Alexandra Carpentier

Alessandro Lazaric

Mohammad Ghavamzadeh

Rémi Munos

Peter Auer

Upper-Confidence-Bound Algorithms for Active Learning in Multi-Armed Bandits

In this paper, we study the problem of estimating the mean values of all the arms uniformly well in the multi-armed bandit setting. If the variances of the arms were known, one could design an optimal sampling strategy by pulling the arms proportionally to their variances. However, since the distributions are not known in advance, we need to design adaptive sampling strategies to select an arm at each round based on the previous observed samples. We describe two strategies based on pulling the arms proportionally to an upper-bound on their variances and derive regret bounds for these strategies. We show that the performance of these allocation strategies depends not only on the variances of the arms but also on the full shape of their distributions.

Introduction

Consider a marketing problem where the objective is to estimate the potential impact of several new products or services. A common approach to this problem is to design active online polling systems, where at each time a product is presented (e.g., via a web banner on Internet) to random customers from a population of interest, and feedbacks are collected (e.g., whether the customer clicks on the ad or not) and used to estimate the average preference of all the products. It is often the case that some products have a general consensus of opinion (low variance) while others have a large variability (high variance). While in the former case very few votes would be enough to have an accurate estimate of the value of the product, in the latter the system should present the product to more customers in order to achieve the same accuracy. Since the variability of the opinions for different products is not known in advance, the objective is to design an active strategy that selects which product to display at each time step in order to estimate the values of all the products uniformly well.

The problem of online polling can be seen as an online allocation problem with several options, where the accuracy of the estimation of the quality of each option depends on the quantity of the resources allocated to it and also on some (initially unknown) intrinsic variability of the option. This general problem is closely related to the problems of active learning [START_REF] Cohn | Active learning with statistical models[END_REF][START_REF] Castro | Faster rates in regression via active learning[END_REF], sampling and Monte-Carlo methods [START_REF] Étoré | Adaptive optimal allocation in stratified sampling methods[END_REF], and optimal experimental design (Fedorov, 1972, Chaudhuri and[START_REF] Chaudhuri | On efficient designing of nonlinear experiments[END_REF]. A particular instance of this problem is introduced in [START_REF] Antos | Active learning in heteroscedastic noise[END_REF] as an active learning problem in the framework of stochastic multi-armed bandits. More precisely, the problem is modeled as a repeated game between a learner and a stochastic environment, defined by a set of K unknown distributions {ν k } K k=1 , where at each round t, the learner selects an action (or arm) k t and as a consequence receives a random sample from ν kt (independent of the past samples). Given a total budget of n samples, the goal is to define an allocation strategy over arms so as to estimate their expected values uniformly well. Note that if the variances {σ 2 k } K k=1 of the arms were initially known, the optimal allocation strategy would be to sample the arms proportionally to their variances, or more accurately, proportionally to λ k = σ 2 k / j σ 2 j . However, since the distributions are initially unknown, the learner should follow an active allocation strategy which adapts its behavior as samples are collected. The performance of this strategy is measured by its regret (defined precisely by Eq. 4) that is the difference between the expected quadratic estimation error of the algorithm and the error of the optimal allocation. [START_REF] Antos | Active learning in heteroscedastic noise[END_REF] presented an algorithm, called GAFS-MAX, that allocates samples proportionally to the empirical variances of the arms, while imposing that each arm should be pulled at least √ n times (to guarantee good estimation of the true variances). They proved that for large enough n, the regret of their algorithm scales with Õ(n -3/2 ) and conjectured that this rate is optimal. 3 However, the performance displays both an implicit (in the condition for large enough n) and explicit (in the regret bound) dependency on the inverse of the smallest optimal allocation proportion, i.e., λ min = min k λ k . This suggests that the algorithm is expected to have a poor performance whenever an arm has a very small variance compared to the others. Whether this dependency is due to the analysis of GAFS-MAX, to the specific class of algorithms, or to an intrinsic characteristic of the problem is an interesting open question.

The main objective of this paper is to investigate this issue and identify under which conditions it can be avoided. Our main contributions and findings are as follows:

-We introduce two new algorithms based on upper-confidence-bounds (UCB) on the variance. -The first algorithm, called CH-AS, is based on Chernoff-Hoeffding's bound, whose regret has the rate Õ(n -3/2 ) and inverse dependency on λ min , similar to GAFS-MAX. The main differences are: the bound for CH-AS holds for any n (and not only for large enough n), multiplicative constants are made explicit, and finally, the proof is simpler and relies on very simple tools. -The second algorithm, called B-AS, uses an empirical Bernstein's inequality, and has a better performance (in terms of the number of pulls) in targeting the optimal allocation strategy without any dependency on λ min . However, moving from the number of pulls to the regret causes the inverse dependency on λ min to appear in the bound again. We show that this might be due to the specific shape of the distributions {ν k } K k=1 and derive a regret bound independent of λ min for the case of Gaussian arms.

-We show empirically that while the performance of CH-AS depends on λ min in the case of Gaussian arms, this dependence does not exist for B-AS and GAFS-MAX, as they perform well in this case. This suggests that 1) it is not possible to remove λ min from the regret bound of CH-AS, independent of the arms' distributions, and 2) GAFS-MAX's analysis could be improved along the same line as the proof of B-AS for the Gaussian arms. We also report experiments providing insights on the (somehow unexpected) fact that the full shape of the distributions, and not only their variance, impacts the regret of these algorithms.

Preliminaries

The allocation problem studied in this paper is formalized as the standard Karmed stochastic bandit setting, where each arm k = 1, . . . , K is characterized by a distribution ν k with mean µ k and variance σ 2 k . At each round t ≥ 1, the learner (algorithm A) selects an arm k t and receives a sample drawn from ν kt independently of the past. The objective is to estimate the mean values of all the arms uniformly well given a total budget of n pulls. An adaptive algorithm defines its allocation strategy as a function of the samples observed in the past (i.e., at time t, the selected arm k t is a function of all the observations up to time t -1). After n rounds and observing

T k,n = n t=1 I {k = k t } samples from each arm k, the algorithm A returns the empirical estimates μk,n = 1 T k,n T k,n t=1 X k,t ,
where X k,t denotes the sample received when pulling arm k for the t-th time. The accuracy of the estimation at each arm k is measured according to its expected squared estimation error, or loss

L k,n = E ν k (µ k -μk,n ) 2 .
(1)

The global performance or loss of A is defined as the worst loss of the arms

L n (A) = max 1≤k≤K L k,n . (2)
If the variance of the arms were known in advance, one could design an optimal static allocation (i.e., the number of pulls does not depend on the observed samples) by pulling the arms proportionally to their variances. In this case, if an arm k is pulled a fixed number of times T * k,n , its loss is computed as4

L k,n = σ 2 k T * k,n . (3)
By choosing T * k,n so as to minimize L n under the constraint that K k=1 T * k,n = n, the optimal static allocation strategy A * pulls each arm k (up to rounding effects)

T * k,n = σ 2 k n K i=1 σ 2 i
times, and achieves a global performance L n (A * ) = Σ/n, where

Σ = K i=1 σ 2 i . We denote by λ k = T * k,n n = σ 2 k
Σ , the optimal allocation proportion for arm k, and by λ min = min 1≤k≤K λ k , the smallest such proportion.

In our setting where the variances of the arms are not known in advance, the exploration-exploitation trade-off is inevitable: an adaptive algorithm A should estimate the variances of the arms (exploration) at the same time as it tries to sample the arms proportionally to these estimates (exploitation). In order to measure how well the adaptive algorithm A performs, we compare its performance to that of the optimal allocation algorithm A * , which requires the knowledge of the variances of the arms. For this purpose we define the notion of regret of an adaptive algorithm A as the difference between the loss incurred by the learner and the optimal loss L n (A * ):

R n (A) = L n (A) -L n (A * ). ( 4
)
It is important to note that unlike the standard multi-armed bandit problems, we do not consider the notion of cumulative regret, and instead, use the excessloss suffered by the algorithm at the end of the n rounds. This notion of regret is closely related to the pure exploration setting (e.g., [START_REF] Audibert | Best arm identification in multiarmed bandits[END_REF][START_REF] Bubeck | Pure exploration in finitelyarmed and continuous-armed bandits[END_REF]). An interesting feature that is shared between this setting and the problem of active learning considered in this paper is that good strategies should play all the arms as a linear function of n. This is in contrast with the standard stochastic bandit setting, at which the sub-optimal arms should be played logarithmically in n.

3 Allocation Strategy Based on Chernoff-Hoeffding UCB

The CH-AS Algorithm

The first algorithm introduced in this paper, called Chernoff-Hoeffding Allocation Strategy (CH-AS), is based on a Chernoff-Hoeffding high probability bound on the difference between the estimated and true variances of the arms. Each arm is simply pulled proportionally to an upper confidence bound (UCB) on its variance. This algorithm deals with the exploration-exploitation trade-off by pulling more the arms with higher estimated variances or higher uncertainty in these estimates. The pseudo-code of the CH-AS algorithm A CH is given in Fig. 1. It takes a confidence parameter δ as input and after n pulls returns an empirical mean μq,n for each arm q. At each time step t, the algorithm computes the empirical mean μq,t and variance σ2 q,t of each arm q as5 μq,t = 1 T q,t Tq,t i=1 X q,i and σ2

q,t = 1 T q,t Tq,t i=1 X 2 q,i -μ2 q,t , (5)
where X q,i is the i-th sample of ν k and T q,t is the number of pulls allocated to arm q up to time t. After pulling each arm twice (rounds t = 1 to 2K),

Input: parameter δ Initialize: Pull each arm twice

for t = 2K + 1, . . . , n do Compute Bq,t = 1 T q,t σ2 q,t + 5 log(1/δ) 2T q,t
for each arm 1 ≤ q ≤ K Pull an arm kt ∈ arg max 1≤q≤K Bq,t end for Output: μq,n for all arms 1 ≤ q ≤ K Fig. 1. The pseudo-code of the CH-AS algorithm. The empirical variances σ2 q,t are computed from Eq. 5.

from round t = 2K + 1 on, the algorithm computes the B q,t values based on a Chernoff-Hoeffding's bound on the variances of the arms:

B q,t = 1 T q,t σ2 q,t + 5 log(1/δ) 2T q,t ,
and then pulls the arm with the largest B q,t .

Regret Bound and Discussion

Before reporting a regret bound for CH-AS, we first analyze its performance in targeting the optimal allocation strategy in terms of the number of pulls. As it will be discussed later, the distinction between the performance in terms of the number of pulls and the regret will allow us to stress the potential dependency of the regret on the distribution of the arms (see Section 4.3).

Lemma 1. Assume that the support of the distributions {ν k } K k=1 are in [0, 1]. For any δ > 0, any arm 1 ≤ k ≤ K, and any time 1 ≤ t ≤ n, with probability 1 -4nKδ, the number of pulls by the CH-AS algorithm satisfies -2

Σ 2 λ 3/2 min n log(1/δ) ≤ T k,n -T * k,n ≤ 2(K -1) Σ 2 λ 3/2 min n log(1/δ) . (6)
Proof. Let ξ be the event

ξ = 1≤k≤K, 1≤t≤n 1 t t i=1 X 2 k,i - 1 t t i=1 X k,i 2 -σ 2 k ≤ 5 log(1/δ) 2t . ( 7
)
It can be shown using Hoeffding's inequality that Pr(ξ) ≥ 1 -4nKδ. Several of the following statements will be proved on this event. We divide the proof of this lemma into the following three steps.

Step 1. Mechanism of the algorithm. From Chernoff-Hoeffding's inequality (applied to X k,t and X 2 k,t ), one may prove that for any δ > 0, there exists an event ξ with probability at least 1 -nKδ (a more detailed definition of this event and its probability is available at the longer version of the paper [START_REF] Carpentier | Upper-confidence-bound algorithms for active learning in multi-armed bandits[END_REF]), such that on ξ, for all t ≤ n and q ≤ K, we have

|σ 2 q,t -σ 2 q | ≤ 5 log(1/δ) 2Tq,t ,
and the following upper and lower bounds for B q,t

σ 2 q Tq,t ≤ Bq,t ≤ 1 Tq,t σ 2 q + 10 log(1/δ) 2Tq,t . ( 8
)
Let t be the time when arm k is pulled for the last time, i.e., T k,t = T k,n -1 and T k,(t+1) = T k,n . Since A CH chooses to pull arm k at time t, for any arm p = k, we have B p,t ≤ B k,t . From Eq. 8 and the fact that T k,t = T k,n -1, we obtain

B k,t ≤ 1 T k,t σ 2 k + 10 log(1/δ) 2T k,t = 1 T k,n -1 σ 2 k + 10 log(1/δ) 2(T k,n -1) . ( 9
)
Using the lower-bound in Eq. 8 and the fact that T p,t ≤ T p,n , we derive a lowerbound for B p,t as

Bp,t ≥ σ 2 p Tp,t ≥ σ 2 p Tp,n . (10)
Combining the condition B p,t ≤ B k,t with Eqs. 9 and 10, we obtain

σ 2 p Tp,n ≤ 1 T k,n -1 σ 2 k + 10 log(1/δ) 2(T k,n -1) . ( 11
)
Note that at this point there is no dependency on t, and thus, Eq. 11 holds with probability 1 -4nKδ (this is because Eq. 11 is defined on the event ξ) for any pair of arms p and k.

Step 2. Lower bound on T p,n . If an arm p is under-pulled, i.e., T p,n < T * p,n , then from the constraint k T k,n = n and the definition of the optimal allocation, we may deduce that there must be at least one arm k that is over-pulled, i.e., T k,n > T * k,n . Using the definition of the optimal allocation T * k,n = nλ k = nσ 2 k /Σ and the fact that T k,n ≥ T * k,n + 1, Eq. 11 may be rewritten as

σ 2 p Tp,n ≤ 1 T * k,n σ 2 k + 10 log(1/δ) 2T * k,n = Σ n + 5 2 log(1/δ) (nλ k ) 3/2 ≤ Σ n + 5 2 log(1/δ) (nλmin) 3/2 . ( 12
)
By reordering the terms in Eq. 12, we obtain a lower bound on T p,n as

Tp,n ≥ σ 2 p Σ n + 5 √ 2 log(1/δ) (nλ min ) 3/2 ≥ T * p,n - 5 2n log(1/δ) 4Σ 2 λ 3/2 min ≥ T * p,n - 2 Σ 2 λ 3/2 min n log(1/δ), ( 13
)
where in the second inequality we used 1/(1 + x) ≥ 1x (for x > -1) and σ 2 p ≤ 1/4, and in the last passage we used 5 √ 2/4 < 2. Note that the lower bound holds w.h.p. for any arm p.

Step 3. Upper bound on T p,n . Using Eq. 33 and the fact that k T k,n = n, we obtain

Tp,n = n - k =p T k,n ≤ T * p,n + 2(K -1) Σ 2 λ 3/2 min n log(1/δ) . ( 14
)
The claim follows by combining the upper and lower bounds.

⊓ ⊔

We now show how the bound on the number of pulls translates into a regret bound for the CH-AS algorithm.

Theorem 1. Assume that the support of the distributions ν 1 , . . . , ν K are in [0, 1]. For any n ≥ 0, the regret of A CH , when it runs with the parameter δ = n -5/2 , is bounded as

R n (A CH ) ≤ 28K √ log n n 3/2 Σ λ 5/2 min + O log n n 2 . ( 15
)
For space limitations, we only report a sketch of the proof here, the full proof is provided in the longer version of the paper [START_REF] Carpentier | Upper-confidence-bound algorithms for active learning in multi-armed bandits[END_REF].

