Contextual Bandits
A contextual bandit picks a different winner for each situation and learns from the payoff, so morning phone shoppers and evening laptop shoppers stop seeing the same list.
Why Does This Exist?
Say you run a shop homepage with two carousels: sports gear and cooking kits. The classic way to pick a winner is A/B testing. You split traffic 50/50, wait two weeks, then ship the higher click rate. If cooking wins, everyone sees cooking from then on.
You've paid for that answer. Half your visitors spent two weeks seeing the worse carousel. And the answer is still wrong for part of your crowd. Morning phone shoppers may tap sports while evening laptop shoppers buy cooking kits. One global winner averages those groups together and serves both badly.
Collaborative filtering has the same blind spot from the other side. It learns what similar users liked, but it keeps serving past winners and rarely tries anything new. New users and new items freeze for the same reason, which is the cold start problem. You will see that freeze the day you add a fresh product with zero clicks.
This page covers the fix that learns while it serves: read the shopper context first, score each arm for that context with fit plus bonus, then update from the click or skip. The static test lives in A/B testing. The crowd-wisdom layer lives in collaborative filtering. The new-user freeze lives in cold start problem.
Think of It Like This
The morning market stall
You run a market stall with two specials: grilled corn and hot soup. Each visitor arrives with visible context: gray sky or bright sun, hurrying commuter or lingering family. You choose which pot goes front, which is the arm, and you watch whether they buy, which is the reward.
After a few dozen visitors you learn a split rule. Soup wins on cold mornings, corn wins on sunny afternoons. You still try the other pot sometimes, because a cold snap or a new crowd can flip the rule. The sky plus the crowd is the context vector, the front pot is the arm, the coins are the reward.
Where it stops: you remember faces and moods you never wrote down. The bandit remembers only the features you feed it. If the real signal is something you didn't encode, like a festival down the street, it keeps picking from a blind menu.
How It Actually Works
The setup in symbols
At each round , meaning one visitor, you observe a context vector , meaning numbers describing this visitor right now. You choose one arm from options, meaning sports or cooking here with . You then observe a reward , meaning 1 for click and 0 for skip. A policy is the rule mapping context to choice. The goal is low regret, meaning few lost clicks against always picking the best arm for each context.
A context-free bandit skips and learns one global winner. That is the parent problem in multi-armed bandits: same arms, no features, one answer for everyone. Contextual adds the features back, so the answer can differ by shopper.
How LinUCB turns context into scores
LinUCB keeps one linear model per arm. For arm , is a by matrix counting how much context you have seen for that arm, starting at identity. is a vector adding up context times reward. is the current best guess of what each feature is worth for that arm. is the feature count, here .
For a new context , the fit is , the predicted click rate. The bonus is , the uncertainty payment for an arm you have tried less. is a knob you set, here . The score is fit plus bonus. You pick the highest score, observe , then update only that arm with and .
Worked example: 1.42 against 1.50
Take , meaning bias 1 plus morning flag 1. Sports has seen more traffic. Its inverts to . Its gives .
Fit is . The inside of the bonus is . The square root is , times gives after rounding. Score is .
Cooking has been tried less. Its inverts to . Its gives .
Fit is . The inside of the bonus is , square root . Score is .
So cooking wins to despite the lower fit. That's the whole idea. The bonus pays for uncertainty and flips the pick toward the less tried arm. The diagram draws these same numbers, with the bonus block labeled so shade is not the only signal.
Code
This replays the worked example with only the standard library. It computes fit, bonus, and score for both arms and checks the winner.
import math
def linucb_score(theta: list[float], inv_diag: list[float], x: list[float], alpha: float) -> tuple[float, float, float]: """Return (fit, bonus, score) for one arm on context x.""" fit: float = theta[0] * x[0] + theta[1] * x[1] quad: float = x[0] * inv_diag[0] * x[0] + x[1] * inv_diag[1] * x[1] bonus: float = alpha * math.sqrt(quad) return fit, bonus, fit + bonus
x: list[float] = [1.0, 1.0]fit_s, bonus_s, score_s = linucb_score([0.4, 0.2], [1.0 / 3.0, 1.0 / 3.0], x, 1.0)fit_c, bonus_c, score_c = linucb_score([0.1, 0.4], [0.5, 0.5], x, 1.0)
print(f"{fit_s:.2f} {bonus_s:.2f} {score_s:.2f}") # -> 0.60 0.82 1.42print(f"{fit_c:.2f} {bonus_c:.2f} {score_c:.2f}") # -> 0.50 1.00 1.50print(score_c > score_s) # -> TrueThe printout matches the hand computation: sports , cooking , and cooking wins the max.
Watch Out For
Retraining on your own winners
Symptom: offline accuracy climbs while fresh items never surface. Your logs overrepresent arms the old policy already liked, so a supervised retrain mistakes exposure for quality and doubles down. The top 50 items get more top slots, which get more clicks, which look like more proof.
Fix: log the propensity, meaning the probability you gave that arm for that context, on every serve. Retrain with inverse propensity weighting or a doubly robust estimator, keep an exploration floor near 5 to 10 percent of traffic, and check coverage of new items daily. If coverage falls while accuracy rises, your data collected you.
Paying for clicks you did not want
Symptom: click rate climbs while watch time, returns, or repeat visits fall. The bandit found the bait: flashy thumbnails that earn the instant 1 but lose the delayed payoff. You told it a click equals happy, and it believed you.
Fix: define reward past the click. Wait for a 10 minute stay with no quick return, or a purchase without refund, before writing the 1. Hold the update inside that window instead of learning on the instant tap. If instant and delayed rewards disagree for a week, trust the delayed one.
The Quick Version
- A contextual bandit reads context before picking arm and learns from reward , so different shoppers get different winners instead of one global winner.
- LinUCB scores each arm as fit plus bonus, meaning predicted payoff plus uncertainty, and serves the highest score for that context.
- The same morning context scores for sports and for cooking, so the less tried arm wins on bonus despite lower past clicks.
- Logs from a bandit favor old winners, so log propensities and keep an exploration floor or new items starve while accuracy looks healthy.
- Clicks alone teach clickbait, so define reward with a delay or quality check or the bandit will learn the wrong goal.