强化学习Exploration漫游

这篇文章打算讲讲强化学习的Exploration方法。强化学习的Exploration方法五花八门，三天三夜讲不完，但其背后是主要思想只有寥寥几个。

本文打算抓重点来讲，主要介绍三种最重要的Exploration思路——Optimistic Exploration、Posterior Sampling和Information Gain。（搞懂这三个思路之后，就可以关闭这个网页了）

这三种Exploration思路从传统强化学习时代（以多臂老虎机研究环境为主）一直走到了深度强化学习时代，这里也会介绍主要的场景和实际算法。

全文2万字左右，没讲清楚的部分会附上链接和参考文献。

第一部分：Exploration简介

对RL稍有了解的同学都知道，Exploration是一件很重要同时也很困难的事情。与其他机器学习范式相比，RL通常只知道某个动作的能得多少分，却不知道该动作是不是最好的——这就是基于evaluate的强化学习与基于instruct的监督学习的根本区别。

正因如此，RL的本质决定了它极其需要Exploration，我们需要通过不断地探索来发现更好的决策，或者至少证明当前的决策是最好的——所以Exploration-Exploitation成为了强化学习领域诸个Tradeoff中最出名的一个。

【什么是Exploration？】

Exploration是尝试新的东西，本质上是为了获取更多信息。各种Exploration方法的核心就是用尽可能少的代价获得尽可能有价值的信息。

【什么是Exploration-Exploitation Tradeoff？】

探索（Exploration）就是采取先前没有使用过的决策，期望能获得更高的收益。利用（Exploitation）就是采取现阶段已知的最佳决策，见好就收，稳扎稳打。所有exploration方法的都需要平衡这两者，否则无法获得满意的回报。

最简单的exploration方法就是epsilon-greedy，即设置一个探索率epsilon来平衡两者的关系——在大部分时间里采用现阶段最优策略，在少部分时间里实现探索。

Epsilon-greedy很简单，它根本不会考虑更加有针对性的探索机制，它仅仅是在纯贪心的基础上加入了一定概率的uniform噪声——所以epsilon-greedy又被称为Naive Exploration。

三个重要的Exploration Intuition

现在介绍三个经典而实用的exploration intuition——Optimistic Exploration、Posterior Sampling和Information Gain。

第一类方法：Optimistic Exploration（乐观探索）

乐观的人相信未来越来越好，虽然未来充满了不确定性，但是明天一定更好。我们可以用一句话来概括这类算法——“new state = good state”。

因为这类基于Optimistic的算法总是倾向于不确定性较大的动作，所以它们又被称为“novelty detection”。那么什么才是不确定性（Uncertainty）呢？

从最简单的角度看，见得少的东西有比较大的不确定性，也就是俗话说的“少见多怪”。这类算法都需要计算某个action或者某对action-state的出现频率，然后把这些频率作为一种bonus——出现越少的state有着越高的bonus。

1.Upper-Confidence-Bound Exploration

上述基于频率来分发奖励的机制一直被广泛使用，AlphaGo所使用的MCTS算法的第一个步骤里，就使用了UCB函数来实现Exploration。下图给出了UCB的公式，可以看出除了UCB函数之外，还有许多的其他的算子可以由来设计Bonus——

可以看出optimistic exploration与greedy select的本质区别就是附带的那个权重项，不管是UCB还是其他的optimistic exploration项（也许公式很复杂），但它们的本质都是相同的——倾向于选择最优的、最新的或者把两者兼顾最佳的。

2.Optimistic Initial Value（乐观初始值方法）

在更一般的情况下，我们可以把Optimistic Exploration的公式写成如下形式（自然也包括了前面介绍的UCB和其他方法）——

这里的u指的是每个action的average reward。为了计算这个u，我们需要保留每个action的reward sum和visit count，两者相除的结果就是对应action的average reward（在具体计算的时候可以采用增量计算方法）

下面要介绍的Optimistic Initial Value方法虽然不需要记录state的出现频率，但是其本质也是去探索那些出现频率较低的state。Optimistic Initial Value顾名思义就是通过增大值函数初值来实现exploration。

举多臂老虎机的例子来说，假设Bandit里各个trigger的真实收益都在1~10之间浮动，而Optimistic Initial方法把全部的值函数都初始化为50（甚至100）。在这种情况下，即使我们扳动了最优的trigger并获得了最大的回报10，考虑到action的值函数是被平均回报定义的，所以此时它的值函数变成了(100+10)/2=55。