Proof (Sketch). Eq. 3 indicates that the more an arm is pulled, the more its estimation error becomes small. However, this is not true in general because T k,n is a random variable that depends on the actual received rewards, and thus, L k,n = E ν k (µ kμk,n ) 2 does not satisfy Eq. 3. Nevertheless, we have the property that for any arm k, the number of pulls T k,n is a stopping time w.r.t. the filtration induced by the rewards received for arm k. Hence, by applying the result of Lemma 2 in [START_REF] Antos | Active learning in heteroscedastic noise[END_REF] (a form of the Wald's theorem), one may derive6

L k,n (ξ) = E (µ k -μk,n ) 2 I {ξ} ≤ 1 T 2 k,n E T k,n t=1 (µ k -X k,t ) 2 = σ 2 k E(T k,n ) T 2 k,n , (16)
where T k,n is a lower-bound for T k,n on ξ. From this bound, one can use Lemma 4, which provides both upper and lower-bounds for T k,n on the event ξ to deduce

that L k,n (ξ) = σ 2 k T * k,n + O n -3/2 log(1/δ) and L k,n (ξ c ) ≤ 1 (which is obvious).
The claim follows by setting δ = n -5/2 . ⊓ ⊔ Remark 1. As discussed in Sec. 2, our objective is to design a sampling strategy capable of estimating the mean values of the arms almost as accurately as the estimations by the optimal allocation strategy, which assumes that the variances of the arms are known. In fact, Thm. 1 shows that the CH-AS algorithm provides a uniformly accurate estimation of the expected values of the arms with a regret R n of order O(n -3/2 ). This regret rate is the same as the one for the GAFS-MAX algorithm [START_REF] Antos | Active learning in heteroscedastic noise[END_REF].

Remark 2. In addition to a linear dependency on the number of arms K, the bound also displays an inverse dependency on the smallest proportion λ min . As a result, the bound scales poorly when an arm has a very small variance relative to the other arms (i.e., σ k ≪ Σ). Note that GAFS-MAX has also a similar dependency on the inverse of λ min , although a precise comparison is not possible due to the fact that [START_REF] Antos | Active learning in heteroscedastic noise[END_REF] do not explicitly report the multiplicative constants in their regret bound. Moreover, Thm. 1 holds for any n whereas the regret bound in [START_REF] Antos | Active learning in heteroscedastic noise[END_REF] requires a condition n ≥ n 0 , where n 0 is a constant that scales with λ -1 min . Finally, note that this UCB type of algorithm (CH-AS) enables a much simpler regret analysis than that of GAFS-MAX.

Remark 3. It is clear from Lemma 4 that the inverse dependency on λ min appears in the bound on the number of pulls and then is propagated to the regret bound. We now show with a simple example that this dependency is not an artifact of the analysis and is intrinsic in the performance of the algorithm. Consider a twoarm problem with σ 2 1 = 1 and σ 2 2 = 0. Here the optimal allocation is T * 1,n = n-1, T * 2,n = 1 (only one sample is enough to estimate the mean of the second arm), and λ min = 0, which makes the bound in Thm. 1 vacuous. This does not mean that CH-AS has a linear regret, it indicates that it minimizes the regret with a poorer rate (see Sec. A.3 in Carpentier et al. 2011, for a sketch of the proof). In fact, the Chernoff-Hoeffding's bound used in the upper-confidence term forces the algorithm to pull the arm with zero variance at least O(n 2/3 ) times, which results in under-pulling the first arm by the same amount, and thus, in worsening its estimation. It can be shown that the resulting regret has the rate O(n -4/3 ) and no dependency on λ min . So, it still decreases to zero, but with a slower rate than the one in Thm. 1. Merging these two results, we deduce that the regret of CH-AS is in fact R n ≤ min Õ(n -3/2 λ -5/2 min ), Õ(n -4/3 ) . We will further study the behavior of CH-AS, i.e., how its regret changes with n, in Sec. 5.1.

The reason for the poor performance in Lemma 4 is that Chernoff-Hoeffding's inequality is not tight for small-variance random variables. In Sec. 4, we propose an algorithm based on an empirical Bernstein's inequality, which is tighter for small-variance random variables, and prove that this algorithm under-pulls all the arms by at most O(n 1/2 ), without a dependency on λ min (see Eqs. 19 and 20).

Allocation Strategy Based on Bernstein UCB

In this section, we present another UCB-like algorithm, called Bernstein Allocation Strategy (B-AS), based on a Bernstein's inequality for the variances of the arms, that enables us to improve the bound on |T k,n -T * k,n | by removing the inverse dependency on λ min (compare the bounds in Eqs. 19 and 20 to the one for CH-AS in Eq. 26). However this result itself is not sufficient to derive a better regret bound than CH-AS. This finding is interesting since it shows that even an adaptive algorithm which implements a strategy close to the optimal allocation strategy may still incur a regret that poorly scales with the smallest proportion λ min . We further investigate this issue by showing that the way the bound of

Input: parameters c1, c2, δ Let b = 2 2c1 log(c2/δ) log(2/δ) + √ 2c 1 δ(1+c 2 +log(c 2 /δ)) (1-δ) n 1/2 Initialize: Pull each arm twice for t = 2K + 1, . . . , n do Compute Bq,t = 1 T q,t σ2 q,t +2bσq,t 1 T q,t +b 2 1 T q,t
for each arm 1 ≤ q ≤ K Pull an arm kt ∈ arg max 1≤q≤K Bq,t end for Output: μq,t for each arm 1 ≤ q ≤ K Fig. 2. The pseudo-code of the B-AS algorithm. The empirical variances σk,t are computed according to Eq. 17 the number of pulls translates into a regret bound depends on the specific distributions of the arms. In fact, when the reward distributions are Gaussian, we can exploit the property that the empirical variance σk,t is independent of the empirical mean μk,t , and show that the regret of B-AS no longer depends on λ -1 min . The numerical simulations in Sec. 5 further illustrate how the full shape of the distributions (and not only their first two moments) plays an important role in the regret of adaptive allocation algorithms.

The B-AS Algorithm

The algorithm is based on the use of a high-probability bound (empirical Bernstein's inequality), reported in [START_REF] Maurer | Empirical bernstein bounds and sample-variance penalization[END_REF] (a similar bound can be found in [START_REF] Audibert | Exploration-exploitation tradeoff using variance estimates in multi-armed bandits[END_REF], on the variance of each arm. Like in the previous section, the arm sampling strategy is proportional to those bounds. The B-AS algorithm, A B , is described in Fig. 2. It requires three parameters as input (see Remark 4 in Sec. 4.2 for a discussion on how to reduce the number of parameters from three to one) c 1 and c 2 , which are related to the shape of the distributions (see Assumption 1), and δ, which defines the confidence level of the bound. The amount of exploration of the algorithm can be adapted by properly tuning these parameters. The algorithm is similar to CH-AS except that the bounds B q,t on each arm are computed as

Bq,t = 1 Tq,t σ2 q,t + 2bσq,t 1 Tq,t + b 2 1 Tq,t , where b = 2 2c 1 log(c 2 /δ) log(2/δ) + √ 2c1δ(1+c2+log(c2/δ)) (1-δ) n 1/2 and 7 σ2 k,t = 1 T k,t -1 T k,t i=1 (X k,i -μk,t ) 2 , with μk,t = 1 T k,t T k,t i=1 X k,i . (17)

Regret Bound and Discussion

The B-AS algorithm is designed to overcome the limitations of CH-AS, especially in the case of arms with small variances (Berstein's bound is tighter than Chernoff-Hoeffding's bound for distributions with small variance). Here we consider a more general assumption than in the previous section, namely that the distributions are sub-Gaussian.

Assumption 1 (Sub-Gaussian distributions) There exist c 1 , c 2 > 0 such that for all 1 ≤ k ≤ K and any ǫ > 0,

P X∼ν k (|X -µ k | ≥ ǫ) ≤ c 1 exp(-c 2 ǫ 2 ) . ( 18
)
We first state a bound in Lemma 2 on the difference between the B-AS and optimal allocation strategies.

Lemma 2. Under Assumption 1 and for any δ > 0, when the B-AS algorithm runs with parameters c 1 , c 2 , and δ, with probability at least 1 -2nKδ, we have

Tp,n ≥ T * p,n -Kλp 1+ 16a log(2/δ) Σ √ Σ+ 2a log(2/δ) c(δ) √ n+128Ka 2 log(2/δ) Σ c(δ) n 1/4 , (19) and Tp
,n ≤ T * p,n +K 2 1+ 16a log(2/δ) Σ √ Σ+ 2a log(2/δ) c(δ) √ n+128Ka 2 log(2/δ) Σ c(δ) n 1/4 , (20)
for any arm p ≤ K and any n ≥ 16 9 c(δ) -2 , where c(δ)

= 2a √ log(2/δ) √ K( √ Σ+4a √ log(2/δ))
and a = 2 c 1 log(c 2 /δ).

Remark. Unlike the bounds for CH-AS in Lemma 4, B-AS allocates the pulls on the arms so that the difference between T p,n and T * p,n grows with the rate Õ(

√ n) without dependency on λ min . This overcomes the limitation of CH-AS, which as discussed in Remark 3 of Sec. 3.2, may over-sample (thus also undersample) some arms by Ω(n 2/3 ) whenever λ min is small. We further note that the lower bound in Eq. 19 is of order Õ(λ p √ n), which implies that the gap between T p,n and T * p,n decreases as λ p becomes smaller. This is not the case in the upper bound, where the gap is of order Õ( √ n), but is independent of the value of λ p .

This explains why in the case of general distributions, B-AS has a regret bound with an inverse dependency on λ min (similar to CH-AS), as shown in Thm. 2

Theorem 2. Assume all the distributions {ν k } K k=1 are sub-Gaussians with parameters c 1 and c 2 . For any n ≥ 0, the regret of A B run with parameters c 1 , c 2 , and δ = n -7/2 is bounded as

R n (A B ) ≤ 28230 c 1 (c 2 + 2) 2 + 1 K 5/2 log(n) 2 λ min n 3/2 + 24K n 7/4 λ min 4368K 2 c 1 (c 2 + 2) 2 log(n) 2 3 1 Σ 3 + 2 .
Similar to Thm. 1, the bound on the number of pulls translates into a regret bound through Eq. 16. As it can be noticed, in order to remove the dependency on λ min , a symmetric bound on |T p,n -T * p,n | ≤ Õ(λ p √ n) is needed. While the lower bound in Eq. 19 already decreases with λ p , the upper bound scales with Õ( √ n). Whether there exists an algorithm with a tighter upper bound scaling with λ p is still an open question. Nonetheless, in the next section, we show that an improved loss bound can be achieved in the special case of Gaussian distributions, which leads to a regret bound without the dependency on λ min .

Regret for Gaussian Distributions

In the case of Gaussian distributions, the loss bound in Eq. 16 can be improved by the following lemma (the full proof is reported in [START_REF] Carpentier | Upper-confidence-bound algorithms for active learning in multi-armed bandits[END_REF]).

Lemma 3. Assume that all the distributions {ν k } K k=1 are Gaussian. Let T k,n be a lower-bound on the number of pulls on an event ξ. Then the loss for arm k

satisfies 8 L k,n (ξ) ≤ E (μ k,n -µ k ) 2 I {ξ} ≤ σ 2 k T k,n . (21)
Proof (Sketch). A property of Gaussian distributions is that at any time t, the empirical mean μk,t and variance σ2 k,t of the rewards of arm k are independent. Since T k,t depends only on (σ k,t ′ ) t ′ <t , it is straightforward to show by induction that T k,n and μk,n are independent as well. This gives the desired result.

⊓ ⊔ Remark 1. We notice that the loss bound in Eq. 21 does not require any upper bound on T k,n . It is actually similar to the case of deterministic allocation. When Tk,n is the deterministic number of pulls, the corresponding loss resulting from pulling arm k, Tk,n times, is L k,n = σ 2 k / Tk,n . In general, when T k,n is a random variable depending on the empirical variances {σ 2 k } k (like in our adaptive algorithms CH-AS and B-AS), we have

E (μ k,n -µ k ) 2 I {ξ} = n t=T k,n E (μ k,n -µ k ) 2 I {ξ} |T k,n = t P(T k,n = t),
which might be bigger than σ 2 k /T k,n . In fact, the empirical average μk,n depends on

T k,n through {σ k,n } K k=1 and E (μ k,n -µ k ) 2 I {ξ} |T k,n = t is no longer equal to σ 2 k /t.
However, Gaussian distributions have the property that the empirical mean μk,n is independent of the empirical variance σk,n (and thus also from T k,n ), which allows us to obtain the property reported in Lemma 3.

We now report a regret bound in the case of Gaussian distributions. Note that in this case, Assumption 1 holds for c 1 = 2Σ and c 2 = 1. 9 Theorem 3. Assume that all distributions {ν k } K k=1 are Gaussian and that an upper-bound Σ on Σ is known. The B-AS algorithm run with parameters c 1 = 2Σ, c 2 = 1, and δ = n -7/2 has a regret bounded as

R n (A B ) ≤ 4K n 2 + 7060 n 3/2 c 1 (c 2 + 2) 2 + 1 K 3/2 log(n) 2 + 2560K 2 Σ(c 2 + 1)(c 1 (c 2 + 2) 2 log(n) 2 n -7/4 . ( 22
)
Remark 2. In the case of Gaussian distributions, the regret bound for B-AS has the rate Õ(n -3/2 ) without dependency on λ min , which represents a significant improvement over the regret bounds for the CH-AS and GAFS-MAX algorithms.

Remark 3. In practice, there is no need to tune the three parameters c 1 , c 2 , and δ separately. In fact, it is enough to tune the algorithm for a single parameter b (see Fig. 2). Using the proof of Thm. 3 and the optimized value of δ, it is possible to show that the expected regret is minimized by choosing b = O max{Σ 3/2 , √ Σ} log n , which only requires an upper bound on the value of Σ. This is a reasonable assumption whenever a rough estimate of the magnitude of the variances is available.

Numerical Experiments

CH-AS, B-AS, and GAFS-MAX with Gaussian Arms

In this section, we compare the performance of CH-AS, B-AS, and GAFS-MAX algorithms on a two-armed problem with Gaussian distributions ν 1 = N (0, σ 2 1 = 4) and ν 2 = N (0, σ 2 2 = 1). Note that these arm distributions lead to λ min = 1/5. Figure 3-(left) shows the rescaled regret, n 3/2 R n , for the three algorithms. Each curve is averaged over 50, 000 runs. The results indicate that while the rescaled regret is almost constant w.r.t. n in B-AS and GAFS-MAX, it increases for small (relative to λ -1 min ) values of n in CH-AS. The robust behavior of B-AS when the distributions of the arms are Gaussian may be easily explained by the bound of Thm. 2 (Eq. 22). The initial increase in the CH-AS curve is also consistent with the bound of Thm. 1 (Eq. 15). As discussed in Remark 3 of Sec. 3.2, the regret bound for CH-AS is of the form Rn ≤ min Õ(n -3/2 λ -5/2 min ), Õ(n -4/3 ) , and thus, the algorithm behaves as Õ(n -4/3 ) and Õ(n -3/2 λ -5/2 min ) for small and large (relative to λ -1 min ) values of n, respectively. It is important to note that this behavior of CH-AS is independent of the arms' distributions and is intrinsic in the allocation mechanism, as shown in Lemma 4. Finally, the behavior of GAFS-MAX indicates that although its analysis [START_REF] Antos | Active learning in heteroscedastic noise[END_REF] shows an inverse dependency on λ min and yields a regret bounds similar to CH-AS, its rescaled regret in fact does not grow with n when the distributions of the arms are Gaussian. This is why we believe that it would be possible to improve the GAFS-MAX analysis by bounding the standard deviation using Bernstein's inequality (e.g., replacing Lemma 2 in [START_REF] Antos | Active learning in heteroscedastic noise[END_REF] with Lemma 1 in our paper). This would remove the inverse dependency on λ min and provide a regret bound similar to the one for B-AS in the case of Gaussian distributions.

B-AS with Non-Gaussian Arms

In Sec. 4.3, we showed that when the arms have Gaussian distributions, the dependency on λ min may be removed from the regret bound of the B-AS algorithm.

We also had a discussion on why we conjecture that it is not possible to remove this dependency in case of general distributions unless tighter upper bounds on the number of pulls can be derived. Although we do not yet have a lower bound on the regret showing the dependency on λ min , in this section we empirically show that the shape of the distributions has a direct impact on the regret of the B-AS algorithm.

As discussed in Sec. 4.3, the property of Gaussian distributions that allows us to remove the λ min dependency in the regret bound of B-AS is that the empirical mean μk,n of each arm k is independent of its empirical variance σ2 k,n . Although this property might approximately hold for a larger family of distributions, there are distributions, such as Rademacher, for which these quantities are negatively correlated. In the case of Rademacher distribution,10 the loss (μ k,tµ k ) 2 is equal to μ2 k,t and we have σ2

k,t = 1 T k,t t i=1 X 2 k,i -μ2 k,t = 1 -μ2 k,t
, as a result, the larger σ2 k,t , the smaller μ2 k,t will be. We know that the allocation strategies in CH-AS, B-AS, and GAFS-MAX are based on the empirical variance which is used as a substitute for the true variance. As a result, the larger σ2 k,t , the arm k is pulled more often (given all other things are equal). In case of Rademacher distributions, this means that an arm is over-pulled (pulled more than its optimal allocation) exactly when its mean is accurately estimated (the loss is small). This may result in a poor estimation of the arm, and thus, negatively affect the regret of the algorithm.

In the experiments of this section, we use B-AS in two different bandit problems: one with two Gaussian arms ν 1 = N (0, σ 2 1 ) (with σ 1 ≥ 1) and ν 2 = N (0, 1), and one with a Gaussian ν 1 = N (0, σ 2 1 ) and a Rademacher ν 2 = R arms. Note that in both cases λ min = λ 2 = 1/(1 + σ 2 1 ). Figure 3-(right) shows the rescaled regret (n 3/2 R n ) of the B-AS algorithm as a function of λ -1 min for n = 1000. As expected, while the rescaled regret of B-AS is constant in the first problem, it increases with σ 2 1 in the second one. As explained above, this behavior is due to the poor approximation of the Rademacher arm which is over-pulled whenever its estimated mean is accurate. This result illustrates the fact that in this active learning problem (where the goal is to estimate the mean values of the arms), the performance of the algorithms that rely on the empirical-variances (e.g., CH-AS, B-AS, and GAFS-MAX) crucially depends on the shape of the distributions, and not only on their variances. This may be surprising since according to the central limit theorem the distribution of the empirical mean should tend to a Gaussian. However, it seems that what is important is not the distribution of the empirical mean or variance, but the correlation of these two quantities.

Conclusions and Open Questions

In this paper we studied the problem of adaptive allocation for the (uniformly good) estimation of the mean value of K independent distributions first introduced in [START_REF] Antos | Active learning in heteroscedastic noise[END_REF]. Although the algorithm proposed in [START_REF] Antos | Active learning in heteroscedastic noise[END_REF] achieves a small regret of order Õ(n -3/2 ), it displays an inverse dependency on the smallest proportion λ min . In this paper, we first introduced a novel class of algorithms based on upper-confidence-bounds on the (unknown) variances of the arms, and analyzed the two algorithms: CH-AS and B-AS. For CH-AS we derived a regret similar to [START_REF] Antos | Active learning in heteroscedastic noise[END_REF], scaling as Õ(n -3/2 ) and with the dependence on λ min . Unlike in [START_REF] Antos | Active learning in heteroscedastic noise[END_REF], this result holds for any n and the constants in the bound are made explicit. We then introduced a more refined algorithm, B-AS, which performs an allocation strategy similar to the optimal one. Nonetheless, its general regret bound still depends on λ min . We show that this dependency may be related to the specific distributions of the arms and can be removed for the case of Gaussian distributions. Finally, we report numerical simulations supporting the idea that the shape of the distributions has a relevant impact on the performance of the allocation strategies. This work opens a number of questions.

-Upper bound on the number of pulls. As mentioned in the Remark of Sec. 4.2, an open question is whether it is possible to devise an allocation algorithm such that |T p,n -T * p,n | is of order Õ(λ p √ n). Such a symmetric bound on the number of pulls would translate into a regret bound without any dependency on λ min for any distribution. -Distribution dependency. Another open question is to which extent the result for B-AS in case of Gaussian distributions could be extended to more general families of distributions. As illustrated in the case of Rademacher, the correlation between the empirical means and variances may cause the algorithm to over-pull arms even when their estimation is accurate, thus incurring a large regret. On the other hand, if the reward distributions are Gaussian, the empirical means and variances are uncorrelated and the allocation algorithms such as B-AS achieve a better regret. Further investigation is needed to identify whether this results can be extended to other distributions. -Lower bound. The results in Secs. 4.3 and 5.2 suggest that the dependency on the distributions of the arms could be intrinsic in the allocation problem. If this is the case, it should be possible to derive a lower bound for this problem showing such dependency (a lower-bound with dependency on λ -1 min ).

A Proof of Theorem 1: The Regret Bound for the CH-AS Algorithm

A.1 Basic Tools

Since the basic tools used in the proof of Theorem 1 are similar to those used in the work by [START_REF] Antos | Active learning in heteroscedastic noise[END_REF], we begin this section by restating two results from that paper. Let ξ be the event

ξ = 1≤k≤K, 1≤t≤n 1 t t i=1 X 2 k,i - 1 t t i=1 X k,i 2 -σ 2 k ≤ 5 log(1/δ) 2t . (23)
Note that the first term in the absolute value in Equation 23is the sample variance of arm k computed as in Equation 5for t samples. It can be shown using Hoeffding's inequality that Pr(ξ) ≥ 1 -4nKδ. The event ξ plays an important role in the proofs of this section and several statements will be proved on this event. We now report the following proposition which is a restatement of Lemma 2 in [START_REF] Antos | Active learning in heteroscedastic noise[END_REF].

Proposition 1. For any fixed k = 1, . . . , K and t = 1, . . . , n, let {X k,i } i be T k,t i.i.d. random variables bounded in [0, 1] from the distribution ν k with mean µ k and variance σ 2 k , and σ2 k,t be the sample variance computed as in Equation 5. Then the following statement holds on the event ξ:

|σ 2 k,t -σ 2 k | ≤ 5 log(1/δ) 2T k,t . (24)
We also need to draw a connection between the allocation and stopping time problems. Thus, we report the following proposition which is a restatement of Lemma 10 in [START_REF] Antos | Active learning in heteroscedastic noise[END_REF].

Proposition 2. Let {F t } be a filtration and X t be a F t -adapted sequence of i.i.d. random variables. Assume that F t and σ {X i : i ≥ t + 1} are independent and T is a stopping time w.r.t. F t with a finite expected value

. If E[X 2 1 ] < ∞ then E T i=1 X i -T µ 2 ≤ E[T ] σ 2 .
(25)

A.2 Allocation Performance and Regret Bound

In this section, we first provide the proof of Lemma 4 and then use the result to prove Theorem 1.

Lemma 4. Assume that the supports of the distributions {ν k } K k=1 are in [0, 1] and that n ≥ 4K. For any δ > 0, for any arm 1 ≤ k ≤ K, the number of pulls T k,n played by the CH-AS algorithm satisfies with probability at least 1 -4nKδ, -5

Σ 2 λ 3/2 min n log(1/δ) - K Σ ≤ T k,n -T * k,n ≤ 5(K -1) Σ 2 λ 3/2 min n log(1/δ) + K 2 Σ . (26)
Proof (Lemma 4). The proof consists of the following three main steps.

Step 1. Mechanism of the algorithm. Recall the definition of the upper bound used in A CH at a time t + 1 > 2K:

Bq,t+1 = 1 Tq,t σ2 q,t + 5 log(1/δ) 2Tq,t , 1 ≤ q ≤ K .
From Proposition 1, we obtain the following upper and lower bounds for B q,t+1 on the event ξ:

σ 2 q Tq,t ≤ Bq,t+1 ≤ 1 Tq,t σ 2 q + 10 log(1/δ) 2Tq,t . (27)
Let t + 1 > 2K be the time when a given arm k is pulled for the last time, i.e., T k,t = T k,n -1 and T k,(t+1) = T k,n . Note that as n ≥ 4K, there is at least one arm k that is pulled after the initialization. Since A CH chooses to pull arm k at time t + 1, for any arm p, we have

Bp,t+1 ≤ B k,t+1 . (28)
From Equation 27and the fact that T k,t = T k,n -1, we obtain

B k,t+1 ≤ 1 T k,t σ 2 k + 10 log(1/δ) 2T k,t = 1 T k,n -1 σ 2 k + 10 log(1/δ) 2(T k,n -1) . ( 29
)
Using the lower bound in Equation 27 and the fact that T p,t ≤ T p,n , we may lower bound B p,t as

Bp,t+1 ≥ σ 2 p Tp,t ≥ σ 2 p Tp,n . ( 30
)
Combining Equations 28, 29, and 30, we obtain

σ 2 p Tp,n ≤ 1 T k,n -1 σ 2 k + 10 log(1/δ) 2(T k,n -1) . ( 31
)
Note that at this point there is no dependency on t, and thus, Equation 31 holds with probability 1 -4nKδ (this is because Equation 31 is defined on the event ξ)

for an arm k that is pulled at least once after the initialization, and for any arm p.

Step 2. Lower bound on T p,n . If an arm p is under-pulled without taking into account the initialization phase, i.e., T p,n -2 < λ p (n -2K), then from the constraint k (T k,n -2) = n -2K, we deduce that there must be at least one arm k that is over-pulled, i.e., T k,n -2 > λ k (n -2K). Note that for this arm, T k,n -2 > λ k (n -2K) ≥ 0, so we know that this specific arm is pulled at least once after the initialization phase and that it satisfies Eq. 11. Using the definition of the optimal allocation T * k,n = nλ k = nσ 2 k /Σ and the fact that T k,n ≥ λ k (n -2K) + 2, Eq. 11 may be written as

σ 2 p T p,n ≤ 1 T * k,n n n -2K σ 2 k + 100 log(1/δ) 2(λ k (n -2K) + 2 -1) ≤ Σ n + 20 log(1/δ) (λ min n) 3/2 + 4KΣ n 2 , ( 32
) since λ k (n -2K) + 1 ≥ λ k (n/2 -2K + 2K) + 1 ≥ nλ k 2 , as n ≥ 4K (thus also 2KΣ n(n-2K) ≤ 4KΣ n 2 )
. By reordering the terms in the previous equation, we obtain the lower bound

T p,n ≥ σ 2 p Σ n + 20 √ log(1/δ) (nλmin) 3/2 + 4KΣ n 2 ≥ T * p,n - 5 n log(1/δ) Σ 2 λ 3/2 min - K Σ , (33)
where in the second inequality we used 1/(1 + x) ≥ 1x (for x > -1) and σ 2 p ≤ 1/4. Note that the lower bound holds w.h.p. for any arm p.

Step 3. Upper bound on T p,n . Using Eq. 33 and the fact that k T k,n = n, we obtain the upper bound

T p,n = n - k =p T k,n ≤ T * p,n + 5(K -1) Σ 2 λ 3/2 min n log(1/δ) + K 2 Σ . ( 34
)
The claim follows by combining the lower and upper bounds in Equations 33 and 34. ⊓ ⊔ We are now ready to prove Theorem 1.

Proof (Theorem 1.). The proof consists of the following two main steps.

Step 1. T k,n is a stopping time. For each arm 1 ≤ k ≤ K, let {X k,t } t≤n be all the samples collected from pulling that arm. We first show that T k,n is a stopping time adapted to the process (X k,t ) t≤n . At each time step t, the CH-AS algorithm decides which arm to pull only according to the current values of the upper-bounds {B k,t } k . Thus for any arm k, T k,(t+1) depends only on the values {T k,t } k and {σ 2 k,t } k . So by induction, T k,(t+1) depends on the sequence {X k,1 , . . . , X k,T k,t }, and on the realizations of the other arms (whose randomness is independent of the value of arm k), and thus, we may conclude that T k,n is a stopping time adapted to the process (X k,t ) t≤n .

Step 2. Regret bound. Using its definition, we may write L k,n as follow:

L k,n = E (μ k,n -µ k ) 2 = E (μ k,n -µ k ) 2 I{ξ} + E (μ k,n -µ k ) 2 I{ξ C } .
Using the definition of μk,n and Proposition 2 we bound the first term as

E (μ k,n -µ k ) 2 I{ξ} ≤ σ 2 k E[T k,n ] T 2 k,n , (35)
where T k,n is the lower bound on T k,n on the event ξ. Since the upper-bound in Lemma 4 is obtained with high probability with respect to the event ξ, we may easily convert it to a bound in expectation as follows:

E[T k,n ] ≤ T * p,n + 5(K -1) Σ 2 λ 3/2 min n log(1/δ) + K 2 Σ + n × 4nKδ. ( 36
)
Combining Equation 35and 36, and using Equation 32 for σ 2 k /T k,n , we obtain

E (μ k,n -µ k ) 2 I{ξ} ≤ Σ n + 20 log(1/δ) (λ min n) 3/2 + 4KΣ n 2 2 T * p,n + 5(K-1) Σ 2 λ 3/2 min n log(1/δ) + K 2 Σ + n × 4nKδ σ 2 k . (37) By setting A = 5 √ log(1/δ) λ 3/2 min
to simplify the notation, Equation 37 may be rewritten as

E (μ k,n -µ k ) 2 I{ξ} ≤ Σ 2 n 2 + 2Σ n 2 4A √ n + 4KΣ n + 32A 2 + 32Σ 2 K 2 n 3 n Σ + AK Σ 2 σ 2 k √ n + K 2 Σ + 4n 2 Kδ ≤ Σ 2 n 2 n Σ + AK Σ 2 σ 2 k √ n + K 2 Σ + 4n 2 Kδ + 8AΣ n 5/2 + 32A 2 + 40Σ 2 K 2 n 3 n Σ + AK 2 σ 2 k √ n( 1 Σ 2 + 1 Σ ) + 4n 2 Kδ ≤ Σ n + AK σ 2 k n 3/2 + ΣK 2 n 2 + 4Σ 2 Kδ + 8A n 3/2 + 8A 2 K 2 σ 2 k n 2 ( 1 Σ + 1) + 32AKΣδ √ n + 8 4A 2 + 5Σ 2 K 2 n 2 Σ + 8AK 2 4A 2 + 5Σ 2 K 2 σ 2 k n 5/2 ( 1 Σ 2 + 1 Σ ) + 32Kδ 4A 2 + 5Σ 2 K 2 Σn ≤ Σ n + A n 3/2 ( K σ 2 k + 8) + K 2 n 2 41Σ + 8A 2 σ 2 k (5 + 1/Σ) + 8AK 2 4A 2 + 5Σ 2 K 2 σ 2 k n 5/2 ( 1 Σ 2 + 1 Σ ) + 4K 3 A 2 δ(15Σ 2 + 22 Σ )δ ≤ Σ n + A n 3/2 ( K σ 2 k + 8) + K 2 n 2 41Σ + 128A 3 K 2 σ 2 k ( 16 Σ 2 + 16Σ) + 4K 3 A 2 δ(15Σ 2 + 22 Σ )δ.
Note that if δ = n -5/2 , we have A ≤ 8 log(n)

λ 3/2 min
and also, we obtain

E (μ k,n -µ k ) 2 I{ξ} ≤ Σ n + A n 3/2 ( K σ 2 k + 8 + 4Σ 2 K) + K 2 n 2 41Σ + 128A 3 K 2 σ 2 k ( 18 Σ 2 + 18Σ 2 ) ≤ Σ n + 8 log(n) n 3/2 λ 3/2 min ( K λ min Σ 2 + 8 + 4Σ 2 K) + 65536 log(n) 3 K 4 n 2 λ 7 min Σ 2 ( 18 Σ 2 + 18Σ 2 ). ( 38
) Since |μ k,n -µ k | is always smaller than 1, we have E (μ k,n -µ k ) 2 I{ξ C } ≤ 4nKδ ≤ 4K n 3/2
. Thus using Equation 38, the expected loss of arm k is bounded by

L k,n ≤ Σ n + 8 log(n) n 3/2 λ 3/2 min ( K λ min Σ 2 + 8 + 4Σ 2 K) + 65536 log(n) 3 K 4 n 2 λ 7 min Σ 2 ( 18 Σ 2 + 18Σ 2 ) + 4nKδ ≤ Σ n + 8 log(n) n 3/2 λ 3/2 min ( K λ min Σ 2 + 8K + 4Σ 2 K) + 65536 log(n) 3 K 4 n 2 λ 7 min Σ 2 ( 18 Σ 2 + 18Σ 2 ).
Using the definition of regret R n = max k L k,n -Σ n , we obtain

Rn ≤ 8 log(n) n 3/2 λ 3/2 min ( K λminΣ 2 + 8K + 4Σ 2 K) + 65536 log(n) 3 K 4 n 2 λ 7 min Σ 2 ( 18 Σ 2 + 18Σ 2 ) . (39)
⊓ ⊔

A.3 Example of an Alternative Regret Bound

We report a sketch of the proof for the example with λ min reported in the Remark 3 of Section 3.2. Using the definition of B k,t+1 and Proposition 1, since σ2 2,t = 0, we have that at any time t + 1 > 4

B1,t+1 ≤ 1 T1,t 1 + 10 log(1/δ) 2 and B2,t+1 = 1 T2,t 5 log(1/δ) 2T2,t . ( 40
)
Let t + 1 ≤ n be the last time that arm 1 was pulled, i.e., T 1,t = T 1,n -1 and B 1,t+1 ≥ B 2,t+1 . From Equation 40, we have

B2,t+1 = 1 T2,t 5 log(1/δ) 2T2,t ≤ B1,t+1 ≤ 1 T1,n -1 1 + 10 log(1/δ) 2 . ( 41
)
Now consider the two possible cases: 1) T 1,n ≤ n/2, in which case obviously T 2,n ≥ n/2 and 2) T 1,n > n/2, in this case Equation 41 implies that T 2,n ≥ T 2,t = Ω n 2/3 . Thus in both cases, we may write T 2,n = Ω n 2/3 , which indicates that arm 2 (resp. arm 1) is over-sampled (resp. under-sampled) by a number of pulls of order O(n 2/3 ). By following the same arguments as in the proof of Theorem 1, we deduce that the regret in this case is of order O(n -4/3 ).

B Proof of Theorems 2 and 3: The Regret Bounds for the Bernstein Algorithm

B.1 Basic Tools

The main tool: a high probability bound on the standard deviations Upper bound on the standard deviation: The upper confidence bounds B k,t used in the MC-UCB algorithm is motivated by Theorem 10 in [START_REF] Maurer | Empirical bernstein bounds and sample-variance penalization[END_REF]. We extend this result to sub-Gaussian random variables.

Lemma 5. Let Assumption 1 hold and n ≥ 2. Define the following event

ξ = ξ K,n (δ) = 1≤k≤K, 2≤t≤n    1 t -1 t i=1 X k,i - 1 t t j=1 X k,j 2 -σ k ≤ 2a log(2/δ) t    , (42)
where

a = 2c 1 log(c 2 /δ) + √ c1δ(1+c2+log(c2/δ)) (1-δ) √ 2 log(2/δ) n 1/2 . Then Pr(ξ) ≥ 1 -2nKδ.
Note that the first term in the absolute value in Equation 42is the empirical standard deviation of arm k computed as in Equation 17 for t samples. The event ξ plays an important role in the proofs of this section and a number of statements will be proved on this event.

Proof.

Step 1. Truncating sub-Gaussian variables. We want to characterize the mean and variance of the variables

X k,t given that |X k,t -µ k | ≤ c 1 log(c 2 /δ). For any positive random variable Y and any b ≥ 0, E(Y I {Y > b}) = ∞ b P(Y > ǫ)dǫ + bP(Y > b).
If we take b = c 1 log(c 2 /δ) and use Assumption 1, we obtain:

E |X k,t -µ k | 2 I |X k,t -µ k | 2 > b = +∞ b P |X k,t -µ k | 2 > ǫ dǫ + bP(|X k,t -µ k | 2 > b) ≤ +∞ b c 2 exp(-ǫ/c 1 )dǫ + bc 2 exp(-b/c 1 ) ≤ c 1 δ + c 1 log(c 2 /δ)δ ≤ c 1 δ(1 + log(c 2 /δ)).
We have

E |X k,t -µ k | 2 I |X k,t -µ k | 2 > b +E |X k,t -µ k | 2 I |X k,t -µ k | 2 ≤ b = σ 2 k , which, combined with the previous equation, implies that E |X k,t -µ k | 2 | |X k,t -µ k | 2 ≤ b -σ 2 k = E (X k,t -µ k ) 2 -σ 2 k I |X k,t -µ k | 2 > b P |X k,t -µ k | 2 ≤ b ≤ c 1 δ(1 + log(c 2 /δ)) + δσ 2 k 1 -δ . ( 43
)
Note also that Cauchy-Schwartz inequality implies

E X k,t -µ k I |X k,t -µ k | 2 > b ≤ E (X k,t -µ k ) 2 I {|X k,t -µ k | 2 > b} ≤ c 1 δ(1 + log(c 2 /δ)). Now, notice that E X k,t I |X k,t -µ k | 2 > b +E X k,t I |X k,t -µ k | 2 ≤ b = µ k ,
which, combined with the previous result and using n ≥ K ≥ 2, implies that

|μ k -µ k | = E X k,t -µ k I |X k,t -µ k | 2 > b P |X k,t -µ k | 2 ≤ b ≤ c 1 δ(1 + log(c 2 /δ)) 1 -δ , (44)
where

μk = E X k,t | |X k,t -µ k | 2 ≤ b = E X k,t I{|X k,t -µ k | 2 ≤b} P |X k,t -µ k | 2 ≤b . We note σ2 k = V X k,t | |X k,t -µ k | 2 ≤ b = E |X k,t -µ k | 2 | |X k,t -µ k | 2 ≤ b -(µ k -μk ) 2 .
From Equations 43 and 44, we derive

|σ 2 k -σ 2 k | ≤ E |X k,t -µ k | 2 | |X k,t -µ k | 2 ≤ b -σ 2 k + |μ k -µ k | 2 ≤ c 1 δ(1 + log(c 2 /δ)) + δσ 2 k 1 -δ + c 1 δ(1 + log(c 2 /δ)) (1 -δ) 2 ≤ 2c 1 δ(1 + log(c 2 /δ)) + δσ 2 k (1 -δ) 2 , from which we deduce, because σ 2 k ≤ c 1 c 2 | σk -σ k | ≤ 2c 1 δ(1 + c 2 + log(c 2 /δ)) 1 -δ . ( 45
)
Step 2. Application of large deviation inequalities.

Let ξ 1 = ξ 1,K,n (δ) be the event:

ξ 1 = 1≤k≤K, 1≤t≤n |X k,t -µ k | ≤ c 1 log(c 2 /δ) .
Under Assumption 1, using a union bound, we have that the probability of this event is at least 1 -nKδ.

We now recall Theorem 10 of [START_REF] Maurer | Empirical bernstein bounds and sample-variance penalization[END_REF]:

Theorem 4 [START_REF] Maurer | Empirical bernstein bounds and sample-variance penalization[END_REF]). Let (X 1 , ..., X t ) be t ≥ 2 i.i.d. random variables of variance σ 2 and mean µ and such that ∀i ≤ t, X i ∈ [a, a+c].

Then with probability at least 1δ:

1 t -1 t i=1 X i - 1 t t j=1 X j 2 -σ ≤ 2c log(2/δ) t -1 . On ξ 1 , the {X k,i } i , 1 ≤ k ≤ K, 1 ≤ i ≤ t are t i.i.d
. bounded random variables with standard deviation σk .

Let ξ 2 = ξ 2,K,n (δ) be the event:

ξ 2 = 1≤k≤K, 1≤t≤n    1 t -1 t i=1 X k,i - 1 t t j=1 X k,j 2 -σk ≤ 2 c 1 log(c 2 /δ) log(2/δ) t -1    .
Using Theorem 10 of [START_REF] Maurer | Empirical bernstein bounds and sample-variance penalization[END_REF] and a union bound, we deduce that Pr(ξ 1 ∩ ξ 2 ) ≥ 1 -2nKδ. Now, from Equation 45, we have on

ξ 1 ∩ ξ 2 , for all 1 ≤ k ≤ K, 2 ≤ t ≤ n: 1 t -1 t i=1 X k,i - 1 t t j=1 X k,j 2 -σ k ≤ 2 c 1 log(c 2 /δ) log(2/δ) t -1 + 2c 1 δ(1 + c 2 + log(c 2 /δ)) 1 -δ ≤ 2 2c 1 log(c 2 /δ) log(2/δ) t + 2c 1 δ(1 + c 2 + log(c 2 /δ)) 1 -δ ,
from which we deduce Lemma 5 (since ξ ∩ ξ 2 ⊆ ξ and 2 ≤ t ≤ n).

We deduce the following corollary when the number of samples T k,t are random.

Corollary 1. For any k = 1, . . . , K and t = 2K, . . . , n, let {X k,i } i be n i.i.d. random variables drawn from ν k , satisfying Assumption 1. Let T k,t be any random variable taking values in {2, . . . , n}. Let σ2 k,t be the empirical variance computed from Equation 17. Then, on the event ξ, we have:

|σ k,t -σ k | ≤ 2a log(2/δ) T k,t . (46)

Other important properties

A stopping time problem: We now draw a connection between the adaptive sampling and stopping time problems. We report the following proposition which is a type of Wald's Theorem for variance (see e.g. ?).

Proposition 3. Let {F t } be a filtration and X t a F t -adapted sequence of i.i.d. random variables with variance σ 2 . Assume that F t and the σ-algebra generated by {X i : i ≥ t + 1} are independent and T is a stopping time w.r.t. F t with a finite expected value

. If E[X 2 1 ] < ∞ then E T i=1 X i -T µ 2 = E[T ] σ 2 . ( 47
)
Bound on the regret outside of ξ. The next lemma provides a bound for the loss whenever the event ξ does not hold.

Lemma 6. Let Assumption 1 holds. Then for every arm k:

E |μ k,n -µ k | 2 I ξ C ≤ 2c 1 n 2 Kδ(1 + log(c 2 /2nKδ)) .
Proof. Since the arms have sub-Gaussian distribution, for any 1 ≤ k ≤ K and 1 ≤ t ≤ n, we have

