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 co nvergence of empirical measures in controlled Markov chains are obtain ed under some recurrence conditions. These include bounds obtained thr ough large deviations and central limit theorem arguments. These resul ts 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 conv ergence of the costs. Finally, new optimal control problems that invol ve not only average cost criteria but also measures on the transient b ehavior of the cost, namely the rate of convergence, are introduced an d applied to a problem in telecommunications. The solution to these pr oblems rely on the bounds introduced in previous sections.