First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach
First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach
复制标题
DOI：
--
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
Andrew J. Wagenmaker;Yifang Chen;Max Simchowitz;S. Du;Kevin G. Jamieson
中科院分区：
文献类型：
--
作者：
Andrew J. Wagenmaker;Yifang Chen;Max Simchowitz;S. Du;Kevin G. Jamieson
获得一阶后悔界限-后悔界限不是作为最坏的情况，但在给定的情况下，最优策略的性能的一些措施-是一个核心问题，在顺序决策。虽然这种界限存在于许多设置中，但它们在具有大状态空间的强化学习中被证明是难以捉摸的。在这项工作中，我们解决了这一差距，并表明在具有大状态空间的强化学习中，即线性MDP设置中，可以获得后悔缩放为$\widetilde{\mathcal{O}}（\sqrt{d^3 H^3 \cdot V_1^\star \cdot K} + d^{3.5}H^3\log K）$。这里$V_1 ^\star $是最优策略的值，$K$是发作次数。我们表明，现有的技术基于最小二乘估计是不足以获得这一结果，而是开发一种新的强大的自我归一化浓度界的基础上强大的Catoni平均估计，这可能是独立的利益。
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.