RL-Lec3 动态规划

动态规划的基本概念

动态规划（Dynamic Programming）是指通过把原问题分解为子问题的方式求解的一类方法，它通过记住求解过的子问题来节省时间。

一般地，适用动态规划解决的问题需要满足如下两个性质：

最优子结构（Optimal Substructure）：整个问题的最优解可以通过求解子问题得到。
重叠子问题（Overlapping Subproblems）：子问题多次重复出现，并且其求解结果可以储存下来并再次使用。

回顾之前介绍的MDP，易知它就满足上述性质：

Bellman方程给出递归分解方法；
值函数可以作为子问题的求解结果。

动态规划是强化学习算法的基础，但一般不能直接应用，因为它要求完整的MDP模型，而且计算量较高。理想情况下，动态规划求解MDP问题有以下两个方面：

预测（Prediction）：计算特定策略 $\pi$ 的值函数 $v_\pi$。
控制（Control）：给定MDP问题得出最优值函数 $v^\star$ 或最优策略 $\pi^\star$。

迭代策略评估（Iterative Policy Evaluation）

策略评估是指给定策略 $\pi$，计算其值函数 $v_\pi$，根据贝尔曼方程有

$\displaystyle v_\pi(s)=\sum_{a\in\mathcal A}\pi(a\mid s)\left(\mathcal R_s^a+\gamma\sum_{s'\in\mathcal S}\mathcal P_{ss'}^av_\pi(s')\right).$

在Lec2.1节已经介绍了策略评估的直接求解方式，它的计算复杂度完全来自于矩阵求逆的复杂度，为 $O(N^3)$。

而根据迭代的思想，在第 $k+1$ 次迭代中，对所有状态 $s\in\cal S$，基于 $v_k(s’)$ 更新 $v_{k+1}(s)$，直至收敛，即迭代公式为

$\displaystyle v_\pi^{k+1}(s)=\sum_{a\in\mathcal A}\pi(a\mid s)\left(\mathcal R_s^a+\gamma\sum_{s'\in\mathcal S}\mathcal P_{ss'}^av_\pi^k(s')\right).$

当两次迭代之间的值函数的差距很小时，则不再迭代，认为已求出其值函数。

策略迭代（Policy Iteration）

当我们对一个策略有了评估方法之后，进一步只需要改进策略即可。这里的思想是基于 $v_\pi$ 采用贪婪的策略，即

$\pi'(s)=\underset{a\in\cal A}{\arg\max}\left(\mathcal R_s^a+\gamma\sum_{s'\in\cal S}\mathcal P_{ss'}^av_\pi(s')\right).$

有了新的策略就再进行评估，再改进策略，直至策略不再改进为止。

值迭代（Value Iteration）

当已知所有子问题的解 $v_\star(s’)$ 时，最终结果可以通过值迭代的方式计算：

$\displaystyle v_\star^{k+1}(s)=\max_{a\in\cal A}\left[\mathcal R_s^a+\gamma\sum_{s'\in\mathcal S}\mathcal P_{ss'}^av_\star^k(s')\right].$

进一步由 $v_\star(s)$ 可以计算出 $\pi_\star(s)$。

一般来说，策略迭代的收敛速度更快一些。在状态空间较小时，最好选用策略迭代方法；在状态空间较大时，值迭代的计算量更小一些。

迭代策略评估每步迭代的时间复杂度为 $O(mn^2)$；
策略迭代每步迭代的时间复杂度为 $O(mn^2+n^3)$；
值迭代每步迭代的时间复杂度为 $O(mn^2)$。

上述算法采用状态值函数 $v_\pi(s)$，也可以采用行动值函数 $q_\pi(s,a)$，而值迭代每步的时间复杂度提高为 $O(m^2n^2)$。这里 $m$ 表示行动总数，$n$ 表示状态总数。

异步动态规划

前面介绍的动态规划方法是同步动态规划，它存在的问题是当状态空间很大时计算代价较大。而异步动态规划则是选择状态分别更新，可以避免更新一些与最优策略无关的状态。

原位动态规划（In-place dynamic programming）

同步值迭代存储两份值函数，而原位动态规划只存储一份，随时更新。这种方法可以减少保存的状态价值的数量，但收敛速度可能较慢。
优先扫描（Prioritized sweeping）

对每一个状态进行优先级分级，优先级越高的状态其状态价值优先得到更新。常常使用贝尔曼误差（即新状态价值与前次计算得到的状态价值差的绝对值）来评估状态的优先级。这种方法可以加快收敛速度，但需要维护一个优先级队列。
实时动态规划（Real-time dynamic programming）

直接使用个体与环境交互产生的实际经历来更新状态价值，对于那些个体实际经历过的状态进行价值更新。个体经常访问过的状态将得到较高频次的价值更新，收敛速度可能稍慢。

算法的收敛性证明

称一个向量空间 $\cal X$ 上的算子 $F$ 是 $\gamma$-收缩的（其中 $0<\gamma<1$），当且仅当对任意的 $x,y\in\cal X$，有

$\|F(x)-F(y)\|\leq\gamma\|x-y\|.$

定理(收缩映射定理) 对于任何在算子 $T(v)$ 下完备的度量空间 $\cal V$，其中 $T$ 是 $\gamma$-收缩的，则 $T$ 以线性收敛速率 $\gamma$ 收敛到一个唯一的不动点。

考虑由所有可能值函数构成的向量空间 $\cal V$，定义两个算子：

贝尔曼期望算子 $F^\pi$：$F^\pi(v)=R^\pi+\gamma P^\pi v$；
贝尔曼最优算子 $F^\star$：$F^\star(v)=\max_{a}[R(a)+\gamma P(a)v]$。

定义两个值函数 $U$ 和 $V$ 的距离为

$\|U-V\|_\infty=\max_s\mid U(s)-V(s)\mid.$

则贝尔曼期望算子和贝尔曼最优算子都是 $\gamma$-收缩的，因此它们都各自有唯一的不动点，这就证明了上述算法的收敛性。

后记

本文内容来自中国科学技术大学《强化学习》（2022Fall）课件。

如对本文内容有任何疑问，请联系 watthu@mail.ustc.edu.cn。

Dynamic Programming