Stochastic Multi-Armed Bandits with Control Variates
Year: 2022

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.

heading: 1 Introduction
text: Stochastic Multi-Armed Bandits (MAB) setting has been extensively used to study decision making under uncertainty (Thompson, 1933; Bubeck et al., 2012; Lattimore and Szepesvári, 2020). In the classical setting, it is assumed that the arm rewards are independent of each other. After playing an arm, the learner observers independent and identically distributed reward samples. The exploration versus exploitation trade-off is a fundamental problem in the bandits setting, and a learner can accumulate more rewards if it is balanced well. A better balance can be achieved if the learner can estimate arm’s mean rewards with tighter confidence bounds (Auer et al., 2002; Auer and Ortner, 2010; Garivier and Cappé, 2011) and smaller variance (Audibert et al., 2009b; Mukherjee et al., 2018). Any available side or 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 is 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 or an increase in the number of samples (Lavenberg et al., 1982). Many stochastic simulations involve inputs generated using known distributions. These inputs can be potential CVs as output could be correlated with them. It has motivated the development of rich theory to analyze the quality of the estimators resulting from CVs (Lavenberg and Welch, 1981; Lavenberg et al., 1982; Nelson, 1990). We adopt these techniques to study the stochastic multi-armed bandits problem when CVs are available for the arms.
In many real-life applications, exogenous variables influence arms’ rewards and act as CVs. For example, consider a job aggregating platform that assigns jobs to one of the servers/workers in each slot. The jobs are of variable size, and the time to serve them depends on their size and other
35th Conference on Neural Information Processing Systems (NeurIPS 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 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 a channel can be used as a CV to estimate the channel’s quality.
The performance of a MAB algorithm depends on how good is the confidence interval of its mean reward estimators (Auer et 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− ρ2) 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.

heading: 1.1 Related Work
text: 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é, 2011), 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., O((b2/∆) log T ), where ∆ is the smallest sub-optimality gap. UCB1-NORMAL by (Auer et al., 2002) uses the variance estimates in the index of the arms and when rewards are Gaussian with variance σ2, to achieve regret is of order O((σ2/∆) log T ). This bound is even better than that of UCB1 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 when rewards are bounded. Extending the idea of using ‘variance aware’ indices, UCBV
(Audibert et al., 2009b) algorithm achieves regret of order O((σ2/∆ + 2b) log 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 not 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 et al., 2010; Filippi et al., 2010; Abbasi-Yadkori et 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 to learn the optimal arm. They assume a 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 not use CVs directly to 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 was 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 use the standard Bernstein inequality to 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.

heading: 2 Control Variate for Variance Reduction
text: Let µ be the unknown quantity that needs to be estimated, and X be an unbiased estimator of µ, i.e., E [X] = µ. A random variable W with known expectation (ω) is a CV if it is correlated with X . Linear control methods use errors in estimates of known random variables to reduce error in the estimation of an unknown random variable. For any choice of a coefficient β, define a new estimator as X̄ = X + β(ω −W ). It is straightforward to verify that its variance is given by
Var(X̄) = Var(X) + β2Var(W )− 2βCov(X,W ).
and it is minimized by setting β to
β? = Cov(X,W )
Var(W ) .
The minimum value of the variance is given by Var(X̄) = (1−ρ2)Var(X), where ρ 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 Cov(X,W ) and Var(W ) are unknown and need to be estimated to compute the best approximation for β?.

heading: 3 Problem Setting
text: We consider a stochastic multi-armed bandits problem with K arms. The set of arms is represented by [K] .= {1, 2, . . . ,K}. In round t, the environment generates a vector ({Xt,i}i∈[K], {Wt,i}i∈[K]). The random variable Xt,i 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 σ2i . The random variable Wt,i is the Control Variate (CV) associated with the reward of arm i in round t. These random variables are drawn from an unknown but fixed distribution with mean ωi and variance σ2w,i and form an IID sequence. The learner knows the values {ωi}i∈[K] but
not the {σ2w,i}i∈[K]. The correlation coefficient between rewards and associated control variates of an arm i is denoted by ρi.
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 µσ = {µi, σ2i }i∈[K], ωσ = {ωi, σ2w,i}i∈[K], and ρ = {ρi}i∈[K] identify an instance of MAB-CV problem, which we denote henceforth using P = (µσ,ωσ,ρ). The collections of all MAB-CV problems are denoted by P . For a problem instance P ∈ P with mean reward vector µ, we denote the optimal arm as i? = argmax
i∈[K] µi.
MAB-CV problem with instance (µσ,ωσ,ρ) For round t:
1. Environment generates a vector Xt = (Xt,1, . . . , Xt,K) ∈ RK and Wt = (Wt,1, . . . ,Wt,K) ∈ RK , where E [Xt,i] = µi, Var(Xt,i) = σ2i , E [Wt,i] = ωi, Var(Wt,i) = σ2w,i, and the sequence (Xt,i)t≥1 and (Wt,i)t≥1 are IID for all i ∈ [K].
2. Learner selects an arm It ∈ [K] based on past observation of rewards and CVs samples from the arms till round t− 1.
3. Feedback and Regret: The learner observes a random reward Xt,It and associated CV Wt,It , and then incurs penalty (µi? − µIt).
Let It 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 an Oracle that plays the optimal arm in each round. Specifically, we measure the performance in terms of regret defined as follows:
RT = Tµi? − E [ T∑ t=1 Xt,It ] . (1)
Note that maximizing the mean cumulative reward of a policy is the same as minimizing the policy’s regret. A good policy should have sub-linear expected regret, i.e., RT /T → 0 as T →∞. Our goal is to learn a 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-exploitation trade-off and start playing the optimal arm more frequently early.

heading: 4 Arms with Normally Distributed Rewards and Control Variates
text: We first focus on the case where the rewards and associated CVs of arms have a multivariate normal distribution. We discuss the general distributions in 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 i in round t as follows:
X̄t,i = Xt,i + β ∗ i (ωi −Wt,i), (2)
whereXt,i is the tth reward, Wt,i is the tth associated control variate with an arm i, ωi = E [Wt,i], and β∗i = Cov(Xt,i,Wt,i)/Var(Wt,i). Using s such samples, the mean reward for an arm i is defined as µ̂cs,i = ( ∑s r=1 X̄r,i)/s. Let µ̂s,i = 1 s ∑s r=1Xr,i and ω̂s,i = 1 s ∑s r=1Wr,i denote the sample mean of reward and CVs of an arm i from s samples. Then µ̂cs,i can be written as follows:
µ̂cs,i = µ̂s,i + β ∗ s,i(ωi − ω̂s,i). (3)
Since the value of Cov(Xi,Wi) and Var(Wi) are unknown, the optimal coefficient β∗s,i need to be estimated. After having s samples, it is estimated as below and used in Eq. (3).
β̂∗s,i = ∑s r=1(Xr,i − µ̂s,i)(Wr,i − ωi)∑s
r=1(Wr,i − ωi)2 . (4)
When the variance of CV is known, it can be directly used to estimate β∗i by replacing estimated variance by actual variance of CV in the denominator of Eq. (4), i.e., replacing ∑s r=1(Wr,i − ωi) 2/(s− 1) by σ2w,i. After observing reward and associated control variates for arm i, the value of β̂?i is re-estimated. The value of β̂ ? i depends on all observed rewards and associated control variates from arm i. Since all X̄.,i uses same β̂?i , this leads to correlation between the X̄.,i observations.
Let Var(X̄i) = σ2c,i denote the variance of the linear CV samples and νs,i = Var(µ̂ c s,i) denote the variance the estimator using these samples. Since the mean reward estimator (µ̂cs,i) 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 µ̂cs,i. Lemma 1. Let the reward and control variate of each arm have a multivariate normal distribution. After observing s samples of reward and control variate from arm i, define ν̂s,i = Zs,iσ̂ 2 c,i(s)
s , where
Zs,i =
( 1− ( ∑s r=1(Wr,i − ωi)) 2
s ∑s r=1(Wr,i − ωi)2
)−1 and σ̂2c,i(s) = 1
s− 2 s∑ r=1 (X̄r,i − µ̂cs,i)2,
then ν̂s,i is an unbiased variance estimator of µ̂cs,i, i.e., E[ν̂s,i] = Var(µ̂cs,i).
The confidence interval for reward estimator is 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 { |µ̂cs,i − µi| ≥ V (α) t,s √ ν̂s,i } ≤ 2/tα,
where V (α)t,s denote 100(1 − 1/tα)th percentile value of the t−distribution with s − 2 degrees of freedom and ν̂s,i is an unbiased estimator for variance of µ̂cs,i.
We prove Lemma 1 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 rewards and CVs have a multivariate normal distribution. Therefore, we can 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 {X̄t,i} deviating from the true mean of arm i decays fast. Further, the deviation factor V (α)t,s √ ν̂s,i depends on the variance of the estimator (µ̂cs,i), which guarantees sharper confidence intervals. As we will see later in Lemma 3, these confidence terms are smaller by a factor (1− ρ2i ) 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.

heading: 4.1 Algorithm: UCB-CV
text: Let Ni(t) be the number of times the arm i is selected by a learner until round t and ν̂Ni(t),i be the unbiased sample variance of mean reward estimator (µ̂cNi(t),i) for arm i. Motivated from Lemma 2, we define optimistic upper bound for mean reward estimate of arm i as follows:
UCBt,i = µ̂cNi(t),i + V (α) t,Ni(t) √ ν̂Ni(t),i. (5)
Using above values as UCB indices of arms, we develop an algorithm named UCB-CV for the MAB-CV problem. The algorithm works as follows: It 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 (σ̂2c,i(s)) can be computed (see Lemma 1).
In round t, UCB-CV computes the upper confidence bound of each arm’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,It and associated control variate Wt,It are observed. After that, the value of NIt(t) is updated and β̂
∗ NIt (t),It , µ̂cNIt (t),It and ν̂t,NIt (t) are re-estimated. The same process is repeated for the subsequent rounds.
UCB-CV UCB based Algorithm for MAB-CV problem 1: Input: K, Q, α > 1 2: Play each arm i ∈ [K] Q times 3: for t = QK + 1, QK + 2, . . . , do 4: ∀i ∈ [K] : compute UCBt−1,i as given in Eq. (5) 5: Select It = argmax
i∈[K] UCBt−1,i
6: Play arm It and observe Xt,It and associated control variates Wt,It . Increment the value of NIt(t) by one and re-estimate β̂
∗ NIt (t),It , µ̂cNIt (t),It and ν̂t,NIt (t) 7: end for

heading: 4.2 Estimator with Multiple Control Variates
text: 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 Wt,i,j be the jth control variate of arm i that is observed in round t, . Then the unbiased mean reward estimator for arm i with associated CVs is given by
µ̂cs,i,q = µ̂s,i + β̂ ∗> i (ωi − ω̂s,i),
where β̂ ∗ i = ( β̂i,1, . . . , β̂i,q )> , ωi = (ωi,1, . . . , ωi,q) >, and ω̂s,i = (ω̂s,i,1, . . . , ω̂s,i,q) >.
Let s be the number of rewards and associated CVs samples for arm i,W i be the s× q matrix whose rth row is (Wr,i,1,Wr,i,2, . . . ,Wr,i,q), and Xi = (X1,i, . . . , Xs,i)>. By extending the arguments used in Eq. (4) to q control variates, the estimated coefficient vector is given by
β̂ ∗ i = (W > i W i − sω̂s,iω̂ > s,i) −1(W>i Xi − sω̂i µ̂s,i).
We can generalize Lemma 1 and Lemma 2 for the MAB-CV problems with q control variates and then use UCB-CV with Q = q + 2 and appropriate optimistic upper bound for multiple control variate case. More details can be found in Appendix C.

heading: 4.3 Analysis of UCB-CV
text: In our next result, we describe the property of our estimator that uses 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 q be the number of control variates. Then after having s observations of rewards and associated control variates from arm i,
E [ µ̂cs,i,q ] = µi, and Var(µ̂cs,i,q) = s− 2
s− q − 2 (1− ρ2i )Var(µ̂s,i),
where ρ2i = σXiW iΣ −1 W iW i σ>XiW i/σ 2 i is the square of the multiple correlation coefficient, σ 2 i = Var(Xi), and σXiW i = (Cov(Xi,Wi,1), . . . ,Cov(Xi,Wi,q)).
The following is 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, ∆i = µi? − µi be the sub-optimality gap for arm i ∈ [K], and Ni(T ) be the number of times sub-optimal arm i selected in T rounds. Let
CT,i,q = E [ Ni(T )−2 Ni(T )−q−2 ( V (2) T,Ni(T ),q
V (2) T,T,q
)2] for all i. Then the regret of UCB-CV in T rounds is upper
bounded by
RT ≤ ∑ i 6=i?
( 4(V
(2) T,T,q) 2CT,i,q(1− ρ2i )σ2i ∆i + ∆iπ 2 3 + ∆i
) .
Note that α is a hyper-parameter to trade-off between exploration and exploitation. UCB-CV works as long as α > 1 and the effect of α on the regret bound is through the term ∑∞ i=1 1 tα . This term has a nice closed form value of π2/6 for α = 2. Hence, we state the results with α = 2 and use it in the experiments as well.
Remark 1. Unfortunately, we cannot directly compare our bound with that of UCB based stochastic MAB algorithms like UCB1-NORMAL and UCBV as V (2)T,T,q do not have closed-form expression. V (2) T,T,q denotes 100(1− 1/T 2)th percentile of t-distribution with T − q − 1 degrees of freedom.
Remark 2. As the degrees of freedom decreases in q, V (2)T,T,q increases in q (see Fig. 1a for small value of T and Fig. 1b for large value of T ). However, this does not imply that the overall regret increases in q as ρ2i also increases in q. Hence dependency of regret on 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,q)
2 is upper bounded by 3.726 log T . This upper bound holds for all q as long as T ≥ q + max(32, 0.7q).
Remark 3. It is hard to boundCT,i,q as V (2) T,·,q does not have a explicit form. However, CT,i,q tends to 1 as T →∞. Indeed, from lower bound argument, we know that Ni(T )→∞ as T →∞ and hence Ni(T )−2 Ni(T )−q−2 ↘ 1 and V (2) T,Ni(T ),q
V (2) T,T,q ↘ 1 (confidence interval shrink with more samples) as shown in Fig. 1c. However, under some assumptions, we can obtain a bound empirically. Specifically, if q ≤ 20
and Ni(T ) > 50, then Ni(T )−2 Ni(T )−q−2 ≤ 1.72 and from t-distribution tables, we get
V (2)
T,Ni(T ),q
V (2) T,T,q
≤ 1.5
(see Fig. 1c), hence the bound CT,i,q ≤ 4. We can guarantee Ni(T ) > 50 by playing each arm 50 times at the beginning. Therefore, we can obtain one possible explicit bound in Lemma (6) by replacing CT,i,q with 4. However, for a general case, an explicit bound in Lemma 8 is hard.

heading: 5 General Distribution
text: We now consider the general case with no distributional assumptions on reward and associated CVs of arms. The samples X̄t,i,q resulting from the linear combination of rewards and CVs are dependent but need not be normally distributed. Hence µ̂cs,i,q need not remain an unbiased estimator. Therefore, we cannot use the t-distribution properties to obtain confidence intervals. However, we can use resampling methods such as jackknifing, splitting, and batching to 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.

heading: 5.1 Jackknifing
text: In statistics, jackknifing is a well-known re-sampling technique for variance and bias estimation (Efron, 1982; Efron and Gong, 1983). We start with a classical presentation of jackknifing for CVs
(Lavenberg et al., 1982). Let µ̂c,−js,i,q be the estimate of the mean reward that is computed without sample X̄j . The Y Jj,i,q = sµ̂ c s,i,q − (s − 1)µ̂ c,−j s,i,q , which is sometimes called the j
th pseudo-value. Using pseudo-values mean reward estimation given as µ̂c,Js,i,q = 1 s ∑s j=1 Y J j,i,q and its sample variance
is ν̂Js,i,q = (s(s− 1))−1 ∑s j=1(Y J j,i,q − µ̂ c,J s,i,q)
2. µ̂c,Js,i,q is shown to be unbiased (Nelson, 1989)[Thm. 7] when reward variance is bounded. Further, µ̂c,Js,i,q ± tα/2(n − 1)ν̂Js,i,q is a asymptotically valid confidence interval (Avramidis et al., 1991) and holds approximately for finite number of samples.

