Contextual Bandit

Unlike a classic bandit that learns a single best arm for all users, a contextual bandit observes a feature vector (the context) before choosing an action. This context encodes the current state of the world—such as user demographics, browsing history, time of day, or device type. The algorithm learns a mapping from this context to the expected reward for each action, enabling personalized decisioning at scale. The core assumption is that the optimal action varies with the observed context, making this a supervised learning problem with a feedback loop.

The central tension in contextual bandits is balancing exploration (trying suboptimal actions to gather data) with exploitation (choosing the current best-known action to maximize immediate reward). Pure exploitation risks missing higher-reward actions, while pure exploration incurs opportunity cost. Contextual bandits formalize this trade-off to minimize cumulative regret—the difference between the reward obtained and the reward of an optimal oracle policy. Effective algorithms provably bound this regret over time.

Many practical contextual bandit algorithms, such as LinUCB and LinTS, operate under the linear realizability assumption. This posits that the expected reward for an action is a linear function of the context features: E[r | x, a] = θ_a^T x. The goal becomes learning the unknown coefficient vector θ_a for each arm. This assumption enables computationally efficient updates and strong theoretical regret bounds, making it suitable for high-throughput, low-latency production environments like ad serving and product recommendations.

Contextual bandits learn from bandit feedback, a form of partial information where only the reward for the chosen action is observed. The algorithm never sees the counterfactual outcome—what would have happened had it chosen a different action. This distinguishes it from standard supervised learning and creates the need for statistical techniques like inverse propensity scoring (IPS) to debias logged data for off-policy evaluation. The model must continuously update its parameters online as new (context, action, reward) tuples stream in.

Two dominant strategies exist for managing exploration:

• Upper Confidence Bound (UCB): Constructs a confidence interval around the estimated reward for each action and selects the action with the highest upper bound. This is an optimistic approach that naturally explores uncertain actions.
• Thompson Sampling: A Bayesian method that maintains a posterior distribution over each action's reward probability. It samples a reward estimate from each distribution and selects the action with the highest sample. This provides a natural, randomized exploration strategy that often outperforms UCB in practice.

When the linear realizability assumption fails, Deep Contextual Bandits use neural networks to model complex, non-linear relationships between context and reward. Architectures replace the linear dot product θ_a^T x with a deep network f(x, a; W) that learns a shared representation across arms. Techniques like the NeuralUCB algorithm use the network's final layer as a learned feature map and apply a UCB strategy on top. These models capture intricate user-item interactions but require careful training to avoid catastrophic forgetting in online settings.

Modern content platforms use contextual bandits to personalize article feeds. The algorithm observes user context—such as device type, time of day, and reading history—to select headlines that maximize click-through rate. Unlike static A/B tests, the bandit continuously shifts traffic toward high-performing articles while still exploring new content to prevent filter bubbles. This mechanism directly optimizes for cumulative engagement rather than short-term clicks.

Pharmaceutical researchers deploy contextual bandits to allocate patients to treatment arms more efficiently. The model ingests biomarker profiles and demographic covariates as context, then dynamically adjusts randomization probabilities to favor treatments showing higher efficacy. This minimizes patient exposure to ineffective therapies while accelerating statistical significance. The approach is governed by Bayesian inference to maintain rigorous safety and ethical constraints.

Retail giants use contextual bandits to curate the entire homepage experience in real time. The context vector includes geolocation, purchase history, referral source, and current cart contents. The bandit selects the optimal layout, hero banner, and product carousel to maximize conversion probability. This replaces rigid rule-based merchandising with a self-optimizing surface that adapts to seasonal trends and inventory levels without manual intervention.

Contextual bandits determine the optimal moment to send push notifications to prevent user churn. The algorithm evaluates context features like app engagement recency, battery level, current time zone, and motion state to decide whether to send a notification and which message variant to use. The reward signal is app opens within 30 minutes, balancing re-engagement against the risk of notification fatigue and permanent opt-outs.

Programmatic advertising platforms leverage contextual bandits to select ad creatives per impression. The context includes publisher domain, user interest segments, browser language, and viewport size. The bandit explores new creative variants while exploiting top performers, optimizing for conversion rate or cost-per-acquisition. This operates at massive scale, making millions of decisions per second with latency budgets under 50 milliseconds.

Adaptive learning platforms apply contextual bandits to sequence instructional content. The model uses skill mastery estimates, learning style indicators, and error pattern history as context to select the next exercise or video. The reward is correct answer rate and completion time. This creates individualized curricula that accelerate proficiency while maintaining learner motivation through appropriately challenging material.

The fundamental dilemma at the heart of every contextual bandit. The system must continuously decide between exploitation—choosing the action with the highest known reward based on current context—and exploration—selecting a potentially suboptimal action to gather new data and reduce uncertainty. A pure exploitation strategy maximizes immediate gains but risks settling on a local optimum, while pure exploration incurs high opportunity costs. Contextual bandits formalize this balance to minimize cumulative regret over time.

A Bayesian algorithm that elegantly balances exploration and exploitation. For each decision, it samples a reward distribution from the posterior probability of each action being optimal, then selects the action with the highest sample. Actions with high uncertainty have wider distributions and are sampled more frequently, naturally decaying exploration as confidence grows. It is computationally efficient and often outperforms more complex methods like Upper Confidence Bound in practice, especially for conjugate prior models like the Beta-Bernoulli bandit.

The optimization objective that measures the difference between the cumulative reward obtained by the bandit and the reward that would have been achieved by an oracle strategy that always selects the truly optimal action. Formally, regret after T rounds is: R(T) = Σ(μ* - μ_at). The goal is to achieve sub-linear regret, meaning the per-round regret approaches zero as time goes to infinity. Algorithms like LinUCB and Thompson Sampling provide theoretical regret bounds of O(√T) or better.

A critical technique for safely assessing a new contextual bandit policy before deploying it live. OPE uses historical log data collected by a different behavior policy to estimate the performance of a target policy without incurring the cost of online experimentation. Key methods include:

• Inverse Propensity Scoring (IPS): Re-weights observed rewards by the inverse probability of the logging policy's action.
• Doubly Robust Estimation: Combines IPS with a direct outcome model to remain unbiased if either the propensity or reward model is correctly specified.

A foundational contextual bandit algorithm that models the expected reward of an action as a linear function of the context features. It selects actions by maximizing an upper confidence bound: the estimated reward plus an exploration bonus proportional to the model's uncertainty about that action's parameters. The uncertainty term shrinks as more data is collected for a specific context-action pair. LinUCB provides strong theoretical guarantees and serves as the basis for many production recommendation and personalization systems.

The phenomenon where the relationship between context, actions, and rewards changes over time, violating the stationary environment assumption of standard bandit algorithms. In e-commerce, this manifests as shifting user preferences during seasonal trends or after a site redesign. Mitigation strategies include:

• Sliding window approaches that discard old data.
• Discount factors that exponentially decay the weight of historical observations.
• Change-point detection that triggers model resets when a distribution shift is statistically identified.