Multi-Armed Bandits and Regret

A gambler stands before a row of slot machines, each with an unknown payout rate. Pull the wrong arm too often and money is wasted. Pull only the one that looked best early on, and a better machine may never be discovered. This is the multi-armed bandit problem. It is the simplest possible laboratory for studying the Exploration-Exploitation Dilemma. It avoids the complications of changing states. Bandits matter far beyond casinos. Online platforms use bandit algorithms to choose which advertisement, headline, or recommendation to show next. They update beliefs from every click or non-click. Clinical trials use bandits to allocate patients to treatments. At the same time, they learn which treatment works best. This saves lives that a rigid fixed-allocation trial would sacrifice. Because the setting has no state transitions, it isolates the core question of reinforcement learning. That question is how to act under uncertainty about rewards. This is separate from the harder question of how to act under uncertainty about future states. That harder question is the subject of full Markov Decision Processes. This article builds the stateless bandit model from scratch. It covers how to estimate action values from samples. It presents two classical strategies for choosing actions: epsilon-greedy and Upper Confidence Bound. It also introduces the formal yardstick used to judge them — regret. Regret is the cumulative gap between the rewards actually received and the rewards an all-knowing agent could have collected. Understanding regret bounds here lays the conceptual groundwork for value estimation. It also supports Rewards and Returns in the full sequential setting. By the end, you will be able to derive the sample-average update rule. You will implement and reason about epsilon-greedy and UCB1. You will prove why their regret grows only logarithmically in the best cases. You will also recognize the practical traps that break these algorithms in deployment. These traps include non-stationarity, poor initialization, and misjudged exploration constants.

Key takeaways

A k-armed bandit has k actions ("arms"), each with a fixed but unknown reward distribution; there is no state.
Action-value estimation tracks $Q_t(a)$ , the running sample average of rewards from arm $a$ , updated incrementally in $O(1)$ time and space per arm.
Epsilon-greedy explores uniformly at random with probability $\varepsilon$ and exploits the best-known arm otherwise; simple but exploration never stops.
UCB1 picks the arm maximizing an optimism bonus $Q_t(a) + c\sqrt{\ln t / N_t(a)}$ , achieving expected regret $O(\log t)$ .
Regret $R_T = T\mu^* - \mathbb{E}\left[\sum_{t=1}^T r_t\right]$ measures cumulative reward lost versus always playing the best arm.
Logarithmic regret is provably the best achievable rate for any algorithm on stochastic bandits with a gap between arms.

The core insight

Regret converts the vague goal of "balance exploration and exploitation" into a precise, provably minimizable quantity — the cumulative gap versus always pulling the best arm.

The idea

A k-armed bandit is a repeated decision problem with $k$ possible actions, called arms. At each time step $t = 1, 2, \dots, T$ , an agent selects an arm $A_t \in \{1, \dots, k\}$ and receives a reward $R_t$ drawn from a fixed but unknown probability distribution associated with that arm. Crucially, there is no notion of state: the reward distribution of arm $a$ does not depend on which arms were chosen before, so the problem has no transitions and no long-term consequences beyond the immediate reward. This statelessness is what separates bandits from a full Markov Decision Process, where actions also change the state the agent finds itself in. Each arm $a$ has a true action value

q_*(a) = \mathbb{E}[R_t \mid A_t = a],

the mean reward that arm produces. If $q_*(a)$ were known for every arm, the optimal policy would be trivial: always pull $\arg\max_a q_*(a)$ . The entire difficulty is that $q_*(a)$ is unknown and must be estimated from experience, and every pull spent estimating a mediocre arm is a pull not spent collecting reward from a better one. This tension is a direct instance of the exploration-exploitation dilemma: exploration gathers information to improve future decisions, exploitation uses current information to maximize immediate reward, and no single action can do both at once. To measure how well an algorithm resolves this tension, we use regret, the cumulative shortfall relative to an oracle that always plays the best arm:

R_T = T\,\mu^{*} - \mathbb{E}\left[\sum_{t=1}^{T} R_t\right], \qquad \mu^{*} = \max_a q_*(a).

An equivalent and often more useful decomposition writes regret in terms of per-arm suboptimality gaps $\Delta_a = \mu^* - q_*(a)$ and expected pull counts $\mathbb{E}[N_T(a)]$ :

R_T = \sum_{a} \Delta_a\, \mathbb{E}[N_T(a)].

