Reproduce “Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsight” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Jiacheng Guo, Minshuo Chen, Huan Wang, Caiming Xiong, Mengdi Wang, Yu Bai

Researchers from Fudan, Princeton, and Salesforce AI Research introduce a 'multiple observations in hindsight' (k-MOMDP) feedback model for Partially Observable Markov Decision Processes (POMDPs). This model enables polynomial sample complexity for newly defined k-MO-revealing and distinguishable POMDP subclasses, achieving improved sample efficiency with algorithms like Optimism with State Testing (OST).

Key insights

  • While k-MOMDP enhances feedback, it does not universally resolve the exponential hardness of POMDPs, as shown by specific 'combination lock' examples that remain hard.
  • The k-MOMDP model enables sample-efficient learning for 'distinguishable POMDPs', a class with weaker conditions (L1 separation of emission distributions) than traditional revealing POMDPs.
  • Any α-distinguishable POMDP can become (1/2, k)-MO-revealing if the number of hindsight observations ($k$) is sufficiently large, specifically $k ext{ extgreater } C ext{√}O ext{log}(SO)/ ext{α}^2$, linking these two newly defined classes.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.