计数与伪计数探索

表格情形下 $1/\sqrt{N(s)}$ 的探索奖励有理论保证；高维下用密度模型或哈希得到伪计数。本章讲伪计数的定义、CTS/PixelCNN 密度模型、SimHash，以及它们在 Montezuma's Revenge 上的效果。

表格情形：计数奖励

最古老的探索奖励是计数：访问次数少的状态给额外奖励。表格情形下有清晰的理论形式（Strehl & Littman）：内在奖励取

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

其中 $N(s)$ 是状态 $s$ 被访问的次数。直觉：第一次到达给大奖励，越常去给得越少； $\beta$ 是内在奖励的尺度。对满足条件的 $\beta$ ，这个奖励使"贪心 + 探索"在多项式样本内逼近最优——计数探索有理论保证。

问题显然：高维像素空间里 $N(s)$ 恒为 1——几乎不会访问同一个状态两次，计数失效。需要把"访问"的概念推广到表示空间。

伪计数：把密度模型的增益变成计数

伪计数（pseudo-count, Bellemare et al., 2016）的想法：用密度模型 $p_\theta(x)$ （学状态分布的生成模型）代替计数器。定义预测增益（prediction gain）——见到新状态 $x$ 前后模型对它的对数概率变化：

$\mathrm{PG}(x) = \log p_\theta(x) - \log p_\theta'(x),$

其中 $p_\theta'$ 是"假装把 $x$ 计入训练后再归一化"的模型。对两参数化的密度模型（每次只更新两个参数），预测增益可以精确地翻译成一个伪计数：

$\hat{N}(x) = \frac{p_\theta(x)\,(1 - p_\theta'(x))}{p_\theta'(x) - p_\theta(x)}, \qquad \hat{\rho}(x) = \frac{\hat{N}(x)}{\hat{N}_{\text{total}} + 1},$

$\hat{\rho}$ 是伪计数比率，行为上近似 $1/\sqrt{\hat{N}}$ 的推广。直觉：新状态让密度模型的预测提升得多，说明它"新鲜"。

密度模型的实现

CTS（Columnar Convolutional Structure）：逐像素自回归的简单模型，Bellemare 等人 2016 的原始实现；
PixelCNN：更强的自回归图像模型，预测增益更准；
SimHash：不做密度模型，把观测编码后哈希到桶，桶内计数——简单、快，但完全依赖编码的质量（随机投影的编码保留了什么信息决定探索去哪里）。

密度模型也有失效模式：模型对从没见过的东西给出过低的 $p(x)$ （密度模型可能给新状态极低的概率而非"新鲜"的信号），需要小心校准。

Montezuma's Revenge 与效果

伪计数 + DQN 在 Montezuma's Revenge 上拿到了当时最高的分数——这是内在奖励方法第一次在"稀疏奖励 + 高维像素"的标志性难题上生效。方法的关键配方：

内在与外在奖励分开估计：两个价值头，避免内在奖励污染外在价值的尺度（→ 好奇心与预测误差：ICM 与 RND）；
内在奖励随时间衰减（ $\beta$ 退火）：探索终究要给利用让路，不衰减会停在"到处看看"而找不到出口；
新鲜度的定义决定探索的方向：密度模型学到什么，策略就去哪——这是所有内在奖励方法的共性（也是共性风险）。

定位

计数与伪计数是"去得少的地方给奖励"这一路线的代表：与好奇心（预测误差）、信息增益（贝叶斯）同属内在奖励家族（→ 第六卷导读）。它的理论根基最清晰（表格情形有保证），工程上则依赖密度模型或哈希的质量。

本章要点

伪计数把密度模型的预测增益转化为计数
哈希方法简单但依赖表示
内在奖励应随时间衰减