Optimizing over Multiple Distributions under Generalized Quasar-Convexity Condition

Authors: shihong  ding
long  yang
luo  luo
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 13:32:27

Abstract: We study a typical optimization model where the optimization variable is composed of multiple probability distributions. Though the model appears frequently in practice, such as for policy problems, it lacks specific analysis in the general setting. For this optimization problem,  we propose a new structural condition/landscape description named  generalized quasar-convexity (GQC) beyond the realms of convexity. In contrast to original quasar-convexity \citep{hinder2020near}, GQC allows an individual quasar-convex parameter $\gamma_i$ for each variable block $i$ and the smaller of $\gamma_i$ implies less block-convexity. To minimize the objective function, we consider a generalized oracle termed as the internal function that includes the standard gradient oracle as a special case. We provide optimistic mirror descent (OMD) for multiple distributions and prove that the algorithm can achieve an adaptive $\tilde{\mathcal{O}}((\sum_{i=1}^d1/\gamma_i)\epsilon^{-1})$ iteration complexity to find an $\varepsilon$-suboptimal global solution without pre-known the exact values of $\gamma_i$ when the objective admits ``polynomial-like'' structural. Notably, it achieves iteration complexity that does not explicitly depend on the number of distributions and strictly faster $(\sum_{i=1}^d 1/\gamma_i \text{ v.s. } d\max_{i\in[1:d]} 1/\gamma_i)$ than mirror decent methods. We also extend GQC to the minimax optimization problem proposing the generalized quasar-convexity-concavity (GQCC) condition and a decentralized variant of OMD with regularization. Finally, we show the applications of our algorithmic framework on discounted Markov Decision Processes problem and Markov games, which bring new insights on the landscape analysis of reinforcement learning.

Main paper: 
 introduction: 
 We study a common class of generic minimization problemEQUATIONwhere the optimization variable x is composed of d probability distributions {x i } d i=1 and X denotes the product space of the d probability simplexes. Problem (1) meets widespread applications in reinforcement learning optimization [62, 2, 35] , multi-class classification [53] and model selection type aggregation [29] . In this paper, we are particularly interested in the case where d is reasonably large and we manage to obtain complexities dependent of d non-explicitly.When f is convex with respect to x, many efficient algorithms can be powerful tools for solving Problem (1) . One well-known algorithm is mirror descent (MD) [5] which is based on Bregman divergence. The wide choices of Bregman divergence enable the algorithm to iterate and converge under specifically constrained region [34] . In particular, if one applies the usual Euclidean distance, the algorithm reduces to project gradient descent [37] . One common and more sophisticated selection is the Kullback-Leibler (KL) divergence, the algorithm thereby becoming the variant of multiplicative weights update (MWU) [41] over probability distribution.Turning to the non-convex world, specific analysis for Problem (1) is rare. In general, finding an approximate global solution suffers from the curse of dimensionality [51, 46] . And one interesting direction is to consider suitable relaxations for the desired solutions, such as an approximate local stationary point of smooth functions [31, 19] . However, for many cases, local solutions may not be sufficient. Moreover, the algorithms often converge much faster in practice than the theoretic lower bounds in non-convex optimization suggest. This observed discrepancy can be attributed to the fairly weak assumptions underpinning these generic bounds. For example, many generic non-convex optimization theories, e.g. Carmon et al. [7, 8] only focus on the consideration of Lipschitz continuity of the gradient and some higher-order derivatives. In practice, the objective is often more "structured". For example, the recent progress in neural networks shows that systems of neural networks approximate convex kernel systems when the model is overparameterized [28] . As pointed out by Hinder et al. [24] , much more research is needed to characterize structured sets of functions for which minimizers can be efficiently found; It was also noted by Yurii Nesterov [47] that lots of functions are essentially convex; Our work follows this research line.We propose generalized quasar-convexity (GQC) for the class of "structure". The original quasarconvex functions [22] is parameterized by a constant γ ∈ (0, 1] and requires f (x) -f (x * ) ≤ 1 γ ⟨∇f (x), xx * ⟩. These functions are unimodal on all lines that pass through a global minimizer and so all critical points are minimizers. We extend quasar-convexity by introducing individual quasar-convex parameter γ i for each distribution x i . Therefore GQC is parameterized by d constants {γ i } d i=1 and implies quasar-convexity in the case d = 1. The main intuition of the generalization is the observation that d/ min i∈ [1:d] γ i often depends on the number of distributions d in real problems, whereas, d i=1 1/γ i may not. That is to say, the hardness for distribution i diverges according to the magnitude of γ i . The larger of γ i implies more convexity and the simpler to solve x i . In general, one always have d i=1 1/γ i ≤ d max i∈[1:d] 1/γ i . In the worst case, d i=1 1/γ i can be d times smaller than d max i∈[1:d] 1/γ i (see discussions in Section 3.3), which motivates us to study the GQC condition.We then study designing efficient algorithms to solve (1) . One simple case is when {γ i } m i=1 is pre-known by the algorithms. The possible direction is to impose a γ i -dependent update rule, such as by non-uniform sampling. However, in general cases, {γ i } m i=1 is not known and determining {γ i } m i=1 require non-negligible costs.In this paper, we consider a generalized oracle, which we refer to as the internal function. Here the standard gradient oracle can be viewed as a special case of the internal function. We provide the optimistic mirror descent algorithm for multiple distributions, which makes sure that each probability distribution is updated according to its own internal function. We first establish an O((dγ max ) 1/2 ( d i=1 γ -1 i ) 3/2 Lε -1 log(N )) complexity with N = max i∈ [1:d] n i and γ max = max i∈ [1:d] γ i when γ max < ∞. However, such an complexity depends on dγ max and requires the step size rely on pre-known γ max d i=1 γ -1 i . We then consider f satisfies "polynomial-like" structural (see Assumption 3.3) . We show the assumption can be achieved in a variety of function classes and important machine learning problems. Under the assumption, we show the algorithm can adapt to the values of {γ i } m i=1 and guarantees an reduced iteration complexity O(( d i=1 1/γ i )ε -1 log(N ) log 4.5 (ε -1 )). In the following, the O(•) notation hides factors that are polynomial in log(ε -1 ) and log(N ).We also extend our framework to the minimax optimizationEQUATIONSolution typeSingle loop ε-approximate NE Cen et al. [9] Chen et al. [12] O 1 (1-θ) 2 ε ✗ Wei et al. [67] O|S| 3 (1-θ) 8 ε 2 ✓Cen et al. [10] O|S| (1-θ) 4 ε ✓ This Work O 1 (1-θ) 2.5 ε ✓ Table 1:Comparison of policy optimization methods for finding an ε-approximate NE of infinite horizon two-player zero-sum Markov games in terms of the max-min gap (see Eq. ( 4)). Since the iteration complexity of several research works (such as Zhao et al. [75] , Alacaoglu et al. [3] and Zeng et al. [72] ) involve concentrability coefficient and initial distribution mismatch coefficient, we will not delve into them here.where both x and y are composed of d probability distributions, and Z = X × Y is a joint region. In the general non-convex and non-concave setting, it is known that finding even an approximated local solution for (2) is computationally intractable [16] . We introduce the generalized quasar-convexityconcavity (GQCC) condition analogous to GQC and demonstrate the feasibility of obtaining an ε-approximate Nash equilibrium with O((1 -θ) -2.5 max z∈Z ( d i=1 ψ i (z))ε -1 log(M ) log(ε -1 )) iteration complexities, where max z∈Z ( d i=1 ψ i (z)) is analogous to ( d i=1 1/γ i ) with ψ i (z) defined in the GQCC condition; θ is the discount parameter; M = max i∈ [1:d] {m i + n i }. Intuitively, the GQCC condition can be viewed as the generalization of convexity-concavity condition. Similarly, the O(•) notation hides factors that are polynomial in log(ε -1 ) and log(M ).Finally, we demonstrate the applications of our framework. For problem (1) , we consider both infinite horizon discounted and finite horizon MDPs problem. For problem (2) , we study the infinite horizon two-player zero-sum Markov games. We prove the learning objectives admit the GQC and GQCC conditions, respectively. This provides new landscape description for RL problems, thereby bringing new insights. Accordingly, our algorithms achieve state-of-the-art iteration complexities up to logarithmic factors. We provide O(ε -1 ) iteration bound for finding an ε-approximate Nash equilibrium of infinite horizon two-player zero-sum Markov games, which outperforms the O(|S| 3 ε -2 ) bound of Wei et al. [67] and the O(|S|ε -1 ) bound of Cen et al. [10] by factors of |S| 3 ε -1 and |S|, respectively, up to a logarithmic factor.(A) We introduce new structural conditions GQC for minimization problems and GQCC for minimax problems over multiple distributions.(B) We provide adaptive algorithm that achieves O((d i=1 1/γ i )ε -1) iteration complexities to find an ε-suboptimal global minimum of "polynomial-like" function under GQC. We also provide an implementable minimax algorithm, given a generalized quasar-convex-concave function with proper conditions, uses O((1 -θ) -2.5 max z∈Z ( d i=1 ψ i (z)) ε -1 ) iterations to find an ε-approximate Nash equilibrium.(C) We show that discounted MDP and infinite horizon two-player zero-sum Markov games admit the GQC and GQCC conditions, respectively, and also satisfy our mild assumptions. In addition, we provide O((1 -θ) -2.5 ε -1 ) iteration bound for finding an ε-approximate Nash equilibrium of infinite horizon two-player zero-sum Markov games. Detailed comparisons between our method and prior arts are provided in Table 1 .Minimization: Convexity condition has been studied at length and plays a critical role in optimizing minimization problems [59, 44, 25, 60, 6, 49] . Several other "convexity-like" conditions have attracted considerable attention, which provide opportunity for designing algorithmic framework to achieve global convergence. Star-convexity [47] is a typical example that relaxes convexity, showing potential in machine learning recently [32, 76] . Quasi-convexity, which admits that the highest point along any line segment is one of the endpoints, is also an important condition [6] . Following this, the concept of weak quasi-convexity is proposed by Hardt et al. [22] which is an extension of star-convexity in the differentiable case, and Hinder et al. [24] provides lower bound for the number of gradient evaluations to find an ε-minimizer of a quasar-convex function (a linguistically clearer redefinition of weak quasi-convex function claimed by Hinder et al. [24] ).Minimax Optimization: Minimax problem attracted considerable attention in machine learning.There exist a variety of algorithms to find the approximate Nash equilibrium points [63, 43, 48, 45, 40, 33, 55, 66, 27] or stationary points [71] for convex-concave functions. Without convexconcave assumption, there exist related work considered specific structures in objective, including nonconvex-(strongly-)concave assumption [39, 73, 50] , Kurdyka-Lojasiewicz condition (or specific PL condition) [68, 11, 69, 38] , interaction dominant condition [21] and negative comonotonicity [17, 36] .RL Landscape Descriptions: For the policy gradient based model of infinite horizon reinforcement learning problems, Agarwal et al. [2] provides a convergence proof for the natural policy gradient descent, which is the same as the mirror descent-modified policy iteration algorithm [20] with negative entropy as the Bregman divergence. Subsequently, Lan [35] focuses on exploring the structural properties of infinite horizon reinforcement learning problems with convex regularizers.For two-player zero-sum Markov games [61, 42] under full information setting, there are various algorithms [26, 54, 64, 18, 42, 67, 9, 74, 70] have been proposed. Specifically, Cen et al. [9] focus on finding approximate minimax soft Q-function in regularized infinite horizon setting; Zhao et al. [74] focus on finding one-sided approximate Nash equilibrium in standard infinite horizon setting with Õ(ε -1 ) iteration bound which depends on the concentrability coefficient; Yang and Ma [70] focus on finding approximate Nash equilibrium in standard finite horizon setting with Õ(ε -1 ) iteration bound.The connection between online learning and game theory [58, 4, 23, 1] has since led to the discovery of broad learning algorithms such as multiplicative weights update (MWU) [41] . Rakhlin and Sridharan [57] introduces an optimistic variant of online mirror descent [56, 14] optimistic mirror descent. Daskalakis et al. [15] shows that the external regret of each player achieves near-optimal growth in multi-player general-sum games, with all players employ the optimistic multiplicative weights update. 
