这是一篇深度强化学习视频的笔记 https://www.bilibili.com/video/BV1XP4y1d7Bk
什么是强化学习
强化学习方法分为三类：Policy-based（训练一个actor，例如 policy gradient）、Value-based（训练一个critic，例如 Q-learning）、Actor-Critic
所谓的actor就是一个agent，即决策者，它能根据一个输入状态，输出一个行为。例如输入一帧游戏画面，它输出前进还是后退等，然后系统根据游戏结果给出相应奖励
所谓critic就是一个预言家。它用来预测某个人执行某种行为的预期结果
某人（actor）问预言家：我现在破产了（当前状态），如果我去抢银行或者去打工（可以采取的动作），我会得到什么后果？预言家说：如果你去抢银行，你会被抓住，后半生就在监狱度过，如果去打工，由于你的人品不错，你会遇到一个贵人，他会让你飞黄腾达（对这个人采取某个行为的预言）。
事实上，上面问预言家（critic）的过程就是Actor-Critic，actor不会真的去抢银行或者打工，他只是提出这个做法，让critic去评价，然后他得到这些评价内容后来审视自己，比如说他知道打工会遇到贵人是因为自己人品好，他就会让自己人品更好，而预言家看到了这个人的改变后又会给出新的预言，两者不断更新
关系梳理
下面的图来源于《深度强化学习》一书，我觉得这些图对学习强化学习的路径规划有很强的指导意义
强化学习在人工智能领域的位置
强化学习算法分类：
在线策略和离线策略分类
蒙特卡罗法（MC）和时序差分法（TD）分类
value-based 和 policy-based 方法分类
基于模型的方法和无模型的方法分类（不是深度学习模型，是数学模型）
policy gradient
每一局游戏都是由 状态-动作-奖励-状态-动作-奖励。。。不断循环进行的
\[ trajectory τ = {S_1, a_1, r_1, S_2, a_2, r_2…, S_T, a_T, r_T} \]
所以一个trajectory发生的可能性为：
\[ p_θ(τ) = p(S_1)p_θ(a_1|S_1) p(S_2|S1, a_1)p_θ(a_2|S_2)p(S_3|S_2, a_2)… = p(S_1)\prod_{t=1}^Tp_θ(a_t|S_t)p(S_{t+1}|S_t, a_t) \]
对于任意一个trajectory来说，它的total reward为：
\[ R(τ) = \sum_{t=1}^Tr_t \]
那么对所有trajectory来说，它的reward期望就是每个trajectory发生的概率乘以其total reward：
\[ \overline{R}_θ = \sum_τp_θ(τ)R(τ) =E_{τ\sim p_θ(τ)}[R(τ)] \]
意思就是trajectory τ服从\(p_θ(τ)\)分布下，\(R(τ)\)的期望
强化学习的目的就是最大化这个\(\overline{R}_θ\)，也就是让模型玩游戏每一局都尽可能得高分。
最大化\(\overline{R}_θ\)可以使用梯度上升的方法，具体来说就是计算出\(\overline{R}_θ\)的梯度，然后在训练的每一个epoch后都让模型的参数θ加上\(μ\nabla \overline{R}_θ\)（学习率乘梯度），\(\overline{R}_θ\)的梯度计算方式为：
\[ \begin{align} \nabla \overline{R}_θ &= \sum_τR(τ)\nabla p_θ(τ) \\ &= \sum_τR(τ)p_θ(τ) \frac {\nabla p_θ(τ)}{p_θ(τ)} \\ &= \sum_τR(τ)p_θ(τ)\nabla logp_θ(τ) \\ &= E_{τ\sim p_θ(τ)}[R(τ)\nabla logp_θ(τ)] \\ &≈ \frac {1}{N}\sum_{n-1}^NR(τ^n)\nabla logp_θ(τ^n) \\ &= \frac {1}{N}\sum_{n-1}^N\sum_{t=1}^{T_n}R(τ^n)\nabla logp_θ(a_t^n|S_t^n) \end{align} \]
注1：式子后面的N表示你采样了多少个τ，因为不可能真的将所有的trajectory都遍历出来，只能使用部分的均值代替期望
注2：最后一项是将前文中的\(p_θ(τ) \)带入式子得到的，可以发现少了一项\(p(S_{t+1}|S_t, a_t)\)，这是因为这一项是由游戏机或系统本身所决定的，虽然它本身可能是一个随机变量，但它和模型没有关系，这里就简化为假设它的值就是1。
为什么可以进行无监督学习？
可以将整个actor看作是一个二（多）分类问题：给模型一个输入S，模型输出每个action的概率，即对S进行分类。与分类问题不同的是，在计算参数的梯度时，多乘了一个\(R(τ)\)，这也是模型可以训练的原因：
多分类问题在训练时往往需要ground-truth作为监督信号，但强化学习往往是没有ground-truth的，假如某个游戏的reward总是正的，那么模型在训练过程中实际上是在提高每个采样的trajectory发生的概率，但是由于乘了一个\(R(τ)\)，所以每个trajectory发生概率提高多少是不一样的，如果某些trajectory提高的较多，而另外一些提高的较少，总体而言，或者做norm之后，那些提高较少的trajectory实际是在降低概率的。就好比所有人都在卷，你虽然也在学，但是别人进步的比较多，相较而言你就是在下降。
总的来说，这里的\(R(τ)\)可以看作是对在S状态下执行a这个action的好坏评分。
梯度计算方法的改进
改进1：上面说到，强化学习训练过程实际上是在增强每一个采样结果发生的可能性，只是有些增强得多有些增强得少，增强得少的相对来说其实是在做抑制，那么那些没采样到的trajectory是不是一定在做抑制呢？假如某种策略是一种比较好的策略，但就是因为没采样到导致学不到这种策略，如何解决？
可以在总的reward上减去一个baseline（下面式子中的b），强行让reward有正有负，这样一来，那些没采样到的就可能不会被抑制了，甚至可能会增强。b的取值可以是之前reward的均值或者是经验值，甚至可以是一个模型的输出
\[ \nabla \overline{R}_θ = \frac {1}{N}\sum_{n-1}^N\sum_{t=1}^{T_n}(R(τ^n) – b)\nabla logp_θ(a_t^n|S_t^n) \]
改进2：从上面的公式可以看出，在一个trajectory中，里面所有的action都乘上了该trajectory的total reward，这可能是不合理的，因为整局游戏结果的好坏，并不表示整局游戏中所有的action都是好的或者坏的。一个trajectory中的一个action的好坏应该只取决于执行这个action之后几步游戏的得分，或者说在某个action执行前，它前面的得分应该和它没关系，而它后面的得分应该是离它越远关系越低，所以还需要在之后的得分中乘以一个折扣因子 γ：
\[ \nabla \overline{R}_θ = \frac {1}{N}\sum_{n-1}^N\sum_{t=1}^{T_n}\sum_{t’=t}^{T_n}γ^{t’-t}r_{t’}^n-b\nabla logp_θ(a_t^n|S_t^n) \]
不管是 \(R(τ)\)、\( R(τ^n) – b \) 还是 \( \sum_{t=1}^{T_n}\sum_{t’=t}^{T_n}γ^{t’-t}r_{t’}^n-b \) 它们本质上都表示在状态S下，模型选择动作a的一个评价指标（状态s下，选择动作a相对于选择其他动作有多好），它当然还能有很多其他的形式，所以将它们简写为 \( A^θ(S_t, a_t) \)
on-policy VS off-policy
如果和环境交互的模型与正在训练的模型是同一个，则是on-policy的，否则是off-policy的
为什么要off-policy？
好处在于可以重复使用数据，如果是on policy的，必须使用策略玩一局游戏更新一次参数。而off policy则可以让交互模型和训练模型不是同一个，即可以重复使用数据。
PPO
在off-policy中，因为策略的采样和目标模型使用的是两个模型，则需要对reward进行修正，也就是在reward前乘以一个矫正参数，这个参数是 \( \frac{动作在采样模型中的概率}{动作在目标模型中的概率} \)。
由于采样不均匀可能导致样本分布差别很大，进而导致上述参数较大或较小，所以可以想办法让这个参数更稳定。
PPO有两种方法，其中一个简单的方法是对这个参数进行裁切。当它大于或小于某个值时就使用上下阈值。
Q-learning
policy gradient训练的是一个actor，也就是给定一个输入状态，让模型直接决定输出什么action。而qlearning则并不直接决定action，它假设已经存在一个策略Π，目的是得到一个状态价值函数\( V^Π(s) \)（critic），它只是用来评价策略Π选择的action的好坏，如何评价一个action的好坏呢？做法是计算策略Π采取某个action后可能得到的累计reward的期望值作为评价标准（在某个S下使用策略Π得到一个action后，进入下一个S继续使用策略Π。。。所能得到的累计reward期望值）。由此可以看出\( V^Π(s) \)其实是和策略Π密切相关的，策略Π的改变也会引起\( V^Π(s) \)的变化
如何得到\( V^Π(s) \)？
1. Monte-Carlo（MC）based 方法
前面说，\( V^Π(s) \)其实是在估算策略Π在遇到状态s采取行为action后的累计reward期望，所以可以使用神经网络来拟合\( V^Π(s) \)，具体做法是使用策略Π玩n场游戏（n个trajectory），计算在每场游戏中，采取一个action后得到的累计reward（使用G表示），然后将该action作为input输入到模型，使用G作为监督量，其实就是一个回归模型。
由于reward可能是一个随机变量（相同状态下采用相同的action也可能得到不同的reward），所以每次采样时即使状态和action都相同，得到的累计reward也可能偏差很大，这就导致算法的不稳定。
2. Temproal-difference （TD）based 方法
MC based方法的一个要求是必须玩完一整场游戏才能计算累计reward G，有些游戏可能流程较长，则可以使用TD的方法：假设玩某局游戏的中间部分流程为：\( … S_t, a_t, r_t, S_{t+1}… \)，那么可以得到 \( V^Π(S_t) = V^Π(S_{t+1} + r_t) \) （游戏中，前一步得到的累计reward等于前一步得到的reward加上后一步的累计reward），这是一个递归函数，它最终也会达到收敛状态。
相较于MC，单步的reward相较于累计reward的方差肯定更小，算法可能更稳定，但是它对G的估算可能不准确，例如 3-2=1，4-3=1，两者的差值都是1，但G是不同的。但是随着训练次数的提高，模型趋于收敛状态时，最终也会得到正确的结果。
一般使用TD多
q-function
qfunction是一种critic，也就是对某个策略Π的评判标准（得到q value），它有两种形式：
- \(Q^Π(s, a) → scalar \)
- \( Q^Π(s) → [(scalar1|a1), (scalar2|a2), (scalar3|a3)…] \)
对于形式2，它只能用作评估离散action
critic如何用作action的决策
前面说到，critic只是用来评判策略Π，事实上，如果可以得到一个策略Π的critic，就可以使用这个critic更新原来的Π得到Π’，新得到的Π’一定比原来的Π更好，然后就重复这个循环，直到找到最好的策略Π
如何根据critic找到更好的策略Π？其实就是让策略Π‘每次都采用Π中价值最高的action，参见 马尔可夫决策过程
可能用到的trick
target network
使用两个一样的网络，一个网络作为target network，固定住其参数，计算t+1时刻s和a的累计reward作为被训练网络的目标G，并每过几步再次同步两个网络的参数。这种做法使得训练过程更稳定
探索
如果每次都采用价值最大的action，则可能错过真正最好的action，所以可以设置一定几率进行探索：
- Epsilon Greedy：设置一个阈值，当随机变量小于该阈值则采取随机action
- Boltzmann Exploration：将所有action的q value作为一个被采样的概率
replay buffer
数据制造线程：初始化一个长度为n的buffer队列，使用策略与环境做互动，互动的结果就放进buffer，buffer满了就移除最早的元素
数据使用线程：模型的每个epoch都随机从buffer中取得一批数据（并不会删除数据）进行训练
两个线程同时工作，可以提升训练效率，一个问题是，这样一来buffer中可能存在多种不同的策略与环境交互的数据，这就相当于是off-policy的做法了（与环境交互的策略和训练的策略不是同一个），但其实这样问题也不大，因为buffer中都是比较相邻的策略得到的交互结果，差别不是很大，另一个主要原因是，如果使用的是TD的方法，则buffer中存的只是两个action的reward的差值，这个差值实际上和策略是无关的。
Double DQN
double dqn是解决累计reward被高估的问题的，为什么使用DQN是会高估累计reward？
详见 Double DQN
因为DQN每次都是选择q value最大的那个action，而这个q value也是模型拟合出来的，它很有可能是被高估的（被高估才有可能成为q value做大的action），那么多步action的q value都被高估，那么它们累加起来就被高估更多了。
一个解决办法是使用两个网络，网络1用来选择q value最大的action，然后将该action带入网络2来计算它在网络2中的q value，将其作为预期的q value。这样一来，虽然网络1高估了某个action，但是网络2很有可能没有高估，进而得到的q value也更接近真实值
前面提到可以使用两个网络（被训练网络和一个target网络）来提高训练的稳定性，正好这里就能使用那个target网络作为q value的修正网络（网络2）。
Dueling DQN
之前的q function输入s直接得到的是每个action的q value，而dueling DQN输出所有action的“基本 qvalue”和一个标量，真正的qvalue是这个“基本 qvalue”加上这个标量得到的。可以想象，在使用TD方法时，3-2=1，4-3=1，它们结果相同但值不同，而这里的“基本qvalue”就相当于计算这个差值，而新的标量则是对“基本qvalue”的修正
prioritized reply
对replay buffer中的数据加权，使得一些差距较大的数据被采样训练的几率更大
multi-step
结合MC和TD两个方法，TD中差值只是两个连续的action的reward的差值，而multi-step则是采样多次的action，计算多个reward的累计差值
Noisy Net
在q function 网络参数中加随机噪声，这样即使每次选择qvalue最大的action，但选择的action其实也具有一定的随机性了，相当于做了探索
Distributional Q-function
qfunction输出的是累计reward的期望值，那么能否直接输出累计reward的分布呢，然后从该分布再采样一个期望值。
以下是某篇文章将这些技术做对比，其中 Rainbow是将所有技术都加到DQN中，因为这些技术本身就是不冲突的。左图是分别在DQN中加入各种技术得到的模型性能，用于查看单独使用哪种技术提升最大，值越高越好。右图是将所有的技术同时用在DQN中，并减少其中一项技术得到的性能，用于查看哪个技术最不重要
Q-learning 比 policy gradient 更稳定，更容易训练出结果
policy gradient 是在鼓励所有采样的action，只不过有些鼓励得多有些少而已，相对来说就是有些下降有些上升，而且由于采样得到的累计reward本身就是一个随机变量（同状态同一个action可能reward不同），这就更增加了算法的不稳定性。而Q-learning则是一个回归模型，因为你使用一个策略执行一个action后，累计reward是固定的，所以可以用它来作为监督量。
也就是说，policy gradient是没有明确目标的，采样得好则训练得可能更好，但具体能达到什么水平，不知道，而Q learning则是有具体的目标的
大概是这么个意思，但总觉得还是有点抽象，下来再百度一下
Actor-Critic
这是上文中提到的计算policy gradient的梯度的方法：
\[ \nabla \overline{R}_θ ≈ \frac {1}{N}\sum_{n-1}^N\sum_{t=1}^{T_n}\sum_{t’=t}^{T_n}γ^{t’-t}r_{t’}^n-b\nabla logp_θ(a_t^n|S_t^n) \]
上式中的 \( G_t^n = \sum_{t’=t}^{T_n}γ^{t’-t}r_{t’}^n \) 是模型在某个trajectory中的某个s下使用action得到的累计reward（G_t^n），这个累计reward是采样得到的，但是因为累计reward可能是一个随机变量，导致即使是在相同的S下使用相同的action也可能获得不同的累计reward，所以上式中的 \( G_t^n \) 也是不稳定的，一个好的做法是这里不使用采样得到的累计reward，而采用该策略下的采用action后得到的累计reward的期望值，这不正是Value-based（Q-function）方法的功能吗？
\[ E(G_t^n) = Q^{Πθ}(S_t^n, a_t^n) = r_t^n+V^Π(S_{t+1}^n) \]
而前文也说了，上式中的baseline（b）其实就是在某个状态S下，使用策略Π可以得到累计reward的期望（注意这里指的是在S下采用所有action得到的累计reward期望，而上面的\( G_t^n \)指的是在S下采用某一个action得到的期望）
\[ b = V^{Πθ}(S_t^n) = \sum_{i=actions}Q^{Πθ}(S_t^n, {a_i}_t^n)p(a_i|s) \]
故，将这两者带入前式就得到了 Advantage Actor-Critic（A2C，就是Actor-Critic将Q function使用Value function代替后的结果，即上式\( E(G_t^n) \) 公式中第二个等号的结果，否则需要训练两个网络：Q function 和 Value function）：
\[ \nabla \overline{R}_θ ≈ \frac {1}{N}\sum_{n-1}^N\sum_{t=1}^{T_n}(r_t^n+V^Π(S_{t+1}^n)-V^Π(S_t^n) )\nabla logp_θ(a_t^n|S_t^n) \]
如此一来，我就有两个网络需要训练：actor和critic，可以使用类似GAN的训练的方法。
具体过程为：初始化一个策略Π（就是actor那个神经网络），使用这个Π与环境互动得到n个trajectory数据，再使用这些数据去训练价值函数 \( V^Π(S) \)，再使用这个价值函数代到上面公式中训练actor（policy），得到一个新的策略Π’，再使用这个新的策略与环境互动。。。
A3C（Asynchronous Advantage Actor-Critic）
将一个网络复制多份，每份都单独训练得到一个梯度，再将梯度传回给中心网络，中心网络使用该梯度更新自己的模型参数，再将更新后的参数返回给子网络。这个过程中可能遇到子网络向中心网络传递的梯度已经是基于之前训练的模型参数得到的了，但A3C选择忽略这个问题，它假设每次迭代前后的参数差距不大。
Pathwise Derivative Policy Gradient
TL;DR：在QLearning中，每次做决策都是使用 argmax(Q(s, a))，即在所以a中选择q value最大的的a，并且在递归计算时，计算 \(S_{t+1}\) 的累计reward也是直接取得最大q value的a（max(Q(St+1, a))）。这里新的方法就是将选择q value最大的a这一步使用一个网络来生成，而不是直接使用 argmax 或者 max。然后再单独训练这个网络，使得它有max的效果。这个网络其实就是一个actor，所以这个方法也是 Actor-Critic 的一种。
这么做的好处在于解决了qlearning对连续action的局限性。
从Actor-Critic训练过程可以看出，Qfunction（或者value function）仅仅是用来估算在状态S下采用action的累计reward（G）期望，这其实和policy gradient本质上是一样的，只不过由于这里的G不再是随机变量了，使得训练过程更加稳定。
qfunction(s, a) 的本质就是在固定的状态S下，评估a的好坏。那么，我假设我现在已经存在这个一个qfunction了，我需要训练出一个actor Π，它可以根据s输出a，那么我只需要最大化函数 \( Qfunction^Π(s, Π(s)) \) 即可（这里的Qfunction的固定权重的，但前文也提到，qfunction其实是依赖于策略Π的，所以这里其实也是假设Qfunction依赖的Π与被训练的actor那个Π的差别不大）
整个训练过程为：假设存在一个策略Π，让它与环境交互，生成一堆数据，使用这些数据训练Qfunction，然后固定住这个Q，训练一个actor，它直接输入一个action，然后将这个action输入到固定参数的Q中得到Q的输出，使用梯度上升的方法最大化这个输出，也就是让actor输出s下最好的a，训练完actor后得到一个新的策略Π，重复上述步骤。最终得到一个actor和一个qfunction。
事实上，这就是一个GAN网络，Qfunction就是discriminator，actor就是generator。
它和上文中A2C的方法有什么不同呢？
懵懵懂懂，似懂非懂
Sparse Reward
奖励的点比较少，例如一局游戏中，仅仅在游戏结束之后才能得到reward。对强化学习是一个挑战。可行的方法有：
reward shaping：刻意设置一些原本不存在的reward来引导agent
curriculum learning：从目标反推，例如训练从1走到4，可以先训练从3走到4，再训练从2走到4等
Hierarchical RL：多层agent，上层agent负责任务拆分，下层负责执行，最上层的输入就是最终目标，最下层输出就是action，但不知道具体应该怎么做
Imitation Learning
假如根本没有reward应该如何学习？例如聊天机器人如何定义是否聊得好。可行的方法有：
behavior cloning：其实就是有监督学习，例如先采集人的开车数据，然后将人的行为数据作为监督量，将看到的画面作为输入训练一个神经网络。局限性在于假如遇到采集数据中没遇到过的情况，机器就不知道该怎么办了，并且还会学习一些本来无用或者错误的行为
inverse RL：使用采集的expert的数据来反推出一个 reward function，然后再使用这个reward function 来训练agent。如果根据expert的数据得到reward function？可以使用类似GAN的方法，假设expert的行为是最好的，初始化一个actor，让它与环境交互得到一些数据，然后初始化一个reward function（网络模型），分别将expert的数据和actor的数据输入进去得到两个reward，训练reward function使得expert的reward越大越好，而actor的reward越小越好，然后使用新的reward function重新训练一个actor，重复上述步骤即可。可以用来学习不同的expert行为风格，通常不需要太多的训练数据。