Victor Gabillon
email: victor.gabillon@inria.fr

Mohammad Ghavamzadeh
email: mohammad.ghavamzadeh@inria.fr

Alessandro Lazaric
email: alessandro.lazaric@inria.fr

Best Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence

We study the problem of identifying the best arm(s) in the stochastic multi-armed bandit setting. This problem has been studied in the literature from two different perspectives: fixed budget and fixed confidence. We propose a unifying approach that leads to a meta-algorithm called unified gap-based exploration (UGapE), with a common structure and similar theoretical analysis for these two settings. We prove a performance bound for the two versions of the algorithm showing that the two problems are characterized by the same notion of complexity. We also show how the UGapE algorithm as well as its theoretical analysis can be extended to take into account the variance of the arms and to multiple bandits. Finally, we evaluate the performance of UGapE and compare it with a number of existing fixed budget and fixed confidence algorithms.

Introduction

The problem of best arm(s) identification [START_REF] Even-Dar | Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems[END_REF][START_REF] Bubeck | Pure exploration in multi-armed bandit problems[END_REF][START_REF] Audibert | Best arm identification in multi-armed bandits[END_REF] in the stochastic multi-armed bandit setting has recently received much attention. In this problem, a forecaster repeatedly selects an arm and observes a sample drawn from its reward distribution during an exploration phase, and then is asked to return the best arm(s). Unlike the standard multi-armed bandit problem, where the goal is to maximize the cumulative sum of rewards obtained by the forecaster (see e.g., [START_REF] Robbins | Some aspects of the sequential design of experiments[END_REF][START_REF] Auer | Finite-time analysis of the multi-armed bandit problem[END_REF]), in this problem the forecaster is evaluated on the quality of the arm(s) returned at the end of the exploration phase. This abstract problem models a wide range of applications. For instance, let us consider a company that has K different variants of a product and needs to identify the best one(s) before actually placing it on the market. The company sets up a testing phase in which the products are tested by potential customers. Each customer tests one product at the time and gives it a score (a reward). The objective of the company is to return a product at the end of the test phase which is likely to be successful once placed on the market (i.e., the best arm identification), and it is not interested in the scores collected during the test phase (i.e., the cumulative reward).

The problem of best arm(s) identification has been studied in two distinct settings in the literature.

Fixed budget. In the fixed budget setting (see e.g., [START_REF] Bubeck | Pure exploration in multi-armed bandit problems[END_REF][START_REF] Audibert | Best arm identification in multi-armed bandits[END_REF]), the number of rounds of the exploration phase is fixed and is known by the forecaster, and the objective is to maximize the probability of returning the best arm(s). In the above example, the company fixes the length of the test phase before hand (e.g., enrolls a fixed number of customers) and defines a strategy to choose which products to show to the testers so that the final selected product is the best with the highest probability. Audibert et al. [START_REF] Audibert | Best arm identification in multi-armed bandits[END_REF] proposed two different strategies to solve this problem. They defined a strategy based on upper confidence bounds, called UCB-E, whose optimal parameterization is strictly related to a measure of the complexity of the problem. They also introduced an elimination algorithm, called Successive Rejects, which divides the budget n in phases and discards one arm per phase. Both algorithms were shown to have nearly optimal probability of returning the best arm. Deng et al. [START_REF] Deng | Active learning for developing personalized treatment[END_REF] and Gabillon et al. [START_REF] Gabillon | Multi-bandit best arm identification[END_REF] considered the extension of the best arm identification problem to the multi-bandit setting, where the objective is to return the best arm for each bandit. Recently, Bubeck et al. [START_REF] Bubeck | Multiple identifications in multi-armed bandits[END_REF] extended the previous results to the problem of m-best arm identification and introduced a new version of the Successive Rejects algorithm (with accept and reject) that is able to return the set of the m-best arms with high probability.

Fixed confidence. In the fixed confidence setting (see e.g., [START_REF] Maron | Hoeffding races: Accelerating model selection search for classification and function approximation[END_REF][START_REF] Even-Dar | Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems[END_REF]), the forecaster tries to minimize the number of rounds needed to achieve a fixed confidence about the quality of the returned arm(s). In the above example, the company keeps enrolling customers in the test until it is, e.g., 95% confident that the best product has been identified. Maron & Moore [START_REF] Maron | Hoeffding races: Accelerating model selection search for classification and function approximation[END_REF] considered a slightly different setting where besides a fixed confidence also the maximum number of rounds is fixed. They designed an elimination algorithm, called Hoeffding Races, based on progressively discarding the arms that are suboptimal with enough confidence. Mnih et al. [START_REF] Mnih | Empirical Bernstein stopping[END_REF] introduced an improved algorithm, built on the Bernstein concentration inequality, which takes into account the empirical variance of each arm. Even-Dar et al. [START_REF] Even-Dar | Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems[END_REF] studied the fixed confidence setting without any budget constraint and designed an elimination algorithm able to return an arm with a required accuracy (i.e., whose performance is at least -close to the optimal arm). Kalyanakrishnan & Stone [START_REF] Kalyanakrishnan | Efficient selection of multiple bandit arms: Theory and practice[END_REF] further extended this approach to the case where the m-best arms must be returned with a given confidence. Finally, Kalyanakrishnan et al. [START_REF] Kalyanakrishnan | Pac subset selection in stochastic multiarmed bandits[END_REF] recently introduced an algorithm for the case of m-best arm identification along with a thorough theoretical analysis showing the number of rounds needed to achieve the desired confidence.

Although the fixed budget and fixed confidence problems have been studied separately, they display several similarities. In this paper, we propose a unified approach to these two settings in the general case of m-best arm identification with accuracy . 1 The main contributions of the paper can be summarized as follows:

Algorithm. In Section 3, we propose a novel meta-algorithm, called unified gap-based exploration (UGapE), which uses the same arm selection and (arm) return strategies for the two settings. This algorithm allows us to solve settings that have not been covered in the previous work (e.g., the case of = 0 has not been studied in the fixed budget setting). Furthermore, we show in Appendix C that UGapE outperforms existing algorithms in some settings (e.g., it improves the performance of the algorithm by Mnih et al. [START_REF] Mnih | Empirical Bernstein stopping[END_REF] in the fixed confidence setting). We also provide a thorough empirical evaluation of UGapE and compare it with a number of existing fixed budget and fixed confidence algorithms in Appendix C. Theoretical analysis. Similar to the algorithmic contribution, in Section 4, we show that a large portion of the theoretical analysis required to study the behavior of the two settings of the UGapE algorithm can be unified in a series of lemmas. The final theoretical guarantees are thus a direct consequence of these lemmas when used in the two specific settings. Problem complexity. In Section 4.4, we show that the theoretical analysis indicates that the two problems share exactly the same definition of complexity. In particular, we show that the probability of success in the fixed budget setting as well as the sample complexity in the fixed confidence setting strictly depend on the inverse of the gaps of the arms and the desired accuracy . Extensions. Finally, in Appendix B, we discuss how the proposed algorithm and analysis can be extended to improved definitions of confidence interval (e.g., Bernstein-based bounds) and to more complex settings, such as the multi-bandit best arm identification problem introduced in [START_REF] Gabillon | Multi-bandit best arm identification[END_REF].

Problem Formulation

In this section, we introduce the notation used throughout the paper. Let A = {1, . . . , K} be the set of arms such that each arm k ∈ A is characterized by a distribution ν k bounded in For each arm k ∈ A, we define the gap ∆ k as

∆ k = µ k -µ (m+1) if k ∈ S * µ (m) -µ k if k / ∈ S * .
This definition of gap indicates that if k ∈ S * , ∆ k represents the "advantage" of arm k over the suboptimal arms, and if k / ∈ S * , ∆ k denotes how suboptimal arm k is. Note that we can also write the gap as

∆ k = | m max i =k µ i -µ k |.
Given an accuracy and a number of arms m, we say that an arm k is ( ,m)-optimal if µ k ≥ µ (m) -. Thus, we define the ( ,m)-best arm identification problem as the problem of finding a set S of m ( ,m)-optimal arms. The ( ,m)-best arm identification problem can be formalized as a game between a stochastic bandit environment and a forecaster. The distributions {ν k } are unknown to the forecaster. At each round t, the forecaster pulls an arm I(t) ∈ A and observes an independent sample drawn from the distribution ν I(t) . The forecaster estimates the expected value of each arm by computing the average of the samples observed over time. Let T k (t) be the number of times that arm k has been pulled by the end of round t, then the mean of this arm is estimated as

µ k (t) = 1 T k (t) T k (t)
s=1 X k (s), where X k (s) is the s-th sample observed from ν k . For any arm k ∈ A, we define the notion of arm simple regret as

r k = µ (m) -µ k , (1)
and for any set S ⊂ A of m arms, we define the simple regret as

r S = max k∈S r k = µ (m) -min k∈S µ k . (2)
We denote by Ω(t) ⊂ A the set of m arms returned by the forecaster at the end of the exploration phase (when the alg. stops after t rounds), and by r Ω(t) its corresponding simple regret. Returning m ( ,m)-optimal arms is then equivalent to having r Ω(t) smaller than . Given an accuracy and a number of arms m to return, we now formalize the two settings of fixed budget and fixed confidence.

Fixed budget. The objective is to design a forecaster capable of returning a set of m ( ,m)-optimal arms with the largest possible confidence using a fixed budget of n rounds. More formally, given a budget n, the performance of the forecaster is measured by the probability δ of not meeting the ( ,m) requirement, i.e., δ = P r Ω(n) ≥ , the smaller δ, the better the algorithm.

Fixed confidence. The goal is to design a forecaster that stops as soon as possible and returns a set of m ( ,m)-optimal arms with a fixed confidence. We denote by n the time when the algorithm stops and by Ω( n) its set of returned arms. Given a confidence level δ, the forecaster has to guarantee that P r Ω( n) ≥ ≤ δ. The performance of the forecaster is then measured by the number of rounds n either in expectation or high probability.

Although these settings have been considered as two distinct problems, in Section 3 we introduce a unified arm selection strategy that can be used in both cases by simply changing the stopping criteria. Moreover, we show in Section 4 that the bounds on the performance of the algorithm in the two settings share the same notion of complexity and can be derived using very similar arguments.

Unified Gap-based Exploration Algorithm

In this section, we describe the unified gap-based exploration (UGapE) meta-algorithm and show how it is implemented in the fixed-budget and fixed-confidence settings. As shown in Figure 1, both fixed-budget (UGapEb) and fixed-confidence (UGapEc) instances of UGapE use the same armselection strategy, SELECT-ARM (described in Figure 2), and upon stopping, return the m-best arms in the same manner (using Ω). The two algorithms only differ in their stopping criteria. More precisely, both algorithms receive as input the definition of the problem ( , m), a constraint (the budget n in UGapEb and the confidence level δ in UGapEc), and a parameter (a or c). While UGapEb runs for n rounds and then returns the set of arms Ω(n), UGapEc runs until it achieves the desired accuracy with the requested confidence level δ. This difference is due to the two different objectives targeted by the algorithms; while UGapEc aims at optimizing its budget for a given confidence level, UGapEb's goal is to optimize the quality of its recommendation for a fixed budget.

UGapEb ( , m, n, a) Parameters: accuracy , number of arms m, budget n, exploration parameter a Initialize: Pull each arm k once, update µ k (K) and set

