Multi-Agent Lipschitz Bandits

Technical Summary: Multi-Agent Lipschitz Bandits

Problem Statement
This paper addresses the decentralized, cooperative multi-player stochastic bandit problem over a continuous, Lipschitz-structured action space. The setting involves $N$ agents operating in a shared environment $X = [0, 1]^d$ without direct communication. The mean reward function $\mu: X \to [0, 1]$ is unknown but assumed to be $L$-Lipschitz continuous.

A critical constraint is the "hard collision" model: if two or more agents select actions within the same region (cell) simultaneously, all colliding agents receive zero reward and no observation. The objective is to maximize the collective cumulative reward over a time horizon $T$. The challenge lies in the confluence of three factors: the continuous action space (which renders naive discretization intractable), the hard collision constraint (requiring coordination), and the lack of communication channels.

Methodology
The authors propose a modular, communication-free, four-phase protocol designed to decouple the coordination problem from the learning problem. The strategy relies on a partition-based collision model where the action space is discretized into $K$ hypercubic cells of side length $h$.

1. Phase I: Coarse Identification:
   All agents perform uniform random sampling of cell centers for a fixed duration $T_0$. Despite the high probability of collisions, this phase ensures that, with high probability, every agent obtains sufficient non-colliding observations to construct coarse confidence bounds on the maximum value of every cell. This phase serves to prune the search space by eliminating suboptimal cells.

2. Phase II: Maxima-Directed Refinement ("Local Peek"):
   To address the "center-vs-maximum" pathology—where a cell's center value is a poor proxy for its true supremum due to sharp peaks near boundaries—agents perform a localized exploration within candidate cells. They sample from a fine grid ($\eta$-net) inside the remaining candidate cells to build high-resolution confidence brackets on the true cell maxima $\mu^*(C)$. This allows agents to identify the top-$N$ cells based on their true suprema rather than their centers.

3. Phase II 1/2: Decentralized Seating (Musical Chairs):
   Once agents agree on a set of $N$ target cells (either through an $\epsilon$-uniqueness condition or public scheduling), they must assign themselves to these cells without conflict. The authors analyze a practical version of the "Musical Chairs" protocol where agents do not know which cells are occupied. Unseated agents repeatedly sample from the target set until they land on an unoccupied cell. The analysis shows this process completes in expected $O(N)$ time.

4. Phase III: Within-Cell Optimization:
   Once seated, the problem factorizes into $N$ independent single-player Lipschitz bandit problems. Each agent runs a standard near-optimal algorithm (e.g., Zooming) confined to their assigned cell for the remainder of the horizon.

Key Contributions

• First End-to-End Solution: This work provides the first principled solution for decentralized multi-player bandits in continuous domains with hard collisions.
• Maxima-Directed Identification: The authors introduce a novel identification phase that performs a "local peek" to bracket true cell suprema, provably avoiding the biases inherent in center-based ranking strategies.
• Decoupling Coordination and Learning: The protocol separates the coordination cost from the learning cost. The coordination phases (I, II, and seating) incur a cost that is independent of the time horizon $T$ (for fixed confidence) or only polylogarithmic in $T$ (in expected regret).
• Gap-Free Guarantees: Under a public coverage/scheduling assumption and a near-optimality-dimension condition, the authors derive a gap-free regret bound, ensuring robustness even when reward gaps between cells are zero.
• Extension to Distance-Threshold Models: The framework is extended to general distance-threshold collision models by mapping the problem to a set of "safe balls" derived from an $r$-packing, ensuring inter-agent separation.

Results and Regret Bounds
The paper establishes the following regret guarantees, where $d$ is the dimension of the action space:

• Consensus Regime: Under an $\epsilon$-uniqueness condition (a sufficient gap between the $N$-th and $(N+1)$-th best cells), the expected cumulative regret is bounded by:
  $$\mathbb{E}[R(T)] \leq \underbrace{O(N(T_0 + T_1) + N^2)}_{\text{Coordination Cost}} + \underbrace{\tilde{O}\left(N (Lh)^{\frac{d}{d+2}} T^{\frac{d+1}{d+2}}\right)}_{\text{Learning Cost}}$$
  The dominant learning term matches the optimal single-player Lipschitz rate of $\tilde{O}(T^{(d+1)/(d+2)})$. The coordination cost is horizon-independent for fixed confidence.

• Gap-Free Regime: Without assuming a reward gap, the algorithm achieves an expected regret of $\tilde{O}(N (Lh)^{\frac{d}{d+2}} T^{\frac{d+1}{d+2}})$ by running the protocol in epochs with dynamically adjusted precision.

• Lower Bound: The authors prove a matching minimax lower bound of $\Omega(N (Lh)^{\frac{d}{d+2}} T^{\frac{d+1}{d+2}})$, demonstrating that the $T^{(d+1)/(d+2)}$ dependence cannot be improved in these regimes. This confirms that decentralization and collisions do not worsen the core statistical difficulty compared to the single-player case.

Significance
The paper claims to provide the first end-to-end guarantees for multi-player bandits in continuous domains. Its primary significance lies in demonstrating that the coordination overhead in a decentralized setting can be isolated and made independent of the time horizon, allowing the collective system to achieve the same asymptotic learning rate as a single optimal agent. The work highlights that with a maxima-directed search strategy, the subtle challenges of continuous action spaces (specifically the center-vs-maximum bias) can be resolved without communication, enabling efficient cooperative exploration in resource-contending environments.