在第一篇博文的时候，我们已经把强化学习的目标给介绍了，基本上就是围绕两个价值函数和策略。

但是求解这个问题并没有那么简单，一个显然的困难就是我们在改变策略的时候，价值函数也会发生变化，如何处理这个问题就是我们今天算法的核心。

0. 关于这两个价值函数

为了更深入地了解这个问题，我们应该更深入地思考这两个价值函数，下面我直接给出他们的性质：

（1）q函数和v函数互转：

1.  q转v：
2. v转q：

有了这个性质，我们知道v就可以求q了。

（2） Bellman方程：

这个东西其实是用来更新我们的价值函数的。

 

1. 策略迭代法

策略迭代法是接下来我要讲的重点，它的核心思想是：你看，我的策略和价值，其实是一对相互依赖的关系。那我就用这两者相互更新——用策略更新价值，再用价值更新策略，不断重复上述过程，知道我的价值收敛为止。

这个算法用伪代码描述就是：

以某种策略π开始，计算当前策略下的值函数

• 利用这个值函数，更新策略，得到π∗
• 再用这个策略π∗
• 继续前行，更新值函数，得到，一直到不在发生变化。

用一张图来描述，就是：

这时候，就会冒出两个问题：

1.  怎么用值函数更新策略？
2.  怎么用策略更新值函数？

 

2. 值函数更新策略——理论部分

先上结论，如果你的新策略，一直选择当前状态最大的Q值，你就会获得一个更好的策略：

如图所示，只要选择能让Q达到最大的a当作我们的策略，就可以达到一个更优的解。如此不断，我们就可以得到一个理想的解。

下图是关于这个观点的推导：

所以，我们的策略的更新应该是。

 

3. 值函数更新策略——探索部分

不过，如果我们单单是使用上面提到的方法来更新策略，那就是有问题的。

想象这么一个问题：在一开始探索时，某一个状态的所有动作的价值都是相同的。在某一轮更新的时候，其中一个动作被采样到，其价值得到更新。——如果采用一直选择最大动作的方法，我们在以后就永远无法探索其他动作了。而其它动作可能有着更好的reward。

因此，我们不能一味地只选择最大值。对于这个问题，有两个解决方法：

（1） Epsilon贪心法

这个方法很简单，就是设置一个很小的概率，如果我们恰好落到这个概率里面，我们就进行随机地探索。

（2） Boltzman方法

这个方法也很简单，就是根据你Q的值，进行softmax转换，用转换得到的概率进行探索。你看，这也符合，越大的概率，越容易被采样到这个事实。

 

4. 用策略更新值函数

下面重点介绍三个方法：DP， MC和TD，最后会涉及到这三种方法的比较。

（1）动态规划算法

动态规划主要基于以下思想：

你看，它的做法是用其它状态来更新现在的状态，缺点是我们需要精确的概率转换模型。而且我需要所有可能的下一个状态。

（2）蒙特卡洛算法

蒙特卡洛的思想更简单了，通过你的策略采样。采样到多个trajectory，算出每一状态的收获，取平均。

这个也有优化方法，注意到这个方法我们要把每一次采样到的trajectory都存起来，才能算平均。

如果能动态地添加进新的收获那是最好的。一个解决方法就是通过迭代，考虑算平均值时进来了一个新的数字：

所以，我们的MC方法就是：

（3）时序差分算法

MC算法的一个缺点就是——由于他需要精确地计算每一个状态的收获，所以他一定要完整的状态序列。

然而很多时候状态序列很长，甚至根本就停不下来，因此我们需要一个更好的方法，TD算法就是这种方法，它是我们后面算法的基础。TD算法更新如下：

这里详细谈谈他和MC方法的不同之处（因为没有人会用DP）:

1.  由于没有完整的序列，因此不知道更新项前面的系数，这里采用了一个超参数来代替。
2.  MC方法需要在收集完以后，走完整个trajectory来累计reward。而TD法则是用后续的状态的价值来代替了。

 

5. 总结

价值函数更新方法	特点	缺点
DP	用其他下一个所有可能的状态来更新当前状态	1. model-based 方法 2. 需要所有后续状态，可能陷入bellman维数爆炸的现象。
MC	自己手动计算reward	1. 有些时候trajectory太长或根本无法停止。 2. reward其实是一个随机变量，累加导致variance高。
TD	利用其它的价值来更新自己的价值	与MC相比，由于其它状态的价值也是自己估计的，所以不太精确