Multi-armed bandits

Exploration means trying arms whose rewards are uncertain to gather information, while exploitation means choosing the arm with the highest estimated reward. The tradeoff exists because purely exploiting may lock onto a suboptimal arm, while purely exploring wastes pulls on arms already known to be inferior.

When epsilon = 0 the algorithm is purely greedy — it always selects the arm with the highest current mean estimate and never explores. This risks permanently settling on a suboptimal arm if initial estimates are misleading due to stochastic noise in early pulls.

Cumulative regret R(T) = sum_{t=1}^{T} [mu* - mu_{a_t}], where mu* is the optimal arm's mean and mu_{a_t} is the mean of the arm chosen at round t. It measures the total expected reward gap between always playing the optimal arm and what the algorithm actually played — the standard objective for minimization.

UCB1 index = mu_hat_i + sqrt(2 * ln(t) / n_i), where mu_hat_i is the empirical mean, t is the total rounds elapsed, and n_i is the number of pulls of arm i. The sqrt term is an upper confidence bonus encoding the OFU principle — it shrinks as n_i grows, ensuring underexplored arms remain attractive until their estimates are reliable.

index_i = mu_hat[i] + np.sqrt(2 * np.log(t) / n[i])

Each arm i maintains a Beta(alpha_i, beta_i) posterior over its success probability. After a pull, alpha_i is incremented on success and beta_i on failure. At each step a sample theta_i ~ Beta(alpha_i, beta_i) is drawn for every arm and the arm with the largest sample is selected. Beta-Bernoulli is the conjugate pair, making the posterior update exact and O(1) per step.

theta = [np.random.beta(alpha[i], beta[i]) for i in range(K)]
arm = np.argmax(theta)

The Beta-Bernoulli model is standard: maintain a Beta(alpha, beta) posterior per arm. Beta is the conjugate prior for the Bernoulli likelihood, so the posterior remains Beta after each observation, enabling cheap exact updates — alpha++ on success, beta++ on failure.

Lai and Robbins (1985) proved that for any consistent policy, lim inf E[R(T)] / ln(T) >= sum_{i: mu_i < mu*} [Delta_i / KL(nu_i || nu*)], where KL is the KL-divergence between reward distributions. This Omega(ln T) lower bound means no algorithm can achieve sub-logarithmic regret; KL-UCB and Thompson Sampling match it asymptotically, while UCB1 is optimal up to a constant factor.

In stochastic MABs, rewards are drawn i.i.d. from fixed unknown distributions. In adversarial MABs, rewards are chosen by an adaptive adversary with no distributional assumption; the goal is to minimize regret against the best fixed arm in hindsight. Adversarial settings require hedging algorithms like EXP3 rather than the distributional exploitation of UCB.

EXP3 (Exponential weights for Exploration and Exploitation) maintains weights w_i, selects arm i with probability p_i = (1-gamma)*w_i/sum(w) + gamma/K, then upon observing reward r forms importance-weighted estimate r_hat_i = r/p_i if i was selected (else 0) and updates w_i *= exp(gamma * r_hat_i / K). Its expected regret against any fixed arm is O(sqrt(T * K * ln K)), which is minimax optimal up to constants.

SW-UCB restricts statistics to the most recent tau rounds for each arm, discarding older observations so the algorithm tracks drifting reward distributions. When the total number of change-points Upsilon_T is known and tau is tuned accordingly, regret is O(sqrt(Upsilon_T * K * T * ln T)). A related variant, discounted UCB, exponentially down-weights older rewards instead of hard-windowing.

LinUCB assumes E[r | x, a] = x^T theta_a. It maintains per-arm ridge regression: theta_a = (A_a)^{-1} b_a, where A_a accumulates x*x^T and b_a accumulates x*r. The UCB index is x^T theta_a + alpha * sqrt(x^T A_a^{-1} x), where the second term is the confidence ellipsoid half-width. The arm maximizing this index is selected, balancing posterior mean and uncertainty.

# UCB index for arm a given context x
index_a = x @ theta_a + alpha * np.sqrt(x @ np.linalg.solve(A_a, x))

Bayesian regret averages regret over a prior on the unknown arm means: BR(T) = E_{theta ~ prior}[R(T, theta)]. Frequentist regret is a worst-case bound over all theta. Thompson Sampling achieves O(sqrt(K*T*ln K)) Bayesian regret (Russo & Van Roy 2014); UCB1 achieves O(sqrt(K*T*ln T)) worst-case frequentist regret for any theta.

