Question

6 蒙特卡罗方法

6.1 真正的增强学习

本节我们来看看无模型的一种简单解决方法 - 蒙特卡罗法。从名字可以看出，当我们无法得到模型内容时，就需要通过不断模拟的方式得到大量相关的样本，并通过样本得到我们预期得到的结果。通过这样的方式，我们似乎又可以前进了。

在前面的策略迭代中，我们曾经总结了一轮迭代过程中的几个主要步骤：

1. 策略评估
2. 策略改进

其中与模型相关的是策略评估部分，既然没有了模型，我们就需要使用蒙特卡罗的方法得到。因为在之前的策略迭代法有模型信息，所以它只需要评估状态价值函数 - 也就是 v(s)，然后根据 Bellman 公式：

求出状态-行动价值函数，并进行策略改进。现在我们没有了模型，不知道状态转移的情况，于是就需要对状态-行动价值函数进行估计。我们将

变换为：

也就是说，只要这个 MDP 是有终点的，我们就可以计算出每一个状态下的 Return，然后利用大数据的力量求出估计值，然后得出策略评估的结果。

听上去是不是挺简单的？没错，精彩的还在后面。

6.2 蒙特卡罗法

接下来我们就实现一个简单的蒙特卡罗法的代码，更重要的是，我们最终还要拿这个算法的结果和策略迭代法进行比较，看看在不知道环境模型的情况下，蒙特卡罗法能否做到和策略迭代一样的效果。

前面对算法的流程已经有了介绍，我们的整理算法如下所示：

def monte_carlo_opt(self):
    while True:
        self.monte_carlo_eval()
        ret = self.policy_improve()
        if not ret:
            break

其中包含了两个子算法。其中 policy_improve 和前面的算法类似，都是完成：

π(s)=argmaxaq(s,a)

所以这里不再赘述，下面来看看 monte_carlo_eval ，这个方法又分成几个部分，首先要用当前的策略玩游戏，产生一系列的 episode：

env.start()
state = env.pos
episode = []
prev_state = env.pos
while True:
    reward, state = env.action(self.policy_act(state))
    episode.append((reward, prev_state))
    prev_state = state
    if state == -1:
        break

产生 episode 之后，我们再来计算每一个状态的长期回报：

value = []
return_val = 0
for item in reversed(episode):
    return_val = return_val * self.gamma + item[0]
    value.append((return_val, item[1]))

最后，我们将每一个状态-行动对应的 return 记录在状态-行动价值函数上：

# every visit
for item in reversed(value):
    act = self.policy_act(item[1])
    self.value_n[item[1]][act] += 1
    self.value_q[item[1]][act] += (item[0] -  \
        self.value_q[item[1]][act]) /  \
        self.value_n[item[1]][act]

这里涉及到一个小的改变，因为我们要计算期望价值价值，将所有观测到的 return 进行平均，那么假设价值为 V，数量为 N，那么有

这样每一时刻我们都可以求出当前所有观测值的平均数，而且这个公式和我们常见的梯度下降法也十分类似，其中的 像学习率，而 像目标函数的梯度。那么是不是真的可以这么考虑呢？当然是的。

以上就是我们进行一轮游戏的运算过程，实际上我们会有多轮游戏，我们先将游戏轮数设置为 100，也就是说，每一次策略评估，我们都来玩 100 轮游戏，并根据这一百轮游戏的结果完成估计。这样，蒙特卡罗算法的基本框架就搭起来了。大家一定非常想看看它的效果，于是我们就来和策略迭代进行一次对比，：

def monte_carlo_demo():
    np.random.seed(0)
    env = Snake(10, [3,6])
    agent = MonteCarloAgent(100, 2, env)
    with timer('Timer Monte Carlo Iter'):
        agent.monte_carlo_opt()
    print 'return_pi={}'.format(eval(env,agent))
    print agent.policy
    agent2 = TableAgent(env.state_transition_table(), env.reward_table())
    with timer('Timer PolicyIter'):
        agent2.policy_iteration()
    print 'return_pi={}'.format(eval(env,agent2))
    print agent2.policy

