🤖 machine learning

Decentralized Best-Response-Based Learning in Two-Player Zero-Sum Stochastic Games: A Finite-Sample Analysis

This paper presents a finite-sample analysis of decentralized, payoff-based best-response learning algorithms for two-player zero-sum matrix and stochastic games, establishing sample complexity bounds of $\mathcal{O}(\epsilon^{-1})$ and $\tilde{\mathcal{O}}(\epsilon^{-8})$ respectively through a novel coupled Lyapunov-drift framework that handles interacting stochastic iterates and nonstationary sampling.

Original authors: Zaiwei Chen, Kaiqing Zhang, Eric Mazumdar, Asuman Ozdaglar, Adam Wierman

Published 2026-06-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zaiwei Chen, Kaiqing Zhang, Eric Mazumdar, Asuman Ozdaglar, Adam Wierman

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.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 two people playing a high-stakes game of chess, but with a twist: they are in separate rooms, they can't talk to each other, and they don't even know the rules of the game or what their opponent is doing. They only know one thing: every time they make a move, they get a score (a reward) or lose points.

This paper is about teaching these two players how to learn the best way to play against each other, purely by trial and error, without ever seeing the other person's strategy. The authors call this "decentralized learning."

Here is a breakdown of their work using simple analogies:

The Problem: Learning in the Dark

In many real-world situations (like self-driving cars or robots working together), multiple "agents" (players) have to make decisions. Sometimes they want to cooperate, but often they are competitors (like in a zero-sum game where one wins and the other loses).

The challenge is that most learning algorithms assume the players can talk or see each other's moves. This paper asks: Can we design a learning system where players act completely independently, only looking at their own score, and still figure out the perfect strategy?

The Solution: The "Smoothed Best Response"

The authors focus on a specific type of learning called "Best Response."

The Analogy: Imagine you are playing a game. A "Best Response" is like looking at what your opponent did last time and thinking, "If I do this specific move, I will win the most points."
The Twist: In the real world, you can't be 100% sure what the opponent will do next. So, the authors use a "Smoothed" version. Instead of picking one perfect move, the player picks a mix of moves that mostly favors the winning strategy but leaves a little room for randomness. This prevents the players from getting stuck in a loop of bad habits.

The Two Scenarios

The paper tests this idea in two different "arenas":

1. The Matrix Game (The Simple Arena)
Think of this as a game of Rock-Paper-Scissors. There are no changing states; you just pick a move, get a score, and repeat.

The Result: The authors proved that if both players use this "Smoothed Best Response" method, they will eventually learn a stable pattern of play (a Nash Equilibrium).
The Catch: Without a little extra help, the learning is slow and inefficient. It's like trying to find a needle in a haystack by only looking at one spot at a time.
The Fix: They added a "Exploration" feature. This is like telling the players, "Every now and then, pick a move completely at random just to see what happens." This small change allowed them to prove that the players can find the perfect strategy much faster (mathematically speaking, the time it takes grows at a manageable rate, not an impossible one).

2. The Stochastic Game (The Complex Arena)
Now, imagine the game is more like a video game with levels. You are in a forest, you pick a path, and the forest changes. You might end up in a cave or a mountain. The goal is to win over a long period, not just one move.

The Challenge: This is much harder because the players have to remember not just their current move, but how that move changes the future "map" of the game.
The Solution (VI-SBR): The authors created a new algorithm called Value Iteration with Smoothed Best Response (VI-SBR).
- Outer Loop (The Map): One part of the algorithm tries to estimate the "value" of different locations on the map (e.g., "The cave is worth 10 points, the mountain is worth 5").
- Inner Loop (The Moves): The other part uses the "Smoothed Best Response" method to decide which move to make in the current location.
The Result: Even though the players are in separate rooms and the game is constantly changing, this algorithm proves they can still learn the perfect strategy. They showed that with the "Exploration" tweak, they can find the winning strategy in a reasonable amount of time.

The Secret Weapon: The "Coupled Lyapunov-Drift" Framework

This is the heavy math part, but here is the simple version:
When you have two people learning at the same time, their progress is linked. If Player A learns faster, it changes the environment for Player B, which changes how Player B learns, which changes Player A again. It's a tangled web.

The authors built a mathematical "safety net" (called a Coupled Lyapunov-Drift framework).

The Analogy: Imagine two hikers climbing a mountain in a fog, holding a long rope between them. They can't see the top, but they can feel the tension in the rope.
The authors created a mathematical tool that tracks the "tension" (the error) in the rope. They proved that no matter how the hikers stumble or how the fog shifts, the tension in the rope will eventually decrease, pulling them both toward the summit (the perfect strategy). This tool allows them to mathematically guarantee that the learning process won't spiral out of control.

Summary of Claims

Decentralized: Players don't need to talk or see each other; they only need their own score.
Symmetric: Both players use the exact same learning rules.
Fast Enough: By adding a little bit of random "exploration," the players can find the perfect strategy in a time that is mathematically predictable and efficient (specifically, the time grows with the 8th power of the desired accuracy, which is a significant improvement over previous methods for this specific type of algorithm).
Robust: The math holds up even when the game is complex and changing over time.

In short, the paper provides a mathematical proof that two stubborn, silent competitors can learn to play the perfect game against each other, provided they are willing to occasionally try a random move to learn something new.

Technical Summary: Decentralized Best-Response-Based Learning in Two-Player Zero-Sum Stochastic Games

1. Problem Formulation

The paper addresses the challenge of decentralized learning in two-player zero-sum games, specifically focusing on matrix games and infinite-horizon discounted stochastic (Markov) games. The setting is characterized by:

