Exploiting hidden structures in non-convex games for convergence to Nash equilibrium
Authors: Iosif Sakos
Emmanouil-Vasileios Vlatakis-Gkaragkounis
Panayotis Mertikopoulos
Georgios Piliouras
Venue: NeurIPS 2023 poster (2023)
Keywords: Nash Equilibrium
Games
Gradient
Non-monotone VI
Natural Gradient
Precondition
TL;DR: For a non-monotone family of games, we provide novel algorithms with convergence guarantess

Abstract: A wide array of modern machine learning applications – from adversarial models to multi-agent reinforcement learning – can be formulated as non-cooperative games whose Nash equilibria represent the system’s desired operational states. Despite having a highly non-convex loss landscape, many cases of interest possess a latent convex structure that could potentially be leveraged to yield convergence to an equilibrium. Driven by this observation, our paper proposes a flexible first-order method that successfully exploits such “hidden structures” and achieves convergence under minimal assumptions for the transformation connecting the players’ control variables to the game’s latent, convex-structured layer. The proposed method – which we call preconditioned hidden gradient descent (PHGD) – hinges on a judiciously chosen gradient preconditioning scheme related to natural gradient methods. Importantly, we make no separability assumptions for the game’s hidden structure, and we provide explicit convergence rate guarantees for both deterministic and stochastic environments.

Exploiting Hidden Structures in Non-Convex Games for Convergence to Nash Equilibrium
Iosif Sakos"
Emmanouil Viaaakis-Gkaragkounis UC Berkeley emvlatakis@cs. cowubiia.acaabbaaaaaa edu
Engineering Systems and Design (SUTD) iosif_ sakos@mymail. sutd. edu. sg
Panayotis Mertikopoulos
Georgios Piliouras Engincering Systems and Design (SUTD) georgios@sutd. edu.
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP LIG 38000 Grenoble, France
panayotis www.::/sss.eetttooooossssiiaaaai
Abstract
A wide array of modern machine learning applications from adversarial models to multi-agent reinforcement learning can be formulated as non-cooperative games whose Nash equilibria represent the system's desired operational states. Despite having a highly non-convex loss landscape, many cases of interest possess a latent convex structure that could potentially be leveraged to yield convergence to equilibrium. Driven by this observation, our paper proposes a flexible first-order method that successfully exploits such "hidden structures" and achieves conver- gence under minimal assumptions for the transformation connecting the players' control variables to the game's latent, convex-structured layer. The proposed method - which we call preconditioned hidden gradient descent (PHGD) hinges judiciously chosen gradient preconditioning scheme related natural gradi- ent methods. Importantly, we make no separability assumptions for the game's ss hidden structure, and we provide explicit convergence rate guarantees for both deterministic and stochastic environments.
Introduction
Many powerful AI architectures based the idea of combining conceptually straightforward settings coming from game theory with the expressive power of neural nets. Some prominent examples of this type include generative adversarial networks (GANs) [14], robust reinforcement learning [36], adversarial training [26], multi-agent reinforcement learning in games [35, 39, 41]. and communication [4]. Intuitively, in all these cases, the ghee-the abstraction serves to provide a palpable, los--to-understand target, i.e. an equilibrium solution with strong axiomatic justification. However, from a complexity complexityttheoretit -theoretic standpoint, such targets are excessively ambitious, requiring huge amounts of data to express and compute, even approximately. Because of this, the agents' policies must be encoded via a universal function approximator (such neural net) and training this architecture boils down to iteratively updating these parameters until the process hopefully! converges to the target equilibrium.
even multi- mulli-ppayer games that include free-form natural-languse
Unfortunately, despite the ubiquitousness of these settings, the design of algorithms with provable convergence guarantees is still relatively lacking. This deficit not surprising if one considers that even the comparatively much simpler problem of equilibrium learning in finite games is hindered by numerous computational hardness [9, 10] as well dynamic impossibility results
"Equal Contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

[15, 16, 19, 24, 30, 31]. In this regard, our best hope for designing provably convergent algorithms is to focus on specific classes of games with some useful structure to exploit.
One of the most well-established frameworks of this type is the class of monotone games whose study goes back least to Rosen [37]. As special cases, this setting includes single-agent convex minimization problems, two-player convex-concal min-max games, diagonally convex N-player games, etc. Owing to this connection, there has been a proliferation of strong positive results at the interface of game theory and optimization, see e.g., [28, 38] and references therein. In our case however, the agents do not play this monotone game directly, but can only access it indirectly via an encoding layer of control variables - like the weight parameters of a neural net that outputs a feasible strategy profile for the game in question. In this sense, from a machine learning perspective. the strategies of the game are latent variables, so we can think of each player as being equipped with a smooth mapping from a high-dimensional space of control variables to the strategy space of the game. Importantly, in contrast to the control variables, the latent variables are not directly accessible to the players themselves and should only be viewed as auxiliary variables and purposes, the goal remains to find an operationally desirable control layer configuration. In this sense, the convex structure of the game becomes "hidden" behind the control layer, which entangles multiple input/control variables into nonlinear manifolds of latent variables.
all extents
As result, the convex structure of the underlying game is effectively destroyed, resulting in highly non-convex end-to-end interactions. This raises the following central challenge:
Can we design provably convergent algorithms for non-corvex games with a hidden structure in the presence of general couplings between control and latent variables?
Prior work in the area has shown that this is a promising and, at the same time, highly challenging question. In [42], the setting of hidden bilinear games was introduced and a number of negative results were presented, to the effect that behaviors, even when the game admits a hidden bilinear structure. Subsequently, [13] provided an approximate minimax theorem for a class of two-agent games where the players pick neural networks, but did not provide any convergent training algorithm for this class of games. Instead, the first positive result on the dynamics of hidden games was obtained by [43] who established a series of non-local convergence guarantees to the von Neumann max- -in solution of the game in the case of two-agent hidden strictly convex-concave games for all initial conditions satisfying a certain genericity assumption. This approach, however, only applied to continuous-lin dynamics not algorithms- and it further imposed strong separability assumptions on the representation of the game in the control layer. More recently, [32] established the first global convergence guarantees in hidden games but, once again, these apply only to continuous-timg time dynamics and a special case of two-agent convex-concave games (akin to playing a convex combination of hidden games with one-dimensional latent spaces). This paper is the closest antecedent our work it introduces dynamical system, called Generalized Natural Gradient Flow, which makes the L norm between the equilibrium in the hidden game and the current set of latent variables Lyapunov function for the system.
can exhibit a variety of non-convergent
Our results & techniques. Our paper seeks to provide an affirmative answer to the key challenge above under minimal assumptions on the coupling between latent and control variables. To that effect, we only assume that each agent is able to affect measurable change along any latent variable by updating their control variables appropriately; without this assumption spurious equilibria can emerge due to the deficiency of the control layer architecture. Importantly however, even though the map from control to latent variables is known to the players, we do not assume that can be efficiently inverted (e.g., to solve for profile of control variables that realizes a profile of latent variables). Otherwise, if could, the entire game could be solved directly in the latent layer and then ported back to the control layer. thus rendering the whole problem moot and, indced, when working with realistic neural net architectures, this inversion problem is, to all intents and purposes, impossible.
For intuition, we begin by designing new continuous-time flow, that we call preconditioned hidden gradient dynamics, and which enjoys strong convergence properties in games with hidden strictly monotone structure (Proposition 1). Similarly to [32], this is achieved by using the L norm in the latent layer as a Lyapunov function the control layer; however, the similarities with the existing literature end there. Our paper does not make any separability or low-dimensionality assumptions, and otherwise purely algorithmic: specifically, building on the continuous-tin intuition, we provide a concrete, implementable algorithm, that we call preconditioned hidden gradient descent (PHGD);
2

---

R R
softrax
softmax
s
Figure A hidden game of Rock- Tack-Paper-Seee Scissors with strategies encoded by two multi layer pereeptrons (MLPs), whose d-diennsional imput is dictated by the two players (cf. [32]). The nonlincarity of the MLP representation maps leads to highly non-convex non-concave zero-sum game. However, by employing PHGD, both players' ML.P control variables accurately identify the (1/3, 1/3, 1/3) equilibrium in the game's latent space.
this algorithm is run with stochastic gradients, and enjoys series of strong, global convergence guarantees in hidden games.
First, baseline, Theorem shows that certain averaged process achieves O(1/v)) conver- gence rate in all games with a hidden monotone structure and Lipschitz continuous loss functions. If the hidden structure is strongly monotone, Theorem further shows that this can be improved to O(1/t) for the actual trajectory of the players' control variables; and if the algorithm is run with full, deterministic gradients, the rate becomes geometric (Theorem 3). To the best of our knowledge, these are the first bona fide algorithmic convergence guarantees for games with hidden structure.
2 Problem setup and preliminaries
Throughout the sequel, we will focus on continuous N N-player games where each player, indexed by i E . = {1,.... N), has a convex set of control variables 0g E O == IRm, and a continuously differentiable loss function f - R. where θ == [[ ; Q denotes the game's control space. For concreteness, we will refer to the tuple r = (W,, O as the hase game.
The most relevant solution concept in this setting is that of Nash equilibrium, i... an action profile 0r E + that discourages unilateral deviations. Formally, we say that 0" E θ is Nash equilibrium of the base game if
(4())) S (0,;; for all 0; E W
(NE)
where we employ the standard game-theoretic shorthand (0;; 0-;) to distinguish between the action of the i-th player and that of all other players the game. Unfortunately, designing learning algorithm that provably outputs Nash equilibrium is very clusive task: the impossibility results of Hart & Mas-Colell [15, 16] already preclude the existence of uncoupled dynamics that converge to a Nash equilibrium in all games;
recently, Milionis et al. [31] established similar impossibility result even for possibly coupled dynamics (in both discrete and continuous time), while Daskalakis et al. [9, 10] has shown that even the computation of an approximate equilibrium can be beyond reach.
In view this, our work focuses on games with a hidden, latent structure that can exploited to compute its Nash equilibria. More precisely, inspired by [42, 43] we have the following definition. Definition 1. We say that the game I I(N, O, admits laten! or hidden structure if:
1. Each player's control variables can be mapped faithfully to closed convex set of latent variables Pi E X RR.:; formally, we posit that there exists Lipschitz smooth map X O -> X; with no critical points and such that cl(x: (+:)) X,
2. Each player's is loss function factors through the game's 's latent space X == II, X,
(0) fx(x (Ox))
for some Lipschitz smooth function f:: X - called the player's latent loss function.
For concreteness, we will refer to the product map x00) (x: map, and the tuple 9 = GNN, X, will be called the hidden / latent game. To simplify notation later on, we also assume that X; has nonempty topological interior, so, in particular, dim(X,) = d, S m,-
the game's representation
illustrate the above notions in two simple but not simplistic - examples below; for a schematic representation, cf. Fig. 2.

---

Control variables
Latent variables
0
X
x(0)
8 fox
R
Figure 2: Schematic representation of game with a hidden / latent structure.
Example 2.1. Consider single-agent game (N 1) where the objective is to minimize the non- convex function E(0) Σ (sigmoid(O.) - 8a )a over a dataset D = {sa). This problem can be recast as a hidden convex problem with f(x) E' (Ia sa))² and x(0) sigmoid(O).
Example 2.2. A more complex scenario involves non-convex non-concave min-max optimization problems of the form ming, maxg, Xa TCx= where X1 and X2 are preconfigured aulti-layer perceptrons (MLPs) constructed with smooth activation functions (such as CeLUs). This problem can be reformulated hidden bilinear problem by setting fi (2)) x1 Caz (2),
Before moving forward, there are some points worth noting regarding the above definitions.
Remark First, the requirement cl(x X' means that all latent variable profiles x E X can be approximated to arbitrary accuracy in the game's ' control space. The reason that we do not make the stronger assumption x() = to capture cases like the sigmoid map: x(0) = [1 + exp(
for 0 E IR, the image of is the interval (0, 1), which is convex but not closed.
Remark Second, the requirement that x has no critical points simply means that, for any control variable configuration 0 E O, the Jacobian Jac(x (0) of at & has full rank. By the implicit function theorem [23], this simply means that x locally looks like a projection (in suitable coordinates around 0), so it is possible to affect a measurable change along any feasible latent direction by updating each player's control variables appropriately. This is no longer true x has critical points, so this is a minimal requirement to ensure that no spurious equilibria appear in the game's 's latent space.
To proceed, we will assume that the latent game is diagonally convex in the sense of Rosen [37], condition more commonly known in the optimization literature as monotonicity [12]. Formally, let
gi (z) = v.fi(z) := V.. f((x)
(2)
denote the individual gradient of the latent loss function of player E W, and write g(x) (gr 9xx))(()))))) for the profile thereof. We then say that the latent game G is:
Monotone if (g(x)) g(x), x' - x) 2 0 for all x, x' EX
(3a)
Strictly monotone if (3a) holds strict inequality whenever x' + x.
(3b)
Strongly monotone (g(x') ( x' z) 2 p||2' =1|2 for some μ and all x, x'. (3c)
Clearly, strong monotonicity implies strict monotonicity, which turn implies monotonicity; on the other hand, when we want to distinguish between problems that monotone but not strictly monotone, we will say that is merely monotone. Finally, extending the above to the base game, we will say that I' admits hidden monotone structure when the latent game G is monotone above (and likewise for strictly/ / strongly monotone structures).
Examples of monotone games include neural Kelly auctions and Cournot oligopolies [5, 6, 20, 25], covariance matrix optimization problems and power control 29,,29, 38), certain classes of congestion games [34], etc. In particular, in the case of convex minimization problems, monotonicity (resp. strict/ strong monotonicity) corresponds to convexity (resp. strict/ strong convexity) of the problem's 's objective function. In all cases, it is straightforward to check that the image x -x0)) of a Nash equilibrium 0* of the base game satisfies a Stampacchia variational inequality of the form
(a(x"), x - x²) 2 for all x E X.
(SVI)
In turn, by monotonicity, this characterization is equivalent to the Minty variational incquality
(g(x), x²) > 0 for all x e X.
(MVI)

---

To avoid trivialities, we will assume throughout that the solution set X of (SVI//MVI) is nonempty. This is standard assumption without which the problem not well-posed and hence, meaningless from an algorithmic perspective.
Notation. To streamline notation (and unless explicitly mentioned otherwise), we will denote control variables by Og and 0, and we will write æ; (0:) and x(0) for the induced latent variables. We will also write m == Σ; my for the dimensionality of the game's is control space e and == E; d, for the dimensionality of the latent space X (so, in general, m 2 d). Finally, when the representation map x is clear from the context, we will write (0:) (0.( Rd xm; for the Jacobian matrix of at 0g E EG and (0) J (0,) for the associated block diagonal sum.
3 Hidden gradients and preconditioning
We are now position to present our main algorithmic scheme for equilibrium learning in games with a hidden monotone structure. In this regard, our aim will be to overcome the following limitations in the existing literature on learning in hidden games: (i) the literature so far has focused exclusively on continuous-tin
dynamics, with no discrete-time algorithms proven to efficiently converge to solution; (ii) the number of players is typically limited to two; and (iii) the representation maps are separable in the sense that the control variables are partitioned into subsets and each subset affects exactly one latent variable.'
We start by addressing the last two challenges first. Specifically, we begin by introducing a gradient preconditioning scheme that allows design convergent continuou--lime dynamical system for hidden monotone games with an arbitrary number of players and no separability restrictions for its representation maps. Subsequently, we propose bona fide algorithmic scheme which we call preconditioned hidden gradient descent (PHGD) - by discretizing the said dynamics, and we analyze the algorithm's 's long-run behavior in Section
3.1. Continuous- time dynamics for hidden games. To connect our approach with previous works in the literature, our starting point will be simple setting already captured within the model of [32], min-max games with a hidden convex-concave structure and unconstrained one-dimensional control and latent spaces per player, i.e., θ R X, for i 1. We should of course note that this specific setting is fairly restrictive and not commonly found in deep neural network practice: in real-world deep learning applications, neural nets generally comprise multiple interconnected layers with distinct activation functions, so the input-output relations are markedly more complex and intertwined. Nevertheless, the setting's simplicity makes the connection with natural gradient methods particularly clear, so as in [32], it will serve as an excellent starting point.
Concretely, Mladenovic et al. [32] analyze the natural hidden gradient dynamics
1 ae, for all i E N.
0, (O)) 00,
(NHGD)
The reason for this terminology- and the driving force behind the definition of (NHGD)- is the observation that, in one-dimensional settings, a direct application of the chain rule to the defining relation E f+ x of the game's latent loss functions yields 0e,/00; (0,) afc/Ox, so, in tum, (NHGD) becomes
Of.
0, = x((0,) Dr.
where, for simplicity, are tacitly assuming that (0.) 0.
This expression brings two important points to light. First, even though (NHGD) is defined in terms of the actual, control-layer gradients 0e,000, of r, Eq. (4) shows that the dynamics are actually driven by the latent-layer, "hidden gradients" gx(z) Off/rr; of g. Second, the preconditioner (x,) in (NHGD) can be seen as Riemannian metric on θ: instead of defining gradients relative to the standard Fuclidean metric of θ = N (NHGD) can be seen as a gradient flow relative
'The separability assumption also rules out the logit representation exp(8ia)) Eg exp(O(s) that is standard when the latent structure expresses mixed strategies in finite game.
5

---

to the Riemannian metric 91y(0) = (,,) which captures the "natural" geometry induced by the representation map x-2
From operational standpoint, the key property of (NHGD) that enabled the analysis of [32] is the observation that the 2 energy function
E(0) -
(5)
between the latent representation x = x0) of 0 and a solution x" of (SVI) (MVI) is a yapunov function for (NHGD). Indeed, a straightforward differentiation yields
1 d
E(O)
2 di || x²1 Σ i; - (a. x;) = -0xx(() -x") <
(6)
with the penultimate step following from (4) and the last one from (MVI). It is then immediate to see that the latent orbits xt)) x(O(1)) of (NHGD) converge to equilibrium in strictly monotone games.
The approach in the example above depends crucially on the separability assumption which, among others, trivializes the problem. Indeed, if there is no coupling between control variables in the game's s latent space, the equations 2; (0,) can be backsolved easily for & (e.g., via binary search), so it is possible to move back-and-forth between the latent and control layers, ultimately solving the game in the latent layer and subsequently extracting solution configuration in the control layer. Unfortunately however, extending the construction of (NHGD) to a non-separable setting is not clear, so it is likewise unclear how to exploit the hidden structure of the game beyond the separable case.
To that end, our point of departure is the observation that the Lyapunov property (6) of the energy function (0) is precisely the key feature that enables convergence of (NHGD). Thus, assuming that control variables are mapped to latent ones via general - but possibly highly coupled representation map X: + X, we will consider an abstract preconditioning scheme of the form
0: (P)
(7)
where
Us (0) = vo,4(0)
(8)
denotes the individual loss gradient of player i, while the preconditioning matrix P.( R
to be designed so that (6) still holds under (7). In this regard, a straightforward calculation (which prove in Appendix A) yields the following:
Lemma 1. Under the dynamics (7), we have
(() - -=aaxp((tt))) (x.(0))))))))))))))))))))))))))) xz)
where, as per Section 2, [(,),) E R.d.x.. denotes the Jacobian matrix of the map Xx: O - X, More compactly, letting P == θ P. denote the block-diagonal ensemble of the players' individual preconditioning matrices P; (and suppressing control variable arguments for concision), we have
È -T JP.J (x 10--r x²)
(10)
In view of Lemma 1, a direct way to achieve the target Lyapunov property (6) would be to find preconditioning matrix such that JPJ I. However, since J is surjective (by the faithfulness assumption for x). the Moore-Penrose inverse J of J will be right inverse to J, i.e., JJ+ I. Hence, letting (JTJ)* J [J we obtain:
JPJ J(JJ))+ JT JJ (JT+ -
(11)
In this way, unraveling the above, we obtain the preconditioned hidden gradient flow
0, = -P. (.. with P,(O.) = [J.(
(PHGF)
By virtue of design, the following property of (PHGF) is then immediate:
Proposition 1. Suppose that I admits a latent strictly monotone structure in the sense of (3b). Then the energy function (5) is a strict Lyapunov function for (PHGF), and every limit point 0* 0()) is a Nash equilibrium of l.
We do not attempt provide here primer Riemannian geometry; for masterful introduction. [22].

---

Figure 3: Exploiting hidden convex struc- ture in the control layer. On the left, we present the dynamics (PHGF) in the example of minimizing the simple function f(0) KL(logit(11 02))l((000)))111222 1/3, 1/6)) over e = R In the subfigure the right, illustrate the hidden convex structure the energy land- scape, from the non-convex sublevel sets of to the latent space X' = {(z1, x2) E 12 S 13.
Proposition validates our design choices for the preconditioning matrix P as it illustrates that the dynamics (PHGF) converge Nash equilibrium, without any separability requirements or dimensionality restrictions; in this regard, Proposition I already provides marked improvement over the corresponding convergence result of [32] for (NHGD). To streamline our presentation, we defer the proof of Lemma and Proposition to Appendix A, and instead proceed directly to provide bona fide, algorithmic implementation of (PHGF).
3.2. Preconditioned hidden gradient descent. In realistic machine learning problems, any algorith- mie scheme based on (PHGF) will have be run in iterative, discrete- time environment; moreover, due to the challenges posed by applications with large datasets and optimization objectives driven by the minimization of empirical risk, we will need to assume that players only have access to stochastic version of their full, deterministic gradients. As such, we will make the following blanket assumptions that are standard the stochastic optimization literature [17, 21]:
Assumption 1. Each agent's loss function is an expectation of a random function I,: x Ω TR over complete probability space (2, P), i.e., (0) (0;w)]: We further assume that:
1. ((:w)) ) is measurable in w and B-Lipschitz smooth (for all E θ and w E Q respectively). 2. The gradients of L; have bounded second moments, i.c., supase E|] V L. w]][] < M
Taken together, the two components of Assumption imply that each & is differentiable and Lipschitz continuous (indeed, by Jensen's 's inequality, we have LO; (0)2) < E[IV (0; (l*) < 3 Moreover, by standard dominated convergence arguments, (.; w) can be seen as an unbiased estimator of (6)),, that is, (0) E(V for all 0 E O. In view of this, we will refer the individual loss gradients (,I,(6; wi player é E N as the player's individual stochastic gradients.
With all this in mind, the preconditiioned hidden gradient descent algorithm is defined as the stochastic first-order recursion
01,111 = O2,t 7: P..
(PHGD)
where:
1. 0, denotes the control variable configuration of player E / at each stage f = 1,2,...
2. > 0 is a variable step-size sequence, typically of the form ii x 1/t2 for some E [0, 1].
3. P,, = ..()..) = (o..)..) (B..))) is the preconditioner of player i E A at the t-th epoch.
4. Vi. == (,L(O wxr is individual stochastic loss gradient generated at the control variable configuration 6e by an i.i.d. sample sequence We E S2 t 1,2....
The basic recursion (PHGD) can be as noisy Fuler discretization of the continuous flow (PHGF), in the same way that ordinary stochastic gradient descent can be seen as a noisy discretization of gradient flows. In this way, (PHGD) is subject to the same difficulties underlying the analysis of stochastic gradient descent methods; we address these challenges in the next section.
4 Convergence analysis and results
In this section, we present our main results regarding the convergence of (PHGD) hidden monotone games. Because we are interested not only on the asymptotic convergence of the method but also on rate of convergence, we begin this section by defining a suitable merit function for each class of hidden monotone games under consideration; subsequently, present main results in
7

---

Section 4.2, where we also discuss the main technical tools enabling our analysis. To streamline our presentation, all proofs are deferred Appendix B.
4.1. Merit functions and convergence metrics. In the variational context of (SVI)/MVI), the quality of candidate solution i is typically evaluated by means of the restricted merit function
Gape (f) = supzec (g(z), a -x)
(12)
where the "test domain" is relatively open subset of X [3]. The raison d' d'être of this definition is that, if is monotone and x² C is a solution of (SVI) (MVI), we have
(g(z), x² z) S (g(x"), x² - x) S 0 for all EC
(13)
so the supremum in (B.6) cannot be too positive if is an approximate solution of (SVI)/MVD,, is encoded in the following lemma, which, among others, justifies the terminology "merit function".
(MVI). This
Lemma 2. Suppose that is monotone. If is a solution of (MVI)/MVII, we have Gapc (i) =
whenever & E C. Conversely, if ( and is a neighborhood of & in X, then & is solution of (SVI)/(MVI).
Lemma extends similar statements by Auslender Teboulle [3] and ? the precise variant that we state above can be found in ?? J. but, for completeness, we provide proof in Appendix B.
Now, since a latent variable profile x- x(0)) solves (SVI) if and only if the control variable configuration 6 is Nash equilibrium of the base game, the quality of candidate solution @ O with x0) can be assessed by the induced gap function
Gap(O) = (x())) = (uPrrex(((x)) a xx).
(14)
Indeed, since a = x() E X. Lemma 2 shows that Gap(() 2 with equality if and only is Nash equilibrium of the base game r. In this regard, Eq. (14) provides a valid equilibrium convergence metric for I, so we will use it freely in the sequel as such; for a discussion of alternative convergence metrics, we refer the reader to Appendix B.
4.2. Convergence results. We are now in a position to state our main results regarding the equilib- rium convergence properties of (PHGD). To streamline our presentation, we present our results from coarser to finer, starting with games that admit a hidden merely monotone structure and stochastic gradient feedback, and refining our analysis progressively to games with a hidden strongly monotone structure and full gradient feedback." 3 In addition, to quantify this distortion between the game's 's latent and control layers, we will require a technical regularity assumption for the game's 's representation map X: θ + X. Assumption 2. The singular values of the Jacobian J(0) of the representation map are bounded as
min I eig eig(J (O))(( < i
(15)
for some Tmin, maxx E (0, o and for all 0 E θ.
With all this in hand, we begin by studying the behavior of (PHGD) in games with a hidden monotone structure.
Theorem 1 (PHGD in hidden monotone games). Suppose that players run (PHGD) in a hidden monotone game with learning rate 7t x 1/1//2, Then, under Assumptions and 2, the averuged process O, E x x.) enjoys the equilibrium convergence rate
E[Gaap(f)]] Ollot//V
(16)
As far as we are aware, Theorem is the first result of its kind in the hidden games literature that is, describing the long-run behavior of a discrete-time algorithm with stochastic gradient input. At the same time, it is subject to two important limitations: the first is that the averaged state 6, cannot be efficiently computed for general representation maps; second, even if it could, the Olog t/vi)
As expected, convergence rates improve along the way.

---

convergence rate is relatively slow. The two results that follow show that both limitations can be overcome in games with hidden strongly monotone structure.
In this case (SVI)/MVI) admits a (necessarily) unique solution x" in the game's 's control space, so we will measure convergence in terms of the latent equilibrium distance
Err(0) == 2 llx(() ==I??.
(17)
With this in mind, we have the following convergence results:
Theorem 2 (PHGD in hidden strongly monotone games). Suppose that players run (PHGD) in hidden p-strongly monotone game with "tt = 7/1 for some 7 > μ.- Then, under Assumptions and 2, the induced sequence of play 0r E b t == .... enjoys the equilibrium convergence rate
E[Erre(0r)) = ((1/t).
(18)
This rate tight, even for standard strongly monotone games. To improve it further, we will need to assume that (PHGD) is run with full, deterministic gradients, i.e., V2 = g(O)). In this case, we obtain the following refinement of Theorem 2.
Theorem 3 (PHGD with full gradient feedback in hidden strongly monotone games). Suppose that players run (PHGD) in a hidden u-strongly monotone game with full grudient and suffciently small learning rate 7 > 0. Then, under Assumptions I and 2, the induced sequence of converggss to equilibrium at a geometric rate, i.e.
play 0g O t 1,2,..... converges
Erre Opp')
(19)
for some constant p E (0, that depends only on the primifives of T and the representation map X-
Importantly, up to logarithmic factors, the convergence rates of Theorems 1-3 mirror the correspond- ing rates for learning in monotone games. This take-away is particularly important as it shows that, when it exists, a hidden convex structure can be exploited to the greatest possible degree, without any loss of speed in convergence relative to standard, non-hidden convex problems.
The proof's of Theorems 1-3 are quite involved, so we defer the details to Appendix B. That said, to give an idea of the technical steps involved, we provide below (without proof) two lemmas that play pivotal role in our analysis. The first one hinges on a transformation of the problem's defining vector field v(0)= = (V (O))(O)) which, coupled with the specific choice of preconditioner + in (PHGD) allows us effectively couple the latent and control layers of the problem in a "covariant" manner:
(0,) (0))
(e,) (I,
Lemma 3. Fix some â E X, and consider the energy function E(0;a) (1/2)llx(0) - =12². Then,
for all 8 E O, we have
(()) x(#) 2.
(20)
Our second intermediate result builds on Lemma and provides "template inequality" for the energy function E(A; .) in the spirit of [7, 11, 18).
Lemma (Template inequality). Suppose that Assumptions and hold. Then, with notation as in Lemma 3, the sequence E, = (1/2) (0.) - 21, t = 1,2,.... satisfies
E.+1 < E. (1) =) + no. + Tie where x2 == (0)). de = (J.O.) o(xx)) (xx. .) and w/s is random error sequence with sup, E[1h] < 00.
(21)
This inequality plays a pivotal role in our analysis because it allows us to couple the restricted merit function (B.8) in the game's control space with the evolution of the algorithm's -yapunov function in the game's ' latent space. We provide the relevant details and calculations in Appendix B.
Experiments
This section demonstrates our method's applicability in a couple of different and insightful se- tups. Technical details of those setups, well as additional experimental results are deferred to the supplementary material. We start with a regularized version of Matching Pemnies zero-sum game where the players' strategies are controlled by two individual preconfigured differentiable MLPs. Each MLP acts as the player's representation map Xs, which for each input O, outputs a uni-dimensional latent variable æ; (0.) guaranteed to lie in X; [0, 1]; the player's 's latent space.

---

Figure 4 illustrates the trajectory of (PHGD), represented by the black curve. The algorithm employs a constant step-size of 0.01 and is initialized at the arbitrary state (1.25, 2.25) in the control variables' space. The color map in the figure serves as a visual representation of the level sets associated with the proposed energy function (5), Notably, the trajectory of the algorithm intersects each of the energy function's 's level sets at most once, indicating its non-cycling behavior, which is an issue that shows up often in the equilibration task. Due to the design of our hidden maps, the stabilization at the point (0, 0) corresponds to the (xx(0), x2)) = (2) 1 2) the unique equilibrium of the game.
Figure 4: The trajectory of (PHGD) in hidden Matching Pennies game over sub- level sets of the energy function in (5)
In the second, more complex, example, we consider a strongly-monotone regularized modification of an (atomic) El Farol Bar congestion game among N = 30 players [1. 44]. In this setup, we let the control space of each player i be multi-dimennional, namely, θ = R i E N, and, as in the previous example, the representation map each player is instantiated by some preconfigured differentiable MLP whose output 2; (=().) is guaranteed to lie in [0, 1]. The MLP's output is going to be the probability with which player visits the El Farol bar. For the interested reader, further details, including technical specification of the MLPs, and loss functions of the games, can be found in the supplementary material. Figure 5 provides a comparative analysis of
10
12
10a
12
520
1535
2000
7520
1000
3500
2003
4500
5000
350
1000
Tinec
Figure 5: The evolution the 2 error function (x() (PHGD) and gradient descent (GD) with constant step-size 0.01 in the regularized games of Matching Pennies and Farol Bar as depicted a semi- logarithmic scale. In the Matching Pennics game (left) we depict single trajectory initialized at (1 (1.25,7 2.25), while in the El Farol Bar game (right) game we depict the mean and confidence bounds of 100 random trajectories.
the performance between (PHGD). and the standard GD method in the aforementioned two game scenarios. In Figure 5 (left) we explore the Matching Pennies game, where GD exhibits slightly erratic behavior. Despite eventually converging to the game's 's equilibrium point, GD's convergence rate, in this case, can be described as linear at best. In Figure 5 (right), we examine the El Farol Bar game. Interestingly, in this highly complex setup, GD fails to reach the equilibrium point entirely. In contrast, (PHGD) not only manages to converge in both of these setups, but it also consistently maintains an exponential rate of convergence. This stark difference underscores the efficacy and robustness of our algorithm.
6 Conclusion
This paper proposed a new algorithmic framework with strong formal convergence guarantees in a general class non-convex games with a latent monotone structure. Our algorithmic method which we call preconditioned hidden gradient descent relies on an appropriately chosen gradient preconditioning scheme akin to natural gradient ideas. Our class of games combines the useful structure of monotone operators as well as the notion of latent/hidden variables that arise in neural networks and can thus model numerous Al applications. Our results indicate the possibility of deep novel algorithmic ideas emerging at the intersection of game theory, non-convex optimization and ML and offers exciting directions for future work.
10

---

Acknowledgments and Disclosure of Funding
This research has been partially supported by the National Research Foundation, Singapore and DSO National Laboratories under its Al Singapore Program (AISG Award No: 1-SG2-RP-2020-016 grant SEESGP-AI-2020-00 AME Programmatic Fund (Grant No.A22H6b015)) from STAR and Provost's Chair Professorship grant RGEPPV2101, project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationFU Program, and the French National Research Agency (ANR) in the framework of the PEPR IA FOUNDRY project (ANR-23 MANR-23--PHH 23-PELA--000 LabEx PERSYVAL (ANR-II 11-LABX-0025-01) and MIAI @ Grenoble Alpes 15-IDEX-0)) the PM is also with the Archimedes Research Unit Athena RC University of Athens.
the "Investissements d' avenir" program
References
[1] Arthur, W. B. Complexity in economic and financial markets. Complexity, 1(1):20-25, 1995.
[2] Auslender, A. Optimisation: Méthodes numériques. Masson, 1976.
[3] Auslender, A. and Teboulle, M. Interior projection-like methods for monotone variational inequalities. Mathematical Progranming, 104:39-68, 2005.
[4] Bakhtin, A., Wu, D. J., Lerer, A., Gray, J., Jacob, A. P., Farina, G., Miller, A. H., and Brown, N. Mastering the game of no-press diplomacy via numan-regularized reinforcement learning and planning, arXiv preprint arXiv:2210.0 054999 2022.
[5] Beltratti, A., Margarita, S.. Terna, P., et al. Neural networks for economic and financial modelling. International Thomson Computer Press London, UK, 1996.
[6] Bichler, M., Fichtl, M., Heidekrüger, S., Kohring, N., and Sutterer, P. Learning equilibria in symmetric auction games using artificial neural networks. Nat. Mach. Intell., 3(8):687-695, 2021. doi: 10.1038/
442256-021-00365-- URL https://doi.... org/10. 1038/s42256- 821 001-00065-44
[7] Bravo, M., Leslie, D. S., and Mertikopoulos, P. Bandit learning in concave N- N-person games. In NeurlPS I&: Proceedings of the 32nd International Conference of Neural Information Processing Systems, 2018.
[8] Chung, K.-L. On a stochastic approximation method. The Annals of Mathematical Statistics, 25(3): 463-483, 1954.
[9] Daskalakis, C., Goldberg. P. W., and Papadimitriou, H. The complexity of computing Nash equilibrium. Communications of the ACM, 52(2):89-97 2009.
[10] Daskalakis, C., Skoulakis, S., and Zampetakis, M. The complexity of constrained min-max optimization. In STOC '21: Proceedings of the 53rd annual ACM SIGACT symposium on the Theory of Computing. 2021.
[11] Duvocelle, B., Mertikopoulos, P., Staudigl, M., and Vermeulen, D. Multi-agent online learning in time- varying games. Mathematics of Operations Research, 48(2):914-941, May 2023.
[12] Facchinei, F. and Pang, J.-S. Springer Series Operations Research. Springer, 2003.
Variational Inequalities and Complementurity Problems.
[13] Gidel, G., Balduzzi, D., Czarnecki, W. M., Garnelo, M., and Bachrach, Y. Minimax theorem for latent games or: How i learned to stop worrying about mixed-nash and love neural nets. AISTATS, 2021.
[14] Goodfellow, I. J., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y. Generative adversarial nets. In NIS 'I4: Proceedings of the 28th International Conference on Neural Information Processing Systems, 2014.
[15] Hart, S. and Colell, A. Uncoupled dynamics do not lead Nash equilibrium. American Economic Review, 93(5):1830- 1836, 2003.
[16] Hart, S. and Mas-Colell, A. Stochastic uncoupled dynamics and Nash equilibrium. Games and Economic
Behavior, 57:286-303. 003866333,,20 2006.
[17] Hazan, F. survey: The convex optimization approach regret minimization. In Sra, S., Nowozin, S., and Wright, S. J. (eds.), Optimization for Machine Learning, pp. 287-304. MIT Press, 2012.
[18] Hsich, Y.G., lutzeler, F., Malick, J., and Mertikopoulos, P. On the convergence of single-call stochastic extra-gradient methods. In NeurlPS '19: Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 6936-6946, 2019.
[19] Hsieh, Y.-.., Mertikopoulos, P., and Cevher. V. The limits of min max optimization algorithms: Conver- gence to spurious non criticaiicl sets. In ICML '21: Proceedings of the 38th International Conference on Machine Learning, 2021.
11

---

[20] Kelly, F. P., Maulloo, A. K., and Tan, D. H. Rate control for communication networks: shadow prices. proportional fairness and stability. Journal of the Operational Research Society, 49(3):237-252, March 1998.
[21] Lan, G. First-order and Stochastic Optimization Methods for Machine Learning. Springer, 2020.
[22] Lec, J. M. Riemannian Manifolds: an Introduction to Curvature. Number 176 in Graduate Texts in Mathematics. Springer, 1997.
[23] Lee. J. M. Introduction to Smooth Manifolds. Number 218 in Graduate Texts in Mathematics. Springer- Verlag, New York, NY, 2003.
[24] Letcher, A. On the impossibility of global convergence in multi-loss optimization. In ICLR '21: Proceed- ings of the 2021 International Conference on Learning Representations, 2021.
[25] Liu, X., Yu, C., Zhang, Z., Zheng, Z., Rong, Y., Lx, H., Huo, D., Wang, Y., Chen, D., Xu, Wu, F, Chen, G., and Zhu, X. Neural auction: End-to-end learning of auction mechanisms for e-commerce advertising. In Zhu, F., Ooi, B. C.,, and Miao, C. (eds.). KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021, pp. 3354-3364. ACM, 2021. doi: 10.1 1..11443447548.24444 103. https:/ /tttpp://ddi..oo ///o//oor////////////////oo 10/g/10.11 1145/3447548, 334177441754.. 3467103.
[26] Madry, A., Makelov, A., Schmidt, L.,, Tsipras, D., and Vladu, A. Towards deep learning models resistant to adversarial attacks. In ICLR '18: Proceedings of the 2018 International Conference on Learning Representations, 2018.
[27] Mertikopoulos, P. and Moustakas, A. L. Learning in an uncertain world: MIMO covariance matrix optimization with imperfect feedback. IEEE Trans. Signal Process., 64( 64( ())558888, January 2016.
[28] Mertikopoulos, P. and Zhou, Learning in games with continuous action sets and unknown payoff functions. Mathematical Programmingg 173(1-2):465 507, January 2019.
[29] Mertikopoulos, P., Belmega, E. V.. Negrel. R., and Sanguinetti, L. Distributed stochastic optimization via
matrix exponential learning. IEEE Truns. Signal Procesx. 65(9):2277-2299) May 2017.
[30] Mertikopoulos, P., Hsieh, Y.PP,, and Cevher, V. A unified stochastic approximation framework for learning in games. Mathematical Programming, forthcoming. 2023.
[31] Milionis, J., Papadimitriou, C., Piliouras, G., and Spendlove, K. An impossibility theorem in game dynamics, Proceedings of the National Academy of Sciences, (e0(41)x2305349122 2023.
[32] Mladenovic, A., Sakos, L., Gidel, G., and Piliouras, G. Generalized natural gradient flows in hidden convex-concave games and gans. In International Conference on Learning Representations, 2021.
[33] Nikaido, H. and Isoda, K. Note on non-cooperative convex games. Pacific Journal of Mathematics, 5: 807-815, 1955.
(34] Orda, A., Rom, R., and Shimkin, N. Competitive routing in multi-user communication networks. IEEE/ACM Trans. Neww, 1(5):14-627 627, October 1993.
[35] Perolat, J., De Vylder, B., Hennes, D., Tarassov, E., Strub, F., de Boer, V., Muller, P., Connor, J. T., Burch, N., Anthony. T.. et al. Mastering the game of stratego with model- free multiagent reinforcement learning. Science, (777(666)):990-99999
20122.
[36] Pinto, L., Davidson, J., Sukthankar, R., and Gupta, A. Robust adversarial reinforcement learning. In ICML 17: Proceedings of the 34th International Conference on Machine Learning, 2017.
[37] Rosen, J. B. Existence and uniqueness of equilibrium points for concave N-person games. Econometrica, 33(3):520-534, 1965.
[38] Scutari. G., Facchinei. F., Palomar, D. P., and Pang. J.SS. Convex optimization, game theory, and variational inequality theory in multiuser communication systems. IEFF Signal Process. Mag., 27(3):35-4, May 2010.
[39] Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M.. Bolton, A., et al. Mastering the game of go without human knowledge. nature, 550(7676)3354 2017.
[40] Singla, S. and Feizi, S. Fantastic four: Differentiable and efficient bounds on singular values of convolution layers. In 9th International Conference on Learning Reprexentations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https://opperrvvii net/ fttm/ooommdddoooi S45
[41] Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H., Powell, R., Ewalds. T., Georgiev, P., Oh, J., Horgan, D., Kroiss, M., Danihelka, 1., Huang, A.. Sifre, L., Cai, T., Agapiou. J. P., Jaderberg. M.. Vezhnevets. A. S., Leblond, R., Pohlen, T.. Dalibard, V., Budden, D., Sulsky, Y., Molloy, J., Paine. T. L., Gulcehre, C., Wang. Z., Pfaff. T.. Wu, Y., Ring, R., Yogatama, D., Wünsch. D., McKinney, K., Smith, O., Schaul, T., Lillicrap. T., Kavukcuoglu, K., Hassabis, D., Apps, C., and Silver, D. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575:350-354, 2019.
[42] Vlatakis Gkaragkounis, E.-V., Flokas, L., and Piliouras, G. Poincaré recurrence, cycles and spurious equilibria in gradient pendient--escent-ee descent-ascent for non- con-convex con-concave zero-sum games. In Advances in Neural 2019.
Information Processing Systems, pp.
12

---

[43] Vlatakis Caaaakis-Gaargkounnii..... E.-V., Flokas, L.,, and Piliouras. G. Solving min-max optimization with hidden structure via gradient descent ascent. Advances in Neural Information Processing Systems, 34:2373-2388 2021.
[44] Whitehead, D. al. The el farol bar problem revisited: Reinforcement learning a potential game. ASE discussion papers, 186, 2008.
[45] Zhang, G., Martens, J., and Grosse, R. B. Fast convergence of natural gradient descent for over-
parameterized neural networks. Advances in Neural Information Processing Systems, 32, 2019.
13

---

Organization of the appendix
A Omitted proofs from Section 3
14
Proof of Lemma 1
14
Proof of Proposition
15
B Auxiliary results from Section 4
15
B.1
Convergence metries and merit functions
15
Proof of Lemma
15
B.2 Convergence analysis and template inequalities
17
Proof of Lemma 3
17
Proof of Lemma
18
C Proofs of Theorems 1-3
19
Proof of Theorem
19
Proof of Theorem 2
Proof of Theorem 3
22
Experiments
23
A Omitted proofs from Section 3
In this first appendix, we provide the technical proofs of our results for the continuous-time dynamics (PHGF), namely Lemma I and Proposition 1. For convenience, restate the relevant results as needed.
Lemma 1. Under the dynamics (7), have
E() --0)=-hm -100//(110000000000000000000
x;)
where, per Section 2, (.,))) RRd.xm. denotes the Jacobian matrix of the map X O X, More compactly, letting P == +. P,, denote the block-diagonal ensemble of the players' individual preconditioning matrices P; (and suppressing control variable arguments for concision), we have
E =-g(<>] - (x-xx")
(10)
Proof. Observe that if we expand the dynamical system of equations in (PHGF) with respect to each individual coordinate, we have that for each player i A. for all profiles 0 θ and for all coordinates a E (1....,m;1
(6,(0)
0,0
ia P (0:)
P
(A.1)
00,3
B=1
Now, since I' has a hidden monotone structure, and due the decomposition 4,00 = f((2), we can expand the above as
d: (f(()) drw
0.. Σ
P
Ping (0:)
Σ Orar 00,3
(A.2)
8=1
Furthermore, if we expand the left-hand side (LHS) of (9) we also get
m:
B(0) = Σ
Ora
(A.3)
2i.m
14

---

where each of the summands of the above expression can also be expanded further to
d:
aza
Dia
Σ
Oza
(A.4)
00 i0
30
1=1
Putting everything together (9) follows by some trivial substitutions.
Proposition 1. Suppose that I' admits a latent strictly monotone structure in the sense of (3b). Then the energy function (5) is a strict Lyapunov function for (PHGF), and every limit point 0* of (tt) is Nash equilibrium Tf
Proof. First, observe that for any player i E .N, and 0 E O since the player's representation map X is faithful, i... (0,), is maximal rank, it holds:
J(.0))P.
(., = (3))
(A.5)
I.
That is, Ex=
E
aea or P
r. E (1,....dd d.). where oG is the Kronecker Piag(( (0,) = 6rr for 1,r
00ia 0013
delta.
Now, by Lemma
we have that:
N
0f((z)
B(0) =
pir (x.
x'a)
Dzir
1=1
0f((z)
(A.6)
x
Saa
=-(((>), x x->)
which is negative, since x² is optimizer of f. i... it satisfies the (MVT) due to monotonicity of Additionally, since g is strictly monotone, x is the unique optimizer of f. and, therefore, the above condition holds with equality if and only if r".
B Auxiliary results from Section 4
B.1. Convergence metrics and merit functions. In this appendix, we provide the technical seaf- folding required for the analysis of(HHD)) namely Lemmas 2-4 in Section 3.2. As before, we restate the relevant results as needed.
Lemma 2. Suppose that is monotone. i is a solution of (MVI) we have Gape( = 0 whenever & E C. Conversely, Gape (.) and a neighborhood of & in X, then & is solution of (SVI)/(MVI).
Proof of Lemma 2. Let & X be a solution of (SVI)(MVI) so (g(#), - a) 2 for x E X.
Then, by the monotonicity of g. we get:
(g(x), 2) S (g(x)) g(t), 2 - x) + (g((), 5 x)
(g(()) g(x), a - x) (g(i), 8) S
(B.1)
so (ă 0. On the other hand, if C, we also get Gap(ă) > (g($), 1) so we conclude that Gape(() 0.
For the converse statement, assume that Gape (+) 0 for some & C and suppose that C contains neighborhood of in X. We then claim that à is solution of (MVI) over C, i.c.,
(g(z), +)
for all C.
(B.2)
To see this, assume to the contrary that there exists some 21 E C such that
(g(21), 21 2) <
(B.3)
15

---

so, in turn, we get
(apr(#) 2 (g(xz), 8 x1) 0,
(B.4)
a contradiction.
With this intermediate "local" result in hand, Indeed, if we suppose to the contrary that there exists some 21 E X such that (g()), 21 - 2) < 0,
in position to prove that & solves (SVI).
then, by the continuity of 9, there exists a neighborhood U' of E in A' such that
(g(z),
2) O for all E E
(B.5)
Hence, assuming without loss of generality that U' H C (the latter assumption due to the assumption that C contains a neighborhood of .), and taking > 0 sufficiently small so that + X(21 -t) UI, we get that (g(x), I =) Xg(a),, #1
0, in contradiction (B.2).
We thus conclude that è is a solution of (SVI) - and hence, by monotonicity, also of (MVI).
For intuition, we discuss below some other merit functions that could be considered valid con- vergence metrics. In this regard, the first thing to note is that the definition of Gap(0) effectively goes through the game's s latent space, so it is natural to ask whether a similar merit function can be defined directly the game's control space. To do so, it will be more convenient to start with a linearized variant of Gapx defined over the cone of tangent directions at é. namely the so-called "tangent residual gap"
TGap (0) min.eme. (o(t), 2)
(B.6)
i.e., the maximum "ascent" step (-g(x); z) over all admissible displacement directions from a.* Just like Gape, this linearized merit function correctly identifies solutions of (SVI)((MVI::
Lemma B.1. For all it E X, we have xo) 2 0 with equality if and only if i solves (SVIV(MVI).
Proof: Let & E X' be some arbitrary profile of latent variables. By definition, we have that TGapx (+) = -
(9(#), z). where (f) is the tangent cone to X' at â. Ob- serve that since (C)( is cone, 0 E (+), so TGapx (8) 2 (g(()) 0) O. Now assume that (2) = 0. Then, the following are equivalent:
TGapx =0 = (e) (g(C), 2) =0
(o()), 2) 2 0 for all 2 E (T), | 1
(B.7)
(o()), 2) 20 0 for all 2 (
where the last equivalence follows because TCx(#) is cone. Rearranging the terms, we may
equivalently write (-g(#), z) < 0 for all E (T). Notice that, by the definition of the tangent cone, the latter is equivalent to (+), 2) < 0 for all z E X. Therefore, TGap ( = if and only if ē satisfies (SVI).
(z).
Now, if 0* is a Nash equilibrium of the base game, the latent variable configuration x = x(") solves (SVI)(MVI), so TGapx valid equilibrium convergence metric for I'. However, since TGap, is still defined on the game's latent space, it does not give a straightforward way of definining the quality of candidate solution directly on the game's control space. To that end, one could consider the gap function
TGap (0) - mir" Smll (v(0), 17) = ||+(0)]|-
(B.8)
where v0) =
collects the players' loss gradients relative to their control variables, and ||+||+ denotes its dual norm (so (0) is evaluated directly the game's control space). Of course, as control variables are mapped to latent variables. X introduces a certaint distortion (due to
nonlincarities). This distortion can be quantified by the following lemma (see also Fig. 6 above):
Lemma B.2. Let f x(0) for some â O. We then have
min TGap, x (t) < TGape S 6mxx TGapx(()
(B.9)
In particular, TGapo 2 for all i E O, with equality if and only if 0 is a Nash equilibrium of
'In the above, TCx (.) denotes the tangent cone to X at â. that is, the closure of the set of all rays emanating from and intersecting X' in at least other point.
16

---

J.
Oraxx (0)
||
Omin (0)
|| S Omax
||=||| S
Omin
Figure The distortion of a ball by (()).
Proof. To begin with, let us define the balls Bg = (n E R" ||vll S 1), and Bx = fa E R || S 1). Now, let 0 E ④ be some arbitrary profile of control variables. By Assumption 2, we have that the singular values of the Jacobian J() of the representation map X bounded from above and below by mmax < oo and min respectively. That is, Vmiu/|y|l S (0)( S T |l for all R", which implies that Tmin C J() S maxlxx By definition, we also have that, v(0) ((0)T = g(t), and, hence
TGaps (0)
min (u(0), nE3e
min (o(#), 2)
(B.
zEJ(0)Be
Now, recall that the set of Nash equilibria O* C θ is non-empty. In particular, since the θ R an open set, the solution set lies in an open set, which, in conjunction with the fact that the representation maps
faithful representations of θ to X, also implies that x(@") lies in the interior of X. Finally, since X is smooth, and in conjunction with the previous observations, it follows that TGape (0) = [|v( and TGapx (+) = [|g( hence it is easy to see from the above discussion that
min TGap TGapx(((0)) < (G) S max (Gapx(x(0)
(B.11)
and our proof is complete.
In view of the above discussion, the reader may wonder why not use the tangent gap TGape directly as performance metric. The reason for this is that, the solutions of (SVI)/(MVI) not belong to the image X. the dual norm of vθ) may be too stringent as a performance metric as it does not vanish near equilibrium (e.g., think of the operator g(x) for z between 0 and 1). In this case, equilibria can be approximated to arbitrary accurarcy but never attained, so the latent gap functions Gap and Err are more appropriate as performance measures.
B.2. Convergence analysis and template inequalities.
Lemma 3. Fix some ê E X, and consider the energy function E(!: (1/2) +12. Then, for all 8 E θ. we have
J F(() x(()
(20)
Proof. Let i E / be some arbitrary player, let 0 E θ be some arbitrary profile of control variables, and let 77 Rdd be some arbitrary vector. Then for each coordinate a {l...., mi), and latent profile & E X', we have that
OE(0; 8)
Oxis D0..
Σ (a. Rij))
(B.
80.m.
1=1
That is Ve, Ely; (x,)) 22). Now, multiply both sides of the above expression with P, (.().) to get
P.(O,) Vo, E(O: (o) -5:)
=J,(0,) (J,())) (O, 2:) =J,(0)) -..),
(B.13)
17

---

where in the last equality we used the fact that the i-th player's representation map Xi is a faithful representation. i.e. (+,) maximal rank. Finally, by expanding the LHS of (20), and applying the above simplification the result follows.
Lemma (Template inequality). Suppose that Assumptions and 2 hold. Then, with notation in Lemma 3, the sequence Eg- = (x/2) - 21 1,2,.... satisfies
Et+1 S E. ( (xxx -)) nh + vi.
(21)
where 2; x(0c). o, = (J(0) ( ((xr))T(Ix and 4/, is random ervor sequence with sup, E[pb]] < 00.
Proof. For each .... we expand 7+41 using its second-order Taylor approximation at 0g i.e. for each player i = ,,..., .N and each coordinate = 1...., de:
Fa,++ xu(0e+2)
= =xa(Or,)) + 7 (a((),)) 0,,11 0s,z)
(B.14)
+ (0 0, (.,,)),,, ((0,,411 0c,,),
where (O,,) is the Hessian of the latent map at some convex combination 0,,e of 0i, and 0,,+1- Then, further expanding 9c-1, we also get
Ta,++1 Zu (a.,,,)), Pa.Va.) + M.
(B.15)
Plugging the above expansion to E(0++1; 2) for arbitrary state è we get
E = E(0+41;
1 N d,
[1+11 - 2)
2 i=1
1 d.
Dst.e hu (V (a(,),,), P.,
2
(B.16)
+
N
E,
%
V Xa (B..)) P..V Fa) + 7
E, Y (J.PP.). x) + 7.m.
where the second-orde term 17, given by the formula
(0a.).) P..Ve.)
7
N d.
P.. P.N. 2a)
(B.17)
V W.l.
H..
7
18

---

For the second-order term, observe that by Assumption 2, we have that []][ = I. Using that fact, it follows that
V X..(B.).P...V.a M
(B.18)
|
Furthermore, since the representation maps Xi are B-Lipschitz smooth for some Lipschitz modulus B, we have that (0,,) 3I for each player and coordinate I. Consequently, we have that
3 --.IV
3
(O..)) & BVT &
|
(B.19)
min
o min
Let D diam(x). (x), then, by applying the Cauchy-Schwand inequality, we also get that
dDV3
d33
11t -
11
|IVE|
+
||
+ 72 σ min
VEll,
(B.20)
0
min
min
where Y sup,- 1.Pptm1,2.... 1,2... Nt and d Σ d;
Finally, let us consider the first-order term of (B.16). Let e (V)C(())))EN and gr = =(xx). Then, by definition, we also have that 1 J gt- Moreover, recall that, by construction, J,P.J] Consequently, we can write
(J.P.V)) 2) (J.P.t) (VP (x) 8)
(J... J[ 5)
(B.21)
(x: 8) (J,P.V -0 (xt 8),
which concludes the proof.
C Proofs of Theorems 1-3
We are now in a position to prove Theorems 1-3 regarding the convergence properties of (PHGD). We proceed sequentially, restating the relevant results needed.
Theorem 1 (PHGD in hidden monotone games). Suppose that players run (PHGD) in hidden monotone game with learning rate x 1/11/2, Then, under Assumptions and 2, the averaged process 02 E E xt- x.) enjoys the equilibrium convergence rate
[[[Gap(O:]] O(lot//Oi)
(16)
Proof. Let 02 E θ be some arbitrary initialization of the algorithm, and let 7 E X' be some arbitrary profile of latent variables. Next, by Lemma 4, we have that for all 2 1:
E < E, (e(g( 2) + me + 72 v.
6: = (J. g(x,)) - -)
(C.I)
1/2 V/l3, for some x > 0.
Rearranging the terms, the above is equivalent to
(g(( x - 5) S F Fx.11 + neh + 77 th-
(C.2)
Furthermore, by the monotonicity of g. we also have that (g(xz) g(ō), It. - x) > 0, and by combining the two, we get that for all >
Ne (g(g))) 2, σ) s ((() Lt -) E. E + mod + 7220..
(C.3)
19

---

Summing up the above terms in both sides of the inequality, we also get that
t
(o)))) Is -8) -
Σ
Eg -E5-1 + 7.00 + +/24//
s=1
= Ei
E1+1 +
7a0ss + Σ
2 tbs
(C.4)
a=1
s=1
< E1
YoHa +
2
Ya 8/..
s=1
Dividing all terms by 7, = E Yas also yields
(9(3), Ez - 8) (9(5),
Ya Fg x)
ft
Ts (g(#), 2g - 8)
(C.5)
E1
Σ s=1
7
Σ
90
ft
where 3; Ei=1
5e Te is the time-average.
Next, let us define the following auxiliary process that will assist us in further bounding the above expression:
1/1 = 21
1/+1 arg min [ige -W0 xEX
x|ll for all i 2,
(C.6)
where 7/2 == J(0.)) g((x)) for all E N. Observe that
No = Y (m. 24 - 2) = V/ (me V - .) + Pe da ve) for all 2 1.
(C.7)
Let us, first, focus on the former of the terms. Notice that for all / 1, write
ne Dr - 5) = Yo (e, ye+1 - Φ) + Velee Dc Ve+1)-
(C.8)
Furthermore, by the optimality of yt++1 2 have also have that
(M++1 - + Tel Dr+1 z) S O.
(C.9)
That is, (T,, Vi+1 Σ) S (yr yt+1, Vt-1 Z).
Let us also recall a couple of useful quadratic identities, namely, we have that 1yx 111 = |I - yt
2 I| 1 112 + 2(yr+ 1++1, Ut-1 .) /e++1 -1]2 and || (yr yt 1
Ve+1
7 Ind 1|2 (T, De 1++1) + 11 De+i Then, in conjunction with the above, we get that for
all t 1:
To Te, Be - 8) = Tillss Vt+1 - σ) + 7e( 8/+ 11++1
< (y) 1/t1, Ut+1
Σ) + Te Tel 21 11++)
1 21|2
2 |1y141 -112-
lreee (vi 11+1)11 7 2
|nd1 (C.10)
2 || l|
$ 1 x
2 |1
=112
20

---

Finally, summing both sides of the above inequalities, we also get that
1
(ee Ys 2)
1//=
x1
2 Me+1
=1
+
2 >
nell
11
2 s=1
1
1 Σ
2
-i12-
Ilue+1
7
1|
2
1
2110
91
31
7/ 1ll111
(C.11)
2
1
1
2 || - 3
7 |m 1|
2
Ei
2 nall
With the above established, let us reconsider the quantity (g(Ø), Hz - z). Specifically, due to the above derivations, we have that for all 1:
E1
EBm1 7sQ=
15m1 12.
(0(5), F2 - x) <
%tt
7t
E1
E'= ?.80
+
Yo me Ye - -3)+ +
me, D1 - --y) +
%/
71
7t s=1
%t
==1
3E1
1
1
11
+
2t (1t, T2 - y1) +
7 ViV&
25
2%
%/
% a=1
a=1
s=1
Considering the mean of supremum over ā E X' of the LHS, we end up with
E sup (op()) Fe- - a)
3F
1
K
22
SEX
25
2
s=1
3E1
2
RM²
2
2
7
24
7t 8=1
7t
3F,
M
(C.12)
+ (1 + R)
2
27
0
2 Fite
= Olog /oogt//o t/vi),
where the last inequality is direct consequence of the bounded second moment of the stochastic gradient in Assumption 1
Theorem 2 (PHGD in hidden strongly monotone games). Suppose that players run (PHGD) in hidden p-strongly monotone game with ?tt = 7/t for some y > μ.. Then, under Assumptions and 2, the induced sequence of play 0 E O, t t= 1,2, .... enjoys the equilibrium convergence rate
[[Erre(00) = O(1tt).
(18)
Proof. Let 01 E ④ be some arbitrary initialization of the algorithm, and let 7 2 1 be arbitrary. 2n Since the map is j-strongly monotone, we have, by the definition of strong monotonicity, that
(g(2z), Fe x²) 2 u||= 211 for all X.
(C.13)
21

---

Next, by Lemma 4, we have that for all t 1:
El+1 I E, - (el - 8) + n + + 1..
Φ: (J.).) (((x)))(ar)) 8)
(C.14)
1/ = x|[Vill, for some K > 0.
That is
Es+1 S E: - - - x 1= _ + Not + 1/
= Fr - 2 F. 7e + 1/+
(C.15)
(1 Ex + 7op + T/.
Let 74 (0, ,,...,,t f} be the history of play up iteration t. In expectation, it follows from the above that, for all 2 1:
E E < (1 2pmn)) E| + 7tt [[ + 7² [B[bb]]
(C.16)
(1 2pmnr) E| + > Eide [eel]
+ 22 E Hal]
Note that dt is H4-measurable; hence, we have that
Blo Hi] = (J(O.) B[V Hi. (x+)) (xxe (xt - 2)) (J())))(0))(())) g(2()) "(xee 2)
(Ite 8)
(J)()))())))(()) 9((z)) (
(C.17)
(g(x+) - g0)))(())))))))))))())))))) (()) (aa-
Furthermore, since, by Assumption 1, we have that |/ 2 H4] S M2, it also holds that
Ei H.] |/I H.] S xM²
(C.18)
Next, by some simple substitutions, we have
E E $ (1 - 2prr)
E[E,] + KM22?
= (1 2pr7
xM2₂²
(C.19)
E E
t
Finally, since y > 24² we may apply Chung's lemma [8] get that, for all t 1:
E E[E < x 1
+ + )
(C.20)
2μ0 - t
Theorem 3 (PHGD with full gradient feedback in hidden strongly monotone games). Suppose that players run (PHGD) in a hidden y-strongly monotone game with full gradient feedback, feedback, and suffciently small learning rate y > 0. Then, under Assumptions I and the induced sequence of play 0, E e 1,2 converges to equilibrium at a geometric rate, i.e.
(f) Oppt)
(19)
for some constant p E (0,1) that depends only the primitives of and the representation map X-
Proof. Due to the absence of randomness, and therefore the absence of noise, Lemma 4 may be simplified
E S E, (x(g(()), - xx) + 1
(C.21)
for constants 0, where vi (V.l(..)))
Let be the modulus of Lipschitz continuity of the gradients v; =(O0)) and / be the modulus of the strong monotonicity of g. Recall that, by Assumption 2. we have that the singular
22

---

values of the Jacobian (() of the representation map are bounded from above and below by
max OC and min 00 respectively. Therefore, since 8t is S-Lipschitz, follows that
8
|1e v0 S 110 1- S
x² x=1
(C.22)
min
In conjunction to the above, we then also have
Ei+1 S E. (gg((z)) It - x²) + Ni |lee|1
= Er (-(((((()))) It - x²) + NY2 1 - 11
kr/33²
s Ex 17/5 || x²11²
|| x=1
min
(C.23)
= Frt Pr + 2n77 132 Ex
0 min
2k²7 182
Ec 1 - phy +
σ min
Restricting >/ such that
2
- M7 +
(C.24)
min
2n,
minl 8x,32
we finally have that, for the choice of 7t- = =
holds
E4 = ( where == (1
30 30 min!4
<1.
(C.25)
32x,32
Leveraging the equivalence of Erre (0:) and (x+x = F., completes the proof.
D Experiments
This section demonstrates the method's applicability in series of different applecations. Along with revisiting the established examples of Section greater detail, we also present how the PHGD method performs in a couple of additional settings of interest. We begin with high-level description of the common test suite, and afterward, we move to the definitive details each of the presented applications.
In each example, we define a base game among two or more players V = (1...., Each player i control m-ddimensional vector of control variables 0; E RT. which they feed in an individual differentiable preconfigured MI.P with two hidden layers that act as the player's representation map Xi 1 - X. The dimensions of each layer of the MLPs vary among the different examples. However, the MLP's output x; = (6.) is guaranteed to be a representation of discrete probability distribution among the player's s actions in some normal-form game, c.g., a Rock-Paper-Scissoon game. The actual latent game G of I, is given by the "hidden" loss functions f: X + IR, i N. Each loss function fi is regularized variation of the aforementioned normal-form game, tuned by some # --strongly convex regularizer (z) = / ((E unique equilibrium point. The modulus is a hyper-parameter, which we tune such that the vector field gzx) = (Vz, f((z)) rex- to be strongly monotone, and to avoid finite-pree precisioe numerical errors, which can potentially arise during the computation of z.
x; l)?). where x" is the normal-form game's
2
A Hidden Game of Matching Pennies. As a first example, we revisit the two-player hidden game of Matching Pennies we introduced in Section 5. Here, each player's i control variables 6, are uni-dimensional, and are fed to each player's individual MLP given by the representation maps
(0,) = sigmoid (2) (a)) ..)) for all i = 1,2,
(D.1)
where a;; E [- are randomly chosen. Although the definition of the activation functions sigmoid R + [0, 1], and CeLU R + (-1, oo) are widely common, give them below for reference; that is:
(1) (2)
sigmoid(z) (1 exp(-z))
(D.2a)
23

---

4
0.9
3
0.8
2
1
0.6
0
0.5
-1
0.3
3
0.2
4
5
0.2
0.4
0.5
0.8
(a) trajectory of PHGD in regularized game of Matching Pennies over the levele of the energy function (5). The trajectory depicted with reference, both, space of control variables (left), and the space of latent variables (right). Notice that trajectory crosses each sub-level set the energy function, at most, once, indicating that the function's 's value is monotone along the trajectory.
0.9
3
2
0.7
0.6
0
0.4
0.3
3
0.2
5
0.2
0.4
0.6
0.8
(b) trajectory of GD in regularized game Matching Pennies over the sub-levels energy function in (5). The trajectory depicted with reference, both, the space of control variables (left), and the space of latent variables (right). Notice that the trajectory crosses each sub-level set of the energy function multiple times indicating that the function's 's value is not monotone along the trajectory.
PGD
GD
10a
10.5
10:30
10:15
500
1000
1500
2000
2500 Time (f)
3000
3500
4000
4500
5000
(c) The distance of x to the latent game's equilibrium point x² ( 3) along similar trajectories of PHGD and
GD in a regularized game of Matching Pennies. The distance is depicted in logarithmic scale in order to reveal the exponential rate of convergence of PHGD.
24

---

Ce) = max(0, + min exp(x) 1}.
(D.2b)
In this, and the following examples, without any loss of the generality, we deliberately set the bias of each of the MLP's hidden layers to zero, in order for the base game's 's unique equilibrium to lie in 0* = 0, and to simplify the notation. Each of the MLP's output I, = x(O)) is the i-th player's probability of playing Heads in a regularized game of Matching Pennies, given by the loss functions
(xx (2)) (2x, 1) (2xg 1) + h (x))
(D.3)
The latent game's unique equilibrium, in this case, is at x= x(0)) (2
In this particular example it is possible visualize the trajectories of PHGD and gradient descent with reference, both, the space of control variables R²² and the space of latent variables [o, 1J2. In Fig. 7a we depict the trajectory of PHGD, with step-size 0.01, in the above game, initialized the arbitrary state (1.25, 2.25) with respect to, both, the space of control variables (left), and the space of latent variables (right), over the sub-level sets of the energy function (5). A similar trajectory of the GD algorithm is depicted in Fig. 7b. Observe that the PHGD's s crosses the sub-level sets of the energy function at most once until it asymptotically reaches the game's equilibrium point at 0", as opposed to the trajectory of GD, which exhibits an erratic behavior. In particular, as is depicted in the semi-log plot in Fig. 7c, PHGD converges to the game's 's equilibrium point at an exponential rate as opposed to the rate of GD, which, at best, can be described as linear.
A Hidden Game of Rock- Pack-Pappe-Ssiisoos. In the next example we consider a regularized hidden game of Rock-Paper-Seisson
between two players. In a standard Rock-Paper-Scisson game each player may choose among three strategies, namely, Rock, Paper, or Scissors. No strategy dominates over the others, with Rock ruling over Scissors, Paper ruling over Rock, and Scissors ruling over Paper. In this example, each player i controls a 5-dimensional vector 0; E F of control variables, which, once again, they may feed their individual differentiable preconfigured MLP, whose output I, = (0.) lies in the 2-dimensional simplex that encodes the space of probability distributions among the three strategies of the latent game. The two MLPs are given by the following representation maps:
(O,) = softmax (A x CALU(A,)) x 0,)) for all = 1,2,
(D.4)
where the matrices A E |1,, and A!30) [-1, are random, and the activation function CeLU RR-- + (o), given as in (D.2b), is applied pair-wise. The definition of
softmax: Rd + Ad-1, where A is the - (d-1)-dine dimmenssio simplex is given, for reference, by
exp(x,)
softmax, (x)
for all j = I....,d. d.
(D.5)
Ed exp(#*)
In this case, the latent game's loss functions are given by the following polynomial system of equations, whose unique equilibrium lies at the uniform distributions xi i= 1,2:
(x)) = (3 3)
h1x)=
-I -I + 2z. where A
1
0
-1
(D.6)
1
Although, in this example, is not possible to visualize the trajectories of PHGD and GD in the space of control variables due to the large dimensionality of the base game, we may still get a glimpse of the trajectories' behavior in the space of latent variables. Fig. 8a depicts an arbitrary trajectory of PHGD with step-size 0.01, as it evolves in the simplices of the two players. Notice, that the trajectory, clearly, converges to the equilibrium initialization point, is depicted in Fig. 8b. In this case, the erratic behavior of GD is more apparent than in the previous example, A more in-depth comparison of the algorithms in the current setup is depicted in the semi-log plot of Fig. 8c, where we visualize the mean distance, and confidence bounds, to the equilibrium point across 100 random trajectories of the two algorithms. Observe, that PHGD exhibits exponential rate of convergence, opposed to the linear rate of GD.
the latent game. A trajectory of GD, with the same step size and
A Hidden Shapley's Game The next game we are interested in a hidden Shapley's 's game. The standard Shapley's 's game is a two-player normal-form game with payoff matrices:
0 5
3 1
07
A
3
1 0
and
B =
0
- 8
1
(D.7)
3
1
0
-3
25