最终的结果为：

Timer Monte Carlo Iter COST:0.128234863281
return_pi=81
[0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0
 0 0 0 1 1 0 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1
 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
policy evaluation proceed 94 iters.
policy evaluation proceed 62 iters.
policy evaluation proceed 46 iters.
Iter 3 rounds converge
Timer PolicyIter COST:0.329040050507
return_pi=84
[0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0
 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0]

可以看出，蒙特卡罗的结果比策略迭代还是要差一些，下面我们就来看看它们差距的原因。

6.3 探索与利用

一直以来我们没有花大篇幅做增强学习原理方面的讨论，是因为前面的算法虽然漂亮，但它们并不能帮我们直接解决实际问题，我们遇到的实际问题大多数都是不知道环境模型，或者环境模型太过于复杂的。所以这涉及到增强学习的一个思路，用英文讲就是“try and error”。

由于不知道完整的环境信息，我们只能通过不断地尝试去增加对环境和问题的理解，并通过这些理解帮助我们做出更好的决策。这里面肯定会走不少弯路，而且有一些弯路甚至不易发觉。所以增强学习遇到的一个问题是，如何找到更好的解决问题的路径，并确认这样路径应该就是最优的路径。

回到蛇棋的问题上来，在前面的问题中，我们可以看到棋盘，所以我们可以精确求出每一个状态-行动的价值函数。但是对于无模型的问题，我们能不能保证遍历所有的状态行动呢？

对于这个问题，我们可以想象，一开始所有的价值函数都初始化为 0，所有的策略均使用第一种投掷手法，如果我们固定这种手法不变，那么我们只能得到这种手法的 return，那么除非这种手法估计得到的价值函数为负，不然新的手法将不会被选中，也不会进行任何的模拟尝试，这就为我们带来了麻烦。

所以，为了“雨露均沾”，我们必须让其他没有被选为最优策略的行动也参与到模拟游戏的过程中来，这样才能让每一个 q(s,a) 都有值，这样做策略改进菜有意义。

基于这个想法，我们改进了我们的策略模块，我们采用一种叫ϵ−greedyϵ−greedy 的方法，首先用一个 0 到 1 的随机数进行判断，如果随机数小于某个ϵϵ，那么我们将采用完全随机的方式产生行动，而在其他情况下将选择当前的最优策略。代码如下：

def policy_act(self, state):
    if np.random.rand() < 0.05:
        return np.random.randint(self.act_num)
    else:
        return self.policy[state]

在这里，我们设定的ϵϵ是 0.05，完成了这一步的修改，我们结果将会如何呢？

Timer Monte Carlo Iter COST:0.486936807632
return_pi=84
[0 1 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 1 0 1 1 0 0
 0 0 1 0 0 1 1 0 0 0 0 1 1 1 1 1 0 0 1 0 1 1 1 0 1 1 0 1 1 1 0 0 0 0 0 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 0 0 0]
policy evaluation proceed 94 iters.
policy evaluation proceed 62 iters.
policy evaluation proceed 46 iters.
Iter 3 rounds converge
Timer PolicyIter COST:0.325078964233
return_pi=84
[0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0
 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0]

可以看出，虽然两种方法的最终策略不同，但是模拟得到的分数几乎相同。说明在增加了对不同方法的尝试后，算法真的会有大幅的提高。

这个问题在增强学习中也被称为是“探索与利用”的对立问题。所谓的探索是指不拘泥于当前的表现，选择一些其他的策略完成行动；利用就是持续使用当前的最优策略，尽可能地获得更多的回报。我们假设总的资源是有限的，比方说时间有限，可以进行模拟游戏的轮数有限，我们不能无止尽地探索，也不能短视地一直利用，那么就需要尝试在两者之间寻找一个平衡。

前面我们提到，蒙特卡罗方法需要模型有明确的终止状态，那么总有一些问题是没有终止状态的，或者说有些任务需要在线学习，也就是说边尝试边学习，这些场景并不是很适合蒙特卡罗方法。而且蒙特卡罗方法也有自己的小问题，那么下一节我们就来看看另一种解决无模型问题的方法。