Aging Wireless Bandits: Regret Analysis and Order-Optimal Learning Algorithm
| Autor: | Igor Kadota, Eray Unsal Atay, Eytan Modiano |
|---|---|
| Přispěvatelé: | Atay, Eray Unsal |
| Rok vydání: | 2021 |
| Předmět: |
Computer Science::Machine Learning
Wireless network Network packet Stochastic process Wireless ad hoc network Computer science Reliability (computer networking) Age of Information Regret Computer Science::Networking and Internet Architecture Learning Multi-armed bandits Wireless networks Thompson sampling Algorithm Computer Science::Information Theory Communication channel |
| Zdroj: | WiOpt International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt) |
| DOI: | 10.23919/wiopt52861.2021.9589673 |
| Popis: | Conference Name: 2021 19th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt) Date of Conference: 18-21 October 2021 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|