Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets
Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets
复制标题
DOI：
--
复制
发表时间：
2022-02
期刊：
影响因子：
--
通讯作者：
Han Zhong;Wei Xiong;Jiyuan Tan;Liwei Wang;Tong Zhang;Zhaoran Wang;Zhuoran Yang
中科院分区：
文献类型：
--
作者：
Han Zhong;Wei Xiong;Jiyuan Tan;Liwei Wang;Tong Zhang;Zhaoran Wang;Zhuoran Yang
我们在离线环境下研究回合制双人零和马尔可夫博弈（MGs），其目标是基于先验收集的数据集找到一个近似纳什均衡（NE）策略对。当数据集对所有策略对没有均匀覆盖时，找到近似纳什均衡在三个方面存在挑战：（i）行为策略和最优策略之间的分布偏移，（ii）处理大状态空间的函数逼近，以及（iii）用于均衡求解的极小极大优化。我们提出一种基于悲观主义的算法，称为悲观极小极大值迭代（PMVI），它通过为两个玩家构建价值函数的悲观估计来克服分布偏移，并通过基于两个价值函数求解纳什均衡来输出一个策略对。此外，我们建立了一个关于次优性的数据相关上界，在不假设数据集均匀覆盖的情况下恢复了一个次线性速率。我们还证明了一个信息论下界，这表明上界中的数据相关项是固有的。我们的理论结果还强调了一个“相对不确定性”的概念，它刻画了在离线马尔可夫博弈中实现样本效率的充分必要条件。据我们所知，我们为具有函数逼近的离线马尔可夫博弈提供了第一个近乎极小极大最优的结果。
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.