分布式多臂老虎机的一种高效同步方案
An Efficient Synchronization Scheme for Distributed Bandits
Raymond Zhang, Henrique Miyamoto, Richard Combes, Sheng Yang
AI 速读 基于摘要
该论文将分布式多臂老虎机中两名玩家的同步问题建模为通信问题，用随机编码集合与最大似然解码分析同步错误指数，并提出达到相同错误指数的通用解码器，进而给出同步方案的遗憾上界。
cs.IT
查看原文摘要
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.