动态规划与强化学习的关系
动态规划的关键点在于：（1）问题的最优解可以由若干个小问题的最优解构成，即通过寻找子问题的最优解可以得到问题的最优解；（2）可以找到子问题状态之间的递推关系。强化学习明显能满足这两个条件。
强化学习的两个基本问题是：（1）给定状态集\(S\)，动作集\(A\)，模型状态转化概率矩阵\(P\)，即时奖励\(R\)，衰减因子\(\gamma\)，给定策略\(\pi\)，求解该策略的状态价值函数\(v(\pi)\)；（2） 给定状态集\(S\), 动作集\(A\), 模型状态转化概率矩阵\(P\), 即时奖励\(R\)，衰减因子\(\gamma\)，求解最优的状态价值函数\(v_{*}\)以及最优策略\(\pi_{*}\)
由贝尔曼方程可得：
\[ v_{\pi}(s) = \sum\limits_{a \in A} \pi(a|s)(R_s^a + \gamma \sum\limits_{s' \in S}P_{ss'}^av_{\pi}(s')) \]
根据上式可以将\(v_{\pi}(s)\)的计算问题分解为计算\(v_{\pi}(s')\)的子问题。因此，可以使用上一个迭代周期内的状态价值来计算更新当前迭代周期某状态\(s\)的状态价值。
策略评估求解预测问题
策略评估的基本思路是从任意一个状态价值函数开始，依据给定的策略，结合贝尔曼方程、状态转移概率和奖励同步迭代更新状态价值函数，直至其收敛，得到该策略下最终的状态价值函数。
假设我们在第\(k\)轮迭代已经计算出了所有的状态的状态价值，那么在第\(k+1\)轮我们可以利用第\(k\)轮计算出的状态价值计算出第\(k+1\)轮的状态价值。这是通过贝尔曼方程来完成的，即：
\[ v_{k+1}(s) = \sum\limits_{a \in A} \pi(a|s)(R_s^a + \gamma \sum\limits_{s' \in S}P_{ss'}^av_{k}(s')) \]
这个式子与标准的贝尔曼方程相同，即对当前状态价值的计算需要考虑到所有可能的动作以及每个动作带来的所有可能的状态的价值。
使用上述式子不停迭代直至收敛即可。
策略迭代求解控制问题
策略迭代可以被分成两步：（1）使用当前策略\(\pi_*\)评估计算当前策略的最终状态价值\(v_*\)；（2）接着根据状态价值\(v_*\)使用一定的方法（如贪婪法）更新策略\(\pi_*\)，接着回到第一步直到收敛。
价值迭代求解控制问题
与策略迭代的区别在于，策略迭代在第一步完成（也就是状态价值收敛后）才进行策略更新，而价值迭代会随着状态价值的迭代及时调整策略，这样可以大大减少迭代次数。此时的状态价值的更新方法也与策略迭代不同，现在的贝尔曼方程的迭代式子如下：
\[ v_{k+1}(s) = \max_{a \in A}(R_s^a + \gamma \sum\limits_{s' \in S}P_{ss'}^av_{k}(s')) \]
价值迭代中的贝尔曼方程在计算当前状态价值时只考虑状态价值最高的动作所带来的所有状态的价值，而不考虑剩下的其余动作，这样能更快速的收敛。
异步动态规划算法
前面提到的都是同步动态规划算法，即每轮迭代会计算出所有的状态价值并保存起来，并在下一轮中使用这些保存起来的状态价值来计算新一轮的状态价值。
而异步动态规划算法在每一次迭代中并不会对所有状态的价值进行更新，而是根据一定的原则有选择性的更新部分状态的价值。较为常见的异步动态规划算法有三种：
- 原位动态规划： 这种方法不会另外保存一份上一轮计算出的状态价值，而是即时计算即时更新。这样可以减少保存的状态价值的数量，节约内存。代价是收敛速度可能稍慢。
- 优先级动态规划：改算法根据贝尔曼误差（即新状态价值与上一次状态价值之间的差值）的大小对状态进行优先级分级，优先级越高的状态其状态价值优先得到更新，这样能够有加快收敛速度，代价是需要维护一个优先级队列。
- 实时动态规划：直接使用个体与环境交互产生的实际经历来更新状态价值，对于那些实际经历过的状态的价值进行更新。这种方法收敛速速的慢，而且在环境中不经常出现的状态的价值可能不会充分的收敛。
动态规划小结
动态规划主要使用贝尔曼方程以及贪婪法进行状态价值以及策略的更新。但是动态规划的回溯机制是全宽度的，即在更新某个状态的价值时都要回溯到该状态所有可能的后续状态，当问题规模较大时，动态规划算法会因为贝尔曼维度灾难而无法使用。