Sutton 强化学习， 21 点游戏的策略蒙特卡洛值预测

会员服务 ·

Sutton 强化学习， 21 点游戏的策略蒙特卡洛值预测

2020 年 10 月 13 日 CSDN

作者 | MyEncyclopedia

来源 | MyEncyclopedia（ID ：MyEncyclopedia）

头图 | CSDN 下载自东方IC

从这期开始我们进入 Sutton 强化学习第二版，第五章蒙特卡洛方法。蒙特卡洛方法是一种在工程各领域都存在的基本方法，在强化领域中，其特点是无需知道环境的 dynamics，只需不断模拟记录并分析数据即可逼近理论真实值。蒙特卡洛方法本篇将会用21点游戏作为示例来具体讲解其原理和代码实现。

21点游戏问题

21点游戏是一个经典的赌博游戏。大致规则是玩家和庄家各发两张牌，一张明牌，一张暗牌。玩家和庄家可以决定加牌或停止加牌，新加的牌均为暗牌，最后比较两个玩家的牌面和，更接近21点的获胜。游戏的变化因素是牌 Ace ，既可以作为11也可以作为1来计算，算作11的时候称作 usable 。

Sutton 教材中的21点游戏规则简化了几个方面用于控制问题状态数：

已发的牌的无状态性：和一副牌的21点游戏不同的是，游戏环境简化为牌是可以无穷尽被补充的，一副牌的某一张被派发后，同样的牌会被补充进来，或者可以认为每次发放的牌都是从一副新牌中抽出的。统计学中的术语称为重复采样（sample with replacement）。这种规则下极端情况下，玩家可以拥有 5个A或者5个2。另外，这会导致玩家无法通过开局看到的3张牌的信息推断后续发牌的概率，如此就大规模减小了游戏状态数。
庄家和玩家独立游戏，无需按轮次要牌。开局给定4张牌后，玩家先行动，加牌直至超21点或者停止要牌，如果超21点，玩家输，否则，等待庄家行动，庄家加牌直至超21点或者停止要牌，如果超21点，庄家输，否则比较两者的总点数。这种方式可以认为当玩家和庄家看到初始的三张牌后独立做一系列决策，最后比较结果，避免了交互模式下因为能观察到每一轮后对方牌数变化产生额外的信息而导致的游戏状态数爆炸。

有以上两个规则的简化，21点游戏问题的总状态数有下面三个维度

自己手中的点数和（12到21）
庄家明牌的点数（A到10)
庄家明牌是否有 A（True, False）。

状态总计总数为三个维度的乘积 10 * 10 * 2 = 200。

关于游戏状态有几个比较 subtle 的假设或者要素。首先，玩家初始时能看到三张牌，这三张牌确定了状态的三个维度的值，当然也就确定了 Agent 的初始状态，随后按照独立游戏的规则进行，玩家根据初始状态依照某种策略决策要牌还是结束要牌，新拿的牌更新了游戏状态，玩家转移到新状态下继续做决策。举个例子，假设初始时玩家明牌为8，暗牌为6，庄家明牌为7，则游戏状态为 Tuple (14, 7, False)。若玩家的策略为教材中的固定规则策略：没到20或者21继续要牌。下一步玩家拿到牌3，则此时新状态为 (17, 7, False)，按照策略继续要牌。

第二个方面是游戏的状态完全等价于玩家观察到的信息。比如尽管初始时有4张牌，真正的状态是这四张牌的值，但是出于简化目的，不考虑 partially observable 的情况，即不将暗牌纳入游戏状态中。另外，庄家做决策的时候也无法得知玩家的手中的总牌数。

第三个方面是关于玩家点数。考虑玩家初始时的两张牌为2，3，总点数是5，那么为何不将5加入到游戏状态中呢？原则上是可以将初始总和为2到11都加入到游戏状态，但是意义不大，原因在于我们已经假设了已发牌的无状态性，拿到的这两张牌并不会改变后续补充的牌的出现概率。当玩家初始总和为2到11时一定会追加牌，因为无论第三张牌是什么，都不会超过21点，只会增加获胜概率。若后续第三张牌为8，总和变成13，就进入了有效的游戏状态，因为此时如果继续要牌，获得10，则游戏输掉。因此，我们关心的游戏状态并不完全等价于所有可能的游戏状态。

