Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

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.

2. 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?

3. 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)?

3. Minor issue:
In Algorithm 1, when sampling another (\tilde{\beta}_1,...\tilde{\beta}_N) do we choose another m_t?


limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

Questions:

1. Just to make sure, \tilde\pi_i(t) is P(\tilde Y_i(t)=\amax_{j\in[N]}\tilde Y_j(t))?
2. 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)?
3. 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.
4. 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?
limitations_and_societal_impact: I believe this work does not have any potential negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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]).

This 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.


Pros:
- 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. 
- 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.
- The dimension-free estimation error bound (Theorem 3) is a novel contribution itself and may be of independent interest. 
- Simulation results are also convincing as to the effectiveness of DRTS.

Cons:
- 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? 
- 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.
- 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. 
- \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})). 
- 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)). 
- 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.

Overall, 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. 

[1] Lattimore, Tor, and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
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_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a new Thompson Sampling-based algorithm for the canonical N-armed T period contextual bandit problem that 
achieves 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.
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:

1. 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?

2. Table 1: Entry for Arm 3 at t=1 should be $Y_{a_1}(1)$.

3.  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?

4. 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.


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_title: null

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)