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

• URL: http://arxiv.org/abs/2402.04417v1
• Date: Tue, 6 Feb 2024 21:33:34 GMT
• Title: Decentralized Blockchain-based Robust Multi-agent Multi-armed Bandit
• Authors: Mengfan Xu, Diego Klabjan
• Abstract summary: We study a robust multi-agent multi-armed bandit problem where multiple clients or participants are distributed on a fully decentralized blockchain. We are the first to incorporate advanced techniques from blockchains, as well as novel mechanisms, into the system to design optimal strategies for honest participants. This is consistent with the multi-agent multi-armed bandit problem without malicious participants and the robust multi-agent multi-armed bandit problem with purely Byzantine attacks.
• Score: 14.822625665220068
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a robust multi-agent multi-armed bandit problem where multiple clients or participants are distributed on a fully decentralized blockchain, with the possibility of some being malicious. The rewards of arms are homogeneous among the clients, following time-invariant stochastic distributions that are revealed to the participants only when the system is secure enough. The system's objective is to efficiently ensure the cumulative rewards gained by the honest participants. To this end and to the best of our knowledge, we are the first to incorporate advanced techniques from blockchains, as well as novel mechanisms, into the system to design optimal strategies for honest participants. This allows various malicious behaviors and the maintenance of participant privacy. More specifically, we randomly select a pool of validators who have access to all participants, design a brand-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 guarantee of the proposed algorithms by regret analyses in the context of optimality in blockchains. Unlike existing work that integrates blockchains with learning problems such as federated learning which mainly focuses on numerical optimality, we demonstrate that the regret of honest participants is upper bounded by $log{T}$. This is consistent with the multi-agent multi-armed bandit problem without malicious participants and the robust multi-agent multi-armed bandit problem with purely Byzantine attacks.

Related papers

• Hollow Victory: How Malicious Proposers Exploit Validator Incentives in Optimistic Rollup Dispute Games [2.88268082568407]
  A popular layer-2 approach is the Optimistic Rollup, which relies on a mechanism known as a dispute game for block proposals. In these systems, validators can challenge blocks that they believe contain errors, and a successful challenge results in the transfer of a portion of the proposer's deposit as a reward. We reveal a structural vulnerability in the mechanism: validators may not be awarded a proper profit despite winning a dispute challenge.
  arXiv  Detail & Related papers  (2025-04-07T14:00:46Z)
• Blockchain-Empowered Cyber-Secure Federated Learning for Trustworthy Edge Computing [0.36700088931938835]
  Federated Learning (FL) is a privacy-preserving distributed machine learning scheme. The FL paradigm may become vulnerable due to an active attack from the network participants, called a poisonous attack. This paper presents a cross-device FL model that ensures trustworthiness, fairness, and authenticity in the underlying FL training process.
  arXiv  Detail & Related papers  (2024-12-30T02:58:18Z)
• Protocol Learning, Decentralized Frontier Risk and the No-Off Problem [56.74434512241989]
  We identify a third paradigm - Protocol Learning - where models are trained across decentralized networks of incentivized participants. This approach has the potential to aggregate orders of magnitude more computational resources than any single centralized entity. It also introduces novel challenges: heterogeneous and unreliable nodes, malicious participants, the need for unextractable models to preserve incentives, and complex governance dynamics.
  arXiv  Detail & Related papers  (2024-12-10T19:53:50Z)
• 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)
• Robust and Performance Incentivizing Algorithms for Multi-Armed Bandits with Strategic Agents [52.75161794035767]
  We introduce a class of bandit algorithms that meet the two objectives of performance incentivization and robustness simultaneously. We show that settings where the principal has no information about the arms' performance characteristics can be handled by combining ideas from second price auctions with our algorithms.
  arXiv  Detail & Related papers  (2023-12-13T06:54:49Z)
• 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.