Exploiting Correlated Auxiliary Feedback in Parameterized Bandits
Authors: Arun Verma
Zhongxiang Dai
Yao Shu
Bryan Kian Hsiang Low
Venue: NeurIPS 2023 poster (2023)
Keywords: Parameterized Bandits
Auxiliary Feedback
Control Variate
Regret Minimization
TL;DR: This paper develops a method that uses additional information about rewards to reduce regret and characterizes regret reduction in terms of the correlation between additional information and reward.

Abstract: We study a novel variant of the parameterized bandits problem in which the learner can observe additional auxiliary feedback that is correlated with the observed reward. The auxiliary feedback is readily available in many real-life applications, e.g., an online platform that wants to recommend the best-rated services to its users can observe the user's rating of service (rewards) and collect additional information like service delivery time (auxiliary feedback). In this paper, we first develop a method that exploits auxiliary feedback to build a reward estimator with tight confidence bounds, leading to a smaller regret. We then characterize the regret reduction in terms of the correlation coefficient between reward and its auxiliary feedback. Experimental results in different settings also verify the performance gain achieved by our proposed method.

Exploiting Correlated Auxiliary Feedback in Parameterized Bandits
Bryan Kian Hsiang Low Department of Computer Science, National University of Singapore, Republic of Singapore {arun, daizhongxiang, shuyao, Bowkh]-ccom cromp.nus:........ nus. edu. sg
Arun Verma Zhongxiang Dai
Yao Shu
Abstract
We study novel variant of the parameterized bandits problem in which the learner can observe additional auxiliary feedback that is correlated with the observed reward. The auxiliary feedback is readily available in many real-life applications, e.g., an online platform that wants to recommend the best-rated services to its users observe the user's 's rating of service (rewards) and collect additional information like service delivery time (auxiliary feedback). In this paper, we first develop method that exploits auxiliary feedback to build reward estimator with tight confidence bounds, leading to a smaller regret. We then characterize the regret reduction in terms of the correlation coefficient between reward and its auxiliary feedback. Experimental results in different settings also verify the performance gain achieved by our proposed method.
Introduction
Parameterized bandits (Slivkins, 2019; Lattimore and Szepesvári, 2020) have many real-life applications online recommendation, advertising, web search, and e-commerce. In this bandit problem, learner selects an action and receives a reward for the selected action. Due to the large (or infinite) number of actions, the mean reward of each action is assumed to be parameterized by an unknown function, e.g., linear (Li et al., 2010; Chu et al., 2011; Abbasi-Yade and Goyal, 2013), GLM (Filippi et al., 2010; Li et al., 2017; Jun et al., 2017), and non-linear (Valko et al., 2013; Chowdhury and Gopalan, 2017). The learner aims learn the best action quickly as possible. However, it depends on the tightness of confidence bounds of function that correlate action with the reward. The learner exploits any available information like side information (i.e., information available to the learner before selecting an action, e.g., contexts) (Li et al., 2010; Agrawal and Goyal, 2013; Li et al., 2017) and side observations (i.e., information about other actions, e.g., graph feedback) (Alon et al., 2015; Wu et al., 2015) to make confidence bounds as tight as possible. This paper considers another type of additional information (correlated with the reward) that learner can observe with reward for the selected action, which we call auxiliary feedback.
et al., 2011; Agrawal
The auxiliary feedback is readily available in many real-life applications. For example, consider an online food delivery platform that wishes to recommend the best restaurants (actions) to its users. After receiving food, the platform observes user ratings (rewards) for the order and can collect additional information like food delivery time (auxiliary feedback). Since the restaurant's 'ss rating also depends overall food delivery time, can expect be correlated with the user rating. The platform can estimate or know the average delivery time for given order from historical data. Similar scenarios arise in recommending the best cab to users (auxiliary information can be the cab's distance from the rider or driver's s response to ride request), e-commerce platforms choosing top sellers buyers (auxiliary information can be seller's response time for order confirmation and delivery), queuing network (Lavenberg and Welch, 1981; Lavenberg et al., 1982), jobs scheduler (Verma and Hanawal, 2021), and many more. Therefore, the following question naturally arises: How to exploit correlated auxiliary feedback to improve the performance of a bandit algorithm?
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

One possible method is to use auxiliary feedback in the form of control variates (Lavenberg et al., 1982; Nelson, 1990) for the observed reward. A control variate represents any random variable (auxiliary feedback) with a known mean that is correlated with the random variable of interest (reward). Several works (Kreutzer et al., 2017; Sutton and Barto, 2018; Vlassis et al., 2021; Verma and Hanawal, 2021) have used control variates to estimate the mean reward estimator with smaller variance, leading to tight confidence bounds and hence better performance. The closest work to our setting is Verma and Hanawal (2021). However, it only focuses on the parametterrzed setting and assumes a finite number of actions, We thus consider a more general bandit setting with a large (or even infinite) number of actions and allow an unknown function to parameterize auxiliary feedback.
Motivated by control variate theory (Nelson, 1990), we first introduce hybrid reward, which combines the reward and its auxiliary feedback in such a way that hybrid reward is an unbiased reward estimator with smaller variance than the observed reward. However, the optimal combination of reward and its auxiliary feedback requires knowledge of the covariance matrix among auxiliary feedback and covariance between reward and its auxiliary feedback, which may not be available in practice. Since the reward and its auxiliary feedback are functions of the selected action, existing control variate results can not be useful to our sequential setting. Naturally, we face the question of how to combine reward and its auxiliary feedback efficiently using available information. To answer this, we extend control variate theory results to the problems where known functions can parameterize control variates (in Section 3) and then extend to setting where unknown functions parameterize control variates (in Section 4). These contributions are themselves of independent interest in control variate theory.
Equipped with these results, we show that the variance of hybrid rewards is smaller than observed rewards (Theorem and Theorem 3). We then propose a method that uses hybrid rewards instead of observed rewards for estimating reward function, resulting in tight confidence bounds and, hence, lower regret. We introduce the notion of Auxiliary Feedback Compatible (AFC) bandit algorithm. An AFC bandit algorithm can use hybrid rewards instead of only observed rewards. We prove that the expected instantaneous regret of any AFC bandit algorithm using hybrid rewards is smaller by a factor of O((1 - ) compared to the same AFC bandit algorithm using only observed rewards, where p is the correlation coefficient of the reward and its auxiliary feedback (Theorem 2 and Theorem 4). Our experimental results in different settings also verify our theoretical results (in Section 5).
1.1 Related work
Several prior works use additional information to improve the performance of bandit algorithms. In the following, we discuss how auxiliary feedback differs from side information and side observation.
Several works use context as side information to select the best action to play. This line of work is popularly known as contextual bandits (Li et al., 2010; Chu et al., 201 I; Agrawal and Goyal, 2013; Li et al., 2017). Here, the mean reward of each arm a function of context and often parameterized, e.g.. linear (Li et al., 2010; Chu et al., 201 I; Agrawal and Goyal, 2013), GLM (Li et al., 2017), and non-linear (Valko et al., 2013). These contexts are assumed to be observed before action is taken. However, we consider problem where additional information is correlated with rewards that can only be observed after selecting the action.
Side Information:
Several works consider the different side observations settings in the literature, e.g.. stochastic (Caron al., 2012), adversarial (Mannor and Shamir, 2011; Kocák et al., 2014), graph feedback (Alon et al., 2015; Wu et al., 2015; Alon et al., 2017), and cascading feedback (Verma et al., 2019, b02 Side observations represent the additional information available about actions that the learner does not select. Auxiliary feedback is different from side information as it is available only for selected action and provides more information about the reward of that action.
Side Observations:
Auxiliary Feedback: We use auxiliary feedback as control variates, which are used extensively for variance reduction in Monte-Carlo simulation of complex systems (Lavenberg and Welch, 1981; Lavenberg et al., 1982; James, 1985; Nelson, 1989, 1990; Botev and Ridder, 2017; Chen and Ghahramani, 2016). Recent works (Kreutzer al., 2017: Vlassis et al., 2021; Verma and Hanawal, 2021) and (Sutton and Barto, 2018, Chapter 7.4) have exploited the availability of these control variates to build estimators with smaller variance and develop algorithms that have better performance guarantees. The closest work to our setting is Verma and Hanawal (2021). However, they only consider -onapaaamtteri setting with finite number of actions. We thus consider more general bandit setting with large (infinite) actions and allow function to parameterize auxiliary feedback.
2

---

2
Problem setting
We consider novel parameterized bandits problem in which the learner can observe auxiliary feedback correlated with the observed reward. In this problem, a learner has been given an action set, denoted by X C IRd where 2 1. At the beginning of round the learner selects an action æt from action set X. Then, the environment generates a stochastic reward yr = f(+)) + E for the selected action 24, where f E - is an unknown reward function and E, is a zero-mean Gaussian noise with variance o². Apart from the stochastic reward yt. the environment generates q of auxiliary feedback. The i-th auxiliary feedback is denoted by wy,i = 9: (x(e) + eY,, where 9: : Rdd - and er, is zero-mean Gaussian noise with variance o The multiple correlation coefficient of reward and its auxiliary feedback denoted by p and assumed be the same across all actions.
The optimal action (denoted by x*) has the maximum function value, i.e., x= E argmaxzex f(x). After selecting an action It. the learner incurs a penalty (or instantaneous regret) rt, where r = f(=*) - [(zz). ) Since the optimal action is unknown, we sequentially estimate the reward function using available information on rewards and associated auxiliary feedback for the selected actions and then use it for choosing the action in the following round. Our goal is to learn a sequential policy that selects actions such that the total penalty (or regret) incurred by the learner is as minimum as possible. After T rounds, the regret of sequential policy æ that selects action in the round f is given by
(x) = Σ - f(x))-
policy ı is good policy if it has sub-linear regret, i.e., lim the policy ı will eventually learn to recommend the best action.
0. This implies that
3 Known auxiliary feedback functions
We first focus on simple case where all auxiliary feedback functions are assumed to be known. This assumption is not very strict in many applications as the learner can construct auxiliary feedback such that its mean value known beforehand (see Kreutzer et al. (2017), Vlassis al. (2021), and Chapter 12.9 of Sutton and Barto (2018) for such examples). When auxiliary feedback functions are unknown, we can estimate them using historical data additional samples of auxiliary feedback. However, it will have some penalty in the performance (more details are in Section 4 and Section 5).
The first challenge face is how to exploit auxiliary feedback get better reward function estimator. To resolve this, we extend control variate theory (Nelson, 1990) to the problems where a function can parameterize control variates. This contribution is itself of independent interest.
3.1 Control variate
Let μ be the unknown variable that needs be estimated and y be its unbiased estimator, i.e.. E [y] = p.. Any random variable w with a known mean value (w) can be treated as a control variate for y if is correlated with y. The control variate method (Nelson, 1990) exploits errors in estimates of known random variables to reduce the estimator's 's variance for the unknown random variable. This method works as follows. For any choice coefficient 3, define a new random variable as
= y
3(w w) Note that is also an unbiased estimator of μu (i.e., E [z]] = 11) as
E ||] = E [v]
/E [w w) = /4 3(T [w] w)
8(w w) = p.
Using properties of variance and covariance. the variance of 2 is given by
( = V (v) + 32V (w) 2.3Cov (y,, w.)
The variance of 2 minimized by setting 3 to 3+ = Cov(y, w) (w) and the minimum value is (1 - y2 (v), where م Cov(y, w)/ (w)) (y) is the correlation coefficient of y and w. We exploit this variance reduction design reward function estimator with tight confidence bounds.
(w)V
3.2 Auxiliary feedback as control variates
Since the auxiliary feedback functions are known, we define a new variable using the reward sample and its auxiliary feedback. We refer to this variable as 'hybrid reward.' The hybrid reward definition
3

---

is motivated by the control variate method, except the control variate is parameterized by function in our setting. As i is the tt auxiliary feedback observed with reward ys, the hybrid reward for reward (ys) with its y auxiliary feedback {w.,; 1 is defined by
9 25.9 = ys Σ (uss, 9:( Us -w-. 9,)
and G (Bi,..., BB,) Let Eww R1x be the covariance matrix among auxiliary feedback and Byw R be the vector of covariance between the reward and each of its auxiliary feedback. Then, the variance of Zx.q is minimized by setting the coefficient vector /3 to 9 = Sww yyw. and the minimum value is (1 - p²)a², where p² == -yyw>ie yww/o" /o" is the multiple correlation coefficient of reward and its auxiliary feedback.
where w, = (w..1 Ws 9s (g) (zx), ................................ Bo (2.))),
However, Eww and "sw can be unknown in practice and need to be estimated to get the best estimate for 9 to achieve maximum variance reduction. In our following result, we drive the best linear unbiased estimator of ,3 (i.e., Br) using t observations of rewards and their auxiliary feedback.
Lemma 1. Let I. > 4 2 E N and Jt be the estimate of function I which uses all information available at the end of round t, i.e,, {I,, Vs.
wz s=1 ) Then, the best linear unbiased estimator of (*
B, = (:, W. W. Y,. where W. is at x q matrix whose th row is (w, ga) and Y, (y1 f.(f)))....... fe ft())))
The proof follows after doing some manipulations in Eq. (2) and then using results from linear regression theory. The detailed proof of Lemma I and all other missing proofs given in the supplementary material. After having a new observation of reward and its auxiliary feedhack, the best linear unbiased estimator of 3 is re-estimated. If Enow oyw are known, we can directly use them to estimate 3 by replacing W, W. with Eww and W, Y, with Tyw in Lemma 1. The following result describes the properties of the hybrid reward when B is replaced by Br in Eq. (2).
Theorem 1. Let t > q + E N. If 3e as defined in Lemma is used to compute hybrid reward 2s.4 for any & S 1 N, then E. [=x.a] = (xr) and V (Za.g) = (1 (1++-0)) (1 - p²)0²
The key takeaways from Theorem I are as follows. First, the hybrid reward using 3, is an unbiased estimator of reward function and hence, we still use it to estimate the reward function f. Second, 2) of maximum possible variance reduction) when 3r is used for constructing hybrid reward in Eq. (2).
there is a less reduction in variance (i.e., by a factor (t - 2t
The variance reduction (given in Theorem 1) depends on the auxiliary feedback via two terms: 1-22 and p² (defined in Line 142). Setting q = 1 gives the minimum value for r-ー-z. but p² for q = 1 will also be small as it only considers one auxiliary feedback, and hence maximum variance reduction will not be achieved. As we increase the number of auxiliary feedback, p² increases, leading to more variance reduction. However, the term r-q-2
I-2 increases at the same time, which can negate the
variance reduction achieved by smaller p². Hence, keeping the number of auxiliary feedback used for hybrid reward small is important. A simple method for selecting a subset of auxiliary feedback (Lavenberg et al., 1982) works as follows: select the auxiliary feedback whose sample correlation coefficient with reward is the largest. Then, select the next auxiliary feedback whose sample partial correlation coefficient with reward was the largest given the first auxiliary feedback selected. Keep repeating the process until there is a variance reduction using additional auxiliary feedback.
3.3 Linear bandits with known auxiliary feedback functions
To highlight the main ideas, we restrict the linear bandit setting in which the reward and auxiliary feedback functions are linear. In this setting, a learner selects an action xe and observes a reward Ve x.. 8* Es, where 8* E Rd (d 1) is unknown and e, is the zero-mean Gaussian noise with known variance a². The learner also observes q auxiliary feedback, where i-th auxiliary feedback is denoted by Wr, x oth + +Z,, Here, Ot. E Rd is known and eY,, is the zero-mean Gaussian noise with unknown variance o Our goal is to learn policy that minimizes regret as defined in Eq. (1). We later extend our method for non-linear reward and auxiliary feedback functions in Section 4.3.

---

Let I be the d x d identity matrix, Vi = Ex=l Tesl and V. - V AI, where À > 0 is the regularization parameter that ensures matrix Vi is positive definite matrix. The notation ||x]|| denotes the weighted 12-norm of vector IR4 with respect to positive definite matrix A E Rdxd
As shown in Theorem 1, the hybrid rewards an unbiased reward estimator with a smaller variance than observed rewards. Thus, hybrid rewards lead to tighter confidence bounds for parameter #* than observed rewards. We propose a simple but effective method exploit correlated auxiliary feedback. i.e,, using hybrid rewards to estimate reward function instead of observed rewards.
Using this method, adapt the well- linear bandit algorithm OFUL (Abbasi- Yadkori et al., 2011) to our setting and named this algorithm OFUL-AF. This algorithm works as follows. It takes > 0 as imput and then initializes VI Xl and sets 0f = Oga as initial estimate of parameter 6*. The superscript 'z' in 0j implies that hybrid rewards are used for estimating 0*, At the beginning of round 6, the algorithm selects an action Dy that maximizes the upper confidence bound of the action's reward, which is a sum of the estimated reward for the action (x 0:) and a confidence bonus of | In the confidence bonus, the first term (af) is slowly increasing function in whose value is given in Theorem 2, and the second term
decreases to zero as increases.
OFUL-AF Algorithm for Linear Bandits with Auxiliary Feedback
1: Input: À >>0 0
2: Initialization: Vi - AI and Oj = -Oee
3: for 1,2,.... do
4: Select action Ia argmaxxex* (xT0; + aon 1|<||17
5: Observe reward and its auxiliary feedback {wr,s)
6: Ift > q 2, compute upper bound hybrid reward's sample variance (Vz,,) or else Dz,, = 0²
7:
If S q 2 or Vz,e o², set B: = or else compute 3r using Lemma 1
8:
Vs - f E N: compute 25.q using }3 in Eq. (2)
9: Set V.+1 = V. + NTt 0 = V Ei= 2z2s.g
end for
After selecting an action It. the algorithm observes the reward yr with its associated auxiliary feedback (1,, It computes the upper bound on sample variance of hybrid reward (denoted by 22 if > q + 2 or else is set to o² and then checks two conditions. The first condition (i.e., S + guarantees the sample variance well-defined. Whereas the second condition (i.c.. Fe. > 0²) ensures the algorithm at least be as good as OFUL because V/,, can be larger than o² due to the overestimation in initial rounds. If both conditions Σ q + 2 and D2.. 2 o² fail, the value of A is re-computed as defined in Lemma 1. The updated } is then used to update all hybrid rewards, ie.. Zz,0: Vs < E N. Finally, the values of V and dz_ are updated as V V. + xą and 0. Vi+1 Σt Zz which are then used to select the action in the following round. When G for all hybrid rewards, hybrid rewards are the same the observed rewards, and hence OFUL--AF is the same as OFUI.
The regret analysis of any bandit algorithm hinges bounding the instantancous regret for each action. The following result gives an upper bound on the instantaneous regret of OFUL-AF.
Theorem With probability of at least 1 28, the instantaneous regret of OFUL-AF in round is
(OFUL-AF s (a( +x1/25) ||salllz
where og. = /min (a², Dz, an 110+1/2 S S, and 0t = v dlog 1+1R1A For > + 2 and & Dz a E (OFULLFF) C (x=جيي= r. (.(FUU))) Here, Ô hides constant terms.
'Let iz.a be the sample variance estimate of hybrid rewards (details in Appendix A.2). Then, Pz,t (e- P).
xi
where xi d.c denotes 100(1 5hth percentile value of the chi- squared distribution with t degrees of freedom.
5

---

The proof follows by bounding the estimation error of the parameter 8* when the estimation method uses auxiliary feedback. This result shows that auxiliary feedback leads better instantaneous regret upper bound and better regret (as defined in Eq. (1)) than the vanilla OFUI. algorithm. Since the improvement in instantaneous regret increase with f. having single constant to compare with regret of OFUL may lead to weaker regret upper bound than the sum of all instantaneous regret.
4 Estimated auxiliary feedback functions
Auxiliary feedback functions may be unknown in many real-life problems. However, the learner can construct an unbiased estimator for the auxiliary feedback function using historical data or acquiring more samples of auxiliary feedback. But these estimated functions offer a lower variance reduction than known auxiliary functions. To study the effect of using the estimated auxiliary feedback functions on the performance of bandit algorithms, we borrow some techniques from approximate control variate theory (Gorodetsky et al., 2020; Pham and Gorodetsky, 2022) as we discussed next.
4.1 Approximate control variates
Let y be unbiased estimator of an unknown variable μ and random variable with known estimated mean (w²) be a control variate of y. As long as the known estimated mean is an unbiased estimator of w, one use to reduce the variance of y follows. For any choice of coefficient Se. define a new random variable as 2, = y 3ew where ã = w we- Since w. is an unbiased estimator of w, it is straightforward to show that z. is also unbiased estimator of y.
By using properties of variance and covariance, the variance of ze is given by
Var(ze) = Var(y) + Cov w) - 2,3 w).
The variance of zg is minimized by setting Be to 3 Cov( w) - Covv(y, w) and the minimum value of Var(ze) is (1 - Var(y), where Pe Cov (y, w) (Cov(w, -) //ar(y)) Cov(y, w))
4.2 Auxiliary feedback with unknown functions as approximate control variates
We now introduce a new definition of hybrid reward that uses estimated auxiliary feedback functions. Let Wggi be the tth auxiliary feedback observed with reward y, and Je,s be the unbiased estimator of function 9:- Then, the hybrid reward with estimated auxiliary feedback functions is defined by
Ze,5.9 = Baslwa,t ge,s(xx)) = - (w. ge..)
(3)
where w, = (Wa.1-.... We.g); Ie.s (x.), Se.g (x, (2r)),, and Br = -Se,1:...,, Be,q) Let Eow E Rax4 denote the covariance matrix among centered auxiliary feedback (i.e., W. w, ge.e). -
and y Rax1 denote the vector of covariance between reward and its centered auxiliary feedback. Then, the variance of Ze,a.9 is minimized by setting the Br to 3 Dow and the minimum value of Var(ze,,,g) is (1 (1-p2)o², where p Ty 2
The definition of hybrid reward given in Eq. (3) is very flexible and allows different estimators to estimate auxiliary feedback functions. The only difference among these estimators is how they partition the available samples of auxiliary feedback to estimate auxiliary function 9i- As no optimal partitioning strategy is known, sampling strategy for our setting where finite samples of auxiliary feedback are available. Both strategies proven be asymptotically optimal (Gorodetsky et al., 2020), implying the variance reduction is asymptotically the same as if auxiliary feedback functions are known.
adopt the Independent Samples (IS) and Multi-Fidelity (MF)
IS and MF sampling strategy: Let and s; J be the sample sets used for estimating functions
and 9:, respectively. Then, for the IS sampling strategy, (s; \ s) n (sy \ s) Ø for * j. i.e., the extra samples used for estimating the function 9: are unique. Whereas, for the MF sampling strategy, 8; د s' and m s' Ø for i & j. i.e., the estimation of function gi uses the samples that were used for estimating function 9i-1 with some additional samples. Refer to Fig. 1 for the visual representation of both sampling strategies. After adopting Theorem and Theorem 4 from

---

92
91
92
9q
fands Mggettlm
Agurttiin
Sampling Strategy
MF Sampling Strategy
Eraiooment
Texirosmann
Left two figures: Visualization of IS and MF sampling strategies. Each column represents samples used for estimating function (written at the top), and the same color is used to show shared samples among auxiliary function estimation. Right two figures: Interaction between AFC bandit algorithm and environment. AFC bandit algorithm that only uses observed rewards (second from right), and AFC bandit algorithm that also uses auxiliary feedback as hybrid rewards (rightmost).
Figure I:
Gorodetsky et al. (2020) our setting, we can further simplify Ewe and Ty when and MF sampling strategies (denoted by e) are used for estimating auxiliary feedback functions as follows:
Ewe = wow Fe)/t and dyu = (diag (F.) d yyw)/t,
where denotes the number of reward observations with auxiliary feedback, diag( (A) represents a vector whose elements are the diagonal of the matrix A, and denotes element-wise product. The zj-th element of matrix Fe E R is
(Tr 1)(r) 1))/(ra))))
if j and if f and e = MF otherwise,
fe.aj = -1
(min(r, (n. 11)0-m)mmnni m/mi(((.r))
(re 1)/r/
where r; +g+i is the ratio between the total number of samples used for estimating function gi by sampling strategy and the total number of samples used for estimating f.
Since Eww and Tyu may be unknown, they must be estimated to get the best estimate for 3 Our following result gives the best linear unbiased estimator 3e (i.e., 3e..) that uses observations of rewards and their auxiliary feedback with estimated auxiliary feedback functions.
Lemma 2. Let > q E N, is the sampling strategy, and fe be the estimate of function at the end of round which uses {xs, Mos w.)
) je=1" Then, the best linear unbiased estimator of B is
Bes = (W, W. F2) (diag (Fe) o W.W Yi).
where W. is a x q matrix whose 5h row is w. 9e.s and Y, (y1 fe(1)). ...1))....3 fx()))
After adopting matrix manipulation tricks from Pham and Gorodetsky (2022) to our setting, the proof follows similar steps as the proof of Lemma 1. We characterize the properties of the hybrid reward that uses either IS or MF sampling strategy for estimating auxiliary feedback functions.
Theorem 3. Let I. q + E N and is the sampling strategy. If Br, defined in Lemma is used to compute hybrid reward Ze,s.g for any 8 S N, then E. [Ze,a.g] = =(xx)) and V (Ze,a.) =
2-q-2) (1 (1- -2) where a(IS) = 1, a(MF) = ifr,= = Vi 21. when using MF sampling strategy for estimating auxiliary feedback frretbackfunntionss functions.
(1+ ale]y
The key takeaways from Theorem are as follows. First, the hybrid reward with estimated auxiliary feedback is still an unbiased estimator, so one can use it to estimate the reward function f. Second, there is a potential loss in variance reduction as it has an extra multiplicative factor a(e) and p² < p².
Remark 1. As samples for estimating auxiliary functions increase compared to the reward function, the variance reduction from IS and MF sampling strategy converges the reduction achieved using known auxiliary functions. As Vi Eew will become Eww. Uyw will become Tyw, and hence P = p² as Vi rg + cc.
oo, then F. 1 1xxg- It is now straightforward to see that
Remark The and MF sampling strategies are shown to be asymptotically optimal (Gorodetsky et al., 2020), i.c., the variance reduction achieved by both strategies is asymptotically the same if

---

auxiliary feedback functions are known. However, both sampling strategies are useful in different applications, e.g., the IS sampling strategy suits the problems in which different auxiliary feedback can be independently sampled. In contrast, the MF sampling suits the problems where auxiliary feedback can not be sampled independently.
4.3 Parameterized bandits with estimated auxiliary feedback functions
We now consider the parameterized bandit setting described in Section 2, where the reward and auxiliary feedback function can be non-linear. To exploit the available auxiliary feedback in linear bandits, we propose a method in Section 3.3 that uses hybrid reward in place of rewards to get tight upper confidence bound for the estimator of unknown reward function and hence smaller regret as compared to the vanilla OFUL due to the smaller variance of the hybrid rewards. We generalize this observation and introduce the notion of Auxiliary Feedback Compatible (AFC) bandit algorithm.
Definition (AFC Bandit Algorithm). Any bandit algorithm 2 is Auxiliary Feedback Compatible if: (i) 2l can use correlated reward samples to construct upper confidence bound for reward function and (ii) with probability 1 - 8, its estimated reward function fi² has the following property:
1f((x) - f (=)) S oh(z, O,) + 1(2, Ot),
where X. o² is the variance of Gaussian noise in observed reward, and O₂ denotes the observations of actions and their rewards with the parameters of Q at the beginning of round t.
As the estimated coefficient vector uses all past samples, the resultant hybrid rewards become correlated due to using this estimated coefficient vector. Bandit algorithms like UCB1 (Auer et al., 2002) and kI-UCB (Cappé al., 2013) are not AFC they need independent reward samples to construct upper confidence bounds. In contrast, bandit algorithms like OFUL (Abbasi- Yadkori et al., 2011), Lin- UCB (Chu et al., 201 1), UCB-GLM (Li al., 2017), IGP-UCB, and GP-TS (Chowdhury and Gopalan, 2017) are AFC as they all use techniques proposed in Abbasi- Yadkori et al. (201 1) for building the upper confidence bound, which does not need reward samples be independent.
As AFC bandit algorithms use the noise variance of observed reward for constructing the confidence upper bound, they can also exploit available auxiliary feedhack by replacing reward with its respective hybrid reward as shown in Fig. (rightmost figure). We next give an upper bound on the instantancous regret for any AFC bandit algorithm that uses hybrid rewards instead of observed rewards.
Theorem 4. Let A be an AFC bandit algorithm with (x) f(x) I ah(x, O.) + 1(x, O.) and Ve,e, be the upper bound sample variance of hybrid reward, whose value is set 0² for S 4 2. Then, with a probability of at least - 28, the instantaneous regret of 21 after using hybrid rewards (named 2- M-AF) reward function estimation in round is
Tr. (2F)FF S 2 min(a, (De,z))* à )h(a, O.) + Oxx,
where {IS, ME, KF), and KF denotes the case where auxiliary functions are known. For t. > 4+2
and De,2,t < 02, E ([ <Ō ((1 ((=11-000))))
p2) re((1) where a(KF) =
1-9-3
After using Theorem and Theorem 3 to replace the variance of hybrid reward, the proof follows similar steps as the proof of Theorem We have given more details about the values of h(x, O,) and ((r, O.) for different AFC bandit algorithms in Table 1.
Table 1: Values of (ax, O.) and 1(x, Ox) for different AFC bandit algorithms
AFC bandit algorithm
M(, Oi)
1(x, O.)
OFUL. KAbbasi-Yadkonf et al., 2011)
d dog
14122/A 8
||ا||
5 ||rll,
Lin-UCB (OFUL for contextual setting)
d log
14412/A
|
S |
||lll
GLM-UCB (Li et al., 2017)
2 log(1 (1 + 2t/d) + log(1/))
IGP-UCB (Chowdhury and Gopalan, 2017)
/2(m--1 + 1 +-1+loge (0g)
Bo,-1(2)
8

---

5
Experiments
To validate our theoretical results, we empirically demonstrate the performance gain due to auxiliary feedback in different settings of parameterized bandits. We repeat all our experiments 50 times and show the regret as defined Eq. (1) with 95% confidence interval (vertical line on each curve shows the confidence interval). Due to space constraints, the details of used problem instances are given Appendix A.5 of the supplementary material.
Comparing regret with benchmark bandit algorithms: We considered three bandit settings for our experiments: linear bandits, linear contextual bandits, and non-linear contextual bandits (details are given in Appendix A.5). The formal setting of a contextual bandits with auxiliary feedback is given in Appendix A.4. We used the following existing bandit algorithms for these settings: OFUL LAbbasi-Yadkon et al., 201 1) for linear bandits, Lin-UCB (Chu et al., 2011) for linear contextual bandits, and Lin-UCB with the polynomial kernel (which we named NLin-UCB, for non non-linear contextual bandits. We compare the performance of these benchmark bandit algorithms with four different variants of our algorithms. The first variant assumes the auxiliary feedback functions known (highlighted by adding '-AF' to the benchmark algorithms). When auxiliary feedback functions are unknown, we use IS and MF sampling strategy while maintaining r = 2 (i.e., getting one extra sample of auxiliary feedback in each round). The IS and MF sampling strategies are the same when only one auxiliary feedback exists. Since we only use one auxiliary feedback in our experiments, we highlight this variant by adding '-I//MF" to the benchmark algorithms. When IS and MF sampling strategies are used, one needs to update the auxiliary feedback functions in each round to get better estimators. However, it leads the re-computation of all variables that needed for updating the hybrid rewards, which is not needed when auxiliary feedback functions are fixed. Therefore, we consider two more computationally efficient variants for the unknown auxiliary functions setting. One variant assumes the knowledge of biased auxiliary feedback, i.c., g:(z) + Ey available instead of gi (2) (highlighted by adding '-BE' to the benchmark algorithms). Another variant assumes that some initial samples of auxiliary feedback are available, which are used to get the auxiliary feedback function estimator. We highlight this variant by adding '-EH' to the benchmark algorithms. All variants with given parameters perform better than benchmark bandit algorithms (see Fig. 2a, Fig. 2b, and Fig. 2c). We observe the expected performance among these variants as the variant with known auxiliary feedback function outperforms all other variants. At the same time, IS/MF sampling strategy- based variant outperforms the other two heuristic variants for the setting of unknown auxiliary feedback function.
Regret vs. different biased estimator: To know the effect of bias in auxiliary feedback (i.e., Eg) in the mean value of auxiliary feedback, we run an experiment with the same linear contextual bandits experiment setup mentioned above. To see the variation regret, we set Eg = (1, 0.2, 0.1, 0.07, 0.05). As shown in Fig. 2d, the regret increases with an increase in bias and even starts performing poorly than UCB. This experiment demonstrates that as long as the bias in auxiliary feedback within a limit, there will be an advantage to using this computationally efficient variant.
Regret vs. number of historical samples of auxiliary feedback: Increasing the number of historical samples of auxiliary feedback for estimating the auxiliary feedback function reduces the error in its estimation, leading better performance. To observe this, we use estimators using different numbers of auxiliary feedback samples, i.c., n& = {5, 7, 10, 15, 20} in linear contextual bandits setting. As expected, the regret decreases with an increase in auxiliary feedback samples, but using an estimator with few samples even performs poorly than Lin-UCB, as shown in Fig. 2e.
Regret correlation coefficient: As theoretical results imply that the regret decreases when the correlation between reward and auxiliary feedback increases. To validate this, we used problem instances with different correlation coefficients in linear contextual bandits setting. As expected, we observe that the regret decreases as the correlation coefficient increases, as shown in Fig. 2f.
6 Conclusion
This paper studies a novel parameterized bandit problem in which a learner observes auxiliary feedback correlated with the observed reward. We first introduce the notion of 'hybrid reward,' which combines the reward and its auxiliary feedback. To get the maximum benefit from hybrid reward, we treat auxiliary feedback control variate and then extend control variate theory to a setting
9

---

Regret
Reg ret
OHUL EP die
Uniuce L1u-310
Kin LCC LS---10
DmUL-42 m D.1)
12-
GHUL isme Iim
Unc I5M 21
Rounds
Rounds
Rounds
(a) Linear Bandit
(b) Linear Contextual Bandits
(c) Non-linear Contextual Bandits
Linuic
LINUED DI
Livicc 0.22
UNUIB-D DEON -1
**- Livace an My
Livaci--E by -000))
Regres
in -0.50) unsas
Regres
Livith
Regret
14
3000
Rounds
Rounds
Rounds
(d) Biased Estimator
(c) Estimator from historical data
(f) Influence of correlation
Figure Top row: Comparing regret of different variants with their benchmark bandit algorithms in different settings. Bottom row: Regret vs. different biases in Lin-UCB-BBI BE (left figure), regret vs. number of historical samples of auxiliary feedback Lin-UCB-ER (middle figure), and regret of Lin-UCB-AF vs. varying correlation coefficients of reward and its auxiliary feedback (right figure).
where a function can parameterize control variates. Equipped with these results, we show that the variance of hybrid rewards is smaller than observed rewards. We then use these hybrid rewards to estimate the reward function, leading to tight confidence bounds and hence smaller regret. We have proved that the expected instantaneous regret of any AFC bandit algorithm after using hybrid rewards improved by factor O((1 p²)
2²)b) ), where p the correlation coefficient of the reward and its auxiliary feedback. Our experiments also validate our theoretical results. An interesting future direction is to extend these results to bandit settings with heteroscedastic and Gaussaani noise.
Acknowledgments and Disclosure of Funding
DesCartes: this research is supported by the National Research Foundation, Prime Minister's Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme.
References
Aleksandrs Slivkins. Introduction to Multi-Armed Bandits. Foundations and Trends@ in Machine Learning, 2019.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. -ontextual- -andit Approach to Personalized News Article Recommendation. In Proc. WWW, pages 661-670 2010.
Wei Chu, Lihong Li, Lev Reyzin, and Robert E Schapire. Contextual Bandits with Linear Payoff Functions. In Proc. AISTATS, pages 208-214, 2011.
Yasin Yadkori Dávid Pál, and Csaba Szepesvári. Improved Algorithms for Linear Stochastic Bandits. In Proc. NeurIPS, pages 2312-2320, 2011.
Shipra Agrawal and Navin Goyal. Thompson Sampling for Contextual Bandits with Linear Payoffs. In Proc. ICML, pages 127-135, 2013.
10

