Contextual bandit

On this page 7

A contextual bandit is a sequential decision problem in which an agent observes a context, chooses one action from a fixed set and then receives a reward only for the chosen action. In reinforcement learning, it sits between the classic multi-armed bandit, which ignores context, and the full Markov decision process, in which actions also change future states.

The goal is to learn a policy that maps contexts to actions so that cumulative reward is as high as possible, or equivalently so that regret against the best policy in hindsight stays low. Because feedback is partial, the agent must balance exploration and exploitation on every decision, which is what separates contextual bandits from ordinary supervised learning.

How the contextual bandit loop works

Each round of a contextual bandit follows the same observe, act, learn cycle. The environment draws a context, the policy selects an action, and the environment reveals the reward for that single action while the rewards of all other actions remain unknown.

  1. Observe context: a feature vector describing the user, item, device or situation.
  2. Select an action: one arm from the action set, often chosen stochastically.
  3. Log the propensity: record the probability with which the policy picked that action.
  4. Receive reward: a click, a purchase, a dwell time or another scalar signal.
  5. Update the model: refine reward estimates or the policy for future contexts.

The defining assumption is that actions do not influence future contexts. The next user arrives regardless of what the previous user was shown, so there is no state transition and no credit assignment problem across time steps. This simplification makes contextual bandits far more sample-efficient and stable than full reinforcement learning in the settings where the assumption holds.

Contextual bandits are best understood as one rung on a ladder of decision problems, each adding information or complexity. The table below positions the setting against its neighbors.

ProblemUses contextFeedbackActions affect future
Multi-armed banditNoReward of chosen arm onlyNo
Contextual banditYesReward of chosen arm onlyNo
Supervised learningYesCorrect label for every exampleNo
Markov decision processYes, as stateReward of chosen actionYes, through state transitions
Where the contextual bandit sits among decision problems

The comparison with supervised learning is the most instructive. A classifier is told the correct answer for every example, while a contextual bandit only learns how good its own choice was, a situation known as bandit feedback. Training a classifier on logged clicks therefore introduces selection bias, because the data reflects what the old policy chose to show.

Main contextual bandit algorithms

Contextual bandit algorithms differ mainly in how they drive exploration. Most of them pair a reward model, such as linear regression or a neural network, with an exploration rule borrowed from classic bandits.

AlgorithmExploration strategyStrengthWeakness
Epsilon-greedyRandom action with probability epsilonSimple, works with any modelExplores blindly, wastes traffic
LinUCBUpper confidence bound on a linear modelStrong regret guaranteesAssumes linear rewards
Linear Thompson samplingSamples model weights from a posteriorEfficient, naturally randomizedNeeds a calibrated posterior
Neural banditsUCB or sampling on network featuresCaptures nonlinear effectsUncertainty is hard to estimate
Policy-based methodsOptimize a stochastic policy over contextsReduce to classification oraclesMore complex to implement
Common algorithm families and their exploration strategies

With well-chosen exploration, regret grows roughly with the square root of the number of rounds, which means the average loss per decision shrinks toward zero. Naive strategies that never explore can suffer linear regret, repeating the same mistake indefinitely.

Off-policy evaluation and logged data

Off-policy evaluation estimates how a new policy would perform using data collected by an older policy, without exposing real users to it. This capability is one of the main practical advantages of contextual bandits, but it depends on having logged action probabilities, known as propensities.

EstimatorHow it worksTypical trade-off
Direct methodPredicts rewards with a regression modelLow variance, biased if the model is wrong
Inverse propensity scoringReweights observed rewards by 1 divided by propensityUnbiased, high variance
Doubly robustCombines the model with propensity correctionLower variance, unbiased if either part is right
Self-normalized IPSNormalizes the importance weightsSmall bias, much more stable
Estimators for evaluating a policy on logged bandit data

Evaluation only works for actions the logging policy actually tried with nonzero probability. A deterministic production policy that never explored leaves gaps that no estimator can fill, so teams that plan to iterate should keep a small amount of randomization in every deployed policy.

When to use contextual bandits and common pitfalls

Contextual bandits fit problems with many repeated, independent decisions and fast feedback. Typical applications include news and product recommendation, ad selection, notification timing, pricing experiments and adaptive clinical or educational interventions.

SituationRecommended approachReason
Few variants, one-time decisionA/B testClean causal estimate, simple analysis
Many variants, personalized responseContextual banditAdapts per context and reduces regret
Choices shape later statesFull reinforcement learningBandits ignore long-term effects
Only historical logs availableOff-policy learningLearn without new live exploration
Choosing between bandits, A/B tests and full reinforcement learning
  • Delayed rewards such as purchases days after a click weaken learning and need careful attribution windows.
  • Short-term proxy rewards such as clicks can reward clickbait; align the reward with the real objective.
  • Non-stationarity in user behavior requires decaying old data or periodic retraining.
  • Missing propensities in logs make reliable off-policy evaluation impossible.
  • Ignoring feedback loops across sessions can hide long-term harm that only full reinforcement learning would model.

The short version

Picture a waiter who greets each new guest, glances at them and suggests one dish. The waiter only learns whether that guest liked the suggested dish, never how the other dishes would have gone over. Over many guests, the waiter learns which dishes suit which kinds of people, while still occasionally trying something new to avoid missing a better option.

That is a contextual bandit: look at the situation, make one choice, learn from the single result and gradually get better at matching choices to situations.

Where it makes a difference

A news application must choose one of 20 headline stories for the top slot each time a reader opens it. The context includes the time of day, the device type, the reader’s region and topic interests inferred from recent sessions, and the reward is whether the reader opens the story within the session.

The team deploys linear Thompson sampling and logs the probability of every choice. Within a few days, the policy learns that morning commuters on phones prefer short local updates while evening tablet readers open long features, and it shifts traffic toward the best story for each context instead of showing one global winner.

Because propensities were logged, the analysts later use a doubly robust estimator to test a new reward model offline before release. The offline estimate guides which candidate reaches live traffic, so experiments become faster and safer than repeated fixed-split A/B tests.