Sparsity-Agnostic Linear Bandits with Adaptive Adversaries
Authors: Tianyuan Jin
Kyoungseok Jang
Nicolò Cesa-Bianchi
Venue: NeurIPS 2024 poster (2024)
Keywords: Regret bounds
online learning
sparse linear regression
model selection
Primary area: bandits
TL;DR: We prove the first sparsity-agnostic regret bounds for stochastic linear bandits without assumptions on the action set or on the sparsity structure.

Abstract: We study stochastic linear bandits where, in each round, the learner receives a set of actions (i.e., feature vectors), from which it chooses an element and obtains a stochastic reward. The expected reward is a fixed but unknown linear function of the chosen action. We study \emph{sparse} regret bounds, that depend on the number $S$ of non-zero coefficients in the linear reward function. Previous works focused on the case where $S$ is known, or the action sets satisfy additional assumptions. In this work, we obtain the first sparse regret bounds that hold when $S$ is unknown and the action sets are adversarially generated. Our techniques combine online to confidence set conversions with a novel randomized model selection approach over a hierarchy of nested confidence sets. When $S$ is known, our analysis recovers state-of-the-art bounds for adversarial action sets. We also show that a variant of our approach, using Exp3 to dynamically select the confidence sets, can be used to improve the empirical performance of stochastic linear bandits while enjoying a regret bound with optimal dependence on the time horizon.

Sparsity-Agnostic Linear Bandits with Adaptive Adversaries
Tianyuan Jin
Kyoungseok Jang
Department of Electrical and Computer Engineering National University of Singapore Singapore tianyuanEnus .du..g
Dipartimento di Informatica Università degli Studi di Milano
Milano, Italy ksajjks@gmill.cm
Nicolò Cesa-Bianchi
Università degli Studi di Milano Politecnico di Milano Milano, Italy
nicolo. wacolo.ceeaabiii...............e Ceeennchh@iiiiin bomimii.......mmm.mmm.mm..mmmmmm it
Abstract
We study stochastic linear bandits where, in each round, the learner receives set of actions (i.e., feature vectors), from which it chooses an element and obtains a stochastic reward. The expected reward is a fixed but unknown linear function the chosen action. We study sparse regret bounds, that depend on the number S of non-zero coefficients in the linear reward function. Previous works focused on the case where is known, or the action sets satisfy additional assumptions. In this work, we obtain the first sparse regret bounds that hold when S is unknown and the action sets are adversarially generated. Our techniques combine online confidence set conversions with novel randomized model selection approach over a hierarchy of nested confidence sets. When S is known, our analysis recovers state-of-the-a -rr bounds for adversarial action sets. We also show that a variant of our approach, using Exp3 to dynamically select the confidence sets, can be used to improve the empirical performance stochastic linear bandits while enjoying a regret bound with optimal dependence on the time horizon.
Introduction
K-armed bandits are basic model of sequential decision-making in which a learner sequentially chooses which arm pull in set of K arms, After each pull, the learner only observes the reward returned by the chosen arm. After I' pulls, the learner must obtain a total reward as close as possible the reward obtained by always pulling the overall best arm. Linear bandits extend K-armed bandits to a setting in which arms belong to a d-dimensional feature space. In each round & of a linear bandit problem, the learner receives an action set At Rd from the environment, chooses an arm A, E A, based on the past observations, and then receives a reward X,. In this work, we consider the stochastic setting in which rewards are defined by X, = (0.. A,) + Et. where 0, Rd is fixed latent parameter and is zero-mean independent noise. In linear bandits, the learner's goal is to minimize the difference between the total reward obtained by pulling in each round the arm a E A, maximizing (0., a) and the total reward obtained by the learner.
In stochastic linear bandits, the regret after T rounds is known to be of order d''T up to logarithmic factors. The linear dependence on the number d of features implies that the learner is better off by ignoring features corresponding to negligible components of the latent target vector 6,. Hence,
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

