Is Long Horizon RL More Difficult Than Short Horizon RL?
Is Long Horizon RL More Difficult Than Short Horizon RL?
复制标题
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Ruosong Wang;S. Du;Lin F. Yang;S. Kakade
中科院分区：
文献类型：
--
作者：
Ruosong Wang;S. Du;Lin F. Yang;S. Kakade
学习规划长期视野是情景强化学习问题的核心挑战。一个基本的问题是理解问题的难度如何随着视野的增加而扩大。在这里，样本复杂度的自然度量是归一化的：我们感兴趣的是可证明地发现其值接近最优值的策略所需的事件数，其中该值由每个事件的归一化累积奖励来衡量。在COLT 2018年的一个公开问题中，Jiang和Agarwal指出，对于表格式的情景强化学习问题，存在一个样本复杂度下限，该下限表现出对视界的多项式依赖性-这一猜想与所有已知的样本复杂度上限一致。这项工作驳斥了这一猜想，证明了表格式、情景式强化学习是可能的，其样本复杂度仅与规划范围成比例。换句话说，当这些值被适当地归一化（位于单位区间内）时，这个结果表明长时间范围RL并不比短时间范围RL更困难，至少在极大极小意义上是这样。我们的分析引入了两个想法：（i）为近似最优策略构建一个ε -网，其对数覆盖数仅与规划范围成几何比例，以及（ii）在线轨迹合成算法，该算法自适应地评估给定策略类中的所有策略，并具有与给定策略类的基数成几何比例的样本复杂度。两者可能是独立的利益。
Learning to plan for long horizons is a central challenge in episodic reinforcement learning problems. A fundamental question is to understand how the difficulty of the problem scales as the horizon increases. Here the natural measure of sample complexity is a normalized one: we are interested in the number of episodes it takes to provably discover a policy whose value is ε near to that of the optimal value, where the value is measured by the normalized cumulative reward in each episode. In a COLT 2018 open problem, Jiang and Agarwal conjectured that, for tabular, episodic reinforcement learning problems, there exists a sample complexity lower bound which exhibits a polynomial dependence on the horizon — a conjecture which is consistent with all known sample complexity upper bounds. This work refutes this conjecture, proving that tabular, episodic reinforcement learning is possible with a sample complexity that scales only logarithmically with the planning horizon. In other words, when the values are appropriately normalized (to lie in the unit interval), this results shows that long horizon RL is no more difficult than short horizon RL, at least in a minimax sense. Our analysis introduces two ideas: (i) the construction of an ε -net for near-optimal policies whose log-covering number scales only logarithmically with the planning horizon, and (ii) the Online Trajectory Synthesis algorithm, which adaptively evaluates all policies in a given policy class and enjoys a sample complexity that scales logarithmically with the cardinality of the given policy class. Both may be of independent interest.