Multi-Armed Bandits and Online Learning – Explore-Exploit, UCB and Thompson Sampling

Every decision-making system that learns from feedback faces the explore-exploit dilemma: should you exploit what you already know works, or explore alternatives that might be better? A recommendation system that only shows users content they have engaged with before will never discover new content they might prefer. A clinical trial that always assigns patients to the treatment that looks best so far wastes resources on suboptimal treatments for patients enrolled early. An ad auction that only bids on placements with known high click-through rates misses placements that might be even better. The multi-armed bandit is the mathematical framework for navigating this tradeoff optimally. Unlike pure reinforcement learning, which models sequential decision-making with delayed rewards and state transitions, bandits address the simpler but ubiquitous setting where each action produces an immediate reward and no state transition — the world is stateless, only the reward distributions matter. This guide covers the complete bandit toolkit: epsilon-greedy, UCB, Thompson Sampling, contextual bandits (LinUCB), and online learning methods for streaming model updates.

Regret, Exploration Strategies and Basic Algorithms

The formal bandit problem: K arms, each with an unknown reward distribution with mean μ_k. At each time step t, the agent pulls arm a_t and observes reward r_t ~ P(r | a_t). The cumulative regret R_T = T × μ* − Σ_{t=1}^T μ_{a_t} measures the total reward lost by not always pulling the optimal arm μ* = max_k μ_k. Minimising regret is the objective: algorithms that achieve O(log T) regret are said to be asymptotically optimal (proved by Lai and Robbins, 1985).

Epsilon-greedy is the simplest exploration strategy: with probability ε, pull a random arm (explore); with probability 1-ε, pull the arm with the highest estimated mean (exploit). Despite its simplicity, epsilon-greedy achieves O(log T) regret with the optimal ε schedule (ε_t = min(1, K/(d²t)) for some d). The main drawback is that it explores uniformly — it is equally likely to explore the arm that has been pulled 5 times and the arm that has been pulled 500 times — wasting exploration budget on well-characterised arms. Standard A/B testing is epsilon-greedy with ε = 0.5 (50% traffic to each variant), which is optimal for hypothesis testing but suboptimal for regret minimisation because it never increases allocation to the better-performing variant during the test.

Upper Confidence Bound (UCB1) eliminates this waste by being optimistic: pull the arm with the highest optimistic estimate of the mean, where the optimism is quantified by the confidence interval width. UCB1 selects arm a_t = argmax_k [x̄_k + sqrt(2 log t / n_k)], where x̄_k is the empirical mean and n_k is the pull count. The UCB term sqrt(2 log t / n_k) is large for rarely-pulled arms (small n_k) and small for frequently-pulled arms — exactly the right exploration incentive. UCB1 achieves O(K log T) regret deterministically (not in expectation), with no randomness in the exploration strategy. The connection to confidence interval construction is direct: UCB uses the same Chernoff-Hoeffding concentration inequality that forms the foundation of conformal prediction.

Thompson Sampling — Bayesian Bandits

Thompson Sampling (Thompson, 1933; rediscovered 2010s) maintains a Bayesian posterior over the reward parameter of each arm and selects arms by posterior sampling: sample θ_k from the posterior P(θ_k | data) for each arm k, then pull the arm with the highest sample. For Bernoulli rewards (binary: click/no-click, conversion/no-conversion), the conjugate prior is Beta(α_k, β_k) where α_k counts successes and β_k counts failures. The update rule is simply: on arm k producing reward r ∈ {0,1}, increment α_k by r and β_k by 1-r. Pulling the arm with the highest sample from Beta(α_k, β_k) across arms is Thompson Sampling for Bernoulli bandits — implementable in three lines of numpy code. For Gaussian rewards, the conjugate normal-inverse-gamma prior gives closed-form posterior updates. For complex reward functions, approximate posterior sampling via MCMC or variational inference is used.

Thompson Sampling is the Bayesian analogue of UCB: UCB explores based on frequentist confidence intervals; TS explores based on Bayesian posterior uncertainty. Empirically, TS consistently outperforms UCB in A/B testing and recommendation system evaluations, often by a significant margin on real-world data. The Bayesian statistics intuition is clear: a Beta(1,1) prior (uniform, complete uncertainty) covers the full [0,1] range for a new arm, ensuring it is explored; as data accumulates, the posterior sharpens around the true success rate, and high-performing arms are sampled more frequently. Thompson Sampling is the algorithm used by Google, Microsoft, and Meta for large-scale content and ad personalisation, scaled to millions of arms via approximate inference and batched updates.

Contextual Bandits and Online Learning

Standard bandits ignore context: the same exploration strategy is applied regardless of who the user is, what time it is, or what the recent interaction history shows. Contextual bandits extend bandits to settings where a feature vector x_t is observed before choosing an arm, and the expected reward depends on both the arm and the context: E[r | a, x]. This is the natural model for personalised recommendation (context = user features, arm = item to recommend), dynamic pricing (context = demand features, arm = price), and clinical trial adaptive allocation (context = patient features, arm = treatment). The connection to our recommendation systems guide is direct: a contextual bandit is a recommendation system with explicit exploration — unlike supervised recommendation models trained on historical data, contextual bandits continuously explore and update.

LinUCB assumes a linear reward model E[r | a, x] = x^T θ_a for each arm a, with a ridge regression posterior over θ_a that is updated with each observation. The UCB is the mean prediction plus a confidence ellipsoid term: UCB_a(x) = x^T θ̂_a + α sqrt(x^T A_a^{-1} x), where A_a is the design matrix and α controls exploration width. LinUCB is the dominant contextual bandit algorithm in industrial recommendation systems due to its closed-form updates (no MCMC), O(d³) update cost, and interpretability — the θ_a weights are the feature importance coefficients, directly interpretable by product teams. The connection to experimental design is deep: the A_a^{-1} matrix is the information matrix, and LinUCB’s UCB term is the D-optimal experimental design criterion — it explores directions in feature space where the reward function is most uncertain.

Online learning is the broader paradigm of updating a model with each arriving example rather than periodically retraining on the full history. Follow-The-Regularised-Leader (FTRL) with L1 regularisation (the algorithm behind Google’s Logistic Regression serving billions of ad predictions per day) achieves online learning at industrial scale: O(sqrt(T)) regret for convex losses, sparse solutions due to L1, and O(d) update cost per example. Vowpal Wabbit is the reference implementation of FTRL and related online learning algorithms. The streaming data infrastructure required for online learning — Kafka for event ingestion, Flink for real-time feature computation — is covered in our Big Data Technologies guide, and the feature engineering for contextual bandit inputs is covered in our Feature Engineering guide.

✦ SUMMARIZE THIS ARTICLE WITH AI

ChatGPT Perplexity Claude Grok

A/B testing as the fixed-allocation special case of bandits — and when to prefer each — is in our A/B Testing guide. Reinforcement learning, of which bandits are the stateless special case, is in our Reinforcement Learning guide and RLHF guide. Recommendation systems that contextual bandits power — collaborative filtering, matrix factorisation — are in our Recommendation Systems guide. The Bayesian posterior update mechanism central to Thompson Sampling is in our Bayesian Statistics guide. Experimental design and power analysis for bandit-vs-A/B decisions are in our Experiment Design guide.