A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs
Contributo in Atti di convegno
Data di Pubblicazione:
2022
Citazione:
A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs / C. Rouyer, D. van der Hoeven, N. Cesa Bianchi, Y. Seldin (ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS). - In: NeurIPS / [a cura di] S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, A. Oh. - [s.l] : Curran Associates, 2022. - ISBN 9781713871088. - pp. 35035-35048 (( Intervento presentato al 36. convegno Conference on Neural Information Processing Systems : Monday November 28th through Friday December 9th tenutosi a New Orleans nel 2022.
Abstract:
We consider online learning with feedback graphs, a sequential decision-making framework where the learner's feedback is determined by a directed graph over the action set. We present a computationally efficient algorithm for learning in this framework that simultaneously achieves near-optimal regret bounds in both stochastic and adversarial environments. The bound against oblivious adversaries is Õ(√αT), where T is the time horizon and α is the independence number of the feedback graph. The bound against stochastic environments is O( (ln T)2 maxS∈I(G) ∑i∈S ∆-1i) where I (G) is the family of all independent sets in a suitably defined undirected version of the graph and ∆i are the suboptimality gaps. The algorithm combines ideas from the EXP3++ algorithm for stochastic and adversarial bandits and the EXP3.G algorithm for feedback graphs with a novel exploration scheme. The scheme, which exploits the structure of the graph to reduce exploration, is key to obtain best-of-both-worlds guarantees with feedback graphs. We also extend our algorithm and results to a setting where the feedback graphs are allowed to change over time. © 2022 Neural information processing systems foundation.
Tipologia IRIS:
03 - Contributo in volume
Elenco autori:
C. Rouyer, D. van der Hoeven, N. Cesa Bianchi, Y. Seldin
Link alla scheda completa:
Titolo del libro:
NeurIPS