C3 贝尔曼最优公式

Policy 改进

设 $\gamma=0.9$，则可以解出上图策略下的 state values 为

$$v_{\pi}(s_1)=8,\\v_{\pi}(s_2)=v_{\pi}(s_3)=v_{\pi}(s_4)=10$$

计算 $s_1$ 的 action values：

$$\begin{array}{l} q _ {\pi} \left(s _ {1}, a _ {1}\right) = - 1 + \gamma v _ {\pi} \left(s _ {1}\right) = 6. 2, \\ q _ {\pi} \left(s _ {1}, a _ {2}\right) = - 1 + \gamma v _ {\pi} \left(s _ {2}\right) = 8, \\ q _ {\pi} \left(s _ {1}, a _ {3}\right) = 0 + \gamma v _ {\pi} \left(s _ {3}\right) = 9, \\ q _ {\pi} \left(s _ {1}, a _ {4}\right) = - 1 + \gamma v _ {\pi} \left(s _ {1}\right) = 6. 2, \\ q _ {\pi} \left(s _ {1}, a _ {5}\right) = 0 + \gamma v _ {\pi} \left(s _ {1}\right) = 7. 2. \\ \end{array}$$

发现在状态 $s_1$ 下采取动作 $a_3$ 有最大的 action value，因此可以将策略改进为在状态 $s_1$ 下采取动作 $a_3$。

optimal policy & optimal state values

若有两个策略 $\pi_1$ 和 $\pi_2$，对于任意的 $s\in\mathcal{S}$，都有 $v_{\pi_1}(s)\geq v_{\pi_2}(s)$，则认为策略 $\pi_1$ 优于策略 $\pi_2$。

因此，一个策略 $\pi^*$ 是 optimal policy（最优策略）当对于任意策略 $\pi$ 和任意状态 $s\in\mathcal{S}$ 都有 $v_{\pi^*}(s)\geq v_{\pi}(s)$，$\pi^*$ 对应的 state values 就是 optimal state values（最优状态价值）。

optimal policy 的存在性、唯一性、确定性和求解正是 **Bellman optimality equation（BOE，贝尔曼最优公式）**需要解决的问题。

贝尔曼最优公式

**Bellman optimality equation（BOE，贝尔曼最优公式）**是分析 optimal policy 和 optimal state values 的一个工具。其 element-wise 形式为

