Research map / Reinforcement learning / MDPs and planning
Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsight
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a multiple-observations-in-hindsight feedback model for POMDPs, defines k-MO-revealing and distinguishable POMDP classes, and gives k-OMLE and OST algorithms with polynomial sample complexity guarantees.
Problem
Sample-efficient learning in POMDPs, which is exponentially hard in the worst case under standard trajectory feedback; the paper asks what enhanced feedback and structural conditions make learning tractable.
Approach
After each episode the learner receives k-1 extra iid observations emitted from the same latent states (not the states themselves). Revealing-type conditions are applied to the augmented k-observation emissions, yielding k-MO-revealing POMDPs. Distinguishable POMDPs (only distinct emission distributions required) are shown to be k-MO-revealing for large k, and OST uses closeness testing to infer l
Key results
- k-OMLE learns (alpha,k)-MO-revealing low-rank POMDPs with O~(poly(H) k d A log N / (alpha^2 eps^2)) samples.
- Any alpha-distinguishable POMDP is (1/2,k)-MO-revealing for k = O(sqrt(O) log(SO)/alpha^2), so it is learnable by reduction to k-OMLE.
- OST achieves O~(poly(H)(SO/eps^2 + SA sqrt(O)/(eps^2 alpha^2) + SA O^{2/3}/(eps^2 alpha^{4/3}))) samples, sharper than the reduction approach.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use OST with explicit closeness tests instead of the k-OMLE reduction | Learning α-distinguishable POMDPs · α-distinguishable POMDPs | sample complexity: OST: \widetilde{\mathcal{O}}\paren{ {\rm poly}(H)\cdot \paren{ \frac{SO}{\varepsilon^2} + \frac{SA\sqrt{O}}{\varepsilon^ | Helped |
Surprising findings
- Some POMDPs (e.g., non-revealing combination lock) remain not polynomially learnable under k-MO feedback for any finite k.
Limitations
- Results are theoretical; no empirical experiments reported.
- Distinguishability defined only for tabular finite state/observation spaces.
- Computational efficiency of algorithms not addressed; relies on a planning oracle.
Experimental setup
Metrics: sample complexity suboptimality gap
Baselines: k-OMLE (reduction approach) HOP-B
Builds on: OMLE revealing POMDP hindsight observable MDP (HOMDP) closeness testing (Diakonikolas-Kane) PSR
Closest papers by meaning
- Sample-Efficient Reinforcement Learning of Undercomplete POMDPs (NeurIPS 2020 · similarity 0.92)
- Provable Representation with Efficient Planning for Partially Observable Reinforcement Learning (ICML 2024 · similarity 0.89)
- Provably Efficient Partially Observable Risk-sensitive Reinforcement Learning with Hindsight Observation (ICML 2024 · similarity 0.89)
- Model-based Reinforcement Learning for Confounded POMDPs (ICML 2024 · similarity 0.89)
- RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation (NeurIPS 2024 · similarity 0.89)
- Sequential Monte Carlo for Policy Optimization in Continuous POMDPs (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.