Introduction
In security-sensitive domains, an agent (the Decision Maker, or DM) rarely operates in a vacuum. Instead, they often face strategic adversaries intent on minimizing the DM's utility. Traditional Reinforcement Learning (RL) paradigms often falter in these adversarial settings due to the underlying assumption of environmental stationarity. When an adversary adapts to the DM's strategy, the environment becomes non-stationary, rendering previously learned policies obsolete. This paper proposes a prescriptive framework to handle such threats by modeling the adversary's decision-making process recursively.
Threatened Markov Decision Processes (TMDPs)
The authors formalize the adversarial environment as a Threatened Markov Decision Process (TMDP). A TMDP extends the standard MDP tuple $(S, A, T, r)$ by incorporating:
- $B$: A set of threat actions available to the adversary.
- $p_A(b|s)$: The DM’s subjective belief distribution over the adversary's actions in state $s$.
- Joint-Action Q-learning: The update rule is modified to $Q(s, a, b)$, accounting for the rewards received under the joint actions of the DM ($a$) and the adversary ($b$).
Level-$k$ Thinking Framework
To navigate the strategic complexity of TMDPs, the paper employs a recursive Level-$k$ thinking scheme. This hierarchy allows the DM to anticipate the opponent's moves by simulating their reasoning:
- Level-0: A non-strategic baseline (e.g., fictitious play based on historical frequencies).
- Level-1: An agent that assumes the opponent is Level-0.
- Level-2: An agent that assumes the opponent is Level-1.
By operating at one level of reasoning higher than the adversary, the DM can effectively "stay one step ahead" without needing an infinite chain of recursive modeling.
Experimental Results
The framework was evaluated using two primary benchmarks: the "Friend or Foe" gridworld and the Iterated Chicken game.
Exploitation Defense in Gridworlds
In the "Friend or Foe" environment, an adaptive adversary attempts to penalize the DM's target selection. As shown in Figure 1, a standard independent Q-learner (cyan) is easily exploited, leading to significant negative rewards. Conversely, the Level-2 Q-Agent (purple) successfully models the adversary's behavior, eventually converging to a strategy that yields positive rewards.
Dominance in Matrix Games
In the Iterated Chicken game, the Level-2 agent ($L2Q$) consistently outperformed both Level-1 agents ($L1Q$) and other adaptive algorithms like $WoLF-PHC$.
As detailed in Figure 3, the $L2Q$ agent achieved a reward of 0.77 against a $WoLF-PHC$ adversary, whereas the $L1Q$ agent suffered a loss of -2.05. This highlights the necessity of higher-order reasoning when facing sophisticated opponents.
Conclusion and Future Work
The TMDP framework and Level-$k$ thinking provide a robust foundation for RL in adversarial settings. While effective, the approach faces challenges regarding computational complexity as $k$ increases and the requirement for observability of opponent actions and rewards. Future research will focus on scaling these methods to "black box" environments where adversarial information is partially hidden or noisy.
Summary updated