Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper characterizes the instance-dependent PAC sample complexity of contextual bandits based on a designed quantity. Matching upper and lower bounds are showed based on this quantity for both agnostic and contextual linear cases. In addition, the paper constructs an instance under which any minimax-optimal regret minimization algorithm suffers from sample complexity that scales quadratically with the optimal sample complexity. The paper further proposes an algorithm with near-optimal sample complexity that only needs a polynomial number of calls to an argmax oracle.
strengths_and_weaknesses: This paper presents a bag of theoretical results and I think they are sound. Maybe it is better to organize them in a more structured way, for example, having more sections instead of many subsections. In my opinion, Assumption 1 (access to offline data) is a strong assumption. Although it might be satisfied by some practical problems, it is a strong assumption in terms of deriving theoretical results. 

There are several relevant papers. [1] also studies pure exploration in contextual bandit, and the results therein probably need to be discussed and compared. [2] and references therein also show that regret minimization algorithms have undesirable sample complexity for pure exploration objective. Last but not least, I think the literature of policy learning (e.g., [3] and references therein) studies a similar problem.

[1] Aniket Anand Deshmukh, Srinagesh Sharma, James W. Cutler, Mark Moldwin, Clayton Scott, Simple Regret Minimization for Contextual Bandits

[2] Zixin Zhong, Wang Chi Cheung, and Vincent Y. F. Tan, On the Pareto Frontier of Regret Minimization and Best Arm Identification in Stochastic Bandits

[3] Ruohan Zhan, Zhimei Ren, Susan Athey, Zhengyuan Zhou, Policy Learning with Adaptively Collected Data


questions: 1. For the complexity quantity between lines 98-99, why \Pi is a subscript as well as in the bracket?

2. The lower bound in Theorem 2.2 has the complexity quantity \rho_{\Pi,0}, which could be infinite without further assumption, right? Similarly, the lower bound in Theorem 2.13 could be infinite?

3. The definition of \delta-PAC in the literature usually requires almost-surely finite stopping time, while in Definition 2.1 requires the expected stopping time is finite. Do the results still only hold for PAC definition with almost-surely finite stopping time?

4. I am not sure I understand the connection between line 73 and line 74. Could the author elaborate more on this?

5. The analysis of Algorithm 3 cannot be directly extended to the realizable linear setting, so what settings can the analysis be applied to?

6. I understand this is a theoretical paper, but I think it is better to discuss the practicability of the proposed algorithms?
limitations: The paper describes the limitations in the conclusion (btw, I think conclusion can be a single section, not just a paragraph). As discussed, one is the limited applicability of the analysis of Algorithm 3, and the other is that Assumption 1 is pretty strong.
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 analyzes the sample complexity of contextual bandit optimization in several setting.
- When the reward and the policy class are both linear, the sample complexity of $(\epsilon, \delta)$-optimal algorithm is upper and lower bounded. The lower bounds are for $\epsilon = 0$.
- Roughly similar analysis is given for when the policy class is linear but no assumption about the reward class has been made. In this case, it is assumed that an empirical distribution over the contexts is known. 
In doing so, the paper establishes how realizability reduces sample complexity. 

Authors further establish that min-max optimal algorithms can not be simultaneously instance optimal. By giving a lower bound on the sample complexity of an $\alpha$-minmax optimal algorithm.

Lastly, two algorithms that are nearly min-max instance optimal are introduced (without empirical evaluation).
strengths_and_weaknesses: Analyzing complexity of sequential learning through sample complexity is a promising area of research, in particular because it leads to design of classes of algorithms. Further, formalized performance of algorithms via instance-dependent bound rather than minmax (aka worst case) bounds is far more informative. This paper combines both and presents a thorough analysis in the two cases of linear and agnostic reward class. The lower bounds are useful for designing new algorithms, and the upper bounds are useful for evaluating existing algorithms. I find the problem of interest to be indeed relevant to community, and I hope that it inspires more work in this area. I am not actively aware of the current state of research on sample complexity in sequential setting. This being said, it seems to me that this paper makes a significant contribution to earlier result on best arm identification, and to other results on instance-dependant regret bounds. 

While minmax algorithms, e.g. the vanilla UCB method, are not sample optimal, they perform quite well in practice. I would be curious if the minmax sample optimality is reflected in practice. Perhaps this is something that the paper lacks, but of course, empirical evidence is not a necessity, just a nice addition. 

I think the presentation of the paper could be improved, so that it addresses a broader audience. Some terms that are not-so-well defined outside this field are commonly used. This can make it an unfriendly read to someone outside the immediate community.

I am not familiar enough with the literature to be able to verify the soundness of the results in limited time. Although simple sanity checks of the bounds all go through. 

questions: Questions: 

- Regarding $\rho_{\pi, \epsilon}$:
    - I don't understand why and how $p_c$ in Def 2.1 depends on $c$. Is this just notation redundancy (e.g. it should read $p_{\pi(c)}$) or am I missing something?
    - Can you give some intuition into equation (1)? In particular, where the terms arise from? Generally, since all the bounds are given in this term, I think it can use more attention and interpretation. 
    - Viewed as a measure of complexity, how does this quantity relate to other notions of complexity for sequential learning? (e.g. ED coefficient [Foster et al 2021], Eluder dimension, Information gain,  Sequential Rademacher complexity, etc)

