Regret of Age-of-Information Bandits

Santosh Fatale, Kavya Bhandari, Urvidh Narula, Sharayu Moharir, Manjesh Kumar HanawalIEEE Trans. Communications 2022 · DOI · OpenReview

Abstract

In modern networked systems such as autonomous vehicles and IoT, the freshness of information—quantified as Age-of-Information (AoI)—is critical for system performance. This paper addresses the challenge of minimizing AoI when transmitting updates over multiple communication channels with unknown success probabilities. By framing this as a Multi-Armed Bandit (MAB) problem, the authors evaluate standard and novel scheduling policies. They demonstrate that while standard agnostic policies like UCB and Thompson Sampling are order-optimal, AoI-aware policies provide superior performance by dynamically adjusting exploration based on the current age of data.

Introduction

In the era of the Internet of Things (IoT) and autonomous systems, the utility of data is often tied to its freshness. Age-of-Information (AoI) measures the time elapsed since the last successful update was generated at a source and received at a destination. Minimizing AoI is essential for real-time monitoring and control. However, in many practical scenarios, the reliability of available communication channels is not known a priori, necessitating a strategy that balances exploring new channels with exploiting known reliable ones.

Problem Formulation

The researchers from IIT Bombay model this scenario as an "AoI Bandit" problem. A source aims to send periodic updates to a monitoring station using one of $K$ available channels. Each channel $k$ has an unknown success probability $\mu_k$.

System model of a source transmitting updates over multiple unknown channels to a monitoring station.

Unlike traditional Multi-Armed Bandit (MAB) problems where a sub-optimal choice leads to a fixed loss in reward, a failure in the AoI context causes the age to grow linearly. This creates a temporal correlation where the "cost" of a mistake increases the longer the system goes without a successful update.

Scheduling Policies

The paper evaluates two primary categories of policies:

  1. AoI-Agnostic Policies: These include standard bandit algorithms like Upper Confidence Bound (UCB) and Thompson Sampling (TS). They select channels based on historical success rates without considering the current AoI.
  2. AoI-Aware Policies: The authors introduce variants such as AA-UCB and AA-TS. These policies incorporate the current AoI into their decision-making. When the AoI is low, the policy explores less certain channels; when the AoI is high, it prioritizes exploitation of the most reliable known channel to ensure a "reset" of the age.

Key Results and Theoretical Insights

The study provides a rigorous theoretical analysis of regret in AoI bandits. Regret is defined as the difference between the cumulative AoI achieved by a policy and that of an optimal policy that knows the channel success probabilities.

Comparison of regret bounds for various scheduling policies.

A significant finding is that standard agnostic policies (UCB and TS) achieve a regret of $O(K \log T)$, which matches the lower bound of $\Omega(K \log T)$ for any consistent policy. This proves that these "blind" algorithms are order-optimal. However, simulation results show that AoI-aware policies, particularly AA-TS, significantly outperform agnostic ones in practice, especially in "hard" environments where channel probabilities are similar.

The analysis also highlights that policies designed for queueing systems, such as Q-UCB, exhibit a higher regret scaling of $O(K \log^4 T)$, making them less efficient for direct AoI minimization.

Conclusion

This research establishes a foundational framework for applying bandit algorithms to information freshness. While standard exploration-exploitation strategies are theoretically sound, incorporating the current state of the system (the AoI) allows for more robust performance. Future work includes extending these models to multi-source networks and non-stationary channel conditions.

Summary updated

Abstract

We consider a system with a single source that measures/tracks a time-varying quantity and periodically attempts to report these measurements to a monitoring station. Each update from the source has to be scheduled on one of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$K$ </tex-math></inline-formula> available communication channels. The probability of success of each attempted communication is a function of the channel used. This function is unknown to the scheduler. The metric of interest is the Age-of-Information (AoI), formally defined as the time elapsed since the destination received the recent most update from the source. We model our scheduling problem as a variant of the multi-arm bandit problem with communication channels as arms. We characterize a lower bound on the AoI regret achievable by any policy and characterize the performance of UCB, Thompson Sampling, and their variants. Our analytical results show that UCB and Thompson sampling are order-optimal for AoI bandits. In addition, we propose novel policies which, unlike UCB and Thompson Sampling, use the current AoI to make scheduling decisions. Via simulations, we show the proposed AoI-aware policies outperform existing AoI-agnostic policies.
BibTeX
@article{fatale2022regret,
  author = {Santosh Fatale and Kavya Bhandari and Urvidh Narula and Sharayu Moharir and Manjesh Kumar Hanawal},
  title = {{Regret of Age-of-Information Bandits}},
  journal = {IEEE Trans. Communications},
  year = {2022},
  doi = {10.1109/tcomm.2021.3118037},
}
Figure