2022/06/01 by Rouyer, Chloé, van der Hoeven, Dirk, Cesa-Bianchi, Nicolò +1 · 1 citation
#FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.2206.00557
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 O (√(α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∈ \mathcal I(G) ∑i ∈ S Δi-1) where \mathcal 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.