Exploration I

Why some games are nearly impossible

The lecture opens with a puzzle from homework 3: the same Q-learning implementation that plays Pong and Breakout well makes essentially no progress on Montezuma’s Revenge — even though, for a human, “getting that trick shot in Breakout where it bounces around up top is probably harder actually than playing Montezuma’s Revenge.” The game gives reward for getting the key and for opening the door; getting killed by the skull does nothing. So an agent might learn that a great way to keep collecting reward is to keep dying to the skull and picking up the key again. The core diagnosis: “finishing the game only weakly correlates with rewarding events.” We know what to do because we understand what the sprites mean; the algorithm has to discover it all by trial and error.

To feel what that’s like, Levine offers the card game Mao, where “the only rule you may be told is this one”: you incur penalties for breaking rules you were never told, and you discover them only through trial and error. Temporally extended tasks get harder with how extended they are and how little you know about the rules — now imagine your goal in life were to win 50 games of Mao. A robotic hand asked to pick up a ball is the continuous-control version of the same problem: it doesn’t know that “picking up objects is actually a thing”; it can only wiggle its fingers, and the reward is too delayed to signal a grasp.

Can we derive an optimal exploration strategy? Only if we can say what optimal means, and Levine’s yardstick is regret against a Bayes-optimal agent — a hypothetical perfect Bayesian that maintains uncertainty about how the world works and resolves it optimally. Problem settings sit on a spectrum from theoretically tractable to intractable: multi-armed bandits (one-step, stateless RL problems), contextual bandits (one step, with a state actions don’t affect), small finite MDPs, and finally the large or infinite MDPs deep RL cares about, where “there isn’t much that we can say theoretically.” Hence the lecture’s plan: principled algorithms in the bandit setting, adapted by analogy to big MDPs, plus “lots of hacks as we always do in deep reinforcement learning.”

Bandits, and what optimal exploration even means

The multi-armed bandit — “the drosophila of exploration problems” — is a bank of slot machines: pull one of $n$ arms, receive a stochastic reward from that arm’s unknown distribution. Model the reward of action $a_i$ as $r(a_i) \sim p_{\theta_i}(r_i)$ — for binary rewards, $p(r_i = 1) = \theta_i$ and $p(r_i = 0) = 1 - \theta_i$ — with a prior $\theta_i \sim p(\theta)$.

Here is the conceptual move that anchors everything after it: this defines a POMDP whose hidden state is $\mathbf{s} = [\theta_1, \ldots, \theta_n]$. Pulling an arm doesn’t change the world, but it changes what you know — your belief $\hat{p}(\theta_1, \ldots, \theta_n)$ — and solving that POMDP yields the optimal exploration strategy. It’s also overkill: the belief state is a full distribution over $\theta$, huge even for binary rewards. The good news is that much simpler strategies do very well, and we measure “well” by regret:

$\text{Reg}(T) = T\, \mathbb{E}[r(a^\star)] - \sum_{t=1}^{T} r(a_t)$

the gap between what the optimal policy (always pull $a^\star$) earns in expectation over $T$ steps and the reward your strategy actually collected.

Three provably good bandit strategies

Optimistic exploration. Pure exploitation keeps track of the average reward $\hat{\mu}_a$ per action and picks $a = \arg\max \hat{\mu}_a$. Optimism instead picks $a = \arg\max \hat{\mu}_a + C\sigma_a$, where $\sigma_a$ is some uncertainty estimate: “try each arm until you’re sure that it’s not great.” A remarkably simple instantiation (Auer et al.) needs nothing but counts:

Posterior sampling (Thompson sampling). Where optimism is model-free — it counts, it doesn’t model uncertainty — Thompson sampling maintains an approximate belief $\hat{p}(\theta_1, \ldots, \theta_n)$ over bandit models, samples one $\theta$ vector, acts optimally as if that sample were the truth, then updates the belief and repeats. Either the sample was right and you got the reward you expected, or you just collected a counterexample and won’t sample that model again. It acts greedily on a sample rather than reasoning about what it will learn — much easier than solving the POMDP, harder to analyze, often excellent empirically (Chapelle and Li, “An Empirical Evaluation of Thompson Sampling”).

Information gain. The most explicitly model-based option, from Bayesian experiment design: to learn about a latent quantity $z$ from an observation $y$, define

$\text{IG}(z, y) = \mathbb{E}_y\!\left[\mathcal{H}(\hat{p}(z)) - \mathcal{H}(\hat{p}(z) \mid y)\right]$

