Asymptotically Efficient Adaptive Allocation Schemes for Controlled Markov Chains: Finite Parameter Space.

Consider a controlled Markov chain whose transition probabilities and initial distribution are parametrized by an unknown parameter Theta belonging to some known parameter space Theta. There is a one-step reward associated with each pair of control and the 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 problem is equivalent to minimizing this Loss. Define a uniformly good adaptive control schemes and restrict attention to these schemes. A lower bound is developed on the Loss associated with any uniformly good control scheme. Finally, an adaptive control scheme is constructed whose Loss equals the lower bound, and is therefore optimal. Keywords: Adaptive control scheme; Controlled Markov chain; Asymptotically optimal.
Prepared in cooperation with Cornell Univ., Ithaca, NY. School of Electrical Engineering.