Entropy of a Policy

1. Background Knowledge

Entropy measures the uncertainty or "surprise" of a probability distribution. For a discrete policy $\pi$ over a set of actions $\mathcal{A}$, the entropy is defined as:

$$H(\pi) = -\sum_{a \in \mathcal{A}} \pi(a) \log \pi(a)$$

A deterministic policy (one action has probability 1, others 0) has zero entropy, meaning no exploration is needed. A uniform policy over $n$ actions has maximum entropy $\log n$, representing maximal uncertainty. In policy gradient methods, adding an entropy bonus to the objective function encourages the agent to keep exploring rather than collapsing to a greedy policy too early.

The term $\pi(a) \log \pi(a)$ is well-behaved in the limit: as $\pi(a) \to 0^+$, the product $\pi(a) \log \pi(a) \to 0$. This is a standard result from calculus (L'Hôpital's rule or the fact that $x \log x \to 0$ as $x \to 0^+$). Therefore, actions with zero probability contribute nothing to the sum, and we should explicitly handle them to avoid computing $\log(0) = -\infty$.

In practice, policies are often represented as probability vectors (e.g., from a softmax output). The entropy is computed over this vector using the natural logarithm ($\ln$), not log base 2 or base 10.

2. Algorithm Approach

This is a straightforward element-wise computation over a probability vector:

1. Iterate over each action's probability $\pi(a)$.
2. If $\pi(a) > 0$, compute $\pi(a) \cdot \ln(\pi(a))$ and accumulate.
3. If $\pi(a) = 0$, skip (contribution is 0).
4. Return the negative of the accumulated sum.

The key insight is that the formula involves a sum of products, so you need a single pass over the vector with a running total. No sorting, no recursion, no data structures beyond a scalar accumulator.

3. Step-by-Step Strategy