增强学习（一）

一. 增强学习简介

1.1 什么是增强学习？

机器学习的算法可以分为三类：监督学习，非监督学习和增强学习。 增强学习也称为强化学习。

增强学习就是将情况映射为行为，也就是去最大化收益。学习者并不是被告知哪种行为将要执行，而是通过尝试学习到最大增益的行为并付诸行动。也就是说增强学习关注的是智能体如何在环境中采取一系列行为，从而获得最大的累积回报。通过增强学习，一个智能体应该知道在什么状态下应该采取什么行为。RL是从环境状态到动作的映射的学习，我们把这个映射称为策略。

比如：flappy bird是现在很流行的一款小游戏，不了解的同学可以点链接进去玩一会儿。现在我们让小鸟自行进行游戏，但是我们却没有小鸟的动力学模型，也不打算了解它的动力学。要怎么做呢？ 这时就可以给它设计一个增强学习算法，然后让小鸟不断的进行游戏，如果小鸟撞到柱子了，那就获得-1的回报，否则获得0回报。通过这样的若干次训练，我们最终可以得到一只飞行技能高超的小鸟，它知道在什么情况下采取什么动作来躲避柱子。

增强学习和监督学习的区别是：

1.  增强学习是试错学习(Trail-and-error)，由于没有直接的指导信息，智能体要以不断与环境进行交互，通过试错的方式来获得最佳策略。

2.  延迟回报，增强学习的指导信息很少，而且往往是在事后（最后一个状态）才给出的，这就导致了一个问题，就是获得正回报或者负回报以后，如何将回报分配给前面的状态。

增强学习的一个挑战是exploration和exploitation之间的权衡。

Exploration就是尝试之前没有执行过的动作以期望获得超乎当前最有行为的收益。

Exploitation就是执行根据历史经验学习到的获得最大收益的动作。

1.2 增强学习构成的元素

1.policy 定义为在给定时刻t下，智能体表现的方式。具体来说，policy就是从环境状态到动作行为的一个映射。policy是增强学习的核心。

2.reward function定义为在增强学习问题中的目标。具体来说，reward就是从环境状态到奖励的一个映射。智能体的任务就是在长期的过程中，不断最大化所得的总奖励。注意，这里的reward function指的是单次行为所造成环境状态改变所带来的奖励，所以为即时奖励。这个reward function定义了对智能体来说，什么是对的行为，什么是错误的行为。

3.value function定义为在长期奖励。也就是说是reward function的累加。如果说reward function告诉智能体什么行为是好的坏的，那么value function告诉智能体的是长期以来你的行为是好的还是坏的。

感觉来说，追求最大的reward为第一位，value为第二位。因为没有reward就没有value而言。但是，对于决策动作来说，应该考虑value为第一位因为我们追求的是长期的回报。对于估计reward是很简单的，因为在执行完当前任务之后，就马上能获得回报。但是对value来说，回报需要经过一段时间的动作执行才能够得到。所以，value estimation是增强学习一个核心的内容。

虽然增强学习的核心是value estimation，但是也有例外的情况，这就是进化算法。进化算法直接在策略空间搜索最优策略，对于策略空间较小或者易于求出策略空间的情况下，进化算法是有效的，另外当环境状态无法准确感知的情况下，进化算法具有优势。

4. a model of environment定义为对环境行为的模拟。比如说，给定state和action，我们要估计下一个时刻的state和reward，这时候就需要model of environment作出预测。

二. 可衡量的反馈(Evaluative feedback)

2.1 多臂老虎机问题

在多臂老虎机问题中，每个行为有个对应的期望或者平均reward，我们称这个为value of this action。如果你知道每个行为所对应的value，那么每次试验你都会选择对应最大value的那个行为。但是我们假设你不知道每个行为所对应的确切的value，但是你可有一个估计的value。

greedy action：如果保持估计value的话，那么在任何时刻都至少有一个action拥有最大的value。那么每次执行这个对应最大估计value的action，称为greedy action。

Exploitation:每次选择行为时选择greedy action。

Exploration:每次选择行为时选择non-greedy action。

exploitation是正确的事，因为它每次都尝试去最大化value的值，但是从长期来看，exploration可能会比exploitation带来更大的收益。所以，需要在exploitation和exploration之间找到一个平衡。

2.2 Action-Value Method

声明：Q*(a)表示action的真实值， Qt(a)表示action的估计值。

如何action a被执行k次，并且得到reward是r1,....,rk，那么估计值就是

Qt(a) = (r1+r2+...+rk) / k

如果k=0，那么Qt(a) = 0； 如果k=∞，那么Qt(a)=Q*(a)

