Competitive Policy Optimization

Abstract

A core challenge in policy optimization in competitive Markov decision processes is the design of efficient optimization methods with desirable convergence and stability properties. To tackle this, we propose competitive policy optimization (CoPO), a novel policy gradient approach that exploits the game-theoretic nature of competitive games to derive policy updates. Motivated by the competitive gradient optimization method, we derive a bilinear approximation of the game objective. In contrast, off-the-shelf policy gradient methods utilize only linear approximations, and hence do not capture interactions among the players. We instantiate CoPO in two ways:(i) competitive policy gradient, and (ii) trust-region competitive policy optimization. We theoretically study these methods, and empirically investigate their behavior on a set of comprehensive, yet challenging, competitive games. We observe that they provide stable optimization, convergence to sophisticated strategies, and higher scores when played against baseline policy gradient methods.

11 pages main paper, 6 pages references, and 31 pages appendix. 14 figures

References in corpus (12)

• DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker
• A Survey and Critique of Multiagent Deep Reinforcement Learning
• Optimization-Based Autonomous Racing of 1:43 Scale RC Cars
• Counterfactual Multi-Agent Policy Gradients
• Actor-Critic Policy Optimization in Partially Observable Multiagent Environments
• Modeling Others using Oneself in Multi-Agent Reinforcement Learning
• Global Convergence to the Equilibrium of GANs using Variational Inequalities
• Can Deep Reinforcement Learning Solve Erdos-Selfridge-Spencer Games?
• No-Regret Learning in Bayesian Games
• Implicit competitive regularization in GANs
• Policy-Gradient Algorithms Have No Guarantees of Convergence in Linear Quadratic Games
• Policy Gradient in Partially Observable Environments: Approximation and Convergence