Contextual Bandits, Explained for Engineers

TL;DR.

• Contextual bandits are A/B testing that learns while you serve. Each request carries features; the policy picks an arm and updates online from the reward.
• Three algorithms cover ~90% of production cases: epsilon-greedy (baseline), Thompson sampling (default), LinUCB (closed-form uncertainty over a linear model).
• Yahoo's LinUCB lifted news CTR 12.5% over a context-free bandit on 33M events. Microsoft's Decision Service lifted MSN.com clicks 26% after Jan 2016.
• Bandits beat A/B tests when reward arrives fast, traffic is plentiful, and the optimal arm differs by context. They lose when rewards are delayed days, segments are too small, or you need a defensible single number.
• Production headaches are boring: reward telemetry, exploration floors, segment dilution, delayed feedback. Get those right before tuning the algorithm.

Most teams reach for A/B testing because it's the only experimentation tool they know. The cost shows up later: every week the loser variant keeps shipping, every dimension you don't slice is a personalization opportunity missed. Contextual bandits collapse "experiment" and "personalize" into the same system. This post covers the algorithms, when they beat A/B testing, and the production failure modes.

From slot machines to contextual bandits

The standard frame: you're in front of K slot machines, each with an unknown payoff distribution. The multi-armed bandit problem asks: how do you balance pulling the arm that looks best so far (exploit) against pulling other arms to find a better one (explore)? Every pull is both an experiment and a decision; you pay for exploration in lost reward but learn the world faster.

Contextual bandits extend this: each pull is accompanied by a feature vector x describing the situation. The user is logged-in, on iPhone, in Brazil, at 9am, last viewed three soccer videos. The optimal arm depends on x — that's the whole point. Your policy is no longer "always pull arm 2"; it's "given x, predict expected reward for each arm and explore where uncertainty is high."

The economic difference is concrete. A/B test allocates 50/50 until significance, then ships the winner. Bandit algorithms skew traffic toward the better arm as evidence accumulates. On the Yahoo Today Module data, Li et al. (2010) showed a contextual-bandit policy (LinUCB) earned a 12.5% click lift over a context-free baseline across 33M events. The lift comes from personalization — different users prefer different articles — not the bandit mechanic alone.

Three bandit algorithms you'll meet in production

You can read 200 papers and still ship ~3 algorithms.

Epsilon-greedy

With probability ε, pick a random arm. Otherwise pick the arm with the highest predicted reward. The predictor can be anything — a per-arm running mean, a regression model, a tree.

def epsilon_greedy(epsilon, predictions):
    if random.random() < epsilon:
        return random.choice(arms)
    return argmax(predictions)

When to use it: you're shipping bandits for the first time, or you want a simple safety net. Set ε = 0.05-0.10; enough exploration for K = 5-20 arms while keeping 90-95% of traffic on exploit. Downside: epsilon doesn't know which arm needs exploration — it spreads budget across confirmed losers. Fine to start, painful to scale.

Thompson sampling

Maintain a posterior distribution over each arm's expected reward. At decision time, sample once from each posterior and pick the arm with the highest sample. Arms with high mean and high uncertainty get pulled more often; the system self-anneals as posteriors tighten.

For Bernoulli rewards (click / no-click), keep a Beta(α, β) per arm. Sample, argmax, observe reward, update. That's it. Chapelle and Li's empirical evaluation of Thompson sampling showed it matches or beats UCB-style bandit algorithms across Yahoo and Microsoft benchmarks. Thompson sampling is the default for new production contextual bandits in 2026.

LinUCB

Assume the expected reward for arm a is linear in context: E[r | x, a] = x^T θ_a. Maintain a ridge-regression estimate of θ_a and its covariance. Pick the arm maximizing x^T θ_a + α · sqrt(x^T A_a^{-1} x) — predicted reward plus a UCB bonus proportional to prediction uncertainty.

