两个问题
强化学习的算法需要利用值函数$v(s), q(s, a)$解决两个基本问题：
预测问题(prediction problem)：评估当前策略 $\Leftarrow$ 估计状态值函数；
控制问题(control problem)：寻找最优策略 $\Leftarrow$ 估计动作值函数，迭代进行策略改进，直到值函数收敛。
基于模型
基于模型指的是状态转移概率$p(s’ | s, a)$和回报值函数$r(s’, s, a)$均是已知的情况，在这种情况下，利用状态值函数对当前策略进行评估，再利用动作值函数进行策略改进，直到策略最优。动态规划就是依据上述思路进行最优策略寻找。
状态值函数和动作值函数分别如下：
动态规划
动态规划是一个理论上比较完美的模型，因为它的前提是模型已知。基于这个前提，迭代进行策略评估和策略改进这两个步骤，直到收敛，根据表达式(1)可以看到，当前状态值函数的计算需要用到其他状态(这里是下一个时刻的状态)的状态值信息，这种思想统称为自举(bootstrapping)，这是动态规划算法的共同特性。具体实现时有下列三种形式。
a. 策略迭代
从上图可以看到，策略评估部分要求所有状态$s$的状态值均在 $\theta$范围内收敛，收敛后才会进入到策略改进部分。策略改进时同样要求对所有状态进行改进，直到策略在所有状态下均是最优的，否则重新开始策略评估，这个过程可以通过如下示意图描述：
策略评估时，当对所有状态完成了一遍评估时，称为一个$sweep$，为了让所有状态的评估值收敛，需要许多的$sweeps$，这正是策略迭代的一个缺点：策略改进必须等待策略评估收敛才能进行，造成改进速度慢；另一个缺点在于策略改进是针对所有状态同步进行的，这同样导致了改进速度较慢。
b. 值迭代
上图的算法可以通过如下示意图描述：
可以看到，值迭代改善了策略迭代的一个缺点：它只进行了一次策略评估，不要求收敛，而且隐藏在策略改进过程中。可以这样来理解这里的关键字”一次”和”隐藏”，算法中核心的语句是:
这里的$a \in A(s)$，同样的，有$\pi(s) \in A(s)$，当对于固定的一个状态$s$，遍历所有可能的动作$A(s)$时，必然会遍历到动作$\pi(s)$，此时表达式(2)中求和部分正好是状态值函数$v_{\pi}(s) = q_{\pi}(s, \pi(s))$，因此进行了一次策略评估，然后在执行贪婪改进策略$max_a$时，状态值函数隐藏在其中参与了最大值操作的比较，结束一个状态的策略改进过程。值迭代的优点是收敛速度快。
c. 一般策略迭代
一般策略迭代的特点是非常灵活：策略迭代过程的次数和针对的状态可以根据问题决定，同时策略改进时可以只针对部分状态进行改进更新。一般应用在环境状态数十分巨大的高维情况，加快策略迭代的收敛速度。
模型无关
基于模型的算法的两个前提假设：状态转移概率$p(s’ | s, a)$和回报值函数$r(s’, s, a)$是已知的。这两个假设在实际情况中往往不能够满足，于是model-free的算法应用而生，这些算法的共同点在于：
1.不需要模型的信息；
2.需要智能体跟环境进行交互获得经验样本（$ S_t, A_t, S_{t+1} $）
蒙特卡罗控制
蒙特卡罗控制(MC)与动态规划的思路一样，智能体与环境交互采样获得样本，从而估计出状态值函数和动作值函数，前者需要经验样本$(s, r)$，后者需要$(s, a, r)$。MC估计值函数的方法是求回报值的平均值，为了求平均值的方便，将MC控制在场景(episode)任务中：即无论起始状态是什么，总能够在有限次状态转移后到达终止状态。
计算回报值的平均值有两种方式：First-visit MC和Every-visit MC。对于一个状态$s$，前者找到所有episode中第一次访问到$s$或$(s, a)$[针对动作值函数估计]后一直到终止状态前的回报值求平均，而Every-visit MC则再找到所有episode中所有访问到$s$或$(s, a)$后一直到终止状态前的回报值求平均。这两种方法均随对状态$s$的(第一次)访问次数接近无穷而收敛。
根据大数定理，在episode接近无穷时，MC预测的值函数逼近真实值，因此蒙特卡罗方法是无偏的(unbiased)，但是采样过程的随机性带给MC方法比较大的方差(variance)，但是，因为MC方法进行值函数的估计周期是episode-by-episode的，因此值函数的评估和改进也是以episode为周期，因此不支持step-by-step形式的增量计算（incremental computation）方式，如果episode的Trajectories非常长，会出现两个问题：评估周期变长；需要很大的存储空间来记录相同状态下的历史回报值，求平均值的计算时间也会增加。而通过增量计算的方式，将累加后求平均值的方式转换为step-by-step的计算方式，评估更新周期缩短且计算量减少。
1. MC
上图是First-visit MC进行状态值函数的算法流程，动作值函数$q_{\pi}(s, a)$的估计采用同样的方式求平均值。
用上述方法估计值函数时，存在两个前提假设：
a. 所有的状态、动作对$(s, a)$均能够访问到；
b. 进行无穷多次的epsilon
第一个前提条件是确保动作值函数的估计覆盖所有的$(s, a)$，这样才能够在策略改进时进行更优动作的选择。为了保证第一个前提假设成立，需要对动作进行持续探索，两种常见的方法是：探索起点条件和$\epsilon$-贪婪策略；
2. MC with exploring start
探索起点(Exploring Start)条件是指在估计动作值函数时，人为的确定所有episode的起始点$(S_0, A_0)$，从而保证所有的(状态，动作)对出现的概率大于0。但是实际应用中初始环境的选择有时候不能人为确定，导致一部分动作仍然可能不会出现。
针对持续探索更一般的方法是让智能体能够持续不断的选择所有可能的动作。两种方法：在策略（on-policy）方法和离策略（off-policy）方法。这两种方法的区别在于生成episode的策略（行为策略 behavior policy）是否和评估并改进的策略（估计策略 estimation policy）相同。若为同一个策略，则称为on-policy方法；否则为off-policy方法，离策略方法的好处在于可以用一个随机性的策略保证所有可能的动作都能够持续的采样到，同时评估和改进的策略可以是不同的确定性策略（比如贪婪策略：每次取值函数最大的动作进行策略改进）
3. MC with $\epsilon$-greedy
$\epsilon$-贪婪策略是on-policy方法的一种。它不对初始状态做任何规定，而是从策略上保证所有的动作都会出现。假设状态$s$下能够取的动作为$A(s)$，记$|A|$表示集合$A(s)$中元素的个数，则$\epsilon$-贪婪策略在策略改进阶段设置非最优动作的概率$\pi(a|s)$为$\epsilon \over |A|$，最优动作的概率为$\pi(a^{\star} | s) = 1 - \epsilon + {\epsilon \over |A|}$。在产生一系列的episode时，逐渐将初始较大的$\epsilon$减少至0，这样就保证了在开始的episode中非最优动作出现的概率较大，越到后面的epsilon则最优动作会出现的越频繁，从而保证所有的$(s, a)$对的动作值函数能够有效的收敛。
4. 0ff-policy MC
离策略给予我们更大的自由：改进和更新的策略$\pi$可以不同于生成episode的行为策略$\mu$。前者依旧可以是确定性策略，同时后者保证所有可能的动作都会出现在episode中。使用离线策略的MC时，选择行为策略$\mu$有比较大的自由，但是必须满足一个约束条件：
这个条件是为了保证目标策略$\pi$下的所有动作$\pi(\cdot | s)$都会出现在策略$\mu(\cdot | s)$下，从而保证对目标策略进行改进和更新。这个约束条件也就意味着行为策略$\mu$只能是随机性策略，比如常见的$\epsilon$-贪婪策略。
在on-policy的情况下，因为行为策略$\mu$和估计策略$\pi$是同一个策略，因此直接利用episode中对应状态下的回报值平均值作为$v_{\pi}(s)$的无偏估计。但是在off-policy的情况下，因为策略$\mu, \pi$的不同，导致在相同状态下的动作分布是不同的：$\mu(a | s) \ne \pi(a | s)$，因此$\mu$策略产生的episode中的回报值平均值是$v_{\pi}(s)$的有偏估计。为了解决这个问题，需要考虑同一状态在两个策略下的相对概率：
中间那一步化简到最后一步是因为状态转移概率分布$p(S_{t+1} | S_t, A_t)$是由环境决定的，不同策略下保持不变。利用这个比值对多个episode中同一状态下的回报值加权求和，得到$v_{\pi}(s)$的无偏估计：
$$
V(s) = {{\sum_{i=1}^{n_s} {p_i(s) \over p'_i(s)} G_i(s)} \over {\sum_{i=1}^{n_s} {p_i(s) \over p'_i(s)}}}
$$
其中$G_i(s)$表示第$i$个episode中状态$s$所观察得到的回报值。具体的算法流程如下图所示：
算法中需要说明地方是：(b)步骤中算法从episode后面往前寻找第一个满足$A_{\tau} \ne \pi(S_{\tau})$的时间点$\tau$，也就意味着$\tau + 1, \ldots, T$时刻的状态总是满足$A_{\tau} = \pi(S_{\tau})$，这等价于$\pi(A_t | S_t) = 1, t = \tau, \ldots, T-1$，因此在步骤(c)中求$W$时累乘的分数中分子为1的原因。
参考文献
1、Richard S. Sutton. Reinforcement learning An introduction. Second edition. MIT Press;