Abstract
Standard multi-armed bandit (MAB) algorithms often struggle with high reward variance, leading to slow convergence and high cumulative regret. This paper introduces UCB-CV, a novel algorithm that incorporates control variates—auxiliary side information correlated with rewards—to significantly reduce estimation variance. We demonstrate that when side information with a known mean is available, the cumulative regret can be reduced by a factor of $(1 - \rho^2)$, where $\rho$ is the correlation coefficient between the reward and the side information. Theoretical bounds and empirical evaluations across various distributions confirm the robustness and efficiency of the proposed approach.
Introduction
The Stochastic Multi-Armed Bandit (MAB) problem is a fundamental framework for decision-making under uncertainty, characterized by the exploration-exploitation trade-off. Traditional approaches like UCB1 use sample means to estimate arm rewards. However, in many practical applications, such as job scheduling or network routing, additional "side information" (e.g., job size or packet length) is available. This information is often highly correlated with the reward (e.g., processing time) and its long-term average is frequently known from historical data.
This paper explores how to formally integrate this exogenous side information as control variates to sharpen confidence intervals and minimize regret. Unlike contextual bandits, where side information changes the expected reward, here the side information is used as a "noise-canceling" tool to see through reward variance more quickly.
The UCB-CV Algorithm
The core of the proposed method is the UCB-CV (Upper Confidence Bound with Control Variates) algorithm. It replaces the standard sample mean with a linear control variate estimator: $$\hat{\mu}^c = \hat{\mu} + \beta(\omega - \hat{W})$$ where $\hat{\mu}$ is the sample reward mean, $\hat{W}$ is the sample mean of the side information, and $\omega$ is its known true mean.
Technical Challenges
A primary difficulty in this approach is that the optimal weight $\beta$ must be estimated from the same data used for the reward mean, introducing dependencies that invalidate standard concentration inequalities like Hoeffding's. To address this, the authors utilize t-distributions to construct valid confidence intervals for multivariate normal rewards. For non-normal distributions, the paper employs Jackknifing and Splitting techniques to reduce bias and ensure asymptotic validity.
Theoretical and Empirical Results
The theoretical analysis reveals a significant performance gain: the regret of UCB-CV scales with $O\left(\frac{\sigma^2(1-\rho^2)}{\Delta} \log T\right)$. This implies that a high correlation $\rho$ between the reward and side information directly translates to a substantial reduction in regret. For instance, a correlation of 0.9 reduces the variance-related regret by 81%.
Empirical tests on synthetic datasets (Normal, Gamma, Log-normal) show that UCB-CV consistently outperforms standard UCB1 and variance-aware variants like UCB-V. The algorithm is particularly effective in high-correlation scenarios and remains robust even when the normality assumption is relaxed through resampling methods. As shown in the figures above, the variance estimator follows the predicted logarithmic growth, which is critical for maintaining tight confidence bounds.
Discussion and Limitations
While UCB-CV offers clear advantages, it relies on the assumption that the true mean $\omega$ of the control variate is known. Significant errors in this prior knowledge can degrade performance below that of standard UCB. Future research directions include extending the framework to handle non-linear relationships between rewards and side information, as well as exploring its application in pure exploration tasks like top-m arm identification.
Summary updated