# Sublinear Regret for Learning POMDPs

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 77 references that are in the map.
- First posted on arXiv 8 Jul 2021.

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

- [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)
- [Deep Recurrent Q-Learning for Partially Observable MDPs](https://mlsanity.com/paper/1507.06527/) (2015)
- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Deep Variational Reinforcement Learning for POMDPs](https://mlsanity.com/paper/1806.02426/) (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)
- [Reinforcement Learning of POMDPs using Spectral Methods](https://mlsanity.com/paper/1602.07764/) (2016)
- [Hedging the Drift: Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1903.01461/) (2019)
- [Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function](https://mlsanity.com/paper/1906.05110/) (2019)
- [A PAC RL Algorithm for Episodic POMDPs](https://mlsanity.com/paper/1605.08062/) (2016)
- [Posterior sampling for reinforcement learning: worst-case regret bounds](https://mlsanity.com/paper/1705.07041/) (2017)
- [Online Regret Bounds for Undiscounted Continuous Reinforcement Learning](https://mlsanity.com/paper/1302.2550/) (2013)
- [Online Learning for Unknown Partially Observable MDPs](https://mlsanity.com/paper/2102.12661/) (2021)
- [Asymptotic Optimality of Finite Approximations to Markov Decision Processes with Borel Spaces](https://mlsanity.com/paper/1503.02244/) (2015)
- [Statistical and Computational Guarantees for the Baum-Welch Algorithm](https://mlsanity.com/paper/1512.08269/) (2015)
- [Regime Switching Bandits](https://mlsanity.com/paper/2001.09390/) (2020)
- [Learning and Optimization with Seasonal Patterns](https://mlsanity.com/paper/2005.08088/) (2020)
- [Multi-Armed Bandits for Correlated Markovian Environments with Smoothed Reward Feedback](https://mlsanity.com/paper/1803.04008/) (2018)
- [Exploration Bonus for Regret Minimization in Undiscounted Discrete and Continuous Markov Decision Processes](https://mlsanity.com/paper/1812.04363/) (2018)
- [A Tractable Algorithm For Finite-Horizon Continuous Reinforcement Learning](https://mlsanity.com/paper/1906.11245/) (2019)

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

- [When Is Partially Observable Reinforcement Learning Not Scary?](https://mlsanity.com/paper/2204.08967/) (2022)
- [Understanding Domain Randomization for Sim-to-real Transfer](https://mlsanity.com/paper/2110.03239/) (2021)
- [Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systems](https://mlsanity.com/paper/2206.12020/) (2022)
- [Learning in Observable POMDPs, without Computationally Intractable Oracles](https://mlsanity.com/paper/2206.03446/) (2022)
- [Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2205.13589/) (2022)
- [Planning in Observable POMDPs in Quasipolynomial Time](https://mlsanity.com/paper/2201.04735/) (2022)
- [Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithms](https://mlsanity.com/paper/2209.14990/) (2022)
- [Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency](https://mlsanity.com/paper/2204.09787/) (2022)
- [Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddings](https://mlsanity.com/paper/2206.12081/) (2022)
- [Reinforcement Learning with History-Dependent Dynamic Contexts](https://mlsanity.com/paper/2302.02061/) (2023)
- [Intrusion Tolerance for Networked Systems through Two-Level Feedback Control](https://mlsanity.com/paper/2404.01741/) (2024)
- [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)
- [Near-Optimal Learning and Planning in Separated Latent MDPs](https://mlsanity.com/paper/2406.07920/) (2024)
- [Anytime-Competitive Reinforcement Learning with Policy Prior](https://mlsanity.com/paper/2311.01568/) (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)
- [Missingness-MDPs: Bridging the Theory of Missing Data and POMDPs](https://mlsanity.com/paper/2605.12262/) (2026)

## Abstract (arXiv)

We study the model-based undiscounted reinforcement learning for partially observable Markov decision processes (POMDPs). The oracle we consider is the optimal policy of the POMDP with a known environment in terms of the average reward over an infinite horizon. We propose a learning algorithm for this problem, building on spectral method-of-moments estimations for hidden Markov models, the belief error control in POMDPs and upper-confidence-bound methods for online learning. We establish a regret bound of O(T2/3√log T) for the proposed learning algorithm where T is the learning horizon. This is, to the best of our knowledge, the first algorithm achieving sublinear regret with respect to our oracle for learning general POMDPs.