Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: In this work the authors present an algorithm for the stochastic multi-armed bandits setting where it is known a priori that arms come in group of size at least q, all having the same mean. A lower bound on the regret is given, as well as an asymptotically order-optimal achievability scheme.
main_review: 1. The motivation provided for this problem is relatively weak. The primary example the authors use to motivate this setting involves arms with differing values across several categorical attributes (some of which are redundant), which has significantly more structure than just groups of arms with the same means. This is more reminiscent of Factored Bandits [Zimmert and Seldin, NeurIPS 2018], which the authors should discuss and compare against.
2. Lack of clarity in simulations; in the paper there are several errors regarding simulations, e.g. for Figure 1 it claims 3 sets of means but lists a set of 4. Similarly in Figures 10,16,17,18,19 it is claimed that there are 4 classes, but 7 means are given. More importantly however, the authors poorly document their simulations, so it is unclear from the paper the true impact of the robustness of the algorithm to the parameter q. For example, it is only given for Fig 3 that there are 7 classes with given means, with an uneven number of Gaussian distributions in each class ranging from 4 to 23. It is not given which class has which size, let alone the total number of arms. For example, if the best class was the one with cardinality 4, this would seem to be a harder problem instance for the algorithm than if the class with cardinality 4 constituted the worst class. As such, the reproducibility and significance of Figure 3 are unclear. Critically, one of the two uses of q is constructing A_*(t), and so the relevant test regarding the robustness of the algorithm to q would seem to be when A_*(t) is impacted, yielding fewer than q optimal arms (which would appear to lead to linear regret, as suboptimal arms are included in A_*(t) ).
3. The lower bound appears to be novel, but the algorithm itself seems to be only a minor modification of the original IMED.
4. There does not appear to be any characterization or bounding of alpha or f in Theorem 2 in the main text. While the empirical performance of this algorithm seems promising, a discussion on alpha and f and the possibility for finite sample guarantees would strengthen this paper.

Minor comments:
- There were many typos and grammatical issues in this paper, which detract from the overall work. Some are listed below 
- Title should not have a period at the end
- Line 40 that we assume ‘is’ unknown to the learner
- Lines 55/56 arms should be plural
- line 127 ‘makes appear’
- line 135 duplicated text
- Line 138 “2 time from” -> a factor of 2
- Line 146 have->has
- Line 210 summation should start from time index 1, and t is overloaded as both the time index and the dummy variable in the sum
- line 266 annex->appendix
- Line 272 duplicated compare
- line 448 Monotony of the KL -> monotonicity

**After Rebuttal:**
The authors clarified some helpful points in the rebuttal:

Experiments: Including all relevant experimental details in the Appendix would help contextualize the simulations; a reader should not need to look at the raw code in order to understand the details of the experiments. 

Robustness: Thank you for clarifying $A_{*}(t)$. However, it is still unclear to me if Figure 3 shows robustness of this scheme with respect to q. From my understanding looking at the experiments, the authors simply vary the number of arms in a suboptimal class, where the interesting experiment to run would be seeing how the algorithm performs if there are fewer than q optimal arms (to which Figure 15 offers some partial insight). 

$\alpha$ and $f$: Bounds and / or considerable discussion on these factors would greatly strengthen this work, as these quantities appear in the primary Theorem of this paper. If it is too difficult to provide these in general, specializing to Gaussian or Bernoulli instances would still be extremely helpful, to give a sense of how these quantities can be expected to scale. It was difficult for me to follow the appendix references as the analysis is not very self contained, and it is not clear why $f$ in particular goes to 0 in the limit.

