Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback

DOI10.1137/140989455zbMath1375.68097arXiv1409.8428OpenAlexW2962927562MaRDI QIDQ4596721

Yishay Mansour, Nicolò Cesa-Bianchi, Ohad Shamir, Noga Alon, Claudio Gentile, Shie Mannor

Publication date: 8 December 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1409.8428

zbMATH Keywords

graph theoryonline learningmulti-armed banditslearning from expertslearning with partial feedback

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Learning and adaptive systems in artificial intelligence (68T05) Applications of game theory (91A80) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Online algorithms; streaming algorithms (68W27)

Related Items

Best Arm Identification for Contaminated Bandits, Improved algorithms for bandit with graph feedback via regret decomposition, Unnamed Item, Unnamed Item, Small-Loss Bounds for Online Learning with Partial Information

Uses Software

• AdaBoost.MH

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The multi-armed bandit problem with covariates
• Combinatorial bandits
• On the independence number of random graphs
• On tail probabilities for martingales
• The weighted majority algorithm
• A decision-theoretic generalization of on-line learning and an application to boosting
• Arbitrary side observations in bandit problems
• Efficient algorithms for online decision problems
• Linearly Parameterized Bandits
• A Greedy Heuristic for the Set-Covering Problem
• How to use expert advice
• The Nonstochastic Multiarmed Bandit Problem
• Partial Monitoring—Classification, Regret Bounds, and Algorithms
• Bandit problems with side observations
• Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
• Prediction, Learning, and Games
• Learning Theory