Introduction: The Challenge of Adversarial Intent
In traditional Reinforcement Learning (RL), the reward function is assumed to be known. Inverse Reinforcement Learning (IRL) flips this paradigm, attempting to infer the reward function by observing an expert's behavior. While Cooperative IRL (CIRL) improved upon passive observation by allowing agents to interact, it fundamentally assumes both agents are on the same team.
But what happens in adversarial settings, such as cyber security? In these scenarios, an attacker (the "expert") has a specific, hidden goal—such as stealing sensitive data or disrupting a service—that the defender does not know. The attacker is not trying to help the defender learn; rather, they actively attempt to mask their intent. Existing Multi-Agent IRL (MA-IRL) techniques often fail in these environments because they assume the environment is stationary or that the agents' goals remain consistent between the learning and execution phases. To address this gap, researchers have introduced Non-Cooperative Inverse Reinforcement Learning (N-CIRL).
The N-CIRL Framework
The authors formalize N-CIRL as a two-player zero-sum Markov game with one-sided incomplete information.
In this structure, the "Attacker" is the more informed player, possessing a hidden intent parameter $\theta$ that defines the reward function. The "Defender" is the less informed player, knowing only the initial probability distribution of possible intents.
Because the information asymmetry is one-sided, the complex multi-stage game can be mathematically decomposed into a sequence of single-stage games. This decomposition relies on two recursive structures:
- The Primal Game: This formulation yields the overall value of the game and the attacker's equilibrium strategy.
- The Dual Game: An auxiliary construction used to determine the defender's optimal strategy. It allows the defender to calculate an equilibrium strategy based on their own belief state, without needing a perfect model of the attacker's internal decision-making process.
Algorithmic Approach: NC-PBVI
Solving these recursive games is theoretically challenging. Standard Point-Based Value Iteration (PBVI) fails here because the Bellman update requires knowing the opponent's strategy.
To bypass this, the authors propose Non-Cooperative Point-Based Value Iteration (NC-PBVI). This algorithm approximates value functions using a set of "information state-value pairs" and uses Linear Programming (LP) to solve the stage-wise games. By employing "sawtooth" function approximations, NC-PBVI maintains lower and upper bounds on the concave and convex value functions of the primal and dual games, rendering the solution computationally tractable.
Key Insights: Interleaved Learning and the Attacker's Dilemma
A major takeaway from the N-CIRL framework is that the defender benefits significantly from interleaving learning and execution. By acting and observing the attacker's real-time responses, the defender learns the hidden intent much faster than by analyzing logs after the fact.
This dynamic creates what is known as the Attacker's Dilemma. In games of incomplete information, the more informed player faces a strict trade-off: they want to achieve their goal, but every optimal action they take inherently "signals" their true intent to the defender. As the authors note, the attacker cannot exploit their private information without revealing it, at least to some extent.
Experimental Results in Cyber Security
The authors evaluated their approach using a novel cyber security simulation based on attack graphs—directed acyclic graphs where nodes represent system conditions and edges represent exploits. They tested on randomly generated graphs ranging from 6 to 10 nodes, with state cardinalities up to 64 and action cardinalities up to 676.
- Superior Performance: N-CIRL strategies consistently resulted in lower average rewards for the attacker compared to strategies derived from standard MA-IRL benchmarks.
- Adaptivity: The N-CIRL defense postures proved highly adaptive, shifting dynamically as the attacker's intent became clearer through their actions.
- Computational Feasibility: Despite the theoretical hardness of the problem, NC-PBVI demonstrated reasonable runtime scaling. For a 10-node graph with hundreds of possible actions, the average runtime was approximately 16 minutes ($10^3$ seconds), making it a viable tool for strategic planning.
Limitations and Future Work
While NC-PBVI represents a significant step forward, challenges remain. The state and action spaces in real-world enterprise cyber networks are vastly larger than the 10-node graphs tested, meaning further optimizations or hierarchical approaches will be necessary for massive systems.
Additionally, the current model assumes the attacker's intent $\theta$ is fixed throughout the game, whereas real-world attackers might pivot their goals mid-intrusion. Future research will likely explore dynamic intents and delve deeper into "signaling effects"—how agents intentionally use actions to manipulate an opponent's beliefs in general asymmetric games.
Summary updated