A/B/n Testing with Control in the Presence of Subpopulations
Authors: Yoan Russac
Christina Katsimerou
Dennis Bohle
Olivier Cappé
Aurélien Garivier
Wouter M Koolen
Venue: NeurIPS 2021 Poster (2021)
Keywords: Pure exploration strategies
subpopulations
bandits

Abstract: Motivated by A/B/n testing applications, we consider a finite set of distributions (called \emph{arms}), one of which is treated as a \emph{control}. We assume that the population is stratified into homogeneous subpopulations. At every time step, a subpopulation is sampled and an arm is chosen: the resulting observation is an independent draw from the arm conditioned on the subpopulation. The quality of each arm is assessed through a weighted combination of its subpopulation means. We propose a strategy for sequentially choosing one arm per time step so as to discover as fast as possible which arms, if any, have higher weighted expectation than the control. This strategy is shown to be asymptotically optimal in the following sense: if $\tau_\delta$ is the first time when the strategy ensures that it is able to output the correct answer with probability at least $1-\delta$, then $\mathbb{E}[\tau_\delta]$ grows linearly with $\log(1/\delta)$ at the exact optimal rate. This rate is identified in the paper in three different settings: (1) when the experimenter does not observe the subpopulation information, (2) when the subpopulation of each sample is observed but not chosen, and (3) when the experimenter can select the subpopulation from which each response is sampled. We illustrate the efficiency of the proposed strategy with numerical simulations on synthetic and real data collected from an A/B/n experiment.

