mlsanityData to 7 Oct 2026

Learning Near Optimal Policies with Low Inherent Bellman Error

arXiv 2003.00153 ↗First posted 29 Feb 2020cs.LG cs.AIcited by 180

Not on the map. Why?

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

Abstract (arXiv)

We study the exploration problem with approximate linear action-value functions in episodic reinforcement learning under the notion of low inherent Bellman error, a condition normally employed to show convergence of approximate value iteration. First we relate this condition to other common frameworks and show that it is strictly more general than the low rank (or linear) MDP assumption of prior work. Second we provide an algorithm with a high probability regret bound widetilde O(sumt=1H dt √K + sumt=1H √dt IBE K) where H is the horizon, K is the number of episodes, IBE is the value if the inherent Bellman error and dt is the feature dimension at timestep t. In addition, we show that the result is unimprovable beyond constants and logs by showing a matching lower bound. This has two important consequences: 1) it shows that exploration is possible using only batch assumptions with an algorithm that achieves the optimal statistical rate for the setting we consider, which is more general than prior work on low-rank MDPs 2) the lack of closedness (measured by the inherent Bellman error) is only amplified by √dt despite working in the online setting. Finally, the algorithm reduces to the celebrated textscLinUCB when H=1 but with a different choice of the exploration parameter that allows handling misspecified contextual linear bandits. While computational tractability questions remain open for the MDP setting, this enriches the class of MDPs with a linear representation for the action-value function where statistically efficient reinforcement learning is possible.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 49; 2022: 45; 2023: 43; 2024: 27; 2025: 9; 2026: 7.

180 papers.

Sort:

By area:

  1. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  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. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  6. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  7. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  8. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  9. 2022Jump-Start Reinforcement Learningcited by 102
  10. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  11. 2023Is RLHF More Difficult than Standard RL?cited by 96
  12. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
38 more
  1. 2021Adapting to Misspecification in Contextual Banditscited by 81
  2. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 80
  3. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  4. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  5. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  6. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  7. 2021Misspecified Gaussian Process Bandit Optimizationcited by 52
  8. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  9. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  10. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  11. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  12. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  13. 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
  14. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  15. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  16. 2021Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent Statescited by 42
  17. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  18. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  19. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  20. 2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
  21. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  22. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
  23. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  24. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  25. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  26. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  27. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  28. 2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximationcited by 31
  29. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  30. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  31. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  32. 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 30
  33. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  34. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  35. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  36. 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
  37. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  38. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27

50 most cited of 180 All 180 (JSON)