Power-of-2-Arms for Adversarial Bandit Learning With Switching Costs
Ming Shi, Xiaojun Lin, Lei Jiao · IEEE Transactions on Networking · 2025
Motivated by edge computing with artificial intelligence, in this paper we study an adversarial bandit-learning problem with switching costs. Existing results in the literature either incur$\Theta(T^{\frac{2}{3}})$regret with bandit feedback, or rely on free full-feedback in order to reduce the regret to$O(\sqrt{T})$. In contrast, we expand our study to incorporate two new factors. First, full feedback could incur a cost. Second, the player may choose$2$(or more) arms at a time and observe their feedback, even though switching costs are still incurred when she changes the set of chosen arms. For the setting where the player pulls only one arm at a time, our new regret lower-bound shows that, even when costly full-feedback is added, the$\Theta(T^{\frac{2}{3}})$regret still cannot be improved. However, the dependence on the number of arms may be improved when the full-feedback cost is small. In contrast, for the setting where the player can choose$2$(or more) arms at a time, we provide a novel online learning algorithm that achieves a significantly lower regret equal to$O(\sqrt{T})$. Further, our new algorithm does not need any full feedback at all. This sharp difference therefore reveals the surprising power of choosing$2$(or more) arms for this type of bandit learning problems with switching costs. Both our new algorithm and regret analysis involve several new ideas in choosing the primary and secondary arms, tuning the weight-decay parameters within and across episodes, and using the loss differences in the weight updates, which may be of independent interest.