← All papers

Pooled Exploration Closes the Distributed Linear-Bandit Gap

Abstract

Distributed adversarial linear bandits have two sources of difficulty. A network needs time to mix information, while bandit feedback needs enough collective exploration to identify a $d$-dimensional loss. The best known finite-action guarantee multiplies both costs by $d$. Its lower bound only multiplies the bandit cost by $d$, leaving a factor $\sqrt d$ gap in the communication term. We close this gap. The key is that exploration should stabilize the pooled block estimate, not every local estimate separately. An exponential-potential argument with conditional Bernstein control allows a spanner exploration rate of order $\eta d/N$ across $N$ agents. The previous pointwise analysis requires order $\eta Bd$, where $B$ is the communication block length. A separate leverage lemma shows that the tiny uniform floor already present in the algorithm keeps every communicated spanner coordinate polynomially bounded, so reducing exploration does not weaken gossip. For $K$ actions spanning dimension $r\le d$, spectral gap $\rho$, and horizon $T$, our algorithm communicates $O(r)$ scalars per agent and round and has per-agent regret $\widetilde O \left( \sqrt{\bigl(\rho^{-1/2}+r/N\bigr)T\log K} \right).$ This matches the known lower bound up to logarithmic factors and resolves the finite-action linear-bandit gap. The proof also gives a general mini-batch EXP2 theorem showing that independent agents pool both variance and the exploration needed for exponential stability.

Keywords: linear bandits, distributed learning, exploration, regret, collaborative bandits, communication

Full text (PDF) · source repository · doi:10.5281/zenodo.21698612