Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Users

• URL: http://arxiv.org/abs/2402.16312v1
• Date: Mon, 26 Feb 2024 05:31:14 GMT
• Title: Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Users
• Authors: Hantao Yang, Xutong Liu, Zhiyong Wang, Hong Xie, John C. S. Lui, Defu Lian, Enhong Chen
• Abstract summary: We propose a UCB-type algorithm with delicate communication protocols. We give sub-linear regret bounds on par with those achieved in the synchronous framework. Empirical evaluation on synthetic and real-world datasets validates our algorithm's superior performance in terms of regrets and communication costs.
• Score: 95.77678166036561
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of federated contextual combinatorial cascading bandits, where $|\mathcal{U}|$ agents collaborate under the coordination of a central server to provide tailored recommendations to the $|\mathcal{U}|$ corresponding users. Existing works consider either a synchronous framework, necessitating full agent participation and global synchronization, or assume user homogeneity with identical behaviors. We overcome these limitations by considering (1) federated agents operating in an asynchronous communication paradigm, where no mandatory synchronization is required and all agents communicate independently with the server, (2) heterogeneous user behaviors, where users can be stratified into $J \le |\mathcal{U}|$ latent user clusters, each exhibiting distinct preferences. For this setting, we propose a UCB-type algorithm with delicate communication protocols. Through theoretical analysis, we give sub-linear regret bounds on par with those achieved in the synchronous framework, while incurring only logarithmic communication costs. Empirical evaluation on synthetic and real-world datasets validates our algorithm's superior performance in terms of regrets and communication costs.

Related papers

• Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity [85.92481138826949]
  We develop a new method-Shadowheart SGD-that provably improves the time complexities of all previous centralized methods. We also consider the bidirectional setup, where broadcasting from the server to the workers is non-negligible, and develop a corresponding method.
  arXiv  Detail & Related papers  (2024-02-07T12:15:56Z)
• Asynchronous SGD on Graphs: a Unified Framework for Asynchronous Decentralized and Federated Optimization [13.119144971868632]
  We introduce Asynchronous SGD on Graphs (AGRAF SGD) -- a general algorithmic framework that covers asynchronous versions of many popular algorithms. We provide rates of convergence under much milder assumptions than previous decentralized asynchronous computation works.
  arXiv  Detail & Related papers  (2023-11-01T11:58:16Z)
• Pure Exploration in Asynchronous Federated Bandits [57.02106627533004]
  We study the federated pure exploration problem of multi-armed bandits and linear bandits, where $M$ agents cooperatively identify the best arm via communicating with the central server. We propose the first asynchronous multi-armed bandit and linear bandit algorithms for pure exploration with fixed confidence.
  arXiv  Detail & Related papers  (2023-10-17T06:04:00Z)
• Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
  We study multi-agent reinforcement learning in the setting of episodic Markov decision processes. We propose a provably efficient algorithm based on value that enable asynchronous communication. We show that a minimal $Omega(dM)$ communication complexity is required to improve the performance through collaboration.
  arXiv  Detail & Related papers  (2023-05-10T20:29:29Z)
• Pick your Neighbor: Local Gauss-Southwell Rule for Fast Asynchronous Decentralized Optimization [37.85806148420504]
  In decentralized optimization environments, each agent $i$ in a network of $n$ optimization nodes possesses a private function $f_i$. We introduce an optimization-aware selection rule that chooses the neighbor with the highest dual cost improvement. We show that the proposed set-wise GS rule achieves a speedup by a factor of up to the maximum degree in the network.
  arXiv  Detail & Related papers  (2022-07-15T15:37:03Z)
• A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits [77.09836892653176]
  We study federated contextual linear bandits, where $M$ agents cooperate with each other to solve a global contextual linear bandit problem with the help of a central server. We consider the asynchronous setting, where all agents work independently and the communication between one agent and the server will not trigger other agents' communication. We prove that the regret of textttFedLinUCB is bounded by $tildeO(dsqrtsum_m=1M T_m)$ and the communication complexity is $tildeO(dM
  arXiv  Detail & Related papers  (2022-07-07T06:16:19Z)
• Communication-Efficient Federated Learning With Data and Client Heterogeneity [22.432529149142976]
  Federated Learning (FL) enables large-scale distributed training of machine learning models. executing FL at scale comes with inherent practical challenges. We present the first variant of the classic federated averaging (FedAvg) algorithm.
  arXiv  Detail & Related papers  (2022-06-20T22:39:39Z)
• Distributed Adaptive Learning Under Communication Constraints [54.22472738551687]
  This work examines adaptive distributed learning strategies designed to operate under communication constraints. We consider a network of agents that must solve an online optimization problem from continual observation of streaming data.
  arXiv  Detail & Related papers  (2021-12-03T19:23:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.