---

Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric Bandits: The Generalized Linear Case. In Proc. NeurIPS, pages 586-594 2010.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably Optimal Algorithms for Generalized Linear Contextual Bandits. In Proc. ICML, pages 2071-2080, 2017.
Kwang-Sung Jun, Aniruddha Bhargava, Robert Nowak, and Rebecca Willett. Scalable Generalized Linear Bandits: Online Computation and Hashing. In Proc. NeurlPS, pages 99-1099, 2017.
Michal Valko, Nathan Korda, Rémi Munos, llias Flaounas, and Nello Cristianini. Finite-time Analysis of Kernelised Contextual Bandits. In Proc. UAI, pages 654-663, 2013.
Sayak Ray Chowdhury and Aditya Gopalan. On Kernelized Multi-armed Bandits. In Proc. ICML, pages 844-853, 2017.
Noga Alon, Nicolo Dssa-Biacchi, Ofer Dekel, and Tomer Koren. Online Learning with Feedback Graphs: Beyond Bandits. In Proc. COLT, pages 23-35, 2015.
Yifan Wu, András György, and Csaba Szepesvári. Online Learning with Gaussian Payoff's and Side Observations. In Proc. NeurIPS, pages 1360-1368, 2015.
Stephen Lavenberg and Peter Welch. Perspective on the Use of Control Variables Increase the Efficiency of Monte Carlo Simulations. Management Science, pages 322-335, 1981.
Stephen S Lavenberg. Thomas L Moeller, and Peter D Welch. Statistical Results on Control Variables with Application to Queucing Network Simulation. Operations Research, pages 182-202, 1982.
Arun Verma and Manjesh K Hanawal. Stochastic Multi-Armed Bandits with Control Variates. In Proc. NeurlPS, pages 27592-27603, 2021.
Barry Nelson. Control Variate Remedies. Operations Research, pages 974-999- 1990.
Julia Kreutzer, Artem Sokolov, and Stefan Riezler. Bandit Structured Prediction for Neural Sequence-to-Sequence Learning. In Proc. ACL, pages 1503-1513, 2017.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Nikos Vlassis, Ashok Chandrashekar, Fernando Amat Gil, and Nathan Kallus. Control Variates for Slate Off-Policy Evaluation. In Proc. NeurlPS, pages 3667-3679, 2021.
Stephane Caron, Branislav Kveton, Mare Lelarge, and S Bhagat. Leveraging Side Observations in Stochastic Bandits. In Proc. UAI, pages 141-151,20 2012.
Shie Mannor and Ohad Shamir. From Bandits to Experts: On the Value of Side-Observations. In Proc. NeurIPS, pages 884-692, 2011.
Tomáš Kocák, Gergely Neu, Michal Valko, and Rémi Munos. Efficient learning by implicit exploration in bandit problems with side observations. In Proc. NeurlPS, pages 613-621, 2014.
Noga Alon, Nicolo Cesa BisacBianchi, Claudio Gentile, Shie Mannor, Yishay Mansour, and Ohad Shamir. Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback. SIAM Journal on Computing, pages 1785-1826, 2017.
Arun Verma, Manjesh K Hanawal, Csaba Szepesvári, and Venkatesh Saligrama. Online Algorithm for Unsupervised Sensor Selection. Proc. AISTATS, pages 3168-3176, 2019.
Arun Verma, Manjesh K Hanawal, and Nandyala Hemachandra. Thompson Sampling for Unsupervised Sequential Selection. In Proc. ACML, pages 545-566 2020a.
Arun Verma, Manjesh K Hanawal, Csaba Szepesvári, and Venkatesh Saligrama. Online Algorithm for Unsupervised Sequential Selection with Contextual Information. In Proc. NeurIPS, pages 778-788, 2020b.
B. P. James. Variance Reduction Techniques. Journal of the Operational Research Society, pages 525-530, 1985.
11

