Rémy Degenne

Pierre Ménard

Xuedong Shang

Michal Valko

Gamification of pure exploration for linear bandits

come   L'archive ouverte pluridisciplinaire

Introduction

Multi-armed bandits (MAB) probe fundamental explorationexploitation trade-offs in sequential decision learning. We study the pure exploration framework, from among different MAB models, which is subject to the maximization of information gain after an exploration phase. We are particularly interested in the case where noisy linear payoffs depending on some regression parameter θ are assumed. Inspired by Degenne et al. (2019), we treat the problem as a two-player zero-sum game between the agent and the nature (in a sense described in Section 2), and we search for algorithms that are able to output a correct answer with Proceedings of the 37 th International Conference on Machine Learning, Vienna, Austria, PMLR 119, 2020. Copyright 2020 by the author(s).

high confidence to a given query using as few samples as possible.

Since the early work of [START_REF] Robbins | Some aspects of the sequential design of experiments[END_REF], a great amount of literature explores MAB in their standard stochastic setting with its numerous extensions and variants. [START_REF] Even-Dar | PAC bounds for Multi-armed Bandit and Markov Decision Processes[END_REF] and [START_REF] Bubeck | Pure exploration in multi-armed bandits problems[END_REF] are among the first to study the pure exploration setting for stochastic bandits. A nonexhaustive list of pure exploration game includes best-arm identification (BAI), top-m identification [START_REF] Kalyanakrishnan | Efficient selection of multiple bandit arms: Theory and practice[END_REF], threshold bandits [START_REF] Locatelli | An optimal algorithm for the thresholding bandit problem[END_REF], minimum threshold [START_REF] Kaufmann | Sequential test for the lowest mean: From Thompson to Murphy sampling[END_REF], signed bandits [START_REF] Ménard | Gradient ascent for active exploration in bandit problems[END_REF], pure exploration combinatorial bandits [START_REF] Chen | Combinatorial pure exploration of multi-armed bandits[END_REF], Monte-Carlo tree search (Teraoka et al., 2014), etc. In this work, we consider a general pure-exploration setting (see Appendix D for details). Nevertheless, for the sake of simplicity, in the main text we primarily focus on BAI. For stochastic bandits, BAI has been studied within two major theoretical frameworks. The first one, fixed-budget BAI, aims at minimizing the probability of misidentifying the optimal arm within a given number of pulls [START_REF] Audibert | Best arm identification in multi-armed bandits[END_REF]. In this work, we consider another setting, fixed-confidence BAI, introduced by [START_REF] Even-Dar | Action elimination and stopping conditions for reinforcement learning[END_REF]. Its goal is to ensure that the algorithm returns a wrong arm with probability less than a given risk level, while using a small total number of samples before making the decision. Existing fixedconfidence algorithms are either elimination-based such as SuccessiveElimination [START_REF] Karnin | Almost optimal exploration in multi-armed bandits[END_REF], rely on confidence intervals such as UGapE [START_REF] Gabillon | Best arm identification: A unified approach to fixed budget and fixed confidence[END_REF], or follow plug-in estimates of the optimal pulling proportions by a lower bound such as Track-and-Stop [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF]. We pay particular attention to the first two since they have been extended to the linear setting, which is the focus of this paper. In particular, a natural extension of pure exploration to linear bandits. Linear bandits were first investigated by [START_REF] Auer | Using confidence bounds for exploitationexploration trade-offs[END_REF] in the stochastic setting for regret minimization and later considered for fixedconfidence BAI problems by [START_REF] Soare | Best-arm identification in linear bandits[END_REF].

Linear bandits. We consider a finite-arm linear bandit problem, where the collection of arms A ⊂ R d is given with |A| = A, and spans R d . We assume that ∀a ∈ A, a ≤ L, where a denotes the Euclidean norm of the vector a. The learning protocol goes as follows: for each round 1 ≤ t ≤ T, the agent chooses an arm a t ∈ A and observes a noisy sample Y t = θ, a t + η t , where η t ∼ N (0, σ 2 ) is conditionally independent from the past and θ is some unknown regression parameter. For the sake of simplicity, we use σ 2 = 1 in the rest of this paper.

Pure exploration for linear bandits. We assume that θ belongs to some set M ⊂ R d known to the agent. For each parameter a unique correct answer is given by the function i : M → I among the I = |I| possible ones (the extension of pure exploration to multiple correct answers is studied by Degenne & Koolen 2019). Given a parameter θ, the agent then aims to find the correct answer i (θ) by interacting with the finite-armed linear bandit environment parameterized by θ.

In particular, we detail the setting of BAI for which the objective is to identify the arm with the largest mean.

That is, the correct answer is given by i (θ) = a (θ) := argmax a∈A θ, a for θ ∈ M = R d and the set of possible correct answers is I = A. We provide other pureexploration examples in Appendix D.

Algorithm. Let F t = σ(a 1 , Y 1 , . . . , a t , Y t ) be the information available to the agent after t round. A deterministic pure-exploration algorithm under the fixed-confidence setting is given by three components: (1) a sampling rule (a t ) t≥1 , where a t ∈ A is F t-1 -measurable, (2) a stopping rule τ δ , a stopping time for the filtration (F t ) t≥1 , and

(3) a decision rule î ∈ I which is F τ δ -measurable. Nondeterministic algorithms could also be considered by allowing the rules to depend on additional internal randomization.

The algorithms we present are deterministic.

δ-correctness and fixed-confidence objective. An algorithm is δ-correct if it predicts the correct answer with probability at least 1 -δ, precisely if P θ î = i (θ) ≤ δ and τ δ < +∞ almost surely for all θ ∈ M. Our goal is to find a δ-correct algorithm that minimizes the sample complexity, that is, E θ [τ δ ] the expected number of sample needed to predict an answer.

Pure exploration (in particular BAI) for linear bandits has been previously studied by [START_REF] Soare | Best-arm identification in linear bandits[END_REF]; [START_REF] Tao | Best arm identification in linear bandits with linear dimension dependency[END_REF]; [START_REF] Xu | A fully adaptive algorithm for pure exploration in linear bandits[END_REF]; [START_REF] Zaki | Towards optimal and efficient best arm identification in linear bandits[END_REF]; [START_REF] Fiez | Sequential experimental design for transductive linear bandits[END_REF]; [START_REF] Kazerouni | Best arm identification in generalized linear bandits[END_REF]. They all consider the fixedconfidence setting. To the best of our knowledge, only [START_REF] Hoffman | On correlation and budget constraints in model-based bandit optimization with application to automatic machine learning[END_REF] study the problem with a fixed-budget.

Beside studying fixed-confidence sample complexity, [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF] and some subsequent works [START_REF] Qin | Improving the expected improvement algorithm[END_REF][START_REF] Shang | Fixed-confidence guarantees for Bayesian bestarm identification[END_REF] investigate a general criterion of judging the optimality of a BAI sampling rule: Algo-rithms that achieve the minimal sample complexity when δ tends to zero are called asymptotically optimal. [START_REF] Ménard | Gradient ascent for active exploration in bandit problems[END_REF] and Degenne et al. (2019) further study the problem in a game theoretical point of view, and extend the asymptotic optimality to the general pure exploration for structured bandits. Note that a naive adaptation of the algorithm proposed by Degenne et al. (2019) may not work smoothly in our setting. In this paper we use some different confidence intervals that benefit better from the linear structure.

Contributions. 1)

We provide new insights on the complexity of linear pure exploration bandits. In particular, we relate the asymptotic complexity of the BAI problem and other measures of complexity inspired by optimal design theory, which were used in prior work. 2) We develop a saddle-point approach to the lower bound optimization problem, which also guides the design of our algorithms. In particular we highlight a new insight on a convex formulation of that problem. It leads to an algorithm with a more direct analysis than previous lower-bound inspired methods. 3) We obtain two algorithms for linear pure exploration bandits in the fixed-confidence regime. Their sample complexity is asymptotically optimal and their empirical performance is competitive with the best existing algorithms.

Asymptotic Optimality

In this section we extend the lower bound of [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF], to hold for pure exploration in finitearmed linear bandit problems.

Alternative

. For any answer i ∈ I we define the alternative to i, denoted by ¬i the set of parameters where the answer i is not correct, i.e. ¬i := {θ ∈ M : i = i (θ)} .

We also define, for any w ∈ (R + ) A , the design matrix

V w := a∈A w a aa .
Further, we define x V := √ x V x for x ∈ R d and a symmetric positive matrix V ∈ R d×d . Note that it is a norm only if V is positive definite. We also denote by Σ K the probability simplex of dimension K -1 for all K ≥ 2.

Lower bound. We have the following non-asymptotic lower bound, proved in Appendix C, on the sample complexity of any δ-correct algorithm. This bound was already proved by [START_REF] Soare | Best-arm identification in linear bandits[END_REF] for the BAI example.

Theorem 1. For all δ-correct algorithms, for all θ ∈ M,

lim inf δ→0 E θ [τ δ ] log(1/δ) ≥ T (θ) ,
where the characteristic time T (θ) is defined by

T (θ) -1 := max w∈Σ A inf λ∈¬i (θ) 1 2 θ -λ 2 Vw .
In particular, we say that a δ-correct algorithm is asymptotically optimal if for all θ ∈ M,

lim sup δ→0 E θ [τ δ ] log(1/δ) ≤ T (θ) .
As noted in the seminal work of [START_REF] Chernoff | Sequential design of experiments[END_REF], the complexity T (θ) -1 is the value of a fictitious zero-sum game between the agent choosing an optimal proportion of allocation of pulls w and a second player, the nature, that tries to fool the agent by choosing the most confusing alternative λ leading to an incorrect answer.

Minimax theorems. Using Sion's minimax theorem we can invert the order of the players if we allow nature to play mixed strategies

T (θ) -1 = max w∈Σ A inf λ∈¬i (θ) 1 2 θ -λ 2 Vw (1) = inf q∈P(¬i (θ)) max a∈A 1 2 E λ∼q θ -λ 2 aa ,
where P(X ) denotes the set of probability distributions over the set X . The annoying part in this formulation of the characteristic time is that the set ¬i (θ) where the nature plays is a priori unknown (as the parameter is unknown to the agent). Indeed, to find an asymptotically optimal algorithm one should somehow solve this minimax game. But it is easy to remove this dependency noting that inf λ∈¬i θ -λ = 0 for all i = i (θ),

T (θ) -1 = max i∈I max w∈Σ A inf λ∈¬i 1 2 θ -λ 2 Vw .
Now we can see the characteristic time T (θ) -1 as the value of an other game where the agent plays a proportion of allocation of pulls w and an answer i. The agent could also use mixed strategies for the answer which leads to

T (θ) -1 = max ρ∈Σ I max w∈Σ A 1 2 i∈I inf λ i ∈¬i ρ i θ -λ i 2 Vw = max ρ∈Σ I max w∈Σ A inf λ∈ i (¬i) 1 2 i∈I ρ i θ -λ i 2 Vw ,
where i∈I (¬i) denotes the Cartesian product of the alternative sets ¬i. But the function that appears in the value of the new game is not anymore convex in (w, ρ) and Sion's minimax theorem does not apply anymore. We can however convexify the problem by letting the agent to play a distribution w ∈ Σ AI over the arm-answer pairs (a, i), see Lemma 1 below proved in Appendix C.

Lemma 1. For all θ ∈ M,

T (θ) -1 = max w∈Σ AI inf λ∈ i (¬i) 1 2 (a,i)∈A×I w a,i θ -λ i 2 aa = inf q∈ i P(¬i) 1 2 max (a,i)∈A×B E λ i ∼ q i θ -λ i 2 aa .
Thus in this formulation the characteristic time is the value of a fictitious zero-sum game where the agent plays a distribution w ∈ Σ AI over the arm-answer pairs (a, i) ∈ A × I and nature chooses an alternative λ i ∈ ¬i for all the answers i ∈ I. The algorithm LinGame-C that we propose in Section 3 is based on this formulation of the characteristic time whereas algorithm LinGame is based on the formulation of Theorem 1.

