TL;DR
This paper tackles the Best-Arm Identification (BAI) problem in Gaussian multi-armed bandits when both means and variances are unknown. The authors introduce two algorithmic wrappers—one using empirical variance plug-ins and another adapting transportation costs—backed by novel time-uniform concentration inequalities. Crucially, they prove that not knowing the variances incurs only a minimal penalty on sample complexity, providing the first asymptotically optimal algorithms for this realistic setting.
What Problem Does This Paper Address?
In multi-armed bandit problems, Best-Arm Identification (BAI) focuses on pure exploration: an agent samples different options ("arms") to identify the one with the highest expected reward as quickly and accurately as possible. In the fixed-confidence setting, the agent must guarantee that the probability of making a mistake is below a user-defined threshold $\delta$.
While BAI is well-understood when rewards follow a Gaussian distribution with known variances, real-world applications—such as A/B testing for website layouts or adaptive clinical trials—rarely provide variance information upfront. Assuming known variance is a major limitation. When variances are unknown, the problem becomes significantly harder because the algorithm must estimate both the mean and the variance of each arm simultaneously. This requires data-dependent stopping thresholds calibrated by sophisticated, time-uniform concentration inequalities to prevent the algorithm from stopping too early and making an error.
Methods
The authors propose two distinct approaches to handle unknown variances, creating "wrappers" that can adapt existing BAI algorithms designed for known variances:
- Empirical Variance Plug-in (EV-GLR): A intuitive approach that takes standard algorithms assuming known variance and simply plugs in the running empirical variance ($\sigma^2_{t,a}$).
- Adapted Transportation Costs (GLR): A mathematically rigorous approach that directly accounts for unknown variances within a Generalized Likelihood Ratio (GLR) framework.
To ensure these algorithms are $\delta$-correct (i.e., they fail less than $\delta$ fraction of the time), the authors derive four new families of time-uniform concentration thresholds for Gaussian distributions with unknown variances:
- Student thresholds: Derived from Student-t distribution quantiles (simple but loose).
- Box thresholds: Derived by bounding the mean and variance independently.
- KL thresholds: Derived by jointly bounding the Kullback-Leibler (KL) divergence using a "peeling" method over exponential families.
- BoB (Best of Both) thresholds: An optimized threshold that combines the tight asymptotic properties of the KL threshold with the small-sample efficiency of the Box threshold using non-linear solvers.
The authors instantiate these wrappers on two popular sequential sampling strategies: Track-and-Stop (TaS) and the Top Two algorithm $\beta$-EB-TCI.
Datasets
The paper evaluates the proposed methods using synthetic simulations (a standard practice for theoretical bandit research):
- Random Instances: 1,000 randomized environments with $K = 10$ arms. The optimal arm is fixed with a mean of 0 and variance of 1. The sub-optimal arms have means ($\mu_a$) and variances ($\sigma_a^2$) drawn uniformly from $U[-1.0, -0.2]$ and $U[0.1, 10]$, respectively.
- Specific Regimes: They isolate a "standard instance" (where the complexity ratio between unknown and known variance settings is close to 1) and an "easy instance" (where the ratio is around 1.384) to evaluate how the algorithms scale.
Key Insights and Ideas
- The Price of Ignorance is Small: By extending the sample complexity lower bounds to a two-parameter setting, the authors prove that the statistical penalty for not knowing the variance is bounded and surprisingly small.
- Closest Alternatives Have Higher Variance: A key mathematical insight from the transportation cost analysis shows that when variances are unknown, the "closest confusing alternative" hypothesis to the true best arm naturally possesses an increased variance.
- Theory vs. Practice Disconnect: Theoretically, adapting the transportation costs (GLR) yields stronger guarantees, providing the first asymptotically optimal algorithms for unknown variances. However, empirically, the simpler empirical variance plug-in (EV-GLR) performs almost identically, making it a highly viable heuristic in practice.
Key Results
- Asymptotic Optimality: The authors prove mathematically that combining the GLR stopping rule with tight thresholds (like KL or BoB) allows Track-and-Stop to match the theoretical lower bound for sample complexity as $\delta \to 0$.
- Empirical Efficiency: In simulations with $K=10$ and $\delta=0.01$, both the EV and GLR wrappers significantly outperformed uniform sampling and performed on par with an "oracle" baseline that knows the true parameters perfectly.
- Threshold Trade-offs: The BoB threshold proved to be the tightest in terms of sample size but comes at a high computational cost (400–800x slower than simpler thresholds). The authors suggest a "lazy" evaluation grid to mitigate this in practice.
Limitations and Future Work
- Fixed-Budget Setting: This work is strictly situated within the fixed-confidence framework. Characterizing the exact impact of unknown variances under a fixed-budget constraint (where the number of samples is fixed, and you minimize error probability) remains an open problem.
- Extension to Sub-Gaussian Distributions: The concentration proofs rely heavily on the independence of the empirical mean and empirical variance, a property unique to Gaussian distributions. Extending these tight bounds to general sub-Gaussian distributions with unknown variance proxies is a steep theoretical challenge.
Summary updated