Fast Policy Extragradient Methods For Competitive Games With Entropy Regularization

Abstract

This paper investigates the problem of computing the equilibrium of competitive games, which is often modeled as a constrained saddle-point optimization problem with probability simplex constraints. Despite recent efforts in understanding the last-iterate convergence of extragradient methods in the unconstrained setting, the theoretical underpinnings of these methods in the constrained settings, especially those using multiplicative updates, remain highly inadequate, even when the objective function is bilinear. Motivated by the algorithmic role of entropy regularization in single-agent reinforcement learning and game theory, we develop provably efficient extragradient methods to find the quantal response equilibrium (QRE) -- which are solutions to zero-sum two-player matrix games with entropy regularization -- at a linear rate. The proposed algorithms can be implemented in a decentralized manner, where each player executes symmetric and multiplicative updates iteratively using its own

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keycen2021fast

Related papers

• Linear Convergence Of Independent Natural Policy Gradient In Games With Entropy Regularization (2024)3.58
• Policy Optimization Finds Nash Equilibrium In Regularized General-sum LQ Games (2024)0.00
• Asynchronous Gradient Play In Zero-sum Multi-agent Games (2022)0.00
• Decoding Rewards In Competitive Games: Inverse Game Theory With Entropy Regularization (2026)0.00
• Learning Nash Equilibria In Zero-sum Stochastic Games Via Entropy-regularized Policy Approximation (2020)0.00
• Entropy Regularization For Mean Field Games With Learning (2020)0.00
• Beyond Exact Gradients: Convergence Of Stochastic Soft-max Policy Gradient Methods With Entropy Regularization (2021)2.26
• Independent Policy Gradient Methods For Competitive Reinforcement Learning (2021)0.00