Asymptotic properties of constrained Markov Decision Processes |
| |
Authors: | Eitan Altman |
| |
Affiliation: | (1) Centre Sophia Antipolis, INRIA, 06565 Valbonne Cedex, France |
| |
Abstract: | We present in this paper several asymptotic properties of constrained Markov Decision Processes (MDPs) with a countable state space. We treat both the discounted and the expected average cost, with unbounded cost. We are interested in (1) the convergence of finite horizon MDPs to the infinite horizon MDP, (2) convergence of MDPs with a truncated state space to the problem with infinite state space, (3) convergence of MDPs as the discount factor goes to a limit. In all these cases we establish the convergence of optimal values and policies. Moreover, based on the optimal policy for the limiting problem, we construct policies which are almost optimal for the other (approximating) problems. Based on the convergence of MDPs with a truncated state space to the problem with infinite state space, we show that an optimal stationary policy exists such that the number of randomisations it uses is less or equal to the number of constraints plus one. We finally apply the results to a dynamic scheduling problem.This work was partially supported by the Chateaubriand fellowship from the French embassy in Israel and by the European Grant BRA-QMIPS of CEC DG XIII |
| |
Keywords: | Constrained Markov Decision Processes countable state space finite horizon infinite horizon finite approximations asymptotic properties dynamic scheduling |
本文献已被 SpringerLink 等数据库收录! |
|