Fixed Confidence Best Arm Identification in the Bayesian Setting

We thank the reviewer for the valuable review and comments. The following are the responses to the questions you raised.

Q1) better upper bound using lil-UCB

We assume your question refers to the improvement of the confidence bound from $\sqrt{\log(N_i(t)/\delta)/N_i(t)}$ to $\sqrt{\log(\log(N_i(t))/\delta)/N_i(t)}$. It is challenging to verify all parts of the proof during this short rebuttal period, but we conjecture this can improve the dependency on $\log(L(H))$ but would not change the dependency with respect to $\log(1/\delta)$. Since this is the first paper on the fixed-confidence Bayesian best arm identification, we consider the current analysis to have enough novelty.

Q2) extending the distribution of the arms is more general, like subgaussian, or non-parametric?

Many results in our paper, such as Lemma 1 (Volume lemma), Lemmas 11, 13~17, and Theorem 18 hold also in non-Gaussian settings. However, several results such as Lemmas 12 and 17 are tailored for the Gaussian setting and we cannot extend those results easily to other environments. Therefore, our lower and upper bound results need some additional work to extend to other settings. As we mentioned in Section 7, extending the current results to more diverse environments is one of the interesting future research topics.

Q3, Q4) modify other algorithms, such as top-two, track-and-stop, LUCB or lil-UCB to make it better in the Bayesian setting

As we have mentioned in our future work section (Section 7), it is another interesting research topic. We chose the Elimination algorithm since it is easier to manage the number of suboptimal arm pulls. Elimination also attains an orderwise optimal ratio in a frequentist setting, so we believe that using TT, T&S, LUCB or lil-UCB won't make an orderwise improvement, especially with respect to $\delta$.

Q5) a high probability bound instead of an expectation bound on the sample complexity?

In the Bayesian setting in general, there is no natural idea of a high-probability bound, since the bandit instance $\mu$ is also another random variable. For example, in many FC-BAI studies in a frequentist setting, they propose the high-probability bounds of the stopping time as the form of '$\tau \leq f(\mu)$ with probability $1-\delta$'. It is reasonable in a frequentist setting since $\mu$ is a fixed instance in their setting. However, in our case, $\mu$ is also a random variable, so it means now the bold inequality compares two random variables. We thought that whether such results could be accepted as high-probability bounds might be controversial depending on the reader. Therefore, we presented expectation bounds.

In the case of the high-probability bound when the bandit instance $\mu$ is fixed, it is relatively trivial. Our Lemma 17 can be seen as the high probability bound for each arm when $\mu$ is given, and from this result we computed the overall expectation, which was computationally challenging (about 5 pages of integral computations).

W3) The lower bound proof (and possibly the upper bound proof) uses standard techniques from the literature.

Our lower bound proof is novel and we suggest the first framework to prove Bayesian FC-BAI lower bound. Our proof structure is significantly different from the standard technique in the Frequentist FC-BAI lower bound, such as Kaufmann et al., (2016).

The main differences come from the different definitions of the error probability (PoE) between the frequentist setting and the Bayesian setting. As mentioned in Lines 178-179, Bayesian $\delta$-correctness is more lenient than the frequentist $\delta$-correctness. This means we need to consider more diverse algorithms for the lower bound since the lower bound is for all possible $\delta$-correct algorithms. We want to mention three challenges in our proof.

• First, in our case, we suggest a novel interpretation of PoE to an optimization problem (Opt0 -> Opt1, given the upper bound of the stopping time, how small the error probability can be?)

• Second, we propose a relaxation (Opt1 -> Opt2), which changes the optimization parameter from algorithms to the positive real functions $\tilde{n}: \mathbb{R}^2 \to [0,\infty)$.

• Lastly, we found out that the main problem happens in the 'instances with small suboptimality gaps' and made a novel modification (Opt2 -> Opt3), and use Jensen's inequality in a creative way (Claim 1 in Appendix D) to achieve a computable optimal answer.

There are also other minor novel techniques, such as extension of the [Lemma 1, Kaufmann et al., 2016] (Lemma 11 in our paper) which helped us to transform the little-kl divergence to easier notation.

W5) The simulations are limited to just two sets of experiments. The baselines or compared algorithms are just 2/1 in the respective setting. And it might be better to include different values since the authors consider the fixed confidence setting and change priors as well.

We made a brief comparison between Algorithm 1 and TTUCB in $K=10$ arm environment with different prior means, prior variances and instance variances. (because of the time constraint, it was not easy to finish TTTS at the same time.) Details of experiments are in the next comment.

After 500 simulations, the expected stopping time of our algorithm was $1.1\times 10^5$, while TTUCB attains $7.1\times 10^5$. Even after giving an advantage to TTUCB, our algorithm shows a much smaller sample complexity than TTUCB.

To avoid possible confusion, allow us to clarify our experiment result again. In Table 1, the compared algorithms have 10 times larger expected stopping time than ours, and about 500 times larger maximum stopping time.

We thank the reviewer for the careful reading of the paper and the insightful comments. In the following, we address the question raised.

The definition of ${\mathcal{H}}_{\mu}$ at the beginning of page 4 may not be precise...is it an event or a $\sigma$-algebra? In the former case, with continuous Gaussian priors, it is not clear if the event has a non-zero probability, which makes all the conditional probabilities technically dubious. Please clarify.

We are using the law of total expectation $\mathbb{E} [X] = \mathbb{E} [\mathbb{E} [X|\sigma(Y)]] = \mathbb{E} [g(Y)]$ where $\sigma(Y)$ is the sigma algebra generated by random variable $Y$ and $g(y) = \mathbb{E} [X|Y=y]$. This argument holds even when {Y=y} has zero probability. See for example

1. Example 4.1.6 in 'Durrett, Rick. Probability: theory and examples. Vol. 49. Cambridge University Press, 2019'
2. Example 4 in https://www.stat.cmu.edu/~arinaldo/Teaching/36752/S18/Notes/lec_notes_6.pdf
3. https://math.stackexchange.com/questions/1332879/conditional-probability-combining-discrete-and-continous-random-variables

In particular, in our case $Y$ is $\mu$ and we are computing $\mathbb{E}\_{\mu_0 \sim \mathcal{H}} [\mathbb{P}(J\neq i^*(\mu)|\mu=\mu_0)]$. In this sense, $\mathcal{H}_{\mu_0} = \{\mu = \mu_0\}$ is an event. In the Bayesian setting, $\mu$ is a random variable, and we wanted to express the probability of error (PoE) as the form of the law of the total expectation, to emphasize that our probability of error is the marginalized form of the PoE. We used the notation $\mathcal{H}\_{\mu}$ to simplify notation.

We thank the reviewer for the careful reading of the paper and the insightful comments. We will revise the typos and references in our final version. In the following, we address the main questions raised.

W2) The authors do not discuss how they derived the constant L(H) and its significance. Since this constant represents sampling complexity and is not a traditional term, it is harder to compare the complexity to existing work.

From Section 3, we find that measuring the probability when $\mu$ achieves a small suboptimality gap is crucial. The constant $L(H)$ represents the ratio between the gap $\Delta$ and the probability that $\mu$ achieves a suboptimality gap smaller than $\Delta$, as outlined in Lemma 1. We will include a discussion on this in our final version.

Q1) 267-268: In Remark 3, can the authors explain if in the general case, the result matches with the lower bound?

Our lower bound holds only when $\delta$ is sufficiently small, whereas the result in Remark 3 (upper bound) is the case of moderately large $\delta$, so we cannot say the result matches with the lower bound.

Q2) 309-313: The authors state that the expected stopping time of the track-and-stop method is at least half of the TTTS and TTUCB methods, which according to Table 1, is on average at least 300. This number is less than that for Algorithm 1, so can the authors explain why they didn’t compare?

To avoid possible confusion, allow us to clarify our experiment result again. In Table 1 of the paper we submitted, our algorithm has a stopping time of $10^4$, TTUCB has a stopping time of $1.5\times 10^5$, and TTTS has an even higher stopping time. Even if the stopping time of Track-and-Stop is half that of TTUCB, it would be $7.6\times 10^4$, which is still over 7 times larger than our algorithm.

W4) 196: The derivation of the inequalities in Section 3.1 is not clear.

We will add more explanation on Section 3.1 in our final version. Corollary 3 implies that for any fixed mean vector $\mu \in \mathbb{R}^2$, the stopping time is lower bounded by $\log (1/\delta)/(\mu_1 -\mu_2)^2$. For the following sequence of equations (equation in line 196~197),

$\mathbb{E}\_{\mu \sim H} [\tau] \geq \mathbb{E}\_{\mu \sim H} [\tau \cdot \mathbb{1}[|\mu_1 -\mu_2| \leq \epsilon]] \geq \frac{\log \delta^{-1}}{\epsilon^2} \mathbb{P}\_{\mu \sim H} [|\mu_1- \mu_2| \leq \epsilon] = \Omega(\frac{\log \delta^{-1}}{\epsilon})$

1. The first inequality holds since $\tau$ is a positive random variable.
2. The second inequality holds by the following

• law of total expectation $\mathbb{E}\_{\mu \sim H} [\tau \cdot \mathbb{1}[|\mu_1 -\mu_2| \leq \epsilon]] = \mathbb{E}\_{\mu \sim H} [\mathbb{E}[\tau |\mu] \cdot \mathbb{1}[|\mu_1 -\mu_2| \leq \epsilon]]$
• and Corollary 3 $\mathbb{E}\_{\mu \sim H} [\mathbb{E}[\tau|\mu] \cdot \mathbb{1}[|\mu_1 -\mu_2| \leq \epsilon]] \geq \mathbb{E}\_{\mu \sim H} [\frac{\log \delta^{-1}}{(\mu_1 - \mu_2)^2} \cdot \mathbb{1}[|\mu_1 -\mu_2| \leq \epsilon]]\geq \frac{\log \delta^{-1}}{\epsilon^2} \mathbb{P}\_{\mu \sim H} [|\mu_1- \mu_2| \leq \epsilon]$

3. Finally, by Lemma 1, we can replace $\mathbb{P}(\cdots)$ as $L(H)\cdot \epsilon$ which leads the RHS.

W5) 242-243: In Chapter 5, there is no explanation for why this particular confidence width was considered.

The bound is for assuring $LCB(i,t) \leq \mu_i \leq UCB(i,t)$ for all $t\in \mathbb{N}$ and $i\in[k]$ with high probability. For more details, please check Lemma 15 (Appendix E). In our final version, we will add more explanation about the proof in Section 5.

W6) In Chapter 6, there is no discussion on why Algorithm 1 shows higher error percentages than the other two algorithms.

When our algorithm finds the suboptimality gap is too narrow, instead of trying to identify the best arm, our algorithm stops sampling to avoid excessive sample complexity. On the other hand, the other two algorithms always keep sampling until they identify the best arm. This difference causes the error rate difference. However, as we have mentioned in Section 3, the algorithm should set an indifference condition in the Bayesian setting or the algorithm will attain an excessive scale of sample complexity, even diverging to infinity in expectation.

We are truly grateful for the encouraging evaluation and valuable comments. The following is the response to the question you raised.

In Thm 4, the constants in the lower bound seem very small ($\frac{1}{16e^4}\approx 2^{-8}$), so it could entail a trivial lower bound in most cases, especially since it is the lower bound to the sample complexity (natural number). What is the actual value of this lower bound in some of your example simulations?

We agree that our lower bound tends to be much smaller than actual values. For example, when $\delta=0.01$, for the instance in our Example 1 ($\mu=(1,0.9,0.1)$), the sample complexity lower bound is 0.0468, smaller than 1. However, the main objective of our lower bound is to check the order of the sample complexity. Through this analysis, we found out that L(H) is a crucial variable in designing the algorithm, and we were able to propose our Algorithm 1 which is optimal up to a logarithmic factor.