While simple exploration strategies like $\epsilon$ -greedy encourage random actions, they often prove insufficient in environments with vast state spaces or sparse rewards. Such methods explore inefficiently, potentially missing critical areas of the state space. Count-based exploration offers a more directed approach by explicitly incentivizing the agent to visit states or state-action pairs that it hasn't encountered frequently. The underlying principle is simple: "if you haven't been here often, it might be interesting."

The Intuition: Rewarding Novelty

Imagine an agent navigating a maze. An $\epsilon$ -greedy agent might repeatedly stumble down familiar corridors. A count-based agent, however, would feel an "attraction" towards paths it hasn't explored much. This attraction comes in the form of an exploration bonus added to the environment's reward signal. The less a state (or state-action pair) has been visited, the higher the bonus for visiting it again.

Tabular Counts: The Basic Idea

In simple environments with a finite, manageable number of states and actions (the "tabular" case), we can directly count visits. Let $N(s)$ be the number of times state $s$ has been visited, or $N(s, a)$ be the number of times action $a$ has been taken in state $s$ . A common form for the exploration bonus $r^+$ added to the extrinsic reward $r_e$ is based on the principle of "Optimism in the Face of Uncertainty":

r^+(s) = \frac{\beta}{\sqrt{N(s)}} \quad \text{or} \quad r^+(s, a) = \frac{\beta}{\sqrt{N(s, a)}}

Here, $\beta$ is a hyperparameter controlling the intensity of exploration. The total reward used for learning becomes $r = r_e + r^+(s)$ (or $r = r_e + r^+(s, a)$ ). As a state is visited more often, $N(s)$ increases, and the exploration bonus diminishes, causing the agent to eventually focus on exploiting the learned policy based on the actual rewards $r_e$ . Algorithms like MBIE-EB (Model-Based Interval Estimation with Exploration Bonus) formalize this idea.

The Challenge of Scale: Pseudo-Counts

Direct counting breaks down in large or continuous state spaces. Why? Because the agent might never visit the exact same high-dimensional state (like an image from a camera) twice. We need a way to generalize the notion of visitation counts to unseen but similar states. This leads to the concept of pseudo-counts.

Instead of exact counts, we use a density model $p(s)$ trained on the history of visited states. This model estimates the probability density around any given state $s$ .

If $s$ is in a region frequently visited before, $p(s)$ will be high.
If $s$ is in a novel region, $p(s)$ will be low.

The core idea is to derive a pseudo-count $N̂(s)$ from this density estimate $p(s)$ . A pseudo-count $N̂(s)$ approximates how many times states "similar" to $s$ have been visited.

How can we connect density $p(s)$ to a pseudo-count $N̂(s)$ ? Consider a sequence of states $s_1, s_2, ..., s_n$ . A density model trained on this sequence might learn $p(s)$ . Now, if we observe a new state $s_{n+1}$ , we can ask: what is the probability $p(s_{n+1})$ according to the model? This probability reflects how "familiar" the new state is.

A key insight comes from relating the probability assigned by the density model $p(s)$ to the probability assigned by simply recording and predicting states $p_{REC}(s)$ . It can be shown that under certain assumptions about the density model learning process, the prediction probability $p(s)$ relates to a pseudo-count $N̂(s)$ via:

p(s) \approx \frac{N̂(s) + \delta}{ \sum_{s'} (N̂(s') + \delta)}

where $\delta$ is a small smoothing constant. More practically relevant is the relationship derived from the increase in density upon observing $s$ again. Let $p_n(s)$ be the density estimate after $n$ observations, and $p_{n+1}(s)$ be the estimate after observing $s$ one more time. The pseudo-count $N̂(s)$ should satisfy:

p_{n+1}(s) - p_n(s) \propto \frac{1}{N̂(s)}

This means observing a state again increases its density more if its current pseudo-count is low. While calculating this difference directly is often complex, several density estimation methods allow us to approximate $N̂(s)$ or directly use $p(s)$ to define an exploration bonus.

The exploration bonus is then calculated similarly to the tabular case, but using the pseudo-count:

