⚡ electrical engineering

Heterogeneous Learning in Zero-Sum Stochastic Games with Incomplete Information

This paper introduces and analyzes heterogeneous learning schemes for zero-sum stochastic games with incomplete information, demonstrating through stochastic approximation and ODE analysis that agents with distinct learning patterns and rationality levels can converge to specific dynamics, which is applied to model security games between attackers and defenders.

Original authors: Quanyan Zhu, Hamidou Tembine, Tamer Basar

Published 2026-06-03

📖 5 min read🧠 Deep dive

CC BY 3.0

Original authors: Quanyan Zhu, Hamidou Tembine, Tamer Basar

Original paper licensed under CC BY 3.0 (http://creativecommons.org/licenses/by/3.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a high-stakes game of chess, but instead of a board, the players are in a chaotic, shifting environment where the rules of the game (the "payoffs") are hidden from them. They don't know the value of their moves, they don't know the history of their opponent's moves, and they can't talk to each other. This is the world of Zero-Sum Stochastic Games with Incomplete Information described in the paper.

Here is a simple breakdown of what the authors, Zhu, Tembine, and Basar, discovered:

The Problem: Learning in the Dark

In many real-world scenarios (like network security or traffic management), two opposing sides (let's call them Player A and Player B) are constantly trying to outsmart each other.

The Catch: They don't have a rulebook. They don't know exactly how much they win or lose for a specific move. They only know the result after they make a move.
The Old Way: Traditional learning methods usually assume both players are identical "robots" using the exact same brain to learn. They also often assume players can see what the other person did in the past.
The Reality: In the real world, players are different. One might be a fast, impulsive learner (like a hacker scanning for vulnerabilities), while the other is a slow, cautious learner (like a security guard checking logs). They also might not be able to see each other's moves.

The Solution: "Heterogeneous" Learning

The authors propose a new way for these players to learn: Heterogeneous Learning.

Think of it like a dance where one partner is a jazz dancer (improvising, fast, reacting to the moment) and the other is a ballet dancer (structured, slow, following a strict routine). The paper asks: Can they still find a stable rhythm together even though they are dancing to different beats?

The authors introduce a family of learning algorithms where:

Player A might use a "fast" learning scheme (updating their strategy quickly based on immediate rewards).
Player B might use a "slow" learning scheme (taking time to average out their experiences).
Crucially: Neither player needs to know the other's strategy or even the other's existence. They just react to the "score" they get from the environment.

The Magic Trick: The "Shadow" Game

How do they prove this works? The authors use a mathematical tool called Stochastic Approximation.

Imagine the players are walking through a foggy forest, taking small, random steps. It's hard to see the path. The authors' trick is to say: "If you zoom out far enough, the fog clears, and you can see that their random steps actually trace a smooth, predictable line."

They translate the messy, random learning process into a smooth, deterministic "shadow game" (represented by Ordinary Differential Equations, or ODEs). By studying this smooth shadow, they can predict where the players will end up.

The Results: Finding the "Sweet Spot"

The paper proves that even with these different learning speeds and styles, the players will eventually settle into a Saddle Point.

The Analogy: Imagine a mountain pass between two peaks. The "Saddle Point" is the lowest point on the ridge between the peaks.
- Player A (the maximizer) wants to climb the highest peak.
- Player B (the minimizer) wants to stay in the lowest valley.
- The "Saddle Point" is the perfect balance where Player A cannot go higher without Player B forcing them down, and Player B cannot go lower without Player A forcing them up.

The paper shows that whether both players use the same learning style (like two jazz dancers) or different styles (one jazz, one ballet), they will eventually find this stable balance.

A Real-World Example: The Security Game

To test this, the authors simulated a Cybersecurity Game:

The Attacker (Player A): Tries to find a hole in a computer system.
The Defender (Player B): Tries to patch the hole.

In the simulation:

The Attacker used a fast, "soft" learning algorithm (like a Boltzmann-Gibbs distribution, which is a bit like a gambler who occasionally tries a risky move just to see what happens).
The Defender used a standard, slower learning algorithm.

The Outcome: Even though they were learning at different speeds and using different mental models, they both converged to a stable strategy. The Attacker learned when to strike, and the Defender learned when to defend, reaching a point where neither could improve their position by changing their strategy alone.

Summary

The paper's main claim is that in a chaotic, information-poor environment, opposing agents don't need to be identical to reach a stable solution. As long as they use specific types of learning algorithms (even if one is fast and one is slow), they will naturally drift toward a fair and stable equilibrium, much like two dancers with different styles eventually finding a shared rhythm.

Technical Summary: Heterogeneous Learning in Zero-Sum Stochastic Games with Incomplete Information

Problem Statement

The paper addresses the challenge of learning in dynamic, decentralized environments where agents (players) operate with incomplete information. Specifically, the authors consider a two-person zero-sum stochastic game where:

Players do not know their own payoff functions (the utility matrix entries).
Players have no knowledge of the past actions of their opponents.
The state space and transition laws are unknown to the players.
Communication between agents is impractical.

In such settings, standard learning algorithms like fictitious play or best response dynamics, which rely on observing the history of opponent actions, are inapplicable. Furthermore, existing reinforcement learning (RL) algorithms often focus exclusively on either strategy reinforcement or payoff reinforcement, rather than coupling them. The central question is how to design fully distributed learning schemes that require minimal information and resources while enabling agents to learn optimal strategies and estimate optimal payoffs simultaneously.

Methodology

The authors propose a class of heterogeneous learning schemes where agents may adopt distinct learning patterns (algorithms) and operate at different learning rates (time scales).

Game Model

The study utilizes a two-person zero-sum stochastic game model $\Xi = \langle S, A_1, A_2, \{U(s, .)\}_{s \in S} \rangle$ .

$S$ : Set of states (unknown to players, i.i.d. random variables).
$A_1, A_2$ : Finite action sets.
$U$ : Utility function where Player 1 (P1) maximizes and Player 2 (P2) minimizes.
Players use mixed strategies $f_t$ and $g_t$ at time $t$ .

Learning Algorithms (CODIPAS-RL)

The core methodology is the Combined Fully Distributed Payoff and Strategy Reinforcement Learning (CODIPAS-RL) framework. This approach couples the learning of expected payoffs with the learning of strategies. The authors define five specific algorithms within this framework:

CRL0: A basic combined algorithm updating strategies and payoffs via weighted averages of observed payoffs (similar to Q-learning coupled with strategy updates).
CRL1: A Boltzmann-Gibbs based algorithm where strategy updates follow a soft-max function of estimated average payoffs.
CRL2: Similar to CRL1 but uses an imitative Boltzmann-Gibbs strategy, weighting the soft-max by the current strategy vector.
RL2: A standard strategy reinforcement algorithm (similar to replicator dynamics) without explicit payoff estimation coupling.
RL3: A normalized version of RL2.

Analytical Approach

The authors employ stochastic approximation techniques to analyze the convergence of these discrete-time learning algorithms. They map the stochastic learning processes to their deterministic Ordinary Differential Equation (ODE) counterparts.

The analysis considers heterogeneous learning rates, where one player may learn significantly faster than the other (e.g., $\lambda_{1,t} / \lambda_{2,t} \to 0$ ).
The resulting ODEs are shown to differ from standard replicator dynamics, best response dynamics, logit dynamics, and fictitious play, depending on the specific combination of algorithms and learning rates used by the players.

Key Contributions

Heterogeneous Learning Framework: The paper introduces a framework where agents can adopt different learning schemes (e.g., one uses CRL1 while the other uses RL2) and operate on different time scales.
Coupled Payoff-Strategy Learning: Unlike standard RL which often separates strategy and value learning, the proposed CODIPAS-RL algorithms simultaneously update strategy vectors and estimated average payoffs without requiring knowledge of opponent actions.
ODE Characterization: The authors derive the specific ODEs governing the asymptotic behavior of these heterogeneous schemes. They demonstrate that when players learn at different speeds, the system dynamics can be described by a "slow" player reacting to the "fast" player's smooth best response, or vice versa.
Convergence to $\epsilon$ -Saddle Points: The paper establishes that these heterogeneous dynamics converge almost surely to an $\epsilon$ -saddle point of the expected game. As the soft-max parameter $\epsilon \to 0$ , these points converge to the true saddle points.
Elimination of Dominated Strategies: Under the CRL1 algorithm, the authors prove that strictly dominated strategies are eliminated in the long term.

Results

Convergence: The paper proves that combinations of CRL1, RL2, and RL3 (e.g., CRL1 vs. RL2, CRL1 vs. CRL2) lead to convergence to saddle-point solutions in zero-sum stochastic games.
Time-Scale Separation: When one player learns faster than the other, the slower player's trajectory converges to a smooth best response (or adjusted replicator dynamics) relative to the fast player's strategy.
Simulation (Security Game Application): The authors apply the algorithms to a network intrusion detection scenario (Attacker vs. Defender).
- Scenario: A $2 \times 2$ game with stochastic payoffs.
- Homogeneous Case: When both players use CRL1, payoffs and strategies converge to the game value (approx. 2.6) and the saddle point strategies ( $f^*=[0.4, 0.6]$ , $g^*=[0.2, 0.8]$ ), though convergence is slow.
- Heterogeneous Case: When the attacker uses CRL1 and the defender uses RL2, the system also converges, demonstrating the robustness of the heterogeneous approach.

Significance and Claims

The paper claims that its primary contribution is addressing the major challenge of learning in decentralized environments with minimal information requirements. By relaxing the assumption that players must observe the history of opponent actions, the proposed algorithms are more applicable to real-world networking and security scenarios where such observation is "implausible and impractical."

The authors emphasize that their work:

Provides a theoretical foundation for heterogeneous learning, acknowledging that agents in real systems (like attackers and defenders) possess different levels of rationality and information.
Offers a class of algorithms that are fully distributed and require only local payoff observations.
Extends the understanding of game dynamics beyond standard replicator or best-response models, showing how different learning rates and schemes create new dynamic behaviors that still converge to equilibrium.

The paper concludes modestly, noting that future work involves extending these results to stochastic games with controlled states and non-zero-sum games.