Riemannian Manifold Learning for Stackelberg Games with Neural Flow Representations

We sincerely thank Reviewer NGCU for their thoughtful and positive review. We greatly appreciate the strengths you highlighted in our work and the constructive feedback you offered. We have worked respond to your concerns and update our document. Below is our detailed response:

What is the intuition behind mapping the action space to a Riemannian manifold? Does this approach stem from leveraging methods such as Riemannian gradient descent?

• The intuition behind mapping to a Riemannian manifold is that the game-theoretic equilibrium solution becomes easier to compute once we can characterize the follower’s best response. This effectively transforms a complex game-theoretic equilibrium computation problem into a much simpler problem of finding equilibrium points on convex subspaces induced by the leader. Deeper commentary addressing this concern is provided in General Response 3.

Is it necessary to consider a general Riemannian manifold, or is it sufficient to focus only on the unit sphere?

• The application of a Riemannian manifold is imposed more as a formality, enabling a rigorous extension of our work. Our study focuses on the D-dimensional sphere, and we propose a rigorous framework that could naturally extend to other Riemannian manifolds. For a deeper discourse, please refer to General Responses 3 & 4.

Can the authors provide a theoretical explanation of why their algorithm has advantages over previously proposed methods?

• Previous solution algorithms are often problem-specific—meaning the algorithm works only within a particular problem setting [1-B, 2-B, 3-B]—or are unable to construct a suitable feature map for a shared reward space in general. Additionally, our work addresses the challenge of building a solution framework for the multi-dimensional continuous action space, a problem with technical challenges distinct from those in previous discrete analyses.

• A key issue is the equilibrium solution. In many cases, this solution does not always have a closed form in the multi-dimensional continuous joint action space, as illustrated by Eq. (2.3) in our paper. Computationally, solving for $\pi^*_A$ is not always tractable via standard methods, which typically involve iterating over the complete best response region of the follower.

• Our work introduces the idea of bridging two seemingly disparate areas of research: multi-agent learning and differential geometry. This is achieved through normalizing flows, an enabling link introduced in recent ML literature [4-B, 5-B]. This allows us to map any ambient joint action space into a shared, tractable feature space $\mathbf{\Phi}$ with desirable properties (as outlined in Table 1, Pg. 4). For further discussion, please refer to General Responses 1 & 3.

PS we have updated our draft to the ICLR 2025 template, thanks for pointing this out.

We appreciate your encouraging and positive review of our work. If you have further questions or concerns, please do not hesitate to follow up. We would be happy to respond accordingly during the discussion period.

[1-B] Zhao, Geng, et al. "Online learning in stackelberg games with an omniscient follower." International Conference on Machine Learning. PMLR, 2023.

[2-B] Liu, Larkin, and Yuming Rong. "No-Regret Learning for Stackelberg Equilibrium Computation in Newsvendor Pricing Games." arXiv preprint arXiv:2404.00203 (2024).

[3-B] Chen, Yiling, Yang Liu, and Chara Podimata. "Learning strategy-aware linear classifiers." Advances in Neural Information Processing Systems 33 (2020): 15265-15276.

[4-B] Brehmer, Johann and Kyle Cranmer (2020). “Flows for simultaneous manifold learning and density estimation”. In: Advances in neural information processing systems 33, pp. 442–453.

[5-B] Durkan, Conor et al. (2020). nflows: normalizing flows in PyTorch. Version v0.14. DOI: 10.5281/zenodo. 4296287. URL: https://doi.org/10.5281/zenodo.4296287.

Thanks the authors for the response, and I will keep my score (which is positive).

We deeply thank Reviewer D4pN for their thoughtful and meticulous review. We greatly appreciate the positive aspects you highlighted and the constructive feedback you provided. We've strived to rectify the typos indicated, and we are optimistic that the concerns and questions have been addressed comprehensively. Here is our detailed response:

Why a spherical embedding (or any embedding) would be helpful for constructing an improved no-regret algorithm (The learned mapping is invertible so there's no dimensionality reduction)?

• The geometric properties of a spherical embedding enable us to solve for anticipative best responses without enumerating the entire action space for the follower. This significantly simplifies equilibrium computation. A similar argument could be made for any manifold with a well-defined geometry. For a more detailed commentary, please refer to General Responses 1 & 4.

It would seem the assumption of reward functions that are linear in the embedding space is critical for this approach to be strong.

• Within the framework of linear bandits and multi-agent learning, this assumption is frequently applied and perfectly valid in most learning scenarios. A detailed explanation is provided in General Response 1.

• As a minor point, [1-A] focuses on modelling MDPs, whereas our paper studies online learning in a repeated game, similar to [1, 2, 3], with extensions to multiple agents.

How might you handle Stackelberg games with discrete action spaces?

• A discrete action space implies that the image of the feature map $\mathbf{\Phi}$ is non-compact. Initially, this presents some limitations. If the degree of discretization is large enough, the discretization error would be sufficiently less than the inverse error (Definition D6 - Eq. (2.13)). This applies when we can freely select the granularity of discretization, typically used to approximate a continuous action space.

• However, if the problem is inherently discrete (e.g., each player selects from $K$ discrete actions), our framework may not be well-suited, as it is designed for high-dimensional continuous action spaces. For such problems, other solution methods, like [2-A, 3-A], are better suited. Moreover, for small discrete action spaces, standard bandit algorithms, such as independently running UCB for each agent, are computationally tractable and converge to equilibrium, as cited in [4-A]. We focus primarily on the more complex higher dimensional continuous action space problem, rather than the smaller scale discrete problem.

Additional manifolds beyond the sphere manifold would strengthen the paper as well if you can construct meaningful motivations for them.

• A deeper discussion on this point is provided in General Responses 3 & 4.

Do the reward functions in this game satisfy the linearity assumption in the chosen embedding space?

• Exploring additional manifolds is a valid extension. As the first work bridging manifold learning with multi-agent learning, we begin with a rigorous examination of the spherical manifold, which naturally extends to additional convex Riemannian manifolds. Further discussion is available in General Response 1A.

The red arrow corresponding to $\overleftrightarrow{\mathbf{\Phi}}_a$ appeared to be suggesting that $\overleftrightarrow{\mathbf{\Phi}}_b$ runs horizontally.

• Thank you for this observation. In the updated draft, we adjusted Fig. 1 to clarify that $\overleftrightarrow{\mathbf{\Phi}}_{\mathbf{a}}$ refers to a single longitudinal line, which can move freely across the sphere's surface (directed by the red arrow).

• The updated diagram demonstrates that for any given value of $\mathbf{a}$, $\overleftrightarrow{\mathbf{\Phi}}_a$ forms a red circumnavigating azimuthal great circle by varying $\mathbf{b}$. The same logic applies to $\overleftrightarrow{\mathbf{\Phi}}_b$, which varies for the small circles. We hope this update clarifies the diagram, and we welcome further suggestions.

Figure 2 / Algorithm 1: $\theta_B$ and $\theta'_B$.

• $\hat{\theta}_B$ and $\theta'_B$: To clarify, $\hat{\theta}_B$ represents the approximation of $\theta'_B$, estimated from sampling actions as the agents play $\mathbf{a}$ and $\mathbf{b}$. $\theta'_B$ represents the projection of the true objective vector onto the manifold $\mathbf{\Phi}$.

• Location of $\tilde{\theta}_A$: In Fig. 2, $\tilde{\theta}_A$ lies on the border of the orange confidence region, representing where the leader's reward outcome $\mu_A$ likely lies (with high probability) when projected onto $\mathbf{\Phi}$. Specifically, this would be the left-most intersection of the red dotted line with the orange border.

Minor Typos:

*Algorithm 1: Line 12 shows the algorithm returning an action before the for-loop completes... *

• Indeed, it should be $\hat{\mathbf{a}}^*$ and not $\mathbf{a}^*$. Regarding the "return $\hat{\mathbf{a}}^*$," the algorithm should return the optimal estimate of the action at the end of $T$ samples. We have updated Algorithm 1 (Lines 11–14) to adopt the yield operator and placed the return at the end of the loop. Thank you for highlighting this point. We hope the algorithm is now clearer.

Is there a typo? "and Eq. (2.15) and Eq. (2.16)"

• Yes, this was a typo. We intended to write: "...the linear relationship to the reward function in Eq. (2.15) and Eq. (2.16) holds..." This correction is reflected in the updated draft.

"In the Stackelberg game, since the follower moves first..."

• We corrected this typo to read: "...the leader moves first..." Thank you for pointing this out.

"Mapping to a Spherical Manifold": The sentence "The transformation from spherical coordinates to..."

• This typo was corrected to read: "...from Cartesian coordinates to spherical..." Thank you for identifying this error.

Thank you once again for taking the time to review our work. We hope the response clarifies most of the questions and concerns raised. Should you have further items for discussion, feel free to let us know and we will respond within the review period as timely as possible.

[1-A] Jin, Chi, et al. "Provably efficient reinforcement learning with linear function approximation." Conference on learning theory. PMLR, 2020.

[2-A] Colman, Andrew M., and Michael Bacharach. "Payoff dominance and the Stackelberg heuristic." Theory and Decision 43 (1997): 1-19.

[3-A] Vasal, Deepanshu. "Stochastic stackelberg games." arXiv preprint arXiv:2005.01997 (2020).

[4-A] Blum, Avrim and Yishay Mansour (2007). “From external to internal regret.” In: Journal of Machine Learning Research 8.6.

Thank you for following up on our responses and providing suggestions to add additional polish to our paper. We also appreciate your acknowledgment that our work serves as an interdisciplinary bridge across three communities (topological learning, online learning, and game theory), which presents some challenges in communicating our work across different vocabularies and definitions. Nevertheless, we believe our work is impactful precisely because it is difficult, as it bridges previously undiscovered connections between different technological domains.

We have provided a modestly revised paper, with pertinent changes highlighted in blue. To further clarify the issues you raised,

Major Components:

$\hat{\phi}^{-1}$ vs $\phi^{-1}$ given the mappings G.1:

This is a very good point. In principle, although the tooling from G.1 already provides a transform from Cartesian to spherical coordinates, it does not guarantee the properties over the manifold as enforced by the criteria from Table 1 (i.e., Lipschitzness, sensitivity, and even spreading). Therefore, without normalizing flows (NF), this causes the mapped data on the spherical manifold to be highly localized or grouped into highly sporadic clusters (we previously confirmed this in tests comparing a non-NF spherical map to an NF one). As the embedding does not cover the entire manifold as intended, this renders our solution method (from Sec. 4.3) ineffective. To reiterate, the role of the NF tooling is to make the data in the feature space evenly spread across the manifold, in addition to ensuring several ideal properties as specified in Table 1.

Algorithm 1 only accounts for a subset of the components:

Allows us to clarify each of the 3 components to our algorithm as you have identified:

• Action embedding: There is indeed an offline training mechanism that is data-independent and constructed before Algorithm 1 proceeds to run. (We updated the description in Algorithm 1 to state this before proceeding with the iterative online learning section.)

• Objective parameter estimation: Typically, the re-estimation procedure for $\hat{\theta}_A$ and $\hat{\theta}_B$ is implied as new data is observed. (Nevertheless, we updated Algorithm 1 to explicitly state a step in parameter re-estimation based on collected data history.)

• Strategy Learning: The main goal of mapping to the Stackelberg manifold is that we obviate the need for strategic learning, as the best response of the follower lies in a confined subspace that is convenient for the follower to derive (as explained in Section 4.3 and illustrated in Fig. 2). Therefore, strategy learning under uncertainty resolves to geodesic distance minimization, which is far more computationally tractable than other approaches from the game theory (such as bi-level optimization for example).

Algorithm 1 Changes: We have updated the paper, specifically Algorithm 1, to present a more comprehensive exposition of our methodology in its entirety:

We overhauled the exposition of Algorithm 1 to be more expressive, adhere to coding conventions, and explicitly add in previously missing steps (which we had assumed were obvious to the reader) in order to communicate it more clearly. Specifically:

• We explicitly state when the actions $\mathbf{a}$ and $\mathbf{b}$ are taken and rewards received ($\mu_A$ and $\mu_B$). Line 16.

• Added an initialization step for $\hat{\theta}_A$ and $\hat{\theta}_B$, and empty arrays $\mathcal{U}$ and $\mathcal{D}$. Line 4.

• We explicitly state how the estimates for the actions $\mathbf{a}$ and $\mathbf{b}$ are obtained. Lines 9, 12, and 14.

• We explicitly state the procedure for constructing $\mathbf{\Phi}$ before the online algorithm begins (Line 5), and also the procedure for re-estimating $\hat{\theta}$ as new online data arrives (Line 18).

Hello R8Sr,

We appreciate the time you’ve taken to review our work, and give invaluable feedback. However, we noticed some ambiguity in your comments that we’d like to clarify to ensure we’re responding as accurately as possible.

Firstly, could you kindly clarify what you’re referring to as “Definition 2”? It seems there may have been a slight typo, as Def. 2 does not appear in our current draft. Were you perhaps referring to Def. 2.1 on pg. 4, item D2 in Table 1 pg. 4, or Def. 4.1 on Page 6? Unfortunately, without further specification, it’s challenging for us to provide a precise response, and we want to ensure we fully address your point.

Additionally, regarding your comment on Lemma 4.1, we would be grateful if you could elaborate on what specific aspects do not make sense. It would be great if you could provide a bit more specificity here.

Feel free to share any clarifications at your earliest convenience, it would greatly help us to provide a more comprehensive response as timely as possible.

We deeply appreciate Reviewer R8Sr's insightful and detailed commentary. For certain points of contention, we have made subtle yet vital updates to our theoretical arguments. For others, we have provided a deeper complementary explanation to clarify the argumentation and justification for specific theorems and lemmas. Overall, we aim to strengthen our claims and address areas of contention. Below are our detailed responses:

It seems like the paper considers a ... bounding a form of regret as a measure of performance. However, Section 2.2 describes a procedure to obtain an embedding on the D-sphere .... It is unclear why people should do this embedding.

• Naturally, when agents know the parameters of $\theta$ and act rationally, the simple regret, as defined in Eq. (4.4) 0, is 0, as there would be no deviation from the equilibrium solution. For further clarification regarding regret and its connection to the embedding $\mathbf{\Phi}$ within the framework of linear bandits, please refer to General Responses 1 & 3.

In the simulations, the reward models seem to be linear in $\theta$ parameters automatically.

• For more clarification on the structure of the reward functions, please refer to General Response 1A. If further clarification is still required, could Reviewer R8Sr kindly specify this point further?

It is not clear how such an embedding is possible. The loss in 2.14 does not reflect that.

• The embedding $\mathbf{\Phi}$ is learned via normalizing flows [5, 6, 7] (also cited in the paper), which construct a bijective map between ambient space and the manifold. The loss component $\mathcal{L}_\phi^N$ is the loss function for the normalizing flow. Additional loss functions, outlined in Table 1 (Pg. 4), ensure uniform spreading, Lipschitz continuity, and bijective properties across the manifold. Once we map our ambient data to a well-behaved embedding space $\mathbf{\Phi}$, General Response 1 provides an argument for why $\mathbf{\Phi}$ is suitable for the linear bandit setting.

• If further clarification is necessary, the reviewer is kindly invited to specify which aspects in Lines 193–224 (in the updated draft) might still be unclear, and we would be happy to provide additional discussion.

Definition 4.2: It seems like such a manifold does not exist unless it is a singleton because any two distinct points as a subset are certainly not geodesically convex.

• We thank Reviewer R8Sr for pointing out the inconsistency in Definition 4.2. We have clarified our original intent and updated the definition. We believe this change has no impact on downstream results.

• The confusion arises from the definition of "possible." We do not mean that any subset of $\mathbf{\Phi}$ is possible; rather, we refer to all permissible subsets that geodesically convex-combine to form $\mathbf{\Phi}$. In other words, the manifold is contained within a union of convex subsets $\mathcal{S}_\mathbf{\Phi}$. Therefore, given reviewer R8Sr's feedback, we have changed the wording in our definition to:

Definition 4.2 (New - Now Def. C.2 in Appendix). Convex Manifolds: A convex manifold is a manifold where the geodesic between any two points on the manifold fall within, or constitutes, a geodesically convex set $\mathcal{S}_\mathbf{\Phi}$ (as per Definition 4.1).

Lemma 4.1: The statement does not make sense for any non-compact domain, & presented counter-example.

• The counter-example provided by Reviewer R8Sr is valid but does not impact our theoretical results, as it lies outside our intended use case. Nevertheless, we have strengthened the assumptions of Lemma 4.1 in our updated draft by adding the additional constraint of orthogonality of $\xi_\theta$ with respect to $\mathbf{\Phi}$. To restate the counter-example, arbitrarily selecting a point in $\mathbb{R}^2$ Euclidean space and projecting it onto an arbitrary convex manifold in $\mathbb{R}^2$ does not guarantee that a larger divergence angle corresponds to a larger geodesic distance.

• Thus, for Lemma 4.1 to hold, we must enforce that $\xi_\theta$ forms a vector intersecting the manifold orthogonally. This is already implied when using a unit D-sphere as the manifold of choice. We will explicitly state this in the updated draft to ensure rigour, and we have updated our draft with an updated Lemma 4.1:

Lemma 4.1 (New). Geodesic Distance and Closeness to $\xi_\theta$: Let $\Phi \subset \mathbb{R}^D$ be a manifold serving as a boundary of a convex set in $\mathbb{R}^D$. Given $\theta$, let $\xi_\theta \in \Phi$ be the point on the manifold that maximizes the dot product $\langle \theta, \xi_\theta \rangle$, and is orthogonal to $\mathbf{\Phi}$ at the point of intersection. For any two points on the manifold $\theta_A', \theta_B' \in \Phi$, if the geodesic distance between $\xi_\theta$ and $\theta_A'$ is greater than that between $\xi_\theta$ and $\theta_B'$, $\mathfrak{G}(\xi_\theta, \theta_A') > \mathfrak{G}(\xi_\theta, \theta_B')$, then the dot product satisfies $\langle \theta, \theta_A' \rangle < \langle \theta, \theta_B' \rangle$.

• We thank Reviewer R8Sr for highlighting this matter.

Lemma 4.3: The justification of this lemma does not make sense other than restating the Poincaré-Hopf Theorem.

• Reviewer R8Sr is correct in asserting that we restate the Poincaré-Hopf (PH) theorem in Lemma 4.3. However, there is more to the argument than mere restatement. We must ensure the conditions for applying the PH theorem are met and provide additional arguments regarding the cardinality of the intersecting set.

• First, we ensure that the criteria on the manifold subspace are met so the PH theorem can apply. Suppose we have a spherical manifold that is compact. The azimuthal subspaces $\overleftrightarrow{\mathbf{\Phi}}_a$ can be represented by a vector field with a fixed index, while the latitudinal subspaces $\overleftrightarrow{\mathbf{\Phi}}_b$ can be represented by trajectories of a vector field circumnavigating small circles around the sphere. For the D-sphere, the fixed index equals 2.

• By the PH theorem, the index remains constant when elevating to higher dimensions. Since we work with constrained isoplanes that do not span the entire manifold, even for orthogonal subspaces, the cardinality of the intersecting subspace must be greater than 0. We believe it is valid to merge Lemma 4.3 with Lemma 4.4, as they are part of Lemma 4.4’s constructive argument. However, we intend to maintain the current structure for this draft. Please refer to General Response 2 for additional insights into Lemma 4.3.

Once again, we thank Reviewer R8Sr for their time and effort in helping improve our paper. Should further clarification be required, feel free to ask, and we would be happy to respond.

We wanted to kindly remind you that the deadline for authors to make revisions to the manuscript is approaching soon (Nov. 27 AoE). While the discussion period has been generously extended by the ICLR committee until Dec. 2 AoE, revisions to the manuscript can only be made before Nov. 27 AoE.

We believe your initial feedback has been very beneficial in clarifying and improving upon our paper. We have already made some revisions under the suggestions from your review and the other reviewers alike, if there are any remaining concerns or suggestions that you feel would benefit from additional updates to the manuscript, we would be very grateful to hear from you before Nov. 27 AoE.

After that date, we are happy to patiently continue the discussion until the end of the discussion period to clarify questions and concerns. Thank you so much for your time and effort in reviewing our work, we appreciate it.

PS. Upon the latest revision, Definitions 4.1 and 4.2 have been moved to the Appendix, now Definition C.1 and C.2 respectively.

We thank Reviewer CJwA for their positive and appreciative review of our work. We understand that the major concerns revolve around intuitively clarifying the theoretical arguments in our paper. We believe that most of these concerns are addressed in the General Responses. To address the specific concerns:

Could the authors discuss more on the roles of Lemmas 4.1–4.4?

• The Lemmas 4.1–4.3 aim to establish rigorous properties useful for online learning in the Stackelberg embedding $\mathbf{\Phi}$. Please refer to General Response 2 for a detailed discussion of their purpose.

Could the authors explain which structures of Riemannian manifolds are essential in the proposed framework? Can this framework be applied to a space with fewer structures, such as a smooth differential manifold?

• The swapping of a Riemannian manifold for a generic smooth manifold has no direct consequences in our framework; our simple regret guarantees are derived from the spherical manifold. Nevertheless, extending our work could pose some challenges if measures of angles and distances are not well-defined. A more detailed discussion is provided in General Response 4.

We are grateful for your positive review and invite you to reach out with any further questions, and we will do our best to respond promptly.

A warm thank you once again for your positive review.

We wanted to kindly remind you that the deadline for authors to make revisions to the manuscript is approaching soon (Nov. 27 AoE). While the discussion period has been generously extended by the ICLR committee until Dec. 2 AoE, revisions to the manuscript can only be made before Nov. 27 AoE.

We’ve already made some relevant updates and clarifications addressing all of the reviewers' feedback thus far. If you have any further suggestions to revise our manuscript, we’d be grateful to hear them before the Nov. 27 AoE deadline.

We hope the updated manuscript and rebuttal will strengthen your assessment in the paper, and we'd be happy to continue the discussion until the end of the discussion period Dec 2 AoE.

We sincerely thank the AC and reviewers for their time, thoughtful feedback, and dedication to reviewing our paper. Your comments have been invaluable in helping us refine our work. Below, we would like to quickly address the AC's final notes:

Motivation for the Riemannian manifold framework: We respond that its simply not possible to obtain a manifold that satisfies the properties needed for Stackelberg equilbrium learning via a simple Euclidean map, as this does not guarantee the properties over the manifold as enforced by the criteria from Table 1 (i.e., Lipschitzness, sensitivity, and even spreading). We discussed this briefly with reviewer D4pN in the rebuttal, however perhaps it was not made super clear in the paper. Based on this review, we see the need to revise the paper to provide a more explicit explanation of this item.

Efficiency concerns: The Riemannian framework trades the complexity of the original bi-level optimization problem for the complexity of normalizing flows, resulting in a simpler optimization problem on the Stackelberg manifold. This trade-off is justified by the framework’s ability to greatly simplify the multi-agent learning process. We see that there is need to clarify this in an update to our paper.

Linearity assumption: Perhaps this was misunderstood, but the linearity assumption is not a limitation but the intention of our framework. We assume a linear relationship between the feature space and the reward space, valid assumption previously established in online learning literature [2, 3]. We then impose the smoothness and biijectivity of the feature map, via representation learning with normalizing flows. Although this may to solve all problems in multi-agent learning, we firmly believe this subsumes a vast domain of Stackelberg online learning problems, as is the focus of our work and also complimented by our empirical results.

Furthermore, the bijectivity and smoothness of the feature map, $\tilde{\phi}$, ensures that this linearity holds for any alternative feature map $\phi$. We provide theoretical proof for this through a change-of-variables argument in the rebuttal. However, we admit this was brief, and we agree that there is more of a need to clarifying this in our paper.

We appreciate the AC and reviewers for highlighting the need several areas of clarification, and we intend to make an update to address this accordingly. We remain grateful for the AC and reviewers’ insightful comments and which serve only to improve our work in the future. Thank you for your time and thoughtful engagement.

Kind regards, Authors