Timezone: »

When Are Linear Stochastic Bandits Attackable?
Huazheng Wang · Haifeng Xu · Hongning Wang

Thu Jul 21 01:00 PM -- 01:05 PM (PDT) @ None

We study adversarial attacks on linear stochastic bandits: by manipulating the rewards, an adversary aims to control the behaviour of the bandit algorithm. Perhaps surprisingly, we first show that some attack goals can never be achieved. This is in a sharp contrast to context-free stochastic bandits, and is intrinsically due to the correlation among arms in linear stochastic bandits. Motivated by this finding, this paper studies the attackability of a k-armed linear bandit environment. We first provide a complete necessity and sufficiency characterization of attackability based on the geometry of the context vectors. We then propose a two-stage attack method against LinUCB and Robust Phase Elimination. The method first asserts whether the given environment is attackable; and if yes, it modifies the rewards to force the algorithm to pull a target arm linear times using only a sublinear cost. Numerical experiments further validate the effectiveness and cost-efficiency of the proposed attacking method.

Author Information

Huazheng Wang (Princeton University)
Haifeng Xu (University of Virginia)
Hongning Wang (University of Virginia)

I am an associate professor in the Department of Computer Science of University of Virginia. My research interest includes data mining, machine learning, and information retrieval, with a special emphasis on computational user behavior modeling.

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors