Skip to content
AI360XpertBeta

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.

Same morning context scores 1.42 for sports and 1.50 for cooking, so the bonus for the less tried arm flips the pick
Same morning context scores 1.42 for sports and 1.50 for cooking, so the bonus for the less tried arm flips the pick

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 tt, meaning one visitor, you observe a context vector xtx_t, meaning numbers describing this visitor right now. You choose one arm aa from KK options, meaning sports or cooking here with K=2K = 2. You then observe a reward rr, meaning 1 for click and 0 for skip. A policy π(a∣x)\pi(a|x) 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 xtx_t 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 aa, AaA_a is a dd by dd matrix counting how much context you have seen for that arm, starting at identity. bab_a is a dd vector adding up context times reward. θa=Aa−1ba\theta_a = A_a^{-1} b_a is the current best guess of what each feature is worth for that arm. dd is the feature count, here d=2d = 2.

For a new context xx, the fit is θaTx\theta_a^T x, the predicted click rate. The bonus is αxTAa−1x\alpha \sqrt{x^T A_a^{-1} x}, the uncertainty payment for an arm you have tried less. α\alpha is a knob you set, here α=1.0\alpha = 1.0. The score is fit plus bonus. You pick the highest score, observe rr, then update only that arm with Aa+=xxTA_a += x x^T and ba+=rxb_a += r x.

Worked example: 1.42 against 1.50

Take x=[1,1]x = [1, 1], meaning bias 1 plus morning flag 1. Sports has seen more traffic. Its A=[[3,0],[0,3]]A = [[3, 0], [0, 3]] inverts to [[0.333,0],[0,0.333]][[0.333, 0], [0, 0.333]]. Its b=[1.2,0.6]b = [1.2, 0.6] gives θ=[0.4,0.2]\theta = [0.4, 0.2].

Fit is 0.4×1+0.2×1=0.600.4 \times 1 + 0.2 \times 1 = 0.60. The inside of the bonus is 1×0.333×1+1×0.333×1=0.66671 \times 0.333 \times 1 + 1 \times 0.333 \times 1 = 0.6667. The square root is 0.81650.8165, times α=1.0\alpha = 1.0 gives 0.820.82 after rounding. Score is 0.60+0.82=1.420.60 + 0.82 = 1.42.

Cooking has been tried less. Its A=[[2,0],[0,2]]A = [[2, 0], [0, 2]] inverts to [[0.5,0],[0,0.5]][[0.5, 0], [0, 0.5]]. Its b=[0.2,0.8]b = [0.2, 0.8] gives θ=[0.1,0.4]\theta = [0.1, 0.4].

Fit is 0.1+0.4=0.500.1 + 0.4 = 0.50. The inside of the bonus is 0.5+0.5=1.00.5 + 0.5 = 1.0, square root 1.001.00. Score is 0.50+1.00=1.500.50 + 1.00 = 1.50.

So cooking wins 1.501.50 to 1.421.42 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)  # -> True

The printout matches the hand computation: sports 0.60+0.82=1.420.60 + 0.82 = 1.42, cooking 0.50+1.00=1.500.50 + 1.00 = 1.50, 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 xx before picking arm aa and learns from reward rr, 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 [1,1][1, 1] scores 1.421.42 for sports and 1.501.50 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.