Multi-Armed Bandit (MAB)

The epsilon-greedy algorithm is a simple, foundational strategy where the agent selects the arm with the highest estimated reward (exploitation) most of the time, but with a fixed probability ε (epsilon), it selects a random arm (exploration).

• Mechanism: At each timestep, generate a random number. If it's below ε, explore randomly; otherwise, exploit the current best-known arm.
• Trade-off: A high ε value leads to more exploration but lower cumulative reward; a low ε leads to rapid exploitation but may converge to a suboptimal arm.
• Use Case: Ideal for simple, stationary environments where a constant level of exploration is acceptable. Often used as a baseline for comparison.

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.

• Mechanism: For each arm, it calculates an index: Estimated Reward + Confidence Bonus. The bonus is proportional to the square root of (ln(total pulls) / arm pulls). Arms pulled less often have a larger bonus, encouraging exploration.
• Theoretical Guarantee: UCB1 provides a proven logarithmic bound on cumulative regret, making it theoretically sound.
• Use Case: Preferred in scenarios requiring rigorous performance guarantees and efficient exploration. It systematically reduces uncertainty.

Thompson Sampling is a probabilistic algorithm that treats the unknown reward of each arm as a random variable, samples from its posterior distribution, and selects the arm with the highest sampled value.

• Mechanism: It maintains a Bayesian prior (e.g., Beta distribution for Bernoulli rewards) for each arm's reward probability. On each pull, it samples a reward estimate from each prior and pulls the arm with the highest sample. The observed result is then used to update that arm's posterior.
• Natural Balance: Exploration occurs naturally because arms with uncertain (wide) posteriors have a higher chance of generating a high sample.
• Use Case: Extremely effective in practice, often outperforming UCB, especially for non-stationary problems when using forgetting priors.

A Contextual Bandit extends the classic MAB by incorporating side information or context (e.g., user features, time of day) into the decision-making process. The goal is to learn a policy that maps contexts to optimal arms.

• Mechanism: At each round, the agent observes a context vector x. Algorithms like LinUCB (linear UCB) or Thompson Sampling with linear payoffs model the expected reward as a function of x and an arm-specific parameter vector.
• Key Difference: It solves a personalization problem, not just a selection problem. The optimal arm can change with the context.
• Use Case: The foundation for real-world recommendation systems, clinical trials with patient covariates, and dynamic pricing.

Adversarial Bandits model a non-stochastic environment where an adversary can arbitrarily assign rewards to arms at each timestep, with no assumptions of a fixed probability distribution.

• Challenge: Traditional stochastic algorithms like UCB can fail catastrophically here, as there is no 'true mean' to converge to.
• Key Algorithms: EXP3 (Exponential-weight algorithm for Exploration and Exploitation) is a seminal algorithm. It maintains a weight for each arm and selects arms probabilistically based on these weights, which are updated using exponential factors of the observed reward.
• Use Case: Modeling non-stationary environments, dynamic pricing against strategic competitors, or any scenario where reward patterns can change maliciously or unpredictably.

Bayesian Bandits provide the theoretical framework for optimal decision-making in the finite-horizon discounted MAB problem, with the Gittins Index offering an optimal solution under geometric discounting.

• Gittins Index Theorem: It states that the optimal policy for a multi-armed bandit with geometric discounting is to always play the arm with the highest Gittins Index. This index is a complex function of the arm's posterior distribution and the discount factor.
• Computational Cost: Calculating the exact Gittins Index is computationally intensive, limiting its direct practical application. Thompson Sampling is often viewed as a tractable, high-performing approximation.
• Significance: Provides the theoretical benchmark for optimality in Bayesian bandit problems, informing the design of heuristic algorithms.

The exploration-exploitation trade-off is the fundamental dilemma at the heart of the MAB problem and sequential decision-making. An agent must choose between:

• Exploitation: Selecting the action with the highest known reward based on current information to maximize immediate gain.
• Exploration: Trying suboptimal or less-known actions to gather more information, potentially discovering a better long-term option. MAB algorithms are specifically designed to mathematically balance this trade-off to maximize cumulative reward over time. This concept is critical in reinforcement learning, online advertising, clinical trials, and recommendation systems.

Upper Confidence Bound (UCB) is a prominent and theoretically-grounded algorithm for solving the stochastic MAB problem. Its core principle is optimism in the face of uncertainty. For each arm, it calculates an index that is the sum of:

1. The empirical average reward (the exploitation term).
2. A confidence interval bound that decreases with the number of times the arm has been pulled (the exploration term). The agent always selects the arm with the highest UCB index. This elegantly ensures that arms with high uncertainty or high potential reward are tried sufficiently often, providing a provable guarantee on regret (total loss versus the optimal arm). Variants include UCB1 and UCB-Tuned.

Thompson Sampling is a Bayesian, probability-matching algorithm for the MAB problem. Instead of computing a deterministic index, it maintains a posterior probability distribution over the expected reward of each arm. At each step, the algorithm:

1. Samples a single reward estimate from the posterior distribution of each arm.
2. Selects the arm whose sampled value is the highest.
3. Updates the posterior for the chosen arm based on the observed reward. This simple, randomized approach naturally balances exploration and exploitation: arms with higher uncertainty have broader posteriors, giving them a chance to be sampled even if their current mean is lower. It is highly effective and widely used in practice.

A Contextual Bandit extends the classic MAB by incorporating side information or context. Before each round, the agent observes a context vector (e.g., user features, time of day). The expected reward of each arm now depends on this context. The goal is to learn a policy that maps contexts to optimal arms. This framework is far more applicable to real-world problems like personalized news article recommendation, where the best article depends on the user's profile. Algorithms like LinUCB (linear UCB) and contextual Thompson sampling are standard solutions, often using linear models or neural networks to model the reward function.

Reinforcement Learning (RL) is the broader machine learning paradigm that encompasses the MAB problem. A MAB is a single-state or stateless RL problem. The key distinction is that in full RL, the agent's actions influence the state of the environment, leading to sequential, long-term consequences. MABs focus on the immediate exploration-exploitation trade-off without state transitions. Core RL concepts like value functions, policies, and temporal difference learning build upon bandit principles. Understanding MABs is often the first step toward grasping more complex RL algorithms like Q-Learning and Policy Gradients.

In MAB analysis, regret is the primary performance metric, quantifying the cost of exploration. It is defined as the difference between the cumulative reward obtained by always pulling the single best arm (in hindsight) and the cumulative reward obtained by the algorithm. Formally, for time horizon T: Regret(T) = T * μ* - Σ(observed rewards), where μ* is the reward of the optimal arm. The goal of MAB algorithm design is to achieve sublinear regret (regret that grows slower than T, e.g., O(log T)), meaning the average regret per round goes to zero. Minimizing cumulative regret is equivalent to maximizing cumulative reward.