# When Is Partially Observable Reinforcement Learning Not Scary?

arXiv: https://arxiv.org/abs/2204.08967 · HTML: https://mlsanity.com/paper/2204.08967/

## Key facts

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

## Builds on (most cited first, 26 of 26)

- [Solving Rubik's Cube with a Robot Hand](https://mlsanity.com/paper/1910.07113/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning](https://mlsanity.com/paper/1911.05815/) (2019)
- [RL for Latent MDPs: Regret Guarantees and a Lower Bound](https://mlsanity.com/paper/2102.04939/) (2021)
- [Sample-Efficient Reinforcement Learning of Undercomplete POMDPs](https://mlsanity.com/paper/2006.12484/) (2020)
- [Reinforcement Learning of POMDPs using Spectral Methods](https://mlsanity.com/paper/1602.07764/) (2016)
- [Provable Reinforcement Learning with a Short-Term Memory](https://mlsanity.com/paper/2202.03983/) (2022)
- [A PAC RL Algorithm for Episodic POMDPs](https://mlsanity.com/paper/1605.08062/) (2016)
- [Planning in Observable POMDPs in Quasipolynomial Time](https://mlsanity.com/paper/2201.04735/) (2022)
- [On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions](https://mlsanity.com/paper/1305.2505/) (2013)
- [Sublinear Regret for Learning POMDPs](https://mlsanity.com/paper/2107.03635/) (2021)
- [Online Learning for Unknown Partially Observable MDPs](https://mlsanity.com/paper/2102.12661/) (2021)
- [Reinforcement Learning in Reward-Mixing MDPs](https://mlsanity.com/paper/2110.03743/) (2021)
- [Reward Biased Maximum Likelihood Estimation for Reinforcement Learning](https://mlsanity.com/paper/2011.07738/) (2020)

## Built on by (most cited first, 30 of 100)

- [DPO Meets PPO: Reinforced Token Optimization for RLHF](https://mlsanity.com/paper/2404.18922/) (2024)
- [RLHF from Heterogeneous Feedback via Personalization and Preference Aggregation](https://mlsanity.com/paper/2405.00254/) (2024)
- [Provable Offline Preference-Based Reinforcement Learning](https://mlsanity.com/paper/2305.14816/) (2023)
- [Making RL with Preference-based Feedback Efficient via Randomization](https://mlsanity.com/paper/2310.14554/) (2023)
- [PAC Reinforcement Learning for Predictive State Representations](https://mlsanity.com/paper/2207.05738/) (2022)
- [Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systems](https://mlsanity.com/paper/2206.12020/) (2022)
- [Adversarial Model for Offline Reinforcement Learning](https://mlsanity.com/paper/2302.11048/) (2023)
- [Learning in Observable POMDPs, without Computationally Intractable Oracles](https://mlsanity.com/paper/2206.03446/) (2022)
- [Sample-Efficient Reinforcement Learning of Partially Observable Markov Games](https://mlsanity.com/paper/2206.01315/) (2022)
- [The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learning](https://mlsanity.com/paper/2305.15703/) (2023)
- [Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2205.13589/) (2022)
- [Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithms](https://mlsanity.com/paper/2209.14990/) (2022)
- [More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learning](https://mlsanity.com/paper/2402.07198/) (2024)
- [On the Provable Advantage of Unsupervised Pretraining](https://mlsanity.com/paper/2303.01566/) (2023)
- [Future-Dependent Value-Based Off-Policy Evaluation in POMDPs](https://mlsanity.com/paper/2207.13081/) (2022)
- [Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Exploration](https://mlsanity.com/paper/2305.18258/) (2023)
- [Corruption Robust Offline Reinforcement Learning with Human Feedback](https://mlsanity.com/paper/2402.06734/) (2024)
- [Learning in POMDPs is Sample-Efficient with Hindsight Observability](https://mlsanity.com/paper/2301.13857/) (2023)
- [Reinforcement Learning in Low-Rank MDPs with Density Features](https://mlsanity.com/paper/2302.02252/) (2023)
- [Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiency](https://mlsanity.com/paper/2205.13476/) (2022)
- [Lower Bounds for Learning in Revealing POMDPs](https://mlsanity.com/paper/2302.01333/) (2023)
- [On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2305.11283/) (2023)
- [Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedback](https://mlsanity.com/paper/2307.02842/) (2023)
- [Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddings](https://mlsanity.com/paper/2206.12081/) (2022)
- [Transformers in Reinforcement Learning: A Survey](https://mlsanity.com/paper/2307.05979/) (2023)
- [Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruption](https://mlsanity.com/paper/2402.08991/) (2024)
- [Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability](https://mlsanity.com/paper/2410.05117/) (2024)
- [Reinforcement Learning with History-Dependent Dynamic Contexts](https://mlsanity.com/paper/2302.02061/) (2023)
- [Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds](https://mlsanity.com/paper/2408.08994/) (2024)
- [Provable Representation with Efficient Planning for Partial Observable Reinforcement Learning](https://mlsanity.com/paper/2311.12244/) (2023)

## 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.