Data-Source Adaptive Online Learning under Heteroscedastic Noise

In this paper, we address the standard $K$-armed multi-armed bandit (MAB) with heterogeneous data sources, each exhibiting unknown and distinct noise variances, $\lbrace \sigma_j^2 \rbrace_{j=1}^{M}$. The learner performs standard regret minimization, with the added challenge of choosing which data source to query at each round. We propose SOAR (Source-Optimistic Adaptive Regret minimization), a novel algorithm that adaptively balances exploration and exploitation by jointly constructing upper confidence bounds for arm rewards and lower confidence bounds for data source variances. Our theoretical analysis establishes that SOAR achieves a regret bound of $\tilde{O}\left({\sigma^\star}^2 \sum_{i=2}^K \tfrac{1}{\Delta_i}\right),$ along with a preprocessing cost that depends only on the problem parameters $\lbrace \sigma_j \rbrace_{j=1}^{M}$, $K$, and grows at most logarithmically with the horizon $T$; where ${\sigma^\star}^2$ is the minimum source variance, and $\Delta_i$ denotes the suboptimality-gap of the $i$-th arm reward. The $\tilde{O}(\cdot)$ notation hides the polylogarithmic factors in these problem parameters. Notably, despite not knowing the minimum-variance source, SOAR matches the instance-dependent regret of a standard MAB run on a single source of variance $\sigma^\star$. This near-optimal instance-dependent regret analysis of SOAR underscores its effectiveness in dynamically managing heteroscedastic noise without incurring significant overhead. Experiments on synthetic problem instances as well as a real dataset (MovieLens 32M) demonstrate that our method significantly outperforms baseline bandit algorithms in terms of regret performance. Our work opens a new direction for adaptively leveraging multiple heterogeneous data sources, extending beyond traditional bandit frameworks.