首页摘要：
动态规划算法主要包括策略评估、策略改进，其中策略评估是为了确定某个策略下对应的各个状态值函数或者是状态动作值函数，而策略改进则是根据确定的状态值函数或者状态动作函数找到最优策略。
最优值函数
要解决强化学习问题就意味着智能体在与环境交互的过程中找到一个能够获得最大回报的策略，假设这个最优策略是 $ \pi^{\star} $，但是实际上是很难找到最优的策略的。一般而言，我们可以在多个策略中选择最好的那个策略，这个策略被当成最优策略，也就是说我们找到的是局部最优解。此时对应的状态价值函数也是最大的，即：
同样地，状态动作价值函数也可以被推出：
那么这个最优策略可以定义成：
这句话的意思是只有在最大状态动作价值函数的时候对应的动作概率为1，其他动作概率为0，这是一种贪婪策略。也就是说状态价值函数在最优的贪婪策略下可以改写成：
进一步，状态动作价值函数的关系式也可以被推出：
综上所述，最优状态价值函数和状态动作价值函数可以被总结成：
动态规划基本流程
由于动态规划的模型是已知的，也就是说 $P_{ss’}^{a}$ 是已知的，因此可以直接采用贪婪寻优策略的方法来求解，这一点要和后面的蒙特卡洛模拟采取的 $\epsilon -greedy$ 策略加以区别。因为markdown里面好像不支持latex的算法描述流程，直接用书中的图来介绍吧。最麻烦也是最先出现的就是策略迭代法，图片中公式略有区别，但是意思是一样的，其中 $p(s’,r|s,\pi (s))$ 是 $\pi (s)$ 执行不同的动作 $a$ 转到状态 $s’$ 具有不同的回报 $r$ 的概率，因此可以累积求和，如下所示：
大致过程是：
（1）随机初始化策略；
（2）估计在该策略下评估每个状态价值及状态动作价值；
（3）估计完价值后，针对每个状态更新策略。
循环（2）-（3），直到策略稳定收敛。
但是值得注意的是，策略评估和策略改进解耦了，也就是所谓的离线策略( $offline-policy$ )这样做会导致计算量非常大，因此有人提出了改进算法，把这两部融合起来了，这就是值迭代过程，称之为在线策略( $online-policy$ )，具体流程如下：
虽然起初通过 $max$ 更新的最优策略下的估值是基于不完整的状态信息的，但每个状态总是有一个最优操作的。那么通过不断地迭代更新，总是有机会能先找到某个状态下的最优操作，保证其足够平稳（即该状态下的操作不会随着迭代经常变）。然后就能以点破面，找到更多周边的平稳的最优估值。久而久之，平稳的状态会越来越多，最后也就能找到最优策略了。
