Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper applies expected improvement to contextual bandits to balance exploration and exploitation. The authors proposed LinEL for linear rewards and NeuralEI for general rewards using neural network for approximation. Theoretical analysis claimed that compared with UCB based approaches, LinEL's regret bound reduces a factor of $\sqrt{\log(T)}$. Empirical results validated the effectiveness of LinEL and NeuralEI.

main_review: 
Expected improvement is a popular method to balance exploration and exploitation. While several works analyzed EI in Bayesian optimization and best-arm identification, this paper provides the first analysis of EI in contextual bandits, which I believe is the most significant contribution. The techniques to combine EI with contextual bandits are rather standard, but I do not think this concern is too serious since this topic is novel and important. Still, I would suggest the authors to include more discussions on the technical challenging in combining EI with contextual bandits (e.g., new tools compared with EI for best-arm identification).

Theoretical results, e.g., regret bounds of LinEL and NeuralEI and the claimed $\sqrt{\log(T)}$ regret improvement, are arguably the second contribution of the paper. However, the claim on regret improvement seems incorrect when I check the regret proof of LinEL in detail. I also found many typos / minor errors. The analysis of NeuralEI is analogous to LinEL so similar errors may also exist.

  1. The regret of LinEL should be $O(d\sqrt{T\ln(T)\ln(T^3)\ln(T/\delta)})$. This should be intuitive as when bounding the regret, $\sum_t s_{a(t),t}$ contributes $O(\sqrt{dT\ln(T)})$ following Lemma 3; when $\beta < 3$ we have $\sqrt{2\ln(RT^\beta)} \leq \sqrt{2\ln(RT^3)}$ and $v_t$ contributes another $O(\sqrt{d\ln(T/\delta)})$. Thus the claimed regret improvement does not exists (and it seems that the logarithmic term is worse than OFUL/LinUCB). Please correct me if I was wrong here.

  2. Lemma 10 is not rigorous. When bounding $\beta_t/v_t$, the second equality should be inequality using the fact that $\ln(t^3/\delta) \leq \ln(t^3/\delta^3)$ when $\delta \leq 1$; the third step (inequality) is also not rigorous. Without fixing the issues, $C'$ will depend on $\delta$.

  3. Missing the regularization term $\lambda$. Lemma 1 and Lemma 3 in their original paper used $I$ for initialization instead of $\lambda I$, which was ignored by the authors when applying the lemmas. The authors should revise the proof to reflect $\lambda$.

 Typos:

  - In proof of Lemma 5: "The second one comes from Eq(8)" -> comes from Eq(6); "fifth inequality holds" -> sixth inequality holds; 
  - In proof of Lemma 5: "The second equality holds due to the definition of .." is redundant.
  - Combining Lemma 5 and 6: redundant $(t)$ in the second step; missing a matching ']' in the last step
  - In proof of Theorem 3: missing $CC_0/t^{\beta}$ in the second step; summation should be $\sum_t$ instead of $\sum_i$.

========================
In the revised version the authors fixed the errors mentioned above. I am increasing my score to 5.

summary_of_the_review: Although the theoretical results are flawed, I think most of the errors should be fixable.  I am open to increasing my score if the authors could fix the problems and make the analysis rigorous. The topic of combining EI with contextual bandits is novel and could be interesting to many audiences, even without the claimed regret improvement.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper extends and modifies the expected improvement (EI) algorithm for contextual bandits. Specifically, LinEI and NeuralEI are proposed for the linear reward function and general reward function (under some assumptions), respectively. The paper claims that LinEI and NeuralEI achieve the state-of-the-art regret bounds and they work well on both synthetic functions and benchmark datasets.
main_review: Major comments:
1. There are some existing papers that provide regret bounds for EI-type algorithms, for example, [1] and [2]. I think citing and comparing with these papers is necessary.
2. LinEI and NeuralEI modify the original EI by using a threshold function, see Line 4 in Algorithm 1 or Algorithm 2. Basically, LinEI and NeuralEI only sample the arm with the largest EI value if and only if the largest EI value is larger than this threshold function; otherwise LinEI and NerualEI sample the arm with the largest posterior reward mean. Intuitively speaking, I think if the largest EI value is small, the arm with the largest EI value is (almost) the same as the arm with the largest posterior reward mean. Hence, I am wondering whether introducing this threshold function is necessary. Do regret bounds still hold without this modification? If not, can the authors elaborate more on the technical difficulties as well as how this modification solves the issues?
3. Inflating the posterior variance is somewhat necessary for randomized algorithms (e.g., Thompson sampling) in order to show the optimism. I am wondering whether inflating the posterior variance is necessary for deterministic algorithms LinEI and NeuralEI.
4. In my opinion, the uniform constant $C'$ in the proof of Lemma 10 depends on $\delta$ (for example, consider $t=1$). If so, the uniform constant $C$ also depends on $\delta$ and then the final regret bound could have worse dependence on $\delta$.
5. I am wondering where Lemma 3 is used in the proof.
6. Both $\ln$ and $\log$ are used in the paper. I think it is consistent to use only one of them. 

There are so many typos in this paper. For example,
1. In the second sentence of Section 2, it should be $x_{i,t}$. 
2. In the paragraph Performance Measure, the summation should from $t=1$ instead of $i=1$.
3. In the paragraph Prior and Posterior Distributions, there are three normal distribution. I think none of the variance expressions is correct.
4. In Equation (2), it should be $s_{i,t}$ instead of $s_i(t)$.
4. There are so many missing brackets in the supplement material.


[1] Nguyen, V., Gupta, S., Rana, S., Li, C., Venkatesh, S.. (2017). Regret for Expected Improvement over the Best-Observed Value and Stopping Condition.
[2] Ziyu Wang, Nando de Fretias. (2014). Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameters.

summary_of_the_review: As mentioned above, some important references are not cited. To show the technical novelty, detailed comparison with these references is needed. In addition, since the uniform constants in the proof do not have clear dependence on the important parameter $\delta$ and there are so many typos, it is a bit hard for me to evaluate the correctness and significance of the main results.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper introduces and studies the expected improvement (EI) technique as a way to balance exploration and exploitation for the contextual bandit problem. The authors propose two EI-based algorithms for linear bandits and for neural bandits for a general class of reward functions. The paper presents regret bounds for both methods and shows the experimental results to support their theoretical claims.
main_review: Strengths:
- The paper introduces and formalizes Expected Improvement as a new strategy for contextual bandits. The EI idea has been around in Bayesian optimization but has not been adapted to contextual bandits.
- The EI is adapted to show regret bounds in linear bandits and neural bandits, both resulting in sublinear regret bounds.
- The empirical experiments show that LinEI outperforms other baselines for linear bandits and NeuralEI outperforms all baselines under the non-linear reward functions the paper considers.

 Weaknesses:
- In addition to regret analysis in linear bandits for LinEI, the regret analysis for NeuralEI is rather straightforward using the existing NTK techniques used in Zhou et al., 2020; Zhang et al., 2021. I am not sure what the analysis of NeuralEI adds to the contribution given by LinEI.
- The claim on the neural version that "no assumption is made about the reward function other than it being bounded" isn't necessarily true. It needs to satisfy certain conditions besides boundedness. See the discussions in Zhang et al., 2021.
summary_of_the_review: For the reasons above, I am leaning towards weak acceptance.

========== Post-reponses =================
Thanks to the authors for the responses, I am staying with the current score.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors study regret analysis of the expected improvement (EI), a popular but theoretically understudied technique to handle the tradeoff between exploration and exploitation in bandits.  They propose two novel EI-based algorithms for this problem, one for linear payoff and for deep neural networks. With a linear reward function, we demonstrate that our algorithm achieves a near-optimal regret. In particular, our regret bound reduces a factor of \sqrt{log T} from UCB. They also present numerical studies using the proposed algorithm.
main_review: This paper shows an innovative algorithm using expectation improvement and the corresponding regret analysis.  It improves the upper bound from UCB by \sqrt{T}.   Although it is debatable whether the upper bound is improved from Thompson sampling since the proposed algorithm does not use any randomization, it has a better upper bound than Thompson sampling by \sqrt{dT}.   Using expected improvement for exploration tools seems to be a good idea.

