Research map / Bandits and online learning / RL theory and MDPs
Provably Efficient UCB-type Algorithms For Learning Predictive State Representations
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 PSR-UCB, the first UCB-type algorithm for online learning of predictive state representations with a novel TV-distance bonus and last-iterate guarantees, and PSR-LCB, the first offline PSR algorithm.
Problem
Learning near-optimal policies in general sequential decision-making with low-rank PSR structure, where existing methods (OMLE, posterior sampling) are computationally or memory intractable and give mixture policies; extending UCB-type methods to PSRs online and offline.
Approach
Designs an explicit UCB bonus, built from the prediction features of estimated PSR models over stable (min-probability-constrained) MLE, that upper bounds the total variation distance between estimated and true models; a termination condition gives a last-iterate near-accurate model and policy. The offline variant uses the analogous pessimistic LCB with a coverage coefficient.
Key results
- PSR-UCB with probability 1-delta outputs a policy with suboptimality at most epsilon and a model with TV error at most epsilon, with sample complexity tilde-O((r + Q_A^2 H/gamma^2) r d H^3 |A|^2 Q_A^4 beta / (gamma^4 epsilon^2)).
- In the regime r < Q_A^2 H/gamma^2, the PSR-UCB sample complexity matches the best known bound in rank r and epsilon.
- PSR-LCB offline output policy suboptimality is tilde-O(C_inf / sqrt(K)) against any covered target policy, the first known offline PSR sample complexity result.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use PSR-UCB with its prediction-feature bonus and stable model estimation | Online PSR learning · Online PSRs | policy suboptimality: \epsilon | Helped |
| use PSR-UCB with its prediction-feature bonus and stable model estimation | Online PSR learning · Online PSRs | total variation distance: \epsilon | Helped |
| use PSR-UCB for online learning | Online PSR learning · Online PSRs | sample complexity: \tilde{O}\left( \left( r + \frac{Q_A^2 H}{\gamma^2}\right) \frac{r d H^3 |\mathcal{A}|^2 Q_A^4 \beta}{\gamma^4\epsilon^2 | Helped |
| use PSR-LCB with its prediction-feature lower confidence bound | Offline PSR learning · Offline PSRs | performance difference: \tilde{O}\left( \left(\sqrt{r} + \frac{ Q_A\sqrt{H}}{\gamma}\right)\frac{ C_{\pi^b,\infty}^{\pi} Q_A H^2\sqrt{d} }{ \iot | Helped |
Limitations
- Requires well-conditioned (gamma) PSR assumption and known initial state features psi_0.
- Sample complexity bounds carry large polynomial dependence on Q_A, |A|, gamma, and log covering number; p_min scales with |O|^H|A|^H in the bound.
- Planning oracle for POMDPs assumed; total variation distance computation is an open question for the reward-free case.
Experimental setup
Metrics: sample complexity suboptimality gap total variation distance between estimated and true models
Baselines: OMLE model-based posterior sampling PSR reward-free algorithms confidence region based offline POMDP algorithms
Builds on: OMLE PSR elliptical potential lemma Liu et al. 2022 PSR sample complexity analysis
Closest papers by meaning
- Regret Bounds for Learning State Representations in Reinforcement Learning (NeurIPS 2019 · similarity 0.89)
- PAC Reinforcement Learning for Predictive State Representations (ICLR 2023 · similarity 0.88)
- Learning in Generalized Linear Contextual Bandits with Stochastic Delays (NeurIPS 2019 · similarity 0.87)
- Conservative Contextual Bandits: Beyond Linear Representations (ICLR 2025 · similarity 0.86)
- Achieving Constant Regret in Linear Markov Decision Processes (NeurIPS 2024 · similarity 0.86)
- Managing Self-Learning Experts under Per-Round Budget Constraints (NeurIPS 2026 · similarity 0.86)
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.