arXiv CSopen access

Active Context Selection Improves Simple Regret in Contextual Bandits

Active Context Selection Improves Simple Regret in Contextual Bandits

arXiv:2605.20040v1 [cs.LG] 19 May 2026

Mohammad Shahverdikondori College of Management of Technology, EPFL [email protected]

Jalal Etesami Department of Computer Science, TU Munich [email protected]

Negar Kiyavash College of Management of Technology, EPFL [email protected]

Abstract We study the contextual multi-armed bandit problem with a finite context space (a.k.a. subpopulations), where the learner recommends a best action for each context and is evaluated by context-weighted simple regret. Our guarantees are worst-case over the reward distributions, while remaining instance-dependent with respect to the context distribution vector p. Akin to experimental design problems where the population of interest is fixed but the sampled subpopulation can be controlled, we allow the learner to actively choose which context to sample from. For a known p, we characterize tight regret rates: passive sampling where q contexts are randomly revealed achieves regret of order n/T ∥p∥1/2 , whereas active sampling with allocation qj ∝ p2/3 achieves the tight rate n/T ∥p∥2/3 . j The resulting improvement can be as large as Θ(k1/4 ), where k is the number of contexts. We further extend the analysis to budgeted active sampling, characterize the corresponding tight rate, and identify when a limited active budget suffices to recover the fully active rate. When p is unknown, we propose the Explore-ExploreThen-Commit (EETC) algorithm, which optimally balances estimating the context distribution and the time to switch to active allocation, such that for large horizons, it matches the known-p active rate up to constants. Experiments on synthetic and real-world data support our theoretical findings. p

1

Introduction

Sequential decision making problems often involve contextual information: the outcome distribution of an action may depend on observable characteristics of the unit under consideration [LS20, BCB+ 12]. In the finite context regime, each context value naturally defines a subpopulation of the target population, such as an age bracket, geographic region, or disease subtype. This viewpoint is especially common in experimental design applications, where the effect of an action, or treatment, may vary substantially across subpopulations. The learning objective is then not simply to identify a single globally best action, but to recommend the best treatment for each subpopulation [PR13, RKB+ 21, CHVDS23] This motivates the context-weighted simple regret objective studied in this paper: after a fixed experimental budget, the learner recommends one treatment per subpopulation. The resulting regret is the average recommendation gap weighted by the population distribution over subpopulations. Even when this distribution is known from historical data, the learner still faces the question of how to allocate the experimental budget across subpopulations. In the standard passive setting, contexts Preprint.

arrive randomly according to the population distribution and the learner only chooses the treatment [KZAB23, JLB22, DSC+ 18]. However, in many applications, the experimenter may have partial control over which subpopulation to sample. For instance, an online platform may target specific user segments, or a clinical study may recruit participants from selected demographic groups, possibly at different costs. This raises two natural design questions which we study in this paper: when is it worth actively choosing the context, and what is the gain compared to passive sampling? Besides a fully passive scenario for benchmarking, we study a fully active setting where the learner can choose both the subpopulation and the treatment as well as a budgeted intervention setting, in which only a fraction of the rounds can be active, capturing cases where targeted recruitment or controlled sampling is costly. Our analysis shows how the value of active subpopulation selection depends on the population distribution and when it can lead to meaningful improvements over passive sampling. Additionally, we consider the setting where subpopulation distribution is not a priori known and must be estimated. This setting introduces a trade-off between using passive samples to learn the subpopulation distribution p and using active samples to improve treatment recommendations. Somewhat surprisingly, we show that for sufficiently large horizons, this uncertainty does not result in worst simple regret rate compared to an active policy that knows the distribution. Our work is related to several lines of work in literature. Heterogeneous treatment effect and subpopulation-aware decision making problems study settings where treatment effects vary across groups and where ignoring this heterogeneity can lead to suboptimal treatment rules [RKB+ 21, CHVDS23]. Contextual bandits and policy learning methods also aim to learn context-dependent decisions, including recent work on simple regret in contextual bandits such as Proportional Response [KZAB23], as well as adaptive experimental designs for policy learning [KOIK24, DSC+ 18, JLB22]. These works typically consider the passive contextual setting, where contexts are revealed by the environment. Our focus is different: we quantify the improvement the learner can obtain by actively selecting which context (or subpopulation) to sample. The closest pure exploration formulation is multi-bandit best arm identification [GGLB11, SBC19], where the goal is to identify the best arm in each of several bandits. This is close to our fully active setting, but it studies best arm identification, where the goal is to minimize the error probability of identifying the best arm, rather than context-weighted simple regret, and does not study active and passive context sampling. We refer the reader to Appendix A for a more detailed discussion of related work. Contributions. Our main contributions are as follows: • For known subpopulation distribution p, we characterize the optimal context-weighted simple regret rate and show that it is attainable, up to constant factors, by a policy that selects which 2/3 subpopulation to sample from independently of the observed history proportionally to pj , where pj is the jth element of the subpopulation distribution p. The gap of this active policy’s regret compared to passive sampling can be of order Θ(k 1/4 ), where k is the number of contexts. • We extend the analysis to a budgeted intervention setting, where the learner can actively choose the subpopulation only in α fraction of the rounds. We characterize the optimal allocation in this setting, propose an algorithm that achieves the optimal simple regret rate, and identify the minimum intervention budget required to match the optimal fully active rate. • We study the setting where the subpopulation distribution p is unknown to the learner. We show that neither fully passive nor fully active policies are optimal in general, and propose the EETC algorithm, which balances passive estimation with active allocation rounds. We prove that, for large horizons, EETC achieves the same rate as the optimal fully active policy that knows p, up to constant factors.

2

Problem Setup

In this section, we formally define the bandit with subpopulations problem considered in this paper and introduce the relevant notation. P Notation. For any natural number n, let [n] := {1, . . . , n}. Let ∆n−1 := {x ∈ Rn | i xi = 1, xi ≥ 0}, denotes the probability simplex in Rn and ∆n−1 ⊂ ∆n−1 the set of vectors with all + n positive entries. For a vector v ∈ R we denote its ℓp norm by ∥v∥p . 2

The bandit with subpopulations problem models a sequential interaction between an agent and an environment. The environment consists of a treatment variable A ∈ [n], a subpopulation (or context) variable C ∈ [k], and a reward variable Y ∈ [0, 1]. For each treatment–subpopulation pair (i, j) ∈ [n] × [k], the reward distribution is given by νi,j with mean µi,j . Let ν and µ ∈ [0, 1]n×k denote the matrix of reward distributions and reward means, respectively. We let p ∈ ∆k−1 denote + the population distribution over subpopulations, that is, ∀j ∈ [k] : P(C = j) = pj > 0 , and define pmin := minj∈[k] pj . The agent interacts with the environment for T rounds. At each round t ∈ [T ], the interaction proceeds as follows. 1. A subpopulation Ct is either sampled according to p and revealed to the agent, or selected by the agent based on the observed history Ht = (As , Cs , Ys )t−1 s=1 and, when known, the population distribution vector p. 2. Based on the history Ht and the current subpopulation Ct , the agent selects a treatment At . 3. The agent then observes a random reward Yt , drawn independently from νAt ,Ct . We refer to a round in which Ct is sampled from p and the agent only chooses At as passive round. In contrast, when the agent is allowed to choose both Ct and At , we call the round active. An instance of the problem is specified by a pair (ν, p). Let E(n, k, p) denote the class of all instances with n treatments and k subpopulations distributed according to p, where the reward distributions is supported on [0, 1]. Although we focus on a finite discrete set of subpopulations, the same perspective also applies to continuous context spaces, as common in contextual bandits, by introducing a suitable discretization of the context space. Under such a discretization, we obtain the same formulation and its corresponding regret bounds up to the discretization error. After T rounds, the agent outputs, for each subpopulation j ∈ [k], a recommended best treatment âT (j). The collection of sampling decisions made during the interaction together with the final recommendation rule forms a policy π. For a policy π interacting with an instance (ν, p) ∈ E(n, k, p) with means matrix µ, we define the simple regret as the expected subpopulation-weighted gap between the optimal and recommended treatments:   X SR (π, T, ν, p) := Ej∼p µa∗ (j),j − µâT (j),j = pj E [∆j ] , j

where a∗ (j) ∈ arg maxi∈[n] µi,j denotes an optimal treatment for subpopulation j, and ∆j the recommendation gap for subpopulation j. The objective is to minimize the worst-case simple regret (over the class E(n, k, p)) defined as: SR(π, T, p) :=

sup

E

SR (π, T, ν, p) ,

(1)

ν:(ν,p)∈ (n,k,p)

for a policy π, i.e., find arg inf π SR(π, T, p). This criterion is worst-case with respect to the reward means, but remains parameterized by the subpopulation distribution p. In other words, the performance measure SR(π, T, p) is the supremum over reward configurations for a fixed population profile p, rather than a worst-case p. This is because our objective is not to design algorithms for an adversarial subpopulation distribution, but develop algorithms whose performance adapts to the instance-dependent vector p. Thus, the problem is worst-case in terms of the mean rewards but instance-dependent for the subpopulation distribution. Throughout the paper, we focus on the data-rich regime, in which the horizon T ≫ n, k, 1/pmin . 2.1

Policy Classes

We consider several classes of policies in the paper. A policy is called passive if, at each round, the subpopulation is randomly drawn according to the distribution p and not selected by the agent. In contrast, a policy is called active if the agent can pick the subpopulation at every round. We denote the classes of passive and active policies by Πpas and Πact , respectively. We say that a policy π is history-free if its subpopulation selection rule does not depend on the observed history and may only depend on the distribution p. Recall that each policy consists of two components: a subpopulation selection rule and an arm selection rule within each subpopulation. 3

For history-free policies, only the first component is restricted to be independent of the history; the second component can clearly depend on the history. In all the algorithms considered in this paper, this second component is implemented through a standard bandit subroutine, as discussed in the next subsection. We denote the class of all history-free policies by Πhf . Note that passive policies form a special case of history-free policies (i.e., Πpas ⊆ Πhf ), since for such policies, the subpopulation is sampled according to p independently of the history. We denote the class of all policies, without any restriction on how the subpopulation selection rule may depend on observed rewards, by Π. Finally, we distinguish between policies that know the distribution p and those that do not by indicating p in parentheses. For example, Πhf (p) denotes the class of history-free policies that know p, whereas Πhf denotes the class of history-free policies that do not. We use the same convention for the other policy classes. 2.2

Within-Subpopulation Bandit Subroutine

