Dueling Bandit: Adversarial Attack and Robust Defense

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 $\mathcal{O}\mathbf{(}\boldsymbol{K}\,\mathbf{ln}\,\boldsymbol{T}\mathbf{)}$ while ensuring that the learner pulls the target arm in $\boldsymbol{T}\mathbf\,{-}\,\mathcal{O}\mathbf{(}\boldsymbol{K}^\mathbf{2}\,\mathbf{ln}\,\boldsymbol{T}\mathbf{)}$ comparisons, where $\boldsymbol{T}$ is the time horizon and $\boldsymbol{K}$ 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 $\boldsymbol{A}$, 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 $\boldsymbol{O}\mathbf{(}\boldsymbol{K}^\mathbf{2}\,\mathbf{ln}\,\boldsymbol{T}\mathbf{)}$ regret when $\boldsymbol{A}\,\mathbf{=}\,\mathbf{0}$ and degrades gracefully to $\boldsymbol{O}\mathbf{(}\boldsymbol{K}^\mathbf{2}\,\mathbf{ln}\,\boldsymbol{T} + \boldsymbol{A}\sqrt{\mathbf{ln}\,\boldsymbol{T}}\mathbf{)}$ as $\boldsymbol{A}$ grows.