# Agent-state based policies in POMDPs: Beyond belief-state MDPs

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 29 of its 112 references that are in the map.
- First posted on arXiv 24 Sep 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Dream to Control: Learning Behaviors by Latent Imagination](https://mlsanity.com/paper/1912.01603/) (2019)
- [Decision Transformer: Reinforcement Learning via Sequence Modeling](https://mlsanity.com/paper/2106.01345/) (2021)
- [Mastering Atari with Discrete World Models](https://mlsanity.com/paper/2010.02193/) (2020)
- [Recurrent World Models Facilitate Policy Evolution](https://mlsanity.com/paper/1809.01999/) (2018)
- [Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Tasks](https://mlsanity.com/paper/2306.13831/) (2023)
- [DeepMDP: Learning Continuous Latent Space Models for Representation Learning](https://mlsanity.com/paper/1906.02736/) (2019)
- [Lipschitz Continuity in Model-based Reinforcement Learning](https://mlsanity.com/paper/1804.07193/) (2018)
- [Approximate information state for approximate planning and reinforcement learning in partially observed systems](https://mlsanity.com/paper/2010.08843/) (2020)
- [When Do Transformers Shine in RL? Decoupling Memory from Credit Assignment](https://mlsanity.com/paper/2307.03864/) (2023)
- [Reinforcement Learning, Bit by Bit](https://mlsanity.com/paper/2103.04047/) (2021)
- [Bridging State and History Representations: Understanding Self-Predictive RL](https://mlsanity.com/paper/2401.08898/) (2024)
- [Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent States](https://mlsanity.com/paper/2102.05261/) (2021)
- [MICo: Improved representations via sampling-based state similarity for Markov decision processes](https://mlsanity.com/paper/2106.08229/) (2021)
- [Unbiased Asymmetric Reinforcement Learning under Partial Observability](https://mlsanity.com/paper/2105.11674/) (2021)
- [Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes](https://mlsanity.com/paper/1302.1525/) (2013)
- [PEGASUS: A Policy Search Method for Large MDPs and POMDPs](https://mlsanity.com/paper/1301.3878/) (2013)
- [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)
- [On overfitting and asymptotic bias in batch reinforcement learning with partial observability](https://mlsanity.com/paper/1709.07796/) (2017)
- [Solving POMDPs by Searching in Policy Space](https://mlsanity.com/paper/1301.7380/) (2013)
- [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)
- [Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environments](https://mlsanity.com/paper/2311.00123/) (2023)
- [Efficient Learning and Planning with Compressed Predictive States](https://mlsanity.com/paper/1312.0286/) (2013)
- [Approximate information state based convergence analysis of recurrent Q-learning](https://mlsanity.com/paper/2306.05991/) (2023)
- [Approximate Information States for Worst-case Control of Uncertain Systems](https://mlsanity.com/paper/2203.15271/) (2022)
- [Approximate Information States for Worst-Case Control and Learning in Uncertain Systems](https://mlsanity.com/paper/2301.05089/) (2023)
- [Worst-Case Control and Learning Using Partial Observations Over an Infinite Time-Horizon](https://mlsanity.com/paper/2303.16321/) (2023)

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

- [A Theoretical Justification for Asymmetric Actor-Critic Algorithms](https://mlsanity.com/paper/2501.19116/) (2025)
- [Real-World Reinforcement Learning of Active Perception Behaviors](https://mlsanity.com/paper/2512.01188/) (2025)
- [Learning to Hand Off: Provably Convergent Workflow Learning under Interface Constraints](https://mlsanity.com/paper/2605.19140/) (2026)
- [Convergence of regularized agent-state-based Q-learning in POMDPs](https://mlsanity.com/paper/2508.21314/) (2025)
- [Agent policies from higher-order causal functions](https://mlsanity.com/paper/2512.10937/) (2025)
- [Memoryless Policy Iteration for Episodic POMDPs](https://mlsanity.com/paper/2512.11082/) (2025)
- [Expanding Spatial and Temporal Context for Robotic Imitation Learning With Scene Graphs](https://mlsanity.com/paper/2606.01072/) (2026)
- [Adaptive Agent Design](https://mlsanity.com/paper/2609.12486/) (2026)
- [From Static Policies to Adaptive Priors in Offline Reinforcement Learning](https://mlsanity.com/paper/2609.35880/) (2026)

## Abstract (arXiv)

The traditional approach to POMDPs is to convert them into fully observed MDPs by considering a belief state as an information state. However, a belief-state based approach requires perfect knowledge of the system dynamics and is therefore not applicable in the learning setting where the system model is unknown. Various approaches to circumvent this limitation have been proposed in the literature. We present a unified treatment of some of these approaches by viewing them as models where the agent maintains a local recursively updateable agent state and chooses actions based on the agent state. We highlight the different classes of agent-state based policies and the various approaches that have been proposed in the literature to find good policies within each class. These include the designer's approach to find optimal non-stationary agent-state based policies, policy search approaches to find a locally optimal stationary agent-state based policies, and the approximate information state to find approximately optimal stationary agent-state based policies. We then present how ideas from the approximate information state approach have been used to improve Q-learning and actor-critic algorithms for learning in POMDPs.