eplison-greedy methods：在大多数的时间内使用exploitation,在eplison概率的情况下使用exploration。

eplison-greedy methods的好处取决于任务。如果该行为的value的方差很大，那么可以说eplison-greedy methods最终表现的会比greedy methods好。如果该行为的value的方差为0，那么可以说greedy methods更好，因为它每次都是执行最大value的行为。

2.3 Soft-max Action Selection

eplison-greedy methods虽然有很多的好处，但是一个缺点就是在exploration的时候，选择每个action的概率是一样的。那么就是说，它很可能会选到一个最烂的action。soft-max action selection就是基于对这种情况的考虑，在exploration的时候，还是给greedy action最大的概率，其他的action根据其value的大小，按概率进行选择。也就是说，最烂的行为被选到的概率是最小的。

2.4 Evaluation Versus Instruction

evaluative-feedback:当执行完一个行为后，得到的reward只是反映出你这个行为有多好，但是没有一个明确的表态说你这个行为是正确的还是错误的。

instructive-feedback:当执行完一个行为后，它会告诉你这个行为是正确的还是错误的。所以在选择行为的时候，就选择在多大数时间内提醒的是正确的动作。这种方法也被称为supervised learning。

比如有100个行为，你选了第32号行为，那么evaluative-feedback会告诉你，你的score是7.2，那么instructive-feedback会说67号行为可能才是正确的行为。

2.5 Incremental Implementation

Qt(a) = (r1+r2+...+rk) / k 计算Qt(a)的话，要存好多的r1到rk的值，那么随着时间的增长，需要的计算量和内存都很大。那么Qt(a)可换一种方式表达：那么，可以表达为：

new estimate = old estimate + (target - old estimate) / step size

target - old estimate = error 

step size随着k改变，从这个式子同样可以看出，当k趋近于无穷大的时候，这个error就很小，那么old estimate就几乎约等于new estimate，也就是说收敛了。

2.6 Tracking a Nonstationary Problem

上面所讨论的问题都是基于恒定的，假设多臂老虎机的action所对应的值不是恒定的，是变化的，那又该如何处理。一个最典型的做法就是将step size设置为常数，因为2.4的公式中，step size是随着执行k次action而变化的。其中， alpha为step-size，是0-1之间的取值。这导致Qk为过去所得到的所有reward的weighted平均值和Q0.

因为

所以称为weighted average。

2.7 Optimistic Initial Values

所有我们之前讨论的方法都在一定程度上依赖于初始动作的值。初始动作值可以作为一种简单的手段来鼓励explore.

比如，多臂老虎机的问题，我们设置每个动作的初始估计值为5而不是0，动作的真实值是服从0，1正态分布。 那么无论你一开始选择哪个动作，反馈总是小于初始估计值。那么，这种优化机制会鼓励去explore，因为每次动作的执行，都会让智能体很失望，因为真实值和估计值总是相差很大。所以即使是采用greedy的方法，那也会采取不同动作n次，直到估计值收敛。这个初始化方法对于stational的问题会鼓励explore并且有效，但是对于nonstational的问题，就并能得到很好的效果。

2.8 Reinforcement Comparison

从直觉来说，一个动作能带来更大的reward应该多执行些，带来更小的reward应该少执行些。但是，怎么样才知道一个动作带来的reward是更大还是更小呢？这时候就需要和一个标准水平对比reward，叫做reference reward。reference reward通常来说就是前k个动作的带来的reward 的平均值。

Reinforcement Comparison：就是一个基于下列想法的方法：当一个动作带来比reference reward更大的reward，那么就说这个reward更大。反之亦然。

所以该方法选择action不是基于对value的估计，而只是计算一个均值。对某个动作的偏好可以用softmax表示：

该式子表示在t时刻选择action a的概率。

pt(a)表示在t时刻，对action a的偏好程度。该偏好程度可通过下列公式进行更新：

Belta是一个正的step size参数。rt是即时reward，r-t是reference reward。从这个式子可以看出来，当action带来reward更大的时候，那么选择该action的概率就会增大。反之亦然。

reference reward的更新通过下面这个公式进行：alpha是在于[0,1]之间取值的step size的参数。

2.9 Pursuit Methods

Pursuit Methods：这个方法是action-value和action preference的结合。该思想是不断的‘pursuit’ greedy action（就是Q最大的那个action）然后通过action preference来更新对该action的偏好。

对该greedy action选择的概率的更新如下：

对其他的action选择的概率的更新如下：

对Q的更新同value-action的方法。

2.10 Associative Search

