[Reinforcement Learning] Model-Free Control

1 Introduction

​ 第四章节的内容讲述了agent在不依赖模型的情况下如何进行预测，也就是求解在给定策略下的状态价值或行为价值函数。本章节则主要讲解在不基于模型的条件下如何通过agent的学习优化价值函数，同时改善自身行为的策略以最大化获得累积奖励的过程，这一过程也称作不基于模型的控制。
​ 生活中有很多关于优化控制的问题，比如控制一个大厦内的多个电梯使得效率最高；机器人足球世界杯上控制机器人球员等等。所有的这些问题要么我们对其环境动力学的特点无法掌握，但是我们可以去经历、去尝试构建理解环境的模型；要么虽然问题的环境动力学特征是已知的，但由问题的规模太大以至于计算机根据一般算法无法高效的求解，除非使用采样的办法。无论问题是属于两种情况中的哪一个，不基于模型的控制都能较好的解决。

On and Off-Policy Learning

根据优化控制过程中是否利用已有或他人的经验策略来改进我们自身的控制策略，我们可以将这种优化控制分为两类：

现时策略学习（On-policy Learning）：其基本思想是agent已有一个策略，并且遵循这个策略进行采样，或者说采取一系列该策略下产生的行为，根据这一系列行为得到的奖励，更新状态函数，最后根据该更新的价值函数来优化策略得到较优的策略。要优化的策略就是当前遵循的策略。
离线策略学习（Off-policy Learning）: 其基本思想是，虽然agent有一个自己的策略，但是agent并不针对这个策略进行采样，而是基于另一个策略进行采样，这另一个策略可以是先前学习到的策略，也可以是人类的策略等一些较为优化成熟的策略，通过观察基于这类策略的行为，或者说通过对这类策略进行采样，得到这类策略下的各种行为，继而得到一些奖励，然后更新价值函数，即在自己的策略形成的价值函数的基础上观察别的策略产生的行为，以此达到学习的目的。这种学习方式类似于“站在别人的肩膀上可以看得更远”。

2 On-Policy Monte-Carlo Control

2.1 Generalised Policy Iteration (Refresher)

​ 通用策略迭代的核心是在两个交替的过程之间进行策略优化。一个过程是策略评估，另一个是改善策略。如上图的三角形区域所示，从一个策略ππ和一个价值函数VV开始，每一次箭头向上代表着利用当前策略进行价值函数的更新**，每一次箭头向下代表着根据更新的价值函数贪婪地选择新的策略，说它是贪婪的，是因为每次都采取转移到可能的、状态函数最高的新状态的行为**。最终将收敛至最优策略和最优价值函数。

​ 当使用动态规划算法来改善策略是需要知道某一状态的所有后续状态及状态间转移概率：

• ​ π*′(s)=argma**x_a∈AR^a_s+P^a_ss′V*(*s′)

2.1.1 Generalised Policy Iteration With Monte-Carlo Evaluation

图中，圆圈表示学生所处的状态，方格Sleep是一个终止状态，或者可以描述成自循环的状态，也就是Sleep状态的下一个状态100%的几率还是自己。箭头表示状态之间的转移，箭头上的数字表示当前转移的概率。
当学生处在第1节课时，他有50%的几率会参加第2节课；同时在也有50%的几率不在认真听课，进入到浏览facebook这个状态中。在浏览facebook这个状态时，他有90%的几率在下一时刻继续浏览，也有10%的几率返回到课堂内容上来。当学生进入到第2节课时，会有80%的几率继续参加第3节课，也有20%的几率觉得课程较难而退出（Sleep）。当学生处于第3节课这个状态时，他有60%的几率通过考试，继而100%的退出该课程，也有40%的可能性需要到去图书馆之类寻找参考文献，此后根据其对课堂内容的理解程度，又分别有20%、40%、40%的几率返回值第1、2、3节课重新继续学习。一个可能的学生马尔科夫链从状态Class1开始，最终结束于Sleep，其间的过程根据状态转化图可以有很多种可能性，这些都称为Sample Episodes。以下四个Episodes都是可能的：

ample Episode就是一个状态序列，一个从初始状态得到的状态序列。每一个序列都是随机序列，该序列来自于动态采样。该序列以一定概率分布在序列上进行状态转移，这个序列具有马尔可夫性。当状态序列的最后一个状态是终止状态时，该状态序列称为完整的状态序列 。
该学生马尔科夫过程的状态转移矩阵如下图：

