强化学习——值和策略迭代（四）

值和策略迭代算法

1 值迭代算法（value iteration algorithm）

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

1.1 策略更新（policy update）

为了得出最优的策略通过
$\pi_{k+1}= \displaystyle \argmax_\pi(r_\pi + \gamma P_\pi v_k)$(matrix form)
或者
$\pi_{k+1}= \displaystyle \argmax_\pi \sum_a \pi(a|s) \underbrace{\left[\displaystyle \sum_r p(r|s,a) r+\gamma \displaystyle \displaystyle \sum_{s'} p(s'|s,a)v_k(s') \right]}_{q_k(s,a)}$(elementwise form)
即

$$\pi_{k+1}(a|s)=\begin{cases} 1, & a = a_k^*= \displaystyle \argmax_a q_k(s,a)\\ 0, & a \neq a_k^* \end{cases}$$

1.2 值更新（value update）

$v_{k+1}= r_{\pi_{k+1}} + \gamma P_{\pi_{k+1}} v_k$(matrix form)
或者
$v_{k+1}= \displaystyle \sum_a \pi(a|s) \underbrace{\left[\displaystyle \sum_r p(r|s,a) r+\gamma \displaystyle \displaystyle \sum_{s'} p(s'|s,a)v_k(s') \right]}_{q_k(s,a)}$(elementwise form)
由于$\pi(a|s)=1$，而且是在$a=a_k^*= \displaystyle \argmax_a q_k(s,a)$取得。可以简化成$v_{k+1}=\max q_k(s,a)$。

1.3 整体步骤

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

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)}= \displaystyle \sum_a \pi(a|s) \underbrace{\left[\displaystyle \sum_r p(r|s,a) r+\gamma \displaystyle \displaystyle \sum_{s'} p(s'|s,a)v_{\pi_{k}}^{(j)}(s') \right]}_{q_{\pi_{k}}^{(j)}(s,a)}$(elementwise form)
现实中往往无法无线迭代，所以当$\Vert v_{\pi_k}^{(j+1)}-v_{\pi_{k+1}}^{(j)} \Vert < \epsilon$停止迭代。

2.2 策略优化（policy improvement）

$\pi_{\pi_{k+1}}= \displaystyle \argmax_\pi(r_{\pi} + \gamma P_{\pi} v_{\pi_{k}})$(matrix form)
或者
$\pi_{\pi_{k+1}}= \displaystyle \argmax_\pi \sum_a \pi(a|s) \underbrace{\left[\displaystyle \sum_r p(r|s,a) r+\gamma \displaystyle \displaystyle \sum_{s'} p(s'|s,a)v_{\pi_{k}}(s') \right]}_{q_{\pi_{k}}(s,a)}$(elementwise form)
即

$$\pi_{k+1}(a|s)=\begin{cases} 1, & a = a_{\pi_{k}}^*= \displaystyle \argmax_a q_{\pi_{k}}(s,a)\\ 0, & a \neq a_{\pi_{k}}^* \end{cases}$$

2.3 整体步骤

初始条件：$p(s'|s,a),p(r|s,a),\gamma$，以及随机初始化的$\pi_0,v_{\pi_0}^{(0)}$。
迭代过程：$v_{\pi_k}^{(\infty)} \rightarrow \pi_{k+1} \rightarrow v_{\pi_{k+1}}^{(\infty)}$
终止条件：$\Vert v_{\pi_k}^{(\infty)}-v_{\pi_{k+1}}^{(\infty)} \Vert < \epsilon$

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$的特殊情况。