Deep Bandits Show-Off: Simple and Efficient Exploration with Deep Networks
Authors: Rong Zhu
Mattia Rigotti
Venue: NeurIPS 2021 Poster (2021)
Keywords: bandits
exploration
deep bayesian bandits
Thompson Sampling

Abstract: Designing efficient exploration is central to Reinforcement Learning due to the fundamental problem posed by the exploration-exploitation dilemma.  
Bayesian exploration strategies like Thompson Sampling resolve this trade-off in a principled way by modeling and updating the distribution of the parameters of the action-value function, the outcome model of the environment.
However, this technique becomes infeasible for complex environments due to the computational intractability of maintaining probability distributions over parameters of outcome models of corresponding complexity.
Moreover, the approximation techniques introduced to mitigate this issue typically result in poor exploration-exploitation trade-offs, as observed in the case of deep neural network models with approximate posterior methods that have been shown to underperform in the deep bandit scenario.

In this paper we introduce Sample Average Uncertainty (SAU), a simple and efficient uncertainty measure for contextual bandits.
While Bayesian approaches like Thompson Sampling estimate outcomes uncertainty indirectly by first quantifying the variability over the parameters of the outcome model, SAU is a frequentist approach that directly estimates the uncertainty of the outcomes based on the value predictions.
Importantly, we show theoretically that the uncertainty measure estimated by SAU asymptotically matches the uncertainty provided by Thompson Sampling, as well as its regret bounds.
Because of its simplicity SAU can be seamlessly applied to deep contextual bandits as a very scalable drop-in replacement for epsilon-greedy exploration.
We confirm empirically our theory by showing that SAU-based exploration outperforms current state-of-the-art deep Bayesian bandit methods on several real-world datasets at modest computation cost, and make the code to reproduce our results available at \url{https://github.com/ibm/sau-explore}.

Deep Bandits Show-Off: Simple and Efficient Exploration with Deep Networks
Rong Zhu
Institute of Science and Technology for Brain-inspired Intelligence, Fudan University rongzhuōfudan. edu. en
Mattia Rigotti* IBM Research Al
m22666ccolumia..om edu
Abstract
Designing efficient exploration is central to Reinforcement Learning due the fundamental problem posed by the exploration-exploiatuiee exploration strategies like Thompson Sampling resolve this trade-off in principled way by modeling and updating the distribution of the parameters of the action-value function, the outcome model of the environment. However, this technique becomes infeasible for complex environments due to the computational intractability maintaining probability distributions over parameters of outcome models of responding complexity. Moreover, the approximation techniques introduced to mitigate this issue typically result in poor exploration-explootttion trade-offs, observed in the case of deep neural network models with approximate posterior methods that have been shown underperform in the deep bandit scenario.
dilemma. Bayesian
In this paper we introduce Sample Average Uncertainty (SAU), simple and effi- cient uncertainty measure for contextual bandits. While Bayesian approaches like Thompson Sampling estimate outcomes uncertainty indirectly by first quantifying the variability over the parameters of the outcome model, SAU a frequentist ap- proach that directly estimates the uncertainty of the outcomes based on the value pre- dictions. Importantly, we show theoretically that the uncertainty measure estimated by SAU asymptotically matches the uncertainty provided by Thompson Sampling, as well as its regret bounds. Because of its simplicity SAU can be seamlessly ap- plied to deep contextual bandits very scalable drop-in replacement for epsilon- greedy exploration. We confirm empirically our theory by showing that SAU-based exploration outperforms current state-of-the-an deep Bayesian bandit methods on several real-world datasets at modest computation cost, and make the code to reproduce our results available at stthttp:: :tttps://githu.. com htm/ sau explore
Introduction
The exploration-exploittiie dilemma a fundamental problem in models of decision making under uncertainty in various areas statistics, economics, machine learning, game theory, adaptive control and management. Given set of actions associated with unknown probabilistic rewards, agent has to decide whether to exploit familiar actions to maximizing immediate reward or to explore poorly understood or unknown actions for potentially finding ways improve future rewards.
CCorresponding author
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Quantifying the uncertainty associated with the value of each action is a key component of conven- tional algorithms for addressing the auploratoon-xxloiiteee
dilemma. In particular, is central the two most successful exploration strategies commonly adopted in bandit settings: Upper Confidence Bound (UCB) and Thompson Sampling. The UCB algorithm [0 follows the principle of optimism in the face of uncertainty, which promotes exploration by maintaining confidence sets for value estimates and then choosing actions optimistically within these confidence sets. Thompson Sampling (TS), introduced by [12] and successfully applied in a wide range of settings [13166), is based on the principle of sampling in the face of uncertainty, meaning that it samples actions from the posterior distribution over action- valuess given past rewards.
In modern reinforcement learning (RL), the flexible generalization capabilities of neural networks brought about by Deep RL have proven successful in tackling complex environments by learning mappings from high-dimensional observations directly to value estimates [17. However, obtaining uncertainty measures over complex value functions like neural network models becomes challenging because of the intractability of estimating and updating posteriors over their parameters, limiting the applicability of Bayesian exploration strategies like UCB and TS. Recently, several proposals to address this challenge have been put forth that rely on approximations of the posterior over value functions. Unfortunately, these methods tend to underperform empirically compared to much simpler heuristics. For instance, [8] showed that in contextual bandit tasks the main approximate Bayesian posterior methods for deep neural networks are consistently beaten by simple baselines such as combining neural network value functions with a basic exploration strategy like epsilon- epsilon-greedy, greedy, or using simple vallus like linear regression where the exact posterior can be computed.
In this paper we propose a novel uncertainty measure which departs from the Bayesian approach of estimating the uncertainty over the parameters of the value prediction model. Our uncertainty measure, which we call Sample Average Uncertainty (SAU) is a frequentist quantity that only depends on the value prediction of each action. In particular, unlike UCB and TS, exploration based on SAU does not require the costly computation of a posterior distribution over models order to estimate uncertainty of their predictions. In fact, instead of first estimating the uncertainty over the parameters of the value function to then use it to quantify the uncertainty over outcomes, SAU directly estimates uncertainty over outcomes by measuring the variance of sample averages. This result is then plugged into the current estimate of the outcome model.
With our new measure of uncertainty of the expected action-values we build two SAU-based exploration strategies: one based on the principle of "optimism in the face of SAU" that we name SAU-UCB, and a second one based on "sampling in the face of SAU" that name Sampligg
We investigate the use of these new exploration strategies tackle contextual bandit problems, and show that SAU is closely related to the mean-squared error in contextual bandits. This allows us to show amalytically that in the case of Bernoulli multi-armed bandits the SAU measure converges the uncertainty of the action-value estimates that are obtained by TS. despite SAU being much simpler to compute and not needing to rely on maintaining the posterior distribution. In addition, we derive an upper bound on the expected regret incurred by our SAU algorithms in multi-armed bandits that shows that they achieve the optimal logarithmic regret.
Finally, we empirically study the deployment of SAU-UCB and SAU-Samplin in the deep bandit setting and use them as exploration strategy for deep neural network value function models. Con- cretely, we follow the study of (18) and show that SAU consistently outranks the deep Bayesian bandit algorithms that they analyzed on the benchmarks that they proposed.
2 Problem Formulation: Contextual Bandits
The contextual bandit problem is a paradigmatic model for the study of the trade-off and is formulated as follows. At each time step n we observe context x,, select an action an from a set IK = (1..... K}, after which we receive reward ra. The value of an action a (in context x,, RRP) is defined the expected reward given that is selected:
Elra la, a] p(xn; 0n),
where in general the action-values uu()) depend on unknown parameters O,. IRP.
Our goal is to design a sequential decision-making policy x that over time learns the action parameters O. which maximize the expected reward. This goal is readily quantified in terms of minimizing
2

---

expected regret, where we say that at step we incur expected regret
max(u 0x)) (x(xn, Oa..);
a'EX
Le. the difference between the reward received by playing the optimal action and the one following the chosen action ag. One way to design sequential decision- policy that minimizes expected regret is to quantify the uncertainty around the current estimate of the unknown parameters 0.. TS for instance does this by sequentially updating the posterior of 0, after each action and reward. This paper presents a novel and simpler alternative method to estimate uncertainty.
Exploration based on Sample Average Uncertainty
3.1 Sample Average Uncertainty (SAU)
In this section, we begin with introducing our novel measure of uncertainty SAU. Let Ta denote the set of time steps when action chosen so far, and let ni be the size of this set. Based on the nhe rewards {rn (nnJ.eT, obtained with action a, the sample mean reward given action a is:
Fg = n EnET." Tn-
At this point reiterate that exploitation and exploration customarily traded off against each other with Bayesian approach that estimates the uncertainty of the action-values on the basis of posterior distribution over their parameters given past rewards. Instead, propose a frequentist approach that directly measures the uncertainty of the sample average rewards that was just computed. Direct calculation using eq. (I) then gives that the variance of the sample mean reward is
Var(F.) = = na/na> where 0² = naa ' nET. 2e with
n;a = E [(ra - ul 0a))
Assuming that there sequence of estimators (0n,a) IneT, of le. we can replace 0, with @n,a at each n E T, to approximate &% with a convenient statistics Th defined as
2 = Σ nET, (rm - m(0n, ul))n.n.a))
(3)
With this we get an approximate sample mean variance of
Var(Fa) = -2/To.
(4)
The central proposal of this paper is use Var(Fa) as measure of the uncertainty of the decision sequence. We call this quantity Sample Average Uncertainty (SAU), since it measures directly the uncertainty of sample mean rewards Fa. In practice, 7 can be updated incrementally as follows:
1. Compute the prediction residual:
en = In - [(Xx,, i mn,..)) ):
(5)
2. Update Sample Average Uncertainty (SAU):
72 - -2_ + n (en
Tan
(6)
Let us take moment to contrast the uncertainty measure given by SAU and existing exploration algorithms like TS, which as we said would estimate the uncertainty of the action-value function yu()) by maintaining and updating distribution over its parameters 0.. SAU instead directly quantifies the uncertainty associated with each action by measuring the uncertainty of the sample average rewards. The clear advantage of SAU is that it is simple and efficient to compute: all it requires the prediction residuals rn p(x,, 0 m..... without any need model or access the uncertainty of μ(x,,, On.a). Because of the simplicity of its implementation, SAU can be naturally adapted to arbitrary action-value functions. In particular, it can be used implement exploration strategy for action-value function parameterized as deep neural networks or other model classes for which TS would be infeasible because of the intractability of computing probability distribution over models.
Note that in updating 72 we use the residuals obtained each step rather than re-evaluating them using later estimates. This is design choice motivated by the goal of minimizing the computation cost and implementation efficiency of SAU. Moreover, this choice can be justified from the viewpoint of the statistical efficiency, since, the number of training samples increases, the impact of initial residuals
3

---

will decrease, so that the benefit of re-evaluating them incurs diminishing returns. Proposition formalizes this argument by showing that indeed T2 as computed in eq. (6) is concentrated around its expectation. In addition, perhaps importantly, the aim of SAU is to provide quantity to support exploration. The effect of potentially inaccurate residuals in the initial steps may actually be beneficial due to the introduction of additional noise driving initial exploration. This might be in part at the root of the good empirical results.
3.2 SAU-based Exploration in Bandit Problems
We now use the SAU measure to implement exploration strategies for (contextual) bandit problems.
SAU-UCB. UCB is a common way to perform exploration. Central to UCB is the specification of an "exploration bonus" which is typically chosen to be proportional to the measure of uncertainty. Accordingly, we propose to use the SAU measure o as exploration bonus. Specifically, given value predictions An.a [((,,, 0 n, for each a at step n,, we modify the values as
An,a = -Ana + V no r log
then choose the action by On = arg max., ((in, We call this implementation of UCB using SAU as exploration bonus: SAU-UCB.
SAU-Sampling. "Sampling in the face of uncertainty" is an alternative exploration principle that we propose to implement with SAU in addition to UCB. This is inspired by TS which samples the success probability estimate A. from its posterior distribution. Analogously, we propose to sample values from a parametric Gaussian distribution with mean given by the value prediction and variance given by o. This results in sampling values Pn.a each time n as:
Unna ~ N (im,a Tá T2/na))
(8)
then choosing the action by a, = arg max, (Lim,a SAU-Sampling. SAU-UCB and SAU-Sampling are summarized in Algorithm
We call this use of SAU inspired by TS,
Algorithm SAU-UCB and SAU-Sampling for bandit problems
1: Initialize: Q., S 1 and for E K.
2: for = 1,2, 2,... do
3: Observe context x,, 4: for = I..... K
5: Calculate the prediction Pn,a = u(x,;; Qa) and r22 = 5? na/nai
6: Draw sample
Pn.a = =nn,a + v T2 logn (SAU-UCB) or An,a ~ N (Rn,a: --2)) (SAU-Sampling);
7:
end for
8:
Compute On = arg maxa ) Jagk) if > K, otherwise an = m
9:
Select action on, observe reward Tni Update Qg, and increment Na,, f- ne, + 1;
11:
Update 5² S2 + eñ using prediction error calculated as en I' Pn,an
12:
end for
3.3 Novelty and comparison with related approaches
Using the variance estimation in MAB is not novel. For example [19 makes use of Bernstein's 's inequality to refine confidence intervals by additionally considering the uncertainty from estimating variance of reward noise. Our approach is fundamentally different from it with two aspects. First, Algorithm T is to propose novel measure to approximate the uncertainty of the estimate of the mean reward that would afford such a flexible implementation and can therefore directly extended

---

and scaled up to complicated value models like deep neural networks. Second, our SAU quantity 7² the per-step squared prediction error, i.e., the average cumulative squared prediction error, as opposed to an estimate of the variance of the different arms. In fact, 7 does not rely on the traditional variance estimation analyzed by [9], but is instead simply computed directly from the prediction. This difference makes SAU even easier to implement and adapt to settings like deep networks.
The exploration bonus in Algorithm i is not function of the observed context, though is updated from historical observations of the context. The algorithm could indeed be extended to provide a quantification of reward uncertainty that is a function of the current context by, for instance, fitting the SAU quantity as a function of context. Clearly, this will come at the cost of substantially increasing the complexity of the algorithm. Therefore avoid this additional complexity, we instead focus the paper on the development of the SAU quantity as simple estimate of uncertainty to efficiently drive exploration. However, exploring this possibility is potentially exciting direction for future work.
SAU in Multi-Armed Bandits
4.1 SAU Approximates Mean-squared Error and TS in Multi-armed Bandits
Before considering the contextual bandits scenario, we analyze the measure of uncertainty provided by SAU in multi-armed bandits, and compare it to the uncertainty computed by TS. This will help motivate SAU and elucidate its functioning.
We assume multi-armed Bernoulli bandit, i.c. at each step each action E IK results in a reward sampled from Tn ~ Bernoulli (pa) with fixed (unknown) means j4 E [0, 1]. Assume that action a has been taken na times far, and let faa denote the sample averages of the rewards for each action. The prediction residual eq. (5) is en = Tn Po. and is the central quantity to compute SAU.
TS in the case of Bernoulli bandits is typically applied by assuming that the prior follows a Beta distribution, i.e. the values are sampled from Beta Sa) with parameters 0a and (3, for a E K. Uncertainty around the estimated mean values are then quantified by its variance denoted by Va (see Appendix A.IIp. Ip. We then have the following proposition relating SAU and TS in Bernoulli bandits:
Proposition 1 For Beta Bernoulli bandits the expectation of the average prediction residual ea an approximate unbiased estimator of the expectation of the posterior variance V. in TS. Concretely:
E a.. = E/ee// n + O (m=!)
Proof Proof of Proposition is provided in Appendix A.
Proposition [ says that SAU asymptotically approximates TS for Bernoulli bandits, despite not needing to assume prior and update a posterior distribution over parameters. In Appendix A.3 we support this empirically by showing that in multi-armed bandits SAU rivals TS.
The following proposition further characterizes the prediction residual:
Proposition 2
For Bernoulli bandits the expectation of the prediction residual used in SAU satisfies
Ele./ E((rx - Paa.,) ///a... = E [Po.. -Ma.) )} + O (
Proof Proof of Proposition is provided in Appendix A.2
Proposition Ssayss that the prediction residual en Ta Aa, is an approximately unbiased estimator of the mean squared error E [Aa.. Ma.. ) )]. This means that for Bernoulli bandits, SAU closely approximates the uncertainty of the action-value estimates.
Armed with this characterization of the prediction residual r, - in Proposition we now quantify the performance of the estimator 722 in eq. (3) in terms of its concentration around its expectation:
Proposition 3 For 8 E ex (-o2na/ (32c)) 1). where o² is the variance of ffr j E Ta and a constant, we have
Pr Pr(112
E E[=ā]] 2 oa BBB/nn 1og(6/21)} 5o,
5

---

Proof Proof of Proposition is provided in Appendix A.4
Proposition says that = is concentrated around its expectation, and thus remains stable as it is being updated. In Appendix A.6 A.6 we also show that E [-2] + o as n., + co, and in Appendix A.7 we derive an upper bound on the expected regrets SAU-UCB and SAU-Sampling multi-armed bandits proving that the optimal logarithmic regrets achievable uniformly over time, which says that the theoretical performance of SAU rivals TS in multi-armed bandits.
4.2 SAU in Linear Contextual Bandits:
Theoretical analysis
We now show that the results in Proposition 2 also hold for another important bandit model beside Bernoulli bandits, i.c linear contextual bandits defined by the following outcome model:
x, 02 + En,a, = 1......
(9)
where xn, On E IRP, and 6n,a are iid random variables with variance of Assume action was selected na times. We obtain the least-squares estimator On,a,, (EjET.... Accordingly, the prediction and the prediction residual step are, respectively,
x] rz).
an.an X, O n.an
and 2 = (Tn - x )
(10)
xxxx,)=xxn The mean squared error of x,, On,a, is MSEn = B[(xIT On.. -x,, 09. With direct calculation we see that MSE, = hno on and that E / = (1 - hn)o /na.. Therefore, we have the following proposition:
Denote hn x (EJETneen
Proposition 4 For linear contextual bandits ( we have that Blei./nan. (h, ) hn) MSE
Furthermore, assuming that there exist constants 6j and 02 that e1 ca/nan S hn S C2/ then
2 (1 (Cc///na.) MSE S STE [E[ce// [e2///an] S oT 10l--///n c1/man) MSE
Proposition provides a lower and an upper bound for E [ez/nan) in terms of MSE., meaning that on average SAU is conservative measure of the uncertainty around x,, On..... Noting that 0 $ hy I and ΣjeT,... h, = the assumption that / S hn S C2//no.. requires that h does not dominate or is dominated by other terms hy. with E T n..... meaning that contexts should be "homogeneous" to a certain extent. To examine the robustness to violations of this assumption, the simulation in Appendix B we empirically test the performance under heavy-tailed t-distribution with df = 2. The results show that SAU works robustly even under such type of context inhomogeneity.
4.3 SAU in Linear Contextual Bandits: Empirical evaluation on synthetic data
In this section, we present simulation results quantifying the performance of our SAU-based explo- ration algorithms linear contextual bandits. We evaluate SAU on synthetically generated datasets to address two questions: (1) How does SAU's performance compare against Thompson Sampling?, and (2) How robust is SAU various parameter regimes?
We consider three scenarios for K (the number of actions) and (the context dimensionality): (a) K 5, p = 5, (b)
20, p 5, and (b) each action parameters 0, are drawn from uniform distribution in [-1, 1). then normalized so that [0a|| = Next, each step context x, is sampled from a Gaussian distribution (O Ip). Finally, we the noise variance to be x² 0.5² that the signal-to-noise ratio equals 4.
5. 40. The horizon is N 20000 steps. For
We compare our AAU-based exploration algorithms, SAU-UCB and SAU-Sampling to Thompson Sampling ("TS" in Fig. []. For TS on linear model, follow [18 and use Bayesian linear regression for exact posterior inference. We also consider the PrecisionDiag approximation for the posterior covariance matrix of O, with the same priors in [88 ("TSdiag" in Fig. [
Fig. bb) shows regret as a function of step for (K,p) = (5,5). From the figure we have two observations: SAU-Sampling is comparable to TS, and SAU-UCB achieves better regret than TS. In

---

a)
5))
b)
(K,
(K, p))(5, 40)
80
400
1000
8-
Regret
200
TS
400
TSdiag
SAU-Sampling
SAU-UCB
10000
10000
10000
Step
Step
Step
120
Regret at final step n=N
2000
450
100
8
400
1500
3.50
1000
300
500
TS
TSdiag SAU-S. SAU-UCB
TS
TSdiag SAU-S.
SAU-S.SA-UUCE SAU-UCB
TS
TSdiag SAU-S. SAU-UCB
Figure I: Performance on contextual linear bandits with various (K,p) parameters showing that our models (SAp-ig and SAU-UCB) consistently achieve lower regret than TS using Bayesian linear regression with exact posterior inference (TS) and TS with PrecisionDiag approximation (TSdiag). The upper panels report regret function of step where results averaged over 100 runs. The lower panels show the distributions of the regret at the final step.
terms of cumulative regret SAU significantly outperforms TS and TSdiag, Figures [b) and c) show the effects of larger K and p. respectively. The observations from Fig. aT] still hold in these cases, implying that SAU's performance is robust to increase in action space and context dimension.
We also consider four other cases: (1) the elements of 9a are sampled from (000 1) then are normalized; (2) the model errors are correlated with AR(1) covariance structure with correlation p 0.5; (3) the elements in x; are correlated with A AR(1) covariance structure with correlation p 0.5; and (4) the elements of are sampled from a heavy-tailed /-distribution with df = 2 and are truncated at 5. These results are shown in Appendix and are consistent with the results in Fig
confirming SAU's robustness to various contextual linear bandit problems.
Deep Contextual Bandits
5.1 Deep Bayesian Bandit Algorithms
Deep contextual bandits refers to tackling contextual bandits by parameterizing the action-value function as a deep neural network (u(x, 0), thereby leveraging models that have been very successful in the large-scale supervised learning (20] and RL [17]. Notice that the deep setting we denote all parameters with 0 {0.)ock. common in the neural network literature. In particular, 0 includes the parameters that are shared across actions, as well as those the last layer of the network which are specific to each action Algorithm 2 breaks down generic deep contextual bandit algorithm in terms of an API exposing its basic subroutines: PREDICT (which outputs the set of action-values [Pn.Fase given the observation x,), ACTION (which selects action given all the action-valuee and UPDATE (which updates model parameters at the and of the step).
In this scheme Thompson Sampling (TS) is implemented as in Algorithm which underlines where TS promotes exploration by sampling from a distribution over model parameters P, In principle this provides an elegant Bayesian approach tackle the exploration-exploitation dilemma embodied

---

Algorithm 2 Generic Deep Contextual Bandit algorithm
1:
for n= 1,2,... do
2: Observe context Xn
3: Compute values {/4naa Jack PREDICT(X,):
4: Choose an = ACTION( ( beEK), observe reward Fn;
5: UPDATE (Tn, On, Xn);
6:
end for
by contextual bandits. Unfortunately, representing and updating posterior distribution over model parameters (0) exactly becomes intractable for complex models such as deep neural networks.
Algorithm 3 Thompson Sampling for Deep Contextual Bandits
function PREDICT(X,)
2: Exploration: Sample model parameters from posterior distribution: 0, (0)
3: Return predicted values (An,aJacK [xxx,, On), where
4: function ACTiON(fPm.aJaE:
5: Return an arg max (f JaEk))
6: function UPDATF(rn On, xn)
7: Use triplet (Ins O2z xn) to update posterior distribution: (0) <- Pr(0)):
To obviate this problem, several techniques that heuristically approximate posterior sampling have emerged, such as randomly perturbing network parameters (3]. or bootstrapped sampling [24]. Within the scheme of Algorithm the role of random perturbation and bootstrapped sampling are to heuristically emulate the model sampling procedure promoting exploration in the PREDICT subroutine (see TS Algorithm 3). However, systematic empirical comparisons recently demonstrated that simple strategies such as epsilon-gredd greedy [17 25 and Bayesian linear regression 26 remain very competitive compared to these approximate posterior sampling methods in deep contextual bandit. In particular, 18] showed that linear models where the posterior can be computed exactly, and apsilon-greede action selection overwhelmingly outrank deep methods with approximate posterior sampling in suite of contextual bandit benchmarks based on real-world data.
5.2 SAU for Deep Contextual Bandits
We now re-examine the deep contextual bandits benchmarks in [18 and show that SAU can be seam- lessly combined with deep neural networks, resulting in an exploration strategy whose performance is competitive with the best deep contextual bandit algorithms identified by [18]
Algorithm shows the deep contextual bandit implementation of SAU. Notice that the PREDICT subroutine is remarkably simple, consisting merely in the forward step of the deep neural network value prediction model. In contrast our extremely simple procedure, TS-based methods require at this step to (approximately) sample from the model posterior to implement exploration. In SAU exploration is instead taken care of by the ACTION subroutine, which takes the values as inputs and either explores through sampling from distribution around the predicted values Sampling) or through an exploration bonus added to them (SAU-UCB). SAU then selects the action corresponding to the maximum of these perturbed values. The UPDATE for SAU is also quite simple, and consists in updating the neural network parameters to minimize the reward prediction error loss L, following action selection using SGD via backprop, or possibly its mini-bate version (which would then be carried out on a batch of (r.., an X,,) triplets previously stored in a memory buffer). UPDATE then updates the count and the SAU measure Ta., for the selected action an.
We notice that the simplicity of SAU for deep contextual bandits is akin to the simplicity of epsilon- greedy, for which exploration is also implemented in the ACTION subroutine (see Algorithms Appendix fact, comparing the two algorithms it is clear that SAU can be used as a drop-in replacement for epsilon- greedy exploration, making it widely applicable.
8

---

Algorithm 4 SAU for Deep Contextual Bandits (SAUi-Nerral-Smpping and UCB)
I: function PREDICT(X,))
2: Return predicted values (in.taEx uxxx,, Qn)):
3: function ACTION ((n,,)))))
4: Exploration: Compute
Pn,a ~ N (Pn,a; To/maa
(SAU-Sampling) (SAU-UCB);
5:
or An. Pnn,a + V To log n/no
6:
Return 0n = arg max ( (Mn,a)aEB);
7:
function UPDATE((,> On
x,)
8:
Compute prediction error en = I' - An,,, and loss 4, (Tn pn, )²
9:
Update model parameters to d using SGD with gradients
01
30 (or mini-batch version);
10:
Update exploration parameters: na, + Ran. + 1, St + S + en To_ = S / /aan'
5.3 Empirical Evaluation of SAU on Deep Contextual Bandit Problems
Benchmarks and baseline algorithms. Our empirical evaluation of SAU's performance in the deep contextual bandit setting is based on the experiments by (T8), who benchmarked the main TS-based approximate posterior sampling methods over series of contextual bandit problems. We test SAU on the same contextual bandit problems against 4 competing algorithms consisting in the 4 best ranking algorithms identified by [8] which are: LinearPosterion (a closed-form Bayesian linear regression algorithm for exact posterior inference under the assumption of a linear contextual bandit (27), LinearGreedy (epsilon-greed) exploration under the assumption of linear contextual bandit), NeuralLinear (Bayesian linear regression on top of the last layer of neural network trained with SGD (8) and NeuralGreedy (a neural network with epsilon-greedy exploration trained with SGD). We neglected a direct comparison with NeuralUCB [29]. since its scaling in memory and computational requirements make quickly impractical for even moderately sized applications of practical interest. Moreover, its reported performance is substantially worse than SAU-UCB.
Implementations of SAU. We implemented and tested 4 versions of SAU on the benchmarks in [8] In the Tables below we refer to them a follows: Linear-SAUs and Sinear-SU--UG refer to a linear regression model using SAU-Sampling and SAU-UCB exploration strategies, respectively. Neural- SAU-S and Neural-SAU-UCA refer to a neural network model trained with SGD using SAU-Sampling and SAU-UCB, respectively.
Empirical evaluation on the Wheel Bandit. The Wheel Bandit Problem is a synthetic bandit designed by [8]] to study the performance of bandit algorithms as function of the need for exploration the environment by varying a parameter E [0, 1] that smoothly changes the importance of exploration. In particular, the difficulty of the problem increases with 6, since the problem is designed so that for ó close to most contexts have the same optimal action, while only for a fraction 1 - 82 of contexts the optimal action is a different more rewarding action (see [8 for more details). In Appendix C, Table 22 quantifiess the performance of SAU-Sampling and SAU-UCB in terms of cumulative regret in comparison to the 4 competing algorithms, and normalized to the performance of the Uniform baseline, which selects actions uniformly at random. There we can see that Neural-SAU-S is consistently the best algorithm with lower cumulative regret for wide rage of the parameter 6. Only for very high values of 5 (ō 0.99) the baseline algorithm NeuralLiner starts to overtake it, but even in this case, another variant of SAU, SAU-Linear-S still maintains the lead in performance.
Empirical evaluation on weal-world Deep Contextual Bandit problems. Table D quantifics the and SAU-UCB in comparison to the 4 competing baseline algorithms,
performance of and normalized to the performance of the Uniform baseline. These results show that a SAU algorithm is the best algorithm in each of the 7 benchmarks in terms of minimizing cumulative regret over all samples. Neural-SAU-S or Neural-SAU--CCA are the best combination 6 out of 7 times, and linear regression with SAU-UCB is the best the bandit built from the Adult dataset. The next best algorithm in terms of minimizing cumulative regret is NeuralLinear [8), which incurs cumulative regret that on average is 32% higher than Neural-SAU: and 34% higher than Neural-SAU-UCB.
As already mentioned, thanks to their implementation efficiency SAU-based algorithms are much less computation intensive than ba-ba algorithms. This is reflected in the remarkably shorter

---

Table I: Cumulative regret incurred on the contextual bandits in [8]] by the 4 best algorithms that they identified (described in Appendix D) compared against our SAU-based algorithms. Results are relative to the cumulative regret of the Uniform algorithm. We report the mean and standard error of the mean over 50 trials. The best mean cumulative regret value for each task is marked in bold.
Mushruom
Statlog
Covertype
Finuncial
Jester
Adult
Census
LincurPosterior
3.02 0.15
10.29 0.19
36.88 a 0.07
10.77 = 0.15
64.01 + 0.40
75.87 a 0.06
46.70 = 0.08
LinearGready
0.35
109.26 0.95
53.50 2.00
15.48 1.02
62.71 0.45
0.24
65.35
Neurall inear
2,66 + 0,08
1.26 + 0.03
29.18 0.07
10, 16 0.18
699.48 0.43
78.28 0.07
41.00 0.09
NeuralGrredy
26,06
40.17 0.46
0.12
93.15 0.77
98,96 0.03
Linear-AUU-S
4,58 0.39
10.44 0.26
36.29 0.12
8.71
62.59 0.43
74.70 0.13
39.65 0.11
Linear-AL--UCE
3.09 1: 0.15
10.02 1: 0.22
36.77 0.17
0.37
64,43 0:40
74.62 1: 0.07
39.98 0.09
Neural-SAU-8
2.20 0.05
0.62 + 0.01
27.46 0.06
5.60 0.11
61.02 0.57
78.02 0.07
38.76 0.08
Neural-SAU--UCCB
+ 0.06
0.60 =: 0.01
27.90 0.06
5.26 + 0.15
62.27 + 0.61
78.09 # 0.06
38.54 0.09
Uniform
100.00
100.00 0.03
100.00 0.02
100.00
100.00 0.96
100,00 0.02
0.04
exccution time: on average Neural-SAU-S and Neural-SAU- run more than 10 time faster than (sce Appendix Table for details), also making them extremely scalable.
NeuralLinear [8]
6 Conclusion and Discussion
Existing methods to estimate uncertainty tend to be impractical for complex value function models like deep neural networks, either because exact posterior estimation become unfeasible, or due to how approximate algorithms coupled with deep learning training amplify estimation errors.
In this paper, we have introduced Sample Average Uncertainty (SAU), a simple and efficient uncer- tainty measure for contextual bandit problems which sidesteps the mentioned problems plaguing Bayesian posterior methods. SAU only depends on the value prediction, contrast to methods based on Thompson Sampling that instead require an estimate of the variability of the model parameters. As result, SAU is immune to the negative effects that neural network parameterizations and opti- mization have the quality of uncertainty estimation, resulting in reliable and robust exploration as demonstrated by our empirical studies. SAU's implementation simplicity also makes it suitable as a drop-in replacement for epsilon- greeddy action selection, resulting in a scalable exploration strategy that can be effortlessly deployed in large-scale and online contextual bandit scenarios.
We also have provided theoretical justifications for SAU-based exploration by connecting SAU with posterior variance and mean-squared error estimation. However, the reasons why SAU is in practice consistently better than TS-based exploration in deep bandits is still not settled theoretically. We hypothesize that this might be due to two main reasons: (1) based methods implement exploration by estimating the uncertainty of the internal model parameters, which might introduce estimation errors, while SAU directly estimates uncertainty at the model output; (2) in addition, the approximation error from the approximate posterior implementations of TS-bases models might result in inefficient uncertainty measures of the internal model parameters. Because of the importance of contextual bandit algorithms for practical applications like for instance recommendation and ad servicing systems, we believe that it will be important to further theoretically refine these hypotheses to help mitigate the possible negative societal impacts that could result from deploying inefficient, miscalibrated or biased exploration algorithms.
Another limitation of our work is that it developed SAU-based exploration in the specific and restricted case of bandits. Despite heing an application of interest, we are excited and looking forward to further development that could extend methods based on SAU to more general sequential decision scenarios in RL beyond the bandit setting.
Acknowledgements
This work was partially supported by National Natural Science Foundation of China (No. 1 1187111144 1871459) and by Shanghai Municipal Science and Technology Major Project (N0.2018SHZDZX01),
10

---

References
[1] L. Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4-22, 1985.
[2] Peter Auer, Nicolo Fesa-Bianchi, and Paul Fischer. Finite time analysis of the multi-armed bandit problem. Machine Learning, 47:235-256, 2002.
[3] M. Woodroofe. A one-armed bandit problem with a concomitant variable. Journal of the American Statistical Association, 74:799-806, 1979.
[4] Auer. Using confidence bounds for exploitation-exploraiio trade-offs. Journal of Machine Learning Research, 3:397-422, 2003.
[5] J. Langford and T. Zhang. The epoch-greedy algorithm for multiarmed bandits with side information. In Advances in Neural Information Processing Systems, volume 20, pages 817- 824, 2008
[6] Varsha Dani, Thomas Hayes, and Sham Kakade. Stochastic linear optimization under bandit feedback. In Proceedings of the s1 Annual Conference on Learning Theory, pages 355-366, 2008.
[7] Patt Rusmevichientong and John Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395
2010. 2010.
[8] Yasin Abbasi- Yadkori, David Pal, and Csaba Szepesväri. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, volume 24, pages 2312-2320, 2011.
[9] Yasin Abbasi- Yadkori. Online learning for linearly parametrized control problems. PhD thesis, University of Alberta, Edmonton, AB, Canada., 2012.
[10] V. Perchet and P. Rigollet. The multi-armed bandit problem with covariates. The Annals of Statistics, 4 (1(2)693-7211, 2013.
[11] A. Slivkins. Contextual bandits with similarity information. Journal of Machine Learning Research, 15(1):2533-255 2014.
[12] William R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 14:285-2944 1933.
[13] M. Strens. A bayesian framework for reinforcement learning. In Proceedings of the 17th international conference on Machine learning, pages 943-950, 2000.
[14] Olivier Chapelle and Lihong Li. An empirical evaluation of Thompson sampling. In Advances in Neural Information Processing Systems, volume 24, 2011.
[15] Shipra Agrawal and Navin Goyal. Further optimal regret bounds for Thompson sampling. In Proceedings of the 16th International Conference on Artificial Intelligence and Statistics, pages 99-107, 2013.
[16] D. Russo and B. Van Roy. Learning optimize via information-direette sampling. In Advances in Neural Information Processing Systems, volume 27, pages 1583-1591, 2014.
[17] V. Mnih, K. Kavukcuoglu, D. Silver, A.A. Rusu, J. Veness, M.G. Bellemare, A. Graves M. Riedmiller, A.K. Fidjeland, G. Ostrovski, Petersen, C. Beattie, A. Sadik, Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis. Human-level control through deep reinforcement learning. Nature, 518:529-533 2015.
[18] Carlos Riquelme, George Tucker, and Jasper Snoek. Deep Bayesian bandits showdown: empirical comparison of Bayesian deep networks for Thompson sampling. In Proceedings of the 6th International Conference on Learning Representations, 2018.
[19] J.-Y. Audibert, R. Munosc, and C. Szepesvári. Exploration-exploitation tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410:1876-1902, 2009.

---

[20] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553):436 2015.
[21] Matthias Plappert, Rein Houthooft, Prafulla Dhariwal, Szymon Sidor, Richard Chen, Xi Chen, Tamim Asfour, Pieter Abbeel, and Marcin Andrychowicz. Parameter space noise for exploration. arXiv preprint arXiv: 000::10060..055 2017.
[22] M. Fortunato, M.G. Azar, B. Piot, J. Menick, Osband, A. Graves, R. Mnih, V. Munos, D. Hassabis, O. Pietquin, C. Blundell, and S. Legg- Noisy networks for exploration. In International Conference on Representation Learning, 2018.
[23] Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In International conference on machine learning, 2016.
[24] Osband, C. Blundell, A. Pritzel, and B. Van Roy. Deep exploration via bootstrapped DQN. In Advances in Neural Information Processing Systems, 2016.
[25] T. Schaul, J. Quan, I. Antonoglou, and D. Silver. Prioritized experience replay. In International Conference on Learning Representations, 2016.
[26] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 214. JMLR Workshop and Conference Proceedings. 2011.
[27] Christopher M Bishop. Pattern recognition and machine learning. springer, 2006.
[28] Jasper Snoek, Oren Rippel, Kevin Swersky, Ryan Kiros, Nadathur Satish, Narayanan Sundaram, Mostofa Patwary, Mr Prabhat, and Ryan Adams. Scalable bayesian optimization using deep neural networks. In International conference on machine learning, pages 2171-2180. PMLR, 2015.
[29] D. Zhou, Li, and Q Gu. Neural contextual bandits with ucb-based exploration. In Proceedings of the 37th International Conference Machine Learning, 2009.
[30] R. Adamczak. A note the hanson-wright inequality for random vectors with dependencies. Electronic Communications in Probability, 20(72): 2015.
[31] Branislav Kveton, Csaba Szepesväri, Sharan Vaswani, Zheng Wen, Mohammad Ghavamzadeh, and Tor Lattimore. Garbage in. reward out: Bootstrapping exploration in multi-armed bandits. In Proceedings of the 36rd International Conference on Machine Learning, 2018.
[32] Dheeru Dua and Casey Graff. UCI machine learning repository. 2017.
[33] Jeff Schlimmer. Mushroom records drawn from the Audubon society field guide to North American mushrooms. GH Lincoff (Pres), New York, 1981.
[34] Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural network. In International Conference Machine Learning, pages 1613-1622. PMLR, 2015.
[35] Ken Goldberg, Theresa Roeder, Dhruv Gupta, and Chris Perkins. Eigentaste: A constant time collaborative filtering algorithm. information retrieval, 4(2):133-151, 2001.
[36] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint urXiv:1412.6988 2014.
12


Reviews:
[{"review_id": "uJS26FiS5dc", "reviewer": "Reviewer_yDN2", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I'll list strong (+) and weak (-) points, together with questions (?).\n\n(+) The algorithm is conceptually simple, computationally cheap, and easy to implement.\n\n(+) Reproducibility code made available.\n\n(-) 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?\n\n(-) 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?\n\n(?/-) 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.\n\n(?) 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?\n\n(?) 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.\n\n[1] - Use of variance estimation in the multi-armed bandit problem (Audibert, Munos and Szepesvari).\n[2] - A Contextual-Bandit Approach to Personalized News Article Recommendation (Li, Chu, Langford, Schapire).\n\n\nTypos:\nLine 4: \"the the\"\nLine 132: In algorithm 1, \\tau is missing the square in SAU-UCB, step 6. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "svX_TGtpAC5", "reviewer": "Reviewer_fQ5w", "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. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \nAs 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "AnWl7cu0Njn", "reviewer": "Reviewer_vh32", "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. \n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nSAU 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? \n\nThe 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The discussion is satisfactory.  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

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)