- How does it (or respectively the bounds) compare to the sample complexity of best-arm identification? In particular the $\epsilon$ and $\delta$ dependency. How much harder is optimality for linear contextual bandits compared to best-arm identification in multi armed bandits?

Small errors:
- Line 20: $r(c_t, a_t)$ is the expectation of the reward. The "$r_t := r_t(c_t, a_t)$" part should be fixed.


Ref:
- Foster, Dylan J., et al. "The statistical complexity of interactive decision making." arXiv preprint arXiv:2112.13487 (2021).

limitations: Perhaps the fact that Assumption 1 is required for the agnostic setup should be mentioned earlier.
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 designs instance-optimal PAC algorithms for contextual bandits in both agonistic and linear realizable settings. This paper proves matching upper and lower instance-optimal bounds for any PAC algorithms. The proposed algorithm is oracle efficient and optimal up to logarithmic factors. Interestingly, this paper also proves that, on some instances, algorithms with minimax-optimal regret guarantees cannot be PAC instance-optimal.
strengths_and_weaknesses: Originality & Significance. While minimax optimal results are well-studied in contextual bandit settings, this paper proves a matching PAC instance-optimal upper bound and lower bound, which is much more desirable because the sample complexity of every PAC algorithm is at least $\rho_{\Pi,0}\log(1/\delta).$ In other words, the proposed algorithm outperforms (or at least matches) every other PAC algorithms (up to logarithmic factors). I believe the results of this paper are important and potentially have a large impact.

The analysis of Contextual-RAGE algorithm is novel and easy-to-follow. The use of the Catoni estimator is neat and simplifies the proof.

Quality. The results are sound and solid. This paper clearly states the strength and limitation in the conclusion.

Clarity. While the paper is well-written in general, some of the details could be further improved (see below). On a high level, it would be better to provide more intuition of Alg. 1 & 2. In particular, it’s unclear why the elimination is necessary without reading the full proof.


questions: Some high-level questions and comments:
- Intuitively, the instance-optimal bounds should be better than the minimax bounds. Are there examples of instances where $\rho_{\Pi,\epsilon}$ is strictly smaller than the minimax bound?
- The lower bound only considers the case when $\epsilon=0$, and thus mismatches the upper bound slightly ($\rho_{\Pi,0}$ vs. $\rho_{\Pi,\epsilon}$).  Is it possible to get a lower bound for $\epsilon>0$? Is it possible that $\rho_{\Pi,0}$ and $\rho_{\Pi,\epsilon}$ are significantly different?

Some details seem to be missing in the first 9 pages of this paper:
- In Definition 2.1, if I understand correctly, the PAC algorithm must find an \epsilon-optimal policy on *every* instance. It’s better to emphasize this because this is critical to prove the lower bound (Theorem 2.2).
- Both the lower and upper bounds require an additive Gaussian noise, which is never mentioned in the first 9 pages.
- In Definition 2.5, the distribution of context is missing.
- The Catoni estimator and its properties are not formally defined in this paper. 

Minor issues:
- In Theorem 2.6, the second max should be over $\mu’$
- Line 4 of Algorithm 1: the RHS should be $\epsilon_\ell^2$.
- In Appendix B, some of the notations are not defined. E.g., $w_\ell,\tau_\ell$.
- Line 585: the inline equation seems to be incomplete.

limitations: The authors adequately addressed the limitations and potential negative societal impact.
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 is concerned with instance-optimal PAC property for contextual bandits. Both agnostic and realizable cases are investigated. One advantage is that the algorithm is computationally efficient.
strengths_and_weaknesses: N/A
questions: After skimming through the paper, I found I'm not confident to review the paper as it is outside my expertise. I do not have bandwidth to read more about the literature and further evaluate the paper.

Maybe one related work is https://arxiv.org/pdf/2108.02717.pdf. Can you comment on the comparison to such work?
limitations: Nan
review_title: null

Meta-review: metareview: This paper considers the contextual bandit problem with general policies/function approximation. The authors focus on the PAC setting, where the goal is to identify an eps-optimal policy, and provide several new results regarding instance-dependent sample complexity:
- A new complexity measure, which is shown to capture the instance-optimal PAC sample complexity.
- A lower bound which shows that no algorithm can simultaneously achieve minimax optimal and instance-optimal PAC sample complexity.
- An oracle-efficient algorithm with sample complexity nearly matching the lower bound.

The reviewers agreed that the problem this paper studies is interesting and relevant to the bandit/decision making community, and has potential for large impact. All of the results in the paper are novel, and there are many interesting technical ideas. They also found the paper to be well-written, though there are some aspects that can be improved.

One reviewer took issue with the assumption that the algorithm has access to unlabeled data (assumption 1), but did not defend this position in the discussion period. Nevertheless, for the final revision, the authors are encouraged to expand the discussion and justification around this assumption. In addition, the authors are encouraged to incorporate the reviewers' suggestions to improve upon presentation.

confidence: Less certain
Decision: Accept