Multi-Armed Bandits Contextual Bandits Sequential Decision-Making Under Uncertainty
# Multi-Armed Bandits & Contextual Bandits: Sequential Decision-Making Under Uncertainty
## Introduction & Motivation
Many real-world decision-making problems require repeatedly choosing among a set of options with initially unknown payoffs, observing only the outcome of the chosen option, and using that feedback to improve future choices, all while the cost of exploring poorly performing options accumulates in real time. This setting, formalized as the multi-armed bandit problem, takes its name from a row of slot machines ("one-armed bandits") with unknown, potentially different payout rates, where a gambler must decide which machines to play, and how often, to maximize total winnings without knowing in advance which machine pays out best. The bandit framework strips away the full complexity of general reinforcement learning, there is no state transition to model, each action's outcome is independent of prior actions, isolating the core tension between exploration, gathering information about which option is best, and exploitation, acting on the best information currently available, in its purest and most mathematically tractable form.
This exploration-exploitation tradeoff is not a minor technical nuisance but the central object of study: an algorithm that always exploits its current best estimate risks getting permanently stuck on a suboptimal option due to early unlucky observations, while an algorithm that explores too much needlessly sacrifices reward on options already known to be inferior. Multi-armed bandit algorithms, including epsilon-greedy strategies, Upper Confidence Bound (UCB) methods, and Thompson sampling, provide principled, theoretically grounded ways to navigate this tradeoff, each backed by provable bounds on regret, the cumulative gap between the reward achieved and the reward an all-knowing oracle would have achieved by always selecting the best option.
Contextual bandits extend this framework to incorporate side information (context) available at each decision point, such as a user's browsing history when selecting which advertisement to display, or a patient's clinical history when selecting which treatment to recommend, allowing the optimal choice to vary systematically with context rather than remaining a single fixed best option across all situations. This extension dramatically broadens the framework's practical applicability, and contextual bandit algorithms such as LinUCB now underlie large-scale production systems for online advertising, content recommendation, and adaptive clinical trial design, making the multi-armed bandit framework one of the most widely deployed branches of sequential decision theory in industry.
## Core Concepts & Theory
In the classical stochastic multi-armed bandit setting, an agent faces $K$ arms (options), each associated with an unknown reward distribution, and at each of $T$ time steps selects one arm to play and observes a stochastic reward drawn from that arm's distribution, with the goal of maximizing cumulative reward, or equivalently minimizing cumulative regret relative to always playing the single best arm. Because reward distributions are unknown at the outset, the agent must learn estimates of each arm's expected reward through repeated play, and the fundamental exploration-exploitation dilemma arises precisely because playing an arm to learn about it (exploration) is costly whenever that arm turns out to be suboptimal, while playing only the current best-estimated arm (pure exploitation) risks never discovering that a different arm is, in fact, better, if early random reward fluctuations happened to make the truly best arm look mediocre.
Epsilon-greedy is the simplest strategy addressing this dilemma: with probability $\epsilon$, the agent explores by selecting a uniformly random arm, and with probability $1 - \epsilon$, it exploits by selecting the arm with the highest currently estimated mean reward. While simple to implement and reason about, epsilon-greedy's fixed exploration rate is a structural inefficiency, since it continues exploring uniformly at random even after the agent has gathered enough evidence to be highly confident about which arms are inferior, wasting reward on exploration that a smarter, uncertainty-aware strategy would no longer need to perform. Upper Confidence Bound (UCB) algorithms address this inefficiency directly by selecting, at each step, the arm with the highest upper confidence bound on its estimated mean reward, a value that combines the current reward estimate with an exploration bonus that shrinks as an arm is played more often and its estimate becomes more statistically certain, implementing the principle of "optimism in the face of uncertainty," acting as if underexplored arms might plausibly be as good as their most optimistic reasonable estimate suggests.
Thompson sampling takes a fundamentally Bayesian approach: it maintains a posterior probability distribution over each arm's true reward parameter (for Bernoulli-reward bandits, commonly a Beta distribution, conjugate to the Bernoulli likelihood and updated in closed form after each observed reward), and at each step samples one plausible reward value from each arm's current posterior, then plays whichever arm's sampled value is highest. Because posteriors for infrequently played arms remain wide (uncertain), sampled values from such arms occasionally come out high purely by chance, naturally driving exploration of underexplored arms, while posteriors for well-explored, confidently poor arms concentrate tightly around low values, naturally suppressing further exploration of them, achieving a self-tuning exploration-exploitation balance without any explicitly tuned exploration parameter.
## Mathematical Formulation
Regret, the standard performance metric for bandit algorithms, is defined as the expected cumulative gap between the reward the optimal arm would have earned and the reward the algorithm actually achieves over $T$ rounds,
$$ R(T) = \sum_{t=1}^{T} \left( \mu^* - \mu_{a_t} ight) $$
where $\mu^* = \max_i \mu_i$ is the mean reward of the best arm and $a_t$ is the arm selected at round $t$. A bandit algorithm is considered effective if its expected regret grows sublinearly in $T$, meaning the average per-round regret $R(T)/T$ shrinks toward zero as more rounds are played, in contrast to a naive strategy such as uniform random selection, whose regret grows linearly in $T$ since it never learns to favor better arms.
UCB1, the canonical UCB algorithm for Bernoulli or bounded-reward bandits, selects the arm maximizing
$$ a_t = \arg\max_{i} \left( \hat\mu_i(t) + \sqrt{\frac{2 \ln t}{n_i(t)}} ight) $$
where $\hat\mu_i(t)$ is the empirical mean reward of arm $i$ up to round $t$ and $n_i(t)$ is the number of times arm $i$ has been played so far; the exploration bonus $\sqrt{2 \ln t / n_i(t)}$ shrinks as $n_i(t)$ grows, reflecting increasing statistical confidence, while growing (very slowly, logarithmically) in $t$ to ensure every arm continues to be revisited occasionally, even after long stretches of apparent inferiority, guaranteeing the algorithm's celebrated $O(\log T)$ expected regret bound.
Thompson sampling for Bernoulli-reward arms maintains a $ ext{Beta}(\alpha_i, \beta_i)$ posterior for each arm $i$'s success probability, initialized to $ ext{Beta}(1, 1)$ (the uniform prior), and updated after each play of arm $i$ with observed reward $r \in \{0, 1\}$ as
$$ \alpha_i \leftarrow \alpha_i + r, \qquad \beta_i \leftarrow \beta_i + (1 - r) $$
with the arm selected at each round by sampling $ heta_i \sim ext{Beta}(\alpha_i, \beta_i)$ for every arm and playing $\arg\max_i heta_i$.
For contextual bandits, LinUCB assumes each arm's expected reward is linear in the observed context vector $x_t \in \mathbb{R}^d$, $\mathbb{E}[r_t \mid x_t, a_t = i] = heta_i^ op x_t$, and maintains, for each arm $i$, a ridge-regression estimate of $ heta_i$ along with its uncertainty via the matrices $A_i = I + \sum_{t: a_t = i} x_t x_t^ op$ and $b_i = \sum_{t: a_t = i} r_t x_t$, selecting the arm maximizing an upper confidence bound analogous to UCB1's but incorporating the context,
$$ a_t = \arg\max_{i} \left( \hat heta_i^ op x_t + \alpha \sqrt{x_t^ op A_i^{-1} x_t} ight), \qquad \hat heta_i = A_i^{-1} b_i $$
where $\alpha$ controls the width of the confidence bound, analogous to the exploration-controlling constant in UCB1.
## Advanced Theory & Extensions
The Gittins index theorem provides an elegant, provably optimal solution to the discounted, infinite-horizon Bayesian bandit problem, showing that an index can be computed independently for each arm based solely on that arm's own observation history, and that always playing the arm with the highest index is globally optimal, a remarkable decomposition result given that the bandit problem is, in general, a difficult joint optimization across all arms simultaneously; despite its theoretical elegance, Gittins indices are computationally demanding to calculate exactly and are used less often in practice than the simpler UCB and Thompson sampling heuristics, which achieve comparable regret guarantees with far simpler computation. Lower bounds on achievable regret, established by Lai and Robbins for the classical stochastic bandit setting, prove that no algorithm can achieve better than $O(\log T)$ expected regret asymptotically (for a fixed set of arm gaps), which is what makes UCB1 and Thompson sampling's matching $O(\log T)$ upper bounds particularly notable: both algorithms are asymptotically optimal, not merely reasonable heuristics.
Adversarial bandits relax the stochastic reward assumption entirely, allowing rewards to be chosen by an adversary rather than drawn from fixed distributions, a setting requiring fundamentally different algorithms such as EXP3 (Exponential-weight algorithm for Exploration and Exploitation), which achieves $O(\sqrt{KT \log K})$ regret against arbitrary, even adversarially chosen, reward sequences, at the cost of a worse regret rate than the logarithmic bounds achievable in the more benign stochastic setting. Best-arm identification (pure exploration), a distinct bandit variant that abandons the goal of maximizing cumulative reward during the learning process entirely in favor of identifying the single best arm as confidently and quickly as possible within a fixed budget of pulls, arises naturally in applications like A/B testing and drug trial design, where the exploration phase's cost is measured differently than the eventual deployment decision's quality, and requires distinct algorithms (such as successive elimination and racing algorithms) optimized for identification accuracy rather than regret minimization during the exploration phase itself.
## Computational Considerations
Classical multi-armed bandit algorithms (epsilon-greedy, UCB1, Thompson sampling for Bernoulli or Gaussian rewards) require only $O(K)$ memory, one running mean and count (or posterior parameter pair) per arm, and $O(K)$ computation per round to select an arm, making them essentially free to run even at very high decision rates and very large numbers of arms, a property that has made them attractive for high-throughput production systems such as real-time ad selection. Contextual bandits incur substantially higher per-round computational cost: LinUCB requires maintaining and inverting a $d imes d$ matrix per arm, an $O(d^3)$ operation if recomputed from scratch at each round, though this cost can be reduced to $O(d^2)$ per round using incremental (Sherman-Morrison) rank-one matrix inverse updates rather than recomputing the full inverse after every observation.
Scaling contextual bandits to very large arm sets, where maintaining a separate parameter vector and confidence matrix per arm becomes prohibitive, motivates shared-parameter formulations in which a single model (potentially a neural network, in "neural bandit" approaches) maps context-action pairs directly to reward estimates and uncertainty, trading the clean closed-form confidence bounds of linear contextual bandits for the representational flexibility needed to handle large or combinatorially structured action spaces, typically at the cost of requiring approximate uncertainty quantification (such as bootstrap ensembles or Bayesian neural network approximations) rather than LinUCB's exact closed-form confidence intervals. Batched and delayed-feedback bandit variants, addressing the practical reality that many production systems cannot update their arm-selection policy after every single observation (due to logging latency, batch processing pipelines, or high query throughput), require additional algorithmic care to maintain regret guarantees when policy updates are applied only periodically rather than after every individual observation.
## Practical Implementation Strategies
Selecting a bandit algorithm in practice should be driven primarily by whether context is available and informative: when no context distinguishes which arm is best at different decision points, classical (context-free) bandit algorithms such as UCB1 or Thompson sampling are simpler to implement, easier to reason about, and typically perform comparably to a contextual approach that would otherwise have nothing meaningful to condition on; when context genuinely shifts which arm is optimal, using a context-free bandit discards substantial available signal and a contextual approach such as LinUCB should be preferred. Thompson sampling is frequently favored over UCB1 in practice despite comparable theoretical regret guarantees, both because it tends to perform somewhat better empirically in many practical settings and because it naturally accommodates delayed and batched reward feedback more gracefully, since posterior updates can be applied whenever rewards eventually arrive without requiring the careful confidence-bound bookkeeping UCB-style methods depend on.
Warm-starting bandit algorithms with informative priors (for Thompson sampling) or with a brief forced-exploration initialization phase (playing every arm a fixed number of times before switching to the adaptive algorithm) meaningfully reduces early-stage regret when reasonable prior beliefs about arm quality are available from historical data or domain knowledge, rather than starting from a fully uninformative uniform prior or zero-initialized estimate that requires the algorithm to relearn information already available before deployment. Off-policy evaluation, estimating how a new candidate bandit policy would have performed using historical data logged under a different (previously deployed) policy, is an essential practical tool for safely comparing candidate algorithms or hyperparameter settings before deploying them live, using importance-weighting-based estimators to correct for the mismatch between the logging policy's action distribution and the candidate policy's action distribution.
## Benchmark Datasets & Evaluation
Bandit algorithms are commonly evaluated through simulation against synthetic reward distributions with controlled arm gaps (the difference between the best and second-best arm's mean reward), since regret bounds are explicitly gap-dependent and evaluating across a range of gap sizes, from very easy (large gap, fast identification) to very hard (near-identical arms, slow identification), reveals an algorithm's practical performance profile more completely than any single fixed benchmark setting could. Standard evaluation metrics include cumulative regret curves plotted against the number of rounds played, which visually reveal an algorithm's regret growth rate (ideally sublinear, flattening over time), and cumulative reward directly, particularly relevant for practical deployment contexts where absolute achieved reward, not comparison to an unobservable oracle, is the actual business-relevant quantity.
For contextual bandits, publicly available click-through and recommendation datasets (such as the Yahoo! Front Page Today module dataset, historically used for LinUCB benchmarking, and various publicly released advertising click-log datasets) enable offline, off-policy evaluation of contextual bandit algorithms against real historical logged interactions, using replay-based evaluation methods that only credit a candidate policy's simulated performance on rounds where its chosen action happened to match the logged historical action, providing an unbiased, though data-inefficient, estimate of a new policy's real-world performance without requiring live deployment. A/B testing platforms and adaptive experimentation frameworks increasingly report both traditional fixed-allocation A/B test metrics and adaptive-bandit-based metrics side by side, since bandit-based adaptive allocation directly optimizes for cumulative reward during the experiment itself, a fundamentally different objective than a fixed A/B test's goal of estimating each arm's true effect size with a target statistical power.
## Key Challenges & Limitations
The classical stochastic bandit assumption that each arm's reward distribution is fixed and stationary over the entire decision-making horizon is frequently violated in real deployments, where arm payoffs drift over time (a phenomenon termed non-stationarity, such as an advertisement's click-through rate declining as novelty wears off, or a recommended item's appeal shifting with changing trends), requiring specialized non-stationary bandit algorithms (such as sliding-window or discounted variants of UCB and Thompson sampling) that deliberately down-weight or discard old observations to remain responsive to a changing environment, at the unavoidable cost of noisier, higher-variance estimates than a stationary algorithm would maintain. Delayed feedback, where the reward for a chosen action is not observed until substantially after the action is taken (common in settings such as long-term user retention or conversion-based advertising metrics measured days after an ad impression), complicates standard bandit algorithms' incremental update assumptions and requires either explicit delay-aware algorithmic modifications or careful batching strategies to avoid systematically underweighting arms whose true reward signal has not yet fully arrived.
Contextual bandits' linearity assumption (in LinUCB and related linear methods) can be a significant limitation when the true relationship between context and reward is substantially nonlinear, motivating kernelized or neural contextual bandit variants at the cost of more complex, harder-to-calibrate uncertainty quantification and generally weaker theoretical regret guarantees than the clean, provable bounds available for the linear case. Bandit algorithms deployed in consequential real-world domains, such as clinical trial adaptive randomization or resource allocation for social programs, also raise distinct fairness and ethical concerns beyond pure regret minimization, since exploration inherently means deliberately assigning some fraction of participants to what current evidence suggests is a worse-performing option, a tension that has motivated specialized constrained and fairness-aware bandit formulations that explicitly bound how unevenly different arms (or different subgroups of participants) can be treated during the learning process.
## Hyperparameter Tuning
Epsilon-greedy's exploration rate $\epsilon$ trades off directly and transparently against regret: too small an $\epsilon$ risks insufficient exploration and premature convergence to a suboptimal arm, while too large an $\epsilon$ wastes reward on excessive random exploration long after the best arm has become clear; decaying $\epsilon$ schedules (starting higher and shrinking over time, commonly proportional to $1/t$) are frequently preferred over a fixed $\epsilon$ specifically because they approximate the naturally decreasing exploration need that UCB and Thompson sampling achieve automatically, without requiring a hand-tuned decay schedule. UCB algorithms' exploration-bonus scaling constant (the coefficient multiplying the confidence-width term, fixed at exactly $\sqrt{2}$ in the theoretically derived UCB1 bound but frequently treated as a tunable hyperparameter in practice) directly controls the exploration-exploitation balance, with smaller values producing a more exploitative, lower-early-regret-but-riskier algorithm and larger values producing a more conservative, more thoroughly exploring algorithm.
Thompson sampling's prior distribution parameters, while asymptotically washed out by enough observed data regardless of the specific prior chosen, meaningfully affect early-stage performance, and an informative prior reflecting genuine domain knowledge about plausible arm reward ranges can measurably reduce early regret relative to an uninformative uniform prior, particularly in settings with a limited total number of rounds where early-stage behavior contributes disproportionately to total regret. LinUCB's exploration constant $\alpha$, analogous to UCB1's exploration-bonus scaling, and the ridge regression regularization strength embedded in the $A_i$ matrices' identity-matrix initialization, both require empirical tuning (commonly via off-policy evaluation on logged historical data) since their theoretically justified values are frequently overly conservative relative to what empirically performs best on real-world context and reward distributions.
## Real-World Applications & Case Studies
Online advertising and content recommendation systems represent the most widespread production deployment of contextual bandit algorithms, with major technology companies using LinUCB and its neural and non-linear extensions to select which advertisement, article, or product recommendation to display given a user's browsing context, continuously balancing exploration of underexplored content against exploitation of content known to perform well, updated in near real time as new interaction data arrives. Adaptive clinical trial design has adopted bandit-inspired methods, including response-adaptive randomization schemes loosely related to Thompson sampling, to assign a progressively larger share of trial participants to treatments showing stronger early evidence of efficacy, aiming to reduce the number of participants exposed to an inferior treatment arm relative to traditional fixed-allocation randomized controlled trials, though this application area also illustrates the fairness and statistical-power tensions bandit-based allocation raises in high-stakes medical contexts.
Website and product A/B testing platforms increasingly offer bandit-based "multi-armed bandit testing" as an alternative to traditional fixed-split A/B testing, particularly for shorter-duration optimization tasks such as headline or button-color selection, where cumulative reward during the test itself (not just the eventual winner identified at the test's conclusion) has direct business value, making the regret-minimization framing bandit algorithms are designed around directly relevant, unlike traditional A/B testing's pure estimation-focused framing. Network routing, dynamic pricing, and resource allocation in cloud computing systems have all been formulated as multi-armed or contextual bandit problems, exploiting the framework's core strength: making good sequential decisions under genuine uncertainty about a set of options' payoffs, using only the feedback each decision itself generates, without requiring an separately collected labeled training dataset in advance.
## Integration with Other Methods
Multi-armed bandits are a special case of the more general reinforcement learning framework, corresponding to a Markov decision process with a single state and no state transitions, and bandit algorithms' exploration strategies, particularly UCB's optimism-under-uncertainty principle and Thompson sampling's posterior-sampling principle, have directly inspired analogous exploration strategies in full reinforcement learning (such as UCB-style exploration bonuses in model-based RL, and posterior sampling for reinforcement learning, an extension of Thompson sampling to the full multi-state RL setting), making bandit theory a foundational building block for understanding exploration in the broader RL literature. Bandit algorithms are also increasingly combined with causal inference techniques, particularly in off-policy evaluation and counterfactual reward estimation from historical logged data, since correctly estimating how a new bandit policy would have performed using data collected under a different, historical policy is fundamentally a causal inference problem requiring appropriate correction for the confounding introduced by the original logging policy's action-selection process.
Neural contextual bandits combine bandit exploration strategies with deep learning's representational flexibility, using a neural network to model the context-to-reward mapping while layering an uncertainty-quantification mechanism, such as an ensemble of networks trained with different random initializations (bootstrapped Thompson sampling), Bayesian neural network approximations, or dedicated uncertainty-output heads, on top to preserve the exploration-driving uncertainty estimates that linear contextual bandits obtain in closed form but that a single point-estimate neural network does not natively provide. Bandit algorithms also underlie hyperparameter optimization and neural architecture search methods such as successive halving and Hyperband, which frame the problem of allocating a limited computational budget across many candidate configurations as a best-arm-identification bandit problem, directly applying pure-exploration bandit theory to the practical problem of efficient model selection.
## Future Research Directions
Extending contextual bandit theory and algorithms to settings with combinatorially large or structured action spaces, such as selecting a ranked list of items rather than a single item, or selecting from an action space defined by a complex feature-based or graph-based structure, remains an active research area, since naive per-arm treatment of every possible combination is computationally infeasible and requires structural assumptions (such as submodularity of combined rewards) to make learning tractable within a reasonable number of rounds. Improving the sample efficiency and theoretical guarantees of neural and other non-linear contextual bandit methods, closing the gap between their strong empirical performance and the comparatively weaker theoretical regret bounds currently available relative to linear contextual bandits, is an important direction as increasingly complex, high-dimensional context representations (derived from large pretrained models) become standard inputs to production bandit systems.
Fairness-constrained and safety-constrained bandit algorithms, which explicitly bound worst-case treatment of any individual arm or subgroup during the learning process rather than optimizing purely for aggregate cumulative reward, are an increasingly important direction as bandit-based decision-making is applied to higher-stakes domains such as lending, hiring, and healthcare resource allocation, where unconstrained regret minimization alone does not adequately capture the full set of considerations a responsibly deployed system must satisfy. Finally, better integration of causal inference and bandit learning, particularly for correctly handling unobserved confounders that affect both the historical logging policy's action choices and the observed rewards, remains an open and practically consequential direction for improving the reliability of off-policy evaluation and safe bandit policy deployment from purely observational historical data.
## Summary & Key Takeaways
Multi-armed bandits formalize the fundamental exploration-exploitation tradeoff inherent in sequential decision-making under uncertainty, with epsilon-greedy, UCB algorithms, and Thompson sampling offering progressively more principled solutions, from epsilon-greedy's simple fixed-rate random exploration, to UCB's optimism-under-uncertainty confidence bounds achieving provably optimal $O(\log T)$ regret, to Thompson sampling's Bayesian posterior-sampling approach that self-tunes its exploration rate without any explicitly set exploration parameter. Contextual bandits extend this framework with algorithms such as LinUCB to incorporate side information that shifts which action is optimal across different decision points, dramatically broadening the framework's applicability to problems such as personalized content recommendation and adaptive treatment assignment where a single globally best action does not exist. Practical deployment requires navigating non-stationary reward distributions, delayed feedback, fairness considerations in exploration, and, for contextual bandits, the tradeoff between linear methods' clean theoretical guarantees and neural methods' greater representational flexibility, with off-policy evaluation from historical logged data serving as an essential tool for safely validating candidate bandit policies before live deployment.
Keywords: multi-armed bandits, contextual bandits, exploration-exploitation tradeoff, epsilon-greedy, UCB, upper confidence bound, Thompson sampling, LinUCB, regret bounds, Gittins index, adversarial bandits, EXP3, best-arm identification, off-policy evaluation, Bayesian bandits
---
## Appendix: Practical Labs
### Lab 1: Epsilon-Greedy Outperforms Both Pure-Greedy and Pure-Random Strategies
This lab runs epsilon-greedy, pure greedy (epsilon=0), and pure random (epsilon=1) strategies on a fixed Bernoulli bandit and verifies that epsilon-greedy achieves substantially higher cumulative reward than either extreme, since pure greedy risks getting stuck on a suboptimal arm while pure random never learns at all.
import numpy as np
def test_epsilon_greedy_outperforms_pure_greedy_and_random():
true_means = np.array([0.2, 0.5, 0.35, 0.65, 0.4])
n_arms = len(true_means)
n_steps = 3000
n_trials = 20
def run_epsilon_greedy(epsilon, rng):
counts = np.zeros(n_arms)
est_means = np.zeros(n_arms)
total_reward = 0.0
for t in range(n_steps):
if rng.uniform() < epsilon:
arm = rng.integers(n_arms)
else:
arm = np.argmax(est_means)
reward = rng.uniform() < true_means[arm]
counts[arm] += 1
est_means[arm] += (reward - est_means[arm]) / counts[arm]
total_reward += reward
return total_reward
eg_rewards, greedy_rewards, random_rewards = [], [], []
for trial in range(n_trials):
eg_rewards.append(run_epsilon_greedy(0.1, np.random.default_rng(trial)))
greedy_rewards.append(run_epsilon_greedy(0.0, np.random.default_rng(trial + 1000)))
random_rewards.append(run_epsilon_greedy(1.0, np.random.default_rng(trial + 2000)))
mean_eg = np.mean(eg_rewards)
mean_greedy = np.mean(greedy_rewards)
mean_random = np.mean(random_rewards)
optimal_total = true_means.max() * n_steps
print(f"mean total reward over {n_steps} steps: epsilon-greedy={mean_eg:.1f} pure-greedy={mean_greedy:.1f} random={mean_random:.1f} optimal={optimal_total:.1f}")
assert mean_eg > mean_greedy
assert mean_eg > mean_random
assert mean_eg > optimal_total * 0.85
print("Epsilon-greedy outperformance test passed.")
if __name__ == "__main__":
test_epsilon_greedy_outperforms_pure_greedy_and_random()### Lab 2: UCB1 Achieves Sublinear Regret Relative to Random Selection
This lab implements UCB1 from scratch and verifies both that its cumulative regret is far lower than uniform random selection's linearly growing regret, and that UCB1's own regret growth rate slows over time (sublinear growth), the hallmark of a successful exploration-exploitation strategy.
import numpy as np
def test_ucb1_achieves_sublinear_regret_vs_linear_regret_of_random():
true_means = np.array([0.3, 0.5, 0.4, 0.65, 0.45])
n_arms = len(true_means)
best_mean = true_means.max()
n_steps = 5000
def run_ucb1(rng):
counts = np.zeros(n_arms)
est_means = np.zeros(n_arms)
regrets = np.zeros(n_steps)
cum_regret = 0.0
for arm in range(n_arms):
reward = rng.uniform() < true_means[arm]
counts[arm] += 1
est_means[arm] += (reward - est_means[arm]) / counts[arm]
cum_regret += best_mean - true_means[arm]
regrets[arm] = cum_regret
for t in range(n_arms, n_steps):
ucb = est_means + np.sqrt(2 * np.log(t + 1) / counts)
arm = np.argmax(ucb)
reward = rng.uniform() < true_means[arm]
counts[arm] += 1
est_means[arm] += (reward - est_means[arm]) / counts[arm]
cum_regret += best_mean - true_means[arm]
regrets[t] = cum_regret
return regrets
def run_random(rng):
regrets = np.zeros(n_steps)
cum_regret = 0.0
for t in range(n_steps):
arm = rng.integers(n_arms)
cum_regret += best_mean - true_means[arm]
regrets[t] = cum_regret
return regrets
n_trials = 15
ucb_regrets = np.mean([run_ucb1(np.random.default_rng(i)) for i in range(n_trials)], axis=0)
random_regrets = np.mean([run_random(np.random.default_rng(i + 500)) for i in range(n_trials)], axis=0)
print(f"final cumulative regret at t={n_steps}: UCB1={ucb_regrets[-1]:.1f} random={random_regrets[-1]:.1f}")
assert ucb_regrets[-1] < random_regrets[-1] * 0.25
half = n_steps // 2
rate_first_half = ucb_regrets[half] - ucb_regrets[0]
rate_second_half = ucb_regrets[-1] - ucb_regrets[half]
print(f"UCB1 regret accumulated: first half={rate_first_half:.2f} second half={rate_second_half:.2f}")
assert rate_second_half < rate_first_half
print("UCB1 sublinear regret test passed.")
if __name__ == "__main__":
test_ucb1_achieves_sublinear_regret_vs_linear_regret_of_random()### Lab 3: Thompson Sampling Achieves Lower Regret Than Epsilon-Greedy
This lab implements Thompson sampling with Beta-Bernoulli conjugate updates from scratch and verifies it achieves lower cumulative regret than epsilon-greedy on the same bandit instance, along with a decreasing regret accumulation rate over time consistent with successful convergence to the best arm.
import numpy as np
def test_thompson_sampling_achieves_lower_regret_than_epsilon_greedy():
true_means = np.array([0.3, 0.55, 0.4, 0.7, 0.45])
n_arms = len(true_means)
best_mean = true_means.max()
n_steps = 3000
def run_thompson(rng):
alpha = np.ones(n_arms)
beta = np.ones(n_arms)
cum_regret = 0.0
regrets = np.zeros(n_steps)
for t in range(n_steps):
samples = rng.beta(alpha, beta)
arm = np.argmax(samples)
reward = rng.uniform() < true_means[arm]
alpha[arm] += reward
beta[arm] += (1 - reward)
cum_regret += best_mean - true_means[arm]
regrets[t] = cum_regret
return regrets
def run_epsilon_greedy(epsilon, rng):
counts = np.zeros(n_arms)
est_means = np.zeros(n_arms)
cum_regret = 0.0
regrets = np.zeros(n_steps)
for t in range(n_steps):
if rng.uniform() < epsilon:
arm = rng.integers(n_arms)
else:
arm = np.argmax(est_means)
reward = rng.uniform() < true_means[arm]
counts[arm] += 1
est_means[arm] += (reward - est_means[arm]) / counts[arm]
cum_regret += best_mean - true_means[arm]
regrets[t] = cum_regret
return regrets
n_trials = 25
ts_regrets = np.mean([run_thompson(np.random.default_rng(i)) for i in range(n_trials)], axis=0)
eg_regrets = np.mean([run_epsilon_greedy(0.1, np.random.default_rng(i + 500)) for i in range(n_trials)], axis=0)
print(f"final cumulative regret at t={n_steps}: Thompson={ts_regrets[-1]:.2f} epsilon-greedy={eg_regrets[-1]:.2f}")
assert ts_regrets[-1] < eg_regrets[-1]
half = n_steps // 2
rate_first = ts_regrets[half] - ts_regrets[0]
rate_second = ts_regrets[-1] - ts_regrets[half]
assert rate_second < rate_first
print("Thompson sampling outperforms epsilon-greedy test passed.")
if __name__ == "__main__":
test_thompson_sampling_achieves_lower_regret_than_epsilon_greedy()### Lab 4: A Contextual Bandit (LinUCB) Outperforms a Context-Free Bandit When Reward Depends on Context
This lab implements LinUCB from scratch on a synthetic problem where each arm's reward depends linearly on a context vector with arm-specific coefficients, so that the best arm genuinely varies with context, and verifies LinUCB substantially outperforms a context-free UCB bandit that can only learn a single fixed average reward per arm.
import numpy as np
def test_contextual_bandit_outperforms_context_free_bandit_when_reward_depends_on_context():
rng = np.random.default_rng(2)
n_arms = 4
d = 5
n_steps = 2000
true_theta = rng.normal(size=(n_arms, d)) * 0.5
def gen_context(rng):
c = rng.normal(size=d)
c[0] = 1.0
return c
def expected_rewards(context):
return true_theta @ context
def run_linucb(alpha, rng):
A = [np.eye(d) for _ in range(n_arms)]
b = [np.zeros(d) for _ in range(n_arms)]
cum_reward = 0.0
for t in range(n_steps):
context = gen_context(rng)
ucb_scores = np.zeros(n_arms)
for a in range(n_arms):
A_inv = np.linalg.inv(A[a])
theta_hat = A_inv @ b[a]
mean_est = theta_hat @ context
bonus = alpha * np.sqrt(context @ A_inv @ context)
ucb_scores[a] = mean_est + bonus
arm = np.argmax(ucb_scores)
true_r = expected_rewards(context)[arm]
reward = true_r + rng.normal(scale=0.1)
A[arm] += np.outer(context, context)
b[arm] += reward * context
cum_reward += true_r
return cum_reward
def run_context_free_ucb(rng):
counts = np.zeros(n_arms)
est_means = np.zeros(n_arms)
cum_reward = 0.0
for t in range(n_steps):
context = gen_context(rng)
if t < n_arms:
arm = t
else:
ucb = est_means + np.sqrt(2 * np.log(t + 1) / np.maximum(counts, 1))
arm = np.argmax(ucb)
true_r = expected_rewards(context)[arm]
reward = true_r + rng.normal(scale=0.1)
counts[arm] += 1
est_means[arm] += (reward - est_means[arm]) / counts[arm]
cum_reward += true_r
return cum_reward
def run_oracle(rng):
cum_reward = 0.0
for t in range(n_steps):
context = gen_context(rng)
cum_reward += expected_rewards(context).max()
return cum_reward
n_trials = 10
linucb_rewards = [run_linucb(1.0, np.random.default_rng(i)) for i in range(n_trials)]
contextfree_rewards = [run_context_free_ucb(np.random.default_rng(i)) for i in range(n_trials)]
oracle_rewards = [run_oracle(np.random.default_rng(i)) for i in range(n_trials)]
mean_linucb = np.mean(linucb_rewards)
mean_cf = np.mean(contextfree_rewards)
mean_oracle = np.mean(oracle_rewards)
print(f"mean cumulative expected reward over {n_steps} steps: LinUCB={mean_linucb:.1f} context-free-UCB={mean_cf:.1f} oracle={mean_oracle:.1f}")
assert mean_linucb > mean_cf
assert mean_linucb > mean_oracle * 0.85
print("Contextual bandit outperformance test passed.")
if __name__ == "__main__":
test_contextual_bandit_outperforms_context_free_bandit_when_reward_depends_on_context()