Yoan Russac
email: yoan.russac@ens.fr

Christina Katsimerou
email: christina.katsimerou@booking.com

Dennis Bohle
email: dennis.bohle@booking.com

Olivier Cappé
email: olivier.cappe@cnrs.fr

Aurélien Garivier
email: aurelien.garivier@ens-lyon.fr

Wouter M Koolen
email: wmkoolen@cwi.nl

A/B/n Testing with Control in the Presence of Subpopulations

Motivated by A/B/n testing applications, we consider a finite set of distributions (called arms), one of which is treated as a 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 τ δ is the first time when the strategy ensures that it is able to output the correct answer with probability at least 1δ, then E[τ δ ] grows linearly with log(1/δ) 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.

Introduction

A/B/n testing is a website optimization procedure where multiple versions of the content (called "arms" below) are compared, often in order to find the one with the highest conversion rate. However, many e-commerce companies use A/B/n testing not only to deploy the best product implementation, but primarily to draw post-experiment inferences [START_REF] Johari | Always valid inference: Bringing sequential analysis to A/B testing[END_REF]. The decision-making involves, besides experiment results, factors such as the cost of scaling-up a solution, external data, or whether the implementation fits in a broader theme. In this setting, each of the arms better than the default product (which we will refer to as the "control" arm) is a contender for being deployed and the interest is not only in the best arm.

35th Conference on Neural Information Processing Systems (NeurIPS 2021).

Given the control and K ≥ 1 alternative implementations (variants), the simplest idea is to distribute the traffic uniformly among the arms; the arms that appear to be significantly better than the control at the end of the experiment are considered for deployment. While well-established, this process can be inefficient in 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 a very conservative approach by choosing a 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 [START_REF] Lattimore | Bandit Algorithms[END_REF]). 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 is considered sufficient for every arm. Approaches have been developed in [START_REF] Even-Dar | Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems[END_REF][START_REF] Kalyanakrishnan | Pac subset selection in stochastic multi-armed bandits[END_REF][START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF] for the identification of the single arm with the highest mean, a task called the Best Arm Identification (BAI) problem. In particular, [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF] propose a strategy that is asymptotically optimal in the fixed confidence setting, meaning that, given a risk parameter δ, it finds the best arm with probability at least 1δ, using an expected number of samples that is hardly improvable when δ is small. Later, [START_REF] Yang | A framework for Multi-A(rmed)/B(andit) testing with online FDR control[END_REF] 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, we 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, we address two additional issues.

First, traditional stochastic bandit models are based on the assumption that the arm samples are i.i.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 on 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-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 a pure sequential experiment in that the experimenter cannot always fix a risk δ at the beginning and passively wait for the stopping time of the experiment without any time limitation. To address this issue, [START_REF] Johari | Always valid inference: Bringing sequential analysis to A/B testing[END_REF] proposed to define some notion of sequential "p-values" that can be monitored as the experiment progresses and used to terminate it. This notion was further used in the BAI setting in [START_REF] Yang | A framework for Multi-A(rmed)/B(andit) testing with online FDR control[END_REF]. In this contribution, we elaborate on this idea 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 [START_REF] Even-Dar | Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems[END_REF][START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF], the identification of the top m arms [START_REF] Chen | Nearly instance optimal sample complexity bounds for top-k arm selection[END_REF][START_REF] Kalyanakrishnan | Pac subset selection in stochastic multi-armed bandits[END_REF][START_REF] Gabillon | Best arm identification: A unified approach to fixed budget and fixed confidence[END_REF] identifying the arms that are better than a threshold [START_REF] Locatelli | An optimal algorithm for the thresholding bandit problem[END_REF][START_REF] Cheshire | The influence of shape constraints on the thresholding bandit problem[END_REF], or identifying all -good arms [START_REF] Mason | Finding all { }-good arms in stochastic bandits[END_REF]. As far as we know, this paper is the first to consider the problem of identifying all the arms better than a 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. [START_REF] Locatelli | An optimal algorithm for the thresholding bandit problem[END_REF] propose an algorithm for identifying all arms above a given threshold. Their algorithm samples according to the significance of a 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 is known but its probability distribution is not.

In our work, the quality of the different arms is assessed with a weighted combination of its subpopulations means. Minimizing the estimation error of a convex combination of means through adaptive sampling was considered in [START_REF] Carpentier | Finite-time analysis of stratified sampling for monte carlo[END_REF] 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-theoretic complexity of the problem, extending the lower bound of [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF] 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 1 below. We also consider in detail the Gaussian case which gives rise to more interpretable results. Section 3 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 4.

The complexity of the ABC-S problem 2.1 Mathematical framework

A problem instance consists of the following ingredients. Known to the learner are the number of arms K ≥ 1 in addition to the designated control arm 0, the number of subpopulations J (a standard bandit being J = 1), and the vector β ∈ R J representing the relative importance of the subpopulations for the learning objective. We further make the stochastic assumption that samples from each arm a (including the control) and subpopulation i are drawn i.i.d. from an unknown probability distribution ν a,i on R, whose mean we will denote by µ a,i . The quality of arm a is µ a := J i=1 β i µ a,i the combination of the means of the arms in the different populations. For β ∈ R J we define the ABC-S problem as the correct identification of the set

S β (µ) := a ∈ [K] J i=1 β i µ a,i > J i=1 β i µ 0,i .
At every time step t, the algorithm selects an arm A t based on previous choices and outcomes and observes or selects (except when explicitly specified) the population type I t . Upon the selection of the arm A t a reward X t is obtained. This defines a sigma-field generated by the observations up to time t denoted F t = σ(I 1 , X 1 , . . . , I t , X t ). The number of times arm a was selected for subpopulation i at time t is denoted N a,i (t) := t s=1 1(A s = a, I s = i) and the number of draws of arm a, N a (t) := t s=1 1(A s = a). We define the gap with the control arm and arm a, ∆ a := µ 0µ a .

Modes of interaction

We consider four modes of interaction of the learner with the bandit, as specified in Figure 1 below. In any of the three passive modes of interaction (described in Figures 1b to 1d), we assume that the subpopulation i represents a known proportion α i of the total population, and hence that the sequence of subpopulations is drawn i.i.d. from the fixed and discrete distribution

