A Framework for Finding Local Saddle Points in Two-Player Zero-Sum Black-Box Games

Comment: There is no discussion on the rationale behind the assumptions in Lemma 4.1. Please offer an explanation here.

Response: We thank the reviewer for the question. The assumptions of Lemma 4.1 are standard technical assumptions. Specifically, the main idea behind these assumptions is to ensure that the Jacobian of the players’ first order necessary conditions is nonsingular; this condition is well-known to ensure that Newton steps on those necessary conditions are descent directions on merit function $M^{CB}_t$ [Nocedal and Wright, Ch. 11], and ultimately that LLGame converges to a first-order local Nash point. If this point remains unclear, we are happy to update the manuscript.

Manuscript Changes: We have clarified the rationale for these assumptions in Section 4.3.

We thank the reviewer for their detailed comments. Please find our responses below. All references refer to works cited in the manuscript.

Comment: The framework innovatively combines ideas from Bayesian optimization with saddle point optimization in a black-box setting. It offers a zeroth-order technique for finding saddle points. The explanation of the bilevel optimization framework is well-organized. The ability to identify saddle points in nonconvex-nonconcave black-box settings is highly relevant for a wide range of applications, particularly those involving adversarial dynamics and game theory. The experimental results are comprehensive, and the ablation studies have been conducted.

Response: We thank the reviewer for their kind words for the strengths of our contribution, and for their time and effort in reviewing our manuscript.

Comment: The theoretical guarantees of the algorithm in this paper are somewhat insufficient, with only Lemma 4.1 used to show that the algorithm converges to a local Nash point, and the assumptions made are rather strong.

Response: We thank the reviewer for their feedback on this important topic. As noted in our top-level comment, this manuscript opens up a new line of work in solving black-box zero-sum games. While we acknowledge that our algorithms may converge to a point which is not precisely a LNP, our empirical success rate results shown in Appendix Table 2 demonstrate that our algorithms find LSPs more frequently than a state-of-the-art baseline method from the literature (called LSS) even when it is provided with a gradient oracle. In the case of LSS, this is because the theoretical guarantee that LSS’ limit points coincide with local saddle points only holds if LSS converges. In practice, we find that LSS often fails to converge on common experiments used in the literature, as reported in Appendix Table 2. Thus, we believe that these empirical results are enough to establish the practical potential of the proposed black-box saddle point approach.

In addition to Lemma 4.1, we highlight additional theoretical results Lemma A.1 and Remark A.2 which discuss how the LCB and UCB approach one another as more function evaluations are taken in subsequent iterations, meaning that the general-sum LLGame becomes more similar to the underlying zero-sum game as described in Section 4.

Manuscript Changes:

• Section 2: We provide a clearer discussion of the drawbacks of existing methods.
• Section 4.3: We more directly reference Lemma A.1 and Remark A.2 from the Appendix which discuss the convergence of LCB and UCB under certain conditions.
• Section 5: We clarify that our chosen experiments are drawn from example problems in the literature.
• Section 6: We have clarified in the conclusion it will be important for future work to establish theoretical guarantees regarding the convergence rate of the GP and guarantees of convergence to LSPs.
• Appendix, Table 2: We clarify that our reported success rates check the success of a given run against the true second-order optimality conditions of $f$ at the solution point.

Comment: The paper lacks a dedicated "Related Work" section. It appears that the related work has been split into two parts, placed separately in Section 1 and Section 2. I suggest reorganizing Section 1 and Section 2. The current structure is somewhat disorganized and lacks a systematic introduction to prior work. The paper lacks a dedicated "Related Work" section. It appears that the related work has been split into two parts, placed separately in Section 1 and Section 2.

Response: As requested, we have reorganized Sections 1 and 2 to more clearly introduce related work.

Manuscript Changes: We renamed the second section of the manuscript to “Related Works and Preliminaries,” and moved the last two paragraphs of the introduction into this section to consolidate the related works and preliminaries into this section.

Question: How to incorporate second-order sufficient conditions to enhance the performance of your approach? Please give further explanation.

Response: We believe the reviewer is likely referring to our statement about the possibility of incorporating second-order conditions to enhance the performance of our algorithms. We envision this arising within the LLGame problem, where currently we are only able to search for first order local Nash points. To understand why we do this, recall that the inner game is not zero-sum, but general-sum. Solving general-sum games in nonconvex-nonconcave settings with guarantees about satisfying second order conditions is an open problem. We note that prior works like Mazumdar et al. 2019 and Gupta 2024 et al. can solve zero-sum games in nonconvex-nonconcave settings with guarantees about second order conditions (though we note that for Mazumdar et al. 2019 and Gupta et al. 2024, such a guarantee is only provided if the algorithm converges). However, these approaches can not be applied to general-sum settings as in LLGame, and moreover they cannot be applied to the original zero-sum problem because they require access to second derivative information.

Ultimately, then, our aim in this pointer to future work is to emphasize the importance of finding algorithms for finding (second order) local Nash equilibria in general-sum games, and to make it clear that progress in this direction would clearly benefit our framework.

Manuscript Changes: We have made clarifications in Section 6 that more clearly explain how we aim to adjust our approach.

We hope these clarifications highlight the advantages of our work and make our contributions more transparent. We are more than happy to address any further concerns and provide additional explanations for any point. If we have addressed all your concerns, we kindly request that you reconsider our score.

Thank you for your response! I will maintain my positive score and recommend accepting this paper.

We thank the reviewer for their detailed comments. Please find our responses below. All references refer to works cited in the manuscript.

Comment: The paper targets an important problem, which is to solve two-player zero-sum games in the general nonconvex-nonconcave setting with only zeroth-order samples. The introduction and description of the algorithm makes general sense. The numerical simulation verifies the algorithm performance to a certain extent.

Response: We thank the reviewer for their kind words regarding our contribution, and for their time and effort in reviewing our manuscript.

We thank the reviewer for their detailed comments. Please find our responses below. All references refer to works cited in the manuscript.

Comment: This paper addresses a problem that has received limited attention in the literature: the optimization of black-box games. It introduces a novel framework that combines a diverse set of techniques to tackle this challenge, making it a noteworthy contribution.

Response: We thank the reviewer for their kind comments on the strengths of our work, and for their time and effort in reviewing our manuscript.

Comment: The experiments are ultimately not convincing: while the experiments on synthetic data successfully achieve the optimal merit function, the real-world examples are less successful compared to the only other baseline and require further improvement.

Response: We thank the reviewer for this feedback. With respect, we believe that these experiments are extensive enough to establish the practical potential of the proposed black-box saddle point approach, though of course there remain a wide variety of interesting application problems which can and should be studied. Regarding the “real-world examples,” we assume that the reviewer is referring to the ARIMA MPC example from Figure 2. In this particular example (see the key takeaway of Figure 2), we highlight the 27.6% improvement in the out-of-distribution (OoD) cost when using our version of Robust MPC and have revised the language to emphasize why operating at a saddle point should lead to better performance on this metric, compared with a MPC which is not operating at a saddle point. Additionally, the third column of Figure 4 in the Appendix demonstrates that all of our algorithms achieve the optimal merit function value when provided a large number of initial samples on this real-world example, and that three of the four do so when provided a limited number of initial samples.

We note that high-dimensional polynomial and the decaying polynomial examples are difficult problems taken from prior works [Bertsimas et al. 2010, Bogunovic et al. 2018, Mazumdar et al. 2019, and Gupta et al. 2024], and that they have been used in other papers as testbenches for comparing the performance of zero-sum game solvers. Moreover, as documented in Table 2 of the Appendix, our algorithms find LSPs more often than state-of-the-art baseline algorithms like LSS (because LSS only guarantees finding a LSP if it converges).

Manuscript Changes: We have included additional clarification in the manuscript regarding the results we have cited in our response. We clarify that our chosen experimental test cases are accepted as baseline problems by many previous works in the literature.

We thank the reviewers again for their time and effort and look forward to further suggestions which may improve our manuscript to clarify this topic.

Important Clarification: We thank the reviewer for their comments. Prior to responding to the specific comments, we would like to clarify a point regarding our contributions compared to prior work, which will be critical to our subsequent responses. Prior work on saddle point optimization varies across three axes:

• A1. whether the optimization objective is known or sampled (“black-box”),
• A2. whether the optimization objective is convex-concave or nonconvex-nonconcave, and
• A3. whether the method assumes gradient access for the samples or not.

We present the first black-box technique for saddle point optimization on nonconvex-nonconcave objectives based on zeroth-order information. While prior works may exist that find saddle points in black-box settings or on nonconvex-nonconcave objectives or with zeroth-order samples, our work is the first, to our knowledge, that achieves all three simultaneously.

Manuscript Changes: Upon reviewing the manuscript once more, we realize we did not state this sufficiently clearly within our contribution, and we have updated the manuscript to clarify this. Specifically, we did not note the nonconvexity-nonconcavity of the objective in our contributions at all, and wanted to clarify in case this had caused confusion.

Comment: The choice of LLS, a second-order method, as a baseline is unclear. Why not use a simpler alternative like gradient descent ascent with finite differences? Moreover, back to my original point, in your polynomial example, where gradients are accessible, it would be highly informative to compare your method against a first-order approach, such as gradient descent ascent. As expected, a zeroth-order method would likely perform worse, but such a comparison would provide valuable context for evaluating your approach.

We thank the reviewer for this line of questioning, as we may have misunderstood the previous question. As mentioned in the manuscript, we provide three baselines:

• Random: This baseline is a zeroth-order optimization method which randomly samples points in the domain and keeps the one with the lower cost. We note, for the purpose of clarity, that zeroth-order here refers to both the optimization method (which does not require gradients at all as compared to GDA) and the order of the samples (each of which simply includes the noisy cost measurement).
• Zeroth: This baseline refers to gradient descent-ascent (GDA) with finite differencing to compute the gradient samples. While we do note this in Section 5.1, in retrospect, this is inappropriately named, and we have changed the name to “GDA with FD”. We also note that the merit function for GDA with FD never converges to 0 (see Figure 1) on our example problems due to the noise introduced by finite differencing, which is excessive for the problems we test against, and subsequently prevents convergence on those problems.
• Local Symplectic Surgery (LSS) [Mazumdar et al. 2019]: Returning to the reviewer's question about LSS, we sought to compare our work to a state-of-the-art approach in order to compare our work with others which have additional theoretical guarantees on these problems. We were limited to works in nonconvex-conconcave settings (A2), and only Mazumdar et al. 2019 provided convergence guarantees in a black-box setting (A1). Thus, we chose to include LSS as a state-of-the-art baseline despite it requiring gradient access (A3). Due to finite differencing not working well in the GDA baseline, we chose to provide a gradient oracle instead of finite differencing, as noted in our previous comment. We note that when we did try LSS on the decaying polynomial example problem with finite differencing to estimate first- and second-order gradients, the solver always converged to the false saddle point at (0, 0).

With regards to using GDA without finite differencing, if this is what the reviewer meant, we don’t quite understand the benefit over the first-order method we did include, but we are open to hearing more.

In summary, we provide zeroth-order, first-order, and second-order baselines as comparisons to our work, including the exact baseline the reviewer asked about (albeit badly labeled). We hope this response clarifies our decision to use each baseline.

Manuscript Changes: Renamed “Zeroth” baseline to GDA with FD in Figure 1 and Section 5. We also added additional discussion about baselines in Section 5.

Comment: To ensure the accuracy of this result, could you clarify what the merit function is exactly? I am surprised that I could not find an exact equation for it. Describing your only metric vaguely with words is not very helpful. This is what I found: $M_f$, which is calculated based on the true gradients of the underlying function, rather than the confidence bounds employed in the actual algorithm. Based on this description, and assuming you have access to the function for the first two experiments, I would expect you to use the second-order derivative to ensure the algorithms do not converge to spurious saddle points. Is that what you did?

Response: We thank the reviewer for this question about the merit function, and for the opportunity to clarify.

For the definition of merit function $M^f$, we point the reviewer to Equation (8) in Section 4.2, where we define $M^f$ as follows,

G^{f}(x, y) = \left[\begin{array}{c} \nabla_{x} f (x, y) \\ -\nabla_{y} f (x, y) \end{array}\right]^\intercal, ~~~~~ M^{f}(x, y) = \frac{1}{2} \|\|G^{f}(x, y) \|\|^2_2. \

