mlsanityData to 7 Oct 2026

Lower Bounds for Learning in Revealing POMDPs

arXiv 2302.01333 ↗First posted 2 Feb 2023cs.LG cs.IT math.ITcited by 14

Not on the map. Why?

Abstract (arXiv)

This paper studies the fundamental limits of reinforcement learning (RL) in the challenging partially observable setting. While it is well-established that learning in Partially Observable Markov Decision Processes (POMDPs) requires exponentially many samples in the worst case, a surge of recent work shows that polynomial sample complexities are achievable under the revealing condition -- A natural condition that requires the observables to reveal some information about the unobserved latent states. However, the fundamental limits for learning in revealing POMDPs are much less understood, with existing lower bounds being rather preliminary and having substantial gaps from the current best upper bounds. We establish strong PAC and regret lower bounds for learning in revealing POMDPs. Our lower bounds scale polynomially in all relevant problem parameters in a multiplicative fashion, and achieve significantly smaller gaps against the current best upper bounds, providing a solid starting point for future studies. In particular, for multi-step revealing POMDPs, we show that (1) the latent state-space dependence is at least Omega(S1.5) in the PAC sample complexity, which is notably harder than the widetildeTheta(S) scaling for fully-observable MDPs; (2) Any polynomial sublinear regret is at least Omega(T2/3), suggesting its fundamental difference from the single-step case where widetildeO(√T) regret is achievable. Technically, our hard instance construction adapts techniques in distribution testing, which is new to the RL literature and may be of independent interest.

Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). Builds on 25 of its 46 references that are in the map. First posted on arXiv 2 Feb 2023.

Builds on

25 of 46 references.

References · 25

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  3. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  4. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  5. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  6. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  7. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  8. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  9. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  10. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
  11. 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
  12. 2022GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyondcited by 45
13 more
  1. 2022PAC Reinforcement Learning for Predictive State Representationscited by 42
  2. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  3. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  4. 2022On the Complexity of Adversarial Decision Makingcited by 32
  5. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  6. 2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 26
  7. 2022Planning in Observable POMDPs in Quasipolynomial Timecited by 25
  8. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  9. 2022Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiencycited by 16
  10. 2022Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiencycited by 15
  11. 2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
  12. 2022Unified Algorithms for RL with Decision-Estimation Coefficients: PAC, Reward-Free, Preference-Based Learning, and Beyondcited by 10
  13. 2022Optimistic MLE -- A Generic Model-based Algorithm for Partially Observable Sequential Decision Makingcited by 6

Built on by

Cited by year (2026 to 7 Oct)

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

14 papers.

Sort:

By area:

  1. 2025A Survey on Active Feature Acquisition Strategiescited by 16
  2. 2024Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnabilitycited by 11
  3. 2024On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluationcited by 9
  4. 2024RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluationcited by 5
  5. 2023Efficient Reinforcement Learning with Impaired Observability: Learning to Act with Delayed and Missing State Observationscited by 4
  6. 2023Prospective Side Information for Latent MDPscited by 4
  7. 2023Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsightcited by 3
  8. 2024Near-Optimal Learning and Planning in Separated Latent MDPscited by 3
  9. 2024A Theoretical Framework for Partially Observed Reward-States in RLHFcited by 1
  10. 2026Toward Learning POMDPs Beyond Full-Rank Actions and State Observabilitycited by 1
  11. 2023Near-Optimal Partially Observable Reinforcement Learning with Partial Online State Informationcited by 0
  12. 2023Posterior Sampling-based Online Learning for Episodic POMDPscited by 0
2 more
  1. 2025Achieving widetildeO(√T) Regret in Average-Reward POMDPs with Known Observation Modelscited by 0
  2. 2025Learning Causal States Under Partial Observability and Perturbationcited by 0