# No-Regret Reinforcement Learning in Smooth MDPs

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

## Key facts

- Cited by 6 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 29 of its 65 references that are in the map.
- First posted on arXiv 6 Feb 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, 29 of 29)

- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [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)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [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)
- [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)
- [Information Theoretic Regret Bounds for Online Nonlinear Control](https://mlsanity.com/paper/2006.12466/) (2020)
- [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)
- [Control Frequency Adaptation via Action Persistence in Batch Reinforcement Learning](https://mlsanity.com/paper/2002.06836/) (2020)
- [Metrics and continuity in reinforcement learning](https://mlsanity.com/paper/2102.01514/) (2021)
- [A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learning](https://mlsanity.com/paper/2111.11485/) (2021)
- [Kernel-Based Reinforcement Learning: A Finite-Time Analysis](https://mlsanity.com/paper/2004.05599/) (2020)
- [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)
- [Online Regret Bounds for Undiscounted Continuous Reinforcement Learning](https://mlsanity.com/paper/1302.2550/) (2013)
- [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)
- [Adaptive Discretization for Model-Based Reinforcement Learning](https://mlsanity.com/paper/2007.00717/) (2020)
- [A theoretical framework for calibration in computer models: parametrization, estimation and convergence properties](https://mlsanity.com/paper/1508.07155/) (2015)
- [Smooth Bandit Optimization: Generalization to H"older Space](https://mlsanity.com/paper/2012.06076/) (2020)
- [Tight Performance Guarantees of Imitator Policies with Continuous Actions](https://mlsanity.com/paper/2212.03922/) (2022)
- [On Thompson Sampling for Smoother-than-Lipschitz Bandits](https://mlsanity.com/paper/2001.02323/) (2020)

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

- [Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs](https://mlsanity.com/paper/2405.06363/) (2024)
- [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)
- [Learning Kernel-Based MDPs from Episodic Preferential Feedback](https://mlsanity.com/paper/2605.23650/) (2026)

## Abstract (arXiv)

Obtaining no-regret guarantees for reinforcement learning (RL) in the case of problems with continuous state and/or action spaces is still one of the major open challenges in the field. Recently, a variety of solutions have been proposed, but besides very specific settings, the general problem remains unsolved. In this paper, we introduce a novel structural assumption on the Markov decision processes (MDPs), namely nu-smoothness, that generalizes most of the settings proposed so far (e.g., linear MDPs and Lipschitz MDPs). To face this challenging scenario, we propose two algorithms for regret minimization in nu-smooth MDPs. Both algorithms build upon the idea of constructing an MDP representation through an orthogonal feature map based on Legendre polynomials. The first algorithm, textscLegendre-Eleanor, archives the no-regret property under weaker assumptions but is computationally inefficient, whereas the second one, textscLegendre-LSVI, runs in polynomial time, although for a smaller class of problems. After analyzing their regret properties, we compare our results with state-of-the-art ones from RL theory, showing that our algorithms achieve the best guarantees.