Asymptotically efficient adaptive allocation schemes for controlled Markov chains: finite parameter space

The authors consider a controlled Markov chain whose transition probabilities and initial distribution are parameterized by an unknown parameter θ to some known parameter space Θ. There is a one-step reward associated with each pair of control and following state of the process. The objective is to maximize the expected value of the sum of one-step rewards over an infinite horizon. By introducing the loss associated with a control scheme, the authors show that the problem is equivalent to minimizing the loss. They define uniformly good adaptive control schemes and restrict attention to these schemes. They develop a lower bound on the loss associated with any uniformly good control scheme. Finally, they construct an adaptive control scheme whose loss equals the lower bound and is therefore optimal