Off-Policy Exploitability-Evaluation in Two-Player Zero-Sum Markov Games
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Off-policy evaluationVocal Bursts Valence PredictionSimilar Papers 제목 키워드 기반
Anytime PSRO for Two-Player Zero-Sum Games
Policy space response oracles (PSRO) is a multi-agent reinforcement learning algorithm that has achieved state-of-the-art performance in very large two-player zero-sum games. PSRO is based on the tabular double oracle (D…
Multi-agent Reinforcement Learningreinforcement-learningReinforcement LearningReinforcement Learning (RL)+1Computing Approximate Equilibria in Sequential Adversarial Games by Exploitability Descent
In this paper, we present exploitability descent, a new algorithm to compute approximate equilibria in two-player zero-sum extensive-form games with imperfect information, by direct policy optimization against worst-case…
counterfactualGlobal Policy-Space Response Oracles for Two-Player Zero-Sum Games
The Policy-Space Response Oracles (PSRO) framework scales equilibrium computation to large zero-sum games by iteratively expanding a restricted strategy set using deep reinforcement learning (DRL). A central challenge is…
Reinforcement LearningLearning to Safely Exploit a Non-Stationary Opponent
In dynamic multi-player games, an effective way to exploit an opponent's weaknesses is to build a perfectly accurate opponent model. This renders the learning problem a single-agent optimization which can be solved by ty…
Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Games
Policy-based methods with function approximation are widely used for solving two-player zero-sum games with large state and/or action spaces. However, it remains elusive how to obtain optimization and statistical guarant…
Policy Gradient MethodsVocal Bursts Valence Prediction