T k (K) = 1 SAMP for t = K + 1, . . . , n do SELECT-ARM (t) end for SAMP Return Ω(n) = arg min J(t) B J(t) (t) UGapEc ( , m, δ, c)
Parameters: accuracy , number of arms m, confidence level δ, exploration parameter c Initialize: Pull each arm k once, update

µ k (K), set T k (K) = 1 and t ← K + 1 SAMP while B J(t) (t) ≥ do SELECT-ARM (t) t ← t + 1 end while SAMP Return Ω(t) = J(t)

SELECT-ARM

(t) Compute B k (t) for each arm k ∈ A Identify the set of m arms J(t) ∈ arg 1..m min k∈A B k (t)
Pull the arm Regardless of the final objective, how to select an arm at each round (arm-selection strategy) is the key component of any multi-arm bandit algorithm. One of the most important features of UGapE is having a unique arm-selection strategy for the fixed-budget and fixed-confidence settings. We now describe the UGapE's armselection strategy, whose pseudo-code has been reported in Figure 2. At each time step t, UGapE first uses the observations up to time t-1 and computes an index

I(t) = arg max k∈{l t ,u t } β k (t -1) Observe X I(t) T I(t) (t -1) + 1 ∼ ν I(t) Update µ I(t) (t) and T I(t) (t)
B k (t) = m max i =k U i (t) - L k (t) for each arm k ∈ A, where ∀t, ∀k ∈ A U k (t) = µ k (t -1) + β k (t -1) , L k (t) = µ k (t -1) -β k (t -1). (3)
In Eq. 3, β k (t -1) is a confidence interval, 3 and U k (t) and L k (t) are high probability upper and lower bounds on the mean of arm k, µ k , after t -1 rounds. Note that the parameters a and c are used in the definition of the confidence interval β k , whose shape strictly depends on the concentration bound used by the algorithm. For example, we can derive β k from the Chernoff-Hoeffding bound as UGapEb:

β k (t -1) = b a T k (t -1) , UGapEc: β k (t -1) = b c log 4K(t-1) 3 δ T k (t -1) . (4)
In Sec. 4, we discuss how the parameters a and c can be tuned and we show that while a should be tuned as a function of n and in UGapEb, c = 1/2 is always a good choice for UGapEc. Defining the confidence interval in a general form β k (t -1) allows us to easily extend the algorithm by taking into account different (higher) moments of the arms (see Appendix B for the case of variance, where β k (t -1) is obtained from the Bernstein inequality). From Eq. 3, we may see that the index B k (t) is an upper-bound on the simple regret r k of the kth arm (see Eq. 1). We also define an index for a set S as B S (t) = max i∈S B i (t). Similar to the arm index, B S is also defined in order to upper-bound the simple regret r S with high probability (see Lemma 1).

After computing the arm indices, UGapE finds a set of m arms J(t) with minimum upper-bound on their simple regrets, i.e., J(t) = arg

1..m min k∈A B k (t).
From J(t), it computes two arm indices u t = arg max j / ∈J(t) U j (t) and l t = arg min i∈J(t) L i (t), where in both cases the tie is broken in favor of the arm with the largest uncertainty β(t -1). Arms l t and u t are the worst possible arm among those in J(t) and the best possible arm left outside J(t), respectively, and together they represent how bad the choice of J(t) could be. Intuitively, UGapE pulls the most uncertain between u t or l t allows Finally, the algorithm selects and pulls the arm I(t) as the arm with the larger β(t -1) among u t and l t , observes a sample X I(t) T I(t) (t -1) + 1 from the distribution ν I(t) , and updates the empirical mean µ I(t) (t) and the number of pulls T I(t) (t) of the selected arm I(t).

There are two more points that need to be discussed about the UGapE algorithm. 1) While UGapEc defines the set of returned arms as Ω(t) = J(t), UGapEb returns the set of arms J(t) with the smallest index, i.e., Ω(n) = arg min J(t) B J(t) (t), t ∈ {1, . . . , n}. 2) UGapEc stops (we refer to the number of rounds before stopping as n) when B J( n+1) ( n + 1) is less than the given accuracy , i.e., when even the mth worst upper-bound on the arm simple regret among all the arms in the selected set J( n + 1) is smaller than . This guarantees that the simple regret (see Eq. 2) of the set returned by the algorithm, Ω( n) = J( n + 1), to be smaller than with probability larger than 1 -δ.

Theoretical Analysis

In this section, we provide high probability upper-bounds on the performance of the two instances of the UGapE algorithm, UGapEb and UGapEc, introduced in Section 3. An important feature of UGapE is that since its fixed-budget and fixed-confidence versions share the same arm-selection strategy, a large part of their theoretical analysis can be unified. We first report this unified part of the proof in Section 4.1, and then provide the final performance bound for each of the algorithms, UGapEb and UGapEc, separately, in Sections 4.2 and 4.3, respectively.

Before moving to the main results, we define additional notation used in the analysis. We first define event E as

E = ∀k ∈ A, ∀t ∈ {1, . . . , T }, µ k (t) -µ k < β k (t) , (5)
where the values of T and β k are defined for each specific setting separately. Note that event E plays an important role in the sequel, since it allows us to first derive a series of results which are directly implied by the event E and to postpone the study of the stochastic nature of the problem (i.e., the probability of E) in the two specific settings. In particular, when E holds, we have that for any arm k ∈ A and at any time t, L k (t) ≤ µ k ≤ U k (t). Finally, we define the complexity of the problem as

H = K i=1 b 2 max( ∆i+ 2 , ) 2 . ( 6
)
Note that although the complexity has an explicit dependence on , it also depends on the number of arms m through the definition of the gaps ∆ i , thus making it a complexity measure of the ( , m) best arm identification problem. In Section 4.4, we will discuss why the complexity of the two instances of the problem is measured by this quantity.

