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
- 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) - The Latency Price of Threshold Cryptosystem in Blockchains [52.359230560289745]
We study the interplay between threshold cryptography and a class of blockchains that use Byzantine-fault tolerant (BFT) consensus protocols.
Existing approaches for threshold cryptosystems introduce a latency overhead of at least one message delay for running the threshold cryptographic protocol.
We propose a mechanism to eliminate this overhead for blockchain-native threshold cryptosystems with tight thresholds.
arXiv Detail & Related papers (2024-07-16T20:53:04Z) - Fuzzychain: An Equitable Consensus Mechanism for Blockchain Networks [12.433289572707212]
Fuzzychain is a proposed solution to the drawbacks of Proof of Stake (PoS)
It introduces the use of fuzzy sets to define stake semantics, promoting decentralised and distributed processing control.
Our results indicate that Fuzzychain not only matches PoS in functionality but also ensures a fairer distribution of stakes among validators.
arXiv Detail & Related papers (2024-04-20T10:01:40Z) - 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) - Defending Against Poisoning Attacks in Federated Learning with
Blockchain [12.840821573271999]
We propose a secure and reliable federated learning system based on blockchain and distributed ledger technology.
Our system incorporates a peer-to-peer voting mechanism and a reward-and-slash mechanism, which are powered by on-chain smart contracts, to detect and deter malicious behaviors.
arXiv Detail & Related papers (2023-07-02T11:23:33Z) - Byzantine-Robust Online and Offline Distributed Reinforcement Learning [60.970950468309056]
We consider a distributed reinforcement learning setting where multiple agents explore the environment and communicate their experiences through a central server.
$alpha$-fraction of agents are adversarial and can report arbitrary fake information.
We seek to identify a near-optimal policy for the underlying Markov decision process in the presence of these adversarial agents.
arXiv Detail & Related papers (2022-06-01T00:44:53Z) - 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) - Byzantine-resilient Decentralized Stochastic Gradient Descent [85.15773446094576]
We present an in-depth study towards the Byzantine resilience of decentralized learning systems.
We propose UBAR, a novel algorithm to enhance decentralized learning with Byzantine Fault Tolerance.
arXiv Detail & Related papers (2020-02-20T05:11:04Z)
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.