Federated Bandit: A Gossiping Approach
Abstract
We study Federated Bandit, a decentralized Multi-Armed Bandit (MAB) problem with a set of N agents, who can only communicate their local data with neighbors described by a connected graph G. Each agent makes a sequence of decisions on selecting an arm from M candidates, yet they only have access to local and potentially biased feedback/evaluation of the true reward for each action taken. Learning only locally will lead agents to sub-optimal actions while converging to a no-regret strategy requires a collection of distributed data. Motivated by the proposal of federated learning, we aim for a solution with which agents will never share their local observations with a central entity, and will be allowed to only share a private copy of his/her own information with their neighbors. We first propose a decentralized bandit algorithm GossipUCB, which is a coupling of variants of both the classical gossiping algorithm and the celebrated Upper Confidence Bound (UCB) bandit algorithm. We show that GossipUCB successfully adapts local bandit learning into a global gossiping process for sharing information among connected agents, and achieves guaranteed regret at the order of O(max(poly(N,M) log T, poly(N,M) logλ2-1 N)) for all N agents, where λ2∈(0,1) is the second largest eigenvalue of the expected gossip matrix, which is a function of G. We then propose FedUCB, a differentially private version of GossipUCB, in which the agents preserve ε-differential privacy of their local data while achieving O(max poly(N,M)/ε log2.5 T, poly(N,M) (logλ2-1 N + log T)) regret.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 22, 2021
- Source ID
- 10.1145/3543516.3453919
Entities
People
- Ji Liu
- Jingxuan Zhu
- Yang Liu
- Zhaowei Zhu
Organizations
- National Science Foundation
- Office of Naval Research
- Stony Brook University
- University of California, Santa Cruz