伪计数：基于计数的寻访方法

虽然像 $\epsilon$ -贪心这类简单的行动策略鼓励随机动作，但在状态空间庞大或奖励稀疏的环境中，它们通常表现不足。这类方法寻访效率不高，可能遗漏状态空间中重要的部分。基于计数的寻访提供了一种更有方向性的方法，它明确激励智能体访问不常遇到的状态或状态-动作对。其基本原则很简单：“如果你不常来这里，那它可能很有价值。”

直观理解：鼓励新颖

想象一个智能体在迷宫中行进。一个 $\epsilon$ -贪心智能体可能会反复走进熟悉的通道。然而，一个基于计数的智能体则会对不常行进的路径感到“吸引”。这种吸引表现为添加到环境奖励信号中的一个寻访增益。状态（或状态-动作对）被访问得越少，再次访问它时获得的增益就越高。

表格计数：基本思路

在状态和动作数量有限且可管理的简单环境中（即“表格型”情况），我们可以直接计算访问次数。设 $N(s)$ 为状态 $s$ 被访问的次数，或 $N(s, a)$ 为在状态 $s$ 中动作 $a$ 被采取的次数。添加到外部奖励 $r_e$ 的寻访增益 $r^+$ 的常见形式基于“不确定性下的乐观主义”原则：

r^+(s) = \frac{\beta}{\sqrt{N(s)}} \quad \text{或} \quad r^+(s, a) = \frac{\beta}{\sqrt{N(s, a)}}

其中， $\beta$ 是一个控制寻访强度的超参数 (parameter) (hyperparameter)。用于学习的总奖励变为 $r = r_e + r^+(s)$ （或 $r = r_e + r^+(s, a)$ ）。随着状态被访问得越来越频繁， $N(s)$ 增加，寻访增益随之减小，使得智能体最终根据实际奖励 $r_e$ 专注于利用所学策略。像 MBIE-EB（基于模型的区间估计与寻访增益）这样的算法将这种思路形式化。

规模的挑战：伪计数

在庞大或连续的状态空间中，直接计数会失效。原因何在？因为智能体可能永远不会两次访问完全相同的高维状态（例如来自摄像头的图像）。我们需要一种方法，将访问计数的思路泛化到未见过但相似的状态。这引出了伪计数的构思。

我们不使用精确计数，而是使用一个基于已访问状态历史训练的密度模型 $p(s)$ 。该模型估计给定状态 $s$ 周围的概率密度。

如果 $s$ 位于之前频繁访问的区域， $p(s)$ 将较高。
如果 $s$ 位于新颖的区域， $p(s)$ 将较低。

核心思路是从这种密度估计 $p(s)$ 中推导出一个伪计数 $N̂(s)$ 。伪计数 $N̂(s)$ 近似表示与 $s$ “相似”的状态被访问了多少次。

我们如何将密度 $p(s)$ 与伪计数 $N̂(s)$ 关联起来？考虑一个状态序列 $s_1, s_2, ..., s_n$ 。在该序列上训练的密度模型可能会学习到 $p(s)$ 。现在，如果我们观测到一个新状态 $s_{n+1}$ ，我们可以问：根据模型， $p(s_{n+1})$ 的概率是多少？这个概率反映了新状态的“熟悉”程度。

一个重要的见解来自将密度模型 $p(s)$ 分配的概率与简单记录和预测状态 $p_{REC}(s)$ 分配的概率联系起来。可以证明，在关于密度模型学习过程的某些假设下，预测概率 $p(s)$ 通过以下方式与伪计数 $N̂(s)$ 关联：

p(s) \approx \frac{N̂(s) + \delta}{ \sum_{s'} (N̂(s') + \delta)}

其中 $\delta$ 是一个小的平滑常数。更具实际意义的是从再次观测 $s$ 时密度的增加中得出的关系。设 $p_n(s)$ 为经过 $n$ 次观测后的密度估计，而 $p_{n+1}(s)$ 为再次观测 $s$ 后的估计。伪计数 $N̂(s)$ 应满足：

p_{n+1}(s) - p_n(s) \propto \frac{1}{N̂(s)}

这意味着如果当前伪计数较低，再次观测某个状态会使其密度增加更多。虽然直接计算这个差值通常很复杂，但几种密度估计方法允许我们近似计算 $N̂(s)$ 或直接使用 $p(s)$ 来定义寻访增益。

寻访增益的计算与表格型情况类似，但使用的是伪计数：

r^+(s) = \frac{\beta}{\sqrt{N̂(s)}}

这种增益鼓励智能体向密度模型认为新颖的状态（低密度、低伪计数）移动。

估计伪计数的方法

在高维空间 (high-dimensional space)中，存在几种实现伪计数密度估计的技术：

