# Learning in Observable POMDPs, without Computationally Intractable Oracles

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 93 references that are in the map.
- First posted on arXiv 7 Jun 2022.

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

- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [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)
- [Recurrent Model-Free RL Can Be a Strong Baseline for Many POMDPs](https://mlsanity.com/paper/2110.05038/) (2021)
- [Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning](https://mlsanity.com/paper/1911.05815/) (2019)
- [DESPOT: Online POMDP Planning with Regularization](https://mlsanity.com/paper/1609.03250/) (2016)
- [When Is Partially Observable Reinforcement Learning Not Scary?](https://mlsanity.com/paper/2204.08967/) (2022)
- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning](https://mlsanity.com/paper/2007.08459/) (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)
- [Memory-based Deep Reinforcement Learning for POMDPs](https://mlsanity.com/paper/2102.12344/) (2021)
- [The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits](https://mlsanity.com/paper/1610.04491/) (2016)
- [The Complexity of Markov Equilibrium in Stochastic Games](https://mlsanity.com/paper/2204.03991/) (2022)
- [Variational Recurrent Models for Solving Partially Observable Control Tasks](https://mlsanity.com/paper/1912.10703/) (2019)
- [Online Planning Algorithms for POMDPs](https://mlsanity.com/paper/1401.3436/) (2014)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [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)
- [Solving POMDPs by Searching the Space of Finite Policies](https://mlsanity.com/paper/1301.6720/) (2013)
- [Planning in Observable POMDPs in Quasipolynomial Time](https://mlsanity.com/paper/2201.04735/) (2022)
- [Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes](https://mlsanity.com/paper/1302.1525/) (2013)
- [Robust Finite-State Controllers for Uncertain POMDPs](https://mlsanity.com/paper/2009.11459/) (2020)
- [Sublinear Regret for Learning POMDPs](https://mlsanity.com/paper/2107.03635/) (2021)
- [On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function](https://mlsanity.com/paper/2102.02049/) (2021)
- [Online Learning for Unknown Partially Observable MDPs](https://mlsanity.com/paper/2102.12661/) (2021)
- [Bayesian Reinforcement Learning in Factored POMDPs](https://mlsanity.com/paper/1811.05612/) (2018)
- [Reinforcement Learning in Reward-Mixing MDPs](https://mlsanity.com/paper/2110.03743/) (2021)

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

- [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)
- [Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithms](https://mlsanity.com/paper/2209.14990/) (2022)
- [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)
- [Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning](https://mlsanity.com/paper/2310.06793/) (2023)
- [Provable Representation with Efficient Planning for Partial Observable Reinforcement Learning](https://mlsanity.com/paper/2311.12244/) (2023)
- [Monitored Markov Decision Processes](https://mlsanity.com/paper/2402.06819/) (2024)
- [Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP](https://mlsanity.com/paper/2306.12356/) (2023)
- [Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPs](https://mlsanity.com/paper/2503.01134/) (2025)
- [Optimistic MLE -- A Generic Model-based Algorithm for Partially Observable Sequential Decision Making](https://mlsanity.com/paper/2209.14997/) (2022)
- [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)
- [Reward-Mixing MDPs with a Few Latent Contexts are Learnable](https://mlsanity.com/paper/2210.02594/) (2022)
- [Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles](https://mlsanity.com/paper/2309.09457/) (2023)
- [Exponential Hardness of Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2302.12940/) (2023)
- [Prospective Side Information for Latent MDPs](https://mlsanity.com/paper/2310.07596/) (2023)
- [Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions](https://mlsanity.com/paper/2406.11640/) (2024)
- [Posterior Sampling for Competitive RL: Function Approximation and Partial Observation](https://mlsanity.com/paper/2310.19861/) (2023)
- [Near-Optimal Learning and Planning in Separated Latent MDPs](https://mlsanity.com/paper/2406.07920/) (2024)
- [To Distill or Decide? Understanding the Algorithmic Trade-off in Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2510.03207/) (2025)
- [Provably Learning from Modern Language Models via Low Logit Rank](https://mlsanity.com/paper/2512.09892/) (2025)
- [Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsampling](https://mlsanity.com/paper/2603.03759/) (2026)
- [A Theoretical Framework for Partially Observed Reward-States in RLHF](https://mlsanity.com/paper/2402.03282/) (2024)
- [Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimation](https://mlsanity.com/paper/2410.23434/) (2024)
- [Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPs](https://mlsanity.com/paper/2604.01024/) (2026)
- [Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamics](https://mlsanity.com/paper/2605.06377/) (2026)
- [Provably Efficient Partially Observable Risk-Sensitive Reinforcement Learning with Hindsight Observation](https://mlsanity.com/paper/2402.18149/) (2024)
- [End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions](https://mlsanity.com/paper/2603.23461/) (2026)
- [Missingness-MDPs: Bridging the Theory of Missing Data and POMDPs](https://mlsanity.com/paper/2605.12262/) (2026)

## Abstract (arXiv)

Much of reinforcement learning theory is built on top of oracles that are computationally hard to implement. Specifically for learning near-optimal policies in Partially Observable Markov Decision Processes (POMDPs), existing algorithms either need to make strong assumptions about the model dynamics (e.g. deterministic transitions) or assume access to an oracle for solving a hard optimistic planning or estimation problem as a subroutine. In this work we develop the first oracle-free learning algorithm for POMDPs under reasonable assumptions. Specifically, we give a quasipolynomial-time end-to-end algorithm for learning in "observable" POMDPs, where observability is the assumption that well-separated distributions over states induce well-separated distributions over observations. Our techniques circumvent the more traditional approach of using the principle of optimism under uncertainty to promote exploration, and instead give a novel application of barycentric spanners to constructing policy covers.