cs.LGNov 9, 2026

UCB-min: Combining Bandits Under Variance Heterogeneity (Extended Version)

Authors: Lilia Izri, Benoit Groz, Silviu Maniu

Organizations: LISN, CNRS Université Paris-Saclay Orsay, France · LIG, CNRS Univ. Grenoble-Alpes, Grenoble INP Grenoble, France

Abstract

Multi-armed bandits are a natural framework for many real-world sequential decision problems, from recommender systems and clinical trials to educational test recommendation and online advertising. The performance of these algorithms depends on how they explore different arms, and exploration strategies range from variance-independent (e.g., UCB1) to variance-aware (e.g., UCB-V). In practice the reward variance of each arm is rarely known and varies widely across arms, and the reward support is often underspecified. In these cases no single rule is uniformly best: variance-independent methods are robust but loose when variances are small, while variance-aware methods are tight only when their variance estimates and the assumed support bound are reliable. Such heterogeneous, unknown variances arise in many settings, for instance when multiple objectives are scalarized into a single reward. We propose UCB-min, a per-arm adaptive meta-algorithm that selects, for each arm, the tighter of a variance-independent and a variance-aware exploration bonus, without prior knowledge of the variance regime and without reward normalization. We prove that, with UCB-V as variance-aware base, its regret is bounded by the sum of the two base bounds at the standard exploration constant, and by their per-arm minimum, up to a constant, for a larger one. We validate it on synthetic data, an educational tutoring task, and two group-recommendation benchmarks (MovieLens, Steam), showing that UCB-min consistently tracks the best base algorithm across diverse variance regimes and datasets.

Figures & tables

Explore similar work

Mar 2, 2026

Stochastic Multi-Armed Bandits with Limited Control Variates

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.
Feb 16, 2026

One Good Source is All You Need: Near-Optimal Regret for Bandits under Heterogeneous Noise

We study KK-armed Multiarmed Bandit (MAB) problem with MM heterogeneous data sources, each exhibiting unknown and distinct noise variances {σj2}j=1M\{σ_j^2\}_{j=1}^M. The learner's objective is standard MAB regret minimization, with the additional complexity of adaptively selecting which data source to query from at each round. We propose Source-Optimistic Adaptive Regret minimization (SOAR), a novel algorithm that quickly prunes high-variance sources using sharp variance-concentration bounds, followed by a `balanced min-max LCB-UCB approach' that seamlessly integrates the parallel tasks of identifying the best arm and the optimal (minimum-variance) data source. Our analysis shows SOAR achieves an instance-dependent regret bound of O~(σ∗2∑i=2Klog⁡TΔi+K∑j=1Mσj2)\tilde{O}\left({σ^*}^2\sum_{i=2}^K \frac{\log T}{Δ_i} + \sqrt{K \sum_{j=1}^M σ_j^2}\right), up to preprocessing costs depending only on problem parameters, where σ∗2:=min⁡jσj2{σ^*}^2 := \min_j σ_j^2 is the minimum source variance and ΔiΔ_i denotes the suboptimality gap of the ii-th arm. This result is both surprising as despite lacking prior knowledge of the minimum-variance source among MM alternatives, SOAR attains the optimal instance-dependent regret of standard single-source MAB with variance σ∗2{σ^*}^2, while incurring only an small (and unavoidable) additive cost of O~(K∑j=1Mσj2)\tilde O(\sqrt{K \sum_{j=1}^M σ_j^2}) towards the optimal (minimum variance) source identification. Our theoretical bounds represent a significant improvement over some proposed baselines, e.g. Uniform UCB or Explore-then-Commit UCB, which could potentially suffer regret scaling with σmax⁡2σ_{\max}^2 in place of σ∗2{σ^*}^2-a gap that can be arbitrarily large when σmax⁡≫σ∗σ_{\max} \gg σ^*. Experiments on multiple synthetic problem instances and the real-world MovieLens;25M dataset, demonstrating the superior performance of SOAR over the baselines.
Oct 19, 2026

Variance-Aware Non-Stationary Bandits:All-Budget Regret Bounds and Adaptation Costs

Low reward variance reduces estimation cost, but does not eliminate monitoring of arms that may improve while unobserved. We refine the variance--variation tradeoff and characterize how both costs depend on supplied variance and variation budgets in bounded, non-stationary multi-armed bandits. Let AA be the number of arms, TT the horizon, BB a bound on consecutive mean variation excluding the initial vector, and QQ a bound on the sum of the largest per-round reward variances. For every admissible pair Q,BQ,B, the minimax expected dynamic regret is, within a single logarithmic factor, min⁡{T,  A+AQ+(AQBT)1/3+ATmin⁡{B,B}}.\min\{T,\;A+\sqrt{AQ}+(AQBT)^{1/3} +\sqrt{AT}\min\{B,\sqrt B\}\}. The deterministic boundary Q=0Q=0 is characterized without logarithms. For small positive budgets, a safe calibration phase identifies a common interval containing all future means of surviving arms. Clipping observations to a wider interval reduces the cost of restarting a prior hybrid static-regret algorithm; an original-mean analytical reference controls its residuals without charging the variation of clipped means. Balancing clipping bias and monitoring closes the small-budget noisy regime. Fixed oblivious constructions give the matching lower bound. We also quantify adaptation costs: on a disclosed deterministic one-improvement family, a stationary-regret budget has a matching worst-case change-regret frontier, including a finite improvement pulse. This implies an Ω((T/A)1/4)Ω((T/A)^{1/4}) loss when one policy competes with all supplied-budget deterministic oracle rates. The budget-free low-noise scheduling problem remains separate.