Decentralized Blockchain-based Robust Multi-agent Multi-armed Bandit

• URL: http://arxiv.org/abs/2402.04417v2
• Date: Thu, 25 Jul 2024 23:31:56 GMT
• Title: Decentralized Blockchain-based Robust Multi-agent Multi-armed Bandit
• Authors: Mengfan Xu, Diego Klabjan,
• Abstract summary: We study a robust, i.e. in presence of malicious participants, multi-agent multi-armed bandit problem where multiple participants are distributed on a fully decentralized blockchain. We are the first to incorporate advanced techniques from blockchains into a cooperative decision making framework to design optimal strategies for honest participants. Notably, we are the first to prove the theoretical regret of the proposed algorithm and claim its optimality.
• Score: 12.547006167704398
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a robust, i.e. in presence of malicious participants, multi-agent multi-armed bandit problem where multiple participants are distributed on a fully decentralized blockchain, with the possibility of some being malicious. The rewards of arms are homogeneous among the honest participants, following time-invariant stochastic distributions, which are revealed to the participants only when certain conditions are met to ensure that the coordination mechanism is secure enough. The coordination mechanism's objective is to efficiently ensure the cumulative rewards gained by the honest participants are maximized. To this end, we are the first to incorporate advanced techniques from blockchains, as well as novel mechanisms, into such a cooperative decision making framework to design optimal strategies for honest participants. This framework allows various malicious behaviors and the maintenance of security and participant privacy. More specifically, we select a pool of validators who communicate to all participants, design a new consensus mechanism based on digital signatures for these validators, invent a UCB-based strategy that requires less information from participants through secure multi-party computation, and design the chain-participant interaction and an incentive mechanism to encourage participants' participation. Notably, we are the first to prove the theoretical regret of the proposed algorithm and claim its optimality. Unlike existing work that integrates blockchains with learning problems such as federated learning which mainly focuses on optimality via computational experiments, we demonstrate that the regret of honest participants is upper bounded by $\log{T}$ under certain assumptions. The regret bound is consistent with the multi-agent multi-armed bandit problem, both without malicious participants and with purely Byzantine attacks which do not affect the entire system.

Related papers

• Securing Proof of Stake Blockchains: Leveraging Multi-Agent Reinforcement Learning for Detecting and Mitigating Malicious Nodes [0.2982610402087727]
  MRL-PoS+ is a novel consensus algorithm to enhance the security of PoS blockchains. We show that MRL-PoS+ significantly improves the attack resilience of PoS blockchains.
  arXiv  Detail & Related papers  (2024-07-30T17:18:03Z)
• Proof-of-Collaborative-Learning: A Multi-winner Federated Learning Consensus Algorithm [2.5203968759841158]
  We propose Proof-of-Collaborative-Learning (PoCL), a multi-winner federated learning validated consensus mechanism. PoCL redirects the power of blockchains to train federated learning models. We present a novel evaluation mechanism to ensure the efficiency of the locally trained models of miners.
  arXiv  Detail & Related papers  (2024-07-17T21:14:05Z)
• Enhancing Trust and Privacy in Distributed Networks: A Comprehensive Survey on Blockchain-based Federated Learning [51.13534069758711]
  Decentralized approaches like blockchain offer a compelling solution by implementing a consensus mechanism among multiple entities. Federated Learning (FL) enables participants to collaboratively train models while safeguarding data privacy. This paper investigates the synergy between blockchain's security features and FL's privacy-preserving model training capabilities.
  arXiv  Detail & Related papers  (2024-03-28T07:08:26Z)
• PureLottery: Fair and Bias-Resistant Leader Election with a Novel Single-Elimination Tournament Algorithm [0.0]
  Leader Election (LE) is crucial in distributed systems and blockchain technology, ensuring one participant acts as the leader. Traditional LE methods often depend on distributed random number generation (RNG), facing issues like vulnerability to manipulation, lack of fairness, and the need for complex procedures such as verifiable delay functions (VDFs) and publicly-verifiable secret sharing (PVSS) This Bachelor's thesis presents a novel approach to randomized LE, leveraging a game-theoretic assumption that participants, aiming to be chosen as leaders, will naturally avoid actions that diminish their chances. This perspective simplifies LE by eliminating the need for decentralized
  arXiv  Detail & Related papers  (2024-02-27T12:30:17Z)
• Generative AI-enabled Blockchain Networks: Fundamentals, Applications, and Case Study [73.87110604150315]
  Generative Artificial Intelligence (GAI) has emerged as a promising solution to address challenges of blockchain technology. In this paper, we first introduce GAI techniques, outline their applications, and discuss existing solutions for integrating GAI into blockchains.
  arXiv  Detail & Related papers  (2024-01-28T10:46:17Z)
• MRL-PoS: A Multi-agent Reinforcement Learning based Proof of Stake Consensus Algorithm for Blockchain [0.18641315013048293]
  This paper introduces MRL-PoS, a Proof-of-Stake consensus algorithm based on multi-agent reinforcement learning. It incorporates a system of rewards and penalties to eliminate malicious nodes and incentivize honest ones.
  arXiv  Detail & Related papers  (2023-12-14T16:58:18Z)
• Adversarial Training Should Be Cast as a Non-Zero-Sum Game [121.95628660889628]
  Two-player zero-sum paradigm of adversarial training has not engendered sufficient levels of robustness. We show that the commonly used surrogate-based relaxation used in adversarial training algorithms voids all guarantees on robustness. A novel non-zero-sum bilevel formulation of adversarial training yields a framework that matches and in some cases outperforms state-of-the-art attacks.
  arXiv  Detail & Related papers  (2023-06-19T16:00:48Z)
• Cooperative Multi-Agent Actor-Critic for Privacy-Preserving Load Scheduling in a Residential Microgrid [71.17179010567123]
  We propose a privacy-preserving multi-agent actor-critic framework where the decentralized actors are trained with distributed critics. The proposed framework can preserve the privacy of the households while simultaneously learn the multi-agent credit assignment mechanism implicitly.
  arXiv  Detail & Related papers  (2021-10-06T14:05:26Z)
• Emergence of Theory of Mind Collaboration in Multiagent Systems [65.97255691640561]
  We propose an adaptive training algorithm to develop effective collaboration between agents with ToM. We evaluate our algorithms with two games, where our algorithm surpasses all previous decentralized execution algorithms without modeling ToM.
  arXiv  Detail & Related papers  (2021-09-30T23:28:00Z)
• Multi-Stage Decentralized Matching Markets: Uncertain Preferences and Strategic Behaviors [91.3755431537592]
  This article develops a framework for learning optimal strategies in real-world matching markets. We show that there exists a welfare-versus-fairness trade-off that is characterized by the uncertainty level of acceptance. We prove that participants can be better off with multi-stage matching compared to single-stage matching.
  arXiv  Detail & Related papers  (2021-02-13T19:25:52Z)

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.