# Scalable Policy-Based RL Algorithms for POMDPs

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 53 references that are in the map.
- First posted on arXiv 8 Oct 2025.

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

- [Deep Recurrent Q-Learning for Partially Observable MDPs](https://mlsanity.com/paper/1507.06527/) (2015)
- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Deep Variational Reinforcement Learning for POMDPs](https://mlsanity.com/paper/1806.02426/) (2018)
- [When Is Partially Observable Reinforcement Learning Not Scary?](https://mlsanity.com/paper/2204.08967/) (2022)
- [Near Optimal Behavior via Approximate State Abstraction](https://mlsanity.com/paper/1701.04113/) (2017)
- [Sample-Efficient Reinforcement Learning of Undercomplete POMDPs](https://mlsanity.com/paper/2006.12484/) (2020)
- [Reinforcement Learning of POMDPs using Spectral Methods](https://mlsanity.com/paper/1602.07764/) (2016)
- [Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs](https://mlsanity.com/paper/2010.00587/) (2020)
- [Provable Reinforcement Learning with a Short-Term Memory](https://mlsanity.com/paper/2202.03983/) (2022)
- [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)
- [Convergence of Finite Memory Q-Learning for POMDPs and Near Optimality of Learned Policies under Filter Stability](https://mlsanity.com/paper/2103.12158/) (2021)
- [Learning Finite-State Controllers for Partially Observable Environments](https://mlsanity.com/paper/1301.6721/) (2013)
- [Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiency](https://mlsanity.com/paper/2205.13476/) (2022)
- [A Simple Finite-Time Analysis of TD Learning with Linear Function Approximation](https://mlsanity.com/paper/2403.02476/) (2024)
- [Finite-Time Analysis of Natural Actor-Critic for POMDPs](https://mlsanity.com/paper/2202.09753/) (2022)
- [Recurrent Natural Policy Gradient for POMDPs](https://mlsanity.com/paper/2405.18221/) (2024)
- [Learning to Represent Haptic Feedback for Partially-Observable Tasks](https://mlsanity.com/paper/1705.06243/) (2017)

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

- [When the Specification Emerges: Benchmarking Faithfulness Loss in Long-Horizon Coding Agents](https://mlsanity.com/paper/2603.17104/) (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)
- [Adaptive Agent Design](https://mlsanity.com/paper/2609.12486/) (2026)

## Abstract (arXiv)

The continuous nature of belief states in POMDPs presents significant computational challenges in learning the optimal policy. In this paper, we consider an approach that solves a Partially Observable Reinforcement Learning (PORL) problem by approximating the corresponding POMDP model into a finite-state Markov Decision Process (MDP) (called Superstate MDP). We first derive theoretical guarantees that improve upon prior work that relate the optimal value function of the transformed Superstate MDP to the optimal value function of the original POMDP. Next, we propose a policy-based learning approach with linear function approximation to learn the optimal policy for the Superstate MDP. Consequently, our approach shows that a POMDP can be approximately solved using TD-learning followed by Policy Optimization by treating it as an MDP, where the MDP state corresponds to a finite history. We show that the approximation error decreases exponentially with the length of this history. To the best of our knowledge, our finite-time bounds are the first to explicitly quantify the error introduced when applying standard TD learning to a setting where the true dynamics are not Markovian.