New optimal regret rates found for kernel based reinforcement learning
Minimax Regret for Sobolev Kernel-Based Reinforcement Learning
Machine Learning
Summary
When computers learn how to make decisions step-by-step in complex situations, it’s important to understand how well they can do over time. This paper studies learning when the system’s behavior is smooth and continuous, described by a mathematical space called Sobolev. The authors identify the best possible rate at which errors (regret) improve as the learner experiences more episodes. They also create an algorithm called SOVI that achieves this best rate, separating initial decisions from ongoing learning. This work answers an open question about limits of learning in continuous decision problems under certain smoothness assumptions.
What this means in practice
- •For reinforcement learning engineers: Build algorithms that efficiently learn optimal actions in continuous state and action environments with smoothness constraints.
- •For robotics software developers: Improve robot decision-making by using new sample-efficient learning methods for smooth continuous control tasks.
A theory result. No direct application yet.
Authors
Haichen Hu, David Simchi-Levi
Abstract
We study the minimax regret rate for episodic kernel-based reinforcement learning, where the expected reward and transition density belong to a Sobolev reproducing kernel Hilbert space, with continuous state and action spaces, and adversarial initial states. For Sobolev smoothness parameter $ν>0$, state dimension $d_S$, and action dimension $d_A$, we prove that the minimax expected regret over $T$ episodes is $\widetildeΘ(T^{\max\{e_A,e_B\}})$, where $e_A=\frac{ν+d_A}{2ν+d_A}$, $e_B=\frac{ν+d_A+3d_S/2}{2ν+d_A+2d_S}$ with the other model parameters fixed. The two exponents reflect the distinct difficulties of action selection and learning across states. We introduce Sobolev Optimal Value Iteration (SOVI), which attains this rate from observed rewards and transitions. For fixed smoothness and reference-kernel lengthscale, its regret bound has a prefactor polynomial in the state-action dimension $d=d_S+d_A$, horizon $H$, transition and reward RKHS norm bounds $u,B_r$, and kernel norm-comparison factor $Λ$, up to logarithmic factors. The algorithm separates initial action selection from continuation-value estimation and combines local polynomial approximation with the shared RKHS structure of the approximation errors. Our matching upper and lower bounds determine the optimal dependence on the number of episodes for Sobolev kernel-based reinforcement learning. Thus, we partially address the open problem in Vakili(2024) under the condition of the Sobolev kernel setup.