#  Exploiting Correlated Auxiliary Feedback in Parameterized Bandits

Arun Verma Zhongxiang Dai Yao Shu Bryan Kian Hsiang Low
Department of Computer Science, National University of Singapore, Republic of
Singapore
{arun, daizhongxiang, shuyao<EMAIL_ADDRESS>
###### 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.

##  1 Introduction

Parameterized bandits (Slivkins, 2019; Lattimore and Szepesvári, 2020) have
many real-life applications in online recommendation, advertising, web search,
and e-commerce. In this bandit problem, a 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-Yadkori et al., 2011; Agrawal 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 to learn the best
action as 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 (Alon et al., 2015; Wu et al., 2015) (i.e., information about
other actions, e.g., graph feedback) to make confidence bounds as tight as
possible. This paper considers another type of additional information
(correlated with the reward) that a learner can observe with reward for the
selected action, which we call auxiliary feedback.

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 rating also depends on overall food delivery time, one can expect
it to be correlated with the user rating. The platform can estimate or know
the average delivery time for a 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 response to ride
request), e-commerce platforms choosing top sellers to 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?

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 non-parameterized 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 knowing 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, no existing control variate result can 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 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 (1 and 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-\rho^{2})^{\frac{1}{2}})$
compared to the same AFC bandit algorithm using only observed rewards, where
$\rho$ is the correlation coefficient of the reward and its auxiliary feedback
(2 and 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.

Side Information: 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., 2011; Agrawal and Goyal, 2013; Li et
al., 2017). Here, the mean reward of each arm is a function of context and is
often parameterized, e.g., linear (Li et al., 2010; Chu et al., 2011; Agrawal
and Goyal, 2013), GLM (Li et al., 2017), and non-linear (Valko et al., 2013).
These contexts are assumed to be observed _before_ an action is taken.
However, we consider a problem where additional information is correlated with
rewards that can only be observed _after_ selecting the action.

Side Observations: Several works consider the different side observations
settings in the literature, e.g., stochastic (Caron et 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, 2020a, 2020b). 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.

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 et 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 a non-
parameterized setting with a finite number of actions. We thus consider a more
general bandit setting with large (infinite) actions and allow a function to
parameterize auxiliary feedback.

##  2 Problem setting

We consider a 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
$\mathcal{X}\subset\mathbb{R}^{d}$ where $d\geq 1$. At the beginning of round
$t$, the learner selects an action $x_{t}$ from action set $\mathcal{X}$.
Then, the environment generates a stochastic reward $y_{t}\doteq
f(x_{t})+\varepsilon_{t}$ for the selected action $x_{t}$, where
$f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is an unknown reward function and
$\varepsilon_{t}$ is a zero-mean Gaussian noise with variance $\sigma^{2}$.
Apart from the stochastic reward $y_{t}$, the environment generates $q$ of
auxiliary feedback. The $i$-th auxiliary feedback is denoted by $w_{t,i}\doteq
g_{i}(x_{t})+\varepsilon_{t,i}^{w}$, where
$g_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R}$ and $\varepsilon_{t,i}^{w}$ is a
zero-mean Gaussian noise with variance $\sigma_{w,i}^{2}$. The multiple
correlation coefficient of reward and its auxiliary feedback is denoted by
$\rho$ and assumed to be the same across all actions.

The optimal action (denoted by $x^{\star}$) has the maximum function value,
i.e., $x^{\star}\in\arg\\!\max_{x\in\mathcal{X}}f(x)$. After selecting an
action $x_{t}$, the learner incurs a penalty (or _instantaneous regret_)
$r_{t}$, where $r_{t}\doteq f(x^{\star})-f(x_{t})$. 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 a sequential policy $\pi$ that selects action
$x_{t}$ in the round $t$ is given by

$\mathfrak{R}_{T}(\pi)\doteq\sum_{t=1}^{T}r_{t}=\sum_{t=1}^{T}\left(f(x^{\star})-f(x_{t})\right).$
(1)

A policy $\pi$ is a good policy if it has sub-linear regret, i.e.,
$\lim_{T\rightarrow\infty}{\mathfrak{R}_{T}(\pi)}/T=0$. This implies that the
policy $\pi$ will eventually learn to recommend the best action.

##  3 Known auxiliary feedback functions

We first focus on a 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 is
known beforehand (see Kreutzer et al. (2017), Vlassis et 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 or
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 we face is how to exploit auxiliary feedback to get a
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 new contribution is itself of independent interest.

###  3.1 Control variate

Let $\mu$ be the unknown variable that needs to be estimated and $y$ be its
unbiased estimator, i.e., $\mathbb{E}\left[y\right]=\mu$. Any random variable
$w$ with a known mean value ($\omega$) can be treated as a control variate for
$y$ if it is correlated with ${y}$. The control variate method (Nelson, 1990)
exploits errors in estimates of known random variables to reduce the
estimator’s variance for the unknown random variable. This method works as
follows. For any choice of a coefficient $\beta$, define a new random variable
as ${z}\doteq y-\beta(w-\omega).$ Note that ${z}$ is also an unbiased
estimator of $\mu$ (i.e., $\mathbb{E}\left[{z}\right]=\mu)$ as

$\mathbb{E}\left[z\right]=\mathbb{E}\left[y\right]-\beta\mathbb{E}\left[(w-\omega)\right]=\mu-\beta(\mathbb{E}\left[w\right]-\omega)=\mu-\beta(\omega-\omega)=\mu.$

Using properties of variance and covariance, the variance of $z$ is given by

$\displaystyle\mathbb{V}\left(z\right)=\mathbb{V}\left(y\right)+\beta^{2}\mathbb{V}\left(w\right)-2\beta\text{Cov}(y,w).$

The variance of $z$ is minimized by setting $\beta$ to
${\beta}^{\star}={\text{Cov}(y,w)}/{\mathbb{V}\left(w\right)}$ and the minimum
value is $(1-\rho^{2})\mathbb{V}\left(y\right)$, where
$\rho={\text{Cov}(y,w)}/\sqrt{{\mathbb{V}\left(w\right)}{\mathbb{V}\left(y\right)}}$
is the correlation coefficient of $y$ and $w$. We exploit this variance
reduction to design a reward function estimator with tight confidence bounds.

###  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 is motivated by the control
variate method, except the control variate is parameterized by function in our
setting. As $w_{s,i}$ is the $i^{\text{th}}$ auxiliary feedback observed with
reward $y_{s}$, the hybrid reward for reward ($y_{s}$) with its $q$ auxiliary
feedback $\\{w_{s,i}\\}_{i=1}^{q}$ is defined by

$z_{s,q}\doteq
y_{s}-\sum_{i=1}^{q}\beta_{i}(w_{s,i}-g_{i}(x_{s}))=y_{s}-(\bm{w}_{s}-\bm{g}_{s})\bm{\beta},$
(2)

where $\bm{w}_{s}=\left(w_{s,1},\ldots,w_{s,q}\right)$,
$\bm{g}_{s}=\left(g_{1}(x_{s}),\ldots,g_{q}(x_{s})\right)$, and
$\bm{\beta}=\left(\beta_{1},\ldots,\beta_{q}\right)^{\top}$. Let
$\Sigma_{\bm{ww}}\in\mathbb{R}^{q\times q}$ be the covariance matrix among
auxiliary feedback and $\sigma_{\bm{yw}}\in\mathbb{R}^{q\times 1}$ be the
vector of covariance between the reward and each of its auxiliary feedback.
Then, the variance of $z_{s,q}$ is minimized by setting the coefficient vector
$\bm{\beta}$ to $\bm{\beta}^{\star}=\Sigma_{\bm{ww}}^{-1}\sigma_{\bm{yw}}$,
and the minimum value is $(1-\rho^{2})\sigma^{2}$, where
${\rho^{2}}=\sigma_{\bm{yw}}^{\top}\Sigma_{\bm{ww}}^{-1}\sigma_{\bm{yw}}/\sigma^{2}$
is the multiple correlation coefficient of reward and its auxiliary feedback.

However, $\Sigma_{\bm{ww}}$ and $\sigma_{\bm{yw}}$ can be unknown in practice
and need to be estimated to get the best estimate for $\bm{\beta}^{\star}$ to
achieve maximum variance reduction. In our following result, we drive the best
linear unbiased estimator of $\bm{\beta}$ (i.e., $\bm{\hat{\beta}}_{t}$) using
$t$ observations of rewards and their auxiliary feedback.

######  Lemma 1.

Let $t>q+2\in\mathbb{N}$ and $f_{t}$ be the estimate of function $f$ which
uses all information available at the end of round $t$, i.e.,
$\left\\{x_{s},y_{s},\bm{w}_{s}\right\\}_{s=1}^{t}$. Then, the best linear
unbiased estimator of $\bm{\beta}^{\star}$ is

$\bm{\hat{\beta}}_{t}\doteq(\bm{W}_{t}^{\top}\bm{W}_{t})^{-1}\bm{W}_{t}^{\top}\bm{Y}_{t},$

where $\bm{W}_{t}$ is a $t\times q$ matrix whose $s^{\text{th}}$ row is
$(\bm{w}_{s}-\bm{g}_{s})$ and
$\bm{Y}_{t}=(y_{1}-f_{t}(x_{1}),\ldots,y_{t}-f_{t}(x_{t}))$.

The proof follows after doing some manipulations in Eq. 2 and then using
results from linear regression theory. The detailed proof of 1 and all other
missing proofs are given in the supplementary material. After having a new
observation of reward and its auxiliary feedback, the best linear unbiased
estimator of $\bm{\beta}^{\star}$ is re-estimated. If $\Sigma_{\bm{ww}}$ or
$\sigma_{\bm{yw}}$ are known, we can directly use them to estimate
$\bm{\beta}^{\star}$ by replacing $\bm{W}_{t}^{\top}\bm{W}_{t}$ with
$\Sigma_{\bm{ww}}$ and $\bm{W}_{t}^{\top}\bm{Y}_{t}$ with $\sigma_{\bm{yw}}$
in 1. The following result describes the properties of the hybrid reward when
$\bm{\beta}^{\star}$ is replaced by $\bm{\hat{\beta}}_{t}$ in Eq. 2.

######  Theorem 1.

Let $t>q+2\in\mathbb{N}$. If $\bm{\hat{\beta}}_{t}$ as defined in 1 is used to
compute hybrid reward $z_{s,q}$ for any $s\leq t\in\mathbb{N}$, then
$\mathbb{E}\left[z_{s,q}\right]=f(x_{s})$ and
$\mathbb{V}\left(z_{s,q}\right)=\left(1+\frac{q}{t-q-2}\right)(1-{\rho^{2}})\sigma^{2}$.

The key takeaways from 1 are as follows. First, the hybrid reward using
$\bm{\hat{\beta}}_{t}$ is an unbiased estimator of reward function and hence,
we can still use it to estimate the reward function $f$. Second, there is a
less reduction in variance (i.e., by a factor $({t-2})/({t-q-2})$ of maximum
possible variance reduction) when $\bm{\hat{\beta}}_{t}$ is used for
constructing hybrid reward in Eq. 2.

The variance reduction (given in 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$
gives 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}$ increases, leading to more variance reduction.
However, the term $\frac{t-2}{t-q-2}$ increases at the same time, which can
negate the variance reduction achieved by smaller $\rho^{2}$. 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 to the linear bandit setting in which
the reward and auxiliary feedback functions are linear. In this setting, a
learner selects an action $x_{t}$ and observes a reward
$y_{t}=x_{t}^{\top}\theta^{\star}+\varepsilon_{t}$, where
$\theta^{\star}\in\mathbb{R}^{d}$ ($d\geq 1$) is unknown and $\varepsilon_{t}$
is the zero-mean Gaussian noise with known variance $\sigma^{2}$. The learner
also observes $q$ auxiliary feedback, where $i$-th auxiliary feedback is
denoted by $w_{t,i}=x_{t}^{\top}\theta_{w,i}^{\star}+\varepsilon_{t,i}^{w}$.
Here, $\theta_{w,i}^{\star}\in\mathbb{R}^{d}$ is known and
$\varepsilon_{t,i}^{w}$ is the zero-mean Gaussian noise with unknown variance
$\sigma_{w,i}^{2}$. Our goal is to learn a 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\times d$ identity matrix,
$V_{t}\doteq\sum_{s=1}^{t-1}x_{s}x_{s}^{\top}$, and $\overline{V}_{t}\doteq
V_{t}+\lambda I$, where $\lambda>0$ is the regularization parameter that
ensures matrix $\overline{V}_{t}$ is a positive definite matrix. The notation
$\left\|x\right\|_{A}$ denotes the weighted $l_{2}$-norm of vector
$x\in\mathbb{R}^{d}$ with respect to a positive definite matrix
$A\in\mathbb{R}^{d\times d}$.

As shown in 1, the hybrid rewards is an unbiased reward estimator with a
smaller variance than observed rewards. Thus, hybrid rewards lead to tighter
confidence bounds for parameter $\theta^{\star}$ than observed rewards. We
propose a simple but effective method to exploit correlated auxiliary
feedback, i.e., using hybrid rewards to estimate reward function instead of
observed rewards.

Using this method, we adapt the well-known 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 $\lambda>0$ as input and then
initializes $\overline{V}_{1}=\lambda I$ and sets
$\hat{\theta}^{z}_{1}=0_{\mathbb{R}^{d}}$ as initial estimate of parameter
$\theta^{\star}$. The superscript ‘$z$’ in $\hat{\theta}^{z}_{1}$ implies that
hybrid rewards are used for estimating $\theta^{\star}$. At the beginning of
round $t$, the algorithm selects an action $x_{t}$ that maximizes the upper
confidence bound of the action’s reward, which is a sum of the estimated
reward for the action ($x^{\top}\hat{\theta}^{z}_{t}$) and a confidence bonus
$\alpha^{\sigma}_{t}\left\|x\right\|_{\overline{V}_{t}^{-1}}$. In the
confidence bonus, the first term ($\alpha^{\sigma}_{t}$) is a slowly
increasing function in $t$ whose value is given in 2, and the second term
($\left\|x\right\|_{\overline{V}_{t}^{-1}}$) decreases to zero as $t$
increases.

OFUL-AF Algorithm for Linear Bandits with Auxiliary Feedback

1: Input: $\lambda>0$

2: Initialization: $\overline{V}_{1}=\lambda I$ and
$\hat{\theta}^{z}_{1}=0_{\mathbb{R}^{d}}$

3: for $t=1,2,\ldots$ do

4: Select action
$x_{t}=\arg\\!\max_{x\in\mathcal{X}}\left(x^{\top}\hat{\theta}^{z}_{t}+\sigma\alpha_{t}\left\|x\right\|_{\overline{V}_{t}^{-1}}\right)$

5: Observe reward $y_{t}$ and its auxiliary feedback $\\{w_{t,i}\\}_{i=1}^{q}$

6: If $t\vspace{-0.5mm}>\vspace{-0.5mm}q+2$, compute upper bound of hybrid
reward’s sample variance ($\bar{\nu}_{z,t}$) or else
$\bar{\nu}_{z,t}\vspace{-0.5mm}=\vspace{-0.5mm}\sigma^{2}$

7: If $t\leq q+2$ or $\bar{\nu}_{z,t}\geq\sigma^{2}$, set
$\bm{\hat{\beta}}_{t}=0$ or else compute $\bm{\hat{\beta}}_{t}$ using 1

8: $\forall s\leq t\in\mathbb{N}:$ compute $z_{s,q}$ using
$\boldsymbol{\hat{\beta}}_{t}$ in Eq. 2

9: Set $\overline{V}_{t+1}=\overline{V}_{t}+x_{t}x_{t}^{\top}$,
$\hat{\theta}^{z}_{t+1}=\overline{V}_{t+1}^{-1}\sum_{s=1}^{t}x_{s}z_{s,q}$

10: end for

After selecting an action $x_{t}$, the algorithm observes the reward $y_{t}$
with its associated auxiliary feedback $\\{w_{t,i}\\}_{i=1}^{q}$. It computes
the upper bound on sample variance of hybrid reward (denoted by
$\bar{\nu}_{z,t}$111Let $\hat{\nu}_{z,t}$ be the sample variance estimate of
hybrid rewards (details in Section A.2). Then,
$\bar{\nu}_{z,t}=\frac{(t-2)\hat{\nu}_{z,t}}{\chi^{2}_{1-\delta,t}}$, where
$\chi^{2}_{1-\delta,t}$ denotes $100(1-\delta)^{\text{th}}$ percentile value
of the chi-squared distribution with $t-2$ degrees of freedom.) if $t>q+2$ or
else it is set to $\sigma^{2}$ and then checks two conditions. The first
condition (i.e., $t\leq q+2$) guarantees the sample variance is well-defined.
Whereas the second condition (i.e., $\bar{\nu}_{z,t}>\sigma^{2}$) ensures the
algorithm at least be as good as OFUL because $\bar{\nu}_{z,t}$ can be larger
than $\sigma^{2}$ due to the overestimation in initial rounds. If both
conditions $t\leq q+2$ and $\bar{\nu}_{z,t}\geq\sigma^{2}$ fail, the value of
$\bm{\hat{\beta}}_{t}$ is re-computed as defined in 1. The updated
$\bm{\hat{\beta}}_{t}$ is then used to update all hybrid rewards, i.e.,
$z_{s,q},\leavevmode\nobreak\ \forall s\leq t\in\mathbb{N}$. Finally, the
values of $\overline{V}_{t+1}$ and $\hat{\theta}_{t+1}$ are updated as
$\overline{V}_{t+1}=\overline{V}_{t}+x_{t}x_{t}^{\top}$ and
$\hat{\theta}^{z}_{t+1}=\overline{V}_{t+1}^{-1}\sum_{s=1}^{t}x_{s}z_{s,q}$,
which are then used to select the action in the following round. When
$\bm{\hat{\beta}}_{t}=0$ for all hybrid rewards, hybrid rewards are the same
as the observed rewards, and hence OFUL-AF is the same as OFUL.

The regret analysis of any bandit algorithm hinges on bounding the
instantaneous regret for each action. The following result gives an upper
bound on the instantaneous regret of OFUL-AF.

######  Theorem 2.

With a probability of at least $1-2\delta$, the instantaneous regret of OFUL-
AF in round $t$ is

$r_{t}(\text{{\ref{alg:OFUL-AF}}})\leq
2\left(\alpha_{t}^{\sigma}+\lambda^{1/2}S\right)\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}},$

