mlsanityData to 7 Oct 2026

Learning in POMDPs is Sample-Efficient with Hindsight Observability

arXiv 2301.13857 ↗First posted 31 Jan 2023cs.LG cs.AI stat.MLcited by 17

Not on the map. Why?

Abstract (arXiv)

POMDPs capture a broad class of decision making problems, but hardness results suggest that learning is intractable even in simple settings due to the inherent partial observability. However, in many realistic problems, more information is either revealed or can be computed during some point of the learning process. Motivated by diverse applications ranging from robotics to data center scheduling, we formulate a Hindsight Observable Markov Decision Process (HOMDP) as a POMDP where the latent states are revealed to the learner in hindsight and only during training. We introduce new algorithms for the tabular and function approximation settings that are provably sample-efficient with hindsight observability, even in POMDPs that would otherwise be statistically intractable. We give a lower bound showing that the tabular algorithm is optimal in its dependence on latent state and observation cardinalities.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). Builds on 41 of its 65 references that are in the map. First posted on arXiv 31 Jan 2023.

Builds on

41 of 65 references.

References · 41

  1. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,861
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2016Learning to reinforcement learncited by 369
  6. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  7. 2019Learning by Cheatingcited by 361
  8. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  9. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  10. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  11. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  12. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
29 more
  1. 2017Asymmetric Actor Critic for Image-Based Robot Learningcited by 202
  2. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  3. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  4. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  5. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  6. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  7. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  8. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  9. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  10. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
  11. 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
  12. 2020Decoupling Exploration and Exploitation for Meta-Reinforcement Learning without Sacrificescited by 59
  13. 2016Reinforcement Learning of POMDPs using Spectral Methodscited by 51
  14. 2022PAC Reinforcement Learning for Predictive State Representationscited by 42
  15. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  16. 2016On Lower Bounds for Regret in Reinforcement Learningcited by 39
  17. 2016A PAC RL Algorithm for Episodic POMDPscited by 37
  18. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 31
  19. 2020Online Model Selection for Reinforcement Learning with Function Approximationcited by 28
  20. 2022Planning in Observable POMDPs in Quasipolynomial Timecited by 25
  21. 2022Hindsight Learning for MDPs with Exogenous Inputscited by 25
  22. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  23. 2020Robust Asymmetric Learning in POMDPscited by 23
  24. 2022Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiencycited by 16
  25. 2022Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiencycited by 15
  26. 2022Oracle Inequalities for Model Selection in Offline Reinforcement Learningcited by 13
  27. 2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
  28. 2020Privileged Information Dropout in Reinforcement Learningcited by 8
  29. 2021Offline RL With Resource Constrained Online Deploymentcited by 1

Built on by

Cited by year

Citing papers per year: 2023: 9; 2024: 5; 2025: 3.

17 papers.

Sort:

By area:

  1. 2024SpecDec++: Boosting Speculative Decoding via Adaptive Candidate Lengthscited by 73
  2. 2025Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPscited by 7
  3. 2023Provably Efficient UCB-type Algorithms For Learning Predictive State Representationscited by 6
  4. 2024Leveraging Approximate Model-based Shielding for Probabilistic Safety Guarantees in Continuous Environmentscited by 5
  5. 2023Efficient Reinforcement Learning with Impaired Observability: Learning to Act with Delayed and Missing State Observationscited by 4
  6. 2023Approximate Model-Based Shielding for Safe Reinforcement Learningcited by 4
  7. 2023Prospective Side Information for Latent MDPscited by 4
  8. 2023Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsightcited by 3
  9. 2024Near-Optimal Learning and Planning in Separated Latent MDPscited by 3
  10. 2025Guided Policy Optimization under Partial Observabilitycited by 3
  11. 2025To Distill or Decide? Understanding the Algorithmic Trade-off in Partially Observable Reinforcement Learningcited by 3
  12. 2024Learning Interpretable Policies in Hindsight-Observable POMDPs through Partially Supervised Reinforcement Learningcited by 2
5 more
  1. 2024Preparing for Black Swans: The Antifragility Imperative for Machine Learningcited by 1
  2. 2023Stochastic Principal-Agent Problems: Efficient Computation and Learningcited by 0
  3. 2023Near-Optimal Partially Observable Reinforcement Learning with Partial Online State Informationcited by 0
  4. 2023Posterior Sampling-based Online Learning for Episodic POMDPscited by 0
  5. 2023Optimizing Heat Alert Issuance with Reinforcement Learningcited by 0