蒙特卡罗预测 (Monte Carlo Prediction)

21 点游戏 (Blackjack)

蒙特卡罗预测代码示例

Blackjack 环境

蒙特卡罗预测代码

蒙特卡罗控制

多臂老虎机和 UCB

On-Policy 蒙特卡洛控制

On-Policy 蒙特卡罗控制代码示例

Off-Policy 蒙特卡罗预测

Off-Policy 蒙特卡罗控制

Off-Policy 蒙特卡罗控制代码示例

动态规划和蒙特卡罗方法的比较

接下来我们介绍解决 MDP 问题的另外一种方法——蒙特卡罗方法。前面的动态规划方法，我们需要完全的环境动力学 (′,|,) 。而蒙特卡罗方法只需要经验 (Experience)——通过与真实环境交互或者模拟得到的状态、行为和奖励的序列。如果从模拟学习，那么需要一个模型来建模环境，但是这个模型不需要完整的环境动力学，它只需要能采样即可。有的时候显示的定义一个概率分布是很困难的，但是从中获取样本却比较容易。

蒙特卡罗方法通过平均采样的回报(return)来解决强化学习问题。它要求任务是 Episodic 的，并且一个 Episode 进入终止状态后才能开始计算（后面介绍的 Temporal Difference 不需要任务是 Episodic，即使 Episodic 的任务也不用等到一个 Episode 介绍才能计算）。

蒙特卡罗预测(Monte Carlo Prediction)

首先我们来使用蒙特卡罗方法解决预测问题——给定策略，计算状态价值函数的问题。回忆一下，状态的价值是从这个状态开始期望的回报——也就是期望的所有未来 Reward 的打折累加。因此很直观的想法就是从经验中估计——所有经过这个状态的回报的平均。我们的目标是估计 ，但是我们有的只是一些经验的 Episode，这些 Episode 是采样策略 得到的。也就是Episode1,1,2,…,∼ 。而 t 时刻状态是 s 的回报是如下定义的：

=++1+...+−1

而状态价值函数是采样策略 时期望的回报：

()=[|=]

蒙特卡罗方法的思想是使用(采样的)平均回报来估计期望回报，根据大数定律，如果采样的次数趋于无穷，那么估计是无偏的。

比如我们要估计 () ，我们用很多 Episodic 的经验，这些经验是使用策略 获得的。一个Episode里 s 的每次出现都叫做 s 的一次 visit。当然在一个 Episode 里 s 可能多次出现，一种方法只考虑 s 的第一次 visit，这就叫 First-Visit 蒙特卡罗方法；而另外一种就是每次 visit 都算，这就是 Every-Visit 蒙特卡罗方法。这两者的收敛在理论上有一些细微区别，我们这里不讨论，这里我们使用 First-Visit 蒙特卡罗方法。算法伪代码如下：

图：First-Visit蒙特卡罗方法伪代码

21 点游戏 (Blackjack)

在介绍蒙特卡罗预测的代码之前，我们来学习一下 21 点游戏的玩法，并且说明为什么之前的动态规划很难解决这个问题，后面我们会使用蒙特卡罗方法来估计状态的价值函数。

这个游戏有一个庄家和一个玩家(我们这里假设只有一个玩家)，有一副扑克牌，他们的目标是使得手中所有的牌加起来尽可能大，但是不能超过 21（可能等于），最终谁的大谁获胜，如果一样大就是平均 (Draw)。所有的花牌 (Face，也就是J、Q、K)都算作 10，Ace 可以算 1 也可以算11。游戏开始时庄家和玩家都会发到两张牌，庄家的一张牌是亮出来的，而玩家的两张牌是不亮的。如果这两张牌是 21 点(一个 Ace 和一个花牌或者一个 10)，那么就叫一个 natural，如果对手不是 natural，那就获胜，否则是平局。如果都不是 natural，那么玩家可以有两种选择，继续要牌(hit)或者不要(stick)。如果继续要牌之后超过21点，就叫爆了(goes bust)，那么庄家获胜。如果没有爆就停止要牌，那就轮到庄家要牌，庄家如果爆了，那就玩家获胜，否则就比最终的大小来区分胜负或者平局。