附代码！一文看懂强化学习中的蒙特卡罗学习法

当听到“强化学习”这个词时，你的第一反应是什么呢？大多数人认为它涉及过多的数学内容所以过于复杂，但强化学习其实是一个极有魅力的学习领域。这篇文章把强化学习相关的技术拆分为了几个概念，便于大家理解。

你一定听过OpenAI和DeepMind这两大行业领先的AI公司，它们在AI研究领域取得了重大成果。在一款极受欢迎且操作复杂的战斗竞技类游戏——Dota2中，一队OpenAI的电脑玩家击败了游戏中的业余玩家。

所以有人猜想：运用动态规划编写一个电脑机器人来应对像Dota2一样复杂的工作是否可行呢？

很遗憾，答案是不可行。游戏中有成百上亿种状态，要想收集所有有关Dota2的细节是不可能的。这时候就需要进入强化学习或更具体地来说——无模型学习领域。

蒙特卡罗学习法的基本原理是一个重要概念：当你缺乏对环境的先验信息，基本上只能靠经验收集信息时，就可以用到蒙特卡洛学习法。本文将通过使用Python中的OpenAI Gym工具包来实现这一方法。

TIPS：如果你刚刚接触到这个领域或者需要快速地了解一些关于强化学习的术语，强烈推荐阅读以下资料，有助于你在本篇文章中尽可能地学到更多东西。

1. Simple Beginner’s guide to Reinforcement Learning & its implementation

2. Nuts & Bolts of Reinforcement Learning: Model Based Planning using Dynamic Programming

3. Reinforcement Learning Guide: Solving the Multi-Armed Bandit Problem from Scratch in Python

1.有模型学习vs无模型学习

动态规划（或更准确的说法，有模型学习）是用于解决事先已知潜藏环境的问题，强化学习则是从游戏经验中学习。然而在所有的动态规划的算法中，我们都没有真正地玩过这个游戏或者体验过这个环境，因为我们拥有一个完整的环境模型，它包括了所有状态转换的概率。

但是在现实生活中，大多数情况下，一个状态到另一个状态的转换率（或者所谓的环境模型）都是未知的，它甚至不一定遵循马可夫性质。

比方说，我们想训练一个电脑机器人学会国际象棋，需要将国际象棋环境转换为MDP（马可夫决策过程）。

根据每个棋子不同的位置，这个环境存在超过1050 种不同的状态以及成千上万种棋子下一步的可能性。这个环境模型几乎是不可能被设计出来的。

有一种潜在的解决方法是不停地进行国际象棋的对局，每局比赛结束后，获得胜利和失败相应的回报（reward），这就是所说的从经验中学习。

2.蒙特卡罗方法使用的实例

任何通过生成随机数并观察数据是否服从某个性质或某些性质的方法都可以被归为蒙特卡洛方法。

让我们来做一个有趣的实验：尝试用笔和纸来计算出π的值。首先，先绘制一个单位长度的正方形和四分之一个以单位长度为半径的圆。现在一个机器人助手C3PO帮助我们，它的任务是尽可能地在正方形上随机点3000下并得到如下表格：

C3PO将计算在圆形中的点的总和，那么π的值通过如下计算得到：

N是图形圈中点的总数，我们要做的只是计算随机落在圆形中的点然后通过它和N的比值就计算出了π的近似值。

3.蒙特卡罗强化学习

使用蒙特卡洛方法的强化学习可以直接从经验中学习，不需要任何MDP转化率的先验信息。其中随机的要素是return或reward。（return是reward总和的平均数。）

TIPS：蒙特卡洛强化学习只能用于情节性的MDP，原因则是在我们计算回报之前任务必须终止。我们并不是在每个动作结束以后进行数据的更新，而是在每个情节（episode）结束以后进行更新。它采用的是最简单的概念——所得的值来自于每个状态所有样本轨迹的平均回报（mean return）。

每一个状态都是一个独立的多臂老虎机问题，蒙特卡罗强化学习的想法就是让所有的多臂老虎机以最佳状态同时运行。

和动态规划类似，蒙特卡洛强化学习也有策略估计（为随机的策略确定值函数）和策略改进（找到最佳策略）的功能。那么，如何使用这两个方法呢？

