Bilevel Optimization for Zero-Sum Markov Games with PANDA Algorithm

Researchers propose PANDA, a penalty-based first-order policy-gradient method for bilevel optimization where the lower-level problem is a regularized min-max zero-sum Markov game. Unlike existing bilevel RL methods that assume a single-policy lower-level MDP, PANDA handles competitive structures arising in applications like incentive design. The method exploits the Nikaido-Isoda function to avoid computing upper-level hypergradients and does not require second-order information. This work addresses a gap in hierarchical RL with multiple interacting policies.