This paper has its upsides, i.e. the problem is fundamental (equivalence classes of means) even if the motivating example is not well thought out, and the technical contributions (primarily the lower bound) are interesting and novel. However, the additional discussion does not change my score; the vague experiments and general lack of care taken with the writing are concerning. To address these issues, the authors will have to go through and correct the individual points we have listed, and all the others we did not. In its current form the presentation is poor so I cannot recommend acceptance. However, I will not object to acceptance either, so I retain my score of 5.
limitations_and_societal_impact: There are no negative societal impacts in this theoretical paper that focuses on regret minimization in the stochastic multi-armed bandit setting.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers a new variant of the classic stochastic bandit problem, analysing the complexity of the problem and proposing an effective algorithm. The new problem matches the classic problem definition of the K-armed bandit, except all arms are grouped into classes with identical distributions. Each class contains at least q arms, and the decision-maker is assumed to know q a priori but not the classes. A motivating scenario where this may arise is one where arms have multiple categorical features but certain features are uniformly redundant in the sense that the reward distributions do not vary with respect to these features. The decision-maker would in such a setting know (a lower bound upon) the number of redundant features but not which features are redundant (and as such which arms are equivalent). 

The authors derive an asymptotic lower bound on the number of plays of suboptimal arms, and then propose an algorithm based on the IMED indices of Honda and Takemura (2015). The regret of this algorithm is shown to coincide with the lower bound in certain settings -  where classes are equally sized (roughly speaking) – and differ from the lower bound by no more than a constant factor in other settings. The algorithm is shown to outperform non-bespoke approaches which treat are unaware of the arm class structure, and have some robustness to misspecification of q.

main_review: The paper is generally of a high quality. The theoretical underpinnings are strong, the authors write mostly very well, and the solution to the problem is appropriate and builds nicely on existing work. I have two main issues with the presentation of the material – firstly that the more theoretical aspects could be explained more clearly in the main text (see section ‘Clarity’) and secondly that the motivation for considering the problem could be more detailed and have a potential issue resolved (see section ‘Significance’). I am impressed by the work and would be happy for the paper to be accepted as is, but could also give a yet higher score and feel the paper would be genuinely improved is these issues were addressed.

ORIGINALITY AND QUALITY: My view is that the paper clears the acceptance bar in this regard. The problem is interesting and the work on it is new, accurate as far as I can tell (I have not been able to thoroughly inspect the appendices in the time-limited reviewing window) – certainly the main results make sense and have required some effort to derive. The performance of the algorithm is impressive and the algorithm is simple to implement and computationally efficient. 

CLARITY: I really enjoyed the introductory section of the paper. The writing is excellent – the authors successfully adopt a blend of conciseness, clarity, and accuracy that explains core concepts quickly but accessibly. This is genuinely some of the best scene-setting I have seen in a bandit theory paper while reviewing at ML conferences. In Section 2, I feel there is something of a departure from this style as the mathematical material becomes more complex. I feel that this is not necessary. There is room within the page limit to guide the reader with more context and intuition here. The definitions and assumptions, and indeed Theorems/Lemmas to some extent, are presented without much linking text or context. The intuitions behind the lower bounds are complex but not (I feel) unaccessible to the unfamiliar reader, and as such I feel more could be done to explain the various steps here. As examples, I would explain to the reader the role of the ‘confusing instances’ (to find the exploration needed in the most challenging cases), give more intuition as to where the various terms in Theorem 1 arise from, percolate the discussion of non-combinatorial and combinatorial regimes with plain text explanations of the concepts (e.g. ‘an instance where all groups of similar of arms are of the same size’), and being more clear in the first instance what the remainder of the section aims to do to improve upon the insight given by Theorem 1. An explanation of how such improvements could be made via the rebuttal would lead me to increase my score.

SIGNIFICANCE: The problem is interesting theoretically, and I could imagine the paper laying the foundation for the study of more complex variants (contextual, combinatorial, non-stationary etc.) which may have genuine applications. The mention of categorical features suggests a setting in which this problem would genuinely arise, however the motivation in this regard is scant. I accept that this predominantly a ‘theory paper’ but I do think the paper could be improved with a more convincing argument as to the motivating applications of the work. If they are genuine – why not explain/cite in more detail? Further, why is it preferable to approach this redundant categorical feature problem via the  approach in this paper over a more structured model selection-type approach where we can use the information that arms which correspond to matching levels of more categorical features are more likely to be part of the same class? I would like to see the motivation for the work addressed in more detail via the rebuttal.