Since we do not impose any structural relation across the reward means of different subpopulations, the learning problem within each subpopulation j ∈ [k] can be viewed as an independent stochastic bandit problem with n arms. If the number of samples allocated to subpopulation j were fixed, then minimizing E[∆j ] would reduce to the classical simple regret problem in standard bandits, which is well-studied in the literature [BMS09, ZSSJ23, LBA+ 26]. In our setting, however, these within-subpopulation horizons are induced by the learner’s subpopulation selection rule. Thus, the main remaining question is how to allocate the total budget T across subpopulations. Throughout the paper, we use ASR to denote an anytime standard bandit subroutine for simple regret minimization. Each subpopulation maintains an independent copy of ASR , which is used to select treatments whenever that subpopulation is sampled. This separates the standard within-subpopulation treatment selection problem from the higher level allocation problem. We rely on the following standard minimax guarantee. Lemma 2.1 ([LS20], Section p 33).
For a stochastic bandit with n arms and T rounds, the minimax simple regret scales as Θ n/T . Moreover, this rate can be achieved by anytime algorithms, i.e., algorithms that do not require prior knowledge of T . For concreteness, uniform sampling over the n arms gives the optimal simple regret rate up to logarithmic factors. Alternatively, an anytime cumulative regret minimization algorithm such as MOSS [AB09], combined with p a recommendation rule that outputs arms proportionally to their play counts, achieves the optimal n/T rate up to constants. This reduction clarifies the allocation problem. Since the final objective weights the recommendation gap in subpopulation j by pj , one might expect the natural allocation to be proportional to p, which is exactly the passive allocation. However, because simple regret decreases nonlinearly with the number of samples, this allocation is generally suboptimal. The next sections show that active subpopulation selection leads to a different allocation rule and can largely improve over passive sampling.

3

Known Subpopulation Distribution

In this section, we study the setting where the subpopulation distribution p is known. We first show that, under the worst-case simple regret criterion in (1), it is sufficient to consider history-free policies: allowing the subpopulation selection rule to depend on observed history does not improve the minimax rate. We then compare passive and fully active policies and characterize the active–passive gap, showing that the optimal active allocation can improve over passive sampling by a factor as large as O(k 1/4 ). Finally, we extend the analysis to the budgeted setting, where only an α fraction of rounds can be active, and characterize the optimal allocation under this constraint. We begin with notation. For a policy π interacting with an instance (ν, p), let q(π, (ν, p)) ∈ ∆k−1 denote the expected proportion of rounds allocated to the different subpopulations under π. More precisely, its j-th coordinate is the expected fraction of rounds t in which Ct = j. As a consequence of our definition, for history-free policies, the allocation proportion is independent of ν, and we simply write q(π, (ν, p)) = q(π, p). 4

3.1

Optimality of History-Free Policies

We formalize the reduction to history-free policies. The key point is that, for the worst-case simple regret in (1), the optimal rate is determined by the allocation of samples across subpopulations, and history-dependent changes to this allocation do not improve the minimax order. Lemma 3.1 (Simple Regret Lower Bound). For any subpopulation distribution p ∈ ∆k−1 known to + the agent and any policy π ∈ Π(p), r n  ∥p∥2/3 . SR(π, T, p) ∈ Ω T Proof sketch. For any policy, we construct a family of 2k hard instances indexed by the binary hypercube. In each instance, the rewards are binary with means equal to 1/2 except for two candidate treatments in each subpopulation, one of which is optimal with a properly chosen gap; the identity of this optimal treatment varies across the family and depends on policy. We then show that ptheP p the average simple regret of the policy over this family is at least Tn j∈[k] √qjj , where qj is the fraction of times the policy samples subpopulation j, averaged over this family of instances. Hence, the worst-case regret is at least of the same order. Optimizing this lower bound over allocations p 2/3 yields the choice qj ∝ pj and gives the minimax lower bound of order Tn ∥p∥2/3 . The full proof alongside all the omitted proofs is deferred to Appendix B. We now show that, for history-free policies, the worst-case simple regret depends solely on the expected allocation proportions across subpopulations, namely on the vector q(π, p). The following characterization is tight up to constant factors. Lemma 3.2 (Simple Regret of History-Free Policies). For any history-free policy π ∈ Πhf (p) along with the subroutine ASR and expected subpopulation proportions q(π, p), if ∀j ∈ [k] : T q(π, p)j > 24 ln(2kT ), then r n X  p p j SR(π, T, p) ∈ Θ . T q(π, p)j j∈[k] This performance depends solely on the quantity P showspthat, for history-free policies, thek−1 p / q(π, p) . Therefore, for any q ∈ ∆ j j + , we define j∈[k] X pj √ . qj

Sp (q) :=

(2)

j∈[k]

The following lemma identifies the optimal active allocation that minimizes this quantity. Lemma 3.3 (Optimal Allocation for Active Policies). For any p ∈ ∆k−1 + , the unique minimizer of Sp (q) over q ∈ ∆k−1 is + 2/3

∗

q (p)j = P

pj

2/3 ℓ∈[k] pℓ

,

j ∈ [k].

Moreover, Sp (q∗ (p)) = ∥p∥2/3 . Combining Lemmas 3.1, 3.2, and 3.3 gives the following optimality result, which states that historyfree policies achieve the same regret as general policies that can select the subpopulation allocation based on the history. Proposition 3.4 (Optimality of History-Free Policies). For every p ∈ ∆k−1 + ,   inf SR(π, T, p) ∈ Θ inf SR(π, T, p) . π∈Πhf (p)

π∈Π(p)

That is, there is no optimality penalty for adhering to history-free policies. 5

(b) Flow from p to the optimal active allocation q∗ (p).

(a) Heatmap of R(p) on the 3-simplex.

Figure 1: Illustration of the active–passive gap on the probability simplex for k = 3. Left: heatmap of R(p) over the simplex, showing that the gap is negligible near the uniform distribution (center) and increases for non-uniform population profiles (corners). Right: for each point p, the arrow points toward the optimal active allocation q∗ (p), illustrating that the optimal active policy shifts the sampling proportions toward a more uniform (center), and hence more exploratory, allocation. 3.2

Gap Between Active and Passive Policies

We now compare the best passive and active policies within the class of history-free policies that know p. Under any passive policy, the subpopulation observed at each round is sampled from p, and hence q(π, p) = p. Lemma 3.2 gives  r n X √  r n 1/2 (3) pj = Θ ∥p∥1/2 . inf SR(π, T, p) ∈ Θ T T π∈Πpas (p) j∈[k]

On the other hand, Lemmas 3.2 and 3.3 imply that the best active history-free policy satisfies r n  inf SR(π, T, p) ∈ Θ ∥p∥2/3 . T π∈Πact (p)∩Πhf (p)

(4)

2/3

This rate is achieved by sampling subpopulation j proportionally to pj and running ASR within each subpopulation. Compared to the passive allocation p, the optimal active allocation is closer to uniform: it downweights large coordinates of p and upweights small ones, leading to a more exploratory allocation. See Figure 1 for an illustration. q The multiplicative active–passive gap is therefore R(p) := ∥p∥1/2 /∥p∥2/3 and (3)–(4) imply
inf π∈Πpas (p) SR(π, T, p) ∈ Θ R(p) . inf π∈Πact (p)∩Πhf (p) SR(π, T, p) Lemma 3.5 (Active–Passive Gap). For every p ∈ ∆k−1 R(p) ∈ + , R(p) ≥ 1. Moreover, supp∈∆k−1 + 1
Θ k 4 , and this order is tight. The inequality R(p) ≥ 1 implies that active policies are always at least as good as passive policies. When p is uniform, R(p) = 1, so the two rates coincide; more generally, the gain is limited near uniform distributions. The largest gap arises for highly non-uniform p, in particular when one subpopulation has a large mass and the remaining coordinates are all equal and of order k −3/2 . 3.3

Budgeted Interventions

In many practical settings, the agent has a limited budget of active rounds, in which it can choose both the subpopulation and the treatment. We focus on such budgeted setting in this section. More 6

Algorithm 1 α-Active Simple Regret Algorithm 1: Input: Standard bandit subroutine ASR , distribution p, budget α, and horizon T . j

2: Initialize one instance ASR of ASR for each subpopulation j ∈ [k]. 2/3
(1 − α)pj , cpj . 4: for t = 1, 2, . . . , ⌊(1 − α)T ⌋ do t 5: Sample Ct ∼ p, and choose the treatment At recommended by AC SR . 6: end for 7: Find the unique value c∗ such that F (c∗ ) = 1. q ∗ −(1−α)pj 2/3
. 8: For every j ∈ [k], set qj∗ = max (1 − α)pj , c∗ pj , and rj = j α 9: for t = ⌊(1 − α)T ⌋ + 1, . . . , T do t Sample subpopulation Ct according to r, and choose the treatment At recommended by AC 10: SR . 11: end for j 12: Output: For each subpopulation j, output the recommended arm âT (j) returned by ASR .

3: Define F (c) =

P

j∈[k] max

precisely, we consider policies that are allowed to actively select the subpopulation in at most αT of the total T rounds, where α ∈ [0, 1]. We assume the distribution p is known to the agent, and denote this class of policies by Πα (p). Note that Πα=0 (p) = Πpas (p) and Πα=1 (p) = Πact (p), so this model interpolates between the passive and fully active settings. Our algorithm design relies on the result of Lemma 3.2, which states that the regret of a history-free policy π depends on the subpopulation proportions q(π, p) only through the quantity Sp (q) defined in (2). Thus, the goal is to choose the allocation vector q to minimize this term. Given that the subpopulation cannot be selected by the agent during the (1 − α)T rounds but must instead be sampled according to p, any policy in Πα (p) must satisfy q(π, p)j ≥ (1 − α)pj , ∀j ∈ [k]. Therefore, the best achievable allocation is given by the solution of the following constrained optimization problem, X pj min Sp (q) = min s.t. qj ≥ (1 − α)pj , ∀j ∈ [k]. (5) √ , qj q∈∆k−1 q∈∆k−1 + + j∈[k]

This optimization problem is convex and its solution admits a simple threshold structure. Let q∗α (p) and vα∗ (p) denote the optimizer and the optimal value of the program, respectively. In particular, 2/3
there exists a constant c∗ ≥ 0 such that q∗α (p)j = max (1 − α)pj , c∗ pj , j ∈ [k]. Thus, the subpopulations are partitioned into two groups. For those subpopulations whose coordinates satisfy 2/3 q∗α (p)j > (1 − α)pj , the optimal allocation remains proportional to pj , whereas for subpopulations ∗ satisfying qα (p)j = (1 − α)pj , the passive rounds already provide a sufficient number of samples, so there is no need to actively allocate additional pulls to them. Algorithm 1, which is based on this characterization, summarizes the steps of the budgeted intervention setting. Theorem 3.6 (Simple Regret of Algorithm 1). For every p ∈ ∆k−1 + , Algorithm 1 is a history-free policy in Πα (p) with expected subpopulation proportions equal to q∗α (p). Consequently, when T is large, its worst-case simple regret satisfies the optimal rate r
n ∗ SR(Alg.1, T, p) ∈ O v (p) . T α Another question that arises naturally in this setting is that given a subpopulation distribution p, what is the minimum intervention budget α required to match the fully active setting? Equivalently, how many active rounds are sufficient to attain the optimal fully active rate. We denote this threshold by αmin (p). The next lemma gives a closed-form expression for αmin (p) in terms of p. Lemma 3.7 (Threshold Budget αmin (p)). For a given p ∈ ∆k−1 + , let αmin (p) := 1 − −1/3 P 2/3 pmax / j∈[k] pj , where pmax = maxj pj . Then, for every α ∈ [αmin (p), 1], we have vα∗ (p) = ∥p∥2/3 . Consequently, for every such α, the simple regret bound of Algorithm 1 matches the optimal rate of fully active policies, which is also the optimal rate over all policies. 7

4

Unknown Subpopulation Distribution

In this section, we study the setting in which the distribution of subpopulations, p, is unknown to the learner, and investigate how this changes the policy design and the achievable regret rates. We show that neither passive nor fully active policies are optimal in general. Instead, the optimal strategy must combine passive and active rounds. We then propose an algorithm based on this principle and show that, for a sufficiently large horizon T , it achieves the same simple regret bound as a fully active policy that knows p. The simple regret criterion in (1) depends explicitly on p. Yet a fully active policy agnostic of p that chooses a subpopulation at every round, receives no information about p. Consequently, if the policy undersamples some subpopulation, the worst-case instance may assign a large mass to that subpopulation, resulting in a large regret. Therefore, without knowledge of p, the minimax fully active policy must allocate samples uniformly across subpopulations, i.e., q(π, p) = k1 1, where 1 denotes the all-ones vector. By Lemma 3.2, the resulting simple regret is Θ

r nk  pj  p , =Θ T T 1/k j∈[k]

r n X

which is worse than the passive regret rate Θ

q

n T ∥p∥ 12

derived in (3), as

P

j∈[k]

√

√ pj ≤ k, for

every p ∈ ∆k−1 + . In the next section, we present an algorithm that outperforms the passive policy. It does so by balancing the exploration–exploitation trade-off in learning the distribution p. Passive rounds provide information about p and allow the learner to estimate it, while active rounds are used to reduce the simple regret once a sufficiently accurate estimate is available. 4.1

Explore-Explore-Then-Commit (EETC)

Pt For each round t ∈ [T ] and subpopulation j ∈ [k], let N (t)j = s=1 1{Cs = j} denote the number of times subpopulation j has been observed up to round t, including round t itself, and let p̂(t) denote the empirical estimate of p, namely p̂(t)j = N (t)j /t. The algorithm proceeds in three phases: (I) The algorithm acts passively in order to estimate p. The key point is that after O(log(T )) rounds, the estimate becomes accurate enough so that the allocation q∗ (p̂(t)) computed from p̂(t) yields a value Sp (q∗ (p̂(t))) within a constant factor of the optimal value ∥p∥2/3 . Motivated by this, we define the first stopping time n o τ1 := inf 1 ≤ t ≤ T | min N (t)j ≥ log(kT 2 ) . j∈[k]

(6)

We show that, with high probability, τ1 is logarithmic in T , and that at time τ1 the estimate p̂(τ1 ) is sufficiently accurate for the subsequent allocation steps. (II) This phase commences at time τ1 and the algorithm still acts passively. While at this point, the estimate is already accurate enough to guide the active allocation, the algorithm can still benefit from additional passive samples as long as doing so does not leave too few active rounds to implement the optimal active allocation which is suggested by the current estimate. Lemma 3.7 gives exactly this threshold: for an estimate p̂(t), the fully active rate can still be matched if the remaining active fraction is at least αmin (p̂(t)), or equivalently if the passive fraction is at most 1 − αmin (p̂(t)). Accordingly, we define  τ2 := inf t ≥ τ1 + 1 | t/T > 1 − αmin (p̂(t)) . (7) Thus, τ2 is the first round at which the current estimate no longer allows us to keep playing passively and still match the optimal active rate. The algorithm therefore stops the passive phase at round τ2 and sets p̂fr := p̂(τ2 − 1), where p̂(τ2 − 1) is the estimate of the subpopulation distribution vector at the previous round, i.e., τ2 − 1. For large T , we show that τ2 ≤ T with high probability. 8

Algorithm 2 Explore-Explore-Then-Commit (EETC) 1: Input: standard bandit subroutine ASR and horizon T . j

2: Initialize one instance ASR of ASR for each subpopulation j ∈ [k]. 3: for t = 1, . . . , τ2 do C

4: Sample Ct ∼ p and choose the treatment At recommended by ASRt . 5: end for 6: Compute q and r from (8) using p̂fr . 7: for t = τ2 + 1, . . . , T do C

8: Sample subpopulation Ct according to r and choose the treatment At recommended by ASRt . 9: end for j 10: Output: For each subpopulation j, output the recommended arm âT (j) returned by ASR .

(III) The algorithm switches to active play using p̂fr . The remaining rounds are then allocated exactly as in the budgeted-intervention algorithm of Section 3.3, with active fraction 1 − τT2 and estimated distribution p̂fr . Specifically, for each c > 0, define X τ2 2/3 F (c) := max{ p̂fr , (p̂fr c}, j) T j j∈[k]

∗

let c be the unique value such that F (c∗ ) = 1, and define the vectors q and r by qj := max

nτ

2 fr 2/3 ∗ p̂j , (p̂fr c j)

T

o ,

rj =

qj − τT2 p̂fr j . 1 − τ2 /T

(8)

The algorithm then uses the remaining rounds actively, selecting subpopulations according to r. Algorithm 2 presents the pseudocode, and the next theorem states its regret guarantee. Theorem 4.1 (Simple Regret of EETC). For sufficiently large horizon T , the worst-case simple regret of EETC is r
n ∥p∥2/3 . SR(EETC, T, p) ∈ O T Consequently, EETC up to a constant achieves the same simple regret rate as the optimal fully active policy that knows p, and hence also matches the known-p lower bound up to constant factors.

5

Experiments

This section presents the experimental results on real-world data. Additional dataset details and further experiments are deferred to Appendix C. MovieLens Experiment. We evaluate the algorithms on a MovieLens 1M instance [HK15]. Treatments correspond to the five most frequently rated movies, and subpopulations correspond to the 14 demographic groups obtained from the Cartesian product of gender and age group. Thus, in this experiment, n = 5 and k = 14, yielding nk = 70 different treatment-subpopulation reward distributions. When an algorithm selects treatment a for subpopulation j, the environment samples uniformly with replacement from the historical ratings matching (a, j) and returns the sampled rating as the reward. The population weights pj and the mean rewards µa,j are computed from the empirical frequencies and cell averages of the filtered dataset. For more details see Appendix C. Within each subpopulation, we instantiate the standard bandit subroutine in two ways: Uniform, which samples the available treatments uniformly, and UCB, which uses the standard upper-confidencebound rule. Both are known to achieve the optimal simple regret rate up to logarithmic factors. We compare three policy classes: fully passive, fully active with known p using the optimal allocation 2/3 proportional to pj , and EETC. For each policy class, we report results with both subroutines, yielding six methods in total. Results. Table 1 reports the simple regret after horizons T ∈ {2500, 5000, 10000, 15000}, averaged over 50 independent runs, together with confidence intervals. Across both subroutines, the passive policies perform worst, while EETC and the known-p active policies achieve clearly smaller regret. 9

Table 1: Simple regret on the MovieLens 1M instance [HK15]. Each entry reports mean ± 95% confidence interval over 50 independent runs. All values are multiplied by 100 for readability. Method

T = 2500

T = 5000

T = 10000

T = 15000

Passive + Uniform EETC + Uniform Known-p Active + Uniform

3.76 ± 0.53 3.52 ± 0.52 2.99 ± 0.51

2.05 ± 0.32 1.85 ± 0.32 1.78 ± 0.37

1.10 ± 0.23 0.81 ± 0.25 0.74 ± 0.17

0.75 ± 0.13 0.59 ± 0.13 0.56 ± 0.14

Passive + UCB EETC + UCB Known-p Active + UCB

2.53 ± 0.37 2.57 ± 0.37 2.28 ± 0.46

1.29 ± 0.23 0.97 ± 0.17 0.88 ± 0.21

0.71 ± 0.13 0.41 ± 0.11 0.49 ± 0.12

0.47 ± 0.11 0.33 ± 0.10 0.31 ± 0.07

Moreover, as the horizon increases, the performance of EETC becomes very close to that of the known-p active benchmark. These results consistent with the theory showcase that estimating p from passive observations and then switching to an active allocation is more efficient than remaining fully passive, and that EETC can closely approach the performance of the optimal known-p active policy.

6

Conclusion

We studied the bandit with subpopulations problem with a context-weighted simple regret objective and quantified the benefit of actively choosing which subpopulation to sample. We showed that active subpopulation selection always improves performance over passive sampling, characterized the extent of this improvement, and proved the optimality of a simple history-free allocation rule up to constant factors. Moreover, we extended the analysis to settings with a limited intervention budget and unknown subpopulation distribution. In the latter case, we proposed the EETC algorithm that balances passive estimation with active allocation rounds and for long horizons matches the performance of the optimal fully active policy which knows the population distribution. An interesting direction for future work is to develop gap-dependent guarantees for the same problem. In such a setting, optimal algorithms may allocate fewer samples to subpopulations where the best treatment is easy to identify, leading to allocation rules that differ from the worst-case ones studied here. Another possible extension is to consider models where the context is observed only after the treatment is chosen, inspired by related contextual and causal bandit settings [RKB+ 21, LLR16, SARK25].

References [AB09] Jean-Yves Audibert and Sébastien Bubeck. Minimax policies for adversarial and stochastic bandits. In Colt, pages 217–226, 2009. [BBS09] Steffen Bickel, Michael Brückner, and Tobias Scheffer. Discriminative learning under covariate shift. Journal of Machine Learning Research, 10(9), 2009. [BCB+ 12] Sébastien Bubeck, Nicolo Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends® in Machine Learning, 5(1):1–122, 2012. [BMS09] Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration in multi-armed bandits problems. In International conference on Algorithmic learning theory, pages 23–37. Springer, 2009. [CHVDS23] Alicia Curth, Alihan Hüyük, and Mihaela Van Der Schaar. Adaptive identification of populations with treatment benefit in clinical trials: machine learning challenges and solutions. In International Conference on Machine Learning, pages 6603–6622. PMLR, 2023. [DP09] Devdatt P Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009. [DSC+ 18] Aniket Anand Deshmukh, Srinagesh Sharma, James W Cutler, Mark Moldwin, and Clayton Scott. Simple regret minimization for contextual bandits. arXiv preprint arXiv:1810.07371, 2018. 10

[FJB+ 19] Adam Foster, Martin Jankowiak, Elias Bingham, Paul Horsfall, Yee Whye Teh, Thomas Rainforth, and Noah Goodman. Variational bayesian optimal experimental design. Advances in neural information processing systems, 32, 2019. [GGLB11] Victor Gabillon, Mohammad Ghavamzadeh, Alessandro Lazaric, and Sébastien Bubeck. Multi-bandit best arm identification. Advances in Neural Information Processing Systems, 24, 2011. [GKK16] Aurélien Garivier, Emilie Kaufmann, and Wouter M Koolen. Maximin action identification: A new bandit framework for games. In Conference on Learning Theory, pages 1028–1050. PMLR, 2016. [HK15] F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis), 5(4):1–19, 2015. [HLP52] G. H. Hardy, J. E. Littlewood, and G. Pólya. Inequalities. Cambridge University Press, 2 edition, 1952. [JEK24] Fateme Jamshidi, Jalal Etesami, and Negar Kiyavash. Confounded budgeted causal bandits. In Causal Learning and Reasoning, pages 423–461. PMLR, 2024. [JLB22] Matthew Jörke, Jonathan Lee, and Emma Brunskill. Simple regret minimization for contextual bandits using bayesian optimal experimental design. In ICML2022 Workshop on Adaptive Experimental Design and Active Learning in the Real World, 2022. [KIIK22] Masahiro Kato, Masaaki Imaizumi, Takuya Ishihara, and Toru Kitagawa. Best arm identification with contextual information under a small gap. arXiv preprint arXiv:2209.07330, 2022. [KOIK24] Masahiro Kato, Kyohei Okumura, Takuya Ishihara, and Toru Kitagawa. Adaptive experimental design for policy learning. arXiv preprint arXiv:2401.03756, 2024. [KZAB23] Sanath Kumar Krishnamurthy, Ruohan Zhan, Susan Athey, and Emma Brunskill. Proportional response: Contextual bandits for simple and cumulative regret minimization. Advances in Neural Information Processing Systems, 36:30255–30266, 2023. [LB18] Sanghack Lee and Elias Bareinboim. Structural causal bandits: Where to intervene? Advances in neural information processing systems, 31, 2018. [LBA+ 26] Shuai Liu, Alireza Bakhtiari, Alex Ayoub, Botao Hao, and Csaba Szepesvári. Efficient simple regret algorithms for stochastic contextual bandits. arXiv preprint arXiv:2601.21167, 2026. [LLR16] Finnian Lattimore, Tor Lattimore, and Mark D Reid. Causal bandits: Learning good interventions via causal inference. Advances in neural information processing systems, 29, 2016. [LMTY20] Yangyi Lu, Amirhossein Meisami, Ambuj Tewari, and William Yan. Regret analysis of bandit problems with causal background knowledge. In Conference on Uncertainty in Artificial Intelligence, pages 141–150. PMLR, 2020. [LS20] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020. [MNS22] Aurghya Maiti, Vineet Nair, and Gaurav Sinha. A causal bandit approach to learning good atomic interventions in presence of unobserved confounders. In Uncertainty in Artificial Intelligence, pages 1328–1338. PMLR, 2022. [NPS21] Vineet Nair, Vishakha Patil, and Gaurav Sinha. Budgeted and non-budgeted causal bandits. In International Conference on Artificial Intelligence and Statistics, pages 2017–2025. PMLR, 2021. [PR13] Vianney Perchet and Philippe Rigollet. The multi-armed bandit problem with covariates. THE ANNALS of STATISTICS, pages 693–721, 2013. 11

[RKB+ 21] Yoan Russac, Christina Katsimerou, Dennis Bohle, Olivier Cappé, Aurélien Garivier, and Wouter M Koolen. A/b/n testing with control in the presence of subpopulations. Advances in Neural Information Processing Systems, 34:25100–25110, 2021. [RV24] Alessio Russo and Filippo Vannella. Fair best arm identification with fixed confidence. In 2024 IEEE 63rd Conference on Decision and Control (CDC), pages 1173–1180. IEEE, 2024. [SARK25] Mohammad Shahverdikondori, Amir Mohammad Abouei, Alireza Rezaeimoghadam, and Negar Kiyavash. Optimal best arm identification with post-action context. arXiv preprint arXiv:2502.03061, 2025. [SBC19] Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher. Overlapping multi-bandit best arm identification. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 2544–2548. IEEE, 2019. [SBK25] Mohammad Shahverdikondori, Mohammad Reza Badri, and Negar Kiyavash. Best group identification in multi-objective bandits. arXiv preprint arXiv:2505.17869, 2025. [SEK25] Mohammad Shahverdikondori, Jalal Etesami, and Negar Kiyavash. Graph learning is suboptimal in causal bandits. arXiv preprint arXiv:2510.16811, 2025. [WS22] Zhenlin Wang and Jonathan Scarlett. Max-min grouped bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8603–8611, 2022. [WZZ23] Yuhang Wu, Zeyu Zheng, and Tingyu Zhu. Best arm identification with fairness constraints on subpopulations. In 2023 Winter Simulation Conference (WSC), pages 540–551. IEEE, 2023. [ZSSJ23] Yao Zhao, Connor Stephens, Csaba Szepesvári, and Kwang-Sung Jun. Revisiting simple regret: Fast rates for returning a good arm. In International Conference on Machine Learning, pages 42110–42158. PMLR, 2023.

12

Appendix The appendix is organized as follows. Section A provides a more detailed discussion of related work. Section B contains the proofs omitted from the main text. Finally, Section C presents additional experimental details and results.

A

Further Discussion on Related Work

In this section, we provide some additional discussion of related work. Heterogeneous Treatment Effects and Subpopulation-Aware Decision Making. A central line of work studies how treatment heterogeneity across subpopulations fundamentally alters optimal experimental design and decision rules. [RKB+ 21] shows that ignoring heterogeneity across observed or latent subgroups can lead to systematically suboptimal or even misleading treatment selection, even when each arm is evaluated against a control. When outcomes vary across groups, the problem shifts from selecting a globally best arm to learning group-conditional policies, effectively turning A/B/n testing into a policy learning problem. This perspective is further developed in adaptive clinical trial settings by [CHVDS23], who propose methods to sequentially identify subpopulations with positive treatment effects under strict statistical constraints. Their work emphasizes adaptive refinement of target populations via procedures such as AdaGGI and AdaGCPI, focusing not on a single optimal subgroup but on any collection of beneficiaries. Complementing this line, [WZZ23] and [RV24] study best arm identification under fairness constraints across subpopulations. Unlike [RKB+ 21], which allows fully personalized policies, fairness requirements couple subpopulations by imposing performance constraints across groups. This fundamentally changes the decision problem: the goal is no longer purely optimal identification but balancing optimality with worst-case guarantees across groups, at the cost of increased sample complexity. Contextual and Policy Learning Bandits. A related but distinct literature incorporates observable covariates into sequential decision making. [PR13] extends the classical bandit setting to contextual information, where the goal is to learn a context-dependent policy rather than a single best arm. Under smoothness assumptions, they show that partition-based methods achieve minimax optimal regret by learning locally optimal actions within regions of the covariate space. In the small gap regime, [KIIK22] further studies best arm identification with context, showing that contextual structure can significantly reduce sample complexity when arms are hard to distinguish. The key difference is that efficiency gains arise only when contexts meaningfully separate arms; otherwise, learning remains intrinsically difficult. More generally, [KOIK24] shows that even in contextual settings, standard experimental designs are suboptimal when the goal is policy learning rather than estimation, and proposes adaptive designs that concentrate sampling in regions where policy decisions are most uncertain. Similarly, [DSC+ 18, JLB22] frame simple regret minimization in contextual bandits as a Bayesian experimental design problem where exploration is guided by expected information gain about the optimal policy rather than reward maximization. Beyond bandits, Bayesian optimal experimental design provides a general framework for sequential data acquisition. [FJB+ 19] develops scalable variational approximations to expected information gain, enabling BOED in complex models where exact computation is infeasible. These methods connect naturally to contextual bandits and policy learning approaches that also select experiments based on information gain rather than immediate reward. A complementary perspective arises in supervised learning under covariate shift which could be the result of different subpopulations. [BBS09] shows that distribution mismatch between training and test covariates biases standard empirical risk minimization, and proposes density-ratio reweighting to correct this issue. While outside the sequential decision-making setting, this line of work shares with contextual bandits and adaptive design the central idea that data collection and inference must be aligned with the target decision environment. Bandits with Grouped Arms. Our setting is also related to bandit problems with grouped arms. Indeed, each subpopulation can be viewed as a group of n treatment arms, so the learner effectively faces k groups and seeks to identify the best arm within each group. The closest line of work is multi-bandit best arm identification [GGLB11, SBC19], which studies identifying the best arm in 13

each of several bandits with the objective of minimizing the probability of misidentification. This is particularly close to our fully active setting, since both problems require allocating samples across several independent bandit instances. However, those works focus on best arm identification, whereas our objective is to minimize context-weighted simple regret. Other grouped arm formulations consider different objectives. Maximin action identification [GKK16] and max-min grouped bandits [WS22] study settings in which performance is determined by the worst arm or outcome within a group, while best group identification in multi-objective bandits [SBK25] focuses on identifying a single best group under multi-objective rewards. In contrast, our goal is not to identify one best group or action, but to recommend the best arm separately within every group. In addition, we characterize the gain obtained by actively choosing which group, that is, which subpopulation, to sample. Causal Bandits. Another related line of work is the general framework of causal bandits [LLR16, LB18, LMTY20, JEK24], where actions correspond to interventions on subsets of variables in a causal graph and the learner observes the reward together with the non-intervened variables; see [LLR16] for details. Our setting can be viewed as a simple causal bandit problem with three nodes: a treatment node, a subpopulation node, and a reward node, where the reward is affected by both the treatment and the subpopulation, while the two parent variables are independent. Under this interpretation, the passive setting corresponds to intervening only on the treatment node, whereas the active setting corresponds to intervening on both the treatment and subpopulation nodes. A related class of models in this literature is the parallel graph setting, in which several independent variables all directly affect the reward [LLR16, NPS21]. In [LLR16] the authors provide algorithms with simple regret guarantees for binary variables, while [NPS21] and [MNS22] study more general no-backdoor and general graphs and settings with intervention costs, and derive both simple and cumulative regret guarantees. Another related work studies best arm identification in a setting where the context is not independent of the treatment but is instead a random function of the chosen treatment [SARK25]. These works are structurally related to ours, but differ substantially in objective and in the type of interventions being compared. In particular, they focus on identifying a single globally best action, whereas our goal is to identify the best treatment separately for each subpopulation and to characterize the gain obtained by actively choosing both the treatment and the subpopulation, rather than only one of them. Another recent work has also studied the effect of the number of intervened nodes at each round, but the results are on cumulative regret in a setting where the causal structure is unknown [SEK25]. Extending our results to settings with multiple variables and richer causal structures would be an interesting future direction.

B

Omitted Proofs

This section presents the proofs omitted from the main text due to space constraints. We first start with a Lemma that will be used throughout the proofs. Lemma B.1 (Concentration of Independent Bernoulli Counts). Let X1 , . . . , Xm be independent Bernoulli random variables with means α1 , . . . , αm ∈ [0, 1]. Define Sm :=

m X

Xt ,

Mm := E[Sm ] =

t=1

m X t=1

If, for some η ∈ (0, 1),   2 Mm ≥ 24 ln , η then  P

Mm 3Mm ≤ Sm ≤ 2 2 14

 ≥ 1 − η.

αt .

Proof. Since X1 , . . . , Xm are independent Bernoulli random variables, possibly with different means, the multiplicative Chernoff bounds apply; see, e.g., [DP09]. In particular,     Mm Mm P Sm < ≤ exp − , 2 8     Mm 3Mm ≤ exp − . P Sm > 2 12 Therefore, by a union bound,       Mm 3Mm Mm Mm P ≤ Sm ≤ ≥ 1 − exp − − exp − 2 2 8 12   Mm ≥ 1 − 2 exp − . 24 Since Mm ≥ 24 ln(2/η), it follows that 

Mm 2 exp − 24 and hence

 P

 ≤ η,

Mm 3Mm ≤ Sm ≤ 2 2

 ≥ 1 − η.

Next, we introduce inequalities on the norms of vectors in Rk . These inequalities are standard; see, for example, [HLP52, Chapter 2]. Theorem B.2 (Comparison and Interpolation of ℓp Norms). For any vector x ∈ Rk and any exponents 0 < p < q < ∞, we have 1 1 ∥x∥q ≤ ∥x∥p ≤ k p − q ∥x∥q . More generally, for any 0 < p ≤ r ≤ q < ∞ and any θ ∈ [0, 1] such that θ 1−θ 1 = + , r p q we have

θ

1−θ

∥x∥r ≤ ∥x∥p ∥x∥q B.1 B.1.1

.

Proofs of Section 3 Proof of Lemma 3.1

Lemma 3.1 (Simple Regret Lower Bound). For any subpopulation distribution p ∈ ∆k−1 known to + the agent and any policy π ∈ Π(p), r n  SR(π, T, p) ∈ Ω ∥p∥2/3 . T Proof. Fix p ∈ ∆k−1 and an arbitrary policy π ∈ Π(p). + For each subpopulation j ∈ [k] and arm a ∈ [n], let Ta,j denote the number of times arm a is pulled in subpopulation j over the T rounds. For a family of instances defined below and indexed by ω, let X 1 X T̄a,j := k Eω [Ta,j ], T̄j := T̄a,j , 2 k a∈[n]

ω∈{0,1}

where Eω denotes expectation under instance V ω . For each j, choose bj ∈ arg min T̄a,j . a̸=1

15

Then, by the pigeonhole principle, T̄bj ,j ≤

T̄j . n−1

Now fix gaps δ1 , . . . , δk ∈ (0, 1/4], and consider the family of instances V := {V ω : ω ∈ {0, 1}k }, where rewards are Bernoulli and, for each ω = (ω1 , . . . , ωk ), the mean rewards are given by 1 if a = 1,  2 + δj , 1 µω + 2δ ω , if a = bj , j j a,j =  12 , otherwise. 2 Thus, in subpopulation j, the optimal arm is a∗j (ω) =



1, if ωj = 0, bj , if ωj = 1.

For any ω ∈ {0, 1}k , let SR(π, T, V ω ) denote the simple regret of π on instance V ω . Since recommending a non-optimal arm in subpopulation j incurs regret at least δj , we have X
SR(π, T, V ω ) ≥ pj δj Pω âT (j) ̸= a∗j (ω) , (9) j∈[k]

where Pω denotes the probability measure induced by the full interaction between π and V ω . Averaging over the family and using the fact that the worst-case regret dominates the average regret, we obtain 1 X SR(π, T, p) ≥ k SR(π, T, V ω ) 2 ω∈{0,1}k X ≥ pj δj ēj , (10) j∈[k]

where ēj :=

1 2k

X

Pω âT (j) ̸= a∗j (ω) .

ω∈{0,1}k

We now lower bound ēj . Fix j ∈ [k]. For ω with ωj = 0, let ω ¬j denote the vector obtained by flipping the j-th coordinate of ω, and let Bj := {âT (j) = 1}. ¬j

Under V ω , arm 1 is optimal in subpopulation j, while under V ω , arm bj is optimal. Therefore,

Pω âT (j) ̸= a∗j (ω) + Pω¬j âT (j) ̸= a∗j (ω ¬j ) ≥ Pω (Bjc ) + Pω¬j (Bj ). By the Bretagnolle–Huber inequality, Pω (Bjc ) + Pω¬j (Bj ) ≥

1 exp (−D(Pω , Pω¬j )) , 2

where D(·, ·) shows the KL divergence. Hence,

1 Pω âT (j) ̸= a∗j (ω) + Pω¬j âT (j) ̸= a∗j (ω ¬j ) ≥ exp (−D(Pω , Pω¬j )) . 2 Averaging (11) over all ω with ωj = 0 gives X 1 ēj ≥ k+1 exp (−D(Pω , Pω¬j )) . 2 ω:ω =0 j

16

(11)

(12)

¬j

We now control the KL terms. Since V ω and V ω differ only in the reward distribution of arm bj in subpopulation j, by KL divergence decomposition Lemma [LS20] we have   1 1 D(Pω , Pω¬j ) = Eω [Tbj ,j ] KL , + 2δj , 2 2 where KL (·, ·) denotes the Bernoulli KL divergence. Since δj ≤ 1/4, there exists a universal constant c0 > 0 such that   1 1 , + 2δj ≤ c0 δj2 , KL 2 2 and therefore D(Pω , Pω¬j ) ≤ c0 Eω [Tbj ,j ]δj2 . Using Jensen’s inequality in (12), we obtain   2 X c0 δj 1 ēj ≥ exp − k−1 Eω [Tbj ,j ] . 4 2 ω:ω =0 j

Since 1 2k−1

X

Eω [Tbj ,j ] ≤ 2T̄bj ,j ≤

ω:ωj =0

2T̄j , n−1

it follows that ēj ≥

  1 2c0 T̄j 2 exp − δj . 4 n−1

(13)

  2c0 T̄j 2 1 X pj δj exp − δj . 4 n−1

(14)

Substituting (13) into (10) gives SR(π, T, p) ≥

j∈[k]

We now optimize each term in (14) with respect to δj . For each j ∈ [k], we set s n−1 δj = . 4c0 T̄j Since we work in the data-rich regime and k and 1/pmin are treated as constants, we may assume T is large enough so that δj ≤ 1/4 for all j. Plugging the value of δj into (14), we obtain r X pj √ n X pj p ≥ c2 SR(π, T, p) ≥ c1 n − 1 (15) √ , T q̄j T̄j j∈[k] j∈[k] for universal constants c1 , c2 > 0, where q̄j :=

T̄j , T

X

q̄j = 1.

j∈[k]

It remains to optimize the right hand side of (15) over all q̄ ∈ ∆k−1 + . In the proof of Lemma 3.3, we show that the minimum of this optimization problem is achieved at the unique point q̄∗ with 2/3 q̄j∗ ∝ pj , and the optimal value is ∥p∥2/3 . Therefore, (15) yields r inf π∈Π(p)

SR(π, T, p) ∈ Ω

which completes the proof.

17

 n ∥p∥2/3 , T

(16)

B.1.2

Proof of Lemma 3.2

Lemma 3.2 (Simple Regret of History-Free Policies). For any history-free policy π ∈ Πhf (p) along with the subroutine ASR and expected subpopulation proportions q(π, p), if ∀j ∈ [k] : T q(π, p)j > 24 ln(2kT ), then r n X  p p j SR(π, T, p) ∈ Θ . T q(π, p)j j∈[k] Proof. For a history-free policy π ∈ Πhf (p), let Tj :=

T X

1{Ct = j}

t=1

denote the number of rounds in which subpopulation j is observed. Since the subpopulation selection rule is history-free, there exist deterministic probabilities {qt,j }t∈[T ], j∈[k] , depending only on p, such that X P(Ct = j) = qt,j , qt,j = 1 ∀t ∈ [T ]. j∈[k]

Hence Tj is a sum of independent Bernoulli random variables, and E[Tj ] =

T X

qt,j = T q(π, p)j .

t=1

We first prove the lower bound. We use the lower bound construction from the proof of Lemma 3.1. In that proof, for an arbitrary policy π, one constructs a family of hard instances and derives the bound   r X pj n SR(π, T, p) ∈ Ω  √ , T q̄j j∈[k]

where q̄j denotes the average fraction of rounds allocated to subpopulation j across the hard instance family. For a history-free policy, the subpopulation selection rule is independent of the observed history and therefore independent of the realized rewards and of the instance itself. Consequently, the allocation vector is the same on every instance in the family, and thus q̄j = q(π, p)j

∀j ∈ [k].

Substituting this into the lower bound from Lemma 3.1 yields   r X n p . p j SR(π, T, p) ∈ Ω  T q(π, p)j j∈[k]

(17)

We now prove the upper bound. For each j ∈ [k], define the event   T q(π, p)j 3T q(π, p)j Ej := ≤ Tj ≤ , 2 2 and let E :=

\

Ej .

j∈[k]

Since Tj is a sum of independent Bernoulli random variables with mean T q(π, p)j , Lemma B.1 with η = 1/kT implies that 1 P(Ej ) ≥ 1 − , kT where we use the assumption T q(π, p)j > 24 ln(2kT ). 18

Therefore, by a union bound, P(E c ) ≤

X

P(Ejc ) ≤

j∈[k]

1 . T

(18)

Fix any instance (ν, p). On the event E, each subpopulation j is observed at least T q(π, p)j /2 times. Since the subroutine ASR is anytime and achieves the optimal simple regret rate in Lemma 2.1, there exists a universal constant c1 > 0 such that the expected recommendation gap in subpopulation j is at most s r n 2n c1 ≤ c1 . Tj T q(π, p)j Therefore, on E, SR(π, T, (ν, p)) =

X

pj ∆j

j∈[k]

r ≤ c1

p 2n X p j . T q(π, p)j j∈[k]

On the complement event E c , the simple regret is at most 1, since rewards lie in [0, 1] and Hence r 2n X p p j SR(π, T, (ν, p)) ≤ c1 + P(E c ). T q(π, p) j j∈[k]

P

j pj = 1.

Taking the supremum over all instances and using (18), we obtain r 2n X p 1 p j SR(π, T, p) ≤ c1 + . T T q(π, p)j j∈[k] Finally, since q(π, p)j ≤ 1 for all j, we have X X p p j ≥ pj = 1, q(π, p)j j∈[k] j∈[k] and therefore the term 1/T is of smaller order than the main term. Thus,   r X n p . p j SR(π, T, p) ∈ O  T q(π, p)j j∈[k]

