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: The paper shows how to extend the widely-used expected improvement heuristic from into the contextual bandits setting to create a new basic type of contextual bandit algorithm. They propose two novel algorithms, and propose a method for choosing an improvement threshold for controlling the exploration/exploitation cutoff which provably achieves an $\tilde O(\sqrt{T})$ regret rate, even in settings with adaptive adversaries. The paper then shows that the proposed methods have strong empirical performance.
strengths_and_weaknesses: Strengths:
1) Paper extends the expected improvement heuristic into contextual bandits, building a connection with the best arm identification and bayesian optimization literature, providing a novel and significant result.
2) Paper provides proofs for the results, and is able to get competitive regret rates for linear contextual bandits and neural bandits.
3) Paper shows experimental evidence for the value of the method.
4) Paper is clearly written, and contextualizes expected improvement in the broader literature, and clearly shows how the analysis of the linear and neural cases differ.

Weaknesses:
1) (minor) I wish the paper explained a bit more how the algorithms are able to work even with an adaptive adversary.

questions: 1) Are $\Phi$ and $\phi$ supposed to be the cdf and pdf of the normal distribution? They seem to be introduced on line 143 without that being explicitly stated.
limitations: The paper discusses the limitations of using a Gaussian distribution for the reward model, as well the fact that their usage of the NTK kernel restricts the neural network classes that they can use.

The paper does not address potential negative societal impact of this work.
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 authors propose a novel contextual bandit algorithm based on the expected improvement (EI) and study the corresponding regret analysis.  The proposed algorithm contains a modified element from EI for MAB by suggesting a hybrid of EI with pure exploitation. The paper adds different insights to the body of literature in that EI is an understudied technique to handle the tradeoff between exploration and exploitation in contextual bandits. They propose two novel EI-based algorithms for this problem, one for linear payoff and deep neural networks.  The authors provide numerical experiments.
strengths_and_weaknesses: Strength:

The paper adds different insights to the body of literature in that EI is an understudied technique to handle the tradeoff between exploration and exploitation in contextual bandits. 

EI can be viewed as a variation of TS, and in that respect, the proposed algorithm improves the upper bound of TS by \sqrt{d}.

Weakness:

Explanations for modifying EI by mixing with pure exploitation are not convincing.  
 
Why should one use the proposed algorithm over LinUCB since it carries extra \sqrt{log T}?


questions:  Explanations for modifying EI by mixing with pure exploitation is not convincing.  If the EI value is small, that means the posterior variance is small, which will pick greedily anyway.  Is it necessary?  Also, what is the regret upper bound without the modification? 

Do authors have experiments comparing TS and LinEI in terms of d?  
limitations: yes
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 applies the expected improvement (EI) principle to contextual bandits, which contrasts with the more popular approaches of upper-confidence bound (UCB) and Thompson sampling (TS).  For adversarially chosen contexts but realizable (conditional) mean rewards, EI is practically applicable with both linear and neural network predictors.  In the linear case the proposed technique essentially achieves information-theoretic lower bounds given sub-Gaussian residuals.  In the neural case the network tangent kernel can be used to characterize the regret matching analogous results for NeuralUCB and NeuralTS.
strengths_and_weaknesses: Strengths include the novelty of EI in this setting and the connection to NTK theory.

Weaknesses:
  * the lack of clear motivation for EI.  
    * is it just "another way to do contextual bandits that nobody has done yet?"
      * if so this paper is likely to be ignored by practitioners.
    * is it statistically distinct from UCB/TS approaches (i.e., works better)?
      * in theory no, everybody is achieving the same regret bounds essentially.
      * in practice, maybe, but that's where the experiments are too limited for a strong conclusion.
      * one advantage of using older datasets is you can provide exhaustive comparative study as in https://arxiv.org/abs/1802.04064 
    * is it computationally distinct from UCB/TS approaches (i.e., cheaper to compute or scales better to larger action sets)?
      * if so you could exhibit on a modern dataset such as amazon-3m from https://arxiv.org/abs/2102.07800