Decentralization: Players observe only their own state and realized payoffs. They do not have access to the opponent's policy, actions, or the game's transition/reward matrices (model-free).
Independence: Players update their policies without explicit coordination or communication.
Rationality: The learning dynamics should ensure that if an opponent plays a stationary policy, the player converges to a best response.
Goal: To establish finite-sample guarantees (sample complexity) for finding an $\epsilon$ -Nash equilibrium (NE) or $\epsilon$ -Nash distribution, moving beyond traditional asymptotic convergence analyses.

The paper focuses on best-response-based learning algorithms, where players incrementally update their policies toward an estimated smoothed best response to the opponent's current strategy.

2. Methodology

The authors propose and analyze two primary algorithms, one for matrix games and an extension for stochastic games.

A. Matrix Games: Payoff-Based Decentralized Learning
The authors analyze an algorithm (Algorithm 1) originally proposed in [36], which operates on a single timescale (or with a multiplicative stepsize difference) using only payoff feedback.

Mechanism: Each player maintains a $q$ -function to estimate the opponent's policy-weighted payoff matrix ( $R_i \pi_{-i}$ ). The policy is updated via a smoothed best response (softmax) of this estimated $q$ -function.
Exploration Issue: The standard softmax policy leads to a lower bound on action probabilities that is exponentially small in the temperature parameter $\tau$ . This "lack of exploration" causes sample complexity bounds for finding an $\epsilon$ -NE to be exponential in $\epsilon^{-1}$ .
Solution: The authors introduce an $\bar{\epsilon}$ -exploration variant (Algorithm 2). This modifies the policy update to include a uniform exploration component: $\sigma_{\bar{\epsilon}}^\tau(q) = \bar{\epsilon} \cdot \text{Unif} + (1-\bar{\epsilon}) \cdot \sigma^\tau(q)$ . This ensures a uniform lower bound on action probabilities that is polynomial in the parameters, enabling polynomial sample complexity.

B. Stochastic Games: Value Iteration with Smoothed Best-Response (VI-SBR)
For stochastic games, the authors develop Algorithm 3 (VI-SBR), which combines the matrix-game primitive with minimax value iteration.

Structure: The algorithm features an outer loop performing decentralized, model-free minimax value iteration and an inner loop running the smoothed best-response learning for induced auxiliary matrix games at each state.
Key Challenge: In a decentralized setting, players maintain independent value functions ( $v^1_t, v^2_t$ ). Consequently, the induced auxiliary matrix games at each state are not exactly zero-sum during the learning process ( $T^1(v^1_t) + T^2(v^2_t) \neq 0$ ).
Exploration Enhancement: Similar to the matrix game case, the authors propose Algorithm 4 (VI-SBR with $\bar{\epsilon}$ -Exploration) to ensure polynomial sample complexity.

3. Technical Contributions and Framework

The core technical contribution is the development of a Coupled Lyapunov-Drift Framework to handle the complex interactions in decentralized learning.

Coupled Iterates: The analysis must simultaneously track multiple interacting stochastic iterates: policies ( $\pi$ ), local $q$ -functions ( $q$ ), and value functions ( $v$ ).
Non-Zero-Sum Auxiliary Games: The framework introduces a Lyapunov function ( $L_{sum}$ ) to track the error induced by the non-zero-sum nature of the auxiliary games caused by independent value function updates.
Time-Inhomogeneous Noise: The analysis accounts for Markovian noise generated by time-varying policies, utilizing mixing-time arguments and sensitivity analysis of stationary distributions.
Decoupling Strategy: The authors solve the system of coupled Lyapunov drift inequalities through a bootstrapping procedure:
1. Derive a crude bound on the $q$ -function error.
2. Substitute this back to tighten the bound on the policy error.
3. Use the tightened bounds to decouple the value function updates from the inner-loop errors.

4. Key Results

Matrix Games:

Nash Distribution: The algorithm achieves a sample complexity of $O(\epsilon^{-1})$ for finding an $\epsilon$ -Nash distribution (measured by the regularized Nash gap).
Nash Equilibrium: With the exploration-enhanced variant (Algorithm 2), the sample complexity for finding an $\epsilon$ -Nash equilibrium is $\tilde{O}(\epsilon^{-8})$ . This is the first finite-sample guarantee for a payoff-based, symmetric, and decentralized best-response algorithm in this setting.

Stochastic Games:

Nash Equilibrium: The exploration-enhanced VI-SBR algorithm (Algorithm 4) achieves a sample complexity of $\tilde{O}(\epsilon^{-8})$ for finding an $\epsilon$ -Nash equilibrium.
Rationality: The paper also proves that if the opponent plays a stationary policy, the player achieves a best response with $\tilde{O}(\epsilon^{-8})$ sample complexity, satisfying the rationality property.

5. Significance and Claims

The paper claims to provide the first finite-sample analysis of decentralized, best-response-based learning algorithms for two-player zero-sum stochastic games that simultaneously satisfy:

Decentralization: No coordination or knowledge of the opponent's policy.
Convergence: Provable finite-sample convergence to an $\epsilon$ -Nash equilibrium.
Rationality: Convergence to a best response against stationary opponents.
Polynomial Complexity: The sample complexity is polynomial in $\epsilon^{-1}$ (specifically $\tilde{O}(\epsilon^{-8})$ ), overcoming the exponential dependence found in previous analyses of similar natural dynamics.

The authors note that while their bounds are $\tilde{O}(\epsilon^{-8})$ , concurrent work using mirror-descent-based methods has achieved better rates (e.g., $\tilde{O}(\epsilon^{-4})$ to $\tilde{O}(\epsilon^{-5})$ ). However, the significance of this work lies in analyzing the natural best-response dynamics (as opposed to mirror descent) and extending them to the stochastic game setting with a novel coupled Lyapunov framework. The paper acknowledges that the current bounds are likely not optimal and that extending these results to function approximation settings is a necessary future direction.