概述

蒙特卡罗方法(Monte Carlo Methods)是强化学习中基于无模型的训练方法。与动态规划(Dynamic Programming)不同，该方法并没有明确的模型(即transition-state probability)，也就是说我们并不知道各个状态之间转换的概率，可以把它看作是环境(environment)模型。

那么，没有了环境模型，蒙特卡罗方法是如何进行学习的呢？其答案很容易想到，就是通过采样来逼近真实的环境模型。下面，我们就来讲述基于蒙特卡罗方法的state value和action value的预测和判断。

蒙特卡罗预测(Monte Carlo Prediction)

蒙特卡罗预测的目的是来预测状态值(state value)。因为蒙特卡罗方法是通过采样来进行学习的，因此，基础的approximate环境模型的方法有两种，分别为The fist-visit MC method和The every-visit MC method。

The fist-visit MC method和The every-visit MC method

该两种方法本质上的区别其实就在于first和every的区别。在训练强化学习过程中，我们通过强化学习可以很多数据，这些数据就是一个个的试验(experience)，如下图所示：

试验数据

红色的实心点表示他们的状态都相同，但reward值不同。The first-visit method就是只计算每次试验中，第一次出现该状态对应的reward值，将其求和之后求平均值，即为该state的return。而The every-visit method则是将每个试验中出现的红色实心点的reward都相加起来求平均。例如fist-visit return和every-visit return计算公式如下：

计算公式1

因为，蒙特卡罗方法是将所有试验采样求平均值，因此是没有偏差的，其方差为根号试验visit数量分之1。

蒙特卡罗估计动作值(Monte Carlo Estimation of Action Values)

在有模型的强化学习中，因为我们知道各个状态之间转换的概率，因此，我们只需要计算state value值即可选出最优的策略。但是，在无模型的强化学习中，即使我们得到了最优的state value值，也就是说我们知道了在该状态下应该转换到哪个状态最好。可是，我们却无法确认应该采取哪个动作最好。因此，在无模型的强化学习中，我们需要通过计算action value的值来得到最优策略，而不是通过state value。

Maintaining Exploration

试验数量是一点一点创造出来的，而在试验中每次采取的行动也是基于相应action value的值。为了保证每一个状态(state)在试验中出现过，同时也为了保持探索性，因此每次采取动作时可以通过下列公式来进行决定：

Maintaining Exploration

蒙特卡罗控制(Monte Carlo Control)

控制，其实就是为了选取到最优策略，如动态规划中的策略迭代。蒙特卡罗控制伪代码如下所示：

蒙特卡罗无探索伪代码

On-policy MC control & Off-policy MC control

下面来讲一讲on-policy和off-policy的区别。其根本区别就是，on-policy是通过一个policy来评估和改善策略(即进行policy evaluation和policy improvement)，而off-policy则是有两个policy，分别负责产生episode和改善策略，这两个policy的名称分别为动作策略(behavior policy)和目标策略(target policy)。On-policy MC control伪代码如下所示：

蒙特卡罗有探索伪代码

Off-policy MC control

该方法中有两个policy，分别为动作策略和目标策略。动作策略主要负责产生试验，通过一定的探索和action value值。而目标策略主要是为了得到最优策略。几乎所有的Off-policy方法都基于了重要性采样(importance sampling)这个概念。重要性采样用来在给定一个概率分布(如采样的样本概率)来去接近另外一个概率分布(如真实数据概率分布)，从而预测真实值。将其应用在Off-policy方法中时，我们首先需要一个重要性采样率(importance-sampling ratio)，公式如下：

重要性采样率公式1

重要性采样率公式2

公式一表示的是在Sk状态下，采取动作Ak之后状态转换到Sk+1的概率。公式2即为我们要计算的重要性采样率，分子为通过目的策略计算的概率分布，分母为动作策略计算的概率分布。因为我们要得到最优的策略，因此是要动作策略的概率分布尽可能的逼近目的策略的概率分布，而重要性采样率我们可以把它理解为动作策略在目的策略的重要程度。而重要性采样有两个计算公式，分别为普通重要性采样(ordinary importance sampling)和加权重要性采样(weighted importance sampling)，公式如下：

普通重要性采样

加权重要性采样

这两种重要性采样的区别在于普通重要性采样是无偏差的，而加权重要性采样是有偏差的，普通重要性的方差是无边界的，而加权重要性采样是有边界的且边界为1。通常，我们往往使用加权重要性采样。

Incremental Implementation

因为要计算action value，我们之前知道的action value的计算公式如下：

action value formula1

从公式可以看出，我们需要额外的内存来存储每一个reward值。同时，也增加了额外的计算量。为此，我们对其进行了进一步的推导，使其减小了内存和计算量，其推导过程如下所示：

action value formula2

将其公式应用于off-policy预测action value中，可得如下伪代码，相应根据蒙特卡罗方法得到最优策略代码如下：

action value estimation

off-policy control

Reference

1. Reinforcement Learning An Introduction

2.强化学习入门 第三讲 蒙特卡罗方法 https://zhuanlan.zhihu.com/p/25743759

3.重要性采样简述 https://blog.csdn.net/philthinker/article/details/80608502

4.蒙特卡洛方法 （Monte Carlo Method) https://blog.csdn.net/coffee_cream/article/details/66972281