Stochastic Approximations for Finite-State Markov Chains.

摘要

In constrained Markov decision problems, optimal policies are often found to depend on quantities that are not readily available due to either insufficient knowledge of the model parameters or computational difficulties. This 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 to illustrate the key ideas unencumbered with technical details. An application to constrained Markov decision processes is briefly discussed.