📊 statistics

Bilevel Optimization over Saddle Points of Zero-Sum Markov Games

This paper proposes PANDA, a penalty-based first-order policy-gradient method that efficiently solves bilevel optimization problems where the lower level is a zero-sum Markov game, achieving convergence to stationary points with optimal sample complexity without requiring second-order information or convexity assumptions.

Original authors: Zihao Zheng, Irwin King, Songtao Lu

Published 2026-05-27

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Zihao Zheng, Irwin King, Songtao Lu

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 you are the Mayor of a city (the Upper Level), and you want to design a new traffic system. However, you don't drive the cars yourself. Instead, you set the rules (like speed limits or toll prices), and then two rival groups of drivers—the "Speeders" and the "Cautious Drivers"—react to your rules.

These two groups are constantly playing a game against each other. The Speeders want to go as fast as possible, while the Cautious Drivers want to avoid accidents. They adjust their driving styles based on the Mayor's rules and each other's moves until they reach a "stalemate" where neither side wants to change their strategy. This stalemate is called a Saddle Point or an Equilibrium.

The Problem:
Most previous computer programs trying to help the Mayor were designed for a simpler world where there was only one group of drivers (a single policy). They assumed the drivers just reacted to the Mayor without fighting each other. But in the real world, drivers compete. When the Mayor changes a rule, the Speeders and Cautious Drivers change their strategies simultaneously in response to each other. This makes the math incredibly hard. If you try to use the old methods, the computer gets confused because it doesn't know how to calculate the "best" reaction when two enemies are reacting at the same time.

The Solution: PANDA
The authors of this paper created a new algorithm called PANDA (Penalty-Augmented Nikaido–Isoda Descent–Ascent). Here is how it works, using a simple analogy:

The "Penalty" Trick:
Imagine the Mayor wants to make sure the drivers actually reach a fair stalemate before she judges her own success. Instead of trying to calculate the complex math of "what if they change their minds?" (which requires expensive second-order math), PANDA uses a Penalty.
- If the drivers are not at a fair stalemate, PANDA adds a "fine" (a penalty) to the Mayor's score.
- The algorithm then tries to minimize the Mayor's score plus these fines.
- By pushing the drivers to pay fewer fines, the algorithm naturally forces them into that fair stalemate.
The "Descent-Ascent" Dance:
Inside the algorithm, there is a constant dance:
- The "Speeder" driver tries to descend (lower) their cost.
- The "Cautious" driver tries to ascend (raise) their cost (since they are the "max" player in a zero-sum game).
- PANDA coordinates this dance so they find their balance point quickly, without needing to know the exact curvature of the road (second-order derivatives), which saves a massive amount of computing power.
Why It's Special:
- No Heavy Lifting: Previous methods tried to calculate complex "hyper-gradients" (gradients of gradients) to see how the Mayor's rules affect the drivers' equilibrium. This is like trying to predict the weather by calculating every single molecule's movement. PANDA avoids this heavy math.
- Speed: The paper proves that PANDA finds a good solution in a number of steps that is as fast as the best methods for the simpler, single-driver problems. It achieves this efficiency even though it's dealing with two competing drivers.
- Sample Efficiency: In the real world, you don't have a perfect map; you have to learn by driving (sampling). PANDA is proven to learn the best rules using a number of driving samples that is theoretically optimal.

The Results:
The authors tested PANDA in two scenarios:

A Synthetic Incentive Game: A made-up world where a designer tries to reward two competing agents to cooperate. PANDA found better rewards for the designer than other methods.
Sentinel vs. Intruder: A grid-world game where a "Sentinel" tries to catch an "Intruder." The Mayor (Upper Level) wants to set rules so the Sentinel avoids dangerous "restricted zones" while still trying to catch the Intruder. PANDA successfully taught the Sentinel to avoid the danger zones better than other algorithms, all while the Sentinel and Intruder played their competitive game.

In Summary:
PANDA is a smart, efficient way for a "boss" (Upper Level) to set rules for a "competitive team" (Lower Level) where two members are fighting each other. It uses a clever "fine" system to force the team into a fair balance, allowing the boss to optimize their goals without getting bogged down in impossible math. It works fast, uses fewer data samples, and outperforms current methods in these competitive settings.

Technical Summary: Bilevel Optimization over Saddle Points of Zero-Sum Markov Games

1. Problem Formulation

This work addresses Bilevel Reinforcement Learning (BRL) in settings where the lower-level (LL) problem is not a standard single-policy Markov Decision Process (MDP), but rather a regularized min–max zero-sum Markov game (MMZSMG).

In this hierarchical framework:

Upper-Level (UL): An optimizer selects parameters $x$ (e.g., incentive structures or reward shaping) to minimize an objective $f(x, \phi, \psi)$ .
Lower-Level (LL): Two opposing agents (min-player with policy $\pi_\phi$ and max-player with policy $\pi_\psi$ ) interact in a Markov game parameterized by $x$ . They seek a saddle-point equilibrium (Nash Equilibrium) that solves:
$(\phi^*(x), \psi^*(x)) \in \arg\min_{\phi'} \max_{\psi'} J(x, \phi', \psi')$
where $J$ is the regularized value function of the game.
Objective: The UL objective is evaluated at the equilibrium induced by the LL game:
$\min_x F(x) \equiv f(x, \phi^*(x), \psi^*(x))$