Best-arm identification complexity. The inverse of the characteristic time of Theorem 1 specializes to

T (θ) -1 = max w∈Σ A min a =a (θ) θ, a (θ) -a 2 2 a (θ) -a 2 V -1 w
for BAI (see Appendix D.1 for a proof). It is also possible to explicit the characteristic time

T (θ) = min w∈Σ A max a =a (θ) 2 a (θ) -a 2 V -1 w θ, a (θ) -a 2 .
Since the characteristic time involves many problem dependent quantities that are unknown to the agent, previous papers target loose problem-independent upper bounds on the characteristic time. [START_REF] Soare | Best-arm identification in linear bandits[END_REF] (see also [START_REF] Tao | Best arm identification in linear bandits with linear dimension dependency[END_REF][START_REF] Fiez | Sequential experimental design for transductive linear bandits[END_REF]) introduce the G-complexity (denoted by AA) which coincides with the G-optimal design of experimental design theory (see [START_REF] Pukelsheim | Optimal Design of Experiments[END_REF]) and the AB dir -complexity 1 (denoted by AB dir ) inspired by the transductive experimental design theory [START_REF] Yu | Active learning via transductive experimental design[END_REF],

AA = min w∈Σ A max a∈A a 2 V -1 w , AB dir = min w∈Σ A max b∈Bdir b 2 V -1 w ,
where B dir := {a -a : (a, a ) ∈ A × A}. For the Goptimal complexity we seek for a proportion of pulls w that explores uniformly the means of the arms, since the statistical uncertainty for estimating θ, a scales roughly with a V -1 w . In the AB-complexity we try to estimate uniformly all the directions a -a . On the contrary in this paper we try to maximize directly the characteristic times, that is try to estimate all the directions a (θ)-a scaled by the squared gaps θ, a (θ) -a . Note that the characteristic time can also be seen as a particular optimal transductive design. Indeed for

B := (a (θ) -a)/ θ, a (θ) -a : a ∈ A/ a (θ) , it holds T (θ) = 2AB (θ) := 2 min w∈Σ A max b∈B (θ) b 2 V -1 w .
We have the following ordering on the complexities

T (θ) ≤ 2 AB dir ∆ min (θ) 2 ≤ 8 AA ∆ min (θ) 2 = 8d ∆ min (θ) 2 , ( 2
)
where ∆ min = min a =a (θ) θ, a (θ) -a and the last equality follows from the Kiefer-Wolfowitz equivalence theorem [START_REF] Kiefer | Optimum designs in regression problems[END_REF]. Conversely the AAcomplexity and the AB dir -complexity are linked to an other pure exploration problem, the thresholding bandits (see Appendix D.2).

Remark 1. In order to compute all these complexities, it is sufficient to solve the following generic optimal transductive design problem: for B a finite set of elements in R d ,

AB = min w∈Σ K max b∈B b 2 V -1 w .
When B = A we can use an algorithm inspired by Frank-Wolfe [START_REF] Frank | An algorithm for quadratic programming[END_REF]) which possesses convergence guarantees [START_REF] Atwood | Optimal and efficient designs of experiments[END_REF][START_REF] Ahipasaoglu | Linear convergence of a modified Frank-Wolfe algorithm for computing minimum-volume enclosing ellipsoids[END_REF]. But in the general case, up to our knowledge, there is no algorithm with the same kind of guarantees. Previous works used an heuristic based on a straightforward adaptation of the aforementioned algorithm for general sets B but it seems to not converge on particular instances, see Appendix I. We instead propose in the same appendix an algorithm based on Saddle point Frank-Wolfe algorithm that seems to converge on the different instances we tested.

Algorithm

