Paper deep dive
$Q$ Can Play That Game: Online Fitted $Q$-Iteration for Continuous-Action Zero-Sum Markov Games with Convex-Concave Function Approximation
Kushagra Gupta, Jingqi Li, Cade Armstrong, Lasse Peters, Ross E. Allen, Ufuk Topcu, David Fridovich-Keil
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 10/6/2026, 9:43:18 AM
Summary
This paper introduces a novel class of convex-concave neural network function approximators for the Q-function in continuous-action zero-sum Markov games. By ensuring the Q-function is convex in the minimizing player's action and concave in the maximizing player's action, the method guarantees the existence of pure-strategy saddle points for the minimax problem within the Bellman operator. The authors propose an online variant of fitted Q-iteration using this architecture and establish the first finite-sample convergence guarantees for non-linear-quadratic (non-LQ) zero-sum Markov games with continuous states and actions.
Entities (7)
Relation Signals (5)
Convex-Concave Neural Network → ensures → Saddle Point
confidence 95% · The convex-concave structure addresses the challenge above, as the minimax theorem guarantees that a pure-strategy saddle point exists for the minimax problem inside the Bellman operator.
Online Fitted Q-Iteration → provides → Finite-Sample Guarantees
confidence 94% · establish, to the best of our knowledge, the first finite-sample guarantees for non-LQ zero-sum Markov games with continuous states and actions.
Online Fitted Q-Iteration → employs → Convex-Concave Neural Network
confidence 93% · We then study an online variant of fitted Q-iteration employing this function class...
PICNN → isbasisfor → Convex-Concave Neural Network
confidence 92% · Building on the partially input convex neural network architecture (Amos et al., 2017), this class is convex in the minimizing player’s actions and concave in the maximizing player’s actions by construction.
Bellman operator → contains → Minimax Problem
confidence 90% · the associated Bellman operator involves a minimax problem that need not admit a tractable saddle-point solution.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Zero-sum Markov games arise in a wide variety of sequential decision-making problems such as adversarial learning and planning against modeled uncertainties. However, prior work on finite-sample guarantees on the learned state-action value function ($Q$-function) for zero-sum Markov games is largely restricted to finite-action settings, or to continuous-action games in which agents have linear dynamics and quadratic rewards (i.e. linear-quadratic, or LQ, games). A central challenge in extending such guarantees to more general continuous-action zero-sum Markov games is that the associated Bellman operator involves a minimax problem that need not admit a tractable saddle-point solution. To this end, we first introduce a class of neural network function approximators for the $Q$-function that is convex-concave in the players' actions, which guarantees that this minimax problem admits a pure-strategy saddle point. We then study an online variant of fitted $Q$-iteration employing this function class and establish, to the best of our knowledge, the first finite-sample guarantees for non-LQ zero-sum Markov games with continuous states and actions. Our code can be found at this https URL.
Tags
Links
- Source: https://arxiv.org/abs/2610.04010v1
- Canonical: https://arxiv.org/abs/2610.04010v1
Trouble viewing inline? Open PDF directly →
Full Text
128,201 characters extracted from source content.
Expand or collapse full text
Q Can Play That Game: Online Fitted Q-Iteration for Continuous-Action Zero-Sum Markov Games with Convex-Concave Function Approximation Kushagra Gupta Affiliation: The University of Texas at Austin Email: kushagrag@utexas.edu Jingqi Li Affiliation: The University of Texas at Austin Email: jingqi.li@utexas.edu Cade Armstrong Affiliation: The University of Texas at Austin Email: cadearmstrong@utexas.edu Lasse Peters Affiliation: The University of California, Berkeley Email: utopcu@utexas.edu Ross E. Allen Affiliation: Massachusetts Institute of Technology (MIT) Lincoln Labs Email: dfk@utexas.edu Ufuk Topcu Affiliation: The University of Texas at Austin Email: lasse.peters@berkeley.edu David Fridovich-Keil Affiliation: The University of Texas at Austin Email: ross.allen@l.mit.edu Abstract Zero-sum Markov games arise in a wide variety of sequential decision-making problems such as adversarial learning and planning against modeled uncertainties. However, prior work on finite-sample guarantees on the learned state-action value function (Q-function) for zero-sum Markov games is largely restricted to finite-action settings, or to continuous-action games in which agents have linear dynamics and quadratic rewards (i.e. linear-quadratic, or LQ, games). A central challenge in extending such guarantees to more general continuous-action zero-sum Markov games is that the associated Bellman operator involves a minimax problem that need not admit a tractable saddle-point solution. To this end, we first introduce a class of neural network function approximators for the Q-function that is convex-concave in the players’ actions, which guarantees that this minimax problem admits a pure-strategy saddle point. We then study an online variant of fitted Q-iteration employing this function class and establish, to the best of our knowledge, the first finite-sample guarantees for non-LQ zero-sum Markov games with continuous states and actions. Our code can be found at https://github.com/CLeARoboticsLab/QCanPlayThatGame. 1 Introduction We consider the problem of learning state-action value functions (Q-functions) in discounted, infinite-horizon, two-player zero-sum Markov games with continuous state-action spaces. Such games naturally arise in competitive scenarios and robust decision-making, where environmental uncertainties and disturbances are adversarially modeled (Zhou et al., 1996; Morimoto and Doya, 2000; Pinto et al., 2017). Prior work has established finite-sample guarantees for zero-sum Markov games in the finite-action setting (Lagoudakis and Parr, 2002; Perolat et al., 2015; Zhao et al., 2022; Fan et al., 2020; Zhang et al., 2021a; Jia et al., 2019; Sidford et al., 2020; Xie et al., 2020; Alacaoglu et al., 2022; Chen et al., 2024; Feng et al., 2024). However, extending these results to the continuous state-action setting remains challenging. The difficulty stems from the minimax problem on Q inside the Bellman operator. At every state, each player wishes to play a security strategy, meaning that one player’s policy solves a minmax problem and the other’s solves a maxmin . The solutions to these two distinct problems are mutually consistent at saddle points, where both players have non-exploitable security strategies. Saddle points are guaranteed to exist when policies map from state to mixed strategies over the action space. In finite-action spaces, the resulting saddle-point problem can be solved via a linear program; in continuous action spaces however, it is generally intractable to compute mixed-strategy saddle points as mixed-strategy spaces are infinite-dimensional. Moreover, when policies are restricted to output pure strategies at each state, i.e. raw actions, saddle-point solutions generally do not exist for arbitrary Q. In this work, we propose a new class of neural network function approximators of the Q-function which is convex in the minimizing player’s action and concave in the maximizing player’s action. This convex-concave structure addresses the challenge above, as the minimax theorem guarantees that a pure-strategy saddle point exists for the minimax problem inside the Bellman operator. Further, this pure-strategy saddle point can also be reliably computed up to any desired accuracy using existing minimax optimization methods (Nemirovski, 2004; Lin et al., 2020). We analyze an online variant of minimax fitted Q-iteration which employs this convex-concave function class and establish finite-sample bounds between the learned Q-function and the fixed point of the Bellman operator, assuming that the fixed point admits pure-strategy saddle points. The prior work closest to ours establishes finite-sample bounds for online minimax fitted Q-iteration with neural network function approximation, but is restricted to finite-action spaces (Fan et al., 2020). In the continuous-action setting, single-player reinforcement learning literature has developed finite-sample analysis for fitted Q-iteration with function approximation (Antos et al., 2007). However, extending these results to the zero-sum Markov game setting remains underexplored. Within the game setting we consider, theoretical finite-sample results for continuous state-action domains remain largely confined to the linear-quadratic (LQ) setting, where agents have linear transition dynamics and quadratic objectives (Başar and Olsder, 1998; Al-Tamimi et al., 2007a; Al-Tamimi et al., 2007b; Zhang et al., 2019; Bu et al., 2019; Zhang et al., 2021b). These results exploit the fact that in the LQ setting, the optimal Q-function and the resulting policies admit a closed-form solution via the algebraic Riccati equations (Başar and Olsder, 1998). Unfortunately, this Riccati structure does not extend beyond the LQ setting. In this work we move beyond the LQ setting, and make the following contributions: • Contribution 1. We propose a new class of neural network function approximators for the Q-function of zero-sum Markov games. Building on the partially input convex neural network architecture (Amos et al., 2017), this class is convex in the minimizing player’s actions and concave in the maximizing player’s actions by construction. The convex-concave structure ensures the existence of a saddle-point solution to the minimax problem in the Bellman operator. • Contribution 2. We analyze batched minimax Q-learning employing the above function approximation class, and establish finite-sample bounds comparing the learned Q-function to the fixed point of the Bellman operator, assuming the fixed point admits pure-strategy saddle points. To the best of our knowledge, this is the first such bound for neural network function approximation in zero-sum Markov games with continuous state-action spaces beyond the LQ setting. Additionally, we empirically investigate whether these convex-concave neural networks lead to stable training when used on a practical version of modified fitted Q-iteration. 2 Preliminaries Notation. ℤ≥0Z_≥ 0 denotes the set of non-negative integers, and for n∈ℤ≥0n _≥ 0, [n][n] denotes the set 1,2,⋯,n\1,2,·s,n\. ()P(S) denotes the set of all probability measures over a measurable space S. M()M(S) denotes the space of bounded measurable functions with domain S. For f∈M()f∈ M(X) and a probability measure σ∈()σ (X), we denote ‖f‖2,σ=∼σ[f()2]\|f\|_2,σ= E_ x σ [f( x)^2 ]. For a measure μ absolutely continuous with respect to another measure σ, i.e., μ≪σμ σ, dμ/dσ dμdσ denotes the Radon-Nikodym derivative. We denote a sequence of vectors 1,…,j v_1,…, v_j in short as 1:j v_1:j. We denote the Lebesgue measure by λ, and we denote the Lebesgue measure of an ℓ2 ^2-ball in d dimensions with radius η by αdηd _dη^d. We consider two-player, zero-sum, infinite-horizon discounted Markov games given by the tuple (,,,P,r,γ) (S,U,V,P,r,γ ), where ⊂ℝdS ^d_ s is the continuous state space, and ⊂ℝdU ^d_ u and ⊂ℝdV ^d_ v are the continuous action spaces of the minimizing and maximizing players, respectively. We take ,,S,U,V to be convex and compact. P:(×)→()P:(S×U×V) (S ) denotes the transition dynamics of the game, r:(×)→ℝr:(S×U×V) is the immediate reward function, and γ∈(0,1)γ∈(0,1) is the discounting factor. Let player 1 and player 2 be the minimizing and maximizing players respectively. At each time t∈ℤ≥0t _≥ 0, at some game state t∈ s_t , players 1 and 2 choose actions t∈ u_t and t∈ v_t . This yields an immediate reward of r(t,t,t)r( s_t, u_t, v_t) and the game proceeds to the next state t+1∼P(⋅|t,t,t) s_t+1 P(·| s_t, u_t, v_t). Player 1 chooses actions to minimize the expected discounted cumulative return ℛ=[∑t=0∞γtr(t,t,t)]R=E [ _t=0^∞γ^tr( s_t, u_t, v_t) ], while player 2 chooses actions to maximize ℛR. Each player chooses its actions according to a policy. We consider deterministic Markovian policies induced by a state-action value function (Q-function), in which players are restricted to pure strategies. For a given continuous function Q:(×)→ℝQ:(S×U×V) , at state s, player 1 chooses πQ()∈argmin∈max∈Q(,,) _Q( s)∈ _ u _ v Q( s, u, v) and player 2 chooses μQ()∈argmax∈min∈Q(,,) _Q( s)∈ _ v _ u Q( s, u, v). These are the players’ security strategies: player 1 is guaranteed a value no worse than min∈max∈Q(,,) _ u _ v Q( s, u, v) and player 2 is guaranteed a value no worse than max∈min∈Q(,,) _ v _ u Q( s, u, v). For such games the minimax Bellman operator :M(×)→M(×)T:M (S×U×V )→ M (S×U×V ) is defined by Q(,,)=r(,,)+γ′∼P(⋅|,,)[inf~∈sup~∈Q(′,~,~)]. ( s, u, v )=r ( s, u, v )+ _ s P(·| s, u, v) [ _ u _ v Q ( s , u, v ) ]. (1) It is well known that the minimax Bellman operator is contractive in the L∞L_∞-norm and thus a unique fixed point Q∗Q^* exists such that Q∗=Q∗TQ^*=Q^* (Shapley, 1953; Perolat et al., 2015). Equation 1 reveals that in order to compute the Bellman operator for continuous functions, one needs to solve a minimax problem, in this case corresponding to player 1’s security strategy πQ _Q. One can analogously define the maximin Bellman operator associated with player 2’s security strategy μQ _Q. While both minimax and maximin problems admit solutions for compact U and V and continuous Q, these solutions need not coincide, i.e., (πQ,μQ)( _Q, _Q) need not be a saddle-point pair for generic Q. We restrict Q to a convex-concave function approximation class, convex in the player 1’s action and concave in player 2’s action so that the minimax theorem guarantees that at every state, (πQ,μQ)( _Q, _Q) forms a saddle point for every Q in our function class (Sion, 1958). Further, these saddle points can be found up to any desired accuracy using existing minimax optimization methods (Nemirovski, 2004; Lin et al., 2020). Remark 1 (Mixed Strategies). An alternative route to ensure existence of a saddle-point solution is to let players employ mixed strategies, where they randomize over pure strategies. In the finite-action setting, mixing ensures that a saddle point of the minimax problem always exists, and it can be computed by solving a linear program at every state s. In the continuous-action setting, a saddle point over mixed strategies still exists under mild continuity assumptions (Glicksberg, 1952), but computing it is far less straightforward than in the finite-action setting. The iterative double oracle algorithm (Adam et al., 2021) is guaranteed to return a saddle point up to any desired accuracy; however, each iteration requires computing a global best response for each player, which can be intractable under function approximation. Moreover, an explicit bound on the required number of iterations as a function of the saddle-point accuracy remains unknown. These difficulties motivate our focus on pure strategies with convex-concave function approximation instead. To represent the return ℛR obtained by policies (π,μ)(π,μ), it is useful to define the state value function Vπ,μ:→ℝV^π,μ:S , given by Vπ,μ()=[∑t=0∞γtr(t,π(t),μ(t))|0=]V^π,μ( s)=E [ _t=0^∞γ^tr ( s_t,π( s_t),μ( s_t) )| s_0= s ]. The state value function V∗V^* relates to the fixed point Q∗Q^* of eq. 1 as Q∗(,,)=r(,,)+γ′∼P(⋅|,,)[V∗(′)]Q^*( s, u, v)=r( s, u, v)+ _ s P(·| s, u, v) [V^*( s ) ]. The state value function can be used to determine whether the policies π,μπ,μ form a saddle-point equilibrium via the Nash gap. Let Π denote the set of pure Markovian strategies, then for an evaluation distribution ρ∈()ρ (S), the Nash gap is defined by NashGapρ(π,μ)=∼ρ[maxμ′∈ΠVπ,μ′()−minπ′∈ΠVπ′,μ()]. NashGap_ρ(π,μ)=E_ s ρ [ _μ ∈ V^π,μ ( s)- _π ∈ V^π ,μ( s) ]. (2) The Nash gap is always non-negative, and is zero only when the input policies form a saddle-point Nash equilibrium with respect to ρ. Formally, NashGapρ(π,μ)=0⇔Vπ,μ′()≤Vπ,μ()≤Vπ′,μ() NashGap_ρ(π,μ)=0 V^π,μ ( s)≤ V^π,μ( s)≤ V^π ,μ( s) for all π′∈Ππ ∈ , μ′∈Πμ ∈ , and ρ-almost every ∈ s . In particular, when the fixed point Q∗Q^* of the minimax Bellman operator 1 admits pure-strategy saddle points, the induced policies (πQ∗,μQ∗)( _Q^*, _Q^*) satisfy NashGapρ(πQ∗,μQ∗)=0 NashGap_ρ( _Q^*, _Q^*)=0 for every evaluation distribution ρ∈()ρ (S). The goal of this paper is to obtain bounds on the Q-function learned from a finite number of samples, and in turn bound the Nash gap corresponding to its induced security strategies. 3 Convex-Concave Function Approximation We now describe the convex-concave neural network architecture used to approximate the Q-function: for every network parameter vector θ∈Θθ∈ , and every state ∈ s , the Q-function network Qθ:(×)→ℝQ_θ:(S×U×V) should be convex-concave, i.e., Qθ(,,)Q_θ( s, u, v) must be convex in ∈ u for every fixed (,)( s, v) and concave in ∈ v for every fixed (,)( s, u). To construct such a network, we build on partially input convex neural networks (PICNNs) (Amos et al., 2017), a network architecture that guarantees convexity in a designated subset of the network’s inputs, while simultaneously leaving the dependence on the other inputs unconstrained. Formally, given two inputs x and y where convexity in y is desired, the PICNN architecture constructs a neural network Nθ(,)N_θ( x, y), such that for every choice of parameters θ, Nθ(,)N_θ( x, y) is convex in y for fixed x, while retaining full expressivity in x. PICNNs achieve this by constraining a subset of weights along the computation graph edges traceable back to y to be non-negative and pairing them with convex, non-decreasing activations, while leaving weights traceable to x unconstrained. We review the PICNN architecture in more detail in Appendix C. To develop a convex-concave Qθ(,,)Q_θ( s, u, v), we use three neural networks with parameters θ1,θ2,θ3θ^1,θ^2,θ^3, representing the concatenated parameters as θ=(θ1,θ2,θ3)∈Θθ=(θ^1;θ^2;θ^3)∈ . We use two PICNNs Nθ11(,):(×)→ℝN^1_θ^1( s, u):(S×U) (convex in the input u) and Nθ22(,):(×)→ℝN^2_θ^2( s, v):(S×V) (convex in the input v), as well as a standard feedforward matrix-valued neural network Mθ3():→ℝd×dM_θ^3( s):S ^d_ u×d_ v. We construct a convex-concave Qθ(,,)Q_θ( s, u, v) as Qθ(,,):=Nθ11(,)−Nθ22(,)+⊤Mθ3(). Q_θ( s, u, v):=N^1_θ^1( s, u)-N^2_θ^2( s, v)+ u M_θ^3( s)\, v. (3) Note that while the first two terms Nθ11(,)−Nθ22(,)N^1_θ^1( s, u)-N^2_θ^2( s, v) alone would be convex in u and concave in v, they would make QθQ_θ only additively separable in u and v. The third, bilinear term ⊤Mθ3() u M_θ^3( s)\, v captures interactions between the players’ actions beyond the separable structure, while being simultaneously convex in u and concave in v. Note that it may be possible to include coupling terms that are more expressive than a bilinear mapping. We do not pursue this direction here, as the bilinear term suffices to guarantee joint convexity-concavity for our theoretical result in Section 4, and we found it to be adequate for our experiments in Section 5 as well. Our theoretical results will need the the Lipschitz constant of QθQ_θ in the joint actions, as well as the covering number. We bound these for a particular architectural choice of NiN^i and M in Theorem 2 of Section C.2, and Theorem 3 of Section C.3 respectively. 4 Online Minimax Fitted Q Iteration We now describe our modified minimax fitted Q-iteration procedure, given in Algorithm 1. We restrict the class of function approximators class to be the convex-concave neural network architecture described in Section 3, which we denote as ℱF. Further, we assume access to a minimax oracle ϵ:ℱ→(×)O_ε:F→(U×V). For a convex-concave objective f(,)f( u, v) and any desired ϵ>0ε>0, ϵO_ε returns an approximate saddle point (~,~)∈(×)( u, v)∈(U×V) such that the gap |max∈f(~,)−min∈f(,~)|<ϵ | _ v f ( u, v )- _ u f( u, v) |<ε. Several existing minimax optimization methods can be feasibly used as the oracle for Q∈ℱQ , because ℱF guarantees convexity-concavity. At the kthk^th iteration of Algorithm 1, when the parameter estimate for the Q-function is θk _k, we denote the corresponding network QθkQ_ _k as QkQ_k. Algorithm 1 Online Minimax Fitted Q-Iteration 1: Hyper-parameters: Number of iterations K, batch size n. 2: Inputs: Markov game (,,,P,r,γ) (S,U,V,P,r,γ ), initial Q-function Q0∈ℱQ_0 , fixed sampling distribution σ∈(×)σ (S×U×V), minimax oracle ϵO_ε. 3: for k=0k=0 to K−1K-1 do 4: Sample n i.i.d. samples (i,i,i)i=1n∼σ \ ( s_i, u_i, v_i ) \_i=1^n σ 5: Draw i′∼P(⋅∣i,i,i) s_i P (· s_i, u_i, v_i ) for each i∈[n]i∈[n] 6: For each i∈[n]i∈[n], form the target (~i,~i)=ϵ(Qk(i′,⋅,⋅)) ( u_i, v_i )=O_ε (Q_k ( s _i,·,· ) ) yi=r(i,i,i)+γQk(i′,~i,~i) y_i=r ( s_i, u_i, v_i )+γ Q_k ( s _i, u_i, v_i ) 7: Solve the regression problem exactly L^n(f,Qk) L_n(f;Q_k) :=1n∑i=1n(f(i,i,i)−yi)2, := 1n _i=1^n (f( s_i, u_i, v_i)-y_i )^2, Qk+1 Q_k+1 :=argminf∈ℱL^n(f,Qk) := _f \ L_n(f;Q_k) 8: end for 9: Output: Learned Q-function QKQ_K Algorithm 1 differs from standard fitted Q-iteration in the sense that we use data in an online manner and do not reuse it. Specifically, at iteration k, using a fixed sampling distribution σ∈(×)σ (S×U×V), we sample n i.i.d. state-action tuples (i,i,i)∼σ( s_i, u_i, v_i) σ for i∈[n]i∈[n]. Using these states and actions, we sample the next states according to the transition dynamics i′∼P(⋅|i,i,i) s _i P(~·~| s_i, u_i, v_i) for i∈[n]i∈[n]. For each i∈[n]i∈[n], we invoke the minimax oracle ϵO_ε on the fitted Q-function Qk∈ℱQ_k evaluated at the next state i′ s_i to obtain an approximate saddle-point action pair (~i,~i):=ϵ(Qk(i′,⋅,⋅))( u_i, v_i):=O_ε (Q_k( s_i ,·,·) ). Since QkQ_k is convex-concave from Equation 3, the minimax theorem guarantees that a saddle point of Qk(i′,⋅,⋅)Q_k( s_i ,·,·) exists, and ϵO_ε returns an ϵε-accurate approximation to it. We use (~i,~i)( u_i, v_i) to form the regression target yi=r(i,i,i)+γQk(i′,~i,~i)y_i=r( s_i, u_i, v_i)+γ Q_k( s_i , u_i, v_i), which serves as an empirical estimate of an approximate minimax Bellman operator from Equation 1 applied to the sampled tuple (i,i,i)( s_i, u_i, v_i). This approximation occurs because in practice, one can solve the minmax problem up to ϵε-accuracy instead of exactly. Finally, we update the Q-function estimate by solving a least-squares regression problem over ℱF: Qk+1:=argminf∈ℱL^n(f,Qk):=argminf∈ℱ1n∑i=1n(f(i,i,i)−yi)2.Q_k+1:= _f L_n(f;Q_k):= _f 1n _i=1^n (f( s_i, u_i, v_i)-y_i )^2. (4) Note that in Equation 4, the regression target yiy_i is treated as a constant independent of ℱF. Repeating this procedure for K iterations yields the final estimate QKQ_K returned by Algorithm 1. Sources of error in Algorithm 1. We now shift our focus to analyzing how the learned QKQ_K compares to the fixed point of the minimax Bellman operator Q∗Q^*. It is pertinent to note that Algorithm 1 departs from an exact Bellman iteration Qk+1=QkQ_k+1=TQ_k in three ways, which introduce three corresponding sources of error: (i) an optimization error from only being able to solve the minimax problem up to ϵε-accuracy with ϵO_ε, (i) an approximation error from restricting to the convex-concave function class ℱF, and (i) a statistical error from using finitely many samples per iteration. We now describe each in detail. First, because we solve the minimax problem in Equation 1 with ϵε-accuracy and not exactly, Algorithm 1 is better represented by the approximate minimax Bellman operator ~:M(×)→M(×) T:M (S×U×V )→ M (S×U×V ) defined by ~Q(,,)=r(,,)+γ′∼P(⋅|,,)[Q(′,ϵ(Q(′,⋅,⋅)))], TQ( s, u, v)=r( s, u, v)+ _ s P (·| s, u, v ) [Q ( s ,O_ε (Q ( s ,·,· ) ) ) ], (5) where use a slight abuse of notation by denoting Q(′,~,~)Q( s , u, v) where (~,~)=ϵ(Q(′,⋅,⋅))( u, v)=O_ε (Q( s ,·,·) ) as Q(′,ϵ(Q(′,⋅,⋅)))Q ( s ,O_ε(Q( s ,·,·)) ). Secondly, without additional assumptions on the Markov game, the approximate Bellman operator need not satisfy Bellman completeness, i.e., it is possible that for Q∈ℱQ , we have ~Q∉ℱ TQ . This motivates the fundamental approximation error δapprox:=supQ∈ℱinff∈ℱ‖f−~Q‖2,σ. _approx:= _Q _f \|f- TQ \|_2,σ. (6) The third error is statistical: because we only have n samples at each iteration, we can only perform an empirical approximate Bellman iteration. We will show how these affect the bound on ‖QK−Q∗‖2,ρ\|Q_K-Q^*\|_2,ρ for a distribution ρ∈(×)ρ (S×U×V), where Q∗Q^* is the fixed point of the exact Bellman operator T given in Equation 1. We now list our assumptions that hold throughout our analysis. Assumption 1 (State-Action Spaces). The continuous state and action spaces ,S,U and V are compact and convex, with D:=sup∈‖2<∞D_S:= _ s \| s\|_2<∞, D:=sup∈‖2<∞D_U:= _ u \| u\|_2<∞ and D:=sup∈‖2<∞D_V:= _ v \| v\|_2<∞. Assumption 2 (Reward Function). The immediate reward function r is continuous and ‖r‖∞≤Rmax<∞\|r\|_∞≤ R_max<∞. Further, r is LrL_r-Lipschitz in its actions, i.e., there exists Lr>0L_r>0 such that for all ∈ s , ,′∈ u, u , and ,′∈ v, v , |r(,,)−r(,′,′)|≤Lr(‖−′‖2+‖−′‖2). |r( s, u, v)-r( s, u , v )|≤ L_r (\| u- u \|_2+\| v- v \|_2 ). Assumption 3 (Transition Dynamics). For every bounded continuous function h:→ℝh:S , the map (,,)↦s′∼P(⋅∣,,)[h(′)]( s, u, v) _s P(· s, u, v)[h( s )] is continuous. Further, P is also LPL_P-Lipschitz in its actions, i.e.,, there exists LP>0L_P>0 such that for all ∈ s , ,′∈ u, u , ,′∈ v, v , and measurable sets S of S, P(S|,,)−P(S|,′,′)≤LP(‖−′‖2+‖−′‖2). P(S| s, u, v)-P(S| s, u , v )≤ L_P (\| u- u \|_2+\| v- v \|_2 ). Assumptions 1, 2 and 3 are standard in the literature and ensure that the Bellman operator T preserves continuity, admits a fixed point, and is Lipschitz continuous. Assumption 4 (Exploratory Distribution). There exists c>0c>0 such that exploratory sampling distribution σ has a conditional density p(,|)p( u, v| s) satisfying p(,|)≥c>0p( u, v| s)≥ c>0 for all ∈ s , ∈ u , ∈ v . Assumption 5 (Action Spaces Regularity). Consider a ball ℬ(,η)B( a,η) in the joint action space ×⊂ℝd+dU×V ^d_ u+d_ v centered at ∈× a ×V with radius η>0η>0. We assume there exists α>0α>0 such that λ(ℬ(,η)∩(×))≥min(α⋅αd+dηd+d,λ(×)). λ (B( a,η)∩(U×V) )≥ (α· _d_ u+d_ vη^d_ u+d_ v,λ (U×V ) ). Assumption 4 ensures that the action sampling distribution assigns positive mass to all regions of the players’ action spaces, and is satisfied by standard distributions used in reinforcement learning such as Gaussian and uniform distributions. Assumption 5 is a mild geometric condition on the players’ joint action spaces ruling out pathological geometries near the boundary, and is satisfied by convex action spaces. Assumption 6 (Convex-Concave Function Approximation). For the class of function approximators ℱF, every Q∈ℱQ satisfies: • Boundedness: ‖Q‖∞≤Qmax\|Q\|_∞≤ Q_max, with Qmax≥Rmax/1−γQ_max≥ R_max1-γ. • Convex-concavity: Q(,⋅,⋅)Q( s,·,·) is convex in u for fixed v and concave in v for fixed u, for every s. • Joint Lipschitzness: There exists a positive constant Lℱ<∞L_F<∞ such that for all Q∈ℱQ , |Q(,,)−Q(,′,′)|≤Lℱ(‖−′‖2+‖−′‖2)∀|Q( s, u, v)-Q( s, u , v )|≤ L_F (\| u- u \|_2+\| v- v \|_2 )~∀~ s and all ,′∈ u, u , ,′∈ v, v . Convexity-concavity in Assumption 6 is satisfied by the neural network architecture we introduce in Section 3 through construction. The Lipschitzness can be ensured by standard machine learning practices such as spectral normalization with bounded inputs (Miyato et al., 2018). Note that the same practices also ensure boundedness. We provide a Lipschitz bound for ℱF in Theorem 2 of Section C.2. Assumption 7 (Minimax Oracle). We have access to an oracle ϵ:×ℱ→×O_ε:S×F ×V, such that for any desired ϵ>0ε>0, for (πQ,μQ):=ϵ(,Q)( _Q, _Q):=O_ε( s,Q) we have |max∈Q(,πQ,)−min∈Q(,,μQ)|<ϵ∀∈,Q∈ℱ. | _ v Q ( s, _Q, v )- _ u Q ( s, u, _Q ) |<ε~∀~ s ,Q . Assumption 7 is satisfied for convex-concave, Lipschitz Q-functions by a variety of minimax optimization methods introduced in prior literature (Nemirovski, 2004; Lin et al., 2020). Assumption 8 (Discounted Concentrability Coefficients). For the sampling distribution σ∈(×)σ (S×U×V) with state marginal σ _S, let πjπ^j denote any Markov policy with πj:→×π^j:S ×V. Define the jthj^th-step concentrability coefficient for a distribution ν≪σν _S cj(ν):=supπ1,…,πj‖d(νPπ1⋯Pπj)dσ‖∞,c0(ν)=‖dνdσ‖∞,Cν:=(1−γ)∑j=0∞γjcj(ν), c_j(ν):= _π^1,…,π^j \| d(ν P^π^1·s P^π^j)d _S \|_∞, c_0(ν)= \| dνd _S \|_∞, C_ν:=(1-γ) _j=0^∞γ^jc_j(ν), with Pπj(⋅|):=P(⋅|,πj())P^π^j(·| s):=P(·| s,π^j( s)). Then, we assume that Cσ<∞C_ _S<∞. Assumption 8 quantifies the similarity between the sampling distribution σ and the future state distributions of the Markov game, and analogous versions of Assumption 8 are standard in reinforcement learning literature for both Markov decision processes and zero-sum Markov games (Antos et al., 2007; Munos and Szepesvári, 2008; Scherrer et al., 2015; Lazaric et al., 2016; Fan et al., 2020). To analyze the convergence of Algorithm 1, we assume that Q∗Q^* from Section 2 admits a pure-strategy saddle point, so that Algorithm 1 converges towards a meaningful equilibrium. We formally state this as follows. Assumption 9 (Saddle-point Existence). For every s∈s , min∈max∈Q∗(,,)=max∈min∈Q∗(,,) _ u _ v Q^*( s, u, v)= _ v _ u Q^*( s, u, v). We are now ready to state our main result. For the sampling distribution σ∈(×)σ (S×U×V), σ _S denotes the marginal of σ over S. Theorem 1. Under Assumptions 1, 2, 3, 4, 5, 6, 7, 8 and 9, let an evaluation distribution ρ∈()ρ (S) satisfy c0(ρ)=‖dρ/dσ‖∞≤Cρ,σ<∞c_0(ρ)=\| dρd _S\|_∞≤ C_ρ,σ<∞. Then for all δ>0δ>0, the output QKQ_K of Algorithm 1 after K iterations satisfies, with probability at least 1−δ1-δ ∼ρ[sup∈,∈|QK−Q∗|]≤2QmaxCρ,σ⋅γK+6CσCρ,σ(Lℱ+Lr+2γQmaxLP)η21−γ _ s ρ [ _ u , v |Q_K-Q^* | ]≤ 2Q_maxC_ρ,σ·γ^K+ 6C_ _SC_ρ,σ (L_F+L_r+2γ Q_maxL_P ) _21-γ +2CσCρ,σ(1−γ)cV(η2/2)(γϵ+δapprox2+5Δn(η1,δ3K)+4Qmax2log(3K/δ)2n+6Qmaxη1), + 2C_ _SC_ρ,σ(1-γ) cV ( _22 ) (γε+ _approx^2+5 _n ( _1, δ3K )+4Q_max^2 ( 3Kδ )2n+6Q_max _1 ), where Δn(η1,δ/3K):=4Qmax22log(6KN(η1)/δ)n+8Qmax2log(6KN(η1)/δ)3n+2Qmaxη1, _n ( _1, δ3K ):=4Q_max^2 2 ( 6KN( _1)δ )n+ 8Q_max^2 ( 6KN( _1)δ )3n+2Q_max _1, V(η2/2)=inf∈×λ(ℬ(,η2/2)∩(×))≥min(ααd+d(η2/2)d+d,λ(×))V( _22)= _ a ×Vλ (B( a, _22)∩(U×V) )≥ (α _d_ u+d_ v ( _22 )^d_ u+d_ v,λ (U×V ) ) from Assumption 5, N(η1):=N(ℱ,η1,∥⋅∥∞)N( _1):=N(F, _1,\|·\|_∞) is the covering number for the class of functions ℱF, and η1,η2>0 _1, _2>0 are chosen positive constants, and δapprox _approx is defined in Equation 6. The proof of Theorem 1 is in Appendix A. Theorem 1 decomposes the error sup∈,∈‖QK−Q∗‖ _ u , v \|Q_K-Q^*\| for some evaluation distribution ρ into several error sources. The first term is an algorithmic error that decays geometrically. The remaining terms capture the three error sources discussed above, and do not vanish with K, representing the fundamental difficulty of the problem. The ϵε term reflects the cost of using an ϵε-accurate solver as exact minimax solutions cannot be practically computed, and this term linearly vanishes with ϵε at the cost of more costly oracle computation. The presence of δapprox2 _approx^2 in the bound represents the cost of working with a restricted, tractable convex-concave function class ℱF. δapprox _approx will be 00 when the underlying game satisfies Bellman completeness. The terms (Δn(η1,δ/3K))O ( _n( _1, δ3K) ) and (log(3K/δ)/2n)O ( ( 3Kδ )2n ) correspond to the statistical error and quantify how fast the statistical error decays with the number of samples n and the covering number N(η1)N( _1) of ℱF. Unlike the finite-action setting, continuous action spaces cannot be covered exactly with finitely many samples. The parameters η1,η2>0 _1, _2>0 correspond to this covering tradeoff. Smaller η1,η2 _1, _2 lead to better approximation but higher covering number N(η1)N( _1) and larger inverse volume 1/V(η2/2) 1 V ( _22 ), which as mentioned in Theorem 1, depends exponentially on the dimension of the action spaces. The covering number N(η1)N( _1) depends on the particular architecture used to construct Q∈ℱQ and depends polynomially on the action space dimensions. We give a bound on N(η1)N( _1) for a particular architecture in Theorem 3 in Section C.3. To the best of our knowledge, Theorem 1 is the first finite-sample guarantee of this form for zero-sum Markov games with continuous state and action spaces beyond the linear quadratic setting. Theorem 1 also allows us to establish a bound on the Nash gap when players employ their security strategies (πQK,μQK) ( _Q_K, _Q_K ) induced by the learned Q-function QKQ_K. Corollary 1. Let ρ∈()ρ (S) be an evaluation distribution. Under Assumptions 1, 2, 3, 4, 5, 6, 7, 8 and 9, if Cρ<∞C_ρ<∞, the oracle-returned approximate security strategies (πQK(),μQK())=ϵ(,QK) ( _Q_K( s), _Q_K( s) )=O_ε ( s,Q_K ) corresponding to the output QKQ_K of Algorithm 1 satisfy NashGapρ(πQK,μQK)≤4Cρ1−γ∼σ[sup∈,∈|QK−Q∗|]+2ϵ1−γ. NashGap_ρ( _Q_K, _Q_K)≤ 4C_ρ1-γE_ s _S [ _ u , v |Q_K-Q^*| ]+ 2ε1-γ. The proof of Corollary 1 is in Appendix B. Importantly, Corollary 1 shows how the bounds developed in Theorem 1 can be used to bound the Nash gap itself. 5 Simulation Experiments We now complement our result from Theorem 1 with simulation experiments investigating whether the convex-concave Q-function neural network architecture introduced in Equation 3 leads to stable training in practice. The practical issue arises because one cannot implement Algorithm 1 exactly, since each iteration requires solving a non-convex regression problem of optimizing a neural network. We therefore empirically study a practical version of Algorithm 1 in which at each iteration, we take a gradient step on the empirical loss, mimicking online temporal difference (TD) learning. At iteration k of Algorithm 1, instead of getting Qk+1Q_k+1 from Equation 4, we have for a step-size α>0α>0 θk+1=θk−α∇θL^n(Qk,Qk),Qk+1=Qθk+1. _k+1= _k-α _θ L_n(Q_k;Q_k), Q_k+1=Q_ _k+1. We investigate whether this practical modification to Algorithm 1 trains stably with the convex-concave Q-function architecture of Equation 3. Markov Game Setup. We consider a planar pursuit-evasion game between two players in a 88-dimensional state space =[−2.5,2.5]8S=[-2.5,2.5]^8. At a state ∈ s , the first 44 components (s1,s2),(s3,s4)(s_1,s_2),(s_3,s_4) denote player 1’s planar position and velocity, and the last 44 components (s5,s6),(s7,s8)(s_5,s_6),(s_7,s_8) denote player 2’s planar position and velocity. Both players have 22-dimensional action spaces ,=[−1,1]2U,V=[-1,1]^2, and actions denote the players’ horizontal and vertical planar accelerations. Both players follow noisy double integrator dynamics ′=A+B1+B2+wnξ s =A s+B^1 u+B^2 v+w_nξ, where A=diag(Ap,Ap)A= diag(A_p,A_p), B1=[Bp;0]B^1= bmatrixB_p;0 bmatrix, B2=[0;Bp]B^2= bmatrix0;B_p bmatrix, ξ∼(0,I)ξ (0,I), Ap=[10Δt0010Δt00100001], and Bp=[12Δt20012Δt2Δt00Δt]. A_p= bmatrix1&0& t&0\\ 0&1&0& t\\ 0&0&1&0\\ 0&0&0&1 bmatrix, and B_p= bmatrix 12 t^2&0\\ 0& 12 t^2\\ t&0\\ 0& t bmatrix. Player 1 wishes to pursue player 2, who evades player 1, while both want the save their control effort and waste the other’s control effort. We encode this behavior with the immediate reward function r(,,)=−wexp(−((s1−s5)2+(s2−s6)2)2wd2)+12⊤R1−12⊤R2. r( s, u, v)=-w (- ((s_1-s_5)^2+(s_2-s_6)^2 )2w_d^2 )+ 12 u R^1 u- 12 v R^2 v. Note that this game lies beyond the linear-quadratic setting studied in prior work (Al-Tamimi et al., 2007a; Al-Tamimi et al., 2007b; Zhang et al., 2019; Zhang et al., 2021b; Bu et al., 2019), and the optimal Q-function cannot be found by using Riccati equations. We choose the sampling distribution σ=(Uni([−2.5,2.5]8)×Uni([−1,1]2)×Uni([−1,1]2))σ= (Uni ([-2.5,2.5]^8 )×Uni ([-1,1]^2 )×Uni ([-1,1]^2 ) ), with independent marginals. The discount factor γ is 0.950.95. We set w=0.01,wd=0.1,wn=0.01,Δt=0.1,R1=0.01Iw=0.01,w_d=0.1,w_n=0.01, t=0.1,R^1=0.01I and R2=0.02IR^2=0.02I. We use SecOND (Gupta et al., 2024), which is a second-order constraint-aware solver, as our minimax oracle ϵO_ε, as we found it to converge favorably in practice. Instead of setting an ϵε, we terminate the solver once successive candidate solution iterates differ by less than a tolerance of 10−810^-8. For convex-concave, Lipschitz Q-functions, this serves as a practical proxy for ϵε. We use the partially input convex-concave neural network as described in Section 3 for our choice of Q-function, with softplus activations. We empirically bound the value that the Q-function neural network outputs by clipping values to lie between [rmin/1−γ,rmax/1−γ][ r_min1-γ, r_max1-γ], and found that while in theory this breaks convexity-concavity, it did not harm performance in practice. Additional implementation details are provided in Appendix D. Along the iterations k, Figure 1 plots the normalized mean absolute error δNMAE:=1/n∑i=1n|Qk(i,i,i)−yi|(rmax−rmin)/1−γ, _NMAE:= 1n _i=1^n |Q_k( s_i, u_i, v_i)-y_i | (r_max-r_min )1-γ, where yiy_i is the regression target formed at iteration k of Algorithm 1 for the ithi^th data sample pair (i,i,i),i∈[n]( s_i, u_i, v_i),i∈[n], and the denominator (rmax−rmin)/1−γ (r_max-r_min )1-γ is the largest absolute error attainable given the bounded Q-value range derived above. Figure 1 shows that the TD-style modification of Algorithm 1 trains stably with the partially input convex-concave Q-function architecture. The error δNMAE _NMAE decreases and plateaus within the first 100100 iterations across all sample sizes we test. Across all 20 seeds, there is no divergence observed across the iterations. This empirically suggests that using the partially input convex-concave architecture from Equation 3 for the Q-function allows stable training. Though Theorem 1 does not directly apply to this practical version, we observe that both the error and its spread shrink as n increases from 100100 to 500500, which is consistent with the statistical benefit of larger per-iteration sample size n. 005050100100150150200200000.050.050.10.10.150.15Iteration kδNMAE _NMAEn=100n=100n=200n=200n=300n=300n=400n=400n=500n=500 Figure 1: The TD-style modification of Algorithm 1 trains stably with the partially input convex-concave Q-function architecture. Each curve shows the normalized mean absolute training error δNMAE _NMAE against iteration k, for n samples per iteration. Solid lines are the mean over 2020 random seeds and shaded bands show the min–max spread across seeds. An increase in n yields both lower steady-state error and lower variance. 6 Conclusion We study the learning of Q-functions in infinite-horizon zero-sum Markov games in continuous state and action spaces. Prior finite-sample guarantees of Q-function learning have largely been confined to either games with finite-actions or to continuous linear-quadratic games, where the agents have linear dynamics and quadratic rewards. A key challenge in extending the guarantees of these prior works to more general continuous-action zero-sum Markov games is that the associated Bellman equation involves a minimax problem that is not guaranteed to admit a tractable saddle-point solution in pure strategies. To address this issue, we introduce a class of neural network function approximation for Q which is convex-concave in the players’ actions, guaranteeing that the minimax problem admits a pure-strategy saddle point that can be computed efficiently by existing solvers. We study an online variant of the fitted Q-iteration algorithm employing this function class and establish, to the best of our knowledge, the first finite-sample guarantees for continuous state-action zero-sum Markov games beyond the linear-quadratic setting. Finally, we empirically validate that these convex-concave neural networks lead to stable training when used on a practical version of modified fitted Q-iteration. The empirical results naturally point to a future work direction of extending the finite-sample analysis for the practical temporal difference-style variant of Theorem 1 studied in Section 5, in which the exact regression step of Algorithm 1 is replaced by a single gradient step, as in Section 5. AI use statement In this work, we used generative AI tools for the following critical tasks: • Assist in a literature review about zero-sum continuous state-action Markov games. • Help in understanding the proof machinery of related papers, to see how can existing mathematical techniques be used in our work. These techniques were critical for proving our mathematical claims. • Help in implementing the practical version of Algorithm 1 for experiments in Section 5. We have not used generative AI tools for other tasks with required disclosure mentioned in the AI policy for authors like proof writing and developing conceptual frameworks. The rest of the required disclosure tasks are not applicable to this work. Additionally, we used generative AI tools for checking grammatical correctness of our writing. We have reviewed all AI-assisted work. For the tasks listed above, we took the following measures: • Any relevant paper suggested by an AI tool was manually screened to verify its relevance to our work. • The applicability of proof techniques from prior work that were suggested by AI tools were manually verified, and the proof was then manually done using these suggested techniques. • LLM-generated implementation was manually verified and tested. We take responsibility for the final content of this work, including text, claims or artifacts produced with the aid of generative AI. Ethics statement Our work deals with zero-sum game theory. Zero-sum games can be used for robust, safety-oriented applications, but the same techniques may be misused adversarially. Our work is mostly theoretical and does not directly enable any specific application that could be exploited in this manner. Reproducibility statement This work is mostly theoretical and all assumptions for the main Theorem 1 are listed before the theorem statement. The proofs of Theorem 1 and Corollary 1 are given in Appendix A and Appendix B respectively. Additional bounds and corresponding proofs are presented in Section C.2 and Section C.3. For our experiments, all details are presented in Section 5 and Appendix D. Code with running instructions can be found in the supplementary material. Acknowledgments DISTRIBUTION STATEMENT A. Approved for public release. Distribution is unlimited. This material is based upon work supported by the Under Secretary of War for Research and Engineering under Air Force Contract No. FA8702-15-D-0001 or FA8702-25-D-B002. Any opinions, findings, conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the Under Secretary of War for Research and Engineering. ©2026 Massachusetts Institute of Technology. Delivered to the U.S. Government with Unlimited Rights, as defined in DFARS Part 252.227-7013 or 7014 (Feb 2014). Notwithstanding any copyright notice, U.S. Government rights in this work are defined by DFARS 252.227-7013 or DFARS 252.227-7014 as detailed above. Use of this work other than as specifically authorized by the U.S. Government may violate any copyrights that exist in this work. Additionally, this work was also supported by the following: Army Research Office under Grant No. W911NF-23-1-0317, Office of Naval Research under Grant No. N00014-24-1-2797 and a National Science Foundation CAREER award under Grant No. 2336840 References Adam et al. (2021) L. Adam, R. Horčík, T. Kasl, and T. Kroupa Double oracle algorithm for computing equilibria in continuous games. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35, p. 5070–5077. Cited by: Remark 1. Al-Tamimi et al. (2007a) A. Al-Tamimi, M. Abu-Khalaf, and F. L. Lewis Adaptive critic designs for discrete-time zero-sum games with application to H∞H_∞ control. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 37 (1), p. 240–247. Cited by: §1, §5. Al-Tamimi et al. (2007b) A. Al-Tamimi, F. L. Lewis, and M. Abu-Khalaf Model-free q-learning designs for linear discrete-time zero-sum games with application to h-infinity control. Automatica 43 (3), p. 473–481. Cited by: §1, §5. Alacaoglu et al. (2022) A. Alacaoglu, L. Viano, N. He, and V. Cevher A natural actor-critic framework for zero-sum markov games. In International Conference on Machine Learning, p. 307–366. Cited by: §1. Amos et al. (2017) B. Amos, L. Xu, and J. Z. Kolter Input convex neural networks. In International conference on machine learning, p. 146–155. Cited by: Appendix C, Appendix C, Appendix C, 1st item, §3. Antos et al. (2007) A. Antos, C. Szepesvári, and R. Munos Fitted q-iteration in continuous action-space mdps. Advances in neural information processing systems 20. Cited by: §A.3, §1, §4. Başar and Olsder (1998) T. Başar and G. J. Olsder Dynamic noncooperative game theory. SIAM. Cited by: §1. Bu et al. (2019) J. Bu, L. J. Ratliff, and M. Mesbahi Global convergence of policy gradient for sequential zero-sum linear quadratic dynamic games. arXiv preprint arXiv:1911.04672. Cited by: §1, §5. Chen et al. (2024) Z. Chen, K. Zhang, E. Mazumdar, A. Ozdaglar, and A. Wierman Two-timescale q-learning with function approximation in zero-sum stochastic games. In Proceedings of the 25th ACM Conference on Economics and Computation, EC ’24, p. 378. Cited by: §1. Fan et al. (2020) J. Fan, Z. Wang, Y. Xie, and Z. Yang A theoretical analysis of deep q-learning. In Learning for dynamics and control, p. 486–489. Cited by: §1, §1, §4. Feng et al. (2024) S. Feng, M. Yin, Y. Wang, J. Yang, and Y. Liang Improving sample efficiency of model-free algorithms for zero-sum markov games. In Forty-first International Conference on Machine Learning, External Links: Link Cited by: §1. Glicksberg (1952) I. L. Glicksberg A further generalization of the kakutani fixed theorem, with application to nash equilibrium points. Proceedings of the American Mathematical Society 3 (1), p. 170–174. Cited by: Remark 1. Gupta et al. (2024) K. Gupta, X. Liu, R. Allen, U. Topcu, and D. Fridovich-Keil Second-order algorithms for finding local nash equilibria in zero-sum games. arXiv preprint arXiv:2406.03565. Cited by: §5. Jia et al. (2019) Z. Jia, L. F. Yang, and M. Wang Feature-based q-learning for two-player stochastic games. arXiv preprint arXiv:1906.00423. Cited by: §1. Lagoudakis and Parr (2002) M. G. Lagoudakis and R. Parr Value function approximation in zero-sum markov games. In Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence, UAI’02, p. 283–292. Cited by: §1. Lazaric et al. (2016) A. Lazaric, M. Ghavamzadeh, and R. Munos Analysis of classification-based policy iteration algorithms. Journal of Machine Learning Research 17 (19), p. 1–30. Cited by: §4. Lin et al. (2020) T. Lin, C. Jin, and M. I. Jordan Near-optimal algorithms for minimax optimization. In Conference on learning theory, p. 2738–2779. Cited by: §1, §2, §4. Miyato et al. (2018) T. Miyato, T. Kataoka, M. Koyama, and Y. Yoshida Spectral normalization for generative adversarial networks. arXiv preprint arXiv:1802.05957. Cited by: §4. Morimoto and Doya (2000) J. Morimoto and K. Doya Robust reinforcement learning. In Advances in Neural Information Processing Systems, T. Leen, T. Dietterich, and V. Tresp (Eds.), Vol. 13, p. . Cited by: §1. Munos and Szepesvári (2008) R. Munos and C. Szepesvári Finite-time bounds for fitted value iteration.. Journal of Machine Learning Research 9 (5). Cited by: §4. Nemirovski (2004) A. Nemirovski Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization 15 (1), p. 229–251. Cited by: §1, §2, §4. Perolat et al. (2015) J. Perolat, B. Scherrer, B. Piot, and O. Pietquin Approximate dynamic programming for two-player zero-sum markov games. In International Conference on Machine Learning, p. 1321–1329. Cited by: §1, §2. Pinto et al. (2017) L. Pinto, J. Davidson, R. Sukthankar, and A. Gupta Robust adversarial reinforcement learning. In International conference on machine learning, p. 2817–2826. Cited by: §1. Scherrer et al. (2015) B. Scherrer, M. Ghavamzadeh, V. Gabillon, B. Lesner, and M. Geist Approximate modified policy iteration and its application to the game of tetris. The Journal of Machine Learning Research 16 (1), p. 1629–1676. Cited by: §4. Shapley (1953) L. S. Shapley Stochastic games. Proceedings of the national academy of sciences 39 (10), p. 1095–1100. Cited by: §2. Sidford et al. (2020) A. Sidford, M. Wang, L. Yang, and Y. Ye Solving discounted stochastic two-player games with near-optimal time and sample complexity. In International Conference on Artificial Intelligence and Statistics, p. 2992–3002. Cited by: §1. Sion (1958) M. Sion On general minimax theorems.. Pacific Journal of Mathematics 8 (1), p. 171 – 176. Cited by: §2. Vershynin (2026) R. Vershynin High-dimensional probability: an introduction with applications in data science. 2 edition, Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge. Cited by: §A.1, §C.3. Xie et al. (2020) Q. Xie, Y. Chen, Z. Wang, and Z. Yang Learning zero-sum simultaneous-move markov games using function approximation and correlated equilibrium. In Conference on learning theory, p. 3674–3682. Cited by: §1. Zhang et al. (2019) K. Zhang, Z. Yang, and T. Basar Policy optimization provably converges to nash equilibria in zero-sum linear quadratic games. Advances in Neural Information Processing Systems 32. Cited by: §1, §5. Zhang et al. (2021a) K. Zhang, Z. Yang, H. Liu, T. Zhang, and T. Başar Finite-sample analysis for decentralized batch multiagent reinforcement learning with networked agents. IEEE Transactions on Automatic Control 66 (12), p. 5925–5940. Cited by: §1. Zhang et al. (2021b) Y. Zhang, Z. Yang, and Z. Wang Provably efficient actor-critic for risk-sensitive and robust adversarial rl: a linear-quadratic case. In International Conference on Artificial Intelligence and Statistics, p. 2764–2772. Cited by: §1, §5. Zhao et al. (2022) Y. Zhao, Y. Tian, J. Lee, and S. Du Provably efficient policy optimization for two-player zero-sum markov games. In International Conference on Artificial Intelligence and Statistics, p. 2736–2761. Cited by: §1. Zhou et al. (1996) K. Zhou, J. C. Doyle, K. Glover, et al. Robust and optimal control. Vol. 40, Prentice hall New Jersey. Cited by: §1. Appendix A Proof of Theorem 1 We will first list several classical results. Then, to prove Theorem 1, we establish a per-iteration error bound on Qk+1−QkQ_k+1-TQ_k in Appendix A.2, and in Appendix A.3 show how this bound propogates across iterations and leads to the final result of Theorem 1. A.1 Useful Concentration Inequalities We list two common concentration inequalities here that we use. A detailed background can be found in standard references, for example, Vershynin (2026). Fact 1 (Bernstein). If Z1,…,ZnZ_1,…,Z_n are i.i.d., [Zi]=0E[Z_i]=0, |Zi|≤b|Z_i|≤ b a.s., Var(Zi)≤τ2Var(Z_i)≤τ^2, then for every t>0t>0, ℙ(1n∑i=1nZi>t)≤exp(−nt2/2τ2+bt/3).P ( 1n _i=1^nZ_i>t )\;≤\; (- nt^2/2τ^2+bt/3 ). Equivalently, for every δ∈(0,1)δ∈(0,1), with probability ≥1−δ≥ 1-δ, we have 1n∑i=1nZi≤2τ2log(1/δ)n+2blog(1/δ)3n. 1n _i=1^nZ_i≤ 2τ^2 (1/δ)n+ 2b (1/δ)3n. Fact 2 (Hoeffding). If Zi,i∈[n]Z_i,i∈[n] are bounded random variables such that ai≤Zi≤bia_i≤ Z_i≤ b_i almost surely, then ∀t>0∀~t>0 P(1n∑i=1nZi−1n∑i=1nE[Zi])≤exp(−2n2t2∑i=1n(bi−ai)2). P ( 1n _i=1^nZ_i- 1n _i=1^nE [Z_i ] )≤ (- 2n^2t^2 _i=1^n(b_i-a_i)^2 ). Equivalently, for δ>0δ>0, we have with probability ≥1−δ≥ 1-δ 1n∑i=1nZi≤1n∑i=1nE[Zi]+∑i(bi−ai)2log(1/δ)2n2. 1n _i=1^nZ_i≤ 1n _i=1^nE [Z_i ]+ _i(b_i-a_i)^2 ( 1δ )2n^2. A.2 Per-iteration Error Bound We will first bound the per-iteration error incurred by Algorithm 1. For convenience we restate the minimax Bellman operator T from Equation 1 and approximate minimax Bellman operator ~ T from Equation 5: Q(,,)=r(,,)+γE′∼P(⋅|,,)[min~∈max~∈Q(′,~,~)], ( s, u, v )=r ( s, u, v )+γE_ s P(·| s, u, v) [ _ u _ v Q ( s , u, v ) ], ~Q(,,)=r(,,)+γE′∼P(⋅|,,)[Q(′,ϵ(Q(′,⋅,⋅)))]. TQ( s, u, v)=r( s, u, v)+γE_ s P (·| s, u, v ) [Q ( s ,O_ε(Q( s ,·,·)) ) ]. Let us define the error at iteration k as εk:=Qk+1−Qk _k:=Q_k+1-TQ_k. As mentioned in Section 4, besides the fact that we can only approximate QkTQ_k, there are additional sources of error: (i) the restriction of Qk+1∈ℱQ_k+1 , while Qk,~QkTQ_k, TQ_k need not belong to ℱF, and (i) a statistical error stemming from the use of finite samples. We decompose the error εk _k as εk _k =(Qk+1−~Qk)⏟statistics + approximation+(~Qk−Qk)⏟oracle bias = (Q_k+1- TQ_k )_statistics + approximation+ ( TQ_k-TQ_k )_oracle bias ⟹‖εk‖2,σ \| _k \|_2,σ ≤‖Qk+1−~Qk‖2,σ+‖~Qk−Qk‖2,σ. ≤ \|Q_k+1- TQ_k \|_2,σ+ \| TQ_k-TQ_k \|_2,σ. From the use of ϵO_ε and Assumption 7, the oracle bias is uniformly bounded. It is not difficult to see that ‖~Qk−Qk‖2,σ≤γϵ. \| TQ_k-TQ_k \|_2,σ≤γε. (7) We will now analyze the ‖Qk+1−~Qk‖2,σ\|Q_k+1- TQ_k\|_2,σ term. Let :=(,,)∈:=(×) x:=( s, u, v) :=(S×U×V). It is clear from Algorithm 1 that yiy_i is an unbiased conditional estimate of ~Qk(i,i,i)=~Qk(i) TQ_k( s_i, u_i, v_i)= TQ_k( x_i), i.e., yi=~Qk+ξiy_i= TQ_k+ _i, where E[ξ|Qk,i]=0E [ξ~|~Q_k, x_i ]=0. We define f¯k∈argminf∈ℱ‖f−~Qk‖2,σ. f_k∈ _f \|f- TQ_k \|_2,σ. It will be useful to quantify how close Qk+1Q_k+1 is to ~Qk TQ_k empirically for the batch of data samples compared to f¯k f_k. We formalize this in the next lemma. Lemma 1. From Algorithm 1, Qk+1=argminf∈ℱL^n(f,Qk)Q_k+1= _f L_n(f;Q_k) yields 1n∑i=1n(Qk+1(i)−~Qk(i))2≤1n∑i=1n(f¯(i)−~Qk(i))2+2n∑i=1nξi(Qk+1(i)−f¯(i)). 1n _i=1^n (Q_k+1( x_i)- TQ_k( x_i) )^2≤ 1n _i=1^n ( f( x_i)- TQ_k( x_i) )^2+ 2n _i=1^n _i (Q_k+1( x_i)- f( x_i) ). Proof. As Qk+1Q_k+1 is optimal for the regression problem at iteration k, we have L^n(Qk+1,Qk) L_n(Q_k+1;Q_k) ≤L^n(f¯k,Qk) ≤ L_n( f_k;Q_k) ⟹1n∑i(Qk+1(i)−yi)2 1n _i (Q_k+1( x_i)-y_i )^2 ≤1n∑i(f¯(i)−yi)2 ≤ 1n _i( f( x_i)-y_i)^2 ⟹1n∑i(Qk+1(i)−~Qk(i)−ξi)2 1n _i (Q_k+1( x_i)- TQ_k( x_i)- _i )^2 ≤1n∑i(f¯(i)−~Qk(i)−ξi)2 ≤ 1n _i( f( x_i)- TQ_k( x_i)- _i)^2 Opening squares, canceling the ξi _i terms and rearranging yields the claim. ∎ The ‖Qk+1−~Qk‖2,σ\|Q_k+1- TQ_k\|_2,σ term can be bounded by uniformly bounding the two right hand side terms of Lemma 1. We will first bound the term 2n∑i=1nξi(Qk+1(i)−f¯(i)) 2n _i=1^n _i (Q_k+1( x_i)- f( x_i) ). For f∈ℱf , let Zi(f):=ξi(f(i)−~Qk(i))Z_i(f):= _i (f( x_i)- TQ_k( x_i) ). Note that we can apply Bernstein’s inequality on ZiZ_i. To see this, E[Zi]=Ei[E[Zi|i]]=0E [Z_i ]=E_ x_i [E [Z_i| x_i ] ]=0, and from Assumptions 2 and 6, we have |yi|≤Qmax|y_i|≤ Q_max, |~Qk(i)|≤Qmax| TQ_k( x_i)|≤ Q_max, which implies |ξi|≤2Qmax| _i|≤ 2Q_max. Thus, |Zi(f)|≤2Qmax⋅‖f−~‖∞≤4Qmax2=:b |Z_i(f)|≤ 2Q_max·\|f- T\|_∞≤ 4Q_max^2=:b Further, we have Var(Zi(f))≤E[ξi2(f(xi)−~Qk(xi))2]≤4Qmax2‖f−~Qk‖2,σ2≤16Qmax4=:τ2 (Z_i(f))≤E [ _i^2(f(x_i)- TQ_k(x_i))^2 ]≤ 4Q_ ^2\,\|f- TQ_k\|_2,σ^2≤ 16Q_ ^4=:τ^2 Thus, for f∈ℱf , for δ′∈(0,1)δ ∈(0,1), we have with probability at least 1−δ′1-δ 1n∑iZi(f)≤4Qmax22log(1/δ′)n+8Qmax2log(1/δ′)3n 1n _iZ_i(f)≤ 4Q_max^2 2 (1/δ )n+ 8Q_max^2 (1/δ )3n To extend this statement uniformly to the whole family ℱF, for a fixed η1>0 _1>0, let N:=N(η1):=N(ℱ,η1,∥⋅∥∞)N:=N( _1):=N(F, _1,\|·\|_∞) be the minimal covering number of ℱF in the sup norm with associated cover f(1),…,f(N)\f^(1),…,f^(N)\. Note that f↦Zi(f)f Z_i(f) is 2Qmax2Q_max-Lipschitz in the sup norm. To see this, for f,f′∈ℱf,f , we have |Zi(f)−Zi(f′)|=|ξ⋅(f(i)−f′(i))|≤2Qmax‖f−f′‖∞|Z_i(f)-Z_i(f )|=|ξ· (f( x_i)-f ( x_i) )|≤ 2Q_max\|f-f \|_∞. Now, for each f∈ℱf , we have from the η1 _1-cover that ∃j∈[N]∃~j∈[N] such that ‖f−f(j)‖∞≤η1\|f-f^(j)\|_∞≤ _1. Thus, supf∈ℱ|1n∑iZi(f)|≤max1≤j≤N|1n∑iZi(f(j))|+2Qmaxη1. _f | 1n _iZ_i(f) |≤ _1≤ j≤ N | 1n _iZ_i(f^(j)) |+2Q_max _1. We can use the point wise bounds on the cover points f(j)f^(j) with δ′=δ/2N(η1)δ = δ2N( _1), where the factor of 2 comes because we bound the absolute value. Using the union bound yields with probability at least 1−δ1-δ supf∈ℱ|1n∑iZi(f)| _f | 1n _iZ_i(f) | ≤4Qmax22log(2N(η1)/δ)n+8Qmax2log(2N(η1)/δ)3n+2Qmaxη1 ≤ 4Q_max^2 2 (2N( _1)/δ)n+ 8Q_max^2 (2N( _1)/δ)3n+2Q_max _1 =:Δn(η1,δ). =: _n( _1,δ). (8) Thus, we have 2n∑iξi(Qk+1(i)−f¯k(i))=2n∑iZi(Qk+1)−2n∑iZi(f¯k)≤4Δn(η1,δ) 2n _i _i (Q_k+1( x_i)- f_k( x_i) )= 2n _iZ_i(Q_k+1)- 2n _iZ_i( f_k)≤ 4 _n( _1,δ) (9) We need to also connect the empirical LHS term of Lemma 1, 1n∑i=1n(Qk+1(i)−~Qk(i))2 1n _i=1^n (Q_k+1( x_i)- TQ_k( x_i) )^2 with the bound ‖Qk+1−~Qk‖2,σ2\|Q_k+1- TQ_k\|^2_2,σ. For f∈ℱf , let us define a centered random variable Xi:=(f(i)−~Qk(i))2−‖f−~Qk‖2,σ2. X_i:= (f( x_i)- TQ_k( x_i) )^2- \|f- TQ_k \|^2_2,σ. To analyze 1n∑i=1n(f¯(i)−~Qk(i))2 1n _i=1^n ( f( x_i)- TQ_k( x_i) )^2, we can again apply Bernstein’s inequality on for XiX_i. To see this, we have E[Xi]=0E [X_i ]=0, |Xi|=|(f(i)−~Qk(i))2−‖f−~Qk‖2,σ2|≤4Qmax2=b|X_i|= |(f( x_i)- TQ_k( x_i) )^2- \|f- TQ_k \|^2_2,σ |≤ 4Q_max^2=b, and Var(Xi)=Var((f(i)−~Qk(i))2)≤E[(f(i)−~Qk(i))4]≤16Qmax4=τ2Var(X_i)=Var ((f( x_i)- TQ_k( x_i))^2 )≤E [(f( x_i)- TQ_k( x_i))^4 ]≤ 16Q_max^4=τ^2. Also, the function h(f):=(f()−~Qk())2h(f):=(f( x)- TQ_k( x))^2 is 4Qmax4Q_max-Lipschitz in the sup norm as for f,f′∈ℱf,f , |h(f)−h(f′)|=|f()−f′()|⋅|f()+f′()−2~Qk()|≤4Qmax‖f−f′‖∞|h(f)-h(f )|=|f( x)-f ( x)|·|f( x)+f ( x)-2 TQ_k( x)|≤ 4Q_max\|f-f \|_∞. Analyzing similarly to ZiZ_i yields |1n∑i(f(i)−~Qk(i))2−‖f−~Qk‖2,σ2|≤Δn(η1,δ)+6Qmaxη1. | 1n _i (f( x_i)- TQ_k( x_i) )^2-\|f- TQ_k\|_2,σ^2 |≤ _n( _1,δ)+6Q_max _1. (10) We now analyze the term 1n∑i=1n(f¯(i)−~Qk(i))2 1n _i=1^n ( f( x_i)- TQ_k( x_i) )^2 from Lemma 1. Note that for each i, (f¯(i)−~Qk(i))2 ( f( x_i)- TQ_k( x_i) )^2 is i.i.d. with mean E∼σ[(f¯()−~Qk())2]=‖(f¯−~Qk)‖2,σ2≤δapprox2E_ x σ [ ( f( x)- TQ_k( x) )^2 ]= \| ( f- TQ_k ) \|^2_2,σ≤ _approx^2 from the definition of δapprox _approx from Equation 6. Also (f¯(i)−~Qk(i))2∈[0,4Qmax2] ( f( x_i)- TQ_k( x_i) )^2∈ [0,4Q_max^2 ]. Thus, we can make use of Hoeffding’s inequality. For δ>0δ>0, we have with probability at least 1−δ1-δ that 1n∑i(f¯k(i)−~Qk)2 1n _i ( f_k( x_i)- TQ_k )^2 ≤‖(f¯−~Qk)‖2,σ2+4Qmax2log(1/δ)2n ≤ \| ( f- TQ_k ) \|^2_2,σ+4Q_max^2 ( 1δ )2n ≤δapprox2+4Qmax2log(1/δ)2n. ≤ _approx^2+4Q_max^2 ( 1δ )2n. (11) We will now combine these inequalities to get a per iteration error bound on εk _k. Lemma 2 (Per iteration error bound). Under Assumptions 1, 2, 3, 4, 6 and 7, for δ>0δ>0, for εk=‖Qk+1−Qk‖ _k=\|Q_k+1-TQ_k\|, we have with probability at least ≥1−δ≥ 1-δ, the error at the kthk^th iteration ‖εk‖2,σ≤γϵ+δapprox2+5Δn(η1,δ3)+4Qmax2log(3/δ)2n+6Qmaxη1. \| _k\|_2,σ≤γε+ _approx^2+5 _n( _1, δ3)+4Q_max^2 ( 3δ )2n+6Q_max _1~. Proof. We have ‖Qk+1−~Qk‖2,σ2 \|Q_k+1- TQ_k\|_2,σ^2 ≤Equation 101n∑i(Qk+1(i)−~Qk(i))2+Δn(η1,δ)+6Qmaxη1 @crefcreftypecap~refnumeq: X_i bernstein≤ 1n _i (Q_k+1 ( x_i )- TQ_k ( x_i ) )^2+ _n( _1,δ)+6Q_max _1 ≤Lemma 11n∑i=1n(f¯(i)−~Qk(i))2+2n∑i=1nξi(Qk+1(i)−f¯(i)) @crefcreftypecap~refnumlemma: separation bound≤ 1n _i=1^n ( f( x_i)- TQ_k( x_i) )^2+ 2n _i=1^n _i (Q_k+1( x_i)- f( x_i) ) +Δn(η1,δ)+6Qmaxη1 + _n( _1,δ)+6Q_max _1 ≤112n∑i=1nξi(Qk+1(i)−f¯(i))+δapprox2+4Qmax2log(1/δ)2n @crefcreftypecap~refnumeq: f bar hoeffding≤ 2n _i=1^n _i (Q_k+1( x_i)- f( x_i) )+ _approx^2+4Q_max^2 ( 1δ )2n +Δn(η1,δ)+6Qmaxη1 + _n( _1,δ)+6Q_max _1 ≤Equation 9δapprox2+5Δn(η1,δ)+4Qmax2log(1/δ)2n+6Qmaxη1. @crefcreftypecap~refnumeq: cross term bernstein≤ _approx^2+5 _n( _1,δ)+4Q_max^2 ( 1δ )2n+6Q_max _1. ∎ A.3 Error Propogation Across Iterations We have so far a bound on ‖εk(,,)‖2,σ\| _k( s, u, v)\|_2,σ. For error propogation across iterations, we shall need a bound on ε¯k:=‖sup,εk(,,)‖2,σ _k:=\| _ u, v _k( s, u, v)\|_2,σ To that end, we have the following result for our setting, analogous to single-agent versions used in prior work (Antos et al., 2007). Lemma 3. Let f:×→Rf:S×U×V→R be such that ∀∈,f(,⋅,⋅)∀~ s ,f( s,·,·) is jointly LfL_f-Lipschitz and non-negative. Let ℬ(,η)B( a,η) denote an ℓ2 ^2 ball in ×U×V centered at ∈× a ×V with radius η. Then for η2>0 _2>0, we have E∼σ[sup,f(,,)2]≤4cV(η2/2)‖f(,,)‖2,σ2+3Lf2η22, E_ s _S [ _ u, vf( s, u, v)^2 ]≤ 4cV ( _22 )\|f( s, u, v)\|_2,σ^2+3L_f^2 _2^2, where V(η)V(η) is the lebesgue measure V(η)=inf∈×λ(ℬ(,η)∩(×))V(η)= _ a ×Vλ (B( a,η)∩(U×V) ). Proof. Let (j,j)j∈[N(η2)]\( u^j, v^j)\_j∈[N( _2)] be the minimal cover of ×U×V associated with η2>0 _2>0 in the ∥⋅∥2\|·\|_2 norm. Consider (,)( u, v) and let its closest cover point be (j,j)( u^j, v^j). Then we have |f(,,)−f(,j,j)|≤Lfη2 |f( s, u, v)-f( s, u^j, v^j) |≤ L_f _2 ⟹ |f(,,)|≤|f(,j,j)|+Lfη2 |f( s, u, v) |≤ |f( s, u^j, v^j) |+L_f _2 ⟹ sup,f(,,)2≤2maxjf(,j,j)2+2Lf2η22 _ u, vf( s, u, v)^2≤ 2 _jf( s, u^j, v^j)^2+2L_f^2 _2^2 (12) Now we bound maxjf(,j,j)2 _jf( s, u^j, v^j)^2. We have for (,)( u, v) in a radius η2/2 _22 around (j,j)( u^j, v^j), i.e., (,)∈ℬ((j,j),η2/2)( u, v) (( u^j, v^j), _22 ), that f(,,)−f(,j,j) f( s, u, v)-f( s, u^j, v^j) ≥−Lfη22 ≥- L_f _22 ⟹f(,,)2 f( s, u, v)^2 ≥(maxf(,j,j)−Lfη22,0)2 ≥ ( \f( s, u^j, v^j)- L_f _22,0 \ )^2 ≥f(,j,j)22−Lf2η224. ≥ f( s, u^j, v^j)^22- L_f^2 _2^24. Here we used that (maxa−b,0)2≥a2/2−b2 ( \a-b,0\ )^2≥ a^22-b^2 for positive a,ba,b. Now, ∥f(,,)∥2,p(⋅,⋅|s)2≥∫ℬ((j,j),η2/2)f(,,)2p(,|)d(,)\|f( s, u, v)\|_2,p(·,·|s)^2≥ _B (( u^j, v^j), _22 )f( s, u, v)^2p( u, v| s)d( u, v), meaning that ∃c>0∃~c>0 such that ∥f(,,)∥2,p(⋅,⋅|s)2 \|f( s, u, v)\|_2,p(·,·|s)^2 ≥∫ℬ((j,j),η2/2)f(,,)2p(,|)d(,)≥cV(η22)(f(,j,j)22−Lf2η224) ≥ _B (( u^j, v^j), _22 )f( s, u, v)^2p( u, v| s)d( u, v)≥ cV ( _22 ) ( f( s, u^j, v^j)^22- L_f^2 _2^24 ) (13) ⟹f(,j,j)2≤2cV(η2/2)∥f(,,)∥2,p(⋅,⋅|s)2+Lf2η222. f( s, u^j, v^j)^2≤ 2cV ( _22 )\|f( s, u, v)\|_2,p(·,·|s)^2+ L^2_f _2^22. (14) Combining 12 and 13, we get that sup,f(,,)2≤4cV(η2/2)∥f(,,)∥2,p(⋅,⋅|s)2+3Lf2η22 _ u, vf( s, u, v)^2≤ 4cV ( _22 )\|f( s, u, v)\|_2,p(·,·|s)^2+3L_f^2 _2^2 ⟹E∼σ[sup,f(,,)2]≤4cV(η2/2)‖f(,,)‖2,σ2+3Lf2η22. E_ s _S [ _ u, vf( s, u, v)^2 ]≤ 4cV ( _22 )\|f( s, u, v)\|_2,σ^2+3L_f^2 _2^2. This completes the proof. ∎ We shall use Lemma 3 to analyze error propagation across iterations. We define Dk:=Q∗−QkD_k:=Q^*-Q_k. Note that Dk+1=Q∗−Qk+1=Q∗−Qk+1−εkD_k+1=Q^*-Q_k+1=TQ^*-TQ_k+1- _k. Thus Dk+1(,,)=(Q∗−Qk)(,,)−εk(,,). D_k+1( s, u, v)= (TQ^*-TQ_k )( s, u, v)- _k( s, u, v). Let ek():=sup,|Dk(,,)|e_k( s):= _ u, v |D_k( s, u, v) |. Then, we have ∀s∈,ek+1()≤γsup,E′∼P(⋅|,,)[ek(′)]+sup,|εk(,,)|. ∀~s ,~e_k+1( s)≤γ _ u, vE_ s P(·| s, u, v) [e_k( s ) ]+ _ u, v | _k( s, u, v) |. At step K, for (0)∼σ s_(0) _S, we have eK((0))≤γsup(0),(0)E(1)∼P(⋅|,(0),(0))[eK−1((1))]+sup,|εK−1((0),,)| e_K( s_(0))≤γ _ u_(0), v_(0)E_ s_(1) P(·| s, u_(0), v_(0)) [e_K-1( s_(1)) ]+ _ u, v | _K-1( s_(0), u, v) | ≤γsup(0),(0)E(1)[γsup(1),(1)E(2)∼P(⋅|(1),(1),(1))[eK−2((2))]+sup,|εK−2((1),,)|] ≤γ _ u_(0), v_(0)E_ s_(1) [γ _ u_(1), v_(1)E_ s_(2) P(·| s_(1), u_(1), v_(1)) [e_K-2( s_(2)) ]+ _ u, v | _K-2( s_(1), u, v) | ] +sup,|εK−1((0),,)| + _ u, v | _K-1( s_(0), u, v) | ≤γ2sup(0),(0)E(1)[sup(1),(1)E(2)[eK−2((2))]]+γsup(0),(0)E(1)[sup,|εK−2((1),,)|] ≤γ^2 _ u_(0), v_(0)E_ s_(1) [ _ u_(1), v_(1)E_ s_(2) [e_K-2( s_(2)) ] ]+γ _ u_(0), v_(0)E_ s_(1) [ _ u, v | _K-2( s_(1), u, v) | ] +sup,|εK−1((0),,)| + _ u, v | _K-1( s_(0), u, v) | ⋮ ≤γKsup(0),(0)E(1)[sup(1),(1)E(2)[⋯sup(K−1),(K−1)E(K)[e0((K))]]] ≤γ^K _ subarrayc u_(0),\\ v_(0) subarrayE_ s_(1) [ _ subarrayc u_(1),\\ v_(1) subarrayE_ s_(2) [·s _ subarrayc u_(K-1),\\ v_(K-1) subarrayE_ s_(K) [e_0( s_(K)) ] ] ] +∑k=0K−2γK−1−ksup(0),(0)E(1)[⋯sup(K−2−k),(K−2−k)E(K−1−k)[sup,|εk((K−1−k),,)|]] + _k=0^K-2γ^K-1-k _ subarrayc u_(0),\\ v_(0) subarrayE_ s_(1) [·s _ subarrayc u_(K-2-k),\\ v_(K-2-k) subarrayE_ s_(K-1-k) [ _ u, v | _k( s_(K-1-k), u, v) | ] ] +sup,|εK−1((0),,)| + _ u, v | _K-1 ( s_(0), u, v ) | Consider the term e0e_0. We have ∀∈,e0()≤‖Dk‖∞≤2Qmax∀~ s ,e_0( s)≤\|D_k\|_∞≤ 2Q_max. For the second term, we have from Assumption 8 that E(0)∼σ[sup(0),(0)E(1)[⋯sup(K−2−k),(K−2−k)E(K−1−k)[sup,|εk((K−1−k),,)|]]] E_ s_(0) _S [ _ subarrayc u_(0),\\ v_(0) subarrayE_ s_(1) [·s _ subarrayc u_(K-2-k),\\ v_(K-2-k) subarrayE_ s_(K-1-k) [ _ u, v | _k( s_(K-1-k), u, v) | ] ] ] ≤cK−1−kE∼σ[sup,|εk(,,)|] ≤ c_K-1-kE_ s _S [ _ u, v | _k( s, u, v) | ] ≤cK−1−kE∼σ[sup,εk(,,)2],=cK−1−kε¯k ≤ c_K-1-k E_ s _S [ _ u, v _k( s, u, v)^2 ],=c_K-1-k _k (Jensen’s inequality (E[X])2≤E[X2](E[X])^2≤E[X^2]) where we write cj:=cj(σ)c_j:=c_j( _S). Thus, we have E∼σ[eK()]≤γK⋅2Qmax+∑k=0K−1γK−1−kcK−1−kε¯k E_ s σ [e_K( s) ]≤γ^K· 2Q_max+ _k=0^K-1γ^K-1-kc_K-1-k _k Now we have for ∈ s , ,′∈ u, u and ,′∈ v, v |εk(,,)−εk(,′,′)| | _k( s, u, v)- _k( s, u , v ) | ≤|Qk(,′,′)−Qk(,,)|+|Qk(,′,′)−Qk(,,)| ≤ |Q_k( s, u , v )-Q_k( s, u, v) |+ |TQ_k( s, u , v )-TQ_k( s, u, v) | ≤Lℱ‖(,)−(′,′)‖2+|r(,′,′)−r(,,)| ≤ L_F\|( u, v)-( u , v )\|_2+ |r( s, u , v )-r( s, u, v) | +γ|∫min~∈max~∈Qk(′,~,~)(P(d′|,)−P(d′|′,′))| +γ | _ u _ v Q_k( s , u, v) (P(d s | u, v)-P(d s | u , v ) ) | ≤2(Lℱ+Lr+2γQmaxLP)⏟:=Lε∥(,)−(′,′)∥2, ≤ 2 (L_F+L_r+2γ Q_maxL_P )_:=L_ \|( u, v)-( u , v )\|_2, implying that εk _k is Lε:=2(Lℱ+Lr+2γQmaxLP)L_ := 2 (L_F+L_r+2γ Q_maxL_P )-Lipschitz in the joint actions. Thus from Lemma 3, we have for ε¯k=‖sup,|εk(,,)|‖2,σ _k=\| _ u, v| _k( s, u, v)|\|_2,σ for η2>0 _2>0 ε¯k2 _k^2 ≤4cV(η2/2)‖εk‖2,σ2+3Lε2η22 ≤ 4cV ( _22 )\| _k\|_2,σ^2+3L_ ^2 _2^2 ⟹ε¯k _k ≤2cV(η2/2)‖εk‖2σ+3Lεη2. ≤ 2 cV ( _22 )\| _k\|_2σ+ 3L_ _2. Thus, for δ>0δ>0, from Lemma 2, using the union bound for k iterations, we have with probability at least 1−δ1-δ ∀k∈[K],ε¯k≤ ∀~k∈[K], _k≤ 3Lεη2+2cV(η2/2)(γϵ+δapprox2+5Δn(η1,δ3K)+4Qmax2log(3K/δ)2n+6Qmaxη1)⏟:=b 3L_ _2+ 2 cV ( _22 ) (γε+ _approx^2+5 _n ( _1, δ3K )+4Q_max^2 ( 3Kδ )2n+6Q_max _1 )_:=b This yields that with probability at least 1−δ1-δ E∼σ[eK()] E_ s σ [e_K( s) ] ≤γK⋅2Qmax+∑k=0K−1γK−1−kcK−1−k⋅b ≤γ^K· 2Q_max+ _k=0^K-1γ^K-1-kc_K-1-k· b ≤γK⋅2Qmax+Cσ1−γb ≤γ^K· 2Q_max+ C_ _S1-γb ⟹E∼ρ[eK()] E_ s ρ [e_K( s) ] ≤γK⋅2QmaxCρ,σ+CσCρ,σCσ1−γb, ≤γ^K· 2Q_maxC_ρ,σ+C_ _S C_ρ,σC_ _S1-γb, (dρ/dσ≤Cρ,σ dρdσ≤ C_ρ,σ) where in the last step we used Eρ[g]≤Cρ,σEσ[g]E_ρ[g]≤ C_ρ,σE_σ[g] for non-negative g by the definition of Cρ,σC_ρ,σ from the statement of Theorem 1. This completes the proof for Theorem 1. Appendix B Proof of Corollary 1 Let us denote the true security strategies corresponding to Q∈ℱQ as πQ∗()∈argmin∈max∈Q(,,)π^*_Q( s)∈ _ u _ v Q( s, u, v) and μQ∗()∈argmax∈min∈Q(,,)μ^*_Q( s)∈ _ v _ u Q( s, u, v). We will first bound the entity maxμ′VπQK,μ′−V∗ _μ V _Q_K,μ -V^*. Consider any state s and Markov policy μ′μ . Let eK():=sup∈,∈|QK(,,)−Q∗(,,)|e_K( s):= _ u , v |Q_K( s, u, v)-Q^*( s, u, v) |. Now consider the difference Δ~():=VπQK,μ′()−V∗()=VπQK,μ′()−Q∗(,πQK,μ′())+Q∗(,πQK,μ′())−V∗() ( s):=V _Q_K,μ ( s)-V^*( s)=V _Q_K,μ ( s)-Q^*( s, _Q_K,μ ( s))+Q^*( s, _Q_K,μ ( s))-V^*( s). From the definition of V and Q∗Q^* we have VπQK,μ′()−Q∗(,πQK,μ′()) V _Q_K,μ ( s)-Q^*( s, _Q_K,μ ( s)) =γE1∼P(⋅|,πQK(),μ′())[VπQK,μ′(1)−V∗(1)] =γE_ s_1 P(·| s, _Q_K( s),μ ( s)) [V _Q_K,μ ( s_1)-V^*( s_1) ] =γE1∼P(⋅|,πQK(),μ′())[Δ~(1)] =γE_ s_1 P(·| s, _Q_K( s),μ ( s)) [ ( s_1) ] Thus we have the recursion Δ~()=Q∗(,πQK,μ′())−V∗()+γE1∼P(⋅|,πQK(),μ′())[Δ~(1)]. ( s)=Q^*( s, _Q_K,μ ( s))-V^*( s)+γE_ s_1 P(·| s, _Q_K( s),μ ( s)) [ ( s_1) ]. This yields VπQK,μ′()−V∗() V _Q_K,μ ( s)-V^*( s) =∑t=0∞γtEt|(0=,πQK,μ′)[Q∗(t,πQK(t),μ′(t))−V∗(t)], = _t=0^∞γ^tE_ s_t|( s_0= s, _Q_K,μ ) [Q^*( s_t, _Q_K( s_t),μ ( s_t))-V^*( s_t) ], (15) where we use Et|(0=,πQK,μ′)E_ s_t|( s_0= s, _Q_K,μ ) as shorthand to denote the iterated expectation over the states from 0 s_0 to t s_t under player policies πQK _Q_K and μ′μ . To bound Q∗(,πQK(),μ′())−V∗()Q^*( s, _Q_K( s),μ ( s))-V^*( s). We have that Q∗(,πQK(),μ′()) Q^*( s, _Q_K( s),μ ( s)) ≤Q∗(,πQK,~),~∈argmax∈Q∗(,πQK,) ≤ Q^*( s, _Q_K, v),~ v∈ _ v Q^*( s, _Q_K, v) ≤QK(,πQK,~)+eK() ≤ Q_K( s, _Q_K, v)+e_K( s) ≤max∈QK(,πQK,)+eK() ≤ _ v Q_K( s, _Q_K, v)+e_K( s) ≤min∈QK(,,μQK)+eK()+ϵ ≤ _ u Q_K( s, u, _Q_K)+e_K( s)+ε ≤QK(,~,μQK)+eK()+ϵ,~∈argmin∈Q∗(,,μQK) ≤ Q_K( s, u, _Q_K)+e_K( s)+ε, u∈ _ u Q^*( s, u, _Q_K) ≤Q∗(,~,μQK)+2eK()+ϵ ≤ Q^*( s, u, _Q_K)+2e_K( s)+ε =min∈Q∗(,,μQK)+2eK()+ϵ = _ u Q^*( s, u, _Q_K)+2e_K( s)+ε ≤max∈min∈Q∗(,,)⏟=V∗()+2eK()+ϵ ≤ _ v _ u Q^*( s, u, v)_=V^*( s)+2e_K( s)+ε Using this in Equation 15, we get VπQK,μ′()−V∗()≤∑t=0∞γtEt|(0=,πQK,μ′)[2eK(t)+ϵ], V _Q_K,μ ( s)-V^*( s)≤ _t=0^∞γ^tE_ s_t|( s_0= s, _Q_K,μ ) [2e_K( s_t)+ε ], From Assumption 8, we have E∼ρ[eK(t)]≤ct(ρ)E∼σ[eK(t)]E_ s ρ [e_K( s_t) ]≤ c_t(ρ)E_ s _S [e_K( s_t) ]. Thus ∑t=0∞γtE∼ρ[2eK(t)+ϵ] _t=0^∞γ^tE_ s ρ [2e_K( s_t)+ε ] ≤∑t=0∞γt(2ct(ρ)E∼σ[eK()]+ϵ) ≤ _t=0^∞γ^t (2c_t(ρ)E_ s _S [e_K( s) ]+ε ) ≤2Cρ1−γE∼σ[eK()]+ϵ1−γ. ≤ 2C_ρ1-γE_ s _S [e_K( s) ]+ ε1-γ. Thus we have E∼ρ[VπQK,μ′()−V∗()]≤2Cρ1−γE∼σ[eK()]+ϵ1−γ E_ s ρ [V _Q_K,μ ( s)-V^*( s) ]≤ 2C_ρ1-γE_ s _S [e_K( s) ]+ ε1-γ ⟹E∼ρ[maxμ′VπQK,μ′()−V∗()]≤2Cρ1−γE∼σ[eK()]+ϵ1−γ. E_ s ρ [ _μ V _Q_K,μ ( s)-V^*( s) ]≤ 2C_ρ1-γE_ s _S [e_K( s) ]+ ε1-γ. (16) Similarly, for a policy π′π , let us define Δ~′():=V∗()−Vπ′,μQK()=V∗()−Q∗(,π′,μQK)+Q∗(,π′,μQK)−Vπ′,μQK() ( s):=V^*( s)-V^π , _Q_K( s)=V^*( s)-Q^*( s,π , _Q_K)+Q^*( s,π , _Q_K)-V^π , _Q_K( s). From the definition of V∗,Q∗V^*,Q^*, Q∗(,π′,μQK)−Vπ′,μQK() Q^*( s,π , _Q_K)-V^π , _Q_K( s) =γE1∼P(⋅|,πQK,μ′)[V∗(1)−Vπ′,μQK(1)] =γE_ s_1 P(·| s, _Q_K,μ ) [V^*( s_1)-V^π , _Q_K( s_1) ] =γE1∼P(⋅|,πQK,μ′)[Δ~′(1)]. =γE_ s_1 P(·| s, _Q_K,μ ) [ ( s_1) ]. This gives the recursion Δ~′()=V∗()−Q∗(,π′,μQK)+γE1∼P(⋅|,πQK,μ′)[Δ~′(1)], ( s)=V^*( s)-Q^*( s,π , _Q_K)+γE_ s_1 P(·| s, _Q_K,μ ) [ ( s_1) ], which yields V∗()−Vπ′,μQK()=∑t=0∞γtEt|(0=,πQK,μ′)[V∗(t)−Q∗(t,π′(t),μQK(t))] V^*( s)-V^π , _Q_K( s)= _t=0^∞γ^tE_ s_t|( s_0= s, _Q_K,μ ) [V^*( s_t)-Q^*( s_t,π ( s_t), _Q_K( s_t)) ] (17) To bound V∗()−Q∗(,π′(),μQK())V^*( s)-Q^*( s,π ( s), _Q_K( s)), similar to before we have Q∗(,π′(),μQK()) Q^*( s,π ( s), _Q_K( s)) ≥Q∗(,~,μQK()),~∈argminQ∗(,,μQK()) ≥ Q^*( s, u, _Q_K( s)), u∈ _ uQ^*( s, u, _Q_K( s)) ≥QK(,~,μQK())−eK() ≥ Q_K( s, u, _Q_K( s))-e_K( s) ≥min∈QK(,,μQK())−eK() ≥ _ u Q_K( s, u, _Q_K( s))-e_K( s) ≥max∈QK(,πQK,)−eK()−ϵ ≥ _ v Q_K( s, _Q_K, v)-e_K( s)-ε ≥QK(,πQK,~)−eK()−ϵ,~∈argmax∈Q∗(,πQK(),) ≥ Q_K( s, _Q_K, v)-e_K( s)-ε,~ v∈ _ v Q^*( s, _Q_K( s), v) ≥Q∗(,πQK,~)−2eK()−ϵ ≥ Q^*( s, _Q_K, v)-2e_K( s)-ε =max∈Q∗(,πQK,)−2eK()−ϵ = _ v Q^*( s, _Q_K, v)-2e_K( s)-ε ≥min∈max∈Q∗(,,)⏟:=V∗()−2eK()−ϵ ≥ _ u _ v Q^*( s, u, v)_:=V^*( s)-2e_K( s)-ε ⟹V∗() V^*( s) ≤Q∗(,π′(),μQK())+2eK()+ϵ. ≤ Q^*( s,π ( s), _Q_K( s))+2e_K( s)+ε. Using in Equation 17, we get V∗()−Vπ′,μQK()≤∑t=0∞γtEt|(0=,πQK,μ′)[2eK(t)+ϵ]. V^*( s)-V^π , _Q_K( s)≤ _t=0^∞γ^tE_ s_t|( s_0= s, _Q_K,μ ) [2e_K( s_t)+ε ]. From similar analysis as previously, this yields for ∼ρ s ρ E∼ρ[V∗()−minπ′Vπ′,μQK()]≤2Cρ1−γE∼σ[eK()]+ϵ1−γ E_ s ρ [V^*( s)- _π V^π , _Q_K( s) ]≤ 2C_ρ1-γE_ s _S [e_K( s) ]+ ε1-γ (18) Combining Equations 16 and 18, we get for ∼ρ s ρ E∼ρ[maxμ′VπQK,μ′()−minπ′Vπ′,μQK()] E_ s ρ [ _μ V _Q_K,μ ( s)- _π V^π , _Q_K( s) ] ≤4Cρ1−γE∼σ[eK()]+2ϵ1−γ ≤ 4C_ρ1-γE_ s _S [e_K( s) ]+ 2ε1-γ ⟹NashGapρ(πQK,μQK) NashGap_ρ( _Q_K, _Q_K) ≤4Cρ1−γE∼σ[sup∈,∈|QK−Q∗|]+2ϵ1−γ ≤ 4C_ρ1-γE_ s _S [ _ u , v |Q_K-Q^*| ]+ 2ε1-γ Appendix C On Partially Input Convex-Concave Neural Network Architecture In this section, we describe the architecture underlying the function class ℱF of Section 3. Throughout, we use the softplus action function φ(x):=log(1+ex) (x):= (1+e^x) applied entrywise to vectors and matrices. Softplus satisfies the PICNN requirement of being convex and non-decreasing in the input required for guaranteeing desirable convexity in the partial input (Amos et al., 2017). We first review the PICNN architecture. Partially Input Convex Neural Networks (Amos et al., 2017) Fix i∈1,2i∈\1,2\ and write (,)=(,)( x, y)=( s, u) for i=1i=1 and (,)=(,)( x, y)=( s, v) for i=2i=2. For convenience, we assume both blocks NθiiN^i_θ^i, i∈1,2i∈\1,2\ have hidden width m for the convex path corresponding to y and p for the state path corresponding to x, and depth L. All results presented here follow for different, network specific choices of m,pm,p as well. The architecture involves two recursions, one related with the state path, denoted by hih^i, and the other related with the convex path, denoted by ziz^i, give by h0i:=,hℓ+1i h^i_0:= x, h^i_ +1 =φ(W~ℓihℓi+b~ℓi), = ( W^i_ \,h^i_ + b^i_ ), (19) zi0=,ziℓ+1=φ(W(z),iℓ(ziℓ⊙ z^i_0= 0, z^i_ +1= (W^(z),i_ (z^i_ OPENφ(Wℓ(zh),ihℓi+bℓ(z),i))+ (W^(zh),i_ h^i_ +b^(z),i_ ) )~+ W(y),iℓ(⊙ W^(y),i_ ( y OPENOPEN(Wℓ(yh),ihℓi+bℓ(y),i))+Wℓ(h),ihℓi+bℓi), (W^(yh),i_ \,h^i_ +b^(y),i_ ) )+W^(h),i_ \,h^i_ +b^i_ ), Ni(,)=(wi)⊤zLi, N^i( x, y)=(w^i) z^i_L, whereℓ=0,…,L−1. ~ =0,…,L-1. Convexity of y↦Nθi(,)y N^i_ _i( x, y) requires Wℓ(z),iW^(z),i_ and wiw^i to have non-negative entries (Amos et al., 2017). This can be done in multiple ways, for example, by projecting the WℓiW^i_ and wiw^i parameters to the non-negative set while training. In our work, to ensure smoothness, we enforce non-negativity through unconstrained reparameterization where one can optimize over free parameters W~ℓ(z),i∈ℝm×m W^(z),i_ ^m× m and w~i∈ℝm w^i ^m and set Wℓ(z),i=φ(W~ℓ(zh),i),wi=φ(w~i)W^(z),i_ = ( W^(zh),i_ ), w^i= ( w^i ) (20) Equation 19 implies that the network NiN^i has |θi|:=L(m2+md+2m+d)+m+pd+(p2+2mp+pd)(L−1)+pL+2md+dd aligned |θ^i|:=&L(m^2+md_ y+2m+d_ y)+m+pd_ s+(p^2+2mp+pd_ y)(L-1)+pL\\ &+2md_ s+d_ yd_ s aligned (21) parameters, with d=d_ y=d_ u for i=1i=1 and d=d_ y=d_ v for i=2i=2. We use this partially input convex NiN^i to construct our Q-function, as described in Equation 3, which we restate here Qθ(,,)=Nθ11(,)−Nθ22(,)+⊤Mθ3(),θ=(θ1,θ2,θ3)∈Θ.Q_θ( s, u, v)=N^1_θ^1( s, u)-N^2_θ^2( s, v)+ u M_θ^3( s)\, v, θ=(θ^1,θ^2,θ^3)∈ . (22) Here, Θ is a convex set with ‖θ‖2≤BΘ∀θ∈Θ\|θ\|_2≤ B_ ~∀~θ∈ . We take M()M( s) as a standard feedforward network given by h0M=,hℓ+1M=φ(WℓMhℓM+bℓM),ℓ=0,⋯,LM−1,vec(M):=WouthLMM, h^M_0= s, h^M_ +1= (W_ ^Mh_ ^M+b_ ^M),~ =0,·s,L_M-1, vec(M):=W_outh^M_L_M, (23) where we take the hidden width as pMp_M. For convenience, we take the activation functions for M to be the same as NiN^i, though M can have any 11-Lipschitz activation alternatives such as ReLU. Our construction exploits two elementary properties of the softplus function φ . Equation 23 implies that M has |θ3|=pMLM+(LM−1)pM2+pMd+pMdd |θ^3|=p_ML_M+(L_M-1)p_M^2+p_Md_ s+p_Md_ ud_ v (24) parameters. Thus, QθQ_θ has |θ1|+|θ2|+|θ3||θ^1|+|θ^2|+|θ^3| total parameters. Lemma 4. Let φ(t)=log(1+et) (t)= (1+e^t). Then (i) φ is 11-Lipschitz, strictly increasing and convex; (i) for every ∈ℝm a ^m, with φ applied entrywise, ‖φ()‖2≤‖2+mlog2\;\| ( a)\|_2≤\| a\|_2+ m 2. Proof. (i) is immediate from φ′(t)=et/(1+et)∈(0,1) (t)=e^t/(1+e^t)∈(0,1), and convexity follows from φ′>0 >0. For (i), let ∈ℝm 1 ^m be the all-ones vector and note φ(0)=log2 (0)= 2. By (i) each coordinate obeys |φ(aj)−log2|≤|aj|| (a_j)- 2|≤|a_j|, so ‖φ()−(log2)‖22=∑j(φ(aj)−φ(0))2≤∑jaj2=‖22\| ( a)-( 2) 1\|_2^2= _j( (a_j)- (0))^2≤ _ja_j^2=\| a\|_2^2. The triangle inequality gives ‖φ()‖2≤‖φ()−(log2)‖2+‖(log2)‖2≤‖2+mlog2\| ( a)\|_2≤\| ( a)-( 2) 1\|_2+\|( 2) 1\|_2≤\| a\|_2+ m 2. ∎ The following assumption will be required to establish output and Lipschitz bounds, and is standard in neural network literature. Assumption 10 (Bounded inputs and weights). There exist finite positive constants BW,Bb,Bw,BMB_W,B_b,B_w,B_M and D_S such that: 1. For any weight matrix W and bias vector b in Equation 19, the spectral norm ‖W‖2≤BW\|W\|_2≤ B_W and ℓ2 ^2-norm ‖b‖2≤Bb\|b\|_2≤ B_b. 2. The output weights wiw^i satisfy ‖wi‖2≤Bw\|w^i\|_2≤ B_w. Assumption 10 allows us to establish the Lipschitzness (with respect to the convex input) of a single PICNN NiN^i as described in Equation 19. C.1 Notation for Lipschitz and covering number bounds. Besides the constants in Assumption 10, we use several other notations throught the rest of this Section. For a scalar t∈ℝt , let the function G(t,j)G(t,j) denote the sum G(t,j)=∑k=0jtkG(t,j)= _k=0^jt^k. From eq. 19, for NiN^i, we refer to the pre-activation layer of the convex path as aℓ+1ia^i_ +1, i.e., zℓ+1i=φ(aℓ+1i)z^i_ +1= (a^i_ +1), and we denote Dℓ+1i:=diag(φ′(aℓ+1i))D^i_ +1:=diag ( (a^i_ +1) ) for all ℓ∈0,…,L−1 ∈\0,…,L-1\. Similarly, for all ℓ∈0,…,L−1 ∈\0,…,L-1\, we refer to the pre-activation layer of the state path as a~ℓ+1i:=W~ℓihℓi+b~ℓi a^i_ +1:= W^i_ h^i_ + b^i_ , and define D~ℓ+1i:=diag(φ′(a~ℓ+1i)) D^i_ +1:= diag ( ( a^i_ +1) ). For each layer ℓ of the PICNN NiN^i, we denote the vectors dependent only on x as cℓ(z):=φ(Wℓ(zh),ihℓi+bℓ(z),i)∈ℝ≥0m,cℓ(y):=Wℓ(yh),ihℓi+bℓ(y),i∈ℝd, c^(z)_ := (W^(zh),i_ h^i_ +b^(z),i_ ) ^m_≥ 0, c^(y)_ \;:=\;W^(yh),i_ h^i_ +b^(y),i_ ^d_ y, with ‖cℓ(z)‖∞,‖cℓ(y)‖∞≤BWH+Bb+log2=:C\|c^(z)_ \|_∞,\|c^(y)_ \|_∞≤ B_WH+B_b+ 2=:C, where H is defined in Lemma 5, and BW,BbB_W,B_b defined in Assumption 10. We also denote ρ:=BW(C)ρ:=B_W(C), and CZ=BWH+Bb+mlog2C_Z=B_WH+B_b+ m 2. Finally, BΘB_ is a positive constant such that ‖θ‖2≤BΘ∀θ∈Θ\|θ\|_2≤ B_ ~∀~θ∈ . C.2 Lipschitz Bounds on Partially Input Convex-Conave Neural Network Lemma 5 (Lipschitzness of PICNN). Under Assumptions 1 and 10, a single PICNN Nθi(,N^i_θ( x, y) as described in Equation 19 is LNL_N-Lipschitz in the input y, where LN=Bw⋅ρ⋅G(ρ,L−1) L_N=B_w·ρ· G(ρ,L-1) where ρ=BW(BWH+Bb+log2)ρ=B_W(B_WH+B_b+ 2) from Section C.1 and H is defined as H=max(D,(BW)LD+(Bb+plog2)⋅G(BW,L)), H= (D_S,(B_W)^LD_S+(B_b+ p 2)· G(B_W,L) ), and D=sup∈‖2<∞D_S= _ s \| s\|_2<∞ from Assumption 1. Proof. We will first show that ‖hℓi‖2≤H\|h^i_ \|_2≤ H for all ℓ∈[L] ∈[L] and ∈ s . From Equation 19, we have ‖h0i‖2=‖≤D\|h^i_0\|_2=\| s\|≤ D_S, and ‖hℓ+1i‖2=‖φ(W~ℓihℓi+b~ℓi)‖2≤BW‖hℓi‖2+Bb+plog2. \|h^i_ +1\|_2= \| ( W^i_ \,h^i_ + b^i_ ) \|_2≤ B_W\|h^i_ \|_2+B_b+ p 2. Unrolling this yields H. For each layer ℓ , considering the vectors dependent only on x, we have ‖cℓ(z)‖∞≤‖Wℓ(zh),ihℓi+bℓ(z),i‖2≤BWH+Bb+log(2)\|c^(z)_ \|_∞≤\|W^(zh),i_ h^i_ +b^(z),i_ \|_2≤ B_WH+B_b+ (2). Similarly, ‖cℓ(y)‖∞≤BWH+Bb\|c^(y)_ \|_∞≤ B_WH+B_b. For fixed x, the vectors cℓ(z)c^(z)_ and cℓ(y)c^(y)_ can be treated as constants independent of y. Then, the forward pass reduces to: zℓ+1i=φ(Wℓ(z),idiag(cℓ(z))zℓi+Wℓ(y),idiag(cℓ(y))+constant in ). z^i_ +1= (W^(z),i_ \,diag (c^(z)_ )z^i_ +W^(y),i_ \,diag (c^(y)_ ) y+constant in y ). Let Jℓ:=‖∂zℓi/∂‖2J_ :=\|∂ z^i_ /∂ y\|_2. Differentiating through φ , since φ′∈(0,1) ∈(0,1): Jℓ+1≤‖Wℓ(z),i‖2‖cℓ(z)‖∞Jℓ+‖Wℓ(y),i‖2‖cℓ(y)‖∞,J0=0.J_ +1≤\|W^(z),i_ \|_2\|c^(z)_ \|_∞J_ +\|W^(y),i_ \|_2\|c^(y)_ \|_∞, J_0=0. Note that both ‖Wℓ(z),i‖2‖cℓ(z)‖∞\|W^(z),i_ \|_2\|c^(z)_ \|_∞ and ‖Wℓ(y),i‖2‖cℓ(y)‖∞\|W^(y),i_ \|_2\|c^(y)_ \|_∞ are less than ρ:=BW(BWH+Bb+log2)ρ:=B_W(B_WH+B_b+ 2). Then, unrolling Jℓ+1≤ρJℓ+ρJ_ +1≤ρ J_ +ρ from J0=0J_0=0 yields JL≤∑k=1Lρk=ρ⋅G(ρ,L−1)J_L≤ _k=1^Lρ^k=ρ· G(ρ,L-1). Since Ni(,)=(wi)⊤zLiN^i( x, y)=(w^i) z^i_L and ‖∂Ni/∂y‖2≤‖wi‖2JL≤BwJL\|∂ N^i/∂ y\|_2≤\|w^i\|_2J_L≤ B_wJ_L, the mean value theorem gives |Ni(,)−Ni(,′)|≤BwJL‖−′‖=LN‖−′‖|N^i( x, y)-N^i( x, y )|≤ B_wJ_L\| y- y \|=L_N\| y- y \|. ∎ We are now ready to show that the convex-concave neural network function approximation class introduced in Section 3 is Lipschitz in the players’ actions. Theorem 2 (Lipschitzness of Q∈ℱQ ). Under Assumptions 1 and 10, any function belonging to the convex-concave neural network function class introduced in Section 3 with architecture specified in eqs. 19 and 23 is LℱL_F-Lipschitz in the players’ joint actions, with Lℱ=2LN+BM(D+D), L_F=2L_N+B_M (D_U+D_V ), where LNL_N is defined in Lemma 5, D,D_U,D_V are defined in Assumption 1, and ‖Mθ(s)‖2≤BM\|M_θ(s)\|_2≤ B_M for all s∈s . Note that a bound for BMB_M will be established later on in Theorem 3. Proof. For fixed ∈,θ∈Θ s ,~θ∈ , we have from Lemma 5 that |Qθ(,,)−Qθ(,′,′)|≤|N1(,)−N1(,′)|⏟≤LN‖−′‖2+|N2(,)−N2(,′)|⏟≤LN‖−′‖2 |Q_θ( s, u, v)-Q_θ( s, u , v ) |≤ |N^1( s, u)-N^1( s, u )|_≤ L_N\| u- u \|_2+ |N^2( s, v)-N^2( s, v )|_≤ L_N\| v- v \|_2 +|⊤M()−′⊤M()′| +| u M( s) v- u M( s) v | ≤LN‖−′‖2+LN‖−′‖2+|⊤M()−⊤M()′+⊤M()′−′⊤M()′| ≤ L_N\| u- u \|_2+L_N\| v- v \|_2+| u M( s) v- u M( s) v + u M( s) v - u M( s) v | ≤LN‖−′‖2+LN‖−′‖2+DBM‖−′‖2+DBM‖−′‖2. ≤ L_N\| u- u \|_2+L_N\| v- v \|_2+D_VB_M\| u- u \|_2+D_UB_M\| v- v \|_2. This established the Lipschitz constant LℱL_F of Q∈ℱQ for the architecture specified in eqs. 19 and 23. ∎ C.3 Upper Bound on the covering number of convex-concave Q-function Theorem 1 depends on the covering number of the convex-concave neural network function class ℱF introduced in Section 3 in the sup norm, N(η):=N(ℱ,η,∥⋅∥∞)N(η):=N(F,η,\|·\|_∞) for the case when Qθ∈ℱQ_θ is constructed according to eqs. 19 and 23. In this section, we provide a bound on this covering number. Theorem 3 (Covering number bound). Under Assumptions 1 and 10, for convex-concave networks Qθ∈ℱQ_θ constructed according to eqs. 19 and 23 with ‖θ‖2≤BΘ∀θ∈Θ\|θ\|_2≤ B_ ~∀~θ∈ , we have N(ℱ,η,∥⋅∥∞)≤(2BΘΓη+1)|θ1|+|θ2|+|θ3| N(F,η,\|·\|_∞)≤ ( 2B_ η+1 )^|θ^1|+|θ^2|+|θ^3| with Γ=2LθPICNN+LθM = 2L PICNN_θ+L^M_θ, where LθPICNN=(C2Z2+C2D2+H2+(BW2Z2+BW2D2)(H2+1)+1)Bδ+(H2+1)Bδ~+Z2, L PICNN_θ= (C^2Z^2+C^2D_ y^2+H^2+ (B_W^2Z^2+B_W^2D_ y^2 ) (H^2+1 )+1 )B_δ+ (H^2+1 )B_ δ+Z^2, LθM=D2D2(BW)2LM((HM)2+1)G(1BW2,LM−1)+D2D2HM2 L^M_θ=D_U^2D_V^2 (B_W )^2L_M ( (H^M )^2+1 )G ( 1B_W^2,L_M-1 )+D^2_UD^2_VH^M^2 Bδ=Bw2G(ρ2,L−1), B_δ=B_w^2G (ρ^2,L-1 ), Bδ~=∑ℓ=0L−1((BW2(Z+D)+BW)BwρL−ℓ−1G(BW/ρ,L−1−ℓ))2 B_ δ= _ =0^L-1 ( (B_W^2(Z+D_ y)+B_W )B_wρ^L- -1G ( B_Wρ,L-1- ) )^2 Z=(Dρ+CZ)G(ρ,L−1),D=maxD,D, Z= (D_ yρ+C_Z )G(ρ,L-1), D_ y= D_U,D_V, C,CZ,ρC,C_Z,ρ are defined in Section C.1, H is the constant defined in Lemma 5, HMH^M is defined in eq. 28 and |θ1|,|θ2||θ^1|,|θ^2|, and |θ3||θ^3| are defined in eqs. 21 and 24 Further, for sup‖M()‖2≤BM _ s\|M( s)\|_2≤ B_M used in Theorem 2, we have BM=BWHMB_M=B_WH^M. Proof. To bound the covering number, we need a bound on the Lipschitz constant of Qθ∈ℱQ_θ with respect to the network parameters θ, which can in turn be found by bounding sup,‖∇θQθ‖2 _ s u, v\| _θQ_θ\|_2 uniformly over all θ∈Θθ∈ . Let δℓi:=∂Ni/∂zℓiδ^i_ := ∂ N^i∂ z^i_ , a bound on ‖δℓi‖\|δ^i_ \| will help us bound the gradients with respect to all network parameters. By definition, δLi=wiδ^i_L=w^i, and for ℓ=0,…,L−1 =0,…,L-1, by the chain rule δℓi=(∂zℓ+1i∂zℓi)⊤ δ^i_ = ( ∂ z^i_ +1∂ z^i_ ) δℓ+1i=diag(cℓ(z))(Wℓ(z),i)⊤diag(φ′(aℓ+1i))δℓ+1i δ^i_ +1=diag(c^(z)_ ) (W^(z),i_ ) diag( (a^i_ +1))δ^i_ +1 ⟹ ‖δℓi‖2≤‖cℓ(z)‖∞BW‖δℓ+1i‖2=CBW‖δℓ+1i‖2 \|δ^i_ \|_2≤\|c^(z)_ \|_∞B_W\|δ^i_ +1\|_2=CB_W\|δ^i_ +1\|_2 Starting from ‖δLi‖2=‖wi‖2≤Bw\| _L^i\|_2=\|w^i\|_2≤ B_w, this recursion implies ‖δℓi‖2≤BwρL−ℓ\|δ^i_ \|_2≤ B_wρ^L- . Let us define ∑ℓ=0L−1Bw2ρ2(L−ℓ−1)=Bw2G(ρ2,L−1):=Bδ _ =0^L-1B_w^2ρ^2(L- -1)=B_w^2G (ρ^2,L-1 ):=B_δ We will also use a bound on ‖zℓi‖2\|z_ ^i\|_2. We have zℓ0=z_ ^0= 0, and from Equation 19, ‖zℓ+1i‖2≤ρ‖zℓi‖2+Dρ+CZ⟹‖zℓi‖2≤(Dρ+CZ)G(ρ,ℓ−1)\|z_ +1^i\|_2≤ρ\|z_ ^i\|_2+D_ yρ+C_Z \|z^i_ \|_2≤ (D_ yρ+C_Z )G(ρ, -1) implying that for all ℓ∈0,…,L ∈\0,…,L\, ‖zℓi‖2≤‖zLi‖2≤(Dρ+CZ)G(ρ,L−1)=:Z\|z^i_ \|_2≤\|z^i_L\|_2≤ (D_ yρ+C_Z )G(ρ,L-1)=:Z. We will use this result to bound the gradients with respect to all parameters. Starting with the parameters on the convex path, we have for rℓ(z),i:=Wℓ(zh),ihℓi+bℓ(z),ir^(z),i_ :=W^(zh),i_ h^i_ +b^(z),i_ : ∇Wℓ(z),iNi=Dℓ+1iδℓ+1i(zℓi⊙cℓ(z))⊤⟹‖∇Wℓ(z),iNi‖F≤‖δℓ+1i‖2⋅CZ,∇Wℓ(y),iNi=Dℓ+1iδℓ+1i(⊙cℓ(y))⊤⟹‖∇Wℓ(y),iNi‖F≤‖δℓ+1i‖2⋅CD,∇Wℓ(h),iNi=Dℓ+1iδℓ+1i(hℓi)⊤⟹‖∇Wℓ(h),iNi‖F≤‖δℓ+1i‖2⋅H,∇Wℓ(zh),iNi=(φ′(rℓ(z),i)⊙zℓi⊙((Wℓ(z),i))⊤Dℓ+1iδℓ+1i)(hℓi)⊤⟹‖∇Wℓ(zh),iNi‖F≤‖δℓ+1i‖2⋅BWZH,∇Wℓ(yh),iNi=(((Wℓ(y),i)⊤Dℓ+1iδℓ+1i)⊙)(hℓi)⊤⟹‖∇Wℓ(yh),iNi‖F≤‖δℓ+1i‖2⋅BWDH∇bℓ(z),iNi=φ′(rℓ(z),i)⊙zℓi⊙((Wℓ(z),i)⊤Dℓ+1iδℓ+1i)⟹‖∇bℓ(z),iNi‖2≤‖δℓ+1i‖2⋅BWZ,∇bℓ(y),iNi=((Wℓ(y),i)⊤Dℓ+1iδℓ+1i)⊙⟹‖∇bℓ(y),iNi‖2≤‖δℓ+1i‖2⋅BWD, and∇bℓiNi=Dℓ+1iδℓ+1i⟹‖∇bℓiNi‖2≤‖δℓ+1i‖2, aligned & _W^(z),i_ N^i=D^i_ +1δ^i_ +1(z^i_ c^(z)_ ) \| _W^(z),i_ N^i\|_F≤\|δ^i_ +1\|_2· CZ,\\ & _W^(y),i_ N^i=D^i_ +1δ^i_ +1( y c^(y)_ ) \| _W^(y),i_ N^i\|_F≤\|δ^i_ +1\|_2· CD_ y,\\ & _W^(h),i_ N^i=D^i_ +1δ^i_ +1(h^i_ ) \| _W^(h),i_ N^i\|_F≤\|δ^i_ +1\|_2· H,\\ & _W^(zh),i_ N^i= ( (r^(z),i_ ) z^i_ ( (W^(z),i_ ) ) D^i_ +1δ^i_ +1 )(h^i_ ) \\ & \| _W^(zh),i_ N^i\|_F≤\|δ^i_ +1\|_2· B_WZH,\\ & _W^(yh),i_ N^i= ( ( (W^(y),i_ ) D^i_ +1δ^i_ +1 ) y )(h^i_ ) \\ & \| _W^(yh),i_ N^i\|_F≤\|δ^i_ +1\|_2· B_WD_ yH\\ & _b^(z),i_ N^i= (r^(z),i_ ) z^i_ ( (W^(z),i_ ) D^i_ +1δ^i_ +1 ) \| _b^(z),i_ N^i\|_2≤\|δ^i_ +1\|_2· B_WZ,\\ & _b^(y),i_ N^i= ( (W^(y),i_ ) D^i_ +1δ^i_ +1 ) y \| _b^(y),i_ N^i\|_2≤\|δ^i_ +1\|_2· B_WD_ y, and\\ & _b^i_ N^i=D_ +1^iδ^i_ +1 \| _b^i_ N^i\|_2≤\|δ^i_ +1\|_2, aligned (25) Similarly, for parameters on the state path, we will need a bound on δ~ℓi:=∇hℓiNi δ^i_ := _h^i_ N^i. We have δ~ℓi=(∂hℓ+1i/∂hℓi)⊤δ~ℓ+1i+(∂aℓ+1i/∂hℓi)⊤(∂Ni/∂aℓ+1i) δ^i_ = ( ∂ h^i_ +1∂ h^i_ ) δ^i_ +1+ ( ∂ a^i_ +1∂ h^i_ ) ( ∂ N^i∂ a^i_ +1 ). From Section C.1, a~ℓ+1i=W~ℓihℓi+b~ℓi a^i_ +1= W^i_ h^i_ + b^i_ , and D~ℓ+1i=diag(φ′(a~ℓ+1i)) D^i_ +1= diag ( ( a^i_ +1) ). Then the first derivative above ∂hℓ+1i/∂hℓi=D~ℓ+1iW~ℓi ∂ h^i_ +1∂ h^i_ = D^i_ +1 W^i_ , and the second derivative ∂aℓ+1i/∂hℓi=Wℓ(z),idiag(zℓi⊙φ′(rℓ(z),i))Wℓ(zh),i+Wℓ(y),idiag()Wℓ(yh),i+Wℓ(h),i ∂ a^i_ +1∂ h^i_ =W^(z),i_ diag (z^i_ (r^(z),i_ ) )W^(zh),i_ +W^(y),i_ diag ( y )W^(yh),i_ +W^(h),i_ , yielding δ~ℓi δ^i_ =(Wℓ(z),idiag(zℓi⊙φ′(rℓ(z),i))Wℓ(zh),i+Wℓ(y),idiag()Wℓ(yh),i+Wℓ(h),i)⊤Dℓ+1δℓ+1i = (W^(z),i_ diag (z^i_ (r^(z),i_ ) )W^(zh),i_ +W^(y),i_ diag ( y )W^(yh),i_ +W^(h),i_ ) D_ +1δ^i_ +1 +(W~ℓi)⊤D~ℓ+1iδ~ℓ+1i + ( W^i_ ) D^i_ +1 δ^i_ +1 ⟹ ‖δ~ℓi‖2≤BW‖δ~ℓ+1i‖2+(BW2(Z+D)+BW)BwρL−ℓ−1 \| δ^i_ \|_2≤ B_W\| δ^i_ +1\|_2+ (B_W^2(Z+D_ y)+B_W )B_wρ^L- -1 Unrolling this recursion with ‖δ~L−1i‖2≤(BW2(Z+D)+BW)Bw\| δ^i_L-1\|_2≤ (B_W^2(Z+D_ y)+B_W )B_w yields ‖δ~ℓi‖2≤(BW2(Z+D)+BW)BwρL−ℓ−1G(BW/ρ,L−1−ℓ)\| δ^i_ \|_2≤ (B_W^2(Z+D_ y)+B_W )B_wρ^L- -1G ( B_Wρ,L-1- ). We define ∑ℓ=0L−1((BW2(Z+D)+BW)BwρL−ℓ−1G(BW/ρ,L−1−ℓ))2=:Bδ~ _ =0^L-1 ( (B_W^2(Z+D_ y)+B_W )B_wρ^L- -1G ( B_Wρ,L-1- ) )^2=:B_ δ Using this, we have ∇W~ℓiNi=(D~ℓ+1iδ~ℓ+1i)(hℓi)⊤⟹‖∇W~ℓiNi‖F≤‖δ~ℓ+1i‖2⋅H _ W^i_ N^i=( D^i_ +1 δ^i_ +1)(h^i_ ) \| _ W^i_ N^i\|_F≤\| δ^i_ +1\|_2· H ∇b~ℓiNi=(D~ℓ+1iδ~ℓ+1i)⟹‖∇W~ℓiNi‖F≤‖δ~ℓ+1i‖2 _ b^i_ N^i=( D^i_ +1 δ^i_ +1) \| _ W^i_ N^i\|_F≤\| δ^i_ +1\|_2 Now for each PICNN NiN^i, we have ‖∇θiNi‖22=∑ℓ=0L−1(‖∇Wℓ(z),iNi‖F2+‖∇Wℓ(y),iNi‖F2+‖∇Wℓ(h),iNi‖F2+‖∇Wℓ(zh),iNi‖F2CLOSE+‖∇Wℓ(yh),iNi‖F2+‖∇bℓ(z),iNi‖22+‖∇bℓ(y),iNi‖22+‖∇bℓiNi‖22OPEN+‖∇W~ℓiNi‖F2+‖∇b~ℓiNi‖22+‖∇wiNi‖22). aligned \| _θ^iN^i\|_2^2&= _ =0^L-1 (\| _W^(z),i_ N^i\|_F^2+\| _W^(y),i_ N^i\|_F^2+\| _W^(h),i_ N^i\|_F^2+\| _W^(zh),i_ N^i\|_F^2\\ &+\| _W^(yh),i_ N^i\|_F^2+\| _b^(z),i_ N^i\|_2^2+\| _b^(y),i_ N^i\|_2^2+\| _b^i_ N^i\|_2^2\\ &+\| _ W^i_ N^i\|_F^2+\| _ b^i_ N^i\|_2^2+\| _w^iN^i\|_2^2 ). aligned (26) Using the bounds for each set of derivatives from Equations 25 and 26, we have supθi‖∇θiNi‖22≤(C2Z2+C2D2+H2+(BW2Z2+BW2D2)(H2+1)+1)∑ℓ=0L−1‖δℓ+1i‖22 _θ^i\| _θ^iN^i\|_2^2≤ (C^2Z^2+C^2D_ y^2+H^2+ (B_W^2Z^2+B_W^2D_ y^2 ) (H^2+1 )+1 ) _ =0^L-1\|δ^i_ +1\|_2^2 +(H2+1)∑ℓ=0L−1∥δ~ℓ+1i∥22+Z2 + (H^2+1 ) _ =0^L-1\| δ^i_ +1\|_2^2+Z^2 ≤(C2Z2+C2D2+H2+(BW2Z2+BW2D2)(H2+1)+1)Bδ+(H2+1)Bδ~+Z2⏟=:LθPICNN ≤ (C^2Z^2+C^2D_ y^2+H^2+ (B_W^2Z^2+B_W^2D_ y^2 ) (H^2+1 )+1 )B_δ+ (H^2+1 )B_ δ+Z^2_=:L^PICNN_θ (27) For the standard feedforward network Mθ3()M_θ^3( s) defined in eq. 23, we will first bound ‖hℓM‖2\|h^M_ \|_2. We have hk+1M=φ(WkhkM+bk)⟹‖hℓ+1M‖2≤BW‖hℓM‖2+Bb+pMlog2h^M_k+1= (W_kh_k^M+b_k) \|h^M_ +1\|_2≤ B_W\|h^M_ \|_2+B_b+ p_M 2. Unrolling this recursion with ‖h0M‖2=‖2≤D\|h^M_0\|_2=\| s\|_2≤ D_ s yields ‖hℓM‖2≤DBWℓ+(Bb+pMlog2)⋅G(BW,ℓ−1)\|h^M_ \|_2≤ D_SB_W +(B_b+ p_M 2)· G(B_W, -1) for ℓ>0 >0. This gives that ‖hℓM‖≤max(D,DBWLM+(Bb+pMlog2)⋅G(BW,LM−1))=:HM \|h^M_ \|≤ (D_S,D_SB_W^L_M+(B_b+ p_M 2)· G(B_W,L_M-1) )=:H^M (28) Note that Equation 28 also gives sup‖M‖2≤‖WouthLMM‖F≤BWHM=:BM _ s\|M\|_2≤\|W_outh^M_L_M\|_F≤ B_WH^M=:B_M Let w=vec(⊤)w=vec( u v ), then note that ‖w‖2≤DD\|w\|_2≤ D_UD_V. Let f=⊤Mf= u M v, then f=⊤M=(vec(⊤))⊤vec(M)=w⊤WouthLMMf= u M v= (vec( u v ) ) vec(M)=w W_outh^M_L_M. We have ∇Woutf=w(hLMM)⊤⟹‖∇Woutf‖F≤DD⋅‖hLMM‖ _W_outf=w(h^M_L_M) \| _W_outf\|_F≤ D_UD_V·\|h^M_L_M\| Let δℓM:=∇aℓMfδ^M_ := _a^M_ f, then δℓM=diag(φ′(aℓM))(WℓM)⊤δℓ+1Mδ^M_ =diag ( (a^M_ ) )(W^M_ ) δ^M_ +1. Unrolling this recursion with ‖δLMM‖2≤BWDD\|δ^M_L_M\|_2≤ B_WD_UD_V yields ‖δℓM‖2≤BWLM−ℓ+1DD\|δ^M_ \|_2≤ B_W^L_M- +1D_UD_V. Now we have ∇WℓMf=δℓ+1M(hℓM)⊤⟹‖∇WℓMf‖F≤BWLM−ℓDD‖hℓM‖2 _W^M_ f=δ^M_ +1(h^M_ ) \| _W^M_ f\|_F≤ B_W^L_M- D_UD_V\|h^M_ \|_2 ∇bℓMf=δℓ+1M⟹‖∇WℓMf‖F≤BWLM−ℓDD _b^M_ f=δ^M_ +1 \| _W^M_ f\|_F≤ B_W^L_M- D_UD_V Thus ‖∇θ3⊤Mθ3()‖22=‖∇Woutf‖F2+∑ℓ=0LM−1‖∇WℓMf‖F2+‖∇bℓMf‖22 \| _θ^3 u M_θ^3( s) v\|_2^2=\| _W_outf\|_F^2+ _ =0^L_M-1\| _W^M_ f\|_F^2+\| _b^M_ f\|_2^2 ⟹supθ3 _θ^3 ‖∇θ3⊤Mθ3()‖22 \| _θ^3 u M_θ^3( s) v\|_2^2 ≤D2D2(BW)2LM((HM)2+1)G(1BW2,LM−1)+D2D2HM2⏟:=LθM. ≤ D_U^2D_V^2 (B_W )^2L_M ( (H^M )^2+1 )G ( 1B_W^2,L_M-1 )+D^2_UD^2_VH^M^2_:=L^M_θ. (29) Thus, using eqs. 27 and 29, any Qθ∈ℱQ_θ constructed according to the architecture specified in eqs. 19 and 23 satisfies ‖supθ∇θQθ‖2≤2LθPICNN+LθM=Γ. \| _θ _θQ_θ\|_2≤ 2L^PICNN_θ+L^M_θ= . Thus, the QθQ_θ network in the function class ℱF with the architecture specified in eqs. 19 and 23 is Γ -Lipschitz in the parameters θ. Correspondingly, using the facts that the required covering number N(ℱ,η,∥⋅∥∞)≤N(Θ,η/Γ,∥⋅∥2)N(F,η,\|·\|_∞)≤ N( , η ,\|·\|_2), and that for positive BΘB_ such that ‖θ‖2≤BΘ∀θ∈Θ\|θ\|_2≤ B_ ~∀~θ∈ , N(Θ,η~,∥⋅∥2)≤(2BΘ/η~+1)|θ|N( , η,\|·\|_2)≤ ( 2B_ η+1 )^|θ| when Θ is any convex set within the BΘB_ -bounded ℓ2 ^2 ball in R|θ|R^|θ| (c.f., Chapter 4 of Vershynin (2026)), we have N(ℱ,η,∥⋅∥∞)≤(2BΘΓ/η+1)|θ1|+|θ2|+|θ3|N(F,η,\|·\|_∞)≤ ( 2B_ η+1 )^|θ^1|+|θ^2|+|θ^3|, with |θ1|,|θ2||θ^1|,|θ^2|, and |θ3||θ^3| from eqs. 21 and 24. ∎ Appendix D Experimental Details In this section, we provide additional implementation details for the experiments in Section 5. Convex-Concave Q-function. We used the architecture described in eqs. 19 and 23. Each partially convex input network has 22 hidden layers with hidden depth 3232 for both state and convex paths. We used softplus activation for the convex path, and ReLU activation for the state path. For the bilinear network M, we used 1 hidden layer with width 3232, and ReLU activation. Hardware. All experiments were carried out on a desktop with an AMD Ryzen 9 7950X 16-Core Processor.