The Power of Feel-Good Thompson Sampling: A Unified Framework for Linear Bandits
Authors: Zhiyuan Fan
Quanquan Gu
Venue: Submitted to ICLR 2023 (2023)

Abstract: Linear contextual bandit is one of the most popular models in online decision-making with bandit feedback. Prior work has studied different variants of this model, e.g., misspecified, non-stationary, and multi-task/life-long linear contextual bandits. However, there is no single framework that can unify the algorithm design and analysis for these variants. In this paper, we propose a unified framework for linear contextual bandits based on feel-good Thompson sampling (Zhang, 2021). The algorithm derived from our framework achieves nearly minimax optimal regret in various settings and resolves the respective open problem in each setting. Specifically, let $d$ be the dimension of the context and $T$ be the length of the horizon, our algorithm achieves an $\widetilde{\mathcal{O}}(d\sqrt{ST})$ regret bound for non-stationary linear bandits with at most $S$ switches, $\widetilde{\mathcal{O}}(d^{\frac{5}{6}} T^{\frac{2}{3}} P^{\frac{1}{3}})$ regret for non-stationary linear bandits with bounded path length $P$, and $\widetilde{\mathcal{O}}(d\sqrt{kT} + \sqrt{dkMT})$ regret for (generalized) lifelong linear bandits over $M$ tasks that share an unknown representation of dimension $k$. We believe our framework will shed light on the design and analysis of other linear contextual bandit variants.

