Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
58,797 characters · 18 sections · 41 citation commands
Off-Policy Exploitability-Evaluation in Two-Player Zero-Sum Markov Games
\pagestyle{fancy} \fancyhead
Off-policy evaluation (OPE) is the problem of evaluating new policies using historical data obtained from a different policy. Because online policy evaluation and learning are usually expensive or risky in various applications of reinforcement learning (RL), such as medicine murphy2003optimal and education mandel2014offline, OPE is attracting considerable interest athey2017efficient,kallus2019intrinsically,kitagawa2018should,liu2018breaking,swaminathan2015batch,thomas2016data,zhou2018offline. In the recent OPE context, most studies have focused on single-player cases rather than multi-player cases.
Multi-Agent Reinforcement Learning (MARL) is a generalization of single-agent RL for multi-agent environments. It is widely applicable to situations where there are multi-agent interactions, such as security games, auctions, and negotiations. In recent years, MARL has achieved many successes in the games Go silver2016mastering, silver2017mastering and poker brown2019superhuman,brown2017libratus. MARL is a field with potential real-world applications, such as automated driving shalev2016safe.
In this study, we propose OPE estimators in two-player zero-sum Markov games (TZMGs), which is one of the problems dealt with in MARL. In general, existing OPE estimators in RL estimate the discounted value of a new policy. However, estimating the discounted value is ineffective when the policy of the other player is unknown. Unlike these estimators, for OPE in MARL, our OPE estimators evaluate a strategy profile by estimating exploitability, which is a metric for determining how close a strategy profile is to a Nash equilibrium in TZMG. The proposed exploitability estimators are constructed by the doubly robust (DR) jiang2016doubly and double reinforcement learning (DRL) kallus2019double value estimators. We prove that the proposed exploitability estimators are $\sqrt{n}$-consistent estimators for the true exploitability.
We also propose the methods to find the best candidate strategy profile from a given strategy profile class. The proposed methods select the strategy profile that minimizes the exploitability projected by our exploitability estimators. Then, we prove that we can consistently select the true lowest-exploitability policy profile using the proposed methods.
To demonstrate the effectiveness of our exploitability estimators, we compare our estimators to the estimators based on the following representative value estimators: importance sampling (IS), marginalized importance sampling (MIS), direct method (DM) value estimators. The results show that the exploitability estimators based on the DR and DRL value estimators generally outperform the other estimator-based methods. To the best of our knowledge, this is the first proposed estimators for exploitability for OPE in TZMGs.
A TZMG is defined as a tuple $\langle \mathcal{S}, \mathcal{A}_1, \mathcal{A}_2, T, P_I, P_T, P_R, \gamma \rangle$, where $\mathcal{S}$ represents a finite state space; $\mathcal{A}_i$ represents an action space for player $i \in \{1, 2\}$; $T$ represents a horizon; $P_I : \mathcal{S} \to [0, 1]$ represents an initial state distribution; $P_T : \mathcal{S} \times \mathcal{A}_1 \times \mathcal{A}_2 \times \mathcal{S} \to [0, 1]$ represents a transition probability function; $P_R : \mathcal{S} \times \mathcal{A}_1 \times \mathcal{A}_2 \times \mathbb{R} \to [0, 1]$ represents a reward distribution; and $\gamma \in [0, 1]$ represents a discount factor. We define $R: \mathcal{S} \times \mathcal{A}_1 \times \mathcal{A}_2$ as a mean reward function of $P_R$. For $t=1, \cdots, T$, we define $r_t\sim P_R(s_t,a_t^1, a_t^2)$ as a player 1's reward for taking actions $a_t^1$ and $a_t^2$ at state $s_t$, and define $-r_t$ as a player $2$'s reward. Let $\pi_{i,t} : \mathcal{S} \times \mathcal{A}_i \to [0, 1]$ be a Markov policy for player $i$ at step $t\leq T$, and let $\pi_i=(\pi_{i,t})_{t\leq T}$. We define $\pi=(\pi_1, \pi_2)$ as a strategy profile or a policy profile. The $T$-step discounted value of the policy profile $(\pi_1, \pi_2)$ for each player is represented as follows:
We further define the state value function of state $s_t$ at step $t~(1\leq t\leq T)$ as follows:
Based on the state value function, we define the state-action value function of taking actions $a_t^1$ and $a_t^2$ at state $s_t$ as follows:
For a given policy profile $\pi$, we recursively define the marginal state-action distribution $p^{\pi}_t(s_t,a_t^1,a_t^2)$ at step $t$ as follows:
where $p^{\pi}_1(s_1,a_1^1,a_1^2) = \pi_{1,1}(a_{1}^1|s_{1})\pi_{2,1}(a_{1}^2|s_{1})P_I(s_1)$.
A common solution concept for two-player zero-sum games is a Nash equilibrium nash1951non, shapley1953stochastic, where no player cannot improve by deviating from their specified strategy. In TZMGs, a Nash equilibrium $\pi^{\star}=(\pi_1^{\star}, \pi_2^{\star})$ ensures the following condition:
where $\Omega_1$ and $\Omega_2$ are the whole policy sets, i.e., the sets of all possible Markov policies for players 1 and 2, respectively. The best response is a policy for player $i$ that is optimal against $\pi_{-i}$, where $\pi_{-i}$ is a policy for a player other than $i$. Here, we introduce the value known as exploitability, which is a metric for measuring how close a policy profile $\pi$ is to a Nash equilibrium $\pi^{\star}=(\pi_1^{\star}, \pi_2^{\star})$ in two-player zero-sum games. Formally, the exploitability of $\pi_1,\pi_2$ is represented as follows:
Note that in two-player zero-sum games, we can rewrite the exploitability as $v^{\mathrm{exp}}(\pi_1,\pi_2)=v_1(\pi_1^{\star}, \pi_2^{\star}) - \min_{\pi_2^{\prime}\in \Omega_2} v_1(\pi_1, \pi_2^{\prime}) + v_2(\pi_1^{\star}, \pi_2^{\star}) - \min_{\pi_1^{\prime}\in \Omega_1} v_2(\pi_1^{\prime}, \pi_2)$. From the definition, a Nash equilibrium $\pi^{\star}$ has the lowest exploitability of $0$.
In this study, we assume that we can observe the historical data
where $n \in \mathbb{N}$ denotes the number of sampled trajectories. The data is sampled using a fixed policy profile $\pi^b=(\pi_1^b, \pi_2^b)$. We refer to this policy profile as a behavior policy profile. The distribution of $\mathcal{D}$ is then defined as follows:
In most of the studies related to OPE, the goal is to estimate the discounted value of a given target policy from the historical data. However, this goal is not appropriate for multi-agent environments because, in general, in TZMGs, the policy of the opponent player is unknown, and one may play a game against a different policy than the target policy. In this case, the discounted value of the target policy depends critically on the opponent player's policy. Therefore, when the opponent policy is unknown, it is not worth estimating the discounted value against a specific policy. In this study, for OPE in TZMGs, we estimate the exploitability of a given target policy profile $\pi^e=(\pi_1^e,\pi_2^e)$ from the historical data instead of estimating the discounted value. In other words, we estimate the value against the worst opponent policy for each player.
In this study, we assume that we are constrained to consider each player's policies within pre-defined policy classes $\Pi_1\subset \Omega_1$ and $\Pi_2\subset \Omega_2$. In this case, if the best responses $\mathop{\rm arg~max}\limits_{\pi_1^{\prime}\in \Pi_1} v_1(\pi_1^{\prime}, \pi_2^e)$ and $\mathop{\rm arg~max}\limits_{\pi_2^{\prime}\in \Pi_2} v_2(\pi_1^e, \pi_2^{\prime})$ are not included in $\Pi_1$ and $\Pi_2$, we cannot calculate the true exploitability $v^{\mathrm{exp}}(\pi_1^e,\pi_2^e)$. Therefore, instead of calculating $v^{\mathrm{exp}}(\pi_1^e,\pi_2^e)$, our exploitability estimators project the following value:
where $\Pi=\Pi_1\times\Pi_2$ is a policy profile class. Note that our exploitability estimators project the exploitability from the historical data, without the structure information $P_I$, $P_T$, $P_R$, and $R$.
For simplicity, we abbreviate terms like $V_1(s_t)$ as $V_{1,t}$. For a policy profile $\pi$, we define the following variables (note that each variable implicitly depends on $\pi$):
Besides, we use the notation $\mathbb{E}_{\mathcal{D}}[f(X)]=\frac{1}{|\mathcal{D}|}\sum_{x\in \mathcal{D}} f(x)$ as an empirical average over $\mathcal{D}$, and we use $\mathbb{V}[\cdot]$ as a variance.
In the proofs presented in this study, we make the following assumptions regarding the overlapping of the policies and bounds of rewards and estimators, which are standard in the existing OPE literature zhou2018offline, kallus2019double, kallus2019efficiently:
In this study, we construct the exploitability estimators using DR and DRL value estimators jiang2016doubly, kallus2019double, which are the efficient estimators for the discounted value $v_i(\pi_1, \pi_2)$. Therefore, in this section, we discuss the off-policy value evaluation and propose DR and DRL estimators for the discounted value in TZMGs. To distinguish these estimators from the exploitability estimators, we refer to them as value estimators.
First, we discuss the (semiparametric) efficiency bound, which is the lower bound of the asymptotic mean squared error of OPE, among regular $\sqrt{n}$-consistent estimators. Following the general literature tsiatis2007semiparametric, we discuss the efficiency bound of the discounted value in TZMGs. An efficiency bound is defined for estimators under several conjectured models of the data generating process. If the conjectured model is parametric, the efficiency bound is equal to the Cram\'er-Rao lower bound. Even if the conjectured model is non-parametric or semi-parametric, we can still define a corresponding Cram\'er-Rao lower bound. Here, we introduce the following theorem from kallus2019double.
In this section, we propose the DR and DRL value estimators in TZMGs and their asymptotic properties.
{\bf Double Robust Estimator: } We extend the DR value estimator for Markov decision processes (MDPs) proposed by jiang2016doubly to apply to TZMGs. For the theoretical guarantees, we consider the cross-fitting version of the DR value estimator. We split the historical data into $K$ evenly-sized folds. Next, for each fold $k$, we construct estimators $\hat{\rho}_t^{-k}$ and $\hat{Q}_{1,t}^{-k}$ based on all the data except fold $k$. We define the DR value estimator as follows:
where $\hat{V}_t^{-k(i)}=\mathbb{E}_{\pi}[\hat{Q}_{1,t}^{-k(i)} | s_t]$\footnote{$\mathbb{E}_{\pi}[\hat{Q}_{1,t}^{-k(i)} | s_t]$ is the expected value taken only over $a^1\sim \pi_{1,t}(a^1|s_t)$ and $a^2\sim \pi_{2,t}(a^2|s_t)$.} and $k(i)$ denotes the fold that contains the $i$-th data point. By extending the proof of Theorem 4 in kallus2019double to the case of TZMG, we can easily show the asymptotic property of the DR value estimator.
The proof of this theorem is shown in Appendix (ref). As in jiang2016doubly,kallus2019double, we can easily show that $\Upsilon^{\mathrm{DR}}$ is the semiparametric efficiency bound under games where the current state $s_t$ uniquely determines a trajectory.
{\bf Double Reinforcement Learning Estimator: } In addition to the DR value estimator, we extend a DRL value estimator with cross-fitting for MDPs proposed by kallus2019double to one for TZMGs. The DRL value estimator is defined as follows:
By extending the proof of Theorem 10 in kallus2019double to the TZMG case, we can again show the asymptotic property of the DRL value estimator.
According to this result, the DRL value estimator is efficient under mild assumptions, whereas the IS, MIS, DM, and DR estimators may be inefficient.
In this study, we compare our exploitability estimators to the estimators constructed by the IS, MIS, and DM value estimators. This section summarizes these value estimators.
{\bf Importance Sampling Estimator:} An IS estimator is represented as follows:
When the behavior policy profile is known, i.e., $\hat{\rho}_t=\rho_t$, the IS estimator is an unbiased and consistent estimator of $v_1(\pi_1,\pi_2)$ and $v_2(\pi_1,\pi_2)$. However, in general, the variance of the IS estimator grows exponentially with respect to horizon $T$ jiang2016doubly.
{\bf Marginalized Importance Sampling Estimator:} A MIS estimator is represented as follows:
The MIS estimator can be regarded as one of the IS-type estimators. Although the MIS estimator addresses the curse of horizon by exploiting the Markov decision process (MDP) structure, it is inefficient kallus2019double,xie2019towards.
{\bf Direct Method Estimator:} A DM estimator is represented as follows:
The DM estimator is not consistent if $\hat{Q}_{1,1}$ is not consistent, and it is not unbiased if $\hat{Q}_{1,1}$ is not correct.
For OPE in TZMGs, we propose the following exploitability estimators constructed by the DR and DRL value estimators, respectively:
Similarly, we define $\hat{v}^{\mathrm{exp}}_{\mathrm{IS}}$, $\hat{v}^{\mathrm{exp}}_{\mathrm{MIS}}$, and $\hat{v}^{\mathrm{exp}}_{\mathrm{DM}}$ as the exploitability estimators based on the IS, MIS, and DM value estimators, respectively. We present the pseudocode of the proposed estimator with $\hat{v}_i^{\mathrm{DR}}$ in Algorithm (ref). The procedure of the exploitability estimator with $\hat{v}_i^{\mathrm{DRL}}$ is the same as Algorithm (ref) except that $\hat{\rho}_t$ is replaced with $\hat{\mu}_t$.
In this section, we demonstrate the exploitability estimation error bounds of $\hat{v}^{\mathrm{exp}}_{\mathrm{DR}}(\pi^e_1,\pi^e_2)$ and $\hat{v}^{\mathrm{exp}}_{\mathrm{DRL}}(\pi^e_1,\pi^e_2)$. To obtain theoretical implications, we define the $\epsilon$-Hamming covering number $N_H(\epsilon, \Pi)$ under the Hamming distance $H_{n}(\pi^a,\pi^b)=\frac{1}{n}\sum_{i=1}^n\bm{1}(\{\bigvee_{t=1}^T\pi_{1,t}^a(s_{i,t})\neq\pi_{1,t}^b(s_{i,t})\}\vee\{\bigvee_{t=1}^T\pi_{2,t}^a(s_{i,t})\neq\pi_{2,t}^b(s_{i,t})\})$ and its entropy integral $\kappa(\Pi)=\int_{0}^{\infty}\sqrt{\log N_H(\epsilon^2,\Pi)}$. In the proofs of the remaining theorems, we make the following assumptions on the covering number $N_H(\epsilon,\Pi)$:
Assumption (ref) is precisely the same as the assumption in the proof of zhou2018offline,kato2020off, and this is not strong assumption zhou2018offline. Furthermore, to establish uniform error bounds on $\hat{Q}_{1,t}$ and $\hat{\mu}_{t}$, in the remaining theorems, we assume that $\hat{Q}_{1,t}$ and $\hat{\mu}_{t}$ are computed using the estimated TZMG model $\hat{R}$, $\hat{P}_T$, $\hat{p}^{\pi^b}_t$. Under similar consistency assumptions as in zhou2018offline, kato2020off, the estimation error bounds of $\hat{v}^{\mathrm{exp}}_{\mathrm{DR}}$ and $\hat{v}^{\mathrm{exp}}_{\mathrm{DRL}}$ are then obtained as follows:
Theorems (ref) and (ref) mean that $\hat{v}^{\mathrm{exp}}_{\mathrm{DR}}$ and $\hat{v}^{\mathrm{exp}}_{\mathrm{DRL}}$ are $\sqrt{n}$-consistent estimators for the true exploitability defined among $\Pi$. In particular, when $\Pi=\Omega_1\times\Omega_2$, the error between the estimated exploitability and the true exploitability $v^{\mathrm{exp}}(\pi^e_1,\pi^e_2)$ converges to $0$ at a rate $O_p(\frac{1}{\sqrt{n}})$. Because $\Upsilon^{\ast}_{\mathrm{DR}}=\sup\limits_{\pi\in \Pi}(\Upsilon_{\mathrm{DR}}+v_1^2(\pi_1,\pi_2))$ and $\Upsilon^{\ast}_{\mathrm{DRL}}=\sup\limits_{\pi_1, \pi_2\in \Pi}(\Upsilon_{\mathrm{EB}}+v_1^2(\pi_1,\pi_2))$, it is necessary to use the value estimator with a small (asymptotic) variance to reduce the exploitability estimation error. That is, the exploitability estimation error would be small using the value estimator with a small asymptotic variance. Therefore, from Theorems (ref) and (ref), using the efficient value estimator $\hat{v}^{\mathrm{exp}}_{\mathrm{DRL}}$ would result in a small estimation error. Note that we do not assume that the behavior policy profile is known in Theorems (ref) and (ref). We sketch the proof of Theorem (ref). The proof of Theorem (ref) is almost the same as Theorem (ref).
\paragraph{Proof sketch of Theorem (ref)} First, we define the DR value estimator with oracles $Q_{1,t}$ and $\rho_t$ as follows:
Besides, we define the value difference between two policy profiles $\pi^{\alpha}$ and $\pi^{\beta}$ in $\Pi$ as follows:
We mainly show the uniform concentration of these difference functions following the proof of zhou2018offline.
{\bf Uniform concentration of the difference of influence functions: } First, we prove that the influence difference function $\tilde{\Delta}(\cdot,\cdot)$ concentrates uniformly around its mean $\Delta(\cdot,\cdot)$:
The proof of Lemma (ref) is the extension of the concentration result in zhou2018offline to the TZMG setting. The proof of this lemma is shown in Appendix (ref).
{\bf Uniform concentration of the estimated value difference function: } Next, we prove that with high probability, the estimated value difference function $\hat{\Delta}(\cdot,\cdot)$ concentrates around $\tilde{\Delta}(\cdot,\cdot)$ uniformly at a rate $o_p(\frac{1}{\sqrt{n}})$:
The proof of this lemma is shown in Appendix (ref). Here, we have:
Therefore, combining Lemmas (ref) and (ref), we can show the uniform concentration of $\hat{\Delta}(\cdot,\cdot)$ on $\Delta(\cdot,\cdot)$:
{\bf Estimation error bound of the exploitability estimator: } Next, we define the best response and the estimated best response as follows:
Then, by some algebra, we have:
and
Therefore, we have:
Then, from Lemma (ref) and this equation, the statement is concluded. For further details on the proof, see Appendix (ref).
In this section, we consider the problem of selecting the best candidate policy profile from a given policy profile class, one of the most practical applications of OPE. For given historical data $\mathcal{D}$, our goal is to select the best policy profile with the lowest exploitability from the candidate policy profile class $\Pi$, i.e.,
According to Equation ((ref)), when $\Pi_1=\Omega_1$ and $\Pi_2=\Omega_2$, the policy profile $(\pi^{\ast}_1,\pi^{\ast}_2)$ is a Nash equilibrium.
To this end, we propose methods based on the exploitability estimators proposed in the previous section. Based on the exploitability estimator $\hat{v}^{\mathrm{exp}}_{\mathrm{DR}}$, we select the policy profile that minimizes the estimated exploitability as follows:
From the definition of $\hat{v}^{\mathrm{exp}}_{\mathrm{DR}}$, we can rewrite the $\hat{\pi}_1^{\mathrm{DR}}$ and $\hat{\pi}_2^{\mathrm{DR}}$, respectively, as follows:
Similarly, we define $\hat{\pi}^{\mathrm{IS}}$, $\hat{\pi}^{\mathrm{MIS}}$, $\hat{\pi}^{\mathrm{DM}}$, and $\hat{\pi}^{\mathrm{DRL}}$ as the estimators based on $\hat{v}^{\mathrm{exp}}_{\mathrm{IS}}$, $\hat{v}^{\mathrm{exp}}_{\mathrm{MIS}}$, $\hat{v}^{\mathrm{exp}}_{\mathrm{DM}}$, and $\hat{v}^{\mathrm{exp}}_{\mathrm{DRL}}$, respectively. We describe the pseudocode of the proposed method with $\hat{v}^{\mathrm{exp}}_{\mathrm{DR}}$ in Algorithm (ref). The procedure of the proposed method with $\hat{v}^{\mathrm{exp}}_{\mathrm{DRL}}$ is the same as Algorithm (ref) except that $\hat{\rho}_t$ is replaced with $\hat{\mu}_t$.
We can derive the exploitability bounds of $\hat{\pi}^{\mathrm{DR}}$ and $\hat{\pi}^{\mathrm{DRL}}$ similarly as in the proofs of Theorems (ref) and (ref).
These theorems mean that we can consistently select the true lowest-exploitability policy profile $\pi^{\ast}$ using the proposed methods. According to the minimax theorem, if $\Pi_1=\Omega_1$ and $\Pi_2=\Omega_2$, then $v^{\mathrm{exp}}(\pi_1^{\ast},\pi_2^{\ast})=0$. Therefore, in this case, the exploitability of the selected policy profile converges asymptotically to $0$. This means that the selected policy profile converges asymptotically to a Nash equilibrium when $\Pi_1=\Omega_1$ and $\Pi_2=\Omega_2$. We sketch the proof of Theorem (ref). The proof of Theorem (ref) is almost the same as Theorem (ref).
\paragraph{Proof sketch of Theorem (ref)} Let define:
Besides, for simplicity, we write $\hat{\pi}^{\mathrm{DR}}_i$ as $\hat{\pi}_i$ and $\hat{v}^{\mathrm{DR}}_i$ as $\hat{v}_i$. From the definitions of $\pi^{\ast}_i$ and $\hat{\pi}_i$, we have:
Therefore, the exploitability bound of $\hat{\pi}$ is:
Then, from Lemma (ref) and this equation, the statement is concluded.
We conduct experiments to analyze and evaluate the proposed exploitability estimators and the policy profile selection methods. We conduct our experiments in two environments: repeated biased rock-paper-scissors (RBRPS) and Markov soccer littman1994markov.
In all the experiments, we first prepare a near optimal policy profile $\pi_d$ using Minimax-Q learning littman1994markov, after which we construct the behavior and target policy profiles using $\pi_d$. We use an off-policy temporal difference learning sutton1998rli to construct a Q-function model, and we use a histogram estimator for $\mu$, as in Section 5.2 in kallus2019double. In our experiments, we assume that the behavior policy profile is known and fixed.
RBRPS is a simple TZMG where two players play an one-shot biased rock-paper-scissors game schaeffer2009comparing multiple times. We refer to a game that is repeated once as RBRPS1 and a game that is repeated two times as RBRPS2. Note that RBRPS1 is precisely the same as the conventional rock-paper-scissors game. Figure (ref) (a) shows the payoff matrices and the state transition graph of RBRPS2. In the first step, the payoff matrix is the same as in the conventional rock-paper-scissors game. Depending on the result of the one-shot game, the next state and the payoff matrix transition. There are five states in RBRPS2, and each state corresponds to each payoff matrix.
Markov soccer is a 1 vs 1 soccer game on a $4 \times 5$ grid , as shown in Figure (ref) (b). A and B denote players 1 and 2, respectively, and the circle in the figure represents the ball. In each turn, each player can move to one of the neighboring cells or stay in place, and the actions of the two players are executed in random order. When a player tries to move to the cell occupied by the other player, the ball's possession goes to the stationary player, and the positions of both players remain unchanged. When the player with the ball reaches the goal (right of cell 10 or 15 for A, left of cell 6 or 11 for B), the game is over. At this time, the player receives a reward of $+1$, and the opponent receives a reward of $-1$. The player's positions and the ball's possession are initialized as shown in Figure (ref) (b).
In the first experiment, we compare the performance of $\hat{v}^{\mathrm{exp}}_{\mathrm{IS}}$, $\hat{v}^{\mathrm{exp}}_{\mathrm{MIS}}$, $\hat{v}^{\mathrm{exp}}_{\mathrm{DM}}$, $\hat{v}^{\mathrm{exp}}_{\mathrm{DR}}$, and $\hat{v}^{\mathrm{exp}}_{\mathrm{DRL}}$ in RBRPS1 and RBRPS2. We define the behavior policy profile as $\pi^b_1=0.7\pi^d_1 + 0.3\pi^{r}$ and $\pi^b_2=0.7\pi^d_2 + 0.3\pi^{p}$, where $\pi^r$ is a deterministic policy that always chooses rock, and $\pi^p$ is one that always chooses paper. Similarly, we define the target policy profile as $\pi^e_1=0.9\pi^d_1 + 0.1\pi^{r}$ and $\pi^e_2=0.5\pi^d_2 + 0.5\pi^{p}$. We define the policy classes as $\Pi_1=\Omega_1,\Pi_2=\Omega_2$. We conduct $100$ trials using varying historical data sizes.
Tables (ref) and (ref) show the root-mean-squared error (RMSE) of each exploitability estimator in RBRPS1 and RBRPS2, where bold font indicates the best estimator in each case. For further details on the results, see Appendix (ref). We find that $\hat{v}^{\mathrm{exp}}_{\mathrm{DR}}$ and $\hat{v}^{\mathrm{exp}}_{\mathrm{DRL}}$ generally outperform the other estimators. Note that $\hat{v}^{\mathrm{exp}}_{\mathrm{DRL}}$ has no advantage over $\hat{v}^{\mathrm{exp}}_{\mathrm{DR}}$ because the current state $s_t$ uniquely determines a trajectory. Because the exploitability evaluation requires estimating best response value using historical data, the estimation error of the discounted value must be small. Therefore, $\hat{v}^{\mathrm{exp}}_{\mathrm{DR}}$ and $\hat{v}^{\mathrm{exp}}_{\mathrm{DRL}}$, with a small estimation error of the discounted value, would perform better than the other estimators.
In the second experiment, we analyze the performance of our policy profile selectors in RBRPS1, RBRPS2, and Markov soccer. We compare the five policy profiles $\hat{\pi}^{\mathrm{IS}}$, $\hat{\pi}^{\mathrm{MIS}}$, $\hat{\pi}^{\mathrm{DM}}$, $\hat{\pi}^{\mathrm{DR}}$, and $\hat{\pi}^{\mathrm{DRL}}$, which are selected by each policy profile selector.
In the experiments on RBRPS1 and RBRPS2, we define the behavior policy profile as $\pi^b_1=0.5\pi^d_1 + 0.5\pi^{r}$ and $\pi^b_2=0.5\pi^d_2 + 0.5\pi^{p}$. We define the candidate policy classes as $\Pi_1=\Omega_1,\Pi_2=\Omega_2$ in RBRPS1, and set them to $\Pi_1=\{\{\alpha_1(s)\pi_1^d(s)+(1-\alpha_1(s))\pi^r(s)\}_{s\in S} | 0\leq \alpha_1(s)\leq 1\}$ and $\Pi_2=\{\{\alpha_2(s)\pi_2^d(s)+(1-\alpha_2(s))\pi^p(s)\}_{s\in S} | 0\leq \alpha_2(s)\leq 1\}$ in RBRPS2. Note that the number of policy parameters is reduced to simplify minimax optimization in RBRPS2. We conduct ten trials in each experiment with a historical data size of $250$.
Table (ref) shows the exploitability of each selected policy profile in RBRPS1 and RBRPS2. We find that all selected policies are better than the behavior policy profile. Again, bold font indicates the best policy profile in each case. Notably, $\hat{\pi}^{\mathrm{DR}}$ and $\hat{\pi}^{\mathrm{DRL}}$ outperform the policy profiles obtained by the other estimators.
In the Markov soccer experiment, we define the behavior policy profile as $\pi^b_1=0.3\pi^d_1 + 0.7\pi^{u}$ and $\pi^b_2=0.5\pi^d_2 + 0.5\pi^{u}$, where $\pi^u$ is a uniform random policy. We set the candidate policy classes to $\Pi_1=\{\alpha_1\pi_1^d+(1-\alpha_1)\pi^u | 0\leq \alpha_1\leq 1\}$ and $\Pi_2=\{\alpha_2\pi_2^d+(1-\alpha_2)\pi^u | 0\leq \alpha_1\leq 1\}$. As before, we conduct ten trials in each experiment with a historical data size of $250$. Because it is difficult to calculate the exploitability accurately in Markov soccer accurately, we compare the selected policy's winning rates against other policies. Here, we approximate the winning rate using the rate of reaching the goal in $10,000$ games. Note that player 1 has an advantage over player 2 because the possession of the ball always goes to player 1 at the initial state.
Table (ref) shows the winning rates of each selected policy in Markov soccer. In this table, we show the winning rate of player 1. The winning rates of $\hat{\pi}^{\mathrm{DRL}}_1$ and $\hat{\pi}^{\mathrm{DRL}}_2$ are generally higher than those of the other policies. Unlike the results in RBRPS, the policy profile selected using $\hat{v}^{\mathrm{exp}}_{\mathrm{DRL}}$ is more robust and better than that obtained using $\hat{v}^{\mathrm{exp}}_{\mathrm{DR}}$. These results suggest that we can select the policy profile the lowest exploitability when using $\hat{v}^{\mathrm{exp}}_{\mathrm{DRL}}$.
In the context of OPE, there are many previous studies focusing on the theoretical properties of the value estimators, such as the IS hirano2003efficient, MIS xie2019towards, DR chernozhukov2018double,dudik2014doubly,farajtabar2018more,jiang2016doubly,liu2018representation,robins1994estimation,thomas2016data, and DRL kallus2019double,kallus2019efficiently estimators. In particular, the DRL estimator has the crucial advantage of using Markov properties to avoid the curse of horizon. The main difference between these studies and our study is that we propose exploitability estimators for OPE in MARL.
There are some studies on inverse MARL that assume the situation where the historical data is obtained in multi-agent environments lin2017multiagent,reddy2012inverse,wang2018competitive,natarajan2010multi,zhang2019non,yu2019multi. These studies differ from ours in that they aim to restore the reward function from the historical data. In contrast, our study uses the historical data to estimate the exploitability of a given policy profile.
MARL in Markov games has been studied extensively in the literature hu2003nash,littman1994markov,littman1996generalized,bai2020provable,zhang2019multi,busoniu2008comprehensive. Most existing studies on MARL focus on online policy learning. In contrast, our study focuses on offline policy evaluation.
As with policy learning in Markov games, there is a large body of literature on policy learning in extensive-form games mccracken2004safe,southey2009effective,zinkevich2008regret,davis2019low,schmid2019variance,gibson2012generalized. These studies focus on developing efficient method for computing Nash equilibria in extensive-form games, such as counterfactual regret minimization zinkevich2008regret. On the other hand, we focus on policy evaluation in Markov games. Various works have investigated policy evaluation in extensive-form games zinkevich2006optimal,bowling2008strategy,johanson2009data,davidson2013baseline,bard2013online,davis2014using. While these studies have focused on online strategy evaluation with known structure, our study focuses on offline estimating exploitability without structural information.
There are several studies on the best policy selection in bandit problems or RL athey2017efficient,kitagawa2018should,swaminathan2015batch,zhou2018offline,kato2020off. Unlike these studies, we propose the policy selection methods in multi-agent settings. Various studies on batch MARL perolat2017learning, zhang2018finite also have considered the off-policy data setting. The most significant difference between these studies and our study is that our study's main objective is to develop OPE estimators in MARL. Furthermore, we consider the situation where candidate policies belong to a restricted policy class. This has advantages in practical situations where only specific policies can be implemented.
In this study, we proposed estimators for TZMGs. The proposed estimators project the exploitability of a target policy profile from historical data. We proved the exploitability estimation error bounds for the proposed estimators. Besides, we proposed the methods for selecting the best policy profile from a given policy profile class based on our exploitability estimators. We proved the exploitability bounds of the policy profiles selected by the proposed methods. In future studies, we will explore the application of our exploitability estimators in more general settings, such as large extensive-form games.