Communication-Corruption Coupling and Verification in Cooperative Multi-Objective Bandits
Ming Shi · 2026
Read Communication-Corruption Coupling and Verification in Cooperative Multi-Objective Bandits by Ming Shi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-11924.txt.
Introduction
Ming Shi studies shared bandit tasks where reward data can be spoiled. Many agents pick arms over many rounds and share what they learn. Each reward is a vector, so more than one goal is in play. A foe can spoil the shared data, but only up to a set total budget.
A check step can test some data, but checks are scarce. Shi links how much spoil is used with how checks are placed. The work aims for methods that still learn well under attack. Such guards help shared learning in open, risky nets.
Catalog record
| CREATOR | Ming Shi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 29 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-11924
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Communication-Corruption Coupling and Verification in Cooperative Multi-Objective Bandits Thanks: Ming Shi Abstract We study cooperative stochastic multi-armed bandits with vector-valued rewards under adversarial corruption and limited verification. In each of T T rounds, each of N 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 L -Lipschitz scalarization ϕ \phi , 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 N Γ N\Gamma , 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 N -fold larger additive corruption penalty, whereas summary sharing and recommendation-only sharing preserve an unamplified O ( Γ ) 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 Γ = Θ ( N T ) \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 . I Introduction Stochastic multi-armed bandits (MAB) provide a canonical model for sequential decision-making with unknown reward distributions and a regret objective [ 12 , 3 , 5 ] . A growing class of applications, however, is inherently distributed and multi-metric: multiple cooperative agents (devices, robots, base stations, edge servers) repeatedly probe the same set of actions while optimizing a vector of objectives such as latency, reliability, energy, and fairness. These settings naturally lead to multi-agent multi-objective bandits , where learning speed is shaped not only by the stochasticity of the environment but also by how agents communicate and aggregate information [ 2 , 14 ] . A central obstacle in such deployments is that feedback can be strategically corrupted , e.g., measurements may be perturbed by sensor faults, compromised telemetry, click fraud, fake reviews, or data poisoning. This has motivated the study of stochastic bandits with adversarial corruptions , where an adaptive adversary perturbs observed rewards subject to a global budget [ 13 , 10 , 11 ] . Existing theory largely characterizes a single learner’s regret as a stochastic term plus corruption term tradeoff. In contrast, in cooperative systems the communication layer can replicate corrupted samples across agents (e.g., via raw-sample broadcasting), thereby altering the statistical effect of the same environment-side corruption budget. This communication-induced amplification phenomenon is orthogonal to (and not captured by) standard models of cooperative bandits under clean feedback and limited/imperfect communication [ 2 , 14 ] , and decentralized robustness to malicious/Byzantine agents [ 17 , 16 ] . Moreover, corruption is especially consequential in multi-objective learning. Each pull returns a reward vector, and small perturbations can distort implied trade-offs, invalidate dominance relations, and break optimism based on scalar utilities. While multi-objective bandits have been studied under clean feedback (e.g., Pareto or scalarization objectives) [ 15 , 8 , 4 , 7 , 6 ] , their intersection with budgeted adversarial corruption and cooperative communication is not well understood. We study cooperative N -agent stochastic multi-objective bandits with vector rewards in [0,1]^{d} . Agents exchange messages according to one of three canonical protocols: raw-sample sharing (S1), sufficient-statistic sharing (S2), or recommendation-only sharing (S3). An adaptive adversary corrupts unverified observations under a global corruption budget \Gamma , and the team may additionally acquire at most \nu verified (clean) observations system-wide. Performance is measured by team regret under a monotone L -Lipschitz scalarization \phi (covering linear, Chebyshev/min, and smooth log-sum-exp utilities) [ 15 ] . This setting leads to three information-theoretic questions that are specific to cooperative systems: 1. Communication–corruption coupling: how does the regret depend on (\Gamma,N) under different sharing protocols? 2. Protocol-induced phase transitions: can a fixed environment-side budget \Gamma yield qualitatively different learnability depending on whether corrupted data are replicated through communication? 3. Clean side information: how much verification budget \nu is necessary and sufficient to recover learnability when corruption is severe? Our main contributions provide a protocol-level characterization of corruption robustness in cooperative multi-objective bandits. • A protocol-level corruption functional (effective corruption). We formalize how a cooperative algorithm uses each underlying agent-round observation across the network via a multiplicity (replication) factor, which induces an effective corruption level. This yields a sharp distinction. That is, (S1) can inflate the corruption impact by up to a factor N via replication, whereas (S2)-(S3) avoid replication and preserve the original O(\Gamma) corruption penalty. • A meta regret theorem parameterized by effective corruption. We prove a protocol-agnostic robust-UCB guarantee in which the corruption term scales with the induced effective corruption (rather than \Gamma itself), and we show how monotone scalarizations can be handled via a dominance-preserving vector-to-scalar optimism principle. • Tight separation between sharing modes (S1) versus (S2) and (S3). For (S1), we provide a matching lower bound showing that naive “append-all” raw sharing can be information-theoretically N -times worse in the corruption term. For (S2) and (S3), we obtain centralized-rate team regret (up to logarithmic factors) with only an unamplified O(\Gamma) corruption penalty. • Verification and certified sharing under high corruption. To address regimes where corrupted feedback alone is insufficient, we introduce a verification channel and show that sharing verified certificates enables the team to filter corrupted recommendations and regain identifiability with \nu scaling on the order of K\log(\cdot)/\Delta_{\min}^{2} (up to constants and Lipschitz factors), even when \Gamma is linear in the total number of pulls. This mechanism is distinct from prior multi-agent robustness models (e.g., Byzantine agents) [ 17 ] and from existing corruption-robust multi-agent bandits that do not treat multi-objective scalarization and verification jointly [ 9 ] . Overall, our results show that in cooperative multi-objective bandits, what agents share can be as consequential as how much corruption the environment injects . Communication protocols reshape the effective statistical contamination, and limited verified information can be leveraged to restore learnability in the high-corruption regime. II Problem Formulation Notation: Let [K]\triangleq\{1,\dots,K\} denote the arm set and d the number of objectives. For x,y\in\mathbb{R}^{d} , write x\preceq y for coordinate-wise inequality. Unless stated otherwise, \|\cdot\|=\|\cdot\|_{\infty} . Let \mathbf{1}\in\mathbb{R}^{d} be the all-ones vector. There are N agents indexed by n\in[N] and the horizon is T rounds. II-A Multi-Agent Stochastic Multi-Objective Bandits Each arm k is associated with an unknown distribution \mathcal{D}_{k} supported on [0,1]^{d} , with mean vector \mu_{k}\triangleq\mathbb{E}_{R\sim\mathcal{D}_{k}}[R]\in[0,1]^{d} . At each round t=1,2,\dots,T , agent n chooses an arm k_{n,t}\in[K] . Conditioned on joint action \{k_{n,t}\}_{n=1}^{N} , the environment draws clean rewards R_{n,t}\sim\mathcal{D}_{k_{n,t}} , independently across agents and time (conditioned on the chosen arms). Let \mathcal{H}_{n,t-1} be the \sigma -field generated by agent n ’s past observations and all messages received up to time t-1 under the communication