Thus, we note that minimizing $M^f$ satisfies first-order necessary conditions as defined in Proposition 3.3. This is the merit function used to produce the plots in Figures 1 and 4.

As the reviewer correctly expects, we then compute the success rate based on the true second-order derivatives $\nabla^2_{xx} f, \nabla^2_{yy} f$ as described by the second-order sufficient conditions in Proposition 3.4. This ensures that we do not include spurious saddle points when we report success rates in Appendix Table 2.

Next, for the purpose of clarity, we reiterate the differences between the three merit functions present in our manuscript, $M^{f}$, $M\^{CB}\_{t}$, and $M\^{\\mu}\_{t}$. Each of these is associated with a vector $G^{f}$, $G\^{CB}\_{t}$, and $G\^{\\mu}\_{t}$, which describe the roots which satisfy first-order conditions according to Proposition 3.3. For the latter two, the subscript $t$ indexes the iterations of BSP, i.e. how many times we have sampled the function, added the sample to the dataset, and updated the GP estimate of $f$.

As $f$ is not known in our black-box setting, we can not use it directly to measure progress within the algorithm. Thus, we do the following in our work.

• $M^f$ measures the progress towards the true first-order roots of the true objective, and it is used solely for describing the performance of our algorithm compared to other algorithms. It is not used within the BSP algorithm at all.
• $G^{CB}_t$ is defined using the gradients of $\\text{LCB}_t$ with respect to x and $-\text{UCB}_t$ with respect to y. The confidence bounds are defined as a function of the GP estimate. Thus, $M^{CB}_t$ measures the progress towards a first-order root of the general-sum lower-level game (5). $M^{CB}_t$ is only used in the lower level game.
• $M\^{\\mu}\_{t}$ serves as the replacement of $M^{f}$ in our BSP algorithm. The merit function $M\^{\\mu}\_{t}$ is defined by replacing $f$ in $M^{f}$ with $\\mu_t$, the mean function of the GP at iteration $t$. Thus, $M\^{\\mu}\_{t}$ measures the progress of the high-level, zero-sum game towards a first-order root of the GP mean $\\mu_t$, which estimates $f$ based on the samples. Upon the convergence of the algorithm, BSP tests the second-order conditions (in Proposition 3.4) using $\\nabla_{xx} \\mu_t$ and $\\nabla_{yy} \\mu_t$ to test for spurious saddle points. If the test fails, it reinitializes and begins again.

We hope that this answers the reviewer’s question, but if anything remains unclear, we are happy to further refine our manuscript based on feedback.

Manuscript Changes: We edit the passage in Section 5 that the reviewer cites to include a reference to Eq. (8) in Section 4.2, where $M^f$ is defined. We further clarify in the caption of Table 2 that the success rate is checked using the true second-order sufficient conditions of $f$, as defined in Proposition 3.4.

Comment: Thank you for your response.

The explanation regarding your random and zeroth-order baselines, as well as the new naming, was very helpful. I appreciate it.

The fact that you are providing the first- and second-order oracles to LSS (if I understand correctly) and yet your method still performs better highlights the strength of your approach.

Response: We thank the reviewer for their kind words, and for helping us clarify this point to better highlight the strengths of our approach. We confirm that the reviewer’s understanding is correct. Our method performs better than LSS in this setting despite us providing LSS with an “unfair advantage,” so to speak: providing it first- and second-order oracles.

We thank the reviewers one final time for their feedback and engagement during the discussion period. We are happy the reviewers like that our approach to the relevant and understudied problem of saddle point optimization used a diverse set of techniques based on Bayesian optimization to create a surrogate model of the objective (gbJe, C6CC, euUW), introduced a way to frame the saddle point optimization as a bilevel game (gbJe, C6CC, euUW), and strong, thorough experimental results which outperformed existing baselines (gbJe, eeUW).

We have addressed each reviewer’s comments thoroughly, including by

• reiterating the diversity, strength, and thoroughness of our first-of-kind experimental results on multiple challenging real-world and synthetic settings, (as emphasized in the previous comment)
• introducing a new baseline and associated experimental results based on a related work we were initially unaware of, which our method outperforms significantly on nonconvex-nonconcave settings, and
• clarifying the reasoning behind each choice of baseline, including zeroth-order, first-order and second-order comparisons.