Non-Cooperative Inverse Reinforcement Learning

Xiangyuan Zhang, Kaiqing Zhang, Erik Miehling, Tamer Basar

Abstract

Making decisions in the presence of a strategic opponent requires accounting for the opponent's ability to actively mask its intended objective. This paper introduces the Non-Cooperative Inverse Reinforcement Learning (N-CIRL) formalism, designed for strategic situations where two agents have completely misaligned objectives and only one agent knows the true objective function. Modeled as a zero-sum Markov game with one-sided incomplete information, the N-CIRL framework allows a less-informed player to simultaneously infer and respond to the true objective through interaction. We present a recursive decomposition of the multi-stage game, a dual game construction for strategy computation, and the NC-PBVI algorithm for tractable approximation. Numerical simulations in a cyber security setting demonstrate that N-CIRL significantly outperforms traditional multi-agent IRL methods.

Introduction

In standard Reinforcement Learning (RL), the reward function is typically known. Inverse Reinforcement Learning (IRL) addresses scenarios where the reward function must be deduced by observing an "expert." However, most IRL research assumes a cooperative setting where the expert intends to help the learner. In domains like cyber security, the expert is an adversary who may strategically mask their intentions to maintain a competitive advantage.

Existing Multi-Agent IRL (MA-IRL) techniques often assume a stationary environment where learning occurs offline before execution. This paper identifies a critical gap: in dynamic security settings, learning and execution must be intertwined. The N-CIRL framework addresses this by modeling the interaction as a strategic game where the defender learns the attacker's intent in real-time while actively defending the system.

The N-CIRL Formalism

The authors formalize N-CIRL as a two-player zero-sum Markov game with one-sided incomplete information.

  • The Attacker (Informed Player): Possesses knowledge of the true reward function, parameterized by an intent $\theta$.
  • The Defender (Less Informed Player): Does not know $\theta$ and must maintain a belief distribution over possible intents based on the attacker's observed actions.

Technical Innovations

To solve this complex interaction, the paper introduces three key technical contributions:

  1. Sequential Decomposition: The authors prove that the multi-stage game can be decomposed into a sequence of single-stage games. This recursive structure allows for the computation of the game's value and the informed player's equilibrium strategy.
  2. The Dual Game: Because the defender lacks knowledge of the attacker's internal state, the authors construct an auxiliary "dual game." This allows the defender to derive an equilibrium strategy by observing only external actions and state transitions.
  3. NC-PBVI Algorithm: The authors adapt Point-Based Value Iteration (PBVI) for the non-cooperative setting. While standard PBVI uses alpha-vectors to approximate value functions, N-CIRL utilizes information state-value pairs and a "sawtooth" approximation method. This ensures the optimization remains computationally tractable via linear programming.

Experimental Evaluation

The framework was evaluated using a novel cyber security simulation based on Attack Graphs. These graphs represent system vulnerabilities as directed acyclic graphs. The experiments utilized graph sizes ranging from $n=6$ to $10$ nodes, with state cardinalities up to 64 and action cardinalities up to 676.

N-CIRL was compared against a traditional MA-IRL baseline, where the defender learns from an attack log (historical data) before the game begins. This comparison highlights the difference between static offline learning and the adaptive, online nature of N-CIRL.

Key Insights and Results

The Deception Limit

A central insight of the research is the "deception limit." While a strategic attacker can attempt to mask their intent, they must eventually take actions that reveal their true goals to achieve their objective. N-CIRL is specifically designed to exploit this inevitable signaling, allowing the defender to refine their beliefs as the game progresses.

Performance Gains

In numerical simulations, the N-CIRL strategy consistently resulted in lower rewards for the attacker compared to the MA-IRL baseline. Notably, as the complexity of the network (number of nodes) increased, the relative performance benefit of N-CIRL also grew. This suggests that the framework is particularly resilient in complex, high-stakes environments.

Computational Feasibility

The NC-PBVI algorithm demonstrated practical scaling. While runtime increases with the number of nodes, it remained within a manageable range (approximately 100-1000 seconds for the largest tested graphs), proving that strategic inference can be performed in reasonably sized state spaces.

Conclusion and Future Work

N-CIRL provides a robust mathematical foundation for learning from strategic opponents. By interleaving learning and execution, it overcomes the limitations of stationary offline IRL. Future research directions include extending the model to general-sum games, where players may have partially overlapping interests, and improving scalability to handle the thousands of nodes found in real-world enterprise networks. Additionally, further investigation into the nuances of "signaling"—how players use actions specifically to manipulate opponent beliefs—remains a promising frontier for asymmetric stochastic 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 act according to, 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