An active learning framework for multi-group mean estimation
Authors: Abdellah Aznag
Rachel Cummings
Adam N. Elmachtoub
Venue: NeurIPS 2023 poster (2023)
Keywords: Active learning
mean estimation
bandit feedback
data acquisition

Abstract: We consider a fundamental problem where there are multiple groups whose data distributions are unknown, and an analyst would like to learn the mean of each group. We consider an active learning framework to sequentially collect $T$ samples with bandit, each period observing a sample from a chosen group. After observing a sample, the analyst may update their estimate of the mean and variance of that group and choose the next group accordingly.  The objective is to dynamically collect samples to minimize the $p$-norm of the vector of variances of our mean estimators after $T$ rounds. We propose an algorithm, Variance-UCB, that selects groups according to a an upper bound on the variance estimate adjusted to the $p$-norm chosen. We show that the regret of Variance-UCB is $O(T^{-2})$ for finite $p$, and prove that no algorithm can do better. When $p$ is infinite, we recover the $O(T^{-1.5})$ obtained in \cite{activelearning, carpentier2011upper} and provide a new lower bound showing that no algorithm can do better.

An active learning framework for multi-group mean estimation
Abdellah Aznag
Adam N. Elmachtoub Department of Industrial Engineering and Operational Research Columbia University
Rachel Cummings
(aa4683, rac2239, ae2516)
@col umbi edu
Abstract
We consider a problem with multiple groups whose data distributions unknown, and an analyst would like to learn the mean of each group. We consider an active learning framework to sequentially collect T samples with bandit feedback, each period observing a sample from a chosen group. After observing a sample, the analyst may update their estimate of the mean and variance of that group and choose the next group accordingly. The analyst's objective to dynamically collect samples minimize the p-norm of the vector of variances of the mean estimators after 7 rounds. We propose an algorithm, Variance-UCB that selects groups according
upper bound the variance estimate adjusted the p-norm chosen. We show that the regret of Variance-UCB Ö(T-2) for finite and prove that no algorithm can do better. When is infinite, we recover the Ó(T-1.5) regret bound obtained in 44 [3] with improved dependence on the remaining parameters and provide a new lower bound showing that no algorithm can do better.
Introduction
Obtaining accurate estimates from limited labeled data is fundamental challenge. To tackle this issue, active learning has emerged as a promising solution framework where a decision-maker strategically selects one sample at time [35] [5] 22 40, (24). The estimation task becomes more complex when faced with a large population different groups, where is important that all groups are represented in the estimation procedure. If this allocation is not done correctly, the decision might incur structural
bias against some groups [32 21 33 29). allowed to adjust the sampling allocation strategy, the analyst address their biases and re-allocate their sampling resources. A key challenge is to dynamically collect data from different groups while maintaining a reasonable representation of all the groups, which is the problem tackle in this paper. We provide an active learning framework for dynamic data collection with bandit feedback for estimating the means of multiple groups in a representative manner.
We consider population partitioned into multiple groups, each with data points drawn from an unknown data distribution, and analyst would like to learn the mean of each group. Each group's distribution has an unknown mean and unknown variance. At each time period, the analyst collects one sample from group of their choice and observes sample from that group. Since only one group is observed, this is also known as bandit feedback. Upon observation, the analyst exploits their new knowledge optimize their choice of the next group to observe. At the end of the time horizon T. the analyst forms a mean estimate for each group. The objective the analyst is to return a vector of mean estimates with smallest p-norm of the variance vector of the mean estimates. The choice of p-norm is motivated by its ability to capture different aspects of multi- gallt--gropp estimation performance
10 23 28
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