heading: 5.2 Splitting
text: Splitting is a technique to split the correlated observations into two or more groups, compute an estimate of β∗i from each group, then exchange the estimates among the groups. Nelson (1990) considers an extreme form of splitting, where he splits s observations into s groups. The jth observation is given by
Y Sj,i,q = Xj,i + β̂ ∗−j i (ω −W j,i), j ∈ [s],
where β̂ ∗−j i is estimated without j
th observation and W j,i = (Wj,i,1, . . . ,Wj,i,q) is the vector of CVs with q elements associated with reward Xj,i. The point estimator for splitting method is µ̂c,Ss,i,q = 1 s ∑s j=1 Y S j,i,q and its sample variance is ν̂ S s,i,q = (s(s−1))−1 ∑s j=1(Y S j,i,q− µ̂ c,S s,i,q)
2. Then µ̂c,Ss,i,q ± tα/2(n− 1)ν̂Ss,i,q gives an approximate confidence interval (Nelson, 1990).
Below we define UCB index for these methods. Let ν̂GNi(t),i,q be the sample variance of mean reward estimator (µ̂c,Gs,i,q) for arm i. We define the optimistic upper bound for mean reward for G ∈ {J, S} as follows:
UCBGt,i,q = µ̂ c,G Ni(t),i,q + V G,αt,Ni(t),q √ ν̂GNi(t),i,q. (6)
where V G,αt,s,q is the 100(1 − 1/tα)th percentile value of the t−distribution with s − 1 degrees of freedom. Since the optimistic upper bounds defined in Eq. (6) are valid only asymptotically (Nelson, 1990; Avramidis et al., 1991), it 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 in the next section.

heading: 6 Experiments
text: 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 et al., 2018) on different synthetically generated problem instances. For all the instance we use we use K = 10, q = 1, and α = 2. All the experiments are repeated 100 times and cumulative regret with a 95% confidence interval (the vertical line on 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 a multivariate normal distribution. The reward of each arm has two components. We treated one of the components as CV. In round t, the reward of arm i is given as follows:
Xt,i = Vt,i +Wt,i,
where Vt,i ∼ N (µv,i, σ2v,i) andWt,i ∼ N (µw,i, σ2w,i). Therefore,Xt,i ∼ N (µv,i+µw,i, σ2v,i+σ2w,i). We treat Wi as CV of Xi. It can be easily shown that the correlation coefficient of Xi and Wi is ρi = √ σ2w,i/(σ 2 v,i + σ 2 w,i). For each i, we set µv,i = 0.6 − (i − 1) ∗ 0.05, µw,i = 0.3, for arm
i ∈ [K]. The value of σ2v,i = 0.1 and σ2w,i = 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 1 except each arm has a different CV associated with its reward. The mean value of the CV associated with arm i is set as µw,i = 0.8− (i− 1) ∗ 0.05. Instance 3: It is the same as the Instance 2 except the samples of reward and associated control variate are generated from Gamma distribution, where the value of scale is set to 1.
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 σ2v,i = 1 and σ 2 w,i = 1 for all arms.
Comparing regret of UCB-CV with existing algorithms The regret of 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 a 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-based strategy, which has a small probability of eliminating the optimal arm.
Regret of UCB-CV vs Correlation Coefficient Theorem 1 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 a multivariate normal distribution with rewards expressed as sum of two components. We set µv,i = 6.0− (i− 1) ∗ 0.5 and µw,i = 4.0 for arm i ∈ [K]. The value of σ2v,i = 1.0 and σ2w,i = 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 Xi and Wi is ρi = √ σ2w,i/(σ 2 v,i + σ 2 w,i), we varied σ 2 v,i over the
values {1.0, 1.5., 2.0, 2.5, 3.0} to obtain problem instances with different correlation coefficient. Increasing σ2v,i reduces the correlation coefficient of Xi and Wi. 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 as 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-tailed distributions (Instance 3) and UCB-CV performs better for normal distribution (Instance 2) and Log-normal distribution (Instance 4) as shown in Fig. 3.
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/approximated means can deteriorate the performance of the proposed algorithm.s 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 (ε) in the mean estimation of CVs, we run an experiment with Instance 1, Instance 2, and Instance 5. We assume that the approximated mean of CVs is given by ωi + ε. 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-art 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, and EUCBV with the appropriate factor (used 6 for the experiment) for a 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.
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 an advantage using control variates. The impact of such approximations in bandits needs to be analyzed extensively and demands independent work.

heading: 7 Conclusion
text: 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 a 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 O(σ2(1− ρ2)/∆ log T ) where σ2 is the maximum variance of arm rewards and ρ 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. It 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 top-ranked arm.

heading: Acknowledgements
text: Manjesh K. Hanawal is supported by INSPIRE faculty fellowship from DST and Early Career Research Award (ECR/2018/002953) from SERB, Govt. of India. This work was done when Arun Verma was at IIT Bombay.

Review summaries:
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.  The 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.  The 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.

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.