Stochastic Multi-Armed Bandits with Control Variates

Arun Verma, Manjesh Kumar Hanawal

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%.

Figure 4: Validation of the logarithmic growth of the variance estimator $(V^{(2)})^2$ and its stability across different burn-in parameters $q$.

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

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