Aging Wireless Bandits: Regret Analysis and Order-Optimal Learning Algorithm
Aging Wireless Bandits: Regret Analysis and Order-Optimal Learning Algorithm
复制标题
DOI：
10.23919/wiopt52861.2021.9589673
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
Eray Unsal Atay;I. Kadota;E. Modiano
中科院分区：
文献类型：
--
作者：
Eray Unsal Atay;I. Kadota;E. Modiano
我们考虑一个单跳无线网络的源发送时间敏感的信息到目的地在多个不可靠的信道。来自每个源的分组根据具有已知统计的随机过程生成，并且每个无线信道的状态（开/关）根据具有未知统计的随机过程而变化。无线信道的可靠性是通过观察来了解的。在每个时隙，学习算法选择单个对（源、信道），并且所选择的源尝试经由所选择的信道发送其分组。成功传输到目的地的概率取决于所选信道的可靠性。学习算法的目标是在T个时隙上最小化网络中的信息量（AoI）。为了分析其性能，我们引入了AoI遗憾的概念，这是所考虑的学习算法的预期累积AoI和已知先验信道可靠性的Genie算法的预期累积AoI之间的差异。AoI-regret捕获由于必须学习T个时隙上的信道的统计而引起的惩罚。结果是双重的：首先，我们考虑使用已知的随机多臂强盗问题的解决方案的学习算法（例如，贪婪，上置信界，和汤普森采样），并证明其AoI后悔尺度为Θ（log T）; 2其次，我们开发了一种新的学习算法，并证明其具有O（1）后悔。据我们所知，这是第一个有界AoI后悔的学习算法。
We consider a single-hop wireless network with sources transmitting time-sensitive information to the destination over multiple unreliable channels. Packets from each source are generated according to a stochastic process with known statistics and the state of each wireless channel (ON/OFF) varies according to a stochastic process with unknown statistics. The reliability of the wireless channels is to be learned through observation. At every time-slot, the learning algorithm selects a single pair (source, channel) and the selected source attempts to transmit its packet via the selected channel. The probability of a successful transmission to the destination depends on the reliability of the selected channel. The goal of the learning algorithm is to minimize the Age-of-Information (AoI) in the network over T time-slots. To analyze its performance, we introduce the notion of AoI-regret, which is the difference between the expected cumulative AoI of the learning algorithm under consideration and the expected cumulative AoI of a genie algorithm that knows the reliability of the channels a priori. The AoI-regret captures the penalty incurred by having to learn the statistics of the channels over the T time-slots. The results are two-fold: first, we consider learning algorithms that employ well-known solutions to the stochastic multi-armed bandit problem (such as ϵ-Greedy, Upper Confidence Bound, and Thompson Sampling) and show that their AoI-regret scales as Θ(log T); second, we develop a novel learning algorithm and show that it has O(1) regret. To the best of our knowledge, this is the first learning algorithm with bounded AoI-regret.