Fixed Confidence Best Arm Identification in the Bayesian Setting

Summary

This paper considers the best arm identification (BAI) problem in the fixed confidence setting and in the Bayesian setting, where the mean rewards of each arm is drawn from a known prior distribution. The authors formulate the problem and discuss the related literature. The authors provide the lower bound of the expected sample complexity of finding the optimal arm, which is proportional $L(\mathbb{H})/\delta$ where $L(\mathbb{H})$ is defined by the authors to characterize the sample complexity. Then the authors show the current optimal algorithms in the frequentist setting: the top two and tack-and-stop algorithms are suboptimal in the Bayesian setting. The authors then propose a new algorithm based on the successive elimination algorithm in the frequentist setting, showing that this algorithm reaches the optimal sample complexity up to a logarithmic factor. The authors provide the upper bound of the algorithm on the expected sample complexity. Finally the authors run two simulations to show that the top-two algorithm is indeed suboptimal comparing with Algorithm 1, and also show the superior performance of algorithm1 compared to the no-elimination version of it.

Strengths

1. The problem is clearly defined and the paper is nicely presented. 2. It is nice to show that the optimal algorithms (top-two and tack-and-stop) are suboptimal in the Bayesian setting 3. The authors illustrate the theorems and proofs using a simpler 2-arm version which can be better understood.

Weaknesses

1. The assumption of the arms may be stringent, i.e. all arms are from the Gaussian distribution. The current literature considers many more general distributions, such as sub-gaussian, exponential family, or even non-parametric cases. 2. The confidence interval is not optimized to the tightest confidence interval which is suggested in the lil-UCB paper from Jamieson: "lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits" 3. The lower bound proof (and possibly the upper bound proof) uses standard techniques from the literature. Perhaps the authors could point out the difficulty or challenge in the proofs. 4. The upper bound is not optimal compared to the lower bound, with an extra logarithmic factor. Is it possible to reduce this gap using tighter confidence bound or do some modification to the algorithm, such as modification of top-two or tack-and-stop instead of modify the SE algorithm (which is not optimal in the frequentist setting) 5. 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 $\delta$ values since the authors consider the fixed confidence setting and change priors as well.

Questions

1. Is it possible to use tighter confidence intervals to get a better upper bound? 2. Is it trivial or direct to consider similar algorithms when the distribution of the arms is more general, like subgaussian, or non-parametric? 3. Is it possible to modify top-two or tack-and-stop to make it better in the Bayesian setting? 4. Just out of curiosity, is it possible to modify LUCB or lil-UCB to this setting so that it achieves similar performance when the authors modify the successive elimination algorithm? Since the former two algorithms have better sample complexity in the frequentist setting. 5. Can the upper bound be modified to a high probability bound instead of an expectation bound on the sample complexity? Would it be challenging or trivial?

Rating

5

Confidence

3

Soundness

3

Presentation

4

Contribution

2

Limitations

See weaknesses and questions.

Summary

This paper considers a best arm identification problem in Bayesian multi-armed bandit setting. The arms' distributions are generated according to the unknown prior, and the probability of error is averaged over this prior distribution. The paper makes two key contributions: first, a lower bound characterizing the fundamental hardness of BAI in the Bayesian setting (where the L(H) parameter is identified as playing a key role), and second, and achievability part that proposes a successive elimination-based algorithm (with early stopping in case the arm instance has very close best arms). The algorithm achieves within a logarithmic factor of the lower bound.

Strengths

The paper brings out an interesting twist on BAI, where the Bayesian setting is statistically easier on "an average" compared to the frequentist setting. The paper explains the intuition clearly throughout, and is executed competently.

Weaknesses

There is no glaring weakness. It appears to be obvious in hindsight that "very close" instances do not occur with substantial probability, when we have a Gaussian prior, making the hard frequentist instances statistically irrelevant in the Bayesian setting. This makes the BAI problem easier in terms of the expected stopping time. If the prior model creates close instances with non-vanishing probability, I suppose we'd be back to the frequentist performance.

Questions

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 non-zero probability, which makes all the conditional probabilities technically dubious. Please clarify.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Limitations are acknowledged in the conclusions reasonably.

Summary

