Two-Player Zero-Sum Differential Games with One-Sided Information and Continuous Actions

Authors: Mukesh Ghimire, Lei Zhang, Zhe Xu, Yi Ren
Primary area: learning theory
Keywords: Incomplete Information Game, Differential Game

Abstract:
Unlike Poker where the action space $\mathcal{A}$ is discrete, differential games in the physical world often have continuous action spaces not amenable to discrete abstraction, rendering no-regret algorithms with $\mathcal{O}(|\mathcal{A}|)$ complexity not scalable. To address this challenge within the scope of two-player zero-sum (2p0s) games with one-sided information, we show that (1) a computational complexity independent of $|\mathcal{A}|$ can be achieved by exploiting the "Cav u" property of behavioral strategies in incomplete-information games and the Isaacs' condition that commonly holds for control systems, and that (2) the computation of the two equilibrium strategies can be decoupled under the Isaacs' condition. We provide computational complexity of the resultant algorithm for approximating continuous-action mixed strategies (CAMS). Empirically, we demonstrate correctness of CAMS using a homing game where the Nash equilibrium exists analytically, and scalability through the same game with higher-dimensional actions. Codes available in [anonymous repo](https://anonymous.4open.science/r/iclr-3245).

Decision: reject
Reviewer scores: 6, 3, 3

Reviews and discussion:
<thread>
creation date:
1730482441766

thread_type:
official_review

<thread_object>
creator: reviewer_zbcv

<content>
summary:
In this work, the authors consider the problem of solving a differential two-player zero-sum game with one-sided information, meaning a game where only one player is informed about the "type" of the terminal function, i.e., the reward/loss function.

strengths:
Unfortunately, I cannot identify any significant strengths in this work. The writing is so unclear that it is nearly impossible to follow.

weaknesses:
Immediately upon beginning to read the paper, it becomes evident that it requires extensive rewriting. The phrasing is often either ambiguous or nonsensical. This issue is apparent even from the abstract, where the authors attempt to present their results with phrases like "a computational complexity independent of $|A|$ can be achieved," when they actually mean "a method/algorithm with computational complexity independent of $|A|$ can be achieved." They define CAMS as approximating continuous-action mixed strategies, but then ambiguously state “we demonstrate correctness of CAMS.”

Throughout the paper, there are missing articles and numerous errors. Additionally, the definition of zero-sum differential games is presented hastily; understanding the concept requires consulting other sources. Even the statement of the problem—that in zero-sum differential games, P1 seeks to minimize the terminal payoff function $g_i(x(T))$ (plus a running cost) while P2 aims to maximize it—is not clearly stated. The equilibrium, which is presumably the key concept, is not defined. Even in the introduction, the authors mention a no-regret algorithm without explaining what no-regret is. They reference no-regret algorithms, but the work instead presents a direct game-solving method, rather than focusing on minimizing regret. 

Furthermore, in the introduction, the authors claim to reformulate a convex-concave problem (which is not clearly articulated) into a nonconvex-nonconcave one (also not clearly articulated) that they assert can be solved easily, though without clear reasoning. Overall, there are missing explanations throughout, making it nearly impossible for the reader to follow. Here are a few additional specific examples:

- **Line 128**: The motivation for including the additional running cost $l(u,v)$ is unclear.
- **Line 130**: The phrase “has a value” is misattributed, and the concept of "the value" is only explained later on the page.
- **Line 143**: "to have pure Nash" lacks clarity and does not seem adequately explained.
- **Line 175**: In equation 5, the expected payoff includes $V_\tau$ and $l(u,v)$, though the former represents the expected value of the terminal payoff plus the integral of the running cost $l(u,v)$.
- **Line 179**: The phrase “has a pure equilibrium” is not defined.
- **Line 179**: The sentence “If $U_\tau$ is not convex in $p$, P1…” is nonsensical.

The authors need to introduce the problem more clearly, describe its inherent difficulties, and explain how and why their proposed method is able to overcome these difficulties.

questions:
Please read the comments above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730665043888

thread_type:
official_review

<thread_object>
creator: reviewer_czpx

<content>
summary:
The paper studies zero-sum two player differentiable games with one-side information and infinite action space.
The paper shows that under some conditions (Cav u and Isaacs conditions) there exists an algorithm with complexity that does not depend on the cardinality of the action space. Experimental evaluation is provided

strengths:
Finding algorithms with better dependency on the cardinality of the action space is an important topic.

weaknesses:
The paper has important presentation issues. Someone non familiar with differentiable games has difficulty even understanding the setup. 
Moreover the authors do not make a great job at differentiating between their contributions and known results. In the reviewer's opinion the paper needs substantial rewriting.
For example, from section 3, it seems that the game is in continuous time, while the related works section speaks about cfr+ and deep CFR, which are designed for EFG. What is the exact setting considered by the paper? The theoretical grounding of the works seems to be based on Cardaliaguet (2007), which is based on different assumptions/language/theory than the works the authors cite as related works. This might be a strong point in favor of the paper (bringing concepts from another field into the computational game theory framework); however, the authors should invest more effort in relating the two. 
I even struggle to understand what the Cav u property is.

questions:
Have you considered the online convex optimization point of view of learning in EFG? There, you consider a continuous actions space (although a polytope). More in general, games with continuous actions are not unfeasible to optimize per se. How does this relate?
What exactly are your technical contributions? Theorem 1 and related lemmas seem straightforward from existing results.
Is the game continuous or discrete time? How can you adapt something like CFR to work in continuous time?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730688073805

thread_type:
official_review

<thread_object>
creator: reviewer_q83l

<content>
summary:
This paper proposes an algorithm for solving two player zero sum differential games with one-sided information under the assumption that Isaac's condition holds. In particular, the paper exploits the fact that in a one-sided imperfect information game with a finite set $I$ of payoff types and  the imperfect information is on the payoff types, the game (which originally could have an infinitely large action set) can be reformulated as a a nonconvex-nonconcave problem of size $O(I^2)$, which can potentially be much smaller than the original game size. Then, the paper introduces an algorithm called Continuous Action Mixed Strategy solver that is able to achieve approximate Nash equilibria of the game with a complexity of $O(TNI^2 \epsilon^{-4})$. The key contribution of this paper is the characterization of a class of differential games for which tractable solutions can be found even with continuous action spaces, and the accompanying analysis of an algorithm which exploits the structure of the game to compute equilibria faster than SOTA methods.

strengths:
- To my knowledge, this is the first paper that gives a framework to solve 2p0s differential games where the imperfect information is specifically about the payoff types and is one-sided in the sense that P1 obtains information about the payoff type before P2. While this seems like a fair niche class, the paper gives game examples from the literature that satisfy this condition, showing that the proposed algorithm performs well in practice and indeed shows time-invariance to increasing action sets since the underlying payoff types are invariant.
- The paper gives a thorough description and analysis of the specific class of games studied and the accompanying primal-dual reformulation. Overall a good description of why and when the proposed approach works is given, and the structure of the paper as a whole is good.

weaknesses:
- The paper gives a comprehensive analysis which crucially hinges on the assumptions of information asymmetry and a finite set of payoff types. However, there is a lack of explanation for when these assumptions are natural as well as when or how one can verify that a game lives in this class. It seems that Hexner's game is certainly an important game in this setting, but are there more game examples that can be shown to satisfy these assumptions? 
- There are a few typos in the paper (some are listed below), and the notation especially in the preliminaries are quite dense. The paper could be improved by taking more time/space to explain the notation (particularly for readers unfamiliar with differential games), perhaps in the appendix.

Typos:
- References for Diplomacy seem to be broken, displaying as (, FAIR). 
- 'tractable solve' in the last line of the conclusion is a grammatical error.
- Some typos in the references, e.g. P Cardaliaguet vs Pierre Cardaliaguet; some proper nouns are not properly capitalized.

questions:
- A question about the experiments on Hexner's game: Unless I am misunderstanding the results, the normal-form variants of Hexner's game you experimented with are all with finite $\vert A \vert$. Would there be an easy way to verify your results in a game where $\vert A \vert = \infty$ but $I$ is finite?
- Given that the games you study are of the pursuit-evasion type, would it also be interesting to study Stackelberg equilibria and algorithms to compute Stackelberg equilibria in this setup?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732564145282

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We sincerely appreciate the time and effort all reviewers have invested in evaluating our work. Their diverse perspectives have provided valuable insights that will help us improve our paper. 

We are particularly encouraged by the positive feedback from Reviewer **Q83L**, who recognized our work as the **“first paper that gives a framework for 2p0s differential games where the imperfect information is specifically about the payoff types and is one-sided”**. They also commended the paper’s **“thorough description and analysis”** and its **“good description of why and when the proposed approach works”**. Additionally, Reviewer **CzPX** noted that **“finding algorithms with better dependency on the cardinality of the action space is an important topic,”** which aligns with our core motivation and contribution.

We acknowledge that our paper addresses a complex topic at the intersection of differential game theory and computational game theory. This interdisciplinary nature may have led to some challenges in comprehension, especially for those more familiar with one field than the other. We take full responsibility for any lack of clarity and are committed to improving the presentation to make our work more accessible to a broader audience. 

We recognize the concerns raised by Reviewers **CzPX** and **Zbcv** regarding clarity and presentation. In our rebuttals, we have addressed these issues, including clarifications on the game setting, the definition of equilibrium, and the motivation behind our approach. We have also explained how our work connects differential games with computational game theory methods, and how our algorithm overcomes limitations of existing solvers when applied to games with continuous action spaces. We believe these clarifications resolve many of the reviewers’ concerns and further highlight the novelty and practical benefits of our approach.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper shows that efficient equilibrium computation is possible for a class of asymmetric-information differential games that satisfies certain technical conditions.

All reviewers had a background on learning and equilibrium computation in games. While they seemed interested in the contribution, there was consensus that the paper's presentation was confusing and not enough self-contained. These difficulties likely prevented the reviewers from fully appreciating whether the technical claims of the paper are correct. With only one reviewer weakly in support of the paper, and two reviewers confident that the paper should be rejected, a rejection decision was made.