I t ∼ α = (α 1 , . . . , α J ) with α ∈ Σ J := {x ∈ [0, 1] J | i x i = 1} the J-dimensional simplex.
Here α is an exogenous parameter and can differ from β which is inherent to the learning objective and is also assumed to be known. Although it is most natural in many applications to consider that β = α (it is even necessary in the oblivious mode to make the estimation of the µ a 's feasible), Example 1 below describes a concrete scenario in which β has negative components.

The distributions (ν a,i ) a,i are assumed to belong the same one-parameter exponential family, P := {(ν θ ) θ : dν θ /dξ = exp(θxb(θ))}, with ξ a reference measure on R and b : Θ ⊂ R → R. Every probability distribution ν θ in P is entirely defined by its mean ḃ(θ) [START_REF] Cappé | Kullback-leibler upper confidence bounds for optimal sequential allocation[END_REF]. We may hence identify any bandit instance with its matrix of means µ ∈ R (K+1)×J In addition, the Kullback-Leibler divergence between two distributions ν θ and ν θ ∈ P may be written in the following Bregman form: where µ = ḃ(θ) and µ = ḃ(θ ) correspond to the means of the two distributions ν θ and ν θ . We also use the notation kl(p, q) to denote the KL divergence of two Bernoulli distributions of parameter p and q.

d(µ, µ ) = KL(ν θ , ν θ ) = b(θ ) -b(θ) -ḃ(θ)(θ -θ) ,
We define L := {µ : ∀a ∈ [K] ∪ {0}, ∀i ∈ [J], ν a,i ∈ P and µ 0 = µ a } 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 a risk assessment δt together with a recommendation Ŝt . We focus on safely calibrated policies, that are defined as satisfying the following property ∀µ ∈ L, ∀δ ∈ (0, 1),

P µ ∃t ≥ 1 : Ŝt = S β (µ) ∩ δt ≤ δ ≤ δ . (1)
Finally, when fixing a level of risk δ, we consider the stopping time associated to the filtration F t , τ δ = inf{t ≥ 0, δt ≤ δ}. The objective is then to minimize the expected number of rounds necessary to obtain a level of risk of at most δ. Contrary to usual δ-PAC algorithms if stopped before τ δ , the strategy still provides guarantees on the output set following Equation 1. In particular, safely calibrated policies have a sampling rule that does not depend on any pre-specified δ, and as such they are δ-PAC for any δ.

Example 1 ([Largest Profit Identification problem 13, p24]). Consider a company choosing among K product designs the model to mass produce. Each candidate design k has an (equilibrium) sales price µ k,1 and production cost µ k,2 . The goal is to find the model k with the largest profit µ k,1µ k,2 . Prices and costs are currently unknown, but can be adaptively sampled. Sampling the "price" subpopulation i = 1 is typically implemented by performing user preference studies, taking questionnaires, etc. Samples from the "cost" subpopulation i = 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 β = (1, -1) and α has to be set by the learner.

General form of the sample complexity

Depending on the mode of interaction from Figure 1, the learner has a set of sampling constraints to satisfy, here denoted C and precisely defined in the next section. We define Alt(µ), the different problem instances where the set of arms better than the control differs from that of the instance µ. Formally, Alt β (µ) := {λ ∈ L | S β (λ) = S β (µ)}. This allows us to bound the sample complexity.

Theorem 1. Let δ ∈ (0, 1) and β ∈ R J . For any strategy satisfying Equation 1 and any µ ∈ L, the expected number of rounds for the ABC-S problem for the agnostic, proportional and active mode satisfies:

E µ [τ δ ] ≥ T (µ) kl(δ, 1 -δ) and lim inf δ→0 E µ [τ δ ] ln(1/δ) ≥ T (µ) . (2)
where (recalling that λ a = J i=1 β i λ a,i )

T (µ) -1 = sup w∈C inf λ∈Alt β (µ) K a=0 J i=1 w a,i d(µ a,i , λ a,i ) (3)
= sup

w∈C min b =0 inf λ∈L:λ0=λ b a∈{0,b} J i=1 w a,i d(µ a,i , λ a,i ) . ( 4
)
This result is established in Appendix A. T characterizes the difficulty of the learning problem.

Influence of the mode of interaction

We consider the four different modes governing the sampling rule as outlined in Figure 1. In the agnostic mode (Fig. 1c) an arm is first selected, after which the subpopulation type is observed. Mathematically, this brings the equality E µ [N a,i (T )] = α i E µ [N a (T )] established in Lemma 2 and the independence constraint on the weights w ∈ C agnostic := {w a,i = α i u a : (u 0 , . . . , u K ) ∈ Σ K+1 }.

In the proportional mode (Fig. 1b), A t is chosen based on F t-1 and the current subpopulation I t .

Here, the constraint is that the total number of pulls of the different arms in the subpopulation i should respect the frequency of this subpopulation, i.e. a E µ [N a,i (T )] = α i T . This induces a marginal constraint on the weights of the form w ∈ C prop := {w ∈ Σ (K+1)J | ∀i ≤ J, a w a,i = α i }. This result is established in Lemma 3 reported in Appendix B.

In the active mode (Fig. 1a), the learner has an additional degree of freedom-she can ask for any subpopulation type at any round. In that case, w ∈ C active := Σ (K+1)J is unconstrained.

By remarking that C agnostic ⊂ C prop ⊂ C active , and given the optimization program (3) solved to obtain the characteristic time, one immediately gets

∀µ ∈ L, T active (µ) ≤ T proportional (µ) ≤ T agnostic (µ) . (5)
Hence, as expected, the more control/information on 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 α = β. In that case, the arm rewards follow a mixture distribution:

X t |A t = a ∼ J i=1 α i ν a,i .
In Proposition 4 reported in Appendix B.3, we properly define the characteristic time of an oblivious safely calibrated policy and prove that the joint convexity of Kullback-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 α = β,

∀µ ∈ L, T active (µ) ≤ T proportional (µ) ≤ T agnostic (µ) ≤ T oblivious (µ) . (6)
Note that although we provide, in Section 3, algorithms to numerically compute the first three complexites, evaluating T oblivious (µ) 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 single-population 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).

Single population and relationship with best arm identification

In order to illustrate the nature of the the ABC-S problem, we make a detour through the single population case, that is, when J = 1. Given two weights w a , w b and two means µ a , µ b , we introduce the minimum weighted transportation cost for moving the means to a common position.

d mid (w a , µ a , w b , µ b ) := inf v w a d(µ a , v) + w b d(µ b , v) = w a d(µ a , v a,b ) + w b d(µ b , v a,b )
where v * a,b , the optimal common location, is the weighted average

, i.e. v * a,b = wa wa+w b µ a + w b wa+w b µ b .
Constructing an instance in the alternative When identifying all the arms better than a control, there are two different ways to obtain a close-by bandit model λ in the alternative. The first option consists in taking an arm which does not belong to S β (µ) 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 µ 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 1 in Appendix A.2).

There is a priori no link between a BAI problem and an ABC one. In particular, in the BAI problem there are only K + 1 possible choices for the best arm while when looking for S β (µ) there are up to 2 K different sets to consider. Yet, the next proposition shows that the characteristic time T of any ABC problem with J = 1 subpopulation shares strong similarities with that of BAI problems. Proposition 1. Let δ ∈ (0, 1) and µ ∈ L. For any strategy satisfying Equation 1, Equation 2 holds with

T (µ) -1 = sup w∈Σ K+1 inf λ∈Alt β (µ) K a=0 w a d(µ a , λ a ) = sup w∈Σ K+1 min b =0 d mid (w 0 , µ 0 , w b , µ b ) .
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 3]) except that we consider all the indices different from the control here instead of the indices different from the best arm.

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 to further investigate the differences between the various modes of interaction. We will state our results for the heteroscedastic case, in particular to get a closed-form proxy for the Bernoulli case, where each variance is a function of the (unknown) mean.

A/B testing When K = 1 (one arm and the control arm), we are considering a standard A/B test with subpopulations and one can easily prove the following result (established in Appendix C). Proposition 2. For any µ ∈ L with K = 1 and ν a,i = N (µ a,j , σ 2 a,j ) one has

1. T agnostic (µ) = 2 J i=1 β 2 i σ 2 0,i α i + J i=1 β 2 i σ 2 1,i α i 2 ∆ 2 1 and w a,i = αi J i=1 β 2 i σ 2 a,i α i J i=1 β 2 i σ 2 0,i α i + J i=1 β 2 i σ 2 1,i α i 2. T prop (µ) = 2 J i=1 β 2 i α i (σ0,i+σ1,i) 2 ∆ 2 1 and ∀i ≤ J, ∀a ∈ {0, 1}, w a,i = αiσa,i σ0,i+σ1,i 3. T active (µ) = 2( J i=1 |βi|(σ0,i+σ1,i)) 2 ∆ 2 1 and ∀i ≤ J, ∀a ∈ {0, 1}, w a,i = |βi|σa,i J i=1 |βi|(σ0,i+σ1,i)
The optimal allocations in the agnostic and proportional cases are constrained by the proportion of the different subpopulations α, whereas, for the active mode, the optimal weights only depend on β. In general, the optimal weights also depend on the subpopulation variances, as is well-known in stratified sampling estimation. Note however, that when (a) the subpopulations all have a common variance σ 2 and (b) β = α, then the optimal allocations and the characteristic times are equal for the agnostic, the proportional and the active modes. In that case, w a,i = α i /2, which also corresponds to the well-known result in Gaussian A/B testing [START_REF] Kaufmann | On the complexity of best-arm identification in multi-armed bandit models[END_REF]. 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 variances are equal to σ 2 , the active mode remains very attractive in the cases where β = α. 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 σ 2 , letting (u 0 , . . . , u

K ) = argmax u∈Σ K+1 min b =0 ∆ 2 b 2 1 u 0 + 1 u b
, the optimal weights for the active mode satisfy

