Constrained Exploitability Descent: Finding Mixed-Strategy Nash Equilibrium by Offline Reinforcement Learning

Authors: Runyu Lu, Yuanheng Zhu, Dongbin Zhao
Primary area: reinforcement learning
Keywords: offline reinforcement learning, adversarial Markov game, mixed-strategy Nash equilibrium, policy constraint, exploitability descent

Abstract:
This paper presents Constrained Exploitability Descent (CED), a novel model-free offline reinforcement learning algorithm for solving adversarial Markov games. CED is a game-theoretic approach combined with policy constraint methods from offline RL. While policy constraints can perturb the optimal pure-strategy solutions in single-agent scenarios, we find this side effect can be mitigated when it comes to solving 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. The min-player policy at the stationary point satisfies the necessary condition for making up an exact mixed-strategy Nash equilibrium, even when the offline dataset is fixed and finite. Compared to the model-based method of Exploitability Descent that optimizes the max-player policy, our convergence result no longer relies on the generalized gradient. Experiments in matrix games, a tree-form game, and an infinite-horizon soccer game verify that a single run of CED leads to an optimal min-player policy when the practical offline data guarantees uniform coverage. Besides, CED achieves significantly lower NashConv compared to an existing pessimism-based method and can gradually improve the behavior policy even under non-uniform coverage.

Decision: reject
Reviewer scores: 6, 3, 6

Reviews and discussion:
<thread>
creation date:
1729439114469

thread_type:
official_review

<thread_object>
creator: reviewer_ezxc

<content>
summary:
This paper introduces Constrained Exploitability Descent (CED), a novel model-free offline reinforcement learning algorithm designed to find mixed-strategy Nash equilibria in adversarial Markov games. The key contributions of the paper are:

1. The authors propose CED, which combines game-theoretic approaches with policy constraint methods from offline RL to address the challenge of learning in adversarial settings, where the optimal policy can be a mixed-strategy Nash equilibrium.
2. In contrast to previously proposed model-based methods, CED no longer relies on generalized gradient computation.
3. The authors provide experimental validation of CED in matrix games, a tree-form game, and an infinite-horizon soccer game. The results demonstrate that CED can effectively find optimal min-player policies when practical offline data guarantees uniform coverage and achieves significantly lower NashConv compared to existing pessimism-based methods.

strengths:
The primary strengths of this paper can be summarized in the following two aspects:

1. The authors present a novel model-free offline reinforcement learning algorithm that improves upon previously proposed methods for solving adversarial Markov games.  
2. The paper provides both rigorous theoretical analysis and thorough empirical validation.

weaknesses:
Here are the major weaknesses from my perspective:

1. While I acknowledge the authors' contribution in improving the performance of Exploitability Descent, they only compare their method to one RL algorithm for solving adversarial Markov games. This limits the contribution, as the authors have not compared their method to other previously proposed approaches, both from a theoretical and empirical standpoint.
2. In the experimental implementation, the authors only evaluate their algorithm on games with relatively simple structures. This raises uncertainty about whether the proposed algorithm achieves significant improvement over existing methods in more complex, practical tasks.
3. The discussion on the coverage condition is insufficient. The assumption of uniform coverage seems quite strong in the offline RL literature, and the authors have not explored how their algorithm performs under other, less restrictive coverage conditions.

questions:
Based on the discussion of the paper's strengths and weaknesses, I have the following questions for the authors:

1. Is the uniform coverage assumption essential for the analysis? Could the proposed algorithm also work under different coverage conditions?
2. Can the proposed method be extended to other game-theoretic settings, such as multi-agent general-sum games?
3. Does CED outperform other algorithms for adversarial zero-sum Markov games beyond Exploitability Descent (ED)?
</content>
</thread_object>

</thread>
<thread>
creation date:
1729574738485

thread_type:
official_review

<thread_object>
creator: reviewer_spgt

<content>
summary:
This paper studies the problem of offline learning Nash Equilibrium in model-free deterministic two-player zero-sum Markov games. It combines the techniques from exploitability descent and policy constraints in offline learning setting and proposed an algorithm CED. The authors further showed that, under suggested assumptions, the proposed algorithm might converge to a NE. This paper provided some numerical results to support their theorems.

strengths:
1. The proposed algorithm achieves last-iterate convergence under suggested assumptions.
2. Numerical results and graphs are provided to support the proposed theorems.