这个方法的目的是在π策略下从阶段性经验中学习值函数。回想之前提到的，return是所有状态平均reward的总和：

S1, A1, R2, ….Sk ~ pi

同样，之前提到值函数是预计的累积return：

我们可以简单地通过样本的相加除以样本的总数来估计任何期望值:

• i – Episode index
• s – Index of state

问题是如何得到那些样本return？对于这点，需要先进行一组episode并产出结果。

运行完每一个episode，我们都会得到一系列的状态和reward。然后从这些reward中，我们可以通过定义来计算return，而这正是未来所有reward的总和。

蒙特卡罗的第一次遍历: 平均returns 是指第一次在episode出现的状态。

下面是这个算法的具体步骤：

1. 将策略与状态值函数初始化
2. 根据现有策略开始运行episode
3. 1.记录实验中遇到的所有状态
4. 在 2.1中选取一个状态
5. 1.记录此状态第一次出现后的return
6. 2.算出所有return的平均值
7. 3.将所得return平均数设为状态的值
8. 重复第三步
9. 重复2-4步直到得到满意的结果

全遍历蒙特卡罗方法: 将每一次s – Index of state在episode中遍历，都取回报的平均数:

对于这个算法，我们只需将步骤3.1改为“将每次该状态出现的return记录下来”。

下面我们来看一个样本实例来更好地理解这个概念。假设一个环境拥有两种状态——A和B。让我们观察这两个样本实验：

A+3=>A表示从状态A到状态A的转换附带的reward是3。让我们同时用这两种方法确定值函数：

增量式平均数

这个方法使得将平均return转换为增量式更新变得非常方便，这样平均值就可以随着实验的状态return更新，让我们可以掌控每次实验得到的进展。我们已经知道这个方法可以帮助我们解决多臂老虎机的问题。

将v(s)在每个实验结束后逐渐增加，每个状态St带着return Gt：

在非平稳问题中，这个方法可以用作记录连续的平均数，比如：

V(St) ← V(St) + α (Gt − V(St))

蒙特卡罗控制和动态规划类似，只要我们确定一个随机策略的值函数，关键的任务就只剩下运用蒙特卡罗方法找到最佳策略。

回想一下DP（Date Processing 数据处理）中策略改进的公式，它需要下列所示的环境模型：

这个等式通过找到能够最大化reward的行动来确定最佳策略。然而在这里要注意一下：它采用的状态转换率在无模型学习中是未知的。

既然我们不知道状态转换率p(s’,r/s,a)，我们就不能像DP一样做预测搜索，因此所有的信息都是通过运行episode的经验或探索环境得来的。

策略改进就是尽可能地使策略与现存的值函数接近。这样我们就可以得到一个行动值函数，我们就不需要模型来构建一个贪心策略了。

如果大多数行动并没有被充分地发掘的话，一个贪心策略（就像刚才提到的）总会倾向于某些行动。以下有两个解决方案：

蒙特卡罗探索起点

在该算法中，所有状态动作的起始对概率都大于零。这就保证了所做的每个episode都会将主体带到新的状态，然后实现对环境的更多的探索。

蒙特卡罗epsilon-Soft

那如果一个环境是单一的起点呢（如国际象棋）？探索起点在这种情况下并不适用。回想我们刚刚提到的多臂老虎机的问题，我们讲过epsilon-greedy approach。

为了能够持续地探索，所有行为都要和概率大于0紧密相连——epsilon可能会选择能够得到最大行动值的行动或随机选择一个行动。

现在我们了解了蒙特卡罗控制和估计的基础，让我们将算法运用到Python中。我们将从OpenAI Gym 工具包中导入冰湖环境。

4.蒙特卡罗在Python中的实际运用

玩家会控制一个人物在网格里的移动。网格里一些格子是可行走的，而其他格子则导致玩家落入水中。此外，玩家的移动方向是不确定的，只是部分取决于所选择的方向。玩家找到到达目的地的路径就能获得奖励。

这个游戏表面是由如下格子构成的：

(S:起点，安全)，(F: 冰冻区域，安全)，(H: 洞, 摔死)， (G: 目的地)

