Model-Based Reinforcement Learning for Offline Zero-Sum Markov Games

arXiv:2206.04044v2 Announce Type: replace
Abstract: This paper makes progress towards learning Nash equilibria in two-player zero-sum Markov games from offline data. Specifically, consider a $\gamma$-discounted infinite-horizon Markov game with $S$ states, where the max-player has $A$ actions and the min-player has $B$ actions. We propose a pessimistic model-based algorithm with Bernstein-style lower confidence bounds -- called VI-LCB-Game -- that provably finds an $\varepsilon$-approximate Nash equilibrium with a sample complexity no larger than $\frac{C_{\mathsf{clipped}}^{\star}S(A+B)}{(1-\gamma)^{3}\varepsilon^{2}}$ (up to some log factor). Here, $C_{\mathsf{clipped}}^{\star}$ …

abstract algorithm arxiv cs.gt cs.it cs.lg data equilibria game games horizon markov math.it math.st max offline paper progress reinforcement reinforcement learning stat.ml stat.th style type