mlsanityData to 7 Oct 2026

End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions

arXiv 2603.23461 ↗First posted 24 Mar 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We study reinforcement learning (RL) with linear function approximation in Markov Decision Processes (MDPs) satisfying linear Bellman completeness -- a fundamental setting where the Bellman backup of any linear value function remains linear. While statistically tractable, prior computationally efficient algorithms are either limited to small action spaces or require strong oracle assumptions over the feature space. We provide a computationally efficient algorithm for linear Bellman complete MDPs with deterministic transitions, stochastic initial states, and stochastic rewards. For finite action spaces, our algorithm is end-to-end efficient; for large or infinite action spaces, we require only a standard argmax oracle over actions. Our algorithm learns an varepsilon-optimal policy with sample and computational complexity polynomial in the horizon, feature dimension, and 1/varepsilon.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 34 of its 49 references that are in the map. First posted on arXiv 24 Mar 2026.

Builds on

34 of 49 references.

References · 34

  1. 2022Training language models to follow instructions with human feedbackcited by 15,712
  2. 2017Proximal Policy Optimization Algorithmscited by 14,441
  3. 2018Learning Dexterous In-Hand Manipulationcited by 643
  4. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  5. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  6. 2018Is Q-learning Provably Efficient?cited by 485
  7. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  8. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  9. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  10. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  11. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  12. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 158
22 more
  1. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  2. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  3. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  4. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  5. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  6. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  7. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  8. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  9. 2023Making RL with Preference-based Feedback Efficient via Randomizationcited by 46
  10. 2025Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Explorationcited by 34
  11. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  12. 2014Statistical and computational trade-offs in estimation of sparse principal componentscited by 26
  13. 2023Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RLcited by 22
  14. 2013Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalizationcited by 19
  15. 2020Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexitycited by 19
  16. 2020Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iterationcited by 19
  17. 2023Efficient Model-Free Exploration in Low-Rank MDPscited by 16
  18. 2018Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approachescited by 5
  19. 2023Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oraclescited by 5
  20. 2024Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamicscited by 5
  21. 2024Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actionscited by 4
  22. 2019Sample-Optimal Parametric Q-Learning Using Linearly Additive Featurescited by 2

Built on by

Not cited yet.