Value Iteration vs Policy Iteration

策略迭代 Policy Iteration

• 策略迭代包括策略评估(Policy Evaluation)和策略改进(Policy Improvement)两个步骤，通过二者的交替迭代来求解MDP。
  • 策略评估
    • 给定一个Policy，通过动态规划求价值函数: $$\begin{equation*} \begin{split} V_{t+1}(s) &= \sum\limits_{a\in A}\pi(a|s)\Big(R(s,a) + \gamma \sum\limits_{s^\prime \in S}p(s^\prime|s,a)V_t(s^\prime)\Big)\\ &= R(s) + \gamma \sum\limits_{s^\prime \in S}p(s^\prime|s)V_t(s^\prime) \end{split} \end{equation*}$$

      给定了策略，所以在某个状态选择哪个Action已经给定，概率为1，因而可以将式子中的a去掉。

  • 策略改进
    • 通过策略评估所获得的奖励函数和状态转移函数计算Q函数： $$Q_{\pi_i}(s,a) = \sum\limits_{s^\prime \in S}p(s^\prime|s,a)\Big(R(s^\prime,s,a) + \gamma V_{\pi_i}(s^\prime)\Big)$$
    • 改进策略：采用贪心的策略，每个状态选择Q-value最大的那个动作，即 $$\pi_{i+1}(s) = arg \max\limits_{a}Q_{\pi_i}(s,a)$$
  • 策略评估和策略改进交替迭代，最终价值函数和策略将会收敛，此时有： $$Q_\pi(s,\pi^\prime(s)) = \max\limits_{a \in A}Q_\pi(s,a) = Q_\pi(s,\pi(s)) = V_\pi(s)$$ 即 $$\pi^*(s) = arg \max\limits_{a}\sum\limits_{s^\prime \in S}(r + \gamma V_{\pi_i}(s^\prime))$$

    上式也称为贝尔曼最优方程，记为$V_\pi(s) = \max\limits_{a\in A}Q_\pi(s,a)$

值迭代 Value Iteration

• 为了缩短策略迭代过程中策略评估的时间，可将值迭代理解为策略迭代的改进版本；
• 策略迭代每次需要值函数完全收敛的情况下才进行策略更新，将对策略评估的要求放低，以此提升迭代速度；
• 改进方法：使用贝尔曼方程，将策略改进视为价值改进，让策略函数与价值函数同时收敛，每一步求取最大的值函数，具体迭代公式如下： $$V_{k+1}(s) = \max\limits_{a \in A}(R_s^a + \gamma\sum\limits_{s^\prime \in S}P(s^\prime|s,a)V_k(s^\prime))$$

对当前状态s，对每一个可能的动作a都计算才去这个动作后下一个状态的期望值，将最大的期望值作为当前状态的价值函数，直到收敛；
与策略迭代相比，没有等到状态价值函数收敛再更新策略，而是根据贪心法寻找最优价值函数，值迭代的过程不会对应任何明确的策略；
值迭代是根据状态期望值选择动作，而策略迭代是先估计状态值，再更新策略；