Epsilon Best Arm Identification in Spectral Bandits

1 Introduction

A bandit model (see [Lattimore and Szepesv´ari, 2019] and references therein) is a set of probability distributions ν = {νa : a ∈ A}. These distributions are called arms, and the statistician can sample one of them at each time step t ≥ 1. Best-arm identification (BAI) consists of using those samples so as to find which arm has the highest expectation µa = E(νa), while ε-BAI aims at identifying an arm a such that µa ≥ maxb µb - ε. A fixed-confidence algorithm for a given risk δ At choosing thanks to past observations which arm is sampled at each time step t, and of a stopping rule τ (a stopping time): it is called δcorrect if Aτ+1 is ε-optimal with probability at least 1 - δ. The efficiency of this algorithm is measured by the mean

number Eν[τ ] of samples needed.

Since the work of [Mannor and Tsitsiklis, 2004] and [EvenDar et al., 2006], best-arm identification has received considerable interest. It has been proved that good strategies require no more than A(ν)+B(ν) log(1/δ) samples, for some functions A and B of the model that were progressively improved. While, for example, [Karnin et al., 2013] investigated more on term A, other authors insisted on the fact that B is the dominant term when δ is small and focused on the best possible term B. For BAI (with ε = 0), the latter was identified by [Garivier and Kaufmann, 2016] and [Russo, 2016]. The first of those articles provided a generic analysis that reduces BAI to the identification of an information-theoretic complexity term that gives at the same time a lower bound on the performance of any algorithm, and a key ingredient of an asymptotically optimal strategy called Track-and-Stop. This term appears to be the solution of a min-max optimization program, for which an ad-hoc solution was given in the aforementioned article.

While these first works were limited to the δ-correct identification of the best arm (which was assumed to exist and be unique), [Garivier and Kaufmann, 2019] proposed an extension to the problem of identifying ε-optimal arms. Simultaneously, [Degenne and Koolen, 2019] leveraged the gametheoretic nature of the complexity term to encompass even more general objectives.

In parallel with this progress, vanilla bandit models have shown limitations in settings (such as recommendation systems) where the number of arms is huge. It is then not uncommon that the set of arms is naturally endowed with some structure. One simple way to take this structure into account is to assume the existence of some notion of similarity: some arms are "close" from one another, in the sense that their outcomes are expected to have similar distributions. Graph bandits are meant to provide a theoretical framework for this setting: the set of arms is provided with a graph structure where the weight wa,b of the link from arm a to arm b measures their similarity. The set of means µ = (µa : 1 ≤ a ≤ K) is assumed to be smooth with respect to this graph in the sense that

where L denotes the graph's Laplacian and R is some known upper-bound. This means that two arms connected by an edge with significant weight should have similar expectations.

Recently, [Koc´ak and Garivier, 2020] showed how to optimally, δ-correctly identify the best arm in a graph bandit model if it exists. But the consideration of very large sets of arms, and the fact that many of them might be close to optimal, suggest that it is often more relevant to identify (more quickly) any ε-optimal arm instead of the unique best.

In the present work, we address the problem of PAC identification of an ε-best arm in graph bandit models, hence encompassing all the aforementioned difficulties. We focus on finite bandit models with K arms: A = {1, . . . , K}. In order to avoid technicalities, we consider Gaussian arms νa = N(µa, 1) and identify the bandit problem with vector µ = (µ1, . . . , µK) of arm expectations.

Following the approach of [Garivier and Kaufmann, 2016], we start in Section 2 by identifying the complexity of the problem as the optimal ratio Eν[τ]/ log(1/δ) of any (ε, δ)- PAC algorithm when δ → 0. This complexity term appears to be the solution of an interesting max-min progam. Taking great benefit from its game-theoretic structure, we propose a solution that is radically different from [Garivier and Kaufmann, 2019] even in the case where R = ∞, a case that we treat separately in Section 3. The structured case R < ∞, which is the main contribution of this paper, is treated in Section 4.

2 The Complexity of ε-BAI for Graph Bandits

2.1 Characteristic Time

Several factors are contributing to the complexity of identifying one of the ε-best arms in bandit problems. The difficulty is related to the quantity T ∗R, ε (µ) called characteristic time.

Definition 1. Characteristic time T ∗R, ε (µ) is defined as

where ∆K is the K-dimensional simplex, A∗ε (µ) is the set of all ε-best arms of bandit problem µ

and Mi, j R, ε is a set of bandit problems with smoothness at most R and with arm j being better than arm i by at least ε marginMi, j R, ε ≜ {λ ∈ RK : λTLλ ≤ R, λi ≤ λj - ε}. (3)

λTLλ ≤ R is often called a spectral constraint, hence the name spectral bandits.

Remark. This definition is backward compatible with previous papers. By setting R to infinity, every problem satisfies the spectral constraint and we obtain the setting of [Garivier and Kaufmann, 2019]. By setting ε to zero, we are identifying only the best arm which leads to the setting of [Koc´ak and Garivier, 2020]. By setting R to infinity and ε to zero at the same time we obtain the original setting of [Garivier and Kaufmann, 2016].

The starting point for this paper is stated in the following proposition. This proposition can be obtained along the lines of a recent paper by [Garivier and Kaufmann, 2019]. It shows the connection between the expected stopping time of any δcorrect algorithm that identifies ε-best arms and the characteristic time defined previously.

Proposition 1. For any δ-correct strategy and any bandit problem µ, the expectation of stopping time τδ of the strategy is lower bounded as

where the characteristic time T ∗R, ε (µ) is defined in Eq. (2).

The most significant part of this proposition is that it provides a lower bound that scales with the characteristic time. The proof is assuming that the learner plays according to strategy ω from the definition of T ∗R, ε (µ), i.e. playing arm a with probability ωa, while the environment chooses some bandit problem λ for the learner. By choosing the best possible strategy ω for the learner while the environment chooses the hardest possible bandit problem λ we obtain the lower bound from the proposition.

However, this works also the other way around. If the learner plays according to the optimal strategy ω∗ , the strategy that maximizes expression in the definition of T ∗R, ε (µ), the expected stopping time of the learner is also proportional to the characteristic time and therefore matching the lower bound (possibly up to some multiplicative constant). Therefore, the main focus of this paper is on analyzing the characteristic time and finding a way to compute optimal weight ω∗ for the learner and provide an algorithm that utilizes these weights.

2.2 Game-Theoretical Point of View

As we hinted in the previous section, computing the inverse of characteristic time, T ∗R, ε (µ)-1 , can be seen as a game between the learner and the environment where:

• The first player (learner) chooses one of the ε-best arms i ∈ A∗ε (µ) and ω ∈ ∆K while trying to maximize the value of the optimization problem.
• The second player (environment) chooses alternative arm j ̸= i and bandit problem λ ∈ Mi, j R, ε while trying to minimize the value of the optimization problem.

In fact, the optimization function in the definition of T ∗R, ε (µ)-1 is very simple; linear in ω and quadratic in λ. To make it more apparent, we use the following definition and rewrite the optimization problem in a slightly different way.

Definition 2. Let Mi, j R, ε be the set of the problems with smoothness at most R and arm j being better than arm i by at least ε (expression (3)). Define the set of elementwise divergences from µ to Mi, j R, ε as

This definition enables us to rewrite T ∗R, ε (µ)-1 in a more compact way as

Thanks to this reparametrization we obtained an optimization problem that is linear with independent ω and d. We use this form later to simplify the presentation of some ideas and proofs. We approach this optimization problem in two steps:

1. Given i and ω of the first player (learner), we compute the best response d (resp. λ) of the second player
2. Having the best response, we can find optimal ω∗ (either directly or numerically, depending on the problem)

