Reproduce “PAC Reinforcement Learning for Predictive State Representations” 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
Wenhao Zhan, Masatoshi Uehara, Wen Sun, Jason D. Lee
CRANE, a new algorithm from researchers at Princeton and Cornell Universities, provides the first polynomial sample complexity guarantees for Probably Approximately Correct (PAC) reinforcement learning in general Predictive State Representations (PSRs). This framework enables efficient learning of near-optimal policies in partially observable systems, extending its applicability to various POMDP subclasses with improved or comparable theoretical guarantees.
Key insights
- PSRs offer a more expressive and compact modeling framework than POMDPs, defining states directly from observable quantities and facilitating efficient learning via spectral methods.
- Combining optimism in the face of uncertainty with MLE for model estimation within a dynamically updated confidence set provides an effective strategy for exploration and learning in partially observable environments.
- The PSR rank ($d_{PSR}$) and a derived regularity parameter ($ rac{1}{\alpha}$) are identified as key structural quantities that govern the learning complexity, enabling polynomial sample complexity bounds even with function approximation.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.