Finally, some minor typographical errors as follows: in line 114, should be ‘authors’ not ‘author’ in line 126, should be ‘paper’ not ‘papers’, in Thm 1, should be ‘suboptimal arms’ not ‘suboptimal arm’ there are further similar issues around pluralisation throughout the remainder - in line 179, should be ‘times’ not ‘time’ in line 180 the l in ‘Lemma 1’ should be capitalised, in line 281, should be ‘imperfect’ not ‘unperfect’. [NB, I have not considered these minor typos in assigning my review score]. 

limitations_and_societal_impact: They have adequately addressed limitations
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper extends the study of multi-armed bandits to the case where there are groups of arms having the same distribution (in the exponential family), and a lower bound $q$ on the size of these groups is known to the learner. The authors introduce a new parametric asymptotic lower bound for this setting. They build on the IMED strategy from Honda and Takemura to propose an adapted strategy. This new strategy has a regret that is at worst 2 times the asymptotic lower bound, and q-times smaller than the regret of an unstructured bandit instance having the same number of arms.
main_review: ## Originality / Significance
 The authors consider a setting where there are groups of arms having the same distribution and a lower bound $q$ on the size of these groups is known to the learner. They justify the interest of this setting by an example of problem where each arm can be described with a list of categorical attributes, and the reward function only depends on a subset of them. This is an original problem, that has not yet been studied, as I understand. The lower bound is original and even though the algorithm heavily resembles another algorithm( IMED from Honda and Takemura), the algorithm is efficient and the upper bound is technically involved. 

However, a first question arises regarding the interest and significance of this setting. I would like to understand from the authors what are the practical cases where the learner knows a lower bound on the size of the groups but does not know at least a subset of the features that are redundant and hence the groups? The authors attempt to explain it line 62, but do not succeed in making it clear, in my opinion.
 
## Clarity/ Soundness
The paper lacks precision on multiple occasions, which harms its clarity but also makes the reader doubt its soundness :
- In Theorem 1, should $\lambda$ be replaced with $\mu^*$? Otherwise, how is it defined? (same for l.174 and equation 6)
- Why does $|c_q|\geq 2q$ belong to the non-combinatorial regime? There is absolutely no explanation for this fact.
- The paragraph starting in l186 and explaining the difficulties with the combinatorial regime is not clear. Can the authors reformulate the paragraph?
- In Theorem 3, is the liminf a limsup? A liminf would not be satisfactory.

## Minor flaws 
- In the proof of Theorem 1, the use of the Fano inequality should be explicit, even if it is classic.
- Also, the authors should explain how they swap the liminf and the min , line 493.
- The fact that the distributions are parametrized by their means because of assumption 2 should be explained earlier than on page 4.  Otherwise, the equivalence classes based on the means only seem strange.

## Typos 
- l45 : we study/studies
- l114 : The authors show
- l170: combinatorial
- l175: amounts
- l178: assumption
- l179: times
- l221: makes
- l246: assumptions
- l252: a striking result 




limitations_and_societal_impact: I am satisfied with the way the authors addressed the limitations of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies a version of the stochastic multi-armed bandit problem where arm-means have a multiplicity of at least $q$, meaning, for any given arm "a," there exist at least $q-1$ other (distinct) arms with a mean reward same as that of "a." The parameter $q$ is assumed known. The reward distributions are assumed to belong to a one-dimensional exponential family. Under this premise, the authors show refined lower bounds for the expected sampling times of inferior arms (also regret) that exhibit a $q^{-1}$-scaling. Additionally, leveraging the underlying problem structure, a refinement of the KL-divergence-based terms appearing in the lower bound is also shown. The authors propose a modification of the IMED algorithm that suffers a regret within a multiplicative "control" factor of the lower bound. All in all, the takeaway is that the achievable regret is reduced by a factor of $q$. The reported numerical experiments indicate robustness to misspecification of $q$. 
main_review: UPDATE: 
I thank the authors for their response; I have revised my rating to 6 since the authors could satisfactorily answer several of my questions. However, in light of the issues raised by the other reviewers, I am also minded to reduce my confidence score to 3.

