Data-Source Adaptive Online Learning under Heteroscedastic Noise

Amith Bhat Hosadurga Anand, Haipeng Luo, Aadirupa Saha
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:2614-2649, 2026.

Abstract

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$, $M$ 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-anand26a, title = {Data-Source Adaptive Online Learning under Heteroscedastic Noise}, author = {Anand, Amith Bhat Hosadurga and Luo, Haipeng and Saha, Aadirupa}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {2614--2649}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/anand26a/anand26a.pdf}, url = {https://proceedings.mlr.press/v306/anand26a.html}, abstract = {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$, $M$ 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.} }
Endnote
%0 Conference Paper %T Data-Source Adaptive Online Learning under Heteroscedastic Noise %A Amith Bhat Hosadurga Anand %A Haipeng Luo %A Aadirupa Saha %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-anand26a %I PMLR %P 2614--2649 %U https://proceedings.mlr.press/v306/anand26a.html %V 306 %X 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$, $M$ 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.
APA
Anand, A.B.H., Luo, H. & Saha, A.. (2026). Data-Source Adaptive Online Learning under Heteroscedastic Noise. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:2614-2649 Available from https://proceedings.mlr.press/v306/anand26a.html.

Related Material