Stochastic Multi-Armed Bandits with Control Variates
Authors: Arun Verma
Manjesh Kumar Hanawal
Venue: NeurIPS 2021 Poster (2021)
Keywords: Stochastic Multi-Armed Bandits
Variance Reduction
Control Variates

Abstract: This paper studies a new variant of the stochastic multi-armed bandits problem where auxiliary information about the arm rewards is available in the form of control variates. In many applications like queuing and wireless networks, the arm rewards are functions of some exogenous variables. The mean values of these variables are known a priori from historical data and can be used as control variates.  Leveraging the theory of control variates, we obtain mean estimates with smaller variance and tighter confidence bounds. We develop an upper confidence bound based algorithm named UCB-CV and characterize the regret bounds in terms of the correlation between rewards and control variates when they follow a multivariate normal distribution. We also extend UCB-CV to other distributions using resampling methods like Jackknifing and Splitting. Experiments on synthetic problem instances validate performance guarantees of the proposed algorithms.



Stochastic Multi-Armed Bandits with Control Variates
Arun Verma
Manjesh Hanawal Department of IEOR IIT Bombay, Mumbai, India Mhanawa@@itbb ac. in
Department of Computer Science National University of Singapore arun@comp. mus edu. sg
Abstract
This paper studies a new variant of the stochastic multi-armes bandits problem where auxiliary information about the arm rewards is available in the form control variates. In many applications like queuing and wireless networks, the arm rewards are functions of some exogenous variables. The mean values these variables are known a priori from historical data and can be used control variates. Leveraging the theory of control variates, we obtain mean estimates with smaller variance and tighter confidence bounds. We develop upper confidence bound based algorithm named UCB-CV and characterize the regret bounds terms of the correlation between rewards and control variates when they follow a multivariate normal distribution. We also extend UCB-CV to other distributions using resampling methods like Jackknifing and Splitting. Experiments synthetic problem instances validate performance guarantees of the proposed algorithms.
Introduction
Stochastic Multi-Armed Bandits (MAB) setting has been extensively used study decision making under uncertainty (Thompson, 1933; Bubeck et al., 2012; Lattimore and Szepesvári, 2020). In the classical setting, is assumed that the arm rewards are independent of each other. After playing arm, the learner observers independent and identically distributed reward samples. The exploration versus exploitation trade-off is fundamental problem in the bandits setting, and learner can accumulate more rewards if it is balanced well. A better balance can be achieved the learner can estimate arm's 's mean rewards with tighter confidence bounds (Auer et al., 2002; Auer and Ortner, 2010; Garivier and Cappé, 2011) 1) and smaller variance (Audibert et al., 2009b; Mukherjee et al., 2018). Any available side auxiliary information can aid in building tighter confidence bounds. In this paper, we study the improvement in the performance that can be achieved when side information available in the form of control variates.
Any observable input that is correlated with the random variable of interest can be a Control Variate (CV). When the mean of the CV is known, it becomes useful to reduce the variance of the mean estimator of the random variable. CV method is a popular variance reduction technique to improve the estimates' precision without altering the simulation runs of samples (Lavenberg et al., 1982). Many stochastic simulations involve inputs generated using known distributions. These inputs can be potential CVs output could be correlated with them. has motivated the development of rich theory to analyze the quality of the estimators resulting from CVs (Lavenberg and Welch. 1981: Lavenberg al., 1982; Nelson. 1990). We adopt these techniques to study the stochastic multi-armed bandits problem when CVs are available for the arms.
increase the number
In many real-life applications, exogenous variables influence arms' rewards and example, consider job aggregating platform that assigns jobs to one of the servers/workers in each slot. The jobs are of variable size, and the time serve them depends on their size and other
CVs. For
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

