English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study bandit algorithms under data poisoning attacks in a bounded rewardsetting. We consider a strong attacker model in which the attacker can observeboth the selected actions and their corresponding rewards and can contaminatethe rewards with additive noise. We show that any bandit algorithm with regret$O(\log T)$ can be forced to suffer a regret $\Omega(T)$ with an expectedamount of contamination $O(\log T)$. This amount of contamination is alsonecessary, as we prove that there exists an $O(\log T)$ regret banditalgorithm, specifically the classical UCB, that requires $\Omega(\log T)$amount of contamination to suffer regret $\Omega(T)$. To combat such attacks,our second main contribution is to propose verification based mechanisms, whichuse 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 theETC type bandit algorithm can restore the order optimal $O(\log T)$ regretirrespective of the amount of contamination used by the attacker. We alsoprovide a UCB-like verification scheme, called Secure-UCB, that also enjoysfull recovery from any attacks, also with $O(\log T)$ expected number ofverifications. To derive a matching lower bound on the number of verifications,we prove that for any order-optimal bandit algorithm, this number ofverifications $\Omega(\log T)$ is necessary to recover the order-optimalregret. On the other hand, when the number of verifications is bounded above bya budget $B$, we propose a novel algorithm, Secure-BARBAR, which provablyachieves $O(\min\{C,T/\sqrt{B} \})$ regret with high probability against weakattackers where $C$ is the total amount of contamination by the attacker, whichbreaks the known $\Omega(C)$ lower bound of the non-verified setting if $C$ islarge.

Saving Stochastic Bandits from Poisoning Attacks via Limited Data Verification