Multi-Armed Bandit

The epsilon-greedy algorithm is a simple, widely-used strategy that balances exploration and exploitation via a fixed parameter, ε (epsilon). With probability ε, the algorithm selects a random arm (exploration). With probability 1-ε, it selects the arm with the highest current estimated reward (exploitation).

• Key Mechanism: Uses a fixed exploration rate.
• Advantages: Simple to implement and understand; computationally inexpensive.
• Disadvantages: Explores suboptimal arms uniformly, even after they are known to be poor; does not adapt exploration based on uncertainty.
• Typical Use Case: Baseline algorithm for online advertising and recommendation systems where simplicity is prioritized.

The Upper Confidence Bound algorithm selects the arm with the highest statistical upper bound on its potential reward, formally balancing the estimated mean reward and the uncertainty around that estimate.

• Key Mechanism: Uses confidence intervals derived from Hoeffding's inequality or other concentration bounds. The chosen arm maximizes: estimated_mean + exploration_bonus * sqrt(ln(total_pulls) / arm_pulls).
• Advantages: Deterministic and has strong theoretical regret bounds; explores arms with high uncertainty or few pulls.
• Disadvantages: Can be sensitive to the exploration parameter tuning in non-stationary environments.
• Real Example: Used in clinical trial designs to dynamically allocate patients to the most promising drug regimens while rigorously quantifying uncertainty.

Thompson Sampling is a Bayesian algorithm that selects an arm by sampling from the posterior probability distribution of each arm's reward and choosing the arm with the highest sampled value.

• Key Mechanism: Maintains a posterior distribution (e.g., Beta distribution for binary rewards, Gaussian for continuous) for each arm's reward. An action is chosen by drawing a sample from each posterior and acting optimally according to those sampled beliefs.
• Advantages: Naturally balances exploration and exploitation; often achieves lower empirical regret than UCB; adapts to non-stationary environments with online posterior updates.
• Disadvantages: Computationally more intensive than epsilon-greedy; requires specifying a prior.
• Sibling Topic: See the dedicated glossary entry for Thompson Sampling for a deeper dive into its Bayesian mechanics.

Contextual bandits extend the classic bandit framework by incorporating side information (context) about each decision round, allowing the policy to personalize arm selection based on observed features.

• Key Mechanism: At each round, a context vector (e.g., user demographics, page features) is observed. The algorithm learns a mapping from context to arm rewards, often using a linear model or neural network.
• Algorithms: Common implementations include LinUCB (linear model with UCB) and Thompson Sampling with linear payoffs.
• Advantages: Enables personalization, dramatically improving performance in heterogeneous populations.
• Primary Use Case: News article recommendation, where the 'context' is the user's reading history and the 'arms' are different articles.

Adversarial bandits model a scenario where an opponent can arbitrarily assign losses to arms in each round, with no assumption of stochastic reward generation. This framework is used for worst-case analysis.

• Key Mechanism: Algorithms are designed to minimize regret relative to the best fixed arm in hindsight, even under adversarial conditions.
• Core Algorithm: EXP3 (Exponential-weight algorithm for Exploration and Exploitation) is the canonical solution. It maintains a weight for each arm and selects arms with probability proportional to exponentially weighted cumulative losses.
• Advantages: Provides robust performance guarantees when reward distributions are non-stationary or intentionally manipulated.
• Application Domain: Online routing, spam filtering, and scenarios where the environment may be non-stochastic or actively hostile.

Non-stationary bandit algorithms are designed for environments where the true reward distribution of arms can change over time, requiring the policy to adapt and forget outdated information.

• Core Challenge: The exploration-exploitation dilemma is compounded by the need to detect and respond to drift.
• Common Techniques:
  • Sliding-Window UCB: Only uses recent data within a fixed time window for estimation.
  • Discounted UCB/Thompson Sampling: Applies a discount factor to older observations, reducing their weight.
  • Change-Point Detection: Uses statistical tests to reset estimates when a significant change is detected.
• Real-World Relevance: Critical for applications like financial trading, dynamic pricing, and content recommendation where user preferences and market conditions evolve.

Multi-armed bandits are used to dynamically optimize user interfaces, content layouts, and promotional offers in real-time. Unlike static A/B tests, they continuously shift traffic toward the best-performing variant (e.g., a button color or headline that yields higher click-through rates), maximizing cumulative reward during the experiment.

• Key Mechanism: Algorithms like Upper Confidence Bound (UCB) or Thompson Sampling balance trying new options with exploiting the current winner.
• Real Example: A news website uses a bandit to test multiple headline variants for an article, automatically directing more readers to the version generating the most engagement without waiting for a fixed test period to end.

In pharmaceutical research, bandit algorithms enable adaptive clinical trials. They can dynamically allocate new patients to the most promising treatment arms based on accumulating efficacy and safety data, while still exploring less-tested options.

• Key Benefit: This can lead to more ethical trials by exposing fewer patients to inferior treatments and can accelerate the identification of effective therapies.
• Statistical Consideration: Specialized bandit designs incorporate bayesian inference to handle the high stakes and complex, delayed feedback inherent in medical outcomes.

