Planning by Prioritized Sweeping with Small Backups
Harm van Seijen Richard S. Sutton Department of Computing Science, University of Alberta, Edmonton, Alberta, T6G 2E8, Canada
Abstract
Efficient planning plays a crucial role in model-based reinforcement learning. Traditionally, the main planning operation is a full backup based on the current estimates of the successor states. Consequently, its computation time is proportional to the number of successor states. In this paper, we introduce a new planning backup that uses only the current value of a single successor state and has a computation time independent of the number of successor states. This new backup, which we call a small backup, opens the door to a new class of model-based reinforcement learning methods that exhibit much finer control over their planning process than traditional methods. We empirically demonstrate that this increased flexibility allows for more efficient planning by showing that an implementation of prioritized sweeping based on small backups achieves a substantial performance improvement over classical implementations.
中文速览
在基于模型的强化学习（model-based RL）中，规划效率至关重要，而传统的"完整备份"（full backup）每次更新一个状态的价值时，必须遍历它所有的后继状态，计算代价随状态数线性增长。本文提出了一种名为"小备份"（small backup）的新操作：每次只利用单个后继状态的当前价值来增量式地更新状态价值，计算量与后继状态总数无关，只需额外存储每个状态对各后继状态的局部价值估计。基于这一机制，作者重新设计了优先级扫描（prioritized sweeping）算法，使其能以更细粒度、更灵活地分配计算资源，实验结果表明新方法在规划效率上显著优于两种经典实现；此外，每步仅做一次小备份的方案在计算复杂度上与TD(0)相当，却无需调整步长参数，性能可媲美精心调参后的TD(0)。这项工作为在计算预算有限的场景下构建更高效、更易用的基于模型强化学习方法提供了新的基础工具。
原文 arXiv:1301.2343;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1301.2343v1