mlsanityData to 14 Oct 2026

Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs

arXiv 2410.24071 ↗First posted 31 Oct 2024cs.LGcited by 4

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Achieving the no-regret property for Reinforcement Learning (RL) problems in continuous state and action-space environments is one of the major open problems in the field. Existing solutions either work under very specific assumptions or achieve bounds that are vacuous in some regimes. Furthermore, many structural assumptions are known to suffer from a provably unavoidable exponential dependence on the time horizon H in the regret, which makes any possible solution unfeasible in practice. In this paper, we identify local linearity as the feature that makes Markov Decision Processes (MDPs) both learnable (sublinear regret) and feasible (regret that is polynomial in H). We define a novel MDP representation class, namely Locally Linearizable MDPs, generalizing other representation classes like Linear MDPs and MDPS with low inherent Belmman error. Then, i) we introduce Cinderella, a no-regret algorithm for this general representation class, and ii) we show that all known learnable and feasible MDP families are representable in this class. We first show that all known feasible MDPs belong to a family that we call Mildly Smooth MDPs. Then, we show how any mildly smooth MDP can be represented as a Locally Linearizable MDP by an appropriate choice of representation. This way, Cinderella is shown to achieve state-of-the-art regret bounds for all previously known (and some new) continuous MDPs for which RL is learnable and feasible.

Key facts. Cited by 4 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 27 of its 42 references that are in the map. First posted on arXiv 31 Oct 2024.

Builds on

27 of 42 references.

Closest ancestors · 2

Same direction, newest first

  1. 2024Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs10 May
  2. 2024No-Regret Reinforcement Learning in Smooth MDPs6 Feb

Other references · 25

  1. 2016OpenAI Gymcited by 1,736
  2. 2020Deep Reinforcement Learning for Autonomous Driving: A Surveycited by 721
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  4. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  5. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  6. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  7. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
  8. 2021Recent Advances in Reinforcement Learning in Financecited by 110
  9. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  10. 2018Lipschitz Continuity in Model-based Reinforcement Learningcited by 91
  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 70
13 more
  1. 2020Bandit optimisation of functions in the Mat'ern kernel RKHScited by 40
  2. 2019On Online Learning in Kernelized Markov Decision Processescited by 35
  3. 2020Control Frequency Adaptation via Action Persistence in Batch Reinforcement Learningcited by 28
  4. 2021Metrics and continuity in reinforcement learningcited by 26
  5. 2020Kernel-Based Reinforcement Learning: A Finite-Time Analysiscited by 23
  6. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  7. 2019Efficient Model-free Reinforcement Learning in Metric Spacescited by 18
  8. 2019Adaptive Discretization for Episodic Reinforcement Learning in Metric Spacescited by 16
  9. 2022Delayed Reinforcement Learning by Imitationcited by 16
  10. 2020Adaptive Discretization for Model-Based Reinforcement Learningcited by 13
  11. 2023Sample Path Regularity of Gaussian Processes from the Covariance Kernelcited by 11
  12. 2020Smooth Bandit Optimization: Generalization to H"older Spacecited by 10
  13. 2022Tight Performance Guarantees of Imitator Policies with Continuous Actionscited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 1; 2026: 2.

4 papers.

  1. 2025The Confusing Instance Principle for Online Linear Quadratic Controlcited by 1
  2. 2024Finite Sample Bounds for Non-Parametric Regression: Optimal Sample Efficiency and Space Complexitycited by 0
  3. 2026Sharper Guarantees for Misspecified Kernelized Bandit Optimizationcited by 0
  4. 2026Learning Kernel-Based MDPs from Episodic Preferential Feedbackcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Achieving Constant Regret in Linear Markov Decision Processes
  2. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
  3. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs
  4. 2024Horizon-Free Regret for Linear Markov Decision Processes
  5. 2024Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs
  6. 2026Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochs
  7. 2021Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuity
  8. 2024Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation