Exploration II

Exploration with no reward at all

Monday’s lecture treated exploration conventionally: trade off exploration and exploitation, incentivize visits to novel or high-information-gain states. This lecture is “a different perspective on exploration which is quite distinct from the one on Monday and a little bit unusual” — a research-focused lecture, partly aimed at final-project ideas. The question: what if rewards aren’t delayed or sparse but absent altogether? Human children spend copious amounts of time playing — energy-intensive, presumably not random, with goals set, goals accomplished, and something useful distilled. The practical version: a home robot spends all day in your kitchen figuring out what it can do there, so that when you come home and say “do my dishes,” whatever it practiced lets it learn the commanded task very efficiently. If you can prepare for an unknown future goal, you can accomplish it quickly when it arrives. Exploration reframed: not seeking the states that have reward, but acquiring skills that can be repurposed later — a repertoire for new goals, sub-skills for hierarchical RL, a broad buffer of experience.

An information theory refresher

Entropy, $\mathcal{H}(p(\mathbf{x})) = -\mathbb{E}_{\mathbf{x} \sim p(\mathbf{x})}[\log p(\mathbf{x})]$, measures how broad a distribution is — uniform maximal, point mass minimal. The second tool is the one this lecture runs on:

Write $\pi(\mathbf{s})$ for the state marginal of policy $\pi$ (elsewhere $p_\theta(\mathbf{s})$); its entropy $\mathcal{H}(\pi(\mathbf{s}))$ quantifies coverage. Mutual information can encode surprisingly rich notions — the classic example, from Polani and colleagues, is empowerment: $\mathcal{I}(\mathbf{s}_{t+1}; \mathbf{a}_t) = \mathcal{H}(\mathbf{s}_{t+1}) - \mathcal{H}(\mathbf{s}_{t+1} \mid \mathbf{a}_t)$. Maximizing it wants many possible next states, yet predictable ones once you know your action. Stand in the middle of a room: many actions, each reliably leading somewhere different — both terms cooperate. At the bottom of a well the next state is predictable with or without the action (no options); in a chaotic environment the future is varied but out of your control. Only agents with many reliable options score well — “a notion of control authority in an information-theoretic way.”

Propose your own goals: Skew-Fit

The first algorithm attacks the kitchen robot head on. Goals are commanded as states — for images, a picture of the desired outcome. During the unsupervised phase the agent should imagine its own goals and attempt to reach them, training a goal-conditioned policy that can later reach whatever state you command. Since every image in a continuous space is unique, train a generative model — Levine’s working example is a variational autoencoder, covered a few weeks from now — whose latent codes $\mathbf{z}$ put functionally similar states close together.

The catch: the model proposes goals that look like the data it was trained on. If the agent learns to pick up one mug, it drowns in mug data and proposes yet more mug goals. The fix imports Monday’s novelty-seeking into step 4: skew the data toward rarely seen states before fitting. Replace maximum likelihood with weighted maximum likelihood, letting the model itself score rarity:

$\psi \leftarrow \arg\max_\psi \; \mathbb{E}\big[w(\bar{\mathbf{x}}) \log p_\psi(\bar{\mathbf{x}})\big], \qquad w(\bar{\mathbf{x}}) = p_\theta(\bar{\mathbf{x}})^\alpha, \quad \alpha < 0$

What objective does the whole procedure optimize? Skewing maximizes $\mathcal{H}(p(G))$ — goal coverage. The RL part makes the final state $S$ predict the commanded goal ever better: a good policy’s goal “was probably the thing that it actually reached,” so $\mathcal{H}(p(G \mid S))$ shrinks. Together that maximizes $\mathcal{H}(p(G)) - \mathcal{H}(p(G \mid S)) = \mathcal{I}(S; G)$.

In the real-robot experiment, a robot was parked at a door without being told the door mattered. At zero hours it wiggles in place; at 10 hours it touches the handle and occasionally opens it; at 25 hours it reliably opens the door to all different angles — and once trained, show it an image of the door at some angle and it matches it.

Matching a state distribution

Run Monday-style intrinsic motivation with no reward at all — bonus $\tilde{r}(\mathbf{s}) = -\log p_\pi(\mathbf{s})$, or pseudo-counts, EX2, hash exploration — alternating policy updates with density refits. The density estimator eventually covers everything, but the policy ends up arbitrary: each iterate flees wherever the previous density was high, “chasing its tail all around the space.”

What we want is state marginal matching: learn $\pi(\mathbf{a} \mid \mathbf{s})$ minimizing $D_{KL}(p_\pi(\mathbf{s}) \,\|\, p^\star(\mathbf{s}))$ — with uniform $p^\star$, pure state-entropy maximization. Set $\tilde{r}(\mathbf{s}) = \log p^\star(\mathbf{s}) - \log p_\pi(\mathbf{s})$ and notice something curious: $\mathbb{E}_{p_\pi(\mathbf{s})}[\tilde{r}(\mathbf{s})]$ is exactly the negative KL we want. Yet RL on $\tilde{r}$ doesn’t perform marginal matching, for a subtle reason: the algorithm isn’t aware the reward itself depends on $\pi$, so it plays the greedy tail-chasing game. The fix:

Empirically, in a three-winged ant maze, standard SAC gravitates toward one wing; state marginal matching covers all three about equally.

But is coverage of valid states even a good objective? Levine’s half-joking “Eisenbach’s theorem” (after Ben Eysenbach, who wrote it down — really a trivial consequence of classical maximum-entropy modeling) says yes: suppose at test time an adversary picks the worst possible goal — you bought the robot intending to watch it fail and leave a one-star review. If the goal will be adversarial, the best training distribution over goals is exactly uniform. Absent any knowledge of the test-time task, maximizing the entropy of goals or states makes the worst case as good as possible — the principled justification for the uniform-coverage business.

Beyond states: covering the space of skills

Finally, generalize goals to skills: a policy $\pi(\mathbf{a} \mid \mathbf{s}, z)$ conditioned on a task index $z$ (separate per-skill policies are a special case). Reaching diverse goals is not the same as performing diverse tasks: “reach the green ball while avoiding the red circle” is no goal-reaching behavior, since no commanded final state encodes the avoidance. The space of skills is larger than the space of goal-reaching behaviors, and the intuition is that different skills should visit different state-space regions, not just different individual states.

The recipe (Diversity Is All You Need; also Variational Intrinsic Control) rewards states under skill $z$ that are unlikely for other skills $z' \neq z$. Operationally, train a classifier — a discriminator — to guess the skill from the state, and use it as the reward:

$\pi(\mathbf{a} \mid \mathbf{s}, z) = \arg\max_\pi \sum_z \mathbb{E}_{\mathbf{s} \sim \pi(\mathbf{s} \mid z)}\big[r(\mathbf{s}, z)\big], \qquad r(\mathbf{s}, z) = \log p_D(z \mid \mathbf{s})$

Each iteration the discriminator classifies better and the policy becomes easier to classify. Picture two initially random skills, green and blue, that by chance visit slightly different states: the classifier draws a decision boundary, RL against that reward pushes the skills apart, the boundary sharpens, and so on — with dozens or hundreds of skills, they tile the space. On the HW1 cheetah this discovers running forward, running backward, and “a cool flip” — each skill guessable from a still frame, which is exactly the objective. On mountain car, some skills simply solve the task.

Once more the recipe is mutual information in disguise: $\mathcal{I}(z; \mathbf{s}) = \mathcal{H}(z) - \mathcal{H}(z \mid \mathbf{s})$. A uniform prior over skills maximizes the first term for free; maximizing $\log p(z \mid \mathbf{s})$ — precisely what the discriminator-reward loop does — minimizes the second. The whole algorithm maximizes $\mathcal{I}(z; \mathbf{s})$.

Check yourself

Conceptual and derivation exercises in the lecture’s spirit — work them on paper.

Problem 14.1 mutual information identity

Starting from $\mathcal{I}(\mathbf{x};\mathbf{y}) = \mathbb{E}_{p(\mathbf{x},\mathbf{y})}\left[\log \frac{p(\mathbf{x},\mathbf{y})}{p(\mathbf{x})p(\mathbf{y})}\right]$, derive the difference-of-entropies form $\mathcal{I}(\mathbf{x};\mathbf{y}) = \mathcal{H}(p(\mathbf{y})) - \mathcal{H}(p(\mathbf{y} \mid \mathbf{x}))$, and explain in one sentence why this justifies reading mutual information as information gain.

Show solution

Factor the joint as $p(\mathbf{x},\mathbf{y}) = p(\mathbf{x})\,p(\mathbf{y} \mid \mathbf{x})$ inside the log: $\log \frac{p(\mathbf{x})p(\mathbf{y} \mid \mathbf{x})}{p(\mathbf{x})p(\mathbf{y})} = \log p(\mathbf{y} \mid \mathbf{x}) - \log p(\mathbf{y})$. Take the expectation under $p(\mathbf{x},\mathbf{y})$: $\mathbb{E}[-\log p(\mathbf{y})] = \mathcal{H}(p(\mathbf{y}))$ (the argument doesn’t involve $\mathbf{x}$, so marginalizing over $\mathbf{x}$ is harmless), and $\mathbb{E}[\log p(\mathbf{y} \mid \mathbf{x})] = -\mathcal{H}(p(\mathbf{y} \mid \mathbf{x}))$, the expected conditional entropy. Hence $\mathcal{I} = \mathcal{H}(p(\mathbf{y})) - \mathcal{H}(p(\mathbf{y} \mid \mathbf{x}))$: the expected reduction in the entropy of $\mathbf{y}$ from observing $\mathbf{x}$ — exactly “how much did I learn about $\mathbf{y}$,” i.e. information gain, and by symmetry the same holds with the roles swapped.

Problem 14.2 empowerment calculation

