Multi-Player Age-of-Information Bandits: A Trekking Approach

We study the algorithmic task of scheduling communication in a decentralized manner in a multi-source, single-destination network. The sources share multiple communication channels to send updates to a common destination. The metric of interest is the cumulative Age-of-Information (AoI) of the sources. Unlike most AoI based works, we consider the setting where channel statistics are unknown to the sources and have to be learned via the feedback obtained on using those channels. In the absence of a central coordinating entity, the key challenge is to design a decentralized scheduling policy to identify the best channels while simultaneously minimizing the number of collisions between the sources. We design a policy that is effective at avoiding collisions and provide performance guarantees for the proposed policy. In addition, we compare the performance of our policy with existing approaches via simulations to demonstrate that our approach leads to a significant improvement in performance.