# Kernel-Based Reinforcement Learning: A Finite-Time Analysis

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Apr 2020.

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

- [Kernelized Reinforcement Learning with Order Optimal Regret Bounds](https://mlsanity.com/paper/2306.07745/) (2023)
- [Unlocking the Power of Representations in Long-term Novelty-based Exploration](https://mlsanity.com/paper/2305.01521/) (2023)
- [Sample Complexity of Kernel-Based Q-Learning](https://mlsanity.com/paper/2302.00727/) (2023)
- [Minimax Optimal Q Learning with Nearest Neighbors](https://mlsanity.com/paper/2308.01490/) (2023)
- [Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Data](https://mlsanity.com/paper/2411.03810/) (2024)
- [Near-optimal Policy Identification in Active Reinforcement Learning](https://mlsanity.com/paper/2212.09510/) (2022)
- [No-Regret Reinforcement Learning in Smooth MDPs](https://mlsanity.com/paper/2402.03792/) (2024)
- [Near-optimal Conservative Exploration in Reinforcement Learning under Episode-wise Constraints](https://mlsanity.com/paper/2306.06265/) (2023)
- [Provably Efficient Kernelized Q-Learning](https://mlsanity.com/paper/2204.10349/) (2022)
- [Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs](https://mlsanity.com/paper/2410.24071/) (2024)
- [A Kernel Perspective on Behavioural Metrics for Markov Decision Processes](https://mlsanity.com/paper/2310.19804/) (2023)
- [Quantizer Design for Finite Model Approximations, Model Learning, and Quantized Q-Learning for MDPs with Unbounded Spaces](https://mlsanity.com/paper/2510.04355/) (2025)
- [UVIP: Model-Free Approach to Evaluate Reinforcement Learning Algorithms](https://mlsanity.com/paper/2105.02135/) (2021)
- [Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2405.18793/) (2024)
- [Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learning](https://mlsanity.com/paper/2502.07715/) (2025)
- [Provably Adaptive Average Reward Reinforcement Learning for Metric Spaces](https://mlsanity.com/paper/2410.19919/) (2024)
- [Reinforcement Learning Using known Invariances](https://mlsanity.com/paper/2511.03473/) (2025)
- [SHAP-Guided Kernel Actor-Critic for Explainable Reinforcement Learning](https://mlsanity.com/paper/2512.05291/) (2025)
- [Generalisation in Multitask Fitted Q-Iteration and Offline Q-learning](https://mlsanity.com/paper/2512.20220/) (2025)
- [Fitted Q-Iteration with Continuous Actions and Adaptive Data: Smoothed Coverage and Minimax Rates](https://mlsanity.com/paper/2605.05791/) (2026)
- [Improved Model-based Reinforcement Learning with Smooth Kernels](https://mlsanity.com/paper/2605.07218/) (2026)
- [Kernel-Based Safe Exploration in Deep Reinforcement Learning](https://mlsanity.com/paper/2605.22207/) (2026)
- [Mathematical methods of reinforcement learning](https://mlsanity.com/paper/2607.06935/) (2026)

## Abstract (arXiv)

We consider the exploration-exploitation dilemma in finite-horizon reinforcement learning problems whose state-action space is endowed with a metric. We introduce Kernel-UCBVI, a model-based optimistic algorithm that leverages the smoothness of the MDP and a non-parametric kernel estimator of the rewards and transitions to efficiently balance exploration and exploitation. For problems with K episodes and horizon H, we provide a regret bound of widetildeOleft( H3 K^frac2d2d+1right), where d is the covering dimension of the joint state-action space. This is the first regret bound for kernel-based RL using smoothing kernels, which requires very weak assumptions on the MDP and has been previously applied to a wide range of tasks. We empirically validate our approach in continuous MDPs with sparse rewards.