21点游戏 OpenAI Gym环境

OpenAI Gym 已经实现了 Sutton 版本的21点游戏环境，并按上述规则来进行。在安装完 OpenAI Gym 包之后 import BlackjackEnv 即可使用。

from gym.envs.toy_text import BlackjackEnv

根据这个游戏环境，我们先来定义一些类型，可以令代码更具可读性和抽象化。State 上文说过是由三个分量组成的Tuple。Action 为 bool 类型表示是否继续要牌。Reward 为+1或者-1，玩家叫牌过程中为0。StateValue 为书中的，实现上是一个 Dict。DeterministicPolicy 为一个函数，输入是某一状态，输出是唯一的决策动作。

State = Tuple[int, int, bool]Action = boolReward = floatStateValue = Dict[State, float]DeterministicPolicy = Callable[[State], Action]

以下代码是 BlackjackEnv 核心代码，step 方法的输入为玩家的决策动作（叫牌还是结束），并输出 State, Reward, is_done。简单解释一下代码逻辑，当玩家继续加牌时，需要判断是否超21点，如果没有超过的话，返回下一状态，同时 reward 为0，等待下一 step 方法。若玩家停止叫牌，则按照庄家策略：小于17时叫牌。游戏终局时产生+1表示玩家获胜，-1表示庄家获胜。

class BlackjackEnv(gym.Env):
    def step(self, action):        assert self.action_space.contains(action)        if action:  # hit: add a card to players hand and return            self.player.append(draw_card(self.np_random))            if is_bust(self.player):                done = True                reward = -1.            else:                done = False                reward = 0.        else:  # stick: play out the dealers hand, and score            done = True            while sum_hand(self.dealer) < 17:                self.dealer.append(draw_card(self.np_random))            reward = cmp(score(self.player), score(self.dealer))            if self.natural and is_natural(self.player) and reward == 1.:                reward = 1.5        return self._get_obs(), reward, done, {}
    def _get_obs(self):        return (sum_hand(self.player), self.dealer[0], usable_ace(self.player))

下面示例如何调用 step 方法生成一个 episode 的数据集。数据集的类型为 List[Tuple[State, Action, Reward]]。

def gen_episode_data(policy: DeterministicPolicy, env: BlackjackEnv) -> List[Tuple[State, Action, Reward]]:    episode_history = []    state = env.reset()    done = False    while not done:        action = policy(state)        next_state, reward, done, _ = env.step(action)        episode_history.append((state, action, reward))        state = next_state    return episode_history

策略的蒙特卡洛值预测

Monte Carlo Prediction 解决如下问题：当给定 Agent 策略时，反复试验来预估策略的值。具体来说，产生一系列的episode数据之后，对于出现了的所有状态分别计算其Return，再通过 average 某一状态 s 的 Return 来估计，理论上，依据大数定理（Law of large numbers），在可以无限模拟的情况下，Monte Carlo prediction 一定会收敛到真实的。算法实现上有两个略微不同的版本，一个版本称为 First-visit，另一个版本称为 Every-visit，区别在于如何计算出现的状态 s 的 Return 值。

对于 First-visit 来说，当状态 s 第一次出现时计算一次 Returns，若继续出现状态 s 不再重复计算。对于 Every-visit 来说，每次出现 s 计算一次 Returns(s)。举个例子，某 episode 数据如下：

First-visit 对于状态 S1 的 Returns 计算为

Every-visit 对于状态 S1 的 Returns 计算了两次，因为 S1 出现了两次。

下面用 Monte Carlo 来模拟解得书中示例玩家固定策略的 V值，策略具体为：加牌直到手中点数>=20，代码为

