arXiv:2611.09806 · v1

An Efficient Synchronization Scheme for Distributed Bandits

首次提交 2026-11-07 01:55

版本更新 2026-11-07 01:55

雷达观测 2026-11-09 13:22

摘要

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.

作者备注：Accepted at IEEE ISIT2026. 3 Figures, 6 pages. Theorem 7 redrawn