CS285课程笔记（4）——Exploration Method

通过近期对强化学习和多智能体强化学习相关论文的不断阅读发现，强化学习中的data efficiency或sample efficiency真的可以算是一个可以好好钻研的课题了，我觉得Exploration从一定程度上加速了算法的收敛也提高了采样效率。欢迎各位大佬指出本文任何问题！。

本文内容对应CS285课程的lecture 13和14，内容先对课程中所讲述的内容进行总结，如后续通过suggested reading有了一些新的想法再回来更新本文。

1. 为什么要用引入exploration

1.1 直观解释

强化学习中最关键的一步就是人为设计reward function，如果设计的不好，那整个算法也就不收敛。但是人为觉得设计了非常合理的Reward function，能够代表强化学习算法能让智能体高效完成任务吗，智能体会不会只是为了获取高的reward而出现了一些“作弊”（无效）行为而不是完成最终的任务吗？

课程中以Atari game中的Montezuma’s revenge游戏来举例说明该问题。在该游戏中，模拟器中reward的给定方式是：“人”得到了钥匙之后可以得到reward，人打开门可以得到reward，人与骷髅相撞的时候什么都得不到（reward=0），直到给定的游戏次数结束。这时候如果智能体随机探索的话（没有专门的探索策略的情况下），首先它会非常低效，如果运气比较好的话它也有可能专注于重复积累某个非完成任务的但却能得到比较高Reward的动作（例如这里的开门）从而最终获得比较高的episode reward。显然这种结果是我们希望避免的。这类任务被称为temporally extended task，在这类任务中reward的获得是延迟的，这里的延迟含义我理解为是本身动作空间的探索和获取reward的规则并不是强相关的（动作空间的随机探索也是每次变化一些数值，而上升不到通过这些数值的变化能够理解规则本身的高度），所以强化学习算法中的智能体只能通过试错法去不断发现隐藏的规则，那么在没有提供先验知识的前提下智能体出现上述情况也就是正常情况了（这也是强化学习为什么存在sample efficiency的一个原因之一，因为很多random exploration其实是比较低效的）。

1.2 强化学习中的exploration-exploitation权衡

强化学习中最重要的一个权衡就是Exploration-exploitation的权衡。在之前的强化学习笔记博客中也提到过，这里再重新举例陈述一下。所谓的exploration就是对新的状态或动作空间进行搜索，而Exploitation就是充分利用已经通过之前探索得到的状态和动作空间，从中找出最优的决策方式。

下图为一个例子：

1.3 最优探索策略（Optimal Exploration Strategy）

上文陈述了加入探索策略的重要性，那么如何得到一个最优的探索策略呢？探索策略的最优性如何定义？

这里的最优性主要是是对比当前策略的regret和Bayes-optimal strategy（见后文）。从问题的复杂度角度（从bandits问题到MDP，再到infinite MDP问题）来看，探索策略能否达到最优也是不断变化的。首先是原始问题的可解性上，位于横轴最左边的multi-armed bandits问题理论上是可解的，可得到最优决策序列。而横轴的最右端的infinite MDPs则是不可解的，这也是为什么在强化学习中引入深度学习的原因之一。

2. Multi-armed Bandits问题中的exploration

2.0 Multi-armed Bandits问题描述

Multi-armed bandits问题就是在一个场景中，有$n$个可选的决策方式（$a_1,a_2,\dots ,a_n$），每一个time step选择其中的一个决策方式后并收到reward值，即$r(a_i)$，最后得到整个的episode reward。Multi-armed bandits的例子有：医生为一连串的病人提供治疗方案，其中治疗方案有$N$种，也就是该问题下的action space，而Reward与病人存活或死亡有关。