The core challenge lies in the strategic coupling between the two LL players. Unlike single-policy MDPs, the optimal response of one player depends on the other's behavior, making the computation of hypergradients (derivatives of the UL objective with respect to $x$ ) computationally expensive and structurally complex. Existing BRL methods often rely on second-order information (Hessian inverses) or structural assumptions specific to single-policy MDPs, which fail to generalize to the coupled min–max structure of MMZSMGs.

2. Methodology: PANDA

The authors propose PANDA (Penalty-Augmented Nikaido–Isoda Descent–Ascent), a first-order stochastic policy-gradient algorithm designed to solve this Bilevel Optimization over Saddle Points of Markov Games (BOSMG) without requiring second-order derivatives.

Key Components:

Penalty-Based Reformulation:
Instead of computing hypergradients directly, PANDA reformulates the constrained bilevel problem using the Nikaido–Isoda (NI) function, $g(x, \phi, \psi)$ , which measures the gap between the current policy pair and the Nash Equilibrium. The constrained problem is transformed into an unconstrained penalized objective:
$L_\lambda(x, \phi, \psi) = f(x, \phi, \psi) + \lambda g(x, \phi, \psi)$
where $\lambda$ is a penalty parameter.
Three-Step Iterative Algorithm:
The algorithm operates in an outer loop (updating $x$ ) and an inner loop (updating policies $\phi, \psi$ ):
- Step 1: Best-Response Approximation: The algorithm approximates the best-response policies ( $\tilde{\phi}, \tilde{\psi}$ ) for the current policies using policy-gradient descent (for the min-player) and ascent (for the max-player). This allows the estimation of the NI function $g(x, \phi, \psi) \approx J(x, \phi, \tilde{\psi}) - J(x, \tilde{\phi}, \psi)$ .
- Step 2: Penalty-Subproblem Approximation: The algorithm updates the policy parameters $(\phi, \psi)$ via stochastic gradient descent to minimize the penalized surrogate objective $h(x, \phi, \psi) = \frac{1}{\lambda}f(x, \phi, \psi) + g(x, \phi, \psi)$ . This step drives the LL policies toward the saddle point.
- Step 3: Hypergradient Step: The UL parameter $x$ is updated using a stochastic gradient estimate of the penalized objective $L_\lambda$ . Crucially, this gradient is computed using first-order information from the sampled trajectories, avoiding the inversion of the LL Hessian.
Stochastic Estimation:
The method relies on Monte Carlo roll-outs with truncated horizons to estimate gradients for the value functions and the NI gap, making it suitable for large-scale, sample-based settings.

3. Theoretical Contributions

The paper establishes rigorous convergence guarantees for PANDA under standard assumptions (bounded rewards, Lipschitz continuity, and Polyak-Łojasiewicz (PŁ) conditions).

Convergence to Stationary Points: PANDA is proven to converge to an $\epsilon$ -stationary point of the original bilevel problem without requiring convexity assumptions on either the UL or LL objectives.
Complexity Bounds:
- Iteration Complexity: $\tilde{O}(\epsilon^{-1})$ outer iterations.
- Sample Complexity: $\tilde{O}(\epsilon^{-3})$ .
  These rates match the state-of-the-art bounds previously known only for BRL with single-policy LL MDPs, despite the added complexity of the coupled min–max game.
Structural Properties: The authors prove new structural results for regularized MMZSMGs, including:
- The uniqueness of the equilibrium policy pair under general regularization.
- The non-uniform PŁ property of the NI function with respect to the policy parameters, which is critical for the convergence analysis.
- Smoothness and Lipschitz continuity properties of the NI function and the hyper-objective.

4. Experimental Results

The authors validate PANDA through numerical experiments in two settings:

Synthetic Incentive Design Problem:
- Setup: A UL designer sets incentives to influence two competing agents in a small MDP.
- Baselines: Compared against Meta-Gradient (heuristic), Differentiable Arbitrating (DA, second-order), and PBRL (penalty-based single-policy).
- Results: PANDA achieves the highest UL incentive reward and converges to a Nash Equilibrium (NE) gap near zero. It performs comparably to an "Oracle" baseline that uses exact dynamic programming and second-order information, significantly outperforming other first-order baselines.
Sentinel-Intruder Game:
- Setup: A grid-world game where a sentinel tries to capture an intruder. The UL objective is to minimize the sentinel's visits to restricted (dangerous) areas while maintaining competitive play.
- Scale: Tested on $5 \times 5$ and $20 \times 20$ grids.
- Results: PANDA consistently achieves lower UL loss (fewer restricted area visits) and smaller NE gaps compared to DA, PBRL, and Meta-Gradient, demonstrating scalability and robustness in larger, more complex environments.

5. Significance and Claims

The paper claims that PANDA is the first stochastic first-order algorithm with provable convergence guarantees for bilevel problems where the lower level is a regularized MMZSMG.

Bridging the Gap: It addresses a critical gap in BRL literature where existing methods fail to handle competitive multi-agent interactions at the lower level efficiently.
Efficiency: By avoiding second-order information (Hessian inversion), PANDA remains computationally feasible for large-scale problems while achieving sample complexity rates ( $\tilde{O}(\epsilon^{-3})$ ) that match the best-known results for simpler single-policy settings.
Practical Applicability: The method is designed for sample-based settings, making it directly applicable to real-world scenarios like incentive design, mechanism design, and adversarial training where competitive equilibria are central.

The authors conclude that while their current work focuses on regularized MMZSMGs, the framework offers a promising direction for extending bilevel optimization to general min–max games and broader multi-agent settings.