Remote tracking of dynamic sources under sublinear communication costs

We study the remote monitoring of multiple sensors with evolving states following a Wiener Process under communication cost. We assume that the communication cost is sublinear such that the cost decreases with the number of simultaneous state updates. Such sublinear structures emerge in various settings, such as frame aggregation, and give rise to interesting unexplored tradeoffs between: updating a smaller subset of the processes earlier at a higher cost-per-process; and updating a larger subset of them later at a lower cost-per-process. We attack this problem by first providing two competitive benchmark strategies of All-at-once and Multi-threshold policies. Then, we propose a novel strategy of MAX-k policy that not only includes the two benchmark threshold-based policies as special cases, but also improves over them by better exploiting the aforementioned tradeoff. Further, we develop the GPSO optimization technique to develop an online learning algorithm that adaptively optimizes the parameters of MAX-k policy. We demonstrate that the proposed scheme outperforms the well-known online learning algorithm based on UCB index.