# Bilevel Optimization over Saddle Points of Zero-Sum Markov Games

arXiv: https://arxiv.org/abs/2605.26654 · HTML: https://mlsanity.com/paper/2605.26654/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Multi-agent reinforcement learning, one of 15 directions in Deep reinforcement learning methods.
- Builds on 4 of its 55 references that are in the map.
- First posted on arXiv 26 May 2026.

## Placed in

- Deep reinforcement learning methods / [Multi-agent reinforcement learning](https://mlsanity.com/deeprl/multi-agent-reinforcement-learning/)

## Builds on (most cited first, 4 of 4)

- [Direct Nash Optimization: Teaching Language Models to Self-Improve with General Preferences](https://mlsanity.com/paper/2404.03715/) (2024)
- [Language Self-Play For Data-Free Training](https://mlsanity.com/paper/2509.07414/) (2025)
- [Extragradient Preference Optimization (EGPO): Beyond Last-Iterate Convergence for Nash Learning from Human Feedback](https://mlsanity.com/paper/2503.08942/) (2025)
- [Achieving Logarithmic Regret in KL-Regularized Zero-Sum Markov Games](https://mlsanity.com/paper/2510.13060/) (2025)

## Abstract (arXiv)

Reinforcement learning (RL) often has a hierarchical structure, where an upper-level (UL) learner selects model parameters and a lower-level (LL) decision-making process responds, naturally leading to a bilevel optimization problem. Most existing bilevel RL methods assume a single-policy LL Markov decision process (MDP), and therefore fail to capture competitive structures arising in applications such as incentive design, where multiple policies interact. We study bilevel optimization problems in which the LL problem is a regularized min-max zero-sum Markov game and the UL objective is optimized through the saddle-point equilibrium induced by the LL game. In this work, we propose penalty-augmented Nikaido-Isoda descent-ascent (PANDA), a penalty-based first-order policy-gradient method based on the Nikaido-Isoda function. By exploiting the min-max game structure, PANDA avoids computing UL hypergradients and does not require second-order information. We prove that PANDA converges to stationary points without convexity assumptions on either the UL or LL objectives. Moreover, PANDA reaches an ε-stationary point in tildeO(ε-1) iterations with sample complexity tildeO(ε-3), matching the best-known rates for bilevel RL with single-policy LL MDPs. Experiments demonstrate the superior performance of PANDA over closely related baselines.