------------------------------------------------------------------------------------------- 


The model and results certainly seem interesting. Since multiplicity of arm-means is a key feature, a brief survey of extant works that have considered such models will only make the literature review more comprehensive. Recent papers that come to mind are https://arxiv.org/pdf/2105.10721.pdf and https://arxiv.org/pdf/2103.12452.pdf (check references for related works). Cited papers assume $q=\infty$, basically meaning that the arms are sampled from an infinite "reservoir." However, the reservoir is assumed to hold a fixed (positive) fraction of "optimal" arms which are "well-separated" in the mean-reward from other sub-optimal types. Despite an infinity of arms in said problem, the papers show that logarithmic regret is still achievable. It would be interesting to see how the finite-armed model with a multiplicity of arm-means studied in this paper relates to its infinite-armed counterpart from cited works, achievability of logarithmic regret surprisingly being the unifying thread. 

limitations_and_societal_impact: Unfortunately, the paper appears to have overloaded notation with plenty of typos and notational inconsistencies, which make it hard to parse. It could seriously benefit from a revision along these lines. Typos (not a comprehensive list) and some general remarks are noted below:

1. Line 51: I suggest you use a different notation for $\mathcal{B}_q(\mu)$, it gets really confusing later on when you overload it further.

2. Lines 134-137: Please rephrase.

3. Line 151: The mapping $\mu^\prime$ is not defined before. Also, I believe there is scope for making the definition of "confusing" instance, less-confusing (no pun intended).

4. Lines 158-163: Please decide upon a stable convention for KL divergences. As in, KL$(.,.)$ vs. KL$(.||.)$. Similarly for $\mathcal{K}_{eq}$.

5. Theorem 1 second line: A should be $\mathcal{A}$, equivalence class in $\nu$ (not $\mu$). 

6. Line 165: What is a "bandit dependent lower bound?"

7. In equation (2), the $\nu_a$'s should be $\mu_a$'s (there are other instances too, not noted here). The $\mu$ below the "inf" should be $\nu$. Also, how is $\lambda$ specified?

8. It would greatly help the reader if you could provide intuition on the combinatorial vs. non-combinatorial regimes in terms of the $q,2q$ business.

9. Equation (5): $\nu_a$ should be $\mu_a$ and a possible summation missing?

10. Equation (6): Extraneous log term and unspecified $\lambda$.

11. Line 210: Typo in the range of summation. Also, the $X_{t}'s$ haven't been defined before.

12. Just below line 214: It should be $\mathcal{A}_{\ast}(t)$ below "min."

13. Please mention the acronym IMED-EC next to Algorithm 1.

14. Line 221: *makes.

Some of these issues recur subsequently too, I am not mentioning them again. Overall, I like the punchline of the paper -- a factor $q$ reduction in achievable regret if arm-means have $q$-multiplicities. But the paper needs a clean-up. I am open to increasing my score if aforementioned points are satisfactorily addressed.
review_title: null

Meta-review: The committee was divided about this paper: while the technical value is recognized by all and praised by one reviewer, it seems like at least two reviewers were puzzled by the clarity of the paper. I decided to read the draft myself to make my own opinion on whether the pass needed was minor (and does not require another cycle of review) or major. I think it is rather the former situation, though I see how a few typos at the wrong places may have mislead reader. Please update your work for the final version, removing typos and adding comments on motivation as well as citations to further highlight the connection with existing work and the potential impact of your discoveries. 
Decision: Accept (Poster)