--- title: "Improved Pure Exploration in Linear Bandits with No-Regret Learning" authors: - "Mohammadi Zaki" - "Avi Mohan" - "Aditya Gopalan" doi: "10.24963/ijcai.2022/515" url: "https://ijcai.org/proceedings/2022/515" pdf: "https://ijcai.org/proceedings/2022/0515.pdf" venue: "Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence" year: 2022 pages: "3709-3715" track: "Main Track" keywords: - "Machine Learning: Online Learning" - "Machine Learning: Learning Theory" --- # Improved Pure Exploration in Linear Bandits with No-Regret Learning Mohammadi Zaki, Avi Mohan, Aditya Gopalan *Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence*, pages 3709-3715. DOI: [10.24963/ijcai.2022/515](https://doi.org/10.24963/ijcai.2022/515) ## Abstract We study the best arm identification problem in linear multi-armed bandits (LMAB) in the fixed confidence setting ; this is also the problem of optimizing an unknown linear function over a discrete domain with noisy, zeroth-order access. We propose an explicitly implementable and provably order-optimal sample-complexity algorithm for best arm identification. Existing approaches that achieve optimal sample complexity assume either access to a nontrivial minimax optimization oracle (e.g. RAGE and Lazy-TS) or knowledge of an upper-bound on the norm of the unknown parameter vector(e.g. LinGame). Our algorithm, which we call the Phased Elimination Linear Exploration Game (PELEG), maintains a high-probability confidence ellipsoid containing the unknown vector, and uses it to eliminate suboptimal arms in phases, where a minimax problem is essentially solved in each phase using two-player low regret learners. PELEG does not require to know a bound on norm of the unknown vector, and is asymptotically-optimal, settling an open problem. We show that the sample complexity of PELEG matches, up to order and in a non-asymptotic sense, an instance-dependent universal lower bound for linear bandits. PELEG is thus the first algorithm to achieve both order-optimal sample complexity and explicit implementability for this setting. We also provide numerical results for the proposed algorithm consistent with its theoretical guarantees. ## Full text ## 1 Introduction Noisy function optimization over a domain is a basic primitive in machine learning, and a well-known formalization of it is the problem of Probably Approximately Correct (PAC) best arm identification in multi-armed bandits [Even-Dar et al., 2006]. In this problem, a learner is given a set of arms with unknown means. The learner must sequentially test arms and output, as soon as possible with high confidence, a near-optimal arm (where optimality is defined in terms of the largest mean). Often, the arms (decisions) and their associated rewards are structurally related, allowing for more efficient learning of the rewards and transfer of learnt information. One of the best-known examples of structured decision spaces is the linear bandit, whose arms are vectors (points) in Rd . The reward or function value of an arm is an unknown linear function of its vector representation, and the goal is to find an arm with maximum reward in the shortest possible time by measuring arms' rewards sequentially with noise. This framework models an array of structured online linear optimization problems including adaptive routing [Awerbuch and Kleinberg, 2008b], smooth function optimization over graphs [Valko et al., 2014], subset selection [Kuroki et al., 2019] and, in the nonparametric setting, black box optimization in smooth function spaces [Srinivas et al., 2010], among others. We study the problem of best arm identification (BAI) in linearly parameterized multi-armed bandits (LMAB), which was first introduced by [Soare et al., 2014] and has received extensive attention ever since. Given a (finite) set of feature vectors in Rd , the goal is to identify the vector with the largest inner product with an unknown weight vector θ∗ ∈ Rd using only noisy linear measurements of the form xT θ∗ + η. Our main contribution is to propose a new phased elimination algorithm for this problem. At a high level, the design of the algorithm follows the template of the phased RAGE algorithm of [Fiez et al., 2019], which enjoys informationtheoretically optimal (instance-dependent) PAC sample complexity. Their algorithm, however, requires repeated oracle access to a non-trivial minimax oracle in each phase. It is not clear, from a performance standpoint, in what manner (and to what accuracy) this optimization problem should be practically solved 1 to enjoy the claimed sample complexity. [Jedra and Prouti`ere, 2020] propose an algorithm (Lazy Track-andStop) inspired by ideas from [Garivier and Kaufmann, 2016]. Lazy-TS is shown to achieve optimal expected sample complexity, again in the limit as δ ↓ 0. However, their algorithm again prescribes a sampling strategy which requires a minimax oracle, the formal implementation of which is left unclear. 1 For its experiments, the paper implements a (approximate) minimax oracle using a naive variant of the the Frank-Wolfe algorithm (with subgradients instead of gradients) and a heuristic stopping rule, but such a scheme is not theoretically guaranteed to converge for non-smooth optimization, see Sec. 4 for a detailed discussion. [Wang et al., 2021] propose a scheme where they modify the Frank-Wolfe implementation proposed in [Jedra and Prouti`ere, 2020] to deal with non-smooth optimization objectives and implement it for the case of unstructured and structured bandits. However, their algorithm (which we call FWS) requires explicit forced exploration which can prove to be costly especially for the linear bandit setting, where K could be very large. We show via simulations (Sec. 6) that this indeed causes FWS to waste many samples on uninformative arms causing the performance to degrade. In contrast, PELEG performs exploration implicitly by constructing correct confidence sets around the unknown parameter, thus circumventing this problem. In summary, we give an explicit linear-bandit best-arm identification algorithm with instance-optimal PAC sample complexity and, more importantly, a clearly quantified computational effort by using new techniques. The algorithm relies upon a game-theoretic interpretation of the minimax optimization problem that is at the heart of the instance-based sample complexity lower bound. This yields a concrete adaptive sampling strategy that uses carefully constructed confidence sets for the unknown parameter θ∗ . The adaptive sampling strategy is driven by the interaction of two no-regret online learning subroutines that attempt to solve the minimax problem approximately (the seeds of this game-theoretic approach were laid by [Degenne et al., 2019] for the simple (i.e., unstructured) multiarmed bandit problem), obviating the worry of i) solving the optimal minimax allocation to a suitable precision and ii) making an integer sampling allocation from it by rounding, which occur in the approach of Fiez et al [Fiez et al., 2019]. As will be evident in Sec. 5 this approach (and careful choices of parameters) obviate the need of knowing bounds on the norm of the parameter-space; trading it off with a computable parameter from the arm set. ## 2 Preliminaries Problem statement. Given a finite set of arms X = {x1, . . . , xK} ⊂ Rd , the learning agent can play in each round t = 1, 2, . . . an arm xt ∈ X, and receives a reward y(xt) = θ∗T xt + ηt, where the noise ηt is zero-mean assumed to be conditionally 1- sub-Gaussian. In this regard, a learning algorithm for the best arm identification problem comprises the following rules: (1) a sampling rule, which determines which arm to play based on past data, (2) a stopping rule, which controls the end of sampling phase and is a function of the past observations and reward, and (3) a recommendation rule, which, after the algorithm stops, outputs a guess A ∈ [K] for the best arm's index. An algorithm that stops and returns A = a∗ = argmaxa∈[K] xTa θ∗ with probability at least 1-δ is said to be δ-Probably Approximately Correct (δ-PAC), and by its sample complexity we mean how soon the algorithm stops. Assumptions and Notation. We assume that there is a unique optimal arm for the true parameter θ∗ , i.e., ∃a ∈ [K] : ∀b ∈ [K] \ {a} : θ∗T xa > θ∗T xb. More generally, for any θ ∈ Rd for which there is a unique optimal arm w.r.t. θ, we define a∗ (θ) = argmaxa∈[K] θT xa. We denote by ν k θ∗ the distribution of the reward (observation) obtained by sampling arm k ∈ [K], i.e., ∀t ⩾ 1, y(xt) ∼ ν k θ∗, whenever xt = xk. Given two probability distributions µ, ν over R, KL(µ, ν) denotes the Kullback-Leibler divergence of µ with respect to ν (assuming absolute continuity of the measures). We assume that ∥xk∥2 ⩽ 1, ∀xk ∈ X. Given a positive definite matrix A, ∥x∥A := √xT Ax denotes the matrix norm induced by A. When the matrix is unspecified, this defaults to the standard 2-norm. For any i ∈ [K], i ̸= a∗ , let ∆i := θ∗T (xa∗ -xi) be the gap between the largest expected reward and the expected reward of (suboptimal) arm xi. Let ∆min := mini∈[K] ∆i. We denote B(z, r) as the closed ball with center z and radius r. We define PK to be the set of all probability mass functions on an alphabet of size K. For the benefit of the reader, we provide a glossary of commonly used symbols in Sec. A. ## 3 AGame-theoretic Approach towards Optimal Sample Complexity The phased elimination approach. We first note that a lower bound on the sample complexity of any δ- PAC algorithm for the canonical (i.e., unstructured) bandit setting [Garivier and Kaufmann, 2016] was generalized by [Fiez et al., 2019] and [Zaki et al., 2019] to the linear bandit setting. This result states that any δ-PAC algorithm in the linear setting must satisfy Eθ∗[τ] ⩾ (log 1/2.4δ) 1 Tθ∗ = (log 1/2.4δ) 1 Dθ∗ , where Tθ∗ := maxw∈P(X) min θ:a∗ (θ)̸=a∗ (θ∗ ) ∑k∈[K] wkKL (ν k θ , ν k θ∗ ), Dθ∗ := bound suggests a natural δ-PAC strategy in hindsight, namely, to sample arms according to the distribution Note however that x∗ is unknown a priori. [Fiez et al., 2019] design a strategy (RAGE) that attempts to mimic the optimal allocation w∗ in phases. In each phase m, RAGE tries to eliminate arms that are 2-m-suboptimal (compared to the empirical best arm), by solving (1) with a plugin estimate of θ∗ . The resulting fractional allocation, is passed through a separate discrete rounding procedure, to give an integer pull count distribution to ensure that all surviving arms' mean differences are estimated with high precision and confidence. This approach, however, is based crucially on solving minmax problems of the form (1). Though the inner (max) function is convex as a function of w on the probability simplex [Zaki et al., 2019, Lemma 1], it is non-smooth, and it is not clear how, and to what precision, it must be solved to satisfy the δ-PAC guarantee. using ideas from games between noregret online learners with optimism, as introduced in [Degenne et al., 2019] for unstructured bandits, we are able to sidestep this obstacle entirely. From Pure-exploration Games to δ-PAC Algorithms. We briefly explain some of the insights in [Degenne et al., 2019] that we leverage to design an explicit linear banditδ-PAC algorithm with low computational complexity. We consider the related geometrical optimization problem of fitting an ellipsoid inside a polygon, both centered at the origin, namely maxw∈PK minλ∈∪x∈Xm Cm(x) ∥λ∥2∑x∈X wxxxT , where Cm(x) is a union of halfspaces, defined in Alg. 1. By subsequently reducing the size of the polygon (i.e., value of εm in alg 1) we achieve a reduction in size of the confidence-ellipsoid. To this end, consider the two-player, zero-sum "pure exploration" game in which the MAX player (or column player) plays an arm kt ∈ [K] while the MIN (or row) player chooses an λt ∈ ∪x∈Xm Cm(x). MAX then receives a payoff of ∥λt∥2xkxTk from MIN. With MAX moving first and playing a mixed strategy w ∈ P(X), the value of the game becomes maxw∈PK minλ∈∪x∈Xm Cm(x) ∥λ∥2∑x∈X wxxxT . As shown in Appendix F, this quantity is directly related to 1/Dθ∗ . Table 1: Comparison of Sample complexities achieved by various algorithms for LMAB in the literature. Here, S denotes a bound on |θ∗ |2 and H0 is the solution to an offline optimization problem in LinGapE. | Algorithm | Sample Complexity | Remarks | |--------------------------------------------------|-----------------------------------------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------| | XY-static [Soare et al., 2014] | O( d ∆min (ln 1δ + lnK + ln 1 ∆min ) + d2) | Static allocation, worst-case optimal Dependence on d cannot be removed | | LinGapE [Liyuan Xu, 2017] | O(dH0 log (dH0 log 1δ )) | Fully adaptive, sub-optimal in general. | | ALBA [Tao et al., 2018] | O( ∑di=1 1 ∆2(i) ln ( Kδ + ln 1 ∆min ) ) | Fully adaptive, sub-optimal in general (see [Fiez et al., 2019]) | | RAGE [Fiez et al., 2019] | O ( 1 Dθ∗ log 1/∆min log ( K2 log2 1/∆min δ )) | Instance-optimal, but Minimax oracle required | | LinGame [Degenne et al., 2020] | O ( log 1/δ+K2 d√log 1/δ+S2 (log 1/δ)3/4 Dθ∗ ) | Requires knowledge of a upperbound on ∥θ∗ ∥2 Optimal lower bound is achieved only in the limit as δ ↓ 0 | | Lazy Track-and-Stop [Jedra and Prouti`ere, 2020] | O ( log(1/δ) Dθ∗ ) + o(log(1/δ)) | Asymptotically-optimal, but Minimax oracle required Instance-optimal, | | PELEG (this paper) | O ( log2 (1/∆min) Dθ∗ log ((log2 (1/∆min))2 K2 /δ)) | Explicitly implementable Does not require knowledge of ANY parameter that cannot be gleaned from the given arm set Access to minimax oracle not required. | We crucially employ no-regret online learners to solve this Pure Exploration Game. More precisely, no-regret learning with the well-known Exponential Weights rule/Negativeentropy mirror descent algorithm [Shalev-Shwartz and others, 2011] on the one hand, and a best-response convex programming subroutine on the other, directly provides a sampling strategy that obviates the need for separate allocation optimization and rounding for sampling as in [Fiez et al., 2019]. An advantage of our approach (inspired by [Degenne et al., 2019]) is that we only use a best-response oracle to solve for Tθ∗(w), which gives us a computational edge over [Fiez et al., 2019] who employ the more computationally costly max-min oracle to solve Tθ∗ (w), or, equivalently, Dθ∗ . ## 4 Proposed Algorithm and Sample Complexity Bound Our algorithm, that we call "Phased Elimination Linear Exploration Game" (PELEG), is presented in detail in Algorithm 1. PELEG proceeds in phases with each phase comprising multiple rounds, maintaining a set of active arms Xm for testing during phase m. A least squares estimate ̂ θm of θ∗ is used to estimate the mean reward of active arms and, at the end of phase m, every active arm with a plausible reward more than ≈ 2-m below that of some arm in Xm is eliminated. If we can ensure that Xm ⊂ Sm in every Phase m ⩾ 1, then PELEG will terminate within ⌈log2(1/∆min)⌉ phases, where ∆min = minx̸=x∗ θ∗⊤ (x∗ - x) . This statement is proved in Corollary 2 in the Supplementary Material. Note 1. The set XB in the input to Algorithm 1 is a subset of arms of cardinality d (value of ambient dimension), which is played during the burn-in period in each phase of the algorithm. We need to compute it only once offline in order to run the entire algorithm, and it is desirable to have λmin(∑x∈XB xx⊤) as large as possible. A principled way in which this subset can be chosen is, for instance, as a barycentric spanner of the arm set X , which can be computed in time O(d2 ) [Awerbuch and Kleinberg, 2008a]. Note 2. C = λmin(∑x∈XB xx⊤) can be interpreted as a measure of how much information arms give about each other. If the arms in XB are near-collinear, this eigenvalue will be very small and it is hard to transfer information across arms. Conversely, if the arms in XB are highly 'spread out' this eigenvalue will be large and sampling an arm will give more information about the best arm [Zaki et al., 2019]. Approximating the minimax problem using no regret learners. We formulate the minimax problem discussed in Sec. 3 as a two player, zero-sum game. We solve the game sequentially, converging to its Nash equilibrium by invoking the use of the EXP-WTS algorithm [Cesa-Bianchi and Lugosi, 2006]. Specifically, in each round t in a phase, PELEG supplies EXP-WTS (MAX player) with an appropriate loss function lMAX t-1 and receives the requisite sampling distribution wt . This wt is then fed to the second no-regret learner (MIN player) - a best response subroutine - that in turn returns a 'competing' model λ ∈ Rd (i.e., a model whose best arm is different but whose distribution is not too different) to focus on. This is a minimization of a quadratic function over a union of finitely many convex sets (halfspaces intersecting a ball) which can be transparently implemented in polynomial time. Once the sampling distribution is found, we use an efficient tracking procedure, from [Degenne et al., 2020] (see Lemma 6), to ensure that ∑ts=1 wk s - (logK) ⩽ nkt ⩽ ∑ts=1 wk s + 1 for every t ⩾ 1. This procedure avoids the need for explicit rounding techniques that plagues [Fiez et al., 2019]. Finally, in each phase m, we need to sample arms often enough to (i) construct confidence intervals of size at most ## Algorithm 1 Phased Elimination Linear Exploration (PELEG) Input: X (Arm set), XB (set of d arms to be played in the burn-in period), δ (probability of error). Init: m ← 1, Xm ← X . Output: Guess for the best arm. - 1: C ← λmin (∑x∈XB xxT ). 2: ˜ S ← √ dC . - 3: while {|Xm| > 1} do - 4: δm ← δ m2 . {Phase starts } - 5: εm ← ( 12 )m+1 . - 6: rm ← √8 log (K2 /δm). - 7: lm ← ⌈ r2m ˜ S2C ⌉. - 8: Cm(x) ← {λ ∈ Rd : ∃x′ ∈ Xm, x′ ̸= x| ↪→ λTx′ ⩾ λTx + εm}, for x ∈ Xm. - 9: t ← 0, nk0 ← 0, ∀k ∈ [K]. - 10: Play each arm in XB lm times and collect rewards. {Burn-in period} - 11: ∀x ∈ XB, ndx = l, V m dlm ← lm ∑x∈XB xxT , t ← dlm. - 12: Initialize AMAX m ≡ EXP - WTS with expert set {̂ e1, · · · , ̂ eK} ⊂ RK and loss function lMAX t-1 ().{MAX player: Exponential Weights} {Phase Stopping Criterion} - 14: t ← t + 1 - 15: Get wt from AMAX m and form the matrix Wt = ∑Kk=1 wk t xkxTk . - 16: λt ← argminλ∈∪x∈Xm Cm(x)∩B(0, ˜ S) ∥λ∥2Wt .{MIN player: Best response} - 17: for k ∈ [K] do - 18: U k t := (λTt xk)2 - 19: end for - 20: Construct loss function lMAX t (w) = -wTUt - 21: Play arm kt = argmaxk∈[K] ∑ts=1 wk s - nkt-1 {Tracking the play distribution provided by the MAX player} - 22: nkt t ←nkt t +1 - 23: Collect sample Yt = θ∗Txkt + ηt - 24: V m t = V m t-1 + xkt xkt T . - 25: end while - 26: Nm ← t - 27: ̂ θm ← (V m Nm )-1 (∑Nm s=1 Ysxks ) {Least-squares estimate of θ∗ } - 28: ̂ xm+1 ← argmaxx∈Xm ̂ θTmx. 29: Xm+1 ← {x ∈ Xm|̂ xm+1 -x) ⩽ 2-(m+2)} . { θTm(̂ Elimination of suboptimal arms } - 30: m←m+1. {Phase ends} - 31: end while - 32: return Xm {Output the sole surviving arm} 2-(m+1) around (x - x′ )⊤θ∗ , ∀x, x′ ∈ Xm, (ii) ensure that Xm ⊂ Sm and (iii) that x∗ ∈ Xm. In Sec. E, we prove a Key Lemma (whose argument is discussed in Sec. 5) to show that our novel Phase Stopping Criterion ensures this with high probability. It is worth remarking that the use of phased elimination template of [Fiez et al., 2019] eliminates the need to use more complex, self-tuning online learners like AdaHedge [de Rooij et al., 2014], as used in [Degenne et al., 2019] and more recently [Degenne et al., 2020], in favor of the simpler Exponential Weights (Hedge) algorithm. The main theoretical result of this paper is the following performance guarantee. A more detailed version is in Appendix. Theorem 1 (Sample Complexity of PELEG). With probability at least 1-δ, the worst-case sample complexity of PELEG, which we denote as τ , is bounded as where C1 and C2 are universal constants. We sketch the arguments behind the result in Sec. 5; the full proof appears in Appendix F. Note 3. As explained in Sec. 3, the optimal (oracle) allocation requires O ( 1 Dθ∗ log 1δ ) samples. Comparing this with (2), we see that our algorithm is instance-optimal up to logarithmic factors. ## 5 Sketch of Sample Complexity Analysis This section outlines the proof of the δ-PAC sample complexity of Algorithm 1 (Theorem 1) and describes the main ideas and challenges involved in the analysis. As described, the algorithm operates in phases, with the goal of the m-th phase being to eliminate, with high probability, arms which are roughly 2-m-suboptimal w.r.t. other surviving arms and hence whose reward gaps are at least 2-m. This can be guaranteed if all available arms (i.e., directions) are sampled sufficiently enough to reduce the uncertainty in estimating mean differences by about 2-m. To achieve such a sampling pattern, alternating no-regret learners are used in the central while loop which is terminated according to a phase stopping criterion (Step 13 of PELEG). At a high level, the proof of Theorem 1 involves two main parts: (1) a correctness argument for the phase stopping criterion that eliminates suboptimal arms, and (2) a bound for the length of the central while loop, which, when added across all phases, gives the overall sample complexity bound. 1. Uncertainty control along relevant directions. At the heart of the analysis is the following result which guarantees that upon termination of the central while loop, the uncertainty in estimating all differences of means among the surviving (i.e., non-eliminated) arms remains bounded. (a) After the burn-in period: The 2-norm of each vector in the blue ellipsoid is smaller than ˜ S. Its extent along (xi -xj) may exceed the gap between the hyperplanes (parallel black lines). ![Image](https://ijcai.org/proceedings/2022/fulltext/515/image_000000_f1b9350f738afc0a44812c80ae0bada6c9851b8d3fbb3bf0f6fa107f915413d5.png) (b) After end of phase m: The blue ellipsoid separates from the halfspaces intersecting the ball (red) by staying within the ball. In this case its extent along (xi - xj) is within the gap between the hyperplanes (parallel black lines). ![Image](https://ijcai.org/proceedings/2022/fulltext/515/image_000001_0b8b2452dc1045728e642493a35d4a86a47a1448360072054987cd9653c5a12d.png) Figure 1: The phase stopping condition in Algorithm 1 ensures that ∥xi - xj∥(V m t )-1 ⪅ 2-m after phase m. Remarks. In each phase m ⩾ 1, we have a burn-in period, where each arm in the set XB, is played lm number of times where lm is chosen carefully. At a high level the goal of the burn-in period is to ensure that the ellipsoid E(0, V m t , rm), becomes 'small' (see Figure 1a). More precisely, we ensure E (0, V m t , rm) ⊂ B(0, ˜ S). This step is crucial in the analysis, as it helps ensuring that the losses passed to the no-regret learners remain bounded. Lemma 2. For any phase m ⩾ 1, at the end of the burn-in period (line 10, in which each arm x ∈ XB is played lm := ⌈ r2m ˜ S2C ⌉ times), we have E(0, V m t , rm) ⊆ B(0, ˜ S). After this, the algorithm enters the while loop. Phase m ends at round t when the ellipsoid E(0, V m t , rm), with center 0 and shape according to the arms played in the phase so far, becomes small enough to avoid intersecting the half spaces Cm(x), for all surviving arms x, within the ball ∩B(0, ˜ S) (Phase Stopping Criterion of the algorithm) which is required to keep loss functions bounded for no-regret properties. We show a simpler situation in Figure 1b when there are only two arms xi, xj remaining when phase m starts. Cm(xi) ≡ Cm(xi; εm) and Cm(xj; εm) with εm ≈ 2-m are halfspaces, denoted in gray, that intersect the ball B(0, ˜ S) in the areas colored red. In this situation, the ellipsoid V m t , shaded in blue, has just broken away from the red regions in the interior of the ball. Because its extent in the direction xi -xj lies within the strip between the two hyperplanes bounding Cm(i), Cm(j), it can be shown (see proof of lemma in appendix) that ∥xi - xj∥(V m t )-1 is small enough to not exceed roughly 2-m. ## 2. Bounding the number of arm pulls in a phase. The main bound on the length of the central while loop (l. 13) is: Lemma 3 (Phase length bound). Let Bm := minw∈PK maxx,x′∈Xm,x̸=x′ ∥x - x′ ∥2W -1 , where W = ∑Kk=1 wk xkxTk . There exists δ0 such that ∀δ < δ0, the length Nm of any phase m is bounded as : To prove this we use the no-regret property of both the bestresponse (MIN) and the Exponential Weights (MAX) learners (the full proof appears in the Appendix D). Here we essentially approximate the saddle point minimax optimization problem Bm (mentioned in the above item) to a certain level of accuracy. The details of the MIN and MAX learners are deferred to Appendix B. Finally we use the concavity of the function t ↦→ √t to obtain the above bound on phase-length. Note 4. The careful choice of ˜ S (on line 2 of the algorithm) plays a crucial rule in the phase-length bound. It provides just enough exploration at the beginning of each phase, so that the regret of the online learning algorithm (i.e., AMAX ) is controllable, while not being too large to effect the sample complexity. Moreover, the minimum eigenvalue C = λmin (∑x∈XB xxT ) used by the algorithm does not affect the sample complexity when δ is small. More details can be found in Appendix Sec. D. 3. Correct elimination of sub-optimal arms at the end of each phase. Here we argue the progress made after every phase and the correctness of the algorithm. Let Sm := {x ∈ X : θ∗T (x∗ -x) < 1 2m }. Let B∗m := minw∈PK max(x,x′ )∈S 2m,x̸=x′ ∥x-x′ ∥2W -1, where W = ∑Kk=1 wk xkx⊤k . We show in Appendix (Sec. E) that with high probability, after the end of any phase m ⩾ 1, {x∗ ∈ Xm+1} and {Xm+1 ⊆ Sm+1}. To show this, we use the sub-Gaussian property of rewards obtained in every round, along with Lemma 1 which holds for every phase m ⩾ 1 and the elimination criteria (Step 29). We refer the reader to Sec. E for the details. We finally put these ingredients together, along with Prop 1 (in the appendix), to show the final sample complexity result (Appendix F). Figure 2: Sample complexity performance of LMAB algorithms for 3 different settings: Standard bandit (Figs. a, b), Unit Sphere (Fig. c) and Standard bandit with confounding arm (Fig. d). The means reported are computed over 30 trials with 1-standard deviation error bars. ![Image](https://ijcai.org/proceedings/2022/fulltext/515/image_000002_60d71dda4db2387a1a89df2e4442aa717c2a20729c7f6706392f4b486c5d096a.png) ## 6 Experiments We numerically evaluate PELEG against the algorithms XYstatic [Soare et al., 2014], LUCB [Kalyanakrishnan et al., 2012], ALBA [Tao et al., 2018], LinGapE [Liyuan Xu, 2017], RAGE [Fiez et al., 2019], Lazy-TS [Jedra and Prouti`ere, 2020] and LinGame [Degenne et al., 2020], for 3 common benchmark settings. The oracle lower bound is also calculated. In our implementation, we ignore the term B(0, ˜ S) in the phase stopping criterion; this has the advantage of making the criterion verifiable in closed form. We simulate independent, N(0, 1) observation noise in each round. All results reported are averaged over 30 trials. We also empirically observe a 100% success rate in identifying the best arm, although a confidence value of δ = 0.01 is passed in all cases. Setting 1: Standard bandit. The arm set is the standard basis {e1, e2, . . . , e5} in 5 dimensions. The unknown parameter θ∗ is set to (∆, 0, . . . , 0), where ∆ > 0, with ∆ swept across {0.1, 0.2, 0.3, 0.4, 0.5}. As noted in [Liyuan Xu, 2017], for ∆ close to 0, XY-static's essentially uniform allocation is optimal, since we have to estimate all directions equally accurately. However, PELEG performs better (Fig. 2(a)) due to being able to eliminate suboptimal arms earlier instead of uniformly across all arms. Fig. 2(b) compares PELEG and RAGE in the smaller window ∆ ∈ [0.11, 0.19], where PELEG is found to perform better than RAGE. Setting 2: Unit sphere. The arms set comprises of 100 vectors sampled uniformly from the surface of the unit sphere Sd-1 . We pick the two closest arms, say u and v, and then set θ∗ = u + γ(v - u) for γ = 0.01, making u the best arm. We simulate all algorithms over dimensions d = 10, 20, . . . , 50. This setting was introduced in [Tao et al., 2018], and PELEG is uniformly competitive with the other algorithms (Fig. 2(c)). Setting 3: Standard bandit with a confounding arm . As in [Soare et al., 2014], we instantiate d canonical basis arms {e1, e2, . . . , ed} and an additional arm xd+1 = (cos(ω), sin(ω), 0, . . . , 0), d = 2, . . . , 10, with θ∗ = e1 so that the first arm is the best arm. By setting 0 < ω ≪ 1, the (d + 1)st arm becomes the closest competitor. Here, the performance critically depends on how much an agent focuses on comparing 1st and (d+1)th arm. LinGapE performs very well in this setting, and PELEG is competitive with it (Fig. 2(d)). Note 5. In Setting 3, we empirically observe that at the time of stopping in the case of d = 2, wt(d + 1) ≈ 0. This is in accordance with the optimal allocation for the case when 0 < ω < π/2, as shown by explicit calculation in [Zaki et al., 2019]. More details can be found in Appendix G. Setting 4: Many arms with moderate gaps. This setting is similar to the 'many arms' setting in [Fiez et al., 2019]. We choose d = 2, with x∗ = θ∗ = (1, 0)⊤. The second arm, which happens to be the most informative arm, is chosen as (0, 1)⊤. The remaining K - 2 arms are chosen as (cos(π/6 + φ(j)), sin(π/6 + φ(j))) where each φ(j) ∼ N(0, 0.1), j = 1, 2, 3, . . . , K - 2. We choose K to be large : K ∈ {600, 700}. We compare PELEG with FWS [Wang et al., 2021] in this setting, and show the number of times each arm is pulled in both the cases. From [Zaki et al., 2019], it is known that it is optimal and sufficient to pull only the first two arms. This experiment shows that FWS wastes samples by choosing uninformative arms causing the performance to suffer. We set δ = 0.05, and the results are averaged over 30 trials each. Table 2: Average sample complexity performance of PELEG and FWS on Setting 4 (with 1-standard deviation). The second row shows that FWS wastes a lot of sample on unimportant arms even on relatively easier problems with moderate gaps. | K = 600 | PELEG FWS | PELEG FWS | |------------------------------------|-------------|-------------| | Sample Complexity | 4924 ± 156 | 7172 ± 567 | | # of samples of arms {3, . . . ,K} | 142 ± 49 | 2392 ± 74 | | K = 700 | PELEG | FWS | | Sample Complexity | 3744 ± 125 | 7760 ± 739 | | # of samples of arms {3, . . . ,K} | 656 ± 67 | 2792 ± 147 | ## Acknowledgments Mohammadi Zaki was supported in part by Microsoft Travel Grants, MS RESEARCH LAB INDIA PVT (Ref # 100316111), Aerospace Network Research Consortium (ANRC) Grant on Airplane IOT Data Management and ACM-India/IARCS Travel Grants. ## References 1. [Awerbuch and Kleinberg, 2008a] B. Awerbuch and Robert D. Kleinberg. Online linear optimization and adaptive routing. J. Comput. Syst. Sci., 74:97-114, 2008. 2. [Awerbuch and Kleinberg, 2008b] Baruch Awerbuch and Robert Kleinberg. Online linear optimization and adaptive routing. Journal of Computer and System Sciences, 74(1):97-114, 2008. 3. [Cesa-Bianchi and Lugosi, 2006] Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cam- bridge University Press, 2006. 4. [de Rooij et al., 2014] Steven de Rooij, Tim van Erven, Pe- ter Grunwald, and Wouter Koolen. Follow the leader if you can, hedge if you must. Journal of Machine Learning Research, 15:1281-1316, 2014. 5. [Degenne et al., 2019] Rémy Degenne, Wouter M. Koolen, and Pierre Ménard. Non-asymptotic pure exploration by solving games. In NeurIPS, 2019. 6. [Degenne et al., 2020] Rèmy Degenne, Pierre Mènard, Xue- dong Shang, and Michal Valko. Gamification of pure ex- ploration for linear bandits. Proceedings of the 37th Inter- national Conference on Machine Learning. PMLR, 2020. 7. [Even-Dar et al., 2006] Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Action elimination and stopping condi- tions for the multi-armed bandit and reinforcement learn- ing problems. J. Mach. Learn. Res., 7:1079-1105, Decem- ber 2006. 8. [Fiez et al., 2019] Tanner Fiez, Lalit Jain, Kevin G Jamieson, and Lillian Ratliff. Sequential experimental design for transductive linear bandits. In Advances in Neural Infor- mation Processing Systems, pages 10666-10676, 2019. 9. [Garivier and Kaufmann, 2016] Aurélien Garivier and Emi- lie Kaufmann. Optimal best arm identification with fixed confidence. In Conference On Learning Theory, pages 998-1027, 2016. 10. [Jedra and Proutière, 2020] Yassir Jedra and A. Proutière. Optimal best-arm identification in linear bandits. NeurIPS, abs/2006.16073, 2020. 11. [Kalyanakrishnan et al., 2012] Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. Pac subset se- lection in stochastic multi-armed bandits. In ICML, 2012. 12. [Kuroki et al., 2019] Yuko Kuroki, Liyuan Xu, Atsushi Miyauchi, Junya Honda, and Masashi Sugiyama. Polynomial-time algorithms for combinatorial pure exploration with full-bandit feedback. arXiv preprint arXiv:1902.10582, 2019. 13. [Liyuan Xu, 2017] Masashi Sugiyama Liyuan Xu, Junya Honda. Fully adaptive algorithm for pure ex- ploration in linear bandits. 2017. 14. [Shalev-Shwartz and others, 2011] Shai Shalev-Shwartz et al. Online learning and online convex optimiza- tion. Foundations and trends in Machine Learning, 4(2):107-194, 2011. 15. [Soare et al., 2014] Marta Soare, Alessandro Lazaric, and Remi Munos. Best-arm identification in linear bandits. Advances in Neural Information Processing Systems 27, pages 828-836, 2014. 16. [Srinivas et al., 2010] Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: no regret and experi- mental design. In In International Conference on Machine Learning, 2010. 17. [Tao et al., 2018] Chao Tao, Saúl Blanco, and Yuan Zhou. Best arm identification in linear bandits with linear dimen- sion dependency. volume 80 of Proceedings of Machine Learning Research, pages 4877-4886. PMLR, 2018. 18. [Valko et al., 2014] Michal Valko, Rémi Munos, Branislav Kveton, and Tomáš Kocák. Spectral bandits for smooth graph functions. In International Conference on Machine Learning, pages 46-54, 2014. 19. [Wang et al., 2021] Po-An Wang, Ruo-Chun Tzeng, and Alexandre Proutiere. Fast pure exploration via frank- wolfe. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Infor- mation Processing Systems, 2021. 20. [Zaki et al., 2019] Mohammadi Zaki, Avinash Mohan, and Aditya Gopalan. Towards optimal and efficient best arm identification in linear bandits. arXiv preprint arXiv:1911.01695, 2019.