Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium
Authors: Runyu Lu
Yuanheng Zhu
Dongbin Zhao
Venue: ICML 2025 poster (2025)
Keywords: offline reinforcement learning
adversarial Markov game
mixed-strategy Nash equilibrium
policy constraint
exploitability descent
Primary area: reinforcement_learning->batchoffline

Abstract: This paper proposes Constrained Exploitability Descent (CED), a model-free offline reinforcement learning (RL) algorithm for solving adversarial Markov games (MGs). CED combines the game-theoretical approach of Exploitability Descent (ED) with policy constraint methods from offline RL. While policy constraints can perturb the optimal pure-strategy solutions in single-agent scenarios, we find the side effect less detrimental in adversarial games, where the optimal policy can be a mixed-strategy Nash equilibrium. We theoretically prove that, under the uniform coverage assumption on the dataset, CED converges to a stationary point in deterministic two-player zero-sum Markov games. We further prove that the min-player policy at the stationary point follows the property of mixed-strategy Nash equilibrium in MGs. Compared to the model-based ED method that optimizes the max-player policy, our CED method no longer relies on a generalized gradient. Experiments in matrix games, a tree-form game, and an infinite-horizon soccer game verify that CED can find an equilibrium policy for the min-player as long as the offline dataset guarantees uniform coverage. Besides, CED achieves a significantly lower NashConv compared to an existing pessimism-based method and can gradually improve the behavior policy even under non-uniform data coverages. When combined with neural networks, CED also outperforms behavior cloning and offline self-play in a large-scale two-team robotic combat game.

Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium
Runyu Lu"
Yuanheng Zhu 21
Dongbin Zhao 21
Abstract
1. Introduction
Data-driven learning of policies is appealing, especially in scenarios where the interaction with the environment is ex- pensive, e.g., robotic manipulation, autonomous driving, and health care. Therefore, offline reinforcement learning (RL) (Levine et al., 2020) has become an increasingly at- tractive research topic in recent years. However, offline RL faces an inherent challenge of distributional shift (Ross et al., 2011), which arises from visiting out-of-distribution states and actions. A direct way to address this issue is to apply policy constraints, which constrain how much the learned policy differs from the behavior policy in the dataset (Kakade & Langford, 2002; Schulman et al., 2015). In single-agent Markov decision processes (MDPs), such con- straints can lead to suboptimality of the learned policy since the optimal policy is usually pure strategy that assigns the optimal action probability one at each state (Sutton & Barto, 2018). Since the behavior policy derived from set of offline transitions can hardly be pure strategy, applying policy constraints with respect to the behavior policy will sacrifice the optimality of the learned policy, even if the coverage of the offline data is theoretically sufficient for learning the optimal policy (e.g., satisfying uniform concentration).
This paper proposes Constrained Exploitability Descent (CED), a model-free offline reinforce- ment learning (RI.) algorithm for solving adver- sarial Markov games (MGs). CED combines the same-theoretical approach of Exploitability De- scent (ED) with policy constraint methods from offline RL. While policy constraints can perturb the optimal pure-strategy solutions in single-agent scenarios, we find the side effect less detrimental in adversarial games, where the optimal policy can be mixed-strated -trateyy Nash equilibrium. We theoretically prove that, under the uniform cov- erage assumption on the dataset, CED converges to a stationary point in deterministic two-player zero-sum Markov games. We further prove that the min-player policy at the stationary point fol- lows the property of mixed-strategy Nash equi- librium in MGs. Compared to the model- ED method that optimizes the max max-playe max-pplaer policy, our CED method longer relies ized gradient. Experiments in matrix games, a soccer tree-form game, and an infinite-horize game verify that CED can find an equilibrium policy for the min-player as long as the offline dataset guarantees uniform coverage. Besides, CED achieves a significantly lower NashConv compared to an existing pessimism-basee method and can gradually improve the behavior policy even under non- non-uniform data coverages. When combined with neural networks, CED also outper- forms behavior cloning and offline self- olly-pay in a large-scale two-team robotic combat game.
general-
For multi-agent scenarios, the optimal solution can still be pure strategy when it is fully cooperative. However, in adversarial games, e.g., two-player zero-sum Markov games (MGs), we usually characterize the optimal solution with the concept of Nash equilibrium (NE), which admits mixed strategies. For example, in a two-player Rock-Paper- Scissors (RPS) game, the unique NE is the mixed strategy (3. 3: (. for both players. It is thus possible that policy constraint methods under a mixed-strategy behavior policy may not sacrifice policy optimality in MGs. While recent research in the field of game theory has developed vari- ous efficient equilibrium-leannn tended into model-free RL algorithms (Lanctot et al., 2017: Lockhart et al., 2019), it has not been examined if these algorithms can be further combined with existing offline learning techniques (Siegel et al., 2020; Wu et al., 2019) while preserving the guarantee to find an exact Nash equi- librium under sufficient assumptions on the data coverage.
dynamics that can be ex-
'School of Artificial Intelligence, University of Chi- nese Academy of Sciences "Institute of Automation, Chi- Runyu .cn... Yuanheng Zhu <yuan- ann..nn................... Dongbin Zhao <dongbin. ia..ccn.........................
nese Academy of Sciences. Correspondence e mere@mmall...c..... Lu <lurunyul7e
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
On the other hand, while the existing pessimism based meth-

---

Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium
ods are provably efficient for solving offline MDPs and MGs (see Jin et al. (2021); Xiong et al. (2023)), they have certain limitations when they are practically applied to real-world games. First, they require infinitely many samples to fully capture the stochasticity of the game and achieve the opti- mal solution, i.c., Nash equilibrium. However, when the game is deterministic (e.g., chess and Go), they become no longer optimal since the game transition can be determined by finite number of samples, which are already sufficient for finding NE. Second, existing pessimism-based methods usually require information about the game horizon (see Cui & Du (2022a:b); Zhong et al. (2022); Xiong et al. (2023)) or the dynamics model (see Yan et al. (2024)) to solve Markov games. Zhang et al. (2023), as an exception, suffers from computational inefficiency. Therefore, it is still challeng- ing to propose a practical model-free algorithm to solve infinite-horizon MGs offline with theoretical guarantees.
2. Related Work
Pessimism-based methods in offline games. The recent works that directly examine offline games basically focus on sample complexity and rely on pessimistic value func- tions, which have been well understood in single-agent RL (Rashidinejad et al., 2021; Xie et al., 2021). These works typically append bonuses to the original Bellman operators and obtain confidence bounds on the duality gap for the policy computed from dynamic programming (Cui & Du, 2022a:b; Zhong et al., 2022; Xiong et al., 2023; Yan et al., 2024). In the theoretical analyses, corresponding concen- tration inequality is utilized to capture the stochasticity of the transition function. As fundamental work. Cui & Du (2022a) proves that the coverage assumption of unilateral concentration is sufficient for finding Nash equilibrium of- fline in two-player zero-sum games by providing algorithms with Creffding/Bernsteinn -type bonuses. Subsequent works improve the sample complexity (see Cui & Du (2022b)) and extend the analyses more complex scenarios concern- ing linear/general function approximations (sce Xiong et al. (2023); Zhang et al. (2023)).
With the above- mentiond concerns, we ask the question:
Is possible to find mixed-strategy Nash equilibrium offline via model-free learning dynamics with policy constraints?
This paper provides a positive answer to this question. Specifically, our contributions are threefold:
Equilibrium-eearinng dynamics. The field of algorithmic game theory (Roughgarden, 2016; Nisan et al., 2007) exam- ines wide range of equilibrium- -earming dynamics. While the basic method of dynamic programming (or more simply, backward induction) can only deal with perfect information games like Markov games, game- theerthe learning dynam- ics, including Fictitious Play (FP) (Brown, 1951), Policy Space Response Oracle (PSRO) (Lanctot et al., 2017), and Exploitability Descent (ED) (Lockhart et al., 2019), can solve a broad class of games even with imperfect infor- mation. Among them, PSRO is already extended through deep reinforcement learning. ED exhibits best-iterate con- vergence and is conducive to offline RL extensions. While other methods like optimistic multiplicative weights update (OMWU) also enjoy last-iterate convergence (see Lee et al. 1), they have not been examined in infinite-horizon Markov games. Therefore, we consider ED as the basic dy- namic to construct a new method for solving offline games.
We propose a novel model-free RL algorithm to find mixed-strategy Nash equilibrium in adversarial Markov games possibly with an infinite horizon. The algorithm, named Constrained Exploitability Descent (CED), is constructed by combining the policy constraint meth- ods from offline RL with a game theoretic approach called Exploitability Descent (ED).
We prove that, under the uniform coverage (concen- tration) assumption, CED converges in deterministic two-player zero-sum MGs (Theorem 5.2) without rely- ing on generalized gradient like ED. We further show that the min-player policy becomes unexploitable when the opponent converges to an interior point of the con- strained policy space (Theorem 5.6). By exchanging the status of the two players and running CED twice, we can obtain a potential mixed- sixed-strategy NE.
3. Preliminaries
We verify the by conducting experiments in matrix games, tree- form game, soccer game, and two-team robotic combat game'. From finite dataset, CED can find NE policies in all scenarios with uniform coverage, guaranteeing an ultimate NashCony significantly lower than the baseline from a pessimism-based method. As a practical offline method, CED also gradually improves the behavior policy under non-uniform data coverages. In the large-scale robotic combat game, CED clearly outperforms behavior cloning and offline self-play. http://gihaaacoommllloo////////p
caabbriuu-finnding capability of CED
3.1. Problem Formulation
Two-player zero-sum Markov games. An infinite-horizon two-player zero-sum Markov game (Littmann, 1994; Shapley, 1953) is represented by tuple Mg = (S, A, B. P, r, 7): S is the state space. A is the action space of the max- player, who aims to maximize the cumulative reward. B is the action space of the adversarial min-player. P. e [o, 1||S1144 [B]x[S] is the transition matrix. r E [0, 1] 1| is the reward vector, E (0, is the discount factor.
2

---

Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium
Algorithm 1 Exploitability Descent (ED) in two-player zero-sum Markov games
Input: game model MG and iteration number K
Output: last iterate jax for max-player
For k E (1,
Compute Qx= Qt 1,x under MG, where vt =b((ux=1) is best response against 1 For 8 E S
Σ [M(s,a) -11--11 + E (rtss.)) ((((s)))Q(((aaa))) 2) DEA
Update (s((s) arg min ((S)EA(A)
BEB
In this paper, focus the deterministic two-player zero- sum MG with P E {0, 11 IS $1 which means that the transition is deterministic. As a multi-agent extension to the deterministic MDP (see Castro (2020)), it can describe various games ranging from real-world combat games (Chai et al., 2023) to video fighting games (Tang et al., 2023).
3.2. Exploitability Descent
Exploitability Descent (ED) (Lockhart et al., 2019) is game-theoretic approach that generalizes the classic convex- concave optimization for solving matrix games. The core idea is to iteratively update the current policy along the gra- dient computed against a best response from the opponent. Compared to the methods of fictitious play (Brown, 1951) and regret minimization (Hart & Mas-Colell, 2000), ED exhibits best-iterate convergence rather than average-iterate convergence in two-player zero-sum games. Therefore, ED can be readily extended to online RL. algorithms (like Zhu & Zhao (2022)) with policies parameterized by neural net- works. In two-player zero-sum Markov games, ED for optimizing max max-player policy μ is shown in Algorithm 1.
Policy and value functions. We use (14, v) to represent the joint policy of the two players, where is the policy of the max-player (pursuers) and v is the policy of the min-player (evader). Specifically,, p(s) E A(A) (resp., v(s) E ABB) is the max-player's (resp., min-player's) action distribution at state E S, with p(s,a) a) (resp., v(s, 6)) being the proba- bility of selecting action E A (resp., b E B3). Furthermore, as in single-agent MDPs, define value functions (s) E 1 > (rr(s,, as, by) Su = s: p1 | and Q" a. b) 1 7'1(81, ar by) 880 = 8, dg = a, bo b: μ1, w..
E
Define the utility function ((..)) Esprpo (s))) For each (s, ΣtEB v (s., (s,,,,, can make up generalized gradient of Pk-1's worst-case utility V "u(s,a)u(1 br(p)) E Ōmin, v) (Clarke, 1975). Fol- lowing the generalized gradient, μ* can approach local optimum ja of the minimax problem ma,, v). To optimize min-player policy v, we run Algorithm again by exchanging the status of μ and and using an opposite re- ward. Then, (ū. 8) constructs potential Nash equilibrium.
Nash equilibrium. A Nash equilibrium (NE) in game corresponds to a joint policy where each individual player cannot benefit from unilaterally deviating from his/her own policy. Specifically, in a two-player pero-sum MG, an NE (n", =²) satisfies VH.²* < VVa .' < VV*'* V for any μe and v at all states. An NE always exists when the game is finite, and all NEs share the same value (Shapley, 1953) V*(s) Vale Vi (s) = max, V min,max, VAV(ss) (s).
3.3. Policy Constraint Methods
For fixed μ and define best-response value functions (s)*(s) Vane and (** max, VH. (s). Furthermore, let Pa E A(S) be an initial state distribution (x))
In offline RL, the training process is always affected by ac- tion distributional shift (Kumar et al., 2019), which is one of the largest obstacles for model-free applications of the learn- ing dynamics like Algorithm 1. In single-agent scenarios, the effect can be weakened by applying constraints to the learned policy и to keep it close to the behavior policy ng which corresponds to the state-action distribution of the of- fline data. This ensures that the process of value estimation has a lower chance of considering the -ittr--disttibution actions. The extrapolation error in value estimation can be thus mitigated at the expense of policy suboptimality.
and define NashConv(J4, v) = Egyro (s) NashConv equals to the sum of the exploitability of the each player's policy and corresponds to the duality gap from the minimax perspective in two-player zero-sum games. For an arbitrary NE (ni", v/",, we have NashConv(J" v²") O.
In this paper, we aim to find approximate Nash equilibria, which are the joint policies with NashConv close to zero. An important property of NE in two-player zero-sum games is that if (Mi v1) and (n2 12) are both NEs, then (Mi, 22) and (Mg, 21) are also NEs. Therefore, it is reasonable to unilaterally learn the equilibrium policy for the max-player and the min-player. An NE policy be constructed by combining any two of the individual equilibrium policies.
Such constraints are commonly realized using direct policy constraints on the policy update (Siegel et al., 2020) or indi- rect policy penalties on the value functions (Wu et al., 2019). Both methods require using a certain measure ((: (e.g..
3

---

Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium
Algorithm 2 Constrained Exploitability Descent (CED)
Input: offline dataset D, discount factor y, and iteration number K Output: last iterate vK for min-player
Set policy constraint measure ((--) and range 6, policy penalty parameter e, and learning rate Extract non-repetitive transition set D", state set S, and action sets AA, B from Compute state distribution po and behavior policy (13,13) from {% Evaluate the value function under behavior policy}
(rsss, (() ( d'mpult') [Q d''',''' [((s),,',']) dd,,)) 2
Compute Q"ai"9= arg min
Σ
Q(ss,,,))
Q
Unuus(d')
Initialize Qo = Qua po = (4,, V0 = VB
For k E (1,2.... K}
1% Apply Bellman operator the current value function)
(Qls.a.))
()) (r(r))))(((,.))++ a'mm--111))) (Q==1(s,dd
Update Qx = arg min
Σ
Q
(s.0.br,s")ED-
D'mua-1(d))
For 8 S {% Update p along ED-like gradient under policy constraint
Update (8)
arg arg min (AS)EA(A)) sa ((()))
Σ (((s,a)
(ua-1 + app((s) Σ [1
CEAA
bEB
For S
1% Compute approximate best response v under policy penalty)
Compute (*) = arg max
Σ u(s
(- Σ
MM a) ausua)aa(aaa (s, (s,
-e eDRI. (v())
v(s)EA(B)
bEB
dEA
KL-divergence) to describe the closeness of two policies.
in Algorithm 1, the resulting max- maxx-plaerr policy f will surely deviate from the equilibrium of the original game for the same reason in single-agent scenarios. Surprisingly, we find that it is possible to instead keep the min min-player policy unexploitable. We will further explain it through our subse- quent mathematical derivations in theoretical analysis. With this observation, we propose an offline equilibrium-learnin algorithm under policy constraints and call it Constrained Exploitability Descent (CED; see Algorithm 2).
The following policy update formula is an example of ap- plying direct policy constraints:
(s) arg (A))) s.L. (1))))
1QT*
In comparison, a regularized value is computed when using indirect policy penalties:
(s) = arg max =(s)EA(A)
{ (Eana(s) [Q(s, a)] -
CED inherits the basic structure of ED in each iteration. A Q value is computed, the current μ is updated, and best response is computed in preparation for the next iteration. However, CED has multiple differences in detail:
For direct policy constraints, the optimality of the learned policy is preserved only when the behavior policy Te is close enough to the true optimal policy, which in theory a pure strategy in single-agent scenarios. However, this unlikely to happen since Ty is derived from an offline dataset. For indirect policy penalties, they face the same problem since the resulting solution could never be pure strategy (see Lemma 4.1 for the case of KL-divergencee.
Qs is updated from the last Qt-1 rather than directly solved under the current Bellman equation.
The update of at each state E S is under direct policy constraint D(p(s), (s)) S 5. An additional factor (s(s) is also appended after the learning rate a.
4. Constrained Exploitability Descent
The computation of v is based on Q"a-"e (without esti- mating QlIE.P)) and is under a KL-divergence penalty (vL(v(s), ug(s)) with a regularization parameter c.
For adversarial games, even if we only apply a constraint to the computation of the best response y for the min-player

---

Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium
Note that 2y can still be viewed as an approximate best response to the current μ4 when (Mu: 2x) is kept close to (ue) As result, the best iterate of j locally minimizes exploitability in a regularized game. However, under the ad- ditional KI -i-divereence regularization, now VE has a unique solution with a closed-form expression (see Lemma 4.1), which allows j to update along a deterministic gradient rather than an arbitrary generalized gradient. This mitigates the problem that following generalized gradient can lead to recurrence around a local optimum, making it possible to prove last-iterate (rather than best-iterate) convergence.
5.1. Convergence of CED
Lemma 5.1 shows the explicit gradient of utility function u(μ, v) Es- [V*, with respect to μ.. This can be viewed as an application of the policy gradient theorem in MDPs (Sutton et al., 1999) to multi-agent scenarios.
Lemma 5.1 (Policy Gradient in MG). Let (s)
Σxz0 x Pr (s]k; H.V), where Pr (slk;,, is the proba- bility of reaching state at time step k under joint policy (1, Then, it holds for all s S and a E A:
Ōu(p,v) = -st Σ BEB
Lemma 4.1 (Uniqueness of v in CED). In Algorithm 2, Va Vs, b) can be uniquely determined by computing:
0y(s,a)
Using Lemma 4.1 and Lemma 5.1, we are able to demon- strate the convergence of CED (Theorem 5.2) under an approximation about the state visitation probability p.
(-t m (uss,,
us(8,b) b) exp
aEA
Σ (0(8. B
B) - Σ
Theorem 5.2 (Convergence of CED). When ptu approxi- mates the true state distribution pD of the dataset DD CED with sufficiently small a and 1/ will converge to a stationary point (Q, p. D) under the uniform coverage assumption.
aEA
When e > 0, the min-player policy y is a mixed strategy and no longer an exact best response to the max- max-player policy μ. As a result, the limit point of deviates from the solution to the original minimax problem. Instead, we will prove in the following section that v4 approaches an unexploitable min- player policy P. By exchanging the status of max-player and min- min-player in the game and running Algorithm 2 again, we can also obtain an unexploitable max-player policy jr. The joint policy (ýi D) constructs a potential Nash equilibrium.
Proof. By Lemma 4.1, Vy is uniquely determined by 14p. As D" covers all (s, a, b) tuples and the MG is deterministic, Q++1 in CED approximates the true value Qua when jıs learning rate a is close to zero. Therefore, we only need to consider the convergence of μ. By Lemma 5.1, we have:
Dulue, v(NE)) = @pa(s,)) a) (pp(),a)
Ōu((R: ux)
= Ouluer Ovr (8. b) Oux(s,b) @px(s,a)
+
BEB
pmm (s)ux(s
5. Theoretical Analysis
Σ bEB
Ou(uus uk) Ovp(s,6) Duk(o,b) (s,
In this section, we theoretically show that it is possible for CED (Algorithm 2) to find an exact Nash equilibrium with
the following two steps: First, we prove that CED can con- verge to stationary point (Q, F., D) (Section 5.1). Second, we prove that the min-player policy E at the stationary point of CED is unexploitable, like any mixed-strategy Nash equi- librium of full support (Section 5.2). All of the omitted proofs are provided in Appendix A.
Note that (u.().)) 0 when ! O (see Appendix A.3 for [pe()
details). When p/u approximates PD. we have Ou(mg."e)
(sa(s,a)
(D(s) EbEB (s, ()(ss))) b)Q++1 as,,,,,, b). Therefore, P& in CED updates along the gradient of w(na, (()) at a sufficiently small learning rate a. As a result, j will converge to a local maximum j for u(Hs, v(w),, which implies CED will converge to a stationary point (Q. D).
Throughout our analysis, we require the uniform coverage assumption, which means that the non-repetitive transition set D' derived from the dataset 'D covers all state-action tu- ples (s, a, b). In Cui & Du (2022a), this assumption is called uniform concentration, and a weaker assumption named uni- lateral concentration is analyzed. By constructing a coun- terexample where the exact NE becomes impossible learn, they proved that unilateral concentration is somewhat nec- essary for finding Nash equilibrium offline. However, when the NE is a completely mixed strategy (e.g., the unique NEs of the matrix games in Section 6.1,, unilateral concentra- tion is equivalent to uniform concentration. Therefore, the uniform coverage assumption can be necessary for our theo- retical analysis on finding mixed-strategy Nash equilibrium.
Theorem 5.2 provides direct convergence guarantee for CED without relying on generalized gradient like ED. Besides, compared to ED's underlying assumption that pa is uniform, the assumption of piu x pp is more realistic. The policy constraints employed in CED will keep (1, v) close to the behavior policy (Ho, 1/)) derived from D.
5.2. Relationship to Nash Equilibrium
Now we further show that the min-player policy i at the stationary point of CED follows a property of mixed-strategy Nash equilibrium in MGs, namely, being unexploitable.
5

---

Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium
Definition 5.3 (Unexploitable). We say a joint policy (14, v) in an MG is unexploitable if both y and are unexploitable with respect to each other. Specificallyy, Vss E S:
Therefore, it holds for all E S that P 0, E A, which further implies that 2 = c(s), Va A. As result, EEE ((s, (ss,)))(s,, c(s), Va E A, which means that the min- min-player policy 1 is unexploitable with respect to jr.
= LEE p(s, b)Qa* a, b) =
is unexploitable: ΣnEa (ss. b) = (s)s), Ab v is unexploitable: EeEB v(s, b)Q"" = ot (s), Va
Intuitively, a policy y is unexploitable with respect to an opponent policy v in an MG if all of the opponent actions b have the same constant value 2 (s) under each S. As result, the opponent cannot exploit μ by deviating from v at any state. Lemma 5.4 shows this property can characterize the mixed-strategy Nash equilibria with full support.
With Theorem 5.6, if we run Algorithm 2 twice by ex- changing the status of the two players and both max-player policies converge to an interior point, then the last iterates (1, D) and (Ā, v) can construct an unexploitable joint policy (R, D). Policy constraints play an important role in support- ing this claim. On the one hand, the distance between μ and (48 is restricted by the direct policy constraint. On the other hand, the indirect policy penalty can also bound the distance between á and μ4 (corresponding to the 1%k and V3 in Algorithm 2 after the status exchange; see Lemma A.1 in Appendix A.6 for an explicit bound). Since both I and ju are close to jág under policy constraints, we have Qu.P ~ Qua.6 R Qa.P. which implies that i is also un- exploitable with respect to p. By symmetry, it is direct to show that the joint policy (a. i) is unexploitable and thus constructs a potential mixed-strategy Nash equilibrium.
Lemma 5.4 (Property of Interior NE). If a Nash equilibrium (n², v*) in an MG has full support on the action space (thus being an interior point of the joint policy space), then is unexploitable.
Now we demonstrate that ú at any stationary point of CED is also an unexploitable min-player policy in the MG. We first provide an auxiliary lemma to show the update of j at each state 8 E S can be equivalently enforced within the hyperplane of probability simplex, where M(s, a) = 1.
Lemma 5.5 (Update Projection). Let z be the original update (sp((s) EOEB (ss b) Q))++1 a, b) for pa(s, a) in CED. Let y Ene = be the summation over A and de- fine the projected update p = -.. Then, replacing all = with pl resulls in the same pa+ (8) in CED.
In Appendix C. we combine the existing theory to provide an overall explanation about the advantages of the CED method. In the next section, we will further verify through experiments that CED can practically find NE policies un- der uniform coverage. Under non-uniform data coverages, we also find that CED can gradually improve the behavior policy and eventually obtain a competitive policy.
We call Pa= a projected update because EeEa P- and (p(s,a) a) + Pa) is kept in the hyperplane of probability simplex. Using Lemma 5.5, we can prove that & is unex- ploitable under an interior point assumption (sufficient also for the theoretical analysis of ED (Lockhart et al., 2019)).
6. Experiments
We conduct experiments for tabular CED in matrix games, a tree-form game, and soccer game. We also evaluate CED under function approximations in robotic combat game.
Theorem 5.6 (Unilateral Unexploitability). Let II(s) =
(s) (s) be the feasible region for pls), where (s) is the probability simplex and [2((s) is the region induced by the constraint ((p(s), ), (a(s)) S 8. For any stationary point (Q, F.. D) of CED, if ja(s) is an interior point of (s))) for all s S, then is an unexploitable policy with respect to jú under the uniform coverage assumption.
6.1. Matrix Game
We first examine if CED manages to find mixed-strategy Nash equilibrium in static matrix games. We consider two games with two valid actions from (1 for both play-
ers. The payoff matrices are M1 = ((1, 0), 2,44) and M2 = ((1, 0), (-2,3)), where the rows correspond to the actions of the max- max-player and the columns correspond to the actions of the min-playes (1*(1) G. v² (() 4) and
Proof. As D" covers all (s, a, b) tuples and the MG is de- terministic, a stable Q with respect to (p, F) in CED cor- responds to the true value Qu. Since (ū(s,a) a) + Pa)aEA in the hyperplane of [[)) and j is stable with respect to (Q, v), we can consider the following two cases:
(n²(1) = 5. v* (1) = 1) are the unique NEs in the games.
The learning curves of (H, for CED (a 0.01, 1.0) under uniform coverage (Ha(1 = 2. (1) = =)) are shown in Figure 1. The y-axis indicates the probability of choosing action 1 under the corresponding policy. The dashed lines show the action probabilities of the unique NE policy. In both games, CED manages to learn the equi- librium policy u = v² for the min-player. This result is
Case i: (p(s,a) + Pa)asA belongs to ((s). Then, A(s) (p(s,a) + pa)aEA = 22 O, Va A.
Case ii: (īis, a) + pa)ac does not belong to Il(s). Then, j(ss) is the closest point in ((s) with respect to the point (p(s,a) a) + -P)) in the same hyperplane. This contradicts the assumption that (is) is an interior point of (Ts)).
6

---

Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium
Matrix Game 1
Matrix Game 2
S-Action RPS Game
vrooc) (paper)
Probabiity of Actionn
0.8
Probability of Action
Aclion Probability
0.8
viscisoors
0.6
0.6
0.6
kiwster
0.4
0.4
0.4
0.2
0.2
0.2
200
300 Iteration
500
200
500
100
200
500
Iteration
Iteration
Figure 1. CED learning curves in the matrix games
Stage and Stage ICED)
Stage (ED)
Stage (CED)
v13
vtrock) viscissors)
Probability of Actoo
0.8
V121
Probability of Actioo
0.8
Action Probabillty
0.8
viirel vdwater!
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
100
200
300 Iteration
400
500
600
100
200
300
400
500
600
100
200
300
400
500
600
Iteration
Iteration
Figure 2. CED and ED learning curves in the tree-form game
consistent with Theorem 5.2 and Theorem 5.6, which claim that under uniform coverage, CED can converge an unex- ploitable v (an NE policy in this case). We may find that the learned for M2 also corresponds to the equilibrium. How- ever, this is because Vy happens to be v² in MM2. Otherwise, the divergence regularization applied to the computation of will force the stationary point of j to deviate from μ² because n" is not an exact best response to the stationary μ. This phenomenon is shown in the learning curve on M1, with the ultimate f # 1x" as result of Vg # v*.
spectively. T starts with Stage (M1) and enters Stage 2 (M2) Stage (Ma) conditioned on the joint actions of two players at Stage 1 (see Appendix B. By back- ward induction, we can compute that the NE at Stage is 13
(p (1) = I6 v2 (1) T6/ which deviates from the origi- nal equilibrium point (9. in M1.
9
As is shown in Figure (left & right), CED (a = 0.005, 0.1) finds the NE policy for the min-player the tree-form game. As there is a mismatch between the convergence speed Stage and Stage 3, v at Stage experiences an oscillation and eventually converges to the solution. This phenomenon is consistent with the intuition that the learning process at the initial stage depends on subsequent stages in dynamic games. Besides, we test the behavior of the mrodel-based ED algorithm in this scenario. As is shown in Figure (mid), while ED can approximate the NE policy for the max-player, it suffers from continual oscillations as side effect of following generalized gradient.
We also test CED in a 5-action "Rock-Paper-Sor" Seapee-Sssssoos-Fiiie Water" game denoted by M3. Besides the common rules of the RPS game, fire beats everything except water, and water beaten by everything except beats fire. (b: 9: 91 3: 3) an unexploitable policy for both players, and the unique Nash equilibrium of M3 is constructed when both play- ers use this policy. As is shown in Figure (right), CED (a = 0.01, 0.1) manages to learn the mixed-stratee equilibrium policy, where the black dashed lines correspond to the action probabilities and J. respectively.
6.3. Soccer Game
While the theoretical analysis and the toy problem experi- ments above have suggested the capability of CED to find mixed-stratee strategy Nash equilibrium, here we further verify the conclusion in an infinite- Markov game, the soccer game (see Appendix B.2). To measure the performance of CED, we compute the NashConv of the learned (μ4, v)
6.2. Tree-Form Game
Now we further consider dynamic games, where the Nash cquilibrium at a decision point is affected by the results of subsequent game stages. We examine the learning be- haviors in tree-form game T consisting of three decision points whose payoff matrices are Mi, M2, and M3. re-
7

---

Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium
Soccer Game (uniform coverage)
Soccer Game (uniform coverage)
Soccer Game (uniform coverage)
VI4CB Gamc
CED Io=10"
CED (a-10" 1=10
CED lours)
CED i==10 ..220
CFD (am10 =0100
2
1,-20
10
(sm10" ,,=10
NashCorv
NashCoom
NashCone
10a1
10
10:5
2
10
8
10
10
Iteration
x10
lteration
x10*
Iteration
x10
Figure Learning curve comparisons under uniform coverage in the soccer game
Soccer Game (non-uniform coverage)
150
Performance comparison between learned policy and behavior policy under different coverages
CED Iseed 1)
CED Iseed 2)
Iseed
Player
Player
Win Rate
100
Behavior solicy from uniform
92.4%
NashC
Learned policy from uniform coverage
Betov policy from non-uriform covenage
91.9%
50
Behavior solicy from uniform coverage
91.8%
Learned policy from not- con-uniform coverage
Bul avior solicy from noe-uniform coverage
91.8%
0.5
1.5
2.5
from coverage
45.8%
Iteration
x10
Figure 4. Performance improvements behavior policy by CED in the soccer game
and compare with the result of pessimistic model-based algorithm, VI-LCB-Game (Yan et al., 2024), which prov- ably finds approximate Nash equilibrium offline for infinite- horizon MGs but requires infinitely many samples in theory. In Figure 3 (left), the dashed line corresponds to the joint policy derived from VI-LCB-Game given the minimum amount samples for uniform coverage. Under the same offline dataset, CED steadily reduces the exploitability of the learned policy in this symmetric MG and eventually obtains policy with significantly lower NashConv.
all the related transitions from the dataset D. This makes it impossible to learn exact Nash equilibrium in theory, as preferred action from the NE can be completely removed. As is shown in Figure 4 (left), CED still gradually improves the behavior policy under such random data coverages.
Besides NashConv, we estimate the win rate to intuitively show the improvement over behavior policy by CED. As shown Figure 4 (right), whether under uniform or non- uniform coverage, the policy learned by CED significantly improves the practical performance, with win rates over 90% against the behavior policies. When playing against the approximate Nash equilibrium policy learned by CED from the dataset with uniform coverage, the learned policy from non-uniform coverage still achieves close win rate (45.8%). As no policy can possibly win an NE policy with probability over 50% in symmetric two-player zero-sum game, this result reflects that CED can learn competitive policy even from the datasets without uniform coverage.
Theorem 5.2 proves the convergence of CED under suff- ciently small a and L. However, we are also curious about whether it is possible to use different a and in practice. As is shown Figure 3 (mid), an overly large a makes it significantly harder for CED to converge, while an overly small slows down the speed of learning. Figure (right) shows that does not affect convergence to small (but not too small) regularization parameter c. These results can be viewed as supplement to our theoretical analysis.
6.4. Robotic Combat Game
As CED is model-free and does not rely on the full game in- formation, is, in principle, applicable an arbitrary set of offline data, regardless of the coverage. Here we further ex- amine if it can gradually improve the behavior policy when the coverage is non-uniform, like those single-agent offline RL algorithms. To be specific, we randomly banned one action out of five for each player at each state and removed
Now we show that CED can also be combined with neu- ral networks to approximately solve large-scale adversarial games in an offline manner. We implement CED in a graph- based two-team robotic combat game (see Appendix B.3). We construct an offline dataset that contains 2000 game tra- jectories, where the actual behavior policy for both teams
8

---

Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium
1.0
1,0
CED
0.9
0SP
0SP
0.8
Win Ralls
Win Rate
0.6
0.7
0.5
0.8
0.5
0.2
0.4
500
1000
1500 Iteration
2000
2500
3000
0.%
1000
2000
3000
4000
5000
Iteration
Figure 5. Learning curves under BC initialization (left) and random inirialization (right) in the robotic combat game
Iteration 3000
CED (BC_Init)
OSP (BC_Init)
CED (RD_Init)
OSP (RD_Init)
Iteration
CED (BC_Init)
OSP (BC_Init)
CED (RD_Init)
OSP (RD_Init)
5000
(BC_init)
CED
50%
52%
66%
67%
CED (BC_init)
50%
51%
61%
58%
OSP (BC_ init)
48%
50%
55%
65%
OSP (BC_ init)
50%
55%
CED
34%
45%
50%
65%
CED (RD (iD_init)
39%
45%
50%
57%
(RD_ init)
(RD_init) init)
33%
35%
35%
50%
(RD (RD_init)
42%
43%
43%
Figure 6. Win rate comparisons of CED/ / OSP policy under BC / random initialization in the robotic combat game
a cooperative multi-agent policy previously trained against a rule-based opponent through online RL. We first use su- pervised behavior cloning (BC) to approximate the behavior policy from the dataset. This corresponds to the first step of CED (Algorithm 2). As we verify that the learned behavior policy has win rate around 50% against the actual behav- ior policy, simply use the win rate against the learned behavior policy from BC as the performance measure.
policy constraints in adversarial MGs. This conclusion is drawn from our theoretical and empirical results. With The- orem 5.2 and Theorem 5.6, we prove that under uniform coverage, CED converges to an unexploitable min-player policy without relying on the generalized gradient. In the experiments, our theory is verified by the practical results of CED in multiple game scenarios. We also show that, similar to single-agent offline RI. algorithms, CED can improve the behavior policy from datasets without uniform coverage, even under function approximations for large-scale games.
We compare the last-iterate performance of CED with of- fline self-play (OSP in Chen et al. (2024)) under the same network architecture that represents multi-agent policies on graphs for both teams. We also consider two initializations under behavior policy and random policy. As is shown in Figure 5, under either initialization, both CED and OSP eventually outperform BC-approximated behavior policy, and CED has a comparatively better learning performance than OSP. Figure 6 shows the tested win rates the four learned policies against each other. While the initializations under behavior policy have a clear advantage over random initializations, randomly initialized CED still has close win rate against BC-initialized OSP (45%) under the same number of iterations (3000 or 5000). That is to say, CED can consistently outperform BC and OSP methods.
We hope this work will inspire more research on solving of- fline games. Actually, since CED is constructed based the game-theon thme-theoretti approach of Exploitability Descent, which is also capable of solving imperfect- imperfecttinformaaion information games (IIGs), it is possible to use CED as an offline IIG solver by replacing the state and value with the information state and counterfac- tual value. However, how to estimate counterfactual value under the current policy using offline game data remains an open problem. Further theoretical analysis is still required.
CED has the theoretical limitation that it is only guaranteed to find mixed-strategy Nash equilibria in two-player zero- sum games. However, it may not be the unique way of equilibrium learning under policy constraints, as a wide range of algorithms that exhibit last-iterate convergence (e.g., DRDA (Lu et al., 2025)) are currently available the field of game theory. Combining them with existing offline RL techniques may lead more offline RL algorithms with possibly better guarantees to find Nash equilibrium.
7. Conclusion
In this paper, by proposing CED and analyzing its conver- gence properties, demonstrate for the first time that, unlike in MDPs, an optimal policy can be learned under

---

Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium
Acknowledgements
Markov game. IEEE Transactions on Emerging Topics in Computational Intelligence, 8(6):4033-4044 2024. doi: 10.1 10.1109/TETC1.22243333434
This work was supported in part by the National Natural Science Foundation of China under Grant 62293541 and Grant 62136008, in part by the Beijing Natural Science Foundation under Grant 4232056, and in part by the Beijing Nova Program under Grant 20240484514. We would like to thank the reviewers for providing valuable comments and Ruochuan Shi for helping to evaluate CED under function approximations the robotic combat game.
Jin, Y., Yang, Z., and Wang, Z. Is pessimism provably efficient for offline RL? In International Conference on Machine Learning, pp. 5084-5096. PMLR, 2021.
Kakade, S. and Langford, Approximately optimal ap- proximate reinforcement learning. In Proceedings of the Nineteenth International Conference Machine Learn- ing, pp. 267-274, 2002.
Impact Statement
Kumar, A., Fu, J., Soh, M., Tucker, G., and Levine, S. Stabilizing off- off-policy Q-learning via bootstrapping error reduction. Advances Neurul Information Processing Systems, 32, 2019.
This paper presents work whose goal is advance the field of machine learning. There are many potential societal consequences of our work, and we feel that none of them must be specifically highlighted here.
Lanctot, M.. Zambaldi, V., Gruslys, A., Lazaridou, A., Tuyls, K., Pérolat, J., Silver, D., and Graepel, T. A uni- fied game-theoreeic approach to multiagent reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
References
Brown, G. W. Iterative solution of games by fictitious play. Act. Anal. Prod Allocation, 13(1):374, 1951.
Castro, P.S. Scalable methods for computing state similarity in deterministic decision processes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 10069-10076, 2020.
Lee, C.-W., Kroer, C., and Luo, H. Last-iterate convergence in extensive-form games. Advances in Neural Information Processing Systems, 34:14293-14305, 2021.
Levine, S., Kumar, A., Tucker, G., and Fu, J. Offline rein- forcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint 0rXiv:2005.016433 2020.
Chai, J., Chen, W., Zhu, Y., Yao, 7.-X., and Zhao, A hierarchical deep reinforcement learning framework for 6-DOF UCAV air-to-air combat. IEEE Transactions on Systems. Man, and Cybernetics: Systems, 53(9))5417- 5429, 2023. doi: 10. 10.109//TMMC.222332770000
Littman, M. L.. Markov games as a framework for multi- agent reinforcement learning. In Machine learning pro- ceedings 1994, pp. 157-163. Elsevier, 1994.
Chen, J., Xie, W., Zhang, W., Wen, Y., et al. Offline fic- titious self-play for competitive games. arXiv preprint arXiv:2403.00 00841, 2024.
Lockhart, E., Lanctot, M., Pérolat, Lespiau, J.-B., Morrill, D., Timbers, F., and Tuyls, K. Computing approximate equilibria sequential adversarial games by exploitabil- ity descent. Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 464 470. 2019.
Clarke, F. H. Generalized gradients and applications. Trans- actions of the American Mathematical Society, 205:247- 262, 1975.
Lu, R., Zhu, Y., Zhao, D., Liu, Y., and He, Y. Last-iterate convergence to approximate Nash equilibria in multi- player imperfect information games. IEEE Transactions on Neural Networks and Learning Systems, pp. 1-15, 2024. doi: 10. 00.9TNNIS.2022.33555.
Cui, Q. and Du, When are offline two-player zero-sum markov games solvable? Advances in Neural Information Processing Systems, 35:25779-25777 257911, 2022a.
Cui, Q. and Du, S. S. Provably efficient offline multi-agent reinforcement learning via strategy- wise bonus. Advances in Neural Information Processing Systems, 35:9 11751, 2022b.
Lu, R., Zhu, Y., and Zhao, Divergence-regullrizeed dis- counted aggregation: Equilibrium finding multiplayer partially observable stochastic games. In The Thirteenth International Conference on Learning Representations, 2025.
Hart, S. and Mas- Mas-Colell, A. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5); 1127-1150, 2000.
Nisan, N., Roughgarden, T., Tardos, E.,, and Vazirani, V. V. Algorithmic game theory. Cambridge University Press, 2007.
Hu, G., Zhu, Y., Li, H., and Zhao, D. FM3Q: Factorized multi-agent minimax Q-learning for two-team zero-sum
10

---

Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium
Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. Bridging offline reinforcement learning and imita- tion learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34:11702-11716, 2021.
Yan, Y., Li, G., Chen, Y., and Fan, J. Model-based rein- forcement learning for offline zero-sum Markov games. Operations Research, 2024.
Zhang, Y., Bai, Y., and Jiang. N. Offline learning in Markov games with general function approximation. In Inter- national Conference Machine Learning, pp. 40804- 40829. PMLR, 2023.
Ross, S., Gordon, G., and Bagnell, D. A reduction of imita- tion learning and structured prediction to no-regret online learning. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp- 627-635. JMLR Workshop and Conference Proceedings, 2011.
Zhong, H., Xiong, W., Tan, J., Wang, L.., Zhang, T. Wang, Z., and Yang, Z. Pessimistic minimax value it- eration: Provably efficient equilibrium learning from of- fline datasets. In International Conference Machine Learning, pp. 27117-27142. PMLR, 2022.
Roughgarden, T. Twenty lectures on algorithmic game the- ory. Cambridge University Press, 2016.
Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. Trust region policy optimization. In International Con- ference on Machine Learning, pp. (1889-1897 PMLR, 2015.
Zhu, Y. and Zhao, Online minimax network learning for two-player zero-sum Markov games. IEEE Transac- tions Neural Networks and Learning Systems, 33(3): 1228-1241 2022. doi: 10. 11991NNNNS.200220 2020.3041469,
Zhu, Y., Li, W. Zhao, M., Hao, J., and Zhao, D. Empirical policy optimization for n-player Markov games. IEEE Transactions Cybernetics, (3(10))6443-645)) 2023. doi: 10. (C000//CCYYY.22.179977.7
Shapley, L. S. Stochastic games. Proceedings of the Na- tional Academy of Sciences, 39(10):0095-1100, 1953.
Siegel, N. Y., Springenberg. J. T., Berkenkamp, F., Abdol- maleki, A., Neunert, M., Lampe, T., Hafner, R., Heess, N., and Riedmiller, M. Keep doing what worked: Behav- ioral modelling priors for offline reinforcement learning. International Conference on Learning Representations, 2020.
Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018
Sutton, R. S., McAllester, D.. Singh. S., and Mansour, Y. Policy gradient methods for reinforcement learning with function approximation. Advances in Neural Information Processing Systems, 12, 1999.
Tang. Z., Zhu, Y., Zhao, D., and Lucas, S. M. Enhanced rolling horizon evolution algorithm with opponent model learning. IEEE Transactions on Games, 15(1):5-15, 2023.
doi: 10.1 1911009G.2000030220000
Wu, Y., Tucker, G.. and Nachum, O. Behavior regu- larized offline reinforcement learning. arXiv preprint 1911v:9911.111 2019.
Xie, T., Jiang, N., Wang, H., Xiong, C., and Bai, Y. Policy finetuning: Bridging sample- efficient offline and online reinforcement learning. Advances in Neural Information Processing Systems. 14:27395-27400 2021.
Xiong, W., Zhong, H., Shi, C., Shen, C., Wang, L., and Zhang, T. Nearly minimax optimal offline reinforcement learning with linear function approximation: Single-agent MDP and Markov game. International Conference on Learning Representations, 2023.

---

Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium
A. Omitted Proofs
A.1. Proof of Lemma 4.1
Proof. First, we prove:
Σ
(r)) -bgg(()))) = x(a)) x et
arg max REA(A) REA
Write the corresponding optimization problem:
maximize
Σ
x(a) (r(a) log (a))
aEA
Σ T(a)= =1
s.t.
aEA
<(a) 2 0, Va EA
Using the Lagrange multiplier, we have:
L Σ -(a))
log (()) - / T(a) T(a)-1)
AEA
WEA
OL
- r(a) (10gx(a)+ + x(a)
a(a) -\
@T(a)
7 x(a) = (a) = T(a) x (a(a)
By definition of vk. we have:
(s( = arg max
Σ b(s
Σ
Me(s, (slssaa))uiisssaa (s...)) <DRL (u(s), ps(+))
(())E(())
BEB
aEA
Σ b)) BEB
Σ
Mr((8 (((ss log u(s,b)
arg max (1))
v)(5,b)
aEd
Σ b) (logu((s))) DEB
1 Σ
mn(s (m( (s, log ((s,))) }
arg max (())E((B)
aed
Therefore:
(s( x exp (oggu((,b)
1 Σ
( (sses.))
aEA
which implies:
b)( exp
- Σ
N4 (s, (s,
PR (8, b)
aEA
Σ bz) exp
- Σ
Hy (s (5
FEB
aEA
12

---

Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium
A.2. Proof of Lemma 5.1
Proof. By definition:
(s)
Σ Eu(s,a) bu(ssb)Q""
0)(
ap(3,a) a)
aEA
BER
@p((s,a)
(ss (Qu"(s,
Σ
Σ (ss + u(s, a)
Σ
0u(3,a) a)
ap(s,a)
aEA
dEB
I||s
Σ
v(s (s, () + u(s,a) a)
Σ
v(s, b)
au(3,a) (r(s,a,b) + (VH)(
BEB
BEB
v(s b) (V
I|ss
((s (os,b)Q"H0 (8, b) + Σ
u(s, a)
Σ
0p(3,a)
DEB
aEA
bEB
* Pr(s + u, Σ
(3Q
0=
bEB
where I[-] is the indicator function and Pr(s - a|k: v) is the probability of reaching from s using ls steps under joint policy V),
Then, it is direct to show:
Ōu((), a E Esoxpo [so)] ap(s,a)
Öp(s, a)
Σ Po(5)) S
/ Pr(so - s,k;,,
Σ
u(s,, u(s, (s,
k=
BEB
* Pr(s(k;p,,))
Σ v(s, (ss a)
BEB
pm))(s (s)
BEB
13

---

Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium
A.3. Details in the Proof of Theorem 5.2 Here, we will show that (s,() By Lemma 4.1:
0 when 0. (pp(s,a)
b) exp
(- Σ
pk (s. (s(
(s,
VA (8. b)
aEA
Σ 9))
- Σ (sl
BEE
aEA
Besides:
i @xxp
- Σ Mx ", (1(ss
aEA
(pp)(
bxxp (--))) (4(6
Therefore:
(s,
u)(s, 1-2
(s)(s,a)
aEA
exp (-t Mes, (s)ooos,,00 (Q -su0
Σ pss(s exp MEB
(s,
aEd
(- aEA
Σ v)((,0))exp
WEB
Now, it clear:
Σ Mo(s, (Qua.us (s) - Que b))
lim dvr(s,b)
BEB
0
-
a)))
Σ vo(s,b)
WEB
14

---

Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium
A.4. Proof of Lemma 5.4
Proof. Without loss of generality, we prove the first half that J¹ is unexploitable with respect v/. We show that Σ (s, (es.a)Qi "" (s,), Σ p= as " (s, a, b2) leads to contradiction when (n"," ,a"")") ) is Nash equilibrium aEA
aEA
with full support. By definition, the value at state is:
Ve = Ev as M' (8,a,
DEB
aEd
When (s) has nonzero probability at each b E B, decreasing v v'(s, b1) and increasing v" (s, b2) should decrease the value for the min-player. Therefore, v² is not best response against μ², which contradicts the NE assumption.
A.5. Proof of Lemma 5.5
Proof. By definition:
Σ (u(s,a) (14((8,)+ +
aEA
2
Σ
(((s a) ( + + y
[A]
aEA
2
Σ
(u(s,a) a) - (un(s, a) +v)))
y/
[
cEA
Σ
(u(ss (wE( + +r)))²
Σ
y/
2y
Σ
(m(ss a) - (Mx a) () +r,))
[AT]
TAI
dEA
aEA
GEA
Σ =0
Σ
(u(s,a) (u)(s, + +2))
y²
2y
Σ u(s,a)= - Σ Mu(ssa)+ + Σ
2/
aeA
LA
|A|
|AI
aEA
aEA
REA
y²
2y
Σ (M(s,a) (1)(s, +r)))²
(1 1)
[A
[A|
aEA
y²
Σ (u(s,a) a) - a))
+ +r:))²
LAI
aEA
Therefore:
(8)+ = arg min
Σ (a(s,a)= (ME(), ((x((,,)+==)) +z0))² = arg min
Σ
(a(s,a) (ux(s, ())(s,)++20) - p:))²
(())E((A) aEd
((A) aEd
15

---

Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium
A.6. Policy Penalty Bound
We use the following lemma rigorously demonstrate that the indirect policy penalty in CED can bound the distance between the learned policy Ve and the behavior policy V3-
Lemma A.1 (Policy Penalty Bound), Let Q Qax and Qmin be the maximum and minimum values of Qua and let be any threshold. When Qmaa-Qme it holds that (8)x()) 2s(s))l C for all E S in the CED algorithm.
log(I+C)
Proof. By Lemma 4.1, we have:
(g(s, exp
- Σ (s. (s(5s,))44333)0,.a
(s,
aEA
Σ b9)
- Σ
DEB
aEA
Let / = (a(s.b) PL(a,)]
Σ ()( exp DEB
ux(8, ax (s. Qua.es Qus.ss (s,
Σ
aEAA
By definition of Qmax and Quin. we have:
Qmin Qmax I (s, (s, S Qmax Qmin
Since Σ (1. a) we have:
acA
Qmi
Qmax 1 Σ a)) (s, (s, Qmax Qmin
Since Σ vs(ss D') 1, we further have:
MEB
Qmin Qmax
Qmax Qmiu
exp
< exp
Since
Qmax Quin it holds that exp -Qaine < 1 C. Therefore, 1. 111+ C. [og(1+C)
When C >> 1, clear that exp -mmx- C. When C' 1, have:
Qmax Quin
Quax - Q Qiiu
Qmin - Q max
log (1 + C)) -log (1 C)
log (1 C))
2 1 - C. Therefore, 1. 1 C. Since (ut(s,)) b) vs(s, b)l (s, b)(1 - 1) S uk b) - 1). we have:
is also clear that exp Qmin Qmaa
[Ix(s)) xs())) S Σ -
16

---

Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium
B. Test Environments
B.1. Tree-Form Game
We use a tree-form game as a test environment for both CED and ED algorithms. Figure an illustration of 7, which consists of three decision points with payoff matrices M1, M2, and M3, respectively. 7 starts with Stage (M11 and enters Stage (M2) Stage (Mg) conditioned previous actions. If both the same action 0 or 1, T enters Stage 2. Otherwise, T enters Stage 3.
a = b
M2
M
a x b
M
Figure Illustration of tree-form game
B.2. Soccer Game
We use two-player of the game. The two players are marked with A and B. The player who keeps the ball is marked with a circle. Each player can choose an action from "up", "down", "left", "right", and "stay" at each time step. If the two players collide after the simultaneous move, then the ball possession exchanges. When the ball carrier moves into the opponent's goal, the game terminates. The winning player receives a reward of +100, and the opponent receives a reward of -000. The initial state distribution Pa is set be uniform, and the discount factor 7 set to 0.95.
game small-scale environment for infinite-horizon MGs. Figure 8 is illustration
goa
9086
0g
B
A
Figure 8, Illustration of soccer game
B.3. Robotic Combat Game
We two-team zero-sum robotic combat game environment for large-scale MGs. Figure 9 is an illustration of the game, where each team consists of three homogeneous robots. The game map is abstracted 100-node graph, where each robot can move to unoccupied adjacent node or attack an enemy each time step. The HP reduction is influenced by the terrain and actual distance between the attacker and the target. The robots under different terrains cannot damage each other (e.g., green cannot damage purple but can damage orange since nodes 55 and 72 are at the same level), and the damage to reduced zero.
node 55 from node 61 is much higher than from node 72. A team of robots wins all opponents'
C. Further Explanations of CED
Recall that the NE strategy n² for the max-player always satisfies jr* arg max, {min,,u v)). The idea of ED is to update y along the gradient of min,au(p, v). However, this gradient may not exist since br(μ) == arg u(4, v) may have multiple solutions. Therefore, by fixing an arbitrary v E br(p), generalized gradient Ga(a.v) E Ömin,u(p, v) 2n.
17

---

Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium
Total Step:
Circle Survival: [True, True, True], Square Survival: [True, True, True] Circle HP: [10.00, 10.00, 10.00], Square HP: [10.00, 10.00, 10.00]
100
22
32
38
56
63
67
733
87
20
5
60
66
74
82
86
80
36
99
61
83
2
26
41
49
68
76
88
.65
8
39
44
48
54
58
70
89
34
72
40
19
25
45
52
95
69
91
57
78
16
29
35
96
90
40
47
75
50
97
8
10
17
24
31
85
37
53
80
59
25
100
125
175
200
Figure 9. Illustration of robotic combat game (Team Circle vs Team Square)
used instead. Lockhart et al. (2019) prove that the best iterate of the max-played policy μ can converge to a Nash equilibrium.
For CED (Algorithm 2), since the computation of v is under divergence regularization (indirect policy constraint), uniquely determined by p but is no longer exact best response μ.. The benefit is that we can directly prove last-iterate convergence (see Lu et al. (2024)) rather than best-iterate convergence of The problem is that the update of μ does not follow a gradient induced by its best response and cannot converge to the NE strategy. However, long the limit point is interior in the constrained policy set, we can use the projected update formula in Lemma 5.5 to prove that μ has the same value for all actions at any given state E S. Therefore, the min-player policy v satisfies the property of mixed-strategy NE, ie.. being unexploitable with respect to its opponent policy. The NE policies our matrix/tree form game experiments are the explicit examples. Note that ED itself does not have this property because the learned policy unstable around local optimum of the minimax problem. From the perspective of offline RL, the policy constraints in CED also mitigate the problem of encountering out-of-distribe distribbiitiitoinn states and actions, guaranteeing a bounded distributional shift.
Besides, directly extending ED to deep RL algorithms faces the problem that we need to approximate a best response (BR) of the current in every single gradient update. However, this requirement is relaxed in CED (Algorithm 2). Actually, the "approximate best response" that we require the second inner loop only at the level each single state, under a state-action value function Qua."' preprocessed outside the main loop. This is in sharp contrast to computing an exact BR against the current μ and does not need a separate BR oracle all. In our tabular experiments, we simply traverse all states and compute the current by Lemma 4.1. When employ function approximator for direct approach is update its parameters along the gradient of the current target in the first inner loop. Since this target only changes with pas) at each state E S, it is reasonable for y to take comparative amount of gradient steps as y in each iteration of the main loop.
D. Parameter Selection Details
For the learning rate a, Theorem 5.2 provides guideline that should be sufficiently small. However, an overly small will slow down the speed of convergence, shown in Figure 3 (mid). Therefore, there a trade-off with respect the selection of For the policy penalty parameter Theorem 5.2 also provides guideline that it should not be overly small, as is verified in Figure (right). However, it is risky to set overly large because the interior point condition in Theorem 5.6 is implicitly affected by the policy constraint on the min-player policy v. Therefore, there is also trade-off with respect to the selection of e. From our experience, as long as is sufficiently large for the practical convergence of CED, relatively small e generally guarantees relatively low NashConv of the learned policy v under the same number of iterations.
18


Reviews:
[{"review_id": "nncWrjbFUv", "reviewer": "Reviewer_UYuk", "summary": "This paper introduces Constrained Exploitability Descent (CED), a novel model-free offline reinforcement learning algorithm for adversarial Markov games (MGs). The authors demonstrate, both theoretically and empirically, that, unlike in MDPs, an optimal policy can be learned under policy constraints in adversarial MGs. They prove that CED converges to an unexploitable min-player policy under uniform coverage without relying on generalized gradients. Experiments in multiple game scenarios validate these theoretical results, and similar to single-agent offline RL algorithms, CED can improve the behavior policy even with non-uniform data coverage.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing this paper and providing valuable comments. We are updating the manuscript according to the comments from all reviewers. Here, we reply to your question and concern about the paper.\n\n**[Questions For Authors]**\n\n_**Question**_: Could you elaborate more on the novelty of the proposed method? It seems that the contribution is in terms of the improvement.\n\nYes, we can provide more explanations on the novelty of CED. While the proposed method resembles ED, the learning behaviors are quite different. ED exhibits best-iterate convergence, while CED guarantees last-iterate convergence. The improvement from best-iterate convergence to last-iterate convergence is usually at the sacrifice of policy optimality. Actually, after we apply divergence regularization to the computation of the min-player policy $\\nu$, the convergence of the max-player policy $\\mu$ improves, but the convergent point is no longer a Nash equilibrium policy. The CED method, however, is established upon the surprising observation that the opponent policy $\\nu$ can instead preserve the property of being unexploitable as long as no explicit regularization is applied to the update of $\\mu$. That is why we apply direct policy constraint on $\\mu$ rather than policy penalty under the offline setting. The proposed method eventually guarantees last-iterate convergence, policy unexploitability, and bounded distributional shift at the same time.\n\n**[Methods And Evaluation Criteria]**\n\n_**Comment**_: The proof of theorem 1 relies on the assumption that $\\frac{1}{\\epsilon}\\to\\infty$, I am curious about if the empirical performance will be improved with increasing $\\epsilon$.\n\nThank you for this comment. Actually, while the assumption $\\frac{1}{\\epsilon}\\to\\infty$ theoretically guarantees the convergence of CED, it is not a necessary condition in practical games. As is stated in the second paragraph of Section 6.3, it does not affect convergence to use a small (but not too small) regularization parameter $\\epsilon$ in the soccer game. As is shown in Figure 3 (right), while CED cannot converge under $\\epsilon=10^{-4}$, it actually converges when $\\epsilon\\geq 10^{-3}$. Besides, the performance under $\\epsilon=10^{-3}$ is better than under $\\epsilon=10^{-2}$. Therefore, the empirical performance of CED is not guaranteed to improve with increasing $\\epsilon$.\n\nEmpirically, there is a trade-off with respect to the selection of $\\epsilon$. If $\\epsilon$ is very large, the computation of $\\nu$ is reduced to behavior cloning. The equilibrium property of the converged $\\bar{\\nu}$ is no longer guaranteed since the interior-point premise for Theorem 5.6 can hardly be satisfied. From our experience, as long as $\\epsilon$ is sufficiently large for the practical convergence of CED, a relatively small $\\epsilon$ generally guarantees a relatively low NashConv of the learned policy $\\nu$ under the same number of iterations.\n\nThanks again for your comments. We are looking forward to having further discussions with you.", "claims_and_evidence": "See methods and evaluation below", "methods_and_evaluation_criteria": "* The proof of theorem 1 relies on the assumption that $\\frac{1}{\\epsilon} \\rightarrow 0$, I am curious about if the empirical performance will be improved with increasing $\\epsilon$.", "theoretical_claims": "Seems correct to me.", "experimental_designs_or_analyses": "Simple setup but sufficient to support the goal of this method", "relation_to_broader_scientific_literature": "Contribute to game theory/ multi-agent in offline RL", "essential_references_not_discussed": "I think the authors may already cover most of the references.", "other_strengths_and_weaknesses": "Strengths:\n* The paper presents solid theoretical results, proving that CED converges to a stationary point in deterministic two-player zero-sum Markov games, given the assumption of uniform data coverage.\n\n* CED does not rely on generalized gradient computation.\n\nWeaknesses:\n* Theorem 5.2 only provides asymptotic convergence analysis under assumption of uniform coverage", "other_comments_or_suggestions": "N/A", "questions_for_authors": "* Could you elaborate more on the novelty of the proposed method? It seems that the contribution is in terns of the improvement.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gFoIntneuc", "reviewer": "Reviewer_CuY7", "summary": "The authors extend Exploitability Descent to the offline setting by applying a regularization constraint to minimize distance to the behavior policy. They provide theoretical guarantees for convergence under uniform concentration assumptions, and they provide experiments empirically validate their method, CED, on toy games.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing this paper and providing valuable comments. We are updating the manuscript according to the comments from all reviewers. Here, we reply to your questions and concerns about the paper.\n\n**[Questions For Authors]**\n\n_**Question**_: A critical limitation to scaling up ED with neural networks compared to methods like PSRO[1], MMD[2], and NFSP[3], is that an approximate best response operator would be required for every single gradient update. Wouldn't this easily cripple the usability of ED-based methods in larger games? Could the authors please comment on the severity of this limitation and discuss approaches the field has made towards addressing this? I think adding a paragraph on this would address a blind spot in the limitations.\n\nWe agree that directly extending ED to deep RL algorithms faces the problem that we need to approximate a best response (BR) of the current $\\mu$ in every single gradient update. However, this requirement is relaxed in the proposed method CED (Algorithm 2). Actually, the \"approximate best response\" that we require in the second inner loop is only at the level of each single state, given a state-action value function $Q^{\\mu_\\beta,\\nu_\\beta}$ preprocessed outside the main loop. This is in sharp contrast to computing an exact BR against current $\\mu$ and does not need a separate BR oracle at all. In our tabular experiments, we simply traverse all states and compute current $\\nu$ by Lemma 4.1. When we employ a function approximator for $\\nu$, a direct approach is to update its parameters along the gradient of the current target in Line 191. Since this target only changes with $\\mu(s)$ at each state $s\\in S$, it is reasonable for $\\nu$ to take a comparative amount of gradient steps as $\\mu$ in each iteration of the main loop. We can add a paragraph and discuss the benefit of this difference for potential deep RL extensions.\n\n**[Other Strengths And Weaknesses]**\n\n_**Comment**_: My main complaint with this paper is that only toy games were tested on, and the authors did not consider an extension of CED to function approximation. I think doing so would have made the paper significantly stronger.\n\nThank you for this comment, and we agree that it is more convincing to evaluate CED under function approximation. Currently, we have implemented CED in a large-scale Markov game that simulates a two-team robotic combat scenario, where each team consists of three homogeneous robots. The game map is abstracted as a 100-node graph, where each robot can move to an unoccupied adjacent node or attack an enemy at each time step. The HP reduction is influenced by the terrain and actual distance between the attacker and the target. A GIF illustration for a complete game is provided in the anonymous link https://sites.google.com/view/icml-2025-9335/.\n\nWe construct an offline dataset that contains $2000$ game trajectories, where the actual behavior policy for both teams is a cooperative MARL policy previously trained against a rule-based opponent. We first use supervised behavior cloning (BC) to approximate the behavior policy from the dataset. This corresponds to the first step of CED (Algorithm 2), and we verify that the learned behavior policy has a win rate around 50% against the actual behavior policy. Therefore, we simply use the win rate against the learned behavior policy (i.e., the result of behavior cloning) as the performance measure.\n\nWe compare the last-iterate performance of CED with offline self-play (OSP in [4]) under the same network architecture. We consider initializations under either behavior policy or random policy. Figure A2 in the link shows that, under either initialization, both CED and OSP eventually outperform BC-approximated behavior policy, and CED has a comparatively better learning performance than OSP. Figure A3 shows the tested win rates of the four learned policies against each other. While the initializations under behavior policy have a clear advantage over random initializations, random-initialized CED still has a close win rate against BC-initialized OSP under the same number of iterations.\n\n**[Other Comments Or Suggestions]**\n\n_**Comment**_: The y-axes for Figure 2 need to be labelled. More descriptive figure captions in general would improve readability greatly.\n\nThank you for this comment. In our revision, we have labeled the y-axes for Figure 2 and provided more descriptive captions for the figures.\n\n**References**:\n\n[1] Lanctot, Marc, et al. \"A unified game-theoretic approach to multiagent reinforcement learning.\"\n\n[2] Sokota, Samuel, et al. \"A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games.\"\n\n[3] Heinrich, Johannes, and David Silver. \"Deep reinforcement learning from self-play in imperfect-information games.\"\n\n[4] Chen, Jingxiao, et al. \"Offline Fictitious Self-Play for Competitive Games.\"\n\nThanks again for your comments. We are looking forward to having further discussions with you.", "claims_and_evidence": "The authors both prove and demonstrate CED's convergence properties under uniform concentration assumptions, and they also include an empirical result showing improvement over the behavior policy with non-uniform coverage.", "methods_and_evaluation_criteria": "The evaluation criteria (demonstrating convergence to optimal actions and reduction of NashConv) with and without uniform dataset coverage are appropriate evaluation criteria.\n\nHowever, the games tested are incredibly small. The authors argue in appendix C.2 that larger scale games are not evaluated on because calculating approximate NashConv with RL is an inaccurate measurement to use. I disagree with this argument under certain conditions. I believe this measurement accuracy tradeoff is acceptable if they were to scale up to slightly larger games in which RL algorithms can still reliably find approximately optimal solutions.", "theoretical_claims": "I did not rigorously check the correctness of proofs.", "experimental_designs_or_analyses": "The experimental design is sound. Leaving out an action at every state is a reasonable choice for the non-uniform coverage experiment.", "relation_to_broader_scientific_literature": "Most model-free methods for Markov games consider the online setting. Here, they extend Exploitability descent to the offline setting with Constrained Exploitability Descent.", "essential_references_not_discussed": "The literature review is sufficient and accurately contextualizes this work in the broader field.", "other_strengths_and_weaknesses": "Strengths:\n- Extending online Markov game algorithms to the offline setting has immediate and clear utility for the community as a whole.\n- The paper is well-written, and the claims made are reasonable and validated.\n\nWeaknesses:\n- My main complaint with this paper is that only toy games were tested on, and the authors did not consider an extension of CED to function approximation. I think doing so would have made the paper significantly stronger.\n- I also am concerned with the scalability of CED (or future extensions of it) to larger games, and I ask the authors to address this in Questions.", "other_comments_or_suggestions": "The y-axes for Figure 2 need to be labelled. More descriptive figure captions in general would improve readability greatly.", "questions_for_authors": "A critical limitation to scaling up ED with neural networks compared to methods like PSRO[1], MMD[2], and NFSP[3], is that an approximate best response operator would be required for every single gradient update. Wouldn't this easily cripple the usability of ED-based methods in larger games? Could the authors please comment on the severity of this limitation and discuss approaches the field has made towards addressing this? I think adding a paragraph on this would address a blind spot in the limitations.\n\n[1] Lanctot, Marc, et al. \"A unified game-theoretic approach to multiagent reinforcement learning.\"\n\n[2] Sokota, Samuel, et al. \"A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games.\"\n\n[3] Heinrich, Johannes, and David Silver. \"Deep reinforcement learning from self-play in imperfect-information games.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "I have no ethical concerns for this work."}}, {"review_id": "JKZATnnyXc", "reviewer": "Reviewer_shnB", "summary": "This paper proposes an offline RL method to solve mix-strategy Nash Equilibrium via a game-theoretic method, exploitability descent.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing this paper and providing valuable comments. We are updating the manuscript according to the comments from all reviewers. Here, we reply to your questions and concerns about the paper.\n\n**[Claims And Evidence]**\n\nYes, average-iterate convergence means that we have to preserve an averaged policy from history policies. When the policy is represented by neural networks, such an averaging can hardly be accurate if we only preserve the parameters for the current policy. Even if we save the models of all history policies, it is costly to generate the average policy by querying each one of them. In comparison, best-iterate convergence usually has a similar behavior as last-iterate convergence, with a near-monotone policy improvement over training iterations. Under last-iterate convergence (which we prove for CED), it is reasonable to only preserve the current policy.\n\n**[Methods And Evaluation Criteria]**\n\n_**Comment**_: The main concern is the algorithmic design in Algo 2. From my understanding, we should compute exploitability first and then do descent of it. So \\nu_0 shouldn't be \\nu_\\beta, but br(\\mu_0). In practice it might not influence a lot, but I wonder if it is a simple mistake or the authors do it on purpose?\n\nYes, we do it on purpose. Actually, a major technical difference between CED and ED is that CED optimizes the min-player strategy $\\nu$ rather than the max-player strategy $\\mu$. The purpose of CED is not to guarantee that $\\mu$ approaches Nash equilibrium like ED, which is theoretically impossible when $\\nu$ is regularized. Instead, we prove the unexploitability of the last-iterate $\\nu$ under the convergence of $\\mu$, with a theoretical analysis quite different from common best-iterate analysis on exploitability descent. Besides, CED does not compute an exact best response br$(\\mu)$, but a state-level approximate BR in the last line of Algorithm 2. Since CED optimizes $\\nu$, its computation is placed after $\\mu$.\n\n_**Comment**_: Some baselines are lacking. To me, the proposed will be more convincing if it can beat behavior cloning.\n\nActually, behavior cloning (BC) can serve as the first step of CED, i.e., to compute the behavior policy $(\\mu_\\beta,\\nu_\\beta)$ from the dataset. Since CED initializes $(\\mu,\\nu)$ to be $(\\mu_\\beta,\\nu_\\beta)$, the performance of the behavior policy corresponds to the starting points in Figures 3 and 4. In the tabular case, our existing experiments verify that CED consistently improves the performance of the behavior policy, which is in theory close to the result of BC.\n\nCurrently, we have also implemented CED in a large-scale perfect-information game that simulates a two-team robotic combat scenario, where each team consists of three homogeneous robots. The game map is abstracted as a 100-node graph, where each robot can move to an unoccupied adjacent node or attack an enemy at each time step. A GIF illustration for a complete game is provided in the anonymous link https://sites.google.com/view/icml-2025-9335/.\n\nAmong the mentioned references, Tang et al. (2024) require separate data relabeling and decision transformer training. Li et al. (2022) and Chen et al. (2024) employ PSRO and FSP, respectively, both of which require preserving all history policies. For a direct comparison, we alternatively use offline self-play (OSP in Chen et al.) as a baseline to test the last-iterate performance of CED under the same offline dataset (with 1000 trajectories) and network architecture (for representing the in-team joint policies). We consider two initializations with BC-approximated behavior policy or random policy. Figures A2 and A3 in the link show that CED can defeat BC policy under either initialization and has a comparatively better offline learning performance than OSP.\n\n**[Theoretical Claims]**\n\nThanks for the comment. For the notation $\\mu(s,a)$, it is defined as the probability of selecting action $a$ under policy $\\mu(s)$ (in Line 125 of Page 3).\n\n**[Experimental Designs Or Analyses]**\n\nLines 362-365 on Page 7 suggest that $\\mu^*=\\nu^*=(1/9,/1/9,1/9,1/3,1/3)$, and the dashed lines in Fig 2 correspond to $1/9$ and $1/3$, respectively. We will make it clearer in our revision.\n\n**[Questions For Authors]**\n\nAs is stated in the conclusion part, we agree that it is a good direction to extend CED to imperfect-information games like poker. However, as shown in our response to the other two reviewers, CED has a few technical differences with ED and does not naturally follow the applicability of ED. In terms of offline learning, current theoretical works mainly focus on MGs and have few guarantees in imperfect-information games like history-based extensive-form games (EFGs). While we agree that MG is a simplified formulation, it is still challenging to answer fundamental problems like how to estimate the counterfactual value using offline game data in EFGs.\n\nThanks again for your comments. We are looking forward to having further discussions with you.", "claims_and_evidence": "Is best-iterate convergence better than average-iterate convergence? Would be good to get more detailed comments on this.", "methods_and_evaluation_criteria": "The main concern is the algorithmic design in Algo 2. From my understanding, we should compute exploitability first and then do descent of it. So \\nu_0 shouldn't be \\nu_\\beta, but br(\\mu_0). In practice it might not influence a lot, but I wonder if it is a simple mistake or the authors do it on purpose?\n\nEvaluation demonstrates the convergence to mixed-strategy NE. But the results in Fig 2 to me did not show much gap from model-based ED. \n\nGiven ED is originally widely evaluated on pokers, it would be more convincing to test on pokers. Current environments are relatively toy. \n\nSome baselines are lacking. To me, the proposed will be more convincing if it can beat behavior cloning. In those perfect-information games, it would be better to compare with simple in-sample minimax Q-learning (like multi-agent version of Implicit Q-Learning) introduced in this work:\nTang, Xiaohang, et al. \"Adversarially Robust Decision Transformer.\" *arXiv preprint arXiv:2407.18414* (2024).", "theoretical_claims": "In general make sense. Minor one: The notation of policy is problematic. In Algorithm 1 and 2, the authors have \\mu sometimes a function of s, sometimes of s and a. Would be better to be rigorous.", "experimental_designs_or_analyses": "Fig 2 is relatively confusing. I cannot conclude by looking at the dynamics of action probabilities without comparing to the solution of the game. Shouldn't the \\mu^* and \\nu^* plotted in the figure as in Fig 1?", "relation_to_broader_scientific_literature": "This paper extend the following paper to offline RL setting:\nLockhart, Edward, et al. \"Computing approximate equilibria in sequential adversarial games by exploitability descent.\" arXiv preprint arXiv:1903.05614 (2019).", "essential_references_not_discussed": "Some other offline RL for game solving literatures:\n\nLi, Shuxin, et al. \"Offline equilibrium finding.\" arXiv preprint arXiv:2207.05285 (2022).\n\nTang, Xiaohang, et al. \"Adversarially Robust Decision Transformer.\" *arXiv preprint arXiv:2407.18414* (2024).\n\nChen, Jingxiao, et al. \"Offline Fictitious Self-Play for Competitive Games.\" *arXiv preprint arXiv:2403.00841* (2024).", "other_strengths_and_weaknesses": "Strength:\n\nThis paper studies the open problem of offline equilibrium finding, leverage exploitability descent is an interesting direction.\n\n\n\nWeakness:\n\nThe main issue is the insufficient environment and baselines. I'm happy to increase the score if the concerns are addressed.", "other_comments_or_suggestions": "NA", "questions_for_authors": "Is Markov Game a good formulation? For matrix game it is fine since it's state free. But tree-form game (extensive-form game) is history-based. In this case, will MG be a limited formulation?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper introduces Constrained Exploitability Descent, a model-free reinforcement learning algorithm that exhibits last iterate convergence for two player stochastic games. The authors demonstrate, both theoretically and empirically, that, an optimal policy can be learned using their method. All reviewers were positive or slightly positive about this work, so we recommend acceptance.
Decision: Accept (poster)