Heterogeneous Multi-Agent Bandits with Parsimonious Hints
This work addresses a multi-agent bandit problem with hints for scenarios like distributed sensing or resource allocation, but it is incremental as it extends existing methods to incorporate hints and heterogeneous agents.
The paper tackles the problem of heterogeneous multi-agent bandits with hints, where agents aim to maximize total utility by querying minimal hints to avoid pulling arms, achieving time-independent regret. The centralized algorithm GP-HCLA achieves O(M^4K) regret with O(MK log T) hints, while decentralized algorithms HD-ETC and EBHD-ETC achieve O(M^3K^2) regret with O(M^3K log T) hints, with lower bounds established for optimality.
We study a hinted heterogeneous multi-agent multi-armed bandits problem (HMA2B), where agents can query low-cost observations (hints) in addition to pulling arms. In this framework, each of the $M$ agents has a unique reward distribution over $K$ arms, and in $T$ rounds, they can observe the reward of the arm they pull only if no other agent pulls that arm. The goal is to maximize the total utility by querying the minimal necessary hints without pulling arms, achieving time-independent regret. We study HMA2B in both centralized and decentralized setups. Our main centralized algorithm, GP-HCLA, which is an extension of HCLA, uses a central decision-maker for arm-pulling and hint queries, achieving $O(M^4K)$ regret with $O(MK\log T)$ adaptive hints. In decentralized setups, we propose two algorithms, HD-ETC and EBHD-ETC, that allow agents to choose actions independently through collision-based communication and query hints uniformly until stopping, yielding $O(M^3K^2)$ regret with $O(M^3K\log T)$ hints, where the former requires knowledge of the minimum gap and the latter does not. Finally, we establish lower bounds to prove the optimality of our results and verify them through numerical simulations.