Exploiting Correlated Auxiliary Feedback in Parameterized Bandits

Arun Verma, Zhongxiang Dai, Yao Shu, Bryan Kian Hsiang Low

Introduction

In the realm of multi-armed bandits, a learner sequentially chooses actions to maximize a cumulative reward. In "parameterized" bandits, where the action space is massive or infinite, algorithms typically assume the reward follows a parameterized function (such as a linear model). The primary bottleneck for these algorithms is uncertainty: the learner requires numerous samples to build tight "confidence bounds" around its reward estimates.

Standard algorithms rely solely on the observed reward to update their estimates. However, in many real-world applications, additional information becomes available after an action is taken. For instance, a food delivery platform recommending a restaurant observes the user's rating (the primary reward) but also records the delivery time (auxiliary feedback). Because delivery time often influences user ratings, these two metrics are correlated.

This paper introduces a novel approach to accelerate learning in bandit problems by leveraging this "auxiliary feedback." By treating these extra, correlated data points as control variates, the authors develop a method to significantly reduce variance, leading to tighter confidence bounds and lower regret (faster learning).

Methods

The core innovation of this paper lies in adapting Control Variate theory to the sequential bandit setting.

1. Hybrid Rewards

Instead of relying exclusively on the observed reward $y$, the authors propose constructing a "hybrid reward" $z$. This estimator subtracts the expected "error" in the auxiliary feedback from the observed reward. For example, if the auxiliary feedback is higher than its expected mean and is known to be positively correlated with the reward, the algorithm adjusts its reward estimate downward to correct for the variance.

Modified bandit loop incorporating auxiliary feedback to compute a hybrid reward.

2. Auxiliary Feedback Compatible (AFC) Algorithms

The authors adapt the classic OFUL (Optimism in the Face of Uncertainty Linear bandit) algorithm to utilize these hybrid rewards, creating OFUL-AF. More broadly, they define a class of algorithms called Auxiliary Feedback Compatible (AFC) that can seamlessly integrate this hybrid reward structure.

3. Handling Unknown Functions

In practice, the exact function governing the auxiliary feedback is rarely known in advance. The authors extend their method to estimate these functions on the fly using two distinct sampling strategies:

  • Independent Samples (IS): Allocating separate, independent data points to estimate different auxiliary functions.
  • Multi-Fidelity (MF): Utilizing a nested structure where samples gathered for one function are reused to help estimate another, improving sample efficiency.

4. Online Variance Estimation

Because the exact correlation between the reward and the auxiliary feedback is typically unknown, the algorithm incorporates a mechanism to estimate this correlation—and the resulting variance reduction—dynamically as it collects data.

Key Insights and Ideas

  • Auxiliary Feedback as Variance Reduction: The critical insight is that auxiliary feedback is not just additional feature data to regress on; it acts as a variance reduction tool to filter out noise in the primary reward signal.
  • The Power of Correlation: The theoretical advantage is directly tied to the correlation coefficient, $\rho$. The authors prove that regret is reduced by a factor proportional to $\sqrt{1-\rho^2}$. If the feedback is perfectly correlated ($\rho=1$), the variance—and consequently the regret—drops to zero.
  • Plug-and-Play Compatibility: The AFC framework is highly versatile. It is not a single algorithm but a structural wrapper that can be applied to many existing bandit strategies, such as Lin-UCB, GLM-UCB, or IGP-UCB.
Table of Auxiliary Feedback Compatible (AFC) bandit algorithms.
  • Robustness to Bias: Even if the auxiliary feedback estimates are slightly biased or constructed from a very small number of historical samples, the hybrid approach consistently outperforms standard methods that ignore the extra data.

Experimental Results

The authors evaluated their approach across several synthetic environments, including Linear Bandits, Linear Contextual Bandits, and Non-linear Contextual Bandits (using a polynomial kernel).

  • Regret Reduction: Both theoretically and empirically, the proposed OFUL-AF achieves significantly lower regret than the standard OFUL baseline.
  • Efficiency Gain: In simulations, the hybrid approach reached optimal regret levels much earlier in the training process, requiring fewer rounds to converge.
  • Correlation Sensitivity: As expected from the theory, experiments confirmed that higher correlation $\rho$ between the reward and auxiliary feedback yields a more pronounced performance gain.
  • Sample Efficiency: The algorithm demonstrated a clear advantage over baselines even when initialized with as few as 5 to 10 historical samples to estimate the auxiliary function.

Limitations and Future Work

While promising, the current framework has a few theoretical limitations:

  • Gaussian Assumption: The regret bounds and proofs currently rely on the assumption that the noise is zero-mean Gaussian. Real-world noise can often be skewed or heavy-tailed.
  • Homoscedasticity: The model assumes the noise variance is constant across all actions. In reality, heteroscedastic noise is common, where certain actions or contexts are inherently more unpredictable than others.

Future directions proposed by the authors include extending the AFC framework to handle non-Gaussian and heteroscedastic noise, as well as exploring more complex, non-linear relationships between primary rewards and auxiliary signals.

Summary updated

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.
BibTeX
@inproceedings{verma2023exploiting,
  author = {Arun Verma and Zhongxiang Dai and Yao Shu and Bryan Kian Hsiang Low},
  title = {{Exploiting Correlated Auxiliary Feedback in Parameterized Bandits}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=vM5VnNQ4n7},
}
Figure