NeuralUCB (Zhou et al., 2020) uses the Neural Tangent Kernel of an overparameterized network to define a confidence ellipsoid in gradient feature space. The UCB bonus is alpha * ||phi(x)||_{Z_t^{-1}} where phi(x) is the normalized gradient feature vector of the network and Z_t accumulates outer products of these gradient features. Under the NTK approximation, the network behaves like a linear model in this feature space, yielding O(tilde{O}(sqrt(T))) regret.

In fixed-budget BAI, the learner has exactly T pulls and must output the best arm minimizing error probability. In fixed-confidence BAI, the learner must identify the best arm with probability >= 1-delta using the fewest pulls possible, minimizing sample complexity. The two formulations are fundamentally different: Sequential Halving is near-optimal for fixed-budget; LUCB/lil'UCB for fixed-confidence.

In a combinatorial bandit the learner selects a super-arm S (a subset of base arms), observes rewards for chosen base arms, and receives combined reward f(S). CUCB maintains UCB indices per base arm and uses an offline combinatorial oracle to maximize f(S) over these upper bounds. Under monotonicity and bounded smoothness of f, CUCB achieves O(sqrt(K*T*ln T)) regret.

KL-UCB uses the index max{mu : n_i * KL(mu_hat_i || mu) <= ln(t) + c*ln(ln(t))}, rather than the Hoeffding-based sqrt bonus in UCB1. KL-UCB matches the Lai-Robbins asymptotic lower bound for one-parameter exponential families (Bernoulli, Poisson), while UCB1 is suboptimal by a constant factor. KL-UCB is strictly better for bounded rewards like Bernoulli.

GP-UCB (Srinivas et al., 2010) models the reward function as a Gaussian process. At each round it selects a_t = argmax [mu_{t-1}(x) + beta_t^{1/2} * sigma_{t-1}(x)] where mu and sigma are GP posterior mean and std. Cumulative regret is O*(sqrt(T * gamma_T)) where gamma_T is the maximum information gain: O(log^{d+1} T) for the squared-exponential kernel, O(T^{alpha}) for some alpha < 1 for the Matérn kernel.

Use a Gaussian prior N(mu_0, sigma_0^2) on each arm's mean. After n_i pulls with sample mean x_bar_i, the posterior is N(mu_n, sigma_n^2) where 1/sigma_n^2 = 1/sigma_0^2 + n_i/sigma^2 and mu_n = sigma_n^2 * (mu_0/sigma_0^2 + n_i*x_bar_i/sigma^2). Sample theta_i from each posterior and pull the arm with the largest sample. Gaussian-Gaussian is conjugate so updates are exact and O(1) per step.

sigma_n2 = 1.0 / (1/sigma0**2 + n[i]/sigma**2)
mu_n = sigma_n2 * (mu0/sigma0**2 + n[i]*xbar[i]/sigma**2)
theta_i = np.random.normal(mu_n, np.sqrt(sigma_n2))

In restless bandits each arm evolves as a Markov chain regardless of whether it is pulled. The Whittle index for arm i in state s is the subsidy lambda* making it equally optimal to pull or not pull arm i. The policy selecting the m arms with highest indices is asymptotically optimal as K->inf (m/K fixed) under Whittle's indexability condition — the pull region must be a threshold in the subsidy — proven by Weber and Weiss (1990).

Successive Elimination maintains an active set of arms; in each phase it pulls all active arms equally and eliminates any arm whose UCB falls below the LCB of any other active arm. This continues until one arm remains. It achieves O(H_1 * ln(K/delta)) sample complexity where H_1 = sum_i 1/Delta_i^2, matching information-theoretic lower bounds up to log factors.

LinTS maintains a Gaussian posterior theta ~ N(mu_t, v^2 * A_t^{-1}) where A_t is the ridge gram matrix. At each step it samples theta_tilde from the posterior and selects a_t = argmax_{a} x_{a,t}^T theta_tilde. Agrawal and Goyal (2013) prove LinTS achieves O(d * sqrt(T) * ln^{3/2}(T)) regret with high probability, matching LinUCB up to polylog factors.

theta_tilde = np.random.multivariate_normal(mu_t, v**2 * np.linalg.inv(A_t))
arm = np.argmax([x[a] @ theta_tilde for a in range(K)])

Bandit algorithms continuously allocate more traffic to better-performing variants during the experiment, reducing cumulative regret (lost conversions/revenue) compared to A/B tests with fixed traffic splits. They adapt in real time without a pre-determined sample size. The tradeoff is that adaptive sampling complicates frequentist inference — p-values and CIs require correction (e.g., via anytime-valid sequential testing).

