# Robust Multi-Agent Bandits with Heavy-Tailed Rewards and Information Asymmetry

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 16 references that are in the map.
- First posted on arXiv 11 Aug 2026.

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

- [Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffs](https://mlsanity.com/paper/1810.10895/) (2018)
- [Cooperative Multi-Agent Bandits with Heavy Tails](https://mlsanity.com/paper/2008.06244/) (2020)
- [Catoni-style confidence sequences for heavy-tailed mean estimation](https://mlsanity.com/paper/2202.01250/) (2022)
- [Online Learning for Cooperative Multi-Player Multi-Armed Bandits](https://mlsanity.com/paper/2109.03818/) (2021)
- [Multi-player Multi-armed Bandits with Collision-Dependent Reward Distributions](https://mlsanity.com/paper/2106.13669/) (2021)
- [Optimal Cooperative Multiplayer Learning Bandits with Noisy Rewards and No Communication](https://mlsanity.com/paper/2311.06210/) (2023)
- [Multi-agent Multi-armed Bandit with Fully Heavy-tailed Dynamics](https://mlsanity.com/paper/2501.19239/) (2025)

## Abstract (arXiv)

The multi-armed bandit problem is a central framework in sequential decision-making, extensively studied under sub-Gaussian reward assumptions. However, real-world applications often involve heavy-tailed reward distributions and decentralized, information-asymmetric interactions. We study multi-agent multi-armed bandits with heavy-tailed rewards under three information-asymmetry regimes: unobserved actions with common rewards, observed actions with independent rewards, and unobserved actions with independent rewards. We develop robust decentralized algorithms for each setting and derive regret guarantees that nearly match centralized heavy-tailed rates. Experiments on a Pareto-distributed reward environment validate our theoretical findings and illustrate the trade-offs between synchronization, coordination, and exploration across the three regimes.