unifying-count-based-exploration-and-intrinsic-motivation.md

DQN-CTS

Unifying Count-Based Exploration and Intrinsic Motivation

我们考虑一个代理对其环境的不确定性，以及将这种不确定性分散到不同状态的问题。具体来说，我们关注非表格强化学习中的探索问题。从内在动机文献中得到启发，我们使用密度模型来测量不确定性，并提出了一种从任意密度模型中导出伪计数的新算法。这种技术使我们能够将基于计数的勘探算法推广到非表格情况。我们将我们的想法应用于雅达利2600游戏，从原始像素中提供合理的伪计数。我们将这些伪计数转化为探索奖励，并在许多游戏中获得显著改善的探索，包括臭名昭著的困难MONTEZUMA 'SREVENGE。

马尔可夫决策过程( MDP)的探索算法通常关注于降低代理对环境回报和转换函数的不确定性。在白板中，这种不确定性可以使用从切尔诺夫边界导出的置信区间来量化，或者从环境参数的后验值来推断。事实上，置信区间和后验收缩都是状态行为访问计数 $$( x,a )$$ 的平方根倒数，这使得这个量成为大多数理论探索结果的基础。

基于计数的探索方法直接使用访问计数来指导代理人的行为以减少不确定性。例如Model-based Interval Estimation with Exploration Bonuses使用如下的增强版Bellman方程：

$$ V(x)=\max {a \in \mathcal{A}}\left[\hat{R}(x, a)+\gamma \mathbb{E}{\hat{P}}\left[V\left(x^{\prime}\right)\right]+\beta N(x, a)^{-1 / 2}\right] $$

该奖励考虑了转移和奖励函数的不确定性，并且能够对代理的次优性进行有限时间限制。

内在动机旨在为探索提供定性指导，这个指导可以概括为“探索让你惊讶的事情”，一种典型的方法基于预测误差或者学习进度。如果 $$e_n(A)$$ 是代理在某一事件A发生时所犯的错误，并且在观察到一个新的信息后，再得到错误 $$e_{n+1}(A)$$ ，则学习进度为：

$$ e_{n}(A)-e_{n+1}(A) $$

在本文中，我们提供了正式的证据，证明内在动机和基于计数的探索是同一枚硬币的两面。我们的贡献是提出一个新的量化机制，即伪计数，它用信息增益作为学习进度与基于计数的探索联系起来。我们从状态空间上的密度模型中导出伪计数。这与更传统的内在动机方法不同，后者考虑了转换模型的学习进度。我们在这里介绍的伪计数最好被认为是“探索的函数逼近”。

方法

Notation

密度模型

$$ \rho_{n}(x) :=\rho\left(x ; x_{1 : n}\right) $$

即 $$X_{n+1}=x \text { given } X_{1} \ldots X_{n}=x_{1 : n}$$ 的概率

经验分布，其中 $$N_{n}(x) :=N\left(x, x_{1 : n}\right)$$ 是经验计数函数

$$ \mu_{n}(x) :=\mu\left(x ; x_{1 : n}\right) :=\frac{N_{n}(x)}{n} $$

在我们的设置中，密度模型假定状态独立（但不一定相同）分布的任何模型; 因此，密度模型是一种特殊的生成模型。我们强调密度模型不同于前向模型，前向模型考虑了连续状态之间的时间关系。

From Densities to Counts

_实际上_访问次数 $$N_n(x )$$ 在实际环境中没有直接用处，因为很少重新访问状态。具体来说， $$N_n(x )$$几乎总是零。估计代理人知识的不确定性，我们必须寻找一个跨状态泛化的量化。 在内在动机文献的指导下，我们现在得出这样的量化，我们称它为伪计数，就是用一个密度模型$$\rho$$估计$$N_n(x )$$ 。

Pseudo-Counts and the Recoding Probability

我们给出了密度模型 $$\rho$$ 。 密度模型可以是近似的，有偏差的，甚至是不一致的。我们首先介绍状态 $$x$$ 的_recoding probability：_

$$ \rho_{n}^{\prime}(x) :=\rho\left(x ; x_{1 : n} x\right) $$

$$ \rho_{n}^{\prime}(x)=\operatorname{Pr}{\rho}\left(X{n+2}=x | X_{1} \ldots X_{n}=x_{1 : n}, X_{n+1}=x\right) $$

我们现在假设两个未知数:伪计数函数 $$\hat{N}_{n}(x)$$ 和伪总计数函数 $$\hat{n}$$ ，并服从以下约束

$$ \rho_{n}(x)=\frac{\hat{N}{n}(x)}{\hat{n}} \quad \rho{n}^{\prime}(x)=\frac{\hat{N}_{n}(x)+1}{\hat{n}+1} \ \ \ \ \ \ \ \ \ \ (1) $$

注意 $$\hat{N}{n}(x)=0(\text { with } \hat{n}=\infty) \text { when } \rho{n}(x)=\rho_{n}^{\prime}(x)=0$$ ，且当 $$\rho_{n}(x)<\rho_{n}^{\prime}(x)=1$$ 时不一致。

换句话说:我们要求，在观察到 $$x$$ 的一个实例后，密度模型对同一 $$x$$ 的预测的增加应对应于伪计数的单位增加。伪计数本身是从求解线性系统中推导出来的:

$$ \hat{N}{n}(x)=\frac{\rho{n}(x)\left(1-\rho_{n}^{\prime}(x)\right)}{\rho_{n}^{\prime}(x)-\rho_{n}(x)}=\hat{n} \rho_{n}(x) \ \ \ \ \ \ \ \ \ \ (2) $$

定义 Learning-positive density model

Estimating the Frequency of a Salient Event in FREEWAY

