Non-Cooperative Inverse Reinforcement Learning

Xiangyuan Zhang, Kaiqing Zhang, Erik Miehling, Tamer Basar

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

Abstract

Making decisions in the presence of a strategic opponent requires one to take into account the opponent’s ability to actively mask its intended objective. To describe such strategic situations, we introduce the non-cooperative inverse reinforcement learning (N-CIRL) formalism. The N-CIRL formalism consists of two agents with completely misaligned objectives, where only one of the agents knows the true objective function. Formally, we model the N-CIRL formalism as a zero-sum Markov game with one-sided incomplete information. Through interacting with the more informed player, the less informed player attempts to both infer and optimize the true objective function. As a result of the one-sided incomplete information, the multi-stage game can be decomposed into a sequence of single- stage games expressed by a recursive formula. Solving this recursive formula yields the value of the N-CIRL game and the more informed player’s equilibrium strategy. Another recursive formula, constructed by forming an auxiliary game, termed the dual game, yields the less informed player’s strategy. Building upon these two recursive formulas, we develop a computationally tractable algorithm to approximately solve for the equilibrium strategies. Finally, we demonstrate the benefits of our N-CIRL formalism over the existing multi-agent IRL formalism via extensive numerical simulation in a novel cyber security setting.
BibTeX
@inproceedings{zhang2019non,
  author = {Xiangyuan Zhang and Kaiqing Zhang and Erik Miehling and Tamer Basar},
  title = {{Non-Cooperative Inverse Reinforcement Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=DTCZozrcGa},
}
Figure