Power-of-2-Arms for Adversarial Bandit Learning With Switching Costs

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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Theta(T^{\frac{2}{3}})$</tex-math> </inline-formula> regret with bandit feedback, or rely on free full-feedback in order to reduce the regret to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(\sqrt{T})$</tex-math> </inline-formula> . In contrast, we expand our study to incorporate two new factors. First, full feedback could incur a cost. Second, the player may choose <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2$</tex-math> </inline-formula> (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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Theta(T^{\frac{2}{3}})$</tex-math> </inline-formula> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2$</tex-math> </inline-formula> (or more) arms at a time, we provide a novel online learning algorithm that achieves a significantly lower regret equal to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(\sqrt{T})$</tex-math> </inline-formula> . Further, our new algorithm does not need any full feedback at all. This sharp difference therefore reveals the surprising power of choosing <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2$</tex-math> </inline-formula> (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.