Asymptotically-Optimal Gaussian Bandits with Side Observations

Alexia Atsidakou, Orestis Papadigenopoulos, Constantine Caramanis, Sujay Sanghavi, Sanjay Shakkottai
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:1057-1077, 2022.

Abstract

We study the problem of Gaussian bandits with general side information, as first introduced by Wu, Szepesvári, and György. 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-atsidakou22a, title = {Asymptotically-Optimal {G}aussian Bandits with Side Observations}, author = {Atsidakou, Alexia and Papadigenopoulos, Orestis and Caramanis, Constantine and Sanghavi, Sujay and Shakkottai, Sanjay}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {1057--1077}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/atsidakou22a/atsidakou22a.pdf}, url = {https://proceedings.mlr.press/v162/atsidakou22a.html}, abstract = {We study the problem of Gaussian bandits with general side information, as first introduced by Wu, Szepesvári, and György. 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.} }
Endnote
%0 Conference Paper %T Asymptotically-Optimal Gaussian Bandits with Side Observations %A Alexia Atsidakou %A Orestis Papadigenopoulos %A Constantine Caramanis %A Sujay Sanghavi %A Sanjay Shakkottai %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-atsidakou22a %I PMLR %P 1057--1077 %U https://proceedings.mlr.press/v162/atsidakou22a.html %V 162 %X We study the problem of Gaussian bandits with general side information, as first introduced by Wu, Szepesvári, and György. 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.
APA
Atsidakou, A., Papadigenopoulos, O., Caramanis, C., Sanghavi, S. & Shakkottai, S.. (2022). Asymptotically-Optimal Gaussian Bandits with Side Observations. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:1057-1077 Available from https://proceedings.mlr.press/v162/atsidakou22a.html.

Related Material