Doubly Robust Thompson Sampling with Linear Payoffs
Authors: Wonyoung Kim
Gi-Soo Kim
Myunghee Cho Paik
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Linear contextual bandits
Thompson Sampling
Using contexts of all arms
An improved regret bound

Abstract: A challenging aspect of the bandit problem is that a stochastic reward is observed only for the chosen arm and the rewards of other arms remain missing.    
The dependence of the arm choice on the past context and reward pairs compounds the complexity of regret analysis.
We propose a novel multi-armed contextual bandit algorithm called Doubly Robust Thompson Sampling (DRTS) employing the doubly-robust estimator used in missing data literature to Thompson Sampling with contexts (\texttt{LinTS}).
Different from previous works relying on missing data techniques (Dimakopoulou et al. [2019], Kim and Paik [2019]), the proposed algorithm is designed to allow a novel additive regret decomposition leading to an improved regret bound with the order of $\tilde{O}(\phi^{-2}\sqrt{T})$, where $\phi^2$ is the minimum eigenvalue of the covariance matrix of contexts.
This is the first regret bound of \texttt{LinTS} using $\phi^2$ without $d$,  where $d$ is the dimension of the context.
Applying the relationship between $\phi^2$ and $d$, the regret bound of the proposed algorithm is $\tilde{O}(d\sqrt{T})$ in many practical scenarios, improving the bound of \texttt{LinTS} by a factor of $\sqrt{d}$.
A benefit of the proposed method is that it uses all the context data, chosen or not chosen, thus allowing to circumvent the technical definition of unsaturated arms used in theoretical analysis of \texttt{LinTS}.
Empirical studies show the advantage of the proposed algorithm over \texttt{LinTS}.

