Source-linked AI summary
What Doubling Tricks Can and Can't Do for Multi-Armed Bandits
Lilian Besson, Emilie Kaufmann
TL;DR
When the horizon is unknown, the Doubling Trick can make a bandit algorithm anytime, but it is unclear whether one schedule can retain both logarithmic problem-dependent and square-root minimax regret. The paper analyzes geometric and exponential schedules, finding that geometric doubling preserves positive-power bounds but not logarithmic ones. Exponential doubling preserves logarithmic bounds, while its ability to preserve minimax bounds remains unresolved.
Problem
It is unknown whether a single Doubling Trick can make an algorithm anytime while preserving both problem-dependent logarithmic and minimax square-root regret.
Source: §1 · p. 3Method
Results
Geometric doubling preserves minimax-scale bounds but not logarithmic bounds, whereas exponential doubling preserves logarithmic bounds and its minimax preservation remains open.
Source: §6 · p. 11Takeaways & Limitations
For stochastic problems, geometric doubling should be avoided when preserving logarithmic regret is required.
Source: §1 · p. 2, §6 · p. 11Whether an exponential doubling sequence can preserve minimax regret bounds remains an open question.
Source: §4.2 · p. 8, §6 · p. 11
Abstract
from arXiv · showhide
An online reinforcement learning algorithm is anytime if it does not need to know in advance the horizon T of the experiment. A well-known technique to obtain an anytime algorithm from any non-anytime algorithm is the "Doubling Trick". In the context of adversarial or stochastic multi-armed bandits, the performance of an algorithm is measured by its regret, and we study two families of sequences of growing horizons (geometric and exponential) to generalize previously known results that certain doubling tricks can be used to conserve certain regret bounds. In a broad setting, we prove that a geometric doubling trick can be used to conserve (minimax) bounds in $R\_T = O(\sqrt{T})$ but cannot conserve (distribution-dependent) bounds in $R\_T = O(\log T)$. We give insights as to why exponential doubling tricks may be better, as they conserve bounds in $R\_T = O(\log T)$, and are close to conserving bounds in $R\_T = O(\sqrt{T})$.
1. Introduction
When a bandit algorithm must operate without knowing the experiment horizon, the Doubling Trick offers a general way to make it anytime. This section motivates the question of whether one trick can preserve both logarithmic problem-dependent and square-root minimax regret, and frames the paper’s answer as negative.
1. Introduction
- The Doubling Trick repeatedly runs a base algorithm with increasing horizons, making it a general route to anytime behavior when the total number of decisions is unknown.In website optimization or smart-radio communication, the total number of decisions may not be known in advance.Source: §1 · p. 1
- The study compares geometric and exponential horizon sequences and concludes that geometric doubling should be avoided for stochastic problems.The paper also reports experiments after presenting bounds for the two families.Source: §1 · pp. 2–3
- Bandit performance is measured by regret: adversarial problems have square-root-scale worst-case bounds, while stochastic problems can admit problem-dependent logarithmic bounds.In the stochastic setting, the bound’s constant depends on the arm distributions; hard instances can make that constant large.Source: §1 · p. 2
- kl-UCB++ is simultaneously minimax optimal and asymptotically optimal, but it is not anytime, prompting the question of whether doubling can remove that limitation.The paper’s motivating question is whether one Doubling Trick can preserve both problem-dependent and minimax regret.Source: §1 · p. 3
- The paper answers that a single Doubling Trick cannot preserve both types of guarantee and identifies a constant multiplicative loss when bounds are conserved.The constant loss is called the “constant manipulative loss.”Source: §1 · p. 3
2. Doubling Tricks
The Doubling Trick converts a possibly non-anytime algorithm into an anytime one by restarting it on successively longer horizon blocks. The analysis uses generic regret bounds over those blocks to study which growth schedules preserve a base algorithm’s guarantees.
2. Doubling Tricks
- The Doubling Trick fully restarts the base algorithm at each new sequence boundary and runs it for that block’s length.The sequence must be non-decreasing and diverge; the algorithm is reinitialized at time T_i + 1.Source: §2 · p. 3
- The geometric schedule T_i = 2^i is the conventional Doubling Trick, while prior stochastic-bandit work also used T_i = 2^(2^i).The latter schedule was used to make UCB-R anytime.Source: §2 · p. 3
- For general bandit models, total regret is upper-bounded by summing regret over the horizon blocks, while stochastic i.i.d. rewards also permit a lower bound from completed blocks.The analysis excludes the final partial block for the lower bound and can enlarge it for the upper bound.Source: §2 · p. 4
- The sequence-growth rate determines whether an anytime version can retain a regret bound, with an explicit multiplicative loss greater than one.The paper examines geometric and exponential growth; slow-growing schedules such as arithmetic progressions can yield linear regret.Source: §2 · p. 4
3. What the Geometric Doubling Trick Can and Can’t Do
Geometric horizons can preserve regret bounds with a positive power of T, but they cannot preserve logarithmic bounds in stochastic bandits. The lower-bound analysis explains the extra logarithmic factor, while the upper bound quantifies the loss for positive-power guarantees.
3.1. Conserving a Regret Upper Bound with Geometric Horizons
- For 0 < γ < 1 and δ ≥ 0, geometric horizons preserve a base bound of order T^γ(log T)^δ up to a constant multiplicative loss, under the theorem’s stated remainder and sequence conditions.The theorem assumes R_T(A_T) ≤ c T^γ(log T)^δ + f(T), with f(t) = o(t^γ(log t)^δ), and requires T_0(b − 1) > 1 when δ > 0.Source: §3.1 · p. 5
- For γ = 1/2 and δ = 0, the optimized geometric loss is approximately 3.33, compared with approximately 3.41 for the usual choice b = 2.The cited practical discussion prefers T_0 much larger than K in its experiments.Source: §3.1 · p. 5
3.2. A Regret Lower Bound with Geometric Horizons
- For stochastic models, a base lower bound of c(log T)^δ with δ > 0 yields a doubled-algorithm lower bound of order (log T)^(δ+1), so geometric horizons cannot preserve logarithmic regret.At δ = 1, the paper states that regret grows at least on the order of (log T)^2.Source: §3.2 · pp. 5–6
3.3. Proof of Theorem 5
- The lower-bound proof sums regret across completed geometric blocks, whose count grows on the order of log_b(T), producing the additional logarithmic factor.The argument uses the stochastic-model lower bound while excluding the final partial sequence.Source: §3.3 · pp. 6–7
4. What Can the Exponential Doubling Trick Do?
Exponential doubling sequences can preserve logarithmic regret and a broader family of regret bounds, though polynomial-rate bounds incur a changed exponent. The lower-bound and constant-loss analyses clarify both their promise and their qualifications.
4.1. Conserving a Regret Upper Bound with Exponential Horizons
- Theorem 7 preserves bounds of the form O(T^γ(log T)^δ) for 0≤γ<1, but the polynomial factor becomes T^(bγ).For γ>0, the constant loss can be made arbitrarily small by choosing a sufficiently large first step T0.Source: §4.1 · pp. 7–8
- For O(log T) regret, b=2 gives the optimal exponential-trick loss of 4, versus 8.0625 in Auer and Ortner (2010, Sec.4)1.The paper states that logarithmic regret is preserved with multiplicative loss ℓ≥4.Source: §4.1 · p. 8
4.2. A Regret Lower Bound with Exponential Horizons
- For stochastic models, an exponential doubling trick preserves a lower bound cT^γ when the base algorithm has that bound, for 0<γ≤1.The theorem gives a positive constant c′ for the anytime version.Source: §4.2 · p. 8
- Because b cannot depend on T, taking b→1 does not establish matching upper and lower bounds for minimax regret.The paper therefore presents exponential tricks as promising candidates for preserving both problem-dependent and minimax bounds, not as a proof that they do so.Source: §4.2 · p. 8
4.3. Proof of Theorem 7
- At T0=a, the proof’s multiplicative loss has minimum 4 for any δ and γ; increasing T0 makes the a/T0 term tend to zero.The proof also notes that a more subtle bound does not appear to simplify the logarithmic terms.Source: §4.3 · pp. 9–10
5. Numerical Experiments
The experiments compare doubling sequences on AFHG and kl-UCB++ against horizon-aware and anytime baselines. They report that the no-restart heuristic performs better empirically than the standard Doubling Trick, while noting important limits on its applicability and analysis.
5. Numerical Experiments
- Experiments compare AFHG for Gaussian bandits and kl-UCB++ for Bernoulli bandits using geometric and exponential doubling sequences.The comparison includes the horizon-aware versions and kl-UCB (or UCB for Gaussian bandits) as an anytime baseline.Source: §5 · p. 10, §5.2 · p. 11
5.1. Two Index-Based Algorithms
- Each algorithm chooses the arm with the highest index, and both index-based algorithms assume the horizon T is known.The experiments apply AFHG to Gaussian bandits and kl-UCB++ to bounded rewards, including Bernoulli bandits.Source: §5.1 · p. 10
5.2. Experiments
- The experiments use K=9 arms, T=45678, and 1000 repetitions, on either one evenly spaced-mean instance or random instances.The plotted average regret is compared with an asymptotic lower bound; the sequences use T0=200, with exponential variants including b=2 and b=1.1.Source: §5.2 · p. 11
- The no-restart heuristic exhibits better empirical performance than the standard Doubling Trick, but cannot be applied to every algorithm and is difficult to analyze.The paper says it is inapplicable to arm-elimination algorithms and that successive non-uniform prior information has an unpredictable effect on regret.Source: §5.2 · p. 11
6. Conclusion
The conclusion finds that geometric doubling preserves minimax regret bounds with constant loss but fails to preserve logarithmic problem-dependent bounds; exponential doubling preserves logarithmic bounds, while its minimax guarantee remains unresolved. The appendix supports these results by analyzing how doubling partitions regret across sequences.
6. Conclusion
- Geometric doubling preserves minimax bounds with constant loss but not logarithmic problem-dependent bounds; exponential doubling preserves logarithmic bounds, while its minimax status remains open.The authors believe exponential doubling may preserve minimax bounds of the form T^γ(log T)^δ, based on partial upper and lower bounds.Source: §6 · p. 11
- The conclusion leaves open whether any anytime algorithm can be both asymptotically optimal with the exact problem-dependent constant and minimax optimal.The authors believe doubling non-anytime algorithms such as kl-UCB++ cannot achieve this, and conjecture exponential doubling will not recover the exact constant.Source: §6 · p. 11
A.2. Proof of Theorem 4, “Conserving a Regret Upper Bound with Geometric Horizons”
The proof bounds regret under geometric horizons by summing the regret over sequence blocks and deriving a constant multiplicative loss. That loss separates into factors with distinct parameter dependencies.
A.2. Proof of Theorem 4, “Conserving a Regret Upper Bound with Geometric Horizons”
- The geometric-horizon upper-bound proof sums regret over sequence blocks and bounds the result by a constant multiple of the original regret order.It uses nondecreasing regret-bound terms and bounds the block lengths by a geometric expression.Source: §A.2 · p. 17
- The multiplicative loss factors into ℓ1, depending on δ, T0, and b, and ℓ2, depending on γ and b; ℓ1 equals 1 when δ = 0.For fixed b, ℓ1 approaches 1 as T0 grows, and the proof says this convergence is rapid when T0 is large enough.Source: §A.2 · p. 18
- For fixed γ, the proof notes that ℓ2 has a global minimum over b > 1, but its derivative has no explicit generic root, so b can be optimized numerically.The function diverges as b approaches 1 from above and as b grows without bound.Source: §A.2 · p. 18
A.3. Proof of Theorem 9, “Minimax Regret Lower Bound with Exponential Horizons”
The proof applies the base algorithm’s regret lower bound across completed exponential-horizon sequences. The location of the experiment horizon within the final sequence matters to the worst-case bound.
A.3. Proof of Theorem 9, “Minimax Regret Lower Bound with Exponential Horizons”
- The lower-bound proof applies the base algorithm’s guarantee to completed exponential-horizon blocks and uses a telescoping sum.It also uses that the final sequence endpoint is at least T and that its logarithm is bounded below in terms of log(T).Source: §A.3 · p. 19
- The proof compares the transformed algorithm’s lower bound with the base algorithm’s bound, and the worst case can depend on where T falls within the final sequence.The text highlights horizons close to the sequence endpoint when discussing this worst-case placement.Source: §A.3 · p. 19
Appendix B. Minimax Regret Lower Bound with Geometric Horizons
For stochastic models, the geometric doubling lower bound retains the base algorithm’s T^γ scale with a multiplicative factor and an O(log T) term. The factor depends on γ and the growth ratio b, and can exceed 1.
Appendix B. Minimax Regret Lower Bound with Geometric Horizons
- If the base algorithm has regret at least cT^γ for 0 < γ < 1, geometric doubling gives a lower bound ℓ0(γ, b)cT^γ + g0(T), where g0(T) = O(log T) = o(T^γ).The result is stated for stochastic models and a geometric sequence with parameters T0 and b > 1.Source: Appendix B · pp. 19–20
- The lower-bound factor ℓ0 is positive, tends to zero as b grows without bound, and can exceed 1 for some choices of b.When ℓ0 > 1, the authors state that the geometric anytime version suffers a non-improvable constant multiplicative loss relative to the base algorithm.Source: Appendix B · pp. 19–20
- For fixed γ, the factor ℓ0 decreases with b and diverges as b approaches 1 from above.For γ = 1/2, choosing b to minimize the upper-bound loss yields a lower-bound factor of approximately 1.71, so that choice cannot preserve the optimal constant.Source: Appendix B · pp. 20–21
Appendix C. An Efficient Heuristic, the Doubling Trick with “No Restart”
The no-restart doubling trick initializes each new algorithm using the history of actions and rewards from earlier sequences. It is a heuristic without a general theoretical guarantee and is unsuitable for some algorithm classes.
Appendix C. An Efficient Heuristic, the Doubling Trick with “No Restart”
- Each new algorithm is fed the observed history from prior plays, even though it might have chosen a different action path.The method creates a fresh algorithm at each sequence boundary and supplies it with observations from the prior plays of the deployed algorithm.Source: Appendix C · p. 21
- DT no-restart is practically applicable to index-based algorithms whose indexes use the horizon as a numerical parameter, such as AFHG and kl-UCB++.The passage says arm-elimination methods, including Explore-Then-Commit, will most surely fail with this approach.Source: Appendix C · p. 21
- A regret upper bound for DT no-restart remains an open problem for a generic algorithm, despite the authors' intuition that prior observations can improve performance on later intervals.The proposed intuition is specifically for observations from the same i.i.d. process.Source: Appendix C · p. 21
Appendix D. Basic but Useful Results
Appendix D collects conventions and inequalities used in the proofs of the main theorems. Appendix E adds experiments, including Gaussian-bandit results where doubling variants converge more slowly than the baselines.
Appendix D. Basic but Useful Results
- Appendix D fixes logarithm and integer-rounding conventions, and notes that its functional inequalities are used in proofs of the main theorems.Logarithms are natural unless a base is specified; floor and ceiling are defined explicitly.Source: Appendix D · p. 22, §D.3 · p. 23
D.1. Weighted Geometric Inequality
- For non-decreasing non-negative f, the weighted geometric inequality bounds a sum using its final term, while its bound becomes uninformative as δ approaches zero.The proof uses monotonicity and a geometric-series sum.Source: §D.1 · p. 22
D.2. Another Sum Inequality
- The additional sum inequality bounds increasing terms from a doubly exponential sequence by a constant-scale expression involving the last term.The stated result applies for a > 1, b > 1, and γ > 0.Source: §D.2 · p. 22
D.3. Basic Functional Inequalities
- The functional inequalities cover fractional-power comparisons, logarithmic bounds, and monotonicity of x^γ(log x)^δ, supporting upper-bound proofs.The cited lemmas include conditions on γ, δ, and the domain of the logarithm.Source: §D.3 · p. 23, §D.4 · p. 24
D.4. Controlling an Unbounded Sum of Dominated Terms
- If f(t) = o(g(t)) and the sequence sum of g(T_i) is bounded by h(T), then the corresponding unbounded sum of f(T_i) remains bounded by h(T).The lemma assumes positive, diverging, non-decreasing functions and sequences.Source: §D.4 · p. 24
Appendix E. Additional Experiments
- Appendix E adds experiments on Gaussian bandits and the heuristic no-restart doubling trick.The Gaussian experiment is included in subsection E.1.Source: Appendix E · p. 25, §E.1 · p. 25
E.1. Experiments with Gaussian Bandits (with Known Variance)
- The Gaussian-bandit example shows near-constant regret for UCB, AFHG, and each doubling trick, but geometric b = 2 and slow exponential b = 1.1 converge more slowly.The experiment uses nine Gaussian arms with distinct means; the passage attributes the ease of identifying the best arm to their separation.Source: Figure 5 · p. 25
E.2. Experiments with DT no-restart
The experiments find that no-restart doubling can improve empirical performance over restarting and can approach the non-anytime kl-UCB++ baseline. Results also depend on the doubling sequence and problem instance.
E.2. Experiments with DT no-restart
- The no-restart method is presented as a heuristic without a proved theoretical guarantee.The experiments compare its performance with the restarting version.Source: §E.2 · p. 25
- No-restart kl-UCB++ can outperform kl-UCB and perform similarly to non-anytime kl-UCB++, while short initial sequences cause early regret spikes and fast-growing sequences can cause later spikes.The Bernoulli experiment marks the effect of a new sequence at t = 40000 for T_i = 200 × 2^i.Source: §E.2 · p. 25, Figure 6 · p. 26
- On the easy Bernoulli instance, geometric no-restart kl-UCB++ outperforms both kl-UCB and kl-UCB++.The arms' means are evenly spaced in [0, 1].Source: Figure 7 · p. 26