Counting the Unseen: Count-Based Exploration

From bandit bonuses to big worlds

UCB taught us that uncertainty shrinks with the number of tries — its bonus depends on a count. Count-based exploration carries that idea straight into full RL: keep a tally N(s) of how many times each state s has been visited, and hand the agent an exploration bonus that is large for rarely-seen states and small for familiar ones. A common form is a bonus proportional to 1/√N(s), echoing UCB.

Mechanically, the bonus is just added to the environment's reward before learning. The agent's value method (Q-learning, an actor-critic, anything) then treats "go somewhere new" as intrinsically rewarding. This is exactly optimism under uncertainty expressed as a reward: novel states look valuable until visited enough to know better.

# count-based exploration bonus, added to the real reward
N[s] += 1                       # update the visit count for state s
bonus = beta / sqrt(N[s])       # large for rare states, decays as N grows
reward_for_learning = env_reward + bonus

A visit-count bonus turns optimism into an intrinsic reward signal.

The problem: nothing repeats

Counting works perfectly in small, tabular worlds — a 10×10 grid has 100 states you can count exactly. But in any interesting problem the state is a raw image or a continuous vector, and the agent never sees the exact same state twice. Every count N(s) is stuck at either 0 or 1. The bonus becomes useless: everything is equally "novel," forever.

Pseudo-counts: counting with a density model

Pseudo-counts recover counting in high dimensions with one clever observation. Train a density model — a model that estimates the probability ρ(s) of any state under the data seen so far. A state the agent has visited often gets a high probability; a genuinely new state gets a low one. The model generalizes: visiting one state also raises the probability of similar states, exactly as a sensible count should.

The trick: a pseudo-count can be derived from how much the density rises after you train on one more occurrence of that state. If seeing s once barely changes ρ(s), the model has effectively seen it many times — a high pseudo-count. If one sighting jolts ρ(s) upward, it was nearly new — a low pseudo-count. Feed that pseudo-count into the same 1/√N bonus and count-based exploration suddenly works on raw pixels. This was the engine behind the first agents to make real progress on Montezuma's Revenge.

\hat{N}(s) = \frac{\rho(s)\,\bigl(1-\rho'(s)\bigr)}{\rho'(s)-\rho(s)}

The pseudo-count recovers an effective visit count from how much the density model's probability rises after training on one more occurrence of the state.

Novelty search: novelty as the whole goal

Count and pseudo-count bonuses are a quiet vote for novelty. Novelty search takes the idea to its limit: in its purest form it ignores the task reward entirely and rewards the agent only for reaching states unlike anything it has reached before, measured by distance to its archive of past behaviors. Counter-intuitively, chasing pure novelty sometimes solves deceptive tasks that direct reward-seeking cannot — because it refuses to get trapped polishing a mediocre strategy.

In practice the strongest agents blend the two: keep the real reward and add a novelty/count bonus, so the agent both seeks the goal and refuses to stop exploring. This combination is the bread-and-butter recipe for sparse-reward problems, the focus of the final guide.

r^{+}_{t} = r_{t} + \frac{\beta}{\sqrt{N(s_t)}}

The intrinsic exploration bonus β⁄√N(s) is added to the real reward — large for novel states and shrinking with every visit, so the weight β must be tuned and decayed.