mlsanityData to 14 Oct 2026

Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions

arXiv 2406.11640 ↗First posted 17 Jun 2024cs.LG cs.AI stat.MLcited by 4

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

Abstract (arXiv)

One of the most natural approaches to reinforcement learning (RL) with function approximation is value iteration, which inductively generates approximations to the optimal value function by solving a sequence of regression problems. To ensure the success of value iteration, it is typically assumed that Bellman completeness holds, which ensures that these regression problems are well-specified. We study the problem of learning an optimal policy under Bellman completeness in the online model of RL with linear function approximation. In the linear setting, while statistically efficient algorithms are known under Bellman completeness (e.g., Jiang et al. (2017); Zanette et al. (2020)), these algorithms all rely on the principle of global optimism which requires solving a nonconvex optimization problem. In particular, it has remained open as to whether computationally efficient algorithms exist. In this paper we give the first polynomial-time algorithm for RL under linear Bellman completeness when the number of actions is any constant.

Key facts. Cited by 4 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 42 references that are in the map. First posted on arXiv 17 Jun 2024.

Builds on

26 of 42 references.

References · 26

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2015Deep Reinforcement Learning with Double Q-learningcited by 1,745
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  4. 2019Reinforcement Learning in Healthcare: A Surveycited by 310
  5. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  6. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  7. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  8. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  9. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  10. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  11. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  12. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
14 more
  1. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  2. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  3. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  4. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  5. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  6. 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
  7. 2020Tight Hardness Results for Training Depth-2 ReLU Networkscited by 35
  8. 2018Learning Two Layer Rectified Neural Networks in Polynomial Timecited by 31
  9. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  10. 2023Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RLcited by 22
  11. 2013Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalizationcited by 19
  12. 2023Efficient Model-Free Exploration in Low-Rank MDPscited by 16
  13. 2023Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oraclescited by 5
  14. 2023Exponential Hardness of Reinforcement Learning with Linear Function Approximationcited by 4

Built on by

Cited by year (2026 to 14 Oct)

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

4 papers.

  1. 2025Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learningcited by 12
  2. 2026Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsamplingcited by 2
  3. 2026Frozen Policy Iteration: Computationally Efficient RL under Linear Qπ Realizability for Deterministic Dynamicscited by 0
  4. 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. 2024Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics
  2. 2024The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation
  3. 2022Bellman Residual Orthogonalization for Offline Reinforcement Learning
  4. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning
  5. 2025Gradual Transition from Bellman Optimality Operator to Bellman Operator in Online Reinforcement Learning
  6. 2025Bellman operator convergence enhancements in reinforcement learning algorithms
  7. 2026Lifted Bellman Linear Programming for Offline Reinforcement Learning
  8. 2026Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework