Contextual Bandit

The algorithm receives a d-dimensional feature vector x summarizing the current context—such as user demographics, device type, time of day, or item metadata. This side information allows the model to generalize across similar contexts rather than treating each action independently. For a new user with no history, the context vector provides the only signal for initial action selection, making feature engineering critical for cold-start performance.

Most contextual bandit implementations assume a linear relationship between the context features and expected reward: E[r | x, a] = θ_a^T x. Each arm a maintains a coefficient vector θ_a that is updated via ridge regression as feedback arrives. This linear assumption enables efficient closed-form updates and provides theoretical regret bounds, though neural bandits using deep networks can capture non-linear patterns at the cost of increased sample complexity.

The LinUCB algorithm selects arms by computing an optimistic estimate: the predicted reward plus a confidence bonus proportional to the uncertainty in the arm's parameters. This bonus shrinks as more data is collected for a given context region, naturally shifting from exploration to exploitation. For cold-start items, the high initial uncertainty drives exploration, ensuring new inventory receives traffic proportional to its potential value.

A Bayesian alternative to UCB that maintains a posterior distribution over model parameters. At each decision point, the algorithm samples a parameter vector from the posterior and selects the arm with the highest predicted reward under that sample. This naturally balances exploration—arms with high variance are chosen when their sampled parameters happen to be optimistic. For cold-start users, the broad initial posterior ensures diverse recommendations until preferences are inferred.

Unlike batch-trained supervised models, contextual bandits update arm parameters incrementally after each interaction using online learning. The update rule for LinUCB involves a recursive least-squares formulation: A_a = A_a + x x^T and b_a = b_a + r x, where A_a is the covariance matrix and b_a accumulates reward-weighted features. This allows the system to adapt to shifting user preferences without costly retraining cycles.

Contextual bandits provide theoretical regret bounds that grow sub-linearly with time—typically O(√(T d)) for LinUCB, where T is the number of rounds and d is the feature dimension. This means the average per-round regret approaches zero, proving the algorithm eventually matches the performance of the best fixed policy in hindsight. For cold-start mitigation, this guarantees the system learns efficient exploration strategies rather than wasting impressions on irrelevant items.

The fundamental dilemma that contextual bandits are designed to solve. Exploitation selects the action with the highest known reward given the context, maximizing immediate gain. Exploration chooses suboptimal actions to gather data about their true reward distribution. The regret metric quantifies the cost of exploration—the difference between the reward obtained and the optimal reward that could have been achieved. Contextual bandits use side information to make exploration more efficient than context-free alternatives like epsilon-greedy.

A probabilistic algorithm that elegantly balances exploration and exploitation by maintaining a posterior distribution over each action's reward probability. For each decision, it samples from these distributions and selects the action with the highest sample. Actions with high uncertainty—such as new items in a cold-start scenario—naturally receive more exploration because their wide distributions occasionally produce high samples. This probability matching approach is provably optimal for many bandit formulations and handles non-stationary environments gracefully.

The contextual data that distinguishes a contextual bandit from a standard multi-armed bandit. Side information includes any observable attributes available at decision time:

• User features: demographics, device type, referral source, time of day
• Item features: category, brand, price point, color, release date
• Session features: page context, prior clicks in session, geolocation This auxiliary data enables the algorithm to generalize across similar contexts, making it possible to estimate rewards for new items that share features with previously explored ones.

A deterministic alternative to Thompson Sampling that selects actions by maximizing an optimistic estimate of the expected reward. The UCB formula adds an exploration bonus proportional to the uncertainty of the estimate: actions with fewer trials receive a larger bonus. The LinUCB variant extends this to contextual settings by modeling rewards as a linear function of context features, with a confidence ellipsoid around the parameter estimates. This approach provides strong theoretical regret bounds and is widely deployed in news recommendation systems.

While A/B testing measures the average treatment effect across a population, contextual bandits continuously adapt traffic allocation based on observed outcomes. Key differences:

• Static vs. Dynamic: A/B tests use fixed allocation ratios; bandits shift traffic toward winning variants in real time
• Population vs. Personalization: A/B tests find a single winner; contextual bandits learn which variant works best for each user segment
• Opportunity Cost: Bandits minimize the cumulative regret of showing suboptimal variants during the test For cold-start item launches, bandits reduce the cost of learning by quickly identifying which user segments respond positively.

The methodology for estimating a contextual bandit policy's performance using logged historical data collected under a different policy. Techniques include:

• Inverse Propensity Scoring (IPS): Reweights observed rewards by the inverse probability of the logging policy selecting that action
• Doubly Robust Estimation: Combines IPS with a reward model to reduce variance while maintaining unbiasedness
• Direct Method: Trains a regression model to predict rewards for all actions and evaluates the target policy against these predictions Off-policy evaluation is critical for safely validating new bandit algorithms before deploying them to production traffic.