🤖 machine learning

When Actions Disappear: Adversarial Action Removal in Self-Play Reinforcement Learning

This paper investigates adversarial action masking in self-play reinforcement learning, demonstrating that selectively removing legal actions causes significantly more damage than perturbations, persists across diverse algorithms and domains, and exploits high-value decision points without allowing for recovery.

Original authors: Arahan Kujur

Published 2026-05-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Arahan Kujur

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a high-stakes game of poker against a super-smart computer opponent. You've trained for months, learning every possible move and counter-move. You feel confident. But then, the game changes in a way you can't see: someone quietly takes away your cards.

Not all of them, just the specific ones that would help you win the hand. You still have to play, but your best options are gone. You are forced to make a move you never wanted to make, and you lose.

This paper is about a new kind of "hacker" attack on Artificial Intelligence (AI) that works exactly like that. Instead of confusing the AI with fake information (like putting a sticker on a stop sign so a self-driving car thinks it's a speed limit sign), this attack removes the AI's choices entirely.

Here is the breakdown of the research in simple terms:

1. The Setup: The "Silent Saboteur"

The researchers studied AI agents that learn by playing against themselves (called "self-play"). This is how AIs like those that beat humans at Go or Poker get so good.

The Victim: An AI trying to learn the best strategy.
The Attacker: A "saboteur" AI that doesn't try to win the game itself. Instead, its only job is to look at the victim's options and delete the best ones before the victim can choose them.
The Rule: The attacker can only delete a limited number of options (a "budget"), but it chooses exactly which ones to delete to cause the most chaos.

2. The Big Discovery: "Taking Away the Keys" is Worse Than "Jamming the Lock"

Previous research focused on "perturbations"—basically adding noise or confusion to the AI's senses. Imagine trying to drive while wearing foggy glasses. It's annoying, but you can still steer.

This paper shows that removing actions is like taking the steering wheel away entirely.

The Result: The "action removal" attack was 4 to 5 times more damaging than random removal or noise-based attacks.
The Analogy: If you are a chef, random noise is like someone shaking the salt shaker so you can't tell how much salt you added. Action removal is like someone taking the salt shaker away and forcing you to use only sugar. You can still cook, but the dish will be ruined.

3. The "Magic Formula": Finding the Weak Spots

How does the attacker know which actions to delete? It uses a clever metric the researchers call CAC (Contingent Action Capacity).

Think of a decision point in a game like a fork in the road.
Some forks are trivial (you can go left or right, and it doesn't matter much).
Some forks are critical (going left wins the game; going right loses it).
The attacker looks for the critical forks that the AI visits often and deletes the "winning" path.
The researchers found that the more they reduced the AI's ability to choose at these critical moments, the more the AI's performance collapsed.

4. It Works Everywhere (Not Just Poker)

The researchers tested this in many different "worlds":

Poker: From tiny 6-card games to massive 5,500-card games.
Gridworlds: A simple video game where a character tries to reach a goal while avoiding a predator.
Resource Collection: A game about gathering items.

In every single case, the attack worked. It didn't matter if the AI was a simple math-based learner or a complex neural network (like the ones used in modern deep learning). If you take away the AI's best moves, it gets crushed.

5. The AI Can't "Get Used to It"

Usually, if you train an AI in a difficult environment, it eventually learns to adapt.

The Finding: When the researchers kept the "action removal" active during training, the AI did not recover. It stayed broken.
Why? Because the attack changes the fundamental rules of the game. The AI isn't just learning a new trick; it's being forced to play a game where the winning moves have been deleted. No amount of practice helps if your best moves are missing.

6. The "Scaling" Surprise

The more complex the game, the worse the attack became.

In a tiny game, the attacker was about 2 times more effective than random chance.
In a huge, complex game, the attacker was nearly 5 times more effective.
The Metaphor: In a small room, if you block one door, you can just walk around it. In a giant maze, if you block the one specific hallway that leads to the exit, you are trapped. The bigger the game, the more valuable those specific "blocked" choices become.

Summary

This paper reveals a hidden weakness in AI: They are brittle when their choices are removed.

Current AI safety research often worries about the AI being "tricked" by bad data. This paper says we also need to worry about the AI being "handcuffed" by having its options taken away. The researchers found that a smart attacker can easily identify the most important decisions an AI makes and delete them, causing the AI to fail spectacularly, regardless of how smart or complex the AI is.

The Bottom Line: If you build an AI that relies on having a full menu of options to choose from, you need to protect that menu. If an enemy can delete the best items from the menu, the AI will starve, no matter how well-trained it is.

Technical Summary: Adversarial Action Removal in Self-Play Reinforcement Learning

Problem Definition

This paper investigates a novel and severe adversarial attack surface in Multi-Agent Reinforcement Learning (MARL): adversarial action masking. Unlike prior work focusing on observation perturbations (adding noise to inputs) or reward manipulation, this study formalizes an attack where an adversary selectively removes legal actions from a victim agent's action set before the agent makes a decision.

The problem is framed as a bi-level optimization:

Inner Loop: A victim agent (Player 0) trains via self-play under a constrained action space defined by the mask.
Outer Loop: An adversary (Player 1) learns a policy to select which actions to remove at specific information states to minimize the victim's expected value.

The adversary operates under a budget constraint $k$ , limiting the number of information states where actions can be removed, but must retain at least one legal action per state. The core hypothesis is that removing decision options (structural reduction) is qualitatively different and more damaging than bounded perturbations, as it can collapse decision points to singleton actions, eliminating the agent's ability to choose.

Methodology

Formal Framework

The authors model the environment as a two-player zero-sum extensive-form game. The adversary is defined as a mapping $M: I_0 \to 2^A$ that selects a subset of actions to retain at each victim information set $h$ . The adversary's objective is to minimize the victim's value $V_0(\pi^*_M)$ .

Mechanistic Analysis:
The paper introduces two metrics to explain the attack mechanism:

Reach-Weighted Contingent Action Capacity ( $CAC_w$ ): Measures the remaining multi-action decision capacity at reached information states, weighted by their reach probability $\rho(h)$ .
Value-Weighted Refinement ( $CAC_v$ ): A more precise metric that weights the capacity by the value gap $\delta(h)$ between the victim's optimal action and the forced action: $CAC_v = \sum \rho(h) \cdot \delta(h) \cdot \mathbb{1}[|M(h)| > 1]$ .

Theoretical propositions suggest that a greedy adversary targets states with high $\rho(h) \cdot \delta(h)$ , effectively driving $CAC_w$ and $CAC_v$ downward. Under specific conditions (e.g., $\epsilon$ -greedy Q-learning), the authors prove that if $CAC_w$ is driven to zero, the victim's policy converges to a unique forced action, leading to a stable but suboptimal fixed point.

Experimental Setup

The study evaluates the attack across:

Algorithms: Five distinct learning algorithms including Tabular Q-Learning, Tabular PPO, Tabular NFSP (Neural Fictitious Self-Play), Neural NFSP, and DQN.
Domains:
- Poker: Kuhn Poker (6 states), Leduc Poker (50 states), and scaled variants Leduc-5 (389), Leduc-10 (1,496), and Leduc-20 (5,531 states).
- Non-Poker: Competitive Gridworld (149 states) and Resource Collection (18,604 states).
Baselines: Comparisons against random action removal, fixed action removal, and learned perturbation (RARL-style) attacks.

The training protocol involves alternating between 500 episodes of victim training and one gradient step for the adversary (using REINFORCE) over 20–25 outer iterations.

Key Results

1. Superiority of Adversarial Masking

Learned adversarial masking causes substantially more damage than random masking or learned perturbation.

In Leduc Poker, learned removal is up to 4.8× more damaging than random masking at comparable support levels.
Compared to learned perturbation (RARL-style) with equal training budgets, adversarial action removal is 4× more damaging in Kuhn Poker.
The attack persists even when the adversary is restricted to public information only, though private information access yields stronger results.

2. Scaling with Complexity

The advantage of the learned adversary increases as game complexity grows.

In the Leduc family, the damage ratio (Adversarial/Random) scales from 2.2× (at ~50 states) to 4.8× (at 5,531 states).
This suggests that larger, more complex games offer more "strategic heterogeneity" for the adversary to exploit.

3. Algorithm and Domain Invariance

The vulnerability is not specific to a single algorithm or domain:

Algorithms: All tested agents (QL, PPO, NFSP, DQN) collapse under adversarial masking. Even Neural NFSP, a robust game-solving method, degrades significantly (from -0.13 to -1.89 in Leduc-5).
Domains: The phenomenon holds in non-poker environments. In Competitive Gridworld, adversarial masking caused 1.9× more damage than random masking. In Resource Collection, the gap was 1.4×.

4. Lack of Recovery

Victims do not recover even under extended training with the mask active.

When training continues under a fixed adversarial mask, the victim's reward stabilizes at a significantly lower level compared to the unmasked baseline.
Retraining from scratch on the final learned mask also results in large losses, indicating the structural damage is not easily mitigated by adaptation.

5. Mechanistic Correlation

There is a strong empirical correlation between the reduction of $CAC_w$ and $CAC_v$ and the victim's performance degradation.

$CAC_w$ correlates with victim reward at $r = 0.80$ .
$CAC_v$ correlates at $r = 0.81$ , suggesting that targeting states with high value gaps is the primary driver of the attack's success.

Significance and Claims

The paper argues that action availability constitutes a distinct robustness surface in self-play RL, separate from observation or reward robustness.

Structural Vulnerability: The findings demonstrate that self-play agents are brittle to targeted structural changes in the action space. Unlike perturbations which add noise, removal eliminates decision options, collapsing the agent's strategic flexibility.
Limitations of Current Defenses: Existing robust MARL defenses (e.g., training against perturbations or using population diversity) are insufficient because they assume the joint action space remains intact. The paper notes that averaging strategies or maintaining population diversity cannot restore eliminated strategic dimensions.
Implications for Deployment: In real-world systems where adversaries can disable specific capabilities (e.g., API endpoints, actuators), agents may suffer catastrophic failure. The authors suggest that effective defenses must focus on preserving strategic flexibility at high-reach, high-value decision points ( $CAC_v$ ) rather than optimizing for uniform robustness to arbitrary action unavailability.

The authors remain modest regarding their theoretical claims, noting that the damage bounds are local and additive, and the scaling trend is empirical (based on four game sizes) rather than a proven scaling law. They acknowledge that verification at full poker scale ( $10^5+$ states) and in continuous action domains remains future work.