← 研踪 PaperTrailarXiv:2610.34045 · v2
Minimax Regret for Sobolev Kernel-Based Reinforcement Learning
首次提交 2026-10-25 12:12
版本更新 2026-11-07 09:46
雷达观测 2026-11-10 10:11
摘要
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 (RKHS), 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 (\texttt{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$, reward and transition RKHS norm bounds $B_r,B_p$, and the norm-comparison factor $Λ$, up to logarithmic factors; $Λ=1$ for normalized Matérn kernels. 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 regret minimization. Thus, we partially address the open problem in Vakili(2024) under Sobolev kernel RL.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-07 09:46 · 最新观测版本
Minimax Regret for Sobolev Kernel-Based Reinforcement Learning
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 (RKHS), 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 (\texttt{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$, reward and transition RKHS norm bounds $B_r,B_p$, and the norm-comparison factor $Λ$, up to logarithmic factors; $Λ=1$ for normalized Matérn kernels. 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 regret minimization. Thus, we partially address the open problem in Vakili(2024) under Sobolev kernel RL.
查看此版本解读 →查看此版本原文 ↗