mlsanityData to 7 Oct 2026

Provably Efficient UCB-type Algorithms For Learning Predictive State Representations

arXiv 2307.00405 ↗First posted 1 Jul 2023cs.LG stat.MLcited by 6

Not on the map. Why?

Abstract (arXiv)

The general sequential decision-making problem, which includes Markov decision processes (MDPs) and partially observable MDPs (POMDPs) as special cases, aims at maximizing a cumulative reward by making a sequence of decisions based on a history of observations and actions over time. Recent studies have shown that the sequential decision-making problem is statistically learnable if it admits a low-rank structure modeled by predictive state representations (PSRs). Despite these advancements, existing approaches typically involve oracles or steps that are computationally intractable. On the other hand, the upper confidence bound (UCB) based approaches, which have served successfully as computationally efficient methods in bandits and MDPs, have not been investigated for more general PSRs, due to the difficulty of optimistic bonus design in these more challenging settings. This paper proposes the first known UCB-type approach for PSRs, featuring a novel bonus term that upper bounds the total variation distance between the estimated and true models. We further characterize the sample complexity bounds for our designed UCB-type algorithms for both online and offline PSRs. In contrast to existing approaches for PSRs, our UCB-type algorithms enjoy computational tractability, last-iterate guaranteed near-optimal policy, and guaranteed model accuracy.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 44 of its 77 references that are in the map. First posted on arXiv 1 Jul 2023.

Builds on

44 of 77 references.

References · 44

  1. 2019Solving Rubik's Cube with a Robot Handcited by 699
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  6. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  7. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  8. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  9. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  10. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  11. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  12. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
32 more
  1. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  2. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  3. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  4. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  5. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  6. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  7. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  8. 2020The AI Economist: Improving Equality and Productivity with AI-Driven Tax Policiescited by 75
  9. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
  10. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  11. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  12. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  13. 2016Reinforcement Learning of POMDPs using Spectral Methodscited by 51
  14. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  15. 2022PAC Reinforcement Learning for Predictive State Representationscited by 42
  16. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  17. 2016A PAC RL Algorithm for Episodic POMDPscited by 37
  18. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  19. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  20. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 31
  21. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  22. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processescited by 26
  23. 2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 26
  24. 2022Planning in Observable POMDPs in Quasipolynomial Timecited by 25
  25. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  26. 2020The Elliptical Potential Lemma Revisitedcited by 23
  27. 2021Sublinear Regret for Learning POMDPscited by 19
  28. 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 17
  29. 2022Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiencycited by 16
  30. 2022On Approximating Total Variation Distancecited by 13
  31. 2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
  32. 2023Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDPcited by 8

Built on by

Cited by year

Citing papers per year: 2023: 3; 2024: 3.

6 papers.

  1. 2023Provable Representation with Efficient Planning for Partial Observable Reinforcement Learningcited by 10
  2. 2024On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluationcited by 9
  3. 2024RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluationcited by 5
  4. 2023Prospective Side Information for Latent MDPscited by 4
  5. 2023Provable Benefits of Multi-task RL under Non-Markovian Decision Making Processescited by 0
  6. 2024Robust Offline Reinforcement Learning for Non-Markovian Decision Processescited by 0