Source-linked AI summary
A Survey of Online Experiment Design with the Stochastic Multi-Armed Bandit
Giuseppe Burtini, Jason Loeppky, Ramon Lawrence
TL;DR
Sequential experiment design can be framed as multi-armed bandit learning, but experiment goals and practical conditions affect which formulations fit. The survey connects bandit research to online experiments, organizes complications to the stochastic model, and synthesizes theoretical results and design considerations.
Problem
Bandit research and sequential experiment design have developed with distinct perspectives, while experiment design may prioritize estimator variance and effect sizes over regret.
Source: §1 · p. 3, §2.1 · p. 6Method
The survey synthesizes multi-armed bandit research for online experiment design, covering the stochastic model and complications relevant to experimental settings.
Source: §1 · p. 3, §4 · p. 22Results
The survey connects bandit methods to experiment design and organizes complications that affect the simple stochastic model, including adversarial, contextual, and nonstationary settings.
Source: §1 · p. 3, §4 · p. 22Takeaways & Limitations
Bandit methods can support sequential experiments, but best-arm identification aligns more directly with regret than arm-to-arm significance comparisons.
Source: §2 · p. 6Regret may not capture experiment-design priorities such as estimator-variance minimization and accurate effect-size estimation.
Source: §2.1 · p. 6
Abstract
from arXiv · showhide
Adaptive and sequential experiment design is a well-studied area in numerous domains. We survey and synthesize the work of the online statistical learning paradigm referred to as multi-armed bandits integrating the existing research as a resource for a certain class of online experiments. We first explore the traditional stochastic model of a multi-armed bandit, then explore a taxonomic scheme of complications to that model, for each complication relating it to a specific requirement or consideration of the experiment design context. Finally, at the end of the paper, we present a table of known upper-bounds of regret for all studied algorithms providing both perspectives for future theoretical work and a decision-making tool for practitioners looking for theoretical guarantees.
1. Introduction
The survey brings multi-armed bandit research into sequential experiment design, connecting its statistical and machine-learning framework to online experiments. It introduces the bandit model and motivates its relevance to adaptive clinical and other experiments.
1. Introduction
- The survey integrates advances in multi-armed bandits with sequential experiment design, offering a statistical perspective and a unified discussion of response-adaptive experiments.Source: §1 · p. 3
1.1. Motivating Applications
- Clinical trials involve costly, sometimes geographically constrained observations, while sequential designs can use information revealed during an experiment to adapt allocation.Source: §1.1 · pp. 3–4
- Bandits fit treatment experiments because only the selected arm's payoff is observed, and adaptive dose-finding and biomarker designs map to continuum-armed and contextual bandits.Source: §1.1 · p. 4, §1.2 · p. 5
1.2. The Multi-Armed Bandit Model
- The formal model repeatedly selects among K independent, unknown reward distributions over horizon H, using each selected arm's reward to inform later choices.Source: §1.2 · p. 6
2. Considerations of Multi-Armed Bandits
The section explains how experiment-design goals and practical conditions qualify the use of multi-armed bandits. It surveys regret measures, variability and bounds, nonstationarity, and delayed feedback.
2. Considerations of Multi-Armed Bandits
- Bandits naturally suit best-arm identification, but are less suited to arm-to-arm significance comparisons because regret penalizes exploration of suboptimal arms.Arm-to-arm comparison can still be plausible while maximizing within-experiment utility.Source: §2 · p. 6
2.2. Variance and Bounds of Regret
- Regret may not capture experiment-design priorities such as estimator-variance minimization and accurate effect-size estimation; high-probability and finite-time bounds address variation and bounded-horizon performance.Source: §2.1 · p. 6, §2.2 · pp. 8–9
2.1. Measures of Regret
- Regret has several definitions, including expected-expected regret, expected-payoff regret, and suboptimal plays; oracle-based measures generally require simulation.Source: §2.1 · p. 7
2.3. Stationarity of the Problem
- Stationarity is often assumed, but changing reward distributions can make fixed-policy performance degrade, while decay-based adaptation requires a suitable decay rate.Source: §2.3 · p. 9
2.4. Feedback Delay
- Delayed feedback is under-considered despite practical cases such as clinical trials, and known delays can be modeled with multiple-play bandit variants.Source: §2.4 · pp. 9–10
3. Algorithms for the Application of Multi-Armed Bandits
The survey reviews policies for the finite-armed stochastic bandit, from the Gittins index to simple exploration strategies. It contrasts their decision rules with computational limits and tuning trade-offs.
3. Algorithms for the Application of Multi-Armed Bandits
- The survey covers policies for the traditional finite-armed model, including Gittins indices, epsilon strategies, UCB, standalone algorithms, and probability matching.Source: §3 · p. 10
3.1. Gittins index
- The Gittins rule selects the arm with the highest index, an estimated average discounted reward, but index computation can be costly and is constrained by finite-state distributions.Source: §3.1 · p. 11
3.2. ǫ-greedy
- Epsilon-greedy explores randomly with probability epsilon and otherwise selects the arm with the best observed mean; after O random plays, epsilon strategies find an alpha-optimal arm with probability greater than 1 minus delta.Source: §3.2 · p. 11
3.2.1. Constant ǫ
- Constant-epsilon policies can achieve linear regret but remain suboptimal because they continue random exploration and generally do not asymptotically reach the optimal arm.Source: §3.2.1 · pp. 11–12
3.2.2. Adaptive and ǫ-Decreasing
- Epsilon-decreasing policies shift from early exploration toward exploitation, with GreedyMix achieving regret of order ln(H)^2 for Bernoulli and normal bandits, but performance depends on tuning d.Source: §3.2.2 · p. 12
- A correctly tuned epsilon schedule can yield expected regret O(log H), but its parameters depend on the unknown reward distribution and incorrect tuning degrades performance rapidly.Source: §3.2.2 · p. 12
3.3. ǫ-first
The section contrasts staged exploration with policies that adapt exploration over time, then describes improvements to upper-confidence-bound strategies. It also notes horizon and stationarity conditions that shape their use.
3.3. ǫ-first
- ǫ-first explores uniformly for a fixed initial fraction of a known horizon, then exploits the empirically best arm; it is vulnerable to non-stationarity and horizon-estimation errors.With a fixed horizon and stationary arms, its estimates are expected to be better than ǫ-greedy’s, leading to fewer expected suboptimal plays.Source: §3.3 · p. 13
3.3.1. Multiple Epoch
- Multiple epochs reapply a policy over spaced intervals, a proposed way to reduce ǫ-first’s vulnerability to non-stationarity and horizon unawareness.Epoch length and data decay can control maximum deviation, but this approach is largely unstudied outside ǫ-based policies.Source: §3.3.1 · p. 13
3.4. UCB1
- UCB1 achieves expected logarithmic regret uniformly over time for all reward distributions without requiring prior knowledge of the reward distribution.Unlike semi-uniform strategies, it adapts exploration at each iterate rather than separating exploration and exploitation into phases.Source: §3.4 · p. 14
3.5. UCB2
- UCB2 reduces the constant term in the fraction of suboptimal-arm selections, lowering overall regret at the cost of a slightly more complicated algorithm.Its parameter α trades off terms in the bound; the original work recommends decreasing α slowly, while experiments suggest relatively small choices perform similarly.Source: §3.5 · p. 15
3.6. UCB-Tuned
This section presents UCB variants that tune exploration using variance, horizon, distributional distance, or Bayesian posterior quantiles. The reported comparisons and guarantees differ across these approaches.
3.6. UCB-Tuned
- UCB-Tuned empirically outperforms UCB1 and UCB2 in frequency of selecting the best arm, and the authors report significant improvement over earlier UCBs in their results.The tuning replaces UCB1’s padding term with one based on an upper-bound estimate of arm variance.Source: §3.6 · p. 15
3.7. MOSS
- MOSS replaces UCB1’s ln t padding component with ln(H/K), and its regret bound depends on the smallest positive gap between the optimal and second-best arms.Here H is the horizon and K is the number of arms.Source: §3.7 · p. 16
3.8. KL-UCB
- KL-UCB derives its padding function from Kullback-Leibler divergence, using distributional distance rather than only a midpoint such as the expectation.The cited passage says this approach improves regret bounds over earlier UCB algorithms.Source: §3.8 · p. 16
3.9. Bayes-UCB
- Bayes-UCB selects arms using time-varying posterior quantiles and is reported to empirically outperform KL-UCB; its analysis shows asymptotic optimality and finite-time regret in O(H).The survey describes it as distribution agnostic, while noting that computational complexity is acknowledged but not explored in depth.Source: §3.9 · p. 17
3.10. POKER and price of knowledge
POKER assigns each arm an expected value of information and adds it to expected payoff when choosing an arm. Its reported comparison is empirical, while finite-time regret analysis is unavailable in the survey’s account.
3.10. POKER and price of knowledge
- The asymptotic-optimality derivation depends on a horizon term, though the survey says this appears largely to be a mathematical artifact.The expected-improvement approximation may be poor when there are few arms and trials.Source: §3.10 · pp. 17–18
- POKER chooses the arm maximizing expected reward plus the expected value of information over the remaining horizon.Its exploration bonus estimates the chance and value of improving on the current best empirical arm.Source: §3.10 · p. 18
- The horizon length weights exploration against exploitation; when the horizon is unknown or infinite, the parameter can instead be set to a fixed value.The authors describe the horizon as a more intuitive parameter than those used by many other algorithms.Source: §3.10 · p. 19
- Approximately 3×: POKER outperformed ǫ strategies on a real-world redundant-retrieval routing problem, but no finite-time regret analysis was known.The authors compared it with ǫ strategies, Exp3, and others.Source: §3.10 · p. 19
3.11. Thompson Sampling and Optimism
Thompson sampling approximates the probability that each arm is best by sampling once from each estimated payoff distribution and selecting the largest draw. The discussion also covers optimism and BESA, a nonparametric alternative with logarithmic finite-time regret.
3.11. Thompson Sampling and Optimism
- O(log H) regret bounds and performance comparable to correctly tuned UCB-type algorithms are reported for Thompson sampling.The method samples once from each estimated payoff distribution and selects the highest sampled reward.Source: §3.11 · p. 20
3.11.1. Optimism and Confidence Bounds in Probability Matching
- Optimism improves Thompson sampling’s regret, while pure Thompson sampling is argued to explore efficiently for estimating effect sizes.The variance-weighting property is cited as supporting efficient exploration for data collection.Source: §3.11.1 · p. 21
3.12. Best Empirical Sampled Average (BESA)
- BESA equalizes sample sizes by subsampling rewards from the more-observed arm before comparing empirical averages.Ties go to the less-played arm; for more than two arms, a randomized recursive tournament compares pairs.Source: §3.12 · pp. 21–22
- O(log H) finite-time regret is reported for BESA, whose nonparametric design avoids reward-distribution knowledge but costs 2–20x more computation than Thompson sampling naively.Its empirical performance is described as comparable to properly tuned Thompson samplers and other state-of-the-art algorithms [18].Source: §3.12 · pp. 21–22
4. Complications of the Simple Stochastic Model
The paper turns from the simple stochastic bandit to complications that better reflect varied experiment-design settings, including adversarial, contextual, nonstationary, and multiple-play bandits.
4. Complications of the Simple Stochastic Model
- Adversarial, contextual, nonstationary, and multiple-play bandits extend the simple stochastic model to capture varied experiment-design requirements.Contextual bandits can incorporate covarying dimensions, while nonstationary models address contextual misspecification and long-running or infinite-horizon experiments.Source: §4 · p. 22
4.1. Adversarial Bandits
Adversarial bandits remove assumptions about a fixed statistical reward process, but meaningful performance comparisons use regret against a fixed arm. The section also describes Exp3 and its context-aware extension, Exp4.
4.1. Adversarial Bandits
- Adversarial bandits allow reward distributions to be chosen over time, potentially in response to the agent’s past decisions, removing fixed-distribution assumptions.The paper’s taxonomy distinguishes deterministic, stochastic, fully oblivious, oblivious, and non-oblivious settings.Source: §4.1 · pp. 22–23
- In the paper’s stochastic-centered lens, contextual covariates and nonstationarity are treated as misspecification, but pure non-oblivious adversarial problems are excluded.The lens is motivated by experiments with unknown or unknowable covariates, some of which are observable.Source: §4.1 · p. 23
- Adversarial performance is measured against a fixed arm over time, so only weak-regret notions remain meaningful in this setting.Source: §4.1 · p. 23
4.1.1. Hedge and Exp3
- Exp3 mixes random exploration at rate γ with weighted exploration and exploitation based on estimated rewards.Exp4 extends Exp3 with context vectors treated as experts advising on arm selection.Source: §4.1.1 · p. 24, §4.1.2 · p. 24
Exp4.P
Exp4.P modifies Exp4’s weight update to provide a high-probability regret bound. SAO tests whether rewards remain consistent with a stochastic model and switches to Exp3 when conditions fail.
Exp4.P
- ˜O(√(KH log N)) high-probability regret is given for Exp4.P, whose update addresses excessive variance in Exp4’s importance-weighted numerator.The bound holds with probability at least 1 − δ; K is the number of arms, H the horizon, and N the number of context vectors.Source: Exp4.P · p. 25
4.1.3. Stochastic and Adversarial Optimal (SAO)
- SAO reports O(polylog(n)) regret in the stochastic case and O(√n) pseudo-regret in the adversarial case, switching to Exp3 if consistency checks fail.The checks assess whether observed rewards remain compatible with the stochastic model during exploitation.Source: §4.1.3 · pp. 25–26
- SAO has no finite-time regret analysis, and its consistency parameters must prevent high regret under a carefully crafted adversary while holding with high probability in stochastic settings.Source: §4.1.3 · p. 27
4.2. Contextual Bandits for Experiments with Covariates
Contextual bandits extend arm selection to experiments where rewards may depend on covariates, including properties of the selected treatment and the patient or environment. The section surveys linear and nonlinear methods, including their regret guarantees and practical constraints.
4.2. Contextual Bandits for Experiments with Covariates
- Contextual bandits can use treatment and patient or environment covariates, even when their relevance is unknown; this is more applicable than ignoring available context.The paper separates arm-context from world-context and notes that weakly related contextual variables generally do not significantly harm learning.Source: §4.2 · p. 27
4.2.1. LinUCB
- LinUCB combines UCB with ridge-regression feature estimates and has polylog(H) regret, but sensitivity to non-stationarity and feedback delay remains insufficiently investigated.Its stated bound depends on feature dimension and confidence level.Source: §4.2.1 · p. 29
4.2.2. LinTS
- LinTS fits a linear model and uses coefficient and variance-covariance estimates in a Bayesian fashion to estimate each arm’s reward and uncertainty.The model can include arm indicators, interactions, and contextual variables.Source: §4.2.2 · pp. 29–30
4.2.3. CoFineUCB
- CoFineUCB estimates coarse and fine feature subspaces in sequence; recommender-system experiments show good regret performance when the coarse subspace reduces prediction variation for most users.The coarse-to-fine structure can represent hierarchies such as movie genre and subgenre.Source: §4.2.3 · p. 30
4.2.4. Banditron and NeuralBandit
- Banditron and NeuralBandit use partial bandit feedback in perceptron-style updates; they are robust to non-linearity and non-stationarity but lack much theory and can have suboptimal regret in stationary or linear settings.Source: §4.2.4 · p. 30
4.2.5. RandomizedUCB and ILOVETOCONBANDITS
- ILOVETOCONBANDITS uses policy-space optimization and inverse-propensity reward estimates to achieve low regret with fewer optimization-oracle calls than RandomizedUCB, but implementation remains complex.RandomizedUCB’s oracle calls scale as ˜O(H5); ILOVETOCONBANDITS updates policy distributions by epochs and coordinate descent.Source: §4.2.5 · p. 31
4.3. Nonstationary Bandits for Ongoing Experimentation
The section surveys methods for ongoing experiments in which reward distributions can change over time. These methods adapt estimates or policies to recent data, detected changes, or evolving uncertainty, with different guarantees and empirical strengths.
4.3. Nonstationary Bandits for Ongoing Experimentation
- Non-stationary bandits address settings such as ongoing antibiotic selection, where resistance, bacterial loads, and other factors may evolve in unmodelled ways.Source: §4.3 · pp. 31–32
4.3.1. Discounted UCB(-T)
- Discounted UCB applies exponential discounting to reward averages and optimism padding; Discounted UCB achieves optimum non-stationary regret up to logarithmic factors.The discount factor γ controls how strongly older observations are downweighted.Source: §4.3.1 · p. 32
4.3.2. Sliding-Window UCB(-T)
- Sliding-Window UCB replaces continuous discounting with a fixed window; experiments found it slightly better than discounted UCB and both variants strongly superior to Exp3-type algorithms and unmodified UCB1 on tested non-stationary problems.The window also avoids maintaining records older than τ.Source: §4.3.2 · pp. 32–33
4.3.3. Weighted Least Squares
- Weighted least squares modifies linear Thompson sampling by weighting observations according to time, and linear or exponential decay both show promise in general unknown environments.The weighting targets the reduced predictive value of older information.Source: §4.3.3 · p. 33
4.3.4. Adapt-EvE
- Adapt-EvE detects change points and uses a meta-bandit to choose between continuing with trained UCB-Tuned parameters and resetting; an improved Page-Hinckley test yielded a small, consistent benefit across binomial and normally distributed arms.The broader approach permits substituting the bandit algorithm and detector for the problem at hand.Source: §4.3.4 · pp. 33–34
4.3.5. Exp3.R
- Exp3.R resets Exp3 data when an optimistic change detector signals a change; its regret bound is O(N√(H log H)), and it outperformed Adapt-EvE in tested switching, otherwise stochastic experiments.N counts changes in which arm is best.Source: §4.3.5 · pp. 34–35
4.3.6. Kalman Filtered Bandit
- Kalman-filtered bandits perform well under drift and change points but are outperformed by Adapt-EvE in defined change-point cases; results are sensitive to noise estimates, and the approach is valuable when parameters can be predicted well.Source: §4.3.6 · p. 35
4.4. Infinite- and Continuum-Armed Bandits for Continuous Spaces
Infinite- and continuum-armed bandits represent choices over very large or continuous spaces by exploiting relationships among arms. The section describes tree-based methods that use structural assumptions to guide search.
4.4. Infinite- and Continuum-Armed Bandits for Continuous Spaces
- Infinite-armed methods make continuous choice spaces tractable by assuming a well-behaved relationship between arms and payoffs; theoretical work also considers high-dimensional, non-smooth, and multi-objective variants.Source: §4.4 · pp. 35–36
4.4.1. Bandit Algorithm for Smooth Trees (BAST)
- BAST represents a continuous space as a tree and uses a smoothness assumption to guide UCB selection; iterative growth expands selected leaves and explores only optimal branches in depth, using O(n) memory.Source: §4.4.1 · pp. 36–37
4.4.2. Hierarchical Optimistic Optimization (HOO)
- HOO traverses a binary coarse-to-fine tree using optimistic reward bounds, splitting leaves as it searches; it requires a dissimilarity function that lower-bounds mean payoff, a weaker shape assumption than BAST’s.Source: §4.4.2 · p. 37
4.5. Bandits with Multiple Plays
In multiple-play settings, the survey contrasts an efficient adversarial approach with Thompson-sampling extensions, reporting asymptotic guarantees and empirical advantages for the latter.
4.5. Bandits with Multiple Plays
- Multiple-play bandits select m arms per round, with applications in advertising, recommendations, and scarce-sensor search.Examples include displaying multiple ads or product recommendations and using multiple cameras to locate an object.Source: §4.5 · p. 38
4.5.1. Exp3.M
- Exp3.M keeps computation in the original K-arm action space instead of expanding to the exponentially many possible action sets.It updates a weighted sample exponentially.Source: §4.5.1 · p. 38
- [129] reports that Exp3.M converges to the optimal selection faster than other algorithms while remaining highly computable and retaining core theoretical guarantees.An implementation addressing practical considerations runs in O(K log K) time.Source: §4.5.1 · p. 38
4.5.2. Thompson Sampling and MP-TS
- MP-TS selects the top m arms from Thompson-sampling draws and is proved asymptotically optimal under a regret definition adapted to multiple plays.In empirical tests, it outperforms Exp3.M and MP-KL-UCB.Source: §4.5.2 · pp. 38–39
- IMP-TS takes m−1 arms with the highest empirical means and samples the final arm with single-play Thompson sampling, slightly outperforming MP-TS while retaining its asymptotic bound.The reported gains are large when the number of rounds is small, on the order of thousands.Source: §4.5.2 · p. 39
- The survey identifies provably optimal regret with low computation and implementation cost as a benefit of MP-TS and IMP-TS.The authors place these methods within the broader trend toward Thompson-sampling techniques in multi-armed bandits.Source: §4.5.2 · p. 39
5. State of the Theory and Future Work
Regret bounds remain unknown or potentially loose for some bandit variants, while the survey’s future-work direction combines regret minimization with constraints on estimator quality.
State of the Theory
- For oblivious adversaries, regret lower and best upper bounds are O(√H); with switching costs they are O(H2/3), while worst-case adaptive-adversary bounds are linear in H.The survey notes that the O(log H) bound for simple stochastic bandits does not extend to many generalizations.Source: §5 · p. 39
- The survey identifies algorithms with unknown regret properties and bounds that may be looser than possible, and presents a table of known regret bounds.When δ appears in a bound, it denotes a high-probability bound holding with probability at least 1−δ.Source: §5 · p. 39, Table 1 · p. 40
- NeuralBandit outperforms Banditron and LinUCB in empirical experiments and provides robustness to nonstationarity and nonlinearity.The passage attributes the empirical comparison to.Source: §5 · p. 40
- IMP-TS shows better empirical performance than MP-TS.Source: §5 · p. 40
Future Work
- Future work could combine regret minimization with constraints requiring sufficiently strong, high-probability estimates of parameters such as treatment effects.The survey proposes this as a way to reduce ex-ante uncertainty costs in high-cost or high-risk experiments.Source: §5 · p. 41