P |X k,t -µ k | 2 ≥ ǫ ≤ c 2 exp(-ǫ/c 1 ) ,
and thus by setting ǫ = c 1 log(c 2 /2nKδ) 11 , we obtain

P |X k,t -µ k | 2 ≥ c 1 log(c 2 /2nKδ) ≤ 2nKδ .
We thus know that max

Ω/P(Ω)=2nKδ E |X k,t -µ k | 2 I {Ω} ≤ ∞ c1 log(c2/2nKδ) c 2 exp(-ǫ/c 1 )dǫ + c 1 log(c 2 /2nKδ)P Ω = 2c 1 nKδ(1 + log(c 2 /2nKδ)) .
Since the event ξ C has a probability at most 2nKδ, for any 1 ≤ k ≤ K and 1 ≤ t ≤ n, we have

E |X k,t -µ k | 2 I ξ C ≤ max Ω/P(Ω)=2nKδ E |X k,t -µ k | 2 I {Ω} ≤ 2c 1 nKδ(1+log(c 2 /2nKδ)) .
The claim follows from the fact that

E |μ k,n -µ k | 2 I ξ C ≤ n t=1 E |X k,n - µ k | 2 I ξ C ≤ 2c 1 n 2 Kδ(1 + log(c 2 /2nKδ)).

Technical inequalities

Upper and lower bound on a:

If δ = n -7/2 , with n ≥ 4K ≥ 8 a = 2c 1 log(c 2 /δ) + c 1 δ(1 + c 2 + log(c 2 /δ)) (1 -δ) 2 log(2/δ) n 1/2 ≤ 7c 1 (c 2 + 1) log(n) + 1 n 3/2 c 1 (2 + c 2 ) ≤ 2 2c 1 (c 2 + 2) log(n).
[On multiplie juste par √ 2 et on vire le terme en μ par rapport a avant.]

We also have by just keeping the first term and choosing c 2 such that c 2 ≥ eδ = en -7/2

a = 2c 1 log(c 2 /δ) + c 1 δ(1 + c 2 + log(c 2 /δ)) (1 -δ) 2 log(2/δ) n 1/2 ≥ √ 2c 1 ≥ √ c 1 .
Lower bound on c(δ) when δ = n -7/2 : Since the arms have sub-Gaussian distribution, for any 1 ≤ k ≤ K and 1 ≤ t ≤ n, we have

P |X k,t -µ k | 2 ≥ ǫ ≤ c 2 exp(-ǫ/c 1 ) ,
We then have

E |X k,t -µ k | 2 ≤ ∞ 0 c 2 exp(-ǫ/c 1 )dǫ = c 2 c 1 We then have Σ w ≤ √ c 2 c 1 .
If δ = n -7/2 , we obtain by using the lower bound on a that c(δ = n -7/2 ) = 2a log(2/δ)

Σ w + 4a log(2/δ) 1 K 2/3 = 1 2K - 1 2K Σ w Σ w + 4a log(2/δ) 2/3 ≥ 1 2K - 1 2K Σ w Σ w + 4 c 1 log(n) 2/3 ≥ 1 2K 2/3 √ c 1 Σ w + √ c 1 2/3 ≥ 1 2K 2/3 1 √ c 2 + 1 2/3
, by using Σ w ≤ √ c 2 c 1 for the last step.

Upper bound on E |μ k,n -µ k | 2 I ξ C
when δ = n -7/2 : We get from Lemma 6 when δ = n -7/2 and when choosing c 2 such that c 2 ≥ 2enKδ = 2Ken -5/2

E |μ k,n -µ k | 2 I ξ C ≤ 2c 1 n 2 Kδ(1 + log(c 2 /2nKδ)) ≤ 2c 1 K 1 + 5 2 (c 2 + 1) log(n) n -3/2 ≤ 6c 1 K(c 2 + 1) log(n)n -3/2 . Upper bound on B for δ = n -7/2 B = 16Ka log(2/δ) √ Σ + 2a log(2/δ) c(δ) ≤ 36K log(n)a √ Σ + 12 √ K( √ c 2 + 1)a log(n) ≤ 36K log(n)a √ Σ + 432K 3/2 ( √ c 2 + 1)a 2 log(n) ≤ 72 √ 2K log(n) c 1 (c 2 + 1) √ Σ + 3456c 1 (c 2 + 2)K 3/2 ( √ c 2 + 1) log(n) 2 ≤ 3559 c 1 (c 2 + 2) 2 + 1 K 3/2 log(n) 2 . Upper bound on C for δ = n -7/2 C = 64 √ 2K 3/2 a 2 log(2/δ) c(δ) ≤ 640K 2 ( √ c 2 + 1) log(n)a 2 ≤ 640K 2 c 1 (c 2 + 2) 2 log(n) 2 ≤ 640K 2 c 1 (c 2 + 2) 2 log(n) 2 .

B.2 Allocation Performance and Regret Bounds for Sub-Gaussian Distributions

In this section, we first provide the proof of Lemma 2, we then derive the regret bound of Theorem 2 in the general case, and we prove the Theorem 3 for Gaussians.

Proof (Lemma 2). The proof consists of the following five main steps.

Step 1. Lower bound of order O( √ n). Let k be the index of an arm such that T k,n ≥ n K and t + 1 ≤ n be the last time that it was pulled, i.e., T k,t = T k,n -1 and T k,t+1 = T k,n .12 From Equation 46 and the fact that T k,n ≥ n K ≥ 4, we obtain on ξ

B k,t+1 ≤ 1 T k,t σ k + 4a log(2/δ) T k,t 2 ≤ K √ Σ + 4a log(2/δ) 2 n , (48)
where we also used T k,t ≥ 1 to bound T k,t in the parenthesis and the fact that σ k ≤ √ Σ. Since at time t we assumed that arm k has been chosen then for any other arm q, we have

Bq,t+1 ≤ B k,t+1 . (49)
From the definition of B q,t+1 , removing all the terms but the last and using the fact that T q,t ≤ T q,n , we obtain the lower bound

Bq,t+1 ≥ 4a 2 log(2/δ) T 2 q,t ≥ 4a 2 log(2/δ) T 2 q,n . ( 50
)
Combining Equations 48-50, we obtain

4a 2 log(2/δ) T 2 q,n ≤ K √ Σ + 4a log(2/δ) 2 n .
Finally, this implies that for any q

Tq,n ≥ 2a log(2/δ) √ Σ + 4a log(2/δ) n K . ( 51
)
In order to simplify the notation, in the following we use

c(δ) = 2a log(2/δ) √ K √ Σ + 4a log(2/δ)
, thus obtaining T q,n ≥ c(δ) √ n on the event ξ for any q.

Step 2. Mechanism of the algorithm. Similar to Step 1 of the proof of Lemma 4, we first recall the definition of B q,t+1 used in the B-AS algorithm Using Lemma 1 it follows that on ξ, for any q,

σ 2 q Tq,t ≤ Bq,t+1 ≤ 1 Tq,t σq + 4a log(2/δ) Tq,t 2 . ( 52
)
Let t + 1 > 2K be the time when an arm q is pulled for the last time, that is T q,t = T q,n -1. Note that there is at least an arm that verifies this as n ≥ 4K. Since at time t + 1 this arm q is chosen, then for any other arm p, we have

Bp,t+1 ≤ Bq,t+1 . (53)
From Equation 52and T q,t = T q,n -1, we obtain Summing over all q that are pulled after initialization on both sides, we obtain on ξ for any arm p

σ 2 p T p,n (n -2K) ≤ q|Tq,n>2 σ q + 4a log(2/δ) T q,n -1 2 , ( 56
)
because the arms that are not pulled after the initialization are only pulled twice.

Step 3. Intermediate lower bound. It is possible to rewrite Equation 56, using the fact that T q,n ≥ 2, as

σ 2 p T p,n (n -2K) ≤ q σ q + 4a log(2/δ) T q,n 2 ≤ q σ q + 4a 2 log(2/δ) T q,n 2 .
Plugging Equation 51 in Equation 56, we have on ξ for any arm p

σ 2 p Tp,n (n -2K) ≤ q σq + 4a 2 log(2/δ) Tq,n -1 2 ≤ √ Σ + 4 √ Ka 2 log(2/δ) c(δ) √ n 2 , (57)
because for any sequence (a k ) i=1,...,K ≥ 0, and any b ≥ 0,

k (a k + b) 2 ≤ ( k a 2 k + √ Kb)
2 by Cauchy Schwartz. Building on this bound we may finally recover the desired bound.

Step 4. Final lower bound. We first develop the square in Equation 56 using T q,n ≥ 2 as

σ 2 p Tp,n (n -2K) ≤ q σ 2 q + 8a 2 log(2/δ) q σq Tq,n + q 32a 2 log(2/δ) Tq,n .
We now use the bound in Equation 57 in the second term of the RHS and the bound in Equation 51 to bound T k,n in the last term, thus obtaining

σ 2 p Tp,n (n-2K) ≤ Σ+8a 2 log(2/δ) K √ n -2K √ Σ+4 √ Ka 2 log(2/δ) c(δ) √ n + 32Ka 2 log(2/δ) c(δ) √ n .
By using again n ≥ 4K and some algebra, we get

σ 2 p Tp,n (n -2K) ≤ Σ + 16Ka Σ log(2/δ) n + 64 √ 2K 3/2 a 2 log(2/δ) c(δ) n -3/4 + 32Ka 2 log(2/δ) c(δ) √ n = Σ + 16Ka log(2/δ) √ n √ Σ + 2a log(2/δ) c(δ) + 64 √ 2K 3/2 a 2 log(2/δ) c(δ) n -3/4 . ( 58
)
We now invert the bound and obtain the final lower-bound on T p,n as follows:

Tp,n ≥ σ 2 p (n-2K) Σ 1 + 16Ka log(2/δ) Σ √ n √ Σ + 2a log(2/δ) c(δ) + 64 √ 2K 3/2 a 2 log(2/δ) Σ c(δ) n -3/4 -1 ≥ σ 2 p (n -2K) Σ 1 - 16Ka log(2/δ) Σ √ n √ Σ + 2a log(2/δ) c(δ) -64 √ 2K 3/2 a 2 log(2/δ) Σ c(δ) n -3/4 ≥ T * p,n -Kλp 16a log(2/δ) Σ √ Σ + 2a log(2/δ) c(δ) n 1/2 + 64 √ 2Ka 2 log(2/δ) Σ c(δ) n 1/4 + 2 .
Note that the above lower bound holds with high probability for any arm p.

Step 5. Upper bound. The upper bound on T p,n follows by using T p,n = nq =p T q,n and the previous lower bound, that is

Tp,n ≤ n - q =p T * q,n + q =p Kλq 16a log(2/δ) Σ √ Σ + 2a log(2/δ) c(δ) n 1/2 + 64 √ 2Ka 2 log(2/δ) Σ c(δ) n 1/4 + 2 ≤ T * p,n + K 16a log(2/δ) Σ √ Σ + 2a log(2/δ) c(δ) n 1/2 + 64 √ 2Ka 2 log(2/δ) Σ c(δ) n 1/4 + 2 .
⊓ ⊔ We can now prove a general bound for the regret of this algorithm.

Proof (Theorem 2).

At first let us call, for the sake of convinience,

B = 16Ka log(2/δ) √ Σ + 2a log(2/δ) c(δ) and C = 64 √ 2K 3/2 a 2 log(2/δ) c(δ) .
Then Equation 58 easily becomes

σ 2 p Tp,n (n -2K) ≤ Σ + B √ n + C n 3/4 . ( 59
)
We also have the upper bound in Lemma 2 which can be rewritten:

Tp,n ≤ T * p,n + BK Σ √ n + CK Σ n 1/4 + 2K.
Note that because this upper bound holds on an event of probability bigger than 1 -4nKδ and also because of T p,n is bounded by n anyways, we can convert the former upper bound in a bound in expectation:

E(Tp,n) ≤ T * p,n + BK Σ √ n + CK Σ n 1/4 + 2K + n × 4nKδ (60)
We recall that the loss of any arm k is decomposed in two parts as follows:

L k,n = E[(μ k,n -µ) 2 I {ξ}] + E[(μ k,n -µ) 2 I{ξ C }].
By combining that and Equations 59, 60, and 47 (as done in Equation 35), we obtain for the first part of the loss and because:

E[(μ k,n -µ) 2 I {ξ}] ≤ 1 σ 2 p (n -2K) 2 Σ + B √ n + C n 3/4 2 T * p,n + KB Σ √ n + CK Σ n 1/4 + 2K + 4n 2 Kδ ≤ 1 (n -2K) 2 Σ 2 + 2Σ( B √ n + C n 3/4 ) + (B + C) 2 n 3/2 n Σ + KB Σ 2 λ k √ n + CK Σ 2 λ k n 1/4 + 2K Σλ k + 4n 2 Kδ Σλ k ≤ 1 (n -2K) 2 nΣ + KB λ k √ n + CK + 2KΣ λ k n 1/4 + 4n 2 KΣδ λ k + 2B √ n + 2Cn 1/4 + 2(B + C)( KB Σ + KC Σ + 2K) λ k + 8(B + C)n 2 Kδ λ k + (B + C) 2 Σλ k √ n K(B + C) Σ + 3K + 4n 2 Kδ (B + C) 2 Σλ k ≤ 1 (n -2K) 2 nΣ + 2KB λ k √ n + K λ k (B + C) Σ + 3 3 + 2(C + Σ) n 1/4 + 4n 2 Kδ λ k 2(B + C) + Σ + (B + C) 2 ) . Now note, as δ = n -5/2 , that E[(μ k,n -µ) 2 I {ξ}] ≤ Σ n + 8KB λ k n 3/2 + 4K n 7/4 λ k 2 (B + C) Σ + 3 3 + 2(C + Σ) + 16Kn -5/2 λ k 2(B + C) + Σ + (B + C) 2 ) ≤ Σ n + 8KB λ k n 3/2 + 24K n 7/4 λ k (B + C) Σ + 3 3 1 + 2Σ 3 .
Finally, combining that with Lemma 6 gives us for the regret:

Rn ≤ 8KB λminn 3/2 + 24K n 7/4 λmin (B + C) Σ + 3 3 1 + 2Σ 3 + 2c1nKδ(1 + log(c2/2nKδ)).
By recalling the bounds on B and C in Appendix B.1 and taking δ = n -5/2 , we obtain:

Rn ≤ 8KB λminn 3/2 + 24K n 7/4 λmin (B + C) Σ + 3 3 1 + 2Σ 3 + 6c1c2K log(n)n -3/2 ≤ 28230 c1(c2 + 2) 2 + 1 K 5/2 log(n) 2 λminn 3/2 + 24K n 7/4 λmin 4368K 2 c1(c2 + 2) 2 log(n) 2 3 1 Σ 3 + 2 .

⊓ ⊔

B.3 Regret Bound for Gaussian Distributions

Here we report the proof of Lemma 3 which states that when the distributions of the arms are Gaussian, bounding the regret of the B-AS algorithm does not require upper-bounding the number of pulls T k,n (it can be bounded only by using a lower bound on the number of pulls). Before reporting the proof of Lemma 3, we recall a property of the normal distribution that is used in this proof (see e.g., [START_REF] Brémaud | An Introduction to Probabilistic Modeling[END_REF]).

Proposition 4. Let X 1 , . . . , X n be n i.i.d. Gaussian random variables. Then their empirical mean μn = 1 n n i=1 X i and empirical variance σ2 n = 1 n-1 n i=1 (X iμn ) 2 are independent of each other.

Proof (Lemma 3).

Let T ≥ 2 be a integer-valued random variable, which is a stopping time with respect to the filtration F t generated by the sequence of i.i.d. random variables X t drawn from a Gaussian distribution. Write μt = 1 t t i=1 X i and σ2 t = 1 t-1 t i=1 (X iμt ) 2 the empirical mean and variance of the t first samples.

Lemma 7. We have

σ2 t+1 = t -1 t σ2 t + 1 t + 1 (X t+1 -μt ) 2 ,
which leads to for any t ≥ 3 to

σ2 t = a 2,t σ 2 2 + t i=3 a i,t (X i -μi-1 ) 2 ,
where the (a i,t ) i are real numbers.

Proof. At first note that from the definition of empirical variance and empirical mean

σ2 t+1 = 1 t t+1 i=1 (X i -μt+1 ) 2 = 1 t t i=1 (X i -μt+1 + μt -μt ) 2 + 1 t (X t+1 -μt+1 ) 2 = 1 t t i=1 (X i -μt ) 2 + 1 t (X t+1 -μt+1 ) 2 + (μ t -μ+1 ) 2 = 1 t t i=1 (X i -μt ) 2 + t (t + 1) 2 (X t+1 -μt ) 2 + 1 (t + 1) 2 (X t+1 -μt ) 2 = 1 t t i=1
(X iμt ) 2 + t t + 1 (X t+1μt ) 2 , which proofs the first part of the lemma. We now want to prove the second part by induction. Note that for t = 3, the property we just proved gives us

σ2 3 = t -1 t σ2 2 + 1 3 (X 3 -μ2 ) 2 ,
and the property is true for t = 3. Now assume that for a given t ≥ 3, we have

σ2 t = a 2,t σ 2 2 + t i=3 a i,t (X i -μi-1 ) 2 ,
where the (a i,t ) i are real numbers. Note that by using σ2 and then the property holds at time t+1 with a 2,t+1 = t-1 t a 2,t and ∀2 ≤ i ≤ t, a i,t+1 = t-1 t a i,t and a t+1,t+1 = 1 t+1 .

Lemma 8.

∀2 ≤ t ≤ n, μt σ2 2 , (X i+1 -μi ) 2 i≤t-1 ∼ N (µ, σ 2 t )
Proof. We proof this result by induction.

Step 1: Initialization. For t = 3, we have by Lemma 7

σ2 3 = t -1 t σ2 2 + 1 3 (X 3 -μ2 ) 2
As X 1 , X 2 ∼ N (µ, σ 2 ) and are independent, we know that σ2 2 is independent of μ2 . We thus have μ2 σ2 2 ∼ N (µ, σ 2 /2). Note that X 3 is independent from X 1 and X 2 , so from σ 2 2 as well and we have X 3 σ2 2 ∼ N (µ, σ 2 ). This means that U = (X 3 -μ2 ) σ2

2 and V = (μ 3 -µ) σ2 2 = ( 1 3 X 3 + 2 3 μ2 -µ) σ2 2 are zero-mean gaussians. Note also that μ2 σ2 2 is independent of X 3 σ2 2 , again because X 3 is independent of (X 1 , X 2 ). From that we deduce that

E U V = E X 3 -μ2 1 3 X 3 + 2 3 μ2 -µ σ2 2 = E (X 3 -µ) -(μ 2 -µ) 1 3 (X 3 -µ) + 2 3 (μ 2 -µ) σ2 2 = 1 3 σ 2 - 2 3 σ 2 2 = 0.
As U and V are zero mean gaussians, the fact that their cross product is zero means that they are independent and that V U = V σ2 2 , U ∼ V σ2 2 . In other words, (μ 3µ) σ2

2 , (X 3 -μ2 ) 2 ∼ (μ 3µ) σ2 2 ∼ N (µ, σ 2 /3), because (μ 3µ) σ 2 2 ∼ N (0, σ 2 /3) from the fact that μ2 σ2 2 ∼ N (µ, σ 2 /2) and X 3 σ2 2 ∼ N (µ, σ 2 /2) and because they are independent. This shows the property for t = 3.