也就是说，获得了最大收益action此时的值函数最小的，智能体还会去探索其他的action。在多轮的模拟之后，虚高的初始值函数会被拉回真实水平，但是在此之前Exploration的任务已经都完成了。（这里值得注意的是，Optimistic Initial值选择需要一定的先验知识，并且在最开始的阶段会有比较大的震荡。）

3.Gradient Bandit Algorithm

这个方法并没有使用值函数Q，而是设置了熵值H。熵值H往往代表着不确定性，既代表着新颖性，智能体更倾向于选择熵值比较大的Action。每个动作的熵通过获得的reward来调整。

Sutton的RL Introduction介绍了上面这两种方法。

4.Pseudo-counts Exploration（伪计数探索）

在信息科学中，出现了pseudo-xxx就意味着算法进入到了近似计算的阶段。从现在开始，我们介绍Deep RL中的Optimistic Exploration——Pseudo-counts。

之前介绍几种利用state频率来进行探索的算法都属于count-based exploration，然而在深度学习的复杂环境下，我们需要思考一个新的问题——究竟什么是count？

在某些复杂高维连续环境中（例如星际争霸），完全相同的状态几乎不可能出现两次，这时每个state都是最新的，那么传统意义上的count便没有了意义——因为几乎每一个state count都等于1！

因此这里将要介绍的Pseudo-count算法微调了count的定义——我们可以这样认为：虽然各个状态是不同的，但是很多状态都是相似的。特别是在哪些连续的状态空间中，如果不同的状态其实仅相差一个像素位，那么我们可以认为它们是相同的。

(1) CTS-based Pseudocounts（Bellemare 2016）

这种方法的思路是拟合一个density generative model p(s,a)或p(s)。如果新状态s和之前某个出现过的状态比较相似，那么p(s)的值就比较大。我们用这个p(s)来实现对状态s的伪计数。

随后计算新状态下的p(s)

在上面两个公式的基础上，用以下二元一次方程组解得近似的pseudo-count

完整的流程如下：

这类算法的难点在于拟合Model的选择，因为state的生成或者预测模型在高维连续环境中难以得到。

Bellmare的CTS-base pseudo-count最后解决了高难度游戏——蒙特祖玛的复仇，随后Ostrovski又对Bellmare的算法做出改良，下面是参考文献——

Bellmare 2016 Unifying Count-Based Exploration and Intrinsic Motivation Ostrovski et al, 2017. Algorithm: PixelCNN-based Pseudocounts.

