Rate of Convergence of Empirical Measures and Costs in Controlled Markov Chains and Transient Optimality

The purpose of this paper is two fold. First, bounds on the rate of convergence of empirical measures in controlled Markov chains are obtained under some recurrence conditions. These include bounds obtained through large deviations and central limit theorem arguments. These results are then applied to optimal control problems. Bounds on the rate of convergence of the empirical measures that are uniform over different sets of policies are derived, resulting in bounds on the rate of convergence of the costs. Finally, new optimal control problems that involve not only average cost criteria but also measures on the transient behavior of the cost, namely the rate of convergence, are introduced and applied to a problem in telecommunications. The solution to these problems rely on the bounds introduced in previous sections.