2022-06-28-atsidakou22a.md

title	booktitle	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Asymptotically-Optimal Gaussian Bandits with Side Observations	Proceedings of the 39th International Conference on Machine Learning	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 <em>a priori</em> known <em>side information</em> 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.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	atsidakou22a	0	Asymptotically-Optimal {G}aussian Bandits with Side Observations	1057	1077	1057-1077	1057	false	Atsidakou, Alexia and Papadigenopoulos, Orestis and Caramanis, Constantine and Sanghavi, Sujay and Shakkottai, Sanjay	given family Alexia Atsidakou given family Orestis Papadigenopoulos given family Constantine Caramanis given family Sujay Sanghavi given family Sanjay Shakkottai	2022-06-28		Proceedings of the 39th International Conference on Machine Learning	162	inproceedings	date-parts 2022 6 28	https://proceedings.mlr.press/v162/atsidakou22a/atsidakou22a.pdf