Stochastic Multi-Armed Bandits with Control Variates

Arun Verma, Manjesh Kumar Hanawal

Introduction

In the classic Stochastic Multi-Armed Bandit (MAB) problem, a learner attempts to maximize cumulative rewards by sequentially choosing between different "arms" with unknown reward distributions. The speed at which a learner identifies the optimal arm depends heavily on the "tightness" of the confidence bounds around its reward estimates. High variance in rewards leads to wide confidence intervals, forcing the learner to spend excessive time exploring sub-optimal arms.

This paper introduces UCB-CV (Upper Confidence Bound with Control Variates), a novel multi-armed bandit algorithm that utilizes "control variates"—auxiliary variables with known means—to drastically reduce the variance of reward estimates. In many real-world scenarios, we have access to side information correlated with the reward. For instance, in a job-scheduling platform, the time required to complete a task (the cost/reward) is highly correlated with the size of the job (the side information). While the average service time is unknown, the average job size might be known from historical data. By leveraging the correlation between rewards and these side variables, UCB-CV can significantly accelerate learning in environments like wireless networks and job scheduling.

The UCB-CV Algorithm

The core technical challenge in integrating control variates is that standard bandit tools, such as Hoeffding’s inequality, assume samples are independent. However, using control variates to adjust a reward estimate requires estimating the "weight" of that correlation from the data, which inherently makes subsequent samples dependent on each other.

To overcome this, the authors employ several key techniques:

  1. Linear Control Variates: They construct a new reward estimator that adjusts the observed reward based on the deviation of the control variate from its known mean.
  2. Regression-based Confidence Bounds: For normally distributed rewards, the authors pivot away from standard concentration inequalities. Instead, they utilize t-distribution theory to derive unbiased variance estimators and tight confidence bounds that account for the broken independence assumption.
  3. Resampling for General Distributions: Recognizing that real-world rewards are rarely perfectly Gaussian, they adapt UCB-CV using statistical resampling techniques—specifically Jackknifing and Splitting. These methods help reduce bias and provide valid confidence intervals for heavy-tailed or non-normal data.

Theoretical Insights & Trade-offs

The theoretical analysis of UCB-CV yields several compelling insights into the mechanics of variance reduction in bandit problems:

  • The $(1 - \rho^2)$ Advantage: The most significant finding is that the regret of UCB-CV is scaled by a factor of $(1 - \rho^2)$, where $\rho$ is the correlation coefficient. If the side information is 90% correlated with the reward ($\rho = 0.9$), the variance—and effectively the regret—drops by 81%.
  • More Isn't Always Better: Adding more control variates (increasing $q$) increases the "degrees of freedom" required for the t-distribution. This creates a fundamental trade-off: while more control variates might reduce the underlying variance, they can make the confidence bounds wider initially because the estimator itself is more complex.
Variance bounds scaling with time T and number of control variates q.
  • Robustness to Error: The algorithm remains advantageous even if the "known" mean of the control variate is slightly inaccurate (approximation error $\epsilon$), provided the error stays within a reasonable limit.

Empirical Performance

The authors evaluated UCB-CV on several synthetically generated problem instances designed to test specific conditions, including multivariate normal distributions, Gamma distributions (skewed data), and Log-normal distributions (heavy-tailed data).

  • Regret Reduction & Faster Convergence: In experiments, UCB-CV consistently outperformed state-of-the-art algorithms like UCB1, UCB-V, and EUCBV. Because the confidence intervals shrink faster due to lower variance, UCB-CV identifies the optimal arm much earlier.
  • Correlation Sensitivity: Quantitative tests confirmed the theoretical prediction: as the correlation $\rho$ increases, the regret decreases linearly following the $(1 - \rho^2)$ curve.
  • Resampling Success: For non-normal distributions, the Jackknifing and Splitting variants of UCB-CV remained robust, successfully outperforming standard methods without relying on Gaussian assumptions.

Limitations and Future Directions

While UCB-CV presents a significant step forward, the primary theoretical results assume the mean of the control variate is known exactly. A full theoretical framework for estimated control variate means in bandits remains an open area. Additionally, resampling methods like Jackknifing introduce computational overhead compared to simple UCB indices, which could be a bottleneck in high-frequency real-time systems. Future work may also explore how control variates can accelerate "Best Arm Identification" or ranking problems, moving beyond cumulative regret minimization.

Summary updated

Abstract

This paper studies a new variant of the stochastic multi-armed bandits problem where auxiliary information about the arm rewards is available in the form of control variates. In many applications like queuing and wireless networks, the arm rewards are functions of some exogenous variables. The mean values of these variables are known a priori from historical data and can be used as control variates. Leveraging the theory of control variates, we obtain mean estimates with smaller variance and tighter confidence bounds. We develop an upper confidence bound based algorithm named UCB-CV and characterize the regret bounds in terms of the correlation between rewards and control variates when they follow a multivariate normal distribution. We also extend UCB-CV to other distributions using resampling methods like Jackknifing and Splitting. Experiments on synthetic problem instances validate performance guarantees of the proposed algorithms.
BibTeX
@inproceedings{verma2021stochastic,
  author = {Arun Verma and Manjesh Kumar Hanawal},
  title = {{Stochastic Multi-Armed Bandits with Control Variates}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=jHAAHg8T7Nx},
}
Figure