Optimizing over Multiple Distributions under Generalized Quasar-Convexity Condition
Authors: Shihong Ding
Long Yang
Luo Luo
Cong Fang
Venue: NeurIPS 2024 poster (2024)
Keywords: Generalized Quasar-Convexity
Generalized Quasar-Convexity-Concavity
Primary area: optimization

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.

Optimizing over Multiple Distributions under Generalized Quasar-Convexity Condition
Shihong Ding'
Long Yang' WANCLONGO1@@pku.com edu.
dingshihongestu. pku. enu.cn
Luo Luo 2,4 Luoluoffudan, edu. en
Cong Fang 1.3 fangcongépku. edu. on
State Key Lab of General AI, School Intelligence Science and Technology. Peking University
2 School of Data Science, Fudan University
Institute for Artificial Intelligence, Peking University
4 Shanghai Key Laboratory for Contemporary Applied Mathematics
Abstract
We study a typical optimization model where the optimization variable com- posed of multiple probability distributions. Though the model appears frequently in practice, such for policy problems, lacks specific analysis the general setting. For this optimization problem, we propose new structural condition/landscap description named generalized quasar-convexity (GQC) beyond the realms of con- vexity. In contrast to original quasar-convexity (24), GQC allows an individual quasar-convex parameter "/ for each variable block and smaller of 7/ implies less block-convexity. To minimize the objective function, we consider generalized oracle termed as the internal function that includes the standard gradient oracle as special case. We provide optimistic mirror descent (OMD) for multiple distri- butions and prove that the algorithm can achieve adaptive Ó( 1/xx)--1) iteration complexity to find an e-suboptimal global solution without pre-known the exact values of 7, when the objective admits "polynomial-iike" structural. Notably, it achieves iteration complexity that does not explicitly depend on the number of distributions and strictly faster (wi i= 1/7s v.s. d maxxe[1dd] L//x) than mirror decent methods. also extend GQC to the minimax optimization problem proposing the generalized quasar-convexity wtt---ooovexit-oociiityy (GQCC) condition and decentralized variant of OMD with regularization. Finally, we show the appli- cations of our algorithmic framework discounted Markov Decision Processes problem and Markov games, which bring new insights on the landscape analysis reinforcement learning.
Introduction
We study common class of generic minimization problem
min =
f(x),
where the optimization variable z is composed of d probability distributions (x, ) and denotes the product space of the probability simplexes. Problem meets widespread applications in
Corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

