递推表达式

通过之前的定义可以得到一个递推版本的DP状态转移方程：

这里的 代表的是 步，具体的含义是可以通过 次 action 到达这个状态。
所以上面的更新就是从 步的价值函数去更新 步的价值函数
这里的并不是Bellman 方程，只是递推表达式，算法要求是到最后接近满足Bellman方程

注意，这里的更新是和策略 有关的，是在策略确定的情况下，通过更新的方式来确定真正的状态价值函数。

具体的算法如图：

在递推的过程中改进策略

在迭代的过程中，如果已知策略 的价值函数 希望知道在某个状态 下选择一个不同于 的动作 是否会带来改善，这种策略的价值为：

如果上面的式子的值大于目前的状态价值函数 那么就更新此时的策略为

而由于所有的策略的状态价值函数存在偏序关系，也就是说存在 upper bound 那么就可以利用这一点证明，每次取贪心的策略 即
$$
\pi’ = \mathop{argmax}a q_\pi(s,a) = \mathop{argmax}a \mathbb E[R{t + 1} + \gamma v_\pi (S{t +1}) | S_t = s,A_t = a] = \mathop{argmax }a \sum{s’,r} p(s’,r|s,a)[r +\gamma v_\pi(s’)]
$$
那么根据上面的式子，每一次向前看一步，根据新的状态价值函数可以贪心地更新当前的策略。

迭代的终止条件

经过不断的迭代，如果最后出现两个策略 和 完全相同，即对于任意的 有

注意到这个式子和Bellman Equation 的形式是一样的，也就是说迭代除非到达最优策略，否则可以继续进行

算法流程图

在迭代的过程中更新价值函数和策略的大致流程图如下：

价值迭代

注意到上面的迭代其实是根据策略进行迭代的，也就是说选择一个初始的策略，然后进行贪心去逼近最优的算法，但这样的速度是非常慢的，所以可以利用最开始的哪个价值迭代的递推表达式，来直接进行价值迭代，其算法示意图如下：

这种算法不依赖任何初始的策略，只依赖价值，收敛速度更快，但是每一次都要遍历整个图，所以称为 同步的 动态规划算法。