AoI-Constrained Bandit: Information Gathering over Unreliable Channels with Age Guarantees

Age-of-Information (AoI) is an application layer metric that has been widely adopted to quantify the information freshness of each information source. However, few works address the impact of probabilistic transmission failures on satisfying the harsh AoI requirement of each source, which is of critical importance in a great number of wireless-powered real-time applications. In this paper, we investigate the transmission scheduling problem of maximizing throughput over wireless channels under different time-average AoI requirements for heterogeneous information sources. When the channel reliability for each source is known as prior, the global optimal transmission scheduling policy is proposed. Moreover, when channel reliabilities are unknown, it is modeled as an AoI-constrained Multi-Armed Bandit (MAB) problem. Then a learning algorithm that meets the AoI requirement with probability 1 and incurs up to O(K\sqrt{T\log T}) accumulated regret is proposed, where K is the number of arms/information sources, and T is the time horizon. Numerical results show that the accumulated regret of our learning algorithm is strictly bounded by K\sqrt{T\log T} and outperforms the AoI-constraint-aware baseline, and the AoI requirement of every source is robustly satisfied.