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} = eta / 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.