Cooperative Online Learning with Feedback Graphs
We study the interplay between communication and feedback in a cooperative online learning setting, where a network of communicating agents learn a common sequential decision-making task through a feedback graph. We bound the network regret in terms of the independence number of the strong product between the communication network and the feedback graph. Our analysis recovers as special cases many previously known bounds for cooperative online learning with expert or bandit feedback. We also prove an instance-based lower bound, demonstrating that our positive results are not improvable except in pathological cases. Experiments on synthetic data confirm our theoretical findings.
Code (1)
Tasks
Decision MakingSequential Decision MakingSimilar Papers 제목 키워드 기반
Distributed Nash Equilibrium Seeking for Noncooperative Games of High-Order Nonlinear Multi-Agent Systems Over Weight-Unbalanced Digraphs
In this paper, we investigate the noncooperative games of multi-agent systems. Different from existing noncooperative games, our formulation involves the high-order nonlinear dynamics of players, and the communication to…
Solving Nash Equilibria in Nonlinear Differential Games for Common-Pool Resources
Many resources are provided by an ecological system that is vulnerable to tipping when exceeding a certain level of pollution, with a sudden big loss of ecosystem services. An ecological system is usually also a common-p…
Online Learning with Dependent Stochastic Feedback Graphs
A general framework for online learning with partial information is one where feedback graphs specify which losses can be observed by the learner. We study a challenging scenario where feedback graphs vary stochastically…
Online Learning with Feedback Graphs: Beyond Bandits
We study a general class of online learning problems where the feedback is specified by a graph. This class includes online prediction with expert advice and the multi-armed bandit problem, but also several learning prob…
Online Learning with Feedback Graphs Without the Graphs
We study an online learning framework introduced by Mannor and Shamir (2011) in which the feedback is specified by a graph, in a setting where the graph may vary from round to round and is \emph{never fully revealed} to …