Minimax Regret for Sobolev Kernel-Based Reinforcement Learning
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 dS, and action dimension dA, we prove that the minimax expected regret over T episodes is Θ̃(Tmax{eA,eB}), where eA=(ν+dA)/(2ν+dA), eB=(ν+dA+3dS/2)/(2ν+dA+2dS) 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=dS+dA, horizon H, transition and reward RKHS norm bounds u,Br, 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.
Related
- Frequency-Uniform Log-Regret Reinforcement Learning for Diffusions
- Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning
- Minimax-Optimality of Posterior Sampling for Reinforcement Learning
- Reinforcement Learning for Hierarchical Reasoning Rewards: Minimax-Optimal Rates with Transformers
- Near Minimax Rate for Quantile Distributional Reinforcement Learning
BibTeX
@misc{hu2026minimax,
title = {{Minimax Regret for Sobolev Kernel-Based Reinforcement Learning}},
author = {Haichen Hu and David Simchi-Levi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34045},
eprint = {2610.34045},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34045},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Minimax Regret for Sobolev Kernel-Based Reinforcement Learning
AU - Haichen Hu
AU - David Simchi-Levi
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2610.34045
UR - https://arxiv.org/abs/2610.34045
AB - 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 Θ̃(T^max{e_A,e_B}), where e_A=(ν+d_A)/(2ν+d_A), e_B=(ν+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.
ER -