到目前为止，我们还没考虑过一种情况，那就是不同动作要对应不同的情况。我们考虑的都是在task是stationary的时候，采取单一最优动作，或者在task是nonstationary的时候采取一系列最优动作以满足环境的变化。但是，在通常的强化学习任务中，设计到的环境变化往往不是单一的，所以我们要让智能体学会如何在不同的环境中，采取不同的动作。

还是老虎机的例子，你可能面对n个赌博臂，如果每次变化是随机的，那你面对的是单一的nonstationary的问题，如果每次变化是固定的，那你面对的是单一的stationary的问题。那么，能不能换个复杂点的情况。就是每当你选择不同的赌博臂的时候，老虎机的提示灯颜色变化不同，这个可以作为你选择赌博臂的一个提示。比如说，所学到的结果是，当是红色提示灯的时候，选择1号赌博臂，当时黄色提示灯的时候，选择2号赌博臂。所以，这个是强化学习更典型的一个问题。因此，这时候会需要state表示你周围的环境，将其与action联系起来。在接下来的一章会展开介绍。

三. 马尔可夫链

3.1 The Agent-Environment Interface

agent：学习者和决策者

environment：除了agent之外的任何一切

state：环境的抽象表达

policy：agent会生成一个从state到选择action的概率的一个映射，这个映射为policy。

3.2 Goals and Rewards

reward：要设置为我们想达到的目标。如果agent为我们的目标做出了行动，那么就应该给它奖励。明确的是，这个奖励的信号应该定义为你想要达成的目标是什么，而不是告诉它如何去达成这个目标，比如设置子任务之类的。所以来说reward和goal是相连的，我们的goal决定了reward的定义。

3.3 Returns

Return 的无限表达：简单地，我们可以将return定义为reward的和：episodic tasks：在任务中，有一个自然的表示任务终结的时间点，我们把这个开始到结束的一个过程称为episode，比如说一盘游戏的结束，一盘棋的结束等。每个episode结束的那个特殊的state称为terminal state。所有的nonterminal state的集合用S表示，含有terminal state的S用S+表示。episodic tasks能应用上面定义的return。

continuing tasks：但是不同于episodic tasks，有的任务并没有自然的终止过程。比如一个任务需要贯穿一个agent的一生。所以对于这种任务而言，终止时间T=∞。所以，对于return来说，很有肯能就是∞，假设定义r为1.

Return的有限表达：discount rate决定了未来reward在当前的价值。如何r<1，那么一个无限的和就会有一个有限的值。如果r=0，那么agent是鼠目寸光的，只关心当前reward的最大回报就好。如果r趋近于1，那么agent是很有远见的，未来reward对当前价值的影响越大。

3.4 Unified Notation for Episodic and Continuing Tasks

S_t,i 表示在时间t，第i个episode的状态。但是因为每个episode的状态具有共性，所以常用S_t代替S_t,i。此表示法同样的道理用于a_t,i, r_t,i等。absorbing state：仅在自身和reward为0之间转换。如上图实心正方形所示。

上图可知，无论是加S0-S2，还是S0-S∞，结果都是3.所以，这个对有限的reward也适用，因为其可以表示为：所以，用这个表示episode和continuing tasks的关系。

3.5 马尔科夫特性

Markov property: 马尔可夫性(无后效性)，也就是指系统的下个状态只与当前状态信息有关，而与更早之前的状态无关。

state： 对agent来说一切有用的外界信息。

Markov：所有的state信号能成功的表示所有相关的信息。

试想下，如果在t的时刻采取的动作，那么在t+1的时刻，环境对行为会产生什么反应？所以这个是个动态的过程，用数学可表示为：但是，如果这个state符合马尔科夫特性，那么在t+1时刻的反应仅仅依赖于t时刻的state和action。甚至在一些不符合马尔科夫的state里，我们可以认为它们近似于马尔科夫特性。

3.6 马尔科夫决策过程

Markov decision process（MDP）：符合马尔科夫特性的增强学习任务叫做马尔科夫决策过程。与上面不同的是MDP考虑了动作，即系统下个状态不仅和当前的状态有关，也和当前采取的动作有关。举下棋的例子，当我们在某个局面（状态s）走了一步(动作a)，这时对手的选择（导致下个状态s’）我们是不能确定的，但是他的选择只和s和a有关，而不用考虑更早之前的状态和动作，即s’是根据s和a随机生成的。

Hidden Markov Model（HMM）:它用来描述一个含有隐含未知参数的马尔可夫过程。

www.cnblogs.com/skyme/p/4651331.html

