PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash
Equilibrium
- URL: http://arxiv.org/abs/2303.00970v2
- Date: Mon, 20 Nov 2023 22:51:36 GMT
- Title: PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash
Equilibrium
- Authors: Shihong Ding, Hanze Dong, Cong Fang, Zhouchen Lin, Tong Zhang
- Abstract summary: We consider the non-AL equilibrium nonconptotic objective function in two-player zero-sum continuous games.
The proposed algorithm employs the movements of particles to represent the updates of random strategies for the $ilon$-mixed Nash equilibrium.
- Score: 62.51015395213579
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the non-convex non-concave objective function in two-player
zero-sum continuous games. The existence of pure Nash equilibrium requires
stringent conditions, posing a major challenge for this problem. To circumvent
this difficulty, we examine the problem of identifying a mixed Nash
equilibrium, where strategies are randomized and characterized by probability
distributions over continuous domains.To this end, we propose PArticle-based
Primal-dual ALgorithm (PAPAL) tailored for a weakly entropy-regularized min-max
optimization over probability distributions. This algorithm employs the
stochastic movements of particles to represent the updates of random strategies
for the $\epsilon$-mixed Nash equilibrium. We offer a comprehensive convergence
analysis of the proposed algorithm, demonstrating its effectiveness. In
contrast to prior research that attempted to update particle importance without
movements, PAPAL is the first implementable particle-based algorithm
accompanied by non-asymptotic quantitative convergence results, running time,
and sample complexity guarantees. Our framework contributes novel insights into
the particle-based algorithms for continuous min-max optimization in the
general non-convex non-concave setting.
Related papers
- Learning Nash Equilibria in Zero-Sum Markov Games: A Single Time-scale Algorithm Under Weak Reachability [11.793922711718645]
We consider decentralized learning for zero-sum games, where players only see their information and are to actions and payoffs of the opponent.
Previous works demonstrated convergence to a Nash equilibrium in this setting using double time-scale algorithms under strong reachability assumptions.
Our contribution is a rational and convergent algorithm, utilizing Tsallis-entropy regularization in a value-iteration-based algorithm.
arXiv Detail & Related papers (2023-12-13T09:31:30Z) - Can Decentralized Stochastic Minimax Optimization Algorithms Converge
Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
Decentralized minimax optimization has been actively studied in the past few years due to its application in a wide range machine learning.
This paper develops two novel decentralized minimax optimization algorithms for the non-strongly-nonconcave problem.
arXiv Detail & Related papers (2023-04-24T02:19:39Z) - An Exponentially Converging Particle Method for the Mixed Nash
Equilibrium of Continuous Games [0.0]
We consider the problem of computing mixed Nash equilibria of two-player zero-sum games with continuous sets of pure strategies and with first-order access to the payoff function.
This problem arises for example in game-inspired machine learning applications, such as distributionally-robust learning.
We introduce and analyze a particle-based method that enjoys guaranteed local convergence for this problem.
arXiv Detail & Related papers (2022-11-02T17:03:40Z) - Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games [16.09467599829253]
We study the problem of finding Nash equilibrium in a two-player zero-sum game.
Our main contribution is to show that under proper choices of the regularization parameter, the gradient descents to the Nash equilibrium of the original unregularized problem.
arXiv Detail & Related papers (2022-05-27T03:24:12Z) - First-Order Algorithms for Nonlinear Generalized Nash Equilibrium
Problems [88.58409977434269]
We consider the problem of computing an equilibrium in a class of nonlinear generalized Nash equilibrium problems (NGNEPs)
Our contribution is to provide two simple first-order algorithmic frameworks based on the quadratic penalty method and the augmented Lagrangian method.
We provide nonasymptotic theoretical guarantees for these algorithms.
arXiv Detail & Related papers (2022-04-07T00:11:05Z) - Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth
Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO.
We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size.
Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
arXiv Detail & Related papers (2021-06-30T18:32:46Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence.
We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
arXiv Detail & Related papers (2021-06-30T17:51:36Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
It is essential to theoretically guarantee that algorithms provide small objective residual with high probability.
Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level.
We propose novel stepsize rules for two methods with gradient clipping.
arXiv Detail & Related papers (2021-06-10T17:54:21Z) - Stochastic optimization with momentum: convergence, fluctuations, and
traps avoidance [0.0]
In this paper, a general optimization procedure is studied, unifying several variants of the gradient descent such as, among others, the heavy ball method, the Nesterov Accelerated Gradient (S-NAG), and the widely used Adam method.
The avoidance is studied as a noisy discretization of a non-autonomous ordinary differential equation.
arXiv Detail & Related papers (2020-12-07T19:14:49Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.