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": "w4SIUN6XoTB", "reviewer": "Reviewer_bpP1", "summary": "This paper proposes a simple and efficient uncertainty measure Sample Average Uncertainty (SAU) for contextual bandits. The paper provides theoretical analysis to show that the uncertainty measure estimated by SAU asymptotically matches that estimated by Thompson Sampling. The paper also combines SAU with neural networks to design a deep contextual bandit algorithm which achieves good empirical performance. The presented experimental results on real-world datasets demonstrate that SAU-based exploration outperforms current state-of-the-art deep Bayesian bandit methods with low computation cost.", "questions": "", "limitations": "", "rating": 5, "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": "Strengths:\n1.\tThis paper conducts experiments on extensive real-world datasets to show the performance superiority of the proposed SAU-based exploration over existing deep Bayesian bandit methods.\n2.\tThe proposed SAU based algorithms are simple and easy to implement. The computation cost is largely reduced compared to existing deep Bayesian bandit methods.\n\nWeakness:\n1.\tRegret performance is one of the most important and canonical metrics in the bandit literature, but this paper only presents the regret bounds for the proposed SAU-UCB and SAU-Sampling algorithms for the preliminary K-armed bandit setting (in Appendix). The regret results of SAU-UCB/SAU-Sampling and SAU-Neural-UCB/SAU-Sampling for the contextual bandit problem are not provided, so readers cannot directly compare the theoretical performance of the proposed SAU-based algorithms with existing ones. For this reason, I give a ‘below the acceptance threshold’ score. If the authors could provide sufficient theoretical analysis of SAU-UCB/SAU-Sampling and SAU-Neural-UCB/SAU-Sampling for the (deep) contextual bandit problem, I am ready to raise my score.\n2.\tComparisons with some important related works on theoretical and empirical results are missing. For example, the classic algorithm LinUCB (Abbasi-Yadkori et al. 2011) for contextual linear bandits, and the recent state-of-the-art algorithms NeuralUCB (Zhou et al. 2019) and NeuralTS (Zhang et al. 2020) for deep contextual bandits. This paper needs to include comparisons on regret bounds and empirical evaluations with these important related works, and give a sufficient discussion on why the SAU-based exploration can attain better/state-of-the-art performance on online regrets and computation costs.\n\nReferences: \n1.\tYasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. NIPS, 2011. \n2.\tDongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with UCB-based exploration. ICML, 2020. \n3.\tWeitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. ICLR, 2021.\n\n\n**After Rebuttal**\n\nI have read the rebuttal of the authors.\n\nOverall, I think that while the proposed SAU measure is simple and interesting, given that the theoretical analysis is not completed, this paper still needs further improvements and is not sufficient for acceptance in terms of its current version. So I keep my score ‘5’.\n\nFor the bandit literature, the regret is a critical performance metrics. I suggest the authors to complete the regret analysis for contextual bandits to demonstrate the superiority of the proposed SAU measures on regret performance.\n\nAs for the experiments, comparisons with recent deep algorithms are helpful for readers to understand the empirical performance of SAU-based deep algorithms. It would be better if the authors include these experimental results and comparisons in their revision. \n\n", "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": "4"}, "extra_text": {}}, {"review_id": "mRPv2QUgw2x", "reviewer": "Reviewer_TBN4", "summary": "This paper proposes a new uncertainty measure for contextual bandits named Sample Average Uncertainty (SAU). SAU is derived from a frequentist point of view by directly looking at statistics from model predictions/outputs, and two SAU-based exploration schemes are proposed accordingly (similar to UCB and TS). The simplicity of SAU makes it scalable and compatible with complex function approximators such as neural networks. Theoretically, the authors showed that SAU asymptotically approximates TS for Bernoulli multi-armed bandits. Empirically, SAU-based exploration outperformed TS in both linear and neural contextual bandits.     ", "questions": "", "limitations": "", "rating": 5, "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": "Although a lot of effort has been made in the literature to learn and approximate Bayesian posterior, this paper proposes a simple yet effective frequentist approach for uncertainty estimate and efficient exploration, which does not require maintaining a posterior distribution. The approach is tractable and scales well for problems that require flexible generalization with neural networks. Claims in the paper are appropriately supported by theoretical analysis and empirical results, and the overall paper is well-written and well-organized. \n\nThe experiments show that the SAU-based exploration is quite promising for contextual bandits. However, my major concerns with the current version are (a) the baselines did not include more recent developments in the related field and (b) methods have not been compared on environments that require sophisticated exploration. Please see detailed comments below. \n\n(a)\tBaselines: Hypermodels [1] and NeuralUCB [2] are recently proposed methods for efficient exploration in bandits, which have not been discussed in the current paper. I wonder how well SAU would perform compared to, for example, linear-hypermodel [1] or NeuralUCB [2]. Computational comparison is also welcomed.  \n\n(b)\tEnvironment(s): I am interested to see how well SAU can perform against baselines on environments that require efficient exploration. The WHEEL bandit problem introduced in [3] can be a good example. With different difficulty settings $\\delta$, we can better gauge the effectiveness and limit of SAU-based exploration.         \n\n(c)\tSensitivity analysis: if mini-batches are used for model training, does the performance vary when the number of batches changes? Does the size of the data buffer matter? Finite buffer vs. infinite buffer (that includes all observed data)? \n\n(d)\tProposition 3 (line 160-162): the direction of inequality inside Pr{$\\cdot$} seems incorrect. Should be $\\geq$ instead of $\\leq$? Please check.  \n\n(e)\tSynthetic datasets: in Section 4.3, SAU-UCB seems to be consistently better than SAU- Sampling. Any thoughts on why this might be the case? What would happen if both K and p keep increasing? e.g. K = 20, p = 100  \n\nI am willing to adjust my evaluation should the above issues be addressed and fully discussed.    \n\nRef.:\n\n[1] Dwaracherla, Vikranth, Xiuyuan Lu, Morteza Ibrahimi, Ian Osband, Zheng Wen, and Benjamin Van Roy. \"Hypermodels for exploration.\" arXiv preprint arXiv:2006.07464 (2020).\n\n[2] Zhou, Dongruo, Lihong Li, and Quanquan Gu. \"Neural contextual bandits with ucb-based exploration.\" In International Conference on Machine Learning, pp. 11492-11502. PMLR, 2020.\n\n[3] Riquelme, Carlos, George Tucker, and Jasper Snoek. \"Deep bayesian bandits showdown.\" In International conference on learning representations. 2018. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have discussed limitations and potential negative social impact of their work. However, mitigation strategies for negative impact were not fully discussed.   ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "a5kLWwXWVcE", "reviewer": "Reviewer_opYp", "summary": "### Summary\n\n(+) Simplicity!\n\n(+) Formal justification and guarantees of the approach in two popular bandit settings\n\n(+) The experiments on the bandit benchmark from [18] are convincing. I think it is meaningful to first consider and understand the bandit setting before the RL setting.\n\n(+/-) The paper is overall well written and clear, except for some technical sections where I found the exposition confusing (see below)\n\n(-) In my opinion, an important weakness appears to be the clear positioning of the paper in the light of previous research (see details below). The approach---which seems very similar to maximum likelihood + using the residual variance to drive exploration---should be better connected to previous work and the claimed contributions revised accordingly (perhaps only the evaluation and theoretical guarantees are novel?)\n", "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": "### Detailed comments\n\n* The paper could explain more why it focuses on the instantaneous regret as opposed to the cumulative regret.\n\n* I am a bit confused by the derivations in Sec. 3.1.: (a) Are the {r_n}\\_{n in T_a} assumed to be independently distributed?  (b) For the expression of sigma^2_{n, a}, is the expectation with respect to distribution of rewards conditional on a_n=a? (c) How does the sequence of estimators {hat{theta}_{n,a}}\\_{n in T_a} relate to theta_a, in particular to ensure that tau^2_a is an unbiased estimator?\n\n* Is tau^2_a meant to capture the aleatoric uncertainty or the epistemic uncertainty? It seems to me that this is the former since its definition corresponds to the residual variance.\n\n* I am under the impression that the proposed scheme corresponds to using the maximum-likelihood estimators (MLE)  (for a Gaussian likelihood  r | x, a ~ N(mu(x, theta_a), sigma^2_a)) of both the mean and the variance (we could even further simplify the reasoning by assuming that we store all the contexts so that the sample mean and variance could be evaluated at a single estimator hat{theta}_a per action a).\nUsing such a residual variance (i.e., more related to the aleatoric uncertainty) to drive exploration has been already proposed, e.g., [A] for Bayesian optimization (see their Sec. 4.1 that corresponds to SAU-Sampling) and [B] (when they reduce to a single ensemble member; see Fig. 1, second plot from the left)---Those two references are recent, there must be earlier ones.\nI would therefore suggest to better connect the proposed formalism with previous works and MLE, and clearly state what the novel contributions are (e.g., the theoretical analysis?)\n\n* In both Proposition 1 and 2, it would be helpful to specify with respect to which random variables the expectations are taken.\n\n* “...meaning that contexts should be ‘homogeneous’ to a certain extent.”: If we were to assume a random design setting with x_n distributed according to some Gaussian distribution, what would be the probability of the assumption in Proposition 4 to hold?\n\n* In Sec. 4.2., it seems that the proposed estimator (line 172) requires for all actions a, n_a > p in order to guarantee the existence of sum_j x_j x_j^T; is that the case?\n\n\n* In Sec. 4.3, why aren't UCB and UCB-diag (based on the linear model, like TS) part of the  comparison?\n\n* I would like to better understand what the effect is of computing the sample mean and variance for different estimators at each time step. An ablation could be run in which the triplets (r, a, x) are all recorded so that the sample mean and variance could be computed at a single (i.e., the latest) estimator.\n\n* (I only skimmed through the proofs in the appendix and they look technically sound)\n\n\n### Minor\n\n* “...of the the action…” → remove “the”\n\n* If space is not a concern, “ACT” could be replaced by the more readable “ACTION”\n\n### References\n\n[A] Salinas et al., A Quantile-based Approach for Hyperparameter Transfer Learning (https://arxiv.org/pdf/1909.13595.pdf)\n\n[B] Lakshminarayanan et al., Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles (https://papers.nips.cc/paper/2017/file/9ef2ed4b7fd2c810847ffa5fa85bce38-Paper.pdf)\n\n\n### UPDATE POST REBUTTAL\n\nI have gone through the reviews and the replies of the authors, whom I would like to thank.\n\nMost of my concerns/questions have been clarified, e.g., \n* The positioning with respect to previous research and maximum likelihood estimators is clearer. And I assume the authors would add the related discussion in their final version of the paper.\n* Absence of UCB in the comparison of Sec. 4.3.\n* Derivations in Sec. 3.1.\n\nWhile those clarifications were leading me to increase my score further, the discussion with the other reviewers made me realise that I had overlooked the important missing baselines (e.g., NeuralUCB (Zhou et al. 2020)/NeuralTS (Zhang et al. 2021)) and the partial theoretical analysis. The combined (i) partial theoretical analysis together with (ii) the partial experimental comparisons are leading me to keep my score. The only weakness (i) would have been acceptable provided a stronger experimental comparison.  \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequately addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "YmY8unOSoOG", "reviewer": "Reviewer_R6yL", "summary": "This paper introduces a simple exploration strategy called Sample Average Uncertainty (SAU) for contextual bandit problems. It estimates the mean and variance of the reward distribution for different actions, where the estimate of the mean is given by a parametric function that is trained on experience while the estimate of the variance is a simple sample average of the residuals between observed and predicted rewards for each action. It then defines a UCB-like objective and a sampling based objective to transform these predictions into actions, taking into account the exploration/exploitation trade-off. This sampling strategy is analysed theoretically and evaluated empirically, where the results demonstrate the benefit of SAU in terms of achieving lower cumulative regret than baselines.\n\nThis is not my main area of expertise and I did not go through all the math in detail, so it is difficult for me to assess the novelty as I am unfamiliar with directly related work. However, it seems to me that the paper presents a simple and useful strategy that is effective in addressing the exploration/exploitation trade-off for contextual bandits. Given the importance of the general exploration/exploitation problem and the simplicity of the approach, this paper may contain more generally useful ideas and therefore my evaluation is that the paper could be accepted.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "**Originality**\nThe paper presents a simple idea but I am not familiar enough with related literature to completely assess the novelty. In this respect, it would be helpful if the paper would include a more structured discussion of related work, which is a bit scattered through the paper and not discussed in much detail.\n\n**Quality**\nThe proposed methods are principled and well motivated and I cannot spot any obvious flaws. The claims made by the paper are supported by the empirical results. Overall, I think this paper is of good quality.\n\n**Clarity**\nThe overall idea of the paper was very clear and easy to understand. If the main goal of the paper is to present a practical method, then I think some of the math heavy analysis could be deferred to smooth the overall flow of the paper, but it does not really bother either.  The pseudocodes are very helpful for understanding how to actually implement the proposed strategy and see the relation to e.g. Thompson Sampling.\n\n**Significance**\nThe exploration-exploitation trade-off is important and the paper presents a simple and effective strategy to address this. As variants of baselines such as UCB are widely used, the ideas presented in this paper may be of interest to a wider audience.\n\n**Questions**\nDo I understand correctly that there is an implicit assumption that the variance does not depend on the context. What is the implication of this assumption? Could we (like the mean) also use a parametric estimate of the variance that does depend on context?\nIs the term (log n)/n_a in the SAU-UCB necessary? As the variance of the mean already decreases as n_a increases (since tau_a^2 = S_a^2/n_a), can't we just use something like \\tilde{u}_n,a = \\hat{u}_n,a + 2 \\tau (standard confidence interval UB).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Obvious limitations are adequately discussed in the discussion section, although I would find it helpful to discuss the implications/limitations of the implicit assumption that the variance does not depend on the context.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not see any direct ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Two reviewers recommended acceptance of the paper (1x weak accept, 1xaccept) and two reviewers recommended (weak) rejection of the paper. The most positive review had low confidence and I downweighed it when comming to a final decision for the paper. The reviewers acknowledged the simple and efficient proposed exploration approach but also raised concerns regarding completeness of the theoretical analysis and the presented empirical evaluation. While a more complete theoretical analysis was not deemed crucial for accpetance of the paper, the missing baselines make it impossible to fully (empirically) understand the value of the proposed approached. The authors commented on this issue but did not provide an empirical comparison but rather highlighted (only) the theoretical differences. I am therefore recommending rejection of the paper but at the same time would like to encourage the authors to improve their paper according to the reviewers' suggestions and in particular work on the empirical comparison of the proposed approach to recently proposed algorithms in the field.
Decision: Accept (Poster)