mlsanityData to 7 Oct 2026

Planning in Observable POMDPs in Quasipolynomial Time

arXiv 2201.04735 ↗First posted 12 Jan 2022cs.LG cs.DS math.OCcited by 25

Not on the map. Why?

Abstract (arXiv)

Partially Observable Markov Decision Processes (POMDPs) are a natural and general model in reinforcement learning that take into account the agent's uncertainty about its current state. In the literature on POMDPs, it is customary to assume access to a planning oracle that computes an optimal policy when the parameters are known, even though the problem is known to be computationally hard. Almost all existing planning algorithms either run in exponential time, lack provable performance guarantees, or require placing strong assumptions on the transition dynamics under every possible policy. In this work, we revisit the planning problem and ask: are there natural and well-motivated assumptions that make planning easy? Our main result is a quasipolynomial-time algorithm for planning in (one-step) observable POMDPs. Specifically, we assume that well-separated distributions on states lead to well-separated distributions on observations, and thus the observations are at least somewhat informative in each step. Crucially, this assumption places no restrictions on the transition dynamics of the POMDP; nevertheless, it implies that near-optimal policies admit quasi-succinct descriptions, which is not true in general (under standard hardness assumptions). Our analysis is based on new quantitative bounds for filter stability -- i.e. the rate at which an optimal filter for the latent state forgets its initialization. Furthermore, we prove matching hardness for planning in observable POMDPs under the Exponential Time Hypothesis.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). Builds on 19 of its 68 references that are in the map. First posted on arXiv 12 Jan 2022.

Builds on

19 of 68 references.

References · 19

  1. 2015Deep Recurrent Q-Learning for Partially Observable MDPscited by 457
  2. 2016DESPOT: Online POMDP Planning with Regularizationcited by 105
  3. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
  4. 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
  5. 2016Reinforcement Learning of POMDPs using Spectral Methodscited by 51
  6. 2014Online Planning Algorithms for POMDPscited by 42
  7. 2016A PAC RL Algorithm for Episodic POMDPscited by 37
  8. 2020POPCORN: Partially Observed Prediction COnstrained ReiNforcement Learningcited by 36
  9. 2013Solving POMDPs by Searching the Space of Finite Policiescited by 25
  10. 2013Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processescited by 24
  11. 2013Tractable Inference for Complex Stochastic Processescited by 20
  12. 2020Near Optimality of Finite Memory Feedback Policies in Partially Observed Markov Decision Processescited by 20
7 more
  1. 2021Sublinear Regret for Learning POMDPscited by 19
  2. 2021Reinforcement Learning in Reward-Mixing MDPscited by 15
  3. 2013Solving POMDPs by Searching in Policy Spacecited by 13
  4. 2016Prediction with a Short Memorycited by 13
  5. 2016Provable Algorithms for Inference in Topic Modelscited by 6
  6. 2021Kalman Filtering with Adversarial Corruptionscited by 6
  7. 2013Approximate Planning for Factored POMDPs using Belief State Simplificationcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 9; 2023: 8; 2024: 5; 2025: 2; 2026: 1.

25 papers.

Sort:

  1. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  2. 2023SayCanPay: Heuristic Planning with Large Language Models using Learnable Domain Knowledgecited by 49
  3. 2022PAC Reinforcement Learning for Predictive State Representationscited by 42
  4. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  5. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  6. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  7. 2022Future-Dependent Value-Based Off-Policy Evaluation in POMDPscited by 20
  8. 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 17
  9. 2022Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiencycited by 15
  10. 2023Lower Bounds for Learning in Revealing POMDPscited by 14
  11. 2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
  12. 2024On Limitation of Transformer for Learning HMMscited by 9
13 more
  1. 2023Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDPcited by 8
  2. 2025Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPscited by 7
  3. 2022Optimistic MLE -- A Generic Model-based Algorithm for Partially Observable Sequential Decision Makingcited by 6
  4. 2023Provably Efficient UCB-type Algorithms For Learning Predictive State Representationscited by 6
  5. 2024How to Explore with Belief: State Entropy Maximization in POMDPscited by 6
  6. 2024The Limits of Pure Exploration in POMDPs: When the Observation Entropy is Enoughcited by 6
  7. 2023Exponential Hardness of Reinforcement Learning with Linear Function Approximationcited by 4
  8. 2024Near-Optimal Learning and Planning in Separated Latent MDPscited by 3
  9. 2025Provably Learning from Modern Language Models via Low Logit Rankcited by 3
  10. 2023Posterior Sampling for Competitive RL: Function Approximation and Partial Observationcited by 2
  11. 2023Near-Optimal Partially Observable Reinforcement Learning with Partial Online State Informationcited by 0
  12. 2024Provably Efficient Partially Observable Risk-Sensitive Reinforcement Learning with Hindsight Observationcited by 0
  13. 2026Minimax-Optimal Policy Regret in Partially Observable Markov Gamescited by 0