We present two asymptotically optimal algorithms for the general pure-exploration problem. We also make the additional assumption that the set of parameter is bounded, that is we know M > 0 such that for all θ ∈ M, θ ≤ M . This assumption is shared by most of the works on linear bandits (e.g. [START_REF] Abbasi-Yadkori | Improved algorithms for linear stochastic bandits[END_REF][START_REF] Soare | Best-arm identification in linear bandits[END_REF].

We describe primarily LinGame-C, detailed in Algorithm 2. The principle behind LinGame, detailed in Algorithm 1, is similar and significant differences will be highlighted.

Notations

Counts. At each round t the algorithms will play an arm a t and choose (fictitiously) an answer i t . We denote by N a,i t := and when it is clear from the context we will also denote by N a t = (N a,i t ) i∈I and N i t = (N a,i t ) i∈I the vectors of partial counts.

Regularized least square estimator. We fix a regularization parameter η > 0. The regularized least square estimator for the parameter θ ∈ M at time t is

θt = (V Nt + ηI d ) -1 t s=1 Y s a s ,
where I d is the identity matrix. By convention θ0 = 0.

Algorithms

Stopping rule. Our algorithms share the same stopping rule. Following [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF], our algorithms stop if a generalized likelihood ratio exceeds a threshold. It stops if

max i∈I inf λi∈¬i 1 2 θt -λ i 2 V N t > β(t, δ) , (3)
and

return i t ∈ argmax i∈I inf λ i ∈¬i θt -λi 2 V N t /2.
This stopping and decision rules ensures that the algorithms LinGame and LinGame-C are δ-correct regardless of the sampling rule used, see lemma below 2 proved in Appendix F. Lemma 2. Regardless of the sampling rule, the stopping rule (3) with the threshold

β(t, δ) = log 1 δ + d 2 log 1 + tL 2 ηd + η 2 M 2 , (4)
2 The fact that τ δ < +∞ is a consequence of our analysis, see Appendix E.

satisfy P θ τ δ < ∞ ∧ i τ δ = i (θ) ≤ δ.
Our contribution is a sampling rule that minimizes the sample complexity when combined with these stopping and decision rules. We now explain our sampling strategy to ensure that the stopping threshold is reached as soon as possible.

Saddle point computation. Suppose in this paragraph, for simplicity, that the parameter vector θ is known. By the definition of the stopping rule and the generalized likelihood ratio, as long as the algorithm does not stop,

β(t, δ) ≥ inf λ∈¬i (θ) a∈A N a t θ -λ 2 aa /2 .
If we manage to have N t ≈ tw (θ) (the optimal pulling proportions at θ), then this leads to β(t, δ) ≥ tT (θ) -1 and, solving that equation, we have asymptotic optimality.

Since there is only one correct answer, the parameter θ belongs to all sets ¬i for i = i (θ). Hence

inf λ∈¬i (θ) 1 2 a∈A N a t θ -λ 2 aa ≥ inf λt∈ i (¬i) 1 2 (a,i)∈A×I N a,i t θ -λ i 2 aa .
Introducing the sum removes the dependence in the unknown i * (θ). LinGame-C then uses an agent playing weights w in Σ AI . LinGame does not use that sum over answers, but uses a guess for i (θ). Its analysis involves proving that the guess is wrong only finitely many times in expectation.

Our sampling rule implements the lower bound game between an agent, playing at each stage s a weight vector w s in the probability simplex Σ A×I , and nature, who computes at each stage a point λ i s ∈ ¬i for all i ∈ I. We additionally ensure that N a,i t ≈ t s=1 w a,i s . Suppose that the sampling rule is such that at stage t, a ε t -approximate saddle point is reached for the lower bound game, see Lemma 1. That is,

inf λ∈ i (¬i) t s=1 (a,i)∈A×I w i,a s θ -λ i 2 aa /2 + ε t ≥ t s=1 (a,i)∈A×I w i,a s θ -λ i s 2 aa /2 ≥ max (a,i)∈A×I t s=1 θ -λ i s 2 aa /2 -ε t .
Then if the algorithm did not stop, it verifies, using Lemma 1,

β(t, δ) ≥ t max (a,i)∈A×I 1 t t s=1 θ -λ i s 2 aa /2 -2ε t ≥ t inf q∈ i∈I P(¬i) max (a,i)∈A×I E λ i ∼q i θ-λ i 2 aa /2-2ε t = tT (θ) -1 -2ε t .
Solving that equation, we get asymptotically the wanted t T (θ) log(1/δ).

We implement the saddle point algorithm by using Ada-Hedge for the agent (a regret minimizing algorithm of the exponential weights family), and using best-response for the nature, which plays after the agent. Precisely the learner L w for LinGame-C is AdaHedge on Σ AI with the gains

g θ t ( w) = 1 2 (a,i)∈A×I w a,i θ -λ i s 2 aa .
Whereas LinGame uses I learners L i w , one for each possible guess of i (θ) with the gains. For i ∈ I, the learner L i w is also AdaHedge but only on Σ A with the gains (when the guess is i)

g θ t (w) = 1 2 a∈A w a θ -λ i s 2 aa .
ε t is then the sum of the regrets of the two players. Bestresponse has regret 0, while the regret of AdaHedge is O( √ t) for bounded gains, as seen in the following lemma, taken from de [START_REF] De Rooij | Follow the leader if you can, hedge if you must[END_REF].

Lemma 3. On the online learning problem with K arms and gains g s

(w) = k∈[K] w k U k s for s ∈ [t], AdaHedge, predicting (w s ) s∈[t] , has regret R t := max w∈Σ K t s=1 g s (w) -g s (w s ) ≤ 2σ t log(K) + 16σ(2 + log(K)/3) , where σ = max s≤t ( max k∈[K] U k s -min k∈[K] U k s ) .
Other combinations of algorithms are possible, as long as the sum of their regrets is sufficiently small. At each stage t ∈ N, both algorithms advance only by one iteration and as time progresses, the quality of the saddle point approximation improves. This is in contrast with Track-and-Stop [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF], in which an exact saddle point is computed at each stage, at a potentially much greater computational cost.

Optimism. The above saddle point argument would be correct for a known game, while our algorithm is confronted to a game depending on the unknown parameter θ. Following a long tradition of stochastic bandit algorithms, we use the principle of Optimism in Face of Uncertainty. Given an estimate θt-1 , we compute upper bounds for the gain of the agent at θ, and feed these optimistic gains to the learner. Precisely, given the best response λ i t ∈ ¬i we define,

U a,i t = max ξ min ξ -λ i t 2 aa , 4L 2 M 2 s.t. θt-1 -ξ 2 V N t-1 +ηI d ≤ 2h(t)
, where h(t) = β(t, 1/t3 ) is some exploration function. We clipped the values, using that M and A are bounded to ensure bounded gains for the learners. Under the event that the true parameter verifies θt-1 -θ 2 ≤ 2h(t), this is indeed an optimistic estimate of θ -λ i t 2 aa . Note that U a,i t has a closed form expression, see Appendix E. The optimistic gain is then, for LinGame-C (see Algorithm 1 for the one of LinGame),

g t ( w) = 1 2 (a,i)∈A×I w a,i U a,i t .
Tracking. In both Algorithm 1 and 2, the agent plays weight vectors in a simplex. Since the bandit procedure allows only to pull one arm at each stage, our algorithm needs a procedure to transcribe weights into pulls. This is what we call tracking, following [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF]. The choice of arm (or arm and answer) is

a t+1 ∈ argmin a∈A N a t -W a t+1
for Algorithm 1,

(a t+1 , i t+1 ) ∈ argmin (a,i)∈A×I N a,i t -W a,i t+1 for Algorithm 2.
This procedure guarantees that for all t ∈ N, u ∈ U, with

U = A (resp. U = I × A) for Algo. 1 (resp. Algo. 2), -log(|U|) ≤ N u t -W u t ≤ 1.
That result is due to Degenne et al. ( 2020) and its proof is reproduced in Appendix G. Theorem 2. For a regularization parameter 3 η ≥ 2(1 + log(A))AL 2 + M 2 , for the threshold β(t, δ) given by (4), for an exploration function h(t) = β(t, 1/t 3 ), LinGame and LinGame-C are δ-correct and asymptotically optimal. That is, they verify for all θ ∈ M,

lim sup δ→0 E θ [τ δ ] log 1/δ ≤ T (θ) .
The main ideas used in the proof are explained above. The full proof is in appendix E with finite δ upper bounds.

Bounded parameters

We provide a bounded version of different examples (e.g. BAI) in Appendix D where we add the assumption that the parameter set M is bounded. In particular we show how it affects the lower bound of Theorem 1: the characteristic time T (θ) is reduced (or equivalently T (θ) -1 increases). This is not surprising since we add a new constraint in the optimization problem. This means that the algorithm should stop earlier. The counterpart of this improvement is that it is often difficult to compute the best response for nature. Indeed, for example, in BAI, there is an explicit expression of the best response, see Appendix D.1. When the constraint λ ≤ M is added there is no explicit expression anymore and one needs to solve an uni-dimensional optimization problem, see Lemma 5. To devise an asymptotically optimal algorithm without the boundedness assumption remains an open problem.

Note that in the proof of Theorem 2 we only use two times the boundedness assumption, first in the definition of the threshold β(t, δ) (see Theorem 3) to handle the bias induced by the regularization. Second, since the regret of AdaHedge is proportional to the maximum of the upper confidence bounds U i,a s , we need to ensure that they are bounded.

Related Work

We survey previous work on linear BAI. The major focus is put on sampling rules in this section. We stress that all the stopping rules employed in the linear BAI literature are equivalent up to the choice of their exploration rate (More discussion given in Appendix H). As aforementioned, existing sampling rules are either based on SuccessiveElimination or UGapE. Elimination-based sampling rules usually operate in phases and progressively discard sub-optimal directions. Gap-based sampling rules always play the most informative arm that reduces the uncertainty of the gaps between the empirical best arm and the others.

X Y-Static and X Y-Adaptive. [START_REF] Soare | Best-arm identification in linear bandits[END_REF] first propose a static allocation design X Y-Static that aims at reducing the uncertainty of the gaps of all arms. More precisely, it requires to either solve the AB dir -complexity or use a greedy version that pulls the arm argmin a∈A max b∈Bdir b 2

V -1 w at the cost of having no guarantees. An elimination-like alternative called X Y-Adaptive is proposed then to overcome that issue. We say elimination-like since X Y-Adaptive does not discard arms once and for all, but reset the active arm set at each phase. X Y-Adaptive and X Y-Static are the first algorithms being linked to AA-optimality, but are not asymptotically optimal.

ALBA. ALBA is also an eliminations-based algorithm designed by [START_REF] Tao | Best arm identification in linear bandits with linear dimension dependency[END_REF] that improves over X Y-Adaptive by a factor of d in the sample complexity using a tighter elimination criterion. RAGE. [START_REF] Fiez | Sequential experimental design for transductive linear bandits[END_REF] extend X Y-Static and X Y-Adaptive to a more general transductive bandits setting. RAGE is also elimination-based and requires the computation of AB dir -complexity at each phase. LinGapE and variants. LinGapE [START_REF] Xu | A fully adaptive algorithm for pure exploration in linear bandits[END_REF] is the first gap-based sampling rule for linear BAI. LinGapE is inspired by UGapE [START_REF] Gabillon | Best arm identification: A unified approach to fixed budget and fixed confidence[END_REF]. It is, however, not clear whether LinGapE is asymptotically optimal or not. Similar to X Y-Static, LinGapE either requires to solve a time-consuming optimization problem at each step, or can use a greedy version that pulls arm argmin a∈A a it -a jt 2 (Vw+aa ) -1 instead, again at the cost of losing guarantees. Here i t = i ( θt ) and a jt is the most ambiguous arm w.r.t. a it , i.e. argmax j =it θt , a j -a ( θt ) + a ( θt ) -a jt V -1 N t 2β(t, δ). On the other hand, [START_REF] Zaki | Towards optimal and efficient best arm identification in linear bandits[END_REF] propose a new algorithm based on LUCB. With a careful examination, we note that the sampling rule of GLUCB is equivalent to that of the greedy LinGapE using the Sherman-Morrison formula. Later, [START_REF] Kazerouni | Best arm identification in generalized linear bandits[END_REF] provide a natural extension of LinGapE to the generalized linear bandits setting, where the rewards depend on a strictly increasing inverse link function. GLGapE reduces to LinGapE when the inverse link function is the identity function.

Note that all the sampling rules presented here depend on δ (except X Y-Static), while our sampling rules have a δfree property which is appealing for applications as argued by [START_REF] Jun | Anytime exploration for multiarmed bandits using confidence information[END_REF]. Also all the guarantees in the literature are of the form C log(δ) + O log(1/δ) for a constant C that is strictly larger than T (θ) -1 .

Experiments

Besides our algorithms, we implement the following algorithms, all using the same stopping rule (more discussion given in Appendix H): uniform sampling, the greedy version of X Y-Static (including AA-allocation and AB dirallocation), X Y-Adaptive, and the greedy version of LinGapE. We skip GLUCB/GLGapE since they are more or less equivalent to LinGapE in the scope of this paper.

The usual hard instance. Usual sampling rules for classical BAI may not work for the linear case. This can be understood on a well-studied instance already discussed by [START_REF] Soare | Best-arm identification in linear bandits[END_REF]; [START_REF] Xu | A fully adaptive algorithm for pure exploration in linear bandits[END_REF], which encapsulates the difficulty of BAI in a linear bandit, and thus is the first instance on which we test our algorithms. In this instance, arms are the canonical basis a 1 = e 1 , a 2 = e 2 , a d = e d , plus an additional disturbing arm a d+1 = (cos(α), sin(α), 0, . . . , 0) , and a true regression parameter θ equal to e 1 . In this problem, the best arm is always a 1 , but when the angle α is small, the disturbing arm a d+1 is hard to discriminate from a 1 . As already argued by [START_REF] Soare | Best-arm identification in linear bandits[END_REF], an efficient sampling rule for this problem instance would rather pull a 2 in order to reduce the uncertainty in the direction a 1 -a d+1 . Naive adaptation of classical BAI algorithms cannot deal with that situation naturally. We further use a simple set of experiments to justify that intuition. We run our two algorithms and the one of Degenne et al. (2019) that we call DKM over the problem instance whence d = 2, δ = 0.01 and α = 0.1. We show the number of pulls for each arm averaged over 100 replications of experiments in Table 1. We see that, indeed, DKM pulls too much a 3 , while our algorithms focus mostly on a 2 . Comparison of different complexities. We use the previous setting to illustrate various complexities differ in practice. In Table 2 we compare the different complexities mentioned in this paper: the characteristic time T (θ) and its associated optimal weights w AB (θ) , the AB dir -complexity and its associated optimal design w ABdir , the G-optimal complexity AA and its associated optimal design w AA . For each weight vector w ∈ {w AB (θ) , w ABdir , w AA }, we also provide the lower bound T w given by Therorem 1, i.e. In particular we notice that targeting the proportions of pulls w ABdir , w AA leads to a much larger lower bound than the one obtained with the optimal weights. Comparison with other algorithms. Finally we benchmark our two sampling rules against others from the literature. We test over two synthetic problem instances, with the first being the previous counter-example. We set d = 2, α = π/6. Fig. 1 shows the empirical stopping time of each algorithms averaged over 100 runs, with a confidence level δ = 0.1, 0.01, 0.0001 from left to right. Our two algorithms show competitive performance (the two leftmost boxes on each plot), and are only slightly worse than LinGapE.

T w = max a =a (θ) θ, a (θ) -a 2 2 a (θ) -a 2 V -1 w log(1/δ).
For the second instance, we consider 20 arms randomly generated from the unit sphere S d-1 := {a ∈ R d ; a 2 = 1}. We choose the two closest arms a, a and we set θ = a + 0.01(a -a) so that a is the best arm. This setting has already been considered by [START_REF] Tao | Best arm identification in linear bandits with linear dimension dependency[END_REF].

We report the same box plots over 100 replications as before with increasing dimension in Fig. 2. More precisely, we set d = 6, 8, 10, 12 respectively, and always keep a same δ = 0.01. Our algorithms consistently show strong performances compared to other algorithms apart from LinGapE. Moreover, we can see that in these random examples, LinGame-C works better than the non-confexified one, and is even competitive compared to LinGapE.

We stress that although the main focus of this paper is theoretical, with algorithms that are asymptotically optimal, our methods are also competitive with earlier algorithms experimentally.

Conclusion

In this paper, we designed the first practically usable asymptotically optimal sampling rules for the pure exploration game for finite-arm linear bandits. Should the boundedness assumption be necessary to have optimal algorithm remains an open question.

Another concern about the current sampling rules could be their computational complexity. In BAI, the one step complexity of LinGame-C (or LinGame) is dominated by the computation of the best response for nature, which requires a full matrix inversion. Alternatives that involve rank-1 updates should be considered.

More generally, however, the part of fixed-confidence pure exploration algorithms that needs an improvement the most is the stopping rule. While the one we used guarantees δcorrectness, it is very conservative. Indeed, the experimental error rates of algorithms using that stopping rule are orders of magnitude below δ. This means that the concentration inequality does not reflect the query we seek to answer. It quantifies deviations of the d-dimensional estimate in all directions (morally, along 2 d directions). However, for the usual BAI setting with d arms in an orthogonal basis, it would be sufficient to control the deviation of that estimator in d -1 directions to make sure that i * (θ) = i * ( θt ).

Finally, the good performance of LinGapE raises the natural question of whether it could be proven to have similar asymptotic optimality.

A. Outline

The appendices are organized as follows:

Notation is given in Appendix B.

We give a full proof of Theorem 1 in Appendix C.

We list and elaborate in detail several pure exploration problems in Appendix D.

Appendix E is dedicated to the proof of sample complexity for LinGame-C and LinGame.

Appendix F is dedicated to some important concentration results.

We discuss the tracking procedure in Appendix G.

We discuss the stopping rules in Appendix H.

Finally, we provide some further details about the experiments in Appendix I.

B. Notation

Table 3.

C. Proofs of the Lower Bounds and Equivalent Formulations

We start this section by proving the lower bound.

Proof of Theorem 1. Fix λ ∈ ¬i (θ) in the alternative of θ. Thanks to the contraction of the entropy and the chain rule (see [START_REF] Garivier | Explore first, exploit next: The true shape of regret in bandit problems[END_REF], we have

kl P θ (î = i ), P λ (î = i ) ≤ a∈A E θ N a (τ δ ) θ -λ i 2 aa 2 ,
where we denote by kl(p, q) the Kullback-Leibler divergence between two Bernoulli distributions Ber(p) and Ber(q)

kl(p, q) = p log p q + (1 -p) log 1 -p 1 -q .
Since the algorithm is δ-correct we know that

P λ î = i (θ) ≤ δ ≤ 1 2 ≤ 1 -δ ≤ P θ î = i (θ) .
Thanks to monotonic properties of the function kl(•, •) and the inequality kl(1 -p, p) ≥ -log(2.4p) (see [START_REF] Garivier | Explore first, exploit next: The true shape of regret in bandit problems[END_REF], it yields

kl P θ (î = i (θ)), P λ (î = i (θ)) ≥ kl(1 -δ, δ) ≥ log 1 2.4δ , thus log 1 2.4δ ≤ a∈A E θ N a (τ δ ) θ -λ i 2 aa 2 .
Using the fact that the previous inequality is true for all λ ∈ ¬i (θ) and that the vector of components E θ N a (τ δ ) /E θ τ δ belongs to the probability simplex Σ A we get

log 1 2.4δ ≤ E θ [τ δ ] inf λ∈¬i (θ) K a=1 E θ N a (τ δ ) E θ [τ δ ] θ -λ i 2 aa 2 ≤ E θ [τ δ ] sup w∈Σ K inf λ∈¬i (θ) K a=1 w a θ -λ i 2 aa 2 .
Dividing the previous inequality by log(1/δ) and taking the limit inferior when δ goes to zero allows us to conclude.

We restate and prove below Lemma 1.

Lemma 4. For all θ ∈ M,

T (θ) -1 = max i∈I max w∈Σ A inf λ∈¬i θ -λ 2 Vw 2 (5) = max w∈Σ AI inf λ∈ i (¬i) 1 2 (a,i)∈A×I w a,i θ -λ i 2 aa (6) = max w∈Σ AI inf q∈ i P(¬i) (a,i)∈A×I w a,i E λ i ∼ q i θ -λ i 2 aa (7) = inf q∈ i P(¬i) 1 2 max (a,i)∈A×B E λ i ∼ q i θ -λ i 2 aa . (8)
Proof. The transition from ( 6) to (7) comes from the fact that the second player can use indifferently mixed or pure strategy. The equality between ( 7) and ( 8) is just an application of the Sion lemma (see Degenne & Koolen 2019). It remains to prove (5) = ( 6). First note that we can replace the first maximum in (5) over i (θ) by a maximum over I because when i / ∈ i (θ)

we know that θ ∈ ¬i. Since we can express the maximum over the answers as a maximum over the probability simplex Σ I we have

max i∈I sup w∈Σ A inf λ∈¬i 1 2 a∈A w a θ -λ 2 aa = max ρ∈Σ I i∈I sup w∈Σ A inf λ∈¬i 1 2 a∈A ρ i w a θ -λ 2 aa = max ρ∈Σ I i∈I sup w i ∈Σ A inf λ i ∈¬i 1 2 a∈A ρ i w i a θ -λ i 2 aa = sup w∈Σ AI inf λ∈ i∈I ¬i 1 2 (a,i)∈A×I w i a θ -λ i 2 aa ,
where for the last line we use the fact that all w ∈ Σ AI can be written as w i a = ρ i w i a with ρ ∈ Σ I and w i ∈ Σ A for all i ∈ I.

D. Examples

We gather in this appendix several pure exploration problems for linear bandits. We first state a useful lemma.

Lemma 5. For θ, λ ∈ R d , w in the interior of the probability simplex

• Σ A , y ∈ R d , x ∈ R, we have inf λ: λ,y ≥x θ -λ 2 Vw 2 =      (x -θ, y ) 2 2 y 2 V -1 w if x ≥ θ, y 0 otherwise .
Proof. We consider the Lagrangian of the problem, and we obtain

inf λ: λ,y ≥x θ -λ 2 Vw 2 = sup α≥0 inf λ∈R d θ -λ 2 Vw 2 + α(x -λ, y ) = sup α≥0 α(x -θ, y ) -α 2 y 2 V -1 w 2 =      (x -λ, y ) 2 2 y 2 V -1 w if x ≥ θ, y 0 otherwise
, where the infimum in the first equality is reached at λ = θ + αV -1 w y and the supremum in the last equality is reached at α = (x -θ, y )/ y 2 V -1 w if x ≥ θ, y and at α = 0 else.

D.1. Best-arm identification

For BAI the goal is to identify the arm with the largest mean. Thus, the set of parameters is

M = R d /{θ ∈ R d : | argmax a∈A θ, a | > 1}
, the set of possible answers is I = A and the correct answer is given by i (θ) = a (θ) := argmax a∈A θ, a . Lemma 6. For all θ ∈ M,

T (θ) -1 = max w∈Σ A min a =a (θ) θ, a (θ) -a 2 2 a (θ) -a 2 V -1 w , and
T (θ) = min w∈Σ A max a =a (θ) 2 a (θ) -a 2 V -1 w θ, a (θ) -a 2 .
Proof. Recall that the characteristic time is given by

T (θ) -1 = max w∈∆ A inf λ∈¬a (θ) θ -λ 2 Vw 2 .
We just express the set ¬a (θ) as a union of convex sets, and then compute the infimum for each one of them. Using Lemma 5, it yields

T (θ) -1 = max w∈∆ A min a =a (θ) inf λ: λ,a > λ,a (θ) θ -λ 2 Vw 2 = max w∈∆ A min a =a (θ) θ, a (θ) -a 2 2 a (θ) -a 2 V -1 w .
The formula for T (θ) is then straightforward given the one for T (θ) -1 .

In fact the characteristic time is just a particular case of the optimal transductive design. Indeed if we set

B (θ) := 1 θ, a (θ) -a a (θ) -a : a ∈ A/ a (θ) ,
then we have T (θ) = 2AB (θ) where AB (θ) := min

w∈Σ A max b∈B b 2 V -1 w .
Best response. There is an explicit formula for the best response in BAI. Indeed if we inspect the proof of Lemma 6 we have

inf λ∈¬a (θ) θ -λ 2 Vw 2 = min a =a (θ) θ -λ a V -1 w .
where λ a is defined in Lemma 7.

Lemma 7. For θ ∈ R d , w in the interior of the probability simplex

• Σ A , we have min λ,a-a (θ) ≥0 θ -λ 2 Vw = θ, a (θ) -a 2 2 a (θ) -a 2 V -1 w ,
and λ a defined below attains the infimum of the left hand term above

λ a = θ - max ( θ, a (θ) -a , 0) a (θ) -a 2 (Vw+γI d ) -1 V -1 w (a -a) .
Proof. See proof of Lemma 5.

D.1.1. BOUNDED BAI

One straightforward extension of this setting is to consider the bounded BAI. In this case, the set of parameters is

M = {θ ∈ R d : | argmax a∈A θ, a | = 1 and θ ≤ M } for some M > 0.
The set of possible answers is I = A and the correct answer is given by i (θ) = a (θ) := argmax a∈A θ, a . This additional assumption reduces the characteristic time to

T (θ) -1 = max w∈Σ A min a =a (θ) inf λ,a-a (θ) >0 λ ≤M θ -λ 2 Vw .
But the best response is less trivial to compute, in particular there is no closed formula for λ a as in BAI, see Lemma 8.

Lemma 8. For θ, λ ∈ R d , w in the interior of the probability simplex

• Σ A , min λ,a-a (θ) ≥0 λ ≤M θ -λ 2 Vw = sup γ≥0 max θ, (V w + γI d ) -1 V w (a (θ) -a) , 0 2 2 a (θ) -a 2 (Vw+γI d ) -1 - γ 2 θ 2 -M 2 . ( 9
)
And if γ attains the supremum in the right hand term of (9), then

λ = θ - max θ, (V w + γI d ) -1 V w (a (θ) -a) , 0 a (θ) -a 2 (Vw+γI d ) -1 (V w + γI d ) -1 (a -a) ,
attains the minimum of the left hand term of (9).

Proof. We set a (θ) = a , and introduce the Lagrangian

inf λ,a-a >0 λ ≤M θ -λ 2 Vw = sup γ≥0,α≥0 inf λ,a-a >0 λ ≤M θ -λ 2 Vw + α θ, a -a + γ 2 λ 2 -M 2 .
The infimum above is attained for

λ = θ -α(V w + γI d ) -1 (a -a) .
Thus the Lagrangian reduces to

inf λ,a-a >0 λ ≤M θ -λ 2 Vw = sup γ≥0,α≥0 - α 2 2 a -a 2 Vw+γI d + α θ, (V w + γI d ) -1 V w (a -a) + γ 2 θ 2 -M 2 .
The supremum in α is reached for

α = max θ, (V w + γI d ) -1 V w (a -a) , 0 a -a 2 (Vw+γI d ) -1
.

Using this particular α in the definition of λ and in the Lagrangian allows us to conclude.

D.1.2. TRANSUDCTIVE BAI

We can also consider the transductive BAI [START_REF] Fiez | Sequential experimental design for transductive linear bandits[END_REF] where the agent wants to find the best arm of a different set B that the one he is allow to pull. Precisely the set of parameters is The characteristic time in this case is

M = R d /{θ ∈ R d : | argmax b∈B θ, b | > 1},
T (θ) -1 = max w∈Σ A min b =b (θ) θ, b (θ) -b 2 2 b (θ) -b 2 V -1 w .
Note that the dependency on the arm set A here only appears through the matrix V w .

D.2. Threshold bandits

In this example the goal is to identify the set of arms whose mean is above a threshold ι ∈ R known by the agent. Thus, the set of parameters is M = R d /{θ ∈ R d : ∃a ∈ A, θ, a = ι}, the set of possible answers is I = P(A), the power set of the set of arms and the correct answer is given by i (θ) = {a ∈ A : θ, a ≥ ι}. We can also express in this example the characteristic time in a more explicit way.

Lemma 9. For all θ ∈ M,

T (θ) -1 = max w∈Σ A min a∈A ι -θ, a 2 2 a 2 V -1 w ,
and T (θ) = 2AA(ι), where we define A(ι) := {|ι -θ, a | -1 a : a ∈ A} and

AA(ι) := min w∈Σ A max a∈A(ι) a 2 V -1 w .
Proof. We proceed as the proof of Lemma 6. We have, using Lemma 5,

T (θ) -1 = max w∈∆ A min a∈A inf λ: sign(ι-λ,a ) λ,a >ι θ -λ 2 Vw 2 = max w∈∆ A min a∈A ι -θ, a 2 2 a 2 V -1 w .
Note that we recover in this example a weighted version of the G-complexity (AA-complexity) defined in Section 2. In particular if θ = 0 and ι = 1 then T (θ) = 2AA = 2d .

That makes sense since in this case, one shall estimate uniformly the mean of each arms.

D.2.1. TRANSDUCTIVE THRESHOLD BANDITS

We can generalize the previous example to any set of arms. Indeed if we fix a finite set of vector B ∈ R d the goal is then to identify all the elements b of this set such that θ, b ≥ ι for a known threshold τ ∈ R. Thus, the set of parameters is

M = R d /{θ ∈ R d : ∃b ∈ B, θ, b = ι}, the set of possible answers is I = P(B)
and the correct answer is given by i (θ) = {b ∈ B : θ, b ≥ ι}. The characteristic time makes appear, unsurprisingly, in this case, the transductive optimal design [START_REF] Yu | Active learning via transductive experimental design[END_REF].

Lemma 10. For all θ ∈ M, Proof. Simple adaptation of the proof of Lemma 9.

T (θ) -1 = max w∈Σ A min b∈B ι -θ, b 2 2 b 2 V -1
Again, in particular, if θ = 0 and τ = 1 we recover the complexity of the optimal transductive design T (θ) -1 = 2AB .

E. Proof for the Sample Complexity

In this section we prove the asymptotic optimality of LinGame-C and LinGame.

E.1. Events

We fix a constant α > 2 and define the event where the least square estimator is concentrated around the true parameter,

E t = ∀s ≤ t : 1 2 θs -θ 2 V Ns +ηI d ≤ h(t) := β(t, 1/t α ) .
This event holds with high probability.

Lemma 11. For all t ≥ 1

P θ (E c t ) ≤ 1 t α-1 .
Optimistic loss. We need to build an upper confidence bound on the true gain for LinGame-C and LinGame respectively at time s, for all w ∈ Σ AI or all w ∈ Σ A ,

g θ s ( w) = 1 2 (a,i)∈A×I w a,i θ -λ i t 2 V w g θ s (w) = 1 2 a∈A×I w a θ -λ is t 2 V w ,
where λ i s ∈ argmin λ∈¬i θs-1 -λ Vw s . For that, we just build a confidence bound for each term that appears in the right hand sum.

Lemma 12. On the event E t , for all a ∈ A and λ ∈ M, for all s ≤ t, θ -λ 2 aa ≤ min max

± θs -λ, a ± 2h(t) a (V Ns +ηI d ) -1 2 , 4L 2 M 2 .
Proof. First, note that since θ, λ ∈ M, their norms are bounded by M , thus it holds

θ -λ 2 aa = θ -λ, a 2 ≤ θ -λ 2 λ 2 ≤ 4M 2 L 2 .
Furthermore on E t we have

θ -λ 2 aa = θ -λ, a 2 ≤ sup θ : θs-θ 2 (V Ns +ηI d ) -1 ≤2h(t) θ -λ, a 2 = max ± θs -λ, a ± 2h(t) a (V Ns +ηI d ) -1 2 .
Combining the two inequalities above allows us to conclude.

Thus we define the upper confidence U a,i s on the coordinate (a, i) of the loss at time s ≤ t by

U a,i s = min max ± θs-1 -λ, a ± 2h(t) a (V N s-1 +ηI d ) -1 2 , 4L 2 M 2 , ( 10
)
where λ = λ i s for LinGame-C and λ = λ i s for LinGame. The optimistic gains are: g s ( w) = (a,i)∈A×I w a,i U a,i s /2 for LinGame-C and g s (w) = a∈A w a U a,is s /2 for LinGame.

Analysis. The first step of our analysis is to restrict it to the event E t , as done by [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF]; Degenne et al. (2019).

Lemma 13. Let E t be an event and T 0 (δ) ∈ N be such that for t ≥ T 0 (δ), E t ⊆ {τ δ ≤ t}. Then

E[τ δ ] ≤ T 0 (δ) + 1 + 2 α-2 α -2 .
Proof. We have, using Lemma 11,

E θ [τ δ ] = +∞ t=0 P(τ δ ≤ t) = T 0 (δ) + +∞ t=T0(δ) P(E c t ) ≤ T 0 (δ) + +∞ t=1 1 t α-1 ≤ T 0 (δ) + 1 + 2 α-2 α -2 ,
where we use an integral-sum comparison for the last inequality.

We need to prove that if E t holds, there exists such a time T 0 (δ) of order T (θ) -1 log(1/δ) + o log(1/δ) . The proof is given in the next section.

E.2. Analysis under concentration of LinGame-C

We assume in this section that the event E t holds. If the algorithm does not stop at stage t, then it holds

β(t, δ) ≥ max i∈I inf λi∈¬i 1 2 θt -λ i 2 V N t .
However, by definition of the event E t we have

i∈I inf λi∈¬i 1 2 θt -λ i 2 V N i t ≤ inf λ∈¬i (θ) 1 2 θt -λ 2 V N i (θ) t + i =i (θ) 1 2 θt -θ 2 V N i t ≤ inf λ∈¬i * 1 2 θt -λ 2 V N t + 1 2 θt -θ 2 V N t ≤ max i inf λ∈¬i 1 2 θt -λ 2 V N t + 1 2 θt -θ 2 V N t ≤ max i inf λ∈¬i 1 2 θt -λ 2 V N t + h(t) , thus one obtains β(t, δ) + h(t) ≥ i∈I inf λi∈¬i 1 2 θt -λ i 2 V N i t .
Hence we need to find a lower bound for the right hand sum. Let λ i,w (θ) ∈ argmin λ∈¬i θ -λ Vw .

Lemma 14. On E t , if the algorithm does not stop at t,

β(t, δ) + 4h(t)β(t, δ) + 4h(t) ≥ 1 2 i∈I θ -λ i,N i t ( θt ) 2 V N i t . (11)
Proof. Using the triangular inequality,

θ -θt V N i t + θt -λ i,N i t ( θt ) V N i t ≥ θ -λ i,N i t ( θt ) V N i t ,
and the inequality of Cauchy-Schwarz, we obtain

i∈I 1 2 θt -λ i,N i t ( θt ) 2 V N i t ≥ i∈I 1 2 θ -λ i,N i t ( θt ) V N t i -θt -θ V N i t 2 ≥ i∈I 1 2 θ -λ i,N i t ( θt ) 2 V N i t - i∈I θt -θ V N i t θ -λ i,N i t ( θt ) V N i t ≥ i∈I 1 2 θ -λ i,N i t ( θt ) 2 V N i t - i∈I θt -θ 2 V N i t i∈I θ -λ i,N i t ( θt ) 2 V N i t .
Using again that 1 2 θt -θ 2

V N t ≤ h(t) on E t , we get β(t, δ) ≥ i∈I 1 2 θ -λ i,N i t ( θt ) 2 V N i t -4h(t) i∈I 1 2 θ -λ i,N i t ( θt ) 2 V N i t ,
which leads to, using Lemma 28,

β(t, δ) + 4h(t)β(t, δ) + 4h(t) ≥ 1 2 i∈I θ -λ i,N i t ( θt ) 2 V N i t .
We now continue the proof by replacing the counts by the weights in (11).

Lemma 15. On E t , if the algorithm does not stop at t,

β(t, δ) + 5AI h(t)β(t, δ) + 2h(t) ≥ 1 2 i∈I θ -λ i,N i t ( θt ) 2 V W i t . (12)
Proof. Using the tracking property, see Lemma 31, to state that for all (a, i)

∈ A × I, -log(AI) ≤ N a,i t -W a,i t ≤ 1, which implies 1 2 i∈I θ -λ i,N i t ( θt ) 2 V N i t ≥ 1 2 i∈I θ -λ i,N i t ( θt ) 2 V W t - log(AI) 2 (a,i)∈A×I θ -λ i,N i t ( θt ) 2 aa ≥ 1 2 i∈I θ -λ i,N i t ( θt ) 2 V W i t - log(AI) 2 (a,i)∈A×I N a,i t θ -λ it,Nt ( θt ) 2 aa (a,i):N a,i t ≥1 1 N a t ≥ 1 2 i∈I θ -λ i,N i t ( θt ) 2 V W t - log(AI) 2 i∈I θ -λ i,N i t ( θt ) 2 V N i t AI .
Combining the last inequality with (11) yields

β(t, δ) + 4h(t)β(t, δ) + 4h(t) + log(AI) 2 √ 2AI β(t, δ) + 4h(t)β(t, δ) + 4h(t) ≥ 1 2 i∈I θ -λ i,N i t ( θt ) 2 V W i t .
Some simplifications, using the fact that h(t) ≥ 1 and β(t, δ) ≥ 1 (thanks to the choice of η), give us

β(t, δ) + 5AI h(t)β(t, δ) + 2h(t) ≥ 1 2 i∈I θ -λ i,N i t ( θt ) 2 V W i t .
We now transit from θ to each θs for s ≤ t in the right hand term of (12).

Lemma 16. On E t , if the algorithm does not stop at t,

β(t, δ) + 30AI h(t) β(t, δ) + 2h(t) 2 ≥ 1 2 i∈I t s=1 θs-1 -λ i,N i t ( θt ) 2 V w i s . (13)
Proof. Thanks to the inequality of Cauchy-Schwarz, we have,

1 2 i∈I θ -λ i,N i t ( θt ) 2 V W i t = 1 2 i∈I t s=1 θ -λ i,N i t ( θt ) 2 V w i s ≥ 1 2 i∈I t s=1 θs-1 -λ i,N i t ( θt ) 2 V w i s -2 θ -θs-1 V w i s θs-1 -λ i,N i t ( θt ) V w i s ≥ 1 2 i∈I t s=1 θs-1 -λ i,N i t ( θt ) 2 V w i s - i∈I t s=1 θ -θs-1 2 V w i s i∈I t s=1 θs-1 -λ i,N i t ( θt ) 2 V w i s . (14)
We need to upper bound the quantity i∈I t s=1 θ -θs-1

2 w i s
. By definition of the event E t we have θ -θs-1

2 aa = θ -θs-1 , a 2 ≤ θ -θs-1 2 V N s-1 +ηI d a 2 (V N s-1 +ηI d ) -1 ≤ 2h(t) a 2 (V N s-1 +ηI d ) -1 .
Thus thanks to Lemma 30, we get

i∈I t s=1 θ -θs-1 2 w i s = t s=1 (a,i)∈A×I w a,i s θ -θs-1 2 aa ≤ 2h(t) t s=1 a∈A w a s a 2 (V N s-1 +ηI d ) -1 ≤ 4h(t) 2 .
Now going back to ( 14) in combination with ( 12) and Lemma 28, it follows

β(t, δ) + 30AI h(t) β(t, δ) + 2h(t) 2 ≥ 1 2 i∈I t s=1 θs-1 -λ i,N i t ( θt ) 2 V w i s .
We now introduce the upper confidence bounds.

Lemma 17. On E t , if the algorithm does not stop at t,

β(t, δ) + 50AI h(t) β(t, δ) + 2h(t) 2 ≥ 1 2 t s=1 (a,i)∈A×I w a,i s U a,i s . (15)
Proof. By definition of the best response λ i s = argmin λ∈¬i θs-1 -λ 2 w i s , we have

1 2 i∈I t s=1 θs-1 -λ i,N i t ( θt ) 2 V w i s ≥ 1 2 i∈I inf λi∈¬i t s=1 θs-1 -λ i 2 V w i s ≥ 1 2 t s=1 (a,i)∈A×I w i,a s θs-1 -λ i s 2 aa . (16)
We recall the upper confidence bounds (10),

U i,a s = min max ± θs-1 -λ i s ), a ± 2h(t) a (V N s-1 +ηI d ) -1 2 , 4L 2 M 2 , it then holds U i,a s -θs-1 -λ i s 2 aa ≤ max ± θs-1 -λ i s , a ± 2h(t) a (V N s-1 +ηI d ) -1 2 -θs-1 -λ i s 2 aa ≤ 2h(t) a 2 (V N s-1 +ηI d ) -1 + 2 2h(t) a (V N s-1 +ηI d ) -1 | θs-1 -λ i s , a | .
Hence summing over t and using the inequality of Cauchy-Schwarz, we obtain

1 2 t s=1 (a,i)∈A×I w a,i s U i,a s -θs-1 -λ i s 2 aa ≤ t s=1 (a,i)∈A×I w a,i s h(t) a 2 (V N s-1 +ηI d ) -1 + w a,i s 2h(t) a (V N s-1 +ηI d ) -1 | θs-1 -λ i s , a | ≤ h(t) (a,i)∈A×I t s=1 w a,i s a 2 (V N s-1 +ηI d ) -1 + 2h(t) (a,i)∈A×I t s=1 w a,i s a 2 (V N s-1 +ηI d ) -1 t s=1 (a,i)∈A×I w a,i s θs-1 -λ i s 2 aa ≤ 2h(t) 2 + 2 √ 2h(t) 1 2 t s=1 (a,i)∈A×I w a,i s θs-1 -λ i s 2 aa ,
where the last inequality is derived from Lemma 30. Thus combining the previous inequality with ( 13) and ( 16) with some simplifications leads to

β(t, δ) + 50AI h(t) β(t, δ) + 2h(t) 2 ≥ 1 2 t s=1 (a,i)∈A×I w a,i s U a,i s .
It remains to bound the regret of the learner. Lemma 18. On E t , if the algorithm does not stop at t,

β(t, δ) + 50AI h(t) β(t, δ) + 2h(t) 2 + C 1 √ t + C 2 ≥ tT (θ) -1 , (17)
where

C 1 = 4L 2 M 2 log(AI) C 2 = 64L 2 M 2 (2 + log(AI)) .
Proof. Thanks to Proposition 3 for the algorithm AdaHedge, we have the following regret bound for the L w -learner

max w∈Σ AI 1 2 t s=1 (a,i)∈A×I w a,i U a,i s - 1 2 t s=1 (a,i)∈A×I w a,i s U a,i s ≤ 4L 2 M 2 log(AI) :=C1 √ t + 64L 2 M 2 (2 + log(AI)) :=C2
.

Finally, using this inequality in combination with (15) and the fact that the gains are optimistic (see Lemma 12), we obtain

β(t, δ) + 50AI h(t) β(t, δ) + 2h(t) 2 + C 1 √ t + C 2 ≥ sup w∈Σ AI 1 2 t s=1 (a,i)∈A×I w a,i U a,i s ≥ sup w∈Σ AI 1 2 t s=1 (a,i)∈A×I w a,i θ -λ i s 2 aa = t sup w∈Σ AI i∈I 1 t t s=1 1 2 θ -λ i s 2 V w i ≥ t sup w∈Σ AI i∈I inf q i ∈P(¬i) E λ∼q i 1 2 θ -λ 2 V w i = tT (θ) -1 ,
where for the last line we use the Sion's minimax theorem, see Lemma 1. Now let T (δ) be the maximum of the t ∈ N such that

β(t, δ) + 50AI h(t) β(t, δ) + 2h(t) 2 + C 1 √ t + C 2 ≥ tT (θ) -1 . (18)
And let δ min be the largest δ ∈ (0, 1) such that

β(log(1/δ) 3/2 , δ)+50AI h log(1/δ) 3/2 β log(1/δ) 3/2 , δ + 2h log(1/δ) 3/2 2 +C1 log(1/δ) 3/4 +C2 < log(1/δ) 3/2 T (θ) -1 . (19)
Such δ always exists since

β(log(1/δ) 3/2 , δ) + 50AI h log(1/δ) 3/2 β log(1/δ) 3/2 , δ + 2h log(1/δ) 3/2 2 + C1 log(1/δ) 3/4 + C2 = o log(1/δ)
and it depends only on the parameter of the problem: T (θ), M, α, η, A, I. Hence for δ ≤ δ min we know that T (δ) ≤ log(1/δ) 3/2 , which implies

T (δ) < T0(δ) := T (θ) β(log(1/δ) 3/2 , δ) + 50AI h log(1/δ) 3/2 β log(1/δ) 3/2 , δ + 2h log(1/δ) 3/2 2 + C1 log(1/δ) 3/4 + C2 + 1 . (20)
Actually, if we do not stop on E t , it implies that t ≤ T (δ) thanks to Lemma 17. Thus for t ≥ T 0 (δ) > T (δ) we know that τ δ ≤ t. We just proved the following lemma.

Lemma 19. If δ ≤ δ min , defined in (19) then for t ≥ T 0 (δ) where T 0 (δ) is defined in (20) , E t ⊂ {τ δ ≤ t} .

E.3. Proof of Theorem 2

Combining Lemma 13 and Lemma 19 for LinGame-C or Lemma 27 in Appendix E.4 for LinGame, we have for δ ≤ δ min ,

E θ [τ δ ] ≤ T 0 (δ) + 1 + 2 α-2 α -2 , ( 21
)
with T 0 (δ) = T (θ) log(1/δ)+o(log(1/δ)), see (20) for an exact expression for LinGame-C (or equation (33) for LinGame).

That implies the asymptotic optimality of LinGame-C and LinGame,

lim sup δ→0 E θ [τ δ ] log(1/δ) = T (θ) .
It remains to prove the δ-correctness. Thanks to the inequality (21) above, we have4 that τ δ < +∞ almost surely. And using Lemma 2 we know that P θ î = i (θ) ≤ δ, which allows us to conclude.

E.4. Analysis under concentration of LinGame

In this section we assume that the event E t holds and set i = i (θ). We prove that β(t, δ) N i t T (θ) -1 and that

N i t = O( √ t
) , for all i = i . We define the weights w i t = 1 {it=i} w t and the best response λ t s = argmin λ∈¬i θt-1 -λ 2 wt . Note that our algorithm computes λ i t only when i t = i.

When i s = i . Here we proceed as in Appendix E.2. If the algorithm does not stop at stage t we have

β(t, δ) ≥ 1 2 max i∈I inf λi∈¬i θt -λ i 2 V N t ≥ 1 2 inf λ∈¬i θt -λ 2 V N t .
Hence we need to find a lower bound for the right hand sum. Let λ i,w (θ) ∈ argmin λ∈¬i θ -λ Vw . We first replace in this sum θt by θ.

1 N a t ≥ 1 2 θ -λ i ,Nt ( θt ) 2 V W t - log(A) 2 A θ -λ i ,Nt ( θt ) 2 V N t
.

Combining the last inequality with (22) yields

β(t, δ) + 4h(t)β(t, δ) + 4h(t) + log(A) 2 √ 2A β(t, δ) + 4h(t)β(t, δ) + 4h(t) ≥ 1 2 θ -λ i ,Nt ( θt ) 2 V W t .
Some simplifications, using the fact that β(t, δ) ≥ 1 and h(t) ≥ 1, give us

β(t, δ) + 5A h(t)β(t, δ) + 2h(t) ≥ 1 2 θ -λ i ,Nt ( θt ) 2 V W t .
We now go from θ to each θs for s ≤ t in the right hand term of (23). Lemma 22. On E t , if the algorithm does not stop at t,

β(t, δ) + 30A h(t) β(t, δ) + 2h(t) 2 ≥ 1 2 t s=1 θs-1 -λ i ,Nt ( θt ) 2 Vw s . (24)
Proof. Using the inequality of Cauchy-Schwarz, we have,

1 2 θ -λ i ,Nt ( θt ) 2 V W t = 1 2 t s=1 θ -λ i ,Nt ( θt ) 2 Vw s ≥ 1 2 t s=1 θs-1 -λ i ,Nt ( θt ) 2 Vw s -2 θ -θs-1 Vw s θs-1 -λ i ,Nt ( θt ) Vw s ≥ 1 2 t s=1 θs-1 -λ i ( θt ) 2 Vw s - t s=1 θ -θs-1 2 Vw s t s=1 θs-1 -λ i ,Nt ( θt ) 2 Vw s . (25)
We need to upper bound the quantity t s=1 w a s θ -θs-1 2 aa . By definition of the event E t we have θ -θs-1

2 aa = θ -θs-1 , a 2 ≤ θ -θs-1 2 V N s-1 +ηI d a 2 (V N s-1 +ηI d ) -1 ≤ 2h(t) a 2 (V N s-1 +ηI d ) -1 .
Thus thanks to Lemma 30, we get t s=1 a∈A w a s θ -θs-1

2 aa ≤ 2h(t) t s=1 a∈A w a s a 2 (V N s-1 +ηI d ) -1 ≤ 4h(t) 2 . ( 26
)
Now going back to (25) in combination with ( 23) and Lemma 28 leads to

β(t, δ) + 30A h(t) h(t)β(t, δ) + 2h(t) 2 ≥ 1 2 t s=1 θs-1 -λ i ,Nt ( θt ) 2 Vw s . (27)
We now introduce the upper confidence bounds. Lemma 23. On E t , if the algorithm does not stop at t,

β(t, δ) + 50A h(t) β(t, δ) + 2h(t) 2 ≥ 1 2 t s=1 w a s U a,i s . ( 28
)
Proof. By definition of the best response λ i s = argmin λ∈¬i θs-1 -λ 2 ws , we have

1 2 t s=1 θs-1 -λ i ,Nt ( θt ) 2 Vw s ≥ 1 2 inf λ∈¬i t s=1 θs-1 -λ 2 Vw s ≥ 1 2 t s=1 a∈A w a s θs-1 -λ i s 2 aa . (29)
We recall the upper confidence bounds (10)

U a,i s = min max ± θs-1 -λ i s ), a ± 2h(t) a (V N s-1 +ηI d ) -1 2 , 4L 2 M 2 , it then holds U a,i s -θs-1 -λ i s 2 aa ≤ max ± θs-1 -λ i s , a ± 2h(t) a (V N s-1 +ηI d ) -1 2 -θs-1 -λ i s 2 aa ≤ 2h(t) a 2 (V N s-1 +ηI d ) -1 + 2 2h(t) a (V N s-1 +ηI d ) -1 | θs-1 -λ i s , a | .
Hence summing over t and using the inequality of Cauchy-Schwarz we obtain

1 2 t s=1 a∈A w a s U a,i s -θs-1 -λ i s 2 aa ≤ t s=1 a∈A w a s h(t) a 2 (V N s-1 +ηI d ) -1 + w a s 2h(t) a (V N s-1 +ηI d ) -1 | θs-1 -λ i s , a | ≤ h(t) a∈A t s=1 w a s a 2 (V N s-1 +ηI d ) -1 + 2h(t) a∈A t s=1 w a s a 2 (V N s-1 +ηI d ) -1 t s=1 a∈A w a s θs-1 -λ i s 2 aa ≤ 2h(t) 2 + 2 √ 2h(t) 1 2 t s=1 a∈A w a s θs-1 -λ i s 2 aa ,
where the last inequality is derived from Lemma 30. Thus combining the previous inequality with ( 24) and ( 29) with some simplifications leads to

β(t, δ) + 50A h(t) β(t, δ) + 2h(t) 2 ≥ 1 2 t s=1 a∈A w a s U a,i s .
We then bound the regret of the learner.

Lemma 24. On E t , if the algorithm does not stop at t,

β(t, δ) + 50A h(t) β(t, δ) + 2h(t) 2 + C 1 √ t + C 2 ≥ N i (t)T (θ) -1 , (30)
where

C 1 = 4L 2 M 2 log(A) and C 2 = 64L 2 M 2 (2 + log(A)) .
Proof. Thanks to Proposition 3 for the algorithm AdaHedge we have the following regret bound for the learner

L i w max w∈Σ A 1 2 t s=1 1 {is=i } a∈A w a U a,i s - 1 2 t s=1 a∈A w a,i s U a,i s ≤ 4L 2 M 2 log(A) :=C1 √ t + 64L 2 M 2 (2 + log(A)) :=C2
.

Note that the learner L i w is updated only when i s = i that is why the indicator function appears in the regret above. Finally using this inequality in combination with (28) and the fact that the gains are optimistic (see Lemma 12) we obtain

β(t, δ) + 50A h(t) β(t, δ) + 2h(t) 2 + C 1 √ t + C 2 ≥ 1 2 t s=1 a∈A w a,i s U a,i s ≥ sup w∈Σ A 1 2 t s=1 1 {is=i } a∈A w a U a,i s ≥ sup w∈Σ A 1 2 t s=1 1 {is=i } a∈A w a θ -λ i s 2 aa = N i t sup w∈Σ A 1 t t s=1 1 {is=i } 1 2 θ -λ i s 2 Vw ≥ N i t sup w∈Σ A inf q∈P(¬i ) E λ∼q 1 2 θ -λ 2 Vw = N i t T (θ) -1 ,
where in the last line we use the Sion's minimax theorem, see (1).

When i s = i . It remains to show that N i t = t -O( √ t). Lemma 25. Under event E t , N i t ≥ t - 2AI ∆ 2 min 8h(t) 2 + C 1 √ t + C 2 ,
where

C 1 = 4L 2 M 2 log(A) and C 2 = 64L 2 M 2 (2 + log(A)) .
Proof. Under E t , using successively (26) and the fact that θ ∈ ¬i for i = i , we get

2h(t) 2 ≥ t s=1 a∈A w a s 1 2 θ -θs-1 2 aa ≥ t s=1 1 {i =i } 1 2 a∈A w a s θ -θs-1 2 aa ≥ i =i inf λ∈¬i t s=1 1 2 a∈A w a,i s λ -θs-1 2 aa ≥ i =i t s=1 1 2 a∈A w a,i s λ i s -θs-1 2 aa
where for the last inequality we used the fact that w a,i s = 0 if i s = i and w a,i s = w a s otherwise. Now proceeding exactly as in the proof of Lemma 23 we have

1 2 t s=1 a∈A w a,i s U a,i s ≤ 1 2 t s=1 a∈A w a,i s θs-1 -λ i s 2 aa + 2h(t) 2 + 2 √ 2h(t) 1 2 t s=1 a∈A w a s θs-1 -λ is s 2 aa .
Summing over i = i in combination with the previous inequality then the inequality of Cauchy-Schwarz, we obtain

i =i 1 2 t s=1 a∈A w a,i s U a,i s ≤ 2h(t) 2 + 2h(t) 2 I + 4h(t) 2 √ I ≤ 8Ih(t) 2 .
However, thanks to Proposition 3 for the algorithm AdaHedge we have the following regret bound for the learner L

i w max a∈A 1 2 t s=1 1 {is=i} U a,i s - 1 2 t s=1 a∈A w a,i s U a,i s ≤ 4L 2 M 2 log(A) :=C1 √ t + 64L 2 M 2 (2 + log(A)) :=C2
.

Therefore combining the two previous inequalities leads to

I 8h(t) 2 + C 1 √ t + C 2 ≥ i =i 1 2 max a∈A t s=1 1 {is=i} U a,i s ≥ i =i 1 2A a∈A t s=1 1 {is=i} U a,i s . (31)
We now use the lemma stated below to lower bound one of the U a,i s . Lemma 26 and (31) then allow us to conclude

I 8h(t) 2 + C 1 √ t + C 2 ≥ i =i 1 2A t s=1 1 {is=i} ∆ 2 min = ∆ 2 min 2A (t -N i t ) .
Lemma 26. On E t , for all s ≤ t, if i s = i then there exists an arm a ∈ A such that

U a,is s ≥ ∆ 2 min , where ∆ 2 min = inf λ∈¬i max a∈A θ -λ, a 2 > 0 . Proof. Consider the projection θM s-1 ∈ argmin θ ∈M θs-1 -θ V N s-1 +ηI d . By definition of i s we know that i ( θM s-1 ) = i s = i . Indeed if i ( θM s-1 ) = i = i s then inf λ∈¬i θs-1 -λ V N s-1 +ηI d < inf λ∈¬is θs-1 -λ V N s-1 +ηI d ≤ inf λ∈M: i (λ)=i θs-1 -λ V N s-1 +ηI d = θs-1 -θM s-1 V N s-1 +ηI d ,
which leads to a contradiction since ¬i ∈ M. In particular θM s-1 ∈ ¬i , thus there exists a ∈ A such that

θ -θM s-1 , a 2 ≥ ∆ 2 min .
Then by construction of the upper confidence bound, the definition of the projection and the inequality of Cauchy-Schwarz,

U a,is s ≥ 2h(t) a 2 (V N s-1 +ηI d ) -1 ≥ θ -θs-1 2 V N s-1 +ηI d a 2 (V N s-1 +ηI d ) -1 ≥ θ -θM s-1 2 V N s-1 +ηI d a 2 (V N s-1 +ηI d ) -1 ≥ θ -θM s-1 , a 2 ≥ ∆ 2 min .
Conclusion. Hence combining Lemma 24 and Lemma 25, on the event E t , if the algorithm does not stop

β(t, δ) + 50A h(t) β(t, δ) + 2h(t) 2 + C 1 √ t + C 2 + 2AIT (θ) -1 ∆ 2 min 8h(t) 2 + C 1 √ t + C 2 ≥ T (θ) -1 t . ( 32
)
We can then conclude as in Appendix E.2. Let δ min be the largest δ ∈ (0, 1) such that

β(log(1/δ) 3/2 , δ) + 50A h log(1/δ) β(log(1/δ) 3/2 , δ) + 2h(t) 2 + C 1 log(1/δ) 3/4 + C 2 + 2AIT (θ) -1 ∆ 2 min 8h log(1/δ) 3/2 2 + C 1 log(1/δ) 3/4 + C 2 < T (θ) -1 log(1/δ) 3/2 .
Then for

T 0 (δ) := T (θ) β(log(1/δ) 3/2 , δ) + 50A h log(1/δ) β(log(1/δ) 3/2 , δ) + 2h(t) 2 + C 1 log(1/δ) 3/4 + C 2 + 2AIT (θ) -1 ∆ 2 min I 8h log(1/δ) 3/2 2 + C 1 log(1/δ) 3/4 + C 2 (33)
we have the following lemma. Note that we have T 0 (δ) = T (θ) log(1/δ) + o log(1/δ) .

Lemma 27. If δ ≤ δ min then for t ≥ T 0 (δ) where T 0 (δ) is defined in (33) , E t ⊂ {τ δ ≤ t} .

E.5. Technical lemmas

We regroup in this section some technical lemmas.

Lemma 28. For all α, y ≥ 0, if for some

x ≥ 0 if holds y ≥ x -α √ x then x ≤ y + α √ y + α 2 . Proof. Just note that for z = √ x we have z 2 -αz -y ≤ 0 , thus x ≤ 1 4 α + α 2 + 4y 2 ≤ y + α 2 2 + α 2 α 2 + 4y ≤ y + α √ y + α 2 .
We then state a result derived from the concavity of V → log det(V ).

Lemma 29. Let (w t ) t≥1 be a sequence in Σ A and η > 0 then 2018). And its partial derivative with respect to the coordinate a at W is

