Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies representation learning for stochastic contextual linear bandit problems. This is done by combining a novel constrained optimization problem to learn a realizable representation with a generalized likelihood ratio test to exploit the structural information. The authors propose BANDITSRL algorithm which could be paired with any no-regret algorithm and achieve constant regret.

strengths_and_weaknesses: Pros: This paper focuses on a very important question and it explores the structural information contained in the learning problem. It can be viewed as a combination of model-based and model-free learning, which is practically promising and theoretically plausible.

Cons: It is not clear how exploration plays a role here and how it could be improved by the  BANDITSRL algorithm. The benefit of finding realizable representations is that representations with certain spectral properties may be more effective for the exploration-exploitation trade-off. In particular, [1] showed that when the regularity condition (Assumption 2 in this paper) is satisfied, the greedy algorithm (with no exploration) is optimal for the linear contextual bandit problem since the feature itself has certain exploratory properties. I am wondering why this does not hold for the feature-based linear contextual bandit.

In addition, this representation formulation seems to be closely related to the sparse linear contextual bandits problem by replacing the linear contexts with feature contexts. The authors are encouraged to explore the connections and differences.

[1] Ren, Zhimei, and Zhengyuan Zhou. "Dynamic batch learning in high-dimensional sparse linear contextual bandits." arXiv preprint arXiv:2008.11918 (2020).


==========
I have read the reviews from other reviewers and the responses from the authors. The authors have addressed my concerns and I am happy to keep my recommendation to "accept" this submission!
questions: See above.
limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a new algorithm BanditSRL, that can select the realizable HLS representations from a family of representations for linear contextual bandit learning. The new algorithm is a framework that can apply to any constant-regret base algorithms like LinearUCB. Theoretical analysis show that the algorithm can indeed achieve constant regret when an HLS representation is present and sub-linear regret when only realizable representations are available. The algorithm is also extended to a more practical version that utilizes deep neural networks as the representation family. Experiments show the algorithms are efficient and can achieve small regret.
strengths_and_weaknesses: Strength:
+ This paper proposes a new solution to representation learning for linear contextual bandit. Compared with previous work, the new algorithm has a very clean structure and can utilize any base linear bandit algorithm. I believe the algorithmic design and the theoretical analysis are quite original.
+ The paper is written in high quality. It is clearly written and easy to follow. Potential concerns are discussed and addressed.
+ The improvement compared with Papini et al. can be significant in that the algorithm goes beyond just LinUCB and the NN-based variant can be practical. 
questions: At Line 204, Equation (2), what exactly does the Lagrangian relaxation refer to? Here the equality sign is drawn but I cannot easily see why the equality can hold. Could you explain in detail how this is derived? Or is this an approximation.
limitations: There are no foreseeable negative societal impact.

I think the authors should also compare the regret bounds in detail with LEADER in terms of all the variables. While the proposed algorithm BanditSRL surely is more general than LEADER, potentially the regret bound dependence can be worse due to a more complicated analysis.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper provides better algorithms to learn the good representation from a set of realizable representation in contextual bandits. The algorithm is interesting and enjoys provable guarantees. Experiments are also conducted to justify the performance. 
strengths_and_weaknesses: This paper is well-written and well-organized. The algorithm is interesting and can be generalized with neural net function approximation. I appreciate the author could carefully compare with prior LEADER algorithms. 

I only have some questions for the experiments part, especially  for the Non-Linear Benchmarks. For those datasets statlog, magic, covertype, it looks like the best proposed algorithm can achieve constant regret easily. This is a huge improvement over the class of TS reported in "DEEP BAYESIAN BANDITS SHOWDOWN". Can you comment why this could happen and do you make a fair comparsion? I can understand approximate TS does not do representation learning but is your result suggesting HLS is satisfied in those dataset? Do you cherry-pick those dataset? I feel this is important to understand how frequently HLS conditions can be satisfied in real world problems.  

questions: 1. HLS condition is never cited. I think that is from the last name of the authors of "Adaptive exploration in linear contextual bandit" and should be acknowledged.  
limitations: I feel in experiments the authors could try to discuss some failure cases and when people should be cautious to use this algorithm.
review_title: null

Meta-review: metareview: All reviewers are in agreement that this paper provides better algorithms to learn good representation from a set of realizable representation in contextual linear bandits. The proposed algorithm is deemed to be novel and general. Accept. 

In the final version, please release the code for reproducibility. The authors are encouraged to include the detailed comparison with LEADER in the rebuttal.
confidence: Certain
Decision: Accept