假设智能体做出某种决策后收到的reward为：$r(a_i)\sim p_{{\theta }_i}(r_i)$，而reward服从Bernoulli分布，即$p_{{\theta }_i}(r_i=1)={\theta }_i,p_{{\theta }_i}(r_i=0)=1-{\theta }_i$，这里的$\theta$有其先验分布，记为${\theta }_i\sim p_i({\theta }_i)$。假设在某个问题中动作空间中总共有3个动作，$a_1,a_2,a_3$，则$r(a_1)\sim p_{{\theta }_1}(r_1),r(a_2)\sim p_{{\theta }_2}(r_2),r(a_3)\sim p_{{\theta }_3}(r_3)$，其他信息均为未知。

2.1 理论上获取最优探索策略的方式

上述的描述其实构成了一个POMDP问题（把$\theta$当成隐变量即可），其状态为$\mathbf{s}=[{\theta }_1,\dots ,{\theta }_n]$，而belief state为$\hat{p}({\theta }_1,\dots ,{\theta }_n)$，先说明课程中的结论，求解该POMDP就相当于得到了最优的探索策略。而探索策略的好坏取决于Regret，regret的定义为采用当前action所获取的reward与采用最优动作所获得reward的差值，其表达式为：
$$\text{Reg}(T)=TE[r(a\ast )]-\sum _{t=1}^{T}r(a_t)$$

但是该方法存在一个问题，就是POMDP中的belief state的维度过大，例如上述简单的医生-患者情境中，有5个治疗方案选项，每采取一个action所获得的reward服从一个Bernoulli分布（患者死亡Reward为0，患者生存为1），每个参数的先验概率分布等概率地在$[0,0.2,0.4,0.6,0.8,1]$中选择，这里假设各个参数的分布都是独立的（当然这种假设是理想化的，实际上每个治疗方案之间或多或少是类似的），$\hat{p}({\theta }_1,{\theta }_2,\dots ,{\theta }_5)=p_1({\theta }_1)p_2({\theta }_2)\dots p_5({\theta }_5)$，belief state的可能性有$5^6$种，如果参数的先验概率分布为连续概率密度函数，则belief state的概率分布更为复杂。 所以这也就引出了以下的较为简单的探索方式。

2.2 Optimistic Exploration

第一种方式为optimistic exploration，该方式建立在Exploitation的基础之上，从上文可知，exploitation是指追踪每个动作得到的Reward值，每次选取reward最大的一个，表达式为$a=\arg \max {\hat{\mu }}_a$，其中${\hat{\mu }}_a$为每个action的平均Reward。optimistic exploration是在此基础上加入了在该动作下获取的reward的方差估计，$a=\arg \max {\hat{\mu }}_a+C{\sigma }_a$，其中一个示例是：
$$a=\arg \max {\hat{\mu }}_a+\sqrt{\frac{2\ln T}{N(a)}}$$
这里的$N(a)$记录了动作a被选择的次数。

2.3 Posterior Sampling (Probability Matching)

另一种方式为Posterior sampling，该方法需借助上文所述POMDP框架中的belief state概率分布。大致流程为：从belief state中采样出各个参数的概率值，假设该belief state是完全准确的并根据其选择最优策略，最后更新belief state中的参数。该方法很难进行理论分析，但实际应用中有着不错的效果。

2.4 Information Gain

最后一类方法是利用information gain中的熵来进行探索，这里先引入一个隐变量$z$，其可以表示最优的动作或最优动作的值。

总结一下这三种方法：

3. 用于深度强化学习中的exploration策略

第一部分直接改进bandits和MDP问题中的相关探索方法，即将上文中的三大类探索方法扩展到深度强化学习中，第二部分是一些其他的方法（比较新的研究）

3.1 Optimistic Exploration类方法

pseudo-counts方法

optimistic exploration的核心思想在于统计或估算每个state-action pair的已访问次数，通过该值判断这个state-action pair是不是新的并由此作为exploration bonus加到reward function中，并用该Reward function进行训练。其一般形式可以写为：
$$r^{+}(\text{s},\text{a})=r(\text{s},\text{a})+w\mathcal{B}(N(\text{s}))$$

