arXiv (Cornell University) · 2020 · 10 citations · 0 references
EngineeringElectrical EngineeringMathematicsOptimizationStochastic ProcessesWireless CommunicationsNetwork Information TheoryReinforcement LearningStochastic ControlStochastic OptimizationStochastic ProgrammingWireless NetworksBandit AlgorithmsChannelsRegret OptimizationStochastic BanditsStochastic Network OptimizationStochastic Process AnalysisWireless Communication ChannelsWireless Networking
We consider a single-hop wireless network with sources transmitting\ntime-sensitive information to the destination over multiple unreliable\nchannels. Packets from each source are generated according to a stochastic\nprocess with known statistics and the state of each wireless channel (ON/OFF)\nvaries according to a stochastic process with unknown statistics. The\nreliability of the wireless channels is to be learned through observation. At\nevery time slot, the learning algorithm selects a single pair (source, channel)\nand the selected source attempts to transmit its packet via the selected\nchannel. The probability of a successful transmission to the destination\ndepends on the reliability of the selected channel. The goal of the learning\nalgorithm is to minimize the Age-of-Information (AoI) in the network over $T$\ntime slots. To analyze the performance of the learning algorithm, we introduce\nthe notion of AoI regret, which is the difference between the expected\ncumulative AoI of the learning algorithm under consideration and the expected\ncumulative AoI of a genie algorithm that knows the reliability of the channels\na priori. The AoI regret captures the penalty incurred by having to learn the\nstatistics of the channels over the $T$ time slots. The results are two-fold:\nfirst, we consider learning algorithms that employ well-known solutions to the\nstochastic multi-armed bandit problem (such as $\\epsilon$-Greedy, Upper\nConfidence Bound, and Thompson Sampling) and show that their AoI regret scales\nas $\\Theta(\\log T)$; second, we develop a novel learning algorithm and show\nthat it has $O(1)$ regret. To the best of our knowledge, this is the first\nlearning algorithm with bounded AoI regret.\n