# Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithms

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 88 references that are in the map.
- First posted on arXiv 29 Sep 2022.

## Builds on (most cited first, 30 of 35)

- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [Solving Rubik's Cube with a Robot Hand](https://mlsanity.com/paper/1910.07113/) (2019)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [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)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [When Is Partially Observable Reinforcement Learning Not Scary?](https://mlsanity.com/paper/2204.08967/) (2022)
- [The AI Economist: Improving Equality and Productivity with AI-Driven Tax Policies](https://mlsanity.com/paper/2004.13332/) (2020)
- [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)
- [PAC Reinforcement Learning for Predictive State Representations](https://mlsanity.com/paper/2207.05738/) (2022)
- [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)
- [Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systems](https://mlsanity.com/paper/2206.12020/) (2022)
- [Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexity](https://mlsanity.com/paper/2206.07659/) (2022)
- [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)
- [Near-Optimal Learning of Extensive-Form Games with Imperfect Information](https://mlsanity.com/paper/2202.01752/) (2022)
- [Planning in Observable POMDPs in Quasipolynomial Time](https://mlsanity.com/paper/2201.04735/) (2022)
- [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)
- [Hilbert Space Embeddings of Predictive State Representations](https://mlsanity.com/paper/1309.6819/) (2013)
- [Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency](https://mlsanity.com/paper/2204.09787/) (2022)
- [Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiency](https://mlsanity.com/paper/2205.13476/) (2022)

## Built on by (most cited first, 24 of 24)

- [Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL](https://mlsanity.com/paper/2304.05889/) (2023)
- [Learning in POMDPs is Sample-Efficient with Hindsight Observability](https://mlsanity.com/paper/2301.13857/) (2023)
- [Efficient Model-Free Exploration in Low-Rank MDPs](https://mlsanity.com/paper/2307.03997/) (2023)
- [Lower Bounds for Learning in Revealing POMDPs](https://mlsanity.com/paper/2302.01333/) (2023)
- [Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs](https://mlsanity.com/paper/2303.10859/) (2023)
- [On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluation](https://mlsanity.com/paper/2402.14703/) (2024)
- [Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPs](https://mlsanity.com/paper/2503.01134/) (2025)
- [Provably Efficient UCB-type Algorithms For Learning Predictive State Representations](https://mlsanity.com/paper/2307.00405/) (2023)
- [RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation](https://mlsanity.com/paper/2406.01389/) (2024)
- [How to Explore with Belief: State Entropy Maximization in POMDPs](https://mlsanity.com/paper/2406.02295/) (2024)
- [The Limits of Pure Exploration in POMDPs: When the Observation Entropy is Enough](https://mlsanity.com/paper/2406.12795/) (2024)
- [Efficient Reinforcement Learning with Impaired Observability: Learning to Act with Delayed and Missing State Observations](https://mlsanity.com/paper/2306.01243/) (2023)
- [Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsight](https://mlsanity.com/paper/2307.02884/) (2023)
- [Prospective Side Information for Latent MDPs](https://mlsanity.com/paper/2310.07596/) (2023)
- [Near-Optimal Learning and Planning in Separated Latent MDPs](https://mlsanity.com/paper/2406.07920/) (2024)
- [Multi-Environment POMDPs: Discrete Model Uncertainty Under Partial Observability](https://mlsanity.com/paper/2510.23744/) (2025)
- [Sample-Efficient Multi-Agent RL: An Optimization Perspective](https://mlsanity.com/paper/2310.06243/) (2023)
- [A Theoretical Framework for Partially Observed Reward-States in RLHF](https://mlsanity.com/paper/2402.03282/) (2024)
- [Toward Learning POMDPs Beyond Full-Rank Actions and State Observability](https://mlsanity.com/paper/2601.18930/) (2026)
- [Near-Optimal Partially Observable Reinforcement Learning with Partial Online State Information](https://mlsanity.com/paper/2306.08762/) (2023)
- [Posterior Sampling-based Online Learning for Episodic POMDPs](https://mlsanity.com/paper/2310.10107/) (2023)
- [Provable Benefits of Multi-task RL under Non-Markovian Decision Making Processes](https://mlsanity.com/paper/2310.13550/) (2023)
- [Robust Offline Reinforcement Learning for Non-Markovian Decision Processes](https://mlsanity.com/paper/2411.07514/) (2024)
- [The Value Function Semi-Algebraic Set in Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2606.03048/) (2026)

## Abstract (arXiv)

Partial Observability -- where agents can only observe partial information about the true underlying state of the system -- is ubiquitous in real-world applications of Reinforcement Learning (RL). Theoretically, learning a near-optimal policy under partial observability is known to be hard in the worst case due to an exponential sample complexity lower bound. Recent work has identified several tractable subclasses that are learnable with polynomial samples, such as Partially Observable Markov Decision Processes (POMDPs) with certain revealing or decodability conditions. However, this line of research is still in its infancy, where (1) unified structural conditions enabling sample-efficient learning are lacking; (2) existing sample complexities for known tractable subclasses are far from sharp; and (3) fewer sample-efficient algorithms are available than in fully observable RL. This paper advances all three aspects above for Partially Observable RL in the general setting of Predictive State Representations (PSRs). First, we propose a natural and unified structural condition for PSRs called B-stability. B-stable PSRs encompasses the vast majority of known tractable subclasses such as weakly revealing POMDPs, low-rank future-sufficient POMDPs, decodable POMDPs, and regular PSRs. Next, we show that any B-stable PSR can be learned with polynomial samples in relevant problem parameters. When instantiated in the aforementioned subclasses, our sample complexities improve substantially over the current best ones. Finally, our results are achieved by three algorithms simultaneously: Optimistic Maximum Likelihood Estimation, Estimation-to-Decisions, and Model-Based Optimistic Posterior Sampling. The latter two algorithms are new for sample-efficient learning of POMDPs/PSRs.