mlsanityData to 14 Oct 2026

Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics

arXiv 2406.11810 ↗First posted 17 Jun 2024cs.LG cs.RO cs.SYcited by 5

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

We study computationally and statistically efficient Reinforcement Learning algorithms for the linear Bellman Complete setting. This setting uses linear function approximation to capture value functions and unifies existing models like linear Markov Decision Processes (MDP) and Linear Quadratic Regulators (LQR). While it is known from the prior works that this setting is statistically tractable, it remained open whether a computationally efficient algorithm exists. Our work provides a computationally efficient algorithm for the linear Bellman complete setting that works for MDPs with large action spaces, random initial states, and random rewards but relies on the underlying dynamics to be deterministic. Our approach is based on randomization: we inject random noise into least squares regression problems to perform optimistic value iteration. Our key technical contribution is to carefully design the noise to only act in the null space of the training data to ensure optimism while circumventing a subtle error amplification issue.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 26 of its 41 references that are in the map. First posted on arXiv 17 Jun 2024.

Builds on

26 of 41 references.

References · 26

  1. 2019Dota 2 with Large Scale Deep Reinforcement Learningcited by 1,103
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  3. 2018Is Q-learning Provably Efficient?cited by 487
  4. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  5. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  6. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  7. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  8. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  9. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 161
  10. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  11. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  12. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
14 more
  1. 2019Model-free Deep Reinforcement Learning for Urban Autonomous Drivingcited by 98
  2. 2022The Role of Coverage in Online Reinforcement Learningcited by 83
  3. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  4. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  5. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  6. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  7. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  8. 2023Making RL with Preference-based Feedback Efficient via Randomizationcited by 46
  9. 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
  10. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  11. 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
  12. 2013Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalizationcited by 19
  13. 2020Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexitycited by 19
  14. 2020Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iterationcited by 19

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 3.

5 papers.

  1. 2025Qsharp: Provably Optimal Distributional RL for LLM Post-Trainingcited by 15
  2. 2025Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learningcited by 12
  3. 2026Eluder dimension: localise it!cited by 3
  4. 2026Frozen Policy Iteration: Computationally Efficient RL under Linear Qπ Realizability for Deterministic Dynamicscited by 0
  5. 2026End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitionscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions
  2. 2024The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation
  3. 2026Mathematical methods of reinforcement learning
  4. 2026Lifted Bellman Linear Programming for Offline Reinforcement Learning
  5. 2022Bellman Residual Orthogonalization for Offline Reinforcement Learning
  6. 2026Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework
  7. 2025Bellman operator convergence enhancements in reinforcement learning algorithms
  8. 2024Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation