mlsanityData to 7 Oct 2026

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

arXiv 2405.06363 ↗First posted 10 May 2024cs.LG cs.AIcited by 5

Not on the map. Why?

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.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 22 of its 43 references that are in the map. First posted on arXiv 10 May 2024.

Builds on

22 of 43 references.

References · 22

  1. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,873
  2. 2020Deep Reinforcement Learning for Autonomous Driving: A Surveycited by 698
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  4. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  5. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  6. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  7. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  8. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  9. 2021Recent Advances in Reinforcement Learning in Financecited by 102
  10. 2018Lipschitz Continuity in Model-based Reinforcement Learningcited by 90
  11. 2018Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulatorcited by 86
  12. 2019Learning Linear-Quadratic Regulators Efficiently with only √T Regretcited by 67
10 more
  1. 2021Metrics and continuity in reinforcement learningcited by 26
  2. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  3. 2019Efficient Model-free Reinforcement Learning in Metric Spacescited by 18
  4. 2019Adaptive Discretization for Episodic Reinforcement Learning in Metric Spacescited by 16
  5. 2023Efficient Model-Free Exploration in Low-Rank MDPscited by 16
  6. 2022Delayed Reinforcement Learning by Imitationcited by 15
  7. 2018Optimization of Smooth Functions with Noisy Observations: Local Minimax Ratescited by 14
  8. 2023Sample Efficient Deep Reinforcement Learning via Local Planningcited by 9
  9. 2022Tight Performance Guarantees of Imitator Policies with Continuous Actionscited by 6
  10. 2024No-Regret Reinforcement Learning in Smooth MDPscited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 4; 2025: 0; 2026: 1.

5 papers.

  1. 2024Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPscited by 4
  2. 2024Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learningcited by 1
  3. 2024Provably Adaptive Average Reward Reinforcement Learning for Metric Spacescited by 0
  4. 2024Finite Sample Bounds for Non-Parametric Regression: Optimal Sample Efficiency and Space Complexitycited by 0
  5. 2026Sample Complexity of Equivariant Reinforcement Learningcited by 0