Stochastic Multi-Armed Bandits with Limited Control Variates

• URL: http://arxiv.org/abs/2603.02100v1
• Date: Mon, 02 Mar 2026 17:20:46 GMT
• Title: Stochastic Multi-Armed Bandits with Limited Control Variates
• Abstract summary: We are motivated by wireless networks where interference or channel state estimates provide partial insight into throughput.<n>We study a variant of the classical multi-armed bandit problem in which the learner has limited access to auxiliary information.
• Score: 15.867573467164123
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• An LP-based Sampling Policy for Multi-Armed Bandits with Side-Observations and Stochastic Availability [40.54677625701658]
  We study the multi-armed bandit (MAB) problem where an underlying network structure enables side-observations across related actions.<n>We use a bipartite graph to link actions to a set of unknowns, such that selecting an action reveals observations for all the unknowns it is connected to.
  arXiv  Detail & Related papers  (2026-03-27T17:50:42Z)
• Learnable Chernoff Baselines for Inference-Time Alignment [64.81256817158851]
  We introduce Learnable Chernoff Baselines as a method for efficiently and approximately sampling from exponentially tilted kernels.<n>We establish total-variation guarantees to the ideal aligned model, and demonstrate in both continuous and discrete diffusion settings that LCB sampling closely matches ideal rejection sampling.
  arXiv  Detail & Related papers  (2026-02-08T00:09:40Z)
• Using causal abstractions to accelerate decision-making in complex bandit problems [4.09922517136932]
  We propose AT-UCB, an algorithm which efficiently exploits shared information between CMAB problem instances defined at different levels of abstraction.<n>We illustrate the advantages of AT-UCB theoretically, through a novel upper bound on the cumulative regret, and empirically, by applying AT-UCB to epidemiological simulators with varying resolution and computational cost.
  arXiv  Detail & Related papers  (2025-09-04T15:11:04Z)
• Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond [58.39457881271146]
  We introduce a novel framework of multi-armed bandits (CMAB) with multivariant and probabilistically triggering arms (CMAB-MT)<n>Compared with existing CMAB works, CMAB-MT not only enhances the modeling power but also allows improved results by leveraging distinct statistical properties for multivariant random variables.<n>Our framework can include many important problems as applications, such as episodic reinforcement learning (RL) and probabilistic maximum coverage for goods distribution.
  arXiv  Detail & Related papers  (2024-06-03T14:48:53Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
  arXiv  Detail & Related papers  (2023-12-19T13:17:43Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  The sequential decision-making problem is statistically learnable if it admits a low-rank structure modeled by predictive state representations (PSRs) This paper proposes the first known UCB-type approach for PSRs, featuring a novel bonus term that upper bounds the total variation distance between the estimated and true models. In contrast to existing approaches for PSRs, our UCB-type algorithms enjoy computational tractability, last-iterate guaranteed near-optimal policy, and guaranteed model accuracy.
  arXiv  Detail & Related papers  (2023-07-01T18:35:21Z)
• Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds [46.30750729936261]
  Follow-the-regularized-leader (FTRL) has recently emerged as one of the most promising approaches for obtaining various types of adaptivity in bandit problems. We establish several algorithms with three types of adaptivity: sparsity, game-dependency, and best-of-both-worlds (BOBW)
  arXiv  Detail & Related papers  (2023-05-26T23:20:48Z)
• Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
  We study the semi-bandits (CMAB) and focus on reducing the dependency of the batch-size $K$ in the regret bound. First, for the setting of CMAB with probabilistically triggered arms (CMAB-T), we propose a BCUCB-T algorithm with variance-aware confidence intervals. Second, for the setting of non-triggering CMAB with independent arms, we propose a SESCB algorithm which leverages on the non-triggering version of the TPVM condition.
  arXiv  Detail & Related papers  (2022-08-31T13:09:39Z)
• Deep Upper Confidence Bound Algorithm for Contextual Bandit Ranking of Information Selection [0.0]
  Contextual multi-armed bandits (CMAB) have been widely used for learning to filter and prioritize information according to a user's interest. In this work, we analyze top-K ranking under the CMAB framework where the top-K arms are chosen iteratively to maximize a reward. We introduce a novel algorithm called the Deep Upper Confidence Bound (UCB) algorithm.
  arXiv  Detail & Related papers  (2021-10-08T13:32:14Z)
• Tuning Confidence Bound for Stochastic Bandits with Bandit Distance [5.818764911456228]
  "Distance tuning" of the standard UCB is done using a proposed distance measure. "Exploration Bargain Point" gives insights into the tradeoffs between exploration and exploitation.
  arXiv  Detail & Related papers  (2021-10-06T12:24:07Z)
• Stochastic Multi-Armed Bandits with Control Variates [6.548580592686076]
  We study a new variant of the multi-armed bandits problem, where the learner has access to auxiliary information about the arms. The auxiliary information is correlated with the arm rewards. We develop an algorithm named UCB-CV that uses improved estimates.
  arXiv  Detail & Related papers  (2021-05-09T15:40:09Z)
• Batched Neural Bandits [107.5072688105936]
  BatchNeuralUCB combines neural networks with optimism to address the exploration-exploitation tradeoff. We prove that BatchNeuralUCB achieves the same regret as the fully sequential version while reducing the number of policy updates considerably.
  arXiv  Detail & Related papers  (2021-02-25T17:36:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.