Contextual Bandits

A contextual bandit is a sequential decision algorithm that, on each round, observes some context (features of a user or situation), chooses one action from a set, and sees the reward for that action only. It then updates its policy so that future choices earn more. The name extends the multi-armed bandit, a row of slot machines with unknown payouts, by letting the best arm depend on who is pulling it. Contextual bandits are the standard tool for personalised choices with fast feedback: which article, offer, message or price variant to show to which person. They sit between a fixed A/B test, which learns one answer for everybody, and full reinforcement learning, which also models how today's action changes tomorrow's state.

The Problem: Partial Feedback

In supervised learning every example comes with the right answer. A bandit sees only the outcome of what it chose; it never learns what would have happened under the alternatives. That creates the explore/exploit trade-off. A policy that always takes the action it currently believes is best never gathers evidence about the others, and can lock in an early mistake. A policy that explores too much wastes traffic on options it already knows are poor. Performance is measured as regret: the reward lost relative to always playing the best action for each context.

Core Algorithms

Epsilon-greedy takes the best-looking action most of the time and a uniformly random one with small probability. It is crude but simple.

LinUCB (Li, Chu, Langford and Schapire, WWW 2010) models each action's expected reward as a linear function of the context and adds an upper-confidence bonus that is large where the model has seen little data, so uncertain options are tried because they might be good. In the original paper, on about 33 million events from a news-recommendation log, it achieved a 12.5% click lift over a context-free bandit, with a larger advantage when data was scarce.

Thompson sampling keeps a posterior distribution over each action's reward model, draws one sample from it, and acts greedily on the sample. Exploration comes from posterior uncertainty and fades as data accumulates. Chapelle and Li (NeurIPS 2011) showed it was competitive with the alternatives of the time and argued that it belonged among the standard baselines; Agrawal and Goyal (2012) later proved a regret bound of order d^3/2√T for the linear case, within a √d factor of the lower bound.

Modern systems often replace the linear model with boosted trees or neural networks and reduce the bandit to repeated supervised learning. An empirical "bake-off" by Bietti, Agarwal and Langford (JMLR, 2021) found that an optimism-based method did best overall, and that a purely greedy policy came a surprisingly close second when contexts were diverse enough to provide exploration for free. That result comes from supervised datasets converted to bandit problems, so it is suggestive only.

Relation to A/B Testing and Reinforcement Learning

	A/B test	Contextual bandit	Full reinforcement learning
Allocation	Fixed split for the test's duration	Adapts continuously	Adapts continuously
Uses context	No (one winner overall)	Yes (a winner per context)	Yes
Models long-term effects of actions	No	No; each round is treated as independent	Yes; states and delayed rewards
Main output	A statistically clean estimate of an effect	A policy that earns reward while learning	A policy for sequences of decisions

An A/B test is designed for inference: whether a change works and by how much. A bandit is designed for optimisation: losing as little as possible while finding out. Because a bandit shifts traffic toward winners, its data is not uniformly randomised and naive averages from it are biased. The comparison is developed in Contextual Bandits vs A/B Testing.

Off-Policy Evaluation

A valuable property of bandits is that a new policy can be assessed on logs collected by an old one, without exposing users to it, provided the old policy randomised and recorded the probability of each choice. Li et al. (WSDM 2011) introduced a replay method that is provably unbiased when logged actions were chosen uniformly at random. Inverse propensity scoring generalises it to non-uniform logging by reweighting each record by one over its logged probability, at the cost of high variance. The doubly robust estimator (Dudík, Langford and Li, ICML 2011) combines a reward model with propensity weights and is accurate if either one is good. The Open Bandit Dataset and Pipeline (Saito et al., NeurIPS 2021) made real logged bandit data and standard estimators public. The practical corollary is to log, for every decision, the context, action, reward and action probability; the Vowpal Wabbit library encodes exactly that as action:cost:probability | features.

Typical Uses and Pitfalls

Common applications are content recommendation, personalisation of layouts and messages, choice among promotional offers, and creative selection in advertising.

• Delayed or proxy rewards. Optimising clicks is easy; optimising retention or revenue weeks later is not. A bandit trained on a short-term proxy will maximise the proxy.
• Missing propensities. Without logged action probabilities, off-policy evaluation is impossible and the logs are confounded.
• No exploration floor. If some action's probability falls to zero for a segment, the system can never discover that conditions changed.
• Interference and carry-over. If today's offer changes next week's behaviour, the independence assumption fails and the problem is really reinforcement learning.
• Delegating exploration to a language model. There is early evidence that LLM agents explore poorly when left to do it implicitly: Choi et al. (July 2026) report "myopic and polarized interaction patterns" when agents must probe one another's capabilities. That is one study in a multi-agent setting, but it supports the cautious design in which a language model proposes candidate actions and an explicit bandit allocates traffic among them.