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.

本研究针对具有线性结构的两人零和有限马尔可夫博弈提出了一种基于乐观价值迭代的增强学习算法，该算法通过构建价值函数的上下置信区间，并用 Coarse Correlated Equilibrium 求解泛化和纳什均衡问题，实现了性能的总时间平方根复杂度的上限。