Can Reinforcement Learning Solve Asymmetric Combinatorial-Continuous Zero-Sum Games?
Authors: Yuheng Li
Wang Panpan
Haipeng Chen
Venue: ICLR 2025 Poster (2025)
Keywords: zero-sum game
combinatorial optimization
reinforcement learning
Primary area: reinforcement learning

Abstract: There have been extensive studies on learning in zero-sum games, focusing on the analysis of the existence and algorithmic convergence of Nash equilibrium (NE). Existing studies mainly focus on symmetric games where the strategy spaces of the players are of the same type and size. For the few studies that do consider asymmetric games, they are mostly restricted to matrix games. In this paper, we define and study a new practical class of asymmetric games called two-player Asymmetric Combinatorial-Continuous zEro-Sum (ACCES) games, featuring a combinatorial action space for one player and an infinite compact space for the other. Such ACCES games have broad implications in the real world, particularly in combinatorial optimization problems (COPs) where one player optimizes a solution in a combinatorial space, and the opponent plays against it in an infinite (continuous) compact space (e.g., a nature player deciding epistemic parameters of the environmental model). Our first key contribution is to prove the existence of NE for two-player ACCES games, using the idea of essentially finite game approximation. Building on the theoretical insights and double oracle (DO)-based solutions to complex zero-sum games, our second contribution is to design the novel algorithm, Combinatorial Continuous DO (CCDO), to solve ACCES games, and prove the convergence of the proposed algorithm. Considering the NP-hardness of most COPs and recent advancements in reinforcement learning (RL)-based solutions to COPs, our third contribution is to propose a practical algorithm to solve NE in the real world, CCDORL (based on CCDO) and provide the novel convergence analysis in the ACCES game. Experimental results across diverse instances of COPs demonstrate the empirical effectiveness of our algorithms.

Published as a conference paper at ICLR 2025
CAN REINFORCEMENT LEARNING SOLVE ASYMMETRIC COMBINATORIAA-COOTINUOUS ZERO-SUM GAMES?
Yuheng Li, Panpan Wang & Haipeng Chen Department of Data Science
College of William & Mary (yli95, pwang12, hchen23) ) 0 @wm. edu
anXiv: [cs.GT] 8 Feb 2025'
ABSTRACT
There have been extensive studies on learning in zero-sum games, focusing the analysis of the existence and algorithmic convergence of Nash equilibrium (NE). Existing studies mainly focus symmetric games where the strategy spaces of the players are of the same type and size. For the few studies that do consider asymmetric games, they mostly restricted to matrix games. In this paper, we define and study a new practical class of asymmetric games called two-player Asymmetric Meaiiinttoral-oontiieettt combinatorial action space for one player and an infinite compact space for the other. Such ACCES games have broad implications in the real world, particularly in combinatorial optimization problems (COPs) where one player optimizes a so- lution in a combinatorial space, and the opponent plays against it in an infinite (continuous) compact space (e.g.. nature player deciding epistemic parameters the environmental model). Our first key contribution is to prove the existence of NE for two-player ACCES games, using the idea of essentially finite game approx- imation. Building on the theoretical insights and double oracle (DO)-based solu- tions complex zero-sum games, second contribution is design the novel algorithm, Combinatorial Continuous DO (CCDO), to solve ACCES games, and prove the convergence of the proposed algorithm. Considering the NP-hardness of most COPs and recent advancements in reinforcement learning (RL)-based so- lutions to COPs, our third contribution is propose a practical algorithm to solve NE in the real world, CCDORL (based on CCDO) and provide the novel conver- gence analysis the ACCES game. Experimental results across diverse instances of COPs demonstrate the empirical effectiveness of our algorithms. The code of this work is available at at/htps:///gii
ZEro-Sum (ACCES) games, featuring a
com/ /
INTRODUCTION
Zero-sum games depict a game theoretic paradigm among adversarial players, where the increase in one player's 's rewards inevitably leads to decrease in the other's (Lipton and Young. 1994). It is prevalent in various real-world domains such as board games (Ghory, 2004), poker (Zinkevich et all 2007), and price games (Kakkar al. 2022). Since solving NE plays vital role in the game theory, from fictitious play (Brown, 1951 1), and double oracle (DO) (McMahan et al. 2003) to Policy-Space Response Oracles (Lanctot et al. 2017), numerous algorithms have endeavored to find NE while
providing theoretical analysis of algorithmic convergence and approximation (Jafari et al.. 2001
Waugh and Bagnell, 2015:
Balandat et al. 2016: Dinh et al., 2022: Tang et all 2023).
One way to classify zero-sum games is based on the symmetry of the players' strategy spaces (Amir et all 2008: Cox et al. 2013: Stella and Bauso, 2018). symmetric game describes a see- nario where players can be interchanged (Cheng et all 2004), meaning that all the players have the same strategy set and payoff matrices. Otherwise, the game is asymmetric. Symmetric games have been well-studied in terms of both theories (Tuyls et all, 2018b Hefti. 2017) and applications (Bichler et all, [2021; Altman et all 2011), partly due to their simple and structural properties. How- ever, in many scenarios such Leduc Poker (Tuyls et al. 2018a), network security games (Wilder

---

Published as a conference paper at ICLR 2025
2018), and cash-in tranitt VRP (Ghannadpour and Zandiych. 2020), the strategy spaces of the play- ers are asymmetric.
Despite the extensive literature on asymmetric games, most current studies remain confined to relatively traditional backgrounds such as the Battle of the Sexes game (Tulls et all 2018b) and Leduc Poker (Tyyls et all 2018a). As kind of strategy space that is ubiquitous in real-world applications, much less exploration has been made toward asymmetric games with combinatorial strategy spaces, except for some sporadic studies like min-max traveling distance of multi VRP (Naaaiihaa et al., 201 3), security scheduling with attacker (Jain et al. (01 D. max-min influence maximization (Chen et all, 2016), etc. Typically, these studies assume finite action spaces for all players in asymmetric game settings. These studies neglect another broad class of asymmetric games where the other player's strategy space is not only asymmetric but also infinite compact (e.g., real- valued vector intervals). Such infinite compact strategy spaces in asymmetric games have broad implications in the real world, which can be interpreted as the physical or environmental parameters of COPs, such as the attractive degrees targets in the security game (Xu et al.. 2021). uncertain net- work edge weights in influence maximization problems (Kalimeris et al 2019) and unknown outer condition effect the charging demand in facility location problems (An 2020 Tirkolaee et all 2020), and customer demand in routing problems (Florio et al. 2023).
Formally, we define this class of games zEro-Sum (ACCES) game with dynamics of simultaneous move and static form. Player I's strategy space is combinatorial, while Player 2's is infinite and compact with a continuous utility function. As an illustrative example (more examples in Section (6) we consider a patrolling game between a defender (Player 1) and an attacker (Player 2). To prevent attacks from the attacker, the defender chooses a feasible route to patrol subset II of all targets {1, 11.2.....N 3 meanwhile satisfying the total distance constraint Lall because of limited patrol time. For the attacker, the strategy is the attack probability vector {P1. PP.......,,P fo for the target set. Besides, each target E f1.2...., has its own value v;. The utility function for the defender is the expectation of successfully protected target values, i.e. Ua = Σ P.0.IIn The attacker's 's utility function is then: Ua = -Ua-
two-player Asymmetric
For this new class of games, our key research question is:
"Whether and how can we solve asymmetric combinatorial-coniimuon zero-sum games?"
This question can be decomposed into the following sub-questions:
1) Does NE exist? Before finding solutions to ACCES games, the first question is whether such games are guaranteed to have NE. Due to the asymmetry of the game, especially the different, less-structured properties of the strategy sets coominntoriallccotinnoo
this question is much less straightforward than established results in matrix games (Nash et al 1950). market games
(Peck et al. 1992), and continuous games (Glickshergl 1952: Fan. 1952 Reny. 2005), for which the existence of NE has already been proven.
2) Is there any algorithm that can converge to NE? If the existence of NE holds, the next ques- tion is then to find algorithm that converge to the NE. Due to the infinite strategy of one player, common qquilibruum-seeking algorithms (McMahan et al. 2003; Dinh et al. 2022) in matrix games lose their convergence guarantees because they rely on the finiteness of strategy sets ter- minate iterations. On the other hand, classic algorithms in continuous games (Balandat et all 2016 Adam et al. 1) do not work for ACCES games because the continuity of the unity function no longer holds with the discrete (combinatorial) strategy set of the other player.
3) there a practical algorithm that we can actually implement in the real world? While is critical to understand the theoretical questions above, an equally important practical question is how can we design efficient and practical algorithms to actually solve the ACCES games? This is extremely challenging as even sub-problem of finding the best response for the combinatorial strategy space of one player is known to be NP-hard, let alone the entire ACCES game.
We give YES answer to each of the three sub-questions. Our main contributions are as follows.
1) We are the first to summarize and define the class of ACCES games, elucidating its rationale and practical significance via examples from min-max games and security games.
2) We prove the existence of mixed NE in ACCES games through the finite-game approximation, which relies on two important properties that have yet to be established, the weakly sequential com-
2

---

