Multi-Armed Bandit

The fundamental tension at the heart of sequential decision-making. Exploitation involves choosing the best-known option to maximize immediate reward. Exploration involves testing lesser-known options to gather data that may lead to higher rewards in the future. A pure exploitation strategy risks settling on a local maximum, while pure exploration incurs unnecessary opportunity cost. The MAB framework provides a mathematical structure to balance these competing objectives optimally.

The simplest MAB algorithm. With probability 1-ε, the algorithm exploits the current best arm. With probability ε, it explores a random arm.

• Typical ε values: 0.05 to 0.10
• Annealing: Gradually reducing ε over time shifts from exploration to exploitation
• Limitation: Explores uniformly, wasting trials on clearly inferior arms
• Use case: Good baseline when computational simplicity is paramount

A deterministic algorithm that selects arms based on an optimistic estimate of their potential reward. UCB calculates an upper confidence bound for each arm's expected value, combining the observed mean with an exploration bonus proportional to the uncertainty.

• Formula: Select arm maximizing μ̂ᵢ + √(2 ln(t) / nᵢ)
• Principle: Optimism in the face of uncertainty
• Automatically reduces exploration as sample size grows
• Advantage: No randomness; exploration is directed toward arms with high uncertainty

A Bayesian approach that maintains a probability distribution over each arm's true reward rate. At each step, the algorithm samples a value from each arm's posterior distribution and selects the arm with the highest sample.

• Prior: Typically a Beta distribution for binary rewards
• Posterior update: Incorporates observed successes and failures
• Natural balance: Arms with high uncertainty are sampled more widely, increasing their chance of selection
• Empirical strength: Often outperforms UCB in practice, especially with delayed or non-stationary rewards

An extension where the algorithm observes context features (user demographics, device type, time of day) before selecting an arm. The expected reward is modeled as a function of context, enabling personalization.

• Linear bandits: Model reward as a linear function of context features
• Neural bandits: Use deep networks to learn complex, non-linear reward functions
• Application: Personalized content recommendation where user attributes influence which variation performs best
• Key distinction: Unlike standard MABs, the optimal arm varies by context

The primary mathematical objective of MAB algorithms. Regret is defined as the difference between the cumulative reward obtained and the reward that would have been achieved by always selecting the optimal arm.

• Cumulative regret: Sum of per-step regret over the entire horizon
• Lai & Robbins lower bound: No algorithm can achieve regret growing slower than O(log T) for stochastic bandits
• Sub-linear regret: The hallmark of an effective algorithm; regret grows slower than linearly with time
• Practical implication: Minimizing regret means losing as little traffic as possible during the learning phase