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

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

DRL 中的 Policy Gradient

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

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

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

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

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

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

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

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

\[R(\tau) = \{ r_1 + r_2 + r_3 + ... + r_n \}\]

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

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

\[\theta \leftarrow \theta + \eta \nabla R\]

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

\[\overline{R_{\theta}} = \sum_{\tau} R(\tau) p_{\theta} (\tau)\]

对 \(\theta\) 求梯度:

\[\begin{align} \nabla \overline{R_{\theta}} & = \sum_{\tau} R(\tau) \nabla p_{\theta} (\tau) \\ & = \sum_{\tau} R(\tau) p_{\theta}(\tau) \frac{\nabla p_{\theta}(\tau)}{p_{\theta}(\tau)} \\ & = \sum_{\tau} R(\tau) p_{\theta}(\tau) \nabla \log p_{\theta}(\tau) \\ & = \mathbb{E}_{\tau \sim p_{\theta}(\tau)} \left [ R(\tau) \nabla \log p_{\theta}(\tau) \right ] \\ & \approx \frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_n} R(\tau^{n}) \nabla \log p_{\theta}(a_t^n | s_t^n) \end{align}\]

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

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

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

\[\mathbb{E}_{x \sim p} \left [ f(x) \right ] \approx \frac{1}{N} \sum_{i=1}^{N} f(x^i)\]

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

另外一个小技巧是:

\[\nabla f(x) = f(x) \nabla \log f(x)\]

我们可以通过分子分母同时乘上一个 \(p_{\theta}(\tau)\) 将 \(p_{\theta}(\tau)\) 中梯度运算中拿出来:

\[\sum_{\tau} R(\tau) p_{\theta}(\tau) \frac{\nabla p_{\theta}(\tau)}{p_{\theta}(\tau)} = \sum_{\tau} R(\tau) p_{\theta}(\tau) \nabla \log p_{\theta}(\tau)\]

更精准的 Reward Function

改进的 \(R_{\theta}(\tau)\)

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

\[\nabla \overline{R_{\theta}} \approx \frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_n} R(\tau^{n}) \nabla \log p_{\theta}(a_t^n | s_t^n)\]

有些 action 是好的,有的是不好的,但是所有的 action 的概率前面都会被乘上同样的 weight: \(R(\tau^{n})\),显然是不合理的。

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

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

State \(s_a\) \(s_b\) \(s_c\)
Action \(a_1\) \(a_2\) \(a_3\)
Reward +10 +0 -6
\[R_1 = +4\]
State \(s_a\) \(s_b\) \(s_c\)
Action \(a_2\) \(a_2\) \(a_3\)
Reward -5 +0 -6
\[R_2 = -11\]

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

所以我们可以使用某个特定的 \(a_t\) 之后的所有 reward 总和来代表 \(a_t\) 的 reward,而不是全部 reward 的总和。为了表示计算 reward 的方法,我们引入 advantage function: \(A^{\theta}(s_t, a_t)\),在之前 \(A^{\theta}(s_t, a_t) = R(\tau^{n})\)。

我们把改进的 reward 计算式 \(A^{\theta}(s_t, a_t) = \sum_{t'=t}^{T_n} r_{t'}^{n}\) 代入

\[\nabla \overline{R_{\theta}} \approx \frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_n} A^{\theta}(s_t, a_t) \nabla \log p_{\theta}(a_t^n | s_t^n)\]

得到

\[\nabla \overline{R_{\theta}} \approx \frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_n} \sum_{t'=t}^{T_n} r_{t'}^{n} \nabla \log p_{\theta}(a_t^n | s_t^n)\]

另外,我们可以给 \(\sum_{t'=t}^{T_n} r_{t'}^{n}\) 加上一个影响力衰弱参数 \(\gamma\),因为时间拖得越长,越前面发生的事件对后来的影响就会越小:

