最近因为项目和论文的关系需要用到一些 Deep Reinforcement Learning 的知识,于是快速把 DRL 的一些基本算法和思想过了一遍。之前赶时间寥寥草草地写了七八页纸,现在因为 COVID-19 导致各种 DDL 推迟了以后便有了一些空闲时间,觉得还是记录在博客比较好。个人觉得 RL 这个东西思想是很精妙的,但如果只是要了解一些比较粗浅的东西,学习成本很低,完全可以几天内掌握个大概。

由于我比较懒,这篇博客主要是写给自己看的,可能有些地方不会解释得太清楚 : )

DRL 中的 Policy Gradient

强化学习实际上是一个机器与环境不断互动和学习的过程,其中包括几个重要的组成部分:

  • Agent: 与环境互动的智能体
  • Environment: 与智能体交互的环境
  • Reward Function: 环境给予智能体反馈的方式

举个例子,比如使用强化学习玩游戏,那么理论上的一个流程就是:

  • 初始化一个 agent
  • agent 接收环境所给的第一个界面,也是输入第一个 state:
  • agent 给出一个对应的反应:
  • 环境接收 给出对应的

重复上述流程直到游戏结束。

我们认为从游戏开始到游戏结束是一个 episode,用 表示。然后在这个玩游戏的过程中,举个例子:假设这个游戏是我们熟知的雷电(飞机大战游戏),用户需要操作飞机左右移动以避开飞来的陨石等障碍,同时又要主动出击才能获得比较高的分数。我方战斗机便可以看作强化学习中的 agent,周围的陨石,敌机等无法控制(含有随机性)的东西就是与我们 agent 交互的环境。

为了让我们的 agent 在玩游戏的过程中逐渐掌握游戏的技巧,我们需要设计 reward function, 也就是设计一个反馈机制。其实游戏本身是含有这样的反馈机制的,比如击落一架敌方战斗机可以获得多少分,吃到补给可以获得多少分,被子弹击中扣多少分这样。agent 做出的每一步,或多或少都在改变着最终的游戏结果。

我们把整个 episode 最终获得的分数用 reward function 表示为:

深度强化学习,之所以称为深度强化学习,是因为我们的 agent 实际上是一个 DNN,给定某个 state 输入,针对这个输入输出对应的 action,学习的过程实际上就是在 update 这个 DNN 的参数,使得最终一个 episode 下来全局的 reward function 可以达到最大值。

其中,我们把一个 agent 进行玩游戏的策略称为一个 policy, 用 表示,不同的 表示不同的游戏策略(不同的 agent), 我们要做的就是求给定 的最大值, 这里我们可以用梯度增加的方式计算:

为了准确更新神经网络的参数,我们需要尽可能多的获取一些游戏数据,在一个相同的 policy 下,我们可能会进行非常多场游戏,所以计算多场游戏的平均 reward 就是:

求梯度:

为了方便实现最终将式子写成了上述形式,其中 是第 n 个 episode 的 reward 总和, 代表的意思是在第 n 个 episode 里面,总共有 个 step (一个 step 定义为给定一个 state s, agent 做出一个反应 a)。

这个式子是非常好理解的,为了让最终的 policy gradient 有最大值,当某个 step 发生的那个 中有相对较大的 ,我们就要增加其出现的概率,反之,如果 reward 的值太小我们就要减小这个操作所出现的概率。

上述公式中用了一个近似,在给定分布求期望的过程中:

这里的 N 越大,实际上相当于在 p(x) 分布上 sample 到的值越多,结果也就越接近。

另外一个小技巧是:

我们可以通过分子分母同时乘上一个 中梯度运算中拿出来:

更精准的 Reward Function

改进的

在上述公式中,实际上存在着一些问题,其中最大的问题就是:该如何定义我们的 reward function ?如果仅仅是按照游戏的规则来, 是游戏中的每一步所产生的 reward 在整场游戏中的累加,在式子中:

有些 action 是好的,有的是不好的,但是所有的 action 的概率前面都会被乘上同样的 weight: ,显然是不合理的。

那么如果我在给定某个 后 agent 输出了 ,实际上它并不会影响到 之前的那些情况,在 发生之前的 reward 实际上是和 无关的。

举个例子,一个简单的游戏我们玩了两场:

State
Action
Reward +10 +0 -6
State
Action
Reward -5 +0 -6