基于哈希的方法：这些方法使用哈希函数或学习到的特征嵌入 (embedding) $\phi(s)$ ，将高维状态 $s$ 映射到低维（通常是离散）表示 $z = \phi(s)$ 。然后在此压缩空间中维护计数 $N(z)$ 。
- 示例：局部敏感哈希（LSH）可以将相似状态分组到相同的桶中。随机投影也可以生成特征。
- 优点：比复杂的密度模型计算更简单。
- 缺点：性能严重依赖于哈希函数或特征 $\phi$ 的质量。相似状态可能映射到不同的桶（低召回率），或者不相似状态映射到相同的桶（低精度）。需要精心设计 $\phi$ 。
生成模型：深度生成模型，针对观测到的状态流 $s_t$ 进行训练，可以自然地估计密度或新颖性。
- 示例：
  - PixelCNN/PixelRNN：自回归 (autoregressive)模型，根据之前的像素预测图像中的像素值。分配给图像 $s$ 的似然度 $p(s)$ 反映了该图像根据模型学习到的训练图像分布的可预测（常见）程度。较低的似然度意味着较高的新颖性。
  - 变分自编码器（VAEs）或生成对抗网络 (GAN)（GANs）：虽然不直接提供密度 $p(s)$ ，但重构误差（VAEs）或判别器输出（GANs）有时可以作为新颖性的代理，尽管这对于伪计数的理论基础较少。
- 推导增益：伪计数 $N̂(s)$ 通常可以与模型的似然度 $p(s)$ 相关联。例如，一些方法根据观测 $s$ 会在多大程度上提高模型在 $s$ 上的似然度来近似计算 $N̂(s)$ 。一个更简单的方法是直接使用似然度：较低的 $p(s)$ 带来更高的增益。
- 优点：可以捕捉图像等高维数据中的复杂结构。无需手动进行特征工程。
- 缺点：训练和查询的计算成本高昂。对超参数 (parameter) (hyperparameter)敏感。可能关注统计上新颖但与状态无关的方面（例如，背景噪声）。
上下文 (context)树切换（CTS）模型：这些是强大的序列模型，可以为转换 $p(s' | s, a)$ 构建自适应密度估计。它们在强化学习 (reinforcement learning)中有效地用于伪计数估计。

整合增益

无论伪计数 $N̂(s)$ （或新颖性的代理）如何计算，寻访增益 $r^+ = \beta / \sqrt{N̂(s)}$ 通常会添加到从环境中获得的外部奖励 $r_e$ 中。然后，学习算法（例如，DQN，PPO）使用组合奖励 $r = r_e + r^+$ 来更新其价值函数或策略。

流程图说明了伪计数如何在强化学习 (reinforcement learning)循环中生成寻访增益。状态被输入到密度模型中，该模型生成用于计算增益的伪计数。此增益会修改强化学习智能体使用的奖励信号。

考量与取舍

计算成本：训练和查询密度模型，尤其是深度生成模型，可能比简单的寻访方法计算量显著更高。
模型选择：伪计数寻访的有效性严重依赖于所选的密度模型及其捕捉状态空间中新颖性相关方面的能力。选择不当的模型可能导致寻访效率低下。
高维度：密度估计本质上受“维度灾难”的影响。尽管哈希或深度模型等技术旨在缓解这一点，但性能在极高维空间 (high-dimensional space)中仍可能下降。
不相关的新颖性：有时，密度模型可能会识别出与实际任务或潜在奖励无关的新颖性（例如，图像中随机的背景变化）。这可能导致智能体寻访到状态空间中无产出的部分。将基于计数的寻访与任务相关信息相结合是持续研究的一个领域。

使用伪计数的基于计数的寻访提供了一种有原则且通常有效的方式来推动复杂环境中的寻访行为。通过将访问不熟悉状态的直观感受形式化，这些方法使智能体能够系统地收集信息并应对随机寻访失效的难题。它们代表了对简单启发式方法的重大进步，推动了更智能的寻访行为。

这部分内容有帮助吗？

参考文献

A Reinforcement Learning Algorithm for MDPs with Large State Spaces Based on Interval Estimation, Alexander L. Strehl, Michael L. Littman, 2008 Advances in Neural Information Processing Systems, Vol. 21 (Neural Information Processing Systems Foundation, Inc.) - 介绍了基于区间估计的模型学习与探索奖励（MBIE-EB），该基础算法通过“面对不确定性的乐观主义”形式化了用于表格或大型状态空间的基于计数的探索。
Unifying Count-Based Exploration and Intrinsic Motivation, Marc G. Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, Remi Munos, 2016 Advances in Neural Information Processing Systems (NIPS) DOI: 10.48550/arXiv.1606.01868 - 这篇重要论文提出了利用密度模型（如PixelCNN）估计伪计数，以实现深度强化学习中的有效探索，并将其与内在动机相关联。
A Survey of Exploration Strategies in Reinforcement Learning, Yuhao Li, Zhen Wang, and Yang Yu, 2021 Artificial Intelligence Review, Vol. 54 (Springer) DOI: 10.1007/s10462-021-09950-8 - 全面概述了强化学习中的各种探索策略，包括基于计数的方法和内在动机方法。