# Near Optimality of Finite Memory Feedback Policies in Partially Observed Markov Decision Processes

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Oct 2020.

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

- [Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent States](https://mlsanity.com/paper/2102.05261/) (2021)
- [Planning in Observable POMDPs in Quasipolynomial Time](https://mlsanity.com/paper/2201.04735/) (2022)
- [Convergence of Finite Memory Q-Learning for POMDPs and Near Optimality of Learned Policies under Filter Stability](https://mlsanity.com/paper/2103.12158/) (2021)
- [Future-Dependent Value-Based Off-Policy Evaluation in POMDPs](https://mlsanity.com/paper/2207.13081/) (2022)
- [Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuity](https://mlsanity.com/paper/2111.06781/) (2021)
- [Common Information based Approximate State Representations in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2110.12603/) (2021)
- [Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environments](https://mlsanity.com/paper/2311.00123/) (2023)
- [Approximate information state based convergence analysis of recurrent Q-learning](https://mlsanity.com/paper/2306.05991/) (2023)
- [Scalable Policy-Based RL Algorithms for POMDPs](https://mlsanity.com/paper/2510.06540/) (2025)
- [Finite Memory Belief Approximation for Optimal Control in Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2601.03132/) (2026)
- [Approximate Information States for Worst-Case Control and Learning in Uncertain Systems](https://mlsanity.com/paper/2301.05089/) (2023)
- [Intermittently Observable Markov Decision Processes](https://mlsanity.com/paper/2302.11761/) (2023)
- [To Distill or Decide? Understanding the Algorithmic Trade-off in Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2510.03207/) (2025)
- [Model approximation in MDPs with unbounded per-step cost](https://mlsanity.com/paper/2402.08813/) (2024)
- [Operator-Theoretic Foundations and Policy Gradient Methods for General MDPs with Unbounded Costs](https://mlsanity.com/paper/2603.17875/) (2026)
- [Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPs](https://mlsanity.com/paper/2604.01024/) (2026)
- [Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamics](https://mlsanity.com/paper/2605.06377/) (2026)
- [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)
- [Learning POMDPs with Linear Function Approximation and Finite Memory](https://mlsanity.com/paper/2505.14879/) (2025)
- [Reinforcement Learning with Function Approximation for Non-Markov Processes](https://mlsanity.com/paper/2601.00151/) (2026)
- [Threshold Structure of Optimal Policies in Restart POMDPs](https://mlsanity.com/paper/2608.10936/) (2026)
- [How Wrong Can a Good Predictor Be? Diverging Updates with Vanishing Predictive KL](https://mlsanity.com/paper/2609.11132/) (2026)

## Abstract (arXiv)

In the theory of Partially Observed Markov Decision Processes (POMDPs), existence of optimal policies have in general been established via converting the original partially observed stochastic control problem to a fully observed one on the belief space, leading to a belief-MDP. However, computing an optimal policy for this fully observed model, and so for the original POMDP, using classical dynamic or linear programming methods is challenging even if the original system has finite state and action spaces, since the state space of the fully observed belief-MDP model is always uncountable. Furthermore, there exist very few rigorous value function approximation and optimal policy approximation results, as regularity conditions needed often require a tedious study involving the spaces of probability measures leading to properties such as Feller continuity. In this paper, we study a planning problem for POMDPs where the system dynamics and measurement channel model are assumed to be known. We construct an approximate belief model by discretizing the belief space using only finite window information variables. We then find optimal policies for the approximate model and we rigorously establish near optimality of the constructed finite window control policies in POMDPs under mild non-linear filter stability conditions and the assumption that the measurement and action sets are finite (and the state space is real vector valued). We also establish a rate of convergence result which relates the finite window memory size and the approximation error bound, where the rate of convergence is exponential under explicit and testable exponential filter stability conditions. While there exist many experimental results and few rigorous asymptotic convergence results, an explicit rate of convergence result is new in the literature, to our knowledge.