weaknesses:
1. The theoretical novelty of this paper is limited.
2. Theorem 1 only provides asymptotic convergence analysis, which is sharp contrast even with the direct previous work [1].
3. The proof of theorem 1 relies on the assumption that $\frac{1}{\epsilon} \to 0$. However, in the provided numerical experiments, all $\epsilon$ are set to be small (e.g. $1, 0.1, 10^{-3}, 10^{-4}$).
4. Theorem 2 relies on the assumption that the final stationary point $\bar{\mu}(s)$ lies in the interior of the feasibility set $\Pi(s)$. However, it seems to be a relative strong assumption, for example, it requires the Markov game to have a NE with full support. The paper claims that previous work [1] posed the same assumption but I couldn't find any reference in [1] regarding this assumption. I would be grateful if the authors can specifically indicate where the assumption is specifically stated during their rebuttal.
5. This work establish the convergence to NE by stating that $Q^{\mu, \hat{\nu}} \approx Q^{\mu_{\beta}, \hat{\nu}} \approx Q^{\hat{\mu}, \hat{\nu}}$ and reach the conclusion that $(\hat{\mu}, \hat{\nu})$ forms a NE (386-387). I believe that more rigorous mathmatical statements are required to reach this conclusion, for example, can the error bound  $||\mu_{\beta} - \hat{\mu}||$ be provided?
6. Behavior policies are not provided in numerical results.
7. In line 203 the regularizing term should be $+ \epsilon D(\pi(s), \pi_{\beta}(s))$ instead of negative.

[1] Edward Lockhart, Marc Lanctot, Julien Pe ́rolat, Jean-Baptiste Lespiau, Dustin Morrill, Finbarr Timbers, and Karl Tuyls. Computing approximate equilibria in sequential adversarial games by exploitability descent. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 464–470, 2019.

questions:
1. In the last line of  proof of lemma 4, I don't see why the term $\frac{y^2}{|A|}$ disappears.
2. In lemma 4 it is stated that $(\bar{\mu}(s, a) + p^s_a)_{a \in A}$ stays in the probability simplex. However, it is not clear to me why this is the case. I would appreciate if the authors can provide some insights during their rebuttal.
</content>
</thread_object>

</thread>
<thread>
creation date:
1729753467120

thread_type:
official_review

<thread_object>
creator: reviewer_iyxn

<content>
summary:
The paper presents Constrained Exploitability Descent (CED), a novel model-free offline RL algorithm aimed at finding mixed-strategy Nash equilibria in two-player zero-sum Markov games. CED combines game-theoretic approaches with policy constraint methods from offline RL to find mixed-strategy NEs. The authors also provide theoretical results, showing that CED converges to an unexploitable policy under certain conditions. Finally, experiments in matrix games, a tree-form game, and a soccer game validate that CED outperforms existing methods in achieving lower NashConv. The algorithm is notable for its stability and effectiveness, even with limited offline data.

strengths:
1.	The introduction of Constrained Exploitability Descent (CED) is an innovative contribution to offline reinforcement learning in adversarial two-player zero-sum Markov games. By combining the concepts of Exploitability Descent (ED) with policy constraints typically seen in offline RL, the paper introduces a new approach to handling distributional shifts in a competitive setting.

2.	The paper provides solid theoretical results, proving that for CED converges to a stationary point in deterministic two-player zero-sum Markov games under uniform data coverage assumptions.

3.	The empirical results are thorough and well-presented. The experiments span various scenarios, including matrix games, tree-form games, and a soccer game, demonstrating the practical applicability and effectiveness of CED in different settings.

weaknesses:
1.	The convergence proof relies on the assumption of uniform data coverage, which may not always hold in real-world offline RL settings.

2.	The paper does not provide detailed insights into the computational complexity or scalability of CED, especially in environments with larger state or action spaces.

questions:
As I’m not an expert in this area, I have listed my questions below. If there are any mistakes, please feel free to correct me.

Q1: The convergence proof of CED relies on uniform data coverage. Could you elaborate on how the algorithm performs when this assumption is not met, especially in cases of highly imbalanced or sparse datasets? Are there mechanisms within CED to mitigate these issues, or would it require additional modifications?

Q2: Could you provide more insights into the scalability of CED in larger games with high-dimensional state-action spaces or more complex multi-agent interactions? Or have you tested its computational efficiency or considered potential bottlenecks when scaling up to larger environments?
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper presents Constrained Exploitability Descent (CED), which is a descent type algorithm on the exploitability (also known as duality gap or Nash gap) in order to find Nash equilibria in two-player zero-sum Markov games. The approach does not seem novel in the sense that Descent type algorithms on the exploitability have been proposed before for normal form games, but in terms of Markov Games the AC believes that the proposed approach is kind of novel and interesting. The reviewers also had mixed reviews, two were slightly positive and one strongly negative. In terms of the technical meat, the AC will agree with the negative reviewer; the AC does not see much novelty in here. There are some other weaknesses mentioned (e.g only asymptotic convergence is shown, however prior works have rates). Overall this is a borderline paper with a slight opinion towards rejection.