Contraction mappings underlying undiscounted Markov decision problems |
| |
Authors: | A Federgruen PJ Schweitzer HC Tijms |
| |
Institution: | 1. Mathematisch Centrum, Amsterdam, Netherlands;2. Graduate School of Management, University of Rochester, Rochester, New York 14627 U.S.A.;3. Mathematisch Centrum/Vrije Universiteit, Amsterdam Netherlands |
| |
Abstract: | This paper is concerned with the properties of the value-iteration operator0 which arises in undiscounted Markov decision problems. We give both necessary and sufficient conditions for this operator to reduce to a contraction operator, in which case it is easy to show that the value-iteration method exhibits a uniform geometric convergence rate. As necessary conditions we obtain a number of important characterizations of the chain and periodicity structures of the problem, and as sufficient conditions, we give a general “scrambling-type” recurrency condition, which encompasses a number of important special cases. Next, we show that a data transformation turns every unichained undiscounted Markov Renewal Program into an equivalent undiscounted Markov decision problem, in which the value-iteration operator is contracting, because it satisfies this “scrambling-type” condition. We exploit this contraction property in order to obtain lower and upper bounds as well as variational characterizations for the fixed point of the optimality equation and a test for eliminating suboptimal actions. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|