This says regret accumulates only from pulling suboptimal arms, at a rate proportional to how far below optimal they are. A good algorithm must therefore make $\mathbb{E}[N_T(a)]$ grow slowly for every arm with $\Delta_a > 0$ , while still growing enough to be statistically sure it is not the best arm.

How it works

The two pieces every bandit algorithm needs are value estimation — maintaining a running estimate $Q_t(a)$ of $q_*(a)$ — and an action-selection rule that uses those estimates to pick $A_t$ .

Sample-average estimation. After arm $a$ has been pulled $n$ times with observed rewards $R_1, \dots, R_n$ , the natural estimator is the sample mean:

Q_{n+1}(a) = \frac{1}{n}\sum_{i=1}^n R_i.

Storing all past rewards is wasteful. The estimate can instead be updated incrementally in constant time and space:

Q_{n+1} = Q_n + \frac{1}{n}\left(R_n - Q_n\right).

This is a special case of the general update rule NewEstimate ← OldEstimate + StepSize × (Target − OldEstimate), which recurs throughout reinforcement learning, including in Rewards and Returns-based value updates for full MDPs.

Epsilon-greedy action selection exploits the current best estimate most of the time, but explores uniformly at random with small probability $\varepsilon$ :

A_t = \begin{cases} \arg\max_a Q_t(a) & \text{with probability } 1-\varepsilon \\ \text{uniform random arm} & \text{with probability } \varepsilon. \end{cases}

UCB1 (Upper Confidence Bound) instead selects the arm with the highest optimistic estimate, adding a bonus that shrinks as an arm is pulled more:

A_t = \arg\max_a \left[ Q_t(a) + c \sqrt{\frac{\ln t}{N_t(a)}} \right].

The bonus term is large for arms pulled rarely (encouraging exploration) and shrinks as $N_t(a)$ grows (allowing exploitation to dominate once an arm is well understood). The constant $c$ controls the exploration strength; $c=\sqrt{2}$ is the classical choice matching the theoretical derivation under bounded rewards in $[0,1]$ . ```

# UCB1 bandit algorithm

# k : number of arms

# T : total time horizon

# c : exploration constant (e.g. sqrt(2)) initialize Q[1..k] = 0 # estimated action values initialize N[1..k] = 0 # pull counts

# Phase 1: play each arm once to avoid division by zero for a in 1..k: r = pull(a) N[a] = 1 Q[a] = r

# Phase 2: main loop for t in (k+1)..T:

# choose arm maximizing UCB score scores = [ Q[a] + c * sqrt(ln(t) / N[a]) for a in 1..k ] A = argmax(scores) r = pull(A) N[A] = N[A] + 1 Q[A] = Q[A] + (r - Q[A]) / N[A] # incremental sample average return Q, N ``` ```

# Epsilon-greedy bandit algorithm

# k : number of arms

# T : total time horizon

# epsilon : exploration probability initialize Q[1..k] = 0 initialize N[1..k] = 0 for t in 1..T: if random_uniform(0,1) < epsilon: A = random_arm(1..k) # explore else: A = argmax(Q) # exploit (break ties randomly) r = pull(A) N[A] = N[A] + 1 Q[A] = Q[A] + (r - Q[A]) / N[A] return Q, N ``` Both loops are identical in structure — a value-estimation update wrapped around an action-selection rule — which is exactly the template every reinforcement learning algorithm follows, bandits included.

Figure

UCB1 decision loop and confidence-bound shrinkage

Complexity & correctness

Time and space complexity. Both epsilon-greedy and UCB1 use $O(k)$ space, storing one $Q$ estimate and one count $N$ per arm — no history of individual rewards is retained. Per-step time is $O(k)$ : epsilon-greedy scans all arms to find the current max, and UCB1 recomputes the bonus term for all $k$ arms at every step (the $\sqrt{\cdot}$ and $\log$ evaluations are $O(1)$ per arm under standard floating-point arithmetic). Over a horizon $T$ , total time is $O(kT)$ , and this is essentially unavoidable if the algorithm must consider every arm's current estimate before acting.

Correctness of the incremental update. The recurrence

Q_{n+1} = Q_n + \tfrac{1}{n}(R_n - Q_n)

is correct by induction: the base case $Q_1 = R_1$ trivially matches the sample mean of one observation. Assuming $Q_n$ is the mean of the first $n-1$ rewards, algebra gives

Q_n + \tfrac{1}{n}(R_n - Q_n) = \tfrac{n-1}{n}Q_n + \tfrac{1}{n}R_n = \tfrac{1}{n}\sum_{i=1}^{n} R_i,

which is exactly the sample mean of $n$ rewards, closing the induction. By the law of large numbers, $Q_n(a) \to q_*(a)$ almost surely as $n \to \infty$ , so estimates become arbitrarily accurate given enough pulls of each arm.

Why epsilon-greedy has linear regret. Because $\varepsilon$ is fixed, the algorithm explores a uniformly random arm with constant probability $\varepsilon$ at every single step, forever. Even after $Q_t$ has converged to $q_*$ for all arms, a constant fraction $\varepsilon(k-1)/k$ of the remaining pulls still go to suboptimal arms. This forces

R_T = \Theta(\varepsilon T),

linear in $T$ — the mistake never stops, only its per-step probability stays fixed. Decaying $\varepsilon_t = c/t$ can recover logarithmic regret, but requires tuning the decay schedule to the (unknown) gaps $\Delta_a$ , which is exactly the fragility UCB1 is designed to avoid.

Why UCB1 achieves logarithmic regret. The key idea is optimism in the face of uncertainty: since the true mean $q_*(a)$ lies within the confidence interval $[Q_t(a) - c\sqrt{\ln t/N_t(a)}, \, Q_t(a) + c\sqrt{\ln t/N_t(a)}]$ with high probability (by Hoeffding's inequality for bounded rewards), acting on the upper bound never rules out an arm that could secretly be optimal. A sketch of the argument: if a suboptimal arm $a$ (with gap $\Delta_a > 0$ ) is chosen at time $t$ , it must be that its UCB score exceeds the optimal arm's true mean, i.e.

Q_t(a) + c\sqrt{\frac{\ln t}{N_t(a)}} \ge \mu^*.

Since $Q_t(a)$ concentrates around $q_*(a) = \mu^* - \Delta_a$ , this forces the bonus term $c\sqrt{\ln t / N_t(a)}$ to be at least roughly $\Delta_a$ , which upper-bounds $N_t(a)$ :

N_t(a) \le \frac{4c^2 \ln t}{\Delta_a^2} + O(1).

Summing $\Delta_a \cdot N_T(a)$ over suboptimal arms yields the classical UCB1 bound (Auer, Cesa-Bianchi & Fischer, 2002):

R_T \le \sum_{a:\, \Delta_a > 0} \left( \frac{8\ln T}{\Delta_a} \right) + \left(1 + \frac{\pi^2}{3}\right)\sum_a \Delta_a.

The dominant term grows as $O(\log T)$ — each suboptimal arm is pulled only $O(\log T / \Delta_a^2)$ times, not a constant fraction of all pulls. This logarithmic rate is optimal: the Lai–Robbins lower bound (1985) shows that any algorithm satisfying mild consistency conditions must have

\liminf_{T\to\infty} \frac{R_T}{\ln T} \ge \sum_{a:\Delta_a>0} \frac{\Delta_a}{\mathrm{KL}(q_*(a) \,\|\, \mu^*)},

so no algorithm can do asymptotically better than logarithmic regret in the stochastic bandit setting. UCB1's regret matches this rate up to constants.

Tradeoffs. UCB1's guarantee assumes bounded, stationary reward distributions; the confidence radius derivation relies on Hoeffding's inequality, which needs a known bound on reward range. If rewards are unbounded or heavy-tailed, the bonus term must be redesigned (e.g., using empirical Bernstein bounds). If the environment is non-stationary — true means drift over time — both algorithms degrade, since old data is trusted as much as new data; sliding-window or discounted variants are needed in that regime.

Worked example

Consider a 3-armed bandit with true (unknown to the agent) means $q_*(1) = 0.2$ , $q_*(2) = 0.5$ , $q_*(3) = 0.8$ (Bernoulli rewards, so each pull returns 0 or 1). Arm 3 is optimal, with $\mu^* = 0.8$ . Suppose UCB1 with $c = \sqrt{2}$ is run and, after the mandatory first pass (one pull per arm), the observed rewards were: arm 1 → 0, arm 2 → 1, arm 3 → 1. State after $t = 3$ :

Arm	N	Q (sample mean)	Gap Δ
1	1	0.0	0.8
2	1	1.0	0.3
3	1	1.0	0.0

At $t = 4$ , compute UCB scores with bonus $c\sqrt{\ln t / N}$ , $\ln 4 \approx 1.386$ :

Arm	Q	bonus = √2·√(1.386/N)	UCB score
1	0.0	√2·√1.386 = 1.665	1.665
2	1.0	1.665	2.665
3	1.0	1.665	2.665

Arms 2 and 3 tie at the top (ties broken randomly); say arm 3 is chosen and returns reward 1. Update: $N_3 = 2$ , $Q_3 = 1.0 + \tfrac{1}{2}(1 - 1.0) = 1.0$ . At $t = 5$ , $\ln 5 \approx 1.609$ :

Arm	Q	bonus	UCB score
1	0.0	√2·√1.609 = 1.793	1.793
2	1.0	1.793	2.793
3	1.0	√2·√(1.609/2) = 1.268	2.268

Now arm 2 has the highest score because its lower pull count keeps its bonus large — the algorithm gives arm 2 another chance despite arm 3's strong start, which is exactly the "optimism" mechanism preventing premature commitment. Suppose arm 2 is pulled and returns 0 (a plausible outcome since $q_*(2)=0.5$ ). Update: $N_2 = 2$ , $Q_2 = 1.0 + \tfrac12(0 - 1.0) = 0.5$ . Over many more steps, as $N_1$ stays small (arm 1's poor early result keeps its score low relative to the others once bonuses shrink), $N_2$ grows only until its confidence interval no longer overlaps arm 3's, and $N_3$ dominates the pull count — matching the theoretical prediction that suboptimal arms receive only $O(\ln T/\Delta_a^2)$ pulls: arm 1 (large gap 0.8) is pulled rarely, arm 2 (moderate gap 0.3) is pulled a bit more before being abandoned, and arm 3 absorbs almost all remaining pulls.

Common pitfalls & traps

Pitfall	Why it happens	Fix
Fixed ε forever	Constant exploration rate never decays, causing linear regret even after convergence	Decay ε over time, or switch to UCB1
Dividing by zero on first pull	Naive incremental update assumes $N \ge 1$ before updating	Explicitly initialize by pulling each arm once
Wrong reward-range assumption in UCB	Confidence bound derivation assumes bounded rewards (e.g., $[0,1]$ ); using it on unbounded rewards invalidates the bound	Normalize rewards, or use a variant with empirical variance (UCB-V, KL-UCB)
Optimistic initialization miscounted as real data	Setting $Q_1(a)$ very high to force exploration, but forgetting it biases early average estimates	Track it as a deliberate, temporary bias; it fades after enough pulls
Ignoring non-stationarity	Reward means silently drift, but sample-average weights all past data equally, going stale	Use a constant step size or sliding window instead of $1/n$
Treating regret as if it converges to zero	Regret is cumulative; even a perfect algorithm has nonzero — just slow-growing — regret	Report regret rate (e.g. $O(\log T)$ ), not "regret equals zero"

Pioneers & history

Origins · 1 minHerbert Robbins and how this was discovered

Herbert Robbins

1915–2001 · Columbia University, mathematical statistics

Herbert Robbins introduced the multi-armed bandit problem in a 1952 paper and, decades later with Tze Leung Lai, proved the asymptotic lower bound on regret that every subsequent bandit algorithm is measured against.

History

1933

— William R. Thompson proposes randomized probability matching for clinical trial allocation, later known as Thompson Sampling.

1952

— Herbert Robbins formalizes the sequential design problem that becomes the multi-armed bandit.

1985

— Tze Leung Lai and Herbert Robbins prove the asymptotic logarithmic lower bound on regret for consistent policies.

1995

— Gittins index theory matures, giving an exact Bayesian-optimal solution for discounted bandits.

2002

— Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer publish UCB1 with a finite-time logarithmic regret bound.

Where this matters

Online advertising and content-recommendation platforms run bandit algorithms at massive scale to choose which ad, article, or product to show, treating each option as an arm and each click or purchase as a reward, continuously updating $Q_t(a)$ from live traffic. A/B testing frameworks increasingly use bandit-style adaptive allocation instead of fixed 50/50 splits, routing more traffic to the better-performing variant as evidence accumulates, which reduces the cost of experimentation. Clinical trial design uses bandit-inspired adaptive randomization to shift patient allocation toward more effective treatments as data arrives, an application close to Robbins's original motivation. Bandit algorithms also underlie hyperparameter tuning tools that allocate a limited compute budget across configurations, treating each configuration as an arm whose "reward" is validation performance. Beyond these direct uses, the exploration bonus idea in UCB1 generalizes to reinforcement learning agents navigating full Markov Decision Processes, where analogous optimism-based exploration strategies encourage visiting under-explored states — a bridge from the stateless setting studied here to sequential decision making built on Rewards and Returns.

Ask the tutor: How would the regret bound change if two arms have nearly identical means (a very small gap Δ)?

Why is regret defined relative to always playing the best arm, rather than some absolute reward target?

Regret needs a meaningful baseline, and the tightest fair one is the reward an oracle with full knowledge would collect — always pulling the single best arm. Comparing against an absolute number (like "reward of 1 per step") would conflate the difficulty of the problem itself (how good the best arm actually is) with the quality of the algorithm's exploration strategy. By subtracting $T\mu^*$ , regret isolates exactly the cost of not knowing which arm is best, which is the quantity an exploration algorithm can actually control. It also makes cross-problem comparison possible: an algorithm with regret $O(\log T)$ is well-behaved regardless of the specific reward distributions involved.

Does logarithmic regret mean the algorithm eventually stops making mistakes?

Not exactly — it means the rate at which mistakes accumulate slows dramatically, not that mistakes stop. UCB1's regret bound shows each suboptimal arm is pulled only $O(\ln T / \Delta_a^2)$ times in total, so the number of exploratory mistakes keeps growing, just extremely slowly compared to $T$ . Since $\ln T$ grows unboundedly (just very slowly), regret is never truly zero at any finite time; it merely becomes negligible relative to the total reward collected, which grows linearly with $T$ . This is why $O(\log T)$ is considered the gold standard rather than an unreachable ideal of exactly zero regret.

How should the exploration constant c in UCB1 be chosen in practice?

The theoretical value $c = \sqrt{2}$ comes directly from a Hoeffding-inequality derivation assuming rewards lie in $[0,1]$ ; it guarantees the stated logarithmic regret bound under that assumption. In practice, this constant is often conservative, and smaller values of $c$ can perform better empirically by exploring less aggressively when reward variance is low. If rewards are not bounded in $[0,1]$ , they should first be normalized, or $c$ should be rescaled to match the actual reward range, otherwise the confidence bound no longer has the guarantee it was derived for. Many practitioners tune $c$ via held-out simulation rather than relying purely on the theoretical constant.

Can Thompson Sampling replace UCB1, and how does it differ conceptually?

Thompson Sampling takes a Bayesian approach: it maintains a posterior distribution over each arm's true mean, samples one value per arm from these posteriors at each step, and pulls the arm with the highest sampled value. This differs from UCB1's deterministic optimism bonus — instead of a fixed confidence-interval formula, uncertainty is expressed through randomness in the sampling itself, naturally shrinking as more data narrows each posterior. Thompson Sampling often matches or beats UCB1 empirically and also achieves near-optimal logarithmic regret under mild conditions, but it requires specifying a prior and computing posterior updates, adding modeling overhead UCB1 avoids.

What happens to these algorithms if the reward distributions change over time (non-stationary bandits)?

Both epsilon-greedy and UCB1, as presented, assume stationary reward distributions and use a sample average that weights all historical observations equally, via the $1/n$ step size. If an arm's true mean drifts, old observations become misleading, and the $1/n$ weighting makes the estimate increasingly slow to adapt as $n$ grows, since each new observation contributes less and less. The standard fix is to replace the $1/n$ step size with a small constant step size $\alpha$ , which gives exponentially-decaying weight to older rewards and lets the estimate track a moving target, at the cost of never fully converging even in a stationary environment.

Why does the mandatory "play each arm once" initialization matter for UCB1?

The UCB1 formula divides by $N_t(a)$ , which is undefined at $N_t(a) = 0$ ; some implementations avoid this by treating any unpulled arm as having infinite (or maximal) priority, but the simplest and most common fix is to force one pull of every arm before applying the formula. This initialization also serves a statistical purpose: without at least one observation, there is no basis at all for even a rough interval around $q_*(a)$ , so the optimism principle has nothing to be optimistic about. Skipping this step, or initializing $N_t(a)$ incorrectly, is a common source of divide-by-zero bugs or degenerate always-explore-arm-1 behavior in naive implementations.