Sending Timely Status Updates through Channel with Random Delay via Online Learning

In this work, we study a status update system with a source node sending timely information to the destination through a channel with random delay. We measure the timeliness of the information stored at the receiver via the Age of Information (AoI), the time elapsed since the freshest sample stored at the receiver is generated. The goal is to design a sampling strategy that minimizes the total cost of the expected time average AoI and sampling cost in the absence of transmission delay statistics. We reformulate the total cost minimization problem as the optimization of a renewal-reward process, and propose an online sampling strategy based on the Robbins-Monro algorithm. Denote K to be the number of samples we have taken. We show that, when the transmission delay is bounded, the expected time average total cost obtained by the proposed online algorithm converges to the minimum cost when K goes to infinity, and the optimality gap decays with rate ${\mathcal{O}}$(ln K/K). Simulation results validate the performance of our proposed algorithm.