A Policy-Gradient Approach to Solving Imperfect-Information Games with Iterate Convergence
Policy gradient methods have become a staple of any single-agent reinforcement learning toolbox, due to their combination of desirable properties: iterate convergence, efficient use of stochastic trajectory feedback, and theoretically-sound avoidance of importance sampling corrections. In multi-agent imperfect-information settings (extensive-form games), however, it is still unknown whether the same desiderata can be guaranteed while retaining theoretical guarantees. Instead, sound methods for extensive-form games rely on approximating counterfactual values (as opposed to Q values), which are incompatible with policy gradient methodologies. In this paper, we investigate whether policy gradient can be safely used in two-player zero-sum imperfect-information extensive-form games (EFGs). We establish positive results, showing for the first time that a policy gradient method leads to provable best-iterate convergence to a regularized Nash equilibrium in self-play.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Reevaluating Policy Gradient Methods for Imperfect-Information Games
In the past decade, motivated by the putative failure of naive self-play deep reinforcement learning (DRL) in adversarial imperfect-information games, researchers have developed numerous DRL algorithms based on fictitiou…
counterfactualDeep Reinforcement LearningPolicy Gradient MethodsData-Augmented Game Starts for Accelerating Self-Play Exploration in Imperfect Information Games
Finding approximate equilibria for large-scale imperfect-information competitive games such as StarCraft, Dota, and CounterStrike remains computationally infeasible due to sparse rewards and challenging exploration over …
Reinforcement LearningEMAgnet: Parameter-Space EMA Regularization for Policy Gradient Self-Play in Large Games
Recent work has established that regularized policy gradient methods such as PPO, when used in self-play, can match or exceed specialized game-theoretic algorithms for solving two-player zero-sum imperfect-information ga…
Joint Policy Search for Multi-agent Collaboration with Imperfect Information
To learn good joint policies for multi-agent collaboration with imperfect information remains a fundamental challenge. While for two-player zero-sum games, coordinate-ascent approaches (optimizing one agent's policy at a…
Beyond Outcome-Based Imperfect-Recall: Higher-Resolution Abstractions for Imperfect-Information Games
Hand abstraction is crucial for scaling imperfect-information games (IIGs) such as Texas Hold'em, yet progress is limited by the lack of a formal task model and by evaluations that require resource-intensive strategy sol…