Contextual Multi-Armed Bandit

Unlike standard bandits that rely solely on historical reward averages, a CMAB observes a context feature vector (e.g., user demographics, time of day, device type) before selecting an action. The expected reward is modeled as a function of this context, allowing the algorithm to generalize across similar situations. For example, a CMAB can learn that 'User A' responds better to 'Offer X' while 'User B' prefers 'Offer Y', even if both are new to the system.

The algorithm must continuously balance exploitation (choosing the best-known action for the current context to maximize immediate reward) against exploration (trying a potentially suboptimal action to gather new data). This is managed through strategies like:

• Epsilon-Greedy: A simple heuristic that explores randomly with probability ε.
• Upper Confidence Bound (UCB): Adds an uncertainty bonus to action estimates, favoring actions with wide confidence intervals.
• Thompson Sampling: A Bayesian approach that samples from the posterior probability of each action being optimal.

The primary mathematical goal is regret minimization. Regret is defined as the cumulative difference between the reward achieved by an oracle (a hypothetical policy that always picks the truly optimal action) and the reward accumulated by the bandit algorithm. A well-tuned CMAB exhibits sub-linear regret, meaning the average regret per round tends to zero over time, proving it converges to near-optimal performance without excessive costly exploration.

CMABs operate on partial feedback, also known as bandit feedback. The environment only reveals the reward for the action that was actually taken (e.g., did the user click?). The counterfactual outcomes of all other unchosen actions remain unknown. This distinguishes it from supervised learning and necessitates specialized evaluation techniques like Inverse Propensity Scoring (IPS) to debias historical logs when validating new policies offline.

Foundational algorithms like LinUCB assume the expected reward is a linear function of the context features. The model learns a coefficient vector θ for each action, where the predicted reward is the dot product of the context and θ. While computationally efficient and analytically tractable, this assumption can be limiting. Modern variants like Neural Bandits replace the linear model with a deep neural network to capture complex, non-linear relationships between context and reward.

In dynamic retail environments, user preferences shift over time due to seasonality, trends, or inventory changes. A non-stationary bandit explicitly models this by discounting historical observations or using a sliding window. Without this adaptation, a standard CMAB would suffer from contextual drift, where the learned model becomes stale and performance degrades. Techniques like online model retraining ensure the policy remains fresh and responsive to the latest behavioral patterns.

A Bayesian probabilistic algorithm for action selection. Instead of picking the arm with the highest point estimate, it samples from the posterior distribution of each arm's reward probability and selects the arm with the highest sample.

• Naturally balances exploration vs. exploitation
• Explores more when uncertainty is high
• Exploits more as confidence increases
• Often outperforms epsilon-greedy in practice

A deterministic algorithm that selects actions by maximizing an optimistic estimate. It adds an exploration bonus proportional to the uncertainty of the arm's estimated reward.

• Formula: UCB = mean_reward + c * sqrt(ln(t) / n)
• Arms with fewer trials get a larger bonus
• The c parameter controls the exploration-exploitation balance
• Provides strong theoretical regret guarantees

A statistical method for estimating a new policy's performance using historical data collected under a different logging policy. Critical for safe model validation without deploying live.

• Avoids risky A/B tests for untested models
• Relies on inverse propensity scoring (IPS) to correct selection bias
• Requires logged propensities from the original policy
• Enables rapid offline iteration on model design

The fundamental optimization objective in bandit problems. Regret is the difference between the cumulative reward of an optimal oracle policy and the reward accumulated by the learning algorithm.

• Zero-regret algorithms converge to optimal performance
• Sub-linear regret growth is the theoretical gold standard
• Drives algorithm design toward efficient exploration
• Directly translates to lost revenue or clicks in practice

A bandit problem where reward distributions change over time. User preferences drift, competitors shift strategies, and seasonality alters behavior.

• Requires discounting or sliding windows to forget old data
• Static algorithms fail catastrophically under drift
• Common in e-commerce during flash sales or holidays
• Often paired with online model retraining pipelines

The broader process of assessing a target policy's value using data from a different behavior policy. Goes beyond counterfactual estimation to include diagnostics and bias analysis.

• Doubly Robust estimators combine IPS with direct reward models
• Provides unbiased estimates even with misspecified models
• Essential for shadow deployment validation
• Enables continuous model quality monitoring