preliminary: 
 Notation:Let x = (x 1 , • • • , x d ) ∈ R d i=1ni be the joint vector variable, for every vector variable n) . Let f : R n → R be a smooth function, we expand its Taylor expansion with Lagrange remainder R f K,w (u) as follows,x i ∈ R ni . Let α = (α(1), • • • , α(n)) be the multi-indices, where α(i) ∈ Z + , we define |α| = n i=1 α(i) and α! = α(1)! • • • α(n)!. For any vector u = (u(1), • • • , u(n)) ∈ R n , we define u α = u(1) α(1) • • • u(n) α(EQUATIONGiven matrices Q and P in R ℓ1×ℓ2 we claim thatQ ≤ P if [Q] i,j -[P] i,j ≤ 0 for every i, j.For a sequence of vector-valued functions{F i } d i=1 , we say that {F i } d i=1 is uniformly L-Lipschitz continuous with respect to ∥•∥′ under ∥•∥ if ∥F i (x i ) -F i (u i )∥′ ≤ L∥x i -u i ∥ for every i ∈ [1 : d]and any x, u ∈ X . We denote by ∥ • ∥ * the dual norm of ∥ • ∥. Let P : R ℓ1×ℓ2 → R n1×n2 be a matrix function, we say that P is a θ-contraction mapping under ∥•∥ if ∥P(Q 1 )-P(Q 2 )∥ ∞ ≤ θ∥Q 1 -Q 2 ∥ for any Q 1 , Q 2 ∈ R ℓ1×ℓ2 . For matrix-valued function P : R n → R ℓ1×ℓ2 ,we define D P (x, x ′ ) = P(x) -P(x ′ ) for any x, x ′ ∈ R n . The KL divergence KL(p∥q) = n j=1 p(j) • log p(j) q(j)between distributions p and q is defined on probability simplex ∆ n . And the variance of x over p is defined byVar p (x) = n j=1 p(j) • (x(j) -E j ′ ∼p [x(j ′ )])2 . We define max-min gap of functionEQUATIONWe claim that (x, y) is an ε-approximate Nash equilibrium (ε-approximate NE) if G f (x, y) ≤ ε. When ε = 0, (x, y) is a Nash equilibrium.Infinite Horizon Discounted Markov Decision Process: We consider the setting of an infinite horizon discounted Markov decision process (MDP), denoted by M := (S, A, P, σ, θ, ρ 0 ). S is a finite state space; A is a finite action space; P(s|s ′ , a ′ ) denotes the probability of transitioning from s to s ′ under playing action a ′ ; σ : S × A → [0, 1] is a cost function, which quantifies the cost associated with taking action a in state s; θ ∈ [0, 1) is a discount factor; ρ 0 is an initial state distribution over S.π : S → ∆ A (where ∆ A is the probability simplex over A) denotes a stochastic policy, i.e., the agent play actions according to a ∼ π(•|s). We use Pr π t (s ′ |s) = Pr π (s t = s ′ |s 0 = s) to denote the probability of visiting the state s ′ from the state s after t time steps according to policy π. Let trajectory τ = {(s t , a t )} ∞ t=0 , where s 0 ∼ ρ 0 , and, for all subsequent time steps t, a t ∼ π(•|s t ) and s t+1 ∼ P(•|s t , a t ). The value function V π : S → R is defined as the discounted sum of future cost starting at state s and executing π, i.e.V π (s) = (1 -θ)E ∞ t=0 θ t σ(st, at) π, s0 = s .Moreover, we define the action-value function Q π : S × A → R and the advantage function A π : S × A → R as follows:Q π (s, a) = (1 -θ)E ∞ t=0 θ t σ(st, at) π, s0 = s, a0 = a , A π (s, a) = Q π (s, a) -V π (s).It's also useful to define the discounted state visitation distribution d π s0 of a policy π asd π s0 (s) = (1 -θ) ∞ t=0 θ t Pr πt (s|s 0 ). In order to simplify notation, we writed π ρ 0 (s) = E s0∼ρ 0 [d π s0 (s)], where d π ρ 0 is the discounted state visitation distribution under initial distribution ρ 0 . 
minimization optimization: 
 In this section, we propose the generalized quasar-convexity (GQC) condition, and analyze a related algorithmic framework for minimization over X = d i=1 ∆ ni , under mild assumptions.We provide a novel depiction of function structure-generalized quasar-convexity, which is defined as follows:Definition 3.1 (Generalized Quasar-Convexity (GQC)). Let x * ∈ X ⊂ R d i=1ni be a minimizer of the function f : X → R. We say that f is generalized quasar-convex on X with respect to x * if for all x ∈ X , there exist a sequence of vector-valued functionsEQUATIONIf Eq. ( 5) holds, we say thatF = (F ⊤ 1 , • • • , F ⊤ d ) ⊤ is the internal function of f . Given i ∈ [1 : d] we say that F i is the internal function of f for variable block x i .Our proposed GQC condition concerns the multi-variable generalized extension of the quasarconvexity condition. In the case d = 1, the GQC condition degenerates into the γ-quasar-convexity condition as studied in Hinder et al. [24] with the gradient ∇f (x) belongs to the internal functions of f . In the case d > 1, the GQC condition is instrumental in capturing the crucial characteristic of those optimization applications with each variable block has difficulty to be optimized.Input:g 0 i = x 0 i = (1/ni, • • • , 1/ni) d i=1, η and T . Output: Randomly pick up t ∈ {1, • • • , T } following the probability P[t] = 1/T and return x t . 1: while t ≤ T do 2:for all i ∈ [1 : d] do 3:x t i = argminx i ∈∆n i η F i(x t-1 ), xi + KL xi ∥g t-1 i , 4: g t i = argmin g i ∈∆n i η F i(x t ), g i + KL g i g t-1i .end for 6:t ← t + 1. 7: end whileRecall that GQC condition provides a perspective to bound function error f (x) -f (x * ) based on internal function, which is different from that based on gradient oracle. We therefore aim to provide an algorithmic framework for finding an approximate suboptimal global solution using internal function. Given an objective function f : X → R with internal function F , our algorithm (Algorithm 1) independently computes points g t i and x t i following OMD over each block. If max i∈[1:d] γ i < ∞ and internal function F has Lipschitz continuity, we have following basic and primary convergence result of Algorithm 1, Theorem 3.2. Assuming that F is L-Lipschitz continuous with respect to ∥ • ∥ * under ∥ • ∥ andEQUATIONHowever, the estimation provided by Theorem 3.2 depends on dγ max . And the step size relying on γ max d i=1 γ -1 i might be difficult to set when {γ i } d i=1 is unknown.We then hope to propose an alternative analytical method that can adapt to unknown {γ i } d i=1 and obtain complexity which does not depends on block dimension d explicitly. The challenges includes: 1) The algorithm does not know the weight 1/γ i ; 2) every F i has dependence on the joint variable x instead of depending on x i . Before we present the details of convergence analysis, we need the following notations and assumptions:Denote P f K,y (x)) = K i=0 |α|=i |D α f (y)| α! • (|x| + |y|) α and let P ϕ K,y (x) = (P ϕ(1) K,y (x), • • • , P ϕ(ℓ)K,y (x)) for any vector-valued function ϕ : R n → R ℓ . Recalling the definition of R f K,w in Eq. ( 3), we shall also defineR ϕ K,y (x) = (R ϕ(1) K,y (x), • • • , R ϕ(ℓ)K,y (x)). Assumption 3.3. Let F be the internal function of f . There exists Θ 1 , Θ 2 > 0, K 0 ∈ Z + , and θ ∈ [0, 1), and a fixed y ∈ R EQUATIONF p = {E[( m j=1 p j σ(x ⊤ P j ) -y)σ(x ⊤ P i )]} m i=1for block p and F Pi = E[(σ(x ⊤ P i ) -y)x] for block P i . Note previous work [65] studies single neuron learning by considering P * 1 in the sphere and assuming x follows from a Gaussian distribution. To our knowledge, there is no evidence shows that objective function of Example 3.4 has quasar-convexity. This example demonstrates the advantage of studying the GQC framework over the previous approach. The proof of Example 3.4 is in Section B.2.Parameter Setting Before stating the convergence result, we set the parameters as follows:EQUATIONTheorem 3.5. Let f satisfies the GQC condition and denote N = max i∈[1:d] {n i }. Under Assumption 3.3, the following estimation holds for Algorithm 1's outputEQUATIONTheorem 3.5 implies that for any generalized quasar-convex function f satisfies Assumption 3.3, the T -step random solution outputted by Algorithm 1 is a O((d i=1 1/γ i )T -1 log(N ) log 4.5 (T ))- suboptimal solution.Ignoring the logarithmic factor, the iteration complexity of our algorithm is competitive to the state-of-the-art algorithm when applied to specific application (i.e. policy optimization of reinforcement learning [2] ). Moreover, our algorithm makes iteration complexity depend on d i=1 1/γ i linearly. In some common applications, d i=1 1/γ i has no dependence on d, which is the number of variable blocks (see discussions in Section 3.3).This section reveals that GQC condition provides a novel analytical approach to reinforcement learning. We show how to leverage Algorithm 1 to find ε-suboptimal global solution for infinite horizon reinforcement learning problem. And in Appendix B.3.2, we show how to leverage Algorithm 1 to minimize finite horizon reinforcement learning problem.The infinite horizon reinforcement learning is formulated as the following policy optimization problem:EQUATIONwhereJ π (ρ 0 ) = E s0∼ρ 0 [V π (s 0 )] and X = |S| i=1 ∆ A denotes |S| probability simplexes. We write S = {s i } |S| i=1and denote the action-value vector on state s i by Q π (s i , •). The next Proposition 3.6 states that J π (ρ 0 ) satisfies the GQC condition for any initial state distribution ρ 0 . Proposition 3.6. Let {π * (•|s) ∈ ∆ A } s∈S denote the optimal global solution of problem (9) . We have that J π (ρ 0 ) satisfies the GQC condition in Eq. (5) with internal function F i (π) = Q π (s i , •) for variable block π i and F satisfies Assumption 3.3 with Θ 1 = θ, Θ 2 = 1 and K 0 = 1.According to Theorem 3.5, if we apply Algorithm 1 to the infinite horizon reinforcement learning basing action-value vector Q π with parameter selection Eq. (7) , which is actually a simple variant of natural policy gradient descent [2] , then the iteations T we need to find an ε-suboptimal global solution is upper-bounded by O(max{1, log -1 (θ -1 )}(1-θ) -1 ε -1 log 4.5 (ε -1 ) log(|A|)) under Agarwal et al. [2] 's setting. Therefore, the iteration complexity of Algorithm 1 does not depend on the size of states, since the summation of d π * ρ 0 over S ( Theorem 5.3] has demonstrated that utilizing the information of joint variables to separately update each variable block ensures global convergence for problem (9) with O((1 -θ) -2 ε -1 ) iteration complexity. However, their analytical approach is carefully designed for infinite horizon reinforcement learning problems.|S| i=1 1/γ i = |S| i=1 d π * ρ 0 (s i ) = 1)] d π * ρ 0 (s i ) ≥ (1 -θ) max i∈[1:|S|] ρ 0 (s i ). Previous research [2, 
minimax optimization: 
 In this section, we introduce the generalized quasar-convexity-concavity (GQCC) condition, which can be verified in real applications such as two-player zero-sum Markov games. We provide a related algorithm for minimax optimization (minimizing G f (x, y) has been defined in Eq. ( 4)) over Z = d i=1 Z i = d i=1 (∆ ni × ∆ mi ), under proper assumptions. We specify the divergencegenerating function v as v(x) = E i∼x(•) [log(x(i))] in probability simplexes setting. We also provide a framework for minimax problem over the general compact convex regions in Appendix C.We provide a new notion called generalized quasar-convexity-concavity for nonconvex-nonconcave minimax optimization, which is defined as follows: Definition 4.1 (Generalized Quasar-Convexity-Concavity (GQCC)). Denote Z i = X i × Y i for any i ∈ [1 : d], and let f : Z → R be the objective function. We say that f is generalized quasar-convexconcave on Z if for all z = (x, y) ∈ Z, there exist a sequence of functions {f i : R ℓ×d × Z i → R} d i=1 , a sequence of non-negative functions {ψ i : Z → R + ∪ 0} d i=1 and a matrix-valued function P = (P 1 , • • • , P d ) : Z → R ℓ×d where every P i is a ℓ-dimensional vector-valued function, such thatEQUATIONwhere eachf i (Q, •, •) is convex-concave for a fixed Q = (Q 1 , • • • , Q d ) ∈ R ℓ×d .We denote the internal operator of f for variable block z i by F i whereF i (Q, z i ) = ((∇ xi f i (Q, z i )) ⊤ , (-∇ y i f i (Q, z i )) ⊤ ) ⊤ . Moreover, we say that F = (F ⊤ 1 , • • • , F ⊤ d ) ⊤is the internal operator of f . The GQCC condition is an extension of the GQC condition in minimax optimization setting. The specific connection between them can be found in Appendix C. The GQCC condition can be viewed as an extension of the convexity-concavity condition in multi-variable optimization; it seamlessly reduces to the convexity-concavity condition with f 1 (P(z), z) = f (z) and ψ 1 (z) ≡ 1, in the case d = 1. Assuming every ψ i is bounded, f i (P(z), z i ) ≡ f i (0, z i ) with Lipschitz continuous gradient and is convex-concave with respect to z i , then finding the Nash equilibrium point of f is reduced to finding the Nash equilibrium points of d independent convex-concave minimax problems. However, how to find the approximate Nash equilibrium points in more general case has not been well-studied. Most of existing work for minimax optimization without convex-concave assumption are focused on finding the approximate stationary points.For simplicity, we denote by F x i and F y i the projection of F i in the x i and y i directions, respectively, i.e.,F ⊤ i = (F x i ) ⊤ , (F y i ) ⊤ .Given an objective function f : Z → R with internal operator F , our algorithm (Algorithm 2) employs regularized OMD over each distribution independently basing on F i and updates matrix Q t to track the behavior of function P iteratively. It's worth noting that each iteration of Algorithm 2 provides explicit expressions for x t i and g t i (see the proof of Theorem 3.5 in Appendix B). Consequently, Algorithm 2 essentially operates as a single-loop algorithm. Assumption 4.2. In Definition 4.1, we assume that matrix-valued function P has the form of P(Q z , z) where Q z ∈ R ℓ×d depends on z, and P satisfies the following properties on regionQ ∈ R ℓ×d ∥Q∥ ∞ ≤ C} × Z for some constant C > 0:Algorithm 2 Optimistic Mirror Descent with Regularization for Multiple DistributionsInput: z 0 i d i=1 = g 0 i d i=1 = {(1/ni, • • • , 1/ni), (1/mi, • • • , 1/mi)} d i=1 , {αt ≥ 0} T t=1 with T t=1 αt = 1, {γt ≥ 0} T t=1 , {λt ≥ 0} T t=1 , η and Q 0 = 0. Output: zT = T t=1 αtz t . 1: while t ≤ T do 2: Q t = (1 -βt-1)Q t-1 + βt-1P(Q t-1 , zt-1). 3:for all i ∈ [1 : d] do 4:x t i = argminx i ∈X i η F x i (Q t-1 , z t-1 i ), xi + γtKL xi (g x i ) t-1 + λtv(xi),5:y t i = argmin y i ∈Y i η F y i (Q t-1 , z t-1 i ), y i + γtKL y i (g y i ) t-1 + λtv(y i ), 6: (g x i ) t = argmin g x i ∈X i η F x i (Q t , z t i ), g x i + γtKL g x i (g x i ) t-1 + λtv(g x i ), 7: (g y i ) t = argmin g y i ∈Y i η F y i (Q t , z t i ), g y i + γtKL g y i (g y i ) t-1 + λtv(g y i ).8: end for 9:t ← t + 1. 10: end while [A 1 ] There exist constants L 1 , L 2 ≥ 0 such that F i (•, z i ) is uniformly L 1 -Lipschitz continuous with respect to ∥ • ∥ ∞ under ∥ • ∥ ∞ , and F i (Q, •) is uniformly L 2 -Lipschitz continuous with respect to ∥ • ∥ ∞ under ∥ • ∥ 1 . [A 2 ]There are a positive constant γ > 0 and a set of non-negative constant matrices{B i , C i } d i=1 satisfying d i=1 (B i + C i ) ∞ ≤ γ, such that D P(Q,•,y) (x, x ′ ) ≤ d i=1 C i ⟨F x i (Q, z i ), x i -x ′ i ⟩ and D P(Q,x,•) (y, y ′ ) ≥ d i=1 B i ⟨F y i (Q, z i ), y ′ i -y i ⟩. [A 3 ] There exists θ ∈ [0, 1) such that P(•, z) is a θ-contraction mapping under ∥ • ∥ ∞ , and ∥P(Q, z)∥ ∞ ≤ C for any z ∈ Z.We present Lemma 4.3 to demonstrate that there exist Q * ∈ R ℓ×d , x * ∈ X and y * ∈ Y satisfy the saddle point and fixed point conditions of function P, i.e., Eq. ( 11), under proper assumptions.Lemma 4.3. Assuming that Assumption 4.2 holds, [P(Q, •, •)] k,j is continuous, convex with respect to x, concave with respect to y for any (k, j), and min k,j,imin{[Ci] k,j ,[Bi] k,j } [Ci] k,j +[Bi] k,j ≥ C ′ for some C ′ > 0,then there exist Q * ∈ R ℓ×d and z * ∈ Z such thatEQUATIONFor Algorithm 2, we let β T,t = β t T j=t+1 (1 -β j ) for any T ≥ t and β T,T = β T , and set parametersEQUATION)Then we have the following convergence result by denotingM = max i∈[1:d] {m i + n i }.Theorem 4.4. For any generalized quasar-convex-concave function f which satisfies Assumption 4.2 with P ≡ Q * , where Q * satisfies Eq. (11) . Algorithm 2's output zT = (x T , ȳT ) satisfiesG f (x T , ȳT ) ≤ 60 max z∈Z d i=1 ψ i (z) (1 -θ) -1 2 η log(M ) + ηL 2 1 + L 1 Y η T T -1 ,whereY η T = 8(c + 1)[ 4γ η log(M ) + 160γL 2 + 2ηγL 2 1 (1 + 64C 2 )](log(c + T ) + 1).Similar to minimization Algorithm 1, the iteration complexity of minimax Algorithm 2 linearly depends on the upper bound of In this section, we show how to leverage Algorithm 2 to achieve accelerated rates for optimizing infinite horizon two-player zero-sum Markov games. Our algorithm use Õ(ε -1 ) iteration bound to find an ε-approximate Nash equilibrium of infinite horizon two-player zero-sum Markov games.As similar as the definition of discounted MDP in Preliminary, we utilize M = (S, A, B, P, σ, θ, ρ 0 ) to define a infinite horizon two-player zero-sum Markov game. The difference here compared to Section 3.3 is that the cost function σ is defined on S × A × B with values in [0, 1], and the transition model P(s|s ′ , a ′ , b ′ ) denotes the probability of transitioning into state s upon player 1 taking action a ′ and player 2 taking action b ′ in state s ′ . We can define the value function V z and action-value functionQ z on the joint distribution z = (x, y) ∈ Z = |S| i=1 ∆ A × |S| i=1 ∆ B .The infinite horizon two-player zero-sum Markov games consider the following policy optimization problem:EQUATIONwhereJ z (ρ 0 ) = E s0∼ρ 0 [V z (s 0 )].The following proposition indicates that J z is general quasar convex-concave, and satisfies Assumption 4.2 and the condition of Theorem 4.4,Proposition 4.5. For any Q = (Q 1 , • • • , Q |S| ) with every Q i ∈ R |A|×|B| , define function f i (Q, z i ) := x ⊤ i Q i y i for any i ∈ [1 : |S|].There exists a tensor-valued function P such that J z (ρ 0 ) satisfies GQCC condition with f i (P(z), z i ) = f i (Q * , z i ) for any ρ 0 ∈ ∆ S , where Q * satisfies the conditions mentioned in Eq. (11) . Moreover, P satisfies Assumption 4.2.According to Proposition 4.5 and Theorem 4.4, if we apply Algorithm 2 to the infinite horizon two-player Markov games basing internal operatorF i (Q, z) = (y ⊤ i Q ⊤ i , -x ⊤ i Q i ) ⊤for block z i with parameter selection Eq. ( 12), which is actually a variant of optimistic gradient descent/ascent for Markov games [67] , then the iterations T we need to find an ε-approximate Nash equilibrium is upperbounded by Õ((1 -θ) -2.5 ε -1 ). To the best of our knowledge, our iteration bound matches state-ofthe-art iteration bound and is a factor of (1 -θ) -1.5 |S| better than Õ((1 -θ) -4 |S|ε -1 ) bound of Cen et al. [10] . Since the upper bound of |S| i=1 ψ i over feasible region Z in infinite horizon two-player zero-sum Markov games' setting satisfies|S| i=1 ψ i (z) ≤ |S| i=1 [d x,y * (x) ρ 0 (s i ) + d x * (y),y ρ 0 (s i )] ≤ 2for any z ∈ Z, our algorithm's iteration bound does not depend on the size of states. 
conclusion: 
 In this work, we introduce two function structures: GQC and GQCC and provide related algorithmic frameworks with convergence result. To complement our result, we also show that discounted MDP and infinite horizon two-player zero-sum Markov games admit the GQC and GQCC condition, respectively, and satisfy our mild assumptions. For simplicity, we denote g(Γ) :=∞ k=1 Γ -k [k 7 + (k + 1) exp{2k}], the chi-squared divergence between p, q as χ 2 (p∥q) := n j=1 (p(j)-q(j)) 2 q(j) , E p (x) := n j=1 p(j)x(j) and Var p (x) := n j=1 p(j) • (x(j) -E p (x)) 2 for any p, q ∈ ∆ n and x ∈ R n . For ζ > 0, n ∈ Z + , we say that a sequence of distributions p 1 , • • • , p T ∈ ∆ n is ζ-consecutively close if for each 1 ≤ t < T , it holds that max p t p t+1 , p t+1 p t ≤ 1 + ζ.For positive scalar θ ∈ [0, 1), non-negative integers t and T , we defineβ θ T,t := β t T -1j=t (1 -β j + θβ j ), and β θ T,T = 1. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: NA Justification: Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: YES Justification: Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: NA Justification: Since this paper is a theoretical paper, it may not have other social impacts. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: NA Justification: Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: NA Justification: Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? 
 
 Appendix: Definition A.1 (Finite Differences). For a sequence of vectors L = (L 0 , • • • , L T ) where each L t ∈ R n , and integers h ∈ Z + , the order-h finite difference sequence for the sequence L is denoted byD h L := (D h L) 0 , • • • , (D h L) T -h recursively with (D 0 L) t := L t for all t ∈ [0 : T ],andEQUATIONfor all h ≥ 1 and t ∈ [1 :T -h].As stated in [15, Remark 4.3], we haveEQUATIONTo guarantee the coherence of the analysis's structure, we introduce the definition of the shift operator E s as follows:Definition A.2 (Shift Operator). For a sequence of vectors L = (L 0 , • • • , L T ) where each L t ∈ R n , and integers s ∈ Z + , the s-shift sequence for the sequence L is denoted byE s L := (E s L) 0 , • • • , (E s L) T -h with (E s L) t = L t+s for t ∈ [1 : T -s].We also consider the following finite horizon Markov decision process (MDP), denoted by M := (H, S 1:H , A 1:H , P 2:H , σ, ρ 1 ). H ∈ Z + denotes the number of horizon;S 1:H = (S 1 , • • • , S H ) is a sequence of H finite state spaces; A 1:H = (A 1 , • • • , A H ) is a sequence of H finite action spaces; P h (s h |s h-1 , a h-1) denotes the probability of transitioning from s h-1 to s h under playing actiona h-1 at horizon h -1; σ : S 1:H × A 1:H → [0, 1]is a cost function; ρ 1 is a initial state distribution over S 1 . π = (π 1 , • • • , π H ) : S 1:H → ∆ A1 × • • • × ∆ A Hdenotes a stochastic policy. Similarly, we use Pr for all i ∈ [1 : d] do 3:π 1:h-1 h (s ′ |s) = Pr π 1:h-1 h (s h = s ′ |s 1 = s) toEQUATIONg t i = argmin g i ∈Xi η ⟨F i (x t ), g i ⟩ + V g i , g t-1 i . 5:end for 6:t ← t + 1. 7: end whileπ h:H = (π h , • • • , π H ), i.e., V π h:H h (s h ) = E H h ′ =h σ(s h ′ , a h ′ ) π h:H , s h .For convenience, we defineV π 1 (s 1 ) = V π 1:H 1 (s 1 ). Moreover, we define the action-value function Qπ h+1:H h : S h × A h → [0, 1 + H -h] as follows: Q π h+1:H h (s h , a h ) = σ(s h , a h ) + E H h ′ =h+1 σ(s h ′ , a h ′ ) π h+1:H , s h , a h .We begin with a general version of Theorem 3.2 basing Algorithm 3 in this part. Theorem B.1. [General Version of Theorem 3.2] We consider the divergence-generating function v with Bregman's divergenceEQUATIONwith setting η = (L 2 dγ maxd i=1 γ -1 i ) -1/2 /2.Proof. According to GQC condition (Definition 3.1), we have the following estimationEQUATIONFor any fixed i ∈ [1 : d], we obtain thatEQUATION)Since F is L-Lipschitz continuous with respect to ∥ • ∥ * under ∥ • ∥, we have following estimation of I by using Cauchy-Schwarz inequalityEQUATION)In addition, utilizing the result of [Lemma 3.4, [34] ] on step-3 and step-4 of Algorithm 3, we haveEQUATIONEQUATIONTherefore, by applying Eq. ( 19), ( 20) and ( 21) into Eq. ( 18), we obtainEQUATIONwhere (a) is derived from the assumption thatV (x i , u i ) ≥ ∥x i -u i ∥ 2 for any x i , u i ∈ X i and (b)follows from the convexity of ∥ • ∥. Applying Eq. ( 22) to Eq. ( 17), we haveEQUATIONwhere (c) is derived from the fact that g 0i = x 0 i for any i ∈ [1 : d] and (d) follows from the convexity of ∥ • ∥ ( 1 d d i=1 ∥x i ∥ 2 ≤ ∥ 1 d d i=1 x i ∥ 2 ). Since KL divergence satisfies KL(x i ∥u i ) ≥ ∥x i -u i ∥ 21 (Pinsker's inequality), Theorem 3.2 can be directly derived from Theorem B.1. Next, we propose Proposition B.2 and provide related proof. Proposition B.2. We denote N = d i=1 n i and let a smooth vector-valued function F : R N → R ℓ satisfies:1. There is a point y ∈ R N such that ∥D α F (y)∥ ∞ ≤ γ k with |α| = k for all k ∈ [0 : K],2. For any positive integer k greater than K, ∥D α F ∥ ∞ ≤ γ k with |α| = k uniformly over X , with a positive constant γ and a positive integer K, then F satisfies Assumption 3.3.Proof of Proposition B.2. For any k ∈ Z + and j ∈ [1 : l], we haveEQUATIONusing the fact that ∥D α F (y)∥ ∞ ≤ γ k for any k ∈ Z + and |α| = k. In addition, by the Taylor expansion of F (j) with Lagrange remainder formula for any j ∈ [1 : l] and k > 1, we can obtainEQUATIONwhere t ∈ [0, 1] depends on F (j), x and y. Letting k 0 = ⌈3γ(d + ∥y∥ 1 )⌉ and supposing k ≥k 0 1 + log(1+γ(d+∥y∥1)) log(3/2), we derive thatEQUATION)Therefore, in the light of Eq. ( 24), Eq. ( 25) and Eq. ( 26), it's direct to derive that F statisfies Assumption 3.3 withK 0 = k 0 1 + log(1+γ(d+∥y∥1)) log(3/2) , θ = 1 3 , Θ 1 = 3 k0 and Θ 2 = exp{γ(d + ∥y∥ 1 )}.The following remark discusses the reasonability of Proposition B.2 conditions, which supports the reasonability of Assumption 3.3. Remark B.3. Since region X = d i=1 ∆ ni is bounded, it's reasonable to assume that the growth rate of the upper bound of internal function's high-order derivatives is not faster than linear growth rate. For example, the upper bounds of high-order derivatives of sin(Cx), cos(Cx) and exp{Cx} have linear growth rate over X for fixed constant C. Therefore, if the internal function F can be generated by the linear combination of {sin(C k x)} K k=1 and {cos(C k x)} K k=1 (or {exp{C k x}} K k=1 ) with finite K, F satisfies Assumption 3.3 by using Proposition B.2.We briefly introduce our techniques to make the proof of Theorem 3.5 more comprehensible in this part. Our proof consists of two ingredients. The first is applying Lemma B.4 to construct a variant upper bound of average function error 1 T T t=1 (f (x t ) -f (x * )) that is different from the upper bound derived from the classical OMD algorithm. This bound is composed of a) O 1 ηT invariant error and b) weighted sum of the variance for finite difference sequence {(D 1 F i (x t-1 )} T t=1 and {(D 0 F i (x t-1 )} T t=1 over i ∈ [1 : d], which has the form ofd i=1 1 γi [ O(1) T T t=1 Var x t i (D 1 F i (x t-1 )) -O(1) T T t=1 Var x t i (F i (x t-1 ))].The second is applying Lemma D.7 (refer to it as control lemma) on each {F i (x t )} T t=1 to bound (b) by a quantity that grows poly-logarithmically in T . Therefore, it's necessary to leverage Theorem B.5 and Lemma B.7 to show that every sequence {F i (x t )} T t=0 outputted by Algorithm 1 satisfies the preconditions of Lemma D.7.The next Lemma B.4 provides a variant convergence proof of the OMD algorithm. In this Lemma, basing on KL divergence, an explicit expression for the optimal solution of the OMD sub-problem is utilized to provide an upper bound ofT t=1 (f (x t ) -f (x * )). Lemma B.4. Suppose ∥F (x)∥ ∞ ≤ Θ (Θ ≥ 1)for any x ∈ X and policy set {x t } T t=1 follows the iteration of Algorithm 1 with step size η ∈ (0, 1 32Θ ). Then, it holds thatEQUATIONwhere ĝ1 (η) := 1 2 + 64 Proof. As claimed by Definition 3.1, we have the following estimationEQUATIONIn the following, considering a fixed i ∈ [1 : d], it's easy to obtain thatEQUATIONRecall the update of Algorithm 1 can be devided into two parts:EQUATIONx t+1 i = arg minEQUATIONfor any i ∈ [1 : d] whereg 0 i ∝ x 0 i • exp{η(F i (x 0 ) -F i (x -1 ))} and x -1 i = x 0 i = 1 ni , • • • , 1 ni ⊤ .According to Cauchy-Schwarz inequality, we can evaluate I as followsEQUATIONIn addition, utilizing the result of Lemma D.2, we haveEQUATIONEQUATIONTherefore, by applying Eq. ( 32), (33) and (34) into Eq. ( 29), we obtainEQUATION)Since there is a vector F i (x t ) -F i (x t-1 ) such that for any j ∈ [1 : n i ]EQUATIONwe have thatEQUATIONandmax i∈[1:d] x t i g t-1 i ∞ ≤ exp{2η∥F i (x t-1 )∥ ∞ } ≤ exp{2ηΘ} ≤ 1 + 4ηΘ,with combining Eq. ( 31) and choosing proper η such that ηΘ ≤ 1 4 . According to Lemma D.3, we haveEQUATIONfor any i ∈ [1 : d]. Noting that X 2 (ρ, µ) = ∥ρ -µ∥ * µ 2, in the light of Lemma D.4, we derive thatEQUATIONas long as ηΘ ≤ 1 32 . There exists a similar lower bound with respect toEQUATIONwhere (a) is derived from exp{-2ηΘ} ≥ 1 -4ηΘ for any ηΘ ≤ 1 32 . Relying on Eq. ( 35), Eq. ( 38)-( 40), we conclude thatEQUATIONFinally, applying the estimation Eq. ( 41) to Eq. ( 28), we complete the proof.Basing on the conclusion of Lemma B.4, if the finite sum of Varx t i (F i (x t ) -F i (x t-1)) can be controlled by the finite sum of Var x t i (F i (x t-1 )) with a O(poly(log(T ))) constant for each i ∈ [1 : d], the final convergence result can be obtained directly. Hence, to demonstrate this relationship, we require the assistance of auxiliary Lemma D.7. Our initial step is to prove that F i (x t ) satisfies the first condition in Lemma D.7 for any i ∈ [1 : d]. Theorem B.5. Assuming f satisfies GQC condition and Assumption 3.3 holds, x t follows the iteration of Algorithm 1, we set β ∈ 0,1 (Θ1+Θ2+1)(H+3) , Γ ≥ e 2 + 322560Θ 2 , K ≥ max{K 0 , H log(4β -1 )+log(Θ1) log(θ -1 )} and η = β 6e 3 KΓ max{Θ,1} . Then, the following finite difference bound with respect toEQUATIONfor all h ∈ [1 : H] and t 0 ∈ [0 : T -h]. Without loss of generality, we require that H does not exceed T .Proof of Theorem B.5. According to the Taylor expansion of each component k of F i at y, one can notice thatEQUATIONfor any K ∈ Z + . Therefore, setting K ≥ max H log(4β -1 )+log(Θ1) log(θ -1 ), K 0 and combining the remark Eq. ( 15) of operator D h in Appendix A.2, we can guarantee the validity of the following estimationEQUATIONfor any h ∈ [1 : H]. Moreover, as stated by Assumption 3.3, we obtain maxi∈[1:d] ∥F i (x)∥ ∞ ≤ Θ 1 + Θ 2 for any x ∈ X . Suppose that max i∈[1:d] ∥(D h ′ F i (x)) t0 ∥ ∞ ≤ β h ′ h ′Bh ′ +1 holds for any h ′ ∈ [1 : h] and t 0 ∈ [0 : T -h ′ ],we deduceEQUATIONby using Lemma B.6 with p(x):= |D α F i(k)(y)| α!(x -y) α and the fact that g(Γ)Θ 2 ≤ 1 2 (which can be derived from Lemma D.1). Therefore, to apply mathematical induction, it suffices to prove that maxi∈[1:d] ∥(D h ′ F i (x)) t0 ∥ ∞ ≤ β h ′ h ′Bh ′ +1 holds when h ′ = 1.Observe that Lemma B.6 holds in the case h = 0. Thus, we can obtain Eq. ( 45) for h = 0 as well. Hence, we have max i∈[1:d] ∥(D 1 F i (x)) t0 ∥ ∞ ≤ β.EQUATIONif the condition maxi∈[1:d] ∥(D h ′ F i (x)) t0 ∥ ∞ ≤ β h ′ h ′Bh ′ +1 holds for any h ′ ∈ [1 : h] and t 0 ∈ [0 : T -h ′ ].Proof. Drawing on the premises outlined in the lemma, we assume that each u(k) corresponds to a unique x i(k) (j(k)). According to the iteration of Algorithm 1, we can obtainEQUATIONfor any k ∈EQUATIONfor any k ∈EQUATIONAlso, for a vector z ∈ R n i(k) and an index j ∈ [1 : n i(k) ], defineEQUATION) so that u t0+t (k) = x t0 i(k) (j(k)) • ψ j(k) t0,k ηr t t0,k = u t0 (k) • ψ j(k)t0,k ηr t t0,k for t ≥ 1. For convenience, we denote thatD := α ∈ N K |α(i) ∈ {0, 1}, ∀ i ∈ [1 : K] and e := (1, • • • , 1) ∈ N K .In particular, for any α ∈ D, we haveEQUATIONwhere ψ t0 (ηr t t0 ) := ψj(1) t0,1 (ηr t t0,1 ), • • • , ψ j(K) t0,K (ηr t t0,K ) , h ′ ∈ [1 : h + 1] and t 0 ∈ [1 : T -h -1].It is important to observe that the finite difference in Eq. ( 51) pertains specifically to ψEQUATIONfor any t ∈ [0 : h]. Therefore, for any h ′ ∈ [1 : h + 1], we obtainEQUATIONfor any t ∈ [0 :EQUATIONfor any h ′ ∈ [0 : h] by using Eq. ( 53) where r t t0 := r t t0,1 (j(1)), • • • , r t t0,K (j(K)) . By Lemma D.5 and Lemma D.6, we haveEQUATIONand applying bound Eq. ( 55) to Eq. ( 50), we can deriveEQUATIONfor anyt 0 ∈ [1 : T -h -1]where (a) is derived from the equivalent expression Eq. ( 56) of the polynomial p(u) and Eq. ( 15) of the finite difference (D h f (x)) t0 w.r.t function f respectively.Recalling that we set parameters as followsEQUATIONAccording to Theorem B.5, we have maxi∈[1:d] (D h F i (x)) t ∞ ≤ β h H 3h+1 for each h ∈ [0 : H] and t ∈ [1 : T -h].We are now prepared to prove that x t i satisfies the second condition of Lemma D.7. Lemma B.7. The sequence {x t i } T t=1 which has been generated from Algorithm 1 is 7η(Θ 1 + Θ 2 )consecutively close when H ≥ 1, β 0 = (4H) -1 and η ∈ (0,β 4 0 (Θ 1 + Θ 2 + 1) -1 /57792].Proof. According to the iteration of Algorithm 1, we haveEQUATION)EQUATIONwhere (a) is derived from the fact that exp(x) ≤ 1 + 7 6 x for x ∈ [0, 1/24].With the preparatory work for proving Theorem 3.5 is completed, we now turn to providing the final proof:Proof of Theorem 3.5. Applying Theorem B.5 and Lemma B.7 to Lemma D.7, we haveEQUATIONAccording to the result of Lemma B.4, we obtainEQUATIONCombining Assumptions 3.3 and parameters selection Eq. ( 7), we complete the proof.In this section, we provide the proof of Example 3.4 which satisfies GQC condition and Assumption 3. since f (•, P) is convex for any fixed P. In addition, we obtainEQUATIONwhere B C is a constant depends on C and (a) is derived from the fact thatB C ⟨exp{x 1 } - exp{x 2 }, x 1 -x 2 ⟩ ≥ | exp{x 1 } -exp{x 2 }| 2 for any x 1 , x 2 ∈ [-C, C].Therefore, summing up Eq. ( 63) and Eq. ( 64), we have that f satisfies GQC condition with the internal functionsF p = {E[( m j=1 p j σ(x ⊤ P j ) -y)]σ(x ⊤ P i )} m i=1 for block p and F Pi = E (σ(x ⊤ P i ) -y)x for block P i . Notice that γ p = 1, γ P1 = B C2 and γ Pi = 0 for any i ̸ = 1. Furthermore, we have There is also a toy example satisfying GQC condition and Assumption 3.3.∥D α F p (•)∥ ∞ ≤ 2 exp{C}(2C) |α| and ∥D α F Pi (•)∥ ∞ ≤ exp{C}C |α|+1Example B.8. Assuming (p 1 , p 2 ) ∈ ∆ m × ∆ n , the function f (p 1 , p 2 ) = 1 2 ∥p 1 p ⊤ 2 ∥ 2F satisfies GQC condition and Assumption 3.3 with the internal functions F p 1 = ∥p 2 ∥ 2 p 1 for block p 1 and F p 2 = p 2 for block p 2 .Proof. We have 1 2∥(p * 1 ) ⊤ p 2 ∥ F -1 2 ∥p ⊤ 1 p 2 ∥ F ≥ ∥p 2 ∥ 2 p ⊤ 1 (p * 1 -p 1 ) and 1 2 ∥(p * 1 ) ⊤ p * 2 ∥ F - 1 2 ∥(p * 1 ) ⊤ p 2 ∥ F ≥ ∥p * 1 ∥ 2 p ⊤ 2 (p * 2 -p 2 ). Therefore, we have that f satisfies GQC condition with the internal functions F p 1 = ∥p 2 ∥ 2 p 1 for block p 1 and F p 2 = p 2 for block p 2 . Notice that γ p 1 = 1 and γ p 2 = ∥p * 1 ∥ 2 . Since both ∥p 2 ∥ 2 p 1 and p 2 are polynomials with respect to (p 1 , p 2 ), we derive that the internal function of f satisfies Assumption 3.3.Proof of Proposition 3.6. The following performance difference lemma [30, 13, 2, 35] plays an important role in the policy gradient based model of infinite horizon reinforcement learning problems,EQUATION) Let d = |S|, S = {s i } d i=1 and write 1/γ i = d π * ρ 0 (s i ), F i (π) = Q π (s i , •).According to Eq. ( 65) whose proof is given in Cheng et al. [13] and⟨A π (s i , •), π ′ (•|s i )-π(•|s)⟩ = ⟨Q π (s i , •), π ′ (•|s i ) -π(•|s)⟩for any policy π and π ′ , we obtain thatEQUATION)Eq. ( 66) implies that V π (ρ 0 ) satisfies GQC condition. For every a ∈ A, the Taylor expansion of Q π (s i , a) up to K-th order at origin is the same as its truncation at horizon K, which indicatesR Q π (si,a) K,0 (π) = θ K+1 E s K+1 [V π (s K+1 )|s 0 = s i , a 0 = a] ≤ θ K+1 .Therefore, according to the fact thatP Q π (si,a) K,0 (π) ≤ Q π (s i , a) ≤ 1,we have that Q π (s i , •) satisfies Assumption 3.3 with Θ 1 = θ, Θ 2 = 1 and K 0 = 1.The function structure of finite horizon reinforcement learning on policy is strictly polynomial. Moreover, since the action-value functions on horizon h is only dependent of policy π h+1:H , we may therefore verify that the objective function of finite horizon reinforcement learning satisfies GQC condition by utilizing finite difference expansion on function error J π 1 (ρ 1 ) -J π * 1 (ρ 1 ). The finite horizon reinforcement learning considers the following policy optimization problem:EQUATIONwhere , we obtain the observation as Eq. ( 68).J π 1 (ρ 1 ) = E s1∼ρ 1 [V π 1 (s 1 )], and X = X 1 × • • • × X H ,EQUATIONSince Qπ h+1:H h (s h , a h) is a polynomial with respect to policy π 1:H , whose value is bounded by 1 + H -h for any s h ∈ S h and a h ∈ A h , we derive that J π 1 (ρ 1 ) satisfies GQC condition with internal functionF h,i h (π) = Q π h+1:H h (s h,i h , •) for variable block x h,i h where i h ∈ [1 : |S h |],and F satisfies Assumption 3.3 with θ = 0, Θ 1 = 0, Θ 2 = H and K 0 = H. Therefore, for finite horizon reinforcement learning, it follows from Theorem 3.5 that Algorithm 1 with parameter selection Eq. ( 7) finds an ε-suboptimal global solution in a number of iterations that is at mostO(H max h∈[0:H] log(|A h |)ε -1 log 4 (ε -1 )).We begin with showing the connection between GQCC condition and GQC condition. Without loss of generality, we assume n i = n and m i = m for any i ∈ [1 : d], and let ℓ = n + m. If f (•, y) and -f (x, •) satisfy GQC condition with respect to a pair of minimizers x * (y) and y * (x), respectively, then we have the following estimations of function errorEQUATIONEQUATIONwheref i (Q, z i ) = ⟨Q i , z i ⟩ for any Q ∈ R ℓ×d and z i ∈ R n+m, and each P i includes the internal function of f (•, y) for varriable block x i and the internal function of -f (x, •) for variable block y i . It follows from Eq. ( 69) and Eq. ( 70) that Eq. ( 10) holds for f with ψ i (z) = max{1/γ i (y), 1/τ i (x)}.In this section, we provide the convergence analysis of general version of Algorithm 2, i.e., Algorithm 4. We consider the divergence-generating function v with Bregman's divergenceV (i.e., V (x, u) = v(x) -v(u) -⟨∇v(u), x -u⟩ for any x, u) over general compact convex regions Z = X × Y ⊂ R d i=1 ni × R d i=1 mi. Before we introduce the main theorem, we need the following assumptions: Assumption C.1. There exists positive constants A, D such that[A 1 ] max i∈[1:d] {∥z i ∥} ≤ A uniformly on Z.Assumption C.3. In Definition 4.1, let matrix-valued function P has the form of P(Q z , z) where Q z ∈ R ℓ×d depends on z, and assume that P satisfies the following properties on regionQ ∈ R ℓ×d ∥Q∥ ∞ ≤ C} × Z for some constant C > 0: [A 4 ] There exist constants L 1 , L 2 ≥ 0 such that F i (•, z i ) is uniformly L 1 -Lipschitz continuous with respect to ∥ • ∥ * under ∥ • ∥ ∞ , and F i (P, •) is uniformly L 2 -Lipschitz continuous with respect to ∥ • ∥ * under ∥ • ∥.[A 5 ] There are a positive constant γ > 0 and a pair of sets of matrices{B i } d i=1 , {C i } d i=1 ⊂ R ℓ×d + ∪ 0 satisfying d i=1 (B i + C i ) ∞≤ γ, such that the following bounds holdD P(Q,•,y) (x, x ′ ) ≤ d i=1 C i ⟨F x i (Q, z i ), x i -x ′ i ⟩ , D P(Q,x,•) (y ′ , y) ≤ d i=1 B i ⟨-F y i (Q, z i ), y ′ i -y i ⟩ ,for any y, y ′ ∈ Y and x, x ′ ∈ X .[A 6 ] There exists θ ∈ [0, 1) such that P(•, z) is a θ-contraction mapping under ∥ • ∥ ∞ , and∥P(Q, z)∥ ∞ ≤ C for any z ∈ Z.Lemma C.4 (General Version of Lemma 4.3). Assuming that Assumption C.1 and C.3 hold, [P(Q, •,•)] k,j is continuous, and convex with respect to x, and concave with respect to y for any (k, j), and mink,j i∈[1:d] min{[Ci] k,j ,[Bi] k,j } [Ci] k,j +[Bi] k,j≥ C ′ for some C ′ > 0, then we claim that there exist Q * ∈ R ℓ×d andEQUATIONEQUATIONEQUATION)Proof. We shall begin the proof by proving the following lemma.Lemma C.5. Under the conditions of Lemma C.4, it can be proven that for any Q ∈ R ℓ×d , there exists a pair of x * , y * that satisfy the followingEQUATION)Proof. Considering the following iterationEQUATIONfor any i ∈ [1 : d] and combining [57, Lemma 1], we haveEQUATIONfor any i ∈ EQUATION)where the convexity of function [P(Q, •, w) -P(Q, u, •)] k,j for fixed Q and v = (u, w) implies (b), and (c) is derived from Eq. ( 76) and the definition that (x * T , ȳ * T ) := argmaxz ′ ∈Z [P(Q, xT , y ′ ) - P(Q, x ′ , ȳT )] k,j . Since Z is a compact set, the sequence {(x T , ȳT )} ∞ T =1must have a convergent subsequence. Therefore, all accumulation points of the sequence {(x T , ȳT )} ∞ T =1 satisfy Eq. ( 74) by using the continuity of P(Q, •, •). Now, we define the iterately update as followsEQUATIONwhere (x * t , y * t ) satisfies Eq. ( 74) in Lemma C.5 w.r.tEQUATIONEQUATIONFinally, according to the contraction mapping principle, we complete the proof.Corollary C.6. Assuming preconditions of Lemma C.4 hold, and letting {f i (Q, •) : R ni+mi → R} d i=1 be a sequence of continuous convex-concave functions which satisfies∇f i (Q, •) = (F x i (Q, •), -F y i (Q, •)) for any fixed Q ∈ R ℓ×d and i ∈ [1 : d],then there exist a matrix Q * and a pair of (x * , y * ) which satisfy Eq. (71)-Eq. ( 73) andf i (Q * , x * i , y * i ) ≥ f i (Q * , x * i , y i ), f i (Q * , x * i , y * i ) ≤ f i (Q * , x i , y * i ), for any z i ∈ Z i and i ∈ [1 : d].Proof. With proper selection of η, we have the following bound which is similar to that derived from Eq.( 77)EQUATIONfor every i ∈ [1 : d], where {z t = (x t , y t )} T t=1 follows from the iteration (75) and(z * T ) i = ((x * T ) i , (ȳ * T ) i ) denotes argmax z ′ i ∈Zi [f i (Q, (x T ) i , y ′ i ) -f i (Q, x ′ i , (ȳ T ) i )].Hence, by directly leveraging the result of Lemma 4.3, we obtain the result.Before stating the general version of Theorem 4.4 as follows, we define 73), with parameter configuration in Eq. (12), the weighted average of Algorithm 2's outputs {z t } T t=1 satisfies the following inequalityEQUATIONEQUATIONFor a generalized quasar-convex-concave function satisfying smoothness and recurrence conditions, the iteration complexity of our algorithm matches the lower bound [52] for solving ε-approximate Nash equilibrium points in the smooth convex-concave setting, up to a logarithmic factor. Furthermore, we prove that standard smooth convex-concave functions satisfy the preconditions of Theorem C.7 (as discussed in Appendix C.3.2).Input:z 0 i d i=1 = g 0 i d i=1 , {αt ≥ 0} T t=1 ( T t=1 αt = 1), {γt ≥ 0} T t=1 , {λt ≥ 0} T t=1 , η and Q 0 = 0. Output: zT = T t=1 αtz t . 1: while t ≤ T do 2: Q t = (1 -βt-1)Q t-1 + βt-1P(Q t-1 , zt-1). 3:for all i ∈ [1 : d] do 4:x t i = argminx i ∈X i η F x i (Q t-1 , z t-1 i ), xi + γtV xi, (g x i ) t-1 + λtv(xi),5:y t i = argmin y i ∈Y i η F y i (Q t-1 , z t-1 i), y i + γtV y i , (g y i ) t-1 + λtv(y i ),(g x i ) t = argming x i ∈X i η F x i (Q t , z t i ), g x i + γtV g x i , (g x i ) t-1 + λtv(g x i ), 7: (g y i ) t = argmin g y i ∈Y i η F y i (Q t , z t i ), g y i + γtV g y i , (g y i ) t-1 + λtv(g y i ).8: end for 9:t ← t + 1. 10: end while Our analysis relies on the connection between F i (Q t , z t i ) and F i (Q * , z t i ). Theorem C.8 combines a) classical O(log(T )/T ) bound derived from regularized OMD, and b) the weighted average of iteration error  and c ) weighted average of approximation error∥Q t -Q t-1 ∥ 2 ∞ over t ∈ [1 : T ] which has the form of T t=1 α t ∥Q t -Q t-1 ∥ 2 ∞ , with magnitude O(T -1 log(T )),∥Q t -Q * ∥ ∞ over t ∈ [1 : T ] which has the form of T t=1 α t ∥Q t -Q * ∥ ∞ tobound the max-min gap of f at zT . Next, we leverage Lemma C.9 to show the decreasing trend of approximation error ∥Q t -Q * ∥ ∞ and bound T t=1 α t ∥Q t -Q * ∥ ∞ by a quantity that grows only logarithmically in T . We may therefore obtain the result of Theorem C.7 by applying the estimation of weighted average of approximation error T t=1 α t ∥Q t -Q * ∥ ∞ to Theorem C.EQUATIONEQUATION)Suppose that v modulus 2 w.r.t ∥ • ∥, ∥z∥ ≤ A for any z ∈ Z, and {z t } T t=1 follows the iterations of Algorithm 4, then we can show that maxEQUATIONwhere B(ψ) := maxz∈Z d i=1 ψ i (z) and zT := T t=1 α t z t .Proof. Recalling the definition of GQCC, we derive thatEQUATIONfor any z = (x, y), v = (u, w) ∈ Z andEQUATION≤ T t=1 α t F i (Q * , z t i ), z t i -v i ≤ T t=1 α t F i (Q t , z t i ), z t i -v i + 2AL 1 T t=1 α t ∥Q t -Q * ∥ ∞ ,for any v i ∈ Z i . Using the optimality condition, we obtainEQUATIONEQUATIONFor each t ∈ [1 : T ], we can apply Eq. (89) and Eq. (90) to the following equationEQUATIONTherefore, by summing Eq.(91) from t = 1 to t = T and utilizing Eq. (84), we haveEQUATION)According to the Lipschitz continuity of F i , we derive thatEQUATIONIt follows from parameter setting Eq. ( 84) and Cauchy-Schwarz inequality thatEQUATIONCombining Eq. ( 85) and Eq. ( 94), we may therefore obtainEQUATION)Applying Eq. (93) and Eq. (95) to Eq. ( 92) and utilizing Eq. (87), Eq. (88), we complete the proof.∥Q t -Q * ∥According to the iterately update of Q t , we can derive the upper bound of weighted average of ∥Q t -Q t-1 ∥ 2 ∞ . Next, we aim to bound ∥Q t -Q * ∥ for each iteration t. In this section, we select the following parameter settings:EQUATION)Lemma C.9. Consider the settings:γ t = αt-1 αt ≤ 1, λ t = 1 -γ t , and η ≤ (1-θ) 1/2 8(γAL1L2) 1/2. Then, we obtain the estimation of ∥Q t -Q * ∥ as follows,EQUATIONfor any t ≥ 2 whereEQUATIONProof. According to the fact that Q * is a fixed point of function P , we haveEQUATIONWhere (a) is derived from the maximizer's property of y * for matrix-valued function P (Q * , x * , •).Similarly, we can obtainEQUATIONHence, we derive EQUATIONmax vi∈Zi t-1 κ=1 β t-1,κ ⟨F i (Q κ , z κ i ), z κ i -v i ⟩ as follows max vi∈Zi t-1 κ=1 β t-1,κ ⟨F i (Q κ , z κ i ), z κ i -v i ⟩ ≤ D η β t-1,1 γ 1 + 2 t-1 κ=1 β t-1,κ λ κ + 8ηA 2 L 2 2 β t-1,1 + 8ηL 2 1 C 2 t-1 κ=1 β t-1,κ β 2 κ-1 - 1 8η t-1 κ=1 β t-1,κ z k κ -z k κ-1 2 .(102)Furthermore, we also have a lower bound estimation of itEQUATIONTherefore, combining Eq. ( 102) and Eq. ( 103), we derive the following resultEQUATIONFinally, by applying [67, Lemma 33] to Eq. ( 105), we complete the proof.Under parameter settings Eq. ( 96), the following auxiliary Lemma C.10 provides both lower bound and upper bound of β T,t .Lemma C.10. Assuming that β t = c ′ c+t and c ≥ c ′ , we can obtain the following result:EQUATIONfor any T ≥ t ≥ 1.Proof. Recalling thatEQUATIONwe haveEQUATIONandEQUATIONby combining the result of Lemma D.9.Corollary C.11. Assuming thatEQUATIONfor any T ≥ t ≥ 1.By utilizing the result of Lemma C.10, we notice thatEQUATIONandEQUATIONwhere (a) and (b) are derived from the fact that j-2 κ=1 (c + κ + 1) c-2 ≤ j-1 1(c + x + 1) c-2 dx. Next, we haveEQUATIONandEQUATIONwhere (c) follows from Corollary C.11. For simplicity, we denoteEQUATIONTherefore, it follows from Eq. ( 114) and Lemma C.9 thatEQUATIONAccording to Eq. ( 116) and the initial Q 0 satisfies ∥Q 0 ∥ ∞ ≤ C, we have ∥Q * ∥ ≤ C. We are ready to complete the proof of Theorem C.7.Proof of Theorem C.7. It is noteworthy that the hyper-parameters selected in Eq. ( 96) satisfies the preconditions of Theorem C.8. Combining the conclusion of Theorem C.8, Eq. ( 116) and the estimation of α t (i.e. β T,t ) in Lemma C.10, we obtain: EQUATIONz = Q z (s 1 , •, •), • • • , Q z (s |S| , •,•) the joint action-value matrix where Q z (s i , •, •) ∈ R |A|×|B| is an action-value matrix on state s i . According to the connection between value function and action-value functionV z (s i ) = E a∼x(•|s i ) b∼y(•|s i ) [Q z (s i , a, b)], Q z (s i , a, b) = (1 -θ)σ(s i , a, b) + θE s i ′ ∼P(•|si,a,b) [V z (s i ′ )],we provide the following proof for Proposition 4.5.Proof of Proposition 4.5. By definingEQUATIONwe derive that Q z = P(Q z , z). We can notice thatEQUATIONTherefore, for any Q satisfies ∥Q∥ ∞ ≤ 1, it's easy to verify that 1. Therefore, according to Lemma 4.3, there exist a tensor Q * and a pair of (x * , y * ) satisfy Eq. (11) . Furthermore, the (x * , y * ) mentioned above is a Nash equilibrium of J x,y (ρ 0 ) by utilizing Corollary C.6. We may therefore derive that Q * ≡ Q z * . Leveraging Eq. ( 65) for any Nash equilibrium (x * , y * ) ∈ Z and denoting QEQUATIONEQUATIONwhere x * (y) = argmin u∈X J u,y (ρ 0 ) and y * (x) = argmax w∈Y J x,w (ρ 0 ). Similarly, we haveEQUATIONBy setting ψ i (z) := max{d x,y * (x)EQUATIONIn this section, we consider convex-concave minimax problem over compact concave region Z = X × Y ⊂ R where f is convex with respect to x and concave with respect to y. Therefore, we obtain thatEQUATIONfor any z = (x, y) ∈ Z. We may therefore derive that f satisfies GQCC condition with g(z) ≡ 1 and f (P(z), z) = f (z). Furthermore, assuming ∇f is L-lipschitz continuous (i.e., ∥∇f (z) -∇f (v)∥ * ≤ L∥z -v∥ for any z, v ∈ Z) and choosing P ≡ 0, then verifying that f satisfies the preconditions of general version of Theorem C.7 is reduced to verifying that f satisfies (1) in Assumption C.3. Since F = ∇f only depends on variable z, it is evident that f satisfies (1) in Assumption C.3 when ∇f is L-Lipschitz. Therefore, under the smoothness condition of f , Theorem C.7 implies that O(ε -1 ) iterations Algorithm 4 needs to find an ε-approximate Nash equilibrium of f matches the lower bounds of Ω(ε -1 ) [52] for the number of iterations that any deterministic first-order method requires to find an ε-approximate Nash equilibrium of a smooth convex-concave function.Lemma D.1. For Γ ≥ 17, the function g(Γ) can be bounded by 80640 Γ-1 + 2 Γe -2 -1 . Let g(Γ) be defined asEQUATION(a) can be deduced based on the following inequality EQUATIONProof. We just need to prove p * (i) ≡ p ′ (i) := q(i) exp{-ηr(i)} n j=1 q(j) exp{-ηr(j)} for any i ∈ [n] which satisfies ⟨p -p ′ , ηr + log(p ′ ) -log(q)⟩ = 0,for any p ∈ ∆ n . Assume that F (p) := η ⟨p, r⟩ + KL(p∥q) and defineEQUATIONwhere (a) is derived from Eq. (129). Therefore, we obtain that p * ≡ p ′ . By using equality (b), we finish the proof.Lemma D.3. Suppose that for τ ∈ (0, 1), we havep q ∞ ≤ 1 + τ . Then 1 -τ 2 - 2τ 3(1 -τ ) X 2 (p, q) ≤ KL(p∥q).Proof. We consider the Taylor expansion of the function logEQUATIONfor any x ∈ [-τ, τ ], we have logEQUATIONWe complete the proof ifEQUATIONThenEQUATIONProof. Without loss of generality, we consider the case ⟨p, r⟩ = 0. If not, redefine r := r -⟨p, r⟩ • e(∥r∥ ∞ ≤ τ ) and analyze r where e ∈ R n is an all 1 vector. It's clear thatEQUATIONWe defineEQUATIONEQUATIONwhere Eq. ( 136) is derived from the summation of the 2k-th and 2k + 1-th (k ≥ 2) terms in the Taylor expansion of exp{x} is always non-negative, Eq. ( 137) is derived from∞ k=3 x k k! ≤ |x| 3 6(1-x) ≤ |x| 3 6(1-τ ) for any x ∈ [-τ, τ ]. Therefore, we have exp{x} -F 1 D (x) ≥ 0 and F 2 D (x) -exp{x} ≥ 0 for all x ∈ [-τ, τ ] if D ≥ 1 3(1-τ ). Then, we haveEQUATIONwhen Dτ ≤ 1 2 . In addition, by ⟨p, r⟩ = 0, it's obvious thatEQUATIONCombining Eq. ( 138) and (139), we derived thatEQUATIONEQUATIONfor Dτ ≤ 1 2 . According to Eq. ( 135) ,( 140) and (141), we have-1 + E p exp{r} E p [exp{r}] 2 ≥ (1 -(2D + 3)τ )E p [r 2 ] 1 + (1 + (D + 1)τ )E p [r 2 ] ≥ (1 -(2D + 4)τ )E p [r 2 ], -1 + E p exp{r} E p [exp{r}] 2 ≤ (1 + (2D + 3)τ )E p [r 2 ] 1 + (1 -(D + 1)τ )E p [r 2 ] ≤ (1 -(2D + 4)τ )E p [r 2 ].We derive Eq. ( 134) by setting D = 1 3(1-τ ) . Lemma D.5 (Lemma B.6, [15] ). Let ϕ 1 , • • • , ϕ l be softmax-type functions.EQUATIONwherej i ∈ [1, • • • , n], n k=1 τ ik = 1 for any i ∈ [1, • • • , l]. Let P (x) = k=0 |α|=k D α P (0) α! x αdenote the Taylor series of l i=1 ϕ i . Then for any integer k,EQUATION)We introduce the conception of (Q, R)-bounded function briefly. Suppose ϕ : R n → R is realanalytic in a neighborhood of the origin. For real numbers Q, R > 0, we say that ϕ is (Q, R)-bounded if the Taylor expansion of ϕ at 0, denotedP ϕ (x) = ∞ k=0 |α|=k D α f (0) α!x α , satisfies, for each Lemma 4.5, [15] ). Suppose that h, n ∈ N, ϕ : R n → R is a (Q, R)-bounded function such that the radius of convergence of its power series at 0 is at least ν > 0, andinteger i ≥ 0, |α|=k |D α ϕ(0)| α! ≤ Q • R k . Lemma D.6 (Detailed version ofEQUATION) where g(Γ) is a bounded function with respect to Γ.Proof. Without loss of generality, we assume ϕ(0) = 0.We define (ϕ • Z) t = γ∈Z n ≥0 :|γ|=k a γ Z t γ and obtainEQUATIONwhere (c) is derived from (Q, R)-bounded condition. (147) Lemma D.9. For a constant c ≥ c ′ > 0, the following inequality holdsEQUATIONwhen T > t ≥ 1.Proof. Accoding to the Taylor expansion of log(1 -x) when x < 1, we obtain the estimation of log 1 -c ′ c+k for any k ≥ 1 as followsEQUATION) log 1 - c ′ c + k ≥ - c ′ c + k - (c ′ + cc ′ ) 2 2 1 c + k 2 .(150)Next, we haveEQUATIONEQUATIONFor objectives with GQC condition (GQCC condition) and general smooth internal function (i.e. Lipschitz continuous internal function), our analytical method might not provide similar iteration complexity. We leave the related algorithmic analysis on more generalized smoothness conditions as a future work.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 


