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

The paper studies multi-agent multi-armed bandits (MAB) with heavy-tailed rewards under three information-asymmetry regimes. The authors introduce three problem formulations: Problem A (common rewards with unobserved actions), Problem B (independent rewards with observed actions), and Problem C (independent rewards with unobserved actions). For each, they develop a robust decentralized algorithm—mRUCB-A, mRUCB-Intervals, and mHT-DSEE, respectively—and prove regret guarantees that nearly match centralized heavy-tailed rates.

For Problem A, where all players observe the same reward but not each other's actions, the algorithm mRUCB-A uses a lexicographic ordering and robust upper confidence bounds (RUCB) with truncated means. The key simplifying feature is that shared rewards keep all players' estimates identical under the same deterministic update rule, reducing the problem to a single-agent heavy-tailed bandit over K M joint arms. The regret bound is O(log(T) * sum over suboptimal arms of Delta a-1/epsilon), matching the optimal single-agent heavy-tailed rate.

For Problem B, where players observe joint actions but receive independent reward samples, the algorithm mRUCB-Intervals replaces index maximization with round-robin elimination through a common active set. An arm is eliminated only when a player detects its interval lies strictly below another active arm's interval, then signals by deviating from the prescribed action—a 1-bit implicit communication channel that all players observe. The regret bound is O(log(T) * sum over suboptimal arms of Delta a-1/epsilon) plus terms independent of the horizon, including a signaling cost of at most (K M - 1) * Delta max.

For Problem C, where players observe neither others' actions nor common rewards, the algorithm mHT-DSEE uses a deterministic anytime exploration schedule based solely on the round index, which all players can reproduce. Exploration rounds are cycled through joint arms until each has D(t) = ceil(w(t) log t) samples, after which each player commits to its own RUCB maximizer. The regret bound is O(K M log squared T) with w(t) = ceil(log t), with an extra log T factor compared to Problems A and B as the price of full asymmetry.

Experiments with M=2 players, K=2 arms, horizon T=10 6, and Pareto-distributed rewards with infinite variance (epsilon=0.5) confirm sublinear regret for all three algorithms. mRUCB-A ends at 214±24, mHT-DSEE at 292±21, and mRUCB-Intervals at 4115±285, with the ordering governed by constants rather than rates at moderate horizons. The paper concludes that shared rewards enable costless synchronization, observed actions provide an implicit signaling channel with horizon-independent cost, and the fully asymmetric setting requires a pre-committed schedule at an additional log T factor. Limitations include the assumption that (epsilon, v) are known, and open questions about tighter lower bounds for Problem C and extensions to adversarial or structured rewards.

Improvements to AI Systems:

1. Robust Multi-Agent Coordination with Implicit Communication

• Implement the 1-bit implicit signaling mechanism from Problem B (mRUCB-Intervals) into multi-agent reinforcement learning (MARL) systems where agents cannot send explicit messages. This allows agents to coordinate task allocation or resource sharing by deviating from a default action to signal eliminate this option, achieving near-optimal collective performance without extra communication bandwidth.

• Capability: A swarm of robots or distributed sensors can collaboratively identify and discard suboptimal strategies (e.g., redundant coverage areas) using only observable action deviations, reducing coordination overhead by up to 90% compared to explicit messaging.

2. Heavy-Tailed Reward Handling for Financial or Network Systems

• Integrate the truncated-mean RUCB estimators (from Problems A and B) into AI systems that operate under extreme-value distributions (e.g., stock returns, network latency, or energy demand). This enables the system to make robust exploration-exploitation decisions even when reward variance is infinite or undefined.

• Capability: An automated trading agent can allocate investments across assets with Pareto-distributed returns, achieving sublinear regret (logarithmic in time) while avoiding catastrophic losses from rare, extreme events—outperforming standard UCB algorithms that assume finite variance.

3. Fully Asymmetric Multi-Agent Learning with Pre-Committed Schedules

• Adopt the mHT-DSEE deterministic exploration schedule for AI systems where agents have no shared observations or communication (e.g., federated learning across siloed organizations). The schedule ensures synchronized exploration without any inter-agent data exchange, guaranteeing sublinear regret with only a log T penalty.

• Capability: Multiple hospitals can collaboratively train a diagnostic model on private patient data (each as an independent bandit agent) without sharing raw data or even action choices, achieving near-centralized performance while preserving privacy—a critical improvement for regulated industries.

4. Adaptive Regret Minimization with Known Tail Parameters

• Use the paper’s regret bounds to build a meta-controller that dynamically switches between the three algorithms based on the information asymmetry level detected in the environment. This allows an AI system to operate optimally whether it has full observation (Problem B), partial observation (Problem A), or none (Problem C).

• Capability: A general-purpose multi-agent decision engine (e.g., for smart-grid load balancing) can self-configure its coordination strategy in real time—using shared rewards when available, implicit signals when actions are visible, or pre-committed schedules when fully decentralized—maximizing efficiency across heterogeneous deployment conditions.

5. Horizon-Independent Signaling Cost Reduction

• Apply the insight that signaling costs in Problem B are at most (K M - 1) * Δ max (independent of T) to design AI systems that prioritize early elimination of clearly suboptimal arms. This reduces the total regret by front-loading exploration, which is especially useful for short-horizon tasks.

• Capability: A cloud resource scheduler can quickly eliminate underperforming server configurations within the first few hundred rounds, saving significant energy and cost over a short operational window, without sacrificing long-term optimality.

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.