@article{fcb9a15a26b245faae783e19aa8b51f7,
title = "Nonstochastic multi-armed bandits with graph-structured feedback",
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.",
keywords = "Graph theory, Learning from experts, Learning with partial feedback, Multi-armed bandits, Online learning",
author = "Noga Alon and Nicolo Cesa-Bianchi and Claudio Gentile and Shie Mannor and Yishay Mansour and Ohad Shamir",
note = "Funding Information: ∗Received by the editors September 29, 2014; accepted for publication (in revised form) September 14, 2017; published electronically November 28, 2017. Preliminary versions of this manuscript appeared in [3, 37]. http://www.siam.org/journals/sicomp/46-6/98945.html Funding: The first author was supported in part by a USA-Israeli BSF grant, by an ISF grant, by the Israeli I-Core program, and by the Oswald Veblen Fund. The second author was supported in part by MIUR (project ARS TechnoMedia, PRIN 2010-2011, grant 2010N5K7EB 003). The fourth author was supported in part by the European Community{\textquoteright}s Seventh Framework Programme (FP7/2007-2013) under grant agreement 306638 (SUPREL). The fifth author was supported in part by a grant from the Israel Science Foundation, a grant from the United States-Israel Binational Science Foundation (BSF), a grant by Israel Ministry of Science and Technology, and the Israeli Centers for Research Excellence (I-CORE) program (Center 4/11). The sixth author was supported in part by a grant from the Israel Science Foundation (425/13) and a Marie-Curie Career Integration Grant. Publisher Copyright: {\textcopyright} 2017 the authors.",
year = "2017",
doi = "10.1137/140989455",
language = "English (US)",
volume = "46",
pages = "1785--1826",
journal = "SIAM Journal on Computing",
issn = "0097-5397",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "6",
}