∀a ∈ {0, . . . , K}, ∀i ≤ J, w a,i = u a |β i | J i=1 |β i | .
If, in addition α = β, the above also holds for the agnostic and the proportional modes.

The interesting part of Proposition 3 is that computing (u 0 , . . . , u K ) can be done efficiently using Theorem 5 from [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF]. The optimal weights of the ABC-S problem can be deduced from u without any further calculation.

Algorithms

To obtain our algorithms, we instantiate the Track-and-Stop algorithm template to our ABC-S problem. Garivier and Kaufmann [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF] introduced Track-and-Stop and proved its asymptotic optimality in the BAI setting. Asymptotic optimality for general partition identification problems was subsequently established by Kaufmann and Koolen [START_REF] Kaufmann | Mixture martingales revisited with applications to sequential tests and confidence intervals[END_REF]Theorem 23] under the assumption of continuity of the oracle weights µ → w * (µ). Degenne and Koolen [START_REF] Degenne | Pure exploration with multiple correct answers[END_REF] show that the continuity assumption holds for all single-answer problems, in the upper-hemicontinuity 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. [START_REF] Degenne | Non-asymptotic pure exploration by solving games[END_REF] interpret T-a-S as a noisy sequential equilibrium computation for the max-min problem from the lower bound (e.g. Equation 3) and develop computationally attractive variants including lazy iterative solution of the w * problem, and optimistic gradients instead of forced exploration.

The details of our implementation are given in Appendix F. In short, we use the simple standard Θ( √ t) forced exploration rounds, a mode/subpopulation aware upgrade of the D-tracking scheme [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF] (which is empirically superior to C-tracking) and we approximately and incrementally compute the oracle weights using the AdaHedge vs Best Response iterative saddle point solver from [START_REF] Degenne | Non-asymptotic pure exploration by solving games[END_REF]. We use one single learner, instead of one per possible answer, as advocated in [7, Section 4]. Note that we are not affected by the non-convergence of D-tracking from [7, Appendix E], as our problem has a unique w * because it is strictly concave in w (see Appendix E).

The sampling rule The high level overview of the algorithm is as follows. We are given the number of arms K and subpopulations J, the exponential family, the mode of interaction, the subpopulation importance coefficients β and, for passive modes, their natural frequencies α. The algorithm then proceeds in rounds t = 1, 2, . . . Each round t, it calculates the empirical frequencies μt ∈ R (K+1)×J given by μa,i (t) = 1 Na,i(t) t s=1 X s 1 {A s = a, I s = i}. It then computes (a suitable approximation of) the maximiser (i.e. the oracle policy) w t = w * ( μt ) ∈ Σ (K+1)×J of problem (2). In the active mode, we "D-track" w t , i.e. we sample (A t , I t ) ∈ argmax a,i N a,i (t -1)tw t (a, i). In the proportional mode, the subpopulation I t is given and we "D-track" the conditional distribution of w t on arms given the subpopulation, i.e. A t ∈ argmax a N a,It (t -1)tα It w t (a|I t ), where w t (a, i) = α i w t (a|i). In the agnostic mode we "D-track" the marginal distribution of w t on arms, i.e. A t ∈ argmax a N a (t -1)tw t (a). For each mode, this sampling strategy ensures that N a,i (t) ≈ tw t (a, i) ≈ tw * a,i (µ), thus driving down the reported level of confidence as quickly as possible given the lower bound from Theorem 1.

The recommendation Concluding each round, we recommend S β ( μt ) at confidence level δ(t) = min {δ ∈ (0, 1)|Λ(t) ≥ β(t, δ)} obtained by inverting the threshold β(t, δ) at the GLR statistic

Λ(t) = min b =0 inf λ∈L:λ0=λ b a∈{0,b} J i=1 N a,i (t)d(μ a,i (t), λ a,i ) . ( 7
)
The threshold For the sharpest theoretically supported thresholds we refer to [START_REF] Kaufmann | Mixture martingales revisited with applications to sequential tests and confidence intervals[END_REF]. Namely, an ABC-S problem with K-arms and J-subpopulations has 2 K answers, and its rank [13, Definition 22] is 2J, as can be read off from [START_REF] Cheshire | The influence of shape constraints on the thresholding bandit problem[END_REF]. By [13, Proposition 23] we have validity for β(t, δ) = 6J ln ln t + ln

1 δ + K + 2J • O(ln ln 1 δ ).
In practice, we follow [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF] and use instead the heavily stylized ln((1 + ln t)/δ) that omits several union bounds. Theorem 2. For every mode, Subpopulation Track-and-Stop is safely calibrated (Equation 1). Moreover, Subpopulation Track-and-Stop is asymptotically optimal and matches the lower bound from Theorem 1, in the sense that

for every bandit µ ∈ L, lim δ→0 E[τ δ ] ln(1/δ) = T (µ) .
We include the proof in Appendix E.

Experiments

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 to 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 [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF], adapted to the ABC problem and denoted BC-ABC in the sequel. BC [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF] for the BAI problem samples in every round the empirical best arm ât or its best challenger, i.e. the arm ĉt = ât 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), in the agnostic interaction mode (since Λ(t) is subpopulation independent). For clearer comparison between the sampling strategies, all algorithms use the Chernoff stopping criterion [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF] to determine either when to stop or output the risk assessment at a given time. We also opted for sampling rules independent from the confidence parameter δ, because we are aiming for safely calibrated policies.

We first illustrate the fact that the T-a-S algorithm provides a correct -but rather conservativeassessment of the risk of its decision whatever the time it is stopped at. To do so, we generated 1000 bandit instances uniformly at random from [0, 1] with K = 2 arms. For each instance, we recorded the first time a certain risk assessment level is reached and the correctness of the algorithm's 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 [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF]. Figure 2 (Left) illustrates the isotonic curve fitted on our observations and suggests that even the most lenient stopping threshold ln((ln(t) + 1)/δ) results in much lower empirical probability of error than the risk assessment. In the following, we use the stopping threshold ln((ln(t) + 1)/δ). In our second experiment1 , we generated 3000 Bernoulli bandit instances with K = 2 and a random number of subpopulations J between 2 and 10. Each subpopulation-arm's mean µ a,i is drawn uniformly at random from [0, 1], and the subpopulation frequency vector α is drawn from a Dirichlet(10) distribution. Table 1 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. To better understand the role of β and α, we ran the algorithms on a specific model (see Figure 2, Right) with α = β. 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 kl(δ, 1δ)T * (µ), and with a more practical version, which indicates, approximately, the first time at which the GLR statistic crosses the threshold, i.e. solving t = ln((ln(t) + 1)/δ)T * (µ), as was done in [START_REF] Degenne | Non-asymptotic pure exploration by solving games[END_REF]. All adaptive algorithms perform well on this instance, with their average runtime being very close to their respective practical bound.

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 a 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 to one of the variants. For this setup we 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 a day, as seen in Figure 3a, in which every point corresponds to click-through rate per six hours (quarter of day) for 12 consecutive days. We treat the J = 4 seasons as i.i.d. subpopulations. Within each season we shuffled the data to 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. Note that the small gaps between the arm means makes this practical ABC-S problem much harder than the synthetically generated examples.

