# Minimizing Queue Length Regret for Arbitrarily Varying Channels

arXiv: https://arxiv.org/abs/2501.13551 · HTML: https://mlsanity.com/paper/2501.13551/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 21 references that are in the map.
- First posted on arXiv 23 Jan 2025.

## Builds on (most cited first, 5 of 5)

- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [Dynamic channel selection in wireless communications via a multi-armed bandit algorithm using laser chaos time series](https://mlsanity.com/paper/1909.03629/) (2019)
- [Joint Channel Selection and Power Control in Infrastructureless Wireless Networks: A Multi-Player Multi-Armed Bandit Framework](https://mlsanity.com/paper/1407.5447/) (2014)
- [A General 3D Non-Stationary 5G Wireless Channel Model](https://mlsanity.com/paper/2311.16783/) (2023)
- [Dynamic Rate and Channel Selection in Cognitive Radio Systems](https://mlsanity.com/paper/1402.5666/) (2014)

## Built on by (most cited first, 2 of 2)

- [Queue Length Regret Bounds for Contextual Queueing Bandits](https://mlsanity.com/paper/2601.19300/) (2026)
- [Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret](https://mlsanity.com/paper/2606.09668/) (2026)

## Abstract (arXiv)

We consider an online channel scheduling problem for a single transmitter-receiver pair equipped with N arbitrarily varying wireless channels. The transmission rates of the channels might be non-stationary and could be controlled by an oblivious adversary. At every slot, incoming data arrives at an infinite-capacity data queue located at the transmitter. A scheduler, which is oblivious to the current channel rates, selects one of the N channels for transmission. At the end of the slot, the scheduler only gets to know the transmission rate of the selected channel. The objective is to minimize the queue length regret, defined as the difference between the queue length at some time T achieved by an online policy and the queue length obtained by always transmitting over the single best channel in hindsight. We propose a weakly adaptive Multi-Armed Bandit (MAB) algorithm for minimizing the queue length regret in this setup. Unlike previous works, we do not make any stability assumptions about the queue or the arrival process. Hence, our result holds even when the queueing process is unstable. Our main observation is that the queue length regret can be upper bounded by the regret of a MAB policy that competes against the best channel in hindsight uniformly over all sub-intervals of [T]. As a technical contribution of independent interest, we then propose a weakly adaptive adversarial MAB policy which achieves tildeO(√NT^frac34) regret with high probability, implying the same bound for queue length regret.