Contextual Bandit

A foundational algorithm that models the expected reward of each action as a linear function of the context features. It selects actions by computing an upper confidence bound on the predicted reward, analytically adding an exploration bonus proportional to the uncertainty of the parameter estimates.

• Mechanism: Maintains a ridge regression model per arm; the confidence interval width shrinks as more data is collected.
• Exploration bonus: Computed as the standard deviation of the estimate multiplied by a hyperparameter alpha.
• Use case: News article recommendation where user and article features are available.
• Advantage: Computationally efficient with a closed-form update and strong theoretical regret guarantees under linear realizability.

A Bayesian algorithm that maintains a probability distribution over the reward model parameters for each action. At each step, it samples a set of parameters from the posterior, acts greedily with respect to that sample, and then updates the posterior with the observed reward.

• Mechanism: For linear models, uses a Gaussian posterior over weight vectors; for categorical rewards, uses Beta distributions.
• Key property: Probability of selecting an action matches the probability that it is optimal given current knowledge.
• Advantage: Naturally balances exploration and exploitation without an explicit hyperparameter; empirically outperforms UCB in many settings.
• Variants: Can be extended to deep neural networks via Monte Carlo dropout or ensemble sampling.

The simplest contextual bandit strategy: with probability 1 - ε, exploit by selecting the action with the highest predicted reward from a supervised model; with probability ε, explore by selecting a random action uniformly.

• Implementation: Train a regression or classification model on all observed (context, action, reward) tuples to predict expected reward for each candidate action.
• Decay strategies: Often anneal ε over time (e.g., ε = 1/t) to shift from exploration to exploitation.
• Limitation: Explores uniformly without considering uncertainty, wasting trials on clearly suboptimal actions.
• Practical use: A strong baseline in production systems due to simplicity; often paired with warm-starting from logged bandit feedback data.

Extensions of linear bandit algorithms that use a deep neural network as the reward function approximator, enabling the modeling of complex, non-linear relationships between context and reward.

• NeuralUCB: Uses the network's gradient features as a learned representation and applies a UCB exploration bonus in the penultimate layer's space.
• NeuralTS: Applies Thompson Sampling by treating the neural network's output as a Gaussian process with the neural tangent kernel, sampling from the posterior predictive distribution.
• Challenge: Requires careful tuning of network width and learning rates to maintain calibrated uncertainty estimates.
• Advantage: Can capture feature interactions and non-linear patterns that linear models miss, crucial for high-dimensional user behavior contexts.

A suite of statistical techniques for evaluating a new contextual bandit policy using only logged historical data collected under a different (often stochastic) logging policy, without deploying the new policy online.

• Inverse Propensity Scoring (IPS): Reweights observed rewards by the ratio of target policy probability to logging policy probability for the chosen action.
• Doubly Robust (DR): Combines IPS with a direct reward model to reduce variance while maintaining unbiasedness if either the propensity model or reward model is correct.
• Self-Normalized IPS (SNIPS): Normalizes IPS weights to control variance from extreme propensity ratios.
• Critical for safety: Enables offline validation before risking real user experience degradation.

An extension where the agent selects a set or slate of actions simultaneously (e.g., a ranked list of products) rather than a single action, with the reward depending on the entire chosen combination.

• Challenge: The action space grows combinatorially (e.g., choosing 5 items from 10,000), making naive enumeration impossible.
• Solution approaches: Assume reward is a linear combination of individual item rewards, or use submodular maximization with bandit feedback.
• Application: Personalized homepage layout, where the system must select and order a set of widgets or articles.
• Key metric: Often optimized for Cascade Model user behavior, where users scan top-to-bottom and click probability decays with position.

Modern news aggregators use contextual bandits to personalize article rankings for each visitor. The context includes user demographics, reading history, time of day, and device type. The action is selecting which article to display in a headline slot, and the reward is a click or long dwell time. Unlike static collaborative filtering, the bandit continuously adapts to breaking news and shifting reader interests without waiting for batch retraining. Yahoo! pioneered this approach with their Today module, achieving a 12.5% click-through rate lift over non-contextual methods by balancing the exploration of fresh content against the exploitation of proven high-performers.

In pharmaceutical research, contextual bandits optimize patient treatment assignment in adaptive trials. The context is a patient's genomic markers, disease progression metrics, and demographic profile. The action is assigning a treatment arm, and the reward is a positive therapeutic outcome. By using a Thompson Sampling policy, the system allocates more patients to promising treatments while continuing to explore alternatives for under-represented subgroups. This approach reduces the number of patients exposed to ineffective treatments and accelerates the identification of responder populations, directly addressing the ethical and economic costs of traditional fixed-randomization trials.

