Bilevel Optimization over Saddle Points of Zero-Sum Markov Games

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 $\epsilon$-stationary point in $\tilde{\mathcal{O}}(\epsilon^{-1})$ iterations with sample complexity $\tilde{\mathcal{O}}(\epsilon^{-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.

Many reinforcement learning (RL) problems involve two levels of decision-making. For example, an upper-level (UL) learner may set rules or incentives, while lower-level (LL) decision-makers respond strategically to those choices. Existing bilevel RL methods usually assume that the LL decision process involves only one policy, which makes them less suitable for competitive settings where two sides interact with conflicting goals. This paper studies a more general setting where the LL problem is a regularized two-player zero-sum Markov game. We propose PANDA, a new first-order learning algorithm for solving this type of bilevel RL problem. PANDA uses a penalty-based formulation and a game-theoretic measure called the Nikaido–Isoda function to guide learning, avoiding expensive second-order computations and difficult hypergradient calculations. We prove that PANDA converges under broad conditions, without requiring the UL or LL objectives to be convex. Our theoretical rates match the best known results for simpler bilevel RL settings, and experiments show that PANDA performs better than closely related baselines. This work provides a more practical foundation for learning in hierarchical RL problems with strategic competition.