where
$\alpha_{t}^{\sigma}=\sqrt{\min\left(\sigma^{2},\bar{\nu}_{z,t-1}\right)}\leavevmode\nobreak\
\alpha_{t}$, $\left\|\theta^{\star}\right\|_{2}\leq S$, and
$\alpha_{t}=\sqrt{d\log\left(\frac{1+tL^{2}/\lambda}{\delta}\right)}$. For
$t>q+2$ and $\bar{\nu}_{z,t}<\sigma^{2}$,
$\mathbb{E}\left[r_{t}(\text{{\ref{alg:OFUL-
AF}}})\right]\leq\widetilde{O}\left(\left(\frac{(t-3)(1-\rho^{2})}{t-q-3}\right)^{\frac{1}{2}}r_{t}(\text{{OFUL}})\right).$
Here, $\widetilde{O}$ hides constant terms.

The proof follows by bounding the estimation error of the parameter
$\theta^{\star}$ when the estimation method uses auxiliary feedback. This
result shows that auxiliary feedback leads to a better instantaneous regret
upper bound and a better regret (as defined in Eq. 1) than the vanilla OFUL
algorithm. Since the improvement in instantaneous regret increase with $t$,
having a 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 an unbiased estimator of an unknown variable $\mu$ and a random
variable $w$ with a known estimated mean ($\omega_{e}$) be a control variate
of $y$. As long as the known estimated mean is an unbiased estimator of $w$,
one can use it to reduce the variance of $y$ as follows. For any choice of a
coefficient $\beta_{e}$, define a new random variable as $z_{e}\doteq
y-\beta_{e}\bar{w}$, where $\bar{w}=w-\omega_{e}$. Since $\omega_{e}$ is an
unbiased estimator of $w$, it is straightforward to show that $z_{e}$ is also
an unbiased estimator of $y$.

By using properties of variance and covariance, the variance of $z_{e}$ is
given by

$\text{Var}(z_{e})=\text{Var}(y)+\beta^{2}_{e}\text{Cov}(\bar{w},\bar{w})-2\beta_{e}\text{Cov}(y,\bar{w}).$

The variance of $z_{e}$ is minimized by setting $\beta_{e}$ to
$\beta^{\star}_{e}=\text{Cov}(\bar{w},\bar{w})^{-1}\text{Cov}(y,\bar{w})$ and
the minimum value of $\text{Var}(z_{e})$ is $(1-\rho_{e}^{2})\text{Var}(y)$,
where
$\rho_{e}=\text{Cov}(y,\bar{w})\left(\text{Cov}(\bar{w},\bar{w})^{-1}/\text{Var}(y)\right)\text{Cov}(y,\bar{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 $w_{s,i}$ be the $i^{\text{th}}$ auxiliary
feedback observed with reward $y_{s}$ and $g_{e,i}$ be the unbiased estimator
of function $g_{i}$. Then, the hybrid reward with $q$ estimated auxiliary
feedback functions is defined by

$z_{e,s,q}=y_{s}-\sum_{i=1}^{q}\beta_{e,i}(w_{s,i}-g_{e,i}(x_{t}))=y_{s}-(\bm{w}_{s}-\bm{g}_{e,s})\bm{\beta}_{e}.$
(3)

where $\bm{w}_{s}=\left(w_{s,1},\ldots,w_{s,q}\right)$,
$\bm{g}_{e,s}=\left(g_{e,1}(x_{s}),\ldots,g_{e,q}(x_{s})\right)$, and
$\bm{\beta}_{e}=\left(\beta_{e,1},\ldots,\beta_{e,q}\right)^{\top}$. Let
$\Sigma_{\bm{\bar{w}\bar{w}}}\in\mathbb{R}^{q\times q}$ denote the covariance
matrix among centered auxiliary feedback (i.e.,
$\bm{\bar{w}_{s}}=\bm{w}_{s}-\bm{g}_{e,s}$), and
$\sigma_{\bm{y\bar{w}}}\in\mathbb{R}^{q\times 1}$ denote the vector of
covariance between reward and its centered auxiliary feedback. Then, the
variance of $z_{e,s,q}$ is minimized by setting the $\bm{\beta}_{e}$ to
$\bm{\beta}^{\star}_{e}=\Sigma_{\bm{\bar{w}\bar{w}}}^{-1}\sigma_{\bm{y\bar{w}}}$,
and the minimum value of $\text{Var}(z_{e,s,q})$ is
$(1-\rho_{e}^{2})\sigma^{2}$, where
${\rho_{e}^{2}}=\sigma_{\bm{y\bar{w}}}^{\top}\Sigma_{\bm{\bar{w}\bar{w}}}^{-1}\sigma_{\bm{y\bar{w}}}/\sigma^{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 $g_{i}$. As no optimal
partitioning strategy is known, we adopt the Independent Samples (IS) and
Multi-Fidelity (MF) sampling strategy for our setting where finite samples of
auxiliary feedback are available. Both strategies are proven to be
asymptotically optimal (Gorodetsky et al., 2020), implying the variance
reduction is asymptotically the same as if auxiliary feedback functions are
known.

#### IS and MF sampling strategy:

Let $s$ and $s_{i}\supset s$ be the sample sets used for estimating functions
$f$ and $g_{i}$, respectively. Then, for the IS sampling strategy,
$(s_{i}\setminus s)\cap(s_{j}\setminus s)=\varnothing$ for $i\neq j$, i.e.,
the extra samples used for estimating the function $g_{i}$ are unique.
Whereas, for the MF sampling strategy, $s_{i}=s\cup_{j=1}^{i}s^{\prime}_{j}$
and $s_{i}^{\prime}\cap s_{j}^{\prime}=\varnothing$ for $i\neq j$, i.e., the
estimation of function $g_{i}$ uses the samples that were used for estimating
function $g_{i-1}$ with some additional samples. Refer to Fig. 1 for the
visual representation of both sampling strategies.

Figure 1:  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).

After adopting Theorem 3 and Theorem 4 from Gorodetsky et al. (2020) to our
setting, we can further simplify $\Sigma_{\bm{\bar{w}\bar{w}}}$ and
$\sigma_{\bm{y\bar{w}}}$ when IS and MF sampling strategies (denoted by $e$)
are used for estimating auxiliary feedback functions as follows:

$\Sigma_{\bm{\bar{w}\bar{w}}}=({\Sigma_{\bm{{w}{w}}}\circ\bm{F}_{e}})/{t}\text{
and
}\sigma_{\bm{y\bar{w}}}=({\text{diag}\left(\bm{F}_{e}\right)\circ\sigma_{\bm{y{w}}}})/{t},$

where $t$ denotes the number of reward observations with its auxiliary
feedback, $\text{diag}(A)$ represents a vector whose elements are the diagonal
of the matrix $A$, and $\circ$ denotes an element-wise product. The $ij$-th
element of matrix $\bm{F}_{e}\in\mathbb{R}^{q\times q}$ is

$\displaystyle
f_{e,ij}=\left\\{\begin{array}[]{ll}(({r_{i}-1})({r_{j}-1}))/({r_{i}}{r_{j}})&\mbox{if
}i\neq j\mbox{ and }e=\mbox{IS}\\\
({\min(r_{i},r_{j})-1})/{\min(r_{i},r_{j})}&\mbox{if }i\neq j\mbox{ and
}e=\mbox{MF}\\\ ({r_{i}-1})/{r_{i}}&\mbox{otherwise},\end{array}\right.$

where $r_{i}\in\mathbb{R}^{+}$ is the ratio between the total number of
samples used for estimating function $g_{i}$ by sampling strategy $e$ and the
total number of samples used for estimating $f$.

Since $\Sigma_{\bm{\bar{w}\bar{w}}}$ and $\sigma_{\bm{y\bar{w}}}$ may be
unknown, they must be estimated to get the best estimate for
$\bm{\beta}^{\star}$. Our following result gives the best linear unbiased
estimator of $\bm{\beta}_{e}$ (i.e., $\bm{\hat{\beta}}_{e,t}$) that uses $t$
observations of rewards and their auxiliary feedback with estimated auxiliary
feedback functions.

######  Lemma 2.

Let $t>q+2\in\mathbb{N}$, $e$ is the sampling strategy, and $f_{t}$ be the
estimate of function $f$ at the end of round $t$ which uses
$\left\\{x_{s},y_{s},\bm{w}_{s}\right\\}_{s=1}^{t}$. Then, the best linear
unbiased estimator of $\bm{\beta}^{\star}_{e}$ is

$\bm{\hat{\beta}}_{e,t}=(\bm{W}_{t}^{\top}\bm{W}_{t}\circ\bm{F}_{e})^{-1}\left(\text{diag}\left(\bm{F}_{e}\right)\circ\bm{W}_{t}^{\top}\bm{Y}_{t}\right),$

where $\bm{W}_{t}$ is a $t\times q$ matrix whose $s^{\text{th}}$ row is
$\bm{w}_{s}-\bm{g}_{e,s}$ and
$\bm{Y}_{t}=(y_{1}-f_{t}(x_{1}),\ldots,y_{t}-f_{t}(x_{t}))$.

After adopting matrix manipulation tricks from Pham and Gorodetsky (2022) to
our setting, the proof follows similar steps as the proof of 1. We now
characterize the properties of the hybrid reward that uses either IS or MF
sampling strategy for estimating auxiliary feedback functions.

######  Theorem 3.

Let $t>q+2\in\mathbb{N}$ and $e$ is the sampling strategy. If
$\bm{\hat{\beta}}_{e,t}$ as defined in 2 is used to compute hybrid reward
$z_{e,s,q}$ for any $s\leq t\in\mathbb{N}$, then
$\mathbb{E}\left[z_{e,s,q}\right]=f(x_{s})$ and
$\mathbb{V}\left(z_{e,s,q}\right)=\left(1+\frac{a(e)q}{t-q-2}\right)(1-{\rho_{e}^{2}})\sigma^{2}$,
where $a(\text{IS})=1$, $a(\text{MF})=\frac{r-1}{r}$ if
$r_{i}=r,\leavevmode\nobreak\ \forall i\in\\{1,2,\ldots,q\\}$ when using MF
sampling strategy for estimating auxiliary feedback functions.

The key takeaways from 3 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
$\rho_{e}^{2}\leq\rho^{2}$.

######  Remark 1.

As samples for estimating auxiliary functions increase compared to the reward
function, the variance reduction from IS and MF sampling strategy converges to
the reduction achieved using known auxiliary functions. As $\forall
i:r_{i}\rightarrow\infty$, then $\bm{F}_{e}\rightarrow\bm{1}_{q\times q}$. It
is now straightforward to see that $\Sigma_{\bm{\bar{w}\bar{w}}}$ will become
$\Sigma_{\bm{{w}{w}}}$, $\sigma_{\bm{y\bar{w}}}$ will become
$\sigma_{\bm{y{w}}}$, and hence $\rho_{e}^{2}=\rho^{2}$ as $\forall
i:r_{i}\rightarrow\infty$.

######  Remark 2.

The IS and MF sampling strategies are shown to be 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. 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 an 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 1 (AFC Bandit Algorithm).

Any bandit algorithm $\mathfrak{A}$ is Auxiliary Feedback Compatible if: (i)
$\mathfrak{A}$ can use correlated reward samples to construct upper confidence
bound for reward function and (ii) with probability $1-\delta$, its estimated
reward function $f_{t}^{\mathfrak{A}}$ has the following property:

$|f_{t}^{\mathfrak{A}}(x)-f(x)|\leq\sigma
h(x,\mathcal{O}_{t})+l(x,\mathcal{O}_{t}),$

where $x\in\mathcal{X}$, $\sigma^{2}$ is the variance of Gaussian noise in
observed reward, and $\mathcal{O}_{t}$ denotes the observations of actions and
their rewards with the parameters of $\mathfrak{A}$ 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 kl-UCB (Cappé et
al., 2013) are not AFC as 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., 2011), UCB-GLM (Li et al., 2017),
IGP-UCB, and GP-TS (Chowdhury and Gopalan, 2017) are AFC as they all use
techniques proposed in Abbasi-Yadkori et al. (2011) for building the upper
confidence bound, which does not need reward samples to 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 feedback by replacing reward with its respective hybrid reward as
shown in Fig. 1 (rightmost figure). We next give an upper bound on the
instantaneous regret for any AFC bandit algorithm that uses hybrid rewards
instead of observed rewards.

######  Theorem 4.

Let $\mathfrak{A}$ be an AFC bandit algorithm with
$|f^{\mathfrak{A}}_{t}(x)-f(x)|\leq\sigma
h(x,\mathcal{O}_{t})+l(x,\mathcal{O}_{t})$ and $\bar{\nu}_{e,z,t}$ be the
upper bound on sample variance of hybrid reward, whose value is set to
$\sigma^{2}$ for $t\leq q+2$. Then, with a probability of at least
$1-2\delta$, the instantaneous regret of $\mathfrak{A}$ after using hybrid
rewards (named $\mathfrak{A}$-AF) for reward function estimation in round $t$
is

$r_{t}(\mathfrak{A}\textnormal{-AF})\leq
2\min(\sigma,(\bar{\nu}_{e,z,t})^{\frac{1}{2}})h(x,\mathcal{O}_{t})+l(x,\mathcal{O}_{t}),$

where $e=\\{\text{IS, MF, KF}\\}$, and KF denotes the case where auxiliary
functions are known. For $t>q+2$ and $\bar{\nu}_{e,z,t}<\sigma^{2}$,
$\mathbb{E}\left[r_{t}(\mathfrak{A}\textnormal{-AF})\right]\leq\widetilde{O}\left(\left(\left(\frac{t-(1-a(e))q-3}{t-q-3}\right)(1-{\rho_{e}^{2}})\right)^{\frac{1}{2}}r_{t}(\mathfrak{A})\right),$
where $a(\text{KF})=1$.

After using 1 and 3 to replace the variance of hybrid reward, the proof
follows similar steps as the proof of 2. We have given more details about the
values of $h(x,\mathcal{O}_{t})$ and $l(x,\mathcal{O}_{t})$ for different AFC
bandit algorithms in Table 1.

Table 1: Values of $h(x,\mathcal{O}_{t})$ and $l(x,\mathcal{O}_{t})$ for different AFC bandit algorithms AFC bandit algorithm | $h(x,\mathcal{O}_{t})$ | $l(x,\mathcal{O}_{t})$
---|---|---
OFUL (Abbasi-Yadkori et al., 2011) | $\sqrt{d\log\left(\frac{1+tL^{2}/\lambda}{\delta}\right)}\left\|x\right\|_{\overline{V}_{t}^{-1}}$ | $\lambda^{\frac{1}{2}}S\left\|x\right\|_{\overline{V}_{t}^{-1}}$
Lin-UCB (OFUL for contextual setting) | $\sqrt{d\log\left(\frac{1+tL^{2}/\lambda}{\delta}\right)}\left\|x\right\|_{\overline{V}_{t}^{-1}}$ | $\lambda^{\frac{1}{2}}S\left\|x\right\|_{\overline{V}_{t}^{-1}}$
GLM-UCB (Li et al., 2017) | $\sqrt{\frac{d}{2}\log(1+2t/d)+\log(1/\delta)}\frac{\left\|x\right\|_{{V}_{t}^{-1}}}{\kappa}$ | 0
IGP-UCB (Chowdhury and Gopalan, 2017) | $\sqrt{2(\gamma_{t-1}+1+\log(1/\delta))}\sigma_{t-1}(x)$ | $B\sigma_{t-1}(x)$

##  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 in Eq. 1 with a $95\%$ confidence interval (vertical line on
each curve shows the confidence interval). Due to space constraints, the
details of used problem instances are given in Section 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 Section A.5). The formal setting of a contextual bandits with
auxiliary feedback is given in Section A.4. We used the following existing
bandit algorithms for these settings: OFUL (Abbasi-Yadkori et al., 2011) 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-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 are 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 ‘-IS/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 to the re-
computation of all variables that are 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.e., $g_{i}(x)+\varepsilon_{g}$ is available instead of $g_{i}(x)$
(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 a 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.

(a) Linear Bandit

(b) Linear Contextual Bandits

(c) Non-linear Contextual Bandits

(d) Biased Estimator

(e) Estimator from historical data

(f) Influence of correlation

Figure 2:  Top row: Comparing regret of different variants with their
benchmark bandit algorithms in different settings. Bottom row:  Regret vs.
different biases in Lin-UCB-BE (left figure), regret vs. number of historical
samples of auxiliary feedback in Lin-UCB-EH (middle figure), and regret of
Lin-UCB-AF vs. varying correlation coefficients of reward and its auxiliary
feedback (right figure).

Regret vs. different biased estimator: To know the effect of bias in auxiliary
feedback (i.e., $\varepsilon_{g})$ 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 in regret, we set
$\varepsilon_{g}=\\{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 Lin-
UCB. This experiment demonstrates that as long as the bias in auxiliary
feedback is 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 to
better performance. To observe this, we use estimators using different numbers
of auxiliary feedback samples, i.e., $n_{h}=\\{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 a few samples even
performs poorly than Lin-UCB, as shown in Fig. 2e.

Regret vs. 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 as a control variate and then extend control variate theory
to a setting 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 is improved by a factor of
$O((1-\rho^{2})^{\frac{1}{2}})$, where $\rho$ is 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 non-Gaussian 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

  * Slivkins (2019) Aleksandrs Slivkins.  Introduction to Multi-Armed Bandits.  _Foundations and Trends® in Machine Learning_ , 2019\.
  * Lattimore and Szepesvári (2020) Tor Lattimore and Csaba Szepesvári.  _Bandit Algorithms_.  Cambridge University Press, 2020.
  * Li et al. (2010) Lihong Li, Wei Chu, John Langford, and Robert E Schapire.  A Contextual-Bandit Approach to Personalized News Article Recommendation.  In _Proc. WWW_ , pages 661–670, 2010.
  * Chu et al. (2011) Wei Chu, Lihong Li, Lev Reyzin, and Robert E Schapire.  Contextual Bandits with Linear Payoff Functions.  In _Proc. AISTATS_ , pages 208–214, 2011.
  * Abbasi-Yadkori et al. (2011) Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved Algorithms for Linear Stochastic Bandits.  In _Proc. NeurIPS_ , pages 2312–2320, 2011.
  * Agrawal and Goyal (2013) Shipra Agrawal and Navin Goyal.  Thompson Sampling for Contextual Bandits with Linear Payoffs.  In _Proc. ICML_ , pages 127–135, 2013.
  * Filippi et al. (2010) Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári.  Parametric Bandits: The Generalized Linear Case.  In _Proc. NeurIPS_ , pages 586–594, 2010.
  * Li et al. (2017) Lihong Li, Yu Lu, and Dengyong Zhou.  Provably Optimal Algorithms for Generalized Linear Contextual Bandits.  In _Proc. ICML_ , pages 2071–2080, 2017.
  * Jun et al. (2017) Kwang-Sung Jun, Aniruddha Bhargava, Robert Nowak, and Rebecca Willett.  Scalable Generalized Linear Bandits: Online Computation and Hashing.  In _Proc. NeurIPS_ , pages 99–109, 2017.
  * Valko et al. (2013) Michal Valko, Nathan Korda, Rémi Munos, Ilias Flaounas, and Nello Cristianini.  Finite-time Analysis of Kernelised Contextual Bandits.  In _Proc. UAI_ , pages 654–663, 2013.
  * Chowdhury and Gopalan (2017) Sayak Ray Chowdhury and Aditya Gopalan.  On Kernelized Multi-armed Bandits.  In _Proc. ICML_ , pages 844–853, 2017.
  * Alon et al. (2015) Noga Alon, Nicolo Cesa-Bianchi, Ofer Dekel, and Tomer Koren.  Online Learning with Feedback Graphs: Beyond Bandits.  In _Proc. COLT_ , pages 23–35, 2015.
  * Wu et al. (2015) Yifan Wu, András György, and Csaba Szepesvári.  Online Learning with Gaussian Payoffs and Side Observations.  In _Proc. NeurIPS_ , pages 1360–1368, 2015.
  * Lavenberg and Welch (1981) Stephen S Lavenberg and Peter D Welch.  A Perspective on the Use of Control Variables to Increase the Efficiency of Monte Carlo Simulations.  _Management Science_ , pages 322–335, 1981.
  * Lavenberg et al. (1982) Stephen S Lavenberg, Thomas L Moeller, and Peter D Welch.  Statistical Results on Control Variables with Application to Queueing Network Simulation.  _Operations Research_ , pages 182–202, 1982.
  * Verma and Hanawal (2021) Arun Verma and Manjesh K Hanawal.  Stochastic Multi-Armed Bandits with Control Variates.  In _Proc. NeurIPS_ , pages 27592–27603, 2021.
  * Nelson (1990) Barry L Nelson.  Control Variate Remedies.  _Operations Research_ , pages 974–992, 1990.
  * Kreutzer et al. (2017) Julia Kreutzer, Artem Sokolov, and Stefan Riezler.  Bandit Structured Prediction for Neural Sequence-to-Sequence Learning.  In _Proc. ACL_ , pages 1503–1513, 2017.
  * Sutton and Barto (2018) Richard S Sutton and Andrew G Barto.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Vlassis et al. (2021) Nikos Vlassis, Ashok Chandrashekar, Fernando Amat Gil, and Nathan Kallus.  Control Variates for Slate Off-Policy Evaluation.  In _Proc. NeurIPS_ , pages 3667–3679, 2021.
  * Caron et al. (2012) Stephane Caron, Branislav Kveton, Marc Lelarge, and S Bhagat.  Leveraging Side Observations in Stochastic Bandits.  In _Proc. UAI_ , pages 142–151, 2012.
  * Mannor and Shamir (2011) Shie Mannor and Ohad Shamir.  From Bandits to Experts: On the Value of Side-Observations.  In _Proc. NeurIPS_ , pages 684–692, 2011.
  * Kocák et al. (2014) Tomáš Kocák, Gergely Neu, Michal Valko, and Rémi Munos.  Efficient learning by implicit exploration in bandit problems with side observations.  In _Proc. NeurIPS_ , pages 613–621, 2014.
  * Alon et al. (2017) Noga Alon, Nicolo Cesa-Bianchi, 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.
  * Verma et al. (2019) Arun Verma, Manjesh K Hanawal, Csaba Szepesvári, and Venkatesh Saligrama.  Online Algorithm for Unsupervised Sensor Selection.  In _Proc. AISTATS_ , pages 3168–3176, 2019.
  * Verma et al. (2020a) Arun Verma, Manjesh K Hanawal, and Nandyala Hemachandra.  Thompson Sampling for Unsupervised Sequential Selection.  In _Proc. ACML_ , pages 545–560, 2020a.
  * Verma et al. (2020b) 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.
  * James (1985) B. A. P. James.  Variance Reduction Techniques.  _Journal of the Operational Research Society_ , pages 525–530, 1985\.
  * Nelson (1989) Barry L Nelson.  Batch size effects on the efficiency of control variates in simulation.  _European Journal of Operational Research_ , pages 184–196, 1989\.
  * Botev and Ridder (2017) Zdravko Botev and Ad Ridder.  Variance Reduction.  _Wiley statsRef: Statistics reference online_ , pages 1–6, 2017.
  * Chen and Ghahramani (2016) Yutian Chen and Zoubin Ghahramani.  Scalable Discrete Sampling as a Multi-Armed Bandit Problem.  In _Proc. ICML_ , pages 2492–2501, 2016.
  * Gorodetsky et al. (2020) 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.
  * Pham and Gorodetsky (2022) Trung Pham and Alex A Gorodetsky.  Ensemble Approximate Control Variate Estimators: Applications to MultiFidelity Importance Sampling.  _Journal on Uncertainty Quantification_ , pages 1250–1292, 2022.
  * Auer et al. (2002) Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.  Finite-time Analysis of the Multiarmed Bandit Problem.  _Machine Learning_ , pages 235–256, 2002.
  * Cappé et al. (2013) 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.
  * Hayashi (2000) F Hayashi.  _Econometrics_.  Princeton University Press, 2000.
  * Van De Geer (2005) Sara A Van De Geer.  Estimation.  _Encyclopedia of Statistics in Behavioral Science_ , pages 549–553, 2005.
  * Schmeiser (1982) Bruce Schmeiser.  Batch Size Effects in the Analysis of Simulation Output.  _Operations Research_ , pages 556–568, 1982.

##  Appendix A Supplementary material

###  A.1 Missing proofs related to auxiliary feedback

### Results from linear regression

We first state results for linear regression that we will use in the
subsequent proofs. Consider the following regression problem with $t$ samples
and $q$ features:

$z_{s}=\bm{x}_{s}^{\top}\bm{\theta}+\varepsilon_{s},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ i\in\\{1,2,\ldots,t\\}$

where $z_{s}\in\mathbb{R}$ is the $s^{\text{th}}$ target variable,
$\bm{x}_{s}=(x_{s1},\ldots,x_{sq})\in\mathbb{R}^{q}$ is the $s^{\text{th}}$
feature vector, $\bm{\theta}\in\mathbb{R}^{q}$ is the unknown regression
parameters, and $\varepsilon_{s}$ is a normally distributed noise with mean
$0$ and constant variance $\sigma^{2}$. The values of noise $\varepsilon_{s}$
form an IID sequence and are independent of $\bm{x}_{s}$. Let

$\bm{Z}_{t}=\begin{pmatrix}z_{1}\\\ \vdots\\\
z_{t}\end{pmatrix},\qquad\bm{X}_{t}=\begin{pmatrix}x_{11}\leavevmode\nobreak\
\leavevmode\nobreak\ \ldots\leavevmode\nobreak\ \leavevmode\nobreak\ x_{1q}\\\
\vdots\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\cdots\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \vdots\\\
X_{t1}\leavevmode\nobreak\ \leavevmode\nobreak\ \ldots\leavevmode\nobreak\
\leavevmode\nobreak\ x_{tq}\end{pmatrix},\text{
and}\quad\bm{\varepsilon}_{t}=\begin{pmatrix}\varepsilon_{1}\\\ \vdots\\\
\varepsilon_{t}\end{pmatrix}.$

Then, the best linear unbiased estimator of $\bm{\theta}$ is
$\bm{\hat{\theta}}_{t}=(\bm{X}_{t}^{\top}\bm{X}_{t})^{-1}\bm{X}_{t}^{\top}\bm{Z}_{t}$,
which has the following finite sample properties.

######  Fact 1.

The following are the finite sample properties of the least square estimator
$\bm{\hat{\theta}}_{t}$:

$\displaystyle 1.\leavevmode\nobreak\
\mathbb{E}\left[\bm{\hat{\theta}}_{t}|\bm{X}_{t}\right]=\bm{\theta},$
(unbiased estimator) $\displaystyle 2.\leavevmode\nobreak\
\text{Var}(\bm{\hat{\theta}}_{t}|\bm{X}_{t})=\sigma^{2}(\bm{X}_{t}^{\top}\bm{X}_{t})^{-1},\text{
and}\leavevmode\nobreak\ $ (expression for the variance) $\displaystyle
3.\leavevmode\nobreak\
\text{Var}(\bm{\hat{\theta}}_{ti}|\bm{X}_{t})=\sigma^{2}(\bm{X}_{t}^{\top}\bm{X}_{t})_{ii}^{-1},\leavevmode\nobreak\
$ (element-wise variance)

where $(\bm{X}_{t}^{\top}\bm{X})_{ii}^{-1}$ is the $ii-$element of the matrix
$(\bm{X}_{t}^{\top}\bm{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 $\sigma^{2}$.

######  Fact 2.

(Hayashi, 2000, Proposition 1.2) Let
$\hat{\sigma}^{2}_{t}=\frac{1}{t-q}\sum_{s=1}^{t}(z_{s}-\bm{x}_{s}^{\top}\bm{\hat{\theta}}_{t})^{2}$
be estimator of $\sigma^{2}$ and $t>q$ (so that $\hat{\sigma}^{2}_{t}$ is well
defined). Then, $\hat{\sigma}^{2}_{t}$ is an unbiased estimator of
$\sigma^{2}$, i.e.,
$\mathbb{E}\left[\hat{\sigma}^{2}_{t}|\bm{X}_{t}\right]=\sigma^{2}$.

Using the Schur complement, we have the following results about the inverse of
the block matrix.

######  Fact 3.

Let $G=\begin{pmatrix}t\leavevmode\nobreak\ \leavevmode\nobreak\ B\\\
C\leavevmode\nobreak\ \leavevmode\nobreak\ D\end{pmatrix}$ be a block matrix,
where $t\in\mathbb{R}\setminus\\{0\\}$, $B$, $C$, $D$ are respectively
$1\times q$, $q\times 1$, and $q\times q$ matrices of real numbers. Then,
$G^{-1}_{11}=t^{-1}+t^{-1}B({tD-CB})^{-1}C$.

### Control variates theory

Let $y$ be the random variable of interest with unknown mean $\mu$. There are
$q$ control variates correlated with $y$, where $i^{\text{th}}$ control
variate has mean $\omega_{i}$ and its $s^{\text{th}}$ observation is denoted
by $w_{s,i}$. For any $s\in\\{1,\ldots,t\\}$, we define a variable $z_{s}$
using $s^{\text{th}}$ observation of $y_{s}$ and its control variates as
follows:

$z_{s}=y_{s}-(\bm{w}_{s}-\bm{\omega})\bm{\beta},$

where $\bm{w}_{s}=(w_{s,1},\ldots,w_{s,q})$ and
$\bm{\omega}=(\omega_{1},\ldots,\omega_{q})$. The above equation can be re-
written as:

$y_{s}=z_{s}+(\bm{w}_{s}-\bm{\omega})\bm{\beta}.$

Under the assumption of $z_{s}$ being a unbiased estimator of $\mu$, we can
write $y_{s}$ as follows:

$y_{s}=\mu+(\bm{w}_{s}-\bm{\omega})\bm{\beta}+\varepsilon_{z,s}.$

where $\varepsilon_{z,1},\ldots,\varepsilon_{z,t}$ are IID and have zero mean
Gaussian noise with variance $(1-\rho^{2})\sigma^{2}$. Let

$\bm{\overline{Y}}_{t}=\begin{pmatrix}y_{1}\\\ \vdots\\\
y_{t}\end{pmatrix},\leavevmode\nobreak\
\bm{\overline{W}}_{t}=\begin{pmatrix}1&\bm{w}_{1}-\bm{\omega}\\\
\vdots&\vdots\\\ 1&\bm{w}_{t}-\bm{\omega}\end{pmatrix},\leavevmode\nobreak\
\bm{\gamma}=\begin{pmatrix}\mu\\\ \bm{\beta}\end{pmatrix},\text{
and}\leavevmode\nobreak\
\bm{\varepsilon}_{z,t}=\begin{pmatrix}\varepsilon_{z,1}\\\ \vdots\\\
\varepsilon_{z,t}\end{pmatrix}.$

The best linear unbiased estimator of $\bm{\gamma}$ is
$\bm{\hat{\gamma}}=(\bm{\overline{W}}_{t}^{\top}\bm{\overline{W}}_{t})^{-1}\bm{\overline{W}}_{t}^{\top}\bm{\overline{Y}}_{t}$.
To get $\hat{\mu}_{z,t}$ and $\hat{\beta}^{\star}$, we expand
$\bm{\hat{\gamma}}$ as follows:

$\displaystyle\bm{\hat{\gamma}}$
$\displaystyle=\left(\begin{pmatrix}1&\bm{w}_{1}-\bm{\omega}\\\
\vdots&\vdots\\\
1&\bm{w}_{t}-\bm{\omega}\end{pmatrix}^{\top}\begin{pmatrix}1&\bm{w}_{1}-\bm{\omega}\\\
\vdots&\vdots\\\
1&\bm{w}_{t}-\bm{\omega}\end{pmatrix}\right)^{-1}\begin{pmatrix}1&\bm{w}_{1}-\bm{\omega}\\\
\vdots&\vdots\\\
1&\bm{w}_{t}-\bm{\omega}\end{pmatrix}^{\top}\begin{pmatrix}y_{1}\\\ \vdots\\\
y_{t}\end{pmatrix}$ $\displaystyle=\left(\begin{pmatrix}1&\ldots&1\\\
\bm{w}_{1}-\bm{\omega}&\ldots&\bm{w}_{t}-\bm{\omega}\end{pmatrix}\begin{pmatrix}1&\bm{w}_{1}-\bm{\omega}\\\
\vdots&\vdots\\\
1&\bm{w}_{t}-\bm{\omega}\end{pmatrix}\right)^{-1}\begin{pmatrix}1&\ldots&1\\\
\bm{w}_{1}-\bm{\omega}&\ldots&\bm{w}_{t}-\bm{\omega}\end{pmatrix}\begin{pmatrix}y_{1}\\\
\vdots\\\ y_{t}\end{pmatrix}$
$\displaystyle=\begin{pmatrix}t&\sum_{s=1}^{t}(\bm{w}_{s}-\bm{\omega})\\\
\sum_{s=1}^{t}(\bm{w}_{s}-\bm{\omega})&\sum_{s=1}^{t}(\bm{w}_{s}-\bm{\omega})^{\top}(\bm{w}_{s}-\bm{\omega})\end{pmatrix}^{-1}\begin{pmatrix}\sum_{s=1}^{t}y_{s}\\\
\sum_{s=1}^{t}(\bm{w}_{s}-\bm{\omega})y_{s}\end{pmatrix}$

After taking first matrix from RHS to LHS and using
$\bm{\hat{\gamma}}=\begin{pmatrix}\hat{\mu}_{z,t}\\\
\bm{\hat{\beta}}_{t}\end{pmatrix}$, we have

$\displaystyle\begin{pmatrix}t&\sum_{s=1}^{t}(\bm{w}_{s}-\bm{\omega})\\\
\sum_{s=1}^{t}(\bm{w}_{s}-\bm{\omega})&\sum_{s=1}^{t}(\bm{w}_{s}-\bm{\omega})^{\top}(\bm{w}_{s}-\bm{\omega})\end{pmatrix}\begin{pmatrix}\hat{\mu}_{z,t}\\\
\bm{\hat{\beta}}_{t}\end{pmatrix}$
$\displaystyle=\begin{pmatrix}\sum_{s=1}^{t}y_{s}\\\
\sum_{s=1}^{t}(\bm{w}_{s}-\bm{\omega})y_{s}\end{pmatrix}.$ (4)

From above, we get the following equation:

$\displaystyle
t\hat{\mu}_{z,t}+\left(\sum_{s=1}^{t}(\bm{w}_{s}-\bm{\omega})\right)\bm{\hat{\beta}}_{t}=\sum_{s=1}^{t}y_{s}$
$\displaystyle\implies$
$\displaystyle\hat{\mu}_{z,t}=\frac{1}{t}\sum_{s=1}^{t}y_{s}-\left(\frac{1}{t}\sum_{s=1}^{t}(\bm{w}_{s}-\bm{\omega})\right)\bm{\hat{\beta}}_{t}.$

Using $\hat{\mu}_{y,t}=\frac{1}{t}\sum_{s=1}^{t}y_{s}$ and
$\bm{\hat{\omega}}_{t}=\frac{1}{t}\sum_{s=1}^{t}\bm{w}_{s}$, we get

$\hat{\mu}_{z,t}=\hat{\mu}_{y,t}-(\bm{\hat{\omega}}_{t}-\bm{\omega})\bm{\hat{\beta}}_{t}.$
(5)

Similarly, we have another equation as follows:

$\displaystyle\hat{\mu}_{z,t}\sum_{s=1}^{t}(\bm{w}_{s}-\bm{\omega})+\left(\sum_{s=1}^{t}(\bm{w}_{s}-\bm{\omega})^{\top}(\bm{w}_{s}-\bm{\omega}))\right)\bm{\hat{\beta}}_{t}=\sum_{s=1}^{t}(\bm{w}_{s}-\bm{\omega})y_{s}$
$\displaystyle\implies$
$\displaystyle\bm{\hat{\beta}}_{t}=\left(\sum_{s=1}^{t}(\bm{w}_{s}-\bm{\omega})^{\top}(\bm{w}_{s}-\bm{\omega}))\right)^{-1}\left(\sum_{s=1}^{t}(\bm{w}_{s}-\bm{\omega})(y_{s}-\hat{\mu}_{z,t})\right).$

Using $\bm{{W}}_{t}=\begin{pmatrix}\bm{w}_{1}-\bm{\omega}\\\ \vdots\\\
\bm{w}_{t}-\bm{\omega}\end{pmatrix}$ and
$\bm{Y}_{t}=\begin{pmatrix}y_{1}-\hat{\mu}_{z,t}\\\ \vdots\\\
y_{t}-\hat{\mu}_{z,t}.\end{pmatrix}$, we have

$\implies\bm{\hat{\beta}}_{t}=(\bm{W}_{t}^{\top}\bm{W}_{t})^{-1}\bm{W}_{t}^{\top}\bm{Y}_{t}.$
(6)

In the following, we first state the fundamental results from the control
variates theory.

######  Fact 4.

(Nelson, 1990, Theorem 1) Let $O_{s}=(Y_{s},W_{s,1},\ldots,W_{s,q})^{\top}$
follow a $(q+1)-$variate normal distribution with mean vector
$(\mu,\bm{\omega})$ and $\\{O_{1},\ldots,O_{t}\\}$ be a IID sequence. Assume
$\hat{\mu}_{z,t}=\sum_{s=1}^{t}z_{s}$, where
$z_{s}=y_{s}-(\bm{w}_{s}-\bm{\omega})\bm{\hat{\beta}}_{t}$ and
$\bm{\hat{\beta}}_{t}$ used here is given by Eq. 6, then

$\displaystyle\mathbb{E}\left[\hat{\mu}_{z,t}\right]=\mu\text{ and}$
$\displaystyle\mathbb{V}\left(\hat{\mu}_{z,t}\right)=\left(1+\frac{q}{t-q-2}\right)(1-{\rho^{2}})\mathbb{V}\left(\hat{\mu}_{y,t}\right),$

where
$\sigma_{Y\bm{W}}\Sigma_{\bm{W}\bm{W}}^{-1}\sigma_{Y\bm{W}}^{\top}/\sigma^{2}$
is the square of the multiple correlation coefficient,
$\sigma^{2}=\mathbb{V}\left(Y\right)$, and
$\sigma_{Y\bm{W}}=(\text{Cov}(Y,W_{1}),\ldots,\text{Cov}(Y,W_{q}))$ (we have
dropped the subscript $s$ as observations are IID).

### Auxiliary feedback as control variates

See 1

###### Proof.

Recall Eq. 2 for $s^{\text{th}}$ hybrid reward with known auxiliary functions,
i.e., $z_{s,q}=y_{s}-(\bm{w}_{s}-\bm{g}_{s})\bm{\beta},$ which can be re-
written as $y_{s}=z_{s,q}+(\bm{w}_{s}-\bm{g}_{s})\bm{\beta}$. By definition,
$z_{s,q}=f(x_{s})+\varepsilon_{s}^{z}$ for optimal $\beta$, where
$\varepsilon_{z,s}$ is zero-mean Gaussian noise with variance
$(1-\rho^{2})\sigma^{2}$. Then,
$y_{s}=f(x_{s})+(\bm{w}_{s}-\bm{g}_{s})\bm{\beta}+\varepsilon_{z,s}.$ Let
$\varphi$ be an unknown function that maps every $x$ to a space where
$f(x)=\varphi(x)^{\top}f$ holds. Then we can re-write the above equation as
follows:

$y_{s}=f^{\top}\varphi(x_{s})+(\bm{w}_{s}-\bm{g}_{s})\bm{\beta}+\varepsilon_{z,s}.$

Adapting Eq. 4 to our setting, we have

$\displaystyle\begin{pmatrix}\sum_{s=1}^{t}\varphi(x_{s})^{\top}\varphi(x_{s})&\sum_{s=1}^{t}\varphi(x_{s})^{\top}(\bm{w}_{s}-\bm{g}_{s})\\\
\sum_{s=1}^{t}(\bm{w}_{s}-\bm{g}_{s})^{\top}\varphi(x_{s})&\sum_{s=1}^{t}(\bm{w}_{s}-\bm{g}_{s})^{\top}(\bm{w}_{s}-\bm{g}_{s})\end{pmatrix}\begin{pmatrix}f_{t}\\\
\bm{\hat{\beta}}_{t}\end{pmatrix}$
$\displaystyle=\begin{pmatrix}\sum_{s=1}^{t}\varphi(x_{s})y_{s}\\\
\sum_{s=1}^{t}(\bm{w}_{s}-\bm{g}_{s})y_{s}\end{pmatrix}.$

Let $f_{t}$ is the estimated $f$ using available information, i.e.,
$\\{x_{s},y_{s},\bm{w}_{s}\\}_{s=1}^{t}$. To get best linear unbiased
estimator for $\bm{\beta}^{\star}$, we use the following equation from above
matrix,

$\displaystyle\left(\sum_{s=1}^{t}(\bm{w}_{s}-\bm{g}_{s})^{\top}\varphi(x_{s})\right)f_{t}+\left(\sum_{s=1}^{t}(\bm{w}_{s}-\bm{g}_{s})^{\top}(\bm{w}_{s}-\bm{g}_{s})\right)\bm{\hat{\beta}}_{t}=\sum_{s=1}^{t}(\bm{w}_{s}-\bm{g}_{s})y_{s}$
$\displaystyle\implies$
$\displaystyle\left(\sum_{s=1}^{t}(\bm{w}_{s}-\bm{g}_{s})^{\top}(\bm{w}_{s}-\bm{g}_{s})\right)\bm{\hat{\beta}}_{t}=\sum_{s=1}^{t}(\bm{w}_{s}-\bm{g}_{s})y_{s}-\sum_{s=1}^{t}(\bm{w}_{s}-\bm{g}_{s})^{\top}\left(\varphi(x_{s})^{\top}f_{t}\right)$
$\displaystyle\implies$
$\displaystyle\bm{\hat{\beta}}_{t}=\left(\sum_{s=1}^{t}(\bm{w}_{s}-\bm{g}_{s})^{\top}(\bm{w}_{s}-\bm{g}_{s})\right)^{-1}\sum_{s=1}^{t}(\bm{w}_{s}-\bm{g}_{s})\left(y_{s}-\varphi(x_{s})^{\top}f_{t}\right)$
$\displaystyle\implies$
$\displaystyle\bm{\hat{\beta}}_{t}=\left(\sum_{s=1}^{t}(\bm{w}_{s}-\bm{g}_{s})^{\top}(\bm{w}_{s}-\bm{g}_{s})\right)^{-1}\sum_{s=1}^{t}(\bm{w}_{s}-\bm{g}_{s})\left(y_{s}-f_{t}(x_{s})\right)$

Using definition $f_{t}(x_{s})=\varphi(x_{s})^{\top}f_{t}$,
$\bm{W}_{t}=\begin{pmatrix}\bm{w}_{1}-\bm{g}_{s}\\\ \vdots\\\
\bm{w}_{t}-\bm{g}_{s}\end{pmatrix}$, and
$\bm{Y}_{t}=\begin{pmatrix}y_{1}-f_{t}(x_{1})\\\ \vdots\\\
y_{t}-f_{t}(x_{t}).\end{pmatrix}$, we get

$\implies\bm{\hat{\beta}}_{t}=(\bm{W}_{t}^{\top}\bm{W}_{t})^{-1}\bm{W}_{t}^{\top}\bm{Y}_{t}.\qed$

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 its function value
and defined new centered variables as follows:

$y_{s}^{c}=y_{s}-f(x_{s}),\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \bm{w}_{s}^{c}=\bm{w}_{s}-\bm{g}_{s},\text{ and
}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
z_{s,q}^{c}=z_{s,q}-f(x_{s}).$

In our setting, these centered variables ($y_{s}^{c},\bm{w}_{s}^{c},\text{ and
}z_{s}^{c},$) follow zero mean Gaussian distributions with variance
$\sigma^{2}$,
$\bm{\sigma}^{2}_{w}=(\sigma^{2}_{w,1},\ldots,\sigma^{2}_{w,q})$, and
$(1-\rho^{2})\sigma^{2}$, respectively.

See 1

###### Proof.

The sequence $(y_{s}^{c},\bm{w}_{s}^{c})_{s=1}^{t}$ is an IID sequence and
follows a Gaussian distribution with mean $0$. We now define
$z_{s,q}^{c}=y_{s}^{c}-\bm{w}_{s}^{c}\bm{\beta}=y_{s}^{c}-(\bm{w}_{s}-\bm{g}_{s})\bm{\beta}$,
which can be re-written as
$y_{s,q}^{c}=z_{s}^{c}+(\bm{w}_{s}-\bm{g}_{s})\bm{\beta}$. Let $f_{t}$ be the
estimated $f$ using available information, i.e.,
$\\{x_{s},y_{s},\bm{w}_{s}\\}_{s=1}^{t}$ and hence we can write estimated
$z_{s,q}$ as $\hat{z}_{s,q}=f_{t}(x_{s})$ and hence
$\hat{z}_{s,q}^{c}=f_{t}(x_{s})-f(x_{s})$. Now, adapting Eq. 6 to our setting
and replacing estimated mean in $\bm{Y}_{t}$ by $\hat{z}_{s,q}^{c}$,
$s^{\text{th}}$ value of $\bm{Y}_{t}$ is
$y_{s}^{c}-\hat{z}_{s,q}^{c}=y_{s}-f(x_{s})-(f_{t}(x_{s})-f(x_{s}))=y_{s}-f_{t}(x_{s})$.
With these manipulations, we get the following best linear unbiased estimator
for $\bm{\beta}^{\star}$:

$\bm{\hat{\beta}}_{t}=(\bm{W}_{t}^{\top}\bm{W}_{t})^{-1}\bm{W}_{t}^{\top}\bm{Y}_{t},$

which is the same as defined in 1.

By adapting 4 for a single sample (i.e., $z_{s,q}$) while using
$\bm{\hat{\beta}}_{t}$ to define hybrid reward, we have

$\displaystyle\mathbb{E}\left[z_{s,q}^{c}\right]=0\text{ and}$
$\displaystyle\mathbb{V}\left(z_{s,q}^{c}\right)=\left(1+\frac{q}{t-q-2}\right)(1-{\rho^{2}})\mathbb{V}\left(y_{s}^{c}\right),$

By extending the definition of $\mathbb{E}\left[z_{s,q}^{c}\right]$ we have,

$\mathbb{E}\left[z_{s,q}-f(x_{s})\right]=0\implies\mathbb{E}\left[z_{s,q}\right]-f(x_{s})=0\implies\mathbb{E}\left[z_{s,q}\right]=f(x_{s})$

This proofs the hybrid reward is an unbiased estimator of reward.

Since variance is invariant to constant change, we have

$\displaystyle\mathbb{V}\left(z_{s,q}\right)$
$\displaystyle=\mathbb{V}\left(z_{s,q}-f(x_{s})\right)$
$\displaystyle=\mathbb{V}\left(z_{s,q}^{c}\right)$
$\displaystyle=\left(1+\frac{q}{t-q-2}\right)(1-{\rho^{2}})\mathbb{V}\left(y_{s}^{c}\right)$
$\displaystyle=\left(1+\frac{q}{t-q-2}\right)(1-{\rho^{2}})\mathbb{V}\left(y_{s}-f(x_{s})\right)$
$\displaystyle=\left(1+\frac{q}{t-q-2}\right)(1-{\rho^{2}})\mathbb{V}\left(y_{s}\right).$

Since $\mathbb{V}\left(y_{s}\right)=\sigma^{2}$, we have
$\mathbb{V}\left(z_{s,q}\right)=\left(1+\frac{q}{t-q-2}\right)(1-{\rho^{2}})\sigma^{2}.$
∎

See 2

###### Proof.

Recall the $s^{\text{th}}$ hybrid reward defined in Eq. 3 using sampling
strategy $e$ as $z_{e,s,q}^{e}=y_{s}-(\bm{w}_{s}-\bm{g}_{e,s})\bm{\beta}_{e},$
which can be re-written as
$y_{s}=z_{e,s,q}^{e}+(\bm{w}_{s}-\bm{g}_{e,s})\bm{\beta}_{e}.$ Following
similar steps as of 1, we can re-write the above equation as
$y_{s}=f^{\top}\varphi(x_{s})+(\bm{w}_{s}-\bm{g}_{e,s})\bm{\beta}_{e}+\varepsilon_{z,s}.$

Using $\bm{W}_{e,t}=\begin{pmatrix}\bm{w}_{1}-\bm{g}_{e,s}\\\ \vdots\\\
\bm{w}_{t}-\bm{g}_{e,s}\end{pmatrix}$, and
$\bm{Y}_{t}=\begin{pmatrix}y_{1}-f_{t}(x_{1})\\\ \vdots\\\
y_{t}-f_{t}(x_{t}).\end{pmatrix}$, we get
$\bm{\hat{\beta}}_{e,t}=(\bm{W}_{e,t}^{\top}\bm{W}_{e,t})^{-1}\bm{W}_{e,t}^{\top}\bm{Y}_{t}.$
From Appendix D and E of Gorodetsky et al. (2020), we have
$\bm{W}_{e,t}^{\top}\bm{W}_{e,t}=\bm{W}_{t}^{\top}\bm{W}_{t}\circ\bm{F}_{e}$
and
$\bm{W}_{e,t}^{\top}\bm{Y}_{t}=\text{diag}\left(\bm{F}_{e}\right)\circ\bm{W}_{t}^{\top}\bm{Y}_{t}.$
Using these two equality, we have

$\bm{\hat{\beta}}_{e,t}=(\bm{W}_{t}^{\top}\bm{W}_{t}\circ\bm{F}_{e})^{-1}(\text{diag}\left(\bm{F}_{e}\right)\circ\bm{W}_{t}^{\top}\bm{Y}_{t}).\qed$

See 3

###### Proof.

The proof follows the similar steps as 1 except we adapt the part (b.) of
Theorem 4 from Pham and Gorodetsky (2022) instead of using 4 to show the
variance reduction when sampling strategy (IS or MF) is used for estimating
auxiliary feedback functions. ∎

###  A.2 Unbiased estimate of variance

Consider the following regression problem with target variable $y_{s}$, which
is defined as follows:

$y_{s}=\mu+(\bm{w}_{s}-\bm{\omega})\bm{\beta}+\varepsilon_{z,s}.$

where $\varepsilon_{z,1},\ldots,\varepsilon_{z,t}$ are IID and have zero mean
Gaussian noise with variance $(1-\rho^{2})\sigma^{2}$. Let

$\bm{\overline{Y}}_{t}=\begin{pmatrix}y_{1}\\\ \vdots\\\
y_{t}\end{pmatrix},\leavevmode\nobreak\
\bm{\overline{W}}_{t}=\begin{pmatrix}1&\bm{w}_{1}-\bm{\omega}\\\
\vdots&\vdots\\\ 1&\bm{w}_{t}-\bm{\omega}\end{pmatrix},\leavevmode\nobreak\
\bm{\gamma}=\begin{pmatrix}\mu\\\ \bm{\beta}\end{pmatrix},\text{
and}\leavevmode\nobreak\
\bm{\varepsilon}_{z,t}=\begin{pmatrix}\varepsilon_{z,1}\\\ \vdots\\\
\varepsilon_{z,t}\end{pmatrix}.$

Now, using 1, we have
$\mathbb{V}\left(\hat{\mu}_{z,t}\right)=\sigma^{2}(\bm{\overline{W}}_{t}^{\top}\bm{\overline{W}}_{t})^{-1}_{11},$
where $(\bm{Y}^{\top}\bm{Y})_{11}^{-1}$ is the upper left most element of
matrix $(\bm{Y}^{\top}\bm{Y})^{-1}$ (Schmeiser, 1982). Then after $t$
observations, the unbiased variance estimator of
$\mathbb{V}\left(\hat{\mu}_{z,t}\right)$ is given by

$\hat{\nu}_{z,t}=\hat{\sigma}^{2}_{z,t}(\bm{\overline{W}}_{t}^{\top}\bm{\overline{W}}_{t})^{-1}_{11},$

where
$\hat{\sigma}^{2}_{z,t}=\frac{1}{t-q-1}\sum_{s=1}^{t}(y_{s}-\hat{\mu}_{z,t})^{2}$
(Nelson, 1990), which is also an unbiased variance estimator of $\sigma^{2}$
(from 2). Further, $\hat{\nu}_{z,t}$ is also an unbiased estimator of
$\mathbb{V}\left(\hat{\mu}_{z,t}\right)$, i.e.,
$\mathbb{E}\left[\hat{\nu}_{z,t}\right]=\mathbb{V}\left(\hat{\mu}_{z,t}\right)$
(Nelson, 1990, Theorem 1). We can adapt this approach to our setting. However
when noise variance ($\sigma$) is unknown, computing
$(\bm{\overline{W}}_{t}^{\top}\bm{\overline{W}}_{t})^{-1}_{11}$ may not be
possible to general function $f$ as $\varphi$ function may not be known.
Though the setting in which
$(\bm{\overline{W}}_{t}^{\top}\bm{\overline{W}}_{t})^{-1}_{11}$ can be
computed, we have to use the upper bound of variance to construct the
confidence bound for reward function $f$ as random sample variance estimate
can be small and leads to invalid confidence bounds. Given $t$ observations,
the upper bound of the sample variance is given by
$\bar{\nu}_{z,t}=\frac{(t-2)\hat{\nu}_{z,t}}{\chi^{2}_{1-\delta,t}}$, where
$\chi^{2}_{1-\delta,t}$ denotes $100(1-\delta)^{\text{th}}$ percentile value
of the chi-squared distribution with $t-2$ degrees of freedom.

###  A.3 Missing proofs related to regret analysis

See 2

###### Proof.

When only observed rewards are used for estimating underlying unknown
parameters in the linear bandit setting, i.e.,
$\hat{\theta}_{t}=\overline{V}_{t}^{-1}\sum_{s=1}^{t}x_{s}y_{s}$, then with
probability $1-\delta$, the confidence bound (Abbasi-Yadkori et al., 2011,
Theorem 1) is

$\left\|\hat{\theta}_{t}-\theta^{\star}\right\|_{\bar{V}_{t}}\leq\sigma\sqrt{d\log\left(\frac{1+tL^{2}/\lambda}{\delta}\right)}+\lambda^{1/2}S,$
(7)

where $\sigma^{2}$ is the variance of observed rewards given action (since the
noise variance is $\sigma^{2}$). To ensure the performance of OFUL-AF is as
good as OFUL, we 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.e., $\bar{\nu}_{z,t-1}<\sigma^{2}$. At the beginning of round $t$,
the variance upper bound of hybrid rewards is computed using $t-1$
observations and given by
$\bar{\nu}_{z,t-1}=\frac{(t-2)\hat{\nu}_{z,t-1}}{\chi^{2}_{1-\delta,t}}$,
where $\hat{\nu}_{z,t-1}$ is an unbiased sample variance estimate of hybrid
rewards using $t-1$ observations and $\chi^{2}_{1-\delta,t}$ (implying the
variance upper bound holds with at least probability of $1-\delta$) denotes
$100(1-\delta)^{\text{th}}$ percentile value of the chi-squared distribution
with $t-2$ degrees of freedom. When $\bar{\nu}_{z,t}<\sigma^{2}$, we replace
rewards $\\{y_{s}\\}_{s=1}^{t}$ with its respective hybrid rewards, i.e.,
$\\{z_{s,q}\\}_{s=1}^{t}$ to estimate underlying parameter and use it for next
round. After using hybrid rewards to estimate the unknown parameter, we
replace $\sigma^{2}$ in Eq. 7 with the variance upper bound of hybrid rewards.
Then we get the following upper bound which holds with a probability of
$1-2\delta$.

$\displaystyle\left\|\hat{\theta}_{t}-\theta^{\star}\right\|_{\bar{V}_{t}}$
$\displaystyle\leq\sqrt{\min\left(\sigma^{2},\bar{\nu}_{z,t-1}\right)}\sqrt{d\log\left(\frac{1+tL^{2}/\lambda}{\delta}\right)}+\lambda^{1/2}S$
$\displaystyle=\sqrt{\min\left(\sigma^{2},\bar{\nu}_{z,t-1}\right)}\alpha_{t}+\lambda^{1/2}S$
$\displaystyle\implies\left\|\hat{\theta}_{t}-\theta^{\star}\right\|_{\bar{V}_{t}}$
$\displaystyle=\alpha_{t}^{\sigma}+\lambda^{1/2}S,$

where
$\alpha_{t}^{\sigma}=\sqrt{\min\left(\sigma^{2},\bar{\nu}_{z,t-1}\right)}\alpha_{t}$
and $\alpha_{t}=\sqrt{d\log\left(\frac{1+tL^{2}/\lambda}{\delta}\right)}$.

Let action $x_{t}$ be selected in the round $t$. Then, the instantaneous
regret is given as follows:

$\displaystyle r_{t}$
$\displaystyle=\max_{x\in\mathcal{X}}x^{\top}\theta^{\star}-x_{t}^{\top}\theta^{\star}$
$\displaystyle={x^{\star}}^{\top}\theta^{\star}-x_{t}^{\top}\theta^{\star}\hskip
56.9055pt(\text{as }x^{\star}=\max_{x\in\mathcal{X}}x^{\top}\theta^{\star})$
$\displaystyle=(x^{\star}-x_{t})^{\top}\theta^{\star}$
$\displaystyle=(x^{\star}-x_{t})^{\top}\theta^{\star}+(x^{\star}-x_{t})^{\top}\hat{\theta}_{t}-(x^{\star}-x_{t})^{\top}\hat{\theta}_{t}$
$\displaystyle=(x^{\star}-x_{t})^{\top}\hat{\theta}_{t}-(x^{\star}-x_{t})^{\top}(\hat{\theta}_{t}-\theta^{\star}).$
A sub-optimal action is only selected when its upper confidence bound is
larger than the optimal action. Then, if
$\left\|\hat{\theta}_{t}-\theta^{\star}\right\|_{\overline{V}_{t}}=\alpha_{t}^{\sigma}+\lambda^{1/2}S$,
then we have $\displaystyle r_{t}$
$\displaystyle\leq\alpha_{t}\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}-\alpha_{t}\left\|x^{\star}\right\|_{\overline{V}_{t}^{-1}}-(x^{\star}-x_{t})^{\top}(\hat{\theta}_{t}-\theta^{\star})$
$\displaystyle\leq\alpha_{t}\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}-\alpha_{t}\left\|x^{\star}\right\|_{\overline{V}_{t}^{-1}}-\left\|x^{\star}-x_{t}\right\|_{\overline{V}_{t}^{-1}}\left\|\hat{\theta}_{t}-\theta^{\star}\right\|_{\overline{V}_{t}}$
$\displaystyle\leq\alpha_{t}\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}-\alpha_{t}\left\|x^{\star}\right\|_{\overline{V}_{t}^{-1}}+\alpha_{t}\left\|x^{\star}-x_{t}\right\|_{\overline{V}_{t}^{-1}}$
$\displaystyle=\alpha_{t}(\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}-\left\|x^{\star}\right\|_{\overline{V}_{t}^{-1}}+\left\|x^{\star}-x_{t}\right\|_{\overline{V}_{t}^{-1}})$
$\displaystyle\leq\alpha_{t}(\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}-\left\|x^{\star}\right\|_{\overline{V}_{t}^{-1}}+\left\|X_{t,a_{t}^{\star}}\right\|_{\overline{V}_{t}^{-1}}+\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}})$
$\displaystyle=2\alpha_{t}\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}$
$\displaystyle\implies r_{t}$ $\displaystyle\leq
2(\alpha_{t}^{\sigma}+\lambda^{1/2}S)\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}.$

