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

Read full text Summarise with VIRAT
Authors: Zakaria Mhammedi, Alexander Rakhlin, Nneka Okolo
Cited by: 0
References: 24

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

We study reinforcement learning (RL) with linear function approximation in Markov Decision Processes (MDPs) satisfying \emph{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 \emph{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$.

Fields of Study & Subjects

Reinforcement Learning in Robotics Advanced Bandit Algorithms Research Machine Learning and Algorithms

Publication details

Journal / source
arXiv (Cornell University)
Publication date
24 March 2026
Language
EN
Document type
Preprint