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

wizard-黑影

649人浏览 · 2025-03-04 15:32:32

wizard-黑影 · 2025-03-04 15:32:32 发布

值和策略迭代算法

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