Timezone: »

 
Poster
A Natural Actor-Critic Framework for Zero-Sum Markov Games
Ahmet Alacaoglu · Luca Viano · Niao He · Volkan Cevher

Wed Jul 20 03:30 PM -- 05:30 PM (PDT) @ Hall E #928
in Poster Session 2 »

We introduce algorithms based on natural actor-critic and analyze their sample complexity for solving two player zero-sum Markov games in the tabular case. Our results improve the best-known sample complexities of policy gradient/actor-critic methods for convergence to Nash equilibrium in the multi-agent setting. We use the error propagation scheme in approximate dynamic programming, recent advances for global convergence of policy gradient methods, temporal difference learning, and techniques from stochastic primal-dual optimization. Our algorithms feature two stages, requiring agents to agree on an etiquette before starting their interactions, which is feasible for instance in self-play. However, the agents only access to joint reward and joint next state and not to each other's actions or policies. Our complexity results match the best-known results for global convergence of policy gradient algorithms for single agent RL. We provide numerical verification of our methods for a two player bandit environment and a two player game, Alesia. We observe improved empirical performance as compared to the recently proposed optimistic gradient descent-ascent variant for Markov games.

Keywords: RL: Discounted Cost/Reward · RL: Policy Search · T: Reinforcement Learning and Planning

Author Information

Ahmet Alacaoglu (University of Wisconsin-Madison)
Luca Viano (EPFL)
Niao He (ETH Zurich)
Volkan Cevher (EPFL)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors