Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback
Authors:
- Noga AlonNANoga Alon
- Nicolò Cesa-BianchiNCNicolò Cesa-Bianchi
- Claudio GentileCGClaudio Gentile
- Shie MannorSMShie Mannor
- Yishay MansourYMYishay Mansour
- Ohad ShamirOSOhad Shamir
- 1 January 2017
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 46 (6) , 1785-1826
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...Keywords
All Related Versions
Funding Information
- USA-Israeli BSF Grant
- Oswald Veblen Fund
- Israel Ministry of Science and Technology
- Marie-Curie Career Integration Grant
- Israeli Centers for Research Excellence
- Seventh Framework Programme (306638)
- Israel Science Foundation (425/13)
- Instituto Nazionale di Fisica Nucleare (2010N5K7EB_003)
- United States - Israel Binational Science Foundation
This publication has 18 references indexed in Scilit:
- Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit ProblemsFoundations and Trends in Machine Learning, 2012
- Combinatorial banditsJournal of Computer and System Sciences, 2012
- Linearly Parameterized BanditsMathematics of Operations Research, 2010
- Arbitrary side observations in bandit problemsAdvances in Applied Mathematics, 2005
- The Nonstochastic Multiarmed Bandit ProblemSIAM Journal on Computing, 2002
- A Decision-Theoretic Generalization of On-Line Learning and an Application to BoostingJournal of Computer and System Sciences, 1997
- How to use expert adviceJournal of the ACM, 1997
- The Weighted Majority AlgorithmInformation and Computation, 1994
- On the independence number of random graphsDiscrete Mathematics, 1990
- On Tail Probabilities for MartingalesThe Annals of Probability, 1975