​ 动态规划的方法是否适用于模型未知的蒙特卡洛学习呢？答案是否定的。我们无法通过分析、比较基于状态的价值来改善贪婪策略，因为不知道上述公式中当前状态的所有后续状态，以及他们的状态转移概率，进而无法确定在当前状态下采取怎样的行为更合适。
​ 这不难理解，拿第二章节提到的学生马尔科夫决策过程的例子来说，假如需要在贪婪策略下确定学生处在第三节课时的价值，你需要比较学生在第三节课后所能采取的全部两个行为“Study”和“Pub”后状态的价值。选择“Study”比较简单，在获得一个价值为10的即时奖励后进入价值恒为 0的“Sleep”状态，此时得到在“第三节课”后选择“Study”的价值为 +10；而选择“Pub”时，计算就没那么简单了，因为在“Pub”过后，学生自己并不确定将回到哪个状态，因此无法直接用某一个状态的价值来计算“Pub”行为的价值。环境按照一定的概率（分别为 0.2, 0.4, 0.4）把学生重新分配至“第一节课”、“第二节课”或“第三节课”。也只有再知道这三个概率值后，我们才能根据后续这三个状态的价值计算得到“Pub”行为的价值为 +9.4，根据贪婪策略，学生在“第三节课”的价值为 +10。在基于采样的强化学习时，我们无法事先知道这些状态之间在不同行为下的转移概率，因而无法基于状态价值来改善我们的贪婪策略。

2.1.2 Model-Free Policy Iteration Using Action-Value Function

​ 生活中也是如此，有时候一个人给自己制定了一个价值很高的目标，却发现不知采取如何的行为来达到这个目标。与其花时间比较目标与现实的差距，倒不如立足于当下，在所有可用的行为中选择一个最高价值的行为，如此来接近目标。
​ 因此，解决这一问题的方法是，使用行为价值函数Q(s,a)Q(s,a)代替状态价值函数：

​ 这样做的目的是可以改善策略而不用知道整个模型，只需要知道在某个状态下采取什么什么样的行为使得行为价值最大即可。具体是这样：我们从一个初始的Q和策略π开始，先根据这个策略更新每一个状态行为对的q值，s随后基于更新的Q确定改善的贪婪算法。

​ 即使这样，至少还存在一个问题，即当我们每次都使用贪婪算法来改善策略的时候，将很有可能由于没有足够的采样经验而导致产生一个并不是最优的策略，我们需要不时的尝试一些新的行为，这就是探索（Exploration），使用一个示例来解释：

如图：在你面前有两扇门，考虑如下的行为、奖励并使用贪婪算法改善策略：
你打开左侧门得到即时奖励为０：V(left)=0V(left)=0；
你打开右侧门得到即时奖励１：V(right)=+1V(right)=+1；
在使用贪婪算法时，接下来你将会继续打开右侧的门，而不会尝试打开左侧门
你打开右侧门得到即时奖励＋３：V(right)=(1+3)/2=+2V(right)=(1+3)/2=+2；
你打开右侧门得到即时奖励＋2：V(right)=(1+3+2)/3=+2V(right)=(1+3+2)/3=+2；
这种情况下，打开右侧门是否就一定是最好的选择呢？答案显而易见是否定的。因此完全使用贪婪算法改善策略通常不能得到最优策略。

2.2 Exploration

2.2.1 ϵ-Greedy Exploration

​ 再举一个例子。
​ 假设你刚搬到一个街区，街上有两家餐馆，你决定去两家都尝试一下并给自己的就餐体验打个分，分值在 0-10 分之间。你先体验了第一家，觉得一般，给了 5 分；过了几天又去了第二家，觉得不错，给了 8 分。此时，如果你选择贪婪策略，每次只去评分高的餐馆就餐，那么下一次你将继续选择去第二家餐馆。假设这次体验差了点，给了 6 分。经过了三次体验后，你对第一家餐馆的评分为 5 分，第二家的评分平均下来是 7 分。之后你仍然选择贪婪策略，下一次体验还去了第二家，假设体验为 7 分，那么经过这 4 次体验之后，你能确认对你来说第二家餐馆就一定比第一家好吗？答案是否定的，原因在于你只尝试了一次去第一家就餐，仅靠这一次的体验是不可靠的。贪婪策略并不意味着你今后就一定无法选择第一家就餐，当你每次依据贪婪算法在第二家餐馆就餐时，如果体验分降低导致平均分低于第一家的评分 5 分，那么下一次你将选择去第一家餐馆。不过如果你对第二家餐馆的平均体验分一直在第一家之上，那么依据贪婪策略将无法再去第一家参观体验了，也许你第一次去第一家餐馆就餐时恰好碰到他们刚开张管理还不完善的情况，而现在已经做得很好了。贪婪策略将使你错失第一家餐馆的许多美味了。采取贪婪策略还有一个问题，就是如果这条街上新开了一家餐馆，如果你对没有去过的餐馆评分为 0 的话，你将永远不会去尝试这家餐馆。
​ 贪婪策略产生问题的根源是无法保证持续的探索，为了解决这一问题，我们需要引入一个随机机制，以一定的概率选择当前最好的策略，同时给其它可能的行为一定的几率，这就是ϵ-贪婪探索。
​ ϵ-贪婪探索的目标使得某一状态下所有可能的行为都有一定非零几率被选中执行，也就保证了持续的探索，1−ϵ的概率下选择当前认为最好的行为，而ϵ的概率在所有可能的m个行为中选择（也包括那个当前最好的行为）。数学表达式如下：

