Multi-armed bandits

The stochastic bandit#

$K$ arms, each with an unknown reward distribution $\nu_i$ with mean $\mu_i$, bounded in $[0,1]$. At each round $t$ the learner picks $a_t$ and observes $X_t \sim \nu_{a_t}$. Write $\mu^* = \max_i \mu_i$ and the suboptimality gap $\Delta_i = \mu^* - \mu_i$.

Pseudo-regret after $T$ rounds: $$ \mathcal{R}(T) = T\mu^* - \mathbb{E}\left[\sum_{t=1}^{T} \mu_{a_t}\right] = \sum_{i=1}^{K} \Delta_i \, \mathbb{E}[N_i(T)] $$ where $N_i(T)$ is the number of pulls of arm $i$. The decomposition on the right is the one that matters: regret is entirely determined by how often you pull suboptimal arms, weighted by how bad they are.

The lower bound#

Lai and Robbins (1985) proved that for any consistent policy, $$ \liminf_{T\to\infty} \frac{\mathcal{R}(T)}{\ln T} \ge \sum_{i : \Delta_i > 0} \frac{\Delta_i}{\mathrm{KL}(\nu_i \,|\, \nu^*)} $$ where $\mathrm{KL}$ is the Kullback-Leibler divergence between the suboptimal arm's reward distribution and the optimal arm's. Logarithmic regret is therefore not only achievable — it is the best possible. Any claim of sublogarithmic regret on a stochastic bandit is a claim of a contradiction.

The gap-dependent bound blows up as $\Delta_i \to 0$, which is why the minimax (gap-free) form is also quoted: $\Theta(\sqrt{KT})$, achieved by MOSS (Audibert and Bubeck, 2009).

UCB1#

Auer, Cesa-Bianchi and Fischer (2002): pull $\arg\max_i \left[ \hat\mu_i + \sqrt{\frac{2\ln t}{N_i(t)}} \right]$.

The bonus comes from Hoeffding's inequality: with probability at least $1 - t^{-4}$, $|\hat\mu_i - \mu_i| \le \sqrt{2\ln t / N_i}$. The resulting bound is $$ \mathcal{R}(T) \le \sum_{i:\Delta_i>0} \frac{8\ln T}{\Delta_i} + \left(1 + \frac{\pi^2}{3}\right)\sum_i \Delta_i $$

The constant 8 is loose and the Hoeffding bound ignores the reward distribution's shape. KL-UCB (Garivier and Cappé, 2011) replaces it with a KL-based confidence set and attains the Lai-Robbins constant exactly. In practice KL-UCB substantially outperforms UCB1 on Bernoulli arms, and the empirical gap seen in the code above largely disappears.

Thompson sampling#

Sample $\theta_i \sim p(\mu_i \mid \mathcal{D}_t)$ for each arm, pull $\arg\max_i \theta_i$, update the posterior. For Bernoulli rewards with a $\mathrm{Beta}(\alpha, \beta)$ prior the posterior is $\mathrm{Beta}(\alpha + w_i, \beta + l_i)$, conjugate and free.

Published in Thompson (1933) and ignored for seventy years. Chapelle and Li (2011) demonstrated it empirically outperforming UCB on display advertising; Agrawal and Goyal (2012) and Kaufmann, Korda and Munos (2012) then proved it achieves the Lai-Robbins bound. It is optimal, it has no tuning constant, and it is three lines of code — an unusual combination.

Its practical advantage over UCB comes from randomisation: UCB is deterministic given the history, so under delayed or batched feedback it pulls the same arm repeatedly before any update lands. Thompson sampling diversifies naturally, which matters a great deal in systems where feedback arrives minutes later.

Adversarial bandits#

Drop the stochastic assumption and let an adversary choose rewards. EXP3 (Auer et al., 2002) uses exponential weights over an importance-weighted reward estimate and attains $O(\sqrt{TK\ln K})$ regret against the best fixed arm in hindsight. The $\sqrt{T}$ rate is unimprovable here — no logarithmic regret exists without stochastic structure.

Contextual bandits#

At each round a context $x_t \in \mathcal{X}$ arrives before the choice, and the reward depends on $(x_t, a_t)$. This is the formulation that dominates industrial deployment.

• LinUCB (Li et al., 2010) assumes $\mathbb{E}[r \mid x, a] = x^\top \theta_a$ and builds ellipsoidal confidence sets by ridge regression; regret $\tilde{O}(d\sqrt{T})$ for $d$-dimensional contexts.
• Thompson sampling for linear bandits (Agrawal and Goyal, 2013) samples $\tilde\theta$ from a Gaussian posterior.
• Off-policy evaluation matters more than the algorithm in practice: inverse propensity scoring and doubly robust estimators (Dudík, Langford and Li, 2011) let you estimate a new policy's value from logged data, provided the logging policy was stochastic and its propensities were recorded. Systems that log only the chosen action, without the probability it was chosen with, cannot be evaluated offline at all. Record propensities from day one.

The bridge to full RL#

A bandit is an MDP with $|\mathcal{S}| = 1$. Everything hard about RL that is absent here — state, transitions, delayed credit, bootstrapping — arrives at once when you add states. The optimality results in this lesson do not survive that transition, which is worth remembering whenever a deep RL paper cites a bandit bound as motivation.

References#

• Lai and Robbins (1985), Asymptotically efficient adaptive allocation rules.
• Auer, Cesa-Bianchi and Fischer (2002), Finite-time Analysis of the Multiarmed Bandit Problem.
• Chapelle and Li (2011), An Empirical Evaluation of Thompson Sampling.
• Agrawal and Goyal (2012), Analysis of Thompson Sampling for the Multi-armed Bandit Problem.
• Li et al. (2010), A Contextual-Bandit Approach to Personalized News Article Recommendation — arxiv.org/abs/1003.0146.
• Lattimore and Szepesvári (2020), Bandit Algorithms — free online, and the current standard reference.

What to learn next#

• Q-learning — what happens when your choice changes what you face next.
• Exploration vs exploitation — the intuition this lesson formalises.
• The cold-start problem — bandits doing real work inside recommender systems.