∇ a f (W ) = a 2 (W +ηI d ) -1 .
Hence using the concavity of f we have

a∈A w s a a 2 (V Ws +ηI d ) -1 = W s -W s-1 , ∇ a f (W s ) ≤ f (W s ) -f (W s-1 ) . Which implies that t s=1 a∈A w s a a 2 V Ws +ηI d ≤ f (W t ) -f (W 0 ) = log det(V Wt + ηI d ) det(ηI d ) ≤ d log 1 + tL 2 dη ,
where for the last inequality we use the inequality of arithmetic and geometric means in combination with Tr(W t ) ≤ tL 2 .

A simple consequence of the previous lemma follows.

Lemma 30. For all t, t s=1 a∈A

w a s a 2 (V N s-1 +ηI d ) -1 ≤ 2h(t) = 2β(t, 1/t α ) t s=1 a∈A w a s a 2 (V N s-1 +ηI d ) -1 ≤ 2h(t) .
Proof. According to the tracking procedure (Lemma 31), we know that N a s-1 ≥ W a s-1 -log(AI). Thus, in combination with the choice of η we can replace counts by weights

V Ns-1 + ηI d ≥ V W a s -V w a s -log(AI)V 1 A + ηI d ≥ V W a s -(log(A) + 1)V 1 A + ηI d ≥ V Ws + η 2 I d ,
where

