Research map / Adversarial robustness and security / Attacks on text and graphs

Optimal Attack and Defense for Reinforcement Learning

AAAI 2024 · Adversarial robustness and security › Attacks on text and graphs · approach: Attacks and defenses in sequential settings · 9 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Formulates optimal online manipulation attacks on RL as a meta-MDP solvable by standard planning/RL, and defenses as weak Stackelberg equilibria of a POTBSG, with polynomial-time optimal defenses in restricted settings.

Problem

Adversarial RL where an attacker manipulates states, observations, actions, or rewards during victim-environment interaction; both optimal attacks and provably robust defenses are needed.

Approach

Model the attacker's problem as an MDP (meta-MDP) over subtime-expanded meta-states, so optimal attacks are computed by standard planning or learning; model the victim's defense as a Stackelberg equilibrium of a partially-observable turn-based stochastic game, solvable efficiently when perceived-state attacks are excluded.

Key results

• On a 10x10 grid world with H=20, the optimal policy achieves value 3; under optimal perceived-state, true-state, and action attacks the victim gets -100, 0, and -160 respectively.
• The robust defense avoids the unmonitored regions and still achieves the optimal value of 3 under the strongest attack.
• Attacker's meta-MDP has size polynomial in the original environment, enabling polynomial-time optimal attacks; defense is NP-hard with observation attacks but polynomial for fully observable, no perceived-state attack settings.

Measured effects reported in the paper

Surprising findings

• State attacks, despite seeming most powerful, cause less damage (value 0) than perceived-state or action attacks because the attacked state leaves immediately.

Limitations

• Defense problem is NP-hard in general when observation attacks are permitted
• Experiments limited to a small tabular grid-world
• Victim's optimal defense may not be useful if attacker is too powerful

Experimental setup

Datasets: 10x10 grid-world with lava (constructed)

Benchmarks: 10x10 grid-world shortest path with lava

Metrics: victim value under attack

Builds on: Stackelberg games for security POTBSG perceived-state attack MDP

Closest papers by meaning

• Policy Teaching via Environment Poisoning: Training-time Adversarial Attacks against Reinforcement Learning (ICML 2020 · similarity 0.91)
• Rethinking Adversarial Policies: A Generalized Attack Formulation and Provable Defense in RL (ICLR 2024 · similarity 0.91)
• Beyond Worst-case Attacks: Robust RL with Adaptive Defense via Non-dominated Policies (ICLR 2024 · similarity 0.89)
• PolicyGuard: Towards Test-time and Step-level Adversary Defense for Reinforcement Learning Agent (ICML 2026 · similarity 0.89)
• Multi-level Certified Defense Against Poisoning Attacks in Offline Reinforcement Learning (ICLR 2025 · similarity 0.88)
• Diffusion Guided Adversarial State Perturbations in Reinforcement Learning (NeurIPS 2025 · similarity 0.88)