Off-Policy Exploitability-Evaluation in Two-Player Zero-Sum Markov Games
This work addresses a gap in multi-player off-policy evaluation, offering a method to assess policies in competitive settings, though it is incremental as it extends existing single-player techniques.
The paper tackles off-policy evaluation in two-player zero-sum Markov games by proposing estimators based on doubly robust and double reinforcement learning methods to project exploitability, a metric for proximity to Nash equilibrium, and proves error and regret bounds with experimental validation.
Off-policy evaluation (OPE) is the problem of evaluating new policies using historical data obtained from a different policy. In the recent OPE context, most studies have focused on single-player cases, and not on multi-player cases. In this study, we propose OPE estimators constructed by the doubly robust and double reinforcement learning estimators in two-player zero-sum Markov games. The proposed estimators project exploitability that is often used as a metric for determining how close a policy profile (i.e., a tuple of policies) is to a Nash equilibrium in two-player zero-sum games. We prove the exploitability estimation error bounds for the proposed estimators. We then propose the methods to find the best candidate policy profile by selecting the policy profile that minimizes the estimated exploitability from a given policy profile class. We prove the regret bounds of the policy profiles selected by our methods. Finally, we demonstrate the effectiveness and performance of the proposed estimators through experiments.