​ 有一个定理：使用ϵ-贪婪探索策略，对于任意一个给定的策略π，我们在评估这个策略的同时也总在改善它。

2.3 Monte-Carlo Control

2.3.1 Monte-Carlo Policy Iteration

​ 如此，我们最终可以看到蒙特卡洛控制的全貌：使用ＱＱ函数进行策略评估，使用ϵϵ-贪婪探索来改善策略。该方法最终可以收敛至最优策略。如下图所示

​ 图中每一个向上或向下的箭头都对应着多个Episode。也就是说我们一般在经历了多个Episode之后才进行依次Ｑ函数更新或策略改善。

2.3.2 GLIE

​ 但是实际上我们也可以在每经历一个Episode之后就更新Ｑ函数或改善策略。但不管使用那种方式，在ϵ-贪婪探索算下我们始终只能得到基于某一策略下的近似Ｑ函数，且该算法没有一个终止条件，因为它一直在进行探索。因此我们必须关注以下两个方面：一方面我们不想丢掉任何更好信息和状态，想继续探索一些随机行为，保证没有丢掉更好的策略；另一方面随着我们策略的改善我们最终希望能终止于某一个最优策略，因为一个最优策略不应该包括一些随机行为。

3 On-Policy Temporal-Difference Learning

3.1 MC vs. TD Control

	TD相比MC有很多优点：低方差，可以在线实时学习，可以学习不完整Episode等。在控制问题上使用 TD 学习同样具备上述的一些优点。这就是Sarsa和Sarsa(*λ*λ)算法

3.2 Sarsa

Updating Action-Value Functions with Sarsa

​ SARSA的名称来源于下图所示的序列描述：针对一个状态S，agent通过行为策略产生一个特定的行为A，执行该行为进而产生一个状态行为对(S,A)，与环境交互，环境收到agent的行为后会告诉agent即时奖励R以及后续进入的状态S′；接下来agent再次遵循现有的行为策略产生一个新行为A′，agent此时并不执行该行为，而是根据当前的行为价值函数得到后一个状态行为对(S′,A′)的价值Q，利用这个Q值和前面的即时奖励RR更新前一个状态行为对(S,A)的价值。

3.3 Example：Sarsa on the Windy Gridworld

​ 如图所示，使用一个经典环境有风格子世界来解释 Sarsa 算法的学习过程。环境是一个10×7的长方形格子世界，标记有一个起始位置 S 和一个终止目标位置 G，格子下方的数字表示对应的列中一定强度的风。当agent进入该列的某个格子时，会按图中箭头所示的方向自动移动数字表示的格数，借此来模拟世界中风的作用。同样格子世界是有边界的，agent任意时刻只能处在世界内部的一个格子中。agent并不清楚这个世界的构造以及有风，也就是说它不知道格子是长方形的，也不知道边界在哪里，也不知道自己在里面移动移步后下一个格子与之前格子的相对位置关系，当然它也不清楚起始位置、终止目标的具体位置。但是agent会记住曾经经过的格子，下次在进入这个格子时，它能准确的辨认出这个格子曾经什么时候来过。格子可以执行的行为是朝上、下、左、右移动一步。现在要求解的问题是agent应该遵循怎样的策略才能尽快的从起始位置到达目标位置。

​ 首先将这个问题用强化学习的语言再描述一遍。这是一个不基于模型的控制问题，也就是要在不掌握马尔科夫决策过程的情况下寻找最优策略。环境世界中每一个格子可以用水平和垂直坐标来描述，如此构成拥有 70 个状态的状态空间 S。行为空间 A 具有四个基本行为。环境的的动力学特征不被agent掌握，但agent每执行一个行为，会进入一个新的状态，该状态由环境告知agent，但环境不会直接告诉agent该状态的坐标位置。即时奖励是根据任务目标来设定，现要求尽快从起始位置移动到目标位置，我们可以设定每移动一步只要不是进入目标位置都给予一个 -1 的惩罚，直至进入目标位置后获得奖励 0 同时永久停留在该位置。

​ agent通过学习发现下面的行为序列（共15步）能够得到最大程度的奖励: -14
右、右、右、右、右、右、右、右、右、下、下、下、下、左、左
agent找到该最优策略的进度以及最优策略下agent从起始状态到目标状态的行为轨迹如图：

​ 在个体找到这个最优行为序列的早期，由于个体对环境一无所知，SARSA算法需要尝试许多不同的行为，因此在一开始的2000多步里，个体只能完成少数几个完整的Episode，但随着个体找到一条链接起点到终点的路径，其快速优化策略的能力就显现的很明显了，因为它不需要走完一个Episode才能更新行为价值，而是每走一步就根据下一个状态能够得到的最好价值来更新当前状态的价值。

3.4 Sarsa(λ)

3.4.1 n-Step Sarsa

根据前面的n-步收获，类似的可以引出一个 n-步 Sarsa 的概念。

3.4.4 Sarsa(λ) Gridworld Example

接下来用格子世界的例子具体解释了 Sarsa 和 Sarsa(λ) 算法的区别：假设图最左侧描述的路线是agent采取两种算法中的一个得到的一个完整状态序列的路径。为了下文更方便描述、解释两个算法之间的区别，先做几个合理的小约定：

1. 认定每一步的即时奖励为 0，直到终点处即时奖励为 1；
2. 根据算法，除了终点以外的任何状态行为对的 Q 值可以在初始时设为任意的，但我们设定所有的 Q 值均为 0；
3. 该路线是agent第一次找到终点的路线。

Sarsa（0） 算法：

​ 由于是现时策略学习，一开始个体对环境一无所知，即所有的 Q 值均为 0，它将随机选取移步行为。在到达终点前的每一个位置 S，agent依据当前策略，产生一个移步行为，执行该行为，环境会将其放置到一个新位置 S’，同时给以即时奖励 0，在这个新位置上，根据当前的策略它会产生新位置下的一个行为，agent不执行该行为，仅仅在表中查找新状态下新行为的Q值，由于 Q = 0，依据更新公式，它将把刚才离开的位置以及对应的行为的状态行为对价值Q(S,A)更新为 0。如此直到个体最到达终点位置 S_G，它获得一个即时奖励 1，此时agent会依据公式更新其到达终点位置前所在那个位置（暂用 S_H 表示，也就是终点位置下方，向上的箭头所在的位置）时采取向上移步的那个状态行为对价值 Q(S_H,A_up)，它将不再是 0，这是agent在这个状态序列中唯一一次用非 0 数值来更新 Q 值。这样完成一个Episode，此时agent已经并只进行了一次有意义的行为价值函数的更新；同时依据新的价值函数(即Q表)产生了新的策略。这个策略绝大多数与之前的相同，只是当agent处在特殊位置 S_H 时将会有一个近乎确定的向上的行为。这里请不要误认为 Sarsa 算法只在经历一个完整的状态序列之后才更新，在这个例子中，由于我们的设定，它每走一步都会更新，只是多数时候更新的数据和原来一样罢了。

​ 此时如果要求agent继续学习，则环境将其放入起点。个体的第二次寻路过程一开始与首次一样都是盲目随机的，直到其进入终点位置下方的位置 S_H，在这个位置，agent更新的策略将使其有非常大的几率选择向上的行为直接进入终点位置 S_G。
​ 同样，经过第二次的寻路，agent了解到到达终点下方的位置S_H 价值比较大，因为在这个位置直接采取向上移步的行为就可以拿到到达终点的即时奖励。因此它会将那些通过移动一步就可以到达 S_H位置的其它位置以及相应的到达该位置位置所要采取的行为对所对应的价值进行提升。如此反复，如果采用贪婪策略更新，agent最终将得到一条到达终点的路径，不过这条路径的倒数第二步永远是在终点位置的下方。如果采用 ϵϵ-贪婪策略更新，那么个体还会尝试到终点位置的左上右等其它方向的相邻位置价值也比较大，此时个体每次完成的路径可能都不一样。通过重复多次搜索，这种 QQ 值的实质有意义的更新将覆盖越来越多的状态行为对，agent在早期采取的随机行为的步数将越来越少，直至最终实质性的更新覆盖到起始位置。此时agent将能直接给出一条确定的从起点到终点的路径。

Sarsa(λ) 算法

