Contextual Bandits

Corresponds to Lattimore & Szepesvári, Part V introduction and Chapter 18.

Motivation: real problems have many actions and side information

IntuitionWhy the earlier algorithms aren’t enough

A targeted-advertising system may have thousands of actions, and before each decision it sees contextual information about the user and the ads. The algorithms so far can’t use side information, and ignoring it makes the problem effectively non-stationary: the best ad for a teenager and for a retiree differ, so “the best single ad in hindsight” is a poor target.

NoteHow Part V handles this

Large action sets: add structure so that what is learned about one action generalizes to others. Ads have features (topic, format), and the reward is modelled as a nice function (linear, smooth) of the features.
Context: model the mean reward as a function of context features and action features together. As later chapters show, this amounts to an action set that changes every round.
Linear structure (Chapter 19 onward) is the main case: stochastic-linear-bandits.
Computation becomes a central concern, which it never was with a few arms.
Delayed or unattributed rewards (Part VII) and non-stationarity (Chapter 31) are treated elsewhere.

ImportantChoosing a benchmark is a trade-off

A weak benchmark is pointless: matching it perfectly can still mean performing badly. A strong benchmark is more meaningful but harder to learn to compete with, and the learning penalty must be weighed against the gain. This is the bandit version of the bias–variance trade-off, and it runs through this whole chapter. The chapter first shows how to compete with richer benchmarks; it does not settle how rich to make them.

Contextual bandits: one bandit per context

DefinitionAdversarial $k$ -armed contextual bandit

The adversary secretly fixes rewards $(x_t)_{t=1}^n$ with $x_t\in[0,1]^k$ and contexts $(c_t)_{t=1}^n$ with $c_t\in\mathcal C$ , an arbitrary fixed set. In each round the learner:

observes $c_t$ ;
picks a distribution $P_t\in\mathcal P_{k-1}$ and samples $A_t\sim P_t$ ;
observes only $X_t = x_{tA_t}$ .

flowchart LR
  A["Adversary fixes rewards x_t and contexts c_t"] --> C["Learner sees context c_t"]
  C --> P["Learner picks P_t, samples A_t"]
  P --> O["Observes only X_t = x_t,A_t"]
  O --> C

DefinitionContextual regret

Compete with the best context-dependent choice in hindsight:

$R_n = \mathbb E\Big[\sum_{c\in\mathcal C}\max_{i\in[k]}\sum_{t:\,c_t = c}(x_{ti} - X_t)\Big] \tag{18.1}$

Equivalently, with $\Phi$ the set of all maps $\mathcal C\to[k]$ ,

$R_n = \mathbb E\Big[\max_{\phi\in\Phi}\sum_{t=1}^n\big(x_{t\phi(c_t)} - X_t\big)\Big] \tag{18.5}$

Component	Detail
Benchmark	The best policy $\phi : \mathcal C\to[k]$ in hindsight.
Versus Chapter 11	There, $\Phi$ contained only the $k$ constant maps.
Randomness	Only the learner’s, since rewards and contexts are fixed in advance.

One Exp3 per context

AlgorithmIndependent Exp3 instances

If $\mathcal C$ is finite, run a separate Exp3 for each context, and in round $t$ consult only the instance for $c_t$ . Each instance’s regret is

$R_{nc} = \mathbb E\Big[\max_i\sum_{t:\,c_t = c}(x_{ti} - X_t)\Big]\le2\sqrt{k\,n_c\log k}, \qquad n_c = \sum_{t=1}^n\mathbb I\{c_t = c\} \tag{18.2}$

WarningUse an anytime Exp3

$n_c$ isn’t known in advance, so the learning rate can’t be tuned to it. Use a version with a decreasing learning rate (Exercise 28.13), for which (18.2) holds without knowing $n_c$ .

TheoremRegret of one Exp3 per context

$R_n = \sum_cR_{nc}\le2\sum_{c\in\mathcal C}\sqrt{k\log(k)\,n_c}\le2\sqrt{nk|\mathcal C|\log k} \tag{18.3–18.4}$

ProofCauchy–Schwarz on the context counts (Exercise 18.1)

$\sum_c\sqrt{n_c}\le\sqrt{|\mathcal C|\sum_cn_c} = \sqrt{n|\mathcal C|}$ , with equality when every context occurs $n/|\mathcal C|$ times. Equivalently, by Jensen, uniform context frequencies are the worst case. With one context the bound reduces to the ordinary $2\sqrt{nk\log k}$ .

∎

RemarkWhich bound to prefer

Ignoring context, Exp3 guarantees $\mathbb E\sum_tX_t\ge\max_i\sum_tx_{ti} - 2\sqrt{kn\log k}$ . Per-context Exp3 guarantees $\mathbb E\sum_tX_t\ge\sum_c\max_i\sum_{t:c_t=c}x_{ti} - 2\sqrt{kn|\mathcal C|\log k}$ . The second benchmark is higher but the penalty is larger by $\sqrt{|\mathcal C|}$ . For large $n$ and useful contexts the second wins; it is vacuous whenever $n\le4k|\mathcal C|\log k$ .

Bandits with expert advice

The problem. When $\mathcal C$ is large, one bandit per context wastes almost all the data: each context is seen too rarely to learn anything. But large context sets are rarely unstructured. In movie recommendation, the context (age, demographics, viewing history) lives in a combinatorially large space, yet similar users tend to like similar movies. So compete with a smaller, smarter set $\Phi$ of policies.

ExampleWays to shrink $\Phi$

Idea	Competitor class $\Phi$	Algorithmic consequence
Partitions	maps constant on each part of a partition $\mathcal P$ of $\mathcal C$	one Exp3 per part: regret depends on $\lvert\mathcal P\rvert$ , not $\lvert\mathcal C\rvert$
Similarity	maps whose average dissimilarity $\frac1{\lvert\mathcal C\rvert^2}\sum_{c,d}(1 - s(c,d))\mathbb I\{\phi(c)\ne\phi(d)\}$ is at most $\theta$	a meaningful target, but no simple Exp3 meta-algorithm
Supervised learning	predictors $\phi_1, \ldots, \phi_M$ trained offline on batch data	compete online with the best of them, with no need to pick one by offline evaluation

IntuitionOnce $\Phi$ is fixed, contexts barely matter

Each round, all a learner needs is what each policy recommends now. That suggests forgetting the internal structure of $\Phi$ and treating its members as black-box experts.

DefinitionBandits with expert advice

$M$ experts. In round $t$ each expert $m$ announces a probability vector $E^{(t)}_m\in\mathcal P_{k-1}$ over actions (it may randomize), collected in the advice matrix $E^{(t)}\in[0,1]^{M\times k}$ . The learner observes $E^{(t)}$ , chooses $P_t$ , samples $A_t$ and receives $X_t = x_{tA_t}$ . The regret is against the best expert in hindsight:

$R_n = \mathbb E\Big[\max_{m\in[M]}\sum_{t=1}^nE^{(t)}_mx_t - \sum_{t=1}^nX_t\Big] \tag{18.6}$

where $E^{(t)}_mx_t$ is expert $m$ ‘s expected reward in round $t$ . The experts are oblivious: their advice doesn’t depend on the learner’s actions.

RemarkMore general than contextual bandits

A contextual bandit is the special case where each expert is a fixed map $\phi : \mathcal C\to[k]$ , with $E^{(t)}_{mi} = \mathbb I\{\phi(c_t) = i\}$ . This is the “socks for feet” picture: experts look at the context and recommend; the learner decides whom to trust.

Exp4

AlgorithmExp4 — “exponential weighting for exploration and exploitation with experts” (Algorithm 11)

Input $n, k, M, \eta, \gamma$ . Set $Q_1 = (\frac1M, \ldots, \frac1M)$ (a row vector over experts). For $t = 1, \ldots, n$ :

receive advice $E^{(t)}$ ;
play $A_t\sim P_t = Q_tE^{(t)}$ , i.e. sample an expert $M_t\sim Q_t$ , then $A_t\sim E^{(t)}_{M_t}$ ;
receive $X_t = x_{tA_t}$ ;
estimate action rewards: $\hat X_{ti} = 1 - \frac{\mathbb I\{A_t = i\}}{P_{ti} + \gamma}(1 - X_t)$ ;
propagate to experts: $\tilde X_t = E^{(t)}\hat X_t$ , so expert $m$ gets $\tilde X_{tm} = \sum_iE^{(t)}_{mi}\hat X_{ti}$ ;
exponential weights over experts: $Q_{t+1,m} = \dfrac{\exp(\eta\tilde X_{tm})Q_{tm}}{\sum_j\exp(\eta\tilde X_{tj})Q_{tj}}$ .

IntuitionScore experts, not arms

Exp3 keeps weights on arms. Exp4 keeps weights on experts: it estimates every arm’s reward by importance weighting, credits each expert with what it would have earned in expectation under its own advice, and reweights. With $\gamma = 0$ this is the original Exp4; $\gamma > 0$ gives Exp4-IX (implicit exploration).

WarningCost

$O(M)$ memory and $O(M + k)$ computation per round (sampling in two stages). Practical only when $M$ and $k$ are both modest, which rules out naive use with combinatorially many experts.

Regret analysis

TheoremTheorem 18.1 — Regret of Exp4

With $\gamma = 0$ and $\eta = \sqrt{2\log(M)/(nk)}$ ,

$R_n\le\sqrt{2nk\log M} \tag{18.7}$

LemmaLemma 18.2 — Exponential weights over experts

For any $m^*\in[M]$ ,

$\sum_{t=1}^n\tilde X_{tm^*} - \sum_{t=1}^n\sum_{m=1}^MQ_{tm}\tilde X_{tm}\le\frac{\log M}\eta + \frac\eta2\sum_{t=1}^n\sum_{m=1}^MQ_{tm}(1 - \tilde X_{tm})^2$

This is exactly the potential argument of Theorem 11.2 with experts in place of arms (Exercise 18.2). It needs $\tilde X_{tm}\le1$ , which holds because each $\hat X_{ti}\le1$ and $\tilde X_{tm}$ is a convex combination of them.

ProofProof of Theorem 18.1: unbiased propagation, then a variance bound of exactly

k

Step 1: The benchmark is fixed. Experts are oblivious, so the best expert $m^* = \arg\max_m\sum_tE^{(t)}_mx_t$ is deterministic (18.8).

Step 2: Unbiasedness carries through the advice. With $\gamma = 0$ , $\mathbb E_t[\hat X_t] = x_t$ , so $\mathbb E_t[\tilde X_t] = E^{(t)}\mathbb E_t[\hat X_t] = E^{(t)}x_t$ (18.10). And $\sum_mQ_{tm}\tilde X_{tm} = \sum_iP_{ti}\hat X_{ti}$ , whose conditional mean is the learner’s expected reward. Taking expectations in Lemma 18.2,

$R_n\le\frac{\log M}\eta + \frac\eta2\sum_t\mathbb E\Big[\sum_mQ_{tm}(1 - \tilde X_{tm})^2\Big] \tag{18.11}$

Step 3: Switch to losses. With $\hat Y_{ti} = 1 - \hat X_{ti} = \frac{A_{ti}y_{ti}}{P_{ti}}$ and $\tilde Y_{tm} = 1 - \tilde X_{tm} = E^{(t)}_m\hat Y_t = \frac{E^{(t)}_{mA_t}y_{tA_t}}{P_{tA_t}}$ ,

$\mathbb E_t[\tilde Y_{tm}^2] = \sum_iP_{ti}\frac{(E^{(t)}_{mi}y_{ti})^2}{P_{ti}^2} = \sum_i\frac{(E^{(t)}_{mi}y_{ti})^2}{P_{ti}}\le\sum_i\frac{E^{(t)}_{mi}}{P_{ti}} \tag{18.12}$

using $E^{(t)}_{mi}, y_{ti}\in[0,1]$ .

Step 4: Averaging over experts gives exactly $k$ .

$\sum_mQ_{tm}\sum_i\frac{E^{(t)}_{mi}}{P_{ti}} = \sum_i\frac{\sum_mQ_{tm}E^{(t)}_{mi}}{P_{ti}} = \sum_i\frac{P_{ti}}{P_{ti}} = k$

Step 5: Tune. $R_n\le\frac{\log M}\eta + \frac{\eta nk}2 = \sqrt{2nk\log M}$ .

∎

ImportantExperts cost only $\log M$

The variance term is $k$ per round regardless of $M$ : an expert’s estimate is noisy only through the arms it recommends, and averaged over the learner’s own distribution this always sums to $k$ . The number of experts enters only through the starting uncertainty $\log M$ . That is why exponentially many experts are statistically affordable.

CorollaryContextual bandits recovered and generalized

All maps on a finite context set: $M = k^{|\mathcal C|}$ , so $\log M = |\mathcal C|\log k$ and $R_n\le\sqrt{2nk|\mathcal C|\log k}$ , the per-context Exp3 bound with a slightly better constant.
Any finite class $\Phi$ of maps $\mathcal C\to[k]$ , with $\mathcal C$ arbitrary or infinite: $R_n\le\sqrt{2nk\log|\Phi|}$ . The size of the context space no longer matters, only the size of the policy class.

Adapting to agreement among experts

DefinitionEffective number of experts

$E_t^* = \sum_{s=1}^t\sum_{i=1}^k\max_{m\in[M]}E^{(s)}_{mi}$

If all experts agree, each round contributes $\sum_iE_i = 1$ , so $E_t^* = t$ . In general (Exercise 18.7)

$E_n^*\le n\min(k,M) \tag{18.13}$

since $\sum_i\max_mE_{mi}\le\sum_i1 = k$ and $\le\sum_i\sum_mE_{mi} = M$ . So $E_n^*/n$ is an effective number of experts, measuring how much they disagree.

TheoremTheorem 18.3 — Agreement-adaptive regret

With time-varying learning rate $\eta_t = \sqrt{\log(M)/E_t^*}$ , for a universal constant $C$ ,

$R_n\le C\sqrt{E_n^*\log M} \tag{18.14}$

(Proof: Exercise 18.4, adapting the Exp3 analysis to decreasing learning rates; see Exercises 28.12–28.13.)

IntuitionLearning is easy when experts agree

If every expert says the same thing, there is nothing to learn, and the bound grows like $\sqrt{n\log M}$ rather than $\sqrt{nk\log M}$ . The bound is data-dependent (in adversarial bandits, data and instance coincide), never worse than (18.7) up to constants, and, since $\eta_t$ doesn’t use $n$ , the algorithm is anytime. This is the first time-varying learning rate in the book; they become a main tool for adapting to the instance later.

Notes and extensions

RemarkExp4 as a building block

Define your own experts and Exp4 gives a regret bound for free, though not always an efficient algorithm.

Non-stationary bandits (Chapter 31): experts are switching sequences of arms. One of the rare cases where Exp4 runs efficiently with combinatorially many experts.
Finite-memory policies (Exercise 18.5): with observations $o_t\in[O]$ and experts all maps $[O]^m\to[k]$ of the last $m$ observations, $M = k^{O^m}$ and $\mathbb E[R_n]\le\sqrt{2knO^m\log k}$ .
When Exp4 isn’t computationally efficient, it is still a good way to find out what regret is statistically achievable.

WarningComputation is the real obstacle

In general there is no way around $O(M + k)$ per round. One escape is an optimisation oracle that, given contexts and reward vectors, returns the best expert in hindsight (the offline problem (18.8)). Chapter 30 shows follow-the-perturbed-leader with such an oracle for combinatorial bandits, though those settings carry extra information that makes reward estimation possible. Note that ERM can be NP-hard even for linear classifiers.

TheoremStochastic contextual bandits: epoch-greedy ETC (Exercise 18.8)

Contexts $C_t$ i.i.d. from $\xi$ , rewards from $P_{C_tA_t}$ with mean $\mu(c,i)$ , policy value $\mu(\phi) = \int\mu(c,\phi(c))\,d\xi(c)$ , and regret $R_n = n\sup_{\phi\in\Phi}\mu(\phi) - \mathbb E\sum_tX_t$ . Explore uniformly for $m$ rounds, estimate $\hat\mu(\phi) = \frac km\sum_{t\le m}\mathbb I\{A_t = \phi(C_t)\}X_t$ , then commit to $\hat\phi^* = \arg\max_\phi\hat\mu(\phi)$ using the oracle. For finite $\Phi$ and tuned $m$ ,

$R_n = O\big(n^{2/3}(k\log|\Phi|)^{1/3}\big)$

DerivationWhere

n^{2/3}

comes from

Each $\hat\mu(\phi)$ is an average of $m$ i.i.d. unbiased terms in $[0,k]$ with variance at most $k$ (the indicator fires with probability $1/k$ ). By Bernstein and a union bound over $\Phi$ , every estimate is within about $\sqrt{k\log|\Phi|/m}$ of the truth (the range term $\frac km\log|\Phi|$ is lower order at the optimal $m$ ). So the committed policy loses at most about $2\sqrt{k\log|\Phi|/m}$ per round, and $R_n\lesssim m + n\sqrt{k\log|\Phi|/m}$ . Balancing at $m\approx n^{2/3}(k\log|\Phi|)^{1/3}$ gives the bound. Using Hoeffding with range $k$ instead would give the worse $k^{2/3}$ . (Sketch worked here.) This is the explore-then-commit version of epoch-greedy (Langford–Zhang 2008), the contextual cousin of ETC.

RemarkReducing contextual bandits to cost-sensitive ERM

Agarwal et al. (2014) give a polynomial-time algorithm with regret about that of Theorem 18.1, using only an ERM oracle. Each round it forms importance-weighted reward estimates, estimates every expert’s regret, and solves a feasibility problem for a sparse distribution over experts whose importance weights stay bounded while its average estimated regret stays small. The distribution is recomputed on an exponentially growing schedule. Any progress on cost-sensitive ERM translates directly into contextual bandits. Earlier attempt: Dudík et al. (2011).

TheoremInfinite policy classes with finite VC dimension (Exercise 18.9)

For stochastic contextual bandits with $k = 2$ and $d = \mathrm{VC}(\Phi)$ , some policy achieves

$R_n\le C\sqrt{ndk\log\frac nd}$

Explore for an initial period, keep one representative from each group of policies that agree on the observed contexts, and run Exp4 on those. Sauer’s lemma bounds the number of representatives by $(em/d)^d$ , so $\log M\approx d\log\frac md$ . Exchangeability of i.i.d. contexts makes the representatives behave like the full class on the remaining rounds. (Beygelzimer et al. 2011.)

RemarkHigh probability and non-oblivious experts

Exp4-IX (Exercise 18.3; Neu 2015): with probability $1-\delta$ , $\hat R_n\le C\big(\sqrt{nk\log M} + \sqrt{\frac{nk}{\log M}}\log\frac1\delta\big)$ , the analogue of Theorem 12.1. Exp3.P generalizes too (Beygelzimer et al. 2011).
Non-oblivious experts (Exercise 18.6): define $R_n' = \max_m\mathbb E\big[\sum_tE^{(t)}_mx_t - \sum_tX_t\big]$ . Then $R_n'\le R_n$ always (the max of expectations is at most the expectation of the max), and Theorem 18.1 holds for $R_n'$ : the proof never needs a deterministic $m^*$ if the comparison expert is fixed before taking expectations. A non-trivial bound on $R_n$ itself is open.
Lower bounds depend on the experts’ structure. They are sometimes tight (examples come later), sometimes not.

RemarkHistory and related settings

Exp4 is due to Auer et al. (2002); Theorem 18.1 matches their result with a slightly smaller constant. McMahan–Streeter (2009) observed that expert agreement, not $M$ or $k$ , is what matters, and optimized the played distribution to stay close to $P_t$ while exploring every expert. Theorem 18.3’s learning-rate-only adaptation appears to be new. Other settings: FTPL with static experts and contexts known upfront (Syrgkanis et al. 2016); i.i.d. contexts with adversarial rewards (Lazaric–Munos 2009; Rakhlin–Sridharan 2016, including approximate oracles); bandit multiclass classification with mistake bounds against convex surrogates (Kakade et al. 2008). Survey: Tewari–Murphy (2017).

Quick reference

Object	Statement	Note
Contextual regret	$\mathbb E\max_{\phi\in\Phi}\sum_t(x_{t\phi(c_t)} - X_t)$	$\Phi$ = all maps gives (18.1)
One Exp3 per context	$2\sum_c\sqrt{k n_c\log k}\le2\sqrt{nk\lvert\mathcal C\rvert\log k}$	needs anytime Exp3
Worst case	uniform context frequencies	Cauchy–Schwarz
Vacuous when	$n\le4k\lvert\mathcal C\rvert\log k$	richer benchmark, larger penalty
Expert advice	rows $E^{(t)}_m\in\mathcal P_{k-1}$ ; regret vs best expert	oblivious experts
Exp4 play	$P_t = Q_tE^{(t)}$	pick an expert, follow it
Exp4 update	$\tilde X_t = E^{(t)}\hat X_t$ ; $Q_{t+1}\propto Q_te^{\eta\tilde X_t}$	loss-based IW estimates
Exp4 regret	$\sqrt{2nk\log M}$ at $\eta = \sqrt{2\log M/(nk)}$	variance term is exactly $k$
Finite $\Phi$	$\sqrt{2nk\log\lvert\Phi\rvert}$	context-space size irrelevant
Agreement	$E_n^* = \sum_t\sum_i\max_mE^{(t)}_{mi}\le n\min(k,M)$	$=n$ if experts agree
Adaptive Exp4	$C\sqrt{E_n^\log M}$ with $\eta_t = \sqrt{\log M/E_t^}$	anytime
Cost	$O(M + k)$ per round	oracles needed for large $M$
Epoch-greedy ETC	$O(n^{2/3}(k\log\lvert\Phi\rvert)^{1/3})$	stochastic, oracle-efficient
VC classes	$C\sqrt{ndk\log(n/d)}$	Sauer’s lemma + Exp4
Finite memory	$\sqrt{2knO^m\log k}$	experts on the last $m$ observations

Facts to keep to hand

The competitor class is a modelling choice. Bigger classes mean more meaningful regret and larger regret: per-context learning pays $\sqrt{|\mathcal C|}$ , and is vacuous until $n\gg k|\mathcal C|\log k$ .
Score experts, not arms. Exp4 importance-weights the arms, credits each expert through its advice, and runs exponential weights over experts. Its variance term stays $k$ per round, so the number of experts costs only $\log M$ .
Statistics is cheap; computation is not. $\sqrt{nk\log|\Phi|}$ is achievable for any finite (or finite-VC) policy class, but naive Exp4 is linear in $|\Phi|$ . Oracle-based reductions to cost-sensitive ERM are the practical route.
Agreement among experts is what makes learning hard or easy. The effective number of experts $E_n^*/n$ , captured by a time-varying learning rate, interpolates between full-information-like and bandit-like regret.

References

Lattimore & Szepesvári, Bandit Algorithms — Part V introduction; Chapter 18
Shalev-Shwartz & Ben-David, Understanding Machine Learning (2014) — VC dimension, Sauer’s lemma, hardness of ERM

Related