🤖 machine learning

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

This paper proposes robust decentralized algorithms for multi-agent multi-armed bandits under heavy-tailed rewards and three distinct information-asymmetry regimes, achieving regret guarantees that nearly match centralized rates while validating performance through experiments on Pareto-distributed environments.

Original authors: Daphne Feng, Ricardo Parada, Lily Jiang, Sophia Yi, William Chang

Published 2026-08-12

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Daphne Feng, Ricardo Parada, Lily Jiang, Sophia Yi, William Chang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are part of a team of explorers trying to find the best hidden treasure in a vast, foggy forest. You can't talk to each other once the game starts, and you can't see what your teammates are doing. Every time you pick a spot to dig, you get a reward, but sometimes that reward is a tiny pebble, and other times it's a massive, unpredictable boulder that knocks you over. This is the world of "Multi-Armed Bandits," a famous puzzle in computer science and math where a learner must balance trying new things (exploration) with sticking to what seems good (exploitation). Usually, scientists assume these rewards are predictable, like rolling a fair die. But in the real world—think of stock market crashes, viral internet posts, or sudden network spikes—rewards can be wild, heavy-tailed, and full of extreme surprises. The big question this paper tackles is: How can a team of smart agents learn to find the best treasure together when the rewards are chaotic, they can't talk, and they might not even see what the others are doing?

The researchers, a team from UCLA and UC Riverside, set out to solve this messy, real-world version of the treasure hunt. They didn't just look at one scenario; they tested three different levels of "information asymmetry," which is a fancy way of saying "how much do you know about your teammates?" In the first scenario, everyone sees the same treasure chest opening (common reward) but can't see who picked which lock (unobserved actions). In the second, everyone sees who picked which lock, but each person gets their own, separate treasure chest (independent rewards). In the third, and hardest scenario, no one sees anything about the others; everyone is blind to the team's actions and gets their own random loot.

The team invented three new "decentralized algorithms"—essentially, rulebooks for how the agents should behave without talking. For the first two scenarios, they created methods called mRUCB-A and mRUCB-Intervals. These clever strategies use a "robust" way of calculating averages that ignores the crazy, giant outliers (the boulders) so the team doesn't get confused. They found that even without talking, the team could learn almost as fast as if they were all in the same room, provided they could either see the shared reward or see each other's moves. The third algorithm, mHT-DSEE, tackles the hardest case where everyone is totally blind to each other. Here, the agents have to follow a strict, pre-agreed schedule to take turns exploring, which works but is a bit slower.

When they tested these ideas on a computer simulation using a "Pareto distribution"—a mathematical model that mimics those wild, heavy-tailed rewards where a few extreme events dominate—they found that their theories held up. The algorithms successfully found the best treasure, proving that you don't need perfect communication or calm, predictable rewards to work as a team. However, the experiments also showed a trade-off: the method that relied on seeing each other's moves (Problem B) was slower to start because it needed more data to be sure, but once it figured things out, it stopped making mistakes entirely. The totally blind method (Problem C) was cheaper to start but kept exploring a little longer than necessary. Ultimately, the paper shows that even in a chaotic, noisy world where teammates are strangers, smart, coordinated strategies can still lead the group to the best outcome, though the price of being "out of sync" depends heavily on what little bits of information you can share.

Technical Summary: Robust Multi-Agent Bandits with Heavy-Tailed Rewards and Information Asymmetry

Problem Formulation
This work addresses the Multi-Armed Bandit (MAB) problem in a decentralized, multi-agent setting where reward distributions are heavy-tailed. Unlike standard literature that assumes sub-Gaussian rewards, this paper considers distributions where the $(1+\epsilon)$ -th moment is finite ( $E[|X - \mu|^{1+\epsilon}] \le v$ ) but the variance may be infinite. The study focuses on $M$ players who must coordinate to maximize joint rewards without online communication. The authors define three distinct information asymmetry regimes:

Problem A (Common Rewards, Unobserved Actions): All players observe the same reward realization for a joint action but cannot see the individual actions chosen by others.
Problem B (Independent Rewards, Observed Actions): Players observe the joint action taken by the group but receive independent, i.i.d. reward samples.
Problem C (Independent Rewards, Unobserved Actions): Players observe neither the actions of others nor a common reward; each receives only their own independent sample.

Methodology and Algorithms
The authors propose robust decentralized algorithms for each regime, adapting robust mean estimators (specifically truncated means) to the multi-agent context.

Problem A (mRUCB-A): Since rewards are shared, all players maintain identical statistical estimates if they follow a deterministic rule. The algorithm employs a Robust Upper Confidence Bound (RUCB) index. Players agree on a lexicographic ordering to break ties consistently. Because estimates remain synchronized, the problem effectively reduces to a single-agent heavy-tailed bandit over the joint action space, incurring no additional cost from action asymmetry.
Problem B (mRUCB-Intervals): With observed actions but independent rewards, players' estimates diverge. To prevent miscoordination, the authors replace index maximization with a round-robin elimination strategy. Players maintain confidence intervals for each arm. If a player's interval for an arm lies strictly below another's, they signal this by deviating from the scheduled joint action (pulling a different individual arm). Since actions are observable, this deviation acts as a 1-bit implicit communication channel, causing all players to eliminate the suboptimal arm simultaneously. Signaling rounds discard rewards to maintain statistical alignment.
Problem C (mHT-DSEE): In the fully asymmetric setting, neither shared rewards nor observed actions allow for implicit signaling or synchronized estimates. The authors utilize a Deterministic Schedule for Exploration and Exploitation (DSEE). Players follow a pre-agreed cyclic exploration schedule for a duration determined by a function $w(t)$ (e.g., $\lceil \log t \rceil$ ). Once the exploration budget is met, players switch to exploitation based on their own RUCB indices computed solely from exploration samples. Synchronization is maintained because the schedule depends only on the round index $t$ .

Key Contributions and Theoretical Results
The paper derives regret bounds that nearly match centralized heavy-tailed rates for each setting:

Problem A: The expected regret is $O(\log T \sum \Delta_a^{-1/\epsilon})$ . The decentralized agents incur no additional cost compared to a centralized learner, as the shared reward ensures perfect synchronization.
Problem B: The regret bound is $O(\log T \sum \Delta_a^{-1/\epsilon})$ plus constant terms independent of the horizon $T$ . The mechanism uses action deviations as an implicit signaling channel; the cost of signaling is bounded by $(K^M - 1)\Delta_{\max}$ , independent of $T$ and the number of players $M$ .
Problem C: The regret bound is $O(K^M \log^2 T)$ . This setting requires a pre-committed anytime schedule, introducing an extra $\log T$ factor compared to the other regimes. The authors note this factor arises from the lack of shared information to coordinate the switch from exploration to exploitation.

Experimental Validation
Experiments were conducted with $M=2$ players, $K=2$ arms per player, and Pareto-distributed rewards (shape parameter 2, ensuring finite mean but infinite variance).

Results: All three algorithms demonstrated sublinear regret growth, confirming their ability to identify the optimal arm under heavy-tailed noise.
Trade-offs: While mRUCB-A and mHT-DSEE showed lower initial regret, mRUCB-Intervals (Problem B) eventually achieved zero regret growth after the active set collapsed, whereas the others continued to explore. The experiments highlight that while asymptotic rates differ, the constants associated with the coordination mechanisms (e.g., the factor of 4 vs. 2 in interval separation) significantly impact performance at moderate horizons.

Significance and Claims
The authors claim that effective decentralized learning is achievable even under significant information asymmetry and non-sub-Gaussian noise.

Shared rewards enable costless synchronization.
Observed actions provide a sufficient implicit signaling channel to compensate for the loss of shared rewards, with a signaling cost that does not scale with the horizon or the number of agents.
Full asymmetry necessitates a pre-committed schedule, incurring an additional $\log T$ cost, highlighting the value of even minimal observability.

The paper concludes that while the proposed algorithms are robust, they assume knowledge of the tail parameters $(\epsilon, v)$ . Future work is suggested to address adapting to unknown tail heaviness and deriving tighter lower bounds for the fully asymmetric case.

More like this