# Kernelized Reinforcement Learning with Order Optimal Regret Bounds

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

## 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 (most cited first, 26 of 26)

- [QT-Opt: Scalable Deep Reinforcement Learning for Vision-Based Robotic Manipulation](https://mlsanity.com/paper/1806.10293/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [Uncertainty-Aware Reinforcement Learning for Collision Avoidance](https://mlsanity.com/paper/1702.01182/) (2017)
- [Mat'ern Gaussian processes on Riemannian manifolds](https://mlsanity.com/paper/2006.10160/) (2020)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [Worst-Case Regret Bounds for Exploration via Randomized Value Functions](https://mlsanity.com/paper/1906.02870/) (2019)
- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [A Unifying View of Optimism in Episodic Reinforcement Learning](https://mlsanity.com/paper/2007.01891/) (2020)
- [Bandit optimisation of functions in the Mat'ern kernel RKHS](https://mlsanity.com/paper/2001.10396/) (2020)
- [Neural Contextual Bandits without Regret](https://mlsanity.com/paper/2107.03144/) (2021)
- [A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance](https://mlsanity.com/paper/2010.13997/) (2020)
- [On Online Learning in Kernelized Markov Decision Processes](https://mlsanity.com/paper/1911.01871/) (2019)
- [Kernel-Based Reinforcement Learning: A Finite-Time Analysis](https://mlsanity.com/paper/2004.05599/) (2020)
- [Uniform Generalization Bounds for Overparameterized Neural Networks](https://mlsanity.com/paper/2109.06099/) (2021)
- [Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning](https://mlsanity.com/paper/2202.04005/) (2022)
- [Open Problem: Tight Online Confidence Intervals for RKHS Elements](https://mlsanity.com/paper/2110.15458/) (2021)
- [Sample Complexity of Kernel-Based Q-Learning](https://mlsanity.com/paper/2302.00727/) (2023)

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

- [Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization](https://mlsanity.com/paper/2506.01393/) (2025)
- [Minimax Optimal Q Learning with Nearest Neighbors](https://mlsanity.com/paper/2308.01490/) (2023)
- [Tighter Confidence Bounds for Sequential Kernel Regression](https://mlsanity.com/paper/2403.12732/) (2024)
- [No-Regret Reinforcement Learning in Smooth MDPs](https://mlsanity.com/paper/2402.03792/) (2024)
- [Variational Search Distributions](https://mlsanity.com/paper/2409.06142/) (2024)
- [Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm](https://mlsanity.com/paper/2410.23498/) (2024)
- [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)
- [No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes](https://mlsanity.com/paper/2510.20725/) (2025)
- [Vector-valued self-normalized concentration inequalities beyond sub-Gaussianity](https://mlsanity.com/paper/2511.03606/) (2025)
- [Wasserstein Distributionally Robust Bayesian Optimization with Continuous Context](https://mlsanity.com/paper/2503.20341/) (2025)
- [Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spaces](https://mlsanity.com/paper/2603.08287/) (2026)
- [A Differential and Pointwise Control Approach to Reinforcement Learning](https://mlsanity.com/paper/2404.15617/) (2024)
- [Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learning](https://mlsanity.com/paper/2502.07715/) (2025)
- [One-Step Bellman Alignment Enables Provably Efficient Transfer in Online RL](https://mlsanity.com/paper/2601.21924/) (2026)
- [Reinforcement Learning Using known Invariances](https://mlsanity.com/paper/2511.03473/) (2025)
- [Fitted Q-Iteration with Continuous Actions and Adaptive Data: Smoothed Coverage and Minimax Rates](https://mlsanity.com/paper/2605.05791/) (2026)
- [Sharper Guarantees for Misspecified Kernelized Bandit Optimization](https://mlsanity.com/paper/2605.05967/) (2026)
- [Improved Model-based Reinforcement Learning with Smooth Kernels](https://mlsanity.com/paper/2605.07218/) (2026)
- [Learning Kernel-Based MDPs from Episodic Preferential Feedback](https://mlsanity.com/paper/2605.23650/) (2026)

## 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.