Multi-Armed Bandit

The epsilon-greedy algorithm is a simple, widely-used strategy that chooses the arm with the highest estimated reward (the greedy choice) most of the time, but with a small probability ε (epsilon), it selects a random arm for exploration.

• Mechanism: For each trial, generate a random number. If it's less than ε, explore a random arm. Otherwise, exploit the arm with the current highest empirical mean reward.
• Trade-off: A high ε value leads to more exploration but sacrifices short-term reward. A low ε exploits more but may converge to a sub-optimal arm.
• Use Case: Ideal for simple, stationary environments where a fixed exploration rate is acceptable. It's computationally cheap and easy to implement, making it a common baseline.

The Upper Confidence Bound (UCB) family of algorithms selects the arm with the highest statistical upper bound on its potential reward, formally balancing exploration and exploitation without a randomness parameter.

• Principle: For each arm, it calculates a confidence interval around the estimated mean reward. The algorithm chooses the arm with the highest upper confidence bound, which is the sum of the current mean reward and an exploration bonus.
• Exploration Bonus: This bonus is proportional to the logarithm of the total number of pulls and inversely proportional to the number of pulls for that specific arm. Less-pulled arms receive a larger bonus, ensuring they are eventually tried.
• Use Case: Excellent for deterministic, optimistic exploration. Variants like UCB1 are theoretically proven to minimize cumulative regret in stochastic environments.

Thompson Sampling is a probabilistic algorithm that treats the uncertainty of each arm's reward as a probability distribution. It selects arms by sampling from these distributions and choosing the sample with the highest value.

• Bayesian Approach: It maintains a prior belief (e.g., a Beta distribution for binary rewards) about the reward probability of each arm. After observing a reward, it updates the posterior distribution for that arm.
• Mechanism: On each trial, it draws one random sample from the current posterior distribution of each arm. It then pulls the arm whose sampled value is the highest. This naturally balances exploration and exploitation.
• Use Case: Highly effective for both stochastic and contextual bandits. It often achieves lower empirical regret than UCB and automatically adapts its exploration rate based on uncertainty.

Contextual Bandits extend the classic bandit problem by incorporating side information or context (e.g., user demographics, page features) into the decision-making process. The goal is to learn a policy that maps contexts to optimal arms.

• Key Difference: Rewards depend on both the chosen arm and the observed context vector for that round.
• Algorithms: Common approaches include LinUCB (linear models with upper confidence bounds) and Contextual Thompson Sampling, which use the context to model the expected reward for each arm.
• Use Case: The foundation for modern recommendation systems, personalized news article selection, and adaptive clinical trials where decisions must be tailored to individual observed features.

Adversarial Bandits model a non-stochastic environment where an opponent can arbitrarily assign losses (negative rewards) to arms in each round, potentially in response to the player's past actions.

• Assumption: Makes no statistical assumptions about reward generation. Rewards can be chosen to maximize the player's regret.
• Strategy: Algorithms like Exp3 (Exponential-weight algorithm for Exploration and Exploitation) are designed for this setting. They maintain a weight for each arm and select arms with a probability proportional to their exponentially weighted cumulative reward.
• Use Case: Modeling dynamic environments where conditions change adversarially, such as in some online auction or routing problems where other agents are adaptive.

A controlled experiment methodology where two or more variants (A, B, n) of a feature or model are presented to different user segments to statistically compare their performance against a defined objective. Unlike a multi-armed bandit, which dynamically reallocates traffic to optimize a reward, A/B/n tests typically use fixed traffic splits for the duration of the experiment to achieve statistical significance. This approach is ideal for conclusive, non-adaptive hypothesis testing.

• Key Use: Determining a definitive winner between discrete options.
• Contrast with Bandits: Bandits minimize opportunity cost during the experiment by exploiting the best-known option.

A deployment pattern where a stable, currently serving production model (the champion) is compared against one or more candidate models (challengers) using live traffic. This framework is a common application for multi-armed bandit algorithms, which manage the traffic split between the champion and challengers, balancing exploration of the challengers' performance with exploitation of the known-good champion. The goal is to automatically identify and promote a superior challenger to champion status.

• Core Mechanism: Bandits dynamically adjust traffic based on real-time performance.
• Outcome: Continuous model improvement with reduced risk.

The controlled routing of a percentage of user requests to different versions of a service or model. This is the foundational infrastructure capability that enables both A/B/n testing and multi-armed bandit experiments. In bandit systems, the split is not static but is algorithmically adjusted in real-time. This routing is often managed by service meshes (e.g., Istio VirtualService) or specialized Kubernetes operators.

• Enabling Technology: Critical for canary deployments and online experimentation.
• Dynamic vs. Static: Bandits use dynamic splitting; A/B tests use static splitting.

An advanced extension of the multi-armed bandit problem where the algorithm receives context (feature vectors about the current user, request, or state) with each decision. Instead of learning a single best arm, it learns a policy to select the best arm given the specific context. This is crucial for personalization and recommendation systems where the optimal choice depends on user attributes.

• Key Enhancement: Incorporates feature vectors to make conditional decisions.
• Real-world Use: Personalized news articles, ad selection, and dynamic UI rendering.

A Bayesian algorithm for solving the multi-armed bandit problem. It works by maintaining a probability distribution (posterior) over the expected reward of each arm. For each decision, it samples a potential reward value from each arm's distribution and selects the arm with the highest sampled value. This elegantly balances exploration and exploitation, as arms with uncertain (high-variance) distributions are sampled more often.

• Core Principle: Probability matching based on Bayesian posteriors.
• Advantage: Provides a principled, often highly effective, solution with strong theoretical guarantees.