End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911541946744832 |
|---|---|
| author | Mhammedi, Zakaria Rakhlin, Alexander Okolo, Nneka |
| author_facet | Mhammedi, Zakaria Rakhlin, Alexander Okolo, Nneka |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_23461 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions Mhammedi, Zakaria Rakhlin, Alexander Okolo, Nneka Machine Learning 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$. |
| title | End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2603.23461 |