mlsanityData to 14 Oct 2026

Posterior Sampling-based Online Learning for Episodic POMDPs

arXiv 2310.10107 ↗First posted 16 Oct 2023cs.LG cs.AI cs.SYcited by 0

Not on the map. Why?

Abstract (arXiv)

Learning in POMDPs is known to be significantly harder than in MDPs. In this paper, we consider the online learning problem for episodic POMDPs with unknown transition and observation models. We propose a Posterior Sampling-based reinforcement learning algorithm for POMDPs (PS4POMDPs), which is much simpler and more implementable compared to state-of-the-art optimism-based online learning algorithms for POMDPs. We show that the Bayesian regret of the proposed algorithm scales as the square root of the number of episodes and is polynomial in the other parameters. In a general setting, the regret scales exponentially in the horizon length H, and we show that this is inevitable by providing a lower bound. However, when the POMDP is undercomplete and weakly revealing (a common assumption in the recent literature), we establish a polynomial Bayesian regret bound. We finally propose a posterior sampling algorithm for multi-agent POMDPs, and show it too has sublinear regret.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 24 of its 56 references that are in the map. First posted on arXiv 16 Oct 2023.

Builds on

24 of 56 references.

References · 24

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2016Deep Exploration via Bootstrapped DQNcited by 527
  3. 2017A Tutorial on Thompson Samplingcited by 433
  4. 2018Pyro: Deep Universal Probabilistic Programmingcited by 380
  5. 2013Learning to Optimize Via Posterior Samplingcited by 256
  6. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  7. 2014An Information-Theoretic Analysis of Thompson Samplingcited by 178
  8. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 117
  9. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  10. 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
  11. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  12. 2016Reinforcement Learning of POMDPs using Spectral Methodscited by 52
12 more
  1. 2022GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyondcited by 46
  2. 2022PAC Reinforcement Learning for Predictive State Representationscited by 43
  3. 2016A PAC RL Algorithm for Episodic POMDPscited by 37
  4. 2013Prior-free and prior-dependent regret bounds for Thompson Samplingcited by 25
  5. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  6. 2020The Elliptical Potential Lemma Revisitedcited by 23
  7. 2021Sublinear Regret for Learning POMDPscited by 19
  8. 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 18
  9. 2021Online Learning for Unknown Partially Observable MDPscited by 17
  10. 2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
  11. 2023Lower Bounds for Learning in Revealing POMDPscited by 15
  12. 2023Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violationcited by 6

Built on by

Not cited yet.