Stochastic Approximations for Finite-State Markov Chains.

Abstract

In constrained Markov decision problems, optimal policies are often found to depend on quantities which are not readily available due either to insufficient knowledge of the model parameters or to computational difficulties. Thia motivates the on-line estimation (or computation) problem investigated in this paper in the context of a single parameter family of finite-state Markov chains. The computation is implemented through an algorithm of the Stochastic Approximations type which recursively generates on-line estimates for the unknown value. A useful methodology is outlined for investigating the strong consistency of the algorithm and the proof is carried out under a set of simplifying assumptions in order to illustrate the key ideas unencumbered with technical details. An application to constrained Markov deciaion processes is briefly discussed.