(19)

Combining (17) and (19) proves the claim. B.1.3

Proof of Lemma 3.3

Lemma 3.3 (Optimal Allocation for Active Policies). For any p ∈ ∆k−1 + , the unique minimizer of k−1 Sp (q) over q ∈ ∆+ is 2/3 pj q ∗ (p)j = P , j ∈ [k]. 2/3 ℓ∈[k] pℓ Moreover, Sp (q∗ (p)) = ∥p∥2/3 . Proof. Recall that Sp (q) =

X pj √ , qj

q ∈ ∆k−1 + .

j∈[k]

−1/2

Since pj > 0 for all j ∈ [k], each term pj qj is strictly convex on (0, ∞). Therefore, Sp is strictly k−1 convex on ∆+ . Hence, if a minimizer exists, it is unique. 19

We now characterize this minimizer. Since pj > 0 for all j, we have pj √ → +∞ qj

as qj ↓ 0.

Therefore, the minimum over the simplex cannot be attained on the boundary, and the minimizer must lie in the interior. Thus, we may use the first order optimality conditions for the equality-constrained problem X pj min √ qj q∈Rk j∈[k] X s.t. qj = 1, qj > 0 ∀j ∈ [k]. j∈[k]

Consider the Lagrangian  L(q, λ) =

X

−1/2

pj qj

 X

+ λ

j∈[k]

qj − 1  .

j∈[k]

At the optimum, for each j ∈ [k], ∂L 1 −3/2 + λ = 0. = − pj qj ∂qj 2 Hence −3/2

qj

=

2λ , pj

which implies qj =

 p 2/3 j

2λ

.

Therefore, there exists a constant c > 0 such that 2/3

∀j ∈ [k].

qj = c p j Using the constraint

P

j∈[k] qj = 1, we obtain

1=

X

X

qj = c

j∈[k]

2/3

pj ,

j∈[k]

and thus 1

c= P

2/3 l∈[k] pl

.

Substituting back gives 2/3

pj

qj∗ (p) = P

2/3 l∈[k] pl

,

j ∈ [k].

Since Sp is strictly convex on ∆k−1 + , this minimizer is unique. Then, by substituting this back to Sp (q), we obtain 3/2

 Sp (q∗ (p)) = 

X

2/3 pj 

j∈[k]

20

= ∥p∥2/3 .

B.1.4

Proof of Lemma 3.5

Lemma 3.5 (Active–Passive Gap). For every p ∈ ∆k−1 R(p) ∈ + , R(p) ≥ 1. Moreover, supp∈∆k−1 + 1
Θ k 4 , and this order is tight. Proof. Recall that 1/2

R(p) =

∥p∥1/2 ∥p∥2/3

.

√ We first show that R(p) ≥ 1 for every p ∈ ∆k−1 pj for all j ∈ [k], and let + . Let aj := a = (a1 , . . . , ak ). Then X√ X 1/2 2 ∥a∥1 = pj = ∥p∥1/2 , ∥a∥2 = pj = 1, j∈[k]

j∈[k]

and

3/2

 2

∥a∥4/3 = 

X

2/3 pj 

= ∥p∥2/3 .

j∈[k]

Applying the interpolation part of Theorem B.2 with p = 1, r = 4/3, q = 2, and θ = 1/2, we obtain 1/2

∥a∥4/3 ≤ ∥a∥1

1/2

∥a∥2

.

Since ∥a∥2 = 1, this yields 1/2

2

∥p∥2/3 = ∥a∥4/3 ≤ ∥a∥1 = ∥p∥1/2 , and hence R(p) ≥ 1. For the upper bound, applying the comparison part of Theorem B.2 with p = 1/2 and q = 2/3 gives ∥p∥1/2 ≤ k 1/2 ∥p∥2/3 . Taking square roots and using ∥p∥2/3 ≥ ∥p∥1 = 1, we obtain 1/2

∥p∥1/2 ≤ k 1/4 ∥p∥2/3 , which implies R(p) ≤ k 1/4 . It remains to prove the matching lower bound. For k = 1, the claim is trivial, so assume k ≥ 2. Consider the family of probability vectors   ε ε p(ε) = 1 − ε, ,..., , ε ∈ (0, 1). k−1 k−1 Choose ε= √

1 . k−1

Then (ε)

1/2

p

=

√

r 1 − ε + (k − 1)

1/2

p √ ε = 1 − ε + ε(k − 1) ≥ (k − 1)1/4 . k−1

On the other hand, (ε)

p

2/3 !3/2 ε = (1 − ε) + (k − 1) k−1 2/3  3/2 = (1 − ε)2/3 + (k − 1)1/3 ε2/3 . 

2/3

21

With ε = (k − 1)−1/2 , we have (k − 1)1/3 ε2/3 = 1, and therefore

 3/2 √ = (1 − ε)2/3 + 1 ≤ 23/2 = 8.

p(ε) 2/3

Combining the two bounds yields 1/2



(ε)

R p Hence



=

p(ε) 1/2 p(ε)

≥

2/3

(k − 1)1/4 √ . 8

  sup R(p) ∈ Ω k 1/4 . p∈∆k−1 +

Combining the upper and lower bounds, we conclude that   sup R(p) ∈ Θ k 1/4 , p∈∆k−1 +

and this order is tight. B.1.5

Proof of Theorem 3.6

Theorem 3.6 (Simple Regret of Algorithm 1). For every p ∈ ∆k−1 + , Algorithm 1 is a history-free policy in Πα (p) with expected subpopulation proportions equal to q∗α (p). Consequently, when T is large, its worst-case simple regret satisfies the optimal rate r
n ∗ SR(Alg.1, T, p) ∈ O v (p) . T α Proof. For simplicity, assume that αT is an integer. Replacing αT by ⌊αT ⌋ changes the number of passive and active rounds by at most one and therefore does not affect the regret rate. We first characterize the optimizer of min

q∈∆k−1 +

s.t.

X pj √ qj

Sp (q) =

(20)

j∈[k]

qj ≥ (1 − α)pj ,

∀j ∈ [k].

P P When α = 0, the constraints reduce to qj ≥ pj for all j, and since j qj = j pj = 1, the feasible set contains only the point q = p. Hence q∗α (p) = p, and the claim is immediate. We therefore assume in the remainder of the proof that α ∈ (0, 1]. Since ∆k−1 is not compact, we instead consider the same problem over the closed simplex ∆k−1 . + The feasible set   Qα := q ∈ ∆k−1 : qj ≥ (1 − α)pj , ∀j ∈ [k] is compact and nonempty, so the minimum is attained on Qα . Moreover, because each pj > 0, pj √ → +∞ qj

as qj ↓ 0.

Hence the minimizer cannot lie on the boundary {qj = 0}, and therefore lies in ∆k−1 + . Thus the minimizer over Qα is also the minimizer of (20). −1/2

The objective is strictly convex on ∆k−1 + , since each map qj 7→ pj qj Hence the minimizer is unique. We now derive its form. Let bj := (1 − α)pj , 22

j ∈ [k].

is strictly convex on (0, ∞).

By the KKT conditions, there exist λ ∈ R and multipliers νj ≥ 0 such that 1 −3/2 − pj qj + λ − νj = 0, νj (bj − qj ) = 0, qj ≥ bj . 2 Therefore, if qj > bj , then νj = 0 and  p 2/3 j 2/3 = c pj qj = 2λ for some constant c > 0. If qj = bj , then the lower bound constraint is active. Hence the unique optimizer must be of the form 2/3
qα∗ (p)j = max (1 − α)pj , c∗ pj , j ∈ [k], for some constant c∗ ≥ 0. To determine c∗ , define F (c) :=

2/3

X

max (1 − α)pj , cpj

.

j∈[k]

Then F is continuous and nondecreasing on [0, ∞). Moreover, since α > 0, X F (0) = (1 − α)pj = 1 − α < 1, j∈[k]

and clearly F (c) → ∞ as c → ∞. Hence there exists at least one c∗ ≥ 0 such that F (c∗ ) = 1. 1/3

We now show uniqueness. Let pmin := minj pj . If c < pmin , then for every j ∈ [k], 2/3

cpj

1/3 2/3

< pmin pj

≤ pj ,

and therefore

(1 − α)pj < pj , 2/3

max (1 − α)pj , cpj

< pj .

1/3 1/3 Summing over j gives F (c) < 1 for all c < pmin . On the other hand, for c ≥ pmin , the coordinate corresponding to pmin is already on the linear branch, so F has strictly positive slope and is therefore 1/3 1/3 strictly increasing on [pmin , ∞). Since F (c) < 1 for all c < pmin and F is strictly increasing ∗

afterwards, the equation F (c) = 1 has a unique solution c . Thus,

2/3

qα∗ (p)j = max (1 − α)pj , c∗ pj is indeed the unique optimizer of (20).

,

j ∈ [k],

We now show that Algorithm 1 has expected subpopulation proportions equal to q∗α (p). By construction, the algorithm computes the same constant c∗ and sets 2/3

qj∗ = max (1 − α)pj , c∗ pj

= qα∗ (p)j ,

rj =

qj∗ − (1 − α)pj . α

Since qj∗ ≥ (1 − α)pj , we have rj ≥ 0, and P P ∗ X 1 − (1 − α) j∈[k] qj − (1 − α) j∈[k] pj rj = = = 1, α α j∈[k]

so r ∈ ∆k−1 + . During the first (1 − α)T rounds, the algorithm samples subpopulations according to p, hence the expected number of observations of subpopulation j in this phase is (1 − α)T pj . During the remaining αT rounds, the algorithm samples according to r, so the expected number of observations of subpopulation j in the active phase is αT rj = αT ·

qj∗ − (1 − α)pj = T qj∗ − (1 − α)pj . α 23

Therefore the total expected number of observations of subpopulation j is
(1 − α)T pj + T qj∗ − (1 − α)pj = T qj∗ . Hence the expected subpopulation proportions of Algorithm 1 are exactly q(Alg.1, p) = q∗ = q∗α (p). The subpopulation selection rule of the algorithm depends only on p, α, and the deterministic vector r. It is therefore independent of the observed history, so the algorithm is history-free. Moreover, it is passive for exactly (1 − α)T rounds and active for exactly αT rounds, hence it belongs to Πα (p). 1/3

We next verify the condition of Lemma 3.2. Since c∗ ≥ pmin by the argument above, for every j ∈ [k], 2/3
2/3 1/3 2/3 qα∗ (p)j = max (1 − α)pj , c∗ pj ≥ c∗ pj ≥ pmin pj ≥ pmin . Thus

min qα∗ (p)j ≥ pmin .

j∈[k]

Since we work in the data rich regime and assume T ≫ 1/pmin , it follows that, T qα∗ (p)j > 24k ln(2T ),

∀j ∈ [k].

