Can Reinforcement Learning Solve Asymmetric Combinatorial-Continuous Zero-Sum Games?

We thank the reviewer for the very detailed and constructive comments and feedback!

W1: Clarified explanation for the patrolling game

Thanks for your advice. We have updated this example as follows (Section 1, Paragraph 4):

Player 1’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 \ref{sec_exp}), 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 a subset $\Pi$ of all targets $\{1, 2, …, N\}$ meanwhile satisfying the total distance constraint $L_{all}$ because of limited patrol time. For the attacker, the strategy is the attack probability vector $\{p_1, p_2, …, p_N\}$ for the target set. Besides, each target $i \in \{1, 2, …, N\}$ has its own value $v_i$. The utility function for the defender is the expectation of successfully protected target values, i.e. $U_d = \sum_{i=1}^N p_i v_i \mathbb{I}_{\Pi}$. The attacker’s utility function is then: $U_a = - U_d$.

W2: Differences of CCDO-RL to XDO/NXDO

Thanks for your positive advice! In Related Work and Section 5.1, we have added and highlighted the difference between our algorithm and DO’s variants.

Compared with XDO/NXDO, our algorithm is different from the perspective of convergence analysis of CCDO and CCDO-RL, and termination criterion. The detailed difference is as follows:

1. Novelties of convergence analysis of CCDO and CCDO-RL

• XDO is a tabular extensive-form double oracle algorithm, while NXDO extends it using deep reinforcement learning (DRL). It guarantees convergence only in matrix games, as its strategy space can be expanded to the full game within a finite number of iterations which does not work for the infinite/continuous strategy space in ACCES games. NXDO addresses continuous-action games empirically with Deep RL, though it lacks algorithmic guarantees. Our algorithm, CCDO-RL (CCDOA), has a convergence analysis (Theorem 3) in ACCES games, which is not feasible for XDO or other DO variants like ODO, despite a similar framework. In CCDO-RL, the DRL component helps achieve approximate best responses, leveraging its strengths in solving combinatorial problems (Section 5.2, Lines 336-342), rather than facing issues with continuous strategy spaces as in XDO.
• We propose the convergence analysis with approximate best responses (ABRs) and different ABRs’ influence on the convergence. Approximate best responses (ABR) are very commonly used in COPs due to their NP-hardness. It’s therefore critical to consider its effect on the convergence of ACCES games which wasn’t addressed before. We provide the novel convergence analysis of CCDOA\CCDO-RL and study different ABR’s influence on convergence (Theorem 3 Item 2 and Remark 2) in Section 5.4.

2. Termination criterion

It's interesting to note that XDO doesn't have a specific termination criterion because it can naturally stop because of the finiteness of actions but cannot be possibly guaranteed in ACCES games because of the infinite strategy space of the continuous player (Player 2). Due to the continuity/infiniteness of Player 2’ strategy space, we've incorporated a termination criterion (Line 11 of Algorithm 1). This helps us ensure that the algorithm can stop while still maintaining convergence.

W3: Solving mixed NE in the subgame

Thanks for your constructive suggestion! We have added the statement of solving mixed NE in Section 5.2, paragraph 2.

We solve for the mixed Nash equilibrium in the ACCES game using the support enumeration algorithm [1]. This approach is based on linear programming and utilizes the Nashpy implementation [2], which relies solely on the utility matrix of the subgame without considering the strategy spaces.

[1] Tim Roughgarden. Algorithmic game theory. Communications of the ACM, 53(7):78–86, 2010.

[2] Vincent Knight and James Campbell. Nashpy: A python library for the computation of Nash equilibria. Journal of Open Source Software, 3(30):904, 2018.

We thank the reviewer for the positive and constructive comments.

W1: Scalability

Great point. As noticed by the reviewer, scalability is not the main focus of the paper, but we do agree that this is a critical aspect that needs further work. To shed some light on this point, we have added the following discussion to Appendix E.2.

[COPs simplification method]

• The pruning method: this one was introduced in the original scale of COPs to reduce the number of possibly useful actions. In this way, the computational burden will be decreased [1, 2].
• Broken down into subproblems: in some concrete COPs like TSP[3], and VRP [4], the originally large-scale problem can be broken down into smaller problems to solve, thereby reducing the solution difficulty.

[RL algorithms]

