Doubly Adversarial Federated Bandits

2023-01-22 · Jialin Yi, Milan Vojnović

We study a new non-stochastic federated multi-armed 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

📄 PDF Abstract BibTeX arXiv:2301.09223

Code (0)

등록된 구현이 없습니다.

Tasks

Open-Ended Question Answering

Bias-Robust Bayesian Optimization via Dueling Bandits

2021-05-25 · Johannes Kirschner, Andreas Krause

We consider Bayesian optimization in settings where observations can be adversarially biased, for example by an uncontrolled hidden confounder. Our first contribution is a reduction of the confounded setting to the dueli…

Bayesian Optimization

Federated Linear Bandits with Finite Adversarial Actions

2023-11-02 · NeurIPS 2023 11

We study a federated linear bandits model, where $M$ clients communicate with a central server to solve a linear contextual bandits problem with finite adversarial action sets that may be different across clients. To add…

Multi-Armed Bandits

Federated Linear Contextual Bandits with User-level Differential Privacy

2023-06-08 · Ruiquan Huang, Huanyu Zhang, Luca Melis, Milan Shen 외

This paper studies federated linear contextual bandits under the notion of user-level differential privacy (DP). We first introduce a unified federated bandits framework that can accommodate various definitions of DP in …

Decision Making Multi-Armed Bandits Sequential Decision Making

Federated Doubly Stochastic Kernel Learning for Vertically Partitioned Data

2020-08-14 · Bin Gu, Zhiyuan Dang, Xiang Li, Heng Huang

In a lot of real-world data mining and machine learning applications, data are provided by multiple providers and each maintains private records of different feature sets about common entities. It is challenging to train…

BIG-bench Machine Learning Federated Learning

More Robust Doubly Robust Off-policy Evaluation

2018-02-10 · ICML 2018 7 · Mehrdad Farajtabar, Yin-Lam Chow, Mohammad Ghavamzadeh

We study the problem of off-policy evaluation (OPE) in reinforcement learning (RL), where the goal is to estimate the performance of a policy from the data generated by another policy(ies). In particular, we focus on the…

Multi-Armed Bandits Off-policy evaluation Reinforcement Learning Reinforcement Learning (RL)