On the asymptotic optimality of finite approximations to Markov decision processes with Borel spaces
From MaRDI portal
Publication:4595952
DOI10.1287/MOOR.2016.0832zbMATH Open1417.93337arXiv1503.02244OpenAlexW2964034900MaRDI QIDQ4595952FDOQ4595952
Authors: Naci Saldi, Serdar Yüksel, Tamás Linder 
Publication date: 7 December 2017
Published in: Mathematics of Operations Research (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1503.02244
Recommendations
- Computable approximations for continuous-time Markov decision processes on Borel spaces based on empirical measures
- Approximation of Markov decision processes with general state space
- Approximation of infinite horizon discounted cost Markov decision processes
- Zur konstruktfon ∊-optimaler polltiken in markovschen entscheidungsmodellen mit überabzämbarem zustandsraum
- On finite approximations to Markov decision processes with recursive and nonlinear discounting
Dynamic programming (90C39) Markov and semi-Markov decision processes (90C40) Optimal stochastic control (93E20)
Cited In (22)
- Weak Feller property of non-linear filters
- A low-rank approximation for MDPs via moment coupling
- Efficient approximate planning in continuous space Markovian decision problems
- Robust optimal control using conditional risk mappings in infinite horizon
- Dual-based methods for solving infinite-horizon nonstationary deterministic dynamic programs
- Computable approximations for continuous-time Markov decision processes on Borel spaces based on empirical measures
- Zur konstruktfon ∊-optimaler polltiken in markovschen entscheidungsmodellen mit überabzämbarem zustandsraum
- Robustness to incorrect system models in stochastic control
- Ordinary differential equation methods for Markov decision processes and application to Kullback-Leibler control cost
- Approximation of Markov decision processes with general state space
- Markov decision processes on Borel spaces with total cost and random horizon
- A stability result for linear Markovian stochastic optimization problems
- A perturbation approach to approximate value iteration for average cost Markov decision processes with Borel spaces and bounded costs
- A convex optimization approach to dynamic programming in continuous state and action spaces
- Primal-Dual Regression Approach for Markov Decision Processes with General State and Action Spaces
- Title not available (Why is that?)
- Another look at partially observed optimal stochastic control: existence, ergodicity, and approximations without belief-reduction
- Robustness to approximations and model learning in MDPs and POMDPs
- Approximate policy iteration for Markov decision processes via quantitative adaptive aggregations
- Dual Ascent and Primal-Dual Algorithms for Infinite-Horizon Nonstationary Markov Decision Processes
- A simplex method for countably infinite linear programs
- Continuity of cost in Borkar control topology and implications on discrete space and time approximations for controlled diffusions under several criteria
This page was built for publication: On the asymptotic optimality of finite approximations to Markov decision processes with Borel spaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4595952)
