Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits
Authors: Xuheng Li
Quanquan Gu
Venue: NeurIPS 2025 poster ()
Keywords: Thompson sampling
variance aware
contextual bandits
Primary area: theory

Abstract: Variance-dependent regret bounds have received increasing attention in recent studies on contextual bandits. However, most of these studies are focused on upper confidence bound (UCB)-based bandit algorithms, while sampling based bandit algorithms such as Thompson sampling are still understudied. The only exception is the `LinVDTS` algorithm (Xu et al., 2023), which is limited to linear reward function and its regret bound is not optimal with respect to the model dimension. In this paper, we present `FGTSVA`, a variance-aware Thompson Sampling algorithm for contextual bandits with general reward function with optimal regret bound. At the core of our analysis is an extension of the decoupling coefficient, a technique commonly used in the analysis of Feel-good Thompson sampling (FGTS) that reflects the complexity of the model space. With the new decoupling coefficient denoted by $\mathrm{dc}$, `FGTS-VA` achieves the regret of $\tilde{\mathcal{O}}(\sqrt{\mathrm{dc}\cdot\log|\mathcal{F}|\sum_{t=1}^T\sigma_t^2}+\mathrm{dc})$, where $|\mathcal{F}|$ is the size of the model space, $T$ is the total number of rounds, and $\sigma_t^2$ is the subgaussian norm of the noise (e.g., variance when the noise is  Gaussian) at round $t$. In the setting of contextual linear bandits, the regret bound of `FGTSVA` matches that of UCB-based algorithms using weighted linear regression (Zhou and Gu, 2022).

Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits
Xuheng Li
Quanquan Gu
Department of Computer Science University of California, Los Angeles California, 90095 xuheng. li@cs. ucla. edu
Department of Computer Science University of California, Los Angeles California, 90095 qguêcs. ucla.edu
Abstract
Variance-dependent regret bounds have received increasing attention in recent studies on contextual bandits. However, most of these studies are focused on upper confidence bound (UCB)-based bandit algorithms, while sampling based bandit al- gorithms such as Thompson sampling are still understudied. The only exception is the LinVDTS algorithm (Xu et al. (2023), which is limited to linear reward function and its regret bound is not optimal with respect to the model dimension. In this paper, we present FGTS-VA, variance-aware Thompson Sampling algorithm for contextual bandits with general reward function with optimal regret bound. At the core of our analysis is an extension of the decoupling coefficient, a technique com- monly used in the analysis of Feel-good Thompson sampling (FGTS) that reflects the complexity of the model space. With the new decoupling coefficient denoted by de, FGTS-VA achieves the regret of Ö(V de- log [F] o + de) where IF is the size the model space, the total number of rounds, and of is the subgaussian norm of the noise (e.g., variance when the noise is Gaussian) at round t. In the setting of contextual linear bandits, the regret bound of FGTS- matches that of UCB-based algorithms using weighted linear regression (Zhou and Gu 2022
Introduction
The contextual bandit (Langford and Zhang 2007) is pivotal setting in interactive decision making, and is an important generalization of the multi-aredd bandit that incorporates context- context-dependent reward functions. However, the standard contextual bandit setting is unable to account for hetero- geneous and context-dependent noise the observed rewards, which can have significant impacts the performance of algorithms (Auer) 2002). Additionally, algorithms designed for standard contextual bandits (Abbasi- Yadkori et al. 2011 Chu et al., 2011) are usually incompatible with potentially benign environments, despite achieving the minimax regret bound in the worst case. For example, these algorithms have worst-case regret bound of (dd for linear contextual bandits, where 7' is the number of steps; however, if the reward is deterministic, then the algorithm based on simple exploration can achieve the regret of (d)) To fill this gap, number of approaches (Zhou et al. 2021 Zhang et al. 2021 Zhou and Gu 2022 Kim et al. 2022, Xu et al.) [2023] Zhao et al. 2023 Jia et al. (2224) have been developed to account for the heterogeneous magnitudes of the noise, and regret bounds are established depending on of i.c., the noise variance in step t. Most these approaches based the upper confidence bound (UCB). Notably, Zhou and Gu (2022) and Zhao
al. 2023) established the nearly optimal regret bound of Odd Et of + d) in linear bandits, which degenerates to Ö(d) in the deterministic case, under the settings where of are known and agnostic to the agent, respectively.
Thompson sampling (TS) (Thompson 1933) another technique that facilitates exploration of the action space apart from UCB- UCB-based methods. In TS-based algorithms, an estimation of the reward 39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

