On the Asymptotic Optimality of Finite Approximations to Markov Decision Processes with Borel Spaces

Naci Saldi (), Serdar Yüksel () and Tamás Linder ()
Additional contact information
Naci Saldi: Coordinated Science Laboratory, University of Illinois, Urbana, Illinois 61801, USA
Serdar Yüksel: Department of Mathematics and Statistics, Queen’s University, Kingston, Ontario, Canada, K7L 3N6
Tamás Linder: Department of Mathematics and Statistics, Queen’s University, Kingston, Ontario, Canada, K7L 3N6

Mathematics of Operations Research, 2017, vol. 42, issue 4, 945-978

Abstract: Calculating optimal policies is known to be computationally difficult for Markov decision processes (MDPs) with Borel state and action spaces. This paper studies finite-state approximations of discrete time Markov decision processes with Borel state and action spaces, for both discounted and average costs criteria. The stationary policies thus obtained are shown to approximate the optimal stationary policy with arbitrary precision under quite general conditions for discounted cost and more restrictive conditions for average cost. For compact-state MDPs, we obtain explicit rate of convergence bounds quantifying how the approximation improves as the size of the approximating finite state space increases. Using information theoretic arguments, the order optimality of the obtained convergence rates is established for a large class of problems. We also show that as a pre-processing step, the action space can also be finitely approximated with sufficiently large number points; thereby, well known algorithms, such as value or policy iteration, Q -learning, etc., can be used to calculate near optimal policies.

Keywords: Markov decision processes; stochastic control; finite state approximation; quantization (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1287/moor.2016.0832 (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:ormoor:v:42:y:2017:i:4:p:945-978

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().