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.

Many systems must repeatedly choose the best option, which treatment to give a patient, which movie to recommend, while learning from feedback as they go. Increasingly, that feedback is gathered from crowds: on a platform like Amazon Mechanical Turk, many workers can rate or label items, but they differ widely in reliability, with some careful and consistent and others careless and inconsistent. The difficulty is that you don't know in advance which sources to trust, and relying on unreliable ones wastes time and effort. We developed SOAR, a method that learns on the fly which sources, for example, which crowd workers are reliable, while simultaneously figuring out which option is best. It quickly sets aside the least reliable sources and steadily concentrates its questions on the trustworthy ones, pursuing both goals together: identifying reliable sources and finding the best option, rather than tackling one after the other. Surprisingly, SOAR performs almost as well as a system that had been told the single most reliable source from the start, even though it must discover this on its own, paying only a small, inevitable price for not knowing in advance. This enables faster, cheaper learning wherever feedback comes from sources of unknown and varying quality a challenge that spans clinical trials run across hospitals of differing expertise, crowdsourced data labeling, and movie or product recommendations, among many other settings.