On the existence and memory requirements of convergent on-line decision rules

We observe a countable family of real valued sequences J_p, p ε P, and we want to design a decision rule that at each time k selects a parameter p ε P based on the past observations in such a way that the decisions converge to some q ε P with the q^th data sequence having desirable properties, e.g., is suitably bounded or converges to zero. In a general setting we give a positive result that there exist decision rules with countable memory that converge (in finite time) to a 'correct selection'. These decision rules are robust in a sense made precise in the paper. In addition, we demonstrate that there does not exist a decision rule with finite memory that has this property. This type of problem arises in a variety of contexts such as on-line model selection and on-line controller selection.