A/B/n Testing with Control in the Presence of Subpopulations
Yoan Russac CNRS, Inria, ENS
Christina Katsimerou Booking.com christina. haw.iaa..aaammmmrrooooooiiii....
Université PSL yoan. www.ruuussss.......... fr
Dennis Bohle Booking.com com dennis. heniis.bohee@bokiing www.eehhookkkgg.com
Olivier Cappé CNRS, Inria, ENS Université PSL olivier. cappe@cnrs. fr
Aurélien Garivier UMPA, CNRS Inria, ENS Lyon aurelien. aurelieen.garivieeren----oo
Wouter M. Koolen Centrum Wiskunde & Informatica wmkoolen@cwi.nn
Abstract
Motivated by A/B/n testing applications, we consider finite set of distributions (called arms), one which treated as a control. assume that the population is stratified into homogeneous subpopulations. At every time step, subpopulation is sampled and an arm chosen: the resulting observation an independent draw from the arm conditioned the subpopulation. The quality of cach arm is assessed through a weighted combination of its subpopulation means. We propose strategy for sequentially choosing one per time step which arms, if any, have higher weighted expectation than the control. This strategy is shown to be asymptotically optimal in the following sense: if is the first time when the strategy ensures that it is able to output the correct answer with probability least 1 5, then E[Ts] grows linearly with log(1/ō) the exact optimal rate. This rate identified in the paper in three different settings: (1) when the experimenter does not observe the subpopulation information, (2) when the subpopulation of each sample is observed but not chosen, and (3) when the experimenter can select the subpopulation from which each response is sampled. We illustrate the efficiency of the proposed strategy with numerical simulations on synthetic and real data collected from A/B/n experiment.
to discover fast possible
Introduction
A/B/n testing is a website optimization procedure where multiple versions of the content (called "arms" below) are compared, often order to find the one with the highest conversion rate. However, many e-commerce companies A/B/n testing not only to deploy the best product implementation, but primarily to draw post-experiment inferences IT. The decision-making involves, besides experiment results, factors such the cost of scaling-up solution, external data, whether the implementation fits in broader theme. In this setting, each of the arms better than the default product (which we will refer the "control" arm) is contender for being deployed and the interest only in the best arm.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Given the control and K 2 1 alternative implementations (variants), the simplest idea is to distribute the traffic uniformly among the arms; the arms that appear to be sigmificantly better than the control at the end of the experiment are considered for deployment. While well-established, this process can be inefficient terms of resources. Some alternatives are soon obviously worse (or better) than the control and would require fewer samples than the alternatives closer to the control. A second related shortcoming of the basic A/B/n testing approach is that setting the duration of the experiment -when done in advance- necessitates very conservative approach by choosing run-length that is sufficiently long to differentiate even the smallest possible changes.
To address these limitations, we consider in this work sequential testing policies that can both adjust the allocation of the samples and be stopped adaptively, in light of the data gathered during the experiment. In the terminology of multi-armed bandits, this corresponds to pure exploration problems (see, e.g., Chap. 33 of [5).. A pure exploration strategy will typically choose every minute (say), an allocation of traffic that favors arms for which the uncertainty is the highest. The experiment is stopped as soon as the significance considered sufficient for every arm. Approaches have been developed in 88 [2 [0] for the identification of the single arm with the highest mean, a task called the Best Arm Identification (BAI) problem. In particular, [10] propose a strategy that is asymptotically optimal in the fixed confidence setting, meaning that, given risk parameter 6, it finds the best arm with probability at least 1 - 6, using an expected number of samples that is hardly improvable when is small. Later, [18] incorporated the special role of the control arm in BAI and proposed an algorithm that declares as winning arm the one with the highest mean only if it is significantly better than the control. In this paper, propose a solution to the problem of identifying all the arms that are better than the control, in a framework that generalizes the fixed confidence setting. In order to provide useful tools for practical A/B/n testing, address two additional issues.
First, traditional stochastic bandit models are based on the assumption that the arm samples are ii.d., whereas real world data streams usually show trends or some form of inhomogeneity. A particular case of interest for website optimization are the seasonal patterns caused by time-of-day or day-of-week variations. We henceforth include in our model observed covariates (e.g. the time of the day, but possibly also the country of origin, or controlled covariates like the order in which partners appear the page, etc.) that stratify the observations into homogeneous subpopulations. We study different scenarios, depending on how much interaction is possible with these subpopulations. We provide a sample complexity analysis and an efficient algorithm in each case. In particular, we will show that using the subpopulation information efficiently can provide significant speedups of the decision-make making. In the following, we will refer to the task of identifying the set of Arms that are Better than the Control in the presence of Subpopulations as the ABC-S problem.
Second, the practice of A/B/n testing often differs from pure sequential experiment in that the experimenter cannot always fix a risk 8 at the beginning and passively wait for the stopping time of the experiment without any time limitation. To address this issue, [II] proposed to define some notion of sequential "p-values" that can be monitored as the experiment progresses and used to terminate it. this idea
This notion was further used in the BAI setting in [8]. In this contribution, we elaborate by sequentially updating a suggested solution to the ABC-S problem together with a risk assessment for this suggestion. We show that, for any stopping time, the probability that the suggested solution is incorrect is indeed lower than the risk assessment. When the stopping time is selected as in usual fixed-confidence pure exploration, we recover the exact same guarantees but this view of the problem also provides useful results, for instance, if the experiment needs to be terminated prematurely.
Related work. Pure exploration strategies have been studied in various settings: the identification of the best arm R 10), the identification of the top m arms [3 12 9 identifying the arms that are better than a threshold [16 4) or identifying all e-good arms [17]. As far as we know, this paper is the first to consider the problem of identifying all the arms better than control. It is also the first to consider subpopulations in pure exploration tasks. While motivated by the example of online companies, we believe that the proposed algorithms are relevant to other domains where randomized controlled trials are used for learning. An example could be clinical trials: one may wish to identify all the alternative treatments that work better that some reference medical treatment. This would permit to choose among them taking into account different characteristics (some could be cheaper, using another molecule for avoiding allergy, etc.).
Close to the notion of the control is the notion of threshold. Locatelli et al. [6 propose an algorithm for identifying all arms above given threshold. Their algorithm samples according to the significance

---

of statistical test, and shares some similarities with the present article in the Gaussian case; however, the perspective is rather different: the authors consider the fixed-budget setting: the total number of samples is fixed, and the goal is then to minimize the probability of returning a wrong answer at the end. Here, the index of the control arm known but its probability distribution is not.
In our work, the quality of the different arms is assessed with weighted combination of its subpopu- lations means. Minimizing the estimation error of a convex combination of means through adaptive sampling was considered in 22 with the introduction of a stratified estimator that will naturally appear in our analysis.
The paper is organized as follows. In Section 2 we present the mathematical model and study the information -hooraation-thooretic complexity of the problem, extending the lower bound of [TO] to the ABC-S setting. We show how the complexity of the problem depends on the degree of interaction that one has with the subpopulations, introducing different modes of interaction to be defined in Figure [ below. We also consider in detail the Gaussian case which gives rise to more interpretable results. Section DectionB]dssctt describes how to implement the proposed strategy, which involves the numerical resolution of non-trivial optimization problems. Finally, we provide the results of numerical experiments on synthetic and real data sets in Section
2
The complexity of the ABC-S problem
2.1 Mathematical framework
problem instance consists of the following ingredients. Known to the learner are the number of arms K 2 in addition to the designated control arm O, the number of subpopulations J (a standard bandit being J = 1). and the vector [ E IR'' representing the relative importance of the subpopulations for the learning objective. We further make the stochastic assumption that samples from each arm (including the control) and subpopulation are drawn i.i.d. from an unknown probability distribution
- Vaii on R. whose mean we will denote by Pa.i- The quality of arm a is Pa == Σiz 3apa, the combination of the means of the arms in the different populations. For B E R we define the ABC-S problem the correct identification of the set
Sa(1) = {a E [K]
Σ
Bspaas Σ B.pa
At every time step i, the algorithm selects an arm A, based on previous choices and outcomes and observes selects (except when explicitly specified) the population type I,- Upon the selection of the arm A, a reward X, is obtained. This defines a sigma-field generated by the observations up to time t denoted F, oII,, .I....,I. It, X2). The number of times arm a was selected for subpopulation at time denoted (t) = E a=1 (A, = a, I = e) and the number of draws of arm a,
(1) = Eim 1(A,- = a). We define the gap with the control arm and arm a, A₂ == pro - Pa-
Modes of interaction We consider four modes of interaction of the learner with the bandit, as
specified in Figure[ below. In any of the three passive modes of interaction (described in Figures [b Id) we assume that the subpopulation represents a known proportion a; of the total population, and hence that the sequence of subpopulations is drawn i.i.d. from the fixed and discrete distribution I a- (oi,,...,a.) with a Σ, {i E [0, 1]" Σ, x3 = 1} the J-dimensional simplex. Here a is an exogenous parameter and can differ from B which is inherent to the learning objective and is also assumed to be known. Although it most natural in many applications consider that B = a (it is even necessary in the oblivious mode to make the estimation of the Na 's feasible). Example I below describes a concrete scenario in which ,3 has negative components.
The distributions (Va,)a. are assumed to belong the same one- per-aarmeeter exponential family, P = {(v))) dug/dg exp(Or= b(0)),. with & a reference measure on R and b θ C R + R. Every probability distribution 24 in is entirely defined by its mean b(0) M... We may hence identify any bandit instance with its matrix of means μ E [K] In addition, the Kullback-Leibler divergence between two distributions vy and ugr E P may be written in the following Bregman form:
d(u, p¹) KL ver b(0') - b(0) - 6(0)(0' - -0)
3

---

1. See 1t ~ a
Pick Ar
Pick As
1. Pick A, and 4
2. Pick A,
See 1, a
2. Do not see Lt
2. See X VArl
3. See X2 VArt
3. See X VAr,
3. See X₃ VArl
(a) Active mode
(b) Proportional mode
(c) Agnostic mode
(d) Oblivious mode.
Figure I: Modes of Interaction between Learner and Bandit each round. In Active mode the learner determines the subpopulation, while in the right three passive modes it is sampled from
where μ = 6(0) and μ' = b(0') correspond to the means of the two distributions Me and var. We also use the notation kl q) to denote the KL divergence two Bernoulli distributions of parameter p and g.
We define C c= f Va [0), Vi [J]. P and po * Ha the set of identifiable instances where no arm has the same weighted mean as the control. At every time step. the policies we consider output risk assessment 6, together with a recommendation St. We focus on safely calibrated policies, that are defined as satisfying the following property
Ai E L, Vo E (0, PA (3 S. Sa(u) n 8, s 56.
(1)
Finally, when fixing level of risk 6, we consider the stopping time associated to the filtration Fe ft 2 0, & S 5}. The objective is then to minimize the expected number of rounds necessary to obtain a level of risk at most 8. Contrary to usual 8-PAC algorithms stopped before Ts, the strategy still provides guarantees on the output set following Equation]] [ In particular, safely calibrated policies have a sampling rule that does not depend on any pre- specified 6, and as such they 8-PAC for any 8.
Example 1 ([Largest Profit Identification problem 13 p24]). Consider company choosing among K product designs the model mass produce. Each candidate design i has an (equilibrium) sales price μx,1 and production cost μ4.2- The goal is to find the model k with the largest profit fk.1 - M4,2- Prices and costs are currently unknown, but can be adaptively sampled. Sampling the "price" subpopulation = 1 is typically implemented by performing user preference studies, taking questionnaires, etc. Samples from the "cost" subpopulation
2 involve rating manufacturing facilities, forecasting material and labor costs etc. This problem is interesting both in the BAI and ABC objectives. The importance vector is here B = (1, -1) and a has to be set by the learner.
2.2 General form of the sample complexity
Depending on the mode of interaction from Figure I the learner has a set of sampling constraints to satisfy, here denoted C and precisely defined in the next section. We define Alt(u), the different problem instances where the of arms better than the control differs from that of the instance μ. Formally, (1) = (X E L S ()) + Sz(1)). This allows us to bound the sample complexity.
Theorem 1.
Let E (0, and & R. For any strategy satisfying Equation 1 and any μ u L, the expected number of rounds for the ABC-S problem for the agnostic, proportional and active mode satisfies:
E ETlTT]] iim 5-+0
E T* (H) kl -) and
T (M)).
ln(1/8)
where (recalling that \a E1 = (ida,s)
T (M))1 sup inf
Wa da,i)
(3)
weC (1)) a=0 i=1
sup min inf weC by0 Ad dE(0,6)
Σ
Wa da,t)
(4)
This result is established in Appendix A T characterizes the difficulty of the learning problem.