$$\begin{align} v(s) &=\max_{\pi(s)\in\Pi(s)}\sum_{a\in\mathcal{A}(s)}\pi(a|s)\cdot\left(\sum_{r\in\mathcal{R}(s,a)}p(r|s,a)r+\gamma\sum_{s'\in\mathcal{S}}p(s'|s,a)v(s')\right)\\ &=\max_{\pi(s)\in\Pi(s)}\sum_{a\in\mathcal{A}(s)}\pi(a|s)\cdot q(s,a) \end{align}$$

其中 $v(s),v(s')$ 都是待解未知量。$\pi(s)$ 表示 $s$ 状态下的一个策略，待确定；$\Pi(s)$ 表示对于状态 $s$ 的所有可能策略。

其 matrix-vector 形式为

$$v=\max_{\pi\in\Pi}(r_{\pi}+\gamma P_{\pi}v)$$

其中 $v\in\mathbb{R}^{|\mathcal{S}|}$，$\max_{\pi}$ 是逐元素意义上的最大；$r_{\pi}\in\mathbb{R}^{|S|}$ 是每个状态下的即时奖励的期望构成的向量，$P_{\pi}\in\mathbb{R}^{|\mathcal{S}|\times|\mathcal{S}|}$ 是当前环境与策略下的状态转移概率矩阵。

等式的右边称为贝尔曼最优算子。

解的形式

先看解长什么样。注意到这里有两个未知量 $v(s)$ 和 $\pi(s)$，但要求解贝尔曼最优方程，事实上只要关注等式右边即可。

考虑求解这样一个有两个未知量 $x,y\in\mathbb{R}$ 的方程

$$x=\max_{y\in\mathbb{R}}(2x-1-y^2)$$

要想使得右边最大，需令 $y=0$，即 $\max_{y\in\mathbb{R}}(2x-1-y^2)=2x-1$，于是 $x=2x-1$，得 $x=1$。因此该方程的解为 $x=1,y=0$。BOE 也是类似这样的形式，只需要求出令右边项最大的最优策略 $\pi^*$，就可以求出所有的最优状态价值。

而对于等式右边项 $\sum_{a\in\mathcal{A}(s)}\pi(a|s)\cdot q(s,a)$ 的最大值，实际上就是 $q(s,a)$ 中的最大的那一个，即 $\max_{a\in\mathcal{A}(s)}q(s,a)$。

考虑下列式子的最大值

$$\sum_{i=1}^{3}c_{i}q_{i}=c_1q_1+c_2q_2+c_3q_3$$

其中 $c_1+c_2+c_3=1$ 且 $c_1,c_2,c_3\geq 0$。

不失一般性，假设 $q_3\geq q_1,q_2$，则最大值当 $c_3=1$ 且 $c_1=c_2=0$ 时取得，为 $q_3$。这是因为

$$q_3=(c_1+c_2+c_3)q_3=c_1q_3+c_2q_3+c_3q_3\geq c_1q_1+c_2q_2+c_3q_3$$

因此 BOE 解出来的 optimal policy 是确定性的，每一个 $v(s)$ 取得最大值当且仅当

$$\pi(a|s)=\begin{cases} 1, & a=a^*\\ 0, & a\neq a^* \end{cases}$$

其中 $a^*=\arg\max_{a}q(s,a)$。也就是在最优策略下，每一个状态 $s$ 都采取了 action value 最大的那个动作（事实上，这是后续会讲到的贪婪策略）。

解的存在性与唯一性证明

如何证明 BOE 是否存在解，解是否唯一？以及，如果存在解如何求？这需要引入一个理论——contraction mapping theorem（压缩映射理论）。

压缩映射理论

考虑函数 $f(x)$，其中 $x\in\mathbb{R}^d$ 且 $f:\mathbb{R}^d\to\mathbb{R}^d$。若一个点 $x^*$ 满足

$$f(x^*)=x^*$$

则 $x^*$ 称为一个不动点，即 $f$ 将 $x^*$ 映射到自身。

若存在实数 $\gamma\in(0,1)$ 使得函数 $f$ 对任意 $x_1,x_2\in\mathbb{R}^d$ 都满足

$$\left\|f(x_1)-f(x_2)\right\|\le\gamma\left\|x_1-x_2\right\|$$

则函数 $f$ 被称为一个 contraction mapping（压缩映射）。这里 $\|\cdot\|$ 表示向量或矩阵的范数。

例如函数 $f(x)=0.5\sin x,x\in\mathbb{R}$ 为一个压缩映射，因为

$$\begin{align} \left|\frac{f(x_1)-f(x_2)}{x_1-x_2}\right|=\left|\frac{0.5\sin x_1-0.5\sin x_2}{x_1-x_2}\right|&=\left|\frac{\cos\frac{x_1+x_2}{2}\sin\frac{x_1-x_2}{2}}{x_1-x_2}\right|\le\left|0.5\cos\frac{x_1+x_2}{2}\right|\le0.5 \end{align}$$

即 $\left|f(x_1)-f(x_2)\right|\le0.5\left|x_1-x_2\right|$，因此 $f(x)$ 是压缩映射。$x=0$ 是其一个不动点。

压缩映射理论中指出，对于任意满足 $x=f(x)$ 的等式，其中 $x$ 和 $f(x)$ 都是实数或实向量，若函数 $f$ 是压缩映射，则方程的解就满足以下性质（此处不证明）：

• 存在性：存在一个不动点 $x^*$ 满足 $f(x^*)=x^*$。
• 唯一性：不动点 $x^*$ 唯一。
• 求解算法：使用迭代的数值求解 $x_{k+1}=f(x_k)$，对于任意初始值 $x_0$，当 $k\to\infty$ 时都有 $x_{k}\to x^*$，且是指数级收敛。

BOE 满足压缩映射

记贝尔曼最优公式的等式右边为 $f(v)$，即

$$f(v)=\max_{\pi}(r_{\pi}+\gamma P_{\pi}v)$$

则 $f(v)$ 为压缩映射。事实上，对于任意 $v_{1},v_{2}\in R^{|\mathcal{S}|}$，都有

$$\left\|f(v_{1})-f(v_{2})\right\|_{\infty}\le\gamma\left\|v_{1}-v_{2}\right\|_{\infty}$$

其中 $\gamma\in(0,1)$ 是折扣系数，$\|\cdot\|_{\infty}$ 表示无穷范数（$\|X\|_{\infty}=\max_{i}|x_i|$，即所有分量中绝对值最大的一个）。

注意，上述的性质在无穷范数下成立，但在 $l_2$ 范数下一般不再保证相同的压缩因子（甚至可能不是压缩映射）。

因此，贝尔曼最优方程 $v=f(v)$ 存在解且唯一，并能通过迭代的数值方法求解：

$$v_{k+1}\gets \max_{\pi}(r_{\pi}+\gamma P_{\pi}v_{k})$$

每一轮迭代需要根据 $v_{k}$ 确定当前的最优策略 $\pi$，事实上由前面“解的形式”部分可知，对于每个状态 $s$，先利用 $v_{k}(s')$ 求出 $s$ 下所有的 $q_{k}(s,a)$，然后最优策略便为采取 $q_{k}(s,a)$ 中最大的那个动作，即 $\arg\max_{a}q_{k}(s,a)$；随后便得到 $v_{k+1}$ 的第 $i$ 行就是状态 $s_{i}$ 下最大的 $q_{k}(s,a)$（事实上，这是求解贝尔曼最优方程的方法之一 value iteration 方法）。当 $k\to\infty$ 时 $v_{k}\to v^*$。

证明 BOE 满足压缩映射：

考虑两个向量 $v_{1},v_{2}\in\mathbb{R}^{|\mathcal{S}|}$，设 $\pi_{1}^*=\arg\max_{\pi}(r_{\pi}+\gamma P_{\pi}v_{1})$ 和 $\pi_{2}^*=\arg\max_{\pi}(r_{\pi}+\gamma P_{\pi}v_{2})$（这里的 $\pi_{1}^*$ 和 $\pi_{2}^*$ 理解为在当前 state values 分别为 $v_{1}$ 和 $v_{2}$ 时的最优策略，通过采取这些最优策略能够使 state values 向着更优值更新）。因此，有

$$f(v_{1})=\max_{\pi}(r_{\pi}+\gamma P_{\pi}v_{1})=r_{\pi_{1}^*}+\gamma P_{\pi_{1}^*}v_{1}\ge r_{\pi_{2}^*}+\gamma P_{\pi_{2}^*}v_{1}\\ f(v_{2})=\max_{\pi}(r_{\pi}+\gamma P_{\pi}v_{2})=r_{\pi_{2}^*}+\gamma P_{\pi_{2}^*}v_{2}\ge r_{\pi_{1}^*}+\gamma P_{\pi_{1}^*}v_{2}$$

其中 $\ge$ 时逐元素意义上的。因此，有

$$\begin{align} f(v_{1})-f(v_{2})&=r_{\pi_{1}^*}+\gamma P_{\pi_{1}^*}v_{1}-(r_{\pi_{2}^*}+\gamma P_{\pi_{2}^*}v_{2})\\ &\le r_{\pi_{1}^*}+\gamma P_{\pi_{1}^*}v_{1}-(r_{\pi_{1}^*}+\gamma P_{\pi_{1}^*}v_{2})\\ &=\gamma P_{\pi_{1}^*}(v_{1}-v_{2}) \end{align}$$

同理可得 $f(v_{2})-f(v_{1})\le\gamma P_{\pi_{2}^*}(v_{2}-v_{1})$。得

$$\gamma P_{\pi_{2}^*}(v_{1}-v_{2})\le f(v_{1})-f(v_{2})\le\gamma P_{\pi_{1}^*}(v_{1}-v_{2})$$

记

$$z=\max\left\{\left|\gamma P_{\pi_{2}^*}(v_{1}-v_{2})\right|,\left|\gamma P_{\pi_{1}^*}(v_{1}-v_{2})\right|\right\}\in\mathbb{R}^{|\mathcal{S}|}$$

由定义知 $z\ge 0$。其中 $\max(\cdot)$，$|\cdot|$ 和 $\ge$ 都是逐元素意义上的。

因此有

$$-z\le\gamma P_{\pi_{2}^*}(v_{1}-v_{2})\le f(v_{1})-f(v_{2})\le\gamma P_{\pi_{1}^*}(v_{1}-v_{2})\le z$$

即

$$\left|f(v_{1})-f(v_{2})\right|\le z$$

其中 $\le$ 是逐元素意义的。由此可得

$$\left\|f(v_1)-f(v_2)\right\|_{\infty}\le\|z\|_{\infty}\tag{$\ast$}$$

其中 $\|\cdot\|_{\infty}$ 表示无穷范数。上式即 $|f(v_{1})-f(v_{2})|$ 中的最大分量 $\le$ $|z|$ 中的最大分量。

另一方面，记 $z_{i}$ 表示 $z$ 的第 $i$ 项，$p_{i}^T$ 和 $q_i^T$ 分别表示 $P_{\pi_{1}^*}$ 和 $P_{\pi_{2}^*}$ 的第 $i$ 行，则由 $z$ 的定义可知

$$0\le z_{i}=\max\left\{\left|\gamma p_{i}^T(v_{1}-v_{2})\right|,\left|\gamma q_{i}^T(v_{1}-v_{2})\right|\right\}\in\mathbb{R}$$

由于 $p_{i}$ 的每一项都非负且和为一，因此

$$\left|p_{i}^T(v_{1}-v_2)\right|\le p_{i}^T\left|v_{1}-v_2\right|\le\left\|v_{1}-v_{2}\right\|_{\infty}$$

上式第一个不等号为绝对值不等式，第二个等号可以理解为 $p_{i}$ 把所有概率都给了最大的一项。

同理，有 $\left|q_{i}^T(v_{1}-v_2)\right|\le\left\|v_{1}-v_{2}\right\|_{\infty}$。因此，有

$$0\le z_{i}\le\gamma\left\|v_{1}-v_{2}\right\|_{\infty}$$

进一步地，有

$$\|z\|_{\infty}=\max_{i}|z_{i}|\le\gamma\left\|v_{1}-v_{2}\right\|_{\infty}$$

带入 $(*)$ 式，得

$$\left\|f(v_{1})-f(v_{2})\right\|_{\infty}\le\gamma\left\|v_{1}-v_{2}\right\|_{\infty}$$

这体现了 $f(v)$ 在无穷范数下的压缩性质。

解的最优性证明

到目前为止，尽管已经证明了贝尔曼最优方程解的存在性和唯一性，但是并没有说明其解 $\pi^*$ 和 $v^*$ 就是最优策略和最优状态价值。事实上，贝尔曼最优方程解得到的策略 $\pi^*$ 和状态价值 $v^*$ 就是最优的，即对于任何策略 $\pi$，都有

$$v^*=v_{\pi^*}\ge v_{\pi}$$

其中 $\ge$ 是逐元素意义上的，这正符合最优策略和最优状态价值的定义。

解的最优性证明：

由贝尔曼公式，对于任意策略 $\pi$，有

$$v_{\pi}=r_{\pi}+\gamma P_{\pi}v_{\pi}$$

由于

$$v^*=\max_{\pi}(r_{\pi}+\gamma P_{\pi}v^*)=r_{\pi^*}+\gamma P_{\pi^*}v^*\ge r_{\pi}+\gamma P_{\pi}v^*$$

其中 $\ge$ 是逐元素意义上的。因此

$$v^*-v_{\pi}\ge r_{\pi}+\gamma P_{\pi}v^*-(r_{\pi}+\gamma P_{\pi}v_{\pi})=\gamma P_{\pi}(v^*-v_{\pi})$$

于是可以得到

$$v^*-v_{\pi}\ge \gamma P_{\pi}(v^*-v_{\pi})\ge \gamma^2 P_{\pi}^2(v^*-v_{\pi}) \ge\cdots\ge \gamma^n P_{\pi}^n(v^*-v_{\pi})$$

这里的 $P_{\pi}^n$ 所有元素都非负且小于等于 $1$（事实上，就是当前环境与策略 $\pi$ 下经历 $n$ 步的状态转移概率矩阵），而 $\gamma^n$ 当 $n\to\infty$ 时趋于 $0$。因此，当 $n\to\infty$ 时，可以得到

$$v^*-v_{\pi}\ge\lim_{n\to\infty}\gamma^n P_{\pi}^n(v^*-v_{\pi})=0$$

即 $v^*\ge v_{\pi}$ 对于任何策略 $\pi$ 都成立，证毕。

综上，从贝尔曼最优方程解的存在性、唯一性以及其代表着最优策略和最优状态价值可见，它是分析 optimal policy 和 optimal state values 的一个很好的工具。

影响最优策略的因素

结合 element-wise 的 BOE

$$v(s)=\max_{\pi(s)\in\Pi(s)}\sum_{a\in\mathcal{A}(s)}\pi(a|s)\cdot\left(\sum_{r\in\mathcal{R}(s,a)}p(r|s,a)r+\gamma\sum_{s'\in\mathcal{S}}p(s'|s,a)v(s')\right)$$

到这里可以发现 element-wise 形式的公式便于分析，而 matrix-vector 形式便于求解。

可以发现影响方程解的因素有

• 即时奖励 $r$
• 折扣因子 $\gamma$
• 环境模型 $p(r\mid s,a)$，$p(s'\mid s,a)$

环境往往不可改变，因此这里主要讨论能够改变的因素：即时奖励 $r$ 和折扣因子 $\gamma$。

折扣因子

上图均为特定环境和设置下的最优策略。由上图（a）状态 $(4,1)$ 的选择可以看出，它并没有选择绕远路到达终点，而是采取穿过惩罚区域的冒险行为，由此可见在折扣因子 $\gamma=0.9$ 较大的情况下，最优策略会更加远视，看重长远收益。相反图（b）的最优策略则相对保守，更加短时，注重即时收益。

此外，还可以见得靠近终点的状态会有更高的价值，因为在折扣因子的作用下，离终点越远的状态获得的正奖励（到达终点）越小，而越近的状态获得的正奖励越大。

即时奖励

显然，如果对某些状态下的某些行为给予更多的正奖励或者惩罚，那么最优策略会相应地做出偏好或避免的趋势。但是，最优策略在某些情况下是会保持不变的：对即时奖励 $r$ 进行 affine tranformations（仿射变换），也就是对所有的即时奖励都扩大相同倍数或改变相同的量。

一个变换 $T:\mathbb{R}^n\to\mathbb{R}^m$ 称为Affine Transformation（仿射变换），如果它可以表示为

$$T(\mathbf{x})=A\mathbf{x}+\mathbf{b}$$

其中 $A\in\mathbb{R}^{m\times n}$，$b\in\mathbb{R}^m$。当 $\mathbf{b}=\mathbf{0}$，$T$ 退化为线性变换。

仿射变换可以看作线性变换 + 平移。

考虑一个 MDP，其最优状态价值为 $v^*\in\mathbb{R}^{|\mathcal{S}|}$ 满足 $v^*=\max_{\pi}(r_{\pi}+\gamma P_{\pi}v^*)$。若每一个奖励 $r\in\mathcal{R}$ 都被仿射变换为 $\alpha r+\beta$，其中 $\alpha,\beta\in\mathbb{R}$ 且 $\alpha>0$，则相应的最优状态价值 $v'$ 也是 $v^*$ 的仿射变换：

$$v'=\alpha v^*+\frac{\beta}{1-\gamma}\mathbf{1}$$

其中 $\gamma\in(0,1)$ 是折扣因子，$\mathbf{1}=\left[1,\dots,1\right]^T\in\mathbb{R}^{|\mathcal{S}|}$。相应地，所有 action value 也是原来的仿射变换，因此在 $\alpha>0$ 时最优策略选取的最大 action value 的动作仍为原来最优策略选取的动作，即最优策略不变。

求解 BOE

前文介绍了求解贝尔曼公式的算法，是通过迭代的数值方法求解。这里介绍三种具体实现，分别是 value iteration（值迭代），**policy iteraion（策略迭代）**以及介于二者之间的 truncated iteration（截断迭代）。

这三种方法称为动态规划方法，都是 **model-based（基于模型）**的，与 model-free 不同。

value iteration

value iteration 借助 BOE 的压缩性质求解，其迭代公式为

$$v_{k+1}=\max_{\pi\in\Pi}(r_{\pi}+\gamma P_{\pi}v_{k}),\quad k=0,1,2,\dots$$

根据压缩映射定理，当 $k\to\infty$ 时 $v_{k}$ 和 $\pi_k$ 都会分别收敛到最优状态价值和最优策略。

迭代的过程具体而言，在一开始，会初始化一个 $v_0$，随后每轮的迭代过程分为两步，分别是 policy update 和 value update。

policy update

第一步是 policy update，目的是找到一个策略满足

$$\pi_{k+1}=\arg\max_{\pi}(r_{\pi}+\gamma P_{\pi}v_k)$$

其中 $v_k$ 是前一轮获得的结果。

目标方程的 element-wise 形式为

$$\pi_ {k + 1} (s) = \arg \max _ {\pi} \sum_ {a} \pi (a | s) \underbrace {\left(\sum_ {r} p (r | s , a) r + \gamma \sum_ {s ^ {\prime}} p \left(s ^ {\prime} | s , a\right) v _ {k} \left(s ^ {\prime}\right)\right)} _ {q _ {k} (s , a)}, \quad s \in \mathcal {S}.$$

根据之前“解的形式”部分可以知道，这里找的策略是在每个状态 $s$ 下采取 $q_{k}(s,a)$ 最大的动作，即

$$\pi_{k+1} ( a | s )=\left\{\begin{array} {c c} {1 ,} & {a=a_{k}^{*} ( s ) ,} \\ {0 ,} & {a \neq a_{k}^{*} ( s ) ,} \\ \end{array} \right.$$

其中 $a^*_k(s)=\arg\max_{a}q_k(s,a)$，若有多个最大 $q_{k}(s,a)$，任选一个动作即可。所以 policy update 的一开始要先利用 $v_k$ 计算出所有的 $q_{k}(s,a)$。

需要注意的是，每次迭代更新得到的 $\pi_{k+1}$ 不保证一定比 $\pi_k$ 更优。因为 value iteration 方法本质上是不动点迭代，收敛性由压缩映射保证，但策略的单调性不是其必要性质，它只是逐步逼近最优值函数，中间策略可能振荡。

value update

第二步是 value update，用于根据找到的新策略 $\pi_{k+1}$ 计算一个新的 $v_{k+1}$：

$$v_{k+1}=r_{\pi_{k+1}}+\gamma P_{\pi_{k+1}}v_k$$

得到的 $v_{k+1}$ 将用于下一轮迭代。

目标方程的 element-wise 形式为

$$v _ {k + 1} (s) = \sum_ {a} \pi_ {k + 1} (a | s) \underbrace {\left(\sum_ {r} p (r | s , a) r + \gamma \sum_ {s ^ {\prime}} p \left(s ^ {\prime} | s , a\right) v _ {k} \left(s ^ {\prime}\right)\right)} _ {q _ {k} (s , a)}, \quad s \in \mathcal {S}.$$

根据 $\pi_{k+1}$ 所采取的贪婪策略可知，

$$v_{k+1}(s)=\max_{a}q_{k}(s,a)$$

即上一轮中最大的 $q_{k}(s,a)$。

需要注意的是，在迭代过程中所有的 $v_{k}(s)$ 都不是 state value，因为它们并不满足贝尔曼公式，只是作为迭代过程中的中间值出现。相应地，所有 $q_{k}(s,a)$ 也都不能称作 action value。

如果 $v_{k}(s)$ 想成为 state value，应该在 value update 步骤中通过迭代的数值方法求出（而这事实上就是后面的 policy iteration 方法），而不是直接赋值。

总而言之，value iteration 的过程可以总结如下：

$$v_{k}(s)\rightarrow q_{k}(s,a)\rightarrow\text{new greedy policy }\pi_{k+1}(s)\rightarrow\text{new value }v_{k+1}(s)=\max_{a}q_{k}(s,a)$$

伪代码

policy iteration

policy iteration 事实上并没有直接求解 BOE，但是其与 value iteration 关系密切，且是强化学习中应用非常广泛的方法。当迭代次数 $k\to\infty$ 时，也会得到最优状态价值和最优策略。

policy iteration 首先初始化一个策略 $\pi_0$，随后每轮迭代过程也分为两步，分别是 policy evaluation 和 policy improvement。

policy evaluation

第一步要做 policy evaluation，即对当前策略 $\pi_k$ 进行评价，也就是要求出当前策略 $\pi_k$ 下的 state values。因此这一步就是解一个贝尔曼方程：

$$v_{\pi_k}=r_{\pi_k}+\gamma P_{\pi_k}v_{\pi_k}$$

其中 $\pi_k$ 是上一轮得到的策略。具体的求解方法既可以使用 closed-form 的解析解，也可以使用迭代的数值求解。

注意这里求的是精确的 $v_{\pi_k}$，如果用迭代求解需要迭代无穷次。所以 policy iteration 是理论上的方法，实际不可行。

policy improvement

第二步是 policy improvement，这一步和 value iteration 的 policy update 类似，也是选取当前的最优策略：

$$\pi_{k+1}=\arg\max_{\pi}(r_{\pi}+\gamma P_{\pi}v_{\pi_k})$$

最优策略的形式也是类似的贪婪策略，不再赘述。

不同于 value iteration 的 policy update，policy iteration 的 policy improvement 能够保证 $\pi_{k+1}$ 一定比 $\pi_{\pi}$ 更优。而这实际上也是 policy iteration 能够比 value iteration 更快收敛的原因之一。

证明 $\pi_{k+1}\ge\pi_{k}$：

由于 $v_{k+1}$ 和 $v_{k}$ 都是 state values，因此它们满足

$$\begin{align} v_{\pi_{k}}&=r_{\pi_{k}}+\gamma P_{\pi_{k}}v_{\pi_k}\\ v_{\pi_{k+1}}&=r_{\pi_{k+1}}+\gamma P_{\pi_{k+1}}v_{\pi_{k+1}} \end{align}$$

由于

$$\pi_{k+1}=\arg\max_{\pi}(r_{\pi}+\gamma P_{\pi}v_{\pi_k})$$

因此

$$r_{\pi_k}+\gamma P_{\pi_k}v_{\pi_k}\le r_{\pi_{k+1}}+\gamma P_{\pi_{k+1}}v_{\pi_k}$$

其中 $\le$ 是逐元素意义上的。于是

$$\begin{align} v_{\pi_{k+1}}-v_{\pi_k}&=r_{\pi_{k+1}}+\gamma P_{\pi_{k+1}}v_{\pi_{k+1}}-(r_{\pi_{k}}+\gamma P_{\pi_{k}}v_{\pi_k})\\ &\ge r_{\pi_{k+1}}+\gamma P_{\pi_{k+1}}v_{\pi_{k+1}}-(r_{\pi_{k+1}}+\gamma P_{\pi_{k+1}}v_{\pi_k})\\ &=\gamma P_{\pi_{k+1}}(v_{\pi_{k+1}}-v_{\pi_k}) \end{align}$$

其中 $\ge$ 是逐元素意义上的。由此可得

$$v_{\pi_{k+1}}-v_{\pi_k}\ge \gamma P_{\pi_{k+1}}(v_{\pi_{k+1}}-v_{\pi_k})\ge\gamma^2 P_{\pi_{k+1}}^2(v_{\pi_{k+1}}-v_{\pi_k})\ge\cdots\ge\gamma^n P_{\pi_{k+1}}^n(v_{\pi_{k+1}}-v_{\pi_k})$$

其中 $\gamma\in(0,1)$，$P_{\pi_{k+1}}$ 每个元素均非负且不超过 $1$。

因此

$$v_{\pi_{k+1}}-v_{\pi_k}\ge\lim_{n\to\infty}\gamma^n P_{\pi_{k+1}}^n(v_{\pi_{k+1}}-v_{\pi_k})=0$$

即对于任意的 $k$，都有 $v_{\pi_{k+1}}\ge v_{\pi_k}$，所以 $\pi_{k+1}$ 优于 $\pi_k$。

算法证明

事实上，policy iteration 并没有在直接求解 BOE，因为 policy evaluation 是在计算给定策略 $\pi_{k}$ 下的状态价值，而不是像 value iteration 的 value update 那样利用 BOE 的迭代公式去更新值。因此需要证明 policy iteration 的解能够收敛，且收敛到最优策略与最优状态价值。事实上，policy iteration 相比于 value iteration 能够更快地收敛到最优策略与最优状态价值。

假设 policy iteration 得到的策略序列为 $\{\pi_0,\pi_1,\dots,\pi_k,\dots\}$，state values 序列为 $\{v_{\pi_0},v_{\pi_1},\dots,v_{\pi_k},\dots\}$。设 $v^*$ 为最优状态价值，则根据 policy iteration 每轮迭代的单调性（$\pi_{k+1}$ 一定优于 $\pi_k$）可知

$$v_{\pi_0}\le v_{\pi_1}\le v_{\pi_2}\le\cdots\le v_{\pi_k}\le\cdots\le v^*$$

根据单调有界定理可知数列 $\{v_{\pi_k}\}_{k=0}^{\infty}$ 会收敛到一个常数向量 $v_{\infty}$，而 $v_{\infty}$ 就是 $v^*$。因此 $\{\pi_k\}_{k=0}^{\infty}$ 也会收敛到最优策略。

证明 $\{v_{\pi_k}\}_{k=0}^{\infty}$ 和 $\{\pi_k\}_{k=0}^{\infty}$ 分别收敛到最优状态价值和最优策略：

思路是在 value iteration 解的最优性基础上，使用数学归纳法，证明 $\{v_{\pi_k}\}_{k=0}^{\infty}$ 收敛更快。

设 value iteration 得到的值序列为 $\{v_{k}\}_{k=0}^{\infty}$，其由

$$v_{k+1}=f(v_k)=\max_{\pi}(r_{\pi}+\gamma P_{\pi}v_k)$$

产生，其中 $f$ 是贝尔曼最优算子。已知 $\{v_{k}\}_{k=0}^{\infty}$ 收敛到 $v^*$ 对于任意初始值 $v_0$。

当 $k=0$ 时，对于任意初始策略 $\pi_0$，始终可以找到初始值 $v_0$ 满足 $v_{\pi_0}\ge v_0$。

假设对任意 $k\ge 0$，都有 $v_{\pi_k}\ge v_{k}$。

则当 $k+1$ 时，有

$$\begin{align} v_{\pi_{k+1}}-v_{k+1}&=r_{\pi_{k+1}}+\gamma P_{\pi_{k+1}}v_{\pi_{k+1}}-\max_{\pi}(r_{\pi}+\gamma P_{\pi}v_{k})\\ &=r_{\pi_{k+1}}+\gamma P_{\pi_{k+1}}v_{\pi_{k+1}}-(r_{\pi_{k+1}'}+\gamma P_{\pi_{k+1}'}v_k)\\ &\ge r_{\pi_{k+1}}+\gamma P_{\pi_{k+1}}v_{\pi_k}-(r_{\pi_{k+1}'}+\gamma P_{\pi_{k+1}'}v_k)& (\text{根据 $\{v_{\pi_k}\}_{k=0}^{\infty}$ 的单调性以及 $P_{\pi_{k+1}}$ 的非负性})\\ &\ge r_{\pi_{k+1}'}+\gamma P_{\pi_{k+1}'}v_{\pi_k}-(r_{\pi_{k+1}'}+\gamma P_{\pi_{k+1}'}v_k)& (\text{根据 $\pi_{k+1}=\max_{\pi}(r_{\pi}+\gamma P_{\pi})v_{\pi_k}$})\\ &=\gamma P_{\pi_{k+1}'}(v_{\pi_k}-v_k)\\ &\ge 0 &(\text{根据归纳假设 $v_{\pi_k}\ge v_k$ 以及 $P_{\pi_{k+1}'}$ 的非负性}) \end{align}$$

因此 $v_{\pi_k}\ge v_k$ 对于任意的 $k\ge 0$ 都成立。

由于 $\{v_{k}\}_{k=0}^{\infty}$ 收敛到 $v^*$，因此 $\{v_{\pi_k}\}_{k=0}^{\infty}$ 会更快地收敛到 $v^*$。证毕。

伪代码

truncated iteration

对比 policy iteration 和 value iteration，可以发现二者非常的相似：

$$\begin{align} \text{Policy iteration: }\pi_{0}\xrightarrow{PE} v_{\pi_{0}}&\xrightarrow{PI}\pi_{1}\xrightarrow{PE}v_{\pi_{1}}\xrightarrow{PI}\pi_{2}\xrightarrow{PE}v_{\pi_{2}}\xrightarrow{PI}\dots\\ \text{Value iteration: }\qquad\qquad v_{0}&\xrightarrow{PU}\pi_{1}^{\prime}\xrightarrow{VU}v_{1}\xrightarrow{PU}\pi_{2}^{\prime}\xrightarrow{VU}v_{2}\xrightarrow{PU}\dots \end{align}$$

在策略改进这一步，二者的做法是一样的，都是计算所有的 $q(s,a)$ 值，然后使用贪婪策略选取值最大的动作。

但是在更新值这一步，policy iteration 通过迭代的数值方法求出精确的 $v$ 值，而 value iteration 直接赋值。事实上， value iteration 的值更新可以看成是一轮迭代，而 policy iteration 是无穷轮迭代。因此介于二者中间的方法，也就是进行有限步的 $n$ 轮迭代，就是 truncated iteration（截断迭代）。下面这张图非常直观地展示了三者的区别。

因此，policy iteration 和 value iteration 可以看成是 truncated iteration 的两个极端。前面说过 policy iteration 的 policy evaluation 需要迭代无穷轮，这仅在理论上可行，实际上会采用有限步的 truncated iteration，当 $\left\|v_{\pi_{k+1}}-v_{\pi_k}\right\|$ 小于设定的阈值或迭代到设定轮数时就停止。

下图是三个算法收敛速度的对比：

truncated iteration 实际上属于 generalized policy iteration（广义策略迭代）。

原始的经典策略迭代算法要求：先完全、精确地完成策略评估，然后立即、确定地进行策略改进。

而广义策略迭代将这个要求放宽了，它指的是：

• 评估和改进不必完成：策略评估不需要做到100%精确（比如只评估几步就停止），策略改进也不一定立刻让策略变成确定性的贪婪策略。
• 两者可以交错进行：评估一步，改进一步；或者评估多步，改进一步。
• 两者相互依赖、共同进步：评估的质量为改进提供方向，而改进后的新策略又成为下一次评估的对象。两者朝着共同的目标——最优策略——不断收敛。

直觉上来说，truncated iteration 在值更新这一步采取的迭代轮数介于 value iteration 和 policy iteration，也就是 $v$ 的估计会更加精确，所以会收敛更快，但是又不如 policy iteration。那么，是否迭代次数越多，就一定收敛越快呢？或者说，如何从数学上严谨证明，多轮迭代得到的更新值就一定比一轮迭代的好？

考虑下面的迭代式

$$v_{\pi_k}^{(j+1)}=r_{\pi_k}+\gamma P_{\pi_k}v_{\pi_k}^{(j)},\quad j=0,1,2,\dots$$

若初始值 $v_{\pi}^{(0)}=v_{\pi_{k-1}}$，也就是从上轮获得的值开始迭代，那么对于任意的 $j=0,1,2,\dots$ 都有

$$v_{\pi_k}^{(j+1)}\ge v_{\pi}^{(j)}$$

其中 $\ge$ 是逐元素意义上的。

证明：

根据迭代式，有

$$v_{\pi_{k}}^{(j+1)}-v_{\pi_k}^{(j)}=\gamma P_{\pi_k}(v_{\pi_{k}}^{(j)}-v_{\pi_k}^{(j-1)})=\cdots=\gamma^j P_{\pi_k}^j(v_{\pi_{k}}^{(1)}-v_{\pi_k}^{(0)})$$

因为

$$v_{\pi_k}^{(1)}=r_{\pi_k}+\gamma P_{\pi_k}v_{\pi_k}^{(0)}=r_{\pi_k}+\gamma P_{\pi_k}v_{\pi_{k-1}}\ge r_{\pi_{k-1}}+\gamma P_{\pi_{k-1}}v_{\pi_{k-1}}=v_{\pi_{k-1}}=v_{\pi_k}^{(0)}$$

其中不等式是由于 $\pi_{k}=\arg\max_{\pi}(r_{\pi}+\gamma P_{\pi}v_{\pi_{k-1}})$。因此，再加上 $P_{\pi_k}$ 和 $\gamma$ 的非负性就有 $v_{\pi_k}^{(j+1)}\ge v_{\pi}^{(j)}$。证毕。

由此可见，每多一轮迭代，$v_{\pi_k}^{(j)}$ 都会更优。

伪代码