In any case, it is important to be able to compute the best response of the second player. When finding the best response, usually it is helpful to split the optimization problem into several smaller problems and solve them separately. We do it by considering only a subproblem with fixed i.

Definition 3. By fixing i in T ∗R, ε (µ)-1 we can define

This definition enables us to compute T ∗R, ε (µ)-1 as

3 BAI ProblemWithout Structure

In this section, we focus on the setting without structure. This setting was previously studied by [Garivier and Kaufmann, 2019] and can be obtained simply by setting the smoothness parameter R to ∞ which would make any bandit problem satisfy the smoothness constraint (Expression (1)). The main contribution of this section is to significantly simplify the proofs of [Garivier and Kaufmann, 2019] by using a previously mentioned game-theoretical approach while providing the necessary ideas and reasoning later used in the more difficult spectral case. As mentioned earlier, this game-theoretic approach was initiated in [Degenne and Koolen, 2019].

Finding values of individual T i∞, ε (µ)-1 is reminiscent of the problems solved by [Garivier and Kaufmann, 2016] and [Koc´ak and Garivier, 2020]. However, this time we assume that i is not necessarily the optimal arm but it is at most ε away from the optimal arm. The following theorem shows the main result of the unconstrained case and a convenient way of computing optimal weights ω∗ (µ).

Theorem 2. Assume that i is one of the ε optimal arms of bandit problem µ, i.e. µi > µj - ε for every j ∈ [K]. Let I be any arm different from i and define sequence {xa(c)}a∈[K]/{i} as

for any j ∈ [K]/{i, I}, constant c, and δi, j ε = (µi -µj +ε). Let f(c) be a function with parameter c defined as

Then there exist c∗ ∈ R+ such that f(c∗ ) = 1 and we obtain optimal ω∗ (µ) as

The rest of this section is dedicated to building necessary tools for the proof of Theorem 2 later in Section 3.2.

3.1 Best Response Oracle - SettingWithout Constraint

The following lemma shows us the form of the best response of Player 2 in T i∞, ε (µ)-1 game.

Lemma 3. Let ω be a vector from ∆K and µ a bandit problem. Then the best response λi, j ∞, ε (ω) ∈ Mi, j ∞, ε to ω, with arm j being better than arm i by at least ε, is in form

λi, j ∞, ε (ω) = (µ1, . . . , µi-1, t, . . . , t + ε, µj+1, . . . , µK)T for .

Proof. Assuming that j-th position of λi, j ∞, ε (ω) is exactly ε larger than i-th position of λi, j ∞, ε (ω), for some ε ≥ ε. Using simple calculus we obtain that

while the element on the j-th position has value

The first part of both expressions is a weighted average of µi and µj which is always in interval [µj, µi] and therefore, by increasing ε we increase our objective function. This makes ε = ε the optimal choice.

Corollary 1. Let ω be a vector from ∆K and µ a bandit problem. Then the best response di, j ∞, ε (ω) ∈ Di, j ∞, ε to ω, with arm j being better than arm i by at least ε, is zero everywhere except for the i-th and j-th position

for

Proof. The proof is obtained by combining Lemma 3 with the definition of Di, j ∞, ε .

3.2 Proof of Theorem 2

Now that we know the exact form of the best response provided by the oracle, we are ready to prove the statement of Theorem 2 for the non-spectral setting.

Using Corollary 1 problem T i∞, ε (µ)-1 transforms into

where Player 2 now chooses only j ̸= i. The following lemma shows that Player 2 can play a mixed strategy (a convex combination of pure strategies where the player plays only one arm j) while not changing the value of the game.

Lemma 4. Let ω be a vector in RK and D be a compact subset of RK then

where Conv(D) is the convex hull of D.

Proof. Since D is a compact set, there exist vector d∗ such that