We tested all algorithms described in Section 4.1. Each algorithm terminates when it reaches for the first time δt ≤ 0.1 or outputs a risk assessment on the recommendation if it runs out of samples, which in this experiment occurs after 1.4•10 7 observations. Here, we weigh the importance β of each season equally to its observed frequency α. 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 G). The observations from Fig. 3b are 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 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 it 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 it 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 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 to methods and, as such, do not have a 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 are used to 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 or even oblivious) may become necessary in order to prevent undue use of population-dependent information.

A General form of the characteristic time

A.1 Proof of Theorem 1 Theorem 1. Let δ ∈ (0, 1) and β ∈ R J . For any strategy satisfying Equation 1 and any µ ∈ L, the expected number of rounds for the ABC-S problem for the agnostic, proportional and active mode satisfies:

E µ [τ δ ] ≥ T (µ) kl(δ, 1 -δ) and lim inf δ→0 E µ [τ δ ] ln(1/δ) ≥ T (µ) . ( 2
)
where (recalling that λ a = J i=1 β i λ a,i )

T (µ) -1 = sup w∈C inf λ∈Alt β (µ) K a=0 J i=1 w a,i d(µ a,i , λ a,i ) (3)
= sup

w∈C min b =0 inf λ∈L:λ0=λ b a∈{0,b} J i=1 w a,i d(µ a,i , λ a,i ) . ( 4
)
Proof. Using the transportation lemma from [START_REF] Kaufmann | On the complexity of best-arm identification in multi-armed bandit models[END_REF] and recalling that N a,i (t) is the number of draws of arm a in subpopulation i up to time t, we have for any safely calibrated policies

∀λ ∈ Alt β (µ), J i=1 K a=0 E µ [N a,i (τ δ )]d(µ a,i , λ a,i ) ≥ kl(δ, 1 -δ) .
Therefore,

kl(δ, 1 -δ) ≤ inf λ∈Alt β (µ) K a=0 J i=1 E µ [N a,i (τ δ )]d(µ a,i , λ a,i ) = E µ [τ δ ] inf λ∈Alt β (µ) K a=0 J i=1 E µ [N a,i (τ δ )] E µ [τ δ ] d(µ a,i , λ a,i ) ≤ E µ [τ δ ] sup w∈C inf λ∈Alt β (µ) K a=0 J i=1
w a,i d(µ a,i , λ a,i ) .

In the last inequality, we used the fact that the normalized expected numbers of draws satisfy the set of constraints defined by C ⊂ Σ (K+1)J . Using kl(δ, 1δ) ∼ ln(1/δ) when δ tends to 0 gives the first result.

We denote Λ(w, λ, µ) := K a=0 J i=1 w a,i d(µ a,i , λ a,i ). To obtain the second result, we will simplify the expression of T (µ) -1 . Using that the KL divergences and the weights are positive, for λ to be in the alternative, one of the two following conditions need to be met: (1) there exists a ∈ S β (µ) such that λ a < λ 0 . (2) there exists a ∈ S -

β (µ) := {a ∈ [K] | µ a < µ 0 } such that λ a > λ 0 .
For this reason, one has

inf λ∈Alt β (µ) Λ(w, λ, µ) = min   min a∈S β (µ) inf λ:λa<λ0 Λ(w, λ, µ), min a∈S - β (µ) inf λ:λa>λ0 Λ(w, λ, µ)   .
We obtain the desired result by remarking that the inner optimization programs inf λ are each achieved on the boundary (the constraint being satisfied with equality) where they coincide, and that {1, . . . , K} = S β (µ) ∪ S - β (µ).

A.2 Proof of Proposition 1

In the particular case when J = 1, the expression of the characteristic time can be simplified.

Proposition 1. Let δ ∈ (0, 1) and µ ∈ L. For any strategy satisfying Equation 1, Equation 2 holds with

T (µ) -1 = sup w∈Σ K+1 inf λ∈Alt β (µ) K a=0 w a d(µ a , λ a ) = sup w∈Σ K+1 min b =0 d mid (w 0 , µ 0 , w b , µ b ) .
Proof. The first part of the proof can be obtained using similar argument than for Theorem 1. The missing part is the simplification of the expression of T (µ).

We denote Λ(w, λ, µ) := K a=0 w a d(µ a , λ a ). Following the reasoning from the proof of Theorem 1 one of the two following conditions needs to be met: (1) there exists a ∈ S β (µ) such that λ a < λ 0 .

(2) there exists a ∈ S -

β (µ) := {a ∈ [K] | µ a < µ 0 } such that λ a > λ 0 . For this reason, one has inf λ∈Alt β (µ) Λ(w, λ, µ) = min   min a∈S β (µ) inf λ:λa<λ0 Λ(w, λ, µ), min a∈S - β (µ) inf λ:λa>λ0 Λ(w, λ, µ)   .
In this simpler case, it is possible to obtain an explicit formula for this infimum. We start from

T (µ) -1 = sup w∈Σ K+1 min   min a∈S β (µ) inf λ:λa<λ0 Λ(w, λ, µ), min a∈S - β (µ) inf λ:λa>λ0 Λ(w, λ, µ)   .
Let us focus on the case, λ a < λ 0 and fix an index a ∈ S β (µ). Λ is always smaller when all the λ b for b = 0 and b = a coincides with µ b . This gives,

min a∈S β (µ) inf λ:λa<λ0 Λ(w, λ, µ) = min a∈S β (µ) inf λ:λa≤λ0 w 0 d(µ 0 , λ 0 ) + w a d(µ a , λ a ) .
We consider the Lagrangian function, L(λ 0 , λ a , q) = w 0 d(µ 0 , λ 0 ) + w a d(µ a , λ a ) + q(λ aλ 0 ). Differentiating with respect to λ 0 and λ a brings the condition

λ 0 = λ a = λ a,0 = argmin λ w 0 d(µ 0 , λ) + w a d(µ a , λ) = w 0 w 0 + w a µ 0 + w a w 0 + w a µ a .
Solving the optimization program for a ∈ S - β (µ) and under the constraint λ a > λ 0 , gives the exact same set of constraints and optimal solution, i.e.

min a∈S - β (µ) inf λ:λa>λ0 Λ(w, λ, µ) = min a∈S - β (µ) d mid (w 0 , µ 0 , w a , µ a ) . (9)
Bringing Equation 8and Equation 9together and remarking that [K] = S β (µ) ∪ S - β (µ) gives the announced result.

A.3 Link between ABC and BAI

In the particular case, of Gaussian distributions with a known variance σ 2 , for any µ ∈ L, one can easily create a BAI instance with the same characteristic time as T (µ). Lemma 1. Let µ ∈ L where all the arms are Gaussian distributions with known variance σ 2 . Let µ 0 be the mean of the control arm. We define µ as follows

µ k = 2µ 0 -µ k if µ k > µ 0 µ k otherwise.
By denoting T BAI (µ) the characteristic time for the BAI problem with a bandit instance µ, then one has T (µ) = T BAI ( µ) .

Proof. In the particular case of Gaussian distributions with known variance σ 2 , easy calculation brings

