强化学习基础篇（七）动态规划之价值迭代
1、最优化原理(Principle of optimality)
我们可以将一个最优策略分解为两个部分：
一、在当前状态下采用了最优的动作
二、在后续状态开始沿着最优策略继续进行。
强化学习中的最优性定理可以表示为：
一个策略 能够使得状态获得最优价值，当且仅当：
对于所有的状态可到达任何状态。
从状态中可以获得最优价值，即。
2、确定性价值迭代（Deterministic Value Iteration）
如果我们可以知道子问题的解，即已经获得下一状态的最优价值函数。那么我们就可以很容易得到当前状态的最优价值函数：
在最优性定理的基础上，如果我们清楚地知道我们期望的最终状态的位置以及明确的状态间关系，那么可以认为是一个确定性的价值迭代。此时，我们可以把问题分解成一些列的子问题，从最终目标状态开始分析，逐渐往回推，直至推至所有状态。
3、最短路径问题（Shortest Path）
问题定义
在一个的方格世界中，找到任意一个方格到最左上角方格的最短路径。其中在终点(g)处的奖励为0，其余状态的奖励为-1。
思路：
终点是左上角写着g的灰色格，所以，在迭代的过程中，距离g最近的那两个格子（即A和D）的<svg xmlns:xlink="http://www.w3.org/1999/xlink" width="6.625ex" height="2.298ex" viewBox="0 -780.1 2852.6 989.6" role="img" focusable="false" style="vertical-align: -0.487ex;" class="in-text-selection"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><g transform="translate(769,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">（</text></g><g transform="translate(2045,0)"><text font-family="STIXGeneral, 'PingFang SC', serif" stroke="none" transform="scale(51.874) matrix(1 0 0 -1 0 0)">）</text></g></g></svg>最先可以算出最大值。对于A来说，只要选择向左，就可以到达终点获得reward，而向右则没有奖赏。所以根据公式中的max，A就会选择左走，它的值最大，所以第一次迭代它就已经可以获得最大值了，然后接下来就是对于B来说，第一次迭代向左和向右都一样，但是在第二次迭代中就会发现两次向左就可以达到最大值。这就是值迭代的过程。
求解过程：
一、初始化每个状态的为0。
二、对于第一次迭代：
由于对于，所以就可以得出。
三、对于第二次迭代：
对于状态A:
对于状态B:
以此类推，直到每个状态的累积奖赏都不变。
结果：
4、价值迭代（Value Iteration）
问题：
寻找最优策略。
解决方案：
从初始状态价值开始同步迭代计算，最终收敛，整个过程中没有遵循任何策略。
与策略迭代一样，价值迭代最终也同样收敛到最优值函数，不过，与策略迭代不一样的是，价值迭代没有显式的策略，它通过贝尔曼最优方程，隐式地实现了策略改进这一步。值得注意的是，中间过程中的价值函数可能并不对应于任何策略
价值迭代虽然不需要策略参与，但仍然需要知道状态之间的转移概率，也就是需要知道模型。
算法描述
我们通过回溯（backup）图来对价值迭代进行理解：
其更新过程为贝尔曼最优方程：
一般形式为：
矩阵形式为：
与贝尔曼期望方程相比，贝尔曼最优方程将期望操作变为最大操作，也即隐式地实现了策略改进这一步，不过是固定为greedy的，而不是其他策略改进方法，我们通过greedy得到的策略通常为确定性策略。
5、策略评估（Policy Evaluation）、策略迭代(Policy Iteration)以及值迭代(Value Iteration)总结
这三个算法通过一张表可以总结如下：
| 问题（Problem） | 应用的贝尔曼方程 （Bellman Equation） | 使用到的算法（Algorithm） |
|---|---|---|
| 预测(Prediction） | 贝尔曼期望方程（Bellman Expectation Equation） | 迭代式策略评估（Iterative Policy Evaluation） |
| 控制（Control） | 贝尔曼期望方程（Bellman Expectation Equation）+ 贪婪策略改进（Greedy Policy Improvement） | 策略迭代(Policy Iteration) |
| 控制（Control） | 贝尔曼最优方程（Bellman Optimality Equation） | 值迭代(Value Iteration) |
策略评估（Policy Evaluation）、策略迭代(Policy Iteration)以及值迭代(Value Iteration)这三个算法都是基于状态值函数或者
如果动作数量为，状态数量为，那么每次迭代的计算复杂度为。
这三个算法也同样可以应用到动作值函数或者，同时每次迭代的计算复杂度为。