We then apply Lemma 3.2 with q(π, p) = q∗α (p) to obtain  r n X p p j SR(Alg.1, T, p) ∈ O T qα∗ (p)j j∈[k] r n  Sp (q∗α (p)) . =O T By definition of vα∗ (p) as the optimal value of (20), Sp (q∗α (p)) = vα∗ (p). Hence SR(Alg.1, T, p) ∈ O

r n T

 vα∗ (p) .

This proves the theorem. B.1.6

Proof of Lemma 3.7

Lemma 3.7 (Threshold Budget αmin (p)). For a given p ∈ ∆k−1 + , let αmin (p) := 1 − −1/3 P 2/3 pmax / j∈[k] pj , where pmax = maxj pj . Then, for every α ∈ [αmin (p), 1], we have vα∗ (p) = ∥p∥2/3 . Consequently, for every such α, the simple regret bound of Algorithm 1 matches the optimal rate of fully active policies, which is also the optimal rate over all policies. Proof. Recall that the optimal value vα∗ (p) is defined as the minimum of X pj min Sp (q) = √ k−1 qj q∈∆+ j∈[k]

s.t.

qj ≥ (1 − α)pj ,

∀j ∈ [k].

By Lemma 3.3, the unique minimizer of the unconstrained problem over ∆k−1 is + 2/3

qjact := P

pj

2/3 ℓ∈[k] pℓ

,

j ∈ [k],

and its objective value is Sp (qact ) = ∥p∥2/3 . 24

(21)

We claim that qact is feasible for (21) whenever α ≥ αmin (p). Indeed, the feasibility condition is qjact ≥ (1 − α)pj ,

∀j ∈ [k],

which is equivalent to 2/3

pj

2/3 ℓ∈[k] pℓ

P

≥ (1 − α)pj ,

∀j ∈ [k].

Since pj > 0, dividing by pj gives −1/3

pj

2/3 ℓ∈[k] pℓ

P

≥ 1 − α,

∀j ∈ [k].

Equivalently, −1/3

1 − α ≤ min P j∈[k]

pj

2/3

.

ℓ∈[k] pℓ

Now the function x 7→ x−1/3 is decreasing on (0, ∞), so −1/3

= p−1/3 max ,

min pj

j∈[k]

where pmax = maxj pj . Therefore, −1/3

−1/3

pj

pmax =P . 2/3 2/3 ℓ∈[k] pℓ ℓ∈[k] pℓ

min P

j∈[k]

Hence the feasibility condition becomes −1/3

1−α≤ P

pmax

2/3 ℓ∈[k] pℓ

,

or equivalently −1/3

α≥1− P

pmax

2/3 ℓ∈[k] pℓ

= αmin (p).

Thus, for every α ∈ [αmin (p), 1], the fully active optimizer qact is feasible for the budgeted problem (21). Since (21) minimizes the same objective Sp as the fully active problem, but over a smaller feasible set, its optimal value is at least the unconstrained optimum: vα∗ (p) ≥ ∥p∥2/3 . On the other hand, when α ≥ αmin (p), the vector qact is feasible, and therefore vα∗ (p) ≤ Sp (qact ) = ∥p∥2/3 . Combining the two inequalities yields vα∗ (p) = ∥p∥2/3 ,

∀α ∈ [αmin (p), 1].

The final statement follows immediately from Theorem 3.6: for every α ∈ [αmin (p), 1], Algorithm 1 satisfies r n  r n  ∗ SR(Alg.1, T, p) ∈ O vα (p) = O ∥p∥2/3 . T T This is exactly the optimal rate of fully active policies, which, by Lemma 3.1, is also the optimal rate over all policies up to constant factors. B.2

Proofs of Section 4

This section presents the omitted proofs of Section 4 of the main text. 25

B.2.1

Proof of Theorem 4.1

