Discounting, Ergodicity and Convergence for Markov Decision Processes

The rate at which Markov decision processes converge as the horizon length increases can be important for computations and judging the appropriateness of models. The convergence rate is commonly associated with the discount factor \alpha . For example, the total value function for a broad set of problems is known to converge 0(\alpha n ), i.e., geometrically with the discount factor. But the rate at which the finite horizon optimal policies converge depends on the convergence of the relative value function. (Relative value at a given state is the difference between total value at that state and total value at some fixed reference state.) Relative value convergence in turn depends both on the discount factor and on ergodic properties of the underlying nonhomogeneous Markov chains. We show in particular that for the stationary finite state space compact action space Markov decision problem, the relative value function converges 0((\alpha \lambda) n ) for all \lambda > r(P), the argument of the subdominant eigenvalue of the optimal infinite horizon policy (assumed unique). Easily obtained bounds for r(P) are also given which are related to those of A. Brauer. Under additional restrictions, policy convergence is shown to be of the same order as relative value convergence, generalizing work of Shapiro, Schweitzer, and Odoni. The same result gives convergence properties for the undiscounted problem and for the case \alpha > 1. If \alpha r(P) > 1 the problem does not converge. As a by-product of the analysis, necessary conditions are given for the relative value function to converge 0((\alpha \lambda) n ), 0