# Communication-Corruption Coupling and Verification in Cooperative Multi-Objective Bandits

arXiv: https://arxiv.org/abs/2601.11924 · HTML: https://mlsanity.com/paper/2601.11924/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 18 references that are in the map.
- First posted on arXiv 17 Jan 2026.

## Builds on (most cited first, 10 of 10)

- [A Survey of Multi-Objective Sequential Decision-Making](https://mlsanity.com/paper/1402.0590/) (2014)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Better Algorithms for Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/1902.08647/) (2019)
- [Multi-Agent Multi-Armed Bandits with Limited Communication](https://mlsanity.com/paper/2102.08462/) (2021)
- [On Optimal Robustness to Adversarial Corruption in Online Decision Problems](https://mlsanity.com/paper/2109.10963/) (2021)
- [One More Step Towards Reality: Cooperative Bandits with Imperfect Communication](https://mlsanity.com/paper/2111.12482/) (2021)
- [Sequential Learning of the Pareto Front for Multi-objective Bandits](https://mlsanity.com/paper/2501.17513/) (2025)
- [Provably Efficient Multi-Objective Bandit Algorithms under Preference-Centric Customization](https://mlsanity.com/paper/2502.13457/) (2025)
- [Byzantine-Resilient Decentralized Multi-Armed Bandits](https://mlsanity.com/paper/2310.07320/) (2023)
- [Multi-Agent Stochastic Bandits Robust to Adversarial Corruptions](https://mlsanity.com/paper/2411.08167/) (2024)

## Built on by (most cited first, 1 of 1)

- [Multi-Objective Multi-Agent Bandits: From Learning Efficiency to Fairness Optimization](https://mlsanity.com/paper/2605.06864/) (2026)

## Abstract (arXiv)

We study cooperative stochastic multi-armed bandits with vector-valued rewards under adversarial corruption and limited verification. In each of T rounds, each of N agents selects an arm, the environment generates a clean reward vector, and an adversary perturbs the observed feedback subject to a global corruption budget Gamma. Performance is measured by team regret under a coordinate-wise nondecreasing, L-Lipschitz scalarization φ, covering linear, Chebyshev, and smooth monotone utilities. Our main contribution is a communication-corruption coupling: we show that a fixed environment-side budget Gamma can translate into an effective corruption level ranging from Gamma to NGamma, depending on whether agents share raw samples, sufficient statistics, or only arm recommendations. We formalize this via a protocol-induced multiplicity functional and prove regret bounds parameterized by the resulting effective corruption. As corollaries, raw-sample sharing can suffer an N-fold larger additive corruption penalty, whereas summary sharing and recommendation-only sharing preserve an unamplified O(Gamma) term and achieve centralized-rate team regret. We further establish information-theoretic limits, including an unavoidable additive Omega(Gamma) penalty and a high-corruption regime Gamma=Theta(NT) where sublinear regret is impossible without clean information. Finally, we characterize how a global budget nu of verified observations restores learnability. That is, verification is necessary in the high-corruption regime, and sufficient once it crosses the identification threshold, with certified sharing enabling the team's regret to become independent of Gamma.