Step 2: Induction Property. Assume that for a given t, we have μt σ2 2 , (X i+1μi ) 2

i≤t-1

∼ N (µ, σ 2 t )
Let us call U = (X t+1μt ) σ2 2 , (X i+1μi ) 2

i≤t-1 and V = (µ t+1 -

µ) σ2 2 , (X i+1 -μi ) 2 i≤t-1 = ( t t+1 (µ t -µ) + t t+1 (X t+1 -µ)) σ2 2 , (X i+1 - μi ) 2 i≤t-1
.

Note that because of X t+1 is independent from (X 1 , . . . , X t ), we have

X t+1 σ2 2 , (X i+1 -μi ) 2 i≤t-1 ∼ N (µ, σ 2 ),
and also that

X t+1 σ2 2 , (X i+1 -μ i ) 2 i≤t-1 is independent from μt σ2 2 , (X i+1 - μi ) 2 i≤t-1
. This combined with the induction assumption ensures that U and V are zero-mean gaussians, and also that

E U V = E X t+1 -μt 1 t + 1 X t+1 + t t + 1 μt -µ σ2 2 , (X i+1 -μi ) 2 i≤t-1 = E (X t+1 -µ) -(μ t -µ) 1 t + 1 (X t+1 -µ) + t t + 1 (μ t -µ) σ2 2 , (X i+1 -μi ) 2 i≤t-1 = 1 t + 1 σ 2 - t t + 1 σ 2 t = 0
As U and V are zero mean gaussians, the fact that their cross product is zero means that they are independent and that V U = V σ2 2 , (X i+1μi )

2 i≤t-1 , U ∼ V σ2 2 , (X i+1 -μi ) 2 i≤t-1
. In other words,

(μ t+1 -µ) ˆσ2 2 , (X i+1 -μi ) 2 i≤t ∼ (μ t+1 -µ) σ2 2 , (X i+1 -μi ) 2 i≤t-1
∼ N (µ, σ 2 /(t + 1)), because (μ t+1 -µ) σ 2 2 ∼ N (0, σ 2 /(t+1)) from the fact that μt σ2 2 , (X i+1μi ) 2 i≤t-1 ∼ N (µ, σ 2 /t) and X t+1 σ2 2 , (X i+1μi ) 2

i≤t-1

∼ N (µ, σ 2 /2) and because they are independent. This finishes the induction.

From Lemma 8 and the second part of Lemma 7, we have ∀2 ≤ t ≤ n:

μt σ2 i i≤t ∼ N (µ, σ 2 t )
The algorithm we use is such that T k,n is a (noisy with respect to the samples on the other arms) function of the σ2 where mt = 1 t t i=1 X i where X i is the ith sample collected from arm k.

⊓ ⊔

We prove Theorem 3.

Proof (Theorem 3). Note that Lemma 2 is only based on the assumption that samples are generated by a sub-Gaussian distribution. Here we strengthen that assumption and require all the distributions to be Gaussian with parameters µ k and σ 2 k . We recall that the loss of any arm k is decomposed in two parts as follows:

L k,n = E[(μ k,n -µ) 2 I {ξ}] + E[(μ k,n -µ) 2 I ξ C ].
From Lemma 3 and the bound in Equation 58, we have

E[(μ k,n -µ) 2 I {ξ}] ≤ σ 2 k T k,n ≤ Σ n + 4K n 2 + B n 3/2 + C n 7/4 ≤ Σ n + 4K n 2 + 7056 n 3/2 [3528 c1(c2 + 2) 2 + 1 K 3/2 log(n) 2 + 1280K 2 c1(c2 + 2) 2 log(n) 2 + ( √ c2 + 1)μ 2 n 2 n -7/4 ≤ Σ n + 4K n 2 + 7056 n 3/2 c1(c2 + 2) 2 + 1 K 3/2 log(n) 2 + 2560K 2 Σ(c2 + 1)(μ + μ2 ) + c1(c2 + 2) 2 log(n) 2 n -7/4 . ( 61
)
where we use the bounds on B and C in Appendix B.1. Note that for Gaussian distributions P(|X -µ| > t) ≤ exp(-t 2 /2σ 2 ). From Lemma 6 and by taking c 1 = 2Σ and c 2 = 1, we obtain also with δ = n -5/2

E (μ k,n -µ) 2 I ξ C ≤ 8K n 3/2 log(n). (62)
Finally, combining Equations 61 and 62, and recalling the definition of regret, we have

Rn ≤ 4K n 2 + 7060 n 3/2 c1(c2 + 2) 2 + 1 K 3/2 log(n) 2 + 2560K 2 Σ(c2 + 1)(c1(c2 + 2) 2 log(n) 2 n -7/4 .

(63)

Fig. 3 .

 3 Fig. 3. (left) The rescaled regret of CH-AS, B-AS, and GAFS-MAX algorithms on a two-armed problem, where the distributions of the arms are Gaussian. (right) The rescaled regret of B-AS for two bandit problems, one with two Gaussian arms and one with a Gaussian and a Rademacher arms.

  and that T k,n depends on the samples of arm k only trough those empirical variances σ2 k,t t≤n . We thus haveE (μ k,nµ k ) 2 I {ξ} = n t=T k,n E (μ k,nµ k ) 2 T k,n = t P(T k,n = t)

  Furthermore, since T p,t ≤ T p,n , then

					Bp,t+1 ≥	σ 2 p Tp,t	≥	σ 2 p Tp,n	.	(55)
	Combining Equations 53-55, we obtain
			σ 2 p Tp,n	(Tq,n -1) ≤ σq + 4a	log(2/δ) Tq,n -1
	Bq,t+1 ≤	1 Tq,t	σq + 4a	log(2/δ) Tq,t	2	=	1 Tq,n -1	σq + 4a	log(2/δ) Tq,n -1	2	.	(54)

2

.

The notation un = Õ(vn) means that there exist C > 0 and α > 0 such that un ≤ C(log n) α vn for sufficiently large n.

This equality does not hold when the number of pulls is random, e.g., in adaptive algorithms, where the strategy depends on the random observed samples.

Notice that this is a biased estimator of the variance.

The total loss L k,n is decomposed asL k,n = L k,n (ξ) + L k,n (ξ c ).

The exact definition of the event ξ is available in Sec. B.1 of[START_REF] Carpentier | Upper-confidence-bound algorithms for active learning in multi-armed bandits[END_REF].

Note that for a single Gaussian distribution c1 = 2σ, where σ is the standard deviation of the distribution. Here we use c1 = 2Σ in order for the assumption to be satisfied for all K distributions simultaneously.

A random variable X is Rademacher if X ∈ {-1, 1} and admits values -1 and 1 with equal probability.

Note that such an arm always exists for any possible allocation strategy given the constraint n = q Tq,n.


Paul Grace
email: p.grace@lancaster.ac.uk

Gordon Blair
email: gordon@comp.lancs.ac.uk

Valérie Issarny

Valerie Issarny
email: valerie.issarny@inria.fr

Emergent Middleware

Emergent Middleware by Paul Grace, Gordon S. Blair and Valerie Issarny

We are moving towards a world in which everything is connected. Yet such a goal highlights the deficiencies of today's systems platforms in achieving a fundamental property of distributed systems, namely interoperability. Faced with extreme heterogeneity of computational devices and networks, how can we ensure that every system can talk to every other system? Interoperability is the ability for two systems to exchange, understand and use each other's data, and is a long-standing problem in the field of distributed systems. However, the emergence of pervasive computing and the Internet of Things have brought about new challenges to achieving universal interoperability. Today's complex distributed systems are characterized by extreme heterogeneity and spontaneous interactions. Computational devices ranging from embedded devices, sensors, and smartphones through to cluster machines and the Cloud use a wide range of communication networks and middleware protocols to communicate with one another. However, as soon as two systems adhere to heterogeneous protocols (from application down network layers) to interact with each other, interoperability is impossible. Standards are a well-established approach to rectifying these types of problems, eg the set of CORBA standards from the OMG, and the set of Web Services standards from the W3C. Where two systems agree upon such a standard, interoperability can be guaranteed. However, systems may encounter one another spontaneously where no such agreement is possible, and hence where the communication protocols differ they cannot interoperate.

The CONNECT project, which began in February 2009 and concludes at the end of 2012, is an EU Future and Emerging Technologies project involving partners whose expertise covers middleware, software engineering, formal methods, machine learning, software synthesis and systems dependability. The aim of the project is to overcome interaction protocol heterogeneity at all layers, on-the-fly, by using a revolutionary approach that dynamically generates the necessary interoperability solution to connect two heterogeneous systems. We term this new style of middleware: Emergent middleware. 1. Message interoperability is dedicated to the interpretation of messages from/toward networked systems (listeners parse messages and actuators compose messages); by plugging in the correct listeners and actuators we can communicate with any legacy protocol. 2. Behavioural interoperability mediates the interaction protocols run by the communicating networked systems by translating messages from one protocol to the other.

In order to dynamically generate the above solution on-the-fly, CONNECT employs a runtime architecture that executes the following phases (these phases are depicted in Figure 1):

1. Discovery. Systems in the local environment are discovered and their information (eg an interface description) is used to build a model of the service provided and what middleware it utilizes. Ontological information is then used to understand this provision and obtains better matching with other systems, ie does one system provide the behaviour another requires (irrespective of the heterogeneity)? 2. Learning. Active learning algorithms determine more precisely the behaviour of a given system in terms of the sequence of operations executed to provide a particular service and therefore enhance the model of a system. 3. Synthesis. The models of the two systems are used to calculate the necessary mediator that will ensure the translation between two systems. The generated mediator is used to create an emergent middleware, aka CONNECTor, which is deployed to achieve the interoperability between two systems. 4. Evolution. The deployed CONNECTor is monitored to ensure it is meeting the nonfunctional requirements of the connection (eg performance in terms of a minimum level of network latency). Where the requirement is not met, the architecture cycle is re-run to generate a new CONNECTor. CONNECT has illustrated the possibilities of emergent solutions. However, the inherent openness and probability of such solutions raise important challenges, especially when deployed at Internet scale. Here it must be reliably able to produce correct mediators and also be secure against malicious threats, which are other areas of active research in CONNECT.

Figure 1

 1 Figure 1 illustrates an emergent middleware solution. The figure shows a CONNECTor ensuring interoperation between two networked systems and performs two important functions:

  The above functionalities are supported by dedicated Enablers that are being developed as part of CONNECT and released open source from the project Web site. In particular, the Starlink open source software framework offers the tools to develop Message interoperability solutions. Currently, Starlink has been successfully used to dynamically generate CONNECTors directly between middleware protocols such as: CORBA to XML-RPC, and Service Location Protocol to Bonjour; it has also been used to build bridges between heterogeneous application systems eg a Flickr client application built using XML-RPC interoperating with the Picasa REST API.

Figure 1 :

 1 Figure 1: On the fly generation of emergent middleware

Links:

The Connect Project website: http://www.connect-forever.eu

The Starlink Framework: http://starlink.sourceforge.net