Model and Reinforcement Learning for Markov Games with Risk Preferences

Wenjie Huang, Pham Viet Hai, William Benjamin HaskellAAAI 2020 · DOI

Introduction

In standard Markov games (stochastic games), agents are typically assumed to be risk-neutral, optimizing for expected average costs. However, in high-stakes environments such as finance, cybersecurity, or autonomous driving, agents are often risk-averse, prioritizing the avoidance of catastrophic "tail-end" events over average outcomes.

This paper addresses the challenge of extending risk-aware models from single-agent scenarios to multi-agent games. This transition is complex due to dual sources of risk—environmental randomness and the randomized strategies of opponents—and the computational intractability of traditional robust game formulations. The authors introduce a framework for Markov games with risk-averse players, define a new risk-aware equilibrium, and propose RaNashQL, a model-free reinforcement learning algorithm to find these equilibria.

Methodology: The RaNashQL Algorithm

The authors combine dynamic risk measures with reinforcement learning to navigate the complexities of multi-agent risk. They utilize time-consistent risk measures, ensuring that strategies optimal at one point in time remain optimal throughout the game. By applying Kakutani’s fixed point theorem, they prove that a Risk-Aware Markov Perfect Equilibrium always exists in stationary strategies.

At the heart of their contribution is the RaNashQL algorithm, a simulation-based, model-free Q-learning approach. The algorithm operates via a nested loop structure:

  • Inner Loop: Employs a Stochastic Approximation for Saddle-Point (SASP) algorithm to estimate the risk associated with specific state-action pairs.
  • Outer Loop: Updates Q-values (estimated long-term costs) based on the Nash equilibrium of the "stage game" derived from those values.
Architecture of the RaNashQL algorithm, illustrating the interaction between risk estimation and Nash Q-learning.

To ensure convergence, the authors introduce the $\mathcal{I}'$-mixed point, a technical concept that bridges global optima and saddle points in game theory, proving that RaNashQL converges "almost surely" to the risk-aware equilibrium.

Experimental Evaluation

The framework was evaluated using a Single Server Exponential Queuing System. In this setup, a Service Provider (SP) aims to maximize packet throughput while a Router (R) seeks to minimize latency. The system is modeled as a birth-and-death process with a state space of up to 30 packets. RaNashQL was benchmarked against standard Nash Q-learning and traditional multilinear system solvers.

Key Results and Insights

The study yielded several significant findings regarding risk-aware behavior in competitive environments:

  • Equilibrium Shifting: Risk preferences fundamentally change player behavior, leading to stable points entirely different from those in risk-neutral scenarios.
  • The Variance Paradox: Unlike single-agent optimization where risk-aversion typically reduces variance, in a multi-agent game, risk-awareness can actually increase variance. This occurs because individual attempts to avoid worst-case scenarios can lead to more volatile interactions between opponents.
  • System-Wide Benefits: Interestingly, the total cost to the entire system (the sum of all players' costs) decreased when players were risk-aware compared to the risk-neutral baseline.
  • Performance and Efficiency: RaNashQL achieved a relative error of less than 25% in approximately 5,122 seconds—nearly twice as fast as a standard interior-point solver (10,471 seconds).
Performance evaluation of RaNashQL showing convergence iterations and optimal gap across different precision levels.

Conclusion and Future Work

While RaNashQL provides a robust, model-free advantage by operating purely through observation, it remains computationally more expensive than standard risk-neutral Q-learning due to its nested risk-estimation loops. Future research will focus on scaling this framework to larger state spaces and deriving tighter explicit bounds for the algorithm's time complexity.

Summary updated

BibTeX
@inproceedings{huang2020model,
  author = {Wenjie Huang and Pham Viet Hai and William Benjamin Haskell},
  title = {{Model and Reinforcement Learning for Markov Games with Risk Preferences}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i02.5574},
}
Figure