Connected Superlevel Set in (Deep) Reinforcement Learning and its Application to Minimax Theorems
Authors: Sihan Zeng
Thinh T. Doan
Justin Romberg
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement learning
superlevel sets
minimax optimization
robust reinforcement learning

Abstract: The aim of this paper is to improve the understanding of the optimization landscape for policy optimization problems in reinforcement learning. Specifically, we show that the superlevel set of the objective function with respect to the policy parameter is always a connected set both in the tabular setting and under policies represented by a class of neural networks. In addition, we show that the optimization objective as a function of the policy parameter and reward satisfies a stronger “equiconnectedness” property. To our best knowledge, these are novel and previously unknown discoveries.

We present an application of the connectedness of these superlevel sets to the derivation of minimax theorems for robust reinforcement learning. We show that any minimax optimization program which is convex on one side and is equiconnected on the other side observes the minimax equality (i.e. has a Nash equilibrium). We find that this exact structure is exhibited by an interesting class of robust reinforcement learning problems under an adversarial reward attack, and the validity of its minimax equality immediately follows. This is the first time such a result is established in the literature.

Connected Superlevel Set in (Deep) Reinforcement Learning and its Application to Minimax Theorems
Sihan Zeng
Thinh T. Doan
Electrical and Computer Engineering Georgia Institute of Technology
Electrical and Computer Engineering
Virginia Tech Blacksburg, VA 24061 t chinhdoan@vt. edu
Atlanta, GA 30318 $ @attchhhhhhhhhh...ocomooo edu
Justin Romberg
Electrical and Computer Engineering
Georgia Institute of Technology
Atlanta, GA 30318
Abstract
The aim of this paper improve the understanding of the optimization landscape for policy optimization problems in reinforcement learning. Specifically, we show that the superlevel set the objective function with respect to the policy parameter is always connected set both in the tabular setting and under policies represented by a class neural networks. In addition, we show that the optimization objective function of the policy parameter and reward satisfies stronger "equiconnect- edness" property. To our best knowledge, these are novel and previously unknown discoveries.
We present application of the connectedness of these superlevel sets to the deriva- tion minimax theorems for robust reinforcement learning. We show that any minimax optimization program which is convex on one side and is equiconnected on the other side observes the minimax equality (i.e. has a Nash equilibrium). We find that this exact structure is exhibited by an interesting class of robust reinforce- ment learning problems under an adversarial reward attack, and the validity of its minimax equality immediately follows. This is the first time such result established in the literature.
Introduction
Policy optimization problems in reinforcement learning (RL) are usually formulated as the maximiza- tion of non-concave objective function over convex constraint set. Such non-convex programs are generally difficult to solve globally, as gradient-based optimization algorithms can be trapped in sub-optimal first-order stationary points. Interestingly, recent advances in RL theory (Fazel al. 2018 Agarwal et al., [202]] Mei et al. 22200] have discovered a "gradient domination" structure in the optimization landscape, which qualitatively means that every stationary point of the objective function is globally optimal. An important consequence of this condition is that any first-order algorithm that converges a stationary point guaranteed find the global optimality.
In this work, our aim is to enhance the understanding of the optimization landscape in RL beyond the gradient domination condition. Inspired by Mohammadi al. (2021), FFathhulin and Polyak 2021 that discuss properties of the sublevel set for the linear-quadratic regulator (LQR), we study
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the superievel set of the policy optimization objective under a Markov decision process (MDP) framework and prove that is always connected.
As an immediate consequence, we show that any minimax optimization program which is convex on one side and is RL objective the other side observes the minimax equality. We apply this result to derive an interesting and previously unknown minimax theorem for robust RL. We also note that it unclear at the moment, but certainly possible, that the result on connected superlevel sets may be exploited to design more efficient and reliable policy optimization algorithms in the future.
1.1 Main Contribution
Our first contribution in this work is to show that the superlevel set of the policy optimization problem in RL is always connected under a tabular policy representation. We then extend this result the deep reinforcement learning setting, where the policy is represented by a class of parammtteeee neural networks. We show that the superlevel set of the underlying objective function with respect to the policy parameters (i.e. weights of the neural networks) is connected at all levels. We further prove that the policy optimization objective as function of the policy paraneter and reward is "equiconnected", which is a stronger result that we will define and introduce later in the paper. To the best of our knowledge, our paper is the first to rigorously investigate the connectedness of the superlevel sets for the MDP policy optimization program, both in the tabular case and with neural network policy class.
As a downstream application, we discuss how our main results can be used to derive a minimax theorem for a class of robust RL problems. We consider the scenario where an adversary strategically modifies the reward function to trick the learning agent. Aware of the attack, the learning agent defends against the poisoned reward by solving a minimax optimization program. The formulation for this problem is proposed and considered in Banihashem et al. [2021]. Rakhsha et al. [2020). However, as a fundamental question, the validity of the minimax theorem (or equivalently, the existence of a Nash equilibrium) is still unknown. We fill in this gap by establishing the minimax theorem as simple consequence of the equiconnectedness of the policy optimization objective.
1.2 Related Works
Our paper closely connected the existing works that study the structure of policy optimization problems in RL, especially those on the gradient domination condition. Our result also relates to the literature on minimax optimization for various function classes and robust RL. We discuss the recent advances in these domains to give context to our contributions.
Gradient Domination Condition. The policy optimization problem in RL is non-convex but obeys the special "gradient domination" structure, which has been widely used as a tool to show the convergence of various gradient- based algorithms to the globally optimal policy [Agarwal al.
2020
Mei et al.) 2020 Bhandari and Russo 2021 Zeng et al.) [222 Xiao 2022). In the settings of Yang et al. 2019 and entropy retropy-regularized MDP Mei al. 2020 Cen et al.
LOR
Fazel al. 2018
2022
Zeng et al.
2022 the gradient domination structure can be mathematically described by the
(PL) condition, which bears a resemblance to strong convexity but does not even imply convexity. It is known that functions observing this condition can be optimized globally and efficiently by (stochastic) optimization algorithms [Karimi et al.. 2016 Zeng et al.) 2021b] Gower et al., 2021]. When the policy optimization problem under standard, non-regularized MDP is considered, the gradient domination structure is weaker than the Pt. condition but still takes the form of upper bounding a global optimality gap by measure of the magnitude of the gradient (Bhandari and Russo| 2019 Agarwal et al., 2020 2021]. In all scenarios, the gradient domination structure prevents any stationary point from being sub-optimal.
may be tempting to think that the gradient domination condition and the connectedness of the superlevel sets are strongly connected notions or may even imply one another. For I-dimensional function (f R" + R with n = 1), it is easy to verify that the gradient domination condition necessarily implies the connectedness of the superlevel sets. However, when n 2 2 this is no longer true. In general, the gradient domination condition neither implies nor is implied by the connectedness of superlevel sets, which we illustrate with examples in Section 1.3 These two structural properties are distinct concepts that characterize the optimization landscape from different angles. This observation precludes the possibility of deriving the connectedness of the superlevel
2

---

sets in RL simply from the existing results on the gradient domination condition, and suggests that a tailored analysis is required.
Minimax Optimization & Minimax Theorems. Consider a function f x y + R on convex sets X. y. In general, the minimax inequality always holds
sup inf fzz y) - inf sup f(x =E yEy
yEy =EX
The seminal work Neumann 1928] shows that this inequality holds as an equality for matrix games where X' C Rm , C IR" are probability simplexes and we have f(x., y) = x. Ay given payoff matrix A E Rmxx. The result later gets generalized to the setting where X', y/ are compact sets, f(x, :) is quasi-convex for all x E X, and f(: y) is quasi-concave for all y E y [Fan 1953 Sion 1958 Much more recently, Yang et al. [2020] establishes the minimax equality when f satisties the two-sided PE. condition. For arbitrary functions f. the minimax equality need not be valid.
The validity of the minimax equality is essentially equivalent to the existence of global Nash equilibrium vx","") such that
[a, v²" S f(x",8") S f(x", .9), Ve E X, EY.
The Nash equilibrium (x* . )* is point where neither player can improve their objective function value by changing its strategy. In general
nonconcave settings where the global Nash equilibrium may not exist, alternative approximate local/global optimality notions are considered [Daskalakis and Panageas 2018 Nowiched et al. 2019 Adolphs et al. 2019 Jin et al. 2020].
Robust Reinforcement Learning. Robust RL studies finding the optimal policy in the worst-case scenario under environment uncertainty and/or possible adversarial attacks. Various robust RL models have been considered in the existing literature, such 1) the learning agent operates under uncertainty in the transition probability kernel [Goyal and
[022]] Li et al.) 2022]
Panaganti and Kalathil 2022 Wang et al.) 2023). 2) an adversary exists and plays two-player zero-sum Markov game against the learning agent (Pinto et al. 2017 Tessler et al.) 2019]. 3) the adversary does not affect the state transition but may manipulate the state observation Havens et al. 2018, Zhang et al.)
2020 4) there is uncertainty or attack only on the reward (Wang et al.) 2020
Banihashem et al.) 2021 Sarkar et al.) 2022]. 5) the learning agent defends against attacks from a population of adversaries rather than single one [Vinitsky et al.] 2020 A particular attack and defense model considered later our paper is adapted from Banihashem et al. (202T).
Other Works on Connected Level Sets in Machine Learning. Last but not least, we note that our paper is related the works that study the connectedness of the sublevel sets for the LQR optimization problem FFakhhulin and Polyak| [222]] and for deep supervised learning under a regression loss Nguyenn 2019]. The neural network architecture considered in our paper is inspired by and similar to the one in N Nguyen 2019). However, our result and analysis on deep RL are novel and significantly more challenging to establish, since 1) the underlying loss function in Nguyen 2019 is convex, while ours is con--c policy optimization objective, 2) the analysis of Nguyen [2099] relies critically on the assumption that the activation functions are uniquely invertible, while we use a non-uniquely invertible softmax activation function to generate policies within the probability simplex.
1.3 Connection between Gradient Domination and Connected Superlevel Sets
We loosely use the term "gradient domination" to indicate that differentiable function does not have any sub-optimal stationary points. In this section, we use two examples to show that the gradient domination condition in general does not imply get implied by the connectedness of the superlevel sets. The first example is a function that observes the gradient domination condition but has a disconnected set of maximizers (which implies that the superlevel is not always connected).
Consider f : [-4, 4| [-2,0] +
f(x, = { (14x,))-(4- - -((=)))=(---1)-33((( -1--------------------00----
0.02 10) xx2), for x 2 (1 --
+ 10) 10:00-20 x²), else
It is obvious that the function is symmetric along the line x 0 and that fi (0,y) fz y) for all
y E |-2, 0J. Computing the derivatives of fi and f2 with respect to x, we have
vzfi(z,v) = -3(r - 1)2 + 3 0.04m
V vaf((z,)) = 3(x + - 3 0.04 3
3

---

We can again verify V vzfi(0. V2,2(0., y) for all which implies that the function f is everywhere continuous and differentiable. Visualization of in Fig. Talong with simple calculation (solving the system of equations V=
0 and vzf(x, y) 0) show that there are only two stationary points of / on [-4,4] [-2, 0j. The two stationary points are (3.05, -1.12) and (-3.05, 1.12), and they are both global maximizers on this domain, which means that the gradient domination condition observed. However, the set of maximizers {(.005, 1.12), (-3.05, 3.11)) is clearly disconnected.
We next present a function that has connected superlevel sets at all level but does not observe the gradient domination condition (i.e. has sub-optimal stationary points).
30
15
(x.y)
g(x.y)
0.
-10
-15
13
Figure I: Visualization of Functions f (Left) and (Right)
Consider g R² R defined
g(x, v) -x 2 4(x² + y²2)
This is a volcano-shaped function, which we visualize in Fig. [ It is obvious the superlevel set {(x, v) g(x, y) 2 }} always either 2D circle (convex set) or a donut-shaped connected depending on the choice of X. However, the gradient domination condition does not hold as (0, 0) is a first-order stationary point but not global maximizer (it actually a local minimizer).
Outline of the paper. The rest of the paper is organized as follows. In Section 2 we discuss the policy optimization problem in the tabular setting and establish the connectedness of the superlevel sets. Sec- tion generaliizes the result to a class of policies represented by over-parane weer-paaameterized neural networks. We introduce the structure of the neural network and the definition of super level sets in this context, and present our theoretical result. In Section we use our main results on superlevel sets to derive two minimax theorems for robust RL. Finally, conclude Section with remarks on future directions.
2 Connected Superlevel Set Under Tabular Policy
We consider the infinite-horizon average-reward MDP characterized by M (S,,,,,),,) We use S and A to denote the state and action spaces, which assume are finite. The transition probability kernel is denoted by S x A As. where As denotes the probability simplex over S. The reward function regarded vector in [AI) We use pa RR58 to represent the state transition probability matrix under policy π E AS, where A is the collection probability simplexes over A across the state space
S A J0, U,] is bounded for
positive constant U, and also be
Σ P(s' (s,a)T(a Vs',sES. a
We consider the following ergodicity assumption in the rest of the paper, which is commonly made in the RL literature [Wang 2017 Wei al. 2020 Wu et al. 2020).
Assumption Given any policy w, the Markov chain formed under the transition probability matrix pa is ergodic, i.e. irreducible and aperiodic.

---

Let Ux E As denote the stationary distribution of the states induced by policy и. As consequence of Assumption [ the stationary distribution μ4 is unique and uniformly bounded away from under any æ. In addition, /Mr is the unique eigenvector of pa with the associated eigenvalue equal to 1, i.e. 1'm 1. Let 7 AsxA denote the state-action stationary distribution induced by n, which can be expressed as
(n a) (s) s).
(2)
We measure the performance of a policy и under reward function by the average cumulative reward Jr
= r(sk (x)
J (T(
lim
LLseur (r(s au)] (r(s.a)
The objective of the policy optimization problem is to find the policy that maximizes the average cumulative reward
max (x)...
TEAX
The superlevel set of J, is the of policies that achieve value function greater than equal to a specified level. Formally, given X E R, the A-superlevel set (or superlevel set) under reward is defined as
Uxr { E A (,(T) 2 Aj.
The main focus of this section is study the connectedness of this Ux which requires to formally define connected set.
Definition A set U connected for any x, there exists a continuous map p :00, 2 such that p(0) = x and p(1) =
We say that function is connected if its superlevel sets are connected at all levels. We also introduce the definition of equiconnected functions.
Given two spaces and y, the collection of functions {fy X - RJbey is said to be equiconnected if for every Iı, 22 E X, there exists a continuous path map p: [0, 1] X such that
Definition
p(0) = 21, p(1) = I2, fo(p(a)) 2 ((nn)
for all [0, and y y.
Conceptually, the collection of functions {fy X PEy being equiconnected requires 1) that fo(+) is connected function for all y E ) (or equivalently, the set {a X' fy(x) 2 X} is connected for all X R and ))) and 2) that the path map constructed to prove the connectedness
of (x X (z) 2 A} is independent of y.
We now present our first main result of the paper, which states that the superlevel set Ux,r always connected.
Theorem Under Assumption 1 the superlevel set Uxrr is connected for any E RR and E [RSSIA In addition, the collection of functions (J,(.) : A + R)EERISIXIA) is equiconnected.
Our result here extends easily the infinite-horizon discounted-reward setting since a discounted- reward MDP can be regarded as an average-reward one with a slightly modified transition kernel [Kondal 2002).
The claim in Theorem I on the equicomeectedness of [J.)reRIsiia is a slightly stronger result than the connectedness of Ur and plays important role in the application minimax theorems discussed later in Section
We note that the proof, presented in Section A. of the appendix, mainly leverages the fact that the value function J,-(T) is linear in the state-action stationary distribution 7h and that there a special connection (though nonlinear and nonconvex) between f.x and the policy which we take advantage
5

---

of to construct the continuous path map for the analysis. Specifically, given two policies TT 72 with (T)). J, (T²) 2 we show that the policy Ta defined as
(s) 8) + (1 amju (S)
Va E [0, 1]
Offer (s) + a))
is guaranteed achieve J, (Ta) X for all E [0, 1].
Besides playing key role in the proof Theorem 1 our construction of this path map may inform the design of algorithms in the future. Given any two policies with certain guaranteed performance, we can generate a continuum of policies least as good. As a consequence, if find two optimal policies (possibly by gradient descent from different initializations) interpolating optimal policies. If the agent has a preference over these policy (for example, to minimize certain energy like in Hi control, or if some policies are easier to implement physically), then the selection can made on the continuum of optimal policies, which eventually leads to more preferred policy.
generate range of
3 Connected Superlevel Set Under Neural Network Parameterized Policy
In real-world reinforcement learning applications, is common to use a deep neural network to parameterize the policy [Silver et al. 2016 Arulkumaran et al. 2017]. In this section, consider the policy optimization problem under a special class of policies represented by an over-parameterized neural network and show that this problem still enjoys the important structure the connectedness of the superlevel sets - despite the presence of the highly complex function approximation. Illustrated in Fig. the neural network parameterizes the policy in very natural manner which matches how neural networks are actually used practice.
festure
neural network Becollection of all weights
poliey cistribution space ma (
vector
gener generate output (softim function appiled last layer)
0.7
abstracted by
input
0.05
0.15
Figure Neural Network Policy Representation
Mathematically, the parameterization with feature vector (08) E Rd, which in practice is usually carefully selected to summarize the key information of the state. For state identifiability, assume that the feature vector of each state is unique, i.e.
be described follows. Each state S is associated
o(s) + Φ(s'), ss E and s'.
To map a feature vector ((s) to policy distribution over state we employ L-layer neural network, which in the km layer has weight matrix W₂ R 1xm; and bias vector by R with no and 1y [A]. For the simplicity of notation, we use Og to denote the space of weight and bias Qr We use 0 to denote the collection
parameters (W;. k. bạ) of layer k. and we write 22
of the weights and biases
= ((W, b1), (Wz, bn.)) E EΩ
We use the same activation function for layers 1 through L - 1, denoted by a : - R, applied in an element-wise fashion vectors. To ensure that the output of the neural network valid probability distribution, the activation function for the last layer is softmax function, denoted by ab: IR|A| + AA, i.c. for any vector v E RlA
( Al P=1 exp(ve)
(10),
-i= = IA).
Σ

---

With E Rd as the input to neural network with parameters 8 we use (o) output of the network at layer k. For k = 1.... ,. (v) ) is computed as
RR* to denote the
(W.T b1)
k = 1 k = 2, 3, ..... L k == L.
f2(2)
σ W. f2) + by) [W I1-1(1) - by)
(4)
The policy Ny RISiXAA parametrized by 0 is the output of the final layer:
T 8) - ((((s) AA. E
Our analysis relies two assumptions about the structure of the neural network. The first concerns the invertibility of (-)) as well as the continuity and uniqueness of its inverse, which can be guaranteed by the following:
Assumption a is strictly monotonic and (R) = R. In addition, there do not exist non-zero sealars
(R)
{pis () with q: + 9j. Vi + such that for some (xx) -i= P:o q:), Ya R.
We note that this assumption holds for common activation functions including leaky-ReLU and parametric ReLU [uu et al. 2015).
Our second assumption is that the neural network is sufficiently over-parameterized and that the number parameters decreases with each layer.
Assumption The output of the first layer is wider than 2|S), and the width of the network decreases over the layers, i.e.
n1 2 2|5), and n1 > >12 > > 7n = |A
Neural networks meeting this criteria have number of weight parameters that is larger than the cardinality of the state space, making them impractical for large [S]. While ongoing work seeks to relax remove this assumption,
point out that similar ser-parramtterzzaiinn assumptions
critical and very common in most existing works on the theory of neural networks [Zou and Gu 2019
Nguyen 2019
Liu al. 2022 Martinetz and Martinetz) 2022 Pandey and Kumar
2023
The >-superlevel set of the value function with respect to under reward function r is
uS. A {0 e Ω (,(T)) 2 A].
Our next main theoretical result guarantees the connectedness of U
Theorem Under Assumptions the superlevel set U is connected for any E R. In addition, with (0) & J, (TT), the collection functions (Jr.a(-) Ω R is equiconnected.
The proof of this theorem is deferred the appendix. Similar to Theorem [ the claim in Theorem on the equiconnectedness of [Jr. ( is again stronger than the connectedness of U and needs to be derived for the application to minimax theorems, which we discuss in the next section.
Application to Robust Reinforcement Learning
In this section, we consider the robust RL problem under adversarial reward attack, which can be formulated convex-nove noncooev minimax optimization program. In Section 4.1 we show that the minimax equality holds for this optimization program in the tabular policy setting and under policies represented by a class of neural networks, as a consequence of our results in Sections 2 and 3 To our best knowledge, the existence of the Nash equilibrium for this robust RL problem has not been established before even the tabular case, A specific example of this type of robust RL problems given in Section 4.2
7

---

4.1
Minimax Theorem
Robust RL in general studies identifying a policy with reliable performance under uncertainty or attacks. A wide range of formulations have been proposed for robust RL (which we reviewed in details in Section I.2]. and an important class formulations takes the form of defending against an adversary that can modify the reward function in convex manner. Specifically, the objective of the learning agent can be described as solving the following minimax optimization problem
max min J,(x), TEAS rEC
(5)
where C is some convex set. It is unclear from the existing literature whether minimax inequality holds for this problem, i.e.
max min J+ = min max (r(),, reC rE4x
(6)
TEAR rEC
and we provide a definitive answer to this question. We note that there exists classic minimax theorem on a special class convex-nonconcave functions [Simons 1995], which we adapt and simplify as follows.
Theorem Consider a separately continuous function f : X y + R, with y being a convex, compact set. Suppose that f(x.)) ) is convex for all E X. Also suppose that the collection of functions (f(,9) is equiconnected. Then, we huve
sup min f(x,y) min sup (z. #EX vEy
DE zE
Theorem 3 states that the minimax equality holds under two main conditions (besides the continuity condition, which can easily be verified to hold for Jz(z)). First, the function f(x, y) needs to be convex with respect to the variable y within a convex, compact constraint set. Second, ff (z, y) needs to have connected superlevel set with respect to and the path function constructed to prove the connectedness of the superlevel set is independent of y. As we have shown in this section and earlier in the paper, if we model (T) by f(x, y) with π and corresponding are observed by the optimization problem (5) which allows us to state the following corollary.
and y. both conditions
Corollary Suppose that the Markov chain M satisfies Assumption 7 ergodicity. Then, the minimax equality (6) holds.
When the neural network presented in Section is used to represent the policy, the collection of functions {Jr.st }r is also equiconnected. This allows us to extend the minimax equality above to the neural network policy class. Specifically, consider problem (5) where the policy no is represented by the parameter 8 E Ωl as described in Section 3 Using f (x. y) to model J, (Tp) with x and y mirroring 0 and r, we can easily establish the minimax theorem this case as consequence of Theorem and
Corollary 2 Suppose that the Markov chain M satisfies Assumption 7 on ergodicity and that the neural policy class satisfies Assumptions 2
Then, we have
sup min (Te) min sup Jr (TT). rEC BEn
(8)
EEN rEC
Corollary M [ndd establish the minimax equality (or equivalently, the existence of the Nash equilib- rium) for the robust reinforcement learning problem under adversarial reward attack for the tabular and neural network policy class, respectively. To our best knowledge, these results are both novel and previously unknown in the existing literature. The Nash equilibrium is important global optimality notion minimax optimization, and the knowledge on its existence can provide strong guidance on designing and analyzing algorithms for solving the problem.
4.2 Example Defense Against Reward Poisoning
We now discuss particular example of (5). We consider the infinite horizon, average reward MDP M = (S, A, r)) introduced in Section 2 where is the true, unpoisoned reward function. Let ds denote the set of deterministic policies from S to A. With the perfect knowledge of this MDP, an attacker has target policy nt E _ldet and tries to make the lcarning agent adopt the policy by
8

---

manipulating the reward function. Mathematically. the goal of the attacker can be described by the function Attack(r, TT. Et) which returns poisoned reward under the true reward r, the target policy tt and pre-selected margin parameter et 2 0. Attack(r, Ri. <t) is the solution to the following optimization problem
Attack(r,
argmin
Σ #ES,
(r (.,,a))(s,,a))
s.t.
(T+) 2 (T) +
VT 1I TT
In other words, the attacker needs to minimally modify the reward function to make "t the optimal policy under the poisoned reward. This optimization program minimizes a quadratic loss under finite number of linear constraints and obviously convex.
The learning agent observes the poisoned reward Ft = Attack(r, m (4) rather than the original reward r. As noted in Banihashem al. (202T]. without any defense, the learning agent solves the policy optimization problem under rt to find Tt, which may perform arbitrarily badly under the original reward. One way to defend against the attack is to maximize the performance of the agent in the worst possible case of the original reward, which leads to solving minimax optimization program of the form
max min (T) s. t. Attack(r', Tt, maacckrr,,,,ee (4) = Tt. mEAx p'
(10)
When the policy is fixed, (10)
reduces to
min (T) t. Autack(r', -4, rt.
(11)
With the justification deferred to Appendix D
we point out that (11 consists of linear objective function and a convex (and compact) constraint set, and is therefore convex program. On the other side, when we fix the reward r', 10 reduces to a standard policy optimization problem.
We are interested investigating whether the following minimax equality holds.
max REAS r Actack((" Ko
min
(T)
min p':Attack("' (e)) TEA
max J,- (TT)
(12)
This is a special case of 55 with = fr' Attack (r's ++) = rt). which can be verified to
convex set. Therefore, the validity of (12) directly follows from Corollary [ Similarly, in the setting of neural network parameterized policy we can establish
max
Jr (T() AEN p':Attack(("' (t.))))
min
min
max J, (T²) BE12
r':Attack("" (1.6))
as result of Corollary 2
Conclusions & Future Work
We study the superlevel set of the policy optimization problem under the MDP framework and show that it is always connected set under tabular policy and for policies parameterized by a class of neural networks. We apply this result to derive a previously unknown minimax theorem for a robust RL problem. An immediate future direction of the work is to investigate whether/how the result discussed in this paper can be used to design better RL algorithms. In Faathullin and Polyak| [202]] }, the authors show that the original LQR problem has connected level sets, but the partially observable LQR does not. It is interesting to study whether this observation extends to the MDP setting, i.e. the policy optimization problem under partially observable MDP can be shown have disconnected superlevel sets.
Acknowledgement
This work was supported in part by the NSF AI Institute AI4OPT, NSF 2112533.

---

References
Leonard Adolphs, Hadi Daneshmand, Aurelien Lucchi, and Thomas Hofmann. Local saddle point optimization: A curvature exploitation approach. In The 22nd International Conference Artificial Intelligence and Statistics, pages 1866495. PMLR, 2019.
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in markov decision processes. In Conference on Learning Theory, pages 64 66. PMLR, 2020.
Alekh Agarwal, Sham M Kakade, Jason D Lec, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):4431-4500 2021.
Kai Arulkumaran, Mare Peter Deisenroth, Miles Brundage, and Anil Anthony Bharath. Deep reinforcement learning: A brief survey. IEEE Signal Processing Magazine, 34(6):26-38, 2017.
Kiarash Banihashem, Adish Singla, and Goran Radanovic. Defense against reward poisoning attacks in reinforcement learning. arXiv preprint arXi::2002.0577, 2021.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. arXiv preprint arXiv: (ete::9000000000 2019.
Jalaj Bhandari and Daniel Russo. On the linear convergence of policy gradient methods for finite mdps. In International Conference on Artificial Intelligence and Statistics, pages 2386-2394.
PMLR, 2021.
Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 70(4): 2563-2578, 2022.
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. Advances neural information processing systems, 31, 2018.
J-CI Evard and Farhad Jafari. The set of all m x n rectangular real matrices of rank r is connected by analytic regular ares. Proceedings of the American Mathematical Society, 120(2):413-419, 1994.
Ky Fan. Minimax theorems. Proceedings of the National Academy of Sciences, 39(1):42 47, 1953.
Ilyas Fatkhullin and Boris Polyak. Optimizing static linear feedback: Gradient method. SIAM Journal on Control and Optimization, 59(5):3877-3911 2021.
Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence policy gradient methods for the linear quadratic regulator. In International conference on machine learning, pages 1467-1476. PMLR, 2018.
Robert Gower, Othmane Sebbouh, and Nicolas Loizou. Sgd for structured nonconvex functions: Learning rates, minibatching and interpolation. In International Conference on Artificial Intelli- gence and Statistics, pages 1315-1323, PMLR, 2021.
Vineet Goyal and Julien Grand-Clement, Robust markov decision processes: Beyond rectangularity. Mathematics of Operations Research, 2022.
Aaron J Havens, Zhanhong Jiang, and Soumik Sarkar. Online robust policy learning in the presence of unknown adversaries. arXiv preprint arXiv:1807.06064, 2018.
Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex-nooncocave minimax optimization? In International conference on machine learning, pages 4880-4889. PMLR, 2020.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the Polyak-oojasiewiez condition. In Machine Leurning and Knowledge Discovery in Databases: European Conference, ECML. PKDD 2016, Riva del Garda, Italy, September 19-23, 2016. Proceedings, Part I 16, pages 795- 1. Springerr 2016.
10

---

Vijay R. Konda. Actor-critic algorithms. PhD thesis, Massachusetts Institute of Technology. 2002.
Yan Li, Tuo Zhao, and Guanghui Lan. First-order policy optimization for robust markov decision process. arXiv preprint arXiv:2209.1053 2022.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59: 85-116, 2022.
Julius Martinetz and Thomas Martinetz. Highly over- paramerraeeee classifiers classisse generalize since bad solutions are rare. arXiv preprint arXiv:2211.00 1.05570, 2022.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pages 6820-6829. PMLR, 2020.
Hesameddin Mohammadi, Armin Zare, Mahdi Soltanolkotabi, and Mihailo R Jovanović. Convergence and sample complexity of gradient methods for the model-free linear- quaar-qu regulator problem. IEEE Transactions on Automatic Control, 67(5):2435-244 2450, 2021.
J Neumann. Zur theorie der gesellschaftsspiele.. Mathematischhe annalen, 100(1):295-333) -22-20, 1928.
Quynh Nguyen. On connected sublevel sets in deep learning. In International Conference on Machine Learning, pages 4790-4799. PMLR, 2019.
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. Advances in Neural Information Processing Systems, 32, 2019.
Kishan Panaganti and Dileep Kalathil. Sample complexity of robust reinforcement learning with a generative model. In International Conference on Artificial Intelligence and Statistics, pages 9582 9602. PMLR, 2022.
Eshan Pandey and Santosh Kumar. Exploring the generalization capacity of over-parameterized networks. International Journal of Intelligent Systems and Applications in Engineering, 11(Is): 97-112, 2023.
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforce- ment learning. In International Conference Machine Learning, pages 2817-2826. PMLR, 2017.
Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla. Policy teaching via environment poisoning: Training thining-timee time adversarial attacks against reinforcement learning. In International Conference on Machine Learning, pages 7974-7984. PMLR, 2020.
Anindya Sarkar, Jiarui Feng, Yevgeniy Vorobeychik, Christopher Gill, and Ning Zhang. Reward delay attacks on deep reinforcement learning. arXiv preprint arXiv:2209. 035400, 2022.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schriuwieser, Joannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484-48, 2016.
Stephen Simons. Minimax theorems and their proofs. In Minimax and applications, pages 1-23. Springer, 1995.
Maurice Sion. On general minimax theorems. Pacific Journal of mathematics, 8(1):171-176, 1958.
Chen Tessler, Yonathan Efroni, and Shie Mannor. Action robust reinforcement learning and applica- tions in continuous control. In International Conference on Machine Learning, pages 6215-6224. PMLR, 2019.
Eugene Vinitsky, Yuging Du, Kanaad Parvate, Kathy Jang, Pieter Abbeel, and Alexandre Bayen. Robust reinforcement learning using adversarial populations. arXiv preprint arXiv:2008.01825 2020.

---

Jingkang Wang, Yang Liu, and Bo Li. Reinforcement learning with perturbed rewards. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 6202-6209, 2020.
Mengdi Wang. Primal-dual и learning: Sample complexity and sublinear run time for ergodic markov decision problems. arXiv preprini urXiv:1710.06100 2017.
Yue Wang, Alvaro Velasquez, George Atia, Ashley average-reward markov decision processes. arXiv preprint arXiv:2301.00858, 2023.
and Shaofeng Zou. Robust
Chen-Yu Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, Hiteshi Sharma, and Rahul Jain. Model- free reinforcement learning in infinite-horizon average-reward markov decision processes. In International conference on machine learning, pages 10170-10180, PMLR, 2020.
Yue Frank Wu, Weitong Zhang, Pan Xu, and Quanquan Gu. A liiie--time analysis of two time-scale actor-critic methods. Advances in Neural Information Processing Systems, 33: 13:17717-17628 2020.
Lin Xiao. On the convergence rates of policy gradient methods. The Journal of Machine Learning Research, 23(1):12887-122) 12922,, 2022.
Bing Xu, Naiyan Wang, Tianqi Chen, and Mu Li. Empirical evaluation of rectified activations in convolutional network. arXiv preprint arXiv:1505.00853 2015.
Junchi Yang. Negar Kiyavash, and Niao He. Global convergence and variance reduction for class of nonconvex-noncomcave minimax problems. Advances in Neural Information Processing Systems, 153-1165,, 2020.
Zhuoran Yang, Yongxin Chen, Mingyi Hong, and Zhaoran Wang. Provably global convergence of actor-critie: case for linear quadratic regulator with ergodic cost. Advances neural information processing systems, 32, 2019.
Sihan Zeng, Malik Ageel Anwar, Thinh T Doan, Arijit Raychowdhury, and Justin Romberg. A decentralized policy gradient approach to multi-task reinforcement learning. In Uncertainty in Artificial Intelligence, pages 1002-1012. PMLR, 2021a.
Sihan Zeng, Thinh T Doan, and Justin Romberg. two-time-scale stochastic optimization framework with applications control and reinforcement learning. arXiv preprint arXiv:2 1cXiv:2109.14777 2021b.
Sihan Zeng, Thinh Doan, and Justin Romberg, Regularized gradient descent ascent for two-player zero-sum markov games. Advances Neural Information Processing Systems, 35:34546-3453 2022.
Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Mingyan Liu, Duane Boning, and Cho-Jui Hsieh. Robust deep reinforcement learning against adversarial perturbations on state observations. Advances in Neural Information Processing Systems, 33:21024-21033 2020.
Difan Zou and Quanquan Gu. An improved analysis of training over- over-paramett parameterized deep neural networks. Advances in neural information processing systems, 32, 2019.
12

---

A Proof of Theorems
A.1 Proof of Theorem
We note that there exists a bijective map between x and jä, where Ja is induced by æ according to and conversely
T(a 8) (r, 0)
(s,
(13)
(x(() EeEA (8,
provided that Ne, (s) * O, which is guaranteed by Assumption | the path map.
Eq. (13) inspires the construction of
To prove that the superlevel set is connected, show that for any À E R and T1 T2 Ur there exists a continuous path map : [0, + Ux such that p(0) = ιı and p(1) = T2. We now construct the path function p by defining
p(a)(a 8) apn (5) (a 5) (1 (1-11))10 am (s) T2
Opt (8) + (1 am)
which is well-defined for all E [0, 1] as Um, (s), (s) are positive for all E S. Note that the construction of p does not depend on the reward function r. easy to see that p(a) E A is
continuous in a. To stress that p(a) is in the policy space, we denote =p(a).
Recall the definition of the transition probability matrix in T We define B E R|S| as
B = p (oup + (1 - a))
Each entry of B can be expressed as
B(s') Σ P(s' s,a) s) (aper, (s) + a) (s))
Σ P(s' (8,0) 0f (s) 8) + (1 02) PTm (TZ(a (aifm (s) (1
ape. (s) + (1 - a (s)
8,a
Σ P(s' (3.0)amm (6)=z(a| (8) Σ P(s' |s, a)ur (8)=z(a)
9,0
5,a
a
Σ
pat Lll s (8) + a) Σ
Por pplallm (8)
8.a
8.0
aafar (s') + (1-a)uaaa
which implies
p (app + (1 a))T)) aptn + (1 am)
(14)
consequence Assumption iis that for any policy π there is a unique eigenvector pa associated with the eigenvalue 1, and this eigenvector (properly normalized) is the stationary distribution. Therefore, (14) means that ojta, + +(1 - a)Ma has to be the stationary distribution under policy n.. i.e.
Nta cpti + (1 a))
As result, for all s E S, a A
Nro (s, a) = UT., (a) (8)
(apm (s) (1 a) (s)) Oftm (8) () a)) (s) axpir (s) + (1 - a) (8)
app (5) (a 8) + (1 a)M (s)TT(a = aijn (5, a) + (1 - a)),
Note that J,(T) = ESESIEd ()) a). Since Tिi Trz E Ur we know
Σ a( (8, 21,
Σ
r(s, (s,,))mm (8,, a) 2 A.
sES
13

---

which implies Ta r. So far we have verifed that the constructed path map p is indeed continuous and maps a E [0, 1] Uxr with p(0) #1 and p(1) æ2. This concludes the proof on the connectedness of the superlevel set M, The claim on the equiconnectedness simply follows from Therefore, we have for any a E [0,
(T()a)= E r(s, a) (5,
E r(s, a) (aftir, (8, + (1-a))1a a)ting (s, a)) 2 A,
sES,aEA
sES,aEd
the fact that the construction of the path map p does not depend on the reward function.
A.2 Proof of Theorem
We use X to denote the concatenation of the feature vectors across all states
((1))
((52) T
E R Sixd
(+sss)
In the analysis we may apply the softmax function up to a matrix in row-wise fashion. Specifically, for any n 2 and matrix M E [Rnx|A|, we have
exp(Mr.)
(M)
=i= I,
exp(M
The softmax operator vi can be inverted up additive constant factor. We define tine for any matrix M E [RaX|4
Vino (M) log(M + cs Vi,j,
with e, determined such that Σ/ vine (M) = 0. Note that oiee is right inverse of v/, i.e. (h (M)) M for all matrix A.
When the input to a neural network with parameter is the feature table X, we denote the output of layer by Ft RlS|xax, According to 4.. F can be expressed as
XW + 11 F Wx b)
k =
F2
k = 2, 2.., L -
W2 - 1 b))
k == L
where 1|st is the all-one vector of dimension |S] x 1. Note that F% E [R|S| is the policy table produced by the neural network, i.e. =
The proof of Theorem relies on the following intermediate results, which now present. The proof of Proposition [ can be found in Appendix B
Proposition 1 Ifrank(X). = |S), then under Assumption and the superlevel US is connected for all À E IR.
Let (X, W, V) E R x R x Ra1 x Ruixa, Let 2 = o + ((S V. Suppose has distinct rows. Then, under Assumption and 3 there exists continuous path map xna x with c(A) = (W ()), b b(A), V()) such that
Lemma
e: 10 1 + RnoXnn x (Rmh x (R
()) (W.b.V.
2) a (XW(A) 1 B(A)T) V(A) = Z,VX [0.1].
3) rank (a (1 1( N.
Lemma 2 Lef (X, W, V. W E Siixna R x R Xna x Xn. Suppose rank(o(XW)) (S] and rank(a
(S) Then, under Assumption 2 and 3 there exists a continuous path map
: [0, Km1 x [m, x with c(A) (W (()) such that
14

---

1))(0 = (W.V),
a (XW())) V(A) V, [0.
3) W(1)= = =
To prove Theorem it suffices show that for any 0, (W1,, (1,)=b1.)f11 E UL, and 02 (W2,, 12.1)/11 E U there exists a connected path that is completely within 2
Applying Lemma | with (X, W1,1, b1,1, W1,2) and (X, W2,1. b2,1, W2,2), the problem simplifies to showing the existence of continuous path within Uh that connects
0 ((W [W 1111, (W b1.2), (Wi,1, b1.)(=3)
and
82 ((W 66 1), (W2, 11,2), (W2, by (23))
such that
rank = rank rank FF()) = |S|-
Then, we can apply Lemma 2 with ss)) [W7.T. 81,1" [T Wi,2: [W 1221 to show that there
is a continuous path between 0f and 0f with 0r = ((W2, 12,1); (W b1,2), (W1,; b1,))=a)) such that
rank(I=")) = rank(4 1S
As a consequence, now we simply have to show that 0r and 0/ is connected by a continuous path within 4r,-
Note that of and 8% have identical first layer parameters and thus the same first layer output, which is full rank. This allows us to treat the layers from 2 to L as a new network and apply Proposition (which requires the input to be full rank) to the new network to guarantee that there exists continuous path map e [0, 1] + Q2 x ... x Q2 such that c(0) ((W b1,2), (W1,,, b1,)) c(1) = ((222,, 212),, 2W2,1 by b2.)) and min (J,((J,TTO) ), J. (moz)) s J. (,,,), S max J
I
for all a E [0, 1]. This implies that there is indeed a continuous path between 0f and 022 within &
Similar to the proof of Theorem [ the claim the connectedness simply follows from the fact that the construction of the path map does not depend on the reward function.
B Proof of Proposition 1
For each layer of the neural network h = 1.... L, we define 22 S Sz be the set of weights Wa and biases by of layer k such that Wa is full rank, i.e.
02 (WWk,b)) bw) E St : We is full rank).
(15)
We denote 92" = 22 x O7
227 Next, we introduce the following lemmas in aid of the analysis.
Condition 1 Given 0 (W,, b W, has full rank for every E [2, L).
Lemma Under Assumption 2 and Condition
1 given any [2, L] and matrix R|S|xm,
there exists continuous map Q2 ... 22
R
S xns + S2 such that
1) Given b2), ..., (W..,, bx), F) E 22 ... 22 x RlS) we have
F (((W P).
2) For any 8r (Wttbb)fe Ω x 22 ... Di there exists continuous path map p [0, U2 22 ... x Ri such that p(0) 0-, p(1) (b(WW,,b)) Ff (Wt.b) b))=z) and EP(()) FL, for all [0.
15

---

Lemma 4 Given two connected sets A C Rm and B S R the set {ab a E A. E B) is connected. Given two connected sets A, B S Rmxx the set {a + b bla E A, B} is connected.
Lemma 5 Under Assumption for any Ω there exist 0 E S and continuous path map p: [0, 11 + St such that p(0) = 0, p(1) = 0", and popaa) =F all a E [0,
Lemma nf < m, then the set F {F' R raak((P) (F) ni is connected. In other words,
given F1, F2 E F, there exists a continuous path map [0, 1] + F such that q(0) Fi and (1) P2.
Fix a À E IR. To show the superlevel set is connected, it suffices to show that for any 01, 02 E uRR there exists continuous path between them that is completely in 2
Without any loss of generality, we can safely assume that both 01 = (W1,, b1,1)==1 and 02 (W2,,, 12,1)==1 satisfy Condition [ since otherwise by Lemma we can find continuous path from
0i and O2 that leads one satisfying Condition We denote the policies parameterized by 0,, 02 as Ti 22, i.e.
mi F2:
T2 FL.-
By Lemma 3 there is continuous path from 0 to 0 00/ where we define
0 = (n ((W1,, b,:) m1) (W1.,, (W.11,b1.)f=2 b11)(=))
and 8 = (n (WW2,, 12:)) m2) (W2,1, (W,2,,22,((- b2.1)=2)
Now, we just have show that there exists continuous path between 0f and 032 that is completely
within UR By Lemma 6 we know that for 1 = 2,.., I, there exists a continuous path map
[0, 1] + 22 such that (1) = W1,1 and (0) = W2,1. Then, we construct the map g [0, 1] + Ω (()) = (h((ara),,b1, + (1 - a)62.)) R1), (1 abL. + (1 (1)621)/222
Va E [0, 1].
is obvious that g a continuous map h, 92, ..., ar are continuous. In addition, F*(a) J for all [0, 1], and ((1) = 8,. We define
8" = q(0)= = (n (WWa, bew), m1) (W2,1, b2.))=2)
Now our aim simplifies to finding continuous path between 0% and 032 that is completely U To show that this path exists, we construct a continuous map pt [0, 1] - follows
t(a) hh (Wo.. b2 ( #a) (W2,,,
Va E j0, 1],
where से is defined entry-wise
(a 8) aftir (s)TT(( (a () + (1 am) (T) s)
Ofti (s) + (1 - a)) (8)
can be seen that is indeed continuous since n. is continuous in a, and t(0) = 6/2 and f(1) = 8% What remains to be shown is that F((a) E i.e J, (F!(aa) > X. By the definition of h in Lemma F (() . It has been shown in the proof of Theorem that indeed J,...) 2 À provided that
( N and (T22) 2 X. This concludes the proof of Proposition
C Proof of Supporting Lemmas
C.1 Proof of Lemma
This lemma is adapted from Lemma 5.2 of Nguyen 20199]
16

---

C.2 Proof of Lemma 2
This lemma adapted from Lemma 5.3 of Nguyen (2019).
C,3 Proof of Lemma 3
We provide proof for the case k For k o L,, the proof can be found Nguyen (0119 Lemma
3.3].
For ((W2, b2), ..., (Wz, bL), R) Q ... x S2F, x A define the map h follows
h (( b() [W,
where W1 and by is defined as
W1
[x, 1|s1] σ (B1),
b
(16)
Bi (o (B(+)) 11s b(-1) w W1 vi E [1,
Bx-1 = (#) 1 Wi
where we use At to denote the Moore-Penrose inverse of a matrix A. A has full column rank, then we have A'A = If A has full row rank, we have AA I. We can easily see that the defined operator is continuous as it is composition of continuous operators.
Assumption 3 and Condition I iiply that the matrices W ..., Wt. all have full column rank, which means W/ Wi I. We also know that [X, s has full row rank by our assumption that X has full row rank, which means [X, [ X, 1 [ss]" that
T. Therefore, we can layerwise invert (T6) and verify
F
For every layer = 2, ..., L, we define the operator Gi R|S|xxe-- + *R 5|5mm
YWT 1|st (b7)
LE 12, 11
G(M)
4b YWW + 1|s1 (bt)
1= HYY) (1x)1)))
We also define the operator H R(d++))xn - R 81x1
To show the continuous path claimed in Lemma 3 existss, it suffices to show that the set {(W, b1) F-L (.(W,,.).WW; Ai F.f." } is connected, which is equivalent to showing that the set f 1 (F is
connected where f is defined as
f([WT. .6]T),))+)))))) G2 o..... ... G2 H[[[[] b.l
Note that the definition of f implics
( = H o G5 o (T).
(17)
Note that GT is
G7 ( {
(Nime (F)+ = Vi, vi.j+ (WI)* + (B]BW] = -}, 1 = L
(F) 1xb₁) (W?)* + (B BW? = -], 1= 2,.., L-1
is easy to verify that {C Ci.j Cayy Vi * j'} and (B) BW: = 0) for all 2, ..., L.. Then, Lemma implies that G, (F) is a connected set for all F.
B = 0} is also connected set for all F. Therefore, from (17) know that f (F) is connected set for any F, which concludes the proof of Lemma
Similarly, H (F) [X, L I' (F) +F)+((B) [X, |ss
17

---

C.4 Proof of Lemma 4
To show that the product of the two connected sets are connected, we consider any x. y {ab E A, E B). Obviously, there exist ag. Oy E A and bz, by E B such that I = ag
The connectedness of A and implies that there exists continuous path maps PA 0, - and
ps [0, 1] + B such that (0)= dxz PA(1) ) ky. Ps(0) (0) = bb. (1) = by. Define p(a) = PAPS for E [0, 1]. is obvious that p(a) E {ab a E A,b E B} for a. Since the product of continuous maps is still continuous, p [0. 1] {ab a E A,b E B) is continuous path map satisfying p() = x and p(1) = y. This implies that the {ab a E A, B) is connected set.
A similar argument can be used to show that the sum of two connected sets is connected.
C.5 Proof of Lemma 5
Define (L( (WW,,))))) b)) as the output of the final layer before the softmax activation
F POW.d = Fr. 1 Wr. + 1
Then, existing results in the literature (such as Lemma 3.4 of Nguyen 2019]) show that for any
0 E S2 there exists continuous path map p [0, 1] + Q such that p(0) = 0, p(1) = 0* E O and (p(a)) = (0) for all a E [0, 1]. This leads to our claim.
C.6 Proof of Lemma 6
This lemma adapted from Theorem Evard and Jafari
[994]]
D Convexity of Optimization Program
In this section, we show that [11 is convex optimization program. First, note that
(T) = Σ
= ()
8,0
which means that the objective function is linear in the reward.
The constraint is obvious closed. It also bounded as the reward r(s, a) e [0, Uy]. To prove the constraint set is convex, we need to show that for any Tı, 72 such that Attack(ri, TT ET) = ri and Attack(r2, Ti, () = rj. we have
Attack(ari a)r2, ... (4) Tt. Va E [0, 1].
(18)
By the optimality condition of 9 being the optimal poisoned reward for true reward ri and r2 is equivalent
rt r+) <0 and (r rt, -r) 50
for all r such that (T.) 2 Jx(x) + c₁. Vx E Ieder
Ty. \m.
By taking the convex combination of these
two inequalities, we have for any a E [0, 1]
(r ( r ori + (1 - a)r2 - -rt) 0
(19)
for all such that (,+m)) 199 equivalent to (T8).
2 (+( +
Vn Medett
Again by the optimality condition of (
At this point, we have shown that II has a linear objective function and convex (and also compact) constraint set. As result, the optimization program is convex.
18


Reviews:
[{"review_id": "yMWUx8i3bM", "reviewer": "Reviewer_efCX", "summary": "This work studies the connectedness in (deep) reinforcement learning. First, the authors show that the superlevel set of average reward objective in reinforcement learning is connected under both tabular and over-parameterized policies. The objective is shown to satisfy a stronger equiconnectedness property. Second, the authors use the results to get minimax theorems for robust reinforcement learning. In particular, they show that show that minimax problems with convex functions on one side and equiconnected functions on the other side observes the minimax equality (i.e. has a Nash equilibrium).", "questions": "1. The authors showed that gradient dominance and connectedness do not imply one another. This raises the question of whether connectedness properties of objective functions allow any algorithms to find optimal solutions?\n\n2. Related question: It seems that in Figure 1, the left example is easy for optimization (separated global maximizers), while the right example seems to be harder for optimization (stationary points which are not global maximizer). Does this imply that comparing to gradient dominance, connectedness is a less favourable property for optimization?\n\n3. There are existing results showing that in game settings, a property called pseudo-linearity is satisfied, i.e., there are monotonically increasing path between two policies, see Theorem 1 of https://arxiv.org/abs/2204.04186. I am curious if there is any relation between the connectedness in this work and pseudo-linearity in the above paper?", "limitations": "This is a mostly theoretical work. There is no negative societal impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The superlevel set of average reward objective in reinforcement learning is connected seems a novel and interesting result.\n\nThe results holds for over-parameterized neural networks, and find applications in minimax problems.", "weaknesses": "Some simulations could be used to verify the results.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for bringing to our attention this highly relevant pseudo-linearity structure. From the way we construct the path map in the proof of Theorem 1, it is not difficult to see that our result implies the pseudo-linearity, but pseudo-linearity does not imply connected superlevel sets as it lacks the sense of connectedness. The pseudo-linearity structure plays an important role in the algorithm design process in the paper [Jin 2022], which strengthens our belief that the results on connected superlevel sets can inspire and guide the design of future algorithms that we may not foresee at this point.\n\nBesides its potential application to algorithm design, our result in Section 4 discusses something more fundamental. The connectedness of superlevel sets allows us to derive the existence of a globally optimal solution (global Nash equilibrium), which in general may not exist for a nonconvex-concave minimax optimization problem. Knowing that the solution exists is a prerequisite before any algorithms can be designed to find the solution. When the existence of Nash equilibrium is unclear, we usually need to compromise by considering weaker notions of optimality. Please see our response to Reviewer ceyJ for a short list of alternative local/global optimality notions that have been proposed in nonconvex-concave and nonconvex-nonconcave minimax optimization.\t\n\nReferences\n\nJin, Yujia, Vidya Muthukumar, and Aaron Sidford. \"The complexity of infinite-horizon general-sum stochastic games.\" arXiv preprint arXiv:2204.04186 (2022)."}, {"review_id": "XCr68DfcRU", "reviewer": "Reviewer_ceyJ", "summary": "This paper aims to enhance the comprehension of the optimization landscape in reinforcement learning (RL) for policy optimization problems. The primary contribution of this work is to demonstrate the connectedness of the superlevel set of the policy optimization problem in RL under a tabular policy representation. Furthermore, the authors establish that the superlevel set of the objective function, considering the policy parameters (i.e., weights of the neural networks), remains connected across all levels. The authors also illustrate the practical implications of their main findings by deriving a minimax theorem for a specific class of robust RL problems.", "questions": "- I would like the authors to include an explanation for why one needs to expand their understanding of RL optimization landscape beyond gradient domination. To motivate the problem to the general conference audience, it is important to list additional insights one might gain from studying super level set connectedness (SLSC). For example, does SLSC help identifying bottlenecks, regions of poor convergence, or potential areas for algorithmic improvement? \n- It is also not clear to me what were the exact challenges in establishing results for deep RL? \n- Are the results in Sec 2 similar to Nguyen [2019]? If not, what are the exact differences? ", "limitations": "The authors are clear on the limitations of the work. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper studies an exciting area of research on optimization applied to policy learning in reinforcement learning. \n- The paper is generally well written and coherent. ", "weaknesses": "- The paper briefly talks about robust RL as a potential application of studying super level connectedness. It does not provide any practical robust RL algorithm. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to read the paper and for providing important feedback, which we will carefully consider and incorporate in the next revision.\n\nFirst of all, we confirm that studying SLSC can inform algorithm design. As we discuss in the last paragraph of page 5, given any two policies, our results provide us with a tool to generate a spectrum of policies that interpolate their values. This means that we can generate a continuum of optimal policies if we find two (possibly by gradient descent from different initializations). If the agent has a secondary preference over these policies (for example, some policies are easier to implement on the physical actuator), an eventually more preferred policy can be selected. In addition, in the paper [Jin 2022] pointed out by Reviewer efCX, the authors introduced a pseudo-linearity structure, which is weaker than and gets implied by our result in Theorem 1. This structure plays an important role in their algorithm design process, which strengthens our belief that the results on connected superlevel sets can inspire and guide the design of future algorithms that we may not foresee at this point.\n\nIn the broad minimax optimization and game theory literature, knowledge on the existence of Nash equilibrium (NE) guides the design of algorithms and helps researchers understand the limit of any algorithms that can be designed. In nonconvex-nonconcave minimax optimization problems, global NE may not always exists, and weaker notions of optimality have been introduced including local NE [Daskalakis 2018, Mazumdar 2018], coarse correlated equilibria [Muller 2022, Mao 2023], and local/global min-max equilibria [Jin 2020, Vamvoudakis 2023]. Algorithms that search for these alternative solutions are designed by exploiting their specific structure, which may not be optimal in the NE sense even if the existence of NE is established later on.\n\nAs we discussed in the related works section, our analysis and network architecture in the deep RL setting are inspired by [Nguyen 2019], which studies the optimization landscape of a supervised learning problem with a convex objective function. Assumptions on the piecewise linearity and monotonicity of the activation functions are required in [Nguyen 2019]. As our objective is a non-convex value function and the last layer of our neural network has to use a nonlinear, non-monotone softmax activation function to produce a valid probability distribution, important innovations need to be made to handle the activation function and the interfacing between the neural network and the policy optimization objective. The analysis of the first and last layer of our neural networks especially reflect the innovation.\n\n\n\nReferences\n\nDaskalakis, Constantinos, and Ioannis Panageas. \"The limit points of (optimistic) gradient descent in min-max optimization.\" Advances in neural information processing systems (2018).\n\nMazumdar, Eric, Lillian J. Ratliff, and S. Sastry. \"On the convergence of gradient-based learning in continuous games.\" arXiv preprint arXiv:1804.05464 (2018).\n\nNguyen, Quynh. \"On connected sublevel sets in deep learning.\" In International conference on machine learning, pp. 4790-4799. PMLR, 2019.\n\nJin, Chi, Praneeth Netrapalli, and Michael Jordan. \"What is local optimality in nonconvex-nonconcave minimax optimization?.\" In International conference on machine learning, pp. 4880-4889. PMLR, 2020.\n\nMuller, Paul, Romuald Elie, Mark Rowland, Mathieu Lauriere, Julien Perolat, Sarah Perrin, Matthieu Geist, Georgios Piliouras, Olivier Pietquin, and Karl Tuyls. \"Learning Correlated Equilibria in Mean-Field Games.\" arXiv preprint arXiv:2208.10138 (2022).\n\nJin, Yujia, Vidya Muthukumar, and Aaron Sidford. \"The complexity of infinite-horizon general-sum stochastic games.\" arXiv preprint arXiv:2204.04186 (2022).\n\nMao, Weichao, and Tamer Başar. \"Provably efficient reinforcement learning in decentralized general-sum markov games.\" Dynamic Games and Applications 13, no. 1 (2023): 165-186.\n\nVamvoudakis, Kyriakos G., Filippos Fotiadis, João P. Hespanha, Raphael Chinchilla, Guosong Yang, Mushuang Liu, Jeff S. Shamma, and Lacra Pavel. \"Game theory for autonomy: From min-max optimization to equilibrium and bounded rationality learning.\" In 2023 American Control Conference (ACC), pp. 4363-4380. IEEE, 2023."}, {"review_id": "ew4KDTOQOz", "reviewer": "Reviewer_UPhm", "summary": "This work shows the superlevel set of the objective function in reinforcement learning is always equiconnected for both tabular policy and neural policy. An application of the connected property is the minimax theorem. As a consequence, reward attack robust RL can be shown to have Nash equilibrium.  ", "questions": "I have some minor questions:\n1. What is the intuition behind Assumption 2? Why do we need the non-zero scalar condition?\n2. Can we use the equiconnected property to prove minimax theorems other than Theorem 3?\n", "limitations": "The authors address limitations in the conclusion section. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper show the superlevel set of the RL objective is connected. Furthermore, the collection of the objective functions under the tabular and the neural policy is equiconnected. \n2. The connected property is used to establish the minimax theorem.\n3. As a corollary, the authors show that reward attack robust RL problems have Nash equilibrium. This is the first work that shows such a result. \n4. The paper is well-written.", "weaknesses": "1. Although Theorem 1 and 2 are general results that cover a large class of policies, it is not clear whether the minimax theorem can be used to show the existence of Nash equilibrium for other robust RL problems, e.g., when the agent is uncertain of the transition kernels. \n2. It is unclear whether the theoretical results can help design algorithms for robust RL problems. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the feedback, which we will incorporate when making the next revision. We confirm that our results can be used to drive the design of algorithms (please see our response to Reviewer ceyJ above).\n\nThe technical reason for considering Assumption 2 is to make the activation function invertible and its inverse unique, which ensures that the activation function does not break the connected path constructed in the analysis. A sufficient condition that guarantees Assumption 2 is that the activation function is 1) monotonically increasing or decreasing and 2) piecewise linear.\n\nRegarding the question on whether the equiconnectedness property can be used to derive results other than Theorem 3, we would like to point to the pseudo-linearity condition that Reviewer efCX brought up from a recent work [Jin 2022]. In the tabular case, this condition gets implied by our results and analysis of Theorem 1, and it plays an important role in the algorithm design process in [Jin 2022]. Theorem 2 of our paper can be used to establish a neural network version of the pseudo-linearity condition, which may be helpful in extending their algorithm to the function approximation setting.\n\nReferences\n\nJin, Yujia, Vidya Muthukumar, and Aaron Sidford. \"The complexity of infinite-horizon general-sum stochastic games.\" arXiv preprint arXiv:2204.04186 (2022)."}, {"review_id": "pG6veqZVY8", "reviewer": "Reviewer_DdeT", "summary": "Authors found novel discoveries in policy optimization problems: 1.the superlevel set of the objective function related to the policy parameter is always a connected set and the optimization objective as a function of the policy parameter and reward satisfies a stronger “equiconnectedness” property. Based on the discoveries, authors derive a novel minimax theorem for a robust RL problem.\n", "questions": "Would it be possible to design a toy env and run some small experiments to explicitly show how the derived theorem can help develop better algorithm in addition to the reward poisoning example? ", "limitations": "Again, checking math is not my strength so I'll refrain from providing my opinion on the math. One limitation is lack of experiments and application. ", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Well written and well organized.\nNovel discoveries of policy optimization problems in reinforcement learning. \nDerived a novel minimax theorem for a robust RL problem which may contribute to the development of novel robust algorithm in the future. Theoretical analysis and proofs are nicely presented.\n", "weaknesses": "Checking math is not my strength so I'll refrain from providing my opinion on the math. I think one weakness is about the application side of the paper and lack of any experiments(maybe just a toy example?). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort in reviewing the paper. We agree that it would be good to complement the theory with simulations in some way, but so far the results mostly focus on the fundamental structure of the optimization problem, and it is unclear what simulations would be meaningful. We do want to point out that our theoretical results can lead to the design of better algorithms as we discuss in the response to Reviewer ceyJ."}]

Author rebuttal:

Meta-review: This paper studies the optimization landscape of average reward objective in reinforcement learning. The main results are the superlevel set of the objective with respect to policy parameter is connected under direct and over-parameterized neural network parameterizations, found to be interesting by all reviewers. The authors then used the findings to get minimax theorems for robust reinforcement learning.
Decision: Accept (poster)