那么 在第一种游戏情况上就会被增加出现的概率 (乘上 4),而在第二种情况下同样的场景和操作就会被降低概率 (乘上 -11),这是不科学的,第二场游戏之所以不好,是因为在 之前的 产生了 -5 的 reward,这个实际上和 是无关的。但是 之后的是和它有关的, 可能正是要发生在 之后才会带来 -6 的 reward。

所以我们可以使用某个特定的 之后的所有 reward 总和来代表 的 reward,而不是全部 reward 的总和。为了表示计算 reward 的方法,我们引入 advantage function: ,在之前

我们把改进的 reward 计算式 代入

得到

另外,我们可以给 加上一个影响力衰弱参数 ,因为时间拖得越长,越前面发生的事件对后来的影响就会越小:

添加 Baseline

有些游戏中,游戏者无论采取何种 action,reward 可能的情况全都是正的,这个从理论上来说并不会出现问题。但是在 sample 数据的时候,如果 sample 的数量不够多,没被 sample 到的 action 保持不变,但是被 sample 到的所有 action 都会相应的增大,在 normalize 之后未被 sample 到的 action 对应的概率就减小了,但是我们能说没被 sample 到的 action 就不是好的 action 吗?

很显然不能,所以这里又有一个小的 tip:减去一个 baseline 使得 的值有正有负 ,一般来说这个 baseline 就是所有 reward 的期望:

代入得:

结合上面的优化方法:

On-Policy 到 Off-Policy

On-Policy 学习方式

理解了上述原理,之后要做的无非就是更新神经网络,on-policy 的意思就是:与环境交互学习的 agent 和被动更新的 agent 是同一个。具体的流程可以表示为:

  • agent 先初始化,并且与环境做互动
  • 在互动的过程中我们 sample 一定数量 (m) 的数据
  • 在积累了 m 个 的数据以后,我们用这么多数据去 update agent policy
  • 把用过的数据扔掉,重新与环境继续互动生成数据 (因为 policy 更新了,旧的数据没有参考价值)
  • 继续用新的数据 update agent policy

显而易见,on-policy 的方式是存在一定问题的,比如进行飞机大战的游戏,输入 DNN 的 state 是用 image 表示的,训练 -> sample -> 训练 这样的方式非常耗时,并且一旦原有的 policy 更新了以后,

上述梯度中分布 就变了,之前在老的 上面采样的数据就没用了,这意味着每次更新 policy 会浪费大量的数据,并且需要大量的时间进行 sampling。

所以针对这种 on-policy 研究人员希望能够在不影响 agent 与环境互动的前提下持续地对我们需要的 agent 进行更新,于是便有了 off-policy,这里主要讲 PPO/TRPO 和 PPO2 这几种方法。

Important Sampling

Important Sampling,它并不是 RL 里面独有的方法,简要来说就为了实现线下学习我们需要用一个不同的分布 去估计我们所需要的分布 。在 off-policy 中体现为:我们想用另外一个 去跟环境做互动,使用 收集到的数据去训练我们想要的 ,这个流程就像你让一个小朋友去看另外一个小朋友玩游戏,并从中学到游戏的方法。

通过这种方法 与环境互动获取到的数据可以被使用多次,并且不需要考虑 变化时数据就会失效的问题。

具体来说,important sampling 中用一个分布 来估计另一个分布 可以这样表示:

Proximal Policy Optimization (PPO)

将这种 important sampling 的方式应用到 policy gradient 上面,我们可以得到:

假设 ,那么上面的式子可以写成:

去估计 的分布,实际上就是用 agent 去和环境互动,根据其互动的数据去更新我们的 policy。这里 important sampling 其实有一个问题,虽然两个分布的 mean 是一样的,但是他们的方差是不同的,在 sample 数量不够多的话, 的方差就会变得很大,所以采样的时候我们应该尽可能的保持多的样本数据来保证准确率,同时要保证两个分布不能差别太大。

借助之前的公式 ,我们可以用 gradient 去反推原来的 objective function,得到函数

非常的直观:我们用 去做 demonstration 从而优化我们想要的参数 ,但是由于这个 objective function 牵扯到 important sampling,为了保证 important sampling 的效果,我们要让两个分布尽可能的相似,所以 PPO 就应运而生了: 在做训练的时候多加一个 constrain: ( 为常数),这一项代表着两个分布 之间的 KL 距离,减去这一项我们可以得到:

其中如果 越大 (即 越不相似),最终的 就会越小。通过优化这个式子求其最大值,我们可以达到更好的强化学习效果。