1 A = (1, . . . , 1) ∈ R A . Hence we obtain a 2 (V N s-1 +ηI d ) -1 ≤ a 2 (V W a s +(η/2)I d ) -1 ,
and applying Lemma 29 leads to

t s=1 a∈A w a s a 2 (V N s-1 +ηI d ) -1 ≤ d log 1 + tL 2 dη ≤ 2h(t) .
The exact same proof holds for w a s instead of w a s since thanks to the tracking we have also in this case

N a s-1 ≥ W a s-1 - log(A) ≥ W a s-1 -log(AI).

F. Concentration Results

We restate here the Theorem 20.4 (in combination with the Equation 20.10) by [START_REF] Lattimore | Bandit Algorithms[END_REF]. Theorem 3. For all η > 0 and δ ∈ (0, 1),

P θ ∃t ∈ N, 1 2 θt -θ 2 V N t +ηI d ≥ β(t, δ) ≤ δ , where
β(t, δ) := log 1 δ + d 2 log 1 + tL 2 ηd + η 2 M 2 = log 1 δ + d 2 log 1 + tL 2 ηd + M √ η 2 log 1 δ + d log 1 + tL 2 ηd + ηM 2 2 .
The Lemma 2 is a simple consequence of this theorem.

Proof of Lemma 2. Using the fact that θ ∈ ¬i t when i t = i (θ) and Theorem 3, it follows

