Efficient synchronization method cuts errors in distributed decision making

An Efficient Synchronization Scheme for Distributed Bandits

Information Theory

Summary

When two decision makers work separately but want to stay coordinated, errors can happen because they don’t communicate perfectly. The authors treat this coordination problem like sending messages over a noisy channel and design a way to reduce mistakes. They provide mathematical guarantees on how fast errors drop with their approach. Their method also helps keep the overall decision quality high when working with multiple options.

What this means in practice

Authors

Raymond Zhang, Henrique Miyamoto, Richard Combes, Sheng Yang

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.