Research map / Learning theory and algorithms / Submodular and game algorithms
Can Reinforcement Learning Solve Asymmetric Combinatorial-Continuous Zero-Sum Games?
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.
Defines asymmetric combinatorial-continuous zero-sum (ACCES) games, proves Nash equilibrium existence via essentially finite game approximation, and proposes CCDO and RL-based CCDO-RL (double oracle with RL best responses) that converge to approximate NE on adversarial covering salesman, capacitated VRP and patrolling game instances.
Problem
Existence and computation of Nash equilibrium in two-player zero-sum games where one player has a finite combinatorial strategy space and the other has an infinite compact continuous space; best responses for the combinatorial player are NP-hard.
Approach
Extends double oracle to combinatorial-continuous games (CCDO) with convergence guarantees, and replaces exact best responses with RL-based approximate best responses (attention encoder-decoder REINFORCE for the combinatorial player, PPO for the continuous adversary), with a practical stopping/discriminant rule for approximate oracles.
Key results
- CCDO-RL reaches approximate NE within about 25 iterations, with exploitability of 0.05 (ACSP), 0.10 (ACVRP), and 0.03 (PG) at 20 nodes.
- On seen graphs, CCDO-RL improves average reward over baselines by 10.08% on average across settings, e.g. 46.98% over heuristic on ACSP-20.
- On unseen graphs, CCDO-RL improves over heuristic and RL-against-stochastic-adversary baselines, e.g. 46.61% and 7.02% on ACSP-20.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CCDO-RL instead of RL against Stoc | ACSP protagonist policy · ACSP 20 nodes, seen graphs | average reward: 3.50$\pm$0.47 -> $\pmb{3.25}$$\pm$0.42; 7.14% | Helped |
| Use CCDO-RL instead of RL against Stoc | ACSP protagonist policy · ACSP 50 nodes, seen graphs | average reward: 4.55$\pm$0.62 -> $\pmb{4.31}$$\pm$0.51; 5.28% | Helped |
| Use CCDO-RL instead of RL against Stoc | ACVRP protagonist policy · ACVRP 20 nodes, seen graphs | average reward: 7.55$\pm$1.16 -> $\pmb{7.42}$$\pm$1.21; 3.01% | Helped |
| Use CCDO-RL instead of Heuristic | ACVRP protagonist policy · ACVRP 50 nodes, seen graphs | average reward: 13.38$\pm$1.70 -> $\pmb{13.28}$$\pm$1.52; 0.75% | Helped |
| Use CCDO-RL instead of RL against Stoc | PG protagonist policy · PG 20 nodes, seen graphs | average reward: 2.71$\pm$0.90 -> $\pmb{2.75}$$\pm$0.87; 1.48% | Helped |
| Use CCDO-RL instead of RL against Stoc | PG protagonist policy · PG 50 nodes, seen graphs | average reward: 4.80$\pm$2.18 -> $\pmb{5.01}$$\pm$1.91; 4.38% | Helped |
| Use CCDO-RL instead of RL against Stoc | ACSP protagonist policy · ACSP 20 nodes, unseen graphs | average reward: 3.56$\pm$0.37 -> $\pmb{3.31}$$\pm$0.35; 7.02% | Helped |
| Use CCDO-RL instead of RL against Stoc | ACSP protagonist policy · ACSP 50 nodes, unseen graphs | average reward: 4.57$\pm$0.58 -> $\pmb{4.39}$$\pm$0.52; 3.94% | Helped |
| Use CCDO-RL instead of Heuristic | ACVRP protagonist policy · ACVRP 20 nodes, unseen graphs | average reward: 7.64$\pm$1.30 -> $\pmb{7.55}$$\pm$1.28; 1.12% | Helped |
| Use CCDO-RL instead of Heuristic | ACVRP protagonist policy · ACVRP 50 nodes, unseen graphs | average reward: 13.27$\pm$1.87 -> $\pmb{13.15}$$\pm$1.59; 0.90% | Helped |
| Use CCDO-RL instead of RL against Stoc | PG protagonist policy · PG 20 nodes, unseen graphs | average reward: 2.50$\pm$0.95 -> $\pmb{2.56}$$\pm$0.92; 2.40% | Helped |
| Use CCDO-RL instead of RL against Stoc | PG protagonist policy · PG 50 nodes, unseen graphs | average reward: 4.26$\pm$2.17 -> $\pmb{4.70}$$\pm$1.94; 10.33% | Helped |
Surprising findings
- Approximate best responses can yield utility below the subgame NE, which never happens for exact DO, so standard DO convergence fails and extra discriminant checks are needed.
Limitations
- Scalability is untested beyond 20 and 50 node instances.
- Complexity analysis is not available for RL or heuristic best-response oracles.
Experimental setup
Datasets: synthetic COP graph instances (ACSP, ACVRP, PG; 20 and 50 nodes)
Benchmarks: ACSP ACVRP patrolling game
Metrics: exploitability average reward generalization reward on unseen graphs
Baselines: Heuristic (Tabu search for ACVRP, LS2 for ACSP, greedy for PG) RL against Stoc
Builds on: double oracle policy-space response oracles attention-based encoder-decoder for combinatorial optimization PPO REINFORCE
Closest papers by meaning
- Towards convergence to Nash equilibria in two-team zero-sum games (ICLR 2023 · similarity 0.89)
- The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback (ICML 2025 · similarity 0.88)
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms (NeurIPS 2024 · similarity 0.88)
- Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.88)
- Memory Asymmetry Creates Heteroclinic Orbits to Nash Equilibrium in Learning in Zero-Sum Games (AAAI 2024 · similarity 0.88)
- Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games (ICML 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.