Distributed online learning of the shortest path under unknown random edge weights

We consider the distributed shortest path problem in an undirected graph where the edge weights are random variables with unknown distributions. The objective is to design a distributed online learning algorithm to find the shortest path from a source node to a destination node where each node only knows its neighbors but not the entire network topology. The performance of the learning algorithms is measured by regret defined as the additional cost incurred over a time horizon of length T when compared to a centralized shortest path algorithm carried out under known edge weight distributions. We propose a distributed learning algorithm that achieves a regret logarithmic with the number of packets and polynomial with the network size. The same order with time and network size holds for the message complexity of the proposed algorithm. This result finds applications in cognitive radio and ad hoc networks under unknown and dynamic communication environments.