(2) hash-based pseude-count (#Exploration 2016)

下面介绍一种使用hash进行伪计数的办法——这类算法通过Hash函数把状态s映射成一个k-bits的hash code，随后通过hash table对这个hash code进行计数。计数的结果用于计算reward bonus。这里主要介绍Tang的#Exploration算法（2016年）

虽然简单的hash functions已经可以获得不错的效果，但是文章采用了locality-sensitive hashing (LSH)。LSH这类算法的本质是根据选定的相似度来查询最近邻状态。推荐的LSH算法实现是SimHash。

同时可以学习domain-dependent hash code来提升特定领域内的效果。学习hash function的途径是AutoEncoder。

参考论文：#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning, Tang et al, 2016. Algorithm: Hash-based Counts.

参考博客：https://blog.csdn.net/qq_30159351/article/details/78212235

(3) exemplar models exploration (EX2 2017)

基于示例模型（exemplar models）的算法将new state与past state进行隐式比较——如果某个new state可以比较容易地同past state区别开来，那么就可以认为这个state是比较新颖的。

参考文献：EX2: Exploration with Exemplar Models for Deep Reinforcement Learning, Fu et al, 2017. Algorithm: EX2.

第二类方法：Posterior Sampling（后验采样）

现在进入第二大类算法。第二种方法有许多名字，包括Probability Matching、Thompson sampling等，其实本质是相同的。这类方法融合了贝叶斯学习的一些思想，其核心是使用后验概率进行更有针对性的探索。（虽然这种算法在理论分析上比较困难，但是在实际的编程中比较容易实现。）

普通的epsilon-greedy采用无差别的uniform select，其采样过程并没有任何针对性，所以说是非常Naive的。有些情况下，我们已经知道了某些Action是绝对不好的，所以我们就没有必要继续浪费时间在那些Action上了。

以上图为例，在这种环境下，action2的平均回报绝对小于action1，所以我们不需要再探索action2。如果采用epsilon-greedy，那么还有许多探索机会将浪费在action2上。

基于Posterior Sampling的算法在每次采样之后都会修正它的概率分布，这和贝叶斯学习的内涵是完全一致的。在进行了大量学习之后，我们将会对各个action有着更强的信念，反映在概率上就意味着更小的方差。

1.Thompson Sampling

Thompson Sampling(TS)算法是一种Probability matching的实现，因为每个action对应的Q值是采样自先验分布的，每个action对应的奖赏概率就是目前认为最优的，当然这都是基于到目前为止已经观测到的事实。

以多臂老虎机的环境为例，TS将Multi-Armed Bandit的每一个action的回报率看作一个Beta分布。Beta分布需要先验概率参数alpha和beta。当我们收集到越来越多的实验结果后，我们可以对分布的参数alpha和beta进行更新：

Beta分布有很多与生俱来的优秀性质——随着我们观测到的结果越多，分布的置信区间就越窄。(alpha, beta)=(5, 5)和(alpha, beta)=(5000, 5000)有着相同的均值，但是后者的方差极小。正因此，当轮数较少时，Thompson Sampling可能会以比较大的概率进行探索，较少的情况使用greedy action；但是轮数上升后，Thompson Sampling的尝试收敛了，

参考论文：Chapelle & Li, “An Empirical Evaluation of Thompson Sampling”

参考博客：https://medium.com/@yaoyaowd/从thompson-sampling到增强学习-再谈多臂*屏蔽的关键字*问题-23a48953bd30

2. Bootstrap DQN （2016）

这里介绍一种用DQN来实现Posterior Sampling探索的算法。这个算法通过创建一个新的DQN架构来鼓励exploration，该DQN架构支持从若干个互不相同的Q函数中选择动作，而这些Q函数通过训练bootstrap data而得到。具体架构如下图——

最上层是K个端口（head），也就是K个互不相同的Q函数。这K个Q函数在数据集的一个subset上进行训练。在每个episode开始之时，该算法会随机地抽取一个Q函数，这个被抽出来的Q函数会在后面用到。
中间层是共享层（shared network），共享层从全部数据中学习联合特征表示（joint feature representation），它可以视为data-dependent dropout。
最下层是输入的数据帧。（注意：所有的sample保存在一个replay buffer之中，每个replay buffer都需要记录它从哪个Q函数中来。）

每个Q-value都有一个bootstrap mask，该mask用于决定是否应该根据在时刻t产生的sample进行训练。每个独立的sample都被赋予了一个随机mask的（可以通过Bernoulli分布或者Poisssion分布）

随后，当网络在replay buffer的minibatch sample上进行训练时，mask就决定了某个特定的Q函是否要参与这个训练过程。（因为Q-learning是off-policy的，所以我们不需要关注哪个Q-function是用于collect data的。）

为什么这个算法好用（相比于epsilon-greedy而言）？

因为这种对Q函数进行随机化的方法平衡了learning from noisy data与exploring complex state/action spaces。最基础的epsilon-greedy算法可能会存在oscillate的现象，所以无法进入到一个更有针对性的区域中。而用random Q-functions进行探索的算法，可以在整个episode中保证一个randomized but internally的一致探索策略。

参考文献：Osband 2016 Deep Exploration via Bootstrapped DQN

参考博文：

https://pemami4911.github.io/paper-summaries/deep-rl/2016/08/16/Deep-exploration.html

第三类方法：Information Gain Exploration（信息增益）

这类方法将Agent自身拥有的信息（info）也视为状态（state）的一部分。它们希望通过遍历新的state来获得新的info，它们把那些可以获得更多信息增益的state视作最理想的state。

这类算法使用了大量信息论的知识，所以又被称为Information-theoretic exploration。它们的缺点是计算复杂，即通常情况下都无法获得精确的解析解，所以这类方法引入了许多variational approximation技巧来简化运算。这里重点强调其思想，而不被数学部分搞糊涂了。

1. info gain

用Bayesian experimental design的角度来分析，我们的目的是寻找一个latent variable z，这就是optimal action。Information gain使用信息熵和信息增益来决策。

这里y指的是action对应的reward，z对应拟合模型p(r_a)的参数。对应的exploration策略如下——

参考文献：Russo Van Roy 2014 Learning to Optimize via Information-Directed Sampling

2. VIME

VIME是OpenAI提出的探索机制，全程是Variational Information Maximizing Exploration，也就是变分信息最大化探索。

顾名思义，VIME的主要思路是最大化信息增益（Information Gain），VIME希望每一步行动都能够尽可能利用这次交互机会来更多地获取环境的信息。

之前介绍的大部分exploration方法都十分依赖reward。一般来说，我们希望好的reward至少密集（dense）的，即每时每刻都有reward可以指导agent如何改善自己。然而在真实环境中，reward常常是sparse & delayed的。

VIME对于reward的依赖大大减弱，相比于利用Reward进行探索，VIME的信息增益探索机制是一种内在探索机制，这种性质使得VIME可以在稀疏奖励任务中更好地探索。（VIME可以与各种其他标准的RL算法结合使用，例如VIME+TRPO等等。）

VIME所利用的Information Gain主要围绕环境的动力学模型（dynamic）展开。这里设置系统的动力学模型为p(s_t+1 | s_t, a_t, theta)。现在的问题是如何衡量信息增益IG？VIME使用了KL散度来衡量信息增益——

假设所有先验数据为h，当前环境参数为theta，当前状态为st，当前决策为at，新状态为s_t+1，那么信息增益可以衡量为——

VIME的目标是最大化上面这个KL散度，由于计算上存在问题，所以把这个KL散度纳入到原来的奖励中——

虽然做了上面的化简，但是KL散度内部的分布依然比较难以计算，所以VIME采用了Variational Bayes方法来解决。这里使用了一个规则化的分布来近似真实的分布——

VIME选用了Gaussian作为近似分布，也就是说q(theta | fi)可以理解成独立的高斯分布的乘积。此处可以继续阅读Blundell的“Weight uncertainty in neural networks”。经过近似处理，KL散度奖励变成了可以计算的形式（也就是把p变成了q）——

VIME可以在非常稀疏奖励的任务中获得比较好的效果。VIME的官方实现在 https://github.com/openai/vime.

参考论文：Houthooft et al, 2016 VIME: Variational Information Maximizing Exploration

参考博客：https://zhuanlan.zhihu.com/p/48042454

3.好奇心（Curiosity-Driven Learning ）

上面介绍的VIME与好奇心有密切联系。和VIME和相似。好奇心（Curiosity-Driven Learning ）就是一种intrinsic reward（内在奖励函数），它使用预测误差作为奖励信号。

Curiosity-Driven Learning的本质就是intrinsic reward的设计。好奇心机制提出了一种假设：Agent对某个环境的熟悉程度可以作为一种reward，我们只需要设计一种熟悉度的评价指标就可以了。（也就是默认Agent拥有好奇心）

一种常见的指标就是根据当前state/action预测new state，然后计算与实际state的偏差。这个代表着Agent对环境的熟悉程度，Agent的目标就是去缩小这个预测误差。

有人可以就要问了，好奇心是不是可以理解成对于transition的一种预测？某种意义上说是的，因为curiosity其实就是用一种用fitting的方法近似计算原本无解的transition dist entropy。

参考文章：

2017 Curiosity-driven Exploration by Self-supervised Prediction（地址：https://arxiv.org/abs/1705.05363）, Pathak et al, Intrinsic Curiosity Module (ICM).

2018 Large-Scale Study of Curiosity-Driven Learning

（https://arxiv.org/pdf/1808.04355.pdf）

张楚珩：【强化学习算法 23】ICM（https://zhuanlan.zhihu.com/p/47912734）

其他的话

这篇文章是我对Sergey Levine主讲的CS 294-112 Deep Reinforcement Learning - Exploration Part I/II这两节课的笔记。虽然说目前最流行的RL书籍是R.Sutton的《Reinforcement Learning An Introduction》，但是明显可以看出Sergey（及其身后的OpenAI）在理解DRL的方式上与Sutton（及其徒子徒孙DeepMind）有着明显不同。

这篇文章还有不少仓促的地方（还有一些地方没有详细引用），写这篇文章也是我自己搞的学习笔记。请大家多批评或者私信。未来一段时间里我会不断修改。

本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。