  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.