The regret analysis is interesting and innovative.  

The authors may give a more intuitive explanation of how \sqrt{d} is shaved compared to Thompson sampling.  It seems like computing expected improvement instead of randomly drawing the estimator from the distribution, a new regret decomposition is possible, and thus \beta_t and v_t appear in an additive manner instead of multiplicative. 

Experiments seem to show the regret grows linearly.  Have you tried a larger T?


summary_of_the_review: This paper is well written and shows novel contextual bandit algorithms using expected improvement with new regret analysis.   This could be a nice contribution to the bandit community.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work proposes two Expected Improvement (EI)-based algorithms to solve the regret minimization problem for the linear and neural bandits. It provides regret analysis for both algorithms and also comparison to some existing algorithms.
main_review: Generally speaking, this work is well-organized and it is interesting in the sense that it is the first the analyze EI-based algorithms for RM in linear bandits. Besides, it shows that the theoretical and numerical performance of the two proposed algorithms.  My major comments are as follows:
1. The design of the algorithm and the analytical methods seem to be quite standard. Despite the existing discussions, it would be better if the author(s) can further highlight the difference between the proposed algorithm in Qin et al. (2017) and also the challenge to derive the bounds. For example, although the analysis of linEI is a bit different from that of linUCB and linTS, what is the key challenge considering the existing EI analysis for BAI?
2. The lower bound by Dani et al. (2008) should also be placed in Table 1. Moreover, I suggest to compare to the bounds in "The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits" (http://proceedings.mlr.press/v54/lattimore17a/lattimore17a.pdf).
3. Since the linear bandit setting is a generalization of the standard bandit setting, the authors can consider to also compare the linear algorithm to 'non-linear algorithms' in a standard setting. Both theoretical and numerical comparisons should be possible. 
4. The numerical experiments do not consider a traditional bandit problem. Although it is good to generalize the application of bandit algorithms, what is the numerical comparison in a standard bandit problem, e.g. those in Qin et al. (2017)?
summary_of_the_review: The paper is okay but the contribution to the study of bandit problems does not seem to be significant. I think it would be better if the authors can highlight their contributions pertaining to what I suggested above.


=======================
Thanks for response from the authors. I am increasing my score from 5 to 6.
review_title: null

Meta-review: Summary: The paper introduces and studies the expected improvement (EI) technique as a way to balance exploration and exploitation for the contextual bandit problem. The authors propose two EI-based algorithms for linear bandits and for neural bandits for a general class of reward functions. The paper presents regret bounds for both methods and shows the experimental results to support their theoretical claims.

Discussion: The reviewers have identified technical issues in the regret bound of LinEL which has been now corrected. Similarly, reviewers have had difficulty assessing the correctness of the paper due to typos and unclear exposition, and raise concerns regarding the amount of corrections that were necessary to reach the current stage. There is no consensus between the reviewers, and some would feel more comfortable if the paper could go through another round of review after major revision.
Reviewer UDHj points that after corrections, "the regret has an additional $O(\sqrt{\ln T})$ dependency compared with the regret of LinUCB and Thompson Sampling." and this should be discussed in the updated version.
Reviewer co1L suggests to compare to the bounds in "The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits". The authors responded that " To our knowledge, the analysis of the optimal asymptotic regret for contextual bandits as we consider (where the context may be controlled by an adversary) is still an open problem.". In fact, this is the topic of several recent works including:
* "Asymptotically Optimal Information-Directed Sampling" COLT 2021
* "An asymptotically optimal primal-dual incremental algorithm for contextual linear bandits", NeurIPS 2021

The connections of the present work with these two references are strong and should be discussed in more depth. I believe it is a more important discussion than the comparison with the regret bound of LinTS which is yet another problem.  

The reviewers have appreciated the originality of the ideas and for that reason we encourage the authors to revise their draft and submit to a future venue.

Recommendation: Reject.
Decision: Reject