Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose a novel algorithm for contextual bandits in the adversarial setting, where the loss functions belong to some parametric class. They show that their algorithm achieves the same "first order bound" (where the regret is upper bounded by a function of the loss of the optimal arm) as known algorithms, while being, in some cases, easier to implement. Overall the paper is well written although quite technical in some places. 
main_review: 1) The algorithm requires the value of the loss of the best arm as an input. How is one supposed to know this information in practice ? Knowing this information certainly is possible once all of the losses have been observed, but otherwise it seems difficult.

2) The authors discuss "computational efficiency" only by discussing how many times the prediction subroutine must be called. However, while this might be of theoretical interest (if for some reason one only wants to consider algorithms that are based on a prediction subroutine as described by the authors), what matters most is the actual amount of time and space required to implement the whole algorithm. A discussion of this and a comparison with existing algorithms would make the argument that the proposed algorithm is computationally faster more convincing.

3) The paper contains numerical experiments, which is very good. What is perhaps missing is the comparison of running times of different algorithms (since the main claim of the authors is the design of computationally efficient algorithms).

Minor Remarks:
- Isn't Assumption 2 always true providing that $Reg_{KL}(T)$ is chosen large enough ? Isn't this simply a definition ?
- In equation (3) what is $z_t$ ? And why is it that function $f$ now only takes one argument ? It was defined as a function of two arguments.
- the way that the algorithm is presented in the introduction makes it sound more complex than it actually is, and the algorithm operates as do all adversarial bandit algorithms: they predict the loss of each arm using some estimation procedure, and then draw a distribution where the probability to select an action is some simple decreasing function of the loss estimate.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This work is about contextual bandits in the low noise regime. It introduces the first efficient algorithm with a small loss bound. The latter is close to a previous algorithm SquareCB. However, the main idea is to use an online regression oracle working with a log-loss instead of a square loss. They also show that this change is fundamental as SquareCB can not achieve small loss bound. Some experiments have also been done.
main_review: The main contribution of paper is to have design the first efficient algorithm for contextual bandits with small loss bound under the realizability assumption. The algorithm relies on a regression oracle using the log-loss. The authors show that using the log-loss is key to achieve the small loss bound.

The paper is very well written. I particularly appreciate the effort to explain the main ideas that make the proof work.
Theorem and assumptions are well stated. The proofs are easy to follow. I have only checked the core of the proof of Theorem 1 which seems correct.

The results seems important both in theory and practice. Moreover, the theoretical tools used like triangular discrimination are promising to be used in future works.

To conclude, this work is clearly a good paper.

I have only few remarks :
- It may interesting to give real computational complexity for several cases. Indeed, the efficiency of the algorithm may relativized because some regression algorithms for log-loss are not so cheap e.g. exponential forecaster.
- In example 2 (p.23), the references given suggest that the log-loss with linear function could be seen as a portfolio selection problem. However, it is not completely clear to me that it is true. For example, the loss induced by d=2, \phi(x,a) = [1,0], y =1/2 does not seem to correspond to a portfolio selection loss.

Typos/omissions:
- l.113 definition of z_t ?
- l.216 oft = often ?
limitations_and_societal_impact: -
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Optimal first-order regret bound for contextual bandits.
main_review: This paper built on the recent SquareCB paper and derived an optimal first-order regret bound for contextual bandits. The main change of the algorithm is to use a cross-entropy loss instead of square loss. It's interesting that the authors claim that SquareCB can not achieve the optimal first-order bound which means cross-entropy loss improves a lot. I nearly have no complaint about this work since the contribution is clear and the new technique used is highlighted. Experiments are included which is appreciated for a theory paper. One minor point is that if it is possible to design experiments to verify your conjecture or argument about the sub-optimality of SquareCB in terms of the first-order regret. Or is there any way to design experiments to justify the first-order regret is a strong measure? 

======