---

2.3 Influence of the mode of interaction
We consider the four different modes governing the sampling rule as outlined in Figure I In the agnostic mode (Fig. Ic] an arm is first selected, after which the subpopulation type is observed. Mathematically, this brings the equality En (T)) B, (T)) established in Lemma 2 and
the independence constraint on the weights ur Cagnosii = [Wa,i = Okyilaa (Mo, ..... ux) E E
In the proportional mode (Fig. Thp, A, is chosen based on F and the current subpopulation J Here, the constraint is that the total number of pulls of the different arms in the subpopulation i should a;T. This induces marginal constraint on the weights of the form w E Cprop == {w E (KK+1) Vi S J, 2a Wa, = ai). This
respect the frequency of this subpopulation, i.c. Ee Bu[NN,, (T))
result established in Lemma reported in Appendix [
In the active mode (Fig. Lap. the learner has an additional degree of freedom she can ask for any Cactive == [(K+))J is unconstrained.
subpopulation type at any round. In that case,
By remarking that Cagnestic C Crrup C Castives and given the optimization program solved to obtain the characteristic time, one immediately gets
VuE T S proportionall (1) S agnossic (14)
(5)
Hence, expected, the more control/information the subpopulation the learner has, the faster she is able to identify the set of arms that are better than the control.
To compare with the oblivious mode, in which the subpopulation information is not even observed, we have to assume that a = B. In that case, the arm rewards follow a mixture distribution: x,|4,=a ~ Σi= a;Van.: In Proposition 4 reported in Appendix B.3 we properly define the characteristic time of oblivious safely calibrated policy and prove that the joint convexity of Kullback-Leible Leibler divergences implies that it is larger than its agnostic counterpart. This completes the picture of the ordering of the characteristic times by showing that, when a B,
Ay E L, Trative (14) S T proportional (1)) S T agnostic (1) S ohlivious (1))
(6)
Note that although we provide, in Section 3 algorithms complexites, evaluating chtivious (14) would be much harder, as the mixture distributions can no more be parameterized by their mean only. Our current techniques do not yield a general-purpose practical algorithm that is asymptotically optimal in the oblivious mode for the ABC-S problem. In the Bernoulli case, however, as mixtures of Bernoulli distributions are Bernoulli distribution, one can use the peggle-opplation Bernoulli approach discussed in the next paragraph. For Gaussian distributions, one can use a suboptimal approach based on the observation that location mixtures of Gaussians with bounded means are sub-Gaussian (see Appendix B.3 for details).
numerically compute the first three
2.4 Single population and relationship with best arm identification
In order to illustrate the nature of the the ABC-S problem, we make detour through the single population case, that is, when J = 1. Given two weights wa, we and two means Has Ha. we introduce the minimum weighted transportation cost for moving the means to a common position.
dmia(w, Way Bay Wh, pb) = inf w.,((a, v) + wndd(u,, v) wad(pa, va,b) waddus, v(,o)
wa where th the optimal common location, is the weighted average, i.e. vi.b = wa Ma +
mn 4.0 Mb-
Constructing an instance in the alternative When identifying all the arms better than a control, there are two different ways to obtain close-by bandit model X in the alternative. The first option consists in taking an arm which does not belong to S3(H) and to augment its mean on the alternative model such that it becomes above the control (or to reduce the mean of the control). Otherwise, it is possible to take an arm that is better than the control in the bandit model Js and to shrink its mean such that it becomes lower than the control on the alternative (or augment the control). Note that the infimum over the alternative has the same expression in the two cases (see proof of Proposition I in Appendix A.2). A.22)
There a priori no link between a BAT problem and an ABC one. particular, in the BAT problem there only K + possible choices for the best arm while when looking for (p())) there are up to
5

---

the optimal weights 2" different sets to consider. Yet, the next proposition shows that the characteristic time T* of any ABC problem with J subpopulation shares strong similarities with that of BAI problems. Proposition 1. Let 8 E 10 and μ L. For any strategy satisfying Equation with
Equation holds
K
(1)
inf wEEx++ (M)) a=0
sup
Wad(Ma da)=
sup min danial (Wo, Mo, Wb, (b6) weEK4 6ş60
The proof is reported in Appendix A.2 Note that the expression of the sample complexity is really close to the one in the BAI setting Garivier and Kaufmann [10] Lemma 3J) except that we consider all the indices different from the control here instead of the indices different from the best arm.
2.5 The Gaussian case
In this section, we consider the Gaussian case which is of interest as the characteristic time admits a more explicit expression, making it possible further investigate the differences between the various modes of interaction. We will state our results for the heteroscedastic case, in particular to get closed-form proxy for the Bernoulli case, where each variance a function of the (unknown) mean.
A/B testing When K = (one arm and the control arm), we are considering a standard A/B test with subpopulations and one easily prove the following result (established in Appendix C Proposition 2. For any μ E L with K and Vo, = N (Haag o2.5) one has
(
Σl
+V
Eim
2 DE
1. T agnostic (p)
and WA,+ =
oz
A
19 0.
s8 a.
E ar
+V E
(on 2
2. Ti prop ppiop(1)) (1e)
on
and Vi S J, Va E (0, 1), w
0..0.1
A9
do., +0..
3. T active (1)) 2(E! t0. and Vi S J, Va E {0, 1}. W E'm 13 (do. +01.))
Af
The optimal allocations in the agnostic and proportional cases constrained by the proportion of the different subpopulations a, whereas, for the active mode, the optimal weights only depend on G. In general, the optimal weights also depend on the subpopulation variances, is well-known in stratified sampling estimation. Note however, that when (a) the subpopulations all have common variance o² and (b) B a. then the optimal allocations and the characteristic times are equal for the agnostic, the proportional and the active modes. In that case, : a:/2, which also corresponds to the well-know result in Gaussian A/B testing [14.. We have more generally observed that whenever the subpopulations have approximately the same variances, the agnostic and proportional modes yield very similar performances.
Weight computation in the homoscedastic case Even in scenarios where all subpopulation vari- ances are equal 2², the active mode remains very attractive in the cases where 3 * a. The following proposition shows that in that case, the optimal weights for the ABC-S problem can be computed efficiently.
Proposition 3 (Efficient computation in the Gaussian case). With Gaussian distributions with a known variance o², letting (ug .... ux) argmax min A
for the active mode satisfy
Va {O..... KJ, vi J, w u
If. in addition a [,, the above also holds for the agnostic and the proportional modes.
The interesting part of Proposition 3 is that computing (ui:..., "ix can be done efficiently using Theorem from [00) The optimal weights of the ABC-S problem can be deduced from u² without any further calculation.

---

3 Algorithms
To obtain our algorithms, instantiate the Track-and-Sen -top algorithm template to our ABC-S problem. Garivier and Kaufmann [10] introduced Track-and-Stop and proved its asymptotic optimality in the BAT setting. Asymptotic optimality for general partition identification problems was subsequently established by Kaufmann and Koolen [13] Theorem 23] under the assumption of continuity of the oracle weights μ w" (1.). Degenne and Koolen [6] show that the continuity assumption holds for all single-answer problems, in the upper- apper-hemicontinityy sense, which they show implies asymptotic optimality of the Track-and-Stop (T-a-S) algorithm. These results directly apply to our ABC-S problem. Degenne et al. (7] interpret T-a-S as noisy sequential equilibrium computation for the max-min problem from the lower bound (e.g. Equation and develop computationally attractive variants including lazy iterative solution of the w" problem, and optimistic gradients instead of forced exploration.
The details of our implementaiion are given in Appendix F In short, we use the simple standard ( forced exploration rounds, a mode/subpopulation aware upgrade of the D-tracking scheme 10 (which is empirically superior to C-tracking) and approximately and incrementally compute the oracle weights using the AdaHedge vs Best Response iterative saddle point solver from [7]. We one single learner, instead of one per possible answer, advocated in 77] Section 4]. Note that we are not affected by the non-convergence of D-tracking from [7] Appendix EJ. as our problem has unique wn because it is strictly concave in (see Appendix E
The sampling rule The high level overview of the algorithm is follows. We are given the number of arms and subpopulations J. the exponential family, the mode of interaction, the subpopulation importance coefficients 33 and, for passive modes, their natural frequencies a. The algorithm then proceeds in rounds 1, Each round I, it calculates the empirical frequencies ja. E R R
given by (t) = No.ity E.= X,1 (A, L. i}. It then computes (a suitable approximation of) the maximiser (i.e. the oracle policy) w, = w² (pt) E E(K+1xxJ of problem (2). In the active mode, we "D-track" w;, i.e. we sample (A,,4, 4e) E argmax, Nt, Naa, the proportional mode, the subpopulation I, is given and we "D-track" the conditional distribution of w. on arms given the subpopulation, i.e. At argmax, Na.1, Naamax,Na.1140 (.(a, i) = a;wr(ali). In the agnostic mode we "D-track" the marginal distribution of w, on arms, i.e. A, E argmax, - 1) (a). For each mode, this sampling strategy ensures that (t, xs (a, tw (H). thus driving down the reported level of confidence as quickly as possible given the lower bound from Theorem
- 1) (a, In
1) to ur, (a) where
The recommendation Concluding each round, we recommend Sg(it)) at confidence level ô(t) min {ō ())((( 2 S(t, })} obtained by inverting the threshold ((t, 5) at the GLR statistic
A(I)
min inf
Σ
do 6y0 AEC:do= =
aE (0.5) 1m
The threshold For the sharpest theoretically supported thresholds we refer to 13 Namely, an
ABC-S problem with K-arms and J-subpopulations has 2 answers, and its rank 13
Definition 22]
2.,, as can be read off from 4 By [13] Proposition 23] we have validity for B(t, 6) 66
In + K 2J O(In In 4). In practice, we follow [10 and use instead the heavily stylized
In((1 + In ()5) that omits several union bounds.
Theorem 2. For every mode, Subpopulation Track-and-Stop is safely calibrated (Equation Moreover, Subpopulation Track-and-Stop is asymptotically optimal and matches the lower bound from Theorem 7 in the sense that
E[Ta] 6-+0 (1
for every bandit μa L, lim
T T*))
We include the proof in Appendix E

---

Experiments
4.1 Simulations
We conduct numerical experiments to evaluate the proposed algorithms, focusing on Bernoulli bandit models, which are ubiquitous in practical applications.
In our experiments, in addition our T-a-S algorithms with the various interaction modes, we include two more sampling rules for comparison: (1) uniform sampling as a baseline, and (2) the experimentally efficient Best Challenger heuristic inspired by [0], adapted to the ABC problem and denoted BC-ABC in the sequel. BC [10] for the BAI problem samples in every round the empirical best arm à, or its best challenger, i.c. the arm & * āy at which the GLR statistic (Equation 7 reaches its minimum. Our BC-ABC adaptation samples in every round the control arm or the arm that yields the minimum GLR statistic (t), the agnostic interaction mode (since A(t) is subpopulation independent). For clearer comparison between the sampling strategies, all algorithms use the Chernoff stopping criterion [10] to determine either when to stop or output the risk assessment at given time. We also opted for sampling rules independent from the confidence parameter 6, because aiming for safely calibrated policies.
We first illustrate the fact that the T-a-S algorithm provides a correct but rather conservative- assessment the risk of its decision whatever the time it is stopped at. To so, we generated 1000 bandit instances uniformly at random from [0, I] with K" = 2 arms. For each instance, we recorded the first time a certain risk assessment level reached and the correctness of the algorithm'ss recommendation at that point. We map to each risk assessment level the proportion of errors across all instances. We chose two stopping rates that are not supported by theory but are recommended in practice [10]. Figure (Left) illustrates the isotonic curve fitted on observations and suggests that even the most lenient stopping threshold In (In(t) + +)//)) results in much lower empirical probability of eтror than the risk assessment. In the following, we use the stopping threshold In In(In(t) + 1)/6).
70000
In(0kCC 17/3) In(Kke66) 11/8)
akg
practical
35
risk Acsessment
activve
prop.
agn.
BC-ABC
Uniform
Figure 2: (Left) Risk assessment calibration log-log scale. (Right) Stopping time boxplot for μ [0.1 0.4 0.3; 0.2 0.5 0.2; 2; 0.5 0.1 0.1] e [o, 1](++1)x] when 3 = [1/3, 1 1/3, 1/3], a [0.4, 0.5, 0.1] with Bernoulli distributions.
In our second experiment we generated 3000 Bernoulli bandit instances with K = 2 and random number of subpopulations J between 2 and 10. Each subpopulation-arm'ss mean Ma, is drawn uniformly at random from [0, 1]. and the subpopulation frequency vector a is drawn from Dirichlet(10) distribution. Table [ reports the average stopping time of each algorithm across all bandit instances. On average, the T-a-S algorithms at all modes stop at similar times, and all adaptive sampling methods terminate faster than uniform sampling.
Table 1: Average stopping time. Description in text.
T-a-S (active) T-a-S (proportional) T-a-S (agnostic) BC-ABC
Uniform
14871
15231
15444
15279
21586
athttpss//giitann http://aw..ccneeeaeeeeee/eaaaaap

---

To better understand the role of [3 and a. we ran the algorithms on specific model (see Figure 2 Right) with * B. In this case, the optimal proportions are constrained by the frequencies of the subpopulation for passive interaction modes. The expected number of samples needed to identify the ABC-S solution is lower for the active policy, which has an additional degree of freedom in its sampling strategy. The proportional interaction mode and the agnostic interaction modes perform similarly, As expected, all the proposed strategies outperform the uniform sampling rule. We contrast the stopping time with the lower bound (l(6, 1 - 8yT" and with a more practical version, which indicates, approximately, the first time at which the GLR statistic crosses the threshold, i.e. solving t In( (In((t) + 1)/)T"(()) as was done in [7] All adaptive algorithms perform well on this instance, with their average runtime being very close to their respective practical bound.
4.2 Application to A/B/n experiment
We evaluate the algorithms on data collected from an actual A/B/n experiment, which compares different copies of component of the webpage, in order to identify the ones better than the default copy. The metric of interest is whether the visitor clicked at least once during the experiment to the next page after getting exposed one of the variants. For this setup considered K 2 copies competing against the control, with each copy being treated as an arm. Due to global traffic, the data exhibits strong seasonality patterns within day, as seen in Figure Baj in which every point corresponds to click-through rate per six hours (quarter of day) for 12 consecutive days. We treat the J seasons as i.i.d. subpopulations. Within each season we shuffled the data eliminate the weekly trend.
The summary statistics of the dataset, together with the characteristic times and the optimal weights for each T-a-S mode can be found in Appendix G makes this practical ABC-S problem much harder than the synthetically generated examples.
Note that the small gaps between the arm means
We tested all algorithms described in Section 4.1 Each algorithm terminates when it reaches for the first time 8, S 0.1 or outputs a risk assessment on the recommendation if it runs out of samples, which in this experiment occurs after 1.4-107 observations. Here, we weigh the importance 33 of each season equally to its observed frequency a. Doing so, we do not expect large performance discrepancies between the different T-a-S interaction modes, which is confirmed by their characteristic times (Appendix The observations from Fig.Bb]arc Bbee similar to the results from the numerical simulations: adaptive sampling achieves lower sample complexity over uniform sampling and T-a-S for the active interaction mode terminates faster than for the passive modes. All algorithms yield the correct recommendation, but not with the same risk assessment. All T-a-S algorithms terminated within the available sample size, BC-ABC almost terminated and output a risk assessment slightly above 0.1 and uniform's 's risk assessment was 0.67. Of course, when viewing seasonality as a subpopulation. the active mode is unrealistic, but it is still informative to see that it can be very economical in hard problems in which sampling the subpopulations actively is an option. In this instance, proportional, agnostic and oblivious modes terminated at similar times. However, we would recommend using the proportional mode, given that we expect to never perform worse than the other passive modes on average. One should not be surprised by the curve for the uniform sampling, this policy was stopped before convergence because it ran out of samples.
Lastly, here we assumed that seasons occur in i.i.d. fashion, but in reality there is temporal dependence between them. This imposes extra constraints on the optimal weights and increases the sample complexity. However, we do not expect this to be detrimental for cases in which seasons alternate frequently and full cycles are observed often, as was the case with our example.
Conclusion
In this work, we considered the pure exploration task of identifying all the arms that are better than a control arm in the presence of subpopulations (ABC-S). We design asymptotically optimal policies for this problem under different assumptions on the mode of interaction between the learner and the bandit. We observed that the active mode, in which the learner decides which subpopulation samples, may significantly reduce decision times. On the other hand, the other modes, in which the learner has to respect the natural proportions of the different subpopulations (i.e., in proportional and agnostic modes) produce more modest effects, except when the subpopulations differ significantly in

---

0.7
0.00
16k stsnsmmett
metti
0.00
active
0.4
prpprtional
ablivious
0.2
BCABC
unifirm
20
0
1.0
11
1.3
time
samples/10 /10' (aher 8 10
(a) Click-through rate per 6 hours for 12 days.
(b) Risk assessment over time.
Figure 3: Real data and results.
variances. Finally, we proposed a natural way to provide anytime decisions with risk guarantees in the Track-and-Stop framework.
Potential Societal Impact
The contributions presented in this work are mostly related methods and, as such, do not have direct expected societal impact. This being said, a potential concern that will need to be addressed more carefully in subsequent applications of these methods is the use of subpopulation information, which could be exploited to target specific user behaviour or characteristics. In the use case considered in Section 4.2, the subpopulations correspond to time slots that used model seasonality in the user responses, which does not raise any specific ethical concern. However, in cases where the subpopulations are formed using characteristics of individual users, the impact needs to be assessed more thoroughly. Note that in such cases, restricting to one of the more conservative modes of interaction (i.e. agnostic even oblivious) may become necessary in order prevent undue use of population-dependent information.
Acknowledgment
The authors would like to thank the anonymous reviewers whose comments and questions helped improve the clarity of this manuscript. A. Garivier acknowledges the support of the Project IDEX- LYON of the University of Lyon, in the framework of the Programme Investissements d' Avenir (ANR-16-IDE) ID--X-I0) and Chaire SeqALO (ANR-20-CHIA-0022)
10

---

References
[1] O. Cappé, A. Garivier, O.-A. Maillard, R. Munos, G. Stoltz, et al. Kullback-lcible upper confidence bounds for optimal sequential allocation. Annals Statistics, 41(3):111-1541, 2013.
[2] A. Carpentier and R. Munos. Finite-time analysis stratified sampling for monte carlo. In NIPS- NIPS-Twwnnty-Fife Annual Conference on Neural Information Processing Systems, 2011.
[3] L. Chen, Li, and M. Qiao. Nearly instance optimal sample complexity bounds for top-k arm selection. In Artificial Intelligence and Statistics, pages 101-110. PMLR, 2017.
[4] J. Cheshire, P. Menard, and A. Carpentier. The influence of shape constraints on the thresholding bandit problem. In Conference on Learning Theory, pages 1228-1275. PMLR, 2020.
[5] de Rooij, T. van Erven, P. Grünwald, and W. M. Koolen. Follow the leader if you can, Hedge if you must. Journal of Machine Learning Research, 15:1281-1316, Apr. 2014.
[6] R. Degenne and W. M. Koolen. Pure exploration with multiple correct answers. In Advances in Neural Information Processing Systems (NeurIPS) 32, pages 14591-14600. Dec. 2019.
[7] R. Degenne, W. M. Koolen, and P. Ménard. Non-asymptotic pure exploration by solving games. In Advances in Neural Information Processing Systems (NeurIPS) 32, pages 14492-14501. Dec. 2019.
[8] E. Even-Dar. S. Mannor, Y. Mansour, and S. Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.
[9] V. Gabillon, M. Ghavamzadeh, and A. Lazaric. Best amm identification: A unified approach to fixed budget and fixed confidence. In W/PS-Twenty-Sitt Annual Conference on Neural Information Processing Systems, 2012.
[10] A. Garivier and E. Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998-1027. PMLR, 2016.
[11] R. Johari, L. Pekelis, and D. J. Walsh. Always valid inference: Bringing sequential analysis to A/B testing. arXiv preprint /5 044222 2015.
[12] S. Kalyanakrishnan, A. Tewari, P. Auer, and Stone. Pac subset selection in stochastic multi-armed bandits. In ICML, volume 12, pages 155-662, 2012.
[13] E. Kaufmann and W. M. Koolen. Mixture martingales revisited with applications to sequential tests and confidence intervals. Preprint, Oct. 2018.
[14] E. Kaufmann, O. Cappé, and A. Garivier. On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17(1): 2016.
[15] Lattimore and Szepesvári. Bandit Algorithms. Cambridge University Press, 2020. doi: 10. 1017/997 10857 1401.
[16] A. Locatelli, M. Gutzeit, and A. Carpentier. An optimal algorithm for the thresholding bandit problem. International Conference on Machine Learning, pages 1690-1698. PMLR, 2016.
[17] B. Mason, L. Jain, A. Tripathy, and R. Nowak. Finding all {c]-good arms stochastic bandits. Advances in Neural Information Processing Systems, 2020.
[18] Yang, A. Ramdas, K. Jamieson, and M. J. Wainwright. A framework for Multi- A(rmed)/B(andit) testing with online FDR control. In Advances in Neural Information Process- ing Systems, 2017.
11


Reviews:
[{"review_id": "lzE3yDSM1kR", "reviewer": "Reviewer_VNse", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\nThe paper derives theoretical results on the sample complexity of the proposed procedure, along with a valid \"risk assessment\" strategy.\n\nOverall, 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:\n\n* It seems too restrictive to assume the same model for all different subpopulations. Is this common in the literature?\n\n* Moreover, it seems very restrictive to assume the same one-parameter exponential family model. \n  (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?\n   (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? \n\n* What does kl(p, q) look like? It would help to have an idea about how this depends on, say, |p-q|.\n\n* Prop 2 was useful. Is it obvious how to order the T^* from various settings?\n\n* 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?\n\n* The application in 4.2 involves time, which is a mismatch with the theory in the paper (which focused on subpopulations). \nSo, I am not sure how much this adds to the paper.\n\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": ".", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "g3zV5HywpPm", "reviewer": "Reviewer_x5R6", "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.\n\nThe 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Positives:\n- The paper demonstrates a firm grasp of the literature upon which it builds, and the algorithmic and proof techniques therein.\n- 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.\n- Including the optimal weight vector and resulting stopping time for the Gaussian case really helps the reader understand the improvements possible in different settings.\n\nAreas for improvement:\n- 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.\n- 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.\n\n\nAdditional comments:\n- 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).\n- Proposition 2, missing a comma in the first line of math before w_{a,i}^\\star.\n- 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).\n\n\nUpdate 8/16:\nI 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. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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?\n\nIt'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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "cuMvDfVaNSH", "reviewer": "Reviewer_4N5J", "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. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- The paper is well-written and the problem is interesting. \n\n- The paper is mathematically rigorous. \n\n- 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. \n\n- 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. \n\n- 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).   \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "JBAIULKxzmp", "reviewer": "Reviewer_KZHw", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "(not an expert in the area so will provide general reviews. please refer to other reviewers on evaluation on the tech details)\nPaper provided a solution to the A/B/n testing problem which is very useful in the industry data analysis\n- Paper constructed a complexity bound and provided algorithm reaching it, constructing an optimal framework\n- Simulation showing superior performance\n- Various parameter models are analysed and they are widely applicable to the real setups\n\nHowever 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

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)