T (µ) -1 = sup w∈Σ K+1 min b =0 d mid (w 0 , µ 0 , w b , µ b ) = min b =0 (µ 0 -µ b ) 2 2 ((1 -α b ) 2 w 0 + α 2 b w b )
with α b = w0 w b +w0 . On the instance μ, first note that μ0 is the best arm by construction. For an index k such that µ k > µ 0 , one has

μ0 -μk = µ 0 -(2µ 0 -µ k ) = µ k -µ 0 > 0 . For this reason, ∀k ∈ [K], μ0 > μk . Using Lemma 3 from [10], by defining I γ (µ 1 , µ 2 ) := γd(µ 1 , γµ 1 + (1 -γ)µ 2 ) + (1 -γ)d(µ 2 , γµ 1 + (1 -γ)µ 2 ), one has T BAI ( µ) = sup w∈Σ K+1 min b =0 (w 0 + w b )I w 0 w 0 +w b (µ 0 , µ b ) .
Furthermore, letting α b = w 0 /(w 0 + w b ):

(w 0 + w b )I α b (µ 0 , µ b ) = (w 0 + w b ) α b (1 -α b ) 2 (µ 0 -µ b ) 2 2σ 2 + (1 -α b ) α 2 b (µ 0 -µ b ) 2 2σ 2 = (µ 0 -µ b ) 2 2σ 2 (1 -α b ) 2 w 0 + α 2 b w b .
Plugging this in the expression of T BAI ( µ) gives the announced result.

B Results for specific modes of interaction

B.1 Agnostic mode Lemma 2. For any agnostic policy where A t is chosen knowing F t-1 but independently from I t , when defining N a,j (t) =

t s=1 1(A s = a ∩ I s = j) and N a (t) = t s=1 1(A s = a), then ∀a ∈ {0, . . . , K}, ∀j ∈ {1, . . . , J}, ∀t ≥ 1, E µ [N a,j (t)] = α j E µ [N a (t)] Proof. E µ [N a,j (t)] = t s=1 P(A s = a ∩ I s = j) = t s=1 P µ (A s = a|I s = j)P(I s = j) = t s=1 α j P µ (A s = a|I s = j) = t s=1 α j P µ (A s = a) = α j E µ [N a (t)] ,
where in the third equality, we have used that the action A t is selected independently from the population indicator I t .

B.2 Proportional mode

Lemma 3. For any proportional policy where A t is chosen knowing F t-1 and I t , when defining

N a,j (t) = t s=1 1(A s = a ∩ I s = j) and N a (t) = t s=1 1(A s = a), then ∀j ∈ {1, . . . , J}, ∀t ≥ 1, K a=0 E µ [N a,j (t)] = α j t . Proof. K a=0 E µ [N a,j (t)] = t s=1 K a=0 E µ [1(I s = j)1(A s = a)] = t s=1 E µ 1(I s = j) K a=0 1(A s = a) = t s=1 P µ (I s = j) = α j t .

B.3 Oblivious mode

In the oblivious mode, the subpopulations can not be observed by the learner. In this case, we have

1. E [X t |A t = a] = J i=1 α i µ a,i , 2. X t |A t = a ∼ J i=1 α i ν a,i .
While with observable subpopulations the distributions are entirely characterized by their means, this is no longer the case with mixture distributions. In particular, this requires defining a different alternative.

Alt(ν) := {ν : ∀a, ν a = J i=1 α i ν a,i with ν a,i ∈ P and S(ν ) = S(ν) } . Proposition 4. Let δ ∈ (0, 1) and β ∈ R J . For any oblivious strategy satisfying Equation 1 and any µ ∈ L, the characteristic time satisfies

E µ [τ δ ] ≥ T oblivious (µ) kl(δ, 1 -δ) and lim inf δ→0 E µ [τ δ ] ln(1/δ) ≥ T oblivious (µ) .
where

T oblivious (µ) -1 = sup w∈Σ K+1 inf ν ∈ Alt(ν) K a=0 w a KL J i=1 α i ν a,i , J i=1 α i ν a,i . (10)
Furthermore, ∀µ ∈ L, T oblivious (µ) ≥ T agnostic (µ) .

Proof. Using the transportation lemma from [START_REF] Kaufmann | On the complexity of best-arm identification in multi-armed bandit models[END_REF] we have for any safely calibrated oblivious policy

∀ν ∈ Alt(ν), K a=0 E µ [N a (τ δ )]KL J i=1 α i ν a,i , J i=1 α i ν a,i ≥ kl(δ, 1 -δ) .
Therefore,

kl(δ, 1 -δ) ≤ inf ν ∈Alt(ν) K a=0 E µ [N a (τ δ )]KL J i=1 α i ν a,i , J i=1 α i ν a,i = E µ [τ δ ] inf ν ∈Alt(ν) K a=0 E µ [N a (τ δ )] E µ [τ δ ] KL J i=1 α i ν a,i , J i=1 α i ν a,i ≤ E µ [τ δ ] sup w∈Σ K+1 inf ν ∈Alt(ν) K a=0 w a KL J i=1 α i ν a,i , J i=1 α i ν a,i .
Using kl(δ, 1δ) ∼ ln(1/δ) when δ tends to 0 gives the first result.

Using the joint convexity of the KL divergence one gets

KL J i=1 α i ν a,i , J i=1 α i ν a,i ≤ J i=1 α i KL(ν a,i , ν a,i ) .
Assuming that the mean of ν a,i = λ a,i and recalling that for distributions in P, one has KL(ν a,i , ν a,i ) = d(µ a,i , λ a,i ), we deduce,

T oblivious (µ) -1 = sup w∈Σ K+1 inf ν ∈ Alt(ν) K a=0 w a KL J i=1 α i ν a,i , J i=1 α i ν a,i ≤ sup w∈Σ K+1 inf λ∈ Alt(µ) K a=0 J i=1 α i w a d(µ a,i , λ a,i ) = T agnostic (µ) -1 .
Except in the case of Bernoulli distributions -where the mixture is also a Bernoulli distribution-, finding a strategy that matches T oblivious (µ) -1 is a hard task. However, one may use the following lemma to treat the mixture in a sub-optimal way, based on the fact that it exhibits sub-gaussian behavior.

Lemma 4 (Sub-gaussianity of mixture). For each µ ∈ R, assume that ν µ is a distribution on R with mean E X∼νµ [X] = µ that is σ 2 -sub-Gaussian, meaning that E X∼νµ e λ(X-µ) ≤ e σ 2 λ 2 /2 for any λ ∈ R. Further let α(µ) be a prior on µ with mean m that is itself η 2 -sub-Gaussian, meaning that

E µ∼α e λ(µ-m) ≤ e λ 2 η 2 /2 . Then the mixture distribution Q = E µ∼α [ν µ ] is σ 2 + η 2 sub-Gaussian.
Proof. The mixture distribution obviously has mean

E X∼Q [X] = m and E X∼Q e λ(X-m) = E µ∼α e λ(µ-m) E X∼νµ e λ(X-µ) ≤ E µ∼α e λ(µ-m) e σ 2 λ 2 /2 ≤ e (σ 2 +η 2 )λ 2 /2 .
In particular, if α is supported on [±M ], then α is M 2 sub-Gaussian, and hence

Q is (σ 2 + M 2 ) sub-Gaussian.
C Optimal allocations in the Gaussian case for K = 1 (A/B testing) Lemma 5. When K = 1 with Gaussian distributions such that ν a,i = N (µ a,i , σ 2 a,i ) the following holds

inf λ:λ0=λ1 J i=1 w 0,i d(µ 0,i , λ 0,i ) + J i=1 w 1,i d(µ 1,i , λ 1,i ) = ∆ 2 1 2 J i=1 β 2 i σ 2 0,i w0,i + σ 2 1,i w1,i
.

Proof. One has for b ∈ {0, 1},

