Unverified

Order-Optimal Regret Bounds for Kernel-Based Reinforcement Learning

Consider an episodic Markov decision process with state space $S$ , action space $A$ , horizon $H$ , and $T$ episodes. Put $Z=S\times A$ . Let $\mathcal H_k$ be the RKHS of a positive-definite kernel $k\colon Z\times Z\to\mathbb R$ . Assume that, for every stage $h\in[H]$ and next state $s'\in S$ , the function $z\mapsto P_h(s'\mid z)$ belongs to $\mathcal H_k$ and has RKHS norm at most a constant $u$ .

Can one design a no-regret learning algorithm under this assumption?
What is the minimum possible regret growth with $T$ and $H$ ?
Can an algorithm achieve order-optimal or near-order-optimal regret, closely matching the established lower bound?

Download

Abstract

For episodic reinforcement learning whose transition model lies in a reproducing kernel Hilbert space, determine whether no-regret learning is possible and identify the optimal dependence of regret on the number of episodes and the horizon.

Background and progress

Kernel models extend linear Markov decision processes to possibly infinite-dimensional feature spaces. Existing kernel-based RL analyses either impose stronger assumptions or produce bounds that do not align with the lower-bound behavior. Kernel ridge regression supplies predictions and uncertainty estimates, but the transition observations are not independent scalar-noise observations of the Bellman target, which obstructs direct use of kernel-bandit confidence bounds [Chowdhury and Oliveira, 2023]. The open problem is posed directly in [Vakili, 2024].

Reference papers

Open Problem: Order Optimal Regret Bounds for Kernel-Based Reinforcement LearningSattar VakiliProceedings of Thirty Seventh Conference on Learning Theory · 2024 ↗
Value Function Approximations via Kernel Embeddings for No-Regret Reinforcement LearningSayak Ray Chowdhury, Rafael OliveiraAsian Conference on Machine Learning · 2023

Order-Optimal Regret Bounds for Kernel-Based Reinforcement Learning

Coming soon

Organizer