LinUCB powered Yahoo's news recommender in Li et al. (2010). Why pick it over Thompson? Closed-form uncertainty makes it cheap, it has rigorous regret bounds, and engineers like watching the bonus shrink as data accumulates. The catch: linear reward and K separate models — if your true reward surface is nonlinear or you have thousands of arms with shared structure, you graduate to neural bandits or LinTS.

Why Thompson sampling is the default in 2026

Three reasons most teams converge to Thompson sampling personalization defaults:

1. Implementation cost: O(50) lines for a Bernoulli or Gaussian arm. No matrix inversion, no hyperparameter tuning of an exploration coefficient.
2. Empirical regret: across the Chapelle and Li benchmarks, Thompson matched or beat LinUCB and ε-greedy on cumulative reward. A recent arXiv literature review on scalable bandits confirms it as the production default.
3. Native uncertainty: the posterior is right there. You can stop arms, monitor convergence, and feed credible intervals into reporting without a separate confidence-interval calculation.

The downside: Thompson is high-variance when posteriors are wide, and naive Bayesian updates assume a stationary reward distribution. Fixable — add a min_pulls floor per arm before sampling, and decay old observations to track drift.

Production realities nobody mentions

Picking the algorithm is ~10% of the work. The other 90% is plumbing.

Reward telemetry. Arm, reward, and timestamp must round-trip into the policy reliably. We've seen teams ship LinUCB with 4-7% of rewards dropped silently — the policy still learns, but slowly, and the loss is invisible until you reconcile served-vs-rewarded counts. Build the reconciliation dashboard before you ship.

Exploration floor. Every arm needs a minimum traffic share — typically 1-2% — even when its posterior says it's worse. Distributions drift, content rotates, a bad arm might become good after a UX change. Microsoft's Multiworld Testing Decision Service is built around guaranteed exploration logging to make recovery possible.

Segment dilution. With K = 20 arms and 100k daily decisions, that's 5k pulls per arm — fast learning. Split by 10 user segments and you're down to 500 pulls per arm per segment per day. Most bandits then under-learn segment-specific patterns. Fix: pool data with a hierarchical model, or use a linear contextual algorithm where segments enter the feature vector instead of partitioning the data.

Delayed rewards. Bandit theory assumes the reward arrives right after the pull. In ecommerce, a purchase can arrive 30 minutes later; in ad-tech, conversion windows are 7-30 days. The naive policy treats unrewarded pulls as zero and over-explores. Fix: keep pulls pending until the reward window closes. Contextual bandits under delayed feedback gives formal regret bounds.

Logging policy probability. Log the probability the live policy assigned to the chosen arm. This single field unlocks off-policy evaluation and makes algorithm swaps 10x safer. Bake it in from day one.

When contextual bandits LOSE to A/B testing

The case against contextual bandits, which fans of the technique tend to skip:

• Reward arrives slowly. If your conversion signal is days out, A/B testing's ability to wait for clean significance is a feature. Bandits learning from delayed signals chase noise. A 30-day retention test should be an A/B test.
• Tiny traffic. Below ~1000 decisions per arm per day, posterior variance is high enough that bandits won't reliably outperform a simple A/B test. Ship the winner, revisit at scale.
• You need a defensible single number. A finance team that wants "the lift from feature X is 4.2% ± 0.6%" wants an A/B test result. Bandit policies produce a non-stationary, traffic-allocation-weighted reward stream — reporting becomes an explanation, not a number.
• High-stakes one-shot decisions. Pricing tier launches, new payment integrations, anything where a bad arm is expensive or irreversible. A/B test with guardrails; don't let bandit algorithms explore into a hole.
• Compliance and auditability. Regulated industries need exact records of "who saw what when". A bandit policy mutates continuously; you'll need extra logging to reproduce decisions. An A/B framework gives that out of the box.

We think the sensible default is: A/B test for binary feature launches with slow rewards, contextual bandit for ranking and selection problems with fast rewards. Most teams over-rotate one direction or the other.

What real production looks like

Public-record contextual bandits in production worth knowing:

