mlsanityData to 7 Oct 2026

Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsight

arXiv 2307.02884 ↗First posted 6 Jul 2023cs.LG stat.MLcited by 3

Not on the map. Why?

Abstract (arXiv)

This paper studies the sample-efficiency of learning in Partially Observable Markov Decision Processes (POMDPs), a challenging problem in reinforcement learning that is known to be exponentially hard in the worst-case. Motivated by real-world settings such as loading in game playing, we propose an enhanced feedback model called ``multiple observations in hindsight'', where after each episode of interaction with the POMDP, the learner may collect multiple additional observations emitted from the encountered latent states, but may not observe the latent states themselves. We show that sample-efficient learning under this feedback model is possible for two new subclasses of POMDPs: multi-observation revealing POMDPs and distinguishable POMDPs. Both subclasses generalize and substantially relax revealing POMDPs -- a widely studied subclass for which sample-efficient learning is possible under standard trajectory feedback. Notably, distinguishable POMDPs only require the emission distributions from different latent states to be different instead of linearly independent as required in revealing POMDPs.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 28 of its 50 references that are in the map. First posted on arXiv 6 Jul 2023.

Builds on

28 of 50 references.

References · 28

  1. 2019Solving Rubik's Cube with a Robot Handcited by 699
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  4. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  5. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  6. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  7. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  8. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  9. 2020The AI Economist: Improving Equality and Productivity with AI-Driven Tax Policiescited by 75
  10. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
  11. 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
  12. 2022PAC Reinforcement Learning for Predictive State Representationscited by 42
16 more
  1. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  2. 2013Optimal Algorithms for Testing Closeness of Discrete Distributionscited by 37
  3. 2016A PAC RL Algorithm for Episodic POMDPscited by 37
  4. 2015Optimal Testing for Properties of Distributionscited by 36
  5. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  6. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 31
  7. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
  8. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  9. 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 17
  10. 2022Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiencycited by 16
  11. 2018Bayesian Reinforcement Learning in Factored POMDPscited by 15
  12. 2022Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiencycited by 15
  13. 2023Lower Bounds for Learning in Revealing POMDPscited by 14
  14. 2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
  15. 2023Learning Hidden Markov Models Using Conditional Samplescited by 12
  16. 2022A Few Expert Queries Suffices for Sample-Efficient RL with Resets and Linear Value Approximationcited by 7

Built on by

Cited by year

Citing papers per year: 2024: 2; 2025: 1.

3 papers.

  1. 2025Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPscited by 7
  2. 2024Learning Interpretable Policies in Hindsight-Observable POMDPs through Partially Supervised Reinforcement Learningcited by 2
  3. 2024Provably Efficient Partially Observable Risk-Sensitive Reinforcement Learning with Hindsight Observationcited by 0