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

• URL: http://arxiv.org/abs/2608.10529v1
• Date: Tue, 11 Aug 2026 06:10:42 GMT
• Title: Robust Multi-Agent Bandits with Heavy-Tailed Rewards and Information Asymmetry
• Abstract summary: We study multi-agent multi-armed bandits with heavy-tailed rewards under three information-asymmetry regimes.<n>We develop robust decentralized algorithms for each setting and derive regret guarantees that nearly match centralized heavy-tailed rates.
• Score: 1.1689657956099038
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Coordinating the Unknown Lipschitz Constant in Multiplayer Bandits [1.3700362496838856]
  We study cooperative multi-agent bandits in continuous (Lipschitz) action spaces when the Lipschitz constant is unknown.<n>We consider three information structures: (A)unobserved actions with common rewards, (B)observed actions with independent rewards, and (C)unobserved actions with independent rewards.
  arXiv  Detail & Related papers  (2026-08-11T06:06:12Z)
• On the Regularity and Fairness of Combinatorial Multi-Armed Bandit [8.61754191125565]
  This paper is inspired by two critical applications in wireless networks.<n>It's not only essential to maximize cumulative rewards but also to guarantee fairness among arms.<n>We propose a parameterized regular and fair learning algorithm to achieve these three objectives.
  arXiv  Detail & Related papers  (2025-09-15T21:08:16Z)
• Semi-Parametric Batched Global Multi-Armed Bandits with Covariates [0.48342038441006807]
  The multi-armed bandits (MAB) framework is a widely used approach for sequential decision-making.<n>We propose a novel semi-parametric framework for batched bandits with coparametrics and a shared parameter across arms.<n>Our algorithm, Batched single-Index Dynamic binning and Successive arm elimination (BIDS), employs a batched successive arm elimination strategy.
  arXiv  Detail & Related papers  (2025-03-01T17:23:55Z)
• Continuous K-Max Bandits [54.21533414838677]
  We study the $K$-Max multi-armed bandits problem with continuous outcome distributions and weak value-index feedback.<n>This setting captures critical applications in recommendation systems, distributed computing, server scheduling, etc.<n>Our key contribution is the computationally efficient algorithm DCK-UCB, which combines adaptive discretization with bias-corrected confidence bounds.
  arXiv  Detail & Related papers  (2025-02-19T06:37:37Z)
• Pure Exploration in Asynchronous Federated Bandits [57.02106627533004]
  We study the federated pure exploration problem of multi-armed bandits and linear bandits, where $M$ agents cooperatively identify the best arm via communicating with the central server. We propose the first asynchronous multi-armed bandit and linear bandit algorithms for pure exploration with fixed confidence.
  arXiv  Detail & Related papers  (2023-10-17T06:04:00Z)
• Networked Communication for Decentralised Agents in Mean-Field Games [59.01527054553122]
  We introduce networked communication to the mean-field game framework.<n>We prove that our architecture has sample guarantees bounded between those of the centralised- and independent-learning cases.<n>We show that our networked approach has significant advantages over both alternatives in terms of robustness to update failures and to changes in population size.
  arXiv  Detail & Related papers  (2023-06-05T10:45:39Z)
• DM$^2$: Distributed Multi-Agent Reinforcement Learning for Distribution Matching [43.58408474941208]
  This paper studies the problem of distributed multi-agent learning without resorting to explicit coordination schemes. Each individual agent matches a target distribution of concurrently sampled trajectories from a joint expert policy. Experimental validation on the StarCraft domain shows that combining the reward for distribution matching with the environment reward allows agents to outperform a fully distributed baseline.
  arXiv  Detail & Related papers  (2022-06-01T04:57:50Z)
• The Combinatorial Multi-Bandit Problem and its Application to Energy Management [2.236663830879273]
  We study a Combinatorial Multi-Bandit Problem motivated by applications in energy systems management. For our energy management application we propose a range of algorithms that combine exploration principles for multi-arm bandits with mathematical programming.
  arXiv  Detail & Related papers  (2020-10-30T13:42:54Z)
• Unifying Clustered and Non-stationary Bandits [50.12992652938055]
  Non-stationary bandits and online clustering of bandits lift the restrictive assumptions in contextual bandits. We propose test of homogeneity, which seamlessly addresses change detection for non-stationary bandits and cluster identification for online clustering of bandit. Rigorous regret analysis and extensive empirical evaluations demonstrate the value of our proposed solution.
  arXiv  Detail & Related papers  (2020-09-05T04:58:06Z)
• Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
  We introduce a theory for multi-armed bandits where the values are the modes of the reward distributions instead of the mean. We show in simulations that our algorithms are robust to perturbation of the arms by adversarial noise sequences.
  arXiv  Detail & Related papers  (2020-03-05T21:29:27Z)
• Incentivizing Exploration with Selective Data Disclosure [70.11902902106014]
  We propose and design recommendation systems that incentivize efficient exploration. Agents arrive sequentially, choose actions and receive rewards, drawn from fixed but unknown action-specific distributions. We attain optimal regret rate for exploration using a flexible frequentist behavioral model.
  arXiv  Detail & Related papers  (2018-11-14T19:29:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.