要注意的是,这里的 并不是参数上的距离,而是这些 action 之间的相似度。总的来说,PPO 的算法可以描述为:

  • 初始化一个 policy
  • 在每次迭代过程中:
    • 使用 去与环境交互,收集数据 并且计算
    • 找到 去优化 , 其中

那么对于 PPO 约束条件 中的 要怎么设定呢?实际上可以很直观地设定一个最大值和最小值,如果两个分布的 KL 距离已经到了最大值,然后整个式子还是没有起到明显的约束作用,就增大 。同理,如果距离小到了最小值,整个式子的值仍然偏大,这时候就需要动态减小 的值:

  • 如果 , 增加
  • 如果 , 减小

Trust Region Policy Optimization (TRPO)

另外一种方法叫做 TRPO: Trust Region Policy Optimization, 它和 PPO 唯一不一样的地方是这个 constrain 设计的方式有点不一样,它将约束条件放到了式子外面:

但是实际上实现 TRPO 的时候,式子外面的约束条件是非常难处理的,一般不推荐 (因为 PPO 和 TRPO 效果差不多,但是实现起来简单很多)。

PPO2

PPO2 算法是在 PPO 算法上衍生的另外一种算法,本质也是为了使得两个分布 的差距不要太大,数学表示为:

的意思是说:

这样就可以动态地将 的值限定在 之间,达到两个分布不会相差太多的效果。而取最小值是因为,当 时,我们希望 objective function 越大越好,但是一旦大过了 ,这个式子就不再有 benefit 了,因为不满足两个分布差别不要太大的这个约束条件,同理当 的时候也是一样。

Q-Learning

除了直接学习一个 policy,我们还可以从另外一个角度出发,去学习一个 critic,这也被称作是 value-based 的学习方法。Critic 就是一个评价者,去客观地评价你这个 action 做得好还是不好。

这里需要引入一个 state value function ,代表着在 state s 之后所有 reward 累加的期望值。 越大,意味着给定 state 开始到游戏结束,这个 agent 可能获得的 reward 就越多(前景越光明),在某种意义上来说,这就是一个 critic,但是目前的 只是一个 scalar function,不能够给出指导性的意见。

Monte-Carlo (MC) 和 Temporal-difference (TD)

那怎么去估计这样一个 呢?这里一般用两种方法,MC 和 TD,其中各有优劣。

MC 的方法很简单,一般来说 MC 会训练一个 DNN,给定一个 state 输入,这个网络返回预测的从 往后所有 reward 的总和 ,我们希望它与实际的总和 越接近越好。

简要表示就是这个样子:

另外一种方法是 TD,和 MC 有所不同的是,TD-based 的方法不用计算积累的所有 reward 和,意味着你必须走完整个流程直到结束才能够完成 MC-based 的估测,有的游戏非常耗时,使用 MC-based 的方法可能在短时间是无法获得多少数据的。

TD-based 的方法具体来说是针对每个 step,我们可以得到 ,那么从这个式子可以看出,对应的 实际上是满足:

具体的实现我们可以构造两个一样的网络 ,分别接收 ,之后我们将输出作差 ,尽量使得差值和给定的训练数据 保持一致。

这样我们就不需要整场游戏的所有 reward 和进行训练,能够通过差分的方式,利用前后步之间的 reward 差估测出 ,这就是 TD 的方法。

MC 和 TD 各有优劣,MC 最大的问题就是,因为 是有随机性的,这种随机性来自环境本身和 agent 之后所做的动作的不同,一旦累加以后 会产生很大的方差,而这个问题在 TD 中并不明显,在 TD 中具有随机性的是前后两步之间的 reward r,而并不是 r 的累加。

但是在 TD 中也存在一个问题, 也是一个估计值,这个值有可能是不准确的,这个不准确会直接造成最终 的不准确。

State-action Value Function

比起 ,我们引入一个进阶的版本,也就是我们接下来在 Q Learning 中重点要研究的 Q 函数。与之前的 不同的是, 给定了计算初始的 state ,但是没有指定初始的 action,初始的 action 完全是由 policy 自己决定的。Q 函数的不同之处在于其不仅给定一个初始状态,更指定在遇见这个状态之后应该做出怎么样的 action。

剩下就是计算 cumulated reward,这个和 V 函数是一样的。那么如何使用 Q 函数进行强化学习呢?

Q-Learning 的算法可以简单地用三步来表示:

  • 初始化一个 actor
  • 在一次迭代过程中:
    • actor 与环境做互动,并且收集数据
    • 用上述的数据,TD 或者是 MC 的方法估测出 Q 函数
    • 根据 Q 函数,找到一个永远比 “更好的”
    • 去替换原有的