Recommendation engines (e.g., for content, products, or ads) use contextual bandits to personalize choices for each user. The system learns a policy that maps user context (profile, history) to the item with the highest predicted engagement, constantly exploring to avoid recommendation staleness.

• Core Concept: Contextual Bandits extend the classic framework by incorporating feature vectors about the user and the environment into the decision process.
• Example: A streaming service uses a contextual bandit to decide which movie thumbnail to show a user, based on their past genre preferences and time of day, to maximize the probability of a play.

E-commerce platforms and ad exchanges employ bandit algorithms to set prices or bids in real-time. The system explores different price points to discover the one that optimizes a key metric like revenue, conversion rate, or profit margin.

• Exploration-Exploitation Trade-off: The algorithm must cautiously test potentially suboptimal prices (exploration) to learn demand elasticity, while predominantly using the currently best-known price (exploitation).
• Industry Use: Ride-sharing apps dynamically adjust surge pricing using bandit-like mechanisms that respond to real-time supply and demand signals.

In cloud infrastructure and distributed systems, bandits help solve online resource allocation problems. This includes job scheduling, load balancing, and selecting between different backend services or model variants to minimize latency or cost.

• Problem Framing: Each server, cluster, or model endpoint is an "arm." The reward is a performance metric like throughput or inverse latency.
• Practical Impact: An API gateway can use a bandit to route requests to the fastest-responding backend instance from a pool, automatically adapting as network conditions and server loads change.

This card contrasts the multi-armed bandit approach with fixed-horizon A/B testing, highlighting the core trade-offs.

• A/B Testing (Fixed Sample Size):

  • Goal: Statistical significance for a definitive final decision.
  • Traffic: Split evenly (e.g., 50/50) for the entire experiment duration.
  • Best For: Non-urgent learning, regulatory validation, or when the cost of exploration is negligible.

• Multi-Armed Bandit (Adaptive):

  • Goal: Maximize cumulative performance during the experiment.
  • Traffic: Dynamically reallocated toward better performers.
  • Best For: High-traffic environments, when suboptimal choices have a high cost (e.g., lost revenue), or when a "good enough" decision is needed quickly.

A/B testing is a controlled experiment methodology where two or more variants of a system are randomly assigned to users to statistically compare their performance on a predefined primary metric. It is the foundational framework for making data-driven product decisions.

• Key Mechanism: Uses random assignment to create comparable control and treatment groups.
• Core Limitation: Requires a fixed sample size determined upfront; allocates traffic inefficiently compared to adaptive methods like bandits.
• Typical Use Case: Testing a new user interface layout against the current design to measure impact on click-through rate.

Thompson Sampling is a Bayesian algorithm for solving the multi-armed bandit problem. It selects an action by sampling a potential reward from the posterior probability distribution of each variant and choosing the one with the highest sampled value.

• Core Principle: Balances exploration and exploitation naturally through probability matching.
• Advantage: Provides a principled, often optimal, solution to the bandit problem with strong theoretical guarantees.
• Implementation: Maintains a distribution (e.g., Beta) for each arm's success rate; samples from these distributions to make each decision.

A contextual bandit is an extension of the multi-armed bandit framework where the decision-making algorithm has access to contextual features (e.g., user demographics, device type) before choosing an arm. The goal is to learn a policy that maps contexts to optimal actions.

• Key Difference: Moves from learning the best overall arm to learning the best arm for a given context.
• Architecture: Often implemented using a linear model or a neural network to predict the expected reward for each arm given the context.
• Application: Personalizing news article recommendations based on a user's past reading history and profile.

Sequential testing is an experimental design where data is analyzed continuously as it accumulates, allowing for the possibility of early stopping if results become statistically significant or if futility is determined, rather than waiting for a fixed, pre-determined sample size.

• Benefit: Can reduce the required sample size and time-to-decision compared to fixed-horizon tests.
• Challenge: Requires specialized statistical procedures (e.g., Sequential Probability Ratio Test) to control Type I error rates.
• Relation to Bandits: Bandits are a form of sequential decision-making, but they optimize for cumulative regret, not just early stopping for a single hypothesis.

The explore-exploit trade-off is the fundamental dilemma in sequential decision-making: whether to explore uncertain options to gather more information or to exploit the option currently believed to be best to maximize immediate reward.

• Core of Bandit Problems: Every bandit algorithm is a specific strategy for managing this trade-off.
• Exploration Cost: Gathering information (exploration) often requires sacrificing short-term reward.
• Algorithms Differ: Epsilon-Greedy uses a fixed probability for random exploration, while Upper Confidence Bound (UCB) algorithms use statistical confidence intervals to guide exploration.

In bandit and online learning literature, regret is the primary performance metric. It measures the total opportunity cost incurred by not always playing the optimal arm.

• Definition: Cumulative Regret = Σ (Reward of best possible arm - Reward of arm actually chosen).
• Goal of Algorithms: To design policies that minimize cumulative regret over time, often ensuring it grows sub-linearly with the number of trials.
• Types: Theoretical regret provides worst-case bounds; empirical regret is calculated on actual experiment data to evaluate algorithm performance.