Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets
This work addresses a key challenge in offline reinforcement learning for multi-agent systems, offering a provably efficient solution with theoretical guarantees, though it is incremental in extending pessimism methods to the multi-agent setting.
The paper tackles the problem of learning approximate Nash equilibrium policies from offline datasets in two-player zero-sum Markov games without uniform coverage, proposing a pessimism-based algorithm that achieves a data-dependent sublinear rate and provides the first nearly minimax optimal result with function approximation.
We study episodic two-player zero-sum Markov games (MGs) in the offline setting, where the goal is to find an approximate Nash equilibrium (NE) policy pair based on a dataset collected a priori. When the dataset does not have uniform coverage over all policy pairs, finding an approximate NE involves challenges in three aspects: (i) distributional shift between the behavior policy and the optimal policy, (ii) function approximation to handle large state space, and (iii) minimax optimization for equilibrium solving. We propose a pessimism-based algorithm, dubbed as pessimistic minimax value iteration (PMVI), which overcomes the distributional shift by constructing pessimistic estimates of the value functions for both players and outputs a policy pair by solving NEs based on the two value functions. Furthermore, we establish a data-dependent upper bound on the suboptimality which recovers a sublinear rate without the assumption on uniform coverage of the dataset. We also prove an information-theoretical lower bound, which suggests that the data-dependent term in the upper bound is intrinsic. Our theoretical results also highlight a notion of "relative uncertainty", which characterizes the necessary and sufficient condition for achieving sample efficiency in offline MGs. To the best of our knowledge, we provide the first nearly minimax optimal result for offline MGs with function approximation.