Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost-猫眼课题宝

DOI：

发表时间：

2022-02

期刊：

ArXiv

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Dan Qiao;Ming Yin;Ming Min;Yu-Xiang Wang

我们研究了具有低（策略）切换成本的强化学习（RL）问题-这是一个由现实生活中的RL应用程序驱动的问题，其中部署新策略的成本很高，并且策略更新的数量必须很低。在本文中，我们提出了一个新的算法，基于阶段明智的探索和自适应的政策消除，实现了遗憾的$\widetilde{O}（\sqrt{H^4S^2AT}）$，而需要的切换成本为$O（HSA \log\log T）$。这是一个指数级的改进，在现有的方法中，最著名的转换成本为O（H^2SA\log T）$，具有$\widetilde{O}（\mathrm{poly}（H，S，A）\sqrt{T}）$遗憾。在上面，$S，A$表示具有未知转移的$H$-水平情景马尔可夫决策过程模型中的状态和动作的数量，$T$是步骤的数量。作为我们的新技术的副产品，我们还得到了一个无奖励的探索算法的切换成本为O（HSA）$。此外，我们证明了一对信息理论的下界，即（1）任何无遗憾算法必须有一个切换成本$\Omega（HSA）$;（2）任何$\widetilde{O}（\sqrt{T}）$遗憾算法必须招致一个切换成本$\Omega（HSA\log\log T）$。因此，我们的算法是最佳的切换成本。

We study the problem of reinforcement learning (RL) with low (policy) switching cost - a problem well-motivated by real-life RL applications in which deployments of new policies are costly and the number of policy updates must be low. In this paper, we propose a new algorithm based on stage-wise exploration and adaptive policy elimination that achieves a regret of $\widetilde{O}(\sqrt{H^4S^2AT})$ while requiring a switching cost of $O(HSA \log\log T)$. This is an exponential improvement over the best-known switching cost $O(H^2SA\log T)$ among existing methods with $\widetilde{O}(\mathrm{poly}(H,S,A)\sqrt{T})$ regret. In the above, $S,A$ denotes the number of states and actions in an $H$-horizon episodic Markov Decision Process model with unknown transitions, and $T$ is the number of steps. As a byproduct of our new techniques, we also derive a reward-free exploration algorithm with a switching cost of $O(HSA)$. Furthermore, we prove a pair of information-theoretical lower bounds which say that (1) Any no-regret algorithm must have a switching cost of $\Omega(HSA)$; (2) Any $\widetilde{O}(\sqrt{T})$ regret algorithm must incur a switching cost of $\Omega(HSA\log\log T)$. Both our algorithms are thus optimal in their switching costs.

Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost

文献摘要

相似文献