---

(a) A trajectory of PHGD in regularized game of Rock-Paper-Seisorrs depicted in each player's dimensional simplex of latent variables. Notice that the trajectory converges to the latent game's equilibrium point z".
(b) A trajectory of GD in regularized game of Rock- Rock-Paper-S Sciper-Siisoor as depicted in each player's 2-dimensional simplex of latent variables. Notice that the trajectory exhibits erratic behavior.
PGD
109
10:10
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
Time (()
(c) The mean distance and confidence bound of z to the latent game's equilibrium point x* along similar trajectorics of PHGD and GD in a regularized game of Rock-Paper Par---Ppppssssooo The distance is depicted in logarithmic scale in order to reveal the exponential rate of convergence of PHGD.
26

---

PGD
GD
100
10
1000 2000
3000
4000
5000 Time (f)
6000
7000
8000
9000
10000
Figure 9: The mean distance and confidence bounds æ the latent game's 's equilibrium point x: along similar trajectories of PHGD and GD a regularized Shapley game. The distance depicted in a logarithmic scale in order to reveal the exponential rate of convergence of PHGD.
for some B E (0, 1). The setup of this example is quite similar to the one in the previous example. However, there few noteworthy differences. To begin with, the hidden Shapley's 's game is not zero-sum game. Specifically, the latent game's 's loss functions are given by the following polynomial system of equations:
fi(z) = - A2 + h0.2(x))
(D.8)
fz(z) = B + ho.2(x).
As in the hidden Rock Rock-Paper- Paper--ciisonee Scissors game, this game's unique equilibrium also lies in x xx() = (3. 3: t) 1, A second difference the small modulus, l 0.2, that we choose for the strongly-come convexx regularizer of this game. In Fig. we depict semi-log plot of the mean performance of PHGD and GD in the above game constructed using the same parameters as in the case of the hidden Bock-Paper-Scisson game. Notice that although the behaviour of PHGD is similar both games, the confidence bounds of GD are drastically larger in the current example.
PGD
10a
10
100
200
300
400
500
600
700
800
900
1000
Time
Figure 10: The mean distance and confidence bounds of x to the latent game's equilibrium point x along similar trajectories of PHGD and GD in regularized El Farol Bar game. The distance is depicted in logarithmic scale in order to reveal the exponential rate of convergence of PHGD.
A Hidden El Farol Bar Game. As final example, we are going to revisit and describe the details of the hidden El Farol Bar game we introduced in Section The Farol Bar game a famous congestion game that is often described as a game between populations. However, in this example, we are interested in its atomic N-playe variant. given the option of visiting a specific bar in El Farol, and the outcome of the game is determined based on the number of players that decided visit the har. From the perspective of the player, there three possible situations they may encounter, which carry some respective payoff. If the player
the standard Farol Bar game each player
27

