On the Performance of Social Learning

Decentralized decision-making (a.k.a. social learning) deals with a group of agents, connected according to a graph, which cooperate to form their beliefs about some hypotheses of interest. Under mild technical conditions regarding the graph connectivity and the identifiability of the statistical model, the belief of each agent ultimately places all the probability mass on the true hypothesis when sufficient time to learn is granted. Less is known as regards the evaluation of the learning performance. One criterion that has been proposed is the rejection rate, i.e., the rate at which the belief about the wrong hypotheses converges to zero. We show in this work that this metric is not appropriate, since it leads to the paradoxical conclusion that the optimal Bayesian decision rule can be defeated by other rules. In contrast, we show that proper performance measures are the error probability and the error exponent, namely, the rate at which the error probability converges to zero. We compare different schemes in terms of these metrics, establishing useful connections between decentralized implementations and the optimal Bayesian system. Several interesting phenomena emerge. For example, we show that traditional social learning can be sensitive to the initial state and that the recently proposed doubly Non-Bayesian (NB2) learning scheme solves this issue.