We also know that d∗ is a vector from the convex hull of D therefore, d∗ can be expressed as a convex combination ∑j∈[K] qjdj for q = (q1, . . . , qK) ∈ ∆K of at most K points dj ∈ D. Therefore, we have

The inequality in the previous expression holds since d∗ is the minimizer of the expression from the lemma statement. However, the first term in the previous expression is the same as the last term and therefore the inequality should achieve equality. This can occur only if ωTdj = ωTd∗ for every j where qj ̸= 0. Since at least one qj is strictly positive, corresponding dj is one of the minimizers of the minimization problem over D.

As we mentioned, Lemma 4 allows Player 2 to play a mixed strategy while the value of the game stays the same. The main benefit of this change is that the game now has a Nash equilibrium. In order to be in the equilibrium, any change to the strategy of the first player should result in same value of the game as long as the second player plays the optimal mixed strategy. This also means that in the mixed strategy of the second player, all the elements of played vector should be the same. Therefore, there has to be a convex combination with coefficients {qj ≥ 0}j∈[K]/{i} such that

for some constant r. Since for any j ̸= i only di, j ∞, ε (ω) is not 0 at position j, value of qj can not be 0 and

Now we have everything necessary to find the convex combination for a given ω as well as the way to find optimal ω∗ for the first player.

3.3 FindingWeights qj and Optimal ω∗

Instead of finding the convex combination we can look for a linear combination that gives us 1 and then renormalize it to obtain a convex combination. Since di, j ∞, ε (ω) is the only member contributing to the j-th element, we can divide it by di, j ∞, ε (ω)j to obtain 1 at the j-th position. Therefore, qj is proportional to di, j ∞, ε (ω)-1 j . Now we have a vector of ones except for the i-th element for which we do not have any guarantees. In order to be in Nash equilibrium, i-th element should be 1 as well. That means that

From Lemma 4 and the fact that both di, j ∞, ε (ω) and di, k ∞, ε (ω) contribute to the optimal mixed strategy, they need to be equally good when the first player chooses optimal ω∗ . Therefore, we have

ω∗ i di, j ∞, ε (ω∗ )i + ω∗ j di, j ∞, ε (ω∗ )j = ω∗ i di, k ∞, ε (ω∗ )i + ω∗ k di, k

which, after a few steps, leads to

.

This provides us a way to express xj (c∗ ) using xk(c∗ ) for any combination of arms j and k. In particular, setting k = I we recover Theorem 2

4 BAI Problemwith Structure

The main complexity of spectral setting comes from the fact that the best response for the second player of game T iR, ε (µ)-1 does not have a closed form and therefore, it is impossible to compute ω∗ directly as in the case without structure. We solve this problem in several steps:

• Computing best response to ω numerically.
• Restating T iR, ε (µ)-1 as a function of ω.
• Computing a supergradient for this function.
• Applying a gradient algorithm to compute optimal ω∗ .

4.1 Best Response Oracle - Spectral Setting

The oracle needs to find λi, j R, ε (ω) that minimizes

In the case where the oracle for the setting without structure returns λi, j ∞, ε (ω) that satisfies spectral constraint (λi, j ∞, ε (ω)TLλi, j ∞, ε (ω) ≤ R), we are done and the spectral oracle should return value λi, j R, ε (ω) = λi, j ∞, ε (ω). On the other hand, we can restrict our search for the problems λi, j R, ε (ω) with smoothness exactly R, thanks to the following lemma.

Lemma 5. Let λi, j ∞, ε (ω) be the response of non-spectral oracle such that λi, j ∞, ε (ω)TLλi, j ∞, ε (ω) > R then the response of spectral oracle λi, j R, ε (ω) satisfies λi, j R, ε (ω)TLλi, j R, ε (ω) = R.

Proof idea. Suppose that the smoothness of λi, j R, ε (ω) is smaller than R, i.e. λi, j R, ε (ω)TLλi, j R, ε (ω) < R. Define λ as a convex combination of non-spectral and spectral oracle responses with parameter α ∈ (0, 1).

