Summary
The paper investigates the problem of fixed-confidence BAI in stochastic multi-armed bandits. Simply stated, the problem entails finding the best arm (the arm with the largest mean reward) as quickly as possible, subject to an upper bound on the error probability. There exist a plethora fo works that investigate this problem, derive problem instance-dependent lower bounds on the asymptotic growth rate of the expected stopping time, and devise algorithms that achieve the asymptotic lower bound; here, the asymptotics is one of vanishing error probabilities. One class of efficiently implementable algorithms for this problem that has gained significant attention in the recent years is that of top-2 sampling algorithms. The basic premise on which such algorithms function is to pull the empirical best arm at any given time with a certain constant probability, say $\beta$, and to pull the empirically second-best arm (or the challenger arm) with the remaining probability. Despite its elegance and ease of implementability, the aforementioned $\beta$-top-2 sampling algorithm an algorithm falls short of achieving the instance-dependent lower bound. The key to achieving the lower bound, as it turns out, is to set $\beta=\beta^*$, where $\beta^*$ depends on the underlying problem instance and is therefore unknown to the algorithm. While several attempts to learn the value of $\beta^*$ as part of the algorithm have taken place in the recent past, the current work accomplishes the same objective elegantly, using the theory of ODEs. Notably, the paper proposes an algorithm for BAI, and analyses the fluid dynamics (ODE) corresponding to a continuous version of the same. Implicit function theorem is used to demonstrate the existence and uniqueness of the solutions to the ODE, and to further demonstrate that the arm allocations under the algorithm closely follows the trajectory coming from the ODE. It is then argued that the limiting solution of the ODE (and hence the asymptotic arm allocations under the algorithm) matches with the optimum allocations corresponding to the underlying instance, thereby proving the asymptotic optimality of the proposed algorithm.
Strengths
The use of the theory of ODEs and the implicit function theorem to demonstrate the asymptotic optimality of the proposed algorithm is the novel aspect of this paper. To the best of my knowledge, such an approach to the demonstration of asymptotic optimality does not exist in the literature on fixed-confidence BAI. Furthermore, while the concept of *anchor function* appearing in the paper has its roots in Garivier and Kaufmann's paper on BAI, a careful analysis of its behaviour using the theory of ODE to demonstrate asymptotic optimality of the proposed algorithm is impressive.
(I must acknowledge, though, that I was unable to go through the extensive and detailed appendix due to paucity of time.)
Weaknesses
The writing of the paper can be slightly improved. While the authors have done a commendable job in explaining the intuition behind their detailed proofs, I have some minor suggestions that might possibly improve the readability of the paper.
1. In the paragraphs leading up to Proposition 2.1, the authors introduce the notation $x\_{1,a}=\dfrac{\omega\_1 \ x\_1 + \omega\_a \ x\_a}{\omega\_1 + \omega\_a}$. Shortly thereafter, the authors use the phrase "define $N\_{1,1}$ as the value of $N\_1$ at which $\sum\_{a \neq 1} \dfrac{d(\mu\_1, x\_{1,a})}{d(\mu\_1, x\_{1,a})}=1$ for a given allocation $\boldsymbol{N}\_{\bar{B}^c}$", without stating the (new) definition of $x\_{1,a}$. The actual definition of $x\_{1,a}$ only appears later, in the first part of Proposition 2.1. I suggest that the authors move the definition of $x\_{1,a}$ to an earlier paragraph if possible.
Some minor comments:
2. "alocation" in line 160 --> "allocation".
3. $f(\boldsymbol{\mu}, a, N)$ in line 291 --> $f(\boldsymbol{\mu}, a, \boldsymbol{N})$.
Questions
Can the authors explain what role the anchor function $g$ plays at a higher level. It seems almost unintuitive that this function, together with the empirical means and allocations, should dictate the sampling of the best empirical arm or challenger arm at any given time (items 3,4 in lines 208-211), in order to match with the optimal allocations in the long run. For a contextual comparison, in the TCB and ITCB algorithms of [21], the place of the anchor function is taken by the empirical problem complexity. Given that the empirical terms are expected to be close to their true values in the long run, the empirical problem complexity is likely to be close to the true complexity. It is then intuitive to expect that any sampling rule that is based on the empirical problem complexity, is likely to lead to sampling the arms according to the optimal allocation in the long run.
Along these/similar lines, can the authors provide a high-level intuition for why looking at the anchor function and its long-term behaviour is pivotally connected to learning the optimal $\beta$ and thereby matching the arm selection frequencies with the optimal allocation?