• 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 RL).
• NN Model Adjustment: most constructive neural network fitting combinatorial optimization can not solve problems with large-scale instance sizes. One feasible way is to design an NN model with strong scalability which means that the trained model on small-scale problem instances can be used on large-scale ones, such as in influence maximization [5].
• Distributed training: reduces the time required for training by splitting the computational workload across multiple devices.

W2: Convergence guarantee dependent on finding ϵ best-responses

Thanks for your comment. We really agree with the reviewer. Find best responses(BRs) or $\epsilon$- best responses are an important part of all DO-based algorithms because we need to assume the property of approximate BRs to prove the convergence guarantee and the approximate degree to NE. To some extent, \epsilon-best response plays a very important role in the whole algorithm.

Q1: Scalability

Please see the response to W1.

Q2: Termination guarantee of CCDO-RL

Good question! CCDO-RL had its convergence guarantee as stated in Theorem 3, which considers RL as a method for achieving an approximate best response(ABR).

Regarding the scenario where both conditions on Lines 6 and 8 fail, we think it’s a special case of Theorem 3 Item 1, i.e. CCDO-RL converges to the $(\epsilon_1 + \epsilon_2)$- equilibrium. Two ABRs have their approximate error bound, $\epsilon_1$ and $\epsilon_2$ respectively. If Lines 6 and 8 fail together, assuming the current subgame mixed NE is $(p_k^*, q_k^*)$, we can get that

$\max_{x \in X}U(x, q_k) - \min_{y \in Y}U(p_k, y) \leq \epsilon_1 + \epsilon_2.$

Set $\bar{\epsilon} = \epsilon_1 + \epsilon_2$ as a new stopping criterion in CCDO, we can draw our conclusion by Theorem 2 Item 2.

Additional Comments

Thanks for your comments! We have corrected these two points in the updated version.

[1] Manchanda S, Mittal A, Dhawan A, et al. Learning heuristics over large graphs via deep reinforcement learning[J]. arXiv preprint arXiv:1903.03332, 2019.

[2] Lauri J, Dutta S, Grassia M, et al. Learning fine-grained search space pruning and heuristics for combinatorial optimization[J]. Journal of Heuristics, 2023, 29(2): 313-347.

[3] Fu Z H, Qiu K B, Zha H. Generalize a small pre-trained model to arbitrarily large tsp instances[C]// AAAI. 2021, 35(8): 7474-7482.

[4] Hou Q, Yang J, Su Y, et al. Generalize learned heuristics to solve large-scale vehicle routing problems in real-time[C]// ICLR. 2023.

[5] T. Chen, S. Yan, J. Guo, and W. Wu, "ToupleGDD: A Fine-Designed Solution of Influence Maximization by Deep Reinforcement Learning," in IEEE Transactions on Computational Social Systems, vol. 11, no. 2, pp. 2210-2221, April 2024.

We sincerely appreciate your constructive feedback on our work.

W1: ML (RL)/neural network motivation

Thanks for your comments. We have added the adversarial motivation in Section 5.2. We will explain the motivation of the adversary from two perspectives, solvability to diverse instances of the problem, and generalizability.

• Solvability to diverse instances of the problem: RL combined with GNN demonstrates strong adaptability in handling diverse instances of a problem. For example, in scenarios like the patrolling game, where target positions and values vary, RL+GNN effectively updates its strategy and makes good decisions. This is because it learns the complex nonlinear mapping from problem-specific information—often represented as high-dimensional graph data in combinatorial optimization problems (COPs)—to precise decision-making actions.
• Generalizability: The adversary trained using RL+GNN exhibits remarkable generalization capabilities across different data distributions, including unseen graphs. As demonstrated in the "unseen" column of Tables 4-9, the trained adversary causes greater average performance degradation in the combinatorial player's strategies compared to the stochastic adversary (3.38% on average of all problems).

W2: Related Work

We appreciate your insights into the literature on zero-sum games. Based on your feedback, we have enhanced our related work (Section 2, paragraph 2), adding the following sentence and several references,

“Except for DO and its variants, NE learning in zero-sum settings remains appealing in periodic games [1], polymatrix games [2], Markov games [3], etc.”

W3: Novelty and significance of existence and convergence results

Thanks for your comments. We have rewritten and highlighted novelties of the existence of NE and CCDO in Section 4 paragraph 2, and Section 5.1. Here we emphasize those novelties as follows.

