用法总结

Imitation learning只能模仿所给的demonstration，并不能超越，而且没有应用到reward。

对于Markov decision process，如果policy和state transition是deterministic的，而且state和action是连续的，我们可以直接把reward当做label来进行监督学习。但是效果不会好。

如果是stochastic policy，那么就用policy gradient。

如果是deterministic policy，那么就用Q-learning。但是如果action是continuous的，可能没那么直接。

如果可以学习到或者直接知道state transition，那么就用model-based RL。

而如果reward没那么直接得到，inverse RL就是用来学习reward如何设置。

效果比较

Q-learing一般用在Q函数表述简单，action是discrete，以及policy是deterministic的时候。

Policy Gradient可用范围较大，也收敛的更快。但是容易陷入局部最优，也容易受到high variance的影响。原因是数据必须是当前policy产的，数据较稀疏。Q-learning就stable一些。如果Q-learning比较适用，一般会比policy gradient效果好。

Trade-offs Between Policy Optimization and Q-Learning. The primary strength of policy optimization methods is that they are principled, in the sense that you directly optimize for the thing you want. This tends to make them stable and reliable. By contrast, Q-learning methods only indirectly optimize for agent performance, by training Q to satisfy a self-consistency equation. There are many failure modes for this kind of learning, so it tends to be less stable. [1]But, Q-learning methods gain the advantage of being substantially more sample efficient when they do work, because they can reuse data more effectively than policy optimization techniques.

Lecture 1: Introduction and Course Overview

对于单独决策，例如分类，回归，现在的结果不影响之后的状态并且现在的决策不影响以后的决策，不需要用强化学习来解决。

对于你知道reward该如何衡量但是没有直接的训练数据，或者当前决策影响之后的结果（需要拿到后面的反馈）甚至只有在最后才得到反馈，即序列决策问题，则用强化学习来解决。

除了一般的最大化reward的强化学习还有如下几种：（1）直接copy观察到的action，例如imitation learning；（2）从观察到的action中学习reward应该如何设置，例如inverse RL；（3）从观察到的state中学习predict state来帮助我们提前做prediction，例如model-based RL。

Deep强化学习的局限：不能很快的学习；不能很好的应用过去的知识（transfer learning）；目前不清楚reward function应该是什么样；以及prediction应该扮演什么角色。

Lecture 2: Supervised Learning and Imitation

如果是fully observed，那么observation就是state，否则只是partial observation。对于fully observed情况，下一个state只依赖于当前state和当前action。Imitation learning是在partial observation假设下。而后续要讲的Policy gradient和Q-learning都是在fully observation假设下。

Imitation learning就是有监督的behavior cloning。以state作为输入，action作为label。以下主要讲用监督学习解决decision making所遇到的问题。

问题1：distribution drift

当训练语料的分布跟我们真实模型action到的分布不一致时，在训练时没有见过的state会让我们陷入超大error bound，而且正比于T^2，其中T是序列长度。但是如果分布一致，就只正比于T。

例如为什么对于自动驾驶，直接进行有监督的训练行不通：有可能现在的情景训练语料里面没有见过，所以就会一步步把错误放大。但是有人确实利用监督训练进行自动驾驶，他们的方法是加入额外左右视角，然后label为转动到正常的角度，这样在训练语料里面就有了脱轨的场景。

这样就启发我们利用Gaussian distribution来获得训练语料的variant。

DAgger（Dateset Aggregation）也是解决distribution drift的一种方法，通过让人额外标注policy新产生的数据来增加训练语料的鲁棒性直到不再产生新的状态。此方法可以证明收敛性。缺点是需要人标注大量语料，而且人类标注新增的语料往往没那么容易。

另外一个缓解的方法是尽量让你的模型学习地准备！

问题2：Non-markovian action

如果给的训练语料里面的action并不仅仅是根据当前的observation，还依赖之前的一系列历史observation，即partially observation，那么我们的模型也需要引入历史状态。一种解决方法是引入RNN。

问题3：Multimodal action

对于multimodal action，如果action是discrete的，那么没问题。如果action是continuous的，比如我们用高斯分布来建模，那么就会average我们的行动，得到一个不想要的结果。有三种解决方法：（1）输出用混合高斯来表述，但是需要每次都要根据输出个数调整高斯的个数；（2）Latent variable models是在输入的时候加入一个高斯干扰，这样尽管输出是一个高斯分布，仍旧可以区分multimodal ，但是很难训练学习（问题：如何变的？）例子有conditional variational autoencoder，stein variational gradient descent ；（3）以及autoregressive discretization，即把连续值离散化，有一个trick是分层离散化不同维度的action。

应用：

应用DAgger来训练夏天跟冬天的飞行场景，但是冬天的场景语料比较少，所有额外用了advertiser loss来保证共享的底层不能分辨出来是夏天还是冬天的场景。

应用RNN作为历史输入表达以及混合高斯作为输出表述，同时用autoencoder以及GAN来做regularization，来解决移动物体到特定位置的问题。cost不单单是是否完成了动作，而可以是物体跟目标的距离以及机器跟物体的距离之和，从而可以更好让模型学习。

机器翻译可以看成imitation learning。

Imitation learning的局限

Imitation learning受限制的原因有：需要人类标注大量的data；人类在一些领域表现不擅长，比如飞机的花式表演；或者我们想要超越人类demonstrate的表现；人类可以自动的学习，model是不是可以自己去学习？

那么我们如果可以从demonstration里面学习到reward到底是什么（inverse RL），或者直接人为的给出reward是什么，就可以真正的超越人类demonstration的表现了。

作业1！！！

Lecture 4: Reinforcement Learning Introduction

本课程先介绍Markov decision process，然后RL的定义，outline of RL算法。

基本定义

Markov decision process定义了基本的RL架构。Markov chain定义了state和state transition，而当前状态只依赖前一个state。Markov decision process在此基础上加入了action和reward，state transition此时则依赖于前一个state和当前action。 Partially observed Markov decision process是一个更general的假设。但是后续的算法主要是关于fully observed Markov decision process问题。一般情况下转移状态概率是未知的。

RL优化目标

RL的优化目标是

式4-1

在一般情况下，如果T趋向于无穷，那么我们最终到达的state和action分布将会趋向于稳定。但是也有很多情况不会。

虽然很多action和reward单个都是不连续不可导的，但是期望是smooth的，而RL优化的是期望。

对于Markov decision process，如果policy和state transition是deterministic的，而且state和action是连续的，我们可以直接把reward当做label来进行监督学习。但是你可以看到，它的预设条件很多，也就是可用范围很小。而且随着T的增大，会跟RNN一样遇到导数vanish或者exploding的问题。Model-based RL可以更好地处理这类问题。

对于stochastic的system，就需要对policy的期望求导才能得到。对于式4-1，一方面你可以直接求导，即policy gradient方法。另外一方面，人们引入了V和Q函数来表示某个状态或者某个状态和动作下，根据某个policy后续所累计达到的reward的值。这样一来，RL的优化目标就可以表达成V或者Q的期望。而单独利用Q函数，我们就可以优化policy：根据whatever policy产生的数据，我们只需要在每次选择action的时候都选择使得当前Q值最大的那个action，就可以保证新产生的policy是至少不差于原policy的。对于action的continuous的情况，上面的方法就没那么直接了，这个时候我们仍旧可以利用V和Q函数帮助我们做policy gradient：对Q-V来期望最大化，也就是让对于其Q值跟平均的Q值差异最大化的action，我们增加它的概率。

RL算法分类

Policy gradient直接对式4-1进行求导，当然因为有太多太多trajectory所以对真实的期望求导是intractable的，所以实际上是进行sample来近似求解。Value-based算法，是根据V或者Q（也是sample得到）来求解最优policy（不会得到explicit的policy，而是一个deterministic的plan）。Actor-critic则是上面两种方式的结合：得到现有policy的V或者Q，然后据此来依据policy gradient优化policy。Model-based RL,通过学习state transition，可以用它来帮助我们：Discrete planning（e.g. Monte Carlo tree search）；帮助policy gradient；帮助学习V函数（dynamic programming或者产生simulated数据来帮助model-free算法（Dyna））。

以下根据不同的标准对算法进行比较。

不同算法有不同的考量：policy比较好表达？还是state transition比较好表达？policy是随机的还是确定性的？state和action是连续的还是离散的？Horizon是episodic还是无限的？

根据sample efficiency（ how many samples do we need to get a good policy）从小到大，算法排序为：evolutionary<policy gradient<actor-critic<Q learning<model-based。但是这个不是衡量算法好坏的唯一标准，我们还要考虑算法的学习效率以及稳定性。

监督学习通常是通过gradient descent on objective来求解，所以收敛性总是有保证的。但是RL通常不是：（1）Q-learning是通过fixed point iteration迭代求解，是在minimize “Bellman error”，所以对复杂的网络不能保证收敛；（2）model-based RL是用gradient descent来优化state transition model而不是reward，所以也不能保证收敛性；（3）policy gradient是gradient descent on objective，所以确实是收敛的，但是需要大量的数据，所以最低效，而且有high variance问题。

Value function fitting方法需要fully observability假设，当然可以通过recurrence来缓解。Policy gradient方法需要episodic假设，但是actor-critic不需要。以及一些model-based RL也需要episodic假设。有一些value functions方法以及一些model-based方法需要 continuity或者smoothness的假设。

Lecture 5: Policy Gradients Introduction

以下主要是在finite horizon假设下做推算：

式5-1

但是我们只能做近似推算：sample一些case来最小化trajectory的平均reward。注意：我们所求解的policy都是stationary policy，也就是同一个状态有相同的policy分布，而不是根据t的改变有所改变。有可能我们的最优policy不是stationary的，但是我们一般都是来求解stationary的policy。

REINFORCE算法

式5-1中的目标可以改写为：

式5-2

但是因为 $\pi _{\theta}$ 的展开式是：

式5-3

里面含有state transition，而这个我们是未知的，所以不能对式5-2直接求解。所以对式5-2进行形变为：

式5-4

然后通过代入5-3的展开就可以简化为：

式5-5

此时就只有policy而没有state transition了。注意：上式对于没有markov property假设的情况下也是可以直接约掉的，这个时候只是state transition不是上面这个形式了而已。所以对于partially observd MDPs我们同样可以用这种方法来求解。

接着我们就可以sample数据来求解了。

式5-6

此方法被称为REINFORCE算法。跟SGD一样，此方法只能求得局部最优解。而因为我们的trajectory reward的期望计算需要引入要优化的policy来求导，所以trajectory需要根据要优化的policy来产生，因此此方法是on policy的。

首先我们来看一下式5-6跟监督学习的区别，监督学习要对极大似然函数求导：

式5-7

可以看出跟式5-6的区别主要是我们把所有的trajectory的reward都等价为一样的了。

如何避免high-variance

如果真的按照式5-6来优化，那么算法会运行的非常poor，因为会受到variance的影响。接下来主要给一些如何缓解variance的trick。

为什么我们的REINFORCE算法是high variance的？考虑一种情况：对于一个reward为r且不等于0的trajectory，它本身对式5-6是有贡献的。但是如果我们对所有的trajectory的reward都减去这个r，那么应该学习得到policy跟之前是一样的。但是根据式5-6，此trajectory的reward变为0，那么就不会对求导有贡献了。这对于sample只有有限的数据的情况下会出现问题。

下面给出两种不会有损害的降低variance的方法。

方法一：

根据分配率，式5-6等价于：

式5-8

根据“reward to go”，上式等价于（问题：为什么？）：

式5-9

为什么上式会让variance减小呢，因为variance是期望的当前求导值减去求导值的期望，那么当我们的导数越小，variance也会越小。

方法二：

针对上面所举例的情况，我们可以对所有的reward进行标准化，即全部减去一个baseline值，最优的baseline值是，即对reward的根据导数的weighted期望。

式5-10

一种近似的方法是直接把reward的平均值作为baseline，虽然不是最优baseline，但是表现不错。

利用importance sampling来实现Off-policy learning

接下来给出一个off-policy版本的policy gradient。

首先importance sampling是：

式5-11

利用上式，我们就可以根据来着分布 $\tilde{\pi }$ 的sample来优化 $\pi _\theta$ ，后者的目标可以表示为：

式5-12

按照式5-4类似的方式变形最终得到：

式5-13

那么我们就可以利用之前根据 $\pi_\theta$ sample出来的数据来训练更新 $\pi_{\theta^"}$ 。根据式5-3展开约分得到如下：

式5-14

由于policy给出的值是[0-1]，指数乘积只会越来越趋向于0或者1，为了解决这个问题，首先我们带入“reward to go”，则得到

式5-15

其中第一个乘积代表当前state在新的policy下是有多大概率出现，第二个乘积代表之后的reward在新的policy下有多大概率出现。然后再进一步降低指数运算，直接把后面的乘积去掉

式5-16

这样的计算更新policy的方法不再叫做policy gradient而是policy iteration。但是可以保证每次更新的policy都比之前的好。

但是importance sampling并不能保证我们仍然可以学到一个好的policy，estimator的variance是：

式5-17

其中红色第一项如果在f(x)较大的地方过大，那么variance过大，会估计不准。

利用监督学习工具来做Policy Gradient

我们要利用式5-9来迭代训练参数。式5-9可以改写成：

式5-18

注意：上面这个loss并不能看成简单的weighted loss，因为Q必须依赖于当前的policy生成，所以是一个根据policy分布得到的一个期望值。而监督学习是利用式5-7来迭代训练，所以我们可以利用监督学习工具来训练，即把后面的Q作为一个weight。对于discrete action，就是weighted cross entropy。对于continues action，就是weighted squared error。但是注意，如果policy是deterministic的，那么此方法就不管用了。这时候就要用到Q-learning。

关于policy gradient的一些文章

Lecture 6: Actor-Critic Introduction

进一步避免high variance

式5-17中的Q是利用sample来得到的（式5-6中的约等于号），sample量经常是不够的，所以有high variance的问题。因此这里引入真实的期望reward-to-go:

式6-1

加入baseline，最终要求导的公式为：

式6-2

其中

式6-3

所以为了求得A，有不同的方式。我们可以fit Q或V来达到。首先对于Q，可以进一步写为

式6-4

但是我们不知道state transition，所以用其中的一个state近似后面部分：

式6-5

注意，这样的近似仍然是比式5-17要好的，因为我们只是在t+1步做了一次sample，而此后我们仍然是计算的期望。此时的A写成：

式6-6

纯粹是可以用V来表述了。其中V可以写为：

式6-7

注意，目标也可也用V来表述：

式6-8

而V可以用policy evaluation（也就是evaluate reward值）来求解。注意：这里的V只是用来evaluate当前状态值，而Q-learning里面的求得的V是用来找到一个更好的policy。

Monte Carlo方法来做policy evaluation

也就是policy gradient所用的方法：

式6-9

为了让上式接近期望值，第一种方法是使用simulator然后多次back to状态s_t来sample reward：

式6-10

但是一般我们不能做到上述sample。第二种种方法是，如果我们用NN网络来监督学习V，那么多个sample就共享了网络参数，有个额外好处就是虽然输入state不完全相同，但是相似state输入是相似的，就可以互相帮助学习。虽然不如第一种方法那么好，但是效果也不错。也就是输入训练语料为：

式6-11

训练目标是

式6-12

对于式6-11，我们的目标是y能不能更贴近于期望值式6-7呢？所以第三种实现方法是引入之前学习到的V'来近似式6-7（bootstramp），此时输入的训练语料变为：

式6-13

因为引入了之前的V'，所以模型是high bias（结果可能是incorrect的）的但是同时相比之前也是low variance的，所以从仅有的sample里更有可能学习到好的模型。这里引入的V'不会用来做gradient。

Actor-critic算法

其中第二部就是上面的Monte Carlo policy evaluation中的式6-12。此算法中我们需要学习两个NN网络， $\pi$ 和 $V$ ，前者交actor，后者交critic。因为输入都是state，他们的网络可以共享或者部分共享。

如果T是无限大，那么V就会无限大，模型就不会学得好。解决方法是引入discount factor。这样MDP结构就被改变了一下。如果把discout factor带入式5-9，那么就变成下式：

式6-14

但是实际上我们带入式5-8，那么就得到

式6-15

利用‘reward-to-go’就转化成：

式6-16

比较式6-14跟6-16，发现后式多了个衰减。正确的式子应该是后式，但是实际上大家用的都是前式。因为加入discount factor只是为了解决T过大的现象，但是也有可能会使得模型过分关注当前的一两步，而我们实际上想要的是学的一个process。这里discount factor可以看成是一个防止之后的未知state过分影响现在导致variance过大的超参数，所以是一个balance，不过分受后面的影响也不过分只关注眼前。

Actor-critic算法的online版本就是在每次产生了一个新的state之后就更新。这个要得益于式6-1到6-3的引入，因为这样一来就不需要等到产生完后面状态才能得到当前的reward的了。实际情况中，我们会batch的来产生数据来更新参数，一个目的是为了防止陷入locally overfit。

进一步选择baseline

式6-6引入降低variance的方法是有high bias问题的。如果我们把式5-10的baseline换做当前V值，则可以在保证low bias的情况下有low variance。当然没有式6-6的variance低。

式6-17

另外一种方法是把Q值当做baseline然后再加上：

式6-18

上式跟式5-9是等价的，但是如果我们能够evaluate第二项，那么在保证low bias的情况下可以求解的更好。（问题：如何降低variance的？）

Variance跟bias的trade off

式6-6跟式6-17的区别就是对于未来t+1之后的reward，我们应该完全相信当前预测的V值还是sample出来的值。如果完全相信，那么就会有high bias的问题。一个折中的方案是只在n步内相信sample（eligibility trances），之后相信预测的V值：

式6-19

上式集成的方法是：

式6-19

关于Actor-critic的一些文章

作业2！！！！

Lecture 7: Value Functions and Q-Learning

对于一个已知的数据集和在此上的一个policy，如果我们选择以下方式产生一个新的policy：

式7-1

那么可以保证至少不差于之前的policy。而且对于fully observed MDPs，可以证明存在一个deterministic policy是optimal的，但是对partial observed就不是了。另外，如果是stochastic policy，则会在求解的过程中学的更快。

Policy iteration

根据上面的方法，我们得到policy iteration algorithm:

policy iteration

第一步可以根据我们式6-6介绍的policy iteration的方法得到。但是此时我们有更好的方法。而第二步是通过式7-1得到。此方法在别人产的数据上做优化，是off policy learning。

Dynamic programming

根据式6-3和6-4我们得到policy iteration中第一步的A可以表示为：

式7-2

那么为了求上式中的A，求出V即可。根据式6-3中的V和6-4得到

式7-3

此时的policy已知了是deterministic的，那么上式可以简化为：

式7-4

因为policy是已知的，假设我们知道state transition，上式就可以通过动态规划（参考https://www.jianshu.com/p/ce359c661c99）一步一步求得每个state的V值。之后就可以带入policy iteration来更新policy。

Value iteration

我们知道有

式7-5

那么policy iteration的第一步就变成求Q，而第二步可以跳过显式的求policy直接把式7-1带入到求V中，从而得到value iteration。

式7-6

但是要保证等价于policy iteration，则需要符合动态规划的更新步骤，同时每个state的1、2步要一起更新。

Fitted value iteration

对于现实问题state空间比较大，我们用NN网络来逼近第二步（问题：是否有保证符合动态规划的更新步骤？）：

式7-7

Q value iteration

但是注意上式中期望需要用到state transition，而max on action则需要我们拿到所有的action作用在同一个状态上的reward，这是不可能实现的。回归式7-5，我们可否绕过V而直接做Q的逼近呢？一旦有了Q的NN网络实现，那么我们可以得到任何action的Q值了。我们把式7-6中的第二步直接带入到第一步，就得到Q值更新方式为：

式7-8

其中 $\pi$ 是在选择最大的Q。而上面单一步就叫做Q value iteration方法。此时直接assign更新的方法叫做tabular case。

但是式7-8同样需要用到state transition，为了跨过这个，我们用其中一个state近似期望：

式7-9

Fitted Q value iteration

类似得到fitted Q value iteration算法：

式7-10

此时最小化fitted的方法叫做approximator case。而因为只有一个网络Q需要学习，所以没有policy gradient那么high-variance（问题：为什么？）。由于是fitted方式，所以此算法对于non-linear的网络不能保证收敛。Fitted Q value iteration算法是off-policy的，因为我们有了一个fitted Q网络可以产生任意state的Q值，而这里第一步的最后面一项是我们的上次迭代policy，不依赖于产生数据的policy。

把式7-10里面的第二项带入第一项，就得到我们实际要minimize的目标是：

式7-11

而如果有一个式7-1的策略满足

式7-12

那么就肯定是一个optima的policy。（问题：s'是怎么来的？只需要保证collect data里面的s'吗？需要保证多少（s,a）对满足?）。

Online Q-learning算法

通过把式7-10的fitted Q value iteration变成online形式，就是我们所说的Q-learning了。

式7-13

相比较式7-10中的第二步的minimization，这里只做了一步的gradient。在式7-13中的第一步，如果我们想产生新的数据，一种尝试是直接用我们目前学习到的policy来产。但是因为我们的policy是deterministic的，所以会造成只做固定的一些action，此时我们需要加入exploration。常用的方法是加入“epsilon-greedy”，也就是在epsilon概率下做一些其他random的action。另外一种方法是做“Boltzmann exploration”，也就是我们可以借助学到的Q函数帮助我们判断，如果一个action的Q值特别特别低，那么就没必要尝试了。

Value function learning theory

为什么式7-6算法可以得到最优的policy？依据是contraction map，如果||B(x) - B(y)|| <= r||x-y||，其中r\in[0,1]，那么B就是contraction的。在这个前提下，通过repeated应用B在当前的输出上，最终就会逼近B的unique fixed-points。而我们如果把式7-6中第二步带入第一步就是一个contraction map:

式7-14

同时最优policy对应的V也是此map的unique fixed-point，即：

式7-15

但是对于fitted value iteration，式7-7引入了approximation，它的第二步projection可以看成是另外一个contraction map： L2 norm。当我们把这两个contraction map合起来之后，并不能再得到一个contraction map。所以fitted value iteration不能coverage，在通常的现实情况下都不能。

Q value iteration同样也是这种情况，tabular case可以coverage，但是approximation case不能。

同样的情况也发生在式6-13和式6-12组成的在actor-critic算法中学习V的时候。此时的approximation也造成了不能收敛。当然单纯的Monte Carlo策略是可以收敛的。（问题：此时的收敛应该不是指regression的收敛，那么为何单纯的Monte Carlo可以收敛？）

从regression的角度考虑，式7-13的regression完全可以让我们达到最优Q。但是注意式7-13中的第二步的y我们是固定住的，没有对此进行求导，所以Q-learning并不能使其逼近assign的值。如果我们强行对y求导，那么情况只会更糟。

Lecture 8: Advanced Q-Learning Algorithms

再来回顾一下online Q-learning，在现实情况中，有两个问题使得此算法表现不好：

问题1：式7-13中的第一步产生的data是correlated的，而stochastic algorithm假设数据是不相关的，前后相关的数据会让模型陷入locally overfitting；

问题2：第三步是没有对y进行gradient，所以不能收敛。

对于问题1，我们可以跟actor-critic一样引入batch，这样同一个batch里面的数据就不怎么相关了（问题：为什么不相关？）。另外一个解是加入replay buffer：跟试7-13的第一步不同，我们store所有产生的data在一个buffer里面，然后每次随机选取一个batch来做gradient。有时候对于过老的数据，我们也会从buffer里面去掉。

对于问题2，我们是不是可以引入一个比较stable的不依赖于 $Q_\phi$ 而改变的y？这里我们引入一个target network $Q_{\phi"}$ 来求y，而此网络的参数延迟几步更新为 $Q_\phi$ 。

最终我们得到“classic” deep Q-learning 算法：

式8-1

DQN就是每次只generate一次data，每个batch只做一次gradient。

上面这种方法有一个缺点是对距离更新 $\phi"$ 不同距离的时间点， $\phi$ 跟 $\phi"$ 的差距会不一样。一种方法是保留一部分之前的值。

式8-2

Double Q-learning

现实实验表明我们的预测的Q值远远大于真正的reward，原因是式8-1的第三步我们引入了max，而

式8-3

所以我们overestimates Q值on state s'。注意到我们可以改写max这一项：

式8-4

即先选择action，再算出value。那么如果我们把这两部分分开由两个network得到，是不是就可以缓解overestimate的问题了？因为他们noisy in different ways。现实中，我们只需要把target network跟当前的network分别当做这两个network就可以了，也就是把式8-1的第三步改变为：

式8-5

如果我们的Q不准的话，那么上式就只能依赖当前的reward来学习了。类似于式6-19，我们是否可以找到一个balance？我们得到如下方法：

式8-6

但是跟actor-critic不同的是，此时我们是off-policy的，也就是右边的第一项并不是当前policy对应的reward list！或者我们忽略这一点，或者我们可以cut the trance保证选择的N步内的data跟当前的policy一致，或者用importance sampling的方法。

Q-learning with continuous actions

当action是连续的，式7-1和式8-5的max就需要额外考虑了。要计算这一部分有几种方法：

（a）当做一个optimization来用SGD求解；

（b）或者stochastic optimization，其中一种是sample一些action，虽然不是很准确，但是反正我们有式8-3引入的overestimate问题。

（c）改变Q的形式为Normalized Advantage Functions

式8-7

（c）DDPG算法。再创建一个network用来学习deterministic policy，把式8-4中的最后一项用另外一个网络表示：

式8-8

参数更新方式为：

式8-9

而此时的target y是：

式8-10

Tips for Q-learning

Large replay buffers help improve stability

Bellman error gradients can be big; clip gradients or user Huber loss

Double Q-learning helps a lot in practice, simple and no downsides

N-step returns also help a lot, but have some downsides

Run multiple random seeds, it’s very inconsistent between runs

关于Q-learning的一些文章

Lecture 9: Advanced Policy Gradients

本节课主要是讲述policy gradient更新策略的优化。

首先从policy iteration出发，式5-17的policy gradient可以看成是policy iteration的形式：

式9-1

上式是不是跟policy iteration形式很像？那么以policy iteration的角度更新policy实际上就是在找一个可以max（ $J(\theta")-J(\theta)$ ）的更新方式。而此项实际上等价于：

式9-2

也就是依据之前advantage值的基础上，最大化在新策略上的期望。而上式通过形变之后等价于：

式9-3

能否把前面一项用后面一项近似呢？这样一来后面一项就可以用 $\theta$ 对应的sample来得到了。为了实现近似，我们必须加入一个约束，即前后的p变化不大，也就等价于约束前后的policy变化不大。（问题：p不是state transition吗？什么情况下会不一致？）所以实际上等价于更新policy方式为：

式9-3

有两种方法求解这个问题。

一种是使用拉格朗日乘子法（参考https://www.cnblogs.com/xinchen1111/p/8804858.html）：

式9-4

Natural policy gradient

第二种方法是在一个假设的基础上：如果式9-3种第二行的 $\epsilon$ 足够小的话，可以把式9-3的第一行改变为以 $\theta$ 的导数方向为步长更新，即式9-3可以改写为：

式9-5

而其中的 $\bar{A}$ 有：

式9-6

也就是normal policy gradient！那么式9-5是不是可以直接按照normal的方式更新呢：

式9-7

别忘记我们还有一个constraint。而上式实际上等价于：

式9-8

即对所有的参数约束都一样。也就是对所有参数的更新步长一致（去除掉各自导数的不同）。但是式9-5中对每个参数约束是不一样的。而式9-5中的第二行可以泰勒展开为：

式9-9

其中F是Fisher-information matrix：

式9-10

此matrix可以通过sample得到。所有参数更新的方式为：

式9-11

此方法就被称为natural policy gradient。

Trust region policy optimization

上面的方法有几个问题：式9-5的第二行我们的约束是一个超参数，如果设置的过大或者过小都会有问题。而且因为我们用了式9-9近似，原本的KL-divergence约束可能会被violated。所以TRPO做了如下条件判断：

式9-12

只有在上面两个条件满足的时候才进行gradient，否则的话j++来减小step size直到条件满足（backtracking line search）。

Proximal policy optimization

在引入deep learning之后，上面的方法很难计算。此时引入了PPO with KL penalty方法，此方法跟上面的方法稍微有几点不同。

1. collect大量的partial trajectory而不是fully。

2. 不再计算Fisher-information matrix来得到gradient，而是用下式更新 $\theta$ ：

式9-13

也就是说把朗格朗日乘子式通过先固定 $\beta$ 来更新 $\theta$ ，然后又固定 $\theta$ 来更新 $\beta$ ，

式9-14

也就是说如果此次的KL-divergence过大的话，我们就调整它的权重 $\beta$ ，而如果过小的话，则减小其权重。

在更新 $\theta$ 的时候这里是用mini-batch来多次小步做SGD。

而PPO with clipped objective则直接把上面的第二步变成直接对clip的目标函数求导：

式9-15

其中

式9-16

其中 $\epsilon$ 是个超参数。上式中的clip跟KL-divergence的目的一样，但是此方法没有理论基础。看下图：

式9-17

虽然orange和blue的线都是在远离的时候或者上升或者保持不变，但是min on 他们，也就是red的线会在远离的时候降低step size（问题：为什么会降低？）。

作业3！！！！

Lecture 10: Optimal Control and Planning

上面介绍的模型都是在当我们不知道state transition的时候，用sample来进行近似学习。但是对于一些棋类游戏或者物理模型或者在simulated环境中，我们知道transition dynamics是什么样的，或者我们可以学习到transition dynamics，就可以用到model-based RL了。Optimal control， trajectory optimization, planning都是在dynamics已知的情况下去做plan without policy的一些方法。Model-based的好处是一旦我们知道了transition是什么，我们就可以直接去plan而不用学习policy是什么了。

Open-loop vs Closed-loop

对于open-loop也就是只能跟环境交互最初的一次，如果state transition以及policy是deterministic的，那么仍旧可以求得最优解；如果是state transition是stochastic的，那么在已经有了action的情况下，reward的概率为：

式10-1

根据此概率来期望最大化action为：

式10-2

由于式10-1跟式5-3的差别导致求解式10-2的最优解并不是式5-1的最优解。也就是说，在没有环境交互的情况下，我们并不能找到最优policy。因为我们的policy不能根据具体的state来选择，而是每一步对所有state都是一样的。

而对于closed-loop，也就是每一步都能跟环境交互得到下一个state，我们就可以求得最优解了。

Monte Carlo Tree Search （MCTS）

先跳出open-loop还是closed-loop的框架。对于discrete的action问题，不管是open-loop还是closed-loop，只要我们有了一个simulator或者环境可以允许我们执行一个policy来得到对应的reward的，那么就可以用MCTS这种planning方法来帮助我们根据当前的state找到一个较好的action。（问题：如果transition不知道会如何？）

单纯的search每个可能的action来找最优解肯定是太费时的。类似的优化方法有A* search或者breadth-first search，MCTS不同于他们，通过对node进行好坏的衡量来确定是否要expand此node。那么如何评价一个node好坏呢，可以选择任意的一个policy来执行，根据得到的reward就能一定程度达到衡量当前node好坏的目的。一般的MCTS的执行过程为：

式10-3

其中TreePolicy是在选择expand的node，DefaultPolicy是在执行一个policy得到reward值。TreePolicy一般的策略是：如果root没fully expanded，那么expand root；否则，选择一个score最大的node。其中score的计算方法为：

式10-4

其中的Q值就是每个descendant node（包括当前节点）执行DefaultPolicy得到的reward值的总和，N代表执行DefaultPolicy的次数。所以式10-4的第一项表示平均reward值，第二项代表相比其parent node被expand的次数的log，当前node的descendants被expand的次数。所以此式是在trade-off on是否应该expand一个reward值较大的node还是应该去expand不经常visit的node（或者相比parent被visit的次数不经常visit）。此方法当然会有它的bias。可以参考《 A Survey of Monte Carlo Tree Search Methods.》。

Open-loop planning

为什么我们考虑open-loop呢，因为在做plan的时候我们并不能知道中间state是什么。（问题：为什么？）

那么对于open-loop也就是我们只能跟环境交互最初的一次的情况下，如何做planning呢？

对于stochastic state transition，最简单但是有效的方法是guess and check。此方法的进阶版是cross-entropy method（CEM）：基于已有guess and check的基础上，用好的guess帮助我们fit我们guess的分布（即maximum likelihood）从而产生更好guess。缺点是步长有限制，不适合高维问题。

对于discrete action，我们可以用MCTS方法来求解。对于continuous action，以及deterministic state transition，用LQR方式来解。式10-2可以改写成

式10-5

可以展开为：

式10-6

由于多个嵌套，对此式直接进行求导会造成ill conditioned gradient。

如果我们指导reward和state transition如何表述，并且对上式的c和f可以做到linear建模：

式10-7

那么就可以从最后一步对 $Q(x_t,u_t)$ 的导数求 $u_t$ in terms of $x_t$ 的closed-form值，从而V( $x_t$ )可以表示为Q( $x_t,u_t$ )从而带入closed-form可以只表示为 $x_t$ 的式子。然后迭代回前一步的 $Q(x_{t-1},u_{t-1})$ 可以表示为含有 $(x_{t-1},u_{t-1},V(x_t))$ 的式子,但其中的 $V(x_t)$ 可以表示为 $x_t$ 的式子，而根据式10-7重的第一项， $x_t=f(x_{t-1},u_{t-1})$ ，带入 $V(x_t)$ 从而使得 $Q(x_{t-1},u_{t-1})$ 可以表示为只含有 $(x_{t-1},u_{t-1})$ 的式子，此时就可以求解 $u_{t-1}$ in terms of $x_{t-1}$ 的closed form了。迭代会前一步进而求得直到第一步的closed form值。（问题：是不是需要保证trajectory足够多？）这样在知道了第一个state之后，根据这些closed form可以推出要做的action：

式10-8

注意，这样求得的closed form值实际上是求最小化极值，而我们用当前的Q值来近似V值，所以是在做min of Q on action:

式10-9

对于stochastic state transition，如果transition符合高斯分布，那么在closed-form下最优解仍旧跟式10-8一样。

对于Nonlinear case，我们用iteration LQR来解。此方法是跟Newton's方法很像。任何nonlinear的函数都可以用linear-quadratic来近似：

式10-10

如果f用二阶来近似，就是differential dynamic programming (DDP)方法。

关于DDP的一些文章

Lecture 11: Model-Based Reinforcement Learning

上一课讲得都是关于我们在知道了state transition之后，如何通过planning（backpropagate）来求解。本课是关于当我们不知道transition是什么样的时候，我们或者全局的fit我们的transition model或者局部的fit，从而可以使用LQR去做planning。

Global Model

全局fit通过以下的步骤完成：

式11-1

这种方法在classical robotics学习物理模式里面很常用。但是第一步同样会导致跟imitation learning一样的distribution drift问题。所以类似于DAgger，我们也用新的action来补充训练语料：

式11-2

但是注意，第四步中，我们实际上是在执行一个非optimal的actions，如果每一步都有可能偏离正确的action，那么最终我们collect的数据会偏离真实的数据很多。修正的方式是每次只做一次action而不是一系列action，然后再根据collect的data重新计算当前action，从而防止单步错误影响后续过多（问题：DAgger如何起作用的？）：

式11-3

其中的第二步可以通过Gaussian Process，或者neural network，或者GMM。

对于Markov decision process，如果policy和state transition是deterministic的，而且state和action是连续的，我们可以直接把reward当做label来进行监督学习来学习policy和state transition。但是随着T的增大，会跟RNN一样遇到导数vanish或者exploding的问题。而我们又不能像LSTM一样设计特殊的结构给它。

Local Models

局部方法在对式10-6进行求导的时候，用linear model来近似。但是同时要保证trajectory在优化前后不要差别太大。通过用KL divergence来约束。

Lecture 12: Advanced Model Learning and Images

Model-based RL容易在开始的时候就陷入过拟合。原因是式11-3的第三步在选择action的时候可能会根据一些noise的case而过拟合于一个state。那么我们是否可以加入uncertainty来衡量我们对于是否要做某个action的信心？

在NN网络结构下，我们可以通过类似于集成学习的方法来训练多个网络，然后查看variance。训练多个网络的训练数据要保证独立性，所以选用bootstrap方法。但是实际上不太需要重新选择数据。

在Gaussian Process结构下，使用moment matching来查看variance。

Model-based RL on 图像

在使用Model-based RL在图像上，如果我们是partial observation，那么我们是否可以从当前observation上学习到state，从而根据学习到的state来做policy。第一种学习图像的state embedding的方法是autoencoder。或者可以直接用cnn来跟rl模型一起学习。但是如果state需要embedding后才能得到的话，reward就不能直接得到了（问题：为什么？），一种方法是直接把目标图片的embedding作为reward衡量。

或者我们是不是可以直接丢弃掉之前的方法，直接从observation里面学习到下一个observation。这个是图片领域是很火的一个方向：video prediction。

Lecture 13: Learning Policies by Imitating Other Policies

前面两课都是关于如何根据已知的或者学习到的transition model来直接做planning选择action。本节课主要关于如何利用transition model来帮助policy模仿最优控制。

Guided policy search

对于deterministic policy，实际上我们是在求解：

式13-1

此式等价于

式13-2

根据拉格朗日乘子法可以等价变换为在优化：

式13-3

Guided policy search求解上式为：

式13-4

也就是先用iLQR算法求解最优的trajectory，再求解对应的最优的policy。所以此方法是模仿学习，或者可以被看成是有约束的trajectory优化方法。

如果我们对多个trajectory进行优化，那么就可以学习到一个generalized policy了：

式13-5

优化方法变为：

式13-6

对于stochastic policy，式13-2就变成了：

式13-7

我们可以用局部高斯分布来近似policy分布：

式13-8

那么优化方法的第一步就变成我们想要根据下式优化 $p(\tau )$ :

式13-9

Imitating optimal control with DAgger

DAgger（Dateset Aggregation）通过让人额外标注policy新产生的数据来增加训练语料的鲁棒性。那么我们是否可以利用MCTS来帮助我们标记policy产生的数据来做DAgger：

式13-10

但是第三步会产生非常drift的数据，考虑自动驾驶技术，如果偏离太多会造成灾难。这里采取的方法是保证不要偏离太多，即使用跟学习到的policy相似但是cost尽量小的action：

式13-11

但是相比Guided policy search，DAgger有一个假设，即初始给的expert训练语料是最优的。但是GPS就不需要这个假设，因为他可以学习调整expert。

Imitation优势

GPS和DAgger这种imitation learning的方法相比policy gradient或者Q-learning的好处是：（1）式13-6的第一步是在做planning，第二步是在做监督学习，而这两种方法相比model-free方法都稳定了许多。（2）对于observation不足够学习planning但是可以学习policy的时候，那么可以用full state做planning，但是用observation来学习policy。

Dyna

还有一种利用transition model的方法是使用model作为model-free算法的simulator来产生数据。Dyna就是使用model来直接计算式7-8，而不是像式7-7的方式还要近似：

式13-12

也就是在第三步中计算transition model然后第四步使用它来更精确的更新Q。

上面的是最初始的版本，现在更general的Dyna是：

式13-13

也就是在第二步学习到了transition model之后，利用它来simulate训练数据给model-free RL。相比单纯的model-free RL方法，此方法只用simulator来产生数据，节省了很多时间和资源。相比单纯的model-based RL方法，此方法第四步产生的state是随机的真实state，相比式11-3中的第四步只能根据初始的state来产生训练数据，现在的方式得到的数据更多样跟真实分布更接近。

各类算法比较

各类算法根据需要数据量大小来排序是：

式13-14

可以看到A3C相比TRPO或者PPO需要十倍多的训练数据，而后者相比Q-learning也需要十倍多的训练数据。Model-based RL方法需要的数据最少。

但是如果我们按照优化时间的长短来排序，那么就正好是反过来了。

所以如果我们有一个simulator，而且不怎么花费时间来产生数据，那么就用TRPO或者PPO。反之就用Q-learning。如果我们没有simulator，那么如果产生真实数据代价不大就用Q-learning，反之就用model-based RL，尽管其优化比较耗时。

Lecture 14: Probability and Variational Inference Primer

所谓latent variable是指从输入x到输出y中间还依赖其他的变量z。比如在lecture2中处理问题3：Multimodal action时，一共三种方法，都是如何利用latent variable来求解最终y。

第一种方法是输出用混合高斯来表述：

式14-1

可以简单的假设等式后面的每一项都是高斯分布。

第二种方法是Latent variable models，现在假设我们在学习x的分布，即p(x)。尽管p(x)不是一个高斯分布，但是通过加入一个条件z，变成

式14-2

即 $p(x|z)$ 是一个关于z的高斯分布，而z也是一个高斯分布。所以最终表示出来的x是一个类似混合高斯的multi-model形式。

在model-based RL中，我们用g来表示从observation到state的映射。但是实际上我们想要的是从前一个state到后面一个state的映射，而它是通过前一个state到后一个observation再到后一个state的映射，所以observation是latent variable。

如何训练latent variable model

最大似然估计方法是：

式14-3

写成latent variable的形式是：

式14-4

此时是完全intractable的。其中p(z)是我们不知道的分布。但是我们可以把z的分布写成依据每一个 $x_i$ 都有不同对应的高斯分布的形式，即：

式14-5

那么式14-4可以写成：

式14-6

式14-7

等式后面的我们表示为 $L_i(p,q_i)$ 。最后面的一项（带负数）实际上是 $q_i$ 的entropy，z越random其值越大。对于高斯分布也就是方差越小其值越小。那么maximize上式实际上是在对第一项当 $p(x_i,z)$ 确定的情况下， $q_i$ 的分布越能在 $p(x_i,z)$ 的高峰分布概率越大越好，但是第二项同时又保证了 $q_i$ 的方差越大越好。这两项合起来就是在保证 $q_i$ 能尽量cover并贴合 $p(x_i,z)$ 的分布。

另外对于 $q_i(z)$ 和 $p(z|x_i)$ 的KL-divergence有：

式14-8

也就是

式14-9

其中

式14-10

而式14-7中我们得到

式14-11

根据式14-8我们知道最后面一项是不依赖 $q_i$ 的，所以优化 $L_i(p,q_i)$ with respect to $q_i$ 就等于优化KL-divergence with respect to $q_i$ ，根据式14-9也就等于优化 $p(x_i)$ 。所以优化式14-10中的后面一项不仅仅是前面一项的lower bound还是等价于前面的。

所以根据式14-10，我们现在来优化：

式14-12

参数更新方法为：

式14-12

即首先对 $\theta$ 进行更新，需要根据p进行求导，在求导之前，z需要从当前的分布 $q_i$ 中sample一些值来近似式14-10中的期望。而因为 $q_i$ 我们假设是一个高斯分布，那么式14-10中的期望就很容易代入高斯分布的均值和方差来求其导数。

但是对于每一个 $x_i$ 我们都有一套对应的参数需要求解。这样参数量是巨大的。我们是否可以利用神经网络来做泛化呢？既然我们是在保证式14-8的KL-divergence最小，那么是否可以用如下近似

式14-13

即学习如下的一个网络

式14-14

然后 $p_\theta(x|z)$ 通过如下网络得到：

式14-15

这样一来，参数更新方式就变为：

式14-16

其中：

式14-17

式14-16中如何对 $\phi$ 进行求导呢？考虑式14-17中的第二项，直接用entropy的方法求导就行。第一项则跟我们policy gradient形式很像。所以可以直接用policy gradient的方法求导。但是policy gradient的问题high variance同样在这里会存在，因为要进行sample。另外一种方法就是reparameterization trick：对于continuous的z，如果可以假设 $q_\phi(z|x)$ 是一个关于x的高斯分布，那么可以变形为：

式14-18

其中 $\epsilon$ 是一个标准高斯分布。这样一来式14-17中的第一项就可以变形为：

式14-19

那么此时在sample的时候只需要从标准高斯分布中sample数值就可以了。此方法相比直接对式14-17进行求导的好处是，式14-17中我们需要对所有的[]里面的值进行sample，但是这里只需要对 $\epsilon$ 进行sample就可以了，variance更小。

把式14-14跟式14-15结合到一起，实际上就是variatinal autoencoder：

式14-20

而通过调节 $\epsilon$ 我们就可以得到不同类型的图像。在测试阶段测试方式为（问题：如何测试？）：

式14-21

其实其目标函数从式14-17形变为：

式14-22

最后一项也就是在保证求的的q跟z的原始分布接近。这样一来我们的式14-21得到的测试结果才可信。

Conditional models

以上我们都是在求解p(x)，那么如何求解p(y|x)呢？目标可以类似的变化为：

式14-23

即在输入的时候加入一个高斯干扰z，学习网络为：

式14-24

这样在测试阶段测试方式是：

式14-25

Lecture 15: Connection between Inference and Control

class：deep RL UC Berkeley