mlsanityData to 7 Oct 2026

Sample-Efficient Reinforcement Learning of Undercomplete POMDPs

arXiv 2006.12484 ↗First posted 22 Jun 2020cs.LG cs.AI math.OCcited by 66

Not on the map. Why?

Abstract (arXiv)

Partial observability is a common challenge in many reinforcement learning applications, which requires an agent to maintain memory, infer latent states, and integrate this past information into exploration. This challenge leads to a number of computational and statistical hardness results for learning general Partially Observable Markov Decision Processes (POMDPs). This work shows that these hardness barriers do not preclude efficient reinforcement learning for rich and interesting subclasses of POMDPs. In particular, we present a sample-efficient algorithm, OOM-UCB, for episodic finite undercomplete POMDPs, where the number of observations is larger than the number of latent states and where exploration is essential for learning, thus distinguishing our results from prior works. OOM-UCB achieves an optimal sample complexity of tildeO(1/varepsilon2) for finding an varepsilon-optimal policy, along with being polynomial in all other relevant quantities. As an interesting special case, we also provide a computationally and statistically efficient algorithm for POMDPs with deterministic state transitions.

Key facts. Cited by 66 papers in the map (data through 7 Oct 2026). First posted on arXiv 22 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 20; 2023: 13; 2024: 11; 2025: 10; 2026: 7.

66 papers.

Sort:

By area:

  1. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  2. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
  3. 2021Understanding Domain Randomization for Sim-to-real Transfercited by 69
  4. 2023POPGym: Benchmarking Partially Observable Reinforcement Learningcited by 59
  5. 2022PAC Reinforcement Learning for Predictive State Representationscited by 42
  6. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  7. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  8. 2021A Minimax Learning Approach to Off-Policy Evaluation in Confounded Partially Observable Markov Decision Processescited by 34
  9. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  10. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processescited by 26
  11. 2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 26
  12. 2022Planning in Observable POMDPs in Quasipolynomial Timecited by 25
38 more
  1. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  2. 2022Future-Dependent Value-Based Off-Policy Evaluation in POMDPscited by 20
  3. 2022An Instrumental Variable Approach to Confounded Off-Policy Evaluationcited by 20
  4. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
  5. 2021Sublinear Regret for Learning POMDPscited by 19
  6. 2022Off-Policy Evaluation for Episodic Partially Observable Markov Decision Processes under Non-Parametric Modelscited by 18
  7. 2022Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limitscited by 17
  8. 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 17
  9. 2022Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiencycited by 16
  10. 2021Reinforcement Learning in Reward-Mixing MDPscited by 15
  11. 2022Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiencycited by 15
  12. 2023Lower Bounds for Learning in Revealing POMDPscited by 14
  13. 2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
  14. 2025LLM-Guided Probabilistic Program Induction for POMDP Model Estimationcited by 11
  15. 2023Provable Representation with Efficient Planning for Partial Observable Reinforcement Learningcited by 10
  16. 2024On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluationcited by 9
  17. 2023Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDPcited by 8
  18. 2022On the Power of Pre-training for Generalization in RL: Provable Benefits and Hardnesscited by 7
  19. 2023Offline RL with Observation Histories: Analyzing and Improving Sample Complexitycited by 7
  20. 2025Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPscited by 7
  21. 2025PIGDreamer: Privileged Information Guided World Models for Safe Partially Observable Reinforcement Learningcited by 7
  22. 2024Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learningcited by 6
  23. 2024How to Explore with Belief: State Entropy Maximization in POMDPscited by 6
  24. 2024The Limits of Pure Exploration in POMDPs: When the Observation Entropy is Enoughcited by 6
  25. 2024RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluationcited by 5
  26. 2023Efficient Reinforcement Learning with Impaired Observability: Learning to Act with Delayed and Missing State Observationscited by 4
  27. 2025Scalable Policy-Based RL Algorithms for POMDPscited by 4
  28. 2022Blessing from Human-AI Interaction: Super Reinforcement Learning in Confounded Environmentscited by 3
  29. 2022Tractable Optimality in Episodic Latent MABscited by 3
  30. 2023Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsightcited by 3
  31. 2024Near-Optimal Learning and Planning in Separated Latent MDPscited by 3
  32. 2025Reinforcement Learning with Continuous Actions Under Unmeasured Confoundingcited by 3
  33. 2025To Distill or Decide? Understanding the Algorithmic Trade-off in Partially Observable Reinforcement Learningcited by 3
  34. 2024Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learningcited by 2
  35. 2024Tractable Offline Learning of Regular Decision Processescited by 2
  36. 2025Ego-centric Learning of Communicative World Models for Autonomous Drivingcited by 2
  37. 2023Sample-Efficient Multi-Agent RL: An Optimization Perspectivecited by 1
  38. 2024A Theoretical Framework for Partially Observed Reward-States in RLHFcited by 1

50 most cited of 66 All 66 (JSON)