P θ τ δ < ∞ ∧ i τ δ = i (θ) ≤ P θ ∃t ∈ N, inf λ∈¬i t 1 2 θt -λ 2 V N t > β(t, δ), i t = i (θ) ≤ P θ ∃t ∈ N, 1 2 θt -θ 2 V N t +ηI d ≥ β(t, δ) ≤ δ .
2. v j-1 (j) ≤ v j (j) + 1. Then let v j-1:K be the mean of v j-1 (j) , . . . , v K (j) and let v (j-1) be the vector with v 1 (j-1) = v 1 (j) , ..., v j-2 (j-1) = v j-2 (j) and v j-1 (j-1) = . . . = v K (j-1) = v j-1:K . Then v (j-1) ← v (j) .

Case 1: v j-1 (j) > v j (j) + 1. Let S = [j : K]. then S = [K] and v ∈ A S . Hence v is not reachable from 0.

Case 2: v j-1 (j) ≤ v j (j) + 1. Let w be defined by w 1 = . . . = w j-2 = 0, w j-1 = 1 -(K -j + 1)(v j-1:K -v j (j) ) and w j = . . . = w K = v j-1:K -v j (j) . Since v j-1 (j) ≤ v j (j) + 1 and w ∈ K , the reverse move ← j-1,w is valid at v (j) . Then the image of v (j) by that reverse move is v (j-1) . Note that w j-1 ≥ w j = . . . = w K .

