标题： 任意变化信道的队列长度遗憾最小化 显示英文标题

标题： Minimizing Queue Length Regret for Arbitrarily Varying Channels

摘要： 我们考虑一个单个发射机-接收机对配备有$N$任意变化的无线信道的在线信道调度问题。 信道的传输速率可能是非平稳的，并可能由一个无意识的对手控制。 在每个时隙，到达的数据会进入位于发射机处的无限容量数据队列中。 一个调度器，它不知道当前的信道速率，会选择其中一个$N$信道进行传输。 在时隙结束时，调度器只能知道所选信道的传输速率。 目标是使队列长度遗憾最小化，即定义为在某个时间$T$通过在线策略实现的队列长度与始终在事后选择最佳信道传输所得到的队列长度之间的差值。 我们提出了一种弱自适应多臂老虎机（MAB）算法，用于在此设置中最小化队列长度遗憾。 与之前的工作不同，我们不对队列或到达过程做出任何稳定性假设。 因此，我们的结果即使在排队过程不稳定时也成立。 我们的主要观察是，队列长度遗憾可以被一个MAB策略的遗憾所上界，该策略在所有$[T]$的子区间内统一地与事后最佳信道竞争。 作为一项独立感兴趣的的技术贡献，我们随后提出了一种弱自适应对抗性MAB策略，以高概率实现$\tilde{O}(\sqrt{N}T^{\frac{3}{4}})$的遗憾，这意味着队列长度遗憾也具有相同的界限。 显示英文摘要

摘要： 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 $\tilde{O}(\sqrt{N}T^{\frac{3}{4}})$ regret with high probability, implying the same bound for queue length regret.