1. 前言
在强化学习-MDP(马尔可夫决策过程)算法原理中我们已经介绍了强化学习中的基石--MDP，本文的任务是介绍如何通过价值函数，去寻找到最优策略，使得最后得到的奖励尽可能的多。
2. 回顾MDP
通过学习MDP我们得到了2个Bellman公式：
- 状态值函数：
- 状态-行动值函数：
和2个(v_{pi}(s_t),q_{pi}(s_t,a_t))之间的推导关系。
3. 策略迭代法
我们发现如果想知道最优的策略，就需要能够准确估计值函数。然而想准确估计值函数，又需要知道最优策略，数字才能够估计准确。所以实际上这是一个“鸡生蛋还是蛋生鸡”的问题。
所以策略迭代法通过迭代的方式，去不断的靠近最优策略。
策略迭代法的思路：
- 以某种策略(pi)开始，计算当前策略下的值函数(v_{pi}(s))。
- 利用这个值函数，更新策略，得到(pi*)。
- 再用这个策略(pi*)继续前行，更新值函数，得到(v'_{pi}(s))，一直到(v_{pi}(s))不在发生变化。
如何计算当前的状态值函数(v^T_{pi}(s))呢？比较正常的思路是通过上一次的迭代的(v^{T-1}_{pi}(s))，来计算当前这一轮迭代的值函数(v^T_{pi}(s))。那我们结合下之前的状态值函数的Bellman公式，我们就能写出策略迭代中，计算当前状态值函数的公式了。
公式中的T代表迭代的轮数，有了这个公式，我们计算出了当前的(v^T_{pi}(s))，然后如何去更新策略(pi*)呢？
其实也比较简单，需要两个步骤：
- 计算当前的状态-动作值函数：
- 通过当前的状态-动作值函数，找出比较好的策略序列：
到这里策略迭代的基本过程在逻辑上已经走通了，这里其实还有一个概念，在策略迭代的算法中，其实大家把整个过程分为两个大的步骤。
- 计算当前的状态值函数的过程，即公式(1)称为--策略评估(policy evaluation)
- 计算最优策略的过程，即公式(2)(3)称为--策略提升(policy improvement)
3.1 策略评估步骤
- 输入：策略(pi^{T-1})，状态转移概率(p(s_{t+1}|s_t,a_t))，奖励(r)，衰减因子(gamma)，值函数(v^{T-1}(s))
- (v_{0}(s) = v^{T-1}(s))
- (Repeat;;k=0,1...)
- (for;;every;;s;;do)
- (v_{k+1}(s_t)=sum_{a_t}pi^{T-1}(a_t|s_t)sum_{s_{t+1}}p(s_{t+1}|s_t,a_t)[r_{a_t}^{s_{t+1}} + gamma * v_{k}(s_{t+1})])
- (Until;;v_{k+1}(s) = v_{k}(s))
- 输出(v^{T}(s)=v_{k+1}(s))
3.2 策略迭代步骤
- 输入：策略(pi_{0})，状态转移概率(p(s_{t+1}|s_t,a_t))，奖励(r)，衰减因子(gamma)，值函数(v_{0}(s))
- (Repeat;;k=0,1...)
- (policy;;evaluation)
- (q_{k}(s_t,a_t)=sum_{s_{t+1}}p(s_{t+1}|s_t,a_t)[r_{a_t}^{s_{t+1}} + gamma * v_{k}(s_{t+1})])
- (pi_{k+1}(s) = argmax_aq_{k}(s,a))
- (Until;;pi_{k+1}(s) = pi_{k}(s))
- 输出(pi^{*}(s)=pi_{k+1}(s))
3.3 策略迭代图形化展示
其中横轴X表示值函数的收敛效果，数值到达∞时完成收敛，纵轴Y表示策略的优异度，数值到达∞时策略到达最优。每一次迭代的过程，首先达到值函数的收敛，再提升一些策略的优异度。
从图中也可以看出，策略评估在横轴X反向上的截距比较长，所以它花费的时间比较多，策略提升是在纵轴Y上的截距，所以花费的时间比较短。
4. 总结
策略迭代的思想比较简单，先策略评估，再策略提升，直到策略不再变化为止。
但是策略迭代有点缺点，策略迭代的主要时间都花费在策略评估上，对一个简单的问题来说，在策略评估上花费的时间不算长；但对复杂的问题来说，这个步骤的时间实在有些长。一个最直接的想法就是，我们能不能缩短在策略评估上花的时间呢？有，就是价值迭代，我们下一篇要讲解的内容。