In this paper, the focus is on the fixed-confidence best-arm identification problem within a Bayesian setting. The objective is to determine the arm with the largest mean with a certain confidence, given a known prior distribution. Existing work in FC-BAI is mostly in the frequentist setting. This paper shows that the popular algorithms used in the frequentist setting are not optimal in this setting. Additionally, a lower bound for this setting is derived, using a sampling complexity constant and the confidence level. Lastly, a successive elimination method that matches the order of the derived lower bound along with experiments comparing the performance of popular frequentist algorithms and this algorithm are presented.

Strengths

- The authors show that popular frequentist algorithms are suboptimal in the Bayesian setting. - The paper presents a novel algorithm, which is significant because, according to related work, it is uncommon to have a stopping time in Bayesian optimization. - In the successive elimination method, the indifference zone is not a parameter. - The derived lower bound is novel.

Weaknesses

1. 47: Example 1 lacks proof or reference for the number of samples. 2. 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. 3. 171: In Chapter 3, the authors claim there is a known lower bound for the expected stopping time without providing any reference. 4. 196: The derivation of the inequalities in Section 3.1 is not clear. 5. 242-243: In Chapter 5, there is no explanation for why this particular confidence width was considered. 6. In Chapter 6, there is no discussion on why Algorithm 1 shows higher error percentages than the other two algorithms. 7. 313: there are two dots instead of one.

Questions

- 267-268: In Remark 3, can the authors explain if in the general case the result matches with the lower bound? - 309-313: The authors state that the expected stopping time of the track-and-stop method is at least half of the TTS 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?

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

The research was done only for the Gaussian distribution.

Summary

The paper studies the problem of FC-BAI; the goal is to find the arm with largest mean with a given probability of correctness. It analyzes FC-BAI for a Gaussian bandit model where the arms reward mean is sampled from a known prior and the reward variances are known. It proves other (frequentist) FC-BAI algorithms could fail at this setting. Then it proves a lower bound for the sample complexity of this problem. Finally, an elimination algorithm is introduced which is near-optimal. The main difference of this algorithm with previous algorithms is in its less conservative stopping criteria, where it stops if the remaining arms have small enough optimality gap.

Strengths

*Soundness*: the paper clearly defines the problem, introduces a lower bound for the problem, theoretically proves the sub-optimality of previous algorithms, and conducts simulation studies along with ablation experiment. *Presentation*: The paper provides all the proof sketches and pseudo-codes required for reproducibility of the results. It efficiently uses its notation and avoids overloading symbols.

Weaknesses

*Contribution*: The paper considers a small subset of bandit models, Gaussian reward with know prior and variance. This limits applicability of the algorithm and theoretical results. As also mentioned in the discussion section, it would be great if they could generalize the algorithm to deal with misspecified or under-specified prior (see [1]), or unknown variance. [1] Azizi, J., Kveton, B., Ghavamzadeh, M. and Katariya, S. 2023. Meta-Learning for Simple Regret Minimization. Proceedings of the AAAI Conference on Artificial Intelligence. 37, 6 (Jun. 2023), 6709-6717. DOI:https://doi.org/10.1609/aaai.v37i6.25823.

Questions

1. In Thm 4, the constants in the lower bound seem very small ($\frac{1}{16 e^4} \approx \frac{1}{2^8}$), so it could entail a trivial lower bound in most cases, specially 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?

Rating

7

Confidence

5

Soundness

4

Presentation

4

Contribution

3

Limitations

Yes.

Details on experiment (W5)

**Experiment Setting** - Number of arms $k=10$ - Prior means: we sample 10 random numbers before the experiment starts, and set them as prior means. Here's the list of prior means: [-0.053 0.528 -0.332 -0.368 -0.273 0.909 0.418 -1.17 0.873 -0.405] - Prior variance: we sample 10 random numbers before the experiment starts, and set them as prior means. Here's the list of prior std: [0.604 1.477 1.163 0.988 0.560 0.513 0.997 1.332 0.828 0.833] - Instance variance: we sample 10 random numbers before the experiment starts, and set them as prior means. Here's the list of instance std: [1.498, 1.262, 1.485, 0.963, 1.375, 0.969, 1.357, 1.238, 1.088, 0.699] - Number of experiments: 500 - We stop additional sampling of TTUCB when its number of samples is over $10^8$ because of the time constraint. This means we gave some 'advantage' on TTUCB about expected stopping time (since it makes TTUCB stop earlier than it should.)