function is sampled from the posterior distribution instead of being deterministically constructed. TS- based algorithms have displayed better efficiency than UCB-based algorithms empirically (Chapelle
and Li 2011; Osband and Van Roy 2017), and have been extensively studied for both multi-armed
bandits (Agrawal and Goyal| 2012 Kaufmann et al.] 2012 Agrawal and Goyal, 2017 7 Din et al.
202T) and linear bandits (Agrawal and 2013). However, minimax-optine frequentist regret bound of standard TS has been lacking, and Zhang (022) constructed an instance such that standard
TS is suboptimal. To resolve this issue, ZZhang (2022) proposed new variant of TS called the Feel-Good Thompson sampling (FGTS)) and theoretically justifies that the frequentist regret of FGTS is ((dvT), which is minimax optimal and similar to UCB-based algorithms (e.g.. OFUL AAbbasi-Yadkoy et al., 2011) and LinUCB (Li at. 20100).
Despite the success the success of TS-based algorithms in the vanilla contextual bandit setting, there is scarcity of results concerning pariance-aware contextual bandits. A notable exception is Xu et al. 2023), which proposed variant of TS with weighted ridge regression. However, this result is restricted to linear contextual bandits, and the regret is suboptimal in the model dimension d. which is an issue shared by TS-based algorithms designed for vanilla contextual bandits (Agrawal and Goyal 2013 Abeille and Lazaric 2017). Therefore, the following open question arises:
Is it possible to design a TGTS-busel algorithm for contextual bandits whose regret is both optimal in d and pariance-dependee similar to UCB B-b-baded algorithms?
In this paper, we answer this question affirmatively with the first variance-aware algorithm based on FGTS and new analysis techniques. We summarize contributions follows, with comparison of our algorithm against related algorithms shown in Table D
1. We propose an (GTTSbbaeed algorithm called FGTS-VA for the setting of puriance-depende contextual bandits, which is applicable to the general reward function class. Compared with the standard FGTS algorithm (Zhang (2022), the posterior distribution of FGTS-VA adopts not only seriance-deendent weights applied to the log-likelshoods but also a new feel-good exploration
term. When reduced to standard contextual bandits, FGTS-VA is the first PGTS-based algorithm that does not require knowledge of the horizon T.
2. In the analysis FGTS-VA -AA, we propose the generalized decoupling coefficient, which is a novel extension of the standard decoupling coefficient commonly used in the analysis of FGTS. We relate the generalized decoupling coefficient to other complexity measures by showing that (i) the generalized decoupling coefficient is ((d) for linear contextual bandits, and that (ii) it is bounded by the generalized Eluder dimension for the general reward function class.
3. Equipped with the generalized decoupling coefficient (denoted as dc), we show that the regret
bound of FGTS VA is O(v (1 Σ of) de log FF + dc) in expectation, where [F is the cardinality of the function class. For linear contextual bandits, FGTS-VA enjoys the nearly optimal
regret of (dy Σ.= of + d), similar to UCB-based algorithms (hou and Gu 2022 Zhao et al.
2023). When restricted to the deterministic case, the regret of FGTS-VA is (dc), matching the lower bound given by Xu al. (2023).
Notation. We use [|:] to denote the indicator function. We use KL(-II-) to denote the KL-divergence of two distributions. We use standard asymptotic notations (--) ()-). and ((-), with Ö(-). ()()). and Õ(.) hiding logarithmic factors; f(-) S g()) means f(.) = (g)()). We use non-boldface letters to denote scalars, boldface lower-case letters denote vectors, and boldface upper-case letters to denote matrices. We use (.. to denote the inner product, i.e., for vectors a and b, define (a, b) = a b; for matrices A and B, define (A, B) = tr(ABT) For a vector v and a positive semi-definite (PSD) matrix M, let ||v||M = VVTMv. For a positive integer n, let [n] denote the set of (1,2,...., r.).
2
Related Work
Variance-aware algorithms. AAudibert et al. (2009) proposed the first algorithm that utilized the variance information through empirical estimates of the variance, with a line of works based on similar techniques for various settings (Hazan and Kale 2011 Wei and Luo 2018 Ito 2021 Ito and Takemuraa 2023). Mukherjee et al. (2018) used the variance estimates to characterize connidence intervals and to perform arm elimination.
2

---

Table 1: Comparison of variance- algorithms for bandits. We compare the regret under the setting of both stochastic and deterministic linear bandits, where d is the model dimension, the number of steps, and A Σi=1 of is the sum of variances. The last column stands for whether the variance is revealed to the learning agent at step t.
Algorithm
Technique
Regret (General)
Regret (Deterministic)
Weighted OFUL
UCB
Ö(dVA+
((d)
Known
SAVE
UCB
Ö(dVA + +d)
((d)
Unknown
Zhoo et
2025
LanVDTS DS
TS
Old VÀ +
Ö(d'-5
Unknown
3023
FGTS
TS
Ö(dvT)
Ö(dvT)
NA
Zhang 2022
FGTS-VA
TS o(dVA +
((d)
Known
A recent line of works study variance-dependent algorithms for bandits with function approximation. For the case known variances, a line of works have utilized the variances in weighted ridge regression in linear bandits (Zhou et al., 2021; Zhou and Gu 2022). For the case of unknown variances, ZZhang et al. (2021) and Kim et al. (2022) constructed variance-dependent confidence sets, and /Zao et al. (2023) designed SupLin- in-type algorithm and proposed the idea of classifying
samples into different variance levels. Di et al. (2023) used the idea of Zhao et al. (2023) to develop a
variance-aware algorithm for dueling bandits. Notably, Zhou and Gu (2022) and Zhao et al. (2023)
managed to derive the nearly optimal regret bounds of Ö(dy Ei, respectively. For contextual bandits with the general function class, Wei et al. (2020) focused on the case where the action space is small and derived the regret bound related to the total estimation error. recent work (Jia et al. 2024) studied two cases that are referred to the weak adversary and the strong adversary, depending on whether the actions of the agent can affect variances. This work
of
d) for the
cases,
managed establish regret bound of Ödelu v ΣT ET= + delu) for the strong adversary, where detu stands for the Eluder dimension. However, the analysis the weak adversary setting, which is more closely related to the setting of our work, is restricted to the case of finite action space.
Another line of works derived second-order bounds for Markov decision processes. |Wang al. (2024a) derived the first second-order bound for distributional RI. Built on the pivotal triangle inequality in Wang al. (2024a). Wang et al. (2024b) proved that OMLE algorithm (Liu al. 2023 without weighted regression enjoys the second-orde regret bound.
Feel-Good Thompson sampling (FGTS). Zhang et al. (202T) first proposed FGTS, and achieved the
minimax--ptimmn regret bound for linear contextual bandits by virtue the feel-good exploration term in the posterior distribution. Fan and Gu 2023) extended the technique to function approximation of the policy space and applied the algorithm to a number of variants of linear contextual bandits. A recent work by Li et al. (2224) derived an algorithm for contextual ducling bandits based on FGTS that is efficient both theoretically and empirically. By replacing the feel-good exploration term with the value function in the first step, Agarwal and Zhang (022): Dann et al. (202T) applied FGTS to masel-based RL and model-free RL, respectively, with the technique of Agarwal and Zhang (2022) more similar to Zhang 2022).. and the technique of Dann et al. (2021) motivating of our algorithm.
Variance-aware Thompson sampling algorithms. (aha and Kveton (2023) proposed variance- aware TS- ba-dd algorithm for multi-armes bandits. Xu et al. (2023) proposed LinVDTS, which is the only algorithm for linear bandits based on Thompson sampling. The posterior distribution in LinVDTS is Gaussian with the mean estimated with the weighted ridge regression in Zhou and Gu
(2022). However, the regret bound of LinVDTS is (d. VVT +d1.5), which is suboptimal in d, similar to the regret bound of 1.. (T) of standard TS algorithms for linear bandits (Agrawal
and Goyal 2013 Abeille and Lazaric 2017
3

---

3 Preliminaries
3.1 Contextual Bandits
We study the setting of contextual bandits (angford and Zhang, 2007) which is an extension to multi-armed bandits by adding the notion of the context set X and allowing the action set to be context-dependent subset of the whole action set A. In step t over a total of steps, the agent first receives the context Iy and the action set Ar A. The agent then selects action or É A and receives randomized reward r; = [= a+) + ct. where f.
x A. + [0, 1] is the ground truth reward function which is unknown to the agent, and c is the zero-mean noise. We use Fr to denote the filtration generated by {(1,, az ft. re) hemm, i.e., all the randomness up to step t (including the randomness the reward function fa sampled), and Ge denote the filtration that includes all the randomness of F, but rs. The goal of the agent is to minimize the total regret defined as
T Regret (T) (.)(m,,))) fa aj)]
where of argmax fo (Tr, a) is the optimal action in step f.
Subgaussian noise. Following previous works FGTS for contextual bandits (Zhang 2022 Fan
and Gu 2023), we assume that the noise subgaussian, and denote the subgaussian norm of as of which is formalized by the following assumption:
Assumption 3.1. The noise e, is of -ussuaaausn conditioned on the history, i.c., for any A, the moment-gencratinn function of e, conditioned on G, satisfies
log Elgx(p((Ae < x21²/8.
We denote A = ΣT= of We assume that of is revealed to the agent at the beginning of step t, which is referred to as the setting of "weak adversary with variance revealing" in Tia et al. (2024). Compared with the assumption used in
variance- algorithms (Zhou et al. 2021
Kim al. 2022 Zhou and Gu 2022 Zhao et al., 2023 Xu al., 2023) where e, bounded with
variance E
9r) Assumption 3.1 subsumes that E 2 = O(az) (but not the boundedness of c,)
because
E(exp(Aee)](Ar
exp(o - of
B[(]G.) = lim 2
lim A-0
X²/2
X2/2
Reward function class. The agent may estimate the reward function that belongs function class F. We focus on the realizable setting where the ground truth reward function satisfies f. E F. An example of the reward function class the family of linear functions denoted by F ife 0 E θ).
where fe (2, a) (0, Φ(zz a)) E [0, 1). e C {w E Rd ||w]|2 S 1} the parameter space, and &: X' x - Rd is feature mapping. We also consider the function class with finite generalized Eluder dimension (Agarwal et al. 2023). defined as follows:
Definition 3.2. Let Z = { be a sequence of context-action pairs, and 3 = {(rcher be positive numbers. The generalized Eluder dimension of the function class JF is given by dimx.r((F) = sup2,3s. dim Z, where
dimx(F,
Σ min L,D (zt, (1-11,
(2) f2(2))
(2,01,11)1,,,,,0--11))) f1.fEEF X D (a(((zz) - f2((z))²
sup
3.2 Feel-Good Thompson Sampling
In Thompson Sampling [Thmmpson] 1933), instead of deterministically estimating the reward function, an estimation of the reward function fi is sampled in step t from the posterior distribution defined as
pf ())S,_) & Po()) exp
Σ L.lf Q..)))
(3.1)

---

where Po(f) is a prior distribution, and L, is the log-likelihood often set as the square loss Ls Ts) = n7(T, fzz a,))² with being a hyperparameter. from Ar to maximize (). However, Zhang (202)) showed that the frequentist regret of vanilla Thompson sampling is suboptimal in the worst case, and proposed Feel-Good Thompson sampling (FGTS) to fill this gap. At the core of FGTS is modification to the posterior distribution called the feel-good exploration term the form A. f (Iz. a). Two types feel-good exploration terms have been developed:
action is then selected
Type A. Agarwal and Zhang 2022). i.c.,
Augment the log- lieeliidl of each step with the feel-good exploration term Zhang 2022
Pt
PGTS- (f(S:-1) po(f) exp
Ei-nrr (I,, + max s(ss.
(3.2)
aeA.
Type B. Only add the feel-good exploration term of the current step DDann et al. 2021
i.e.
FGTS Pt
(f(St-1) Po(f) exp
exp
Σ nr. f(x,, az))² + max f(z,, ())
(3.3)
aEA.
Different from (Zhang 2022) that applied Type of FGTS to contextual bandits, algorithm is more closely related to Type B. We will present details of our posterior distribution Section[4] show the effectiveness of Type B applied to (variance-awarg contextual bandits in Section 5 (although
is originally developed for model-free RL), and explain the reason why Type B is preferred for variance-aware FGTS in Section 6
4 Variance Aware Feel-Good Thompson Sampling
In this section, we sketch our algorithm PCTS-VA Algorithm for contextual bandits with heteroge- neous noise levels. FGTS-VA -VA adopts the general framework of FGTS algorithms where estimation of the reward function fi is sampled from the posterior distribution augmented with the feel-good exploration term, and then the action o, is selected maximize the reward function. Algorithm FGTS VA
1: Given hyperparameter a and y. Initialize Su = 2.
2: for t = 1 to T do
3: Receive context Zz--
4: Set parameters sE(t_11 and de according to (4.2)
5: Sample fo Pr (-1S with the posterior distribution P.(f(S--1 defined in 44.1
6: Sclect a, = argmax fi a).
7: Observe reward rı; update S, St-1 { at,
8: end for
Posterior distribution. Motivated by
3.3). the posterior distribution is designed
Pr(f(St-1) x pf( exp nr f(x,, 0.)) + max f()1,))
(4.1)
aEA:
where parameters 7), and de are chosen as
77 -==0- = =
where o. maxfo a) A Σ 03.
(4.2)
with a and e being hyperparameters. We explain the design of ne and A as follows:
The constructions of n)s and ã, are similar to Zhou et al. (2021), with > beinng hyperparameter
that controls 7) in case of vanishing o² and can be set as ((1/poly(T)) (T)) The coefficient n, functions as preconditioner that balances the squared error (r. f( steps. Compared with our algorithm, Zhou and Gu (202)) and Xu et al. (2023) set o, as maximum of not only d, and but also quantity called the "uncertainty" that depends on the action de- However, this approach prohibitive in our algorithm due the occurrence of a X which is required before the choice of a..
across different
5

---

The parameter A controls the magnitude of the feel exploration term. X scales with o, because intuitively, if the reward of the current step small, then exploration should be encouraged due to the more informative reward feedback. Setting X evAr/ot of achieves the same regret setting A evA/ož (explained in Section 6). and avoids requiring the total variance A at initialization.
Main Results
We first introduce the generalized decoupling coefficient, an extension of the standard decoupling coefficient in Dann et al. (202T) which crucial tool in the analysis of algorithms based on FGTS: Definition 5.1 (Generalized decoupling coefficient). Let Z (Z()TT be sequence of context- action pairs, and B { be positive numbers. The decoupling coefficient is defined as dex,..(F)) = a. de (F, 2,3), where (F, Z, (3 is the smallest number that satisfies
- (z))) S T
T
Bc + (1+ 1 4x
B.(f((z)) - f.(2.))
(F,
Be t=1
1=1
(5.1)
for any sequence (fi)eETT) where fa F and any y 0.
The generalized decoupling coefficient is used to analyze ft(2s, a.) f. (zz, az) where and fe
are dependent random variables because d, selected to maximize fe(().)) in the algorithm design. It relates the error of the current step the error of historic steps f (zx), and generalizes the standard decoupling coefficient (Dann et al. 2021) by introducing undermined parameters 3r. We discuss the relationships of the generalized decoupling coefficient with the standard decoupling coefficient and with other complexity measures as follows:
-
Relationship with standard decoupling coefficient. By fixing 3, = 1, the generalized decoupling coefficient is closely related the standard decoupling coefficient in Dann al. (2021): For any < 1, the standard decoupling coefficient is defined as (F) = supz de' (FF, 2), where de' dc'(F, FF, Z) the smallest number that satisfies
T
T T
+ de' dc)(F.Z)
-(((z)- - fl(2)) SY E - 1=1
(5.2)
4
1=1==
Comparing 5.. and 5.2 two additional terms occur in the definition of the generalized decoupling
coefficient: (i) The term > > 3,- is technical artifact and can be shaved by choosing small X; (ii) The term dex (F, Z, B) is shadowed by de, (F, Z. 34);()))) when 7 S 1 as is the case in (5.2). However, as more flexible choices of both 33 and 7 (possibly > 1) are required, this additional term is unavoidable in the variance-awane setting. The occurrence of this term is due to the possibly large values of B, and will be explained in detail in Appendix (see (A.I)).
Relationship with other complexity measures. For the linear reward function class, we can upper bound the generalized reward function as follows:
Proposition 5.2. For the linear function class Flia, the generalized decoupling coefficient satisfies
(F). < 2d + (dT))
For the general reward function class, the generalized decoupling coefficient can be bounded by the generalized Eluder dimension (Agarwal et al. (023) as follows:
Proposition 5.3. For a reward function class with finite generalized Eluder dimension, the generalized decoupling coefficient satisfies (FF "dixx,,7(F..
The proofs of Propositions 5.2 and 5.3 are given Appendix A
We now present the regret upper bound of FGTS-VA:
Theorem 5.4. Suppose that Assumption 3.J holds, the function class F has finite cardinality, and the prior distribution Po is the uniform distribution on F. Assume that parameters 1), and X are chosen according to (4.)) and the hyperparameters are chosen as
a a= 1/VT, 1=1, e a
c= dc log FF.

---

Then the total regret of FGTS-VA satisfies
E ([Re X v(++ (e..,.((F) (F) log [F] + de
The proof of Theorem 5.4, as well as a more general version of Theorem 5.4 that extends to the case of infinite function class, given in Appendix
Remark 5.5. Under the setting of linear contextual bandits, F can be chosen as the c-net of the unit ball whose cardinality satisfies log [F] (d). Additionally, the generalized decoupling coefficient satisfies dc (d) as is shown in Proposition 5.2 Therefore, when applied to linear contextual bandits, FGTS- VA has a nearly-optimal regret of O(dv + d), similar to UCB-based algorithms
(Zhou and Gu 2022 Zhho et al., (003))
Remark 5.6. Under the setting of deterministic reward, the total variance is A = 0, and the regret of VGTS-VA is O(de Note that the generalized decoupling coefficient upper bounded by the generalized Eluder dimension, which reduces to the standard Eluder dimension (Russo and Van Roy 2013) in the deterministic case. Therefore, the regret of FGTS-VA is minimax-optimal in the deterministic case for the general reward function class (Jia et al. (024)..
Remark 5.7. When of for all / [T), the setting reduces to the standard contextual bandits, and the reward of FGTS-VA VA is Õ(yT
T de log [F] + dc), which is (dv/T) for linear contextual bandits. Therefore, although Dann et al. (2021) only studied FGTS in model-free RL, we have shown that a similar posterior distribution (333) is applicable to the setting of contextual bandits, and enjoys the minimax- optimall regret bound for the linear regret function class similar to Zhang (2022). Additionally, since the parameters are 7/2 and X @dd vi log FF). FCTS-VA is reduced to the first based algorithm that does not require knowledge of the horizon T..
Overview of Proof
We first define several shorthand notations: We use de to denote the (generalized) decoupling coefficient, and denote
AL 2, a) (r- f(, - f(), FG,(f) max f(z,, a) f=(x1, "EA. LS,(f) a.) ax,,,,)))
then the posterior distribution
4.1 is equivalent to
o po() po()) exp
Σ +
(6.1)
Note that the regret step i can be decomposed
(If, f- (~ a:)] ([ az) fo ac)l [f((z,, -
fo (Zx, af)
= [E(((Tz, - fa az) [FFG(()))]
Bellman Frror
where the second equality holds because a4 the maximizer of fe( )). The Bellman error term [[,e( (t) - (x 4:)] is then bounded using the (generalized) decoupling coefficient, which has two versions corresponding
the two types of posterior distributions. In the remaining of this section, we will explain the reason why Type B of the posterior distribution in (3.3) is the basis of our algorithm instead of Type A in (3.2) by first explaining the obstacles in the analysis based on Type A. and then showing how FGTS-W VA built on Type B manages to overcome the obstacle. We will also explain the technical trick in the construction of A
6.1 Technical Obstacle when Applying Type A of FGTS
When applying the posterior distribution similar
3.2
3.2p..e. i.e.
n. I.. + FG.(1)).
P((f(S(-1) & pf((f exp
Although there is 1 + A term in the regret bound of Theorem 5.4 it can be further suppressed by setting be even smaller number.
7

---

the proof developed based on Zhang 2002) requires that π is upper bounded by an absolute constant that is irrelevant to T, which results the regret bound polynomial in T because the occurrence of Σ 1/1 in the regret bound. In detail, by applying the decoupling coefficient for this type of posterior distribution, we have
de
Eif(re a.) (z ae) &
+ Br,
E jmp LS
47
Therefore, it suffices to prove upper bound for
T dc
Es ne jmii [TBBailS LS((F) FF)
(6.2)
4
1=1
We define the potential as
Z Es, log pypo exp Σ AL, x (G,(f, (f,)l)
The proof proceeds by bounding Z. Z and applying the telescope sum. Note that
Zr Z -Es, log E jnp exp ( 1). [ T2, (2) + de FG.(S.
$ Es. log 1og jmpl 81-1) exp( 2n, 2 re) + log J~p( exp(21,
FG, FG.(F,
2
where the inequality holds due to Hölder's inequality. By using the Hoeffding's 's Lemma, the term l2 can be bounded by 2Ap 2xp: FG,
m.)) + 2AP. For the term I, By first taking the conditional
expectation on G. and using Assumption
3.1 we have
|[4 log T-p. exp( 2m ) LS((F).
(6.3)
By choosing f/ S o, 2/2, the coefficient 2n, - n)) can be lower bounded by the To connect 6.3 with (6.2), the RHS of (6.3) has to be bounded by -On) - pi--(-1s_ (f) where C' is an
absolute constant. This is possible only when 7): LS.() (1). Since LS.(F) = (11) in the worst case, 7h should be an absolute constant. Comparing what we obtain against (.2)) we note that (i) A has to be a constant match, we require an undesirable factor of T. Therefore, Type A of FGTS (3.2) cannot yield variance-aware regret bounds with existing techniques, even if inhomogeneous parameters 7/ and X are allowed.
enable the telescope sum of Z Zt-1. and (ii) to make coefficients Cnt/A O(x-1). Thus, the first term of (6.) becomes O(T de), with
6.2 Highlight of Proof Techniques
By proceeding through sharply different path, the analysis of FGTS-VA avoids the aforementioned obstacle that stems from bounding the expectation the exponential term on RHS of (6.3). The following two techniques work together to relate the posterior distribution with the desired form of the decoupling coefficient:
Technique I: Prioritizing expectation over the randomness of reward. Although the expectation of exponential term over the randomness of posterior sampling causes trouble, the expectation over the randomness of adopts simple form due to Assumption 3.1 Therefore, by defining
Eo( Tar Oa, r.) = AL, La. as r.) log E E(exp(- -11 ALA AALJ,
Ls. a,, Ts (9.))
we have the following property (following Dann al. 2021): formalized in Lemma D.I
Es, exp Σ (s,
By using the Jensen's inequality, we have
1
0 = log Ej- Es, 1.a, exp
Σ
Eo( Is. (s,)
8

---

1-1 Ea (e)
2 Es log 1
Trppo exp
(6.4)
Technique 2: KL-regularized optimality. The following lemma is used to remove the exponential on the RHS of (6.4):
Lemma 6.1 (Donsker-Varadhan duality, e.g., Proposition 7.16 in Zhang (2023)) ) Let (K Po) be a probability space and (x) be a measurable function. Then for any distribution P on (X,F), we have
E=>)\U(<)] KL(PIP))) - log E exp(-U(z)),
and the infimum is attained when P(z) x Po(x) exp(-U(x:))
The RHS of Lemma 6.1 contains the expectation of the exponential term, similar the RHS of (6.4) and the LHS is the simple expectation of (-), free of exponential terms. The price of the removal of the exponential is additional KL-divergence term,
Lemma 6. twice cancel the KL-divergence, one using the inequality itself, and the other using the optimality condition:
log Bi-po exp Σ
Biw (,( - KL(p:llpo);
(6.5)
KL( llpo) & Brap
Σ ALLL as + de FG. KL(ppllpo)
(6.6)
Plugging 6.5 and 6.6 into 66.4..
noting that (T,(8,.1pp)) = -log| [Fl. we have
log| F > Es, ma B Binn
log E/x Fa, as,
- FG.(()
LS.(F) -
Es Es, jiwps
(6.7)
where the second inequality holds due to Assumption 3.1 with an argument similar to 6..3
6.. is
thus completely free of the expectation of exponential terms.
Avoiding A in parameters. If we follow the proof of Dann et al. (021)) then we require A 1/(27a])) where 7 scales with A -0.5 which unknown the agent. To resolve this issue, we observe that the proof can proceed by replacing the total variance A with the partial sum A₁- Specifically, dividing d cvA./o? on both sides of the 6.7p. noting that A, Ar, we have
of
o²
1-1
o - F.
log F
ES...
E Jom
C
2evAT
Plugging the inequality into the definition of the decoupling coefficient, we have
x log
F
AvAT
dc S 2VAT [F] + (1+ CVAT de,
E[Regret(T))
(1+
VA
2
where we use the crucial technical lemma (Lemma D.2p stating that Di_10 T./ S 2/AT. Finally, by choosing c = 2 regret can bounded by O (o((a2T + A) de log F dc).
log [F] (which is irrelevant to A) and noting that Ay = Oaa2T AA), the de //
7 Experiments
In this section, we examine our algorithm, FGTS- VA, against baselines (including Weighted OFUL+. FGTS. and SAVE) in experiments with synthetic data. The code can be found at https://githuu com/xuheng- 1 1.99/FFTS-VA.
Environment. We focus on the setting of linear bandits with d = 5 and X' = {x], so we omit the context æ: for simplicity. The action set is A, = A = (+1/VØ)d and the ground truth parameter 0. sampled from the uniform distribution on the unit sphere. We consider two noise models with heterogencous noise magnitudes. In both cases, the noise E, is sampled from (N( of).

---

1. The noise is sparse: of = with probability and of = 0 with probability 1 - p. We set 0.1 in our experiments.
2. The noise is dense: of is sampled from a x² distribution with degree of freedom equal to 1.
Implementation details. For FGTS-VA, in the linear bandit setting, we let the prior distribution be the Gaussian distribution (0, La/d). We use Langevin dynamics to sample from this distribution:
[++1 (8) + g Vlogp((()s-)) + 25(()) Et:
where 6, is the standard Gaussian noise, and 8(k) is the stepsize. We K 20 SGLD steps in experiments, and initialize 0 = k(())
POTS-W with Agurrtana
Compatien NOTS Alprrhia
10
100
205
120 1200
2028
2.2
300
1200 1200
(a) Sparse noise.
(b) Dense noise.
Figure 1: Comparison of different algorithms. Error bands are plotted over 100 runs.
Comparison of different algorithms. We first compare FCTS-VA with c = 0.003 against Weighted OFUL+ (Zoou and Gu 2022). SAVE (Zhao al., 2023), and FGTS (Zhang, 2022) with results in Figure 1
For both data models, FATS-VA outperforms the baselines by a large margin.
Orevaor Diferent.
Oompaniee NOTS Difieent
(a) Sparse noise.
(b) Dense noise.
Figure 2: Comparison of different choices of c. The averages of regret over 100 runs are plotted. Ablation studies. We then perform ablation studies of the algorithm with different choices of It worth noting that c the only tunable parameter of FGTS-VA VA, and c Õ(1) for linear bandits according to Theorem (.44 The results are shown in Figure For the case of sparse noise, we observe the advantage of choosing bounded away from i.c., advantage of the feel-good exploration. For the case of dense noise, the optimal choice of is close to O.
8 Conclusion
In this work, we present FGTS-VA VA, a variance-aware algorithm for general contextual bandits based on Feel-Good Thompson sampling. In the posterior distribution, we incorporate not only variance-related weights, but also feel-good exploration term that adopts the idea from model-free RL (Dann et al. 2021). The generalized decoupling coefficient is the pivotal technique in our analysis, with which we show that FGTS- VA achieves nearly optimal regret bound similar to UCB-base algorithms. A restriction our work the setting of variance revealing, so interesting to explore the possibility of designing FGTS-basee bassd algorithms without requiring the variance of the current step as in Zhou and
Gu (2022), and ultimately without knowing the variance at all similar to Zhao al. (2023). Extending of the techniques in this work to reinforcement learning is also interesting future direction.
10

---

Acknowledgment
We thank the anonymous reviewers and area chair for their helpful comments. XL and QG supported in part by the National Science Foundation and conclusions contained this paper are those of the authors and should be interpreted as representing any funding agencies.
13 and IIS-2403400. The views
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.
ABEILLE, M. and LAZARIC, A. (2017). Linear thompson sampling revisited. In Artificial Intelligence and Statistics. PMLR.
AGARWAL, A., JIN, Y. and ZHANG, T. (2023). Vo qgl: Towards optimal regret in model-free rl with nonlinear function approximation. In The Thirty Sixth Annual Conference Learning Theory. PMLR.
AGARWAL, A. and ZHANG, T. (2022). Model-based rl with optimistic posterior sampling: Structural conditions and sample complexity. Advances in Neural Information Processing Systems 35 35284-35297,
AGRAWAL, S. and GOYAL, N. (2012). Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory. JMLR Workshop and Conference Proceedings.
AGRAWAL, S. and GOYAL, N. (2013). Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning. PMLR.
AGRAWAL. S. and GOYAL, N. (2017). Near-optimal regret bounds for thompson sampling. Journal of the ACM (JACM) 64 1-24.
AUDIBERT, J.-Y., Y., MUNos, R. and SZEPESVÁRI, C. (2009), Exploration-exploittiio exploitation tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science 410 1876-1902.
AUER, P. (2002). Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research 397-422.
CHAPPLLE, O. and L1, L. (2011). An empirical evaluation of thompson sampling. Advances in neural information processing systems 24.
CHU, W., LI, L., REYZIN, L. and SCHAPIRE, (2011). Contextual bandits with linear payoff functions. In Proceedings of the fourteenth international conference artificial intelligence and statistics. JMLR Workshop and Conference Proceedings.
DANN, C., MOIRII M., ZIIANG, T. and ZIMMERT, J. (2021). A provably efficient model-free posterior sampling method for episodic reinforcement learning. Advances in Neural Information Processing Systems 34 12040-12051.
DI. Q. JIN, T., WU, Y., ZHAO, H., FARNOUD, F. and GU, Q. (2023). Variance-aware regret bounds for stochastic contextual dueling bandits. arXiv preprint arXiv:2310.0066.
FAN, Z. and Gu, Q. (2023). The power of feel-good thompson sampling: A unified framework for linear bandits
HAZAN, E. and KALE, S. (2011). Better algorithms for benign bandits. Journal of Machine Learning Research 12.
ITO, S. (2021). Parameter-free multi-armed bandit algorithms with hybrid data-dependent regret bounds. In Conference Learning Theory. PMLR.
ITO, S. and TAKEMURA, K. (2023). Best-of-three- worlds linear bandit algorithm with variance- adaptive regret bounds. In The Thirty Sixth Annual Conference on Learning Theory. PMLR

---

JIA, Z., QIAN, J.. RAKHLIN, A. and WEI, C.-Y. (2024). How does variance shape the regret in contextual bandits? Advances in Neural Information Processing Systems 37 83730-83785.
JIN, T., XU, P., SHI, J., XIAO, X. and GU, Q. (2021). Mots: Minimax optimal thompson sampling.
In International Conference on Machine Learning. PMLR.
KAUFMANN, E., KORDA, N. and MUNOS, R. (2012). Thompson sampling: An asymptotically optimal finite-time analysis. In International conference on algorithmic learning theory. Springer.
KIM, Y., YANG, I. and JUN, K.-S. (2022). Improved regret analysis for variance-adaptive linear bandits and horizon-free linear mixture mdps. Advances in Neural Information Processing Systems 35 1060-1072.
LANGFORD, J. and ZHANG, T. (2007). The spoch-greedy algorithm for multi-armed bandits with side information. Advances in neural information processing systems 20.
LI, L., CIIU, W., LANGFORD, J. and SCHAPPRE, R. E. (2010). A contextual- approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web.
LI, X., ZuAo, H. and GU, Q. (2024). Feel-good thompson sampling for contextual dueling bandits. arXiv preprint arXiv:2404.00013.
LIU, Q., NETRAPALLI, P., SZEPESVARI, C. and JIN, C. (2023). Optimistic mle: generic model- based algorithm for partially observable sequential decision making. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing.
MUKHERJEE, S., NAVEEN, K., SUDARSANAM, N. and RAVINDRAN, B. (2018). Efficient-ucby An almost optimal algorithm using variance estimates. Proceedings of the AAAI Conference on Artificial Intelligence, vol. 32.
OSBAND, I. and VAN Roy, B. (2017). Why is posterior sampling better than optimism for reinforce- ment learning? In International conference on machine learning. PMLR.
RUSSO, D. and VAN Roy, B. (2013). Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems 26.
SAHA, A. and KVETON, B. (2023). Only pay for what is uncertain: Variance-adaptiva thompson sampling. arXiv preprint 2rX1::2303.0003.
THOMMPON, W. R. (1933). On the likelihood that one unknown probability exceeds another in view of the evidence two samples. Biometrika 25 285-294.
WANG, K., OERTELL, O., AGARWAL, A., KALLUS, N. and SUN, W. (2024a). More benefits of being distributional: Second-order bounds for reinforcement learning. arXiv preprint arXiv:2402.07118.
WANG, Z., ZHoU, D., LUI, J. and SUN, W. (2024b). Model-based rl as minimalist approach to horizon-free and second-orded bounds. arXiv preprins arXiv:2408.089% 08994.
WEI, C.-Y. and LUO, H. (2018). More adaptive algorithms for adversarial bandits. In Conference On Learning Theory. PMLR.
WEI, C.-Y., LUO, H. and AGARWAL, A. (2020). Taking a hint: How to leverage loss predictors in contextual bandits? In Conference on Learning Theory. PMLR.
XU, R., MIN, Y. and WANG, T. (2023). Noise-adaptive thompson sampling for linear contextual bandits. Advances in Neural Information Processing Systems 36 23630-2363 23657.
ZHANG, T. (2022). Feel-good thompson sampling for contextual bandits and reinforcement lcarning. SIAM Journal on Mathematics of Data Science 4 834 857.
ZHANG, T. (2023). Mathematical analysis of machine learning algorithms. Cambridge University Press.
12

---

ZHANG, Z., YANG, J., JI, X. and DU, S. S. (2021). Improved sariance-awary confidence sets for linear bandits and linear mixture mdp. Advances in Neural Information Processing Systems 34 4342 4355.
Ziao,, H., HE, J., ZIOOU, D., ZIIAGG, T. and GU, Q. (2023). Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency. In The Thirty Sixth Annual Conference on Learning Theory. PMLR.
ZHOU, D. and GU, Q. (2022). Computationally efficient horizon-free reinforcement learning for linear mixture mdps. Advances in neural information processing systems 35 36337-36349.
ZHOU, D., GU, Q. and SZEPES VARI, C. (2021). Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference Learning Theory. PMLR.
13

---

A Generalized Decoupling Coefficient
A.1 Linear Reward Function Class
In this section, prove the decoupling coefficient for linear contextual bandits. We assume that
0. = 0 without loss generality. We use the shorthand notation Φe == ((Tz, Oz), and define
= XI+ Σ S.0.0.
The following lemma. known the elliptical potential lemma, is well-known result in previous works (Abbasi- Yadkori et al. 2011: Zhou and Gu 2022):
Lemma A.1. For any À >> 0, we have
min Bellob E .1 I 2(log det Er) - log dee((Eo)) & logo + (dT)
With Lemma A.1 smaller than I,
we decompose the sum of (0e, Φb) into cases based whether Be 1 is
T
T 0r. Φ.)
Or, Φ.) Σ
00, Φe) 1 Bell 1lllob.l12 2 +
Bellob >
(A.1)
12
For any 7 >> 0, the term J satisfies
T
1
3,
1/2
0
1
[ s
1
1=1
T
<
3:
1/2
min { 110
1=1
T
T
1
0,
1
+
min
Bell0b x
3t
47
1=1
t=1
T
di
1110
Σ
B, (0 0z)²)
3
27
t=1
$ >1
Σ
7
1-1 (0, Φ2)²
di
(A.2)
3
B
27
where the first inequality holds due to AM-GM inequality, the second inequality holds because
1[z < < min 1). the third inequality holds due Cauchy-Schwar Schwarz inequality, the fourth inequality holds due to Lemma A. and the last inequality holds because ||0,|l2 S 1. The term l2 satisfies
T L S I
1
Σ min (illsrlls .11 s 2ds,
(A.3)
where the first inequality holds because min 1, 2. < 1, the second inequality holds because
[[ > 1] < min(z, 1), and the last inequality holds due to Lemma A.I Plugging (A.)) and (A.3)
into A. b, we have
T
T
O., ).) 5
0r,
).)
+
+ 2di
1 1rr
3
3.
14

---

A.2 General Reward Function Class
In this section, we relate the generalized decoupling coefficient the generalized Eluder dimension (Agarwal et al. (023). The proof is similar to that of the linear reward function. We first make the following decomposition:
E(e(ee - fa(x)) = Σ -
( (es S
T
+ -((2))ff(=)))) ( 1
(A.4)
The term 11 satisfies
T
8 1/12 (fe(z)
Do(2t:2p-1).B111 ) (2 (y
D2(2: B1-1 $ $11)
1
Br (1(z)) - -o((z))
min { Dy (1-11 B/c (1-))))
$
Dy (
- (z))) 7 (
Σ
91-1))) min (1
Be
(2, (((-1))
47
Σ
- -.((e)))))
dim 3)
Br
4y
T 1-1 Σ Ba(f((z)) - f2(2))) + 7
T
dim,,I(F)
Σ 1=1
(A.5)
B1
47
where the first inequality holds because [[ 1] min(2, 1}. the second incquality holds due
to AM-GM inequality, the third inequality holds due to the definition of (rt ( 11, and the definition of dim(F,Z, Z), and the last inequality holds because dim,,r (F) sup, dim 2,3), The term I2 satisfies
B/1-1)
1 S Σ min { (1 71- //- = dim(F (.mnFFZ,,))
2, < dim., (F),
(A.6)
where the first inequality holds because ff I 1, the equality holds due the definition of dim(F. 3. and the last inequality holds because because dim,,r(F) = supz,age dim(F, 3)) Plugging (A.5) into (A.6), have
[-1
T 1
1 47
Σ - S
Σ
+
1
dim..((F)
B
B
B Proof of Main Theorem
In this section, we first provide general version of Theorem 5.4 Theorem B.I. Define
t-1
CVAr
Z, Es,.,.. log E
E exp
jupo
Σ σ. A x. as)
of
FG.(F)
(B.1)
7 1V sup Z.- (a.hem LE|T
(B.2)
Suppose that the parameters set in (42 and the hyperparameters
A= 1, 6=0 c= 2 7/ dox.e.
15

---

Then the total regret satisfies
9 S 4 (a²T + A)Z dex, (F) + dex.e, (F).
E [[Regret
To prove Theorem B.1 we need the following lemma:
Lemma B.2. Under the conditions of Theorem B.1 the following inequality holds:
t-1 0
(s) - FG,(F) -
& oī
Es 2e
0.
Zz
Trpp
2evA A
c/A,
==1
We show the proof of Lemma B.2 in Appendix
C.1
We now provide the proof of Theorem B.1
Proof of Theorem B.1
The regret can be decomposed as
T
Regret(t)
Lff((e an) f+(2,, - FGo(ff)
t=1
1=1
3. (f)) FG. -F.))) + 72
Σ B
+
1 (1+ 47
(F)..
(B.3)
where the equality holds due to the optimality of a,, and the inequality holds due to the definition of the generalized decoupling coefficient. Taking the expectation on both sides of (B.3). we have
E (Regget (T)
S
B. (... FG.(O)
71
(1+ 47
de).,(())
B
B
Σ E S.
T-mpe
Be
3, LF) FG,
+ +nd
1 B
+
(1+
47
de de
where the equality holds due to the double expectation theorem and because neither (S.(fi) (fi) explicitly contain ae By selecting Bg o, 2 and y 1/(2ovAT)) can use Lemma B.2 to further bound the regret:
T
E(Regret(T))
AvAT + (1+
CVTT
(c Σ
o
Zz
2
CvA
AvAT
+ (1+
AVAT
dcx., (F) + 2 Σ
T
0,
2c
2
Ar
1=1
AVAT + (1
CV
dex.e.(FF) + Z Z
2c
2
where the second inequality holds due to the definition of Z, and the last inequality holds due to Lemma D.2 Plugging in = 2/ Z/ dcx,,.T(FF. we have
dex., T (F)AT + 2 Z (dcx dF)...(F))
[[Regret <
Z
7 (des...(F)AA (F)..(FF)
TV
(a2T + dcx.,. + (F))...(FFFF
where the second inequality holds because = and Z 2 1, and the last inequality holds because -T 1= (o? + +a²)
Ar = E max(o?, a²) <
In order to prove Theorem 5.4 from Theorem B.1 note that 7 S log [F] using the argument in
I/VT, we can prove Theorem B. and by selecting be even smaller number, we can prove further shave the term aT + A.
Section 6 By selecting
In order to deal with the infinite function class, need the following lemma to characterize Z:
16

---

Lemma B.3. Suppose that d; is uniformly bounded by a, and the hyperparameter satisfies a S 1. Define
a² 8 27
min (1,0
Then Z satisfies
f log Po (oF((f)))
2 VT
For the linear reward function class where è is the unit ball, we have (o - O(d) according to Zhang 2022).. Therefore, the regret of FGTS-V -VA in linear contextual bandits is O(dvA+ d), even if F is not the e-net.
C Proof of Lemmas in Appendix B
C.1 Proof of Lemma B.2
Proof. We aim to apply Lemma D.I
so for any E 1], we define F, (..
o, Of Zn azs rs), then by Lemma D.I have
0 - log E j~po Es exp
<- S...... log E j~po exp Σ (e.f.az,0011))
(C.1)
where the inequality holds due to the Jensen's inequality. We then Lemma 6.1 twice:
1-1
- -log jmpo exp
Σ
s Rimps
Σ
EalF, as asi
+ KT(P:llpo),
mml
mm1
(C.2)
t-1
(-2 Σ o. -o FGI(N)
llg japo exp
1-1 = -jj
Lf 2f, x1 FG.(F)) + KL((lllPo).
(C.3)
#=1
Furthermore, since
(e) = = - F(re: 0z)) (r. fa(2,, a=))
=0,> fa a,) ax)) e?)
- 2c,0 (f(rs,) as) - (x(5,
we have
log El E(xpppx((-Fjp FF.(F as g.)
=- (() fx,, ((),)) S -T, + (3 -2T..
S 2-5.2/2 (LS(
(C.4)
where the first inequality holds due to Assumption o I T. Plugging (C.2)
3.1 and the second inequality holds because C.3) and C.4) into C..l we have
< Es, 1.
Bi-m
Σ Eo Es (.
+ KL(p-lloo))
2 Althoughh Zy has additional terms in a and c, they can be shaved by carefully choosing hypermeters in Theorem B.I
17

---

AL as, - de FG.(() + +pT(pellpo)
1,
E
Jnupt
==1
t-1
+
E
log
Blep(e Ts. Oz, ag. ro)]][i]] + j.b. FG)
Sope
Σ 0 3 aL Is, V.) + de FGa(T)
< -Es, 1 log jupo exp
0g
LS.(F) + da FG1(f)
+ Es an E
Srups
2
8=1
Rearranging terms and plugging in A co2 VA, we obtain
2 (f) FG.(T)
E Es
20vA A
o
t-1
LS.(F) FGI(1)
$ Es. By
FT-pi
o
20V At
==1
exp where the first inequality holds because A S A.
< Es
0 1.
log
E
J~po
Σ
1-1
0, PL[L( to,
AvAr
rG((n)
cvA,
8=1
C.2 Proof of Lemma B.3
Proof of Lemma
B.3
We note that for any f E FF(f.), we have
0 2 [T 0z: r.) + cvA FG,(f)
o
8=1
A.
Σ o, 22e, (f(x:, ag) - fo (z, - (f)
FG.(f)
of
o.- (le,10 c5vA,
(C.5)
=
Therefore, -Ze can be lower bounded as
(-1
2 AL(F (L, + CVA,
FG((F)
Zz= Es, log E j~po exp
0.
> Es 1. log (Po(F((f))
inf exp JEF
Σ
f-1
AL(S, Is. Ts) + oo
ovAr
rG.(n)
1-1
2 (oggo(FF((a)) + Es. ES-11.1
Σ
((c,10 + 82)
-
o²
s=1
52
c5
2
Σ ==1
+
20,
02
oī
where the first inequality holds because for any function F(x) > 0, we have E[F(x)] 2 E[F(x) [[r E C]] 2 p(C))(infaec F(x)], the second inequality holds due to CC.5). and the last in-
equality holds because ElG, S / S vo2/4 < 0./2. By choosing 8 = a² min(1/o, (2(() we have
1
a?
1
Z, < log
+
s log log po(Fo(f-))
Po (o(F)(f-)
47
2VT
2 VT
where the second inequality holds because S and T > 1.
18

---

D Auxiliary Lemmas
Lemma D.I. For any function F: F X A R RR define
Elff 2t, ae, re) = -F(lF, It, ae, r2) - log E[cxp(- Fe(F, ( 2e, ae, at, r.))
Then for all f and all f F, we have
Es. exp [E((f.,,, =
Proof. We prove the lemma by induction. The property holds trivially for t = 0. Now suppose that the lemma holds for then that
Elexp(E. (F. 3z, at, rz)) [.]
FelJ, Tt, az, rt) log = exp
or rz)) Gi
exp(-Fo(I1 dr: rz))
Gr 1,
(D.I)
E Elexp(-Fe(f. It, ar, G.)
where the first equality holds due the definition of E.s and the last equality holds because the denominator belongs to Gr. We then have
Σ
Es, exp
E
exp
EolF
(s)
Blexp(Ex Øo, a, a,) Gi]
Σ L. (a)
E exp
where the first equality holds due the double expectation theorem and because (, 2,. ag Ts) G for all 5 [t - 1], the second equality holds due to (D.T). and the last equality holds due to the induction hypothesis. Combining all the above, the lemma holds for all by induction.
Lemma D.2. Let o, and A, be defined in (.2).
Then the following property holds:
62
Σ
22 <TVAT. AT.
V
Proof. We note that
T
A-1
T 2
of
A (V A-1)
A--1
2VA
[=1
where the first equality holds due to the telescope sum and because Ao 0, and the inequality holds because A-1 < A, and of = A,- At-1-
19

---

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

---

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

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We have uploaded the code to GitHub.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https httpollccgguiee///ee www.dddueeeoeeuummiicae htt.summmmssiooooooooooooo ssiocyolccy for more details.
/
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if' applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provided the experiment details.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification:
We included the error bands.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
22

---

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

---

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

---

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

---

Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should not be described.
26


Reviews:
[{"review_id": "wUqXm54sUB", "reviewer": "Reviewer_tepv", "summary": "The paper studies the problem of regret minimization for contextual bandits. More specifically, they study the setting of \"weak adversary with variance revealing\" in which the noise (or an upper bound of the noise) is revealed to the learner at each time step. In that setting, previous work obtain a regret bound scaling with the cumulative variances $\\lambda$ and the dimension $d$ at a rate $d \\sqrt{\\Lambda} + d$ for UCB-based methods and at a rate $d^{1.5} \\sqrt{\\Lambda} + d^{1.5}$ for Thompson Sampling based methods. The authors bridge this gap and propose an adaptation of the Feel-Good Thompson Sampling algorithm that attains the correct scaling with respect to the cumulative variance and the dimension. To do that, they propose a new version of the decoupling coefficient, the generalized decoupling coefficient that controls the Bellman Error in a variance-aware way. Then, they propose a new analysis of the Feel-Good Thompson Sampling algorithm that doesn't rely on the usual telescoping analysis of exponential weights. This allows them to use time-dependent learning rates and control the regret of their algorithm in a variance-aware way.", "questions": "- The fact that this analysis doesn't use the telescoping argument is quite surprising to me, in particular, it's not required that the learning rates are increasing or decreasing which is often the case for this type of analysis. While I agree with the technical details I would like to have a higher level understanding of the analysis. Could you provide a very high level of this part of the analyis and in particular why the telescoping is not needed anymore ?\n- If it were possible to use time-varying learning rate(and still telescope Z_t - Z_t-1) with Type-A FGTS, would it be possible to adapt to the variance ?\n- Is there a way to tune the other hyperparameters of the algorithm (like c) to obtain an anytime algorithm ? If not, what are the main limitations ?\n- Could the techniques of this paper be adapted to the \"strong\" adversary case ?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The main result of the paper shows that Thompson-Sampling based method can obtain the same variance-aware rate as UCB based methods. Moreover, as noted by the authors, their algorithm can accomodate time variying learning rates and doesn't require previous knowledge of the total variance. This results holds with a high degree of generality as it mostly requires bounded generalized eluder dimension. \nThe analysis is also insightful, they show the limitations of the usual telescoping analysis of the exponential weights algorithms when dealing with the concurrent choice of the learning rates. They show how to circumvent this limitation by avoiding the telescoping all together. The work of relating the instantaneous regret to the potential of the exponential weight is then handled by the generalized decoupling coefficient and some careful analysis. The arguments they use are (to my knowledge) new and could be used beyond the scope of this paper to analyze exponential weights algorithms.\n\nThe main limitation of the result is that the algorithms requires the knowledge of $\\sigma_t$ unlike the SAVE algorithm mentionned in previous work. Also, while the algorithm is able to scale with the cumulative variance $\\Lambda_t$, the algorithm is not anytime as only $\\nu_t $ and $\\lambda_t$ are scaling with time. The rest of the hyperparameters need to be set with knowledge of the horizon.\n\n\nThe analysis is somewhat difficult to follow in its current form. A significant portion of the main paper focuses on illustrating the failure modes of Type A FGTS, which results in many crucial elements of the new analysis being deferred to the appendix. As a consequence, the presentation feels scattered. It would greatly improve clarity to include a few introductory lines in the main text that summarize the gist of the analysis starting from the regret and Bellman Error Feel-Good decomposition, introducing the generalized decoupling coefficient, and then outlining the bounds on the LS and FG terms. For example, Line 307 is difficult to interpret without such context.\n\nAdditionally, there are some missing details, unclear references, and minor errors or typos that hinder comprehension:\n\n* In the main text, pointers to the appendix are not always clear. For instance, Line 301 states: “the second inequality holds due to Assumption 3.1 with an argument similar to (6.3). (6.7) is thus completely free of the expectation of exponential terms,” but does not clearly indicate where in the appendix the relevant derivation can be found.\n* Conversely, the appendix sometimes refers imprecisely to the main text. Line 461, for example, states: “we note that $Z \\leq \\log |\\mathcal{F}|$ using the argument in Section 6,” without a clear pointer to the specific argument.\n* In Line 121, there is a typo, the cumulative variance is not appearing in the regret bound.\n* Line 209: The decoupling coefficient should be defined such that the stated relationship holds for any $\\gamma$.\n* Line 270: The function to which Jensen’s inequality is applied is not explicitly stated. Since the function involved is the log-sum-exp, whose convexity is less immediate than that of more common functions, it would be helpful to mention this explicitly—or alternatively, use Hölder’s inequality.\n* Lemma 6.1 is cited as originating from Zhang (2023), but it is actually the well-known Donsker–Varadhan duality formula for the KL divergence.\n* Lines 192–193 mention that $\\sigma_t$ is revealed to the agent at the beginning of step $t$, and that this defines the “weak adversary” setting. This should ideally be clarified earlier in the paper, when the setting is first introduced.\n* Line 216 refers to an additional term in the generalized decoupling coefficient as arising from potentially large values of $\\beta_t$, with a promise of further explanation in Appendix A. However, the appendix contains little elaboration on this point.\n* The choice to set the hyperparameter $\\epsilon = T$ is surprising and counterintuitive, as one typically expects $\\epsilon$ to be a small quantity. This can be confusing at first (I initially assumed it was a typo). Moreover, this choice introduces an additional $\\log T$ factor in the generalized decoupling coefficient for the linear function class. When combined with the $\\log |\\mathcal{F}|$ term in the regret, it appears that the logarithmic term lies outside the square root, unlike in UCB-based methods where it is typically inside.", "was_revised": true, "final_justification": "Given the answers of the authors, I maintain my positive view of the paper.", "rebuttal": "**Q1 (Hyperparameters).** While the algorithm is able to scale with the cumulative variance $\\Lambda_t$, the algorithm is not anytime as only $\\lambda_t$ and $\\mu_t$ are scaling with time. The rest of the hyperparameters need to be set with knowledge of the horizon.\n\nThe choice to set the hyperparameter $\\epsilon$ is surprising and counterintuitive, as one typically expects $\\epsilon$ to be a small quantity. This can be confusing at first (I initially assumed it was a typo). Moreover, this choice introduces an additional $\\log T$ factor in the generalized decoupling coefficient for the linear function class. When combined with the $\\log|\\mathcal F|$ term in the regret, it appears that the logarithmic term lies outside the square root, unlike in UCB-based methods where it is typically inside.\n\nIs there a way to tune the other hyperparameters of the algorithm (like c) to obtain an anytime algorithm ? If not, what are the main limitations ?\n\n**A1.** We would like to remark that the choice of hyperparameters $\\lambda$, $\\alpha$, and $\\epsilon$ is less restricted than $c$, $\\mu_t$, and $\\lambda_t$. We first briefly discuss the reason we set the hyperparameters as in Theorem 5.4:\n\n- *Selection of $\\lambda$.* We set $\\lambda=1$ for simplification.\n- *Selection of $\\alpha$.* The upper bound depends on $\\Lambda_T=\\sum_{t=1}^T\\max\\lbrace\\sigma_t^2, \\alpha^2\\rbrace\\le\\alpha^2T+\\Lambda$. We select $\\alpha=1/\\sqrt T$ to make $\\alpha^2T=O(1)$.\n- *Selection of $\\epsilon$.* $\\epsilon$ is the upper bound of $\\beta_t$. Since $\\beta_t=\\bar\\sigma_t^{-2}=\\sigma_t^{-2}\\wedge\\alpha^{-2}\\le\\alpha^{-2}$, we set $\\epsilon=\\alpha^{-2}$. We agree that $\\epsilon=T$ may cause confusion because $\\epsilon$ is usually small, and will change $\\epsilon$ to $B$.\n\nIt is possible to choose these hyperparameters to achieve an anytime algorithm, under mild assumptions. If $T$ is not known, we can still choose $\\alpha=1/\\sqrt{\\hat T}$ if $\\hat T$ is an upper bound of $T$ that can be polynomial in $T$, as long as the generalized decoupling coefficient depends logarithmically on $\\epsilon$. We would disagree with the reviewer on the $\\log T$ term instead of $\\sqrt{\\log T}$ because $\\log|\\mathcal F|$ does not depend on $T$.\n\n---\n\n**Q2.** The analysis is somewhat difficult to follow in its current form. A significant portion of the main paper focuses on illustrating the failure modes of Type A FGTS, which results in many crucial elements of the new analysis being deferred to the appendix. As a consequence, the presentation feels scattered. It would greatly improve clarity to include a few introductory lines in the main text that summarize the gist of the analysis starting from the regret and Bellman Error Feel-Good decomposition, introducing the generalized decoupling coefficient, and then outlining the bounds on the LS and FG terms. For example, Line 307 is difficult to interpret without such context.\n\n**A2.** We appreciate the reviewer for the suggestion. We will add details about the application of the generalized decoupling coefficient to the analysis of the Bellman error term.\n\n---\n\n**Q3 (Weak adversary setting).** The main limitation of the result is that the algorithms requires the knowledge of $\\sigma_t$ unlike the SAVE algorithm mentioned in previous work.\n\nCould the techniques of this paper be adapted to the \"strong\" adversary case?\n\nLines 192–193 mention that $\\sigma_t$ is revealed to the agent at the beginning of step $t$, and that this defines the “weak adversary” setting. This should ideally be clarified earlier in the paper, when the setting is first introduced.\n\n**A3.** It would be hard to design a FGTS algorithm without knowing the variances using the current techniques: The term corresponding to step $t$ in the definition of the generalized decoupling coefficient is $\\sum_{s=1}^{t-1}\\frac{\\beta_s}{\\beta_t}(f_t(z_s)-f_*(z_s))^2$, which depends on not only $\\beta_s$ for $s<t$ but also $\\beta_t$ that scales with the variance of the current step. Therefore, when choosing hyperparameters given the result in (6.7), the parameters in step $t$ unavoidably depends on $\\sigma_t$. Given the success of UCB-based algorithms like SAVE, we conjecture that a FGTS-type algorithm without knowing the variances can be designed if a new analysis framework is developed that (i) avoids the decoupling coefficient and (ii) derives a high-probability bound of the term $\\mathrm{LS}_t$ instead of the bound in expectation.\n\nWe will clarify the weak adversary setting right after Assumption 3.1 in the revision of our manuscript.\n\n---\n\n**Q4 (Reference between main text and appendix).** In the main text, pointers to the appendix are not always clear. For instance, Line 301 states: “the second inequality holds due to Assumption 3.1 with an argument similar to (6.3). (6.7) is thus completely free of the expectation of exponential terms,” but does not clearly indicate where in the appendix the relevant derivation can be found.\n\nConversely, the appendix sometimes refers imprecisely to the main text. Line 461, for example, states: “we note that $Z\\le\\log|\\mathcal F|$ using the argument in Section 6,” without a clear pointer to the specific argument.\n\nLine 216 refers to an additional term in the generalized decoupling coefficient as arising from potentially large values of $\\beta_t$, with a promise of further explanation in Appendix A. However, the appendix contains little elaboration on this point.\n\n**A4.** We will clarify these claims in the revision:\n\n- The derivation of (6.7) corresponds to Lines 476-477 in the appendix\n- Line 461 corresponds to (6.6) and Line 300 of the main text.\n- The case of large $\\beta_t$ corresponds to the second term on the righthand side of (A.1).\n\n---\n\n**Q5.** Type in Line 121: missing total variance; Line 270: Equality holds by Hölder’s inequality.\n\n**A5.** We appreciate the reviewer for pointing out the typo, and will continue working on refining our writings.\n\n---\n\n**Q6.** The decoupling coefficient should be defined such that the stated relationship holds for any $\\gamma$.\n\n**A6.** We would like to point out a misunderstanding of the reviewer: The requirement of $\\gamma\\le1$ is not a typo. The reviewer could refer to Theorem 1 of Dann et al. (2021).\n\n---\n\n**Q7.** Lemma 6.1 is cited as originating from Zhang (2023), but it is actually the well-known Donsker–Varadhan duality formula for the KL divergence.\n\n**A7.** We appreciate the reviewer for pointing out the name of this property. We will modify the reference in the revision.\n\n---\n\n**Q8.** The fact that this analysis doesn't use the telescoping argument is quite surprising to me, in particular, it's not required that the learning rates are increasing or decreasing which is often the case for this type of analysis. While I agree with the technical details I would like to have a higher level understanding of the analysis. Could you provide a very high level of this part of the analyis and in particular why the telescoping is not needed anymore?\n\n**A8.** The observation of the reviewer is very insightful. We provide a high-level explanation as follows:\n\nWe actually implicitly use the telescope sum when bounding the generalized decoupling coefficient for the linear reward function class. The proof of Lemma A.1 (elliptical potential lemma), we can lower bound $\\log\\det(\\Sigma_t)-\\log\\det(\\Sigma_{t-1})$ with $1/2\\cdot\\beta_t\\||\\phi_t\\||\\_{\\Sigma_{t-1}^{-1}}^2$ and apply telescope sum.\n\nFrom a high level, the regret bound should be characterized with the **information gain**, and should use the telescope sum somewhere in the proof. For Type A of FGTS, the information gain is $Z_t-Z_{t-1}$, and for Type B, the information gain is $\\log\\det(\\Sigma_t)-\\log\\det(\\Sigma_{t-1})$. The decoupling coefficient of type A of FGTS does not involve the information gain, and the upper bound of the decoupling coefficient for linear reward functions only uses the linear structure. Therefore, the information gain is explicit in the proof for Type A of FGTS.\n\n---\n\n**Q9.** If it were possible to use time-varying learning rate (and still telescope $Z_t-Z_{t-1}$) with Type-A FGTS, would it be possible to adapt to the variance?\n\n**A9.** We have tried this approach, but unfortunately it does not work. We have made an explanation in Section 6.2: The telescope sum analysis relies on the RHS of (6.3) being linear in $\\eta_t\\mathrm{LS}_t(\\tilde f)$. However, this is possible only when $\\eta_t\\mathrm{LS}_t(\\tilde f)\\lesssim1$. Since $\\mathrm{LS}_t(\\tilde f)$ is in the order of a constant in the worst case, $\\eta_t$ cannot be $\\bar\\sigma_t^{-2}$ when $\\sigma_t$ is close to zero.\n\n---\n\nDann et al. A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learning. 2021."}, {"review_id": "YkEdC7jZPc", "reviewer": "Reviewer_3xSL", "summary": "This paper proposes FGTS-VA, a new variance-aware Thompson Sampling algorithm for contextual bandits that achieves optimal regret bounds. The key innovation is incorporating variance-dependent weights and a \"feel-good\" exploration term into the posterior distribution, allowing it to handle general reward functions while matching the performance of UCB-based methods. Theoretical analysis introduces a generalized decoupling coefficient to prove regret bounds for linear bandits, which is minimax optimal and improves upon prior TS approaches. Though requiring known variances, this work represents significant progress in making Thompson Sampling both theoretically sound and practically competitive for variance-sensitive bandit problems.", "questions": "1. Is it possible to design a feel-good Thompson Sampling type algorithm without needing to know the variances?\n\n2. Could you explain in more intuitive terms how the generalized decoupling coefficient differs from standard decoupling coefficients?\n\n3. How does the feel-good exploration term in Type B posterior differ fundamentally from Type A in handling variance awareness? Why does Type A fail in this setting?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1. Theoretical guarantees of this paper are sound, when the variances are known, the upper bound of the algorithm matches the UCB-type algorithm.\n\n2. The writing of this paper is clear and complete, and they also mentioned the technical challenges in the proofs.\n\nWeaknesses:\n\n1. This algorithm requires knowing the variances, but for UCB-type algorithms in the field of Variance-Aware contextual bandits, there are already good algorithms like Save+, which do not need to know the variances for prior knowledge. This means that the algorithm proposed in this paper can not match the state-of-the-art in UCB-type algorithms.\n\n2. The algorithm design seems to be just a trivial combination of weighted linear regression and feel-good Thompson Sampling.\n\n3. There are no empirical studies in this paper.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the positive review!\n\n---\n\n**Q1.** This algorithm requires knowing the variances, but for UCB-type algorithms in the field of Variance-Aware contextual bandits, there are already good algorithms like Save+, which do not need to know the variances for prior knowledge. This means that the algorithm proposed in this paper can not match the state-of-the-art in UCB-type algorithms.\n\n**A1.** We believe that the setting where variances are known is a starting point for developing truly variance-dependent algorithms. We will continue working on this direction.\n\n---\n\n**Q2.** The algorithm design seems to be just a trivial combination of weighted linear regression and feel-good Thompson Sampling.\n\n**A2.** We would like to point out a misunderstanding of the reviewer: Although the algorithm looks like FGTS + weighted linear regression, the selection of parameters $\\lambda_t$ and the definition of generalized decoupling coefficient constitute novel technical contribution of our paper. In UCB-based algorithms, there is no parameter $\\lambda_t$ that controls feel-good exploration, and in FGTS for standard contextual bandits, $\\lambda_t$ is $1/\\sqrt T$. We are the first to use the partial sum of the variances $\\Lambda_t$ in variance-aware bandit algorithms. The definition of the generalized decoupling coefficient is also nontrivially different from the generalized Eluder dimension due to the introduction of parameters $\\beta_t$.\n\n---\n\n**Q3.** There are no empirical studies in this paper.\n\n**A3.** We appreciate the reviewer for the suggestion. We will add experiments on the following setting:\n\n- Linear reward function: The context set has a single element, and will be omitted. The action set is $\\{\\pm 1/\\sqrt d\\}^d$. We assume that $f_*(\\mathbf a)=\\langle\\theta_*, \\mathbf a\\rangle$ where $\\theta_*\\in B(0, 1)$.\n- Variances: We assume that the noise $\\epsilon_t$ is Gaussian with variance $\\sigma_t^2$ either sampled from some distribution (e.g., $\\chi^2$ distribution) or being sparse (only nonzero in a few steps).\n- Baselines: We will compare `FGTS-VA`, standard `FGTS`, `SAVE`, and Weighted-OFUL+.\n\n---\n\n**Q4.** Is it possible to design a feel-good Thompson Sampling type algorithm without needing to know the variances?\n\n**A4.** It would be hard to design a FGTS algorithm without knowing the variances using the current techniques, mainly due to the generalized decoupling coefficient: The term corresponding to step $t$ in the definition of the generalized decoupling coefficient is $\\sum_{s=1}^{t-1}\\frac{\\beta_s}{\\beta_t}(f_t(z_s)-f_*(z_s))^2$, which depends on not only $\\beta_s$ for $s<t$ but also $\\beta_t$ that scales with the variance of the current step. Therefore, when choosing hyperparameters given the result in (6.7), the parameters in step $t$ unavoidably depends on $\\sigma_t$. Given the success of UCB-based algorithms like SAVE, we conjecture that a FGTS-type algorithm without knowing the variances can be designed if a new analysis framework is developed that (i) avoids the decoupling coefficient and (ii) derives a high-probability bound of the term $\\mathrm{LS}_t$ instead of the bound in expectation.\n\n---\n\n**Q5.** Could you explain in more intuitive terms how the generalized decoupling coefficient differs from standard decoupling coefficients?\n\n**A5.** The term of major importance in the definition of the generalized decoupling coefficient is $\\sum_{t=1}^T\\sum_{s=1}^{t-1}\\frac{\\beta_s}{\\beta_t}(f_t(z_s)-f_*(z_s))^2$. The main difference from the standard decoupling coefficient is the introduction of $\\beta_t$. Intuitively, these weights makes the terms $\\beta_s[(r_s-f_t(z_s))^2-(r_s-f_*(z_s))^2]$ more balanced. The additional $\\frac1{\\beta_t}$ serves as a normalization factor that cancels out with $\\beta_s$ when the variances are homogeneous.\n\n---\n\n**Q6.** How does the feel-good exploration term in Type B posterior differ fundamentally from Type A in handling variance awareness? Why does Type A fail in this setting?\n\n**A6.** The failure of Type A posterior attributes mainly to the analysis technique that depends on the difference of the potential $Z_t-Z_{t-1}$. The log-sum-exp term causes minor gain when the variance is small compared to when the variance is large. A major difference in Type B posterior is that it can incorporate information of the current step. It would be interesting to draw intuitions about how this difference results in the failure of Type A but success of Type B, but currently, our preference for Type B is solely due to technical considerations."}, {"review_id": "NqFaZNFXf4", "reviewer": "Reviewer_5NwX", "summary": "The paper introduces **FGTS-VA**, a variance-aware variant of Feel-Good Thompson Sampling for contextual bandits.  The algorithm samples a reward model from a modified posterior that (i) weights squared-loss terms by the per-round noise variance and (ii) adds a “feel-good” exploration bonus.  A new **generalized decoupling coefficient** \\(dc_{\\lambda,\\varepsilon,T}\\) is defined to control the dependence between the sampled model and the action it optimizes; it upper-bounds to \\(O(d)\\) for linear models and to the generalized Eluder dimension for arbitrary function classes.  The authors prove an expected regret which matches the best known UCB-style bounds for linear bandits and collapses to \\(O(\\tilde d)\\) in deterministic settings.", "questions": "### Questions and Suggestions\n1. **Variance-revealing assumption** – Many real systems do not expose \\(\\sigma_t^2\\).  Could the method be adapted with online variance estimation, or maybe a doubling scheme?  Even a heuristic discussion would help.  \n2. **Computability of \\(dc_{\\lambda,\\varepsilon,T}\\)** – In practice, how would one estimate or bound the generalized decoupling coefficient for non-linear models?  Any thoughts or heuristics?\n3. **Finite vs. infinite \\(\\mathcal F\\)** – The main theorem requires a finite function class with a uniform prior. Remark 5.5 talks about the linear case with F being set to an \\epsilon net of the unit ball. What about general function classes? A complete analysis with an epsilon net argument is missing. Also in comparison to the IGW methods (https://arxiv.org/pdf/2107.02237, https://arxiv.org/pdf/2107.02237), if we assume finite arms K, would the bound only depend on K and not something like log |F| or Eluder dimension?\n4. **Empirical check** – A small simulation (e.g., linear bandit with heteroscedastic noise) comparing FGTS-VA to LinVDTS and weighted OFUL would demonstrate that the theory transfers to practice.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths and Weaknesses\n**Quality** – The theoretical analysis is careful: bounds hold for finite function classes. Matching optimal variance-dependent regret for linear bandits closes a known gap between UCB and Thompson-sampling methods.  However, the work is entirely theoretical; there is no empirical demonstration.\n\n**Clarity** – Algorithm 1 and Table 1 are easy to follow, and key assumptions are explicit.  The proofs are long and notation-heavy; readers unfamiliar with prior FGTS analyses may struggle.\n\n**Significance** – Providing the first variance-aware, horizon-free FGTS algorithm is a meaningful advance for bandit theory.  Practical impact is limited because the algorithm assumes each round’s variance \\(\\sigma_t^2\\) is revealed. This is in contrast to other existing variance aware methods.\n\n**Originality** – Extending FGTS with variance weighting and introducing the generalized decoupling coefficient are novel ideas, though they build on established FGTS and UCB techniques.", "was_revised": true, "final_justification": "The submission is a good theoretical contribution, and as such I support it's acceptance", "rebuttal": "Thank you very much for the positive review!\n\n**Q1.** The work is entirely theoretical; there is no empirical demonstration.\n\nA small simulation (e.g., linear bandit with heteroscedastic noise) comparing FGTS-VA to LinVDTS and weighted OFUL would demonstrate that the theory transfers to practice.\n\n**A1.** We appreciate the reviewer for the suggestion.  We will add experiments on the following setting:\n\n- Linear reward function: The context set has a single element, and will be omitted. The action set is $\\{\\pm 1/\\sqrt d\\}^d$. We assume that $f_*(\\mathbf a)=\\langle\\theta_*, \\mathbf a\\rangle$ where $\\theta_*\\in B(0, 1)$.\n- Variances: We assume that the noise $\\epsilon_t$ is Gaussian with variance $\\sigma_t^2$ either sampled from some distribution (e.g., $\\chi^2$ distribution) or being sparse (only nonzero in a few steps).\n- Baselines: We will compare `FGTS-VA`, standard `FGTS`, `SAVE`, and Weighted-OFUL+.\n\n---\n\n**Q2.** The proofs are long and notation-heavy; readers unfamiliar with prior FGTS analyses may struggle.\n\n**A2.** We have provided Section 6 as an overview of proof techniques. We will also add more details about how the decoupling coefficient is used, which is a crucial technical tool for FGTS-based algorithms.\n\n---\n\n**Q3.** Practical impact is limited because the algorithm assumes each round’s variance is revealed. This is in contrast to other existing variance aware methods.\n\nMany real systems do not expose $\\sigma_t^2$. Could the method be adapted with online variance estimation, or maybe a doubling scheme? Even a heuristic discussion would help.\n\n**A3.** We believe that the setting where variances are known is a starting point for developing truly variance-dependent algorithms without knowing $\\sigma_t^2$. We will continue working on this direction.\n\nIt would be hard to design a FGTS-based algorithm without knowing the variances using the current techniques: The term corresponding to step $t$ in the definition of the generalized decoupling coefficient is $\\sum_{s=1}^{t-1}\\frac{\\beta_s}{\\beta_t}(f_t(z_s)-f_*(z_s))^2$, which depends on not only $\\beta_s$ for $s<t$ but also $\\beta_t$ that scales with the variance of the current step. Therefore, when choosing hyperparameters given the result in (6.7), the parameters in step $t$ unavoidably depends on $\\sigma_t$. Given the success of UCB-based algorithms like SAVE, we conjecture that a FGTS-type algorithm without knowing the variances can be designed if a new analysis framework is developed that (i) avoids the decoupling coefficient and (ii) derives a high-probability bound of the term $\\mathrm{LS}_t$ instead of the bound in expectation. With this analysis framework, a doubling scheme or online variance estimates will be helpful in removing the dependence on $\\sigma_t^2$.\n\n---\n\n**Q4.** Extending FGTS with variance weighting and introducing the generalized decoupling coefficient are novel ideas, though they build on established FGTS and UCB techniques.\n\n**A4.** Beyond the generalized decoupling coefficient, we would also like to highlight our novel techniques in choosing the parameters in the posterior distribution. In UCB-based algorithms, there is no parameter $\\lambda_t$ that controls feel-good exploration, and in FGTS for standard contextual bandits, $\\lambda_t$ is $1/\\sqrt T$. We are the first to use the partial sum of the variances $\\Lambda_t$ in variance-aware bandit algorithms. In this way, the requirement of the total sum of variances $\\Lambda$ can be avoided.\n\n---\n\n**Q5.** In practice, how would one estimate or bound the generalized decoupling coefficient for non-linear models? Any thoughts or heuristics?\n\n**A5.** There has been no work studying the Eluder dimension for practical neural networks. We hereby provide a heuristic of estimating the generalized decoupling coefficient for MLP: We can modify the analysis in Appendix A.1. We can define $\\phi_t$ to be the output of the last hidden layer. However, since the network weights change across time, we need to characterize the difference between $\\phi_t(z_s)$ and $\\phi_s(z_s)$ using the Lipschitzness of the network.\n\n---\n\n**Q6.** The main theorem requires a finite function class with a uniform prior. Remark 5.5 talks about the linear case with F being set to an $\\varepsilon$-net of the unit ball. What about general function classes? A complete analysis with an epsilon net argument is missing.\n\n**A6.** The assumption of finite function class in Theorem 5.4 is only for the clarity of presentation, and we consider the $\\varepsilon$-net for the linear function class to show that the regret bound of `FGTS-VA` recovers those of UCB-based algorithms. In the appendix, we present Theorem B.1 that does not depend on the assumption of finite function class, so the discussion about the $\\varepsilon$-net for the general function class is unnecessary.\n\n---\n\n**Q7.** Also in comparison to the IGW methods, if we assume finite arms $K$, would the bound only depend on $K$ and not something like $\\log|\\mathcal F|$ or the generalized decoupling coefficient?\n\n**A7.** As our algorithm is tailored for contextual bandits and function approximation, it would be hard to remove the dependence on $\\log|\\mathcal F|$ and the generalized decoupling coefficient without incuring the cardinality of the context set.\n\n- $\\log|\\mathcal F|$ is $\\tilde O(|\\mathcal X|\\cdot|\\mathcal A|)$ if we apply quantization to the output of the reward function.\n- Following the proof in Dan et al. (2021), the generalized decoupling coefficient is also $\\tilde O(|\\mathcal X|\\cdot|\\mathcal A|)$.\n\nCombining the two terms, the regret bound scales with $|\\mathcal X|\\cdot|\\mathcal A|$ (ignoring logarithmic terms) when the action set and the context set are both finite.\n\n---\n\nDann et al. A provably efficient model-free posterior sampling method for episodic reinforcement learning. 2021"}, {"review_id": "eAD4eAXLYc", "reviewer": "Reviewer_jEKf", "summary": "This paper brings the feel-good Thompson sampling (FGTS) algorithm into the second-order (variance-aware) contextual bandit. They show that the regret of the algorithm can upper bounded by the decoupling coefficient, specifically, if the decoupling coefficient of the function class is d, then the regret of variance-aware FGTS is bounded by $\\sqrt{d*\\Sigma*\\log F}+d$. This is the first paper to provide variance aware guarantees for feel good Thompson sampling algorithm.", "questions": "I have the following questions about this paper:\n1. Is there an computationally efficient way for updating the distribution and performing FGTS?\n2. When the variance $\\sigma_t$ is revealed to the learner after making action at round $t$, or even not revealed to the learner, does the algorithm still work?\n3. In reference [1], they also present an upper bound scaled with $\\sqrt{A*\\Sigma}$ for the inverse-gap-weighting algorithms in that paper, does a similar guarantee holds for FGTS?\n4. This paper only considers the prior to be uniform over all functions, what about other priors? Can the algorithm achieves similar guarantees, or under what assumptions over the prior can the algorithm has similar guarantees?\n5. Since the Thompson sampling algorithm was firstly introduced for Bayesian regret, is there tight characterization of the variance-aware FGTS in Bayesian regret setting?\n\n[1] Jia, Zeyu, et al. \"How does variance shape the regret in contextual bandits?.\" Advances in Neural Information Processing Systems 37 (2024): 83730-83785.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n1. This paper is well-written. All assumptions required by the algorithms are made clear and easily understood in this paper.\n2. The study of variance-aware FGTS is of interest to the community, as FGTS is a kind of posterior sampling algorithm, which has better guarantee in Bayesian regret setting than other frequentist regret algorithm (like UCB or inverse-gap-weighting), and also the variance-aware study also provides tighter guarantees than the common regret bound.\n3. In this paper, they considered different parameter $\\eta$ across different time ste. This modification is novel and not appeared in previous feel-good TS papers.\n\nWeakness:\n1. This paper does not provide numerical experiments to demonstrate the influence of total variances and regret bound. Some numerical experiments will be much helpful to illustrate the theoretical findings.\n2. There is no lower bound provided. It will be better if there exists some lower bound which shows that the regret of the upper bound is tight up to some factors.\n3. The decoupling coefficient is a little bit difficult to understand than the normally used eluder dimension. It will be better if there is more explanation on how the decoupling coefficient can be bounded for some specific function classes.", "was_revised": true, "final_justification": "This paper presents good results. Given the answers by the authors to my questions, I will maintain the score of this paper as acceptance.", "rebuttal": "Thank you very much for the strong recommendation!\n\n---\n\n**Q1.** This paper does not provide numerical experiments to demonstrate the influence of total variances and regret bound. Some numerical experiments will be much helpful to illustrate the theoretical findings.\n\n**A1.** We appreciate the reviewer for the suggestion. We will add experiments on the following setting:\n\n- Linear reward function: The context set has a single element, and will be omitted. The action set is $\\{\\pm 1/\\sqrt d\\}^d$. We assume that $f_*(\\mathbf a)=\\langle\\theta_*, \\mathbf a\\rangle$ where $\\theta_*\\in B(0, 1)$.\n- Variances: We assume that the noise $\\epsilon_t$ is Gaussian with variance $\\sigma_t^2$ either sampled from some distribution (e.g., $\\chi^2$ distribution) or being sparse (only nonzero in a few steps).\n- Baselines: We will compare `FGTS-VA`, standard `FGTS`, `SAVE`, and Weighted-OFUL+.\n\n---\n\n**Q2.** There is no lower bound provided. It will be better if there exists some lower bound which shows that the regret of the upper bound is tight up to some factors.\n\n**A2.** We appreciate the reviewer for the suggestion. Under the assumption of finite action set, lower bounds have been shown by Jia et al. (2024). We will add the discussion of their results in the revision.\n\n---\n\n**Q3.** The decoupling coefficient is a little bit difficult to understand than the normally used Eluder dimension. It will be better if there is more explanation on how the decoupling coefficient can be bounded for some specific function classes.\n\n**A3.** The generalized decoupling coefficient has similar intuitions of the Eluder dimension. The Eluder dimension characterizes the function class in the following way: If we know the values of the function on a historical sequence, how predictable is the value of the function on a new point? The generalized decoupling coefficient works in a similar way. The term $(f_t(z_s)-f_*(z_s))^2$ on the RHS of the definition is the error of the function on a historical sequence, and the LHS $f_t(z_t)-f_*(z_t)$ measures the error of a new point. The coefficients $\\beta_t$ enables the variance-dependent bound. We have shown that the generalized decoupling coefficient is upper bounded by the generalized Eluder dimension, and is $\\tilde O(d)$ for the linear reward function class.\n\n---\n\n**Q4.** Is there an computationally efficient way for updating the distribution and performing FGTS?\n\n**A4.** The sampling can be efficiently implemented using SGLD: Suppose that the reward function class is a parameterized function class $\\lbrace f_\\theta: \\theta\\in\\Theta\\rbrace$. Let $q$ be the logarithm of the posterior distribution. For the sampling in step $t$, we can start from the sampled reward function in the previous step and perform the update $\\theta_{t, k+1}=\\theta_{t, k}+\\eta\\nabla_\\theta q(f_{\\theta_{t, k}})+\\sqrt{2\\eta\\epsilon_{t, k}}$, where $\\eta$ is a step size, and $\\epsilon_{t, k}$ is a standard Gaussian random variable.\n\n---\n\n**Q5.** When the variance $\\sigma_t$ is revealed to the learner after making action at round $t$, or even not revealed to the learner, does the algorithm still work?\n\n**A5.** It would be hard to design a FGTS algorithm without knowing the variances using the current techniques: The term corresponding to step $t$ in the definition of the generalized decoupling coefficient is $\\sum_{s=1}^{t-1}\\frac{\\beta_s}{\\beta_t}(f_t(z_s)-f_*(z_s))^2$, which depends on not only $\\beta_s$ for $s<t$ but also $\\beta_t$ that scales with the variance of the current step. Therefore, when choosing hyperparameters given the result in (6.7), the parameters in step $t$ unavoidably depends on $\\sigma_t$. Given the success of UCB-based algorithms like SAVE, we conjecture that a FGTS-type algorithm without knowing the variances can be designed if a new analysis framework is developed that (i) avoids the decoupling coefficient and (ii) derives a high-probability bound of the term $\\mathrm{LS}_t$ instead of the bound in expectation.\n\n---\n\n**Q6.** In Jia et al. (2024), they also present an upper bound scaled with $\\sqrt{A\\cdot\\Lambda}$ for the inverse-gap-weighting algorithms in that paper, does a similar guarantee holds for FGTS?\n\n**A6.** As our algorithm is tailored for contextual bandits and function approximation, it would be hard to derive such an upper bound without incuring the size of the context set:\n\n- $\\log|\\mathcal F|$ is $\\tilde O(|\\mathcal X|\\cdot|\\mathcal A|)$ if we apply quantization to the output of the reward function.\n- Following the proof in Dan et al. (2021), the generalized decoupling coefficient is also $\\tilde O(|\\mathcal X|\\cdot|\\mathcal A|)$.\n\nCombining the two terms, the regret bound scales with $|\\mathcal X|\\cdot|\\mathcal A|\\cdot\\sqrt{1+\\Lambda}$ (ignoring logarithmic terms) when the action set and the context set are both finite.\n\n---\n\n**Q6.** This paper only considers the prior to be uniform over all functions, what about other priors? Can the algorithm achieves similar guarantees, or under what assumptions over the prior can the algorithm has similar guarantees?\n\n**A6.** The assumption of finite function class in Theorem 5.4 is only for the clarity of presentation. In the appendix, we present Theorem B.1 that does not depend on the assumption of finite function class. Combined with Lemma B.3, we can see that the regret bound scales with $\\sqrt{Z}$, where the quantity $Z$ is related to the measure induced by the prior distribution on the neighborhood of the ground truth. Therefore, `FGTS-VA` should perform well as long as the prior distribution has adequate coverage around the ground truth.\n\n---\n\n**Q7.** Since the Thompson sampling algorithm was firstly introduced for Bayesian regret, is there tight characterization of the variance-aware FGTS in Bayesian regret setting?\n\n**A7.** Since the Bayesian regret is the average of the frequentist regret studied in this paper, the regret bound of `FGTS-VA` applies naturally to Bayesian regret.\n\n---\n\nJia et al. How Does Variance Shape the Regret in Contextual Bandits? 2024."}]

Author rebuttal:

Meta-review: This paper contributes new algorithmic and analysis ideas to our understanding of posterior sampling-based approaches to learning contextual bandits. In particular, it proposes a novel Thompson Sampling algorithm, adapted with a 'feel-good'-style prior, that adapts to the variances of the rewards to achieve regret bounds comparable with UCB-style approaches to the problem. The theoretical analysis introduces a new notion of problem complexity by generalizing the decoupling coefficient from prior work and relating it to the classic Eluder-dimension, which may prove to be useful for further applications in sequential decision making. 

On the flip side, the main concern, brought up by several referees, is the rather strong assumption of known, time-varying reward variances throughout time. The authors do clarify that this is the starting point to eventually ridding the approach of this assumption, perhaps using auxiliary estimation techniques. 

Despite this concern, the referees are unanimous in their positive-leaning assessment of the paper (if not clearly recommending acceptance), and I am happy to concur with them to recommend acceptance. I urge the authors to consider the suggestions of the referees to improve the clarity of presentation in a revised version.
Decision: Accept (poster)