---

Barry L Nelson. Batch size effects on the efficiency of control variates in simulation. European Journal of Operational Research, pages 184-196, 1989.
Zdravko Botev and Ridder. Variance Reduction. Wiley statsRef: Statistics reference online, pages 1-6, 2017.
Yutian Chen and Zoubin Ghahramani. Scalable Discrete Sampling Multi-Armed Bandit Problem. In Proc. ICML, pages 2492-2501, 2016.
Alex A Gorodetsky, Gianluca Geraci, Michael S Eldred, and John D) Jakeman. A Generalized Approximate Control Variate Framework for Multifidelity Uncertainty Quantification. Journal of Computational Physics, page 109257, 2020.
Trung Pham and Alex A Gorodetsky. Ensemble Approximate Control Variate Estimators: Applications to MultiFidelity Importance Sampling. Journal on Uncertainty Quantification, pages 1250-1292, 2022.
Peter Auer, Nicolo Cesa-Bine Bianchi, and Paul Fischer. Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning, pages 235-256, 2002.
Olivier Cappé, Aurélien Garivier, Odalric-Ambrym Maillard, Rémi Munos, and Gilles Stoltz. Kullback-Leibler Upper Confidence Bounds for Optimal Sequential Allocation. The Annals of Statistics, pages 1516-1541, 2013.
F Hayashi. Econometrics. Princeton University Press, 2000.
Sara A Van De Geer. Estimation. Encyclopedia of Statistics in Behavioral Science, pages 549-553, 2005.
Bruce Schmeiser. Batch Size Effects in the Analysis of Simulation Output. Operations Research, pages 556-568, 1982.
12

