蒙特卡罗预测 (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)，那么庄家获胜。如果没有爆就停止要牌，那就轮到庄家要牌，庄家如果爆了，那就玩家获胜，否则就比最终的大小来区分胜负或者平局。
读者可以在继续阅读之前上网“搜索21点在线”来试玩一下，这样对这个游戏更加熟悉。进入网站点击”Try it free”可以免费单人试玩，请不要赌博！！
从游戏的技巧来看（作者在学习强化学习之前也没玩过，所有总结的不一定正确），玩家需要根据庄家亮的牌以及自己牌的和来决定是否继续要牌。同样庄家可能需要根据自己的点数以及玩家的牌的张数以及玩家要牌的快慢表情等(如果是跟机器玩可能就无表情了？机器能像人那样使用表情骗人吗？——明明分不高故意装得很有信心，从而引导对手爆掉)来决定是否继续要牌。另外就是Ace的使用，如果把 Ace 算成 11 也没有超过 21 点，那么在要牌肯定不会爆掉，但是有可能分变小，比如现在是3+Ace，我们可以认为是 4 点或者 14 点，但似乎都有点少，那么我们再要一张。如果是8，那么Ace只能算成1，否则就爆了(22)，这样的结果就是 12 点。
由于有两个角色——庄家和玩家，玩的好的 Agent 可能还要对对手建模，甚至还要利用对手的表情这样的信息，包括用表情来骗人。这里为了简单，我们假设看不到表情，而且我们的 Agent 是玩家，而庄家使用一个固定的策略：如果得分达到或者超过 17 就 stick，否则就一直 hit。
我们可以用 MDP 来对这个游戏进行建模，这是个有限的 MDP，而且是 Episodic 的，游戏肯定会结束。对于结束状态，获胜、失败和平局，Reward分别是 +1、-1 和 0。没有结束的状态的Reward 都是 0,打折因子是 1。玩家的 Action 只有 stick 和 hit 两种。状态是玩家的牌和庄家亮出来的那种牌（这部分信息是玩家可以获得的所有信息）。此外为了简单，我们假设发牌的牌堆是无限的（也就是每种牌都可能无限张，因此记住已经发过的牌是没有什么意义的，但实际的情况是有区别的，如果拿过一张Ace，那么再拿到 Ace 的概率会变化）
（编辑：温州站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