\[A^{\theta}(s_t, a_t) = \sum_{t'=t}^{T_n} \gamma^{t'-t} \cdot r_{t'}^{n} , (0 < \gamma < 1)\]

添加 Baseline

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

很显然不能,所以这里又有一个小的 tip:减去一个 baseline 使得 \(A^{\theta}(s_t, a_t)\) 的值有正有负 ,一般来说这个 baseline 就是所有 reward 的期望:

\[b = \mathbb{E}\left [ R(\tau) \right ]\]

代入得:

\[\begin{align} \nabla \overline{R_{\theta}} & \approx \frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_n} \left [ R(\tau) - b \right ] \nabla \log p_{\theta}(a_t^n | s_t^n) \\ & = \frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_n} \left [ R(\tau) - \mathbb{E}\left [ R(\tau) \right ] \right ] \nabla \log p_{\theta}(a_t^n | s_t^n) \end{align}\]

结合上面的优化方法:

\[\nabla \overline{R_{\theta}} \approx \frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_n} \sum_{t'=t}^{T_n} (\gamma^{t'-t} \cdot r_{t'}^{n} - \mathbb{E}\left [ R(\tau) \right ]) \nabla \log p_{\theta}(a_t^n | s_t^n)\]

On-Policy 到 Off-Policy

On-Policy 学习方式

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

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

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

\[\nabla \overline{R_{\theta}} = \mathbb{E}_{\tau \sim p_{\theta}(\tau)} \left [ R(\tau) \nabla \log p_{\theta}(\tau) \right ]\]

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

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

Important Sampling

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

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

具体来说,important sampling 中用一个分布 \(q(x)\) 来估计另一个分布 \(p(x)\) 可以这样表示:

\[\begin{align} \mathbb{E}_{x \sim p} \left [ f(x) \right ] & \approx \frac{1}{N} \sum_{i=1}^{N} f(x^i) \\ & = \int f(x)p(x) dx = \int \frac{f(x)p(x)}{q(x)} \cdot q(x) \\ & = \mathbb{E}_{x \sim q} \left [ \frac{f(x)p(x)}{q(x)} \right ] \\ \end{align}\]

Proximal Policy Optimization (PPO)

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

\[\begin{align} \nabla \overline{R_{\theta}} & = \mathbb{E}_{\tau \sim p_{\theta}(\tau)} \left [ R(\tau) \nabla \log p_{\theta}(\tau) \right ] \\ & = \mathbb{E}_{\tau \sim p_{\theta'}(\tau)} \left [ \frac{p_{\theta}(\tau)}{p_{\theta'}(\tau)} R(\tau) \nabla \log p_{\theta}(\tau) \right ] \\ & \rightarrow \mathbb{E}_{(s_t, a_t) \sim \pi_{\theta}} \left [ A^{\theta}(s_t, a_t) \nabla \log p_{\theta}(\tau) \right ] \\ & = \mathbb{E}_{(s_t, a_t) \sim \pi_{\theta'}} \left [ \frac{p_{\theta}(s_t, a_t)}{p_{\theta'}(s_t, a_t)} A^{\theta}(s_t, a_t) \nabla \log p_{\theta}(\tau) \right ] \\ & = \mathbb{E}_{(s_t, a_t) \sim \pi_{\theta'}} \left [ \frac{p_{\theta}(a_t | s_t)p_{\theta}(s_t)}{p_{\theta'}(a_t | s_t)p_{\theta'}(s_t)} A^{\theta}(s_t, a_t) \nabla \log p_{\theta}(\tau) \right ] \\ \end{align}\]

假设 \(p_{\theta'}(s_t) \approx p_{\theta}(s_t)\),那么上面的式子可以写成:

\[\mathbb{E}_{(s_t, a_t) \sim \pi_{\theta'}} \left [ \frac{p_{\theta}(a_t | s_t)}{p_{\theta'}(a_t | s_t)} A^{\theta}(s_t, a_t) \nabla \log p_{\theta}(\tau) \right ]\]

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

借助之前的公式 \(\nabla f(x) = f(x) \nabla \log f(x)\),我们可以用 gradient 去反推原来的 objective function,得到函数 \(J^{\theta'}(\theta)\):

\[J^{\theta'}(\theta) = \mathbb{E}_{(s_t, a_t) \sim \pi_{\theta'}} \left [ \frac{p_{\theta}(a_t | s_t)}{p_{\theta'}(a_t | s_t)} A^{\theta}(s_t, a_t) \right ]\]

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

\[J_{PPO}^{\theta'}(\theta) = J^{\theta'}(\theta) - \beta KL(\theta, \theta')\]

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

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

  • 初始化一个 policy \(\theta^{0}\)
  • 在每次迭代过程中:
    • 使用 \(\theta'\) 去与环境交互,收集数据 \(\{ s_t, a_t \}\) 并且计算 \(A^{\theta'}(s_t, a_t)\)
    • 找到 \(\theta\) 去优化 \(J_{PPO}(\theta)\), 其中 \(J_{PPO}^{\theta'}(\theta) = J^{\theta'}(\theta) - \beta KL(\theta, \theta')\)

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

  • 如果 \(KL(\theta', \theta) > KL_{max}\), 增加 \(\beta\)
  • 如果 \(KL(\theta', \theta) < KL_{min}\), 减小 \(\beta\)

Trust Region Policy Optimization (TRPO)

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

\[J_{TRPO}^{\theta'}(\theta) = \mathbb{E}_{(s_t, a_t) \sim \pi_{\theta'}} \left [ \frac{p_{\theta}(a_t | s_t)}{p_{\theta'}(a_t | s_t)} A^{\theta}(s_t, a_t) \right ], KL(\theta, \theta') < \delta\]

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

PPO2

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

\[J_{PPO2}^{\theta^k}(\theta) \approx \sum_{(s_t, a_t)} min \left [ \frac{p_{\theta}(a_t | s_t)}{p_{\theta^k}(a_t | s_t)} A^{\theta^k}(s_t, a_t), clip(\frac{p_{\theta}(a_t | s_t)}{p_{\theta^k}(a_t | s_t)}, 1 - \varepsilon, 1 + \varepsilon) A^{\theta^k}(s_t, a_t) \right ]\]

\(clip \left [f(x), 1 - \varepsilon, 1 + \varepsilon \right ]\) 的意思是说:

\[clip \left [f(x), 1 - \varepsilon, 1 + \varepsilon \right ] = \begin{cases} f(x) & 1 - \varepsilon < f(x) < 1 + \varepsilon \\ 1 - \varepsilon & f(x) < 1 - \varepsilon \\ 1 + \varepsilon & f(x) > 1 + \varepsilon \end{cases}\]

这样就可以动态地将 \(f(x)\) 的值限定在 \(1 - \varepsilon\) 到 \(1 + \varepsilon\) 之间,达到两个分布不会相差太多的效果。而取最小值是因为,当 \(A^{\theta^k}(s_t, a_t) > 0\) 时,我们希望 objective function 越大越好,但是一旦大过了 \(1 + \varepsilon\),这个式子就不再有 benefit 了,因为不满足两个分布差别不要太大的这个约束条件,同理当 \(A^{\theta^k}(s_t, a_t) < 0\) 的时候也是一样。

Q-Learning

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

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

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

那怎么去估计这样一个 \(V^{\pi}(s)\) 呢?这里一般用两种方法,MC 和 TD,其中各有优劣。

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

简要表示就是这个样子:

\[s_a \rightarrow network \left [ V^{\pi} \right ] \rightarrow V^{\pi}(s_a) \leftrightarrow G_a\]

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

TD-based 的方法具体来说是针对每个 step,我们可以得到 \(...s_t, a_t, r_t, s_{t + 1}...\),那么从这个式子可以看出,对应的 \(V^{\pi}(s_t)\) 实际上是满足:

\[V^{\pi}(s_t) = V^{\pi}(s_{t + 1}) + r_t\]

具体的实现我们可以构造两个一样的网络 \(V^{\pi}\),分别接收 \(s_t\) 和 \(s_{t+1}\),之后我们将输出作差 \(V^{\pi}(s_{t}) - V^{\pi}(s_{t + 1}) \approx r_t\),尽量使得差值和给定的训练数据 \(r_t\) 保持一致。

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

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

但是在 TD 中也存在一个问题,\(V^{\pi}(s_t) = V^{\pi}(s_{t + 1}) + r_t\) 中 \(V^{\pi}(s_{t + 1})\) 也是一个估计值,这个值有可能是不准确的,这个不准确会直接造成最终 \(V^{\pi}(s_{t})\) 的不准确。

State-action Value Function \(Q^{\pi}(s, a)\)

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

\[Q^{\pi}(s_t, a_t)\]

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

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

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

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

证明如果存在 \(\pi'(s) = arg max_{a} Q^{\pi}(s, a)\),那么对任意的 s 有 \(V^{\pi'}(s) > V^{\pi}(s)\):

\[V^{\pi}(s) = Q^{\pi}(s, \pi(s)) \leq max_a Q^{\pi}(s, a) = Q^{\pi}(s, \pi'(s))\]

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

\[\begin{align} V^{\pi}(s) & \leq Q^{\pi}(s, \pi'(s)) \\ & = \mathbb{E} \left [ r_{t+1} + V^{\pi}(s_{t+1})_{|s_t = s, a_t = \pi'(s_t)} \right ] \\ & \leq \mathbb{E} \left [ r_{t+1} + Q^{\pi}(s_{t+1}, \pi'(s_{t+1}))_{|s_t = s, a_t = \pi'(s_t)} \right ] \\ & = \mathbb{E} \left [ r_{t+1} + r_{t+2} + V^{\pi}(s_{t+2})_{| ...} \right ] \\ & \leq \mathbb{E} \left [ r_{t+1} + r_{t+2} + Q^{\pi}(s_{t+2}, \pi'(s_{t+2}))_{| ...} \right ] ... = V^{\pi'}(s) \end{align}\]

Target Network

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

\[(s_t, a_t) \rightarrow \left [ Q^{\pi} \right ] \rightarrow Q^{\pi}(s_t, a_t) \leftrightarrow r_t + Q^{\pi}(s_{t+1}, \pi(s_{t+1})) \leftarrow \left [ Q^{\pi} \right ] \leftarrow (s_{t+1}, \pi(s_{t+1}))\]

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

Exploitation 和 Exploration

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

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

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

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

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

\[a = \begin{cases} arg max_a Q^{\pi}(s, a) & f(x) < 1 - \varepsilon \\ random & otherwise \end{cases}\]

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

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

\[P(a|s) = \frac{exp(Q(s, a))}{\sum_a exp(Q(s, a))}\]

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

Reply Buffer

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

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

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

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

  • 先初始化两个 Q function: Q 和 target Q function \(\hat{Q} = Q\)
  • 在每个 episode 中:
    • 在每次迭代中:
      • 给定一个输入 state \(s_t\),根据 Q 采取相应的 action \(a_t\)
      • 得到 reward \(r_t\),并且进入下一个 state \(s_{t+1}\)
      • 把上面收集到的 \(( s_t, a_t, r_t, s_{t+1})\) 放到 reply buffer 中
      • 从 reply buffer 中 sample 数据,一般按照 batch 来 sample
      • 训练,更新 Q 的参数使得 \(Q(s_i, a_i)\) 接近于 \(y = r_i + max_a \hat{Q}(s_{i+1}, a)\)
    • 每 N 次迭代完成之后更新 \(\hat{Q} = Q\)