Certainty equivalence control with forcing: revisited

Summary form only given, as follows. Stochastic adaptive optimization problems are considered with the objective of minimizing the rate of increase of the learning loss, i.e. the additional cost one has to pay due to the inbuilt learning tasks in such problems. In particular, an examination is made of two problems: the multiarmed bandit problem, and the adaptive control of Markov chains. Previous work has shown that the minimum rate of increase of the learning loss for these problems is typically O(log n). The schemes that achieve this minimum are quite complicated. The authors show that, with simple schemes of the certainty equivalence control with forcing type, one can come arbitrarily close to the optimal performance. Specifically, they construct a class of schemes so that, for any δ>0, they have a scheme whose learning loss is O((log n)^1+δ)