Obtaining first-order regret bounds -- regret bounds scaling not as the
worst-case but with some measure of the performance of the optimal policy on a
given instance -- is a core question in sequential decision-making. While such
bounds exist in many settings, they have proven elusive in reinforcement
learning with large state spaces. In this work we address this gap, and show
that it is possible to obtain regret scaling as
$\widetilde{\mathcal{O}}(\sqrt{d^3 H^3 \cdot V_1^\star \cdot K} +
d^{3.5}H^3\log K )$ in reinforcement learning with large state spaces, namely
the linear MDP setting. Here $V_1^\star$ is the value of the optimal policy and
$K$ is the number of episodes. We demonstrate that existing techniques based on
least squares estimation are insufficient to obtain this result, and instead
develop a novel robust self-normalized concentration bound based on the robust
Catoni mean estimator, which may be of independent interest.

本研究基于鲁棒 Catoni 平均值估计器，提出一种新的鲁棒自归一化浓度界，解决了已有技术在大状态空间强化学习中无法获得遗憾上界的问题，并证明了在线性 MDP 设定下，可以获得与最优策略性能某种度量成比例的遗憾上界。