Byzantine-Resilient Decentralized Multi-Armed Bandits

Jingxuan Zhu, Alec Koppel, Alvaro Velasquez, Ji Liu

TL;DR

This paper introduces a decentralized, Byzantine-resilient Multi-Armed Bandit (MAB) algorithm that allows cooperative agents to safely share information even when an unknown fraction of the network is malicious. By combining a threshold-based consistency filter with a trimmed-mean step, the algorithm guarantees that honest agents perform no worse than independent single agents, and collectively outperform them if local network connectivity is sufficient ($3f+1$ neighbors).

What Problem Does This Paper Address?

Multi-Armed Bandit (MAB) problems model the classic exploration-exploitation trade-off, where an agent tries to maximize rewards by choosing from multiple options (arms) with unknown reward distributions. In multi-agent cooperative MAB, agents share their experiences over a network to learn the best actions faster, significantly reducing their cumulative "regret" (the loss incurred by not choosing the optimal arm).

However, existing cooperative methods assume a perfect world where all agents are honest. In reality, networks are vulnerable to "Byzantine" agents—malicious actors that broadcast completely false reward estimates or manipulated sample counts to derail the network. This can model cyberattackers, financial market manipulators, or bots injecting offensive content into recommender systems. If standard consensus algorithms are used, even a single Byzantine agent can corrupt the network, leading to catastrophic performance degradation. The authors tackle the challenge of preserving the benefits of cooperation in a fully decentralized network without relying on a central server or global network knowledge, even in the presence of these malicious actors.

Methods

The authors propose a Byzantine-Resilient Collaborative UCB framework. Instead of using standard running consensus protocols—which pass weighted averages over time and inadvertently trap malicious bias in a network loop—this algorithm utilizes a one-time local information mixing step combined with two distinct filters at each time step:

  1. Consistency Filter: Eliminates data from neighbors whose reported sample counts are suspiciously low compared to the agent's own sample count. This prevents Byzantine agents from freezing their sample counts to manipulate confidence intervals.
  2. Trimmed Mean Filter: If the number of remaining neighbors is greater than $2f$ (where $f$ is the maximum number of Byzantine neighbors), the agent discards the $f$ highest and $f$ lowest reported reward means. This strips away extreme adversarial values before calculating the local estimate.

By avoiding historical consensus memory and computing a fresh, filtered local average at each step, the adversarial bias naturally shrinks toward zero as honest agents collect more real data.

Datasets

The paper evaluates its approach using simulated environments rather than static real-world datasets:

  • Synthetic Bernoulli Bandits: A 4-arm bandit problem where rewards follow Bernoulli distributions, tested over 5-agent and 10-agent random network topologies.
  • Simulated Recommender System: A practical setup modeling 10 advertising firms cooperating to serve the best ads out of 20 options to users. This environment was tested under two attack models: Gaussian Attacks (adding random noise) and Adaptive Attacks (where adversaries perfectly monitor honest agents to strategically down-rate the optimal arm).

Key Insights and Ideas

  • Consensus is a Trap for Resilient MAB: The most surprising insight is that standard running consensus is fundamentally incompatible with Byzantine filtering in MAB. Because consensus propagates information recursively, malicious bias accumulates over time. Discarding network memory and relying on one-time local filtering is the key to achieving resilience.
  • No Global Knowledge Required: Unlike previous robust MAB methods, this algorithm requires absolutely no global knowledge of network connectivity or topology. Agents only need to know a local upper bound ($f$) on the number of malicious neighbors they might have.
  • The $3f+1$ Rule for Network Synergy: The authors prove that if every agent has at least $3f+1$ neighbors, the network achieves "Network Outperformance." This means the group collectively achieves strictly lower regret than if they all worked in isolation, proving that cooperation is viable even under attack.

Key Results

  • Per-Agent Guarantees: Mathematically, the regret of any honest agent using this method is proven to be no worse than the classic single-agent UCB1 algorithm ($O(\log T)$ regret).
  • Prior Methods Fail: In simulations, applying a trimmed-mean filter to older consensus-based MAB algorithms still resulted in linear regret (complete failure), validating the authors' theoretical critique of running consensus.
  • Robustness to Attack Types: In the recommender system simulation, the proposed algorithm successfully resisted both basic Gaussian noise attacks and highly sophisticated Adaptive Attacks, maintaining low regret in both scenarios.

Limitations and Future Work

  • No Contextual Information: The current framework is limited to standard multi-armed bandits. It cannot yet incorporate contextual information (like user demographics or historical features), which is vital for modern real-world recommender systems.
  • Known Adversarial Bound: The algorithm assumes each agent knows $f$, the maximum number of Byzantine neighbors. In highly dynamic or completely anonymous networks, estimating this bound accurately remains an open challenge.

Summary updated

Abstract

In decentralized cooperative multi-armed bandits (MAB), each agent observes a distinct stream of rewards, and seeks to exchange information with others to select a sequence of arms so as to minimize its regret. Agents in the cooperative setting can outperform a single agent running a MAB method such as Upper-Confidence Bound (UCB) independently. In this work, we study how to recover such salient behavior when an unknown fraction of the agents can be Byzantine, that is, communicate arbitrarily wrong information in the form of reward mean-estimates or confidence sets. This framework can be used to model attackers in computer networks, instigators of offensive content into recommender systems, or manipulators of financial markets. Our key contribution is the development of a fully decentralized resilient upper confidence bound (UCB) algorithm that fuses an information mixing step among agents with a truncation of inconsistent and extreme values. This truncation step enables us to establish that the performance of each normal agent is no worse than the classic single-agent UCB1 algorithm in terms of regret, and more importantly, the cumulative regret of all normal agents is strictly better than the non-cooperative case, provided that each agent has at least 3f+1 neighbors where f is the maximum possible Byzantine agents in each agent's neighborhood. Extensions to time-varying neighbor graphs, and minimax lower bounds are further established on the achievable regret. Experiments corroborate the merits of this framework in practice.
BibTeX
@article{zhu2024byzantine,
  author = {Jingxuan Zhu and Alec Koppel and Alvaro Velasquez and Ji Liu},
  title = {{Byzantine-Resilient Decentralized Multi-Armed Bandits}},
  journal = {Accepted by TMLR},
  year = {2024},
  url = {https://openreview.net/forum?id=JoYMJJdvry},
}
Figure