mlsanityData to 7 Oct 2026

Sublinear Regret for Learning POMDPs

arXiv 2107.03635 ↗First posted 8 Jul 2021cs.LG math.OCcited by 19

Not on the map. Why?

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.

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

Builds on

21 of 77 references.

References · 21

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2015Deep Recurrent Q-Learning for Partially Observable MDPscited by 457
  4. 2014Statistical guarantees for the EM algorithm: From population to sample-based analysiscited by 131
  5. 2018Deep Variational Reinforcement Learning for POMDPscited by 122
  6. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
  7. 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
  8. 2016Reinforcement Learning of POMDPs using Spectral Methodscited by 51
  9. 2019Hedging the Drift: Learning to Optimize under Non-Stationaritycited by 46
  10. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 43
  11. 2016A PAC RL Algorithm for Episodic POMDPscited by 37
  12. 2017Posterior sampling for reinforcement learning: worst-case regret boundscited by 28
9 more
  1. 2013Online Regret Bounds for Undiscounted Continuous Reinforcement Learningcited by 17
  2. 2021Online Learning for Unknown Partially Observable MDPscited by 17
  3. 2015Asymptotic Optimality of Finite Approximations to Markov Decision Processes with Borel Spacescited by 11
  4. 2015Statistical and Computational Guarantees for the Baum-Welch Algorithmcited by 11
  5. 2020Regime Switching Banditscited by 9
  6. 2020Learning and Optimization with Seasonal Patternscited by 6
  7. 2018Multi-Armed Bandits for Correlated Markovian Environments with Smoothed Reward Feedbackcited by 4
  8. 2018Exploration Bonus for Regret Minimization in Undiscounted Discrete and Continuous Markov Decision Processescited by 2
  9. 2019A Tractable Algorithm For Finite-Horizon Continuous Reinforcement Learningcited by 1

Built on by

Cited by year (2026 to 7 Oct)

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

19 papers.

Sort:

By area:

  1. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  2. 2021Understanding Domain Randomization for Sim-to-real Transfercited by 69
  3. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  4. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  5. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processescited by 26
  6. 2022Planning in Observable POMDPs in Quasipolynomial Timecited by 25
  7. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  8. 2022Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiencycited by 15
  9. 2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
  10. 2023Reinforcement Learning with History-Dependent Dynamic Contextscited by 11
  11. 2024Intrusion Tolerance for Networked Systems through Two-Level Feedback Controlcited by 8
  12. 2025Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPscited by 7
7 more
  1. 2022Optimistic MLE -- A Generic Model-based Algorithm for Partially Observable Sequential Decision Makingcited by 6
  2. 2023Provably Efficient UCB-type Algorithms For Learning Predictive State Representationscited by 6
  3. 2024Near-Optimal Learning and Planning in Separated Latent MDPscited by 3
  4. 2023Anytime-Competitive Reinforcement Learning with Policy Priorcited by 1
  5. 2023Near-Optimal Partially Observable Reinforcement Learning with Partial Online State Informationcited by 0
  6. 2023Posterior Sampling-based Online Learning for Episodic POMDPscited by 0
  7. 2026Missingness-MDPs: Bridging the Theory of Missing Data and POMDPscited by 0