count-based exploration

This is one of the most intuitive ways to encourage curiosity: keep a tally of how many times the agent has visited each state, and hand out a bonus reward for visiting states it has seen rarely. Novel states glow brightly, familiar ones dim out. Added to the real reward, this bonus quietly turns the agent's value-maximising drive into a drive to seek out the unfamiliar corners of the world.

The bonus typically scales as one over the square root of the count, echoing the UCB confidence term, so rarely-seen states are strongly attractive and well-trodden ones are not. In a small, discrete world this works beautifully and comes with theory. But it breaks the moment states are images or continuous vectors, where almost every state is visited exactly once and the counts carry no signal — the problem that pseudo-counts were invented to solve.