Analysis of the Arm-Selection Strategy

Here we report lower (Lemma 1) and upper (Lemma 2) bounds for indices B S on the event E, which show their connection with the regret and gaps. The technical lemmas used in the proofs (Lemmas 3 and 4 and Corollary 1) are reported in Appendix A. We first prove that for any set S = S * and any time t ∈ {1, . . . , T }, the index B S (t) is actually an upper-bound on the simple regret of this set r S . Lemma 1. On event E, for any set S = S * and any time t ∈ {1, . . . , T }, we have B S (t) ≥ r S .

Proof. On event E, for any arm i / ∈ S * and each time t ∈ {1, . . . , T }, we may write

B i (t) = m max j =i U j (t) -L i (t) = m max j =i µ j (t -1) + β j (t -1) -µ i (t -1) -β i (t -1) ≥ m max j =i µ j -µ i = µ (m) -µ i = r i . (7)
Using Eq. 7, we have

B S (t) = max i∈S B i (t) ≥ max i∈(S-S * ) B i (t) ≥ max i∈(S-S * ) r i = r S ,
where the last passage follows from the fact that r i ≤ 0 for any i ∈ S * .

Lemma 2. On event E, if arm k ∈ {l t , u t } is pulled at time t ∈ {1, . . . , T }, we have

B J(t) (t) ≤ min 0, -∆ k + 2β k (t -1) + 2β k (t -1). (8)
Proof. We first prove the statement for B(t) = U ut (t) -L lt (t), i.e.,

B(t) ≤ min 0, -∆ k + 2β k (t -1) + 2β k (t -1). (9)
We consider the following cases: Case 1. k = u t : Case 1.1. u t ∈ S * : Since by definition u t / ∈ J(t), there exists an arm j / ∈ S * such that j ∈ J(t). Now we may write

µ (m+1) ≥ µ j (a) ≥ L j (t) (b) ≥ L lt (t) (c) ≥ L ut (t) = µ k (t -1) -β k (t -1) (d) ≥ µ k -2β k (t -1) (10)
(a) and (d) hold because of event E, (b) follows from the fact that j ∈ J(t) and from the definition of l t , and (c) is the result of Lemma 4. From Eq. 10, we may deduce that -∆ k + 2β k (t -1) ≥ 0, which together with Corollary 1 gives us the desired result (Eq. 9). Case 1.2. u t / ∈ S * : Case 1.2.1. l t ∈ S * : In this case, we may write

B(t) = U ut (t) -L lt (t) (a) ≤ µ ut + 2β ut (t -1) -µ lt + 2β lt (t -1) (b) ≤ µ ut + 2β ut (t -1) -µ (m) + 2β lt (t -1) (c) ≤ -∆ ut + 4β ut (t -1) (11)
(a) holds because of event E, (b) is from the fact that l t ∈ S * , and (c) is because u t is pulled, and thus, β ut (t -1) ≥ β lt (t -1). The final result follows from Eq. 11 and Corollary 1.

Case 1.2.2. l t / ∈ S * : Since l t / ∈ S * and the fact that by definition l t ∈ J(t), there exists an arm j ∈ S * such that j / ∈ J(t). Now we may write

µ ut + 2β ut (t -1) (a) ≥ U ut (t) (b) ≥ U j (t) (c) ≥ µ j (d) ≥ µ (m) (12)
(a) and (c) hold because of event E, (b) is from the definition of u t and the fact that j / ∈ J(t), and (d) holds because j ∈ S * . From Eq. 12, we may deduce that -∆ ut + 2β ut (t -1) ≥ 0, which together with Corollary 1 gives us the final result (Eq. 9).

With similar arguments and cases, we prove the result of Eq. 9 for k = l t . The final statement of the lemma (Eq. 8) follows directly from B J(t) (t) ≥ B(t) as shown in Lemma 3.

Using Lemmas 1 and 2, we define an upper and a lower bounds on B J(t) in terms of quantities related to the regret of J(t). Lemma 1 confirms the intuition that the B-values upper-bound the regret of the corresponding set of arms (with high probability). Unfortunately, this is not enough to claim that selecting J(t) as the set of arms with smallest B-values actually correspond to arms with small regret, since B J(t) could be an arbitrary loose bound on the regret. Lemma 2 provides this complementary guarantee specifically for the set J(t), in the form of an upper-bound on B J(t) w.r.t. the gap of k ∈ {u t , l t }. This implies that as the algorithm runs, the choice of J(t) becomes more and more accurate since B J(t) is constrained between r J(t) and a quantity (Eq. 8) that gets smaller and smaller, thus implying that selecting the arms with the smaller B-value, i.e., the set J(t), corresponds to those which actually have the smallest regret, i.e., the arms in S * . This argument will be implicitly at the basis of the proofs of the two following theorems.

Regret Bound for the Fixed-Budget Setting

Here we prove an upper-bound on the simple-regret of UGapEb. Since the setting considered by the algorithm is fixed-budget, we may set T = n. From the definition of the confidence interval β i (t) in Eq. 4 and a union bound, we have that P(E) ≥ 1 -2Kn exp(-2a). 4 We now have all the tools needed to prove the performance of UGapEb for the m ( ,m)-best arm identification problem.

Theorem 1. If we run UGapEb with parameter 0 < a ≤ n-K 4H , its simple regret r Ω(n) satisfies

δ = P r Ω(n) ≥ ≤ 2Kn exp(-2a),
and in particular this probability is minimized for a = n-K 4H .

Proof. The proof is by contradiction. We assume that r Ω(n) > on event E and consider the following two steps:

Step 1: Here we show that on event E, we have the following upper-bound on the number of pulls of any arm i ∈ A:

T i (n) < 4ab 2 max ∆i+ 2 , 2 + 1. ( 13
)
Let t i be the last time that arm i is pulled. If arm i has been pulled only during the initialization phase, T i (n) = 1 and Eq. 13 trivially holds. If i has been selected by SELECT-ARM, then we have

min -∆ i + 2β i (t i -1), 0 + 2β i (t i -1) (a) ≥ B(t i ) (b) ≥ B J(ti) (t i ) (c) ≥ B Ω(n) (t ) (d) > , (14)
where t ∈ {1, . . . , n} is the time such that Ω(n) = J(t ). (a) and (b) are the results of Lemmas 2 and 3, (c) is by the definition of Ω(n), and (d) holds because using Lemma 1, we know that if the algorithm suffers a simple regret r Ω(n) > (as assumed at the beginning of the proof), then ∀t = 1, . . . , n + 1, B Ω(n) (t) > . By the definition of t i , we know T i (n) = T i (t i -1) + 1. Using this fact, the definition of β i (t i -1), and Eq. 14, it is straightforward to show that Eq. 13 holds.

Step 2: We know that K i=1 T i (n) = n. Using Eq. 13, we have

K i=1 4ab 2 max ∆ i + 2 , 2 + K > n
on event E. It is easy to see that by selecting a ≤ n-K 4H , the left-hand-side of this inequality will be smaller than or equal to n, which is a contradiction. Thus, we conclude that r Ω(n) ≤ on event E. The final result follows from the probability of event E defined at the beginning of this section.

Regret Bound for the Fixed-Confidence Setting

Here we prove an upper-bound on the simple-regret of UGapEc. Since the setting considered by the algorithm is fixed-confidence, we may set T = +∞. From the definition of the confidence interval β i (t) in Eq. 4 and a union bound on T k (t) ∈ {0, . . . , t}, t = 1, . . . , ∞, we have that P(E) ≥ 1 -δ.

Theorem 2. The UGapEc algorithm stops after n rounds and returns a set of m arms, Ω( n), that satisfies

P r Ω( n+1) ≤ ∧ n ≤ N ≥ 1 -δ,
where N = K + O(H log H δ ) and c has been set to 1/2.

Proof. We first prove the bound on the simple regret of UGapEc. Using Lemma 1, we have that on event E, the simple regret of UGapEc upon stopping satisfies B J( n+1) ( n + 1) = B Ω( n+1) ( n + 1) ≥ r Ω( n+1) . As a result, on event E, the regret of UGapEc cannot be bigger than , because then it contradicts the stopping condition of the algorithm, i.e., B J( n+1) ( n + 1) < . Therefore, we have P r Ω( n+1) ≤ ≥ 1 -δ. Now we prove the bound for the sample complexity. Similar to the proof of Theorem 1, we consider the following two steps:

Step 1: Here we show that on event E, we have the following upper-bound on the number of pulls of any arm i ∈ A:

T i ( n) ≤ 2b 2 log(4K( n -1) 3 /δ) max ∆i+ 2 , 2 + 1. ( 15
)
Let t i be the last time that arm i is pulled. If arm i has been pulled only during the initialization phase, T i ( n) = 1 and Eq. 15 trivially holds. If i has been selected by SELECT-ARM, then we have B J(ti) (t i ) ≥ . Now using Lemma 2, we may write

B J(ti) (t i ) ≤ min 0, -∆ i + 2β i (t i -1) + 2β i (t i -1). ( 16
)
We can prove Eq. 15 by plugging in the value of β i (t i -1) from Eq. 4 and solving Eq. 16 for T i (t i ) taking into account that T i (t i -1) + 1 = T i (t i ).

Step 2: We know that

K i=1 T i ( n) = n.
Using Eq. 15, on event E, we have 2H log K( n -1) 3 /δ + K ≥ n. Solving this inequality gives us n ≤ N .

Problem Complexity

Theorems 1 and 2 indicate that both the probability of success and sample complexity of UGapE are directly related to the complexity H defined by Eq. 6. This implies that H captures the intrinsic difficulty of the ( ,m)-best arm(s) identification problem independently from the specific setting considered. Furthermore, note that this definition generalizes existing notions of complexity. For example, for = 0 and m = 1 we recover the complexity used in the definition of UCB-E [START_REF] Audibert | Best arm identification in multi-armed bandits[END_REF] for the fixed budget setting and the one defined in [START_REF] Even-Dar | Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems[END_REF] for the fixed accuracy problem. Let us analyze H in the general case of > 0. We define the complexity of a single arm i ∈ A, H ,i = b 2 / max( ∆i+ 2 , ) 2 . When the gap ∆ i is smaller than the desired accuracy , i.e., ∆ i ≤ , then the complexity reduces to H ,i = 1/ 2 . In fact, the algorithm can stop as soon as the desired accuracy is achieved, which means that there is no need to exactly discriminate between arm i and the best arm. On the other hand, when ∆ i > , then the complexity becomes H ,i = 4b 2 /(∆ i + ) 2 . This shows that when the desired accuracy is smaller than the gap, the complexity of the problem is smaller than the case of = 0, for which we have H 0,i = 4b 2 /∆ 2 i . More in general, the analysis reported in the paper suggests that the performance of a confidencebound-based algorithm such as UGapE is characterized by the same notion of complexity in both settings. Thus, whenever the complexity is known, it is possible to exploit the theoretical analysis (bounds on the performance) to easily switch from one setting to the other. For instance, as suggested in section 5.4 of [START_REF] Kalyanakrishnan | Learning Methods for Sequential Decision Making with Imperfect Representations[END_REF], if the complexity H is known, an algorithm as UGapEc can be adapted to run in the fixed budget setting by inverting the bound on its sample complexity (equation xxx). This would lead to an algorithm very similar to UGapEb with similar performance, although the parameter tuning could be more difficult because of the intrinsic poor accuracy in the constants in the bound. On the other hand, it is an open question whether it is possible to find an "equivalence" between algorithms for the two different settings when the complexity is not known. In particular, it would be important to derive a distribution-dependent lower bound in the form of the one reported in [START_REF] Audibert | Best arm identification in multi-armed bandits[END_REF] for the general case of ≥ 0 and m ≥ 1 for both the fixed budget and fixed confidence settings.