该形式的好处在于其简便性，而它存在的问题在于需要调bonus的参数，另外一个问题在于如果该方法用于连续状态空间，有些状态不可能访问两次（当然该问题在离散状态空间下也有可能存在）。解决该问题的一个思路是拟合一个density model $p_{\theta }(\text{s})$（或者是$p_{\theta }(\text{s},\text{a})$），如果某个状态从来没有被访问过，$p_{\theta }(\text{s})$的值会比较高。接下来的问题是如何通过density model得到访问次数（该访问次数被称为 $pseudo-counts$），对于简单MDP来说，状态访问概率可以写成：$P(s)=\frac{N(s)}{n}$，如果访问到一个新的状态$s^{\prime }$之后，该概率可以被改写为：$P^{\prime }(s)=\frac{N(s)+1}{n+1}$。

根据上述思路可以写出大致的算法思路：

上述流程中通过$p_{\theta }(\text{s})$，$p_{{\theta }^{\prime }}(\text{s})$得到pseudo-counts $\hat{N}({\text{s}}_i)$的公式为：

得到pseudo-counts之后，就可以在此基础上计算bonus，以下为几种常用方式：

需要注意的是，这里的density model与GAN有区别，GAN是要求网络生成采样数据，而density model只需要输出某个状态的density即可，不需要从中采样。

Counting with hashes

与上文直接用模型输出某个状态的density不同，该方法将状态压缩，思路是用一个encoder将状态$\text{s}$压缩成一个k-bit code $\varphi (\text{s})$，然后对该code计数，得到$N(\varphi (\text{s}))$。但存在的问题是如果编码长度过短，可能不同状态经过encoder之后可能得到相同的hash值。

Exemplar Exploration方法