作为一个说明性的例子，我们使用我们的方法来估计Atari 2600视频游戏FREEWAY中频繁事件的发生次数(图1，截屏)。我们将演示以下内容：

1. 对于新事件，伪计数大致为零
2. 他们表现出可信的量级
3. 他们尊重状态频率的顺序
4. 它们随着实际计数线性增长(平均)
5. 它们在非平稳数据存在的情况下很稳健

在高速公路上，代理人必须让一只鸡穿过繁忙的道路。作为我们的例子，我们考虑估计鸡到达屏幕顶部的次数。就像雅达利2600游戏一样，这一自然显著的事件与分数的增加相关联，这也转化为积极的回报。我们可以合理地想象知道我们对环境的这一部分有多确定是有用的。穿越后，鸡被传送回屏幕底部。

为了突出伪计数的稳健性，我们考虑一个等待250,000帧的非平稳策略，然后将UP动作应用于250,000帧，然后等待，然后继续UP。 该事件仅发生在UP期间。 它也发生在汽车处于不同位置，因此需要概括。 作为参考，我们记录了显著事件和访问鸡的起始位置的伪计数。

我们使用了一个简化的，像素级的Atari 2600帧CTS模型，由Bellemare等人(2014)提出，忽略了时间依赖性。虽然CTS模型与最先进的图像密度模型相比相当贫乏。其基于计数的性质导致极快的学习，使其成为一个吸引人的探索候选。关于该模型的更多细节可在附录中找到。

检查图1中描述的伪计数可以确认它们显示出上面列出的理想属性。特别地，在显著事件第一次出现时，伪计数几乎为零；它在第三阶段略有增加，因为显著事件和参考事件有一些共同的结构；自始至终，它都小于参考伪计数。平均值的线性和对非平稳性的鲁棒性直接来自图表。然而，请注意，伪计数只是实际访问计数的一小部分(因为我们可以定义“真实”) :到行程结束时，开始位置已经被访问了大约140，000次，屏幕的最上面部分被访问了1285次。此外，记录的伪计数的比率不同于实际计数的比率。这两种影响都是可以量化的，我们将再后面说明。

The Connection to Intrinsic Motivation

在论证了伪计数恰当地概括了访问计数之后，我们现在将表明它们与信息增益密切相关，信息增益通常用于量化新颖性或好奇心，并作为一种内在的奖励。信息增益的定义关系到一类密度模型 $$\mathcal{M}$$ 上的混合模型$$\xi$$ ：

$$ \xi_{n}(x) :=\xi\left(x ; x_{1 : n}\right) :=\int_{\rho \in \mathcal{M}} w_{n}(\rho) \rho\left(x ; x_{1 : n}\right) \mathrm{d} \rho $$

其中 $$w_{n}(\rho)$$ 是量化权重，并且是递归定义的：

$$ w_{n+1}(\rho) :=w_{n}\left(\rho, x_{n+1}\right) \quad w_{n}(\rho, x) :=\frac{w_{n}(\rho) \rho\left(x ; x_{1 : n}\right)}{\xi_{n}(x)} $$

然后，信息增益是先验和后验的KL散度

$$ \mathrm{IG}{n}(x) :=\mathrm{IG}\left(x ; x{1 : n}\right) :=\mathrm{KL}\left(w_{n}(\cdot, x) | w_{n}\right) $$

计算复杂密度模型的信息增益通常是不切实际的，如果不是非常简单的话。 然而，我们称之为预测收益的数量为我们提供了一个很好的信息增益近似值。 我们将密度模型 $$ρ$$ （特别是ξ）的预测增益定义为 $$recoding log-probability$$ 和 $$log-probability$$ 之间的差异。

$$ \mathrm{PG}{n}(x) :=\log \rho{n}^{\prime}(x)-\log \rho_{n}(x) $$

当且仅当 $$ρ$$ 为learning positive时，预测增益是非负的。它与伪计数相关:

$$ \hat{N}{n}(x) \approx\left(e^{\mathrm{PG}{n}(x)}-1\right)^{-1} $$

如下定理所示，预测增益允许我们将伪计数和信息增益联系起来

定理1表明，使用与 $$\hat{N}_{n}(x)^{-1 / 2}$$ 成比例的探索奖励，类似于MBIE-EB 奖励，会导致一种行为，至少与从信息增益奖励中获得的行为一样具有探索性。由于伪计数对应于表格设置中的经验计数，这种方法还保留了已知的理论保证。事实上，我们确信伪计数可以用于证明非表格设置中的类似结果。

Asymptotic Analysis

在本节中，我们分析比率 $$\hat{N}{n} / N{n}$$ 的极限行为。我们使用这种分析来评估从表格密度模型(即维护状态访问计数的模型)导出的伪计数的一致性。

我们还假设经验分布 $$μ_n$$ 指向分布 $$μ$$ ，并且对于recoding probability写为 $$\mu_{n}^{\prime}(x)$$ 。 我们从密度模型的两个假设开始。

假设（a）表明， $$ρ$$ 最终应该将概率与经验分布 $$μ(x)$$ 的极限成比例。 另一方面，假设( b )限制了 $$ρ$$ 相对于 $$μ$$ 的learning rate。

该模型的相对变化率在伪计数与经验计数的比率中起着至关重要的作用，这种变化率需要 $$\dot{r}(x)$$ 收敛。

一些公式的详细推导请参阅原文附录

实验

DQN

设计数探索奖励为：

$$ R_{n}^{+}(x, a) :=\beta\left(\hat{N}_{n}(x)+0.01\right)^{-1 / 2} $$

其中 $$\beta=0.05$$

Actor-Critic