Corruption-Robust Offline Two-Player Zero-Sum Markov Games
Andi Nika Debmalya Mandal Adish Singla Goran Radanović
We study data corruption robustness in offline two-player zero-sum Markov
games. Given a dataset of realized trajectories of two players, an adversary is
allowed to modify an $\epsilon$-fraction of it. The learner's goal is to
identify an approximate Nash Equilibrium policy pair from the corrupted data.
We consider this problem in linear Markov games under different degrees of data
coverage and corruption. We start by providing an information-theoretic lower
bound on the suboptimality gap of any learner. Next, we propose robust versions
of the Pessimistic Minimax Value Iteration algorithm, both under coverage on
the corrupted data and under coverage only on the clean data, and show that
they achieve (near)-optimal suboptimality gap bounds with respect to
$\epsilon$. We note that we are the first to provide such a characterization of
the problem of learning approximate Nash Equilibrium policies in offline
two-player zero-sum Markov games under data corruption.