Research map / Multi-agent systems and games / Games and equilibria
Adaptive Sample Sharing for Multi Agent Linear Bandits
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes BASS, a multi-agent linear bandit algorithm that adaptively shares samples between agents using an anisotropic (Mahalanobis) ellipsoid-separation test, with no cluster assumption, and proves separation-time and regret bounds.
Problem
Regret minimization in heterogeneous multi-agent linear stochastic bandits, where agents must decide when sharing observations reduces variance more than it introduces bias from differing bandit parameters.
Approach
Decides collaboration between agent pairs via a Mahalanobis-based ellipsoid separation test (gamma-relaxed function Psi) built on the design matrices, so sharing stops once parameter bias exceeds the current uncertainty in the directions of large reward, without assuming a cluster structure.
Key results
- On synthetic environment with Delta_min=0.2, BASS (delta=0.1) reaches cumulative regret 1096.8 vs 6100.7 for independent agents and 5765.5 for DynUCB (Oracle 318.5).
- On MovieLens, BASS (delta=0.1) attains cumulative regret 10273.2 vs 11825.2 for Ind and 11504.2 for CLUB.
- BASS achieves the best clustering F1 (0.7 to 0.9) in synthetic settings, while CLUB, SCLUB and CMLB score 0.0 in most settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use BASS instead of independent agents (Ind) | Multi-agent linear bandits · Synthetic (Δminθ,2=0.2) | cumulative regret: 6100.7 +/- 468.4 -> 1096.8 +/- 411.9 | Helped |
| Use BASS instead of independent agents (Ind) | Multi-agent linear bandits · Synthetic (Δminθ,2=1.27) | cumulative regret: 5465.0 +/- 352.7 -> 1563.2 +/- 750.7 | Helped |
| Use BASS instead of SCLUB (γ=1.0) | Multi-agent linear bandits · MovieLens | cumulative regret: 11085.5 +/- 701.3 -> 10273.2 +/- 686.3 | Helped |
| Use BASS instead of CLUB (γ=0.1) | Multi-agent linear bandits · Yahoo | cumulative regret: 13321.5 +/- 4228.8 -> 12456.0 +/- 2096.1 | Helped |
| Use BASS (δ=0.1) instead of DynUCB | Multi-agent linear bandits · Synthetic (Δminθ,2=0.2) | F1 score: 0.7 +/- 0.1 -> 0.7 +/- 0.0 | Mixed |
| Use BASS (δ=0.1) instead of DynUCB | Multi-agent linear bandits · Synthetic (Δminθ,2=1.27) | F1 score: 0.9 +/- 0.2 -> 0.9 +/- 0.0 | No clear effect |
Surprising findings
- Most cluster-based baselines (CLUB, SCLUB, CMLB) recover the cluster structure poorly, with F1 near 0 in most synthetic settings.
- Under the synthetic setting with Delta_min=0.2, CMLB with gamma=Delta/2 performs no better than independent agents.
Limitations
- Theoretical bounds rely on synchronous pulling and sub-Gaussian noise assumptions; the algorithm is analyzed for two-agent pairs and extended to N agents by pairwise consideration.
- Empirical evaluation uses a single synthetic setting with M=3 clusters and a few real datasets; the paper notes the clustering error bound is loose (exponent depends on gamma^2 R^2 - 1).
Experimental setup
Datasets: MovieLens Yahoo!
Benchmarks: synthetic clustered linear bandit environment MovieLens ranking Yahoo! ranking
Metrics: cumulative pseudo-regret clustering F1 score
Baselines: Ind Oracle DynUCB CLUB SCLUB CMLB
Builds on: OFUL CLUB overlapping ellipsoid test (Gentile et al.)
Closest papers by meaning
- Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with Heterogeneous Rewards (NeurIPS 2023 · similarity 0.89)
- Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Bounds (NeurIPS 2022 · similarity 0.89)
- Collaborative Multi-Agent Heterogeneous Multi-Armed Bandits (ICML 2023 · similarity 0.89)
- Replication-proof Bandit Mechanism Design with Bayesian Agents (AAAI 2025 · similarity 0.88)
- Distributed Multi-Agent Bandits Over Erdős-Rényi Random Networks (NeurIPS 2025 · similarity 0.88)
- Federated Combinatorial Multi-Agent Multi-Armed Bandits (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.