Contextual Bandits

A recommender choosing among a million items cannot treat them as independent arms, because learning each one's reward separately would take a million rounds before anything useful happened. Contextual bandits fix this by assuming reward is a function of features, so learning about one arm teaches you about similar ones.

The setting

At each round, observe a context \(x_t\), which describes the user, the time, the session, and the available actions. Choose an action, and receive a reward that depends on both. The goal is to learn a policy mapping contexts to actions.

This is supervised learning with partial feedback, and the difference from ordinary supervised learning is entirely in the feedback: you only see the outcome for the action you took, so the training data is generated by your own policy, which is what makes exploration necessary.

LinUCB

Assume the expected reward is linear in a feature vector combining context and action, \(\mathbb{E}[r \mid x, a] = \theta^\top \phi(x,a)\). Ridge regression gives an estimate of \(\theta\) and, from the design matrix, a confidence ellipsoid around it. The upper confidence bound on an action's reward is then

where \(A\) is the accumulated feature covariance and \(\alpha\) controls the exploration rate. The bonus is large in feature directions with little data, which means exploration is targeted at unexplored regions of feature space rather than at unexplored arms.

That is the key property. With a million items sharing features, the algorithm explores the feature space rather than the item space, so the number of rounds required scales with feature dimension rather than with the number of arms.

Thompson sampling has a linear analogue that samples \(\tilde{\theta}\) from the posterior over parameters and acts greedily, with the same advantages it has in the non-contextual case.

Beyond linear

Where a linear model is too restrictive, the options are a neural reward model with an approximate posterior, or reduction approaches that convert the bandit problem into a sequence of cost-sensitive classification problems solvable by any supervised learner. The second is attractive because it inherits whatever supervised methods work on the problem, and it requires importance weighting by the logged propensity to correct for the policy that generated the data.

When it breaks

The reward model is the whole thing. A misspecified model produces confidence estimates that are wrong in a direction the algorithm cannot detect, so it explores confidently in the wrong places. Contextual bandit performance is bounded by the reward model's quality, and the exploration machinery cannot compensate for a bad one.

Feature drift invalidates the accumulated design matrix. \(A\) encodes what has been seen, and if the feature distribution shifts, its inverse describes a region no longer relevant. Periodic refresh or discounting is required.

Log propensities or lose the data. Without recording the probability of each chosen action, the logged data cannot be reweighted for off-policy evaluation, so every future policy change requires a live experiment. Logging propensities costs one float per decision and is the highest-return instrumentation in the system.

Delayed and attributed rewards break the round structure. The formalism assumes reward follows the action promptly and unambiguously. Real rewards arrive hours later and may be attributable to several actions, and reconciling that with the algorithm is usually the hardest engineering in the deployment.