Decision: This paper introduces "generalized quasar convexity" and shows that the optimization problems of (P1) Tabular Infinite Horizon reinforcement learning problems and (P2) Two-Player Markov-Zero Sum Game satisfy the condition. Iteration complexity of Optimistic Mirror Descent for these two applications using the generalized quasar convexity is provided. 

An issue raised during the discussion is that the iteration complexity is not better than the existing results in the literature, and the authors, in the current version, were not explicit about the comparison.  Specifically, for (P1), the current version does not explicitly state the best iteration complexity in the related works; for (P2), while it mentions that the result matches the state-of-the-art iteration bound, no citations are provided. Therefore, the usefulness of the proposed "generalized quasar convexity" might not be completely clear, and the authors might want to discuss more in the next version.

While the paper is recommended for acceptance, a more comprehensive discussion of the literature on (P1), (P2), and quasar convexity should be provided in the next version. It would also be illuminating to discuss how existing results on P1 and P2 were derived, such as using the PL condition (Gradient-Dominance Condition), and if the existing conditions used in the related works could be related to the proposed generalized quasar convex condition for these two problems.

Reviews: review: paper_summary: paper_summary: The paper studies the optimization of generalized quasar convex (GQC) functions, a new global
structure introduced in this paper. This definition relaxes the quasar convexity (QC) 
condition, in a way that different components of the optimization variable satisfy 
the QC like condition with different parameters.
The key idea is that if we simply treat a GQC function as a QC function, one needs to take
d times the maximum value of these paramters which can be large. Applying GQC allows one 
to deal with the sum instead which could be significantly smaller than d. Leveraging this 
insight, the authors adapt the well-known optimistic mirror descent algorithm.
The main use case appears to be in policy optimization in MDPs, where the authors show 
that the GQC condition is shown to be satisfied by the expected value function.
The authors also define a similar condition for minimax optimization problems, and apply 
their framework to find the Nash equilibrium of a two-player zero sum Markov game.

