mlsanityData to 14 Oct 2026

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

arXiv 2409.15703 ↗First posted 24 Sep 2024eess.SY cs.LG cs.SYcited by 9

On the map: Deep reinforcement learning methods → RL theory and sample complexity

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.

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.

Builds on

29 of 112 references.

References · 29

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  2. 2019Dream to Control: Learning Behaviors by Latent Imaginationcited by 1,653
  3. 2021Decision Transformer: Reinforcement Learning via Sequence Modelingcited by 1,546
  4. 2020Mastering Atari with Discrete World Modelscited by 1,007
  5. 2018Recurrent World Models Facilitate Policy Evolutioncited by 785
  6. 2023Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Taskscited by 327
  7. 2019DeepMDP: Learning Continuous Latent Space Models for Representation Learningcited by 207
  8. 2018Lipschitz Continuity in Model-based Reinforcement Learningcited by 91
  9. 2020Approximate information state for approximate planning and reinforcement learning in partially observed systemscited by 70
  10. 2023When Do Transformers Shine in RL? Decoupling Memory from Credit Assignmentcited by 63
  11. 2021Reinforcement Learning, Bit by Bitcited by 59
  12. 2024Bridging State and History Representations: Understanding Self-Predictive RLcited by 54
17 more
  1. 2021Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent Statescited by 43
  2. 2021MICo: Improved representations via sampling-based state similarity for Markov decision processescited by 43
  3. 2021Unbiased Asymmetric Reinforcement Learning under Partial Observabilitycited by 25
  4. 2013Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processescited by 24
  5. 2013PEGASUS: A Policy Search Method for Large MDPs and POMDPscited by 22
  6. 2021Convergence of Finite Memory Q-Learning for POMDPs and Near Optimality of Learned Policies under Filter Stabilitycited by 22
  7. 2013Learning Finite-State Controllers for Partially Observable Environmentscited by 19
  8. 2017On overfitting and asymptotic bias in batch reinforcement learning with partial observabilitycited by 16
  9. 2013Solving POMDPs by Searching in Policy Spacecited by 13
  10. 2021Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuitycited by 11
  11. 2022Reinforcement Learning in Non-Markovian Environmentscited by 10
  12. 2023Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environmentscited by 7
  13. 2013Efficient Learning and Planning with Compressed Predictive Statescited by 5
  14. 2023Approximate information state based convergence analysis of recurrent Q-learningcited by 5
  15. 2022Approximate Information States for Worst-case Control of Uncertain Systemscited by 4
  16. 2023Approximate Information States for Worst-Case Control and Learning in Uncertain Systemscited by 3
  17. 2023Worst-Case Control and Learning Using Partial Observations Over an Infinite Time-Horizoncited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 5; 2026: 4.

9 papers.

  1. 2025A Theoretical Justification for Asymmetric Actor-Critic Algorithmscited by 6
  2. 2025Real-World Reinforcement Learning of Active Perception Behaviorscited by 1
  3. 2026Learning to Hand Off: Provably Convergent Workflow Learning under Interface Constraintscited by 1
  4. 2025Convergence of regularized agent-state-based Q-learning in POMDPscited by 0
  5. 2025Agent policies from higher-order causal functionscited by 0
  6. 2025Memoryless Policy Iteration for Episodic POMDPscited by 0
  7. 2026Expanding Spatial and Temporal Context for Robotic Imitation Learning With Scene Graphscited by 0
  8. 2026Adaptive Agent Designcited by 0
  9. 2026From Static Policies to Adaptive Priors in Offline Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Periodic agent-state based Q-learning for POMDPs
  2. 2025Scalable Policy-Based RL Algorithms for POMDPs
  3. 2026Policy Gradient Methods for Non-Markovian Reinforcement Learning
  4. 2023Safe Policy Improvement for POMDPs via Finite-State Controllers
  5. 2024How to Explore with Belief: State Entropy Maximization in POMDPs
  6. 2024Bridging the Gap between Partially Observable Stochastic Games and Sparse POMDP Methods
  7. 2026Belief-State Engine: Augmenting LLMs for Principled Planning Under Partial Observability
  8. 2024Multi-agent Off-policy Actor-Critic Reinforcement Learning for Partially Observable Environments