mlsanityData to 7 Oct 2026

Online Learning for Unknown Partially Observable MDPs

arXiv 2102.12661 ↗First posted 25 Feb 2021cs.LGcited by 17

Not on the map. Why?

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.

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

Builds on

25 of 56 references.

References · 25

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2013Learning to Optimize Via Posterior Samplingcited by 253
  5. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  6. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  7. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  8. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  9. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  10. 2020Naive Exploration is Optimal for Online LQRcited by 111
  11. 2018Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulatorcited by 86
  12. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
13 more
  1. 2020Approximate information state for approximate planning and reinforcement learning in partially observed systemscited by 67
  2. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  3. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  4. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  5. 2020Logarithmic Regret Bound in Partially Observable Linear Dynamical Systemscited by 46
  6. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 43
  7. 2020Online Learning of the Kalman Filter with Logarithmic Regretcited by 21
  8. 2019√n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rankcited by 20
  9. 2018Bayesian Reinforcement Learning in Factored POMDPscited by 15
  10. 2017Learning-based Control of Unknown Linear Systems with Thompson Samplingcited by 10
  11. 2020Adaptive Approximate Policy Iterationcited by 9
  12. 2019Exploration-Enhanced POLITEXcited by 8
  13. 2017Experimental results : Reinforcement Learning of POMDPs using Spectral Methodscited by 1

Built on by

Cited by year

Citing papers per year: 2021: 4; 2022: 5; 2023: 5; 2024: 2; 2025: 1.

17 papers.

Sort:

By area:

  1. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  2. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  3. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processescited by 26
  4. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  5. 2021Sublinear Regret for Learning POMDPscited by 19
  6. 2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
  7. 2021Common Information based Approximate State Representations in Multi-Agent Reinforcement Learningcited by 8
  8. 2023Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDPcited by 8
  9. 2023Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violationcited by 6
  10. 2021A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponentcited by 3
  11. 2024Near-Optimal Learning and Planning in Separated Latent MDPscited by 3
  12. 2023Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Spacecited by 2
5 more
  1. 2022Deriving time-averaged active inference from control principlescited by 1
  2. 2023Learning Successor Features with Distributed Hebbian Temporal Memorycited by 1
  3. 2024Efficient Learning of POMDPs with Known Observation Model in Average-Reward Settingcited by 1
  4. 2023Posterior Sampling-based Online Learning for Episodic POMDPscited by 0
  5. 2025Achieving widetildeO(√T) Regret in Average-Reward POMDPs with Known Observation Modelscited by 0