reinforcement learning optimization 662 2 351, multi-class classification [33 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 dl non-explicitly.
When f is convex with respect a; many efficient algorithms can be powerful tools for solving Problem ( 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 I 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 [3] [9]] 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. 3 only focus on the consideration of Lipschitz continuity of the gradient and some higher-order 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 [2]. As pointed out by Hinder et al. [24), much more research 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 quasar- convex functions 22 is parameterized by a constant 7 E (0, 1] and requires f(x) f(x") < 7 (V)()) x x²). These functions are unimodal on all lines that pass through a global minimizer and so all critical points are minimizers. We extend guasar-convexity by introducing individual quasar-convex parameter ?/t for each distribution T; Therefore GQC parameterized by d constants {rr] and implies quasar-convexity in the case d = 1. The main intuition of the generalization is the observation that d/ min.e(1:d, 7/2 often depends on the number of distributions d in real problems,
whereas, Σ 1/y; may not. That is to say, the hardness for distribution i diverges according the magnitude of %- The larger of 7/8 implies more convexity and the simpler to solve 2;. In general, one always have Ei=1 1/11/ I d max4e(1:d) [1:d] 1/%/ In the worst case, Σ'= 1/% can be d times smaller than d (a 1/7 (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 { is pre-known by the algorithms. The possible direction is to impose 71-dependent update rule, such as by non-uniform sampling. However, in general cases, { is not known and determining { require non-negliiible costs.
1m
In this paper, we consider generalized oracle, which we refer to as the internal function. Here the standard gradient oracle can be viewed as special case of the internal function. We pro- vide 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 ((dTmaxx)
( (2 25 113/ " complexity with N max ni and Tmax max,g(L:d] 7/4 when Tmax < 00. However, such an complexity depends on drymax and requires the step
size rely on pre- pre-known 7max
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 impor- tant machine learning problems. Under the assumption, we show the algorithm can adapt to the values )mm) In the following, the (() notation hides factors that are polynomial in log(s and log(AV).
Ei=1
of (7% m and guarantees an reduced iteration complexity O 1/7s)e log(N) log 2.5(c ()-"))
We also extend our framework to the minimax optimization
min max f(x 8), øE yEY
(2)
2

---

Solution type
Related work
Iteration complexity
Single loop
Convexity condition has been studied at length and plays a critical role in optimizing Several other "convexity- -iiee" conditions have Cen et al.
x
Chen et al.
(1 =
Wei et al. 67
Is|s
V
(1-0)>²²
e-approximate NE
Cen et
10
[S] (1-0)at
This Work
[1 0)2260
Table 1: Comparison of policy optimization methods for finding e-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 al. [75), Alacaoglu
and Zeng et al. (72l) involve concentrability coefficient and initial distribution mismatch coefficient, we will not delve into them here.
where both æ and y are composed of d probability distributions, and Z X x y 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-convexity-
concavity (GQCC) condition analogous to GQC and demonstrate the feasibility of obtaining an
e-approximate Nash equilibrium with O((1 0) 2.5 max (E Ei=1 (>)()))== log(M) log(=-1))
iteration complexities, where m (Ei dd th (z)) is analogous to (Ei 1/ms) with (2(()) defined in the GQCC condition; 0 is the discount parameter; M = ma {m, + n.). Intuitively, the GQCC condition can be viewed as the generalization convexity-concavity condition. Similarly, the (+) notation hides factors that are polynomial in log(s-1) and log(M).
Finally, demonstrate the applications of our framework. For problem I. 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 loga- rithmic factors. We provide Ö(= iteration bound for finding an e-approximate Nash equilibrium of infinite horizon two-player zero-sum Markov games, which outperforms the Ö([S)= 2) bound of Wei et al. 667 and the (( bound of Cen et al. [T0 by factors of [ and (S), respectively, up logarithmic factor.
1.1
Contribution
(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 Ö( d find e-suboptimal global minimum of "polynomial-like" function under GQC. We also provide an implementable minimax algorithm, given a generalized quasar-convex-coccaee
1/m))-1) iteration complexities to
function with proper conditions, uses Õ((1 0) 02.5. maxxez( (x())) e11 iterations to find an e-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, provide Õ 0) - 2-5 iteration bound for finding e-approximate Nash equilibrium of infinite horizon two-player zero-sum Markov games. Detailed comparisons between our method and prior arts are provided in Table T
1.2 Related Works
Minimization:
minimization problems (59
44
25
60
49

---

attracted considerable attention, which provide opportunity for designing algorithmic framework to achieve global convergence. Star-convexity 47 a typical example that relaxes convexity, showing 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
potential in machine learning recently 32 76
star-convexity in the differentiable case, and Hinder et al. (24) provides lower bound for the number of gradient evaluations to find an s-minimizer of quasar-convex function (a linguistically clearer
redefinition 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 4 48
45 40
66, [27] or stationary points [7]] for convex-concays functions. Without convex- concave assumption, there exist related work considered specific structures objective, including nonconvex- (strooggyyyooooooccccco assumption [9) 73 50), -oodyka-Lojasiewiez condition (or specific
33
55
PL condition)
68
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-modiffed policy iteration algorithm [0] 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
42 under full information setting, there are various 70 have been proposed. Specifically, Cen al. [ 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 Ö(e-1) iteration bound which depends on the concentrability coefficient; Yang and Ma
61
algorithms [26 55 64 18
42 67
744
(70 focus on finding approximate Nash equilibrium in standard finite horizon setting with O 2) iteration bound.
Related Works on Optimistic Mirror Descent (OMD) and Optimistic Multiplicative Weights
Update (OMWU): 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 [4
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.
2 Preliminary
Notation: Let æ = (æi),... (.)) E RE- the be the joint vector variable, for every vector variable x; E I2 Let (a(1), ..................... an)) be the multi-indices, where axii) Z4. we define |a| Σi= a(t) and a! = a (n)). For any vector u = (u(1),... uun)) E R", we define n²th = u(1))(1)) ... -.nnn())))))) Let f R. IR be a smooth function, we expand its Taylor expansion with Lagrange remainder
as follows,
K
D f(w) ad!
R/, nn (1) = f(u)
(u w)a
(3)
1=0 |a|
Given matrices Q and P in X we claim that Q < P if
Q ij - Plas S 0 for every i.j.
For sequence of valued functions (F.) we say that
{F
ld :=1 is uniformly L-Lipschitz
continuous with respect to ||-|]- under ||- if F (z:) F, (u,)),
< L L u. for every i E [1 df
and any x, X. We denote by ||-1|= || the dual norm of || || Let P Raxe + R be matrix
function, we say that P is a --contractionn mapping under ||. if [P(Q1)
P(QQ < < -z Q2i
for any Q Q2 E & xt2, For matrix-valued function P R. R x2, we define Dp xx)
P(z) P(x') for any x, x E R". The KL divergence KL(p))q)
Σラ p()) log (0)
p()
between distributions p and is defined on probability simplex An- And the variance of x over
is defined by Varp = p(j) (xx(s) ()))) We define max-min gap of function
4

---

x:Xx> + R as follows,
(5( = max f(z y') y'
min f( :)) x'ex
(4)
We claim that (æ), 3) is an E-approximate Nash equilibrium (s-approximate NE) if gy(2, y) S When 0, (a, y) is Nash equilibrium.
Infinite Horizon Discounted Markov Decision Process: We consider the setting of infinite
horizon discounted Markov decision process (MDP), denoted by M == (S, A, IP, a, 0, Po). - S is finite state space: A finite action space; [ a') denotes the probability of transitioning from to s' under playing action a'; a S x A + [0. 1] is a cost function, which quantifies the cost associated with taking action in state 8; 0 [0, 1) discount factor; Po is initial state distribution over S.
S + AA (where A is the probability simplex over A) denotes stochastic policy, i... the agent play actions according to a ~ (-1s). We use Pr, (s'[s) Pr = s'|s0 = 5) to denote the probability of visiting the state s' from the state after time steps according to policy trajectory: {(t,,a) J-- where 8o ~ and, for all subsequent time steps f, dz ~ (1(())) and 8141 P(-|a,, az). The value function V S - IR defined as the discounted sum of future cost starting at state and executing π, i.e.
Let
V (s)
0)E
Σ t=0
0' ('o
T,
Moreover, we define the action-value function Q" -xxA + and the advantage function A S A + R as follows:
Q" (1 01EE
Σ 0' (st n. 8,00 8,00= = (= (=)aaa) (s).
It's also useful to define the discounted state visitation distribution d of policy as d (s) (1 - 0) Et= 0'Pr," (s|so). In order to simplify notation, we write dtt (s) = Eer-p, (s)], where dp is the discounted state visitation distribution under initial distribution Pa-
3 Minimization Optimization
In this section, we propose the generalized quasar-convexity (GQC) condition, and analyze a related algorithmic framework for minimization over X' = I[ An; under mild assumptions.
3.1 Generalized Quasar-Convexity (GQC)
We provide novel depiction of function structure -eetrraiiege quasar-convexity. which is defined as follows:
Definition 3.1 (Generalized Quasar-Convexing (GQC)), Let xt E X' C RE be a minimizer of the function f X R. We say that f is generalized quasar-convex X' with respect x if for all x X. there exist sequence of vector-valued functions [F, X + a Ri= and sequence of positive scalars (1:) such that
f(x') 2 f(x) +
(F) xx)
(5)
If Eq. (5) holds, we say that F = [F [FI,.... 1 say that F, is the internal function of f for variable block æ;,
is the internal function of f. Given i E [1 d] we
Our proposed GQC condition concerns the multi-variable generalized extension of the quasar- convexity condition. In the case 1, the GQC condition degenerates into the 7-quasar-convexity condition as studied in Hinder et al. [24 with the gradient ( belongs to the internal functions of f. In the case d > the GQC condition is instrumental in capturing the crucial characteristic of those optimization applications with each variable block has difficulty to be optimized.
5

---

Algorithm Optimistic Mirror Descent for Multi-Distribttions
Input: {o. = = (I/ma... .1/n,]] k-1' and T.
Output: Randomly pick up E {1, (T' following the probability P(t] = 1/ll' and return æ'.
I: while - T do
2:
for all i E [1 d] do
a = argmin 7 (F, (ax (al="), + KL (a: (lg)- =;E0n,
4:
g argmin 77 (Fi(x"),,) 9.) KL (9. llg
a.eAm,
5:
end for
6:
1 <- L 1
7:
end while
3.2 Main Results
Recall that GQC condition provides a perspective 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 function. Given an objective function f X > R. with internal function F, our algorithm (Algorithm Tb independently computes points g and at following OMD over each block. If [1x 7/ < and internal function F has Lipschitz continuity, we have following basic and primary convergence result of Algorithm !
approximate suboptimal global solution using internal
Theorem 3.2. Assuming that F is L-Lipschitz continuous with respect to I
ll. under and Mmax [l.4] Vi and setting r7 (L2d" E 2) 1/2/2 have
2L maxie(ldd] log(n,) (dymax) 1/2
(Ii= 7/4
3/2
1 +
-(())))((")
(6)
However, the estimation provided by Theorem 3.2 depends on dm And the step size relying on might be difficult to set when {7:){_) unknown.
Ymax EE=
We then hope propose alternative analytical method that can adapt unknown { and obtain complexity which does not depends on block dimension d explicitly. The challenges includes: 1) The algorithm does not know the weight 1//;; 2) every F, has dependence on the joint variable x instead of depending on x; Before we present the details of convergence analysis, we need the following notations and assumptions:
pf Denote P (x)) Σk Eja|= Da f(wll (|arl ly|)a and let Pxyy(() (z) (P& (æ),.... poll) K,y (a)) for any vector-valued function Φ R" R Recalling the definition of RK in Eq.
we shall also define d (x) = (R (x), ... ( (z)).
Assumption 3.3. Let be the internal function of f. There exists O1, O2 > 0, Ko E Z,, and
0 E [0, 1), and fixed E RE such that
[Ai]
RR,y (x)
< 0K for any integer K > Kg and x e X.
[Aa] Pkyy (x)
θ for any integer K Z, and x E X.
8
Assumption 3.3 is a characterization of "polynomial-like functions. We clarify this view as follows. For standard polynomial function p, it's clear that p satisfies Assumption 3.3] since the Taylor expansion of after order Ko is always equal to 0 ([A1] in Assumption 3.3 holds) and X' is bounded and closed set ([A2] Assumption 3.3 holds). Assumption 3.3 easy to achieve. Shown in Proposition and
and Remark B.3 in Appendix B Assumption 3.3 can be satisfied by many smooth
functions defined on bounded region X. In addition, we introduce simple machine learning example:
learning one single neuron network over a simplex in the realizable setting.

---

P.o(2 P,) - -y) where E II:=1 Au and the target y given E [-C, C7 admits y = Pi) for some Pi Ad- For activation function (zz) exp(x). f satisfies GQC condition and Assumption 3.3 with the internal functions F₂ = 1 P,) (a: P.) )
Example 3,4. The objective function is written as P) Am and P PI..... .mm)
for block p and Pp.- [[ P;) y)]r for block P
Note previous work [65] studies single neuron learning by considering P in the sphere and assuming 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, set the parameters follows:
Po = (4H)-) B -min {
Ba/8
1
θ - θ + +1
H = [lo[(11)),
H3
201H +3)
I (ogg log(O1) -oo 3 7=min
3
r e² 002)), k max
min 6e RT max f 1)
log(0-1)
O())
(7)
Theorem 3.5. Let f satisfies the GQC condition and denote N- [ {ng]. Under Assumption 3.3 the following estimation holds for Algorithm oulput {x²)²==
T T E((a')) -((=))))) S
Σ 1/7s
log(N)+ + 0 + 3302400HH T-1,
(8)
Theorem 3.5 implies that for any generalized quasar-convex function f satisfies Assumption 3.3
the 7- Ttep random solution outputted by Algorithm | is O( log))T-loo 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 22.. Moreover, our algorithm makes iteration complexity
depend on Σ 1/7 linearly. In some common applications, > 1/7g has no dependence on d,
which is the number of variable blocks (see discussions in Section 3.3
3.3 Application to Reinforcement Learning
This section reveals that GQC condition provides a novel analytical approach to reinforcement learning. We show how to leverage Algorithm to find e-suboptimal global solution for infinite horizon reinforcement learning problem. And in Appendix[B.3x we show how to leverage Algorithm to minimize finite horizon reinforcement learning problem.
The infinite horizon reinforcement learning is formulated the following policy optimization problem:
min J (P()), xEX
where J (pp) = Exoopo (V and = [1 AA denotes |S] probability simplexes. We write
S= -= and denote the action-value vector state 8; by Q" (s;..). The next Proposition 3.6 states that J (Po) satisfies the GQC condition for any initial state distribution Po-
Proposition 3.6. Let (-Is) AAtseS denote the optimal global solution of problem
We
have that J (po) satisfies the GQC condition in Eq. (5) with internal function F, F((T) Q" (81,
for variable block n; and F satisfies Assumption 3.3 with O = 0, θ = and K =
According Theorem 3.5, if we apply Algorithm to the infinite horizon reinforcement learning basing action-value vector Q with parameter selection Eq. 7 which is actually simple variant of natural policy gradient descent (2), then the iteations 7 we need to find e-suboptimal global solution (8-
is upper-bounded by O(max 2 setting. Therefore, the iteration complexity of Algorithm [ does not depend on the size of states,
-1 1og4.5((
log([AA)) under Agarwal et al.
since the summation of d% over S (2 1/x
| Diml dp, (s.) = 1) mollifies the accumulation
7

---

of the maximum of d% over S with |S] times. Specifically, if we take into account the loosest upper bound |S| max4e[1:|s[] d (si), then the iteration complexity of algorithm may suffer from the linear dependence on |S], since maX]e(1:[s] dr (s;) 2 (1 1- -) [IXss( Po(ss). Previous research
12 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 - - iteration complexity. However, their analytical approach carcfully designed for infinite horizon reinforcement learning problems.
4 Minimax Optimization
In this section, we introduce the generalized cowaarr-ooexxxxcocncneoec (GQCC) condition, which can be verified in real applications such as two-player zero-sum Markov games. We provide related algorithm for minimax optimization (minimizing gy( y) has been defined in Eq. 4
over 2 = -I 2, -T= AA, x Am.) ). under proper assumptions. We specify the divergence-
i=
generating function v(x) -)) [[)]] in probability simplexes setting. We also provide
framework for minimax problem over the general compact convex regions in Appendix C
4.1 Generalized
(GQCC)
We provide new notion called generalized quasar- quasar-convexity -onnnxixttyconcvvity for nonconvex-nonconee minimax optimization, which is defined as follows:
-oeecvttCoo (GQCC)). Denote Z, = = X; x 3 for any i E [1 : d]. and let f Z + R be the objective function. We say that f is generalized quasar-convex- concave on if for all z = (x, y) E Z, there exist sequence of functions {fa : fxd d Z, + R j= sequence of non-negative functions {1hy : Z - R2 00 and a matrix-valued function P = (P,, Pa) Z exd where every P, is E-dimensional vector-valued function, such
Definition 4.1 (Generalized
that
( & Σ
(10)
where each fi(Q. .)) is convex-concave for a fixed Q= ( 1 QQ) E Rexd We denote the in- ternal operator of f for variable block 2; by F, where (Q, 2,) ((V.. 2,)) f,
z;)) T)T. Moreover, we say that F = (F
F 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 extension of the convexity- convexity-concavityy condition in multi- aauriila optimization; it seamlessly reduces to the convexityconncvvity condition with (P(x), x) = =(z) and t (z) = 1, in the case d 1. Assuming every t. is bounded, f((((z), 2;) f0 2;) with Lipschitz continuous gradient and is convex-concave with respect to z;, 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.
4.2 Main Results
For simplicity, we denote by F. and FV the projection of F; in the a. and y, directions, respectively. ie., F. = ((FT),,
(F)) Given objective function f Z + R with internal operator F, our algorithm (Algorithm 2 employs regularized OMD over each distribution independently basing on F, and updates matrix Q' to track the behavior of function P iteratively. It's worth noting that each iteration of Algorithm 2 provides explicit expressions for ac and g (see the proof of Theorem 3.5 in single-loop algorithm.
Appendix B). Consequently, Algorithm essentially operates
Assumption 4.2. Definition 4.1 we assume that vatrix-valued function P has the form of P(Q x) where Q* R depends x, and P satisfies the following properties region ||]| 0c < C} x Z for some constant C 0:
{Q gex
8

---

Algorithm 2 Optimistic Mirror Descent with Regularization for Multiple Distributions
Input: {0]] ] {9.] ;--1 {(1/us,... 1/mx), (1/m,... ,1/m))) (ar 2 03Σ with Σ 04
(% 2 0) (), 2 0){=,, and Q =0.
Output: 2r = - a1z".
I: while < do
2:
Q' = =1 (1- 8 Q
11 + P(Q" =)-
3:
for all i E [1 dJ do
4:
x: = argmin 7 P (Q -1 - x.) + KK (a: (1)")"²)))) + (xx)))) =,Ea;
y. = argmin 7 (Q'
), v.) + k, (y. [1)))) + Aev(y)))
M,
6:
(g.) = argmin 7 (Q =)) kKL (g [(=")=11 + >vv(gT)
ex;
7:
(g.)² = argmin 7 (Q' =)),0²) + (o. |,,))= + >xv(g"))
of
8: end for
9: t- + 1.
10:
end while
[A]] There exist constants I,, T,2 2 0 such that F. zi) is uniformly I, Lipships continuous with respect to -1>s0 under || l| oc: and F; (Q, is uniformly T--Lipschitz continuous with respect to
|l under ||- ||1.
[Aa] There are positive constant y > and set of non-negative constant matrices [B,, C. satisfying E (B. + C.)llo I 7 such that Dpro x') I Eis CF(F7(QQF) 21), z; xi{) and Dp(q.,,) 3') 2 E B,(F 21), V6 y.)-
[As] There exists 0 E [0, 1) such that P(., 2) is a 0-contraction mapping under [P(Q. 2)) < C for any Z.
lloo, and
We present Lemma 4.3 to demonstrate that there exist Q* E Bexd x² X and y' E y satisfy the saddle point and fixed point conditions of function P. i.e. Eq. (1). under proper assumptions.
Lemma 4.3. Assuming that Assumption 4.2 holds, [P(Q.)) (..))kk,, j is continuous, convex with respect to x, concave with respect to for any (k, and mink.j.t then there exist Q* E R and x² E Z such that
min [ C.)e... 2 C' for some C' > 0,
(C.).. [Bila.
P(Q', x. ,y),, Q- < P(Q" x, y"), and Q" 2 P(Q""x"", x),
(1I)
For Algorithm we let Br, 3e II j=t+1 (1 - 33)) for any T 2 and BT. Br, and set parameters
= 2(1 - -) n 16T2((7/L))1/2 + Br c+i an Bryy 2
(1-8)1/2
Qt-1 d -/c-
(12)
ai
Then we have the following convergence result by denoting M maxie(l.d] {m, + nz).
Theorem 4.4. For any generalized quasar-convex-comcayy functioo f which satisfies Assumption 4.2
with P = Q", where Q" satisfies Eq. (TT). Algorithm 2s oulput žT = (ØT, Dr) satisfies
(2 log(M) + n + IL T 17
Gy(ār, Fr) < 60 max
Σ (a(x) (1 (1-8) (1-8)-1
#62
6 where Y7 = 8(c+ = log( (M) + 160 + +00 (oc)) T) 1).
Similar to minimization Algorithm ! the iteration complexity of minimax Algorithm linearly depends on the upper bound of > v); over Z. Generally, the upper bound of >d 3/2 on Z is related to d. In specific problems of multi-variable optimization (such as two-player zero-sum
Markov games), can uniformly bound Ed v/s on Z by constant.

---

4.3 Application to Infinite Horizon Two-Player Zero-Sum Markov Games
In this section, we show how to leverage Algorithm achieve accelerated rates for optimizing infinite horizon two-player zero-sum Markov games. Our algorithm use O( iteration bound to find an e-approximate Nash equilibrium of infinite horizon two-player zero-sum Markov games.
As similar the definition of discounted MDP in Preliminary, utilize . AS, 0, Po) 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 x A B with values in [0. 1]. and the transition model ( s', a', ,',b') denotes the probability of transitioning into state upon player 1 taking action a' and player taking action b' in state s'. We can define the value function V and action-value
function Q on the joint distribution & = (x, y) 2 = I1 A x II Ag. The infinite horizon two-player zero-sum Markov games consider the following policy optimization problem:
min max J JP.)) #EX yEy
(13)
where (po) = Bso~p, (8n)] The following proposition indicates that J is general quasar convex-concave, and satisfies Assumption 4.2 and the condition of Theorem 4.4
Proposition 4.5. For any Q (Q), ..,, +(s) with every Qi TR|AAX define function
f((Q. == x! Q,y; for any [1 [S)). There exists a tensor-valued function P such that (P,) satisfies GQCC condition with f.(((z).z) = fi(Q", zi) for any Po E As. where Q*
satisfies the conditions mentioned in Eq. (II) Moreover. P satisfies Assumption 4.2
if we apply Algorithm 2 to the infinite horizon two-player Markov games basing internal operator (Q, ( (Q,) for block z; 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 E e-approximate Nash equilibrium is upper- bounded by (((1- 0) 2.5g 1) To the best of our knowledge, our iteration bound matches state-of- -|S|== bound of Cen et al. 10 Since the upper bound of E v\2 over feasible region 2 in infinite horizon two-player
According to Proposition 4.5 and Theorem
the-art iteration bound and a factor of (1 6) 1)-1-5 [ [S] better than Ō((1 6)
zero-sum Markov games' setting satisfies | (=) s Σ Di=1 d=.
(a) (ss) + de (2).v (s:)] $ po
for any 2, our algorithm's 's iteration bound does not depend on the size of states.
5 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.
Acknowledgements
C. Fang was supported by National Key R&D Program of China 20022DD0114009 and the NSF China (20.62376008). L. Luo was supported by National Natural Science Foundation of China (No. 62206058). Shanghai Sailing Program (22YF1402900) Shanghai Basic Research Program (23IC1401000), and the Major Key Project of PCL under Grant PCI.2024A06.
References
[1] Jacob D. Aberneth,, Peter L. Bartlett, and Elad Hazan. Blackwell approachability and no-regret learning are equivalent. arXiv preprint 1011.10001.990 2010.
[2] Alekh Agarwal, Sham M. Kakade, Jason D. Lec, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 2021.
[3] Ahmet Alacaoglu, Luca Viano, Niao He, and Volkan Cevher. A natural actor-critic framework for zero-sum Markoy games. In International Conference on Machine Learning. PMLR, 2022.
10

---

[4] David Blackwell. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics, 1956.
[5] Charles E. Blair. Problem complexity and method efficiency in optimization (a. s. nemirovsky and d. b. yudin). Siam Review, 1985.
[6] Stephen P. Boyd and Lieven Vandenberghe. Convex optimization. Journal of the American Statistical Association, 2005.
[7] Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points I. Mathematical Programming, 2017.
[8] Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points II: first-order methods. Mathematical Programming, 2017.
[9] Shicong Cen, Yuting Wei, and Yuejie Chi. Fast policy extragradient methods for competitive games with entropy regularization. Advances in Neural Information Processing Systems, 2021.
[10] Shicong Cen, Yuejie Chi, Simon Shaolei Du, and Lin Xiao. Faster last-iterate convergence of policy optimization zero-sum markov games. International Conference on Learning Representations, 2023.
[11] Lesi Chen, Boyuan Yao, and Luo Luo. Faster stochastic algorithms for minimax optimization under Polyak Lojasiewicz condition. Advances in Neural Information Processing Systems, 2022.
[12] Ziyi Chen, Shaocong Ma, and Yi Zhou. Sample efficient stochastic policy extragradient algorithm for zero-sum markov game. 2021.
[13] Ching-An Cheng, Remi Tachet des Combes, Byron Boots, and Geoff Gordon. A reduction from reinforcement learning to no-regret online learning. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, 2020.
[14) Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. Conference on Learning Theory, 2012.
[15] Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 2021.
[16] Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021.
[17] Jelena Diakonikolas, Constantinos Daskalakis, and Michael Jordan. Efficient methods for structured
min-max optimization. Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, 2021.
[18] Jerzy A. Filar and Boleslaw Tolwinski. On the algorithm of Pollatschek and Avi-ltzhak. 1991.
[19] Anders Forsgren, Philip E. Gill, and Margaret H. Wright. Interior methods for nonlinear optimization. SIAM Rev., 2002.
[20] Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized markov decision processes. International Conference on Machine Learning, 2019.
[21] Benjamin Grimmer, Haihao Lu, Pratik Worah, and Vahab Mirrokni. The landscape of the proximal point method for nonconvex-nonconee minimax optimization. Mathematical Progranming, 2023.
[22] Moritz Hardt, Tengyu Ma, and Benjamin Recht. Gradient descent learns linear dynamical systems. The Journal of Machine Learning Research, 2018.
[23] Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilib- rium. Econometrica, 2000.

---

[24] Oliver Hinder, Aaron Sidford, and Nimit Sohoni. Near-optimal methods for minimizing star-convex functions and beyond. Conference on learning theory, 2020.
[25] Jean-Baptiste Hiriart- Hiriart-Uruuty and Claude Lemaréchal. Convex analysis and minimization algorithms. 1993.
[26] Alan J. Hoffman and Richard M. Karp. On nonterminating stochastic games. Management Science, 1966.
[27] Feihu Huang, Xidong Wu, and Heng Huang. Efficient mirror descent ascent methods for nonsmooth minimax problems. Advances in Neural Information Processing Systems, 2021.
[28] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 2018.
[29] Anatoli B. Juditsky, Philippe Rigollet, and Tsybakov. Learning by mirror averaging. Annals of Statistics, 2005.
[30] Sham M. Kakade and John Langford. Approximately optimal approximate reinforcement learning. International Conference on Machine Learning, 2002.
[31] Alexander Kaplan and Rainer Tichatschke. Proximal point methods and nonconvex optimization. Journal of Global Optimization, 1998.
[32] Robert D. Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does SGD escape local minima? International Conference on Machine Learning. 2018.
[33] GM Korpetevich, Extragradient method for finding saddle points and other problems. Matekon, 1977.
[34] Guanghui Lan. First-order and Stochastic Optimization Methods for Machine Learning. Springer Cham, 2020.
[35] Guanghui Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical Programming, 2022.
[36] Sucheol Lee and Donghwan Kim. Fast extra gradient methods for smooth structured nonconvex- nonconcave minimax problems. Advances in Neural Information Processing Systems, 2021.
[37] E.S. Levitin and Boris Polyak. Constrained minimization methods. USSR Computational Mathematics and Mathematical Physics, 1966.
[38] Jiajin Li, Linglingzhi Zhu, and Anthony Man-Cho So. Nonsmooth composite nonconvex- concave minimax optimization. arXiv preprint arXiv:2209. 10825, 2022.
[39] Tianyi Lin, Chi Jin, and Michael I. Jordan. On gradient descent ascent for nonconvex-concave minimax problems. International Conference on Machine Learning, 2020.
[40] Tianyi Lin, Chi Jin, and Michael I. Jordan. Near-optimal algorithms for minimax optimization. Proceedings of Thirty Third Conference on Learning Theory, 2020.
[41] Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. 30th Annual Symposium on Foundations of Computer Science, 1989.
[42] Michael Littman. Markov games as framework for multi-agent reinforcement learning. International Conference on Machine Learning, 1994.
[43] Arkadi Nemirovski. Prox-method with rate of convergence O(1/t) for variational inequali- ties with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 2004.
[44] Yurii Nesterov. A method of solving convex programming problem with convergence rate O (k- (k=))). In Doklady Akademii Nauk. Russian Academy of Sciences, 1983.
[45] Yurii Nesterov. Dual extrapolation and applications to solving variational inequalities and related problems. Mathematical Programming, 2007.
12

---

[46] Yurii Nesterov. Introductory lectures on convex optimization basic course. In Applied Optimization, 2014.
[47] Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and global performance. Mathematical Programming, 2006.
[48] Yurii Nesterov and Laura Rosa Maria Scrimali. Solving strongly monotone variational and quasi-variational inequalities. Econometrics eJournal 2006.
[49] Jorge Nocedal and Stephen J. Wright. Numerical optimization. In Fundamental Statistical Inference, 2018
[50] Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving class of non-convex min-max games using iterative first order methods. In H. Wallach, H. Larochelle. A. Beygelzimer, d'Alché-Bue Buch E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems. Curran Associates, Inc., 2019.
[51] Erich Novak. Deterministic and stochastic error bounds in numerical analysis. 1988.
[52] Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Mathematical Programming, 2018.
[53] Sam Patterson and Yee Whye Teh. Stochastic gradient riemannian langevin dynamics on the probability simplex. In Neural Information Processing Systems, 2013.
[54] Moshe Asher Pollatschek and Benjamin Avi-ltzhak. Algorithms for stochastic games with geometrical interpretation. Management Science, 1969.
[55] Leonid Denisovich Popov. A modification of the arrow-hurwicz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 1980.
[56] Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. arXiv preprint arXiv: 1208.7728 2012.
[57] Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems, 2013.
[58] Julia Jean Robinson. An iterative method of solving game. Classics in Game Theory, 1951.
[59] R. Tyrrell Rockafellar. Convex analysis: (pms-28). 1970.
[60] R. Tyrrell Rockafellar, Roger J.-B. Wets, and Maria Wets. Variational analysis. In Grundlehren der mathematischen Wissenschaften, 1998.
[61] Lloyd S. Shapley. Stochastic games Proceedings of the National Academy of Sciences, 1953.
[62] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances in neural information processing systems, 1999.
[63] Paul Tseng, On linear convergence of iterative methods for the variational inequality problem. Journal of Computational and Applied Mathematics, 1995.
[64] Jan van der Wal. Discounted markov games: Generalized policy iteration method. Journal of Optimization Theory and Applications, 1978.
[65] Gal Vardi, Gilad Yehudai, and Ohad Shamir. Learning a single neuron with bias using gradient descent. ArXiv, 2021.
[66] Yuanhao Wang and Jian Li. Improved algorithms for convex-concawe minimax optimization. Advances in Neural Information Processing Systems, 2020.
[67] Chen- Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in hnriine-horizon competitive markov games. In Annual Conference Computational Learning Theory, 2021.
13

---

[68] Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance-reduced optimiza- tion for class of nonconvex-nonconeee nonconeave minimax problems. arXiv preprint arXiv:2002.00622 09621, 2020.
[69] Junchi Yang, Antonio Orvieto, Aurelien Lucchi, and Niao He. Faster single-loop algorithms for minimax optimization without strong concavity. In International Conference on Artificial Intelligence and Statistics, 2022.
[70] Yuepeng Yang and Cong Ma. OT convergence of hewp:iiiee..oooooooeeeegglaaaiia in two-player zero-sum markov games. arXiv preprint 2rX9v:2209.122 2022.
[71] TacHo Yoon and Emest K Ryu. Accelerated algorithms for smooth connxve minimax problems with (11/2² rate on squared gradient norm. International Conference on Machine Learning, 2021.
[72] Sihan Zeng, Thinh T. Doan, and Justin Romberg. Regularized gradient descent ascent for two-player zero-sum Markov games. Advances in Neural Information Processing Systems, 2022.
[73] Jiawei Zhang, Peijun Xiao, Ruoyu Sun, and Zhi-Quan Luo. A single-loop smoothed gradient descent-ascent algorithm for conconvex-concan min-max problems. Advances in Neural Information Processing Systems, 2020.
[74] Yulai Zhao, Yuandong Tian, Jason D. Lee, and Simon Shaolei Du. Provably efficient policy optimization for two-player zero-sum markov games. In International Conference on Artificial Intelligence and Statistics, 2021.
[75] Yulai Zhao, Yuandong Tian, Jason Lee, and Simon Du Provably efficient policy optimization for two-player zero-sum markov games. In International Conference Artificial Intelligence and Statistics. PMIR, 2022.
[76] Yi Zhou, Junjie Yang, Huishuai Zhang, Yingbin Liang, and Vahid Tarokh. SGD converges to global minimum in deep learning via star-convex path. arXiv preprint 1rX1v:1901.00451, 2019.
14

---

Contents
Introduction
1.1
Contribution
Related Works
2
Preliminary
3
Minimization Optimization
3.1
Generalized Quasar-Convery (GQC)
3.2
Main Results
3.3
Application to Reinlorcement Learning
Minimax Optimization
4.1
Generalized Quasar- Coneea (GQCC) (GQCC)
4.2
Main Results
8
4.3
Application Infinite Horizon Two-Player Zero-Sum Markov Games
10
5
Conclusion
10
Acknowledgements
10
Preliminary
16
A.I Supplemental Notation
16
A.2 Finite Differences
16
Finite Horizon Markov Decision Process
16
Minimization Optimization
17
Proof of Theorem 3.5
19
B.I.1 Part
19
B.1.2 Part
21
B.1.3 The Last Step
24
B.2
Simple Example
24
B.3
Application to Reinforcement Learning
25
B.3.1
Analysis of Infinite Horizon Reinforcement Learning
................................
25
B.3.2
Analysis of Finite Horizon Reinforcement Learning
26
Minimax Optimization
26
Preparatory Discussion
26
Theorem C.7 and Relate Proof
29
Part
30
C.2.2
Part II: Estimation of Approximation Error Q Q"
32
C.2.3
The Last Step
35
15

---

C.3
Application to Minimax Problems
36
C.3.1
Infinite Horizon Two-Player Zero-Sum Markov Games
36
Convex-Concave Minimax Problems
37
D Auxiliary Lemma
37
L Limitation
41
A
Preliminary
A.1 Supplemental Notation
For simplicity, we denote g(T) = Ek=1 -- + (k: + 1) e2p())]] the chi-squared divergence between p, q (pllg) Σド= (p(i)-
q()) Ex(x) P(ja(( and Varp(*)
R". For Ç 0. n E Z+. we say that sequence of distributions p² ... ,p" E An is (-consecutively close if for each 1 1 T. it holds that max
Σj=1 p()) (x(j) (x))
2 for any p.q An and
<1+6 Ç. For positive scalar E [0, 1), non-negative integers p
P
and T, define B4 Be
(1 8j 03,), and B4. 1.
A.2 Finite Differences
Definition A.1 (Finite Differences). For sequence of vectors L (L"..... ,L') where each L' E R and integers h Z.,, the order-h finite difference sequence for the sequence L is denoted by DnL = ((D,)),, (D recursively with (DoL)* := L' for all t [0 T). and
(DaL)' = (Da-1 - -DDp-L))
(14)
for all 2 1 and t E [1: : h].
As stated in 15 Remark 4.3], we have
(DaL)* =
(-1)
(15)
==0
To guarantee the coherence of the analysis's structure, we introduce the definition of the shift operator E, as follows:
Definition A.2 (Shift Operator). For sequence vectors (L".... .L') where each L' E R". and integers Z.,, the s-shift sequence for the sequence L denoted by F., == (),,L)),,.. (E, L)Thb) with L), = ++ for E [ -
A.3 Finite Horizon Markov Decision Process
We also consider the following finite horizon Markov decision process (MDP), denoted by M (H, Si.H. AI. H2. a, Pi). H E 24 denotes the number of horizon; S (Si, SH) ) is sequence of H finite state spaces; AI: (Ai,... ,Arr) is sequence of H finite action spaces; PA (sn 18,,,, (h-1) denotes the probability of transitioning from 8h-1 to under playing action
ah-1 at horizon h 1: SI.H X A [0, 1]is cost function; P1 is initial state distribution over ST.
AA denotes stochastie policy. Similarly, Pr T = s'|ss = s) to denote the probability of visiting the state s' (8h, ) A=1. where 81 ~ Pı. and, for subsequent horizon h, an ny (-18%) and 8h-1 ~ Ph++1 (-1sn, an). The value function Vi Sh + R is defined as the sum of future cost starting at state sy and executing
(TI TH) S.H + AA, use Pr P from the state at horizon h according policy 11:-11 Let trajectory
16

---

Algorithm 3 Optimistic Mirior Descent for Multi-Variables
Input: {9) = ) _ 1= 7 and T. Output: Randomly pick up & E (1, ,T following the probability P[ 1/T and return x'.
1: while ~ T do
2: for all E [1 d] do
3: o argmin 17 (FF(w .i)) + (xt.g;-)) m;eX;
4: 9 argmin (F; ..)) + V (g.gg-1) 9,Ea;
5:
end for
6: <- +++
7:
end while
h: (Th. TH), i...
;
Vh V.TiH (5h) E σ (sw, and
Th:H4 Sh
For convenience, we define (s1( Vi (s1). Moreover, we define the action-value function
T Sp. x An - [0, 1 H - h] follows:
Qh (8h, a an) +
Σ h-=h-1
oss, ax) Tht1:H, 8h, Ch
B Minimization Optimization
We begin with general version of Theorem 3.2
basing Algorithm iin this part.
Theorem B.1. [General Version of Theorem 3.2
We consider the divergence perrggennceggeeratinng function
v with Bregman's 's divergence V(x, u,)
v(u;) - (Vv(u,), x; - u,) for any block X;
and any æi u, X4. Assuming that F is L-piscchitz continuous with respect to -|- under ||
V Vxx, u;) 2 ||0; uill² for any Di, u. E X; and Tmaox max < oc, we have
2L (d7mmx) 1/2 1/2
(EL 75
3/2
(f(x') f((x'))
max max V(z.,
(16)
T
sE[1:]] m.EX:
with setting n dLad Eim 1/22222
Proof. According to GQC condition (Definition 3.1
we have the following estimation
T
-((('))f(x>)
<
F Fz(x))), x;))
(17)
For any fixed i E d]. we obtain that
(F.(x'), xt x;) F(('')) Fi x 9 (Fi(x' 11, x g
(F 9 x
(18)
Since F is L-Lipschitz continuous with respect to || ||. under || I by using Cauchy-Schwarz Schwarz inequality
||. we have following estimation of
1.2m 2
I <
||
xx
-112
|| gfll²
(19)
2n
17

---

In addition, utilizing the result of [Lemma 3.4, [4]] on s and step-4 of Algorithm
we have
II
- V (g ") V (gf. x!) V (x);,
(20)
"
III - [V (a) " 1) V (कf gf) V (
(21)
7/
Therefore, by applying Eq.
(19). 20 and (1) into Eq. (18) we obtain
Σ (F,(a)), xx)) S Vaa)
a.0t..0 9 +
T
L
n
| x
111
1 + 2n
|
9ill?
7)
t=1
V Vggi x
1
Σ
V
(af% gi 1
"
t=1
L2n
T
V(at 9.) +
Σ
||
xt-
7
2
1 T
T
2
|
9 11
21
2n
- Vat
1
(9
+
1
11
+
L T
Σ
|| - x 112
())
21
2
t=1
1
0 x 11
(22)
4x
where (a) is derived from the assumption that V( u.) 2 |.z u for any 2,, u, E X4 and (b)
follows from the convexity of || |l. Applying Eq. (22) to Eq. [7].
we have
T
V( )
I,2n1
d
E(((a') (oee)-f(aa) -(x)))
x
x'-11
%
T
d
| ar! "11
4n
7/
V( 9
ma8 [E(1
max R.EA:
11
1,211
d
x
x x11
(23)
2
1=1
where (c) is derived from the fact that gi = x! for any E [1 d] and (d) follows from the convexity
of || ( Σ
[<> |
1 Σー -- 13)
Since KL. divergence satisfies KT. (|;;;) 2 |m: 1i (Pinsker's inequality). Theorem 3.2 can be directly derived from Theorem B.I Next, we propose Proposition an2 provide related proof.
Proposition B.2. We denote N Di n, and let a smooth vector-valued functioooluddunncionn F RR R satisfies:
1. There is a point y E RN such that F(y)lle S Sn with |a] = k for all ls E 10: K],
2. For any positive integer k greater than K, | S 5 with |a| = k uniformly over X. with positive constant and a positive integer K, then F satisfies Assumption 3.3
Proof of Proposition
B.2 For any is E Z4 and j E [1 : 1), we have
(|æ) + 1b)) Ixdd + [|)] <exp(>(d + [1)l1)), (24)
P
a!
2=0
18

---

using the fact that || F( I 7tth for any k 2+ and |a] = k. In addition, by the Taylor expansion of Fj) with Lagrange remainder formula for any j E [1 and k > 1, we can obtain
D F + 1(x y) (x y)
(7 11
R (x)
Σ la|=k
(25)
ad
k!
where t E [0, 1] depends on FG), and y. Letting Ko
[3y(d + ||alh) and supposing 2
kn 1 + (dd 1ll))) (3/23
we derive that
htdd
1)
3
(26)
kd
Therefore, in the light of Eq. (24). Assumption 3.3 with Ko = ko (+ [|
Eq. 25
and Eq.
26
it's direct to derive that F statisfies
3 θ = 3 and O = expl
lng(3/2)
The following remark discusses the reasonability of Proposition B.2 conditions, which supports the reasonability of Assumption 33.3
Remark B.3. Since region X'
An. is bounded, it's reasonable assume that the growth rate of the upper bound of internal function's 's high-order derivatives is not faster than linear growth rate. For example, the upper bounds of high-order derivatives of sin(Ca:), cos and exp(Ca) have linear growth rate over X' for fixed constant C. Therefore, if the internal function F can be generated by the linear combination of ) and (cos(Caa) Cx=)) (or {cxp(Cx=r) K with finite K, F satisfies Assumption 3.3 by using Proposition B.2
B.1 Proof of Theorem 3,5
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 con- struct a variant upper bound of average function error 1 ET (J(x') f(x")) that is differ- ent from the upper bound derived from the classical OMD algorithm. This bound com- posed of O
nT invariant error and weighted sum of the variance for finite difference sequence {(D, (x (>T and (( " over i [1 d], which has the form of 1 O11) -=1 Var,; (1x o(1) E Var.: (F.(x=-1))], The second is applying Lemma D.7 (refer it as control lemma) on each (F,("") to bound (b) by a quantity that grows loly-logari in T. Therefore, it's necessary to leverage Theorem B.5 and Lemma B.7 to show that every sequence { (F; (xx")) outputted by Algorithm satisfies the preconditions of Lemma
>d
-i=1
T
D.7
B.1.1
Part I
The next Lemma B.4 provides 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 of Et (f(x') f(x")).
Lemma B.4. Suppose F())ll O ( for any X and policy set (x* (t)))= the iteration of Algorithm 7
with step size 1) (0, )t) Then, it holds that
T
log(ne)
T
Σ (f(x') f((x)))
<
+ ộ1 (n0)m0²
Var (F,(z!) - Fx(x(-1))
%
17
Var (F; (2(t-111))
(27)
where (n) = + +44 (5I1-167) + 2) y and (2((1) = 1/2
3(1 3(1-167) + 2)
19

---

Proof. As claimed by Definition 3.1 we have the following estimation
T
d
T
E((a') - f(x))) -
(x)) x. x;)
(28)
1=1
In the following, considering fixed i E [1 d], it's easy to obtain that
(F:(x'). at 2;)) (Fx'')) F (((x"")) at 9 (Fi( x gi)
II
FF (x")) ).9. x.)
(29)
III
Recall the update of Algorithm
1 can be devided into two parts:
g arg min 1) 1 (FF.()))..)) + (l
(30)
9. e.E.n
o arg min 1j (F.(2")), m.) (L<
(31)
2. E.E
for any E [1 d] where g x of exp( - (xx and x; 11 x (1,
(1)
T
n.
According to Mauchy-Schward inequality, we can evaluate I follows
I I | x l|a / Vara;
Fi(x(-1)).
(32)
In addition, utilizing the result of Lemma D.2 we have
II KL (g11l
KL (g/l(=)) KL (z l9g ')]
(33)
III
KT. (ar | ) KT. (a: (1g)) KT. (gillg 1)
(34)
Therefore, by applying Eq. 32 33 and 34 into Eq. 29 we obtain
Σ (F.(")) 10--a) axt) < KL (at (1 + lo 1
Varag (Fi(a!) F; (xrt-1)
"
kL(g)((
Σ KL(W|ll9 1)
(35)
Since there vector F, F((x')
Fx such that for any j [1 n:]
x (j) exp -(())
g
(36)
Σ Th
-ドー (j') exp -3"")""(
we have that
g
expp(2n F((x')) (a(a''>)) exp(4n0) $ 1 8n0,
(37)
#E[1:]
x
and
x exp(22)) F F.( S exp(21 < 4n0,
max #E]1:d]
g.
with combining Eq. have
31 and choosing proper y such that r70 < 1. According to Lemma D.3 we
1 (1-
16n0
kL(gi||=f) 2
X²(g xx),
2
3(1 - 3(1-817)
(38)
1
4n
870
KL(x
>
x² ( -1),
2
3(1 - 41)0)
20

---

(ll- ull;))
for any i E [1 dj. Noting that X2 (p,
in the light of Lemma D.4 we derive that
(g). x)) 1
1 + 32
+2 n/ (nr)) (F,(z') F)
3(1 16n
(39)
X2 xi)
1 32
+ 2 n/
(nn)) (F,(x") F F((x'=1))
3(1
16n
long as n/
There exists similar lower bound with respect x²2 (at 1
32
1
x² (2/ gi
2
16
+2
1/0 (19) af (F,(x'=11
3(1 - 81)()
1
IV
16
+ n/0 (())) expl - Yarm: (F (xx
3(1 - 8n)0)
1
EIV
16
3(1 - (9 + 3 170 (nt)) (x)
(40)
where (a) is derived from expl -1/0 2 1 - 4n/0 for any 7/0 s मेz Relying on Eq. conclude that
(35). Eq.
38
40
F((x)), -x;)
log(n:)
+
1 1++3 32
1
+2 n/0
n0²
Σ 1=1
T
Vargt (F,(z") - FF((==1))
71
3(1 16n0)
11
1
32
36
n/
1/0
Var,; (F:(x') (F,t'-=F((''- F,(
3(1
16n/0)
1
16
T
2
+ 27
n/
n7?
Var (F((x111))
3(1
8n)))
t=1
lns)
+
+ 64
1
+2 n10)
17022
Σ
T
Var (Fi(x") - F((x'=1))
7
2
3(1 - 1670)
1=1
1
1
16
+2
n/
m/
Var (F((x'=1))
(41)
2
3(1
16//0)
Finally, applying the estimation Eq. to Eq. (88 we complete the proof.
B.1.2 Part II
Basing the conclusion of Lemma B.4 if the finite sum of Varg; (F.(x') F, F,(x'=1) can be controlled by the finite sum Var,; (Fi(x' 11) with a ((poly(log(T))
constant for each i E [I d]. the final convergence result can be obtained directly. Hence, demonstrate this relationship, we require the assistance of auxiliary Lemma Our initial step is to prove that F,(x") satisfies the first condition Lemma D.7 for any E [1:d..
Theorem B.5. Assuming satisfies GQC condition and Assumption 3.3 holds, x² follows the iteration of Algorithm
1 we set B (0, +e. ). r 2 e² + 3225600 K 2 max Ko,
Hlog(40 3 [+)) log(! 1)
Then, the following finite difference bound with and = (eaKTmax(e.1))
3
respect to (F,( holds
max vE[1:d]
[(D S 3h+
(42)
for all E [1 : H] and to E [0 T 1). exceed T.
Without loss of generality, we require that H does not
21

---

Proof of Theorem B.3 notice that
According to the Taylor expansion of each component & of F; at y, one can
(D&Fi(+)())*)
D F(),(()()))
|(D - y) ( R (x)) ( R.
(43)
ad
j=0 ja|jj
for any Ke E Z4. Therefore, setting K 2
max Hog((1 Hoog(1g-)) ()+g)(()1)) log(0-1)
Ko and combining the remark we can guarantee the validity of the following estimation
Eq. (1) of operator Dr in Appendix A.2
(DaRR
F.lk) R.y
(x))
to
S 2
max =xX
R (k()) (x)
I 0,2"
1 r
3 h B
(44)
R
for any h E [1 H. Moreover, as stated by Assumption 3.3 we obtain max xE[I:d]
| S01= - 22
for any X. Suppose that max :E[I:d]
(((:))(( 1l S 3hd BBN'+1 holds for any 1' E [1 hi and
to E [0: T h'), we deduce
(g( 1) B( pF (2²0) + / ght +) 1)B(++)++1
Ryy
(45)
+ gh+ + 1) B(++1++11 S gh+ (h 1) 11(
1 (which can be derived from Lemma D.I Therefore, to apply mathematical induction, suffices to Observe that Lemma
by using Lemma B.6 with p(x) = 100 ((((())) (a y) and the fact that (T) S 2
prove that max F(, (x)))) Ilo0 S 3h 1BB++1 holds when h'
*E[1-d] B.6 holds in the case h = 0. Thus, we can obtain Eq. 455 for h 0 well. Hence, have max ( B. <E[I:d]
The proof of Theorem B.5 relies the next Lemma B.6
Lemma B.6. Assume max [x))l S θ for any x X and each element in un belongs to <E(l:d]
one of the d probability distributions generated by Algorithm Witt 17 S 6 1a for some
8
>>> 1,K N K in iteration t, and consider positive constants B 2 3, B E (0, [++1] and polynomial function p(u)= == CH (u(k) - ykk) where u = (u(1), ... u(K) and
y = (v(1), ... .y(K))] E RKK is a fixed point. Given h E [1: H - 1]. we derive that
K
((D+ip(u)) S ((T)
(u + (k)))) (h 1) B(++1)+1
(46)
k=1
if the condition max <E(L:d]
[1 (x)) lloc S 3h n holds for any h'' E [1 : h) and to E [0
- h²].
Proof. Drawing the premises outlined in the lemma, we assume that each u(k) corresponds to unique x (1) (jk))). According to the iteration of Algorithm D can obtain
u (K) Tlue (i(k)) exp {n- (2F (A))) (x*) F Fi(K) (k()) (x 1)}
Eje 1i(s)) (i) exp (n (2F (i) (xt) (i) (x'
u' (lc) exp {n. (2F (2) (ik))) (x¹) - F (ik))(((k))))))))))))))))))))) (x (x)
(47)
(1(0)) (/()) (j) exp (n- (2F s(a)) (J) (a*) F F(( (J) (x* Σj
for any &: E [1: K] and / [1 : T - 1). Given the sequence wt.... toth generated by Algorithm
I it is straightforward to derive that
u (o+++((k) = (N#)) - -' (I)) exp(n (F (()
F Figo (())
+
-==
(48)
22

---

for any k E [1 K], to E [ - h- 1] and E [1: h], where No = = =EE= x ((kk) (5) exp(n
(F (F10))))((ztot1) + Er=o F ((x) (z) - F (1))(()(x001)) })}} We write
to F i(k) (x
F (()) (x)) - Fi(a) (2
(49)
Also, for vector (2 and an index j e [1 m.())) define
exp(z(i))
V (2)
(50)
-x T1oo ((K) (f') exp (z(i')}
so that ( = x 2(1 (i(t)
look (Tri (o.k) = ( veak (Tri for t 2 1. For conve-
nience, we denote that D = fa E NK ((())(1)= E (0,1), [1: KJ} and e = (1, 11) E N In particular, for any D, we have
( (ua 10 (u
(Dhr (1
(51)
I(ach(,fo)
where ti (wri.)
( (pri...)....
(00 Pt (ori..))) .. h' [L h+ 1] and to E [ h 1].
It is important to observe that the finite difference in Eq. (5T) pertains specifically to (k( (or) Notice that
(Dirto,s)* 2(E, F ((ck) (2)) for any & [0: :l. Therefore, for any h' E [1: h+ + 1], we obtain (Dartta.)) = (Fa Dr
Fa(k) (o
(52)
(F (())) (x=))
tott-1 ) (Dw- (F (R) (z))) 10tt-1
(53)
Donrr '01
for any t E [0: h + - W/. Because the step size 7, satisfies 17 S 6 max
nHO S 6G and max aE[1:]]
(Dxx I gh 1Bb++ for all N' E [1 : h), the following
estimation holds
(DN+)7r:))) S 2 2h+1(('' + 1) B(((1)))
(54)
for any h [0: h by using Eq. (33 where ri. = ( (i(1),, x (K())) By Lemma D.5 and Lemma D.6. we have
I(a, h + 1,1o) S g(T))gh+1() (h 1) 1(++1))++
(55)
Noting that
K
p(u) = C
Σ
1-1)
Σ
you
(56)
1=0
aED: a|=
and applying bound Eq.
55
to Eq.
50
derive
K
h+1
(Da+1p(u))
C
Σ
1))
Σ
++11
) (-1) (wtothi
W
k=0
aED:aa
=i
#=1
K
<|
(Dh+1 (ua-ai)
1=0 DE al=i
K
<|0|
1))
0 aED: al=i
K (u to (k) + (k))))
<g(T)ggh+1() 11 11)
II
(57)
k=1
for any to E [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 (Dif(z))) w.r.t function f respectively. D
23

---

Recalling that we set parameters as follows
1
T T2 4, H = (ooo(oT)))))) 8 8(0, O2 1)H7/2
== e² 32256002,
(58)
H 1og(433 + log((1)
B
max
Ko
, ,1= Ge KT
B 2 3,
log((-1)
According to Theorem B.5
we have max iE[L:d]
(Dx
< 3hh H3h+1 for each It E [0: H] and
E [ T1:T-hhy lb.. We are now prepared to prove that æt satisfies the second condition of Lemma D.7
-
Lemma B.7. The sequence {ar which has been generated from Algorithm i (n(( θ2)
consecutively close when H 2 1. 5p (4H) and E (0, + 6 + 1) /57792].
Proof. According to the iteration of Algorithm we have
F(()(aa)))) (k) - xf(k') exp(1 (2F. 2F; 2k:(k') (x')
(k) exp
(59)
for any i E [1 df and K E [1 : n... Therefore, for any i E [] df and t E [] T - 1/. we obtain
x
} s exp(6n((0) θ2)) (1 (n O2)),
(60)
where (a) is derived from the fact that exp(x) < 1 + o for x E 10,1/24].
B.1.3 The Last Step
With the preparatory work for proving Theorem 3.5 is completed, now turn providing the final proof:
Proof of Theorem 3.3
Applying Theorem B.5 and Lemma B.7 to Lemma D.7 we have
Vara; (F, F.(x''1) s 230
Var,; (Fi(x' + 1651200 (1+ + 7T +
(61)
According to the result of Lemma B.4
we obtain
log(n;)
T
((((a)) - (xx)))
-2 (10))0))))) (0z(10)))0² 230
Σ
Var (F,(a!))
7/
t=1
d
فn (n ?
2
+ 1651200 777) 2].
(62)
Combining Assumptions 3.3 and parameters selection Eq.
we complete the proof.
B.2 Simple Example
In this section, we provide the proof of Example 3.44 which satisfies GQC condition and Assumption
Proof of Example 3.4 Recalling the objective function f(p, P) Em En (2 TP.) -y)
we have
f(p".P) f(p, (F, -p)
(63)
24

---

since f(.PP) is convex for any fixed P. In addition, we obtain
1 E 10o PP)) - -o(x (()))
f(p pP)) f(p',f(p_ P)
2
( BC
2
E [<o Pi)- -
Pi), x (PI Pi-PP))
Bc E [(o( (P Pÿ) y),, Pi Pi],
(64)
2
where Be is a constant depends on C' and (a) is derived from the fact that Be (exp(z1) exp(x2) J. F1 x22
2 exp(x1) 222 for any 21, 22 E []C,C). Therefore, summing
up Eq. 63) and Eq. (64). we have that f satisfies GQC condition with the internal functions
F
[E j=1 ojo o x P2) v))o p.) for block p and Fp. = [( P.) - y)
for block P,. Notice that "pp 1, P, Be and PP O for any o 1. Furthermore,
have || F-))l>
(exp(C)(2C))a) and F), I exp(C)Clalt) by using and [-C, C7 According to Proposition B.2 we complete the proof.
There is also a toy example satisfying GQC condition and Assumption 3.3
Example B.8. Assuming (P1.P>) E Am x An. the function f(p P2) #lpip1 1 satisfies
GQC condition and Assumption 3.3 F = P2 for block P2.
with the internal functions Fp. -1(p21 lp for block P1 and
Proof. We have (pi) P2 F 1 2 11p211 (p) - P,) and (l()) Pille il((p)) P2ll 2 |pl p p (p) - P2). Therefore, we have that satisfies GQC condition with the internal functions Fp, - 1p211'p, for block P1 and Fp. for block P2. Notice that "p, - 1 and Tp, = ||pil| Since both ||21l"p, and P2 are polynomials with respect to (p1.P2), we derive that the internal function of satisfies Assumption 3.3
B.3 Application to Reinforcement Learning
B.3.1 Analysis of Infinite Horizon Reinforcement Learning
Proof of Proposition 3.6 The following performance difference lemma 30 13 2 35 plays an
important role the policy gradient based model of infinite horizon reinforcement learning problems,
v (po) (P)) Eaadd (s,,,,)) π (+|s) TT-Is))
(65)
Let d |S { and write 1/4 = (st), Fi(TT) = Q According
to Eq. (65) whose proof is given in Cheng et al. 13 and (AT(si,)) -), T (-18:)- T-|ss)
(Q (8t, ) T' (-1s)) x--ss)) for any policy and N². obtain that
v (po) - (po) = Σ (F.(T), x (-18)) T ((118)))
(66)
Eq. (66) implies that (pb) satisfies GQC condition. For every a A, the Taylor expansion of
Q" (3), a) to K-th order at origin is the same as its truncation at horizon K, which indicates
( (TT) a E.._ RKO
V (VTKx)) $1.00 a) gK+1
Therefore, according to the fact that
(s (T)) (st a) 1,
have that Q (st, satisfies Assumption
3.3 with θ = 0, O2 and Ko 1.
25

---

B.3.2 Analysis of Finite Horizon Reinforcement Learning
The function structure of finite horizon reinforcement learning policy is strictly polynomial. Moreover, since the action-value functions on horizon h is only dependent of policy 1-+1 we may therefore verify that the objective function of finite horizon reinforcement learning satisfies GQC condition by utilizing fimite difference expansion on function error J/ (pt) JJ (p))
The finite horizon reinforcement learning considers the following policy optimization problem:
min J (p1), TEX
(67)
XH. and each X₁ denotes [Sh] probability simplexes. We write S = (sp =1==1 for any h E [1 H] and denote the action-value vector on state sh,in at horizon h by 0% QT**1 r).. According to the definition of finite horizon value function Vehl we obtain the observation Eq. (68).
where J (p:) = Ess [V ($1)], and x= X1 |Sal
(pt) - (T,)
Σ
J Tin (p1) J1 Fish Ta-l (pi))
H
1.8 (shy ),, (1188)))) - IT =x((111))
Pr, -in (-1os)
h=1
(68)
Since Q Thiii (sh, an) ) is a polynomial with respect to policy a:H. whose value is bounded by H -- for any 8, E Sy. and an Ar. we derive that J (p,) satisfies GQC condition with internal function FA,i, (T)
Tk 1:H (8h for variable block Lh,i where in E [S 0, θ = 0, θ₂ = H and Ko = H. Therefore, for
h
and F satisfies Assumption 3.3 with finite horizon reinforcement learning, it follows from Theorem 3.5 that Algorithm with parameter selection Eq. ? finds an e-suboptimal global solution in a number of iterations that is at most OH [a log(I-An] De - log (s-1))
C Minimax Optimization
We begin with showing the connection between GQCC condition and GQC condition. Without loss of generality, we assume n, = n and m, = m for any E [1 : d]. and let f = n m. If f(, y) and -f(x,) :) satisfy GQC condition with respect to pair of minimizers x (ty and y yx)), respectively, then we have the following estimations of function error
f(x, 3) f(x" (3),
(4AP))),....)--PPtaaaa" (v)
(69)
1=1
f(x, (o,)"((x))) f(x,
(F((P(z), x, y (
(70)
Ty (x)
where f((Q. = (Q.,,, for any Q Rxd and z; E F"+m and each P, includes the internal function of f(. 3) for varriable block æ; and the internal function of - fx, -) for variable block y, It follows from Eq. (69) and Eq. (70p that Eq. (10p holds for with vix(z) max(1/7x(00) (z)
C.1 Preparatory Discussion
In this section, we provide the convergence analysis of general version of Algorithm 2 i.c., Algorithm
4
We consider the diveerennce-genrraiin function with Bregman's divergence 1/ (i.e., V(x,, u)
(x)
v(u) (Ve(u), x u) for any u) over general compact convex regions Z = X' x ) C
RE 14 Di m. Before introduce the main theorem, we need the following assumptions:
Assumption C.1. There exists positive constants A, D such that
[Ai] max [|] < A uniformly on Z.
(E[1:d]
26

---

[Aa] max
max (V (z), (g. ) + (y: (g) [e
max (v(x;)) + v(Bi)) S D. [E
[Aa] v modulus 2 with respect
|| (i.e., vi [1: d. V( u.) Bi U; E 2; and V (y; w;) 2 y; - will for any w; E V:).
| u.ll for any
|| 11, then (1) in Assumption C. holds with A = 2: (2) in Assumption C.I holds with D = 2 [ (log(n.) + log(m,)): (3) in Assumption
we choose v(z)= = و3 x (ag(((()) and |. ||
C.1 holds following Pinsker's inequality. According Remark C.2 we state that there exist some
compact convex regions Ri (m:+m²) with proper -eererrteggnnraating function v and proper
choice of g satisfy Assumption C.1
compact set of Euclidean space, then it is reasonable Remark C.2. If the feasible region function v (i.e., v(x) = ンÿ= =(i) log (o)() over the that assuming the divergence-generaaiee
probability simplex or v(x) = > l over the standard compact set) and the norm || || are uniformly bounded on every Z,, For some Bregman divergences, if x" is a fixed point. ( x²) can be bounded by a constant (may depend on the dimension of space) on a compact feasible region. such as V(. 2²) = -1 with x² = 0 on the closed ball B (0) for radius R E (0, co) and ((,,x=) (= with x. (1/n.- 1/n) on the probability simplex A...
Assumption C.3. Definition 4.1 let matrix-valued function P has the form of P(Q where Q* Rxd depends on 2, and assume that satisfies the following properties on region |Q]| I C} x Z for some constant C' >> 0:
{Q E R Rexd
[A4] There exist constants L1, L2 2 0 such that F (.) is uniformly L1 Lipischhi continuous with respect to || : under || ll oo. and F, F,,,, is uniformly Læ-Lipschitz continuous with
respect to -|- under || II---
[As] There are a positive constant 7 > 0 and a pair of sets of matrices (B. (C.) c
R fxd U 0 satisfying
D (B. + C:)
S y, such that the following bounds hold
(0,
C (FT (Q, -z,),
1=1
Dr(a. (1'
B F. 2.). 1.- y.)
for any y, y E y and æ' E X.
[Ap] There exists 0 10,1) such that P(, 2) is 6-contraction mapping under [P(Q, 2) < C' for any z E Z.
lloc, and
Lemma C.4 (General Version of Lemma Assuming that Assumption C.1 and C.3 hold, [P(Q,, : lk.. is continuous, and convex with respect x, and concave with respect to y for any (k,j), and
min kej
2 C' for some C' > 0, then we claim that there exist Q" E RR. txd and
[C.).. (B.jks
E Z such that
Q' =P('' x²' x²,""),
(71)
Q' <P(Q' x. x,yy) Qt 2P('' x=' y)
(72)
(73)
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 E Rexd there
exists a pair of x" y that satisfy the following
P(Q,x",)) < P(Q vr) P(Q.0,y))
(74)
27

---

Proof. Considering the following iteration
z argmin 1/ (F.(Q, 25 1 ); zi) + V (z), (of( + V (g.'
=
(75)
9 argmin 1/ (F, ; + V (g (ox) + V (
g,e2;
for any i E [1 df and combining [77 Lemma 1]. we have
[C (Q.) - x1) + B (FT - -vi)
<(CCilk
+ (Bilk,)) DD |Cilks Σ F? (Q. zt) F? (Q. ( ||| - -9
T
+ [Bi]as
Σ
(Q, x FQ 20 111 | (,:\')
(1|a)) - (,,041² + -110 a (1)
[B. Mui
(110) (,: + ||( 1-----1111 -vili²)
17
<(Ciik + (Bilk.)) -D n13(1C + [B.lks)
T
Σ -1
2
t=1
mil((C [..le.)]
T
2 - 9:ll + 2 |1g 1-1 2111?)
(76)
4
for any i E 1 d.. (k, [1 4 x [1 d]. and z 2, where (a) is derived from A4 in
Assumption C.3 and Cauchy-Schie -chhwrr inequality. Therefore, by setting 1 = 21g 2T = (ØT, Dr the following estimation holds for any (k;,)
vCr and 7 Ei= x²
P(Q, Tr. - P(Q, x', Brr)..
max (#' E2
P(Q Ø7) - P(Q. Ti. y kss
(Cilks (F.(Q.z)) (.+).) + [Bels (F, 21), vt ((+t)))
2ym D + A
(77)
T
where the convexity of function PQQ.. w) P(Q, u, 1)k, for fixed Q and (u, w) implies (b), and (c) is derived from Eq. (76) and the definition that (ø7. Ø7) == argmax(P((Q) T7, y²)
z'eZ
P(Q, x', Mr.. Since 2 is a compact set, the sequence ((Dr, }r) must have convergent subsequence. Therefore, all accumulation points of the sequence {(0T, Dr ) satisfy Eq. (74 by using the continuity of P(Q.:)).
Now, we define the iterately update as follows
Q = P(Q', vi),
(78)
28

---

where (z). vi) satisfies Eq.
77 in Lemma C.5 w.r.t P(Q', ..)). It's direct to derive that
Q_1 Q' <P(Q' o i vi) - P(Q -.-11.77
< Q Q'1 1l,x0
(79)
Q Q' PP xi. vi-1)
-PQQ" oi. vi-1)
2 0 Q Q' ll
(80)
Finally, according to the contraction mapping principle, we complete the proof.
n7
Corollary C.6. Assuming preconditions of Lemma C.4 hold, and letting (fi(Q.) : +mm
RIj be a sequence of continuous convex-concave functions which satisfies ( = (F (Q. ))
Fu (Q:
-)))e for any fixed Q E Rexd and E [1 : d], then there exist a matrix Q" and pair of
(xx", V²) which satisfy Eq.
7
Eq. 73) and
fi(Q x. vi) 2 fiQQ', 2i,3:), fi(Q" x. v.) S , vf),
for any 2, 2, and i []:
Proof. With proper selection of we have the following bound which is similar to that derived from Eq.77
max fiQ (IT)..))) VE
min fi( or, (Dr))
x/E
Ji(Q ( (+7),,))
[Q - + -()))))))))
1=1
An An D + ST,A113
(81)
T
for every [1 d/. where {2, (I,, v.) follows from the iteration 75) and (z))); (()))) h (+)))) denotes argmaxi (QQ (ir). vn f. x (Dr):)). Hence, by directly leveraging
=!EZ,
the result of Lemma 4.3 we obtain the result.
Before stating the general version of Theorem 4.4 as follows, we define
Y7 8 +(c+1) 7D (
16nl2 7 21 64,) 1303) (log(c+ T) 1).
(82)
C.2 Theorem C.7 and Relate Proof
Theorem C.7. [General Version of Theorem which satisfies Assumption C. and C.3 with constant matrix function P = Q²' where Q" is
4.4 For any generaized quasarr-comees-comcave function
unknown and satisfies Eq. (71 Eq. (73), with parameter configuration in Eq. 12. the weighted average of Algorithm
2's outputs { ft= satisfies the the following inequality
6 max Ed ZE2 11=1 V1(x)) (1 (1-0)
3D - +100L 5ALLY? + A
((T, S
(83)
For generalized quasar-convex convex-concave function satisfying smoothness and recurrence conditions, the iteration complexity of our algorithm matches the lower bound [52] for solving e-approximate Nash equilibrium points in the smooth convex-concave setting, up 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.
29

---

Algorithm 4 Optimistic Mirror Descent with Regularization for Varial-Vsi
Input: {=(] {9?)
i-1
(ar 2 0 (Ei= 1). t% 2 2) (Ae 2 0) and Q 0.
Output:
_(=100z 0.2".
-t=1
I: while < T do
2:
Q' (1 31-1) Q'=1))"111
+ P z0-1)
3:
for i E [1: do
4:
x arrgmin ( ), + V (a; (07))=1) + Aev(as). m,Ex;
5:
y. = argmin " (Q ,-- ). + + (y.: (1"))=)) + ).(()))
6:
(g.)² = argmin 17 (PT =)) + (0. (4:) + ),v
oPER.
7:
(g.)²= argmin (Q' =)) + V (o", + \vv(g,))
end for
9:
1 t + 1.
10:
end while
Our analysis relies on the connection between F, 21) and F,(Q". 21). Theorem C.8 combines a) classical (logg())TT) bound derived from regularized OMD, and b) the weighted average of iteration error || 11. over E [1 : T] which has the form of Σ/=1 0g Q'
12
with magnitude O(T lTg( and c) weighted average of approximation error Q| - Q" cloo over
t E [1 :T] which has the form of E/= ar Qrl Q* to bound the max-min gap of at Ty. Next, we leverage Lemma C.9 to show the decreasing trend of approximation error |Q' - lee and
bound . Σ/= 0t Q Qo by 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 Σ 04 [4| Qo to Theorem C.8
C.2.1 I
Theorem C.8. Assuming that Assumption C.1 holds, set the hyper-parameters for Algorithm carefully such that
ar(7 de) 2 0++17++1
(84)
veln + Xee)
1 < min (E[1:T]
(85)
4T.2
Suppose that v modulus 2 w.r. || 11. ||=||| S for any 2, and (2t) follows the iterations of Algorithm 4 then can show that
ann
max I (iT,, y') - min (a',Dr) y'Ey
(
max :E(lad]
max (V (g7)) + V (9))))
#'E
17 z.E2,
1
jellz1 g - +
nt + A
و zi11?
at
21
2
+.
2
2
1==
azde
max 2IEZ.
(u(x;) + o(yx)))
"1
T
+ 2B(
an
1| - Q" -
Nt + Ax
8A2 L1)
+ -2A(()) 1 Σ
F. Q¹ 20 +
71 + A
(86)
where B(b) ;= max
Di vx(()) and ΣT: == T aiz!
30

---

Proof. Recalling the definition of GQCC, we derive that
fi(Q", us fia (87)
max f(x,z') min y'E3
f(z', y) SB()) max <E[Ldd]
max w,eyi
f((Q", 2i, w.)
min u.eX:
x x'ex
for any 2 = (x, 2). v (u, w) E 2 and
F((Q",(ār): (ār),, - -((QQ", u. (ir))) S -
at w.) - f((Q², u, wi)]
(88)
at (Fi(Q",zz)) , - -vi)
t=1
an (F: 21), u²) 2AL1
aul| Q"11=0
for any U2 2,. Using the optimality condition, we obtain
(F,(Q'"), ,,, ) 2 - 9i) S 22 (V
+ (( (o9)
2' (V (g). (gf) + (g).
+ de (V m²) + V (6x") vi))
"
+
+ (
(a!) - (vi)).
(89)
(F,(Q', 2))99 01)
7t (V (u, (gf) + (w; (w (0)))
17
(V
+ (( (=))
Tt A (V (ui, (g. v (w: (g.))))
"
A (v(u:) + v(w::) - (( v ((o))))
+
(90)
7
For each / [1 [1:T]. can apply Eq.
89 and Eq. (90) to the following equation
at (F,(Q', 2/), 2 - wi) =oz (
=1),
9t)
+ (F, 2/) (1 -
gill
2t (V (ui (gf) + (w; (0)))=1)) Ytt - de (V (ut, (o:)))
<az
1)
(V (gf) + V (4', (1:)) 7t " V (w,, (of)
7 d (V ((9)) =!) + +V ((g)) v/)) + a,dr
(u(u,) ) + v(w,)
17
-- (19?))) ((g a. (F.(Q' ./)
-F,(Q' 1- x ), x g
911)
31

---

Therefore, by summing Eq. (91 from t = 1 to t T and utilizing Eq. 884 we have
at (F, z1), 2 v.) - π
ann (V (u,, (gft)) + V (w., ())
2 1=1
a+d
max (v(x;) ) + v(y.)) #1E2.
7
T
Σ
Nellz 11= + de
l1g - zil??
a2
17
2
1=1
T
|1,( 2)) - F, 10-0-,,,---1- 11
(92)
Tt X
According to the Lipschitz continuity of F;, we derive that
Fi(Q', 21)
F. ,-5 , 1|
+ A1
22n
1
at
| -
2n [ Σ or 1 - 11
(93)
Mtt + Xe
itt + de
follows from parameter setting Eq. (84) and Cauchy- inequality that
9
11- Oz- (Th-1
+ de-1)
9
-
21 11
0x
||
112
(94)
2
2
Combining Eq.
85
and Eq. 944 may therefore obtain
T
a2
It 2
g
11
7/ A llg
21|12
2m
a2
||
21-1|
4
7t
+ A
20
||
(95)
7/1 + A1
Applying Eq.
993 and Eq. 955 to Eq. (92 and utilizing Eq. (87)
Eq.
88
complete the proof.
D
C.2.2 Part II: Estimation of Approximation Error ||Q
Q*1
According to the iterately update of Q', we can derive the upper bound of weighted average of ||Q' - Q -1 Next, we aim to bound ||Q' Q'Il for each iteration I. this section, we select the following parameter settings:
(1 (1-8)1/2
c= 2 (011-))_1,1 7 8(7AL1)
Br c+t at = BT,,,
?t
0t-1
de =1 7o. (96)
at
(1-0)1/2
Lemma C.9. Consider the settings:
< 1, de = 1 - and 17 < 80yAE1 Then, we
obtain the estimation I[Q' Q'Il as follows,
|| - Q*1 -
(1+0)/2 H3:
(97)
j=2
for any t 2 2 where
j-1
Hj : ( 16m[/2)
13-1,171 +2 >
Bj - An
"7
1-1
+ 277 647 1302
Σ
B 1. B2 + L,
(98)
32

---

Proof. According to the fact that Q" is fixed point of function P, we have
Q- 1111x P(Q =²) - P(Q",=")
1 (P((Q", x²""") P(Q", x², y"" +P(Q", x", x²,y")
" x ,")
d
1 (F", - -x;) C, +0 c
Σ Br B1-1 - -Q'l
ede,
(99)
Where (a) is derived from the maximizer's property of y" for matuix-valued function ,(Q", x), Similarly, we can obtain
Q'
Σ Be I (Q" ; vi) B, 0
Σ 3 1, I Q"
-0"la=
eaes
(100)
Hence, we derive
11-1,171
Q Q-" Sy max se[1:d
max (V (zi, (g,) V (y:, (g))
#1E2:
2 Σ x=1 31- B1-1,xh
max (u(x,) + =(y,)) 2,E2;
11
+ 2.2 2
B--1x
|| - - 1|
7/ Ax
==1
L3
11-1,8 1,N
11Q th - Qk-1 11 + 0
Σ Be Be-1,x1 -Q'1lo
7x Ax
(101)
by combining
B 1,x 11 (1 33) a₂ and Eq. (99), and using the proof technique of
Theorem C.8 Next, for any i E [1 : d). we can obtain an upper bound estimation of
max
(Q", 2{t, 2x - v;) as follows
0,E2,
max
31-1,6 ,,"(,,²²)) x - -v)) _
D
1 +2 2
+
e,
8
Km
+ C
8 11-1,
1
Σ
3 1,
1
2
817
(102)
Furthermore, we also have lower bound estimation of it
max
Σ B (F, ,
v.) 2 max
Σ 1, (F) -vv)
0.E2
2
max 2
B (F,(Q, ,0),, 23 v.)
- 2AL
1x -Q
2 - 2AL, Σ
B 1,- 1 Q2" - Q7
(103)
33

---

Therefore, combining Eq.
(022 and Eq.
103
we derive the following result
Σ 1, || 2, 11 < 166ALL AL
- QQ"loo -
+ +64n A1y2A2L:, 13
A=1
A=1
+D
1--117 +2
Br Lxde + C4 Σ
Br 1 1
k-11
k=1
(104)
for any i E [1:d]
( + 16723) 17
2-1 (8-11 +2
|| - Q' SyD
Σ SL-Indd)
+ 12811"n22 L
x=1
+ 2 (1+ + C²
Br 11-1 Σ
N=
t-1
+ +32n + 0)
B 1x111=
Q'1
(105)
#=1
Finally, by applying
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 ST,I-
Lemma C.10. Assuming that Be = eit and c 2 c', we can obtain the following result:
(c' cc))2
(c t)
(c - T)e" & BT, S (++ 1)
exp
(106)
2c
(c+T+11)
for any T 12
Proof. Recalling that
ST. c+1 k=t+1
d
II
I - (I-C+t)
d) = c+l
exp
Σ log ( 1- c++ c
(107)
1=1-1
we have
BI, S d' 3/(ctto (c+l+1) -
(1+0)c+(+1)d+
(108)
c+t
(c- T 1)
and
(d' (c+cc))2
(c+1)c'-1 (T+
Br. 2 exp
(109)
2c
by combining the result of Lemma D.9 Corollary C.11. Assuming that B c=p C c² and c((1 - 0) 2 1, we can obtain
L
d'
89. c+T'
(110)
for any T T2t21 1.
By utilizing the result of Lemma C.10 we notice that
(1 + x)
(c+
x=
(1 c)
Cc + j (" 1-1
dr + (1+c)²
(c 1c+
(c+
(1 + c)2
(1+c)²
(III)
cc- 1)(c+
34

---

and
(c++)+++)
Σ
8 1x
dc+
==1
==1
(1 c1+
(1 c]
(e+2+1)-
xcc+
c(++)}
(1+c)d
(1+c)*
(112)
ccc-1)(c+
where (a) and (b) are derived from the fact that E + K. + 1)0-2 Σ (c Next, we have
(c x + 1)0
11 STD ( 16nL2
(2(c+2) 2)
2(1 c)2
+ 2(1+ c)3
(c+
() (c-1)(c+))
(c
(c+
(1 c)+
+ (1+c)4
2m + 64n²
clc 1](c
dct
(c 2) (c j)
128n""7211
(113)
and
[ 2(c+2) dr
Btj
(2+0)/2 1
H
<
7D
+ 16n
cettl
17
(ct
/=
+ tf,"
2(1 + c)²
2(1 c))
+
dx +
(c- 1)(c x)
(c+
(1 cc3
(1 + dec
+2 64n L3022
dx
1 dec ()
1 /" (c+ dx
7
2 x)
S -- DD
c
1 + 117L22
2(c 1)²
log(c + t) + 5 2c
+ +640m)
c+t
c-1
2(c + 1)²
(c+ 1)2
+ 217 64n 13
log(c c + 1) +
2c
(114)
where (c) follows from Corollary C.II For simplicity, we denote
Y = 8(c /DD { + 16 + 4007872222 + 21 64n L3C9) (log(c + T) + 1).
(115)
Therefore, follows from Eq. (14) and Lemma C.9 that
||Q' - Q -
Ptj
(1+00/2
11, <
c Y??
(116)
C.2.3 The Last Step
According to Eq. (16) and the initial Q" satisfies ||Q% S C, we have ||Q1|| < C.. We are ready
to complete the proof of Theorem C.7
Proof of Theorem It noteworthy that the hyper-parameters selected Eq. 96 satisfies the
preconditions of Theorem C.8 Combining the conclusion of Theorem C.8 Eq. (166) and the
35

---

estimation of ar (i.e. (r,() in Lemma C.10
we obtain:
on
Gy(2, v) B iE[1:d]
max
max (V (z) (g.))) + V 2,E2:
2 -- ant
max (v(z)) + +e(wii)) )+ + 2n Σ a. 2
7
T
+ +2ABcL Y7
at
+ BL
c+t
2BD
(c (c+2) + dc+22 2)
2(c+ 1)
(c+ 13c (c+ + ++11 1)2
c+T+1
(c+1))
(c+1)a
2
c(c-1)(e+T+]) + dc+
+ +2ABLY
c+T+1 + dc+2)
4c
+ B8A
+
+c)
(c+T +++T+112 +
(c+T+1)e
3D
c+1
<2B
+ 10 + 5AL1 YI + 44
(117)
7
c+T+1'
when 2 1, where B denotes max Σi=1 (z) and (a) is derived from parameter settings Eq. (96) and the result of Lemma C.10
C.3 Application to Minimax Problems
C.3.1 Infinite Horizon Two-Player Zero-Sum Markov Games
To simplify notations, in the following discussion, write S { and denote by Q*
S
(s) (s the joint action-value matrix where Q* (s)))))-)) [| is an action-value matrix on state s;. According to the connection between value function and action-value function
(s:); E. laset [Q* a, b)], bwut *0)
(V= = (1 ()a((s; a, b) + (le
provide the following proof for Proposition 4.5
Proof of Proposition 4.5
By defining
[P: (0.2)aaab (1 ())((; a, b) + re y( (118)
we derive that Q P(Q :)). We can notice that
(P, x. v) P:(Q. x', y)),,a = PP ( (Quyyr (x')²))
(119)
[P, x x,) P.(Q Q, x, y)]a,6 - [( Q xv. y - (3/)x)}
Therefore, for any Q satisfies ||||| I 1, it's easy to verify that
1. F.(., z;) is uniformly 2- 2-Lipschitz continuous with respect to || oloo under || |oo for any zi Zí and (.( is uniformly I-Lipschitz continuous with respect || Il under
|| |11, since F FQQ, 2;) (y. Q - [=.
2. P satisfies [Ag] in Assumptions 4.2 with [B:].,,bb = [Ci]s.a,b 01P(s:ls, a, a) and 7 20, since Eq. (11
3. P(.2) 2) is a d-contraction mapping under || |lso, and [P(cs)) I 1, since the definition of P.
4. [P(QQ, : la,bb bi-linear with respect to æ and y, and minn([C.).a.bbBBBBB....... and b.
[C. B.Jraa,b = 1/2 for any
36

---

Therefore, according to Lemma 4.3 there exist tensor Q" and pair of (æ".y") satisfy Eq. (II.
Furthermore, the (x". .y") mentioned above is Nash equilibrium of J (Pn) by utilizing Corollary
C.6 We may therefore derive that Q' = Q Leveraging Eq. (65) for any Nash equilibrium
(x:" yy" E Z and denoting Q Qm y (st, we have
Je v (po) - ju "we (po) = Σ dm (V) (s)
1000 ' (8, (-1s), (-18))
(120)
eES
-(Q"' "v' (8.1)))((11s)). x (1){11b))
[S]
d
(v) (8:) (Q x;)
min Q Q us uz) u.E.
(121)
Po
1=1
where x (1)) argmin Ju.v and y² (x:) = argmax Ja. (Po). Similarly, we have uEX'
wEy
joey (a) (pu) jou
v2' (po) S
()) max ((Q)) T Zs. w.;) ((Q)) T 2/. y/¹
Po
w.yY
(122)
By setting (z) = max dpp (m) de (w).3) (8:)} (s:)3 and combining the facts that Qi 2; y
p.
min Ji(Q", ubs, y;) 2 and max fi(Q" a. wi) fi(Q", aq. yu) 2 derived from Corollary
u:E2:
wiEVi
C.6
we have
d
(a)) (p) J -0 (v)) (Po) -
Σ
(z)
max f((Q", w.E)
2;, w;) min f((Q", us v.)
n.E..
1=1
(123)
C,3.2 Convex-Concave Minimax Problems
In this section, consider convex-concave minimax problem over compact concave region 2 X x y - R m, which satisfies Assumption C.I with pnperence--gnnraaine function The standard convex-concane minimax problem is formulated as follows:
min max fæ. y),
(124)
#eX yEy
where f is convex with respect to and concave with respect to y. Therefore, we obtain that f(z.8"(x)) - f(x" f(x"(v), s ( - x (v)) + (-V y
(125)
for any = (z. E Z. We may therefore derive that f satisfies GQCC condition with g(z) =
and f(P(z) 2) f(z). Furthermore, assuming f is L-lipschitz continuous (i.e., [[(
f((e)ll- < L||= - æll for any 2, E Z) and choosing P = O, then verifying that f satisfies the preconditions of general version of Theorem C.7 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 when f is L-Lipschitz. Therefore, under the smoothness condition of S. Theorem C.7 implies that (s--1) iterations Algorithm 4 needs to find an e-approximate Nash equilibrium of / matches the lower bounds (1=- [52 for the number of iterations that any deterministic first-order method requires to find e-approximate Nash equilibrium of smooth convex-concave function.
D Auxiliary Lemma
Lemma D.I. For 2 17, the function g(T)) can be bounded by
80640 To 3 Let g(L) be defined
T-1
I k (k + +1 1) [xp(k])
kk=l
37

---

Proof.
(k
7)!
9(T) 1
r
+
(k
(k+1)
k!
r
1m1
d7
d
a²
da
da
1 1-
a=r-1
1==22-11
80640
(126)
(
T-11
Te-
2
(a) can be deduced based on the following inequality
d² ( a
(-1)*
8!k!
a
h+1
da 1 -
k
(k
+
1)!
1
k
0
8
α
<7
k
(6)
k=1
=7!
1
8
<!
exp
1
80640a
(127)
1
where (b) and (c) are derived from Leibniz equation, and the inequality cx 1 S 2r holds for 0 S x & 1/2 respectively.
Lemma D.2. For any n E N,r RR. p E A", if holds that p arg min 1j (p,r) + (T.(p)))) ped,
then we have
(p" r, _ (KL(pllg) KL(plpp" (L(p"(1g))
(128)
Proof. We just need to prove p p"(1) = (')) = Σm= 41z) expl -,त(
exp np(())
for any E [n]] which satisfies
ip - p', fyr + log(p') log (4)) = 0,
(129)
for any p E An. Assume that F(p) = 1/ (p,r) r) (Tl()))) and define E(p) -E p(i) log(p(i)) for any E A.. Clearly, p' E A.. Hence, for all p An.
F(p) = (p. r) + KL(p|lg)
=n (p',r) r) KL(p' ([q) (p p'. log(g)) + E(p) E(p')
= (1),r) + KL(p'll E(p) Elp') + (p p', - log(p'))
=F(p') KL(pllp').
(130)
(b)
where (a) is derived from Eq. finish the proof.
129
Therefore, we obtain that p' = p'. By using equality (b),
Lemma D.3. Suppose that for E (0,1), we have | S1 r.
Then
T-T T 2r
x2 x²(p. q) < KL(pllg)
2
3(1 - T)
38

---

2k=1 (-1)-=1 x* and define
Proof. We consider the Taylor expansion of the function log + x) Qr,((x) = x -3 + Dr) x². According to
|x/3
log(1 + x) Qr.((x) 2 Dr
(131)
3(1 T)
for any x E [- we have log(1 + x) 2 Qr, when D 2 उ/- and E [-T, Therefore, we obtain
p(i)
KL(pllg) Σ p(i) log
9(5))
2 Σ p(i)
[
(p())
-1) - ( { +
DD Dr)
(p())
q(1) - 1) 1
27
q(1)
2
#=1
( Dr Σ p(i)
P(U)
- 1)
-x²(p, 9)
9
9(5)
j=l
(1+- + DT(1 (1(1+
(p)())))
x2 (p.
2
= - (p.
(132)
We complete the proof D 3(1-r)
L
Lemma D.4. Suppose that E R²,T E (0, 12,) S 1.4
and P. P E An satisfy, for each
j 6 [n].
p(i) exp(rrii
p(1) E p(j') . exp(r(j'))
(133)
Then
(1
3(1 - +4 +4)=) Varp(r) 5 Varp(r)
2
xp))p))) - 1+
3(1 ((1-7) + 1) ))) Varp(r). (134)
2
Proof. Without loss of generality, we consider the case (p,r) = 0. If not, redefine F =- (p,r)- e(I]i]lo S T) and analyze ÿ where e R" an vector. It's clear that
p(j)
exp(r) 12
x² p) 1+ Σ
p(j)
= Ep
(135)
p(j)
E (eep
We define Fb(() = 1++ 2 x2 Fb( = + x
1+Dr x² and note that for any E [-7,7]
2
Dr
x3
exp(x) Fb(x) 2
2 x²
(136)
6
Dr 2
|+| 3
F cxp(x} 2
(137)
2
6(1
where Eq. (16 derived from the summation of the 2 and 2k 1-th (l: 2 2) terms in the Taylor
expansion of exp(x) is always non-negative, Eq. (137 is derived from Σ x² S 6(1-x)
|x| S |
6(1-r)
for any x E [-r, 7]. Therefore, we have exp(x) Fb(x) > 0 and F3(() - -ep(x>} 2 for all
x TT if D 2 _1- Then, we have
1 2r + (2 (D+2)))a²* < (exp(=))² < 1 2x + (2 (D+ 2)7)
(138)
when Dr < J. In addition, by (p.r) r) 0, it's obvious that
Dr
1 Dr
1+ 2
Ep |r < Ep
2 E 1.
(139)
39

---

Combining Eq. 138 and 139
we derived that
1+ (1 (1- (1
[r]] _ [expe }1) < 1 (1+
(140)
1 (2 (D
|rr =mp (exp (r)) - (1+
(141)
for Dr S 2. According to Eq.
(35
140 and (141). we have
exp(r}
(1- (2D (2)
-1+ F
2 (1 (2D + ()))),((2))
Ep(cpp(r)
1+ (1+
1)7)
exp(r}
+ (2
-1 Ep
S (2D + Ep(r?
E Ep(exp(r))
1 (1 (1- (D - 1)7)
We derive Eq.
134) by setting D 3(1-))
Lemma D.5 (Lemma B.6, [15 Let 01," dii be softmax-type funcciiion
cxp(
d((x) Ex=1 Tik exp (k))
(142)
where j: E [1, ,n], Σ Tik for any i [L.... .4. Let P(x) Eia
D P(O)
x
denote the Taylor series of II 0, Then for any integer k.
D P(O(
Σ k
< (e
(143)
a
We introduce the conception of (Q, Rb-buudded function briefly. Suppose & R - R is real- analytic in a neighborhood of the origin. For real numbers Q2 R > we say that i (Q, Ro-buudded
if the Taylor expansion of Φ at O, denoted (x( = 00 Σ al==
na f(o) va satisfies, for each at
integer i 2 0, | a! < RR
(00)
Lemma D.6 (Detailed version Lemma 4.5, [5)). Suppose that h, E N. R - R is a (Q, -l)boudded function such that the radius of convergence of its power series at 0 is at least > O, and Z (ZO.... Z²} Rn is a sequence of vectors satisfying |z'
for h' and E [0...., T h1), it holds that Die Z'1l S 3h (M) BM for some B 2 3, r e². Then for all t [0..... , h].
EE (0.... ,T). Suppose for some (0, 1), for each
(Du o | s Q g(()) 3hh Bh+1
(144)
where g(T) is bounded function with respect to T.
Proof. Without loss of generality, we assume ((0) = 0.
We define (o o z)
Exe2g an (z and obtain
(D 2))²
Σ Σ
ay (Dn
7E2 =k
layl
Σ II
1= 7E2 7|=k
x:(h)--11] j=1
Gh (TR)
|ayl-
Σ B[MN-
k= YE2 7/=k
20
(TR) h Bh max { k7, (hk + 1) exp {
Bh
2k
lay1-
k=1 7E2N 7/=k
k
max { (k + exp (2k}} Bh+1
PR
(0) k=
<Q . g(T) 1. Bh+1
(145)
40

---

where (c) is derived from RD-bunddd condition.
Lemma D.7 (Lemma C.4, 15)). Let (n,T) C E4 with n 2 2 and 2 4, we select H =
[log(T)],, 90 4m and B V Assume that {2' [0, 1]"h and {p'} An satisfy the following condition
1. For each 0 S h < and SIST h, holds that II(),)) S 8hh H3h+1
2. The sequence {p'} Yim is cconsecuuivvly close for some Ç E (2T) -1 , /8//256].
Then, we have
T
Σ Varp (z' - 2111) S 23
Σ
Var, (2'-1) 165120(1 + <)H$ +
(146)
1=1
Proposition D.8. Given constant
0, we have
Sc.
(147)
+
k=
Lemma D.9. For constant c² c' O. the following inequality holds
d'oog 1
(c' cdc)
log (1- d'
+ log
c+t
(1-ctk) ctk)
(148)
C+T
c+1+T
when T > 1.
Proof. Accoding to the Taylor expansion of log(1 x) when æ < 1, we obtain the estimation of for any 2 as follows
log 1 [1-6) c+h
5 d
log 1
(149)
c+ k:
c+k K' d
(d + ed)2
(
log 1
2 c+k k
(150)
ctk
2
c k
Next, we have
Σ
d'
T+1 d'
dr d log
c+++T)
c+l
(151)
c+k k
c+
T d' (c'2ce))
d
(d'cc')2
27
2 1-1
+
dx
c+ k
2 c k
c+
2
c+
c
(c'
cd)2
> d log
(152)
c+T
2c
E
Limitation
For 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 future work.
41

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: YES
Justification:
We have a detailed explanation in the contribution section of the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: YES
Justification:
See Section in appendix.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: YES
42

---

We provide the assumptions and the associated theoretical results in Section and Section respectively.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: NA
Justification:
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
43

---

Answer: NA
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nips... cc/
pub icl gui Codeeubmie ss ssionns cisionnoliic icy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https //nips. cc/ wwwpiicgguiiiooooooo / /eddeddee//deeeeeeee CooeeeoeeeSeeeeeee SodeSuumiieee Submiss wwwsssssiiiiigpo.. for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: NA
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: NA
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
44

---

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 96% CI, if the hypothesis of Normality of enrors 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 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.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
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 compute required for each of the individual experimental runs well 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 into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http::::///eurs....mm httpa//www.p...ppoaaacccccccaaaa
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations 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 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
45

---

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 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.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: NA
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have 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 challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators 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?
Question:
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 dataset.
The authors should state which version of the asset is used and, if possible, include 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 (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperssi hopersswiccoee com/ dataset has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
46

---

Answer: NA
Justification:
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: NA
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: NA
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
47


Reviews:
[{"review_id": "uTedUdih4J", "reviewer": "Reviewer_hhK8", "summary": "The paper studies the optimization of generalized quasar convex (GQC) functions, a new global\nstructure introduced in this paper. This definition relaxes the quasar convexity (QC) \ncondition, in a way that different components of the optimization variable satisfy \nthe QC like condition with different parameters.\nThe key idea is that if we simply treat a GQC function as a QC function, one needs to take\nd times the maximum value of these paramters which can be large. Applying GQC allows one \nto deal with the sum instead which could be significantly smaller than d. Leveraging this \ninsight, the authors adapt the well-known optimistic mirror descent algorithm.\nThe main use case appears to be in policy optimization in MDPs, where the authors show \nthat the GQC condition is shown to be satisfied by the expected value function.\nThe authors also define a similar condition for minimax optimization problems, and apply \ntheir framework to find the Nash equilibrium of a two-player zero sum Markov game.\n\nOverall my evaluation of the paper is quite positive. Even as a non-expert, I was able to\nappreciate the ideas and the contributions of the authors. The paper is also well-written\nand easy to follow.\n\nI have given a positive score to reflect my current assessment. However, as this is not \nmy area, I am unable to evaluate the technical merit and novelty of proot techniques in\nthe paper, and I did not dive into the proofs in the appendix. So I will also wait to hear\nfrom more expert reviewers.", "questions": "See above", "limitations": "See above", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "See above", "weaknesses": "See above", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for dedicating your time and effort to reviewing our manuscript. We appreciate that you acknowledge our paper. We will also carefully revise the paper to enhance its readability.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eSHTLChA3v", "reviewer": "Reviewer_NA4U", "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.", "questions": "Yes", "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?\n\n- 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?", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The introduction of GQC and GQCC conditions provides a fresh perspective on optimization problems involving multiple distributions, extending beyond traditional convexity assumptions.\n\n- The paper offers rigorous theoretical analysis, including complexity bounds for the proposed OMD algorithm, and demonstrates that these bounds are tighter than those for existing methods.\n\n- The application of the proposed framework to reinforcement learning and Markov games showcases its practical relevance and potential impact on real-world problems.", "weaknesses": "- 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.\n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments and suggestions. We will respond to each of your comments individually in the following.\n## Discuss the applicability of these assumptions in broader contexts:  \nThanks for your suggestion. We will add more discussions on the applicability of the assumption and our framework. For minimization problems under the GQC condition, we begin with a convergence result relying on the general Lipschitz continuous condition of internal function $F$. However, under this condition, we need to additionally assume that $\\max_{i\\in[1:d]}\\gamma_i<+\\infty$. Based on the aforementioned assumption merely, according to our knowledge, it appears impossible to eliminate the coupling effects between different variable blocks without a consistent upper-bounded assumption of $\\{\\gamma_i\\}$. In certain applications, $\\max_{i\\in[1:d]}\\gamma_i$ can indeed approach $+\\infty$. For instance, in the infinite horizon reinforcement learning problems, the discounted state visitation distribution $d_{\\rho_0}^{\\pi}(s)$ for a particular state $s$ may approach zero, implying that $1/\\gamma_s=0$. Therefore, to address this uncertainty of unknown $\\{\\gamma_i\\}$, we introduce the Assumption 3.3.  Assumption 3.3 is not hard to achieve. In Proposition B.2 of Appendix B, we demonstrate that if the absolute value of the higher-order derivatives of a vector-valued function $F$ grows exponentially with its order, then $F$ admits Assumption 3.3. Furthermore, since the feasible domain of the functions considered in this paper is a bounded closed region, the conditions of Proposition B.2 are easily satisfied by smooth $F$, making Assumption 3.3 hold easily. Additionally, we provide two examples of functions that simultaneously satisfy both the GQC condition and Assumption 3.3: a toy example (Example B.8 in Appendix B) and a simple neuron network over a simplex (Example 3.4 in Section 3.2). For minimax problems, most algorithms that guarantee global convergence are based on a convex-concave structure. Our assumptions not only encompass the assumption of Lipschitz continuous gradients for the objective function $f$ in the convex-concave case (refer to Section C.3.2 in Appendix C) but also provide a unified landscape description for infinite horizon two-player zero-sum Markov games. It is worth noting that Algorithm 2 in this paper achieves a better convergence rate in infinite horizon two-player zero-sum Markov games compared to the results in Wei et al., (2021).\n\n## Experiments:\nPlease refer to response Author Rebuttal:$\\textbf{Experiments}$.\n\n## Potential relaxations or alternative conditions:\nThanks for your concerns about the generality of our conditions and the request to relax the assumptions. The GQC condition include quasar convexity (QC) condition. Actually, our algorithm can achieve $\\tilde{\\mathcal{O}}(1/T)$ convergence rate under QC condition with Lipschitz continuous internal function $\\nabla f$. Currently, to achieve the faster $\\tilde{\\mathcal{O}}(1/T)$ convergence rate, we do not find a clear way to have a good relaxation. The main challenges of multi-variable block optimization problems lie in its non-convex (non-convex-non-concave) structure and the coupling of multiple variable blocks. Therefore, a simple Lipschitz continuity assumption on internal function may not be helpful in obtaining a faster rate. However, for a slower rate, such as $\\tilde{\\mathcal{O}}(1/\\sqrt{T})$, it is possible and we leave it as a future work.\n\n\n## Detailed insights or examples of real-world problems where the proposed GQC and GQCC conditions are particularly beneficial?\nWe prove that for reinforcement learning (RL) problem, GQC can be achieved. For the infinite horizon reinforcement learning problems, the discounted state visitation distribution $d_{\\rho_0}^{\\pi}(s)$ satisfies $\\sum_{s\\in S}d_{\\rho_0}^{\\pi}(s)=1$, implying that $\\sum_{s\\in S}1/\\gamma_s=1$, therefore our algorithmic complexity does not rely on $|S|$. However, if we describe the properties of the function using the worst $1/\\gamma_s$ (similar to the QC condition), then the complexity might be $|S|\\max_{s\\in S}1/\\gamma_s$. Similarly, we prove that infinite horizon two-player zero-sum Markov games satisfies GQCC condition. For infinite horizon two-player zero-sum Markov games, $\\sum_{s\\in S}\\psi_s(z)\\leq 2$ for any $z\\in \\mathcal{Z}$. Therefore, the convergence rate of Algorithm 2 does not depend on $|S|$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OUj2adHmCL", "reviewer": "Reviewer_e1HQ", "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.", "questions": "Does the assumption 4.2 can be relaxed? \n\nCan the Section 4.3 be written more?", "limitations": "No", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "It looks like the authors propose a new theoretical analysis for the quasar-convex optimization.", "weaknesses": "It would be better if the authors added more motivation for why they focus on quasar optimization. \n\nAnother point: the theoretical analysis demonstrated is not very clear. If they can show it clearer, it will be better,", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and suggestions. We will respond to each of your comments individually in the following.\n\n## Motivation:\nIn many non-convex optimization problems, the objective function often admits  ''convexity-like'' properties, such as matrix completion, phase retrieval, and neural network under some settings (Bartlett et al., 2019; Ge et al., 2016). Therefore, exploring the structured sets of functions for which the problem can be efficiently solved is meaningful. This aligns with the ideas proposed by Hinder et al., (2020). Quasar convexity is a widely known condition in the field of optimization with two typical examples in machine learning: 1) the loss functions of neural networks satisfy the quasar convexity condition in large neighborhoods of the minimizers (Kleinberg et al., 2018; Zhou et al., 2019); 2) Under mild assumptions, the objective function for learning linear dynamical systems also admits to the quasar convexity condition (Hardt et al., 2018). Furthermore, generalized quasar convexity (GQC), as an extension of quasar convexity, encompasses not only quasar convexity but also the function structures of reinforcement learning and certain neural networks. This implies that the objective functions of more machine learning problems may satisfy the GQC condition. Our analysis provides a theoretical guarantee for the solvability of approximate global optima of these problems. As a supplement to the GQC condition, generalized quasar-convexity-concavity (GQCC) extends the concept of convexity-concavity. Based on this landscape characterization and appropriate assumptions, we propose an algorithm for solving minimax problems that have a better convergence rate in specific machine learning problems.\n\n## Theoretical analysis is not clear: \nThanks for your suggestions. We will add more intuitive discussions for our analysis. For\nThm 3.5, the key idea is to reduce the impact of each variable block on the function error, which plays a crucial role in establishing global convergence. Concretely, we separate the upper bound of $\\frac{1}{T}\\sum_{t=1}^T(f(x^t)-f(x^{*}))$ into: a) an invariant lower order term and b) the weighted sum of variance of finite difference term $\\frac{\\mathcal{O}(1)}{T} \\sum_{t=1}^TVar_{x_i^t}(F_i(x^t)-F_i(x^{t-1}))-\\frac{\\mathcal{O}(1)}{T} \\sum_{t=1}^TVar_{x_i^t}(F_i(x^{t-1}))$. Furthermore, applying the property of sequence $(F_i(x^t))_{t=1}^T$ under ''polynomial-like'' structure condition, we bound (b) by a quantity that grows poly-logarithmically in $T$. For a more detailed proof sketch, please refer to the beginning of Appendix B.1.\nWe will add more explanations for both Thm 3.5 and 4.4 in the revised version.\n\n##  Relax Assumption 4.2:\nThanks for suggestion. Currently, to achieve the faster $\\tilde{\\mathcal{O}}(1/T)$ convergence rate, we do not find a clear way to have a good relaxation. The main challenges of multi-variable block optimization problems lie in its non-convex (non-convex-non-concave) structure and the coupling of multiple variable blocks. Therefore, a simple Lipschitz continuity assumption on internal function may not be helpful in obtaining a faster rate. However, for a slower rate, such as $\\tilde{\\mathcal{O}}(1/\\sqrt{T})$, it is possible and we leave it as a future work. We will discuss it in the revised version.\n\n## Written more Section 4.3:\nThanks for suggestion. We will introduce more background about Markov games, including its problem formulation, relation to convex and concave optimization, and current results.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2u34cQvJvl", "reviewer": "Reviewer_oxwM", "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.\nConvergence guarantees are established for the situations where the interval functions are either Lipschitz continuous of \"polynomial-like\". \nInfinite horizon reinforcement learning is shown two be a special case of this setting. Similar results are derived for the minimax setting.", "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, \n$\\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": "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.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* thorough theoretical analysis\n* method requires strictly less iterations than mirror descent\n* algorithm also works for unknown $\\gamma_i$\n* reinforcement learning application is an important one\n* extensive overview of related work", "weaknesses": "* 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$.  \n* 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)\n* 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?\n\n\n\nTypos:\n* Headline Algorithm 1: Mirior -> Mirror\n* line 206: depends -> depend", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and suggestions. We will respond to each of your comments individually in the following.\n\n## Algorithms Descriptions:\nThanks for your suggestion. We will use equations and sentences to introduce the algorithm. One randomly picks $t$ following probability means we output $x^t$ by uniformly sample from $(x^t)_{t=1}^T$.\n\n## Examples:\nFor minimization problems, we provide two examples of functions that simultaneously satisfy both the GQC condition and Assumption 3.3: a toy example (Example B.8 in Appendix B) and a simple neuron network over a simplex (Example 3.4 in Section 3.2). For minimax problems, In addition to infinite horizon two-player zero-sum Markov games, we have also demonstrated that general smooth convex-concave problems satisfy the GQCC condition and Assumption 4.2 (see Appendix C.3.2). Further examples await our future exploration.\n\n## Computational Costs: \nSince the MD method requires computing a $\\sum_{i=1}^d n_i$-dimensional gradient vector at each iteration, and Algorithm 1 also requires computing a $\\sum_{i=1}^d n_i$-dimensional internal function at each iteration, so Algorithm 1 does not need more additional computational costs.\n\n## Response to confuse about line 62-65: \nSorry for the confusion. We mean that If $\\{\\gamma_i\\}$ is known, then the update of our algorithm on each variable block will depend on $\\gamma_iF_i$ rather than solely on $F_i$. However, in many applications, $\\{\\gamma_i\\}$ is often related to the information of the optimal point (see Appendix B.3 for reinforcement learning problem, $\\gamma_i $ depends on the optimal solutions). Therefore, the computational costs of estimating $\\{\\gamma_i\\}$ may even exceed that to solve the optimization problems. This is our motivation to design adaptive algorithms without pre-known $\\{\\gamma_i\\}$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
## Experiments:
We add a simple simulation to validate our proposed algorithm. We do experiments on learning one single neuron network over
a simplex, which has been discussed in Example 3.4 in Section 3.2. The objective function is written as 

\begin{align}
f(p,P)=\frac{1}{2}E_{x,y}(\sum_{i=1}^m p_i\sigma(x^\top  P_{i})-y)^2
\end{align}

where $\sigma(\cdot)=\exp(\cdot), p\in \Delta_m$ and $P = (P_1,\cdots,P_m)\in\prod_{i=1}^m\Delta_d $ and the target $y$ given $x\in[-C,C]^{d}$ admits $y = \sigma(x^\top P_1^*)$ for some $P_1^*\in \Delta_d$. We set $m=20$, $d=20$, $C=4$ and the optimal solution $\mathbf{P}_1^*\in\Delta_d$ is a random probability density function. We compare the convergence performance of OMD\_IF (Optimistic Mirror Descent Method with internal functions, Algorithm 1), OMD\_G (Optimistic Mirror Descent Method with gradients, (Rakhlin et al., 2012)), MD (Mirror Descent Method with gradients), and AMD (Accelerated Mirror Descent Method with gradients, (Lan, 2020)). The experimental result is shown in the PDF file. From the figure, we can see that Algorithm 1 consistently shows superior convergence performance under various step size choices.

Meta-review: 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.
Decision: Accept (poster)