# Convergence of Finite Memory Q-Learning for POMDPs and Near Optimality of Learned Policies under Filter Stability

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 48 references that are in the map.
- First posted on arXiv 22 Mar 2021.

## Builds on (most cited first, 9 of 9)

- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [Partially Observed Markov Decision Processes. Problem Sets and Internet Supplement](https://mlsanity.com/paper/1604.08127/) (2016)
- [Near Optimality of Finite Memory Feedback Policies in Partially Observed Markov Decision Processes](https://mlsanity.com/paper/2010.07452/) (2020)
- [Asymptotic Optimality of Finite Approximations to Markov Decision Processes with Borel Spaces](https://mlsanity.com/paper/1503.02244/) (2015)
- [Solving POMDPs by Searching in Policy Space](https://mlsanity.com/paper/1301.7380/) (2013)
- [Partially Observable Total-Cost Markov Decision Processes with Weakly Continuous Transition Probabilities](https://mlsanity.com/paper/1401.2168/) (2014)
- [Weak Feller Property of Non-linear Filters](https://mlsanity.com/paper/1812.05509/) (2018)
- [Finite Model Approximations for Partially Observed Markov Decision Processes with Discounted Cost](https://mlsanity.com/paper/1710.07009/) (2017)

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

- [Finite-Time Analysis of Natural Actor-Critic for POMDPs](https://mlsanity.com/paper/2202.09753/) (2022)
- [Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuity](https://mlsanity.com/paper/2111.06781/) (2021)
- [Reinforcement Learning in Non-Markovian Environments](https://mlsanity.com/paper/2211.01595/) (2022)
- [Agent-state based policies in POMDPs: Beyond belief-state MDPs](https://mlsanity.com/paper/2409.15703/) (2024)
- [Recurrent Natural Policy Gradient for POMDPs](https://mlsanity.com/paper/2405.18221/) (2024)
- [Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environments](https://mlsanity.com/paper/2311.00123/) (2023)
- [Periodic agent-state based Q-learning for POMDPs](https://mlsanity.com/paper/2407.06121/) (2024)
- [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)
- [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)
- [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)
- [Learning to Hand Off: Provably Convergent Workflow Learning under Interface Constraints](https://mlsanity.com/paper/2605.19140/) (2026)
- [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)
- [Learning POMDPs with Linear Function Approximation and Finite Memory](https://mlsanity.com/paper/2505.14879/) (2025)
- [Convergence of regularized agent-state-based Q-learning in POMDPs](https://mlsanity.com/paper/2508.21314/) (2025)
- [Reinforcement Learning with Function Approximation for Non-Markov Processes](https://mlsanity.com/paper/2601.00151/) (2026)
- [Learning Suffers More Than the Policy Class Under Partial Observability: A Closed-Form Analysis](https://mlsanity.com/paper/2608.07228/) (2026)
- [Adaptive Agent Design](https://mlsanity.com/paper/2609.12486/) (2026)

## Abstract (arXiv)

In this paper, for POMDPs, we provide the convergence of a Q learning algorithm for control policies using a finite history of past observations and control actions, and, consequentially, we establish near optimality of such limit Q functions under explicit filter stability conditions. We present explicit error bounds relating the approximation error to the length of the finite history window. We establish the convergence of such Q-learning iterations under mild ergodicity assumptions on the state process during the exploration phase. We further show that the limit fixed point equation gives an optimal solution for an approximate belief-MDP. We then provide bounds on the performance of the policy obtained using the limit Q values compared to the performance of the optimal policy for the POMDP, where we also present explicit conditions using recent results on filter stability in controlled POMDPs. While there exist many experimental results, (i) the rigorous asymptotic convergence (to an approximate MDP value function) for such finite-memory Q-learning algorithms, and (ii) the near optimality with an explicit rate of convergence (in the memory size) are results that are new to the literature, to our knowledge.