这个游戏的规则就是，从起点开始避开所有的洞，只走冰冻的格子然后到达终点。

首先，我们先定义一些辅助函数来设置蒙特卡罗算法。

创建环境

import gym

import numpy as np

import operator

from IPython.display import clear_output

from time import sleep

import random

import itertools

import tqdm

tqdm.monitor_interval = 0

随机策略函数

def create_random_policy(env):

policy = {}

for key in range(0, env.observation_space.n):

current_end = 0

p = {}

for action in range(0, env.action_space.n):

p[action] = 1 / env.action_space.n

policy[key] = p

return policy

状态行动值储存库

def create_state_action_dictionary(env, policy):

Q = {}

for key in policy.keys():

Q[key] = {a: 0.0 for a in range(0, env.action_space.n)}

return Q

游戏运行函数

def run_game(env, policy, display=True):

env.reset()

episode = []

finished = False

while not finished:

s = env.env.s

if display:

clear_output(True)

env.render()

sleep(1)

timestep = []

timestep.append(s)

n = random.uniform(0, sum(policy[s].values()))

top_range = 0

for prob in policy[s].items():

top_range += prob[1]

if n < top_range:

action = prob[0]

break

state, reward, finished, info = env.step(action)

timestep.append(action)

timestep.append(reward)

episode.append(timestep)

if display:

clear_output(True)

env.render()

sleep(1)

return episode

测试策略并显示胜利百分比的函数

def test_policy(policy, env):

wins = 0

r = 100

for i in range(r):

w = run_game(env, policy, display=False)[-1][-1]

if w == 1:

wins += 1

return wins / r

蒙特卡罗估计和控制第一遍历

def monte_carlo_e_soft(env, episodes=100, policy=None, epsilon=0.01):

if not policy:

policy = create_random_policy(env) # Create an empty dictionary to store state action values

Q = create_state_action_dictionary(env, policy) # Empty dictionary for storing rewards for each state-action pair

returns = {} # 3.

for _ in range(episodes): # Looping through episodes

G = 0 # Store cumulative reward in G (initialized at 0)

episode = run_game(env=env, policy=policy, display=False) # Store state, action and value respectively

# for loop through reversed indices of episode array.

# The logic behind it being reversed is that the eventual reward would be at the end.

# So we have to go back from the last timestep to the first one propagating result from the future.

for i in reversed(range(0, len(episode))):

s_t, a_t, r_t = episode[i]

state_action = (s_t, a_t)

G += r_t # Increment total reward by reward on current timestep

if not state_action in [(x[0], x[1]) for x in episode[0:i]]: #

if returns.get(state_action):

returns[state_action].append(G)

else:

returns[state_action] = [G]

Q[s_t][a_t] = sum(returns[state_action]) / len(returns[state_action]) # Average reward across episodes

Q_list = list(map(lambda x: x[1], Q[s_t].items())) # Finding the action with maximum value

indices = [i for i, x in enumerate(Q_list) if x == max(Q_list)]

max_Q = random.choice(indices)

A_star = max_Q # 14.

for a in policy[s_t].items(): # Update action probability for s_t in policy

if a[0] == A_star:

policy[s_t][a[0]] = 1 - epsilon + (epsilon / abs(sum(policy[s_t].values())))

else:

policy[s_t][a[0]] = (epsilon / abs(sum(policy[s_t].values())))

return 策略

现在使用下列算法解决一个8x8的冰湖环境问题然后查看奖励。

运行这个游戏50000次，我们可以得到0.9分，如果运行更多次，最终我们可以得到最佳方案。

5.总结

蒙特卡罗学习的内容还有很多，此外还有另一套算法称为无策略蒙特卡罗方法。无策略方法是通过使用另一个策略中的return来尝试找出最佳策略。

在本文中讨论的方法都是基于策略的，就如同一边工作一边学习一样。相反，无策略方法就像通过看着别人做从而学习。

编译组：何卿妍、韦振琛

相关链接：

https://www.analyticsvidhya.com/blog/2018/11/reinforcement-learning-introduction-monte-carlo-learning-openai-gym/

如需转载，请后台留言，遵守转载规范