We thank the reviewer for their insightful comments. We provide below detailed replies.

Questions for authors

1. Our analysis and experiments consider overlapping tasks [for “overlap”, we mean the bandits may have the same, or similar, reward distribution for some of the arms/contexts. If the reviewer was thinking of a different kind of overlap, we kindly ask them to please elaborate more on this]. The parameter $\lambda$ controls the degree to which at least one arm distribution does not overlap in any pair of bandits. Since the algorithm uses $\lambda$ to make the tests statistically robust, it suffers from the same misclassification rate with any $\lambda$, whereas the regret degrades as $O(\lambda^{-2})$ (see Theorem 3.1, 4.4)
2. Note that we also consider a setting where tasks are not known to the algorithm, which estimates them through samples (Section 4.1). The reviewer is right that the set of tasks is fixed in the paper: We do not provide results for generalization to tasks that are not seen in training. Arguably, generalization depends on “how” the test tasks differ from the training tasks. We conjecture that similar results could be obtained for the lenient regret (see https://arxiv.org/abs/2008.03959) when the test task is an $\epsilon$-perturbation of a training task. For more general discrepancies between training and test, the algorithm shall be re-designed to allow for additional test-time exploration, which is a nice direction for future works.
3. We proved that $C_{\lambda} (\mathbb{M})$ captures the complexity of an instance of our setting with both a lower bound (Theorem 3.3) and an upper bound (Theorem 3.1). This implies that $C_{\lambda} (\mathbb{M})$ is as good as any other complexity measure for this specific setting: Finite collection of separated bandits. For the latter setting, there might be other complexity measures that are equally good (we are not aware of). In other settings, there might be better complexity measures.

Lower bound

We actually provide a lower bound where a factor $C_\lambda (\mathbb{M})$ appears explicitly (see Theorem 3.3 and discussion thereafter). We thank the reviewer for making us realize that the lower bound is not highlighted enough. We will make this result more central in the updated manuscript.

Ablation study on the effect of separability

Reviewer is mentioning a few times that an analysis of the effect of $\lambda$ on empirical results is missing. We hear their concern: We will report in the Appendix more results for different $\lambda$ values. What we noticed from our experiments is the same effect that one can see by squinting at Figure 4 (a, b). In 4a, $\lambda$ is 0.4 and the elbow in the DT-ECE is very sharp. In 4b, $\lambda$ is 0.04 and the elbow is a lot smoother. With smaller $\lambda$ it takes more time to traverse the tree, both because each test requires more samples and the tree might be deeper.

Experimental design

We agree that experiments on real-world data better supports real-world applicability. We will add to the manuscript an experiment on movie recommendations with the MovieLens dataset (https://grouplens.org/datasets/movielens/), on the same line of the MovieLens experiment in Hong et al 2020a (see response to R. 1Rko "experimental design").

Other weaknesses:

“ECE relies on decision trees for classification, which may not scale well in high-dimensional settings or when task distributions are complex” We recall that the regret of ECE is not affected by the dimensionality of the problem (see Theorem 3.1). However, we believe the Reviewer means something else here: The additional complexity of computing and storing the decision tree. The computational complexity is polynomial in both $d$ (dimensionality) and $M$ (size of the set of tasks), where the factors of $d$ disappear when the tasks are known. The space complexity is $M 2^{C^* (\mathbb{M})} \leq M 2^M$, which may become intractable for a large set of tasks. In those cases, the tree can be traversed online without pre-computing it (like in Algorithm 1) with negligible additional space complexity. We will add space complexity and considerations on balancing interpretability and memory requirements in the updated manuscript.

Intuitive explanation of coefficient $C_\lambda (\mathbb{M})$:

We thank the reviewer for pointing out that the definition of the classification coefficient is difficult to understand. See the comment for all the reviewers in the response to Reviewer HVdH for an intuitive explanation.

Insufficient experimental visualizations:

Following the Reviewer’s suggestion, we will add visualizations of the decision trees learned by our algorithm in the Appendix. As an example, we provide the one for Figure 4a at https://anonymous.4open.science/r/anon_icml_rebuttal-90C9/empirical_tree.pdf. Especially, note the short depth of the tree even for a hard instance that maximizes $C_\lambda (\mathbb{M}) = M$.

We are glad to hear that the reviewer appreciated our work. We thank them for their thoughtful comments, useful suggestions, and for pointing out typos. We will make use of them to improve the manuscript. We address their questions below.

Value of $N_{cls}$ in the experiments

We used $N_{cls} = C / \lambda^2$ in all the experiments, where $C$ is a constant. We set $C = 4$ after trying $C = 2, 4, 8, 16$ (results are not particularly sensitive to this value). Moreover, we implemented an adaptive sampling strategy that checks the confidence of the test at each sample, so that the sampling ends whenever the desired confidence is reached or $N_{cls}$ samples have been taken. The adaptive sampling also didn’t affect results substantially, but it makes the algorithm slightly more efficient in some settings. We thank the reviewer for pointing out that this information is missing in the text. We will add a specific section with experimental details to the Appendix.

Other comments:

• Why is $C (M) < C^* (M)$ in (5)? Thank you for the opportunity to clarify. First, we provide below an detailed explanation of $C (M)$, which can help to understand the proof. Proof: This is a standard argument in decision trees that $C(M)$ is a lower bound to $C^* (M)$. Consider any subset of hypotheses $S$, and when starting from this subset, let the maximum number of hypotheses that we can rule out each round is at most $N$. Then, the depth of any deterministic decision trees with the subset $S$ must be at least $S/N$. Since $C^* (M)$ is the depth of deterministic trees for a larger set of hypothesis, $S/N < C^*(M)$. This holds for all subsets of $M$, hence $C(M) < C^*(M)$. Following reviewer’s suggestion, we will add this sketch of the proof of eq. 5 in the Appendix.
• In Section 3.1 it would improve clarity to explain that the non-optimal arms are such that for $i \neq j$ for which $\mu_i (a) = (1 + \lambda) / 2$ and $\mu_j (a) = (1 - \lambda) / 2$ (I assume this is true based on the rest of the section, but it is not explicitly stated.) The reviewer is right! This is implied by the separation assumption (Asm. 1) but we agree with the reviewer it is very implicit. We will explicitly mention this in the text.

For all the Reviewers

Intuitive explanation of $C_\lambda (\mathbb{M})$

Based on all the reviews, we understand that our exposition of $C_{\lambda} (M)$ could be improved with more intuition. We want to provide an intuitive explanation of its meaning here. We hope that the additional clarity will make the reviewers better appreciate this important contribution.

Informally, the value of $C_\lambda (\mathbb{M})$ measures how much information we gain from a single split of the worst-case node of the decision tree (small value means more information). To see this, let us look at the math:

$C_\lambda (\mathbb{M}) := \max_{S \in 2^{[M]}} \min_{\pi \in [K]} \max_{i \in S} \frac{|S|}{|S_{\lambda}^\pi (i)|}$ Let us unpack each term. $S$ is a set of candidate bandits and $i$ stands for the true bandit within $S$. $\pi$ is an arm we test on the true bandit. $S_{\lambda}^\pi$ is the subset of $S$ that we can eliminate from the set of candidates by pulling $\pi$ enough. Thus, the ratio $|S| / |S_{\lambda}^\pi|$ measures the amount of information we can gain from this split. In the extreme cases: We eliminate a single bandit from $S$, so that $C_{\lambda} (\mathbb{M}) = M$ is large (little information gained) We eliminate half of the bandits in $S$ and $C_{\lambda} (\mathbb{M}) = M / (M/2) = 2$ is small (a lot of information gained). Note that we cannot reduce $C_{\lambda} (\mathbb{M})$ by eliminating more than half of the candidates, as $i$ is chosen worst-case to select the largest set after the split.

We will add this intuitive explanation together with extreme cases and visualizations in the updated manuscript.

We want to thank the reviewer for their feedback. We are replying to their comments below.

Claims and evidence

Interpretability is a crucial motivation of our paper and we want to make sure we are on the same page with the reviewer on this. Especially:

• Interpretability of bandit algorithms: Translating a notion from supervised learning to the bandit setting, we say that exploration is interpretable if it can be represented through a decision tree with small depth (see Bressan et al. 2024 https://proceedings.mlr.press/v247/bressan24a Def. 2). Our work is the first to establish bounds on the depth of the decision tree for exploration (Lemma 4.3)
• UCB and TS are interpretable: UCB and TS may also be represented through a decision tree, but its depth can be as large as the number of rounds. According to this notion UCB and TS are not interpretable. See an example of how our algorithm builds a compact decision tree (https://anonymous.4open.science/r/anon_icml_rebuttal-90C9/empirical_tree.pdf from the experiment of Figure 4a) whereas an analogous tree for UCB or TS exploration is too large to be visualized

Methods and evaluation criteria

Great point! Storing the full decision tree requires additional $M 2^{C^* (\mathbb{M})} \leq M 2^M$ space in the worst-case, which may be impractical in applications where the number of tasks $M$ is huge. In those cases, the tree can be traversed online without pre-computing it (like in Algorithm 1) with negligible additional space complexity. We will add space complexity and considerations on balancing interpretability and memory requirements in the updated manuscript.

Theoretical claims

“Each bandit might be at a different stage of convergence” we are not sure we understand the reviewer’s concern here. Note that we interact with only one bandit at test time. Moreover, stationarity is orthogonal to whether the reward distributions are stochastic or adversarial. We target the stationary stochastic setting, just like in the previous literature of latent bandits (with the exception of Hong et al 2020b), aiming for fast and interpretable exploration. This makes the approach more practical (than previous works) in some applications, e.g., the candidate bandits represent user “types” in a recommendation system: It is often reasonable to assume that a user doesn’t change “type” during the interaction. We agree with the Reviewer that some other applications are inherently non-stationary and extending our results is a non-trivial direction for future works.

Experimental design

While we developed a method intended for practical settings, we remark that the core contribution of the paper is conceptual. However, to support practicality of our method, we will add an additional experiment in which we compute the decision tree on the MovieLens dataset (https://grouplens.org/datasets/movielens/), similarly to Hong et al 2020a (see their Sec 5.2). Users are first clustered into types, based on historical data. Then, the decision tree that we learn essentially prescribes what movies to recommend in order to classify the type of an unknown user, to then maximize their reward by providing recommendations specialized for the classified type.

• Super-parameters are fixed. We considered different values for the separation parameter, number of arms and bandits. Is there any other parameter the reviewer would like to see explored?
• Baselines. The aim of the experiments is not to outperform any prior bandit algorithm, as our is the first method that is interpretable (in the sense above) and thus competes in a different field. If the reviewer thinks there is a baseline that is relevant to the latter field, we will be happy to include a comparison.

Essential references

Thanks for pointing out additional relevant work. We will be happy to include them in the paper with appropriate discussion. Qi et al and Xie et al are interesting but tackle orthogonal problems. S&D 2021 meta learn exploration for contextual bandits, which is similar in nature to our setting. Their algorithm, MELEE, trains exploration by imitating an expert (optimal exploration) in simulation. There are crucial differences:

• We do not assume access to an expert during training, but only to simulators
• MELEE is not interpretable according to our notion (see above), as we cannot bound the depth of a decision tree representing its policy
• MELEE’s regret goes to zero asymptotically, but the regret rate is implicit in their result

Other weaknesses

Thanks for letting us know that the symbols are sometimes hard to grasp. We will make a careful revision of all the symbols and to convey enough intuition. See the comment for all the reviewers in the response to Reviewer HVdH for an intuitive explanation of the coefficient $C_{\lambda} (M)$.