Source-linked AI summary
On Explore-Then-Commit Strategies
Aurélien Garivier, Emilie Kaufmann, Tor Lattimore
TL;DR
The paper studies whether explore-then-commit strategies can minimize regret in two-armed Gaussian bandits as effectively as unrestricted sequential strategies. It compares fixed-design, explore-then-commit, and fully sequential approaches, finding that commitment incurs asymptotically twice the average regret; matching bounds also establish minimax rate-optimality.
Problem
The paper asks whether natural exploration-then-exploitation strategies can match fully sequential policies in two-armed Gaussian bandits, where the objective is to minimize regret.
Source: §1 · pp. 1–2Method
Results
Takeaways & Limitations
In this setting, optimal strategies must remain fully sequential and mix exploration with exploitation rather than commit after a separate exploration phase.
Source: §1 · p. 2The paper's non-trivial lower-bound analysis for explore-then-commit strategies assumes uniform sampling; using UCB with an almost-surely infinite stopping rule is formally possible but is not a faithful exploration rule.
Source: §6 · p. 8
Abstract
from arXiv · showhide
We study the problem of minimising regret in two-armed bandit problems with Gaussian rewards. Our objective is to use this simple setting to illustrate that strategies based on an exploration phase (up to a stopping time) followed by exploitation are necessarily suboptimal. The results hold regardless of whether or not the difference in means between the two arms is known. Besides the main message, we also refine existing deviation inequalities, which allow us to design fully sequential strategies with finite-time regret guarantees that are (a) asymptotically optimal as the horizon grows and (b) order-optimal in the minimax sense. Furthermore we provide empirical evidence that the theory also holds in practice and discuss extensions to non-gaussian and multiple-armed case.
1 Introduction
The paper asks whether exploration-then-commit strategies can match unrestricted sequential choices in two-armed Gaussian bandits. It finds that commitment is costly, with regret asymptotically twice as large on average as fully sequential strategies, whether the mean gap is known or unknown.
1 Introduction
- Fully sequential strategies achieve asymptotically half the average regret of explore-then-commit strategies, which must commit even if later observations disappoint.The paper characterizes this cost as regret asymptotically twice as large on average.Source: §1 · p. 2
- In the known-gap setting, a sequential probability ratio test yields explore-then-commit regret log(T)/∆, four times better than fixed design but still worse than fully sequential strategies.The paper proves a lower bound showing no explore-then-commit strategy can improve on this result.Source: §1 · p. 2
- For known gaps, the fully sequential rate is log(T)/(2∆), improving on fixed-design strategies by a factor of 8 and on SPRT by a factor of 2.The authors also prove that no strategy can improve on this result.Source: §1 · p. 2
- For unknown gaps, an explore-then-commit strategy using modified fixed-budget best-arm identification achieves regret 4 log(T)/∆, optimal within that strategy class.The paper states that this remains a factor of 2 worse than fully sequential strategies such as UCB.Source: §1 · p. 2
- The analysis characterizes achievable asymptotic regret across fixed-design, explore-then-commit, and fully sequential strategies, with explicit finite-time bounds that imply optimal minimax guarantees.The authors present lower bounds and matching strategies.Source: §1 · p. 2
2 Notation and Summary of Results
This section defines the two-armed Gaussian bandit setting and formalizes explore-then-commit and fixed-design strategies. It states tight regret bounds for uniformly efficient strategies and notes that matching strategies yield minimax rate-optimality.
2 Notation and Summary of Results
- The setting assumes a known horizon T and unknown arm means; the goal is to minimize regret over T steps.The section defines the optimal arm and the gap as the absolute difference between the two means.Source: §2 · p. 3
- An explore-then-commit strategy alternates uniform sampling until an even stopping time, then selects an arm measurable from the observations collected by that time.The stopping time depends on the horizon; the paper focuses on uniform sampling for two-armed Gaussian bandits with equal variances.Source: §2 · p. 3
- A fixed-design strategy is an explore-then-commit strategy whose stopping time is a fixed number of samples per arm.The paper denotes the sets of explore-then-commit, fixed-design, and all strategies separately.Source: §2 · p. 3
- For each strategy class, the paper gives a regret lower bound and establishes that the bounds are tight with matching strategies and a tight non-asymptotic bound implying minimax rate-optimality.The bounds are organized by strategy class and by whether the mean gap is known.Source: §2 · p. 3
3 Explore-Then-Commit Strategies
For known gaps, adaptive stopping lets ETC improve on fixed-design exploration; for unknown gaps, BAI-based ETC reaches the lower bound with refined finite-time guarantees.
Fixed Design Strategies for Known Gaps
- The optimized fixed-design strategy has regret asymptotic to 4 log(T)/Δ.The design explores each action a fixed number of times before committing.Source: §3 · pp. 3–4
- The fixed-design 4 log(T)/Δ expression is not a lower bound, even up to an additive constant, and regret can fall below it by a diverging amount.For large Δ, the additive Δ term in the upper bound is necessary because at least one identifying observation cannot be avoided.Source: §3 · p. 4
Explore-Then-Commit Strategies for Known Gaps
- For known gaps, SPRT-ETC matches the asymptotic regret lower bound and improves on the optimal fixed-design strategy.It alternates between arms and stops when the SPRT reaches a confidence threshold depending on Δ and T.Source: §3 · pp. 4–5
- For testing the known-gap hypotheses, a sequential probability ratio test needs asymptotically one quarter as many expected samples as a batch test at the same error level.The respective sample sizes are asymptotic to log(1/δ)/Δ² and (4/Δ²) log(1/δ).Source: §3 · p. 4
- Theorem 2 gives an upper bound when TΔ² ≥ 1 and a separate bound otherwise, with a uniform bound stated for all T and Δ.The supplied passage does not include the bound expressions.Source: §3 · p. 5
Explore-Then-Commit Strategies for Unknown Gaps
- For unknown gaps, BAI-ETC matches the asymptotic lower bound and its refined threshold supports asymptotic optimality and order-optimal minimax regret.The threshold uses log(T/2n) rather than log(T); the passage states this refinement is needed for the non-asymptotic result.Source: §3 · p. 5
4 Fully Sequential Strategies for Known and Unknown Gaps
For both known and unknown gaps, the paper reports that fully sequential strategies improve on the best ETC strategies by a factor of two, with distinct algorithms for each setting.
Fully Sequential Strategies
- Fully sequential strategies improve on the best ETC strategies by a factor of 2 in both the known- and unknown-gap settings.The paper identifies its unknown-gap algorithm as simultaneously asymptotically optimal and order-optimal in the minimax sense.Source: §4 · pp. 6–7
Known Gaps
- For known gaps, the lower bound motivates Δ-UCB, which uses the gap to guide arm choices but requires both T and Δ in advance.It selects the less-played arm unless the other arm’s upper confidence bound is close to Δ above the empirical estimate of the most-played arm.Source: §4 · p. 6
Unknown Gaps
- For unknown gaps, UCB* is presented as simultaneously asymptotically optimal and minimax order-optimal; its smaller confidence bonus improves empirically on UCB.The UCB* regret bound is stated under conditions involving T, Δ, and ε.Source: §4 · p. 7
- For K > 2, the strategy remains asymptotically optimal but has minimax regret Ω(√(TK log(K))).The supplied passage begins to describe a factor comparison but does not provide its value.Source: §4 · p. 7
5 Numerical Experiments
The experiments compare five strategies over multiple horizons and report that observed regret growth and policy ordering broadly reflect the theory, with short-horizon exceptions.
Numerical Experiments
- The plotted regrets are estimated across different horizons for five strategies on a bandit instance with Δ = 1/5.The plot reports estimated slopes of ΔRπ(T) on a logarithmic scale.Source: §5 · p. 7
- Estimated log-scale slopes were FB−ETC 3.65, BAI−ETC 2.98, UCB 1.59, SPRT−ETC 1.03, and D−UCB 0.77.These estimates come from a bandit problem with Δ = 1/5 and 4.105 Monte Carlo replications.Source: §5 · p. 7
- The experiments broadly reflect the theory in logarithmic regret growth, approximate theoretical coefficients, and relative policy ordering, but short-horizon behavior differs.BAI performs well at short horizons and starts to be beaten only when TΔ² is much larger than 10.Source: §5 · p. 7
6 Conclusion: Beyond Uniform Exploration, Two Arms and Gaussian distributions
The conclusion examines how ETC regret minimization extends beyond uniform exploration, two arms, and Gaussian rewards. It notes limits to general multi-arm analysis and gives a factor-two comparison for two-armed Gaussian problems.
Beyond Uniform Exploration, Two Arms and Gaussian distributions
- For non-uniform sampling, no non-trivial lower bound applies to every formally valid ETC strategy, since UCB sampling with an almost-surely infinite stopping rule is allowed.The paper treats uniform sampling as the relevant exploration rule because it is known to be optimal for two-armed Gaussian bandits [Kaufmann et al., 2014].Source: §6 · p. 8
- The conclusion describes successive elimination as a multiple-arm ETC extension and states that it is suboptimal by a factor 2 on every two-armed Gaussian problem.The passage also notes that the most favorable relative-efficiency case seems to have µ2 = · · · = µK; the comparison with Lai and Robbins’ lower bound is said to grow with K.Source: §6 · p. 8
- Using Track-and-Stop exploration with risk 1/T, the paper gives an ETC regret bound for one-parameter exponential families when arm 1 is best.The bound is stated for means where µ1 > maxa≠1 µa and is based on an optimization involving T*(µ) and w*(µ).Source: §6 · p. 8
- For K > 2, the paper reports no general closed-form expressions for T*(µ) or w*(µ), while conjecturing a factor-two ETC suboptimality in a specified worst case.The conjectured case has µ1 and µ2 much larger than the other means; the stated comparison is to the two-arm case.Source: §6 · p. 8
Notation for the Proofs
The proof notation uses successive observations from each arm and, without loss of generality, orders the means so arm 1 is better.
Notation for the Proofs
- (Xs) and (Ys) denote the successive observations from arms 1 and 2, respectively.The passage begins to state a further relation between the sequences but does not provide it in the supplied text.Source: Notation for the Proofs · p. 10
- In the appendix proofs of regret upper bounds, assume without loss of generality that µ1 > µ2.The gap is then written as ∆ = µ1 − µ2.Source: Notation for the Proofs · p. 10
- Under this convention, ∆ denotes the positive difference between the better and worse arm means..Source: Notation for the Proofs · p. 10
A Proof of the Lower Bounds (Theorems 3, 4, 6 and Lai&Robbins)
The lower-bound proofs use change of measure between nearby reward vectors with different expected algorithm behavior. They apply this approach to both general policies and ETC strategies.
A Proof of the Lower Bounds (Theorems 3, 4, 6 and Lai&Robbins)
- The proofs compare a reward vector with a nearby alternative under which the algorithm’s expected behavior differs.This change-of-measure approach follows Lai and Robbins [1985], and the paper says its improvements use Inequality 4 in [Garivier et al., 2016].Source: A Proof of the Lower Bounds (Theorems… · p. 10
- The argument applies the change-of-measure inequality to stopping times at which the suboptimal-arm count is measurable.The passage says the inequality holds for every alternative mean vector and every such stopping time.Source: A Proof of the Lower Bounds (Theorems… · p. 10
- The paper presents applying this lower-bound argument to ETC strategies as an extension of its routine use for general policies.It also notes that similar arguments can yield non-asymptotic lower bounds, citing Garivier et al. [2016].Source: A Proof of the Lower Bounds (Theorems… · pp. 10–11
- For ETC strategies, the proof uses the fact that both arms are sampled equally until the stopping time and that the final arm count is measurable at that time.The supplied passage states N1(τ ∧ T) = N2(τ ∧ T) = (τ ∧ T)/2.Source: A Proof of the Lower Bounds (Theorems… · p. 10
B Proof of Theorem 1
The proofs bound regret using Gaussian tail probabilities, stopping-time arguments, and a modified best-arm-identification exploration phase. They cover fixed-budget ETC, sequential ETC, and unknown-gap ETC analyses.
C Proof of Theorem 2
- The sequential ETC proof uses an exponential martingale and optional stopping to bound the probability of committing to the suboptimal arm.For T∆² ≤ 1, the proof uses one sample from each arm and gives the regret upper bound ∆ + T∆/2.Source: C Proof of Theorem 2 · pp. 13–14
D Proof of Theorem 5
- The unknown-gap ETC proof analyzes a modified fixed-budget best-arm-identification phase and combines its finite-time bound with the trivial regret bound ∆T.The supplied proof passage says this minimum yields a regret bound for all µ, but its displayed conclusion is truncated.Source: D Proof of Theorem 5 · p. 14
E Proof of Theorem 7
The proof bounds the exploration stopping time and uses concentration to control estimates after exploration. It derives logarithmic asymptotic regret for UCB.
E Proof of Theorem 7
- The proof defines τ as the maximum of two arm-specific stopping times and bounds each expected stopping time using a concentration lemma.For each i, Eµ[τi] ≤ 1 + 9/ε².Source: E Proof of Theorem 7 · p. 15
- For t > 2τ, the best arm’s estimated mean, hat μ_{A_t,max}(t−1), differs from its true mean, μ_{A_t,max}, by less than εT; the passage then turns to bounding expected suboptimal-arm draws.Source: E Proof of Theorem 7 · p. 15
- 1/(2∆) bounds the asymptotic regret ratio R∆-UCB(T)/log(T).The proof obtains this from an upper bound on the expected number of suboptimal-arm draws.Source: E Proof of Theorem 7 · p. 15
F Proof of Theorem 8
The proof of Theorem 8 combines deviation bounds to establish asymptotic and minimax regret guarantees. The accompanying Gaussian deviation inequalities support the analyses, while their extension to sub-Gaussian variables remains unresolved.
F Proof of Theorem 8
- The asymptotic and minimax results follow by taking a limit with ε = log^-1/8(T) and optimizing the finite-time bound against naive RUCB.The proof’s concentration bounds apply under T(∆−ε)² ≥ 2 and Tε² ≥ e².Source: F Proof of Theorem 8 · p. 16
G Deviation Inequalities
- Lemma 1 collects specific deviation results used in the regret analyses and presented as independently interesting.The proof of the lemma uses peeling techniques and inequalities for Gaussian sums.Source: G Deviation Inequalities · pp. 16–17
- Whether the stated deviation results hold for sub-Gaussian variables is unknown; adding log-log terms to the confidence interval may yield weaker results but sacrifices minimax optimality.The proof relies on Gaussian-sum inequalities.Source: G Deviation Inequalities · p. 17