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

arXiv:2602.14474v2 Announce Type: replace Abstract: We study K-armed Multiarmed Bandit (MAB) problem with M heterogeneous data sources, each exhibiting unknown and distinct noise variances {sigma_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 ilde{O}left({sigma^*}^2sum{i=2}^K frac{log T}{Delta_i} + sqrt{K sum_{j=1}^M sigma_j^2}right), up to preprocessing costs depending only on problem parameters, where {sigma^}^2 := min_j sigma_j^2 is the minimum source variance and Delta_i 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 {sigma^}^2, while incurring only an small (and unavoidable) additive cost of ilde O(sqrt{K sum_{j=1}^M sigma_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 sigma_{max}^2 in place of {sigma^}^2-a gap that can be arbitrarily large when sigma_{max} gg sigma^. Experiments on multiple synthetic problem instances and the real-world MovieLens;25M dataset, demonstrating the superior performance of SOAR over the baselines.

Source: arXiv cs.LG | 2026-05-04