finite Markov decision process：如果state和action的空间是有限的，那么称为有限的马尔科夫决策过程。

给定state St和action a，下一个状态St+1的概率是：

给定state St和action a，下一个状态reward的是：3.7 Value Functions

State-value function:

the value of a state under a policy, denoted Vpai(s)

Action-value function:

在Qπ(s,a)中，不仅策略π和初始状态s是我们给定的，当前的动作a也是我们给定的，这是Qπ(s,a)和Vπ(a)的主要区别。

例子：

blog.csdn.net/zz_1215/article/details/44138823

3.8 贝尔曼方程（Bellman Equation）

Bellman equation：

Vπ(s,a)和Qπ(s,a)这两个式子称为贝尔曼方程，它表明了当前状态的值函数与下个状态的值函数的关系。optimal policy: 当且仅当一个policy比之前的policy所带来的Value相等或者更好，这个policy称为最优policy。

optimal state-value function：optimal action-value function：

四. 动态规划

增强学习的目的就是求解马尔可夫决策过程(MDP)的最优策略，使其在任意初始状态下，都能获得最大的Vπ值。(本文不考虑非马尔可夫环境和不完全可观测马尔可夫决策过程(POMDP)中的增强学习)。那么如何求解最优策略呢？基本的解法有三种：动态规划法(dynamic programming methods)，蒙特卡罗方法(Monte Carlo methods)，时间差分法(temporal difference)。动态规划法是其中最基本的算法，也是理解后续算法的基础。

动态规划是一种通过把复杂问题划分为子问题，并对自问题进行求解，最后把子问题的解结合起来解决原问题的方法。「动态」是指问题由一系列的状态组成，而且状态能一步步地改变，「规划」即优化每一个子问题。因为MDP 的 Markov 特性，即某一时刻的子问题仅仅取决于上一时刻的子问题的 action，并且 Bellman 方程可以递归地切分子问题，所以我们可以采用动态规划来求解 Bellman 方程。

优化目标：

4.1 Policy Evaluation

policy evaluation:  对于任意的policy，计算state-value function。

对于确定性策略，值函数：

扩展到更一般的情况，如果在某策略π下，π(s)对应的动作a有多种可能，每种可能记为π(a|s)，则状态值函数定义如下：

一般采用迭代的方法更新状态值函数，首先将所有Vπ(s)的初值赋为0（其他状态也可以赋为任意值，不过吸收态必须赋0值），然后采用如下式子更新所有状态s的值函数（第k+1次迭代）：

对于Vπ(s)，仅用一个数组保存各状态值函数，每当得到一个新值，就将旧的值覆盖,形如[Vk+1(s1),Vk+1(s2),Vk(s3)..]，第k+1次迭代的Vπ(s)可能用到第k+1次迭代得到的Vπ(s')。更新算法如下：

4.2 Policy Improvement

Policy Improvement：上一节中进行策略估计的目的，是为了寻找更好的策略，这个过程叫做策略改进。

假设我们有一个策略π，并且确定了它的所有状态的值函数Vπ(s)。对于某状态s，有动作a0=π(s)。 那么如果我们在状态s下不采用动作a0，而采用其他动作a≠π(s)是否会更好呢？要判断好坏就需要我们计算行为值函数Qπ(s,a)。

评判标准是：Qπ(s,a)是否大于Vπ(s)。如果Qπ(s,a)> Vπ(s)，那么至少说明新策略【仅在状态s下采用动作a，其他状态下遵循策略π】比旧策略【所有状态下都遵循策略π】整体上要更好。

策略改进定理(policy improvement theorem)：π和π'是两个确定的策略，如果对所有状态s∈S有Qπ(s,π'(s))≥Vπ(s)，那么策略π'必然比策略π更好，或者至少一样好。其中的不等式等价于Vπ'(s)≥Vπ(s)。

有了在某状态s上改进策略的方法和策略改进定理，我们可以遍历所有状态和所有可能的动作a，并采用贪心策略来获得新策略π'。即对所有的s∈S, 采用下式更新策略：

这种采用关于值函数的贪心策略获得新策略，改进旧策略的过程，称为策略改进(Policy Improvement)。

4.3 Policy Iteration

策略迭代算法就是上面两节内容的组合。假设我们有一个策略π，那么我们可以用policy evaluation获得它的值函数Vπ(s)，然后根据policy improvement得到更好的策略π'，接着再计算Vπ'(s),再获得更好的策略π''，整个过程顺序进行如下图所示：算法如下：

4.4 Value Iteration