​ 该算法同时还针对每一次状态序列维护一个关于状态行为对 (S,A) 的 E 表，初始时 E 表值均为 0。当agent首次在起点 S₀ 决定移动一步 A₀(假设向右) 时，它被环境告知新位置为 S₁，此时发生如下事情：
​ 首先，agent会做一个标记，使 E(S₀,A₀) 的值增加 1，表明agent刚刚经历过这个事件(S₀,A₀)；
​ 其次，它要估计这个事件的对于解决整个问题的价值，也就是估计TD误差，此时依据公式结果为 0，说明agent认为在起点处向右走没什么价值，这个“没有什么价值”有两层含义：不仅说明在 S₀ 处往右目前对解决问题没有积极帮助，同时表明agent认为所有能够到达 S₀ 状态的状态行为对的价值没有任何积极或消极的变化。
​ 随后，agent将要更新该状态序列中所有已经经历的 Q(S,A) 值，由于存在 E 值，那些在(S₀,A₀) 之前近期发生或频繁发生的 (S,A) 的 Q 值将改变得比其它 Q 值明显些，此外agent还要更新其 E 值，以备下次使用。对于刚从起点出发的agent，这次更新没有使得任何 Q 值发生变化，仅仅在 E(S₀,A₀) 处有了一个实质的变化。随后的过程类似，agent有意义的发现就是对路径有一个记忆，体现在 E 里，具体的 Q 值没发生变化。这一情况直到agent到达终点位置时发生改变。此时agent得到了一个即时奖励 1，它会发现这一次变化（从 S_H 采取向上行为 A_up 到达 S_G）价值明显，它会计算这个 TD误差为 1，同时告诉整个经历过程中所有(S,A)，根据其与 (S_H,A_up) 的密切关系更新这些状态行为对的价值Q，agent在这个状态序列中经历的所有状态行为对的Q值都将得到一个非 0 的更新，但是那些在个体到达 S_H 之前就近发生以及频繁发生的状态行为对的价值提升得更加明显。
​ 在图示的例子中没有显示某一状态行为频发的情况，如果agent在寻路的过程中绕过一些弯，多次到达同一个位置，并在该位置采取的相同的动作，最终agent到达终止状态时，就产生了多次发生的 (S,A)，这时的 (S,A) 的价值也会得到较多提升。也就是说，agent每得到一个即时奖励，同时会对所有历史事件的价值进行依次更新，当然那些与该事件关系紧密的事件价值改变的较为明显。这里的事件指的就是状态行为对。在同一状态采取不同行为是不同的事件。
​ 当agent重新从起点第二次出发时，它会发现起点处向右走的价值不再是 0。如果采用贪婪策略更新，agent将根据上次经验得到的新策略直接选择右走，并且一直按照原路找到终点。如果采用 ϵ-贪婪策略更新，那么agent还会尝试新的路线。由于为了解释方便，做了一些约定，这会导致问题并不要求agent找到最短一条路径，如果需要找最短路径，需要在每一次状态转移时给agent一个负的奖励。
​ Sarsa(λ)算法里在状态每发生一次变化后都对整个状态空间和行为空间的Q和E值进行更新，而事实上在每一个Episode里，只有agent经历过的状态行为对的E才可能不为0，为什么不仅仅对该Episode涉及到的状态行为对进行更新呢？理论上是可以仅对Episode里涉及的状态行为对的E和Q进行更新的，不过这要额外维护一个表，而往这个额外的表里添加新的状态行为对的E和Q值比更新总的状态行为空间要麻烦，特别是在早期agent没有一个较好的策略的时候需要花费很长很长时间才能找到终点位置，这在一定程度上反而没有更新状态空间省时。不过随着学习深入、策略得到优化，此表的规模会变小。

4 Off-Policy Learning

​ 现时策略学习的特点就是产生实际行为的策略与更新价值 (评价) 所使用的策略是同一个策略，而借鉴策略学习 (off-policy learning) 中产生指导自身行为的策略 µ(a|s) 与评价策略 π(a|s)是不同的策略，具体地说，agent通过策略µ(a|s) 生成行为与环境发生实际交互，但是在更新这个状态行为对的价值时使用的是目标策略π(a|s)。目标策略π(a|s)多数是已经具备一定能力的 策略，例如人类已有的经验或其他个体学习到的经验。借鉴策略学习相当于站在目标策略π(a|s)的“肩膀”上学习。借鉴策略学习根据是否经历完整的状态序列可以将其分为基于蒙特卡洛的和基于 TD 的。基于蒙特卡洛的借鉴策略学习目前认为仅有理论上的研究价值，在实际中用处不大。这里主要讲述常用借鉴策略 TD 学习。