这里的 “更好” 指的是对任意的 s: , 即对所有可能的 action a 来说,能够代入 并且获得最大值的那个 action 就是 会采取的 action。这里有个小问题,如果 action 是离散的,那么只要一个一个代进去算就可以得到 ,但是如果 action 是连续的就不容易计算。

证明如果存在 ,那么对任意的 s 有 :

即针对某一个特定的 s , 所采用的 action 一定不比 采取的有更小的 reward,那么加入每一步都 follow 给的 action:

Target Network

如果使用 TD-based 的方式训练神经网络来估计 Q 函数的时候,需要初始化两个一样的 DNN:

两个网络输出的差就是 ,但是在训练的过程中输入 是负责产生 target 的,如果保持两个网络一直一样,相当于在训练的过程中目标网络是会变化的,这是不好的,所以在训练的时候会现将目标网络固定住,直到某个固定的跌代次数之后再更新。

Exploitation 和 Exploration

在强化学习中,一直存在着一个 trade-off:就是探索新的 action 还是专注获得最大的 reward。这里不得不提到一个非常经典的问题:multi-arm bandit,多臂老虎机问题。 具体来说就是 你进了一家赌场,前面有着 K 台老虎机,每台老虎机去摇动的时候都有一定概率吐出一定量的钱,也有可能不吐钱,这个你没法事先知道,现在你有 T 个钱币,一个钱币只能摇动一台老虎机一次,怎样做你才能够拥有最大的金钱回报?

这实际上牵扯到一个权衡,你想知道哪台老虎机吐钱的概率最大,这需要你去尝试:Exploration。当然,探索是有成本的,因为你可能花了很多钱摇了各种各样的老虎机,但是收获的回报微乎其微。你还想获得最大的收益,如果你发现了一个相对吐钱概率高的老虎机,你得多摇摇才行,这是 Exploitation。

那么在 Q-Learning 中如果一开始在 state 有三个可能的 action ,一开始由于这三种 action 都没有被 sample 到,所以他们的 reward 是不存在的,这时候如果其中某个 action 被 sample 到了并且取得了好的反馈,根据 Q 函数永远都会选择最大 reward 的 action 去执行,那么这个 action 就会一直被 sample,而另外两个得不到被 sample 的机会,这显然是不合理的。

那么该怎么解决这个问题呢?

一种非常直观地方法叫 Epsilon Greddy,具体表示为:

在一定概率下随机乱试,起到 exploration 的作用。这个 一般会随着时间往后推移而减小,因为越往后可能没有尝试过的新 action 就越少,没必要使用这么大的概率去进行探索。

或者觉得随机乱试不是一个好方法,那么可以参考 policy gradient 的方法,给 Q 函数构建一个概率分布,假设某个 action 的 Q value 越大,那么采取这个 action 的几率也就会越大,但是不代表其他 action 不会被 sample 到。这个具体的方法叫做 Boltzmann Exploration:

之所以要用 Exp,是因为 Q value 可能是有正有负的,之后再做归一化。

Reply Buffer

在 Q Learning 中,我们有一个 policy 去和环境做互动并且产生数据,reply buffer 指的是我们会把所有的数据放到一个类似于缓冲区的地方,具体的数据含有 ,这个 buffer(缓冲区) 里面可能包含非常非常多的数据,随着互动的 policy 不断更新,buffer 里面自然也会包含不同的 policy 收集到的数据,并且这个 buffer 只有在转满的时候才会把旧的数据丢掉。

实际上当我们有了这个 reply buffer 以后,整个学习过程可以看作是 off-policy 的,其好处就是,DRL 往往会花很多时间与环境做互动,所以使用了 reply bufer 可以增加训练效率。

并且 reply buffer 里面含有不同的 policy 数据,可以在训练深度神经网络的时候起到增加数据多样性的目的,因为数据并不是一笔笔完整的 episode 而是每一步产生的结果,所以不同的 policy 也可以用来估测

综合上述算法和 tips,一个典型的 Deep Q-Learning 的算法可以描述为:

  • 先初始化两个 Q function: Q 和 target Q function
  • 在每个 episode 中:
    • 在每次迭代中:
      • 给定一个输入 state ,根据 Q 采取相应的 action
      • 得到 reward ,并且进入下一个 state
      • 把上面收集到的 放到 reply buffer 中
      • 从 reply buffer 中 sample 数据,一般按照 batch 来 sample
      • 训练,更新 Q 的参数使得 接近于
    • 每 N 次迭代完成之后更新