Near Optimal Best Arm Identification for Clustered Bandits

Knowledge of $\eta$: We run additional experiments to validate the robustness of our schemes. Please refer to our rebuttal of Reviewer UFPL.

Different bandit instances have Different best arms: Our objective is to find the best arm for every agent, and so it seems reasonable to define the clustering based on best arms. Naturally, we put all the agents in a cluster who possess the same best arm. Furthermore, we are able to at least identify a few real-life datasets where these assumptions do hold.

**$\eta-free algorithm:** We can remove the knowledge of$\eta$from our learning algorithms completely. We can propose a multi-phase algorithm where we start with a large enough value of$\eta$, and at the beginning of each phase, we reduce it by a factor of 2. After some phases, the value of$\eta$ falls below the actual separation and the algorithms start learning the best arm. If we select exponentially increasing phase length, we can show this multi-phase algorithm will succeed in finding the best arms of all the agents. Rigorously proving the correctness is part of our future plans.

Cl-BAI vs Naive in real data: As explained in the same paragraph (line 234-248), Cl-BAI will out-perform the naive algorithm if the `separability' parameter $\eta$ is much bigger than the bandit sub-optimality (arm) gaps $\bar{\Delta}$; {in particular when $\eta \gg \bar{\Delta}$}. While this is the case in synthetic datasets, for the real datasets we chose, it turns out (based on our sub-sampling of data) that the bandit arm gaps are comparable to the cluster separation (e.g for Yelp, $\eta=0.375$ and $\bar{\Delta} = 0.25$) , and hence the sample complexities are comparable.

Results for non-uniform clusters: We invoke the results of coupon collector problem with unequal probabilities $p_1,\ldots,p_M$, where $p_i$ is proportional to size of cluster $i$. From [1], the term $\mathcal{O}(M\log M/\delta)$ in Theorem 5.3 will be replaced with the following term: $\mathcal{O}[\int_0^\infty [1- \prod_{i=1}^M (1-e^{-p_it})] dt]\log(1/\delta).$

Novelty and reliance on SE Our goal is to perform both clustering and best arm identification jointly, and SE is a common tool to help in both the jobs. We believe the novelty of this work lies in utilizing SE for both clustering and best arm identification judiciously in a sample efficient manner. We choose to run SE with different combinations of the subset of arms, success probability and number of rounds to reduce the sample complexity which is highly non-trivial. The easy tunability of SE allows us do do this and obtain near optimal performance. To the best of our knowledge, this is not done in the literature yet.

This work may be viewed as the first step towards understanding parameter-free clustering in the Federated setup with the objective of finding best arms for all the agents (not appropriately defined Global best arm).

Knowledge of $M$: The number of clusters $M$ is not needed to be known for Cl-BAI, where the clusters are created based on a nearest-neighbor graph type construction. For BAI-Cl and BAI-Cl++, knowledge of $M$ is needed since the first phase corresponds to recovering the set of all possible best arms using random sampling. Here, we do not require the exact value, any upper bound will suffice with a small increase in sample complexity.

Technical Contribution:  (i) Successive Elimination (SE):  We believe the contribution of this work lies in utilizing and tuning SE for both clustering and best arm identification judiciously in a sample efficient manner which is highly non-trivial. As a result, we obtain near optimal performance in terms of sample complexity. Even though this seems apparently simple, to the best of our knowledge, this is currently absent from the literature.

(ii) Coupon Collector: We use ideas from the Coupon Collector problem to improve the sample complexity of our proposed algorithm, $BAI-Cl$. Using this with SE, we find at least one agent from each cluster with a set of active arms containing the best arms from all $M$ clusters. In the subsequent phase, we let the rest of the agents play only from the obtained subset. Since the cardinality of this set can be much smaller than the total number of arms, we get an improved sample complexity, which is near optimal.

(iii) Lower Bound We also use instance perturbation based technique to obtain lower bounds on the expected sample complexity. We obtain both instance dependent as well as instance independent bounds. The lower bound we obtain (nearly) matches the sample complexity of our proposed algorithm rendering them near optimal. Such a lower bound is also novel for this multi agent best arm identification problem.

(iv) Experiments We run experiments on real datasets, Yelp and Movielens dataset.

Reference [1]  "Birthday paradox, coupon collectors, caching algorithms and self-organizing search", Philippe et.al, Discrete Applied Math, 1992.

Current state-of-the-art algorithm for Best Arm Identification (BAI): We choose Successive Elimination (SE) over other state of the art algorithms like Track And Stop (TAS) or Lower Upper Confidence bound (LUCB) for a number of reasons:

(i) We aim to address the problem of Clustering and BAI jointly, and SE is a common tool to address both of these problems. In other words, SE could seamlessly be adapted to our problem formulation. The same thing can not be said for TAS and LUCB.

(ii) For TAS, in general asymptotic guarantees are known, where as we require sharp non-asymptotic guarantees for proving correctness of our proposed algorithms. Some non-asymptotic guarantees of LUCB is known, however they are not immediately adaptable to our problem formulation. Moreover, SE has $3$ tuning parameters, namely the subset of arms, success probability and the number of rounds. Overall, SE is easier to tune compared to other best arm identification algorithms like TAS.

(iii) We would like to clarify that the order-wise performance (sample complexity) of both SE and TAS are similar, whereas SE may have sub-optimal constants. In this work, we provide guarantees on order-wise sample complexity and hence TAS and SE would yield similar results.

(iv) In terms of experiments, one can use other BAI algorithms. However, TAS is computation heavy as compared to SE. Hence, we have taken SE as a default choice.

Typos and Related work We apologize for the typos. We have corrected them in the modified version. We have also added a few relevant and recent papers in the Related Work section and provided comparisons with them.

The paper lacks a discussion/conclusion section Thank you for the suggestion. Indeed, we have added a Conclusion section now. Additionally we have corrected the typos, actively worked on the writing, and re-organized a few section (including appendix) to improve readability.

Why optimal TAS is not used? Although we have discussed this in the first question, we summarize the comparison with TAS here:

(i) Note that for TAS, in general asymptotic guarantees are known, where as we require sharp non-asymptotic guarantees for proving correctness of our proposed algorithms. Moreover, SE has $3$ tuning parameters, namely the subset of arms, success probability and the number of rounds. Overall, SE is easier to tune compared to other best arm identification algorithms like TAS.

(ii) We would like to clarify that the order-wise performance (sample complexity) of both SE and TAS are similar, whereas SE may have sub-optimal constants. In this work, we provide guarantees on order-wise sample complexity and hence TAS and SE would yield similar results.

(iii) We aim to address the problem of Clustering and Best Arm Identification (BAI) jointly, and SE is a common tool to address both of these problems. In other words, SE could seamlessly be adapted to our problem formulation. The same thing can not be said for TAS.

(iv) Finally, in experiments, one can use other Best arm Identification algorithm like TAS. Hoever, TAS is computation heavy compared to SE. Hence, we have taken SE as a default choice.

Other relevant algorithms and comparison There are a lot of works in bandit clustering albeit in a parametric setting. In other words, for linear bandits and contextual bandits (which are parameterized), one can naturally define a clustering based on the underlying unknown parameters. On the other hand, needless to say that there is a rich literature on the Best Arm Identification (BAI) problem without clustering structure. However, we are not aware of any other papers in the intersection of non-parametric bandit clustering and BAI, where our work lies.

Alternatively, there are a few works on the BAI problem for Federated Bandits. Out of these, we consider [1]. Note that if we remove the notion of Global best arm from [1] and only focus on recovering Local best arms, the proposed algorithm there reduces to the naive algorithm we compare against since they do not consider any underlying clustering among agents. We would like to point out that, since we are interested in the BAI for all the agents, naturally the notion of Global best arm makes little sense in our setup.

Reference: [1] Almost Cost-Free Communication in Federated Best Arm Identification; Kota Srinivas Reddy, P. N. Karthik, and Vincent Y. F. Tan; AAAI 2023.

Additional references We thank the reviewer for these pointers. As suggested by the reviewer, we will aim to do a more extensive review of the related literature on clustering in bandits. We would like to point out that one key difference between most of the literature there (including the papers pointed out above) and our work is in how the clusters are defined. While the literature mainly considers parameterized settings such as linear / contextual bandits where the clusters are based on the unknown user preference vectors, our setting is non-parameterized and the cluster definition is based on the mean reward vectors.

Assumptions 2.1 and 6.1 Thank you for raising this point. Note that our objective is to find the best arm for every agent in the system, and so it seems reasonable to define the clustering based on the best arms. Assumptions 2.1 and 6.1 essentially quantify a separability condition amongst clusters, based on how the best arm of a given cluster performs in other clusters. These assumptions allow us to provide analytical guarantees on the performance of our proposed algorithms; furthermore, as part of our numerical evaluation, we are able to at least identify a few real-life datasets where these assumptions do hold and our proposed schemes are able to provide significant savings in terms of sample complexity and communication cost.

Having said that, there might be other definitions of separability which might also be suited to our setup. However, we choose this since it aligns well with our overall objective of best arm identification.

Knowledge of $\eta$ The reviewer's point is well-taken. Our response to this is two-fold:

1. Robustness to $\eta$: We have run additional experiments to illustrate that our algorithms are robust to the choice of $\eta$. For the Movielens and the Yelp datasets, we run our algorithms assuming different values of $\eta$ and have tabulated the results below. Each experiment is repeated 10 times.

We have the following observations on the impact of $\eta$-misspecification on correctness and sample complexity. Firstly, as expected, when the assumed $\eta$ is smaller than the true value, the algorithm recovers the best arms correctly. Surprisingly, the same in fact holds true even with larger values of $\eta$ which illustrates that our algorithms are in fact quite robust to the choice of $\eta$. Again, as expected, the incurred sample complexity grows as the gap between the assumed $\eta$ and the true value increases, and there are errors in recovery when $\eta$ is chosen too large.

Movielens: $M= 6, N = 120, K = 316 , \eta_{true} = 0.0027$

Yelp: $M= 4, N = 80, K = 211 , \eta_{true} = 0.375$

2. $\eta$ free algorithm: Alternatively, we can remove the knowledge of $\eta$ from our learning algorithms completely. We can propose a multi-phase algorithm where we start with a large enough value of $\eta$, and at the beginning of each phase, we halve $\eta$. After some phases, the value of $\eta$ falls below the actual gap and the algorithms start learning the best arm. If we select exponentially increasing phase length, we can show this multi-phase algorithm will succeed in finding the best arms of all the agents. Rigorously proving the correctness is part of our future plans.

Nearest neighbor and pairwise distance: The claim being discussed here considers the `bad' event that two agents belonging to the same cluster get assigned to different clusters, i.e., there exists an arm in the union of the active sets of these two agents, whose estimated means for agents $i$ and $j$ differ by more than $\eta/2$. Our claim is a high probability result and it implies that while the bad event (including for example the specific case that the reviewer has mentioned) can happen, it will occur with very small probability because the underlying ground truth dictates that for any $i,j,k$ which are in the same cluster, their true mean reward vectors will all be identical and thus, when the SE procedure (as prescribed by our algorithm) is run by each of them in the first (clustering) phase, it is very unlikely that the mean reward estimates will be significantly far apart. The claim essentially provides an upper bound on the probability that the bad event occurs.

