值和策略迭代算法

1 值迭代算法（value iteration algorithm）

根据贝尔曼最优公式就能得出最优的 state value 和最优的 policy。

1.1 策略更新（policy update）

为了得出最优的策略通过
${\pi }_{k+1}=\underset{\pi }{\mathrm{argmax}}(r_{\pi }+\gamma P_{\pi }{v}_k)$(matrix form)
或者
${\pi }_{k+1}=\underset{\pi }{\mathrm{argmax}}\sum _a\pi (a|s)\underset{q_k(s,a)}{\underbrace{\left[\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_k(s^{\prime })\right]}}$(elementwise form)
即
$${\pi }_{k+1}(a|s)=\{\begin{array}{ll}1,& a=a_k^{\ast }=\underset{a}{\mathrm{argmax}}{q}_k(s,a)\\ 0,& a\ne a_k^{\ast }\end{array}$$

1.2 值更新（value update）

$v_{k+1}=r_{{\pi }_{k+1}}+\gamma P_{{\pi }_{k+1}}{v}_k$(matrix form)
或者
$v_{k+1}=\sum _a\pi (a|s)\underset{q_k(s,a)}{\underbrace{\left[\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_k(s^{\prime })\right]}}$(elementwise form)
由于$\pi (a|s)=1$，而且是在$a=a_k^{\ast }=\underset{a}{\mathrm{argmax}}{q}_k(s,a)$取得。可以简化成$v_{k+1}=\max q_k(s,a)$。

1.3 整体步骤

初始条件：$p(s^{\prime }|s,a),p(r|s,a),\gamma$，以及随机初始化的$v_0$。
迭代过程：$v_k\to q_k\to {\pi }_{k+1}\to v_{k+1}$
终止条件：$\Vert v_{k+1}-v_k\Vert <ϵ$

2 策略迭代算法（policy iteration algorithm）

2.1 策略评估（policy evaluation）

通过贝尔曼公式的迭代解求出当前策略下最优的 state value。该步骤是需要不断迭代的。
$v_{{\pi }_k}^{(j+1)}=r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k}^{(j)}$(matrix form)
或者
$v_{{\pi }_k}^{(j+1)}=\sum _a\pi (a|s)\underset{q_{{\pi }_k}^{(j)}(s,a)}{\underbrace{\left[\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{{\pi }_k}^{(j)}(s^{\prime })\right]}}$(elementwise form)
现实中往往无法无线迭代，所以当$\Vert v_{{\pi }_k}^{(j+1)}-v_{{\pi }_{k+1}}^{(j)}\Vert <ϵ$停止迭代。

2.2 策略优化（policy improvement）

${\pi }_{{\pi }_{k+1}}=\underset{\pi }{\mathrm{argmax}}(r_{\pi }+\gamma P_{\pi }{v}_{{\pi }_k})$(matrix form)
或者
${\pi }_{{\pi }_{k+1}}=\underset{\pi }{\mathrm{argmax}}\sum _a\pi (a|s)\underset{q_{{\pi }_k}(s,a)}{\underbrace{\left[\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{{\pi }_k}(s^{\prime })\right]}}$(elementwise form)
即
$${\pi }_{k+1}(a|s)=\{\begin{array}{ll}1,& a=a_{{\pi }_k}^{\ast }=\underset{a}{\mathrm{argmax}}{q}_{{\pi }_k}(s,a)\\ 0,& a\ne a_{{\pi }_k}^{\ast }\end{array}$$

2.3 整体步骤

初始条件：$p(s^{\prime }|s,a),p(r|s,a),\gamma$，以及随机初始化的${\pi }_0,v_{{\pi }_0}^{(0)}$。
迭代过程：$v_{{\pi }_k}^{(\infty )}\to {\pi }_{k+1}\to v_{{\pi }_{k+1}}^{(\infty )}$
终止条件：$\Vert v_{{\pi }_k}^{(\infty )}-v_{{\pi }_{k+1}}^{(\infty )}\Vert <ϵ$

3 中断策略迭代（truncated policy iteration）

观察 policy iteration 发现，在 policy evaluation 过程中无法取得$v_{{\pi }_k}^{(\infty )}$，而当每次的迭代次数都设置为固定值$j_{truncated}$，称为 truncated policy iteration。而 value iteration 和 policy iteration 算法分别是该算法$j_{truncated}=1$和$j_{truncated}=\infty$的特殊情况。

4 代码链接

GitHub