# Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs

arXiv: https://arxiv.org/abs/2405.06363 · HTML: https://mlsanity.com/paper/2405.06363/

## 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 22 of its 43 references that are in the map.
- First posted on arXiv 10 May 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 22 of 22)

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Recent Advances in Reinforcement Learning in Finance](https://mlsanity.com/paper/2112.04553/) (2021)
- [Lipschitz Continuity in Model-based Reinforcement Learning](https://mlsanity.com/paper/1804.07193/) (2018)
- [Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator](https://mlsanity.com/paper/1805.09388/) (2018)
- [Learning Linear-Quadratic Regulators Efficiently with only √T Regret](https://mlsanity.com/paper/1902.06223/) (2019)
- [Metrics and continuity in reinforcement learning](https://mlsanity.com/paper/2102.01514/) (2021)
- [Kernelized Reinforcement Learning with Order Optimal Regret Bounds](https://mlsanity.com/paper/2306.07745/) (2023)
- [Efficient Model-free Reinforcement Learning in Metric Spaces](https://mlsanity.com/paper/1905.00475/) (2019)
- [Adaptive Discretization for Episodic Reinforcement Learning in Metric Spaces](https://mlsanity.com/paper/1910.08151/) (2019)
- [Delayed Reinforcement Learning by Imitation](https://mlsanity.com/paper/2205.05569/) (2022)
- [Efficient Model-Free Exploration in Low-Rank MDPs](https://mlsanity.com/paper/2307.03997/) (2023)
- [Optimization of Smooth Functions with Noisy Observations: Local Minimax Rates](https://mlsanity.com/paper/1803.08586/) (2018)
- [Sample Efficient Deep Reinforcement Learning via Local Planning](https://mlsanity.com/paper/2301.12579/) (2023)
- [Tight Performance Guarantees of Imitator Policies with Continuous Actions](https://mlsanity.com/paper/2212.03922/) (2022)
- [No-Regret Reinforcement Learning in Smooth MDPs](https://mlsanity.com/paper/2402.03792/) (2024)

## Built on by (most cited first, 5 of 5)

- [Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs](https://mlsanity.com/paper/2410.24071/) (2024)
- [Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2405.18793/) (2024)
- [Provably Adaptive Average Reward Reinforcement Learning for Metric Spaces](https://mlsanity.com/paper/2410.19919/) (2024)
- [Finite Sample Bounds for Non-Parametric Regression: Optimal Sample Efficiency and Space Complexity](https://mlsanity.com/paper/2412.14744/) (2024)
- [Sample Complexity of Equivariant Reinforcement Learning](https://mlsanity.com/paper/2609.36421/) (2026)

## Abstract (arXiv)

We consider the problem of learning an varepsilon-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Given access to a generative model, we achieve rate-optimal sample complexity by performing a simple, perturbed version of least-squares value iteration with orthogonal trigonometric polynomials as features. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our~widetildeO(ε-2-d/(nu+1)) sample complexity, where d is the dimension of the state-action space and nu the order of smoothness, recovers the state-of-the-art result of discretization approaches for the special case of Lipschitz MDPs (nu=0). At the same time, for nu→∞, it recovers and greatly generalizes the O(ε-2) rate of low-rank MDPs, which are more amenable to regression approaches. In this sense, our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.