— the expected drop in entropy of your $z$-estimate after observing $y$, conditioned on the action when needed. Russo and Van Roy (“Learning to Optimize via Information-Directed Sampling”) take $y$ to be the observed reward $r_a$ and $z$ to be $\theta_a$, define $g(a)$ as the information gain of action $a$ and $\Delta(a)$ as its expected suboptimality, and choose

$a = \arg\min_a\, \frac{\Delta(a)^2}{g(a)}$

Don’t take actions you know won’t teach you anything (small $g(a)$ blows the ratio up), and don’t take actions you’re sure are bad (large $\Delta(a)$ does too).

From counts to pseudo-counts in deep RL

The UCB recipe ports directly to MDPs as count-based exploration: count visits $N(\mathbf{s})$ (or $N(\mathbf{s}, \mathbf{a})$) and hand any RL algorithm the modified reward

$r^+(\mathbf{s}, \mathbf{a}) = r(\mathbf{s}, \mathbf{a}) + \mathcal{B}(N(\mathbf{s}))$

with $\mathcal{B}$ any bonus decreasing in $N(\mathbf{s})$. It’s modular — but you must tune the bonus weight, and there’s a deeper problem: what’s a count? If the skull moves while your avatar moves, every configuration is a fresh state; in continuous spaces “no two states are going to be the same.” In big problems we never see the same thing twice, which makes literal counting useless — but some states are more similar than others, and a density model can exploit that. Fit $p_\theta(\mathbf{s})$; a well-generalizing model assigns high density to a never-seen state that resembles familiar ones (guy in a known spot, skull in a known spot, just never together) and low density to something genuinely new, like the key suddenly missing.

The trick, from Bellemare et al.’s “Unifying Count-Based Exploration,” is to notice that in a small MDP true counts and probabilities are locked together: $P(\mathbf{s}) = N(\mathbf{s})/n$, and after one more visit $P'(\mathbf{s}) = (N(\mathbf{s})+1)/(n+1)$. So demand that your density model behave the same way.

For the bonus, the literature offers $\mathcal{B}(N(\mathbf{s})) = \sqrt{2 \ln n / N(\mathbf{s})}$ (UCB), $\sqrt{1/N(\mathbf{s})}$ (MBIE-EB, Strehl and Littman — the one Bellemare et al. use), and $1/N(\mathbf{s})$ (BEB, Kolter and Ng); “they’re all pretty good.” Empirically, against DQN the $1/\sqrt{n}$-bonus agent barely matters on games like H.E.R.O., but on Montezuma’s Revenge it’s the difference between visiting two rooms of the pyramid and more than half of it, with almost no progress at all without the bonus.

What density model? The requirements are peculiar: you need densities out, you never need samples — “often the opposite of the considerations for many popular generative models in the literature like GANs,” which produce great samples but no densities. Bellemare et al. use a simple CTS model that conditions each pixel on its top-left neighbors: not a good density model, but it produces the scores.

Other ways to score novelty

Counting with hashes (Tang et al.): keep literal counts, but over a compressed representation. Encode $\mathbf{s}$ into a short $k$-bit code $\phi(\mathbf{s})$; with more states than $2^k$ codes, collisions are forced, and the code length sets how broad your notion of “similar” is. Training the encoder as an autoencoder makes collisions similarity-driven — mistaking one state for another costs little reconstruction error only when they look alike.

Classifier-based densities (EX2, Fu et al.): skip density modeling entirely. For each new state, train a classifier $D_{\mathbf{s}}$ to distinguish that state (the lone positive) from all past states in the buffer (the negatives); if the classifier separates them easily, the state is novel. This is exact, not just intuitive: the Bayes-optimal classifier satisfies $D_{\mathbf{s}}(\mathbf{s}) = 1/(1 + p(\mathbf{s}))$, which rearranges to

$p_\theta(\mathbf{s}) = \frac{1 - D_{\mathbf{s}}(\mathbf{s})}{D_{\mathbf{s}}(\mathbf{s})}$

Isn’t the classifier just checking whether $\mathbf{s}$ equals itself? No — if copies of $\mathbf{s}$ also appear among the negatives, the optimal $D_{\mathbf{s}}(\mathbf{s})$ is below 1, and in continuous spaces a regularized classifier generalizes across near-duplicates instead of memorizing. One amortized network conditioned on the exemplar replaces the classifier-per-state.

Errors against a target function. Loosen the requirements once more: the score doesn’t even need to be a density — “you just need to be able to tell if a state is novel or not.” Pick any target $f^\star(\mathbf{s}, \mathbf{a})$, fit $\hat{f}_\theta$ to it on your buffer, and use

$\mathcal{E}(\mathbf{s}, \mathbf{a}) = \|\hat{f}_\theta(\mathbf{s}, \mathbf{a}) - f^\star(\mathbf{s}, \mathbf{a})\|^2$

as the bonus: small near the data, large far from it. Common choice: $f^\star(\mathbf{s}, \mathbf{a}) = \mathbf{s}'$, next-state prediction. Even simpler: $f^\star = f_\phi$ with $\phi$ a random, untrained parameter vector — the target needn’t be meaningful, just nontrivial to fit (random network distillation, which appears on homework 5, “so it’s a good idea to kind of understand why this works”).

Posterior sampling with Q-functions

What’s the deep-RL analog of sampling a bandit model? In a bandit, the reward model is all you need to act; in an MDP, that role belongs to the Q-function. So: sample a Q-function from a distribution over Q-functions, act greedily with respect to it for a whole episode, update the distribution, repeat. Since Q-learning is off-policy, every rollout — whichever sample collected it — trains the whole ensemble.

Represent the distribution with bootstrap ensembles, as in the model-based lectures: resample the dataset $N$ times, train a Q-network on each, sample one at random per episode. In practice (Osband et al., “Deep Exploration via Bootstrapped DQN”) you skip the resampling and share one trunk with multiple heads — multiple copies of the last layer — accepting correlated heads as the price of cheapness: “not a great way to estimate a very accurate posterior but it might be good enough.”

Bootstrapped exploration helps a fair bit on some games and not at all on others — not on Montezuma’s Revenge — and generally loses to good count-based bonuses. Its virtues are that it never modifies the reward and has no exploration hyperparameters to tune; at convergence every head should be a fine Q-function.

Information gain in deep RL

Information gain about what? Gaining information about the reward is useless when reward is sparse — it’s zero almost everywhere. Information gain about the state density $p(\mathbf{s})$ “sounds a bit strange but actually somewhat makes sense”: changing the density means doing novel things. The most reasonable choice is the dynamics $p(\mathbf{s}' \mid \mathbf{s}, \mathbf{a})$: with sparse reward and an easy initial state, the dynamics are the one part of the MDP that’s both unknown and informative — a good proxy for learning the MDP, “though it’s still a heuristic.”

Exact information gain is intractable in large spaces, so everything hinges on the approximation. The cheapest is prediction gain, $\log p_{\theta'}(\mathbf{s}) - \log p_\theta(\mathbf{s})$: if updating the density model on a state changes its log-probability a lot, the state was novel — pseudo-counts-adjacent, without the counts.

The principled version is variational (VIME). Information gain equals a KL divergence, $\text{IG} = D_{KL}(p(z \mid y)\, \|\, p(z))$: you learned a lot from $y$ exactly when your posterior moved. Take $z = \theta$, the dynamics-model parameters, and $y$ a transition $(\mathbf{s}_t, \mathbf{a}_t, \mathbf{s}_{t+1})$; the transitions worth seeking maximize

$D_{KL}\big(p(\theta \mid h, \mathbf{s}_t, \mathbf{a}_t, \mathbf{s}_{t+1})\, \big\|\, p(\theta \mid h)\big)$

where $h$ is the history (the replay buffer). True parameter posteriors are intractable, so approximate $p(\theta \mid h)$ with a variational $q(\theta \mid \phi)$ — an independent Gaussian per weight, as in Bayes-by-backprop — trained on the usual variational lower bound. On each new transition, update $\phi \to \phi'$ and use the closed-form Gaussian KL $D_{KL}(q(\theta \mid \phi')\, \|\, q(\theta \mid \phi))$ — intuitively, how far the means moved — as the bonus added to $r^+$. It works across a range of tasks and has “a very appealing mathematical formalism”; the downside is training entire dynamics models just to get bonuses, so “if you can estimate densities maybe it’s easier to use something like pseudo counts.” Drop the Bayesian framing and just measure how much some parameter vector changes — model error on autoencoded latents, model gradients, other variants back to Schmidhuber — and you recover the error-based family from before.

Check yourself

Bandit arithmetic and deep-exploration reasoning, in the lecture’s spirit — work them on paper.

Problem 13.1 regret accounting

A two-armed bandit has true expected rewards $\mu_1 = 0.9$ and $\mu_2 = 0.5$. Strategy A alternates arms forever. Strategy B pulls arm 2 for the first 10 steps, then arm 1 forever. Compute the expected regret $\text{Reg}(T)$ of each strategy at $T = 100$ and as $T \to \infty$ (as a function of $T$). Which is consistent with “optimal” exploration in the big-O sense, and why is $O(\log T)$ the benchmark?

Show solution

The optimal policy always pulls arm 1, earning $0.9T$ in expectation. Strategy A earns $\tfrac{T}{2}(0.9 + 0.5) = 0.7T$, so $\text{Reg}(T) = 0.2T$ — at $T = 100$, regret 20, and $O(T)$ asymptotically: linear regret means you never stop paying for exploration. Strategy B loses $0.4$ per step for 10 steps and nothing thereafter: $\text{Reg}(100) = 4$, and $\text{Reg}(T) = 4$ for all $T \ge 10$ — constant, hence better than $O(\log T)$ (a real algorithm can’t do this reliably; B just got handed the right answer after its trial period, with no guarantee 10 pulls suffice to identify the best arm). The point of the comparison: good exploration strategies must have regret that grows sublinearly, and $O(\log T)$ — achieved by UCB with the $\sqrt{2\ln T / N(a)}$ bonus — is asymptotically the best achievable by any algorithm that must actually learn which arm is best, matching the big-O regret of solving the belief POMDP exactly.

Problem 13.2 pseudo-count arithmetic

Your density model assigns a state $p_\theta(\mathbf{s}) = 0.01$; after updating on one more visit to $\mathbf{s}$, the new model gives $p_{\theta'}(\mathbf{s}) = 0.012$. Compute $\hat{n}$ and the pseudo-count $\hat{N}(\mathbf{s})$, then the MBIE-EB bonus $\sqrt{1/\hat{N}(\mathbf{s})}$. What happens to $\hat{N}$ as $p_{\theta'} \to p_\theta$, and why is that the right behavior?

Show solution

Solving the system $p_\theta = \hat{N}/\hat{n}$, $p_{\theta'} = (\hat{N}+1)/(\hat{n}+1)$ gives $\hat{n} = \dfrac{1 - p_{\theta'}}{p_{\theta'} - p_\theta} = \dfrac{1 - 0.012}{0.012 - 0.01} = \dfrac{0.988}{0.002} = 494$, so $\hat{N}(\mathbf{s}) = \hat{n}\, p_\theta(\mathbf{s}) = 494 \times 0.01 = 4.94$ — the state has effectively been seen about five times. Verify against the defining equations: $\hat{N}/\hat{n} = 4.94/494 = 0.01$ and $(\hat{N}+1)/(\hat{n}+1) = 5.94/495 = 0.012$, both correct. The bonus is $\sqrt{1/\hat{N}} = \sqrt{1/4.94} \approx 0.45$ — moderate, befitting a somewhat-familiar state. As $p_{\theta'} \to p_\theta$, the denominator $p_{\theta'} - p_\theta \to 0$ and $\hat{n}, \hat{N} \to \infty$: if seeing the state again doesn’t change the model at all, the model has already fully absorbed it — an infinitely familiar state deserves zero bonus, which is exactly what a huge pseudo-count delivers. Conversely, a big density jump on update means the state was novel, yielding a small $\hat{N}$ and a large bonus.

Problem 13.3 EX2 classifier density

In the EX2 scheme, suppose the buffer of negatives contains exactly three copies of the query state $\mathbf{s}$ out of nine negatives total, and the classifier trained with $\mathbf{s}$ as the single positive is Bayes-optimal. What probability $D_{\mathbf{s}}(\mathbf{s})$ does it assign, and what density does the formula $p_\theta(\mathbf{s}) = (1 - D_{\mathbf{s}}(\mathbf{s}))/D_{\mathbf{s}}(\mathbf{s})$ recover? Explain why the answer is not $D_{\mathbf{s}}(\mathbf{s}) = 1$, and what role regularization plays in continuous spaces.

Show solution

When the classifier is shown the input $\mathbf{s}$, that input could be the positive (1 way, weight one positive example) or any of the three matching negatives. Treating positive and negative sets as equally weighted classes, the positive class places all its mass (1) on $\mathbf{s}$ while the negative class places $3/9 = 1/3$ of its mass on $\mathbf{s}$; the optimal classifier outputs $D_{\mathbf{s}}(\mathbf{s}) = \frac{1}{1 + 1/3} = 3/4$. The recovered density is $p_\theta(\mathbf{s}) = (1 - 3/4)/(3/4) = 1/3$ — exactly the empirical frequency of $\mathbf{s}$ among past states, consistent with the general identity $D_{\mathbf{s}}(\mathbf{s}) = 1/(1 + p(\mathbf{s}))$. The output isn’t 1 because “is this the positive?” is genuinely ambiguous when identical copies live among the negatives: the classifier can’t do better than the ratio of class masses at that point. In continuous spaces every state is unique, so an unregularized classifier would output 1 everywhere and declare everything maximally novel; weight decay forces it to generalize across similar states, so near-duplicates in the negatives pull $D_{\mathbf{s}}(\mathbf{s})$ below 1 and the recovered density behaves like a smoothed count.

Problem 13.4 coherent vs. dithering exploration

A corridor MDP has states $1, \ldots, n$ in a line; the agent starts at state 1, actions are left/right, and the only reward is at state $n$. (a) Under uniform random exploration, how does the expected time to first reach state $n$ scale with $n$, and why is this the Seaquest surfacing problem? (b) Explain why an ensemble of randomly sampled Q-functions, each followed greedily for a whole episode, can reach state $n$ in time linear in $n$ with constant probability per episode. (c) Give the two practical advantages Levine cites for bootstrapped exploration despite bonuses usually working better.

Show solution

(a) Uniform random actions perform an unbiased random walk; reaching a point $n$ steps away takes $O(n^2)$ expected steps for an unbiased walk, and if the environment (like Seaquest’s mechanics, which make going deeper slightly easier) biases the walk away from the goal, the expected time becomes exponential in $n$ — the “exponentially unlikely to resurface” failure: coherent multi-step commitment (push up many times in a row) has vanishing probability under per-step dithering. (b) A randomly sampled Q-function induces some greedy policy that is internally consistent for the whole episode. Among sampled Q-functions, some assign higher value to moving right; such a sample walks right every step and covers the corridor in exactly $n - 1$ steps. If each head has some constant probability $p$ of preferring right, each episode succeeds with probability about $p$, so the expected number of episodes is $1/p$ — no exponential dependence on $n$. The exploration is random across episodes but coherent within them, which is the entire point. (c) It requires no change to the original reward function — at convergence all heads should be good Q-functions — and there are no exploration hyperparameters to tune (no bonus weight), making it a simple, unintrusive addition; nevertheless “very good bonuses often do quite a bit better,” which is why it’s not the method of choice for genuinely hard exploration problems.

Problem 13.5 choosing the info-gain target

You’re designing a VIME-style exploration bonus for a sparse-reward manipulation task. (a) Why is information gain about the reward function a poor target, and why are the dynamics the natural choice? (b) Write the exact quantity VIME wants to maximize and the two approximations that make it tractable. (c) Contrast the resulting bonus with prediction gain — what does each measure, and which is closer to the pseudo-count method?

Show solution

(a) With sparse reward, the reward is zero almost everywhere, so observing it carries almost no information — the posterior over reward parameters barely moves, and the bonus would be flat exactly where exploration is needed. The MDP is determined by initial state, dynamics, and reward; the initial state is easy to learn and the reward is uninformative, so the dynamics $p(\mathbf{s}' \mid \mathbf{s}, \mathbf{a})$ are “the one thing that varies quite frequently and provides a useful signal” — a good, if heuristic, proxy for learning the MDP. (b) The exact target is the KL form of information gain over dynamics parameters: maximize $D_{KL}(p(\theta \mid h, \mathbf{s}_t, \mathbf{a}_t, \mathbf{s}_{t+1}) \| p(\theta \mid h))$. Approximation one: replace the intractable parameter posterior with a variational $q(\theta \mid \phi)$ — independent Gaussians per weight, trained on the variational lower bound (Bayes-by-backprop). Approximation two: on each new transition, update $\phi \to \phi'$ and use the closed-form Gaussian KL $D_{KL}(q(\theta \mid \phi') \| q(\theta \mid \phi))$ as the per-transition bonus added to the reward. (c) The VIME bonus measures how much your belief over dynamics models shifted; prediction gain $\log p_{\theta'}(\mathbf{s}) - \log p_\theta(\mathbf{s})$ measures how much a state-density model’s log-probability of the new state rose after updating on it. Prediction gain is the one closer to pseudo-counts: it uses the same before/after density-model pair as Bellemare et al.’s method and targets information about the state density (i.e., novelty), just without solving for an explicit $\hat{N}(\mathbf{s})$.