r^+(s) = \frac{\beta}{\sqrt{N̂(s)}}

This bonus encourages the agent to move towards states that the density model considers novel (low density, low pseudo-count).

Methods for Estimating Pseudo-Counts

Several techniques exist to implement density estimation for pseudo-counts in high-dimensional spaces:

Hashing-Based Methods: These methods use hash functions or learned feature embeddings $\phi(s)$ to map high-dimensional states $s$ to a lower-dimensional (often discrete) representation $z = \phi(s)$ . Counts $N(z)$ are then maintained in this compressed space.
- Example: Locality-Sensitive Hashing (LSH) can group similar states into the same buckets. Random projections can also create features.
- Pros: Computationally simpler than complex density models.
- Cons: Performance heavily depends on the quality of the hash function or features $\phi$ . Similar states might map to different buckets (low recall), or dissimilar states to the same bucket (low precision). Requires careful design of $\phi$ .
Generative Models: Deep generative models, trained on the stream of observed states $s_t$ , can naturally estimate density or novelty.
- Examples:
  - PixelCNN/PixelRNN: Autoregressive models that predict pixel values in an image conditioned on previous pixels. The likelihood $p(s)$ assigned to an image $s$ reflects how predictable (common) it is based on the model's learned distribution of training images. Lower likelihood implies higher novelty.
  - Variational Autoencoders (VAEs) or Generative Adversarial Networks (GANs): While not directly providing density $p(s)$ , reconstruction error (VAEs) or discriminator output (GANs) can sometimes be proxies for novelty, although this is less theoretically grounded for pseudo-counts.
- Deriving Bonus: The pseudo-count $N̂(s)$ can often be related to the model's likelihood $p(s)$ . For instance, some methods approximate $N̂(s)$ based on how much observing $s$ would improve the model's likelihood on $s$ . A simpler approach uses the likelihood directly: lower $p(s)$ leads to a higher bonus.
- Pros: Can capture complex structures in high-dimensional data like images. No need for manual feature engineering.
- Cons: Computationally expensive to train and query. Can be sensitive to hyperparameters. Might focus on statistically novel but irrelevant aspects of the state (e.g., background noise).
Context-Tree Switching (CTS) Models: These are powerful sequence models that can build adaptive density estimates for transitions $p(s' | s, a)$ . They have been used effectively for pseudo-count estimation in RL.

Integrating the Bonus

Regardless of how the pseudo-count $N̂(s)$ (or a proxy for novelty) is calculated, the exploration bonus $r^+ = \beta / \sqrt{N̂(s)}$ is typically added to the extrinsic reward $r_e$ received from the environment. The learning algorithm (e.g., DQN, PPO) then uses the combined reward $r = r_e + r^+$ to update its value functions or policies.

Flow diagram illustrating how pseudo-counts generate exploration bonuses within an RL loop. The state is fed into a density model, which yields a pseudo-count used to compute a bonus. This bonus modifies the reward signal used by the RL agent.

Considerations and Trade-offs

Computational Cost: Training and querying density models, especially deep generative models, can be significantly more computationally intensive than simpler exploration methods.
Model Choice: The effectiveness of pseudo-count exploration depends heavily on the chosen density model and its ability to capture relevant aspects of novelty in the state space. A poorly chosen model might lead to inefficient exploration.
High Dimensions: Density estimation inherently suffers from the "curse of dimensionality". While techniques like hashing or deep models aim to mitigate this, performance can still degrade in extremely high-dimensional spaces.
Detached Novelty: Sometimes, the density model might identify novelty unrelated to the actual task or potential rewards (e.g., random background variations in an image). This can lead the agent to explore unproductive parts of the state space. Combining count-based exploration with task-relevant information is an area of ongoing research.

Count-based exploration using pseudo-counts provides a principled and often effective way to drive exploration in complex environments. By formalizing the intuition of visiting less familiar states, these methods enable agents to systematically gather information and tackle challenging problems where random exploration fails. They represent a significant step beyond simple heuristics, pushing towards more intelligent exploration behavior.