Doubly Robust Thompson Sampling with Linear Payoffs
Wonyoung Kim Department of Statistics Seoul National University (raser347@smus ac. kr
Gi-Soo Kim
Department of Industrial Engineering & Artificial Intelligence Graduate School
UNIST gisookimuunist.om ac.
Myunghee Cho Paik Department of Statistics Scoul National University Shepherd23 Inc. nyunghoechooaikkesm..aa ac. kr
Abstract
A challenging aspect of the bandit problem is that stochastic reward is observed only for the chosen arm and the rewards of other arms remain missing. The dependence of the arm choice the past context and reward pairs compounds the complexity of regret analysis. We propose a novel multi-armed contextual bandit algorithm called Doubly Robust (DR) Thompson Sampling employing the doubly-robust estimator used in missing data literature to Thompson Sampling with contexts (LinTS). Different from previous works relying missing data techniques (Dimakopoulou et al. [2019). Kim and Paik (2019), the proposed algorithm is designed allow a novel additive regret decomposition leading an improved regret bound with the order of -(0-~ ²VT), where ø² is the minimum eigenvalue of the covariance matrix of contexts. This is the first regret bound of LinTS using d² without the dimension of the context, d. Applying the relationship between o² and d, the regret bound of the proposed algorithm is Ö(dVT) in many practical scenarios, improving the bound of LinTS by a factor of vd. benefit of the proposed method is that it utilizes all the context data, chosen or not chosen, thus allowing to circumvent the technical definition of unsaturated arms used in theoretical analysis of LinTS. Empirical studies show the advantage of the proposed algorithm over LinTS.
-2
Introduction
Contextual bandit has been popular in sequential decision tasks such as news article recommendation systems. In bandit problems, the learner sequentially pulls arm among multiple arms and receives random rewards on each round of time. While not knowing the compensation mechanisms of rewards, the learner should make his/her decision to maximize the cumulative sum of rewards. In the course of gaining information about the compensation mechanisms through feedback, the learner should carefully balance between exploitation, pulling the best arm based information accumulated far, and exploration, pulling the arm that will assist in future choices, although it does not seem to be the best option at the moment. Therefore in the bandit problem, estimation learning is important element besides decision making.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Table 1: The shaded data are used in complete record analysis (left) and DR method (right) under multi- aummi contextual bandit settings. The contexts, rewards and DR imputing values are denoted by X, Y, and y YDR, respectively. The question mark refers to the missing reward of unchosen arms.
2=2
Arm 1
(1)
(2)
?
Arm 1
(1)
(1)
(2)
Y (2)
Arm 2
X2(1)
?
Xa2 (2)
Yng(2
Arm 2
(1)
(1)
Xag (2)
Yag (2)
Amm 3
Xo, (1)
Ya (1)
(2)
Arm 3
(1)
(1)
(2(2)
n9 (2)
Arm 4
X1(1)
? (2)
? Arm 4
Xa(1)
(1)
(2(2)
YP (2)
A challenging aspect of estimation in the bandit problem is that stochastic reward is observed only for the chosen arm. Consequently, only the context and reward pair of the chosen arm is used for estimation, which causes dependency of the context data the round the past contexts and rewards. To handle this difficulty, we view bandit problems as missing data problems. The first step in handling missing data is to define full, observed, and missing data. In bandit settings, full data consist of rewards and contexts of all arms; observed data consist of full contexts for all arms and the reward for the chosen arm; missing data consist of the rewards for the arms that are not chosen. Typical estimation procedures require both rewards and contexts pairs to be observed, and the observed contexts from the unselected are discarded (see Table I.. The analysis based on the completely observed pairs only is called complete record analysis. Most stochastic bandit algorithms utilize estimates based on complete record analysis. Estimators from complete record analysis are known to be inefficient. In bandit setting, using the observed data whose probability of observation depends on previous rewards requires special theoretical treatment.
There are two main approaches to missing data: imputation and inverse probability weighting (IPW). Imputation is fill in the predicted value of missing data from specified model, and IPW is to use the observed records only but weight them by the inverse of the observation probability. The doubly robust (DR) method [Robins et al. 1994 Bang and Robins 2005) is a combination of imputation and IPW tools. We provide a review of missing data and DR methods in supplementary materials. The robustness against model misspecification setting since the probability of observation or allocation to an arm is known. The merit of the DR method in the bandit setting is its ability to employ all the contexts including unselected arms.
missing data settings insignificant in the bandit
We propose a novel multi-armed contextual bandit algorithm called Doubly Robust Thompson Sampling (DRTS) that applies the DR technique used in missing data literature to Thompson Sampling with linear contextual bandits (LinTS). The main thrust of DRTS is to utilize contexts information for all arms, not just chosen arms. By using the unselected, yet observed contexts, along with novel algorithmic device, the proposed algorithm renders a unique regret decomposition which leads to a novel regret bound without resorting to the technical definition of unsaturated arms used by Agrawal and Goyal (2014). Since categorizing the arms into saturated vs. unsaturated plays a critical role in costing extra vd, by circumventing it, we prove a Ö(dvT)) bound of the cumulative regret in many practical occasions compared to (dB/2 VT) shown in Agrawal and Goyal 2014
The main contributions of this paper are as follows.
We propose novel contextual bandit algorithm that improves the cumulative regret bound of LinTs by a factor of vd (Theorem 1) in many practical scenarios (Section 4.1 This improvement is attained mainly by defining a novel set called super-unsee unsaturated arms, that is utilizable due to the proposed estimator and resampling technique adopted in the algorithm.
We provide novel estimation error bound of the proposed estimator (Theorem which depends on the minimum eigenvalue of the covariance matrix of the contexts from all arms without d.
We develop a novel dimension maneensoon-fre concentration inequality for Gabb-aassiinn vector martingale (Lemma 4 and use it in deriving our regret bound in place of the self-normalized theorem by Abbasi- Yadkori et al. 2011].
We develop a novel concentration inequality for the bounded matrix martingale (Lemma 6 which improves the existing result (Proposition 5) by removing the dependency on d in the bound. Lemma also allows eliminating the forced sampling phases required some
bandit algorithms relying on Proposition 5 Amani et al. 2019 Bastani and Bayati 2020

---

All missing proof's are in supplementary materials,
2
Related works
Thompson Sampling [Thompson, 1933 has been extensively studied and shown solid performances
in many applications (e.g. Chapelle and Li (011)) Agrawal and Goyal| [2013] is the first to prove theoretical bounds for LinTS and an alternative proof is given by Aheille et al. [017]. Both papers show (dd//2 /T) regret bound, which is known as the best regret bound for LinTS. Recently, Hamidi and Bayati 2020 points out that (dd VT) could be the best possible one can get when the estimator used by LinTS is employed. In our work, we improve this regret bound by a factor of vd in many practical scenarios through a novel definition of super-unsature unsaturated arms, which becomes utilizable due to the proposed estimator and resampling device implemented in the algorithm.
Our work assumes the independence of the contexts from all arms across time rounds. Some notable works have used the assumption that the contexts are independently identically distributed (IID). Leveraging the IID assumption with margin condition, Goldenshluger and Zeevi (2013) derives two-armed linear contextual bandit algorithm with regret upper bound of order and Bayati [2020] has extended this algorithm to any number of arms and improves the regret bound
Bastani
to Oddlogg2 d logT). The margin condition states that the gap between the expected rewards of the optimal arm and the next best arm is nonzero with some constant probability. This condition is crucial in achieving a OlogT)) regret bound instead of ((VT). In this paper, we do not assume this margin condition, and focus on the dependence on the dimension of contexts d.
From missing data point of view, most stochastic contextual bandit algorithms use the estimator from complete record analysis except Diiaaooooloor et al. [2019] and and Paik (2019). Dimakopoulou
et al. 2019 employs an IPW estimator that is based the selected contexts alone. Dimakopoulou
et al. 2019 proves Ó(dve-ITI+ N) regret bound for their algorithm which depends the
number of arms, N. Kim and Paik 2019] considers the high-dimensional settings with sparsity, utilizes DR technique, and improves the regret bound in terms of the sparse dimension instead of the actual dimension of the context, d. Kim and Paik [2099] is different from ours in several aspects: the mode of exploration (e-greedy vs. Thompson Sampling), the mode of regularization (Lasso vs. ridge regression); and the form of the estimator. A sharp distinction between the two estimators lies in that Kim and Paik (2019) aggregates contexts and rewards over the arms although they employ all the contexts. If we apply this aggregating estimator and DR-Lasso bandit algorithm to the www-dimensiona setting, we obtain regret bound of order O Nd oF /T) when the contexts from the arms are independent. This bound is bigger than our bound by factor of d and N. It is because the aggregated form of the estimator does not permit the novel regret decomposition derived in Section 4.2 The proposed estimator coupled with a novel algorithmic device renders the additive regret decomposition which in turn improves the order of the regret bound.
3 Proposed estimator and algorithm
3.1 Settings and assumptions
We denote a d-dimensional context for the 5th arm at round t by Xt(t) E Rd, and the corresponding random reward by (t) for i L..... N. We assume E [Y;(t)) Xx())] = X,(t)" for some unknown parameter B Rd. At round t, the arm that the learner chooses is denoted by a, e (1....,N) NJ. and the optimal arm by aj := arg max;= (I) Let regret(t) be the difference between the expected reward of the chosen arm and the optimal arm at round 1, i.e., (Igrel(I) == Xaz (1)" 3 Xa, (1) 3. The goal is to minimize the sum of regrets over T rounds, R(T)= == Σt rt)r The total round T is finite but possibly unknown. We also make the following assumptions.
Assumption 1. Boundedness for scale-free regrets. For all i 1,..., N and (= = I,..., T, have | ||x(())22 < 1 and ||3|| S 1.
Assumption 2. Sub-Gaussian error. Let Hr := U.:1 [(X(()) U ) U.Y, (T) U
(t)) be the set of observed data at round t. For each and i, the error (t)) := x(())_x,(t)
3

---

is conditionally pero-mean
for fixed constant 0 2 0, i.e, E (t) H4] = 0 and [exp (An; (t)) H4] I exp()²o² /2), for all X F. Furthermore, the distribution of (t) does not depend on the choice at round I, i.e.
Assumption 3. Independently distributed contexts. The stacked contexts vectors (XI(I)) (X,(T)) E Rdd.v are independently distributed.
Assumption 4. Positive minimum eigenvalue of the average of covariance matrices. For each t,
there exists a constant o² > 0 such that Arnin (E. E x((1)x,(0)) 2 6².
Assumptions and 2 are standard in stochastic bandit literature Agrawal and Goyal 2013). We point out that given round t. Assumption allows that the contexts among difterent arms,
correlated each other. Assumption 3 is weaker than the assumption of IID, and the III condition is considered by Goldenshluger and Zeevi (013 and Bastani and Bayati| (2020). As Bastani and
Bayati (2020) points out, the IID assumption is reasonable in some practical settings, including clinical trials, where health outcomes of patients are independent of those of other patients. Both
Goldenshluger and Zeevi (2013) and Bastani and Bayati (2020) address the problem where the
(N(),, while our work admits different contexts over all arms, Assumption 4 guarantees that the average of covariance matrices of contexts over the arms is by the spectral norm. This assumption helps controlling the estimation error of in linear regression models, Similar assumptions are adopted in existing works in the bandit setting [Goldenshluger and Zeevi
contexts are equal across all arms, i.e. X()) = (i()
so that the inverse of the sample covariance matrix is bounded
2013
Amani et 2019 al. 2017 Bastani and Bayati 2020).
3.2 Doubly robust estimator
To describe the contextual bandit DR estimator, let (1) == TP (a, = il He) > 0 be the probability of selecting arm i round L. We define DR pseudo-reward as
{ (i = az) x,(1TT,, + T at) -(i=at) Ya, (t), (1(
Y (PP(()-
(1)
(1)
for some 3, depending on He. Background of missing data methods and derivation of the DR pseudo-reward is provided in the supplementary material. Now, we propose our new estimator 3 with regularization parameter A as below:
N Σ
t
t N ΣΣ X()
3r
x.))xx(()) + +AT
Harnessing the pseudo-rewards defined in (T. we can make use of all contexts rather than just selected contexts. The DR estimator by Kim and Paik (2019) utilizes all contexts but has a different form from ours. While and Paik [2019] uses Lasso estimator with pseudo-rewards aggregated over all arms, we use ridge regression estimator with pseudo-rewards in IT) which are defined separately for each i 1, ...... NN. This seemingly small but important difference forms paves way in rendering our unique regret decomposition and improving the regret bound.
3.3 Algorithm
In this subsection, we describe our proposed algorithm, DRTS which adapts DR technique to LinTS.
The DRTS is presented Algorithm [ Distinctive features of DRTS compared to LinTS include the novel estimator and the resampling technique. At each round t 2 1, the algorithm samples (t( from the distribution (( for each independently. Let (t) = Xt) B,t)) and m, : arg max, (t). We set m, as a candidate action and compute 7m, (t) == PO (1) =
max; (.()))))) ! If #m, > 7, then the arm m, is selected, i.e., a, = m.- Otherwise, the algorithm resamples (t) until it finds another arm satisfying (t) > up to predetermined fixed value M,. Section A.3 in supplementary materials describes issues related M, including a suitable choice of Mr.
'This computation is known to be challenging but employing the independence among A (1)...... (.))..,,.(())) (t). we derive explicit form approximating 7m. (t) in supplementary materials Section H.l.

---

Algorithm Doubly Robust Thompson Sampling for Linear Contextual Bandits (DRTS)
Input: Exploration parameter v > O, Regularization parameter À > 0, Selection probability threshold E 1 + 1).1, Imputation estimator 3u [r(X(r), Ya, (r))) Number of maximum possible resampling Mt.
Set Fo = 0. Wo = 0, 3. = 0 and Vo XI
for t 1 to T do
Observe contexts {X,
Sample 31 (1), (,) (t) from N( x2 7 independently, Compute Y:(1) x.(1)²B.(1)
Observe a candidate action my == arg max; Yt()).
Compute nm (1) = max; Vi(1)= Y,m, (t) H4)) for 1 = 1 to My do
if mm (t) 7 then
Sample another (t)..... BN (t). observe another m, and update Tm, (t).
else Break. end if end for Set a, m,, and play a,. Observe reward Ya, (t) and compute (tDR(t)
P. = P1- P E (,(O),R()); W. Wi-1 EE X((0)x1)) W.+ XIII
=
Update 3-11 for next round.
end for
The resampling step is incorporated to avoid small values of the probability of selection so that the pseudo-reward in (T numerically stable. naive remedy to stabilize the pseudo-reward is to use max(T;; (f), 7.. which fails to leading our regret bound since induces bias and also cannot guarantee that the selected arm is the super-unsaturated arms defined (5) with high probability (For details, see Section 4.2). The resampling step implemented in the proposed algorithm is designed to solve these problems.
Theoretical results
Our theoretical results are organized as follows. In Section we provide the main result, the cumulative regret bound of vVT of DRTS. The main thrust of deriving the regret bound is to define super-unsaturated arms. In Section 4.2 we introduce the definition of super-unsaturated arms and show how admits a novel decomposition of the regret into two additive terms as (6). In Section 4.3 we bound each term of the decomposed regret bounds (6). The first term is the estimation error, and Theorem 3 finds its bound. In the course of proving Theorem 3 we need Lemma [ which plays similar role to the self-normalized theorem Abbai- et al. [011]. We conclude the section by presenting Lemma and bound the second term of (6).
4.1 An improved regret bound
Theorem provides the regret bound of DRTS in terms of the minimum eigenvalue without d.
Theorem 1. Suppose that Assumptions 1-4 hold. If 3 in Algorithm satisfie J || -11 < b for constant b 0, for all I.... T. then with probability 1 26, the cumulative regret by time T for DRTS algorithm is bounded by
4Cb. 22
1272
2T2T OVN
R(T) 22+
Tlog
(3)
where Co,o is constant which depends only b and
5

---

The bound eigenvalue can be shown by
3 has a rate of V(T-
The relationship between the dimension d and the minimum
N
N R
dØ² N
Amin
E x,(1)x(00))
S
1 N
R
Tr (x((0)((0)) 1 N
1x,00 <
This implies Φ6 2 d. but there are many practical scenarios such that ø = (d) holds. Bastani et al. 2021 identifies such examples including the uniform distribution and truncated multivariate normal distributions. When the context has uniform distribution on the unit ball, Φ = d + 2. When the context has truncated multivariate normal distribution with mean and covariance Σ, we can set sー= (d + 2) exp( (Ay ). For more examples, we refer to Bastani et al. [2021]. Furthermore, regardless of distributions, x- (d) holds when the correlation structure has the row sum of off- diagonals independent of the dimension, for example, AR(1), tri-diagonal, block-diagonal matrices. In these scenarios, the regret bound in (3) becomes (dv Compared to the previous bound of LinTS [Agrawal and Goyal 2014 Abeille al. 2017 we obtain a better regret bound by the factor of Vd for identified practical cases.
As for the imputation estimator 3,, assume that ||, 3112 S b, where b is absolute constant. We suggest two cases which guarantee this assumption. First, a biased estimator is used, we can rescale the estimator so that its 1/2 -orm is bounded by some constant > Then, || 8112 S ||3:112 + ||:1|2 S C + and b = C + 1. Second, consistent estimators such as ridge estimator or the least squared estimator satisfy the condition since | }112 = Old /lo t/t). The term is cancelled out when 2 ta. where ta is the minimum integer that satisfies log t/t S d-2. In these two cases, we can find a constant which satisfies the assumption on the imputation estimator 3r.
4.2 Super-unsaturated arms and a novel regret decomposition
The key element in deriving 3 is to decompose the regret into two additive terms as in (6). To allow such decomposition be utilizable, we need to define novel of arms called super-unsaturated arms, which replaces the role of unsaturated arms in [Agrawal and Goyal 2014). The super- unsaturated arms are formulated that the chosen arm is included in this set with high probability. For each and f, let (t) Xa; (t)" 3 (t) T Define A, := Σi= Xa, (T) (r)*+ Al and V, : Ex EN arms by Agrawal and Goyal 2014
Di= (7))). + A.T. For the sake of contrast, recall the definition of unsaturated
U = i (t) s 9
Ix,(0)1) (X
(4)
where := CV (t//0) min V d, Vlog.V N} for some constant C. >> 0. This is constructed to ensure that there exists a positive lower bound for the probability that the selected arm unsaturated. In place of 4 we define set of anper-unsaturated arms for each round by
N i: (1) S A - $112 + 11xx 1X000)
(S)
While de [X,,())) in normalized with only selected contexts, the second term the right hand side of (5) is normalized with all contexts including Xx; (l), the contexts of the optimal arm. This bound of (t) plays erucial role in bounding the regret with a novel decomposition as
in (6) The following Lemma shows a lower bound of the probability that the candidate arm is super-unsaturated.
Lemma 2. For each t, let m arg max; Y,(t) and let Ne be the super-amssaturated arms defined in (5.. For any given y [1/(N + 1),1/N), set (o (N/(1 7//) Then,
P (mm+ E H.]
Lemma 2 directly contributes to the reduction of vd in the hyperparamter v. In Agrawal and Goyal 2014 to prove a lower bound of P (a, E Uel 74). it is required to set v = /9d (9dlog(t/5) with the
"Some previous works assume o = 0(1) even when (t)]2 < (e.g. Li al. 2017 D. As pointed out by Ding al. 2021), this assumption is unrealistic and the reported regret bound should be multiplied by O(d).

---

order of vd. In contrast, Lemma 2 shows that v does not need to depend on d due to the definition of super- unsaturated arms in ( In this way, we obtain lower bound of (m, N₁ H,) without costing extra vd.
Using the lower bound, we can show that the resampling scheme allows the algorithm to choose the super-unsse uuper-nsatuurted arms with high probability. For all Nt.
(4) = PP (m,- i| H.) S IP (UJÆN, {m = Ha) = (m, & No1 H.) S
where the last inequality holds due to Lemma that {i: 3z (t) > y subset of N₂ and
Thus, in turn, if x;(t) y, then i E N₁. This means
(a, {i #.(1) > *) c (ar N.).
Hence, the probability of the event {a, E NN) is greater than the probability of sampling any arm which satisfies (t) 7. Therefore, with resampling, the event far N₂} occurs with high probability. (See supplementary materials Section A for details.)
When the algorithm chooses the arm from the super-unsaturatedd set, i.e., when a, E N, happens, (5) implies
D., (t) S 2 B 1 8112 +
Xx:: (0) 11ll+V11xs
+ 1o, (OIR
By definition, De, (t) (t)r and the regret round be expressed the two additive terms, which presents stark contrast with multiplicative decomposition of the regret in AAgraaal and Goyal 2014]. In section 4.3 show how each term can be bounded with separate rate.
4.3
Bounds for the cumulative regret
We first bound the leading term of (6) and introduce a novel estimation error bound free of for the contextual bandit DR estimator.
Theorem 3. (A dimension-free estimation error bound for the contextual bandit DR estimator.) Suppose Assumptions 1-4 hold. For each = I....,T, let Bt be any Hl-measurable estimator satisfying || - Bl1 < b, for some constant b > O. For each i and assume that nT(1) > 0 and that there exists ? E [1/(N + 1/N) such that na (f) > 7.. Given any E (0,1), set
X = =442N Velog 12g2. Then with probability at least 1 - 6, the estimator Br in 22 satisfies
13. 1 S
Co.o
1212
log 5
82v7
for all ( 1= 1=,,...,2 where the constant Cs which depends only b and
In bandit literature, estimation error bounds typically include a term involving d which emerges from using the following Lemmas: (i) the self-normalized bound for vector-valued martingales [Abbasi- Yadkori et al. 2011 Theorem 1], and (ii) the concentration inequality for the covariance matrix Tropp 2015 Corollary 5.2]. Instead of using (i) and (ii). develop the two dimension -free bounds in Lemmas and 6 to replace (i) and (ii), respectively. With the two Lemmas, we eliminate the dependence on d and express the estimation error bound with @² alone.
Lemma 4. (A dimension free bound for vector-valued martingales.) Let (Fr) be filtration and {n(T))+= be real-valued stochastic process such that nTT) is F,-measurable. Let (X(T)), be an Ral-uel stochastic process where X(T) is --e--uuuuurablle and [|X S 1. Assume that in Assumption 2. Then with probability least 5/t?, there
(n(())t==
exists an absolute constant C > such that
4/2 8
Σ (())(())
S <Covi log
(8)
Compared to Theorem 1 of Abbasi- Yadkori et al. 20 our bound 8 does not involve d, yielding a dimension-free bound for vector-valuse martingales. However, the bound (8) has vi term which comes from using I|-l|2 instead of the self-normalized norm I1-Ily--

---

To complete the proof of Theorem we need the following condition,
Amia (V)) 2 ct,
for some constant e > 0. Li et al. 2017] points out that satisfying is challenging. To overcome this difficulty, Amani et al. [2019] and Bastani and Bayati| (020 use assumption the covariance matrix of contexts and a concentration inequality for matrix to prove ( described as follows.
Proposition 5. (Tropp 2015 Theorem 5.1.1] Let P(1)..... P(t) E Ruxd d be the symmetric matrices
such that Amiu (P(r)) 2 0, Amax (P(T)) S L. and Amin (B((()) 2 Φ², for all T 1,2,..... .
Then,
P Xmnin Σ P(T)
ΣP(T)
1 I
1d/2
S dexp
102
(10)
2
8L
To prove ( using 100 with probability least 1 - 6, for å E (0, 1), it requires t
84
log g
2
Thus, one can use 10 only after O( d) rounds. Due to this requirement, Bastani and Bayati implements the forced sampling techniques for O (NV2 d)²) rounds, and Amani et al. 2019 forces to select arms randomly for O ( d) rounds. These mandatory exploration
2020
phase empirically prevents the algorithm choosing the optimal arm. An alternative form of matrix Chernoff inequality for adapted sequences is Theorem 3 in Tropp [2011), but the bound also has multiplicative factor of d. Instead of applying Proposition S to prove (g) we utilize novel dimension- free concentration inequality stated in the following Lemma.
Lemma 6. (A dimension-free concentration bound for symmetric bounded matrices.) Let ||All be a Frobenious norm of a matrix A. Let {P(T)) E Raxd be the symmetric matrices adapted filtration {Fr)t= For each 1,...,t, suppose that [|P(T)] for some 0 and Amin (E) [((T)) 2 6² 0, almost surely. For given any 5 (0, set
X 4V2ovt log 412, Then with probability at least 1 1- 5/P,
Amin Σ
P(T) + X 2 12
(11)
Lemma 6 shows that setting A with v rate guarantees for all f 2 1. We incorporate À stated Lemma our estimator (2), and show in Section 5 that the DR estimator regularized with A outperforms estimators from other contextual bandit algorithms in early rounds.
We obtain the bounds free of d in Lemmas and 6 mainly by applying Lemma 2.3 in Lee al. (2016) which states that any Hilbert space martingale can be reduced to RR.. Thus, we can project the vector-valued (or the matrix) martingales
martinnggs,,ss, and reduce the dimension from d (or d2) to 2. Then we apply Azuma-Hoeffühe inequality just twice, instead of d times. In this way, Lemma 6 provides novel dimension- free bound for the covariance matrix.
Lemmas 4 and 6 can be applied to other works to improve the existing bounds. For example, using these Lemmas, the estimation eтrоr bound of Bastani and Bayati] [2200] can be improved by factor of log d. Proposition EC.1 of Bastani and Bayati (2020) provides an estimation error bound for the ordinary least square estimator by using Proposition 5 and bounding all values of coordinates. By applying Lemmas 4 [ one does not have to deal with each coordinate and eliminate dependence on d.
Using Lemma we can bound the second term of the regret in (6) as follows. For j = I,...,N
|x,(0lk S ||2(0012 / /|villl2 S Amin (V--1) 1/2 <
(12)
(ON((-1)
Finally, we ready to bound (tgret(t) in 16
Lemma 7, Suppose the assumptions in Theorem 7 hold. Then with probability at least
26,
2Crba
12t2
2
regret(t) < 8² /t
log
(13)
8
N(
for all t ..
8

---

Tmili Bock
5-32.4
-.0 Litts
BU'S
2750
Cunumber Sounde
r.Hurberoflcune
1: T.lomnerr Rounds
Tmith Axrt
No72
Lntt
d-
BU'S
200
15c
of 2/50
Libes 20053
1: of Roands
Figure 1: A Comparison of cumulative regrets and estimation errors of LinTS, BLTS and DRTS. Each line shows the averaged cumulative regrets (estimation errors, resp.) and the shaded area in the right two figures represents the standard deviations over 10 repeated experiments.
Proof. Since ag shown to super-unsaturated with high probability, we can use 6 to have rt)ret(t) S 211 B|12 + VIIXa; (t)l 4 + ||. (t)] (= for all t = ,,..., We see that
T.
the first term is bounded by Theorem 3 and the second term by (2). Note that to prove Theorem 1, Lemma Glis invoked, and the event (Il) of Lemma 6 a subset of that in (7). Therefore (13) holds
with probability at least 1 26 instead of 1 35. Details are given in supplementary materials.
Lemma 7 shows that the regret at round t does not exceed O 2-212) bound when a, E No. which guaranteed in our algorithm via resampling with high probability (See Section A.3 for details). This concludes the proof of Theorem
5 Simulation studies
In this section, we compare the performances of the three algorithms: (i) LinTS (Agrawal and Goyal 2013), (ii) BLTS [iimakopoulou et al., 2019, and (iii) the proposed DRTS. We use simulated data described as follows. The number of arms N is set to 10 or 20, and the dimension of contexts d is set 20 or 30. For each element of the contexts j 1.. .d. we generate [X1, (t), ... (N,(t)] from normal distribution N (pN, VN) with mean P10 = [-10,
-222, 8, 10 or 1i20 [-20, -18, ... -2, 2, ... 18, 20 and the covariance matrix Vv E NRNNN has VN (i, i) = 1 for every and x (i, kt) p for every * We set == 0.5 and truncate the sampled contexts satisfy [tX(())la < 1. To generate the stochastic rewards, we sample (t) independently from A( 1). Each element of | follows a uniform distribution, L1(-1//,1)))) 1/Vd).
All three algorithms have as input parameter which controls the variance of (t) BLTS and DRTS require positive threshold 7 which truncates the selection probability. We consider e e (0.001, 0.01, 0.1, 1] in all three algorithms, DRTS. Then we report the minimum regrets among combinations. The regularization parameter A, v7 in DRTS and A; required in DRTS, we use ridge regression with (Xa, (T), Ya, (7) for each round t. Other implementation details are in supplementary materials.
{0.01, 0.05, 0.1) for BLTS, and set 7 1/(N + 1)
in both LinTS and BLTS. To obtain an imputation estimator 3
Figure shows the average of the cumulative regrets and the estimation error || Bl| of the three algorithms based on 10 replications. The figures in the left columns show the average cumulative regret according to the number of rounds with the best set of hyperparameters for each algorithm. The total rounds are T 20000. The figures in the third columns show the average of the estimation error || - B1|2- In the early stage, the estimation errors of LinTS and BLTS increase rapidly, while that of DRTS is stable. The stability of the DR estimator follows possibly by using full contexts and

---

the regularization parameter X = Vt. This yields large margin of estimation error among LinTS, BLTS and DRTS, especially when the dimension is large.
Conclusion
In this paper; we propose novel algorithm for stochastic contextual linear bandits. Viewing the bandit problem as missing data problem, we use the DR technique to employ all contexts including those that are not chosen. With the definition of super-unsaturated arms, we show a regret bound which only depends on the minimum eigenvalue of the sample covariance matrices. This new bound has (dv/T) rate in many practical scenarios, which is improved by factor of v compared to the previous LinTS regret bounds. Simulation studies show that the proposed algorithm performs better than other LinTS algorithms in a large dimension.
Acknowledgements
This work is supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT, and by the Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) N0.2000-0-01336 Artificial Intelligence Graduate School Program(UNIST) and the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT, No.2021R RIGIA 10008000 1) (Gi-Soo Kim). Wonyoung Kim was also supported by Hyundai Chung Mong-kov goo foundation.
AAA.RRRR221111111100 1950) (Wonyoung Kim and Myunghee Cho Paik),
References
Yasin Yadkor, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
Mare Abeille, Alessandro Lazaric. al. Linear thompson sampling revisited. Electronic Journal of Statistics, 1(2):5165-5199) 2017.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs.. In International Conference Machine Learning, pages 127-135, 2013.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. 2014.
Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Linear stochastic bandits under safety constraints. In Advances in Neural Information Processing Systems, pages 9252-9262, 2019.
Kazuoki Azuma. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, Second Series, 19(3)357-3677, 1967.
Heejung Bang and James M Robins. Doubly robust estimation in missing data and causal inference models. Biometrics, (1()):962-97) 2005.
Hamsa Bastani and Mohsen Bayati. Online decision making with high-dimensional covariates. Operations Research, 68(1 (8(1)2276,294, 2020.
Hamsa Bastani, Mohsen Bayati, and Khashayar Khosravi. Mostly exploration-free algorithms for contextual bandits. Management Science, 329-11933, 2021.
Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. In J. Shawe- Taylor, R. Zemel, I.. Bartlett, Pereira, and K. Q. Weinberger, editors, Advances Neural Information Processing Systems 24, pages 2249-2257. Curran Associates, Inc., 2011.
Fan Chung and Linyuan Lu. Concentration inequalities and martingale inequalities: a survey. Internet Mathematics, 3(1):79-127, 2006.
10

---

Maria Dimakopoulou, Zhengyuan Zhou, Susan Athey, and Guido Imbens. Balanced linear contextual bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1445-3453, 2019.
Qin Ding, Cho-Jui Hsieh, and James Sharpnack. An efficient algorithm for generalized linear bandit: Online stochastic gradient descent and thompson sampling. In International Conference Artificial Intelligence and Statistics, pages 1585-1593, PMLR, 2021.
Alexander Goldenshluger and Assaf Zeevi. A linear response bandit problem. Stochastic Systems, (1):230-261, 2013.
Nima Hamidi and Mohsen Bayati. On worst-case regret of linear thompson sampling, 2020.
Gi-Soo Kim and Myunghee Cho Paik. Doubly-robust lasso bandit. In Advances in Neural Information Processing Systems, pages 5869-5879, 2019.
James Lee, Yuval Peres, and Charles K. Smart. A gaussian upper bound for martingale small-ball probabilities. Ann. Probab., (46))4184-4197 11 2016.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. Proceedings of the 34th International Conference on Machine Learning-Volume Volume 70, pages
JMLR. org, 2017.
James M. Robins, Andrea Rotnitzky, and Lue Ping Zhao. Estimation of regression coefficients when some regressors are not always observed. Journal of the American Statistical Association, 89(427): 846-866 866, 1994.
William R. Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3/4)225-229) 1933.
Joel A Tropp. User-friendly tail bounds for matrix martingales. Technical report, CALIFORNIA
INST OF TECH PASADENA, 2011.
Joel A Tropp. An introduction to matrix concentration inequalities. Foundations and Trends@ in Machine Learning, 8(1-2):1-230, 2015.
Roman Vershynin.
Highh-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Martin J. Wainwright. Figh-DDmensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.


Reviews:
[{"review_id": "gRfyLGDgQDo", "reviewer": "Reviewer_SUDA", "summary": "The paper proposes a new Thompson Sampling-based algorithm for the canonical N-armed T period contextual bandit problem that \nachieves an expected cumulative regret of $\\mathcal{O}\\left( \\phi^{-2}\\sqrt{T} \\right)$, where $\\phi^2$ is the min eigenvalue of the context covariance matrix. It is easily observed that $\\phi^{-2} \\geqslant d$, where $d$ is the dimension of the context space. However, the authors point out that $\\phi^{-2} = \\mathcal{O}(d)$, in fact, holds in many practical scenarios. In such cases, therefore, the $\\phi$-dependent scaling corresponds to an improvement upon the well-known $\\tilde{\\mathcal{O}}\\left( d^{3/2}\\sqrt{T}\\right)$ standard by a factor of $\\sqrt{d}$. The primary algorithmic innovation driving this result is the use of a \"doubly robust\" model for unobserved rewards, and a ridge estimator for the underlying $d$-dimensional (true) parameter vector, which facilitates a regret decomposition that is amenable to the aforementioned improvement in the upper bound. Numerical studies illustrate a significant performance improvement over standard well-known algorithms for the problem. The robust performance is plausibly due to a full utilization of the entire $N\\times d \\times T$ context stack, and use of the ridge estimator.", "questions": "", "limitations": "", "rating": 7, "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": "The paper is well-written overall with accessible proofs. A provable $\\sqrt{d}$-factor performance improvement in \"typical\" scenarios certainly makes it worthy of inclusion in the broader literature. Additionally, some of the technical development may be of independent interest in the analysis of related algorithms. Some broad remarks and typos are noted below:\n\n1. Under a similar eigenvalue positivity condition per arm, can the algorithm and results be adapted to the setting where each arm has a different $\\beta_i$? Or is it a non-trivial extension?\n\n2. Table 1: Entry for Arm 3 at t=1 should be $Y_{a_1}(1)$.\n\n3.  In Algorithm 1, inside the \"for $l=1$ to $M_t$ do\" loop, what if $\\tilde{\\pi}_{m_t}(t) \\leqslant \\gamma$ is always true? In this case, which arm $a_t$ is played after this loop has finished execution?\n\n4. Line 181 - Theorem 1: How does the result depend on inputs to Algorithm 1, in particular, $M_t$? An appropriate specification of $M_t$ seems critical to the achievability of sub-linear regret. It is unclear how this is being ensured. Where is $M_t$ specified? Since the result is projected as the primary contribution, these points need to be appropriately addressed.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper could benefit from a revision along the lines of the points raised above. I am willing to increase my score if these are (especially 4) adequately addressed. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "_yPoVoGeIf4", "reviewer": "Reviewer_gHQb", "summary": "The paper proposes a variant of Thompson Sampling for the linear contextual bandit problem. Using a doubly robust estimator for estimating the underlying parameter, the paper shows a regret bound of the order \\sqrt{T}/\\phi^2, where \\phi^2 is a lower bound of the minimum eigenvalue of the covariance matrix of contexts. In some special cases, this bound implies a bound of the order d\\sqrt{T}, which is an improvement of the current result.\n", "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": "1. This paper presents an interesting application of the doubly robust estimator in the online setting (Thompson Sampling). Especially, it uses a resampling technique to provide the propensity score with a lower bound, without bringing auxiliary bias (when compared with other methods, say, propensity score clipping). The resulting bound improves the current result in some special cases.\n\n2. How should one choose M_t when implementing the algorithm? How do the theoretical results and the empirical performance of the algorithm depend on the choice of M_t?\n\n3. In line 534, is Lemma 4 applied conditional on the event {all \\pi_{a_t} > \\gamma}? In that case, does the conditions required by Lemma 4 still hold (e.g. sub-gaussian)?\n\n3. Minor issue:\nIn Algorithm 1, when sampling another (\\tilde{\\beta}_1,...\\tilde{\\beta}_N) do we choose another m_t?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "HUryAfnMlZz", "reviewer": "Reviewer_Sp81", "summary": "This work studies the problem of contextual linear bandits following a combination of Thompson Sampling approach and Doubly Robust methods. It proposes an algorithm that improves the cumulative regret bound of existing LinTS algorithm by a factor of \\sqrt{d} through the new definition of super-unsaturated arms.for some specific examples where the contexts are independently distributed.", "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": "The paper is well-written and the problem formulation and the contributions are clearly stated. My first comment is on the definition of \\pi_i(t) which is crucial in computing Y_i^{DR}(t) and thus the algorithm implementation. The computation of \\pi_i(t) is not discussed until in appendix A.2. I would suggest that the authors bring up this remark sometime earlier in the main body or make a small comment on it when they first introduce \\pi_i(t) in line 144.\n\nQuestions:\n\n1. Just to make sure, \\tilde\\pi_i(t) is P(\\tilde Y_i(t)=\\amax_{j\\in[N]}\\tilde Y_j(t))?\n2. Could the authors comment on how they make sure that \\pi_i(t) is non-zero as it is necessary in the computation of Y_i^{DR}(t)?\n3. What part of the analysis does the following affect? If we consider that the action set is fixed at all rounds and replace the current definition of \\phi^2 with \\frac{1}{N}\\sum_{i=1}^N X_i X_i^T.\n4. Could the authors comment on the computation of imputation estimator and what the condition is to guarantee that \\| \\breve\\beta_t-\\beta\\|\\leq b for all t\\in[T]? Can we simply replace \\breve\\beta_t with LSE of \\beta, and b with O(\\sqrt{d \\log(T)})? In this case regret bound will become O(d^{3/2}\\sqrt{T}). Do the authors have a better choice for \\breve\\beta_t and b?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I believe this work does not have any potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "5ZMXzq-PWw", "reviewer": "Reviewer_Qbta", "summary": "This work proposes and analyzes a variant of the classical Thompson Sampling algorithm for linear contextual bandits (DRTS) which relies on a novel doubly robust estimator inspired from the missing data literature. They show a regret bound for their algorithm which depends on the context distribution and which, for a variety of different context distributions, improves on the state of the art for linear Thompson Sampling by a factor of \\sqrt{d}. This result partially resolves a long-standing open question on the worst-case performance of linear Thompson Sampling.", "questions": "", "limitations": "", "rating": 7, "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": "Thompson Sampling for the linear contextual bandit problem has been studied extensively. In the frequentist setting, the best known worst case upper bound for the classical linear Thompson Sampling algorithm (LinTS) scales as d^{3/2}\\sqrt{T}, a factor of d^{1/2} off of the minimax optimal rate. The extra \\sqrt{d} arises from inflating the covariance of the posterior by an extra factor of d to ensure sufficient exploration. It has been an open question whether this inflation factor of d can be removed for LinTS and the regret improved to d\\sqrt{T} (see chapter 36 of [1]).\n\nThis work proposes a variant of the LinTS algorithm which relies on a novel estimator inspired by the the missing data literature. The authors show that their algorithm does not require inflating the covariance of the posterior by a factor of d. As such, instead of incurring regret of d^{3/2}\\sqrt{T}, they show that they are able to obtain regret scaling as a function of the context distribution, which they show that, in many cases, yields a regret of d\\sqrt{T}. While this does not completely resolve the open question around LinTS, it takes a major step forward in illustrating how the context distribution can be leveraged to obtain tighter regret bounds.\n\n\nPros:\n- The improvement of the regret bound for Thompson Sampling to d\\sqrt{T} in some cases is a noteworthy contribution. Furthermore, the explicit dependence on the context distribution in the regret bound is interesting and, to my knowledge, novel in existing minimax results. As noted above, the improvements here partially answer an open question and are a major step forward in our understanding of Thompson Sampling for linear bandits. \n- The proposed estimator of \\beta is novel in the bandits literature, to my knowledge, and could potentially be used to improve dimension dependence in other linear bandit algorithms.\n- The dimension-free estimation error bound (Theorem 3) is a novel contribution itself and may be of independent interest. \n- Simulation results are also convincing as to the effectiveness of DRTS.\n\nCons:\n- While in some cases it is better, the regret bound could actually be worse than the existing d^{3/2} \\sqrt{T} regret bounds for LinTS. Is it possible to instead get regret of \\min{d^{3/2}, \\phi^{-2}}? For really applications of contextual linear bandits, the context distribution could be nearly anything (e.g. the feature vectors corresponding to a stream of users we have no control over) so without some sort of a worst-case guarantee, this regret bound could actually be quite bad. Can the \\phi be improved from being the worst-case lower bound on the minimum eigenvalue to, e.g., the average case lower bound on the minimum eigenvalue? \n- Alternatively, if one could show a lower bound that depended on \\phi when running a TS-like algorithm without inflating the covariance by a factor of d, this would also help in convincing the reader that the \\phi is fundamental and necessary.\n- More discussion and examples should be given on the value of \\phi obtained by various context distributions. While there is a short paragraph after Theorem 1 giving some discussion of \\phi, I would like to see more precise statements of the value of \\phi in the various settings mentioned. \n- \\check{\\beta} (the imputation estimator) is not specified in the main text. This should be defined. Furthermore, it should be clarified what the value of C_{b,\\sigma} is and what value of b is achievable  if \\| \\check{\\beta} - \\beta \\|_2 \\le b. From the appendix, it seems C_{b,\\sigma} = O(b), so it should be shown that b does not need to scale with d (naively one might imagine we would have b = \\Omega(\\sqrt{d})). \n- As stated, the algorithm cannot be run in a computationally efficient way, due to the computation of \\tilde{\\pi}_t. While an approximation to this is proposed in the appendix, it is not stated how using the approximate version affects the theoretical results. Furthermore, it is not stated how to compute \\pi_t (which is needed to compute Y^{DR}(t)). \n- It would be interesting to see an experimental comparison against the version of LinTS which does not have covariance inflated by a factor of d. While this version doesn’t have theoretical guarantees in the frequentist setting, it is known to often perform well empirically, and it would be interesting to see how it compares to DRTS.\n\nOverall, this work makes a non-trivial contribution to our understanding of Thompson Sampling in the linear contextual bandit setting, partially answering an open question, and, as such, I believe merits an accept, assuming the issues outlined above are resolved. \n\n[1] Lattimore, Tor, and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not discuss potential societal impact. However, the work is primarily theoretical so it is difficult to determine what negative societal impacts it may have. Limitations are discussed and addressed. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper combines Thompson Sampling and doubly robust estimators for the linear contextual bandits. We have had many discussions and comments. The authors successfully answered all the questions raised during the rebuttal.  All the reviewers agree that this is a nice paper with a solid contribution. 
Decision: Accept (Spotlight)