What it actually does
Everything else in this category spends its effort on credit assignment across time. A bandit has no time to assign across — you pick an arm, you get a reward, and the next decision starts from the same place. What is left when the temporal structure is gone is the exploration-exploitation trade in its purest form: you can only learn about an arm by pulling it, and every pull spent learning is a pull not spent earning. Three answers matter. Epsilon-greedy explores at random with some probability, which is simple and wasteful, because it explores arms it already knows are bad just as often as promising ones. UCB is optimistic in the face of uncertainty: score each arm by its estimated mean plus a confidence bonus that shrinks as it is pulled, then take the best score. An arm that looks bad but has barely been tried keeps a high bonus and gets tried again; an arm that has been tried and is genuinely bad falls away. Thompson sampling is Bayesian and even simpler to state: keep a posterior over each arm's value, draw one sample from each, play the argmax of the samples. Arms the posterior is uncertain about sometimes draw high and get played, in exact proportion to the probability they are best. What makes this group worth studying is that it is the only one here with meaningful theory — regret bounds that hold, are tight, and are actually predictive of behaviour — and simultaneously the group that appears most often in production, usually in contextual form. It is also the group most often reached for wrongly, because the assumption it rests on, that actions do not change the state, fails quietly rather than loudly.
- Actions do not change the state — the defining assumption, what buys the regret guarantees, and the one most likely to be quietly false
- Arm means are stationary, or an explicit forgetting mechanism is present; every bound here is stated against a fixed best arm
- Feedback arrives quickly enough relative to the decision rate that the posterior is not badly stale when the next decision is made
- Rewards are bounded or sub-Gaussian, which is what the concentration inequalities behind the confidence bonus require
- The arm set is fixed, or new arms are explicitly initialized with an optimistic prior rather than left to accumulate history
- Arms are independent unless a contextual model is used, so near-duplicates genuinely do waste evidence
Loss function
The decomposition on the right is the most useful thing in the formula, because it says exactly where regret comes from: each suboptimal arm contributes its gap multiplied by how often it was played. Two consequences follow. An arm that is nearly as good as the best is cheap to keep exploring — the gap is small, so pulling it costs almost nothing — while an arm that is much worse must be abandoned fast. And no algorithm can do better than logarithmic pulls of a suboptimal arm, which is the lower bound: you cannot become confident an arm is worse without sampling it enough times to distinguish it, and the number of samples needed scales as one over the gap squared. UCB achieves that bound by construction, and the bonus term is doing precisely this accounting: it is the width of a confidence interval, so an arm stops being played once its upper confidence bound falls below the best arm's mean. Thompson sampling achieves it too, by an entirely different route — it plays each arm with the posterior probability that it is best, which is exactly the amount of exploration the uncertainty justifies. The two are worth holding side by side because they are the same idea in two languages, frequentist and Bayesian, and the Bayesian one is usually better in practice while the frequentist one is easier to reason about. The limitation is in the first symbol: regret is defined against a fixed best arm, so all of this assumes the arm means are stationary, and none of it survives a world where the best arm changes without an explicit mechanism for forgetting.
- cumulative regret: what an oracle always playing the best arm would have earned, minus what was actually earned — the quantity every guarantee here is stated about
- the gap between the best arm and arm a; regret decomposes into gap times number of pulls, which is why a nearly-tied arm is cheap to be wrong about
- how many times arm a was pulled — the only thing an algorithm controls, and the whole design problem is keeping it small for bad arms
- the best arm's mean reward, unknown; the regret is defined against it and measured only in hindsight
How it is minimized
Sequential decisions under uncertainty: optimism via confidence bounds (UCB), probability matching via posterior sampling (Thompson), or random exploration (epsilon-greedy), with contextual variants fitting a per-arm model of reward given features
- the confidence radius: wide for a rarely pulled arm, shrinking as the square root of its pull count, growing slowly in total time so nothing is abandoned permanently
- one draw from arm a's posterior — Thompson plays an arm with exactly the probability that it is best, which is probability matching
- the running mean, updated incrementally; storing a sum and a count is all the state a non-contextual bandit has
- total pulls so far, not pulls of this arm — the bonus grows for every arm as time passes, which is what keeps an abandoned arm eventually revisited
Three algorithms, and the differences between them are more instructive than any one alone. Epsilon-greedy is the baseline everyone writes first and it is genuinely bad in a specific way: it spends its exploration budget uniformly over arms, so an arm already known to be terrible is explored exactly as often as one that is plausibly best. It has linear regret with a fixed epsilon and needs an annealing schedule to be competitive, which is one more thing to tune. UCB replaces random exploration with directed exploration: the bonus is a confidence radius, so exploration goes where uncertainty is, and the algorithm is deterministic, which makes it reproducible and auditable — genuinely useful properties in production. Thompson sampling is usually the best-performing of the three and the easiest to extend, because the whole algorithm is "sample from the posterior and act greedily on the sample", which works for any model you can put a posterior on. It also handles delayed and batched feedback more gracefully than UCB, since several decisions drawn from the same posterior naturally diversify, where UCB would deterministically pick the same arm every time until the batch lands. The contextual extension is what actually ships: model reward as a function of features and arm, maintain uncertainty over the model parameters, and apply the same optimism or sampling to the predicted reward. LinUCB and linear Thompson sampling are the standard forms, and the reason they stay linear in practice is that the uncertainty quantification is what matters, and it is exactly what gets hard when the model gets deep.
exploration constant
The multiplier on UCB's confidence radius. The theoretical value is often too exploratory in practice, and tuning it down is standard and worth doing deliberately rather than accidentally (0.5 to 2.0 times the theoretical bonus)
prior
Thompson sampling's starting belief per arm. A Beta(1,1) is uninformative; a stronger prior is how domain knowledge enters and how a cold start is survived (Beta(1,1), or matched to a known base rate)
epsilon and its schedule
For the baseline. Fixed epsilon gives linear regret; a 1/t decay is needed to be competitive, which is a hyperparameter the other two do not have (0.1 fixed, or decaying as 1/t)
discount or sliding window
The nonstationarity mechanism. Without one, an arm with a long history cannot be overtaken when the world changes, because its confidence interval has already collapsed (discount 0.99, or a window of recent pulls)
regularization (contextual)
The ridge term in LinUCB's design matrix. It sets the initial uncertainty and keeps the matrix invertible before enough data has arrived (1.0)
batch size / update cadence
How many decisions are served before the posterior is refreshed. Larger batches are operationally simpler and delay learning, and Thompson tolerates them far better than UCB does (per-request to hourly)
minimum allocation floor
A guaranteed share of traffic per arm. Not in any of the theory, and standard in production because it preserves the ability to detect a change and to estimate every arm (1% to 5% per arm)
This is the only group in this category with guarantees that are both provable and predictive of what actually happens. UCB1 attains regret O(sum over suboptimal arms of log(T) over the gap), which matches the known lower bound up to constants — no algorithm can do better, and the reason is information-theoretic rather than algorithmic. Thompson sampling attains the same asymptotic rate and is typically better in finite time. Epsilon-greedy with a fixed epsilon has linear regret and is only competitive with an annealing schedule. Read these bounds carefully, though, because their assumptions are where deployments fail. They assume stationary arm means: if the best arm changes, an algorithm whose confidence intervals have already collapsed will not notice, and the failure mode is a system confidently serving a formerly-best arm long after it stopped being best. A discount factor or a sliding window is the standard fix and it costs some asymptotic regret to buy responsiveness. They assume immediate feedback: with delayed rewards, decisions are made against a stale posterior, and Thompson sampling degrades gracefully here while UCB degenerates into pulling the same arm repeatedly. They assume independent arms, so a hundred near-identical variants are each explored separately rather than sharing evidence, which is what the contextual form fixes. And they assume the arm set is fixed, so a new arm added mid-run has no history and either needs an optimistic prior or will be starved. Perhaps most importantly, they say nothing about the quality of the estimates produced: a bandit deliberately stops sampling arms it believes are bad, so the data it leaves behind supports a confident statement about the winner and a very weak one about everything else.
Non-contextual: O(K) per decision to score the arms and O(1) to update, with O(K) memory holding a running mean and a count per arm. This is cheap enough to run inside a request handler and is one of the reasons bandits ship where the rest of this category does not. Contextual LinUCB: maintaining the inverse of a d-by-d design matrix per arm costs O(d^2) per update with a rank-one formula, or O(d^3) if the inverse is recomputed, and scoring is O(K d^2) per decision for the confidence term. Linear Thompson sampling additionally samples from a d-dimensional Gaussian, which needs a factorization of the covariance — O(d^3) if done naively per decision, and O(d^2) if the factor is maintained incrementally. The practical scaling limit is the number of arms times the feature dimension, which is why production systems narrow the arm set with a retrieval stage first and keep the model linear.
How, where, and why it is used
Time-Series Forecasting
AdaptedAllocate a decision — which forecaster to trust, which model to serve — across a set of candidates whose performance is learned online, treating each candidate as an arm and its realized accuracy as the reward.
- Online model selection among competing forecasters, where the best model changes with the regime and a fixed backtest choice goes stale
- Forecast combination with weights adapted online rather than fitted once on history
- Deciding which of several expensive forecasting pipelines to run when only some can be afforded per cycle, which is genuine bandit feedback
- Regime-change detection as a by-product: a persistent shift in which arm wins is a signal in itself
Marked adapted because the honest version of this fit contains a correction worth making. In most forecasting settings the feedback is FULL, not bandit: the outcome is observed, so every candidate forecaster can be scored after the fact, whether or not it was the one served. That is the prediction-with-expert-advice problem, and its right algorithm is exponential weighting over all experts, which has better regret than any bandit algorithm because it uses strictly more information. Reaching for a bandit there is over-general and measurably worse. Genuine bandit feedback appears only when running a candidate is itself costly — an expensive simulation, a paid external forecast, a pipeline that cannot be run for every model every cycle — and then the bandit machinery is correct. The second correction is that forecasting is usually nonstationary by nature, which is the assumption every bound here rests on, so a discounted or sliding-window variant is mandatory rather than optional. Get both of those right and this is a clean, cheap, well-understood way to keep a model portfolio honest; get them wrong and it is a complicated way to underperform a simple weighted average.
- Check whether feedback is really bandit feedback: if every candidate can be scored after the outcome, use exponential weights over experts instead, which strictly dominates
- Use a discounted or sliding-window variant, since forecasting regimes shift and an undiscounted bound assumes they do not
- Define the reward as a proper scoring rule on the forecast, not as accuracy on a threshold, or the allocation optimizes the wrong thing
- Keep an allocation floor per candidate so a model that becomes good again can be noticed
Cumulative realized forecast loss against the best single candidate chosen in hindsight — that difference is the regret and it is the quantity the method is designed to control. Report it against the simple baselines too: a static backtest-selected model and a uniform average, because the adaptive machinery has to beat both to be worth its complexity.
- Using a bandit where full feedback is available, which discards information and underperforms exponential weights
- No discounting, so a candidate that dominated an old regime keeps a collapsed confidence interval and cannot be overtaken
- A reward defined on a metric that is not a proper scoring rule, which makes the allocation optimize something other than forecast quality
- Treating the selection as free when running each candidate has a real cost, which is the thing that made it a bandit in the first place
Anomaly Detection
AdaptedAllocate a fixed investigation budget across candidate alerts, detectors or segments, treating each as an arm and the confirmed-incident rate as the reward, so that triage capacity flows toward the sources that are actually finding things.
- Analyst review queues where only a fraction of alerts can be investigated and the split across detectors is a live decision
- Threshold and detector selection under a fixed alert budget, learned online rather than fixed at deployment
- Cold-start for a newly deployed detector, which needs enough investigated alerts to establish a precision estimate it will otherwise never earn
- Segments or rules whose yield drifts, where an undiscounted allocation keeps serving the detector that used to work
Marked adapted with a precise boundary, because the distinction is the useful part: the bandit does not detect anything. Scoring an observation for how unusual it is has no action and no reward, so nothing here applies to the detector itself. What the bandit does is decide where scarce human attention goes, which is a genuine repeated decision under uncertainty with an observable payoff — did this investigation confirm an incident — and the feedback loop it fixes is real. A triage system that routes purely on estimated precision only ever learns about the detectors it already trusts, so a new or improved detector cannot accumulate the evidence that would justify using it. Directed exploration breaks that, cheaply, on top of whatever scoring already exists. Two cautions. Confirmation is often delayed by days, which favours Thompson sampling heavily and makes the posterior stale in a way the bounds do not model. And the reward must be defined on confirmed outcomes rather than on analyst dispositions, or the allocation optimizes for alerts that are easy to close rather than for incidents that matter.
- Define the reward on confirmed incidents, not on analyst dispositions, or the allocation learns to prefer alerts that close quickly
- Use a discounted variant, since detector yield drifts as the underlying behaviour changes and an undiscounted estimate outlives it
- Prefer Thompson sampling, because investigation outcomes arrive days later and a deterministic rule would serve one detector for the whole delay window
- Keep an allocation floor per detector, or a newly deployed one never accumulates the evidence that would justify it
Confirmed incidents found per unit of investigation capacity, against a uniformly allocated holdout — the holdout is what makes the comparison meaningful and is also the only sample that supports an unbiased precision estimate for every detector. Report time-to-detection separately, since an allocation that maximizes total finds can systematically deprioritize a slow-burning class.
- Treating the detection itself as a bandit problem, when only the allocation of attention is one
- Reward defined on analyst disposition rather than confirmed outcome, which optimizes for closure speed
- Long confirmation delays left unmodelled, so decisions are made against a badly stale posterior
- No allocation floor, so a detector that has become useful is never given the chance to show it
Optimization
Primary fitChoose repeatedly among a fixed set of options whose payoffs are unknown, balancing the cost of learning against the cost of not learning, with the arm means estimated online and exploration directed by uncertainty rather than by chance.
- The exploration-exploitation trade isolated from credit assignment, which is what makes it analyzable at all
- Regret as an objective with matching upper and lower bounds — the only place in this category where the theory is tight and predictive
- Optimism versus probability matching as two routes to the same rate, one frequentist and one Bayesian
- The contextual extension, which is where almost all production use actually lives
The most practically useful entry in this category and the most commonly reached for wrongly. Three lessons transfer. The first is the regret decomposition: cost equals gap times pulls, so being wrong about a near-tie is cheap and being wrong about a large gap is expensive — a framing that applies to any resource allocation under uncertainty and that reframes "how confident do I need to be" as "how much does being wrong cost here". The second is that directed exploration beats random exploration by a wide margin, and the mechanism is simply a confidence interval; epsilon-greedy explores arms it already knows are bad, which is the clearest illustration available of why uncertainty should steer exploration. The third is a warning. A bandit optimizes cumulative reward and will deliberately stop sampling arms it believes are inferior, which means it is actively destroying the statistical power needed to estimate those arms. If the goal is to learn each option's effect precisely, that is a randomized experiment, not a bandit, and the two objectives genuinely conflict. Where bandits are the wrong choice otherwise: if the action changes what the next decision looks like, the state assumption is false and this is an MDP wearing a disguise; and if the arm set is enormous or the arms are near-duplicates, independent per-arm estimation wastes evidence and a contextual model is required.
- Verify the action does not change the next state — that assumption is the whole method and it fails quietly rather than loudly
- Use a discounted or sliding-window variant if the arm means can move, since every bound assumes they cannot
- Prefer Thompson sampling when feedback is delayed or batched, because several decisions drawn from one posterior diversify where UCB repeats
- Keep an allocation floor per arm, which is absent from all the theory and standard in production for exactly the reasons the theory ignores
Cumulative regret against the best fixed arm in hindsight is the primary metric, and it is computable offline in simulation where the true means are known. In production, track realized reward against a holdout running uniform allocation — that holdout is what makes regret measurable at all, and it is also the only sample that supports unbiased estimation of every arm.
- Using a bandit when the actions change the state, which silently makes every guarantee inapplicable
- Expecting reliable estimates for arms the bandit stopped pulling, when it stopped pulling them precisely to avoid paying for that information
- No nonstationarity mechanism, so a collapsed confidence interval outlives the world it was measured in
- Near-duplicate arms treated as independent, so evidence that should be shared is spent many times over
Recommendation & Ranking
Primary fitScore a narrowed candidate set with a model of reward given user and item features, then select optimistically or by posterior sampling so that the system continuously buys the information it needs about items it has not shown enough.
- Cold-start items and users, where the uncertainty is largest and directed exploration is worth the most
- Headline, creative and layout selection, which are small fixed arm sets and the textbook case
- Ad and content allocation, where contextual bandits with linear models are the long-standing production standard
- Generating the exploration data that every downstream off-policy method needs, with logged propensities
The largest production deployment of anything in this category, and the reason is fit rather than fashion. A supervised ranker trained on logged clicks has a feedback loop: it only observes outcomes for items it chose to show, so items it never shows never accumulate evidence and stay unshown regardless of merit. That is exactly the failure directed exploration fixes, and the fix is cheap — a confidence term or a posterior draw, computed per request, on top of a model that already exists. Three qualifications decide whether it works. The arm set must be narrowed by retrieval first, because per-arm uncertainty over a catalogue is not maintainable and near-duplicate items waste evidence that a contextual model would share. Feedback is delayed and batched in almost every real system, which favours Thompson sampling strongly — a batch of decisions drawn from one posterior explores naturally, where UCB would serve the same arm for the whole batch. And the state assumption deserves genuine scrutiny: if a recommendation meaningfully changes what the user does next, this is a sequential problem and the bandit is approximating it, which is often an acceptable approximation and should be a decision rather than an oversight.
- Narrow the arm set with retrieval before anything else, since per-arm uncertainty over a catalogue is not maintainable
- Log the selection propensities at serving time, because every off-policy method downstream needs them and they cannot be recovered later
- Prefer Thompson sampling under batched or delayed feedback, where a single posterior naturally diversifies a batch of decisions
- Share evidence across near-duplicate items with a contextual model rather than treating each as an independent arm
Online experiments decide, with a uniform-allocation holdout maintained deliberately — it is what makes regret measurable and it is the only traffic that supports unbiased estimation of every arm. Report the long-horizon objective as well as immediate reward, since a bandit optimizes the immediate reward it was given and will happily trade away anything it was not.
- An un-narrowed catalogue as the arm set, where per-arm uncertainty cannot be maintained and everything is a cold start
- Propensities never logged, which makes every downstream correction unavailable
- UCB under batched feedback, which deterministically serves the same arm for the entire batch
- Assuming the state assumption holds when a recommendation visibly changes what the user does next
Causal Inference & Uplift
AdaptedRun an experiment whose allocation adapts as evidence accumulates, shifting traffic toward better-performing arms while retaining enough sampling of the alternatives to say something about them afterwards.
- Adaptive experiments where the cost of serving a losing variant to users is substantial
- Best-arm identification, which is a genuinely different objective from regret minimization and has its own algorithms
- Sequential testing where a decision must be made as early as the evidence allows
- Understanding why adaptively collected data breaks ordinary inference, which is the most useful thing here
Included because the tension is real and routinely mishandled. A bandit minimizes regret, which means it deliberately stops sampling arms it believes are worse — and the sample sizes it leaves behind are therefore both small and, crucially, dependent on the outcomes observed so far. That dependence breaks the standard estimators: the sample mean of an adaptively sampled arm is biased, the usual confidence intervals do not have their nominal coverage, and a p-value computed as though the allocation were fixed is simply wrong. There is real methodology for this — adaptively weighted estimators and always-valid sequential inference — and it is not what most teams reach for. So the first thing to settle is which objective is actually wanted. If the goal is to earn as much as possible while learning, a bandit is right and the inference afterwards needs the corrected machinery. If the goal is a trustworthy estimate of every arm's effect, a fixed randomized allocation is right and the bandit is actively working against you. If the goal is to find the best arm as fast as possible and the intermediate cost does not matter, neither is right — best-arm identification is a third objective with its own algorithms, and it allocates quite differently from regret minimization.
- Decide the objective first: cumulative reward, best-arm identification, or unbiased estimation of every arm — the three lead to different allocations
- Keep a fixed-allocation holdout, which preserves a clean sample for ordinary inference and costs a known amount of regret
- Use adaptively weighted estimators or always-valid sequential intervals when analyzing adaptively collected data
- Record the allocation probabilities at decision time, since the analysis depends on them and they cannot be reconstructed
State the objective and evaluate against it: regret against the best arm in hindsight for cumulative reward, probability of correct selection for best-arm identification, and coverage of the intervals for estimation. Reporting a naive confidence interval on adaptively collected data is the characteristic error, and it will be too narrow and centred in the wrong place.
- Naive confidence intervals on adaptively collected data, which are biased and do not have their stated coverage
- Expecting a bandit to deliver a precise estimate of a losing arm it deliberately stopped sampling
- Using regret minimization when the actual goal is identifying the best arm, which allocates differently
- Switching allocation rules mid-experiment without recording when, which makes any later analysis unreconstructable
Risk & Fraud
AdaptedRoute cases among review queues, rule sets or verification challenges, learning online which routing wins per segment, with the reward defined on the confirmed outcome of the review rather than on the decision that produced it.
- Manual review routing, where several queues or vendors have different and drifting hit rates
- Step-up verification: choosing which challenge to present when several are available and their friction-versus-catch trade differs by segment
- Rule and threshold selection within a fixed review budget, adapted as fraud behaviour shifts
- Vendor and model bake-offs run as live allocation rather than as a fixed split
A narrow fit, and the boundary is what makes it worth stating. The adversarial core of fraud is genuinely sequential and genuinely unsuited to online learning, because exploring means deliberately approving transactions you believe are fraudulent in order to find out — a cost nobody accepts, and the reason reinforcement learning generally does not belong in the decision itself. What bandits are for here is the low-stakes decisions around it, where an exploratory choice costs some friction or some analyst time rather than a loss. Routing, challenge selection and review allocation all have that shape: a repeated choice, a measurable outcome, and a wrong answer that is recoverable. Two things constrain it in practice. Fraud is adversarial, so arm means move deliberately in response to what you do, which is a stronger form of nonstationarity than any discount factor was designed for and a reason to treat allocation shifts as signals rather than just as tuning. And confirmation is slow and often one-sided — a blocked transaction never reveals whether it was fraudulent — so the reward definition is the hardest part of the design and getting it wrong produces a system that confidently optimizes a censored outcome.
- Confine the bandit to recoverable decisions — routing, challenge selection, review allocation — and keep the block-or-approve decision out of it
- Define the reward on a confirmed outcome and be explicit about censoring, since a blocked case never reveals what it was
- Use a discounted or sliding-window variant, because an adversary moves the arm means on purpose
- Treat a sudden shift in allocation as a detection signal in its own right, not only as the algorithm adapting
Confirmed fraud caught per unit of review capacity and per unit of customer friction, against a fixed-allocation holdout. Report the censoring assumption explicitly alongside the numbers, since the estimate of any arm that blocks cases depends entirely on it and no amount of data will settle it.
- Putting the approve-or-block decision itself under a bandit, where exploration means knowingly approving fraud
- A reward computed from censored outcomes without saying so, which makes the whole comparison rest on an unstated assumption
- Undiscounted statistics against an adversary who is actively moving the arm means
- Friction costs left out of the reward, so the allocation optimizes catch rate and quietly degrades the customer experience
What it costs to run
Negligible, and that is a substantive property rather than a footnote. A non-contextual bandit holds a running mean and a count per arm and updates in constant time; a contextual one maintains a small matrix per arm. There is no training job, no simulator, no replay buffer and no gradient step — the model updates as the data arrives, inside the serving path. This is the main reason bandits appear in production systems where nothing else in this category does. Illustrative, not a measured benchmark.
Microseconds for the non-contextual case: score K arms and take the argmax. Contextual scoring is a small matrix operation per arm and still comfortably inside a request budget once the arm set has been narrowed. UCB is deterministic, which makes decisions reproducible and auditable; Thompson sampling is not, so an identical request can yield different arms, and any system needing reproducible decisions must log the draw rather than expecting to replay it.
There is no retraining. The state is the posterior or the sufficient statistics, and it updates continuously as rewards arrive — which is the entire operational appeal. What does need a cadence is a decision about forgetting: with a discount or a sliding window, how fast to forget is the one parameter standing between a system that adapts to change and one that is confidently serving yesterday's winner. Reviewing that setting against observed nonstationarity is the real periodic task.
- Arm allocation over time, which is the most directly interpretable signal available — a collapse onto one arm means exploration has effectively stopped
- Realized reward against a uniform-allocation holdout, which is what makes regret measurable in production rather than only in simulation
- Per-arm pull counts and posterior widths, since an arm with a collapsed interval cannot be overtaken without an explicit forgetting mechanism
- Feedback delay distribution, because every guarantee assumes immediate feedback and a lengthening delay quietly degrades the algorithm
- Evidence of nonstationarity: a change in which arm wins on recent data, compared against what the undiscounted statistics still believe
- Logged selection propensities, which are needed by every downstream off-policy analysis and are irrecoverable if not written at decision time
- The no-state assumption is the whole method and it fails quietly. If an action changes what the next decision looks like, every guarantee here is void and nothing will indicate that
- A bandit deliberately stops sampling arms it believes are worse, so the data it leaves cannot support a confident estimate of those arms. Wanting both maximum reward and precise per-arm estimates is wanting two different experiments
- Confidence intervals computed on adaptively collected data are biased and do not have their nominal coverage. This is the most common analytical error downstream of a bandit deployment
- Without discounting or a sliding window, an arm with a long history has a collapsed interval and cannot be overtaken when the world changes
- UCB under batched or delayed feedback degenerates into serving the same arm for the whole batch, because it is deterministic and nothing has updated. Thompson sampling does not have this problem
- A new arm added mid-run has no history and will be starved unless given an optimistic prior, which is a deployment step rather than an algorithmic one
- Near-duplicate arms are treated as independent and each explored separately, spending the same evidence many times. That is what the contextual form exists to fix
- The theoretical exploration constant is usually too exploratory in practice. Tuning it down is normal and should be a recorded decision rather than an accident
Pros and cons, in context
Real guarantees that match a lower bound and predict actual behaviour
UCB and Thompson both attain logarithmic regret, and no algorithm can do better. This is the only group in this category where the theory is tight, and where it tells you something useful about a run before you start it
Cheap enough to run inside a request handler
A running mean and a count per arm, updated in constant time, with no training job, no simulator and no replay buffer. That operational profile is the main reason bandits ship where the rest of this category does not
Directed exploration is dramatically better than random exploration
Epsilon-greedy explores arms it already knows are bad; UCB and Thompson spend their budget where uncertainty is. The gap between the two is the clearest demonstration available of why uncertainty should steer exploration
Thompson sampling extends to anything you can put a posterior on
Sample from the posterior, act greedily on the sample. That recipe carries to linear models, trees and neural approximations, and it handles delayed and batched feedback gracefully because one posterior naturally diversifies a batch
The contextual form fixes the cold-start feedback loop directly
A supervised ranker only observes outcomes for what it chose to show, so unshown items stay unshown. Adding a confidence term or a posterior draw on top of the existing model breaks that loop for very little machinery
The no-state assumption fails silently
If an action changes what the next decision looks like, the problem is an MDP and every guarantee is void — with nothing raising an error. This is the most common way a bandit is the wrong tool and nobody notices
It destroys the statistical power needed to estimate the arms it abandons
Minimizing regret means deliberately not paying for information about inferior arms. Wanting both maximum reward and precise per-arm effects is wanting two different experiments, and they allocate traffic differently
Adaptively collected data breaks ordinary inference
Sample means are biased and standard confidence intervals lose their coverage, because the sample sizes depend on the outcomes observed. Corrected estimators exist and are not what most teams reach for
Every guarantee assumes stationarity
An arm with a long history has a collapsed confidence interval and cannot be overtaken when the world changes. A discount or a sliding window is mandatory in practice and costs asymptotic regret to buy responsiveness
Independent arms waste evidence
A hundred near-identical variants are each explored separately, so the same information is bought many times. Contextual models fix this and bring their own difficulty — maintaining calibrated uncertainty over a learned model
UCB handles delay and batching badly
Being deterministic, it serves the same arm for an entire batch when nothing has updated in between. Thompson sampling has no such problem, which is a large part of why it dominates in real systems
Intuitive, idiomatic, optimized
The same algorithm in three languages, each progressing through Kent Beck's three stages. Every optimization names the lever it pulls and the trade-off it accepts — cost profiles are illustrative, not measured benchmarks.
The math, transcribed literally. No dependencies.
"""Three bandit algorithms, transcribed side by side.
All three answer the same question - which arm now - and the differences
between them are the whole content of the topic. Only the standard library is
used, including for the Beta draw Thompson needs.
"""
import math
import random
def epsilon_greedy(means, counts, epsilon):
"""Explore at random, otherwise take the best known arm.
The flaw is visible in one line: the random branch picks UNIFORMLY, so an
arm already known to be terrible is explored exactly as often as one that
is plausibly best. That is why fixed-epsilon regret is linear in T.
"""
if random.random() < epsilon:
return random.randrange(len(means))
return max(range(len(means)), key=lambda arm: means[arm])
def ucb1(means, counts, total_pulls):
"""Optimism in the face of uncertainty.
The bonus is a confidence RADIUS: wide for an arm pulled rarely, shrinking
as the square root of its pull count. So exploration goes where the
uncertainty is rather than where a coin lands, which is the entire
improvement over epsilon-greedy.
Note the numerator is the TOTAL pull count, not this arm's. That is what
makes every bonus creep upward as time passes, so an arm abandoned early is
eventually revisited rather than written off forever.
"""
for arm in range(len(means)):
if counts[arm] == 0:
return arm # every arm once, or the bonus is undefined
best_arm, best_score = 0, -float("inf")
for arm in range(len(means)):
bonus = math.sqrt(2.0 * math.log(total_pulls) / counts[arm])
score = means[arm] + bonus
if score > best_score:
best_arm, best_score = arm, score
return best_arm
def thompson_sampling(successes, failures):
"""Probability matching, via one draw per arm.
A Beta(1 + successes, 1 + failures) posterior over each arm's success rate,
one sample from each, and the argmax of the samples. An arm is played with
exactly the probability that it IS the best arm under the current posterior
- which is precisely as much exploration as the uncertainty justifies, with
no bonus term and no schedule to tune.
"""
best_arm, best_draw = 0, -float("inf")
for arm in range(len(successes)):
draw = random.betavariate(1.0 + successes[arm], 1.0 + failures[arm])
if draw > best_draw:
best_arm, best_draw = arm, draw
return best_arm
def run(bandit, n_arms, horizon, algorithm="ucb", epsilon=0.1):
"""One pull per step, with the regret decomposition accumulated alongside.
Regret is gap times pulls, summed over suboptimal arms. Tracking it
directly makes the accounting visible: a near-tied arm costs almost nothing
to keep trying, and a badly worse one has to be abandoned fast.
"""
means = [0.0] * n_arms
counts = [0] * n_arms
successes = [0] * n_arms
failures = [0] * n_arms
cumulative_reward = 0.0
regret_history = []
best_mean = max(bandit.true_means)
for step in range(1, horizon + 1):
if algorithm == "epsilon":
arm = epsilon_greedy(means, counts, epsilon)
elif algorithm == "ucb":
arm = ucb1(means, counts, step)
else:
arm = thompson_sampling(successes, failures)
reward = bandit.pull(arm)
# Incremental mean: a running sum and a count is ALL the state a
# non-contextual bandit has, which is why this fits in a request
# handler and nothing else in this category does.
counts[arm] += 1
means[arm] += (reward - means[arm]) / counts[arm]
if reward > 0.5:
successes[arm] += 1
else:
failures[arm] += 1
cumulative_reward += reward
regret_history.append(step * best_mean - cumulative_reward)
return means, counts, regret_historyO(K) per decision to score the arms, O(1) to update. Three running numbers per arm and nothing else.
How this language actually wants it written.
"""Bandit policies - typed, with a forgetting mechanism and honest diagnostics."""
from __future__ import annotations
from dataclasses import dataclass, field
from typing import Protocol
import numpy as np
from numpy.typing import NDArray
class Policy(Protocol):
"""One interface, three implementations. The whole topic is the difference
between them, so making them substitutable is the point of the abstraction
rather than an incidental tidiness."""
def select(self, step: int) -> int: ...
def update(self, arm: int, reward: float) -> None: ...
@dataclass
class ArmStatistics:
"""Sufficient statistics with a DISCOUNT.
Every regret bound in this area assumes stationary arm means. Without
forgetting, an arm with a long history has a confidence interval that has
already collapsed and cannot be overtaken when the world changes - and the
failure mode is a system confidently serving a formerly-best arm. The
discount costs asymptotic regret and buys responsiveness, which is almost
always the right trade in production.
"""
n_arms: int
discount: float = 1.0
_weighted_sum: NDArray[np.float64] = field(init=False)
_weighted_count: NDArray[np.float64] = field(init=False)
def __post_init__(self) -> None:
if self.n_arms < 2:
raise ValueError("a one-armed bandit has nothing to decide")
if not 0.0 < self.discount <= 1.0:
raise ValueError(f"discount must be in (0, 1], got {self.discount}")
self._weighted_sum = np.zeros(self.n_arms, dtype=np.float64)
self._weighted_count = np.zeros(self.n_arms, dtype=np.float64)
def update(self, arm: int, reward: float) -> None:
# Everything decays, not just the arm that was pulled: the passage of
# time is what makes old evidence about ANY arm less relevant.
self._weighted_sum *= self.discount
self._weighted_count *= self.discount
self._weighted_sum[arm] += reward
self._weighted_count[arm] += 1.0
@property
def means(self) -> NDArray[np.float64]:
# Safe division: an unpulled arm has no mean, and returning zero rather
# than a nan keeps the comparison well-defined without pretending.
return np.divide(
self._weighted_sum,
self._weighted_count,
out=np.zeros_like(self._weighted_sum),
where=self._weighted_count > 0,
)
@property
def counts(self) -> NDArray[np.float64]:
return self._weighted_count
@property
def effective_horizon(self) -> float:
"""Total weighted evidence. With a discount this plateaus rather than
growing, which is exactly what keeps the confidence bonus from
shrinking to nothing."""
return float(self._weighted_count.sum())
@dataclass
class UcbPolicy:
stats: ArmStatistics
# The theoretical constant is usually too exploratory in practice. Tuning
# it down is normal and belongs in the config as a recorded decision rather
# than as a magic number edited into the formula.
exploration: float = 1.0
def select(self, step: int) -> int:
counts = self.stats.counts
unpulled = np.flatnonzero(counts == 0)
if unpulled.size > 0:
return int(unpulled[0]) # the bonus is undefined without a pull
horizon = max(self.stats.effective_horizon, np.e)
bonus = self.exploration * np.sqrt(2.0 * np.log(horizon) / counts)
return int(np.argmax(self.stats.means + bonus))
def update(self, arm: int, reward: float) -> None:
self.stats.update(arm, reward)
@dataclass
class ThompsonPolicy:
"""Beta-Bernoulli posterior sampling.
Preferred under delayed or batched feedback: several decisions drawn from
one posterior diversify naturally, where UCB is deterministic and will
serve the same arm for an entire batch because nothing has updated.
"""
n_arms: int
prior_alpha: float = 1.0
prior_beta: float = 1.0
rng: np.random.Generator = field(default_factory=lambda: np.random.default_rng(0))
_successes: NDArray[np.float64] = field(init=False)
_failures: NDArray[np.float64] = field(init=False)
def __post_init__(self) -> None:
if self.prior_alpha <= 0.0 or self.prior_beta <= 0.0:
raise ValueError("Beta prior parameters must be positive")
self._successes = np.zeros(self.n_arms, dtype=np.float64)
self._failures = np.zeros(self.n_arms, dtype=np.float64)
def select(self, step: int) -> int:
draws = self.rng.beta(
self.prior_alpha + self._successes, self.prior_beta + self._failures
)
return int(np.argmax(draws))
def update(self, arm: int, reward: float) -> None:
if not 0.0 <= reward <= 1.0:
raise ValueError(f"Beta-Bernoulli needs a reward in [0, 1], got {reward}")
# Fractional updates are valid for a reward in [0, 1] and keep the
# conjugacy exact, which is cleaner than thresholding to a Bernoulli.
self._successes[arm] += reward
self._failures[arm] += 1.0 - reward
@dataclass
class AllocationFloor:
"""A guaranteed share of traffic per arm.
Absent from every bound in the literature and standard in production, for
reasons the theory does not model: it preserves the ability to notice that
an arm has become good, and it leaves a sample that ordinary inference can
actually be run on. Adaptively collected data cannot support a standard
confidence interval, and this is the cheapest way to keep some that can.
"""
inner: Policy
n_arms: int
floor: float = 0.02
rng: np.random.Generator = field(default_factory=lambda: np.random.default_rng(1))
def select(self, step: int) -> int:
if self.rng.random() < self.floor * self.n_arms:
return int(self.rng.integers(self.n_arms))
return self.inner.select(step)
def update(self, arm: int, reward: float) -> None:
self.inner.update(arm, reward)What changed: The three algorithms become one substitutable interface, because the topic is the difference between them. Statistics gain a discount, since every bound here assumes stationary arm means and an undiscounted arm with a long history has a collapsed interval that cannot be overtaken. Thompson accepts fractional rewards rather than thresholding to a Bernoulli, which keeps the conjugacy exact. And an allocation floor is added — absent from all the theory and standard in production, because it preserves both the ability to notice a change and a sample that ordinary inference can be run on.
O(K) per decision as array operations; the discount makes the update O(K) rather than O(1).
Faster, and the justification for each change.
"""LinUCB - Cholesky maintained incrementally, never an explicit inverse.
The contextual case is where production lives, and it is where the naive
implementation quietly becomes the bottleneck. Per arm it maintains a d-by-d
design matrix A = lambda*I + sum x x^T, and it needs two things from it: the
ridge solution A^-1 b, and the confidence width sqrt(x^T A^-1 x).
Forming A^-1 to get either is the wrong move twice over - O(d^3) per update,
and numerically the worst available way to solve a linear system.
"""
from __future__ import annotations
import numpy as np
from numpy.typing import NDArray
class CholeskyArm:
"""Ridge statistics for one arm, held as a Cholesky factor.
A = L L^T is maintained directly. Adding an observation is a rank-one
update to A, and there is an O(d^2) in-place algorithm that turns L into
the factor of A + x x^T without ever rebuilding it - compared with O(d^3)
to refactorize and the same again to invert.
Everything the algorithm needs is then a triangular solve, which is both
faster and far better conditioned than multiplying by an inverse.
"""
def __init__(self, dimension: int, ridge: float = 1.0) -> None:
# A = ridge * I, so its factor starts as sqrt(ridge) * I.
self.factor = np.eye(dimension, dtype=np.float64) * np.sqrt(ridge)
self.b = np.zeros(dimension, dtype=np.float64)
self.dimension = dimension
self._updates_since_refactor = 0
# Scratch buffers reused by every update and every score, so the hot
# path allocates nothing at all.
self._scratch = np.empty(dimension, dtype=np.float64)
def update(self, features: NDArray[np.float64], reward: float) -> None:
"""Rank-one Cholesky update, in place, O(d^2).
The classic cholupdate: sweep down the diagonal, rotating each row so
that the factor absorbs the outer product. No matrix is formed and no
inverse is touched.
"""
np.copyto(self._scratch, features)
x = self._scratch
for k in range(self.dimension):
diagonal = self.factor[k, k]
r = np.hypot(diagonal, x[k])
cosine = r / diagonal
sine = x[k] / diagonal
self.factor[k, k] = r
if k + 1 < self.dimension:
column = self.factor[k + 1 :, k]
# In place on both the factor column and the working vector.
column += sine * x[k + 1 :]
column /= cosine
x[k + 1 :] *= cosine
x[k + 1 :] -= sine * column
self.b += reward * features
self._updates_since_refactor += 1
def score(self, features: NDArray[np.float64], alpha: float) -> float:
"""Predicted reward plus the confidence width, via two triangular solves.
theta = A^-1 b is L^T z = y after L y = b
width = sqrt(x^T A^-1 x) is ||z|| after L z = x
Both are back-substitutions. Neither forms an inverse, and the second
one is why this formulation is worth the trouble: the width IS the norm
of a solve, which is numerically clean where x^T A^-1 x computed from
an explicit inverse loses precision exactly when A is near-singular -
which is precisely the under-explored regime the bonus exists for.
"""
theta = _solve_from_factor(self.factor, self.b)
z = _forward_substitute(self.factor, features)
return float(features @ theta + alpha * np.linalg.norm(z))
@property
def needs_refactor(self) -> bool:
"""Rank-one updates drift. Periodically rebuilding the factor from the
accumulated matrix restores exactness, and the interval is a real
trade rather than defensive padding."""
return self._updates_since_refactor >= 10_000
def _forward_substitute(factor: NDArray[np.float64], rhs: NDArray[np.float64]):
"""Solve L z = rhs. Contiguous, single dtype, one BLAS-level call."""
from scipy.linalg import solve_triangular
return solve_triangular(factor, rhs, lower=True, check_finite=False)
def _solve_from_factor(factor: NDArray[np.float64], rhs: NDArray[np.float64]):
"""Solve A theta = rhs given A = L L^T, as two triangular solves."""
from scipy.linalg import cho_solve
return cho_solve((factor, True), rhs, check_finite=False)
def score_all_arms(
factors: NDArray[np.float64],
thetas: NDArray[np.float64],
features: NDArray[np.float64],
alpha: float,
) -> NDArray[np.float64]:
"""Score every arm for one context in a single batched operation.
Stacking the per-arm factors into one (K, d, d) block turns K separate
triangular solves into one batched solve, and the mean term into a single
matrix-vector product. At production arm counts that is the difference
between a Python loop over arms and one BLAS call.
"""
means = thetas @ features # (K,) in one GEMV
# One batched triangular solve across the leading arm axis.
z = np.linalg.solve(factors, np.broadcast_to(features, (factors.shape[0], features.size)).T).T
widths = np.linalg.norm(z, axis=1)
return means + alpha * widthsWhat changed: The contextual case is where production lives and where the naive implementation becomes the bottleneck. Instead of forming and storing each arm's inverse design matrix, the Cholesky factor is maintained directly with an in-place rank-one update — O(d²) per observation against O(d³) to refactorize, and every quantity the algorithm needs becomes a triangular solve. That is faster and materially better conditioned: the confidence width is the norm of a solve, which stays accurate exactly where an explicit inverse loses precision, in the under-explored regime the bonus exists for. Arm scoring is then one batched operation rather than a loop.
Replace a closed-form solve with a numerically stabler factorization
Maintaining a Cholesky factor and back-substituting replaces an explicit inverse, which is both O(d) more expensive to keep up to date and the least accurate way to solve a linear system — worst precisely when the design matrix is near-singular, which is the under-explored arm the bonus is meant to serve.
Trade-off: Rank-one updates accumulate floating-point drift, so the factor must be periodically rebuilt from scratch — a maintenance obligation an explicit recomputation does not carry.
Vectorize to NumPy/BLAS (@, np.dot, einsum)
Stacking the per-arm factors into one leading-axis block turns K separate triangular solves into one batched call and the mean terms into a single product.
Trade-off: Every arm must share the same feature dimension and be resident in one contiguous block, so adding or removing an arm means reallocating the whole stack.
Pre-allocate output arrays and use in-place operations
The rank-one update runs entirely in a reused scratch vector and writes the factor in place, so the per-observation path performs no allocation.
Trade-off: The scratch buffer makes the arm object non-reentrant, so two threads updating the same arm corrupt it silently rather than contending.
Eliminate Python-level loops over samples
Scoring every arm for a context is one batched solve and one norm along an axis, replacing a per-arm Python loop that dominates at production arm counts.
Trade-off: The batched form computes a full solve for every arm including ones a cheap pre-filter would have excluded, so it does more arithmetic to avoid more overhead.
O(d^2) per observation instead of O(d^3); one batched solve per decision instead of K. Illustrative, not a measured benchmark.