Timezone: »

 
Spotlight
Asymptotically-Optimal Gaussian Bandits with Side Observations
Alexia Atsidakou · Orestis Papadigenopoulos · Constantine Caramanis · Sujay Sanghavi · Sanjay Shakkottai

Thu Jul 21 01:35 PM -- 01:40 PM (PDT) @ Ballroom 3 & 4
in T: Online Learning and Bandits »

We study the problem of Gaussian bandits with general side information, as first introduced by Wu, Szepesv\'{a}ri, and Gy\"{o}rgy. In this setting, the play of an arm reveals information about other arms, according to an arbitrary {\em a priori} known {\em side information} matrix: each element of this matrix encodes the fidelity of the information that the row" arm reveals about thecolumn" 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.

Keywords: T: Online Learning and Bandits · MISC: Online Learning, Active Learning and Bandits

Author Information

Alexia Atsidakou (University of Texas at Austin)
Orestis Papadigenopoulos (The University of Texas at Austin)
Constantine Caramanis (University of Texas)
Sujay Sanghavi (UT Austin)
Sanjay Shakkottai (University of Texas at Austin)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors