Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a neural network based contextual bandit algorithm in the offline setting where a dataset of contexts and rewards are given by a logging policy. The goal of the proposed algorithm is to learn an optimal policy from the offline dataset. The proposed algorithm NeuralLCB is similarly structured as the NeuralUCB algorithm (Zhou et a., 2019) in the online setting. The difference is that it uses a lower confidence bound for estimating the reward function instead of an upper confidence bound, and that the optimization procedure for learning the neural network representation is based on the loss on one data point instead of the whole historical data. The authors established an upper bound of the optimal gap of the learned policy and evaluated the algorithm on both simulation and UCI datasets. 

main_review: Some references are repeated in the bibgraph. For example, there are multiple entries for the same papers (Is pessimism provably efficient for offline rl, Gradient descent provably optimizes over-parameterized neural networks, Neural contextual bandits with ucb-based exploration). In the related work, there is another recent paper that studies policy learning in contextual bandit using the same neural network structure as in this paper (Xu, P., Wen, Z., Zhao, H., & Gu, Q. (2020). Neural contextual bandits with deep representation and shallow exploration. arXiv preprint arXiv:2012.01780.). Similar to the claim of the current work, this paper also improves the computational complexity of neural contextual bandits to a large extent. 

In Line 4 of Algorithm 1, are you retrieving the data tuple randomly, sample without replacement, or just in a fixed order? The notation of x_t and x^{(i)}

In the introduction, the authors stated that “actions in the offline data are independent and depend only on the current state” in Rashidinejad et al. (2021). However, it should be also clearly stated that the current paper did not resolve this problem since by Assumption 4.2 we know that the authors in this paper still need the actions to be independent from each other. 

Under Assumption 4.2, the authors claimed that the data coverage condition is only imposed on the observed feature contexts. However, a significant difference in the setting of this paper from others that rely on uniform coverage is that the total number of arm contexts are fixed as nK (shown in Assumption 4.1), while other papers such as Nguyen-Tang et al., (2021) do not require this condition. Is this the crucial reason for the relaxation of the condition?

In Theorem 1, it is claimed that the network width m is a polynomial in the number of data n. But it is unclear to me what the exact dependence of m on the number of data n is. In addition, did you also validate the dependency in the experiment settings (m=100, T=15000)?


=========after the authors' response========         
I am satisfied with the responses to my questions. I agree that this paper makes good progress in connecting neural contextual bandits and offline settings. I am willing to increase my score for this paper.
summary_of_the_review: My recommendation is mainly based on the theoretical novelty and the applicability of the theory.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper is the first study considers offline policy learning for contextual bandits with neural networks. The authors proposed NeuraLCB algorithm that used neural network to model the rewards and followed pessimism principle with lower confidence bound in policy learning. It is a very intuitive combination. The algorithm works with mild assumptions with theoretical guarantee on its suboptimality. Experiments also showed that NeuraLCB outperforms other baselines.
main_review: Strength

- Comparing with existing works, NeuraLCB requires weaker assumptions on data coverage (empirical single-policy concentration condition) and data generation (data can be dependent on history / past data) and I think this is a major contribution of the paper. The weaker assumption makes the algorithm applicable to more practical settings.

- Theoretical analysis on sub-optimality learned by NeuraLCB is provided. The algorithm essentially works in an online fashion that trained on one data point at each iteration. Thus several intermediate results can be directly applied from or very similar to online regret minimization in neural bandits (e.g., NeuralUCB, Zhou et al., 2019). If my understanding is correct, due to the different goal between online and offline policy learning (instead of improved technical lemmas over Zhou et al., 2019), the design of NeuraLCB is very different from NeuralUCB, e.g., single data point SGD verse full gradient descent at every iteration.

I checked the main theorem and several lemmas; they look sound and I only found a few mistakes (see below).

Weakness

- Mistakes in proof of Lemma B.5:
  - $\log \det$ function is concave instead of convex.
  - When bounding the difference of the $\log \det$ functions, the first inequality does not hold. Because log det function is concave, by taylor expansion we have that $\log \det(X) - \log \det(Y) \leq <Y^{-1}, X-Y>_F$. But the inequality does not hold when taking the absolute value of both sides, which is the case in current proof. This problem should be fixable and Lemma B.5 should still hold.

- In experiments the authors mentioned a B-mode variant of NeuraLCB (and NeuralGreedy) that update with a small batch of data points at each iteration. The result is reported after grid search over B-mode and S-mode (one step SGD on single data point). I would suggest the authors to report the performance of S-mode and B-mode separately. In experiment on the real-world datasets, the authors observed that S-mode performed better than B-mode (again, both results should be plotted). That's an interesting observation. It would be helpful to provide some explanations over this observation.

Other comments

- Besides the theoretical convenience of learning in an online manner, are there any other reasons to prevent full gradient descent training? It sounds very natural for offline learning. 

- The authors mentioned after Assumption 4.2 that NeuraLCB works with depend data: 'the offline data was collected by an active learner such as a Q-learning agent'. Currently the synthetic experiment is on independent data. It would be interesting to see if NeuraLCB could work well with depend data, e.g., use some bandit algorithms to collect the dataset. 



summary_of_the_review: Overall I think this is a good paper with a straightforward idea of combining pessimism and neural bandits for offline policy learning. I am open to revise my rating if the authors could address the concerns.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies the problem of offline contextual bandits, where policy learning can only leverage a fixed dataset collected a priori by behavior policies. Using a pessimism principle, the authors propose a new algorithm called NeuralLCB with overparameterized neural networks and provide theoretical regret guarantees based on the analysis framework of the neural tangent kernel. Experiments on both synthetic and real-world data are conducted, which confirms the theoretical results.
main_review: Pros:

a) The paper provides concrete theoretical analysis to support the proposed algorithm. I have not gone through all the derivations, but the overall result looks good.

b) Comprehensive comparisons with other related works are properly presented.

c) The paper is generally well written. The required assumptions are discussed clearly.

Cons:

a) Apart from theoretical analysis, it would be better if the paper could throw some light on algorithm design consideration beyond LCB-like algorithm.

b) It is not very clear how the improvement of \sqrt{d} and O(n) is achieved. It would be better to give more concrete discussions.

summary_of_the_review: Overall the paper studies a new problem and presents a good analysis. Since the technique is quite similar to existing works, it would be much better to present necessary discussions to claim their contributions.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: ~~~~~~~~~~~~~~
Thank the authors for the clarification. Some of my former comments were nicely addressed and hence I am willing to increase my rating to 6.

~~~~~~~~~~~~~~
This paper considers the offline setting of the contextual bandit with neural network function approximation. The key idea of the proposed NeuraLCB is to use neural network to learn the reward function and use a pessimism principle via a lower confidence bound (LCB) for decision making. In theory, the proposed approach is shown to learn the optimal policy with an error bound $O(\kappa \tilde{d}^{1/2} n^{-1/2})$ where $\kappa$ measures the distributional shift and $\tilde{d}$ is an effective dimension of the neural network. The empirical effectiveness of the proposed method is shown in a range of synthetic and real-world off-policy learning problems.


main_review: Pros: 

1. The pessimism principle (Kidambi et al., 2020; Buckman et al., 2020; Jin et al., 2020) is a recent idea introduced in off-policy learning to avoid the strong assumption of sufficient coverage of the data. The key idea is to consider a regularization version, i.e. lower confidence bound (LCB). After its introduction, it has been applied in various off-policy RL and off-policy bandit settings. This paper further advances this area by introducing this idea into the neural contextual bandit setting. 


2. This paper is very well written and is easy to follow.


Cons: 

1. Related to my previous comments on the pessimism principle, the main contribution of this paper is to incorporate the pessimism principle neural contextual bandit setting. It combines the strength of both Rashidinejad et al. (2021) and Zhou et al. (2020), where the former studies the lower confidence bound (pessimism principle) for decision-making in tabular MDP and contextual bandit, and the latter studies neural contextual bandit with upper confidence bound in typical online setting. Therefore, the technical advantages over these existing work are expected and routine. 

2. In Algorithm 1, why to randomly sample policy uniformly from $\hat{\pi}_1, \ldots, \hat{\pi}_n$? 

3. In Theorem 4.1, the error bound $O(\kappa \tilde{d}^{1/2} n^{-1/2})$, $\kappa$ measures the distributional shift and $\tilde{d}$ is an effective dimension of the neural network. 

(1) The Assumption 4.2 requires $\kappa$ to be a uniform upper bound over all sample size $n$ and all samples $x_t$. $\kappa$ would be a function of the dimension and the sample size. In this case, the error bound might diverge. It would be more convincing if the authors could provide some justifications or examples when $\kappa$ would be small.

(2) Similarly, the effective dimension of the neural network $\tilde{d}$ might be very large. This effective dimension of the neural network was used for online neural contextual bandit (Zhou et al., 2019) and neural MDP (Yang et al., 2020). The authors commented that $\tilde{d}$ in these references were typically small, in the order of $log(n)$. However, it is unknown whether  $\tilde{d}$ in the proposed off-policy neural contextual bandit is still small. In order to ensure this, one would inevitably assume conditions on the data generation process to control the decaying speed of eigenvalues of the gram matrix $H$. It would be more convincing if the authors could provide detailed quantification of data generation process. 

summary_of_the_review: The technical contribution of this paper is OK but not strong. The assumptions and theory of the paper need substantial clarifications.
review_title: null

Meta-review: This paper studies off-policy learning of contextual bandits with neural network generalization. The proposed algorithm NeuraLCB acts based on pessimistic estimates of the rewards obtained through lower confidence bounds. NeuraLCB is both analyzed and empirically evaluated.

This paper received four borderline reviews, which improved during the rebuttal phase. The main strengths of this paper are that it is well executed and that the result is timely, considering the recent advances in pessimism for offline RL. The weakness is that the result is not very technically novel, essentially a direct combination of pessimism with neural networks. This paper was discussed and all reviewers agreed that the strengths of this paper outweigh its weaknesses. I agree and recommended this paper to be accepted.
Decision: Accept (Poster)