policy iteration的缺点：在每次的policy iteration中，都包含了policy evaluation，因为policy evaluation自身则需要扫描(sweep)所有的状态若干次，其中巨大的计算量直接影响了策略迭代算法的效率。我们必须要获得精确的Vπ值吗？事实上不必，有几种方法可以在保证算法收敛的情况下，缩短策略估计的过程。

Value Iteration：policy iteration的policy evaluation可以被简化以至于不会失去其收敛的保证。Value Iteration就是其中一种简化的办法。它的每次迭代只扫描(sweep)了每个状态一次。值迭代的每次迭代对所有的s∈S按照下列公式更新：

即在值迭代的第k+1次迭代时，直接将能获得的最大的Vπ(s)值赋给Vk+1。值迭代算法直接用可能转到的下一步s'的V(s')来更新当前的V(s)，算法甚至都不需要存储策略π。而实际上这种更新方式同时却改变了策略πk和V(s)的估值Vk(s)。 直到算法结束后，我们再通过V值来获得最优的π。此外，值迭代还可以理解成是采用迭代的方式逼近1中所示的贝尔曼最优方程。

值迭代完整的算法如图所示：

由上面的算法可知，值迭代的最后一步，我们才根据V*(s)，获得最优策略π*。

一般来说值迭代和策略迭代都需要经过无数轮迭代才能精确的收敛到V*和π*， 而实践中，我们往往设定一个阈值来作为中止条件，即当Vπ(s)值改变很小时，我们就近似的认为获得了最优策略。在折扣回报的有限MDP(discounted finite MDPs)中，进过有限次迭代，两种算法都能收敛到最优策略π*。

动态规划的优点在于它有很好的数学上的解释，但是动态要求一个完全已知的环境模型，这在现实中是很难做到的。

4.5 Asynchronous Dynamic Programming（异步动态规划）

动态规划的缺点：在上面讨论过的DP中，它涉及了对所有状态集的扫描。当状态数量较大的时候，动态规划法的效率也将是一个问题。异步动态规划就很好的解决了这个问题。

These algorithms back up the values of states in any order whatsoever, using whatever values of other states happen to be available. The values of some states may be backed up several times before the values of others are backed up once.

4.6 Generalized Policy Iteration

Generalized Policy Iteration：我们使用广义策略迭代（GPI）一词来引用policy evaluation和policy improvement过程互动的一般思路，而不依赖于两个流程的粒度和其他细节。

GPI可表示为如下：

五. 蒙特卡洛方法

蒙特卡罗方法又叫统计模拟方法，它使用随机数（或伪随机数）来解决计算的问题，是一类重要的数值计算方法。该方法的名字来源于世界著名的赌城蒙特卡罗，而蒙特卡罗方法正是以概率为基础的方法。

一个简单的例子可以解释蒙特卡罗方法，假设我们需要计算一个不规则图形的面积，那么图形的不规则程度和分析性计算（比如积分）的复杂程度是成正比的。而采用蒙特卡罗方法是怎么计算的呢？首先你把图形放到一个已知面积的方框内，然后假想你有一些豆子，把豆子均匀地朝这个方框内撒，散好后数这个图形之中有多少颗豆子，再根据图形内外豆子的比例来计算面积。当你的豆子越小，撒的越多的时候，结果就越精确。

现在我们开始讲解增强学习中的蒙特卡罗方法，与上篇的DP不同的是，这里不需要对环境的完整知识。蒙特卡罗方法仅仅需要经验就可以求解最优策略，这些经验可以在线获得或者根据某种模拟机制获得。

要注意的是，我们仅将蒙特卡罗方法定义在episode task上，所谓的episode task就是指不管采取哪种策略π，都会在有限时间内到达终止状态并获得回报的任务。比如玩棋类游戏，在有限步数以后总能达到输赢或者平局的结果并获得相应回报。

那么什么是经验呢？经验其实就是训练样本。比如在初始状态s，遵循策略π，最终获得了总回报R，这就是一个样本。如果我们有许多这样的样本，就可以估计在状态s下，遵循策略π的期望回报，也就是状态值函数Vπ(s)了。蒙特卡罗方法就是依靠样本的平均回报来解决增强学习问题的。

尽管蒙特卡罗方法和动态规划方法存在诸多不同，但是蒙特卡罗方法借鉴了很多动态规划中的思想。在动态规划中我们首先进行策略估计，计算特定策略π对应的Vπ和Qπ，然后进行策略改进，最终形成策略迭代。这些想法同样在蒙特卡罗方法中应用。

5.1 Monte Carlo Policy Evaluation（State Values）

every-visit MC method：Vπ(s)是在所有的episodes里，每次对state s访问产生的所有回报的平均值。