• Yahoo Front Page Today Module (Li et al., 2010): LinUCB serving news, 12.5% click lift over context-free baseline on 33M events.
• Microsoft Decision Service (Agarwal et al., MWT-DS): cloud service exposing explore/log/learn/deploy abstractions, MSN.com clicks up 26% after Jan 2016, with deployments reporting 25-30% CTR lifts and an 18% revenue lift on one landing page.
• Netflix artwork personalization (Netflix Tech Blog): contextual bandits choosing which thumbnail to show per user, serving over 20M personalized image requests per second at peak. Action space is ~10s of candidate artworks per title, not the full catalog.

The thread: fast rewards, large traffic, action space in the 10s or 100s, and reward telemetry that's actually wired up. Where those conditions hold, contextual bandits beat A/B tests routinely. Where they don't, no algorithm tweak will save you.

How ×marble fits in

×marble is a personalization knowledge graph — we model users, items, and contexts as a graph so the policy layer (a contextual bandit, a learning-to-rank model, our own ranker) has stable, explainable features to work with. We've found that most teams' bandit problems are actually feature problems: the policy is fine, but the context vector lacks signal. A graph that surfaces "user is in onboarding day 2, reacted to two pricing-themed articles, prefers short-form" gives the bandit something to learn from.

If you'd rather not stand up the explore/log/learn loop and reconciliation dashboards yourself, we built that. Vivo uses bandits to pick which daily video brief slot to serve; marble × Music uses them to choose between catalog candidates with different reward signals. Integration patterns are open; the engine stays private.

FAQ

What are contextual bandits in simple terms?

Contextual bandits are an online machine-learning method where, on each request, the system sees a context (user features, page, time), picks one action from a small set of options, observes a reward (click, conversion, watch-time), and updates its model. They're "A/B testing that learns while it serves" — the policy continuously shifts traffic toward better-performing arms in each context.

When should I use contextual bandits instead of A/B testing?

Use contextual bandits when the reward arrives fast (seconds to minutes), traffic exceeds roughly 1000 decisions per arm per day, the action space is 5-100 arms, and the optimal action depends on user context. Use A/B testing when rewards are delayed days, you need a defensible single lift number, traffic is small, or the decision is high-stakes and irreversible.

What's the difference between multi-armed bandits and contextual bandits?

A multi-armed bandit picks among arms based only on the history of rewards. A contextual bandit also sees a feature vector describing the situation and picks the arm that's best for that context. Contextual bandits subsume non-contextual ones — they reduce to standard multi-armed bandits when the context is constant.

Is Thompson sampling better than epsilon-greedy?

In most production settings, yes. Thompson sampling explores proportional to uncertainty — wider posteriors get pulled more. Epsilon-greedy explores uniformly with fixed probability, wasting budget on confirmed losers. Chapelle and Li's empirical evaluation shows Thompson matches or beats epsilon-greedy and UCB methods across Yahoo and Microsoft ad benchmarks.

Can contextual bandits handle delayed rewards?

Yes, with care. Naive implementations bias the posterior pessimistically because not-yet-arrived rewards look like zero. The standard fix is to hold pulls pending until the reward window closes, then commit. Contextual bandits under delayed feedback provides formal regret bounds. If your reward arrives more than a few hours later, an A/B test is often more practical.

Further reading

• Hyper-personalization explained for engineers — where bandits sit in the broader stack.
• Reference architecture for real-time personalization — the plumbing bandits run inside.
• Recommendation engine vs personalization layer — bandits are the policy; the recommender is the candidate generator.
• Explainable recommendations and the path of a recommendation — auditing why a bandit picked an arm.
• A Contextual-Bandit Approach to Personalized News Article Recommendation (Li et al., 2010) — the LinUCB paper.
• An Empirical Evaluation of Thompson Sampling (Chapelle & Li, 2011) — why Thompson became the default.
• Multiworld Testing Decision Service (Agarwal et al.) — Microsoft's productionization.
• Artwork Personalization at Netflix — bandits at over 20M decisions per second.