Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium

By Qiaomin Xie, Yudong Chen, Zhaoran Wang, Zhuoran Yang. 2020

144 citations recorded by the source corpus.

We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games with simultaneous moves. To incorporate function approximation, we consider a family of Markov games where the reward function and transition kernel possess a linear structure. Both the offline and online settings of the problems are considered. In the offline setting, we control both players and aim to find the Nash Equilibrium by minimizing the duality gap. In the online setting, we control a single player playing against an arbitrary opponent and aim to minimize the regret. For both settings, we propose an optimistic variant of the least-squares minimax value iteration algorithm. We show that our algorithm is computationally efficient and provably achieves an $\tilde O(\sqrt{d^3 H^3 T} )$ upper bound on the duality gap and regret, where $d$ is the linear dimension, $H$ the horizon and $T$ the total number of timesteps. Our results do not require additional assumptions on the sampling model. Our setting requires overcoming several new challenges that are absent in Markov decision processes or turn-based Markov games. In particular, to achieve optimism with simultaneous moves, we construct both upper and lower confidence bounds of the value function, and then compute the optimistic policy by solving a general-sum matrix game with these bounds as the payoff matrices. As finding the Nash Equilibrium of a general-sum game is computationally hard, our algorithm instead solves for a Coarse Correlated Equilibrium (CCE), which can be obtained efficiently. To our best knowledge, such a CCE-based scheme for optimism has not appeared in the literature and might be of interest in its own right.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, background): “Bai and Jin (2020); Bai et al. (2020); Liu et al. (2021) address the problems from finite action two player markov games, while Xie et al. (2020) extended this setting to zero sum games with linear function approximation.”
Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability (2021, methodology): “While the specific formulations vary considerably, one formulation can be seen as a multi-step generalization of (contextual) dueling bandits, where regret is measured using our best response notion (which, as discussed, subsumes many other notion in the literature) (Bai and Jin, 2020; Xie et al., 2”
Near-Optimal Reinforcement Learning with Self-Play (2020, methodology): “We pick parameter αt and βt as follows for some large constant c , and log factors ι: αt = (H + 1)/(H + t), βt = c √ H3ι/t (3) In part (c), our greedy policies are computed using a Coarse Correlated Equilibrium (CCE) subroutine, which is first introduced by [35] to solve Markov games using value ite”
A Sharp Analysis of Model-based Reinforcement Learning with Self-Play (2020, methodology): “To overcome this computational challenge, we compute a relaxation of the Nash equilibrium—Coarse Correlated Equalibirum (CCE)—instead, a technique first introduced by Xie et al. (2020) to address reinforcement learning problems in Markov Games.”