Major Research Breakthrough in High-Dimensional Complex System Decision-Making at Nanjing University's School of Intelligent Science and Technology
Recently, the School of Intelligence Science and Technology at Nanjing University has achieved a significant research breakthrough in the field of high-dimensional complex system decision-making. Assistant Professor Yang Tianpei, from the research group of Professor Gao Yang, has proposed a novel surrogate loss function named the Nash Advantage Loss (NAL) to address the critical efficiency bottleneck in computing Nash Equilibria for multi-player general-sum games.
The NAL method achieves faster and more stable convergence to Nash Equilibria by significantly reducing variance during stochastic optimization, thereby establishing a new and highly efficient computational paradigm for solving large-scale multi-agent interaction problems.
The Nash Equilibrium, a cornerstone of game theory, describes a stable state in a strategic environment where no participant can gain an advantage by unilaterally changing their strategy. Its precise computation is vital across diverse fields such as artificial intelligence, economics, computational advertising, and multi-agent reinforcement learning. However, as the number of participants and available strategies increases, the computational complexity for storing and processing the entire game payoff matrix grows exponentially—a phenomenon known as the curse of dimensionality. This renders traditional computational methods infeasible for large-scale, real-world problems.
To tackle this challenge, researchers have turned to stochastic optimization techniques from machine learning, which approximate Nash Equilibria by sampling from the game. While promising, existing methods are consistently plagued by the high variance problem. During the sampling process, the estimated value of the loss function experiences substantial fluctuations—akin to navigating through thick fog—leading to slow algorithm convergence, highly unstable training processes, and frequent failure to reach a valid equilibrium point.
To overcome this core difficulty, the research group adopted a novel approach. Starting from the fundamental requirements of stochastic optimization, they innovatively designed the NAL loss function. The key insight is that common stochastic optimization algorithms (e.g., Adam, SGD) require only an unbiased estimate of the gradient when updating parameters, not an unbiased estimate of the loss function itself. Building on this, NAL is skillfully constructed as a surrogate loss function. It theoretically guarantees gradient unbiasedness while successfully circumventing the quadratic growth in variance inherent in existing methods—variance caused by the inner product of two independent random variables. This design suppresses the source of variance at its root, providing the optimization algorithm with a much clearer and more stable field of view.
Figure 1: Comparative Experimental Results
To comprehensively evaluate the performance of NAL, the research team conducted extensive and in-depth experiments on multiple internationally recognized game theory algorithm testing platforms, including OpenSpiel and GAMUT. The results demonstrate that across various representative complex game scenarios, such as Kuhn Poker and Liar's Dice, the algorithm minimizing NAL comprehensively and significantly outperformed all existing baseline algorithms in terms of convergence speed, stability, and the quality of the final solution. Notably, in some large-scale games, NAL reduced estimation variance by up to six orders of magnitude, dramatically enhancing learning efficiency.
This research outcome not only provides a powerful new tool for efficiently solving large-scale game problems but also opens up new research directions for the deep integration of optimization theory and machine learning. It is expected to play a significant role in cutting-edge applications such as large-scale economic system modeling, multi-agent collaboration and competition, and policy alignment for large language models.
The related research paper, titled Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games, has been accepted as a Spotlight Poster (top 2.6%) by the 42nd International Conference on Machine Learning (ICML 2025), a premier international academic conference in the field of artificial intelligence. This achievement fully demonstrates the robust research capabilities and innovative strength of the School of Intelligent Science and Technology at Nanjing University in fundamental AI theory and frontier algorithm development.