For small enough α, we can show that λ improves the optimization problem while still satisfying the spectral constraint.

Knowing that the smoothness of the oracle response is exactly R, we use the Lagrange multiplier method to solve the problem

where λi = λj - ε and γ is the Lagrange multiplier. Before solving this problem we need to eliminate coupling between i-th and j-th elements of λ and introduce some notation to simplify some of the expressions in the next lemma. Lets fix indices i and j for the moment and define:

Any tilde index ˜a is equal to a if a < j or a - 1 if a > j. This means that by removing element on the j-position of some vector, we can refer to the original element on the a-th position using ˜a.

• ˜ω is a vector such that

• ˜Ω is a diagonal matrix with ˜ω on diagonal.
• ˜λ is a vector such that

• ˜µ is a vector such that

• ˜ L is a matrix created from L by adding j-th row and column to i-th row and column and updating diagonal entries to have a zero sum on every row and column and then removing t-th row and column from the matrix.

• ˜ Lj is a vector created from the j-th column of L by setting i-th element to 0, updating j-th element to have zero sum of elements, and removing i-th element.

Lemma 6. Let i and j are fixed and ˜ Lj be the j-th column of ˜ L. Then we define ˜λ(γ) as

There exists γ ∗ such that λ(γ ∗ )TLλ(γ ∗ ) = R and λ(γ ∗ ) is the best response vector that corresponds to ˜λ(γ ∗ ) such that element on the j-th position is larger than the element on the i-th position by exactly ε.

Proof idea. The statement of the lemma can be obtain taking partial derivatives of F(λ, γ) and solving the resulting system of equations.

4.2 Supergradient as the Best Response

Now that we have a way to compute the best response to Player 1, we are ready to restate T iR, ε (µ)-1 as a function of ω and provide a lemma that shows the form of a supergradient for this function. Define f i (ω) as

Note that T iR, ε (µ)-1 = sup ω∈∆K f i (ω) . The following lemma

gives us a convenient way to compute a supergradient of f i at ω. In fact, the best response di, j (ω), computed by the best response oracle from Section 4.1, is a supergradient of f i thanks to the following lemma.

Lemma 7. Let D ⊆ RK be a compact set. Then function f : ∆K → R defined as f(ω) = infd∈D ωTd is a concave function and d∗ (ω) = arg mind∈D ωTd is a supergradient of f at ω.

Proof. Let d∗ (ω) ∈ D be a vector that realizes the infimum from the definition of f(ω). Such a vector is well defined since D is compact. First, we prove that d∗ (ω) is a supergradient of f at any point ω since the existence of supergradient implies the concavity of the function.

Let ω1 and ω2 be any two points from the domain of f. From the definition of d∗ (ω) we have

Which, using the definition of f, can be further rewritten as

Thus, d∗ (ω1) is a supergradient of f at ω1 and function f is concave.

Now that we have a supergradient for function f i (ω), we are ready to apply a gradient-based algorithm to find the optimal ω∗ and therefore, the value of T iR, ε (µ)-1 . The algorithm of our choice is the mirror ascent algorithm that provides strong guarantees.

Theorem 8. Let ω1 = ( 1K , . . . , 1K )T and learning rate η = 1L √ 2 log K t . Then mirror ascent algorithm optimizing L-Lipschitz function f, with respect to ‖ · ‖1 , defined on ∆K with generalized negative entropy Φ as the mirror map enjoys the following guarantees

Proof. This result can be adapted from [Bubeck, 2015].

Now, the last step is using the geometry of the problem and the form of the best response oracle to show that f i (ω) is Lipschitz for some constant L. This is captured in the following lemma.

Lemma 9. Let f i : ∆K →R be a function such that

Then function f i is L-Lipschitz with respect to ‖ · ‖1 for any

