Discounting, Ergodicity and Convergence for Markov Decision Processes

Thomas E. Morton and William E. Wecker
Additional contact information
Thomas E. Morton: Carnegie-Mellon University
William E. Wecker: University of Chicago

Management Science, 1977, vol. 23, issue 8, 890-900

Abstract: 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

Date: 1977
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.23.8.890 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:23:y:1977:i:8:p:890-900

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().