Paperlane

no. 11 · Monday 9 November 2026

An Efficient Synchronization Scheme for Distributed Bandits

Raymond Zhang, Henrique Miyamoto, Richard Combes and Sheng Yang

math.IT · 6 pp

Abstract

We study the problem of synchronizing two players in a \emph{distributed multi-armed bandit} setting. The probability of \emph{synchronization error} is analyzed by recasting synchronization as a \emph{communication problem}. Using a well-designed random coding ensemble, we derive error exponents for the maximum-likelihood decoder. We then introduce a \emph{universal decoder} that achieves the same error exponents as the optimal decoder. Finally, applying these results to distributed multi-armed bandits, we show an upper bound on the regret of our synchronization scheme.

comments
Accepted at IEEE ISIT2026. 3 Figures, 6 pages. Theorem 7 redrawn
fields
Information Theory
pdf ↗ page arXiv:2611.09806 ↗