Skip to content
mlmentorship

Contextual bandits

Choose actions from context while balancing reward and uncertainty. The bridge between supervised prediction, experimentation, and reinforcement learning.

Published · 5 min read ·Specialist ·Intermediate

Summary

Bandits show up everywhere a system chooses an action and only learns about the action it took: recommendation, notifications, ranking, treatment selection, adaptive experiments. They formalize the cost that logged production data hides: you know what happened under the policy you ran, not what would have happened under the alternatives you never tried.

Formally, a contextual bandit sees context , chooses action , and receives a reward only for that action, maximizing cumulative reward while learning which actions work for which contexts. It sits between two neighbors: unlike full reinforcement learning, the action does not drive a persistent state transition; unlike supervised learning, the labels for the actions you did not choose are missing by design.

Learning objective

Zero logging probability leaves action C's reward unidentified

Action C has no logged supportAn unobserved reward cannot be filled with zero. No importance weight can recover an action whose logging probability is zero.The logger decides which paths existA0.6seenB0.4seenC0?No path means no observed rewardUnknown is not zero
Derivation
The logging policy reveals one reward and two unknown counterfactuals For context x, logging policy mu assigns probabilities 0.70 to action A, 0.30 to B, and zero to C. It chooses B and observes reward one. Rewards for unchosen A and C are unknown, shown as question marks rather than zeros. 1 · ONE LOGGED EVENT context x · logging policy μ ACTION μ(a|x) REWARD A B C 0.70 0.30 · chosen 0 ? unknown 1 observed ? unknown UNCHOSEN REWARDS ARE MISSING, NOT ZERO
The target policy fails the support check on action C Target policy pi assigns probabilities 0.20 to A, 0.30 to B, and 0.50 to C. Actions A and B have positive logging probability and are supported. C is unsupported because the target probability is positive while the logging probability is zero, so this target policy cannot be identified from these logs. 2 · TARGET POLICY SUPPORT CHECK same context x · target policy π ACTION π(a|x) LOG SUPPORT? A B C 0.20 0.30 0.50 yes · μ(A|x) = 0.70 yes · μ(B|x) = 0.30 NO · μ(C|x) = 0 π(C|x) > 0 BUT μ(C|x) = 0 → NOT IDENTIFIABLE
Read it this way: start with the left panel: one decision logs one chosen action and one reward; the other rewards remain unknown counterfactuals. Then align the same action rows on the right. The target policy puts probability on C, but the logging policy never tried C in this context, so no propensity correction can recover its reward from these logs. Original synthetic example informed by Li et al. on unbiased offline evaluation and Dudík et al. on doubly robust evaluation.
Check: Why is the target policy not identifiable when it assigns mass to C?
Read it this way: An unobserved reward cannot be filled with zero. No importance weight can recover an action whose logging probability is zero.
Can multiplying observed A and B records reveal C rewards?

Core approaches

  • Epsilon-greedy: exploit most of the time; pick randomly with probability .
  • UCB: choose the highest estimated reward plus an uncertainty bonus.
  • Thompson sampling: sample parameters from the posterior and act greedily under that sample.
  • LinUCB / linear Thompson sampling: assume expected reward is linear in the context features.

Off-policy evaluation

Logged data needs propensities. Inverse propensity scoring estimates a target policy by weighting reward by the probability of the logged action; doubly robust estimators combine a reward model with that correction. Without exploration support, a policy that chooses actions absent from the log is not identifiable offline: you have no evidence about what they would have returned.

In an interview

  1. Separate contextual bandits from supervised learning and MDPs.
  2. Define regret and the exploration-exploitation trade-off.
  3. Describe UCB or Thompson sampling.
  4. Explain logging propensities and off-policy evaluation.
  5. Cover delayed rewards, non-stationarity, safety constraints, and feedback loops.

Common confusions

  • “An A/B test is a bandit.” A fixed A/B test explores with a static policy; a bandit adapts assignment over time.
  • “Bandits always beat experiments.” Adaptive policies complicate inference and can chase short-term proxies.
  • “Use historical clicks as labels.” Only the actions the logging policy chose have outcomes; selection bias is the whole problem.

Related: exploration versus exploitation, A/B testing for ML, and policy gradient.

Found an error or stale claim? Report a correction or send a private note.