ASYMPTOTICALLY EFFICIENT ADAPTIVE CHOICE OF CONTROL LAWS IN CONTROLLED MARKOV-CHAINS

We consider a controlled Markov chain on a general state space whose t ransition probabilities are parameterized by an unknown parameter belo nging to a compact metric space. There is a one-step reward associated with each pair of control and the following state of the process. Giv en a finite set of stationary control laws, under each of which the Ma rkov chain is uniformly recurrent, an optimal control law in this set is one that maximizes the long-run average reward. In ignorance of the parameter value, we construct an adaptive control rule which uses the optimal control law(s) at a relative frequency of 1-O(n(-1) log n) an d show that this relative frequency gives an asymptotically optimal ba lance between the control objective and the amount of information need ed to learn about the unknown parameter. The basic idea underlying thi s construction is to introduce suitable ''uncertainty adjustments'' vi a sequential testing theory into the certainty-equivalence rule, thus resolving the apparent dilemma between control and information.