unknown extraneous factors. The platform observes the size of each job and knows their mean value from historical data. The random job sizes correlate with service times and can be used as a CV to estimate each server's 's mean service time. Another example is a wireless system where a transmitter can transmit packets on a channel in each slot. Successful transmission of the packets (quality) depends on random quantities like fading, interference, and channel noise on the selected channel. The transmitter can observe the fading value using pilot signals in each round and know their mean value from past observations. These fading values on channel can be used as CV to estimate the channel's s quality.
The performance of a MAB algorithm depends on how good is the confidence interval of its mean reward estimators (Auer al.. 2002; Auer and Ortner, 2010; Garivier and Cappé. 2011). The tightness of these intervals depends on the variance of the estimators (Audibert et al., 2009b; Mukherjee et al., 2018). Naturally, estimators with smaller variance for the same number of samples result in better performance. Thus CVs can be leveraged to improve the performance of bandits algorithms with smaller confidence intervals. The reduction depends on how strongly the reward samples and associated CVs are correlated.
Linear methods are widely used for variance reduction using CVs where the new samples are generated taking the weighted sum of reward samples and centered CV samples. Then these new samples are used for the estimation of the mean rewards. The choice of the weight that results in maximum variance reduction depends on the variance of CV and its correlation with reward samples. In practice, both of these quantities are unknown and need to be estimated from the observed samples. However, using the estimated weight makes the new samples highly correlated and makes the analysis of confidence intervals challenging.
For multivariate normal distributions, tight confidence intervals can be constructed that hold with high probability for the mean reward estimators resulting from the linear control variates. Using these results, we develop a MAB algorithm that exploits CVs to improve the regret performance. For general distributions, we discuss resampling methods that result in unbiased estimators with better confidence intervals. Specifically, our contributions are as follows:
For the case where rewards and CVs are normally distributed, we develop an algorithm named Upper Confidence Bounds with Control Variates (UCB-CV) that uses the estimators based on the linear control variates.
In Section 4, we show that the regret of UCB-CV is smaller by a factor (1 - p2) compared to the existing algorithms when the rewards and CV have a multivariate normal distribution. where is the correlation coefficient of the reward and control variates.
In Section 5, we discuss how to adapt UCB-CV for the general distributions using estimators and associated confidence intervals based on jackknifing, splitting, and batching methods.
We validate the performance of UCB-CV on synthetically generated data in Section 6.
1.1 Related Work
Our work uses side or auxiliary information available in the form of CVs to improve the variance of estimates. In the following, we discuss works that incorporate variance estimates and/or side information to improve the performance of multi-armed bandits algorithms.
Incorporating variance estimates: Many stochastic multi-armed bandits algorithms like UCB1 (Auer et al., 2002), DMED (Honda and Takemura, 2010), KL-UCB (Garivier and Cappé, 201 1), Thompson Sampling (Chapelle and Li, 2011; Agrawal and Goyal, 2012; Kaufmann et al., 2012; Agrawal and Goyal, 2013), assume that the rewards are bounded on some interval [0, b] and define index of each arm based on its estimates of the mean rewards and ignore the variance estimates. The regret of these algorithms have optimal logarithmic bound in the number of rounds (T'), and grows quadratic in b, i.e., ( A log T). where A is the smallest sub-optimality gap. UCB1-NORMA by (Auer al., 2002) uses the variance estimates in the index of the arms and when rewards are Gaussian with variance o², to achieve regret is of order ((o² / log T). This bound is even better than that of UCBI when the variance is smaller than b2 even though it has considered unbounded support. Further, the authors experimentally demonstrate that the UCB-Tuned algorithm (Auer et al., 2002), which uses variance estimates in arm indices, significantly improves regret performance over UCB1 I when rewards are bounded. Extending the idea of using 'variance aware' indices, UCBV

---

(Audibert et al., 2009b) algorithm achieves regret of order ( 26) Iog T)) thus confirming that making algorithms variance aware is beneficial. EUCBV (Mukherjee et al., 2018) improves the performance of UCBV using an arm elimination strategy like used in UCB-Improved (Auer and Ortner, 2010).
Incorporating side information: In the applications like advertising and web search, whether or users like a displayed item could depend on their profile. Users' profile is often available to the platform, which could then be used as side information. Contextual bandits (Dani et al., 2008; Rusmevichientong and Tsitsiklis, 2010; Li al., 2010; Filippi al., 2010; Abbasi- Yadkori al., 2011; Chu et al., 2011; Li et al., 2017; Jun et al., 2017; Zhang et al., 2016) and MAB with covariates (Perchet and Rigollet, 2013) exploit such side information learn the optimal arm. They assume correlation structure (linearity, GLM, etc.) between mean reward and context where mean reward varies with side-information (context).
In contrast to contextual bandits, mean rewards do not vary in our unstructured setup with side information available in the form of CVs. We do use CVs directly decide which arm to select in each round but use them only to get better estimates of the mean rewards by exploiting their correlation with rewards. Our motivating examples from jobs scheduling and communication networks capture these unstructured bandits where CVs provide information about the rewards but do not alter their mean values.
Our confidence bounds for mean reward estimators are based on the variance of estimators rather than on the variance of the reward sample, as the case in UCBV (Audibert et al., 2009a) and EUCBV (Mukherjee et al., 2018). The samples that we use to estimate mean rewards are not independent and identically distributed. Hence, we can not the standard Bernstein inequality get confidence bounds on mean and variance estimates.
CVs are used extensively for variance reduction (James, 1985; Botev and Ridder, 2014; Chen and Ghahramani, 2016; Kreutzer et al., 2017; Vlassis et al., 2019) in the Monte-Carlo simulation of complex systems (Lavenberg and Welch, 1981; Lavenberg et al., 1982; Nelson, 1989, 1990). To the best of our knowledge, our work is the first to analyze the performance of stochastic bandits algorithms with control variates.
2 Control Variate for Variance Reduction
Let be the unknown quantity that needs to be estimated, and X be an unbiased estimator of i... E [X] = μ.. A random variable W with known expectation (w) a CV if it correlated with X. Linear control methods use errors in estimates of known random variables to reduce error in the estimation of unknown random variable. For any choice of coefficient B8, define a new estimator
as X = X + B(w W). It is straightforward to verify that its variance is given by
Var( X) Var(X) + Var(WW) 2,3Cov W).
and it is minimized by setting ,3 to
3* Cov(X, W)
Var(W)
The minimum value of the variance is given by Var(X] = (1 - p²) Var(X), where p is the correlation coefficient of X and W. Larger the correlation, the greater the variance reduction achieved by the CV. In practice, the values of (X, W) and Var(W) are unknown and need to be estimated to compute the best approximation for 3*.
3 Problem Setting
We consider stochastic multi-armed bandits problem with K arms. The set of arms is represented by [K] (1.2..... K}. round t,, the environment generates a vector (Xe.avvef (e)))- The random variable X,,; denotes the reward of arm i in round t, and form an Independent and Identically Distributed (IID) sequence drawn from an unknown but fixed distribution with mean μi; and variance of. The random variable W,, is the Control Variate (CV) associated with the reward of arm i in round These random variables are drawn from an unknown but fixed distribution with mean W, and variance o2 and form an IID sequence. The learner knows the values {wy be[[]] but
3

---

not the i The correlation coefficient between rewards and associated control variates of an arm is denoted by Pt.
In our setup, the learner observes the reward and associated CVs from the selected arm. We refer to this new variant of the multi-armed bandits problem as Multi-Armed Bandits with Control Variates (MAB-CV). The parameter vectors μrº { of [[ w = {wi, He(K]) and = (PstEejk] identify an instance of MAB-CV problem, which we denote henceforth using P = (μr ,w,, p). The collections of all MAB-CV problems are denoted by P. For problem instance P P with mean reward vector μ4, we denote the optimal arm as i* argmax H4.
[E|K]
MAB-CV problem with instance (nr w P)
For round t:
Environment generates a vector Xt (Xta...., X(,K) R and W. (Wi.1...., Wi,k) RK where E [X1,s] pt, Var(X of. [[W W/. Var(W,,) = w. and the sequence (N2,))e21 and (War)21 are IID for all E [K].
2. Learner selects an arm 4. E [K] based on past observation of rewards and CVs samples from the arms till round 1.
3. Feedback and Regret: The learner observes random reward Xt,, and associated CV Wt, and then incurs penalty (14-- p1.).
Let 4, denote the arm selected by the learner in round t based on the observation of past reward and control variate samples. The interaction between the environment and a learner is given in MAB-CV problem. We aim to learn policies that accumulate maximum reward and measure its performance by comparing its cumulative reward with that of Oracle that plays the optimal arm in each round. Specifically, we measure the performance in terms of regret defined as follows:
Ry Ty4- E
Σ X
Note that maximizing the mean cumulative reward of policy is the same as minimizing the policy's regret. A good policy should have sub-linear expected regret, i.e., R - 0 as T + co.
Our goal is to learn policy that is sub-linear with small regret. To this effect, we use CVs to estimate mean rewards with sharper confidence bounds so that the learner can have a better exploration-explootttion trade-off and start playing the optimal arm more frequently early.
4 Arms with Normally Distributed Rewards and Control Variates
We first focus on the case where the rewards and associated CVs of arms have a multivariate normal distribution. We discuss the general distributions the next section. To bring out the main ideas of the algorithm, we first consider the case where each arm is associated with only one CV. Motivated by the linear CV technique discussed in the previous section, we consider a new sample for an arm in round t as follows:
= =
+ (w; - W.,),
where Xt,; is the tth reward, Wt, is the 7hh associated control variate with an arm i, w = E [W..]] and 3: = Cov(Xr,,, ( (ar////r(W..))) Using s such samples, the mean reward for an arm is defined as A = (Ei x/s)/s. Let Aa.a = E X,,; and Wa.i = = Ee W denote the sample mean of reward and CVs of arm from samples. Then fi,; can be written as follows:
p io. + P7,((u -.,,)-
(3)
Since the value of Cov(X, W,) and Var(W,) are unknown, the optimal coefficient 8 need to be estimated. After having samples, it is estimated as below and used in Eq. (3).
8r Ei=1(x, (W..) wi)
(4)
Ei= (W,, w;)2

---

When the variance of CV is known, it can be directly used to estimate 5 by replacing estimated variance by actual variance of CV in the denominator of Eq. (4), ie., replacing > (W,, wx)2/(s 1) by w After observing reward and associated control variates for arm the value of 3 is re-estimated. The value of 3 depends on all observed rewards and associated control variates from arm i. Since all X,, uses same Bř, this leads correlation between the X., observations.
Let (X) = 2., denote the variance of the linear CV samples and s, Var (A))) denote the variance the estimator using these samples. Since the mean reward estimator (fS, is computed using the correlated samples, we cannot use Bernstein inequality to get confidence bounds on mean reward estimates. However, when the rewards and CVs follow a multivariate normal distribution, the following results tell how to obtain an unbiased variance estimator and confidence interval for i=
Lemma 1. Let the reward and control variate of each arm have multivariate normal distribution. After observing samples of reward and control variate from arm i, define U=,5 (
where
Zu,i 1 1 1 (W w;))² and 62.(()) s- E( p,, (W,,, E E w;)2
then Da is an unbiased variance estimator of Pggy i.e. E[va,d = Var((a
The confidence interval for reward estimator given by our next result. Lemma 2. Let the conditions in Lemma 1 hold and s be the number of reward and associated control
variate samples from arm i in round t. Then
P pes - mil 16:--11:2
v((a VDsd S 2/1t"
v-aa) where Vi, denote 100(1 - yh percentile value of the t- distribbbttion with - 2 degrees of freedom and Da.s is an unbiased estimator for variance of p..:
We prove Lemma I and Lemma 2 using regression theory and control theory results (Nelson, 1990). The detailed proofs are given in Appendix B. The proof uses the fact that the arm's 's rewards and CVs have multivariate normal distribution. Therefore, we use t-distribution for designing confidence intervals of mean reward estimators. Analogous to the Hoeffding inequality, this result shows that the probability of the estimate obtained by samples } deviating from the true mean of arm decays fast. Further, the deviation factor v((a) VDs.i depends on the variance of the estimator (A%.,) which guarantees sharper confidence intervals. As we will see later in Lemma 3, these confidence terms are smaller by a factor (1 - pt) compared to the case when no CVs are used. Equipped with these results, we next develop a Upper Confidence Bound (UCB) based algorithm for the MAB-CV problem.
4.1 Algorithm: UCB-CV
Let (t) be the number of times the arm i is selected by a learner until round and (N), be the unbiased sample variance of mean reward estimator (1)).))).)) for arm i. Motivated from Lemma 2, we define optimistic upper bound for mean reward estimate of arm as follows:
UCB = =AN VON PNNa),.
(5)
Using above values as UCB indices of arms, we develop algorithm named UCB-CV for the MAB-CV problem. The algorithm works as follows: takes the number of arms K, a constant Q = 3 (number of CV per arm + 2), and > 1 (trades-off between exploration and exploitation) as input. Each arm is played Q times to ensure the sample variance for observations (+), can be computed (see Lemma 1).
In round t, UCB-CV computes the upper confidence bound of each arm't 's mean reward estimate using Eq. (5) and selects the arm having highest upper confidence bound value. We denote the selected arm by It. After playing arm It, the reward Xt,I. and associated control variate W.,, are observed. After that, the value of Nr, (t) is updated and 3%,, te PN,,(0... and D1, (1) are re-estimated. The same process is repeated for the subsequent rounds.
5

---

UCB-CV UCB based Algorithm for MAB-CV problem
1: Input: K, Q, >
2: Play each arm E [K] Q times
3: for t = QK + 1, QK 22 ..... do
4: Vi E [ compute L as given in Eq. (5)
5: Select 4 arg max i
UCB
6: Play arm 4 and observe Xt,,, and associated control variates Wt,,.- Increment the value of N1, (f) by one and re-estimate (N,,00 (N,1, and (t)
7: end for
4.2 Estimator with Multiple Control Variates
In some applications, it could be possible that each arm is associated with multiple CVs. We denote the number of CVs with each arm as q. Let Wr,,,j the 1rh control variate arm i that is observed in round L, Then the unbiased mean reward estimator for arm i with associated CVs is given by
P9... Ns,i G (wo w.,s);
where 3 = -B.1. (8.1....,B.....
Bi.)) " w. = (1i,1, (wi,1,,...,..ppp win) and W.si = (............. (..i.a))
Let be the number of rewards and associated CVs samples for arm é, W, be the q matrix whose 7hth row is (Wr..1. Wr..2..... W,,.,g), and X; = (X1.s..., X.,)) T. By extending the arguments used in Eq. (4) to q control variates, the estimated coefficient vector is given by
3 = (W; W. , -
(W? X; - (A..s).
We can generalize Lemma and Lemma for the MAB-CV problems with q control variates and then use UCB-CV with Q g + 2 and appropriate optimistic upper bound for multiple control variate case. More details can be found in Appendix C.
4.3 Analysis of UCB-CV
In our next result, we describe the property of our estimator that control variates. This result is derived from the standard results of control variates theory (Nelson, 1990).
Lemma 3. Let reward and control variates have a multivariate normal distribution and be the number of control variates. Then after having observations of rewards and associated control variates from arm i,
E [AS. = 14i and Var(
5 -
Var((s))))
s 9-9-2
where pf = d..w, Ew w. o /o? is the square of the multiple correlation coefficint,, o? Var( and ox.w, = (Cov(X,, Wi,).... Cov(X,, Weg)).
The following our main result which gives the regret upper bound of UCB-CV. The detailed analysis is given in Appendix D.
Theorem 1. Let the conditions in Lemma 3 hold, = 2, A; p4- pu be the sub-optimality gup for arm i E [K. and (T) ) be the number of times sub-optimal arm selected T rounds. Let
27
Cr
E
- N(T)-9-2
for all i. Then the regret of UCB-CV in T rounds is upper
bounded by
A(V....))
Pr -1 p3)03
A
2.)
Ry
Σ
A,

---

Note that a is hyper- parametere to trade-ofi off between exploration and exploitation. UCB-CV works as long as a >> 1 and the effect of a on the regret bound through the term Σi=1 This term has a nice closed form value of x² x²/ /6 for a Hence, we state the results with a and use in the experiments as well.
Remark 1. Unfortunately, we cannot directly compare our bound with that of UCB based stochastic MAB algorithms like UCBI-NORMAL and UCBV as V do not have closed-form expression. (2) denotes y percentile of t-distribution with T - degrees of freedom.
TIT, increases in (see Fig. Ia for small value Tf and Fig. 1b for large value of T). However, this does not imply that the overall regret increases in q p3 also increases in q- Hence dependency of regret q is delicate. It is also observed in Nelson (1989) that having more CVs does not mean better variance reduction. One can empirically verify that (V (2) T.T.ql ) is upper bounded by 3.726 log T. This upper bound holds for all as long as T 2 q max 0.7g)
Remark 2. As the degrees of freedom decreases in q. V
20
(4 J..PPwi where T> 7050
Waete where M(T x
q=1
where T>
q=2
g=1
Q-3
16
==10
(V42) []
9-10
20
q=20
3.726loo(1)
20
3.726 1 log(()
0.25
1.00
50
100
150
200
MXTI
(a) 2,2,g 1 726 (T) for small
(b) T.
(v ) ex 3.772 (T) for large T.
(c) Viriaton in
2.N (T). with N.(T).
Figure Properties of (Vi22.2² and (2
/
T. 1.1.9
Remark is hard bound CTá,g as V TT:. does have explicit form. However, Cr,ig tends to I aas T D0. Indeed, from lower bound argument, we know that N,(T) > oc as T > oc and hence
> (confidence interval shrink with more samples) as shown in v(2) TTN.TTY
N.(T)-2 > 1 Lndd N((T)-q-2
Via
Fig. Ic. However, under some assumptions, we can obtain a bound empirically. Specifically, if $ 20
(
and N:(T) > 50, then
N -(T))--- S 1.72 and from I-distribution tables, we gel "TNNCTT S 1.5
V-2
(see Fig. 1c), hence the bound CT,i I 4. We can guarantee N((T) 50 by playing each arm 50 times at the beginning. Therefore, we can obtain one possible explicit bound in Lemma (6) by replacing Crig with 4. However, for general case, explicit bound in Lemma 8 is hard.
General Distribution
We consider the general case with no distributional assumptions reward and associated CVs of arms. The samples X, resulting from the linear combination of rewards and CVs are dependent but need not be normally distributed. Hence f..., need not remain unbiased estimator. Therefore, we cannot use the (-distribution properties to obtain confidence intervals. However, use resampling methods such as jackknifing, splitting, and batching reduce the bias of the estimators and develop confidence intervals that hold approximately or asymptotically. These confidence intervals can then be used to defined indices for the arms. Below we briefly discuss these methods.
5.1 Jackknifing
In statistics, jackknifing is a well-known re-sampling technique for variance and bias estimation (Efron, 1982: Efron and Gong, 1983). We start with classical presentation of jackknifing for CVs
7

---

(Lavenberg et al., 1982). Let P...yy be the estimate of the mean reward that is computed without sample x. The Vja.g = spa.i. - (s - 1) which is sometimes called the j vecudo-value... Using pseudo-values mean reward estimation given as Pesiig : Ei Yl and its sample variance fnd
is /2 s,i. (s(s - 1)) - 7] when reward variance is bounded. Further, H + la/2(n 1) is a asymptotically valid confidence interval (Avramidis et al., 1991) and holds approximately for finite number of samples.
- j.i. "s.igg) Ps.ig is shown to be unbiased (Nelson, [Thm)
5.2 Splitting
Splitting is a technique to split the correlated observations into two or more groups, compute an estimate of [ from each group, then exchange the estimates among the groups. Nelson (1990) considers an extreme form of splitting, where he splits observations into groups. The j"h observation is given by
V-S j.H. - =
1, x, (w- W,,),, J [s]:
where 3.-² is estimated without jth observation and J, (Wj........ ( ) is the vector of CVs with elements associated with reward X3.- The point estimator for splitting method is Pss.g = - y and its sample variance is isS (s(s 1)) E 2..99 Ma..g ) Then Ma,i. + ( - 1) gives approximate confidence interval (Nelson, 1990).
Below we define UCB index for these methods. Let 0 (1))).5g be the sample variance of mean reward
estimator (Ps,i.g) for arm i. We define the optimistic upper bound for mean reward for G E (J,S)
as follows:
G.GG UCB t,ig 6i.9 (.(0).g (.N.(1). V EG
V.laa
(6)
(1(.)...
where V.G. the 100(1 - 1/t2) percentile value of the distribbuttio with s degrees of freedom. Since the optimistic upper bounds defined in Eq. (6) are valid only asymptotically (Nelson, 1990; Avramidis et al., 1991), cannot be used for any finite time regret guarantee. However the above UCB indices can be used in UCB-CV to get an heuristic algorithm for the general case. We experimentally validate its performance the next section.
Experiments
We empirically evaluate the performance of UCB-CV by comparing it with UCB-CV with UCB1 (Auer et al., 2002), UCB-V (Audibert et al., 2009b), Thompson Sampling (Agrawal and Goyal, 2013), and EUCBV (Mukherjee al., 2018) different synthetically generated problem instances. For all the instance we use we use K = 10, q = 1, and a = 2. All the experiments are repeated 100 times and cumulative regret with 95% confidence interval (the vertical line each curve shows the confidence interval) are shown. Details of each instance are as follows:
Instance 1: The reward and associated CV of this instance have multivariate normal distribution. The reward of each arm has two components. We treated one of the components as CV. In round f, the reward of arm is given as follows:
X = Ve, + We,s
where Ve,; N (Hr,i, (. and W.,- NH 2. Therefore, X,,, (Nu,, + o t We treat W; as CV of X;. It can be easily shown that the correlation coefficient of X; and W; is
/ + o..)). For each i, we set M..; 0.6 (i - 1) 0.05, Par,i = 0.3, for arm
i [K]. The value of o². = 0.1 and of 0.1 for all arms. Note that the problem instance has the same CV for all arms, but all the CVs observations for each arm are maintained separately.
Instance 2: It is the same as the Instance except each arm has a different CV associated with its reward. The mean value of the CV associated with arm i is set as pho.i = 0.8 (i 1) 0.05.
Instance 3: is the same as the Instance except the samples of reward and associated control variate generated from Gamma distribution, where the value of scale is set to 1.
8

---

Instance 4: It is the same as the Instance 2 except the samples of reward and associated control variate are generated from Log-normal distribution with the values of o 1 and o 1 for all arms.
Comparing regret of UCB-CV with existing algorithms The regret different algorithms for Instances 1 and 2 are shown in Figures Fig. 2a and Fig. 2b, respectively. As see UCB-CV outperforms all the algorithms. We observe that Thomson Sampling has large regret for normally distributed reward and CVs. Hence, we have not added regret of Thomson Sampling. Note that UCB-CV does not require a bounded support assumption, which is needed in all other algorithms. The regret of the EUCBV algorithm is closest to UCB-CV but EUCBV can stick with the sub-optimal arm as it uses an arm elimination-bo strategy, which has a small probability climinating the optimal arm.
200
Rounds
Rounds
Rounds
(a) Instance
(b) Instance 2
(c) Varying Correlation Coefficient.
Figure 2: Regret comparison of different multi-armed bandits algorithms with UCB-CV.
Regret of UCB-CV vs Correlation Coefficient Theorem shows that UCB-CV have better regret bounds when correlation between arm rewards and CVs is higher. To validate this we derived problem instances having different correlation coefficients as follows:
Instance 5: Similar to the Instance 1, the reward and associated CVs have multivariate normal distribution with rewards expressed as sum of two components. We set jrr,i = 6.0 (i - 1) * 0.5 and Mw ; 4.0 for arm i [K]. The value of o 1.0 and a 1.0 for all arms. The problem instance has common CV for all arms but all the observations are maintained for each arm separately,
As the correlation coefficient of X; and W; is P; = / + o. we varied of over the values {1.0, 1.5., 2.0, 3.0) obtain problem instances with different correlation coefficient. Increasing o² reduces the correlation coefficient of X; and W; We have plotted the regret of UCB-CV for different problem instances. As expected, we observe that the regret decreases as the correlation coefficient of reward and its associated control variates increases shown in Fig. 2c.
Performance of Jackknifing, Splitting, and Batching Methods We compare the regret of UCB-CV with Jackknifing. Splitting and Batching (see Appendix E for more details) methods. The regret of the batching method is worse for all the instances. Whereas, the jackknifing and splitting are performing well for heavy-tailes distributions (Instance 3) and UCB- CCB-CV performs better for normal distribution (Instance 2) and Log- oon-oomal distribution (Instance 4) shown in Fig. 3.
Jalksal
4500
1002
1209
300
Rounds
Rounds
Rouncs
(a) Instance 2
(b) Instance
(c) Instance 4.
Figure 3: Comparing regret of UCB-CV with Jackknifing, Splitting, and Batching method based.

---

Regret of UCB-CV vs Estimated Mean of CV Our work has demonstrated the applicability of CVs to bandit theory. To establish the gains analytically, we have to assume that mean of the CVs is known. However, it is not unreasonable as the mean of CVs can be constructed such that its mean value is known (see Eq. (7) and Eq. (8) of Kreutzer et al. (2017)). If the mean of CV is unknown, we estimate it from the samples, but using the estimated/approximate
means can deteriorate the performance of the proposed algorithm.ss Though the theory of control variate is well developed for known mean, and only empirical studies are available to the case when the CV means are known approximately (Schmeiser et al., 2001; Pasupathy et al., 2012).
To know the effect of approximation error (E) in the mean estimation of CVs, we run an experiment with Instance Instance 2, and Instance 5. We assume that the approximated mean of CVs given by w; + E. We observe that the regret of UCB-CV increases with an increase in approximation error. UCB-CV can even start performing poorly than the existing state-of-the-an algorithm for significant large approximation errors as shown in Fig. 4. Since the maximum and minimum reward gap can be more than one for the Instance 5, we must multiply confidence intervals of UCB1, UCB-V V, and EUCBV with the appropriate factor (used 6 for the experiment) for fair comparison. We also observe that Thompson Sampling has almost linear regret for the Instance 5. We believe that it is due to the high variance of arms' rewards that leads to overlapping of rewards distributions.
(OS-CVIew31 L05.0//ved)
LOk -11
10% 2
3000
2040
2000
400
900
1000
200
2009
4000
500
90
3006
-500
2000
2500
300
(a) Instance
(b) Instance
(c) Instance
Figure 4: Regret comparison of UCB-CV with varying approximation error in the mean estimation of control variates and different multi-armed bandits algorithms.
Our experimental results demonstrate that as long as the error in the estimation of the mean of CVs is within a limit, there will be advantage using control variates. The impact of such approximations in bandits needs to be analyzed extensively and demands independent work.
Conclusion
In this work, we studied stochastic multi-armed bandits problem with side information available in the form of Control Variate (CV). Leveraging the linear control variates' variance reduction properties, we developed variant of the UCB algorithm named UCB-CV. When reward and CVs have a multivariate normal distribution, we showed that the regret of UCB-CV, which is of the order O1 /²) log T)) where o² is the maximum variance of arm rewards and p is the minimum correlation between the arm rewards and CVs. As expected, our the bounds showed that when the correlation is strong, one can get significant improvement in regret performance. For the case where the reward and control variates follow a general distribution, we discussed Jackknifing and splitting resampling that will give estimators with smaller bias and sharper confidence bounds.
The variance reduction techniques based on CVs assume that the exact mean of the CVs are known. In practice, only some rough estimates of the mean of CVs rather than the exact values may be available. would be interesting to study how does it affect the performance of the bandit algorithms. Another interesting direction to study how CVs are helpful if one has to rank the arms instead of just finding the tap-ranked arm.
Acknowledgements
Manjesh K. Hanawal is supported by INSPIRE faculty fellowship from DST and Early Career Research Award (ECR/201 (ECR/2018/00295)) from SERB, Govt. of India. This work was done when Arun Verma was at IIT Bombay.
10

---

References
Yasin Yadkor,, Dávid Päl, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
Shipra Agrawal and Navin Goyal, Analysis of thompson sampling for the multi-armed bandit problem. In Conference on Learning Theory, pages 39-1, 2012.
Shipra Agrawal and Navin Goyal. Further optimal regret bounds for thompson sampling. In Artificial intelligence and statistics, pages 99-107, 2013.
Jean-Y Yves Audibert, Rémi Munos, and Csaba Szepesvári. aoploratioo-ccploiiaaae tradcoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19):1876 1902,
2009a.
Jean-Y Yves Audibert, Rémi Munos, and Csaba Szepesvári. Exploration-xxploitation tradcoff using variance estimates in multi-armes bandits. Theoretical Computer Science, 410(19):187-1192. 2009b.
Peter Auer and Ronald Ortner. Ucb revisited: Improved regret bounds for the stochastic multi-armed bandit problem. Periodica Mathematica Hungarica, 61(1-2):55-66 65, 2010.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, pages 235-256, 2002.
Athanassios N Avramidis, Kenneth W Bauer Jr, and James R Wilson. Simulation of stochastic activity networks using path control variates. Naval Research Logisties (NRL). 3822)1833-01,, 1991.
Zdravko Botev and Ad Ridder. Variance reduction. Wiley StatsRef: Statistics Reference Online, pages 1-6, 2014.
Sébastien Bubeck, Nicolo Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends@ Machine Learning, 5(1):1-122, 2012.
Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. In Advances in neural information processing systems, pages 2249-2257, 2011.
Yutian Chen and Zoubin Ghahramani. Scalable discrete sampling multi-armed bandit problem. In International Conference on Machine Learning, pages 2492-2501. PMLR, 2016.
Wei Chu, Lihong Li, Lev Reyzin, and Robert E Schapire. Contextual bandits with linear payoff functions. In International Conference Artificial Intelligence and Statistics, pages 208-214, 2011.
Richard W Conway, Some tactical problems in digital simulation. Management science, 10(1):47-61, 1963.
Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. COLT, pages 355-366, 2008
Bradley Efron. The jackknife, the bootstrap and other resampling plans. SIAM, 1982.
Bradley Efron and Gail Gong. A leisurely look at the bootstrap, the jackknife, and cross-validation. The American Statistician, 37(1):36-48, 1983.
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. Advances in Neural Information Processing Systems, pages 586-594, 2010.
Aurélien Garivier and Olivier Cappé. The kl-ucb algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual Conference On Learning Theory, pages 359-376, 2011.
Hayashi. Econometrics. Princeton University Press, 2000.
Junya Honda and Akimichi Takemura. An asymptotically optimal bandit algorithm for bounded support models. In COLT, pages 67-79, Citeseer, 2010.

---

BAP James. Variance reduction techniques. Journal of the Operational Research Society, 36(6): 525-530, 1985.
Kwang-Sung Jun, Aniruddha Bhargava, Robert Nowak, and Rebecca Willett. Scalable generalized linear bandits: Online computation and hashing. In Advances in Neural Information Processing Systems, pages 99-109, 2017.
Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In International Conference on Algorithmic Learning Theory, pages 199-213. Springer, 2012.
Julia Kreutzer, Artem Sokolov, and Stefan Riezler. Bandit structured prediction for neural sequence-to-seqqeenee learning. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages 1503-1513, 2017.
Tor Lattimore and Csaba Szepesvári. Bandil Algorithms. Cambridge University Press, 2020. doi:
10.1017/978 108571401.
Stephen S Lavenberg and Peter D Welch. A perspective on the use of control variables to increase the efficiency of monte carlo simulations. Management Science, 27(3):322-335, 1981.
Stephen S Lavenberg, Thomas L Moeller, and Peter D Welch. Statistical results on control variables with application queueing network simulation. Operations Research, 30(1):182-200 1982.
Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual-bandit approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web, pages 661-670. ACM, 2010.
Lihong Li, Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In International Conference Machine Learning, pages 2071-20000 2017.
Subhojyoti Mukherjee, KP Naveen, Nandan Sudarsanam, and Balaraman Ravindran. Efficient-ucbv: An almost optimal algorithm using variance estimates. In Proceedings the AAAI Conference Artificial Intelligence, volume 32, 2018.
Barry L Nelson. Batch size effects on the efficiency of control variates in simulation. European Journal of Operational Research, 43(2): (122):144111 84-196, 1989.
Barry Nelson. Control variate remedies. Operations Research, 38(6):974-992, 1990.
Raghu Pasupathy, Bruce W Schmeiser, Michael R Taaffe, and Jin Wang. Control-variate estimation using estimated control means. IIE Transactions, 44(5):381-388 2012.
Vianney Perchet and Philippe Rigollet. The multi-armed bandit problem with covariates. The Annals of Statistics, 41 (22))6933771, 2013.
Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395-411, 2010.
Bruce Schmeiser. Batch size effects in the analysis of simulation output. Operations Research, 30(3): 556-568, 1982.
Bruce W Schmeiser, Michael R Taaffe, and Jin Wang. Biased control-variate estimation. IE Transactions, 33(3):219-228, 2001.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-294, 1933.
Sara Van De Geer. Least squares estimation. Encyclopedia of statistics in behavioral science. 2005.
Nikos Vlassis, Aurelien Bibaut, Maria Dimakopoulou, and Tony Jebara. On the design of estimators for bandit off-policy evaluation. In International Conference on Machine Learning, pages 6468 6476. PMLR, 2019.
Lijun Zhang, Tianbao Yang, Rong Jin, Yichi Xiao, and Zhi-hua Zhou. Online stochastic linear optimization under one-bit feedback. International Conference on Machine Learning, pages 392-401, 2016.
12


Reviews:
[{"review_id": "bIJQzBj3-yN", "reviewer": "Reviewer_7d9W", "summary": "The paper tackles a bandit setting similar to contextual bandits, where the feedback consists of the reward obtained from playing an arm, but also an additional random variable (the control variate) which is correlated with the reward but whose mean is known to the decision maker. Unlike in contextual bandits, the value of this control variate is not available at decision time but it is only revealed after the arm's play and can thus only be used to produce better estimates of the rewards of arms. The paper proposes the UCB-CV algorithm that builds confidence intervals that exploit this additional information to produce lower regret. The algorithm is accompanied by a regret analysis and experiments demonstrating the algorithm's performance and the decrease in regret that can be achieved based on the correlation coefficient between the reward and the control variates.", "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": "Overall I found the paper well written and presented. I appreciate the effort put into the experimental section as well as the Section 2 offering introduction to the area. My main concerns surround the practical relevance of the setting (and algorithm - relative to Splitting for instance), the unclear distinction of the results here from prior work (a fence between the problem tackled here and contextual bandits, and MABs with covariates). Detailed review below:\n\n**Originality**:\\\nTo the best of my knowledge this setting is original for the bandit setting. I do however have a few questions regarding the practical relevance of the problem studied here. First, the control variates would be available at decision time in most practical scenarios (the job \"size\" is usually known ahead of time, similarly wouldn't the pilot signals be sent in advance of the packet?). Secondly, from the historic data used to estimate the means of the control variates, we can also estimate the variance. What is the reason why the variance of the control variate ${\\sigma^2_{w,i}}_{i \\in [K]}$ is left unknown?\\\nI think there is a bit of room for improvement when it comes to separating the setting here from contextual bandits. If the control variates were revealed at the begining of the round (like contexts are revealed in contextual bandits), would this setting be a specific instance of contextual bandits?\\\nI am also missing how this setting compares to the MAB problem with covariates (see [1], [2]).\n\n**Quality**:\\\nI have not checked the proofs in the Appendix. The paper seems technically sound and the algorithm well-grounded in theory. The authors also point out several remarks offering insights into the bound presented in Theorem 1. I would have liked to see a bit more detail as to where the upper bound on $(V^{(2)}_{T,T,q})^2$ is obtained. Possibly also include larger time horizon T in the plot (order of thousands or tens of thousands).\\\nI appreciate the effort put into the experiments section and implementing a good number of baselines. I would like to know more about why Splitting outperforms all algorithms and why would UCB-CV be preferable?\\\nA further question surrounds what is the impact of the hyperparameter $\\alpha$ that is fixed to $\\alpha=2$ throughout the majority of the paper. Is this the optimal value for this parameter? If not, how sensitive is the algorithm to the choice of $\\alpha$?\n\n**Clarity**:\\\nI found the paper well presented with sufficient attention given to aspects that cause confusion (I particularly appreciate the clarifying remarks following Theorem 1.) I would appreciate more clarifications surrounding the novelty of the setting and the advantages of the proposed method relative to just using Splitting which appears to outperform UCB-CV in the experiments (an example of a problem instance where Splitting would fail would present a convincing argument).\n\n**Significance**:\\\nThe significance of the results should be stated more clearly in the paper. As is, I believe the setting studied here has limited connection to practical applications, though I do see the potential of future study into the theory of exploiting control variates (I liked the ranking example in Section 7). \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper does a decent job addressing limitations of their work in the 3 remarks at the end of Section 4, though this might not be comprehensive.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "QOyLey-ygw1", "reviewer": "Reviewer_bigw", "summary": "This paper considers low regret learning in stochastic multi-armed bandits in the presence of control variables. For jointly Gaussian reward and control variables, and linear control variates, the authors show a factor 1-ρ^2 reduction in the regret.", "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": "The paper focuses on reducing regret in multiarmed bandits using control variates. The authors derive the regret under linear control variates for the joint Gaussian case, and show that the regret reduces by a multiplicative factor 1-ρ^2 .\n\nFor general reward and CV distributions, the authors utilise jackknifing and splitting resampling to obtain estimators with smaller bias and sharper confidence intervals. For the general case, the confidence intervals are only asymptotic and hold approximately for finite samples.\n\nOverall, the paper is reasonably well written, and seems technically sound. It takes a well-known technique of CVs and applies it in the context of MABs using standard techniques. The innovativeness of the work can be characterised as “moderate” in my opinion. \n\nMinor:\n\n(I) Line 165: Please clarify why \\bar{X}_i are correlated\n(II) Line 176: It is not clear how lemma 2 is analogous to Hoeffding from the way you have written it in terms of the t-distribution. Please elucidate by comparing to the exponential decay in Hoeffding\n(III) Line 322: “our the bounds”", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "\nNo negative social impact.\n\nOne of the shortcomings is that the motivating examples are sketchy and weak. The authors speak about examples from queueing and wireless fading channels, but they do not give concrete examples where such CVs are available, or can be used to improve learning performance.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "OduXei00Cpa", "reviewer": "Reviewer_trp8", "summary": "Starting from the hypothesis that smaller variance estimators of mean rewards result in better bandit performance, the authors leverage Control Variate (CV) theory to propose a bandit algorithm under the presence of auxiliary information about arm rewards.\n\nThe authors provide theoretical regret bounds of the proposed control variate based UCB algorithm (under the multivariate normal distribution assumption) and experimentally validate the performance on Gaussian and other distribution based assumptions.\n\nThe authors show that, as expected, the attained regret reduction is a function of how strongly correlated the reward samples and the observed control variates are.", "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 contribution of this work is on the combination of Control Variate theory (well-known in the statistics community) with a state of the art bandit algorithm (UCB), along with its corresponding regret bounds. The experimental evaluation section however can be significantly improved.\n\nThe analysis of the confidence intervals is challenging and novel in the context of the bandit literature, because the optimal (linear) control variate parameters need to be estimated from the observed reward samples (as determined by the bandit algorithm). The authors present in Section 4 the regret bound of the proposed algorithm for multivariate Gaussian rewards and leave for Section 5 the adaption of the algorithm (via jackknifing, splitting, and batching methods) for general distributions.\n\nLemma 1 and Lemma 2, where control variate theory is used to design confidence intervals of the proposed control variate mean reward estimators, are key for their regret bound in Theorem 1, where the regret reduction induced by control variates is reflected via the correlation parameter $\\rho$. The authors provide a very informative discussion in Remarks 1-3 and Figure 1 on the non-trivial dependency between number of covariates $q$ and the constants appearing in Theorem 1.\n\nThe proposed algorithm assumes knowledge of the mean $w$ of the control variates per-arm (a limitation only discussed in their conclusion).\n- The paper could be significantly improved if a theoretical analysis of the error introduced by estimates of the control variate mean $\\widehat{w}$ were to be provided.\n\nIn order to extend their control variate based approach to non-Gaussian distributions (where the properties of t-distributions can not be used to obtain analytical confidence intervals), the authors resort to well-known resampling methods to develop (approximate and/or asymptotic) confidence intervals.\n\nFinally, to illustrate the performance of the proposed algorithm and the validity of the presented regret bound, synthetic evaluations are presented in Section 6. However, the results would be more convincing if the following suggestions were to be incorporated:\n\n1. The proposed algorithm assumes knowledge of the mean of the control variates $w$, which is an unreasonable assumption in practice. As such, it would be informative to show, empirically, how much the performance of the proposed algorithm degrades with the quality of the control variate mean estimates $\\widehat{w}$.\n\n2. The studied bandit instances can be posed as linear contextual bandits:\n   - $y=x^\\top \\theta + \\epsilon$, with $y_{t}=X_{t}$, $x_{t}=(1, W_{t})$ and $\\theta=(\\mu_{v}, 1)$, where $\\theta$ are the unknown parameters, $x_t$ the observed context (with a bias term) and $\\epsilon \\sim N(0, \\sigma_{v}^2)$.\n   - A set of experiments where their proposed algorithm is compared to linear Gaussian Thompson sampling and UCB algorithms would be very insightful to better illustrate the benefits of control variates in the linear-Gaussian setting. \n\n3. The authors state that \"We observe that Thomson Sampling has a large regret\". Given the successful performance presented by many in the literature with Thompson sampling for Gaussian bandit rewards, I encourage the authors to clarify what mean and variance priors they used for their Gaussian Thompson sampling implementation, and whether adjusting them improves the observed performance. \n\nOther minor comments/suggestions:\n\n- Line 15: \"the arms rewards\" -> \"the arm rewards\"\n- Line 165: \"CVs have follow multivariate\" -> \"CVs follow a multivariate\"\n- Line 276: \"regret bound with\" -> \"and regret results with\"?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss in their conclusion section the fact that the proposed algorithm assumes knowledge of the mean of the control variates per-arm.\n\nThe analysis (at least empirically) of the impact of estimating these control variate means on regret performance would significantly strengthen their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "E4p68P3moS6", "reviewer": "Reviewer_2Zfv", "summary": "This paper considers the (stochastic) multi-armed bandit problem, and proposes to use control variates to improve estimates of the reward for each arm. The case of Gaussian reward and control variates is studied in detail from a theoretical viewpoint, and the more general case is studied empirically. ", "questions": "", "limitations": "", "rating": 6, "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": "I should clarify before starting my review that my knowledge of reinforcement learning is fairly limited, but that I have significant experience with the use of control variates for Monte Carlo methods more generally. My comments should therefore be interpreted with this in mind.\n\n\nMain comments\n----------------\n\n- I found the paper to be well written and argued. This made it easier for me to read given I am not an expert in reinforcement learning.\n- The literature review seems fairly thorough to me. A large number of relevant papers are discussed, and comparisons are made with the present paper. I have nevertheless suggested a number of other papers from the statistics literature which could be interesting to discuss, mostly as I believe they could potentially bring further gains. See the \"literature\" section below. \n- Section 4: It is very much unclear to me whether assuming that the reward and control variate of each arm have a multivariate normal distribution is something reasonable in practice. From the literature review (Section 1.1.), it seems like a range of assumptions are used in practice, with Auer et al 2002 being the closest to this setting. Looking at some of the papers cited, it does however seem overly restrictive. For example, the Bubeck and Cesa-Bianchi paper from 2012 uses much less restrictive assumptions on the reward. I would find it particularly useful for the authors to provide a much more detailed discussion of this point. For example, what if the reward and control variates are only sub-Gaussian? What if the reward has a heavier tail distribution than the control variate or vice versa? I can understand why using Gaussian assumptions is useful for the theory (since it is then simply a linear regression problem with Gaussian variables), but it would be interesting to understand the limitations of this assumption for deriving the theoretical results and whether any of the assumption could be relaxed.\n- The numerical experiments section is interesting, but left me wondering how realistic it is to actually use this approach in practice. This is mostly because it did not contain any practical example (as opposed to a synthetic simulation study) where a control variate is actually available. I think the paper would strongly benefit from such an example as otherwise it is difficult to see this actually being a practical method. \n- Also, as pointed out in the conclusion, one of the biggest issue will be getting a control variate with known mean. I again struggle to see situations where this would be the case in applied problems. If it is not possible to know the mean exactly, what would be the impact on the estimated reward? Could the bias introduced somewhat lead to sub-optimal results relative to not using a control variate?\n\n\nLiterature review:\n-------------------\n- There are a number of papers on the use of control variates in reinforcement learning that could be discussed, including: \nhttps://jmlr.csail.mit.edu/papers/volume5/greensmith04a/greensmith04a.pdf\nhttps://arxiv.org/abs/1908.03263\nhttps://arxiv.org/abs/1906.08868\nhttps://openreview.net/pdf?id=H1mCp-ZRZ\nAlthough it is not applied to the same set of RL algorithms, it might still be useful to tell the reader about this for context. Note that I have just listed the first few that come up on Google, but a more complete literature review could help.\n\n- Control variates are also very common in Monte Carlo methods; for example:\nhttps://link.springer.com/article/10.1007/s11222-012-9344-6\nhttps://rss.onlinelibrary.wiley.com/doi/abs/10.1111/rssb.12185\nhttps://projecteuclid.org/journals/bernoulli/volume-25/issue-2/Convergence-rates-for-a-class-of-estimators-based-on-Steins/10.3150/17-BEJ1016.short\nThese are constructed somewhat differently from the control variates in here, and it might be interesting to discuss the advantages and disadvantages of each approach.\n\nMinor comments\n---------------\n- line 93: \"which could then used as side information\"\n- Eq 4 and line 161: slightly inconsistent use of * or \\star", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There was no discussion of societal impact. I have also highlighted above a number of limitations which should be discussed in more details.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The committee has appreciated the involved and detailed response to their questions and comments and agreed that this work should be accepted. One reviewer raised the question of the knowledge of the variance of the control variate $\sigma_{w,i}^2$ and would encourage the authors to investigate and discuss this question in their final version.
Decision: Accept (Poster)