Unlike the previous chapter, here we do not assume complete knowledge of the environment. Monte Carlo methods require only experience—sample sequences of states, actions, and rewards from actual or simulated interaction with an environment. Learning from actual experience is striking because it requires no prior knowledge of the environment’s dynamics, yet can still attain optimal behavior.
Monte Carlo Prediction
蒙特卡洛预测是利用蒙特卡洛方法的最简单的强化学习算法，通过给定的policy进行模拟，并根据模拟episodes来进行state-value期望计算。
这里要注意的是，预测分为first-visit和every-visit，前者是本章讲述的重点，后面其他的算法也都是first-visit的，它的意思是指模拟过程中只对一次状态s计算return，
换句话说episode中只能存在一个s，如果存在多个s的episode这种方法就会直接舍弃；
后者会在后面章节讲述，every-visit会对episode中所有s的return进行计算。
first-visit的Monte Carlo预测伪代码：
Monte Carlo Estimation of Action Values
看了网上的一些解释，如果是model-free的强化学习问题，都是要学习Q(s,a)的，只有model-based的方法可以直接学习v(s)。
其实感觉model-free是一种更普适的方法，因为一个一般的决策问题如果知道行为带来的value的话决策起来就会很舒服，直接greedy action嘛。
但是如果我对环境有一些了解，比如像MDP中那样使用model-based的学习方法，知道状态间的转移概率p(s,a)，那么我在训练的过程中不同step对应的state可以通过动态规划联系在一起，即state和following states之间并没有通过action来连接。那么我在学习的时候就不用去考虑不同的action导致的Q(s,a)，具体的算法可以参考前面MDP的post。那我自然只通过建立v(s)就够了。
这里关于如何建立action-value有一点需要注意：在MDP问题中，每个state都会被更新，所以是不需要maintain exploring的；但是对于action来说，如果采用完全greedy的policy的话，所有的action不一定都会选中，这个问题和第2章的Bandit问题一样，所以需要在greedy policy之外保持一种exploring的策略。于是这里便引入了exploring start的方法，即每次episode的初始state-action会保证所有的state-action对都有概率被选中。
Monte Carlo Control
蒙特卡洛控制通过上一章提到的GPI(generalized policy iteration)的思路来解决的。就是控制环保有一个近似的value function和一个近似的policy，the value function is repeatedly altered(改变) to more closely approximate the value function for the current policy, and the policy is repeatedly improved with respect to the
current value function.GPI的流程可以简单理解为下图：
这个地方和上一章DP算法提到的policy Iteration和value Iteration原理是一致的就不多赘述了。下面看一下基于ES(exploring start)的Control方法：
Monte Carlo Control without Exploring Start
Exploring start的假设在实际问题中不是很常见，所以这一部分提出了两个without exploring start的控制方法：on-policy和off-policy的。
首先需要了解on和off-policy之间的区别和联系：
off-policy是通过behavior policy来模拟并产生数据(episode)，但是学习得到的是target policy π，即使用的episode is “off” the target policy π；
on-policy则在模拟数据和学习时都使用同一个policy。一般来说on-policy更简单易用，off-policy则会有更多的参数和更复杂的学习过程，收敛起来也比较慢，但是off-policy可以适的范围更广，可以更好的解决问题。而且如果off-policy的behavior policy = target policy，二者就一致了。
这一部分主要讨论了on-policy的控制方法，先看一下算法的伪代码：
算法提升原理如下所示，这里的q(s,π’(s))指的是在π’策略下的s的state-value。π’是上面伪代码中的ε-greedy策略。
Off-policy Prediction via Importance Sampling
behavior policy vs target policy
关于target policy π cover behavior policy b的概念，这里什么才能被称为cover(覆盖)那？
文中解释是这样的：通过π选取的action一定有概率通过b选取，即通过π(a|s)>0一定可以推出b(a|s)>0，前者是后者的充分条件。
what is importance sampling
重要取样(Importance Sampling)的推导是通过MDP得到的，它是一种off-policy方法中通过behavior policy来训练target policy的重要途径，其中一个重要的概念就是重要取样比率(importance-sampling ratio)，它的定义式是target policy下的状态轨迹的π(a|s)和behavior policy下的状态轨迹的b(a|s)的比值。具体推导如下：
首先定义通过behavior policy取样得到的states-chain的联合概率，这里的进一步计算使用了马尔科夫独立性假设：
然后给出重要取样比率的定义：
其中的状态转移概率p被消去了，可以证明这个结论虽然是通过马尔科夫独立性推出的，却具有一般性。
好了，现在我们基本理解了重要采样比率的概念，那么它到底有什么用那？下面的公式解释了这个问题（具体推导不清楚QAQ）：
这个值是联系episode的return和target policy π下的v_π(s)的关键！
所以很直观的从这个期望公式引出ordinary importance sampling：
但是有一个问题，就是如果重要采样因子有可能是方差无限的，这时我们近似得到的state-value就会发散而无法收敛，这个问题很严重，随后也会通过代码来解释。
所以通过对采样因子做归一化，引出了Weighted importance sampling的概念：
和前者相比，虽然weighted importance sampling是有偏的(bias)，因为它不是直接从上面的期望公式来的，但是经过多次迭代bias会趋于0。但是如果采样因子的方差不是有限的，
ordinary importance sampling就很有可能无法收敛，也就是说它的方差(variance)是高于weighted importance sampling的，所以总的来说后者更常用。
Incremental Implementation for Off-policy Prediction
增量算法实现和第2章的增量实现原理类似，先给出简单的证明：
设V_n是模拟过程中第n对(s,a)，G1，G2,…Gn是behavior policy产生的对应第n对(s,a)的return，则有下述表达式成立:
额感觉翻译的不够好，粘一下原文吧：
Suppose we have a sequence of returns G1 , G2 , . . . , Gn−1 , all starting in the same state and each with a corresponding random weight Wi (e.g., Wi = ρ_{t:T(t)−1} ). We wish to form the estimate:
增量形式表达式:
其中：
紧接着给出预测的增量形式伪代码：
Off-policy Monte Carlo Control
这一章脉络很清晰啊，基本是先阐述预测算法，再讨论控制算法。这种方法在本书中很常见，因为policy的improve，还是control算法都是建立在predict(or evalution)的基础上的，再加上greey的policy提升方法得到的。下面给出off-policy的增量控制算法：
针对这个算法有几点想讨论的：
1、b是soft-policy的，soft是指b在生成模拟过程的时候对所有的状态动作对的发生概率都不为0，即可以尽可能多的产生不同的过程，相当于一种exploring吧。原文解释是：
policy π is soft, meaning that π(a|s)>0 for all s and a. ε-soft policy is defined as policies for which π(a|s) ≥ ε/|A(s)| for all states and actions, for some ε > 0
2、如果使用π(St)得到的action和episode中的At不同，那么重要采样因子的分子是为0的，此时不对W进行更新。