Lasso Bandit with Compatibility Condition on Optimal Arm
Authors: Harin Lee
Taehyun Hwang
Min-hwan Oh
Venue: ICLR 2025 Poster (2025)
Keywords: Sparse linear bandits
Lasso
Regret analysis
Primary area: learning theory
TL;DR: We propose a Lasso bandit algorithm that achieves $\mathcal{O}(\text{poly} \log dT)$  regret bound based on the compatibility condition on the optimal arm.

Abstract: We consider a stochastic sparse linear bandit problem where only a sparse subset of context features affects the expected reward function, i.e., the unknown reward parameter has a sparse structure.
In the existing Lasso bandit literature, the compatibility conditions, together with additional diversity conditions on the context features are imposed to achieve regret bounds that only depend logarithmically on the ambient dimension $d$.
In this paper, we demonstrate that even without the additional diversity assumptions, the \textit{compatibility condition on the optimal arm} is sufficient to derive a regret bound that depends logarithmically on $d$, and our assumption is strictly weaker than those used in the lasso bandit literature under the single-parameter setting.
We propose an algorithm that adapts the forced-sampling technique and prove that the proposed algorithm achieves $\mathcal{O}(\text{poly}\log dT)$ regret under the margin condition.
To our knowledge, the proposed algorithm requires the weakest assumptions among Lasso bandit algorithms under the single-parameter setting that achieve $\mathcal{O}(\text{poly}\log dT)$ regret.
Through numerical experiments, we confirm the superior performance of our proposed algorithm.

Published as a conference paper at ICLR 2025
LASSO BANDIT WITH COMPATIBILITY CONDITION ON OPTIMAL ARM
Harin Lee"
Taehyun Hwang" Seoul National University th hww.g@snu....mmmmmm.mm........w. ac.
Min-hwan Ohf Seoul National University minoh@snu. ac kr
Seoul National University harinboy@snu.co krr
ABSTRACT
We consider a stochastic sparse linear bandit problem where only sparse sub- set of context features affects the expected reward function, i.e., the unknown reward parameter has a sparse structure. In the existing Lasso bandit literature. the compatibility conditions, together with additional diversity conditions on the context features are imposed achieve regret bounds that only depend logarith- mically on the ambient dimension d. In this paper, we demonstrate that even without the additional diversity assumptions, the compatibility condition on the optimal arm is sufficient to derive regret bound that depends logarithmically on d, and our assumption is strictly weaker than those used in the lasso bandit lit- erature under the Linle-parameter setting. We propose algorithm that adapts the sampllng technique and prove that the proposed algorithm achieves (poly log d'T) regret under the margin condition. To our knowledge, the pro- posed algorithm requires the weakest assumptions among Lasso bandit algorithms under the singleparamettr setting that achieve Oppoly log d'(') regret. Through numerical experiments, we confirm the superior performance of our proposed al- gorithm.
INTRODUCTION
Linear contextual bandits (Abe & Long 1999 Auer 2002 Chu et al. 2011 Lattimore & Szepesvári 2020 are a generalization of the classical Multi Armed Bandit problem (Robbins) 1952 Lai & Robbins 1985). In this sequential decision making problem, the decision decision-making agent is provided with a context in the form of feature vector for each arm in each round, and the expected reward of the arm is linear function of the context vector for the arm and the unknown reward parameter. To be specific, {xt, E Rd k [K]]. Then, the agent selects an arm E [K] and observes sample of stochastic reward with mean 3", where 3 E Rd is fixed parameter that is unknown to the agent. Linear contextual bandits are applicable in various problem domains, including online advertising, recommender systems, and healthcare applications (Chu et al.) 2011 Li et al.) 2016 Zeng et al. 2016 Tewari & Murphy, 2017). In many applications, the feature space may exhibit high dimensionality (d >> 1); however, only small subset of features typically affects the expected reward, while the remainder of the features may not influence the reward at all. Specifically, the unknown parameter vector 3 is said be sparse when only the elements corresponding to pertinent features possess non-zero values. The sparsity of 3 is represented by the sparsity index so = || d, where ||x||o denotes the number of non-zero entries in the vector x. Such a problem setting is called the sparse linear contextual bandit.
each round E [T] = {1, [1...., T}. the agent observes feature vectors of the arms
3",
There has been large body of literature addressing the sparse linear contextual bandit prob- lem (Abbasi- Yadkori et al. 2012)] Gilton & Willett 2017: Wang et al. (0018) Kim & Paik 2019
Bastani Bayati] 2020 Hao et al. 2020b) et 2021 Oh et al. [021] Ariu et al.] [022, Chen
et al. 2022 Li et al. 2022 Chakraborty et al.) 2023). To efficienlly take advantage of the sparse
structure, the Lasso [Tibshirani] (996) estimator is widely used to estimate the unknown parame-
ter vector. Utilizing the -error bound of the Lasso estimation, many Lasso-based linear bandit
"Equal contribution
I "Correponndigg author

---

