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

Weiwei WuarXiv 2021 · arXiv

TL;DR

This paper tackles the challenge of efficiently gathering information from multiple sources over unreliable wireless channels while ensuring that the information remains fresh enough for real-time applications. They propose novel algorithms, MOSS and MOSS-CB, that guarantee Age-of-Information (AoI) constraints are met and maximize data throughput, even when channel reliability is unknown.

What Problem Does This Paper Address?

In many modern applications like disaster management, aerial surveillance, and smart grids, data needs to be collected from various sources in real-time. The "freshness" of this data is crucial, and it's quantified by the Age-of-Information (AoI) metric, which measures the time since the last successful data update. However, wireless channels are inherently unreliable, meaning data packets can be lost, potentially leading to unbounded AoI. Furthermore, different sources have varying requirements for information freshness and different channel reliabilities. Existing research often focuses on minimizing overall AoI or assumes perfect channels, leaving a gap in addressing the problem of guaranteeing per-source AoI constraints under probabilistic transmission failures with unknown channel conditions. This paper aims to fill that gap by developing scheduling policies that maximize data throughput while robustly satisfying heterogeneous AoI requirements over unreliable channels.

Methods

The paper proposes two main approaches:

  • MOSS (Maximum Optimal-Source Sampling Probability): For the scenario where channel reliability is known a priori, MOSS is a stationary randomized sampling policy. It intelligently assigns sampling probabilities to sources: sub-optimal sources (with less reliable channels) receive the minimum probability needed to meet their AoI constraints, while the remaining probability is allocated to the most reliable source to maximize throughput. This policy is proven to be globally optimal.
  • MOSS-CB (MOSS with Confidence Bound): When channel reliability is unknown, the problem is framed as an AoI-constrained Multi-Armed Bandit (MAB) problem. MOSS-CB adapts MOSS by using confidence bounds to estimate channel reliability. It employs an Upper Confidence Bound (UCB) for exploration and a Lower Confidence Bound (LCB) for determining sampling probabilities. A key innovation is the introduction of a "fallback policy" (Least-pull-Arm First) that is activated when the estimated channel reliabilities are too unreliable to guarantee the AoI constraints. This ensures that the algorithm eventually enters a "SPO-MF" (SPO-is-Mostly-Feasible) phase where the AoI constraints are met with high probability.

Datasets

Not discussed in the paper. The evaluation is based on simulated scenarios with defined parameters for channel reliability and AoI requirements.

Key Insights and Ideas

  • AoI as a Constraint, Not Just an Objective: The paper shifts the focus from simply minimizing AoI to guaranteeing it, which is critical for real-time decision-making.
  • Balancing Throughput and AoI: The core challenge is to maximize data collection while ensuring information freshness, a trade-off that MOSS and MOSS-CB effectively manage.
  • The Power of Confidence Bounds for Learning: Using UCB for exploration and LCB for sampling probability in MOSS-CB is a clever way to learn about unknown channels while simultaneously satisfying constraints.
  • Fallback Mechanism is Crucial: The introduction of the LAF fallback policy in MOSS-CB is essential for handling the initial uncertainty of unknown channel reliabilities and ensuring eventual feasibility.
  • Feasibility Condition: The paper derives a critical condition (Equation 7) that must be met for a problem instance to be feasible, providing a theoretical boundary for solvable scenarios.

Key Results

  • MOSS: Proven to be the globally optimal policy for the known channel reliability case.
  • MOSS-CB:
    • Guarantees satisfaction of AoI constraints with probability 1.
  • Achieves an accumulated regret upper-bounded by $O(K\sqrt{T}\log T)$, where $K$ is the number of sources and $T$ is the time horizon.
  • Outperforms baseline algorithms (UCB1 and MAGF) in simulations, demonstrating robust AoI satisfaction and lower accumulated regret.
  • Numerical results show MOSS-CB's accumulated regret is strictly bounded by $K\sqrt{T}\log T$.

Limitations and Future Work

  • Limitations:
    • The analysis for MOSS-CB's feasibility and regret bound primarily relies on the "clean event" assumption, where estimated channel reliabilities are within a certain bound of the true values. While the probability of this event is high, it's not absolute.
  • The paper assumes a single base station acting as a scheduler.
  • Future Work:
    • Consideration of combinatorial-arm scenarios.
  • Incorporating channel availability or sleeping-arm scenarios with source availability.
  • Extending to more complex network topologies and scenarios.

Summary updated

Abstract

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.
BibTeX
@misc{wu2021aoi,
  author = {Weiwei Wu},
  title = {{AoI-Constrained Bandit: Information Gathering over Unreliable Channels with Age Guarantees}},
  year = {2021},
  eprint = {2112.02786},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.02786},
}
Figure