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

arXiv: https://arxiv.org/abs/2602.14474 · HTML: https://mlsanity.com/paper/2602.14474/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 24 references that are in the map.
- First posted on arXiv 16 Feb 2026.

## Builds on (most cited first, 3 of 3)

- [Multi-Information Source Optimization](https://mlsanity.com/paper/1603.00389/) (2016)
- [A General Framework for Multi-fidelity Bayesian Optimization with Gaussian Processes](https://mlsanity.com/paper/1811.00755/) (2018)
- [The Multi-fidelity Multi-armed Bandit](https://mlsanity.com/paper/1610.09726/) (2016)

## Built on by (most cited first, 1 of 1)

- [Bandits for Efficient Experimentation: Adapting to Control Group, Preferences, and Context Drifts](https://mlsanity.com/paper/2606.09802/) (2026)

## Abstract (arXiv)

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.