4.3　蒙特卡罗控制

策略评估的结果是获得了每一个状态行为对（s_t，a_t）的行为值函数Q（s_t，a_t），策略控制要做的事情就是基于策略评估结果采用贪心算法改进策略。

如果每次都使用贪心算法就会存在一个问题，很有可能由于没有足够的采样经验而导致我们选择的是并不是最优的策略。因此，我们需要不时地尝试新行为去挖掘更多的信息，这就是探索（Exploration），使用一个示例来解释。

如图4-1所示，有6个宝盒。打开1号宝箱得到立即回报为1：V（1）=1。打开2号宝箱得到立即回报为3：V（2）=3。打开3号宝箱得到立即回报为2：V（3）=2。

在这种没有足够采样的情况下，如果使用贪心算法，将会继续打开2号宝箱。打开2号宝箱是否就一定是最好的选择呢？答案显然是否定的。也许4、5、6号宝箱会有更高的回报。因此完全使用贪心算法改进策略通常不能得到最优策略。

为了解决这一问题，需要引入一个随机机制，使得某一状态下所有可能的行为都有一定非零概率被选中执行，以保证持续的探索，代表性的方法是ε-贪心探索（也称ε-贪心法）。以ε的概率从所有动作中均匀随机选取一个，以1-ε的概率选取当前最优动作。假设m为动作数，在ε-贪心策略中，当前最优动作被选中的概率是，而每个非最优动作被选中的概率是，数学表达式如下：

ε-贪心策略中，每个动作都会被选取，保证了探索的充分性。如果使用这样的策略进行采样（生成轨迹），就可以保证多次采样产生不同的采样轨迹，保证采样的丰富性。

接下来需要证明使用ε-贪心策略可以改进任意一个给定的策略，并且是在评估这个策略的同时改进它。假设需要改进的原始策略为π，使用ε-贪心策略选取动作后对应的策略为π'。

证明：

其中，

则有

上述结果表明，ε-贪心探索策略可以改进任意一个给定的策略π，满足Q_π（s，π'（s））≥V_π（s）。紧接着需要证明：策略改进后，值函数单调递增，即V_π（s）≤V_π'（s）。

证明过程如下：

解决了策略评估和策略控制两个问题，最终得到蒙特卡罗方法，即使用行为值函数Q进行策略评估，使用ε-贪心算法改进策略，该方法最终可以收敛至最优策略，如图4-2所示。