---

A Supplementary material
A.1 Missing proofs related to auxiliary feedback
Results from linear regression
We first state results for linear regression that will use in the subsequent proofs. Consider the following regression problem with samples and g features:
2, x + Eat i
where 2e R is the Sh target variable, 2. (Zel...., xaq) R is the 8th feature vector, 0 129 is the unknown regression parameters, and a is a normally distributed noise with mean and constant variance o². The values of noise E, form an IID sequence and are independent of xg. Let
21
F11
Ilg
E1 :
Ze
X₁
and
Et
X11
Etq
Then, the best linear unbiased estimator of 0 is 0 (x, x,) X, Z, which has the following finite sample properties. Fact 1. The following are the finite sample properties of the least square estimator 0g:
0. X 0
(unbiased estimator) (expression for the variance)
2. Var(0.|X) = (X, X, 11 and
3. Var(O.. X,) o²
o² (X, X
(element-wise variance)
where (X, X) ) is the ii elementnt of the matrix (X.X)-1.
In the above result, the first two properties are from Proposition 1.1 of Hayashi (2000), whereas the third property is from Van De Geer (2005). The following result gives the finite sample properties of the estimator of noise variance o². Fact 2. (Hayashi, 2000, Proposition 1.2) Let o7
x 0.)² 2 be estimator of o² and t q (so that a? is well defined). Then, o? is an unbiased estimator of a i.e., E X. = o².
-
E.
Using the Schur complement, have the following results about the inverse of the block matrix.
CCC
Fact 3. Let
block matrix, where E RR \ (0), B, C. D are respectively 9. q X 1, and X q matrices real numbers. Then, GTi = 1 + t B(t CB)
C D
Control variates theory
Let y be the random variable of interest with unknown mean There are g control variates correlated with y, where 2thh control variate has mean w; and its 4th observation is denoted by W.,s. For any E (1, (1....,(), define variable 2, using th observation of ys and its control variates follows:
2, Us (w, w)B,
where w, (W..11.... Wa,g) and (w) ... wg) The above equation can be re-written y. 2, (w, w)B.
Under the assumption of being unbiased estimator of μ,, write y, follows:
V/ (w, w)B E2,s-
where ... Ez,t E2,t are IID and have zero mean Gaussian noise with variance (1 p²)0² Let
t/1
wi
[Ex,1
Y, =
W =
(HL
and Ez, =
1/
w.
Ex,
13

---

The best linear unbiased estimator of y (W. W Fy as follows:
W Y.. c. To get usss and B+, we expand
w1
W
1/1
:
:
Wi w
W
w
w
91
W1
y1
1
:
W1
wi
W1
wi
w
wt
V/+
Σx= (w, w)
-1
Esm y/
E W. w) Ee=1 (w, - w) (w, - w)
===1
(w
wwys/
P2g. 3g
After taking first matrix from RHS to LHS and using 9
wwe have
(E w) Ex=1 (w, T w)) )
E (w, w)
E'=1 Us
B.
s=1 (w, w w)yss)
(4)
From above, we get the following equation:
112,,t +
Σ (w. w)
3r =
Σ
ys
1=1
==1
= Pz,tt =
1 Σ Us
Σ
(w, w)
Be.
t s=1
==1
Using Ay, = + + Me and w. Eim1 Wa. we get
N3,1 igg (we w)
(5)
Similarly, we have another equation as follows:
3. = i
(w. - w) + Σ (w (ww, w))
>((w (wo - w)y
Pzz1 ==1
s=1
-1
= 3 =
Σ (w T - ww)
Σ (w, w) R2.o))
/wi w
y1 juz
Using W. =
and Y =
we have
wi
y1 Pz,b.)
B (W, WW, Y,
(6)
In the following, we first state the fundamental results from the control variates theory. Fact 4. (Nelson, 1990, Theorem 1) Let O, = (Y., W Ws.g) follow a (q+1)-variat) variate normal distribution with mean vector (H, w) and {O,.... O,} be a IID sequence. Assume Pz. E. Z.. where 2, ys- (w, -.) and G. used here is given by Eq. (6), then LE [Rc.e] fl and v (Pz,t)
(1 (1- (1- (1 (1 (1+1-1-)((-
(Qy,t),
where oyw TywwTw/ol the square of the multiple correlation coefficient, o² = V (Y), and Jyw = (Cov(Y, (Y, W1).... Cov(Y, Wg)) (we have dropped the subscript observations are IID).
14

---

Auxiliary feedback as control variates
Lemma Let q 9-22+02 2 E N and ft be the estimate of function f which uses all information
available at the end of round t, i.e. {ra, Vsr waYa=1- Then, the best linear unbiased estimator of 3 is
B. (W W.) (.) ",, Yv: where Wi is at x q matrix whose 8t row is (w, 9s) and Y (y1 fe(11),...... ...... f((zz)).
Proof. Recall Eq. (2) for 8h hybrid reward with known auxiliary functtion, i.e., 2z,9 = y/ - (w, g,),3 which be re- re-written 3 2s.4 + (w, 9.) By definition, 20.9 f(x)) + E for optimal 3, where E2,a is zero-mean Gaussian noise with variance (1 p²)0²² Then, ys f(x..) + (w,- - g + Ez,s- Let yp an unknown function that maps every x to space where f()) = xxx) holds. Then we can re- re-write the above equation as follows:
ys = 1 ((x)) + (ur, - -9a)3 + E2,
Adapting Eq. (4) to our setting, we have
[i= ((x,) (pxx)) (((xa)
Fim (WW, -s)) (w, ga) (w, ga)
fo 3r
Fi F p(xx)\=
(w.)) -.)) (x(x))
E (w. -g,)ya) (0.--
E. (w, (w,
=
Let Sa is the estimated f using available information, i.e., {0a, Us. w=)s== To get best linear unbiased estimator for Br, we use the following equation from above matrix,
Σ (w, gx)
TT ()(x))))) fe
Σ w. -ga)
(w, gz) 3e Σ (w., 9v)ys
(w,- g²) T(w, - gz) B Σ (w, 9.)y, Σ (w - -g))² (p((s)) ft)
= B. (w [&) T(w,= -9o)
go)
(w. -g)) (vo ((xx))
1=1
8=1
= B
Σ
Ww 96) (w- - go)
(w, gg) (ys- - fe(x.))
8=1
(wi 9s
(1) fe((1))
Using definition fe(x=) = =p([x)] T
fr. W, =
and Y.
we get
wt 9&
91 fc(x)).
A. (W W.) W. Y.
Since the reward and its auxiliary feedback observations are functions of the selected action, we can not directly use the control variate theory due to parameterized mean values of the reward and its auxiliary feedback. To overcome this challenge, we centered the observations by function value and defined new centered variables follows:
v = ys- - f(xx), w. w - 9:: and = = 2s.4 =5.. - f(x)).
In our setting, these centered variables (vf, we. and 2..) follow mean Gaussian distributions with variance o², o = (o Gmng), and (1 - p²)o? respectively.
Theorem 1. Let t > a E If 33 as defined in Lemma is used to compute hybrid reward 2s.4 for any & St N, then E [=x.a] = f (x.) and (2s.g) = (1 + -+) (1 - )2)00
Proof. The sequence (vf. w is an IID sequence and follows a Gaussian distribution with mean 0. We now define 2x.q = ve w = v. (w, 9,)3, which can be re-written as Vo. 2 + (w, 9. Let f. be the estimated using available information. i.c., {Ze, yo, W.Y.
15

---

and hence we can write estimated 22.9 2s.4 = f((2,) and hence 25 = - Now, adapting Eq. (6) to setting and replacing estimated mean in Y, by 2g.g. 5th value of Y, is V. 25.g Ve - f(z,) (fr (a:.) f(r))) V/ f((r)). With these manipulations, get the following best linear unbiased estimator for 3
3 = (,, W W Y. which is the same defined in Lemma 1.
By adapting Fact 4 for a single sample (i.e., 2s,q) while using 3r define hybrid reward, we have
22 0 anddd
(= (1
q t 1- --22)
(1 (1- (1))
By extending the definition of IE [>5.g] we have, E 12..4 f(x))] 0 = E [Z f(x)) = - E [z = f(x))
This proofs the hybrid reward is an unbiased estimator of reward. Since variance is invariant to constant change, have
V (Z = (Fam f(x)))
(Z(gg)
+ t
(1 - (16)
2
1
(1- 131 (vo f(xx))
1- 2
+ q
(1 -1- (v.)
Since V (y+) = o², we have V (2s,g) = ( (1-
Lemma 2. Lett > q + E N, the sampling strategy, and ft be the estimate of function f the end of round which uses {e Vss we)- Then, the best linear unbiased estimator of B
Ber = (W, W. o Fa) (diag (Fe) o W,Y.). where We is a x q matrix whose t row is w. ge.s and Y, = (31 fe(x1). - fe(
Proof. Recall the th hybrid reward defined in Eq. (3) using sampling strategy e as 2,,5.q = ys (w, Be, which can be re-written as ye = وς, + (w, Be. Following similar steps as of Lemma 1, we can re-write the above equation as = fo Tx(xx)) + (w, ge. + E2.0.
W1 Je,s
111 f(((1)
Using W., e,t
and Y,
we get Be, = =WTT Wo,)) WTTY.
we 9e.s
1/1 fe(
From Appendix D and E of Gorodetsky al. (2020), we have W.,, We,t = W, W, o F. and WT Y = diag (Fa) W. Y. Using these two equality, we have
Be, (W, W, o F.)- (F.) o W,TY.) Y.).
Theorem 3. Let L. > +2 E N and e is the sampling strutegy. If Be,t as defined in Lemma is used to compule hybrid reward ze,s.g for any < E N, then E [= = f(x.) and V (Ze,a.)
(1+ 2(e) (1-4))(11))))) (1- where a(IS) 1, a(MF) - ifr =r, ifr:=r MF sampling strategy for estimating auxiliary feedback functions.
vi
.9} when using
Proof. The proof follows the similar steps as Theorem except we adapt the part (b.) of Theorem
4 from Pham and Gorodetsky (2022) instead of using Fact show the variance reduction when sampling strategy (IS or MF) is used for estimating auxiliary feedback functions.
D
16

---

A.2 Unbiased estimate of variance
Consider the following regression problem with target variable ys. which is defined as follows:
V/s (w, w),3 Es,s-
where -2, Ea,t are IID and have zero mean Gaussian noise with variance (1 -²) Let
y1 Y,
w1
62,1
Y (0) ( and Ext
W.
V1
Wi
Ex,t
Now, using Fact 1, have V (p2..) 0² ( W W WOn' where (Y (YT)) is the upper left most element of matrix (Y TyTYe Y)- (Schmeiser, 1982). Then after t observations, the unbiased variance estimator of V (Pz,e) is given by
222 = 0 (W, W.i.+
where 6²,, = 2-9-I
- Ex-1 (yo P2,))² (Nelson, 1990), which is also an unbiased variance estimator of o² (from Fact 2). Further, D2,e is also an unbiased estimator of V (fg,t), i.e., I [2 = V (Pr..) (Nelson, 1990, Theorem 1). We can adapt this approach to our setting. However when noise variance (a) is unknown, computing (W; We) may not be possible to general function f yp function may not be known. Though the setting in which (W; W) can be computed, we have to use the upper bound of variance to construct the confidence bound for reward function random sample variance estimate
be small and leads to invalid confidence bounds. Given observations, the (1-2))=.t where xi-s, denotes 100(1 8)th
upper bound of the sample variance is given by Vz2 xi percentile value of the chi-squared distribution with - 2 degrees of freedom.
A.3 Missing proof's related to regret analysis
Theorem With probability of at least 1 28, the instantaneous regret of OFUL-AF in round t is
(OFULLL)) s (0f + x1125) ||
110'1/2 S S, and an a = v /dlog (4112/A) For L > + 2 and where of = /min (0², 12)
( ((--))-))) ri (OFUL)) Here, Ô hides conslant terms.
U2 0², ((ruLOFUL-AF) Ō
Proof. When only observed rewards are used for estimating underlying unknown parameters in the linear bandit setting, i.c., 0, =V, Σt= KzYla then with probability - 6, the confidence bound (Abbasi- Yadkori et al., 2011, Theorem 1) is
10-0"11,- S s d
1 tL2
+ 1/2SS
where a2 is the variance of observed rewards given action (since the noise variance o²). To ensure the performance of OFUL-AF is good as OFUL,, only used hybrid reward samples for estimation when the upper bound on the variance of hybrid rewards is smaller than the variance of rewards, i.c., Ve.t-1 o², the beginning of round t, the variance upper bound of hybrid
rewards is computed using t 1 observations and given by 22,1-1 (t-2)),.. where i is an xf s.c
unbiased sample variance estimate of hybrid rewards using
observations and xi-6, (implying
the variance upper bound holds with least probability of 1 - d) denotes 100(1 - 8)th percentile value of the chi-squared distribution with - 2 degrees of freedom. When Dz,t < o² we replace rewards Py= with its respective hybrid rewards, i.e., {= to estimate underlying parameter and use it for next round. After using hybrid rewards to estimate the unknown parameter, replace
17

---

o² in Eq. (7) with the variance upper bound of hybrid rewards. Then we get the following upper bound which holds with a probability of 26.
10. 0=11, s V min (o² Pace- 1) /dog
Vidlog
1 (
+1/225
5
V min (o² (o2,0e, De,e- )an + +11225
= 00. 0-11, 111 of + x2/25,
where og /imin (o², Ja, and 0z2
d log
1+LL2/A 6
Let action Tt be selected in the round Then, the instantaneous regret is given as follows:
Tt max x 0" - x 0r TEA
x² 0r x1 0r
(as x² = max xi 0*)
xEA
(x* xx)T TO
(a* x=)TT 0 + (x" -xx)) _x)TT² 0. - (x* T0.
(x* xT)) TeeT 0. (x* 2x)) T (0. - )¹).
sub-optimal action only selected when its upper confidence bound larger than the optimal
action. Then, if [6. 8r lv a 1/55, then have
r $ a | - ae || 1|. - (x* - -x)) T(; (8;-00) -8)
$ a | - a ||0 ||>*|| || - 1110~1-x0--
- x xello.- |0, - 0- 00llv
s at aalllzllly. a || || |,, + ai ||x= - x zellV."
ar([x=ell,
||~ "lv"" + -|xT - zello.1)
ar(llzellv," || || Il + || Ilv." + ||
2a, 12
r S 2(0 + 1/2 S) |
Let X, = (r5) For > q + and U2,t < o², the expected instantaneous regret of OFUL-AF
E [IF(UOFL-)
< E 2a + 112 || [|
EE
2(
VV + 22 [|<eellv..
2E
E
(V +1122 || X,
=2
la |ITTlll,,
E [ [x]]
+ 112 || 1
(t 2) x
< 2ar ||lellle"
E E
+21 |sllll
xi
2ar I 1
(t 2)
[ 221/25 |srlly, 1.
xi-
Since 22,1-1 is an unbiased estimator of the sample variance of hybrid rewards, E [D,e-1] = V (Zeg)
for E (I....,4). Using Theorem 1, we have V (Feg) = (1+ (1 - 2200²
18

---

((-3)(1-p))
o² as tt observation is not available at the beginning of the round t. With increasing
t-q-3
t, C = (t-2) xi-
tends to 1. With all these observations, we have
(t (t- -()
1/2 oa, || + +22l/25 |
(OFFLLLL-) S 20,
t t- --3 3
$/
(t - (t=3)(1-p)) -
2 C
oa; + 1 Iszellu="
l-q-3
Let (OFUL) be the upper bound on instantaneous regret for OFUL algorithm, i.e., rOFUL)) 2 (oar + x1/25) ||zelly.". Then, we have
(L - 3) - $ (oa, + +X/22) ||
E (OFULLFL-) & 20,
t -- -3 3
1- (1- (1-3)(1- (1--))1--1)
#1
X 2222 |saall,,'
+
(t (t-3)(1 -2²)
C
t- q -3 (OFUL)
)
(t- (t-3)(1- p²)
+2 1 C-C,
12/2 1 I|selll..
t-q -3
(1 (1-3)(1 -1-)) )
(OF(ULLL-A Sō
(OFFL.)))
t-9--3 3
Theorem 4. Let 2 be an AFC bandit algorithm with (x)) [(x) S ohír, O.) + 1xx, O+) and
Ve,e3 be the upper bound on sample variance of hybrid reward, whose value is set o² for q Then, with probability of at least - 26, the instantaneous regret of 21 after using hybrid rewards (named for reward function estimation in round is
Te (A-FF) S 2 min(a, (Pe.z,) MM(x, O,) + (xx,
where e = {IS, MF, KF), and KF denotes the case where auxiliary functions functiony are known. For > 9+2 and De,z,t < 0², E (XI-FF] 5 ((( (1=(-a())) (1 - p²) re rr(2)) where a(KF) =
Proof. Let 2 be an AFC bandit algorithm with 1f. (z) - f(x) S oh(r, O₂) + 1[x, O,) and De,,, be the upper bound sample variance of hybrid reward. After 2 uses hybrid rewards for estimating function f. then, with probability at least 1 28,
(x) f(x)) S min(a, (Pe,e.)+)h(e Oi) + (,)
(8)
The proof follows similar steps as the first part of the proof of Theorem 2. The only key difference is the upper bound of variance of hybrid rewards, which depends on the underlying sampling strategy based on whether auxiliary functions are known or unknown. The upper bound on sample variance given by Pe,,, (t-2)e....t 2 where De,,,t-1 is an unbiased sample variance estimate of hybrid x
rewards using f 1 observations with sampling strategy e and xi-6, (implying the variance upper bound holds with at least probability of 1 -) denotes 100(1 - 5h percentile value of the chi-squared distribution with t degrees of freedom.
Let action Ie be selected in the round t. Then, the instantaneous regret is given as follows: (as x² max f())
Ft max f(x) f(x)) = f(x*) f(x)) z
ZEA
19

---

(x") min(a, (Pe...))))((*' 0,) +1(=- f(a))
- (1x) + min(a, (Pe.z.) (h 0.) + 0,) - ((a))
8 (zx) f(x)) + min(a, (Fe (2 O2) + 1(x,, Oi)
< min(o, (Po...)) (h( O,) + 1(I,, O.),
in which the first and last inequalities have used the upper bound given in Eq. (8), and the second inequality follows because actions are selected using the upper confidence bounds. The remaining proof will follow the similar steps as the second part of Theorem 2 except using Theorem 3 instead of Theorem for quantifying the variance reduction due to hybrid rewards when IS or MF sampling strategy is used for estimating auxiliary feedback function.
A.4 Auxiliary feedback in contextual bandits
Many real-life applications have some additional information readily available for the learner before selecting an action, e.g., users' profile information is known to the online platform before making any recommendations. Such information is treated as contextual information in bandit literature, and the bandit problem having contextual information is refereed as contextual bandits (Li et al., 2010). Since the value of the reward function also depends on the context, the learner's goal use contextual information to select better action.
We extend our results for the contextual bandits problem. In this setting, we assume that learner has been given an action set denoted by A. In round t, the environment generates a vector (Zr,as at,a: i
for each action a E A.. Here, Zz,a is the context-action d-dimensional feature vector of observed context in round and action a, yt.a is the stochastic reward received for context-action pair Tt,a, and Wh,,,i is the 7th auxiliary feedback associated with the reward at,a- We assume that the reward is function of the context-action pair Ft,a, which is given as Vt,a ( + Et, where f Rd - R is unknown function and E is a zero-mean Gaussian noise with variance o², The auxiliary feedback is also assumed to be function of the context-action pair It,a, given as Wr,,, = (z),a) ) + =Y,;, where g, : Idd + IR and EY,; is a zero-mean Gaussian noise with variance o² The correlation coefficient between reward and associated auxiliary feedback is denoted by p.
We denote the optimal action for a context observed in the round as at = argmax,5. ff ( The interaction between a learner and its environment is given follows. At the beginning of round t, the environment generates a context, and then the learner seleets an action o, from action set A for that context using past information of context-actions feature vector, observed rewards and its associated auxiliary feedback until round f. - 1. After selecting action at the learner receives a reward (yt.a.) with its associated auxiliary feedback and incurs a penalty (or instantaneous regret) rt. where re- = a ) o.. We aim to learn a sequential policy that selects actions to minimize the total penalty and evaluate the performance of such policy through regret. which is the sum of the penalty incurred by the learner. Formally, for T contexts, the regret of a policy π that selects action
a, for context observed in round is given by
T Σ (f(Z)a;)) - f(ar..))). 1=1
Ri((T)
(9)
A policy и is good policy when it has aub-linear regret. This implies that the policy will eventually learn to recommend the best action for every context. Similar to the parameterized bandit problem case, we can use the cxisting contextual bandit algorithms, which are AFC bandit algorithms. Depending on the problem, an appropriate AFC contextual bandit algorithm is selected that uses hybrid rewards to estimate reward function. The smaller variance of hybrid rewards leads to tighter upper confidence bound of the unknown reward function and hence smaller regret.
A.5 More details about experiments
To demonstrate the performance gain from using auxiliary feedback, we have considered three different bandit settings: linear bandits, linear contextual bandits, and non-linear contextual bandits. The details of the problem instance used in our experiments are as follows.
20

---

0'll
DIUL
-
0TuL 31
0PUL-O10A
PULO2M4-222 235
OPUL
50
DRUx
Regret
Regret
DHut om 201
Regret
DPUL
200
Rounds
Rounds
Rounds
(a) Biased Estimator
(b) Estimator from historical data
(c) Influence of correlation
M.b-UCB
MLIHUCD 222
200
M MINICHE 2-10
M.IVICC-EE in 2.77
200
Reg PeR
MLn
ALA-ICE-62 ii, 2000
Regres
10 10
Regres
1001
300
1008
2000
2008
300
Rounds
Rounds
Rounds
(d) Biased Estimator
(c) Estimator from historical data
(f) Influence of correlation
Figure 3: Top row: Experiment using linear bandits problem instance. Bottom row: Experiment using non-linear contextual bandits problem instance. Left to right:: Regret vs. different biases (left figure), regret vs. number of historical samples auxiliary feedback (middle figure), and regret vs. varying correlation coefficients of reward and its auxiliary feedback (right figure).
Linear bandits: We 5-dimensional space in which each sample is represented by (Z),.... , 155, where the value æj is restricted in (-3,3) 3). We randomly select a 5-dimensional vector (+* with unit norm whose each value is restricted in (0, 1). In all linear bandits experiments, we use A = 0.01, 2.236, 5 = 1, and ō = 0.05. In round I, the reward for selected action de
V/ + Wt,
where U, x + and w, x, T + We 0 (0, 02, 02, 0) and 0% (0i, 03 0, 05). As we treat wi as auxiliary feedback, 0t, may be assumed to be known in some experiments. The random noise of is zero-mean Gaussian noise with variance of Whereas et is also zero-mean Gaussian noise, but the variance is o² We assumed that x² = of + o² is known, but not the of and o2 The default value of o 0.01 and of 0.01. It can be easily shown that the correlation coefficient of ye and Wi = v / (a? + J. We run each experiment for 5000 rounds.
Linear contextual bandits:
first generate a 2-dimensional synthetic dataset with 5000 (2), where the value of
data samples. Each sample is represented by Our action set A has four actions:
Ty is drawn uniformly at random from (-1,1). We uniformly generate a 0* such that its norm is all experiments, the data samples are treated as contexts, and we use = 0.01, L = 1.41, 0.05. The observed reward for context-action feature vector has two components. We treated one of the components as auxiliary feedback. In round t, the reward context-action feature vector Zt,a is given follows:
{(11, .22), (II,- -22), (-Z1, (-21, =z2)].
S 1, and
Vt,a. Ut.ac + Wt.at'
where Ur,a, = and Wr.a. xT__a +E Weset 6; (0, 0,00, and 6 = (07 0, 87, 0). As we treat Wt.a, as auxiliary feedback, 6t, is known for some experiments. The random noise Ef is zero-mean Gaussian noise with variance o² Whereas et' is also zero-mean Gaussian noise, but the variance is o We assumed that o² of + o is known, but not the o and of The default value of o² 0.01 and o² 0.01. It can be easily shown that the correlation coefficient of yt,a and wrea p / Vo (o? g.).
21

---

0'lL
LiviCD EI
NUT-UCI Rür CIT-LLCOO
RLP
Regret
OHui en 201
Regret
LiviCeen L
Regres
Nür
Rür LLB
Rounds
Rounds
Rounds
(a) Linear Bandit
(b) Linear Contextual Bandits
(c) Non-linear Contextual Bandits
Figure 4: Comparing regret vs. the number of historical samples of auxiliary feedback in different settings. In this experiment, historical samples for each run are randomly generated as compared to Fig. 2e, Fig. 3b, and Fig. 3e where history is kept fixed across the
Non-linear contextual bandits: This problem instance is adapted from the linear contextual bandits problem instance. We first generate 2-dimensional synthetic dataset with 5000 data samples. Each sample is represented by from (-1,1). We then use a polynomial kernel with degree to have a non-linear transformation of samples. We removed (i.e., bias) the first (i.e., 1) and last value (i.e...3) from the transformed samples, which reduced the dimensional
(Z1, where the value of I2 is drawn uniformly at random
each transformed sample to 4 and represented as (21, 22, 27, D2), which is used context. For this setting, the action set A has six actions: {(01, 22, I x2))), (I1, - I2, of. -112)) (-21, (- "1, 112), (-I3, 22, a1 3132), We uniformly generate 0" such that its norm is In all experiments, we use = 0.01, T= 2, S = and 0.05. The observed reward for context-action feature vector has components. We treated one of the components auxiliary feedback. In round f, the reward context-action feature vector Iz, is given as follows:
-1)12), (I1, -22, -xf, 22)),
V1,a, = Ut + Wtaas.
where Ut.o, = Li.a S and Wt.a, = xT_ 0r + + We set 0 = (0,02,0, 01, O, 0g 0, 0g) and 0: = (01.0, 0, 05. 0, 0g 0, 0;, 0). As we treat Wt,a, as auxiliary feedback, 0r is known for some experiments. The random noise Eğ is zero-mean Gaussian noise with variance of Whereas of is also zero-mean Gaussian noise, but the variance is o2. We assumed that の² o oe is known, but not the of and o².- The default value of o² = 0.01 and o = 0.01. It can be easily shown that the correlation coefficient of yt,a and Wro is p = V o (o )
Regret with varying correlation coefficient: As the correlation coefficient of reward and auxiliary feedback is p / (o8 + oZ), we varied a, over the values {0.3, 0.2, 0.1828, 0.1, 0.0655) to obtain problem instances with different correlation coefficient for all problem instances.
Variance estimation: Since the value of o² is know all our experiments, we directly estimate the correlation coefficient (p) Cov(y, (VV (w)o). Then, use it to set Pe,z,t (1 0²)
22


Reviews:
[{"review_id": "QBkIuc907q", "reviewer": "Reviewer_vUBt", "summary": "This paper focus on the problem of parameterized bandits when extra auxiiliary feedback is available, which can be utilized to construct an unbiased reward estimator, which potentially shares smaller variance and thus algorithms based on such estimator can thus incur smaller regret. Experiments validates the estimator and corresponding algorithm.", "questions": "See weaknesses above.", "limitations": "None", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper is clearly-written, in which the problem statement, algorithms, theories and experiments are easy to follow.\n- Control variate theory is applied in this paper, which is suitable for i.i.d. random process in the variance reduction, which is one of the central topic in bandits, and is of independent interests beyond the topic.\n- The proposed algorithm is evaluated both empirically and theoretically.", "weaknesses": "- The improvement is expectable, as auxiliary feedback (AF) requires more information and computation. So this can be seen as a trade-off between extra information beyond rewards, extra computation and a constant order improvement in regret.\n- The hybrid reward only reduces variance when the AF is correlated with reward with same covariance $\\sigma_{y,w}$. I'm worried this could not be true for most real-world applications. \n- Though extra AF is given, the experiments does not design how OFUL or LinUCB can utilize such AFs. One can figure another simplest way to use these extra information, for example, learn a model $f:\\mathbf{R}^d \\rightarrow \\mathbf{R}$, which means to learn the function that maps the AF vector to the reward $y_t$, and thus OFUL and LinUCB can gain extra feedback $f(AF)$ to better estimate the reward. If the baseline just discard the extra AF, its' not fair.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments. In the following, we have responded to your questions.\n\n\n> ### *The improvement is expectable, as auxiliary feedback (AF) requires more information and computation. So this can be seen as a trade-off between extra information beyond rewards, extra computation and a constant order improvement in regret.*\n\nWe agree with the reviewer's observation that there is a trade-off between extra computations needed to incorporate auxiliary feedback in existing bandit algorithms and improvement in regret. However, regret improvement is only possible when the auxiliary feedback correlate with the reward, and the regret improvement is upper bounded by the correlation between the reward and its auxiliary feedback. \n\n\n> ### *The hybrid reward only reduces variance when the AF is correlated with reward with same covariance $\\sigma_{y,w}$. I'm worried this could not be true for most real-world applications.*\n\nYes, we assumed that the correlation between reward and its auxiliary is the same across all actions, i.e., same covariance $\\sigma_{y,w}$ (Line 101). This assumption is reasonable as the source of randomness in reward and auxiliary feedback is zero mean Gaussian noise, whose variance is independent of the action (it is a common assumption in many bandit algorithms like OFUL, Lin-UCB, and UCB-GLM). However, this assumption can be violated in many real-world applications where Gaussian noise varies across actions, making covariance $\\sigma_{y,w}$ vary across actions. The closest bandit setting to this problem is the bandit problem with heteroscedastic noise. Even though the definition of hybrid rewards used in the paper can be used, it may not give the best possible variance reduction. Therefore, the problem of varying covariance $\\sigma_{y,w}$ needs to be systematically studied and can be an independent work, as we mentioned in Line 344.\n\n\n\n> ### *Though extra AF is given, the experiments does not design how OFUL or LinUCB can utilize such AFs. One can figure another simplest way to use these extra information, for example, learn a model $f: R^d \\rightarrow R$, which means to learn the function that maps the AF vector to the reward $y_t$, and thus OFUL and LinUCB can gain extra feedback $f(AF)$ to better estimate the reward. If the baseline just discard the extra AF, its' not fair.*\n\nWe do not know any parameterized bandit algorithm that can exploit the available auxiliary feedback. Therefore, our goal is to design a method that can exploit correlated auxiliary feedback to improve the performance (i.e., minimize regret) of the existing bandit algorithms. To achieve that, we use auxiliary feedback as control variates and extend the existing results from the control variate theory to our setting. We use vanilla OFUL and Lin-UCB as baselines to demonstrate the performance gain achieved by our approach. \n\nLet $f: R^d \\rightarrow R$ learn the function that maps the auxiliary feedback vector to the reward $y_t$. Then, extra feedback $f(AF)$ may not get a better reward estimate in OFUL and LinUCB. Because first, the auxiliary feedback vector may only partially correlate with reward, e.g., user rating of food also depends on food taste and quality (which can not be observed by the platform) apart from the food delivery time. Second, getting an estimate for the reward from auxiliary feedback is impossible as auxiliary feedback is only observed with the reward."}, {"review_id": "YLhgsT4bhl", "reviewer": "Reviewer_CBCn", "summary": "This paper studies the parametrized bandit problem in which the learner observes auxiliary feedback together with the reward, and also correlated with the reward. It is motivated from the control variate approach in causal inference, the main difference is that in this paper, it extends the control variable theory to a setting where the \"control variable\" is parametrized by a function. It proposes a new bandit algorithm which replaces the original observed reward, with a version built upon the known/estimated control variate and studies the expected instantaneous regret compared with the original bandit algorithm. ", "questions": "- For Figure 2 (f), is it possible to add the performance for original Lin-UCB performance?\n- It would be good to have an ablation study w.r.t the number of auxiliary functions.\n- others listed in the Weakness section. ", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- This paper studies a new bandit framework which differs from most of the prior work (such as side information, side observation, etc). In this new framework, the learner also observes the auxiliary feedback beyond the original reward. This setting is pretty relevant to lots of real-world scenarios, such as in food delivery platform, user rating might be revealed together with the delivery time, in recommendation platform, optimizing user like rate might be revealed together with the watch time, etc. \n\n- The paper is very well-written and easy to follow. It is built upon the classical control variate theory, and extends it to the known function (of the control variate), then further down to estimated function setting. The method is solid, and the expected instantaneous regret is provided to validate the soundness of the proposed approach.\n\n- I appreciate the additional efforts in the synthetic datasets to verify the empirical performance of the proposed method under various environment, such as the linear, linear contextual, non-linear contextual bandits, and study how the estimation of the control variate function as well as the correlation of the auxiliary feedback with the reward affect the final performance. These results facilitate the understanding.", "weaknesses": "- I am a little bit confused about the relationship of the variance reduction in terms of the number of auxiliary feedback being used. Under estimated $\\beta$ and from Theorem 1, it seems the optimal number of auxiliary feedback being used is 1, which seems a little bit counter-intuitive, could the authors comment more on this aspect?\n\n- In Section 4, under estimated auxiliary functions, the sampling strategy for estimating the auxiliary function seems very computationally inefficient, and this leaves much smaller sample size for estimating the original f function compared with classical bandit algorithms, especially when the number of auxiliary functions is large. Remark 2 also does not make that much of sense, when $r_i$ goes to infinity where we use most of the sample in auxiliary function estimate. \n\n- The IS and MF sampling strategy are only listed in the method discussions, and for the experiments when $q=2$, it is hard to compare the pros and cons of them as they are equivalently being the same. Could the authors add more results for larger $q$ to showcase the effectiveness of the two sampling methods. A larger $q$ might also be helpful in understanding the effectiveness of having more control variates. \n\n- I am not sure if there is any public dataset available to showcase the effectiveness of the method in more real-world scenarios. The current ablation experiments facilitate the understanding of the method, but adding real-world experiments would be much more convincing.  \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\n\nThank you for the detailed comments and suggestions. We have responded to each of the questions below.\n\n> ### *I am a little bit confused about the relationship of the variance reduction in terms of the number of auxiliary feedback being used. Under estimated $\\beta$ and from Theorem 1, it seems the optimal number of auxiliary feedback being used is 1, which seems a little bit counter-intuitive, could the authors comment more on this aspect?*\n\nThe variance reduction given in Theorem 1 depends on the auxiliary feedback via two terms: $\\frac{t-2}{t-q-2}$ and $\\rho^2$ (defined in Line 142). Setting $q=1$ will give the minimum value for $\\frac{t-2}{t-q-2}$, but $\\rho^2$ for $q=1$ will also be small as it only considers one auxiliary feedback, and hence maximum variance reduction will not be achieved. As we increase the number of auxiliary feedback, $\\rho^2$ will increase, leading to more variance reduction. However, at the same time, the term $\\frac{t-2}{t-q-2}$ will also increase, which can negate the variance reduction. Therefore, it is recommended to use a small number of auxiliary feedback (more in Remark 1).\n\n\n\n> ### *In Section 4, under estimated auxiliary functions, the sampling strategy for estimating the auxiliary function seems very computationally inefficient, and this leaves much smaller sample size for estimating the original f function compared with classical bandit algorithms, especially when the number of auxiliary functions is large. Remark 2 also does not make that much of sense, when $r_i$ goes to infinity where we use most of the sample in auxiliary function estimate.*\n\n\nIn many real-world applications, a learner may have already collected auxiliary feedback (historical data) or collect auxiliary feedback independent of the reward sample (e.g., cheap low-fidelity simulations) or even collect additional samples of auxiliary feedback with no reward sample, e.g., an online food platform will not get a user rating (reward) for each order but will have a food delivery time (auxiliary feedback) for each order. Therefore, our proposed method uses all observations with reward samples to estimate the reward function $f$. \n\nIn practice, one can use an appropriate variant of our proposed method depending on the need of their application (EH and BE variants shown in Fig. 2(a)-2(c)). However, it will be challenging to quantify the exact gain in variance reduction (as shown in Theorem 3 for specific case). \n\n\n> ### *The IS and MF sampling strategy are only listed in the method discussions, and for the experiments when $q=2$, it is hard to compare the pros and cons of them as they are equivalently being the same. Could the authors add more results for larger $q$ to showcase the effectiveness of the two sampling methods. A larger $q$ might also be helpful in understanding the effectiveness of having more control variates.*\n\nIn control variate literature, it has been proven that IS and MF sampling strategies are asymptotically optimal (Gorodetsky et al., 2020), i.e., the variance reduction achieved by both strategies is asymptotically the same as if auxiliary feedback functions are known. Further, it is also shown that they both have similar empirical performance (Gorodetsky et al., 2020, Fig. 4), but these results are shown for a non-parametric offline setting. However, both strategies can be used for different problems: IS sampling strategy suits the problems in which different auxiliary feedback can be independently sampled, whereas MF sampling suits problems where auxiliary feedback can not be sampled independently. We will add experiments on both sampling strategies with larger $q$ in the future version of the paper. When the auxiliary functions are known, we have already added an experiment result with larger $q (={1, 2, 3, 4, 5}$). For more details, please check the attached pdf in the global rebuttal. \n\n\n> ### *I am not sure if there is any public dataset available to showcase the effectiveness of the method in more real-world scenarios. The current ablation experiments facilitate the understanding of the method, but adding real-world experiments would be much more convincing.*\n\nThe main goal of this paper is to propose a method that exploits the auxiliary feedback correlated with reward samples to improve the performance of parameterized bandit algorithms and quantify performance gain (i.e., reduction in regret). It is common in bandit literature to measure the performance of bandits algorithms on synthetically generated data. We have also validated our method using several bandits instances. \n\nIn the future, we will set up an elaborate experiment to demonstrate the effectiveness of our algorithms on real datasets. \n\n\n> ### *For Figure 2 (f), is it possible to add the performance for original Lin-UCB performance?*\n\nWe have added the Lin-UCB in Figure 2(f). For more details, please check Figure 1 in the attached pdf in the global rebuttal. \n\n\n> ### *It would be good to have an ablation study w.r.t the number of auxiliary functions.*\n\nWe have added an experiment result with more auxiliary functions ($q={1, 2, 3, 4, 5}$). For more details, please check Figure 2 in the attached pdf in the global rebuttal. \n\n\n"}, {"review_id": "fcWZOBMG6h", "reviewer": "Reviewer_jBfm", "summary": "This paper leverages the method of control variates to obtain reward estimates with smaller variance for contextual bandit algorithms, since smaller variance in reward estimation means tighter confidence bound estimation and therefore smaller regret. Estimation methods for both unknown and known auxiliar feedback functions are provided, where both theoretical and empirical results were provided to demonstrate the effectiveness of the proposed solution.  ", "questions": "Since we are using linear regression for $\\beta$ estimation, why is $W^\\top_t W_t$ guaranteed to be invertible? Even when we have more samples than the number of auxiliary dimensions, i.e., $t>q+2$, the observations of auxiliary feedback might not span the entire $q$ dimensional space, depending on the distribution of selected arms.   \n\nIs it true that the algorithm is supposed to have free access to auxiliary feedback from any arm? If so, what presents the algorithm from extensively pulling all the arms to estimate their auxiliary feedback function, so as to get the most accurate estimation of those functions first?\n\nThe algorithm assumes the reward noise is known and use this quantity to control when to use which estimator. But in practice, we do not know the actual value of reward variance, and how could we use the proposed algorithm? \n", "limitations": "I do not find any concerns regarding the negative societal impact of this work. ", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Leveraging available auxiliar feedback to improve reward estimation is an important and also meaningful approach for improving bandit algorithms. This paper provides a viable solution to realize the goal. \n\nThe provided solution is an extension of Verma and Hanawal’s NeurIPS’2021 work in multi-armed bandits, and the authors further extended it to contextual bandit problems, especially with the non-linear reward functions.     \n", "weaknesses": "The means of using control variates to reduce the reward estimation variance is not a completely new idea, as the authors pointed out in the related work discussions. And the estimation techniques employed in this paper were also borrowed from prior works. For example, the results under known auxiliary feedback function is a straightforward extension of Verma and Hanawal’s NeurIPS’2021 work on top of OFUL’s analysis, and the results for the unknown auxiliary feedback function is also not super challenging (e.g., using existing estimation technique and assuming the reward variance is known). This to certain degree limits the novelty of this work. \n\nThe description for the unbiased linear estimator $\\beta_e$ is unfortunately unclear and could be actually problematic. Based on the problem setup, my understanding is that every arm pull reveals all $q$ dimensions of the auxiliary feedback, in addition to the reward feedback. And the different sampling/partitioning methods, e.g., IS or MF, decide how to allocate those samples for estimating the reward function and auxiliary feedback function. Hence, the total number of samples for estimation at time $t$ is $t$, but each sample has $q+1$ dimensions. But in line 302, it states to maintain $r=2$, it needs to “getting one extra sample of auxiliary feedback in each round”. This seems to suggest the algorithm can pull another arm and only require the auxiliary feedback for free. If this is the case for algorithm design, it is an unfair advantage to the algorithm, comparing to the baseline bandit algorithms, as it can collect more information about the reward. Or in other words, why not further increase the ratio $r$ to better exploit this advantage? The EH variant of this algorithm further confirmed my understanding: it is assumed more observations about the auxiliary feedback are available.  \n\nThe experiment settings were also overly simplified, which do not strongly support the advantages or demonstrate the limitations of the proposed solution. For example, there is only one dimension of auxiliary feedback. Given the algorithm’s theoretical performance depends on the dimension of auxiliary feedback, it is important to vary its dimension to investigate its practical impact. \n\nAnother factor should be mentioned is that the paper only addresses the finite arm setting (especially in the experiments), though in contextual bandit problems infinite arms with potentially adversarial context arrival is believed to be a more general setting. Otherwise, simple algorithms can already achieve satisfactory regret: for example, a greedy algorithm can obtain sublinear regret with sufficient context diversity and logarithmic regret is also achievable under stochastic context distributions. It would be meaningful to discuss how the developed algorithm can be extended to this more general and also more challenging environment. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed comments and constructive feedback. We have responded to each of the questions below.\n\n> ### *The means of using control variates to reduce the reward estimation variance is not a completely new idea, as the authors pointed out in the related work discussions. And the estimation techniques employed in this paper were also borrowed from prior works. $\\ldots$ This to certain degree limits the novelty of this work.*\n\nOur work is motivated by Verma and Hanawal (2021). Please check the **Main contributions** part of the global rebuttal for our novel contributions.\n\n> ### *$\\ldots$ in line 302, it states to maintain $r=2$, it needs to “getting one extra sample of auxiliary feedback in each round”. This seems to suggest the algorithm can pull another arm and only require the auxiliary feedback for free. If this is the case for algorithm design, it is an unfair advantage to the algorithm, comparing to the baseline bandit algorithms, as it can collect more information about the reward. Or in other words, why not further increase the ratio $r$ to better exploit this advantage? The EH variant of this algorithm further confirmed my understanding: it is assumed more observations about the auxiliary feedback are available.*\n\nDepending on the applications, a learner may have already collected auxiliary feedback (historical data) or may collect auxiliary feedback independent of the reward sample (e.g., cheap low-fidelity simulations) or even collect additional samples of auxiliary feedback without a reward sample, e.g., an online food platform will record the food delivery time (auxiliary feedback) for every order but may not get a user rating (reward) for each order. In our experiments, we maintain $r=2$ to validate our theoretical result, but getting an extra auxiliary sample does not imply that we will play that arm again but ignore the reward sample. Our proposed method uses all observations with reward samples to estimate the reward function $f$. In practice, one can use an appropriate variant of our proposed method depending on the need of their application (EH and BE variants shown in Fig. 2(a)-2(c)). However, it will be challenging to quantify the exact gain in variance reduction for these variants.\n\n\n> ### *The experiment settings were also overly simplified, $\\ldots$. Given the algorithm’s theoretical performance depends on the dimension of auxiliary feedback, it is important to vary its dimension to investigate its practical impact.*\n\nOur work is a theoretical work that quantifies the performance gain achieved by a parameterized bandit algorithm using auxiliary feedback correlated with reward samples. It is common in bandit literature to measure the performance of bandits algorithms on synthetically generated data. Therefore, we have also validated our method using different bandit instances. We have also added an experiment result with larger $q (={1, 2, 3, 4, 5}$) when the auxiliary functions are known. For more details, please check the attached pdf in the global rebuttal. \n\n\n> ### *Another factor should be mentioned is that the paper only addresses the finite arm setting (especially in the experiments), though in contextual bandit problems infinite arms with potentially adversarial context arrival is believed to be a more general setting. $\\ldots$.*\n\nOur experiment results related to OFUL as a baseline linear bandit algorithm deals with infinite arms setting (different results are shown in Fig. 2(a), Fig3(a), Fig3(b), Fig3(c), Fig4(a)). The main challenge for extending our method to more general settings and challenging environments is incorporating correlated auxiliary feedback with reward samples to improve reward function estimation. Our proposed method and techniques will be a baseline for future work in more challenging settings.\n\n\n> ### *Since we are using linear regression for $\\beta$ estimation, why is $W_tW_t^\\top$ guaranteed to be invertible?$\\ldots$.*\n\nThe randomness in each auxiliary feedback is due to IID Gaussian noise, which is independent of actions and other auxiliary feedback. It makes auxiliary feedback vectors independent of each other, and hence $W_tW_t^\\top$ is invertible if there are more than $q$ auxiliary feedback vectors. When auxiliary feedback vectors are not independent, we can add a condition (e.g., Line 7 of OFUL-AF) for calculating $\\boldsymbol{\\hat\\beta}_t$ only if $W_tW_t^\\top$ is an invertible matrix.\n\n\n> ### *Is it true that the algorithm is supposed to have free access to auxiliary feedback from any arm? If so, what presents the algorithm from extensively pulling all the arms to estimate their auxiliary feedback function, so as to get the most accurate estimation of those functions first?*\n\nWe have kept $r$ constant in Theorem 3 to quantify the variance reduction. However, this may not be the case in practice, e.g., having enough historical data of auxiliary feedback can be used to get a reasonable estimate of an auxiliary function. Consider another example of a cheap low-fidelity simulator where an algorithm can get as many auxiliary feedback samples as needed to have a good estimate of the auxiliary function at the start. However, using this may lead to a variant of our method for which quantifying the variance reduction may be challenging.\n\n> ### *$\\ldots$ in practice, we do not know the actual value of reward variance, and how could we use the proposed algorithm?*\n\nWe agree with the reviewer that we do not know the actual value of reward variance in practice. However, the assumption of a known (upper bound of) reward variance is common in many bandit algorithms, e.g., OFUL, Lin-UCB, UCB-GLM, and IGP-UCB. Further, our method can be extended to bandit algorithms like VOFUL and VOFUL2 for problems with unknown variance. "}, {"review_id": "DKT8IIZH3x", "reviewer": "Reviewer_HUuF", "summary": "In this paper, the authors studied a variant of the parameterized bandits problem where the learner has access to auxiliary feedback that is correlated with the observed reward. The authors proposed a method that leverages the auxiliary feedback to construct a reward estimator with more accurate confidence bounds, resulting in better regret bounds. The paper provides a characterization of the regret reduction in terms of the correlation coefficient between the reward and auxiliary feedback. Finally, they demonstrated the effectiveness of their method via numerical experiments. ", "questions": "See weaknesses.", "limitations": "See weaknesses. ", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The setting studied in this paper is interesting and realistically challenging, as it is often unclear how to use such auxiliary feedback for better online decision-making.\n2. The paper is well organized. The theoretical results also appear sound. \n3. The authors have provided a comprehensive literature review on existing research related to this work, and clearly explained the connection between their work and prior works in control variate theory. \n", "weaknesses": "It would be good if the authors could provide further discussions and clarifications on the following points:\n1. The description of the algorithm (OFUL-AF) could be made clearer. Currently, it appears as a rephrasing of each step without clear connections to prior derivations. It would be helpful to explain how each step relates to the preceding derivations.\n2. The procedure of selection of the number of auxiliary feedback $q$ in practice is not entirely clear to me. It'd be helpful to have more details regarding this point in addition to Remark 1. \n3. The regret bound in Theorem 2 contains hidden constant terms. Could you elaborate more on the magnitude of these constant terms and their impact on the overall result?\n4. The authors acknowledge that the actual form of the auxiliary feedback functions is typically unknown in practice, which I consider to be an important realistic challenge that needs to be dealt with. While Section 4 explores the effect of using estimated functions, I wonder how one can obtain an unbiased estimator for the auxiliary feedback functions in the first place. This is a challenging aspect that merits further explanation.\n5. How should I comprehend the terms $a(e)$ and $\\rho_e$ from Theorem 3? What do they each represent and do they constitute certain kind of tradeoff within the regret bound? \n6. It'd be helpful to also see how the proposed model and method can be applied to certain real-world data. This is related to my point (4) above as I'm not entirely sure how one'd make sense of the auxiliary feedback function in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed comments and suggestions. We have responded to each of the questions below.\n\n>### *1. The description of the algorithm (OFUL-AF) could be made clearer. Currently, it appears as a rephrasing of each step without clear connections to prior derivations. It would be helpful to explain how each step relates to the preceding derivations.*\n\nTo improve the readability, we will add more explanations and connections to prior results while explaining each step of OFUL-AF in the revised version of the paper.\n\n>### *2. The procedure of selection of the number of auxiliary feedback $q$ in practice is not entirely clear to me. It'd be helpful to have more details regarding this point in addition to Remark 1.*\n\nThe variance reduction given in Theorem 1 depends on different auxiliary feedback via two terms: $\\frac{t-2}{t-q-2}$ and $\\rho^2$ (defined in Line 142). As we increase the number of auxiliary feedback, $\\rho^2$ will increase, leading to more variance reduction. However, simultaneously, the term $\\frac{t-2}{t-q-2}$ will also increase, negating the gain in variance reduction. Therefore, it is recommended to use a small number of auxiliary feedback to avoid the degradation in variance reduction. One of the possible procedures for the selection of the number of auxiliary feedback is given in Lavenberg et al., 1982 (specifically on page 196).\n\n>### *3. The regret bound in Theorem 2 contains hidden constant terms. Could you elaborate more on the magnitude of these constant terms and their impact on the overall result?*\n\nThere are two constants: one is the multiplicative constant $C_t$ (defined in Line 528 in the Appendix), whose value goes to $1$ as $t$ increases. Another is an additive constant (more details after Line 530 in the Appendix), which is comparatively negligible.\n\n\n>### *4. The authors acknowledge that the actual form of the auxiliary feedback functions is typically unknown in practice, which I consider to be an important realistic challenge that needs to be dealt with. While Section 4 explores the effect of using estimated functions, I wonder how one can obtain an unbiased estimator for the auxiliary feedback functions in the first place. This is a challenging aspect that merits further explanation.*\n\nBased on the application, a learner may have already collected auxiliary feedback (historical data) or may collect auxiliary feedback independent of the reward sample (e.g., having access to cheap low-fidelity simulations) or even collect additional samples of auxiliary feedback without a reward sample, e.g., an online food platform will record the food delivery time (auxiliary feedback) for every order but may not get a user rating (reward) for each order. \n\nIn practice, one can use an appropriate variant of our proposed method depending on the need of their application (EH and BE variants shown in Fig. 2(a)-2(c)). However, it will be challenging to quantify the gain in variance reduction (as in Theorem 3) for these variants.\n\n>### *5. How should I comprehend the terms $a(e)$ and $\\rho_e$ from Theorem 3? What do they each represent and do they constitute certain kind of tradeoff within the regret bound?*\n\nThe term $a(e)$ comes due to different sampling methods used by IS and MF sampling strategies for estimating the unknown auxiliary functions. As given in Theorem 3, the value of $a(IS)$ (for IS sampling strategy) is 1, whereas it is $\\frac{r-1}{r}$ for MF sampling strategy having $r_i = r$ for each auxiliary variable. \n\nThe term $\\rho_e$ denotes the multiple correlation coefficient of reward and its auxiliary feedback when using IS and MF sampling strategies. Its value depends on the sampling strategy (Line 231 for definition and Eqs. before Line 239).\n\nFrom the expression given in Line 282, smaller $a(e)$ and larger $\\rho_e$ lead to smaller regret.\n\n\n>### *6. It'd be helpful to also see how the proposed model and method can be applied to certain real-world data. This is related to my point (4) above as I'm not entirely sure how one'd make sense of the auxiliary feedback function in practice.*\n\nSince it is common in bandit literature to measure the performance of bandits algorithms on synthetically generated data, we have also validated our method using different bandit instances. In the future, we will set up an elaborate experiment to demonstrate the effectiveness of our algorithms on real datasets.\n\n"}]

Author rebuttal:
We thank all reviewers for their time and efforts in evaluating our paper and for their detailed comments and suggestions. We hope our answers to your questions will alleviate your concerns and further improve your opinion of our work. If you have additional questions, we would be happy to address them.

Here, we address two main concerns and respond to your questions in individual rebuttals.


### **Main contributions:**
The following are our main contributions:
- **General setup:** Verma and Hanawal (2021) focus on a non-parameterized bandit setting, which assumes a finite number of actions and known auxiliary mean values. In contrast, we consider a more general bandit setting with a large (or even infinite) number of actions (i.e., parameterized bandits with contextual information). Further, we extend to a setting where unknown functions parameterize different auxiliary feedback. 

- **Control variates theory with parameterized function:** Control variate literature focuses on a non-parameterized control variate (auxiliary feedback in our problem), i.e., control variates are sampled from a fixed distribution. We first extend the existing control theory results to the problems where known functions parameterize the control variates (Section 3) and then extend to problems where functions parameterizing control variates are unknown (Section 4). Our key contribution is to design an unbiased reward function estimator using hybrid rewards (a combination of reward and its auxiliary feedback), which gives a maximum reduction in the estimator's variance. These contributions are themselves of independent interest in control variate theory. 

- **AFC bandit algorithm:** We introduce the notion of the Auxiliary Feedback Compatible (AFC) bandit algorithm. A bandit algorithm is an AFC bandit algorithm when certain conditions are satisfied (more details are in Definition 1). One can use hybrid rewards instead of only observed rewards in the AFC bandit algorithm, which leads to tighter confidence bounds and hence smaller regret. 

Our work has shown that the regret of AFC bandit algorithms can be improved by exploiting the auxiliary feedback. We hope the proposed method and techniques can be used for more challenging bandit problems with auxiliary feedback, e.g., bandit problems with heteroscedastic noise, non-Gaussian noise, adversarial contexts, and different environments.


### **Availability of Auxiliary feedback**
Auxiliary feedback is easily available in many real-life applications. To illustrate that, we consider following different scenarios:
- **Reward sample with auxiliary feedback:** In many problems, reward and its auxiliary feedback are observed jointly in each round. For example, consider a job schedular (Verma and Hanawal, 2021) that aims to assign different jobs to available servers. The job's service time (reward) depends on its size (auxiliary feedback) and other factors (e.g., load in assigned server). 
In such settings, reward and auxiliary feedback are observed jointly. Therefore, the platform can either use available historical data to estimate the mean job size or use observed auxiliary feedback to estimate auxiliary functions but ignore the associated reward samples (this is inefficient).


- **Auxiliary feedback with no reward sample:** Consider an online food delivery platform that keeps track of the user's rating (reward) to recommend the best-rated restaurant and can also observe food delivery time (auxiliary feedback) for each order. The platform can observe the delivery time for every order but may only sometimes receive user ratings. In such settings, additional auxiliary feedback is available apart from historical data, which can be used for estimating the auxiliary feedback functions. Similar scenarios arise in online cab booking platforms and e-commerce platforms, as mentioned in the paper.


- **Sampling auxiliary feedback without reward sample:**
Consider a problem where getting samples from the high-fidelity simulation is very expensive but accurate. However, cheap low-fidelity simulations are available and correlated with expensive high-fidelity simulations. In such scenarios, one can independently collect sufficient samples to get a good estimate of low-fidelity simulations, and then the samples from cheap low-fidelity simulations can be used to minimize the variance of the estimator based on high-fidelity simulations.

Meta-review: This paper generalizes multi-armed bandits with control variates to linear bandits. The proposed algorithm is a variant of LinUCB and computationally efficient. Its analysis shows lower regret due to control variates. The algorithm is empirically evaluated on several synthetic problems.

This paper is easy to read and sound. While the extension is novel, it is not surprising. The additional shortcomings are:

* One strong assumption in this work (also in prior works) is that the auxiliary feedback functions are known. This is rarely true in practice. To counter this point, I suggest that the authors add experiments where the auxiliary feedback functions are estimated from historical logged data. Similar experiments have become common in recent works on hierarchical Bayesian bandits, such as [Mixed-Effect Thompson Sampling](https://proceedings.mlr.press/v206/aouali23a.html), where the model is often unknown and has to be estimated from historical logged data. No analysis is needed. This is for practitioners.

* The proposed algorithm is not compared to any naive way of incorporating side information, such as adding it as features. While this is not theoretically sound, it is a leading approach in practice. Showing that this approach can be beaten would convince practitioners to pay attention to this work.

While this work has shortcomings, they can be addressed with a little bit more work and I hope that the authors will do so. With this, I suggest acceptance of this paper.
Decision: Accept (poster)