d(µ b,i , λ b,i ) = (λ b,i -µ b,i ) 2 2σ 2 b,i
.

Using the result from Theorem 1 for the case K = 1, the following holds

inf λ∈Alt β (µ) 1 a=0 J i=1
w a,i d(µ a,i , λ a,i ) = min λ∈L:λ0=λ1

1 a=0 J i=1
w a,i d(µ a,i , λ a,i ) .

We introduce

L(λ 0 , λ 1 , q) = J i=1 w 0,i (λ 0,i -µ 0,i ) 2 2σ 2 0,i + J i=1 w 1,i (λ 1,i -µ 1,i ) 2 2σ 2 1,i + q J i=1 β i (λ 0,i -λ 1,i ) .
One has, min λ∈L:λ0=λ1

1 a=0 J i=1 w a,i d(µ a,i , λ a,i ) = sup q∈R inf λ∈L L(λ 0 , λ 1 , q) .
Differentiating with respect to λ 0,i and λ 1,i brings the conditions

λ 0,i = µ 0,i - qβ i σ 2 0,i w 0,i and λ 1,i = µ 1,i + qβ i σ 2 1,i w 1,i .
Plugging these values back in L gives the function

f (q) = - q 2 2 J i=1 β 2 i σ 2 0,i w 0,i + σ 2 1,i w 1,i + q J i=1 β i (µ 0,i -µ 1,i ) .
Easy calculations show that the maximum of the function f is attained for

q = J i=1 β i (µ 0,i -µ 1,i ) J i=1 β 2 i σ 2 0,i w0,i + σ 2 1,i w1,i
.

Plugging this value back in the expression of f ,

f (q ) = ∆ 2 1 2 J i=1 β 2 i σ 2 0,i w0,i + σ 2 1,i w1,i
.

Proposition 2. For any µ ∈ L with K = 1 and ν a,i = N (µ a,j , σ 2 a,j ) one has

1. T agnostic (µ) = 2 J i=1 β 2 i σ 2 0,i α i + J i=1 β 2 i σ 2 1,i α i 2 ∆ 2 1 and w a,i = αi J i=1 β 2 i σ 2 a,i α i J i=1 β 2 i σ 2 0,i α i + J i=1 β 2 i σ 2 1,i α i 2. T prop (µ) = 2 J i=1 β 2 i α i (σ0,i+σ1,i) 2 ∆ 2 1
and ∀i ≤ J, ∀a ∈ {0, 1}, w a,i = αiσa,i σ0,i+σ1,i

3. T active (µ) = 2( J i=1 |βi|(σ0,i+σ1,i)) 2 ∆ 2 1 and ∀i ≤ J, ∀a ∈ {0, 1}, w a,i = |βi|σa,i J i=1 |βi|(σ0,i+σ1,i)
Proof.

Agnostic mode From the Lemma 2, we have w ∈ C agnostic implies w a,i = α i u a with (u 0 , . . . , u K ) ∈ Σ K+1 . For this reason,

T agnostic (µ) -1 = sup
w = argmin u:u0+u1=1 J i=1 β 2 i α i σ 2 0,i u 0 + σ 2 1,i u 1 .
We let c a := J i=1

β 2 i σ 2 a,i
αi for a ∈ {0, 1}. Plugging u 1 = 1u 0 in the previous expression and differentiating with respect to u 0 brings the condition

u 2 0 + 2u 0 c 0 c 1 -c 0 - c 0 c 1 -c 0 .
Solving this polynomial and using that u ∈ Σ 2 gives the unique solution

u 0 = √ c 0 √ c 0 + √ c 1 .
Implying,

w 0,i = α i J i=1 β 2 i σ 2 0,i αi J i=1 β 2 i σ 2 0,i αi + J i=1 β 2 i σ 2 1,i αi and w 1,i = α i J i=1 β 2 i σ 2 1,i αi J i=1 β 2 i σ 2 0,i αi + J i=1 β 2 i σ 2 1,i αi .
With those values,

T agnostic (µ) = 2 J i=1 β 2 i σ 2 0,i αi + J i=1 β 2 i σ 2 1,i αi 2 ∆ 2 1 .
Proportional mode Following the same line of proof, gives

T prop (µ) -1 = sup w∈Cprop ∆ 2 1 2 J i=1 β 2 i σ 2 0,i w0,i + σ 2 1,i w1,i
.

The main difference is now on the constraints on the weights. In the proportional mode, following Lemma 3, ∀i ≤ J, 1 a=0 w a,i = α i . We consider the Lagrangian function:

L(w 0 , w 1 , q 1 , . . . , q J ) = J i=1 β 2 i σ 2 0,i w 0,i + σ 2 1,i w 1,i + J i=1 q i   a∈{0,1} w a,i -α i   .
Differentiating with respect to w 0,i and w 1,i gives the constraints:

-β 2 i σ 2 0,i w 2 0,i + q i = 0 and -β 2 i σ 2 1,i w 2 1,i
+ q i = 0 .

From which we can deduce w 0,i σ 0,i = w 1,i σ 1,i .

From w 0,i + w 1,i = α i , we deduce,

q i = β 2 i (σ 0,i + σ 1,i ) 2 α 2 i .
Plugging this value in the first constraint gives w 0,i = α i σ 0,i σ 0,i + σ 1,i and w 1,i = α i σ 1,i σ 0,i + σ 1,i .

Using those weights,

T prop (µ) = 2 J i=1 β 2 i αi (σ 0,i + σ 1,i ) 2 ∆ 2 1 .
Active mode Following the proof of Proposition 2, one has

T active (µ) -1 = sup w∈Σ (K+1)J ∆ 2 1 2 J i=1 β 2 i σ 2 0,i w0,i + σ 2 1,i w1,i . (11)
Using the constraint w ∈ Σ (K+1)J , one gets

w 1,J = 1 - a={0,1} J-1 i=1 w a,i -w 0,J . (12)
We need to minimize the function (where w 1,J has been replaced by the expression from Equation 12)

f (w) = a={0,1} J-1 i=1 β 2 i σ 2 a,j w a,j + β 2 J σ 2 0,J w 0,J + β 2 J σ 2 1,J 1 - 1 a=0 J-1
i=1 w a,iw 0,J .

For i ≤ J -1, taking the derivative with respect to w 0,i and w 1,i gives the following constraints

β 2 i σ 2 0,i 1 - 1 a=0 J-1 i=1 w a,i -w 0,J 2 = β 2 J σ 2 1,J w 2 0,i , β 2 j σ 2 1,i 1 - 1 a=0 J-1 i=1 w a,i -w 0,J 2 = β 2 J σ 2 1,J w 2 1,i .
From which we deduce ∀i ≤ J -1,

w 0,i σ 0,i = w 1,i σ 1,i . (13)
Differentiating with respect to w 1,J gives σ 0,J 1 -

1 a=0 J-1 i=1
w a,iw 0,J = σ 1,J w 0,J .

Rearranging and using Equation 13gives,

w 0,J = σ 0,J σ 0,J + σ 1,J - J-1 i=1 w 0,i σ 0,i σ 0,i + σ 1,i σ 0,J + σ 1,J σ 0,J . (14)
Using Equation 13and Equation 14, we define the function

g(w 0,1 , . . . , w 0,J-1 ) = J-1 i=1 β 2 i σ 0,i w 0,i (σ 0,i + σ 1,i ) + β 2 J (σ 0,J + σ 1,J ) 2 1 - J-1 i=1 w0,i(σ0,i+σ1,i) σ0,i
.

Differentiating with respect to w 0,i for i

