Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback
Noga Alona b, Nicolò Cesa‐Bianchic, Claudio Gentiled, Shie Mannore, Yishay Mansourf, Ohad Shamirg
- aMicrosoft USA
- bTel Aviv University
- cUniversity of Milan
- d(University of Insubria
- eTECHNION-Israel Institute of Technology
- fTel-Aviv University
- gWeizmann Institute of Science
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
We introduce and study a partial-information model of online learning, where a decision maker repeatedly chooses from a finite set of actions and observes some subset of the associated losses. This setting naturally models several situations where knowing the loss of one action provides information on the loss of other actions. Moreover, it generalizes and interpolates between the well-studied full-information setting (where all losses are revealed) and the bandit setting (where only the loss of the action chosen by the player is revealed). We provide several algorithms addressing different variants of our setting and provide tight regret bounds depending on combinatorial properties of the information feedback structure.
TL;DRA partial-information model of online learning, where a decision maker repeatedly chooses from a finite set of actions, and observes some subset of the associated losses, is presented and studied. (Semantic Scholar)