Adversarial Bandits and EXP3

A bidding agent chooses among ten bid-shading strategies in an auction where competitors adjust to whatever it did yesterday. A UCB learner, which assumes each arm has a fixed mean, is a sitting target: its choice next round is a deterministic function of the history, so an opponent who can reconstruct that history knows exactly which arm it will pull and can make that arm pay nothing. Against any deterministic algorithm, some reward sequence forces regret linear in \(T\). The escape is randomisation, and EXP3 is the canonical way to do it.

This concept picks up where regret and the exploration-exploitation tradeoff and UCB leave off, by dropping their stochastic assumption. The full-information version of the problem, where every expert's reward is revealed each round, is handled by multiplicative weights and covered in online learning and regret bounds. The bandit version reveals only the reward of the arm you pulled.

The setting and the algorithm

There are \(K\) arms and \(T\) rounds. Before play, an oblivious adversary fixes rewards \(x_i(t) \in [0,1]\) for every arm and round. At round \(t\) the learner samples arm \(i_t\) from a distribution \(p(t)\) and observes only \(x_{i_t}(t)\). With \(G_i = \sum_t x_i(t)\) and \(G_{\max} = \max_i G_i\), performance is measured by weak regret against the best single arm in hindsight, \(G_{\max} - \mathbb{E}[G_{\text{Exp3}}]\).

EXP3, from Auer, Cesa-Bianchi, Freund and Schapire, keeps a weight \(w_i(t)\) per arm, initialised to 1 (Auer et al., 2002, The Nonstochastic Multiarmed Bandit Problem, SIAM Journal on Computing 32(1)). Each round, with mixing parameter \(\gamma \in (0,1]\):

Two ideas carry the design. The importance-weighted estimate \(\hat{x}_j(t)\) is unbiased, \(\mathbb{E}[\hat{x}_j(t)] = p_j(t)\cdot x_j(t)/p_j(t) = x_j(t)\), so the unobserved arms are credited correctly in expectation. The uniform mixture guarantees \(p_j(t) \ge \gamma/K\), which caps every estimate at \(K/\gamma\) and keeps the exponential update from exploding.

The regret bound, sketched

Auer et al. prove that for any reward assignment,

The proof tracks the log of total weight \(W_t = \sum_i w_i(t)\) from two directions. From below, \(\ln(W_{T+1}/W_1) \ge \frac{\gamma}{K}\sum_t \hat{x}_j(t) - \ln K\) for any arm \(j\), since one weight is at most the total. From above, each round's ratio \(W_{t+1}/W_t\) is bounded using \(e^{u} \le 1 + u + (e-2)u^2\) for \(u \le 1\), which is valid because \(\gamma\hat{x}/K \le 1\). The linear term collapses to the observed reward, \(\sum_i p_i \hat{x}_i = x_{i_t}\), and the quadratic term is at most \(\sum_i \hat{x}_i\), whose expectation summed over time is at most \(K G_{\max}\). Chaining the two inequalities and taking expectations gives the bound.

The first term is the price of exploring uniformly; the second is the price of not exploring enough. Balancing them with \(\gamma = \min\{1, \sqrt{K\ln K/((e-1)g)}\}\) for any \(g \ge G_{\max}\) gives \(2\sqrt{e-1}\sqrt{gK\ln K} \le 2.63\sqrt{gK\ln K}\).

A concrete case: \(K = 10\), \(T = 100{,}000\), and \(g = T\). Then \(\gamma \approx \sqrt{23.03/171{,}828} \approx 0.0116\), and the bound is \(2.63\sqrt{10^5 \cdot 10 \cdot 2.303} \approx 3{,}990\), about 0.04 reward per round lost to the best fixed arm, against an adversary. Auer et al. also proved a lower bound of \(\Omega(\sqrt{KT})\) for any algorithm, leaving a \(\sqrt{\ln K}\) gap that later work closed (Bubeck & Cesa-Bianchi, 2012, Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems, arXiv:1204.5721).

Robustness versus adaptivity

The tradeoff is sharp. In a genuinely stochastic environment UCB and Thompson sampling achieve regret logarithmic in \(T\) for fixed gaps, while EXP3's guarantee is \(\sqrt{T}\). Paying \(\sqrt{T}\) for insurance you did not need is a real cost, and the choice between the two families depends on a question you usually cannot answer in advance: is anything reacting to you? Research on algorithms that achieve near-optimal rates in both regimes at once exists precisely because practitioners rarely know.

There is also disagreement about whether expected regret is the right target. EXP3's importance weights have variance of order \(1/p_i\), so a single run can deviate far from its expectation. Neu showed that biasing the estimator slightly, adding implicit exploration to the denominator, yields high-probability bounds without the explicit uniform mixture (Neu, 2015, Explore no more: Improved high-probability regret bounds for non-stochastic bandits, NeurIPS, arXiv:1506.03271). An operator who runs the system once cares about the tail, not the mean.

When it breaks

Adaptive adversaries change the benchmark. The bound compares against the best fixed arm on the reward sequence that actually occurred. If the environment reacts to your choices, the rewards a fixed arm would have earned are different, and low weak regret can coexist with poor performance. Policy regret is the notion that captures this, and it is much harder to bound.

The best fixed arm may be a weak comparator. When the best arm changes over time, beating the single best arm in hindsight is a low bar. Tracking a shifting best arm needs variants that forget, such as weight sharing or restarts.

Tuning needs the horizon. The optimal \(\gamma\) depends on \(g\), an upper bound on \(G_{\max}\). Without a known horizon, a doubling trick or a decreasing schedule is required, and each costs a constant factor.

Rewards must be bounded and scaled. Everything relies on \(x \in [0,1]\). Unbounded or heavy-tailed rewards, such as revenue per impression, break the exponent bound, and clipping silently changes the objective.