mlsanityData to 7 Oct 2026

Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms

arXiv 2102.00815 ↗First posted 1 Feb 2021cs.LG cs.AI stat.MLcited by 222

Not on the map. Why?

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

Abstract (arXiv)

Finding the minimal structural assumptions that empower sample-efficient learning is one of the most important research directions in Reinforcement Learning (RL). This paper advances our understanding of this fundamental question by introducing a new complexity measure -- Bellman Eluder (BE) dimension. We show that the family of RL problems of low BE dimension is remarkably rich, which subsumes a vast majority of existing tractable RL problems including but not limited to tabular MDPs, linear MDPs, reactive POMDPs, low Bellman rank problems as well as low Eluder dimension problems. This paper further designs a new optimization-based algorithm -- GOLF, and reanalyzes a hypothesis elimination-based algorithm -- OLIVE (proposed in Jiang et al., 2017). We prove that both algorithms learn the near-optimal policies of low BE dimension problems in a number of samples that is polynomial in all relevant parameters, but independent of the size of state-action space. Our regret and sample complexity results match or improve the best existing results for several well-known subclasses of low BE dimension problems.

Key facts. Cited by 222 papers in the map (data through 7 Oct 2026). Builds on 28 of its 69 references that are in the map. First posted on arXiv 1 Feb 2021.

Builds on

28 of 69 references.

References · 28

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  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. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  6. 2016Deep Reinforcement Learning for Dialogue Generationcited by 286
  7. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  8. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  9. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 211
  10. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  11. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
  12. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
16 more
  1. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  2. 2017On the Sample Complexity of the Linear Quadratic Regulatorcited by 151
  3. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  4. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  5. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  6. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  7. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  8. 2020Batch Value-function Approximation with Only Realizabilitycited by 103
  9. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  10. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  11. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  12. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  13. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 50
  14. 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 36
  15. 2019√n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rankcited by 20
  16. 2020On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spacescited by 19

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 26; 2022: 51; 2023: 51; 2024: 53; 2025: 26; 2026: 15.

222 papers.

Sort:

By area:

  1. 2023Cal-QL: Calibrated Offline RL Pre-Training for Efficient Online Fine-Tuningcited by 230
  2. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  3. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 158
  4. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  5. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  6. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  7. 2024Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHFcited by 106
  8. 2024Self-Improvement in Language Models: The Sharpening Mechanismcited by 102
  9. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  10. 2023Is RLHF More Difficult than Standard RL?cited by 96
  11. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  12. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 80
38 more
  1. 2021Understanding Domain Randomization for Sim-to-real Transfercited by 69
  2. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  3. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  4. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  5. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  6. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  7. 2023Making RL with Preference-based Feedback Efficient via Randomizationcited by 46
  8. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  9. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  10. 2022PAC Reinforcement Learning for Predictive State Representationscited by 42
  11. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  12. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  13. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  14. 2023Efficient Reinforcement Learning for Autonomous Driving with Parameterized Skills and Priorscited by 36
  15. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  16. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gapscited by 34
  17. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  18. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  19. 2022On the Complexity of Adversarial Decision Makingcited by 32
  20. 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHFcited by 32
  21. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 31
  22. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  23. 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 30
  24. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 30
  25. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  26. 2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficientcited by 29
  27. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  28. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
  29. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  30. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  31. 2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 26
  32. 2022Sample-Efficient Reinforcement Learning in the Presence of Exogenous Informationcited by 26
  33. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  34. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  35. 2022Regret Bounds for Information-Directed Reinforcement Learningcited by 24
  36. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  37. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
  38. 2024More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learningcited by 23

50 most cited of 222 All 222 (JSON)