论文标题
分布式假设测试和在有限的时间内通过有限的沟通来进行社会学习
Distributed Hypothesis Testing and Social Learning in Finite Time with a Finite Amount of Communication
论文作者
论文摘要
我们考虑了分布式假设检验（或社会学习）的问题，在该问题基于每个代理商收到的一系列随机信号基于有限的假设，以试图从有限的假设中识别世界的真实状态。有关此问题的先前工作提供了分布式算法，以确保对真实状态的渐近学习，并采取相应的努力来提高学习速度。在本文中，我们首先认为人们可以很容易地修改现有的渐近学习算法，以使学习能够在有限的时间内，有效地产生任意的较大（渐近）率。然后，我们为有限时间学习提供了一种简单的算法，该算法仅要求代理在每个时间步长以其邻居（等于可能的假设数量）交换二进制向量（长度等于可能的假设数量）。最后，我们表明，如果代理知道网络的直径，则可以对我们的算法进行进一步修改，以允许所有代理学习真实状态并在有限的时间步长以后停止向其邻居传输。
We consider the problem of distributed hypothesis testing (or social learning) where a network of agents seeks to identify the true state of the world from a finite set of hypotheses, based on a series of stochastic signals that each agent receives. Prior work on this problem has provided distributed algorithms that guarantee asymptotic learning of the true state, with corresponding efforts to improve the rate of learning. In this paper, we first argue that one can readily modify existing asymptotic learning algorithms to enable learning in finite time, effectively yielding arbitrarily large (asymptotic) rates. We then provide a simple algorithm for finite-time learning which only requires the agents to exchange a binary vector (of length equal to the number of possible hypotheses) with their neighbors at each time-step. Finally, we show that if the agents know the diameter of the network, our algorithm can be further modified to allow all agents to learn the true state and stop transmitting to their neighbors after a finite number of time-steps.