5 Algorithm

Solving the complexity problem (3) permits to rely on the SpectralTaS (Algorithm 1) by [Koc´ak and Garivier, 2020] which is a variation of the asymptotically optimal Track-and-Stop algorithm introduced in [Garivier and Kaufmann, 2016]. Essentially, this algorithm tracks optimal sampling distribution ω∗ with respect to the current estimate of unknown bandit problem µ and playing accordingly. By playing an arm, the estimate of µ gets progressively better over time which, in consequence, leads to a more precise sampling distribution ω∗ .

The last two ingredients for the algorithm are sampling and stopping rules. We recall them for self-containment, and refer to [Garivier and Kaufmann, 2016; Koc´ak and Garivier, 2020] for more details.

5.1 Sampling Rule

In order to capture and correct possible arm underestimation, the algorithm introduces extra small amount of exploration. For every γ ∈ (0, 1/K], let ω∗,γ (µ) be an L∞ projection of ω∗ (µ) onto ∆γK defined as {(ω1, . . . , ωK) ∈ [γ, 1]K : ω1 + · · · + ωK = 1}. Then the sampling rule is

where γs of order of 1/√s which provides as much exploration as possible while not influencing the bounds significantly.

5.2 Stopping Rule

The algorithm should stop as soon as it has gathered sufficient evidence on the superiority of one of the arms with probability 1 - δ: for two arms i ∈ A∗ε ( ˆµ) and j ∈ [K], denote by

the generalized likelihood ratio statistics for the test µi > µj . Then the stopping rule is given by

where β(·, ·) is a threshold function to be chosen typically slightly larger than log(1/δ). Theorem 10 in [Garivier and Kaufmann, 2016] shows that the choice β(t, δ) = log(2t(K - 1)/δ) and Aτ+1 = argmaxa∈[K] ˆµa(τ) yields a probability of failure Pν (Aτ+1 /∈ a∗ (µ)) ≤ δ.

.

Algorithm 1 SpectralTaS

• 1: Input and initialization:
• 2: L : graph Laplacian
• 3: ε, δ : tolerance and confidence parameters
• 4: R : upper bound on the smoothness of µ
• 5: Play each arm a once and observe rewards ra
• 6: ˆµ1 = (r1, . . . , rK)T : empirical estimate of µ
• 7: while Stopping Rule (9) not satisfied do
• 8: Compute ω∗ (ˆµt) by mirror ascent
• 9: Choose At according to Sampling Rule (8)
• 10: Obtain reward rt of armAt
• 11: Update ˆµt according to rt
• 12: end while
• 13: Output armA∗ = argmaxa∈[K] ˆµa

6 Experiments

For the experiments, we used bandit problem

with K = 11 arms, a graph that connects all the neighboring actions a and a + 1 for every a ∈ [K - 1], ε = 0.05, and different values of R. The following plot demonstrates the effect of smoothness parameter R on both theoretical and empirical stopping times. The green curve represents the average stopping time of 10 runs of SpectralTaS while the red curve represents the characteristic time.

7 Conclusion and Open Problems

We identified the characteristic time of fixed-confidence εbest arm identification in bandit models with graph smoothness. It appears as a delicate min-max optimization problem, but thanks to a game-theoretic analysis of this complexity we could provide an efficient algorithm for its computation, leading to an asymptotically optimal algorithm. While this provides a complete treatment of the fixed-confidence-setting, the dual fixed-budget setting is still not understood. How good is a strategy following the estimated optimal weights, but stopping at a given time n and not at a chosen stopping time? Are some improvements using the budget n possible? These natural questions are open for further investigations.

Acknowledgements

Aur´elien Garivier (ANR chaire SeqALO) and Tom´aˇs Koc´ak acknowledge the support of the Project IDEXLYON of the University of Lyon, in the framework of the Programme Investissements d'Avenir (ANR-16-IDEX-0005).