Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
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.

The 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.
1. 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.
2. Why $\pi$ is called (meta-)policy? To me, it is the whole model of $T$ periods.
3. 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?
4. 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.
5. 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?
6. 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?

Dylan J. Foster, Sham M. Kakade, Jian Qian, and Alexander Rakhlin, The Statistical Complexity of Interactive Decision Making, 2022



clarity,_quality,_novelty_and_reproducibility: This paper is a follow-up work to Zhang (2021). It is not hard to read the paper. Since the proposed algorithm is (almost) unimplementable, there is no any empirical result.
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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). 
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.

The 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.
clarity,_quality,_novelty_and_reproducibility: The paper is generally clear, the have made references to related work and the overall presentation of the work is good.
summary_of_the_review: Overall it is a good paper that gives a near-optimal algorithm for the lifelong learning setting.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strength:
1. The paper is generally easy to follow and well-organized.
2. The literature review is detailed.

Weaknesses:
1. 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?
2. Since Algorithm 1 is not computationally efficient and even hard to implement, what are the possible solutions? Any thoughts?
3. 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.
4. Small typo: page 6 --- before Definition 4.2: should be "we define the approach of $\epsilon$-net and covering number."
clarity,_quality,_novelty_and_reproducibility: This work does not include experiments, and I think the quality would be improved if the weaknesses mentioned above could be fixed.
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.


=========

After rebuttal:
Thanks for your efforts. I increased the score to 6.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes a framework that encompasses several variants of linear bandits based on feel-good Thompson sampling (Zhang, 2021). The proposed regret bounds have (near-)optimal performances for linear bandits. The analysis of this paper is commendable and unifies previous analyses. 

However, this paper is borderline and as the AC, I discussed it in detail with the three reviewers. There was a strong consensus that the paper has made important theoretical contributions to the bandit literature. However, all three reviewers felt that for the paper to be published in this or other conferences, it is paramount to conduct implementations and experiments for non-stationary linear bandits and compare the performance to existing algorithms. Without which, the practicality of FGTS.LP cannot be unequivocally ascertained. Release of code would further strengthen the paper and its potential impact. 
justification_for_why_not_higher_score: As above
justification_for_why_not_lower_score: Can't go lower.
Decision: Reject