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

We study K-armed Multiarmed Bandit (MAB) problem with M heterogeneous data sources, each exhibiting unknown and distinct noise variances σj2j=1M. 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 tildeOleft(σ^*2sumi=2K fraclog TDeltai + √K sumj=1M σj2right), up to preprocessing costs depending only on problem parameters, where σ^*2 := minj σj2 is the minimum source variance and Deltai denotes the suboptimality gap of the i-th arm. This result is both surprising as despite lacking prior knowledge of the minimum-variance source among M alternatives, SOAR attains the optimal instance-dependent regret of standard single-source MAB with variance σ^*2, while incurring only an small (and unavoidable) additive cost of tilde O(√K sumj=1M σj2) 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 σmax2 in place of σ^*2-a gap that can be arbitrarily large when σmax gg σ^*. Experiments on multiple synthetic problem instances and the real-world MovieLens;25M dataset, demonstrating the superior performance of SOAR over the baselines.