# PAC Reinforcement Learning for Predictive State Representations

arXiv: https://arxiv.org/abs/2207.05738 · HTML: https://mlsanity.com/paper/2207.05738/

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 57 references that are in the map.
- First posted on arXiv 12 Jul 2022.

## Builds on (most cited first, 24 of 24)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [When Is Partially Observable Reinforcement Learning Not Scary?](https://mlsanity.com/paper/2204.08967/) (2022)
- [Improper Learning for Non-Stochastic Control](https://mlsanity.com/paper/2001.09254/) (2020)
- [RL for Latent MDPs: Regret Guarantees and a Lower Bound](https://mlsanity.com/paper/2102.04939/) (2021)
- [Sample-Efficient Reinforcement Learning of Undercomplete POMDPs](https://mlsanity.com/paper/2006.12484/) (2020)
- [Reinforcement Learning of POMDPs using Spectral Methods](https://mlsanity.com/paper/1602.07764/) (2016)
- [Provable Reinforcement Learning with a Short-Term Memory](https://mlsanity.com/paper/2202.03983/) (2022)
- [A PAC RL Algorithm for Episodic POMDPs](https://mlsanity.com/paper/1605.08062/) (2016)
- [Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systems](https://mlsanity.com/paper/2206.12020/) (2022)
- [Learning in Observable POMDPs, without Computationally Intractable Oracles](https://mlsanity.com/paper/2206.03446/) (2022)
- [Planning in Observable POMDPs in Quasipolynomial Time](https://mlsanity.com/paper/2201.04735/) (2022)
- [Hilbert Space Embeddings of Predictive State Representations](https://mlsanity.com/paper/1309.6819/) (2013)
- [Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiency](https://mlsanity.com/paper/2205.13476/) (2022)
- [Predictive State Recurrent Neural Networks](https://mlsanity.com/paper/1705.09353/) (2017)
- [Predictive-State Decoders: Encoding the Future into Recurrent Networks](https://mlsanity.com/paper/1709.08520/) (2017)
- [Learning to Filter with Predictive State Inference Machines](https://mlsanity.com/paper/1512.08836/) (2015)
- [Regret Minimization in Partially Observable Linear Quadratic Control](https://mlsanity.com/paper/2002.00082/) (2020)
- [Efficient Learning and Planning with Compressed Predictive States](https://mlsanity.com/paper/1312.0286/) (2013)

## Built on by (most cited first, 30 of 43)

- [RLHF from Heterogeneous Feedback via Personalization and Preference Aggregation](https://mlsanity.com/paper/2405.00254/) (2024)
- [Reinforcement Learning with Human Feedback: Learning Dynamic Choices via Pessimism](https://mlsanity.com/paper/2305.18438/) (2023)
- [Provable Offline Preference-Based Reinforcement Learning](https://mlsanity.com/paper/2305.14816/) (2023)
- [Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithms](https://mlsanity.com/paper/2209.14990/) (2022)
- [Future-Dependent Value-Based Off-Policy Evaluation in POMDPs](https://mlsanity.com/paper/2207.13081/) (2022)
- [Distributional Offline Policy Evaluation with Predictive Error Guarantees](https://mlsanity.com/paper/2302.09456/) (2023)
- [Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Exploration](https://mlsanity.com/paper/2305.18258/) (2023)
- [Learning in POMDPs is Sample-Efficient with Hindsight Observability](https://mlsanity.com/paper/2301.13857/) (2023)
- [Lower Bounds for Learning in Revealing POMDPs](https://mlsanity.com/paper/2302.01333/) (2023)
- [Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs](https://mlsanity.com/paper/2303.10859/) (2023)
- [Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds](https://mlsanity.com/paper/2408.08994/) (2024)
- [Provable Representation with Efficient Planning for Partial Observable Reinforcement Learning](https://mlsanity.com/paper/2311.12244/) (2023)
- [On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluation](https://mlsanity.com/paper/2402.14703/) (2024)
- [Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP](https://mlsanity.com/paper/2306.12356/) (2023)
- [Optimistic MLE -- A Generic Model-based Algorithm for Partially Observable Sequential Decision Making](https://mlsanity.com/paper/2209.14997/) (2022)
- [A General Framework for Sequential Decision-Making under Adaptivity Constraints](https://mlsanity.com/paper/2306.14468/) (2023)
- [Provably Efficient UCB-type Algorithms For Learning Predictive State Representations](https://mlsanity.com/paper/2307.00405/) (2023)
- [RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation](https://mlsanity.com/paper/2406.01389/) (2024)
- [How to Explore with Belief: State Entropy Maximization in POMDPs](https://mlsanity.com/paper/2406.02295/) (2024)
- [The Limits of Pure Exploration in POMDPs: When the Observation Entropy is Enough](https://mlsanity.com/paper/2406.12795/) (2024)
- [Exploiting Structure in Offline Multi-Agent RL: The Benefits of Low Interaction Rank](https://mlsanity.com/paper/2410.01101/) (2024)
- [Reward-Mixing MDPs with a Few Latent Contexts are Learnable](https://mlsanity.com/paper/2210.02594/) (2022)
- [Efficient Reinforcement Learning with Impaired Observability: Learning to Act with Delayed and Missing State Observations](https://mlsanity.com/paper/2306.01243/) (2023)
- [Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsight](https://mlsanity.com/paper/2307.02884/) (2023)
- [Posterior Sampling for Competitive RL: Function Approximation and Partial Observation](https://mlsanity.com/paper/2310.19861/) (2023)
- [Near-Optimal Learning and Planning in Separated Latent MDPs](https://mlsanity.com/paper/2406.07920/) (2024)
- [Tractable Offline Learning of Regular Decision Processes](https://mlsanity.com/paper/2409.02747/) (2024)
- [To Distill or Decide? Understanding the Algorithmic Trade-off in Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2510.03207/) (2025)
- [Multi-Environment POMDPs: Discrete Model Uncertainty Under Partial Observability](https://mlsanity.com/paper/2510.23744/) (2025)
- [Representations and Exploration for Deep Reinforcement Learning using Singular Value Decomposition](https://mlsanity.com/paper/2305.00654/) (2023)

## Abstract (arXiv)

In this paper we study online Reinforcement Learning (RL) in partially observable dynamical systems. We focus on the Predictive State Representations (PSRs) model, which is an expressive model that captures other well-known models such as Partially Observable Markov Decision Processes (POMDP). PSR represents the states using a set of predictions of future observations and is defined entirely using observable quantities. We develop a novel model-based algorithm for PSRs that can learn a near optimal policy in sample complexity scaling polynomially with respect to all the relevant parameters of the systems. Our algorithm naturally works with function approximation to extend to systems with potentially large state and observation spaces. We show that given a realizable model class, the sample complexity of learning the near optimal policy only scales polynomially with respect to the statistical complexity of the model class, without any explicit polynomial dependence on the size of the state and observation spaces. Notably, our work is the first work that shows polynomial sample complexities to compete with the globally optimal policy in PSRs. Finally, we demonstrate how our general theorem can be directly used to derive sample complexity bounds for special models including m-step weakly revealing and m-step decodable tabular POMDPs, POMDPs with low-rank latent transition, and POMDPs with linear emission and latent transition.