[RL Note] 策略迭代

  在前文中提到,由策略改进定理,对于给定策略 $\pi$,在每一个状态都根据价值函数 $v\pi$ 贪心的选择动作,就可以得到一个更优的策略 $\pi’$

\begin{align}
\pi'(s) \doteq \underset{a}{\arg\max} \; \sum_{s’, r} p(s’, r | s, a) \big[ r + \gamma v_\pi(s’) \big] \tag{1}
\end{align}

然后计算 $\pi’$ 的价值函数 $v_{\pi’}$,通过相同的方式就可以找到一个新的更优的策略 $\pi”$。不断地对价值函数进行评估(evaluation),并对策略进行改进(improvement),得到一个不断改进的策略和价值函数序列

\begin{equation}
\pi_0 \overset{\mathrm{E}}{\rightarrow} v_{\pi_0} \overset{\mathrm{I}}{\rightarrow} \pi_1 \overset{\mathrm{E}}{\rightarrow} v_{\pi_1} \overset{\mathrm{I}}{\rightarrow} \pi_2 \overset{\mathrm{E}}{\rightarrow} \cdots \overset{\mathrm{I}}{\rightarrow} \pi_* \overset{\mathrm{E}}{\rightarrow} v_{\pi_*}
\end{equation}

在上面的序列中,每一个策略都严格优于上一个策略,除非上一个策略已经最优。有限 MDP 只有有限种策略,故在有限次迭代后,上面的序列一定收敛到一个最优策略和最优价值函数。

  上面这种寻找最优策略的方法称为策略迭代,其完整版本如下所示。


策略迭代(使用迭代策略评估),用于估计 $\pi \approx \pi_*$

  1. 初始化
    对 $s \in \mathcal{S}$,任意设定 $V(s) \in \mathbb{R}$ 以及 $\pi(s) \in \mathcal{A}(s)$

  2. 策略评估
    循环:
      $\Delta \leftarrow 0$
      对每一个 $s \in \mathcal{S}$ 循环:
         $v \leftarrow V(s)$
         $V(s) \leftarrow \sum\limits_{s’, r}p(s’,r|s, \pi(s))\big[r + \gamma V(s’)\big]$
         $\Delta \leftarrow \max(\Delta, |v – V(s)|)$
      直到 $\Delta < \theta$(一个决定估计精度的小正数)

  3. 策略改进
      $policy \text{-} stable \leftarrow true$
      对每一个 $s \in \mathcal{S}$:
        $old\text{-}action \leftarrow \pi(s)$
        $\pi(s) \leftarrow \underset{a}{\arg\max} \sum\limits_{s’, r}p(s’,r|s, a)\big[r + \gamma V(s’)\big]$
        如果 $old\text{-}action \neq \pi(s)$,那么 $policy\text{-}stable \leftarrow false$
      如果 $policy\text{-}stable$ 为 $true$,那么停止并返回 $V \approx v_*$ 以及 $\pi \approx \pi_*$;否则跳转到 2。