Research map / Reinforcement learning / Offline RL
Constrained Exploitability Descent: An Offline Reinforcement Learning Method for Finding Mixed-Strategy Nash Equilibrium
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Constrained Exploitability Descent (CED), a model-free offline RL method that adds policy constraints to Exploitability Descent to find mixed-strategy Nash equilibria in deterministic two-player zero-sum Markov games.
Problem
Offline learning of mixed-strategy Nash equilibria in adversarial Markov games with model-free methods; existing pessimism-based methods need horizon or dynamics knowledge or are computationally inefficient, and policy constraints are thought to sacrifice optimality.
Approach
Combine Exploitability Descent with direct policy constraints (on the max-player update) and a KL-regularized best response for the min-player; the KL regularization yields a closed-form, deterministic gradient so the min-player policy converges to an unexploitable (mixed-strategy NE) policy under uniform data coverage, unlike single-agent MDPs where constraints hurt optimality.
Key results
- In the soccer game under uniform coverage, CED steadily reduces NashConv to a significantly lower level than VI-LCB-Game.
- Under non-uniform coverage in the soccer game, CED-learned policies achieve over 90% win rates against behavior policies (e.g., 92.4%, 91.9%).
- In the robotic combat game, CED outperforms BC and offline self-play (OSP) in win rate learning curves, with randomly initialized CED reaching 45% against BC-initialized OSP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CED rather than offline self-play (OSP) | Offline learning in the robotic combat game · Robotic combat game | win rate | Helped |
| Learn with CED rather than behavior cloning (BC) | Robotic combat game · Robotic combat game | win rate | Helped |
| Use CED with random initialization rather than OSP with behavior-policy initialization | Robotic combat game · Robotic combat game, 3000 or 5000 iterations | win rate: 45% | Mixed |
| Apply CED to non-uniform-coverage data | Behavior policy in the soccer game · Soccer game, non-uniform coverage | NashConv | Helped |
| Use CED rather than VI-LCB-Game | Offline equilibrium learning · Soccer game, uniform coverage | NashConv | Helped |
| Increase the learning rate α excessively (ablation) | CED · Soccer game, uniform coverage | convergence | Hurt |
| Make the learning rate α overly small (ablation) | CED · Soccer game, uniform coverage | learning speed | Hurt |
| Use a small (but not too small) regularization parameter ϵ (ablation) | CED · Soccer game, uniform coverage | convergence | No clear effect |
| Use CED to learn the min-player policy under uniform coverage | CED · Matrix games | equilibrium policy learning | Helped |
| Use CED to learn the min-player policy under uniform coverage | CED · 5-action Rock-Paper-Scissors-Fire-Water game | equilibrium policy learning | Helped |
Surprising findings
- Policy constraints, which are suboptimal in single-agent offline RL, do not sacrifice Nash equilibrium optimality for the min-player in deterministic two-player zero-sum games under uniform coverage.
Limitations
- Theoretical guarantee only holds for two-player zero-sum games under uniform coverage and deterministic transitions.
- Mixed-strategy equilibrium recovery needs both players' policies trained by running CED twice with swapped roles.
- Extension to imperfect-information games requires offline counterfactual value estimation that remains open.
Experimental setup
Datasets: offline game datasets generated from behavior policies in matrix games, tree-form game, soccer game robotic combat game offline dataset of 2000 trajectories
Benchmarks: matrix games tree-form game soccer game two-team robotic combat game
Metrics: NashConv win rate
Baselines: VI-LCB-Game Behavior cloning Offline self-play (OSP) Model-based ED
Builds on: Exploitability Descent offline self-play VI-LCB-Game
Closest papers by meaning
- Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.90)
- Efficiently Computing Nash Equilibria in Adversarial Team Markov Games (ICLR 2023 · similarity 0.89)
- Robust and Diverse Multi-Agent Learning via Rational Policy Gradient (NeurIPS 2025 · similarity 0.88)
- Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence beyond the Minty Property (AAAI 2024 · similarity 0.88)
- Robust Adversarial Reinforcement Learning via Bounded Rationality Curricula (ICLR 2024 · similarity 0.87)
- Adversarial Policy Optimization for Offline Preference-based Reinforcement Learning (ICLR 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.