Paper Info
Title
Finite-State Approximations to Discounted and Average Cost Constrained Markov Decision Processes
Abstract
In this paper, we consider the finite-state approximation of a discrete-time constrained Markov decision process (MDP) under the discounted and average cost criteria. Using the linear programming formulation of the constrained discounted cost problem, we prove the asymptotic convergence of the optimal value of the finite-state model to the optimal value of the original model. With further continuity condition on the transition probability, we also establish a method to compute approximately optimal policies. For the average cost, instead of using the finite-state linear programming approximation method, we use the original problem definition to establish the finite-state asymptotic approximation of the constrained problem and compute approximately optimal policies. Under Lipschitz-type regularity conditions on the components of the MDP, we also obtain explicit rate of convergence bounds quantifying how the approximation improves as the size of the approximating finite-state space increases.
Year
DOI
Venue
2019
10.1109/TAC.2018.2890756
IEEE Transactions on Automatic Control
Keywords
Field
DocType
Computational modeling,Markov processes,Convergence,Cost function,Dynamic programming,Kernel,Linear programming
Convergence (routing),Kernel (linear algebra),Dynamic programming,Mathematical optimization,Markov process,Markov decision process,Average cost,Rate of convergence,Linear programming,Mathematics
Journal
Volume
Issue
ISSN
64
7
0018-9286
Citations 
PageRank 
References 
0
0.34
0
Authors
1
Name
Order
Citations
PageRank
Naci Saldi12910.27