Near-Optimal Randomized Exploration for Tabular Markov Decision Processes
Near-Optimal Randomized Exploration for Tabular Markov Decision Processes
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Zhihan Xiong;Ruoqi Shen;Qiwen Cui;Maryam Fazel;S. Du
中科院分区：
文献类型：
--
作者：
Zhihan Xiong;Ruoqi Shen;Qiwen Cui;Maryam Fazel;S. Du
我们研究了在强化学习中使用随机化值函数进行探索的算法。这类算法享有诱人的经验性能。我们证明了当我们使用1)单个随机种子和2)Bernstein型噪声强度时，我们得到了插件式非齐次马尔可夫决策过程的最坏情况$宽{O}左(H<sup>Sat}</sup>右)$遗憾界，其中$S$是状态空间的大小，$A$是行动空间的大小，$H$是计划范围，$T$是相互作用的数目。这个界以多项式的形式改进了基于随机值函数的算法的所有现有界，并首次匹配了对数因子的$\Omega\Left(H\Sqrt{SAT}\Right)$下界。我们的结果强调了随机探索可能是近乎最优的，这在以前只有通过乐观的算法才能实现。为了达到预期的结果，我们提出了一种新的裁剪操作，以确保乐观和悲观的概率都是一个常数的下界，以及2)一个新的估计误差绝对值的递推公式来分析后悔。
We study algorithms using randomized value functions for exploration in reinforcement learning. This type of algorithms enjoys appealing empirical performance. We show that when we use 1) a single random seed in each episode, and 2) a Bernstein-type magnitude of noise, we obtain a worst-case $\widetilde{O}\left(H\sqrt{SAT}\right)$ regret bound for episodic time-inhomogeneous Markov Decision Process where $S$ is the size of state space, $A$ is the size of action space, $H$ is the planning horizon and $T$ is the number of interactions. This bound polynomially improves all existing bounds for algorithms based on randomized value functions, and for the first time, matches the $\Omega\left(H\sqrt{SAT}\right)$ lower bound up to logarithmic factors. Our result highlights that randomized exploration can be near-optimal, which was previously achieved only by optimistic algorithms. To achieve the desired result, we develop 1) a new clipping operation to ensure both the probability of being optimistic and the probability of being pessimistic are lower bounded by a constant, and 2) a new recursive formula for the absolute value of estimation errors to analyze the regret.