Multi-Armed Bandit

The simplest bandit algorithm that selects the best-known action with probability 1-ε and a random action with probability ε.

• Mechanism: A fixed exploration rate ε (e.g., 0.1) ensures continuous sampling of suboptimal arms
• Regret: Linear total regret because exploration never stops, even after identifying the optimal arm
• Practical use: Baseline for A/B testing and rapid prototyping where simplicity outweighs optimality
• Weakness: Wastes resources exploring clearly inferior arms with the same probability as promising ones

A deterministic algorithm that selects arms based on an optimistic estimate of their potential reward, calculated as the sample mean plus an exploration bonus.

• Mechanism: UCB = μ̂ᵢ + √(2 ln(t) / nᵢ), where the bonus shrinks as an arm is pulled more often
• Regret: Logarithmic total regret, a provably optimal scaling for the stochastic bandit problem
• Key insight: The algorithm is optimistic in the face of uncertainty, naturally balancing exploration and exploitation without an explicit ε parameter
• Variant: UCB1 is the canonical form with strong theoretical guarantees under bounded reward assumptions

A Bayesian algorithm that maintains a probability distribution over each arm's reward parameter and selects actions by sampling from these posterior distributions.

• Mechanism: For Bernoulli rewards, use Beta(α, β) priors; after observing a reward, update α (successes) or β (failures)
• Probability matching: The probability an arm is selected equals the probability it is optimal given current data
• Empirical performance: Often outperforms UCB in practice despite similar theoretical regret bounds
• Advantage: Naturally incorporates prior knowledge and handles non-stationary environments gracefully

A gradient-based algorithm that selects arms with probabilities proportional to their estimated values using a temperature-controlled softmax distribution.

• Mechanism: P(aᵢ) = exp(Qᵢ / τ) / Σⱼ exp(Qⱼ / τ), where τ (temperature) controls exploration intensity
• Temperature annealing: High τ encourages uniform exploration; low τ converges to greedy selection
• Gradient-bandit variant: Uses stochastic gradient ascent on expected reward, enabling learning of action preferences rather than just value estimates
• Use case: Effective when arms have similar expected values and fine-grained discrimination is required

An extension where the agent observes side information (context) before each decision, enabling personalized action selection rather than a single best arm for all situations.

• Mechanism: A model f(x, a) predicts the reward for action a given context vector x, typically using linear models or neural networks
• Key distinction: Unlike standard bandits, the optimal arm depends on the observed context, making this a supervised learning problem with partial feedback
• Applications: News recommendation, personalized medicine, dynamic pricing where user features inform the decision
• Challenge: The exploration-exploitation dilemma now operates in a feature space, requiring algorithms like LinUCB or neural bandits

A non-stochastic formulation where rewards are chosen by an adversary rather than drawn from fixed distributions, requiring algorithms with worst-case guarantees.

• Mechanism: The EXP3 (Exponential-weight algorithm for Exploration and Exploitation) algorithm maintains a weight for each arm and updates them multiplicatively based on observed rewards
• Regret bound: Achieves O(√(TK log K)) regret against the best fixed action in hindsight over T rounds with K arms
• Key concept: No statistical assumptions about reward generation; the adversary can adapt rewards based on the algorithm's past choices
• Relevance: Models non-stationary environments, competitive scenarios, and situations where stationarity assumptions fail

The formal mathematical framework that generalizes the bandit problem. An MDP models sequential decision-making in stochastic environments through five components: states, actions, transition probabilities, rewards, and a discount factor. Unlike the stateless bandit, MDPs introduce the concept that an agent's action influences not just immediate reward but also the next state the agent will occupy. This makes MDPs the foundation for full reinforcement learning problems where long-term consequences must be considered.

The central dilemma that defines the Multi-Armed Bandit problem. The agent must constantly decide between exploitation—choosing the arm with the highest known expected reward to maximize immediate gain—and exploration—pulling less-tested arms to gather information that may reveal superior options. Getting this balance wrong leads to two failure modes: premature convergence on a suboptimal arm or wasteful experimentation that forfeits known rewards. Algorithms like Epsilon-Greedy, UCB, and Thompson Sampling are explicit strategies for navigating this trade-off.

A Bayesian heuristic for the bandit problem that explicitly models uncertainty in the estimated reward of each arm. The algorithm maintains a probability distribution over each arm's true reward rate and, at each step, samples a value from each distribution, then selects the arm with the highest sample. This naturally balances exploration and exploitation: arms with high uncertainty have wide distributions and are occasionally sampled favorably, while well-tested arms with tight distributions are selected when their known value is genuinely high. It is provably asymptotically optimal and often outperforms UCB in practice.

A deterministic, frequentist algorithm that selects arms based on an optimistic estimate of their potential reward. UCB calculates an upper confidence bound for each arm using the formula: mean reward plus an exploration bonus that grows with the time since the arm was last pulled. The algorithm then selects the arm with the highest bound. This principle of optimism in the face of uncertainty ensures that no promising arm is permanently neglected. The UCB1 variant provides theoretical guarantees on regret that grow logarithmically with time.

An extension of the standard bandit where the agent observes side information (a context vector) before making each decision. Instead of learning a single best arm for all situations, the algorithm learns a policy that maps contexts to optimal actions. This transforms the problem from finding a global best to learning a personalized decision rule. Contextual bandits power real-world systems like news article recommendation, where the context includes user demographics and browsing history, and each arm represents a different article to display.

The standard theoretical objective for evaluating bandit algorithms. Regret is defined as the difference between the cumulative reward obtained by an algorithm and the reward that would have been obtained by an oracle that always selects the truly optimal arm. The goal is to design algorithms whose regret grows as slowly as possible—ideally sublinearly with respect to time. A sublinear regret bound proves that the algorithm eventually learns the optimal action and that the per-round penalty for learning vanishes. Common bounds include O(log T) for UCB and O(√T) for epsilon-greedy.