one would like to design algorithmss that depend on the number S < d of relevant features without requiring any preliminary knowledge on 0.. This is captured by the setting of sparse linear bandits, where 0. is assumed to have only 0 < S I d nonzero components.
In the sparse setting, Lattimore and Szepesvári [17 Section 24.3] show that a regret of ( SdT) is unavoidable for any algorithm, even with knowledge of S. When S is known, this lower bound is matched (up to log factors) by an algorithm of Abbasi-Yadkori et al. (2] who, under the same assumptions and for the same algorithm, also prove an sestance-deendde Here Á is the minimum gap, over all T rounds, between the expected reward of the optimal arm and that of any suboptimal arm. In this work we focus on the sparsity-agnose unknown. Fewer results are known for this case, and all of them rely on additional assumptions on the action set, or assumptions on the sparsity structure. For example, if the action set is stochastically generated, Oh al.
regret bound of Ö 8d) &)
setting, i.e., when S is
22 prove (SVT) sparsity-agnostic regret bound. More recently, Dai et al. 9 showed a sparsity-agnostic bound Ö(S²VT+ + SvaT) when the action set is fixed and equal to the unit sphere. In a model selection setting, Cutkosky al. [8] prove ((52TT) pparsit--agnoste regret bound for adversarial action sets, but under an additional nestedness assumption: (0.): * 0 for
i = .,.... S. Surprisingly, no bounds improving on the (dvTT) regret of the OFUL algorithm [1 in the sparsity- case are known that avoid additional assumptions on the sparsity structure or on the action set generation.
Main contributions. Here is the summary of our main contributions. All the proofs of our results can be found in the appendix.
We introduce a randomized sparsity-agnosti linear bandit algorithm, SparseLinUCB, achieving regret (dV) with no assumptions on the sparsity structure (e.g., nestedness) or on the action set (which may be controlled by an adaptive adversary). When S = of (())), our bound strictly better than the OFUL bound (dv/)).
Our analysis of SparseLinUCB simultaneously guarantees an lestace-deepeddes regret bound
Ö( max{dd, ( where A is the smallest suboptimality gap over the T rounds.
If the sparsity level is known, our algorithm recovers the optimal bound D(VSdT'.
We also introduce AdaLinUCB, variant of SparseLinUCB that uses Exp3 learn the probability distribution over a hierarchy of confidence sets in stochastic linear bandits. Unlike previous works,
which only showed a Ö (T2/33 regret bound for similar approaches, AdaLinUCB has ((VT) regret bound. In experiments on synthetic data, AdaLinUCB performs better than OFUL.
Technical challenges. Recall that the arm chosen in each round by DFUL is
A argmax (a, θz) + Vrilaallzz aEA.
(1.1)
where 02 is the regularized least-squares estimate of 0., V = I+ E.cr AsA, is the regularized covariance matrix of past actions, and / is the radius of the confidence set
{o {ØER": : 10 o. 12 5m)
(1.2)
The squared radius 7/- Od t) is such that 0. belongs to 1.2) with high probability simultancously for all f 2 1. Our approach, instead, builds on the online to confidence set conversion technique of Yadkoii et al. (2], where they show how to design a different confidence set for 0. based on the predictions of an arbitrary algorithm for online linear regression, such that the squared radius of the confidence set is roughly equal to the regret bound of the algorithm. Using the algorithm SeqSEW for sparse online linear regression [13], whose regret bound is O log T),, they obtain the optimal regret (dT) for sparse linear bandits. Unfortunately. this result requires knowing S to properly set the radius of the confidence set. Our strategy SparseLinUCB (Algorithm [ bypasses this problem by running the online to confidence set conversion technique over a hierarchy of nested confidence sets with radii a, = 2' log T for = 1, ....., n = O(lg d). The framework of Yadkori et al. (2) guarantees that, for any sparsity value S E [d]. there is critical radius a O(S log 7') such that, with high probability, 0_ lies in the set with radius o; for 2 o. SparseLinUCB randomizes the choice of the index i of the confidence radius a;, used for selecting the action at time t. If
2

---

Table I: Comparison with other sparse linear bandit works. S E [d] is the sparsity level and A is the suboptimality gap (3.3). The nested assumption refers to (f.); 7 0 for = = ...... S. The minimum signal and the compatibility condition refer to assumptions on the smallest value of the non-zero elements in 0.. Smoothed adversary refers to adversarially
the distribution of the action set and
selected action sets with added Gaussian noise. The regret bounds listed in 1 23 g 25 18 g
high-probability bounds: with high probability, the regret is of the same order as the bound in the table.
Sparsity Adaptive Agnostic Adversary
Reference
Expected Regret
Assumptions
Abbasi- Yadkki- et al. 0
Ó {dvT, d//A))
Abhasi-Yadkori et al.
x
0 ((min( (SSTT, d8/A))
Pacchiano et
23
V(SVTT)
Nested, i.id, actions
Cutkosky et al.
8
/
O(S'VT)
Nested
Pacchiano et al.
0(S+T))
Nested
/
O(S*d/A)
Nested, i..d. actions
Action set is hypercube
Lattimore al.
Ö(SVT)
E [-1,1]
Sivakumar et al. 26
X
0(8VT)
Smoothed adversary
Actions set spans Rd
Hao et al.
x
x
Ö(VST)
Minimum signal
Oh al. 22
/
Ö(SVT)
Compatibility
Dai et al.
/
x
Ö(s SVOT)
Action set is unit sphere
Lower bound
x
((VSdT)
0( min {Sv /Vd maxfdd ssd
This paper
This paper
Ö(VSOT)
bound the regret incurred at step using standard techniques [ 2]. By choosing P(I, = i) proportional to 2-1, we make sure that larger confidence sets (delivering suboptimal regret bounds) chosen with exponentiall) small probability. If 4 < o, then 9, is not guaranteed to in the confidence set of radius at, with high probability. Our main technical contribution is show that the regret summed by Ö( SdT//). where Q P(4 Z o). The proof of this bound requires showing that the regret in bad round (when
the random index 4, is such that 4, then
these bad rounds bounded
o) can be bounded by vol. | A Proving that ||Af shrinks fast enough uses the fact that det V grows fast enough due to the exploration in the good rounds t (when 2 o). This is done by carefully designed peeling technique that partitions [2'] in blocks based on the value of det V,
To extend our analysis of SparseLinUGn and obtain instance- dependend regret bound, we apply the techniques of Abbasi- Yadkori et al. [ to show that the regret over the good rounds is bounded by Abbasi-Yadkori
Ō(f/A) The regret over bad round is controlled by (a./ A|l and-using techniques similar to the imstance-independeer analysis bound the regret summed over all bad rounds with Ö(S))(QA)).
Given that SparseLinUCH uses fixed probability of order 2 to choose its confidence radius ag tempting to explore adaptive probability assignments, that increase the probability of confidence set proportionally to the rewards obtained by the actions that were selected based on that set. Algorithm AdaLinUCB (see Algorithm (2) is variant of SparseLinUCB using Exp3 4 assign probabilities to confidence sets. The analysis of AdaLinUCB combines in non-trivial way the analysis of Exp3 (including forced exploration term q) with that SparseLin Although resulting regret bound does not improve on OFUL, our algorithm provides a new principled solution to the problem of tuning the radius in I.T). Experiments show that SparseLinUCB can perform better than DFUL.

---

1.1 Additional related work
regret bounds, different types of assumptions on the action set have been considered in the past. Starting from the ((SVT) regret upper bound of [18), where the action set is assumed fixed and equal to the hypercube, some works considered stochastic action sets and proved regret bounds depending on spectral parameters of the action distribution, such the minimum eigenvalue of the covariance matrix 19 20]. Others assumed a stochastic action set with strong properties, such as compatibility conditions or margin As far as we know, there has been no research adaptive adversarial
Sparse linear bandits. With the goal of obtaining
conditions B
6 7 19 22
action sets after 2
Model selection. Sparse linear bandits can be naturally viewed as bandit model selection problem. For example, Ghosh et al. [44 establish regret bound of Ö + of /f/a/t/ttt (.5) for fixed action set, where a is the minimum absolute value of the nonzero components of 8.. Quite a bit of work has been devoted to sparse regret bounds in the nested setting. With i.id. and fixed-size actions sets, Foster al. [12] achieve a regret bound of order Ö (S$1/37//3 />²²) in the nested setting, where y is the smallest eigenvalue of the covariance matrix of A₁. Under the same assumption on the action set, obtain regret bound of (SSVV)) For adversarial action sets, Cutkosky al. [8] obtain DSS'VT the nested setting. When actions are sampled i.i.d., Cutkosky et al. [8] and Pacchiano al. 25 obtain regret bound of VT) for nested settings. They also obtain
Pacchiano et al. [24 23
simultancous instance-dependent bounds, in particular, Pacchiano et al. [25] achieve Ö ((Sd)² /A). Compared the instance-dependent regret bound, our results are more general, as we allow the action set to be adaptively chosen by an adversary and do not require the nested assumption.
Parameter tuning. Although the theoretical anlysis of OFUL only holds for y O(d log t). smaller choices of the radius in (I.2) are known to perform better in practice. Our design of SparseLinUCB and AdaLinUCB borrows ideas from the parameter tuning setting, which is typically addressed using a set of base algorithms and a randomized master algorithm that adaptively changes the probability of selecting each base algorithm [2 23 24 In particular, AdaLinUCB builds on [1]. where they show that running Exp3 as the master algorithm over instances of OFUL with different radii has better empirical performance than Thompson Sampling and UCB. Yet, they only show a regret bound of Ö(T2/3) when the action set drawn i.i.d. in each round (they also prove bound of order vT, but only under additional assumptions on the best model). This is consistent with the results of Pacchiano et al. 224] who also obtained regret of the same order using Exp3 as master algorithm.
2 Problem definition
In linear bandits, a learner and an adversary interact over T rounds. In each round ( t= 1,...," T:
1. The adversary chooses an arm set Ar C Rd;
2. The learner choose an arm A, E A,;
3. The learner obtains reward X,-
We assume the adversary is adaptive, i.c., A, can depend in an arbitrary way on the (possibly randomized) past choices of the learner. The reward in each round i satisfies
X, = (Ar. 0-) E
(2.1)
Here 6, Rd is fixed and unknown target vector and (Ee)retTy are independent conditionally 1 1-subgaussian random variables. We also assume ||@-||a < 1 and [|a]|a for all A, and all t E [r] The regret of a strategy over T rounds is defined as the difference between the reward obtained by the optimal policy, always choosing the best arm in A,, and the reward obtained by the strategy choosing arm A, E A, for t E [T).
T RT
T max 0.) - (Ar, 0.).
Σ
aeA:
'The choice of the constant is arbitrary. Choosing different constants would scale our bounds similarly to the scaling of the bounds in (2]

---

In the sparse setting, we would like to devise strategies whose regret depends on
S = 110 1lo = Σ 1(0 + 0}
corresponding to the number of nonzero components of 0..
2.1 Online to confidence set conversions
Establishing confidence set including the target vector with high probability the core of linear bandit algorithms, and our approach for designing sparsity-agnosse algorithm is based on result by Abbasi- Yadkori al. [2]. They show how to construct confidence for OFUL [ based on the predictions of generic algorithm for online linear regression, a sequential decision-making setting defined as follows. For l, 1,...,,?. T:
1. The adversary privately chooses input A, Rd and outcome X, E IR;
2. The learner observes A, and chooses prediction X, E RR;
3. The adversary reveals X, and the learner suffers loss (Xe X,)
The learner's goal in online linear regression is to minimize the following notion of regret against any comparator Rd
(r) E(x. 2,)² Σ(x, (A,,
t=1
The confidence set proposed by Abbasi-Yadkonk et al. [2] is established by the following result.
Lemma 2.1 (Abbasi- Yadkori et al. (2 Corollary 2)). Let E (0, 1/4] and [|0,112 S 1. Assume a
sequence { (A,, Xt))tery, where Xt satisfies 22I) for all E [T]. fed to an online linear regression
algorithu B generating predictions (Xeheem Then P(3t [T] 0g C.) S 8. where
C (BER" 10112
Σ (A,, (,,
(2.2)
V8++ + /1 (r.)
766, 0.) = 2B. 32
5
and (T(,,) is an upper bound on the regret pr (0.) of B. When understood from the context, we will abuse the notation and denote the best radius in hindsight by (()) == 7(6, (.) and the regret bound by BT.
Gerchinovitz 13 designed an algorithm, SeqSEW, for sparse linear regression that bounds (r( in terms of [[ollo simultaneously for all comparators Rd Below here, we state his bound in the formulation of Lattimore and Szepesvári [17].
Lemma 2.2 (Lattimore and Szepesvári 17
Theorem 23.6)). Assume max |All2 S and
max [X|] < 1. There exists universal constant such that algorithm SeqSEW achieves, for any
0 E Rd
(T( S (0) = ell01lo log(le + T2/2) + Cr log
1011 |00]]
)
1+
where Cr + log, log(e + 1112).
Using the confidence set with B SeqSEW, Abbasi- Yadaori [2 achieved the minimax optimal regret bound of ((VSdT) However, to construct C., the learner must know 7(),, which depends on the unknown sparsity level S ||0~|lo through Br.

---

Algorithm SparseLinUCB
1: Input: T N, IN and q A, (l.............................. 9n) E [0,1]" E 9:
2: Initialization: Let Vi
8u = (O....,0)
3: for t = 2, ..... T do
4: Receive action set A, and draw I, from distribution q
5: Choose action A, = argmax (a. 01) ||al| 2 log aeAA.
6: Receive reward X
7: V = V + A,A!
8: Feed (A,, Xx) to SeqSEW and obtain prediction X,
[1013 Σ (X, (0. (0)))))))))))
9: Compute regularized least squares estimate 0, argmin
BER
8=1
end for
3 A multi-level sparse linear bandit algorithm
In this section, we introduce our main algorithm. SparseLinUCB, whose pseudo-code is shown in Algorithm [ The algorithm, which runs SeqSEW base algorithm B, uses hierarchy of confidence sets of increasing radius. each round = 1..... T, after receiving the action set A, the algorithm draws the index of the confidence set for time by sampling from the distribution E A, = (Q),.... (a) E [0. 1|" Σ 4 = 1}. Then the algorithm plays the action A, using the confidence set C. {0 Rd ||0 0 s 2 log T) (where larger implies larger radius, and thus more exploration). Following the online to confidence approach, upon receiving the reward X₁, the algorithm feeds the pair (A,, X2) to SeqSEW and uses the prediction X, to update the regularized least squares estimate 0..
Let a; = 2' log T for all i E IN and set N as
max 0ER 0|
(1/T,, 0)
71
log2
log T
(3.1)
where (66, is defined in Lemma 2.1 for B SeqSEW.
One can check that n (log d) (when ||0||o d), which gives an O(dlog T). Our bounds depend on the following quantity, which defines the index of the smallest "safe" confidence set (i.c., the smallest [n] such that 0, Cj for all [T))
= argmin (1/T) S 0s
(3.2)
EE|n]
The choice of our confidence set (Line in Algorithm 1 is justified by the following result, which
implies that o is safe. Lemma 3.1. For C, defined
2.2
have that C, Cę for all t [T].
As we use SeqSEW as base algorithm B, a, = O(S log T). Our main result is an upper bound on the regret of SparseLinUCB.
Theorem 3.2. The expected regret of SparssLLiUCB run with the number of models in 3. and distribution q {gx) bejn) satisfies
E[ = ((lgT) Σ
d2 (log T) STa/Q
820
where Q Eszo 4s-
the sparsity level S is indeed known, then in 3.2 can be computed and we get the following bound, which is tight up to log factors [17].

---

Corollary 3.3. Assume that the sparsity level S is known and choose the mumber of models > and the distribution {9s) with 9, where is set as (3.) Then, the expected regret of SparseLinUCB is E[Rr] = (VS log T).
An instance-deeendent bound. SparseLinUCB also enjoys an instance-dependent regret bound comparable to that of OFUL. Let A be the minimum gap between the optimal arm and any suboptimal arms over all rounds,
A min min (A) a, 0.); rE[T] eEAr))
(3.3)
where A = maX.E., (a, 0.) is the optimal arm for round t.
Theorem 3.4. The expected regret of SparseLinUCB run with the number of models in 3.1 distribution q = [[e)) and using SeqSEw as base algorithm satisfies
E = (ds/Q) d2
(log (logT)?
where Q 2=E200
Sparsity-agnostic tuning randomization. Next, we look at a specific choice of q. Fix C 2 and let
4x = f22= C22
C
(3.4)
otherwise,
where K. >> 0 is chosen so to normalize the probabilities. It is easy to verify that for any C 2 1,
Σ E < <19.51
xE(n]
implying that x can chosen in [0. 1]. Combining Theorem 3.2 and 3.4 we obtain the following corollary providing hybrid distribution-fiee and distribution-dependeer bound.
Corollary 3.5. Pick any > 1. Let the number models n as in (3.1 and q {1+ (ga)a be chosen as in 3.4 Then the expected regret of SparseLinUCB is
E E = Ö min max (C,S/C)aT, max ( (dL,SddCC _.s.s///4]] 1)
A
For C the above bound is Ö(SVdT), which is tight up the factor VS due the lower bound of (dT) [17). However, mentioned in Lattimore and Szepesvári [17] Section 23.5], no algorithm can enjoy the regret of DVVSdT) simultaneously for all possible sparsity levels While our worst-case regret bound improves with smaller S. the problem-dependent regret bound scales at least as (d. ) log T, which is independent of S. This raises an interesting question: could the problem- deelededd bound also benefit from sparsity? Even with very small probability p of choosing radius an, the expected number of steps using an would be pT. The results in 2 demonstrate that running the OFUL algorithm with over pf steps results in regret of ((f One simple way is decrease the frequency of selecting radius an, However, selecting an less than d times may prevent the algorithm from obtaining a good enough estimate of 0, in certain settings.
Remark 3.6. At first glance, it may seem straightforward to select C' in Corollary 3.5 as setting C= dd yields a regret of (d² /A) without apparent trade-offs. However, the trade-off lies in balancing the mestance-dependent and worst-case regret bounds. Opting for C = d indeed yields an instance-den deeendeet bound of Ó A). However, this comes at the expense of the worst-case bound, which remains (dvTT), negating any advantages derived from the sparsity assumption &<< d.
If the sparsity level S is indeed known, then o in 3.2 can be computed and we get the following bound.
Corollary 3.7. Assume that the sparsity level S is known and choose {qs ]ee[n) with go where
is set as in 3.2 Then, the expected regret of SparseLinUCB is E[RT] 0 (Sdd)
We note that by setting go = 1 in Theorem 3.4 the regret bound becomes ( ((d²/A). detailed in Theorem 3.4 arises from the parameter (n. O. However, in this case, gn = 0, which allows us achieve more favorable regret bound.
AA). This result, as
7

---

Algorithm 2 AdaLinUCB
1: Input: T E N7 > 0. [0.1]
2: Initialization: Let $1,0 = 0 for all i [n]. Vo I, 0 (0.....00)
3: for t t= 1,2,.... ....,.... I do
4: Receive action set Ar and draw a Bernoulli random variable Ze with P(Zx 1) - q
5: if Ze = then
(la (a,00-1) ||ally, 2 log
6: Choose optimistic action A, argmax nE.A,
7: Receive reward X;;
8: else
exp (1)) for i E [m]:
9:
Draw 4, from the distribution Pt. Σラ=1 exp (1)x-111)
Choose action A, argmax
(a. 0._ + ||a|| /21 log log
acAc
Receive reward Xx;
114= = j](2 -x)/44 for j E [n]:
12:
Compute St,j = 1t
Pts
end if
14:
V V,-1 + A,A,;
15: Feed (A,, Xt) SeqSEW and obtain prediction X;;
(1013 Σ (X. (0, A.))
16:
Compute regularized least squares estimate 0, argmin
DERd
17:
end for
4 Adaptive model selection for stochastic linear bandits
SparseLinUCB is also designed to handle adaptive adversarial action sets. A crucial parameter of SparseLinUCB { (eessjn) the distribution from which the radius of the confidence set is drawn. is a natural question whether there exists an algorithm that adaptively updates this distribution based on the observed rewards. In this section we introduce AdaLinUCB (Algorithm) 2}. which runs Exp3 to dynamically adjust the distribution used by SparseLinUCB.
AdaLinUCB takes as input forced exploration term q and the learning rate v) for Exp3. Similarly SparseLinUCB, AdaLinUCB designs confidence sets of various radii, but its selection method differs in two aspects. First, with probability q. the algorithm performs exploration based the confidence set with the largest radius. With probability 1 - the algorithm instead draws the action based on Exp3. The distribution P. used by Exp3 at round is based on exponential weights applied the total estimated loss, denoted by S. (for technical reasons, we translate losses into rewards). The algorithm then draws I, from P. and selects the action A, based on the confidence set with radius 2 log T. Finally, reward X, observed and the pair (A,, X.) is fed to SeqSEW. The prediction X, returned by SeqSEW is used to update the regularized least squares estimate O,.
The following theorem states the theoretical regret upper bound of AdaLinUCB. Theorem 4.1. If the random independent noise &, in (2.1) satisfies 6G E [-1, for all t E [T), then the regret of AdaLinUCB run with / /loog n)/ (Tn) for in 3.1 and q E (0, 1] satisfies
TL2 -+dd 1+
E(RT] < (V8ang + 4v (200)//)
d' dT (1+
+1 +1+00 O log
= =ō max (Vog,
V 5/g VIT
Although AdaLinUCE dynamically adjusts the distribution used by SparseLinUCB and may achieve better empirical performance, its regret bound no better than that of SparseLinUCB, The issue that the action chosen by AdaLinUCB in Line T0 does not ensure enough exploration to control the regret. Consequently, the algorithm needs to choose the optimistic action in Line 6ine/with with constant probability q. SparseLinUCB has similar parameter, Q, that bounds from the above the probability

---

of choosing the optimistic action. The key difference is that Q can be optimized for an unknown S by carefully selecting the distribution q = (2. whereas the parameter q does not provide a similar flexibility.
5 Model selection experiments
In this section we describe some experiments we performed on synthetic data to verify whether AdaLinUCB could outperform OPUL in model selection task. We also test. the empirical performance of SparseLinUCB on the same data (additional details on all the algorithms and the experimental setting are in Appendix [E. The data for model selection experiments 0, with different sparsity levels, as we know that sparsity affects the radius of the optimal confidence set. On the other hand, since no efficient implementation of SeqSEW is known [77 Section 23.5], we cannot implement the online to confidence set approach as described in 2 to capture sparsity.
generated using targets
Instead, we run SparseLinUCB and AdaLinUCB with X, = X, for all E [7]. which- to the form of our confidence amsonts running the algorithms over multiple instances of OFUL with different choices of radius a; for E [n].
We run SparseLinUCB and AdaLinUCB with a, di,t 2 logt (a mildly time-dependent choice) for = 0,1, log, d. We also include og = corresponding to the greedy strategy A, argmax (a, 11)) The suffix _nif indicates {e>)e([n) set to " 11). The suffix Theory indicates 4- 0 for s O...., n prescribed by (3.4). Finally, we included SparseLinUCB. Known using qi = 1i = of to test the performance when the optimal index o (for the given S) is known in advance (see Corollary 3.3). We run our experiments with a fixed set of random actions, A = A for all E [T). where - 30 and A is a set of vectors drawn i.i.d. from the unit sphere in IR The target vector 02 is S-sparse (S 1, 4, 8, 16) vector whose non-zero coordinates are drawn from the unit sphere in RS. The noise E, is drawn i.idd from the uniform distribution over [-1, 1]. Each curve is an average over 20 repetitions with T 10 where, in cach repetition, we draw fresh instances of A and 0..
As our implementations are not sparsity- awarre we cannot expect the regret to strongly depend on the sparsity level. Indeed, only the regret of SparseLinUCB Known (which is tuned to the sparsity S) significantly affected by sparsity. The theory-driven choice of {4x (e() (SparseLinUCB Thhorry performs better than the uniform assignment (SparseLinUCB fnif,, and is in the same ballpark as OFUL. On the other hand, AdaLinUCB LunuBBnniifffa Unif and AdaLinUCB Theory outperform all the competitors, including OFUL. This provides evidence that using Exp3 for adaptive model selection may significantly boost the empirical performance of stochastic linear bandits.
6 Limitations and open problems
Unlike previous works, we prove poursity-agnosee regret bounds with no assumptions on the action sets or on 0. (other than boundedness of ||0.|| and ||a|| for a A,, which are rather standard assumptions). For AdaLinUCB, however, we do require boundedness of the noise E, (instead of just subgaussianity). We conjecture this requirement could be dropped at the expense of further log T factor in the regret. Finally, for efficiency reasons our implementations are not designed to capture sparsity. Hence experiments limited testing the impact of model selection.
Our work leaves some open problems:
1. Proving lower bound on the regret of sparse linear bandits when the sparsity level is unknown to the learner would be important. Citing again [17] Section 23.5], no algorithm can enjoy regret OdVS simultancously for all sparsity levels However, we do not know whether the known lower bound 22( (VVSdT)) can be strengthened to ((VVTT) in the agnostic case.
2. Our restance-dependess regret bound is of order Ö max ,d] 2) It would be interesting to prove an upper bound that improves on the factor d? /A, or lower bound showing that d² d2/4 cannot be improved on.
3. Our bound on the regret of AdaLinUCB looks pessimistic due to the presence of the constant exploration probability q. would interesting to prove a bound that more closely reflects the good empirical performance of this algorithm.

---

S-2
1400
A Theory
1490
AL Theary
340
Thery
OFUL
OPUL
ORUL
9. Unit
9_unff
Uni
Known
1080
Khown
899
SL Theory
9L Thee'y
SL Theory
000
60
S=116
3400
AL Theory
1400
A. Theory
OFUL
OFUL
Unif
130
Known
Known
SL_ Theory
839
SL_ Theaty
230
Figure 1: Experimental results with different sparsity levels S (1, 16]. In each plot, the X-axis are time steps in [1, 10*] and the Yaxii is cumulative regret. AL stands for AdaLinUCB and SL stands for SparseLinUCB.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their helpful comments. This research is supported by the MUR PRIN grant 2022EKNE5K (Learning Markets and Society), the FAIR (Future Artificial Intelligence Research) project, funded by the NextGenerationEUU program within the PNRR-PE scheme, the EU Horizon 101120237, project ELIAS (European Lighthouse of AI for Sustainability), Singapore Ministry of Education AcRF Tier grant -4-0000423000-00, and the National Research Foundation, Singapore under its Al Singapore Program (AISG Award No: 0BGG-PPD/2021-01-00447777
research, innovation action under grant agreement
In particular, NCB and KJ acknowledge the financial support from the MUR PRIN grant, the FAIR project, and the ELIAS project. TJ is funded by Singapore Ministry of Education AcRF Tier grant (A-8000423-00-00) and the National Research Foundation, Singapore under its AI Singapore Program (AISG Award No: (IG--PDD/202101-00447)).
References
[1] Yasin Sabasi-Yadkori Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[2] Yasin Abbasi-Yadkori David Pal, and Csaba Szepesvari. Online-fo-comfidencc-se conversions and application sparse stochastic bandits. In Artificial Intelligence and Statistics, pages 1-9, PMLR, 2012.
[3] Kaito Ariu, Kenshi Abe, and Alexandre Proutière. Thresholded lasso bandit. In International Conference Machine Learning, pages 878-928, PMLR, 2022.
[4] Peter Auer, Nicolo -iaachi, Yoav Freund, and Robert E Schapire The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48 77, 2002.
[5] Séhastien Bubeck, Nicolo Cesa-Bianchi, al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends@ in Machine Learning, 511) 2012.
[6] Sunrit Chakraborty, Saptarshi Roy, and Ambuj Tewari. Thompson sampling for high- dimensional sparse linear contextual bandits. In International Conference on Machine Learning, pages 3979-4008. PMLR, 2023.
10

---

[7] Yi Chen, Yining Wang, Ethan X Fang, Zhaoran Wang, and Runze Li. Nearly dimension- independent sparse linear bandit over small action spaces via best subset selection. Journal of the American Statistical Association, 1196545):24-2555 2024.
[8] Ashok Cutkosky, Christoph Dann, Abhimanyu Das, Claudio Gentile, Aldo Pacchiano, and Manish Purohit. Dynamic balancing for model selection in bandits and rl. In International Conference Muchine Learning, pages 2276-2283 PMLR, 2021.
[9] Yan Dai, Ruosong Wang, and Simon Shaolei Du Variance-aware sparse linear bandits. In The Eleventh International Conference on Learning Representations, 2023.
[10] Varsha Dani, Thomas P Hayes, and Sham Kakade. Stochastic linear optimization under bandit feedback. 2008
[11] Qin Ding, Yue Kang, Yi- Wii Liu, Thomas Chun Man Lee, Cho-Jui Hsieh, and James Sharp- nack. Syndicated bandits: A framework for auto tuning hyper-parameters in contextual bandit algorithms. Advances in Neural Information Processing Systems, 35: 11:1170-1180 1801, 2022.
[12] Dylan J Foster, Akshay Krishnamurthy, and Haipeng Luo. Model selection for contextual bandits. Advances in Neural Information Processing Systems, 32, 2019.
[13] Sébastien Gerchinovitz. Sparsity regret bounds for individual sequences in online linear regression. In Proceedings of the 24th Annual Conference on Learning Theory, pages 377-396.
JMLR Workshop and Conference Proceedings, 2011.
[14) Avishek Ghosh, Abishek Sankararaman, and Ramchandran Kannan. Proplem-complexity adaptive model selection for stochastic linear bandits. In International Conference on Artificial Intelligence and Statistics, pages 1396-1404. PMIR, 2021.
[15] Botao Hao, Tor Lattimore, and Mengdi Wang. High-dimensional sparse linear bandits. Advances in Neural Information Processing Systems, 11110753-1766,, 2020.
[16] Kyoungseok Jang, Chicheng Zhang, and Kwang-Sune Jun. Popart: Efficient sparse regression and experimental design for optimal sparse linear bandits. Advances Neural Information Processing Systems, 35:2102-2114, 2022.
[17] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[18] Tor Lattimore, Koby Crammer, and Csaba Szepesvári. Linear multi-resource allocation with semi-bandit feedback. Advances Neural Information Processing Systems, 28, 2015.
[19] Ke Li, Yun Yang, and Naveen N Narisetty. Regret lower bound and optimal algorithm for high-dimensional contextual linear bandit. Electronic Journal of Statistics, 150))5652256955 2021.
[20] Wenjie Li, Adarsh Barik, and Jean Honorio. A simple unified framework for high dimensional bandit problems. In International Conference on Machine Learning, pages 12619-12655. PMLR, 2022.
[21] Teodor Vanislavov Marinov and Julian Zimmert. The pareto frontier of model selection for general contextual bandits. Advances in Neural Information Processing Systems, 34:17956- 17967, 2021.
[22] Min-Hwan Oh, Garud Iyengar, and Assaf Zeevi. Sparsity-agnostic lasso bandit. In International Conference Machine Learning, pages 8271-8280. PMLR, 2021.
[23] Aldo Pacchiano, Christoph Dann, Claudio Gentile, and Peter Bartlett. Regret bound balancing and elimination for model selection bandits and RL. arXiv preprint 1=XXi:20022.30455 2020.
[24] Aldo Pacchiano, My Phan, Yasin Abbasi Yadkori, Anup Rao, Julian Zimmert, Tor Lattimore, and Csaba Szepesvari. Model selection in contextual stochastic bandit problems. Advances in Neural Information Processing Systems, 1111012881033, 2020.
[25] Aldo Pacchiano, Christoph Dann, and Claudio Gentile. Best of both worlds model selection. Advances in Neural Information Processing Systems, 35:1883-1895, 2022.

---

[26] Vidyashankar Sivakumar, Steven Wu, and Arindam Banerjee. Structured linear contextual bandits: A sharp and geometric smoothed analysis. In International Conference on Machine Learning, pages 9026-9035. PMLR, 2020.
12

---

Table 2: Notation.
Symbol
Description
A
Action set time
0.
True parameter of the linear model Dimension of 0.
Number of nonzero components in 0_ Random reward pulling arm A, A. Prediction of SeqSEW time [
X,
C7
The confidence set with radius 2" log T and center 0--1
The index of the confidence The probability P(,, = s) drawing index of the confidence set SparseLinUCB The index of the smallest safe confidence set, defined (3.2)
drawn time
4+
Q
The probability P(I, 2 o)
+ +... + In of drawing a safe confidence set in SparseLinUCB
A
The optimistic action for C.
A.
The optimal action A:
Event that E C. for E [T]
det V
Determinant of
A
Notation
In Table we list the most used notations. Next, we recall some definitions that are used throughout this appendix. We have V, I Σ A,A] and
(1018 Σ (X. 10,-00, (0.
0₂
argmin
BER
where Ag Ag is the action chosen by the learner at round t. Recall that a; = log For [n].
A argmaxmaxt max a) = argmax
(la, 0,. + +1alll,, va:)
aE.A.
BEC;
aEA:
where
C 0 DER" 110 11-1 S sai)
Finally, recall definition 2.2 with = -I/T,
> (), - snumm
t-1
C =
θ Rd 11012
s=1
and recall that MKe (0. E C.).
B Analysis of SparseLinUCB
Theorem 3.2. The expected regret of SparseLinUCB with the number of models in 3.1 and a distribution = {gs )ejm) satisfies
E[RT] = (logg) Σ V d2 + (logT) STd/Q (logT)/STd/Q
820
where Q 2=12004 qo-
Proof. Lemma 3.1 implies C. C Cs. Hence, if true and a, then
(0.;A) 2 (0) Vaoll-Elll
(0, C, C C.)
= (0.-1, Ai) /os + (Vao+ Va+lll
13

---

2 (0-1, + va. (1) ( (Vao + va.) 11 (maximality of Ai in Ci)
(0-1, A7) + Va. Vaollill (Vos - va.i 1:llv. - (Vaa + vas Aillv
2 (0,,49 47) - (V - va,)l Afll - (vo5 + va.
(0. E C C.)
(0., A2) - (Vo6 va.) || Afll (Voo + vo. (1
(by Lemma D.3)
(0., 2/ | 1
2 (8., 3/0.1 B/a0l1A911 Aill
(B.1)
where in the first and the third inequalities, use the fact that for any A Rd
(0. - 0--1, A) < 10. - 11-1 ,1lAllvz)>
(Cauchy-Schwarr inequality)
S vvollAlly;
(due 0. E C2)
and for the last inequality,
(0., AA7) S (0) vaoll /aollAillv.t
(0, E C₁, maximality of AQ.)
We can decompose the regret as follows,
RT
(6. A3 1/:1 + Σ
A1:)
T
T -
Σ (0,5 -
A/
Σ
Σ
=
t=1
<
Σ
1(1 2 00. A A1 ((E)). - Σ
1=1
1=1
14 o, min 22.3v 1:1l
$
Σ ((E))).. A;- 1/t + Σ 11, 0, (0. 4; A/-)
Σ
A9llv
(B.2)
Since P(89) 585 S 4. the first sum in the above line easily bounded,
Σ
(B. - A/ s 2TP(EE) 22
1=1
Bounding term a. For each s 2 0, let
T T' I IE [7] det(Vv- E [2n0t 2(0+1)d) }.
Note that de)((V) is monotone increasing w.r.t t. Define s' [log2 det(Vvr)dd. Then,
T = UT s=1
Therefore,
min { 22.3aa APll 1
14

---

By applying Lemma D.5
we obtain
= L
min 22.3voollAillyz
s=1 TET*
= =.
min 1,11,49 v
v
(a. 2 1)
s=1 TET*
<3
E Σ
Σ
min 1.114:111
(Cauchy (Cauchy-Schwarz incquality)
LET
<3va.T
(2d/Q+ + 1/Q)
(due to Lemma D.5
<3Va.T a V (2d 1)s'/Q
= 3 (2d 1)/Q llog dct(Vr))/ /v
= o log SVSd/QQ
Bounding term
Let T3 = E 1(4: s}.
T
E
14 2 (,.) Ai - Att)
11 2 8, min { 2 Van. /aa..1lAA/ || (14/
< E
Σ
t==l
1(1, = $} min { 11:11 Σ Ie [T]
2
V V.TT. T
CCauchy-Schaale inequality)
#20
2
E
V Va,T. T,
Σ KE [T]
min
111 v=
820
2
Σ
V a. T. /2 log det Vi
(Lemma D.I
$20
2 2
Va,T. T,
O(v O(vdlog T)
(upper bound on det(vrr))
$20
2
Va, / [.] d
(Jensen's 's inequality)
#20
=0
Σ V agdTT
ys Tog
(because P(I+ = s) qo.)
$20
Substituting the bounds of and d to (.2)).
we have
E[RT] 5 Σ
Vdo, Tq, + log T T SdT
$20
concluding the proof.
Theorem 3.4. The expected regret of S'SaaseLinUCC run with the number of models in 3.1 distribution q = [qaeoe(n) and using SeqSEW as base algorithm satisfies
E[Ar] = 0 (dS/Q) d
(logTT2) TT2)
(log
15

---

where Q= = Ex 90.
Proof.
T RT
T
188)00, 47 - +
Σ
118 A - A11))
t=1
T
(0., A - A!.!²
HO,,, -5 Σ
$1220,5 0.8}
A
1=1
1=1
00. A7 - A!O1
+
Σ 144< 0,
(minimality of A)
A
t=1
(0., AT A/1)2
$
Σ 10, -
Σ
1 1 2 0,
A
min (1, asl Aill |=l
9
(T < 8
(by applying B.I to
Bounding term + Let s [log2 det Vrd/ By applying Lemma D.5
obtain
Σ
min 1, 1, -1
EET*
9a
E
Σ IET
min {1. (1.114
(a. 2 1)
90
(2d/Q 1/Q)
(due to Lemma D.5
27a,ds/ /Q
dS /
(because s' Olog
Bounding term
1 A; - A/132
E
1(4 o,
A
1(T 2 0, min {
F
min {1.11A }
023 E
Σ
A
rE
[T]
Σ
log det Vr
(due to Lemma D.I
A
$20
d (log 2
(B.3)
A
where the first inequality comes from
(0,, A! max
(0 0,, A/t)
ecc/
16

---

max |10 8. 11.lvv_ || 11 ec
(Cauchy-Scchwanl Inequality)
a A Ilv.
where the last inequality holds because & and 1, both hold, and so 0. E Cc-1 C Ch due to Lemma 3.1 The factor is due to an application the triangular inequality. Substituting the bounds have
of and in (B.2
E[RT] =0( max(8/Q.
d(log T) (1)
A
Corollary B.1. Pick any C 2 1 and let [ge)seju) be chosen as in (.4)) Then the expected regret of SparseLinUCB is
E [T)] Ō min max (C,S/C)Vi,, max { (d
(min
Proof. We consider the following cases based on the value of C.
Case 1: C < 2
9o C 2 According Theorem 3.2
E[RT]= 0
(log T') Σ
d2 4s + VV STd/Q
#20
0 (log Tyny d2 go + (logT)
= mxx(C,s/C]VdT
(due to n = O(log d) and 2 O(S ([SSlog7 T))
Besides, according to Theorem
[ 0 max(S//,dd) dlogg T
A
dlog² 2 T
max((S/o;;)) d}
max (52 d
A
Therefore,
max {d (dP,S/d/09) (
E[Rr] = =
min max (C,S/C)vaT,
A
Case 2: C E 2")
For with 2 2", 2", 9o 222 Letd arg migmm (C2 < 2*). Then, do 2 1/4. According to
Theorem 3.2
F [ =0
(log T)
Σ
v /d2 + (log ( STdd/Q
$20
50 (logT) Σ
Vd2-T (logT)
Σ
Vd2-Tq. + (log T) T) STd/
*E(o,0")
sElo',n]
5 V222T + nCViT + vSTd
17

---

= - max max
(due C -222)) and 2 2 2 5)
Besides, according to Theorem 3.4
d(log
[[r]] = 0 max(5/
A
d(log 7)2
max
A
max ,
Therefore,
E[Rr] = Ō min max (C,S/C)vall max (dP
A
Case C² > 2 Qs 1/n for all E [n]. It is easy to verify that E(RT]
Ö(dVT) and
E[Rr] (dd² / AA). Thus,
E R| = Ō min max (C,8/C)/at max { (8,,51119)))
A
Corollary B.2. Assume that the spursity level S is known and choose distribution q {gs sein]
with 1, where o is set as in 3.2). Then, the expected regret of SparseLinUCE is E(Rr]
Ō Sd
Proof. We follow the same steps as in the proof of Theorem
3.4
The only difference lies in the
bounding term in B.3 We have
10 A;
A
E
111 2 0,
A
(0., Ai AA)²
Σ 118)
40
Σ min (1, (1. }
o (doo
(B.4)
where the second equality is because qo = 1 and so A/t = A₁ = As,, and the first inequality comes from
10.,Ar AA) S max (0 0-, As)
BEC;
< max ||0 8 8.1lvv_ ||
(Cauchy-Schwel -chhar- Inequality)
BECT
1
< 2 Aellv
where the last inequality holds because E and 1 both hold, and so E C.-1 C Cf due to Lemma 3.] Substituting the bounds of and + in B.2). we have
E = 0 Sd(log T)²
18

---

C Analysis of AdaLinUCB
Theorem 4.1. If the random independent noise E, in (2. satisfies Et [-1, for all E [T), then the regret of AdaLinUCB run with 17 //ogg))/ (Tn) n) for 3.1 and q E (0, 1] satisfies
E[RT] < (V Vann + 4v 1/444/22u (20.)//)
dd'log 1+ d
TL2
+ +1+ (V log
= = = mmax
{Vdg, v 5// vdT)
Proof. Let Ti be the set of time steps where Z, 1 in Line of AdaLinUCB and let 72 [T] Ti. For all E Tz the action A₁ E A, is chosen by Exp3 through an adversarial mapping 14 [M]] + A defined in Lines 10 The resulting reward X, [-2, 2] is fed Exp3 as [0, 1]-valued loss (e(4)) = (2 - x/44 where (4(4) = A.. Since To is selected through independent coin tosses with fixed bias q, to bound the regret in Tz and show that
apply the Exp3 regret analysis (for losses chosen by non-oblivious adversary)
Σ (4 0-) 4
Σ (lelle) -((o))
(C.1)
1ET2
tETa
where we used (r) Ag for all t E [T].
We have
RT= = Σ
argmax (a - Ac,
tT
Σ tET
argmaxx (a A9 + A9 Ar, 0z)
aEA:
argmax (a Ap, 0.) + aeAi
Σ
(A Ac, O.)
8E72
Reging
Regrzep
Regexpa is bounded in
hence we only need bound
Reging
Σ
arginax (a A², 0.)
(C.2)
aeA:
1ETa
Let
0 = argmax max (a, 0) and A = argmax(aa 0.). oec; aEA,
aeA:
Recall is the event that
E C2 for all & [T]. Assume holds. We obtain that for [T].
17) s (0: 0., A?) (0,, A;
(because 0, E C. S Cg)
< 10 0, llve ||
(Cauchy-Schwarz inequality)
I vool Ag f'llv=?
(C.3)
where the last inequality is because 03 Cj. Then, assuming & holds, we can bound Reging as
Reging = Σ (0,, A; - -7)
Σ
min Vorl A A18
6ET2
< Σ min 2, 27(1T))
|| [1lllv
(due to a, 22y(1/T)
tETa
< 2 (1/TT)
Σ
min (1,11-9 v
(C.4)
teT2
19

---

where in the first inequality, we use the facts (f.. - -A) - vaol and (f.. - -A? -
(0., S 2.
From Lemma D.3
we have
Σ ET
min [1,11481 v
- Σ
min { 1,, 11,14471 [1,14411 [
1ET2
For each s 2 0, let
T5¹ E T2 E :ee((V--)).. E (2ds 22(0+t1)
so that
T2 = U
#20
Let s' = -llog det (V.)//.. We have
Σ min [1, [1 [|AAillv== }
Reggng
1[8] S 2 (V/(1
(due to C.4
IET2
< 2 20x E
Σ
min {1, 11.114/llv
(due to ag S 2>(1/T))
LET2
$ 2/ 200T
E
min
1,
|1:11 v
(Cauchy-Schwarz inequalitt)
LET
$ 2, 22/20T
Σ
min
1111 v=
TE
(where d s < log det (Vr))
}
S 2 / 200T
min
1, ||A v
IE
(because ||AAlly=] 2 ||4flly=]
< 2/ 200T
(2d + 1)/9
(due to Lemma D.4
$ 2 + 1)aoToo/q
To obtain the final results, have
II X 1 (dmmcc(Vi)) < 1+ TT2
det
(C.5)
where A Aa are the eigenvalues of Vr. Therefore, we have S [loge(1 (1 + TL2/d)).
E [Regimg
1[ < 2 // Vsa 2/ (6do., [og + TT2 /T22/d). [d]
By substituting the bounds on Reging and Regrspa into Ry,, we obtain E[RT,]- E[Regexps 1 ( + E[Reging! + P(E)) 2//6da, // [log(1 TL2/d] + O(v O(VnT(oog)))
where the last inequality is because P(ET) < 1/T from Lemma 2.1 with choice of 8 1/6.
20

---

Finally, we bound Rr. Conditioned on event & and using D.3 vt E (T) 0. E C S Ct S CT. Hence, we can obtain
(0,,
A _ (0) 00, Ag))
(because Os C. C Ci)
- 10 - 0, ve_ 11A22 11,
(Cauchy-Schward inequality)
$ v an AA7) 1ll
(because 07 E CT.)
Hence, conditioned on event &
RT S
Σ
min (2, (0., A7 A&)
1T
Σ
min 2, van | 1
(C.6)
NT
< <2 Ti
Σ min
1, 1,114;112 v.
(Cauchy-Schwarz inequality)
AE
S 22vanlTh
Σ min AE
1, 1,114711% 11
+
Σ
min 1, ||A.
1ET
=2 Ti
Σ min AE(T]
Aell
V
$2 Ti
v log (dtt( Vr)),
(C.7)
where the last inequality is due to Lemma D.I
Therefore, the expected regret for t E Ti is
E(RT, & E[RT, [{8) T P(E))
s E 2/ a.Va,TTi Tıl (2log(det(VV)) +1
TL2
< E
2 avaniiil V
2d
1+ d
+1
2/ LE
[VITi
2d
1+ d
TT2
+1
T12 1
$ 22VonTy
2dlog
+1, 1,
(Jensen's inequality)
d
where the first inequality due to C.7 and P(E)) < 1/T from Lemma 2.1 and the last inequality is due to the fact that for any t [T], with probability T1. Finally, we obtain
E| [[R]] = E(RT.] + E(R
TL2 2dlog 1
< 2 22V Tn |
2 Gdx.. [log(1 + TL2/d)] + O(v n. InTloggw n).
d
Note that n O(log d) and a, MeS T). We obtain
E[RT] = maxx Vod, qd,
S
vdT logT)
which completes the proof.
21

---

D Supporting lemmas
Lemma D.1 (Dani et al. [0]
Let A1, A2,.... Ar E Rd and Vi = I+E A,A for all E [T].
Then
T
Σ
min 1, |||
S dVt(
(D.1)
Moreover,
min
{ L. 11.1A
}
$ log (1 (1+ [1eel1 = =2log det(V(-1)
dei(Vi)
Lemma D.2. For Ct defined in 2.2 we have that Ct S Co for all 1. E [T].
Proof. Recall
8, (0, =
S((ITT)
C++1 =
0 1011
Note that
10112 +
8, - (0, A.)) 2
10:12
Σ
8, (0r, Ai))²
8=1
==1
1 Σ AgA
= =10112 T0
+ Σ A.A.]
- 10:112 + 20, Σ 8 8,11
- -0,
Σ
AsA 8
0r
\==1
|101i; 2 0) V10, 110.112:
(V, + + AA = E.
||0li - 20 TVO0 + ||0:13: = ||0 0e 12:2
Hence, we can express the ellipsoid
C++1 = 110- 0.1li: + 110:112 + Σ 82 (0, A.) (
sx(1m]]
(D.2)
Therefore, for all t 120 0.
0 110 0.112, 10.112 Σ 82, (0 =
C++1
(due (D.))
S 0 |10 0. li, {1(/T)
C 0 110 0. 12: {
(by definition of on)
C++1
(D.3)
concluding the proof.
Lemma D.3. For any $ S 4 n and t E [T],
||4f]| < Il
Proof. Note that
A/ argmax max (8, a) = argmax((a, 0.-1) + varllallyzt
aεA, BEC
aEA.
A = argmax max (0, a) = argmax (a, 0 + Vayllallyzt aEA,
a'A, BEC
22

---

For contradiction, we assume || < || Since || 111 < -1A4111 1
||
+
|| Besides, according to the definition of A/ and Ay, we have
(A), vap a - (A2, 01-1) + vap 11 Afllv
(D.4)
< (A) 0c-1) + v.g 11 [[=
(D.5)
- (4% 0,-1) + / @ Ai
(D.6)
where the first inequality is due to the definition of Ar, the second inequality is due Vap Vog. and the last inequality is due the definition of A?. From the above results, we further have
(A) Ap, 101) S ( v ||4] 1421ly;: v V (1 (I.A y
(Due to D.4
(Due to assumption
|| || < [481ly and 0ig > Opp)
S (A A.. 02-))
(Due to (.6
We obtain a contradiction. Therefore,
||4 2 ||4
(D.7)
Lemma D.4.
E
Σ
min { 1, I|; :}
< 2d/q 1/q.
AETS
Proof. Let det(V--)) = (9 and det 47(7)) = (9i-1 + xxe) For each 2 0, let
{ t [T] det(Vi-1) E [ 22((+1)) }
T =
Since Ty¹ CT. show
Σ min [1.114711 v } NE
< 2d/q + 1/9.
we only need prove
min [1,114711 Σ LTT
v=
< 2d/4 + 1/g.
We let 4, 1 if the coin tosses in the t's round is Head and 0 otherwise. We divide T into two disjoint parts T and T.. Specifically,
for T it holds that for E T del(VV AA(A)) < 2d(++1),
for Ts, it holds that for E T's, det.Ve (A;)) 2d(++1),
From definition of T and the fact that if I, 1, V1 = Vn- A7 T. we have
Σ 2 I 2..
1E
From Algorithm 2 with probability q, 4 1. Therefore, if we let (Feheem be the natural filtration of (Ar, 1,, X1 Keeer, we have
2a > E
Σ xt 1
IET
23

---

E
Σ Tt 1 1..E
LE(T]
E
Σ TE[T]
E
1/.1 T*) TT)
(Law of total expectation)
Σ [E[T]
1(ET)) F-1
(re and {1 E ] are Fi-r-meauurable)
Σ
E
E 1ft E TT
(Ie is an independent coin-tossing)
[E|T
qti
Σ LET
It
and therefore IE (EETT Zt
S 2²//g. For t E T we further have
(det(Ve-1 + AA(A))
min {1,114711
S 2oo
(due to Lemma D.1
dot(V(-1)
1 Zt
2d
4t-1
S 2d
1 2
(since E E TTT 9t-11 2 2*)
(due to log(1 + S x for x > 0.)
2
Therefore,
Σ min (1. 1177 w= TET
SE
2d
2d E
Σ
St
$ 2d/q.
2
1ET
LET
From definition of T., if I = and E T det(V)) > 20(++1) Then, for all > t, $ T
Therefore, there is at most one t E T with 1 1. We obtain
Σ min {1. |14 11:11111 15
S
T < 1/9
where the last inequality because with probability q. I 1. By combining the bounds for t T and E T together, lemma follows.
Lemma D.5. Let Q Eszo 9s. Then,
E
Σ min 1,11 v= < 22//2+1/Q.
LIET*
Proof. Let det(VV-1) = (d- Let x; satisfies det(V,-) + T) = (9-11 + xz)a We let I = 1[4 2 o}. We divide T into two disjoint parts T and T5. Specifically.
for T it holds that for E T de + AP(Ag) < 2d(++1).
for Ts, it holds that for t Ts, det((V + AP(AP) 2d(++1),
24

---

Note that for 1, 2
log(det(VV)) +
= =log(det(VV)) log(V[-1)>
AA(A?))) log(V--1)
(due to Lemma D.I
=log(1 + || 11 [[z log(1 + +114f11==1
20.
(due to Lemma D.3
and I, 2 o, then 2/ 2 2t. Hence, Therefore, if we let (eet(V211= A/ = (qt-1 2/)²
Σ
T 2
Note that P(, 2 20 = We have
Eez0.e =0
Q. Let (Fr (Fi) be the natural filtration of (A, It, X2 Xe)T
2 2
E
Σ It It
1ET
E
Σ
It 1 1(1E
[E(T)
Σ
E [r I 4. 1.t
[E[T]
Σ
[ I 1ft T*)
(Law of total expectation)
(E[T]
Σ
E 1st T*) [4
(ax and 1 T are measurbblab
[E[T]
Σ
E
1ft E -1 Q1
(Ie an independent coin-tossing)
[E[T]
QE
Σ
Tt
IET
and therefore
F
221QQ.
IET
For t T" we further have
min
(1,
||
min { [1.1 11.1A/1112 11- 1|2-_
v=
/de((Ve11 + (A
2og
(due to Lemma D.I
det(VV-1)
1+ Et
2d log
Zt
2d log
1 +
(since E T., 9:-1 2 2*)
2a
2d Zt
(due to log(1 +x) < r for r > 0.)
2
25

---

Therefore,
2d 3t
2d
min 1. 11
E
2t
2d/Q.
2
2
TT
AE
From definition of T., I 1 and E Ts, then 1, and
det(VV) = det (VnttV + (A det (V + A7(4g) (8 1)¹.
Then, for all 7 t, $ T Therefore, there is at most one & T with 17 1. We obtain
Σ min [1.114911 $ 7 TET
S 1/Q.
where the last inequality is because with probability E.z0 Q. I 1. By combining the bounds for E T and t T together, lemma follows.
E
Experimental details
The code used in the experiments can be found in the following repository: httpp:://gtthb:: com/ http:/pprrttttaaassttooo sollsstttttlssseetiio selection
E.1 Settings common to all algorithms
Arm set: A A for all [T). A c 5d-1 (the unit sphere in Rd) is set of d- dimensional vectors drawn independently and uniformly at random from gd-1, with d = 16 and |A| = 30.
02 is S-sparse (S 1,2, 4, 16) vector generated follows: before the game starts, draw (o.)...... (0~)s ~ 98 and (0.) 0 for all A: > S.
The noise on rewards: { are i.idd with & ~ Unif([-1,
Number of iterations: T = 10a
Number of models: n = 6.
Radius of confidence sets: ag = 0, and a; 2 log for 1,.
Prior distribution {q=}aet6)
For _ =
-
6 5 61 6:0
-
-For For_Theory, {g. = 2 4 constant.
C
C
16
32
C C
64
where C
64
63
is a normalizing
Each plot is the result of 20 repetitions for each method. The shade represents the 1-standard deviation bound.
Hardware: Lenovo Thinkpad P16s Gen 2 Laptop Type 21HL
-PPU: 13th Gen Intel(R) Core(TM) i7-1360P 2.20 GHz
-RAM: 32GB
Computation time: total 1338.38 seconds.
E.2 AdaLinUCB details
Since empirically observed that Exp3 provided enough exploration, aggressively set the forced exploration parameter to zero.
The learning rate of Exp3 was set to 2/ logn see 5
Given the prior distribution {g. (gake we set P as follows:
exp St.e)
Pt. Σラ exp St.)
26

---

E.3
OFUL details
We used the log-determinant form of the confidence set based Abbasi- Yadkori Abbasi-Yadkori Theorem 2), which gives the choice
al.
v 2 log T + log (V,)
for the parameter in
1.1 when À = and = 1/T.
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims presented in the abstract and introduction accurately represent the contributions and scope of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have added paragraph in the conclusions section discussing the limitations of our work.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiaatinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
28

---

Answer:
[Yes]
Justification:
We provide the full set of assumptions and complete proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
29

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We include our code in our supplementary material and will make the full code public if this work gets accepted.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
Policyllllyyyyyyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.ccpublle pwwppppguuuiieeeeep httpc///uuidess/deeuuuubiiis
(CodeSubiisss wwtplubmmmssiiiii ssiiiiolcccy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide all the details of our experimental setting.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We reported 1-sigma error bars our plots.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
30

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We state all information on the computer resources in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Our research conform with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no socictal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
31

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: Our paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
32

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "4B8QT8d9WM", "reviewer": "Reviewer_zJ6Y", "summary": "This paper studies Linear bandits with adversaries when the underlying parameter $\\theta$ is sparse. It combines a previous sparse linear regression algorithm named SeqSEW with LinUCB, proposing an algorithm named SparseLinUCB. It also proposes a variant of the EXP3 algorithm named AdaLinUCB. Regret bounds dependent on the sparsity dimension $S$ are proved. Experiments are conducted on synthetic data.", "questions": "See Weaknesses", "limitations": "The authors have addressed the limitations and societal impact.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "1. The paper proposes algorithms for sparse linear bandits with adversarial action sets. It proved a regret upper bound better than previous when the sparsity dimension $S$ is quite small with no assumptions on the sparsity structure. If the sparsity level is known, the result is optimal.\n2. It also provides an instance-dependent regret bound.\n3. It conducts synthetic experiments to show its better performance.", "weaknesses": "1. The paper misses many very related works, especially those on K-armed bandits and linear bandits.\n\n2. For the main algorithm design, I cannot see the necessity to use an online learning oracle to predict the reward $\\hat X_t$ and then calculate the least squares estimation when having access to the real reward $X_t$. Could you explain it further?\n\n3. The writing is unclear. \n\n(1) In Line 176,  \"the distribution $\\\\{q_i\\\\} _ {i \\in [n]}$\" is not well defined, over what? \n\n(2) The notation of the confidence set in Line 177 is contradictory with the notation in Appendix A, as it uses 2-norm rather than the $V_{t-1}$ norm. \n\n(3) In equation 3.1, $\\gamma$ is a problem-dependent term so you cannot set the exact value of $o$, as is done in Corollary 3.3.\n\n(4) Line 240: in terms of what?\n\n4. Line 249: “the parameter q does not provide a similar flexibility”, so I do not see the use of this probable selection, what is the benefit of the new algorithm design in Section 4?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable time and effort in providing detailed feedback on our work. We now address your questions one by one.\n\n---\nQ1: The paper misses many very related works, especially those on K-armed bandits and linear bandits.\n\nA1:  It would be useful to have some concrete pointers to the missing works, but we will definitely browse more carefully through the relevant literature.\n\n---\n\nQ2: For the main algorithm design, I cannot see the necessity to use an online learning oracle to predict the reward.\n\nA2:  The use of an online linear regression oracle for sparse linear bandits is an established technique whose advantages in the analysis have been shown in [2] and also in bandit book [17], see our comment in Line 149.  In particular, using a sparse online learning algorithm provides a dependence on the sparsity parameter $S$ in the confidence bound. We therefore use Lemmas 2.1 and 2.2 from [2] to set $\\gamma(1/T) = O(S\\log T)$. Thus, there exists some constant $C$ such that \n\n$\\mathcal C_t=\\\\{ \\theta \\in \\mathbb R^d: \\|\\theta\\|_2^2+ \\sum_s(\\hat X_s - \\langle A_s, \\theta \\rangle)^2 \\leq CS\\log T \\\\}$.\n\n\nIt is unclear how such a dependence could be obtained using the standard least square estimator, which would only provide a dependence on $d$.\n\n---\n\nQ3: Line 249: “the parameter $q$ does not provide a similar flexibility”, so I do not see the use of this probable selection, what is the benefit of the new algorithm design in Section 4?\n\nA3: The main advantage of AdaLinUCB is its empirical performance, as we explain in Lines 243-244 and demonstrate in our experiments where it outperforms both OFUL and SparseLinUCB. This improved empirical performance is due to AdaLinUCB’s ability of tuning its distribution based on observed rewards.\n\nFrom a theoretical viewpoint, AdaLinUCB achieves a regret bound of $\\tilde{O}(\\sqrt{T})$, using novel techniques descibed in Lines 61-100. Previous analyses of Exp3-based algorithms in [11] and [24] only achieved $\\tilde{O}(T^{2/3})$ regret bounds, even under i.i.d. assumptions on the generation of the action sets, see Lines 122-131 for a description of these related works.\n\n---\n\nQ4: In Line 176, “the distribution $\\\\{q_i\\\\}_{i\\in[n]}$” is not well defined, over what?\n\nA4: In Lines 174-176 we say that the algorithm uses a hierarchy of confidence sets of increasing radius and draws the index $I_t$ of the confidence set by sampling from the probability distribution $\\\\{q_i\\\\}_{i \\in [n]}$. We will clarify that the distribution is over the indices of the confidence sets, and make it explicit that $n$ is an input parameter to SparseLinUCB.\n\n---\n\nQ5: The notation of the confidence set in 177.\n\nA5:  This is a typo. It should be $V_{t-1}$ norm. Thank you for your careful reading!\n\n---\n\nQ6: In equation 3.1, $\\gamma$ is a problem-dependent term so you cannot set the exact value of $o$, as is done in Corollary 3.3.\n\nA6: In Corollary 3.3, we explicitly state that it is assumed the sparsity level $S$ is known, as detailed in Lines 194-195. With $S$ known, the upper bound of $\\gamma(\\delta)$ can be easily calculated from its definition.\n\n---\nQ7: Line 240: in terms of?\n\nA7: This is a typo. We will remove the words “in terms of”.", "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": "XSt7YEWZmc", "reviewer": "Reviewer_muo1", "summary": "This paper studies the stochastic linear bandits when the action set can be arbitrarily chosen without some additional assumptions. And the authors propose a randomized sparsity-agnostic bandit algorithm using the model selection idea, and show that EXP3 can be used as the master algorithm to obtain a decent regret bound. Experimental results are included in the end to verify the high efficiency of the proposed algorithms.", "questions": "1. Why is the boundness of the random noise necessary in your theoretical proof?\n2. Is it possible to bound the regret with high probability instead of the expected value? If some existing literature proposed the regret bound with high probability, then it may not be fair to do the direct order comparison in Table 1.\n3. Can you report the running time of your method in the experiments?", "limitations": "No negative societal impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is easy to read, and most parts are pretty clear. E.g. Table 1 helps reader catch up all the existing literature and their differences quickly.\n2. This paper studies an interesting and important problem when the arm set is arbitrarily chosen under the sparse linear bandit problem. I didn't check the proof in appendix in detail but all arguments seem reasonable to me.\n3. Empirical results are provided to illustrate the high efficiency of the proposed algorithms.", "weaknesses": "1. The used techniques are based on the existing literature (e.g. seqsew, exp3 master algorithm). It will be better to show the theory novelty of this work in a separate paragraph. \n\n2. Lower bounds are not provided, as the authors mention in the limitation parts. So it is a little bit hard for readers to justify how good are the proposed bounds.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your valuable time and effort in offering detailed feedback on our work. In the following, we address your questions one by one.\n\n---\n\nQ1: The used techniques are based on the existing literature (e.g. seqsew, exp3 master algorithm). It will be better to show the theory novelty of this work in a separate paragraph.\n\nA1: We do have a 40-line paragraph “Technical challenges” (Lines 61-100) explaining the theoretical novelty.  One of our main technical contributions is demonstrating that our exploration, measured by $\\det V_{t-1}$, grows very rapidly, as highlighted in Lines 81-86 (the proof details are shown in Lemmas D.4 and D.5). As an example to show the power of our new techniques, we achieve a $\\sqrt{T}$ regret bound for AdaLinUCB, whereas previous works [11,24] using the Exp3 to learn the probability over a hierarchy of confidence sets have a regret bound of only $T^{2/3}$.\n\nPlease refer to the Technical challenges paragraph for a full list of our original contributions.\n\n----\n\nQ2: Why is the boundness of the random noise necessary in your theoretical proof?\n\nA2: Note that our results in Section 3 do not require boundedness of the noise, but only 1-subgaussianity, see (2.1) in Lines 138-139. We only require $\\epsilon_t \\in [-1,1]$ in Section 4 because the Exp3 algorithm, which is used in the proof of Theorem 4.1, requires bounded rewards, which in turn requires the noise to be deterministically bounded.\n\n---\n\nQ3: Is it possible to bound the regret with high probability instead of the expected value? If some existing literature proposed the regret bound with high probability, then it may not be fair to do the direct order comparison in Table 1.\n\nA3: Thanks for pointing out this interesting question. We believe our in-expectation regret bound for SparseLinUCB could be extended to a bound in high probability after some changes in the analysis. As these changes do not appear to be trivial as they require a somewhat intricate martingale concentration analysis, we will leave this extension to future work.\n\nIn the revised version, we will also add notes to the table highlighting the algorithms that are high probability.\n\n---\n\nQ4: Can you report the running time of your method in the experiments?\n\nA4: Although there were slight differences depending on the sparsity level or initial probability distribution, on average, a run of OFUL took 0.7 seconds, a run of SparseLinUCB took 1.4 seconds, and finally, a run of AdaLinUCB took 1.9 seconds. The longer runtime of SparseLinUCB and AdaLinUCB is motivated by the need of managing an ensemble of models. However, as we did not optimize the code, we expect these runtimes to be improvable.", "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": "pvlkEihY1a", "reviewer": "Reviewer_KeoW", "summary": "This paper proposes statistically efficient linear bandit algorithms capable of handling cases where prior knowledge of the sparsity level $S$ is not given. The first algorithm, SparseLinUCB, achieves a $\\tilde{O}(S \\sqrt{dT})$ regret bound without any stochastic assumptions on the context vector, covering adversarially given context vectors. The main idea involves sampling the radius of the confidence set for the true reward parameter $\\theta_*$ from a specific distribution and then selecting the optimistic action. It matches the lower bound when sparsity information is provided. The second algorithm, AdaLinUCB, updates the sampling distribution of the confidence radius using an approach (Exp3) that increases the likelihood of selecting a radius providing higher rewards. AdaLinUCB also achieves a $\\tilde{O}(\\sqrt{T})$ regret bound. Various experiments support the theoretical results of the proposed algorithms.", "questions": "- (Related to the 1st bullet in Weaknesses) Can AdaLinUCB still achieve the currently presented regret bound if the action set (context vectors) is given by an adaptive adversary? If not, can you briefly explain the issue?\n- (Related to the 2nd bullet in Weaknesses) It seems that how $\\set{ q_s }_{s \\in [n]}$ is determined would impact the regret bound. You introduced a specific distribution in Eq. (3.3). How does the regret bound change if $ n$ is significantly increased or decreased?\n- The motivation for updating the confidence radius distribution at each time step in AdaLinUCB is interesting. However, the current result shows a looser regret bound compared to SparseLinUCB. Despite the computational cost of updating the distribution, there seems to be no statistical gain. In what instances would it be better to use AdaLinUCB over SparseLinUCB? Also, can you briefly explain why AdaLinUCB performs better empirically?", "limitations": "The authors have well-addressed the limitations and further research directions in Section 6. The content discussed in this paper appears to have little to no negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The motivation for the problem addressed in the paper is well explained, and the related work is thoroughly described. Overall, the paper is well-written and easy to understand.\n- The first algorithm, SparseLinUCB, is, to my knowledge, the first sparsity-agnostic linear bandit algorithm for adversarial context vectors. Additionally, it matches the lower bound regret when sparsity information is provided.\n- The second algorithm, which updates the confidence radius distribution at each time step, is also very interesting. Previous works using similar methods achieved loose regret bounds ($\\tilde{O}(T^{2/3})$), whereas the proposed algorithm achieves $\\tilde{O}(\\sqrt{T})$ regret (though I have not rigorously checked this proof).\n- Various numerical experiments support the theory behind the proposed algorithms.", "weaknesses": "- The SparseLinUCB algorithm does not make stochastic assumptions about the action set (context vectors), thus providing theoretical guarantees even in the case of an adaptive adversary. However, AdaLinUCB is described as an algorithm for stochastic linear bandits. It seems that the stochastic assumptions required for AdaLinUCB's regret bound are not explained.\n- The explanation about $n$ in the confidence radius distribution $\\set{ q_s }_{s \\in [n]}$ appears insufficient. Additionally, there seems to be no term for $ n $ in the regret bound. I am curious whether the regret bound is independent of $ n$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your valuable time and effort in offering detailed feedback on our work. In the following, we address your questions one by one.\n\n----\n\nQ1: The SparseLinUCB algorithm does not make stochastic assumptions about the action set (context vectors), thus providing theoretical guarantees even in the case of an adaptive adversary. However, AdaLinUCB is described as an algorithm for stochastic linear bandits. It seems that the stochastic assumptions required for AdaLinUCB's regret bound are not explained.\n\nA1: AdaLinUCB is indeed designed to handle adaptive adversarial action sets (see, for example, the initial lines 414-419 of the proof where the adversarial nature of the action set appears in the analysis). We will clarify this in the revision. There may have been some confusion regarding the title of Section 4: \"Adaptive Model Selection for Stochastic Linear Bandits.\"  In the literature, such as Chapter 19 of the bandit book [17] and reference [2], the term \"stochastic linear bandits\" typically refers to the presence of stochasticity in the subgaussian noise term $\\epsilon_t$, as outlined in Equation (2.1).\n\n---\n\nQ2: The explanation about $n$ in the confidence radius distribution $\\\\{q_s\\\\}_{s\\in [n]}$ appears insufficient. Additionally, there seems to be no term for $n$ in the regret bound. I am curious whether the regret bound is independent of $n$.\n\nA2: As stated in Line 182, we choose $n = \\Theta(\\log d)$, which is large enough to ensure $\\alpha_n \\geq \\gamma(1/T)$. We will clarify this fact in the revision.\n\n---\n\nQ3: (Related to the 2nd bullet in weaknesses) It seems that how $\\\\{q_s\\\\}_{s\\in [n]}$ is determined would impact the regret bound. You introduced a specific distribution in Eq. (3.3). How does the regret bound change if $n$ is significantly increased or decreased.\n\nA3: Increasing $n$ beyond $\\Theta(\\log d)$ significantly affects the regret bound of Theorem 3.2 through the choice of $q_s$. If we increase $n$, the regret upper bound approximately becomes $O(n\\sqrt{dT})$. Indeed, following our choice $q_i \\approx 2^{−i}$ (Eq. (3.3)), the first term in Lines 190-191 has order $O(n\\sqrt{dT})$, while the second term has order $O(S \\sqrt{dT})$ since $Q\\approx \\sum_{i>o} 2^{-i} \\approx 2^{-o}\\approx O(1/S)$, regardless of the size of $n$. Therefore, the final regret bound becomes of order $O(n\\sqrt{dT})$. Intuitively, this makes sense, as increasing the number of models increases the exploration, which eventually has a negative impact on the regret. \n\nIf $n$ is decreased such that $\\alpha_n < \\gamma(1/T)$, then $\\theta^*$ may not belong to any confidence set in our hierarchy, and the regret could thus become linear in $T$. As such, we must ensure $\\alpha_{n}\\geq \\gamma(1/T)$ and highlight it in Line 181.\n\n---\n\nQ4: The motivation for updating the confidence radius distribution at each time step in AdaLinUCB is interesting. However, the current result shows a looser regret bound compared to SparseLinUCB. Despite the computational cost of updating the distribution, there seems to be no statistical gain. In what instances would it be better to use AdaLinUCB over SparseLinUCB? Also, can you briefly explain why AdaLinUCB performs better empirically?\n\nA4: AdaLinUCB works better empirically since it automatically adjusts the radius of the confidence bound. Theoretical confidence bounds are typically set very conservatively to ensure error probability guarantees for hard environments (e.g., when the action set is chosen by the adaptive adversary), which often results in over-exploration. For example, in Chapter 36 of the Szepesvari and Lattimore book \"Bandits,\" the sixth note in Section 36.5 mentions that values of the Linear Thompson Sampling parameter (i.e., the variance of the posterior distribution playing a similar role to the radius of the confidence bound in UCB) which show good empirical performance do not have any theoretical guarantee. Conversely, the values of the parameter ensuring a solid theoretical guarantee consistently perform poorly in practice.\n\nAs a future research direction, we can further explore the gap between the practical superior performance and theoretical limitations of AdaLinUCB, and even consider what the lower bound for sparsity-agnostic linear bandits might be.", "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": "EXxqQuR3SV", "reviewer": "Reviewer_9XZb", "summary": "This paper studies the sparse linear bandit problem without the prior knowledge of sparsity. The studied problem also considers general setup in which the context is chosen by an adaptive adversary and action set is not imposed with additional assumptions. Then, A OFUL based algorithms are proposed and regret bounds are provided.", "questions": "Can authors provide another distribution selection case which can recover dS/Delta instance-dependent bound in known sparsity and adaptive adversary setup?", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Lifting assumptions used in existing works while still maintaining comparable or even better regret bounds.\n\n- The proposed algorithm provides an instance-dependent regret bound and worst-case bound as well.\n\n- As the performance of SparseLinUCB highly depends on distribution q, different choices of q are shown.\n\n- Numerical experiments are provided to support the significance of AdaLinUCB algorithm.", "weaknesses": "- The instance dependent regret bound shows no improvement compared with standard OFUL algorithm, and could be even worse than that of OFUL, e.g., S^2>d.\n\n- For known sparsity and adaptive adversary setup, the instance depedent regret bound in Corollary 3.5 is worse than that of [2], which is dS/Delta.\n\n- The regret bound of SparseLinUCB is sensitive to the choice of distribution q. Though authors provide a specific example on the choice of q, the regret bound now highly depends on the choice of constant C. For example, if one chooses C=1, the instance dependent bound is worse than that of OFUL when S^2>d.\n\n- For the action chosen (step 5 in Algorithm 1), it could be difficult to compute A_t since this optimization problem contains non-linear term and the action set is arbitrary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your valuable time and effort in offering detailed feedback on our work. In the following, we address your questions one by one.\n\n---\n\nQ1: Can authors provide another distribution selection case which can recover $dS/\\Delta$ instance-dependent bound in known sparsity and adaptive adversary setup?\n\nA1:  Yes, this can be achieved by setting $q_o = 1$. Then, Theorem 4 of [2] directly implies a problem-dependent bound of order $\\tilde{O}\\left(\\frac{dS}{\\Delta}\\right)$ for $q_o = 1$. We will note this result in the revision.\n\n----\n\nQ2: For known sparsity and adaptive adversary setup, the instance-dependent regret bound in Corollary 3.5 is worse than that of [2], which is dS/Delta.\n\nA2: See A1. For a known sparsity setup, our regret bound can be of the same order as that of [2].\n\n---\n\nQ3: Why the instance dependent regret bound shows no improvement compared with standard OFUL algorithm.\n\nA3:  We have provided some intuitions on why it is difficult to provide a problem-dependent bound that benefits from sparsity in Lines 214-220. Essentially, as long as you set $q_{n}$ as a constant (even as small as $1/\\sqrt{T}$), the regret will scale as $\\tilde O(d^2 / \\Delta)$. \n\n---\n\nQ4: For the action chosen (step 5 in Algorithm 1), it could be difficult to compute $A_t$ since this optimization problem contains non-linear term and the action set is arbitrary.\n\nA4: The computation of $A_t$ in Step 5 of Algorithm 1 is as hard as computing the prediction in the OFUL algorithm, which can be done efficiently when the action set is finite. In the case of arbitrary actions sets, not much can be said about the computational efficiency of solving this problem, see [17, Section 19.3.1].", "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:

Meta-review: This paper studies sparse linear contextual bandits, and developed new regret bounds when the sparsity is unknown. The reviews agree that the paper makes descent contribution to the problem.
Decision: Accept (poster)