A Federated Online Restless Bandit Framework for Cooperative Resource Allocation

• URL: http://arxiv.org/abs/2406.07992v1
• Date: Wed, 12 Jun 2024 08:34:53 GMT
• Title: A Federated Online Restless Bandit Framework for Cooperative Resource Allocation
• Authors: Jingwen Tong, Xinran Li, Liqun Fu, Jun Zhang, Khaled B. Letaief,
• Abstract summary: We study the cooperative resource allocation problem with unknown system dynamics of MRPs. We put forth a Federated Thompson-enabled Whittle Index (FedTSWI) algorithm to solve this multi-agent online RMAB problem. Numerical results show that the proposed algorithm achieves a fast convergence rate of $mathcalO(sqrtTlog(T))$ and better performance compared with baselines.
• Score: 23.698976872351576
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Restless multi-armed bandits (RMABs) have been widely utilized to address resource allocation problems with Markov reward processes (MRPs). Existing works often assume that the dynamics of MRPs are known prior, which makes the RMAB problem solvable from an optimization perspective. Nevertheless, an efficient learning-based solution for RMABs with unknown system dynamics remains an open problem. In this paper, we study the cooperative resource allocation problem with unknown system dynamics of MRPs. This problem can be modeled as a multi-agent online RMAB problem, where multiple agents collaboratively learn the system dynamics while maximizing their accumulated rewards. We devise a federated online RMAB framework to mitigate the communication overhead and data privacy issue by adopting the federated learning paradigm. Based on this framework, we put forth a Federated Thompson Sampling-enabled Whittle Index (FedTSWI) algorithm to solve this multi-agent online RMAB problem. The FedTSWI algorithm enjoys a high communication and computation efficiency, and a privacy guarantee. Moreover, we derive a regret upper bound for the FedTSWI algorithm. Finally, we demonstrate the effectiveness of the proposed algorithm on the case of online multi-user multi-channel access. Numerical results show that the proposed algorithm achieves a fast convergence rate of $\mathcal{O}(\sqrt{T\log(T)})$ and better performance compared with baselines. More importantly, its sample complexity decreases with the number of agents.

Related papers

• 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)
• Serverless Federated AUPRC Optimization for Multi-Party Collaborative Imbalanced Data Mining [119.89373423433804]
  Area Under Precision-Recall (AUPRC) was introduced as an effective metric. Serverless multi-party collaborative training can cut down the communications cost by avoiding the server node bottleneck. We propose a new ServerLess biAsed sTochastic gradiEnt (SLATE) algorithm to directly optimize the AUPRC.
  arXiv  Detail & Related papers  (2023-08-06T06:51:32Z)
• Distributed Consensus Algorithm for Decision-Making in Multi-agent Multi-armed Bandit [7.708904950194129]
  We study a structured multi-agent multi-armed bandit (MAMAB) problem in a dynamic environment. A graph reflects the information-sharing structure among agents, and the arms' reward distributions are piecewise-stationary with several unknown change points. The goal is to develop a decision-making policy for the agents that minimizes the regret, which is the expected total loss of not playing the optimal arm at each time step.
  arXiv  Detail & Related papers  (2023-06-09T16:10:26Z)
• A Bandit Approach to Online Pricing for Heterogeneous Edge Resource Allocation [8.089950414444115]
  Two novel online pricing mechanisms are proposed for heterogeneous edge resource allocation. The mechanisms operate in real-time and do not require prior knowledge of demand distribution. The proposed posted pricing schemes allow users to select and pay for their preferred resources, with the platform dynamically adjusting resource prices based on observed historical data.
  arXiv  Detail & Related papers  (2023-02-14T10:21:14Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  We propose an efficient model-based reinforcement learning algorithm for learning in multi-agent systems. Our main theoretical contributions are the first general regret bounds for model-based reinforcement learning for MFC. We provide a practical parametrization of the core optimization problem.
  arXiv  Detail & Related papers  (2021-07-08T18:01:02Z)
• Robust Restless Bandits: Tackling Interval Uncertainty with Deep Reinforcement Learning [31.515757763077065]
  We introduce Robust Restless Bandits, a generalization of restless multi-arm bandits (RMAB) We develop solutions for a minimax regret objective when transitions are given by interval uncertainties. We introduce RMABPPO, a novel deep reinforcement learning algorithm for solving RMABs.
  arXiv  Detail & Related papers  (2021-07-04T17:21:26Z)
• Low-Latency Federated Learning over Wireless Channels with Differential Privacy [142.5983499872664]
  In federated learning (FL), model training is distributed over clients and local models are aggregated by a central server. In this paper, we aim to minimize FL training delay over wireless channels, constrained by overall training performance as well as each client's differential privacy (DP) requirement.
  arXiv  Detail & Related papers  (2021-06-20T13:51:18Z)
• Multi-resource allocation for federated settings: A non-homogeneous Markov chain model [2.552459629685159]
  In a federated setting, agents coordinate with a central agent or a server to solve an optimization problem in which agents do not share their information with each other. We describe how the basic additive-increase multiplicative-decrease (AIMD) algorithm can be modified in a straightforward manner to solve a class of optimization problems for federated settings for a single shared resource with no inter-agent communication. We extend the single-resource algorithm to multiple heterogeneous shared resources that emerge in smart cities, sharing economy, and many other applications.
  arXiv  Detail & Related papers  (2021-04-26T19:10:00Z)
• Softmax with Regularization: Better Value Estimation in Multi-Agent Reinforcement Learning [72.28520951105207]
  Overestimation in $Q$-learning is an important problem that has been extensively studied in single-agent reinforcement learning. We propose a novel regularization-based update scheme that penalizes large joint action-values deviating from a baseline. We show that our method provides a consistent performance improvement on a set of challenging StarCraft II micromanagement tasks.
  arXiv  Detail & Related papers  (2021-03-22T14:18:39Z)
• Multi-armed Bandits with Cost Subsidy [1.6631602844999724]
  We present two applications, intelligent SMS routing problem and ad audience optimization problem. We show that naive generalizations of existing MAB algorithms do not perform well for this problem. We also present a simple variant of explore-then-commit and establish near-optimal regret bounds for this algorithm.
  arXiv  Detail & Related papers  (2020-11-03T05:38:42Z)
• Resource Allocation via Model-Free Deep Learning in Free Space Optical Communications [119.81868223344173]
  The paper investigates the general problem of resource allocation for mitigating channel fading effects in Free Space Optical (FSO) communications. Under this framework, we propose two algorithms that solve FSO resource allocation problems.
  arXiv  Detail & Related papers  (2020-07-27T17:38:51Z)

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.