Off-Policy Exploitability-Evaluation in Two-Player Zero-Sum Markov Games

Abstract

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.

References in corpus (13)

• Cooperative Inverse Reinforcement Learning
• Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
• Concentration inequalities and asymptotic results for ratio type empirical processes
• Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation
• Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes
• Multi-agent Inverse Reinforcement Learning for Two-person Zero-sum Games
• Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling
• Multi-Agent Adversarial Inverse Reinforcement Learning
• Provable Self-Play Algorithms for Competitive Reinforcement Learning
• Competitive Multi-agent Inverse Reinforcement Learning with Sub-optimal Demonstrations
• Off-Policy Evaluation and Learning for External Validity under a Covariate Shift
• Finite-Sample Analysis For Decentralized Batch Multi-Agent Reinforcement Learning With Networked Agents
• Low-Variance and Zero-Variance Baselines for Extensive-Form Games