Research map / Bandits and online learning / Multi-armed bandits
Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling on Sparse Hypergraphs
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 epsilon-MATS, a variant of multi-agent Thompson sampling on hypergraph-structured bandits that samples posteriors only with probability epsilon (greedy otherwise), and proves the first frequentist regret bound for MATS-type algorithms with a near-matching lower bound for sparse hypergraphs.
Problem
Multi-agent multi-armed bandits where agents are factored into overlapping groups (a hypergraph) and the joint reward is a sum of local hyperedge rewards; existing MATS has only a Bayesian regret bound and no frequentist bound, and is computationally costly.
Approach
Combine MATS local-arm Thompson sampling with probability epsilon and greedy empirical-mean selection otherwise; analyze regret at the level of local arms via partitioning suboptimal joint arms by shared local arms, and use log T variance inflation plus a conditioning argument to get a sqrt(T) worst-case bound whose dependence on the number of groups is C^rho/epsilon^rho.
Key results
- Theorem gives worst-case regret of order rho*sqrt(((C/epsilon)^rho + L) T log^2(T L)), with L the number of local arms, matching the Omega(sqrt(L T/rho)) lower bound up to constants for sparse hypergraphs.
- In 0101-Chain experiments, regret decreases as epsilon falls from 1 to 0.1, and epsilon=0.1 is used as best setting; regret rises for epsilon below 0.1.
- epsilon-MATS outperforms MATS, MAUCE and random policy in regret and reduces runtime relative to MATS (epsilon=1) when epsilon is small.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Reduce ε from 1 (MATS) to 0.1 (ablation) | ε-MATS · Bernoulli 0101-Chain and Poisson 0101-Chain | cumulative regret | Helped |
| Reduce ε below 0.1 (ablation) | ε-MATS · Bernoulli 0101-Chain and Poisson 0101-Chain | cumulative regret | Hurt |
| Reduce ε (ablation) | ε-MATS · Bernoulli 0101-Chain and Poisson 0101-Chain | runtime | Helped |
| Use ε-MATS with ε=0.1 instead of MATS (ε=1) | MAMAB benchmarks · Bernoulli 0101-Chain and Poisson 0101-Chain | regret | Helped |
| Use variable elimination instead of naive search over joint arms | ε-MATS · Hypergraph MAMAB | computational complexity: O(A) -> O(\localArmSize ) | Helped |
Surprising findings
- epsilon-MATS often outperforms vanilla MATS empirically even though the worst-case bound for MATS is slightly better.
Limitations
- Worst-case bound has exponential C^rho dependence on the number of groups, near-optimal only for sparse hypergraphs.
- Worst-case bound for epsilon-MATS is slightly worse than MATS.
- Analysis restricted to worst-case regime with subgaussian rewards.
Experimental setup
Datasets: Bernoulli 0101-Chain Poisson 0101-Chain Gem Mining Wind Farm Control
Benchmarks: Bernoulli 0101-Chain Poisson 0101-Chain Gem Mining Wind Farm Control
Metrics: cumulative regret runtime ratio
Baselines: MATS MAUCE Random
Builds on: Multi-agent Thompson sampling (MATS) Thompson sampling MAUCE
Closest papers by meaning
- Statistical and Computational Trade-off in Multi-Agent Multi-Armed Bandits (NeurIPS 2023 · similarity 0.91)
- Distributed Multi-Agent Bandits Over Erdős-Rényi Random Networks (NeurIPS 2025 · similarity 0.90)
- On Interpolating Experts and Multi-Armed Bandits (ICML 2024 · similarity 0.88)
- Federated Combinatorial Multi-Agent Multi-Armed Bandits (ICML 2024 · similarity 0.87)
- Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox (NeurIPS 2024 · similarity 0.87)
- Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents (ICML 2025 · 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.