上文的方法是获得一个直接输出某个状态的density的density model，那么有没有方法能够隐式输出density呢？exemplar exploration方法回答了上述问题。直观思路就是构造一个判别器（二分类器），当访问到某个状态之后，用其与已有数据中的状态信息对比，如果判别器很难分辨该数据是来源于新数据还是已有数据，那么可以间接说明该状态的density很高，反之亦然。用形式化语言描述判别器，$D_{x^{\ast }}(x):\mathcal{X}\to [0,1]$，其中$x\in \mathcal{X}$，其概率分布为：$P_{\mathcal{X}}(x)$（只说明两种极端情况，其实也是label）
$$D_{x^{\ast }}(x)=P(x=x^{\ast }|x)=\{\begin{array}{ll}1& \text{if }x=x^{\ast }\\ 0& \text{if }x\ne x^{\ast }\end{array}$$

训练中来自Replay buffer中的数据标记为负样本，新数据被标记为正样本（即exemplar）。判别器的训练是通过交叉熵函数：

用该损失函数对$D(x)$求导，可以得到最终的最优判别器，形式化表达为：

通过上式可以得到density的表达式：
$$P_{\mathcal{X}}(x^{\ast })=\frac{1-D_{x^{\ast }}(x^{\ast })}{D_{x^{\ast }}(x^{\ast })}$$

下图可以很直观地说明该方法的思路，第一个场景中A是全新的信息，这时候判别器很容易判断它是来自新数据，所以输出1，所以该数据的density为0，第二个场景中A并不是完全没见过的信息，这时候判别器很难分辨它是来自新数据还是旧数据，判别器会输出0.5，进而其density为1。

但是对于连续状态空间来说，每个状态都是新状态（可以类比连续概率分布中某个点的概率为0来理解），即不会重复遇到同一个状态，所以该情况下density的输出会一直是0，这时候需要向exemplar数据中引入一些噪声，这里引入了高斯隐变量$z$和服从Bernoulli分布的变量$y$，并构成了以下的概率图模型：

该情况下判别器的训练所用目标函数为：

$p(z)$是一个多元高斯分布变量，KL散度项类似于regularizer，这里的$\beta$是超参数。训练过程中的过拟合意味着过于关注第一项，欠拟合说明更关注第二项，让$q(z|x)$更接近隐变量$z$的先验$p(z)$。这里的$\tilde{p}(s)$代表数据集的概率分布，一半数据来自于replay buffer，一半数据来自Exemplar states。

训练用的网络模型是amortized architecture，而不是每个数据点都训练一个判别器，如下图所示：

Heuristic Estimation of counts via errors

上述的几种方法还是有些复杂，有没有一种方法能更加简化地判断所遇到的状态信息是否是新的？这也是启发式估计方法的核心思路。现在假设已经有了智能体与环境的交互数据$\mathcal{D}=({\text{s}}_i,{\text{a}}_i)$，由于optimistic exploration的核心思想是判断状态是否为新，所以可以构造一个反映状态新旧程度的参数化函数${\hat{f}}_{\theta }(\text{s},\text{a})$，这里用神经网络表示该函数，输入是state-action pair，标签为$f^{\ast }(\text{s},\text{a})$，用MSE损失函数 $\mathcal{E}(\text{s},\text{a})=||{\hat{f}}_{\theta }(\text{s},\text{a})-f^{\ast }(\text{s},\text{a})|{|}^2$更新神经网络的参数，并将该误差作为探索用的bonus。

比较直接的选取反映状态新旧程度的参数化函数的方式是利用对下一个状态信息的预测，即 ${\text{s}}^{\prime }=f^{\ast }(\text{s},\text{a})$（类似model-based RL中的对dynamics的模拟），或更直接的一种方式就是随机取一组神经网络的参数，并用该参数下的输出作为Target。

3.2 Posterior Sampling (Probability Matching)类方法

在用于Multi-armed Bandits和MDP问题中的posterior sampling的方法中，其思路是先构建一个belief state $\hat{p}({\theta }_1,{\theta }_2,\dots ,{\theta }_n)$，然后从中采样得到各参数的值，并在当前参数的值下做出最优动作选择，并继续更新模型参数。这里的参数其实是做出每个动作得到reward的概率分布。类比大型MDP问题，Q-function与reward有异曲同工之妙。所以这里选择对Q-function的分布进行拟合，基本思路如下：

有了以上算法思路，那么如何得到Q函数的概率分布呢？可以通过bootstrap的方式学得Q函数的概率分布。给定一个数据集$D$，通过有放回地采样N次得到N个数据集$D_1,D_2,\dots ,D_N$，并且在$D_i$上训练N个模型$f_{{\theta }_i}$，即$Q_i(s,a)$，并构造出一个分布（这里感觉lecture中并么有讲清楚）。要在每个样本集上训练神经网络是非常复杂的，这里取了个巧，只用一个神经网络并且该神经网络中只有最后一层参数不是共享的。

该技巧的优点在于其生成的策略是一致的，比如在Atari Seaquest游戏中，如果使用epsilon greedy策略的话，其产生的动作是震荡的，波动较大；而通过random Q function产生的动作在整个episode中都是一致的。

3.3 Information Gain类方法

第三大类方法是引入信息增益。首先需要明确需要哪个变量的信息增益？有以下三种选项：reward的信息增益，状态密度$p(s)$的信息增益，dynamics的信息增益：$p(s^{\prime }|s,a)$。首先，如果环境的reward过于稀疏那么获取Reward的信息增益没有实际意义，估计状态密度的信息增益相比之下比较合理，因为状态密度的信息增益变多说明可能出现了比较新的状态；估计dynamics的信息增益也是比较合理的，其值也可以说明出现了比较新的状态。总体来说，在不确定使用具体哪个变量的信息增益时，精确表示该增益可能是不可解的。下面提供几种变量的信息增益：

一种是状态密度的对数
$$\text{Prediction Gain: }\log p_{{\theta }^{\prime }}(\text{s})-\log p_{\theta }(\text{s})$$
一种是dynamics: （VIME）
$$p_{\theta }(s_{t+1}|s_t,a_t)$$
这里先重新写一下information gain的公式：
$$\text{IG}(z,y)=E[\mathcal{H}(p(z))-\mathcal{H}(p(z)|y)]$$
信息增益又可以：
$$\text{IG}(z,y)=E[\mathcal{H}(p(z))-\mathcal{H}(p(z)|y)]=D_{\text{KL}}(p(z|y)||p(z))$$

这里的VIME方法是将$\theta$当作变量$z$，变量 $y=(s_t,a_t,s_{t+1})$，写成具体的表达式就是：
$$D_{\text{KL}}(p(\theta |h,s_t,a_t,s_{t+1})||p(\theta |h))$$
然后使用变分推断的方法用$q(\theta |\varphi )$估计概率分布$p(\theta |h)$，ELBO的公式为：$D_{\text{KL}}(q(\theta |\varphi )||p(h|\theta )p(\theta ))$，$q(\theta |\varphi )$的表示由独立的高斯分布变量的乘积组成，$\varphi$作为该分布的均值。根据新的状态转移数据$(s_t,a_t,s_{t+1})$来更新$\varphi$，得到${\varphi }^{\prime }$，使用$D_{\text{KL}}(q(\theta |{\varphi }^{\prime })||q(\theta |\varphi ))$当作approximate bonus

3.4 引入信息论中的互信息

后文有些方法主要基于信息论中的互信息（Mutual Information）的概念，公式如下：
$$\begin{gathered} I(x;y)=D_{\text{KL}}(p(x,y)||p(x)p(y))=E_{(x,y)\sim p(x,y)}\left[\log \frac{p(x,y)}{p(x)p(y)}\right] \\ =\mathcal{H}(p(y))-\mathcal{H}(p(y|x)) \end{gathered}$$
理解上述公式可以通过拆分联合概率分布$p(x,y)=p(x)p(y|x)$来理解，其与KL散度的第二项$p(x)p(y)$对比可看出，其实互信息本质上是计算$p(y|x)$与$p(x)$的熵的差异。

可以将上述公式用于RL中，$\pi (s)$用于表示在策略$\pi$下状态的边缘分布（marginal distribution），而$\mathcal{H}(\pi (s))$表示该分布的熵，直观理解就是策略的覆盖程度coverage，熵越大，该分布越随机，表示能访问更多的状态。而互信息的应用于最大化以下式子（该式子被称为empowerment）：
$$\mathcal{I}(s_{t+1},a_t)=\mathcal{H}(s_{t+1})-\mathcal{H}(s_{t+1}|a_t)$$
最大化上述表达式意味着最大化第一项，即让状态的分布更随机，这样智能体探索的覆盖面就比较大；最小化第二项意味着智能体做出动作之后所到达的状态是确定的，进而智能体能为了访问更多的状态只能进行更多的探索。

3.5 学习过程中不需要Reward function的方法

强化学习算法非常依赖于reward function的设计，那么有没有可能在强化学习过程中的不给定Reward function智能体还能自动学到很好的策略？该类方法受人类日常的决策过程所启发，例如一个餐具凌乱的餐桌上，人会自动将其整理好，如下图：

lecture 14用基于视觉信息的机器人任务作为例子。算法基本思路是由输入信息“联想”出尽可能多的潜在可能目标$z_{g1},z_{g2},\dots$，再由这些潜在可能目标信息推断出真实的目标$x_g$，随后智能体根据臆断出的目标执行策略并访问某个状态。统计这些状态，并对那些很少访问到的状态增加其权重，使其熵增，从而使算法访问到更多的状态。

这里用于更新的目标函数是最大化状态$S$和目标$G$的互信息：
$$\max \mathcal{I}(S;G)=\max \mathcal{H}(p(G)-\mathcal{H}(p(G|S))$$
最大化第一项代表着“联想”出来的目标的熵变大，即这些目标变得更加随机化，而训练的目的正是让策略能访问足够多的目标状态（等同于提高了智能体的探索效率，覆盖了更多的状态）。最大化第二项意味着如果随着策略$\pi$在参数更新之后变得越来越有效时，那么如果使用该策略的情况下，其达到目标状态$G$的概率是越来越确定的，即保证了任务的完成度。

3.6 State-Marginal Matching (SMM)

前文optimisitc exploration中的count-based方法的核心思路是让智能体的策略$\pi (a|s)$能够访问尽可能多的状态，如果访问到了新的状态，就增加一项Bonus Reward。

另一种类似的方法被称为intrinsic motivation的方法（本质方法个人认为并没有变化），思路是在reward中加入与状态概率分布有关的项作为Bonus reward，一般表达形式为：$\tilde{r}(s)=r(s)-\log p_{\pi }(s)$，这里的$p_{\pi }(s)$就是在策略$\pi$下得到的某个状态的概率分布，目标是最大化reward，那么这也意味着要最小化state marginal，其含义是概率密度越低，该状态就更有可能是新状态。

基于上述方法的一种提高智能体探索能力的思路是学习一个策略$\pi (a|s)$，其目标函数是减小以下式子：
$$D_{\text{KL}}(p_{\pi }(s)||p^{\ast }(s))$$
其中$p^{\ast }(s)$代表想要得到的状态概率分布target state density，类似于GAN中的真实数据。该方法也对上文intrinsic motivation的思路进行了修正，首先其reward函数是：
$$\tilde{r}(s)=\log p^{\ast }(s)-\log p_{\pi }(s)$$
下图中的橙色圆圈代表target state density，绿色椭圆代表已经访问的状态概率分布，Intrinsic motivation直观上只得到了单一的某个绿色椭圆。那么对其的修正可以是将访问过的状态density求并集，最终与target state density尽可能保持一致，最终返回一个混合策略（并不像intrinsic motivation中返回最近那一次的策略）。

其中一种特殊情况是：如果目标状态密度是个均匀分布，那么上述KL散度可以简化为状态边缘概率分布的熵。

（证明过程见论文）

那么以上讨论中覆盖足够多的state是否是一个好的探索目标（Exploration Objective）呢，或者说将目标状态goal state的概率分布尽可能贴近均匀分布是否有效？一个合理的解释是，假设在测试阶段，智能体已经知道它将得到的目标是非常随机的，即目标状态是均匀分布的，那么智能体能够做出的有效决策就是尽可能做最坏打算，即尽可能让目标状态的熵最大，从而访问更多的状态以应付更困难的任务。

3.7 另一种方法——cover the space of skills

另外一种探索的思路是将任务分成不同的子任务（用变量$z$表示任务的index），策略表达为$\pi (a|s,z)$。注意这里与3.5让智能体设想尽可能多的不同目标不同，在该设定下智能体可能并不能捕捉到所有行为，而分成不同的子任务会让智能体通过学得不同的技能（解决子任务的子策略）进而访问到更多的状态。

该思路的实现也是对reward function做改进，具体做法是将某个task下的reward表达为：$r(s,z)=\log p(z|s)$，而智能体策略的目标是最大化该reward，即
$$\pi (a|s,z)=\arg \underset{\pi }{\max }\sum _z{E}_{s\sim \pi (s|z)}[r(s,z)]$$

这里智能体所经历的状态被输入给一个判别器，其输出为task index（或与之对应的skill），得到该Index之后将其输入给agent的策略函数，进一步与环境交互。

该方法其实本质上最大化了以下的互信息：
$$\mathcal{I}(z,s)=\mathcal{H}(z)-\mathcal{H}(z|s)$$

其中最大化第一项说明让子任务出现的概率越来越随机，最坏情况是均匀分布，而最大化第二项（$-\mathcal{H}(z|s)$）意味着让某个状态$s$属于某个子任务的概率越来越确定，由于任务Index是非常随机的，那么进而也就能让智能体访问更多的状态。

（个人认为本节内容非常不好理解，我之后也会再继续加深一下对这些探索方法的认知然后再更新本文的一些内容）