THE POWER OF FEEL-GOOD THOMPSON SAMPLING: A UNIFIED FRAMEWORK FOR LINEAR BANDITS
Anonymous authors Paper under double-blind review
ABSTRACT
Linear contextual bandit is one of the most popular models in online decision- making with bandit feedback. Prior work has studied different variants of this model, e.g., misspecified, non-stationary. and multi- multi-task/iife-longg linear contex- tual bandits. However, there is no single framework that can unify the algo- rithm design and analysis for these variants. this paper, we propose a unified framework for linear contextual bandits based on feel-good Thompson sampling (Zhang 202I). The algorithm derived from our framework achieves nearly min- imax optimal regret in various settings and resolves the respective open problem in each setting. Specifically, let be the dimension of the context and be the length of the horizon, our algorithm achieves an ((dvST)) regret bound for non- stationary linear bandits with at most S switches, Odd Pš) regret for non- stationary linear bandits with bounded path length P. and Oldv KT + dTk regret for (generalized) lifelong linear bandits over M tasks that share an unknown representation of dimension We believe our framework will shed light on the design and analysis of other linear contextual bandit variants.
INTRODUCTION
Linear contextual bandit is one of the most popular models in online decision-making with a large, possibly infinite, action space. This bandit model has been widely studied in the past decade. One of the most successful approaches is based on the upper confidence bound (Auer) 2002). For example, LinUCB (Li et al.] 2010) (or OFUL (Abbasi- Yadkori al. 2011)) follows the optimism-in -inttit---i-thee- in-the- -fnceof-uncertaintt principle and chooses the best action within an elliptical confidence ball. The algorithm has been proved to be nearly minimax optimal by using the elliptical potential lemma to track the bonus term. With some modifications to the algorithm, one had generalized this algorithm various settings, e.g., non-stationary linear bandits (Chen al. 2019), multi-task linear bandits (Hu et al. 202T), to mention a few. The analyses for these generalizations require the corresponding modified elliptical potential lemma, which is, however, hard to derive in general. (One may refer to the technical note (Faury et al., (02I)) which discusses the faults in the elliptical potential lemma for non-stationary linear bandits).
Another common approach for online decision-making is exponentially weighted sampling. By sampling from distribution over actions based their historical rewards, gives rise near- optimal policy-based algorithms for various settings such as the hedge algorithm (Littlestone & Warmuth 1994) for prediction with expert advice. For contextual bandits, EXP4 (Auer et al. 2002) enjoys a regret bound of
[eegret (T)) < O(VKT log [?(),
where K is the number of actions, T' is the length of the horizon, and H is the feasible policy set. Note that contextual policy-based algorithms usually allow the policy to take round index as context. This gives natural way to deal with non-stationary environment. For instance, one can solve non-stationary expert problems using meta meta-experts by following different experts in different rounds (Herbster & Warmuth| 2004). With this idea, one can obtain the regret bound for variety of bandit models by counting the number of policies (7H which is easy to do in general.
This motivates to find policy-based algorithm for linear contextual bandits. We note that EXP4 not suitable for our purpose since its regret suffers a polynomial dependence on the number of actions, which can be unbounded in linear contextual bandits. This is due to the fact that EXP4 is designed for general reward functions and does not leverage the linear structure of linear bandits. Given this observation, we raise the following question:

---

Can we design an EXP4-type algorithm for linear contextual bandits?
In this paper, we answer the above question affirmatively. In detail, we propose Feel-Good Thompson Sampling over Linear Policies (FGTS.LP), which is policy-based algorithm for linear contextual bandits. Our algorithm can be regarded as policy-based adaption of feel-good Thomp- sampling (Zhang) 2021) linear bandits, while this adaption is nontrivial. Our algorithm enjoys a regret bound that is logarithmically dependent on the number of policies and polynomially depen- dent on the dimension contexts. To be specific, we prove the following regret bound for FGTS.LP.
Theorem 1.1 (Regret Bound of FGTS.LP (informal)). Let d be the dimension of the context, T be the length of the horizon, and H. the set of all feasible policy hypotheses. The regret of FGTS.LP is bounded by
E B(Regret (T) & O(y N(H, TVdde.
where e some hyperparameter and ((H, c) is the covering number of policy set which contains an c-optimal policy.
The above theorem provides a general interface analyze the performance of FGTS.LP in differ- ent settings. Following the idea of including round index, FGTS.LP can deal with various linear contextual bandits. The results are highlighted as follows:
Theorem 1.2 (Regret Bound over Variants of Linear Bandits (informal)). With specific modification for each setting, the regret of FGTS.LP is bounded as
Regret (7) < Ö(dVT + dV))
(d)()ffoo for (-misspecified linear contextual bandits.
E Regret (T)) < (dv/ST) ( for non-stationary linear contextual bandits with at most S switches.
E Regret (T)) S T pb) for non-stationary linear contextual bandits with path length bounded by P.
E [eggrett(T)] Ö(dvkI+ VdkMT) for (generalized) lifelong linear contextual bandits over M tasks that share an unknown representation of dimension k.
We note that the above results are all near-optimal which match or improve the state-of-the-art in the corresponding settings. To sum up, our contributions are:
We propose a unified framework for design and analyze various linear contextual bandit models.
Our framework is easy interpret and enjoys near-optimal regret bound different settings.
We propose the first nearly minimax algorithm for non-stationary linear contextual bandits with bounded number of switches.
We propose new algorithm for non-stationary linear contextual bandits with bounded path length. It is the first algorithm that achieves nearly minimax regret.
We propose the first near-optimal algorithm for (generalized) lifelong linear contextual bandits. Its regret matches the state-of-the for multi-task linear contextual bandits (Hu al. 2021 which is special case of our model.
Notation. We use lower and upper case bold face letters to denote vectors and matrices respectively. We use [k] to denote the set (1, 2, .. k}. We denote the Euclidean norm of vector x E IRd by ||x||2- For matrix A = [ar.-. ... ax] E Rdxk, we define || = maxisiçe ||a:||2. For two non-negative sequence {a,). {bn we write an < Obb,) ) if there exists absolute constant C such that on I Cbb for all n 1, and an I (bb,) if there exists an absolute constant such that an I Obb, log" b,)); we write an 2 ((bb,)) there exists an absolute constant C' > such that on 2 Cbn for all n 2 and a, 2 ((b..) if there exists absolute constant & such that an 2 (b,, log - bn); we write a, (b,,) if there exists absolute constants 0 < C2 < C2 such that Cibn S on C2b, for all n For any set C. we use |C] to denote its cardinality. We use log to denote log, for short.
RELATED WORK
Misspecified Linear Bandits. The misspecified linear bandits was first studied by Ghosh et al. 2017), and they proposed an algorithm that achieves sub-linear regret when the misspecification small. Lattimore & Szepesvari (2000) proposed algorithm with an (dvT TVdg) regret
2

---

but requiring the contexts to be stationary. The regret is nearly minimax optimal they proved matching lower bound in the paper. Later. Zanette et al. (2020) proposed LinUCB-like algorithm with the same regret that gets rid of the requirement of stationary context. More recent works (Foster et al. 2020a Krishnamurthy et al. 2021 Takemura et al. 2021) studied the problem when the misspecifccttinn level is unknown.
Von-Stationary Linear Bandits with Bounded Switches. Non-stationary online decision-making models with bounded switches have long been studied in the literature. Cesa- nasa-Bianchi et al. (1993) studied the problem in the full information experts setting, and proposed an algorithm with an ex- pected regret bound O v (T)ST, where S' is the number of switches. Later, a high probability bound was obtained by UCB-type algorithm (Auer) 2002). In the bandit feedback setting, EXP3.S (Auer al. 2001 achieves a regret of DVKST)) where K' is the number of actions. Borrowing the idea from EXP4, the algorithm has been extended to the contextual setting with the Oly KS log [1] regret bound (Luo et al. 2018), where II is the finite policy class. More recently, Luo et al. (2022) studied the non-stationary linear bandit setting where the action set a unit ball and proposed a bandit-over-bandit approach that achieves regret of (VdST). There is no existing algorithms for non-stationary linear contextual bandits with bounded switches.
Non-Stationary Linear Bandits with Bounded Path Length. In recent years, -tationii linear bandits with bounded path length have received increasing attention. Various algorithms have been developed (Cheung et al., 2019 Chen et al. 2019 Zhao et al.] (020) in this setting. The key idea behind these algorithms is to progressively forget the past data, and the proof is based on the same kind of elliptical potential lemma. However, as discussed by Faury et al.] (202T), there is a fault in the proof of the original paper (Cheung et al. 2019). and the corrected analysis can only get regret bound of T Pt). Meanwhile, the lower bound of this problem is 2(T pt) (Faury let al. 202T). The algorithm derived from our framework closes the gap on T.
(Generalized) Lifelong Linear Bandits with Shared Representation. dit, in which the agent plays over a collection of tasks simultaneously, was first studied by Yang eet al. (020)). They proposed an explore-then, coom-c algorithm that leverages the multi-task struc- ture but requires a unit-ball action space. Their followed-up work (Yang et al.) 2022) improved the regret of the algorithm and generalized it to the lifelong setting. The algorithm has regret bound of OddvkT++ + kVMT). Hu et al. 2021) studied the multi-task setting in linear contextual bandits and proposed computationally inefficient algorithm with regret of Ö(dvkT + Vdk using LinUCB-tyr approach. Recent work (Qin et al. 2022) studied the non non-stationary lifelong linear bandits with a task diversity assumption. On the lower bound side, Yang et al. (2020) proved that any algorithm for multi-task linear bandits suffers least an ((dkkT + kv MT) regret.
The multi-task linear ban-
3 THE PROPOSED FRAMEWORK
3.1 PROBLEM SETUP
We first introduce a framework which is able to cover variants of linear contextual bandits. Let d' be the dimension of the context, and T be the lenght of horizon. Denote by A S {a E Bd :|al|z < 1} the action space and F C AR- the reward function space. The contextual bandit can be described as repeated game between an agent (the bandit algorithm) and the environment (the adversary). In
each round t = 11. ... .T, the environment first picks hidden reward function f(() E F and draws an action set ( C A. After observing the action set A(t), the agent selects an action a()) E (()) and receives a stochastic reward
(1) = (())(a())) + E(t)
where (a()) is the expected value of the observed reward (() and {(t) is zero mean random
O. where (2(1) (((()),(())) a(r), ) is the history in the first t rounds. The learning objective of the agent is to maximize the expected cumulative reward, or equivalently, to minimize the pseudo-regret
noise satisfying ([((())(())) f(t (()) a(t)]
Regret = Σ'= (f19 (a)))
where ( = arg max s (a) is the optimal action in round t. We assume the reward func- tions can be approximated by linear functions.
3

---

Assumption 3.1. There is mapping 0 : F - fx R ||x|| 1) and universal constant Ç E [0,1] such that
sup (fa)e(FxA)
((a, 0()) - f(a)) s.
Moreover, we assume If(a) S for all (f. E A).
We call Ç the misspecification level of the model. For the special case ( = 0, the model reduces to standard linear bandits. We further assume the observed reward is universally bounded.
Assumption 3.2. The observed reward always satisfies |r(*| for all [T].
This assumption ensures the additive noise g(t) is bounded. Note that this assumption is not essential to the algorithm, our analysis can be naturally generalized to unbounded sub-Guubee abb-Gaussian with constant variance it showed by Zhang (2021). We use bounded noise to avoid introducing variance as extra parameter.
The above framework is compatible with variants of linear contextual bandits. For example, one can formulate specific linear contextual bandits by restricting the enviromment to select reward sequences (f() ,.... (())...)..)))))) f(T) from the corresponding structural set. We will present some concrete instances in the sequel.
3.2
SPECIFIC EXAMPLES
3.2.1
STATIONARY MISSPECIFIED LINEAR BANDITS
For stationary linear contextual bandits, the reward function is fixed before agent decides. Thus, the environment is restricted to select reward function sequences that has the same linear approximation across rounds.
Assumption 3.3. There exists a vector tg E Rd such that (())) On for all & E [T].
The reward function is allowed to be misspecified from linear functions in Assumption 3.1 It is easy to verify that our framework reduces to linear contextual bandits with misspecification (Foster al. 2020a) under Assumptions 3.1 3.3
3.2.2
NON-STATIONARY LINEAR BANDITS WITH BOUNDED SWITCHES
For non-stationary linear bandits, we first consider the case where the reward function may change dramatically for finite number of times (Auer al. 2001 Luo al. (022). The agent is not told when and how the reward function switches, and the environment can schedule the change in an adversarial way. We describe this setting using the following assumption:
Assumption 3.4. There exists a constant such that ET= ((0()()) * ((f(t-1))] S.
We call S the number of switches. We call the problem formulated under Assumptions 3.1 3.2 and 3.4 as the non-stationary linear bandits with bounded switches. We note that the non-stationary linear bandits with bounded switches is a harder problem than that with bounded path length, since there is black-box reduction from non-stationary linear bandits with bounded path length to non- stationary misspecified linear bandits with bounded switches. Recently, Luo et al. 2022] studied this setting but for non-contextual linear bandits with ( {a E Fd ||a//2 S 1}. They proposed an algorithm with 1/2 regret. However, there no existing algorithm for non-stationary contextual linear bandits with 1//2 regret.
3.2.3 NON-STATIONARY LINEAR BANDITS WITH BOUNDED PATH LENGTH
We also consider another kind of non-stationary linear bandits where the reward function can drift slowly over time (Cheung et al. 2019). The agent does not know the evolution dynamic, while the environment can choose the reward function adversarially in each round. We characterize this setting by the following assumption.
Assumption 3.5. There exists a constant P such that Er= ()((())000)))0)))))))))))))))) ( ((((t-)))11 S P.
We call P the path length. One can verify our framework under Assumptions 3. 3.2 and 3.5 reduces
to non-stationary linear bandits with bounded path length (Faury et al. 2021 Existing regret upper bound of order 3/4 while the lower bound is of order T2/3 So there is still gap between the regret upper and lower bounds.
4

---

3.2.4 (GENERALIZED) LIFELONG LINEAR BANDITS WITH SHARED REPRESENTATION
We consider the setting where the agents have to solve a collection of correlated tasks sequentially. Let M be the number of tasks. At the beginning of the process, the environment first chooses M tasks fi,... fas- In each round the environment draws task index m(t) [M] and assign current reward function as f(t) fm.... Besides the action set A the agent is provided with the task index m² and selects the action a
It is worth noting that our lifelong learning setting is generalized version of the lifelong learning setting studied in Yang et al. 2022)) The original setting of lifelong learning, in which the same task only appears in one interval, is equivalent to the case where the same m( lies in a single interval. We consider this generalized setting since it also captures multi-task learning (Hu et al. 202I], where the tasks appear periodically. We make the following assumption.
Assumption 3.6. There exists hidden orthogonal matrix B E Rd and set of hidden vectors w with w, R2 such that O( Bw m holds for all e [T') where {mlt)) ) is some
sequence with mlt) [M.
In Assumption 3.6 B is called the linear feature extractor of the model. The assumption implies 0
[(]] is low rank matrix which can be decomposed over the bases B. This a common assumption for representation learning over linear bandits in the literature (see e.g.. (Hu et al., 2021 Yang et al. 2022)). The genearlized lifelong linear bandits is defined under framework with Assumptions 3.1 3.2 and 3.6 Recently, Yang et al.] (2022) studied the lifelong learning setting for non-contextual linear bandits where A {a E R ||a2 S 1] and proposed an algorithm with T regret. However, there no existing algorithm for lifelong contextual linear bandits with 1/2 regret.
(0(r()),
4 FEEL-GOOD THOMPSON SAMPLING OVER LINEAR POLICIES
In this section, we present our main algorithm FGTS.LP (Feel-Good Thompson Sampling over Linear Policies) for solving linear context bandits under the framework described in Section 3 We first introduce some important concepts in the algorithm design.
4.1 LINEAR POLICY CLASS AND ITS COVERING
It is pretty amnoying that the regret defined in ( is related with dynamic variable A We introduce an essential concept in our algorithm. Instead of selecting action (!!), we let the bandit algorithm to select a sequence of policies =(1), which decide how the agent take action based on the observed context over time. Formally, a sequence of policies π [T') x - ER is time-variant hypothesis for the expected reward of choosing any actions in any round, i.e., the expected reward of action a E A on round t is т (t, a). Thus, the sequence suggests to play action (t) = arg ma (t, a) when the action set (1))) is realized on round t. Since the reward functions in our setting can be approximated by linear functions, we would focus on linear policies that can be approximated by linear functions:
Definition 4.1 (Linear Policy). A linear policy si r( is sequence of models parameterized by the matrix e = 00, 0r] E RddT such that (t) a) = (a, 0,).
Let H be the set of all feasible linear policies. Under certain assumptions within our framework, the linear policy set is restricted to corresponding domain. For example, under Assumption 3.3 the linear policy set H is parameterized by matrices in which all columns are the same.
Note that 7 is a set over continuous domain and thus of infinite size. To deal with the infinite number of linear policies, (c-Net of Linear Policies). H. is said to be a c-net of H if any linear policy O [01...., 0r] E H. has an e-approximation Ô = [O,.... Or] E H. with ||0, - 0, ll2 S é for all t e [T]. Moreover, we define the covering number of H (at scale E) be the size of minimum He, i.e.,
introduce the approach of e-net and covering number.
Definition 4.2
NHH, c, [|2,0=) := inf Hel
One can regard the metric entropy log N N(H, e, 112,00) as the effective dimension of the policy set.
4.2 THE ALGORITIM
Now we are ready to present our main algorithm. The algorithm is an adaptation of the FGTS Zhang 202T). We present the pseudo-code in Algorithm T
5

---

Algorithm 1 FGTS.LP
input:
linear policies set H: inverse temperature 3; exploration parameter X; covering radius c. construct an e-net H. of H such that log [Hr| = Ollo N NHH,,, e, [|2,,)))
for round = 1,... T do
(e) x exp ( 3 レー L (+)) for 3 over He take action a arg max aE ((o) (a. ) end for
sample (1) 10
At the beginning, the algorithm constructs an c-net He over all feasible linear policies H. In each round i, the algorithm first samples a policy @ over H. according to the distribution
()) == exp (- 3 ( (+))
(2)
EOVEn, exp B 3 (0))
where 3 > is the inverse temperature and ((), RdxT + IR is a loss function defined as follows (e) = (r(1) (a 01))² - max (a, O1).
aEAD)
Here À > 0 is tuning parameter which controls the exploration. The algorithm then chooses the optimal action (t) that maximizes the expected reward according to the chosen policy ) among the action set (+).
We note the loss function in (3) has two terms. The first term is the Thompson sampling term. It casts penalty based on the estimation error of the reward. Recall y(T) is a random variable with mean (a(r)) = (a(*), (()((r))) this term forces the algorithm to select policy close to the true policy (((()). This encourages the algorithm to do exploitation. The second term is so called feel-good exploration term (Zhang/ 2021). It favors the policy that grants large rewards for historical actions, which can be regarded as an bonus that encourages the algorithm to do exploration.
Note that Algorithm|] needs to know T and H before hand. By restarting the algorithm periodically with the doubling trick, one can run the algorithm without knowing in hindsight. However, is unclear if the algorithm can be parameter-free for H. since model selection for exponential weighted sampling algorithm remains an open question (Foster et al., 2020b). Furthermore, the algorithm sampled over e-net of H. which is not necessarily computationally efficient in practice. So it is better to regard Algorithm | as an oracle-efficient algorithm provided the sampling oracle over H.. For the implementation of this algorithm in practice, we present a detailed discussion in Appendix B
4.3
COMPARISON WITH EXISTING ALGORITHMS
Comparison with FGTS. One may see that FGTS.LP has the same structure as the original FGTS Zhang 2021). Both algorithms use exponentially weighted sampling over the same loss function. The main difference between the two algorithms is that the original FGTS samples over models (or equivalently, reward functions) rather than policies. Note that sampling over models is equivalent to choosing the stationary policies, which always select the same action given the same context. Thus, the original FGTS cannot deal with non-stationary environments in which the reward functions change over time. In contrast, sampling over policies enables us to inspect the misspecification explicitly and thus analyze it meticulously. As a result, FGTS.LP can achieve nearly minimax regret bound for misspecified linear bandits and non-stationary linear bandits.
Comparison with EXP4. Another contextual bandit algorithm that uses exponentially weighted sampling is EXP4 (Auer al., 2002). Using exponentially weighted sampling, one can corral large set of policies achieving a low regret as long as the reward for each policy is revealed. However, the agent cannot observe the payoff for policies that are not chosen in the bandits setting, and has to estimate it. EXP4 uses an unbiased estimator to estimate the reward. However, the estimator has a large variance which dependence on the size of the action set in the regret bound. As a comparison, FGTS.LP uses the expected reward reported by the policies but casts penalties on the policies that cannot estimate the payoff of chosen actions. Although this estimator may be biased in estimating the actual reward, the estimator will assigns a large value to the policy with a high return. So the regret analysis for exponentially weighted sampling (Littlestone & Warmuth 1994) Since the variance of this estimator is much smaller and independent of the number of actions, FGTS.LP I.P is able to get regret bound that is independent of the size of the action set.
proportional to the number of actions. This causes a polynomial
still be applied to FGTS.LP.

---

Comparison with LinUCB. In addition to Thompson sampling and posterior sampling, another common approach for linear contextual bandits LinUCB (Li et al. 2010) (or OFUL (Abbasi-) Yadkori et al.) 201T)). The algorithm implements the optimism-in otw--ia--of---eeeeeeeeeeee
principle, which selects the policy with the largest optimistic reward among all possible policies that agree with the observed reward in history. Note that FGTS.LP tends to sample policy with large estimated reward on the historical data and small estimation error. Therefore, FGTS.LP can also be regarded as an implementation of the same principle. The difference is, rather than focusing on one action, FGTS, L.P uses exponentially weighted sampling to select policy. From the game theory perspec- tive, the variants of linear contextual bandits can be regarded mixed strategy profile usually generates better rewards than pure strategy profile against adver- sarial opponents (Fudenberg Tirole 199I). Thus, FGTS.LP will have a stronger ability to solve variants of linear contextual bandits.
two-player game. is known that
MAIN RESULTS
In this section, we present the theoretical results of our algorithm. The following theorem provides regret guarantee for Algorithm when applied to general linear bandits.
Theorem 5.1. Suppose E [0, 1]. set X
@(Vlog (HH, c, || /o + +c++ /)2/d) and
(1). Under Assumptions 3.7 and 22
for any policy class H. the expected regret of Algorithm
is bounded by
(Tgg s o dT log No N(H, 6, 112,00 + Tvd(e ((((+))) TV
(4)
where the expectation taken over all randomness of the learning algorithm and the data noise.
There are two terms on the RHS of (4), which we will explain separately. The first term depends on the metric entropy log (H, e, 12,,0),, which depicts the complexity of the policy set H. The second term depends on the scale of the e-nct H. as well as the misspecification level Ç. There is a trade-off between the first term and the second term driven by the scale of the e-net: for large the first term is small and the second term is large; for small c, the first term will be large and the second term will be small.
With Theorem 5.1 one only needs calculate the metric entropy log N N(H, e, l12,00) and select proper to minimize 4 i.e., ensuring log N(H, c, || l12,se) vT(c+ (). Since the metric entropy log (H, II- 1l2. is the effective dimension of the policy class, it is easy to calculate for different policy classes and derive the corresponding regret bound. As a result, Algorithm I can viewed as unified framework for linear contextual bandits.
5.1 IMPLICATIONS TO LINEAR BANDIT VARIANTS
In this subsection, we show the implications of Theorem on the specific examples of contex- tual linear bandit variants. For the ease of comparison between our results and prior results, we summarize the results Table
5.1.1 MISSPECIFIED LINEAR BANDITS
We start with the simple setting where the approximate linear function is stationary. In this setting, the e-net of the linear policy class can be reduced to the e-net of single reward function. Since the embedding is of dimension d, the covering number is exactly O(e-d):
Lemma 5.1 (Covering Number for Misspecified Linear Bandits). Under Assumptions 3.1 and 3.3 the metric entropy of linear policy class satisfies
log (H,, e, || l12,00) < OOdlog
By choosing T the metric entropy can be bounded log (HH, e, 112,,0) S O(d T)).
With Theorem 5. we directly get the following regret bound:
Corollary 5.1 (Upper Bound for Misspecified Linear Bandits). Under Assumptions 3.7 3.2 and 3.3 the expected regret of FGTS.LP is bounded by
E(Regret(T) < o
+ .VCc).
The following lower bound shows that the regret upper bound in Corollary 5.1 is tight up to loga- rithmic factors:
7

---

Existing Algorithm
FGTS.LP (This Paper)
Lower Bounds
OldyT + TVCC)
OddVT- TVdC)
Didd'T + TTT.VV
TVd
Misspecified LCB
Zanette et al. 2020)
(Corollary 5.1)
Lattimore & Szopesvari
2020
Non-stationary LCB
Oldv ST)
((dv/ST)
(Bounded Switches)
(Corollary 5.2)
(Lemma F.5
Non-stationary LCB
Old T Pi)
(d T P5
Q(d T P4
(Bounded Length)
Faury al. 2021)
(Corollary 5.3
(Cheung al.
2019)
Oldyk' KT +
dkMT)
Ody + dkMT)
O(dvk k MT)
Multi-task LCB
(Hu et al.
2021)
(Corollary
5.4)
(Yang al.
2020)
Odvkk + (kMT))
(ddvk
kv (TT)
Lifelong LCB
(Corollary 5.4
(Yang et al. 2020)
Table 1: Summary of the results variants of linear contextual bandits. d is the dimension of the
context, T is the length of horizon, and Ç is the misspecification level for misspecified bandits. In addition, S is the number of switches and P is the path length for non-stationary bandits. Further- more, M denotes the number of tasks and l denotes the representation dimension for multi-task and lifelong bandits.
Proposition 5.1 (Lower Bound for Misspecified Linear Bandits). Under Assumptions 3.1 3.3 for any algorithm, there exists bandit instance for which
3.2 and
E|Regret (T) 2 22
5.1.2 NON-STATIONARY LINEAR BANDITS WITH BOUNDED SWITCHES
In this setting, we can construct the e-net by enumerating the positions of switches and cover the reward function set after each switch. The set of reward functions after each switch has cover- ing number of ((=-d). So the set of reward funetions with S switches has a covering number of OEE Ole-dS). Moreover, the different positions of switches within I rounds can be bounded by ((TS). With above facts, we can bound the size of e-net:
Lemma 5.2 (Covering Number for Non-Stationary Linear Bandits with Bounded Switches). Under Assumptions 3.7 and 3.4 the metric entropy of the linear policy set satisfies
log N (H, e, |l. 112,,x) S OodS Slg
Using Theorem 5.1
with = 1 immediately obtain the following regret bound:
Corollary 5.2 (Upper Bound for Non-Stationary Linear Bandits with Bounded Switches). Under the expected regret of FGTS.LP is bounded by
Assumptions 3.7
3.2 and 3.4
E Regret < 0 ST log + TVd.).
The following lower bound shows FGTS.LP is nearly minimax optimal for non-stationary linear bandits with bounded switches:
Proposition 5.2 (Lower Bound for Non-Stationary Linear Bandits with Bounded Switches). Under
Assumptions 3.7
3.2 and 3.4 for any algorithm, there exists bandit instance for which
[[Regret(T)] a (ddSSTT + TT l/logTTg) TC).
log
5.1.3 NON-STATIONARY LINEAR BANDITS WITH BOUNDED PATH LENGTH
Now we move to the more challenging setting where the parameters slowly drift over time. We would reduce the parameter drift to parameter switch. More specifically, parameter switch is considered happen only if the path length of parameter drift from last switch exceeds e/2. Since the total path length is bounded by P. there are no more than 2P switches. As result, an c/2- net of the reward functions for non-stationary linear bandits with more than 2Pe switches is an e-net of the reward functions for non-stationary linear bandits with path length no more than P. This immediately gives the following result on its covering number:
8

---

Lemma 5.3 (Covering Number for Non-Stationary Linear Bandits with Bounded Path Length).
Under Assumptions 3.1 and 3.5 the metric entropy of linear policies satisfies
log N (H, e, l12,0)) - O(dlog + d log logo-
Pc Pog- T)
Using Theorem 5.1
with = max & p J, P we get the following regret bound:
Corollary 5.3 (Upper Bound for Non-Stationary Linear Bandits with Bounded Path Length). Under
Assumptions 3.7
3.2
and 3.5
the expected regret of FGTS.LP is bounded by
[[Regret(T)] < = ( p3 + dVT + TVVcc..
E
The following lower bound shows that the regret upper bound in Corollary 5.3 is nearly optimal: Proposition 5.3 (Lower Bound for Non-Stationary Linear Bandits with Bounded Path Length). Un- for any algorithm, there exists a bandit instance for which
der Assumptions 3.1
3.2 and 3.5
Reegrtt (T)) 2 ( D pà dvT + T d/ logg/ TC).
5.1.4 (GENERALIZED) LIFELONG LINEAR BANDITS WITH SHARED REPRESENTATION
In this setting, every feasible linear policy can be described by a low-rank matrix that is the product of two matrices B d and [w:]s= R&xM We can construct the e-net of linear policies using the product of two e/ e/2-net over B and [w:] Also, the dimension of linear policies is dk k.M. This implies the following result on its covering number:
Lemma 5.4 (Covering Number for Lifelong with Shared Representation). Under Assumptions 3.1 and 3.6 the metric entropy of linear policies satisfies
log N N(H, c, ||2,,c) Odkkloge" + kM lo cl
Using Theorem 5.1 with 7-11, we obtain the following regret bound:
Corollary 5.4 (Upper Bound for Lifelong Linear Bandits with Shared Representation). Under As-
sumptions
3.7 3.2
and 3.6 the expected regret of FGTS.LP is bounded by
E[Regret < ((VkkT VdkMT + -TvC)).
If each task appears uniformly for T/M rounds, an algorithm that solves each task independently suffers regret bound of (T) using nearly minimax algorithm such as LinUCB (Li et al, 2010). In the case that & < M and k < d. algorithm saves a factor of /M/k / /d, which shows it utilizes the underlying representation. Morcover, this regret bound matches the near-optimal algorithm for multi-task linear bandits (Hu et al. (021]. which is special case of our setting. The following lower bound shows that our algorithm is near-optimal:
Proposition 5.4 (Lower Bound for Lifelong Linear Bandits with Shared Representation). Under
Assumptions 3.1
3.2 and 3.6 for any algorithm, there exists bandit instance for which
E[Regret 2 a 22(dvv (ddKkT +dVKT+KVMMT + /d log //looggTT)
6 CONCLUSION AND FUTURE WORK
In this paper, we proposed a unified framework for linear contextual bandits based on feel-good Thompson sampling, which can cover different variants of linear contextual bandits. At the core of our algorithm is an adaption of feel-good Thompson sampling from reward function policy class, which enables the algorithm to deal with time- vime-varying environments. We showed that our algorithm can achieve near-optimal regret bounds for these variants of linear bandits, which resolve several open problems in the respective settings.
We notice that there is still gap between the regret upper and lower bounds in terms of the depen- dence on the dimension for non-stationary linear bandits with bounded path length. We leave it as future work to close this gap.

---

REFERENCES
Yasin Abbasi-Yadea Yadkori, Dávid Pál, and Csaba Szepesvari. Improved algorithms for linear stochastic bandits. In NIPS, 2011.
Marc Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In AISTATS, 2017.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In ICML,, 2013.
Peter Auer. Using confidence bounds for exploitaiion-exploraiio trade-offs. J. Mach. Learn. Res., 3:397-422, 2002.
Peter Auer, Yoav Freund, and Robert E. Schapire. The non-stochastic multi-armed bandit problem. 2001.
Peter Auer, Nicolò armed bandit problem. SIAM J. Comput., 32:48-77, 2002.
Yoav Freund, and Robert E. Schapire. The nonstochastic multi-
Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and geometry of markov diffusion operators. 2013.
Sébastien Bubeck, Nicolò Cesa Basa-Bianchi, and Sham M. Kakade. Towards minimax policies for online linear optimization with bandit feedback. ArXiv, abs/1202.3079, 2012.
Nicolò Cesa- DesacBianchi, Yoav Freund, David P. Helmbold, David Haussler, Robert E, Schapire, and Manfred K. Warmuth. How to use expert advice. In STOC '93, 1993.
Yifang Chen, Chung wei Lee, Haipeng Luo, and Chen Yu Wei. A new algorithm for non-stationary contextual bandits: Efficient, optimal, and parameter-free ArXiv, abs/1902.000880 2019.
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Hedging the drift: Learning to optimize under non-stationarity, ArXiv,
2019.
Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. Stochastic linear optimization under bandit feedback. In COLT, 2008.
Louis Faury, Yoan Russac, Mare Abeille, and Clément Calauzènes. A technical note non- stationary parametric bandits: Existing mistakes and preliminary solutions. ALT, 2021.
Dylan J. Foster and Alexander Rakhlin. Beyond ueb: Optimal and efficient contextual bandits with regression oracles. In ICML, 2020.
Dylan J. Foster, Alekh Agarwal, Miroslav Dudík, Haipeng Luo, and Robert E. Schapire. Practical contextual bandits with regression oracles. ArXiv, abs/1 803.01088, 2018.
Dylan J. Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert. Adapting misspecification in contextual bandits. ArXiv, abs/2 05745, 2020a.
Dylan J. Foster, Akshay Krishnamurthy, and Haipeng Luo. Open problem: Model selection for contextual bandits. ArXiv, abs/2006. 10940, 2020b.
Drew Fudenberg and Jean Tirole. Game theory. MIT press, 1991.
Avishek Ghosh, Sayak Ray Chowdhury, and Aditya Gopalan. Misspecified linear bandits. ArXiv, abs/1704.06888 06880, 2017.
Nima Hamidi and Mohsen Bayati. On worst-case regret of linear thompson sampling. ArXiv, Abbs/2006006790) 2020.
Mark Herbster and Manfred K. Warmuth. Tracking the best expert. Machine Learning, 32:151-177 2004.
Jiachen Hu, Xiaoyu Chen, Chi Jin, Lihong Li, and Liwei Wang. Near-optimal representation learn ing for linear bandits and linear rl. In ICMI., 2021.
10

---

Sanath Kumar Krishnamurthy, Vitor Hadad, and Susan Athey. Adapting to misspecification in contextual bandits with offline regression oracles. In JCML, 2021.
Tze Leung Lai and Herbert E. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6:4-22, 1985.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. 2020.
Tor Lattimore and Csaba Szepesvari. Learning with good feature representations in bandits and in rl with generative model. In 2CMML,0200
Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual- approach to personalized news article recommendation. ArXiv, abs/1003.0146,, 2010.
Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Inf. Comput., 108: 212-261, 1994.
Haipeng Luo, Alekh Agarwal, and John Langford. Efficient contextual bandits non-stationary worlds. In COLT, 2018.
Haipeng Luo, Mengxiao Zhang, Peng Zhao, and Zhi-Hua Zhou. Corralling larger band of bandits: A case study on switching regret for linear bandits. ArXiv, abs/2202.06151, 2022.
Yuzhen Qin, Tommaso Menara, Samet Oymak, ShiNung Ching, and Fabio Pasqualetti. Non-
stationary representation learning in sequential linear bandits. 2022.
Gareth O. Roberts and Richard L. Tweedie. Exponential convergence of langevin distributions and their discrete approximations. Bernoulli, 2:341-363, 1996.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Math. Oper. Res., 39: 19:1222-2 2014.
Kei Takemura, Shinji Ito, Daisuke Hatano, Hanna Sumita, Takuro Fukunaga, Naonori Kakimura, and Ken-ichi Kawarabayashi. A parameter-free algorithm for misspecified linear contextual ban- dits. In International Conference on Artificial Intelligence and Statistics, pp. 3367-3375, PMLR, 2021.
William R. Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25:285-294, 1933.
Roman Vershynin. Introduction the non-asymptotic analysis of random matrices. In Compressed Sensing, 2012.
Pan Xu, Hongkai Zheng, Eric V. Mazumdar, Kamyar Azizzadenesheli, and Anima Anandkumar. Langevin monte carlo for contextual bandits. In ICML, 2022.
Jiaqi Yang, Wei Hu, Lee, and Simon Shaolei Du. Provable benefits of representation learning in linear bandits. ArXiv, abs/2010.06531, 2020.
Jiaqi Yang, Qi Lei, Jason D. Lee, and Simon Shaolei Du. Nearly minimax algorithms for linear bandits with shared representation. ArXiv, abs/2203.15664, 2022.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In ICML, 2020.
Tong Zhang. Feel-good thompson sampling for contextual bandits and reinforcement learning. ArXiv, 10.0081, 2021.
Peng Zhao, Lijun Zhang, Yuan Jiang, and Zhi-Hua Zhou. A simple approach for non-stationary linear bandits. In A/STATS, 2020.
11

---

A ADDITIONAL RELATED WORK
Thompson Sampling. Thompson sampling is a classical algorithm that can be adapted to contextual bandits [Thmmsson] 1933). Russo & Roy (2014) proposed the first general theoretical guarantee for Thompson sampling. By utilizing the connection between Thompson sampling and optimistic policies. they showed Thompson sampling achieves a Bayesian regret bound of ((dvT) for linear bandits, where the underlying parameters are randomly drawn from some public distribution. For frequentist regret, Agrawal & Goyal (2013) showed a modified Thompson sampling in which the variance of the posterior distribution is inflated by (dd) achieves a regret bound of Ö(d /T) on linear bandits. As shown by (Hamidi & Bayati (2020), inflation is necessary for Thompson sampling to achieve sub-linear regret; thus, one cannot improve the regret bounds for original Thompson sampling. In comparison, feel-good Thompson sampling (Zhang, 2021) introduced an optimistic bonus on the loss function, making it possible to achieve a nearly minimax regret on the linear contextual bandits.
Exponentially Weighted Sampling. A classical technique for online learning is exponentially weighted sampling. This approach allows an algorithm to corral collection of policies in small regret. By constructing unbiased estimators for unobserved actions, [Auer et al. (2002) adapted the ideas to contextual bandits and proposed EXP4. Its regret suffers a polynomial dependence on the number of actions. For linear bandits with stationary contexts, the dependence can be reduced to logarithmic using an EXP2-type algorithm (Bubeck et al. 2012)). The algorithm can also be regarded as an EXP3 with a modified estimator, which can be implemented efficiently under specific action sets using stochastic mirror descent.
UCB-Based Algorithms. The concept of upper confidence bound first proposed by Lai & Rob- bins (1985) to solve multi-arm handits. The algorithm can be adapted to linear contextual bandits with infinite number of actions by analyzing the dynamics of the confidence set using an elliptical
lemma DDan et al. 2008 Li et al. 2210;; [Abbasi- Yadkori et al. 2011). However, it is hard to get generalize the approach broader function class. A recent line of works showed the contextual bandits could be reduced to regression oracles (Foster et al.) 2018 Foster & Rakhlin 2020). This observation pointed out way for UCB-based algorithms to work on general function classes. However, the algorithm suffers from a polynomial dependence on the number of actions, which incapable of infinite action sets.
the potential lemma for other function spaces, making it difficult
B IMPLEMENTATION OF THE PROPOSED ALGORITHM
In this section, we discuss the implementations for our main algorithm FGTS.LP in practice. In particular, we present an efficient algorithm to sample from the distribution defined in 2 approxi- mately. Consider distribution p()) in which the probability density function over + is proportional to
[-1 (0) x exp (-B Σ T (0)) Po(O),
(5)
where 7,09 is the loss function defined in and Po is some prior distribution to be determined. One may see (()) identical to p()(O)) (0) if one chooses the uniform mixture of discrete distribution of support He as prior. For efficient implementations, we would use a continuous distribution to cover H instead. More details can be found in the following sections.
Inspired by Xu et al. (0022) we would use Langevin Monte Carlo (Roberts & Tweedie 1996 Bakry ct al. 2013) to take sample from (). In specific, on round t, we run the following subroutines for K, steps. For iteration step s = 1, ..... Kr, we set
1 O1,
log Po(O).)-1) + 23 Ei
(6)
where 61 Gaussian random matrices and T/t is the step size. This updating rule can be regarded discretization of the following Langevin dynamics
as the
dO(s)
VL (L( + + 3-'V log (s)) /28 dd
(7)
12

---

where 0 is the continuous time index and ((s) R is Brownian motion. It was shown under mild conditions, the above Langevin dynamics will converge to the stationary distribution 5
So it is reasonable to take sample from using LMC. We list the corresponding pseudo-code in Algorithm 2
Algorithm 2 LMC-FGTS.LP, General Framework
input: prior distribution Po: inverse temperature 3; exploration parameter X; number of iterations {Kr)21 step sizes (t.21)
sample matrix (0) E RRxx from H according to Po
for round = 1.... ... . do
O, - O (t-1)
for iteration
1,... K; do sample matrix Et,s ~ (0, lrxd)
O +r,s-1 M1ts 2=1 (O - me, log Po Po(Ot.s-1)+
end for e
K, take action (1) + arg e (a, ) where 0 is the t-th column of (
end for
is important to mention the above algorithm is a general framework for linear contextual bandits. The algorithm could be further refined into specific settings. For example, since we know linear policy set H. only contains matrix @ in which all columns are same, it is sufficient to record only one column of @ In the following sections, we discuss how implement the algorithm for specific linear contextual bandits, and also present corresponding simulation results.
B. MISSPECIFIED LINEAR CONTEXTUAL BANDITS
We first discuss the implementation for misspecified linear contextual bandits, i.e., the variants de- picted in Corollary 5. In this case, we parameterize any matrix O = 10 -.. 0) in H using any of its column vector 0. We choose the Gaussian distribution (T00, La/d) the prior Po. One can
check the expected length of random vector sampled from Po is 1, which matches the hypothesis set given by Assumption 3.1 and 3.3 function R2d TR.
In the algorithm, we slightly abuse [(() and use it to denote loss
(() (r(() - (a 0))² - max (a, 0). aEA(())
(8)
which is a counterpart of B for single round policies. We list the pseudo-code in Algorithm
Algorithm 3 LMC-FGTS.LP for Misspecified Linear Contextual Bandits
input: time horizon T, feature dimension d, misspecification level &, inverse temperature 3
exploration parameter X; number of iterations (Ke) h21i step sizes f1,.21t,221-
sample vector (()) ~ (0, Ia/4)
for round = T do
0.,0 + 0(--
for iteration s 1,... K, do sample vector Et, ~ (O.
0., 0t.--1 Nt. Σi=1 (I(
d.3 Ct,
end for (
Oc,k, take action (1) + arg max (a, 0(1) end for
Simulation Results. We generate the synthetic data in the following way: The horizon length set to T 3000 and the feature dimension is set to 100. We first generate On from unit sphere g {x dd ||x||2 1} randomly. On each round A 20 actions (a," (t)
h=--A are independently drawn from the same unit sphere. The reward action (!) is set to (a()))))
(a (t) 0o) + Unif(- where Unif(1, u) is the uniform random distribution in [t, u] for misspecification level Ç E {0, 0.05, 0.13. The observed reward of it is then given by (0)) = (a(") + g(o) where ((t) randomly sampled from Gaussian noise with standard devia-
tion 0.2.
13

---

theoretical re- sult given by Theorem 5.1 and Lemma 5.1 We set the temperature parameter / to 0.01 following Xu et al. 2022), which is the 1/4 of the variance of reward noise. On cach round t. the algorithm do K, 200 iterations and the step size of iteration is Ta,e 1/(ds). To accelerate the running speed of the algorithm, we do not find the precise maximum action in g in each iteration. We record the
We run Algorithm with exploration parameter À 1 according
maximum action and recompute it only in first 14 steps once for every 14 steps afterwards.
We compare our algorithm to LinUCB with adaptation misspecification (Zanette et al.
2020 and
Linear Thompson Sampling (Abeille & Lazaric (017). The result is shown in Figure
One can
see our algorithm has comparative performance with those existing algorithms.
boarth
Kaune
(a) < 0
(b) ( 0.05
(c) 0.1
The performance of Algorithm comparing with other linear contextual bandit algorithms. Results are averaged over 5 runs with standard errors shown as shaded areas.
Figure I:
B.2 LIFELONG LINEAR CONTEXTUAL BANDITS
This section discuss the practical implementation for lifelong linear bandits, i.e., the variants de- picted in Corollary 5.4 In this case, the linear policy set only contains matrices that can be decomposed using two matrices B E Rd and W [w,, Mx Thus, we do not need to maintain the whole sequence of models O it is sufficient to keep those two matrices. Moreover, rather than taking LMC iterations O we compute the gradient respective to B and W to update them directly.
In the algorithm, instead of taking LMC iterations on O, we compute the gradient to update B and W directly. The prior distribution is also defined on those two matrices. We take A klaxk/ d) and (0, M /k) as the prior distribution for B and W, respectively. We use different prior distribution for initialization which ensures the length of 0 is about 1 to improve the overall per- formance. On every iteration of round f, the algorithm computes linear policy for all historical
task o- and uses them to compute gradient. The loss function defined in We list the
pseudo-code in Algorithm 4
Algorithm 4 L.C-FGGS.L.P for (Generalized) Lifelong Linear Contextual Bandits
input:
task index sequence (m(0)] inverse temperature 3; exploration parameter X; number of iterations {Ke) 322i step sizes {1,..
Jt=ii
sample matrix (0)0) from orthogonal random matrices in Rdxk
sample matrix (0)) ~0, Lxx//k)
for round = f1 1.... .'' do (Br,o, W.,)) + (B(t-1) W((-))
for iteration s = 1, 1.... K, do sample matrix _ ~ NO0, Laxk) and W t, ~ NO, IxXM)
compute 01.5-1;; +- B 1, Wt.s-1,1 for i [M] where 1i i, is the i-th row of W t.s
B + B - T/, -= V ( (0, (m)m)))))) dk 18--1 2,, B + /23 1 M1,5 f,3
B
W.. W Wt,--1 nt.s D1=1 Vw (T) (l.m))))) --8-' m.
ne. W Wi.s-1 + /2 7 C,
end for
(B() W(0) + (Br,k,; )
compute 0(t) + (t.
m(t) m/)) where ((()
(t)
mies is the (0 row of W
take action (1) + arg max ( (a, 0(0)
end for
Simulation Results. We generate the synthetic data in the following way: The horizon length is set to T = 3000 and the feature dimension is set to d = 40. There are M 20 tasks and each of them appear in exactly T/M 100 rounds in sequential, i.e, the task round & is given by
14

---

m( [t/100]. The dimension of hidden subspace is set in k (2,3.4). The hidden linear feature extractor is a random orthogonal matrix in Raxk and each the task-specific vector {w:)_= are independent random vectors from unit sphere S {x R ||x||2 = 1}. On each round t, A 20 actions {aß
(f) (2) /i=1-.AA are randomly drawn from unit sphere sa-1, We fix
the misspecification level be Ç 0. The observed reward of action a given by r(0)
(a. (t) Bw ) + (((+) where <(4) is independent random Gaussian variable of standard deviation 0.2.
f with exploration parameter = v(dk + Mk)/(dT) and temperature parame- ter g-1 = 0.01. On each round f, the algorithm do K₁ = 100 iterations and the step size iteration is Tt. 1/(kks). Similar to misspecified linear contextual bandits, we record the maximum action and recompute it only in first 10 steps or once for every 10 steps afterwards to accelerate its running speed. Since there is existing algorithm for lifelong linear contextual bandits, compare the performance with running LinUCB on each task independently. The result is shown in figure 2
We run Algorithm
One
algorithm leverage the underlying representation with good constant
factor.
FETSUF
RCSUP
10.00
(b) k:
(c) A:
Figure 2: The performance of Algorithm 4 comparing with running LinUCB on each task. Results averaged over 5 runs with standard errors shown shaded areas.
C PROOF SKETCH OF THEOREM 5.1
This section presents proof sketch of our main Theorem 5.1 proof Theorem in Zhang 202TT. The main difference comes from the usage of covering number of the policy set and our decoupling lemma under misspecification.
We note the proof is similar to the
Let θ* [0],- ... 04] be the optimal policy in the c-net Hes For any linear policy e (a!*) 02 02) the Bellman error and (,(O) Aa (a, 0.) max (a, 07) as the feel-good error. Since (a!*) 0z) max, (a, O.)
10,,-. 0r), denote O, (
according to definition of a (*), can decompose the expected regret round by
E (a() (a) a(
(0)
Ai (0))) -))
+(E +C).
at!)ee
Besides, we construct potential function following the classical analysis for exponentially weighted sampling,
(+) = 3A
log
Σ
cxp
B ( I (o))
OEH.
The boundary value of the potential function follows
log [Heel
(0)
(!T)
(10)
The increment of potential function round f satisfies
E ((()
(t) - (t--1) < 3A
log E E Wexp (0)
-
(1I)
at))
a6 (a, 0.), the randomness on (() only casts an additive noise -23e(() A e,, a!)) to the term B (e*) - (((()) in the exponent. Since {(t)
Recall (0) = (r( (a(1), 0,))² max (en
constantly bounded and zero mean, the noise be controlled by selecting proper / according
15

---

to Hoeffding's lemma. With classical inequalities over logarithm and exponential, show the variation of potential function satisfies
(10) -0((-1) S
A.(O, (0)2 (a((+(((()A)A))) (0))
a(9) x(0,)(())
+ θ (0) + A(c |(c+ c)2
(12)
where -(0 (7) ) the misspecification of O' with respect to ground truth f(), One can see that the first two terms on the RHS of (12) are very similar to the first two terms on the replaced by a random Although (tt) and @ have the same margin, O is correlated with (*) but O
(O()),
RHS of ( But with one critical difference, the chosen policy ( in
policy @
independent from a (t), As result, ( (());((())) Ee A (+) but (. , [Ar (e(t), (+)) is necessary equal (e("))//((())) a ).) Therefore, we cannot get a regret bound by combining 9 (TO) and 12 directly.
This is where the decoupling lemma helps. Following Zhang 2021). one can get the following lemma for linear models,
E ( (
(O)) (()))
aa)) S
E a, + O((d). A
(13)
For our usage, in order to achieve optimal dependence with the covering radius and misspecification, we derived a decoupling lemma includes the corruptions. In particular, Lemma D.2 implies
E a(U) a00,
S
1 X 2
+ C((a)")A,(())""")))
+ + (d (c ()+ (2+
(14)
By combining 9.
10
and
with 3 = (1), we conclude that
log HHl (e + 2)
Reerre (T)
[f (a( a(1)
E
= AdT (e +)T+
(a
A
One can obtain the desired statement using = We note our analysis uses refined way to deal with the covering radius and misspecification. One can only get a regret bound of O( /ddTlog log [P + TV d(e + ()) if uses (3) and follows the proof in Zhang 2021) faithfully, which has worse dependence (c ().
D FULL PROOF OF THEOREM 5.1
In this section, we will provide complete proof of Theorem 5.1
The following decoupling lemma a critical structural lemma for our analysis, which is generalization of Lemma in [Zhang (202I)
Lemma D.1 (Decoupling Lemma). Let P a joint distribution over two I2d space, i.e., A(Rd x R.). For any conslunt À >> O, we have
0.25
E (0.0)~
(, < dd
E (0,
(0.0)~P
(0' )~P
where (0, Φ) on LHS is a sample from P while (0, x) and (0', Φ') on RHS are two independent samples from P.
16

---

Proof. Let Σ (( 00 be matrix in Raxd. Denote E , set of orthogonal
eigenvectors of E. Let 8, = (( 2 Then,
E 00 Φ)
E
0. (E.. Φ)
(0.0)~u
(0.0)~P
2A
0.5s:
E
(0 E:)
(5:. 1))
8i
A
0.258;
(0 +
(E:, 6)3)
(15)
(0,0)~P
where the first equality follows from 0 0.5a + 0.5b2. For the first term, we have
Σi= (0, E: and the inequality follows from ab S
A
E 10.0)~P St
(
Ad. i=1
(16)
For the second term, holds that
0.25
0.25
s/(E;,
Σ
(0, Φ'y² (0.6)~P
À 1m1
(0.0)~
A
0''6") )~P
d
d
0.25
(E) '')(0, (y) (1)
X
(0.0)~P
(0' (0'."'>' x''
0.25
Σ 0, E.) (E,, ('))
E
X
(0.0)~P
(0' )'PP
0.25
E (0.0)~P -')
(0.61)
(17)
where the first equality follows from the definition of 8;, the second equality holds since a) (0, (0, +. Σg; 0 for all i * j and the final equality follows from the def-
inition of E: By plugging (66 and 17 into [15). we conclude that
0.25
E (0, Φ) S Ad (0.0)~P
E 10.6m~P
(0, 6)
(0' d'
Using this lemma, we can bound the expectation of the inner product of two correlated random variables using the expectation of the inner product of two independent random variables with the corresponding margin. To provide a nearly minimax bound with optimal dependence on misspecifi- cation, we further propose decoupling lemma that takes misspecification into account:
Lemma D.2 (Decoupling Lemma with Misspecification). Lei P be joint distribution over two Ted space, i.e., P E A (Rd Rd). Let C(-) Rd + RR be a function such that [C(0)] I for all O E IRd. For any constant À O, we have
(0 S Aid 1) + (0.0)>
E
2 x
+ 4 +
0.25
(0.0') 8C(0) (0, (0,
X
(0
(0' + PP
where (0, Φ) on LHS is a sample from P while (0, x) and (6', Φ') on RHS are two independent samples from P.
17

---

Proof. Let P- be auxiliary distribution over ARR*I ( in which each element is (0+.0.) .+) = (00 C(O)) 10 ,1]) where (0, Φ) ~ P. For two independent samples (0+, Φ+)
and (0' (04,, we have
0 (+.0+) + +
(18)
(+. (0, + 80(0) (0, + 16C
(19)
Apply Lemma D.I to distribution P+, we have
0.25
E P
(++ S M(d 1)
E (+.
(20)
X
(0 Φ InP_
(0 / JwP
Plugging
18 and 199 into 20). we have
0.25
00 の) + 4C(0) - +)+ À
+ -0((0)) (0. +0.00)+16((0)))
(0.0)~P
( PP
(0' N'P
Since |C(0)) v f always holds, we can further conclude that
E (0, の) S x(d 1)+ + 452 (0.0)~P
0.25
x 4Ç
+
E (0.0)~P (0' )
+ (0, (0,
X
Denote (t) = (2(1-1) Uf f(0} be the history before the agent chooses action on round t. Let -" = jo..... 07.1 be the optimal policy within c-net He. For any linear policy @ (0..... 0r),
denote
O. (0) = (a 0. 01), (7())
max (a, 0.) max (a, 07) aEA(1))
aEAtr)
Note A, is referred the Bellman error and Aj is referred the feel-good error. The next lemma shows that we can decomposed the expected regret using these two notions: Lemma D.3. Under Assumption
3.7 the expected regret on round satisfies
E ((0(aa)) (1) (()((((())
E a 100
A.(0 aa - (0)))(((011)) + 2(E C).
Proof. For any action a E A, we have
07) (a) + (a) (a.
(a, 0(f())) 07)1 (() + +
where the first inequality follows from triangle inequality and the second inequality holds follows from Assumption 3.1 and the definition of c-net with (a, (((())) (a, 0;) I ||a||2 ((()())
0, ||2 S Ç. Similarly, we have 07) (a) (e (). Thus,
E a(t) (9
(al) (a())) <
E
(ab)) 0,) - (a"),o))
00) + 2(c + C). (21)
a l
Moreover, have
E a (6) (1())))))
(a! 0,) (aa')
max (a, 0,) - (a(),7)) aEA(
(())
E
max (a, 0,) - max 0.) + (a(1). .,) (t) -(a()) (e))(t))
(())
a(,((t)
(e (0) - ()0)
E a0 (0
(22)
where the first equality follows from the fact that action (0) maximizes (a, 0.) and thus max tto (a, 0,) (a 02). By combining (1) and 22 we obtain the desired result. n
18

---

The following lemma shows connection between A and potential function.
Lemma D.4. Define potential function
1 log Σ BEH.
(1() = 3A
exp 8 Σ
Let C=(a())=== (((( (a()) (0)) be the misspecification of Oe on action ( with respect to
ground truth f() For any E [0, 8 E (0,0.01) and X E [0, 1]. under Assumptions 3.1 and 3.2 the expected increment of potential function on any round satisfies
(1()) pb(--1)
0.25
E (00),(p0
E
E P(P(
a a00
88 () + 48A+
E (~H())
c)²
Proof. the expected increment of the potential function in round conditional on the reward function and context in round satisfies:
E
((0)_ - (1--1)
a(t),,00po
Σ exp
B Dr (O' - (()
E
log
BA alt) (11) (t)
ΣOEN. exp
B - (L6) - (()
Σ MEH exp
- 3 E (67 (0)) exp
log
BX
atl p0upp
ΣOen. exp 3 3 (()()))
exp (B(L - -L)
log
BX
p0u (
P
(B(L - (()) -
<
E a
log
E
E
exp
(23)
BA
p alo) P
where the last equality follows from the construction of p(t) and the last incquality follows from Jensen's inequality. Moreover, we can decompose the loss function for any policy e according to
L (e) (7( ()))))) X max (a, 0.) aEA(()
max (a, O₂) (a) + g(1) - (a(*), 0,))2 aEA(1) =C)(a + +(()) - (0))) - max (a, 0z),
(24)
aEA(()
where the first equality follows from the definition ,0) ((0 + g(t) and the second equality follows from the definition of C. For the optimal policy O* in e-net, one can see that
( (e)) = (a,(a (9) + (0)) x max (a, 07).
(25)
a()
Combining 24 and 25
the terms in the exponent can be computed by
(( (()
= (., - 23 (0, - a + (AA;((O)
(26)
Since g(9) is zero mean random variables with range 2, according to Hoeffding's lemma, we have
E
(0) s exp
(27)
( a(t)
19

---

In case that B (0, 0.01], we have -
B B -0.53. Plugging (26) and (27 into 23 gives
E
x(+)) (((-1)
a(0,r(9)) (0()))))
log E exp ( (- ",00//00000000000000000000",,""0 @uP(N
(347)))))))))))
According to Cauchy- Sehharz-- inequality, we can decompose RHS by
E a(O (1)
(p(1) T 1((-1))
0.5
E at
log E @NP(()
( (-ACC(((()A
exp
3A
(2
+
0.25
E
log
E exp (0.10())
(rt((t)
+
0.25
E
log
exp (49)4;(0))
(28)
AA ((0
(~P(tt)
I3
For the first term,
I 5
0.5
E
log E P-t(tt
1-4 163 c)²)
B8
(0))))))
0.25
(C) (1) + 88 + c)2
E
E P
(29)
P(O
where the first inequality follows from e" <1+++t" for |x| < S 1 with [C(( I c S 2,
@ (1) < 2 and B E (0, (0.0. and the second inequality follows from log(1 + x) S for
x 11 For the second term,
0.25
12 -
E
log
E PNP(
1 (O,
BA
a
0.25
E
E
(30)
X
P-1(
where the first inequality follows from e-* 1 0.5x for E [0. 1] with a
< 2 and
(0, 0.01), and the second inequality follows from log x) I r for x < For the third term,
13 <
0.25
E
log E P-P
1 (+44)))( + +
BA
IE ()
4BA,
(31)
(-P(1)
where the first inequality follows from < + x for | S 1 with [A) < 2,
3 E (0, 0.01] and À E [0, 1], and the second inequality follows from log(1 + x) I x for r 2 -1. Combining
29
30p and (31) with (28). we have
(e) (1-11)
0.25
A + (0, [9]
a(t) (0)
X
(0 P
88 + 48
+
A (
x (E + 2)2
(x)(())
20

---

The following Lemma upper bounds the total change of the potential:
Lemma D.5. Under the settings of Lemma D.4
we have
( ( I
log e,H,e, l12,00)
BA
Proof.
The statement can be proved by combining
(0)
log
exp(o)
log [Hl)
B3
BA
OEH,
and
T B
(T)
1
log max exp
Σ L
20,
BA
OEH,
where the second inequality follows from O E Me.
Note the chosen policy (!) Lemma D.3 is correlated with the selected action (() while random policy θ in Lemma D.4 is not. The following lemma presents connection between these two notions.
Lemma D.6. Let C. Rd - R be function such that [C.(a) c c any A. Then,
E
AT(0())
E
(T()),
@
(~P(()
and also
E al0 60,60
A,(O(),a
0.25
E
E @~P(())
(0)+ (
X
x(d+1)+
{ + 5)3 +((
Proof. According to the construction of p(t), the conditional distribution (0)() is identical to distribution ~ p(t), This directly gives
(7
E (A))). PxP(())
Moreover, apply Lemma D.2
to joint distribution (t) ( 0,) conditional on 22(²) have
(a
0
0,)
0.25
E
E
(a 0. 0;)² (a) o. 0;))
att) a09), 0 (
a(i P(P)(s)
A(d +
(e 2)2 4(e C)-
The desired statement can be obtained using the definition of A
Now, we ready prove Theorem 5.1
Proof of Theorem 5.1 We choose the parameters according
log H.
(E + +CPT
01 0.01.
(32)
dT
Denote
0.25
A0 9Ca
X
E
E
(7
(0
P(e)
(mP())
According to Lemma
D.6
we have
E
()() a()) A;(0(1))
(c+ < x(d+1) + 5)2 + +4(c+ 9).
(33)
20 (0
21

---

According to Lemma D.4 we have
83
(p(t) (((-1))
S -x +
X (e+
(34)
a(0, ,0,,r
Combining (33) and 34) gives
(e( (+) - - -ii()
E a(*) e go
E at9, (0000000()))
((t-1) -
+
4+ 83
A (c+
+(c+ ().
(35)
Moreover, have
Regret (T)]
(0) )
E
a(0 (1)
E
A,(O(1), -2)(((0))) 2(e CCT
a( (
T
(tt-1) -11))
+ +Ald + 1+ 43)T + 4+ 83 X
() + C)T
1= a(t) (0)))())))
4 83
log H.l + X(d 1 43YT +
(e + 6 C)T,
6(c
BA
X
where the first inequality follows from Lemma D.3 the second incquality follows from 35 and the
last inequality follows from Lemma D.5 With the parameter defined in (32) we conclude that
E[Regret (T) s o (oooVoolo
log He Tvā(c+
L
E PROOF OF COVERING NUMBER FROM SECTION 5.1
In this section, prove covering number bounds for some specific linear bandit settings. We first introduce a classic result on the covering number of the unit ball.
Lemma E.1 (Lemma 5.2 in Vershynin (012), Restated). The unit Euclidean ball Bd (x E TRd ||x|| < 1) equipped with the Euclidean metric satisfies for every 6 >> 0 that
N(B e, 112) S (1 2e-)
With this lemma, we can directly prove the covering number of stationary linear bandits.
Lemma 5.1 (Covering Number for Misspecified Linear Bandits). Under Assumptions 3.1 and 3.3 the metric entropy of linear policies satisfies
log NHH, c, || 112,00) s Oddloge
Proof. We will prove this lemma by constructing an e-net for H. Let Bdd be the minimum e-net of unit Euclidean ball 8d L2 distance. Let H., be the set that contains every matrix (0.... 0 for all
E Bd According to Lemma E. we have [H = | < (1 (1-2c-1)d
We then show H. an e-net of H under Assumption 3.3 For every linear policy (0. ... 0. there
exists 0 Bd such that 00 0 < according definition of Bd. This shows 00 ...... 0 E H.
an e-approximation policy [0, ..... ,0) which implies H. is indeed an e-net of H. As result, we can bound the metric entropy by
log NHH, )12,50) I log |H4. Odlog
22

---

One can naturally extend the proof to non-stationary linear bandits with bounded switches: Lemma Covering Number for Non-Stationar Linear Bandits with Bounded Switches). Under Assumptions 3.7 and 3.4 the metric entropy of linear policies satisfies
log N (HH, e, l12,cc) S OodSloge + Slg T).
Proof. We will prove this lemma by constructing an e-net for H. Let B. be the minimum e- net of unit Euclidean ball Ba in L2 distance. We build set He by mapping any sequence (t1, tt) with 1 < 4 < ... < I T and S + 1 vectors fo....,0
B to the matrix 0, 0s] where the first 0. occurs index 4. describes the round of i-th (0n.... On, ... ...
switch and O, characterize the parameter after the switch. The size of He can be bounded by
T
HHel S BBI <T - (1-2541)))+4)
where the first term is the number of possible (t:) and the second term is the number of possible 0:. We then show He is an e-net of H under under Assumption 3.4 Every linear policy in H can also be written in form [0u.... ... P., 01, ... 0s] which can be covered by some [0u.- ... Pb ... ... Gs] with the same switch locations and corresponding parameters. Ac- cording the definition of Bd 110, 0:11 for every i and thus H. e-net of H.
As result, we can bound the metric entropy by
log (H,, 1l2,00) & log [Hel OdS loge + SlogT).
For non-stationary linear bandits with bounded path length, will show the e-net for some bounded switches instances can be transformed into a desired covering:
Lemma 5.3 (Covering Number for Non-Stationary Linear Bandits with Bounded Path Length). 3.5 the metric entropy of linear policies satisfies
Under Assumptions 3.
log (HH, c, 112,00) Oddogg dogc-loge" + Pc- log Po
Proof. Let 12 be the e/2-net covering of non-stationary bandits with no more than 2Pc (see
Assumption 3.4b. We will show Hep is e-net covering of non-stationary bandits with path length no more than P:
For some linear policy θ = [61, 02. ... Orl E H such that Σi= 0 - 0,-1 S P. consider a sequence 1 to < f1
tM 1 T where is the minimal index such that ||: 0 c/2 for all 2 1. Denote θ = [0,,... 0,, ... ,,,,, Gearl as the linear policy, which quantizes the parameter drift in which the first Os, occurs index 4, Since the number of switch of θ is bounded by M < P/(e/2) < 2 the e/2-net H.,/ contains an e/2 approximated policy of θ.
Denote the policy as ④.
Since deviation of each single round policy in the same slice is no more than e/2, we have ||
+ 122.00 S e/2. According to the definition of e/2-net, we also have ② θ 12,000 S c/2. According triangle inequality, have || 11 < This shows that + always has an e-approximation within He/2 and thus He/2 is indeed an e-net H. As result, we can bound the metric entropy using Lemma 5.2
log N |l )12,,=) < log fL./2l < Oddoog + d + Pe log T),
where the extra dlloge -1 term follows from the special case S 2 < 1.
Now we consider the lifelong linear bandits. Its covering number bound is essentially the covering number of low-rank matrices.
Lemma 5.4 (Covering Number for Lifelong Bandits with Shared Representation). Under Assump-
tions 3.7 and 3.6 the metric entropy of linear policies satisfies
log N(H, 112,00) & O(dk log - + kM &Mloge -1).
23

---

Proof. We will prove this lemma by constructing e-net for H. This is done by constructing c/2- net for all possible feature extractor B and an e/2 e/2-net t for all possible tasks specific vectors {w; / In specific, we build set Be/2 such that there exists B E Ba/2 such that ||B B/12 c/2 and Wa/2 such that there exists {w, Ji=1 We/2 such that ||: w, I c/2 for all i. We generate the e-net by mapping every pairs of B and {wi)i=1 to matrix [0(1] 0(4) where の Bw m(n))
In any round with g(t) = mt the vector g(() = mm with corresponding B and Wm in e/2-net satisfies
|1000 1 = Bw me
Bw m moltolle ll2
Bw mic
Bw to ll
Bw m())
Bw m0
ll
B |l m())
w
m
2l2 + B
B||2 m ll
- c/1 c/2
where the second inequality follows from triangle inequality and the third inequality holds since B is orthogonal matrix. This shows any task can be e-approximated and the generated set is indeed an e-net. As result, with Lemma E.I we conclude that
log (HH,, e, l12,00) S log [Be/2| + log (Wazl S O(dk loge kM log 7
F LOWER BOUNDS IN SECTION 5.1
In this section, give regret lower bounds for some specific linear bandit settings. We first present some existing result in the literature. It is easy to check the corresponding hard instance satisfies our formulation.
Lemma F.1. (Theorem 24.1 in Lattimore & Szepevvári (2020). Restated) Under Assumptions 3.1 for any algorithm, there exists a bandit instance for which
3.2 and 3.3
E[Regrot(T) 29 (.(dVT))
Lemma F22 (Theorem in Cheung et al. (2019). Restated) Under Assumptions for any algorithm, there exists bandit instance for which
3.1
3.2 and
E. Regret (T)) 22 (
Lemma F.3. (Theorem Yang et al. (2020), Restated) Under Assumptions 3.1 any algorithum, there exists bandit instance for which
3.2 and for
3.6
[[Regret(T)) O (VdKKT +
Lemma E.4. (Theorem F.1 in Lattimore & Szepesvari (2020) Restated) Under Assumptions 3.1 and 3.2 for any algorithm, there exists a bandit instance for which
E(Regret(TT) 2 Ω (T /d/ logTt).
Remark F11 In Lattimore & Szepesvari (2020). they proved a lower bound in the order of Q(min (T,K) /) log( ())), where K is the number of actions. Here we choose K = T for simplicity.
We further prove lower bound for non-stationary linear bandits with bounded switches. Lemma F.S. Under Assumptions 3.1 for which
3.2 and 3.4 for any algorithm, there exists bandit instance
Regret (T)] 2 22 dv (d
Proof. Without loss of generality, assume T is divided by S. Consider bandit instance where the switch occurs at round T/S, 25,,2T/S..... .... Note the reward functionn after different switches are independent. Thus, according to Lemma F.1 any algorithm suffers 2(d//T/S regret in any interval between switches. Since there are S switches, for any algorithm, there exists bandit instance for which ([Re 2 ((dVST).
24

---

The lower bounds result in Section 5.1
can be obtained by combining above lemmas:
Combining Lemma
and Lemma
gives Proposition 5.1
Combining Lemma
R.5
and Lemma F44
gives Proposition 5.2
Combining Lemma Lemma F.1
and Lemma
F.4 gives Proposition 5.3
Combining Lemma
3 and Lemma F44
gives Proposition 5.4
25


Reviews:
[{"review_id": "ypnAXr2Z1J3", "reviewer": "Reviewer_oQHX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors use Feel Good Thompson sampling to derive general bounds for three different linear contextual bandits 1) non-stationary bandits with S switches, 2) non-stationary bandits with path-length P and 3) lifelong bandits over M tasks. In each case they show that their general bound is close to optimal of the lower bound (nearly minimax for 1 and 2 but 2 has a bigger gap between upper and lower bounds). ", "summary_of_the_review": "Overall it is a good paper that gives a near-optimal algorithm for the lifelong learning setting.", "strength_and_weaknesses": "The algorithm proposes a general framework that then is able to be close to optimal for the three cases that are shown. They introduce an algorithm that is close to optimal for the lifelong case.\n\nThe main drawback is that it would be been good to see some simulations results of the methods to see if even in toy examples, these bounds hold in simulation and that also gives a good visual of the constants involved in the algorithm.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "oXweZYI5W6V", "reviewer": "Reviewer_iGav", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work aims to provide a unified Thompson-sampling based algorithm for linear bandits. It provides nearly-matching upper and lower bounds, and also discusses the results in some specific cases: misspecified linear bandits, non-stationary linear bandits with bounded switches, non-stationary linear bandits with bounded path length, and lifelong linear bandits with shared representation.", "summary_of_the_review": "Generally speaking, this work tries to deepen the study of feel-good Thompson-sampling algorithm proposed in Zhang (2021) and it does make some contribution to the field. I would appreciate that if the weaknesses above could be solved.\n\n\n=========\n\nAfter rebuttal:\nThanks for your efforts. I increased the score to 6.", "strength_and_weaknesses": "Strength:\n1. The paper is generally easy to follow and well-organized.\n2. The literature review is detailed.\n\nWeaknesses:\n1. In section 4.3, the comparison with FGTS mentions that \"the original FGTS samples over models (or equivalently, reward functions) rather than policies\". However, a more vital question is: what is the corresponding analytical challenge?\n2. Since Algorithm 1 is not computationally efficient and even hard to implement, what are the possible solutions? Any thoughts?\n3. In section 5, when discussing the results in the four variations of linear bandits, the contribution of this work would be clearer if the author(s) could provide a comparison between the existing bounds and those provided by this work.\n4. Small typo: page 6 --- before Definition 4.2: should be \"we define the approach of $\\epsilon$-net and covering number.\"", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "-4WqzVBoSD", "reviewer": "Reviewer_vpXj", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces a framework that covers several variants of linear contextual bandits, and proposes a variant of feel-good Thompson sampling introduced in Zhang (2021). The theoretical results show that the proposed algorithm has (near-)optimal regret bounds for various settings of linear contextual bandits.", "summary_of_the_review": "My main concern is about the practicality of the proposed algorithm. For example, how to implement even an approximation of the proposed algorithm.", "strength_and_weaknesses": "The main strength of the paper is that the proposed algorithm has (near-)optimal regret bounds for several variants of linear contextual bandits.\n\nThe main weakness is that the proposed algorithm is (almost) unimplementable. I could not see a practical way to implement this algorithm.  Besides this , I have several questions and comments.\n1. The paper claims resolving the respective open problem in each setting of linear contextual bandits. I think it is better to clearly describe these open problems.\n2. Why $\\pi$ is called (meta-)policy? To me, it is the whole model of $T$ periods.\n3. It seems that the proposed algorithm does not need to know the parameters including the misspecification level, the bound of number of switches denoted by $S$ and the bound of the path length denoted by $P$, right? If my understanding is correct, could the authors elaborate more on how the analysis of the algorithm deals with these unknown parameters?\n4. In terms of the algorithm design, why at each period, the algorithm samples the whole model of $T$ periods? I mean at each period $t$, why we need to obtain samples of $\\theta$'s before $t$? I think this is the main step that makes the algorithm not implementable.\n5. In terms of the regret bound in Theorem 5.1, how sensitive is this bound to the choices of $\\lambda$ and $\\beta$? The conditions of $\\lambda$ and $\\beta$ are in the form of $\\Theta$. What are the potential ranges of the hidden constants?\n6. The analysis follows and extends that in Zhang (2021) based on the notion of Decoupling Coefficient (DC). After Zhang (2021), Dylan et al. (2022) introduces a very similar notion called Decision-Estimation Coefficient (DEC) and proposes a general algorithm based on DEC. However, their algorithm's regret bound even for linear bandits is suboptimal in $d$. Could the authors elaborate why the analysis based on DC gives the optimal dependence in $d$, while that based on DEC does not?\n\nDylan J. Foster, Sham M. Kakade, Jian Qian, and Alexander Rakhlin, The Statistical Complexity of Interactive Decision Making, 2022\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject