《强化学习：原理与Python实现 》 —3.4.2　异步动态规划

3.4.2　异步动态规划

上一节提到，扫描一遍全部状态可能会涉及许多无意义的状态，浪费过多的时间和计算资源。本节介绍的异步动态规划（asynchronous dynamic programming）可以解决部分问题。

异步动态规划的思想是，每次扫描不再完整地更新一整套状态价值函数，而是只更新部分感兴趣的值。例如，有些状态不会转移到另一些状态（例如对任意均有的状态），那么更新状态的价值函数后再更新的价值函数就没有意义。通过只做有意义的更新，可能会大大减小计算量。

在异步动态规划中，优先更新（prioritized sweeping）是一种根据Bellman误差来选择性更新状态的算法。在迭代过程中，当更新一个状态后，试图找到一个Bellman误差最大的状态并更新该状态。具体而言，当更新一个状态价值函数后，针对这个状态价值函数会影响到的状态价值函数，计算Bellman误差：

并用一个优先队列来维护各状态的Bellman误差。然后从队头中取出Bellman误差最大的状态，更新其状态价值函数。