New decentralized algorithm learns equilibrium in bounded-rational games

A team of researchers from computer science and game theory has introduced an efficient decentralized learning algorithm for Generalized Quantal Response Equilibrium (GQRE), a solution concept that models bounded rationality in strategic interactions. GQRE generalizes the classic Quantal Response Equilibrium by allowing each player to maximize a smooth, regularized expected utility, reflecting both stochastic choice and individual behavior preferences. The authors prove existence under mild conditions and then present a computationally efficient no-regret learning algorithm based on a smoothened version of the Frank-Wolfe method. Their algorithm operates using noisy gradient estimates obtained via bandit feedback from a simulation oracle that reports on repeated plays of the game.

The approach includes a finite-time convergence analysis under assumptions that guarantee a unique equilibrium, leveraging a novel class of gap functions that extend the traditional Nash gap. Empirical validation on complex general-sum games—such as high-rank two-player games, large-action two-player games, and difficult multiplayer examples—demonstrates the method's effectiveness. This work bridges theoretical game theory and practical multi-agent learning, offering a scalable solution for environments where agents have limited computational resources or imperfect rationality, such as in economics, autonomous systems, and AI coordination tasks.