Published as a conference paper at ICLR 2025
algorithms achieve sharp regret bounds that only depend logarithmically the ambient dimension
d. Furthermore, a margin condition (see Assumption 2 is often utilized to derive an even poly- logarithmic regret in the time horizon, thereby achieving (poly))logarithn)
dependence both d
and 7' simultaneously (Bastani & Bayati 2020 Wang et al. 2018 Li et al. 2021 Ariu et al. 2022
Li at. 2022 Chakraborty et al. 2023).
While these algorithms attain sharper regret bounds, there is no free lunch. The analysis of the existing results achieving (poly log d'T') regret heavily depends on various stochastic assumptions on the context vectors, whose relative strengths often remain unchecked. The regret analysis of the Lasso-based bandit algorithms necessitates satisfaction of the compatibility condition (Van De Geer & Bühhmann 22099 for the empirical Gram matrix Σ, Xt,,,X4,0, constructed from previously se- lected arms, Ensuring this compatibility- -or an alternative form of regularity, such as the restricted eigenvalue condition for the empirical Gram matrices requires an underlying assumption about the compatibility of the theoretical Gram matrix, e.g. & E xx,, Moreover, to establish regret bounds, additional assumptions regarding the diversity of context vectors e.g.. anti-concentration, relaxed symmetry, and balanced covariance are made (refer to Table for a comprehensive com- parison). Many these assumptions are needed solely for technical purposes, and their complexity often obscures the relative strength of one assumption over another. Thus, the following research question arises:
X
Question: Is it possible to construct weaker conditions than those in existing conditions achieve Opooyy log d'T) regret in the sparse linear contextual bandit (under the
setting)?
In this paper, we provide affirmative answer to the above question. We show that (i) the compati- bility condition on the optimal arm is strictly weaker than the existing stochastic conditions imposed on context vectors for (poly log d''') regret in the sparse linear bandit literature (under the single- paramcter setting). That is, the existing conditions in the relevant literature imply our proposed compatibility condition on the optimal arm, but the converse does not hold (refer to Figure I]. Ad- ditionally, (ii) we propose an algorithm that achieves (pooyy log dT) regret under the compatibility condition on the optimal arm combined with the margin condition. Therefore, knowledge, the compatibility condition on the optimal arm that we study in this work - combined with the margin condition- - the mildest condition that allows O(poly log dlT) regret for sparse linear contextual bandits (Oh et al. 2021 Li et al. 2021 Ariu et al. 2022 Chakraborty et al. 2023)
the best of our
Our contributions are summarized follows:
We propose forced-sampling- based algorithm for sparse linear contextual bandits: FS-WLasso. The proposed algorithm utilizes the Lasso estimator for dependent data based on the compatibility condition on the optimal arm. FS- FS-WLasso explores for number of rounds by uniformly sampling context features and then exploits the Lasso estimated ob- tained by weighted mean squared error with fi-penalty. We establish that the regret bound of our proposed algorithm is Oppoly log d'").
One of the key challenges in the regret analysis for bandit algorithms using Lasso is en- suring that the empirical Gram matrix satisfies the compatibility condition. Most existing sparse bandit algorithms based on Lasso not only assume the compatibility condition on the expected Gram matrix, but also impose an additional diversity condition for context features (e.g., anti-concentration, relaxed symmetry, and balanced covariance), facilitating automatic feature space exploration. However, we show that the compatibility condition on the optimal arm is sufficient to achieve (pooyy log d'')) regret under the margin condi- tion, and demonstrate that our assumption on the context distribution strictly weaker than those used in the existing sparse linear bandit literature that achieve Oppoly log d'T') regret. We believe that the compatibility condition on the optimal arm studied in our work can be of interest in future Lasso bandit research.
To establish the regret bounds in Theorems we introduce a novel analysis technique based on prooabbbbbyblitt analysis that utilizes mathematical induction, which captures the cyclic structure of optimal arm selection and the resulting small estimation errors. We believe that this new technique can be applied to the analysis of other bandit algorithms and therefore can be of independent interest (See discussions in Section 3.3).
We evaluate our algorithms through numerical experiments and demonstrate its consistent superiority over existing methods. Specifically, even in cases where the context features of
2

---

Published as a conference paper at ICLR 2025
Table 1: Comparisons with the existing high-dimensional linear bandits with a single parameter
setting. For algorithms using the margin condition, we present regret bounds for the 1-margin (for
simple exposition). We define Σ := E k=
K xx,x,,,), Σ == Ex k. for each & [K],
Dj of xf
x ma x 3 A.J. and X E xa; Taa
Paper
Computibility Eigenvalue
Margin
Additional Diversity
Regret
Kim & Paik 2019
Compatibility on Σ Minimum cigenvalue of Σ
X
x
(laoTloo(ddZ))
Hao ct al
20206
X
X
O((a,T log d))
Oh ct
2021
Compatibility
Relaxed symmetry & balanced covariance
(soyy ((oyTTlo()
Li el al
2021
Bounded sparse eigenvalue of Σj-
Ami-comeentration
O (s8(log(d))) log
Ariu et al.
2022
Compatibility E
Reluxed symmetty &
O O6glog dT))
Balanced covariance
Chakraburly et
2023
Maximum sparse eigenvalue En
Anti-comeentration
O (s log
This work
Compatibility on E
x
O (58(log(())) log T)
Ariu et al. 2022) show a reggett bound of (sğ log su so) log I'), but they implicitly assume that the & norm of feature is bounded by &A when applying the Cauchy-Schward inequality in their proof Lemma
5.8. We display the regret bound when only the foe norms of features are bounded.
all arms except for the optimal arm are fixed (thus, assumptions such as anti-concentraation are not valid), our proposed algorithms outperform the existing algorithms.
1.1 RELATED LITERATURE
Although significant research has been conducted on linear bandits (Abe & Long. 1999, Auer 2002
Dani et al. 2008 |usmevichientong & Tsitsiklis 2010
et al., 2011 Chu et al.
2011 Agrawal & Goyal 2013 & Lazaric 2017 K Kveton et al.) 2020a) and generalizer Seneralized lin-
ear bandits (ilippi et al. 2010 Li et al. 2017] Faury et al. 2020 K Kveton et al. 2020b Abeille
jet al., 2021 Faury al. 2022). applying them to high-dimensional linear contextual bandits poses challenges in leveraging the sparse structure within the unknown reward parameter. Consequently, might lead to regret bound that scales with the ambient dimension d rather than the sparse set of features with cardinality sp. To overcome such challenges, high- nigh-dimensional linear contextual bandits have been investigated under the sparsity assumption and have attracted significant attention under different problem settings. |Bastani & Bayati (2020) consider a multipleparrametr parameter setting where each arm has its own underlying parameter and only one context vector is generated per round. Bastani & Bayati| (2020) propose Lasso Bandit that uses the forced sampling technique (Golden-) shluger& & Zeevi, 2013) and the Lasso estimator [Tibshirani 1996). They establish a regret bound of O(K (log d'))² where K is the number of arms. Under the same problem setting as Bas- tani & Bayati 2020), Wang et al. (2018) propose MCP-Bandit that uses uniform exploration for Os% log(d?)) rounds and the minimax concave penalty (MCP) estimator (Zhang 2010). They show the improved regret bound of Osg((og d + 8o) log
On the other hand, there has also been amount of work in the single-parameter setting where K different contexts are generated for each arm at each round and the rewards of all arms are determined by one shared parameter. Kim & Paik (2019) leverage a doubly-robust technique (Bang & Robins 2005) from the missing data literature to develop DR Lasso Bandit, t. achieving regret upper bound of O(so (osvTloogdd))) Oh et al. (021) present SA LASSO BANDIT, which requires neither knowledge of the sparsity index nor an exploration phase, enjoying the regret upper bound Ariu et al. (2022) design TH Lasso Bandit, adapting the idea of Lasso with thresholding, originally proposed by Zhou (010)). This algorithm estimates the unknown reward parameter along with its support, achieving regret bound of O( log d'T) under the 1-margin condition (Assumption] 2) All the aforementioned algorithms rely on the compatibility condition of the expected Gram matrix for the averaged arm, denoted by Σ := k [E)EE(( X Moreover, Oh et al. 2021); 1 Ariu et al. (202) impose strong conditions on the context distribution, such as relaxed symmetry and balanced covariance (Assumptions (ndd There is another line of work that combines the Lasso estimator with exploration techniques in the linear bandit literature, such as the
of O(so Vo
upper confidence bound (UCB) or Thompson sampling (TS). [i al. (221) introduce algorithm
3

---

Published as a conference paper at ICLR 2025
that constructs el-confieence ball centered at the Lasso estimator, then selects optimistic arm from the confidence set. CChakraborty et al. (2023) propose a Thompson sampling algorithm that utilizes the sparsity-inuucing prior suggested by Castillo et (2015) for posterior sampling. Under assumptions such as the general margin condition, bounded sparse eigenvalues the expected Gram matrix for each arm, and anti-concentration conditions context features, both Li al. (202T) and Chakraborty et al. (203)) achieve a (pooyy log d'I') regret bound. Hao et al. (2020b) propose ESTC, an explore-then-come comeit paradigm algorithm that achieves regret bound of OO log d) it) under the fixed arm set setting. [L al. (2022) introduce a unified algorithm framework named Explore-
the-Structure Trrrcture-Then---ee Commit for various high- -ige-dimensional stochastic bandit problems. Li et al. (2022
establish regret bound of (s ((s)7) T Vlog(dT)) for the Lasso bandit problem. Chen et al. (2022)
propose SPARSE-LINUCE algorithm, which estimates the reward parameter using the best subset selection method based on generalized support recovery.
2 PRELIMINARIES
Notations. For a positive number N, we denote [M] as set containing positive integers up N, i.e, [N] == (1...., Nj. For vector E IR. we denote its j-th component by ny for j E [d]. its transpose by v its norm by llv|lo E}E{ [ * 0}, its f2-norm by ||v 12 vv Tv v. and its 20- -nom by ||v|l=- = maxje l1yl- For each I C [d] and v E Rdd = [ei.I,....
ea,z]" ed.1 where for all j E [d]. Ug.r vy 1i E /}. Refer to Appendix A for a more detailed explanation of the notations.
Problem Setting. We consider stochastic linear contextual bandit problem where 7' is the number of rounds and K (2 3) is the number of arms. In each round E [2], the learning agent observes set of context features for all arms {x,,; E X : E [K]} C I drawn i.i.d. from an unknown joint distribution, chooses an arm ag E [K], and receives a reward Tt,a,- We assume that Tt.o. = =x 3* + Ne where 3 E Rd is the unknown reward parameter and пe random variable such that F[n1[F--1] = O for the sigma-algebra F, generated by (fx,,, (xx],)))(((
independent r-sub-Gaussii
(ar Freit) {rr,-- }rese-1)),i.. EE [e [J,] S e000²/2 /2 for all IR. We assume {x xt, f is a sequence of i.i.d. samples from some unknown distribution Dx on the Lebesgue measurable sets. Note that dependency across arms
given round is allowed. We also define the active set So {j 3 # 0} as the set of indices j for which B3 is non-zero. Let Sp := Sol denote the cardinality of the active set So, which satisfies 80 < d.
Define of == argmax x as the optimal arm in round t. Then, the goal of the agent is to minimize the following cumulative regret:
T
R(T) Σ
(x
-x
2.1 ASSUMPTIONS
We present list of assumptions used for the regret analysis later in Section 3.2
Assumption (Boundedness). For absolute constants Imaxx b >> assume ||x| S Fmax for all x E X, and || [| & b, where may be unknown.
Assumption 2 (a-margin condition). Let D = xT,a; 3 8" maxk4a; xT be the instantaneous
gap in round For > 0, there exists a constant A. O such that for any h. >> O and for all t E PA < h)
< h
Assumption 3 (Compatibility condition on the optimal arm). For a matrix M E Rdxd and a set I C [d], the compatibility constant 6MM, 1) is defined as
[/33 M3
3 (M,
1) min B
[13 S 3311/111 #
1
Let us denote the context feature for the optimal arm in round by Xt,o; Then, assume that the expected Gram matrix of the optimal arm Σ" = E[xx,a; x[o]]] satisfies the compatibility condition

---

Published as a conference paper at ICLR 2025
Ob (2021)
(2021)
Aria (2422)
Chakrabocty (2023)
Compaibility on
Caussian fentures
Sparse posiiive definiteness
Gob-Gaussiam featunes Maximum spanse digetovalue of E, for each & & [K] Anti-conoentration
Relased symmetry
Bounded sparso eigenvalue of Ei for each E [K] Anticomeenmtioo
Compatiblliy on Relased symmetry
Halanced covariance
Halanced covariacce
Bounded sparse eigenvalue of Xi
imply
implics
implies
imply
cannot imply
imply
implies
implics
No margin cundition cueset
This wurk
Opply log di regret
Compatibilit E" (Assumption 3)
Margin condition
can derive
Bounded features
Olpoly cfT) regret bound
Illustration of relationships among distributional assumptions context used in the sparse linear contextual bandit literature. The blue arrows represent implication relationships while the red arrows represent infeasible implication relationships. The conditions written in blue with the check bullet / in the figure imply the compatibility on the optimal arm (Assumption 3). serving as suffi- cient conditions, while the conditions written in orange indicate additional assumptions necessary to achieve the existing methods' regret guarantees, but not needed in our analysis. The case where all sub-optimal arms are fixed serves as a counter-example for the infeasible implication relationships. We provide the proofs of the implication relationship in Appendix B which may be of independent interest.
Figure 1:
with o. O. ie., o² (E",,"" i..dd for each round.
So) 2 22. Note that En is
since the set of features is drawn
Discussion of assumptions. Assumption 1 is standard regularity assumption commonly used in the sparse linear bandit literature (Bastani & Bayati 2020 Hao et al.) [2020b; Ariu et al. [022] Li al. 2022 Chakraborty al., (023). It indicates that both the context features and the true parameter are bounded.
Assumption resstrictss the probability that the expected reward of the optimal arm is close those of the sub-optimal arms. To our best knowledge, the margin condition in the bandit setting was first introduced in Goldenshluger & Zeevi (2013) and is widely used in linear contextual bandit literature (Wang et al. 2018 Bastani & Bayati 2020, Papini et al. 2021 Li et al.) 2021 Bastani al.) [ et al. 2022] Chakraborty et al. 2023). Unlike the minimum gap condition (Abbasi- Yadkori et al. 22111 Papini et 20211. which prohibits the instantaneous gap from being smaller than a fixed constant, the margin condition allows a probability of a small gap. The case where 0 imposes no additional constraints, while
is equivalent to the minimum gap condition. The margin condition with general a smoothly bridges the cases with and without the minimum gap.
Assumption 3 is related to the compatibility condition used to guarantee the convergence property of the Lasso estimator in the high-dimensional statistics literature (Bühlmann & Van De Geer 2011). Since the compatibility condition ensures that the Lasso estimator approaches its true value as the number of samples grows large, many pieces of high-dimensional linear contextual bandit literature
assume the condition (Wang al.] 2018 Kim & Paik 2019 Bastani & Bayati] 2020 Oh al.) 2021]] Ariu et al. 2022). Kim & Paik 2019): Oh al. (2021): Ariu et al. (2022) assume the compatibility EL x, Li et (2021) assume the minimum sparse eigenvalue of
condition on Σ R
when the instantaneous gap is greater than constant A., whose definition slightly differs from ours. Unlike previous works, we assume the compatibility condition on the optimal arm without any constraints. Under this assumption, theoretical guarantee about the convergence of the Lasso estimator can be derived only if sufficient selections of the optimal arms are guaranteed, which necessitates more technical analysis. On the other hand, most of the previous work in sparse linear bandit that achieves poly- poly-logari regret under the margin condition implicitly assumes Assumption 3 indicating that our ussumptions are strictly weaker than others.
the expected Gram matrix of the optimal
5

---

Published as a conference paper at ICLR 2025
Algorithm -Lssos (Forced-Sumplinge then Weighted Loss Lasso)
1: Input: Number of exploration Mo. Weight w, Regularization parameters { 1ete22
2: for t === 2,,.... do
3: Observe {xt,*
4: if I. & Mn then
v Forced sampling stage
5:
Choose ar ~ Uni and observe T2,0.
6: else
Greedy selection stage
Ma
7:
Compute B,-1 = argmin w
( Tx, ri ) )
Σ
(x 3 - riaa)) + Ae- ||
B
== Mo+1
8: Select a, = argmax x, x,, B,1 and observe Tt,ar
9:
end end for
10:
Theorem 1. The compatibility condition on the optimal arm (Assumption 3 is strictly weaker than the assumptions made in previous Lasso bandit works under the single-parameter setting (Oh et al.
2027 Li et al. 2021 Ariu et al. 2 Chakraborty el al. 2023), as illustrated in Figure 7
Discussion of Theorem
al. (2021): Ariu et al. (022) assume the relaxed symmetry and
balanced covariance of the context features, while other works in the literature, such as Li et al.
(2021); Chakraborty et al.] (2023) assume an anti-concentration condition for the feature vectors. These conditions imply that estimation error is reduced when data is obtained by greedy policy, in some cases, by any policy. Since choosing the optimal arm is also a greedy policy with respect to the true parameter, the assumptions in prior works imply ours. The case where the context feature vectors of sub-optimal arms are fixed and only the feature vector of the optimal arm has randomness refer to Appendix B
indicates that the converse does not hold. For detailed proof of Theorem 1
Remark 1. Under the multiple-parameter setting, Bastani & Bayati 2020 Wang et al. (2018) assume the compatibility condition on the feature vectors whose instantaneous gaps are lower- bounded by h. On the other hand, we impose such constraint in Assumption f the single- parameter setting. Further direct comparisons of the compatibility conditions are not possible since compatibility conditions do not translate directly across the two different settings. However, we show that Assumption] 3 is weaker than those Bastani & Bayati (2020); Wang et al. (2018) when compared within the problem instances that are convertible to both settings through a certain con- version (Kim & Paik 2019 Oh et al.) (027]. Refer to Appendix [for more details. It is important to note that we mainly compare our results with the Lasso bandit results under the which is the pre-
setting (Oh et al.) 2027 [i et al. 2 Ariu et a [2022] (Chakraborty et al.|
dominant setup in linear contextual bandits (Abbasi- Yadkori et al. [001] Abeille & Lazaric 2017
Chakraborty et al. 2023 Filippi et al. 2010 Hao et al. 2020b Kim & Paik 2019
Li et al. 2021
Oh et al. 2021).
3 FORCED SAMPLING THEN WEIGHTED LOSS LASSO
3.1 ALGORITHM: FS-WLASSO
In this section, we present FS-WLasso (Forced Sampling then Weighted Loss Lasso) that adapts the forced-sample saceddsampling technique (Goldenshluger Zeevi 2013 Bastani & Bayati| (020). FS-SLasso consists of two stages: Forced sampling stage & Greedy selection stage. First, during the Forced sampling stage the agent chooses an arm uniformly random for M, rounds. Then, for in the Greedy selection stage, the agent computes the Lasso estimator given by
B argmin argminwLo(3) + (B-1 + Ao- 1|
(I)
where Ta( = Me (x] _0, β - ria;; is the sum of squared errors over the samples acquired
through random sampling. ( = Ei= M1+ (xT., - ) is the sum of squared errors over the samples observed in the Greedy selection stage, is the weight between the two loss functions,

---

Published as a conference paper at ICLR 2025
and A--1 O is the regularization parameter. The agent chooses the arm that maximizes the inner product the feature vector and the Lasso estimator. FS-WLasso is summarized in Algorithm
Remark 2. Both FS-WLasso and ESTC (Hao et al. 2020b) have exploration stages, where the agent randomly selects arms for some initial rounds. However, the commil stages are very different. ESTC estimates the reward parameter only using the samples obtained during the exploration stage and does not update the parameters during the commit stage. whereas fS-WLasso continues to update the parameter using the samples obtained during the greedy selection stage. Therefore, our algorithu demonstrates superior statistical performance, achieving lower regret (and thus higher reward) by fully utilizing all accessible data.
Remark 3. The minimization problem [ takes the sum of squared errors, whereas the standard
Lasso estimator takes the average. While X, typically chosen be proportional to /1/t in the
existing literature (Bastani & Bayati 2020; Oh et al. [027] Ariu et al. 2022 Li et al. 2027). this
slight difference leads to x being proportional to vl Theorems and
3.2 REGRET BOUND OF FS-WLASSO
Definition (Compatibility constant ratio). Let Σ = K E ke(K) Xt, be the expected Gram
matrix of the averaged arm. We define the constans p = 60/0² E, So) as the ratio of the compati- bility constant for Σ" the compatibility constant for E.
By the definition of E, it holds that E K [[x,, x1,031, which implics So) 2 ( 2 O./K > 0. Hence, p is well- defined with 0 < p I K.
K E|x,, x xT,; + 1 EE x >
1
Remark 4. When comparing the compatibility conditions only, the compatibilityy condition on the optimal arm implies the compatibility condition on the averaged arm. However, that is not the essence of what we compure between our work and the existing works. Note that under the margin condition, the entire set of stochastic context assumptions (e.g.. the compatibility condition along with additional diversity assumptions) in the previous literature implies the compatibility condition on the optimal arm, as illustrated in Figure and demonstrated in Appendix B
We present the regret upper bound of Algorithm are deferred to Appendix F.2
A formal version of the theorem and its proof
Theorem 2 (Regret Bound of FS- FS-WLasso). Suppose Assumptions hold. For 8 (0, 1). let be a constant that depends on Tmax, 80, &o, a, at A., log d, log If we set the input parameters of Algorithm b
Mo = C, max (p'x 1max 100 log(d/0) 2²00 4+4 2+ Emak s
" - (loglog bogglog+oogd//// log(d/8)) )
A C2 (V(- Mo) log (d(log(l M8))
V Mo log(d/0) , VT/Mo,
for some universal constants C₁ C2 > O, then with probability least - 8, Algorithm 7 achieves the following cumulative regret:
R(T)= S 2xmaxbM + I Ir,
where 1, = O (02A-1
(1 (1 / (02) 1+ log(d/6) and
1
0
-: (logd + log Tog
for a (0,1),
Av(1-o)
IT
0
(ox2 00
log T (log dl + log lng T
for =
mms 2o 2 22 (log d + log +)
for < a 5a500 80.
1a-1y
In terms of key problem instances (So. d, and T), Theorem 2 eestablshess the regret bounds that scale poly-logarithmically d and T, specifically, (( IT (log d +
Discussion of Theorem 2
7

---

Published as a conference paper at ICLR 2025
log log T) + for a E (0, 1). ( log (log d + log T)) for a = 1, and (150 log d) for a > et al. (2021) construct regret lower bound of O (log - + log T) when e 1]. which our algorithm achieves up to log factor. The expected regret for Algorithm can also be obtained by taking 6 = 1/TT. For the T T-agnostic setting, we derive FS-Lasso, which uses forced samples adaptively, and establish the same regret bound as in Theorem 2 (Appendix F). Existing Lasso bandit literature that achieves Oppoly log d'T) regret under the single parameter set- ting necessitates stronger assumptions the context distribution (e.g., relaxed symmetry & bal- anced covariance or anti-concentration), which are non-verifiable in practical scenarios. In addition, when context distributions do not satisfy the strong assumptions employed in the previous literature, the existing algorithms can critically undermine regret performance, with no recourse for adjustment nor guarantees provided. That is, there is nothing one can do when such strong context assumptions are not satisfied in the existing literature. However, we show that the compatibility condition on the optimal arm is sufficient to achieve poly-togarithmic regret under the margin condition, and demon- strate that our assumption is strictly weaker than those used in other Lasso bandit literature under the single-parameter setting.
2+ 2
Our result also improves the known regret bound for the low-dimensional setting, where so may be replaced with d. In this case, Assumption] 3 becomes equivalent to the HLS condition (Hao et al.) 2020at Papini et al. 2021I. Under the HLS condition and the minimum gap condition, [Papini et al. (202T) show that OFUL (Abbasi-Yadile
et al.] (011] achieves a constant regret bound independent of with high probability (Lemma 2 in (Papini et al.. 2021b). However, when the margin condition (Assumption 2 is assumed, the result of Papini et al. 2021) guarantees Ollog T) regret bound only
when > 2. Our algorithm achieves constant regret bound with high probability when a 1, expanding the range of a that the constant regret is attainable.
the value of so when determining Mo. the length of the forced sam- pling stage. On the other hand, there are sparsity-agnostic Lasso bandit algorithms (Oh et al. [202]] Ariu et al. 2022 Chakraborty et al.) 2023). However, these sparsity-agnoster algorithms require stronger diversity assumptions on the context distribution that are not verifiable in practice. Even when the sparsity is known, other works in the literature still either incorporate extra stochastic conditions (Li et al.] (2027) or apply specific optimality criteria for context distributions (Bastani) & Bayali 2020 Wang el al. 20188. As discussed earlier, these additional assumptions may pose obstacles in practical applications. Regardless of sparsity sparsity-awarenes. awareness, our work focuses on alleviat- ing these stringent stochastic assumptions on context distributions, providing the weakest conditions known to achieve poly-logarithmns regret. Furthermore, by tuning My as whole, not knowing the sparsity does not worsen the complexity nor the performance of the algorithm in practice. Mg does not solely depend on so, but also on other problem-dependent factors that may be unknown to the algorithm in practice and hence Mo should be regarded as a tunable parameter. Note that all Lasso bandit including the sparsity agnostic ones and parametric bandit algorithms also have parameters that must be tuned in practice, such as the ones that depend on the sub- -auussasn parameter of the noise Refer to Appendix forr more details.
Remark 5. Theorem2requiie
In most regret analyses of sparse linear bandit algorithms under the single-parameter setting (Kim & Paik 2019;] Li et al., 2021 Oh et al., |021] Ariu et al. 2022 Chakraborty et al. (2023). the maximum regret is incurred during the burn-in phase, where the compatibility condition the empirical Gram matrix is not guaranteed. The compatibility condition after the burn-in phase is ensured by additional
diversity assumptions on context features (e.g., anti-concentration (Li al. 2021 [ Chakraborty et al,, 2023), relaxed symmetry & balanced covariance (Oh et al. 2021 Ariu al.) (022)), rather than by explicit exploration within the algorithms. Therefore, the Lasso estimator calculation (Oh et al.,
2021 Ariu et al. 2022) or explicit exploration (UCB in Li et al. (2021) or TS in Chakraborty et al. (003)) ) during their burn-in phases does not contribute to the regret bound.
On the other hand, our forced sampling stage does not compute parameters but acquires diverse samples without requiring diversity assumptions on context features beyond the compatibility con- dition on the optimal arm, making it more efficient during the burn-in phases. If additional diversity assumptions (Li et al. 2021; Oh et al. 2021 Ariu et al., 2022; Chakraborty et al. (023) are also applied to our algorithm, we show that (poly log T') regret achieved without the forced sampling stage in Algorithm [
Theorem 3. Suppose that Assumptions 3 hold, and further assume either the anti-concentration (Assumption 4) or relaxed symmetry & balanced covariance (Assumption ( assumptions. Let @G be an appropriate constant that is determined by the employed assumptions, and be constant
8

---

Published as a conference paper at ICLR 2025
that depends on 0, Fmax su. A.. 6x, GG. a, log d. and log ö. If we set the input parameters of Algorithm by Mo 0, i.e. no parced-sampling stage, and X Z2 Vtlog (d(log (|llog))///) where C2 the same universal constant in Theorem 2 then with probability at least 1 6, Algorithm achieves the following cumulative regret with probability at least 8:
R(T) < I + (2(
T
12T I T>T,
where
To O (1 (mmax bogd -1 (log(fmaxSodbe)) log d - -log))
0
(owan #0/ #0/
T
1 (log d log To
1tc
for (0,1).
(1-
T2( =
o
(aa 20/2
log T logg + log log
for = 1,
m00 A.
(log d + log )
for 1 <<<< 00,
(a-1)z
and Iy lakes the same value as in Theorem
Discussion of Theorem 3 Theorem 3 offers that random exploration of Algorithm may not be necessary if the additional diversity assumptions on context features are given. This result indicates that the number of exploration may be tuned according to the specific problem instance. The as- sumptions of the Theorem 3 are still weaker than, or equally strong Oh et al. (2021); Li et al. (2021): Chakraborty et al. (2023). while the regret bounds are no greater than theirs. We slightly improve the regret bound of Li et al. (202I) when 1 < S co. Specifically, term proportional to < -8/(A.))) in Li et al. (2021) is sharpened to 1+4 /(A.0, 2+
in our result. We also achieve a tighter regret bound than Chakraborty et al. (2023), which is proportional K1, Our result is proportional to most K² since o; 2 ( holds under their assumptions, as shown in Lemma] |
3.3 TECHNICAL CHALLENGES AND SKETCH OF PROOFS
Under Assumption 3 small estimation error of 3 is ensured when the optimal arms have been chosen a sufficient number of times. Specifically, if the optimal arms have been selected sufficiently many times up to round f, it ensures the compatibility constant of the empirical Gram matrix is (()2)). Then, the Lasso estimation error can be controlled via the oracle incquality for the weighted squared Lasso estimator (Lemmaa 19p. A well-estimated estimator, in turn, leads to the selection of the optimal arm in the next round. This observation highlights the cyclic relationship between estimation error and the selection of optimal arms. However, this is not case of cireular reasoning; rather, it is a domino-like phenomenon that propagates forward in time.
On the other hand, such cyclic structure has not been observed in previous Lasso bandit litera- ture (Bastani & Bayati| 2020 Ohh et al. 2021 Li et al. 2021 Ariu et al., 2022 Chakraborty et al.) 2023). This is because existing methods rely on diversity assumptions on the context distribution, which ensure that samples obtained by the agent's policy automatically explore the feature space, resulting in a positive compatibility constant for the empirical Gram matrix regardless of the pre- viously selected arms. However, since such convenience is no longer available in our setting, we meticulously analyze the eyclic structure between the estimation error and the selection of optimal arms by deriving novel mathematical induction argument.
There are three main difficulties that lie in the way of constructing the induction argument. First, the initial condition of the induction must be satisfied, in other words, the cycle must begin. We guaran- tee the initial condition through random exploration (Theorem or additional diversity assumptions (Theorem 3). We show that after the initial stages, the algorithm attains a sufficiently accurate es- timator, which starts the cycle. Second, the algorithm must be able to propagate such favorable events to the next round. A small estimation error does not always guarantee the selection of the optimal arm. Instead, we show that it leads to a bounded ratio of sub-optimal selections over time. The compatibility condition the optimal arm implies that if the optimal arms constitute large

---

Published as a conference paper at ICLR 2025
Corrllated Gaussian, d 100, S, -
Rixd Sub-aptimal Arms, 100, 20,
Laso
S4 Lasse
SA Losso
Lassa
TH TH-La950
200
ESTC
L1-CB-
ESTC
PS WLasso (0urs)
Gomubable begnet
WLasss 10uns)
P5 Lasso (0urs)
Lasso 10urs)
150
Coruuaale
200
203
50
$10
1000
1750
750 1250
2002
(a) Experiment
Experiment 2
Figure 2: The evaluations of Lasso bandit algorithms are presented. Figure 2a shows results where all context feature vectors are sampled from correlated Gaussian distribution. Figure (2b shows results where the context feature vectors of sub-optimal arms are fixed throughout time, and only the feature vector of the optimal arm has randomness. We plot the mean and standard deviation of cumulative regret across 100 runs for each algorithm.
portion of the observed data, the algorithm attains small estimation enror. We build induction argument upon these relationships. Lastly, due to the stochastic nature of the problem, the algorithm suffers small probability of failing to propagate the good events in every round. Without careful analysis, the sum such probabilities easily exceeds I, invalidating the whole proof. We bound the sum to be small by carefully constructing high-probability events that oceur independently of the induction argument, then prove that the induction argument always holds under the events. The complete proof is illustrated in Appendix F
NUMERICAL EXPERIMENTS
We perform numerical evaluations synthetic datasets. We compare algorithms, PS-WLasso and FS- with sparse linear bandit algorithms including DR Lasso Bandit (Kim & Paik, 2019) SA Lasso BANDIT (Oh et al. 2021). TH Lasso Bandit (Ariu et al. 2022). C-Conndeence Ball Based Algorithm (L1-CB-Lasso (Li et al. 2021), and ESTC (Hao et al. 20206). We plot the mean and standard deviation of cumulative regret across 100 runs for each algorithm.
The results clearly demonstrate that our proposed algorithms outperform the existing sparse linear bandit methods we evaluated. particular, even in cases where the context features of all arms, except for the optimal arm, are fixed (rendering assumptions such anti-concentration invalid), our proposed algorithms surpass the performance of existing ones. More details are presented in Appendix I
5 CONCLUSION
In this work, study the stochastic context conditions under which the Lasso bandit algorithm can achieve poly-logarithmic regret. We present rigorous comparisons on the relative strengths of the conditions utilized in the sparse linear bandit literature, which provide insights that can be of independent interest. Our regret analysis shows that the proposed algorithms establish a poly- logarithmic dependency the feature dimension and time horizon.
10

---

Published as a conference paper at ICLR 2025
6 REPRODUCIBILITY STATEMENT
For each theoretical result, we provide the full set of assumptions in the main paper (Section 2.1 and the complete proofs of the main results are provided in Appendix E and We have also in- cluded the data and code, along with instructions to reproduce the main experimental results, in the supplementary material.
ACKNOWLEDGEMENTS
This work supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. RS-2022-NR07188 1833 and RS-2023-00222663) and by Al-Bio Research Grant through Seoul National University.
REFERENCES
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24:2312-2320, 2011.
Yasin Abbasi-Yadken David Pal, and Csaba Szepesvari. Online-to-onfidenee-stt conversions and application to sparse stochastic bandits. In Artificial Intelligence and Statistics, pp. 1-9. PMLR, 2012.
Naoki Abe and Philip M Long. Associative reinforcement learning using linear probabilistic con- cepts. International Conference on Machine Learning, pp. 3-11, 1999.
Mare Abeille and Alessandro Lazaric. Linear Thompson Sampling Revisited. In Aarti Singh and Jerry Zhu (eds.), Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume of Proceedings of Machine Learning Research, pp. 176-184. PMLR, PMLR, 20-22 Apr 2017.
Mare Abeille, Louis Faury, and Clément Calauzènes. Instance-wise minimax-optimal algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pp. 3691- 3699. PMLR, 2021.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning, pp. 127-135. PMLR, 2013.
Kaito Ariu, Kenshi Abe, and Alexandre Proutière. Thresholded lasso bandit. In International Conference on Machine Learning, pp. 878-928. PMLR, 2022.
Peter Auer. Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research, 3(Nov):397-422, 2002.
Heejung Bang and James M Robins. Doubly robust estimation in missing data and causal inference models. Biometries, 644)999229 2005.
Hamsa Bastani and Mohsen Bayati. Online decision making with high digh-dimensional covariates. Operations Research, 68(1):276-22) 2020.
Hamsa Bastani, Mohsen Bayati, and Khashayar Khosravi. Mostly exploration-free algorithms for 2021.
contextual bandits. Management Science,
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 19-26. JMLR Workshop and Conference Proceedings, 2011.
Peter Bühlmann and Sara Van De Geer. Statistics for high--dimensional data: methods, theory and applications. Springer Science Business Media, 201
Ismaël Castillo, Johannes sparse priors. The Annals of Statisties, 2015.
and Aad Van der Vaart. Bayesian linear regression with
11

---

Published as a conference paper at ICLR 2025
Sunrit Chakraborty, Saptarshi Roy, and Ambuj Tewari. Thompson sampling for high- dinensiinnii sparse linear contextual bandits. In International Conference on Machine Learning, pp. 3979- 4008. PMLR. 2023.
Yi Chen, Yining Wang, Ethan X Fang. Zhaoran Wang, and Runze Li. Nearly dimension-indeeeedeen sparse linear bandit over small action spaces via best subset selection. Journal of the American Statistical Association, pp. 1-13, 2022.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff func- tions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208 214. JMLR Workshop and Conference Proceedings, 2011.
Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. Stochastic linear optimization under bandit feedback. In Annual Conference Computational Learning Theory, 2008.
Louis Faury, Mare Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algo- rithms for logistic bandits. In International Conference on Machine Learning, pp. 3052-3060. PMLR, 2020.
Louis Faury, Mare Abeille, Lwang--ung Jun, and Clément Calauzènes. Jointly efficient and op- timal algorithms for logistic bandits. In International Conference Artificial Intelligence and Statistics, pp. 546-580. PMLR, 2022.
Sarah Filippi, Olivier Cappé, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In Proceedings of the 23rd International Conference on Neural Informa- fion Processing Systems Volume 1, NIPS' 10, pp. 386-594, Red Hook, NY, USA, 2010. Curran Associates Inc.
Aurélien Garivier. Informational confidence bounds for self-normalized averages and applications. In 2013 IEEE Information Theory Workshop (ITW), pp. 1-5. IEEE, 2013.
Davis Gilton and Rebecca Willett. Sparse linear contextual bandits via relevance vector machines. In 2017 International Conference Sampling Theory and Applications (SampTA), pp. 518-522. IEEE, 2017.
Alexander Goldenshluger and Assaf Zeevi. A linear response bandit problem. Stochastic Systems, 3(1):230-261, 2013.
Botao Hao, Tor Lattimore, and Csaba Szepesvari. Adaptive exploration in linear contextual ban- dit. In International Conference on Artificial Intelligence and Statistics, pp. 3536-3545. PMLR, 2020a.
Botao Hao, Tor Lattimore, and Mengdi Wang. High-dimensional sparse linear bandits. Advances in Neural Information Processing Systems, 53:10753-10763 2020b.
Gi-Soo Kim and Myunghee Cho Paik. Doubly-robust lasso bandit. Advances in Neural Information Processing Systems, 32, 2019.
Branislav Kveton, Csaba Szepesvári, Mohammad Ghavamzadeh, and Craig Boutilier. Perturbed- history exploration in stochastic linear bandits. In Uncertainty in Artificial Intelligence, pp. 530- 540. PMLR, 2020a.
Branislav Kveton, Manzil Zaheer, Csaba Szepesvari, Lihong Li, Mohammad Ghavamzadeh, and Craig Boutilier. Randomized exploration in generalized linear bandits. In International Confer- ence on Artificial Intelligence and Statistics, pp. 2066-2076. PMLR, 2020b.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Ke Li, Yun Yang, and Naveen Narisetty. Regret lower bound and optimal algorithm for high- dimensional contextual linear bandit. Electronic Journal of Statisties, 15(2):565255655, 2021.
12

---

Mathematics of Published as a conference paper at ICLR 2025
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contex- tual bandits. In International Conference on Machine Learning, pp. 2071-2080. PMLR, 2017.
Shuai Li, Alexandros Karatzoglou, and Claudio Gentile. Collaborative filtering bandits. In Proceed- ings of the 39th International ACM SIGIR conference on Research and Development in Informa- tion Retrieval, pp. 539-548, 2016.
Wenjie Li, Adarsh Barik, and Jean Honorio. A simple unified framework for high dimensional bandit problems. International Conference on Machine Learning, pp. 12619- 12655. PMLR, 2022.
Min-hwan Oh, Garud Iyengar, and Assaf Zeevi. Sparsity-annostic lasso bandit. In International Conference on Machine Learning, pp. 8271-827888 PMLR, 2021.
Roberto Imbuzeiro Oliveira. The lower tail of random quadratic forms with applications to ordinary least squares. Probability Theory and Related Fields, 166: 175--1994, 2016.
Matteo Papini, Andrea Tirinzoni, Marcello Restelli, Alessandro Lazaric, and Matteo Pirotta. Lever- aging good representations in linear contextual bandits. In International Conference on Machine Learning, pp. 8371-8380. PMLR, 2021.
Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 1952.
Paat Rusmevichientong and John Tsitsiklis. Linearly parameterized bandits. Operations Research, 35(2):395-411, 2010.
Ambuj Tewari and Susan A Murphy. From ads to interventions: Contextual bandits in mobile health.
Mobile health: sensors, analytic methods, and applications, pp. 495-517, 2017.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology, (8(1) 58(1):267-288, 1996.
Sara A Van De Geer and Peter Bühlmann. On the conditions used prove oracle results for the lasso. Electronic Journal of Statistics, 2009.
Xue Wang, Mingcheng Wei, and Tao Yao. Minimax concave penalized multi-armed bandit model with high-dimensional covariates. In International Conference on Machine Learning, pp. 5200- 5208. PMLR, 2018
Chunqiu Zeng, Qing Wang, Shekoofeh Mokhtari, and Tao Li. Online context-aware recommenda- tion with time varying multi-arme bandit. In Proceedings of the 22nd ACM SIGKDD interna- fional conference Knowledge discovery and data mining, pp. 2025-2034, 2016.
Cun-Hui Zhang, Nearly unbiased variable selection under minimax concave penalty. The Annals of Statistics, 2010.
Shuheng Zhou. Thresholded lasso for high dimensional variable selection and statistical estimation. arXiv preprint 1002: 1002. 2010.
13

---

Published as a conference paper at ICLR 2025
Appendix
Table of Contents
Notations and Definitions
14
B
Discussion on Assumption 3 and Proof of T'heorem
16
Comparisons with
Setting
19
Additional Discussion on Sparsity-Awarenes)
22
E
Regret Bound of FS WLasso
23
E.1
Proposition
23
E.2 Proof of Theorem
27
E,3 Proof of Theorem
29
Proof of Technical Lemmas in Appendix E.1
E.
33
F
Forced Sampling with Lasso (FS-Lasso)
40
F
Algorithm: FS Lasso
40
F2 Regret Bound of Lasso
................................ ........
41
F3
Proof of Theorem 4
41
F4
Proof of Technical Lemmas
45
Technical Lemmas for Eppendices and
48
Oracle Incquality for Weighted Squared Error Lasso Estimator
49
Properties of Compatibility Constants)
Guarantees of Greedy Action Selection
52
Behavior of log log
52
G.5
Time-Unfoom Concentration Inequalities
55
Auxiliary Lemmas
57
Numerical Experiment Details
A NOTATIONS AND DEFINITIONS
We introduce notations that necessary for the analysis.
Linear Bandit
3 E Rdd True reward parameter
X Idd: Context feature vector round t, arm
X: Set of all possible context feature vectors
Dx: Distribution of context vectors tuple {xr, 1K
az Chosen arm in round t
: Optimal arm round
ms Rero-mean sub-Gaussian noise in round
Variance proxy of nt
Tt,a; xT, + m/ Observed reward in round
14

---

Published as a conference paper at ICLR 2025
reg. xi, -x, 3" -',
Instantaneous regret in round
d: Dimension of feature and true parameter vectors
K: Number of arms
T: Time horizon
Highh-Dimensiona Statistics
So == {i [d] : (8*), + #0}: Active set
8y == Soo Sparsity index
Uo.So 0y {j E So)
V (10 .... Vd.
Vsg = Vid
C(o)) {v Rd: s|vs S 33llvs
d² So): Compatibility constant of matrix M over set So
Note that the definition of compatibility constant in Assumption can be rewritten as (? infvec())(0.) Soy Mv
1
Assumptions
Tmax: -nom upper bound of E X'
b: nnrrr upper bound of 3
A, max
xi,a; ,.a"" :" Instantaneous gap
A, Margin constant, or relaxed minimum gap
Margin condition parameter
X Optimal arm feature random vector
Expected Gram matrix of optimal arm Ø.: Lower bound of d² (E",
x x
Algorithm
My: Number of random exploration rounds
Weight between square errors of random samples and greedy samples
A Lasso regularization parameter
B3 Lasso estimate 3
Analysis
6: Probability of failure
Σ = k=
X1,
xx 1.6
Theoretical Gram matrix of all arms
Σ/ == E x,
A.]:
Theoretical Gram matrix of optimal arm with large gap
Σx = x T
Theoretical Gram matrix of arm
t.
pi Compatibility constant ratio
V "Mot+ I wxtt,, x Et=Mo+1 Xt,a, XT., (Weighted) Empirical Gram matrix
N₂, (t'): Number of sub-optimal selections during / Mo Tı + 1 to Mo T +
Ag Upper bound of 2x || -Bll1
Fr: o-algebra generated by (x+,) ((( (ar (rria, bre(e11]
Ft: o-algebra generated by (x=_))=((q,ve]))) (ar) (rr,a )reje)
15

---

Published as a conference paper at ICLR 2025
Generic notations
No = NU
[N] := (1.2..... J: Set of natural numbers to N
R Set of non-negative real numbers
I: Indicator function
|| llo: no-mrrm of a vector, iee number non-zero elements
|| |12: lz-norm of vector
|| I -norm a vector or matrix, i.e., maximum of absolute values of elements
(O); j-th element of a vector
() : ij-th element of a matrix
Og: Zero vector in Rd
L Identity matrix in Rdxd
(,,F, Probability space
B DISCUSSION ON ASSUMPTION 3 AND PROOF OF THEOREM 1
We introduce some of the assumptions made in related works about sparse linear bandit. We show that these assumptions imply Assumption proving that our assumptions are strictly weaker than others.
Assumption 4 (Anti-concentratioon (Li et al. 2021
itive constant & such that for each & E [K] 1 Chakraborty et al. E { R2a
2023 There exists a pos- I
S Ca}, and > O,
P((xTT,) I hl] I gh. Ca equals d in Li et al. 2021) and is a big enough constant that depends on 5, K, 80, and more in Chakraborty et al. (2023).
Assumption 5 (Sparse eigenvalue of the optimal arm (Li et al. 202T Let T w Ω
A 2 2-
2 4.) be the event that the instantaneous gap is large enough, and E
[r] be the expected Gram matrix of the optimal arm conditioned on the event I. Then, there exists constant Φ1 > O such that
x
v VTE
inf vER" 1lvl sot1
livl2
where C* is big enough constant that depends on & (in Assumption 4. K, and more.
Assumption 6 (Compatibility condition the averaged arm (Oh al. 2021
Ariu et al. 2022
Let Σ E ~x R Σk Xx,,X,T, be the expected Gram matrix of the averaged arm.
Then, there exists constant d2 0 such that 6² (E, So)
d2.
Assumption (Relaxed symmetry (Oh et al.
2021
Ariu et al.
2022 For the context distribution for any X with Px(x) # O.
Px, there exists constant
such that 0
Pr[-x] Pxix)
Assumption 8 (Balanced covariance (Oh et al. such that for any permutation (i1,..., ik) (I.... K). any K (2..... K 1}, and any fixed ( E Rd, it holds that
2021
Ariu et al. 2022)). There exists 0 < Cx < co
Tx_ B]] 3 Cx
[xx,, xi x (x] < x B)]
We show that some of the assumptions imply the following property, which we name the greedy diversity.
Definition 2 (Greedy diversity). For any fixed B E Rd, define the greedy policy with respect to an estimator B as T3 [xx] { = argmax 3T Denote the chosen feature vector with
16

---

Published as a conference paper at ICLR 2025
respect the greedy policy by Xg x The context distribution Dx satisfies the greedy diversity if there exists a conslant @G > 0 such that for any B RRd
o² ( (( [3x3 1, S, 2 og.
Remark 6. Note that Xg. Xx. Under the greedy diversity, Assumption 3 holds with Φ~ @G by plugging in 3 = B². Therefore, the greedy diversity implies the compatibility condition on the optimal arm.
Anti-concentration to ours:
The following lemma shows that anti-concentration implies the greedy diversity, hence it implics Assumption 3 While Li et al. (202T); Chakraborty et al. (2023) use e-net argument to ensure the compatibility condition of the empirical Gram matrix, we follow a slightly different approach to ensure the compatibility condition of the expected Gram matrix. Another point note that Li eet al. 2222 Chakraborty et al. (2023) employ additional assumptions, such as sub-Gaussianity of feature vectors and maximum sparse eigenvalue condition, to upper bound the diagonal elements of the empirical Gram matrix. To make the analysis simpler, we replace the upper bound by 2
Lemma 1. Asssmmption 4 holds with Co 64x K 80 + 1, then the greedy diversity is satisfied
with of 2 1
agK'
Proof of Lemmal 7 We first show that E X3X has a positive minimum sparse eigenvalue, then
use the Transfer principle (Lemma 31) adopted in Li et al. (202T); Chakraborty et al. (2023). Let
E Rdd be vector with l|vil2 = 1 and l|v|lo I Cg. For a fixed value of h 2 0, (xg v)
< h
implies that there exists at least one & E [K] such that (xg v) < h holds. Then, infer that
IP (xg v)² s h)
< P (3k E [K] (x v)2 - h)
K
P (xx v)² < h) EKk,,
where the second inequality is the union bound, and the last inequality from Assumption 4 Then, using that (xx3" vv² Gram matrix.
(x 7) we bound the minimum sparse eigenvalue of the expected
/ P(v' (xxX8) 1) 2 x) dx
E
(xXX3 v]
>
IP (vvT (xax 1) 2 x) dx
/ 22
(1 - {Kx) dx
1
2
Now, we use the Transfer principle. Let E = R. [xxx]]
and Σ EK La. Inequality
2 shows that
for ||vllo < Ca. it holds that
1
v TT
Ev.
2
For any j E [d], we have Σg EE (xx)
$ 2 Then, the conditions of Lemma 31 hold with
2. D = 222 max la, and m = Ca. Suppose E C(Sb). By Lemma
31
we have
D n
1
u I [x
u >
||u|
(3)
2
C5
1
17

---

Published as a conference paper at ICLR 2025
The first term is lower bounded as the following:
1
u
|us. 11
K
2
||us.
ll
2 K50
where the second incquality is the Cauchy-Schwand inequality. The second term is upper bounded as the following:
D | ull
||u|
| 1
(5)
C - 1
64. max 5K30
64
4
KgKsp s0
where the inequality holds by ||ul|| = llus. 11 + ||us; lla x inequalities (3) and (5) together, obtain
||us. 111 when u E C(So). Putting
||u. 11
E X3xx
45
which implies (I [xxx]]] So) 2 aŞK
Sparse eigenvalue to ours
Assumption 5 does not imply the greedy diversity, but still implies the compatibility condition on the optimal arm. As in the previous subsection, replace the upper bound of the diagonal entries of the Gram matrix obtained in Li et al. (022)) with max for simpler analysis.
Lemma 2. Suppose Assumptions
and hold with C 64x2axx EK. Then, Assumption 3
holdds
with d²
Proof of Lemma
Lemma shows that Assumption implies compatibility condition the opti- di
mal arm with o² 45K I
4CK then the proof is complete. Suppose
2 45k
By the margin condition, the probability of the event least P (T) = TP A < 2-.
1 - 2- = 2. Then, we have
Σ Su) = 0² x, [T)
+ {T9) So)
2 0" E x [T)]
Sp)
3 [E
x
[[] (T), So)
1 So)
(6)
2
where the first inequality holds by concavity of the compatibility constant (Lemma 20 and
o² (E (x.x, 1 [[+}] So) 2 0 (Lemma 21 By Assumption 5 for all v E Idd with vvlo <
C*so so +1, holds that
Ejv T (ofIa) V.
By invoking Lemma 31 with & = Ej. (1 7)) Σ = & D = x2 2 obtain
Ia and m = C* + 1, we
D
Vu E CSo). u Ej1 2 2
|n|
C*
Following the proof of Lemma C (So).
[
especially inequalities and 5
we derive that for all
o >
Σ u
us. 11?
|| 11?
sp
4 KgKs0
18

---

Published as a conference paper at ICLR 2025
Since we supposed that
S
we deduce that
3
Sp
U.
12
4
2
3
which proves o² (E), So) 2 2e1 Together with inequality 6). we obtain x² (o),
Relaxed symmetry & Balanced covariance to ours:
The following lemma shows that assumptions from Oh et (021h: Ariu et (2022) imply the greedy diversity, hence they imply Assumption B
Lemma 3. If Assumption 6 8 hold, then the greedy diversity holds with o
2vCx
Proof of Lemma
See Lemma 10 Of et al. 2021 and the paragraph followed by its statement.
C COMPARISONS WITH MULTTIPLE-PARAMIE
SETTING
In this section, we compare the assumptions for the 2020 Wang et al. 2018) with our Assumption 3
setting (Bastani & Bayati
In the by B1. S2. 3x E TRd.. The active sets of the parameters may differ, and they are denoted by St, S2...., SK C [d]. In each round t E [7' single context vector fixed distribution and revealed to the agent, and the mean reward of arm E [K] given by x, B
setting, there are K true parameter vectors, one for each arm, denoted
X' is sampled from
We first note that direct comparisons of the assumptions defined for these two different problem settings are not possible. For instance, there no "feature vector for optimal arm" the multiple- parameter setting start with, as every feature vector is optimal for some Therefore, the algorithms and the assumptions defined for one specific setting must be converted into the other setting; only then would be possible make comparisons.
method that converts a saaammerrrreter bandit instance into a multiple-paranee parameter one was intro- duced by Kim & Paik (2019): Oh et al. (2021): AAii et al. (2022), although it has only been used for experimental comparisons, and theoretical comparisons between the two settings have never been made. We explain the procedure for the conversion for completeness. Suppose has single- parameter bandit instance and an algorithm that operates in the caltipleepprammetee setting, The con- version concatenates K feature vectors of the single parem-prrretter setting.
Xr,K Rdd xx,x)² Rd and provide it the
into Kddddimensional vector, X, (x],1 x,,2 algorithm as the context vector. the true parameter is 3,, then the hidden parameters the arms 1 { = K) for i = 1,2, K. Formally, we introduce conversion that maps a single- parameter bandit instance to multiple- munttple-pprramtter bandit instance.
that the algorithm must learn are B (1 = 1) Ii 2)
Definition 3 (Conversion mapping single-parameter to cultiple-parameter)) Let (3, (xt,I,...,,x.. x) be a single-purameter bandit instance where B E Rdd and Xt,k Bd for [K]. Then, conversion mapping C from single-parameter bandit instance to bandit instance is defined as follows:
C (x4.1,..., xt,K)) = (x)
where
B. (1fi= 13BT
[i=KKBTT R Kd for i [K], x= (x. -.. x,.xx E kd
We will show that under this conversion, the converted assumptions of Bastani & Bayati (2020) and Wang et al.) (2018) are stronger than ours. We first recall the assumptions for the multiple- parameter setting.
19

---

Published as a conference paper at ICLR 2025
Assumption 9 (Arm optimality, Assumptions 3 in Bastani & Bayati 2020)). h, px > O such that P(x E U1) 2 Px. for all i E [K]
There exist constants
where
U. = X x maxx B3 + h).
Assumption 10 (Compatibilityy condition the constrained optimal arm, Assumption 4 in Bastani
Bayati 2020)). ). There exists a constant do > O such that for all E [K], o(E,, 2 Φo. where
Σ; XX X Uz]-
Assumption T0 imposes the compatibility condition on the set features that are optimal for the i-th arm with large gaps. Although the original statements impose the conditions subset of arms Kopt C [K]. following the proof of Proposition in Bastani Bayati (2020) reveals that
Kopt [K] must hold, and replace it with [K] for simpler comparisons. We define another
set for comparison, which constructed the same way as Ug but without the instantaneous gap condition follows:
W = x EXERIXT,, > max x 8,
Clearly, U, C W, Intuitively, Assumption 3 is translated into the converted multiple-parameter instances as imposing the compatibility condition on a principal sub-matrix of the Gram matrix generated by the features in W., which is weaker than Assumption I0 demonstrated in two steps: the compatibility condition is imposed on a sub-matrix corresponding to the i-th arm, and the Gram matrix of interest is generated a larger set. We rigorously demonstrate the relationship between the assumptions under the conversion by the following lemma.
Lemma 4. Suppose that Assumption and 10 hold for multiple sisiipll--paaeetrr bandit instance that converted from single-paraneter instance by conversion mapping C (Definition 3). Then, for those multiple-panne parameter instances, Assumption 3 holds with o² Z Kppdl in the original single- parameter setling.
Proof of Lemma 4 Let (B, {x1, .x.,..., xx]) be fingle-paramete bandit instance and (B, {x1,..... Xx]
(B.....,8 x) be the converted multiple-parameta bandit instance. Note that for fixed E [K] if U,, then x; is the optimal arm the original setting. Let x, Rd be
the optimal feature vector in the single-parameter setting, i.c., X. = argmax;e|k] x, B. Then, we have
E _ =
E x x XE XEW.
K
E|x,x] T
x E Ui}
1=1
pxxxXxx x Ui],
where the first equality holds by the definition of W;, the first inequality is due to that U; C W., and the last inequality holds by Assumption 9 Note that E|xx,, submatrix of E, e Kdx Since Σ, satisfies the compatibility condition with constant on by Assumption 10 the compatibility constant for E x x E U.} must be at least do. Formally,
E U.] is d x d principal
20

---

Published as a conference paper at ICLR 2025
Multiple-paramete bandit instance
Single-parameter bandit instance
C(S)
S
M2
(Mi
M
Figure 3: Illustration of the results of Lemma and Lemma 5 Let C' be a conversion mapping that converts single-parameter bandit instance into a multiple-parametee one by Kd-dimensional context vector construction, MM a set of multiple-paraan parameter instances converted by C satisfying Assumption 9 and TO, M2 of multiple-paramette instances converted by C satisfying Assump- tion 11 and S a set of single-parameter instances satisfying Assumption 3 By the definition C(S) denotes the image of under C which is the set of
instances converted from S by C. Similarly. C 1 (M1) is the inverse image of M, under C. which is the set of single-parameter S, which means that our compatibility condition on the optimal arm (Assumption 3) is weaker than those of [as- tani & Bayati] (2020); Wang et al.] (2018) through the conversion mapping C. On the other hand, Lemma 5 Jensures that Mi C M2.
instances that map to a member of M,. By Lemma we ensure that C- (M1
let dxdd
E x
|x E Ui] and prove the claim by the following argument:
o s 0² Si)
80,3¹ ΣG}
inf (EC(S))((Ka)
1|
s0B¹ Σ&
inf
11 117 BEC(S.) (O0x)) 05==kka
fof Idxd B
inf BEC(S))\ (0a))
||3 l2
( d So).
Therefore, by the concavity of compatibility constants (Lemma 20 we conclude that Assumption holds with de > Kp-øū-
Lemma 4 should be interpreted with particular care. We note that the comparison is possible only between bandit instances that are converted using the conversion mapping C, and Lemma 4 states that for those instances, our assumption (Assumption (3) is weaker than those of Bastani & Bayati 2020): Wang al. (2018) (Assumptions 9 and TOP. However, it does not imply that our analysis holds for any multiple-paramern
instances that satisfy Assumptions | and TO This is trivial given that our algorithm and assumptions are presented only under the parameeer setting and there are multiple-parmmeter parameter bandit instances that satisfy Assumptions 9 and 10 but do not have corre- instances. If the whole algorithu and analysis were to be transferred to sponding parameter setting, we would require multiple-parameter parameter counterpart of Assumption the multiple-parameter
that validates the analysis. We introduce such an assumption and compare it with the assumptions in Bastani & Bayati (2020); [Wang et al. (2018).
Assumption 11 (Compatibility condition for the optimal feature). There exists Pa > 0 such that P(x E W,) 2 p. for all i E [K]. There exists &h > such that for all [K], dEE, St) 2 &..
where Σ/ = Exxx |x W.).
21

---

Published as a conference paper at ICLR 2025
Assumption 11 does not impose the constraints regarding the gap h in Assumptions 9 and 10 and hence it is strictly weaker than those. Formally, we introduce the following lemma. Lemma 5. In the multiple-parameete setting, Assumption and imply Assumption 11
Proof of Lemma 5 Since U, C W for all i E [K], we have that P(x E W;) 2 P(x E U,). Therefore Px(x E U2) 2 p. implies P(xx W:) 2 p.- We also have that E[xx x Wi] =
E[xx] x E U.]. Then, we derive that
E[xx Xx W.
E[xx² x E Wi
E[xx] x U.}
pxxx Ix E Ui}
which implies that (E,) 2 P.
D ADDITIONAL DISCUSSION ON SPARSITY-AWARENESS
In this section, we provide additional discussion the sparsity-awareness of our algorithm in com- parison to -agnostii algorithms (Oh et al. 2021 Ariu et al. 2022).
Although Mo theoretically depends on So. so does not need to be precisely specified (as long as it is within a constant factor of so). For instance, if an upper bound on So smaller than the trivial ambient dimension d exists, this information can be leveraged. Besides, Mo does not solely depend on So but is a tunable parameter that depends on So combined with other problem-dependent factors that are unknown to the algorithm. Tuning parameters that depend on unknown factors applies not only to ours, bul also to almost all Lasso bandit and parametric bandit algorithms - such as parameters that depend on the Gab-Gassiinn parameter of the noise o and the upper bound of the norm of the context vector mmax- We do not need to specify each of those problem parameters separately in practice. Rather, Mo is tuned as a whole. We observe that algorithm not sensitive the choice of Mo in numerical experiments. Figure shows the cumulative regret of PS-WLasso under the setting of Experiment with different values of Mo and shows the robust performances under different values of Mo.
essential to note that
Fixed Sub-optimal Arms, 100, 20,
250
FS-WLazse
FS WLasso MD = 100
FS-WLasso
T
PS-Wlasss MD - 200
FS-WLasse
Cumuistive Regret
150
100
0-
1250
1500
2000
Time
Figure 4: Evaluations of F-WLssoo with various lengths of forced-sampling stage under the setting of Experiment
There is a clear distinction between knowing sparsity and assuming stronger context distributions. Sparsity is about the unknown parameter f not about context distribution. Whether not so known in practice, one still needs to tune hyper-parameters - and even if the algorithm is sparsity-annostic, there are still hyper-parameters to be tuned anyway with other unknown problem- dependent factors such as the uub-Gaussian parameter of the noise. Hence, not knowing sp does not lead to any increased complexity in practice.
22

---

Published as a conference paper at ICLR 2025
On the other hand, stronger context distributions employed in the existing literature (e.g., relaxed symmetry & balanced covariance) are about xz. When context distributions do not satisfy the strong assumptions in previous literature, algorithms recourse for adjustment or guarantees. What is even worse is that such stochastic assumptions on NOT verifiable in practice, particularly in high dimensions. Our work
critically undermine regret performance, with no
the context distributions primarily focuses on alleviating these stochastic assumptions on context, providing the weakest conditions on context distribution known achieve the voga-logaii regret.
Besides, there are other works that still incorporate extra stochastic conditions despite knowing sparsity (Li et al., (02I) or specific optimality criteria for context distributions also under sparsity- awareness (Bastani & Bayati 2020; WWang et al., 2018). Even with awwastt-awwrennsss our work the first Lasso bandit result that achieves the poly-logaritmic regret bound without additional context distributional assumptions after compatibility condition. In this regard, we still provide a new insight that the previous literature did not know.
To conclude this section, we introduce the fundamental challenges of making our algorithms sparsity-agnostic Regret analysis Lasso bandits necessitates satisfying the compatibility con- dition of the empirical Gram matrix constructed from previously selected arms. Ensuring this re- quires (i) an underlying assumption about the compatibility of the expected Gram matrix and (ii) a sufficient number of samples guarantee that the empirical Gram matrix concentrates around the expected Gram matrix. We note that the number of required samples depends on 80 because the matrix concentration inequality
(Lemma 30 depends 8o. Therefore, in most sparse linear bandit algorithms (Kim & Paik 2019 Li et al., [02] Oh et al. (Aruu et al. 2022 Chakraborty) al. 2023), including ours, the maximum regret incurred during the burn-in phase, where the compatibility condition of the empirical Gram matrix is not guaranteed, and the length of the burn-in phase depends on Sy if one would like the tightest bound.
As we demonstrate in Appendix B, the diversity assumptions employed by the previous works (As- sumptions 4 7nd (8) are designed ensure that samples obtained by greedy selections (or even any other policies) automatically explore the feature space, allowing the algorithm to employ a single exploitative policy, regardless of which phase it is in. For example, in Oh et al. (2021), the length of the burn-in phase, denoted by To. clearly depends so as To = O(5)). but their algorithm only makes greedy selection without explicitly specifying To. In contrast, our case (Theorem D we only assume the compatibility condition on the optimal arm. Without the diversity assumptions on the context distribution, a greedy policy or other exploitative policies no longer ensure the compat- ibility condition on the empirical Gram matrix. Therefore, our algorithm runs in two phases: the Forced sampling stage and the Greedy selection stage. At the end of the forced sampling stage, expect the compatibility condition on the empirical Gram matrix to be ensured. As a result, the length of the forced sampling stage depends on sp. We again note that a possible range of so is sufficient set Mo theoretically, instead of its precise value.
E REGRET BOUND OF FS
In this section, we provide proofs for Theorems and S cations of Assumptions and Under Assumption we have reg, = xT,a; - xT,,,"' 3 < ||xt.a; Xt,a, 11 la 2xuaxxh where the Cauchy- Sehhwar inequality and the triangle inequal- ity are used. The fact that the instantaneous regret is at most 2emaxb implies that A. I 2xmaxh, since otherwise P(A. > mxmaxb > 1 b/ A.)a > 0 by Assumption 2 which contradicts
We briefly mention some trivial impli-
A S 2mmaxb.
E. PROPOSITION
I
We introduce a proposition that establishes the core parts of the proofs for Theorem 2 and 3
Proposition 1. Suppose Assumptions constant that satisfies
3
hold. Let 5 (0, 1] and Ti No be given. Let T2 be
7d + 2C, log log
28dC2
2048 max
2 log 8
df + 2 2log
64x² 64 max
27, w² No
72 2 max
Cg log 5
Ti
8
23

---

Published as a conference paper at ICLR 2025
where C2 = max 2, (0000 A.
2
(000 m0 o7
2
Suppose the agent runs Algorithm
with d
as follows:
d 40xmmax
2d (2u log
28 28 (M) Mo)log log
7d(log 2(1 Mo))
6
Define the (weighted) empirical Gram matrix
V Mota
Σm uxta +
Et=Mot1 Xi, the compatibility constant of Motn satisfies
o² (VM 2 max
ma
800x max 80
Mo 64x So log
1
A.
0²
then with probability 1 48,, the estimation error of B, satisfies the following for all 2 Mo 12 12+
200x
2 log log 2(t Mo) + log Td 8
8 -
22
1 Mo
Furthermore, under the same event, the cumulative regret from Mo + + 1 to T with T 2 Mu + T2 is bounded as the following:
T
regt S I7 + IT
Mo
where
5A.
80.r2 ma
-1-1
I
(T2 - -1 + + 4A, log
4
④²
1ta
0
02 80
T (log + log log
a (0,1),
A
[1(1-a)
Ir
1
(log T) (log d + log Ing
a a= 1,
A.
8
1+1
Fmaa 02
(log d + log 4)
a 1.
(a- 1y
A.
Proof of Proposition L arm selections during the first t' greedy selections, starting from t My + Ti + Define the following events
Let (t) = Em 1 fa; # a be the number sub-optimal
Ma
E : max
Σ nh (xi,a)) S TTmax
2M log
jE[d]
Motn
7d (log 2n)²
Eg = w E Ω2 Vn 2 1, max
Σ ni (Xi,a))
$ 2 0mx
/ n 'nlog
jEld
Mo+1
Motn+e Σ
w 220: Ex(T))
min {1,
22x
1133 -
-3--1111) -
+ llog 8
A
ioMo+7++1
Motritt'
02
(T) wEn: 2 T2 - +1,
Σ
Xt, x x
Mottl
The first two events concentration inequalities of the noise, which necessary guarantee the enror bound of the Lasso estimator. The third event is upper boundedness of the number of sub-optimal selections conditioned on the estimation errors, and the event occurs with high
24

---

Published as a conference paper at ICLR 2025
probability by the margin condition. The last event is that the compatibility constant of the empirical Gram matrix of the optimal feature vectors from round t = My + T1 being bounded below, which holds with high probability by concentration inequality of matrices and Assumption El In Appendix E.4.1] we show that each event happens with probability at least - 6. By the union bound, all the events happens with probability at least 1 46, and we assume that these events valid for the rest of the proof.
We first present a lemma that bounds the estimation errors in rounds Mo + 71
Mo 72-
Lemma 6. For each t' -.... TI, the estimation enror of MotTL is bounded as the following:
- -M 11,
A.
a
2xmax
80.
2 max
Define N(t')
E Mo+n +2'
max A.
8* -B--1 1B- [tt') is determined by the errors of the
Mo=Mo
estimators from round Mo + J1 + 1 to round My + T1 + The following lemma shows that small (t')) implies small estimation emror in round Mo + + + when t' 2 72 7 1.
Lemma 7. Suppose t' 72 1 and N(t') S
s0x t. Then, the following holds:
100 - Mo Mo + 20x
log log 2(T) + 12) + log Id
K
7 +
Combining the two lemmas and using mathematical induction leads to the following lemma: Lemma 8. N(O)
t' holds for all 2 O.
80 max
Combining Lemma 7 and Lemma 8 and by setting t MM TI + t', we obtain that for all 12 Mo + T2 + 1, it holds that
-3,1,
200g 200
2 log log 2(t Mo) log Id
8
1- Mo
which proves the first part of the proposition.
To prove the second part of the proposition, define A, as the following:
A
1. Mo +
A,
SUz
max
2 400g
max d2
2 log log 2(1 Hogg 2- Mo
t 2 Mo
T2 +1
Note that by Lemmas 6 and 8 for all t 2 My + TI it holds that 2mmax 1 -3.1 ST. We utilize the following lemma
Lemma 9. Let E No be given. Suppose { is non-increasing sequence of real numbers
that satisfies mmx 3r 3 < A, for all t. 2 Then, under the event E (T), the cumulative bounded as follows:
regret from 7
T
Σ A min ( 1,
A
Σ reg. S 4A, log
4
A.
1=T
By Lemma 1 with
Mo + Ti, we have
T-1
A
Σ
reg, S 4A Mo log
+
Σ
aa
+1
t= Mot
25

---

Published as a conference paper at ICLR 2025
We are left to bound Σt=
T-1
Mo D We separately bound the summation for cases where t Σ
Mo + 72 and t 2 Mo + + 1. For Mo + T1 St Mo + 72, we have
1ia
A ++
1+o
80 max
Mo
t=
1+a
Al+a
(T2 T1
T1 +1.
80 max 80
d
Note that MotT
A.
S A. by Lemma 21
If we set LT2
44, log +
80 9D
GA.
80x
max
-1-
(T2 Ti + 1). then we have
4
47
1
Mo
Al A
4 Mo log
+ 4
S 17
(8)
Mo
For 1 = Mo +T2 + I,...,T 1, we have
He
Σ
A
Alta=
Σ
400crmmax
Ita
2 log log 2(t Mo) + log Id
0²
t
Mo
+1+12+1
11+
1ta
1000xmmaxx max 80
1ta T Mo
log log 2n + log 3d
5
(9)
d²
1= +1
By Lemma 26
we have
- (2 log log 2T + log Id
1-a
a (0, 1)
T- Mo-1
2 log log 2n + log 7d
1+a
(log (2 log log 2T + log 7d)
I-a
Σ
=
n
(2 log log 2n tlog Id
7
n=
1.
(10)
Lemma 26 requires T2 2 8, and it is guaranteed by 72 2048
22 (lo 2 log
64
50
8 X (log log 4), where the first inequality holds by the choice of 2048
T2
T1 +
log $ + log 64x
64mmax and second inequality holds by Lemma
21
We need to
d2
#2
check another property of 72 to simplify the regret when a > 1. Recall that 2 C2 log
Id +
28dC2 where C2 = max 2,
2000 (800 du
2C₂ log log
Then, by Lemma 25 with
3.0!
C C2 and b log 7d 8 it holds that
log log 2n + log
7d 5
400
-2
100m maxx
80
6iN
Vn T2
(11)
n
A.0?
d²
Therefore, for a > 1, it holds that
(2 log log 2Tz + log Id
5
tt1
Id 2 log log 2n + log
2 log log 27z +
7d
g
T2
T2
400 max
10xx2
7d
max
2 log log 272 +
A.
x2
8
(12)
Putting Eq.
9
10
and 12 together, obtain
2
mux
I+x
T (2log log 2T + log 7d 11
a E (0,
T-1
I-a
o²
Σ
A Ita
<
4000x
(log T) (2 log log 27 + log Zd
a=l 1
M=
dada
2
80x
1
2 log log 272 + log Id
a> 1.
(a-1)²
26

---

Published as a conference paper at ICLR 2025
Then, conclude that
5
T-1
A 1+a
Σ
S
IT,
(13)
A
+2
where
0
lta
T== (logd dogd= + log log
22
a (0,1)
0
IT
0
1
0
(log T) (log d + log los
a=1
A.
1+ (log d - log 5))
o²
a>1.
(a-1)2
A.
The proof is complete by combining inequalities
and
13
Mo
+o
T-1
A +o
reg, I Mo+ log
+ 4
5
Σ
Aa
4
Ag
t= Mo
t=
Ma
t=
S T + IT.
E.2 PROOF OF THEOREM 2
Theorem (Formal version of Theorem constant given by
Suppose Assumptions
hold. For ô E (0, 1], let t be
7d C2 log
28dC2
2048x4 max of
d2 log
61n maxe So
T= = max O2
+ 2C's log log
+ 2 log
where C2 max {2,
[0000mmmm A. m²
800
If we set the input parameters of Algorithmm
by
1000 50
2
7d
2048
2d
Mo max
p²
2 2og log 27 + log
max
log
A. 62
2d
7d(log 2(1 MM))²
A Anxmax
Mo log
2
(t Mo) log
6
= VT/Mo.
then with probability least 1 - 56. Algorithm
Jachievss the following total regret,
T
reg, S 2x + I + Ir.
t=l
where
x2 6²
Su
1+!
log + log 1 1))
1-
A
4
0
am may
T
(log d + log log
(0,1).
0x)
Ae
lT
o
1
o 40
(log T)
(log d + log log 8
= 1,
A_
1t!
Ta-
11
A.
o 80
Φ:
(log d + log 4
a
27

---

Published as a conference paper at ICLR 2025
Proof of Theorem 7 We prove Theorem by invoking Proposition I with 71 0 and Observe that satisfies the lower bound condition of 72 in Proposition since T1 = and w² MM =
We must show that the compatibility constant of V Mo - WX; x1,a, satisfies the lower
bound constraint of the proposition. We first show that x² (V Mo) 2
4m (80x A
A.
Let E. - Mo Eemi Xt.a, X(,as" Since Or ~ Unif([A]) for t S Mo. the expected value of E, is
E
Σ
E
[xaxa]
(x De=n~D Dxx [x))
By the definition of p. we have Ø²
E Exx k ~Dx a~Unif(([A]
Xxxxx
8-
By Lemma 22 with probability
Ma x4
at least 1 22d exp
holds that
2048p2
max
Σ
(14)
2p
2048p" mm log 0: V Mo EM4 wxi,o x = Mo Therefore, with probability at least 6, the compatibility
Since Mo
20 0, inequality (14) holds with probability least 8. Note that
constant of VMd is lower bounded as the following:
2²
V
Ma
w
Mo
(15)
2p
By the choice of and w, we obtain upper bound of AM
M max
v 2w 2
log d 2
/
7d /1 log 27 + log
8
7d
log Log 27 + +log 7d
40 max
Mo
2r log
23 2o
2 W
7d
<
Mo
2 22loglog
27 + log
(16)
2
where the first inequality is due to log 2 log log 5 inequality is 4 x (v2 + 2
and w² Mo. and the last
Then, it holds that S
25 2
"00r ! /
max
80 $0 Φ²
50
S0W
7d
Mot
Mo 2log + log
A.
d²
8
(17)
02
< wMo
2p
s 0² (VMo)) Mo
(18)
where the first inequality comes from inequality (6). the second inequality holds by the choice of
Mo 2 0²
3
80. 2
lo log 2T + log Tid), and the last inequality follows by
A. 02
02
inequality (15
28

---

Published as a conference paper at ICLR 2025
On the other hand, by the choice of w 2048p" maa 2 log 5 it holds that
2048 4
2d log 8
and
Mo
2
Mo
2dh
wMo- = To
2048x4 max
S0
2d
2048pp xd
S0
2d
log
max
log
0f
0.
2048pz max
80
2d
log 5
05
Then, have
x² (VM))
Mo
(19)
2p
1024r max
4
60
2d
log
5
2d
64x max Sg log
1
64s max Su log
(20)
8'
where the third inequality holds by Lemma 21 Putting bounds obtain
and 19
20
together, we
2² (v
2 max
4.
80 80
Mo 6
max log
A
Then, the conditions of Proposition are met with Ti and 72 T. Take the union bound over the event that 2 V Mo
d w: holds and the event of Proposition which happen with 2p
2
probability at least 8 and 46 respectively. Then, with probability at least I-56, the cumulative
regret from Mo + to T is bounded by I-2 + IT in Proposition Since know the value of
2+ &
T2
O
8:
xr mux 50
(log d log (og))) 3)
further bound I, as follows:
-1-1
80x² max
Ir = 24.
(T2
1) + log
d2
o²
2
90
1+
log d + log 1 8
The cumulative regret of the first Mo rounds bounded by 2x max which is the maximum regret possible. The proof is complete by renaming Lzz to Lr.
E.3 PROOF OF THEOREM
Theorem (Formal version of Theorem
Suppose Assumptions 73 hold. Further assume that either
Assumption f or Assumptions 6 hold. Let dG > 0 be constant that depends on the employed
assumptions, specifically.
Under Assumption
o5 =
Under Assumptions
2oCx
For 8 (0, 1), let be the least even integer that satisfies
7d
28dC3
4096.44
d²
64 max 80
2 max
C2 log
+ 2C' log log
max
log
+ 2 log
+2
5
5
29

---

Published as a conference paper at ICLR 2025
where C3 = max {2, m
2
80 may 42
If we set the input parameters of Algorithu
A.05
by Mo 0 and 2' m V tlog
Td(log 21)2
then with probability least 1 5ò, Algorithm
achieves the following total regret.
[I+ (T)
TsT+1
reg
[b + I
T>
t=1
where
2048 max $0
( de
max
4log !
Ib 2x maxb
log
2lo
8
+ T T
(log dl + log 2) 40
E (0,1),
A
9G
(TT)
0
2 50 80
(log T")
(log dl log Logg)
a= 1,
A.
9G
2
"max 80
(log d + log 2))
a> a>l,
(a-1) 1y
A.
4
0
ou aun 50
T
(log dl + log log 0
a (0,1),
-
Ir
0
1
mu
t0
(log I')
(log d + log 0
log
a= 1
4.
l+
g²
50
(log d + log
a a>
(a-1
1j3
A.
Proof of Theorem 3 From Lemma 1 and Lemma we know that the greedy diversity, defined in
Definition holds with compatibility constant ΦG. Let To 2048 ob (log + +2log We present lemma about the greedy diversity.
d' G4 80
48
4
2P suppose Algorithm D runs with Mo 0. Define the empirical Gram matrix V, Σt Xi,o, x For d E (0, 1}. let EGD be the event that the compatibility constant of the empirical Gram matrix being lower bounded for big enough t. Specifically,
Lemma 10. Under the greedy diversity (Definition
EGD ( W WER: +1,2 (
(V) 26
Then, have TP (Eap) 2 --
We prove the theorem under the events EGD, &g, En Ex()), and Ed (1r,T). By Lemma and Lemma 13 15 each of the events holds with probability at least 6, and by the union bound, all the events happen with probability at least 1 - 58. Next lemma states regret bound of Algorithm that is independent of Assumption
Lemma 11. Suppose Assumptions 7 2 hold and Dx satisfies the greedy diversity (Definition 2
Suppose Algorithm runs as in Theorem 3 Then, under the events Eco. Eg. and y (To),, the cumulative regret is bounded as the following:
T
Σ
reg, < Is + L(T),
30

---

Published as a conference paper at ICLR 2025
where
2048
4
max $0
d²
m
+ +410g 1
Ib max
log
+ 2 log
6
g
0
axmax 90
- (log d log ()
E (0,1),
(2(
=
o
max 90
(log T) (log d + log log
a=1, 1,
0
a²
0x man oz
) (log d log 1))
a>1.
(a (a-1)=A.
If ow dG. specifically of < 80 then Theorem 3 reduces to Lemma by replacing ø. with dG and adjusting the constant factors appro- priately. Lemma 11 is also sufficrent to prove the theorem when 7 S + 1. We suppose o 2 8 and T > + from now on.
We can assume that o @ by the Remark 6
We must first show that satisfies the lower bound condition of 72 in Proposition 1 Since suppose x > Seg. C3 in the state- Hence, we have т 2 C2 log o +222 log log 8 T trivially satisfies the rest of the lower bound conditions of 72 when
We invoke Proposition with T1 I and T2
ment of Theorem
3 is greater than C₂ in the statement of Proposition |
28dC2
Ti f and Mo = O. Now, we must show that Φ² (V (V+.:So) satisfies the lower bound constraint
4096x max S (log of 5 2og d
64x 64xmax
in Proposition
As we have chosen T to satisfy T 2
+ 2,
we have f
2
2048 on (log d² + 2og
64ar 64
+ 1. Then, under the event EGD,
46
holds. By the choice of and Lemma
25
we have
2 log log 27 + log 7d 5.
108 max 80
2
80 max $0
Then, we have
7d 27)²
X 2 m.x
Flo
2 log log 2r + log 7d
-² T.Tmax T
7
A 2
11 < T'Tmax
1080
2
max 80
80 max 80
A.08T
16 80
80.r max 80
Therefore, it holds that
4r SD
880mmax
d
(21)
A,
0²
S 0
(22)
On the other hand, by 7 2
4096.4 20
(log d²
8
2 log
24 o6
50
have
6g
T
(23)
xr)
4
1024x 4
max
log
d²
2 log
6 maxxx000
50
de
64.²2 max
log
(24)
8'
31

---

Published as a conference paper at ICLR 2025
where the last inequality holds by Lemma 21 we obtain
Putting inequalities 21
22 and 23 24 together,
max Sn
(80
max
Ar. 64r max 50 log
A.
o²
Then, the conditions of Proposition
hold with
_ and T. By the first part of Proposi-
tion 1
obtain
|88 - -8,1,
200 max
2 log log t + Id
for >> On the other hand, by inequality
from the proof of Lemma 11
we obtain
3 3.11
27 max
log log 2t log 7d
for 2 To Define A, as follows:
540m
log log 21+ T3
t 8
A,
4G
400mm aolerarnnsss
2 log log 1
t>т.
02
Then, 2amax 0r - 3,
< A, holds for all & 2 To + and A, is decreasing in since we assumed
that o3 2 8 By Lemma
9 it holds that
T-1 Σ
A
reg.
< log
A.
min
(25)
7=
Following the proof of Proposition
!
especially inequality
13
we obtain that
Σ
A
IT.
A
t=
Following the proof of Lemma
we observe that
reg, + Ta log J + - A
4
reg.
min
1,
A.
t=Yo
< b b To 4104g 4log !) + +2(T+1)
(26)
Combining Eq.
25 and 266. we conclude that
Σ reg, S 20maxb To - 4log !) 12(T 1) + +I.
32

---

Published as a conference paper at ICLR 2025
E.4 PROOF OF TECHNICAL LEMMAS IN APPENDIX E.1
E33
E.4.1 HIGH PROBABILITY EVENTS
We prove that the events assumed in the proof of Proposition I the definitions of the events.
hold with high probability. Recall
Mo
&.
w EΩ
max JE(4]
Σ 1
(Xioa))
S O.mmxx
2Mo log
Motn Σ k= Mo+1
7d (log 2n)
Eg = w E : Vn 2 1, max
Di (Xi,a))
S 2 02 /
Inlog
jeld
8
Mo Motn+t
En(n)
W WED:VE No)
Σ
min
1,
2xmax
113 113" BB-1lla) + 4 log
A.
+o++++
Motr+te' Σ
Oi6'
(T(T) = wen:ww T2 - +
Xt,aj x
X4,0z
2
2
I'm Mo+
Lemma 12. We have P (Ee) 2 1 8
is the o-algebra generated by Fix E [d]. By uub-Gaussianity of R. Since (xr.,); is F--measurable, we get Therefore, (x),)))))))) Mo se- quence of conditionally O'maa Gau--aasiinn random variables. Then, by the nauma-Hoeffdin inequality, we have
Proof of Lemma 12 Recall that Fr
((xTs)rE)) ar (reee frrai hre(e-1))-
Mh, E E
for all 8 E Fi] I (x..a 0302/2
(x0,)) Fj <
ex =
Mo
2 8) Me (2x.aa)) S O. v 2Ma log
P
Σ
56.
Take the union bound over j E [d] and obtain
Mu
2d
P (ES) =
max ]E[d]
ne (xx
JJ / 2M log
8
d
Mp
2d
Σ j=l
IP
nc (x),)))))
S 00mmx /
2MM log
8
x=1
8.
Lemma 13. We have P (EE) >
Proof of Lemma 13 Fix j [d]. Following the same argument in the proof of Lemma 12
{ni(Xt, ), 100
1+ is a sequence of conditionally a "emmx-sub-Gausiiie random variables.
By
Lemma 27 it holds that
Mote' Σ
7(log 2
P
ni(xi,a
2 2 Tax
V fllog
log
S 88.
8
M=
Taking the union bound over j [d] concludes the proof.
Lemma 14. For any n E No. have P (EN (n))
8 8.
33

---

Published as a conference paper at ICLR 2025
Proof of Lemma 14 Let = 1 {aMo+n-i 7 an Define Ft" to be the o-algebra generated by [e]) (ar]re(t), (Tr..- rr((t)) Note that the only difference between J, and Fi is that F is also generated by Ti, Y, F+
Mo+n++ measurable. By Lemma 29 with probability at
least 1 - 6, the following holds for all t' 2
1'
1
Y
E Y
F
Motnti-1] 4 4log 6
(27)
By Lemma 24 Y, 1 happens only when Dd, 2xmax 3- 3r,-1 1l
where t, Mo + +
By Assumption IP Dr, S 2mmax 3 -e,-1 |1, ( S
2itman A.
3
Be,-111) where
use the fact that Bi.-1 2t, measurable and A, is independent of F Then, have
E Y
P = =1
s PP Dr, S 2xmax 3 -B (
max 3 Be. Be-- Bnm-ll))
On the other hand, E [Y; Ftt has trivial upper bound of 1. Therefore, we deduce that
S min (". |
E Y2 4--
- -..-
(28)
Plug in inequality 28 to 27
and we obtain the desired result.
au (log d' 5 + 2og
Gd ),
Lemma 15. Tf
+ + of
then we have P (T,, 2 1-5.
03
Proof of Lemma 15
Let Vi.
Et=Moto Xt,a;
Mo+n
x o²
Note
that E Vi
E Mot
Mo+r+4
E
By Assumption
Su
o By
Lemma
23 with probability at least - 6, 0² Vi,So
Det 2
holds for all
t' >
2048.4
log d 5 + 2 log 64 *0
+ 1. Since 72 2 +
2048m
?
(log L + + 2lg 64m 80
('
+ implies '' (2) 6.
d² 20482tme of (log
J
2 log
64z o²
+ 1. Therefore, we conclude
that
E.4.2 PROOF OF LEMMA 6
Proof Lemma 0 We apply Lemma 19 events & and Eg. holds that for 2 Mo.
using the constraints of x2 (V No) Under the
Ma
wlY (xi,;))
nh (5
je(d
M
Ma
< max w jE(d]
+ max jE(d
m, mxxxiaal (X)
i=1
i= Mo+1
2d
7d(log 2(t - Mo))²
S JTmax
w
2Mo log
28 $ (t Mo) log
8
which implies
Mo wm. (Xi,o))s
X
max 2 [
Σ
nx(xia))8
5
(29)
M=
34

---

Published as a conference paper at ICLR 2025
For t' 2 O, we have x² ( Mo+ +er So) 2 Ø² V Mo+ So 2
(
(
A.
by the condition of Proposition 1 By Lemma 19 holds that
28y 2
Ait 50 A.
80x2 mug 4:
AMo-ra
280
ditma 8q D.
80 80
A.
2xmax
80x2 max 80
where the second inequality holds since D is increasing and t' S 52 T1
E.4.3
PROOF OF LEMMA
Proof of Lemmal
7
Decompose
V +o as follows:
Mott
Votn
Σ
T Xi,oxi.a.
io
Mo+
Mo Mo-
-
Σ
Xi,a; X xx,oz
Σ
Xio;
Mo+
i= -
Mo+n+t'
Mo Mo+N++
-V
Σ
1fa: oi} (xiaxxta
x1,0;
Σ
x
i=
Mo+1++1
+o+1
Mo+r+tt'
Mota+t'
-Mottn
Σ
1fa: dj) X1,
Σ
1 1 + a )1,0, X1,0;
Mo+t++1
Mo+
Motr+t'
Σ
Xi,x
MotTi+l
Note that d² (V Mo So) 2 64x2 6 Sn log J holds by the assumption of Proposition | By Motn
Lemma 21 8² Σ Li=Mo+ lfa; # aj x1,,x,, So) and d²( Mottr 1fa, *
af Xx,a; x 1, So) are lower bounded by and
Nr (t') respectively. Under the event
(2), 8²( Σ Motri+e'
Xi,a; x So) > ø''' holds when l' > 72 By combining the
lower bounds and by concavity of compatibility constant (Lemma 20 we have
d² (VMotnte)
64x 30 log 8
1 16x max No (t))
(30)
Under the event EN (TL), we have N (t') < :N((t') + 4log 8. We supposed that N(t') <
t. Combining these facts, we have N (t') S Glu t' + 4 4log J. Then, together with
S0a mane
Eq. s² (VMott++*) 2 22 holds.
On the other hand, since 1' >
2 n. it holds that L' > ntt'' 2. Then, we obtain the following
lower bound of o² (V :o++
8² V (VMotn+t)
2 2 (v Motn rattl T
(T +t).
As shown in Eq. maxje[d] EN wree (Xi.2)) + Σ Mo 11(xx (Xi,,
under the events En, Eg. it holds that < A 7.
Therefore, by Lemma 19 we
35

---

2 log 2(TI +t') + log 7d 8 Published as a conference paper at ICLR 2025
have that
Mo0 0²
0 -
-M
8 (TI +0
6-
V 2222 log
2d
④ + 28 +2 / (TI + (2g + +0) + log 7d
(Ti +t)
From Mo S T2 S 7I + t' and log 21og 2( + 1 + log
obtain
0 - -Baottitell
2d 2w2 log
8 + 2 V (Ti (1+ log 2(TI + 17) + log
7d
(n +1)
64
(v2+28) V (1 - 12) 2( + +1 + log
7d
( + +.)
8
3max30
log log 2(T) + +1' + log
T1
where the last inequality used the fact 64 x (V2+2) + +2 < 200.
E.4.4 PROOF OF LEMMA
Proof of Lemma g
By Lemma
6 for S St' T2 - 11 + 1, holds that
Mo Mo-r++1'
N(t') <
22mmxx
3 -B,-
33-1
A,
t= Mo +1
Mo +4'
80x² max
Mo T
t'
80.²2 max 80
To prove that the inequality holds for t'
2 T2 - 11 + 1, we use mathematical induction on t'.
Suppose N(L)
80r l' holds for some
T2 T + We must prove that it implies
N(L' 11 S
80a 80 (1' + 1). By Lemma
we have
100 - Mo- M ||,
200
Φ²
Ti +
2 2log log 2n+log 74
A
Note that for n 2 T2.
holds, which shown in
7
a000 muee
8022 mux 30
Eq. Since 71 + 2 r2, we have
1
80x Sraxx 80
0 - 3 M
S
2xmax
22
Therefore, we have
N(I' 1-1)=N(1))
22mmxx
-r- M 3 -BMott+tlll
A
22
2²
2 80
80 80
(t' + 1).
8 muxe 8p
By mathematical induction, N(t')
t' holds for all H'
72 71 1.
36

---

Published as a conference paper at ICLR 2025
E.4.5 PROOF OF LEMMA 9
Proof of Lemma 9 By Lemma the instantaneous regret in round t 2 7 + at most A,-
i.e., reg, S max 3 3 1-1 -, Define (+ = Eieri {a: * af). The cumulative regret from round
1 to T is bounded as the following:
Tegt
A 1l Fai
1=
t=
T
Σ
A (N+(1 -)- - N2 - - 1))
t=1+1
Σ d=1
A (N+(1') N-(1' 1))
(31)
To show that the bound above is increasing in (1)) for l' 2 1, we rewrite Eq.
31 using the
summation by parts technique as follows:
T-r-1
A (N-(1)) - Nr(L - 1)) Σ
A A
Σ
A
Ar
P==1
F=1
t'=0
T-f-1
= NT -T
Σ
(1 N=(!).
==1
(32)
Since A, is non-increasing, we have Ar+e-1 Arth' 2 O. One can observe that the value of
Eq. (32 increases when (t') is replaced by a larger value for t' Under the event Ex
holds that (t' S 1ir+1 min { 1, A )
+ 4log for all t' 2 Replace N+ by } + 4 log& 1 for 2 in Eq. (31) and obtain the desired upper bound.
E min {1,
A A.
A Artt-1 (N=(1) - -N,(())NN,() -N,(1-
< A,
5
min
A,
/ 41og 8)
1)=
+ Σ A
T
5
min {1, (1(AAr)) (A--1) )}
4
A.
4
A.
(=++2
5 T-1
min {1,
/A-11
4A, log
+
Σ
A
8
4 1=
A.
E.4.6
PROOF OF LEMMA 10
by ((x)))rEj))eeja)) {ar freje {rna, }.e))) Then, Xt,a, and B, are F measurable. Under the greedy diversity, we have that for all 2
Proof of Lemma 10
Let
F+
be the o-algebra
generated
δ² E X
[
So) 0² [E [E[x8__) x X | .S))
2 200
By Lemma with probability at least 8, 8² (V,, So)
2
d holds for all
2
4 mase
log & + 2 log
64
64x
+ 1 = + 1.
37

---

2 log log 2t + log 7d 8 Published as a conference paper at ICLR 2025
E.4.7
PROOF OF LEMMA
Proof of Lemma 11 By Lemma
I
under the events &g and EGD. the estimation error of Bg for
t 2 To + 1 bounded as follows:
8
3,
A
2
2 a max
log log + log
&
t
max 80
2 log log 21 + log
(33)
6
Define A as follows:
54 max
A.
Then, max 3 - -,1111 < A, for all / 1 To 1, and A, is decreasing in I. Therefore, can
Lemma 9 with t = To. which gives the following upper bound of cumulative regret:
T-1
{ 1
(1(22)
A
reg, < 4A log
1 min
A.
We first address the case where
I 1. Plugging in the definition of At, We have
Σ
T
reg, <
log
5
T
A
1+a
To
4
A
+1
t=
4
A
log
+
(54mmmax
80
1ta T-1
Σ
2 log log 21 + log 7d
5
(34)
8
4Ag
By Lemma 26 we bound the sum as the following:
2 log log 2t log Td
2
T (2 log log 2T + log Id a E (0,
(35)
(log T) (2 log 2T log 7d
a = 1.
By combining inequalities
34
and
35
we conclude that
reg, 5 4A To log + 12()),
t= +1
where
0
nx? m0
-
(log d + log logg)
a [0, 1),
(1o0Aa
%6
(TT)
(log 7) (log d log logg))
a=1
Now, suppose > 1. We need more sophisticated analysis to bound the regret in this case. Let T6 be a constant that satisfies the following:
2og log 276 + log 8
(540xmax 4.00
Vn T6.
(36)
28dC12
By Lemma 25 it sufficient to take 7 C/ log
2C log log
where C
3
8
5 90 A.
2
max 2,
Now, we bound the cumulative regret as the following:
T
T-
lta
Σ (=1+1
reg, < 4A To log
Σ
A
(37)
4
t=
1=
38

---

Published as a conference paper at ICLR 2025
where the sum == summation and obtain
D treated as when To > T Plug the definition of A, into the first
540 max
80
2 log log 2t log 7
A
7=
1=70
By Lemma 26 with r
2. we have
To
log log 2t + log 5
7d 2 log 27 + log
<//70 To
t
8
2 2og log 27 + log g
V
To
By constraint 36 of Tos we achieve
5
5
540x
2 log log 2T + log 7d 5
A
2T01
4
4
6G
5T
54oo 80
55lx max 50
A. 2.
5
1
/oxmaxo0)
2
log d + log 2)) 1))
= o
(38)
A.
12
For the last summation in inequality
(37
we have
T-1
I+a T-1
2 2log log 21 + log 3
++a
8D
t
1=
1=
max 8p
I+a
4a
(2 log log 2T + log 7d
(a - 1)2
TO
where the equality holds by the definition of A., and the inequality comes from Lemma 26 by constraint (36). we have
Again
log log 27x
7d
5
1-a
7d 2og log 27d log
8
1-1
2.02
TO
Then, we have
5
T
50
[54o=maxx0 )² oy
2 log log 276 + log 7d 8
a
(a
1)2
t=
a.222 max
logg + log 8 1))
0
(39)
(a
1)2A.
Plugging in inequalities of Eq.
38 and Eq. (39 into Eq. (37) yields
1
reg. S 4A log (T),
t +1 1
where
a²
0 2
Sp OG
(log d + log 3 1
I2(T) = 0
(a 1)2A.
39

---

Published as a conference paper at ICLR 2025
in 1. Putting all together, for any a 2 0, we obtain
reg,
I T log + I2(),
(40)
t= +1
where
Ita T:21 (log d + log log T
0
a a [0,1] E
[-
%6
(2(T)=
max
ou
2
(log 7) (log d + log log
a a=l,
&
a²
on (log d + log 2))
aa-1)AA.
96
We bound the cumulative regret of first rounds by 2mmax which is the maximum regret pos- sible. We also bound A S mxrahh, since A. represents the maximum instantaneous regret in round = + 1. Together with Eq. (40), we obtain
reg, S maxb ro (TO 40+44og/ 8) + I2(T).
Σ t=
F FORCED SAMPLING WITH LASSO (FS- (FS-LASSO)
In this section, present FS-Lasso, algorithm that uses that FS-Lasso is capable of bounding the expected regret even when is unknown. The regret bound matches the regret bound of FS-WLasso.
adaptively. We prove
Porced-sampling algorithms in the existing literature (Goldenshluger & Zeevi 2013 Bastani & Bayati 2020) designed for the multiple parameter setting where each arm has its own hidden parameter and one context feature vector is given at each round. Additionally, the compatibility assumptions employed by Bastani Bayati| (2020) (Assumption in (Bastani & Bayati] 2020 volve the compatibility condition of the expected Gram matrix of the optimal context vectors when the gap is large enough (measured by in (Bastani & Bayati] 2020)). This assumption enables more straightforward regret analysis because it implies that a small estimation error is guaranteed if the agent chooses the optimal arm only when it is clearly distinguishable from the others. However, our assumption (Assumption 3) does not imply such a convenient guarantee. Furthermore, Bastani
Bayati (2020) make an additional assumption (Assumption in (Bastani & Bayatil 2020)). stating that subset of arms is always sub-optimal with gap of least h (denoted by Kaub in (Bastani & Bayati 2020)), and the probability observing an optimal context corresponding to the rest of the arms with sub-optimality gap h is lower-hounded by p.-
We consider the single parameter setting where there is one unknown reward parameter vector and multiple feature vectors for each arm given each round. We emphasize that directly translat- ing assumptions or theoretical guarantees across these different settings is either not trivial or not optimal, or usually both. Under Assumptions bound as FS-WLasso without constraining the expected Gram matrix of the optimal arms only to cases where the sub-optimality gap large, or lower bound on the probability of observing such large sub-optimality gap.
we show that FS-Lasso achieves the same regret
F.1 ALGORITHM: PA-LASSO
For non-empty set of index I, let define LI(3) as follows:
Lz(B)
(xTa, G rs,as)
7
40

---

Published as a conference paper at ICLR 2025
Algorithm 2 FS-FLasse (Forced Sampling with Lasso)
1: Input: Forced sampling function No + I22. localization parameter h > 0, regularization
parameters A1 (221)21
2: Initialize: (e(1) (1) = 0. Bo =Bo- =0a
3: for 1,,,.... do
4: Observe { k==]
5: if [T.(1) S (())(())) then
6:
Choose ~ Unif (A) and observe 12,01
7:
Telt + 1) = (t(t) U {t}
8:
B (t-(t)))] argmin 3 (T((+)) + A1
9:
else
10:
0r [r[] (T.00)
11:
if x B TT( > m X B T2(o)) + h then
x,x
12:
Choose a = az
else
14:
Choose = ke(K] x1,, (T,10)
15:
end
if
Observe Tt,a
17:
+g( 1) ())
Update [[T,(++1= argming LT₃((11) 22,1113112
end if
20:
end for
F.2
REGRET BOUND OF FS-LASSO
Theorem 4. Suppose Assumptions hold. If the agent runs Algorithm 2 with the input parameters
as
((n)
512p" max s0 log 2d (n + 1)s
max
4,
4a²
128x2
max
S0
h
A
A
128x2 max $0
h
2 log 4e( (t) + 1)²
A
A2,1
4ax
5p
then, the expected cumulative regret is bounded as follows:
T
E
Σ
regi
S 2axbbb + IT,
1=1
where
x.
Iu
0 (T))
logd
0
2x
1ta
r' (log + log 4/
a (0.1),
(1-a)á
IT <
0
(log T) (log d + log 77)
a= 1,
02
m d2
(logd + log
a> 1.
(o-1)a_
F.3 PROOF OF THEOREM
4
Proof of Theorem We define T to be the set of rounds that take greedy actions, and Te to be the rounds that take random actions. We define nt,(t) TTg [t] be the number of greedy selections up to round f, and (t) = [Te n [t]] to be the number of random selections up to round f. We first bound the estimation error of (3, the estimator obtained by forced-sampled arms.
41

---

Published as a conference paper at ICLR 2025
Lemma
16.
Suppose ((n) and A of Algorithm
satisfy dh
q(n)
p max 6 max 2048 log 2d (n 1)²
5120" h²
log 2d(n 1)3² and A1
Define an
Apæmaa 90
event (t( w sEEs 10 317
-
S 2xmos ).
h
Then, for all E Ty. IP (I)((()))) S
2
(g)0
We further define set (t)
12 (p(+)+1 (t) = { (iE ()g))))))))))))))
+1}.
To (t) the set of
2
rounds that the latter half of the greedy actions are made, rounded up. Note that [T (t) n,(()
We show that the number of sub-optimal arm selections during the latter half of the greedy actions is bounded with high probability.
Lemma 17. Let (1) = EiET, (1) 1 (az & a.j.
(1) is the num-
ber of sub-optimal arm selections during the latter tions.
half the greedy
6²
Let N (1)
WEQ:N N (1) S 64 max
If the in- q(n)
put
parameters of Algorithm
satisfy h
A.
128
5120² p max 22048 log 2d (n + 115
log 2d(n 1)8} } log 2d (n + 1)3 and X1 4ptmmee
9:
h²a
then P (IN- S (1) + exp (-
16384o
Finally, bound the estimation error of / when the majority of the samples are obtained from greedy actions.
Lemma 18. Suppose t E Tg. A2,t
40 Jmmax
2 log (1)2
and ng(() 2 ne((). Define an event
(t)
w E Q
8r -3(T,(0)
11
1280m
log (t), (t)
Then, P (T (T)(t))) I
20
+
(g
exp (-
(1)
2d exp
(-
(in)(()
1638811
110960
2 We observe that there at most n. (T) random log d For all random actions and the first To greedy actions, we bound the incurred regret by 2x 2To. which is the maximum regret possible. Now, bound the regret incurred by the greedy selections from (1) To 1. We decompose the expected instantaneous regret in round as follows:
Now, bound the total regret of Algorithm
actions. We set To max (T)).. 8192.
E I < E [reg,1 (t)(t) [reg, 11 (T,(t)+H] + [reg, 1 freg, O, O,T,(t)Tr,()))
The first two terms are the regret when good events do not hold. We take 2 b the upper bound of the instantancous regret this case, and bound the terms using Lemmas 16 and 18
E [reg,1 (T.(1) [reg, (T,())
< 2 b (TP (P
2
20
+ exp (-
(1)(())
sin,(1)
< b
+ 2d exp
(t)3
ng(t)²
16384.4 50
4096x4
22
g,ng(t)
Φtng(t)
< 2x
(t)2
+ exp
[613884.4 Aaa $
+ 2d
exp
409624 dmax $
42

---

Published as a conference paper at ICLR 2025
The sum of the expected regret when the good events do not hold is bounded the following:
ng (2(2')
E Ireg (To(t)*))+ (reg, 1 (Tg
ny (1)=-T++1
(T(
22 (t)2
n (t)
g.n (t)
2x maxb
+ exp
+ 2d exp
16384x max
4096x max $
ng (+)=
&I 4096x max $D
88 b + 2% maxb
exp
+ 2d exp
dx
16384x4 max $
16384x S
TToo
8192d x max 0
TTo
m8a + maxb
exp
exp
16384r
4096x
22
max
By the fact that To To
8192.
log d, the exponential in the last term is bounded by We obtain the bound of cumulative regret without the good events,
exp
1096
which is a constant independent of T.
(T)
freg, I (Te(t) + E rrgg11 (T I max 491 49152m max bst
of
(1==++++1
Now, are left to bound the cumulative regret when the good events (t), (t) hold. We first show that if the agent chooses a, = ā by the if clause in line 11, since x PIT(, max (T.(0) + h satisfied, then under [e(t), at at holds. Suppose not, then we have xI. An.(e) ,T, Bn.(t) + h. On the other hand, have x -x 3 0. Combining these two inequalities, we obtain
h
Xi,ūBBnll XiazBmal1) +
-x - 3x)
x (Bn.11) - -3 xxa; (8r -3--Bmmn Bmm(t))
g - Bm.ceo)
< 2mmax
where apply the Cauchy-Schwarz inequality for the last inequality. However, under Pe((), Zirmax. which is contradiction since h < h.
holds that 8 18--Bamcc Bm.(t) I h
Therefore, under the event [t)(), + A occurs only when the agent performs a greedy action according to 3 (T,((0) by the else clause in line 13. By Lemma 24 the instantaneous regret is at most
2xmax
3 -
I,
25601 6²
2 log (0)²
Lemma 24 further tells that the regret is
greater than 0 only when A
256mm 2
40
2 log (t)
Therefore, we deduce that
log (t) [reg, 1 reg, O,T,
2560x max 8o
25 max 80
2 log 4dn, (t)
I
A
<
d²
t
25 So
log idn,(tt)
256 max Sp
log 4dn (t)
P
A
<
t
t
256o 50
log (t)
256a 2
max 80
log 4drt, (8)2
min
1,
t
62
t
256o 2 50 0²
log 4 ng(()
25
2 log 4d72 ng (t)
min
1,
A.02
43

---

Published as a conference paper at ICLR 2025
where the third inequality holds by the margin condition, and the last inequality by ny (t))) <t T. We separately deal with the cases a S 1 and a 1. The expected cumulative regret under the good events when a S 1 is bounded as the following:
E reg, (reg, > 0, 0,Te(0),Tg()))
2o(0)=o+11
(T(
2560 max
2 log 4d7
2560 max
2 log 4
min 1,
A.03
mg (t)
na(1)=To-1
(T(T)
25 2 max 80
log 4dT2
1+a
Σ
(t(t)
1
(T
256 max Su 2 log 4
Σ
A
a10==To+1 ng(t)
1+a
25
2
max
2 log 4
Σ
1
Aa
1+0 2
n=1++1
If < 1, we have E -
If 1, then Ex n- S log T. Then, we obtain the desired upper bound of the expected cumulative regret under the good events.
2 T
T-a
(T)
Σ
E [reg, Il {reg, > (,,{(()),,(())}
(ommgn of
- (log d + log T) 1/20
E (0,1)
(1- (1-a)A9
(41)
(log (log + log T))
a=1
6²
Now, we address the case where a 1. Let Ti regret until (t) Ti-
2256m
)²
(2 log 4dT We first sum the
A.
T Σ
E [reg, freg, > (,T,(t),[,(())
ny(0==2+1
2560x x So
log 4dT2 (t(()
2266 Su
2 log 4dT
min 1,
0.02
ny (t)
ny -1
23
256 max S0
2 log 4 ni (t)
(t)=TTT
25 2
max 80
2 log 4d72
1o+ (()())
2560 max
80 / 2 log 4d72
VTi
2
1
256er 80
(2 log 2
24.
44

---

Published as a conference paper at ICLR 2025
Then, bound the sum of regret from (t(() = Ti to
Be (T
E regg, freg, > O,T,((),
+x(0==++1
2560
2 log 4dT2 ng(()
min {1, 1,
2560
2 log 4dT2 ng (t)
Σ
A.
ny(t)=21-1
T
2560 x So
2oo 4dT2
2560 max SD
log 4dT² my (1)
o
(g(1)
A o
ny ny(1)=21-1
25 max
2 log 4d7
Σ
A
mx(1=T++1 (t) 1
The summation upper bounded by
Σ
1a de
-x(0=T++1
ng (t)
Liu
Ti
dx
2
T
1-a
2
256 max /
2 log 4d
a
A A.
Therefore, we obtain that
(T")
2 (a I)A,
256oxx max 80
E jreg 1l (reg, > (t))(()),,
(2 log 4dT
Da (+)=
(42)
Combining inequalities of Eq.
(41 and Eq. 42
we obtain that
E reg, 1 freg, > O,Te(t),r < Ir.
To (t)=TTo++> T
where
?x 50
50
1ta T-200 (log dl + log 14a
a (0.1),
(1-o)a0
IT <
o
(log (log d + log 7))
a a=1,
A.
0
Tx "0 62
(log dl + log T)
a >>1 1.
[n-1)A.
Putting all together, we obtain
49152.r
max bsg + Iy.
reg,
< 4x bTo + 88 +
which is the desired result.
F.4 PROOF OF TECHNICAL LEMMAS
F.4.1 PROOF OF LEMMA T6
Proof of Lemma 16 We use Lemma 19 with w. 17-00]- Define Σ - [..Ce] ΣieT,(0) Xi,a, XT Xi,
The
lemma
requires two events to hold: lower-boundedness of 0² ($/. and
45

---

Published as a conference paper at ICLR 2025
maxje[d] [7 (i m (xx,)))))
>/|
A Since ΣS the empirical Gram matrix of ran-
domly chosen features, its expectation is E
k k= XLAXT Then, by Lemma 22 with
probability at least 1 - 2ddeexp exp
6.1T.101
So) 2 2p" Since {n (x,,ai,)))) FT
2048p 60
sequence of conditionally 03max sub-Gaussian random variables as shown the proof of Lemma 12 we apply the Azuma- Houua-Hoefiding inequality and obtain
A (2)
Σ (E)
mx(x,a)))) )3
2
S 2 exp
[T((t]
4
320 2x
max
Taking the union bound over j E [d] and plugging in the definition of t yields
2 d1 S 2d exp
(T.2
P
max d
[t)
nh (x(,,a)) Σ
exp
512pp022
iET+(1)
max
Lemma 19 guarantees that under the two events, holds that
|10 T s 28
di
h
2x
By taking the union bound over the two events, conclude that
2 Te(1)
(e())
P (( S 2d exp
+ 2d
2048, m
512
Since Ty. we know that [Te(t)
(t)) and (t())
nt(t).
By q(n) 2
512g² p" "in o max 2004 log 2d (n 1)3,
log 2d(n 1)33 we obtain
(t)
(2A71T.(11)
2d exp
2dexp
2048p2ar1 1haxx
512p2 2 Thax
(1g((T,()))
(1,))((TT(())))
2dl exp
2dexxp
2048pp xtaa 80
512p20221 2t
2d exp
log 2nl (1T, + 1)3) + 2d exp log (t)) + 1)3)
1
1
(1T,(1) + 1)3
(IT,(1) + 1)3
which is the desired result.
F.4.2
PROOF OF LEMMA 17
Proof of Lemma
17 By the union bound, we have
(T (t)s) < P (x)(t)s, U Ie(i)
Σ TE
P (TT()))).
LET, (1)
(0)
46

---

Published as a conference paper at ICLR 2025
By Lemma 16
the summation is bounded the following:
Σ
P(T.(1))
Σ
2
(i(1)3
B (0)
TET
2
+
Σ
2 9
(t)
3
+
2
16
(1
dx
(t)3
2
16
3
(t)3
T2 (t)2
19
(1)2
Under the event (i))), A, > 2h implies that for any + 0j it holds that
x Xi (1,0(11
1T.001) > (xT,a;17T.0))
x (T,1I) (xTa; B² -x
+ 2h
x (BiT((0) - -38) + +x,1 (3" - ) +
-2 B|T.C00 - 33 + 2h
Then, the agent chooses a, 0. in round i. Taking the contraposition, it means that a; + o implies A; < 2h under the event [i) Then, we have that
ng(()
TN (1)s,
U [o(1)
SP
Σ
1(A S 2h}
64x² max
NET,
(ET, (4)
(11 1A: S 2/ HiTT, (0)
is a sequence of independent Bernoulli random variables, whose expectation
is at most
2h
by the margin condition and the definition h. Then, by Hoeffding's
A.
1288
max
inequality, have
(t)
P
Σ
1(, < 2h}
64r max 80
NET, (8)
[ty(t)
P
Σ
(1 2h) E 2bh)))
Σ
E (A, 2n
64.2 max 80
2
iET, (4)
iET, (t)
2²
my (t)
SP
Σ
(1 EEI (A. S 2hJ])
128 max 80
VET, (t)
M (t)
exp
-2
2
128
max 90
(gg(1) (1)
< exp
16384.4
Combining all together, we obtain
19
n2 (t)
PT (1)) <
(1)2
exp
1638441 max
47

---

Published as a conference paper at ICLR 2025
F.4.3 PROOF OF LEMMA 18
Proof of Lemma 18 Define the empirical Gram matrix of the latter half of greedy actions as EieT, (1) Xi,a, Define the empirical Gram matrix of optimal features of the latter half of the greedy actions as Σ I7, (4)
Σ
ITe (x)
EieT, (0) X1, X We decompose Σ, as
follows:
Σ,
Σ
Xi,a; X
(Tg(t)
(t)
SET, (0)
1
Σ
Xi,a Xi i,a; +
Σ
(a + ai
(x
X1,a; x
[Tg (t)
TTg (t)
SE,, (0)
(ET, (4)
Σ
1
Σ
1 (a + ag) Xi xTaa
Σ
fai + a;) Xi,a,
iog (1)
(T'(1)
TET, (4)
iETT(() (1)
By Lemma 22 with probability at least 2d exp
1,(022
2² -
So) 2 The
1096 mase
compatibility constant of the second term is lower bounded by 0. the last term is lower bounded by compatibility constant, we have
The compatibility constant of
17, (0) 16x by Lemma 21
(*)
By the concavity of the
62
16x max So (t)
8²
Tg (4)
Under the event I'v- (t), it holds that
16x?
No (8)
d Therefore, we have Ø² Σ So of
IT (4)
deduce that Let E. El= Xi,a;Xi,0 Xi,a Then, since (l( ne(() and TTg (T) [,,(]]
ITg (t) 2 4. Then, it holds that
[t(t)l
0² S0)
Ø²
Σ
1
2
4
16
By the choice of A2,t 4axmaa
loog (0)
and Lemma
19 for TT.
P (133, 1r 2
1280 S0
2 log 4dh, (t)²
62
18, Sb)
2
.' (t) 5
2
ng (t)2
By the union bound, have
0²
(2, , < 0²
(()(()))) IP
(E, Sp) 2
I (1) +
+
2
19
Ggng(1)
(nnn (t)
(1)=
my
(1)=
+ 2d exp
4096xr max 30
+ eex
1638444 90
which completes the proof.
G TECHNICAL LEMMAS FOR APPENDICES E
AND F
In this section, state and prove the lemmas used for the analysis of Appendices E and
48

---

Published as a conference paper at ICLR 2025
G.1 ORACLE INEQUALITY FOR WEIGHTED SQUARED ERROR LASSO ESTIMATOR
We present the oracle inequality for the weighted squared error Lasso estimator. The proof mainly follows the proof of the standard Lasso oracle inequality with the compatibility condition (Bühlmann & Van De Geer 2011). but with adaptive samples and weights. We provide the whole proof for completeness.
Lemma 19. Let 3 E Rd be the true parameter vector and {xx]i=1 be sequence of random vectors in IRd adapted to filtration (Ft)ezo Let va be the noised observation given by x, 8" + Tb where is a real-valued random variable that is Fe41-measurabl w1, w2..... . Wn and Xn, O, define the weighted squared error Lasso estimator by
For non-negative constants
B = argmin An 113111 +
Σ
We (rr - x, 3)²
(43)
BERd
1=1
Let Va Ei= xxxxx and assume x² (V SVn 2 2 > 0.
Then, under the event
ww E 12 maxje(d]
El=1 wop (xi),| S }. B satisfies
||8- - 3//1
20n
Proof of Lemma 19
Define
Xw
(V 1
/u2X22
Wn
E Rdxn Iw (wnim)) E R..
(Vwirz
(n)
E R". and 7w (Vw11)1 can be rewritten as
Vwgrz
The minimization problem
43
argmin An |1311, + ||tw 31
SER
Since 3 achieves the minimum, it holds that
A 11:1 + Fw
S Am + ||r - 1x
(44)
Using that Fw nw
X I 3r, expand the squares as
Irw x 3/3 ||
nw + T -3)
-|n l12 + T x - (3) + T -3)
(45)
By plugging Eq. 45) into Eq. and reordering the terms, we have
x (B - B)
||
< An (113 - -118111) + 2n, x 33)
s An (1131) - 113111) + X 1loo 1135 - -B111
(46)
Note that X Tw is d-dimensional vector whose j-th component is (X nw), = Em=1 (x,(x
Under the event (w e Q maxje[4]
Σn= wim (xx), < 2x) we have IX I 2x Plug
into the Eq. 46 and obtain
[ - San
13113==
An (118)) -113111))))
+
An 1133 111130 2
-311
(47)
On the other hand, by the definition of Sp. we have
||3 11 || ||, | |1 ||| 11. l|
< |1( 33ss, ll ||3 s ||
11( 3) 11(8" -3)s;; |l
(48)
49

---

Published as a conference paper at ICLR 2025
Also, note that
|3" -B 11 = 11(33 3)s, l11 + 11((3' - -3)s ll1
(49)
By plugging Eq.
48 and
Eq. (49)
into Eq. 47 we have
0 <
X (3" - -33
-/² - 2
222 3An
11(3" B)so 1l
An 2/2 11 - -B)
(50)
2
2
Eq. 50 implies (13" - s) 11 S 311 - -0) 112. by which we conclude B 3 C(S)).
Then, have the following result:
1 - 001l2 + An Am 113 = 2 An (ICC* - s,) +1((8* -B)s8 (11s)111)
2
- 2A ((* - 3)soll1
80 Xw (3) 2
- 2hn
$ X (3"
3)
+
2
80
of
where the first inequality comes from Eq. (50). the second incquality holds due to the compatibility
condition of V, = X X w.
and the last inequality is the AM-GM inequality, namely 2 S a+b.
Therefore, we have ||@ B11 2A
G.2 PROPERTIES OF COMPATIBILITY CONSTANTS
For this subsection, we assume that So C [d] a fixed set and denote the compatibility constant of a matrix A as (²( instead of (A(A, So) for simplicity.
Lemma 20 (Coneavity of Compatibility Constant). Let A, E Rdxd be square matrices. Then, (A+ (A) (B).
Proof of Lemma 20
By definition,
$0,3² (A +B)3
(A+
inf (EC(S.)((.a)
Bs l
$0,3 A,3
$u.3 B3
inf (eC(S.)((O.)
|85001
2
| so l1
s0.31
A,3 2
suf3 B, || so ll
inf BeC(S.)
+
inf
|
B'EC(So)
= (A)
Lemma 21. Let x be a d-dimensional random vector and Σ E [xx
[] Rd Assume that
||x|| S Faax almost surely. Then, for any v E C(S)) \ (0a), it holds that
0 0 Sov Σv
< 16x² 16
v l
Consequently, it holds that S <02EE) S 16x max so and (2(-)) -- 1 80-
Proof of Lemma
21 From V (xxT)
v (x v)) 0, it holds that
v T Σv = v E [xx]] 1]
E [v (xx ) v]
> 0,
50

---

Published as a conference paper at ICLR 2025
which proves 0 < sov -
The upper bound is proved follows:
vss
v Σv E v (xx ) v]
E (x v)²
B (#max |1v|l1)
xmax ||vl]
(51)
where the inequality holds by Hölder's inequality and ||x I Tmax Since v C(S)). we have || = ||v + [|v
S 4 [|vvsoll Therefore, we have
80v T Ev
vsslll
V ll
50
166
166lvvool
l|
16 16x 80
where the first inequality comes from inequality 511) and the second inequality holds by livil < [lvs.l11.
Lemma 22. Let {x1]i=ı be sequence of random vectors in Rd adapted to filtration {Fi)Tzo
such that ||xe|loo S Imax holds for all L 2 1. Let Σ, E x,X; and Σ,
+E E [x
[[-i]- If o² (Σr) o for some do > O, then with probability at least 02 (EE)
1 2d exp
aa holds.
2018
Proof of Lemma
22
Let 7t
(xt)i
(xt); E ((x.); (x+), [F-1) for S ú, d. Then, Azuma-Hoeffding Hoeffding inequality,
E E(7 Fr-1]
0 and
h/ //
s 2x max- By the Azuma
(- TE²
(-
P
2eexp
2x4
1=1
By taking the union bound over S i S d. we have
TEa
P P(1S, loo 2 =
< 2d exp
2xd max
Alternatively,
by taking 8
3250
we
obtain
that with probability at least 1
2d exp
TOU 2048ar4 max 7
ІS - Σx 10000 <
3280
Then, by Lemma 30
we conclude that with probability at least 2dd exp
T 20
0 (²(E,)
holds.
Lemma 23. Let {xe) be sequence of random vectors in T&d adapted to filtration (Fi) such that [xxeloo S Fraxx for all t 2 1. Let V. Eim X and V. '' E { [r,1)]
Suppose that there exists constant Φ > such that o (V.) 2 og for all 2 1.
For any E (0, with probability at least 1 8, 0² (v.) 2
dit holds for all 2
2
20 t an (log o + 2 log 64ar
+
51

---

Published as a conference paper at ICLR 2025
Proof of Lemma 23 By Lemma 22 with Σ, 1 VV, and Σ, = = Ø² (tV.)
2
holds with
2
probability at least 1 2d exp
d 2048x max
Let to maa o %
d² (log
+ log
64
max
)
5
%
By taking the union bound over
to + 1, we conclude that
P 3 to +1: 802 (v,
oit
P
% V
2
2
tmto+1
2d exp
2048 max $
t=
6
2d
cxp
dx
2048a max
t0
2d
2048x
4
max
$0
Poto
exp
2048
I 8
where the last inequality holds by to
2048x
6-1r ma (log of + log
26
%6
G.3 GUARANTEES OF GREEDY ACTION SELECTION
Lemma 24. Suppose or = argmax X ....111 is chosen greedily with respect to an estimator 3 in round Then, the instantaneous regret in round t at most 2xmax 3.-1l1 Conse- quently, A. > 22xmxx BB-1ll1: then a₁ a7.
Proof of Lemma 24 Let a; = argmax A X Br. By the choice of a, the following inequality holds:
x 3,_1 xT,0 3--1 0.
(52)
Then, the instantaneous regret is bounded as the following:
x xT B" xT.
reg,
x0,03 - 3) + X 1x xT.
x (3- (3--B,1) -B,_1) + x (3|-1 33)
||xtaa
11oo 3 - -B/-1 ||xt,a
100 10- -
2mm
3
(53)
where the first inequality holds by inequality (52) and the second inequality due to Hölder's inequality. This result proves the first part of the lemma.
Suppose that A, 2mmax || -r Then, the instantaneous regret in round t is either 0 or less than A., which implies that reg, is either 0 or greater than 2zmax | -B,r1l1 By (53) we
have reg,- S 2xmax 1 -l- Therefore, the reg, must be 0, which implies d; = aj.
G.4 BEHAVIOR OF log log n
Let > be constant and define f(x) 2 log log 2x for 2 2. The derivative of f(x) is
f'(x) 2s 2 log log 2n
(x(x) is decreasing in x and f'(2) < 0, therefore f(x) decreasing
for 2 2.
Lemma 25. Suppose C > 2, b 2 1, and 2 Cb + 2C log (2 log 2C + b). Then, f(n) log log 2n++h
c--
52

---

Published as a conference paper at ICLR 2025
Proof of Lemma 25
Let ny Cb + 2C' (2 PC + b). Since no 2 Cb > 2 and f(z) is
decreasing for x 2 following:
2, is sufficient to show that f (no) I c. We rewrite f(no) c as the
1
2 log log 2no + b 1
I (nn)
C
C
2C log log 2no + Cb - ni
Cno
2C log log 2nd
2o' (2 log 2C' + b)
Cno
2 log log 2C (b 2 log (2 log 2C + b)) - log 2C 2C + b))
7g
Now, sufficient to prove log 2C + 2 log (2 2C + b)) < 2log 2C + b. We prove it by applying log I for all > 0 multiple times.
log 2C (b + log (2 log 2C + b)) = log 2C + log (b + 2 log 2og2C'
2C + 6))
b+ 2 (2 log 20 + b)
< log + log
= =log 2C + +log
log 2C +
log
1 b
4
1 b
log 20
log 20
22
2 log 20 +b.
Lemma 26. Let f() 21og log 20+log for a constant b 2 1 and 2. Suppose S A B are integers and r 2 0 is a nonnegative real number. Then,
1 B (2 log 2B + b)"
r EE [0,1) r=1 1
--r
B Σ J(n)'
(log B) (2log log 2B + b)
(2 log log 24+ - log log 2A+02
r E (1,2)
n=A+1
17
holds.
Proof of Lemma 26 Since f(x) is decreasing for > 2, we have
B
f(n) S / f(x) da.
B
Σ
R=A+1
We bound S& 22log log 1 ) du for each case of r.
x
Case 1: r E 10,
log log 2x + +D) dr < 1"
log log 2B + I
dx
///
p
log log 2B + b)²
- dx
= log log 2B + b)"
(B'---A--)
T-r
< B1-r (2 log log 2B + +b)
53

---

Published as a conference paper at ICLR 2025
Case 2: r 1
B 2 log log 2r +
B 2log log 2B
b
dr
dx
x
B 1
(2 log log 2B + b)
dx
A 2
(2 log log 2B + b) (log B log A)
I (log B) (2 log log 2B + b)
Case 3: r [1
First, apply Jensen's inequality x" with p = 2 log log 2A
obtain
2 2oo log 2A+5
2 log log 2x
log log 2x + 6)"
p
(1 - p)
1 1-3 p
2 log log 2x
b
p
+11 - p)
P
1- p
(2 log 2x) )
+ (1 - p) 1"b""
Then, the integral can be split into
B
2 log log 2x + D) dr S p 1-r
B
2 log log 2x
B
dx + (1 p)
1-r
dr
x
x
11
12
Ip is bounded by
B b
1
1
(1
p)-
dx (1 p)= 1-
r-1
Ar-1
Br-1
(1 p) 2-
(r 1)Ar-I
(1 p)
b
1-p
11)
p) (2g log 2. + b)"
(r 1)Ar-1
where the last equality holds by the definition of p. To bound I, use integration by parts with u = log log 2x)
and v = zf and get
2 log log y dr
(2 log log 2x)
B
(2 log 2x)
2
2x
dx
r-1
1
x--1
r r-1
r
(2log log 2.A)
2r
B
log log 2x)
dx
(r 1)Ar-1
r
x² log 2x
Is
For <rS S 2, holds that (2 log log 2x)
< 2 2og log 2r S log 2r. Then,
13 <
da
A
x¹¹
1
1
-- 1
Ar-1
Br-1
(r-
54

---

Published as a conference paper at ICLR 2025
We have
2 log log 2x
1 p²
dx
(2log log 2A)
2r
S p
+
(r 1)A
(r 1)2
p 2 2og 2A
12- -2r
(r 1)Ar-1
(r (r-1) 1)2
p (2 log 2A + 6)"
2rp
2lo log 2A+b
2 log 24
(r 1)A-11
(r
A)2
(2 log 2A + b)"
(2 log 2. + b)" (r- 1)2
1)-1-
where the last inequality holds since s 1 and 2log 2og2A4 2A 2 whenever A 2 8. Finally, we obtain
13
2 log log 2x + +b) r dx 11 +
p (2 log log 2A + bb
2r (2log log 2A + 6)" (r - ---
(1- p) (2 log log 2A b)" (r 1)A
(r
1)Ar-1
(2 log 2A b)"
r
A--1
1
(2log log 2A +D*
(r 1)²
Ar-1
Case 4: r Use integration by parts with (2 log log 2x + b)" and v' = 1
and get
2 log log 2x + b)
log log 2x b)
B
2r (2 log log 2x + b)= r-
dr
dx
x
xx log 2x
14
(2log log 2A + by
2r
B
(2 log log 2x + b)" xx log 2x.
dx
r
A--1
r-
(2 log 2A + 6)
(2 log log 2x + 6)
+ 4
dx
Ar-1
x" log 2x
For x 2 A 2 8, holds that (2 log log 2r + (log 2xr 2 (2log log 16 + 1)(log 16) 2 8. Then,
B
(2 log log 2r (log 2x)
(2 log log 2x b)"
Is
xx log 2r dx
8
1
log log 2x + b)"
dr
8
A
x¹¹
Therefore we have 14 S
log log 24+
Lo which implies 14 S F--
(2 log log 24+6)" -
G.5 TIME-UNIFORM CONCENTRATION INEQUALITIES
The following lemma a special case of Theorem from Garivier 2013). For completeness, we provide the proof adapted this lemma.
55

---

Published as a conference paper at ICLR 2025
Lemma 27 (Time- Unifo- Azuma inequality). Let (Xt]t=) be real- martingale difference sequence adapted to a filtration (Ft) Assume that {Xt)e=1 is conditionally o-sub-Gaussion
Le., E [eaxe Fr-1]] S _ for all IR. Then, it holds that
223
7(log 2n)² n nlog
P En :
N:
Σ X
280
S 88.
6
Proof of Lemma 27 By the union bound, it is sufficient to prove one side of the inequality, namely,
En ENN : Σ X₂ 2 220 2 log 3.5(log 2n)
S 8.
5
Let 1j = 2 for j 2 0. Partition the set of natural numbers into lo, I,,..,, where 1; ftz,tz +.....,,tye t,41 13. For a fixed positive real number sy. whose values we assign later, define
De = exp (, -300² Then, by uub-Gaussianity of Xx, we have E [D, Fi-1] S 1. Define
Mn = D2D2... Dn = exp 83 E Xx 2302n
where Mo = 1. Then, E [Mr, Fx-11] = E [M,-1Dp, Dr Fn-1l= S Mn-1, therefore (Mn) n is a super-martingale. By Ville's maximal in- equality, we get
PP
En I Mn 2
56.
8
Note that Mn 2 obtain
1 is equivalent to Σ 8
X₂ 2
8,02n 2
+
1
log 1
Take 8j = -/2
log and
8;
V2
lj
1
P 3 e 1 Σ X
+
log
88.
2
tj
8
For E Ij. <t S n holds, therefore
V2
1
<
2v2
n V2
2 Vn. Furthermore,
2
V2
replace with #G+1y to obtain
P
12 3n E
Σ x, 2 2222 log
T2 1)
65
68
22 + 1)2
From
73+11 6
(log, 26,)²
ü 2)z (log 21,)2 12 S 3 (log 2n) )2, we get
x²
n log 7(log 2n)²
68
P
3n I Σ X, 2 28 v
28
π T2 + 1)2
Take the union bound over j 2 0, and by the fact ===
1
n²
we get the desired result.
(1+1)2
3.5 2n)2
En EENN N: Σ X₂ 2 2 0 nlo
S
8
Next lemma is a time-uniform version of Theorem in Beygelzimer et al. (2011). We combine the proof the theorem and a standard super- aaprr-martingal analysis to obtain a time-uniform inequality. Lemma 28 (Time-uniform Freedman's inequality). Let {X be a real-valued martingale dif- ference sequence adapted to a filtration (Fi) Suppose there exists constant R 0 such that for all i 2 Xx) & R holds almost surely. For any constant (0, #] and 8 E (0, 1), it holds that
P 3n E:N: Σ x12
E Xx
Fc + log 3
58.
56

---

Published as a conference paper at ICLR 2025
Proof of Lemma 28
We have 1nX,| Σ almost surely for all 2 1. Since + +xsc e" for all R
and e" $ <1+2+0
for all x E [-1, 1], holds that
E [ Fi-1] S E
[1 n x² Fi-1]
+ B [X Fi-1]
(54)
Define Dj == exp (nx; - B X2 F Fi-1) Eq.
54
implies E E|D F:-1] < 1. Define
Mn = D, ... Dn = exp
|- X, 1/² Σ
E { Fe-1)), 1]), where Mo = 1. Then,
[M,, Fn-1]] B 1 Dn Fn-1] I Mn-1. therefore (MrJn=o is super-martingale. By
Ville's maximal inequality, we obtain
S M, 2 1
B[Ma]] 6.
1
8
1/5
The proof is complete by noting that M, exp (1) m
Xx 17 E
[ Fi-I))
g is
equivalent Σ Xx 2 n E E X2 Fi-1] + log
Next lemma is a widely known application of Lemma 28
Lemma 29. Let {Yr) be sequence of real-valued random variables adapted to filtration (Fi) Suppose 0 Y, S 1 holds almost surely for all 2 1. For any d E (0, 1]. it holds that
n
I E::: En Σ IP
Fi-1) 4log
56.
(55)
Proof of Lemma
29
Let X, Y, E | Then, {x,)== is a martingale difference se- F, 100 with |X,| S almost surely. Apply Lemma 28 with vj = 1 and obtain
quence adapted
[Fe
1 [
PP
J N
Σ
X
E [x?
Fo-i] + 4 log
56.
(56)
t=1
1=1
We have
E
X
F Fi
= E [(Y - E [Yr] 1)) Fr-1]
$ E [Y? Fi-1]
< E [Y, [[-1],
where the last inequality holds by 0 S Y, < 1. Then, Eq.
56 implies
1) Σ E E Fe-1) 4 8) <o.
TP E Σv. P Σ E Y. Fi-1
which is equivalent the desired result of Eq. 55
H AUXILIARY LEMMAS
Lemma 30 (Corollary 6.8 in (Bühlmann & Van De Geer 2011 Let Eo, Ei E RRdxd, Suppose that the compatibility constant of En over the index set with cardinality = |S| is positive, i.e.,
(2 > O. If EE -E I &² (Enn.) then 6² (E, 2 <2 /2.
32sp
Lemma 31 (Transfer principle, Lemma 5.1 in Oliveeraa 2016).. Suppose E and E are d matrices with non-negative diagonal entries. Assume (0, 1) and m E [d] are such that
VV E Re lv S v Êv (1 (1-1)1 n)v Ev.
Assume D is a diagonal matrix whose elements are non-negative and satisfies Dj₃ Egj (1 7)) Ejj. Then,
Dv 2
Vv E Rd Ivll m,, v T 2 (1-n)v Σv
v
m1 1
57

---

Published as a conference paper at ICLR 2025
1 NUMERICAL EXPERIMENT DETAILS
Our numerical experiment in Section measures the performance of various sparse linear bandit algorithms under two different distributions of context feature vectors. For both experiments, set d = 100, T = 2000, and 7/: ~ (O, 0.25). For given s0, we sample So uniformly from all subsets of [d] with size su, then sample ss uniformly from sy-dimensional unit sphere. We tune the hyper-paramenn parameters of each algorithm to achieve their best performance.
Following the experiments Kim & Paik (2019); Oh al. (2021) Chakraborty et al. (2023). for each i E [d], the i-th components of the K feature vectors are sampled
Experiment 1. (Figure Za
from (0,, V). where V, = for S I K and V 0.7 for I i.j s K with * j. this
way, the arms have high correlation across each other. Note that assumptions of Oh et al. (2021); Ariu et al. (2022); Li et al. (2021); Chakraborty et al. (2023) hold this setting. By Theorem 3 FS WLasso may take Mo 0. To distinguish our algorithm from SA Lasso BANDIT, we set My = 10 and w 1.
Experiment 2. (Figure 2b We evaluate algorithms for context distribution that does not satisfy the strong assumptions employed in the previous Lasso bandit literature (Oh et al.] [021] Ariu al. 2022 Li et al. 2021 Chakraborty et al. 2023). We sample K vectors for sub- optimal arms from (02, La) and fix them for all rounds. For each t E [T], we sample the feature for the optimal arm from (O,,,, Ia). Then, appropriately assign the expected rewards of the features by adjusting their ,3 -components. Specifically, for a sampled vector x and a desired value
8" 3 that have x' 3 c. We set the fixed sub-optimal arms to c, we set x' x 1 113
have expected rewards of O.2........ Unif(0.9, 1). To prevent the theoretical Gram matrix from becoming positive-definite or having positive sparse eigenvalue, we sample five indices from S8 in advance and fix their values at 5 for all arms and rounds.
and sample the expected reward of the optimal arm from
All experiments were held in a computing cluster with twenty Intel(R) Xeon(R) Silver 4210R CPUs and 187 GB of RAM.
58


Reviews:
[{"review_id": "JkOZS66UQ1", "reviewer": "Reviewer_Ltvm", "summary": "The paper contributes to the high-dimensional bandits literature by relaxing the compatibility conditions required for analysis. Specifically, it reduces the need for compatibility conditions on all arms to only the optimal arm, thereby enhancing the generality of the results.", "questions": "See weakenesses.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "By weakening the compatibility condition from all arms to only the optimal arm and relaxing all other diversification requirement in other high-dimensional bandits papers, this paper makes a solid contribution that broadens the applicability of high-dimensional bandit algorithms. Figure 1 and Table 1 clearly sketched the comparison against existing literature.", "weaknesses": "- While the paper criticizes other studies for unverifiable conditions, it does not clearly explain how the compatibility condition on the optimal arm (Assumption 3) is more verifiable in practice. This lack of clarity weakens the argument against existing methods. \n\n- The suggestion to treat the forced sampling iteration number  $M_0$  as a tuning parameter could also be applied to other methods where assumptions are stronger and cannot be easily verified as well. This weakens the significance of the advantage in assuming compatibility for only the optimal arm and does not effectively address the issue of unverifiable assumptions.\n\n- The proof sketch in Section 3.3 lacks sufficient emphasis on the techniques used to overcome the challenges posed by the weakened compatibility assumption. Without a clear explanation of how the standard compatibility condition is avoided, readers may find it difficult to understand the paper’s methodological contributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "FXZwK50oKV", "reviewer": "Reviewer_WnKD", "summary": "The author devised an algorithm called FS-WLasso, which is based on a greedy algorithm with the addition of forced exploration. According to the authors, this algorithm demonstrates polylogarithmic regret even under the weakest assumptions in the context of sparse linear bandits in a stochastic environment. They also demonstrated the algorithm’s practical effectiveness through simulations.", "questions": "- Why the exploration in Algorithm 1, line 5 should be a uniform one? I think the most intuitive exploration to guarantee the minimum eigenvalue is $a = argmax_{x\\in x_t} \\|\\|x\\|\\|_{V_t^{-1}}$. \n\n- I don't understand why the fact that $M_0$ depends on multiple variables implies that it is a tunable parameter. Isn't it a worse situation, that a core parameter depends on multiple parameters (even $\\Delta_*$ and $\\phi_*$)? To compare it with Oh et al., 2021, it feels like 'an algorithm which is easy to run but should satisfy some strong assumptions on the environment' vs 'an algorithm which works on a weaker assumption but requires more information about the environment'. Some readers might think of this as an incremental improvement.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Soundness: In theoretical research, relaxing assumptions is undoubtedly meaningful. This work is particularly valuable in the sense that the authors united all various assumptions in sparse contextual linear bandits, and allows researchers to focus on a single general condition.\n\n- Clarity: The authors clearly illustrated the relationship between their results and previous work using diagrams, and, through an extensive literature review, they included comparisons in multi-parameter setups to highlight the versatility of their setting (Remark 1). Additionally, their meticulous preparation is evident in the various remarks and supplementary materials to address anticipated questions (even the fixed arm set case) and to emphasize their significance/novelty.\n\n- They also introduced a novel proof technique using induction - like a domino, they've constructed an interesting proof scheme to maintain their compatibility condition.", "weaknesses": "- Their algorithm works on a more general 'environment', but to guarantee their performance the learning agent requires additional knowledge, such as the sparsity level $s_0$ or the gap $\\Delta_0$. As they have mentioned, their result is not sparsity-agnostic. Even though they've mentioned in Appendix D, it is still true that they rely on the sparsity parameter $s_0$ and many other parameters, and I personally think this parameter is somewhat less general info than the noise level $\\sigma$ or the norm bound of the context vector $x_{max}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "E1nNgZlCHE", "reviewer": "Reviewer_ynf4", "summary": "This paper proposes a weaker sufficient condition for high dimensional bandit algorithm. Under such weaker condition, the paper also proves regret bounds for bandit algorithms.", "questions": "N/A", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "1. The authors provide a lot of intuitions for the algorithm design.\n2. I think in general the weaker condition, and the algorithm induced, would be a good addition to the literature.", "weaknesses": "1. The paper needs to be restructured. If the key idea of this paper is the weaker condition proposed, then the main section and main results should be about this condition. Therefore, Appendix B should be the main part of the paper instead of just in the appendix. \nBesides, the novelty claimed, such as the cyclic induction (Lemma 6?), should be moved to the main text as well. It's hard to read and understand the novelty for the current version.\n2. Assumption 3 is claimed to be \"strictly weaker\" than the existing conditions. Then, some counterexamples should be provided to show that Assumption 3 holds but not any of the existing conditions. \n\nI'd be willing to update my rating if the paper can be structured and easy to understand.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)