Dueling Bandit: Adversarial Attack and Robust Defense

Abstract

Dueling bandit algorithms excel in learning from pairwise comparisons, offering robust performance guarantees in benign environments. However, recent evidence suggests that even state-of-the-art methods can be highly susceptible to adversarial manipulation. In this work, we introduce and analyze a post-action attack model on the Relative Upper Confidence Bound (RUCB) algorithm, a widely used dueling bandit algorithm. Unlike pre-action attack considered in the existing work where the attacker can observe all comparisons beforehand, our post-action adversary intercepts only the feedback from the specific arm pair chosen by the learner at each round. Despite this limited access, we show that such targeted interference can coerce the learner into favoring a predetermined target arm for almost the entire time horizon. Specifically, the attacker incurs a total cost of only <inline-formula><tex-math notation="LaTeX">$\mathcal{O}\mathbf{(}\boldsymbol{K}\,\mathbf{ln}\,\boldsymbol{T}\mathbf{)}$</tex-math></inline-formula> while ensuring that the learner pulls the target arm in <inline-formula><tex-math notation="LaTeX">$\boldsymbol{T}\mathbf\,{-}\,\mathcal{O}\mathbf{(}\boldsymbol{K}^\mathbf{2}\,\mathbf{ln}\,\boldsymbol{T}\mathbf{)}$</tex-math></inline-formula> comparisons, where <inline-formula><tex-math notation="LaTeX">$\boldsymbol{T}$</tex-math></inline-formula> is the time horizon and <inline-formula><tex-math notation="LaTeX">$\boldsymbol{K}$</tex-math></inline-formula> is the number of total arms. To counter such attacks, we propose a novel robust defense strategy Attack-Aware RUCB (AA-RUCB) that augments the RUCB algorithm with attack-awareness. Assuming the adversary’s budget is upper bounded by <inline-formula><tex-math notation="LaTeX">$\boldsymbol{A}$</tex-math></inline-formula>, the proposed algorithm adjusts RUCB’s upper confidence bound estimates to account for potential outcome flips. We prove that the defense algorithm preserves the optimal <inline-formula><tex-math notation="LaTeX">$\boldsymbol{O}\mathbf{(}\boldsymbol{K}^\mathbf{2}\,\mathbf{ln}\,\boldsymbol{T}\mathbf{)}$</tex-math></inline-formula> regret when <inline-formula><tex-math notation="LaTeX">$\boldsymbol{A}\,\mathbf{=}\,\mathbf{0}$</tex-math></inline-formula> and degrades gracefully to <inline-formula><tex-math notation="LaTeX">$\boldsymbol{O}\mathbf{(}\boldsymbol{K}^\mathbf{2}\,\mathbf{ln}\,\boldsymbol{T} + \boldsymbol{A}\sqrt{\mathbf{ln}\,\boldsymbol{T}}\mathbf{)}$</tex-math></inline-formula> as <inline-formula><tex-math notation="LaTeX">$\boldsymbol{A}$</tex-math></inline-formula> grows.