Adaptive control of constrained Markov chains: Criteria and policies

The authors consider the constrained optimization of a finite-state, finite action Markov chain. In the adaptive problem, the transition probabilities are assumed to be unknown, and no prior distribution on their values is given. The authors consider constrained optimization problems in terms of several cost criteria which are asymptotic in nature. For these criteria they show that it is possible to achieve the same optimal cost as in the non-adaptive case. The authors first formulate a constrained optimization problem under each of the cost criteria and establish the existence of optimal stationary policies. Since the adaptive problem is inherently non-stationary, they suggest a class of Asymptotically Stationary (AS) policies, and show that, under each of the cost criteria, the costs of an AS policy depend only on its limiting behavior. This property implies that there exist optimal AS policies. A method for generating adaptive policies is then suggested, which leads to strongly consistent estimators for the unknown transition probabilities. A way to guarantee that these policies are also optimal is to couple them with an adaptive algorithm. This leads to optimal policies for each of the adaptive constrained optimization problems under discussion.