hide
Free keywords:
Computer Science, Learning, cs.LG,Computer Science, Artificial Intelligence, cs.AI,Computer Science, Cryptography and Security, cs.CR,Computer Science, Multiagent Systems, cs.MA
Abstract:
In targeted poisoning attacks, an attacker manipulates an agent-environment
interaction to force the agent into adopting a policy of interest, called
target policy. Prior work has primarily focused on attacks that modify standard
MDP primitives, such as rewards or transitions. In this paper, we study
targeted poisoning attacks in a two-agent setting where an attacker implicitly
poisons the effective environment of one of the agents by modifying the policy
of its peer. We develop an optimization framework for designing optimal
attacks, where the cost of the attack measures how much the solution deviates
from the assumed default policy of the peer agent. We further study the
computational properties of this optimization framework. Focusing on a tabular
setting, we show that in contrast to poisoning attacks based on MDP primitives
(transitions and (unbounded) rewards), which are always feasible, it is NP-hard
to determine the feasibility of implicit poisoning attacks. We provide
characterization results that establish sufficient conditions for the
feasibility of the attack problem, as well as an upper and a lower bound on the
optimal cost of the attack. We propose two algorithmic approaches for finding
an optimal adversarial policy: a model-based approach with tabular policies and
a model-free approach with parametric/neural policies. We showcase the efficacy
of the proposed algorithms through experiments.