An agent picks one of 4 actions uniformly at random. Compute the empowerment $\mathcal{I}(\mathbf{s}_{t+1}; \mathbf{a}_t)$ in bits for three environments: (a) each action deterministically leads to a distinct one of 4 next states; (b) the “bottom of a well” — every action leads to the same next state; (c) a chaotic room — regardless of action, the next state is uniform over 4 states. Which situation does an empowerment maximizer seek, and why do (b) and (c) fail for different reasons?

Show solution

(a) The next-state marginal is uniform over 4 states, so $\mathcal{H}(\mathbf{s}_{t+1}) = 2$ bits; given the action the next state is deterministic, $\mathcal{H}(\mathbf{s}_{t+1} \mid \mathbf{a}_t) = 0$; empowerment $= 2$ bits. (b) Both entropies are $0$: empowerment $= 0$ — the conditional term is minimal, but there are no options. (c) Both entropies are $2$ bits (knowing the action doesn’t help): empowerment $= 0$ — plenty of variety, none of it under the agent’s control. The maximizer seeks (a): many actions leading reliably to many different states — the middle of the room, not the well and not the chaos.

Problem 14.3 Skew-Fit weighting

Your generative model assigns density $p_\theta = 0.64$ to a frequently reached state and $p_\theta = 0.01$ to a rare one. (a) Compute the Skew-Fit weights $w = p_\theta^\alpha$ for $\alpha = -\tfrac{1}{2}$ and the rare-to-frequent weight ratio. (b) Connect the weighting to count-based exploration bonuses. (c) Why does the procedure converge to uniform over valid states rather than over all images, and why is that the right target?

Show solution

(a) Frequent: $w = 0.64^{-1/2} = 1/0.8 = 1.25$. Rare: $w = 0.01^{-1/2} = 10$ — an $8\times$ upweighting of the rare state, so the refit model shifts mass toward the tails and proposes broader goals. (b) Count-based bonuses take the form $n(\mathbf{s})$ raised to a negative power ($n^{-1/2}$, $n^{-1}$); Skew-Fit uses the model’s own density raised to a negative power in the same role — except as a training weight for the goal proposer instead of a reward. (c) Weighted MLE can only redistribute mass over states that appear in the data — states the agent actually reached — so the entropy-increasing dynamics drive $p_\theta$ toward uniform over reachable, valid states. Uniform over all pixel arrays would put mass on static-like non-states that make useless, unreachable goals; uniform over valid states is maximal coverage of what the agent could actually be asked to do.

Problem 14.4 tail-chasing vs. mixture

With no extrinsic reward, consider iterating: (i) train $\pi^k$ to maximize $\tilde{r}^k(\mathbf{s}) = \log p^\star(\mathbf{s}) - \log p_{\pi}(\mathbf{s})$, (ii) refit the density. The RL objective $\mathbb{E}_{p_\pi(\mathbf{s})}[\tilde{r}(\mathbf{s})]$ equals the negative KL divergence we want to minimize — so why doesn’t running RL on $\tilde{r}$ solve state marginal matching, and what two changes fix the procedure?

Show solution

RL treats the reward as fixed: it is not aware that $-\log p_\pi(\mathbf{s})$ depends on the policy being optimized. Each iterate greedily flees wherever the previous density estimate was high, so the density estimator ends up with good coverage but the final policy is arbitrary. Fixes: (1) fit the density to all states seen so far (the whole replay buffer), not just the latest policy’s; (2) return the uniform mixture of iterates $\pi^1, \ldots, \pi^K$ — run a randomly chosen iterate — rather than the last one. The matching distribution is the Nash equilibrium of a two-player game between policy and density estimator; iterated best response doesn’t reach a Nash equilibrium, but self-play — the historical average of iterates — provably does, so the mixture minimizes $D_{KL}(p_\pi \| p^\star)$ even though no individual iterate does.

Problem 14.5 skills beyond goals

(a) State the DIAYN reward and show which term of $\mathcal{I}(z; \mathbf{s}) = \mathcal{H}(z) - \mathcal{H}(z \mid \mathbf{s})$ each design choice handles. (b) Using the lecture’s example, explain why a perfect goal-conditioned policy — able to reach any state — still cannot represent every skill DIAYN could learn.

Show solution

(a) $r(\mathbf{s}, z) = \log p_D(z \mid \mathbf{s})$ with $z$ drawn from a uniform prior. The uniform prior maximizes $\mathcal{H}(z)$ outright: with $n$ skills equally likely, the first term sits at its maximum $\log n$. Jointly improving the discriminator and rewarding the policy for being classifiable maximizes $\mathbb{E}[\log p(z \mid \mathbf{s})]$, minimizing $\mathcal{H}(z \mid \mathbf{s})$ — so the loop maximizes $\mathcal{I}(z; \mathbf{s})$. (b) Consider “reach the green ball while avoiding the red circle.” A goal-conditioned policy is commanded only by a target state; “green ball” says nothing about the path, so no goal encodes the avoidance constraint. Skills are defined by the state-space regions they visit — whole trajectories — so the space of skills strictly contains the space of goal-reaching behaviors, which is why skill discovery goes beyond state coverage.