# Online Learning for Unknown Partially Observable MDPs

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 56 references that are in the map.
- First posted on arXiv 25 Feb 2021.

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

- [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 to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (2014)
- [Naive Exploration is Optimal for Online LQR](https://mlsanity.com/paper/2001.09576/) (2020)
- [Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator](https://mlsanity.com/paper/1805.09388/) (2018)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [Approximate information state for approximate planning and reinforcement learning in partially observed systems](https://mlsanity.com/paper/2010.08843/) (2020)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [Learning Unknown Markov Decision Processes: A Thompson Sampling Approach](https://mlsanity.com/paper/1709.04570/) (2017)
- [Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2007.11849/) (2020)
- [Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems](https://mlsanity.com/paper/2003.11227/) (2020)
- [Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function](https://mlsanity.com/paper/1906.05110/) (2019)
- [Online Learning of the Kalman Filter with Logarithmic Regret](https://mlsanity.com/paper/2002.05141/) (2020)
- [√n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank](https://mlsanity.com/paper/1909.02506/) (2019)
- [Bayesian Reinforcement Learning in Factored POMDPs](https://mlsanity.com/paper/1811.05612/) (2018)
- [Learning-based Control of Unknown Linear Systems with Thompson Sampling](https://mlsanity.com/paper/1709.04047/) (2017)
- [Adaptive Approximate Policy Iteration](https://mlsanity.com/paper/2002.03069/) (2020)
- [Exploration-Enhanced POLITEX](https://mlsanity.com/paper/1908.10479/) (2019)
- [Experimental results : Reinforcement Learning of POMDPs using Spectral Methods](https://mlsanity.com/paper/1705.02553/) (2017)

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

- [When Is Partially Observable Reinforcement Learning Not Scary?](https://mlsanity.com/paper/2204.08967/) (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)
- [Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithms](https://mlsanity.com/paper/2209.14990/) (2022)
- [Sublinear Regret for Learning POMDPs](https://mlsanity.com/paper/2107.03635/) (2021)
- [Online Learning for Stochastic Shortest Path Model via Posterior Sampling](https://mlsanity.com/paper/2106.05335/) (2021)
- [Common Information based Approximate State Representations in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2110.12603/) (2021)
- [Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP](https://mlsanity.com/paper/2306.12356/) (2023)
- [Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violation](https://mlsanity.com/paper/2301.11547/) (2023)
- [A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponent](https://mlsanity.com/paper/2109.03396/) (2021)
- [Near-Optimal Learning and Planning in Separated Latent MDPs](https://mlsanity.com/paper/2406.07920/) (2024)
- [Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space](https://mlsanity.com/paper/2306.02574/) (2023)
- [Deriving time-averaged active inference from control principles](https://mlsanity.com/paper/2208.10601/) (2022)
- [Learning Successor Features with Distributed Hebbian Temporal Memory](https://mlsanity.com/paper/2310.13391/) (2023)
- [Efficient Learning of POMDPs with Known Observation Model in Average-Reward Setting](https://mlsanity.com/paper/2410.01331/) (2024)
- [Posterior Sampling-based Online Learning for Episodic POMDPs](https://mlsanity.com/paper/2310.10107/) (2023)
- [Achieving widetildeO(√T) Regret in Average-Reward POMDPs with Known Observation Models](https://mlsanity.com/paper/2501.18790/) (2025)

## Abstract (arXiv)

Solving Partially Observable Markov Decision Processes (POMDPs) is hard. Learning optimal controllers for POMDPs when the model is unknown is harder. Online learning of optimal controllers for unknown POMDPs, which requires efficient learning using regret-minimizing algorithms that effectively tradeoff exploration and exploitation, is even harder, and no solution exists currently. In this paper, we consider infinite-horizon average-cost POMDPs with unknown transition model, though a known observation model. We propose a natural posterior sampling-based reinforcement learning algorithm (PSRL-POMDP) and show that it achieves a regret bound of O(log T), where T is the time horizon, when the parameter set is finite. In the general case (continuous parameter set), we show that the algorithm achieves O (T2/3) regret under two technical assumptions. To the best of our knowledge, this is the first online RL algorithm for POMDPs and has sub-linear regret.