Let $\bm{X}_{t}=\\{x_{s}\\}_{s=1}^{t}$. For $t>q+2$ and
$\bar{\nu}_{z,t}<\sigma^{2}$, the expected instantaneous regret of OFUL-AF is

$\displaystyle\mathbb{E}\left[r_{t}(\text{{\ref{alg:OFUL-AF}}})\right]$
$\displaystyle\leq\mathbb{E}\left[2(\alpha_{t}^{\sigma}+\lambda^{1/2}S)\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}\right]$
$\displaystyle=\mathbb{E}\left[2(\sqrt{\bar{\nu}_{z,t}}\alpha_{t}+\lambda^{1/2}S)\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}\right]$
$\displaystyle=2\mathbb{E}\left[\mathbb{E}\left[(\sqrt{\bar{\nu}_{z,t}}\alpha_{t}+\lambda^{1/2}S)\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}|\bm{X}_{t}\right]\right]$
$\displaystyle=2\mathbb{E}\left[\alpha_{t}\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}\mathbb{E}\left[\sqrt{\bar{\nu}_{z,t}}|\bm{X}_{t}\right]+\lambda^{1/2}S\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}\right]$
$\displaystyle\leq
2\alpha_{t}\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}\mathbb{E}\left[\mathbb{E}\left[\sqrt{\frac{(t-2)\hat{\nu}_{z,t-1}}{\chi^{2}_{1-\delta,t}}}|\bm{X}_{t}\right]\right]+2\lambda^{1/2}S\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}$
$\displaystyle=2\alpha_{t}\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}\sqrt{\frac{(t-2)}{\chi^{2}_{1-\delta,t}}}\mathbb{E}\left[\sqrt{\hat{\nu}_{z,t-1}}\right]+2\lambda^{1/2}S\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}.$

Since $\hat{\nu}_{z,t-1}$ is an unbiased estimator of the sample variance of
hybrid rewards,
$\mathbb{E}\left[\hat{\nu}_{z,t-1}\right]=\mathbb{V}\left(z_{s,q}\right)$ for
$s\in\\{1,\ldots,t\\}$. Using 1, we have
$\mathbb{V}\left(z_{s,q}\right)=\left(1+\frac{q}{t-q-3}\right)(1-{\rho^{2}})\sigma^{2}=\left(\frac{(t-3)(1-{\rho^{2}})}{t-q-3}\right)\sigma^{2}$
as $t^{\text{th}}$ observation is not available at the beginning of the round
$t$. With increasing $t$, $C_{t}=\sqrt{\frac{(t-2)}{\chi^{2}_{1-\delta,t}}}$
tends to 1. With all these observations, we have

$\displaystyle\mathbb{E}\left[r_{t}(\text{{\ref{alg:OFUL-AF}}})\right]$
$\displaystyle\leq
2C_{t}\left(\frac{(t-3)(1-{\rho^{2}})}{t-q-3}\right)^{\frac{1}{2}}\sigma\alpha_{t}\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}+2\lambda^{1/2}S\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}$
$\displaystyle=2\left(C_{t}\left(\frac{(t-3)(1-{\rho^{2}})}{t-q-3}\right)^{\frac{1}{2}}\sigma\alpha_{t}+\lambda^{1/2}S\right)\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}$