Published as a conference paper at ICLR 2025
pactness and continuity of expected utility function. To address this gap, we prove these properties in Section 4, which provides further insight into developing solution algorithms for ACCES games.
3) We propose two solution algorithms, CCDO and CCDO-RL, for solving the ACCES games. CCDO extends the idea of double oracle (DO)-based solutions from zero-sum finite games (McMahan et all, 2003) to ACCES games, while with different convergence guarantee results. Due to the NP-hardness in most COPs, is infeasible to find the exact best response for the combinatorial player in limited time. Therefore it's critical to consider the solution algorithm and convergence analysis with approximate best responses (ABRs). We bridge this gap by proposing CCDO-RL which adopts RL as an efficient sub-routine to compute the ABRs, inspired by recent advancements in applying reinforcement learning to learn fast, effective. and generalizable solutions for COPs (Khalil al. 2017: Nazari et al., 2018 Deudon al. 2018 Bengio et all 2020; Chen al., 202 1 Berto et al_ 2023). Furthermore, novel convergence analysis of CCDO-RL is studied, along with different ABRs' influence on convergence have been discussed Section 5.
4) We validate our algorithms on three distinct instances of ACCES games adversarial cover- ing salesman problem (ACSP), adversarial capacitated vehicle routing problem (ACVRP), and pa- trolling game (PG). Empirical results are well aligned with our theoretical insights: our proposed CCDO-RL algorithm can learn to converge to NE in all game instances. For the player with the com- binatorial strategy space, our algorithm is better than baselines regardless of the type of adversary or problem size, especially in terms of generalizability.
2 RELATED WORK
Symmetric and asymmetric games. Symmetric games are initially proposed by (Von Neumann and Morgenstern 1947) and studied under the context of non-cooperative (Nash et al., 1950). economic (Hammerstein and Selten, 1994), and two-person (Washburn et all, 2014) games. Amir et al 2008) focus on pure strategy equilibrium with supermodular payoff func- tions. Feyl (2012) studies symmetric games only with asymmetric equilibria. A few studies extend the theories on symmetric games to asymmetric settings (Cox et all 2013) Tuyls et all (018a), or transform asymmetric games to symmetric ones (Tuyls et al. 8a). These studies usually concentrate on specific type of classic game such as metric games or poker. Narasimha et al. (2013) and Carlsson et al. (2009) are among the first to consider asymmetric games involving a combinatorial player in a variant of traveling salesman problem with multiple vehicles. Jain et al. (2011) studies security game where the defender decides the location of sources and the attacker chooses a path to find the source. Xu et al. (2014) extends the idea of Jain et al. (201 1) and consider discrete time domains and moving targets. In the covering problem, Raahmatallabi et all (2019) considers the failure of some nodes and models it as one zero-sum game. All of these studies are limited to finite games.
Equilibrium learning in zero-sum games. DO (McMahan et al., 2003) a powerful tool for solv- ing complex strategic normal-forn games by iteratively expanding the players' strategy sets and efficiently finding equilibria. The idea has been extended toward better NE computation, different forms of games, convergence rate, etc. McAleer al. (200)) and Zhou et al. (2023) focus on accel- erating the computation of the approximate equilibrium. Different diversity metrics are proposed by (Balduzzi et al] 2019 PPree-Nieves et all, 2021; Liu et all 2021] Yao et al.. 2024) find more effective and various strategies. In extensive-form games, McAleer et all (2021) works to achieve linear convergence to approximate equilibrium and Tang al. (2023) studies sample complexity. Except for DO and its variants, NE learning in zero-sum settings remains appealing in periodic games (Fiez et al. 202 polymatrix games (Cai al., (016).. and Markov games (Zhu and Zhao 2020, etc. As far as we know, they are all limited to matrix games in theories related to the existence and convergence of NE although McAleer et all (2021) conduct experiments on continuous-action games by Deep RI. Balandat et al. (2016); Adam et al. (2021) study the NE convergence of contin- uous games but two players are symmetric.
RL for COPs. RL has emerged as effective and generalizable method to solve COPs, where the underlying idea is to decompose the original combinatorial action selection COPs into a sequence of greedily selected individual actions, using deep RL policy value function that is usually rep- resented via various function approximation methods such as graph neural networks (Khalil et all 2017: Joshi et all. 2019 Manchanda et al.. 2020), recurrent (Bello* * et all (017), and attention net-
3

---

Published as a conference paper at ICLR 2025
works (Kool et al. 2018). Search algorithms, such active search (Hottung al 2022). Monte Carlo tree search (Fu et al.. 2021), and multiple rollouts (Kwon et al., 2020). are further integrated into these frameworks to enhance the solution qualities of RI algorithms during inference time. In- tegrating representation learning and search algorithms, RI. has shown promising abilities to learn efficient and generalizable solutions complex COPs. This motivates to adopt RI. the back- bone method to compute the COPs in a subgame of the ACCESS games.
PRELIMINARIES
3.1 TWO-PLAYER ASYMMETRIC DOMBINATORIAL-CONTIINOOO ZERO-SUM (ACCES) GAMES
Most two-player zero-sum strategic games are described as a payoff matrix xm where the rows and columns represent pure strategies for the two players. This does not hold for ACCES games because the strategy space for the continuous player is infinite. Hence, we provide the first formal formulation of ACCES games.
Formally, we represent a two-player ACCES game tuple (X, Y, u). where is the combinatorial but finite space, and Y is compact and infinite metric space, as the pure strategy space for players I and 2 respectively. u is the utility function mapping the joint strategy space X x to a scalar R, with the continuity on Y when fixing z e X. The utility function of Player is u, and for Player is u. For the security patrolling game exemplified in the introduction, X should be all routes that satisfy the distance constraint, Y is the real vector interval [0, 1] for the attack probability p: on each target i = I,... N, and u is the expectation of successfully attacked target negative values.
The mixed strategy in the combinatorial contriuuuusosssuuusu game defined separately because two players own entirely different forms of strategy spaces. For Player I, the set of mixed strategies can be written as Σ (v (1(x1),....) [=(=x),...,pxxxx)) Σ p(æ:) p(x;) > 0), where p(x:)) is regarded as the chosen probability of the pure strategy I; E X. For Player 2, mixed strategy is Borel probability measure q on which can be seen probability distribution function q where F is a- algebra of Y. The set of mixed strategies of Player 2 is denoted by Dy. Every mixed strategy in Ax corresponds to a distribution on feasible routes in the security patrolling game, and that in Ay passes as a cumulative distribution function defined on [0, 1]x
[0. 1].
Due to the infiniteness of strategy space V. the support of q may be infinite. Given a mixed strategy (p,g) Ax Dr & A, the expected utility function of Player I can be defined as
U(p g) = 3 p(z)u(z, v)d4.
(1)
zEX JEY
Correspondingly, the expected utility function of Player 2 is -U (p.
3.2 NASH EQUILIBRIUM IN TWO-PLAYER ACCES GAMES
In two-player ACCES games, a mixed strategy pair (p* .²²)) ))) Nash equilibrium (NE) if and only U(p,a*) U(" .q") & U(p", .), vp E Ax,9E Ay.
(2)
Additionally, we denote e- NE as mixed strategy pair (p*,9*)
q²*) which satisfies U(p.q*) - e & U(p".q .q") & Upp". q) + e, Vp Ax,qE Ly.
(3)
Best response BR, (m=) defines the best pure strategy for Player i for fixed mixed strategy π_ of the other player -i. In ACCES games, the set of best responses for the two players are:
(B1(g) = fi (U( q) max (a', 4)), BI2, (p) = {y E Y!U(p,)) = min Up,.)')).
(4)
x'eX
y'eY
In many situations, finding the best response inherently difficult, especially most combinatorial optimization problems which are P-arar.. Approximate or heuristic algorithms are often used to
sacrifice solution accuracy for faster computation. We use E- best response (BR;( to define the solution that is no worse than the ground truth best response by
BR (g)
{o XUU > max UU', x'eX
ct. BRİ(P) = (v e ( & min U(p.v) + + (5)
y'eY
4

---

Published as a conference paper at ICLR 2025
4 THE EXISTENCE OF NASH EQUILIBRIUM
We first study the existence of Nash equilibrium in ACCES games, which a critical step before designing any actual solutions. For a two-player ACCES game G {X, Y, u,), the strategy set X of Player 1 is finite consisting of certain permuatioon/comminattin of nodes, although the number of the strategy set is possibly exponentially large. In contrast, the strategy set Y of Player is an infinite and compact set. Although the utility function of Player 2 are continuous on Y when fixing E X, but its strategy's infiniteness disqualifies the finite condition of matrix games and makes the convergence to NE less straightforward. Meanwhile, the discreteness of X destroys the continuity of the utility function on X x Y. To whether the existence of mixed strategy NE still holds in ACCES games, we must better understand the game structure. Our thought flow is as follows.
On a high level, we first prove Proposition weakly sequential compactness in the mixed strategy product space of ACCES games. Then, the continuity of the expected utility function on the product space, which contributes to the existence proof and the following convergence of algorithms in Section 5, is proven in Proposition 2 Note that these are two key technical novelties that not only are critical intermediate steps for the proof of the existence of NE, but also build the foundation of the analysis of convergence to NE of our proposed algorithms in Section 5.
Proposition 1 [Weakly Sequential Compactness.] Set the ACCES game is G = (X,Y, where X is finite, Y is nonempty compact metric space, and the utility function u is continuous Y fixing r E X. Then the joint mixed strategy space A Ax x By is weakly sequentially compact.
Proof sketch. To prove the product space X x Y is weakly sequential compact, we just need to prove two parts, weakly sequential compactness and separability of X, Y based on Lemma [ See the full proof in Appendix(A.
Proposition 2 [Continuity of Expected Utility Function.] The expected utility function U(p g) Σ Exex Syey p(x p(z)u(z, dy is continuous joint mixed strategy space A. Vp Ax,q Ay.
Proof sketch. We prove the continuity of the expected utility function by definition. First, define the metric distance on mixed strategy sets Ax, Dy and their product space Ax x Zy. Following this, the distance between two mixed strategy pairs (p. g) and (p',q') can be scaled to the distance sum between p. p and q. q because of the compactness of Y, the continuity of utility function on Y. and Proposition The full proof is provided in Appendix A
Via Proposition 2 and the continuity of U on Y, the following two statements hold:
When Pa = in Ax On = in Av. Upn, gn) (p..)). When Pa = p in Ax Un - in Y. U (po: Mn) + (p, v).
Secondly, for the proof of equilibrium existence, we build on the idea in (Mverson 1991 which approximates the strategy spaces by finite grids. To describe the approximation and the feasibility of approximation by finite games, we first introduce definitions of a-approximate games and essentially finite games. Based on these definitions, we establish Propositions 3 and 4 where the proofs are provided in Appendix A.
Definition 1 [a-Approximate Game.] Assume there exist two strategic games G Y,,Y, (X,Y, u²) in which u and u' are bounded and measurable utility functions. If every joint strategy (5,y) X Y. |u(x,,) u' (1., y)1 & a, then G' is an a-approximation of G.
u).
Definition 2 [Essentially Finite Game.] The game G = =X,Y,u) is essentially finite, if and only if there exists some finite strategic game 9 = (X, Y, fi) and measurable functions f1 X - X, fa Y - Y s.t. u(x,y) (ff((=), fa(v)), V(z, v) X Y
Proposition 3 [Approximate NE of ACCES. g = (X where is an ACCES game. (p" 9²") is an c-equilibrium of g'. then (p" 9²) is an (e 2a-) equilibrium of g.
= Y,ū) is a-approximation of = <X, (XYYuu) Y,u),
Proposition 4 [Essentially Finite of ACCES.) For an ACCES G. Va 0, there exists essentially finite strategic game 9 <X, Y, ú), s.I. 9 is a-approximation of g.
5

---

Published as a conference paper at ICLR 2025
Proposition 5 [Convergence of Approximate ACCES NE.] 9 is an ACCES game, for each (Pn, 9n) is e,-NE of G, (Pn: 9n) = (p* q²),, En - then (p" .9*) is an e-equilibrium of g.
CrppositionS]holde naturally. On account of Proposition B E and the existence of equilibrium can be obtained. We have provided a further discussion of the existence of NE for N-player ACCES games in Appendix A.2
Based on Chapter 3 in Myerson (1991) and Proposition
(X,Y, where X is finite space, Y is nonempty compact metric space, u X X - R is a continuous utility function on Y when fixing E X. Game G has a mixed strategy Nash equilibrium.
Theorem [Existence of NEJ
Proof sketch. For any sequence {ax} - O. there exists an essentially finite game sequence {9k} (Prop such that its NE {(r 9 }} is 20x NE of the initial game G (Prop3). We can prove that the sequence (Pk, 4 converges and its convergent point (p*, (²)) is the NE of the game G (Prop
Remark 1 The proving idea of approximating by finite games is one feasible and concise way to prove Theorem A After analyzing the basic properties in Proposition 7 and the existence of NE can also be proved by the fixed point theorem in (Glicksberg. 1952) while going little bit of detour to fit the problem into its framework.
CCDO & CCDO-RL
In this section, we introduce the Coanbinntooial-Connioooo Double Oracle (CCDO) algorithm and prove its convergence in Section 5.1 and propose the practical version of CCDO, CCDO-RL with the convergence analysis in Sections 5.2 and 5.3 respectively. CCDO has similar algorithmic framework to DO but differs significantly in the convergence analysis. Moreover, we consider one phenomenon that never occurs in DO but is common in the COPs: the performance of the approxi- mate best response (ABR) to another player's 's mixed policy is even worse than that of NE. To handle this phenomenon, we design a CCDO approximate (CCDOA) algorithm, and further propose CCDO- RL (Algorithm[I, where we use RL as the underlying oracle solver for both players in the CCDOA framework inspired by recent advancements in using RL to solve COPs. We provide a further con- vergence analysis on CCDO-RL, and examine how different ABRs influence convergence.
5.1 CCDO AND ITS CONVERGENCE
DO is originally proposed solve NE in the large zero-sum matrix games (McMahan et al. 2003). The key idea is to iteratively compute the mixed NE in the subgame and expand the subgame by the best response (BR) the current NE of the subgame. We adopt the same algorithmic framework and propose CCDO, to solve the NE in ACCES games (see Algorithm (2.. The difference with DO and its variants ODO/XDO the stopping criterion, Line Algorithm 2 The original part in DO is subgame sets both remain unexpanded, i.e. X Xs, Yk+1 Y& which naturally holds on finite games but cannot be possibly guaranteed in ACCES games, even if iterating infinite times because of Y's infiniteness.
We should not ignore that DO and its variants ODO/XDO can only guarantee convergence under a finite action space because the subgame can become the original game by adding the best response over a finite number of iterations. The infinity of the strategy space not only invalidates this guar- antee but also fundamentally alters the structure of convergence analysis. Besides, the two players need to be analyzed separately in the proof because of the asymmetry of ACCES games.
The convergence guarantee of CCDO applies matrix games but also in the ACCES game. In other words, CCDO is the extensive version of DO. First, we prove the convergence of CCDO, providing the basis for the subsequent convergent proof of CCDOA and CCDO-RL. The full proof is provided in Appendix
broader range of zero-sum games, not only in
Theorem 2
Given two-player ACCESS game G (X,Y,u) u), where X is finite, Y is nonempty compact set, and the utility function u is continuous in when fixing the strategy in X, we have
1. When O. every weakly convergent subsequence in the subgame equilibrium sequence Upp. } converges to the equilibrium of the whole game, possibly in an infinite number of iter- ations.

---

Published as a conference paper at ICLR 2025
2. When Algorithm 22 converges to -qqilibrium in a finite number of epochs.
5.2 CCDOA AND CCDORL
Due to the NP-hardness of most COPs, finding the exact BR for the combinatorial player is computa- tionally impractical. Hence, we use more practical approximate version, CCDOA AlgorithmmBot Appendix [B), to solve the approximate NE. However, the approximation of BR may cause circum- stances where the utility of the approximate best response lower than that of NE in the subgame which never happens in CCDO. This issue not only has a tricky effect on the convergence analysis but adds computational overhead to solving NE and the memory burden of saving strategies, and may even prolong the iteration round. To address this, two discriminants (lines 6-13 in Algorithm 3 are added guarantee the optimality of the two ABRs 2 9 in the subgame G* (Xx, Yk. u).
There have been studies using RL to learn generalized policy for certain COPs in graphs (Khalil all, 2017 Nazari et al., 2018 Bengio et all 2020: Ou et al., 2021: Feng et all. 2025). The key idea is to decompose the node selection into a sequence and learn a heuristic policy for se- quentially choosing nodes. The RL policy usually trained on seen training graphs with the hope of generalizing to unseen test graphs of similar characteristics. Such generalization has been fur- ther enhanced via graph embedding techniques such as Structure to Vector (Dai et all (0016) and Graph Convolutional Networks (Kipf and Welling, 2016) as the underlying value/policy network. The adversary's 's task is to choose optimal parameters in COPs. RL would also be a useful method to enhance the adversary's 's generalizability and solvability for diverse instances of the CO problem. Hence, we propose CCDO-RL (see Algorithm[D] D. a practical implementation of CCDOA where we use RL and graph embedding techniques as the underlying method find the approximate BR for each player (Line 4 of Algorithm DD. The mixed NE is solved by the supported enumeration algo- rithm (Roughgarden 2010), utilizing the Nashpy implementation (Kngght and Campbell, 2018).
Algorithm 1
Double Oracle Reinforcement Learning Algorithm
Input: Game G (X, Y, u.), e > O.
Output: of.
1: Initialize strategy set 11,0, T22.-
2: repeat
3: Solve the mixed equilibrium of in the subgame (II1A: l22,k)
4: Find the approximate best response by RL algorithms (Tī k.
5: IT,++1 11 U ). T22
T22 (-
6:
ir (TT,
o2 < (o())) then
7:
I1,+11 II1,..
8:
else if (o x2
> U(at) then
9:
12 122,k.
10:
end if
11:
until UTT o U(o )) &
5.3
CONVERGENCE OF CCDOA AND CCDO-RL
Next, consider the convergence guarantee of CCDOA and CCDO-RL with ABRs (full proof in Appendix[B: [.. Apart from the convergence analysis, the influence of ABRs with different degrees of approximation on the number of algorithm inner iterations is also explained further. Additionally, the computational complexity of CCDO-RL is provided in Theorem Appendix[B
(X,Y, u), where X is finite, Y is a nonempty compact set, and the utility function u is continuous in Y when fixing the strategy in X, with e best response oracle for Player 1 in X and eg best response oracle for Player 2 Y. we have
Theorem Given
1. When > 0, for any form of approximate best response oracles, CCDOA and CCDO-RL -RL can converge to a finitely supported (E + E + E2) equilibrium in a finite number of iterations.
2. When = 0, if the approximate response oracle for Player 2 has uniform lower bound every mixed strategy in Ax, i.e.
Vp E (p. BRF(p) > min Up. v) + cv.
(6)
yEY
7

---

Published as a conference paper at ICLR 2025
then CCDOA and CCDO-RL RL must converge to an (c + e2) equilibrium in a finite iterations.
When e if CCDOA and CCDO-RL produce infinite iterations, every weakly convergent subsequence converges an e1- equilibrium.
The convergence result for > 0 in Theorem 3 Item 1 is similar to Theorem 2 Item 2, converging to the approximate NE in a finite number of iterations. If the iteration continues indefinitely, the approximation of NE found by CCDO-RL depends solely
that of Player I's ABR, i.e. EY. When 0, CCDO may continue for an infinite number of iterations the same problem setting. In contrast, CCDO-RL terminate in finite rounds if the approximate error of ABRs for Player is bounded below by εy or the condition in Remark is satisfied by Player or
Except for the uniform lower bound for Player in 1 if two absolute differences be- tween BR and ABR do not converge to zero, including divergence and convergence to positive number, i.e.
Remark
max U (x, 9 U( k+1 x 0 or UP Ve+1) max Up y) - O,
zeX
then CCDOA and CCDO-RL must terminate in a finite number of iterations, even if
6 EXPERIMENTS
With theoretical guarantees on the existence and convergence of NE for ACCES games, we are also interested in how our proposed algorithm CCDO-RI works empirically. To evaluate this, we conduct experiments of CCDO-RO RL on three distinct ACCES game instances introduced in Section [.] and analyze the performance of CCDO-RL. in Section 6.2 Section 6.2.1 aims to empirically demonstrate the convergence (Fidu) of the algorithm CCDO-RL over realistic CO problems, and show its consistency with Theorem 3 Section 6.2.2 intends to show the average reward (to seen training graphs) well as the generalizability (to unseen test graphs) of the combinatorial player in real- world ACCES games (shown in Tables and 2
6.1 THREE INSTANCES OF ACCES GAMES
We consider certain COP which is parameterized with (0:), where is the index of nodes (such as a target in security games) e.g., such parameters can be interpreted as attack probability of targets. In real-world applications, we often need to estimate such parameters before solving the COPs. Unfortunately, the estimation [d.) often bears gap the true value [0:), which derives from e.g. environment (aleatoric) uncertainty, model (epistemic) uncertainty, or an attacker trying to manipulate the defender's utility. We use a generic model to formulate this gap:
0: 0 + y- Tj:
(7)
where y represents the strategy of the nature/attacker, т; is the environment factors like weather and transportation conditions, human subjective factors like the preference of the attacker. Such abstraction can represent a wide range of ACCES games, such as facility location cover- ing problems An (2020): Tirkolace et al. (2020). CVRP Gendreau al. (2014): Dinh et all (2018); Florio et al. (2023), security patrolling (OP) (Xu et all 2021). and influence maximization problem Kalimeris et al. (2019). We describe three instances of ACCES games based on the model 7
Adversarial Covering Salesman Problem (ACSP): In a map of cities, every city i has coverage 0, A salesman finds the shortest path such that all cities are visited or covered, with 9 influenced by physical factors and transportation parameters based on Eq. 74. The salesman is Player 1 where X consists of the feasible paths of the salesman. Nature is Player 2 with = [0. 1] a y, N.
The utility function of Player u is the opposite of the total traveling distance.
Adversarial Capacitated Vehicle Routing Problem (ACVRP): vehicle with a constrained ca- pacity of goods finds the shortest path under the worst case with the ieh customer's demand 0; changed by environmental factors т; and weather parameter y on Eq. (7) The vehicle Player where X is the set of the feasible path Nature is Player 2 where Y is [0, 1]x y. K N. The utility function of Player 1 u the opposite of total delivery distance satisfying all the demands of customers.
8

---

Published as a conference paper at ICLR 2025
Patrolling Game (PG):
The patrolling game is described in the introduction.
For the problem instances, we run our algorithm on two problem sizes: 20 nodes and 50 nodes. The detailed description and problem parameters of the three game instances are in Appendix [D]
6.2 PERFORMANCE OF CCDO-RL
Two aspects are evaluated for the performance of CCDO-RL, i.e., i) Convergence to NE (Section 6.2.1) exploring whether CCDO-RL can compute the NE, and ii) Protagonist policy's s average reward and generalizability (Section 6.2.2). Generalizability refers to the ability of RL models trained on previously seen graphs (problem instances). to perform well on a new set of unseen test graphs. The model's 's usability is enhanced by generalizability, rather than focusing solely on the average reward, which is critical motivation in the literature on RL for COPs (Khalil et al., 2017: Kool et al., 2018).
For all the problems, CCDO-R RL adopts the REINFORCE algorithm with an attention-based encoder- decoder framework (Kool al 2018) (used as an inductive graph representation component) to learn generalizable COP solver for Player 1 (protagonist), and PPO to train policy for Player 2 (adversary) whose strategy space is continuous. CCDO-RL is trained on a set of 10,000 graphs (with 20 or 50 nodes). The hyperparameters of CCDO-RL specified in Appendix (D) (Table 3). Our code is included as supplementary material and will be open-sourced for ease of reproduction.
6.2.1 CONVERGENCE TO NE
Exploitability is common metric to describe the closeness to true NE by calculating the sum of per- formance distances between each new best response and subgame NE, i.e. Σ U (M a-i,))
(a) in the general two-player game. Since our game is zero-sum, the calculation is follows:
Exploitability(o) = max U(T1 min U T2). R2
Tit
From Figure [ we can see that CCDO-RL can converge approximate NE in 25 iterations or less (in the PG setting), reaching 0.05 ACSP, 0. ACVRP, and 0.03 in PG with 20 nodes. Similar results are observed in problems with 50 nodes (see Figure Appendix D.. These results validate the effectiveness of CCDO-RL in finding the NE for various types of games.
3.30
0.13
0.173
Exploitabilit
Exploitablity
Explobabitt
0.02
0.95
0.20
0.00
0.08
3:30
35
Iterations
kerations
Iterations
(a) ACSP20
(b) ACVRP20
(c) PG20
Figure I: Exploitability curve of CCDO-RL on three games of 20 nodes
6.2.2 AVERAGE REWARD AND GENERALIZABILITY OF COMBINATORIAL PLAYER
Evaluation. The learned policies are tested on 200 graphs, with 100 being randomly selected from the 10.000 training graphs (to show the average reward), and the other 100 being unseen graphs (to test policy generalization). We evaluate the performance of the protagonist with the adversary under three COPs. For each COP, the performance considered both on the 20-node and 50-node map.
Baselines. There are heuristic algorithms for each game instance (Heuristic in Table I and 2 and a single-player RL algorithm. For ACVRP, we adopt the Tabu Search algorithm (Tabu) aLd Li 2020) the heuristic algorithm, which is widely applied in the routing problem. For ACSP, the common benchmark local search algorithm, LS2 (Golden et al. 2012). is used. For PG, we choose the greedy algorithm the baseline. The "RL against Stoc" algorithm in Tables [[ and 2 is identi- cal to the protagonist model CCDO-RL but trained in environments with stochastic adversarial perturbations.

---

Published as a conference paper at ICLR 2025
Average Reward. As illustrated in Table I our algorithm achieves better average reward than baselines (10.08% improvement on average of all settings against two baselines), regardless of CO instance problem size, when confronting the adversary trained by CCDO-RL. In the setting of CSP-20 nodes, the average reward is improved by 46.98% compared to the heuristic and by 7. 7.14% compared with the RI against Stoc. For the 50-node setting, the improvements are 45.91 % and 5.28% respectively. Similarly, the improvements in contrast to Heuristic and RL against Stoc are as follows: 1.72% and 3.01% for CVRP-20 nodes, 0.75% and 4.46% for CVRP-50 nodes, 4.17% and 1.48% for PG-20 nodes, and 10.60% and 4.38% for PG-50 nodes.
Generalizability. From Table CCDO-RL continues to achieve a better average reward when fac- ing the adversary. demonstrating that the learned RL policies generalize well to unseen graphs. Even though the non-RL baselines do have access to the graph structures and other problem information of the unseen problem instances, CCDO-RI can obtain comparable performances without re-training on the new problem instances. The improvements versus Heuristic and RL against Stoc are 46.61% % and 7.02% for CSP-20 nodes, 42.24% and 3,94% for CSP-50 nodes, 1.12% and 1.56% for CVRP-20 nodes, 0.90% and 5.05% for CVRP-50 nodes, 5.35% and 2.40% for PG-20 nodes, and 12.17% and 10.33% for PG-50 nodes. Even when confronting the stochastic adversary, CCDO shows superior generalizability compared to two baselines across three COPs, with average improvements of 6.31 %, 3.42%, and 3.95% respectively. Detailed results are provided in Appendix (F (Tables 5 10
Remark 3 In CO problems (or more broadly, operations research and economics), it is known that achieving solution quality improvements against strong baselines (e.g., the RL methods trained with a stochastic adversary) is very challenging, and the margins are usually small (Kool et al. (018). sometimes even less than 1%. However, these "tiny" marginal improvements in profits keep small business owners in the real world alive. Last, the improvement depends a lot on the problem settings, and we show that sometimes the improvement can be much more significant.
Table 1: Average reward against CCDO-RLL a (on seen graphs)
ACSP Std)
ACVRP (Md)
PG (tda
method
20 nodes
50 nodes
20 nodes
50 nodes
20 nodes
50 nodes
Heuristic
6.13
7.55
7.65
1.73
4.53 1.03
RL against Stoc
0.50
0.65
1.15
2.71=0.90 1..90+1.63
4.80+2.118
CCDO-RL RL
0.24+
4.31
7.22+1221
13.28
2.75=0.87
1.91
Table 2: Generalizability against CCDO-RL's adversary (on unseen graphs)
ACSP Std)
ACVRP (Md)
PG Std)
method
20 nodes
50 nodes
20 nodes
50 nodes
20 nodes
50 nodes
Heuristic
1.33
7.60
1.30
2.43=0.98 1..27
4.19
RL against Stoc
3.36
0.57
1.37
2.50=0.95 1.58
4.26
CCDO-RL
3.31
4.39
1.25
13.15=1.59
4.70 2.56
For the average reward of ACSP and ACVRP, smaller is better while for that of PG larger is better.
7 CONCLUSION & LIMITATIONS
Drawing insights from existing literature and real- weal-world applications, we define a new class of games called ACCES games. We prove the existence of NE for ACCES games, providing a fundamental ba- sis for solution algorithms. Two NE solvers are introduced, namely CCDO and its practical version CCDO-RL, along with original theoretical analysis and ABRs' impact on convergence. Empirical results show that CCDO-RL can converge to approximate NE in small number of iterations. The protagonist policy obtained via CCDO-RL has better average rewards against adversarial perturba- tions and shows great generalizability on unseen graphs. A potential limitation of our method is scalability our experiments mainly focus on small COPs (20 and 50 nodes). While scalability is not the focus of this study, it does remain unexplored and deserves more investigation. Our work also opens up a new area of research centering on ACCES games, and more broadly asymmetric games such as the uniqueness of NE, well as more efficient and practical algorithms.
10

---

Published as a conference paper at ICLR 2025
8 ACKNOWLEDGMENTS
This research was supported by the National Science Foundation under IIS-234840S. The authors acknowledge William & Mary Research Computing for providing computational resources and/or technical support that have contributed to the results reported within this paper.
REFERENCES
Adam, L., Horčík, R., Kasl, T., and Kroupa, T. (2021). Double oracle algorithm for computing equilibria in continuous games. AAAI, pages 5070-5077.
Altman, E., Pourtallier, Jiménez, T., and Kameda, H. (2011). Symmetric games with networking applications. In NerGCooP, pages 1-5.
Amir, R., Jakubczyk, M., and Knauff, M. (2008). Symmetric versus asymmetric equilibria in sym- metric supermodular games. International Journal of Game Theory, 37:307-320.
An, K. (2020). Battery electric bus infrastructure planning under demand uncertainty. Transporta- fion Research Part C: Emerging Technologies, 111:572-587.
Balandat, M., Krichene, W., Tomlin, C., and Bayen, A. (2016). Minimizing regret reflexive banach spaces and nash equilibria continuous zero-sum games. NeurIPS, pages 154-162.
Balduzzi, D., Garnelo, M., Bachrach, Y., Czarnekki, W., Perolat, J., Jaderberg, M., and Graepel, (2019). Open-ended learning in symmetric zero-sum games. In ICML, pages 434-443.
Bello*, I., Pham*, H., Le, Q. V., Norouzi, M., and Bengio, (2017). Neural combinatorial opti-
mization with reinforcement learning. In ICLR Workshops.
Bengio, Y., Lodi, A., and Prouvost, A. (2020). Machine learning for combinatorial optimization: A methodological tour horizon. European Journal of Operational Research.
Berto, F., Hua, C., Park, J., Kim, M., Kim, H., Son, J., Kim, H., Kim, J., and Park, J. (2023). RL4CO:
unified reinforcement learning for combinatorial optimization library. In NeurIPS Workshop.
Bichler, M., Fichtl, M., Heidekrüger, S., Kohring, N., and Sutterer, P. (2021). Learning equilibria in
symmetric auction games using artificial neural networks. Nature machine intelligence, 688) 695.
Brown, G. W. (1951), Iterative solution of games by fictitious play. Act. Anal. Prod Allocation, 13(1):374.
Cai, Y., Candogan, O., Daskalakis, C., and Papadimitriou, C. (2016). Zero-sum polymatrix games: A generalization of minmax. Mathematics Operations Research, 41 41(2):648-66 655..
Carlsson, J., Ge, D.,. Subramaniam, A., Wu, A., and Ye, (2009). Solving min-max multi-depot vehicle routing problem. Lectures on global optimization, 55:31-46.
Chen, H., Qiu, W., Ou, H.-C., An, B., and Tambe, M. (2021). Contingency-awan influence maxi- mization: A reinforcement learning approach. In UAI, volume 161, pages 1535-1545.
Chen, T,, Yan, S., Guo, J., and Wu, W. (2023). Touplegdd: A fine-designed solution of influence maximization by deep reinforcement learning. IEEE Transactions on Computational Social Sys- tems, 11(2):2210-221 2221.
Chen, W., Lin, T., Tan, Z., Zhao, M., and Zhou, X. (2016). Robust influence maximization. In KDD, pages 795-804.
Cheng, S.FF. Reeves, D. M., Vorobeychik, Y., and Wellman, M. P. (2004). Notes on equilibria in symmetric games.
Cox, J. C., Ostrom, E., Sadiraj, V., and Walker, J. M. (2013). Provision versus appropriation in symmetric and asymmetric social dilemmas. Southern economic journal, 79(3):496-512
11

---

Published as a conference paper at ICLR 2025
Dai, H., Dai, B., and Song, L. (2016). Discriminative embeddings of latent variable models for structured data. In ICML, pages 2702-2711.
Deudon, M., Courntt, P., Lacoste, A., Adulyasak, Y., and Rousseau, L.-M. (2018). Learning heuris- tics for the tsp by policy gradient. In CPAIOR, pages 170-181.
Dinh, I. McAleer, S., Tian, Z.,, Perez-Nieves, N., Slumbers, O., Mguni, D. H., Wang. J., Bou Am- mar, H., and Yang, Y. (2022). Online double oracle. TMLR: Transactions on Machine Learning Research.
Dinh, T., Fukasawa, R., and Luedtke, (2018). Exact algorithms for the chance-constrained vehicle routing problem. Mathematical Programming, 172(1-2):100 105--188..
Fan, K. (1952). Fixed-point and minimax theorems in locally convex topological linear spaces. PNAS, 1212)12.
Feng, X., Yu, Z., Xiong, Y., and Chen, H. (2025). Sequential stochastic combinatorial optimization using hierarchal reinforcement learning. In ICLR.
Fey, M. (2012). Symmetric games with only asymmetric equilibria. Games and Economic Behavior, 75(1):424
Fiez, T., Sim, R., Skoulakis, S., Piliouras, G., and Ratliff, L. (2021). Online learning in periodic zero-sum games. In Neurips, volume 34, pages 10313-10325.
Florio, M., Gendreau, M., Hartl, R. F., Minner, S., and Vidal, T. (2023). Recent advances in ve- hicle routing with stochastic demands: Bayesian learning for correlated demands and elementary branch-price maanch-price-addccu European Journal of Operational Research, 306(3):0011-1093
Fu, Z.-H., Qiu, K.-B., and Zha, H. (2021). Generalize a small pre-trained model to arbitrarily large tsp instances. In AAAI, pages 7474-7482.
Gendreau, M., Jabali, O., and Rei, W. (2014). Chapter 8: Stochastic Vehicle Routing Problems, pages 213-239.
Ghannadpour, S. F. and Zandiyeh, F. (2020). A new game-theoretical multi-objective evolutionary approach for cash-in-trame transit vehicle routing problem with time windows real life case). Applied Soft Computing, 93:106378.
Ghory, I. (2004). Reinforcement learning in board games. Department of Computer Science, Uni- versity of Bristol, Tech. Rep, 105.
Glicksberg, I. L. (1952). A further generalization of the kakutani fixed theorem, with application to nash equilibrium points. Proceedings of the American Mathematical Society, 3(1::
Golden, B., Naji-Azimi, Z., Raghavan, S., Salari, M., and Toth, P. (2012). The generalized covering salesman problem. INFORMS Journal on Computing, 24(4):534-553.
Hammerstein, and Selten, R. (1994). Game theory and evolutionary biology. Handbook of game theory with economic applications, 2:929-993.
Hefti, A. (2017). Equilibria in symmetric games: Theory and applications. Theoretical Economics, 1793)097-
Hottung, A., Kwon, Y.-D., and Tiemney, K. (2022). Efficient active search for combinatorial opti- mization problems. In ICLR.
Hou, Q. Yang, J., Su, Y., Wang, X., and Deng. (2023). Generalize learned heuristics to solve large-scale vehicle routing problems in real-time. In ICLR.
Jafari, A., Greenwald, A., Gondek, D., and Ercal, G. (2001). On no-regret learning, fictitious play, and nash equilibrium. In ICML, pages 226-233.
Jain, M., Korzhyk, D., Vančk, O., Conitzer, V., Pěchouček, M., and Tambe, M. (2011). double
oracle algorithm for zero-sum security games graphs. In AAMAS, pages 327-334.
12

---

Published as a conference paper at ICLR 2025
Joshi, C. K., Laurent, T., and Bresson, X. (2019). An efficient graph convolutional network tech- nique for the travelling salesman problem. arXiv preprint arXiv:1906.01227.
Kakkar, R., Agrawal, S., Gupta, R., and Tanwar, S. (2022). Blockchain and zero-sum game-based dynamic pricing scheme for electric vehicle charging. In INFOCOM Workshops, pages 1-6.
Kalimeris, D., Kaplun, G., and Singer, Y. (2019). Robust influence maximization for hyperparamet- ric models. In ICML, pages 3192-3200. PMLR.
Khalil, E., Dai, H.. Zhang, Y., Dilkina, B., and Song, L. (2017). Leamning combinatorial optimizziioniiiiiiiiiiii algorithms over graphs. NeurIPS, pages 6351-6361.
Kipf, N. and Welling, M. (2016). Semi-supervised classification with graph convolutional net- works. arXiv preprini arXiv: 1609.02907.
Knight, V. and Campbell, J. (2018). Nashpy: A python library for the computation of nash equilibria. Journal of Open Source Software, 3(30):904.
Kool, W., van Hoof, H., and Welling, M. (2018). Attention, learn to solve routing problems! In ICLR.
Kwon, Y.-D., Choo, J., Kim, B., Yoon, I., Gwon, Y., and Min, S. (2020). Pomo: Policy optimization with multiple optima for reinforcement learning. In NeurIPS, pages 21 21188-21198.
Lanctot, M., Zambaldi, V., Gruslys, A., Lazaridou, A., Tuyls, K., Pérolat, J., Silver, D., and Graepel, T. (2017). A unified game-theoreti, approach to multiagent reinforcement learning. In NeurIPS, pages 4193-4206.
Lauri, J., Dutta, S., Grassia, M., and Ajwani, D. (2023). Learning fine-grained search space pruning and heuristics for combinatorial optimization. Journal of Heuristics, 29(2)313-347.
Li, G. and Li, J. (2020). An improved tabu search algorithm for the stochastic vehicle routing problem with soft time windows. IEEE Access, 8:158115-158122
Li, K., Zhang, T., Wang, R., Wang, Y., Han, Y., and Wang. L. (2021). Deep reinforcement learning for combinatorial optimization: Covering salesman problems. IEEE transactions on cybernetics, 52(12):1142211155.
Lipton, R. J. and Young. N. E. (1994). Simple strategies for large zero-sum games with applications to complexity theory. In STOC, pages 734-740.
Liu, X., Jia, H., Wen, Y., Hu, Y., Chen, Y., Fan, C., Hu, Z., and Yang, Y. (2021). Towards unifying behavioral and response diversity for open-ended learning in zero-sum games. NeurlPS, pages 941-952.
Liu, Z., Yu, J., and Li. J. (2007). Properties and equilibria of mixed strategies in continuous games. Journal of Capital Normal University (Natural Science Edition), 28(2):13-18.
Manchanda, S., Mittal, A., Dhawan, A., Medya, S., Ranu, S., and Singh, A. (2019). Learning heuristics over large graphs via deep reinforcement learning. arXiv preprint arXiv: TrXxv:9903.0332.
Manchanda, S., Mittal, A., Dhawan, A., Medya, S., Ranu, S., and Singh, A. (2020). Geomb: Leam- ing budget-conee condtrre-ontttaieedd combinatorial algorithms over billion-sized graphs. In NeurIPS, pages 20001-20011.
McAleer, S., Lanier, B., Fox, R., and Baldi, P. (2020). Pipeline psro: A scalable approach for finding approximate nash equilibria in large games. In NeurlPS, pages 20238-20245
McAleer. S., Lanier, J. B., Wang, K. A., Baldi, P., and Fox, R. (2021). Xdo: A double oracle algorithm for extensive-form games. In NeurlPS, pages 23128-23139.
McMahan, H. B., Gordon, G. J., and Blum, A. (2003). Planning in the presence of cost functions controlled by an adversary. In ICML, pages 536-543.
Myerson, R. B. (1991). Game theory- analysis of conflict.
13

---

Published as a conference paper at ICLR 2025
Narasimha, K. V., Kivelevitch, E., Sharma, B., and Kumar, M. (2013). An ant colony optimization technique for solving min max multi- vehicle routing problem. Swarm and Evolutionary Compulation, 13:63-73.
Nash, et al. (1950). Non-cooperative games.
Nazari, M., Oroojlooy. A., Takáč, M., and Snyder, L.. (2018). Reinforcement learning for solving the vehicle routing problem. In NeurIPS, pages 9861-9871.
Ou, H.-C., Chen, H., Jabbari, S., and Tambe, M. (2021). Active screening for recurrent diseases: reinforcement learning approach. In AAMAS, page 992-1000.
Peck, Shell, K., and Spear. S. (1992). The market game: existence and structure of equilibrium. Journal of Mathematical Economics, 21(3):271-29)
Perez-Nieves, N., Yang, Y., Slumbers, O., Mguni, D. H., Wen, Y., and Wang. J. (2021). Modelling behavioural diversity for learning in open-ended games. In ICMI, pages 8514-8524.
Rahmattalabi, A., Vayanos, P., Fulginiti, A., Rice, E., Wilder, B., Yadav, A., and Tambe, M. (2019). Exploring algorithmic fairness in robust graph covering problems. In NeurlPS, pages 15776- 15787.
Reny, P. J. (2005). Non-cooperative games: Equilibrium existence. The New Palgrave Dictionary of Economics, 116.
Roughgarden, T. (2010). Algorithmic game theory. Communications the ACM, 53(7):78-88 -6.
Stella, L. and Bauso, D. (2018). Bio-inspired evolutionary game dynamics in symmetric and asym- metric models. IEEE Control Systems Letters, 2(3):405 410.
Tang, X., McAleer, S. M., Yang. Y., et al. (2023). Regret-minimizing double oracle for extensive- form games. In ICML, pages 33599-33615.
Tirkolaee, E. B., Mahdavi, I., Esfahani, M. M. S., and Weber, G.-W. (2020). A robust green location- allocation-inventory problem to design an urban waste management system under uncertainty. Waste Management, 102:340-3500 3500.
Tuyls, K., Perolat, J., Lanctot, M., Leibo, J. Z.,, and Graepel, T. (2018a). generalised method for empirical game theoretic analysis. In AAMAS, pages 77-85.
Tuyls, K., Pérolat, J., Lanctot, M., Ostrovski, G., Savani, R., Leibo, Z.,, Ord, T., Graepel, T., and Legg, S. (2018h) 8b). Symmetric decomposition asymmetric games. Scientific reports, 8(1):1015.
Von Neumann, J. and Morgenstern, O. (1947). Theory of games and economic behavior, 2nd rev.
Washburn, A. R. et al. (2014). Two-person zero-sum games.
Waugh, K. and Bagnell, J. A. (2015). A unified view of large-scale zero-sum equilibrium computa- tion. In AAA/ Workshops.
Wilder, B. (2018). Equilibrium computation and robust optimization zero sum games with sub- modular structure. In AAAI, volume 32.
Xu, H., Fang, F., Jiang, A., Conitzer, V., Dughmi, S., and Tambe, M. (2014). Solving zero-sum security games in discretized spatio-temporal domains. In AAAI, pages 1500-1506.
Xu, I.., Perrault, A., Fang, F., Chen, H., and Tambe, M. (2021). Robust reinforecen learning under minimax regret for green security. In UAI, pages 257-267.
Yao, J., Liu, W., Fu, H., Yang, Y., McAleer, S., Fu, Q., and Yang, W. (2024). Policy space diversity for non-transitive games. In NeurIPS, pages 67771-67793.
Zhou, M., Chen, J., Wen, Y., Zhang, W., Yang. Y., Yu, Y., and Wang, J. (2023). Efficient policy space response oracles. arXiv preprint 2202.030...
14

---

Published as a conference paper at ICLR 2025
Zhu, Y. and Zhao, D. (2020). Online minimax q network learning for two-player zero-sum markov games. IEEE Transactions on Neural Networks and Learning Systems, 33(3):1228-122 1241.
Zinkevich, M., Johanson, M., Bowling, M., and Piccione, C. (2007). Regret minimization in games with incomplete information. In NeurIPS, pages 1729-1736.
15

---

Published as a conference paper at ICLR 2025
A PROOFS AND ANALYSIS IN SECTION 4
A.1 PROOFS IN SECTION
Definition 3 [Weakly Convergence.] Suppose S is a space, probability measures Pn weakly con- verges to P, wrillen by Pn = P. for every bounded continuous function f.
lim [ fdPa - S fdP. 12000
any sequence in a set has a weakly convergent subsequence, the set weakly sequentially com- pact.
Lemma S uncorrelated general metric spaces and P', pM the probability measure on S' S" respectively. Define TT d S'' x S" as the product space of S' and S" if is separable, then Pk, Pd p' x P" if and only if Pt P' and PM => P". ((Myerson 1991). Theorem 2.8)
Proposition 1 [Weakly Sequential Compactness.] Suppose the ACCES game is g = (X,Y, u). where X is finite, Y is a nonempty compact metric space, and the utility function is continuous on Y fixing x E X. Then the joint mixed strategy space A Ax x Dy is weakly sequentially compact.
Firstly, considering the condition in Lemmall we need to prove the product space X x Y separable. The X is separable obviously, based on its finiteness and discreteness. And every compact metric space has countable base, so separable. Hence the set Y is separable. Then the product space
Proof.
Y is separable too.
The next step is to prove weakly sequential compactness of set 4x and Dy. Due to the finiteness of X, 4x is a nonempty compact convex set on IR X where any element E 4x can be represented p [p(=1). .... p( x x)) satisfying Σ p(x,) = P; 0. Since strong convergence is equiv- alent to weak convergence in the finite- diteedimmnsional normed space, the compact set A is weakly sequentially compact too.
Besides, according to the properties of mixed strategies in continuous games mentioned in Liu et al (000)). Ay is sequentially compact and closed, thus compact. Based its compactness, proposi- tion 1 Adam et al. (202l) guarantees that Z is weakly sequentially compact.
Therefore, due Lemma 1
can get A is weakly sequentially compact.
Proposition 2 [Continuity Expected Utility Function.] The expected utility function Upp 9) + EzEx Syey p(z)u(z, d) is continuous on the joint mixed strategy space 4, Vp e 4x, 9 By.
Proof.
First we denote the related distance mapping P1 and P2 on Ax and By respectively.
(p.pp') = Σ pp(x) p'(x) Vp,p' Ax.
xEX
p2(9.9') sup (g(v) o (v)) Vq. of Av.
yeY
16

---

Published as a conference paper at ICLR 2025
Afterwards, prove the continuousness of U on A. V(po.
qn) E A.p E (((p))00).0) n A,
which means d( q), (Po, (po) + VPi(p. Po) + p (gl q0)
S yEY
[U(p,] 9) - Upo. qo)1 = Σ p(x)
Σ po(x)
u(a, y)dgol
(1)
HEY
xe
Σ
(2)
JEY
Σ
u(x,))((((r)) po(x))dg + po(x))dg - dqo)]]
xe DEY
u(x, (p(z))((z) po(x))dgl + Σ xEX yEY
u(z,)) dq)l
xEX yEY
(4)
Because u(x,)) y) is continuous on Y when fixing x e X, X is finite, and Y is nonempty compact metric space, u( y) is bounded.
Assume |u(r, v)1 & M, d((p 9), (P)0 + Vo(lp.P)) Po) p3(9. 90) Σ (p(x) - po
5 2
get that
Σ xEX YEY
u(z,,)(p(x) -oo())ddg &
u(I, yddg
(5)
yEY
xE
< M
Σ (p(x)) - po(2))) < Mp
(6)
xe
Σ u(a,y)po())(da dg)l $ Σ Po(x) f Jver y) dq)l
xEX JeY
po(t)) S u(I, - dg)l
Σ xeX
(8)
WEY
< sup [ u(x,
d4)1
(9)
zeX yee
< p22
(10)
Then we can get that
(p..)) - Upp. < Mp1 (p. po) + Σ po(x)) [ u(I,z)dg - {
u(x, v)dqol
(11)
Jyer
xeX
< M6 + M6
2M6 e.
(12)
When Pn p and 9n g. the above inequality still holds. Pn. p P1 PP because Strong convergence is equivalent to weak convergence in finite-dimension metric spaces. Addition- ally, lyyer u(x, y) fyev u(x, y),,))dg.l 0 when fixing æ. From inequality (11), we infer
S
u(x,y))d - S
g) - U (pa,ga)) & Mpi(p.Pn) Σ pn(x)) xe
yyev u(x,))dd,
(13)
yeY
u(I, v)dg [ wwey
sup & Mpr(p.Pa)
u(x, y)dqal
(14)
mex
yeY
-Mp(PPPPa +
u(a y)d
u(i, V)dgal O,
(15)
ygEY
JUEY
where à = argmazzzeee byer u(a, y)dg -g)g---- -Sye ult y) dgdll
17

---

Published as a conference paper at ICLR 2025
Proposition 3 [Approximate NE of ACCES.] g' (X, is a-approximation of g = (X,Y, where 9 is an ACCES game. (p*.q" 94") is an e-equilibrium of g", then (p* 94 is an (E + 20:)- equilibrium of g.
Proof.
Define (p, Evex Jpey p(z)ū(r y)dq. for v(p: q) E A we can get
Σ p(z)(u(x,)) - & Σ xeX WEY
f
p(z)dq
xeX UEEY
Next for any Q Dr.
[U(2", -/" :4) (U('"'/"))))) -'0- "0"0(""""")"""" +0"++0("* -,"))00"""")000 -00 .4) Up'* (p))) 2a+e.
Similarly, it can be proved that (U(x" "0** - < 2a + e, Vp 4x.
Proposition 4 [Essentially Finite of ACCES.) For ACCES g, Va 0, there exists essentially finite strategic game & <X,Y, Y, ú). s.t. I is a-approximation of g.
Proof. Due to that Ś is a-approximation of G, then for any z X, E Y, |u(z, v) -(x, v)1 & a. On account that is continuous on Y and Y a nonempty compact metric space, so u is uniformly continuous on Y. According to the uniform continuousness of function Va 0, 0,3e(z) > O. when |y - v'1 exx), (u( y) u(x, v')l & a. Define = min E(x). is a nonempty compact metric space, hence can be covered by finite open balls Oy(1,, c), ie. Y = U, (,,,,)))
Then for Vj. Vy e Oy(,,, x) X, denote that ū(x.y) u(x U5). Hence, Ya X |u(z, y) ú(x, y)1 & a.
Theorem [Existence of NEJ 9 = (X,Y, where X is finite space, Y is nonempty compact metric space, X x R is continuous utility function on Y when fixing e X. Game G has a mixed strategy Nash equilibrium.
Proof. Suppose sequence }ax} converges to zero, i.e. 0₂2 - O. For any On, there exists an essentially finite game Gn, which is an approxxxxmttio of 9 (Proposition Due to Nash's 's theorem, mixed equilibrium (Pn. (n) of Gn, exists. So (Pn, 9n) is 20,, -qquilibiii of G (Proposition B). By Proposition 1 (pn,q.) has a convergent subsequence. For brevity, this convergent subsequence we can know that
denoted by ((Pa, (,)), which converges to (p*, ,q*). Based on Proposition 5 (n* .4*) ) is mixed equilibrium of
A.2 ANALYSIS ON THE EXISTENCE OF NE IN N-PLAYER ACCES GAMES
Our propositions and Theorem 2 be extended to the N-player ACCES games naturally. The key point of the existence of NE to N-player ACCES games is two fundamental properties we propose ACCES games, weakly sequential compactness of the mixed strategy space and continuity of the expected utility function (Propositions and 2), and the approximation idea by finite games, We introduce these as follows.
Two Properties: In Proposition I, we transform the weakly sequential compactness of the joint mixed strategy space into the separability and weakly sequential compactness of each single player by Lemma In Proposition 2, we scale the distance between two mixed strategies to the sum of distances between a single player's mixed strategies while fixing other players, According to the proof of these two propositions, they are all independent of the number of players.
The Approximation idea by finite games: The main idea is to approximate the infinite continuous strategy space by finite grids by definitions of approximate games and essen- tially finite games. The idea and definitions are not limited to the two-player setting.
18

---

Published as a conference paper at ICLR 2025
B PROOFS IN SECTION 5
Theorem Given a two-player ACCESS game 9 = (X, SXXYYu) where X is finite, Y is a nonempty compact set, and the utility function is continuous in Y when fixing the strategy in X, have
1. When = O, every weakly convergent subsequence in the subgame equilibrium pair sequence Upg } converges the equilibrium of the whole game, possibly in an infinite number of itera- tions.
When Algorithm converges to an e- -equlibrrim in a finite number of epochs.
Proof. At every epoch denote the protagonist policy Ik-1 e and adversary policy output 11+1 Y as best responses to mixed equilibrium (p gx) in the kin subgame (X&, Yı, U), i.e.
2k+1 argmax U (z, 9x), Mk++1 = argmin U (pk y):
noting that all maximizers and minimizers exist due to the finiteness of X, compactness of Y, and continuity of when fixing variable æ.
First, prove the efficiency of the stopping criterion, i.e. output (p ox, satisfying this criterion, must be mixed equilibrium of game 9. The stopping criterion
U(I++1, g
UP vk+11) c,
implies that
Ulp x < (1K+11 < Upk 1/++1) +e
(16)
min Up ; y) +c=
min Upt 9) +
yeY
reAy
which means that Vy E Lv, U Ups, qk) & Upk. q) +
Similarly, can get that
U U th) > Upp Mk+11 > ( 1x) -
(17)
max (x, 9% - max Up, 9:) - 9 peAx
x
that is Vp E 4x U. 9x) > u(p, 9x c. Combined 166 and meeting the condition, is e-mixed equilibrium.
mixed equilibrium (vă (x).
Next, we need to prove its convergence of mixed Nash equilibrium, in other words, this algorithm 2 can reach the terminal condition.
When = O, due to Proposition [ every sequence in 4 xxxy has its own weakly convergent subse- quence. For the sequence {(p xt whose element (pî o is the mixed equilibrium of the kih subgame, there exists a weakly convergent subsequence, for simplicity denoted the same indices, i.e. {(p.. ) converges (p".. .²*).
Due to that (pt. gt) is an equilibrium of the subgame (Kx. Yr, U). so Vk, Vy E Yk. we can know that
U'Pi g & (p).
Take the limit on both sides of this inequality, based on the continuousness of U on Axxy, we can get that
U(p q²) & Up" v). Vy c((Yk)).
(18)
Because Y is compact, for sequence {yk} there exists cl(UY)) s.t. yk ÿ.k cD.
Besides, we can get that
Upt v1+1) & Ulp v), Vy YY,
(19)
based the definition of best response, which infer
U(p",q") U U(p"v))Vyee.
(20)
19

---

Published as a conference paper at ICLR 2025
in which the left-hand inequality above follows inequality (88) and the right-hand gets by taking limits on inequality (I9).
For the reason that the strategy space X is finite and the number of iterations is infinite, in the weakly convergent subsequence,
Jku, 8.I.V ko, (ph,, )
max zeX;
(1, 1
(21)
(z v U U1
zeX
which means that T241 E Xk, vk ko- Therefore get that, Yor X,
Urr xx) < (xx++1, x Upp 9)), 4k ko, U(x r²) < Upp",9")
(22)
So we have proven that
U(x,9") Up .4") & U(p v). Vr X,yye
Due equivalent condition to NE, that is(p" q*) is equilibrium if and only if it follows 4²r & Upp & Up* v), Vx N,yeY,
(23)
we can says that (p*,9* .q*) is an equilibrium of G. If 0, 20 imply that
Up vk+1) (p 9h) Upp", < [(pp",9")
(24)
Combined with inequality (20). we know that
(pi Vk+1) - U(p", 0) = Upp ,
(25)
Due to the fact 21 after kn iterations, the strategy space of X will not be expanded. So we can get
lim U U(I++1, ( = lim Upp 9h) = Upp"."")
(26)
k0000
k000
Therefore, utilizing 25 and (6).
U (1 x U Upt Mk+1) - 0, - 80.
(27)
In other words, if >
0, this iterated process must be terminated within limited rounds and the output equilibrium with finite supports.
20

---

Published as a conference paper at ICLR 2025
Theorem 3 Given G = (X, u). where X is finite, Y is nonempty compact set, and the utility function u is continuous in Y when fixing the strategy in X, with 61 best response oracle for Player 1 in X and e2 best response oracle for Player 2 in Y, have
When > O, for any form of approximate best-response oracles, CCDOA and CCDO-RL can converge to a finitely supported (c 6 + (2) equilibrium in a finite number iterations.
When c = 0, if the approximate response oracle for Player 2 has a uniform lower bound every mixed strategy in Ax i.e.
Vp E Ax, R6y, (p. BRF(P) 3 min Upp y) + + yEY
(28)
then CCDOA and CCDO-RL must converge to an 61 + e2)- equilibrium in a finite iterations.
3. When e 0, if CCDOA and CCDO-RL produce infinite iterations, every weakly convergent subsequence converges to an E1- equilibrium.
Proof. (1) Due that
U( 1. - UP VK+z) & U(T++1, UU Vk+1),
combined with the Algorithm can stop a finite number of iterations if e >
(2) Similarly with Theorem 2 firstly we prove the output must be (e 61 + 62) equilibrium if satisfying the stopping termination. Based on the definition of c- best response, we can know that
Vq Ar, U (g), >
max Uzz q) E1,
=
(29)
Vp Ax (p, BR3 (p)) yEY
min
(p, y) + 62.
For simplicity, suppose B (gx)
k+1 BRg (pt)
lx41
ca
for subgame equilibrium (P 9%)
The iteration process stops means that U g ) - U' Me+1) < So we can get that
e2
U Upp t & max (I, t < (2 9 +
xx
Upt / +c+
(30)
min Upn +c+
weY
< U + +
Similarly, we can prove the parallel results on X.
U Upt
min U Upt v) > U Upp; 1k+11 E2
yeY
3 U(iii 1 (h) - 6
(31)
e max U (z, 9k - -6- - 62
weX
U(r, vtt)
62, Vr X.
So combined with 30 and 31..
Vr X, V, - u (pt x
Up y) E,
in which È = c E 62. Hence (pt gt) ) is the E- equilibrium of game G. If the e2- best response has lower bound, which means that Vi.
U Uptx 1)+1) 1) +ey & Upt si < Up d
(32)
assume with + f 30, if iterating infinitely, take limits on both sides, based on 25 we can get
Upp + U ey < UU(p", (o) & Up" xt))
(33)
Obviously, it's contradiction. Hence this iterated process must terminate in finite rounds.
(3) When e = 0, considering that the algorithm 3 produces an infinite number of iterations, the stop- ping termination always stands up, i.e. Vk, (1 U (pt vf2.)) 0. Without consideration
21

---

Published as a conference paper at ICLR 2025
of the effect of approximate best responses' properties on the judgment of termination condition, resembling the proof of theorem 3, based on (20) and we can get
U 4 UpÉ 1 & Up yk+1 62 & +2
(34)
(x, gx) - 6 & max (z. 9 -1 1 & 1 g Up ot) Ko: V
xeX
hence taking limits on both sides
U(z, e & Upp", . .²t) Up"" .) + 62 Vo X,y
(35)
according rium.
23
every weakly convergent subsequence converges to a max(é1, e2)- equilib-
As the example taken in 28 not all forms of approximate best response breach the termination condition in the whole iteration process.
Because of the fact that the strategy space X is finite, combined with can get that
Uph xx) U Upx 11+1) > 0, >> Ko-
(36)
- (pk: vk+11 & Up vk41) < U (pk 9%
Integrated with (21,, easily we can get
U vkt1) - U(p 11 = Up , Upp* (p)))))
(37)
Define 4V & U Up v( U Up M1+1)). From 337 and (11. the following result can be derived:
- - 0, 20.
(38)
According to (6),
U'p lt) & Upk. v = Upp vk+1) + A% < UpE v) + +
(39)
Take limits on both sides,
U(p". < Upp*.v) v)
(40)
Combined with 23 can get that in infinite iterations, every weakly convergent subsequence will converge to E1- equilibriuu
Theorem the combinatorial optimization player employs the state-of-the-ar approximate algo- rithm, whose computational complexity is polynomial with respect the scale of the problem noted as f', m, Kog the continuous adversarial player adopts LinUCB with d-dimension input, then the computational complexity of the algorithm is Opp(f(n, m. log Td)) if O.
Proof. Providing that there exists a representative network that can compress the CO problem into d-dimension vector with full information, then the overall computational complexity is
Of, m, logk)) p O(Td)) = Opp(f m, logK) ) Tdd)):
in which T is the number of iterations in LinUCB, K is the largest value of the single item in the CO problem.
Note that among common algorithms for solving combinatorial optimization problems-namety approximate algorithms, heuristic algorithms, and reinforcement learning (RI.) methods-only ap- proximate algorithms have complexity analysis and performance guarantee. For heuristics and RL methods, complexity analysis remains open challenge. Hence, choose approximate algo- rithms as the approximate best response. Additionally, considering the continuous strategy space of the continuous player, LinUCB is an appropriate algorithm for computing its best response.
22

---

Published as a conference paper at ICLR 2025
C
PSEUDOCODE OF ALGORITHMS
The pseudocode for CCDO and CCDOA is presented in Algorithms 2a and respectively.
Algorithm 2 Combinatorial-CCmminnnn Double Oracle Algorithm
Input: Game (X, u.) O.
Output: (p%. -0%)))
Initialize strategy set X1, Y1.
2: repeat
3: Solve the mixed equilibrium (pt gi) in the subgame (Xx, Yx).
4: Find the best response 2x+1, y 26+1 BR (4t), Me+1 (R2(
5: Xk+1 = X u {xx+1): ). Yx+1 = Yi u (16+1)-
6: until U[ xx) U UpZ vk+1) c
Algorithm 3 Combinatorial- Double Oracle Approximate Algorithm
Input: Game G = (X, Y, u), c > O.
Output: of.
1: Initialize strategy set I1, I12.0-
2: repeat
3: Solve the mixed equilibrium (pā g in the subgame (X,, V&).
4: Find the E1 best response, 62- best response x Mei1i
Ø6+1 IBRT (gt) Mk+11 |BR5 (pt).
5:
X X U (0++1) 1. YL.1 YE (VE+1).
6:
U k+ xx) & Up 4% then
7:
c1 = x random in p X Xx-
8:
else
9:
X = Xx U 1-
10:
end if
11:
if U v ) 2 Upp xx then
12:
yhi = y random g Yk+1 Yk.
13:
else
14:
Yk+1 Yg u (.
end if
16:
until U(a (. UVPi Ee
23

---

Published as a conference paper at ICLR 2025
D EXPERIMENTS PARAMETERS AND SETTINGS
D.1 PARAMETERS OF CCDO-RL
Table 3: Parameters of CCDO-RL
parameter
ACVRP20
ACVRP50
ACSP20
ACSP50
PG20
PG50
Iteration
26
35
24
35
13
12
Batchsize (prog/adv)
512
512
512
512
1024
1024
Prog training epoch
10
25
10
20
150
150
Prog training decoder
sampling greedy
sampling greedy
sampling greedy
sampling greedy
sampling greedy
hop_p-sampling
Prog eval/test decoder
beam-search
Learning rate (prog)
le-4
le-4
le-4
le-4
2e-4
2.5e-4
Adv BR training epoch
5
20
20
20
20
50
Learning rate (adv)
le-4
5e-5
5e-5
5e-5
5e-5
5e-5
Clip range (PPO in adv)
0.2
0.2
0.2
0.2
0.2
0.2
Value Func (PPO)
0.5
0.5
0.5
0.5
0.5
0.5
Entropy (PPO)
0.01
0.0
0.0
0.0
0.0
0.0
Max gradient (PPO)
0.5
0.5
0.5
0.5
0.5
0.5
D.2 PROBLEM SETTING
D.2.1 ACSP
The adversarial covering salesman problem (ACSP) variant of the traveling salesman problem (TSP) with adversaries. The biggest difference is that each city i has one coverage radius r;- If some unvisited cities covered by visited cities, then these unvisited seen as being visited in the TSP. Hence the salesman in the ACSP aims to find the shortest path such that all cities have been visited or covered. However, due some external factors like transportation situations, the coverage radius may be influenced. Similar to the influence model in 7.. the real coverage radius is
Di,m nim
(41)
where di.m is the myh element of oi, i.c the transportation vector at the city correlated with the city's location, i.e. o loc, where & one constant K 2 matrix. and you the component of the environmental parameter matrix y controlled by the adversary. Hence the objective function like the ACVRP,
min max length(x), xxXesp ye [0.1])
(42)
where length is the summary distance from the start to end (two cities can be different), and the path x should visit or cover all cities.
D.2.2 ACVRP
The adversarial capacitated vehicle routing problem (ACVRP) is that there is one depot and one vehicle with constrained good capacity which starts and ends at the depot where the vehicle can supplement goods. The objective of this vehicle is to find the shortest path while satisfying all demands of customers the map. Each customer owns its two-dimension position (I, y) and an estimated demand d, According the influence model the real demand d; is set as follows:
K
d, = d +
Σ m_x=
Wi..Win
(43)
in which Wi.m the My element of W;. ie. the weather vector at the customer point i, and Omn is the component of the environmental parameter matrix controlled by the adversary. In setting,
24

---

Published as a conference paper at ICLR 2025
assume that the weather condition is related to the customer's location, i.e. wi = +.J-loo loo; where w one constant x 2 matrix. Before the vehicle chooses the customer to deliver goods, it can only know the estimated demand d. When arriving at the chosen customer, the vehicle knows the real demand of this customer. should be noted that goods can't 't be split up. In other words, the remaining capacity of goods can't satisfy the real demand of the chosen customer, the vehicle should come there again until its current capacity meets the real demand de.
Hence the objective function of the vehicle is to minimize the maximal path x under the changeable environment parameters y E [0, 1]9, meeting all the demands of customers
min max length(x). xEX yE[U,1]
(44)
where length is the summary distance from the start to end, adopting the Euclidean distance.
D.2.3 PG
About the PG, we set as the classical security patrolling game with two players: one defender and one attacker. There are N targets protect, each one has an individual prize v; and estimated attack probability Pa defined by objective factors. The defender tries to find path to maximize the cumulative prize attained from some targets prevented from attacks successfully under the total distance constraint. For the attacker, will decide the real attack probability of each target based on the estimated probability P: and its objective is to reduce the cost of being caught, equivalent to reducing the total patrolling revenue of the defender. Identically, the attack probability on each target also follows the influence model in 7
K Σ m,,=1
Do
SimSiinnmmn
(45)
where &a is the attacker's preference vector to the target i, to keep consistent with the two settings before, still the preference vector related to the location, i.e. & 3 loc; where & is one constant K x 2 matrix. The objective function of this security game is
max min xox ye [0.1]
Σ Pau.nn
(46)
where II is the set of patrolled targets on the path æ.
D.3 ATTENTION MODEL & HYPERPARAMETERS
INSTANCE GENERATION
For ACVRP and ACSP, we use the default data generated from RL4CO (Berto et al. 2023). For PG, we use the instances generated from a generator provided in the AI for TSP competition hosted at ICCAI2
MODEL ARCHITECTURE
For the protagonist of three COPs, the REINFORCE algorithm with the Attention network used by possessing the graph information in RI4CO. About decoders, we use the static embedding for ACVRP and PG provided in RL4CO (Berto al., 2023). and a dynamic embedding for ACSP from (Li et al. 1).
About the encoder, three instances all adopt the attention network with 8 heads while the number of the network layer is 3 for ACSP and ACVRP, and 5 for PG. Different COPs have their own state and context of the environment, input details for three COPs are follows:
ACVRP: The environment context is each customer's location, demand, and weather vec- tor. The state at time slot is the current location and remaining capacity of the vehicle.
25

---

Published as a conference paper at ICLR 2025
ACSP:
The environment context is each city's location, estimated coverage, and transporta- tion vector. The state at time slot t is the current location( the chosen node to visit at the last time slot) and the start point.
PG: The environment context is each target's location, estimated attack probability, and prize. The state at time slot is the start point and the current location of the defender.
E DISCUSSION ON SCALABILITY AND POTENTIAL OPTIMIZATION OF CCDO-RL
E. SCALABILITY ANALYSIS OF CCDO-RL
In CCDO-RL, three components need to be trained or computed:
1. The combinatorial player's policy. This player solves a combinatorial caapbbinatoralloppmiiiiiiio problem (COPs) under specific strategy of the adversary.
2. The continuous player (as the adversary) with an infinite continuous strategy space.
3. The computation of Mixed Nash Equilibria (NE) in the subgame.
Next, will analyze the computation time for each component individually, from both theoretical and experimental perspectives. For the experimental part, we will use the 50-node Patrolling Game (PG) scenario, which the most challenging problem instance in our experiments, as an example.
1. The combinatorial player is trained using Graph Neural Networks (GNN) and REIN- FORCE to find feasible and optimal solutions for NP-complete COPs. This complexity requires reinforcement learning invest more time and data for effective model training. In the experiment, training a stable and high-performing combinatorial model takes 26 minutes (10000 data, 1024 batch size, 150 epochs) with the continuous player fixed.
2. The continuous player is trained by PPO to tackle one-step problem with continuous objective function building on strategies of the combinatorial player. It still utilizes GNN to understand graph structure. One action per episode reduces training times compared the combinatorial player while achieving similar approximate error levels. In our experiments, training high-performing model takes only and 50 epochs), less than one-fifth of the time required for the combinatorial player.
minutes (10000 data, 1024 batch size,
3. For the NE solution, the mixed equilibria a zero-sum game can be solved by the lin- ear programming method which has polynomial complexity in the size of the game tree. From the perspective of theoretical complexity and experiment implementation, the com- putational time is negligible (less than 2s).
From the statement above, we can conclude that more than five-sixths of the computation time is spent training the model or strategy of the combinatorial player. Therefore, crucial aspect of addressing the scalability issue is to enhance the speed of solving the Combinatorial Optimization Problems (COPs) using Reinforcement Learning (RL).
E.2 POTENTIAL OPTIMIZATION OF SCALABILITY
In this subsection, briefly discuss two main aspects as potential ways of improvement.
COPs Simplification Method
The pruning method: this one was introduced in the original scale of COPs to reduce number of possibly useful actions. In this way, the computational burden will be decreased (Manchanda et al. 2019: Lauri et al. 2023).
2. Broken down into subproblems: in some concrete COPs like TSP (Fu et all 2021). and VRP (Hou et al., (203),, the originally large-scale problem can be broken down into smaller problems to solve, thereby reducing the solution difficulty.
RL algorithms
26

---

Published as a conference paper at ICLR 2025
1. Learning Time Reduction: increase the sampling data quality by attaining good- performance data from pre-trained RL models or heuristic algorithms on COPs (seemingly like the model-based RI.).
2. NN Model Adjustment: most constructive neural network fitting combinatorial optimiza- tion can not solve problems with large-scale instance sizes. One feasible way to design NN model with strong scalability which means that the trained model on small-scale problem instances can used on large-scale ones, such as in influence maximization CCenn et al. (203)).
3. Distributed training: reduces the time required for training by splitting the computational workload across multiple devices.
E.3 EXPERIMENT RESULTS OF CCDO-RL'S SCALABILITY
We test the CCDO-RL model (trained 50-node graphs) larger CSP and PG scenarios. On unseen 100-node and 200-node graphs (100 of each type), CCDO-RL. outperformed other baselines while requiring significantly less test time compared the heuristic algorithm (especially in CSP),
as demonstrated in Tables 4
Table 4: Scalability results ACSP and PG (smaller is better in ACSP, larger is better in PG)
CSP
PG
method
100 nodes
200 nodes
100 nodes
200 nodes
Heuristic
7.38 (Sh 46mins)
6.95 (7h 16mins)
7.71 (53s)
11.01 (120s)
RL against Stoc
7.34
9.86
7.83
9.24
CCDO-RL
4.61
4.89
8.42
11.07
27

---

Published as a conference paper at ICLR 2025
F ADDITIONAL EXPERIMENTAL RESULTS
F.1 CONVERGENCE TO NE IN 50-NODE GRAPHS
All experiments on three COPs are implemented in Python and conducted on two machines. One is NVIDIA GeForce RTX 4090 GPU and Intel 24GB 24-Core 19- 13900K The other is NVIDIA V100 GPU and Inter 256 GB 32-Core Xeon E5-2683 v4.
Illustrated by Fig. 2 we observe that CCDO-RL also converges close to the real NE in 35 iterations for ACSP and ACVRP, and for PG it takes iterations. Their runtimes are 10h 20mins, 4h 40 mins, and 9h 6mins respectively. Exploitability of ACSP, ACVRP, and PG are 0.06, 0.27, and 0.13 respectively. The phenomenon that exploitabilities on three COPs 50 nodes are all larger than that on the 20-node map is reasonable and acceptable because the hardness of solving solutions grows exponentially on NP-hard problems, such as these three.
9.55
050
0.20
045
Exploitabliiyy
0.72
Saglobablis
0.35
6.0
0152
6.5
0.225
0.45
0.30
3.40
029
0.300
0.30
016
0.055
lterations
Rerations
Iterations
(a) ACSP50
(b) ACVRP50
(c) PG50
Figure 2: Exploitability on Three COPs of 50 Nodes
F.2 FULL RESULTS OF CCDORL
Here we replenish and analyze results against the stochastic adversary on three COPs, "Adv" or "no adv" columns in following tables indicates whether all instances are influenced by the learned adversary or a random adversary, respectively.
From "no adv" columns in Tables[]ande (ACSP), generalizability (unseen graphs) of the combinatorial player trained CCDO-RL are both better than others, even though the RI. baseline is trained against the stochastic adversary solely. The average improvement against RI baseline is 3.96% on different types of graphs and different nodes. Similarly under the ACVRP and PG settings, average improvements against are 3.88% and 2.72% respectively. can find CCDO-RL can also get the better reward under the usual stochastic setting, not just the adversarial setting.
(ACSP), we can see the average reward (seen graphs) and
Table 5; Full results ACSP in 20 nodes (smaller values are better)
seen graphs no adv
unseen graphs
method
no adv
ady
adv
Hcuristic
6.17+1.23
6.13++1.0
6.03+1..3
6.20+1.33
RL against Stoc
3.39
3.50
3.3910.46
3.5611..37
CCDO-RL
3.18
3.25
3.19
3.31
28

---

Published as a conference paper at ICLR 2025
Table 6: Full results on ACSP in nodes (smaller values are better)
seen graphs
unseen graphs
method
adv
ady
adv
adv
Heuristic RL against Stoc
1.50 4.29:10.61 4.16110.8
1.55
7.57:1149
7.30
4.551:0.2
4.20:10.56
4.5720.58
CCDO-RL
4.3110.51
4.17
0..52
Table 7: Full results on ACVRP in 20 nodes (smaller values are better)
seen graphs
unseen graphs
method
no adv
adv
no adv
adv
Heuristic RL against Stoc
7.50+1..3
7.65+
7.74+ 1.30
7.64+1.30 7.37+
7.38
1.16
CCDO-RI.
1.23
7.42
7.62 1.30
1.28
Table 8: Full results on ACVRP in 50 nodes (smaller values are better)
graphs
graphs
method
no adv
adv
no adv
adv
Heuristic RL against Stoc
13.22:1.775
13.381
13.45
13.271 13.85+1.53
13.89+1.85
13.90+
13.95+1.70
CCDO-RL
1..14+1.72
13.28+1.52
13.14+1.72
13.15+1.59
Table 9: Full results on PG in nodes (larger values are better)
seen graphs
unseen graphs
method
no adv
adv
no adv
adv
Heuristic
2.70:11.15
2.64
2.6411.18
2.43-10.88
RI. against Stoc
2.81+1.25
2.71++0.0
2.71+1..35
2.50+0.95
CCDO-RI.
2.75+1.06
2.75+0087
2.77
2.56+0.92
Table 10: Full results on PG in 50 nodes (larger values are better)
seen graphs
unseen graphs
method
no adv
adv
no adv
adv
Heuristic RL against Stoc
4.69+1.81
4.53+11.8.
4.47+22.2
1.19+11.9
4.87-12.75
4.80:12.18
4.58
4.26:12.17
CCDO-RL
5.97
5.01
4.84
1.70
29


Reviews:
[{"review_id": "PYSOfysIb9", "reviewer": "Reviewer_H3qj", "summary": "The paper introduces a new class of asymmetric zero-sum games that features combinatorial action space for one player and an infinite compact space for the other, termed Asymmetric Combinatorial-Continuous zEro-Sum (ACCES) games. After providing its definitions and motivations, the authors prove the existence of mixed NE in ACCES games and design two algorithms to solve for NE, with proofs and analysis on their convergence. The second algorithm, which adopts RL concepts, is further validated on three instances of ACCES games and achieves positive experimental results.", "questions": "1. Could the authors provide some remarks on ACCES games with more than 2 or more generally N players i.e., n players with combinatorial action space, and N-n players with infinite compact space? In particular, the existence of NE and generalizability of the proposed algorithms to such settings?\n2. What are the runtimes for CCDOA-RL on 50-node instances?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "+ Good presentations, particularly motivations for ACCES games.\n+ The paper designs an algorithm with proven convergence guarantee called CCDOA to solve ACCES games, which extends the idea of double oracle-based solutions from zero-sum finite games.\n+ The paper further develops a more practical version of CCDOA that uses RL and graph embedding techniques to find the approximate best response for each player.", "weaknesses": "- Experiments for evaluating CCDOA-RL are small-scale, with at most 50 nodes, which limits the practicality of the proposed algorithm. Furthermore, there were no discussions on runtimes or potential performance optimization for reducing computations.\n- Wrong bibliography style (should be [author(s), year], not numbers).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "MPgbn82Pig", "reviewer": "Reviewer_ptbk", "summary": "The paper defines and studies a novel class of two-player zero-sum games termed ACCES (Asymmetric Combinatorial-Continuous zEro-Sum) based on the premise that most zero-sum games that have been studied are either symmetric or confined to matrix games (whenever asymmetric). A natural motivation for this class is a player with a combinatorial action space (e.g., path minimization, scheduling) who plays against an environment that adversarially sets its parameters drawing from continuous parameter-value spaces (e.g., customer demand, edge weights, targets etc). The paper seeks to answer three motivating in this setting: whether a Nash equilibrium (NE) exists, whether it can be found and whether it can be found efficiently and provides affirmative answer to all three. The existence of NE is established through the properties of weakly sequential compactness and continuity of expected utility function that are established for these games. Regarding the other two questions, the paper develops an algorithm that is based on the double-oracle (DO) methods that have been used to solve finite zero-sum games and proposes an approximate, RL-based variant to tackle the exponential blow-up in computing exact best responses in the combinatorial action space of the first player. The paper complements the theoretical proofs of convergence with experiments in three ACCES environments, also demonstrating improved convergence performance against baseline algorithms.", "questions": "Can the authors discuss/address the weaknesses mentioned above?\n\n**Post-rebuttal**: I thank the authors for their responses. I still believe that the properties of weak sequential compactness and continuity of the expected utility function are fairly straightforward and hence that both the existence of Nash equilibria in ACCES games and the class itself don't really depart much from existing classes of zero-sum games. Also, while the updated version cites some zero-sum papers, I don't see a meaningful discussion/comparison with the min-max optimisation in non-convex, non-concave games or these existing classes of zero-sum games. I think this discussion requires more thorough study of the related works which cannot be done on the fly during the limited time of this discussion - and is also beyond my capacity to engage in such a discussion. This limits the contribution of the current paper in my opinion.\n\nNevertheless, I appreciate the practicality of the algorithms for real-world cases that the paper offers and which I had underestimated in my original review. I have revised my scores accordingly.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-written, clearly explains its motivation and its research questions. It also provides a fair discussion of its limitations, mainly the scalability of its proposed algorithms. \n- The paper is rigorous with proofs of convergence that seem correct to the extent that I could verify.", "weaknesses": "- While the ACCES games are interesting and cover various settings as demonstrated by the studied environments, I would have expected some more machine-learning/neural network motivation when I read about the \"adversarial parameter setting of the environment\" that was ultimately missing from the paper. Some examples that may be helpful: (https://arxiv.org/abs/2003.01820, https://arxiv.org/abs/2002.06673).\n\n- The paper does an effort to acknowledge related work, however literature on zero-sum games is vast and recent papers on learning in zero-sum (matrix) games are not entirely acknowledged (e.g., Online Learning in Periodic Zero-Sum Games and references therein, Zero-sum polymatrix games, Efficiently Computing Nash Equilibria in Adversarial Team Markov Games, The complexity of constrained min-max optimization, https://arxiv.org/abs/2011.00364 etc). \n\n- I found the existence result not surprising (maybe I am missing some technically difficult step?) and immediately following from the existence in both continuous (and bounded) and finite zero-sum games. I have a similar consideration for the convergence of the DO-based algorithm.\n\n- Essentially combining my two previous points, it is not entirely clear to me how novel this environment is and how much more interesting that the min-max optimisation in non-convex, non-concave settings. I think that the paper does not make a very convincing argument that the current setting is not a derivative, not-niche and sufficiently different and more complex setting than what is currently studied in the literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "0caAxZUsOh", "reviewer": "Reviewer_xkfi", "summary": "In this paper, the authors define and study a new useful class of two-player games called ACCES games, which feature asymmetry between the players' strategy spaces. One player has a combinatorial strategy space, while the other has a continuous one. The paper has 3 main contributions. First, the authors prove the existence of a Nash equilibrium for two-player ACCES games. Second, they describe an extension to the Double Oracle method that solves two-player ACCES games by provably converging to Nash. This method (CCDO) relies on exact best response computation at every iteration.  Finally, they present a modified version of CCDO that uses RL to approximate best responses and thus approximate Nash in more practical ACCES settings.", "questions": "* What specific scalability concerns do the authors have with CCDO-RL?\n* Is CCDO-RL guaranteed to terminate? It seems if both conditions on lines 6 and 8 in Algorithm 1 fail, then the strategy set is unchanged.\n\n**Additional Comments**\n* There seems to be a mistake on line 71 regarding the attacker and defender's utilities in the example patrolling game.\n* From the formalization, it is clear that every two-player ACCES game is zero-sum, but I suggest mentioning that earlier.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* I like this formalization. It is intuitive and seems to be a natural extension of the two-player zero-sum symmetric case that fits many interesting scenarios (like the nature vs. player and patrolling games examples mentioned in the paper).\n* The paper is impressively well-written and easy to follow. The main contributions are clearly stated and motivated early on, and the theoretical results are presented in a digestible manner that guides the reader through them. \n* The authors present theoretically sound algorithms for solving and approximately solving these games. These results are impressive on their own, but I believe they are valuable to the community because they could act as a foundation for developing more scalable algorithms in this domain in the future.", "weaknesses": "* In the conclusion, the authors mention that scalability may be a limitation of their work. Though it's not the main point of the paper, I'm somewhat concerned that the scalability of the approximate best response may limit the applicability of CCDO-RL. I don't believe the authors have to necessarily evaluate their methods on larger domains, but some insight on how the RL component of every iteration scales could help alleviate these concerns. \n* The convergence guarantees of CCDO-RL seem dependent on finding $\\epsilon$ best-responses at every iteration. To the previous point, this may be unrealistic in some larger domains. This somewhat weakens the guarantees of the algorithm, but I understand that this seems true for many algorithms whose dynamics depends on best response approximation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "L8nUsMqIcU", "reviewer": "Reviewer_LGc6", "summary": "This paper introduces and studies a new class of zero-sum games – two-player Asymmetric Combinatorial-Continuous zEro-Sum (ACCES) games, where one player has a combinatorial action space whereas the other has an infinite compact space. The asymmetry lies in the differing nature of the players’ strategy spaces. The authors claim that ACCES games closely resemble real-world problems, particularly in combinatorial optimization problems (COPs), min-max games, and security games. To evaluate their algorithms, the authors provide three different ACCES game scenarios: adversarial covering salesman problem (ACSP), adversarial capacitated vehicle routing problem (ACVRP), and patrolling game (PG).\n\n As with any new problem in game theory, the authors first prove the existence of the Nash Equilibrium (NE) for this game. The authors then propose a double oracle-based algorithm called Combinatorial Continuous DO (CCDO) to solve ACCES games, alongside proving the convergence of the algorithm. Finally they propose a Reinforcement Learning algorithm, CCDO-RL with convergence guarantees and empirically demonstrate the effectiveness of the proposed algorithm. CCDO-RL adopts RL to compute the approximate best responses.", "questions": "* The dynamics of the ACCES game is unclear. Is it a turn based or a simultaneous move game? Also, is it a fixed-horizon game or an infinite one with some termination criterion? \n* In line 166, shouldn't $X$ be **all** *routes* instead of **any** ? \n* Line 140: \n> As far as we know, they are limited to matrix games, ...\n\n  * Don't McAleer et al. (2021) consider both extensive-form games and a continuous game? I am not sure what is being referred to as being \"limited to matrix games\" as McAleer et al. (2021) also prove convergence to $\\varepsilon$-NE. Could authors please elaborate on this? Perhaps I misunderstood. \n\n* Line 328:\n> However, the approximation of BR may cause circumstances where the utility of the approximate best response is lower than that of NE in the subgame\"\n\n  * I am curious as to how this would impact the final policy. Yes, it is possible that the approximate BR may not be accurate leading to a negative NashConv, which is theoretically not possible. Could authors comment on the impact of removing the steps 6-9 in Algorithm 1 from purely experimental standpoint? Also, explaining this part in a bit detail might help readers understand the issue. \n\n* I couldn't find the results and/or discussion on \"how different ABRs influence convergence\". Perhaps my interpretation of different ABRs as different BR approximating algorithms is not correct. Could authors please comment on this?\n\n*McAleer, S., Lanier, J. B., Wang, K. A., Baldi, P., & Fox, R. (2021). XDO: A double oracle algorithm for extensive-form games. Advances in Neural Information Processing Systems, 34, 23128-23139.*", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The paper tackles a novel problem in 2p0s games by considering asymmetry in strategy space rather than the common forms of asymmetry (e.g., information asymmetry). \n- The authors provide theoretical proofs for the existence of NE and convergence of their algorithms, as well as empirical demonstrations of their effectiveness and superiority compared to baselines based on heuristics and a single-agent RL algorithm.", "weaknesses": "- The patrolling game in the introduction might benefit from a better explanation, especially labels for P1 and P2 (attacker/defender). It would be helpful if the authors could label which player is the attacker and which is the defender. \n- Algorithm 1 in the paper seems very similar to the XDO/NXDO algorithms (McAleer et al., 2021). Perhaps the novelty is in computing the BRs (McAleer et al. consider BRs but the authors here consider approx. BRs), but the underlying algorithm, as presented, seems the same.  Highlighting the difference of the proposed algorithm with existing algorithm such as XDO/NXDO might underscore the challenge of solving the proposed problem. \n- How the mixed equilibria (step 3 in all algorithms) are solved in the subgame is unclear. This is likely the crucial part of the problem, given the different strategy spaces associated with the players. Briefly explaining the computational technique would be helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)