mlsanityData to 14 Oct 2026

Kernelized Reinforcement Learning with Order Optimal Regret Bounds

arXiv 2306.07745 ↗First posted 13 Jun 2023cs.LG cs.AI stat.MLcited by 20

Not on the map. Why?

Abstract (arXiv)

Reinforcement learning (RL) has shown empirical success in various real world settings with complex models and large state-action spaces. The existing analytical results, however, typically focus on settings with a small number of state-actions or simple models such as linearly modeled state-action value functions. To derive RL policies that efficiently handle large state-action spaces with more general value functions, some recent works have considered nonlinear function approximation using kernel ridge regression. We propose π-KRVI, an optimistic modification of least-squares value iteration, when the state-action value function is represented by a reproducing kernel Hilbert space (RKHS). We prove the first order-optimal regret guarantees under a general setting. Our results show a significant polynomial in the number of episodes improvement over the state of the art. In particular, with highly non-smooth kernels (such as Neural Tangent kernel or some Mat'ern kernels) the existing results lead to trivial (superlinear in the number of episodes) regret bounds. We show a sublinear regret bound that is order optimal in the case of Mat'ern kernels where a lower bound on regret is known.

Key facts. Cited by 20 papers in the map (data through 14 Oct 2026). Builds on 26 of its 47 references that are in the map. First posted on arXiv 13 Jun 2023.

Builds on

26 of 47 references.

References · 26

  1. 2018QT-Opt: Scalable Deep Reinforcement Learning for Vision-Based Robotic Manipulationcited by 743
  2. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 573
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  4. 2018Is Q-learning Provably Efficient?cited by 487
  5. 2017On Kernelized Multi-armed Banditscited by 352
  6. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  7. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  8. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  9. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
  10. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  11. 2017Uncertainty-Aware Reinforcement Learning for Collision Avoidancecited by 88
  12. 2020Mat'ern Gaussian processes on Riemannian manifoldscited by 82
14 more
  1. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 78
  2. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  3. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  4. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 54
  5. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 52
  6. 2020Bandit optimisation of functions in the Mat'ern kernel RKHScited by 40
  7. 2021Neural Contextual Bandits without Regretcited by 40
  8. 2020A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performancecited by 39
  9. 2019On Online Learning in Kernelized Markov Decision Processescited by 35
  10. 2020Kernel-Based Reinforcement Learning: A Finite-Time Analysiscited by 23
  11. 2021Uniform Generalization Bounds for Overparameterized Neural Networkscited by 21
  12. 2022Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learningcited by 18
  13. 2021Open Problem: Tight Online Confidence Intervals for RKHS Elementscited by 13
  14. 2023Sample Complexity of Kernel-Based Q-Learningcited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 7; 2025: 6; 2026: 6.

20 papers.

Sort:

By area:

  1. 2025Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimizationcited by 13
  2. 2023Minimax Optimal Q Learning with Nearest Neighborscited by 8
  3. 2024Tighter Confidence Bounds for Sequential Kernel Regressioncited by 8
  4. 2024No-Regret Reinforcement Learning in Smooth MDPscited by 6
  5. 2024Variational Search Distributionscited by 6
  6. 2024Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithmcited by 6
  7. 2024Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPscited by 5
  8. 2024Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPscited by 4
  9. 2025No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processescited by 4
  10. 2025Vector-valued self-normalized concentration inequalities beyond sub-Gaussianitycited by 4
  11. 2025Wasserstein Distributionally Robust Bayesian Optimization with Continuous Contextcited by 3
  12. 2026Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spacescited by 2
8 more
  1. 2024A Differential and Pointwise Control Approach to Reinforcement Learningcited by 1
  2. 2025Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learningcited by 1
  3. 2026One-Step Bellman Alignment Enables Provably Efficient Transfer in Online RLcited by 1
  4. 2025Reinforcement Learning Using known Invariancescited by 0
  5. 2026Fitted Q-Iteration with Continuous Actions and Adaptive Data: Smoothed Coverage and Minimax Ratescited by 0
  6. 2026Sharper Guarantees for Misspecified Kernelized Bandit Optimizationcited by 0
  7. 2026Improved Model-based Reinforcement Learning with Smooth Kernelscited by 0
  8. 2026Learning Kernel-Based MDPs from Episodic Preferential Feedbackcited by 0