Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper focuses on offline learning for linear contextual bandits and provides a novel family of pessimistic learning rules that generalizes over the Bellman--consistent pessimism and lower confidence bound strategies. The statistical guarantees established here for this new family of learning rules are proven to be minimax optimal, as the authors also show a lower bound. Last is demonstrated the adaptive minimax optimality property of one of the new learning rules - the extension of the lower confidence bound strategy - with empirical experiments corroborating the theoretical findings.
strengths_and_weaknesses: Strengths:
- Presentation: the problem is well introduced and the main results are clearly presented
- Impact: this paper provides a minimax optimal solution to the problem of offline linear contextual bandits. This new family of learning rules generalizes well-known approaches.
- The paper is technically sound.
- The experiments seem to nicely support the theoretical findings

Weakness: No instance dependent results. It seems like the instance dependent literature for linear is growing (even for RL, see [1,2]) and it would have been to see a result of that form 

[1] Zanette, A., Kochenderfer, M. J., and Brunskill, E. Almost horizon-free structure-aware best policy identification with a generative model. 
[2] Wagenmaker, A., Simchowitz, M., and Jamieson, K. Beyond no regret: Instance-dependent pac reinforcement learning

questions: - Could this work be extended to RL?
- The definition of the policies of interest are only explicitly made in Equation (9), while they should be explicitly defined before Theorem 1.
- Could the confidence set in Equation (8) and Lemma 1 incorporate more instance-dependent terms in order to get tighter results?

limitations: The theoretical limitations are adequately addressed. The authors state that the potential negative societal impacts of their work is N/A due to its theoretical nature. It might still be valuable to mention what could go wrong if the suggested algorithms were actually deployed.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposed a new confidence set estimation approach for linear contextual bandits based on the pessimistic principal. The optimality gap is derived using the dual norm techniques. The authors are able to show that the l_p confidence set attains the optimal rate when p=infinity. Furthermore, the paper showed that using p=infinity also achieves the adaptive minimax optimality. Experiments on synthetic dataset demonstrate the confidence set derived in this paper is valid and using l_infinity norm indeed outperforms the other candidates.
strengths_and_weaknesses: Strengths:

(1). This paper provided a suite of methods for deriving valid confidence set in the linear contextual bandit scenario. Furthermore, the paper suggested that using l_p norm with p=infinity gives the best suboptimality guarantee. The theoretical results are interesting, which I believe will facilitate future research in offline linear contextual bandits.

(2). The pessimism principle is well-motivated in the beginning of the paper, and it is very clear why pessimism would work in the offline linear contextual bandit scenario through equation (7).

(3). The related works are thoroughly discussed. Two important prior works, the LCB and BCP, are special instantiations of the general confidence set derived in this paper. Therefore, this paper can be viewed as an extension of prior research to the broadest setting.

Weaknesses:

(1). I am a bit skeptical of the contribution of this paper. In particular, the paper basically unified the prior works on LCB and BCP and provided a generic approach for confidence set estimation. The paper also suggested that when p=infinity, the confidence set estimation and the error rate attains the optimum. However, again as the paper pointed out, LCB is an instantiation of the generic approach when p=infinity, thus is already optimal. Therefore, the contribution of this paper is mostly about a general framework to unify previous methods.
questions: (1) How to justify that the paper has significant contributions to the linear contextual bandit community?
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 family of offline pessimistic learning algorithms for linear contextual bandit based on $\ell_p (p\geq 1)$ confidence sets (called $\widehat{\pi}_p$). Among them, the algorithm based on $\ell_\infty$ confidence set (called $\widehat{\pi}_\infty$) has the smallest suboptimality gap. Furthermore, it also proves lower bounds for classes of linear contextual bandit problems indexed by $q\in[1, \infty]$ and shows that $\widehat{\pi}_\infty$ is minimax optimal for all classes of problems.
strengths_and_weaknesses: ### Strengths
The claim that $\widehat{\pi}_\infty$ is adaptively minimax optimal is appreciated and considered to be highly novel. Meanwhile, this paper also provides thorough discussion and comparison between $\widehat{\pi}_\infty$ and previous methods, showing non-trivial advantage of $\widehat{\pi}_\infty$. Furthermore, to support its claim, this paper also proposes a novel lower bound and complexity measure for linear contextual bandit problems.

The writing of the paper is also in a good logic flow.

### Weaknesses

Minor issues:
- It may be better to have a separate section for conclusion to summarize what has been discussed before.
- It may be better to give a sketch or core idea of the hard instance construction for proving the lower bounds.
questions: - It looks peculiar that the requirement for $\Lambda$ in lower bound becomes purely numeric when $p=\infty$. Is there any intuition for this?
limitations: Yes, the limitations are adequately discussed, especially the regime where the proposed lower bounds are applicable.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper studies batch (offline) learning in linear contextual bandits (with a realizability assumption that the expected reward of a context and an action is a linear function of their feature mapping given to the learner). 

They analyze a class of pessimistic learning rules indexed by different l_p norms. For each learning rule, the learning rule is to (1) build a confidence set of the true parameter under l_p norm; (2) pessimistically select the policy that maximizes a lower confidence bound on the expected reward constructed using the confidence set. 

They provide near-optimality analysis of the learning rules and show that the learning rule with l_{\infty} norm enjoys the best performance guarantee under their analysis. 

The show that each learning rule under a norm is minimax optimal under the specific norm, within a norm-constrained class of contextual bandit instances (instances that are "easy" to learn). 

They show that the learning rule under l_{\infty} nrom is minimax optimal under all norms, while the other learning rules are not. 



strengths_and_weaknesses: Strengths:

The paper is well-written and easy to follow. 

They provide instance-dependent and minimax optimality analysis of learning rules under different norms. 

The discussion about the connections to prior works is interesting. 

Weaknesses:

1. The proposed learning rules seem to have already been discussed in many existing offline RL literature, as also mentioned by the authors. The methodological contribution seems limited. 

2. It would be great if the authors discuss and compare with prior works on offline learning in contextual bandit literature (e.g. [1,2,3] and their follow-ups). 

3. The paper lacks empirical evaluation. And I doubt its real-world applicability. In particular, the theoretical analysis of the proposed learning rule relies heavily on a realizability assumption, which might not hold in most of the real-world problems. Also, the minimax optimality analysis is within some benign class of instances, which might not hold in real-world applications. It would be great if the paper shows some empirical evidence that the proposed learning is better compared with other rules and existing works [1,2,3]. 


Some minor issues:
why in eq (6) we use \min (instead of \inf) and in eq (7) we use \sup? 

[1] Dudík, Miroslav, John Langford, and Lihong Li. "Doubly robust policy evaluation and learning." ICML (2011)
[2] Bottou, Léon, et al. "Counterfactual Reasoning and Learning Systems: The Example of Computational Advertising." Journal of Machine Learning Research 14.11 (2013).
[3] Swaminathan, Adith, and Thorsten Joachims. "Counterfactual risk minimization: Learning from logged bandit feedback." International Conference on Machine Learning. PMLR, 2015.

questions: See weaknesses. 
limitations: I did not find limitations and potential negative societal impact.
review_title: null

Meta-review: metareview: The reviewers are in agreement that this paper provides a minimax optimal solution to the problem of offline linear contextual bandits. This new family of learning rules beat state of the art approaches and provide a unified view on existing approaches, such as Lower Confidence Bound and Bellman-Consistent Pessimism. The theoretical results are backed by reasonable numerical simulations. Accept. 
confidence: Certain
Decision: Accept