[The existence of NE]

In the first paragraph of Section 4, Lines 220-225, we have highlighted the reason why the existence of NE of ACCES games can not be derived from matrix games and continuous games directly. In short, the elements in ACCES games violate the basic principles of the existence of NE in matrix games – finite strategies, and that in the continuous game – the continuity of the utility function on $X \times Y$.

More specifically about the difficulty, in the ACCES game, the existence of NE requires the weakly sequentially compact property of the joint mixed strategy space and continuity of the expected utility function, which has not been established in the existing literature. We fill the gap by proving the two properties in ACCES games (Propositions 1 and 2), which further play a foundational role in proving the existence of NE (Theorem 1).

[Novelties of convergence analysis of CCDO and CCDO-RL]

• In Section 5.1 Lines 311-315, we describe the inner mechanism of the convergence of DO and its variants. For DO and its variants (like ODO, XDO, etc.), the convergence of their algorithms mainly relies on the finite strategy space property (to transform the subgame into the original game by adding the best response (BR) over a finite number of iterations), which does not work for the infinite/continuous strategy space in ACCES games, and this fundamentally alters the structure of convergence analysis. Hence the first novelty is that our algorithms, CCDO and CCDOA both have the convergence guarantee in the ACCES game.

• We propose the convergence analysis with approximate best responses (ABRs) and different ABRs’ influence on the convergence. ABRs are very commonly used in COPs due to their NP-hardness. It’s therefore critical to consider its effect on the convergence of ACCES games which wasn’t addressed before. We provide the novel convergence analysis of CCDOA\CCDO-RL and study different ABR’s influence on convergence (Theorem 3 Item 2 and Remark 2) in Section 5.4.

W4: Summarizing W1 and W3

About the motivation of the adversary and novelties of theory, please see our responses to W1 and W3.

We need to bring to the attention of the reviewer that, in addition to the theoretical contributions, we also proposed a practical algorithm to solve real-world problems. This is challenging as even a sub-problem of finding the BR for the combinatorial strategy space of one player is known to be NP-hard, let alone the entire ACCES game. We bridge this gap by proposing CCDO-RL, which adopts RL as an efficient sub-routine to compute the ABRs.

[1] Fiez, T. et al. (2021). Online learning in periodic zero-sum games. In Neurips, volume 34, pages 10313–10325.

[2] Cai, Y. et al. (2016). Zero-sum polymatrix games: A generalization of minmax. Mathematics of Operations Research, 41(2):648–655.

[3] 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–1241.

Q1: Extension to N-player ACCES games

Excellent questions! Thank you for pointing out. We have added the N-player remark in Section 4 (analysis details added in Appendix A.2). Our concrete analysis is as follows.

1. The existence of NE (N-player ACCES games)

Our propositions and Theorem 2 can 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 in ACCES games, weakly sequential compactness of the mixed strategy space and continuity of the expected utility function (Propositions 1 and 2), and the approximation idea by finite games. We introduce these as follows:

• [Two properties] In Proposition 1, 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 1. 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 essentially finite games. The idea and definitions are not limited to the two-player setting.

2. CCDO & CCDO-RL algorithms

Due to the focus on the double oracle setting of our algorithms (CCDO, CCDO-RL), there is no theoretical guarantee possibly on the N-oracle setting. More potential algorithms in the multi-player RL field can be used for reference to develop the N-player ACCES game [1].

Q2: Runtimes on 50-node instances

The following time also contains intermediate variable storage (best response models in each round), and algorithm computation (training two approximate best responses and mixed NE solution). We have added the runtimes on 50-node instances in Appendix F.1. Note that since scalability is not the focus of this work, we did not pay much attention to runtime reduction. As we have discussed in the response to W1 above, there is a suite of methods that can be potentially used to reduce the runtime, the effort of which can be made in parallel with our work. Also, our initial results above show that the RL policies trained on smaller graphs (e.g., 50 nodes) can be generalized to larger graphs (e.g., 100 and 200 nodes), as shown in our response to W1.

• Adversarial covering salesman problem: 10h 20mins
• Adversarial capacitated vehicle routing problem: 4h 40mins
• Patrolling Game: 9h 6 mins

[1] Zhang, Youzhi, and Bo An. "Converging to team-maxmin equilibria in zero-sum multiplayer games." International Conference on Machine Learning. PMLR, 2020.

