count-based exploration

Count-Based Exploration is an exploration strategy that rewards visiting less-visited states — maintaining visitation counts N(s) and providing an exploration bonus inversely related to the count: r_bonus propto 1/sqrt(N(s)), encouraging the agent to visit novel states.

Count-Based Methods

• Tabular: Exact counts in tabular settings — r_bonus = beta / sqrt(N(s)).
• Hash-Based: Hash continuous states to bins and count bin visits — SimHash for high-dimensional states.
• Density Models: Estimate pseudo-counts using density models — hat(N)(s) from pixel-level density estimation.
• Successor Features: Use successor features for count-free, generalized exploration bonuses.

Why It Matters

• Theoretical: Count-based exploration has PAC-MDP guarantees — provably efficient in tabular settings.
• Scaling: The challenge is scaling exact counts to high-dimensional (pixel) observations — density models approximate this.
• Classic: Rooted in classical bandit theory (UCB) — exploration bonus decreases as uncertainty decreases.

Count-Based Exploration is go where you haven't been — rewarding novelty by tracking how often each state has been visited.