Let $r_{t}(\text{{OFUL}})$ be the upper bound on instantaneous regret for OFUL
algorithm, i.e.,
$r_{t}(\text{{OFUL}})=2\left(\sigma\alpha_{t}+\lambda^{1/2}S\right)\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}$.
Then, we have

$\displaystyle\mathbb{E}\left[r_{t}(\text{{\ref{alg:OFUL-AF}}})\right]$
$\displaystyle\leq
2C_{t}\left(\frac{(t-3)(1-{\rho^{2}})}{t-q-3}\right)^{\frac{1}{2}}\left(\sigma\alpha_{t}+\lambda^{1/2}S\right)\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}$
$\displaystyle\qquad+2\left(1-C_{t}\left(\frac{(t-3)(1-{\rho^{2}})}{t-q-3}\right)^{\frac{1}{2}}\right)\lambda^{1/2}S\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}$
$\displaystyle\leq
C_{t}\left(\frac{(t-3)(1-{\rho^{2}})}{t-q-3}\right)^{\frac{1}{2}}r_{t}(\text{{OFUL}})$
$\displaystyle\qquad+2\left(1-C_{t}\left(\frac{(t-3)(1-{\rho^{2}})}{t-q-3}\right)^{\frac{1}{2}}\right)\lambda^{1/2}S\left\|x_{t}\right\|_{\overline{V}_{t}^{-1}}.$
$\implies\mathbb{E}\left[r_{t}(\text{{\ref{alg:OFUL-
AF}}})\right]\leq\widetilde{O}\left(\left(\frac{(t-3)(1-\rho^{2})}{t-q-3}\right)^{\frac{1}{2}}r_{t}(\text{{OFUL}})\right).\qed$

See 4

###### Proof.

Let $\mathfrak{A}$ be an AFC bandit algorithm with
$|f^{\mathfrak{A}}_{t}(x)-f(x)|\leq\sigma
h(x,\mathcal{O}_{t})+l(x,\mathcal{O}_{t})$ and $\bar{\nu}_{e,z,t}$ be the
upper bound on sample variance of hybrid reward. After $\mathfrak{A}$ uses
hybrid rewards for estimating function $f$, then, with probability at least
$1-2\delta$,

$|f^{\mathfrak{A}}_{t}(x)-f(x)|\leq\min(\sigma,(\bar{\nu}_{e,z,t})^{\frac{1}{2}})h(x,\mathcal{O}_{t})+l(x,\mathcal{O}_{t})$
(8)

The proof follows similar steps as the first part of the proof of 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 is given by
$\bar{\nu}_{e,z,t}=\frac{(t-2)\hat{\nu}_{e,z,t-1}}{\chi^{2}_{1-\delta,t}}$,
where $\hat{\nu}_{e,z,t-1}$ is an unbiased sample variance estimate of hybrid
rewards using $t-1$ observations with sampling strategy $e$ and
$\chi^{2}_{1-\delta,t}$ (implying the variance upper bound holds with at least
probability of $1-\delta$) denotes $100(1-\delta)^{\text{th}}$ percentile
value of the chi-squared distribution with $t-2$ degrees of freedom.

Let action $x_{t}$ be selected in the round $t$. Then, the instantaneous
regret is given as follows:

$\displaystyle r_{t}$
$\displaystyle=\max_{x\in\mathcal{X}}f(x)-f(x_{t})=f(x^{\star})-f(x_{t})\hskip
56.9055pt(\text{as }x^{\star}=\max_{x\in\mathcal{X}}f(x))$
$\displaystyle\leq\left|f^{\mathfrak{A}}_{t}(x^{\star})+\min(\sigma,(\bar{\nu}_{e,z,t})^{\frac{1}{2}})h(x^{\star},\mathcal{O}_{t})+l(x^{\star},\mathcal{O}_{t})-f(x_{t})\right|$
$\displaystyle\leq\left|f^{\mathfrak{A}}_{t}(x_{t})+\min(\sigma,(\bar{\nu}_{e,z,t})^{\frac{1}{2}})h(x_{t},\mathcal{O}_{t})+l(x_{t},\mathcal{O}_{t})-f(x_{t})\right|$
$\displaystyle\leq\left|f^{\mathfrak{A}}_{t}(x_{t})-f(x_{t})\right|+\min(\sigma,(\bar{\nu}_{e,z,t})^{\frac{1}{2}})h(x_{t},\mathcal{O}_{t})+l(x_{t},\mathcal{O}_{t})$
$\displaystyle\leq
2\min(\sigma,(\bar{\nu}_{e,z,t})^{\frac{1}{2}})h(x_{t},\mathcal{O}_{t})+l(x_{t},\mathcal{O}_{t}),$

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 2 except using 3 instead of 1 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 is to use contextual information to select a
better action.

We extend our results for the contextual bandits problem. In this setting, we
assume that a learner has been given an action set denoted by $\mathcal{A}$.
In round $t$, the environment generates a vector
$\left(x_{t,a},y_{t,a},\left\\{w_{t,a,i}\right\\}_{i=1}^{q}\right)$ for each
action ${a\in\mathcal{A}}$. Here, $x_{t,a}$ is the context-action
$d$-dimensional feature vector of observed context in round $t$ and action
$a$, $y_{t,a}$ is the stochastic reward received for context-action pair
$x_{t,a}$, and $w_{t,a,i}$ is the $i^{\text{th}}$ auxiliary feedback
associated with the reward $y_{t,a}$. We assume that the reward is a function
of the context-action pair $x_{t,a}$, which is given as
$y_{t,a}=f(x_{t,a})+\varepsilon_{t}$, where
$f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is an unknown function and
$\varepsilon_{t}$ is a zero-mean Gaussian noise with variance $\sigma^{2}$.
The auxiliary feedback is also assumed to be a function of the context-action
pair $x_{t,a}$, given as $W_{t,a,i}=g_{i}(x_{t,a})+\varepsilon_{t,i}^{w}$,
where $g_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R}$ and $\varepsilon_{t,i}^{w}$
is a zero-mean Gaussian noise with variance $\sigma_{w}^{2}$. The correlation
coefficient between reward and associated auxiliary feedback is denoted by
$\rho$.

We denote the optimal action for a context observed in the round $t$ as
$a_{t}^{\star}=\arg\\!\max_{a\in\mathcal{A}}f(x_{t,a})$. The interaction
between a learner and its environment is given as follows. At the beginning of
round $t$, the environment generates a context, and then the learner selects
an action $a_{t}$ from action set $\mathcal{A}$ for that context using past
information of context-actions feature vector, observed rewards and its
associated auxiliary feedback until round $t-1$. After selecting action
$a_{t}$, the learner receives a reward $(y_{t,a_{t}})$ with its associated
auxiliary feedback and incurs a penalty (or instantaneous regret) $r_{t}$,
where $r_{t}=f(x_{t,a_{t}^{\star}})-f(x_{t,a_{t}})$. 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 $\pi$ that selects action $a_{t}$ for a context observed in round $t$
is given by

$\mathfrak{R}_{T}(\pi)=\sum_{t=1}^{T}\left(f(x_{t,a_{t}^{\star}})-f(x_{t,a_{t}})\right).$
(9)

A policy $\pi$ is a good policy when it has sub-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
existing 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.

(a) Biased Estimator

(b) Estimator from historical data

(c) Influence of correlation

(d) Biased Estimator

(e) 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 of auxiliary feedback (middle figure), and regret vs.
varying correlation coefficients of reward and its auxiliary feedback (right
figure).

#### Linear bandits:

We use a $5$-dimensional space in which each sample is represented by
$x=(x_{1},\ldots,x_{5})$, where the value of $x_{j}$ is restricted in
$(-3,3)$. We randomly select a $5$-dimensional vector $\theta^{\star}$ with a
unit norm whose each value is restricted in $(0,1)$. In all linear bandits
experiments, we use $\lambda=0.01$, $L=2.236$, $S=1$, and $\delta=0.05$. In
round $t$, the reward for selected action $x_{t}$ is

$y_{t}=v_{t}+w_{t},$

where $v_{t}=x_{t}^{\top}\theta_{v}^{\star}+\varepsilon_{t}^{v}$ and
$w_{t}=x_{t}^{\top}\theta_{w}^{\star}+\varepsilon_{t}^{w}$. We set
$\theta_{v}^{\star}=(0,\theta_{2}^{\star},0,\theta_{4}^{\star},0)$ and
$\theta_{w}^{\star}=(\theta_{1}^{\star},0,\theta_{3}^{\star},0,\theta_{5}^{\star})$.
As we treat $w_{t}$ as auxiliary feedback, $\theta_{w}^{\star}$ may be assumed
to be known in some experiments. The random noise $\varepsilon_{t}^{v}$ is
zero-mean Gaussian noise with variance $\sigma_{v}^{2}$. Whereas
$\varepsilon_{t}^{w}$ is also zero-mean Gaussian noise, but the variance is
$\sigma_{w}^{2}$. We assumed that $\sigma^{2}=\sigma_{v}^{2}+\sigma_{w}^{2}$
is known, but not the $\sigma_{v}^{2}$ and $\sigma_{w}^{2}$. The default value
of $\sigma_{v}^{2}=0.01$ and $\sigma_{w}^{2}=0.01$. It can be easily shown
that the correlation coefficient of $y_{t}$ and $w_{t}$ is
$\rho=\sqrt{\sigma_{w}^{2}/(\sigma_{v}^{2}+\sigma_{w}^{2})}$. We run each
experiment for $5000$ rounds.

#### Linear contextual bandits:

We first generate a $2$-dimensional synthetic dataset with $5000$ data
samples. Each sample is represented by $x=(x_{1},x_{2})$, where the value of
$x_{j}$ is drawn uniformly at random from $(-1,1)$. Our action set
$\mathcal{A}$ has four actions:
$\\{(x_{1},x_{2}),(x_{1},-x_{2}),(-x_{1},x_{2}),(-x_{1},-x_{2})\\}$. We
uniformly generate a $\theta^{\star}$ such that its norm is $1$. In all
experiments, the data samples are treated as contexts, and we use
$\lambda=0.01$, $L=1.41$, $S=1$, and $\delta=0.05$. The observed reward for a
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 $x_{t,a}$ is given as follows:

$y_{t,a_{t}}=v_{t,a_{t}}+w_{t,a_{t}},$

where $v_{t,a_{t}}=x_{t,a}^{\top}\theta_{v}^{\star}+\varepsilon_{t}^{v}$ and
$w_{t,a_{t}}=x_{t,a}^{\top}\theta_{w}^{\star}+\varepsilon_{t}^{w}$. We set
$\theta_{v}^{\star}=(0,\theta_{2}^{\star},0,\theta_{4}^{\star})$ and
$\theta_{w}^{\star}=(\theta_{1}^{\star},0,\theta_{3}^{\star},0)$. As we treat
$w_{t,a_{t}}$ as auxiliary feedback, $\theta_{w}^{\star}$ is known for some
experiments. The random noise $\varepsilon_{t}^{v}$ is zero-mean Gaussian
noise with variance $\sigma_{v}^{2}$. Whereas $\varepsilon_{t}^{w}$ is also
zero-mean Gaussian noise, but the variance is $\sigma_{w}^{2}$. We assumed
that $\sigma^{2}=\sigma_{v}^{2}+\sigma_{w}^{2}$ is known, but not the
$\sigma_{v}^{2}$ and $\sigma_{w}^{2}$. The default value of
$\sigma_{v}^{2}=0.01$ and $\sigma_{w}^{2}=0.01$. It can be easily shown that
the correlation coefficient of $y_{t,a}$ and $w_{t,a}$ is
$\rho=\sqrt{\sigma_{w}^{2}/(\sigma_{v}^{2}+\sigma_{w}^{2})}$.

#### Non-linear contextual bandits:

This problem instance is adapted from the linear contextual bandits problem
instance. We first generate a $2$-dimensional synthetic dataset with $5000$
data samples. Each sample is represented by $x=(x_{1},x_{2})$, where the value
of $x_{j}$ is drawn uniformly at random from $(-1,1)$. We then use a
polynomial kernel with degree $2$ to have a non-linear transformation of
samples. We removed (i.e., bias) the first (i.e., $1$) and last value
$(i.e.,x_{2}^{2})$ from the transformed samples, which reduced the dimensional
of each transformed sample to $4$ and represented as
$(x_{1},x_{2},x_{1}^{2},x_{1}x_{2})$, which is used as context. For this
setting, the action set $\mathcal{A}$ has six actions:
$\\{(x_{1},x_{2},-x_{1}^{2},-x_{1}x_{2}),(x_{1},-x_{2},x_{1}^{2},-x_{1}x_{2}),(-x_{1},x_{2},x_{1}^{2},-x_{1}x_{2}),(x_{1},-x_{2},-x_{1}^{2},x_{1}x_{2}),$
$(-x_{1},x_{2},-x_{1}^{2},x_{1}x_{2}),(-x_{1},-x_{2},x_{1}^{2},x_{1}x_{2}),\\}$.
We uniformly generate a $\theta^{\star}$ such that its norm is $1$. In all
experiments, we use $\lambda=0.01$, $L=2$, $S=1$, and $\delta=0.05$. The
observed reward for a 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 $x_{t,a}$ is given as follows:

$y_{t,a_{t}}=v_{t,a_{t}}+w_{t,a_{t}},$

where $v_{t,a_{t}}=x_{t,a}^{\top}\theta_{v}^{\star}+\varepsilon_{t}^{v}$ and
$w_{t,a_{t}}=x_{t,a}^{\top}\theta_{w}^{\star}+\varepsilon_{t}^{w}$. We set
$\theta_{v}^{\star}=(0,\theta_{2}^{\star},0,\theta_{4}^{\star},0,\theta_{6}^{\star},0,\theta_{8}^{\star})$
and
$\theta_{w}^{\star}=(\theta_{1}^{\star},0,\theta_{3}^{\star},0,\theta_{5}^{\star},0,\theta_{7}^{\star},0)$.
As we treat $w_{t,a_{t}}$ as auxiliary feedback, $\theta_{w}^{\star}$ is known
for some experiments. The random noise $\varepsilon_{t}^{v}$ is zero-mean
Gaussian noise with variance $\sigma_{v}^{2}$. Whereas $\varepsilon_{t}^{w}$
is also zero-mean Gaussian noise, but the variance is $\sigma_{w}^{2}$. We
assumed that $\sigma^{2}=\sigma_{v}^{2}+\sigma_{w}^{2}$ is known, but not the
$\sigma_{v}^{2}$ and $\sigma_{w}^{2}$. The default value of
$\sigma_{v}^{2}=0.01$ and $\sigma_{w}^{2}=0.01$. It can be easily shown that
the correlation coefficient of $y_{t,a}$ and $w_{t,a}$ is
$\rho=\sqrt{\sigma_{w}^{2}/(\sigma_{v}^{2}+\sigma_{w}^{2})}$.

(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 runs.

#### Regret with varying correlation coefficient:

As the correlation coefficient of reward and auxiliary feedback is
$\rho=\sqrt{\sigma_{w}^{2}/(\sigma_{v}^{2}+\sigma_{w}^{2})}$, we varied
$\sigma_{v}$ over the values $\\{0.3,0.2,0.1528,0.1,0.0655\\}$ to obtain
problem instances with different correlation coefficient for all problem
instances.

#### Variance estimation:

Since the value of $\sigma^{2}$ is know in all our experiments, we directly
estimate the correlation coefficient ($\rho$) as
$\hat{\rho}=\text{Cov}(y,w)/(\sqrt{\mathbb{V}\left(w\right)}\sigma)$. Then,
use it to set $\bar{\nu}_{e,z,t})=(1-\hat{\rho}^{2})\sigma^{2}$.