Chapter 5 Monte Carlo Methods

蒙特卡洛方法不像前面几章那样假设我们对环境有充分的知识（即知道状态转移概率等），而是从真实的experience或者模拟的experience（只知道state、action、reward）来进行学习。

这不是说MC方法不需要模型，而是模型不像之前几章那样提供足够的先验知识，在这里只用来生成experience。

There we computed value functions from knowledge of the MDP, here we learn value functions from sample returns with the MDP.

1 Policy Evaluation

1.1 state value（5.1）

针对给定的policy，学习state-value function。

其实很简单，首先生成一个序列（比如21点，就是完成一次游戏，游戏中有各个状态和行动，游戏结束时有一个奖励，作为每个状态的奖励），然后将奖励从后向前累加添加到当前时刻状态的list上，最后求平均。

MC方法只需要更新真实的或自己生成的一个序列的states，而不管其它的states，这也是MC相对于DP的一个优势。

1.2 action value（5.2）

在有模型的情况下，有state value就可以得到一个policy；

但是没有模型的情况下，上述并不成立，因此需要计算action value，即q(s,a)$q(s,a)$。

与state value唯一不同的是，现在访问的是state-action pair，而不是state。那么就有一个严重的问题，很多state-action pair将不会访问，因为我们需要在某个state下的所有action中做选择。

那么我们就需要保持探索（这就是第二章k-armed bandit问题），一种方式就是使每对state-action pair的概率都不是0——exploring starts。

但这需要基于两个假设：

1. exploring starts
2. policy evaluation could be done with an infinite number of episodes.

2 Policy Improvement（5.3）

在计算出q(s,a)$q(s,a)$后，按照贪心策略的方式得到策略：

greedy policy：

同样，和DP方法一样，如何知道当前策略采取的行动是否是最优呢？如何改进当前策略呢？这就是policy improvement，假设在状态s下，采取行动a≠πk(s)$a\ne {\pi }_k(s)$，看是否比之前的value大，那么按照贪心策略，我们总能得到更优的策略，原因（证明）如下：

policy improvement theorem：

3 Policy Iteration（5.3-5.7）

3.1 GPI of MC

policy iteration：

3.2 on-policy MC（5.3-5.4）

本章的1.2节讲过，通过计算action value得到策略需要有两个假设：

1. exploring starts

2. policy evaluation could be done with an infinite number of episodes.

   • 我们先来考虑去除第二个假设：infinite number of episodes。

去除无穷episode（游戏从一次开始到结束称为一个episode）次数这个假设有两种方法：

1. 我们对q估计一定不是完全准确的，存在误差，但是这种误差的大小和概率有一个范围，只要我们进行足够多次的episode就可以使范围足够小即可；
2. 不再完全进行一次evaluation（即对所有的state进行估计，一次sweep）后再进行improvement，而是像value iteration那样，将每次evaluation和improvement结合在一起，将value function向qπk$q_{{\pi }_k}$移动（value iteration是直接将最大的行动的value赋给value function，比较极端）。

以下是有exploring starts的MC：

• 再来考虑去除第一个假设：exploring starts

exploring starts的意思是让所有的state-action都有被选中的概率，这很像k-armed bandit问题中保持explore的问题，那么这里一种自然的做法就是用e-greedy来选择state-action pair，如下就是完整的on-policy MC：

e-greedy每次变化都是improvement的理论证明：

3.3 off-policy MC（5.5-5.7）

5.5-5.6是铺垫，5.7正式讲off-policy MC

off-policy（异策略）相对于on-policy（同策略）的区别在于它评估的策略和提升的策略是不同的，西瓜书上这段讲的比较言简意赅，贴出来：

之前讨论的on-policy策略有什么问题呢？显然的一点是，我们不得不采取非optimal的行动来explore所有的行动（为了找到最优策略而保持探索）。一种解决方式就是使用两个策略，一个策略用来学习然后最终成为optimal policy（称为target policy），另一个策略用来生成behavior（称为behavior policy）。

off-policy方法的方差更大，收敛更慢，但是更加powerful、general，on-policy方法是off-policy的一个特例。

• importance sampling（5.5）

那么问题来了，既然要用behavior policy生成behavior，那么这样得到的value是behavior policy的，怎么把它用到target policy上呢？这就是importance sampling，用来建立两个策略直接的关联（importance sampling
ratio）

我们看到两个策略之间的比例只依赖各自在某个状态下采取某个策略的概率，不依赖于转移概率。

有了比例，可以计算target policy下的return（Gt$G_t$是behavior policy下的return）：

展开来有两种方式，ordinary/weighted importance sampling.

ordinary importance sampling（有偏差，方差没有边界，结果可能很极端）：

weighted importance sampling（无偏差，方差低，用的更多）：

• 增量实现（5.6）

为了计算方便，off-policy可以增量实现。

ordinary importance sampling和一般求平均值的增量实现一样。

weighted importance sampling：

• off-policy MC（5.7）

选取target policy为greedy policy，behavior policy为e-greedy policy.

我觉得西瓜书这里讲的更清楚，直接贴西瓜书的算法：

有一个地方有疑惑：

2016年1月第一版的西瓜书第6行是：

与上面有两个地方有差，一个是括号的位置，一个是有无指示函数，感觉各对一半，希望能得到解答。