Stochastic Linear Bandits Robust to Adversarial Attacks

Ilija Bogunovic, Arpan Losalka, Andreas Krause, Jonathan Scarlett
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:991-999, 2021.

Abstract

We consider a stochastic linear bandit problem in which the rewards are not only subject to random noise, but also adversarial attacks subject to a suitable budget $C$ (i.e., an upper bound on the sum of corruption magnitudes across the time horizon). We provide two variants of a Robust Phased Elimination algorithm, one that knows $C$ and one that does not. Both variants are shown to attain near-optimal regret in the non-corrupted case $C = 0$, while incurring additional additive terms respectively having a linear and quadratic dependency on $C$ in general. We present algorithm-independent lower bounds showing that these additive terms are near-optimal. In addition, in a contextual setting, we revisit a setup of diverse contexts, and show that a simple greedy algorithm is provably robust with a near-optimal additive regret term, despite performing no explicit exploration and not knowing $C$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-bogunovic21a, title = { Stochastic Linear Bandits Robust to Adversarial Attacks }, author = {Bogunovic, Ilija and Losalka, Arpan and Krause, Andreas and Scarlett, Jonathan}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {991--999}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/bogunovic21a/bogunovic21a.pdf}, url = {https://proceedings.mlr.press/v130/bogunovic21a.html}, abstract = { We consider a stochastic linear bandit problem in which the rewards are not only subject to random noise, but also adversarial attacks subject to a suitable budget $C$ (i.e., an upper bound on the sum of corruption magnitudes across the time horizon). We provide two variants of a Robust Phased Elimination algorithm, one that knows $C$ and one that does not. Both variants are shown to attain near-optimal regret in the non-corrupted case $C = 0$, while incurring additional additive terms respectively having a linear and quadratic dependency on $C$ in general. We present algorithm-independent lower bounds showing that these additive terms are near-optimal. In addition, in a contextual setting, we revisit a setup of diverse contexts, and show that a simple greedy algorithm is provably robust with a near-optimal additive regret term, despite performing no explicit exploration and not knowing $C$. } }
Endnote
%0 Conference Paper %T Stochastic Linear Bandits Robust to Adversarial Attacks %A Ilija Bogunovic %A Arpan Losalka %A Andreas Krause %A Jonathan Scarlett %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-bogunovic21a %I PMLR %P 991--999 %U https://proceedings.mlr.press/v130/bogunovic21a.html %V 130 %X We consider a stochastic linear bandit problem in which the rewards are not only subject to random noise, but also adversarial attacks subject to a suitable budget $C$ (i.e., an upper bound on the sum of corruption magnitudes across the time horizon). We provide two variants of a Robust Phased Elimination algorithm, one that knows $C$ and one that does not. Both variants are shown to attain near-optimal regret in the non-corrupted case $C = 0$, while incurring additional additive terms respectively having a linear and quadratic dependency on $C$ in general. We present algorithm-independent lower bounds showing that these additive terms are near-optimal. In addition, in a contextual setting, we revisit a setup of diverse contexts, and show that a simple greedy algorithm is provably robust with a near-optimal additive regret term, despite performing no explicit exploration and not knowing $C$.
APA
Bogunovic, I., Losalka, A., Krause, A. & Scarlett, J.. (2021). Stochastic Linear Bandits Robust to Adversarial Attacks . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:991-999 Available from https://proceedings.mlr.press/v130/bogunovic21a.html.

Related Material