First-Order Regret in Reinforcement Learning with Linear Function
  Approximation: A Robust Estimation Approach
  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 $\mathcal{O}(\sqrt{V_1^\star
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.
