arXiv preprint ·
Minimax Regret for Sobolev Kernel-Based Reinforcement Learning
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
On the asymptotic behaviour of $α$-divergence generalized posteriors
Inference for Causal Path-Specific Effects in Longitudinal Studies with Repeated Treatments and Multiple Mediators
Minimax Rates for Conditional Generative Learning under Wasserstein Loss
Intrinsic Gradient Barriers in Pushforward Deep Generative Models
Provably Efficient Q-learning for Robust Reinforcement Learning
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.