≤ J -1 brings ∀i ≤ J -1, |β i |σ 0,i σ 0,J + σ 1,J 1 - J-1 i=1 w 0,i σ 0,i (σ 0,i + σ 1,i ) = |β J |w 0,i . (15)
Multiplying both sides of this equation by (σ 0,i + σ 1,i )/σ 0,i and summing for i ≤ J -1,

J-1 i=1 w 0,i σ 0,i (σ 0,i + σ 1,i ) = J-1 i=1 |β i |(σ 0,i + σ 1,i ) J i=1 |β i |(σ 0,i + σ 1,i )
.

Plugging this value back in Equation 15 one has:

∀i ≤ J -1, w 0,i = |β i |σ 0,i J i=1 |β i |(σ 0,i + σ 1,i )
.

From Equation 13, we deduce,

∀i ≤ J -1, w 1,i = |β i |σ 1,i J i=1 |β i |(σ 0,i + σ 1,i )
.

We obtain the value of w 0,J using Equation 14 and that of w 1,J using Equation 12. Plugging those weights in the expression given by Equation 11 yields the characteristic time.

D General form of the optimal allocation in the Gaussian case Proposition 3 (Efficient computation in the Gaussian case). With Gaussian distributions with a known variance σ 2 , letting (u 0 , . . . , u

K ) = argmax u∈Σ K+1 min b =0 ∆ 2 b 2 1 u 0 + 1 u b
, the optimal weights for the active mode satisfy ∀a ∈ {0, . . . , K}, ∀i ≤ J, w a

,i = u a |β i | J i=1 |β i | .
If, in addition α = β, the above also holds for the agnostic and the proportional modes.

Proof. From Lemma 5, when the distribution are Gaussian with a known variance σ 2 one has

T active (µ) -1 = sup w∈Σ (K+1)J min b =0 ∆ 2 1 2 J i=1 β 2 i σ 2 w0,i + σ 2 w b,i
.

Using the same continuity argument than in [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF], we know that the supremum of w is attained and is indeed a maximum. Let

Λ b (v, w) := ∆ 2 b 2 J i=1 β 2 i σ 2 vi + σ 2 wi . Then max w∈Σ (K+1)J min b =0 Λ b (w 0 , w b ) = max u∈Σ K+1 ∀a, J i=1 wa,i=ua min b =0 Λ b (w 0 , w b ) = max u∈Σ K+1 max w∈Σ (K+1)J ∀a, i wa,i=ua min b =0 Λ b (w 0 , w b ) ≤ max u∈Σ K+1 min b =0 max w∈Σ (K+1)J ∀a, i wa,i=ua Λ b (w 0 , w b ) (Max-min inequality) . Let b = 0, max w∈Σ (K+1)J ∀a, i wa,i=ua Λ b (w 0 , w b ) = max w∈Σ (K+1)J ∀a, i wa,i=ua ∆ 2 b 2 J i=1 β 2 i σ 2 w0,i + σ 2 w b,i .
Equivalently, we are interested in min w∈Σ (K+1)J ∀a, i wa,i=ua J i=1

β 2 i σ 2 w 0,i + σ 2 w b,i .
We introduce the associated Lagrangian function

f (w, q) = J i=1 β 2 i 1 w 0,i + 1 w b,i + K a=0 q a J i=1 w a,i -u a .
Taking the derivative with respect to w 0,i and w b,i for the different values of i yields

w 0,i = |β i | √ q 0 and w b,i = |β i | √ q b .
Summing over i implies that

√ q 0 = J i=1 |β i | u 0 and √ q b = J i=1 |β i | u b ,
and plugging the above in the expression of the weights yields

w 0,i = |β i | J i=1 |β i | u 0 and w b,i = |β i | J i=1 |β i | u b .
In particular, max

w∈Σ (K+1)J ∀a, i wa,i=ua ∆ 2 b 2 J i=1 β 2 i σ 2 w0,i + σ 2 w b,i = ∆ 2 b 2σ 2 J i=1 |β i | 2 1 u0 + 1 u b , (16)
yielding

max w∈Σ (K+1)J min b =0 ∆ 2 b 2 J i=1 β 2 i σ 2 w0,i + σ 2 w b,i ≤ 1 2σ 2 J i=1 |β i | 2 max u∈Σ (K+1)J min b =0 ∆ 2 b 1 u0 + 1 u b .
On the other hand, letting w a,i = |βi| J i=1 |βi| u a with a u a = 1 we have 1

2σ 2 J i=1 |β i | 2 max u∈Σ (K+1)J min b =0 ∆ 2 b 1 u0 + 1 u b ≤ max w∈Σ (K+1)J min b =0 ∆ 2 b 2 J i=1 β 2 i σ 2 w0,i + σ 2 w b,i ,
showing that the two optimization programs are equivalent and that when denoting

(u 0 , . . . , u K ) = argmax u∈Σ (K+1)J min b =0 ∆ 2 b 1 u0 + 1 u b , one has ∀a ∈ {0, . . . , K}, ∀i ≤ J, w a,i = u a |β i | J i=1 |β i | .
This corresponds to the optimal allocation strategy in the active mode. Recalling that when α = β, the optimal weights for the active mode satisfy both C prop and C agnostic completes the proof.

Proof. Let w * (µ) be any oracle weights at µ. We will show the lower bound objective (4) is strictly concave as a function of w around w * (µ), so that w * (µ) was in fact unique. For each k > 0, let λ k be the minimiser in Alt k (µ) of the weighted divergence in (4).

We perform a second-order Taylor expansion of the inner objective around λ k , which is a good approximation near λ k (which is, after all, what matters when reasoning about w near w * (µ)). To this end, let us abbreviate the divergences, and their first and second derivatives in their second argument by d k aj := d(µ a,j , λ k a,j ), g k aj := d (µ a,j , λ k a,j ) and h k aj := d (µ a,j , λ k a,j ), which all depend on λ k . A second-order Taylor expansion of the inner objective of (4) around λ k yields inf λ∈Alt k a,j w a,j d(µ a,j , λ a,j ) ≈ Due to the last term, each of these is a strictly concave function of w a,j for a ∈ {0, k} and all j ≤ J (here we use β j = 0 and strong convexity h k aj > 0). Now we still need to consider the max w∈Σ (K+1)×J min k>0 problem. Let's convexify this for the inside finite min, and min-max swap to get a problem of the form min q∈Σ K max w∈Σ (K+1)×J . Fixing the minimax outer strategy for q, we find that w is the maximiser of the strictly concave function To complete the argument, we argue that q k > 0 for all k > 0, or, equivalently, that at w * the min k>0 are all equalised. For if not, we can move mass from w k,j for the higher k > 0 to w k ,j for the lower k and increase the objective value. This then proves that w * (µ) is unique, as the objective function is bounded above by a strictly concave function itself maximised at w = w * (µ).

F Algorithm Details

In this section we go into more details on the algorithm for each mode. Let us start with some notation. Let β(δ, t) be a threshold function. We denote the inverse of β(t, δ) in its second argument by β -1 (t, Λ) = min {δ ∈ (0, 1)|Λ ≥ β(t, δ)} .

We extend the definition of the GLR statistic to sample frequencies w and bandit µ by w a,i d(µ a,i , λ a,i ) , so that the original definition [START_REF] Degenne | Non-asymptotic pure exploration by solving games[END_REF] is Λ(t) = Λ(N (t)/t, μ(t)). For any µ, we denote by ∇ w Λ(w, µ) any sub-gradient of w → Λ(w, µ). We can obtain one such a sub-gradient by letting (b, λ) be any minimiser of Λ(w, µ), and constructing the vector with entry (a, i) given by (a, i) → d(µ a,i , λ a,i ) if a ∈ {0, b} 0 otherwise .