---

decides to do not to visit the bar, then, independently of the number of bar tenants, the player receives a payoff S. On the other hand, the player decides visit the El Farol bar, then depending on how crowded the bar is, they may receive payoff that is strietly smaller, or strictly larger than S. If the bar crowded, i.e., more than C 2 0 other players have visited the har the same time, then each of them receives payoff B < S. However, if the bar is not crowded, i.e., the total number of tenants less than C, then they receive payoff > It's not difficult to verify that the El Farol Bar game has unique mixed Nash equilibrium, where each player chooses to visit the bar with probability N-
We are going to consider a hidden variant of the above game among N 30 players. Each player i controls 5-dimensional vector of control variables 0; E IR', which feeds to individual, differentiable, and preconfigured MLP. The MLP's output 2; (+,) is guaranteed to lie in [0, 1] and is interpreted as the probability of player i visiting the El Farol bar. Regarding the MI.P configuration, we follow a similar structure as the previous examples. Specifically, the representation maps R + [o. 1] are defined as
(e:):) sigmoid (a. (2) -CLLU(A x 0:)) for all == 1,2,
(D.9)
where A!")) E 1-0.85, 0.85]*x6, and a; E [--1, 1] are randomly chosen. The additional restriction to the domain of A reduces the chance for over-flow numerical errors of the sigmoid activation function. The activation function CeLU
+ (-1, oo) given in (D.2b) and applied
pair-wise to the output of A(")) 0,. The loss functions of this game follow the standard variant's definitions, namely, we have that
S xz G G-S+P f1(x) S
+ ho.5(x) for all i N, (D.10)
inj
and the latent game's unique equilibrium is at x i
The large dimensionality of the above game prohibits the usage of a detailed visualization as opposed to the previous examples. However, sufficient information about the behavior PHGD, and GD can be gathered by the performance log-plos across 100 random trajectories in Fig. 10. Observe that, regardless of the increased number of players, the behavior of PHGD is unaffected, i.e., it converges to the game's equilibrium at an exponential rate. On the other hand, the GD fails to converge in the game's s equilibrium. In fact it eventually maintains constant distance from unable procceed further; an indication of a cycling behavior.
28


Reviews:
[{"review_id": "YM0Dz1MW28", "reviewer": "Reviewer_cb9a", "summary": "This paper studies a hidden preconditioned stochastic gradient descent method for finding Nash equilibrium in games with hidden monotone structures. It demonstrates non-asymptotic convergence bound of the proposed algorithm. The complexity bound of the hidden monotone game matches that of monotone games. The topic is very interesting as it provides a way to handle non-monotone stochastic games, which motivates me to read in details. Overall, it is an interesting paper. However, the presentation quality needs serious improvement. It is hard to judge the correctness with so many typos.", "questions": "P2 Line 77, the \"[]\" should be deleted. \n\nP3 Line 99, Here $F$ is defined over $\\theta$. $F$ is later defined over $x$. Making it super confusing. Although $F$ is represent $l$ here, later $f$ is also used to denote $l$. Another notation $L$ is used to denote the stochastic counterpart of $l$. And then $f$ is used to denote a stochastic counterpart of $L(\\chi)$. Please read these notations to see how confusing they are.\n\nP5 Line 195, it is unclear why $P$ is defined over $\\theta_i$ rather than $\\theta$. \n\nP5 Lemma 1, what is a hidden smooth structure? What assumptions are exactly needed on $F$ and $\\chi$ function to ensure the format of $P$. \n\nP6, in Lemma 2, I suppose $\\chi(\\theta)=x$ by definition? \n\nP6 Line 230, about the statement for the first moment is totally wrong.\n\nP6 Line 238 & 239, $f_i$ is previously defined for deterministic function. Now $f_i$ becomes a random function. \n\nWhat is exactly the algorithm that one should run? I suppose that one should run PHGD with $\\hat g_{i,t}$ defined by $L$ rather than $f_i$ right?\n\nLine 308, there should be a space between \"games\" and \"This\".\n\nLemma 6, the notation is broken. \n\nEquation (C.5j) missing 1/2 in the third line.\n\nThere are many mismatch notations in the main context and the appendix.\n\n", "limitations": "The motivation for using the method is not adequately discussed. Some more explanation on the limitation of some assumptions is definitely welcomed. ", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "The motivation of the hidden gradient descent design is clear. \n\nThe convergence rate result for hidden monotone stochastic games seems to be new and matches the optimal complexity bound for stochastic games.\n\n\n", "weaknesses": "The presentation of the paper is poor with lots of typos. Without the Errata provided by the authors in the Appendix, when reading the main context for the first time, I found many mathematical mistakes. After reading the authors own corrections, there still remain many typos, making it hard to understand. The notation system is very confusing. I have tried my best to go through the proof. The overall idea seems correct but I cannot guarantee details. See more comments below. \n\nThe examples used to motivate the problems seems to be too simple. Example 2.1 is too simple. Example 2.2, it is unclear why one does not first solve the bilinear problem and find a corresponding mapping, which is not even needed actually. The example provided in figure 1 does not really need a neural network to approximate the probability space. \n\nFor Assumption 1, the paper claims that $\\theta$ and $x$ does not need to be within the same space, i.e., the dimension of them can be different. I wonder if $\\Theta$ is the whole space on $R^m$ and if $\\mathcal{X}$ is the whole space on $R^d$. Please specify the conditions for the Jacobian has positive and finite minimal and maximum singular values when $m\\not=d$.\n\nPlease give more concrete examples when the Jacobian can be exactly computed as required in the PHGD algorithm. If the Jacobian can be exactly computed, why one does not solve the hidden problem to optimality first and then find a mapping from control to optimal decision directly?\n\nMissing literature: there exists some literature on hidden convex structures in optimization and reinforcement learning with non-asymptotic convergence guarantee. The hidden gradient descent also appears previously. See literature [1-2] and reference therein. \n\n[1] Zhang, Junyu, et al. \"Variational policy gradient method for reinforcement learning with general utilities.\" Advances in Neural Information Processing Systems 33 (2020): 4572-4583.\n\n[2] Chen, Xin, et al. \"Efficient Algorithms for Minimizing Compositions of Convex Functions and Random Functions and Its Applications in Network Revenue Management.\" arXiv preprint arXiv:2205.01774 (2022).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your input. Before our point-by-point replies, we would only like to respectfully point out a potential misunderstanding: the fact that the latent structure may be known to the players does not imply that the problem can be solved in the latent space and the solution transferred back to the control layer. Specifically, even if $\\chi$ is known (and its derivatives computable), it may still be computationally hard to invert it, so mapping latent variables to control variables is, in general, not possible. We detail this issue in our replies below.\n\n\n1. **The [paper has] lots of typos.**  \n    \n    We spotted a number of typos in our original submission, which we fixed in the supplement (cf. Erratum in Appendix A). We trust that our replies below will clear up any remaining confusion.\n\n\n2. **Example 2.1 is too simple.**  \n    \n    This only served as a gentle start to ease the reader into the model, hence its simple (but not simplistic) nature.\n\n\n3. **Example 2.2, it is unclear why one does not first solve the bilinear problem and find a corresponding mapping.**  \n    \n    Inverting $\\chi$ might be an intractable problem, as hard (or harder) than the original game. Since the aim is to find a solution in $\\theta$, solving in $x$ and then inverting is not a viable approach.\n\n\n4. **Figure 1 does not need a neural network.**  \n    \n    This was only meant to illustrate a standard simple example in the spirit of Mladenovic et al. We will add a pointer to clarify.\n\n\n5. **I wonder if $\\Theta$ [and $\\mathcal{X}$] is the whole space. [...] Please specify the conditions for [the singular values of] the Jacobian.**\n\n   The simplify the presentation, we assumed that $\\Theta = \\mathbb{R}^{m}$ from the second line of Section 2. By contrast, the latent space $\\mathcal{X}$ **need not be** all of $\\mathbb{R}^d$ (and, indeed, in many cases of interest, it isn't).\n   \n   For the singular value requirement for $\\chi$, this is a mild topological condition: for example, if $\\chi$ is a linear map, this simply posits that it has full column rank. The general case is the nonlinear version of this requirement, namely that $\\chi$ can be uniformly approximated at each point by a full-rank linear map.\n\n\n6. **If the Jacobian can be computed, why not solve the hidden problem and then find a mapping from control to optimal decision?**  \n   \n   Even though the Jacobian can be computed exactly, this does not mean that $\\chi$ can be inverted. As a toy example, let $\\chi(\\theta_1,\\theta_2) = \\log\\left[(1+\\theta_2^2)e^{\\theta_1} + (1+\\theta_1^2)e^{\\theta_2}\\right]$: the Jacobian is trivial to calculate, but the inversion $\\chi(\\theta_1,\\theta_2) = x$ can be very hard to compute. The difficulty of inverting $\\chi$ scales exponentially in $m$ and $d$ so, in general, backsolving is not a feasible approach.\n\n\n7. **[Missing literature]**  \n\n    Thanks for bringing these papers to our attention. We will certainly discuss them, but we should also stress that our primary focus and results are notably distinct from these references.\n\n    On [1]: hidden games can indeed serve as a model for expressive neural nets. However, Assumption 4.1 of [1] stipulates the invertibility of the policy's hidden map, an assumption that we explicitly avoid. [Inverting a function represented by a neural net can be computationally prohibitive, whereas the Jacobian is typically available in closed form).\n\n   On [2]: Assumption 2.1(b) in [2] calls for the hidden map to be non-decreasing across segments of hidden parameters. This is an inherently one-dimensional consideration, while our model has been explicitly designed to treat high-dimensional problems.\n\n\n8. **L99: $F$ is defined over $\\theta$ [and later] over $x$.**  \n\n    Please disregard L99, this was a typo; see L144 for the proper definition as the pseudo-gradient of $f$. As for $\\ell$ and $f$, since we introduce stochasticity after defining them, randomness was implied from the context. We will update notation to make this clear.\n\n\n9. **L195, it is unclear why $P$ is defined over $\\theta_i$ rather than $\\theta$.**  \n\n    $\\mathbf{P}_i$ should involve only the control variables of player $i$; otherwise, each player would have to know everyone else's control variables.\n\n\n10. **Lemma 1: what is a hidden smooth structure? What assumptions are needed on $F$ and $\\chi$?**  \n\n    Apologies, \"smooth\" should read \"monotone\". Other than that, Lemma 1 was only stated as a stepping stone to achieve the desideratum right above and to derive the form of $P$.\n    \n\n11. **In Lemma 2, I suppose $\\chi(\\theta) = x$?**  \n\n    Yes - cf. Fig. 1, the \"Notation\" paragraph at the end of Section 2, the beginning of Section 3, etc.\n\n\n12. **Line 230, about the statement for the first moment is totally wrong.**  \n\n    Yes, this statement was incorrect; please see the Errata in Appendix A.\n\n\n13. **Lines 238 & 239, $f_i$ is previously deterministic. Now $f_i$ becomes random.**  \n\n    To lighten the notation, we treated $f$ as a variadic function, taking an extra stochastic argument when needed. We did this to minimize notational clutter, but we realize the confusion, so we will correct this in the revision.\n\n14. **One should run PHGD with $\\hat g_{i, t}$ defined by $L$ rather than $f_i$ right?**  \n\n    Yes, the second equality in L239 was only intended as a reminder.\n\n\n15. **Lemma 6, the notation is broken.**  \n\n    This was fixed in the Erratum (App. A).\n\n\n16. **The motivation for using the method is not adequately discussed.**  \n    \n    As we explained above, the motivation is straightforward: knowledge of the hidden structure map $\\chi$ does not mean that it is possible to invert it. PHGD retains all the good convergence properties one could expect in the latent, monotone space, without needing to solve a computationally prohibitive nonlinear system.\n\n\n17. **{Minor typos}**\n\n   Thank you. We will fix them all in the revision.\n\n\nThanks again for your input and please let us know if any of the above is not clear."}, {"review_id": "KoRz2pSxHh", "reviewer": "Reviewer_hHrj", "summary": "The paper focuses on studying non-convex games with hidden structures, where latent variables can be seen as a function of control variables and are decoupled. The authors propose a discrete algorithm called Preconditioned Hidden Gradient Descent (PHGD) to exploit the hidden structure and achieve convergence to Nash equilibrium. The method establishes a connection with natural gradient methods through the selection of gradient preconditioning schemes. The paper provides the first discrete convergence analysis on hidden convex concave games and extends the separable assumption to a more general multi-player setting. Convergence is proven under minimal assumptions, both in deterministic and stochastic environments.", "questions": "- Preconditioning method and its relation to natural gradient: The authors claim that \"a judiciously chosen gradient preconditioning scheme bears an unexpected connection to natural gradient method\". However, the connection has not been well explained in the main context. What is the literature of the preconditioning method? Why is the previous natural gradient approach not seen as preconditioning?\n\n\n- Technical difference in extending to the multi-dimensional case: What are the main technical differences or challenges encountered when extending the approach to the multi-dimensional case?\n\n- Minor issue regarding notation: In Line 195, where $P_i(\\theta_i)$ appears before introducing what $P_i$ represents.", "limitations": "The limitations of this paper have not been addressed adequately.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "- Originality: The paper introduces a novel algorithm, PHGD, to address non-convex games with hidden structure, providing the first discrete convergence analysis in this context. The connection established with natural gradient methods adds an original perspective to the research.\n\n- Quality: The paper demonstrates rigorous analysis by providing explicit convergence rates under minimal assumptions. It extends the previous work by considering a more general multi-player setting.\n\n- Clarity: The summary provided is clear and understandable, indicating good clarity in the paper.\n\n- Significance: The paper addresses an important problem by leveraging hidden structure in non-convex games, which has implications in various domains. The developed algorithm and its convergence properties contribute to the understanding and applicability of game theory.", "weaknesses": "- Lack of diverse examples: The paper could benefit from including additional examples beyond the matching Pennis zero-sum game to illustrate the applicability of the proposed method in different settings. The example shown in this paper can be included within previous 1-dimensional assumptions presented Mladenovic et al. Are there significant instances that this paper covers while previous results do not?\n\n- Lack of comparison with existing methods: It would be helpful if the authors provided a more detailed explanation of the technical challenges associated with discrete analysis compared to continuous ones. For the continuous dynamics, does it reduces to the exact natural gradient flow in hidden convex-concave games in Mladenovic et al., \n\n- It seems that the faster convergence is at the expense of high computational complexity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your input and detailed remarks. We address each of your questions point-by-point below and we will revise our manuscript accordingly at the first revision opportunity.\n\n1. **Lack of diverse examples: The paper could benefit from including additional examples beyond the matching Pennies zero-sum game to illustrate the applicability of the proposed method in different settings.**  \n\n    We kindly refer you to Appendix D where we demonstrate the algorithm's applicability in a series of different examples.\n\n\n2. **The example shown in this paper can be included within previous 1-dimensional assumptions presented Mladenovic et al. Are there significant instances that this paper covers while previous results do not?**  \n\n    The focus of Mladenovic et al (ICLR 2021) is a continuous-time setup. In our work, although we begin by developing a more general continuous-time method than that of Mladenovic et al (Section 3.1), we continue by developing a bona fide, discrete-time algorithm; more importantly, we then go on to provide theoretical guarantees about its convergence, and its rate of convergence (Section 3.2 onwards). This is a crucial distinction from Mladenovic et al, who do not provide an algorithmic analysis of the proposed dynamics.\n\n\n3. **Lack of comparison with existing methods: It would be helpful if the authors provided a more detailed explanation of the technical challenges associated with discrete analysis compared to continuous ones.**  \n\n    We should first point out that, to the best of our knowledge, all dynamics that have been proposed for solving hidden games evolve in *continuous* time; any iterative algorithm that can be programmed in a computer would have to de facto evolve in *discrete* time, so there are no other *algorithms* to compare to.\n   \n   Now, as for the difficulty of going from continuous to discrete time, this has been the driving force for the development of stochastic approximation theory, starting from the original works of Robbins & Monro in the 1950s to the classical textbooks of Kushner and co-authors in the 1970s, and Benaïm in the 1990s. To make an extremely long story extremely short, when performing a Lyapunov/energy analysis of a continuous-time system, the chain rule of ordinary calculus suffices; however, when the analysis needs to be performed at discrete time steps, the step size plays a crucial role, as it introduces further error terms that propagate and require completely different techniques to handle. Then, when noise is also present in the mix, the situation becomes even more complicated because one needs to employ martingale limit theory to control the various stochastic errors that arise - and which are completely absent in the continuous-time flow limit (which is de facto deterministic).\n\n\n4. **For the continuous dynamics, does it reduces to the exact natural gradient flow in hidden convex-concave games in Mladenovic et al.?**  \n\n    The dynamics featured in Mladenovic et al can indeed be viewed as a special case of Preconditioned Hidden Gradient Flow. However, note that Mladenovic et al feature the aforemntioned formula for the case of a single datapoint (i.e., one-dimensional systems). Their general formula is not directly comparable.\n\n\n5. **It seems that the faster convergence is at the expense of high computational complexity.**  \n\n    We are not sure what you mean here: the per-iteration complexity of the algorithm remains the same throughout, so a faster convergence rate would be synonymous with lower computational complexity. Could we kindly ask you to elaborate if needed?\n\n\n6. **Preconditioning method and its relation to natural gradient: The authors claim that \"a judiciously chosen gradient preconditioning scheme bears an unexpected connection to natural gradient method\". However, the connection has not been well explained in the main context. What is the literature of the preconditioning method? Why is the previous natural gradient approach not seen as preconditioning?**  \n\n    Preconditioning simply means finetuning the search direction of an iterative optimization algorithm to make more informed gradient steps. It is a technique that permeates the optimization literature and is the cornerstone of some of the most widely used methods - like L-BFGS, CG, and the like; see e.g., the classical textbook of Himmelblau, \"*Applied Nonlinear Programming*\".\n\n    Natural gradient methods essentially redefine the gradient operator, so they can be seen as a special case of preconditioning. What we found unexpected was the fact that the choice of preconditioner which was the most appropriate for our analysis ended up being itself a natural gradient method (and included the continuous-time method of Mladinovic et al.). We were constrained by space in our original submission but, if the paper is accepted, we will use the extra page allowed in the camera-ready phase to explain all this in more detail.\n\n\n7. **Technical difference in extending to the multi-dimensional case: What are the main technical differences or challenges encountered when extending the approach to the multi-dimensional case?**  \n\n    The original approach of Mladinovic et al (ICLR 2021) is inherently one-dimensional and requires separability: if either condition fails, we see no way of extending it. In this regard, the main technical difficulty was in guessing the form of the preconditioner that would allow us to carry out a Lyapunov analysis.\n\n\n8. **Minor issue regarding notation: In Line 195, where $P_i(\\theta_i)$ appears before introducing what represents $P_i$.**  \n\n    Good catch, we will add a reference to equation PHGF on that line.\n\n\n---\n\nPlease let us know if any of the above is not sufficiently clear.\n"}, {"review_id": "HeEhysSDTX", "reviewer": "Reviewer_dBPZ", "summary": "The paper uses hidden structure to provide continuous time and algorithmic theoretical learning guarantees for certain non-convex games. Specifically, they provide Preconditioned Hidden Gradient Flow and its discrete-time variant Preconditioned Hidden Gradient Descent that can be proved to converge when analyzed under a specific Lyapunov function.\n", "questions": "The examples mentioned in the experiment are interesting but also seem to be restricted to very specific cases. Are there larger classes of problems besides Examples 2.1, 2.2 that could be relevant in applications? For instance, has there been work on when neural network parameterization could satisfy the faithful map condition? While being possibly out of the scope of the main contribution of the paper, a discussion of these points could be interesting.\n\nAs a possible limitation, is the implied access to the Jacobian of representation map standard in the literature?\n\nThe paper mentions dimension reduction as a motivation of the representation map. It is not immediate to me that dimension reduction could be achieved while simultaneously preserving the faithfulness assumptions, due to topological considerations. A discussion of this point could be interesting. For instance, does the El Farol Bar game parameterization satisfy the faithfulness assumptions?\n\n*Minor questions:*\n\nLine 195 -> Is the message that $\\mathbf{P}_i$ will be designed to achieve certain properties of was it defined before? Was not clear on the first read.\n\nLines 177 - 189 -> The connection between the two paragraphs was not clear. Was NHGD shown to not require the mentioned assumptions?\n\n*Possible minor Typos:*\nLine 116: $\\Theta$ -> $\\Theta_i$?\nLine 164: For the Jacobian notation, should it depend on $\\theta_i$\nLine 172: Here, it is possible that the notation is confusing with the previous separation of the control variables of each player. As far as I understand, the individual coordinates of the controls of one player is meant here.\nLine 254: an closed -> a closed", "limitations": "No major limitations. As mentioned above: empirical validation could be extended to relevant problems in application.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The theoretical contribution of the paper is significant, compared to past work, the setting is significantly more general. The paper is very well presented, with figures explaining the basic theoretical ideas behind the paper. The theory is solid and rigorous, while I have not checked the proofs line by line, they seem to be correct. Furthermore, significant motivation is provided both visually and by argumentation for the proof strategies employed.\n\nExperiments are also provided, and in toy examples the algorithm is demonstrably better than alternatives. Overall, the paper solves an important problem in algorithmic game theory.", "weaknesses": "I think this is a strong paper with a solid contribution. Some possible weaknesses:\n\n* A discussion of the relevance of the faithfulness assumption on the hidden map could be discussed. For instance, the experiments conducted seem to be on particular toy problems, it’s not immediately clear if there are large classes of problems with hidden structure that satisfy the given conditions.\n* The authors make an effort to present the ideas behind the proofs, which are the main contributions of the paper. Still, the presentation in the main body could benefit from a condensed roadmap of the proof strategy. While Section 4 contains main ideas, the overall picture was difficult to grasp.\n* The assumption on the representation map (e.g. faithfulness) is difficult to locate, the assumption could be made more explicit for ease of reading.\n* Experiments are limited to somewhat simple cases, an evaluation of PHGD on for instance GAN training or other relevant problems in practice could be a stronger empirical argument.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging remarks and your positive evaluation. We reply to your questions point-by-point below:\n\n1. **A discussion of the relevance of the faithfulness assumption on the hidden map could be discussed.**  \n\n    We will be happy to add a discussion, however, we believe that it could be more useful to see our setting as more prescriptive than descriptive - in the sense that we provide an intuitive set of conditions that allow for strong theoretical guarantees. Our contributions can help the design of practical systems with better performance and stability.\n\n\n2. **The presentation in the main body could benefit from a condensed roadmap of the proof strategy.**  \n\n    Sure thing, if accepted, we would be happy to take advantage of the extra page allowed in the revision to include such a roadmap. Thank you for the suggestion!\n\n\n3. **The assumption on the representation map (e.g. faithfulness) is difficult to locate, the assumption could be made more explicit for ease of reading.**  \n\n    Of course, we will be happy to collect it with the rest of the assumptions in the revision stage.\n\n\n4. **An evaluation of PHGD on GAN training or other relevant problems in practice could be a stronger empirical argument.**  \n\n    Although GAN training is undisputably an important problem, we would like to point out that in game-theoretic setup it corresponds to a 2-player Hidden Convex-Concave Game. Some preliminary experimental results in this setup can be traced to the work of Mladenovic et al. GAN training however is a 2-player game, while in this paper we'd like to provide a method that goes beyond the 2-dimensional barrier. The examples we present build toward that goal, starting with examples that provide good intuition and visual feedback, and eventually arriving at the El Farol Bar game, a hard $n$-player benchmark.\n\n\n5. **Are there larger classes of problems besides Examples 2.1, 2.2 that could be relevant in applications?**  \n\n    We kindly refer the reviewer to Appendix D where we provide empirical evidence in a variety of examples, including a hidden El Farol Bar structure, which is a highly non-trivial $n$-player game. Furthermore, we would like to point out that the complexity of the type of problems we study arises from at least two factors, namely, the complexity of the base game, and the complexity of the associated latent game. For example, in a Deep Learning setup, while the complexity of the base game played in the input layer of the MLPs is high, the latent game, played to, or near, the output layers of the MLPs is comparatively lower. In the examples we provide in Section 5 and Appendix D we provide evidence of the applicability of PHGD in setups where the complexity of the base game is high relative to the capabilities of our own equipment, but also the associated latent games are gradually increasing in difficulty in each of the examples.\n\n\n6. **Has there been work on when neural network parameterization could satisfy the faithful map condition?**  \n\n    We kindly refer you to our answer to the first point of our discussion.\n\n\n7. **As a possible limitation, is the implied access to the Jacobian of representation map standard in the literature?**  \n\n    Yes, indeed: in the literature on hidden games, the latent structure - that is, the map $\\chi$ or its equivalent - is assumed known, so the calculation of the Jacobian is also accessible by the same tenet.\n\n\n8. **The paper mentions dimension reduction as a motivation of the representation map. It is not immediate to me that dimension reduction could be achieved while simultaneously preserving the faithfulness assumptions, due to topological considerations. A discussion of this point could be interesting. For instance, does the El Farol Bar game parameterization satisfy the faithfulness assumptions?**  \n\n    Any linear map $(A:\\mathbb{R}^m \\to \\mathbb{R}^d)$ with full column rank is faithful so, if $m>d$, generic linear maps are faithful. Then, taking a composition with a faithful activation function (for instance, a leaky ReLU) would lead to a faithful representation, so there are no topological obstacles in this regard. [In our \"faithful\" does not mean injective / \"1-1\" in our context; this would indeed be topologically impossible.]\n\n\n9. **Line 195 -> Is the message that $P_i$ will be designed to achieve certain properties or was it defined before? Was not clear on the first read.**  \n\n    The idea was that $\\mathbf{P}$ would be designed to satisfy certain key properties; apologies if this was not clear, we will clarify this in the revision round.\n\n\n10. **Lines 177 - 189 -> The connection between the two paragraphs was not clear. Was NHGD shown to not require the mentioned assumptions?**  \n\n    In our discussion, the work of Mladenovic is, in a sense, \"sitting on the fence\". To elaborate, they sidestep some of the more restrictive assumptions articulated in the introductory paragraph of Section 3. Notably, their portrayal of NHGD eschews any necessity for a one-dimensional representation, instead honing in on the latent space rather than the parameter domain.\n\n    To recast this in our notation for clarity: Mladenovic et al. refrain from prescribing a distinct structure to the latent maps, denoted as $\\chi_i(\\theta_i)$ for $i=1,2$. This approach marks a progression from the strategies adopted by Vlatakis et al. However, it remains imperative to recognize the confines of Mladenovic et al.'s methodology. Among various limitations, their model is primarily tailored for a 2-player scenario. Additionally, upon examining their convergence justification (as delineated in Proposition 4.1 of their paper) and subsequent demonstrations regarding NHGD, their analysis only applies to one-dimensional problems.\n \n\n11. **{Minor typos}**\n\n    Will fix them, thanks for bringing them to our attention!\n\n---\n\nThank you again for your input and positive evaluation - and please let us know if you have any further questions.\n"}, {"review_id": "rMLM33D0Xg", "reviewer": "Reviewer_rghq", "summary": "It is known that a convergence guarantee exists for monotone games. However, most games are not monotone. This paper considers a new scenario where the monotone structure is presented in latent space. It then proposes the 'Preconditioned Hidden Gradient Dynamics' to design the preconditioned hidden gradient descent algorithm. It is demonstrated that the proposed algorithm will converge to the desired Nash equilibrium. The theoretical result is also verified using empirical experiments. ", "questions": "This paper has mentioned many times \"minimal assumptions\" or \"without additional assumptions\". I am probably interested in how strong other assumptions are, such as separability or low-dimensionality assumptions. Do you have any simple examples saying these assumptions are not satisfied. \n\nFigure 1 is very helpful to understand the concept of hidden games. Do you have any practical example or real-world example that would have such Rock-Paper-Scissors hidden structure? ", "limitations": "This is a purely theoretical work so no negative impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Novelty: Existing works have shown the difficulties of finding the equilibrium in hidden-monotone games. Other results usually require additional assumptions on the structure. This work proposes a new perspective to design the preconditioned hidden gradient descent and solves the problem that has not been addressed before.  \n\nSignificance: Most of games are not monotone. Studying the hidden-monotone structure will significantly extend the existing literatures on monotone games, which makes me believe this work opens a new direction of the resarch. The positive result obtained in this work and the new design in the continous-flow will also help understanding on the hidden structure.\n", "weaknesses": "This paper is very well-written. But it may lack some real-world examples to help the reader understand the importance of studying the hidden games. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your support and your helpful comments.\n\n1. **This paper is very well-written. But it may lack some real-world examples to help the reader understand the importance of studying the hidden games.**  \n\n    We are glad to hear that you found our paper very well written! A natural example would be to focus on the competition between two companies that fight for market share. Specifically, let's consider the competition between two ride-share platforms such as Uber vs Lyft. Recent work has produced explicit models of such competition under the assumption that the demand for each company at each location depends linearly on the set of posted prices by each company [1]. Furthermore, they show that these models correspond to a strongly monotone game and then apply dynamics to solve them. Clearly, the linear demand model is a simplified assumption. By introducing a non-linear model (that is linear only on some space of latent variables) we can capture much more complex, real-world dependencies on the elasticity of demands while satisfying hidden monotonicity.\n\n\n[1] Narang, Adhyyan, et al. \"Learning in stochastic monotone games with decision-dependent data.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2022.\n\n2. **This paper has mentioned many times \"minimal assumptions\" or \"without additional assumptions\". I am probably interested in how strong other assumptions are, such as separability or low-dimensionality assumptions. Do you have any simple examples saying these assumptions are not satisfied.**  \n\n    Sure thing, consider e.g., the weighted softmax function $\\chi(\\theta_1,\\theta_2) = \\log\\left[(1+\\theta_2^2)e^{\\theta_1} + (1+\\theta_1^2)e^{\\theta_2}\\right]$. This is neither one-dimensional nor separable.\n\n\n3. **Figure 1 is very helpful to understand the concept of hidden games. Do you have any practical example or real-world example that would have such Rock-Paper-Scissors hidden structure?**  \n\n    We kindly refer you to our answer to the first point of our discussion, as this is a special case.\n"}, {"review_id": "sBMDqHtyrq", "reviewer": "Reviewer_zCUr", "summary": "This paper proposes a preconditioned hidden gradient descent to provide strong formal convergence guarantees in a general class\nof multi-agent settings which are referred to as call hidden monotone games. Theoretical analyses and synthetic experiments are also provided. ", "questions": "1. Is it feasible for this method to be applied to common neural networks, such as ResNet50, BERT, etc?", "limitations": "Yes.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The method seems novel to handle the proposed problem of hidden monotone games.\n2. Theoretical analyses and synthetic experiments are also provided to demonstrate the effectiveness of the proposed method.", "weaknesses": "1. Experiments on real-world datasets (e.g., MNIST or multi-agent reinforcement learning environments) are absent. \n2. Experiments on adversarial generation, adversarial attack, and adversarial transfer learning are absent.\n3. Computational complexity analyses are absent.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your input and positive evaluation. We reply to your questions point-by-point below:\n\n1. **Discussion about the experiments included in the paper:**\nOur work distinctly stands out for its depth and novelty in experimental design within the realm of hidden games. A review of recent studies, such as [1,2,3], showcases their focus on continuous dynamics, offering only a fleeting glance at experiments with discrete step-sizes. Specifically:\n- Their experiments, although illustrative, were limited to synthetic setups, often featuring a single hidden variable and straightforward mappings, like the invertible sigmoid in games such as Rock Paper Scissor.\n- [3] ventured slightly further, introducing a single hidden layer, but fell short in detailing the nuances of converting continuous dynamics to a discrete format using the Euler method.\n\nIn stark contrast, our experiments probe deeper, navigating games with multiple hidden layers using our distinctive method.\nFurthermore, our appendix introduces a seminal benchmark for Nash computation in expansive policy domains, exemplified by the El-Farol Bar (see [4] and references therein).\n\n\n2. **Discussion about real-world application, MARL or adversarial training:**  \n\n    Our primary objective was to devise a game theoretically applicable algorithm for computing Nash equilibria in structured and ML-inspired non-convex settings. Unlike prior works, ours introduces theory and examples with intricate hidden maps. \n\n    Training MARL and the other applications are outside the scope of the current paper. However, the strength of our theoretical analysis distinctly underscores its applicability. In particular, when evaluating works such as [5] and [6] (highlighted by another reviewer for a comparative examination of related work), our framework and algorithm not only address challenges in variational policy methods within MARL and the econometric literature but do so with a broader range of assumptions than those outlined in [5,6]. \n\n    Thus, through establishing the theoretical basis for PHGD, we anticipate inspiring engineers and practitioners to adapt PHGD to large-scale challenges.\n\n\n3. **On the computational complexity of Hidden Games:**\n\n   The computational complexity of Hidden Games is an open and captivating topic. First, it's essential to focus on loss functions/utilities and hidden maps with a succinct polynomial representation under certain well-behaved arithmetic circuits [7]. Without this, defining a meaningful complexity result inside NP for continuous strategy games becomes challenging. When arithmetic circuits that describe losses are generic, the problem becomes FIXP-hard [15]. When equipped with these succinct models, we can efficiently compute value, gradient, and Jacobian oracles for hidden maps in polynomial time. Within this modeling framework, the problem could be shown to be at least as hard as PPAD (the standard complexity class for computing ε-Nash equilibrium ).  On the other hand, proving membership to PPAD for general hidden maps — without escalating higher in the computational hierarchy of TFNP — remains an open question. While the authors of [8] outlined a meta-method using a version of Kakutani's theorem, the specifics are yet to be fleshed out.\n\n   *All this underscores why the assumptions we stipulated are vital for a positive outcome in computing Nash equilibrium in non-concave general games.* Furthermore, when more structures like diagonal convexity/monotonicity are introduced, our results provide an algorithm for finding the Nash equilibrium. **Using our algorithm, PHGD, and given certain value/gradient oracle access, the problem is actually determined to lie in P based on iteration complexity results.**\n\n   The discussion on computational complexity doesn't end here. If we assume only black-box access to the objective, [9-11] derive unconditional lower bounds for the general hidden games. However, a more detailed account goes well beyond the scope of the current work, so it is not possible to go into more length here.\n\n\n\n4. **Regarding the utilization of more general neural networks like BERT/ResNet:**\n\n    In essence, the crux of our theoretical requirements can be distilled to: *if the neural networks are highly expressive, our method can reliably uncover the NE in associated games.* The empirical evidence surrounding the aforementioned networks suggests they meet the prerequisites our theorems mandate. Developing a theoretical framework for such Deep Learning Game Theory would likely necessitate an average/smoothed complexity analysis. Recent findings related to learning models with NNs [12,16] and computing Nash equilibria in generalized random games [14] might provide an intriguing trajectory for subsequent research.\n\n    Given the potential interest in this topic within the community, we will aim to incorporate elements of this discussion into the appendix or the camera-ready version, focusing on future and open challenges.\n\n[1] https://arxiv.org/abs/1910.13010 \n[2] https://arxiv.org/abs/2101.05248 \n[3] https://openreview.net/forum?id=bsycpMi00R1 \n[4] https://arxiv.org/abs/2106.01285 \n[5] https://arxiv.org/abs/2007.02151\n[6] https://arxiv.org/abs/2205.01774\n[7] https://arxiv.org/abs/2011.01929\n[8] https://arxiv.org/abs/2207.07557\n[9] https://arxiv.org/abs/2009.09623\n[10] Exponential lower bounds for finding Brouwer fixed points\n[11] Problem complexity and method efficiency in optimization\n[12] https://arxiv.org/abs/2302.07426\n[13] Book Computational Complexity.\n[14] https://arxiv.org/abs/2007.10857\n[15] https://arxiv.org/abs/2111.06878\n[16] https://arxiv.org/abs/2211.03975"}]

Author rebuttal:
Dear AC, dear reviewers,

We are sincerely grateful for your time and constructive input. To streamline the discussion phase, we reply to each reviewer’s questions in a separate point-by-point thread below.

Kind regards,

The authors

Meta-review: The paper makes solid contribution in introducing a preconditioned hidden gradient descent algorithm for solving a general class of hidden monotone games. Theoretical results are novel, clearly presented, and supported by several non-trivial numerical experiments. 


The authors' response has carefully addressed most concerns brought up by the reviewers in light of the assumptions and comparison to existing work. There are some lingering concerns on the presentation quality. I think the contribution outweighs the weakness and therefore would recommend to accept the paper. In the final version, please follow the reviewers' suggestion and significantly improve the presentation of the paper as promised.
Decision: Accept (poster)