By considering various values of p. we gain insights into different dimensions of estimation accuracy. ranging from the overall spread of the estimates (p = 2. Euclidean norm) the worst case deviation from the true mean (p- = +oc, infinity norm), a case that is studied in 4 13 This approach allows us to assess the estimation quality from multiple perspectives, providing a more nuanced understanding of how the diverse population is represented in the final estimation of the group means. The analyst can choose p in a way to capture notions of fairness in the data collection process.
1.1 Summary of contributions
In this work, we first present active learning framework that captures the trade-off between representation and accuracy in the task of multi-group estimation. Our framework encapsulates a large class of norms (p-norms), which bring various insights into different dimensions of estimation accuracy. In Section 3 we present Variance-UCD an algorithm that selects groups according to an upper bound on the variance estimate adjusted to the p-norm.
We provide a norm-dependent regret bound on Variance-UCB under the two assumptions sub- Gaussian feedback and positive variances. Specifically, we show that the regret is Ô for finite p norms (Theorem 11. For the case of the infinite norm, we show that the regret is ((T-1.5) (Theorem 3). While bounds at this rate are already established in [4] [3], bound provides tighter dependencies in the problem parameters G and min- In the case of the infinite norm, we improve the coefficient of the 7-1.5 term in the regret from o min G to G This improvement not only tightens the dependency in the number of groups, but it also partially solves one of the open questions left in [13 regarding the role of min in the regret bound. While we prove that m can still impact the regret, it appears only in lower order terms with respect to T.
The analysis and proofs of these upper bounds presented in Section 4 Our proof technique differs from proofs of similar upper bounds in the related literature. Instead of studying the regret function directly, we first consider its Taylor expansion, and focus our analysis on its dominant term. This technique has two advantages. First, the dominant term is much simpler to analyze (linear in the case of the infinite norm, and quadratic in the case of finite p norms) than the full regret function. Second, the resulting upper bound is tighter in its dominant term, in that it does not suffer from large numerical constants, as common in the existing literature on regret analysis of bandit algorithms (e.g., [ 13
We also provide new matching lower bounds in T for both finite (Theorem 2) and infinite p-norms (Theorem 4), establishing that Variance-UCCB achieves the best possible regret in both regimes. These bounds are summarized in Table [ Prior to our work and to the best of our knowledge, no lower bounds were known for this problem. The analysis of these results is presented in Section 5
Table 1: Summary of main results
Norm
Variance-UCB Regret Lower Bound on Regret for Any Policy
< oc
0 (T (Thcorem
Ω (T 2) (Theorem
p x
O(T- 1.5) (Theorem
Q(T 155 (Theorem
We empirically validate our findings by numerical experiments presented in Section 6 which show that our theoretical regret bounds match empirical convergence rates in both cases of finite and infinite p-norms. We also provide examples showing that for finite p-norms, the smallest variance affects the regret, even when the feedback is Gaussian. This is in contrast the case of the infinite norm, where is proven
13 that under Gaussian feedback, the algorithm is not affected by the smallest variance.
1.2 Related work
We focus on the problem of mean estimation and dynamically collecting data to achieve this goal. While there a substantial body of literature on data acquisition 9 26), specifically the presence of privacy concerns and associated costs [19 30 12 17 [6], our approach differs we do not consider the costs of sharing data. Instead, we concentrate on the data collection process itself, rather than the costs to data providers.
Our motivation stems from growing attention to data collection methods 34 2 18

---

Our work is related to aume bandits problems 37 in the sense that each group can be seen as an arm, and choosing group to sample from at each time step corresponds to choosing which arm to pull. However, the performance criterion for multi-armes bandits is measured by the difference between the mean of the chosen arm and the best arm 14 38 In our framework, the means of the chosen arms do not impact the performance. It is their variances that matter in the optimal solution, as we measure the performance by considering the p-norm of the variance of the estimator, which can be non-convex. Because of this, and to the best of our knowledge, usual bandits algorithms and proof techniques [25] do not apply. Instead, we propose Variance-UCB: an algorithm that uses high probability upper bounds on the variance estimates adjusted to the chosen norm.
Considering data acquisition from the perspective of active learning natural approach 6 27). and in that sense our work is also related to active learning [15] 22 24 40]. In [. the authors address the optimal data acquisition problem under the assumption of additive objective functions. They formulate the problem as an online learning problem and leverage well-understood tools from online convex optimization 8 36. However, their ideas do not apply to our setting due to the
non-additive nature of our decisions over time.
The case where the chosen norm is ||-Iloo is introduced in 4 where the authors devise the GAFS-MAX algorithm and show that for bounded feedback with known upper bounds, it achieves regret O(TT-155) This case is also studied in [3]. where the authors extend the feedback to sub-Gaussian, and devise the B-AS algorithm, which also has 0(T-1.5) regret. One property that emerges in their study is regret bound deteriorates with min' where Pinn is the smallest variance across groups. This is counter-intuitiyy as smaller variances in general make the learning simpler. The authors pose as an open question whether any algorithm can have performance independent of amin and show that in the special case of exactly Gaussian feedback, one can derive a min free bound. We partially answer this question, by showing that the leading term of the regret bound (with respect to T) does not depend on min- In other words, while min can still impact the regret, its effect appears only in lower order terms. Our regret analysis of Variance-UCB for || so recovers the same dependence in T as in [13), but also has improved dependence in the number of groups G' and the variance vector While 3 serve as a starting point, most of their findings are only applicable to the special case p +oo. In particular, they cannot be expanded to other choices of norm. We show that for finite p norms, prove the regret bound is O(T-2), which is fundamentally different than the previous Ö(T 1.5) bound.
2
Model
We consider population partitioned into G disjoint groups. Each group is represented by an index from [G] : (1...., G}. Each individual in the population holds a real-valued data point; data from each group E [G] are distributed according to an unknown distribution D,, with unknown mean My and unknown variance o We denote miin == min Tg and let D
DD X ... x De. The analyst wishes to compute an unbiased estimate of the population mean for each group over T times of data collection, sampling only one group a time. The set of feasible policies is defined as
II : [ (me) Te E Gd-1 x R + AGG), At E [T]},
where AGG) is the of measures supported on [G]. Let ng. denote the number of collected samples from group at the end of time T, and let už be the sample mean estimator of Mg for Fg. collected samples. Once all data have been collected the end of the time horizon T, the analyst will compute the sample mean of each group. i.c..
T
igT
Σ
Ix
1=
1x,=g 1=1
Note that the vector per is always an unbiased estimator of the vector μt, as long as the policy π samples at least once from each group.
22 The p-rppoooon norm of the vector of variances of ng.r is denoted The variance of f is n
Rg(nT)
g
(1)
ng.T
9=1
3

---

The analyst wishes to minimize E[Rp(nr)]-
When choosing a policy, the analyst does not have access to the true standard deviation vector == (o),...,00 TG), which is needed to compute the value (n()). Therefore the analyst must learn through their decisions. We benchmark the performance of a policy against the best possible performance in complete information setting where a is known, that is,
min (1)) nENG
Σ ng nT SE(G)
The optimization program (2 can be difficult to solve and analyze due to the integer constraints. Instead of using the solution (2) as benchmark, we use the solution its continuous relaxation (a lower bound on (2) which we denote as,
R
min (n) s.l. Σ gE(G]
ng T.
mERC
Thus, we can define the regret of a policy as
Rg. For our analysis, we assume that the distributions D, are sub-suussiie Gaussian, as stated in Assumption | with corresponding constants c1. C2 known to the analyst !
Regret, Re =F
Assumption 1 (Sub-Gaussianity). For each E [G]. D, is sub-Gaussian. That is, there exist universal constants C1, C2 such that for any > 0.
PYWDD (IV
pgl 2 c) v a exp (-22/c2)-
We assume that such C1, 02 are known to the analyst.
Moreover, assume that all groups have some variation in their data, stated in Assumption
2
Assumption (Positive Variance). The minimum group variance is positive; i.e. Omin minge 0g O.
3 Our algorithm: Variance-UCB
Our algorithm, Variance-UCB, builds an increasingly accurate upper confidence bound for each og. which we denote (a,) Recall that ng.t denotes the number of collected samples from group through time t. At each time t, 0g can be estimated via the sample standard deviation
9.t
Σ *5t:X=9
(Y,- Pg
Ng.e
For convention, we set 0000 = ,. = +00, indicating that at least two samples are required to obtain meaningful estimate of o. We then define
UCB,(og) = -ggt C₁
(5)
Mggt
where
Cr 2 log (27') ei log(c27")) + 2 0j log (2T (1 02 + log(oz7")
(6)
(1-T-4) 22-4))2lloeee (2o((2
CT was introduced in and captures the trade-off between accuracy of the upper confidence bound and confidence in the estimate, and a polylogarithmic factor T. In particular, Cr can be constructed by the analyst since it depends only C1, C22 and T, which are known.
At time 1, the algorithm chooses the next group X using the rule:
UCB, (5g)
X arg max
|E[G]
n

---

Algorithm 1 Variance-UCB (p, T, C2
Input: norm parameter p. time horizon T, number of groups G and subgaussian parameters C1 C2.
1: Initialize 7g.0 = 0, 9.0 = 0g.1 = +o0, Vgg E [G]
2: Compute CT according
6
3: for = 0,........ T 1 do
4: Compute (gg): (C) 0g.t
Cr v
Vg
[G]
UCBi(0,) p+1
5: Select group X = g
6: Observe feedback Y(+1 ~ Dxe+1
7:
Update the number of samples: ng,t+1 ngtt Ix 1x
Vg [G]
8: Update the mean estimates: Ag.e+1 = ngg0+1
E 1x,=y
Ag E [G]
9: Update the standard deviation
estimates:
g,1+1
Pg.r+1 Ex (Y, Ag,+t))² e [G]
10:
end for
Output:
ig.T
ng. s= 1x,=g
vg E [G]
where where ties in the argmax can broken arbitrarily. The analyst then observes new sample Y from the chosen group X++1 and updates the upper confidence bounds accordingly. Variance-UCB is presented formally in Algorithm
Variance- UCB takes as input the time horizon T, the norm the groups [G]. and the sub-Gaussian parameters C1 cg. The algorithm initializes the upper confidence bound for every group be infinity, which reflects the absence of knowledge of {o,))
In the special p +00, Variance-UGe UCB (instantiated with different choice of Cr) coincides with the B-AS algorithm of 13
3.1 Regret guarantees
Our first main result gives theoretical bounds on the performance of Algorithm for finite p E (1) We show in Theorem that when p is finite, Variance- UCB incurs regret of ((T-2).
Theorem For any D that satisfies Assumptions and Laaaddaan and for any finite the regret of Variance- UCB is at most (TT-2), That is,
Regret Variiacce-UCB D) = Ō
Our second main result, Theorem 2 provides matching lower bound for problem. Thus showing that the performance of Variance- and its analysis is the best possible in terms of T.
Theorem 2. Let p be finite and be universal constant. For any online policy æ, there exists
instance D m such that for any Z 1,
Regret, p ( π Dz) 2 x(p 1)T-2 - -(T-))
Our analysis and proof techniques can be extended naturally to the case where = +oo. However, the ((T-2) regret no longer holds, and the convergence rate jumps to 3322)/2)
Theorem 3. Let Exe Ege[cy og. For any D that satisfies Assumptions / and 2
Regret so. T (Variance-UCB, D) S (CTV + O9) G1.57-1.3 + (155 Ö(T
Note that a similar bound for Theorem has already been established in 13
28230(ci ((22 + 2)² + 1) log" (T) G2. + o (T-1.)).
Regret (B-AS, D)
T1.5
min
In Section 6 we empirically evaluate the impact mis-estimating e₁ and c2.
OOr results still hold under this modified parameter setting for any Cr satisfying Lemmal
5

---

Our result in Theorem 3 improves the existing regret in all the problem parameters, i.e., Exo to VI and from G to G The most significant improvement lies removing the dependence on min in the main term of the regret. While min still appears in the negligible term o(T-1.5), this term will be asymptotically dominated for even moderate T. This improved bound gives a better understanding on how min impacts the performance of the algorithm, which was left as an open question in [13].
Finally, we give matching lower bound for the case when p = oc, showing that the analysis of Variance-UCD is tight in I when +oc. To the best of our knowledge, no lower bound for this problem was previously known.
Theorem 4. For any online policy æ, there exists instance Dx such that for any T 2 1, 1 G2557-15 2
Regret So. mm)
we give outlines of the proofs of Theorems I and respectively. While briefly mention why both results change at p = +oc, the full proof' for Theorems and is deferred Appendix
In Sections 4 and 5
4 Deriving the upper bounds
In this section, we give an overview of the main steps to prove Theorem 1 A complete proof is given in Appendix A We first show in Lemma that the optimal (o) is achieved for an optimal
static policy n (p) (p),r()) that assumes knowledge of a and samples each group g
proportionally to og
3p
p+t
Lemma 1. [Benchmark analysis] For each t. E No and p E [1, too), let n
Then,
2n
Σnera o
R5(0) = RR((n)())) = T (ni)).
The proof of Lemma utilizes the KKT conditions of the optimization program 3 that defines R For convenience, we introduce Σ = EnE[
a for each p E [1, + so that we can simplify
og
1 "y = Σ, og p+1 Using Equation (4, the expression of regret can be simplified to
Regret,, D) E, (nr) Rp(nr)]
From Eq.
77, we can understand the behavior of the regret by answering the following questions.
1. How close is the random variable ny to the optimal sampling vector nz--?
2. How does the curvature of R.).) affect the difference (TTTT) Rp (n?))?
Upper bounding the error nt nnj: Before we answer the first question, we show in Lemma that (G, an increasingly accurate upper bound for ag.
Lemma 2. For all g E [G]. with probability at least 1 - 2).
24 S UCB
2n
4CT
2CT
P+1
0g
mig ++1
Vig.
The proof of Lemma utilizzes Assumption and the choice of (C D
as defined in Eq. (5)
Using Lemma 2 the difference betwen the number of samples Variance- collects and the optimal number samples can bounded with high probability, which we state Lemma 3
3 Note that the definition E.p consistent with the definition of Exe introduced Theorem 3
'Lemma 2 holds for all choices of E [1. +ool. In particular, it is still true in the case where p
too, it he understood by taking the limit - 4o0 in the inequalities: 0 < (C,) og 5
4Gr
(gg + 2Cr
/ng.
vag.3

---

Lemma 3. Variance-UCB collects a vector of samples n such that for all E [G]. with probability at least 1 - O(T-))
4CTP
2CT
NggT nggr 3 +
0g +
Ep +
To understand the meaning of Lemma 3 we note that the feedback-dependiee structure of the algorithm makes the numbers of samples n, correlated across groups and over time, since the algorithm attempts to sample regularly from all groups. key technical challenge is to decouple yg across groups and derive an instance dependent upper bound on nr nt. This challenge does not arise in the classic multi-armed bandits setting, where the decision decision-maker maker's 's goal is to repeatedly pull only the best arm.
Curvature properties of Rp around the optimal value nř: To answer the second question, exploit the smoothness (-) around n to approximate it with a polynomial function of n. Since nf is the minimizer of R-)-) (subject Ege(c ng T) and Rp(-) is differentiable around n7, the first order of the Taylor approximation of Rp vanishes as T grows large, formalized in Lemma
Lemma 4. Let p +00 and n' E RC such that Eye(o nng T. Then,
RT('') R2( (nn)))
p+1
(n'g ))
7(p 2)
g.T 3
3p+3
n2'
n2 11
max
Tn" g.T
o min
T3
(E(G)
We note that the bound in Lemma holds regardless of the choice of the vector n', including those generated by Variance-UCB. One can interpret the upper bound in Lemmal 4 as follows: the term
represents the exact Taylor first-order approximation of Rn and the right hand side represents an upper bound on this approximation. In particular, assuming an error
p+1
(n'-">"T>> 2 EyE[c] Tny
E = n - -n" Lemma can be restated as,
Rn(n') Rp(nT) = (n()))
||l| T
| T
+o
Putting everything together:
The rest of the proof consists of applying Lemmas 3 and 4
to the
regret expression in Eq. By Lemma with high probability, ||nt
n || Ô
VT
Applying this to Lemma gives that Rpp (nT) (nç.)) |nr 1 0 (T-3)
By
Lemma R = I, and therefore with high probability. Rp(rr) R, = 1 (TT With
additional work, we show that the equality also holds in expectation, which implies from Eq. that
Regret (Variance-UCB, D) F., (n) (n?)) Ó(T-2).
4.1 The case p- +00
Even though Lemmas 1 and hold for p = +o0, the approximation guarantee given in Lemma 4 does not hold because Rox is not differentiable at nzj. As alternative, we derive first order upper bound, which we state in 5
Lemma 5. Let E C and n' E RCC such that E n'y = T. Then,
Roo (n'r)) (oo())))) -imin Roo
min 9
n' n
1)
+ 1
max nig max g
1g n/y
g
n g.T
Similar Lemma 4 we interpret the upper bound above by decomposing it into main term, - -ming ( n/ n.. 1). and an error term, 1 max, y -1) max 1 3
As opposed to the
case where p < +5, Rxo not differentiable n thus the inequality above does not stem from Taylor approximation. Adapting the bound in Lemma 5n the same steps as in Step 3 gives regret bound of 1.5).
7

---

5 Deriving the lower bounds
In this section, provide the key ideas behind the proof of Theorem 2 with the full proof given in Appendix B Given any policy π, the idea is to pick D' from two constructed instances D Df X ........ x & and D' = Dj x ... x D'z The interaction of DD (resp. D'1) with π yields a random vector of the number of collected samples, denoted by n² (resp. n²). D and D' must satisfy the following two conflicting properties:
1. D and D are sufficiently similar, in the sense that the distributions of n²" and n are close, so that would have hard time distinguishing between D" and DV, This notion of similarity is captured by the KI.-divergence of D and D
2. D" and Dd also sufficiently dissimilar in the sense that they induce distinct optimal allocation rules na and nţ. Specifically, any allocation n cannot be simultancously close to both n and nij and n incurs high regret under at least one of the two instances. This notion of dissimilarity is captured below.
Let E IC be the vector of standard deviations of all groups under D", and let Se be the set of allocations n such that Rp (n; r²)) " within of (o") for any n S. Formally.
Sa = n E NG
n Rp - - R2 S
Let g¹ be a second vector and define S similarly. We define the dissimilarity ((o".o") := inf (S S f 0}, which is the smallest so that these sets of allocations are disjoint. There is tension between the two requirements on D and Dd, which formalized next in Lemma 6
Lemma 6.
Let be fixed policy and D", D³ be instances with standard deviation vectors o", respectively. Then,
Regret, DD1} 2 d(o" o00) (- (-Eye(ay DT (ng.e K (D
max (Regret,,
The proof follows from an adapted version of LeCam's method [39] To understand the implication of Lemma 6 we examine the two terms involved the right hand side of the inequality. The first term, d(o increases the further oa and o² are from each other. The second term has the opposite monotonicity, as it decreases with the K L divergence of the two instances. These conflicting terms capture the trade-off of loss minimization versus information gain, and deriving the lower bound will come from constructing two instances for which this trade-off is maximised.
D is chosen such that all groups have data distributed according to D2 ~ N (0, we denote a := ol....,, 1) the vector of standard deviations of each group. Even though instance has all identical groups, the policy æ may treat groups differently, and the interaction of π with D may yield give different expected numbers of samples from each group. We pick h E [G] such that D= [ma.T] is minimized over [G), and construct D' follows:
Specifically,
D ~ N 01,02(1+
Dd
D ~ "~ Vg #
On the one hand, notice that Da and DO only differ in their coordinate h, so that KI(D;) 1 [g h)@(GT and by minimality of h, Ex De [n S g. so that
I ) =(1).
D' (m ( D S Σ Em D In LLD))))) = D vE[G]
Second, we show that d(o" 0²) = ( We do this by measuring the distance be- tween the sets Sa and sh for a fixed e, and then estimate the smallest e for which this dis- tance is O. This smallest e corresponds to d(o") Combining both in Lemma 6 yields max max(Regree) (Regret, p. (TT, D*),, Regret, pe ( (T,DD)} 2
Remark 1. For +o0, the proof remains the same except that in this case d ,²))= O(T-3/2) resulting in overall lower bound of O (T See Appendix C.3 for the complete proof.
8

---

Numerical study
In this section, we present experimental results on the empirical performance of Variance-UCB We explore the impact of varying each important parameter of the problem: the time horizon T', norm parameter p. number of groups G, distributions Dg. and the sub- Gaussianity parameters c1 C2. In all the experiments Dg follow Gaussian distributions. Except where they are varied, the default parameter settings are = 10 = 2. G = 2, with the respective data distributions of groups and 2 as (1,, 1) and (2, 2.5). satisfying c1 c For each parameter setting evaluated, run Variance- 500 times and report average regret over all 500 runs. For convenience, time and regret are presented on logarithmic scales.
20
Log: Regret
-10
22 Q--inee
-30
2
8
10
12
14
log
Figure 1: Impact of the p-norm on the regret.
First, we vary the choice of the parameter E {1, 2 10, 25, Do0 and observe its effect on the regret.
Figure [ shows that the convergence rates for each p precisely match those predicted by Theorems and] a slope of -2 for the finite values of (11, 2, 10, 25})) and a slope of 11. for cc.
Cy 1000
55
Cy 0.001
Log Regret
-20
log T
Figure 2: Impact of mis-cstimating Cr on the regret
Next, study how mis-specifying the lub-Gaussianity parameters ei and 02 affect the regret of Algorithm The parameter values (c1, (2) only affect the algorithm'ss behavior through Cr, so is more natural directly study the impact of errors in Cr. For the parameters used in our experimental setup, the value of Cr prescribed in Equation (6) is ~ 5; we consider both underestimating and overestimating Cr. and evaluate regret when instead plugging in values of OT (0.001, 5, 1000) in shows that choosing an overestimate of Cr incurs increased regret. This is not surprising since choosing larger Cr decreases the confidence of the algorithm in its estimates, and forces everexxplorttion. Choosing low Cy also incurs a higher regret which can more severely impact the performance, as the algorithm under-explores and can get stuck in sub-optimal behavior. However, with long enough time horizon, the algorithm will eventually estimate a accurately, regardless the small choice of Cr. As observed in Figure the smallest value of Cr = 0.001 initially has the highest regret, corresponding to incorrect estimates and insufficient exploration, and then finally converges very late to have the lowest regret. Even for very large T, this curve has higher variance due to the noise in the estimates.
the UCB update step defined in Equation (5). Figure 2

---

= 1
2
p = +00
0
0
Log- Reg-Reeret
w010
-5
-10
-10
10
-20
20
15
5
10
5
10
10
log T
log T
log T
Figure 3: The impact of min on the regret
Next, we study the effect of varying the lowest variance o E {0.05, 0.1, 1} while holding all other variances fixed, for each p E [1, +00 First, Figure shows that varying min has no effect on the regret when too. This matches result of 13 where they prove that when p +o,, their UCB-style algorithm (very similar Variance- UCB) is not affected by the lowest variance when the feedback is Gaussian. However, our experimental results show that this phenomenon does not persist when p is finite, as illustrated in Figure where we observe that regret decreases when the lowest variance min increases. This is surprising since increasing the lowest variance makes the feedback more volatile, and one would expect an increase in regret as result.
G=3
Log Regnet
-10
-20
2
8
10
12
14
log
Figure 4: Impact of the number of groups G on regret
Finally, we vary the number of groups G E {2, 10, 10). For the additional groups, we generate
their data from Gaussian Dg. with means Pa u[[-1,1] and standard deviations og ([2, 4)) independently for each group. From Figure 4 we observe that the regret increases in the number of groups, as expected. When the number of groups is small (G =),, Variance-UCU quickly enters regime where regret decreases quickly. However, as the number of groups grows (G E {10,50) 50)), the necessary time to enter the decay regime increases (~ 30, 000 for
and ~ 90, 000 for G 50). Initially the algorithm samples (on average) uniformly across all groups due to the UCB term outweighing the sample variance estimates, and each group must wait to be sampled enough times for the algorithm to estimate its optimal sampling rate. This delay will naturally increase with the number of groups. Once the confidence bounds are small enough, the algorithm samples the highest variances first. This causes abrupt variation (especially in the case where p is small) because the objective function is very sensitive to changes in one coordinate.
Acknowledgements
The authors gratefully acknowledge the support of National Science Foundation grants IIS-2147361.
The authors would also like to thank reviewers for their valuable feedback which helped improve the paper.
10

---

References
[1] Jacob Abernethy, Yiling Chen, Chien-Ju Ho, and Bo Waggoner. Low-cost learning via ac- tive data procurement. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC 11, page 619-636, New York, NY, USA, 2015. Association for Computing Machinery.
[2] Daron Acemoglu, Ali Makhdoumi, Azarakhsh Malekian, and Asuman Ozdaglar. Too much data: Prices and inefficiencies in data markets. Working Paper 26296, National Bureau of Economic Research, September 2019.
[3] Shipra Agrawal and Nikhil R Devanur. Bandits with concave rewards and convex knapsacks. In Proceedings of the fifleenth ACM conference Economics and computation, pages 989-1006, 2014.
[4] András Antos, Varun Grover, and Csaba Szepesvári. Active learning in multi-armed bandits. pages 287-302, 10 2008.
[5] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-256, 2002.
[6] Maria-Florin Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning, Journal of Computer and System Sciences, 75(1):78-88) 2009. Learning Theory 2006.
[7] Maria-Florina Balcan, Steve Hanneke, and Jennifer Wortman Vaughan. The true sample complexity of active learning. Machine learning, 80:1 1-399, 2010.
[8] Quentin Berthet and Vianney Perchet. Fast rates for bandit optimization with upper-confidence frank-wolfe. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[9] Nikhil Bhat, Vivek F. Farias, Ciamac C. Moallemi, and Decksha Sinha. Near-optimal a-b testing. Management Science, 66(10):4477-4499 2020.
[10] Jack Brimberg and Robert F Love. General considerations on the use of the weighted Ip norm as an empirical distance measure. Transportation Science, 27(4):341-345 1993.
[11] Sébastien Bubeck and Nicold Cesa-Bianchi, Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122, 2012.
[12] Yang Cai, Constantinos Daskalakis, and Christos Papadimitriou. Optimum statistical estimation with strategic data sources. In Peter Grünwald, Elad Hazan, and Satyen Kale, editors, Pro- ceedings of The 28th Conference Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 280-296, Paris, France, 03-06 Jul 2015. PMLR.
[13] Alexandra Carpentier, Alessandro Lazaric, Mohammad Ghavamzadeh, Rémi Munos, and Peter Auer. Upper-conffidence-buur algorithms for active learning in multi-armed bandits. In Algorithmic Learning Theory: 22nd International Conference, ALT 2011, Espoo, Finland, October 5-7, 201 Proceedings 22, pages 189-203. Springer, 2011.
[14] Leonardo Cella, Alessandro Lazaric, and Massimiliano Pontil. Meta-learning with stochastic linear bandits. In International Conference on Machine Learning, pages 1360-1370, PMLR, 2020.
[15] David A Cohn, Zoubin Ghahramani, and Michael I Jordan. Active learning with statistical models, Journal of artificial intelligence research, 4:129-145, 1996.
[16] Rachel Cummings, Hadi Elzayn, Vasilis Gkatzelis, Emmanouil Pountourakis, and Juba Ziani. Optimal data acquisition with privacy-aware agents. In Proceedings of the IEEE Conference on Secure and Trustworthy Machine Learning, SaTML '23, 2023.

---

[17] Rachel Cummings, Vitaly Feldman, Audra McMillan, and Kunal Talwar. Mean estimation with user-level privacy under data heterogeneity. In S. Koyejo. S. Mohamed. A. Agarwal. D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35 of NeurlPS '22, pages 29139-29151, 2022.
[18] Edith D De Leeuw. Choosing the method of data collection. 2008
[19] Arpita Ghosh and Aaron Roth. Selling privacy auction. In Proceedings of the 12th ACM Conference on Electronic Commerce, EC '11 page 199-208, New York, NY, USA, 2011. Association for Computing Machinery.
[20] Stephen Grove and Raymond P Fisk. Observational data collection methods for services marketing: An overview. Journal of the Academy of Marketing Science, 20:217-224, 1992.
[21] Kenneth Holstein, Jennifer Wortman Vaughan, Hal Daumé III, Miro Dudik, and Hanna Wallach. Improving faimess in machine learning systems: What do industry practitioners need? In Proceedings of the 2019 CHI conference human factors in computing systems, pages 1-16, 2019.
[22] B Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A. Al Sallab, Senthil Yogamani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: A survey. IEEE Transactions on Intelligent Transportation Systems, 23(6):4909-499 2022.
[23] Marius Kloft, Ulf Brefeld, Sören Sonnenburg, and Alexander Zien. Lp-norm multiple kernel learning. The Journal of Machine Learning Research, 12:953-9977 2011.
[24] Yoshiaki Kuwata, Justin Teo, Gaston Fiore, Sertac Karaman, Emilio Frazzoli, and Jonathan P How. Real-time motion planning with applications to autonomous urban driving. IEEE Transactions control systems technology, ((5)):105-1111) 2009.
[25] Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
[26] Shengyuan Liu, Yuxuan Zhao, Zhenzhi Lin, Yi Ding, Yong Yan, Li Yang, Qin Wang, Hao Zhou, and Hongwei Wu. Data-driven condition monitoring of data acquisition for consumers' transformers in actual distribution systems using (-statistics. IEEE Transactions on Power 2019.
Delivery, 34(4):
[27] Weiyang Liu, Bo Dai, Ahmad Humayun, Charlene Tay, Chen Yu, Linda B Smith, James M Rehg, and Le Song. Iterative machine teaching. In International Conference Machine Learning, pages 2149-2158. PMLR, 2017.
[28] Wenbo Liu, Shengnan Liang, and Xiwen Qin. Weighted p-norm distance kernel svm classifi- cation algorithm based on improved polarization. Scientific reports, 12(1))1-16, 2022.
[29] Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey bias and faimess in machine learning. ACM Computing Surveys (CSUR), 54(6):1-35. 2021.
[30] Kobbi Nissim, Claudio Orlandi, and Rann Smorodinsky. Privacy-aware mechanism design. In Proceedings of the 13th ACM Conference on Electronic Commerce, EC 12, page 774-789, New York, NY, USA, 2012. Association for Computing Machinery.
[31] Kobbi Nissim, Salil Vadhan, and David Xiao. Redrawing the boundaries on purchasing data from sessiiveee individuals. In Proceedings of the 5th Conference on Innovations in Theoretical Computer Science. ITCS '14, page 411-422, New York, NY, USA, 2014. Association for Computing Machinery.
[32] Dana Pessach and Erez Shmueli. A review fairnsss in machine learning. ACM Computing Surveys (CSUR), 55(3):1-44, 2022.
[33] Alvin Rajkomar, Michaela Hardr, Michael D Howell, Greg Corrado, and Marshall H Chin. Ensuring fairness machine learning to advance health equity. Annals of internal medicine, 169(12)8866877. 2018.
12

---

[34] Mitchell Nicholas Sarkies, K-A Bowles, EH Skinner, D Mitchell, Romi Haas, M Ho, Karen Salter, Kerry May, Donna Markham, L O'Brren, al. Data collection methods in health services research. Applied clinical informatics, 6(01):9-109, 2015.
[35] Burr Settles. Active learning literature survey. 2009.
[36] Aleksandrs Slivkins. Contextual bandits with similarity information. In Sham M. Kakade and Ulrike von Luxburg, editors, Proceedings of the 24th Annual Conference on Learning Theory, volume 19 of Proceedings of Machine Learning Research, pages 679-702, Budapest, Hungary, 09-11 Jun 2011. PMLR.
[37] Alcksandrs Slivkins et al. Introduction to multi-armed bandits. Foundations and Trends@ in Machine Learning, 12(1-2):1-286, 2019.
[38] Marta Soare, Alessandro Lazaric, and Rémi Munos. Best-arm identification in linear bandits. Advances in Neural Information Processing Systems, 27, 2014.
[39] Bin Yu. Assouad, Fano, and Le Cam, pages 423 435.. Springer New York, New York, NY, 1997.
[40] Liang Yu, Shuqi Qin, Meng Zhang, Chao Shen, Tao Jiang, and Xiaohong Guan. A review of deep reinforcement learning for smart building energy management. IEEE Internet Things Journal, 10466-266622266 2021.
13

---

A Proof of Theorem 1
A.1 Proof of Lemmal
The proof of Lemma
consists of using optimality conditions on Tp-
2n
pp Then,
Lemma 1. [Benchmark analysis] For each E N" and p E [1, tool, let nigt
22
Enclay
1
Ro(0) Rp(nf) T Rp(ni).
Proof. The case of p +00 is discussed in 4 13 We focus when p +00. Recall the definition of Ry from Eq. (3)
R = min (n) s.L.
Σ ng= ng=T. Gc(G]
neR
Since the function x² is increasing in R,, o
replace the objective by (n)]" Any feasible point with a zero coordinate would have Ry(n) +oc, therefore any argmin to the optimization program n' above must have positive coordinates, and satisfies the KKT conditions
Eye[G] G] n
Vg E [G],
Rn
Σ n4 T hE(G)
0,
Ōng
XER.
d² For each g E (G), the first line of the system above is equivalent -p p+r KKT conditions imply that
0. Therefore the
2p
G
or equivalently,
p+T
2
G
p+f
2v.
Ege[ey 0g /
EEj[G og
2p
T6
p+I
71
RG
Σ Σge|c] fly
T
Hence the unique minimizer is the vector
T
n
2p. Ege(o 0g
Therefore, R2 = (ntr). Moreover, (n(n)) RG (TTn)) + (ni),,, where the last equality follows from the homogeneity of the norm.
A.2 Proof of Lemma
In this section, we establish key property UCB, (a,), which relies on Assumption
Lemma 2. For all g E [G), with probability at least 1 - Ö(T-2).
p-1
4CT
20T
0 S UCB.(a,) -
og
0g +
Tigtt p +1
Vgg.
Proof. Following the notations of Section 3 we introduce the following event:
100t - -oo1 S Cr
Ar =
Vl
GEGG)2SITT
Based on corollary of 13 we have
①i (A)) 2 - 1-2C--222
14

---

ii
conditionally on Ar,
CT ngt
4g E [G,t 2G,
lōg. 0zl s
so that conditionally on Ar, we have:
UCB, (0g) 0g.t" Cr
Mggt
CT
Og +
(ōg,t-
og)
V
CT
OT
CT nggs
E E0g +
+
Mgg.t
Migel
2CT
0g +
0,
M
where the first Eq. is due to the definition of UCB, introduced in (5) and the bounding is due to the definition of Ar. Next, notice that the function x > (0g + +x) +z)=-1
2n
is increasing. which implies that
Bp 0g
2Cr
8+1
S UCB, (og) S 0g +
Vmggt
which proves the leftmost inequality in Lemma To prove the rightmost inequality, notice that + (og +
ip
x:)
FTT is also convex, therefore by Jensen's inequality,
2CT
S 2Cr 2p
og (a,t 2Cr
4Cr
2Cr Mgg.
0g +
og
Og
/mg.
Mg p+1
Vgg,
/ig.t P +
which concludes the proof.
A.3 Proof of Lemma
The goal of this section is prove Lemma which consists of bounding with high probability n - nz. To do so, we will design an alternative sequence n, that is simultaneously easy to analyze, and upper bounds with high probability. The motivation for the choice of ñ comes from the relaxation of the choice made at every time step by Variance-UCB.
We assume through the whole section what the event Ar is realized. For convenience, view the right hand side of Lemma as a quantity its own, and introduce the width function
(g(x) 4CT P
2CT
Wg x >
Epvxp+1 0g
V
so that the inequality in Lemma can be rewritten
0 < UCB, (oy) og EpWg(ng.)).
We start by proving the following lemma, which follows from the decisions Variance-UCB makes: Lemma 7. For 2G, we have:
nX twx (RxI)1.) S Tx
Proof. The proof exploits the greedy property of the algorithm. A group needs to sam- pled exactly twice to have finite UCB. Therefore, for ples every group twice (in an arbitrary order), so that at 11,2G = NG.2G = 2 and
1,..., 2G, Variance-UCB
UCB2o(0,))tt,.... (CB) A < +o0. By choice of X the following inequality holds:
UC, 7
UCB
Vg [G]
(10)
ngtt
15

---

On the one hand, from the leftmost inequality in 9
U 7
Vg [G].
(11)
Rg.
ngtt
On the other hand, from the rightmost inequality in 9
Xei E (1x(11st)
(12)
Therefore by combining both Inequalities
and 12 in Inequality 10
Xx+1
Sp (1x)-11)))
Vy E [G],
lggtt
nx
which implies, after multiplying both sides by (g,t and summing over [G].
p-t
+ e
0
Xets
GE
gE
=Ep
39 p-1
Dividing both sides by Ep 0, and using the formula ng,e
t (see Lemma 1 implies
Dx+in I nx + twx (1)).11.)). Lemma follows by substracting 1ux. (1x) from both sides.
Lemma 7 states that the possible excess between the number of samples output by the algorithm and the optimal number of samples is not too big, and can be controlled by the width w. Since the width decreases in the number of samples, the function
- x
(wy(()
must be increasing and has therefore inverse function that is also increasing, which denote (x)). We introduce the following sequence, which mimics the behavior stated in Lemma 7
igg = Rg..t
For = 1.... 2G
Mg,t+1 = ng.t + (fi S W (ng,t)
For 1 2 2G
The sequence is easier analyze and upper bounds the true number of samples n: Lemma 8. ñt 2 n.
Proof. By construction, the result holds for t 1...., 2G. Assume for the sake of contradiction that the result does not hold for y E [G] and / 1 > 2G, and take such a minimal. For such a pair (g, l):
1 2 1(X++1 = g) = -gg.t11 - 1lg.t
fgtt-1 fggtt
1 S (z
[m S W2 2 0,
where the first step follows from the definition of By minimality of t, Rg Mga41 and ny.t = ny.t. which induces the second step. The third step follows from the definition of n, and the last step follows once again from the minimality t.
The strict inequality in the chain of inequalities implies that 1(X++1 = g) a ( S W (n"))) = 0, so that
nx (n
By taking the inverse of the increasing function W on both sides, the previous inequality can be rewritten as
1 x (nx....) > nx..n..
contradicting Lemma proof.
Therefore the assumption wrong and ñ 2 n, which completes the
D
16

---

Lemma 9. For a fixed g.the sequence (m),),)) is increasing, Consequently.
ngtt S W (n +2
Proof. For a fixed x > and 2 1,
(x (t ()))(r)) (z twa(x)) -w <
therefore the sequence of functions for + I tw is decreasing in t. Consequentely. the sequence of its inverse functions far (x))221 increasing in t:
W (m) W (m).411)
(13)
Moreover, the function W is increasing in IR+:
Wn 2 Wy (n
(14)
By combining Equations
13 and
14p
we obtain
W (m (0)++1) Wy
which proves that the sequence ( (m),)) is increasing, thus completing the proof for the first part of Lemma 9
The second part follows by induction on t 2 1. For t - 2G, the result holds immediately as Ngtt ngg, and ngge S 2. We assume the result holds for a 2 2G. We distinguish cases:
Ng.t S W (:) This implies that:
Mg.1+1 Rg. +
I Wt (m +1
Wh+1g (1g,et1) + p
S W (ng,++)) +
p
where the first step stems from the definition of n. the second step stems from the assumption
ig S Wi g (ng.)). and the third step stems from the first part the proof.
Gg.t W (m) This implies that:
ig fg fgght
$ g (n +
S Wt++19 (n)++1) +
p
where the first step stems from the definition of n. the second step stems from the induction hypothesis, and the third step stems from the first part the proof.
Studying both cases concludes the induction and proves the inequality for all t 2 1. This concludes the proof of Lemma g
Next, we derive an upper bound on Wt.
Lemma 10. For r > 0. Wg(x) -
1- "00
Proof. Let 2, > 0 with 0 s y twy (v) that y= Wz( by definition of Wt. have:
two (v)
1
We (x)
1 w tw (w))
- Iw (x)
(w)
We [w))
D- (1)
y (x),
where the last step follows from the function y #2(v) proof.
being decreasing, which concludes the
D
17

---

We are now ready to prove Lemma] 3
Lemma 3. Variance-UCB collects a vector of samples nu such that for all E [G], with probability at least - 2),
P-1
4CTP Ep(p+1 +1)
2CT
P41
n. nT 33+
0g
-T -
V
Proof. Conditionally on Ar, all the previous lemmas stated in this section hold. Consequently,
Tg S Rg.T
$ 2+ + W ( ( )
n 9.T
2 +
1 T (
2 + nz + +1++ Two (n
p-1
4CrP
2CT
3 + n +
0g +
1p(++1)
V
where the first step stems from Lemma 8 the second step stems from Lemma 9 the third step stems from first order approximations and the last step stems from Lemma I0 From Assumption o > therefore n (T)) and the right hand side is ((VT).
A.4 Proof of Lemma
The goal of this section is to prove Lemma We will do so by combining the optimality of n and the curvature properties of Ryp
Lemma 4. Let p < too and n' E R such that E [G] n'g = T. Then,
Rn(n')) (n (n))
p
(n's )2
7(p + 2)
g. g
3p43
In'
my 1
max
Tn g.r
o min
T3
GE(G]
Proof. Since Rp is defined over the constrained set fn E R ng = T} with empty interior, Taylor inequality can't directly applied. To overcome this, we construct an alternative function that has the same curvature Rp while being defined non-empty interior domain. Define
- 10 10-1
Σ A 51
(15)
For each vector n E R with Moreover, have from T
Σ T, we set for each g E [G- - 1] 1g = ng We have E JC.
2 ng
1 T
& Ac-1 1 A1
of
b11
(n) =
(16)
9=1
where the last equality follows from the homogeneity property of the p-norm. Eq. (6 motivates the introduction of the re-scaled function r:
d
-EE =
(17)
X
_a-1
1- A
da
so that Eq. 16 can be written
R,, (2).
(18)
18

---

From the definition of IC in
11 the interior of XC, denoted K", is non-empty and is equal to
K
-
XE A 11,9g 0,
Σ Ag
J
9EG-11
Moreover, the function Tp C in 10 From Lemma ! A E KC Therefore from Taylor's theorem, we have for À E K.:
*p(A) --00)) - (3-AA')-y(a")) XA A7AA 23/ s lIA
8³ r'r alyla! 0A, 0X,
sup uE S.D.SEN CIc-1)
(19)
where V the gradient operator and H. the hessian operator. We exploit the optimality of X to ("r)(())
derive simple expressions for Vrp(A"), H((*), and OrgdAnds," First, since X is optimal and an interior point KC the following equality holds:
(r = 0g.
(20)
In particular, (A- (A')) = O. (H((*)(A >') X*) is simpified in the following lemma, which proof is deferred to A.6
(Ag (A--A;)²
Lemma 11. (H(A))AA X²), X²) (p (A)))))))))))))
A5
so that Inequality (99 is rewritten
(Ag - x;)2
Tp(A) (r())) 1 (0t (A*)
1
A
1
sup =E|X.X a.y.SEN (g.h.i)
xlyle!
gE[G]
(21)
(,, alyla! aA, 0A,
remains to bound deferred to A.
To do this, the following lemma is applied (the proof is also
Lemma 12. The following inequality holds:
(1)((1))
7(p + 2)
3p+3
max (p())).
sup "E(X E.V.PEN =+ (g.h.1
xlyle! Oxg
(ming X²)
Ag.
which implies after dividing both sides by (A)
(A()) (A*)
p+1
(Ag
Xg)2
7(p 2)²
A2 3p-3
112 11- (22)
max
(A*)
(ming x;)² 9
Ag
gE|G)
By using the change of variable from À to n', we have
1 Rp(n') = (Po(A),
|l - n2" 1l,c
Ra(n") - ||- X 100 <
T
which implies
Rn,'n') (n()
p+1
(n' n²
7(p 7
n1 g.
3p+3
|
n 113
max g
RT(
2
Tn
min
nt's
7
sE[G]
hence proving Lemma
5
19

---

A.5 Putting everything together
We are now ready complete the proof of Theorem Theorem 1. For any 'D that satisfies Assumptions [and for any finite the regret of Variance- UCB is at most Ó(T-2) 2). That is.
Regret p.r (Variance-UCBB D) Ō
Proof. First, notice that
Regret, p,r Senett,,,(aaiaanee (Variance-UCBB
= En [np())) Ry]
= TE| Ry - (Ar) + (m) - P
S [[) (1) 11
where the first step stems from the definition of regret introduced in Eq. 44, the second step stems from the law of total expectation, and the third step stems from both ((Ar) < and
(n(n) R s -1021pp- It remains to show that each term in the rightmost side is in O(T First, (AA) - 2GT -(T-)).
?). Next, we have conditionally on Ar: o min
(n( - Rx(")))
p+1
Σ
(ng )²
7(p 7
3p+3
n2 n 11
max
(n*)
2
Tn
fg
T3
gE|G]
p + 1 GiIn 11in-ni 13
7(p + 2)
G.
3p+3
||
max g
2 Tmin, "y
Fig
T3
where the first inequality stems from Lemma and the second inequality stems from (ng,T n )² < n n² n= Since
Eg ng.T = from Lemma
ng nzg.
Σ nA.T nh
htg
F-1
4CTP
2CT
F+1
-3 Σ
Ep 11
0g
V
n
lgg
4CTP
2CT
2 -3 - 1) - G max Ep(p+1)
0g
Vnj.r
p-1 PTI
4GCrP
2CT
2 -G
min +
min ni
Ep(p 11)
/ming n
where the first step stems from Σn RA,T n = Σn RA,T E. nu = T - T = 0, the second
step stems from Lemma 3 and the last steps stem from taking the max over the sum. The last inequality implies
4GC1P
2Ct
n - - 3GG
mino, + /ming nigT
minn
(23)
(p +1
In particular, ni-n""lla -O(/min,, /min nij,e)
Ö(VT) and
max T T Tg 1
1
((T-0.5) Ō(1).
ming n²
Therefore,
p + 1 GlIn- 12
7(p 7)
n Ngg
3p+3
|l n
n=1133
p+ GÔ(T)
7(p + 2225
Ö(T15)
Ō(1)
max g
T min, n
2 min
73
TO(T)
73
min
=)
20

---

Recall from Lemma that R = Rp(n") () Thus by taking the conditional expectation on Ar, we have
T (n) RglAr] S which concludes the proof of Theorem I
A.6 Proof of auxiliary lemmas
In this section, we prove Lemmas and 12 To do so, simple expressions for the derivatives of rp are needed. These are established in the following lemma:
Lemma 13. For g. h, e [G 1]. we introduce the following functions K
0
Hg : -
(1 \1
AG
1)
Xg
1 Ô
Gh.g
H
p 1 0bg
1
Lghh.
p+ 2 20, Gg...
The following holds:
1. Vrp = -.-PH.
2. Hggh (1 (1) -- H,H, + (p "G.h
3.
8¹r,
= (1 p)(1 - 2p)H,
ag An
+(1 - 2p)(1 + pp) (H,Gr, HnGig + HyGn,)
+rp 1 2p + (p+ 1)(p + gn
Proof. Fix a À KC and g, h, E [G 1].
Expression of the gradient: On the one hand,the definition of rp in I7 implies
o
2p
Oh
2p
(A)
A
Aa-1
A1
AG
(1
10-1)²
ASG-1
X/1
so that
i (2) = (1 A1 \6-1) 1+|
0
2p
622
(HH(())
(24)
axg
P+1
On the other hand, from the formula (fr) = =p''=ppp pf fp-1
0 (A) = '>) ax Tp (A):
(>)
(25)
Combining Equations 24 and 25 yields
i r = pHg g = pr 1 θ
87g Tp:
2hg
so that
θ = p 11-HH
(26)
87g gg
g-
Therefore Vrp first Eq. of Lemma
0x Pp:
Dec 1 TT) = r -1-P(H "H, HG-1) r rl-PH, which proves the
13
21

---

Expression of the Hessian: We have
O
g 0 "p
(Tp- (1--HH))
0bg
H + - 8 .0gg Tp
[1 p)r,"
H
abg
(1 p)r Hg H (p + 1)r PG gG
where the first equality is due the definition of the Hessian, the second equality is due to the expression of the gradient from Eq. (26). the third equality applies the product rule to the derivative, and the fourth equality applies the defmition Gg.h in Lemma 13 This proves the second Equality of Lemma 1
Third derivatives.
83
0xg0Np0,'
= -==
0%: Hggh
07: {(1 p)r 1--1-2 2p Hgg Hr + (p 1)r Ggght
① HH (p + 1)
8 0x (r g.
(1 p) ax,
where the first equality is due to the definition of the Hessian, the second inequality is due to the Hessian expression established previously, and the third equality is due the linearity of derivation. In similar fashion to the previous case, we derivate each of the products r, -2p H Hr. and r - separately. On the one hand,
[rp 28 HHH = Hg 0);
111-pp] + 11 1-2p Hg ax;
HA + H 0x:
H,
0x;
H. H1 2p)r, 20 1o.1-PH -H; + +rp 2p (Hy 1)G + HA + 1)G
(1 1 H. H1 + (p 1)r--2 (H,G + H,,
where the first equality is due to the derivation product rule, the second equality is due the definition of Gg.A introduced in Lemma 13. and the third equality is due to a reordering of the terms. On the other hand, by following the exact same steps
i ax
8 0x,"
a
(12 3- gGgn) (1 -))rppp Pp +
Gg.hh
=1 -)r 1-P HH, g.h. + (p + 2)r 1-P
(1 - -)r --2 H. y.h. (p+ + 2)r PI h.
Replacing the previous two expressions the formula for
Φ 8A Tp yields
O Tp =(1 (1-p) Hp, 3p
+ - (1-2p)(1 + +p) (H,Gr, + H.Gi HgGh.)
+ + (p + 1)(p + 2)44,,
where the symmetry of Gy.h- Gbi.g is used. This derives the third Eq. of Lemma 13 and concludes the proof.
We ready establish the proof of Lemma
(A, A
Lemma 11. (H((*)((A - A")
X²) = (p 1)r,
A
22

---

Proof. Setting the value X in the value of the Hessian established in Lemma 13 implies that for 9, [G]:
(2*) (1- H1 H H (p+ (r,
= - (1*))
1
- 1111) P("))E"
+ 1g 119-))) -))
%
X
1 1 h)
-)--1rr;(X")
+ X
where the first equality stems from the definition of the Hessian, the second equality stems from
(X") = 0 due to the optimality of A3, the third equality stems from the definition of Gg.h, and the
fourth equality stems from rp(A") = 2p -1
As consequence,
(A(A))a--),, X²)
Σ
Ha,a --)0 >))x
g.
(p ())p(A))
Σ
1
1(g = -1) (2 (A-2")((A-X) ->>)
1
g.he(G-1] 1]
Eg.hela-1ffe
11))(1- - -1))
(A - 2ン)
- (1++))p(A"))
+
Σ
2/
0E(G-1]
EOeEG--I(A (1-11))) )2
(1-2*)
-
=p + 1)pp))
1
gE 1]
(A 222a)
() X3)
(p (p 1rrx))((A"))
A/2
X;
GE(G-1]
(gg )3)
(p+ 1)r,(a))
Σ
where the first step follows from the definition of the scalar product, and the second step stems from the expression of P((*)) derived previously in the proof. In the third step, the sum is distributed over
the terms X x (g = h). In the fourth step, the first sum is factorized, and in the fifth step, the
and
equality Epelo- A Xt)a = (1-AG) Ag) - (1 \aa) No=- Ag used. This completes the proof
of Lemma
Next, we establish the proof of Lemma 12
Lemma 12. The following inequality holds:
1 pr)(2))
7(p + 2)²
max X
3p43
(p(A").
sup ME|A &. 2 +-222332
ply!z! OA,
(min, X²)²
(g.h. (g.h:))((--1
Proof. From Lemma the following equality holds for each g E [G]:
Σ
24
= (2
oh
hE|G]
For a fixed u E [,, Eg Ug = EEg = Eg X; = 1, thus the coordinate yn achieving the
maximal A must have Ugo < Ago. Since u E [2,*]] this implies that Ago S Ugo - Ag and
My
23

---

consequently max, vig < max,
The following upper bounds follow:
Ag"
NG p+1 uG
Ag p+l
1g
p+1
[Hr(W)] 2p+1
Ept1 pp S max
Ug
9 Ag.
(1G p+
(1g)
2 1
p+2.
(ggh(u)] = 2
(uG)
(u, )22 l =
ming A/
max 9
Xn
(1a)
(1g)
>p+1
Ag
P+3
[[),,(())] = 2/
(ug)*t 1 = h = i)
max
(uG)
(ming 2;)3
Ag
Moreover, since p 2 L, each j E {1 p, 2p, 3p} is non-positive, and by minimality of X":
rp(u)² S rx(A')
so that:
1
3p+3
| Hy Harp- S max
23p+3
ry
(A*)1-3P
Xg
pp
22pt1
p+2
p+1
(H,Ghas + HnG + Hy. r2-22m())1== 53 ming X
5p+1
max
max
Xg
Xg
D (ming )3)²
p+3
I M p(]( S
9
-1-p(X))
max g
Xg
Each of the previous three expressions can simplified by using ry (A") = Ex -1
3p43
H HHH (p))] S
max
(A()")
Ag
6
A
2p+3
1H,,Gn, + H.Gig + HgGh,)) ()
max
rp (A());
ming X
Ag
p+3
L ( (min, )1)
max
(A")
Xg
Hence by using the expression of the third derivatives established in Lemma 13
(ur
$ (11 p)(1 - 2p) H H -- (u))
ar,
+ (1 - 2p) (H + Hn + " 2-22p(
+ (p+ ()(p + 4n -
3p43
(A() + 12(p + 1)2
max 1 2p+3
S 2p² max g Ag
(A))
ming 2/
(p + 2)²
A P+3
max
(x()*
(min, 2z)²
Ag
7(p + 2)2
3p+3
(ming );)²
max g
Xg
g
(A*)
As a consequence, by taking the sup over u, 9, 11, i, 2,
1
prr((u)
7(p 2)²
A 3p43 rp()")
sup WE (A.X*) N.N.ZEN
clyle! Or
(min, 2;)² g
max
(27)
(g. [[G--]
which completes the proof of Lemma 12
24

---

B Proof of Theorem 2
In this section, we prove Theorem 2 First, we establish initial lower bound that captures the trade-off between how hard it is to distinguish two instances and how hard is to optimize both under the same action (See Appendix B. Dp. Next, we provide a specific counter example which regret is at least ((T 3) (See Appendix B.2
B.1 Proof of Lemma 6
Lemma 6. Let π be a fixed policy and DD, D' be two instances with standard deviation vectors o" ,",0", respectively. Then,
(T. D"), Regget DD)} d(o", o0)) Coop(-IZn (-Egeta) ET (
Proof. Let D and D be two instances with standard deviations の and o², and let 8 2 d(o _0). Let X be a random variable over the set {a, b). The following inequalities hold
Raggeeg p. ( D Regret, p.r p.r((T D*)) 2 Ex [Regret, (T,, D*
El Rp (n xx 12 )) (p; 12(o") - > 20]
P o (ox) > 6)
8Fx,
17 8)
where the first step stems from the support of X being {a, b). and the second step stems from the law of total expectation. Let & be the following (random) classifier:
a
If Rpp(n; R3 <8
f
b
If (n, ot) R2(0r) 56
Indifferent
Otherwise
6) 2 Px Since 8 2 d(o od), is well defined. Moreover, Pr. (Rp(n:: -
X) 2 infa Px (& # X). where the infinimum is taken all the classifiers of {a, b}. Moreover, by Pinsker's 's inequality, inf, (2 * X) 2 exp (- KL( |D+)). Moreover, from bandits feed- back divergence properties (see (21),, KL(D")I Ege[c] Ex, (n ( (D))) which concludes the proof of Lemma
B.2 The counter-examples
We introduce the following instances for each g [G].
D Dj N (0,1+ + Dr N 49#1
Dbb D2 N (0,1 + +
D ~ N (0, 2
We start by upper bounding the K TT--iieeeeeee between the two instances: Lemma 14. The following inequality holds: EgE(o En D (n,
<
Proof. For convenience, we set V A < 1. univariate normal distributions of zero mean implies
The formula for the KT KTL-divergence of two
KL(D)ID)) = 2 log a
v1+ o2
+ 0² (02(0((1
0²(1+v)
25

---

The taylor expansion of the expression above can be derived by combining the expansions of both the functions x log(1 + 2) and + Ite in the domain (0, 1):
0² ( + 0² -2- -0 = 2
log 2
(2(1
-
k
vb -
1-))²
121
k20
1
1 -
2 121
k.
2
(-1)"v*
(1 1
2
k +
k20
y²
2
Summing over all coordinates implies
F, DD (M,TT)K((DPI))))) S Tv²
Σ Ex. (M,
2'
gE(G]
where the inequality follows from nr S T. This concludes the proof.
Next, we derive simpler form for d(o o²)) The simplification exploits the symmetries o",, o":
Lemma 15. Let denote the unit vector (1, (I,..., 1)". The following equality holds:
d(o" 0²) -rp (u: - rr)(0")
where the function rp is introduced in Appendix
Proof. For x E b), let S. = fc 0/r (A:0") ro² S c). By definition of d,
d(o 00) inf 2 01S ns 00..
We prove d(o", o²) = Tp ( o") - (o") by proving each of the inequalities d(o", s Tp (du:o") - (or)) and d(o od) 2 rr ( u: o (r
(0))) Since a² can be obtained by swapping the first two coordinates of ah, the symmetry of rp implies r3(()) = rg())) Moreover, for each (2,,),, E K. rp((),, A2, Asc):a = rp((A2, Asc): o²). As a consequence, Tp (Hu; 0d) (a") Tp () -r)=))(("), and any > 0 satisfying e 2 rp ( o - (o)) must also satisfy 8 S # 0. In particular, d(oo",o* I ry (t (o"))
First, prove d(o  S rp (du;
To derive d o²) 2 Tp o") ro("") the following lemma, which proof is deferred later in the section:
Lemma 16. If (AI...., da) S. nt and 7 permutation of [G]. X, = (Ar())...., ... also in So S
Let E 2 0 satisfying S. S * 0. and let X E S. nt.. For each permutation т, A, is also in S S.S. Each of S. and Sh is convex and therefore the intersection S n Ss is also convex, which implies that
Σ
X E S
G u
G!
opermutatio
which in turn implies that e 2 rp o") - r (o"). By taking the inf we get do(o", ,o)) A
Tp (uu, σ²) - (o*), which completes the proof.
We now state the proof of Lemma 16
26

---

Proof. Let À = (AI,..., .........e AG) E S n.S. Since every permutation can be written as a composition of transpositions (2-cycles), it suffices to prove the result for transpositions. Let g + h. We distinguish 3 cases:
(g. h) with
1. g, 2 3: Since d&g d'scc rp(2:0")= rp()ri0") for each {a, b). The implication X, St n.S follows.
2. g. I 2: By symmetry of the problem, of o - Similarly, og (2)) Therefore, À St implies X, E St Similarly, X e St implies X, St. The implication x, E S. S.S. follows.
3. E [1 and h 2 3. Without loss of generality, assume that = 1 and = 3. Since Dj ~ Dz. the equality of = og holds and therefore rp(A; o²) = rp (>;)>;; o²), therefore
7, E S. Moreover, rp rp(Ar; = rp():o"), therefore D, S. The implication
2, E St ns. follows.
The three cases cover all possible 2-cycles, which completes the proof.
We are now ready to state the proof of Theorem 2 (( ()) We are ready to state the proof of Theorem 2
It remains show that ddpl", =rp (u.
Theorem 2. Let be finite and be universal constant. For any online policy π, there exists instance D such that for any T 2 1,
Regret,,1 ( Dx)) x(p 1 +0 (T-2.5) (1- =)
Proof. We set DTr = argmax Regret, (T,, DD)) Regret, (T, (T)
The following inequalities
hold:
Regret, (T, Dx) max Regrett, (T,, D"), Regret, (T, D
d(o0 σ²) exp
(- Eye(c Ex, D [1 (...KLL KL( (2)
rp ( 0") - r
-
exp
where the first step stems from the definition of DD. the second step stems from Lemma 6, and the third step stems from combination of both Lemma and Lemma The rest of the proof consists in deriving lower bound rp ( o²) (o)) J. Since will now solely focus oº we can drop the dependencies in ar. direct consequence Inequality (19
Tp 4 2
p
Ce - 2; A
7(p 2)²
X 1/G
3p+3
l//G - X" 11 (28)
(ming )z)² max
2
SE(G]
( (d-x;)²
We
will
lower
bound
each
of the terms
e+1
Σ E
and
Ag
(ming Az max,
7(
1/G
A
3p+3
Iu/G X" 1 oe. For convenience, we set
: 1
Since the first group has the highest variance, >j should also be the highest. In particular, Xi 1120 and fr 0. By symmetry of aa, \ラ = = = = -f. Therefore,
Σ
2
x
G-
G
(d
G
1
2 -
X
+
fn
T
G
1-11-
Gfr
[E(G]
G
21-GfT
27

---

3p+3
Next, notice that X - 1, which implies that max,
G and that ||//G - 11
mnxx(JTITT(CC 1)) = = and minl X1 - 5 Therefore.
Tp C u - -12
" 2 (Gf G+ 7(p + 2-)2223++p f
p+1
p+1
(Gf - G 7(p + 2))++)(pptt 87
(
(1 11---117
(29)
It remains to bound fr. We do by deriving the first terms of its taylor expansion in and T:
1 1
p+1
fr
G
G 1
1 + VT
1+ p+l VT
2p 1
to
1
1
2p G+ p+l VT
+ 0
G
VT
1+
2p
1
(1
p+IGVT to
2p
1 vT )
-1)
G
p+l VT
VT)
2p p+IG
1
1
1
1
+
VT
where the first equality stems from Lemma [ the second equality stems from the binomial Taylor expansion, and the third equality stems from the Taylor expansion of æ + -- The last step implies that there exists universal constants qı 92 such that for T 2
a (1-
(1
42
VT
Replacing the previous bounding of fr in Inequality (9) yields
Tp ())
20
1
+1
1
1 12
1
+0
77
G
T
TVT
which in turn implics
1 rp
(p
+
ppp1
1
G
r
4
GT
+0
T2VT
4 T
+0
T2
where we used r = ( and from Lemma ! that
P+1
2p P+T
(G (G-1)+ (1+ vT)
a²
p+1 Enp
G
p
no
T
T
By setting Theorem
of we get Regret> (T, DT) 2 k
p+1
which completes the proof of + )
L
C Upper and lower bounds when p =
The proof for Theorem 3 (upper bound when p oc) follows the same high-level steps the proof of Theorem (upper bound when p E R). However, some adjustments of the proofs are necessary. Table Sabbarissmmmrize the changes that are required.
In Appendix C.I we introduce and prove Lemma 5 the replacement for Lemma 4 In Appendix
we prove Theorem
28

---

Result
Does it hold for p t00?
Lemma
Yes
Lemmas
Yes
Lemma
No, replaced by Lemma 5
Lemmas
19 15
Yes
d(0", oo)
(
No, replaced by d(o"", o²) = ((T-1.0)
Table 2: Summary of the possible extensions
+.0
C.1
Curvature of Roo
The upper bound Lemma goes +00 as p to0 and no longer insightful. In this section, provide a suitable bound:
Lemma 5. Let a E I and n' E RC such that Eye[a] n' = T. Then,
(n4y) - (no (no(
nlg
)
1
$ -in
+ 4 max
max
ngg
T/
Proof.
From Lemmal)
I
of
Roo (ni)) Rige
"i.r
nG.T
so that for g E [G] and n',
9
R 09
71
T1g
<
R% + dg
(mgTr) 12
(n'g
nggT))
+ 2
(n'g - )
sup xe "
2r
n'
3
R 1
1
+ 4
g
max
1,
TT
NT
T2
the second step follows from Taylor's inequality applied the function + ng and the first step follows from the definition of the infinite norm. By dividing both sides by 1: rearranging the terms, and taking the max, we obtain
where the first step follows from R =
Roo (n/p) Ros (nz.
n'
nig
2
3
max
1
max
1,
Roc (nz7)
71 R.T
n
g.T
T2/
n1z
1
n//
n
- min
+
max
max
n
4
g
n
g
ml
which completes the proof of Lemma
C.2 Proof of Theorem
Theorem 3. Let Ene
EgE[cy oy For any D that satisfies Assumptions / and 2
Regret r (Variance-UCB, D) < (CIVEx + cft G1.5pp-13 1.5 + 1.55 = Ö 1.5).
29

---

Proof. Similarly to Appendix A.5 the txtel-expettation bounding still holds:
Regret (Variance-UCB, D) S 18 (n) Re Ar] + (lo2
(30)
We now upper bound each of the two terms in (30) First, similarly to the case where < +00
presented in Appendix A P- (At) 2GT -2. that
10o (A4.) - o
10oT 2
o(T-1.6).
(31)
Next, we apply the final lower bound derived Section B.2 from 13
Lemma 17. Conditionallyy on Ar,
Rg.I T.
12
-GVG
Cr
(1
1+
CT VE
+ +VV261/4
CT
3/4
V1t
Cr
T-31//
VT
VE
V
VEx
By taking the min over E [G] Lemma 17 the following inequality follows conditionally on Ar:
min g
Rg. g.T
GVG
CT
(1+ CT
VE ) + 8/20//4
(VES
CT
V 1
CT
T-3/4
VT
VE
VEx
(32)
Moreover, since Cr = Ö(), the right hand side of the inequality above is in Ö(VT). Next, from T-mnn
Inequality (23, and from ming "g T min, o²
E
max
Tg.T Tg
-1)
(mina r )2
3G + Ex
4GCT
min +
2Cr /minn 77,
min ni
18G²
32G²
S(minog) + 4C7
(ming T2
Ego minA nijTT
64G
ming og )
207
18
(1
+ T ming o
T
Ö(T-)).
and
max
TT
B.T ming
25,5
1 ming
Rq.I nigT
- 1
1
GvG VT
Cr
1 ++
Cr Vxx
+ 8/201/1
Cr
3/4
V
Cr T
T-31
V
VSxxc
/
= 0(1.
Combining the previous two inequalities yields
8402ch
(
1802
2
n
min
planing
mAX
max
$
7
1ig.
GyLl
(1
Cr
3//20//4
CT
3//4
Cr
8/4
Vie
22.0
(33)
30

---

Recall that R Spp. Applying Lemma 5 on ng. and using the upper bounds 32) and implies that conditionally on Ar
33
G CT
CT
Rx (nz) v
1+
T3/2
VEx
VD
GT
CT
3/4
CT
1+
T9/4
VD,0
VD
64G Cz. T
207 mill of
GVG (1-
Cr v
(1 +
Cr v
2V221/11
Cr VD
3/1
1+
Cr
VT
18G T ming oz
+
+73.
[1--0/ avo VT
Cr_ VI.
(1 +
Cr
+ +V22G1/
3/1
1+ -
Since the right hand side deterministic, the inequality above extends by taking the conditional expected value on Ar. Moreover, the second, third, and fourth term are all in o(T so that:
(1
OT
Bi (n) R Ar) s Cr Exc
G1.5T-13
(.55
(34)
V
Finally, combining both inequalities 31 and 34) in Inequality 30
yields
CT
Re (Variance--U.U D) < Crv Eoo
1+
G1.5pp11 1.5 + o(T-115),
VE
which completes the proof of Theorem 3
C.3 Proof of Theorem
Lemma 18. Let o", o be two vectors with Di = Eg(og)² 2x = (ob' and Doo 2 L..
There exists Da.b (5% Ege such that
Da.b
M(00,0") -= = 27
|> - 200(1")11
Proof. Let ,", o be two vectors with Ea
= Eg(og) and ΣΦ = Eg(ob) e > 0, and
A E 10, such that Eg bg = 1. We have:
1
Σ2 T
2g(00)) -1)
(To; Rox(0))) = T
max
aa
max
g
xg
g
Ag
therefore,
TA E St
+
Roo Tx) - ) 5
aa T
() -1 Se
max g
bg
(0
Vg E [G],
S Ag.
Tr ST
+1
Hence, the allocation 7X is simultaneously in S and S if and only if
X)(oa)
\1(0²)
Vg E [G].
max
Te +1
Te
+1
$ Ag
535
31

---

In particular, S² S.S. is the polytope
1 )g(0o)
TAAE 1J: >
1 =1,
Vg E
[G],
max
Te +1
+1
5
8
which is non-empty if and only
9 (o
22(00)
Σ max
1
Tr
+
Tc E +1
Ag 17(00) +1
so that d(oo", ,²)) understand the form of this solution, we introduce the following three decreasing functions:
) is the (unique) solution to the equation Eg max
1. To better
\7(0))
f:6>
Σ max
Tc +1
+1
X (o
X)(0b)
fo:0>0+ Σ
max
Te +1*
T'. +1 IN
g
Ne
X (aa)
(7)))
fa: Σ max
Tr.
T' 2
First, notice that d(or 0b) (1). Next, by assuming (WLOG) that Eg fe fz fh so that d( (1) (1"0)""0000000))~'))) Moreover,
Σg have
\2 Xz(0")
fa(c) = Σ max
Te +
Te
+1
D
Σn max (Xi(oa). a) (o"))
E +1
= E, (0 Xi X2
+ 127 - X7(0001
Te +1
+ ( - (o*)ll
Te +1
where the first step stems from the definition of far the second step stems from max(x, y) stptlayyl the third step stems from Σn \o 1, and the fourth step stems from the defintion of the 1 I-norm. The last equation implies
Σa fo
(1)
2T
Similarly, (1)
X (a
>²(ab)) )|1b) Therefore:
De
\0 - X3 (o' s d(lo", .0)
(0a -
-X
27
2T
which concludes the proof.
Theorem 4. For any online policy there exists instance Drr such that for any T 2 1,
Regret s0 - (T,, Dz) -157--15
Proof. The proof consists of constructing two instances that optimize the trade-off stated in Lemma 6. The first instance, which denoted aa consists of G groups standard normal distributions. Next, select a group h such that E,, D= [mg.r) is minimal. Notice that by minimality of E,, [T,,T),
32

---

T
E Ea [mn,)] 1
Σ
E D [
Ex D
Σ 9 G)
ng.
(35)
G
G
G
gE|G]
The second instance, which is denotes Dd. is defined as follows:
(N001+1
For g Otherwise
D2
(0()
We have
0o = (I,...,1) 1)
0² = 0" + ven
so that 2 G, mか G + v and
1
\' G (I,...,1) 1)
For g *
Ag E [G], Xi(0") =
G+v
For g = h
We introduce the following Lemma, which proof is deferred to later in this section.
Lemma 19. The following inequality holds: Ege(on E., En (mg.r KL <
Tv 2G
By combining both Lemmas 18 and in the inequality stated in Lemma
we obtain
min( Do
Dgeo
Tv²
max Reggett (TT, Regret, (T, DD}
{x*(o") - X' exp exp
2T
2G
Tv2
20
G
+ (G (1)
1 1
())
27
G
G+v
G+v
20
G
(G+
- (G- Gv G -) v)
T
G(G+
e
Tv2
vG
14 (G-
X
2
T
G(G+v)
By setting v = / < and Dn = argmax Regret 20 (T, Dd), Regret (TE, (T,,")) }. the previous inequality implies
e 112 G1. + (G 1)2
Regret (T, Dr) max Regret (T,, D Regret (T) D.)
T G(G+1) G1.5T-15
which completes the proof of Theorem
We now prove Lemma
19
Lemma 19. The following inequality holds: > En D (x, (D)) <
Tu²
20
Proof. For convenience, we set v = V < 1. univariate normal distributions of zero mean implies
The formula for the KL Li-dvvereence of two
a² v1 o2
+ 0² (0((0((+V))) v))
KL = log
0²(1+v)
33

---

The taylor expansion of the expression above can be derived by combining the expansions of both the functions x log(1 + x) and + It in the domain (0, 1):
1
( 0² (0+(1+111
1)
log
ve
(-1)
2
02
(2(1+
2
121
R20
1
1-1
1
2 k21
k.
v²
Σ
(-1)*b
(1-
1
2
k: +
k20
V²
2
where the first step stems from the inequality nr T. the second step stems from using the previous two equalities, the third step stems from simplifying the infinite sum term-wise wise. the fourth step stems from the expansion of geometric serie, and the fifth step stems from μ VT 2 O. Since D and
D have the same distribution all coordinates except coordinate h, we have:
E., D. [ S Tv2
Σ Ex. (M. SE(G]
2G
where the inequality follows from the minimality of E, [m,,T] and Eg E D [n T. This concludes the proof.
34


Reviews:
[{"review_id": "KIy6F8Fhlo", "reviewer": "Reviewer_ZDPZ", "summary": "The paper provides a general bandit-based active learning approach to the problem of learning the means of several disjoint groups so as to optimize for the variance of the resulting estimates as measured by the p-norm of the variance vector. An algorithm is proposed which samples based on a certain upper confidence bound designed for the variance p-norm, and its regret guarantees are studied. The authors identify and carefully study two regimes: p < infty and p = infty, and prove a somewhat surprising, and tight, dichotomy: namely, the regret is only Theta(1/T^2) for p < infty but increases to Theta(1/T^1.5) for p = infty. The tight lower bounds is achieved via a simple and explicit lower-bounding construction, whereas the upper bounds follow from two different appropriate upper bounds on the curvature of the variance vector p-norm. Some experiments are given to confirm the theoretically identified tight rates.", "questions": "First, for the theory part, and for the experimental part alike, I would like to better understand the nature of requiring the smallest variance to be nonzero as well as it featuring in the performance guarantees and --- in fact, as mentioned on line 275 --- somewhat paradoxically leading to higher regret as it decreases. If there is an intuitive explanation or some examples for why this should be so, I'd like to learn more.\n\nSecondly, could the authors plot out some other norms between l2 and linfty? This way the transition effect as p -> infty could be better portrayed and understood. \n\nThirdly, can plots such as Figure 2 be extended to make the convergence of some \"difficult\" curves (such as C=0.001 in that example) more visible?\n\nFinally, do the authors have any insights into why the transition in Figure 4, even though it takes a long time to wait for it, kicks in so rapidly? Thanks!", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The main strength of the paper is that it presents a very clean and natural UCB-based algorithm which, for reasons that are transparently shown via a sequence of intuitive arguments (such as a simple Taylor-based curvature bound on the p-norm vector), achieves the tight rates for the important problem of identifying group means with small variance using as few samples as possible. I also consider it quite important and strong that the authors were able to locate the corresponding tight lower bounds, which is achieved by a surprisingly clean and simple construction (where two incompatible worlds are provided which are identical except for two groups' distributions that are slightly tweaked). In this manner, this simple case of optimizing for p-norms of the variance vector becomes, in a sense, resolved (up to potential tweaks to the setup which --- as mentioned in the future work section --- could involve constraining the sampling policies etc.)\n\nAnother strength is the lucid and careful presentation of the results --- the paper is generally quite well-written (aside from a few typos that I encourage the authors to locate and fix).", "weaknesses": "In the theory part, there are in my opinion no big weaknesses --- the case is worked out quite comprehensively. Of course, a (small) weakness of the approach is the elusive nature of the subgaussian parameters that the proof assumes --- some experiments are later run to convince the reader that you don't necessarily need to know these constants exactly, but the intricate ways in which they are present in the bounds make the situation not as pleasant to deal with theoretically (on which note, I would like to ask the authors to --- for full transparency ---- more prominently mention the assumption, e.g. in the contributions section).\n\nAnother relatively small weakness is that the experimental section could be tightened up, in the sense of some plots being expanded to be more informative and some off-the-cuff remarks elaborated on. (See the Questions section below.) Still, no major problems there in my opinion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and for your kind words about our paper and results. \n\nWe will add a brief discussion about the sub-Gaussianity assumption in the contributions.\n\nFor the \"relatively small weakness\" in the experimental section, corresponding to Q2 and Q3, we will incorporate your feedback to plot some other norms between $\\ell_2$ and $\\ell_\\infty$ and  extend the x-axis on Figure 2 to better show convergence of the $C=0.001$ case.\n\nQ1 (Requiring non-zero variance): The smallest variance appears in the regret bounds (although not in the dominant term for the case of $p=\\infty$). Suppose the unknown distributions are Bernoulli. Intuitively, an analyst cannot  distinguish (using finitely many samples) between a group with arbitrarily small variance and a group with zero variance, but the optimal strategy can be quite different in these two cases.\n\nQ4 (Rapid convergence in Figure 4):\nTo better understand why this happens, we ran a similar experiment for $p = 1, 2, +\\infty$, which we will add to the paper. Initially the algorithm samples (on average) uniformly across all groups due to the UCB constant outweighing the sample variance estimates, and each group must wait to be sampled enough times for the algorithm to estimate its optimal sampling rate. This delay will naturally increase with the number of groups. Once we are in the right range, the algorithm samples the highest variances first. This causes abrupt variations in the case where $p$ is small because the objective function is very sensitive to changes in one coordinate."}, {"review_id": "777DGf74sr", "reviewer": "Reviewer_m8Me", "summary": "\nThis paper studies the mean estimation problem under the multi-armed bandit setting. Here, we have a group of populations (random variables) with unknown mean and standard deviations. The goal is to estimate the mean of each group on the fly and optimize the regret (measured by different kinds of norms). Their major contribution is a group of confidence interval based online learning algorithms and showing the optimality of these algorithms. \n", "questions": "I have a few questions: \n\n1. The baseline considers a relaxed version of the original problem because the latter is NP-Hard. Nevertheless, the regrets are tight. Does that imply a certain kind of integrality gap bound between the NP-hard original problem and the relaxed problem? \n2. How is the regret related to the number of populations, and is this also tight? \n3. Is it possible to comment on your result with the long line of research related to Stein estimators? It seems that those statistics results also aim to estimate population mean via shrinkage methods. \n4. Is there a reason to call a random variable a population, e.g., they have finite populations, or they are inconsequential naming? \n5. Are there speculations and educated guesses on the generalization of the problem, e.g., what if my goal is to estimate the standard deviation/second moment of each population? \n\n\n\n", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I think many working on multi-armed bandits and statistical learning have naturally wondered this question. I am glad to see this result and that existing UCB type algorithms still work in the new setting. \n", "weaknesses": "The text in intro feels a bit strange to me (e.g., quite a bit of empty sells and and “analyst” also sounds odd to me). I think most people understand the importance of this problem. \n\nIt would be helpful if the authors could relate this result to Stein estimator type research and stratified sampling. They feel related. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review of our work and for your kind words about our contributions to the bandits and statistical learning literature. Below we address the questions posed in your review.\n\nQ1 (integrality gap): Indeed, our tightness results are with respect to the original problem, which implies that the integrality gap goes to zero as $T$ grows large.\n\nQ2 (dependence on $G$): Our main focus in the analysis was dependence on $T$, since this is the parameter that we envision growing large in practice. Upon more careful analysis for the case where $p=\\infty$, we are able to show an upper bound on the order of $\\Sigma_{\\infty} G^{1.5} T^{-1.5}$ and a matching lower bound of $\\Sigma_{\\infty} G^{1.5} T^{-1.5}$. This is a significant improvement in the $G$ and $\\sigma_{\\min}$ parameters, compared to the upper bound result of [Carpentier et al. 2011] for the case of sub-Gaussian distributions, where they provided a bound on the order of $\\Sigma_\\infty \\sigma_{\\min}^{-1} G^{2.5}   T^{-1.5}$. We will add details of these more refined results to the paper.\n\nQ3 (Stein estimators): Stein estimators are biased, and we exclusively want to focus on unbiased which is why we look at the sample mean for each group. A key motivation at looking at the norm of the variances of the mean estimators is to make sure we are sampling each group enough, motivated by fairness reasons. Thus, using a biased estimator (such as the Stein method) is problematic in our setting since we care about fairness across groups.\n\nQ4 (population terminology): We use the term ``population'' in relation to a survey methodology setting, where the decision-maker/analyst/surveyor decides where to collect data in a dynamic fashion. However, we assume each group can be sampled as many times as we want, so essentially the populations is infinite in this setting and the naming is inconsequential.\n\nQ5 (extensions to other statistics): We conjecture that our results and algorithmic framework would generalize to  other well-defined statistics, as long as one can construct an estimator with high probability concentration guarantees.\n\nCarpentier, A., Lazaric, A., Ghavamzadeh, M., Munos, R., & Auer, P. (2011, October). Upper-confidence-bound algorithms for active learning in multi-armed bandits. In International Conference on Algorithmic Learning Theory (pp. 189-203). Berlin, Heidelberg: Springer Berlin Heidelberg."}, {"review_id": "lDIOagNQDg", "reviewer": "Reviewer_kmyz", "summary": "This paper propose the Variance-UCB algorithm to sequentially learn the mean in a multigroup setting in order to minimize the variance over all mean estimates, and prove the regret of the algorithm is optimal for both finite and infinite p values.", "questions": "As stated in the weakness, can the authors compare the Variance-UCB algorithm to other results in the literature? For example, the authors mention in the paper that this work lies in the frame work of a multi-arm bandits setting, but other bandit works in this line did not take care of the variances of the mean estimates. It would be good to empirically show that the proposed algorithm outperforms these bandit algorithms in the literature in this task.", "limitations": "Lack of comparison to other benchmark algorithms in the literature.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The Variance-UCB algorithm in this paper automatically achieves optimal regret for both cases when $p$ is finite and $p=\\infty$, and provide solid theoretical proofs for both the general lower bound and the matching regret for the algorithm.\n\n2. The authors support their statements with empirical results by varying different parameters in time horizon $T$, norm parameter $p$, group numbers $G$ and sub-Gaussian parameters.\n\n3. The paper is in general well-written.", "weaknesses": "The experiment results lack the comparison with other benchmark results in the literature. The authors only mention that the varying lowest variance has no effect on the regret results when p is infinite which is a known result in the literature.\n\nOne typo: line 65 \"it is thekkir variances...\" should it be \"their\"?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and for your kind words about our paper. Thank you also for pointing out the typo; we will correct that.\n\n\n1- Comparison with other algorithms: \n\nFor the case where the norm $p = +\\infty$, two algorithms are known: [Antos et al. 2008, Carpentier et al. 2011]. [Carpentier et al. 2011] provides an algorithm (B-AS) and has already shown that it outperforms the algorithm (GAFS-MAX) derived in [Antos et al. 2008]. Our algorithm (Variance-UCB) coincides with (B-AS) when $p = +\\infty$. We chose not to repeat the experiment made in [Carpentier 2011].\n\nFor the case where $p < +\\infty$, we provide the first algorithm for this setting to the best of our knowledge.\n\nApplying without any adapting traditional algorithms (Thompson sa,pling or $\\epsilon$-greedy) would yield to sub-optimal solutions. In our setting, the optimal strategy samples all groups asymptotically. It is not clear how to adopt traditional bandit algorithms that, at the minimum, converge asymptotically to the right solution.\n\n2- Experiments around the smallest variance:\n\n [Antos 2008, Carpentier 2011] derive an upper bound that depends on $\\sigma_{\\min}^{-1}$ when $p=\\infty$. While [Carpentier 2011] showed that the smallest variance has no effect when the distributions are exactly Gaussian, they did not show this for the general sub-Gaussian case which our paper does.\nOur experiments simply verify our theoretical result that the smallest variance does not impact the regret significantly when $p=\\infty$ and the distributions are sub-Gaussian.\n\nIn stark contrast, we show that when $p$ is finite the smallest variance does still have an effect, even for Gaussian distributions.\n\nAndrás Antos, Varun Grover, and Csaba Szepesvári. Active learning in multi-armed bandits.307\npages 287–302, 10 2008.\n\nCarpentier, A., Lazaric, A., Ghavamzadeh, M., Munos, R., & Auer, P. (2011, October). Upper-confidence-bound algorithms for active learning in multi-armed bandits. In International Conference on Algorithmic Learning Theory (pp. 189-203). Berlin, Heidelberg: Springer Berlin Heidelberg."}, {"review_id": "HGa8rHEPmR", "reviewer": "Reviewer_JGPv", "summary": "This paper focuses on the active learning algorithm for multi-group mean estimation. The authors focus on minimizing the $l_p$-norm of the variance vector. This paper proposes the variance-UCB algorithm to actively select which group to sample in each round. The sample complexities for $p<\\infty$ and $p=\\infty$ are provided, and the tightness of proposed algorithm on $T$ is also verified.", "questions": "The questions are provided in the weaknesses section.", "limitations": "The authors adequately addressed the limitations", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper focuses on the novel problem of estimating the mean values of multiple groups with minimal variance. The authors adopt $l_p$-norm to measure the variances of group mean estimates. The variance-UCB algorithm is designed and analyzed for different values of $p$. In addition, the lower bound is established to justify the tightness of the proposed algorithm on the dependency of $T$. The simulation results are provided to corroborate the theoretical findings.", "weaknesses": "1. The authors mainly focus on the dependency of $T$. However, the variance of each group also influences the sample complexity. It will be helpful to derive the upper bound that reflects these instance-dependent quantities.\n\n2. The limitation part is missing in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your time reviewing our paper, and for your supportive comments. Below we address the two questions raised in your review.\n\nQ1 (Instance-dependent upper bound): Our primary focus in the analysis was dependence on $T$, which is the parameter that we envision growing large in most practical applications. However, our analysis also allows us to provide tight (upper and lower) bounds for all parameters, including $G$ and $\\sigma$. For example, for $p = +\\infty$, we can provide a refined upper bound of $\\Sigma_{\\infty}G^{1.5} T^{-1.5} + o(T^{-1.5})$, and a refined lower bound in $\\Sigma_{\\infty}G^{1.5} T^{-1.5}$. We will add these results to the final version. \n\nQ2 (limitations): We will add a brief limitations section to the final version of our paper. We will include discussions of the limitations arising from our two modeling assumptions, and possible future directions that may arise from removing these assumptions.\n"}, {"review_id": "Gwx7HbZvl5", "reviewer": "Reviewer_kPNK", "summary": "This manuscript studies a special type of bandit problem: instead of maximizing the rewards, the learner aims to minimize the L_p norm of the variance vector for the mean estimators of each arm. The motivation of this problem is multi-group mean estimation, where a small total variance is desired. \n\nThe authors proposed a variance-UCB algorithm, which maintains an upper confidence bound for the variance of each arm, and then chooses the arm which maximizes a certain quantity determined by its current UCB and number of pulls. This quantity is motivated by the expression of optimal allocation in hindsight. This algorithm achieves a regret of O(T^{-2}) for all finite p, which is optimal by matching lower bounds. For p = infinity, this algorithm recovers the \\Theta(T^{-1.5}) optimal regret obtained by [Antos et al. 2008, Carpentier et al. 2011].", "questions": "I'll likely increase my rating if the authors could work out the tight regret dependence on G.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The problem setting is practically relevant, and the authors proposed a novel form of UCB-type algorithm to solve it. The resulting regret bound is also tight.", "weaknesses": "I have several major concerns about this work: \n\n1. The target L_p norm in Eqn. (1) is not properly motivated. The authors should at least describe a scenario where minimizing this specific quantity is meaningful. For example, is p = 1 or infty the only interesting scenario? Can the current result be extended to some value of p < 1, say p = 1/2 (I believe this is relevant when one uses absolute estimation error).\n\n2. Although the algorithm is a new UCB-type algorithm, both the intuition and analysis are very straightforward. By the KKT condition for the objective, the optimal allocation should give the same value to all arms for a certain quantity; so the algorithm simply pulls the arm with the largest quantity in order to reduce it. The analysis is then standard, possibly with the exception of Lemma 8 (the key part of the new UCB algorithm). However, this contribution alone does not reach the bar for a NeurIPS publication. \n\n3. Very importantly, the current manuscript does not have a tight regret dependence on the number of arms G. Obtaining so would require a more careful analysis in both the upper and lower bounds. In particular, the lack of tight dependence on G makes the current two-point lower bound much less interesting. \n\n4. There seems to be an issue in the upper bound analysis. Note that Lemma 3 only proves a one-sided inequality, i.e. an upper bound on n - n^*. However, when the authors applied Lemma 4, a two-sided upper bound on |n - n^*| is needed, and this requires additional explanation. I understand this seems to be fine because the sum of n_g is always T, but arguing in this way would have an additional factor of G which I don't know if that's necessary, and in my opinion (see above) the right dependence on G is important. \n\nAlso, if one would only like to obtain an upper bound on n - n^*, the complicated arguments below Lemma 8 seem unnecessary. It seems that applying Lemma 8 to the last time a certain group g is chosen should be enough. \n\nAdditional comments: \n\nPage 3: \"the optimization program (3) can be NP-hard to prove\". Please add a justification. \n\nPage 4, expression of C_T: the precise form is not interesting at all. Just say C_T = C * log(T) for a large enough constant C. \n\nPage 18, Eqn. (21): where does Sigma_p come from? Lemma 2 does not involve this term.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed comments on our paper.\n\nQ1 (Lp norms):\nThe expression of the $p$-norm for $p \\geq 1$ is $\\|\\boldsymbol{x}\\|_p := (x_1^p + \\ldots + x_n^p)^{1/p}$. The most frequent measures of error we find in the ML literature are $p = 1$ (absolute error), $p=2$ (squared error), and $p=\\infty$ (worst-case error). General $p$-norms are less frequent in practice, but their study in this case allows us to connect results across $p = 1, 2, +\\infty$, thus providing a framework for the most three common measurement errors. We believe $p=2$ is also interesting as it prevents ``outliers'', no variances of any group's mean estimator will be too large, and it provides a nice trade-off between the sum of all the variances ($p=1$) and the worst-case variance ($p=\\infty$).\n\nFor $p < 1$,  $\\|.\\|_p$ is no longer a norm, as it violates the triangle inequality. Maybe we misunderstood the comment: is it possible to provide more detail for the $p = 1/2$ case and how it relates to absolute estimation error? \n\nQ2 (algorithm and analysis): We believe that the algorithm is indeed intuitive, which is a desirable feature, although the analysis is far from immediate. \nLemma 8 is only a first step to solving the first problem, as it gives us a good control of the last pulled arm, but information about the previous arms is lost. Lemma 9 uniformly bounds the number of pulls with a quantity that is decoupled from the algorithm, while Lemmas 10 and 11 are necessary for the tightness of the bounding.\n\nWe also require using a Taylor expansion argument to deal with the complex curvature of our objective function, which does not arise in the traditional MAB setting. This has the benefit of giving the tightest first order approximation. (This is also why we don't have large constants in front of the regret, as opposed to most bandits regret bounds).\n\nWe remark that our results address open questions in [Carpentier et al. 2011], which directly asked if one can relax the Gaussian assumption to remove the dependency on $\\sigma_{min}$, and also asked if tight lower bounds can be obtained. \n\nQ3 (dependence on $G$): You are indeed correct that the dependence on $G$ in the regret bounds is interesting, as well as the smallest variance $\\sigma_{min}$ and total sum of variances $\\Sigma_{\\infty}$. Upon more careful analysis for the case where $p=\\infty$, we are able to show an upper bound on the order of $\\Sigma_{\\infty} G^{1.5} T^{-1.5}$ and a matching lower bound of $\\Sigma_{\\infty} G^{1.5} T^{-1.5}$. This is a significant improvement in the $G$ and $\\sigma_{\\min}$ parameters, compared to the upper bound result of [Carpentier et al. 2011] for the case of sub-Gaussian distributions, where they provided a bound on the order of $\\Sigma_\\infty \\sigma_{\\min}^{-1} G^{2.5}   T^{-1.5}$. We will add details of these more refined results to the paper.\n\nQ4 (upper bound analysis):  \nThe proof we submitted gives sub-optimal dependencies on $G$, and the reason is the one that you pointed out (the naive bounding $n - n^* \\leq ||n-n^*||$ is sub-optimal). We did so because we were more focused on the dependency of $T$ in our bound. However, we can now derive a tight dependency on $G$, as we mentioned above. Here is a brief explanation on how to do so: first, we combine the upper bound in Lemma 3 with a lower bound derived from similar arguments found in [Carpentier et al. 2011]. Next, for $p$ finite, we approximate the objective with a quadratic function in $(n - n^*)$, and maximize it subject to the two-sided bound on $n - n^*$. For $p=\\infty$, we can rewrite the objective function to get a more tractable expression in $n - n^*$.\n\nResponses to additional comments:\n\n-To simplify presentation, we will remove the mention of NP-hardness from the paper.\n-We provided the exact expression of $C_T$ for implementation \n and replicability purposes.\n\n-$\\Sigma_p$ is introduced in line 172. The upper bound in Lemma 2 involves $n$, while the upper bound in Lemma 3 involves $n^*$.\n\nCarpentier, A., Lazaric, A., Ghavamzadeh, M., Munos, R., & Auer, P. (2011, October). Upper-confidence-bound algorithms for active learning in multi-armed bandits. In International Conference on Algorithmic Learning Theory (pp. 189-203). Berlin, Heidelberg: Springer Berlin Heidelberg."}]

Author rebuttal:

Meta-review: Reviewers were generally positive about the problem studied and the technical contribution of this paper. There were some concerns about the regret dependence on $G$.  The authors' rebuttal answered this question satisfactory. In particular, it is good to see that the optimal dependence on $G$ could be obtained for the case $p = \infty$
Decision: Accept (poster)