Source-linked AI summary
lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
Kevin Jamieson, Matthew Malloy, Robert Nowak, Sébastien Bubeck
TL;DR
Fixed-confidence best-arm identification requires adaptive sampling that remains reliable when arm means are arbitrarily close. The paper develops lil’UCB using LIL-based confidence bounds and a novel stopping rule, and reports optimal-up-to-constants sample complexity with superior practical performance. The lower-bound analysis establishes the necessity of the doubly logarithmic factor.
Problem
Fixed-confidence best-arm identification must identify the highest-mean arm uniformly over unknown means, including cases where the best and second-best arms are arbitrarily close.
Method
lil’UCB combines finite-sample LIL confidence bounds with a stopping criterion that avoids naive union bounds over time and arms.
Results
The paper proves sample complexity optimal up to constants relative to the LIL-based lower bound and reports superior practical performance against state-of-the-art algorithms.
Takeaways & Limitations
The LIL lower bound and lil’UCB analysis establish that the doubly logarithmic factor is necessary and achievable for fixed-confidence best-arm identification.
Takeaways & Limitations
The heuristic parameter settings used in practice do not satisfy Theorem 2’s conditions, so the stated guarantee does not apply to that heuristic.
Abstract
from arXiv · showhide
The paper proposes a novel upper confidence bound (UCB) procedure for identifying the arm with the largest mean in a multi-armed bandit game in the fixed confidence setting using a small number of total samples. The procedure cannot be improved in the sense that the number of samples required to identify the best arm is within a constant factor of a lower bound based on the law of the iterated logarithm (LIL). Inspired by the LIL, we construct our confidence bounds to explicitly account for the infinite time horizon of the algorithm. In addition, by using a novel stopping time for the algorithm we avoid a union bound over the arms that has been observed in other UCB-type algorithms. We prove that the algorithm is optimal up to constants and also show through simulations that it provides superior performance with respect to the state-of-the-art.
1 Introduction
The paper frames fixed-confidence best-arm identification as requiring adaptive sampling when arm means may be arbitrarily close. It introduces lil’UCB, whose LIL-based confidence bounds and stopping rule target optimal sample complexity while improving practical performance.
- Problem: Fixed-confidence best-arm identification must find the unique highest-mean arm with probability at least 1 − δ while adapting to unknown mean gaps.The procedure must work uniformly over mean values, including arbitrarily close best and second-best arms.
- Lower-bound context: The LIL establishes that the doubly logarithmic factor in the best-arm sample complexity is necessary, resolving uncertainty about the earlier upper and lower bounds.The cited result implies that the relevant order of samples is both necessary and sufficient up to constants.
- LIL motivation: A two-arm random-walk argument gives the characteristic sample scale 2∆^-2 log log ∆^-2 for distinguishing arms with gap ∆.The deterministic drift crosses the LIL boundary when t∆ ≈ √(2t log log t).
- Contribution: lil’UCB uses finite-sample LIL confidence bounds and a novel stopping criterion to avoid naive union bounds over time and arms.The stopping rule permits larger confidence bounds for arms with larger gaps than a uniform-over-arms analysis would allow.
- Empirical motivation: lil’UCB avoids repeated median-elimination subroutines and is reported to have the best known theoretical sample-complexity bounds and superior practical performance.The comparison is made against state-of-the-art algorithms, including PRISM and exponential-gap elimination.
2 Lower Bound
The lower-bound section shows that fixed-confidence best-arm identification must pay a doubly logarithmic factor when the gap is unknown. The argument reduces the problem to sequentially testing the sign of an unknown mean and invokes LIL behavior.
- Lower bound: Any procedure with error probability at most δ ∈ (0, 1/2) must satisfy E∆[T]∆^-2 log log ∆^-2 ≥ 2 − 4δ.This lower bound applies to the two-arm fixed-confidence setting.
- Reduction: For two arms with unknown gap ∆, the fixed-confidence problem reduces to deciding whether an unknown mean difference is positive or negative.A known value for one arm leaves sampling of the other arm as a sequential sign-testing problem.
- Implication: Consequently, no fixed-confidence best-arm procedure can use fewer than a doubly logarithmic number of samples in the inverse gaps for all arms.The two-arm corollary extends to the multi-arm statement reported in the section.
- Proof strategy: The proof studies a generalized sequential probability ratio test that compares the running empirical mean with a sequence of thresholds.If the thresholds are too small, LIL fluctuations prevent uniformly reliable decisions.
- Proof presentation: The paper supplies a shorter self-contained argument for a slightly simpler version of the cited lower-bound result.The original proof is described as quite involved.
3 Procedure
lil’UCB samples the arm with the largest LIL-inspired upper confidence bound and stops when one arm has received a constant fraction of all samples. Its analysis gives a high-probability sample bound with constants depending on algorithm parameters.
- Procedure: lil’UCB samples the arm with the largest upper confidence bound, whose form accounts for the law of the iterated logarithm.The algorithm is an Upper Confidence Bound procedure based on a finite-sample LIL.
- Procedure: The procedure terminates when an arm has been sampled more than a constant fraction of the total number of samples.
- Procedure: The algorithm initializes by sampling each arm once and then continues while the stopping condition is unmet.
- Guarantee: With probability at least 1 −√ρδ − 4ρδ 1−ρδ, lil’ UCB stops after at most c1H1 log(1/δ) + c3H3 samples.The constants c1 and c3 depend only on ε and β.
- Guarantee: Regardless of ε and β, the algorithm obtains optimal query complexity H1 log(1/δ) + H3 up to constant factors.
4 Proof of Theorem 2
The proof combines finite LIL concentration with controls on suboptimal-arm sampling and the stopping process. It establishes bounds on sampling errors and shows that the resulting total complexity matches the theorem’s stated form up to constants.
- Concentration: A finite form of the law of the iterated logarithm supplies the concentration bound used in the analysis.The proof also invokes maximal inequalities for sub-Gaussian variables.
- Concentration: The proof partitions time using u0 = 1 and u_k+1 = ⌈(1 + ε)u_k⌉ to control deviations within successive intervals.
- Suboptimal-arm sampling: The proof compares empirical upper confidence bounds across arms to show that suboptimal arms cannot continue being selected beyond gap-dependent thresholds.
- Probability control: With probability at least 1 −√ρδ − 2ρδ 1−ρδ, the analysis establishes the required simultaneous inequalities for all suboptimal arms and times.
- Suboptimal-arm sampling: Lemma 2 bounds suboptimal-arm sampling by (β + 2)2(c1H1 log(1/δ) + c3H3), treating ε and log log(β) factors as constants.
- Stopping and conclusion: Only the optimal arm meets the stopping condition, and combining this fact with the suboptimal-arm bound yields the theorem’s total sample bound.
5 Implementation and Simulations
The experiments compare stopping times and anytime identification performance across three problem scenarios and varied numbers of arms. lil’UCB and UCB1 with LIL stopping lead the theoretical algorithms in stopping-time performance, while UCB methods collect information more effectively before termination.
- Stopping criterion: The LIL stopping criterion can be applied to fixed-confidence algorithms by splitting confidence between the algorithm and the stopping rule.The described implementation runs the algorithm with δ/2 and assigns the remaining δ/2 to the LIL stopping criterion.
- Computational considerations: UCB1 was omitted for the largest problem size because its O(n) computation per time step caused practical scaling constraints.The lil’UCB procedures require O(log(n)) computation per step, whereas the first three comparison algorithms require O(1) amortized computation.
- Experimental setup: The evaluation compares algorithms across three scenarios and varied problem sizes, measuring stopping times and anytime best-arm identification.The scenarios are 1-sparse, α = 0.3, and α = 0.6; stopping-time experiments use 40 runs per setting, while anytime experiments use 5000 repetitions.
- Stopping-time results: lil’UCB+LS and UCB1+LS lead the theoretical algorithms in empirical stopping-time performance, while successive elimination remains practically competitive because of small constants.Exponential-gap elimination with LIL stopping barely improves over uniform sampling with the same criterion, consistent with costly repeated median-elimination calls.
- Stopping-time results: The LIL stopping criterion substantially affects regular lil’UCB but has no observed impact on the lil’UCB Heuristic variant.The heuristic performs exceptionally well in the experiments despite lacking the theoretical guarantee supplied by the theorem’s parameter conditions.
- lil’UCB: lil’UCB samples the arm with the largest upper confidence bound and stops when one arm has received more than a constant fraction of all samples.Its confidence bounds incorporate LIL scaling, and the next-arm decision can be maintained in O(log(n)) time using ordered data structures.
- Anytime performance: Anytime error curves reveal larger differences than stopping-time plots, with UCB algorithms collecting sufficient information to output the best arm more reliably.The anytime evaluation outputs the arm with the highest empirical mean at every time and plots its error probability against total pulls.
A Condensed Proof of Lower Bound
The lower-bound argument uses sequential testing and the LIL to show that thresholds growing too slowly yield error probability 1/2. Consequently, reliable identification requires an expected sample scale containing a log log term.
- Sample-complexity consequence: Any test with worst-case error below 1/2 must satisfy E[T]∆^2 log log(∆^-2) > 0 as ∆ approaches zero.This establishes the necessity of a log log factor in the expected sample complexity for distinguishing two close Gaussian means.
- Sequential testing: The proof studies a generalized sequential probability ratio test that compares a running empirical mean with nondecreasing thresholds.The test continues sampling while the relevant running sum remains within the threshold boundaries.
- LIL threshold necessity: Thresholds asymptotically no larger than the LIL boundary make the test’s worst-case error probability equal to 1/2.The argument uses the LIL and continuity in the mean parameter; a zero-mean random walk eventually reaches either boundary, with each side crossed first with probability one half.