Timezone: »

 
Poster
Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms
Jeongyeol Kwon · Yonathan Efroni · Constantine Caramanis · Shie Mannor

Tue Jul 19 03:30 PM -- 05:30 PM (PDT) @ Hall E #1107
in Poster Session 1 »
Motivated by online recommendation systems, we propose the problem of finding the optimal policy in multitask contextual bandits when a small fraction $\alpha < 1/2$ of tasks (users) are arbitrary and adversarial. The remaining fraction of good users share the same instance of contextual bandits with $S$ contexts and $A$ actions (items). Naturally, whether a user is good or adversarial is not known in advance. The goal is to robustly learn the policy that maximizes rewards for good users with as few user interactions as possible. Without adversarial users, established results in collaborative filtering show that $O(1/\epsilon^2)$ per-user interactions suffice to learn a good policy, precisely because information can be shared across users. This parallelization gain is fundamentally altered by the presence of adversarial users: unless there are super-polynomial number of users, we show a lower bound of $\tilde{\Omega}(\min(S,A) \cdot \alpha^2 / \epsilon^2)$ {\it per-user} interactions to learn an $\epsilon$-optimal policy for the good users. We then show we can achieve an $\tilde{O}(\min(S,A)\cdot \alpha/\epsilon^2)$ upper-bound, by employing efficient robust mean estimators for both uni-variate and high-dimensional random variables. We also show that this can be improved depending on the distributions of contexts.
Keywords: OPT: Optimization and Learning under Uncertainty · RL: Policy Search · T: Learning Theory · T: Online Learning and Bandits · T: Reinforcement Learning and Planning · MISC: Transfer, Multitask and Meta-learning

Author Information

Jeongyeol Kwon (The University of Texas at Austin)
Yonathan Efroni (Microsoft Research, New York)
Constantine Caramanis (University of Texas)
Shie Mannor (Technion)

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

More from the Same Authors