Function Approximation for Solving Stackelberg Equilibrium in Large Perfect Information Games
This work addresses a computationally difficult problem in game theory for applications like multi-agent systems, representing an incremental advance by extending function approximation techniques from zero-sum to general-sum games.
The paper tackles the challenge of solving large general-sum extensive-form games by proposing a function approximation method for the Stackelberg extensive-form correlated equilibrium, achieving scalability to larger games with performance guarantees based on approximation error.
Function approximation (FA) has been a critical component in solving large zero-sum games. Yet, little attention has been given towards FA in solving \textit{general-sum} extensive-form games, despite them being widely regarded as being computationally more challenging than their fully competitive or cooperative counterparts. A key challenge is that for many equilibria in general-sum games, no simple analogue to the state value function used in Markov Decision Processes and zero-sum games exists. In this paper, we propose learning the \textit{Enforceable Payoff Frontier} (EPF) -- a generalization of the state value function for general-sum games. We approximate the optimal \textit{Stackelberg extensive-form correlated equilibrium} by representing EPFs with neural networks and training them by using appropriate backup operations and loss functions. This is the first method that applies FA to the Stackelberg setting, allowing us to scale to much larger games while still enjoying performance guarantees based on FA error. Additionally, our proposed method guarantees incentive compatibility and is easy to evaluate without having to depend on self-play or approximate best-response oracles.