mlsanityData to 7 Oct 2026

A PAC RL Algorithm for Episodic POMDPs

arXiv 1605.08062 ↗First posted 25 May 2016cs.LG cs.AI stat.MLcited by 37

Not on the map. Why?

Abstract (arXiv)

Many interesting real world domains involve reinforcement learning (RL) in partially observable environments. Efficient learning in such domains is important, but existing sample complexity bounds for partially observable RL are at least exponential in the episode length. We give, to our knowledge, the first partially observable RL algorithm with a polynomial bound on the number of episodes on which the algorithm may not achieve near-optimal performance. Our algorithm is suitable for an important class of episodic POMDPs. Our approach builds on recent advances in method of moments for latent variable model estimation.

Key facts. Cited by 37 papers in the map (data through 7 Oct 2026). First posted on arXiv 25 May 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 15; 2023: 9; 2024: 4; 2025: 3; 2026: 3.

37 papers.

Sort:

By area:

  1. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  2. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
  3. 2022PAC Reinforcement Learning for Predictive State Representationscited by 42
  4. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  5. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  6. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  7. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processescited by 26
  8. 2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 26
  9. 2022Planning in Observable POMDPs in Quasipolynomial Timecited by 25
  10. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  11. 2022Future-Dependent Value-Based Off-Policy Evaluation in POMDPscited by 20
  12. 2022An Instrumental Variable Approach to Confounded Off-Policy Evaluationcited by 20
25 more
  1. 2021Sublinear Regret for Learning POMDPscited by 19
  2. 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 17
  3. 2022Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiencycited by 16
  4. 2021Reinforcement Learning in Reward-Mixing MDPscited by 15
  5. 2022Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiencycited by 15
  6. 2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
  7. 2023Act-Then-Measure: Reinforcement Learning for Partially Observable Environments with Active Measuringcited by 10
  8. 2023Provable Representation with Efficient Planning for Partial Observable Reinforcement Learningcited by 10
  9. 2024On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluationcited by 9
  10. 2023Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDPcited by 8
  11. 2025Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPscited by 7
  12. 2023Provably Efficient UCB-type Algorithms For Learning Predictive State Representationscited by 6
  13. 2022Reward-Mixing MDPs with a Few Latent Contexts are Learnablecited by 5
  14. 2024RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluationcited by 5
  15. 2023Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsightcited by 3
  16. 2023Representations and Exploration for Deep Reinforcement Learning using Singular Value Decompositioncited by 2
  17. 2024Tractable Offline Learning of Regular Decision Processescited by 2
  18. 2024Efficient Learning of POMDPs with Known Observation Model in Average-Reward Settingcited by 1
  19. 2025Reinforcement Learning with Action-Triggered Observationscited by 1
  20. 2026Toward Learning POMDPs Beyond Full-Rank Actions and State Observabilitycited by 1
  21. 2023Learning Optimal Admission Control in Partially Observable Queueing Networkscited by 0
  22. 2023Posterior Sampling-based Online Learning for Episodic POMDPscited by 0
  23. 2025Achieving widetildeO(√T) Regret in Average-Reward POMDPs with Known Observation Modelscited by 0
  24. 2026Missingness-MDPs: Bridging the Theory of Missing Data and POMDPscited by 0
  25. 2026Minimax-Optimal Policy Regret in Partially Observable Markov Gamescited by 0