I believe this work would benefit from spending more time better differentiating EI before presenting to the general community, otherwise, it's potential impact will be limited.
questions: For clarity state that $\xi_{a(t),t}$ is mean zero in line 71 (in some works, mean zero is an optional part of the definition of sub-gaussian).  For example, "... where $h$ is an unknown mean reward function ...".

I would appreciate some commentary around equation (1) and associated experiments in section 6.1.  For example, compared to equation (1), LinUCB will find the most optimistic value for an arm in an ellipsoid defined by a level set of the posterior, rather than integrating over it.  Thus, relative to LinUCB, LinEI could choose an arm whose maximum optimistic value is lower but for which there are "more possibilities" for improvement.  Try to provide similar comparative insight with LinTS.  

theorem 3.2 and theorem 4.2 have typesetting issues.

The following combination of statements is confusing:
  * line 72: ... conditionally R sub-gaussian for some R >= 0 ... 
  * line 230: We note that although our algorithm is a Bayesian approach, our regret bounds will hold irrespective of whether or not the actual reward distribution matches the Gaussian likelihood function ...
  * line 312: For example, we can extend our work to non-Gaussian distributions to model the unknown reward model parameters and derive regret bounds as long as concentration inequalities can be established.
    * I suspect what you want to say is: "we've modeled the conditional reward residuals as sub-gaussian; our regret bounds hold for all sub-gaussian residuals; and we want to extend our work to more general residuals such as sub-exponential or sub-gamma."  But to be honest, it's a bit unclear.  If my guess is correct, the issue is arguably marginal because: bounded rewards are guaranteed to have sub-gaussian residuals (hence your result is already broadly applicable), and you are already close to the information-theoretic lower bound in Theorem 3.2 (hence you have already squeezed most of the efficiency out of the approach).

limitations: This reviewer is satisfied.

**Update after author discussion period**:  Authors have addressed concerns, raising score.
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 expected improvement (EI) is a classic approach to select the action in Bayesian optimization (BO). This paper extends EI to the contextual bandit setting, including the linear setting and non-linear setting. Based on the fact, the analysis of EI is not well studied, this paper provides the regret analysis of EI in linear contextual bandit and neural contextual bandit. Moreover, authors show good empirical results proposed algorithm.

enecccdejhvddktidjggvrltrghcivbtjdnlekdkejtc

strengths_and_weaknesses: 

Weakness:

(1) The overall proposed two algorithms, LinEI and NeuralEI,  look very similar to TS to me. Take the linEI as an example. In a round, $r_t^+$ is the same for every arm. So the selection criterion can be considered as $E_{\mu \sim N}x^\top \mu $, which is the expected version of LinTS. Just add the expectation to the TS. Theoretically, we only need to take the expectation over the normal distribution based on TS. So, I doubt the novelty of the proposed algorithms and their analysis.
questions: (1) LinEI and NeuralEI, look like the expected version of TS, adding expectation over the sampled reward. Please author convince me of the significant difference from TS. 

(2) Please provide more details about the challenges in the analysis of LinEI and NeuralEI over LinTS and NeuralTS.


limitations: .
review_title: null

Meta-review: metareview: This paper proposes and analyzes algorithms based on expected improvement for the contextual bandit setting, and proves that the resulting algorithm can attain $O(d \sqrt{T})$ regret in the linear bandit setting (the result improves over Linear TS). 

All the reviewers agree that the modified LinEI algorithm and its analysis are novel and important to the community. I agree with the reviewers, and recommend accepting the paper. For the final version of the paper,  it would be helpful to add more details on why the pure EI strategy does not work and add the scaling with $d$ experiments to the main paper (the response to Rev. rpMu). If there is space, it would also be helpful to add a proof sketch for the LinEI algorithm and distinguish it from the LinTS analysis which is more standard and known in the community (response to Rev. KPAe).  
confidence: Certain
Decision: Accept