Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: Paper consider a/b/n testing into a bandit problem. Paper raised a framework and give an algorithm which reaches the complexity lower bound. Paper provided simulations showing advantages of the proposed algorithm.
main_review: (not an expert in the area so will provide general reviews. please refer to other reviewers on evaluation on the tech details)
Paper provided a solution to the A/B/n testing problem which is very useful in the industry data analysis
- Paper constructed a complexity bound and provided algorithm reaching it, constructing an optimal framework
- Simulation showing superior performance
- Various parameter models are analysed and they are widely applicable to the real setups

However the paper is hard to follow, especially since there is no illustrations of algorithm/ toy example for problem setup to understand the math setup, etc. The presentation is a bit packed (might because of the page limit). It might be good to focus on a sub-problem, such as most profitable arm identification / AB testing with 2 subpopulations and present the general setup results as an extension.
limitations_and_societal_impact: No. Theoretical work so the potential societal impact is limited. Potentially will have applications on social network data, etc. So might be good to mention this.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: In this paper, the authors develop and analyze several variants of a bandits algorithm that takes into account possible different subpopulations, and employs an adaptive stopping time.
main_review: In this paper, the authors develop and analyze several variants of a bandits algorithm that takes into account possible different subpopulations, and employs an adaptive stopping time.
The paper derives theoretical results on the sample complexity of the proposed procedure, along with a valid "risk assessment" strategy.

Overall, the paper is clearly written and well motivated. There are some deficiencies, which may be more generally related to the background literature rather than the particular paper --- I would appreciate the authors' feedback on that. Specifically:

* It seems too restrictive to assume the same model for all different subpopulations. Is this common in the literature?

