Beyond No Regret: Instance-Dependent PAC Reinforcement Learning
Beyond No Regret: Instance-Dependent PAC Reinforcement Learning
复制标题
DOI：
--
复制
发表时间：
2021-08
期刊：
影响因子：
--
通讯作者：
Andrew J. Wagenmaker;Max Simchowitz;Kevin G. Jamieson
中科院分区：
文献类型：
--
作者：
Andrew J. Wagenmaker;Max Simchowitz;Kevin G. Jamieson
强化学习理论聚焦于两个基本问题：实现低遗憾值以及识别$\epsilon$-最优策略。虽然一种简单的归约允许人们应用一种低遗憾值算法来获得一个$\epsilon$-最优策略并达到最坏情况最优速率，但低遗憾值算法是否能为策略识别获得实例最优速率尚不清楚。我们表明这是不可能的——在实现低遗憾值和以实例最优速率识别一个$\epsilon$-最优策略之间存在一种基本的权衡。受我们负面发现的启发，我们为大概率近似正确（PAC）表格强化学习提出了一种新的依赖实例的样本复杂度度量，它明确考虑了基础马尔可夫决策过程（MDP）中可达到的状态访问分布。然后我们提出并分析了一种新颖的、基于规划的算法，该算法达到了这种样本复杂度——产生了一种随次优性差距和一个状态的“可达性”而缩放的复杂度。我们表明我们的算法近乎是极小极大最优的，并且在几个例子中，我们的依赖实例的样本复杂度相较于最坏情况界限有显著的改进。
The theory of reinforcement learning has focused on two fundamental problems: achieving low regret, and identifying -optimal policies. While a simple reduction allows one to apply a low-regret algorithm to obtain an -optimal policy and achieve the worst-case optimal rate, it is unknown whether low-regret algorithms can obtain the instance-optimal rate for policy identification. We show that this is not possible—there exists a fundamental tradeoff between achieving low regret and identifying an -optimal policy at the instance-optimal rate. Motivated by our negative finding, we propose a new measure of instance-dependent sample complexity for PAC tabular reinforcement learning which explicitly accounts for the attainable state visitation distributions in the underlying MDP. We then propose and analyze a novel, planning-based algorithm which attains this sample complexity—yielding a complexity which scales with the suboptimality gaps and the “reachability” of a state. We show that our algorithm is nearly minimax optimal, and on several examples that our instance-dependent sample complexity offers significant improvements over worst-case bounds.