first-visit MC method：Vπ(s)是在所有的episodes里，第一次对state s访问产生的所有回报的平均值。

first-visit MC method的算法如下：

举例如下：

5.2 Monte Carlo Estimation of Action Values

如果模型是不可知的，那么此时去估计action values比state values来的更好。如果模型已知，只要state values就足够了；如果模型未知，只有state values是不够的。因为在状态转移概率p(s'|a,s)已知的情况下，策略估计后有了新的值函数，我们就可以进行策略改进了，只需要看哪个动作能获得最大的期望累积回报就可以。然而在没有准确的状态转移概率的情况下这是不可行的。为此，我们需要估计动作值函数Qπ(s,a)。Qπ(s,a)的估计方法前面类似，即在状态s下采用动作a，后续遵循策略π获得的期望累积回报即为Qπ(s,a)，依然用平均回报来估计它。有了Q值，就可以进行策略改进了

持续探索(Maintaining Exploration)：

下面我们来探讨一下Maintaining Exploration的问题。前面我们讲到，我们通过一些样本来估计Q和V，并且在未来执行估值最大的动作。这里就存在一个问题，假设在某个确定状态s0下，能执行a0, a1, a2这三个动作，如果智能体已经估计了两个Q函数值，如Q(s0,a0), Q(s0,a1)，且Q(s0,a0)>Q(s0,a1)，那么它在未来将只会执行一个确定的动作a0。这样我们就无法更新Q(s0,a1)的估值和获得Q(s0,a2)的估值了。这样的后果是，我们无法保证Q(s0,a0)就是s0下最大的Q函数。

Maintaining Exploration的思想很简单，就是用softpolicies来替换确定性策略，使所有的动作都有可能被执行。比如其中的一种方法是ε-greedy policy，即在所有的状态下，用1-ε的概率来执行当前的最优动作a0，ε的概率来执行其他动作a1, a2。这样我们就可以获得所有动作的估计值，然后通过慢慢减少ε值，最终使算法收敛，并得到最优策略。简单起见，在下面MC控制中，我们使用exploring start，即仅在第一步令所有的a都有一个非零的概率被选中。

5.3 Monte Carlo Control

我们看下MC版本的策略迭代过程：

根据前面的说法，值函数Qπ(s,a)的估计值需要在无穷多episode后才能收敛到其真实值。这样的话策略迭代必然是低效的。在上一篇DP中，我们了值迭代算法，即每次都不用完整的策略估计，而仅仅使用值函数的近似值进行迭代，这里也用到了类似的思想。每次策略的近似值，然后用这个近似值来更新得到一个近似的策略，并最终收敛到最优策略。这个思想称为广义策略迭代。

具体到MC control，就是在每个episode后都重新估计下动作值函数（尽管不是真实值），然后根据近似的动作值函数，进行策略更新。这是一个episode by episode的过程。

一个采用exploring starts的Monte Carlo control算法，如下图所示，称为Monte Carlo ES。而对于所有状态都采用softpolicy的版本，这里不再讨论。

Monte Carlo方法的一个显而易见的好处就是我们不需要环境模型了，可以从经验中直接学到策略。它的另一个好处是，它对所有状态s的估计都是独立的，而不依赖与其他状态的值函数。在很多时候，我们不需要对所有状态值进行估计，这种情况下蒙特卡罗方法就十分适用。

不过，现在增强学习中，直接使用MC方法的情况比较少，而较多的采用TD算法族。但是如同DP一样，MC方法也是增强学习的基础之一，因此依然有学习的必要。

5.4  On-Policy Monte Carlo Control

你估计policy或者value-function的时候，需要用到一些样本，这些样本也是需要采用某种策略（可能固定、可能完全随机、也可能隔一段时间调整一次）生成的。那么，判断on-policy和off-policy的关键在于，你所估计的policy或者value-function和你生成样本时所采用的policy  是不是一样。如果一样，那就是on-policy的，否则是off-policy的。基于experience replay的方法基本上都是off-policy的。

on-policy: On-policy methods attempt to evaluate or improve the policy that is used to make decisions.

epsilon-soft on policy算法如下：

5.5 Off-Policy Monte Carlo Control

off-policy: the distinguishing feature of on-policy methods is that they estimate the value of a policy while using it for control. In off-policy methods these two functions are separated. The policy used to generate behaviour, called the behaviour policy, may in fact be unrelated to the policy that is evaluated and improved, called the estimation policy. An advantage of this separation is that the estimation policy may be deterministic (e.g., greedy), while the behaviour policy can continue to sample all possible actions.

off-policy算法如下：

六. 时间差分学习

对于动态规划算法有如下特性：

1. 需要环境模型，即状态转移概率Psa。需要环境模型指的是，需要环境已知，比如grid的游戏，当前状态已知，并且知道采取哪个动作，那么下一个状态一定是已知的，即你将会出现在grid的哪个格子中。

2. 状态值函数的估计是自举的(bootstrapping)，即当前状态值函数的更新依赖于已知的其他状态值函数。

相对的，蒙特卡罗方法的特点则有：

1. 可以从经验中学习不需要环境模型。不需要环境模型指的是，允许环境位置。比如开车的小游戏，那么仅仅知道你当前的状态和你下一个将要采取的动作，你是不知道下一状态的。因为你可以觉得你自己的状态，可是什么时候你前面会出现一辆车子这个是未知的。所以，这种情况是环境位置，所以需要蒙特卡洛用概率去估计你下一个的状态。

2. 状态值函数的估计是相互独立的

3. 只能用于episode tasks

而我们希望的算法是这样的：

1. 不需要环境模型

2. 它不局限于episode task，可以用于连续的任务

时间差分学习(Temporal-Difference learning, TD learning)正是具备了上述特性的算法，它结合了DP和MC，并兼具两种算法的优点。

6.1 TD Prediction

在介绍TD learning之前，我们先引入如下简单的蒙特卡罗算法，我们称为constant-αMC，它的状态值函数更新公式如下：其中Rt是每个episode结束后获得的实际累积回报，α是学习率，这个式子的直观的理解就是用实际累积回报Rt作为状态值函数V(st)的估计值。具体做法是对每个episode，考察实验中st的实际累积回报Rt和当前估计V(st)的偏差值，并用该偏差值乘以学习率来更新得到V(St)的新估值。不同的是，对于蒙特卡罗算法，必须等到一个episode结束之后才能知道Rt, 但是TD算法只要等到下一个时间点t+1即可获得rt.

所以，最简单的TD方法，即TD(0)：

与MC不同的是，TD(0)用代替了Rt.

为什么修改成这种形式呢，我们回忆一下状态值函数的定义：容易发现MC是利用6.3的形式去估计target，而DP是利用6.4的形式去估计target。The Monte Carlo target is an estimate because the expected value in(6.3) is not known; a sample return is used in place of the real expected return. The DP target is an estimate not because of the expected values, which are assumed to be completely provided by a model of the environment, but because Vpai(St+1) is not known and the current estimate, ,Vt(s+1) is used instead. The TD target is an estimate for both reasons: it samples the expected values in(6.4) and it uses the current estimate instead of the true. Thus, TD methods combine the sampling of Monte Carlo with the bootstrapping of DP. 即利用真实的立即回报rt+1和下个状态的值函数V(st+1)来更新V(st)，这种方式就称为时间差分(temporal difference)。由于我们没有状态转移概率，所以要利用多次实验来得到期望状态值函数估值。类似MC方法，在足够多的实验后，状态值函数的估计是能够收敛于真实值的。

那么MC和TD(0)的更新公式的有何不同呢？我们举个例子，假设有以下8个episode, 其中A-0表示经过状态A后获得了回报0:

首先我们使用constant-ααMC方法估计状态A的值函数，其结果是V(A)=0V(A)=0，这是因为状态A只在episode 1出现了一次，且其累计回报为0。

现在我们使用TD(0)的更新公式，简单起见取λ=1λ=1，我们可以得到V(A)=0.75V(A)=0.75。这个结果是如何计算的呢？ 首先，状态B的值函数是容易求得的，B作为终止状态，获得回报1的概率是75%，因此V(B)=0.75V(B)=0.75。接着从数据中我们可以得到状态A转移到状态B的概率是100%并且获得的回报为0。根据公式(2)可以得到V(A)←V(A)+α[0+λV(B)−V(A)]V(A)←V(A)+α[0+λV(B)−V(A)]，可见在只有V(A)=λV(B)=0.75V(A)=λV(B)=0.75的时候，式(2)收敛。对这个例子，可以作图表示：

可见式(2)由于能够利用其它状态的估计值，其得到的结果更加合理，并且由于不需要等到任务结束就能更新估值，也就不再局限于episode task了。此外，实验表明TD(0)从收敛速度上也显著优于MC方法。

将式(2)作为状态值函数的估计公式后，前面文章中介绍的策略估计算法就变成了如下形式，这个算法称为TD prediction:

6.2 Advantages of TD Prediction Methods

1.  Comparing with DP, TD does not require a model of the environment, of its reward and next-state probability distributions.

2. Comparing with MC, TD is naturally implemented in an on-line, fully incremental fashion. With Monte Carlo methods one must wait until the end of an episode, because only then is the return known, whereas with TD methods one need wait only one time step.

3.  Some Monte Carlo methods must ignore or discount episodes on which experimental actions are taken, which can greatly slow learning. TD methods are much less susceptible to these problems because they learn from each transition regardless of what subsequent actions are taken.

6.3 Optimality of TD(0)

batch updating: updates are made only after processing each complete batch of training data. 假设只能获得有限数量的经验，比如说10个片段或者100个时间步长。在这种情况下，一个通用的增量式学习方法的策略是重复的学习这些经验直到方法收敛到一个答案。给定一个近似值函数V,在每一个时间步长t，当一个非终止状态被访问的时候，由上面的式子计算。但是值函数只更新1次，用所有增量的和。然后重复直到收敛。我们称之为批更新因为更新发生在处理完每一批训练数据之后。

在批更新下，TD(0)确定的收敛到一个答案并且独立于步长参数α，只要α足够小。MC方法也收敛到一个确定的答案，但是是一个不同的解。理解这两个解的不同将有助于我们理解这两种方法的不同。

6.4 Sarsa: On-Policy TD Control

现在我们利用TD prediction组成新的强化学习算法，用到决策/控制问题中。在这里，强化学习算法可以分为在线策略(on-policy)和离线策略(off-policy)两类。首先要介绍的sarsa算法属于on-policy算法。

与前面DP方法稍微有些区别的是，sarsa算法估计的是动作值函数(Q函数)而非状态值函数。也就是说，我们估计的是策略π下，任意状态s上所有可执行的动作a的动作值函数Qπ(s,a)，Q函数同样可以利用TD Prediction算法估计。如下就是一个状态-动作对序列的片段及相应的回报值。

给出sarsa的动作值函数更新公式如下：可见上式与TD(0)的形式基本一致。需要注意的是，对于每个非终止的状态st，在到达下个状态st+1后，都可以利用上述公式更新Q(st,At)，而如果stst是终止状态，则要令Q(st+1=0,at+1。由于动作值函数的每次更新都与(st,at,rt+1,st+1,at+1)相关，因此算法被命名为sarsa算法。

Sarsa的算法如下：

6.5 Q-Learning: Off-Policy TD Control

在sarsa算法中，选择动作时遵循的策略和更新动作值函数时遵循的策略是相同的，即ϵ−greedyϵ−greedy的策略，而在接下来介绍的Q-learning中，动作值函数更新则不同于选取动作时遵循的策略，这种方式称为离策略(Off-Policy)。Q-learning的动作值函数更新公式如下：Q-learning 算法如下：

Sarsa和Q-learning的唯一不同之处不是在于动作的选取。不同之处在于Q(s,a)的更新。因为Q-learning的动作选取是eplison-greedy,也就是说不是每次都是选择Q-max的动作,但是更新的时候，他都是按照Q-max的选择的那个动作去更新的。这样造成的后果就是有时候，选择执行的那个动作和更新的时候选择的那个动作会不一样。但是，对于sarsa来说，每次选取执行的动作和更新的动作是完全一致的。换句话来说，当时完全greedy的情况下，那么sarsa和Q-learning的更新是一样的。

6.6 Actor-Critic Methods

一句话概括 Actor Critic 方法:

结合了 Policy Gradient (Actor) 和 Function Approximation (Critic) 的方法.Actor基于概率选行为,Critic基于Actor的行为评判行为的得分,Actor根据Critic的评分修改选行为的概率.

Actor Critic 方法的优势: 可以进行单步更新, 比传统的 Policy Gradient 要快.Actor Critic 方法的劣势: 取决于 Critic 的价值判断, 但是 Critic 难收敛, 再加上 Actor 的更新, 就更难收敛. 为了解决收敛问题, Google Deepmind 提出了Actor Critic升级版Deep Deterministic Policy Gradient. 后者融合了 DQN 的优势, 解决了收敛难的问题.

critic是state-value function，在每次动作选择完成后，critic估计这个动作使得结果变好了还是变坏了。这个估计就是TD误差：

如果这个误差是正的，那么说明这个动作将来被选去的概率要增大，反之亦然。

actor选取动作是根据softmax方程：

p(s,a)表示t时刻actor的可修正的策略参数，即在每个状态s选择action a的概率。概率更新如下：

6.7 R-Learning for Undiscounted Continuing Tasks

R学习是一种离线策略控制方法，用于没有折扣和不能分成片段式任务的高级增强学习方法。算法如下：