Contextual Bandits

Contextual bandits extend multi-armed bandits by using features available at decision time. A stateless bandit asks, “Which arm is best on average?” A contextual bandit asks, “Which arm is best for this user, request, and situation?”

The bandit part remains the same: after choosing an action, the system observes reward only for the action it showed. The contextual part changes the decision rule: user segment, device, query, location, time, item age, price, or content embeddings can all influence the exploration decision. This is the bridge between simple bandit algorithms and personalized recommendation.

Decision loop

At round $t$ , a contextual bandit:

observes context $x_{t}$ before choosing;
builds the eligible action set $A_{t}$ ;
scores each action $a \in A_{t}$ using reward estimates and uncertainty;
chooses one action $a_{t}$ ;
observes reward $r_{t}$ only for $a_{t}$ ;
logs the context, action, reward, policy version, and propensity when available.

A contextual bandit observes user and request features, scores only eligible candidate arms, serves one arm, observes only that arm's reward, and updates the policy state.

The diagram emphasizes two boundaries. Eligibility filtering happens before exploration, so the policy never explores unavailable or unsafe items. Logging happens after serving, because future offline versus online evaluation needs to know what context was visible, which action was eligible, which action was chosen, and what reward was observed.

Formal setup

Let $x_{t}$ be the context vector at round $t$ , $A_{t}$ the eligible arms, $a_{t}$ the chosen arm, and $r_{t}$ the observed reward. A contextual policy estimates the conditional reward:

E [r_{t} ∣ x_{t}, a] .

The goal is not to learn one global $μ_{a}$ per arm, as in the stateless page. The goal is to learn which arm works for which contexts while still handling partial feedback. For example, a finance article may perform well for desktop users reading market news, while a weather alert may perform well for mobile users in the morning.

Feature family	Examples	Risk
User features	segment, locale, tenure, subscription tier	privacy, stale profiles, sensitive proxies
Request features	query, device, hour, surface, referrer	seasonality and traffic shifts
Item features	topic, freshness, price, creator, embedding	leakage if computed after exposure
Policy features	eligibility, inventory, fatigue state	accidental exploration of ineligible items

Only use features known before the recommendation is shown. Post-click features, later conversions, updated popularity, or downstream rank positions leak information from the future and make evaluation invalid.

LinUCB

LinUCB is a common contextual bandit for continuous feature vectors. It assumes each arm has an approximately linear reward model:

E [r ∣ x, a] \approx x^{⊤} θ_{a} .

Here $x$ is the feature vector visible before serving the recommendation, $a$ is an arm, $r$ is the reward, and $θ_{a}$ is the unknown coefficient vector for arm $a$ . If $x$ has $d$ features, then $θ_{a}$ also has $d$ entries. A common choice is to include an intercept feature, so the first coordinate of $x$ is always $1$ .

For each arm $a$ , LinUCB maintains a matrix $A_{a}$ and vector $b_{a}$ from past observations where that arm was chosen. With regularization strength $λ > 0$ , initialize:

A_{a} \leftarrow λ I_{d}

b_{a} \leftarrow 0_{d}

for every arm $a$ . Here $I_{d}$ is the $d \times d$ identity matrix and $0_{d}$ is the $d$ -dimensional zero vector. This initialization is the ridge-regression prior: before seeing data for an arm, the estimated coefficients are zero, but $A_{a}$ is invertible. In practice, $λ = 1$ is a common starting point; larger values make early estimates more conservative.

After several observations for arm $a$ , the estimate is:

\hat{θ}_{a} = A_{a}^{- 1} b_{a} .

This is the same shape as a ridge linear-regression solution. If arm $a$ has been chosen on contexts $x_{1}, \dots, x_{m}$ with rewards $r_{1}, \dots, r_{m}$ , then:

A_{a} = λ I_{d} + i = 1 \sum m x_{i} x_{i}^{⊤}

b_{a} = i = 1 \sum m r_{i} x_{i} .

The matrix $A_{a}$ records where the algorithm has evidence for this arm. Repeatedly showing arm $a$ to users with similar feature vectors makes $A_{a}$ large in that feature direction. The vector $b_{a}$ records reward-weighted evidence: contexts that produced higher rewards pull $\hat{θ}_{a}$ toward predicting higher rewards for similar contexts.

For the current context $x_{t}$ , it chooses

a_{t} = ar g a \in A_{t} max (x_{t}^{⊤} \hat{θ}_{a} + α x_{t}^{⊤} A_{a}^{- 1} x_{t}) .

The first term, $x_{t}^{⊤} \hat{θ}_{a}$ , is exploitation. It is the predicted reward under the current fitted linear model for arm $a$ . If this term is high, the arm looks good based on observed rewards in similar contexts.

The second term, $α x_{t}^{⊤} A_{a}^{- 1} x_{t}$ , is exploration. The quantity inside the square root is large when the current context points in a direction where arm $a$ has little data. It is small when the algorithm has already shown arm $a$ many times in similar contexts. Geometrically, $A_{a}^{- 1}$ describes the remaining uncertainty in the coefficient estimate, and $x_{t}^{⊤} A_{a}^{- 1} x_{t}$ projects that uncertainty onto the specific context being served now.

This is why LinUCB can choose an arm with a lower predicted reward: the upper confidence score asks, “How good could this arm plausibly be, given what we still do not know?” The parameter $α$ controls how much uncertainty is rewarded. Larger $α$ explores more aggressively; smaller $α$ behaves more greedily. Setting $α = 0$ turns the policy into a greedy contextual linear model.

After observing reward $r_{t}$ for the chosen arm $a_{t}$ , the policy updates only that arm:

A_{a_{t}} \leftarrow A_{a_{t}} + x_{t} x_{t}^{⊤}

b_{a_{t}} \leftarrow b_{a_{t}} + r_{t} x_{t} .

The unchosen arms are not updated, because their rewards were not observed. That partial-feedback discipline is the reason contextual bandits need different evaluation from ordinary supervised ranking.

An implementation usually stores one d x d matrix and one d-vector per arm:

State variable	Initialization	Update after choosing arm $a_{t}$	Interpretation
$A_{a}$	$λ I_{d}$	add $x_{t} x_{t}^{⊤}$ only to $A_{a_{t}}$	feature directions where this arm has been observed
$b_{a}$	$0_{d}$	add $r_{t} x_{t}$ only to $b_{a_{t}}$	reward-weighted evidence for this arm
$\hat{θ}_{a}$	$A_{a}^{- 1} b_{a} = 0_{d}$	recompute or solve $A_{a} \hat{θ}_{a} = b_{a}$	fitted reward coefficients for this arm
uncertainty	$x_{t}^{⊤} A_{a}^{- 1} x_{t}$	shrinks in observed directions	context-specific reason to explore

Worked example

Suppose a news homepage can choose one module for a returning user. The current context is:

Feature	Value
intercept	1.0
market-news interest	0.7
morning mobile session	1.0

The eligible arms are:

Arm	Module
A	market briefing
B	personal finance tips
C	local weather alert

A LinUCB policy evaluates each arm for this context:

Arm	Predicted reward $x^{⊤} \hat{θ}_{a}$	Uncertainty bonus	LinUCB score	Interpretation
A	0.071	0.018	0.089	good match to market interest, enough history
B	0.062	0.034	0.096	weaker prediction, but less certainty
C	0.055	0.052	0.107	uncertain in this context, so it gets explored

The policy chooses C even though A has the highest predicted reward. That is not random noise: C has enough plausible upside for this user context that the exploration bonus makes it worth trying. If C gets a click, the model updates C’s parameters toward this context. If C does not get a click, the uncertainty for similar contexts shrinks and future scores fall.

This is different from a non-contextual UCB policy. A stateless bandit would see only arm-level click rates. LinUCB can learn that weather alerts may be weak on average but strong for morning mobile sessions, while market briefings may be strong for market-news readers.

Algorithm families

Family	Decision idea	Typical use
Contextual epsilon-greedy	train a reward model, usually choose the best predicted arm, sometimes explore randomly	simple deployments with bounded randomization
LinUCB	choose predicted reward plus a context-specific uncertainty bonus	small or medium arm sets with numeric features
Linear Thompson sampling	sample plausible model parameters, then choose the arm with the largest sampled reward	binary or continuous rewards with Bayesian uncertainty
Logistic contextual bandit	model click probability through a logistic reward model	binary click or conversion rewards
Neural contextual bandit	use a neural model for reward prediction plus an uncertainty or exploration layer	high-dimensional text, image, or embedding features

The more flexible the model, the harder the uncertainty estimate becomes. A strong reward model without reliable exploration can become a greedy ranker with biased logs.

Logging and evaluation

Contextual bandit logs should include:

request context features or stable feature IDs;
eligible actions after filtering;
chosen action;
observed reward and reward timestamp;
policy version and model version;
action probability or propensity when the policy is randomized;
position, surface, and guardrail decisions that affected exposure.

This logging makes replay, inverse-propensity scoring, and online experiments possible. Without propensities or randomized traffic, historical logs mostly answer “what happened under the old policy,” not “what would happen under the new policy.” See Offline Versus Online Evaluation for the evaluation mechanics.

When to use contextual bandits

Use contextual bandits when the choice should adapt to request features and the reward is observed soon enough to update the policy. They are useful for homepage modules, notification templates, article slots, ad creatives, and candidate-source selection. They are less appropriate when rewards are very delayed, actions interact strongly with each other, or the product needs multi-step planning; those cases may need delayed attribution, slate methods, or reinforcement learning.

Caveats

Contextual bandits optimize the reward they observe, so reward design matters as much as the algorithm. Clicks can reward sensational or repetitive items. Conversion rewards can under-value exploration for early-funnel content. Repeated exposure creates fatigue, and users can influence each other’s rewards through popularity effects.

Feature leakage is a common failure mode. Do not train on popularity, position, or engagement features that were computed after the item was exposed unless the serving system will know those exact values at decision time. Also keep eligibility filters outside the model: a contextual bandit should rank allowed actions, not learn to bypass availability, policy, or safety rules.

References

Nav

Section — Recommendation Systems and Personalization

← Bandit Algorithms Matchmaking Systems →

description	Bandit policies that use user, item, or request features when choosing actions.
area	recommendation-systems
topics	contextual-bandits
level	advanced
status	complete
page_type	algorithm
aliases

Data Science, Machine Learning & AI Wiki

Explorer

Contextual Bandits

Contextual Bandits

Decision loop

Formal setup

LinUCB

Worked example

Algorithm families

Logging and evaluation

When to use contextual bandits

Caveats

References

Graph View

Table of Contents

Backlinks