Thank you for your feedback. Below, we address your comments point by point.

W1: Scalability and runtime discussion

These are great points. Although our conclusion section has summarized that scalability is not the focus of our current work, we agree that this is a critical aspect and hence we have provided the following further discussions in the revised version (Appendix E).

1. [Scale and runtime analysis]

In CCDO-RL, three components need to be trained or computed:

• The combinatorial player’s policy. This player solves a combinatorial optimization problem (COPs) under a specific strategy of the adversary.
• The continuous player (as the adversary) with an infinite continuous strategy space.
• The computation of Mixed Nash Equilibria (NE) in the subgame.

Next, we will analyze the computation time for each component individually theoretically and experimentally. For the experimental part, we will use the 50-node Patrolling Game (PG) scenario, which is the most challenging problem in our experiments, as an example.

• The combinatorial player is trained using Graph Neural Networks (GNN) and REINFORCE to find feasible and optimal solutions for NP-complete COPs. This complexity requires RL to invest more time and data for effective model training. Training a stable and high-performing combinatorial model takes 26 minutes (10000 data, 1024 batch size, 150 epochs) with the continuous player fixed.
• The continuous player is trained by PPO to tackle a one-step problem. It still utilizes GNN to understand graph structure. One action per episode leads to reduced training times compared to the combinatorial player. Training a high-performing model takes only 4 to 5 minutes (10000 data, 1024 batch size, and 50 epochs).
• For the NE solution, the mixed equilibria in a zero-sum game can be solved by the linear programming method which has polynomial complexity in the size of the game tree. From the perspective of experiments, the computational 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, a crucial aspect of addressing the scalability issue is to enhance the speed of solving the COPs using RL.

2. [Potential ways of improvement]

We briefly discuss the following two main aspects. Note again that these methods will be in parallel to our work, and serve as future work.

• COPs simplification method

  • The pruning method: this one was introduced in the original scale of COPs to reduce the number of possibly useful actions. In this way, the computational burden will be decreased [1, 2].
  • Broken down into subproblems: in some concrete COPs like TSP[3], and VRP [4], the originally large-scale problem can be broken down into smaller problems to solve, thereby reducing the solution difficulty.

• RL algorithms

  • 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 RL).
  • NN Model Adjustment: design an NN model with strong scalability which means that the trained model on small-scale problem instances can be used on large-scale ones, such as in influence maximization [5].

3. [Train CCDO-RL in small graphs, test in larger unseen graphs]

We quickly tested the CCDO-RL model (trained on 50-node graphs) on larger patrolling game scenarios. For example, on unseen 100-node and 200-node graphs (100 of each type), CCDO-RL outperformed other baselines with almost negligible test runtime.

We will add more experiment results on CSP and CVRP.

W2: Wrong bibliography style

Thanks for pointing it out! We have corrected the bibliography style in the updated version.

[1] Manchanda S, Mittal A, Dhawan A, et al. Learning heuristics over large graphs via deep reinforcement learning[J]. arXiv preprint arXiv:1903.03332, 2019.

[2] Lauri J, Dutta S, Grassia M, et al. Learning fine-grained search space pruning and heuristics for combinatorial optimization[J]. Journal of Heuristics, 2023, 29(2): 313-347.

[3] Fu Z H, Qiu K B, Zha H. Generalize a small pre-trained model to arbitrarily large tsp instances[C]// AAAI. 2021, 35(8): 7474-7482.

[4] Hou Q, Yang J, Su Y, et al. Generalize learned heuristics to solve large-scale vehicle routing problems in real-time[C]// ICLR. 2023.

[5] T. Chen, S. Yan, J. Guo, and W. Wu, "ToupleGDD: A Fine-Designed Solution of Influence Maximization by Deep Reinforcement Learning," in IEEE Transactions on Computational Social Systems, vol. 11, no. 2, pp. 2210-2221, April 2024.

We have completed an additional set of experiments on the CSP problem. Similarly, we tested the CCDO-RL model (trained on 50-node graphs) on larger-scale scenarios (100-node, 200-node, and 500-node unseen graphs, averaged over 100 of each type). The results demonstrate that CCDO-RL performs better than the baselines while requiring significantly less test time compared to the heuristic algorithm.

We hope our responses address your concerns, and we are happy to clarify further if needed.