Abstract
In fixed-budget bandit identification, an algorithm sequentially observes samples from several distributions until a predetermined deadline, at which point it must identify a specific property of the distributions (e.g., the best arm). While the probability of error decreases exponentially with the budget, the optimal decay rate has remained largely unknown. This research demonstrates that if a fixed-budget task admits a "complexity"—a lower bound on the error probability attained by a single algorithm across all problem instances—that complexity is necessarily determined by the optimal non-adaptive sampling procedure. Furthermore, the paper proves that for many common tasks, including two-arm Bernoulli best arm identification, no such universal complexity exists. This implies that no single algorithm can be optimal across all possible scenarios within these frameworks.
Introduction
In the study of multi-armed bandits, "complexity" refers to a fundamental measure that quantifies the difficulty of a problem and guides the design of optimal algorithms. In the "fixed-confidence" setting, where an algorithm stops as soon as it reaches a target certainty, complexity is well-defined, and strategies like "Track-and-Stop" achieve the theoretical limit.
However, the "fixed-budget" setting—where the sample size is fixed and the goal is to minimize the probability of error—has proven more elusive. Researchers have long sought a "master algorithm" for fixed budgets that could match the efficiency of fixed-confidence counterparts. This paper by Rémy Degenne, presented at COLT 2023, provides a definitive theoretical answer: for many fundamental identification tasks, a universal complexity simply does not exist.
The Fixed-Budget Challenge
Consider a clinical trial or an A/B test with a strict limit of $T$ samples. This is a fixed-budget bandit identification task. Unlike regret minimization, where the goal is to maximize cumulative rewards, the objective here is purely to identify the correct answer (e.g., which treatment is superior) with the highest possible probability after the budget is exhausted.
The paper investigates whether there exists an algorithm that attains the best possible error rate for every instance of a problem. If such an algorithm existed, we could define the "complexity" of the task. Degenne’s work focuses on one-parameter exponential families, such as Gaussian and Bernoulli distributions, to test this hypothesis.
Methodology: The Difficulty Ratio
To evaluate the performance of algorithms, the author introduces the difficulty ratio ($R_{H,T}$). This metric compares the error probability of a given algorithm against a theoretical "oracle" baseline—the best possible static, non-adaptive sampling strategy for a specific problem instance.
- $R_{H,T} = 1$: The algorithm matches the performance of the best static strategy designed specifically for that instance.
- $R_{H,T} > 1$: The algorithm is performing worse than the problem-specific optimal strategy.
Using change-of-measure arguments and Kullback-Leibler (KL) divergence, the author constructs "alternative" bandit problems that are statistically close to the original but require different answers. This allows for the derivation of fundamental limits on how well any algorithm can distinguish between these instances within the fixed budget.
Key Insights
1. The Primacy of Static Sampling
The paper proves that if a universal complexity were to exist for a fixed-budget task, it would be determined by the best non-adaptive sampling procedure. This is a surprising result, as it suggests that in the search for a universal algorithm, adaptivity (changing strategy based on observed data) cannot provide a better rate than the best fixed allocation of samples.
2. The Absence of a Master Algorithm
For the classic task of Best Arm Identification (BAI) with two Bernoulli arms, the paper proves that the difficulty ratio is strictly greater than 1 (approximately 1.22). This means that for any algorithm one might design, there is at least one pair of Bernoulli arms for which the algorithm will be at least 22% less efficient than the optimal strategy for that specific pair. Consequently, no single algorithm can be optimal everywhere in the Bernoulli BAI space.
3. Scaling with Problem Size
In Gaussian bandits, the findings are even more pronounced. Theorems 7 and 8 show that the maximal difficulty ratio grows with the number of arms ($K$), specifically proportional to $\log K$. As the problem complexity increases, the gap between any universal algorithm and the instance-specific optimal strategy widens significantly.
4. The Positivity Task
In the "Positivity" task—determining if the means of all arms are above a certain threshold—the paper finds that while uniform sampling is the best possible universal strategy, it remains $K$ times worse than an oracle that knows which specific arm is most likely to violate the threshold.
Conclusion and Future Directions
This research provides a "negative" result that reshapes the field of bandit theory. By proving the non-existence of a universal complexity for many fixed-budget tasks, it suggests that the search for a single "best" algorithm is, in many cases, futile.
This shift in understanding opens several new avenues for research:
- Minimax Optimality: If no algorithm is perfect everywhere, how do we design algorithms that minimize the maximum possible error across the entire problem space?
- Thresholding Bandits: The existence of complexity for tasks like "is the mean above $X$?" remains an open question.
- Small $K$ Conjectures: While the gap is proven for large $K$ in Gaussian settings, the author conjectures that the same lack of complexity holds for small $K > 2$.
Ultimately, the work suggests that in the fixed-budget regime, the benefits of adaptivity are fundamentally limited by the geometry of the problem space, forcing a trade-over between performance on different problem instances.
Summary updated