Fixed-Budget Best-Arm Identification in Sparse Linear Bandits
Authors: Recep Can Yavas
Vincent Y. F. Tan
Venue: Accepted by TMLR ()

Abstract: We study the best-arm identification problem in sparse linear bandits under the fixed-budget setting. In sparse linear bandits, the unknown feature vector $\theta^*$ may be of large dimension $d$, but only a few, say $s \ll d$ of these features have non-zero values. We design a two-phase algorithm, Lasso and Optimal-Design- (Lasso-OD) based linear best-arm identification. The first phase of Lasso-OD leverages the sparsity of the feature vector by applying the thresholded Lasso introduced by Zhou (2009), which  estimates the support of $\theta^*$ correctly  with high probability using rewards from the selected arms and a judicious choice of the design matrix. The second phase of Lasso-OD applies the OD-LinBAI algorithm by Yang and Tan (2022) on that estimated support.  We derive a non-asymptotic upper bound on the error probability of Lasso-OD by carefully choosing hyperparameters (such as Lasso's regularization parameter) and balancing the error probabilities of both phases. For fixed sparsity $s$ and budget $T$, the exponent in the error probability of Lasso-OD depends on $s$ but not on the dimension $d$,  yielding a significant performance improvement for sparse and high-dimensional linear bandits. Furthermore, we show that Lasso-OD is almost minimax optimal in the exponent. Finally, we provide  numerical examples to demonstrate the significant performance improvement over the existing algorithms for non-sparse linear bandits such as OD-LinBAI, BayesGap, Peace, LinearExploration, and GSE.

Published in Transactions on Machine Learning Research (01/2024)
Fixed-Budget Best-Arm Identification in Sparse Linear Bandits
Recep Can Yavas CNRS at CREATE, Singopore
meep-ygrwas@errsaccrettt--
Vincent Y. F. Tan
vian Coreuss www.uueu.uuu.......
Department of Mathematics,
Department Electrical and Computer Engineering.
National University of Singapore
Reviewed on OpenReview: https: // openreview. net/ formm? id- Igap 7FC8uf
Abstract
Westudy the best-arm identification problem in sparse lincar bandits under the fixed-budget setting. In sparse linear bandits, the unknown feature vector may be of large dimension d, but only a few, say 8 < of these features have non-zero values. We design a two-phase algorithm, Lasso and Optimal-Design- (Lasso-OD) based linear best-arm identification. The first phase of Lasso-OD leverages the sparsity of the feature vector by applying the thresh- olded Lasso introduced by Zhou (2009), which estimates the support of O' correctly with high probability using rewards from the selected arms and a judicious choice of the de- sign matrix. The second phase of Lasso-OD applies the OD-LinBAl algorithm by Yang and Tan (2022) on that estimated support. We derive a non-asymptotic upper bound on the error probability of Lasso- OD by carefully choosing hyperparameters (such as Lasso's regularization parameter) and balancing the error probabilities of both phases. For fixed sparsity and budget T, the exponent in the error probability of Lasso-OD depends but not the dimension d, yielding significant performance improvement for sparse and nigh-dimensional linear bandits. Furthermore, we show that Lasso-OD is almost minimax optimal in the exponent. Finally, we provide numerical examples to demonstrate the signif- icant performance improvement over the existing algorithms for non-sparse linear bandits such as OD-LinBAI, BayesGap, Peace, LinearExploration, and GSE.
1 Introduction
The stochastic multi-armed bandit (MAB) is model that provides mathematical formulation to study the sequential design of experiments and exploration-exploitaaii trade-off, where a learner pulls an arm out of total K and receives a reward drawn from a fixed and unknown distribution according to the chosen arm. This model has several applications including online advertising, recommendation systems, and drug tests. While the standard reward model, the arms are uncorrelated with each other, stochastic linear bandits introduced in Aucr (2002) generalize the standard model by associating each arm with a d-dimensional feature vector and the reward is equal to the inner product between the feature vector and an unknown global parameter. Therefore, the arms are correlated in linear bandits, meaning that pulling arm gives information about the rewards of some other arms.
Most prior work including Auer (2002); Thompson (1933); Robbins (1952); Bubeck & Cesa- Bianchi (2012); Dani et al. (2008) on MABs focuses on regret mónémization, where the goal is to maximize the cumulative reward after arm pulls by optimizing the trade-off between exploration and exploitation. Recently, the pure exploration setting has drawn attention from researchers. One example pure exploration is the best- identification (BAT) problem, where the goal is to identify the arm with the largest mean reward. The

---

Published in Transactions on Machine Learning Research (01/2024)
BAI problem is studied in two settings: (1) the fixed- setting considers budget T E N and aims to minimize the probability of failing to identify the best arm in at most T arm pulls; (2) the fixed-confidence setting considers a confidence level ô E (0, 1) and aims to minimize the average number of arm pulls while identifying the best arm with probability at least 1-5.
For the standard reward model with uncorrelated arms, the works in Even-Dar et al. (2006); Karnin et al. (2013); Kaufmann et al. (2016) and Carpentier & Locatelli (2016); Audibert & Bubeck (2010) consider the BAI problem in the fixed-confidence and fixed-budget settings, respectively. For the linear model, the works in Soare et al. (2014); Xu et al. (2018); Fiez et al. (2019); Tao et al. (2018); Jedra & Proutiere (2020); Zaki et al. (2022) develop several algorithms under the fixed-confidence setting. For the linear model under the fixed-budget setting, Hoffman et al. (2014) develop the first algorithm, BayesGap, which is a gap-based exploration algorithm using a Bayesian approach. Ramuels et al. (2020) develop the Peace algorithm that has equally-sized rounds, where the arm-pulling strategy within each round is based on the Gaussian width of the underlying arm set. Alieva ct al. (2021) develop ExpearExpoooation that exploits the lincar structure of the model and is robust to unknown levels of observation noise and misspecification in the linear model. Yang & Tan (2022) develop the Optimal-Design- Based Linear Best Arm Identification (OD-LinBAI) algorithm, which also employs almost equally-sized rounds, but the arm-pulling strategy within cach round is based on the G-optimal design. In the first round, OD-LinBAI aggressively eliminates all empirically suboptimal arms except the top 2 arms; in the subsequent rounds, half of the remaining arms are eliminated in each round until a single arm remains. Azizi et al. (2022) develop the Generalized Successive Elimination (GSE) algorithm that has similar principles as OD-LinBAI with the difference that GSE eliminates the half of the remaining arms in all rounds. Among these algorithms, only OD-LinBAT is shown to be asymptotically minimax optimal.
d
In many practical applications of MABs, there are large number of features available to the learner, but only a few of these features significantly affect the value of the reward of an arm. Sparse linear bandits are a mathematical abstraction of this phenomenon by assuming that the d-dimensional unknown paramcter 0r in the linear model has only 8 nonzero values, i.e,, 100% = 8, where 8 is usually much smaller than d. The performance in the MAB problems (e.g., cumulative regret, probability of identification error) usually deteriorates as the ambient dimension d increases. Therefore, the goal in the sparse setting is to design an algorithm whose performance is function of s but not d. Some works that study the regret minimization problem for sparse linear bandits include Abbasi-Yadkori et al. (2012); Kim & Paik (2019); Hao et al. (2020); Oh et al. (2021);& Ariu et al. (2022); Li et al. (2022); Jang et al. (2022); Wang et al. (2023); Chakraborty et al. (2023). The OFUL algorithm of A Yadkori et al. (2012) keeps track of a high probability confidence set for 0" and pulls an arm that maximizes the reward with respect to the arm vectors and the confidence set for 0*. The DR Lasso algorithm of Kim & Paik (2019) combines Lasso with a doubly-robsst technique used in the missing data literature. The ESTC algorithm of Hao et al. (2020) uses Lasso to estimate 0* at the end of the first phase and then in the second phase commits to the best arm with respect to the Lasso estimate. The SA Lasso Bandit algorithm of Oh et al. (2021) estimates 0 at each time using Lasso and pulls the best arm with respect to the Lasso estimate. TH Lasso Bandit algorithm of Ariu et al. (2022) estimates the support of 0" using Lasso and a thresholding procedure at each time and pulls the best arm with respect to the ordinary least squares estimation restricted to the estimated support in the first phase. Li et al. (2022) generalize the ESTC algorithm of Hao et al. (2020) to general bandit problems with low-dimensional structures such as low-rank matrix bandits. The PopArt algorithm of Jang el al. (2022) takes the population covariance of arms as input and uses a thresholding step to estimate 0* in the first phase; in the second phase, it commits to the best arm with respect to the estimate of 0* in the first phase. The et al. (2023) combines the thresholded Lasso with random projection where random projection is used to mitigate the negative influence of model misspecificat ion due to the Lasso phase; their algorithm is also computationally efficient since Lasso is computed only at times with exponentially increasing gaps. Finally, Chakraborty et al. (2023) develop a Thompson Sampling algorithu for sparse linear contextual bandits.
algorithm of Wang
In this paper, we study the BAT problem in sparse linear bandits under the fixed-budget setting. To the best of our knowledge, this paper presents the first result on the BAI problem in linear bandits with sparse structure, and we show that our bound on the error probability is almost minimax optimal in the exponent.
2

---

