A Truthful Pricing-Based Defending Strategy Against Adversarial Attacks in Budgeted Combinatorial Multi-Armed Bandits

We study defending strategies against adversarial attacks on Combinatorial Multi-Armed Bandits (CMAB) algorithms. CMAB is an effective sequence decision making tool that has been broadly applied in online real-world applications. We consider a realistic CMAB setting, budgeted CMAB, in which multiple arms associated with pulling costs and unknown rewards are pulled per round, aiming to maximize the cumulative reward under a budget constraint. However, the adversarial attack against budgeted CMAB is rarely studied, posing a very important security issue. Specifically, a suboptimal arm that is not pulled (i.e., attacker) can hijack the budgeted CMAB algorithm's behavior, forcing itself to be pulled frequently by manipulating other arms' rewards. Existing strategies cannot prevent such attacks. Motivated by this, we closely study the adversarial attack against a popular budgeted CMAB algorithm, exposing a significant security threat to real-world applications. The attack extends to other algorithms with certain customization. To address this, we incorporate a truthful pricing-based defending strategy that prevents such attacks effectively and ensures arms share pulling costs truthfully. Extensive simulations have illustrated the proposed attack strategy can hijack the algorithm efficiently, while the defending strategy provides attack prevention, individual rationality, and asymptotic truthfulness guarantees.