Sparsity-Agnostic Linear Bandits with Adaptive Adversaries

Authors: tianyuan  jin
kyoungseok  jang
nicolò  cesa-bianchi
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 17:16:47

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.

Main paper: 
 introduction: 
 K-armed bandits are a basic model of sequential decision-making in which a learner sequentially chooses which arm to pull in a set of K arms. After each pull, the learner only observes the reward returned by the chosen arm. After T pulls, the learner must obtain a total reward as close as possible to 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 t of a linear bandit problem, the learner receives an action set A t ⊂ R d from the environment, chooses an arm A t ∈ A t based on the past observations, and then receives a reward X t . In this work, we consider the stochastic setting in which rewards are defined by X t = ⟨θ * , A t ⟩ + ε t , where θ * ∈ R d is a fixed latent parameter and ε t 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 t the arm a ∈ A t maximizing ⟨θ * , a⟩ and the total reward obtained by the learner.In stochastic linear bandits, the regret after T rounds is known to be of order dT 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 θ * . Hence, one would like to design algorithms that depend on the number S ≪ d of relevant features without requiring any preliminary knowledge on θ * . This is captured by the setting of sparse linear bandits, where θ * is assumed to have only 0 < S ≤ 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 instance-dependent regret bound of O Sd ∆ . 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-agnostic setting, i.e., when S is 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 et al. [22] prove a O ST sparsity-agnostic regret bound. More recently, Dai et al. [9] showed a sparsity-agnostic bound O S 2 √ T + S √ dT when the action set is fixed and equal to the unit sphere. In a model selection setting, Cutkosky et al. [8] prove a O S 2 √ T sparsity-agnostic regret bound for adversarial action sets, but under an additional nestedness assumption: (θ * ) i ̸ = 0 for i = 1, . . . , S. Surprisingly, no bounds improving on the O d √ T regret of the OFUL algorithm [1] in the sparsity-agnostic case are known that avoid additional assumptions on the sparsity structure or on the action set generation.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-agnostic linear bandit algorithm, SparseLinUCB, achieving regret O SdT 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 = o( √ d), our bound is strictly better than the OFUL bound O dT . • Our analysis of SparseLinUCB simultaneously guarantees an instance-dependent regret bound O max{d 2 , S 2 d}/∆ , where ∆ is the smallest suboptimality gap over the T rounds.• If the sparsity level is known, our algorithm recovers the optimal bound Θ( √ SdT ). • We also introduce AdaLinUCB, a variant of SparseLinUCB that uses Exp3 to learn the probability distribution over a hierarchy of confidence sets in stochastic linear bandits. Unlike previous works, which only showed a O T 2/3 regret bound for similar approaches, AdaLinUCB has a O √ T regret bound. In experiments on synthetic data, AdaLinUCB performs better than OFUL.Technical challenges. Recall that the arm chosen in each round by OFUL isA t = argmax a∈At ⟨a, θ t ⟩ + √ γ t ∥a∥ V -1 t-1 (1.1)where θ t is the regularized least-squares estimate of θ * , V t-1 = I + s<t A s A ⊤ s is the regularized covariance matrix of past actions, and √ γ t is the radius of the confidence setEQUATIONThe squared radius γ t = O(d ln t) is such that θ * belongs to (1.2) with high probability simultaneously for all t ≥ 1. Our approach, instead, builds on the online to confidence set conversion technique of Abbasi-Yadkori et al. [2] , where they show how to design a different confidence set for θ * 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(S log T ), they obtain the optimal regret O √ SdT for sparse linear bandits. Unfortunately, this result requires knowing S to properly set the radius of the confidence set. Our strategy SparseLinUCB (Algorithm 1) bypasses this problem by running the online to confidence set conversion technique over a hierarchy of nested confidence sets with radii α i = 2 i log T for i = 1, . . . , n = Θ(log d). The framework of Abbasi-Yadkori et al. [2] guarantees that, for any sparsity value S ∈ [d], there is a critical radius α o = O(S log T ) such that, with high probability, θ * lies in the set with radius α i for all i ≥ o. SparseLinUCB randomizes the choice of the index i of the confidence radius α i , used for selecting the action at time t. If (3.3) . The nested assumption refers to (θ * ) i ̸ = 0 for i = 1, . . . , S. The minimum signal and the compatibility condition refer to assumptions on the distribution of the action set and on the smallest value of the non-zero elements in θ * . Smoothed adversary refers to adversarially selected action sets with added Gaussian noise. The regret bounds listed in [1, 2, 23, 8, 25, 18, 9] are high-probability bounds: with high probability, the regret is of the same order as the bound in the ✓ ✗ O(S √ T ) Compatibility Dai et al. [9] ✓ ✗ O(S 2 √ T + S √ dT ) Action set is unit sphere Lower bound [17] ✗ ✓ Ω √ SdT - This paper ✓ ✓ O min S √ dT , 1 ∆ max{d 2 , S 2 d} - This paper ✗ ✓ O √ SdT -the random index I t is such that I t ≥ o, then we can bound the regret incurred at step t using standard techniques [1, 2] . By choosing P(I t = i) proportional to 2 -i , we make sure that larger confidence sets (delivering suboptimal regret bounds) are chosen with exponentially small probability. If I t < o, then θ * is not guaranteed to lie in the confidence set of radius α It with high probability.Our main technical contribution is to show that the regret summed over these bad rounds is bounded by O SdT /Q , where Q = P(I t ≥ o). The proof of this bound requires showing that the regret in a bad round t (whenI t < o) can be bounded by √ α o ∥A o t ∥ V -1 t-1 . Proving that ∥A o t ∥ V -1 t-1shrinks fast enough uses the fact that det V t grows fast enough due to the exploration in the good rounds t (when I t ≥ o). This is done by a carefully designed peeling technique that partitions [T ] in blocks based on the value of det V t .To extend our analysis of SparseLinUCB and obtain instance-dependent regret bound, we apply the techniques of Abbasi-Yadkori et al. [1] to show that the regret over the good rounds is bounded by O d 2 /∆ . The regret over a bad round t is controlled by(α o /∆)∥A o t ∥ 2 V -1 t-1and-using techniques similar to the instance-independent analysis-we bound the regret summed over all bad rounds with O Sd/(Q∆) .Given that SparseLinUCB uses a fixed probability of order 2 -i to choose its confidence radius α i , it is tempting to explore adaptive probability assignments, that increase the probability of a confidence set proportionally to the rewards obtained by the actions that were selected based on that set. Algorithm AdaLinUCB (see Algorithm 2) is a variant of SparseLinUCB using Exp3 [4] to assign probabilities to confidence sets. The analysis of AdaLinUCB combines-in a non-trivial way-the analysis of Exp3 (including a forced exploration term q) with that of SparseLinUCB. Although the resulting regret bound does not improve on OFUL, our algorithm provides a new principled solution to the problem of tuning the radius in (1.1) . Experiments show that SparseLinUCB can perform better than OFUL.Sparse linear bandits. With the goal of obtaining sparsity-agnostic regret bounds, different types of assumptions on the action set have been considered in the past. Starting from the O(S √ T ) 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 as the minimum eigenvalue of the covariance matrix [9, 15, 16, 20] . Others assumed a stochastic action set with strong properties, such as compatibility conditions or margin conditions [3, 6, 7, 19, 22] . As far as we know, there has been no research on adaptive adversarial action sets after [2] .Model selection. Sparse linear bandits can be naturally viewed as a bandit model selection problem. For example, Ghosh et al. [14] establish a regret bound of O(√ ST + d 2 /α 4.65) for a fixed action set, where α is the minimum absolute value of the nonzero components of θ * . Quite a bit of work has been devoted to sparse regret bounds in the nested setting. With i.i.d. and fixed-size actions sets, Foster et al. [12] achieve a regret bound of order O S 1/3 T 2/3 /γ 3 in the nested setting, where γ is the smallest eigenvalue of the covariance matrix of A t . Under the same assumption on the action set, Pacchiano et al. [24, 23] T ) for nested settings. They also obtain simultaneous instance-dependent bounds, in particular, Pacchiano et al. [25] achieve O (Sd) 2 /∆ . Compared to 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 γ t = O(d log t), smaller choices of the radius in (1.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 [21, 23, 24] . In particular, AdaLinUCB builds on [11] , where they show that running Exp3 as the master algorithm over instances of OFUL with different radii has a better empirical performance than Thompson Sampling and UCB. Yet, they only show a regret bound of O T 2/3 when the action set is drawn i.i.d. in each round (they also prove a bound of order √ T , but only under additional assumptions on the best model). This is consistent with the results of Pacchiano et al. [24] , who also obtained a regret of the same order using Exp3 as master algorithm. 
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 A t ⊂ R d ; 2. The learner choose an arm A t ∈ A t ; 3. The learner obtains a reward X t .We assume the adversary is adaptive, i.e., A t can depend in an arbitrary way on the (possibly randomized) past choices of the learner. The reward in each round t satisfiesX t = ⟨A t , θ * ⟩ + ε t .(2.1)Here θ * ∈ R d is a fixed and unknown target vector and {ε t } t∈[T ] are independent conditionally 1-subgaussian random variables. We also assume ∥θ * ∥ 2 ≤ 1 and ∥a∥ 2 ≤ 1 for all a ∈ A t and all t ∈ [T ]. 1 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 t , and the reward obtained by the strategy choosing arm A t ∈ A t for t ∈ [T ],R T = T t=1 max a∈At ⟨a, θ * ⟩ - T t=1⟨A t , θ * ⟩. 1 The choice of the constant 1 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 onS = ∥θ * ∥ 0 = d i=1 1{θ i ̸ = 0}corresponding to the number of nonzero components of θ * .Establishing a confidence set including the target vector with high probability is at the core of linear bandit algorithms, and our approach for designing a sparsity-agnostic algorithm is based on a result by Abbasi-Yadkori et al. [2] . They show how to construct a confidence set for OFUL [1] based on the predictions of a generic algorithm for online linear regression, a sequential decision-making setting defined as follows. For t = 1, . . . , T :1. The adversary privately chooses input A t ∈ R d and outcome X t ∈ R;2. The learner observes A t and chooses prediction X t ∈ R;3. The adversary reveals X t and the learner suffers loss ( X t -X t ) 2 . The learner's goal in online linear regression is to minimize the following notion of regret against anycomparator θ ∈ R d ρ T (θ) = T t=1 (X t -X t ) 2 - T t=1 (X t -⟨A t , θ⟩) 2 .The confidence set proposed by Abbasi-Yadkori et al. [2] where C T = 2 + log 2 log(e + T 1/2 ).Using the confidence set (2.2) with B set to SeqSEW, Abbasi-Yadkori et al. [2] achieved the minimax optimal regret bound of O( √ SdT ). However, to construct C t , the learner must know γ(δ), which depends on the unknown sparsity level S = ∥θ * ∥ 0 through B T .Algorithm 1 SparseLinUCB1: Input: T ∈ N, n ∈ N and q ∈ ∆ n := {(q 1 , . . . , q n ) ∈ [0, 1] n : n i=1 q i = 1} 2: Initialization: Let V 0 = I, θ 0 = (0, . . . , 0) 3: for t = 1, 2, . . . , T do 4:Receive action set A t and draw I t from distribution q 5: Choose actionA t = argmax a∈At ⟨a, θ t-1 ⟩ + ∥a∥ V -1 t-1 2 It log T 6:Receive reward X t 7:V t = V t-1 + A t A ⊤ t 8:Feed (A t , X t ) to SeqSEW and obtain prediction X tCompute regularized least squares estimate θ t = argminEQUATION10: end for 
a multi-level sparse linear bandit algorithm: 
 In this section, we introduce our main algorithm, SparseLinUCB, whose pseudo-code is shown in Algorithm 1. The algorithm, which runs SeqSEW as base algorithm B, uses a hierarchy of confidence sets of increasing radius. In each round t = 1, . . . , T , after receiving the action set A t , the algorithm draws the index I t of the confidence set for time t by sampling from the distributionq ∈ ∆ n := {(q 1 , . . . , q n ) ∈ [0, 1] n : n i=1 q i = 1}.Then the algorithm plays the action A t using the confidence setC It t := {θ ∈ R d : ∥θ -θ t-1 ∥ 2 Vt-1 ≤ 2 It log T } (where a larger I t implies a larger radius, and thus more exploration). Following the online to confidence set approach, upon receiving the reward X t , the algorithm feeds the pair (A t , X t ) to SeqSEW and uses the prediction X t to update the regularized least squares estimate θ t .Let α i = 2 i log T for all i ∈ N and set n ∈ N as n =     log 2 max θ∈R d :∥θ∥2≤1 γ(1/T, θ) log T     (3.1)where γ(δ, θ) is defined in Lemma 2.1 for B = SeqSEW.One can check that n = Θ(log d) (when ∥θ∥ 0 = d), which gives α n = Θ(d log T ). Our bounds depend on the following quantity, which defines the index of the smallest "safe" confidence set (i.e., the smallest i ∈[n] such that θ * ∈ C i t for all t ∈ [T ]), o := argmin i∈[n] γ(1/T ) ≤ α i (3.2)The choice of our confidence set (Line 4 in Algorithm 1) is justified by the following result, which implies that o is safe.Lemma 3.1. For C t defined in (2.2), we have that C t ⊆ C o t for all t ∈ [T ].As we use SeqSEW as base algorithm B, α o = O(S log T ). Our main result is an upper bound on the regret of SparseLinUCB. Theorem 3.2. The expected regret of SparseLinUCB run with the number of models n in (3.1) and a distribution q = {q s } s∈[n] satisfiesE[R T ] = O   (log T ) s≥o d2 s T q s + (log T ) ST d/Q   where Q = s≥o q s .If the sparsity level S is indeed known, then o 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 number of models n > o and the distribution {q s } s∈[n] with q o = 1, where o is set as in (3.2). Then, the expected regret ofSparseLinUCB is E[R T ] = O √ SdT log T .An instance-dependent bound. SparseLinUCB also enjoys an instance-dependent regret bound comparable to that of OFUL. Let ∆ be the minimum gap between the optimal arm and any suboptimal arms over all rounds, ∆ = minEQUATIONwhere A * t = max a∈At ⟨a, θ * ⟩ is the optimal arm for round t. Theorem 3.4. The expected regret of SparseLinUCB run with the number of models n in (3.1), a distribution q = {q s } s∈[n] and using SeqSEW as base algorithm satisfiesE[R T ] = O (dS/Q) + d 2 ∆ (log T ) 2where Q = s≥o q s .Sparsity-agnostic tuning of randomization. Next, we look at a specific choice of q. Fix C ≥ 1 and letEQUATIONwhere κ > 0 is chosen so to normalize the probabilities. It is easy to verify that for any C ≥ 1,s∈[n] 1 C 2 2 -s < 1 q s ≤ 1implying that κ can be chosen in [0, 1]. Combining Theorem 3.2 and 3.4, we obtain the following corollary providing a hybrid distribution-free and distribution-dependent bound. Corollary 3.5. Pick any C ≥ 1. Let the number of models n as in (3.1) and q = {q s } s∈[n] be chosen as in (3.4) . Then the expected regret of SparseLinUCB isE[R T ] = O min max C, S/C √ dT , max d 2 , S 2 d/C 2 ∆ For C = 1 the above bound is O(S √ dT ), which is tight up to the factor √ S due to the lower bound of Ω(SdT ) [17] . However, as mentioned in Lattimore and Szepesvári [17, Section 23.5], no algorithm can enjoy the regret of O( √ SdT ) simultaneously for all possible sparsity levels S. While our worst-case regret bound improves with a smaller S, the problem-dependent regret bound scales at least as (d 2 /∆) log T , which is independent of S. This raises an interesting question: could the problem-dependent bound also benefit from sparsity? Even with a very small probability p of choosing radius α n , the expected number of steps using α n would be pT . The results in [2] demonstrate that running the OFUL algorithm with α n over pT steps results in a regret of O(d 2 /∆). One simple way is to decrease the frequency of selecting radius α n . However, selecting α n less than d 2 /∆ 2 times may prevent the algorithm from obtaining a good enough estimate of θ * in certain settings. We note that by setting q o = 1 in Theorem 3.4, the regret bound becomes O(d 2 /∆). This result, as detailed in Theorem 3.4, arises from the parameter q n > 0. However, in this case, q n = 0, which allows us to achieve a more favorable regret bound.Algorithm 2 AdaLinUCB1: Input: T ∈ N, η > 0, q ∈ (0, 1] 2: Initialization: Let S i,0 = 0 for all i ∈ [n], V 0 = I, θ 0 = (0, . . . , 0) 3: for t = 1, 2, • • • , T do 4:Receive action set A t and draw a Bernoulli random variable Z t with P(Z t = 1) = q 5:if Z t = 1 then 6:Choose optimistic actionA t = argmax a∈At ⟨a, θ t-1 ⟩ + ∥a∥ V -1 t-1 2 n log T 7:Receive reward X t ; , the distribution from which the radius of the confidence set is drawn. It 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 a forced exploration term q and the learning rate η for Exp3. Similarly to 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 on the confidence set with the largest radius. With probability 1 -q, the algorithm instead draws the action based on Exp3. The distribution P t used by Exp3 at round t is based on exponential weights applied to the total estimated loss, denoted by S t (for technical reasons, we translate losses into rewards). The algorithm then draws I i from P t and selects the action A t based on the confidence set with radius 2 It log T . Finally, reward X t is observed and the pair (A t , X t ) is fed to SeqSEW. The prediction X t returned by SeqSEW is used to update the regularized least squares estimate θ t .The following theorem states the theoretical regret upper bound of AdaLinUCB. Theorem 4.1. If the random independent noise ε t in (2.1)satisfies ε t ∈ [-1, 1] for all t ∈ [T ],then the regret of AdaLinUCB run with η = (log n)/(T n) for n in (3.1) and q ∈ (0, 1] satisfiesE[R T ] ≤ 8α n q + 4 (2α o )/q dT log 1 + T L 2 d + 1 + O nT log n = O max dq, S/q √ dT .Although AdaLinUCB dynamically adjusts the distribution used by SparseLinUCB and may achieve better empirical performance, its regret bound is no better than that of SparseLinUCB. The issue is that the action chosen by AdaLinUCB in Line 10 does not ensure enough exploration to control the regret. Consequently, the algorithm needs to choose the optimistic action in Line 6 with constant probability q. SparseLinUCB has a 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 = {q s } s≥1 , whereas the parameter q does not provide a similar flexibility. 
model selection experiments: 
 In this section we describe some experiments we performed on synthetic data to verify whether AdaLinUCB could outperform OFUL in a 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 our model selection experiments are generated using targets θ * 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 [17, Section 23.5], we cannot implement the online to confidence set approach as described in [2] to capture sparsity. Instead, we run SparseLinUCB and AdaLinUCB with X t = X t for all t ∈ [T ], which-due to the form of our confidence sets-amounts to running the algorithms over multiple instances of OFUL with different choices of radiusα i for i ∈ [n].We run SparseLinUCB and AdaLinUCB with α i = α i,t = 2 i log t (a mildly time-dependent choice) for i = 0, 1, • • • , log 2 d. We also include α 0 = 0 corresponding to the greedy strategyA t = argmax a∈At ⟨a, θ t-1 ⟩. The suffix _Unif indicates {q s } s∈[n] set to ( 1 n , • • • , 1 n ).The suffix _Theory indicates q s = Θ(2 -s ) for s = 0, . . . , n as prescribed by (3.4) . Finally, we included SparseLinUCB_Known using q i = 1{i = o} 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 t = A for all t ∈ [T ], where |A| = 30 and A is a set of vectors drawn i.i.d. from the unit sphere in R 16 . The target vector θ * is a S-sparse (S = 1, 2, 4, 8, 16) vector whose non-zero coordinates are drawn from the unit sphere in R S . The noise ε t is drawn i.i.d. from the uniform distribution over [-1, 1]. Each curve is an average over 20 repetitions with T = 10 4 where, in each repetition, we draw fresh instances of A and θ * .As our implementations are not sparsity-aware, 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) is significantly affected by sparsity. The theory-driven choice of {q s } s∈[n] (SparseLinUCB_Theory) performs better than the uniform assignment (SparseLinUCB_Unif), and is in the same ballpark as OFUL. On the other hand, AdaLinUCB_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. 
