The Library
Saving stochastic bandits from poisoning attacks via limited data verification
Tools
Rangi, Anshuka, Tran-Thanh, Long, Xu, Haifeng and Franceschetti, Massimo (2022) Saving stochastic bandits from poisoning attacks via limited data verification. In: Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22), Virtual conference, 22 Feb- 01 Mar 2022. Published in: Proceedings of the AAAI Conference on Artificial Intelligence, 36 (7). pp. 8054-8061. doi:10.1609/aaai.v36i7.20777 ISSN 2374-3468.
|
PDF
WRAP-Saving-stochastic-bandits-poisoning-attacks-limited-data-verification-2022.pdf - Accepted Version - Requires a PDF viewer. Download (498Kb) | Preview |
Official URL: https://doi.org/10.1609/aaai.v36i7.20777
Abstract
This paper studies bandit algorithms under data poisoning attacks in a bounded reward setting. We consider a strong attacker model in which the attacker can observe both the selected actions and their corresponding rewards, and can contaminate the rewards with additive noise. We show that any bandit algorithm with regret O(log T) can be forced to suffer a regret O(T) with an expected amount of contamination O(log T). This amount of contamination is also necessary, as we prove that there exists an O(log T) regret bandit algorithm, specifically the classical UCB, that requires Omega(log T) amount of contamination to suffer regret Omega(T). To combat such poisoning attacks, our second main contribution is to propose verification based mechanisms, which use limited verification to access a limited number of uncontaminated rewards. In particular, for the case of unlimited verifications, we show that with O(log T) expected number of verifications, a simple modified version of the Explore-then-Commit type bandit algorithm can restore the order optimal O(log T) regret irrespective of the amount of contamination used by the attacker. We also provide a UCB-like verification scheme, called Secure-UCB, that also enjoys full recovery from any attacks, also with O(log T) expected number of verifications. To derive a matching lower bound on the number of verifications, we also prove that for any order-optimal bandit algorithm, this number of verifications O(log T) is necessary to recover the order-optimal regret. On the other hand, when the number of verifications is bounded above by a budget B, we propose a novel algorithm, Secure-BARBAR, which provably achieves O(min(C,T/sqrt(B))) regret with high probability against weak attackers (i.e., attackers who have to place the contamination before seeing the actual pulls of the bandit algorithm), where C is the total amount of contamination by the attacker, which breaks the known Omega(C) lower bound of the non-verified setting if C is large.
Item Type: | Conference Item (Paper) | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > Q Science (General) Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Library of Congress Subject Headings (LCSH): | Machine learning, Computer security | ||||||||
Journal or Publication Title: | Proceedings of the AAAI Conference on Artificial Intelligence | ||||||||
Publisher: | AAAI Press | ||||||||
ISSN: | 2374-3468 | ||||||||
Official Date: | 28 June 2022 | ||||||||
Dates: |
|
||||||||
Volume: | 36 | ||||||||
Number: | 7 | ||||||||
Page Range: | pp. 8054-8061 | ||||||||
DOI: | 10.1609/aaai.v36i7.20777 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||
Copyright Holders: | Copyright © 2022, Association for the Advancement of Artificial Intelligence | ||||||||
Date of first compliant deposit: | 8 February 2022 | ||||||||
Date of first compliant Open Access: | 22 July 2022 | ||||||||
Conference Paper Type: | Paper | ||||||||
Title of Event: | Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22) | ||||||||
Type of Event: | Conference | ||||||||
Location of Event: | Virtual conference | ||||||||
Date(s) of Event: | 22 Feb- 01 Mar 2022 | ||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year