Large retailers deploy contextual bandits to orchestrate every component of a landing page. The context vector encodes the user's referral source, loyalty tier, real-time session behavior, and current inventory levels. The action space is combinatorial: selecting a hero banner, a promotional offer, and a product carousel layout simultaneously. The reward is a composite of add-to-cart events and revenue. This replaces rigid A/B testing with a system that learns the optimal page configuration for each micro-segment. A key architectural challenge is managing the delayed reward problem, where a purchase may occur days after the initial impression, requiring inverse propensity scoring for unbiased offline evaluation.

Contextual bandits determine the optimal moment and message content for push notifications to prevent user churn. The context captures the user's timezone, app engagement history, battery level, and current activity inferred from accelerometer data. The action is choosing whether to send a notification and which copy variant to use. The reward is the user opening the app within a defined attribution window. A critical nuance is modeling the negative reward of sending a notification that causes the user to disable notifications entirely, framing the problem as a constrained optimization where long-term channel health is balanced against short-term engagement.

Infrastructure platforms use contextual bandits to dynamically allocate compute resources. The context is the current server load, request queue depth, and time-of-day traffic patterns. The action is provisioning or de-provisioning virtual machine instances, and the reward is a function of response latency and energy cost. A contextual bandit outperforms static threshold-based autoscaling by learning non-linear relationships between traffic composition and resource needs. For example, a video transcoding workload may require GPU allocation only when specific file formats appear in the queue, a pattern a bandit can learn without explicit rules.

Adaptive learning platforms employ contextual bandits to sequence curriculum modules. The context is the student's knowledge state estimated from assessment performance, learning style indicators, and engagement metrics. The action is selecting the next learning activity from a pool of candidates, and the reward is a correct answer or skill mastery demonstration. The system must handle the cold start problem for new students by leveraging population priors while rapidly individualizing. Crucially, the bandit's exploration policy must be constrained by pedagogical guardrails to prevent exposing a struggling student to material far beyond their current zone of proximal development.

The fundamental dilemma at the heart of every contextual bandit. The algorithm must balance exploiting known high-reward actions against exploring uncertain actions to gather new data.

• Epsilon-greedy: Explores randomly with probability ε, exploits otherwise.
• Upper Confidence Bound (UCB): Selects actions based on an optimistic estimate of potential reward plus an uncertainty bonus.
• Thompson Sampling: A Bayesian approach that samples from the posterior distribution of each action's reward probability.

Poor management of this trade-off leads to regret—the cumulative loss compared to always choosing the optimal action.

A standard Multi-Armed Bandit (MAB) selects actions without observing any side information, treating all users identically. A Contextual Bandit conditions each decision on a feature vector x representing the current user, session, or environment.

• MAB Example: A/B testing a single headline for all visitors.
• Contextual Example: Personalizing the headline based on visitor location, device, and referral source.

The addition of context transforms the problem from finding a single global optimum to learning a policy π(a|x) that maps diverse situations to personalized actions.

Evaluating a new bandit policy offline using historical data collected by a different logging policy. This is critical because deploying an untested policy in production is risky.

• Inverse Propensity Scoring (IPS): Reweights observed rewards by the inverse probability of the action being taken by the logging policy, correcting for selection bias.
• Doubly Robust (DR): Combines IPS with a direct reward model to reduce variance while maintaining unbiasedness if either the propensity or reward model is correct.
• Clipping: Caps extreme importance weights to control variance at the cost of introducing some bias.

Contextual bandits operate in an online learning paradigm where the model updates incrementally as each new data point arrives, without requiring batch retraining.

• Regret is the formal metric: the difference between the cumulative reward of the algorithm and that of the optimal policy in hindsight.
• No-Regret Algorithms: Guarantee that average regret per round approaches zero as T → ∞.
• Concept Drift: Online updates allow the policy to adapt to shifting user preferences, seasonal trends, or catalog changes without manual intervention.

A class of algorithms that directly parameterize and optimize the policy π(a|x) using gradient ascent on expected reward, rather than estimating action values.

• REINFORCE: The simplest policy gradient, using Monte Carlo returns to update the policy in the direction of higher rewards.
• Actor-Critic: Combines a policy network (actor) with a value function estimator (critic) to reduce gradient variance.
• Advantage: Policy gradients naturally handle continuous action spaces and stochastic policies, making them suitable for complex personalization tasks where discrete bandit assumptions break down.

The reward function defines what the bandit optimizes for, and poorly designed rewards lead to unintended behaviors.

• Immediate vs. Delayed: A click is immediate; a purchase or subscription renewal is delayed and must be attributed correctly.
• Primary vs. Proxy: Revenue is a primary metric; time-on-site is a proxy that may not correlate with business value.
• Multi-Objective: Combining conflicting goals (e.g., engagement vs. revenue) requires scalarization or constrained optimization.
• Inverse Reinforcement Learning: Inferring the reward function from observed expert behavior when explicit rewards are unavailable.