Computational Benefits of Intermediate Rewards for Goal-Reaching Policy Learning
Computational Benefits of Intermediate Rewards for Goal-Reaching Policy Learning
复制标题
DOI：
10.1613/jair.1.13326
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
Yuexiang Zhai;Christina Baek;Zhengyuan Zhou;Jiantao Jiao;Yi Ma
中科院分区：
文献类型：
--
作者：
Yuexiang Zhai;Christina Baek;Zhengyuan Zhou;Jiantao Jiao;Yi Ma
许多达成目标的强化学习（RL）任务已经通过经验验证，在子目标上奖励智能体可以提高收敛速度和实际性能。我们试图提供一个理论框架，以同步值迭代的次数来量化奖励完成子目标的计算效益。特别是，我们将子目标视为单向中间状态，每集只能访问一次，并提出了两种考虑这些单向中间状态的设置：单向单路径（OWSP）和单向多路径（OWMP）设置。在OWSP和OWMP设置中，我们证明了向子目标添加中间奖励比仅在智能体完成到达终端状态的目标时进行奖励更具计算效率。我们还揭示了在OWMP设置中计算复杂性和追求最短路径之间的权衡：添加中间奖励显着降低了达到目标的计算复杂性，但智能体可能找不到最短路径，而使用稀疏的终端奖励，智能体以显着更高的计算成本找到最短路径。我们还在MiniGrid环境中使用Q-learning和一些流行的深度强化学习算法进行了大量实验，证实了我们的理论结果。
Many goal-reaching reinforcement learning (RL) tasks have empirically verified that rewarding the agent on subgoals improves convergence speed and practical performance. We attempt to provide a theoretical framework to quantify the computational benefits of rewarding the completion of subgoals, in terms of the number of synchronous value iterations. In particular, we consider subgoals as one-way intermediate states, which can only be visited once per episode and propose two settings that consider these one-way intermediate states: the one-way single-path (OWSP) and the one-way multi-path (OWMP) settings. In both OWSP and OWMP settings, we demonstrate that adding intermediate rewards to subgoals is more computationally efficient than only rewarding the agent once it completes the goal of reaching a terminal state. We also reveal a trade-off between computational complexity and the pursuit of the shortest path in the OWMP setting: adding intermediate rewards significantly reduces the computational complexity of reaching the goal but the agent may not find the shortest path, whereas with sparse terminal rewards, the agent finds the shortest path at a significantly higher computational cost. We also corroborate our theoretical results with extensive experiments on the MiniGrid environments using Q-learning and some popular deep RL algorithms.