* Moreover, it seems very restrictive to assume the same one-parameter exponential family model. 
  (a) Why only one parameter ? (What about the case of normal with mean \mu_{a, i} and variance \sigma^2_{a, i} as in Prop 2? Do we assume known variances here?
   (b) Why exponential family? It is clear that this introduces several simplifications as the log-likelihood is linear in the parameter, but this is not discussed in the paper. What specific structure do we need from the exponential family? How plausible is this for real-world applications? 

* What does kl(p, q) look like? It would help to have an idea about how this depends on, say, |p-q|.

* Prop 2 was useful. Is it obvious how to order the T^* from various settings?

* The sampling rules from L255 and the recommendation in L268 are not entirely clear to me. Would it be possible to present in an Algorithm format?

* The application in 4.2 involves time, which is a mismatch with the theory in the paper (which focused on subpopulations). 
So, I am not sure how much this adds to the paper.






limitations_and_societal_impact: .
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers the problem of A/B/n testing with subpopulations. At each time step, a sample appears from one of $J$ subpopulations and the player chooses an arm to play. Depending on the variant of the game, the sample may be chosen by the player, drawn by nature and observed before (or after) an arm is chosen, or not observed at all. The goal is to identify the arms whose true means, averaged across the subpopulations according to some known weight vector beta, exceed that of the *control* arm. This places the work in a similar vein as work that identifies all arms above a threshold, but the threshold is defined as the mean of the control arm, which must be estimated.

The paper proposes a subpopulation-aware version of the Track-and-Stop algorithm that allocates samples according to an optimization problem present in the lower bound. Since that optimization problem is somewhat opaque, the paper also derives and discusses the closed-form update rule in the Gaussian setting. The paper concludes with simulated and real-data experiments on Bernoulli observations.
main_review: Positives:
- The paper demonstrates a firm grasp of the literature upon which it builds, and the algorithmic and proof techniques therein.
- The paper provides a thorough treatment of different observation settings the player might encounter (active, proportional, agnostic, and oblivious). In addition, the separation of \alpha from \beta provide another layer of detail that makes the setting more broadly applicable.
- Including the optimal weight vector and resulting stopping time for the Gaussian case really helps the reader understand the improvements possible in different settings.

Areas for improvement:
- The algorithm description did not contain enough detail to reproduce the results in the paper, which is even more problematic because code was not submitted. In particular, line 270 (the generalized likelihood ratio test statistic) is itself an optimization problem, and it is not immediately clear how to generate the threshold. If this is trivial, perhaps include it in the appendix with a reference in the main body. Additionally, I suspect that the phrase "(a suitable approximation of)" in lines 259-260 refers to the iterative saddle point solver mentioned in lines 251-252, but it would be nice to see this made explicit.
- After reading the paper, it was unclear whether the method can be practically run for other members of the exponential family. The experiments were run in the Bernoulli setting, but since there wasn't a lot of detail on how to implement the algorithm (see above), it's not clear whether the Bernoulli setting is just particularly tractable, or whether the same method could in practice be used for other exponential-family distributions.


Additional comments:
- Table 1: the absence of confidence intervals or other uncertainty quantification means we cannot evaluate the claim of "the active mode having a slight edge" (line 308).
- Proposition 2, missing a comma in the first line of math before w_{a,i}^\star.
- Caption of Figure 2, mu is a 3x3 matrix, so it's not immediately clear which dimension is J and which is K. Consider adding $\in [0,1]^{K\times J}$ (or the other way around, whichever it is).


Update 8/16:
I would like to thank the authors for their thoughtful rebuttal, which clarified the questions I had about the algorithm. In particular, in light of the authors' proposed clarifications (the optimization from [6], clarification that this is indeed the suitable approximation mentioned in the text, and discussion on when the GLRT threshold is easy to obtain) I have changed my recommendation to 'accept'. I still think that the presentation of the algorithm in paragraph form is borderline too colloquial for this paper, since the algorithm is an important contribution, and I would encourage the authors to formalize their presentation of the algorithm. However, since code will be provided, I am less concerned about a lack of reproducibility. 

limitations_and_societal_impact: I was surprised that, in the paper checklist, the authors responded N/A to the question of societal impacts. In a work on optimizing across subpopulations, where the paper is motivated with examples from e-commerce (line 21) and clinical trials (line 77), the intersection with questions of societal impact is quite large. For example, the goal of this work is to find arms with large beta-weighted rewards, where a common choice is beta=alpha, the population proportions. Are there settings in which we might choose beta differently from alpha, to satisfy certain fairness constraints? Settings in which we might not want to beta-weight our rewards at all, but rather, say, maximize the minimum reward across populations? Populations with more variance are sampled more than their proportion alpha - are there situations in which this could be good or bad for that population?

It's okay if the authors don't want to discuss these questions, but it's surprising that they indicated societal impact was not applicable to their work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studies a variation of the multi-armed bandit problem, in which one seeks to identify all arms that are better than the control arm, as opposed to the standard “best arm identification” problem. The authors study the sampling complexity and investigate the impact of different modes of interactions in sampling from different arms and subpopulations. 
main_review: - The paper is well-written and the problem is interesting. 

- The paper is mathematically rigorous. 

- A major concern is that, apart from the modes of interaction considered in this work (which is a good addition), the main result of the paper in Theorem 1 is well-known. The problem is an instance of a classic problem in statistics on optimal design of experiments, initially studied by Chernoff in his seminal work on "sequential design of experiments". Chernoff analyzed the expected stopping time and obtained a very similar expression, which can be viewed as the valuation of a zero-sum game in which one player (the controller) chooses a randomized strategy over the actions (here, the coefficients w in the supremum in (3) for the arms and subpopulations) to maximize the weighted KL distance, while the other player (nature) chooses the worst-case alternative hypothesis (here, the mean vector \lambda) to minimize the weighted KL distance. I believe the main novelty lies in studying different modes of interactions as special cases of this problem. 

- From an asymptotic analysis standpoint (the focus of this work), I do not see what the major differences between the BAI problem and the problem at hand are. Consider the scenario in which one starts off identifying the best arm, after which we stop sampling from this arm. The process is repeated to identify the best arm from the remaining ones. After at most K times, we can identify all arms that are better than the control. This is just a constant K factor, which will not change the order complexity. 

- The authors do not cite important related work, including the work of Chernoff mentioned earlier on sequential design of experiments, and the work of Lai and Robbins on index policies for multi-armed bandits. There is a large body of closely related work on the topic that the authors ignore (or are probably unaware of).   

limitations_and_societal_impact: N/A
review_title: null

Meta-review: Dear authors,

There was some disagreement between the reviewers.
Given this, and taking into account all comments, as well as background of the reviewers, I decided to take a special look at the article.

After reading the article, I believe this setting is well-motivated and interesting. 
The lower bounds do not seem very hard to derive, but I appreciate the effort to make them explicit on an illustrative example.
The proof of Theorem 2 is heavily relying on previous work, working by reduction. 
Clarity should indeed be improved, regarding presentation of the algorithm and notations. 
[Small point: I suggest you add $\\beta$ in the notation for $S(\\mu)$ or $Alt(\\mu)$, and otherwise it is not clear where is the dependency in beta in Theorem 1]
Regarding the algorithm, I do not encourage using a different beta(t,\delta) for the analysis to be true and a "stylized one" for the experiments, as this indicates mismatch between theory and experiments.
Now, the algorithm does achieve optimality in the considered setting and is supported by illustrative numerical results.

The discussion of the complexity of the algorithm and the handling of the $2^K$ sets to consider should be improved.
Proposition 3 brings an interesting point, but I feel this part could be extended (for instance, what happens then for other distributions, is there any hope of having some reasonable complexity?) 
The numerical experiments should also be clarified, and seem to be restricted to small values of K: I encourage to consider examples with much larger $K$ as well, and perhaps highlight the (low?) computational complexity of the algorithm.


All in all, I believe this is a simple adaptation of an existing work to a relevant problem. The paper has interesting bits, but each of them seem done shallowly. This makes the paper unfortunately borderline. I recommend acceptance, conditioning on the fact the authors provide more convincing discussion and experiments regarding the numerical complexity, but only if there is enough place for that.
Otherwise I would be happy to see an updated version of this article taking into accounts all feedbacks.



Decision: Accept (Poster)