Overall my evaluation of the paper is quite positive. Even as a non-expert, I was able to
appreciate the ideas and the contributions of the authors. The paper is also well-written
and easy to follow.

I have given a positive score to reflect my current assessment. However, as this is not 
my area, I am unable to evaluate the technical merit and novelty of proot techniques in
the paper, and I did not dive into the proofs in the appendix. So I will also wait to hear
from more expert reviewers.
strength_weakness: strength_weakness: See above
questions: questions: See above
limitations: limitations: See above
paper_summary: paper_summary: This paper introduces a novel optimization model for addressing problems involving multiple probability distributions, a common scenario in fields such as policy optimization and reinforcement learning. The authors present a new structural condition called Generalized Quasar-Convexity (GQC), which extends the original quasar-convexity concept by allowing individual quasar-convex parameters for each variable block. This flexibility accommodates varying degrees of block convexity. The paper proposes an Optimistic Mirror Descent (OMD) algorithm tailored to this framework and demonstrates its efficiency in achieving an ε-suboptimal global solution. Furthermore, the paper extends the GQC concept to minimax optimization problems by introducing the Generalized Quasar-Convexity-Concavity (GQCC) condition. The theoretical findings are supported by applications in discounted Markov Decision Processes (MDPs) and Markov games, showing improved iteration complexity bounds over existing methods.
strength_weakness: strength_weakness: - The assumptions made for the GQC and GQCC conditions, such as polynomial-like structures and specific Lipschitz continuity requirements, may limit the generality of the results. It would be beneficial to discuss the applicability of these assumptions in broader contexts.

