Improved Pure Exploration in Linear Bandits with No-Regret Learning

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θ∗ .

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.

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).

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.

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.