Timezone: »

 
Oral
First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach
Andrew Wagenmaker · Yifang Chen · Max Simchowitz · Simon Du · Kevin Jamieson

Thu Jul 21 07:30 AM -- 07:50 AM (PDT) @ Ballroom 3 & 4
in T: Bandits/Online Learning/Reinforcement Learning »
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.
Keywords: Reinforcement Learning · RL: Function Approximation · RL: Online · T: Reinforcement Learning and Planning

Author Information

Andrew Wagenmaker (University of Washington)
Yifang Chen (University of Washington)
Max Simchowitz (MIT)
Simon Du (University of Washington)
Kevin Jamieson (University of Washington)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors