Multi-Armed Bandit Problem

Exploration-exploitation tradeoff, regret formulation, stochastic vs adversarial MAB

A/B testing commits samples to both arms for the full experiment duration, even if one arm is clearly losing early. In online settings — recommending ads, articles, treatments — every suboptimal recommendation has a real cost. Multi-armed bandits formalise the exploration-exploitation tradeoff: you must try options to learn their value (explore), but you want to choose the best option as often as possible (exploit). Doing both simultaneously is the core challenge.

Regret — the accumulated cost of not always choosing the best arm — is the right metric for this problem, not reward prediction accuracy: a reward model that is accurate wherever it has enough data can still incur linear regret under a greedy policy, because its early, noisy estimates on rarely-tried arms can underestimate the best arm, and greedy selection never explores enough to correct that and discover the better arm. The Lai-Robbins lower bound (Ω(log T)) is the key theoretical anchor: any consistent algorithm must pull suboptimal arms at a rate proportional to log T divided by the KL divergence between arm distributions. You cannot beat log T; you can only match it.

Key points

• Regret is the right metric, not reward accuracy. Pseudo-regret $R_T = T·μ* − Σ_t μ_{a_t} measures the cumulative gap betwe$ en the optimal arm's expected reward and your policy's expected rewards. A model whose reward estimates are accurate wherever it has enough data, but that selects greedily, has zero exploration. If its early, noisy estimates on a rarely-tried arm happen to underestimate that arm's true value, it never corrects and incurs linear regret O(T) — accuracy on well-sampled arms says nothing about decision quality, which is permanently compromised for arms the policy stopped trying.
• **Pseudo-regret decomposes as $R_T = Σ_{a≠a*} Δ_a · E[N_a(T)] where Δ_a = μ* − μ_a is the suboptimality gap for arm a an$ d N_a(T) is the number of times you pull it.** Minimising regret means minimising pulls on suboptimal arms — but identifying which arms are suboptimal requires the exploration you are trying to limit. This is the circular dependency that makes the problem hard. Pseudo-regret compares to the best arm's true mean μ* using its expected reward, so it averages only over the algorithm's action-selection randomness and the noise in individual reward draws cancels out; the raw (unaveraged) regret instead compares against the realized reward sequence itself, so as a random variable it also carries that reward noise — but once you take its expectation, E[regret] equals pseudo-regret exactly, since E[X_t] = μ_{a_t}. Pseudo-regret is the lower-variance, more tractable quantity to analyze, and it's what nearly all bandit regret bounds — including the Lai-Robbins bound below — actually establish.
• Lai-Robbins lower bound (1985): for any consistent algorithm (sub-polynomial regret on every instance), expected regret satisfies E[R_T] ≥ Σ_{a: Δ_a > 0} Δ_a / KL(μ_a, μ*) · ln T. This is Ω(log T) and cannot be beaten asymptotically. Algorithms achieving O(log T) regret are optimal. The KL term tells you why near-optimal arms are expensive: if two arms are very similar (small KL), you need many pulls to distinguish them, and each suboptimal pull costs Δ_a.
• Instance regret vs minimax regret are different goals. UCB-type algorithms achieve O(log T) on specific instances but O(√(KT log T)) in the worst case — the matching √(KT) lower-bound rate (no log factor) is only attained by specially-tuned variants like MOSS, not generic UCB. EXP3 achieves O(√(KT ln K)) in the fully adversarial setting without any distributional assumptions. An algorithm optimal for T = 10^6 may underperform at T = 1000 — asymptotic optimality says nothing about finite-horizon performance where prior warm-starting and instance-specific constants dominate.
• Stochastic MAB assumes rewards are i.i.d. from fixed but unknown distributions. The optimal arm is fixed. Most recommendation and ad-serving problems are approximately stochastic over short windows. UCB and Thompson Sampling are designed for this setting and achieve O(log T) regret.
• Adversarial MAB removes all distributional assumptions — the environment can choose reward sequences after seeing your algorithm (but not your random coin flips). Relevant for strategic actors, financial markets, and settings where the reward distribution shifts in response to your policy. EXP3 is the algorithm for this setting.
• Production applications: online ad serving (each ad is an arm, reward is click/conversion, up to tens of millions of arms), recommendation ranking (which item at position 1, with delayed feedback), clinical trials (adaptive randomisation toward better treatments — regulated trials require pre-registered stopping rules, statistically corrected inference after adaptive sampling, careful handling of delayed outcomes, and checking SUTVA — the assumption that one patient's treatment assignment doesn't affect another's outcome, which contagion or shared-resource effects can violate), and hyperparameter tuning (Hyperband allocates compute budget across configurations).
• Finite horizon matters. Most theory is asymptotic (T → ∞) and instance-dependent factors (Δ values, K) dominate at realistic horizons. In production, content has short lifecycles — an article is relevant for hours. At T = 1000 and K = 20, priors and warm-start heuristics matter more than matching the Lai-Robbins asymptotic constant.

Recap

• Explore vs exploit: try arms to learn value, pick the best as often as possible — do both at once.
• Regret, not reward accuracy: greedy on a perfect reward model still incurs linear O(T) regret if it never explores.
• Pseudo-regret decomposes: $R_T = Σ_{a≠a*} Δ_a · E[N_a(T)]$ — minimise pulls on suboptimal arms.
• Lai-Robbins lower bound Ω(log T): any consistent algorithm pulls suboptimal arms ∝ ln T / KL(μ_a, μ*).
• KL term = cost of near-optimal arms: small gap → many pulls to distinguish.
• Stochastic vs adversarial: i.i.d. fixed distributions (UCB/TS, O(log T)) vs no assumptions (EXP3, O(√(KT ln K))).
• Finite horizon matters: theory is asymptotic; at T=1000, K=20, priors and warm-starts dominate the constant.

Check your understanding