# Value Function Approximations via Kernel Embeddings for No-Regret Reinforcement Learning

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Nov 2020.

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

- [Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm](https://mlsanity.com/paper/2410.23498/) (2024)
- [Distributional Bellman Operators over Mean Embeddings](https://mlsanity.com/paper/2312.07358/) (2023)
- [Open Problem: Order Optimal Regret Bounds for Kernel-Based Reinforcement Learning](https://mlsanity.com/paper/2406.15250/) (2024)
- [Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learning](https://mlsanity.com/paper/2502.07715/) (2025)
- [Bayesian Transfer Operators in Reproducing Kernel Hilbert Spaces](https://mlsanity.com/paper/2509.22482/) (2025)
- [Improved Model-based Reinforcement Learning with Smooth Kernels](https://mlsanity.com/paper/2605.07218/) (2026)
- [Sequential operator learning under dependent data](https://mlsanity.com/paper/2608.24426/) (2026)

## Abstract (arXiv)

We consider the regret minimization problem in reinforcement learning (RL) in the episodic setting. In many real-world RL environments, the state and action spaces are continuous or very large. Existing approaches establish regret guarantees by either a low-dimensional representation of the stochastic transition model or an approximation of the Q-functions. However, the understanding of function approximation schemes for state-value functions largely remains missing. In this paper, we propose an online model-based RL algorithm, namely the CME-RL, that learns representations of transition distributions as embeddings in a reproducing kernel Hilbert space while carefully balancing the exploitation-exploration tradeoff. We demonstrate the efficiency of our algorithm by proving a frequentist (worst-case) regret bound that is of order tildeObig(HγN√Nbig)footnote tildeO(·) hides only absolute constant and poly-logarithmic factors., where H is the episode length, N is the total number of time steps and γN is an information theoretic quantity relating the effective dimension of the state-action feature space. Our method bypasses the need for estimating transition probabilities and applies to any domain on which kernels can be defined. It also brings new insights into the general theory of kernel methods for approximate inference and RL regret minimization.