def fixed_policy(observation):    """    sticks if the player score is >= 20 and hits otherwise.    """    score, dealer_score, usable_ace = observation    return 0 if score >= 20 else 1

First-visit MC Predicition

伪代码如下，注意考虑到实现上的高效性，在遍历 episode 序列数据时是从后向前扫的，这样可以边扫边更新 G。

对应的 python 实现

def mc_prediction_first_visit(policy: DeterministicPolicy, env: BlackjackEnv,                              num_episodes, discount_factor=1.0) -> StateValue:    returns_sum = defaultdict(float)    returns_count = defaultdict(float)
    for episode_i in range(1, num_episodes + 1):        episode_history = gen_episode_data(policy, env)
        G = 0        for t in range(len(episode_history) - 1, -1, -1):            s, a, r = episode_history[t]            G = discount_factor * G + r            if not any(s_a_r[0] == s for s_a_r in episode_history[0: t]):                returns_sum[s] += G                returns_count[s] += 1.0
    V = defaultdict(float)    V.update({s: returns_sum[s] / returns_count[s] for s in returns_sum.keys()})    return V

Every-visit MC Prediciton

Every-visit 代码实现相对更简单一些，t 从后往前遍历时更新对应 s 的状态变量。如下所示

def mc_prediction_every_visit(policy: DeterministicPolicy, env: BlackjackEnv,                              num_episodes, discount_factor=1.0) -> StateValue:    returns_sum = defaultdict(float)    returns_count = defaultdict(float)
    for episode_i in range(1, num_episodes + 1):        episode_history = gen_episode_data(policy, env)
        G = 0        for t in range(len(episode_history) - 1, -1, -1):            s, a, r = episode_history[t]            G = discount_factor * G + r            returns_sum[s] += G            returns_count[s] += 1.0
    V = defaultdict(float)    V.update({s: returns_sum[s] / returns_count[s] for s in returns_sum.keys()})    return V

策略 V值 3D 可视化

运行 first-visit 算法，模拟10000次 episode，fixed_policy 的 V值的3D图为下面两张图，分别是不含 usable Ace 和包含 usable Ace 。总的说来，一旦玩家能到达20点或21点获胜概率极大，到达13-17获胜概率较小，在11-13时有一定获胜概率，比较符合经验直觉。

同样运行 every-visit 算法，模拟10000次的 V值图。对比两种方法结果比较接近。

更多精彩推荐
☞300亿美元，AMD为什么要买Xilinx？
☞“我们的边缘计算技术点，可能超前了业界一点”
☞1024程序员节开源技术英雄会，参会“英雄榜”发榜
☞5行Python代码实现刷爆全网的动态条形图！
☞如何应对云原生之旅中的安全挑战？
☞区块链+生鲜：杜绝“偷梁换柱”和“以次充好”

登录查看更多

相关内容

马尔科夫链蒙特卡洛采样

关注 317

马尔科夫链蒙特卡洛方法(Markov Chain Monte Carlo)，简称MCMC，产生于19世纪50年代早期，是在贝叶斯理论框架下，通过计算机进行模拟的蒙特卡洛方法(Monte Carlo)。该方法将马尔科夫(Markov)过程引入到Monte Carlo模拟中，实现抽样分布随模拟的进行而改变的动态模拟，弥补了传统的蒙特卡罗积分只能静态模拟的缺陷。MCMC是一种简单有效的计算方法，在很多领域到广泛的应用，如统计物、贝叶斯(Bayes)问题、计算机问题等。

【ICML2020-伯克利】稳定非策略强化学习的表示，Representations for Stable Off-Policy Reinforcement Learning

专知会员服务

17+阅读 · 2020年7月14日

【IJCAI2020】基于生成对抗模仿学习的多模态模仿学习算法框架

专知会员服务

58+阅读 · 2020年5月26日

【圣经书】《强化学习导论(2nd)》电子书与代码，548页pdf

专知会员服务

208+阅读 · 2020年5月22日

【CVPR2020】我们能用强化学习来学习图模型推断的启发规则吗?

专知会员服务

43+阅读 · 2020年5月5日