First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach
This work addresses a core gap in sequential decision-making for reinforcement learning researchers, providing a novel regret bound that scales with the optimal policy performance rather than worst-case scenarios.
The paper tackles the problem of obtaining first-order regret bounds in reinforcement learning with large state spaces, specifically in the linear MDP setting, and achieves a regret scaling of $\widetilde{\mathcal{O}}(\sqrt{d^3 H^3 \cdot V_1^\star \cdot K} + d^{3.5}H^3\log K)$, where $V_1^\star$ is the optimal policy value and $K$ is the number of episodes.
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.