Our algorithms will make use of an online learning method (called A below) for linear losses defined on the simplex. This online learning task is known as the Hedge or Experts setting in the literature.

We will make use of AdaHedge [START_REF] De Rooij | Follow the leader if you can, Hedge if you must[END_REF], as it adapts automatically to the range of the losses and does not require tuning. Our methods for the active, proportional and agnostic modes are displayed as Algorithms 1, 2 and 3. Each algorithm consists of a Forced Exploration part, which serves to ensure that the empirical estimate of the bandit model converges, i.e. μ(t) → µ. By forcing exploration sublinearly often, the main term in the sample complexity is unaffected asymptotically. Each algorithm further makes use of online learning to compute w * (µ). In the notation of this section, we have w * (µ) = argmax w∈C Λ(w, µ) .

Our approach to learning w * (µ) is to perform gradient steps on the plug-in loss function w → -Λ(w, μ(t)). It is in the convex domain C ⊆ Σ (K+1)×J that we see the main difference between the three modes. Recall from Section 2.3 that in the active mode w is not constrained further, in the proportional mode the subpopulation marginal of w must equal α, i.e. 1, w = α, and in the agnostic mode w must be the independent product w = vα of some arm marginal v ∈ Σ K+1 and the subpopulation frequencies α. We hence need to design online learners for each of the three C. In the active case, we have one learner A that learns the full joint w * (a, j) directly, in the proportional case we use one learner A j for each subpopulation j ∈ [J] to learn the conditional distribution w * (a|j), and in the agnostic case we again use one learner to learn the common marginal w * (a). This difference is reflected in the loss function used in each mode, and hence in the gradient that is fed to each learner. In the active case we use the full (K + 1) × J gradients active t := -∇ w Λ(w t , μ(t)) .

In the proportional case we have w(a, i) = w(a|i)α i , and by the chain rule we hence have gradients i, proportional t := -∇ w(a|i) Λ(w t , μ(t)) =α i ∇ w Λ(w t , μ(t))e i .

Finally, in the agnostic case we have w(a, i) = w(a)α i , and again by the chain rule we have agnostic t := -∇ w(a) Λ(w t , μ(t)) = -∇ w Λ(w t , μ(t))α .

Run Time In each of the three modes, our algorithms evaluate Λ for the confidence in the recommendation, compute one sub-gradient of Λ for the loss function, and spend O(K × J) time bookkeeping. Evaluation and sub-gradient computation for Λ boil down to solving a convex minimisation problem with an equality constraint. We use Newton's method with backtracking line search to find the minimiser given b. Each Newton iteration takes O(J 2 ) time (recall that only 2 arms are involved), and we never needed more than 40. Doing this K times for the explicit minimum over b yields a total per iteration run time of O(KJ 2 ).

Figure 1 :

 1 Figure 1: Modes of Interaction between Learner and Bandit in each round. In Active mode the learner determines the subpopulation, while in the right three passive modes it is sampled from α.

Figure 2 :

 2 Figure 2: (Left) Risk assessment calibration on a log-log scale. (Right) Stopping time boxplot for µ = [0.1 0.4 0.3; 0.2 0.5 0.2; 0.5 0.1 0.1] ∈ [0, 1] (K+1)×J when β = [1/3, 1/3, 1/3], α = [0.4, 0.5, 0.1] with Bernoulli distributions.

  Risk assessment over time.

Figure 3 :

 3 Figure 3: Real data and results.

Recalling, d

  mid (w a , µ a , w b , µ b ) := inf v w a d(µ a , v) + w b d(µ b , v) one has, min a∈S β (µ) inf λ:λa<λ0 Λ(w, λ, µ) = min a∈S β (µ) d mid (w 0 , µ 0 , w a , µ a ) .

  i d(µ a,i , λ a,i ) i d(µ a,i , λ a,i ) (Theorem 1)

  is given byλ a,j = λ k a,j -g k aj h k aj + β j (δ a=0δ a=k ) w a,j h

Table 1 :

 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

Code at https://gitlab.com/ckatsimerou/abc_s_public

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-IDEX-0005), and Chaire SeqALO (ANR-20-CHIA-0020).

E Asymptotic Optimality: Proof of Theorem 2

In this section we show that T-a-S with C-tracking and a certain threshold β(t, δ) is safely calibrated and asymptotically optimal. This is an important sanity check to validate our approach theoretically. Note that for the experimental validation we have explored a practically appealing variant of this algorithm: we employ an iterative scheme to approximate w * ( μ(t)), use D-tracking, and stylise the threshold.

Safe calibration follows from the definition of the recommendation rule (we report the answer S β ( μ(t)) at the empirical estimate μ(t) of the bandit instance), together with the computation of the risk assessment δt . It does not depend on the sampling rule. Our confidence level δt is obtained by inverting the threshold β(t, δ) at the GLR statistic [START_REF] Degenne | Non-asymptotic pure exploration by solving games[END_REF]. Safe calibration then follows from an anytime-valid GLR deviation inequality with boundary β(t, δ). We refer to [START_REF] Kaufmann | Mixture martingales revisited with applications to sequential tests and confidence intervals[END_REF]Proposition 23] for a boundary that is, in case of the ABC-S problem, of order ln 1 δ + K + 2J • O(ln ln t δ ). It remains to argue that the T-a-S sampling rule converges to the oracle weights. The original T-a-S proof for the BAI problem is due to [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF]Theorem 14]. An upgrade to any single-answer problem, including our ABC-S, is due to [START_REF] Degenne | Pure exploration with multiple correct answers[END_REF]. For active mode, their theorem applies directly, while for agnostic mode it applies with the pair (I t , X t ) regarded as the observation. We get: Theorem 3 ([6, Theorems 7 and 10]). For all ABC-S instances µ ∈ L in active mode and agnostic mode, Track-and-Stop with C-tracking and stopping threshold β(t, δ) = ln(t 2 /δ) + O(1) is δ-correct with asymptotically optimal sample complexity.

In proportional mode, we have the additional constraint that the learner chooses its arm in response to seeing (but not controlling) the subpopulation I t . Still, the tracking convergence result [6, Lemma 6] goes through, upon observing that the empirical distribution of I t converges to α by the law of the large numbers, and hence our conditional tracking (see "sampling rule" in Section 3) adds the right conditional to the right marginal. All in all, the computed joint weights converge to the joint w * prop (µ), and tracking makes the sampling proportions also converge there.

We conclude with a remark on our use of D-tracking. Recall that D-tracking is the idea of advancing N a (t) towards t times the most current oracle weights, i.e. tw * a ( μ(t)), while C-tracking makes N a (t) advance towards the sum of encountered oracle weights, i.e. t s=1 w * a ( μ(s)). As argued in [7, Appendix E], D-tracking can fail to make N a (t)/t converge to w * a (µ). However, this requires that the maximiser of the lower bound problem is not unique at µ (as we are maximising a concave function, the set of maximisers is always convex). Here we argue that such a situation does not occur for the ABC-S problem. To see why, we argue that the lower bound objective, as a function of w, is strictly concave. It suffices to show this for the active mode problem, as the problems for the other modes are further constrained maximisation problems of the same objective. Lemma 6. Fix a bandit instance µ ∈ L. Let λ → d(µ a,j , λ) be a strongly convex function for each arm a and subpopulation j. Then for the ABC-S problem with β such that β j = 0 for all j, the oracle weights w * (µ) are unique.

end for Algorithm 2 Algorithm for Proportional Mode.

Require: J online learners A (1) , . . . , A (J) for (K + 1) experts each.

for

(a)

Direct Tracking Obtain sample X t from ν At,It .

For j ∈ [J], send loss vector