mlsanityData to 7 Oct 2026

Learning in Observable POMDPs, without Computationally Intractable Oracles

arXiv 2206.03446 ↗First posted 7 Jun 2022cs.LG cs.AI cs.DScited by 30

Not on the map. Why?

Abstract (arXiv)

Much of reinforcement learning theory is built on top of oracles that are computationally hard to implement. Specifically for learning near-optimal policies in Partially Observable Markov Decision Processes (POMDPs), existing algorithms either need to make strong assumptions about the model dynamics (e.g. deterministic transitions) or assume access to an oracle for solving a hard optimistic planning or estimation problem as a subroutine. In this work we develop the first oracle-free learning algorithm for POMDPs under reasonable assumptions. Specifically, we give a quasipolynomial-time end-to-end algorithm for learning in "observable" POMDPs, where observability is the assumption that well-separated distributions over states induce well-separated distributions over observations. Our techniques circumvent the more traditional approach of using the principle of optimism under uncertainty to promote exploration, and instead give a novel application of barycentric spanners to constructing policy covers.

Key facts. Cited by 30 papers in the map (data through 7 Oct 2026). Builds on 34 of its 93 references that are in the map. First posted on arXiv 7 Jun 2022.

Builds on

34 of 93 references.

References · 34

  1. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  2. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  3. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  4. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  5. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  6. 2021Recurrent Model-Free RL Can Be a Strong Baseline for Many POMDPscited by 115
  7. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  8. 2016DESPOT: Online POMDP Planning with Regularizationcited by 105
  9. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  10. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  11. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
  12. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
22 more
  1. 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
  2. 2021Memory-based Deep Reinforcement Learning for POMDPscited by 53
  3. 2016The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Banditscited by 48
  4. 2019Variational Recurrent Models for Solving Partially Observable Control Taskscited by 46
  5. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  6. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  7. 2014Online Planning Algorithms for POMDPscited by 42
  8. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  9. 2016A PAC RL Algorithm for Episodic POMDPscited by 37
  10. 2013Solving POMDPs by Searching the Space of Finite Policiescited by 25
  11. 2022Planning in Observable POMDPs in Quasipolynomial Timecited by 25
  12. 2013Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processescited by 24
  13. 2020Robust Finite-State Controllers for Uncertain POMDPscited by 23
  14. 2021Sublinear Regret for Learning POMDPscited by 19
  15. 2021On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Functioncited by 17
  16. 2021Online Learning for Unknown Partially Observable MDPscited by 17
  17. 2018Bayesian Reinforcement Learning in Factored POMDPscited by 15
  18. 2021Reinforcement Learning in Reward-Mixing MDPscited by 15
  19. 2013Solving POMDPs by Searching in Policy Spacecited by 13
  20. 2016Open Problem: Approximate Planning of POMDPs in the class of Memoryless Policiescited by 4
  21. 2017Permissive Finite-State Controllers of POMDPs using Parameter Synthesiscited by 4
  22. 2022Computational-Statistical Gaps in Reinforcement Learningcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 5; 2023: 10; 2024: 7; 2025: 3; 2026: 5.

30 papers.

Sort:

By area:

  1. 2022PAC Reinforcement Learning for Predictive State Representationscited by 42
  2. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  3. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  4. 2023Efficient Model-Free Exploration in Low-Rank MDPscited by 16
  5. 2023Lower Bounds for Learning in Revealing POMDPscited by 14
  6. 2023Provable Representation with Efficient Planning for Partial Observable Reinforcement Learningcited by 10
  7. 2023Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learningcited by 9
  8. 2024Monitored Markov Decision Processescited by 9
  9. 2023Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDPcited by 8
  10. 2025Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPscited by 7
  11. 2022Optimistic MLE -- A Generic Model-based Algorithm for Partially Observable Sequential Decision Makingcited by 6
  12. 2023Provably Efficient UCB-type Algorithms For Learning Predictive State Representationscited by 6
18 more
  1. 2022Reward-Mixing MDPs with a Few Latent Contexts are Learnablecited by 5
  2. 2023Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oraclescited by 5
  3. 2024RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluationcited by 5
  4. 2023Exponential Hardness of Reinforcement Learning with Linear Function Approximationcited by 4
  5. 2023Prospective Side Information for Latent MDPscited by 4
  6. 2024Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actionscited by 4
  7. 2024Near-Optimal Learning and Planning in Separated Latent MDPscited by 3
  8. 2025To Distill or Decide? Understanding the Algorithmic Trade-off in Partially Observable Reinforcement Learningcited 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. 2026Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsamplingcited by 2
  12. 2024A Theoretical Framework for Partially Observed Reward-States in RLHFcited by 1
  13. 2024Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimationcited by 1
  14. 2026Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPscited by 1
  15. 2026Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamicscited by 1
  16. 2024Provably Efficient Partially Observable Risk-Sensitive Reinforcement Learning with Hindsight Observationcited by 0
  17. 2026End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitionscited by 0
  18. 2026Missingness-MDPs: Bridging the Theory of Missing Data and POMDPscited by 0