# Learning in POMDPs is Sample-Efficient with Hindsight Observability

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 65 references that are in the map.
- First posted on arXiv 31 Jan 2023.

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

- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [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)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Learning by Cheating](https://mlsanity.com/paper/1912.12294/) (2019)
- [Learning to reinforcement learn](https://mlsanity.com/paper/1611.05763/) (2016)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Bellman-consistent Pessimism for Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06926/) (2021)
- [Asymmetric Actor Critic for Image-Based Robot Learning](https://mlsanity.com/paper/1710.06542/) (2017)
- [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)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning](https://mlsanity.com/paper/2108.08812/) (2021)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [When Is Partially Observable Reinforcement Learning Not Scary?](https://mlsanity.com/paper/2204.08967/) (2022)
- [Policy Certificates: Towards Accountable Reinforcement Learning](https://mlsanity.com/paper/1811.03056/) (2018)
- [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)
- [Decoupling Exploration and Exploitation for Meta-Reinforcement Learning without Sacrifices](https://mlsanity.com/paper/2008.02790/) (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)
- [On Lower Bounds for Regret in Reinforcement Learning](https://mlsanity.com/paper/1608.02732/) (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)
- [Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexity](https://mlsanity.com/paper/2206.07659/) (2022)

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

- [SpecDec++: Boosting Speculative Decoding via Adaptive Candidate Lengths](https://mlsanity.com/paper/2405.19715/) (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)
- [Approximate Model-Based Shielding for Safe Reinforcement Learning](https://mlsanity.com/paper/2308.00707/) (2023)
- [Leveraging Approximate Model-based Shielding for Probabilistic Safety Guarantees in Continuous Environments](https://mlsanity.com/paper/2402.00816/) (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)
- [Guided Policy Optimization under Partial Observability](https://mlsanity.com/paper/2505.15418/) (2025)
- [To Distill or Decide? Understanding the Algorithmic Trade-off in Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2510.03207/) (2025)
- [Learning Interpretable Policies in Hindsight-Observable POMDPs through Partially Supervised Reinforcement Learning](https://mlsanity.com/paper/2402.09290/) (2024)
- [Preparing for Black Swans: The Antifragility Imperative for Machine Learning](https://mlsanity.com/paper/2405.11397/) (2024)
- [Stochastic Principal-Agent Problems: Efficient Computation and Learning](https://mlsanity.com/paper/2306.03832/) (2023)
- [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)
- [Optimizing Heat Alert Issuance with Reinforcement Learning](https://mlsanity.com/paper/2312.14196/) (2023)
- [Revealing After Overwriting: An Exponential POMDP OPE Lower Bound under History-Dependent Logging](https://mlsanity.com/paper/2610.05063/) (2026)

## Abstract (arXiv)

POMDPs capture a broad class of decision making problems, but hardness results suggest that learning is intractable even in simple settings due to the inherent partial observability. However, in many realistic problems, more information is either revealed or can be computed during some point of the learning process. Motivated by diverse applications ranging from robotics to data center scheduling, we formulate a Hindsight Observable Markov Decision Process (HOMDP) as a POMDP where the latent states are revealed to the learner in hindsight and only during training. We introduce new algorithms for the tabular and function approximation settings that are provably sample-efficient with hindsight observability, even in POMDPs that would otherwise be statistically intractable. We give a lower bound showing that the tabular algorithm is optimal in its dependence on latent state and observation cardinalities.