IPS estimates the value of target policy pi_e using logged data from behavior policy pi_b: V_IPS = (1/T) * sum_t [r_t * pi_e(a_t|x_t) / pi_b(a_t|x_t)]. It is unbiased under the overlap condition (pi_b(a|x) > 0 wherever pi_e selects a). Its key limitation is high variance when importance weights are large, often mitigated by doubly-robust estimators that combine IPS with a direct reward model.

V_IPS = np.mean(rewards * (pi_e / pi_b))  # pi_e, pi_b are per-step probabilities

A decaying schedule reduces epsilon over time as estimates improve. With epsilon_t = 1/sqrt(t), the cumulative exploration budget sums to O(sqrt(T)), meaning exploration naturally self-limits as the algorithm gains confidence. The schedule with a proven worst-case regret guarantee is epsilon_t = min(1, (cK/t)^{1/3}), yielding O((KT^2)^{1/3}) = O(K^{1/3} T^{2/3}) regret. All decaying epsilon-greedy variants are dominated asymptotically by UCB or Thompson Sampling, which achieve O(sqrt(K*T*ln T)).

epsilon_t = min(1.0, 1.0 / np.sqrt(t + 1))

In batched bandits the learner makes decisions in B rounds; within each batch all decisions are fixed before observing any new rewards, modeling parallel/distributed systems with delayed feedback. With B = O(log log T) batches, regret of O(sqrt(T * ln T)) is achievable — nearly identical to the sequential setting — while a single batch yields O(T^{2/3}) regret.

Under epsilon-misspecification (best linear approximation has max error epsilon), LinUCB regret becomes O(d * sqrt(T) + epsilon * T). The linear term epsilon*T dominates for large misspecification, making regret grow linearly in T. Remedies include richer feature maps, kernelized UCB, or neural bandits that can represent the true non-linearity.

In dueling bandits feedback is a pairwise preference (arm a_1 preferred over a_2) rather than a scalar reward — directly modeling the human preference oracle in RLHF. RLHF trains a reward model from pairwise human comparisons, which is equivalent to best arm identification in a dueling bandit where arms are LLM outputs. The Condorcet winner (preferred over all others) corresponds to the RLHF-optimal response.

The oracle policy that always pulls the optimal arm has exactly zero regret, since R(T) = sum_t [mu* - mu_{a_t}] = 0 when a_t = a* for all t. All bandit algorithms aim for sub-linear regret R(T)/T -> 0, meaning they asymptotically match the oracle despite not knowing the true arm means.

Softmax selects arm i with probability proportional to exp(mu_hat_i / tau). As tau -> 0, probability concentrates on the highest-estimate arm (pure exploitation). As tau -> inf, the distribution approaches uniform (pure exploration). Unlike epsilon-greedy, Softmax is sensitive to reward scale and often requires normalization or careful tuning of tau.

probs = np.exp(mu_hat / tau); probs /= probs.sum()
arm = np.random.choice(K, p=probs)

H_1 = sum_{i=1}^{K} 1/Delta_i^2 where Delta_i = mu* - mu_i for suboptimal arms (and Delta_{i*} is the gap to the second-best arm for the optimal arm). The sample complexity of any correct (delta-confident) BAI algorithm is Omega(H_1 * ln(1/delta)). This captures that arms with small gaps require far more pulls to distinguish from the best arm, dominating total complexity.

OFU states: act as if the environment is as good as it could plausibly be given observed data. In UCB, this means selecting the arm with the highest upper confidence bound (empirical mean + bonus), not just the highest empirical mean. If the optimism is correct, we exploit the best arm; if wrong, the pull provides information shrinking the bonus — a self-correcting mechanism yielding O(ln T) regret.

In cascading bandits the learner selects an ordered list of K items; the user examines items top-to-bottom and clicks the first relevant one (cascade click model). Feedback reveals only the click position or absence. CASCADEUCB (Kveton et al., 2015) achieves O(sqrt(T * K * ln T)) regret. They model user attention in recommendation systems, search ranking, and ad placement.

One approach is to meta-learn a prior over arm parameters from past tasks, then use this informed prior in Thompson Sampling or Bayesian UCB for the new task. For contextual linear bandits, prior-task data can initialize the gram matrix A_0 and vector b_0 of LinUCB, shrinking the confidence ellipsoid and reducing exploration proportional to task similarity. Formal guarantees exist via transfer regret bounds.

In sleeping bandits only a subset of arms (the awake arms) is available each round, with availability determined stochastically or adversarially. Standard UCB may attempt unavailable arms. Modified algorithms (e.g., AAUCB) condition UCB indices on available arms and redefine the regret baseline as the best available arm per round rather than the global best arm, since the latter is unachievable when it is asleep.

# At each round t, only pull from available_arms[t]
active = available_arms[t]
arm = active[np.argmax([ucb_index(i, t) for i in active])]