Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper introduces a new method for exploration with deep networks. Both theoretical and empirical results are presented. Theoretical results include properties and guarantees of this new method in linear cases. Empirical results include simulations and a few real world datasets, which were used to benchmark contextual bandit algorithms. 

main_review: To the best of my knowledge, the method is new to this application. The contribution of this paper is clear to me. Overall, I am positive about this paper. The new method has the great advantage of computational efficiency, which is one of the big challenges for exploration with deep networks. I find the paper easy to follow and is clearly written. 
As a minor comment, it would be good to step back and also empirically show how well SAU approximates model uncertainty. This might be more helpful to convince the reader that SAU is generalizable that can be potentially applied to other RL problems. One previous paper that did similar evaluations is Ovadia et al, Neurips 2019. That paper specifically looks at datasets with distribution shifts with extensive benchmarks, which by no means is necessary for this paper. 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes an algorithm for contextual bandits based on function approximation using deep neural networks. In order to trade-off exploration and exploitation, the proposed algorithm estimates the variance of the sample mean for each action's rewards, and uses a UCB-like approach to select promising actions. Theoretical results for Bernoulli and linear bandits are provided. Empirical experiments show that the proposed algorithm outperforms standard alternatives in popular benchmark datasets.
main_review: I'll list strong (+) and weak (-) points, together with questions (?).

(+) The algorithm is conceptually simple, computationally cheap, and easy to implement.

(+) Reproducibility code made available.

(-) My main concern is novelty. If I'm not missing something, the idea is to instantiate the standard UCB algorithm with NN representations (see, say, eq 1 in [1]). For each action, we estimate its mean value for the current context, and add a "bonus" that depends on the action but *not* on the current context, as opposed to relying on uncertainty measures that also depend on the context (for example, see eq 5 in [2]). I don't think this is highlighted enough in the paper. How much better can we do by also using the specific context at hand to quantify reward uncertainty?

(-) Literature review and connection with past work is completely missing. For example, how does the proposed approach compare to "Neural Contextual Bandits with UCB-based Exploration" by Zhou, Li and Gu?

(?/-) Why not use \theta_t in (3) for all observations (t = current step)? From a statistical perspective, I don't see any reason to use out-dated estimates. I assume this is for computational reasons, as it's cheaper to not re-evaluate the residuals for the uncertainty estimate at every step (you could do it every M steps though, otherwise your initial residuals may not be accurate at some point). What's the regret price of not updating \theta? I think comparing these two approaches in the empirical results is needed to justify this design choice (i.e., if the difference in performance is tiny but the computational savings are huge, then it should be fine). For practical applications where the environment may not even be stationary (say ads), this could become a big issue, but updating residuals every now and then shouldn't be a big deal.

(?) Aren't we missing a key UCB paramater (\alpha) in (7), which controls the width of the interval (and has been observed to have a strong impact on UCB performance)? Was this optimized for the experiments?

(?) If the main hypothesis to test here is that a simple context-independent variance estimate is enough to explore, why not compare with a simple NN algorithm that outputs not only the mean reward for a context, but some sort of context-dependent variance estimate? This could be optimized by maximizing likelihood at the observed r_i with respect to a Gaussian distribution N(f_mu(x_i), f_sigma2(x_i)). Exploration then can use this uncertainty in the same way you propose. I'm not saying this will work better, but may shed some light on the usefulness or lack-of of context-dependent exploration.

[1] - Use of variance estimation in the multi-armed bandit problem (Audibert, Munos and Szepesvari).
[2] - A Contextual-Bandit Approach to Personalized News Article Recommendation (Li, Chu, Langford, Schapire).


Typos:
Line 4: "the the"
Line 132: In algorithm 1, \tau is missing the square in SAU-UCB, step 6. 

limitations_and_societal_impact: N/A.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors propose a simple exploration method based on Sample Average Uncertainty (SAU) for contextual bandits. SAU is a frequentist approach - it directly estimates the uncertainty in reward prediction. This uncertainty can then be combined with a UCB-type or sampling-type approach. The authors show that SAU approximates mean-square error in Bernoulli bandits and in linear contextual bandits (under technical assumptions). Furthermore, the authors show empirically that the proposed SAU-UCB and SAU-sampling work well under a wide range of benchmark tasks in deep contextual bandits. 


main_review: The main contribution of the work is the development and analysis of a simple exploration technique that is shown to work well under a good range of benchmark tasks and with theoretical properties (for simpler cases). The biggest advantage of the proposed approach is its simplicity. Furthermore, the proposed algorithms seem to be fairly consistent among different tasks based on the numerical evaluation presented in the manuscript. 

SAU is a very simple method (which is its biggest advantage). It will be very helpful for readers if the authors can articulate why it works. Specifically, the exploration term in SAU is independent of the context. Why does it work ignoring the contextual information? Is homogeneity (line 181) the reason? In deep neural network settings, what is the intuition behind it? Is it because the uncertainty under contexts is aggregated into the uncertainty in prediction? 

The current numerical evaluation leverages the benchmark work in [18]. I took a quick look at [18] and have a couple of clarification questions. First, the regret reported in this paper is consistently higher than that reported in [18] for the same environment. Is that because the algorithms are run at a longer period in this paper? Second, in [18], variants of the same algorithm are evaluated and sometimes with much different performance. Which ones are adopted in the evaluation in this paper? For example, the current manuscript picked NeuarlLinear as a baseline where NeuralLInear has two variants in [18], which perform better in different tasks. Similarly, LinearPosterior is another baseline in the current manuscript, which has multiple variants in [18], some with lower regrets. Which one is used in the current manuscript? I do note that consistency is one of the key advantages of the proposed algorithms, especially Neural-SAU-S and Neural-SAU-UCB, based on the presented numeral evaluation.

limitations_and_societal_impact: The discussion is satisfactory.
review_title: null

Meta-review: In this work, the authors present a novel strategy for quantifying uncertainty for the purpose of exploration in contextual bandits.  The simple, frequentist based Sample Average Uncertainty is shown to work well empirically and the authors show theoretically that the method is competitive with Thompson sampling in the limit.  Initially one reviewer was concerned about novelty, but found that concern to be addressed satisfactorily in by the authors.  Overall, there is a consensus among the reviewers that the paper makes a useful contribution, the method is simple, easy to implement and the empirical and theoretical results are compelling.  Thus the recommendation is to accept this paper as a poster.
Decision: Accept (Poster)