Doubly Adversarial Federated Bandits
Jul 24, 2023
Speakers
Milan Vojnovic
Speaker · 0 followers
About
We study a new non-stochastic federated multiarmed bandit problem with multiple agents collaborating via a communication network. The losses of the arms are assigned by an oblivious adversary that specifies the loss of each arm not only for each time step but also for each agent, which we call “doubly adversarial”. In this setting, different agents may choose the same arm in the same time step but observe different feedback. The goal of each agent is to find a globally best arm in hindsight that has the lowest cumulative loss averaged over all agents, which necessities the communication among agents. We provide regret lower bounds for any federated bandit algorithm under different settings, when agents have access to full-information feedback, or the bandit feedback. For the bandit feedback setting, we propose a near-optimal federated bandit algorithm called FEDEXP3. Our algorithm gives a positive answer to an open question proposed in (Cesa-Bianchi et al., 2016): FEDEXP3 can guarantee a sub-linear regret without exchanging sequences of selected arm identities or loss sequences among agents. We also provide numerical evaluations of our algorithm to validate our theoretical results and demonstrate its effectiveness on synthetic and real-world datasets.We study a new non-stochastic federated multiarmed bandit problem with multiple agents collaborating via a communication network. The losses of the arms are assigned by an oblivious adversary that specifies the loss of each arm not only for each time step but also for each agent, which we call “doubly adversarial”. In this setting, different agents may choose the same arm in the same time step but observe different feedback. The goal of each agent is to find a globally best arm in hindsight that…
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Which Invariance Should We Transfer? A Causal Minimax Approach
Watch later
Mingzhou Liu, …
mPLUG-2: A Modularized Multi-modal Foundation Model Across Text, Image and Video
Watch later
Haiyang Xu, …
Feature Expansion for Graph Neural Networks
Watch later
Jiaqi Sun, …
Fast Combinatorial Algorithms for Min Max Correlation Clustering
Watch later
Sami Davies, …
Learning to Learn from APIs: Black-box Data-free Meta-Learning
Watch later
Zixuan Hu, …