I have read the response.
limitations_and_societal_impact: no
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors establish first-order regret guarantees for contextual bandits, that is, the $\sqrt{T}$ dependence on the horizon is replaced by the total loss incurred by the optimal policy. This requires the algorithm to adapt to "low noise".
The proposed algorithm, called FastCB, is a variant of SquareCB by Foster et al, which is based on a reduction to online regression. These kind of algorithms have two components: an online "regression oracle" that learns to predict rewards, and an allocation rule that selects actions based on these predictions. The main innovation w.r.t. SquareCB is replacing the loss of the regression oracle, from square to logarithmic. The allocation rule is also modified to exploit this change. The authors derive first-order regret bound for FastCB.
The change of loss is further motivated by analyzing the off-line cost-sensitive classification setting, which could be of independent interest. The authors show that a plug-in classifier optimizing the squared loss cannot achieve first-order guarantees in general, while the latter is possible by using the logarithmic loss. The argument is two steps: first the excess risk is bounded by the triangular discrimination between true and predicted loss. Then they show that, by minimizing the logarithmic loss, the algorithm also makes the triangular discrimination small. The authors conjecture that triangular discrimination could be a useful tool for studying plug-in classification and contextual bandits in general.
Extensive experiments show that FastCB improves over SquareCB. Ablation shows that the gain is mostly due to the change of loss.

main_review: Overall, this seems a solid contribution to the contextual bandit literature.
I checked the proofs and found no major problems.
The paper is also well written, clear, and well organized. The authors make a good job in communicating the key ideas and the logic behind the theoretical analysis.
Originality is limited, since the proposed algorithm is a variant of SquareCB. The main elements of novelty are in the theoretical methodology. The way triangular discrimination is used to derive upper bounds could indeed be a useful addition to the bandit theory tool set (however, see my issue below)
The results are nonetheless significant: in fact, this paper solves (a variant of) a COLT open problem by Agarwal et al.

My main issue/question is on the importance given to the triangular discrimination. Although it does appear in key theoretical passages, it is only to be bounded by other divergences. The key concept of Appendix B seems to be the Hellinger divergence, not the triangular discrimination (in Theorem 5 the triangular discrimination is even completely bypassed with a Hellinger bound).
In appendix C, the same happens with the KL divergence. The final algorithm has no trace of this concept, only implicitly making the triangular discrimination small.
What motivates the importance this paper assigns to the triangular discrimination, besides proof techinques? Does it have an intuitive meaning in the context of plug-in classification and contextual bandits? Can we gain something by using triangular discrimination in a more explicit way in algorithms?

Minor issues:
1. You should state up front that what you solve is a variant (albeit small) of the original COLT open problem
2. In the proof of Theorem 6, I think the key point is the following (lines 741-746): since the regressor is minimizing the log loss, and you are assuming realizability, the empirical log loss of the regressor is less or equal than that of the true function. This appears in the proof as $C_a(\widehat{f},D)\ge 0$. I think the logic behind this passage should be made more explicit since it's the point where you show that optimizing the log loss is important.
3. The appendix tends to be less organized, with ancillary results appearing suddenly in the main proofs, sometimes with in-place and sometimes with dislocated proofs. A better organization would make the proofs easier to follow.
4. Experiments: you should report the number of independent runs and the meaning of the confidence areas in the main paper too
5. I would mention that $A=|\mathcal{A}|$ at the beginning of Section 2
6. Using "regret" also for the offline setting is a bit confusing. "Excess risk" would be more clear. For the same reason, I would replace $L^\star$ with a different notation in Section 3.1
7. Line 273 "even for SquareCB": this is not very clear. Do you mean "without changing the allocation rule"?
8. Line 742: what is $y_i(a)$?
9. In the proof of Lemma 3, I think $\pi^\star$ should be $\pi$
limitations_and_societal_impact: As mentioned by the authors, the work is mostly theoretical, hence of little immediate impact.
review_title: null

Meta-review: The paper advances the state of the art in contextual bandits by proposing an interesting extension of the SquareCB algorithm of Foster and Rakhlin (ICML 2020), and showing that this method efficiently achieves optimal first-order regret guarantees under realistic conditions. This solves a COLT open problem.

The paper has received uniformly positive reviews, with the reviewers praising the solid theoretical contributions and the thorough experimental evaluation. I myself have found the contribution to be significant and the techniques to be highly original. Overall, I believe that this outstanding paper is likely to have a long-lasting impact in the contextual-bandit literature, and clearly it should be accepted for publication at NeurIPS 2021.
Decision: Accept (Oral)