Number of independent runs 50

Writing, Typos, Figures We apologize. We have actively worked on the writing in the revised draft and also improved the figures.

Knowledge of $M$: The number of clusters $M$ is not needed to be known for Cl-BAI, where the clusters are created based on a nearest-neighbor graph type construction. For BAI-Cl and BAI-Cl++, knowledge of $M$ (or an upper bound) is needed since the first phase corresponds to recovering the set of all possible best arms.

Communication cost: We believe there is a tradeoff between the sample complexity and the communication cost; we see some evidence of this in our analysis. Any algorithm will incur at least $N\cdot \log M \cdot c_b$ communication cost since the learner has to infer each agent's cluster membership. However, we believe this to be weak and identifying the optimal tradeoff is of interest. We have included a more thorough discussion on this.

Random selection in Algo 1: The agent is selected arbitrarily from each cluster. We have clarified this in the revised manuscript.

SE is easy-to-tune: We say this because SE provides a general procedure which can be altered using three `knobs': the subset of arms, the target error probability, and the number of rounds. We use different combinations of these parameters in different schemes (as well as stages of the same scheme) to achieve various guarantees on surviving arms, their confidence interval sizes etc.

Robustness with respect to $\eta$: The reviewer is correct in stating that if $\eta' \leq \eta$, our sample complexity results hold with $\eta$ replaced by $\eta'$. We have run additional experiments to validate the robustness of our schemes with respect to $\eta$. Please see the response for Reviewer UFPL.

Parameter-free algorithm We can remove the knowledge of $\eta$ from our learning algorithms completely. We can propose a multi-phase algorithm where we start with a large enough value of $\eta$, and at the beginning of each phase, we halve $\eta$. After some phases, the value of $\eta$ falls below the actual gap and the algorithms start learning the best arm. If we select exponentially increasing phase length, we can show this multi-phase algorithm will succeed in finding the best arms of all the agents. Rigorously proving the correctness is part of our future plans.

Yun $\&$ Proutiere, 16 Yun and Proutiere consider cluster recovery in the Stochastic Block Model, where the feedback structure (edge label) is quite different to our setting. However, we do agree that some similar spectral decomposition based method might be feasible for our setting as well.

Performance gap between Cl-BAI and BAI-Cl Cl-BAI clusters the users in the first phase and then employs one agent from each cluster to identify the corresponding best arms. However all $K$ arms remain active throughout, including the first phase where all the agents participate. On the other hand, in Cl-BAI, the first phase reduces the active set of arms from $K$ to only $M$ using participation from only $O(M\log M)$ agents and this provides a great reduction in the sample complexity.

Expected sample complexity Similar to several works of best arm identification (BAI) in multi-armed bandits, our upper bounds (achievability) are stated as high-probability results whereas the lower bounds are in expectation. However, there are works available in the literature which prove expected sample complexity upper bounds for BAI. For example, Kalyanakrishnan et. al. (2012) for the LUCB scheme and Even-Dar et. al. (2006) for SE style schemes. We believe that similar ideas can potentially be used to derive expected sample complexity bounds for our schemes as well.

References

1. S. Kalyanakrishnan et. al., PAC subset selection in stochastic multi-armed bandits, ICML 2012.
2. E. Even-Dar et. al., Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems, JMLR 2006.