- While the theoretical contributions are robust, the paper lacks empirical validation through extensive experiments. Including experimental results on synthetic and real-world datasets would strengthen the paper by demonstrating the practical performance of the proposed algorithms.
questions: questions: Yes
limitations: limitations: - How do the assumptions made for the GQC and GQCC conditions compare to those in other optimization frameworks? Are there potential relaxations or alternative conditions that could be explored to broaden the applicability of the proposed methods?

- Can you provide more detailed insights or examples of real-world problems where the proposed GQC and GQCC conditions are particularly beneficial? How do these conditions improve the solution quality or computational efficiency in such scenarios?
paper_summary: paper_summary: The authors study a typical optimization model where the optimization variable is composed of multiple probability distributions. For this optimization problem, they propose a new structural condition/landscape description named generalized quasar-convexity (GQC) beyond the realms of convexity.
strength_weakness: strength_weakness: It would be better if the authors added more motivation for why they focus on quasar optimization. 

Another point: the theoretical analysis demonstrated is not very clear. If they can show it clearer, it will be better,
questions: questions: Does the assumption 4.2 can be relaxed? 

Can the Section 4.3 be written more?
limitations: limitations: No
paper_summary: paper_summary: The paper considers a minimization problem, where the optimizing variable is composed of $d$ probability distributions. The notion of quasar convexity is generalized by allowing for different quasar-convexity parameters $\gamma_i, i=1,...,d$ for the $d$ distributions. Instead of using the gradient function for the oracle term, more generic functions $F_i, i=1,...,d$ ("internal functions") are allowed.
Convergence guarantees are established for the situations where the interval functions are either Lipschitz continuous of "polynomial-like". 
Infinite horizon reinforcement learning is shown two be a special case of this setting. Similar results are derived for the minimax setting.
strength_weakness: strength_weakness: * Algorithm 1 and Algorithm 2 are never actually described in the text, they are only provided as pseudocode. It think it would be nice to add 2-3 sentences to point out how exactly it differs from basic mirror descent. Example given, I don't understand why one randomly picks t following probability $\mathbb{P}[t] =1/T$.  
* There is "only" one example (the reinforcement application) for the new structure the paper introduces. I am not sure if one example is enough to justify speaking of a new structure. (But I also understand that such examples are complex and it might go beyond the scope of the paper to come up with several such examples)
* the paper does not mention the computational costs of the algorithm. Is it $d$ times as much as basic mirror descent? Is this still feasible in praxis?



Typos:
* Headline Algorithm 1: Mirior -> Mirror
* line 206: depends -> depend
questions: questions: * I am confused about the following part in the introduction (line 62-65): "We then study designing efficient algorithms to solve (1). One simple case is when $\gamma_i, i=1...m$ is pre-known by the algorithms. The possible direction is to impose a $\gamma_i$-dependent update rule, such as by non-uniform sampling. However, in general cases, 
$\gamma_i, i=1...m$ is not known and determining $\gamma_i, i=1...m$ require non-negligible costs." Can you elaborate on this?
limitations: limitations: I don't see that the authors explicitly mention limitations of their work, but it is also a theoretical paper, so everyone can just read the assumptions at the beginning of the theorems to see where the results apply and where not. The assumptions made for the theoretical analysis are stated clearly.

Comments: comment: Thank you for the clarifications. I keep my positive score.
Dear reviewer,

Thank you for your efforts in the review process. We have tried our best to address your concerns and answer the insightful questions. Please let us know if you have any other questions regarding our paper or response. If we have successfully addressed your questions, we would greatly appreciate if you can reevaluate the score.

Best,

Authors