Asymptotically-Optimal Gaussian Bandits with Side Observations
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913841430921216 |
|---|---|
| author | Atsidakou, Alexia Papadigenopoulos, Orestis Caramanis, Constantine Sanghavi, Sujay Shakkottai, Sanjay |
| author_facet | Atsidakou, Alexia Papadigenopoulos, Orestis Caramanis, Constantine Sanghavi, Sujay Shakkottai, Sanjay |
| contents | We study the problem of Gaussian bandits with general side information, as first introduced by Wu, Szepesvari, and Gyorgy. In this setting, the play of an arm reveals information about other arms, according to an arbitrary a priori known side information matrix: each element of this matrix encodes the fidelity of the information that the ``row'' arm reveals about the ``column'' arm. In the case of Gaussian noise, this model subsumes standard bandits, full-feedback, and graph-structured feedback as special cases. In this work, we first construct an LP-based asymptotic instance-dependent lower bound on the regret. The LP optimizes the cost (regret) required to reliably estimate the suboptimality gap of each arm. This LP lower bound motivates our main contribution: the first known asymptotically optimal algorithm for this general setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_10698 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Asymptotically-Optimal Gaussian Bandits with Side Observations Atsidakou, Alexia Papadigenopoulos, Orestis Caramanis, Constantine Sanghavi, Sujay Shakkottai, Sanjay Machine Learning We study the problem of Gaussian bandits with general side information, as first introduced by Wu, Szepesvari, and Gyorgy. In this setting, the play of an arm reveals information about other arms, according to an arbitrary a priori known side information matrix: each element of this matrix encodes the fidelity of the information that the ``row'' arm reveals about the ``column'' arm. In the case of Gaussian noise, this model subsumes standard bandits, full-feedback, and graph-structured feedback as special cases. In this work, we first construct an LP-based asymptotic instance-dependent lower bound on the regret. The LP optimizes the cost (regret) required to reliably estimate the suboptimality gap of each arm. This LP lower bound motivates our main contribution: the first known asymptotically optimal algorithm for this general setting. |
| title | Asymptotically-Optimal Gaussian Bandits with Side Observations |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2505.10698 |