Summary and Discussion

We proposed a meta-algorithm, called unified gap-based exploration (UGapE), that unifies the two settings of the best arm(s) identification problem in stochastic multi-armed bandit: fixed budget and fixed confidence. UGapE can be instantiated as two algorithms with a common structure (the same arm-selection and arm-return strategies) corresponding to these two settings, whose performance can be analyzed in a unified way, i.e., a large portion of their theoretical analysis can be unified in a series of lemmas. We proved a performance bound for the UGapE algorithm in the two settings. We also showed how UGapE and its theoretical analysis can be extended to take into account the variance of the arms and to multiple bandits. Finally, we evaluated the performance of UGapE and compare it with a number of existing fixed budget and fixed confidence algorithms. This unification is important for both theoretical and algorithmic reasons. Despite their similarities, fixed budget and fixed confidence settings have been treated differently in the literature. We believe that this unification provides a better understanding of the intrinsic difficulties of the best arm(s) identification problem. In particular, our analysis showed that the same complexity term characterizes the hardness of both settings. As mentioned in the introduction, there was no algorithm available for several settings considered in this paper, e.g., ( ,m)-best arm identification with fixed budget. With UGapE, we introduced an algorithm that can be easily adapted to all these settings.

A Technical Lemmas

In this section, we report three results (Lemmas 3 and 4 and Corollary 1) that have been used in the proof of Lemmas 1 and 2. Let us first redefine B(t) for each time t ∈ {1, . . . , T } as

B(t) = U ut (t) -L lt (t) = max j / ∈J(t) U j (t) -min i∈J(t) L i (t). ( 17
)
Lemma 3. For each t ∈ {1, . . . , T }, we have B J(t) (t) ≤ B(t).

Proof. For t ∈ {1, . . . , T }, we may write U j (t). Using these results, we may write

