Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret
Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret
复制标题
DOI：
--
复制
发表时间：
2021-04
期刊：
影响因子：
--
通讯作者：
Jean Tarbouriech;Runlong Zhou;S. Du;Matteo Pirotta;M. Valko;A. Lazaric
中科院分区：
文献类型：
--
作者：
Jean Tarbouriech;Runlong Zhou;S. Du;Matteo Pirotta;M. Valko;A. Lazaric
我们研究了随机最短路径（SSP）设置下的学习问题，其中智能体寻求在达到目标状态之前最小化累积的期望成本。我们设计了一种新的基于模型的EB-SSP算法，该算法仔细地扭曲了经验转换，并用探索奖励扰动了经验成本，以保证关联值迭代方案的乐观性和收敛性。我们证明了EB-SSP实现了最小最大后悔率$\ widdetilde {O}(B_{\star} \sqrt{S A K})$，其中$K$为事件数，$S$为状态数，$A$为行动数，$B_{\star}$界为任何状态下最优策略的期望累积成本，从而缩小了与下界的差距。有趣的是，EB-SSP在无参数的情况下得到了这个结果，也就是说，它不需要任何关于$B_{\star}$的先验知识，也不需要$T_{\star}$的先验知识，而$T_{\star}$限制了从任何状态到最优策略的预期时间。此外，我们还举例说明了各种情况（例如，正数成本，或当阶精确估计$T_{\star}$可用时的一般成本），其中遗憾仅包含对$T_{\star}$的对数依赖，从而产生超越有限视界MDP设置的第一个无视界遗憾界。
We study the problem of learning in the stochastic shortest path (SSP) setting, where an agent seeks to minimize the expected cost accumulated before reaching a goal state. We design a novel model-based algorithm EB-SSP that carefully skews the empirical transitions and perturbs the empirical costs with an exploration bonus to guarantee both optimism and convergence of the associated value iteration scheme. We prove that EB-SSP achieves the minimax regret rate $\widetilde{O}(B_{\star} \sqrt{S A K})$, where $K$ is the number of episodes, $S$ is the number of states, $A$ is the number of actions and $B_{\star}$ bounds the expected cumulative cost of the optimal policy from any state, thus closing the gap with the lower bound. Interestingly, EB-SSP obtains this result while being parameter-free, i.e., it does not require any prior knowledge of $B_{\star}$, nor of $T_{\star}$ which bounds the expected time-to-goal of the optimal policy from any state. Furthermore, we illustrate various cases (e.g., positive costs, or general costs when an order-accurate estimate of $T_{\star}$ is available) where the regret only contains a logarithmic dependence on $T_{\star}$, thus yielding the first horizon-free regret bound beyond the finite-horizon MDP setting.