pseudo-counts

Count-based bonuses are wonderful until the state space is huge — in an Atari game you will essentially never see the exact same screen twice, so literal counts are all zero or one and tell you nothing. Pseudo-counts rescue the idea by replacing the literal tally with a number inferred from a learned density model: how surprised is the model by this state, and how much less surprised does it become after seeing it once?

The trick is to fit a probabilistic model that assigns each state a probability, then read off an effective visit count from how that probability rises after a single update — a state whose probability barely moves has effectively been seen many times. Plugging this pseudo-count into the usual one-over-square-root bonus gives a count-based signal that works in pixels and other high-dimensional spaces, and it was behind some of the first deep agents to make progress on notoriously hard games.