跳转至

2 基于动态规划的强化学习算法

针对白箱环境，可以使用基于动态规划的强化学习算法。主要有两种：策略迭代（policy iteration）与价值迭代（value iteration）。价值迭代是策略迭代的优化版本。

这两种方法有以下局限：

  1. 需要事先知道环境的状态转移函数 \(\mathcal{P}\) 和奖励函数 \(\mathcal{R}\) ，即整个马尔可夫决策过程（白盒环境，不需要智能体与环境多次交互学习，直接动态规划得最优策略）；
  2. 只适用于有限马尔可夫决策过程，即状态空间和动作空间是离散且有限的。

1 策略迭代

强化学习的终极目的是获得一个最佳策略。

“策略迭代”的意思是从一个策略开始不断优化，直至最佳策略。策略迭代由策略评估（policy evaluation）和策略提升（policy improvement）两部分组成。

  1. “策略评估”：判断当前策略有多好；
  2. “策略提升”：优化当前策略。

1.1 策略评估

1.1a 核心思路与公式

已知贝尔曼期望方程

\[V^{\pi}(s) = \sum_{a\in A}\pi(a|s)\left(r(s,a)+\gamma\sum_{s'\in S}P\left(s'|s,a\right)V^{\pi}\left(s'\right)\right) \tag{1-1}\]

该方程描述了从状态 s 出发遵循策略 \(\pi\) 能获得的期望回报。我们利用期望回报来判断一个策略有多好。

问题是，在已知一个策略 a 的情况下，怎么获知一个策略在不同状态 s 下的期望回报？

答案如下：

\[ V^{k+1}(s) = \sum_{a\in A}\pi(a|s)\left(r(s,a)+\gamma\sum_{s'\in S}P\left(s'|s,a\right)V^{k}\left(s'\right)\right) \tag{1-2} \]

我们任意选定不同状态的期望回报初始值 \(V^0\) ，不断迭代，当 \(k\to\infty\) 后，可以使序列 \(\left\{V^{k}\right\}\) 收敛到当前策略的状态价值函数 \(V^{\pi}\) 。

1.1b 收敛性证明

我们用 # 算符表示式 (1-2) 所示的迭代过程，即

\[V^{k+1}(s) = \#\left\{V^{k}(s)\right\} \tag{1-3}\]

我们要证明序列 \(\left\{V^k\right\}\) 收敛到 \(V^\pi\) ，就是要证明 \(V^{k}\) 迭代成 \(V^{k+1}=\#\left\{V^{k}\right\}\) 之后，与 \(V^{\pi}\) 的差距变小了，即

\[\left|\#\left\{V\right\} - V^{\pi}\right| \le \left|V-V^{\pi}\right| \tag{1-4}\]

一方面，我们注意到式 (1-4) 是和状态 s 相关的。但是，上式是否需要在所有状态 s 下都成立呢？

此处 s 是离散、有限的，因此我们实际上可以遍历所有 s 。

其实不然，可以放宽条件，只要求 \(\max_{s} \left|\#\left\{V\right\} - V^{\pi}\right| \le \max_{s} \left|V-V^{\pi}\right|\) 。这个结论比较显然，参照以下示意图：

另一方面，注意到 \(V^\pi\) 是迭代的不动点，满足 \(V^{\pi} = \#\left\{V^{\pi}\right\}\) 。综合以上两方面，要证明的条件——式 (1-4)——可改成

\[\max_{s}\left|\#\{V\}-\#\{V^{\pi}\}\right| \le \max_{s}\left|V - V^{\pi}\right| \tag{1-5}\]

我们来尝试证明式 (1-5)：

\[\begin{aligned} &\max_{s}\left|\#\{V\}-\#\{V^{\pi}\}\right|\\ =& \max_{s}\left|\sum_{a\in\mathcal{A}}\pi(a|s)\left(r(s,a)+\gamma\sum_{s'\in\mathcal{S}}P(s'|s,a)V(s')\right) - \sum_{a\in\mathcal{A}}\pi(a|s)\left(r(s,a)+\gamma\sum_{s'\in\mathcal{S}}P(s'|s,a)V^{\pi}(s')\right)\right|\\ =& \max_{s}\left|\sum_{a\in\mathcal{A}}\pi(a|s)\left[\gamma\sum_{s'\in\mathcal{S}}P(s'|s,a)\left(V(s')-V^{\pi}(s')\right)\right]\right|\\ =& \gamma\max_{s}\left|\sum_{a\in\mathcal{A}}\pi(a|s)\sum_{s'\in\mathcal{S}}P(s'|s,a)\left[V(s')-V^{\pi}(s')\right]\right|\\ \le&\gamma\max_{s}\left|\sum_{a\in\mathcal{A}}\pi(a|s)\left[\sum_{s'\in\mathcal{S}}P(s'|s,a)\max_{s'}\left|V(s')-V^{\pi}(s')\right|\right]\right|\\ \end{aligned}\]

这里的 \(\max_{s'}\left|V(s')-V^{\pi}(s')\right|\) 是个常数项，可以提出来，即

\[\begin{aligned} &\max_{s}\left|\#\{V\}-\#\{V^{\pi}\}\right|\\ \le&\gamma\max_{s}\left|\sum_{a\in\mathcal{A}}\pi(a|s)\left[\sum_{s'\in\mathcal{S}}P(s'|s,a)\max_{s'}\left|V(s')-V^{\pi}(s')\right|\right]\right|\\ =&\gamma\max_{s'}\left|V(s')-V^{\pi}(s')\right|\max_{s}\left|\sum_{a\in\mathcal{A}}\pi(a|s)\sum_{s'\in\mathcal{S}}P(s'|s,a)\right|\\ =&\gamma\max_{s'}\left|V(s')-V^{\pi}(s')\right|\max_{s}\left|\sum_{a\in\mathcal{A}}\pi(a|s)\right|\\ =&\gamma\max_{s'}\left|V(s')-V^{\pi}(s')\right|\\ \le& \max_{s'}\left|V(s')-V^{\pi}(s')\right| \end{aligned}\]

证毕。

1.2 策略提升

知道了当前策略的状态价值函数 \(V^\pi\) 之后，我们要想办法获得一个更好的策略。

如果我们在状态 s 下不采取动作 \(\pi(s)\) ，而采取另一个动作 a ，之后的所有动作仍然遵循策略 \(\pi\) ，此时的动作价值函数为 \(Q^\pi(s,a)\) 。如果 \(Q^\pi(s,a) > V^\pi(s)\) ，这就说明状态 s 下采取动作 a 是更好的。

策略提升定理

假设存在一个确定性策略 \(\pi'\) ，若和当前策略 \(\pi\) 相比，在任意一个状态 s 下，都满足动作价值函数 \(Q^{\pi}\left(s,\pi'(s)\right) \ge V^{\pi}(s)\) ，则在任意状态 \(s\) 下都有 \(V^{\pi'}(s) \ge V^{\pi}(s)\) 。

根据此定理，我们贪心地更新策略 \(\pi\) 为 \(\pi'\) （对每个状态，都尝试选一个最好的动作使期望回报最大）：

\[ \pi'(s) = \arg\max_{a}Q^{\pi}(s,a) \]

\(\pi'(s)\) 就是一个确定性的策略了，不存在概率分布。

怎么知道什么动作的期望回报最大呢？这就要利用策略评估得到的状态价值函数了：

\[\begin{aligned} \pi'(s) &= \arg\max_{a}Q^{\pi}(s,a)\\ &= \arg\max_{a}\left\{r(s,a)+\gamma\sum_{s'\in \mathcal{S}}P\left(s'|s,a\right)V^{\pi}\left(s'\right)\right\} \end{aligned}\]

整个策略迭代算法的流程为：首先初始化策略 \(\pi(s)\) 和价值函数 \(V(s)\) ，然后反复进行策略评估和策略提升，直到策略足够好。

收敛性证明： 每次迭代后的 \(\pi_{k+1}\) 都优于 \(\pi_{k}\) ，因此只要总策略数是有限的，就能迭代出一个最优策略。

2 价值迭代

2.1 核心思路与公式

策略迭代需要多轮“评估—提升”收敛，计算量大。

我们反思一下。策略迭代中，针对待优化策略，我们需要大量计算获得其策略价值函数 \(V^{\pi}\) ，再进行策略提升。策略评估过程浪费了计算量。

Example

当策略价值函数 \(V^{k}\) 收敛到一定程度时，无论如何继续收敛，策略提升得到的更优策略都是同一个策略。此时，继续进行策略评估就是在浪费计算量。

价值迭代基于贝尔曼最优方程，优化策略迭代过程。贝尔曼最优方程为：

\[V^{*}(s) = \max_{a\in\mathcal{A}}\left\{r(s,a)+\gamma\sum_{s'\in\mathcal{S}}P\left(s'|s,a\right)V^{*}\left(s'\right)\right\}\]

价值迭代方程为：

\[V^{k+1}(s) = \max_{a\in\mathcal{A}}\left\{r(s,a)+\gamma\sum_{s'\in\mathcal{S}}P\left(s'|s,a\right)V^{k}\left(s'\right)\right\}\]

收敛完成后，如下恢复出最优策略：

\[ \pi(s) = \arg\max_a\left\{r(s,a)+\gamma\sum_{s'}P\left(s'|s,a\right)V^{k+1}\left(s'\right)\right\} \]

2.2 收敛性证明

思路和策略评估的收敛性证明一致。若设

\[\begin{aligned} V^{k+1}(s) &= \max_{a\in\mathcal{A}}\left\{r(s,a)+\gamma\sum_{s'\in\mathcal{S}}P\left(s'|s,a\right)V^{k}\left(s'\right)\right\}\\ &= \S\left\{ V^{k}(s) \right\} \end{aligned}\]

易知 \(V^{*}(s)\) 是一个不动点。我们要证明

\[\max_{s}\left|\S(V)-\S(V^{*})\right| \le \max_{s}\left|V-V^{*}\right|\]

证明过程如下：

\[\begin{aligned} &\max_{s}\left|\S(V)-\S(V^{*})\right|\\ =&\max_{s}\left|\max_{a\in\mathcal{A}}\left\{r(s,a)+\gamma\sum_{s'\in\mathcal{S}}P\left(s'|s,a\right)V\left(s'\right)\right\} - \max_{a'\in\mathcal{A}}\left\{r(s,a')+\gamma\sum_{s'\in\mathcal{S}}P\left(s'|s,a'\right)V^{*}\left(s'\right)\right\}\right|\\ \le&\max_{s,a}\left|r(s,a)+\gamma\sum_{s'\in\mathcal{S}}P\left(s'|s,a\right)V\left(s'\right)-r(s,a)+\gamma\sum_{s'\in\mathcal{S}}P\left(s'|s,a\right)V^{*}\left(s'\right)\right|\\ =& \gamma\max_{s,a}\left|\sum_{s'\in\mathcal{S}}P(s'|s,a)\left[V(s')-V^{*}(s')\right]\right| \end{aligned}\]

Note

上面这个不等号本质上是

\[\max_{a_1\in\mathcal{A}}f_1(a_1) - \max_{a_2\in\mathcal{A}}f_2(a_2) \le \max_{a\in\mathcal{A}}\left[f_1(a)-f_2(a)\right]\]

这个式子没有那么显然，可以如下证明：

设 \(a_1 = \arg\max_{a\in\mathcal{A}}f_1(a)\) 以及 \(a_2 = \arg\max_{a\in\mathcal{A}}f_2(a)\) 。

首先，若 \(a_1 = a_2\) ，则等式左边为 \(f_1(a)-f_2(a)\) ，必然小于等于等式右边取 \(\max\) 后的结果。

其次，若 \(a_1 \neq a_2\) ，即 \(f_2(a_2) > f_2(a_1)\) ，则有 \(\max_{a\in\mathcal{A}}\left[f_1(a)-f_2(a)\right] \ge f_1(a_1) - f_2(a_1) > f_1(a_1)-f_2(a_2)\) 。

综合以上两种情况，上式得证。

继续证明：

\[\begin{aligned} &\max_{s}\left|\S(V)-\S(V^{*})\right|\\ \le& \gamma\max_{s,a}\left|\sum_{s'\in\mathcal{S}}P(s'|s,a)\left[V(s')-V^{*}(s')\right]\right|\\ \le& \gamma\max_{s,a}\left|\sum_{s'\in\mathcal{S}}P(s'|s,a)\max_{s'}\left|V(s')-V^{*}(s')\right|\right|\\ =&\gamma\max_{s'}\left|V(s')-V^{*}(s')\right|\max_{s,a}\left|\sum_{s'\in\mathcal{S}}P(s'|s,a)\right|\\ =&\gamma\max_{s'}\left|V(s')-V^{*}(s')\right|\\ \le&\max_{s'}\left|V(s')-V^{*}(s')\right| \end{aligned}\]

证毕。