Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games
원문 초록
We study the problem of finding the Nash equilibrium in a two-player zero-sum Markov game. Due to its formulation as a minimax optimization program, a natural approach to solve the problem is to perform gradient descent/ascent with respect to each player in an alternating fashion. However, due to the non-convexity/non-concavity of the underlying objective function, theoretical understandings of this method are limited. In our paper, we consider solving an entropy-regularized variant of the Markov game. The regularization introduces structure into the optimization landscape that make the solutions more identifiable and allow the problem to be solved more efficiently. Our main contribution is to show that under proper choices of the regularization parameter, the gradient descent ascent algorithm converges to the Nash equilibrium of the original unregularized problem. We explicitly characterize the finite-time performance of the last iterate of our algorithm, which vastly improves over the existing convergence bound of the gradient descent ascent algorithm without regularization. Finally, we complement the analysis with numerical simulations that illustrate the accelerated convergence of the algorithm.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Quantile-Based Deep Reinforcement Learning using Two-Timescale Policy Gradient Algorithms
Leveraging the two timescale regime to demonstrate convergence of neural networks
Training a Two Layer ReLU Network Analytically
MiniRBT: A Two-stage Distilled Small Chinese Pre-trained Model
FinalMLP: An Enhanced Two-Stream MLP Model for CTR Prediction
Using Simple Incentives to Improve Two-Sided Fairness in Ridesharing Systems
토론
이 논문과 연결된 포럼 글이 아직 없습니다.