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

CardsList
  1. Stochastic Multi-Armed Bandits with Limited Control Variates

    Mar 2, 2026Arun Verma, Manjesh Kumar Hanawal, Arun RajkumarMulti-Armed BanditsUCB Algorithms

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

    Oct 19, 2026Xiaojin ZhangMulti-Armed BanditsNon-Stationary Bandits