Peer-to-Peer Non-Bayesian Learning in Finite Time with a Finite Amount of Communication
Shreyas Sundaram, Aritra Mitra · 2022 IEEE 61st Conference on Decision and Control (CDC) · 2022
We consider the problem of distributed non-Bayesian learning (or hypothesis testing) where a group of agents interacts over a peer-to-peer network 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. Furthermore, we show that such finite-time learning can be achieved via a simple algorithm 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.