B J(t) (t) = max i∈J(t) m max j =i U j (t) -L i (t) ≤ max i∈J(t) m max j =i U j (t) -min i∈J(t) L i (t) (a) ≤ max j / ∈J(t) U j (t) -min i∈J(t) L i (t) = U ut (t) -L lt (t) = B(t). (
B ut (t) = m max j =ut U j (t) -L ut (t) < m max j =lt U j (t) -L lt (t) = B lt (t).
Since u t / ∈ J(t) and l t ∈ J(t) and J(t) collects all the arms with the smallest B i values, we have B ut (t) ≥ B lt (t) by definition. This contradicts the previous statement, and thus, Eq. 18 holds. Case 2.2. l t is pulled: With a similar reasoning to Case 2.1. and by contradiction, we can show that Eq. 19 holds in this case. Proof. The proof is a direct application of Lemma 4. We know that the pulled arm k is either u t or l t . If k = u t , we have

B(t) = U ut (t) -L lt (t) (a) ≤ U ut (t) -L ut (t) = 2β ut (t -1) = 2β k (t -1),
where (a) is from Eq. 18 in Lemma 4. Similarly if k = l t , we have

B(t) = U ut (t) -L lt (t) (b) ≤ U lt (t) -L lt (t) = 2β lt (t -1) = 2β k (t -1),
where (b) is from Eq. 19 in Lemma 4.

B Extensions

In this section, we propose three variants of the UGapE algorithm with the objective of extending its applicability and improving its performance.

UGapE-Variance (UGapE-V). As discussed in Section 3, UGapE pulls arms according to their B index, which is a high probability upper-bound on their simple regret. This gives us the flexibility of using any high probability bound in the definition of index in UGapE and to extend the algorithm. As discussed earlier, the algorithm and analysis (for both settings) are also modular enough to allow such extension. One natural extension is to replace the Chernoff-Hoeffding bounds of Eq. 4 with the following Bernstein bounds in order to take into account the variances of the arms:

UGapEb-V: β k (t) = 2a σ 2 k (t) T k (t) + (7/3)ab T k (t) -1 , UGapEc-V: β k (t) = 2c log Kt 3 δ σ 2 k (t) T k (t) + (7/3)bc log Kt 3 δ T k (t) -1 , where σ 2 k (t) = 1 T k (t)-1 T k (t) s=1 X k (s) -µ k (t)
2 is the estimated variance of arm k at the end of round t. We call the resulting algorithm UGapE-variance (UGapE-V). Using Theorem 11 in [START_REF] Maurer | Empirical bernstein bounds and sample-variance penalization[END_REF], it is easy to show that Theorems 1 and 2, bounding the simple regret of the fixed budget and fixed confidence settings, still hold (without major change in their proofs) with a new definition of complexity, i.e.,

H σ = K i=1 σ i + (13/3)b∆ i 2 max ∆i+ 2 , 2 . (20)
This variance-complexity H σ is expected to better capture the complexity of the arms and to be smaller than H defined by Eq. 6 whenever the variances of the arms are small compared to the range b of the distribution.

As mentioned in the introduction, Mnih et al. [START_REF] Mnih | Empirical Bernstein stopping[END_REF] proposed Bernstein Race, a best arm identification algorithm based on the Bernstein inequality for the fixed confidence setting. The term bounding the number of pulls of a sub-optimal arm i in their analysis is of the form (σ 2 (1) + σ 2 i )/∆ 2 i , where σ 2

(1) is the variance of the best arm. This causes Bernstein Race to allocate the pulls equally over the arms, when the task is to discriminate between two arms (K = 2), while intuitively the arms should be pulled proportionally to their variances. UGapE-V on the other hand is able to handle this case properly (i.e., to pull the arms proportionally to their variances), because its bound on the number of pulls of a sub-optimal arm i is of the form σ 2 i /∆ 2 i (see the definition of H σ in Eq. 20). In Appendix C.1, we report numerical results showing that UGapE-V has better performance than Bernstein Race when variance of the optimal arm is larger than those of the sub-optimal arms. Gabillon et al. [START_REF] Gabillon | Multi-bandit best arm identification[END_REF] proposed a similar variance extension in the fixed budget multi-bandit setting studied in their paper, with the price of a separate and tedious proof. The UGapE extension to multiple bandits (see the next paragraph), for the case = 0, recovers the same variance complexity as in [START_REF] Gabillon | Multi-bandit best arm identification[END_REF] not only with improved numerical constants, but also without a separate proof.

Multi-bandit setting. In this setting the forecaster faces M distinct best arm identification problems. The goal is to return the set of (m p , )-optimal arms from the set of available arms A p for each bandit p ∈ {1, . . . , M }. As discussed in the introduction, this settings has been studied in the fixed budget setting for the case of m p = 1, p = 1, . . . , M [START_REF] Gabillon | Multi-bandit best arm identification[END_REF][START_REF] Deng | Active learning for developing personalized treatment[END_REF] and for arbitrary values of m p [START_REF] Bubeck | Multiple identifications in multi-armed bandits[END_REF]. In this section, we briefly outline how our UGapE algorithm can be extended to the multi-bandit multi-armed problem for both fixed budget and fixed confidence settings.

For UGapE to be applied to the multi-bandit problem we first need to define the index B pk (t) over all bandits p and arms k at time t. For each bandit p and arm k, we define the simple regret as r pk = µ p(mp) -µ pk . Similar to the single bandit case, B pk (t) is defined as an upper-bound on the simple regret of the kth arm of bandit p, i.e., B pk (t) = mp max i =k U pi (t) -L pk (t).

At each time t, SELECT-ARM first finds for each bandit p a set of m p arms J p (t) with minimum upper-bound on their simple regrets, i.e., J p (t) = arg 1..mp min k∈Ap B pk (t), and calculates B Jp(t) (t) = 1..mp min k∈Ap B pk (t), where B Jp(t) (t) is the upper bound on the simple regret of the set of arms J p (t). It then selects the bandit with maximal upper bound on its simple regret to explore. Finally, it selects the arm to be pulled in the exact same manner as in the single bandit case (see Figure 2). The analysis of the resulting algorithm is quite similar, up to some new notations, to the one for single bandit. Theorems 1 and 2 will be stated similarly, only with new definition of complexity: , where H (p) and H σ (p) are the complexities of the single bandit problem p, without and with variance, defined by Eqs. 6 and 20. Note that the above complexities resemble those in [START_REF] Gabillon | Multi-bandit best arm identification[END_REF] in the sense that the complexity of the multi-bandit problem is the sum of the single bandit's complexities.

H = M p=1 H (p) = M p=1 K i=1 b 2 max(
Finally it is important to note that our approach can be easily modified to tackle the problem of finding the set of (m p , p )-optimal arms in each bandit p, where the difference w.r.t. the previous version is that now depends on p. For this modification, it is sufficient to select the bandit with maximal value of the quantity B Jp(t) (t)p at time t. This quantity is the difference between the upper-bound on the simple regret of bandit p and its maximum accepted simple regret.

Adaptive UGapEb and UGapEb-V. A drawback of UGapE and UGapE-V in the fixed budget setting is that the exploration parameter a should be tuned according to the complexities H and H σ of the problem, which are rarely known in advance. A straightforward solution to this problem is to move to an adaptive version of the algorithms by substituting H and H σ with suitable estimates, often lower bounds on the true complexities. Such adaptive procedure has been implemented for UCB-E, GapE, and GapE-V algorithms [START_REF] Audibert | Best arm identification in multi-armed bandits[END_REF][START_REF] Gabillon | Multi-bandit best arm identification[END_REF]. Similar implementations can be used here.

2 µ

 2 [0, b] with mean µ k and variance σ 2 k . We define the m-max and m-argmax operators as where (m) denotes the index of the m-th best arm in A and µ (m) is its corresponding mean so that µ (1) ≥ µ (2) ≥ . . . ≥ µ (K) . We denote by S m ⊂ A any subset of m arms (i.e., |S m | = m < K) and by S m, * the subset of the m best arms (i.e., k ∈ S m, * iif µ k ≥ µ (m) ). Without loss of generality, we assume there exists a unique set S m, * . In the following we drop the superscript m and use S = S m and S * = S m, * whenever m is clear from the context. With a slight abuse of notation we further extend the m-max operator to an operator returning a set of arms, such that {µ (1) , . . . , µ (m)

Figure 1 :

 1 Figure 1: The pseudo-code for the UGapE algorithm in the fixed-budget (UGapEb) (left) and fixedconfidence (UGapEc) (right) settings.

Figure 2 :

 2 Figure 2: The pseudo-code for the UGapE's armselection strategy. This routine is used in both UGapEb and UGapEc instances of UGapE.

Corollary 1 .

 1 If arm k is pulled at time t ∈ {1, . . . , T }, then we have B(t) ≤ 2β k (t -1).

Figure 5 :

 5 Figure 5: Comparison between UCB-E, UCBE-V, GapE, GapE-V, UGapE, and UGapE-V algorithms in Problem 3.

Figure 6 :

 6 Figure 6: Comparison between UCB-E, UCBE-V, GapE, GapE-V, UGapEb, and UGapEb-V algorithms in Problem 4.

  a) Let set Z = max i∈J(t) to be the set of m arms with the largest U (t). If J(t) = S(t) then Z = U (m+1) (t) = max j / ∈J(t) U j (t), and ifJ(t) = S(t) then Z = U (m) (t) ≤ max j / ∈J(t) U j (t).Proof. We consider the following two cases:Case 1. µ ut (t -1) ≤ µ lt (t -1): If we pull u t , by definition we have β ut (t -1) ≥ β lt (t -1), and thus, Eq. 18 holds. A similar reasoning gives Eq. 19 when l t is pulled. Case 2. µ ut (t -1) > µ lt (t -1): We consider the following two sub-cases: Case 2.1. u t is pulled: We prove this case by contradiction. Let us assume that L ut (t) > L lt (t). Since arm u t is pulled, by definition we have β ut (t -1) ≥ β lt (t -1), and thus, U ut (t) > U lt (t).

	m max j =i U i (t) Lemma 4. At each time t ∈ {1, . . . , T }, we have that U j (t) and define S(t) = arg 1..m max i∈A
	if u t is pulled,	L ut (t) ≤ L lt (t)	(18)
	if l t is pulled,	U ut (t) ≤ U lt (t).	(19)
	From this, it is easy to see that	m max j =lt	U j (t) ≥

m max j =ut

Note that when = 0 and m = 1 this reduces to the standard best arm identification problem.

Ties are broken in an arbitrary but consistent manner.

To be more precise, β k (t -1) is the width of a confidence interval or a confidence radius.

The extension to a confidence interval that takes into account the variance of the arms is discussed in Appendix B.

C Experimental Results

In this section, we compare UGapE and UGapE-V to the state-of-the-art algorithms in the fixed budget and fixed confidence settings. The objective is to verify that designing a meta-algorithm for the two settings does not come at the cost of a worse performance. • Problem 1. We have K = 5 arms with (0, 1), (0.4, 0.5), (0.4, 0.5), (0.4, 0.5), (0.4, 0.5) . • Problem 2. We have K = 5 arms with (0, 1), (0, 0.8), (0, 0.8), (0, 0.6), (0, 0.6) . We compare UGapEc-V with Bernstein race and Hoeffding race algoerithms. All the algorithms have an exploration parameter c. Although, the theoretical analysis suggests c = 1/2, we tuned c empirically. For each algorithm and each confidence parameter δ, we compute the average sample complexity over 1000 runs for different values of c ∈ {1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01, 0.005}. For each algorithm, we only consider the results corresponding to the value of c for which the required confidence level δ is satisfied (i.e., the values of c for which the algorithm satisfies P[r Ω( n) > = 0] ≤ δ, for all the values of δ considered). Finally in Figure 4, for each algorithm, we report the results for the value of c with the smallest sample complexity.

Sampling complexity w.r.t. confidence

In the left panel of Figure 4, we report the results for Problem 1 with m = 1 and = 0. In this problem, the optimal arm has significantly higher variance than the other arms. This problem has been designed to highlight the difference between the three algorithms and to illustrate the advantage of UGapEc-V over the Racing algorithms, as discussed in Appendix B. Since the suboptimal arms have the same mean and variance, the analysis of Bernstein Race and Hoeffding Race suggests that all the arms (including the best arm) should be pulled the same number of times. However, since the Bernstein Race takes into account the variance, it has a tighter bound and the stopping condition is met earlier than for Hoeffding Race. For instance for δ = 0.1, Bernstein Race has an expected sample complexity of 1181 pulls while the Hoeffding Race stops after 1342 pulls on average. On the other hand, as expected from the theoretical analysis (see Appendix B), UGapEc-V stops after only 719 pulls. Note that UGapEc-V, on average, distributes the number of pulls as (72%,7%,7%,7%,7%) over the arms. This indicates that the algorithm successfully adapts to the variance of the arms. The parameter c for which the algorithms have a minimal sample complexity are c = 0.02 for Bernstein Race and UGapEc-V and c = 0.05 for Hoeffding Race.

Finally, in the right panel of Figure 4 we consider Problem 2. Although this problem has not been specifically designed to illustrate the advantage of UGapEc over the Racing algorithms, UGapEc-V still outperforms the Racing algorithms.

C.2 Fixed Budget Setting

In this section, we compare UGapEb with the state-of-the-art fixed budget algorithms: UCBE, UCBE-V, GapE, and GapE-V. Since all these algorithms share a very similar structure, we expect them to have similar performance. All the algorithms have an exploration parameter a. The theoretical analysis suggests that a should be proportional to n H . Although a could be optimized according to the bound, since the constants in the analysis are not accurate, we will run the algorithms with a = η n H , where η is a parameter which is empirically tuned (in the experiments we use four different values of η). The results are averaged over 1000 runs and the error bars correspond to three times the estimated standard deviation.

Experimental setting. We use the following two problems in our experiments.

• Problem 1. n = 2000, K = 20. The arms have Bernoulli distribution, the best arm has a mean of 1/2 and the sub-optimal arms have a mean of 0.4. • Problem 2. n = 4000, K = 15. The arms have Rademacher distribution with parameters µ i = 0.5 -0.025(i -1), i ∈ {1, . . . , 15}.

Note that b = 1 in these problems. In Figures 5 and6, we report the performance, calculated as the probability to identify the best arm after n rounds, of UCBE, UCBE-V, GapE, GapE-V, UGapEb, and UGapEb-V algorithms. The results indicate that the best performance of each algorithm is achieved for similar values of the parameter η. As expected, all the algorithms achieve similar performance, no one has clear advantage over the others. Investigating the allocation over the budget n over arms, we also notice that for all the algorithms the number of pulls is inversely proportional to the gaps.