Multi-Armed Bandit

The Epsilon-Greedy algorithm is a simple, fundamental strategy where, with probability 1-ε, the agent exploits the arm with the highest current estimated reward, and with probability ε, it explores a random arm uniformly. It provides a direct, tunable knob for the explore-exploit tradeoff.

• Key Parameter: ε (epsilon), the exploration rate.
• Advantages: Simple to implement and understand; computationally inexpensive.
• Limitations: Explores uniformly, ignoring which arms are more promising; exploration rate is fixed and does not adapt to uncertainty.
• Typical Use: Baseline algorithm for A/B testing platforms and simple recommendation systems.

The Upper Confidence Bound (UCB) family of algorithms selects the arm with the highest upper confidence bound on its reward, calculated as the current sample mean plus an exploration bonus. The bonus is proportional to the uncertainty (variance) of the estimate, shrinking as an arm is pulled more often.

• Core Principle: Optimism in the face of uncertainty. It assumes the best plausible reward for each arm.
• Mathematical Form: Common variants include UCB1, which uses a bonus term derived from the Chernoff-Hoeffding bound: mean + sqrt(2 * log(total_pulls) / arm_pulls).
• Advantages: Deterministic, no hyperparameters like ε; provides strong theoretical regret bounds.
• Use Case: Clinical trial designs, web page optimization where deterministic action selection is preferred.

Thompson Sampling is a Bayesian algorithm that selects actions by sampling from the posterior probability distribution that each arm is optimal. For each decision, it draws a sample reward estimate from each arm's posterior and pulls the arm with the highest sampled value.

• Mechanism: Maintains a prior distribution (e.g., Beta for Bernoulli rewards, Gaussian for normal rewards) for each arm's reward. After observing a reward, it updates the posterior via Bayes' rule.
• Natural Balance: Arms with high uncertainty have wider posteriors, leading to a higher chance of being sampled, automatically balancing exploration and exploitation.
• Advantages: Often achieves lower empirical regret than UCB; elegantly incorporates prior knowledge.
• Use Case: The dominant algorithm for modern large-scale recommendation systems and online advertising.

The Exponential-weight algorithm for Exploration and Exploitation (EXP3) is designed for the adversarial bandit setting, where an opponent may generate rewards arbitrarily (not from a stationary distribution). It maintains a weight for each arm and selects actions probabilistically based on these weights, which are updated using an exponential function of the observed reward.

• Key Feature: Makes minimal assumptions about the environment, providing robustness against non-stationary or malicious reward sequences.
• Mechanism: Uses importance sampling to estimate rewards for unchosen arms, then updates weights to favor higher-rewarding actions.
• Trade-off: While robust, it typically has higher regret than stochastic algorithms like UCB or Thompson Sampling in benign, stationary environments.
• Use Case: Cybersecurity (e.g., selecting defensive actions against an adaptive attacker), dynamic pricing against strategic competitors.

LinUCB extends the UCB principle to contextual bandits, where side information (context) is available before each decision. It assumes a linear relationship between the context vector and the expected reward of each arm.

• Model: For each arm a, it models the expected reward as θ_a^T * x, where x is the context and θ_a are learnable parameters. It maintains confidence ellipsoids around these parameter estimates.
• Action Selection: Chooses the arm that maximizes x^T * θ_a + α * sqrt(x^T * A_a^{-1} * x), where the second term is a confidence width derived from the ridge regression solution.
• Advantages: Enables personalization by leveraging user/context features; has strong theoretical guarantees.
• Use Case: News article recommendation, personalized healthcare interventions, and any application where rich feature vectors describe each decision opportunity.

Bayesian UCB is a hybrid approach that uses a Bayesian model (like Thompson Sampling) to compute a credible interval for each arm's reward, then applies the UCB principle by selecting the arm with the highest upper quantile of its posterior distribution (e.g., the 95th percentile).

• Mechanism: It combines Bayesian updating for parameter estimation with a deterministic, optimistic decision rule.
• Flexibility: Can use any tractable posterior distribution (Beta, Gaussian, etc.). The quantile level (e.g., 95%) acts as a hyperparameter controlling optimism.
• Comparison to Thompson Sampling: More deterministic; can be easier to analyze theoretically. Comparison to Frequentist UCB: Uses a probabilistically interpretable uncertainty measure from the posterior.
• Use Case: Problems where deterministic action selection is required but a Bayesian model of uncertainty is desired, such as in some financial trading applications.

The fundamental dilemma in sequential decision-making between gathering new information (exploration) and leveraging current knowledge to maximize immediate reward (exploitation). This tradeoff is quantified and optimized in bandit algorithms.

• Pure Exploration: Maximizes long-term knowledge but sacrifices short-term gains.
• Pure Exploitation: Maximizes immediate reward but may miss superior, undiscovered options.
• Balanced Strategies: Algorithms like Thompson Sampling and UCB mathematically formalize this balance to minimize cumulative regret.

The primary theoretical framework for analyzing online learning and bandit algorithms. Regret is the cumulative difference between the rewards obtained by the algorithm and the rewards that would have been obtained by always choosing the single best action in hindsight.

• Goal: Design algorithms with sublinear regret, meaning the average regret per round approaches zero over time.
• Types: Includes pseudo-regret (simplified analysis) and expected regret (accounts for algorithm randomness).
• Application: Provides performance guarantees for bandit algorithms, ensuring they converge to optimal behavior.

A Bayesian algorithm for solving the multi-armed bandit problem. It selects an arm by first sampling a potential reward value from the current posterior probability distribution for each arm, then choosing the arm with the highest sampled value.

• Mechanism: Naturally balances exploration and exploitation; arms with higher uncertainty have a wider posterior, giving them a chance to be sampled.
• Advantage: Often achieves lower empirical regret than deterministic methods like UCB and is conceptually simple.
• Use Case: The foundation for Bayesian optimization and widely used in contextual bandits for personalized recommendations.

A deterministic bandit algorithm that selects the arm with the highest Upper Confidence Bound. This bound is the sum of the current estimated mean reward plus an exploration bonus (e.g., based on the Hoeffding inequality) that shrinks as the arm is pulled more often.

• Principle: Optimism in the face of uncertainty. It assumes each arm is as good as its plausible best-case scenario.
• Variants: Includes UCB1 (the canonical form), UCB-Tuned (improved variance handling), and LinUCB for contextual settings.
• Characteristic: Provides strong, provable theoretical regret bounds, making it a standard for analysis.

An extension of the classic bandit where, before each decision, the algorithm observes a context vector (e.g., user profile, page content). The goal is to learn a policy that maps contexts to actions to maximize reward.

• Model: Often uses a linear model (e.g., LinUCB, Linear Thompson Sampling) or a neural network to predict reward from context.
• Application: Powers real-world systems like news article recommendation, ad selection, and clinical trial arm allocation where user state is critical.
• Difference from RL: Contextual bandits are stateless; each decision is independent, unlike full Reinforcement Learning which considers sequential state transitions.

A production methodology for comparing two or more variants (e.g., models, UI elements) by randomly assigning them to users. Multi-armed bandit algorithms are increasingly used as a more efficient alternative to traditional fixed-horizon A/B tests.

• Traditional A/B Test: Runs variants for a fixed period with equal traffic, then declares a winner. Inefficient if one variant is clearly worse.
• Bandit-Powered Test: Dynamically allocates more traffic to better-performing variants in real-time (exploitation) while still gathering data on others (exploration).
• Outcome: Minimizes opportunity cost (lost reward during the experiment) compared to static splits.