limitations and open problems: 
 Unlike previous works, we prove sparsity-agnostic regret bounds with no assumptions on the action sets or on θ * (other than boundedness of ∥θ * ∥ and ∥a∥ for a ∈ A t , which are rather standard assumptions). For AdaLinUCB, however, we do require boundedness of the noise ε t (instead of just subgaussianity). We conjecture this requirement could be dropped at the expense of a further log T factor in the regret. Finally, for efficiency reasons our implementations are not designed to capture sparsity. Hence our experiments are limited to testing the impact of model selection.1. Proving a 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 O( √ SdT ) simultaneously for all sparsity levels S. However, we do not know whether the known lower bound Ω( √ SdT ) can be strengthened to Ω(S √ dT ) in the agnostic case.2. Our instance-dependent regret bound is of order O max{S 2 , d} d ∆ . It would be interesting to prove an upper bound that improves on the factor d 2 /∆, or a lower bound showing that d 2 /∆ cannot be improved on. 3. Our bound on the regret of AdaLinUCB looks pessimistic due to the presence of the constant exploration probability q. It would be interesting to prove a bound that more closely reflects the good empirical performance of this algorithm. [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. In Table 2 we list the most used notations. Next, we recall some definitions that are used throughout this appendix. We haveV t = I + t s=1 A s A ⊤ s and θ t = argmin θ∈R d ∥θ∥ 2 2 + t s=1 X s -⟨θ, A s ⟩ 2where A s ∈ A s is the action chosen by the learner at round t. Recall that α i = 2 i log T . For i ∈ [n],A i t = argmax a∈At max θ∈C i t ⟨θ, a⟩ = argmax a∈At ⟨a, θ t-1 ⟩ + ∥a∥ V -1 t-1 √ α iwhereC i t = θ ∈ R d : ∥θ -θ t-1 ∥ 2 Vt-1 ≤ α i .Finally, recall definition (2.2) with δ = 1/T ,C t = θ ∈ R d : ∥θ∥ 2 2 + t-1 s=1 ( X s -⟨A s , θ⟩) 2 ≤ γ(1/T ) . and recall that E = t∈[T ] {θ * ∈ C t }.Theorem 3.2. The expected regret of SparseLinUCB run with the number of models n in (3.1) and a distribution q = {q s } s∈[n] satisfiesE[R T ] = O   (log T ) s≥o d2 s T q s + (log T ) ST d/Q   where Q = s≥o q s . Proof. Lemma 3.1 implies C t ⊂ C o t . Hence, if E is true and s < o, then ⟨θ * , A s t ⟩ ≥ ⟨ θ t-1 , A s t ⟩ - √ α o ∥A s t ∥ V -1 t-1 (θ * ∈ C t ⊂ C o t ) = ⟨ θ t-1 , A s t ⟩ + √ α s ∥A s t ∥ V -1 t-1 -( √ α o + √ α s )∥A s t ∥ V -1 t-1 ≥ ⟨ θ t-1 , A o t ⟩ + √ α s ∥A o t ∥ V -1 t-1 -( √ α o + √ α s )∥A s t ∥ V -1 t-1 (maximality of A s t in C s t ) = ⟨ θ t-1 , A o t ⟩ + √ α o ∥A o t ∥ V -1 t-1 -( √ α o - √ α s )∥A o t ∥ V -1 t-1 -( √ α o + √ α s )∥A s t ∥ V -1 t-1 ≥ ⟨θ * , A o t ⟩ -( √ α o - √ α s )∥A o t ∥ V -1 t-1 -( √ α o + √ α s )∥A s t ∥ V -1 t-1 (θ * ∈ C t ⊂ C o t ) ≥ ⟨θ * , A o t ⟩ -( √ α o - √ α s )∥A o t ∥ V -1 t-1 -( √ α o + √ α s )∥A o t ∥ V -1 t-1(by Lemma D.3)= ⟨θ * , A o t ⟩ -2 √ α o ∥A o t ∥ V -1 t-1 ≥ ⟨θ * , A * t ⟩ -3 √ α o ∥A o t ∥ V -1 t-1 (B.1)where in the first and the third inequalities, we use the fact that for anyA ∈ R d , ⟨θ * -θ t-1 , A⟩ ≤ ∥θ * -θ t-1 ∥ Vt-1 ∥A∥ V -1 t-1 , (Cauchy-Schwarz inequality) ≤ √ α o ∥A∥ V -1 t-1 (due to θ * ∈ C o t )and for the last inequality,⟨θ * , A * t ⟩ ≤ ⟨ θ t-1 , A o t ⟩ + √ α 0 ∥A o t ∥ V -1 t-1 (θ * ∈ C o t , maximality of A o t .)We can decompose the regret as follows,R T = T t=1 1{E}⟨θ * , A * t -A It t ⟩ + T t=1 1{E c }⟨θ * , A * t -A It t ⟩ = T t=1 1{E c }⟨θ * , A * t -A It t ⟩ + T t=1 1{I t ≥ o, E}⟨θ * , A * t -A It t ⟩ + T t=1 1{I t < o, E}⟨θ * , A * t -A It t ⟩ ≤ T t=1 1{E c }⟨θ * , A * t -A It t ⟩ + T t=1 1{I t ≥ o, E}⟨θ * , A * t -A It t ⟩ + T t=1 1{I t < o, E} min 2, 3 √ α o ∥A o t ∥ V -1 t-1 ≤ T t=1 1{E c }⟨θ * , A * t -A It t ⟩ + T t=1 1{I t ≥ o, E}⟨θ * , A * t -A It t ⟩ ♠ + T t=1 2, 3 √ α o ∥A o t ∥ V -1 t-1 ♣ . (B.2) Since P(E c ) ≤ δ ≤ 1T , the first sum in the above line is easily bounded,T t=1 1{E c }⟨θ * , A * t -A It t ⟩ ≤ 2T P(E c ) ≤ 2 .Bounding term ♣. For each s ≥ 0, letT s = t ∈ [T ] : det(V t-1 ) ∈ 2 sd , 2 (s+1)d .Note that det(V t ) is monotone increasing w.r.t t. Define s ′ = ⌈log 2 det(V T )/d⌉. Then,[T ] = s ′ s=1 T s .Therefore,♣ ≤ s ′ s=1 t∈T s min 2, 3 √ α o ∥A o t ∥ V -1 t-1.By applying Lemma D.5, we obtainE[♣] = E   s ′ s=1 t∈T s min 2, 3 √ α o ∥A o t ∥ V -1 t-1   = 3 √ α o E   s ′ s=1 t∈T s min 1, ∥A o t ∥ V -1 t-1   (α o ≥ 1) ≤ 3 √ α o T • E s ′ s=1 t∈T s min 1, ∥A o t ∥ 2 V -1 t-1(Cauchy-Schwarz inequality)≤ 3 α o T s ′ s=1 (2d/Q + 1/Q) (due to Lemma D.5) ≤ 3 α o T (2d + 1)s ′ /Q = 3 α o T (2d + 1)/Q⌈log 2 det(V T )/d⌉ = O log T ST d/Q . Bounding term ♠. Let T s = T t=1 1{I t = s}. E[♠] = E T t=1 1{I t ≥ o, E}⟨θ * , A * t -A It t ⟩ ≤ E T t=1 1{I t ≥ o, E} • min 2, √ α It ∥A It t ∥ V -1 t-1 ≤ 2 s≥o E   α s T s t∈ [T ] 1{I t = s} min 1, ∥A s t ∥ 2 V -1 t-1   (Cauchy-Schwarz inequality) ≤ 2 s≥o E   α s T s t∈ [T ] min 1, ∥A t ∥ 2 V -1 t-1   ≤ 2 s≥o E α s T s 2 log det V T (Lemma D.1) ≤ 2 s≥o E α s T s • O( d log T ) (upper bound on det(V T )) ≤ 2 s≥o √ α s E [T s ] • O( d log T ) (Jensen's inequality) = O s≥o α s dT q s log T (because P(I t = s) = q s .)Substituting the bounds of ♠ and ♣ to (B.2), we haveE[R T ] ≤ O s≥o dα s T log T q s + log T SdT /Qconcluding the proof.Theorem 3.4. The expected regret of SparseLinUCB run with the number of models n in (3.1), a distribution q = {q s } s∈[n] and using SeqSEW as base algorithm satisfiesE[R T ] = O (dS/Q) + d 2 ∆ (log T ) 2where Q = s≥o q s .Proof.R T = T t=1 1{E}⟨θ * , A * t -A It t ⟩ + T t=1 1{E c }⟨θ * , A * t -A It t ⟩ ≤ T t=1 1{E c }⟨θ * , A * t -A It t ⟩ + T t=1 1{I t ≥ o, E} ⟨θ * , A * t -A It t ⟩ 2 ∆ + T t=1 1{I t < o, E} ⟨θ * , A * t -A It t ⟩ 2 ∆ (minimality of ∆) ≤ T t=1 1{E c }⟨θ * , A * t -A It t ⟩ + T t=1 1{I t ≥ o, E} ⟨θ * , A * t -A It t ⟩ 2 ∆ ♠ + 9 T t=1 1{I t < o, E} min 1, α o ∥A o t ∥ 2 V -1 t-1 ∆ ♣ (by applying (B.1) to ♣)Bounding term ♣. Let s ′ = ⌈log 2 det(V T )/d⌉. By applying Lemma D.5, we obtainE[♣] ≤ 9 ∆ E   s≥0 t∈T s min 1, α o ∥A o t ∥ 2 V -1 t-1   ≤ 9α o ∆ s ′ s=1 E t∈T s min 1, ∥A o t ∥ 2 V -1 t-1 (α o ≥ 1) ≤ 9α o ∆ s ′ s=1 (2d/Q + 1/Q) (due to Lemma D.5) ≤ 27α o ds ′ /Q ∆ = O dS(log T ) 2 /Q ∆ (because s ′ = O(log T ).)Bounding term ♠.E[♠] = E T t=1 1{I t ≥ o, E} ⟨θ * , A * t -A It t ⟩ 2 ∆ ≤ 4 ∆ E T t=1 1{I t ≥ o, E} • min 1, α It ∥A It t ∥ 2 V -1 t-1 ≤ 4 s≥o α s ∆ E   t∈ [T ] min 1, ∥A t ∥ 2 V -1 t-1   ≤ 8 s≥o α s ∆ • log det V T (due to Lemma D.1) = O d 2 (log T ) 2 ∆ (B.3)where the first inequality comes from⟨θ * , A * t -A It t ⟩ ≤ max θ∈C I t t-1 ⟨θ -θ * , A It t ⟩ ≤ max θ∈C I t t-1 ∥θ -θ * ∥ Vt-1 ∥A It t ∥ V -1 t-1 (Cauchy-Schwarz Inequality) ≤ 2 √ α It ∥A It t ∥ V -1 t-1where the last inequality holds because E and I t ≥ o both hold, and so θ * ∈ C t-1 ⊂ C It t-1 due to Lemma 3.1. The factor 2 is due to an application of the triangular inequality. Substituting the bounds of ♠ and ♣ in (B.2), we haveE[R T ] = O max{S/Q, d} • d(log T ) 2 ∆ .Corollary B.1. Pick any C ≥ 1 and let {q s } s∈[n] be chosen as in (3.4) . Then the expected regret of SparseLinUCB isE[R T ] = O min max C, S/C √ dT , max d 2 , S 2 d/C 2 ∆Proof. We consider the following cases based on the value of C.Case 1: C 2 < 2 o . q o = C 2 • 2 -o . According to Theorem 3.2, E[R T ] = O   (log T ) s≥o d2 s T q s + (log T ) ST d/Q   ≤ O (log T )n d2 o T q o + (log T ) ST d/q o = O max{C, S/C} √ dT .(due to n = O(log d) and 2 o = Θ(S log T ))Besides, according to Theorem 3.4,E[R T ] = O max{S/Q, d} • d log 2 T ∆ = O max{S/q o , d} • d log 2 T ∆ = O max{d 2 , S 2 d/C 2 } ∆ .Therefore,E[R T ] = O min max C, S/C √ dT , max d 2 , S 2 d/C 2 ∆ . Case 2: C 2 ∈ [2 o , 2 n ). For s with C 2 < 2 s , q s = C 2 2 -s . Let o ′ = arg min s>o {C 2 < 2 s }. Then, q o ′ ≥ 1/4. According to Theorem 3.2, E[R T ] = O   (log T ) s≥o d2 s T q s + (log T ) ST d/Q   ≤ O   (log T ) s∈[o,o ′ ) √ d2 s T + (log T ) s∈[o ′ ,n] d2 s T q s + (log T ) ST d/q o ′   ≤ O √ d2 o ′ T + nC √ dT + √ ST d = O max{C, S/C} √ dT . (due to C 2 = Θ(2 o ′ ) and 2 o ′ ≥ 2 o ≥ S)Besides, according to Theorem 3.4,E[R T ] = O max{S/Q, d} • d(log T ) 2 ∆ = O max{S/q o ′ , d} • d(log T ) 2 ∆ = O max{d 2 , S 2 d/C 2 } ∆ .Therefore,E[R T ] = O min max C, S/C √ dT , max d 2 , S 2 d/C 2 ∆ . Case C 2 ≥ 2 n : q s = 1/n for all s ∈ [n]. It is easy to verify that E[R T ] = O(d √ T ) and E[R T ] = O(d 2 /∆). Thus, E[R T ] = O min max C, S/C √ dT , max d 2 , S 2 d/C 2 ∆ .Corollary B.2. Assume that the sparsity level S is known and choose a distribution q = {q s } s∈ [n] with q o = 1, where o is set as in (3.2). Then, the expected regret of SparseLinUCB isE[R T ] = O 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 haveE[♠] = E T t=1 1{I t ≥ o, E} ⟨θ * , A * t -A It t ⟩ 2 ∆ = E T t=1 1{E} ⟨θ * , A * t -A t ⟩ 2 ∆ ≤ 4α o ∆ E   t∈ [T ] min 1, ∥A t ∥ 2 V -1 t-1   = O Sd(log T ) 2 ∆ (B.4)where the second equality is because q o = 1 and soA It t = A o t = A t ,* , A * t -A t ⟩ ≤ max θ∈C o t-1 ⟨θ -θ * , A t ⟩ ≤ max θ∈C o t-1 ∥θ -θ * ∥ Vt-1 ∥A o t ∥ V -1 t-1 (Cauchy-Schwarz Inequality) ≤ 2 √ α o ∥A t ∥ V -1 t-1where the last inequality holds because E and I t = o both hold, and so θ * ∈ C t-1 ⊂ C o t-1 due to Lemma 3.1. Substituting the bounds of ♠ and ♣ in (B.2), we haveE[R T ] = O Sd(log T ) 2 ∆ .Theorem 4.1. If the random independent noise ε t in (2.1) satisfies ε t ∈ [-1, 1] for all t ∈ [T ], then regret of AdaLinUCB run with η = (log n)/(T n) for n in (3.1) and q ∈ (0, 1] satisfiesE[R T ] ≤ 8α n q + 4 (2α o )/q dT log 1 + T L 2 d + 1 + O nT log n = O max dq, S/q √ dT .Proof. Let T 1 be the set of time steps where Z t = 1 in Line 4 of AdaLinUCB and letT 2 = [T ] \ T 1 .For all t ∈ T 2 the action A t ∈ A t is chosen by Exp3 through an adversarial mapping µ t : [n] → A t defined in Lines 9-10. The resulting rewardX t ∈ [-2, 2] is fed to Exp3 as a [0, 1]-valued loss ℓ t (I t ) = (2 -X t )/4, where µ t (I t ) = A t . Since T 2 is selected through independent coin tosses with fixed bias q, we can apply the Exp3 regret analysis (for losses chosen by a non-oblivious adversary) to bound the regret in T 2 and show that t∈T2⟨A o t -A t , θ * ⟩ = 4 t∈T2 ℓ t (I t ) -ℓ t (o) = O n log n (C.1)where we used µ t (o) = A o t for all t ∈ [T ]. We haveR T2 = t∈T2 argmax a∈At ⟨a -A t , θ * ⟩ = t∈T2 argmax a∈At ⟨a -A o t + A o t -A t , θ * ⟩ = t∈T2 argmax a∈At ⟨a -A o t , θ * ⟩ Reg Img + t∈T2 ⟨A o t -A t , θ * ⟩ Reg Exp3. Reg⟨θ * , A * t -A o t ⟩ ≤ ⟨ θ o t -θ * , A o t ⟩ (because θ * ∈ C t ⊆ C o t ) ≤ ∥ θ o t -θ * ∥ Vt-1 ∥A o t ∥ V -1 t-1 (Cauchy-Schwarz inequality) ≤ √ α o ∥A o t ∥ V -1 t-1 , (C.3)where the last inequality is because θ o t ∈ C o t . Then, assuming E holds, we can bound Reg Img asReg Img = t∈T2 ⟨θ * , A * t -A o t ⟩ ≤ t∈T2 min 2, √ α o ∥A o t ∥ V -1 t-1 ≤ t∈T2 min 2, 2γ(1/T )∥A o t ∥ V -1 t-1 (due to α o ≤ 2γ(1/T )) ≤ 2 γ(1/T ) t∈T2 min 1, ∥A o t ∥ V -1 t-1 , (C.4)where in the first inequality, we use the facts ⟨θ * , A *t -A o t ⟩ ≤ √ α o ∥A o t ∥ V -1 t-1 and ⟨θ * , A * t -A o t ⟩ ≤ ⟨θ * , A * t ⟩ ≤ 2. From Lemma D.3, we have t∈T2 min 1, ∥A o t ∥ 2 V -1 t-1 ≤ t∈T2 min 1, ∥A n t ∥ 2 V -1 t-1 .For each s ≥ 0, letT s 2 = t ∈ T 2 : det(V t-1 ) ∈ 2 ds , 2 d(s+1)so thatT 2 = s≥0 T s 2 .Let s ′ = ⌈log 2 det(V T )/d⌉. We haveE Reg Img • 1[E] ≤ E 2 γ(1/T ) t∈T2 min 1, ∥A o t ∥ V -1 t-1 (due to (C.4)) ≤ 2 √ 2α o E t∈T2 min 1, ∥A o t ∥ V -1 t-1 (due to α 0 ≤ 2γ(1/T )) ≤ 2 2α o T E t∈T2 min 1, ∥A o t ∥ 2 V -1 t-1 (Cauchy-Schwarz inequality) ≤ 2 2α o T s ′ s=1 E t∈T s 2 min 1, ∥A o t ∥ 2 V -1 t-1(where d ln s ′ ≤ log det(V T ))≤ 2 2α o T s ′ s=1 E t∈T s 2 min 1, ∥A n t ∥ 2 V -1 t-1 (because ∥A n t ∥ V -1 t-1 ≥ ∥A o t ∥ V -1 t-1 ) ≤ 2 2α o T s ′ s=1 (2d + 1)/q (due to Lemma D.4) ≤ 2 2(2d + 1)α o T s ′ /q .To obtain the final results, we haveEQUATIONwhereλ 1 , • • • , λ d are the eigenvalues of V T . Therefore, we have s ′ ≤ ⌈log 2 (1 + T L 2 /d)⌉. E Reg Img • 1[E] ≤ 2 2(2d + 1)α o T /q • √ s ′ ≤ 2 (6dα o T /q)⌈log 2 (1 + T L 2 /d)⌉.By substituting the bounds on Reg Img and Reg Exp3 into R T2 , we obtainE[R T2 ] = E[Reg Exp3 1{E}] + E[Reg Img ] + T • P(E c ) ≤ 2 6dα o T /q ⌈log(1 + T L 2 /d)⌉ + O( nT log n),where the last inequality is because P(E c ) ≤ 1/T from Lemma 2.1 with our choice of δ = 1/δ.Finally, we bound R T1 . Conditioned on event E and using(D.3), ∀t ∈ [T ], θ * ∈ C t ⊆ C 0 t ⊆ C n t . Hence, we can obtain ⟨θ * , A * t -A n t ⟩ ≤ ⟨ θ n t -θ * , A n t ⟩ (because θ * ∈ C t ⊆ C n t ) ≤ ∥ θ n t -θ * ∥ Vt-1 ∥A n t ∥ V -1 t-1 (Cauchy-Schwarz inequality) ≤ √ α n ∥A n t ∥ V -1 t-1 (because θ n t ∈ C n t .)Hence, conditioned on event E,EQUATIONwhere the last inequality is due to Lemma D.1. Therefore, the expected regret for t ∈ T 1 isE[R T1 ] ≤ E[R T1 1{E}] + T • P(E c ) ≤ E 2 α n |T 1 | • 2 log(det(V T )) + 1 ≤ E 2 α n |T 1 | • 2d log 1 + T L 2 d + 1 = 2 √ α n E |T 1 | • 2d log 1 + T L 2 d + 1 ≤ 2 α n T q • 2d log 1 + T L 2 d + 1, (Jensen's inequality)where the first inequality is due to (C.7) and P(E c ) ≤ 1/T from Lemma 2.1 and the last inequality is due to the fact that for any t ∈ [T ], with probability q, t ∈ T 1 . Finally, we obtainE[R T ] = E[R T1 ] + E[R T2 ] ≤ 2 α n T q • 2d log 1 + T L 2 d + 2 6dα o T /q ⌈log(1 + T L 2 /d)⌉ + O( nT log n).Note that n = Θ(log d) and α o = Θ(S log T ). We obtainE[R T ] = O max qd, S q • √ dT • log T ,which completes the proof.Lemma D.1 (Dani et al. [10] ).Let A 1 , A 2 , . . . , A T ∈ R d and V t = I + t s=1 A s A ⊤ s for all t ∈ [T ]. Then T t=1 min 1, ∥A t ∥ 2 V -1 t-1 ≤ 2 log det(V T ). (D.1) Moreover, min 1, ∥A t ∥ 2 V -1 t-1 ≤ 2 log 1 + ∥A t ∥ 2 V -1 t-1 = 2 log det(V t ) det(V t-1 ) . Lemma D.2. For C t defined in (2.2), we have that C t ⊆ C o t for all t ∈ [T ].Proof. RecallC t+1 = θ : ∥θ∥ 2 2 + t s=1 X s -⟨θ, A s ⟩ 2 ≤ γ(1/T ) .Note that∥θ∥ 2 2 + t s=1 X s -⟨θ, A s ⟩ 2 -∥ θ t ∥ 2 2 - t s=1 X s -⟨ θ t , A s ⟩ 2 = ∥θ∥ 2 2 -2θ ⊤ t s=1 X s A s + θ ⊤ t s=1 A s A ⊤ s θ -∥ θ t ∥ 2 2 + 2 θ ⊤ t t s=1 X s A s -θ ⊤ t t s=1 A s A ⊤ s θ t = ∥θ∥ 2 Vt + 2( θ t -θ) ⊤ V t θ t -∥ θ t ∥ 2 Vt (V t = I + t s=1 A s A ⊤ s , θ t = V -1 t t s=1 A s X s ) = ∥θ∥ 2 Vt -2θ ⊤ V t θ t + ∥ θ t ∥ 2 Vt = ∥θ -θ t ∥ 2Vt . Hence, we can express the ellipsoid asC t+1 = ∥θ -θ t ∥ 2 Vt + ∥ θ t ∥ 2 2 + t s=1 X s -⟨ θ t , A s ⟩ 2 ≤ γ(1/T ) . (D.2)Therefore, for all t ≥ 0,C t+1 = θ : ∥θ -θ t ∥ 2 Vt + ∥ θ t ∥ 2 2 + t s=1 X s -⟨ θ t , A s ⟩ 2 ≤ γ(1/T ) (due to (D.2)) ⊆ θ : ∥θ -θ t ∥ 2 Vt ≤ γ(1/T ) ⊆ θ : ∥θ -θ t ∥ 2 Vt ≤ α o (by definition of α 0 ) = C o t+1 (D.3)concluding the proof.Lemma D.3. For any 1 ≤ p ≤ q ≤ n and t ∈ [T ],∥A p t ∥ V -1 t-1 ≤ ∥A q t ∥ V -1 t-1 .Proof. Note thatA p t = argmax a∈At max θ∈C p t ⟨θ, a⟩ = argmax a∈At ⟨a, θ t-1 ⟩ + √ α p ∥a∥ V -1 t-1 , A q t = argmax a∈At max θ∈C q t ⟨θ, a⟩ = argmax a∈At ⟨a, θ t-1 ⟩ + √ α q ∥a∥ V -1 t-1.For contradiction, we assume∥A q t ∥ V -1 t-1 < ∥A p t ∥ V -1 t-1 . Since ∥A q t ∥ V -1 t-1 < ∥A p t ∥ V -1 t-1 , ∥A q t ∥ V -1 t-1 ̸ = ∥A p t ∥ V -1 t-1. Besides, according to the definition of A p t and A q t , we have⟨A q t , θ t-1 ⟩ + √ α p ∥A q t ∥ V -1 t-1 ≤ ⟨A p t , θ t-1 ⟩ + √ α p ∥A p t ∥ V -1 t-1 (D.4) < ⟨A p t , θ t-1 ⟩ + √ α q ∥A p t ∥ V -1 t-1 (D.5) ≤ ⟨A q t , θ t-1 ⟩ + √ α q ∥A q t ∥ V -1 t-1 , (D.6)where the first inequality is due to the definition of A p t , the second inequality is due to√ α p < √ α q ,and the last inequality is due to the definition of A q t . From the above results, we further have⟨A q t -A p t , θ t-1 ⟩ ≤ √ α p ∥A p t ∥ V -1 t-1 -∥A q t ∥ V -1 t-1 (Due to (D.4)) < √ α q ∥A p t ∥ V -1 t-1 -∥A q t ∥ V -1 t-1 (Due to assumption ∥A q t ∥ V -1 t-1 < ∥A p t ∥ V -1 t-1and α q > α p )≤ ⟨A q t -A p t , θ t-1 ⟩. (Due to (D.6).)We obtain a contradiction. Therefore,∥A q t ∥ V -1 t-1 ≥ ∥A p t ∥ V -1 t-1 . (D.7) Lemma D.4. E   t∈T s 2 min 1, ∥A n t ∥ 2 V -1 t-1   ≤ 2d/q + 1/q.Proof. Let det(V t-1 ) = (q t-1 ) d and det(V t-1 + A n t (A n t ) ⊤ ) = (q t-1 + x t ) d . For each s ≥ 0, letT s = t ∈ [T ] : det(V t-1 ) ∈ 2 sd , 2 d(s+1) .Since T s 2 ⊆ T s , to showE t∈T s 2 min 1, ∥A n t ∥ 2 V -1 t-1 ≤ 2d/q + 1/q,we only need to proveE t∈T s min 1, ∥A n t ∥ 2 V -1 t-1 ≤ 2d/q + 1/q.We let I t = 1 if the coin tosses in the t's round is Head and 0 otherwise. We divide T s into two disjoint parts T s and T s . Specifically,• for T s , it holds that for t ∈ T s , det(V t-1 + A n t (A n t ) ⊤ ) ≤ 2 d(s+1) . • for T s , it holds that for t ∈ T s , det(V t-1 + A n t (A n t ) ⊤ ) > 2 d(s+1) .From definition of T s and the fact that ifI t = 1, V t = V t-1 + A n t (A n t ) ⊤ , we have t∈T s x t • I t ≤ 2 s .From Algorithm 2, with probability q, I t = 1. Therefore, if we let {F t } t∈[T ] be the natural filtration of {A t , I t , X t } t∈[T ] , we have2 s ≥ E   t∈T s x t • I t   = E   t∈[T ] x t • I t • 1{t ∈ T s }   = t∈[T ] E [x t • I t • 1{t ∈ T s }] = t∈[T ] E [E [x t • I t • 1{t ∈ T s }|F t-1 ]] (Law of total expectation) = t∈[T ] E [x t • 1{t ∈ T s } • E [I t |F t-1 ]] (x t and 1{t ∈ T s } are F t-1 -measurable) = t∈[T ] E [x t • 1{t ∈ T s } • q] (I t is an independent coin-tossing) = qE   t∈T s x t  and therefore E t∈T s x t ≤ 2 s /q. For t ∈ T s , we further havemin 1, ∥A n t ∥ 2 V -1 t-1 ≤ 2 log det(V t-1 + A n t (A n t ) ⊤ ) det(V t-1 )(due to Lemma D.1)= 2d log 1 + x t q t-1 ≤ 2d log 1 + x t 2 s (since t ∈ T s , q t-1 ≥ 2 s ) ≤ 2d • x t 2 s (due to log(1 + x) ≤ x for x > 0.)Therefore,E t∈T s min 1, ∥A n t ∥ 2 V -1 t-1 ≤ E t∈T s 2d • x t 2 s = 2d 2 s E t∈T s x t ≤ 2d/q.From definition of T s , if I t = 1 and t ∈ T s , det(V t ) > 2 d(s+1) . Then, for all τ > t, τ / ∈ T s . Therefore, there is at most one t ∈ T s with I t = 1. We obtainE t∈T s min 1, ∥A n t ∥ 2 V -1 t-1 ≤ E T s ≤ 1/q,where the last inequality is because with probability q, I t = 1. By combining the bounds for t ∈ T s and t ∈ T s together, lemma follows.Lemma D.5. Let Q = s≥o q s . Then,E t∈T s min 1, ∥A o t ∥ 2 V -1 t-1 ≤ 2d/Q + 1/Q. Proof. Let det(V t-1 ) = (q t-1 ) d . Let x t satisfies det(V t-1 + A o t (A o t ) ⊤ ) = (q t-1 + x t ) d .We let I t = 1{I t ≥ o}. We divide T s into two disjoint parts T s and T s . Specifically, • for T s , it holds that for t ∈ T s , det(V t-1 + A o t (A o t ) ⊤ ) ≤ 2 d(s+1) .• for T s , it holds that for t ∈ T s , det(V t-1 + A o t (A o t ) ⊤ ) > 2 d(s+1) .Note that forI t ≥ o, log(det(V t )) -log(det(V t-1 + A o t (A o t ) ⊤ )) = log(det(V t )) -log(V t-1 ) -log(det(V t-1 + A o t (A o t ) ⊤ )) -log(V t-1 ) (due to Lemma D.1) = log(1 + ∥A It t ∥ V -1 t-1 ) -log(1 + ∥A o t ∥ V -1 t-1 ) ≥0. (due to Lemma D.3) Therefore, if we let det(V t-1 + A It t (A It t ) ⊤ ) = (q t-1 + x ′ t ) d and I t ≥ o, then x ′ t ≥ x t . Hence, t∈T s x t • I t ≤ 2 s . Note that P(I t ≥ o) = s≥o q s = Q. Let {F t } t∈[T ] be the natural filtration of {A t , I t , X t } t∈[T ] .We have2 s ≥ E   t∈T s x t • I t   = E   t∈[T ] x t • I t • 1{t ∈ T s }   = t∈[T ] E [x t • I t • 1{t ∈ T s }] = t∈[T ] E [E [x t • I t • 1{t ∈ T s }|F t-1 ]] (Law of total expectation) = t∈[T ] E [x t • 1{t ∈ T s } • E [I t |F t-1 ]] (x t and 1{t ∈ T s } are F t-1 -measurable) = t∈[T ] E [x t • 1{t ∈ T s } • Q] (I t is an independent coin-tossing) = QE   t∈T s x t  and thereforeE   t∈T s x t   ≤ 2 s /Q.For t ∈ T s , we further havemin 1, ∥A o t ∥ 2 V -1 t-1 ≤ min 1, ∥A It t ∥ 2 V -1 t-1 ≤ 2 log det(V t-1 + A It t (A It t ) ⊤ ) det(V t-1 )(due to Lemma D.1)= 2d log 1 + x t q t-1 ≤ 2d log 1 + x t 2 s (since t ∈ T s , q t-1 ≥ 2 s ) ≤ 2d • x t 2 s (due to log(1 + x) ≤ x for x > 0.)Therefore,E t∈T s min 1, ∥A o t ∥ 2 V -1 t-1 ≤ E t∈T s 2d • x t 2 s = 2d 2 s E t∈T s x t ≤ 2d/Q.From definition of T s , if I t = 1 and t ∈ T s , then I t ≥ o anddet(V t ) = det(V n-1 + A It t (A It t ) ⊤ ) > det(V n-1 + A o t (A o t ) ⊤ ) > (s + 1) d .Then, for all τ > t, τ / ∈ T s . Therefore, there is at most one t ∈ T s with I t = 1. We obtainE t∈T s min 1, ∥A o t ∥ 2 V -1 t-1 ≤ E T s ≤ 1/Q,where the last inequality is because with probability s≥o q s = Q, I t = 1. By combining the bounds for t ∈ T s and t ∈ T s together, lemma follows.The code used in the experiments can be found in the following repository: https://github.com/ jajajang/sparsity_agnostic_model_selection. • Radius of confidence sets: α 0 = 0, and α i = 2 i log t for i = 1, • • • , 5.• Prior distribution {q s } s∈ [6] -For _Unif,{q s } s∈[6] = • Since we empirically observed that Exp3 provided enough exploration, we aggressively set the forced exploration parameter q to zero.• The learning rate of Exp3 was set to η t = 2 log n nt , see [5] . • Given the prior distribution {q s } s∈ [6] , we set P t as follows: P t,s = q s exp (η t S t,s ) n j=1 q j exp (η t S t,j )• We used the log-determinant form of the confidence set based on Abbasi-Yadkori et al. [ • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, 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 to a 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, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: We reported 1-sigma error bars in 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, confidence intervals, or statistical significance tests, at 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 run with given experimental conditions).• 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). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration 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 societal 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses 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 not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The paper misses many very related works, especially those on K-armed bandits and linear bandits.

2. 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?

3. The writing is unclear. 

(1) In Line 176,  "the distribution $\\{q_i\\} _ {i \in [n]}$" is not well defined, over what? 

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

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

(4) Line 240: in terms of what?

4. 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?
questions: questions: See Weaknesses
limitations: limitations: The authors have addressed the limitations and societal impact.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 

2. 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.
questions: questions: 1. Why is the boundness of the random noise necessary in your theoretical proof?
2. 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.
3. Can you report the running time of your method in the experiments?
limitations: limitations: No negative societal impact.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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$.
questions: 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?
- (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?
- 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.

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

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

- 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.
questions: questions: Can authors provide another distribution selection case which can recover dS/Delta instance-dependent bound in known sparsity and adaptive adversary setup?
limitations: limitations: Yes

Comments: title: Official Comment by Reviewer 9XZb
comment: Thank you for reviewing our response and for your support. If you have any further questions about our submission, please don't hesitate to reach out.
Thank you for reviewing our response and for your support. If you have any further questions regarding our submission, please feel free to reach out.
Thank you for reviewing our response and for the improved score. We will incorporate your valuable suggestions and make the necessary changes in the revised version of the paper. If you have any further questions about our submission, please don't hesitate to reach out.
Thank you for the detailed explanation. I have no further questions. I have kept my rating, as my original score was already positive and supportive of accepting the paper!
Thanks for your detailed responses, which do solve most of my concerns. I have increased my scores to reflect this. However, I suggest polishing the writing to help with understanding. Good luck!
Thanks for your response. I don't have further questions and will keep my score as is.
Thank you for your feedback. If you have any further questions about our submission, please do not hesitate to reach out. We highly value your perspective, and should you find our responses satisfactory, we would be grateful if you would consider raising your score for our paper.
Thank you for your responses. I have no more questions.