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 naturally models several situations where the losses of different actions are related, and 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.
Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback / N. Alon, N. Cesa Bianchi, C. Gentile, S. Mannor, Y. Mansour, O. Shamir. - In: SIAM JOURNAL ON COMPUTING. - ISSN 0097-5397. - 46:6(2017), pp. 1785-1826.
Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback
N. Cesa BianchiSecondo
;
2017
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 naturally models several situations where the losses of different actions are related, and 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.File | Dimensione | Formato | |
---|---|---|---|
140989455.pdf
accesso aperto
Tipologia:
Publisher's version/PDF
Dimensione
405.22 kB
Formato
Adobe PDF
|
405.22 kB | Adobe PDF | Visualizza/Apri |
1409.8428.pdf
accesso aperto
Tipologia:
Pre-print (manoscritto inviato all'editore)
Dimensione
635.16 kB
Formato
Adobe PDF
|
635.16 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.