深度学习和强化学习（二）

动态规划求解强化学习问题：

动态规划的关键点有两个：一是问题的最优解可以由若干小问题的最优解构成，即通过寻找子问题的最优解来得到问题的最优解。第二是可以找到子问题状态之间的递推关系，通过较小的子问题状态递推出较大的子问题的状态。而强化学习的问题恰好是满足这两个条件的。

强化学习的两个基本问题：

首先，我们来看如何使用动态规划来求解强化学习的预测问题，即求解给定策略的状态价值函数的问题。这个问题的求解过程我们通常叫做策略评估(Policy Evaluation)。策略评估的基本思路是从任意一个状态价值函数开始，依据给定的策略，结合贝尔曼期望方程、状态转移概率和奖励同步迭代更新状态价值函数，直至其收敛，得到该策略下最终的状态价值函数

策略评估实例：

给定的策略是随机策略，即每个格子里有25%的概率向周围的4个格子移动

一直迭代下去，直到每个格子的策略价值改变很小为止。这时我们就得到了所有格子的基于随机策略的状态价值。

策略迭代求解控制问题：

一种可行的方法就是根据我们之前基于任意一个给定策略评估得到的状态价值来及时调整我们的动作策略，这个方法我们叫做策略迭代(Policy Iteration)。

如何调整呢？最简单的方法就是贪婪法。考虑一种如下的贪婪策略：个体在某个状态下选择的行为是其能够到达后续所有可能的状态中状态价值最大的那个状态。

如上面的图右边。当我们计算出最终的状态价值后，我们发现，第二行第一个格子周围的价值分别是0,-18,-20，此时我们用贪婪法，则我们调整行动策略为向状态价值为0的方向移动，而不是随机移动。也就是图中箭头向上。而此时第二行第二个格子周围的价值分别是-14,-14,-20, -20。那么我们整行动策略为向状态价值为-14的方向移动，也就是图中的向左向上。

　　　　如果用一副图来表示策略迭代的过程的话，如下图：

　在策略迭代过程中，我们循环进行两部分工作，第一步是使用当前策略π∗评估计算当前策略的最终状态价值v∗，第二步是根据状态价v根据一定的方法（比如贪婪法）更新策略π∗，接着回到第一步，一直迭代下去，最终得到收敛的策略π∗和状态价值v∗。

价值迭代求解控制问题：

观察第三节的图发现，我们如果用贪婪法调整动作策略，那么当k=3的时候，我们就已经得到了最优的动作策略。而不用一直迭代到状态价值收敛才去调整策略。那么此时我们的策略迭代优化为价值迭代。

还是以第三节的例子为例，如上面的图右边。比如当=2时，第二行第一个格子周围的价值分别是0,-2,-2，此时我们用贪婪法，则我们调整行动策略为向状态价值为0的方向移动，而不是随机移动。也就是图中箭头向上。而此时第二行第二个格子周围的价值分别是-1.7,-1.7,-2, -2。那么我们整行动策略为向状态价值为-1.7的方向移动，也就是图中的向左向上。

和上一节相比，我们没有等到状态价值收敛才调整策略，而是随着状态价值的迭代及时调整策略, 这样可以大大减少迭代次数。此时我们的状态价值的更新方法也和策略迭代不同。现在的贝尔曼方程迭代式子如下：

不再有一个选择动作的策略权重 π(a|s)

由于策略调整，我们现在价值每次更新倾向于贪婪法选择的最优策略对应的后续状态价值，这样收敛更快

异步动态规划：

前几节我们讲的都是同步动态规划算法，即每轮迭代我会计算出所有的状态价值并保存起来，在下一轮中，我们使用这些保存起来的状态价值来计算新一轮的状态价值。

　　　　另一种动态规划求解是异步动态规划算法，在这些算法里，每一次迭代并不对所有状态的价值进行更新，而是依据一定的原则有选择性的更新部分状态的价值，这类算法有自己的一些独特优势，当然有额会有一些额外的代价。

动态规划算法使用全宽度（full-width）的回溯机制来进行状态价值的更新，也就是说，无论是同步还是异步动态规划，在每一次回溯更新某一个状态的价值时，都要回溯到该状态的所有可能的后续状态，并利用贝尔曼方程更新该状态的价值。这种全宽度的价值更新方式对于状态数较少的强化学习问题还是比较有效的，但是当问题规模很大的时候，动态规划算法将会因贝尔曼维度灾难而无法使用。因此我们还需要寻找其他的针对复杂问题的强化学习问题求解方法。