# Stochastic Multi-Armed Bandits with Limited Control Variates

arXiv: https://arxiv.org/abs/2603.02100 · HTML: https://mlsanity.com/paper/2603.02100/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 37 references that are in the map.
- First posted on arXiv 2 Mar 2026.

## Builds on (most cited first, 10 of 10)

- [Scalable Generalized Linear Bandits: Online Computation and Hashing](https://mlsanity.com/paper/1706.00136/) (2017)
- [Prompt Optimization with Human Feedback](https://mlsanity.com/paper/2405.17346/) (2024)
- [Bandit Structured Prediction for Neural Sequence-to-Sequence Learning](https://mlsanity.com/paper/1704.06497/) (2017)
- [Online Stochastic Linear Optimization under One-bit Feedback](https://mlsanity.com/paper/1509.07728/) (2015)
- [Efficient-UCBV: An Almost Optimal Algorithm using Variance Estimates](https://mlsanity.com/paper/1711.03591/) (2017)
- [ActiveDPO: Active Direct Preference Optimization for Sample-Efficient Alignment](https://mlsanity.com/paper/2505.19241/) (2025)
- [Stochastic Multi-Armed Bandits with Control Variates](https://mlsanity.com/paper/2105.03962/) (2021)
- [Exploiting Correlated Auxiliary Feedback in Parameterized Bandits](https://mlsanity.com/paper/2311.02715/) (2023)
- [Scalable Discrete Sampling as a Multi-Armed Bandit Problem](https://mlsanity.com/paper/1506.09039/) (2015)
- [Active Human Feedback Collection via Neural Contextual Dueling Bandits](https://mlsanity.com/paper/2504.12016/) (2025)

## Abstract (arXiv)

Motivated by wireless networks where interference or channel state estimates provide partial insight into throughput, we study a variant of the classical stochastic multi-armed bandit problem in which the learner has limited access to auxiliary information. Recent work has shown that such auxiliary information, when available as control variates, can be used to get tighter confidence bounds, leading to lower regret. However, existing works assume that control variates are available in every round, which may not be realistic in several real-life scenarios. To address this, we propose UCB-LCV, an upper confidence bound (UCB) based algorithm that effectively combines the estimators obtained from rewards and control variates. When there is no control variate, UCB-LCV leads to a novel algorithm that we call UCB-NORMAL, outperforming its existing algorithms for the standard MAB setting with normally distributed rewards. Finally, we discuss variants of the proposed UCB-LCV that apply to general distributions and experimentally demonstrate that UCB-LCV outperforms existing bandit algorithms.