Dealing with Unknown Variances in Best-Arm Identification
This work addresses a practical gap in bandit algorithms for applications where variances are unknown, though it is incremental as it builds on existing methods.
The paper tackles the problem of best-arm identification with Gaussian rewards when variances are unknown, introducing two approaches using empirical variance or adapted transportation costs, and shows that the impact of unknown variances on sample complexity is small.
The problem of identifying the best arm among a collection of items having Gaussian rewards distribution is well understood when the variances are known. Despite its practical relevance for many applications, few works studied it for unknown variances. In this paper we introduce and analyze two approaches to deal with unknown variances, either by plugging in the empirical variance or by adapting the transportation costs. In order to calibrate our two stopping rules, we derive new time-uniform concentration inequalities, which are of independent interest. Then, we illustrate the theoretical and empirical performances of our two sampling rule wrappers on Track-and-Stop and on a Top Two algorithm. Moreover, by quantifying the impact on the sample complexity of not knowing the variances, we reveal that it is rather small.