Research map / Bandits and online learning / Multi-armed bandits
Heterogeneous Multi-Agent Bandits with Parsimonious Hints
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.
Studies heterogeneous multi-agent multi-armed bandits with collisions where agents can query cheap hints, proposing centralized GP-HCLA and decentralized HD-ETC/EBHD-ETC algorithms with time-independent regret and sub-linear hint complexity.
Problem
Heterogeneous multi-agent multi-armed bandits with collisions suffer large regret; the paper asks how low-cost hints can reduce regret to time-independent levels while minimizing the number of queried hints, in both centralized and decentralized settings.
Approach
Introduces hint queries into heterogeneous MA2B: a central decision maker uses kl-UCB indices at the edge level with Hungarian matching and projects hint graphs onto a small set of covering matchings; decentralized agents use round-robin hint querying within explore-then-commit epochs with collision-based communication.
Key results
- GP-HCLA achieves O(M^4K) time-independent regret with O(MK log T) hints, matching the stated lower bound on hint complexity.
- HD-ETC and EBHD-ETC achieve O(M^3K^2) regret with O(M^3K log(MT)) hints and O(log T) communication, with HD-ETC requiring knowledge of the minimum gap and EBHD-ETC not.
- Numerical simulations show the hint-augmented algorithms significantly reduce regret compared to Beacon, and centralized algorithms need fewer hints than the decentralized ones at similar regret.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use edge-level statistics instead of matching-level statistics | HCLA · HMA2B centralized | time-independent regret: O\left(MK^{2M}\right) -> O\left(M^4K\right) | Helped |
| add projection of hint inquiries onto covering matchings | G-HCLA · HMA2B centralized | hint complexity: O\left(\frac{M^2K \log T}{\Delta^{\mathrm{kl}}}\right) -> O\left(\frac{MK \log T}{\Delta^{\mathrm{kl}}}\right) | Helped |
| remove projection from hint inquiries (ablation) | GP-HCLA · HMA2B centralized | hint complexity: O\left(\frac{MK \log T}{\Delta^{\mathrm{kl}}}\right) -> O\left(\frac{M^2K \log T}{\Delta^{\mathrm{kl}}}\right) | Hurt |
| use edge-level statistics rather than separate statistics for each matching | HCLA · HMA2B centralized | hint complexity: O\left(MK^M \log T\right) -> O\left(MK \log T\right) | Helped |
| replace the known-gap stopping time with edge elimination, removing the minimum-gap knowledge requirement | HD-ETC · HMA2B decentralized | hint complexity | Hurt |
| replace the known-gap stopping time with edge elimination, removing the minimum-gap knowledge requirement | HD-ETC · HMA2B decentralized | regret | Hurt |
| use centralized algorithms instead of decentralized algorithms | HMA2B algorithms · HMA2B | hint-query efficiency | Helped |
Limitations
- Assumes accurate hints sampled from the same distribution as rewards
- Decentralized algorithms require communication via intentional collisions and knowledge of unique ranks; HD-ETC needs minimum gap knowledge
- Analysis restricted to Bernoulli rewards and unique optimal matching; experiments are small (M=K=4)
Experimental setup
Metrics: regret number of queried hints communication regret
Baselines: HCLA G-HCLA HD-ETC EBHD-ETC Beacon
Builds on: HCLA kl-UCB Beacon Hungarian algorithm
Closest papers by meaning
- Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with Heterogeneous Rewards (NeurIPS 2023 · similarity 0.89)
- Statistical and Computational Trade-off in Multi-Agent Multi-Armed Bandits (NeurIPS 2023 · similarity 0.89)
- Distributed Multi-Agent Bandits Over Erdős-Rényi Random Networks (NeurIPS 2025 · similarity 0.89)
- Oracle-Efficient Combinatorial Semi-Bandits (NeurIPS 2025 · similarity 0.88)
- Federated Combinatorial Multi-Agent Multi-Armed Bandits (ICML 2024 · similarity 0.87)
- Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling on Sparse Hypergraphs (AAAI 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.