Search papers, labs, and topics across Lattice.
This paper investigates multi-agent multi-armed bandit problems characterized by heavy-tailed reward distributions and varying degrees of information asymmetry. By developing robust decentralized algorithms tailored to three distinct information-asymmetry scenarios, the authors achieve regret guarantees that closely align with those of centralized approaches. Experimental results in a Pareto-distributed reward environment substantiate the theoretical claims and highlight the complexities of synchronization, coordination, and exploration in decentralized settings.
Regret guarantees for decentralized algorithms in multi-agent bandits nearly match centralized rates, even under heavy-tailed rewards and information asymmetry.
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.