We have now all the tools to state the characterization of the the elements v of S 0 such that 0 ← . . . ← v . By a simple induction using the last case distinction, we have the following: let v ∈ S 0 and let i 1 , . . . , i K ∈ [K] be such that v i1 ≥ . . . ≥ v i K . If 0 ← . . . ← v, then there exists u 1 , . . . , u K-2 and w 1 , . . . , w K-1 such that 1. 0 ← i1,w1 u 1 ← i2,w2 . . .

← i K-2 ,w K-2 u K-2 ← i K-1 ,w K-1 v, 2. for all j ∈ [K -2], u i1 j ≥ . . . u ij j ≥ u ij+1 j = . . . = u i K j = 1 K-j K k=j+1 v i k ,
3. for all j ∈ [K -1], w i1 j = . . . w ij-1 j = 0 and w j j ≥ w ij+1 j = . . . = w i K j .

In order to prove the theorem, we then only need a bound on v i K = -K-1 j=1 w K j . The characterization of w j implies that w K j ≤ 1/(K -j + 1) . Hence v i K ≥ -K j=2 1 j .

H. A Fair Comparison of Stopping Rules

We investigate closely the stopping rules employed in existing linear BAI algorithm. We first make a synthesized table that resembles stopping rules and decision rules of all existing algorithms, including ours, in Table 4. We denote by Ât the active arm set for elimination-based algorithms, and by i Ât the only arm left in Ât when | Ât | = 1.

We show that they are all the same up to the choice of the exploration rate. Note that in Table 4, we have replaced all the exploration term by β(t, δ), and we have also listed the original terms (with their original notation, thus may be in conflict with notation of the current paper). In the following, we always use the same exploration rate β(t, δ) for all stopping rules.

LinGame and LinGame-C. We first notice that using the same argument as the proves of Lemma 5 and Lemma 6, the stopping rule of LinGame and LinGame-C (and also the one of GLUCB) can be rewritten as

min i =i ( θt)
θt , a i -a ( θt ) 2 2 a i -a ( θt ) 2

V -1 N t
1 a ( θt ) θt ≥ a i θt > β(t, δ) .

Now we compare it with other stopping rules. It is clear that if such a exists, then it can only be the empirical best arm a ( θt ). Thus, ∀a = a ( θt ), a ( θt ) -a θt , a i -a ( θt ) 2 2 a i -a ( θt ) 2

LinGame-C and

V -1 N t
1 a ( θt ) θt ≥ a i θt = θt , a jt -a ( θt ) 2 2 a jt -a ( θt ) 2

V -1 N t ≥ β(t, δ) ,
and LinGame-C stops as well.

In conclusion, all the stopping rules are equivalent if we set their exploration term to the same, though formulated in different manners.

I. Implementation Details

In this section, we provide some further experiment details. We also share a few insights over different aspects of implementations of different pure exploration linear bandits algorithms. In particular, we propose a new Frank-Wolfe-typed heuristic to solve generic AB-design.

I.1. Experimental setting

More details for algorithm implementations. We give more clarifications on each individual algorithm implemented.

• For our algorithms LinGame and LinGame-C, we implemented the version with the boundedness assumption.

