mlsanityData to 7 Oct 2026

Contextual Decision Processes with Low Bellman Rank are PAC-Learnable

arXiv 1610.09512 ↗First posted 29 Oct 2016cs.LG stat.MLcited by 290

Not on the map. Why?

Cited by 39 in Offline RL and imitation learning from data, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

This paper studies systematic exploration for reinforcement learning with rich observations and function approximation. We introduce a new model called contextual decision processes, that unifies and generalizes most prior settings. Our first contribution is a complexity measure, the Bellman rank, that we show enables tractable learning of near-optimal behavior in these processes and is naturally small for many well-studied reinforcement learning settings. Our second contribution is a new reinforcement learning algorithm that engages in systematic exploration to learn contextual decision processes with low Bellman rank. Our algorithm provably learns near-optimal behavior with a number of samples that is polynomial in all relevant parameters but independent of the number of unique observations. The approach uses Bellman error minimization with optimistic exploration and provides new insights into efficient exploration for reinforcement learning with function approximation.

Key facts. Cited by 290 papers in the map (data through 7 Oct 2026). First posted on arXiv 29 Oct 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2019: 1; 2020: 1; 2021: 65; 2022: 72; 2023: 62; 2024: 49; 2025: 23; 2026: 17.

290 papers.

Sort:

By area:

  1. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  2. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  3. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  4. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  5. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 158
  6. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  7. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  8. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  9. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  10. 2024Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHFcited by 106
  11. 2021Generalized Decision Transformer for Offline Hindsight Information Matchingcited by 105
  12. 2022Jump-Start Reinforcement Learningcited by 102
38 more
  1. 2024Self-Improvement in Language Models: The Sharpening Mechanismcited by 102
  2. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  3. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  4. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  5. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 80
  6. 2025Outcome-based Exploration for LLM Reasoningcited by 79
  7. 2019Provably Efficient Imitation Learning from Observation Alonecited by 78
  8. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  9. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
  10. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 65
  11. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  12. 2021Reinforcement Learning, Bit by Bitcited by 59
  13. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  14. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  15. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  16. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  17. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  18. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  19. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  20. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  21. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  22. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  23. 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
  24. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  25. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  26. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 44
  27. 2021Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent Statescited by 42
  28. 2021Risk Bounds and Rademacher Complexity in Batch Reinforcement Learningcited by 42
  29. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  30. 2022PAC Reinforcement Learning for Predictive State Representationscited by 42
  31. 2024Dataset Reset Policy Optimization for RLHFcited by 41
  32. 2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
  33. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  34. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  35. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
  36. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  37. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  38. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35

50 most cited of 290 All 290 (JSON)