Make the best choice with what you know now (exploitation), or take a loss to find out whether a better option exists (exploration)? It is the most fundamental conflict in online decision-making. In this lecture Silver ties the seemingly disparate exploration strategies into five principles: naive exploration, optimistic initialisation, optimism in the face of uncertainty, probability matching, and information-state search. Every later section hangs somewhere on these five.

Lecture slides: PDF

Exploration vs. exploitation

Exploitation is making the best decision given what you know; exploration is gathering more information. The key point is that making the best long-term decision may require a short-term sacrifice. You have to take a small loss now and gather enough information so that you can make the best choice over the whole journey.

Silver’s examples build the intuition. In choosing a restaurant, exploitation is going to your usual favourite while exploration is trying a new place. In banner advertising, exploitation is showing the ad that has worked best while exploration is testing a different one. In oil drilling, exploitation is drilling the best-known spot so far while exploration is sinking a new hole. In Go, exploitation is playing the move you believe is best while exploration is throwing out an experimental one. They are all the same tension: how to split your time between the present best and the unknown possibility.

The five principles

This is the backbone of the lecture. Silver organises the exploration methods into the following five principles.

  • Naive exploration: add noise to the greedy policy. $\epsilon$-greedy is the representative.
  • Optimistic initialisation: assume every option is the best until proven otherwise.
  • Optimism in the face of uncertainty: prefer actions whose value is uncertain.
  • Probability matching: pick each action in proportion to the probability that it is optimal.
  • Information-state search: fold the value of information into the calculation and plan ahead.

Below we first set these principles up on the simplest stage, the multi-armed bandit, and then lift them to contextual bandits and MDPs.

The multi-armed bandit

A multi-armed bandit is a tuple $\langle \mathcal{A}, \mathcal{R} \rangle$. $\mathcal{A}$ is a known set of $m$ actions (arms), and $\mathcal{R}^a(r) = \mathbb{P}[r \mid a]$ is an unknown reward distribution. At each step $t$ the agent pulls arm $a_t$ and the environment returns a reward $r_t \sim \mathcal{R}^{a_t}$. The goal is to maximise the cumulative reward $\sum_{\tau=1}^t r_\tau$. There is no state and no transition: all that is left is the question of which arm is good, a pure laboratory for exploration and exploitation.

Regret

The natural yardstick for performance is regret. The value of an action is the mean reward of that arm, $Q(a) = \mathbb{E}[r \mid a]$, and the optimal value is

$$V^* = Q(a^*) = \max_{a \in \mathcal{A}} Q(a)$$

The regret of one step is the opportunity cost of pulling some other arm instead of the optimal one.

$$l_t = \mathbb{E}[V^* - Q(a_t)]$$

The total regret is the sum of all of these.

$$L_t = \mathbb{E}\Big[\sum_{\tau=1}^t V^* - Q(a_\tau)\Big]$$

Maximising cumulative reward is the same as minimising total regret. From here on we take the view of reducing regret.

Counting the regret

Breaking the regret down a little more reveals what the problem is. Let $N_t(a)$ be the expected number of times arm $a$ is pulled up to step $t$, and let the gap $\Delta_a = V^* - Q(a)$ be the difference in value between the optimal arm and arm $a$. Then the regret splits cleanly into a function of gaps and counts.

$$L_t = \mathbb{E}\Big[\sum_{\tau=1}^t V^* - Q(a_\tau)\Big] = \sum_{a \in \mathcal{A}} \mathbb{E}[N_t(a)]\,(V^* - Q(a)) = \sum_{a \in \mathcal{A}} \mathbb{E}[N_t(a)]\,\Delta_a$$

How you read it matters. A good algorithm should pull an arm with a large gap (that is, a very bad arm) less often, because a large gap means each pull piles up that much regret. But there is a catch: we do not know the gaps. If we knew the gaps we would already know which arm is optimal, and the problem would be over. We want to pull bad arms less, but we do not know which arm is how bad, and that is the essence of the bandit problem.

Linear vs. sublinear regret

How the total regret grows over time is what grades an algorithm. Both extremes fail. If you explore forever (keep pulling at random), you keep pulling bad arms, so the regret grows linearly in time. If you never explore (keep pulling one arm you fixed on), then when you have picked wrong the loss carries on forever, which is again linear. The question is this: can you reduce regret slower than linear, that is, sublinearly?

Greedy and $\epsilon$-greedy

First we estimate the value of each arm by Monte Carlo: the mean of the rewards received from that arm so far.

$$\hat{Q}_t(a) = \frac{1}{N_t(a)} \sum_{t=1}^{T} r_t\,\mathbf{1}(a_t = a)$$

The greedy algorithm picks the arm with the highest estimated value, $a_t^* = \arg\max_a \hat{Q}_t(a)$. The problem is obvious. If early on you get unlucky and receive a few low rewards from the true optimal arm, greedy can turn its back on that arm forever and settle on a second-best one. Once locked in, it cannot get out. So greedy incurs linear regret.

$\epsilon$-greedy mixes in noise to prevent this lock-in. With probability $1-\epsilon$ it picks $\arg\max_a \hat{Q}(a)$, and with probability $\epsilon$ it pulls any arm at random. Because it keeps exploring forever, it does not miss the optimal arm entirely. But if $\epsilon$ is held constant, the inertia of pulling a bad arm with probability $\epsilon$ at every step never goes away.

$$l_t \geq \frac{\epsilon}{|\mathcal{A}|} \sum_{a \in \mathcal{A}} \Delta_a$$

Since this minimum regret is laid down at every step, constant $\epsilon$-greedy also ends up with linear regret. This is the limit of naive exploration.

Optimistic initialisation

The second principle. A very simple and practical idea: set the initial value $Q(a)$ of every arm deliberately high. Then update by incremental Monte Carlo, but start with $N(a) > 0$ from the outset.

$$\hat{Q}_t(a_t) = \hat{Q}_{t-1} + \frac{1}{N_t(a_t)}(r_t - \hat{Q}_{t-1})$$

The effect is this. Every arm starts out carrying an inflated expectation of “maybe I’m the best,” so the agent naturally tries the untried arms one by one. When it actually pulls one, the inflated expectation is trimmed down to the real value, and only then does the optimism lift. It is the principle “assume the best until proven otherwise,” taken literally. It is good in that it systematically induces early exploration, but it is not a fundamental cure. If bad luck trims the optimal arm’s optimism quickly early on, you can still get stuck on a second-best one. So even greedy plus optimistic initialisation, or $\epsilon$-greedy plus it, is still linear regret.

Decaying $\epsilon$-greedy

If holding $\epsilon$ constant is the problem, what if we shrink it over time? Take a decay schedule $\epsilon_1, \epsilon_2, \dots$. Consider the following schedule, with $c > 0$ and $d = \min_{a \mid \Delta_a > 0} \Delta_i$ (the smallest positive gap):

$$\epsilon_t = \min\left\{1, \frac{c|\mathcal{A}|}{d^2 t}\right\}$$

Remarkably, this decaying $\epsilon$-greedy achieves logarithmic regret asymptotically. It has come down from linear to logarithmic. But a decisive clause is attached: this schedule needs to know the gap $d$ in advance. As we saw, the gap is precisely the thing we do not know. So we have to reset the goal: to find an algorithm that achieves sublinear regret on an arbitrary multi-armed bandit, without any prior knowledge of the reward distribution $\mathcal{R}$.

Lower bound: Lai-Robbins

But there is a wall that no cleverness can get past. Let us first see what makes a problem hard. The difficulty of a problem is set by how alike the optimal arm and the rest are. A hard problem has arms that look similar (in distribution) but differ minutely in mean, because when two arms’ reward distributions nearly overlap it takes a great many samples to tell which is slightly better. This similarity is formalised by the gap $\Delta_a$ and the KL divergence $\mathrm{KL}(\mathcal{R}^a \Vert \mathcal{R}^{a^*})$ between the distributions.

Theorem (Lai and Robbins). The asymptotic total regret is at least logarithmic in the number of steps.

$$\lim_{t \to \infty} L_t \geq \log t \sum_{a \mid \Delta_a > 0} \frac{\Delta_a}{\mathrm{KL}(\mathcal{R}^a \Vert \mathcal{R}^{a^*})}$$

Here is how to read it. No algorithm can reduce regret faster than logarithmic. Logarithmic regret is the best we can hope for. And the smaller the KL in the denominator (the more alike the arms), the larger the lower bound. The intuition that arms which look similar but differ in mean are the hardest is embedded directly in the formula. All that remains is to find an algorithm that actually reaches this logarithmic lower bound.

Optimism in the face of uncertainty

The third principle. Suppose several arms’ value estimates each carry uncertainty (a distribution) of a different width. Which arm should you pick? Silver’s answer is the heart of this principle: the more uncertain we are about an action’s value, the more important it is to explore that action, because that very arm might in fact be the best. Being uncertain means holding open the possibility of being wide open to the upside.

If you pull the blue arm, the uncertainty about that arm’s value shrinks, and then attention shifts to another arm that is still more uncertain. Repeating this process, you eventually converge to the truly best arm. It amounts to verifying the optimism with data, one arm at a time.

Upper confidence bound

The numerical form of this principle is the upper confidence bound (UCB). Attach an upper bonus $\hat{U}_t(a)$ to each action so that, with high probability, the true value lies below it.

$$Q(a) \leq \hat{Q}_t(a) + \hat{U}_t(a)$$

This bonus depends on how many times the arm has been pulled, $N_t(a)$. If $N_t(a)$ is small (pulled less), $\hat{U}_t(a)$ is large (the estimate is uncertain); if $N_t(a)$ is large, $\hat{U}_t(a)$ is small (the estimate is accurate). And you pick the arm with the highest bound.

$$a_t = \arg\max_{a \in \mathcal{A}} \hat{Q}_t(a) + \hat{U}_t(a)$$

Chosen either because the estimate is good (high value) or because it has been pulled little (uncertain). Exploitation and exploration dissolve into a single expression.

Deriving the bonus from Hoeffding’s inequality

But you cannot set the bonus $\hat{U}_t(a)$ to just any constant. It must be a statistical confidence interval, and its width comes from Hoeffding’s inequality.

Theorem (Hoeffding’s inequality). If $X_1, \dots, X_t$ are i.i.d. random variables in $[0,1]$ and $\overline{X}_t = \frac{1}{t}\sum_{\tau=1}^t X_\tau$ is the sample mean, then

$$\mathbb{P}\big[\mathbb{E}[X] > \overline{X}_t + u\big] \leq e^{-2tu^2}$$

The reading is the key. The probability that the sample mean is off from the true mean by $u$ or more shrinks exponentially as $u$ grows. Applying this to the reward when arm $a$ is chosen,

$$\mathbb{P}\big[Q(a) > \hat{Q}_t(a) + U_t(a)\big] \leq e^{-2 N_t(a) U_t(a)^2}$$

Now fix a probability $p$ that the true value exceeds the bound, and solve for $U_t(a)$.

$$e^{-2 N_t(a) U_t(a)^2} = p \quad\Longrightarrow\quad U_t(a) = \sqrt{\frac{-\log p}{2 N_t(a)}}$$

As observations accumulate we want to guard ever more strictly against the accident of the true value exceeding the bound, so we shrink $p$ with time. Setting $p = t^{-4}$, for instance, makes us surely pick the optimal action as $t \to \infty$, and the bonus takes the following clean form.

$$U_t(a) = \sqrt{\frac{2 \log t}{N_t(a)}}$$

The key is that this $\sqrt{2 \ln t / N(a)}$ is not an arbitrarily chosen magic constant. It is the very width of the confidence interval that Hoeffding guarantees. The less an arm has been pulled (the smaller $N$), the wider it opens; and as time passes (larger $t$, demanding more certainty), it opens a little wider still.

UCB1

Set exactly this into an algorithm and you get UCB1.

$$a_t = \arg\max_{a \in \mathcal{A}} Q(a) + \sqrt{\frac{2 \log t}{N_t(a)}}$$

Theorem. The UCB algorithm achieves logarithmic total regret asymptotically.

$$\lim_{t \to \infty} L_t \leq 8 \log t \sum_{a \mid \Delta_a > 0} \Delta_a$$

Unlike decaying $\epsilon$-greedy, which had to know the gap in advance, UCB1 reaches logarithmic regret without any prior knowledge of the gap. Since the Lai-Robbins lower bound was logarithmic, UCB comes within a constant factor of that wall. Silver shows a comparison plot in which, on an actual 10-arm bandit experiment, UCB reliably outperforms $\epsilon$-greedy.

Probability matching and Thompson sampling

So far we have only assumed an upper bound on the reward distribution and used no particular prior knowledge. Bayesian bandits go one step further. They assume a prior $p[\mathcal{R}]$ over the rewards and, given the observed history $h_t = a_1, r_1, \dots, a_{t-1}, r_{t-1}$, compute the posterior $p[\mathcal{R} \mid h_t]$ to guide exploration. If the prior knowledge is accurate, performance improves. There are two roads that use this posterior: one is Bayesian UCB, and the other is the probability matching (Thompson sampling) we now turn to.

As an example of Bayesian UCB, if we assume the rewards are Gaussian, we obtain a Gaussian posterior over each arm’s mean and variance by Bayes’ rule, and pick the arm whose mean plus a constant times the standard deviation is highest.

$$a_t = \arg\max_a\; \mu_a + \frac{c\,\sigma_a}{\sqrt{N(a)}}$$

Same spirit as the earlier UCB: the more uncertain (the larger $\sigma_a$), the more it is pushed upward.

Probability matching

The fourth principle. Probability matching picks each action in proportion to the probability that that action is optimal.

$$\pi(a \mid h_t) = \mathbb{P}\big[Q(a) > Q(a'),\ \forall a' \neq a \mid h_t\big]$$

See why this policy connects to optimism in the face of uncertainty. The more uncertain an action, the thicker the upper tail of its posterior, so the probability that its value exceeds all other arms’, that is, the probability that it is optimal, naturally rises. So an uncertain arm gets picked more often. The catch is only that this probability is hard to compute analytically from the posterior.

Thompson sampling

Here a strikingly simple trick appears. Thompson sampling implements probability matching with a single sample.

$$\pi(a \mid h_t) = \mathbb{P}\big[Q(a) > Q(a'),\ \forall a' \neq a \mid h_t\big] = \mathbb{E}_{\mathcal{R} \mid h_t}\big[\mathbf{1}(a = \arg\max_a Q(a))\big]$$

The procedure is this. Obtain the posterior $p[\mathcal{R} \mid h_t]$ by Bayes’ rule, sample one reward distribution $\mathcal{R}$ from that posterior, compute the value $Q(a) = \mathbb{E}[\mathcal{R}^a]$ from that sample, and then pick the arm that gives the maximum on that sample, $a_t = \arg\max_a Q(a)$. This simple act of taking the argmax of one sample drawn from the posterior each time realises exactly “pick each arm in proportion to the probability that it is optimal.” An uncertain arm often draws a large sample and so wins often.

The twist is in the history. This method is a very old idea proposed by Thompson in 1933, and remarkably, Thompson sampling achieves the Lai-Robbins lower bound. Like UCB, it reaches the theoretical best, and the implementation ends with drawing a single sample from the posterior.

Cumulative regret of ε-greedy, UCB, and Thompson on a 10-arm bandit. Thompson is generally the lowest. Run it long with “+5000” and it becomes clear that ε-greedy, because of its constant exploration, has its regret grow steeply and linearly, while UCB and Thompson flatten out sublinearly (logarithmically). Try raising ε, or “new bandit” to check it on a different problem too.

The value of information and Bayes-adaptive RL

The fifth principle. Why is exploration useful? Because it yields information. So can we put a value on information? The value of information is the amount of reward a decision-maker would be willing to pay to have that information before making a decision. It is the long-term reward after gaining the information minus the immediate reward. The more uncertain the situation, the more information there is to gain, so it makes sense to explore uncertain situations more. If you know the value of information, you can weigh exploration and exploitation optimally.

The information-state space

Here the perspective shifts sharply. So far we have seen the bandit as a one-step decision problem, but it can also be seen as a sequential decision problem. At each step there is an information state $\tilde{s}$. $\tilde{s}$ is a statistic of the history, $\tilde{s}_t = f(h_t)$, summarising all the information accumulated so far. It is, in effect, a state that captures what you still do not know. And each action $a$ (by adding information) causes a transition to a new information state $\tilde{s}'$, with probability $\tilde{\mathcal{P}}^a_{\tilde{s},\tilde{s}'}$. This defines an MDP $\tilde{\mathcal{M}} = \langle \tilde{\mathcal{S}}, \mathcal{A}, \tilde{\mathcal{P}}, \mathcal{R}, \gamma \rangle$ over the augmented information-state space. Exploration is thereby reduced to a planning problem over this vast MDP.

Example: Bernoulli bandit

A concrete example completes the picture. In a Bernoulli bandit each arm is $\mathcal{R}^a = \mathcal{B}(\mu_a)$, a game you win or lose with probability $\mu_a$. You want to find which arm’s $\mu_a$ is highest. Here the information state is $\tilde{s} = \langle \alpha, \beta \rangle$. $\alpha_a$ is the number of times arm $a$ was pulled and the reward was 0, and $\beta_a$ is the number of times the reward was 1. This $\langle \alpha, \beta \rangle$ corresponds to a $\mathrm{Beta}(\alpha, \beta)$ posterior over that arm’s reward model.

Each time you pull an arm, the posterior updates, and that is exactly the state transition.

$$\langle \alpha_a, \beta_a \rangle \to \begin{cases} \langle \alpha_a + 1, \beta_a \rangle & r = 0 \\ \langle \alpha_a, \beta_a + 1 \rangle & r = 1 \end{cases}$$

Starting from a $\mathrm{Beta}(\alpha_a, \beta_a)$ prior and updating the posterior at each pull, this flow defines the transition function $\tilde{\mathcal{P}}$ of the Bayes-adaptive MDP. Each state transition corresponds to one Bayesian model update.

Now we hold an infinite MDP over information states. This can be solved with reinforcement learning. Going model-free gives methods like Q-learning (Duff, 1994), and going Bayesian model-based gives the Gittins index (Gittins, 1979). This approach is called Bayes-adaptive reinforcement learning, and it finds the Bayes-optimal exploration/exploitation trade-off with respect to the prior. That is, solving the Bayes-adaptive MDP by dynamic programming yields an exact solution, and that solution is precisely the Gittins index.

The trouble is that this exact solution is usually intractable: the information-state space is too large. So in practice one uses the recent idea of simulation-based search (Guez et al. 2012), which runs several simulations from the current information state to look ahead into the front of the information-state space.

Contextual bandits

Adding a state (context) to the bandit brings us one step closer to practice. A contextual bandit is a tuple $\langle \mathcal{A}, \mathcal{S}, \mathcal{R} \rangle$. $\mathcal{S} = \mathbb{P}[s]$ is an unknown distribution over states (contexts), and $\mathcal{R}^a_s(r) = \mathbb{P}[r \mid s, a]$ is a reward distribution conditioned on state and action. At each step the environment emits a state $s_t \sim \mathcal{S}$, the agent picks an action $a_t$, and the environment gives a reward $r_t \sim \mathcal{R}^{a_t}_{s_t}$. Problems like which article to feature on a news front page, or which ad to show this user, fit right here. The best action changes with the context (the user, the time of day).

Linear UCB

We estimate the value function with a linear approximator, $Q_\theta(s, a) = \phi(s, a)^\top \theta \approx Q(s, a)$. The parameters are found by least-squares regression.

$$A_t = \sum_{\tau=1}^t \phi(s_\tau, a_\tau)\phi(s_\tau, a_\tau)^\top, \quad b_t = \sum_{\tau=1}^t \phi(s_\tau, a_\tau) r_\tau, \quad \theta_t = A_t^{-1} b_t$$

Here is the decisive observation. Least-squares regression gives not only the mean value $Q_\theta(s, a)$ but also the variance of that value, $\sigma_\theta^2(s, a)$: the uncertainty coming from parameter-estimation error. So we can add a bonus $U_\theta(s, a) = c\sigma$ in proportion to the uncertainty, taking $c$ standard deviations above the mean as the UCB. Geometrically, we draw a confidence ellipsoid $\mathcal{E}_t$ around the parameter $\theta_t$ that contains the true parameter $\theta^*$ with high probability, and pick the parameter within it that maximises the value, reflecting the uncertainty.

Since the parameter covariance in least squares is $A^{-1}$ and the value is linear in the features, the variance of the value becomes a quadratic form, $\sigma_\theta^2(s, a) = \phi(s, a)^\top A^{-1} \phi(s, a)$. So the selection rule is

$$a_t = \arg\max_{a \in \mathcal{A}} Q_\theta(s_t, a) + c\sqrt{\phi(s_t, a)^\top A_t^{-1} \phi(s_t, a)}$$

The bandit’s $\sqrt{2\log t / N(a)}$ has grown, in the contextual setting, into the confidence-ellipsoid width $c\sqrt{\phi^\top A^{-1} \phi}$. Silver cites the case of Li et al., who used this linear UCB to select news front-page articles.

Extension to MDPs

The five principles established for bandits lift straight to MDPs: naive exploration, optimistic initialisation, optimism in the face of uncertainty, probability matching, information-state search. Let us carry each over to the MDP setting.

Optimistic initialisation

Model-free, initialise the action values optimistically.

$$Q(s, a) \leftarrow \frac{r_{\max}}{1 - \gamma}$$

Inflate to the maximum reachable value like this, then run your favourite model-free algorithm, whether Monte Carlo control, Sarsa, or Q-learning, and you systematically explore the unvisited states and actions. Model-based, build an optimistic MDP. Initialise every yet-unexperienced transition as “going to heaven,” that is, as going to a terminal state that gives reward $r_{\max}$. Then solve this optimistic MDP by policy iteration, value iteration, or tree search. This is the RMax algorithm (Brafman and Tennenholtz).

Optimism in the face of uncertainty

Model-free UCB maximises the upper bound of the action value, $a_t = \arg\max_a Q(s_t, a) + U(s_t, a)$. Estimating the uncertainty of policy evaluation is easy, but it ignores the uncertainty coming from policy improvement. To reflect this properly and aim at an upper bound on the optimal action value $Q^*$, you would have to add the uncertainty $U_2$ from improvement as well, as in $a_t = \arg\max_a Q(s_t, a) + U_1(s_t, a) + U_2(s_t, a)$, and this part is tricky.

Probability matching: model-based Thompson

Bayesian model-based reinforcement learning maintains a posterior $p[\mathcal{P}, \mathcal{R} \mid h_t]$ over the MDP model itself, estimating transitions and rewards together. Thompson sampling from this posterior becomes probability matching.

$$\pi(s, a \mid h_t) = \mathbb{E}_{\mathcal{P}, \mathcal{R} \mid h_t}\big[\mathbf{1}(a = \arg\max_a Q^*(s, a))\big]$$

The procedure mirrors the bandit case exactly. Compute the posterior $p[\mathcal{P}, \mathcal{R} \mid h_t]$, sample a whole MDP $\langle \mathcal{P}, \mathcal{R} \rangle$ from it, solve that sampled MDP with your favourite planning algorithm to obtain $Q^*$, and pick the optimal action on that sample. Where the bandit drew a single reward distribution, the MDP draws a whole world and plans inside it.

MDPs too can be augmented with an information state. The augmented state is $\langle s, \tilde{s} \rangle$, where $s$ is the state within the original MDP and $\tilde{s}$ is a statistic of the history (the accumulated information). Each action causes both a transition to a new state $s'$ and a transition to a new information state $\tilde{s}'$, defining an MDP $\tilde{\mathcal{M}}$ over the augmented information-state space.

In particular, the posterior over the MDP model, $\tilde{s}_t = \mathbb{P}[\mathcal{P}, \mathcal{R} \mid h_t]$, is itself an information state, and the augmented MDP over $\langle s, \tilde{s} \rangle$ is called the Bayes-adaptive MDP. Solving it yields the optimal exploration/exploitation trade-off (with respect to the prior). As with bandits, though, the Bayes-adaptive MDP is usually enormously large, so simulation-based search (Guez et al.) has been effective.

Closing

Silver surveyed the several principles of exploration and exploitation: naive methods like $\epsilon$-greedy, optimistic initialisation, upper confidence bounds, probability matching, information-state search. All five were born on the simplest bandit stage, but the same principles apply straight to MDPs. The exploration strategies that looked disparate on the surface were, in fact, laid out on a single five-branched map.