Theorem 4.1 (Simple Regret of EETC). For sufficiently large horizon T , the worst-case simple regret of EETC is r
n ∥p∥2/3 . SR(EETC, T, p) ∈ O T Proof. We analyze a slightly modified version of EETC in which the passive phase ends at time τ2 − 1, the frozen estimate is p̂fr := p̂(τ2 − 1), and the active phase starts at round τ2 . Compared to the algorithm as stated, this removes the single wasted passive round at time τ2 . This changes the number of samples collected from each subpopulation by at most one and therefore does not affect the regret rate. We will therefore ignore this one round discrepancy in the remainder of the proof. et )t∈[T ] of i.i.d. draws from To analyze the stopping times, consider an auxiliary passive sequence (C p. Up to time τ2 − 1, EETC observes exactly the prefix of this sequence, so both stopping times et )t∈[T ] . For t ∈ [T ] and j ∈ [k], define τ1 , τ2 are measurable functions of (C et,j := N

t X

p̂t,j :=

es = j}, 1{C

s=1

et,j N . t

We first show that after O(log T ) passive rounds, the empirical proportions are uniformly accurate. Let   24 ln(2kT 2 ) mT := , pmin := min pj . pmin j∈[k] Since pmin > 0 is fixed, mT ∈ O(log T ). et,j is binomial with mean tpj ≥ mT pmin ≥ For each fixed t ≥ mT and j ∈ [k], the count N 2 24 ln(2kT ). Hence, by Lemma B.1,   tpj et,j ≤ 3tpj ≥ 1 − 1 . ≤N P 2 2 kT 2 Define the event G1 :=

T \

\  tpj 2

t=mT j∈[k]

et,j ≤ ≤N

 3tpj . 2

By a union bound over at most kT pairs (t, j), P(G1c ) ≤

T k X X 1 1 ≤ . 2 kT T t=m j=1

(22)

T

We next record the consequences of G1 . First, on G1 , for every j ∈ [k], em ,j ≥ mT pj ≥ mT pmin ≥ 12 ln(2kT 2 ) > ln(kT 2 ), N T 2 2 and therefore, by the definition of τ1 , τ1 ≤ mT ∈ O(log T ).

(23)

We now show that the frozen estimate p̂fr is accurate. Define −1/3

β(u) := 1 − αmin (u) = P

umax

2/3 j∈[k] uj

26

,

umax := max uj . j

We first note that β(u) admits a uniform positive lower bound over all probability vectors u ∈ ∆k−1 . Indeed, since umax ≤ 1, we have u−1/3 max ≥ 1. Moreover, since x 7→ x2/3 is concave on [0, ∞), Jensen’s inequality gives  2/3  2/3 X X 1 1 1 2/3 uj ≤  uj  = . k k k j∈[k]

j∈[k]

Multiplying both sides by k yields X

2/3

uj

≤ k 1/3 .

j∈[k] k−1

Hence, for every u ∈ ∆

, β(u) ≥ k −1/3 .

(24)

Since mT = O(log T ), for sufficiently large T we have mT < k −1/3 . T Combining this with (24), we obtain mT t ≤ < k −1/3 ≤ β(p̂t ), T T

∀t ≤ mT .

Therefore, the stopping condition defining τ2 cannot be satisfied at any time t ≤ mT , and thus τ2 > mT .

(25)

On the other hand, on the event G1 , we have for every t ∈ [mT , T ] and every j ∈ [k], pj 3pj ≤ p̂t,j ≤ . 2 2

(26)

Since (25) implies τ2 − 1 ≥ mT , it follows from (26) that, on G1 , 3pj pj ≤ p̂fr , j ≤ 2 2

∀j ∈ [k].

(27)

This implies 2/3

2−2/3 pj

2/3 ≤ (p̂fr ≤ j)

 2/3 3 2/3 pj . 2

Summing over j and raising to the power 3/2 proves 3 1 ∥p∥2/3 ≤ p̂fr 2/3 ≤ ∥p∥2/3 . 2 2

(28)

We now analyze phase (III). Let τ2 − 1 . T By the definition of τ2 and the modified algorithm, we have s :=

s ≤ β(p̂fr ) = 1 − αmin (p̂fr ). Therefore, by Lemma 3.7, the optimizer of the budgeted problem with passive fraction s and distribution p̂fr coincides with the fully active optimizer for p̂fr , namely qj = P

2/3 (p̂fr j) , fr 2/3 ℓ∈[k] (p̂ℓ )

27

j ∈ [k].

(29)

This is exactly the vector used by the algorithm in the active phase, and the active phase sampling probabilities are then qj − sp̂fr j rj = . 1−s We next show that the final number of observations of each subpopulation is of order T qj with high probability. For j ∈ [k], t ∈ [T ], let Nt,j :=

t X

1{Cs = j}

s=1

denote the number of times EETC observes subpopulation j by time t. Conditional on p̂fr and τ2 , the passive counts are fixed and equal to Nτ2 −1,j = sT p̂fr j. Let Aj denote the number of times subpopulation j is selected during the active phase. Conditional on p̂fr and τ2 , the variable Aj is a sum of independent Bernoulli random variables with mean Mj := T (qj − sp̂fr j ). Define Jbig := [j ∈ [k] : Mj ≥ 24 ln(2kT )] , Jsmall := [k] \ Jbig . For each j ∈ Jbig , Lemma B.1 with η = 1/(kT ) gives   Mj 1 p̂fr , τ2 ≥ 1 − . P Aj ≥ 2 kT Let

 \  Mj G2 := . Aj ≥ 2 j∈Jbig

fr

Then, conditional on (p̂ , τ2 ), a union bound gives P(G2c | p̂fr , τ2 ) ≤

1 . T

Taking expectation with respect to (p̂fr , τ2 ) yields   1 P(G2c ) = E P(G2c | p̂fr , τ2 ) ≤ . T

(30)

We claim that on G1 ∩ G2 , T qj , 2

NT,j ≥

∀j ∈ [k].

Indeed, if j ∈ Jbig , then on G2 , Mj 2 fr T (qj + sp̂fr T (q − sp̂ ) T qj j j) j = sT p̂fr = ≥ . j + 2 2 2 If j ∈ Jsmall , then Mj < 24 ln(2kT ). We also have fr NT,j = sT p̂fr j + Aj ≥ sT p̂j +

NT,j ≥ sT p̂fr j = T qj − Mj . Moreover, from (29), 2/3 (p̂fr j) ≥ p̂frmin , fr )2/3 (p̂ ℓ∈[k] ℓ

qj = P because

X

(p̂frℓ )2/3 ≤ (p̂frmin )−1/3

ℓ∈[k]

X ℓ∈[k]

28

p̂frℓ = (p̂frmin )−1/3 .

(31)

Together with (27), this implies qj ≥ p̂frmin ≥

pmin . 2

Since T ≫ 1/pmin , k, we have T pmin ≥ 48 ln(2kT ), 2

T qj ≥ and therefore, for j ∈ Jsmall ,

NT,j ≥ T qj − Mj ≥ T qj − 24 ln(2kT ) ≥

T qj . 2

This proves (31). Now fix an arbitrary instance. Let ∆j denote the recommendation gap in subpopulation j at the end of the horizon. Since the bandit subroutine ASR is anytime and achieves the optimal standard bandit simple regret rate, there exists a universal constant c3 > 0 such that, conditional on NT,j , r n E[∆j | NT,j ] ≤ c3 . NT,j Therefore, SR(EETC, T, p) =

X

pj E[∆j ]

j∈[k]

=

X

pj E[∆j 1G1 ∩G2 ] +

j∈[k]

≤ c3

X

pj E[∆j 1(G1 ∩G2 )c ]

j∈[k]

r

X

pj E

j∈[k]

 n 1G ∩G + P((G1 ∩ G2 )c ). NT,j 1 2

Using (31), this yields r SR(EETC, T, p) ≤ c3

2n X pj c √ + P((G1 ∩ G2 ) ). T qj

(32)

j∈[k]

It remains to bound the sum. By (29),  1/2 X pj X X −1/3 (p̂frℓ )2/3  pj (p̂fr . √ = j) qj j∈[k]

ℓ∈[k]

(p̂frℓ )2/3 ≤

 2/3 X 3 2/3 pℓ , 2

j∈[k]

From (27), X ℓ∈[k]

−1/3

−1/3 (p̂fr ≤ 21/3 pj j)

.

ℓ∈[k]

Therefore,  1/2 X 2/3 X 2/3 X pj 1/3 pℓ  pj √ ≤3  qj ℓ∈[k]

j∈[k]

1/3

=3

j∈[k]

∥p∥2/3 .

(33)

Finally, by (22) and (30), P((G1 ∩ G2 )c ) ≤ P(G1c ) + P(G2c ) ≤

2 . T

Substituting this and (33) into (32), we obtain r SR(EETC, T, p) ≤ c4 29

n 2 ∥p∥2/3 + T T

×10 3

Effect of Intervention Budget

6.5

-Active + UCB (95% CI)

Final simple regret

Final simple regret

16 14 12 10

0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0

×10 3

Effect of Intervention Budget -Active + UCB (95% CI)

6.0 5.5 5.0 4.5 4.0 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0

Intervention budget

Intervention budget

(a) T = 5000

(b) T = 10000

Figure 2: Simple regret of the budgeted active algorithm on the MovieLens instance as a function of the intervention budget α. As predicted by the theory, the regret decreases as the active budget increases, interpolating between the passive and fully active regimes. for a universal constant c4 > 0. Hence, for sufficiently large T , r n  SR(EETC, T, p) ∈ O ∥p∥2/3 . T The final claim follows from the known-p analysis: the optimal fully active policy that knows p achieves rate  r n ∥p∥2/3 , Θ T and this also matches the known-p lower bound up to constant factors. Therefore EETC achieves the same simple regret rate, up to constants, as the optimal fully active known-p policy.

C

Additional Experiments

This section provides additional details for the real-world experiment on the MovieLens dataset described in the main text, together with further experimental results. C.1

Details of the MovieLens Dataset

Our real-world experiment is based on the MovieLens 1M dataset, which contains 1,000,209 ratings from 6,040 users on roughly 3,900 movies. We construct a bandit instance by restricting attention to the five most frequently rated movies in the dataset, namely American Beauty (1999), Star Wars: Episode IV - A New Hope (1977), Star Wars: Episode V - The Empire Strikes Back (1980), Star Wars: Episode VI - Return of the Jedi (1983), and Jurassic Park (1993). These five movies define the treatment set, so that n = 5. The subpopulations are defined by the Cartesian product of gender and age group, yielding 2 × 7 = 14 demographic groups and therefore k = 14 subpopulations. After filtering the data to the selected movies and joining with the demographic attributes, the resulting dataset contains 14,964 rating records. Each record consists of a treatment–subpopulation pair together with the corresponding MovieLens rating, which we use directly as the reward. Thus, rewards take values in {1, 2, 3, 4, 5}. For each subpopulation j, the population weight pj is estimated by the empirical fraction of filtered records belonging to that group. The resulting subpopulation distribution is p = (0.0084, 0.0444, 0.0863, 0.0456, 0.0216, 0.0165, 0.0088, 0.0233, 0.1549, 0.2994, 0.1474, 0.0558, 0.0539, 0.0336). The coordinates are ordered by gender and age group, with the seven female groups first and the seven male groups second: (F, Under 18), (F, 18–24), (F, 25–34), (F, 35–44), (F, 45–49), (F, 50–55), (F, 56+), (M, Under 18), (M, 18–24), (M, 25–34), (M, 35–44), (M, 45–49), (M, 50–55), (M, 56+). 30

Similarly, for each treatment–subpopulation pair (a, j), the mean reward µa,j is computed as the empirical average of the corresponding ratings in the filtered dataset. During interaction, when an algorithm selects treatment a for subpopulation j, the environment samples uniformly with replacement from the historical ratings associated with (a, j) and returns the sampled rating as the reward. At the end of the horizon, each algorithm recommends one treatment for every subpopulation, and performance is evaluated using the context-weighted simple regret defined in the main text, with the empirical MovieLens frequencies and empirical cell means used as the ground-truth values. C.2

Budgeted Interventions on MovieLens

We next evaluate the budgeted active algorithm on the MovieLens instance [HK15]. In this experiment, we vary the intervention budget α from 0 to 1 in increments of 0.1, where α = 0 corresponds to the fully passive policy and α = 1 to the fully active policy. We report results for two horizons, T = 5000 and T = 10000, and for UCB as the standard bandit subroutine. Figure 2 shows the average simple regret over 100 independent runs, together with 95% confidence intervals. Although the curves are somewhat noisy due to the variance of the real data environment, both figures clearly exhibit the expected decreasing trend: as the intervention budget α increases, the simple regret decreases. This is consistent with the theory, which predicts that allowing more active control over the sampled subpopulations improves the achievable regret by moving the allocation closer to the optimal active design. Overall, these results support the budgeted intervention analysis and illustrate the gradual interpolation between passive and fully active performance on real data. C.3

Synthetic Experiments

We next report synthetic experiments designed to highlight the gains predicted by the theory. In all synthetic experiments, for each treatment–subpopulation pair (a, j), the reward distribution is Bernoulli and independent across pairs. For each subpopulation j, one treatment is selected uniformly at random to be the optimal one, and its mean is set to r 1 n −1/3 + δj , δj := p , 2 T j while the remaining n − 1 treatments have mean 1/2. This construction follows the worst-case instances appearing in our theoretical analysis. To induce a non-uniform subpopulation distribution with a pronounced active-passive gap, we choose p as   ϵ ϵ 1 − ϵ, , ..., , k−1 k−1 1 where ϵ = √k−1 . That is, one subpopulation has a larger weight, while the remaining k − 1 subpopulations have equal smaller weights. This choice is aligned with the worst-case regime discussed in the proof of Lemma 3.5, in which the gap factor R(p) becomes large. All results below are averaged over 100 independent runs and are reported with 95% confidence intervals. We compare three algorithms: the passive baseline, the known-p fully active algorithm, and EETC. In each case, the standard bandit subroutine is UCB, since it has a better performance compared to the uniform subroutine. Varying the number of subpopulations. In the first synthetic experiment, we fix n = 5 and vary the number of subpopulations over k ∈ {5, 10, 20, 30, 40}. For each value of k, we set T = 100nk, so that the horizon scales linearly with the total number of treatment–subpopulation pairs and the algorithms have sufficient budget to explore all pairs. Figure 3 summarizes the results. The left panel reports the average simple regret, while the right panel reports the regret ratio between the passive baseline and each algorithm, namely Regret of passive baseline , Regret of algorithm 31

Effect of Number of Subpopulations

Regret Ratio Relative to Passive

95% CI Passive + UCB Known-p Active + UCB EETC + UCB

Passive + UCB baseline Known-p Active + UCB EETC + UCB R(p)

1.30 1.25

Regret ratio

Final simple regret

×10 3

25.0 22.5 20.0 17.5 15.0 12.5 10.0 7.5

1.20 1.15 1.10 1.05

5

10

20

30

Number of subpopulations k

1.00

40

(a) Average simple regret.

5

10

20

30

Number of subpopulations k

40

(b) Improvement ratio over passive baseline.

Figure 3: Synthetic experiment with varying number of subpopulations k and fixed n = 5, with horizon T = 100nk. Left: average simple regret over 100 runs with 95% confidence intervals. Right: ratio between the average regret of the passive baseline and the regret of each algorithm. Values above 1 indicate improvement over the passive policy. The theoretical factor R(p) is also shown for reference.

Effect of Number of Treatments

Regret Ratio Relative to Passive

60

1.20

Regret ratio

Final simple regret

×10 3

50 40 30

95% CI Passive + UCB Known-p Active + UCB EETC + UCB

20 10

5

10

15

20

Number of treatments n

25

1.15 1.10 1.05 1.00

5

10

15

Passive + UCB baseline Known-p Active + UCB

30

(a) Average simple regret.

20

Number of treatments n

25

30

EETC + UCB R(p)

(b) Improvement ratio over passive baseline.

Figure 4: Synthetic experiment with varying number of treatments n and fixed k = 20, with horizon T = 10000. Left: average simple regret over 100 runs with 95% confidence intervals. Right: ratio between the average regret of the passive baseline and the regret of each algorithm. Values above 1 indicate improvement over passive sampling, while the passive baseline appears as the constant line at value 1.

so values larger than 1 indicate improvement over the passive policy. The right panel also includes the theoretical quantity R(p). The figure shows that both proposed algorithms uniformly outperform the passive baseline over all tested values of k. Moreover, the gap becomes larger as k increases, which is consistent with the theory, since the value of R(p) also increases with k in this construction. The known-p fully active policy and EETC are not clearly separated from one another, which is expected: they have the same asymptotic rate, and the finite sample variance is relatively high. Varying the number of treatments. In the second synthetic experiment, we fix the number of subpopulations to k = 20 and vary the number of treatments over n ∈ {5, 10, 15, 20, 25, 30}. Unlike the previous experiment, we keep the horizon fixed at T = 10000 for all values of n. For each value of n, we fix one synthetic instance and average the final simple regret over 100 independent runs, varying only the reward samples and the algorithmic randomness. All algorithms use UCB as the within-subpopulation subroutine. Figure 4 reports the same two summaries as in the previous experiment. The left panel shows the average simple regret with 95% confidence intervals, and the right panel shows the regret ratio relative 32

to the passive baseline, Regret of passive baseline . Regret of algorithm Thus, values above 1 indicate improvement over passive sampling, while the passive baseline itself appears as the constant line at value 1. The active algorithms outperform the passive baseline for all tested values of n. The relative gain becomes smaller as n increases, which is expected in this fixed-horizon experiment: larger n creates more treatment–subpopulation reward distributions to explore, while the total budget remains unchanged. As before, the known-p active algorithm and EETC are close to each other and are not uniformly ordered, consistent with their matching theoretical rates and the finite-sample variability of the experiment.

33