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

arXiv: https://arxiv.org/abs/1503.02244 · HTML: https://mlsanity.com/paper/1503.02244/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Mar 2015.

## Built on by (most cited first, 14 of 14)

- [Convergence of Finite Memory Q-Learning for POMDPs and Near Optimality of Learned Policies under Filter Stability](https://mlsanity.com/paper/2103.12158/) (2021)
- [Sublinear Regret for Learning POMDPs](https://mlsanity.com/paper/2107.03635/) (2021)
- [Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuity](https://mlsanity.com/paper/2111.06781/) (2021)
- [Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environments](https://mlsanity.com/paper/2311.00123/) (2023)
- [Online Incident Response Planning under Model Misspecification through Bayesian Learning and Belief Quantization](https://mlsanity.com/paper/2508.14385/) (2025)
- [Finite Memory Belief Approximation for Optimal Control in Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2601.03132/) (2026)
- [Intermittently Observable Markov Decision Processes](https://mlsanity.com/paper/2302.11761/) (2023)
- [Quantizer Design for Finite Model Approximations, Model Learning, and Quantized Q-Learning for MDPs with Unbounded Spaces](https://mlsanity.com/paper/2510.04355/) (2025)
- [Model approximation in MDPs with unbounded per-step cost](https://mlsanity.com/paper/2402.08813/) (2024)
- [Hyperspace Neighbor Penetration Approach to Dynamic Programming for Model-Based Reinforcement Learning Problems with Slowly Changing Variables in A Continuous State Space](https://mlsanity.com/paper/2106.05497/) (2021)
- [Decentralized Multi-Agent Reinforcement Learning for Continuous-Space Stochastic Games](https://mlsanity.com/paper/2303.13539/) (2023)
- [Refined Bounds on Near Optimality Finite Window Policies in POMDPs and Their Reinforcement Learning](https://mlsanity.com/paper/2409.04351/) (2024)
- [Reinforcement Learning for Jointly Optimal Coding and Control Policies for a Controlled Markovian System over a Communication Channel](https://mlsanity.com/paper/2411.13884/) (2024)
- [Reinforcement Learning for Discounted and Ergodic Control of Diffusion Processes](https://mlsanity.com/paper/2603.13155/) (2026)

## Abstract (arXiv)

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.