截断策略迭代算法

Truncated policy iteration algorithm

值迭代算法（value iteration algorithm）

算法的矩阵形式如下：

$$v_{k+1}=\underset{\pi }{max}(r_{\pi }+\gamma {\mathbf{P}}_{\pi }{v}_k)$$

• 策略更新（policy update，PU）

  给定 $v_k$，求解 $\pi$ 可以得到：

  $${\pi }_{k+1}={\text{argmax}}_{\pi }(r_{\pi }+\gamma {\mathbf{P}}_{\pi }{v}_k)$$

• 价值更新（value update，VU）

  代入第一个式子，有：

  $$v_{k+1}=r_{{\pi }_{k+1}}+\gamma {\mathbf{P}}_{{\pi }_{k+1}}{v}_k$$

算法的元素形式如下：

• 策略更新：

  $${\pi }_{k+1}=\underset{\pi }{\text{argmax}}\sum _a\pi (a\mid s)[\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)v_k\left(s^{\prime }\right)],\mathrm{\forall }s\in \mathcal{S}$$

  对应的最优策略为：

  $${\pi }_{k+1}(a\mid s)=\{\begin{array}{ll}1& a=a_k^{\ast }(s)\\ 0& a\ne a_k^{\ast }(s)\end{array}$$$$a_k^{\ast }(s)={\text{argmax}}_a{q}_k^{\ast }(s,a)$$

  注意：$v^{\ast }$ 唯一，但最优策略不一定唯一。

• 价值更新：

  $$v_{k+1}(s)=\sum _a{\pi }_{k+1}(a\mid s)[\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)v_k\left(s^{\prime }\right)],\mathrm{\forall }s\in \mathcal{S}$$

  代入 ${\pi }_{k+1}$：

  $$v_{k+1}(s)=\underset{a}{max}{q}_k(a,s)$$

策略迭代算法（policy iteration algorithm）

给定随机初始策略 ${\pi }_0$：

• 策略评估（policy evaluation，PE）

$$v_{{\pi }_k}=r_{{\pi }_k}+\gamma {\mathbf{P}}_{{\pi }_k}{v}_{{\pi }_k}$$

求解

在贝尔曼公式中介绍了其求解：

直接求解：

$$v_{\pi }={(I-\gamma P_{\pi })}^{-1}{r}_{\pi }$$

采用迭代法：

$$v_{k+1}=r_{\pi }+\gamma {\mathbf{P}}_{\pi }{v}_k$$

有：

$$v_k\to v_{\pi }={(I-\gamma P_{\pi })}^{-1}{r}_{\pi },k\to \mathrm{\infty }$$

• 策略改进（policy improvement，PI）

$${\pi }_{k+1}={\text{argmax}}_{\pi }(r_{\pi }+\gamma {\mathbf{P}}_{\pi }{v}_{{\pi }_k})$$

算法的元素形式如下：

• 策略评估

  $$v_{{\pi }_k}^{(j+1)}=\sum _a{\pi }_k(a\mid s)[\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)v_{{\pi }_k}^{(j)}\left(s^{\prime }\right)],\mathrm{\forall }s\in \mathcal{S}$$

• 策略改进

  $${\pi }_{k+1}(s)=\underset{\pi }{\text{argmax}}\sum _a\pi (a\mid s)[\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)v_{{\pi }_k}\left(s^{\prime }\right)],\mathrm{\forall }s\in \mathcal{S}$$

  对应的最优策略为：

  $${\pi }_{k+1}(a\mid s)=\{\begin{array}{ll}1& a=a_k^{\ast }(s)\\ 0& a\ne a_k^{\ast }(s)\end{array}$$$$a_k^{\ast }(s)={\text{argmax}}_a{q}_{{\pi }_k}^{\ast }(s,a)$$

值迭代与策略迭代的区别：

过程比较：

步骤	值迭代算法	策略迭代算法	说明
Policy	${\pi }_0$	-	策略迭代给出初始策略
Value	$v_{{\pi }_0}=r_{{\pi }_0}+\gamma {\mathbf{P}}_{{\pi }_0}{v}_{{\pi }_0}$	$v_0=v_{{\pi }_0}$	值迭代给出初始值 $v_0$，策略迭代的 $v_{{\pi }_0}$ 需要求解
Policy	${\pi }_1={\text{argmax}}_{\pi }(r_{\pi }+\gamma {\mathbf{P}}_{\pi }{v}_{{\pi }_0})$	${\pi }_1={\text{argmax}}_{\pi }(r_{\pi }+\gamma {\mathbf{P}}_{\pi }{v}_0)$	相同
Value	$v_{{\pi }_1}=r_{{\pi }_1}+\gamma {\mathbf{P}}_{{\pi }_1}{v}_{{\pi }_1}$	$v_{{\pi }_1}=r_{{\pi }_1}+\gamma {\mathbf{P}}_{{\pi }_1}{v}_0$	策略迭代每一步得到 $v$ 是真实的
Policy	${\pi }_2={\text{argmax}}_{\pi }(r_{\pi }+\gamma {\mathbf{P}}_{\pi }{v}_{{\pi }_1})$	${\pi }_2={\text{argmax}}_{\pi }(r_{\pi }+\gamma {\mathbf{P}}_{\pi }{v}_1)$
$\cdots$	$\cdots$	$\cdots$	$\cdots$

截断策略迭代算法

在计算 $v_{{\pi }_k}$ 时，值迭代算法只用计算一次就可以得到结果，而策略迭代算法需要计算无穷次，在实际中并不存在，那么自然能想到只计算 $j$ 次，使用 $v_{{\pi }_k}^{(j)}$ 作为值代入下一步的策略计算，从第 $j$ 步到第 $\mathrm{\infty }$ 步都被截断了，由此得到截断策略迭代算法。

截断策略迭代算法是值迭代算法与策略迭代算法的一般形式，当 $j=1$ 时为值迭代算法，当 $j=\mathrm{\infty }$ 时为策略迭代算法。