Noise-Adaptive Thompson Sampling for Linear Contextual Bandits
Authors: Ruitu Xu
Yifei Min
Tianhao Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: Linear Contextual Bandit
Thompson Sampling
Noise-Adaptive

Abstract: Linear contextual bandits represent a fundamental class of models with numerous real-world applications, and it is critical to develop algorithms that can effectively manage noise with unknown variance, ensuring provable guarantees for both worst-case constant-variance noise and deterministic reward scenarios. In this paper, we study linear contextual bandits with heteroscedastic noise and propose the first noise-adaptive Thompson sampling-style algorithm that achieves a variance-dependent regret upper bound of $\widetilde O\Big(d^{3/2} + d^{3/2} \sqrt{\sum_{t=1}^T \sigma_t^2}\Big)$, where $d$ is the dimension of the context vectors and $\sigma_t^2$ is the variance of the reward in round $t$. This recovers the existing $\widetilde O(d^{3/2}\sqrt{T})$ regret guarantee in the constant-variance regime and further improves to $\widetilde O(d^{3/2})$ in the deterministic regime, thus achieving a smooth interpolation in between. Our approach utilizes a stratified sampling procedure to overcome the too-conservative optimism in the linear Thompson sampling algorithm for linear contextual bandits.

Noise-Adaptive Thompson Sampling for Linear Contextual Bandits
Ruitu Xu
Yifei Min
Department of Statistics and Data Science Yale University
Department of Statistics and Data Science Yale University
New Haven, CT 06511 ruitu. xw@yale...l........oo edu
New Haven, CT 06511 yifei wwwmmmiineele.eemmmmmm
Tianhao Wang
Department of Statistics and Data Science Yale University
New Haven, CT 06511 tianhao. wang@yale.ce edu
Abstract
Linear contextual bandits represent a fundamental class of models with numer- real-world applications, and it is critical developing algorithms that effectively manage noise with unknown variance, ensuring provable guarantees for both worst-case constant-variance noise and deterministic reward scenarios. In this paper. we study linear contextual bandits with heteroscedastic noise and propose the first noise-adaptive Thompson sampling-style algorithm that achieves a
variance-dependent regret upper bound δ + ET= o?) where d is the dimension of the context vectors and of is the variance the reward in round f. This recovers the existing (d2/22 /T) regret guarantee in the constant-variance regime and further improves to (d8/22 in the deterministic regime, thus achieving a smooth interpolation in between. Our approach utilizes stratified sampling procedure overcome the too-conservative optimism in the linear Thompson sampling algorithm for linear contextual bandits.
Introduction
Linear contextual bandits represent natural extension of multi-armed bandit problems (Auer et al., 2002a; Robbins, 1952; Lai et al., 1985), where the reward of each arm is assumed to be linear function of the contextual information associated with the arm. Such problems manifest in numerous real-world applications, encompassing online advertising (Wu et al., 2016), recommendation sys- tems (Deshpande and Montanari, 2012), and personalized medicine (Varatharajah and Berry, 2022; Lu et al., 2021). A multitude of algorithms have been proposed, tailored to diverse settings within domain linear contextual bandits (Auer et al., 2002b; Abe et al., 2003). Notably, two main streams of approaches address the iiloraationexploitttti have emerged: Upper Confidence Bound (UCB) (Chu et al., 2011; Abbasi- Yadkori et al., 201 I) and Thompson sampling (TS) (Agrawal and Goyal, 2013; Abeille and Lazaric, 2017). In practical scenarios, the varying and non cen-transparent noise variance inherent each reward is common phc- nomenon (Towse et al., 2015; Omari al., 2018: Somu et al., 2018; Cheng and Kleijnen, 1999). Such noise, which may exhibit heteroscedasticity and correlation with the context, can significantly impact algorithm performance, particularly when the variance of the noise is unknown priori (Kirschner
dilemma in linear contextual bandits
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

and Krause, 2018; Zhao et al., 2022). Thus, is imperative to develop adaptive algorithms capable of handling noise with unknown heteroscedastic variance, ensuring provable guarantees when operating with both constant-varianee noise and deterministic reward scenarios. Recently, few variance-aware UCB algorithms have been proposed for linear bandits. In particular, Zhou et al. (2021) examined the scenario where the variance is known and observed after each arm pull, while Zhang et al. (2021); Kim et al. (2022b); Zhao et al. (2023) explored the unknown variance case. Nevertheless, there is a scarcity of results concerning TS algorithms in this context.
Thompson Sampling (Thompson, 1933), a notable Bayesian approach, provides a computationally efficient means of addressing the exploattion-explotaaiiie trade-off (Rusmevichientong and Tsitsiklis, 2010; Chapelle and Li, 2011) 1). This method applies posterior sampling to generate parameter estimator for arm selection, thereby naturally balancing exploration and exploitation by selecting arms with high expected rewards and those with substantial uncertainty (Russo et al., 2018; Riquelme et al., 2018). In the existing literature, the regret upper bound for the linear TS algorithm for linear contextual bandits is of order ((d8/3/T) (Agrawal and Goyal, 2013; Abeille and Lazaric, 2017), and the existing algorithm cannot adapt to higher-order structure of the noise.
As an initial endeavor to incorporate variance information into TS Tyysyyle algorithmic design for linear bandits, we adopt a weighted ridge regression approach to construct TS algorithm, LinVDTS, detailed in Algorithm 2. This algorithm achieves variance-dependent performance guarantee the expected regret, as demonstrated in Theorem 4. Nonetheless, a technical barrier intrinsic to TS-style algorithms, yet absent in UCB, emerges during this naive integration of weighted regression with TS. Specifically, the issue stems from inadequate control over the aariance-adjusted norm of unselected context vectors at each step, necessitating anti-concentration argument that only allows for a Seltance-dependedd upper bound on the expected regret and precludes the acquisition of a high-probability guarantee that is simultaneously variance-dependent. More discussion this will be given in Section 4.2.
In bid to navigate this intricate issue and exert explicit uncertainty control, we further propose novel noise-adaptive TS variant in Algorithm 3. Our algorithmic design features (I) an uncertainty stratification scheme applied to contextual vectors, providing explicit regulation of the uncertainty quantification, (2) a cascading construction process for the feasible set, which, in tandem with the stratification scheme, operates to filter out unlikely arms, thereby eliminating the requirement for the nati-concentration argument in the analysis, and (3) the use of noise- adaptive confidence radii to direct the sampling procedure, thereby ensuring a more constricted variance- deeenddddddddeeettt regret. The theoretical analysis yields a high- probabiitty regret bound that interpolates smoothly between the constant-variance and deterministic reward regimes.
Main contributions.
The main contributions of our paper are summarized in three key aspects.
We introduce a simple and efficient TS-style algorithm, named LinVDTS (Algorithm 2), that can utilize variance information for linear contextual bandits. We prove that the expected regret of 5(
LinVDTS is bounded by δ (d [1+ (1+V - , ) where d is the ambient dimension and of is the variance of the noise in round f. We also prove that, with high probability, the regret of LinVDTS VE= +VT). In the analysis of LinVDTS, identify the inherent difficulty of controlling the uncertainty induced by posterior sampling, which precludes a high- nigh-prrobbbiity guarantee that is aware of the noise variance.
is bounded by δ [2//2
We devise a stratified sampling procedure that fulfills more efficient exploration for linear con- textual bandits by exerting explicit uncertainty control over the context vectors. Based on this framework, we propose L LinNATS (Algorithm 3), a noise-adaptive variant of linear TS. To the best of our knowledge, this the first noise-adaptive TS algorithm for linear contextual bandits with heteroscedastic noise.
We prove that LinNATS enjoys a high- probbabbbbbiy regret bound of order 0(8/2 (10)2(++///) (1 under standard assumptions for linear contextual bandits with heteroscedastic noise. This improves over the existing ((33/2 (T) (T) regret bound for linear Thompson sampling (Agrawal and Goyal, 2013; Abeille and Lazaric, 2017), especially when the noise variance diminishes. Our analysis bypasses the standard anti-comeentration argument thanks to the stratification framework.
2

---

Notation. For any n E N we denote [n] (Z1....,Zn). We write scalars in normal font while representing vectors and matrices in bold font. For any vector x and positive semi-definite matrix E, we define ||x||> || For two functions f and defined on N+, we use [(n S g(n) to indicate that there exists a universal constant > 0 such that f(n) S C g(()) for all E X: f(n) Z g(n) is defined analogously. We use f()) x g(n) to imply that both f'(n) S g(n) and f(n) 2 g(n) hold true. We use O()) to hide
:= I=]
f1.2...., and Fi:n is shorthand for the set
constant factors and (-) to further hide poly-logarithmic terms.
Related work
Heteroscedastic linear bandits. The challenge of heteroscedastic noise in linear bandits has been studied through a multitude of perspectives: In particular, Kirschner and Krause (2018) studied linear bandits with heteroscedastic noise via the approach of iiformation-dirctteo sampling. Dai et al. (2022) examined heteroscedastic sparse linear bandits and demonstrated versatile framework capable of transforming any heteroscedastic linear bandit algorithm into an algorithm tailored for heteroscedastic sparse linear bandits. Building on the UCB approach, Zhou et al. (2021) developed an adaptive algorithm that handles anown-varianee noise, providing performance guarantees of
o VVVT + dv E of). Zhang et al. (2021) introduced a variance-aware confidence set using elimination with peeling and proved regret bound of ① (poly(d) 1 Ei=1 Kim al. (2022b) further refined this upper bound to 5( ( d3/2, E of) for linear bandits. Zhao et al. (2022) proposed multi-layered design for UCB algorithm that achieves a 0 Ō l)
dv Ei regret. More recently, Zhao et al. (2023) proposed a UCB-style algorithm with unified regret upper bound of 0(d + dv dv ET= o?) where the guarantee is facilitated by the introduction of a novel Freedman-type concentration inequality for self-normalized martingales.
Thompson sampling. TS as a method to address the opploration-explotaattie trade-off has gained significant attention in recent years due its simplicity, adaptability, and robust empirical perfor- mance (Chapelle and Li, 2011; Gopalan et al., 2014; Kandasamy et al., 2018). Its effectiveness has been demonstrated across various scenarios (Russo al., 2018), and in particular, multitude of theoretical results have been solidified within multi-armed bandit settings (May et al., 2012; Kaufmann et al., 2012 20 Korda al., 2013; Russo and Van Roy, 2016). For linear contextual bandits, Agrawal and Goyal (2013) provided the first proof for the (d3/22 regret of linear TS, and later Abeille and Lazaric (2017) delivered an alternate proof and further extended the analysis to more general linear problems. Notably, Hamidi and Bayati (2020) showed that the (dd3/2 rate cannot be improved in worse-case scenarios. While under additional assumptions such as regularity of the contexts, better rates can be achieved (Hamidi and Bayati, 2020; Kim et al., 2021, 2022a).
Morcover, Zhang (2022) introduced a modified version called Feel-Good TS, which is more aggressive in exploring new actions and achieves an O(d/T) regret. Recently, Luo and Bayati (2023) also approach, enabling the establishment of a minimax optimal regret of order O(dvT) for the TS algorithm. Xu et al. (2022) proposed a Langevin Monte Carlo TS algorithm that samples from the posterior distribution beyond Laplacian approximation. Investigations have also been undertaken into TS for kernelized bandits (Chowdhury and Gopalan, 2017) as well as integration of TS with neural networks (Wang and Zhou, 2020; Zhang et al., 2020). Recently, Saha and Kveton (2023) proposed a variance-aware TS algorithm on the topic of Bayesian bandits with a crriance-dependen upper bound on its Bayesian regret. As far as awareness extends, no existing results address coise-adaptive TS algorithms in the context of linear bandits.
proposed a geometry-
3 Preliminaries
In this section, we introduce the fundamental framework for contextual linear bandits. We also provide concise overview of the linear TS algorithm, which functions our benchmark methodology.
3

---

Algorithm Linear Thompson Sampling
1: for / l,...,T'd do
2: Sample 0 from N(O,, V
3: Select arm X, &- arg max xex, (x, 075) and observe reward Ft
4: end for
3.1 Linear contextual bandits
We investigate linear contextual bandit problem with heteroscedastic noise. Let T be the total number of bandit selection rounds and let d be the ambient dimension. In each round t E [T]. the environment generates an arbitrary set of context vectors X, S R&, potentially even in an adversarial manner, where each x E X, denotes the context vector of a feasible action. Upon observing the decision set X,, the agent selects a context vector X E Xg, and then receives reward rt from the environment. In particular, here the reward is a linear function of the selected context further corrupted by noise, i.e.,
x 0 t
where 0* E Rd represents the true model parameter and e, is the stochastic noise. In this paper, we impose standard assumptions the linear contextual bandit model, which common in literature.
Assumption 3.1. The ground truth satisfies ||0" ll2 I 1. For all t E [T] the decision set X, is contained in the unit ball. i.e., ||x|| < 1 for all x E Xg. There exists constant R 0 such that |eel & for E [T'] For every E [2]. Ble, X1:t: = 0 and Ble? X1st = o?"
In each round 1, an algorithm selects an arm x = arg maxx x x As a result, the suboptimality the selected arm time can be expressed as A, = x; T0" x " The objective of the agent is to minimize the cumulative regret incurred over the time horizon T, which is defined as
X2, and we denote the optimal arm as x; i.e.,
R(T) = Σ 1=1 A.
-
A.
Σ
(x) Xx,
-x, 0")
3.2 Thompson sampling for linear contextual bandits
A standard TS algorithm for linear contextual bandits (ie.. Algorithm 1) was first proposed in Agrawal and Goyal (2013), employing Gaussian priors and likelihood functions the design. At each round / E [T). sample 0 is drawn from the Gaussian posterior distribution, centered at the estimate 0, V, E.=1 T.X, with covariance matrix 3 3², where V, L. Σ X,x and the confidence radius 3 = 3R, d (og( The arm x; is then selected against the sample 07S.
The main idea here is to achieve exploitation by updating the posterior using collected information, and the exploration among the arms performed naturally in posterior sampling. Agrawal and Goyal (2013) demonstrated that the algorithm presented in Algorithm achieves a regret bound of order (dd3/2/)) This bound is worse than the minimax lower bound by unavoidable factor of vd (Hamidi and Bayati, 2020). Despite this discrepancy, the regret bound effectively showcases the algorithm's 's ability to balance exploration and exploitation in the linear contextual bandit setting.
4 Warm up: a simple and variance-dependent Thompson sampling algorithm
In this section, we introduce a preliminary algorithm, LinVDTS, delineated Algorithm 2, which combines TS with weighted ridge regression estimator in straightforward manner. For the sake of clear exposition, we focus on a less complex linear bandit problem which the agent is privy to both the reward r, and its variance of subsequent the selection of arm.
4.1 Algorithmic design
In order to integrate variance information into the estimation process, the use of weighted regression has emerged prevalent approach in the field of variance-awar online learning (Zhou et al., 2021;

---

Algorithm 2 Linear Bariance-Dependee Thompson Sampling (LinVDTS)
Require: Total number of iterations 7,, number of total arms n
1: Initialize V1 +- AIa, +- 0, 0 <- 0, 31 t Vd, and Σ1 t V
2: for mert=,...... T do
3: Observe context vectors Xr
4: Draw 0 ~ N(O,, ..)
5: X₁ - arg max (x, 0
6:
Observe reward Ft and variance of
7:
Update Ve+1 V + X;X /
8: Update M++1 f- Ur tTxi
9: Update 0.+1 + Vi+1
Compute covariance matrix Σ141 < B14 Vi+1
11:
end for
Min et al., 202 2022a; Zhou and Gu, 2022; Yin et al., 2022; Zhao et al., 2023). This methodology intimately associated with the concept of the Best Linear Unbiased Estimator (BLUE), well- established statistical technique for achieving optimal linear estimation (Henderson, 1975).
Let us first explain the details of the proposed algorithm LinVDTS. In every round t, the algorithm computes estimate 0, of the ground truth 0 by solving weighted ridge regression problem:
0, arg min E
1 (r. (x., 0)) 21
Here o, represents a weight parameter and denotes a regularization constant. For each approxi- mation Or we stochastically draw 0 from Gaussian distribution with mean O, and covariance E, 3. V where V. AI Σ x,xX/ /o? is computed from previous context and reward pairs, and the confidence radius, Be, is chosen as
f2 log
72
R 72
t
72 a
B x V dlog
log
log
log
+ Vİ.
dda
Refer to (A.2) for detailed delineation of Be. For each context vector E Xg, we compute the estimated reward as (x, 0, and the algorithm outlined in Algorithm 2 then selects the arm that optimizes this estimated reward. Following the approach of Zhou and Gu (2022), we construct the weight parameter o, max(or, a, >||x, 1/2 V }. which is designed as the maximum among the variance, a constant a, and the uncertainty associated with the selected arm Xt. It ensures the formulation of tight confidence radius Br, guided by a Bernstein-type concentration inequality, cf Theorem I.
4.2 Regret guarantee and technical challenges
The theorem below establishes See Appendix A.3 for detailed proof.
upper bound on the expected regret of LinVDTS.
Theorem 4.1. Set parameters a L/VV,, =R+ RR//dt, X For any 8 E (0, 1), the expected regret of Algorithm 2 is upper bounded as follows:
E(R(T)) O 2// 1+
o8
log T 88
Further, holds with probability 1 that
R(T) = o 0 (1
1+ - of log + + TTlog 1
5

---

Remark 4.2. Choosing ò = 1/T, then we see that the expected regret of Algorithm 2 is bounded by Ei= T
(d8//2
1
of However, the high-probability regret bound of Algorithm is of order
6( 19/2
1
Et=100 of + vT). where the additional VT term fails to be variance-dependent.
Nonetheless, this regret bound already improves over the existing (dd/2 bound for linear Thompson sampling in the literature (Agrawal and Goyal, 2013; Abeille and Lazaric, 2017).
The limitation on the high-probability bound arises from a set of technical challenges that are implicit and inherent in the posterior sampling used in Algorithm 2. To illustrate this, we now provide an outline of the proof for Theorem 4. and then discuss the technical intricacies therein.
Proof sketch of Theorem 4. I. Let us denote A.(x) = (xt x, 0*) as the suboptimality of x E X,. We introduce the saturated set S(t) for round t as the ensemble of arms whose confidence radius is |x|lv, .) (Agrawal and Goyal, 2013). Then the suboptimality A, of the chosen context x, can decomposed as follows:
dwarfed by its suboptimality, i.e., S(t) = {x E X, Ax(x) > (2/dlog
A (x X,, 0²) (x
0" x
where the term x! arg min (t) v norm. Leveraging the concentration results delineated Lemmata A.2 and A.3 pertaining to 0, and 0 we have
| refers to the unsaturated arm that possesses the smallest
A S / log ((1xx/ 1xxllv;)).
(4.1)
For upper bound on the expected regret, anti-concentration argument (Lemma A.6) to relate ||x v- back to ||xllly". This yields
2 12
BIA, H /
(4.2)
where (Hi)22 represents a filtration of the information available up to the observation of the set of context vectors at each round. Then collecting the above inequality for all t E [T], together with an elliptical potential lemma, we get the desired upper bound for B(R(TT).
Next, for the high-probability regret bound, we decompose
R(T) Σ
X
(A, E[A HA)
(4.3)
where the first term corresponds to the expected regret bound. We control the second term using martingale concentration, which results in an additional /T term in the final regret bound.
Why cannot simultaneously achieve variance awareness and high-probabillty bound?
First, the optimism induced by the posterior sampling is too conservative. 1 A primary challenge in the analysis is to effectively control each suboptimality term A., of (4.1). is important to note that one key algorithmic design in UCB-type algorithms is the exact optimism from the UCB bonus
8 || which ensures (x;- O&) + 3 3||xx; ll, (Iz, 0,) + [|]xxellv=" However, for TS-style algorithms,, the absence of this exact optimism hinders our control over the term ||x; llv throughout all rounds & [T], i.e., standard decomposition of A, (x: x,, 0*) yields A, S (2/7logt
(2])x; |lv + ||x=| v ) in this case. As a result, standard analyses turn to methodologies that employ an nnti-concentration inequality on the sampling distribution (Agrawal and Goyal, 2013). This leads to the inequality ||x] y|v < ||x:lly;" with constant probability, thereby providing an
upper bound on the expected regret.
Second, in the conversion of the expected regret bound to a high-probability bound, we have no help from the noise variance information. One may wonder if it is possible to incorporate the
'This is also identified in Zhang (2022) as the source of suboptimal dependence on dimension in the regret bound for TS.

---

variance of A, - E|A, Xi] to get Bernstein type concentration result. However, the variance of - A does not necessarily conform to the noise variance, especially when the decision set X, is revealed adversarially. To see this, consider the following situation: Given 6,, the environment reveals decision set Li {x1, _ where X is orthogonal to 0.. Then small perturbation in f along the direction of x can cause the change of arm selection. This implies that small uncertainty of the posterior distribution along the direction of X1 will be amplified to constant variation of the selected arm x,. Therefore, general, we not have any delicate control of the variance of A. EJA, Ai). Consequently, we can only apply Azuma-Hoefföänn inequality to get
non non-noise-adee adaatiive term of ((VT). We discuss in the next section how to conquer this via more advanced algorithmic design.
5 General case: a noise-adaptive Thompson sampling algorithm
In this section, propose another TS algorithm LinNATS for linear contextual bandits, that is provably adaptive to unknown hetcroscedastic noise. For greater generality, we adopt the identical problem setting delincated in Section 3. and we refrain from assuming access the variance information (o (o associated with the rewards {re)=z-
5.1
Algorithm
The proposed algorithm LinNATS is displayed in Algorithm 3. Below we go through the details of LinNATS and explain the algorithmic design along the way.
Stratification over contextual uncertainty. For more efficient uncertainty control, adopt stratification strategy akin to that previously used for UCB-type algorithms (Chu et al., 2011; Li et al., 2023; Zhao et al., 2023). Our algorithm segments the context vectors each round t into I distinct layers, enabling the precise control of both |xx |x<l|v.' and |xx xll""."
Specifically, the ε-th layer establishes a threshold of 2- and retains a separate estimate o.,e e and sampled variable TTS for each E E [L] and E [T] (Line 3). Commencing from e = 1, sequence of decision sets X, = X2,1 2 X2,2 ... of diminishing sizes is derived by excluding the arms x e Xx,e that are less likely to maximize (x, 0*) at each layer More specifically, on Line 11 we let
Ke.t+1 = fxE Xi,e : (xx O 2
-fx
Ex,e
max (x,0
0 - 2- f+1 ex
( (V2dlog(4#L/8)) + 1)BueJ. (5.1)
which ensures that the optimal arm x falls into all decision sets with high probability. The context vector X₁ maxxex, (x, T is chosen if the uncertainty term ||x|vv; S a for all x e Xe,e (Line 8). Otherwise, x, is selected only when the uncertainty surpasses the threshold, i.e., | 2 2 for some E, and the elimination process (5.1) terminates (Line 13).
The round index i is incorporated into a growing index set Ve+1,e (Line 9 & 15), and the observation pair (x,, participates the later estimation of 0z.e for all > f only if the chosen arm exhibits large uncertainty within the current layer, i.e., ||x i 2 2 (Line 21). This process guarantees that every
context vector Xr,e, cascading through the first (e 1) layer, satisfies ||x|
S 2-(11
Parameter estimation with weighted ridge regression. To estimate 0-, we again utilize weighted ridge regression, but this time within each uncertainty level. For each layer & E [7.] and round E [T). the associated estimator Oz is given by
Put = arg min
E (r, (x,, 2 2--22111111 1010
DER
where the weight parameter we > 0 is selected to fulfill the condition || lv = - (Line 14). Owing to the specific formulation of the weighting parameter, it follows that supsew,, //,.xelly.i
2 - holds universally for all f e [T] and l E [4]. This allows the application of a Freedman-type
7

---

Algorithm 3 Linear Noise-Adaptiss Thompson Sampling (LinNATS)
Require: Time horizon T, number of arms n, and threshold a T /
1: Initialize 4- [1ga(1/a)], V1, + 2- la. Vi,e + 0, 01,e < 0. vi + and B1, t g-t
for all & E [L]
2: for = -1, 1,...,? do
3: Draw ,, ~ N(Or,, E1,e) for all & E [Z]
4: Observe context vectors X, = (x,, Xt,a)
5: Let + 1,, X,
6:
while is nor selected do
7:
|xlly, I a for all x Xx, then Choose X; arg max,axe (x, (g))) and observe reward r
8:
9:
Update V41,1'' + Veee for all 8 E [L] else ||x||= S for all x E Xx,e then
10:
Update Xt,441 following (5.1)
12:
else
13:
Choose any X Xx such that ||xellv,3 2- and observe reward v.
Compute w/ - 2-xe//l
15:
Update V Ve, {1} and V V1i. + Vie for all l' [4]
16:
end if
Update e 1+1+1 end while
18:
for E [Z] do
20:
if Ve+1,e F tre then
21:
Update V <- Vo + wi xxxx V4t1, + Vi,e + wfrixt
22:
Update 0 t- V Vi+,e
23:
Compute confidence radius B141 following Eq. (5.3)
Compute covariance matrix E Bi V
else
26:
V + Vi, V441 + Ve,. 0.+1. + Or B141, + Be, E4ti + Eee
end
28:
end for
29:
end for
concentration inequality to guarantee with high probability for all layer E [L]
that
-0.e-0'la 0'
R 26
L.ve woo?
E.
(5.2)
2
Variance--eependet confidence radius. The variance-deee dependent error bound (5.2) is sufficient for the formulation of a TS confidence radius, provided that the variance of is known. However, under scenarios where the variance is unknown, necessary to further estimate them adaptively and on the fly. Specifically, we estimate the summation of past weighted variances, represented E.ew,r uzo3. each using empirical estimator (r: (xx, 0(,))) as substitute for of. The weighted summation of these estimators Gr, E.ev, wā(r. (x,, 0.,))² effectively acts as precise estimator of E.ew,, wāo? (Zhao et al., 2023). Utilizing this estimator, we adjust the posterior distribution according to the following confidence radius
Br, -1----1 - (8G.. 61 log 8
8t2L
26+1 log
St2L
2--1 log
3R 8t2
(5.3)
2
where the variance estimator takes a slight variant for technical considerations:
Exew,, wg(r= (x,, 0,.))
if 2 64 (4llog(8tt1L/)
S1,
(5.4)
RZ
otherwisc.

---

5.2 Regret analysis
We provide the regret guarantee of Algorithm the following theorem. We also present a proof sketch of Theorem 5.1 emphasize the main idea. A complete proof is given in Appendix B.3.
Theorem 5.1. Set parameters a =T / and L = [[log(1/a]]] For any d E (0, 1), choose
the confidence radii (eL,) (E(L.) and the variance estimators { Meetr,eeen, according to (5.3) and (5.4) respectively. Then with probability at least 28. Algorithm 3 has regret guarantee
R(T) - (
E t=1 of log logT)
1 R+
Remark 5.2. Theorem 5.1 shows that proposed algorithm, LinNATS, delivers sariance-dependen regret guarantee free of any prior knowledge of the noise variance. The regret upper bound is also stipulated to be of the order ① /32/ scenarios where the variance is constant, our LinNATS algorithm recovers the regret guarantee of (() for linear TS (Agrawal and Goyal, 2013; Abeille and Lazaric, 2017), and in situations where the reward is deterministie, it attains regret guarantee of (dd3/3.. This highlights the versatility and adaptive performance our proposed algorithm across various environmental settings.
Ei=no considering R as constant. Notably, in
Next, we present the main ingredients of our analysis for Algorithm 3.
Proof sketch of Theorem 5.1. The choice of the weight parameters in LinNATS allows us to first apply a standard Freedman-type concentration argument (Theorem B.1), and deduce in Lemma B.2 that the estimator 0, is accurate up to a variance-dependent quantity 3r,::
1 00 0 1Vll,.. S BLE 2e E
E
wLo? log
L
R
log
L
1
2
6
2t-1"
However, 3, comprises the variance information { we which is unknown to the algorithm and thus cannot be employed in the construction of the TS process. Thanks to Lemma B.4, the sum of past weighted variances Exev,, wgz? can be upper-bounded by the empirical estimator G. defined in (5.4). Therefore, we can use St, as defined (5.3) for the confidence radius, and show that
10 - 0" lv.. S (v (V 2d log 41 L/6) + 1)
Then, by leveraging the stratified structure in conjunction with the cascading arm selection procedure across e E [L], we are equipped to exert uniform control over [|x|ly. r,f- for every x E Xy, in each instance of t 1T+ which resolves the technical challenge laid out in Section 4.2. Note that for
any context vector x E Xr,e, have ||x|v== 2-++1 and thus by Cauchy-Schwarz inequality
(xx, 0, 0*) < ||X|| 22 1
0" lVv...
< f+1 (ot 4t
1)3,.. (5.5)
Indeed, we ascertain in Lemma B.5 via an induction argument that for all t 2 and E [L], where Xe,e exists, x X,,e- Hence (5.5) holds for both x; and X, as consequence of the stratified structure. This allows us to execute the following decomposition of suboptimality for all / E VT
A (x/ O (x,, 0 025-1)
(x
0 0-) (x,, 0,5511 0*)
<0 by the definition of xs
controlled via (5.5)
2dd (
< 8 2-
1)
The main result is then obtained by collating the preceding inequalities for all [7.] followed by an elliptical potential inequality, taking into account that L O(log
G

---

Conclusion and future work
In this paper, aimed address the task of noise-adaptive learning on linear contextual bandits with indeterminate heteroscedastic variance. As part of our endeavor, we put forth a straightforward algorithm, LinVDTS, which assures a periance-dependen guarantee on the expected regret. Our analytical exploration reveals that a simplistic implementation of Thompson Sampling culminates in a sub-optimal regret bound, To mitigate this issue, we put forth an innovative Thompson Sampling algorithm, LinNATS. With the incorporation of stratification scheme, the algorithm successfully navigates the technical challenges of uncertainty control, securing a depanddet regret under unknown variance. Consequently, it effectively bridges the performance chasm between the worst-case scenarios involving constant variance and those concerning deterministic rewards.
Looking forward, it would be intriguing to conceive a noise-adaptive variant of the recently devised Feel-Good TS introduced by Zhang (2022), which enhances the dependency on the dimension d. Furthermore, extending the adise-ade methodology to TS algorithms designed for more general settings, e.g., generalized linear bandits and Reinforcement Learning with linear function approximation, constitutes an appealing direction for future research.
10

---

References
LBBASI-YADKORK Y., PÁL. D. and SZEPESVÁRI, C. (2011). Improved algorithms for linear stochastic bandits. Advances in neural information processing systems 24.
ABE, N., BIERMANN, A. W. and LONG, P. M. (2003). Reinforcement learning with immediate rewards and linear hypotheses. Algorithmica 37 263-293.
ABEILLE, M. and LAZARIC, A. (2017). Linear thompson sampling revisited. In Intelligence and Statistics. PMLR.
ABRAMOWITZ, M., STEGUN, A. AL. (1964). Handbook of mathematical finnttion, vol. 55. Dover New York.
AGRAWAL, S. and GOYAL, N. (2013). Thompson sampling for contextual bandits with linear payoff's. In International conference on machine learning. PMLR.
AUER, P., CESA-BIANCHI, N. and FISCHER, (2002a). Finite-time analysis of the multiarmed bandit problem. Machine learning 47 235-256.
AUER, P., DESA-BIANCHI N., FREUND, Y. and SCHAPIRE, R. E. (2002b). The nonstochastic multiarmed bandit problem. SIAM journal on computing 32 48-77.
CHAPELLE, O. and LI, L. (2011). An empirical evaluation of thompson sampling. Advances in neural information processing systems 24.
CHEN, L., MIN, Y., BELKIN, M. and KARBASI, A. (2021). Multiple descent: Design your own generalization curve. Advances in Neural Information Processing Systems 34 8898-8912.
CHEN, L.,, MIN, Y., ZHANG, M. and KARBASI, A. (2020). More data expand the generalization gap between adversarially robust and standard models. In International Conference on Machine Learning. PMLR.
CHENG, R. C. and KLEUNEN, J. (1999). Improved design of queueing simulation experiments with highly heteroscedastic responses. Operations research 47 762-777.
CHOWDHURY, S. R. and GOPALAN, A. (2017). On kernelized multi multi-armed bandits. In International Conference on Machine Learning. PMLR.
CHU, W., LI, L., REYZIN, L. and SCHAPIRE, R. (2011). Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics. JMLR Workshop and Conference Proceedings.
DAI, Y., WANG, R. and DU, S. S. (2022). Variance-aware sparse linear bandits. arXiv preprint arX:5
DESHPANDE, Y. and MONTANARI, A. (2012). Linear bandits in high dimension and recommendation systems. In 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE.
FEI, Y. and XU, R. (2022a). Cascaded gaps: Towards gap-dependent regret for risk-sensitive reinforcement learning. arXiv preprint arXiv:2203.03)
FEI, Y. and Xu, R. (2022b). Cascaded gaps: Towards logarithmic regret for risk-sensitive reinforee- ment learning. In International Conference on Machine Learning. PMLR.
GOPALAN, A., MANNOR, S. and MANSOUR, Y. (2014). Thompson sampling for complex online problems. In International conference on machine learning. PMLR.
HAMIDI, N. and BAYATI, M. (2020). On worst-case regret of linear thompson sampling, arXiv preprint arXiv:2006.0677 06790.
HE, J., WANG, T., MIN, Y. and GU, Q. (2022). A simple and provably efficient algorithm for asynchronous federated contextual linear bandits. Advances in neural information processing systems 35 4762-4775

---

HENDERSON, C. R. (1975). Best linear unbiased estimation and prediction under selection model. Biometrics 423-447.
JACOT, A., GABRIEL, F. and HONGLER, C. (2018). Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems 31.
KANDASAMY, K., KRISHNAMURTHY, A., SCHNEIDER, J. and Póczos, B. (2018). Parallelised bayesian optimisation via thompson sampling. In Internationa Conference on Artificial Intelligence and Statistics. PMLR.
KAUFMANN, E., KORDA, N. and MUNOS, R. (2012). Thompson sampling: An asymptotically optimal finite-time analysis. In Algorithmic Learning Theory: 23rd International Conference, ALT 2012, Lyon, France, October 29-31, 31, 2012. Proceedings 23. Springer.
KIM, W., KIM, G.-S. and PAIK, M. C. (2021). Doubly robust thompson sampling with linear payoffs. Advances in Neural Information Processing Systems 34 15830-15840.
KIM, W. LEE, K. and PAIK, M. C. (2022a). Double doubly robust thompson sampling for generalized linear contextual bandits. arXiv preprint arXiv:2209.0693 22920090066......
KIM, Y., YANG, I. and JUN, K.-S. (2022b). Improved regret analysis for variance-adaptiie linear bandits and horizon-free linear mixture mdps. Advances in Neural Information Processing Systems 35 1060-1072.
KIRSCHNER, J. and KRAUSE, A. (2018). Information directed sampling and bandits with het- eroscedastic noise. In Conference On Learning Theory. PMLR.
KORDA, N., KAUFMANN, E. and MUNOS, R. (2013). Thompson sampling for 1-dimensional exponential family bandits. Advances in neural information processing systems 26.
LAI, T. L.., ROBBINS, H. ET AL. (1985). Asymptotically efficient adaptive allocation rules. Advances in applied mathematics 4-22.
LI, Y., WANG, Y. and Znou, Y. (2023). Nearly minimax-optimal regret for linearly parameterized bandits. IEEE Transactions on Information Theory.
LILLICRAP, P., HUNT, J. J., PRITZEL, A., HEESS, N., EREZ, T., TASSA, Y., SILVER, D. and WIERSTRA, D. (2015). Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.02971.
LING, S., XU, R. and BANDEIRA, A. S. (2019). On the landscape of synchronization networks: A perspective from nonconvex optimization. SIAM Journal on Optimization 29 1879-1907.
LU, M., MIN, Y., WANG, Z. and YANG, Z. (2022). Pessimism in the face of confounders: Provably efficient offline reinforcement learning in partially observable markov decision processes. The Eleventh International Conference Learning Representations.
LU, Y., Xu, Z. and TEWARI, A. (2021). Bandit algorithms for precision medicine. arXiv preprint a7Xiv:2108.04782.
LUO, Y. and BAYATI, M. (2023). Geometry-aware approaches for balancing performance and theoretical guarantees in linear bandits. arXiv preprint arXiv:2306. 14872.
MAY, B. C., KORDA, N., LEE, A. and LESLIE, D. S. (2012). Optimistic bayesian sampling in contextual-bande problems. Journal of Machine Learning Research 13 2069-2106.
MIN, Y., CHEN, L. and KARBASI, A. (2021a). The curious case of adversarially robust models:
More data can help, double descend, or hurt generalization. Uncertainty Artificial Intelligence. PMLR.
MIN, Y., HE, J., WANG, T. and GU, Q. (2022a). Learning stochastic shortest path with linear function approximation. In International Conference Machine Learning. PMLR.
12

---

MIN. Y., HE, J., WANG, T. and GU, Q. (2023). Cooperative multi-agent reinforcement learning: Asynchronous communication and linear function approximation. International Conference on Machine Learning.
MIN, Y., WANG, T., XU, R., WANG, Z., JORDAN, M. and YANG, Z. (2022b). Learn match with no regret: Reinforcement learning in markov matching markets. Advances in Neural Information Processing Systems 35 19956-19970.
MIN, Y., WANG, T., ZHOU, D. and GU, Q. (2021b). Variance-aware off-policy evaluation with linear function approximation. Advances in neural information processing systems 34 7598-7610.
OMARI, C. O., MWITA, N. and GICHUHI, A. W. (2018). Currency portfolio risk measurement with generalized autoregressive conditional heteroseedastic-eetrree value theory-copule model.
RIQUELME, C., TUCKER, G. and SNOEK, J. (2018). Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling. arXiv preprinl arXiv:1802.0911:
ROBBINS, (1952). Some aspects of the sequential design of experiments.
RUSMEVICHIENTONG, P. and TSITSIKLIS, N. (2010). Linearly parameterized bandits. Mathemat- ics of Operations Research 35 395-411.
RUSSO, D. and VAN ROY, B. (2016). An cntemmttion-theoreee analysis of thompson sampling. The Journal of Machine Learning Research 17 2442-2471.
Russo, D. J., VAN ROY, B., KAZEROUNI, A., OSBAND, I., WEN, ET AL.. (2018). tutorial on thompson sampling. Foundations and Trends@ in Machine Learning 11 1-96.
SAHA, A. and KVETON, B. (2023). Only pay for what is uncertain: Variance-adaptive thompson sampling. arXiv preprint arXiv:2303.00033.
SOMU, N., MR, G. R., KALPANA, V., KIRTHIVASAN, K. and VS, S. S. (2018). An improved robust hetcroscedastic probabilistic neural network based trust prediction approach for cloud service selection. Neural Networks 108 339-354.
SONG, G., XU, R. and LAFFERTY, J. (2021). Convergence and alignment of gradient descent with random backpropagation weights. Advances in Neural Information Processing Systems 34 19888-19898.
THOMPSON, W. R. (1933). On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25 285-294.
TOWSE, A., JONSSON, B., MCGRATH, C., MASON, A., PUIG-PEIRE R., J., PISTOLLATO, and DEVLIN, N. (2015). Understanding variations in relative effectiveness: A health production approach. International journal of technology assessment in health care 31 363-370.
VARATHARAJAH, Y. and BERRY, B. (2022). A contextual-bandii-basse approach for informed decision-making in clinical trials. Life 12 1277.
WANG, Z. and ZHOU, M. (2020). Thompson sampling via local uncertainty. In International Conference on Machine Learning. PMLR.
WU, Q., WANG, H., GU, Q. and WANG, H. (2016). Contextual bandits in a collaborative en- vironment. In Proceedings of the 39th International ACM SIGIR conference Research and Development in Information Retrieval.
XU, P., ZHENG, H., MAZUMDAR, E. V., AZIZZADENESHELL K. and ANANDKUMAR, A. (2022). Langevin monte carlo for contextual bandits. International Conference on Machine Learning. PMLR.
XU, R., CHEN, L. and KARBASI, (2021). Meta learning in the continuous time limit. In International Conference Artificial Intelligence and Statistics. PMLR.
13

---

XU, R., MIN. Y., WANG, T., JORDAN, M. L. WANG, Z. and YANG, Z. (2023). Finding regularized competitive equilibria of heterogeneous agent macroeconomic models via reinforcement learning. In International Conference on Artificial Intelligence and Statistics. PMLR.
YE, C., XIONG, W. GU, Q. and ZITANG, T. (2023). Cormuptin-robuut algorithms with uncertainty weighting for nonlinear contextual bandits and markov decision processes. International Conference Machine Learning. PMLR.
YIN, M., DUAN, Y., WANG, M. and WANG, Y.-X. (2022). Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism. arXiv preprint arXiv:2203.05804
ZHANG, (2022). Feel-good thompson sampling for contextual bandits and reinforcement learning. SIAM Journal on Mathematics of Data Science 4 834 857.
ZHANG, W., ZHOU, D., LI, L.. and GU, Q. (2020). Neural thompson sampling. arXiv preprint arXiv:2010.00827.
ZHANG, Z., YANG, J., J1, X. and Du, S. S. (2021). Improved variance-aware confidence sets for linear bandits and linear mixture mdp. Advances in Neural Information Processing Systems 34 4342-4355.
ZhAO, H., HE, J., ZHOU, D., ZHANG, T. and GU, Q. (2023). Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency. arXiv preprint arXiv:2302. 10371.
ZHAO. H., ZHOU, D., HE, J. and Gu, Q. (2022). Bandit learning with general function classes: Heteroscedastic noise and variance deeeeddeddeeeeent regret bounds. arXiv preprint arXiv:2202.13600
ZuOU, D. and GU, Q. (2022). Computationally efficient horizon-free reinforcement learning for linear mixture mdps. arXiv preprint 1:XXx::225..15000
ZHOU D., GU, Q. and SZEPESVARI. C. (2021). Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory. PMLR.
14

---

A Regret analysis of Algorithm
A.1 Clarification of notation
Before elaborating on proofs, we delineate several shorthands to facilitate our discourse, For each t [T], we establish the events Eÿ and er" These events are denoted as the inclusion of d₂ and 0 in the pertinent confidence ellipse with some confidence radius 3e, respectively, Lee,
Ee = {xxT0 - x x - B. |x Vx E x,}
and
E7S 1 0 x 0 S 28 logg vx X.).
We proceed to define the set (t) representing the saturated arms at round as follows:
8(t) = {x E X, : Ax(x) > (2/dlogt + 1)x.
(A.1)
where we denote Ax(x) (x} 0") the suboptimality of Xg. Moreover, we present filtration, denoted by {.16) which is defined as
H = (3 00 21,
21 7t-1
This filtration encapsulates the information that has been gleaned up until the observation of the set of context vectors X, each particular round.
Concentration inequalities are widely used literature (Fei and Xu, 2022b; Min et al., 2022b; He et al., 2022; Lu et al., 2022; Xu et al., 2023), and here we introduce Bernstein-type inequality applicable to vector-valued martingales. This theorem, when coalesced with the approach of weighted ridge regression, enables us to construct stringent bounds that are dependent on the variance {oi
Theorem A.1 (Zhou and Gu (2022), Theorem 4.3). Let (Hi) be a filtration, {yo, 0rh121 stochastic process so that for each 2 y. IRd is Hi-measurable and O:. IR is H.41 -measaaaaaalle. For each & 2 1, define Tt = (y,, 0*) + 2r and suppose that Qt. Yt satisfy
yy S L, le R, Elee Hi] =0 0,
Big [xi) S 0²
for some constants L, R, G,E > 0 and 0 E Rd. Then, for any < 1, with probability at least 1 - 8 we have for all t >>> that
Σ L
S Be,
110 10 $ 3 + vAI10"I|
1.
where U: = AI E.
y.y., E
Psyt, 02 U.rtu and
12 8) 32 1 + log )
+ +6log 32 1 + log R) 12 )) 8
3: = 120
d d-log
1+
log
f2)
+ 24 log
32
[ + log
max leal min (1, ||y, ||y.|l } sE(t]
A.2 Proof of supporting lemmata
The forthcoming Lemmas A.2 and A.3 show that the events E and 8 hold with high probability for all & [T]. The anti-concentration argument can then be developed in manner analogous to the approach employed by Agrawal and Goyal (2013), which is often not necessary in UCB-type of arguments (Fei and Xu, 2022a; Chu al., 2011; Min al., 2023; Zhao et al., 2023).
Lemma A.2. Under Assumption 3.1, for any E (0, 1), if we define for all 2 1 that
t.
(6((1 1 log )9/3 12
3, 12 d log
1+ dda?
log
(A.2)
30R
log (04(1 + log
72 8 + VT
72
15

---

with the coefficients À introduced in Algorithm 2, then the estimate 0, given by the associated weighted regressions satisfy
( -00---01-- B.Ilx VX E IG, 2 2011228 8/2.
Proof. Observe that for any and X2, by Cauchy-Schwarzznnequuiill
have
|x x 0 Σ |0, 0 l' || ||y
(A.3)
so it suffices bound each | 1. By Assumption 3.1. the following conditions on Et and x2 hold:
R
Els
Hi] 0, E
H S 1,
Moreover, we can obtain following o. oa a, 7 |
1/2 that
Er
1,
X
X ll. S
o
72
Therefore, by applying Theorem A. with the stochastic process St//ehee and e R8/72 we deduce that with probability at least 8/2 for all t
100 1vv & 12 d log
t 1+
log
64(11
64 1 + log 2)
2²
t2
dxoz
30R + 72
(64(1
644
2 12
llog
log
+
0"1
Since ||0'|12 I 1 by Assumption 3.1, it follows from the definition 3, that 10, - 0' s Br.
Combining this with (A.3), we conclude that with probability least 1- 8/2,
Ō - /lllx
for all 2 and Xt.
The following lemma establishes the control over |xT0IS x Ozl.
Lemma A.3. Under Assumption 3.1, for any E (0, 1), let Br be as defined in Lemma A.2 for all
t 1. Then the sampled variable 0% in Algorithm satisfies
P (1xTOT5- - x xTO,1 $ 2d / ||x||= Vx X Vt 21) 2 1 8
2
Proof. By definition, 8 ~ N(O,, E,) where E, 3 V thus 10 0 N(O, 1). Then using the concentration inequality in Lemma C. for standard normal distribution, for every E [T]. have with probability least
that
xx 0SS x T
VVV
1/2
1/2 (O
-
0.)l
V 1/2
O,)
< 3
||X|V=
Be
< B, / 2d log 4t /8)|
where the first inequality follows from Cauchy- Schhwazz inequality. Applying union bound over
t E [['] and utilizing the fact that Σ 전 < 2, we obtain the final result.
In the following, we delve into the anti-concentration argument presented Lemmas A.4 to A.6, which constitute the upper bound expected regret.
16

---

Lemma A.4. For any t 2 1, if He is filtration such that E holds. we have a constant probability that the reward estimate (x, (,5) of the optimal arm constitutes an upper confidence bound, i.e.,
1
P(x; 0
Hi)
Aev n
Proof. Note that we can bound the quantity J. = (x;T0' x; (3)/ as follows:
x; T x; 02
[4
Bel1x7 liv."
Be||x llv."
[|lxxill,
(A.4)
where the inequality is due to Lemma A.2. Recalling that 0 has mean of 0:, we can establish that the probability of the reward estimate x; 0 serving as an upper bound for the true reward lower-bounded by
Px(;; 00S x; 0
Hi) = P(x;
0
Xi 10
Xi 00 - x; HG)
xi TO.
x; X;TO
X; x;
1111 x lv."
1 Iv."
(A.5)
4VT
The last inequality follows from the anti-concentration inequality in Lemma C.1 for standard normal distribution and the fact that
TO. x
N(O, 1).
B llv
Consequently, combining (A.4) and (A.5). it follows that the desired probability is lower bounded by
a constant, i.e., Pxx; ! x TT" H)) 40/
Lemma A.S. For any t 2 1, if Ay is a filtration such that Es holds, have with constant probability that the chosen arm X2 is not a saturated arm, i.e.,
P(x, & S(t) A6) 2 4e π
Proof. Recall the definition of the set of saturated arms 8(t) in (A.1) and that the selected arm x, arg maxxex, x XTO aims to maximize the estimated reward. Consequently, x, & 8(t) x; 0H0 2 T for all saturated arms x E S(t), implying that the estimated reward for the optimal arm surpasses the estimated rewards of all saturated arms. It follows that:
P(x: & S(t) A) N P(x; 0. 2 x T00 Vx 8(1) | Hi).
Further note that by the definition of saturated arms, we have
x T
x /2ogl 1) <x +x(x)) T 0
when both Es and gss hold. Therefore.
P(x, $ S(t) x) > P(x; 0 x 0* HB) (() Hi)
The last inequality is consequence of Lemmas A.3 and A.4.
17

---

Lemma A.6. For any t 1, if Hi is filtration such that both Ex and E,º hold, we have
2
(2 dogt + 1)3e B| Hi]+ + 2 8²
E
A
+1
lEVE
Proof. Let x represent the unsaturated arm with the smallest || Ilv." norm, i.e.
x arg min ||xly,
xf8(1)
The existence of such unsaturated arm x is guaranteed since x & 8(t). When both &f and Egs hold, we can express the suboptimality as follows:
A = (x]x xi 0- x70'
$ (x - (x] T 0: + (2 /logt + 1) 1)xx1(x(
-x (2 dlogt 1)33 [xx (xollv;1)
Then since x, is the optimal arm under 0rs, we further have
A S (x + (2// + 1)3.11x/11
+ dogg + 1)
S (2 + 12 Ilv." lxxxlly;))
where the second inequality results from x & 8(t). Note that [xollv. 2 ||x]]|v; with constant probability, i.e.
Hi]
E[[
[[|ix|ll;;"
Hr, $ ((()))(PP))))) & 8(t) Hi)
1
E
AA).
(A.6)
4e 4T
The last incquality is due to Lemma A.5 and the definition x as the unsaturated arm with the smallest || llv, Consequently,
E A
AA <
+ 12 + ||x; 1v,
AA] + 2P())))
2
2
+1 +1
(2 d dlogt + B[[xx
A +
where the first inequality is due to A, 2 for all f, the second inequality follows from applying (A.6),
Lemmas A.3 and A.4.
A.3 Proof of Theorem 4.1
Let us define shorthand o = =m 8f. The expected regret can be decomposed as follows:
E [
Σ E 3. EIIP(E)
+
Σ
E
0. P(E9)
E=1
E[A, Hi 16 1.35++22 2T
T
Emmin (2 dlog + 1)C&,1xxelly;
Hi + Σ
8T
12
1=1
T
E
min (2 dlgg + 1)C
03
+ 8T + +4,
18

---

where we write C max
+ 1. The first inequality is due to Lemma A.2, the second
inequality is due Lemma A.6, and the last inequality follows from A, S 2 for all [T]. To alleviate the burden on notation, we write 9r = min (2/dlog + I)C ||x ll, and an index set T = (t E [7]: |xx/orllv, 2 1]. It follows that
T
T
Σ
min (2v dlogt 1)0 1=1
=
(=1
RET
min 11
2 +
(2 +C
IGT
= 2 + 3C
Bi V dlog to, | /
TET
$ 4d + T/(daa))) 3C' Σ 3. to, min(1, /xxt/ 1),
(A.7)
where the first inequality follows from the definition of gc, the last equality is due ||x, ||x//olllv,' for all & J, and the second inequality due to
<
[ S Σ
min(1, 1x1//
NET
T
< min (1x/11//x///=lll
1=1
< 2dlog [ + T/(d)a)))
The last inequality is due Lemma C.2 and ||x/ 0 || s 1/a. Further, we decompose T [T]]J==
Ti UT2 where
J = (t E J o. og o. = a}
J (t E J o.= >11x/|1111 1/2
The second term in (A.7) can be controlled through a decomposition
Σ Blydlog lo, min(1,]|x//7:llvx-])
Σ
3e / log lo, min [l:///lllllll
1ET
T
Σ
B dlog fo, min(1, 1x, /
tTT
For E Tı, we have
Σ T
Brv dog to, min(1, ||x |x./o,lly; } < Σ
Biv (logt(o, + a) min(1, ||x, |xx//vllv.')
T
B. s/llog (0, a) min(1, ||x, |x./orllv:
tm
S
2d
3l + log Σ ||x
Bo a²) T Vd + (/(d))))
19

---

where the first inequality is due to Cauchy-Schwarz inequality, and the second inequality is due to Lemma C.2 and / - 1/a. For t E J2, we have 5 = > (p/lx//=lllv and then
Σ BeVdlog lo, min TT
Σ
B. v d to [xx./ollll
t
x2
3 v 11
tT
2
Σ
B /
$ 27 d dlog log(1 + ()d)a))))) Bo). 'E[?]
Hence, combining the inequalities above, we have
T
T
Σ Dt S 4d Adlog(1 (TTTg((++(((daa))) +30 2,
[o? + a2) T /dlog(1 + T/(daa)))
+ 30 . 2 dlog log(1 + T/(daa
(max 3r), [E[T]
and upper bound expected regret follows noting that Σ min (2v 1) } enjoys a deterministic upper bound:
B(R(T)) S Σ gt + 88 +4
s 4d log(1 + TT/dda 330 2, 2 d (0 a²) /doo (/dd)=))
1=1
3C 2-² 22 log T log(1 + (ddaa)))))))))))))))))) (max 3,) + 8T + 4 rE[2)
Take d, a a 1/VT. and 7 VR/d//t follows that
log(1 + 7/((daa))) s log / + + 1)
and
3. = (/2////ll0(((/(A)))))((((2111111 (1)
+30 (ogrloog/2111+gg)22/
vĀ
< d -
log RR /d))
+ (0 + log RVT/ ( /0) vd.
Combining Lemma A.2 and the inequalities above with = #. we conclude that
T
[[((T)) S dlog + d T
(0 + + +2 d3 log Σ
T( 3.) (E(T]
$ dlog + dlogT
30 + +2) + dlog T dlog
T
dlogg
3l0t + 1/T) dlog T T
S d
of + 3/2 log
20

---

Recall that we have
2
B[R(T)
El Elmin (2ydlogt 1) (xeelv. [1]
t2
1=1
For notational convenience, we further define S. = E Dr where Dj = Ar -
9t p2.
and
9. min(2, (2v logt + 1)C (xell:.)
< for all & E [T], and {St)t> therefore forms super-martingale process with respect to the filtrations {. Note that D < 2gt + 2 s 4, and with Azuma- Hoeffding inequality we have with probability at least 6/2 that
follows that E[D; AxA]
I
T
T
T
G.
St
+
4 1log(2/6)
[=1
t=1
T 2
m2n (2v doog 1) +
2 21 log(2/0)
T
[2, (2v dlogt + 1)C (x: } +
+ 2 2T 12g(2/6)
T
S 2 I T
Σ
of + 812
log T + VT.
t=1
B Regret Analysis of Algorithm 3
B.1 Clarification of notation
Analogous to Appendix A, first introduce two concentration events Ei, and E, for each t [T] and l E [L]. i... i.e.
EG, = 11x - - B..llxlll VX x,}
and
87, = [|x - 0r,el S / log(412
Vx e X,).
These events also characterized the inclusion of θr,e and QTS in the corresponding confidence ellipse, respectively. is noteworthy that the event &f, defined using
B.. 16 16.21
2-
Σ SEV
w6o?
log log 8t + 6 2 Rlog 8t L
(B.1)
rather than the confidence radius Bee--
Subsequently, we introduce a Freedman-type type concentration inequality pertinent to vector-valued martingales. This theorem, distinet from Theorem A. necessitates nuanced control the uncertainty term [lye for all t. 2 1. Consequently, it furnishes an even more stringent bound in comparison Theorem A.I.
Theorem B.1 (Zhao et al. (2023), Theorem 2.1). Let {Ai) be filtration (ye, eche2 a stochastic process so that Yt E Rd is A-measurable and O: E IR is Wini-measurable For 2 1 let (ye. )*) 2t and suppose that Qt. Yt satisfy
lel < R.
Ele
A =
Ble H.l S
21

---

for some constants R. (4) > 0 and 0 E R.. Then, for any 0 < < 1, with probability at least 1 we have for all that
Σ e+Y
S Br, 110, - 001,,, S + vAll0'I|,
where U. AI Σ v.y V1 E r.y 0: U. Ug and
3, = 16pv 0 log( 41 /6) + 6pft log 41 /6).
where p 2 suP121 lylll,
B.2 Proof of supporting lemmata
Lemmas B.2 and B.3 show that the concentration events Ege and E,e hold with high probability for all t [2'] and & [L].
Lemma B.2. For any d (). if we define Be, for all 2 and E [L] as in (B.1), then the
estimate or given by the associated weighted regressions in Algorithm 3 satisfy
IP (1x (ix - x 1 Beellxlll; Vx E X,, VI E V VeLLA, E (1.) 2 2
Proof. Notice that for any fixed l E [L).tC V141, and x E Xn that
xx x-00. -
1 x-0' s | 0* 0 lillv.., l
Following the assumption on et. holds that
|wee& I | & R. Elwre A = 0, Eiuře? HA $ woo?
| = =
where Wy = 2- 331//|x= lIve I Apply Theorem B.1 with stochastic process (wix,, wree) to get for all E Vr+1,
that with probability least 2L
||0 0"Ilvie S S
where
Be.
1--
Σ woo? (og(Stt2L5))) + 6. 2 2- RRogggg L/8) + 2--11
sEV
It follows from union bound that with probability at least - 8/2 that for all & E [L], t E V44. and x E X,
xx |x -
Lemma B.3. For any 5 1) and B. defined in (5.3) for all t 2 and E E [L], the sampled
variables 075, in Algorithm 3 satisfy
P (IxTOTS OTS x x / 22doog Beellx vx X,, Vt V441,, Ve (11) 2
Proof. Note that T ~ N(O... Ex,e) where Eg = Br V we have with probability at least
Ar L
|xTO,S - x xTOrel = |x v 1/2 1/2 1/2 (0 O,,ei
θ..)) 1.1
< Br.
||]|
B.F
< 3r, /
22 (4t
L/5)
|x|
|
22

---

where the last inequality follows the concentration inequality in Lemma C.I for standard normal distribution and that
1/2 O0 .c.z)
~ N(0, 1).
3,,
A union bound over all & E [L] and 2 1 yields the desired result, where the probability bound follows E 1/t2 <2
Next, we show that the empirical estimator Çe, provides an accurate estimate of the summation of weighted variance up to a logarithmic factor. The proof is analogous to Zhao al. (2023), and we provide it here for the sake of maintaining a self-contained discourse.
Lemma B.4. For all 2 and & [L] such that 2 2 GAVIog(A(( + 1)21/6), 118(1(11))110))) if E4,e is satisfied and St,e Eeev,, w](rr (x., 0,, then the the following inequalities hold:
Σ
w S 8G441. + 6R² log + (0g(4((+1)) +
3
Σ
7 w + R² Rogg (ot L/6) L/8) 2
S1-1,E
2
3
sEVi11.e
Proof. For any E [4] and I E [T], we have Exco w being an unbiased estimator of
Eoeuen w conditioned on past observations. More specifically, have E[s Xists Fiat-1]
Elo? X1a, f1a 0 for all t 2 1 and
(s 2 XIa,TTie-1 S
Eluiet XiarTia-1]
1,
sE SEW441.
S R2
8E Ve414
where the first inequality follows from Var(w,e" X1it, (12=)) < Be X1a, ria-i]. Following Freedman inequality, it holds that with probability at least 26/L that for all /
4 R log L/1) +
w
Σ wfo?
s
2R
Σ
Ro
V
sEVi11.
SEVILLE
SEV
(B.2)
1
Σ
"
o000 + 3
7 R² log 4t L/5).
2
SEV
where the second inequality follows from Young's inequality. then follows that
Σ
52
14 R² log(4t+L0 L/8) Σ w +
SEV
sEV
< Σ ( (x,, 02)))² + 14
R² logg(1 L(/8)
3
sEV.e
+4
w (x,, ,..)) 2²)
where the second inequality follows from (x: y) < 2x² + 2yy² Notice that the last term is bounded
by
Σ w (x., 0,,)) - =0)² Σ
(x,, Ore 0-2²
S
SEW.,
(ō., - (.. 07)
< Bin,6
23

---

where the first inequality follows from 2 I V4+i and the second inequality is due to Lemma B.2. If we have 2 z / log (f L/5), then
Σ
u.o? 2(6 2 Rlog( --
NEVi+
and
Σ
w < 4 Σ
14 (r(r= - (x,, 0r,))) 2 +
R² log L/6)
3
Se 1.
n60² 8(6 2 RRoog +
Move ExEVeLL woo to the other side of the inequality, we get the desired result.
Moreover, we can establish the inequality in the other direction:
Σ ..
w (xs, 02,)))
Σ
wr(r,, (x,, 02)) 2 2- 10
W + 2-2
NEVELL.E
where the first incquality follows from dz,e being the minimizer of the weighted ridge regression problem. Combining the inequality with (B.2) yields the desired result.
Lemma B.S. Suppose that Eie and Eit hold for all & E [T] and E V If all the elements in series (rr and (Be,er, as defined in (B.1) and (5.3) respectively, satisfy
3. S Bie.
then all t 2 1 and & [L] such that X,, exists, it holds x E Xx,e.
Proof. We prove the statement by induction. I = 1, then x; E X2,e Xe trivially holds. Suppose x E Ke,t for some é E E4 and Xe,441 exists, we have for all x E Xx. that
(x, 0 0.,) (x, 0 0')1 s (x. t., 0-\ +
< ( 1) | x
<2 (v (t2l L/8) 1)3,.r.
where the second incquality is due to the assumption Be, < B, Lemmas B.2 and B.3, and the last inequality is due to ||xlv, I f for all x E Xe,e. If we define x. arg maxxxxxx, (x, OTS the it holds that
x T 0*) [ 0 I (34 x 0-) + (x.
< (K,, T.S 0-) + [x] TTS 0*)
22 (v 2d log 4/ L/2 1),
where the second inequality follows from (x, x,, 0*) < 0. Hence, the optimal action x E X2, and the statement follows from induction.
Lemma B.6. Suppose that R.s S Br,s &.P and gTs, hold for all & [L] and 1 E V For any é E [L], we have
Σ
4. 16d 22d22///2/lgg///////1 + 1)3 log(1 + T2d)
AE EEW
24

---

Proof. For all E VI+LE we have x E X,,e following Lemma B.5 and the assumptions on Be. Bets Ei, and e. Due to Line 11 in Algorithm holds
++1 (2 0 0 (xe, 0 22 2- (v 2d (og(((()L/0)) + 1) 8-1
(B.3)
In addition, for any M1+1, have both ||x|ll 2- and | | v S 2-1+1 It
follows that
A S (xi, 0 0i(-1) (x,, 0 (x 0i 0²) + (xx, 0 1,8-1 -0)
$ 2- 2 ++| (v 2d log L/6) 1) + 2.2 2-1- (v (4/2 + 1)
8. 2- (v 2d log L/6) + 1)
where the second inequality is due to (B.3), Lemmas B.2 and B.3. Summing over & E 11+1 we have
Σ
D. A.58.27 ( 2dlog4472L/0) + 11)_1//0))113,,-1111 MT+LEl
BE WT+1.
88 8. 28 (V2dlog + 1) T-11
|
IEVT+L
s 2 (V L/ + 1) 2d log(11 + +22
where the second inequality due to //1 ll 2 for all / VT,,, and the last inequality due to Lemma C.2.
B.3 Proof of Theorem 5.1
With probability at least 28, all the statements of Lemmas B.2 and B.3 hold, and the rest of our proof will build such an event. Let to = [ logg log(8(T + 1)21/ + 8, and we have
Be. S Be, for all E [T] and E [[]] following Lemma B.4. It then follows Lemma B.6 that
for all & [[u]
Σ IE 1EVT+L
A < 12 3T.e-1)
3/12
Σ wf(rr - (xr. (x., 0x1,0)+1,0)2 R2 1 R
8/2
Σ
of 3/2 R 1312
where the first inequality due to Lemma B.6, the second inequality is due the definition of Fr. 1, and the last inequality is due to Lemma B.4. For any layer é e [fo] and t Br+1& have
Σ
A s M
BE NEW
22++1
Σ
|wixelle
IE tE
< (d(d).
where the first inequality follows from (x, 0*) < for all x E X, and t E [T], the equality is due to ||w,xi llv = 2- for all t E WT+116 and the last inequality is due to Lemma C.2 and 20a < (lo
25

---

For any t E (Ukee) (T+1.), Algorithm 3 selects an arm at some 4, layer, and it follows that
Σ
A 2
Σ
((x Oli.)) - (xe, 0*))
(ETTT) Pri1.)
NE(T]WWee WrILd)
Σ
(2d10g(4PP/0) 1)3c., laaa,,/xillv;
ME (T+1))
E
((5e, 0 -0") a 442 1)),,e))
1 WT+L))
Σ
(all0 1v + al 2d + 1)
x V++H))
Σ
20 2d L/ + 1)3
< T <T- Ö(Va/T)
s O(Va).
where the first inequality is due to 3,, S Re, Lemmas B.2, B.3 and B.5, the second inequality is due inequality,
to the arm selection rule of Algorithm 3, the third inequality is due to and the fourth inequality is due to Be S Br, Lemmas B.2 and B.3, and the fifth inequality follows from the definition of a and Se., S ((VTT).
Combining the above inequalities together, we conclude that
R(T) Σ A
T
S 8/2 + 8/2 R +3/2
8/2
Σ oo
where the inequality follows from L S log and to = [ log, log + 1)21 +
C
Auxiliary Lemmata
Lemma C.1 (Abramowitz et al. (1964)). For Gaussian distributed random variable X with mean m and variance o², it holds that for any x 2 1 that
exp(-x2 /2) & P[ - -m] xo) S exp(-x2 2/ N
T
Sabbasi-Yadkorii Yadkori al. (2011), Lemma 11). Let (x be sequence in Rdd V Rdxd positive definite matrix, and V. V E.= X.XJ. Then we have that
Lemma C.2 (Abbasi-
(det(V,, det(V)
log
X
Further, x/el22 S L for all then
n
Σ min
11
2(log dot(( Vn.) 17n--1o log det (V))
2dd + /d) log det (V)),
and finally. if Amin (V) 2 max(1, L?2) then
det Vnn) m))
1x S 2log del(V)
26

---

D Numerical Results
In our simulation, we test our algorithm on a linear contextual bandit problem with different sets of reward perturbations. Specifically, the simulation is carried out over T = 2000 rounds with an ambient dimension of 25. For each selection round [T], the environment yields a set of contexts X,, which contains K 50 context vectors. The context vectors are randomly drawn and structured as truncated Gaussian vectors, ensuring their norms remain bounded by Within each trial, random ground truth vector 0* is generated another Gaussian vector. The reward associated with every context vector is then computed based on the expected reward, perturbed by Gaussian noise. We employ proposed algorithms, LinVDTS and LinNATS, to scrutinize their performance within this configuration.
Cumulative Regret Over Time
Baseline on Constant Variance
VDTS an Constant Variance
Bazeline Schoduled Variance
VDTS Scheduled Variance
NATS on Schod uled Variance
Cumulative Regret
300
200
100
250
500
750
1000
1250
1500
1750
2000
Round
Figure 1: Performance comparison of LinVDTS, LinNATS, and the vanilla TS algorithms on the linear contextual bandit problem. The blue (LinVDTS), orange (LinNATS), and green (vanilla TS) lines depict the average regret for each method. Dashed lines represent the average regret in a constant variance scenario, while solid lines indicate the average regret under diminishing noise variance. Confidence bands, plotted for each method, are derived from 50 random trials.
Figure Fig. I presents the cumulative regrets of the LinVDTS and LinNATS algorithms, using the vanilla TS as benchmark. The algorithms evaluated in two distinct bandit environments: one characterized by constant variance and the other by a quadratically decaying variance. Performance under the constant variance setup is captured by dashed lines, whereas the decaying variance scenario depicted by solid lines, with the observations being grounded on 50 randomized trials. It is noteworthy that while LinVDTS is privy the ground truth variance, LinNATS operates without this knowledge in our experimental framework. This distinction underscores LinNATS'S commendable adaptability in environments where the variance is elusive. Given its access variance data, the superior performance of LinVDTS vis-a-vis LinNATS in fluctuating variance situations is anticipated. The presented outcomes showcase the pariance-awarenes, of our proposed algorithms and the inherent ficxibility of these algorithms in modulating their regret according to the prevailing variance dynamics.
Future directions and broader impact. The recent progress in understanding the training dynamics of deep neural networks (Jacot et al., 2018; Song et al., 2021) has paved the way for investigations at the intersection of deep learning and reinforcement learning (Lillicrap et al., 2015; Chen et al., 2021; Xu et al., 2021). This integrative approach promises to yield transformative insights and substantially enhance the performance of existing learning architectures. Further, the incorporation of non-linear function approximation into our frameworks emerges pivotal research direction,
27

---

with the potential to significantly improve their robustness (Ling et al., 2019; Chen et al., 2020; Min al., 2021a; Ye al., 2023). We believe that engaging in these research endeavors important for the refinement of our methodologies.
28


Reviews:
[{"review_id": "5gkWI8Fyqf", "reviewer": "Reviewer_Fr5q", "summary": "This paper presents a Thompson-Sampling style algorithm for linear contextual bandits under a heteroscedastic noise setting. When the heteroskedastic noise is known, they present a simple algorithm, LinVDTS, that achieves a variance-dependent regret upper bound, by utilizing a weighted ridge regression estimator. When the noise is unknown, they present a more general algorithm, LinNATS, that adapts to the unknown noise by using the idea of optimism together with elimination to stratify the uncertainty level. \n", "questions": "1. When the noise is known, can you provide a more elaborate explanation of why you choose \\bar{\\sigma}_s instead of \\sigma_s? Intuitively, if the variance of the noise is known, I would tend to just normalize the variance so that the problem reduces to a homoscedastic noise setting and use classical algorithms to solve it, and I’d like to know more about why that’s not enough. \n2. Can the authors comment on a matching lower bound that incorporates the correct dependence on the changing variance?\n3. Is there an off-by-1 error in line 166? Namely, the definition of \\theta_t uses x_t, whereas \\theta_t in the algorithms seems to only depend on the history up to time t-1. \n4. I think the algorithm is computationally inefficient for large or infinite arm sets, so it is more of a theoretical interest but the practical side of it is less impactful. Do the authors think the algorithm can be made practical?\n\n\n", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written. The author provides a clear structure of the two settings and intuitions for their algorithm design. They also provide a good transition between their two algorithms from an easier to a harder problem setting. Their theoretical bound is impressive in the sense that it is not obvious if one could hit the same regret bound \\tilde{O}(d^{3/2}\\sqrt{T}) as the constant variance case, but their result recovers this bound. Also, the discussion of lines 207-239 is very insightful. \n", "weaknesses": "The explanation of certain details of the algorithm could be improved. For example, the stratification process in the paper is a bit complicated. A picture to explain it would help. \nAlso, the author could add more annotations to the description of their algorithms so that it is easier to read. As another note, the paper is missing experiments, although the theoretical contribution is solid and it could be considered as a theory paper. \n\nMinor Comments:\n1. Line 137: the dependence of the noise on x_t should be more emphasized. At first glance, the fact that the noise at time t depends on the arm x_t was hidden. \n2. Check the sentence structure/grammar. Eg in Line 207\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We extend our sincere gratitude to the reviewer for their positive remarks on our study. In response to the comments, we will enhance our paper by elucidating the stratification strategy further and adding more comprehensive annotations to the algorithm description.\n\n**Q: Missing experiments**\n\nFor insights regarding the results of our numerical experiments, kindly refer to our collective response provided to all reviewers.\n\n**Q: Why choose $\\bar\\sigma_s$ instead of $\\sigma_s$; why not enough just normalizing the variance?**\n\nDirect normalization of the variance, while seemingly straightforward, isn't an effective strategy in this context. The elliptical potential lemma, which we utilize to manage the uncertainty of selected arms, cannot adequately handle exponentially large context vectors when normalized by an exponentially small variance. Therefore, opting for direct normalization could negatively impact the regret bound. The application of $\\bar\\sigma_s$ allows us to strike a balance between managing noise variance and controlling the uncertainty of the context vector. This balance ultimately results in our final regret bound.\n\n**Q: Matching lower bound that incorporates the correct dependence on the changing variance**\n\nThank you for the insightful question! There's currently no known lower bound, even in the context of the UCB case. We hypothesize that a potential lower bound could be in the order of $\\Omega\\Big(d\\sqrt{\\sum_{t=1}^T \\sigma_t^2}\\Big)$. This would hold true under the condition of homoscedastic noise, whereby the lower bound would reduce to $\\Omega(d\\sqrt{T})$. This is a minimax lower bound already achieved by the Feel-Good TS algorithm (Zhang, 2021). Eliminating the additional $d^{1/2}$ factor would constitute a significant undertaking in future research endeavors, and we appreciate you pointing us in this intriguing direction.\n\n**Q: Subscript off by one?**\n\nWe appreciate your keen observation. We will ensure it's corrected in the forthcoming revision of the manuscript.\n\n**Q: Computationally inefficiency for large or infinite arm sets**\n\nIn practical scenarios, we can leverage parallel computing to compute individual reward estimates across a discrete set of arms. In cases with an infinite set of arms, it is also possible to undertake the arm selection and decision set construction process efficiently if the set of all feasible context vectors is convex. Given a convex decision set $\\mathcal{X}\\_{t,\\ell}$, the succeeding level decision set $\\mathcal{X}\\_{t,\\ell+1}$ will also be a convex set through intersection of an additional hyperplane. The optimizer can be computed using convex optimization schemes. We appreciate the reviewer bringing this point to our attention. We plan to incorporate a discussion regarding this in the final revision of our paper.\n"}, {"review_id": "sm3ekr2Er7", "reviewer": "Reviewer_oXdZ", "summary": "This paper investigates the contextual linear bandit model, a widely utilized framework for online decision-making problems. Specifically, it focuses on the heteroscedastic noise setting, where each reward is associated with a different variance. The authors propose a novel noise-adaptive Thompson sampling algorithm that establishes a regret upper bound dependent on the variance. This theoretical contribution not only encompasses the findings from the constant-variance and deterministic-reward regimes but also provides an interpolation between these two settings.\n\nThe paper presents two algorithms in total. The first algorithm, VDTS, achieves a variance-dependent regret bound in expectation. However, the authors acknowledge the inherent challenge of controlling uncertainty induced by posterior sampling, preventing them from obtaining a high-probability regret upper bound.\n\nTo address this limitation, the authors introduce the NATS algorithm, which employs stratification to partition uncertainty terms into distinct layers. By doing so, it bypasses the conventional anti-concentration argument typically employed in Thompson sampling analysis. The proposed NATS algorithm is proven to achieve a high-probability regret upper bound, surpassing existing bounds for linear Thompson sampling.", "questions": "1. Theoretically, NATS is shown to achieve a high probability regret upper bound, while VDTS only in-expectation regret upper bound. I am interested in whether NATS and VDTS will perform differently (or similarly) in empirical results. A numerical simulation would be interesting to check.\n2. In this paper, variance-awareness of the proposed algorithm is only proven theoretically. But I doubt whether this can really be realized empirically. For example, if we apply NATS to two bandit instances with different noise levels, would the observed regret really be smaller if the variance is smaller? ", "limitations": "Please refer to the above Weaknesses.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "**Novelty**\n\nThis paper makes a significant contribution by introducing the first variance-aware Thompson sampling algorithm. Previous theoretical work solely focused on regret bounds that were independent of noise variance. The authors employ novel techniques, drawing inspiration from the stratification framework initially proposed for UCB-based algorithms.\n\n**Theoretical Contribution**\n\nThe theoretical contributions of this paper are commendable. The introduction of a variance-aware bound represents a substantial improvement over existing bounds for linear Thompson sampling. Traditional bounds may prove suboptimal when the true noise variance is relatively small. Additionally, the authors' analysis incorporates stratification, enabling them to circumvent the commonly adopted anti-concentration argument found in classical Thompson sampling analyses.\n\n**Clarity**\n\nThis paper is presented in a clear and coherent manner. The mathematical definitions are precise and well-defined. The VDTS and NATS algorithms are thoroughly explained and accompanied by demonstrations. The main theorems (Theorem 4.1 and 5.1) are followed by discussions regarding their implications.", "weaknesses": "This paper has no empirical results at all. For such kinds of theoretical bandit algorithms, numerical experiments are usually required to demonstrate the correctness of the proposed methods and the validity of the proved theorems. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate the reviewer's generous words and acknowledgement of our theoretical contributions.\n\n**Q: Empirical results**\n\nFor insights regarding the results of our numerical experiments, kindly refer to our collective response provided to all reviewers.\n"}, {"review_id": "rIkLxzwjwg", "reviewer": "Reviewer_AK5v", "summary": "This work delves into the field of the linear contextual bandit, a widely used model for addressing sequential decision-making problems with broad applications in real-world scenarios. In this framework, the player selects an arm from a predefined set and receives a random reward from an unknown distribution upon pulling it. The objective of this learning problem is to minimize the cumulative regret, which is the sum of the differences between the rewards obtained and the rewards of the optimal arm (which is unknown to the player) across all rounds. In particular, Thompson sampling (TS) emerges as a prominent family of algorithms for solving the linear contextual bandit problem, with an extensive body of literature dedicated to analyzing their theoretical properties. TS has garnered considerable attention in research, making it an active area of exploration. This work specifically focuses on the linear Thompson Sampling (TS) algorithms, where existing studies have established an upper bound of $O(d^{3/2} \\sqrt{T})$ for the regret in Linear TS algorithms. However, this bound lacks noise adaptivity, meaning it does not consider the variance in the reward distribution. Intuitively, the bandit learning problem becomes easier when the reward distribution has lower variance, and vice versa.\n\nThis work addresses the limitations of previous methods by providing the first noise adaptive linear TS algorithms and theoretically proves that it achieves a variance-aware regret upper bound. Specifically, two different algorithms are presented. The first algorithm, VDTS, is shown to achieve a variance-aware regret bound in expectation. This work briefly explains the technical difficulty in establishing a high-probability variance-aware bound by identifying two factors: (1) the optimism in VDTS is too conservative; (2) a purely technical challenge for controlling a difference term in the regret analysis. The work also presents another high-probability bound for VDTS, but it is not variance-aware. \n\nThis study then introduces a new algorithm, NATS, which successfully achieves a variance-aware regret bound in high probability. This is the first TS-based algorithm for linear contextual bandit that is noise adaptive. The key design of NATS is a layering technique, which is motivated by some UCB-based algorithms. On a high level, this technique divides the uncertainty quantities into different layers depending on their magnitudes. By doing so, a variance-dependent confidence radius for model parameters can be built, which eventually leads to a variance-aware regret bound. This differs from the anti-concentration argument adopted by existing work in analyzing TS-based algorithms. ", "questions": "1. I would be curious to see how the algorithm performs. The following questions are worth investigating: \n\n​\t (a) How does the regret of NATS respond to the change in the noise level? For example, if one runs a numerical simulation on two synthetic bandit instances with different $\\sigma^2$, will the regret curves manifest obvious differences? \n \t\n(b) It seems that the absence of a high-probability variance-aware bound for VDTS is more of a technical issue. So, I am interested to know whether VDTS indeed has a worse performance than NATS.\n\n2. This manuscript uses both terminologies “variance aware” and “noise adaptive” without an explicit definition (though it's not a big issue). In my understanding, they refer to the same property. So, I am just a bit curious why using two terms instead of one. Or perhaps an explicit definition/explanation can be added to prevent any confusion for future readers. ", "limitations": "See Weaknesses.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. This work provides a solid theoretical analysis of two proposed TS-based linear bandit algorithms with well-grounded motivation. In particular, the study on how to achieve a high-probability noise-adaptive regret bound is comprehensive. The following are my detailed comments.\n2. The focus on noise-awareness is well-motivated. I think it is particularly interesting to have a result for TS that bridges the gap between deterministic reward and constant-variance reward. Furthermore, since such types of results have been developed for UCB-based algorithms, it is a natural question to ask whether this is achievable in a TS setting. \n3. This work is the first work to establish a high probability regret bound with noise-adaptivity for linear TS-based algorithms. Although such kind of results has been achieved by UCB-based algorithms in quite a few existing works, there is a scarcity of results concerning TS-based algorithms. Since TS is believed to have higher computational efficiency than UCB, variance-awareness will make TS more favorable, especially in scenarios characterized by noise heteroscedasticity. \n4. Naively adopting the algorithmic design based on weighted linear regression from UCB will not grant a high probability of regret bound in the TS setting, which is due to the technical barrier in the analysis as mentioned on page 6. Therefore, the work takes a different route by borrowing the idea of stratification over the uncertainty quantity, as introduced in Section 5.1, which results in a variance-dependent concentration inequality (eq 5.2). \n5. As a theoretical work, this current manuscript is well-written. Most parts are relatively easy to follow. The paragraphs are eloquently composed, giving a clear explanation of the complicated algorithmic design of VDTS and NATS. For example, after main theorems 4.1 and 5.1, remarks and discussions are added to provide implications of the results. The discussion on page 6 regarding why VDTS cannot achieve a high-probability variance-aware bound is especially appreciated.", "weaknesses": "1. For theoretical papers on bandit algorithms, numerical simulations are usually quite necessary for demonstrating the empirical performance of the proposed algorithms. For this work, this is especially the case as its main theoretical contribution is a variance-aware regret bound which often involves subtlety. I would not doubt that NATS/VDTS will produce a sublinear ($O(\\sqrt{T})$) cumulative regret. The key implication of this work is whether the algorithm can truly adapt to the noise level, but it is not immediately clear. For more specific questions, please refer to the Question section below.\n2. This is more of a question than a weakness, but the work mentioned that the current regret bound’s dependence on dimension d is $O(d^{3/2}$), in comparison with $O(d)$ in the Feel-good TS algorithm. This makes me very curious about whether the current method can be improved to reach optimality in d. For example, if it is not possible, what technical barrier prevents the method from doing so? It would be helpful to have a bit more discussion on this point. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We extend our heartfelt thanks to the reviewer for their generous praise and acknowledgment of our theoretical contributions.\n\n**Q: Missing experiments**\n\nFor insights regarding the results of our numerical experiments, kindly refer to our collective response provided to all reviewers.\n\n**Q: Improving regret bound’s dependence on dimension $d$**\n\nIndeed, as outlined in the final section of our paper, exploring algorithms that yield an improved regret bound with an $O(d)$ dependence on the ambient dimension presents an intriguing direction for future research. We are actively engaged in developing such algorithms. For instance, the algorithms based on Feel-Good TS (Zhang, 2021) necessitate a specific regularization of the squared loss. This process deviates significantly from our current approach in proving techniques. For canonical TS, our NATS algorithm enjoys a regret bound that aligns with the near-optimal lower bound for both a fixed variance scenario and a constant reward scenario.\n\n**Q: Terminologies “variance aware” and “noise adaptive”**\n\nThis is an insightful observation. We intentionally use both the terms \"variance aware\" and \"noise adaptive\" in our paper, each serving a specific purpose. The term \"noise adaptive\" is used to characterize our algorithms, highlighting that they do not require knowledge of the true variance to achieve variance-dependent regret, thereby illustrating adaptivity to unknown noise. On the other hand, we utilize \"variance aware\" and \"variance dependent\" to depict the resulting concentration bounds and regret performance of the algorithms, as these metrics are explicitly dictated by the true variance. In our subsequent revision, we will unify the terminology by merging \"variance aware\" and \"variance dependent\".\n"}, {"review_id": "zJ6f7TB6Ho", "reviewer": "Reviewer_xGkR", "summary": "This paper considers linear bandit problems with adaptive noise sequences. They propose LinVDTS that takes the noise level as input, applies a weighted RLS to estimate the parameter, and adopts a TS manner to choose the actions. LinVDTS achieves a noise-dependent regret that matches the best $O(d^{\\frac{3}{2}} \\sqrt{d})$ frequentist order. They also propose LinNATS, which drops the requirement of the knowledge of heteroscedastic noise using a weighted RLS estimator with multi-layer uncertainty structures. LinNATS achieves similar regret bounds.", "questions": "As discussed above in the Weakness part, I would appreciate it if the authors could explain more regarding the significance and contributions of this work. Also, can the authors comment on why they fail to achieve optimal Bayesian bound?", "limitations": "I don't see any limitations or potential negative societal impact of this work.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-organized and easy to follow. The proofs seem to be technically sound. In general, I think this paper does a great and complete job in providing theoretical guarantees for the noise-adaptive linear bandit problems.  ", "weaknesses": "My main concern is the significance and contributions of the job. The key contributions are claimed to be LinVDTS, LinNATS and their regret bounds. However, the RLS estimator and its proof technique are standard in the literature of Linear Thomson Sampling (LinTS). Compared with LinTS, the only new component of LinVDTS is the weighted RLS estimator (which is also standard in its literature) to handle adaptive noise. The remaining parts, including the associated regret proof, are essentially the same. The multi-layer design of LinNATS is also common in papers dealing with unknown parameters/uncertainty/non-stationarity. It's not a surprise the authors could get the presented results\n\nI don't agree with the third contribution the author claimed: \"This improves over the existing $\\mathcal{O}(d^{\\frac{3}{2}}\\sqrt{T})$ regret bound for LinTS\". When all variances are fixed at constant, the bound is still $\\mathcal{O}(d^{\\frac{3}{2}}\\sqrt{T})$. The mentioned ``diminishing variances'' are too simplistic and shall not be over-emphasized. \n\nThird, the presented Bayesian regret is of order $\\mathcal{O}(d^{\\frac{3}{2}}\\sqrt{T}+\\delta T)$, which is worse than the known best achievable $\\mathcal{O}(d\\sqrt{T})$ [1]. \n\nRefs:\n1. Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4):1221–1243, 2014. doi: 10.1287/moor.2014.0650. 2, 3", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for the feedback. In the subsequent response, we aim to address the concerns raised.\n\n**Q: Explain more regarding the significance and contributions of this work**\n\nWe appreciate the reviewer's feedback. While we recognize and appreciate the existing literature pointed out by the reviewer, we stress that our work significantly diverges in terms of the primary technical challenges addressed. This results in a unique contribution to the body of research in this area. We elaborate on our contributions as follows:\n\n_1. Identifying a Unique Challenge of Uncertainty Control to TS-based Algorithms Absent in UCB-based Algorithms_\n\nWhile the direct application of weighted ridge regression has been employed in UCB-based algorithms to solve contextual bandits with heteroscedastic noise, the issue of securing a high probability bound using this widely accepted ridge regression approach had not been previously identified. As we've elucidated in our discussion of the VDTS algorithm, the strategy of weighted ridge regression estimation coupled with anti-concentration TS analysis fails to concurrently provide a variance-dependent and high-probability regret bound.\n\nWe identified that the core challenge lies in the design of the canonical TS paradigm. The lack of exact optimism in arm selection necessitates the coarse anti-concentration argument, which falls short in capturing the dependence on the variances even when they are known to the algorithm.\n\n_2. Distinct Purpose of the Stratification Design in Our Algorithm_\n\nWhile the multi-layer design has been utilized in UCB-based algorithms, its application in our algorithm serves a largely different purpose. In UCB algorithms, the multi-layer design is employed to address the issue of the unknown variance when applying self-normalized concentration inequalities. In contrast, we introduced a stratification approach in our work primarily due to the need for explicit control of the uncertainty quantities related to the selected contexts, an issue that does not exist in UCB-based algorithms. Without proper uncertainty control, it is impossible to bound over the most basic regret decomposition.\n\nOur work uncovers this limitation inherent in the widely accepted TS technique and proposes an approach to overcome it. We have shown that this challenge can be effectively addressed by employing stratification over uncertainty levels, which furnishes explicit control over uncertainty quantities. Moreover, such an algorithmic design eradicates the need for the anti-concentration argument prevalent in TS-type algorithms, a complex technique ubiquitously used in almost all regret analyses of TS algorithms.\n\nTo sum up, we put forth the first variance-dependent result in the TS setting. During this process, we identify unique challenges within existing TS algorithmic design and regret analysis techniques and develop effective strategies to overcome these challenges, especially those concerning uncertainty control.\n\n**Q: The mentioned “diminishing variances” are too simplistic and shall not be over-emphasized.**\n\nWe appreciate the chance to clarify that we did not position the performance of our algorithm in the diminishing variance setting as a primary contribution of our work. The example concerning diminishing variance merely serves illustrative purposes. \n\nOur primary contribution lies in the development of noise-adaptive algorithms with explicit variance-dependent regret bounds. This represents an advancement over existing work, as our proposed algorithm offers variance-dependent regret bounds where previous methods fall short. \n\nThank you for bringing this to our attention. We will ensure to clarify this point in our upcoming revision to avoid any potential misunderstandings. \n\n**Q: Bayesian regret and optimal Bayesian bound**\n\nWe would like to clarify that our regret guarantees fall within the frequentist perspective, wherein the expectation is not measured with respect to the prior, as in the case of Bayesian regret. Hence, the Bayesian regret of order $\\mathcal{O}(d\\sqrt{T})$ as specified in Russo and Van Roy (2014) is not directly comparable to our frequentist regret bound $\\mathcal{O}(d^{\\frac{3}{2}}\\sqrt{T}+\\delta T)$, given that the expectations are calculated against different probability measures.\n\nSpecifically, our high-probability upper bound aligns with the lower bound for canonical TS provided in Hamidi and Bayati (2020) under both the constant variance case and deterministic reward scenarios. Though it trails the minimax lower bound by an unavoidable factor of $\\sqrt{d}$, which comes from the conservative nature of the canonical TS approach, this presents an interesting avenue for future research. Integrating components from more explorative algorithms such as Feel-Good TS (Zhang, 2021) could potentially help attain minimax optimality.\n"}]

Author rebuttal:
We sincerely thank all reviewers for their valuable feedback. We will address all highlighted points in the upcoming revision. Detailed responses to specific questions are included below and will also be reflected in the revised manuscript.

**Numerical simulation results**

In response to the collective request of the reviewers, we have integrated numerical experiments into our response. A detailed figure can be found in the attached PDF file.

Our simulation focuses on a linear contextual bandit problem incorporating different reward perturbations. In this setup, we put our proposed algorithms, VDTS and NATS, to the test under a bandit configuration with the total number of $T = 1000$ bandit selection rounds and the ambient dimension $d = 25$. In every selection round $t\in [T]$, the environment generates a context set, $\mathcal{X}_t$, comprising a random assortment of $K=50$ context vectors. These vectors are configured as truncated Gaussian vectors such that their norms do not exceed $1$. Concurrently, a random ground truth $\theta^*$ is generated as a truncated Gaussian vector within each trial. The reward corresponding to each context vector is then determined by the expected reward, offset by Gaussian noise. The complete simulation setup and more simulation results will be included in the revision.

The figure showcases the cumulative regrets of the VDTS and NATS algorithms, with the Vanilla TS serving as a benchmark for comparison. Each algorithm is tested under two different bandit setups: one with a constant variance and another with a quadratically decaying variance. The dashed lines depict the performance under a constant variance scenario, while the solid lines correspond to the decaying variance scenario. These results are based on 50 random trials.

It's worth noting that in our experimental setup, the VDTS algorithm has access to the ground truth variance, while NATS does not. Therefore, the performance of NATS truly reflects its adaptability under conditions of unknown variance. The superior performance of VDTS in comparison to NATS under a varying variance setup is to be expected, as VDTS has explicit access to variance information.

The results validate two critical aspects:
(i) The empirical realization of variance awareness in our proposed algorithms, and
(ii) The adaptive nature of the algorithms' regret in response to different variance scheduling.

**Q: Whether NATS and VDTS will perform differently (or similarly) in empirical results?**

Both NATS and VDTS perform similarly in our experiments under a constant variance setup, and VDTS achieves smaller cumulative regret when the variance decreases over time. 

**Q: Whether variance awareness of the proposed algorithm can be realized empirically?**

Yes. As evidenced in the figure, the performance of both NATS and VDTS progressively improves as the variance of the perturbation decreases, thereby illustrating the empirical realization of variance awareness in our proposed algorithms.

**Q: Does the regret of NATS respond to the change in the noise level?**

Indeed, it does. As observable from the results, the regret associated with NATS markedly decreases as the level of variance diminishes, demonstrating the algorithm's responsive nature to changes in noise levels.

**Q: Whether VDTS indeed has a worse performance than NATS?**

Our numerical findings suggest that under heteroscedastic noise, VDTS typically outperforms NATS. This observation aligns with our expectations, given that VDTS has the advantage of access to explicit variance information, which NATS does not have.


Meta-review: The paper makes a clear contribution of being adaptive to the unknown noise for the Thompson sampling algorithm. The paper is well-written, providing insight.
Decision: Accept (poster)