Count-Based Exploration

Keep a tally of where you have been and pay yourself to go where the tally is low. Rare states earn a big bonus, visited ones earn almost nothing.

A density shift from 0.05 to 0.06 means a pseudo-count of 4.70 paying 0.46, and familiarity pushes the count to 8.90 paying 0.34

Why Does This Exist?

Sparse rewards starve random wandering. If the maze pays only at the exit, epsilon-greedy twitching may never stumble through the door. You can see this in exploration vs exploitation: dithering has no memory of where it has been.

Tables solve it with optimism. Visit a state rarely and it earns a bonus near $\beta / \sqrt{N(s)}$ , with $N(s)$ the visit count and $\beta$ the exploration strength. Unvisited states glow and pull the agent in. That is the upper confidence bound idea carried into RL.

Pixels break the table. No two camera frames match exactly, so every raw count sits at $1$ and every state looks new. This page generalizes the tally with density models and hashing, so noisy nets style dithering is not your only option in big spaces.

Think of It Like This

A passport stamp book for trails

You hike with a stamp book. The first stamp at a new hut thrills you. The hundredth stamp at the same hut bores you. The thrill fades like one over the root of visits, which is exactly the bonus shape.

Backcountry has no huts, and every meadow looks a bit different. So you carry a field guide instead. When a valley matches nothing in the guide, you call it new and push on. As the guide fills with that valley type, the same view stops paying. The guide is the density model, and its surprise is your pseudo-count.

Where it stops: a snowstorm of static also surprises the guide forever. Real hikers ignore whiteout; naive tallies do not, and that failure has its own name below.

How It Actually Works

Total reward is extrinsic plus intrinsic: $r_{\text{total}}(s, a) = r_{\text{ext}}(s, a) + r_{\text{int}}(s)$ , where $r_{\text{ext}}$ is the world and $r_{\text{int}}$ is your curiosity pay. The classic pay is:

r_{\text{int}}(s) = \frac{\beta}{\sqrt{N(s) + c}}

Here $\beta$ sets exploration strength and $c$ is a small constant that avoids dividing by zero. Rare states pay big and the pay dies off as visits pile up.

Pseudo-counts extend this to states you never exactly revisit. Keep a density model $\rho$ that predicts how likely each state is. Before seeing $x$ it says $\rho(x)$ , after absorbing $x$ it says $\rho'(x)$ . If the model found $x$ surprising, $\rho'$ jumps above $\rho$ , and that jump implies a low count:

\hat{N}(x) = \frac{\rho(x)(1 - \rho'(x))}{\rho'(x) - \rho(x)}

Big jump means small $\hat{N}$ , which means big bonus through the same root rule. Familiar states barely move the model, so $\hat{N}$ grows large and the bonus fades.

The cheap alternative is hashing. Project the state through a random matrix and take signs, $\phi(s) = \text{sgn}(A s)$ , then count hash buckets instead of states. Near twins land in one bucket, so counting buckets approximates counting neighborhoods with no neural net at all.

Worked example

Set $\beta = 1.0$ and $c = 0.01$ . A new corridor gives $\rho = 0.05$ before and $\rho' = 0.06$ after:

\hat{N} = \frac{0.05 \times (1 - 0.06)}{0.06 - 0.05} = \frac{0.047}{0.01} = 4.70

r_{\text{int}} = \frac{1.0}{\sqrt{4.70 + 0.01}} = \frac{1.0}{\sqrt{4.71}} \approx 0.46

With no outside reward, the agent banks $0.46$ for stepping there.

Later the corridor is familiar: $\rho = 0.10$ , $\rho' = 0.11$ . Then $\hat{N} = 0.10 \times 0.89 / 0.01 = 8.90$ and $r_{\text{int}} = 1.0 / \sqrt{8.91} \approx 0.34$ . The bonus fell by about 27 percent, so attention drifts to regions still near zero.

Code

The tally plus the bonus in plain Python:

1rho: float = 0.052rho_next: float = 0.063pseudo: float = rho * (1.0 - rho_next) / (rho_next - rho)4bonus: float = 1.0 / (pseudo + 0.01) ** 0.55print(f"{pseudo:.2f} {bonus:.2f}")  # -> 4.70 0.466
7rho2: float = 0.108rho2_next: float = 0.119pseudo2: float = rho2 * (1.0 - rho2_next) / (rho2_next - rho2)10bonus2: float = 1.0 / (pseudo2 + 0.01) ** 0.511print(f"{pseudo2:.2f} {bonus2:.2f}")  # -> 8.90 0.34

Both lines match the hand arithmetic. Raise $\beta$ to explore harder, lower it to exploit sooner.

Watch Out For

Staring at static forever

Symptom: the agent parks in front of flicker, like TV snow or rustling leaves, racking up novelty while the real task sits unsolved. Raw pixel density can never memorize pure noise, so the jump $\rho' - \rho$ stays alive and the bonus never dies.

Fix: never tally raw pixels. Count in a space that keeps only what your actions control, such as inverse-model features or random network projections, and the static stops paying.

The Quick Version

Total reward adds a curiosity bonus shaped like $\beta / \sqrt{N + c}$ that fades as visits grow.
Pseudo-counts read the bonus off a density jump: $\rho$ from $0.05$ to $0.06$ means count $4.70$ paying $0.46$ .
Familiar ground at $\rho$ from $0.10$ to $0.11$ means count $8.90$ paying $0.34$ , down about 27 percent.
Hashing states with random signs counts neighborhoods with zero training cost.
Raw pixel tallies chase noise, so count features your actions actually steer.