Published in Transactions on Machine Learning Research (01/2024)
Contributions Our main contributions are summarized follows.
1. We design an algorithm, Lasso and Splimal-Desight (Lasso-OD) based Linear Best Arm Identifica- tion. This algorithm has two phases. In the first phase, we pull arms to estimate support set S that captures the support of the unknown parameter 0" with high probability and has size as small as possible. This goal is accomplished by the thresholded Lasso (TL) introduced by Zhou (2009). TL obtains an initial estimation Mitt for the parameter O" from Lasso (Tiibshirani, 1996) and passes through an absolute value threshold to obtain Óthres- The support of Oehres is the output of the first phase. In the second phase, we apply OD-LinBAI from Yang & Tan (2022). Lasso-OD has 3 hyperparameters: (i) Ti < T, the budget allocated for the first phase; (īi) Xinit > 0, the parameter in the initial Lasso problem; and (iii) Xthres > 0, the threshold value in TL. The choice of the design matrix (i.e., number of times each arm is pulled) in the first phase is crucial in attaining a good performance. Inspired by Hao et al. (2020), we design it by maximizing the smallest eigenvalue of the Gram matrix associated with the design matrix; this is known as the E-optimal design (Boyd & Vandenberghe, 2004, Sec. 7.5.2). This particular choice minimizes an upper bound on a probability term related to the performance of TL.
We derive a non-asymplotic upper bound on the error probability of Lasso-OD as a function of the total budget T, the number of arms K, the ambient dimension d, the sparsity s, and the arm vectors a(k), k k= 1,...; K, the first few suboptimality gaps, and the hyperparameters Ti, Ainit, and Athress As corollary to this bound, with the knowledge of 8, we carefully choose the hyperparamelens so that firstly, with high probability, phase 1 selects all variables in 0" and at most 8² additional variables and secondly, the probability terms due to phases 1 and 2 are approximately "balanced". Under the assumption that the compatibility constant, which is a quantity that governs the performance of the Lasso, is lower bounded by a constant. that independent 8 and d, our particular choice achieves the error probability exp { 4 -5( [Tora s) a) } for s, d, T - 00, å -,0, 0, and K and d not growing exponentially with T (see Corollary 1). Here, H2,um + s²) is hardness parameter that depends only on the first + s² - suboptimality gaps. Note that the exponent is independent of dimension d, implying that increase in d does not siguificantly increase the error probability. For OD-LinBAI, this exponent is given by exp { 2 [Tog22 d]H }; therefore, Lasso-OD ODD improves the error probability exponent by a factor of 2 d for d 2 s +
T
3.
We empirically compare the identification error of Lasso-OD with that of other existing algorithms in the literature on several synthotic datasets, including one that is a sparsity- used in other papers (Jedra & Proutiere, 2020). The empirical results support our theoretical result that claims that the scaling of the error probability of Tasso-OD is characterized by the sparsity while the performances of other algorithms significantly depend on d. We additionally demonstrate that algorithms that do not exploit the sparsity of 6' are computationally prohibitive, while the computational complexity of Lasso-OI scales well even as d grows.
version of examples
2 Problem Formulation
We consider a standard linear bandit with K arms with a d-dimensional unknown global parameter 0-. Let the arm set be [K] & (1..... .....,,K K}. where each arm & E [K] is associated with a known arm vector a(k) E Rd. A set of K arms, (a(1)..... a(k)), logether with 0* define a linear bandit instance ry. At each time I, the agent chooses an arm A, [K] and observes a noisy reward
y, (0", (0",a(AA)) a(A))) + Ct.
(1)
where E1, ...... are independent 1-subgaussian noise variables. For the arm selection, the agent uses an online algorithm, that is, the arm pull A, E [K] may depend only on the previous t t- 1 arm pulls Ay...., A,-1 and their corresponding rewards N1--- Denote the mean rewards of the arm vectors by
p4 P (0", a(k)), Vk E [K].
(2)
3

---

Published in Transactions on Machine Learning Research (01/2024)
Without loss of generality, assume that b1 μ2 A3 2 2 Mx, i.., arm 1 is the unique best arm. We denote the mean gaps by A _ jn1 Pi for 2 s k K.
Under the fixed-budget setting of BAI, the agent is given a fixed time T, and makes an estimate for the best arm with no more than T arm pulls. The goal is to design an online algorithm with the identification error probability, TP[ * 1], as small as possible.
Notation: For any integer n, we denote [ri] - (l) Let x (x), (Z1,..., Fdl be a d-dimensional vector and S S [d], we denote ass _ (Iz 8 E S) RR.S), We denote || - Vo. Av.. The minimum eigenvalue of symmetric A is denoted by Tmin (A). We denote the set of distributions on the set A as P(A). Let A1,...,Ae A. E [K] be sequence of arm pulls. The matrix X Rxtd whose j-th row is a(A,) T is called the design matria. Let P([]]) be the vector of fractions of arm pulls associated with this strategy, I.C., 1/= = E 1fA }}} for & E [K]. The Gram matric associated with this strategy is denoted by M(v) = x X ExEIK (aa())a(k) E Rdddd When we use asymptotic notation such as O(-) and ())), somewhat unconventionally, we are reforring to nonnegative sequences, c.g., an E O(b,) if and only if lim supn-+00 au < oo and (an]a21 nonnegative sequence. by
Model assumptions: Denote the support of 0" by S(0)) A (j E [d]: + 0}. We assume that the unknown parameter 0 and the arm vectors (a()))=ej]) [] are of length d but 0 is sparse, i.e, the number of non-zero coelficients 0 salisfies |10"1lo _ [S(0)) = a < d. We assune that S(0)) is unknown, but s and oann - minjes(e-) [07] are known. We further assume that l I for all arms k E [K] and that there exists positive constant 0g independent of s and d such that Ownn 2 0g.
3 Our Algorithm: Lasso-OD
We now present our algorithm, Lasso and Optimal-Design (Lasso-OD) based linear best-arm identification which has two phases. In phase 1, we pull judiciously chosen set of arms to learn the support of the unknown parameter l" Specifically, support S captures the true variables, S(0*), with high probability, and its cardinality [8] is small. To do this, we use the thresholded Lasso introduced by Zhou (2009). Once S is obtained, we eliminate all variables in the arm vectors except the ones in S. Note that given that $ 2 2S(0"), this variable elimination would have no effect on the mcan values f1...., PK since by assumption, we only climinate some variables j E [d] with 0j 0. Therefore, the best arm is also preserved after variable elimination. Building upon this principle, in phase 2, we project the arms on the estimated support S and pull arms according to the OD-LinBAI algorithm by Yang & Tan (2022), which is designed for linear bandits without the sparsily assumption.
design phase so that it outputs subset of variables S C [d] whose
3.1 Motivation for Lasso-OD Algorithm
OD-LinBAl used in phase 2 is a minimax optimal algorithm up to a multiplicative factor in the exponent
in the sense that achieves an asymptotic error probability exp { 2 [Tog 2)H2maaa)) ) } and for every
algorithm, there exists bandit instance v) whose asymptotic error probability is lower bounded by exp {
( [log, d)H (4j) The hardness parameter
H (d) A max
(3)
25ied A?
determines how difficult to identify the best arm for a given bandit instance 1) (Yang & Tan, 2022). For sparse linear bandits, if an oracle knew the support of the unknown parameter 0*, then the lower bound in Yang & Tan (2022, Th. 3) would be improved to exp {- 0( [Tog
T { )} The purpose of TL in phase 1 is to provide an estimate for the support of 0 with high accuracy while also pulling arms few enough that the resulting error probability is a function of s rather than d as in the oracle lower bound. Below, we provide the details on two phases of Lasso-OD.
4

---

Published in Transactions on Machine Learning Research (01/2024)
3.2 Phase 1 (TL)
Consider linear model y X0 +6, where X TRT is a fixed design matrix, 0 Rd is a fixed unknown feature vector, y R2's is the response vector, and E IR' is noise vector whose entries are independent and I-subgaussian. Tibshirani (1996) introduces the Lasso optimization problem to identify a sparse solution to the least squares estimation problem
Init
arg min DER"
Ti - x011 Ainit |0]1
(4)
where Amnit > 0 is a suitably chosen regularization parameter. The Lasso (4) is a convex program and can be solved efficiently, e.g., using Alternating Direction Method of Multipliers (ADMM) algorithm (Boyd et al., 2011).
For the task of variable selection, Le., recovering the support of the unknown parameter 0" without missing any of its non-zero variables, we want to obtain estimate Ô that satisfies S(Ō) 2 S(0*) while ensuring that (S(0) ((())) is small possible. Zhou (2009) introduces the following thresholding procedure that has this property
(Othres) = (0mi)) 1 (((Omms)))) Athrea,
Vj E [d],
(5)
where the initial estimate Oiit is given in (4), and Athres >> 0 is the threshold. The set of selected variables by TL is S(Othres). A variation of TL is used by Ariu al. (2022) derive refined regret guarantees in sparse stochastic contextual linear bandits. Their main idea is to find the support estimate S( at each time instance t using TL and then to compute the ordinary least squares (OLS) estimation restricted on the variables in S(O()) thres) ). Ariu et al. (2022) tune the free parameters A and x(e) in way that with high (1)
) 2 S(0") and ((O(() threa) is small enough, which is + O(v²) in their case. Note that on the event {S(0()) thres) S(0)),, the OLS solution restricted on the subset ((é(t) thres) is equal that for the unrestricted case where all d variables are used. Our approach is similar that in Ariu al. (2022) in using TL to reduce the effective dimension of the problem.
probability, S( thres
Let Ti < T be the budgel allocated to the variable selection procedure described above.
Design matrix optimization First, we need to specify the number of pulls for each arm during phase 1, which corresponds determining the design matrix X R in the Lasso problem (4). To do this, we solve the optimization problem, known as the E-optimal design (Boyd & Vandenberghe, 2004, See. 7.5.2),
given by
K Σ vr(())(()))
8'' = arg max Oinn NEP((K)
(6)
Since the function A + min (A) is concave and 4 E (aa())a(iiTT is linear, (6) is a convex optimixation problem, and can be solved efficiently, for example, using the CVX toolbox (Boyd et al., 2011).
The design matrix determined by the allocation in (6) minimizes an upper bound on a probability term related to phase 1; hence, approximately optimizes the penalty term due to incorrectly estimating the variables of 0* More discussion on this choice of the design matrix appears in Appendix The optimization problem (6) also appears in Hao et al. (2020) on their regret analysis in sparse linear bandits. The allocation i² can lead to fractional number of pulls Ti for some arm i [K]. To guarantee integer number of pulls for all arms, apply rounding procedure given in Pukelsheim (2006, Ch. 12), the ROUND function in Appendix B, which is also employed in the fixed-confidence BAI algorithm in Fiez et al. (2019).
Support estimation We compute the number of pulls for each arm using (6) and ROUND, and then estimate the support from (4) and (5). Algorithm 1 below delineates the pseudo-code of this procedure.
5

---

Published in Transactions on Machine Learning Research (01/2024)
Algorithm Thresholded Lasso (TL)
input Time budget Tí, Lasso parameters Xinit and Athres, and arm vectors a(1)...., a(K).
1: Compute the arm pull fractions i' from (6).
2: Update 1/* + ROUND( Ti)) to ensure integer number arm pulls.
Pull each arm E [K] exactly T times. Denote the vector of rewards by y E R
4: Form the design matrix X E I xd so that it has Ti2 rows equal to a(i) for i [K]. Compute Othres from (4) and (5).
output the support S = ((fthr)))
3.3 Phase (OD-LinBAI)
In this section, review the OD-LinBAI algorithm by Yang & Tan (2022). OD-LinBAI divides the budget T into [log2 d| phases, where each phase has roughly the same length.
At the start of round т, OD-LinBAl applies a dimensionality reduction step to maintain that the set of modified arms spans the space of its reduced dimension. The arm allocation during each round is determined by the G-optimal design (Kiefer & Wolfowitz, 1960), which takes set arm vectors (., a(K) C gd and solves the optimization problem
arg min max *EP((K) (E[K]
|a())|
where ((T) & ΣK Tia())(i)TTT is the Gram matrix associated with the allocation æ. At the start of each round, we solve (7) for the set of active arms and then apply the ROUND function Appendix B to the resulting allocation to ensure integer number of pulls. The latter step replaces the procedure in Line 17 Yang & Tan (2022, Algorithm 1). This slight modification may improve the performance of the algorithm especially if the budget T is small. At the end of round we climinate all arms except the top [ with respect to the OLS estimator; in the rest, we halve the remaining arms at the end each round. At the end of the last round, only one arm remains and that arm is declared to be the best one. The pseudo-code of OD-LinBAT can be found in Yang & Tan (2022) and a slight modification of it which loads to the improved error probability bound in Theorem 2 can be found in Appendix B.
3.4 Lasso-OP OD Algorithm
The pscudo-code of Lasso-OD described above is given Algorithm 2. Notice that since the two phases of Lasso-OD operate independently, one can replace either or both of and OD-LinBAl with their alternatives, e.g.; the PopArt algorithm (Jang et al., 2022) and the adaptive Lasso (Bühlmann & van de Geer, 2011, Ch. 2.8) for TL and any of the algorithms in Alieva et al. (2021); Katz-Samuels et al. (2020); Azizi et al. (2022); Hoffiman et al. (2014) for OD-LinBAL. We discuss some of the variants of our algorithm in Appendix G.
Algorithm 2 Lasso and Optimal-Design Based Linear Best Arm Identification (Lasso-OD)
input. Time budgets Ti and T2 so that T Ti + T2, Lasso parameters Vinit. and Aehres, and arm vectors E iRd.
Run TL (Algorithm 1) with Ti, Ainit, and Aehres and get the output $ C [d]. Project the arm vectors the subset S by setting a' ai(i) (a(1)) for E [K]
3: Run OD-LinBAI from Yang & Tan (2022) with budget T, and arm vectors with Line 17 Algorithm 1 in Yang & Tan (2022) replaced by ROUND. output the only remaining arm as the output of OD-LinBAI.
c g

---

Published in Transactions on Machine Learning Research (01/2024)
4
Main Results
This section presents three non-asymptotic upper bounds on the performances of TL, OD-LinBAI, and Lasso-OD algorithms.
4.1 Thresholded Lasso
Recall the linear model y = X0* te, where E R xd is fixed design matrix, 0 E R is a fixed unknown feature vector, y E RR: is the response vector, and E TR noise vector whose entries are independent and I-subgaussian. For any set S S [d], define the set of vectors
C(S) {0 E |00 s <310sl11
(8)
van de Geer & Bühhmann (2009) introduce the following compalibillyy condition that allows one to control the f--ormm error for the sparse estimation of the unknown parameter 0 where the components of the design matrix X are not highly correlated. For the rest of the section, let M = x X denote the Gram matrix associated with
Definition 1 (Compatibility condition). Given fired design matrir X E Rixx (whose Gram matrix is Mj and subset S S [d], the compatibility constant x² (M, S) is defined as
S |
8² (M,S)
min
C(S)
(9)
BER
10sll,70
|0ss1
With some abuse of notation, also define
2² (M,
min d² (M, sgld: [S|=s
(10)
The following result controls the f-norm error of the initial Lasso estimator in (4).
Lemma 1 (Ariu et al. (2022), Lemma G.6). Assume that (M, > 0. The Lasso estimator O in (4) satisfies
4Aini ]
Ti A
0mit -an 0. 5 P
d² (M, 21 - -ddexp
(11)
32
max jE(d]
X
Using Lemma 1, we derive the following bound on the event that the size of the support of the TL output (5) is below a threshold and it captures the true support S(0*).
Theorem 1. Fix design matric X Rixix and paramelers Ainits Aehres >>
Let
Atasaa Arat
Assume that
2 A (M, 8) > and Omin 2 Ainit + ) holds. Then,
S (((@hree)) S s1+
) ) ( (SS( s(0*)) 2 21-1 2dexp ge
(12)
32
max T.
X
jEld
The proofs of Lemma and Theorem are deferred to Appendix C. Theorem follows stops similar those in Ariu al. (2022, Lemma 5.4). The interested reader can refer to Bühlmann & van de Geer (2011, Ch. 6 and 7) for more results and discussions Lasso, TL., and their variants.

---

Published in Transactions on Machine Learning Research (01/2024)
4.2 An Improved Upper Bound the Error Probability of OD-LinBAI
The theorem below gives an improved upper bound on the error probability of OD-LinBAI (Yang & Tan, 2022).
Theorem 2. Let T Tog, di
For any linear bandit instance, the output of OD-LinBAl satisfies
T
p +1 S (K + logg d) exp
(13)
16 (1 + H2amld)
The right-hand side of (13) slightly different than the one presented in Yang & Tan (2022, Th. 2). First, in Yang & Tan (2022, Th. 2), the numerator in the exponent is equal to some constant that is approximately equal to log. just like T: this is due to the modification in the distribution rounding technique. Second, the pre-factor in Yang & Tan (2022, Th. 2) is 4K d 3 instead of (our smaller) K +loog d. More importantly, in (13), the constant 32 in the denominator of the exponent in Yang & Tan (2022, Th. 2) is improved to 16. The last two differences are due to a refinement in the proof technique. Lastly, our result includes a rounding error factor 1 + Tr which becomes negligible as T becomes large. This factor appears due to the fact that the G-optimal design may yield fractional number of pulls for some arms, which is obviously not allowed in practice. The proof of Theorem is deferred to Appendix D.
T
4.3 Upper Bound on the Error Probability of Lasso-OD OD
The theorem below bounds the probability of incorrectly identifying the best arm using Lasso-OD.
Theorem 3. Let Ti < T be the length of phase 1, and let T2 = - be the length of phase Let Ainit and Athres be some positive scolars. Let c= Aahres, Let ir be the solution to (6), and let ROUND Tı) drig
be its rounded version for length TT- Assume. that the compatibility constant associated with the F-optimal design is positive, i.e., 8² a 6² (ER Dra(i)a(i)), ,s) O, and Omnn 2 Ainit (c+ ()). Then, the output of Algorithm 2 salisfies
P
[ + s (K loga d) exp exp
{
Lopg
+ 2d 2d
Ti
(14)
16 16 + <) H2 (81)
32r2 m2x
where
s (1+
sf T2
$1
0²c
x.2 m
max jEId
D& (a()))))
and
(15)
Proof. The proof uses Theorems and 2 for the probability terms due TL and OD-LinBAT, respectively. Let S C [d] denote the output of phase Define the events & (IS] I s1} and F 2 (8 2 S(0)). By the law of total probability, we have
IP i <P i 11 +P[EFF] [
(16)
Given ENF, the error probability is bounded by the right-hand side of (13) with the budget T replaced by the length of phase 2, T2, and with the dimension replaced by 81- This follows since on the event F. the mean rewards are preserved after the arm vectors and 0* are projected on & and since the right-hand side of (13) non-decreasing in d. From Thcorem 1 and the arm-pulling strategy described in Line of Al Algorithm we have
{
Ti Ti
UFF & 2d 2dexp
(17)
32x22 Max
Combining (16) with (13) and (17), we complete the proof.
8

---

Published in Transactions on Machine Learning Research (01/2024)
The following corollary is obtained by choosing the free parameters T1, Ainit and Athres suitably to meet the conditions of Theorem 3. These nontrivial choices use the knowledge of Omin and 8 but not the hardness parameter and achieve an exponent of the error probability that depends only on T, and the hardness parameter.
Corollary 1. For any linear bandil instance that salisfies x² 0, the oulput of Algoritlom salisfies
PP 1 +1| s SK + log2 d + 2d) exp {
T
(18)
[66[log2( + 82 H2, (s s²)(1 co)
where
400 2 co 30402 min loga(s + s2)
(1 (1+ co) + 82)2
max
and
(19)
Here, co = 1/2 the fraction of lengths of two phases of Lasso-OD, and 1 + e is the small multiplicative penalty due to rounding.
Assume that for sequence of bandit instances (of growing dimension d), there exist positive constants Φi and zÿ. both independent of and d, such that x² 2 o and = S xgg A paradigmatic example of this is the scenario where the arm vectors are generated independently from a zero- mero-mean, unit-variance distribution with a finite fourth-order moment (e.g., the Gaussian distribution N/ 1), equiprobable distribution on {-1, Now, consider the setting in which K = Tı = rd where r > 1 is independent of s and d, and we pull each arm once in the Lasso phase. Then, from Bai Yin (1993, Theorem 2), we know that the minimum eigenvalue of the Gram matrix mmin (M) converges to (1- )² with probability one, and 2 converges to also with probability one. For this example, we may take the constants o and zn be Φi = - ) and = = 2. Note that, for this example, of and z are independent of and d. Therefore, the ratio co is 0(1) as d, and T grow. Under these conditions, Corollary 1 implies that the error probability of Lasso-OD is upper bounded by
exp { -
T
(1og 8) H2 (i + 52)
(20)
for 8, T + and K and d not growing exponentially with T, all of which are realistic assumptions in practice. Unlike the non-sparse case in Yang & Tan (2022), the error probability exponent under these assumptions is independent of the dimension d, but instead, depends the sparsity s, which yields much smaller error probabilities for high dimensional sparse linear bandits. The choices of the parameters that achieve the exponent in (20) is nontrivial; we carcfully choose Ainit and Attres so that the condition in Theorem 1 is satisfied with equality and ep is decreasing in s and choose Ti so that two exponents in (14) resulting from phases 1 and 2 are approximately equal. The proof of Corollary is presented in Appendix E.
Assume that the agent knows the support of 0*. Then, following the construction the proof of Yang & Tan (2022, Th. 3), for any algorithm, there exists bandit instance whose error probability is lower bounded by exp - (ToR Ho)) }. This implies that the upper bound in (20) is indeed almost minimax optimal in the exponent. In Appendix G, we develop a variant of Lasso-OD, callod PopArt- which replaces TL in phase 1 of Lasso-OD with PopArt from Jang al. (2022). Thanks to the fact that PopArt provides guarantec on the foo norm of the difference between the estimated parameter 0' and 0*, we derive an upper bound on the probability P SAA * S(0'). where SpA denotes the estimated support using the PopArt algorithm. Using this bound, we show that the error probability of PopArt-OD is upper bounded by exp - ② (log, )) matching the lower bound up a constant factor in the exponent. Due its superior empirical performance over PopArt-OD, we focus on Lasso-OD in the paper.
T
T
In general, x² depends on the geometry of the of vectors. One can construct instances where d vanishes and grow.
9

---

Published in Transactions on Machine Learning Research (01/2024)
2.
10, K 50, Hoa 727.05
2.
20, K 50. He
10549.55 53
0.4%
probebiitt
probebiity
0.
0.3
0.
0.-
0.1
0.1
10
10
10
2.
10, R 100, (ay 1760.6
2. d 20. K
100. M9 (4) 11991
probabilty
grobabiliy
0.4
0.3
02
10
10
10
T'
Lecu CD-CV
Lasso Asss--O-Amillical
O0-LiBA
Bayso Adipiiee
GSE
Figure 1: Comparison of several algorithms with T E [200, 10000] and s = 2.
Table 1: Performance comparison of several algorithms for T= 800, d 10, 50, and
Lasso-OD-CV
Lasso-OD-AN
Peace
LinearExploration
Error probability 0.0275
0.045
0.40
0.39
Std. deviation
0.0026
0.0033
0.049
0.0153
5 Experiments
In this section, we numerically evaluate the performance of Lasso-OD on several synthetic sparse linear bandit instances and compare it with those of OD-LinBAT (Yang & Tan, 2022), BayesGap (Hoffman et al., 2014), GSE (Azizi et al., 2022), Peace (Katz-Samuels et al., 2020), and LinearExploration (Alieva et al., 2021). In each setting, we report the empirical error probabilities for Lasso-OD, BayesGap, and GSE over 4000 independent trials and for Peace and LinearExploration over 100 independent trials.
5.1 Synthetic Dataset with Sparse Unknown Parameter Vector
To illustrate the efficacy and robustness of our algorithm synthetic data, consider three different sets of experiments.
In the first example, we draw K arms independently from the uniform distribution on the d-dimensional sphere radius /d/s, i.e., {a E Rd: ||~|| = 2) and the sparse unknown parameter is taken as 0" = 1,,1,0, 0, .0.....,)) 0), i.e., 8 2. Figure 1 reports the empirical error probabilities for d E (10, 20), K E (50, 100) and T E [200, 10000], except Peace (Katz-Samuels al., 2020) and Exploratonn (Alieva al., 2021). Since the computational complexities of Peace and algorithms, compare Lasso-OD with Peace and Linear Exploraton only for T 800 in Table 1. Among these algorithms, Lasso-OD has the best performance for all sparse instances shown in Figure I and Table 1.
much higher than the rest of the
OD-SO sets the budgets for phase and phase as Ti o and T/ = 4T and tunes the Lasso parameters Anni and A using K-fold cross-validation procodure that uses the value of s its loss function. See Appendix F for the details of the vols-vaaliotion procedure. As an alternative to cross- validation, Lasso-ODD-Anllticcl uses the knowledge of 8, Omin, and the hardness parameter (2in(()) in (14),
5
10

---

Published in Transactions on Machine Learning Research (01/2024)
- 2.4- 10, R 50, T- 800
5- 2.
10, R. 50, 2000
0.8
0.8
Eroo grobabdily
Enror arobabiiity
0.8
0.4
0.4
0
0.006
0.01
0.016
0.02
0.025
0.005
0.01
0.015
0.00
0.025
C0
0D
Figure 2: Comparison of several algorithms with T 1800,,2000) 2, and 8 e [0, 0.055..
d' 500, Hasald) 911.66
0.4
0.35
Engr grobaliyyyy
0.25
0.29
0.05
101
10
Figure 3: Comparison of Lasso-OD, OD-LinBAL, and GSE for d = 500, s = 4, and T E [3 x 10 3 x 10"].
and sets Amit. Athres, and Ti so that 81 in (15) equals s + s², 0min = (c bs), and two exponents in (14) are equal. Note that H2,n((8) is usually not available the agent.
In the second example, lest the robustness of our algorithm with respect to the variables in 0" that are assumed to be zero by keeping the same arms in the previous example and setting 0 as 03 1 for j [2] and 0j RR for E {3.... .3.....e d), where Rj, j = 3,..., d, independent Rademacher (i.e., valued) random variables, and 8 > 0 is a constant. Figure 2 reports the empirical error probabilities for = 2, d == 10, = 50, T E {800, 2000), and E [0, 0.025). The phase transition for Lasso-OD in Figure 2 suggests that Lasso-OD achieves a smaller error probability as long as is small enough that the approximately sparse instance (i.c., > 0) and the sparse instance (i.c., 5 0) have the same best arm. Some examples including an instance where the hyperparameters are set as in Corollary 1 without valssvaniiation or knowing the hardness parameter discussed in Appendix G.
The third experiment is similar to the first, except that the parameters are larger to demonstrate that our method scales well, while others do not. Namely, we set = 4, d = 500, and K = 1000. Since only Lasso-OD, OD-LinBAI, and GSE are the only computationally feasible algorithms for such large dimensions, we only include the performances from 4000 independent. trials for Lasso-OD and from 100 independent trials for OD-LinBAT and GSE. We observe that Lasso-OD outperforms OD-LinBAl for this instance at all T' values shown.
these algorithms in Figure
The empirical error probabilities are obtained
5.2 RerldWorld Dataset with Sparse Unknown Parameter Vector
We conduct an experiment on an online news popularity dataset published by Mashable (Fernandes et al., 2015), which includes 39,797 news articles, each having 58 attributes. Some of these attributes are the
We smaller number independent trials OD-LinBAT and GSE takes too long to run since does exploit the spansity of the problem.
11

---

Published in Transactions on Machine Learning Research (01/2024)
Enor Sty
0.8
Erorp
04
02-
107
10
107
2 10, K 100L (. 106425
2.4 30. N 100, (4) 1200.43
0.0
0.0
9.6
0.4
0.2
Loaa
Lina KY
Pap
Bapo
Figure 4: Comparison of several algorithms for the example bandit instance in Yang & Tan (2022).
0.7
0.8
Enor grobasiits
0.5
0.4
+
10a
10
ORIKRA L0000DD
ReyesTop
Figure 5: Comparison of several algorithus for the real-world dataset with 100), =3, and d 55.
number of words, the number of links, the number of keywords, the day that the news is published, and the channel of the news. The target of the dataset is the number of shares in social network. To adapt the dataset to the sparse linear bandit framework, we first normalize each attribute (and the target) so that the mean and the standard deviation of each attribute is 0 and 1, respectively. Since three of the attributes have > 99% correlation with some other attribute, we remove these three attributes; hence the overall dimension 55. Then, to obtain a sparse ground truth vector E R5 (assuming lincar model between the attributes and the larget), we estimate 0* using the thresholded Lasso, where the hyperparametens Ainit and Atree are determined via validatii. The resulting 0* has 3 nonzero values, hence 3 (all 3 active attributes are related to the number of keywords in the news). We select 500 news articles with the largest shares as the arms, i.e., K = 500.
In Figure 5, we see that Lasso-OD, where its two hyperparameters Amit and Athres are determined by cross- validation, has the smallest error probability for all T values shown. We are not able to conduct experiments using Peace and LipearExnoooation due to their prohibitively high computational complexities for such large dimensions. To corroborate this claim, the CPU runtimes of the algorithms compared in the experiments
12

---

Published in Transactions on Machine Learning Research (01/2024)
Table 2: The empirical means of the CPU runtimes for d E (10, 500) and 7 = 10*.
CPU runtimes (scconds)
Lasso-OD
OD-LinBAI
GSE
BayesGap-Ad.
LinoarExploration
Peace
10
0.0019
0.0084
0.011
0.75
2.33
31.69
55
0.0068
0.048
0.092
83.2
> 1800
>180
500
0.017
4.95
5.29
>> 1800
>880
>1800
above are shown in Table 2.3 In all experiments, Lasso-OD the fastest algorithm, and the gap between the CPU runtimes of the Lasso-OD and of the other algorithms increases with the dimension d, the other algorithms do not exploit the sparsity of the unknown parameter vector 0"
6 Conclusion
In this work, we study the BAI problem in linear bandits with sparse structure under fixed-budget sctting and develop the first BAI algorithm, Lasso-OD, that exploits the sparsily of the unknown parameter 0* Lasso-OD combines TL for support estimation with the minimax optimal BAI algorithm, OD-LinBAL. We analyze the error probability of Lasso-OD and show that the error exponent depends on the sparsity s rather than the dimension d. Unlike other algorithms in the literature, the empirical performance of Lasso-OD does not deteriorate at large dimensions.
One future direction is to derive instance-dependent asymptotic non-asymptotic lower bound for the BAI problem in sparse linear bandits; however, such a bound remains open even in the non-sparse scenario. Another possible direction is to extend the TL technique used in Lasso-OD to the fixed-confidence setting. Although such an extension is relatively easy to analyze, the empirical performances of most fxeed-cofiidence BAI algorithuns in linear bandits are not heavily dependent on the dimension unlike the fixed-budget set setting (see, for example, Zaki al. (2022); Tao et al. (2018); Fiez al. (2019)). Therefore, the benefit of adding TL phase in the fixed-confidence setting could be limited.
7 Acknowledgments and Disclosure of Funding
This research is part of the programme DesCartes and is supported by the National Research Foundation, Prime Minister's Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme.
References
Yasin Abbasi- Yadkori, David Pal, and Csaba Szepesvari. Online-to-conffienne--ss conversions and ap- plication sparse stochastic bandits. In Neil D. Lawrence and Mark Girolami (eds.), Proceedings of the Fifteenth International Conference ceedlngg of Machine Learning Research, pp. 1-9, La Palma, Canary Islands, 21-23 Apr. 2012. URL https://proceeding mlr. prwss/ 2t1////bbasiyyaaae
Artificial Intelligence and Statistics, volume 22 of Pro-
Ayya Alieva, Ashok Cutkosky, and Abhimanyu Das. Robust pure exploration in linear bandits with limited budget. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 187-195, 18-24 24 July 2021. URL https:/ hwtpa////coccceens....o mlr. wwwp:emww.....eeeeeeeeeeeeeeeeee v19// http//lleaaaaa.../ html.
Kaito Ariu, Kenshi Abe, and Alexandre Proutiere. Thresholded Lasso bandit. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th
Note that for Table 2, terminate experiments when their runtimes exceed 30 minutes.
13

---

Published in Transactions on Machine Learning Research (01/2024)
International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 378-928, 17-23 July 2022. URL https://proceeddngg mlr press/v162//rru2222 http://pooeerrgr...epeeeee//////
html.
Yven-Yves Audibert and Sébastien Bubeck. Best arm identification in multi-armed bandits. In COLT 23th Conference on Learning Theory 2010, pp. 13 p., Haila, Israel, June 2010. URL https: https://hal-enpe wuweees-ovveete..r//eeeeee
Peter Auer. Using confidence bounds for exploilattion-exlloratinn trade-offs. Journal of Machine Learning Research, 3:397-422, Nov. 2002.
MohammadJavad Azizi, Branislav Kveton, and Mohammad Ghavamzadeh. Fixed-budget best-arm iden- tification in structured bandits. In Lud De Racdt (od.), Proceedings of the Thirty-First Interna- tional Joint Conference on Artificial Intelligence, IJCAI-22, pp. 2798 2804. International Joint Con- ferences on Artificial Intelligence Organization, July 2022. doi: 10.24463 224963/jjcaii 2022a3. //doi.org/ htgg1..rg111.. 10. 24963/ /////////aa..///// 2082/388.
URL https:
Z. D. Bai and Y. Q. Yin. Limit the Smallest Eigenvalue of a Large Dimensional Sample Covariance Matrix. The Anmals of Probability, 21(3))1275 1294, 1993. doi: 10.1214/aop/ 11669/991../11991118. URL https: //doi. oariliorg/11.0 10/0 /ttp////p/11/9991111
S. Boyd and L. Vandenberghe. Convez Optimization. Cambridge University Press, 2004.
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends08 in Machine learning, 311):1- 2011.
Sébastien Bubeck and Nicolo Cesa-Biande Bisa-Bia Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and TrendsD in Machine Learning, 5(1):1 122, Dec. 2012.
Peter Bühlmann and Sara A. van de Geer. Statistics for Springer, Heidelberg, 2011. ISBN 978-3-642- 22-2111--... ooi.org/// 10. 1007 1007 /908 3- 3-2- 3--42-20192-999
data. Springer Series in Statistios. doi: 10. 1.01000/990 11.007/978-3-642-201850-
URL http://dx.
Alexandra Carpentier and Andrea Locatelli. Tight (lower) bounds for the fixed budget best arm identification bandit problem. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir (eds.), 29th Annuol Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pp. 590 604, Columbia University, New York, New York, USA, 23-26 Jun 2016. URL https://proceeding: mlr, press/v49) carpentier16 html. htmml.
Sunrit Chakraborty, Saptarshi Roy, and Ambuj Tewari. Thompson sampling for high-dimensional sparse linear contextual bandits. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 3979 4008. PMLR, 23 29 Jul 2023. URL https: httpas///pcceeenns... mlr. www.mmeer........e.mmmmm /202///v002/ chakraborty233 html.
Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. 21st Annual Conference on Learning Theory, pp. 355-366, 2008
Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research, 7(39): 1079-1105, 2006. URL attp://jmla: orgh org. htwpg//ppp//////eeeaarraae
Kelwin Fernandes, Pedro Vinagre, Paulo Cortez, and Pedro Sernadela. Online News Popularity. UCI Machine Learning Repository, 2015. DOL: https://doi.org: (tllii.org10.22443333 24432/C5NS3Y,
Tanner Fiez, Lalit Jain, Kevin G Jamieson, and Lillian Railiff. Sequential experimental de- sign for transductive linear bandits. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett (ods.), Advances Neural Information Processing Systems, vol- ume 32, 10-12 Dec. 2019. URL https: https://proceeding/ ipppoeeeiings.nurrpp...... neurips. cc/ wwtpppppppppppeeeeeeeeeeeee...ee stapa//fleessee//////// 8ba6c657b03fc7 cfdd Bad pdf.
14

---

Published in Transactions on Machine Learning Research (01/2024)
M. Grant and S. Boyd. CVX: Matlab software for disciplined convex programming. version 2.0. http: //evxr. www.ecccccccccceeeee August 2012.
Botao Hao, Tor Lattimore, and Mengdi Wang. High-dimensional sparse linear bandits. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and Н. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 10753 10763, 7 12 Dec. 2020. URL https://proeet nttps://proceedings. wewtiiinggneuuir...mmm cwpppppp.ccpppprr.... Pdf.
Matthew Hoffman, Bobak Shahriari, and Nando Freitas. On correlation and budget constraints in model- based bandit optimization with application to automatic machine learning. In Samuel Kaski and Jukka Corander (eds.), Proceedings of the Seventeenth International Conference on Artificial Intelligence and Slatislics, volume 33 of Proceedings of Machine Learving Research, pp. 365 374, Reykjavik, Iceland, 22 25 Apr. 2014. URL https: httpt:://poceeeeeeeeeeeeo http://oooceeeei...e//// mlr press/v33. http/////3//offfffa/////
Kyoungseok Jang, Chicheng Zhang, and Sarang-Sung Jun. Popart: Efficient sparse regression and experimen- tal design for optimal sparse linear bandits. In Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Newral Information Processing Systems, volume 35, pp. 2102-2114. Cur- ran Associates, Inc., 2022. URL httpss:/ neuriig pdf.
neurips wwwrips.cc/pappe.....eeeeeeeeeee wtt.ripps.cpppppe...../////ppp/p fft.ss//paae///222//eea
Yassir Jedra and Alexandre Proutiere. Optimal best-arm identification in linear bandits. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 10007-10017, 7-12 Dec. 2020. URL https://procedding: httprrrreedinnnnnnnoonreoeeeeeee neurips.cc/paper. cc/paper_ Paper.pae.......e..
fi httpap//e////0olaeeee//a/aaaaaa.
Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In Sanjoy Dasgupta and David McAllester (eds.), Proceedings of the 30th International Conference on Ma- chine Learning, volume 28 of Proceedings of Machine Learning Research, pp. 1238 1246, Atlanta, Georgia, USA, 17-19 June 2013. URL https: http::///prcceednggs mlr. htwpeeiinnn.....presssseeeeeeeee wtt.perrr/////rmiinne
html.
Julian Katz-Samuels, Lalit Jain, Zohar Karnin, and Kevin G Jamieson. An empirical process approach to the union bound: Practical algorithms for combinatorial and linear bandits. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 10371 10382, 7 12 Dec. 2020. URL https: https:// http://///oooeess...eeeeee wwtppppp.ccppppprrrrrr..p.p fwwes/ p Fite775800f73380011922211018ee
Paper. påf.
Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best arm identification in multi-armed bandit models. Journal of Machine Learning Research, 17:1 42, 2016.
J. Kiefer and J. Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363 366, 1960. doi: 10.4153/ 1.4115//CJM-1960 CCM--1960-030-4
Gi-Soo Kim and Myunghee Cho Paik. Doubly-robust lasso bandit. In H. Wallach, H. Larochelle, A. Beygelz- imer, F. d'Alché-Buc, E. Fax, and R. Garnett (eds.), Advances én Neural Information Processing Systems, volume 32. Curran Associates, Tnc., 2019. URT. https: htwttts::/ppoeeeeeeeeeee http///poooccee...///e//// wtwpeceeiinnnnnuurppppeeeee www.iis....... wtlppp..ccpppppee cctpaper_ffteeeeeeeeeeeeeeeeeeee www.sflllppppaeeee paper/ /ttp:///////0000/00000000000aaa0
pdf.
Wenjie Li, Adarsh Barik, and Jean Honorio. A simple unified framework for high dinensional bandit problems. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 12619 12655. PMLR, 17-23 Jul 2022. URL https:// proceedings mlr, presss/v12/1122a. html.
J. Löfberg. Yalmip: A toolbox for modcling and optimization in MATLAB. In In Proceedings of the CACSD Conference, Taipei, Taiwan, 2004.
Min-Hwan Oh, Garud Iyengar, and Assaf Zeevi. Sparsity-agnostic lasso bandit. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, volume 139
15

---

Published in Transactions on Machine Learning Research (01/2024)
of Proceedings of Machine Learning Research, pp. 8271-8280. PMLR, 18-24 Jul 2021. URL https:
/ //proceeding.mllr mlr. pttpps/ess//h2eel.// /tt.ee//diig......rese//////////
html.
Friedrich Pukelsheim. Optimal Design of Experiments. Society for Industrial and Applied Mathematics, 2006. doi: 10.1137/1.9780096711
URL https://epubs. siam wttp://///////....oooooo/ /ttp:////000111111..777777099990
Herbert Robbins. Some aspects of the sequential design of experiments. Bull. Amer. Math. Soc., 58:527-553 535, 1952.
Marta Soare, Alessandro Lazaric, and Remi Munos. Best-arm identification in linear bandits. In Z. Ghahra- mani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger (eds.), Advances in Newrol Information Processing Systems, volume 27, 8 8-11 Dec. 2014. URL https://proceedingg neurips cttppp.rcpppprr...ppppp files/
.df.
Chao Tao, Saúl Blanco, and Yuan Zhou. Best arm identification in linear bandits with linear dimension dependency. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedinggs of Machine Leurning Research, pp. 4877 4886, 10 15 July 2018. URL https://ppott httpas//ppooceeing...oo http://nnn........eer/rr//////// sateess/v80/ttolle html.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285225 294, 1933.
Robert Tibshirani. Regression shrinkage and selection via the Lasso. Journal of the Royal Statistical Society: 100.0000.00....00...... URL https / /rs.. onl onw http://////oo/////..oiii1../ 111.:0011111//22211166661 2517- 199.66111.19999111111 tt020800.
Series B (Methondooogical), 58(1):267-288, 1996. doi: http:://obiorr//0111///27766611
Sara A. van de Geer and Peter Bühlmann. On the conditions used to prove oracle results for the Lasso. Electronic Journal of Statistics, ((non)):1300 1392, 2009. doi: 10. 2221400-EJJSS URL https /doi org/10. 10. 12144/9-E-J..566
Xue Wang, Mike Mingcheng Wei, and Tao Yao. Efficient sparse linear bandits under high dimensional data. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '23, pp. 2431-2443, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701030. URL https://doi orrellrrg//o/ htte//...111///111 11445/35355000 3599329.
doi: 10. 0114555550005535999335
Liyuan Xu, Junya Honda, and Masashi Sugiyama. A fully adaptive algorithm for pure exploration in linear bandits. Amas Storkey and Fernando Perez-Cruz (eds.), Proceedings of the Twendy-Firsl Inderna- tional Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pp. 843 851, 09 11 Apr. 2018. URL https://proceedings ww..m.rrreeee pwwps/////zzuiai
Junwen Yang and Vincent Y. F. Tan. Minimax optimal fixed-budget best arm identification in lincar bandits. In Alice Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, Nov. 2022. URL https://openrevier
Mohammadi Zaki, Avi Mohan, and Aditya Gopalan. Improved pure exploration in linear bandits with no- regret learning. In Lud De Raedt (ed.), Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pp. 3709 3715. International Joint Conferences on Artificial Intelligence Organization, July 2022. doi: 10.24963 /ttp//....2//////....2 URL https: //op:: org/10. 24963/2 119963/jjcai... .0222/ 515.
Shuheng Zhou. Thresholding procedures for high dimensional variable select ion and statistical estimationn.
Y. Bengio, D. Schuurmans, Lafferty, C. Williams, and A. Culotta (eds.), Advances in Neural Information Processing Systems, volume 22, 10 Dec. 2009. URL https: / http///peeedggaaee///e////e neurips wttpcc/ppppppaeeeeeee files/ Paper. pdf.
16

---

Published in Transactions on Machine Learning Research (01/2024)
A Design Matrix Optimization in Thresholded Lasso
The performance of TL in Lasso-OD is characterized by the bound on the probability in (12). For any pair of (Amit: Athres), the bound in (12) is optimized by setting the design matrix X maximize the ratio (M)
V # maxxc
Note that in the application of the Lasso, we can normalize the dataset that ExEjK] a(k) are equal for all j E [d]. Under the assumptions that the number of arms, K, large and that the arm vectors are drawn from the same distribution, the value of I maxje[d] X|x, cammot vary too much with respect to 7i
different fraction of arm pulls. Therefore, we relax the quantity 7i max5el4] [| (12) by its upper bound ma [[]()) Then, Theorem implics that the best choice of X maximizes the compatibility constant (M,
Computation of the compatibility constant Let v E Pr ([K]) be the Ty-type distribution describing the fractions of the number of pulls for each arm. Then, M = x = Lie[k] maa(iaa(i) Rewriting the compatibility constant d² (2² from Definition with some overload of notation, obtain
|S| 101 (00 Excng (a(())(1))
(u, o² (M BER
min
|00||1 1, ||0s= s 3
(21)
(v,
2
min 8² (v, SC|d |
(22)
Given fixed v, the program in (21) is non-convex due to the 4--ormm equality constraint; however, by introducing binary variables, it can be turned into mixed-integer discipled convex program (MIDCP) and be efficiently solved using CVX toolbox (Grant & Boyd, 2012). If we relaxed the equality constraint to ||0s||, < 1, then (21) would be a quadratic program (QP).
Relaxing the optimization problem According the arguments above, the optimization problem that we originally need to solve is
1² max (2 s),
(23)
vEPr, ([R]
which is computationally intractable since the maximization constraint makes it an integer program; and even if we relaxed it allow fractional number of pulls, the program would involve (*) R d" MIDCPs in its constraints.
Lemma 2. For any E P((K) and any S C [d], it holds that (v, 2 amin (EK (aa(i)(()))
Lemma 2 follows from [S] |0sl < 00sl < |0012 and relaxing the inequality constraint in (21).
Replacing (v, S) by its lower bound and allowing fractional number of pulls, we get the relaxed optimization problem in (6), which can be solved efficiently.
With the inclusion of πi maxje(d] || |X the optimization problem can be re-formulated as
Jmin (ΣK maa(ia(iiTT)
max (EP((
(24)
max (iag ( ((a(i)(()T))
which does not satisfy the MIDCP ruleset. In our experiments, we observe that the convergence of the mumerical solution to the problem in (24) heavily depends on the initialization; therefore, (24) could not be considered as reliable approach.
17

---

Published in Transactions on Machine Learning Research (01/2024)
B Pseudo-codes of ROUND and OD-LinBAI
The pseudo-codes of the rounding procedure from Pukelsheim (2006, Ch. 12) that is used in Algorithm 1 and OD-Lasso from Yang & Tan (2022) are given below.
Algorithm ROUND(T,
input a distribution π on set with cardinality d and a positive integer T. 1: Initialize T; = [(T d) m for == I,...,d. .d
while Σ + T do
3: if Σ T; < T then
4: Set j - arg ( x.'
2.
Update T₃ t T3 + 1.
5: else if Σ T. then
Set j < arg max m
T--1,
Update T, t T3 1.
end if end while output Distribution ã
7 7
+)
Algorithm 4 Optimal Design-Based Linear Best Arm Identification (OD-LinBAT)
input time budget T, arm set A = [K], and arm vectors fa(1).....a( Rd.
1: Initialize to <- 0, Ao < A, do -- d. For each i E Ao. set an = =a(i. Set R = [log2 d), T, = T for == 1, ..... R 1, and TR for to R do
Σ R-1 18-111 T.
\\ Dimensionality reduction:
Set X so that its columns are (i): Ar-1): Set dr + rank(X). Set ar(1) ar-1(i) for iE A,-1.
5: if d, < d then
Find the singular value decomposition of X UDDV where U Rdd-Ixdd
7:
Update X < UTX X and (1) < X; for i E Ar-1.
end if
\\ G-optimal design:
Input the set (i) A,-1) } to the G-optimal design, and set (r) as the output of (7).
10:
11:
Set ((r) = ROUND(x T,) from Algorithm 2.
12:
\\ Arm pulling:
13: Pull each
E Ar-1 T,(1) 7, T, T, times, which determines A A ITT, Observe the corresponding rewards Yt.-i+::... 1..1:-...,,,,11 Nt,-+TT,
14:
Compute the OLS estimator
v(r) = Σ (1),
(25)
iEA
(6)) = -
Σ ar(At)
(26)
tmty 1+1
15:
Arm elimination:
16: Estimate the mcan rewards for each i Ar-1
- (0()) (i))
(27)
Set A, f- the set of [ _ arms in Ar-1 with the largest estimated mean rewards. Set t, + t--1 + Tr. 17: end for
output f= the only remaining arm in Ag.
18

---

Published in Transactions on Machine Learning Research (01/2024)
C Proofs Related to Lasso
In the following, let be the number of samples. The linear model is given by y= X0 +e, where y E R" are the rewards, X E Rnxd is the design matrix, and e E Rn are i.i.d. 1-subgaussian random variables. Recall the initial Lasso estimator
1 = arg min ly - x0 + +111011 0
(28)
Define the event
T max 1
x - 1
(29)
jeld
The following result, known as the oracle inequality, is the main tool to control the performance of the initial lasso estimator.
Lemma 3 (Oracle Inequality: Theorem 6.1 from Bühlmann & van de Geer (2011)). On the event T, the inilial Lasso eslimalor 0 (28) salisfies
|x(0 00)1 + > 1100 0011 S
4 (M S(O))
(30)
Furthermore, il holds that.
P 1 2dexp {
nd²
(31)
32 max [x,م|ي]
Proof of Lemma 3. Since i minimizes (28), we have
1 n
y x6 + |0
1 Ily x + x
(32)
n
Plugging y X0* + e into (32), after some algebra, we get the basic inequality
1
x 03)1
||081
2 x - 0-) + A |0 11
(33)
Let T be the event
2 c T X 1 20).
max
(34)
jE[d] n
Then, on F. we have using the Hölder inequality that
x 0 13 s No 0 0*11, + +1100111 - ->10/1
(35)
Let S = S(0"). By the triangle inequality, we have
| = | + 0s 2 | 00s 10--0 -85 + 05 |,-
(36)
Applying (36) to (35), we get
x x ((0--rr) 13) S No (10s - 03 + 05. 03- 11)
+ (11011, ||, - |10/1| + 0s 03
0s:
(37)
(Ao + 2) | 00s 03
+ (Ao A)
0s
0
(38)
19

---

Published in Transactions on Machine Learning Research (01/2024)
where the last step uses the fact that f--- 0. We set Ao 2- Then, (38) implies that on the event T,
05 0zzs ||, 3 0s 033 03
(39)
Therefore, -- 0-0- E C(S), and from the definition of compatibility constant in Definition 1, we have
s( T x 0*)
|0s -0's-0311
(40)
Vno(M,
We now continue with (38) with Xo = 2. We have
2 x(O 0-) 1 + A 0 0r
|, = 2 x 0*) 12 + 0s 0%
0s- - -3 11
+
(41)
s (31 + X) | 03
- > 0 -0'.
+1 0s- -03
(42)
42 41/0s 03/1
(43)
4A/s x (0 - 03)1
(44)
vno(M
< / x(6 8*)
422s
(45)
(M.
where (44) applies (40), and (45) applies the inequality 4uo S u² + 4u² to (44). Inequality (45) completes the proof of (30).
Next, we upper bound the probability [To]. We have
PT
x
(46)
jE[d]
d1
x c 1 1
P
X e>
+P
(47)
3=1
X2
$ exp
(48)
2.
j=l
n²
where the last inequality follows since YXT.J - are subgaussian with variance proxy + X | 112
n. ,, n
as 61,...;6p tn are independent 1-subgaussian random variables. Bounding each summand (48) by the maximum of summands completes the proof of (31).
Proof of Lemma 1. The right-hand side of (30) depends on the unknown set S(0"); however, we can further upper bound the right-hand side of (30) by replacing &² (M, S(())) by its lower bound (² s), which is computable using only X and Therefore, Lemma 1 is a corollary to Lemma 3.
]
Proof of Theorem 1. Define the event g & [|0mne - 0011, <
Duaus (*(Mas)
We have
θ 0mi 0
> |||0mme
0 )
(49)
Σ
((0ma))
(50)
Σ
(Omit))
(51)
@ (((((-))
|S(0
(52)
20

---

Published in Transactions on Machine Learning Research (01/2024)
where (50) follows since 3 0 by assumption, and (52) follows from the thresholding step in (5).
Therefore, on the event 9, it holds that
Omit 0-11
AAini 8 Athres
[S(Oehres) \5(0')
(53)
Athres
Φ² (M,
For all j S(0"), on the event 9, we have
10mit))
2 min
(0
Oiit ss(e))
(54)
min
(
Ouitt s(()))
(55)
m
0
iuit
(56)
4Ainit 6² (2 s)
mmn
(57)
Therefore, if
4 4Aint
Athres 2 mmin
(58)
(2
((Othres)) 2 5(0") is satisfied on G. Combining Lemma 1, (53), and (58) completes the proof of Theorem 1.
D Proof of Theorem 2
The proof of Theorem 2 closely follows the proof Yang & Tan (2022, Th. 2). Therefore, we only explain the differences, which are as follows.
ii) Due to our construction, in Yang & Tan (2022) is replaced by T [Toga
(ii) Let A, be the active arms round and let (a)(1): E Ar) RRd- be the dimensionnlliy-rrduees arm vectors. From Fiez et al. (2019, Appendix B), it holds that
(i)( S dr (1+ (
max tEAr
(59)
where #(F) is the rounded version of the G-optimal design output ((r),
(iii) In the proof of Yang & Tan (2022, Lemma 3), the set B, is the set of arms in A,-1 excluding the best arm and [24+1 suboptimal arms with the largest mean rewards. We re-define B, as the set of arms in A excluding the best arm and d suboptimal arms with the largest mean rewards. d
With the modifications in items (i) and (ii) and following the stops in the proof of Yang & Tan (2022, Lemma 2), we get for any arm E Ar-1
TA?
P ( < (A(1) A exp
(60)
8 2r-1
11
T
where (i) denotes the estimated mean of arm in round
21

---

Published in Transactions on Machine Learning Research (01/2024)
Using item (iii) and (60), go through the proof of Yang & Tan (2022, Lemma 3) and get
PA
(K 1 exp
rf
16( + 1+1)
(61)
TA 1-1
(3/ 1) exp
if > 1.
16( 1++))(1+++
Finally, following the steps in the proof of Yang & Tan (2022, Th. 2) with (61), get
p p + <
d
2 +
[log.
Σ
d
+ [log2 dl -1
exp
T
(62)
2
16 1 +
42
7)
H2.
f
$ (K + log2 d) exp
(63)
16
1
de
(2,
T
which completes the proof.
E Proof of Corollary 1
We set N, Ainit and Aphres
16
25
K
Φi 02 24'
(64)
Ainit
and
(65)
Vi(( + s2)
4
Athres
Amit.
(66)
0²s
Note that (66) sets 81 = + s2 in (15), and for any 8 E N, we check that the condition in Theorem 3 holds:
mmi 0²
25
8
Auait c+
(67)
24
+2
Next, we would like to set co = Ti so that the two exponents in (14) are equal. However, since H2, (s + +2)
T2
is not available us, we use the lower bound
S s
$ s
H2, + +2)
(2.....+++
max
A
A
ot&2
4
(68)
where the last inequality follows from the assumption |u S 1 for all k E [K].* One can further upper bound
Asts² by using the values of K arm vectors and searching for 0 that gives the largest Ast32.
We set the ratio co = T as
25 16x
Co
max
(69)
00 min log, (8 + 82)
which together with (64)-(68) ensures that
(81)
Ti Ai 32.r
exp
exp
(70)
16 (1 + <) (2,
Combining (70) with 81 = 8 + x2 completes the proof.
The ratio Co decreasing with as in (69) is consistent since as approaches d, the sparse linear bandit approaches the standard linear bandit, and we would expect to spend more budget phase than phase for large We deliberately choose the parameters in (64)-(66) to maintain this properly.
4This step the only place where the assumption the mean rewards used.
22

---

Published in Transactions on Machine Learning Research (01/2024)
F Implementation Details
Our code is available at https://github: http:///gtthtocooooeeeeeeerrrr/s spartl___aaaaaaaaarrre In all compu- tations of the Lasso problem (4), we use the ADMM algorithm (Boyd et al., 2011).
F.1 Lasso-OD with K-fold Validaaai
Th is set to the default value 1 i.e., In the implementation of Lasso-OD-CV. the ratio of the budgets, Ty naturally, the algorithm spends more budget for the BAI algorithm than for the support estimation.
For tuning the hyperparameters Amit and Attures we pull Ti arms according to the allocation given in (6). We use the following cross- validation steps to tune the parameters.
(i) Fix two sets of hyperparameters (Aiuit, 2 -.... miit.m and {Athres, 2 -... mhres, that are candidates for Amnt and Athres respectively.
iii) Iteratively tune the parameters by fixing one of them and searching for the best parameter for the other one.
(iii) In each cross- vals-vaaii round, the objective is minimize the loss function
Ti - y
L L-
x X
+ c
O
ll.
ogB [
thres
> { []]
|cares
(71)
where ej and 02 are fo-norm regularization parameters. Here, the first term in (71) is the mean-squared error; the second and the third terms penalize the f--norm error and force the hyperparameters output estimate with variables. In application, we set c 200 and c2 5, giving more importance to detecting at least s variables. If the value of s is not available, can still use this technique by setting <2 = 0. As standard, we approximate (71) by training the parameters in K blocks and testing in the remaining block.
(iv) To speed up convergence, each round of cross-validation, we exponentially narrow down the candi- date sets.
(v) To reduce the variance in cross-validation, we employ Monte-Carlo simulations, i.c., we independently partition the data into K blocks for multiple times and then take the average loss.
F.2 LD-sa-OD-Analyticaal
In the implementation of Tasso-OD-Analylinn and cg is set that (69) holds with equality, This setup effectively uses the hardness parameter H2 ss+ To compute these hyperparameters, we first need to compute (2, s). As discussed in Appendix A, this requires solving a MIDCP. We do this by using the YALMIP toolbex (Löfberg, 2004) because it does not ask to convert the problem into another one. Alternatively, one can use the CVX toolbox (Grant & Boyd, 2012)
set the hyperparameters Xinit and Athres in (64) (66).
with a little bit more effort, or use Lemma and solve an easier problem at the expense of some performance loss.
F.3 OD-LinBAl and Other BAI Algorithms
We implement OD-LinBAT and other BAI algorithms shown in section 5 using the methods described in Yang & Tan (2022, Appendix E).
In general, BayesGap algorithm (Hoffman et al., 2014) requires the knowledge of the hardness parameter. As in Hoffman et al. (2014); Yang & Tan (2022), at the beginning of each time instant, we input the estimated hardness parameter according to the three-sigma rule. In the experiments, omit the oracle version of BayesGap that directly uses the knowledge of the hardness parameter.
Addaative
23

---

Published in Transactions on Machine Learning Research (01/2024)
G Additional Experiments
G.1 Variants of Our Algorithm
We present two variants of Lasso-OD that modify the operations in phase and one variant that replaces the thresholded Lasso in phase
This algorithm is identical Lasso-OD except that the G-optimal design used to determine the allocations within each round is replaced by the X'>aallocation from Soare et al. (2014). Let = (a(i): i A} be the set of arms in active set A. Let y {ar x': a, x' E N, + x²) be the set of arm differences. The Xlyallocatiinn solves the problem
Lasso-Xy Allootccto:
arg min max | (B)lM())- TAP(A)
(72)
replaces Line 11 of Algorithm 4 with (72). In the experiments, we compute (72) using
the Frank-Wood Wolfe algorithm as in Ficz et al. (2019).
From Yang& & Tan (2022, Proof of Lemma 2), the probability that sub-optimal arm has a smaller estimated mean than the optimal arm is bounded
A
[i1(1) < ((i)) < exp
(73)
(1a(11) a(i)
A
S exp
(74)
maxi41 |a(
a(i)llM(M))
A
< exp
(75)
8 SmaxeA
aa [())
where is the allocation within the round. Here, (75) follows from the triangle inequality. The G-optimal design optimizes the allocation x in (75), and XYVallocation optimizes (74). Since x)'aallccation optimizes lighter bound, -a-aloionalloocatiion is expected to perform better than Lasso-OD.
Lasso-Baycs Since BayesGap performs better than OD-LinBAT in the examples in section 5, we propose the variant. Gapso where in phase 2, OD-LinBAT replaced by GayesGap-Adapliig from Hoffman et al. (2014).
In our implementations of Ay-Aloyy--ooooatiinnn and Lasso-BayosGap (as described above), the paramcters of Lasso are luned via vross-valiiation.
Recently, Jang et al. (2022) develop the PopArt algorithm, which estimates the unknown parameter 0* similarly to Lasso and TL. Due to its superior & error to Lasso, PopArt also guarantees that the support of 0 is estimated efficiently. Similar to TI., the PopArt estimate obtained by thresholding an initial estimate. Our variant, PopArt-OD, replaces the TL in phase of Lasso-OD with PopArt, and retains phase as is. We give its pseudo-code in Algorithm 5 and analyze its performance in the section below. Line 1 of PopArt involves an optimization problem that yields the optimal covariance matrix with respect to an upper bound on the error probability; this process reflects the design matrix optimization of TL described in Appendix A. In PopArt, if the population covariance M in Line 3 was replaced with the empirical covariance and if the Catoni estimator in Line was replaced with averaging, the resulting algorithm would the thresholded OLS estimator.
PopArt-OD:
PopArt has one hyperparameter (the estimate on the error probability 8 in Jang et al. (2022)). In the experiments to follow, we tune the hyperparameter using K-fold cross validation procedure.
G.2 Analysis of PopArt- OD
The following theorem bounds the error probability of PopArt-OD.
24

---

Published in Transactions on Machine Learning Research (01/2024)
Algorithm 5 PopArt-OD
input Time budget T, arm vectors a(l)....,, a(K) E RR Omin, and sparsity 8.
1: Solve the convex optimization problem v' arg min max
(E (;a(i)(()T)-1))
Let the objective
NEP[K] iE|d
value of the minimum be H2 and M = = U (()aa(i)) Set
ApA min { (V2T?.
min
2H?
T CPA
X
CPA Ap s logg s
Ti
T- T Tı, 9 8H?
2
1 CPA
(76)
Sample Ti arms, A1, A Ar; i.idd with v*, and observe rewards -I 3: For 1,..., Ti, let a-----aA--- (Ar))x E Rd.
g Set for [d] 0g Catoni (01.h..... (.......,,,,,,, Ona.) (M (a 22
where Catoni((Z,,.... Zn), a) is the
unique solution to the equation
(a((z-9)) -))= =0, ((x)) = sign(x)) + +|]
22/2)..
(77)
OPA- (8 2 V 9M [d] and SPA S(Ora).
6: Run OD-LinBAT (Algorithm 4) restricted to the support SPA using T2 pulls. output î is the only remaining arm as the output of Algorithm 4.
Theorem 4. For any linear bandit instance, the error probobility of PopArt-OD given in Algorithm 5 is bounded as
P i 1 S (K+ + log, + 2d) exp { 16 logg EPA) H2 un (s) + CPA) +ppa))
T
(78)
where CPA is defined in (76), below, and ePA [I+opa)a"
Proof. By Line 5 of PopArt, if E [d] satisfies that 6 2 APA. then i e SPA- From Jang et al. (2022, Prop. 1 and Th. 1), with probability at least 1 - 2d exp
{
Ti {
8H1 J. the initial PopArt estimator O' satisfies
110' - -00 I XPA
(79)
and the PopArt estimator satisfies S(Opa) s S(0)). By selecting APA S Ornn we further ensure that S(0") S S(OPA), giving S(0PA) = S(0"). Therefore, by the union bound and Thcorem 2, the error probability of OD is bounded as
P i +
1
s F (((PA)) + S(00)
+ [ 1|((0p)))))) S(Or)
(80)
{
TiAp 8H?
Te
S 2dexp
+ (K + loga d) exp
(81)
16 s) H2 (s) + EPA)
The rest of the proof follows steps similar to the proof of Theorem 3, which aims to balance the two exponents in (81). The choices of CPA. Ti, and Tz together with the lower bound (2) 2 á (see, (68)) imply that
Ai 8H?
T
(82)
16 log, H2 (s) + CPA)'
which completes the proof. Note that we select ApA S /2H, to ensure that 2g 2 > making the Catoni parameter in Line of Algorithm valid.
25

---

Published in Transactions on Machine Learning Research (01/2024)
2, 10, 70, (1) 1210.56
20, 50, Maja(() 1244.31
0.8
probabiltt
Error probabiltty
0.6
0.4
0.2
10
10
10a
10*
3, 10, K 50, (a).()) 1256.54
20, K 50, (en(d) 1244.70
Error probabiitt
Enror probabillty
0.8
0.4
0.4
10a
10
10
10*
10. K 50, (2 1246.54
d= 20, K 50, H.n 124.81
0.89
0.8
Error probeblity
Error grobebilky
0.69
0.8
0.4
0.4
0.2
0.2
T
PopArt BayesGap
Analytical
BayesGap
Figure 6: Comparison of several algorithms with 8 E (2,3,4).
Theorem 4 shows that PopArt-OD has error probability that scales as
exp (n (log2 H)
T
(83)
as T and 8 grow. This is the same theoretical result as that for Lasso-OD, However, we observe from the next section (specifically Appendix G.3.1) that Lasso-OD outperforms PopArt-OD empirically.
G.3 Experiments
In the experiments below, we include Lasso-xYYaallocation and Basso-BByysGap to the list of algorithms in Section 5.
G.3.1 First Example
In the first example, we test the performance of the various BAI algorithms for sparsities at least 2. We generate K d-dimensional arm vectors a(k) = (a(k);: e [d], k E [K], where a(k),'s 's are distributed N/ 4) independent across arms is E [K] and coordinates i E [d]. The s-sparse unknown vector 0* set as 07 vs for í E [s] and 0; 0 for i = the literature and variants of our algorithm for E (2,3,4) 4), K = 50, d E {10, 20), and T E [200, 104). For all bandit instances under consideration, the performances Lasso-OD and Lasso-X) XYy-allcatttooioon are almost identical. However, due to its low computational complexity (sce Tables and for the CPU runtimes), Lasso-OD preferred over Ko-aoo-Y-lllocattonn Among different variants of Lasso-OD, Lasso- OD and Tasso-XYY-allocalll have the best performance for the instances with 2. For and 4.
1.....d. d. Figure 6 comparcs the performances of several algorithms in
26

---

Published in Transactions on Machine Learning Research (01/2024)
2,
(d) 574.54
d=
20,
K
50, Hamm
687.29
0.8
0.8
Error probabilty
0.6
Error probability
0.6
0.4
0.2
10a
10
10
10
T
T
2. d 10, K 100, Mauldd
896.98
2, d
20, K
100,
Hom (4) 836.69
0.8
0.8
Eroo probabiity
Error probability
0.6
0.6
0.4g
0.2
0.2
10
10
10
10
T
Lasso OD
PopArt-O QD LinBAI
BayesGap Adsptiie GSE
Lasso OD An. LB
Lasso BayesGap
Figure 7: Comparison of several algorithms with 0* belonging to finite set.
among the algorithms shown, Lasso-BayssGap performs the best for a large enough budget T. The poor performance of Lasso-based algorithms for small budgets is because at larger 8, the minimum budget that should be allocated to phase 1 to reliably estimate the support of e increases with s. For the instances with E {3, 4), BayesGap-Adaptive performs remarkably well, but is outperformed by Lasso-based algorithms for 2. PopArt-OD algorithm outperformed by Lasso-Oh OD for all instances shown, which implies that the variable selection property of PopArt is poorer than that of the thresholded Lasso.
In Tables 3 and 4,5 report the average CPU runtimes for the instances in the first example with 2 and == 3. Lasso-OD is superior to all other algorithms in terms of the computational complexity.
G.3.2 Second Example
In the second example, we assume that 0' belongs to the finite set H A (0 Rd: |01| {- 1- f Vi [d])- In other words, the non-zero coordinates of 0" are assumed to have mag- nitudes all equal to I. We generate K d-dimensional arm vectors in the vicinity of H as follows: a(k), = RA., cos(TT44 + Zk,;), where RR,y's is are independently and identically distributed (i.id.) generated with distribution are independent. For this bandit instance, given the arm vectors and using the assumption that 0" E H, we can lower bound the hardness parameter H2,i + s2) by computing the minimum hardness parameter for computes the hyperparameters analytically and obtains
E
Ve
11, Zk.''s iss are i.i.d. generated with distribution (N00, 0.01), and RA, and Zz
the vectors H. In Figure 7, Basso-OD-An--l Ti from the lower bound H2 + s²) above instead of the true value of H2, + s?). Figure 7 shows that Lasso-OD-Ande as Lasso-OD and (')-5-AX'--llccal for large enough time budget.
outperforms all other algorithms in the literature and achieves similar performance
Pro-calculation in Tables and 4 refers the calculation of (M, that used to determine the hyperparameters for Masso--O-AAie Analytical... 6 All experiments implemented MATLAB 2023a on an Intel(R) Core(TM) 19-12900H processor.
27

---

Published in Transactions on Machine Learning Research (01/2024)
Table 3: The empirical means of the CPU runtimes for = d 10, K 50.
CPU runtimes (milliseconds)
T
Pre-cale.
Lasso Tuning
Lasso-
Lasso-Xy
Lasso-Bayese
Lasso-OD-An
BayesGap-Ad.
OD-LinBAI
GSB
100
9680
3300
0.98
1.7
3.2
2.2
4.0
200
9680
3500
0.61
5.2
2.9
1.2
5.1
2.2
4.0
400
9680
3800
0.55
3.6
5.5
0.83
2.1
4.0
800
9680
4380
0.48
3.4
11
0.76
17
2.1
4.0
1600
9680
6570
0.66
4.1
23
0.68
34
2.1
4.0
3200
9680
7520
0.66
4.0
46
0.70
69
2.1
4.0
6400
9680
7710
0.70
4.1
89
1.1
139
2.1
4.0
G.3.3
Third Example
the third example, we extend the example Yang Tan (2022); Jedra & Proutiere (2020); Fiez et al. (2019) sparse linear bandits. We set 0* ( ( /2" O,....... 0), i.c., s 2, and S(0)) {1.2). For the coordinates in S, we pull arms as in Yang & Tan (2022); we sct a(1)s K..,.
where di are independently drawn from (0, 0.09). For any E [K], we draw a())s- independently from the uniform
((K)s (cos(57/4) /4), sin(55/ (1)), and a(i)s (cos(T π 2 + de), sin(t/22 + 6.)) for i= 2,..., K
1,
distribution on the (d -0=s)=aa di-diennia centered sphere of radius V ميف Recall that since 03. = 0, the values of arms the coordinates S have effect on the best arm or the value of the hardness parameter. The problem would be identical to that in Yang & Tan (2022) if the agent knew the support S. In this bandit instance, arm is the best arm and there are K 2 arms whose mcan values are close to that of the second best arm. In the non-sparse case, i.e., = 2, Yang & Tan (2022) demonstrate that OD-LinBAl outperforms the other algorithms. Figure 8 compares the performance of variants of our algorithm with the other algorithms in the literature. We report the empirical performances for E {10, 20), K {50, 100), and T [200, 10*). Among the algorithms shown, Oasso-OD and its variants Lasso-X3Y-allocatii and PopArt- OD significantly outperform the other algorithms. Unlike the previous examples, for this example, Lasso-Bayed BapooGaa is not the best performing algorithm.
N 30, H. Haa000) 760
20, X 10 537
08
0.1
0.4
0.2
0.8
0.9
Enor poboato
0.6
10
10?
Hhoayyl- RapeeOop
Figure 8: Comparison of several algorithms for the example bandit instance in Yang & Tan (2022).
28

---

Published in Transactions on Machine Learning Research (01/2024)
Table 4: The empirical means of the CPU runtimes for s s 3, d
10, K 50.
CPU runtimes (milliseconds)
T
Pre-cale.
Lasso Tuning
Lasso-
Lasso-Xy
Lasso-BayesG.
Lasso-O--An
BayesGap-Ad.
OD-LinBAI
GSB
100
27100
4200
1.1
12
2.2
2.5
2.4
4.2
200
27100
4500
0.96
8.9
2.9
2.1
5.2
2.4
4.1
400
27100
4900
0.94
8.1
5.7
2.3
10
2.4
4.1
800
27100
5000
0.98
7.6
12
2.3
17
2.4
4.2
1600
27100
5100
1.5
9.2
24
2.1
34
2.4
4.2
3200
27100
7000
1.5
9.2
47
2
68
2.4
4.2
6400
27100
9800
1.6
9.4
93
137
2.4
4.1
G.3.4 Fourth Example
In the final example, we lest the performance of thresholded Lasso in which the whole horizon of length T used for learning the support of 0 We draw each entry of the design matrix X Rxx ii.d. from Ni(0, 3) and set 0" = ( I 0z.......0 where 0" has non-zero entries. In Figure
report the empirical probability of detection error P ((ahre))) 2 S(0)) and the empirical mean E[]S((ehares)] ) over 10,000 independent trials. For s = 2, the empirical error probability is 0 for 2 400; for s = 4, the empirical error probability for 7 2 800. Figure shows that for T 2 100 and 8 E 4), thresholded Lasso is capable of correctly detecting the active variables in 0 with high probability while also keeping the average number of false positives close to zero. As expected, the average number of false positives increases with
29

---

Published in Transactions on Machine Learning Research (01/2024)
2,d
8= 4,d 10
10
6
5
4
2
0
10
102
10
10
10
10a
10a
10
T
T
2, d
20
4,d
20
14
6
12
5
10
4
3
2
0
10
10
10
10
10a
10
T
Average support size
Probebility of detaction error
Figure The empirical detection error probability and the empirical size of the thresholded Lasso output.
30


Reviews:
[{"review_id": "oycXkTHXrn", "reviewer": "Reviewer_oj4o", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n1.This study first addresses the sparse linear bandit for BAI in the fixed budget setting.\n\n2. The proposed algorithm is computationally efficient and enjoys the desirable upper bound where error probability is independent of the original dimension d. This property is especially useful in high-dimensional settings. \n\n3. The paper is easy to follow, and all the related work is clearly discussed. \n\n\nWeakness:\n1. Theoretical results are not significant, although novel results. Indeed, the proposed algorithm is a naive combination of Lasso and the existing linear bandit algorithm. In particular, the first phase is an adaption of E-optimal design [Hao+2020] to determine the optimal allocation of arm strategy and [Ariu+2020] to find support including the true support with high probability. The second phase is to run OD-LinBAI [Yang and Tan 2022]. The important analysis highly relies on [Ariu+2020] for the concentration bound that relates sparsity parameter s and compatibility constant \\psi(M,s). Combining them to derive the bound for fixed budget setting is not a significant effort. \n\n2. The experimental results are not satisfying. Although the motivation of the problem is from the high-dimensional cases, the experiments are only conducted on a very small dataset. It would be more reasonable to show the high-dimensional instances such as d=1000 or 10000 as in [Ariu+2020]. \n\n3.  The techniques discussed here seems also applicable to fixed confidence settings. Although the authors already mentioned the FC setting in the Conclusion, I would not understand why it is not worth studying FC setting. If there is no result in the sparse linear bandit for the FC setting, it is still interesting to investigate FC setting. As a naive solution for FC setting, we can still use E-optimal design until we can identify \\hat{S} including the true support with a high probability, and after that, we can conduct a phased elimination algorithm based on G-optimal design like [Tao+2018] for FC setting instead of OD-LinBAI [Yang and Tan 2022]. I believe this algorithm can solve FC setting and have a sample complexity bound which is independent of the original dimension d.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this study, they study a fixed budget setting for best arm identification under sparse structure. Given a budget T, the learner aims to find the best arm while minimizing the error probability. The paper considers the sparsity and the goal is to develop an algorithm whose error probability only depends on the sparsity parameter s:=\\|\\theta^*\\|_1 rather than the original dimension d. They also conduct an experimental evaluation on a small dataset.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Experiments for the case when d is sufficiently large. \n\n2. Hope that the authors will address my concern written in Weakness above.\n\n3. Could you provide an explanation on how to compute T_1/T_2 and decide parameters lambda in the main text? What is the order of b (equivalently, what the order will compatibility constant \\psi(M,s) become when we use such an optimal parameter choice in the end)?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "kjdfA1rD0a", "reviewer": "Reviewer_JhRB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I think this is an interesting paper with enough interesting analysis on sparse linear regression.\n\n\n\nStrength:\n1) It is the first algorithm specialized for the sparse linear BAI.\n2) The idea is straightforward - identify support using Lasso, thresholding out the unnecessary coordinates, and apply the known linear BAI algorithm.\n3) Since the idea itself is simple, seems like there's no specific place to make a wrong proof.\n4) They did a thorough research on the sparse linear estimation. It helped me to understand a bit more about sparse linear regression.\n\n\n\nWeakness:\n\n1) They directly used the compatibility constant in their result. Usually, this constant is very difficult to optimize. They even mentioned in Appendix A that it is computationally intractable. Therefore, even though they used 'compatibility constant' in their analysis, actually they used 'E-optimality' (maximizing the minimum eigenvalue) and approximated the compatibility constant by the minimum eigenvalue (Lemma 2 in Appendix A). \n\n1-1) More interestingly, they eventually made their final error probability bound based on $x_{\\max}$ (Theorem 3), which is a kind of 'maximum diagonal entry of the covariance matrix.' I am wondering, if their theoretical result depends on this '$x_{\\max}', why don't they optimize this quantity? Why the authors should rely on the E-optimal experimental design and compatibility constant argument? \n\n\n2) Their problem relies on the assumption that they know the minimum signal, $\\theta_{\\min}$. It usually makes the problem much easier.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper deals with the best-arm identification problem in sparse linear bandits under the fixed-budget setting. \n\nAuthors designed a two-phase algorithm, Lasso and Optimal-Design- (Lasso-OD) based linear best-arm identification. \n\n1) The first phase of Lasso-OD leverages the sparsity of the feature vector by applying the thresholded Lasso [Zhou et al 2009], which estimates the support of the hidden parameter vector with high probability using rewards from the appropriate experimental design. \n2) The second phase of Lasso-OD applies the OD-LinBAI algorithm by Yang and Tan (2022) on that estimated support. \n\nFor fixed sparsity s and budget T, the exponent in the error probability of Lasso-OD depends on s but not on the dimension d which is noticeable. \n\nFurthermore, the authors show a lower bound for this problem and tried to express minimax optimality in their result. \n\nFinally, the authors provide numerical examples to demonstrate the significant performance improvement over the existing algorithms for non-sparse linear bandits.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1) (Minor) I hope authors justify why they should rely on the E-optimality instead of $x_{\\max}$. If they could optimize $x_{\\max}$ easily, it will be better for their theoretical performance. \\\\\\\\\n\n\n2) (Minor) I hope the authors state the scale difference between the 'minimum eigenvalue', 'compatibility constant' they approximated, '$x_{\\max}$, and 'H*' in the PopArt paper. According to my understanding, these are the quantities that depend on the geometry of the action set and determine the error of the regression. Especially, it would be great if they could find an example that $x_{\\max}$ shows a big difference with other action set geometry constants (like minimum eigenvalue).\\\\\\\\\n\n3) (Minor) I hope authors include 'minimum signal' related arguments. What happens when the agent doesn't have the minimum signal assumption? Please let me know if I missed this argument. \\\\\\\\\n\n4) (Minor) How far is the 'relaxed optimization' of MIDCP in Appendix A versus the true compatibility constant? What about the gap between the result of QP after relaxing the $l_1$ norm condition versus the true compatibility constant?\\\\\\\\\n\n5) (Minor) What happens if we apply Thresholded lasso in a sparse linear fixed-confidence BAI problem and use the existing fixed-confidence BAI algorithm, as you did in a fixed-budget setting? Would it easily derive a new sparse-linear fixed-confidence BAI? What is the major difference or difficulty in this approach?", "broader_impact_concerns": "There are no concerns about ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "aflAFNzjwj", "reviewer": "Reviewer_EjKY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper aligns well with the existing work around fixed BAI algorithm and covers the literature properly.\n2. The error bounds are compared to similar algorithms and proven to be SOTA.\n3. Extensive experimental results demonstrate the behavior of the algorithm properly.\n\nWeaknesses:\n1. The paper does not include real-world dataset experiments to study the robustness of the algorithm w.r.t its assumptions.\n2. A simple benchmark that could be used is to replace the OD-LinBAI algorithm with other FB-BAI algorithms. This is also missing.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers the problem of finding the arm with largest reward mean in a linear bandits environment given a fixed budget of samples. The paper also bounds the error probability of their algorithm showing it depends on the sparsity parameter. Experimental results show the proposed algorithm outperforms the existing bechmarks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I suggest including few dataset experiments and comparing the algorithm to sparse algorithms by replacing OD-LinBAI with other FB-BAI algorithms.", "broader_impact_concerns": "Not needed.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers are in favor of accepting this paper: 

- The theoretical results are new, although the reviewers  think that the minimum signal condition somewhat makes the analysis straightforward. 

- The original experiments and the additional high-dimensional / real-world data experiments makes the experimental evaluation convincing overall.

- In the camera-ready version, please take into account an additional technical comment below: 

The presentation of the results needs more clarification. The reviewers and AE agree that that c_0 (19) in Corollary 1 can sometimes be O(1), but it seems not true for the standard basis action set example mentioned below (19) and in the rebuttal -- in that example isn't \phi^2 = \phi^2(1/d*I_d, s), and the best choice of \phi_0 is 1/d?

In defense of the paper's result, one can alternatively consider the hypercube action set A = {-1,+1}^d, in which case both x_max and \phi^2 are constant.

In view of this, we suggest that the authors provide detailed discussions on when c_0 is O(1), perhaps by supplying multiple examples.
Decision: Accept (poster)