mlsanityData to 7 Oct 2026

When Is Partially Observable Reinforcement Learning Not Scary?

arXiv 2204.08967 ↗First posted 19 Apr 2022cs.LG cs.AI cs.SYcited by 100

Not on the map. Why?

Abstract (arXiv)

Applications of Reinforcement Learning (RL), in which agents learn to make a sequence of decisions despite lacking complete information about the latent states of the controlled system, that is, they act under partial observability of the states, are ubiquitous. Partially observable RL can be notoriously difficult -- well-known information-theoretic results show that learning partially observable Markov decision processes (POMDPs) requires an exponential number of samples in the worst case. Yet, this does not rule out the existence of large subclasses of POMDPs over which learning is tractable. In this paper we identify such a subclass, which we call weakly revealing POMDPs. This family rules out the pathological instances of POMDPs where observations are uninformative to a degree that makes learning hard. We prove that for weakly revealing POMDPs, a simple algorithm combining optimism and Maximum Likelihood Estimation (MLE) is sufficient to guarantee polynomial sample complexity. To the best of our knowledge, this is the first provably sample-efficient result for learning from interactions in overcomplete POMDPs, where the number of latent states can be larger than the number of observations.

Key facts. Cited by 100 papers in the map (data through 7 Oct 2026). Builds on 26 of its 58 references that are in the map. First posted on arXiv 19 Apr 2022.

Builds on

26 of 58 references.

References · 26

  1. 2019Solving Rubik's Cube with a Robot Handcited by 699
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  5. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  6. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  7. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  8. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  9. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  10. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  11. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  12. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
14 more
  1. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  2. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  3. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  4. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
  5. 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
  6. 2016Reinforcement Learning of POMDPs using Spectral Methodscited by 51
  7. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  8. 2016A PAC RL Algorithm for Episodic POMDPscited by 37
  9. 2022Planning in Observable POMDPs in Quasipolynomial Timecited by 25
  10. 2013On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functionscited by 23
  11. 2021Sublinear Regret for Learning POMDPscited by 19
  12. 2021Online Learning for Unknown Partially Observable MDPscited by 17
  13. 2021Reinforcement Learning in Reward-Mixing MDPscited by 15
  14. 2020Reward Biased Maximum Likelihood Estimation for Reinforcement Learningcited by 11

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 14; 2023: 24; 2024: 28; 2025: 22; 2026: 12.

100 papers.

Sort:

By area:

  1. 2024DPO Meets PPO: Reinforced Token Optimization for RLHFcited by 126
  2. 2024RLHF from Heterogeneous Feedback via Personalization and Preference Aggregationcited by 71
  3. 2023Provable Offline Preference-Based Reinforcement Learningcited by 55
  4. 2023Making RL with Preference-based Feedback Efficient via Randomizationcited by 46
  5. 2022PAC Reinforcement Learning for Predictive State Representationscited by 42
  6. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  7. 2023Adversarial Model for Offline Reinforcement Learningcited by 31
  8. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  9. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  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. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
38 more
  1. 2024More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learningcited by 23
  2. 2023On the Provable Advantage of Unsupervised Pretrainingcited by 21
  3. 2022Future-Dependent Value-Based Off-Policy Evaluation in POMDPscited by 20
  4. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
  5. 2024Corruption Robust Offline Reinforcement Learning with Human Feedbackcited by 20
  6. 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 17
  7. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 17
  8. 2022Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiencycited by 16
  9. 2023Lower Bounds for Learning in Revealing POMDPscited by 14
  10. 2023On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximationcited by 13
  11. 2023Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedbackcited by 13
  12. 2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
  13. 2024Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruptioncited by 12
  14. 2023Reinforcement Learning with History-Dependent Dynamic Contextscited by 11
  15. 2023Transformers in Reinforcement Learning: A Surveycited by 11
  16. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Boundscited by 11
  17. 2024Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnabilitycited by 11
  18. 2023Provable Representation with Efficient Planning for Partial Observable Reinforcement Learningcited by 10
  19. 2022ARMOR: A Model-based Framework for Improving Arbitrary Baseline Policies with Offline Datacited by 9
  20. 2022Eluder-based Regret for Stochastic Contextual MDPscited by 9
  21. 2024On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluationcited by 9
  22. 2025Partially Observable Reinforcement Learning with Memory Tracescited by 9
  23. 2023Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDPcited by 8
  24. 2024Recurrent Natural Policy Gradient for POMDPscited by 8
  25. 2024The Central Role of the Loss Function in Reinforcement Learningcited by 8
  26. 2024Mitigating Partial Observability in Sequential Decision Processes via the Lambda Discrepancycited by 7
  27. 2025Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPscited by 7
  28. 2022Optimistic MLE -- A Generic Model-based Algorithm for Partially Observable Sequential Decision Makingcited by 6
  29. 2023A General Framework for Sequential Decision-Making under Adaptivity Constraintscited by 6
  30. 2023Provably Efficient UCB-type Algorithms For Learning Predictive State Representationscited by 6
  31. 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
  32. 2024How to Explore with Belief: State Entropy Maximization in POMDPscited by 6
  33. 2024The Limits of Pure Exploration in POMDPs: When the Observation Entropy is Enoughcited by 6
  34. 2024Exploiting Structure in Offline Multi-Agent RL: The Benefits of Low Interaction Rankcited by 6
  35. 2022Reward-Mixing MDPs with a Few Latent Contexts are Learnablecited by 5
  36. 2024RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluationcited by 5
  37. 2024Uncertainty Representations in State-Space Layers for Deep Reinforcement Learning under Partial Observabilitycited by 5
  38. 2023Prospective Side Information for Latent MDPscited by 4

50 most cited of 100 All 100 (JSON)