• For LinGapE We implemented the greedy version, that is, pull the arm argmin a∈A a it -a jt 2 (V N t +aa ) -1 with i t = i ( θt ) and j t = argmax j =it θt , a j -a ( θt ) + a ( θt ) -a jt V -1 N t 2β(t, δ). Note that this version does not have a theoretical guarantee in the general case. However, as we stated in Section 4, the GLUCB proposed by [START_REF] Zaki | Towards optimal and efficient best arm identification in linear bandits[END_REF] is equivalent to this greedy version of LinGapE, and they provided an analysis for the 2-arm and 3-arm case. LinGapE is designed for -best-arm identification, we set = 0 in our experiments to make sure that it outputs the optimal one.

• For X Y-Static, we implemented the greedy incremental version for both AA-allocation and AB dir -allocation, that allows us to avoid the optimal design-computing step. To implement the non-greedy version, readers are invited to look at next Section I.2 where we discuss in detail the computation of AB-optimal design.

• For X Y-Adaptive, it requires a hyper-parameter that characterizes the length of each phase. We set that hyperparameter to 0.1 as done by [START_REF] Soare | Best-arm identification in linear bandits[END_REF].

Technical details. All the algorithms and experiments are implemented in Julia 1.3.1, and plots are generated using the StatsPlots.jl package.

Other external dependencies are: JLD2.jl, Distributed.jl, IterTools.jl, CPUTime.jl, LaTeXStrings.jl.

For reproducibility. To rerun our code, your need to have Julia installed, then unzip code.zip and do the following in your terminal.

$ cd PATH / TO / THE / FOLDER / code / linear $ julia julia > include ( " experiment_bai1 . jl " ) # reproduce Fig . 1 julia > include ( " viz_bai1 . jl " ) # visualization julia > include ( " experiment_bai2 . jl " ) # reproduce Fig . 2 julia > include ( " viz_bai2 . jl " ) # visualization

Figure 1 .Figure 2 .

 12 Figure 1. Sample complexity over the usual counter-example with δ = 0.1, 0.01, 0.0001 respectively. CG = LinGame-C, Lk = LinGame, RR = uniform sampling, fix = tracking the fixed weights, GS = X Y-Static with AA-allocation, XYS = X Y-Static with ABdirallocation, LG = LinGapE. The mean stopping time is represented by a black cross.

  the set of possible answers is I = B and the correct answer is given by i (θ) = b (θ) := argmax b∈B θ, b .

  θ) = 2AB(ι), where we defined B(ι) := {|ι -θ, b | -1 b : b ∈ B} and AB(ι)

  Define the function f (W ) = log det(V W + ηI d ) for any W ∈ (R + ) A . It is a concave function since the function V → log det(V ) is a concave function over the set of positive definite matrices (see Exercise 21.2 of Lattimore & Szepesvari

  LinGame ⇒ X Y-Static. If LinGame-C stops at time t, then for a = a ( θt ), we have∀a = a, a -a V -1 N t 2β(t, δ) ≤ θt , a -a ,and X Y-Static stops as well.X Y-Static ⇒ X Y-Adaptive. Suppose that X Y-Static stops at time t under its stopping rule, then ∃a ∈ A, ∀a = a, a -a V -1 N t 2β(t, δ) ≤ θt , a -a .

Table 1 .

 1 Average number of pulls of each arm.

		LinGame LinGame-C DKM
	a 1	1912	1959	1943
	a 2	5119	4818	4987
	a 3	104	77	1775
	Total	7135	6854	8705

Table 2 .

 2 Optimal w for various complexities (∆min = 0.0049958).

		w AB	w ABdir	w AA
	a 1	0.047599	0.499983	0.499983
	a 2	0.952354	0.499983	0.499983
	a 3	0.000047	0.000033	0.000033
	T w	369	2882	2882
		T (θ)	2AB dir /∆ 2 min	8AA/∆ 2 min
	Complexity 0.124607	32.0469	64.0939

  Table of notation

			Notation	Meaning
	M			set of parameters
	M			upper bound on the norm of θ
	A			finite set or arms
	A			number of arms
	B			transductive set
	B			number of elements in the transductive set
	I			finite set of answers
	I			number of answers
	L			upper bound on the norms of the arms
	θ			parameter in M
	a t			arm pulled at time t
	i t			answer chosen at time t
	N a,i t	=	t s=1 1 {as=a,it=i}	number of draws of arm a for a given answer i
	η			regularization parameter
	θt			regularized least square estimate
	w s			weights in Σ A played by the agent in LinGame
	w a,i s = w s 1 {is=i} W a,i t = t s=1 w a,i s w a s = i∈I w a,i s or (w a,i s ) i∈I w i s = a∈A w a,i s or (w a,i s ) a∈A partial weights or vector of partial weights in LinGame weights for arm a and answer i in LinGame cumulative sum of weights in LinGame partial weights or vector of partial weights in LinGame
	w s			weights in Σ AI played by the agent in LinGame-C
	W a,i t w a s = i∈I w a,i = t s=1 w a,i s s or ( w a,i s ) i∈I w i s = a∈A w a,i s or ( w a,i s ) a∈A partial weights or vector of partial weights in LinGame-C cumulative sum of weights in LinGame-C partial weights or vector of partial weights in LinGame-C U a,i s upper confidence bounds to build the optimistic gain, see (10)

  LinGapE ⇒ LinGame-C and LinGame Finally, we suppose that LinGapE stops at time t, then it comesj t = argmax j∈I θt , a j -a ( θt ) + a ( θt ) -a j V -1 ( θt ) -a j -a ( θt ) -a j V -1

		2β(t, δ)
	N t
	= argmin	2β(t, δ) .
	N t
	By consequence,
	min
	i =i ( θt)

V -1 N t 2β(t, δ) ≤ θt , a ( θt ) -a , j∈I θt , a

This complexity is denoted as X Y by[START_REF] Soare | Best-arm identification in linear bandits[END_REF].

This condition is a simple technical trick to simplify the analysis. An η independent of A,L,M will lead to the same results up to minor adaptations of the proof.

If δ ≤ δmin the inequality holds replacing T0(δ) by T (δ) + 1 defined in[START_REF] Even-Dar | Action elimination and stopping conditions for reinforcement learning[END_REF] which is also finite.

Acknowledgements

The research presented was supported by European CHIST-ERA project DELTA, French Ministry of Higher Education and Research, Nord-Pas-de-Calais Regional Council, and by French National Research Agency as part of the "Investissements d'avenir" program, reference ANR19-P3IA-0001 (PRAIRIE 3IA Institute) and the project BOLD, reference ANR19-CE23-0026-04.

G. Tracking

We call tracking the following interaction. Starting from vectors W 0 = N 0 = (0, . . . , 0) ∈ R K , for each stage t = 1, 2, . . .

• Nature reveals a vector w t in the simplex Σ K and updates W t = W t-1 + w t .

• A tracking rule selects k t ∈ [K] based on (w 1 , . . . , w t ) and forms N t = N t-1 + e kt , where (e i ) i∈ [K] is the canonical basis.

Note that w t is known to the tracking rule when choosing k t . Definition 1. We call C-Tracking any rule which for all stages t ≥ 1 selects

This defines C-tracking up to the choice of k t when the argmin is not unique. The name stands for cumulative tracking and is introduced by [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF].

Lemma 31. The C-Tracking procedure described above ensures that for all t ∈ N, for all k ∈ [K],

The upper bound is given by [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF]. The lower bound is due to [START_REF] Degenne | Structure Adaptive Algorithms for Stochastic Bandits[END_REF] and is reproduced below.

The tracking procedure is such that for all stages t ∈ N, N t -W t ∈ S 0 . Our proof strategy is to characterize the subset of S 0 that can be reached during the tracking procedure, starting from

We define a move → w as function from S 0 to itself parametrized by w that maps v to v-w+e k , where k = argmin j∈[K] vw. If the value of that function at v is u, we write v → w u . A vector u ∈ S 0 is said to be reachable in one move from v ∈ S 0 if there exists w ∈ K such that v → w u. We denote it by v → u. It is said to be reachable from v if there is a finite sequence of such moves such that v → . . . → u.

A reverse move ← k,w is a function from S 0 to itself parametrized by k and w that maps v to v + we k . A reverse move is said to be valid at v if v k ≤ min j v j + 1. If the value of that function at v is u, we write u ← k,w v . A vector u ∈ S 0 is said to be reverse-reachable in one move from v ∈ S 0 if there exists k ∈ [K] and w ∈ K such that u ← k,w v and such that this is a valid reverse move at v. We denote it by u ← v.

We now prove that

Indeed, for the reverse move to be valid, one of the coordinates in M v was decreased by 1, and they were added coordinates of a w ∈ K , that sum at most to 1.

. Then we will prove that one of the two following statements is true:

and all arms different from a ( θt ) would be discarded under X Y-Adaptive. Furthermore, a ( θt ) would never be discarded since ∀a = a ( θt ), θt , a -a ( θt

and X Y-Adaptive stops.

X Y-Adaptive ⇒ ALBA Now if X Y-Adaptive stops at time t, then all arms but a ( θt ) are discarded, and

Therefore, those arms would also be discarded under ALBA, and ALBA stops.

ALBA ⇒ LinGapE and GLGapE. Next, suppose that ALBA stops at time t under its stopping rule, then the only arm left would be a ( θt ), and

And in particular, we get θt , a jt -a ( θt ) + a ( θt ) -

Thus LinGapE/GLGapE stops under its stopping rule.

I.2. Computation of different complexities

As mentioned in Section 2, computing the solution to a specified optimization problem is required in many existing linear BAI algorithms. We survey some methods that can potentially be useful to handle that issue.

We recall that the three notions of complexity AA, AB dir , AB (θ) can be written in a unified form,

where B is the transductive set, i.e. a finite set of elements in R d . Transductive sets corresponding to different complexity types mentioned in this paper can be found in Table 5.

Frank-Wolfe. We can use a Frank-Wolfe heuristic to compute the optimizer of (34) shown in Algorithm 3. This heuristic is used for example by [START_REF] Fiez | Sequential experimental design for transductive linear bandits[END_REF]. Note that this heuristic has been proved to have a linear convergence guarantee when B = A [START_REF] Ahipasaoglu | Linear convergence of a modified Frank-Wolfe algorithm for computing minimum-volume enclosing ellipsoids[END_REF]. It is not clear, however, that the same guarantee holds for other transductive sets.

A simple sanity check to test whether a solver works smoothly is to solve AB (θ) for classical multi-armed bandits (i.e. when A = {e 1 , e 2 , . . . , e d }), for which a solver with guarantee exists (see [START_REF] Garivier | Explore first, exploit next: The true shape of regret in bandit problems[END_REF]. In particular we found instances where Algorithm 3 does not converge toward the optimal weights, for example: A = {e 1 , e 2 , e 3 }, θ = (0.9, 0.5, 0.5).

Algorithm 3 Frank-Wolfe heuristic for computing generic AB-design

We propose a variant of the previous heuristic that takes into account a count for each element in the transductive set B. The pseudo-code of our method is displayed in Algorithm 4. Sanity check on various MAB instances shows the correctness of our heuristic, its convergence guarantee remains for the future work.

Entropic mirror descent. An entropic mirror descent alternative is used by [START_REF] Tao | Best arm identification in linear bandits with linear dimension dependency[END_REF] to compute AA. The entropic mirror descent approach requires the knowldge of the Lipschitz constant of log det V w . Unfortunately, that Lipschitzness property does not seem to hold. [START_REF] Lu | Relatively-smooth convex optimization by first-order methods , and applications[END_REF] propose a solution to overcome the Lipschitz issue, but only for AA-design. Whether it still works for general AB-design remains an open question.

Algorithm 4 Saddle Frank-Wolfe heuristic for computing generic AB-design

V ← V + a a V ← V + b b w ← t t+1 w + 1 t+1 e a t ← t + 1 end while return w