Search papers, labs, and topics across Lattice.
This paper introduces UCB-LCV, a UCB-based algorithm for stochastic multi-armed bandits that leverages limited access to control variates to improve regret. UCB-LCV effectively combines reward and control variate estimators, addressing the limitation of existing methods that assume control variates are always available. The paper also presents UCB-NORMAL, a special case of UCB-LCV for standard MABs with normally distributed rewards, and demonstrates through experiments that UCB-LCV outperforms existing bandit algorithms.
Even with intermittent access, control variates can significantly boost multi-armed bandit performance, offering a practical advantage in real-world scenarios like wireless networks.
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.
