Variance-Aware Sparse Linear Bandits
Authors: Yan Dai
Ruosong Wang
Simon Shaolei Du
Venue: ICLR 2023 poster (2023)

Abstract: It is well-known that for sparse linear bandits, when ignoring the dependency on sparsity which is much smaller than the ambient dimension, the worst-case minimax regret is $\widetilde{\Theta}\left(\sqrt{dT}\right)$ where $d$ is the ambient dimension and $T$ is the number of rounds. On the other hand, in the benign setting where there is no noise and the action set is the unit sphere, one can use divide-and-conquer to achieve $\widetilde{\mathcal O}(1)$ regret, which is (nearly) independent of $d$ and $T$. In this paper, we present the first variance-aware regret guarantee for sparse linear bandits:  $\widetilde{\mathcal O}\left(\sqrt{d\sum_{t=1}^T \sigma_t^2} + 1\right)$, where $\sigma_t^2$ is the variance of the noise at the $t$-th round. This bound naturally interpolates the regret bounds for the worst-case constant-variance regime (i.e., $\sigma_t \equiv \Omega(1)$) and the benign deterministic regimes (i.e., $\sigma_t \equiv 0$). To achieve this variance-aware regret guarantee, we develop a general framework that converts any variance-aware linear bandit algorithm to a variance-aware algorithm for sparse linear bandits in a "black-box" manner. Specifically, we take two recent algorithms as black boxes to illustrate that the claimed bounds indeed hold, where the first algorithm can handle unknown-variance cases and the second one is more efficient.

Published as a conference paper at ICLR 2023
VARIANCE-AWARE SPARSE LINEAR BANDITS
Yan Dai
MM., Tsinghua University
yan-dai20@mailn is. wew.ttsingghu wtt.allssssssnnnedi...... edu.con
Ruosong Wang
Simon S. Du
University of Washington
University of Washington
ruosongwecs washington.cm edu
ssdu@cs. wwshington.cc. edu
ABSTRACT
It is well-known that for sparse linear bandits, when ignoring the dependency sparsity which is much smaller than the ambient dimension, the worst-case minimax regret is θ VdTT) where d is the ambient dimension and 7 is the number rounds. On the other hand, in the benign setting where there is no noise and the action set is the unit sphere, one can use aoviee-and-conueer to achieve (1)) regret, which is (nearly) independent of d and T. In this paper, present the first
variance- variance-wware regret guarantee for sparse linear bandits: Ö (V
where of is the variance of the noise at the f-th round. This bound naturally interpolates the regret bounds for the worst-case constant-variance regime (i.e., ((1) and the benign deterministic regimes (i.e., 0, = 0). To achieve this variance-aware regret guarantee, we develop general framework that converts any variance-aware linear bandit algorithm to a variance-aware algorithm for sparse linear bandits in a "black-box manner. Specifically, we take two recent algorithms black boxes illustrate that the claimed bounds indeed hold, where the first algorithm can handle unknown-varianee cases and the second one is more efficient.
INTRODUCTION
This paper studies the sparse linear stochastic bandit problem, which special case of linear stochastic bandits. In linear bandits (Dani et al., 2008), the agent is facing a sequential decision- making problem lasting for T rounds. For the 1-th round, the agent chooses an action It E C Rd. where X' is an action set, and receives noisy reward r, (0" =x.) + where 0* E X is the (hidden) parameter of the game and 77 is random zero-mean noise. The goal of the agent to minimize her regret Ry, that is, the difference between her cumulative reward Σ (0", and maxxex 20=1(0", (check Eq. (1) for definition). Dani et al. (2008) proved that the minimax optimal regret for linear bandits (dv/T) when the noises are independent Gaussian random variables with means () and variances 1 and both 6* and the actions z, lie in the unit sphere in Rd
In real-world applications such as recommendation systems, only a few features may be relevant despite large candidate feature space. In other words, the high-dimensional linear regime may actually allow now-dimensional structure. As result, if we still use the linear bandit model, we will always suffer ((dVT) regret no matter how many features are useful. Motivated by this, the sparse linear stochastic bandit problem introduced (Abbasi-Yadkori Yadkori al., 2012; Carpentier & Munos, 2012). This problem has an additional constraint that the hidden parameter, 8*, is sparse, i... | llo < for some d. However, the agent has no prior knowledge about s and thus the interaction protocol is exactly the same as that of linear bandits. The minimax optimal regret for
'Throughout the paper, will use the notations (-)) and (-) to hide log T. log d, log (where is the sparsity parameter, which will be introduced later) and log log & factors (where & is the failure probability).

---

Published as a conference paper at ICLR 2023
sparse linear bandits is e( sdTT (Abbasi- Yadkori et al., 2012; Antos & Szepesvári, 2009). This bound bypasses the S2dv VT) lower bound for linear bandits as always have ||0" llo S d and the agent does not have access to either (though a few previous works assumed a known s).
However, both the (dv and the O(vsdT bounds are the worst-case regret bounds and sometime are too pessimistic especially when large. On the other hand, many problems with delicate structures permit a regret bound much smaller than the worst-case bound. The structure this paper focuses on is the magnitude of the noise. Consider the following motivating example.
Motivating Example (Deterministic Sparse Linear Bandits). Consider the case where the action set is the unit sphere X' gd-1, and there is no noise, i.e., the feedback r. (6", 24, for each round & E [T]. In this case, one can identify all non-zero entries of 0" coordinates in O(s log d) steps with high probability via a divide-and-conquee algorithm, and thus yield a dimension-free regret ((s) (see Appendix C for more details about this). However, this divide-and- divide-and-conquer algorithm is specific for deterministic sparse linear bandit problems and does not work for noisy models. Henceforth, we study the following natural question:
Can we design an algorithm whose regret adapts the noise level such that the regret interpolates the VdT-type bound in the worst case and the dimension-free bound in the deterministic case?
Before introducing our results, we would like to mention that there are recent works that studied the noise-adaptivity in linear bandits (Zhou et al., 2021; Zhang et al., 2021; Kim et al., 2021). They
gave variance-awars regret bounds of the form Ö poly(d) Ei= of poly(d) where of is the
(conditional) variance of the noise ?)- This bound reduces to the standard ((poly(d)VT) bound in the worst-case when Ø; [2(1), and to constant-type regret (plol((d) that is independent of T. However, compared with the linear bandits setting, the variance-aware bound for sparse linear bandits is more significant because it reduces to dimension-free bound in the noiseless setting. Despite this, to our knowledge, no variance-aware regret bounds exist for sparse linear bandits.
1.1 OUR CONTRIBUTIONS
This paper gives the first set of variance-aware regret bounds for sparse linear bandits. We design general framework, VASLB, to reduce variance-aware sparse linear bandits to variance-aware linear bandits with little overhead in regret. For ease of presentation, characterize the Definition variance-awee aware sparse linear bandit algorithm F is (f(s, g(s, d) vvrriance aware, for any given failure probability 8 > O, with probability 1 5, F ensures
define the following notation to of a sparse linear bandit algorithm:
T
R SO [(6.d)
Σ
of polylog 5 + *s(s polylog
where RS is the regret of F in T rounds, d is the ambient dimension and 8 is the maximum number of non-zero coordinates. Specifically, for linear bandits, f.9 are functions only of d.
Hence, an v varrianccccee algorithm will achieve Ö(f(s, d) d polylog }t) worst-case regret and Ögg(s, d) polylog 1/) deterministic-cas. regret. Ideally, we would like g(s, d) being independent of d, making the bound dimension-free in deterministic cases, as the divvid-andd-oooge
approach.
In this paper, we provide a general framework that can convert any linear bandit algorithm F to a corresponding sparse linear bandit algorithm G in a black-box manner. Moreover, it is variance- aware-preserving, in the sense that, if F enjoys the variance-aware property, so does G. Generally
"Carpentier & Munos (2012) and Latuimore et al. (2015) obtained an O(svT) T') regret bound under different models. The former assumed component wise noise model. while the latter one assumed ||0'|| S ground-truth as well as ||x || to < action space. See Appendix A for more discussions on this.
'e also remark that some assumptions on the action is needed. For example, if every action can only query coordinate (each action corresponds to one vector of the standard basis) then an l2 (d) regret lower bound is unavoidable. Hence, in this paper, we only consider the benign case that action set the unit sphere.
2

---

Published as a conference paper at ICLR 2023
speaking, if the plug-in linear bandit algorithm F is ((di)-aaaiiiee then our framework directly gives an (s(](s) vd), ((g(s) + 1))--arriacce-wwar algorithm for sparse linear bandits.
Besides presenting our framework, we also illustrate its usefulness by plugging in two existing variance-aware linear bandit algorithms, where the first one is variance-aware (i.e., works in unknown- variance cases) but computationally inefficient. In contrast, the second one is efficient but requires the variance of be delivered together with feedback rt- Their regret guarantees are stated follows.
1. The first variance-aware linear bandit algorithm we plug in is VOFUL, which was proposed by Zhang et al. (2021) and improved by Kim al. (2021). This algorithm is computationally inefficient but deals with unknown variances. Using this VOFUL, our framework generates a (s2.5 + sv d. s²) s )-vara-aeee----eee variance-aware aware algorithm for sparse linear bandits. Compared to the ((vsdT) regret lower-bound for sparse linear bandits (Lattimore Szepesvári. 2020, $24.3), our worst-case regret bound is near-optimal up to a factor vs. Moreover, our bound is independent of d and T in the deterministic case, nearly matching the bound of divide and-cquer algorithm dedicated to the deterministic setting up poly(s) factors.
2. The second algorithm we plug in is Weighted OFUL (Zhou et al., 2021), which requires known variances but is computationally efficient. We obtain an (s² + sv d, s 1155 (T)) (err>vvarince-awaa efficient algorithm. In the deterministic case, this algorithm can only achieve a v /T-type regret bound (albeit still independent of d). We note that this not due our framework but due to Weighted OFUL which itself cannot gives constant regret bound in the deterministic setting.
Moreover, we would like to remark that our deterministic regret can be further improved if better variance-aware linear bandit algorithm is deployed: The current ones either have (dP) (Kim et al., 2021) or (VVTT) (Zhou et al., 2021) regret in the deterministic case, which are both sub-optimal compared with the (dd) lower bound.
1.2 RELATED WORK
Linear Bandits. This problem was first introduced by Dani et al. (2008), where an algorithm with regret (lv/ %) and near- mear-matching regret lower-bound (ddv/)) were given. After that, an improved upper bound (dv log T) (Abbasi- Yadkori et al., 2011) together with an improved lower bound (dd (Li et al., 2019) were derived. An extension of it, namely linear contextual bandits, where the action set allowed for each step can vary with time (Chu et al., 2011; Kannan al., 2018; Li et al., 2019; 2021), is receiving more and more attention. The best-arm identification problem where the goal of the agent is to approximate 6* with as few samples as possible (Soare et al., 2014; Degenne et al., 2019; Jedra & Proutiere, 2020; Alieva al., 2021) is also of great interest.
Sparse Linear Bandits. Abbasi-Yadkori et al. (2011) and Carpentier& & Munos (2012) concurrently considered the sparse linear bandit problem, where the former work assumed noise model of and achieved Ō RV (VvdTT) regret, while the latter one considered the noise model of r. (x, + Tr. f*) such that ||nalla S and ||0' I 0, achieving Ō( =02xsvT) regret. Lattimore al. (2015) assumed hypercube (i.e., X' = []1, action set and a ||0|] || S 1 ground-truth, yielding Ö(sVT) regret. Antos & Szepesvári (2009) proved a 2( d lower-boun bound when s = 1 with the unit sphere as X. Some recent works considered data-poor regimes where d >>>>> T (Hao et al., 2020; 2021a;b; Wang et al., 2020), which is beyond the scope of this paper. Another work worth mentioning is the recent work by Dong et al. (2021), which studies bandits or MDPs with deterministic rewards. Their result implies an ( g//1) bound for deterministic sparse linear bandits, which is independent of d. They also provided an ad-hoc divide-and-conquer algorithm, which achieves O(s log d) regret only for deterministic cases.
rs = (2,, 0*) + 7) such that 7) is
Variance-Aware Online Learning. For tabular MDPs, the variance information is widely used in both discounted settings (Lattimore & Hutter, 2012) and episodic settings (Azar et al., 2017; Jin et al., 2018), where Zanette & Brunskill (2019) used variance information to derive problem- dependent regret bounds for tabular MDPs. For bandits, Audibert et al. (2009) made use of variance information in multi-armer bandits, giving an algorithm outperforming existing ones when the variances for suboptimal arms relatively small. For bandits with high-dimensional structures, Faury et al. (2020) studied variance adaptation for logistic bandits, Zhou et al. (2021) considered linear bandits and linear mixture MDPs where the variance information is revealed to the agent,
3

---

Published as a conference paper at ICLR 2023
Table 1: An overview of the proposed algorithns/results and comparisons with related works.
Algorithm
Setting
Worst-case Rogret"
Deteministi-case Regret"
Efflciency
Variances
ContidenceBalll (Dai al., 2008)
Oon
LinBandit
OldvT)
OFUL (Abbasi Yadkori et al., 2012)
Spurse LinBundit
O(ved))
NIA
S1-0CR (Carpenrier Munos, 2012)
Sparse Lannandii
Lattimore et (2015, Algorithu 4)
Spurse LinBandit
OlavT)"
Neightedd OFUI, (Zhou al., 2021)
LinBandit
Ö(dvT)
Olvar)
Known
VOFUL2 (Kim al., 2021)
LinBandit
Ö(d--VT)
O(dP)
Unknown
Spurse LinBundit
ÖGAVT -sval
((s+-AV))
Known
VASLE (This work)
Sparse LinBandit
O(AAATT + av/i)
O(e))
Unknown
Lower Bound (Antos Szepesvári, 2009)
Sparse LinBandir
D(vaT))
N/A
"Worst-case" means the variances of are all Here, d the ambient dimension, T is the number of rounds,
and the sparsity parameter (only applicable to sparse linear bandits).
"Deeterministic-cae"" means the variances of are all O. Only applicable to variance-aware algorithms. "With a different feedback model; see Appendix A for more comparison.
"With a different action set an different assumption on 0"; see Appendix A more comparison. "This bound holds even 8 and the action set fixed to be the unit sphere.
giving an Oldy Et of + VdT) guarantee for linear bandits, and Zhang et al. (2021) proposed another algorithm for linear bandits and linear mixture MDPs, which does not require any variance of + d) as shown by Kim et al. (2021). The recent work by Hou et al. (2022) considered variance- conntrc-no best arm identification, where the feedback noise only depends on the action by the agent (whereas ours can depend on time, which is more general than theirs). Another recent work (Zhao et al., 2022) studied variance-aware regret bounds for bandits with general function approximation the known variance case.
information, whose regret can be improved to be O
Stochastic Contextual Sparse Linear Bandits. In the setting, the action set for each round f is i.i.d. sampled (called the "context").. It is known that (VVsT) regret is achievable in this setting (Kim & Paik, 2019; Ren & Zhou, 2020; Oh et al., 2021; Ariu et al., 2022). However, in our setting where both action set X' and ground-truth 0" are fixed, a polynomial dependency because it is impossible to learn more than one parameter per arm (Bastani & Bayati, 2020), agreeing with the 22( VdT) lower bound when s = (Antos & Szepesvári, 2009; Abbasi- Yadkori et al., 2012).
d is in general unavoidable
PROBLEM SETUP
Notations. We use [N] denote the set {1, .1, N] where N N. For a vector I E RRd we use ||>|| to its nop-n namely ||>=|p A (Ei Vr. We use $d-1 to denote the (d - di-dienniioa unit sphere, i.e., 1d-1 & {ir Rd ||æ|||2 = 1}. We use Ō(.) and (-)) to hide all logarithmic factors in T, s, d and log 1 3 (see Footnote 1). For a random event E, we denote its indicator by 1[2].
We assume the action space and the ground-truth space are both the (d 1) -ddimensional unit sphere, denoted by X e gd-1, Denote the ground-truth by 0* X. There will be T 2 1 rounds for the agent to make decisions sequentially. At the beginning of round / E [7]. the agent has to choose an action I, X. At the end of step 4, the agent receives a noisy feedback r = (zzz, 0*) + 7h. Vi E [T'. where We is an independent zero-mean Gaussian random variable. Denote by o² = Var(n)) the variance of Me. For a fair comparison with non- van--aarine-aaaan algorithms, we assume that of < 1. The agent then receives a (deterministic and unrevealed) reward of magnitude (I,, 0*) for this round.
The agent allowed to make the decision F, based all historical actions Z1.... It-1, all historical feedback r...... .Tt-1. and any amount of private randomness. The agent's 's goal is to minimize the regret, defined as follows.
Definition 2 (Regret). The following random variable is the regret of a linear bandit algoritim::
T
T
RT = max ZEX
Σ
(z,00)
(o,, 0-) = Σ 10
xtz 0*),
(1)
1=1
where the second equality is due our assumption that X Sd--1
4

---

Published as a conference paper at ICLR 2023
Algorithm 1 Variance-Awar Sparse Linear Bandits (VASLB) Framework
Input: Number of dimensions d, linear bandit algorithm F and its regret estimator R
1: Initialize gap threshold A f- z. estimated "good" coordinates S <- Ø3 current round / < 0.
2: while
do 3: if' S * Ø then
> The algorithm automatically increases by per query. >> Have some coordinates to "commit". Initialize new linear bandit instance F coordinates S.
4:
"CCommit" phase.
5: Execute F for n 2 steps & maintain pessimistic estimation R.F.
until R < <
n 12
6:
Suppose that F plays T1, T2. , Set Ø
Σ
Ty as the estimate for {0] hes.
7: if Eies 07 S A then
Still have undiscovered coordinates with 0 2
8: Let R + V EiEs K-
> "Explore" phase. Perform n 2 calls to RANDOMPROJECTIONCA S, in Algorithm 2, until
9:
2 2 TRi F.) k=
Visis
where r3 is the k-th return vector of RANDOMPROOECTION and F 1 "
Eks Tk-
10:
for i 1.2..... K do
11:
if T, A where 7 4 km T% then add the i-th element that is not in S to S.
Algorithm 2 The RANDOMPROJJETTIO Subroutine
1: function RANDOMPROJJETTON(KK R, S,
2: Generate K i..d. samples y1, 1/2 V/..... yK,, each with equal probability being + VK
0:
E S
3: Play x E X constructed as x; yy
is the j-th element that is not in S
4: return K ((r -ies 07) v) where r (z, 0*) + r the (noisy) feedback.
For the sparse linear bandit problem, we have an additional restriction that ||@* S s, i.c., there are most coordinates of 6* is non-zero. However, mentioned in the introduction, the agent does not know anything about s she only knows that she facing a (probably sparse) linear environment.
3 FRAMEWORK AND ANALYSIS
Our framework VASLB presented Algorithm 1. We explain its design Section 3.1 and sketch its analysis in Section 3.2. Then give two applications using VOFUL2 (Kim et al., 2021) and Weighted VOFUL (Zhou et al., 2021) as F. whose analyses are sketched Sections 4.1 and 4.2.
3.1 MAIN DIFFICULTIES AND TECHNICAL OVERVIEW
At high level, our framework follows the spirit of the classic cetoorettee-ccommeee approach (which is directly adopted by Carpentier & Munos (2012)). where the agent first identifies those "huge" entries of 6* and then performs linear bandit algorithm on them. However, it is hard to incorporate variances into this vanilla idea to make it variance-aware the desired regret depends on variances and thus unknown to the agent. Thus is difficult to determine a "gap threshold" A (that is, the agent stops to "commit" after identifying all 0r A) within few rounds. For example, in the deterministic case, the agent must identify all non-zere entries to make the regret independent of T'; on the other hand, in the worst case where o, 1, the agent only needs to identify all entries with magnitude at least 1 to yield /T-style regret bounds. At the same time, the actual setting might be mixture them (c.g., o, = 0 for t to and o, = 1 for > to where to E [T]). As a result, such an idea cannot always succeed in determining the correct threshold A and getting the desired regret.
5

---

Published as a conference paper at ICLR 2023
multiple times. We reduce the uncertainty gently and alternate between "explore" and "commit" modes. We decrease a "gap threshold" A in a halving manner and, at the same time, maintain set S of coordinates that believe to have a magnitude larger than A. For each A, we "explore" (estimating Of and adding those greater than A into 5) and "commit" (performing linear bandit algorithms coordinates in S).
In our proposed framework, we tackle this issue by texpllre-then-comeee
However, as we "explore" again after "committing", we face a unique challenge: Suppose that some entry E [d] is identified be least 2 by previous "explore" phases. During the next "explore" phase, we cannot directly do pure exploration over the remaining unidentified coordinates otherwise, coordinate i will incur 4A regret for each round. Fortunately, we can get an estimation 0g of f7 during the previous "commit" phase thanks to the regret-to- regret-to-sampee to--ammle-copllleiiii conversion (Eq. (3)). Guarded with this estimation, we can reserve 0; mass for arm and subtract 0² from the feedback in subsequent "explore" phases. More preciously, we do the following.
1. In the "commit" phase where we apply the black-box F, we estimate Hes by the regret-to- sample-complexity conversion: Suppose F plays T1, 22,...; In and achieves regret R then
(0' -000 = RSd where 0 -
T4-
Hence, if we take (0thes as an estimate of {07 hes. the estimation error shrinks as R2 is sub- linear and the LHS of Eq. (3) is non-negative. Moreover, X' by a lot (Lemma 18), we can safely use {0, Jes to estimate hes in subsequent phases. More importantly, if we are granted access to R, know how close the estimate is; we can proceed to the next stage once it becomes satisfactory. But it is unrevealed. Fortunately, we know the regret guarantee of F, namely R.F,, which can serve as pessimistic estimation of R₂ Hence, terminating when 1 RR 2 can ensure (0" 0, 0*) < A to hold with high probability. n phase, as mentioned before, we can keep the regret incurred by the coordinates
show that @ is not away from
2. In the "exploration" identified in S small by putting mass 0: for each E S. For the remaining ones, we use random projection, an idea borrowed from compressed sensing literature (Blumensath Davies, 2009; Carpentier & Munos, 2012), to find those with large magnitudes to add them to S.
One may notice that putting mass 0g for all i S will induce bias to our estimation as Eies 0f +
Eies 6,07. However, as 0g is close to 6 this bias will be bounded by O( and become dominated by A as A decreases. Hence, if we omit this bias, error due to standard concentration inequalities like Empirical Bernstein (Maurer & Pontil, 2009; Zhang et al., 2021). Once it becomes small enough, we alternate the "commit" phase again.
overestimate the estimation
Therefore, with high probability, we can ensure all coordinates not in S have magnitudes no more than O(A) and all coordinates in S will together contribute regret bounded by O(A)). Hence, the regret in each step is (roughly) bounded by (s)22) Upper bounding the number of steps needed for each stage and exploiting the regret guarantees of the chosen F then gives well-bounded regret.
3.2 ANALYSIS OF THE FRAMEWORK
Notations. For each A, let TA be the set of rounds associated with A. By our algorithm, each Ta should be an interval. Moreover, (Ta), a forms partition of [T'. Define Tg as all the rounds in the "commit" phase when the gap threshold is A (where F is executed), and Th as the "explore" phase (i.c., those executing RANDOMPROJECTION Let T and T be the steps that the agent decided not to proceed in Tg and Th respectively, which are formally defined as T = { T I. + max ('}, i = a, b. Define the final value of A as Ay. Denote n = |T and n² = |T (both are stopping times). We have Σx=2-2.... B (n + n'a) )- = T. We can then decompose Ry into R2. and R4.:
RS
Σ
Σ 10~ Fr, 0") RS
Σ
Σ
- 0"),
Ft,
A=
LETS
A= A=2 2.2-2
where R4. may depend on the choice of F and R44 only depends on the framework (Algorithm 1) itself. We now show that, long as the regret estimation R. is indeed an overestimation of R.

---

Published as a conference paper at ICLR 2023
with high probability, The full proof of Theorem 3 will be presented in Appendix F and is only sketched here.
get good upper bound of R4, which is formally stated as Theorem 3.
Theorem 3. Suppose that for any execution of F that last for n. steps, R R holds with probabiliry 1 6, i.e. R is pessimistic. Then the total regret incurred by the second phase satisfies
1 log
1
R₂ = svd Σ oi
s log
with probability 1 d.
Remark. This theorem indicates that our framework itself will only induce an (svd, v--vannance- awareness to the resulting algorithm. As noticed by Abbasi- Yadkori et al. (2011), when or = 1, ((VsdT) regret is unavoidable, which means that it is only sub-optimal by a factor no more than ss. Moreover, for deterministic cases, the (s)) regret also matches the aforementioned divide-and- conquer algorithm, which specially designed and can only work for deterministic cases.
Proof Sketch of Theorem 3. We define two good events with high probability for given gap thresh- old A: GA and Ha. Informally, GA means Eies 8 (0: 0.) A (i.e., 0 is close to 8 after "commit") and Ha stands for [0;] 2 ((A) if and only if E S (i.e., "explore" correctly). Check Eq. (10) in the appendix for formal definitions. For Ga. from Eq. (3), we know that it happens as long as R R remains to argue that Pr[HA 9a. H2a}
sõ.
By Algorithm 2, the i-th coordinate each rи (1 S & S n/ is an independent sample of
K (u:) 07 + > 0, 0,) R
K
K
H Viys
07
+
Th
(4)
R22
JES
JESJ
J/K is an independent Rademacher random variable. After conditioning on GA and H2s where nt. Eies 07 and Eves 0,03 will be close. Therefore, the first term exactly 87 (the magnitude we want estimate), the second term a small bias bounded by ( and the last two terms are zero-mean noises, which are bounded by A according to Empirical Bernstein Inequality (Theorem 10) and our choice of n' (Eq. (2)). Hence, Pr(Ha 9A. Hea} 2 1 1680. sõ.
Let us focus on an arm i* never identified into S in Algorithm By definition of n' (Eq. (2)),
A
(n'
1)
<2
2
(rL.
72.)2
2 Σ
(rr. 12r 0"
4
LETA
YETA
where the second inequality is due to properties of sample variances. By GA. those coordinates in S will incur regret of ( =0, Eies(0r 0,)07 < A for all E Th Moreover, by H2s. each arm outside will roughly incur n'a (0F) O A?) regret, as ys 's are independent and zero-mean. As there are at most s non-zero coordinates, the total regret for Th will be roughly bounded by Onn' sA²) (there exists another term due to randomized yı 's, which is dominated and omitted here; check Lemma 21 for more details). Hence, the total regret is bounded by
Σ (ru, 1(raa-)))21n 4 LET
R4 S
Σ Osn s.
Σ A
A
5 + O(s).
To avoid undesired (T) factors, cannot directly apply Cauchy-Schwartz inequality to the sum of square roots (as there are a lot A's). Instead, again by definition of n (Eq. (2)), we observe the following lower bound of n',, which holds for all A's except for Ay:
n O V (TL. )) 4). As EA n < T. some arithmetic calculation gives
7

---

Published as a conference paper at ICLR 2023
(intuitively, by thresholding, manage to "move" the summation over A into the square root, though suffering an extra logarithmic factor; see Eq. (15) in the appendix for more details)
Σ A ApAs
(ru. - B|r
Σ AAAs
A
(ru. Blra,s113
LET3
IET3
For a given and any 1 S le S na. the expectation of (rk,s- E2 E[ 1)2 bounded by (1 of) (Eq. (19) in the appendix), which is no more than (1+ 4d 22 By concentration properties in the sample variances (Theorem 14 in the appendix), the empirical (Th,s- 1)) should also be close to (1 T hence, one can write (omitting all log & terms)
R2 - E Smngar) -
Σ 2 )
As Ea n24² 2 appears on both sides, apply the "self-bounding" property (Efroni et al., 2020,
Lemma 38) to conclude Ry. = -IE sn A2) A²) = ō (s (s
of + 8). as claimed.
4 APPLICATIONS OF THE PROPOSED FRAMEWORK
After showing Theorem 16, it only remains to bound Rg. which depends on the choice the plug-in in algorithm F. In this section, give two specific choices of F, VOFUL2 (Kim et al., 2021) and Whtge OFUL (Zhou et al., 2021). The former algorithm does not require the information of o,'s 's (i.e., it works in unknown-variance cases), albeit computationally inefficient. In contrast, the latter is computationally efficient but requires of to be revealed with the feedback at round t.
4.1 COMPUTATIONALLY INEFFICIENT ALGORITHM FOR UNKNOWN VARIANCES
We first use the VOFU12 algorithm from Kim al. (2021) as the plug-in algorithm F, which has the following regret guarantee. Note that this is slightly stronger than the original bound: We derive strengthened "self-bounding" version of it (the first inequality), which critical to our analysis.
Proposition (Kim al. (2021, Variant of Theorem 2)). VOFUL2 executed for rounds on d dimensions guarantees, w.p. at least 1- 6, there exists a constant C O(1) such that Rd S & log 2). where stopping time finite a.s. and of oi ......, of are the variances of the independent Gaussians mh .2........ Tn-
(5 V Ei In + d2 In 3) Ō (d).5. ( of log à &
We now construct the regret over-estimation R... Due to unknown variances, is not straightforward. Our rescue is to use ridge linear regression 3 argmin (r (zx, 3)) + ||1 for samples ((Tk, Tkk = which ensures that the empirical variance estimation Ei=1(re (x 3) differs from the true sample variance Σx=1 k= vi Ek= (Tk - (Ix, )² by no more than ( log } (check Appendix E for a formal version). Accordingly, from Proposition 4, we can see that
RT S RI
1.5
E(re (rr, 3 + 2 V 2
s0
In
8
1.5 21n 1
+
1 Iu
(S)
Moreover, one can observe that the total sample variance Σk= o is bounded by (a constant multiple of) the total variance Σ of (which is formally stated as Theorem 13 in the appendix). Therefore, with Eq. (5)
pessimistic regret estimation R.F., have the following regret guarantee.
Theorem 5 (Regret of Algorithm with VOFUL2). Algorithm 1 with VOFUL2 as F and RyJ defined in Eq. (5) ensures that RT Ō( svd)y Σ of log + log 1) with probability 1 - 5.
Due space limitations, we defer the full proof Appendix G.1 and only sketch it here.
8

---

Published as a conference paper at ICLR 2023
Proof Sketch of Theorem 5. To bound R4, consider the regret from the coordinates in and outside separately. For the former, the total regret in a single phase with gap threshold is simply controlled by O (s1.5 V /EEETS oi log 3 5² log }) (thanks to Proposition 4). For the latter, each non-zero coordinate outside S can at most incur ( regret for each & T By definition n (Line 5), we have á
V oi In _ + - In +) just like the proof of Theorem 3. As the regret from the second part is bounded by (s naa ). these two parts together sum to
1T O 2
52.5
Σ m log + log + sA2
BET
As in Theorem 3, we notice that n 2 2
EiETy oi in 3- In 4) for all A A again by definition of n2 This will move the summation over A into the square root. Moreover, by the fact that vi = Oa log 2)) (Theorem 14 the appendix), we have Rÿ Ô (s2.5 E of log } 3 log t). Combining this with the bound of R4 provided by Theorem concludes the proof. C
4.2 COMPUTATIONALLY EFFICIENT ALGORITHM FOR KNOWN VARIANCES
In this section, we consider a computational efficient algorithm Weighted OFUL (Zhou et al., 2021), which itself requires of to be presented at the end of round t. Their algorithm guarantees:
Proposition 6 (Zhou al. (2021, Corollary 4.3)). With probability at least 1 - 5, Weighted OFUL executed for steps on d dimensions guarantees R. I C(v dn log // + +d E of log ()) where C= C1)(1), n a stopping time finite a.s., and of, o2....,oo" on are the variances of m, T2...,, Tn-
Taking F Weighted OFUL, we will have the following regret guarantee for sparse linear bandits: Theorem 7 (Regret of Algorithm 1 with Weighted OFUL). Algorithm with Weighted OFUL F and Ry defined C(V /n + sv Σ oî In {) guarantees Ri Ö ((5²
svd) T. of log + s. V../Tllog 3) with probability 1- 8.
The proof is similar to that of Theorem i.e., bounding n² by Line of Algorithm and then using summation techniques to move the summation over A into the square root. The only difference that we will need to bound O A 2),, which seems to be as large T if we follow the analysis
of Theorem 5. However, as included additive factor V ss In 1 in the regret over-estimation
S In J. which means n = 2(=A From Σa n S T, we can consequently bound ΣA A- as 0( O
Rh, we have n > A
F) The remaining part is just an analog of Theorem 5. Therefore, the proof is omitted in the main text and postponed to Appendix H.
5 CONCLUSION
We considered the sparse linear bandit problem with heteroscedastic noises and provided general framework to reduce any variance-aware linear bandit algorithm F to an algorithm Ç for sparse linear bandits that is also variance-aware. We first applied the computationally inefficient algorithm VOFUL from Zhang et al. (2021) and Kim et al. (2021). The resulting algorithm works for the unknown-
variance case and gets ((s225 + svd) Σ Σt= of log 1 + 8 log 1) regret, which, when regarding the sparsity factor < d as constant, not only is worst-case optimal but also enjoys constant regret in deterministic cases. We also applied the efficient algorithm Wee i ghted OFUL by Zhou et al.
(2021) that requires known variance; we got ((s² + sv E of log + (vsT s) log } regret, still independent of d in deterministic cases. See Appendix B for several future directions.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We greatly acknowledge Csaba Szepesvári for sharing the manuscript (Antos & Szepesvári, 2009) with us, which shows the (VVdT) lower bound for sparse linear bandits when 8 and the action sets are unit balls. The authors thank Xiequan Fan from Tianjin University for the constructive discussion about the application of Propositions and 11. At last, we thank the anonymous reviewers for their detailed reviews, from which we benefit greatly. This work was supported in part by NSF CCF 2212261, NSF IIS 2143493, NSF DMS-2134106, NSF CCF 2019844 and NSF IIS 2110170.
REFERENCES
Yasin Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Yasin Abbasi- Yadkori, David Pal, and Csaba Szepesvari. Onllne-to-cooffienee-stt conversions and application to sparse stochastic bandits. In Artificial Intelligence and Statistics, pp. 1-9. PMLR, 2012.
Ayya Alieva, Ashok Cutkosky, and Abhimanyu Das. Robust pure exploration in linear bandits with limited budget. In International Conference Machine Learning, pp. 187-195. PMLR, 2021.
András Antos and Csaba Szepesvári. Stochastic bandits with large action sets revisited. Personal communication, 2009.
Kaito Ariu, Kenshi Abe, and Alexandre Proutière. Thresholded lasso bandit. In International Conference on Machine Learning, pp. 178-928. PMLR, 2022.
Jean-Y Audibert, Rémi Munos, and Csaba Szepesvári. Exploration-exploitttonn tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19):1876 1902, 2009.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference on Machine Learning, pp. 263-272. PMLR, 2017.
Hamsa Bastani and Mohsen Bayati. Online decision making with high-dimensional covariates. Operations Research, 68(1):276-294, 2020.
Thomas Blumensath and Mike E. Davies. Iterative hard thresholding for compressed sensing. Applied and computational harmonic analysis, 2763)2265- 2009.
Alexandra Carpentier and Rémi Munos. Bandit theory meets compressed sensing for high dimensional stochastic linear bandit. In Artificial Intelligence and Statistics, pp. 190-198. PMLR, 2012.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208-214. JMLR Workshop and Conference Proceedings, 2011.
Varsha Dani, Thomas Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. In st Annual Conference on Learning Theory, pp. 355-366 Omnipress, 2008.
Rémy Degenne, Wouter M Koolen, and Pierre Ménard. Non-asymptotic pure exploration by solving games. Advances in Neural Information Processing Systems, 32, 2019.
Kefan Dong, Jiaqi Yang, and Tengyu Ma. Provable model-based nonlinear bandit and reinforcement learning: Shelve optimism, embrace virtual curvature. Advances in Neural Information Processing Systems, 34, 2021.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-eexploottiion in constrained mdps. arXiv preprint (rXii:2003302189 2020.
Xiequan Fan, Ion Grama, and Quansheng Liu. Exponential inequalities for martingales with applica- tions. Electronic Journal of Probability, 20:1-22, 2015.
10

---

Published as a conference paper at ICLR 2023
Louis Faury, Mare Abeille, Clément Calauzenes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits. In International Conference on Machine Learning, pp. 3052-3066 PMLR, 2020.
David Freedman. On tail probabilities for martingales. the Annals of Probability, pp. 100-118, 1975.
Botao Hao, Tor Lattimore, and Mengdi Wang. High-dimensional sparse linear bandits. Advances in Neural Information Processing Systems, 13:10733-10763, 2020.
Botao Hao, Tor Lattimore, and Wei Deng. Information directed sampling for sparse linear bandits. Advances in Neural Information Processing Systems, 34, 2021a.
Botao Hao, Tor Lattimore, Csaba Szepesvári, and Mengdi Wang. Online sparse reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pp. 316-324. PMLR, 2021b.
Jean Honorio and Tommi Jaakkola. Tight bounds for the expected risk of linear classifiers and pac-bayes finite-sample guarantees. In Artificial Intelligence and Statistics, pp. 384-392. PMLR, 2014.
Yunlong Hou, Vincent YF Tan, and Zixin Zhong. Almost optimal variance-consstrained best arm identification. arXiv preprint wwXiv:2201.10144 2022.
Yassir Jedra and Alexandre Proutiere. Optimal best-arm identification in linear bandits. Advances in Neural Information Processing Systems, 13:10007710017, 2020.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
Sampath Kannan, Jamie H Morgenstern, Aaron Roth, Bo Waggoner, and Zhiwei Steven Wu. A smoothed analysis of the greedy algorithm for the linear contextual bandit problem. Advances in neural information processing systems, 31, 2018.
Gi-Soo Kim and Myunghee Cho Paik. Doubly-robun lasso bandit. Advances Neural Information Processing Systems, 32, 2019.
Yconeung Kim, Insoon Yang, and Kwang-Sung Jun. Improved regret analysis for variance-adaptive linear bandits and horizon-free linear mixture mdps. arXiv preprint arXiv:2111.03288 2021.
Johannes Kirschner and Andreas Krause. Information directed sampling and bandits with het- croscedastic noise. In Conference On Learning Theory, pp. 358-384, PMLR, 2018
Tor Lattimore and Mareus Hutter. Pac bounds for discounted mdps. In International Conference Algorithmic Learning Theory, pp. 320-334. Springer, 2012.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Tor Lattimore, Koby Crammer, and Csaba Szepesvári. Linear multi-resource allocation with semi- bandit feedback. Advances in Neural Information Processing Systems, 28, 2015.
Yingkai Li, Yining Wang, and Yuan Zhou. Nearly minimax-optimal regret for linearly parameterized bandits. In Conference Learning Theory, pp. 2173-2174. PMLR, 2019.
Yingkai Li, Yining Wang, Xi Chen, and Yuan Zhou. Tight regret bounds for infinite-armer linear contextual bandits. In International Conference on Artificial Intelligence and Statistics, pp. 370- 378. PMLR, 2021.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample-variance penaliza- tion. In COLT 2009 The 22nd Conference on Learning Theory, 2009.
Min-hwan Oh, Garud Iyengar, and Assaf Zeevi. Sparsity-agnostic lasso bandit. In International Conference Machine Learning, pp. 8271-8280. PMLR, 2021.

---

Published as a conference paper at ICLR 2023
Zhimei Ren and Zhengyuan Zhou. Dynamic batch learning in high-dimensional sparse linear contextual bandits. arXiv preprint 1991,, 2020.
Marta Soare, Alessandro Lazaric, and Rémi Munos. Best-arm identification in linear bandits. Advances in Neural Information Processing Systems, 27, 2014.
Yining Wang, Yi Chen, Ethan Fang. Zhaoran Wang, and Runze Li. Nearly dimension- independent sparse linear bandit over small action spaces via best subset selection. arXiv preprint arXiv:2009.0200 2020.
Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference Machine Learning, pp.
PMLR, 2019.
Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon S Du Improved variance-aware confidence sets for linear bandits and linear mixture mdp. Advances in Neural Information Processing Systems, 34, 2021.
Heyang Zhao, Dongruo Zhou, Jiafan He, and Quanquan Gu. Bandit learning with general func- tion classes: Heteroscedastic noise and variance-dependent regret bounds. arXiv preprint arXiv:2202.13603, 2022.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pp. 4572-4576. PMLR, 2021.
12

---

Published as a conference paper at ICLR 2023
Supplementary Materials
A More on Related Works
13
Future Directions
14
C Divide-and-Conquer Algorithm for Deterministic Settings
14
D Concentration Inequalities
15
D.1 Sample Mean Upper Bound
15
D.2 Sample Variance Upper Bound
16
Ridge Linear Regression
17
Omitted Proof in Section 3.2 (Analysis of Framework)
19
F.1
Proof of Main Theorem
19
F2
Regreroo-Sampll-Compextt Conversion
22
F3 Random Projection
22
F.4 Single-Phase Regret
24
Omitted Proof in Section 4.1 (Analysis of VOFUL2)
24
G.1 Proof of Main Theorem
24
G.2 Regret Over-Estimation
27
G.3 Extension Unknown Variance Cases
29
H Omitted Proof in Section 4.2 (Analysis of Weighted OFUL)
30
H.1 Proof of Main Theorem
30
H.2 Regret Over-estimation
32
I Auxilliary Lemmas
36
A MORE ON RELATED WORKS
In this section, briefly compare several related works sparse linear bandits in terms of regret guarantees, noise assumptions and query models.
The regret of Abbasi-Yadkori Yadkori et al. (2012) is Õ dT)) when assuming conditionally R-sub- Gaussian noises (i.e., Me F. subG(RE) which will be formally defined in ??). At the same time, they allow an arbitrary varying action set D1. Dz...., Dr C Bd (though they in fact allows arbitrary decision sets D1, Dz. ... Dr C Rd their regret bound scales with max || so we assume D, C Idd without loss of generality). This model is less strictive than ours, as we only allow Dj D:
Dr Bdd (as explained Footnote are Gaussian with variance and the ground-truth 6* is one-hot (i.e., = 1), their regret bound reduces to ((VdT), which matches the Ω (dTTT) bound in Antos & Szepesvári (2009) when the actions sets are allowed to be the entire unit ball (which means the agent will be more powerful than that of Abbasi- Yadkori et al. (2012)).
the main text. When the noises
13

---

Published as a conference paper at ICLR 2023
The regret of Carpentier & Munos (2012) is || assuming unit-ball action set, a | 12 Σ ||0||2 ground-trume -ouun and |m 2|2 I | noises, where 7 will be defined later.
This bound seems to bypass the [2 dT) lower bound when = 1. However, this is due to a different noise model: They assumed the noise component-wise. i.c., Tz = (0" + Ths Ft) where E R. In contrast, our model assumed a (0".z) + Th noise model where T)e E R. Therefore, the max, I/ dependency can be of order O(vd) to ensure similar noise model ours.
The regret of Lattimore et al. (2015, Appendix G) is also of order ((sVT), assuming a [-1, 1]- bounded noises, a hypercube X' = [-1, 1] action set and a |10*1| S ground-truth. We will then explain why this does not violate the S2( (2(vsdT) regret lower bound as well.
E X, which is valid in their query model (in fact, their algorithm is random projection procedure with some carefully designed regularity conditions, so this type of queries appears all the time). However, in our query model where the action set is the unit ball Bd, we have to scale it by Va As the noise will never be scaled, this will amplify
Consider an extreme query (1, 1, .,, 1
the noises by Vd, we will need poly(d) more times of queries to get the same confidence set, making the regret bound have a polynomial dependency on d. Moreover, their ground-truth 0* needs to satisfy ||0* < 1. However, an s-sparse ground-truth 0" with 2-norm 1 can have 1-norm as much as v8. Therefore, another v8 should also be multiplied for fair comparison with our algorithm.
In conclusion, the second and the third work assumed different noise or query models to amplify the signal-to-noise ratio and thus avoid polynomial dependency on d, compared to the regret bounds of Abbasi- Yadkori et al. (2012) and ours.
However, we have admit that Abbasi- Yadkori al. (2011) allows drifting action set, whereas ours only allow a unit-sphere action set, just like Carpentier & Munos (2012). The reason is discussed in Footnote in the main text.
B FUTURE DIRECTIONS
First of all, there is still gap in the worst-case regret in terms of s, the lower bound for sparse linear bandits is (dT) instead of our Ö(sVZT) when a, 1. Closing this gap in s is an interesting future work. Our current algorithm, unfortunately, incapable of O sdT) -style worst-case regret guarantee: Suppose that T ds², 0 1/2 for .. (so ll S 1), and or = Then V n (1+ -22). which gives n ~ dA -4, Hence, the total regret will be Ei Σa>s: na =0)) dE (07)² ds² = (s ). Thus, algorithmic improvements must be made to better dependency
we have n ~ A
We leave this for future research.
Moreover, the current work relies on the random projection procedure (Carpentier & Munos, 2012), which only works when the action set is the unit sphere. Such an assumption is unrealistic in practice. We wonder whether there is an alternative that only requires a looser condition.
At last, deriving variance-aware lower bound rather than minimax one is also important, it can better illustrate the inherent hardness of the problem with different noise levels. We remark that extending the proof of current minimax lower bounds (see, e.g., (Antos & Szepesvári, 2009)) to variance-aware ones is not straightforward.
C DIVIDE-AND-CONQUE ALGORITHM FOR DETERMINISTIC SETTINGS
In this section, we discuss how to solve the deterministic sparse linear bandit problem in Ö(s) steps using a divide-and-conquer algorithm, as we briefly mentioned the main text.
We mainly adopt the idea mentioned by Dong et al. (2021, Footnote 6). For each divide-and- conquer subroutine working on several coordinates é1, i2, is E [d], we query half of them (e.g.. é1, f....., fx/2 when assuming 2 k) with /2/k mass on each coordinate. This will reveal whether there is non-zero coordinate among them. If the feedback is non-zero, we then conclude that there exists a non-zero coordinate in this half. Hence, we dive into this half and conquer this sub- problem (i.e., divide-and-conquee Otherwise, we simply discard this half and consider the other half.
14

---

Published as a conference paper at ICLR 2023
However, this vanilla algorithm proposed by Dong et al. (2021) fails to consider the possibility that two coordinates cancel each other (c.g., two coordinates with magnitude = will make the feedback equal to zero). Fortunately, this problem can be resolved via randomly putting magnitude + \2/k /k on each coordinate, which is similar to the idea illustrated in Algorithm As the environment deterministic, each step will give the correct feedback with probability 1. Therefore, constant number of trials is enough to tell whether there exists non-zero coordinate.
At last, analyze the number of interactions needed for this approach. As it is guaranteed that each divide-and-conguer subrountine will be working on a set of coordinates where at least one of them non-zero, we can bound the number of interactions as O [o;+ #0 #subrountines containing i) As for each time will divide the coordinates into half, there be at most log2 d subrountines containing for each individual i. Therefore, the number of interactions will be O(s log d).
After that, will be sure find out all coordinates with non-zero magnitudes. Asking each of them once then reveals their actual magnitude. Therefore, we can recover #* in (( log + = O log d) rounds and will not suffer any regret after that. So the regret of this algorithm will indeed be (ss), which is (nearly) independent of d and
D CONCENTRATION INEQUALITIES
D.1 SAMPLE MEAN UPPER BOUND
We shall make use of the following self-normalizing result.
Proposition (Fan et al. (2015, Remark 2.9)). Suppose that {E:l= are independent and symmetric. Then for all x > 0.
Σ V
x²
Pr
S exp
ISken
Corollary 9. Let X2,.,.... Xn be sequence of independent and symmetric random variables where n is stopping time that is finite a.s. Thenfor any ō > O, with probability 6, we have
Σ (X 14) S Exx, -0,1-,,111
Proof. This immediately follows by picking x /n and then applying Fatou's lemma.
Therefore, present Empirical Bersstein Inequality for conditional symmetric stochastic processes with a common mean, as follows:
Theorem 10 (Empirical Bernstein Inequality). For sequence of independent and symmetric random variables X2, ... Xn that shares a common mean (i.e., [[[X,] = μu for some μ for all i), we have the following inequality where n is stopping time finite a.s.
m
a In
Pr
Σ
(X.
14) S
2 21-5,
6,
48 E (0.1),
where X = = E. X; is the sample mean.
Proof.
By direct calculation, we have
> -
x 2nX + +
x²
x² > Xx, - 11) n - -1)2
1m1
15

---

Published as a conference paper at ICLR 2023
Applying Corollary 9 to (X; gives
2 4
Pr
Xx 1Q) 2 Σ (X;
1 2
8
Therefore, with probability 1
8 2 we have
11 X
x) Σ (X 22² _ (X; x)2
72 Σ
4 n
(X: 112
In
4
(6)
Hence, with probability 2 we have
-
2) 2 Σ (X; X)2.
By the union bound, with probability we thus have
11) S 2 (X; x)2 4 8¹
X;
i=1
as claimed.
D.2 SAMPLE VARIANCE UPPER BOUND
Recall that random variable X is sub-Gaussian with variance proxy o² if and only if Efexp(A((X E[X]))] I exp(5X2o for all A > We shall denote such a random variable by ~ subG(o"). We first state the following generalized Freedman's 's inequality for sub-Gaussiad random variables.
Proposition 11 (Fan et al. (2015, Theorem 2.6)). Suppose that {E:) is a sequence of zero-mean random variables, i.e., B[G]] = O. Suppose that Elexxp(X,)) S eX)(f(A)Vi) for some deterministic function f(A) and some fixed [V.)== for all X E (0, 20), then, for all x, v > 0 and X > O, we have
k
k
Pr 3I
& 2
V 12 < exp (-Xx I(A)
To derive a bound related to E(x; - X)² and Σ of we will need to characterize the concentration of the square of a sub-Gaussian random variable, which is "sub-exponential" random variable:
Proposition 12 (Honorio & Jaakkola (2014, Appendix B)). For sub-Gaussiad random variable X
with variance proxy o² and mean μ., we have
1 E lepp (A(x² - S exp (16AP0*) KI S 4g2
Theorem 13, For a sequence of sub- -aubsians random variables {X:}a_ such that E[X,] = pa X; ~ (a? and n is a stopping time finite a.s.,
2 S 8, (0,
Σ ((x,-(i) - n2)2 B((X, - (1,)2)) 4
o
Proof. We first consider a non-stopping time n. Apply Proposition 11 to the sequence {(X; - -4;)²² 41)2 E[(X:- - }]) with V; =f f()) 16X for _nf and f()) = oo otherwise, where Tmax
is defined as max(01, .2....,,r, J. Then for all x, v > 0 and X E (0, a we have
Pr
((X: 22) B[(X, - (1) VΛ
Σ of Sv S exp (-Xx Ax + 16)2 1=1
16

---

Published as a conference paper at ICLR 2023
Picking x² = Ei= of
and x = 4v In g gives ozyin In3
2
x² 32v²
Pr
[X -1) > ((x; m₂)²
2
0
In
I
exp
i=1
i=1
32v²
2
8
= exp
32 2
(as 8² Σx= of maxx). A union bound by applying where À is set to 32p2 4v2c Funx
Proposition 1l to the sequence [B(X) (X; }4)3} with the same parameters and noticing the fact that V of < Σ of then shows that our conclusion hold for any fixed n. By Fatou's lemma, we conclude that also holds for a stopping time n that finite a.s.
Theorem 14 (Variance Concentration). Let {Xi)i= be a sequence of random variables with common mean such that X; ) (X; -1) is symmeetri,, and n is stopping time finite a.s. Then vg (0, 1), with probability 8, we have the the following three inequalities:
(X. -x-=
(X: 12)
1=1
Σ (X, -x-=
Σ
(X; - 11)
2 t=1
2
E(x, 112 < 2 of In
where X = E X; is the sample mean.
Proof. The first two inequalities follow from Eqs. (6) and (7). The last one follows from Theorem 13 together with the fact that E[(X; 11) S of by definition of sub-Gaussian random variables. C
E RIDGE LINEAR REGRESSION
Lemma 15. Suppose that we are given samples = G 1,2..., n, where 3 E Bd and { {6)) are stochastic processes adapted to the filtration {F.j such that is conditionally G-Gasssian, i.e. Fi-1 subG(T²). Define the following quantity as the estimate for 3*:
i-
8 argmin Σ (y TT + 1131//2
Then with probability 1 8, the following inequality holds:
(y x. TT
Σ (y. - xT TT
< 2d In
n
+ x
+ x
Xd52
Proof. Denote y (1/1 V ........)))))) T X (XT XT
12... X and (2,,,,, ... T. Denote
Var* E x. f and Var = Σ (v: x.. 2) We have the following representation of 3, which is by direct calculation (check, e.g., (Kirschner & Krause, 2018))
i = (X x + -xx
Furthermore, by Abbasi- Yadkori et al. (2011, Proof of Theorem 2), we have
-- = (x x + Xr -x +
(9)
17

---

Published as a conference paper at ICLR 2023
Therefore, write
Var" Var
(y X3) X3) = -8") x - x
= - (8)) x3") v² x23 8*).
By Eq. (8), we have x = (x + A1)3. So the first term is just A 33. As = X3 + e, the
second term is just (B*) X By Eq. (9), the last term becomes
y x(xxx x + -
For the sake of simplicity, we define (a, b) M = aTxxxX + -1) (note that (a, b) = (b, a) as X + AI is symmetric) and denote the induced norm by |l-||ar Therefore, we have
Var Var x
+ (x y, x M A(X y, 8-)
Again by Eq. (8), we have (X y, x) = 3'X Therefore, the second and third term together give
= -8-
XI
X | l ( 3*) + 18" ,r),,
=1IXTellas x
where the last step is yielded from using Eq. (9) reversely. Then note that (XT y, vy) = -3
taking expectation both sides gives
Var*
Var = A 3 +
cliis - ((3 (((0--))++ + X3 , - 2BT g |xx
|
= || El 1ll - 1 + 11118"113r.
By Muuchy-Schwartz we have
3 - 1 < xx + 11 (1X
X A 1/2
where the matrix norms can further be bounded by 1/ 1/Amin (XTX X + X/) S 1. Similarly, we can conclude that || < 1/ Amin (XTx x + [ < 1/x. Consequently, we have
Vaa"
Var
2 e + +
As proved by Abbasi-Yann Yadkori et al. (2011, Theorem 1), with probability 1 1- 8, we have
|| c S 20 In
(1 Vdee(xx + +X)
= =0² In
1 (A ((A+n/b)* 8
S do In
1
1+ 7
)
(dTt(AI)
52
Xd
where o² is the (maximum) variance proxy and the second last step is due to the Determinant-Trace Inequality (Abbasi-Yadkori al., 2011, Lemma 10). Hence, with probability - 6, we have
Var
Var S 2d In
Ad62 + + A
claimed.
18

---

Published as a conference paper at ICLR 2023
F OMITTED PROOF IN SECTION 3.2 (ANALYSIS OF FRAMEWORK)
F.1 PROOF OF MAIN THEOREM
In this section, we prove Theorem 3, which is restated as follows for the ease of reading:
Theorem 16 (Restatement of Theorem 3), Suppose that for any execution of F that last for n steps,
R. 2 R2 holds with probability 1 - 8, i.e., R2 is pessimistic. Then the total regret incurred by the second phase satisfies
log 1)
R2 Ō sVd
Σ
o log
1
with probability 1 Ó.
Proof. As mentioned in the main body, define the following good events for each A 2 2- 2 ....., Dy where Dy is the final value A:
GA Σ 00 - 0.) < 2 after TX
iE
HA (105) 3A + DiES)A (ES
1 2 = after T
(10)
is by definition to see that H indeed holds, as all |0,1 < and S is initially empty. We can then use induction to prove that all good events hold with high probability.
Here, list several technical lemmas informally referred in the main body, whose proofs left to subsequent sections. The first one is about the regret-to-samae sample-comples conversion.
Lemma 17 (Regret-to-saminn somple-complexity Conversion). If for any execution of F that lasts for steps, we have R. 2 R. with probability 1 then we have Pr(Ga} 2 -
The second term bounds the 'bias' term, i.e., the second term of Eq. (4) for random projection.
Lemma 18 (Bias Term of the Random Projection). Conditioning on GA and H2s, we have Eiss O (0)) < 3A which further gives |Eies 0,(0; 0.)l < 422.
Furthermore, we can bound the estimation error of the random projection process.
Lemma 19 (Concentration of the Random Projection). For any given i E [K], we will have
} so.
Pr F. 0,1
3
94 H2s
As long as the estimation errors are small, we can ensure, with high probability that the good event for A, namely H. will also hold.
Lemma (Identification of Non-zero Coordinates). Pr(Ha | 9a, H2a} 2 d8.
Therefore, by combining all lemmas above, we can ensure that all good events, namely (GA A Ha)a=2 2.....A,, hold simultancously with probability df'S.
At last, we bound the total regret incurred in Phase B for A.
Lemma 21 (Single-Phas Regret Bound), Conditioning on GA and Hep we have
R
Σ 10 xc, 0²) S 36sm A + 6sA 1ET3
2n In 8
with probability s6.
K
19

---

Published as a conference paper at ICLR 2023
Then follow the analysis sketched in the main body. We assume, without loss of generality, that 8 < Then, conditioning on all GA and Ha, some coordinate i* must never included into S as H.s holds for all A.
Therefore, by property of the sample variances (Theorem 14), for such i" and for each phase, with probability 1 1-d 6, we have Σn (Tn,s Tz;)² < Σ (Tn, - B(r Together with Eq. (2),
4 x (n - 1)
(T. - 1 1) In
(11)
By using Lemma 21, the total regret from Phase B is bounded by
R VK
1
RS S
Σ
36sn
6s
2n In
2 2-2 uy
By writing n as (n² 1) + 1, for any given A, the total regret of Phase is bounded by
R2. - Σ Σ
10 Iz. )7))
IET3
4
4 (Tr,i- El 1)a 2 In +1
36
A
LETA
R
2
4A 2
2 Σ
(rr,s. - B|re 1)2 1)2Inn +
K
AET
4
$
Σ
288
A
Σ
(res- E E
)) In 8
+ 36s12
(12)
LET1
Part (a)
Σ
248
In
1
(re. B/re, 1) In 4 + 12s V In
1
(13)
AET
As mentioned in the main text, make use of the following lower bound of n which again follows from Eq. (2) and holds for all A except Ay:
n
2 2
Σ (rr.5- - 7z-) In
2
2
(ne.s- - Elre,s-))211 8¹
A
LET1
LET1
where the last step is due to Theorem 14. For simplicity, define SA = A EIeTy (rn,i - E(r,, and
therefore n 2 A2 VSA where C =
=8 82/211
4 8+
constant we regard as a constant. Therefore,
C
Σ
V
SAS
Σ n ST
(14)
A
A#A,
A#A;
and our goal to upper bound Es VSA. Define threshold X T/ / Sa and
denote Ax = 2- [loRs X so that 4
< 1
x. We will have
Σ VSA= Σ
VSAt +
Σ
VSA
A/A
A
A=Ax/2....22
20

---

Published as a conference paper at ICLR 2023
(0)
x logg X
Σ SAt Σ
VSA
4
A=2-2 ,x.
Ax>A>A,
X
(6)
VSA
S V Vlogi X
Σ
SA +
Σ AxsAsA,
4
+BADAx
[c)
Vlog X
Σ 4aazAx
SA +
17 XC
(vlog, X +11
Σ Sa.
(15)
AWAs
where (a) applied Cauchy-Schward to the first summation, (b) applied the fact that 4 S x and (c)
used Eq. (14). So Part (a) of the regret, namely Eq. (12), can be bounded by
4 + 36s
288
A
(Te, E[r In x
4
(6)
4
1 288 2s
SA In
+
72s
- 288 288/22
In
(4T)
Σ
SA + v /Sa/
72s
A#A,
4 8 log, (47) + 728
576s
Σ
A
(ri. B(res 1)
4=2 2 B,..,Ay
1ET
(d)
S 5768
Σ
Σ 1ET3
(A2 + do?) In 4 1og4(47) 72s
(16)
8
A=2 2 A,
T
$ 115222sVd
Σ
of
In 8
log (4T) + 1152
Σ n' A In 8 (4T) + 72s.
where (a) used the fact that Σ < 2 A = -- (b) used Eq. (15), (c) again used Cauchy- Schwartz inequality and (d) used Theorem 14(3), the variance concentration result, Eq. (19), the magnitude of the variance, and the facts that A, K s d. Therefore, we can conclude that
((s) Inaaas A
5o svd,
Σ of log
T
4 I + + + s
n
Am
1
Notice that the left eeft-handed-sie and the right-handede -eet- has a common term (the RHS one is inside the square-root sign). Hence, by the self- aaf-bounding property Lemma 37, we can conclude that (note that we divided s on both sides)
T
Σ n An
Vd
Σ of log +1 + 5 (m)) }11)
(17)
which means that Part (a) (Eq. (12)), or equivalently
((s Es naA A2), is bounded by
of log 4
log 4
δ svd,
Now consider Part (b) of the regret, namely Eq. (13). The second term in each summand will sum up to Oss 1 log }). For the first term, using the notation SA, we want to bound
24s
1n3
1 3/4
Σ SAVS- < 24s In
Σ A
Sa < 48s In
1
Σ Sa. A
8
A
A
21

---

of log + log 4 g Published as a conference paper at ICLR 2023
Conditioning the same events in Eq. (16), will have
T
T
T
log 5)
S SaSS 0o
Σn
Σ n
Σ
d
s
Σ
do +
Σ
d
log
+ log
50
Σ
do
5
8
A
A
t=1
t=1
[=1
where the second step comes from Eq. (17). Therefore,
24s In !) 4/4 EAVS =
oi log 1 1 4/4
T d
8)
Vd
log
=
oi
log
1=1
which gives (by combining the bound of Eq. (12) and Eq. (13) together):
T
R2 SO
8V d
Σ of log
4
Further notice that, if d Ei= of 1, then the square-root is larger than the 4th-root. When d of & 1, then either root is bounded by s. Hence, in either case, the 4th-root will be hidden by other factors. Henceforth, we indeed have the following conclusion with probability 1 (s + 37)):
T
1 + log of log 8
1 8
R₂ <ō
By setting the actual as (s + 37)5, we will still have the same regret bound as O(log }) Oloo 1 + log c) Ō(lo 1/) as all logarithmic factors will be hidden by Ô.
F.2 SAARRETTTO-SAMPLLE COMPLEXITY CONVERSION
Proof of Lemma 17. By Fatou's lemma and the fact that n' is finite a.s. (as truncated according
to T), the probability that R is a pessimistic estimation for all n 1,2,... n' is bounded by
1 8. Conditioning this, by definition, we will have
10 00 -xn) < RTg S RJ.
which means our stopping criterion (Line 5) will ensure
2
RJP
00
0 0
<
A
7
and thus GA is ensured.
F.3 RANDOM PROJECTION
Proof of Lemma 18. By H2s, we have 10:1 > A, Vi E S, which gives 10; 0.1 < A by GA. So
can bound (EiEs(O - (0;)²) by 2 07 0,) EEes((;; - -0,² < 21 + A² 342
The second claim is then straightforward as 0,(0; - 0.) -0, - -0, - (0: - -007)) O
22

---

Published as a conference paper at ICLR 2023
Proof of Lemma 19. In the random projection procedure, let r (n) be the random variable defined as (which is the i-th coordinate of In in the algorithm)
(n)
K
(m)
(xn, 3-0}+ + +17 -5 03
Vi
R
jES
K
Vi
(n)
2
0,
+ Σ
-,
Σ
122
K
003
K (m) n22ii" ((n)))
Th- (18)
R
jES
Then T; is just the sample mean estimator of {r. (n) 1
R² Firstly, observe that y is always K so the first term of Eq. (18) is just 07, which is exactly the magnitude we want to estimate. Moreover, by Lemma 18, the second term is small (deterministic) bias added to 0 and is bounded by 3A 2 For the third term, each yj is independent, R Miyg is an
A
i..d. Rademacher random variable, denoted by (*) Hence, the last two terms sum to
K (m) R2 Vi
Σ jES
g 0z +
Tn-
By definition of Rademacher random variables, they are all zero-mean and symmetrie. Henceforth they can be viewed as noises with variances at most
E
Σ
R² Vi
K nm
(m)
E
(n) 03)
+
R2
K
nm
2
I 11
+
R
K
n
JES
(19)
where (a) is due to the mutual independence between 2j and (n)
Moreover, as each is also redrawn for every and i, we know that all {2) Jegs and tv," (n) hissing are all mutually independent. Because the first two terms Eq. (18) is not random, all (r(")) higusnn independent, symmetric and Sub-Gaussian (as 87 is bounded and 7n is Gaussian) random variables. Therefore, as na is indeed stopping time finite a.s., we shall apply Empirical Bernstein Inequality (Theorem 10) (r((")) }n where Var(r.")) is characterized by Eq. (19), giving
K
4 (nu. 7.)2 In 8 8.
Pr
2/
0J
+
R2
vi
Tn
2
J$
In other words, our choice of n in Eq. (2) will ensure the average noise is bounded by A By
Lemma 18, we conclude that Pr F; 071 > 3 +
A GA. H2r) S.
Proof of Lemma 20. If we skipped due Eies by Lemma 18, we will have
0
2 which is Line Algorithm 1, then
Σ > 1-11-500 5 conditioning on GA A H2s
iES
and thus all remaining coordinates are smaller than 3A. Moreover, by H2s all discovered coordinates with magnitude at least 24 4. Hence HA automatically holds in this case.
Otherwise, suppose that the conclusion of Lemma 19 holds for all i E [K] (which happens with probability 1 Kg conditioning on GA and H22), As we only pick those coordinates with [Fy > A, all coordinates with magnitude last A 4 3A2
3A will be picked as A 1. so the first
23

---

Published as a conference paper at ICLR 2023
condition of Hs indeed holds. Moreover, all picked coordinates will have magnitudes at least - - + 3A2). But when A t. there will be no coordinates in as it is initially empty. And after that, we will have A I a Hence, all coordinates with magnitude द will surely be identified, which means the second condition of Ha also holds.
We then have Pr[Ha Ga. N2a} 2 1 K6 by putting these two cases together.
F.4 SINGLE- PHASE REGRET
Proof of Lemma 21. Conditioning on Ga. as we are playing Tt,i = 0. for all i E S and / E Th we will have
Σ BET3 SS
Σ
00 - -x,))
Σ 1ET3
Σ (0
0.)0; n A²
Now consider single coordinate not S. For each E this coordinate. Hence, the total regret will become
Th we will equiprobably play + for
VK
R
R
0
0f
n
(01)² + 0
K
VK
RET
1ET
By Hes. the first term bounded by 36n A? By Chernoff bound, the absolute value of the summation in the second term will be bounded by /K non-zero coordinates by sparsity, from union bound, we can conclude that
Rt v 1/2m2g In } with probability 1 - 8. As there
(0 xz, 0-) 36sm A² + Gs IETİ
Σ
R VK
2m In
1
with probability s6.
G OMITTED PROOF IN SECTION 4.1 (ANALYSIS OF VOFUL2)
G. PROOF OF MAIN THEOREM
In this section, we prove Theorem 5, which is restated as Theorem 22. We first assume that Proposition 4 is indeed correct, whose discussion is left to Appendix G.2.
Theorem 22 (Regret of Algorithm 1 with VOFUL2 in Unkown-Variance Case). Consider Algorithum I with F VOFU1.2 (Kim et al., 2021) and R.j.
RF. = C
1.5
Σ (rk 1=1
(o 3))2
σ + 2²
21n
71
+ s
1.5
21n + 82 n 8
(20)
s52
5
where = ((1) is the constant hidden in the δ notation of Proposition 4, Tı, x2, Fn are the actions made by the agent, ..,..., In are the corresponding (noisy) feedback, and B is defined as
3 = argmin
Σ (rk (aTR, 33) + 11/11|2
DER*
The algorithm ensures the following regret bound with probability 1 8:
T + 3 loo
R₂ = (5255
(625 +
Σ
of
log x
1=1
24

---

Published as a conference paper at ICLR 2023
Proof. By Proposition 4, the total regret incurred by algorithm JF satisfies
R2 SC
mh
+ 2²
where C' C= (11 is constant (with some logarithmic factors) and Th NO, of is the noise for the k-th round executing F. We now consider our regret estimator R We show that, with high probability, it pessimistic estimation.
Lemma 23. For any given A with probability 6, R R
Therefore, for the "explore" phase, we can make use of Theorem 16 which only requires R2 be an over-estimate of R2 w.h.p., giving
T
1 8 + s slog
R4 S svd,
o log 5
So we only need to bound the regret for the "commit" phase, namely Rq- As mentioned in the main text, we will consider the regret contributed from inside and outside S seprately. Formally, will write Rgg. as
RS Σ
Σ A=2-2 TETS
EE
0, Lie
Σo;(0
It,i) + E(0r)3
where the equality because we will not put any mass on those ş S during the "commit" phase. We still assume the 'good events' Ga. H. hold for all A (defined in Eq. (10)). By H2a for given A. Eigs (0;)² & 36s22. Moreover, by Lemma 23, we will have
R4
Σ
R. m +
368
Σ
n A
A=2-2
2=2-2
By the terminating criterion
RT. a
A (Line 5 of Algorithm 1), for all A, we will have n²
1 15
4a ng.
which means
<
1.5
(re
1 (ce, 2 1n + 2
21
n1
In
1
+
1.5
21
1
+
2 In
1
+
2
862
g
8
IETS
Therefore, plugging back into the expression of R2. gives (the related with R is dominated by the second term, as intuitively explained in the main text):
In (n
1 1n + SA²
RS.
Σ
225
2.5
Σ (rr - (I,, (2., 1)
+
A
LET
The last term is simply bounded by (ss) after summing up over A. Let us focus on the first term, where need upper bound the magnitude of R.J. Applying Lemma 15 shows that the following with probability
rk (It. 3))²
S
71
2 +
2s
ln
+ 2.
k=1
25

---

Published as a conference paper at ICLR 2023
Therefore, write the regret (conditioning this good event holds for all A, which is with probability at least 1 dl'à according to Theorem 16) as
1 + 8a (Vio8 - log 2 + sA?
RJ S
Σ A=2-3
$2.
Σ FET
o log x
(21)
Again by the technique used for Appendix F, will need the following lower bound for all na except for the last one, which follows from the fact that R2 2 R (Lemma 23):
CgL.5
n A
Σ
In 8
LET
By the summation technique that we used in Appendix F, more preciously, by the derivation of Eq. (15), we will have the following derivation:
Cs
Σ
th In S
/log X
Σ
Σ
Cas
In 1
1 1
Σ Ax>A>Aj
Css.5
Σ
A
A#A,
IETS
1242Ax 1ET3
LET3
where X is defined as
X
c A*A
Σ
Σ
1
and Ax 2 2-1ln x1, which means A
Hence, we will have (the second summation will be
bounded by T' x as Σs n T)
T
C.
Σ of 55
Σ
C log 5
1.5
log
8
LETS
A IET
1=1
In other words, the first term of Eq. (21) will be bounded by
2.5
Σ
Σ LETS
In 5o
2
log
1 0
A=2 Ay
So we are done with the first and the last term of Eq. (21). Now consider the second term, which is equivalent to bounding Es 1. Use the following property guaranteed by (again) Line 5 of Algorithm 1:
Σ
-
4 8
Σ A#A,
n ST.
A#
which means Es 1 log,
log, (T/ = Ō(1). Combining them together gives
1 +3 3
(vios- 1
log 1 1 1
R4 ②
2.5
Σ
log
At last, due to Theorem 13, with probability 1 - 8,
Σ (ri - (0;,8"))
Σ
nh
(a)
<
Σ
Ein
F
4 Σ
ooe In
< 8
σ
In
2 8
A=1
1=1
k=
26

---

Published as a conference paper at ICLR 2023
Algorithm 3 VOFUL2 Algorithm (Kim et al., 2021)
for 1, 2, ....,.,, do
2:
Compute the action for the t-th round as
It = argmax max (2, 0),
(22)
ZE 8EN 6,
where G2 is defined in Eq. (24). Observe reward Ft = (Iz, 8*) + 7t-
3:
where (a) is due to Theorem 13 and (b) is due to Bl Fk S of Hence,
T
o log 1 x + (Vio3
1 log } 8 )
RS S O
2.5
Σ
Combining this with the regret for Rÿ (Theorem 16) gives
T
+ s3 (wioe 5 + log + s log 1
RT 00
(825 + svd)
of log x
T
= 0
(52.5 + sva)
of log
1 + + log g
5
as claimed.
G.2 REGRET OVER-ESTIMATION
In this section, we first discuss why the strengthened Proposition 4 holds. After that, we argue that our pessimistic estimation R,F indeed an over-estimation R, We state the VOFUL. algorithm in Algorithm 3 and also restate Proposition Proposition 24 for the ease of presentation.
Proposition 24. VOFUL2 on d dimensions guarantees, with probability least 1 - 8,
RJ = 0
Σ
T
of log J + de log 1 = -ō
dog
d
Σ
of
1 + dl log 3 log J
1
(23)
where T is a stopping time finite a.s. and of o2.0z..... o....., of are the variances of mh 72 ........ T7--
Proof. We will follow the proof of Kim al. (2021) and highlight the different steps. We first argue that an analog to their Empirical Bernstein Inequality (Zhang et al., 2021, Theorem 4) still holds.
Lemma 25 (Analog of Theorem from Zhang et al. (2021)). Let { be a sequence of zero- mean Gaussian random variables such that is a stopping time finite a.s. Then for all 2 8 and any E (0, 1).
n
4 8
Pr
X
8
Σ
x2
21-8.
Proof. This is direct corollary of Theorem 10.
Thanks to Theorem 14, the following analog of Lemma 17 from Zhang et al. (2021) also holds:
27

---

Published as a conference paper at ICLR 2023
Lemma 26 (Analog of Lemma 17 from Zhang al. (2021)). Let (=)) be sequence zero-mean Gaussian random variables such that n. is a stopping time finite a.s. Then for all å E (0, 1).
Pr
x²
Σ of
where of is the variance of X
Then consider their Elliptical Potential Counting Lemma (Kim et al., 2021, Lemma 5), which holds as long as || la I 1. In our setting, we indeed have this property as E B" (only the noises can be unbounded, instead of actions). Hence, this lemma still holds.
Proposition 27 (Kim et al. (2021, Lemma 5)). Let 21, T2,,.....
................................ E Rd be such that [arallz S 1 for
all E [k]. Let V2 AI Einree! Let J {i [1:
||:0 11 1
2 q), then
2d
In(1 + q) 1)
2/e
J
In 1+
In(1 +
Then consider the confidence set construction:
θ
n
θ e
Σ
Σ
(24)
e=1
where (0) = 1 (0) (c.(0))² 128m((12225)442//
O(Vd), L
max(1, [logz( (1 + }} and (I); ( [|] By using Lemma 25 together with their
original e-net coverage argument, we have 0" E O, for E (T) with high probability:
Lemma 28 (Analog of Lemma from Kim et al. (2021)). The good event & [Vi E T E happens with probability 1 8.
Similar to Kim et al. (2021), we define 0, be the maximizer of Eq. (22) in the f-th round and define
14: = 02 O*, We also consider the following good event
8T 8
& VI (T), Σ
(0000) <
ln
which happens with probability 8 due Lemma 26. Define
2
W Wc+-1(1== = x
Σ
1A
2.5.. T
Abbreviate Wr,s-1(Pe) as W1.--1, then we have the following lemma, which is slightly different from the original one, whose proof will be presented later.
Lemma 29 (Analog of Lemma from Kim al. (2021)). Conditioning on E, and setting 1, we have
1. ||ed Ileel/ S CC2- (/2-1/AA--- 1) for some absolute constant C₁ where A, A Et n/
For all S we have [|pellW.... C,2 (VA-14
3. There exists absolute constant C2 such that Tif4 < C21l=T1e (VAc-1C+))
Therefore, as we have the same ε,, Lemma 5 and similar Lemma 4 (which uses n, instead of as),
we can conclude that
T-1 ne +
T-1 Σ s=1
(1+
R.. <
Σ #=1
d
I+C
+
28

---

Published as a conference paper at ICLR 2023
n log 1 x + de log 1
Ō d
8
as in Kim al. (2021, Theorem 2) (recall that O(Vd)). Conditioning on Eg, we then further have
R2 5
d
Σ
o log 1 + dl log g
claimed.
Proof of Lemma 29. By definition and abbreviating (-), as (-), we have
| 2
c p1) Σ (xT 12 + -zx
[x) (c())) + cx()))
(2 (0))
WV
c (1) 22 22xI
(x] 144 2c2(0*)
8=1
(4) 2 2x
73
==1
2
2 (c)))((())) +
2 2 8811 1-2 + 2
Σ TEC
=
where (a) used (0)) = (r. - x2, (o. 0:) + +00)) S 2(x + 26 and (b) used
(0*) = n/. By the self-bounding property Lemma 37, we have
|pellli 1-21 S 16
Σ
03 + 81,
which means ||pel < 4A + 16 Σ'= 0. St. Setting À = 1 gives the first conclusion. Based on this, the second and third conclusion directly follow according to Kim et al. (2021).
G.3 EXTENSION TO UNKNOWN VARIANCE CASES
Based on Proposition 4, we then show that, our regret estimation Ry Eq. (20) is indeed pessimistic (i.e., Lemma 23).
Proof of Lemma 23. From Lemma 15 with 1, with probability we will have (recall the assumption that of < 1 for all t (T)
Σ (rk (IK,8"))2 = Σ
Σ (Tk
(x 3))² + 2 In sg2 + 2.
m
<
k=
k=
29

---

Published as a conference paper at ICLR 2023
Therefore have
R₂d
2.5
In -
5² In 8
1=1
C
82.5
Σ (rk (Tk, B/)2 + 2s In
n
+
In
1
+
8²
In
1
s62
8
8
A=1
1 + 2
1
1
1 0
C
g
(rk (Ix, 3))² In
2 In
In
+
1.5
In
+
2
In
Rτ.
8
s02
0
8
In other words, our R is an over-estimation of R7 with probability 1 1 8.
H OMITTED PROOF IN SECTION 4.2 (ANALYSIS OF WEIGHTED OFUL)
H.1 PROOF MAIN THEOREM
Similar the VOFUL2 algorithm, we still assume Proposition 6 indeed holds and defer the discussions to the next section. We restate the regret guarantee of Weighted OFUL (Zhou et al., 2021), namely Theorem 7, for the case of reading, follows:
Theorem 30 (Regret of Algorithm with Weighted OFUL in Variinee Case). Consider Algorithm I with F We i ihhted CFUL. (Zhou al., 2021) and R
RS. a c
( sn
Vn
+
of In 8 Σ
The algorithum ensures the following regret bound with probability 1 5:
RT = = (10
1 1 3..5.TT TTVoo log g
Σ
of
log
Proof. Firstly, from Proposition 6, the condition of applying Theorem 16 holds. Therefore, we have
T
1 + a log 1 8 of
R4 S svd,
Σ
log J
For Rg, similar Appendix we decompose it into two parts: those from and from outside of S.
The former case is bounded by Proposition 6, as
Regret from S with gap threshold A SCC
V sng In
In
Σ of In
3
1
LETS
For those outside we will bound O(sn ) where we only need to bound n² From Line of Algorithm 1, we have
15
C
1 s(n'
11)mm
Σ
Σ of
A
LET5
30

---

Published as a conference paper at ICLR 2023
By the "self beeff-bounding" property that + by implies O(a + b²) (Lemma 37), have
n
1
Σ
of In
1
A
A
KET
Therefore, we can conclude that (the regret from S dominated)
RS S
Σ O
x²
log
+
Σ
of log 1 + +17
A
A=2 2
IETS
where the last term is simply bounded by (ss). Again from Line 5 of Algorithm we will have the following property for all A + Ay:
C' A
Vin
8813 In
+
Σ of ln
(25)
IETS
We first bound the second term, which basically follow the summation technique (Eq. (15)) that we used Appendices and G.I:
Σ Cs
Σ LETS
of
In 1 5
Vlgg
X
Σ #2A2Ax IET3
1 11 In C2
Σ Ax>A>A,
Cs
Σ
of
ln
A
A#A,
IETS
where X is defined as
X= /
Σ
Σ
C In
SHA,IETS
and Ax 2 -ooo x1, which means 4
X Hence, we will have (the second summation will be
bounded by x Es n T)
T
Σ Cs A#A,
Σ
of In 5
Σ A 1ET3
Σ
C282 log z
=
o
2
log
BETS
1=1
Hence, for the second term, we have
T log
2
Σ
af
1
log
T
=
s²
Σ
of
log 1 8
At last, we consider the first term. From the same lower bound of n² (Eq. (25)), we will have
C
1
C
1
sng In
na
14 s
A
5
By the fact that EayA, n < T. we will have
T2 C2s 1
Σ
===
A#A,
Henceforth,
O 2 log
Σ
13
- =0
s2log
82
- )
1
<0
8 log
g
1
s In _
T
=
(1.5.
T
1
A=2-2
31

---

Published as a conference paper at ICLR 2023
Algorithm 4 Weighted OFUL Algorithm (Zhou et al., 2021)
1: Intialize Ag AI, co 0, 0o Ab cp. 3 0 and On 10 1110 0oll S 3 + vAB}.
2: fort= = 1, .,, do
3: Compute the action for the t-th round as
It argmax max (æ, 0).
(26)
=EA 8E
4: Observe reward = (Iz, 8*) + and variance information of, set J. max max(1/Vd,o0h
confidence radius 3e
B. 8 8 dln 1+
t
In
412
(27)
dA min,
8
where min,t - minn....... J..
5: Calculate A, A 2 /o t a-1 + mat/ol O2 t Ar and θ +- {0)
|| BellA, S B. + VXB}.
Combining all above together gives
T
T
Rr R2- + R2. S O
1.5
Tog
+ 8²
2 log +
+
sVd,
o log σ + s logg
t=1
1
+ s / log 1
s Ō
(s² (
Σ
of
log
8
8
as claimed.
H.2 REGRET OVER-ESTIMATION
We again briefly argue that Proposition 6 holds under our noise model. We present their algorithm in Algorithm 4.
Proposition 31. With probability at least dimensions guarantees
8, Weighted OFUL executed for T steps d
T
RS. SC V 5 +
Σ of log
where C' = Ö(1), T is stopping time finite a.s., and of oz...., of are the variances of M, :?..
Proof Sketch. We mainly follow the original proof by Zhou et al. (2021) and highlight the differences. We first highlight their Bernstein Inequality for vector-valued martingales also holds under our assumptions, as:
Lemma 32 (Analog of Theorem 4.1 from Zhou et al. (2021)). Let { be sequence of d-
dimensional random vectoes such that | < L. Let {m. be sequence of independent, symmetric and - random variables. Let rt = (0))))) + for all E [ri], Set
Z, = Al + Et= Zz be = Et= ToTa and 02 = Z, by. Let n be stopping time finite a.s. Then,
VO (0,1). 1).
Pr
Σ IoNe s=1
< B.., 8- 12. - B + VAll0 Vt, [n]]
21 21-8.
z,1
32

---

Published as a conference paper at ICLR 2023
where B.
AL2 dA In 812 5 =80 (ddnnnn111 +
80
The proof, which will be presented later, mainly follows from the idea of their proof of Theorem 4.1, except that using Proposition 11. Check the proof below for more details about this.
With this theorem, we can consequently conclude that the confidence construction is indeed valid by applying Lemma 32 to the sequence (n/ooehe which gives
10. 0 11 S B4 Vx100112 - B
VI (T),
with probability 1 6,
where Be 8v /ddn(11 + dxo In 4t as defined in Eq. (27). Therefore, conclude their (B.19) from exactly the same argument, namely
RS. S
min {1 (1. /
Similar to their proof, define I₁ ft E [T]
/ A,2 2 1]
and In = [T] I1, then we have
(where min is the abbreviation of min,,
min T
s=1 σ.)
T
T
mine
min
|
2dIn 1+
rEZ
min
where the last step Proposition 34 and the fact that ||ze//eel2 S minn Therefore, are having the same Eq. (B.21) as theirs, which gives
RJ S
222
2dln
1+
T
Σ ( + vxYao + 4dIn (1+
T
doo min
d
min
By the choice of o. = max(1/ Vd, or) and A = 1, we have
In 1 7) = 5(1)
In 1
aoo
and that
T +1 B, + V o (VCLOSTTO8
= o (Vales
which gives
T
T Σ
RJ = δ d
0 log
=
+ of
log
=ō
1 dTloo
+ d
Σ t=1
of log 1 g
as claimed, while the second step uses क: min
1 of} < 1 + 07.
Proof of Lemma 32. Their original proof mainly use the following two auxiliary results: The first one the well-known Freedman inequality (Freedman, 1975), which is originally for bounded martingale
difference sequences, while the second one Lemma from Abbasi- Yadkori et al. (2011). For the
former one, from its variant for Gau-Gan random variables (Proposition 11), we have:
33

---

Published as a conference paper at ICLR 2023
Corollary 33. Suppose that {5:] is sequence of zero-mean random variables where &
subG(o?) for some sequence {0t) Let n be a stopping time finite a.s. Then for all œ, v > 0 and À >>0 0,
h V3
Pr 31 kisksn n: Σ
E
v²
S exp
x²
2v2
==1
Moreover, for any 8 (0, 1), with probability
8, we have
E 1=1
Σ 8
o In
Proof. The first conclusion is done by applying Proposition 11 optimally with f(A) 12², V; = of
and x pz. The second conclusion is consequently proved by taking v² - of and
20 In 5-
For their second auxiliary lemma (Abbasi- Yadkori et al., 2011, 1, Lemma 11), one can see that the original lemma indeed holds for sub-Gaussian random variables. Therefore, we still have the following lemma:
Proposition 34 (Abbasi-Yadkori al. (2011, Lemma I1)), Let (at)²=1 be a sequence I& and
define V = AI + E. F. for some X > 0. Then, if we have ||æa||2 S for all E [T), then
Σ min {1, 11.10a1l
2 2og det(VV) det(AI)
dd TT.
S 2d
dA
Recall the definition that A
a.ae E
Further define d,
Σ E==1 Telli w || | 2,-
and let & be the event that ||dallz=1 B. for all 8 S L. They proved the following lemma, which still applies to our case:
Lemma 35 (Analog of Lemma B.3 from Zhou et al. (2021)). With probability 2. with the definitions of s4 and b)t in Lemma 32, the following inequality holds for all 1:
2n _ Z- d 1 w
3 < B
1
apply Freedman's inequality l, A 14 1[E.-1]. It is obvious that Eie, F.-1] Moreover, from the following in- equality (which their Eq. (B.3))
Proof. We only need to verify whether ",
2||=allz_1
2w,,
e.l 1 + w
||d 11, 1[8.-11
B,- < min(1, 2ww;1,2w; B
+ w/
and the fact that 77s Denote the sub-Gaussian parameter as o. for simplicity. We have
F.-1 subG(a²), )) we have L, F.-1 SubG min (1, 2w. )))
tL? dA
Eo 32 [min (1, 40 8
min 11 wo} s S0 dd [+
where the first inequality is due the non-decreasing property of {B,} and the last one is due to Proposition 34. Therefore, from our Freedman's 's inequality (Corollary 33), we can conclude that with probability 5/(4t?).
11,2)
812
Σ l. 5 2
Σ
S0 Bdl (+
In
d)
34

---

Published as a conference paper at ICLR 2023
Bi + 160
tI.2
8t
3 t-
$ 2
11
5
dd
8
4
Taking union bound over and make use of the fact that Σt=1
completes the proof.
We also have the following lemma: Lemma 36 (Analog of Lemma B.4 from Zhou et al. (2021)). Under the same conditions as the previous lemma, with probability 1 - 2. will have the following for all 2 simaltaneously:
2 w
1
4 Br.
1+
Proof.
We still need to apply our Freedman's 's inequality (Corollary 33) to
n 11
n/ u
E
w
As 17s Fa-1 ~ sa" n F. is sub- sub-exponential random variable (Proposition 12) such that
1
E [exp(( E(n))) F-.1] S exp(16X80"), 1/lA <
4G
which consequently means
E (exx((Xc)))=-1l exp
(1,,2))3)) l/ S
4
where the second step used the fact that 1+ S min(1, we} as we used in the proof of Lemma 35. Again by Proposition 34, we can conclude that
tL?
Σ of (min 20 1+
dd
Then, as we did in the proof of Theorem 13, we will apply Proposition 11 to the martingale difference sequence {L.)-- with Vg o (min (1, w f() 16X² for X 46 and f(A) otherwise. Then for all x, and (0, ) we have
Pr
Σ (min w2})² s < exp (-λx Ae + 1622
Picking x² E'm (mmnn ([, and 2v In 2 gives
2
x²
5
Pr
2
of (min w2})² In
S exp
32
where À is set to 320 2.
Hence, with probability 1 -
8
indeed have
412
1L2
812
Σ
4654 2 (min 2 s 8/
20
[+
In
dA
Moreover, due Proposition 34, have
E
12 2
Fo
<
0
w²
< 202dl
1+
tL?
1
dA
s=1
35

---

Published as a conference paper at ICLR 2023
which means, as It
S lx
El
Blitw?]
u
(1+
11.2
(1+
11.
812
1
20
+ 8
20
In
S
w
dd
dd
4
Taking union bound over all and again making of the fact that E 21=1 conclusion.
t- < 2 gives
Therefore, as long as their Lemmas B.3 and B.4 still hold, we can conclude exactly the same conclusion from their derivation. One may refer to their proof for the details.
I AUXILLIARY LEMMAS
Lemma 37 (Self Bounding Inequality, Efroni et al. (2020, Lemma 38)), Ler & x S a + b/I where a, b, x 2 then we have
x S 4a + 263.
Proof.
As - b - a S O, we have
b
b
Vā S + 4
+ 4a
+
4a
b 2
2
from the fact that va+bs va + vb. As V 2 0, we have
r $ (b 2/ - 26 + 4a
due to the relation that (a + b)2 < 2a 2 + 212.
36


Reviews:
[{"review_id": "pTfbvrBHb3u", "reviewer": "Reviewer_DQpC", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a variance-aware framework for stochastic sparse linear bandit problems.  The performance (as captured by regret bounds) bridges the general stochastic reward setting and the deterministic reward setting, which can be efficiently solved by a divide-and-conquer method.  The proposed framework employs variance-aware linear bandit methods (i.e. methods that did not assume or exploit sparsity of the coefficient vector), using repeated ‘explore’ steps and ‘commit’ steps with a adapting threshold.  The authors prove regret bounds using two example variance-aware linear bandit methods as sub-routines and achieve ambient dimension free bounds for the deterministic case.", "summary_of_the_review": "The problem is novel (though related to studied problems), the approach extends strategies (explore-then-commit for sparse linear bandits; variance-aware linear bandit methods) in a non-trivial manner.  The paper is well-written.", "strength_and_weaknesses": "Strengths\n- The authors show that variance-aware methods for linear bandits can be adapted variance-aware methods in the sparse linear bandit setting.  \n- While the authors employ standard explore-then-commit style approach in identifying large coefficients for sparse linear bandits, for the variance aware setting the authors use loop over explore-then-commit steps adaptively changing the threshold.\n- The presentation and writing were mostly clear and easy to follow.\n\nWeaknesses\n- (minor) Some experiments (even for a few toy samples) could help clarify whether empirically (a) the variance-aware linear bandit methods perform poorly in sparse settings compared to the proposed framework’s adaptation of those methods, (b) whether the dependence on $s$ in the bound is tight (i.e. would a new algorithm be needed or possibly just an alternative proof), and (c) if the empirical regret incurred by the proposed framework when actually applied to (nearly) deterministic settings is close to what could be achieved by a divide-and-conquer method designed specifically for the deterministic setting.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "_xovabu8dc", "reviewer": "Reviewer_babC", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper provides a black-box conversion from variance-aware linear bandit algorithm to its corresponding variance-aware sparse linear bandit algorithm. The regret framework is applied to two recent algorithms and obtain quite compelling regret bounds.", "summary_of_the_review": "Overall, a good theoretical paper for providing new algorithms for the variance-aware sparse linear bandits and would be of great interest to the community.", "strength_and_weaknesses": "\n   Pros:\n\n   (A) The generic formulation uses gap-dependent rounds split into commit and explore rounds to delicately balance exploration while minimizing the resulting regret. The resulting regret terms are almost tight except for a square root sparsity (s) factor which is typically small in practice.\n   (B) Quite a few state-of-the-art algorithms such as VOFUL2 and Weighted OFUL are considered in the framework and their regret are rigorously derived for both the\nframework and the corresponding algorithm components.\n\nCons:\n\n   (i) Experiments show-casing the proposed regret bounds on datasets would have made the paper much more compelling.\n   (ii) As noted in the paper, there is still a gap with respect to the lower bounds and the obtained bounds.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "NnBPOAzRNM", "reviewer": "Reviewer_MSEd", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes the first variance aware algorithms for sparse linear bandits, which interpolates between the $\\sqrt{dT}$ bound in worst case when variances are constant, and the bound independent of $d$ in the deterministic case where variances are 0.\nThe authors achieved this by an explore-then-commit framework that can be applied to existing variance-aware linear bandit algorithms, and showed that by plugging in VOFUL, it can match the regret lower bound for the worse case by a factor of $\\sqrt{s}$, and attain regret upper bound $O(s^3)$ in the deterministic case, i.e., removed the dependence on d and T.", "summary_of_the_review": "Variance aware algorithm for sparse linear bandit algorithm is well-motivated, and this paper provides the first solution via a explore-then-commit framework that converts existing variance aware algorithm to the sparse setting. However, there is still an $O(\\sqrt{s})$ gap to the regret lower bound in the worst case, and it is not very clear to me whether this gap can be closed under the current framework.", "strength_and_weaknesses": "Strength\n\nThe idea of extending variance-aware algorithm to sparse linear bandit is well-motivated.\nThe proposed techniques to make explore-then-commit framework to work when the desired regret is unknown (as the regret for variance-aware algorithms depends on the variances, which are unknown) may are intuitive and technically interesting.\n\nWeakness\n\n1. The description in Section 3.1 can be further improved. Its current form is a bit hard to follow, e.g., maybe first define what is arm $i$ in the first paragraph on page 6.\n\n2. I would appreciate it if the authors can provide more explanations about the fundamental reasons for requiring action set to be unit sphere for all time steps, while Abbassi et. al. (2012) does not? It seems footnote 3 only provides an extreme case, where $\\Omega(d)$ is unavoidable, i.e., unit sphere is only a sufficient condition to help avoid this. Is it possible to further relax this action set assumption, and allow for drifting action set?\n\n3. The authors mentioned the data-poor regimes where $d>>T$ is beyond the scope of this paper. Can the authors elaborate on what are the possible difficulties in this case, and the reason why the proposed framework does not apply?\n\n4. The authors mentioned the $O(\\sqrt{s})$ gap to the regret lower bound can be improved if better variance aware linear bandit algorithm exists. Can the author provide more justification for this, e.g. why this is due to the sub-optimality of the adopted variance aware linear bandit algorithm, instead of the proposed explore-then-commit framework. And is it possible to derive a regret for the proposed framework (in variance aware sparse bandit), that depends on the regret of the adopted variance aware linear bandit, so that, it directly shows with an optimal variance aware linear bandit, the proposed framework is able to close the $O(\\sqrt{s})$ gap?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Hl8a6Qbi_Bx", "reviewer": "Reviewer_br26", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studied sparse linear bandits with noise variance appearing in the regret bound.", "summary_of_the_review": "Although a new prospective for sparse linear bandits is proposed, the improved regime is less interesting. A lower bound to fully characterize the problem is missing.", "strength_and_weaknesses": "It is interesting to study sparse linear bandits from variance-aware prospective. However, I feel the regime that variance-aware algorithm can improve for sparse linear bandits is not sufficiently interesting. For the current regret bound, it will be dimension-free only for the deterministic case (sigma=0) or nearly deterministic case (sigma=1/sqrt{d}). Sparse linear models or bandits are motivated by the use of high-dimensional features so d is typically very large. The requirement for sigma=1/sqrt{d} is very restricted and does not match any practical application. Thus, the novelty beyond variance-aware linear bandits is limited.\n \nSecond, I feel a variance-aware or problem-dependent lower bound is missing. I would like to see how this problem depends on noise-variance fundamentally. Existing minimax lower bound cannot explain this. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster