Fractal Landscapes in Policy Optimization
Authors: Tao Wang
Sylvia Lee Herbert
Sicun Gao
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement learning
policy gradient
non-smooth landscape
TL;DR: We demonstrate that the optimization landscape of continuous state-space MDPs can be fractal, particularly when the underlying dynamics are chaotic.

Abstract: Policy gradient lies at the core of deep reinforcement learning (RL) in continuous domains. Despite much success, it is often observed in practice that RL training with policy gradient can fail for many reasons, even on standard control problems with known solutions. We propose a framework for understanding one inherent limitation of the policy gradient approach: the optimization landscape in the policy space can be extremely non-smooth or fractal for certain classes of MDPs, such that there does not exist gradient to be estimated in the first place. We draw on techniques from chaos theory and non-smooth analysis, and analyze the maximal Lyapunov exponents and H\"older exponents of the policy optimization objectives. Moreover, we develop a practical method that can estimate the local smoothness of objective function from samples to identify when the training process has encountered fractal landscapes. We show experiments to illustrate how some failure cases of policy optimization can be explained by such fractal landscapes.

Fractal Landscapes in Policy Optimization
Tao Wang UC San Diego taw003ducsd.co edu
Sylvia Herbert UC San Diego sherbert@ucad. edu
Sicun Gao UC San Diego si cungguucdd edu
Abstract
Policy gradient lies at the core of deep reinforcement learning (RL) in continuous domains. Despite much success, is often observed in practice that RL training with policy gradient can fail for many reasons, even on standard control problems with known solutions. We propose framework for understanding one inherent limitation of the policy gradient approach: the optimization landscape in the policy space can be extremely non-smooth fractal for certain classes of MDPs, such that there does not exist gradient to be estimated in the first place. We draw on techniques from chaos theory and non-smooth analysis, and analyze the maximal Lyapunov exponents and Hölder exponents of the policy optimization objectives. Moreover, we develop a practical method that can estimate the local smoothness of objective function from samples to identify when the training process has encountered fractal landscapes. We show experiments to illustrate how some failure cases of policy optimization can be explained by such fractal landscapes.
Introduction
Deep reinforcement learning has achieved much success in various applications [23] 30 38), but they also often fail, especially in continuous spaces, on control problems that other methods can readily solve. The understanding of such failure cases is still limited. For instance, the training process of reinforcement learning is unstable and the learning curve can fluctuate during training ways that are hard to predict. The probability of obtaining satisfactory policies can also be inherently low reward-sparse or highly nonlinear control tasks. Existing analysis of the failures focuses on limitations of the sampling and optimization algorithms, such as function approximation errors 35 39,, difficulty in data collection (34), and aggressive updates
policy space (28]. There has not been much study of potentially deeper causes of failures that may be inherent in the formulation of policy optimization problems.
Motivated by the common observation that small updates in the policy parameters can significantly change the performance, we analyze the smoothness of the optimization landscapes policy opti- mization. Drawing on chaos theory, we introduce the concept of maximal Lyapunov exponent (MLE) to the RL setting measure the exponential rate of trajectory divergence MDP. seems contradictory that trajectory in chaotic systems can be both exponentially divergent and uniformly bounded at the same time, and we will show that these two conflicting facts combine to yield fractal structure in the optimization landscape. Intuitively, the objective function is non-differentiable when the rate of trajectory divergence exceeds the decay rate of discount factor. Furthermore, this finding indicates that the fluctuations observed in the loss curve not just due to the numerical or sampling error but rather reflect the intrinsic properties of the corresponding MDP.
We should emphasize that the fractal landscapes that we will demonstrate are stronger than various existing results on the non- moo-ooothsesss 2 7 Most non-smooth objectives that have been studied still assume is local Lipschitz continuity or piecewise smoothness that implies differentiability almost everywhere (such as far (r). Instead, by showing that the loss landscape of policy optimization can be fractal, we demonstrate the absence of descent directions, which causes the failure of first-order
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

methods in general. Since such behavior is an intrinsic property of the underlying dynamical systems, the results show fundamental limitations of policy gradient methods on certain classes of MDPs.
The paper is organized as follows. In Section 3 and 4 we will introduce the preliminaries and develop the theory for deterministic policies. In particular, we show that the optimization landscape is fractal, even when all elements within the MDP are deterministic. Next, we consider stochastic policies and provide an example show how non-smoothness can still occur if without additional assumptions. In Section 5 estimating the Hölder exponent to determine whether the optimization objective is differentiable at a specific parameter vector. It can also indicate if the training process has encountered fractal regions by comparing the regression slope with some fixed threshold. In Section we show experiments that demonstrate and compare the landscapes of different MDPs.
we turn the theoretical analysis into a practical sampling-base method for
2
Related work
Policy gradient and Q-learning methods. Policy gradient methods 33 41 formulate RL as an optimization problem in the parameter space, with many variations such as natural policy gradient [T]], deterministic policy gradient (29). deep deterministic policy gradient (8, trust region policy optimization [27] and proximal policy optimization (28), were proposed. As all of these algorithms aim to estimate the gradient of the objective function over the policy parameters, they become ill-posed when the objective is non-differentiable, which is the focus of our analysis.
Another popular approach for model-free RL is Q-learning methods, which approximate the Q- function of the policy at each step [22] 40). As neural networks become more and more popular, they are employed as function approximators in deep Q-learning algorithms 9 [ 371. Since the foundation of Q-learning methods is established upon the estimation of value functions, a poor approximation can completely ruin the entire training process. In this paper, will show that the value functions in a certain class of MDPs exhibit significant non-smoothness, making them challenging represent using existing methods.
Chaos in machine learning. Chaotic behaviors due to randomness in the learning dynamics have been reported in other learning problems 66 21 [2]. For instance, when training recurrent neural networks for a long period, the outcome behaves like a random walk due to the problems of vanishing and the exploding gradients [4]. It served as motivation for the work (24), which points out that the chaotic behavior in finite-horizon model--ased reinforcement learning problems may be caused by long chains of nonlinear computation. A similar observation was made in (3I]. However, we show that in RL, the objective function is provably smooth if the time horizon is finite and the underlying dynamics is differentiable. Instead, we focus the general context of horizon problems in MDPs, in which case the objective function can become non-differentiable.
Loss landscape of policy optimization. It has been shown that the objective functions in finite state-space MDPs are smooth I 42.. which enables the use of gradient- methods and direct policy search. It also explains why the classical RL algorithms in 32 are provably efficient in finite space settings. Also, such smoothness results can be extended to some continuous state-space MDPs with special structures. For instance, the objective function in Linear Quadratic Regulator (LQR) problems is almost smooth [00 as long as the cost is finite. Similar results are obtained for the H2/H.x problem 43). For the robust control problem, although the objective function may not be smooth, it is locally Lipschitz continuous, which implies differentiability almost everywhere, and further leads global convergence of direct policy search [TT]. There is still limited theoretical study of loss landscapes of policy optimization for nonlinear and complex MDPs. We aim to partially address this gap by pointing out the possibility that the loss landscape can be highly non-smooth and even fractal, which is far more complex than the previous cases.
3 Preliminaries
3.1 Dynamical Systems Markov Decision Processes
We consider Markov Decision Processes (MDPs) that encode continuous control problems for dynamical systems defined by difference equations of the form:
$1+1 f(s,,
(I)

---

where E S C. R" is the state at time t, So is the initial state and xo(-)s)) E A C I is the action taken time based on policy parameterized by 0 R". We assume that both the state space S and the action space A are compact. The objective function of the RI. problem to minimize is defined by V of policy ng:
DC
((0) V (50)
Σ ((c(s;,))))
where E 1) is the discount factor and c(s, a) is the cost function. The following assumptions are made throughout this paper:
: x + Rd is Lipschitz continuous over any compact domains (i.e., locally Lipschitz
continuous);
(A.2) The cost function R everywhere;
R" R non-negative and locally Lipschitz continuous
(A.3) The state space is closed under transitions, i.e., for any (8,a) S A, the state s' = =((, E.S.
3.2 Policy gradient methods
Policy gradient methods estimate the gradient of the objective J(.) with respect to the parameters of the policies. A commonly used form
(())) Ba, Ve log To (ac(s;) n (st, at)]
where To( (-I-) is a stochastic policy parameterized by 6. A a) = QT* - (s) is the advantage function often used for variance reduction and (.,)..)) is the Q-value function mg. The theoretical guarantee of the convergence of policy gradient methods is typically established by the
argument that the tail term 7 V V (s) diminishes as increases, for any 8 E [33. For such claims to hold, two assumptions
needed:
VgV**(s) (s) exists and is continuous for all E S;
[s)] is uniformly bounded over S.
The second assumption is automatically satisfied if the first assumption holds in the case that S is and either finite or compact. However, as we will see in Section and 6 the existence of VoVT (-) may fail in many continuous MDPs even if S is compact, which challenges the fundamental well well-posedness of policy gradient methods.
3.3 Maximal Lyapunov Exponents
Behaviors of chaotic systems have sensitive dependence on their initial conditions. To be precise, consider the system $2+1 = F(s:) with initial state E P" and suppose that a small perturbation A7 made to 8g. The divergence from the original trajectory of the system under this perturbation at time 1, say AZ (t), can be estimated by (t)] = e o with some À that is called the Lyapunov exponent. For chaotic systems, Lyapunov exponents are typically positive, which implies an exponential divergence rate of the separation of nearby trajectories [19]. Since the Lyapunov exponent at given point may depend on the direction of the perturbation A Zo. and we are interested in identifying the largest divergence rate, the maximal Lyapunov exponent (MLE) is formally defined as follows:
Definition 3.1. (Maximal Lyapunov exponent) For the dynamical system 81+1 = F(s)), Su E IR" the maximal Lyapunov exponent Xmax so defined as the largest value such that
AZ(())l
Amax
lim sup lim sup
log
10000
| +
|
Note that systems with unstable equilibria, not necessarily chaotic, can have positive MLEs.

---

3.4 Fractal Landscapes
The Hausdorff dimension is the most fundamental concept in fractal theory. We first introduce the concept of --cover and Hausdorff measure:
Definition 3.2. (δ-cover) Let { be countable collection of sets of diameter at most å (i.e. [U/] sup yl1 2, U.} 8) and F IR then {Ui} ò-cover of F if U
Definition 3.3. (Hausdorff measure) For any F C.P. RN and 2 0, let
H(((F) inf Σ 1U (U;) ô-cover of F}.
Then we call the limit (F) = limg- - HF(FF the s-dimensional Hausdorff measure of F.
The definition of Hausdorff dimension follows immediately:
Definition 3.4. (Hausdorff dimension) Let C R& be subset, then its Hausdorff dimension
dim F (s 2 H² (F) 0) sup 0: (F) o0).
And we introduce the notion of (--ööler continuity that extends the concept of Lipschitz continuity: Definition 3.5. (a-Hölder continuity) Let a > 0 be scalar. A function R + R is a a-Hölder continuous INN if there exist C > and 8 >> 0 such that
Ig(x) ( S Cl| y
for all y E B(x, 8), where B(x, 8) denotes the open ball of radius 8 centered at æ.
The definition reduces to Lipschitz continuity when a 1. A function is not differentiable, if the largest Hölder exponent at a given point is less than 1. Just as smoothness is commonly associated with Lipschitz continuity, fractal behavior is closely related to Hölder continuity. In particular, for an open set C & and a continuous mapping r) F + E with p > k, the image set (F) is fractal when its Hausdorff dimension dim ry (F)) is strictly greater than k which occurs when F + RP a-Hölder continuous with exponent a < 1:
Proposition 3.1. (18) Let F C R& subset and suppose that vj F + RP is a-Hölder continuous where o > O, then dimw m(F) < dimy F.
implies that if the objective function is a-Hölder for some a < 1, its loss landscape L. {(0, J(0) E N+1+ 0 E R*} be fractal. Further discussion of the theory fractals can be found in Appendix
4 Fractal Landscapes in the Policy Space
In this section, we will show that the objective J(0) in policy optimization can be non-differentiable when the system has positive MLEs. We will first consider Hölder continuity V+* and J(-) with and then discuss the case of stochastic policies in 4.3
deterministic policies in 4.1 and 4.2
4.1 Hölder Exponent of (-)
We first consider deterministic policy my that maps states to actions a To(s) instead of distribu- tions. Consider a fixed policy parameter 0 TRP such that the MIFE of (T. namely X(0), is greater than - -logg: y. Let s/1 E be another initial state that is close to sg. i.c., = || - so > is small enough. According to the assumption (A.3) and the compactness of the state space, we can find constant such that both ||>; < M and || < M for E N. where [ and { the trajectories starting from so and s/g. respectively. Motivated by (4) further make the following assumptions:
(A.4) There exists K2 > 0 such that || sell < K, MP) for all t E N and ā = 11 -sll > 0.
(A.5) The policy N x 1 m is locally Lipschitz continuous everywhere.

---

We then have following theorem, and it provides a lower bound for the Hölder exponent of J whose detailed proof can be found in Appendix [B.1
Theorem 4.1. (Non-smoothnn smoothnooo of V**) Assume (A.1)-A.5) and the parameterized policy TT(.) -) is deterministic. Let A(0) denote the MLE of (I) at R... Suppose that X(0) > - loog,, then V th log -öölder continuous at 80-
A10)
Suppose that (0, 1] is some constant for which we would like to prove that V (s) is p-Hölder continuous at Sg. and here we take p A(0)
Proof sketch of Theorem 4.1
log
According to Definition 3.5 suffices to find some C" > 0 such that | (5/) V (= C'8P when 8 = ||sp soll < I. Consider the relaxed form
(s)) (TTe (su) Σ 2l(c(s c(5/, To( C..
(5)
t=0
Now we split the entire series into three parts as shown in Figure I the sum of first T2 terms, the sum from t T2 1 to T3 1, and the sum from t T3 to co. First, applying (A.4) to the sum of the first T2 terms yields
To Σ
(((())+og 1-7
Io(s,, To(s))) a(1/: no (x()))
Ki K20,
where K2 > O is the Lipschitz constant obtained by (A.2) and (A.5). If we wish to bound the right-hand side of (6) by some term of order (68) when < 1, the length T2(6) e N should satisfy
() = C1 + X(0) + log log());
(7)
where C O some constant independent of p and 8.
Al(samo(se)) - c(st 018")
-(6 o(07)
t=
== (2)))
t = (0)
Figure 1: An illustration of the two series and that need to cover the entire I when ô - 0.
Next, for the sum of the tail terms in (=) starting from T3 E N, it is automatically bounded by
2M log
7'(css (s)))) c(55 no (s())
where M2 maxxes o(s, (s)) is the maximum of continuous function e( (o)))) over the compact domain S (and hence exists). if we bound the right-hand side of ( by term of order ((5)), (P), it yields
(5( ~ C2
log(E),
log
for some independent constant C₂ O. Since the sum of 6 and ( provides good estimate of V only if (d) (d) < No for some No >> 0 as é + O, otherwise there would be infinitely many terms the middle - 0 that cannot be controlled by any (SP) terms. In this case, we have
p- log(o) S No.
(C2 - C2) +
(10)
log
x(O) + log
as log(8) -0, which implies that the slopes satisfy the inequality
p
p
2 0,
(11)
1og7
x(0) + log 7
5

---

where the equality holds when log Thus, V (s) is 1og Hölder continuous at = so. A(8)
On the other hand, the following counterexample shows that Theorem 4.1 has provided the strongest Hölder-continuity result for (* (s) at s so under the assumptions (A.1)-(.55)
Example 4.1. Consider one-dimensional MDP 81+1 = [(8t; 0t) where
-1, a a -1, f(s,a) = a, -1 -1 <a <
(12)
1, 221. 1,
with state space S = [-1,11 and cost function c(s, a) |s). Let the policy be linear, namely (s)s)) 0 and 0 E R. can be verified that all assumptions (A. (A.5) are satisfied. Now let
8o and > 1, then applying 4 directly yields
It(() A
|AZo |
X(0) lim sup lim sup log
lim sup lim sup
log
log 0.
|
(-30 ||azo|1-0
1-00
Let 5 > 0 be sufficiently small, then
To(8)
To(
(8) = 0n'00 = Σ
8
+
Σ
7
1
t=0
t
T=
where To( = 11 1 log
E N and L.] is the flooring function. Therefore, we have
log
log log
|V (8) 4 (0) = (5)
1ng
lux
Remark 4.1. Another way why it is theoretically impossible prove p-Hölder continuity for 1ng notice that the inequality (10) no longer holds as log - since T for any p X(0
X(0) log <0.
logy
Thus, log is the largest Hölder exponent of V**(.) that can be proved in the worst case. x(0)
Remark 4.2. The value function (*) is Lipschitz continuous at 80 when the maximal Lyapunov exponent A(0) < log 7, since there exists a constant K' such that
V (56) - v (so)l <
Me(s,, - c(s), mo()
<
K'' K''de x0)
t=
8K'
(A00)+
K'6
((())+ogg))
where 8 ||50 -/1l > 0 is the difference in the initial state.
4.2
Hölder Exponent of J(-)
The following lemma establishes direct connection between J(Ø) and J(8") through value functions: Lemma 4.1. Suppose that 0, 0' E IR?, then
Fe (su) (su) Σ (Q= Tor V (s
t=0
where {8 100 is the trajectory generated by the policy ner (.).

---

The proof can be found in the Appendix B.2 Notice that indeed we have J = V (so)
and (()) VT (sp). substituting with these two terms in the previous lemma and doing some calculations lead to the following main theorem whose proof can be found in the Appendix [B.
Theorem 4.2. smooomeesss of J) Assume (A. (A.5) and the parameterized policy Te(-) is
deterministic. Let X(f) denote the MLE of ① at Q E R.. Suppose that X(0) > - -log y, then J()) is
2ogg Hölder continuous at 0. X()
Remark 4.3. In fact, the of assumptionns (A.1)-A.5) is quite general and does not exclude the case
of constant cost functions c(s, a) = comst, which always results in a smooth landscape regardless of the underlying dynamics, even though they are rarely used in practice. However, recall that the
llog -Höler continuity is a result of exponential divergence of nearby trajectories, when cost A(0
function can continuously distinguish two separate trajectories (e.g.. quadratic costs) with a discount factor close to 1, the landscape will be fractal as shown in Section Another way to see it is to look into the relaxation in (5) where the Hölder continuity is obtained from the local Lipschitz continuity of c(s, u), i.e., |o(8, TT())) c(88, TT(s'))] S K2
8'11. Therefore, the Hölder continuity is light if for any d > 0, there exists s E B(00, 6) such that |c(se, To (o()t)) - c(s', no (x))))] 2 Kallst - %/.l with some K3 for all & E N. We will leave the further investigation for future studies.
The following example illustrates how the smoothness of loss landscape changes with X(0) and y: Example 4.2. (Logistic model) Consider the following MDP:
8141 = (1- 18--8,11 8t)aat, 80 = 0.9,
(13)
where the policy at is given by deterministic linear function ag (T((s)) 0st- The objective
function is defined as J(0) = = 7² (sî + 0.1 az) where E (0, 1) is the discount It is well-known that (13) begins to exhibit chaotic behavior with positive MLEs (as shown in Figure 2a when 0 2 3.3 115, so we plot the graphs of (() for different discount factors over the interval 0 E [3.3,3 3.9). From Figure 20 2d. the non- mon-smottsnsss becomes more and more significant as ? grows. In particular, Figure 2e shows that the value of [(f) fluctuates violently even within a very small interval of 0, suggesting a high degree of non-differeniaabiiiy in this region.
14
14
14
(a) MLE X(O).
(b)
0.5.
(c) 0.9.
(d) 7 0.99.
(e) Magnified.
Figure 2: The value of MLE x(0) for 0 E [3.3. 3.9 is shown in 2a The graph of objective function
(0) for different values of y are shown in 2b 2e where J0) is estimated by the sum of first 1000 terms in the infinite series.
4.3 Stochastic Policies
The original MDP (I) becomes stochastic when a stochastic policy is employed. First, let us consider the slightly modified version of MLE for stochastic policies:
log E
A (t)ll
Amar lim sup lim sup
(14)
A
to0
7

---

where AZo s/ -5- So is a small pertubation made to the initial state and (t. = = sr(W) (i))sss is the difference in the sample path at time E N and sample w E f2. Since this definition is consistent with that in (4) when sending the variance to 0, we use the same notation X(0) to denote the MIF at given A E R&N and again assume X(0) > logg- 7- Since policies in most control and robotics environments are deterministic, this encourages the variance to converge to O during training.
However, unlike the deterministic case where the Hölder continuity result was proved under the assumption that the policy (s) is locally Lipschitz continuous, stochastic policies instead provide a probability distribution from which the action is sampled. Thus, a stochastic policy cannot be locally Lipschitz continuous in 0 when approaching its deterministic limit. For instance, consider the one-dimensional Gaussian distribution (a(a)s) where [n, o|² denotes the mean and variance. As the variance a approaches 0, (a(as) becomes more and more concentrated at a jas, and eventually converges to the Dirac delta function 8(a - μs)), which means that To (a(a)s) cannot be Lipschitz continuous within neighborhood of any 0 = [1a. 0j² even though its deterministic limit Ts(s) = μ.8 is indeed Lipschitz continuous. The following example illustrates that this case, the Hölder exponent of the objective function J() can still be less than 1:
Example 4.3. Suppose that the one-dimensional MDP St+1 = f(r as) where f a) is defined as in 12) over the state space S = [-,, and action space A = 10, o0). The cost function is c(s, a) = 8 + 1. Also, the parameter space is 8 = [0t, 82] E IR2 and the policy To(-(s) ~ u(181) I 0zl. [0]|s= [+202))
2|02]) is uniform distribution. It is easy to verify that all required assumptions are satisfied. Let the initial state so = O and 8, > 1,02 = 0, then applying (14) directly yields x(0) = log On similarly as in Example 4.1] Now suppose that 0² > 0 is small and O' [0 0z)²
then for any w E Q in the sample space, the sampled trajectory { generated by Ter has
(w) 2 (w)((w) + 02 018((w) 2 01 2 (12))
when (w) < 1. Thus, we have (ww) = 1 for all w E Ω and t 2 To(O") = 1 + which further leads to
log H log P1
J(0') 1 0
Me Ex [0 2 [(0) + Σ
B [8]] 2
(0%)
(6()
using the fact that J(O) = y Plugging |10 8'1l = Bg into the above inequality yields
J(0') - ((0) 2 7 110' 0
log lox 01
(15)
where the Hölder exponent is again
l. as in Example 4.1 x(0)
Remark 4.4. Consider the 1-Wasserstein distance as defined in (36] between the distribution
8(a- - us) and [[1]|s + [82). |0 + 2 which is given by W, (81,02) 02) 3/621 It is Lipschitz continuous at 02 = O, even though the non-smooth result in (15) holds. Therefore, probability distribution metrics, such as the Wasserstein distance, are too "coarse" capture the full fractal nature of the objective function. This also suggests that further assumptions regarding the point- wise smoothness of probability density functions are necessary to create smooth landscape with stochastic policies, even though they may exclude the case of a + O as discussed earlier.
5 Estimating Hölder Exponents from Samples
In the previous sections, we have seen that the objective function ((0) can be highly non-smooth and thus gradient-based methods may not work well in the policy parameter space. The question is: how can we determine whether the objective function J(0) is differentiable at some 0 Og or not in high-dimensional settings? Note that (() may have different levels of smoothness along different directions. To address it, we propose statistical method to estimate the Hölder exponent. Consider the objective function J(f) and a probability distribution whose variance is finite. Consider the isotropic Gaussian distribution X N/o,, I²I,) where Ip the p x p identity matrix. For continuous objective function J(-), then its variance matrix can be expressed as
V (x)( = Ex- 2I (J(X)) Ex
-Ex ,,,()))))))()))))))) ((()))
8

---

where e E Ie' is obtained from applying the intermediate value theorem to Ex~N(% [(X]
and hence not random variable. If J(-) is locally Lipschitz continuous at do, say (J(0) J (00)]
K|10 0pl for some K > 0 when ||0 Boll is small, then it has the following approximation
Var(J(X)) < X= I|X - -1 = (Var(X))² ~ O(o²)
(16)
when < 1. Therefore, T6) provides way to directly determine whether the Hölder exponent of J()) at any given E IR is less than 1, especially when the dimension p is large. In particular, taking the logarithm on both sides of (T6) yields
log (Jrr(J(X)) S CC+ 2loo
(17)
for some constant C' where the subscript in Var, (X)) indicates its dependence on the standard deviation of X. Thus, the log-log plot of V (J))) versus is expected to be close to straight line with slope & 2 2 when J(0) is locally Lipschitz continuous around A = 9p- Therefore, one can determine the smoothness by sampling around On with different variances and estimating the slope via linear regression. Usually, ((0) is Lipschitz continuous at 0 = 6, when the slope is close to or greater than 2, and it is non-differentiable if the slope is less than 2.
6 Experiments
In this section, we will validate the theory presented in this paper through common RL tasks. All environments adopted from The OpenAl Gym Documentation [5] with continuous control input. The experiments are conducted in two steps: first, we randomly sample a parameter Oo from Gaussian distribution and estimate the gradient 17(6) from (3); second, we evaluate (0) at 0 = 0o + 61y(0o) for each small 8 >> 0. According to our results, the loss curve is expected to become smoother as decreases, since smaller makes the Hölder exponent A(0)
-log7 larger. In the meantime,
the policy gradient method (3) should give better descent direction while the true objective function (-) becoming smoother.
Notice that a single sample path can always be non-smooth when the policy is stochastic and hence interferes the desired observation, we use stochastic policies estimate the gradient in (3). and apply their deterministic version (by setting variance equal to 0) when evaluating (().. Regarding the
infinite series, we use the sum of first 1000 terms to approximate J(Ø). The stochastic policy is
given by (-(ss)) A(((s)), T²I,) where the mean u(s) is represented by the 2-layer neural network
u(s) = W2 Lanh(W1s) where Wi E MM (R) and W2 E MMxx (R) are weight matrices. Let
0 [W,. W denote the vectorized policy parameter. For the width of the hidden layer, we use
r = 8 for the inverted pendulum and acrobot, and r = 64 for the hopper.
(a) 7 0.9, deter- (b) 7 = 0.9, stochas-(c) 0.99, deter- (d) Y ministic.
(e) y
1.980z +
tic.
ministic.
stochastic.
2.088.
Figure 3: The experimental results of inverted pendulum. In 3e the linear regression result is obtained
for 7 = 0.9. The loss curves (0) are presented in 3a 3d where 0 = 0g + dnn(0n) with step size 10-7.
Inverted Pendulum. The inverted pendulum task is a standard test case for RL algorithms, and here we use it as an example of non-chaotic system. The initial state is always taken as = = ([0, 0j is the upright position), and quadratic cost function c(s, a) = sf Qs: + 0.001||a,|1 where Q = diag(1 1, 0.1) is a 2 x 2 diagonal matrix, 8, E R and a, E IR. The initial parameter is given by 8g (O, 0.052 Z). In Figure 4a and we see that the loss curve is close to a straight line within very small interval, which indicates the local smoothness of 6y. It is validated by the estimate of the Hölder exponent of (0) at = Op which is based on (16) by sampling many parameters around Og with different variance. In Figure the slope k- = 1.980 is very closed to 2 so Lipschitz continuity (and hence differentiabilitty) is verified at 0 = og- a comparison, the loss curve of single random sample path is totally non-smooth as shown in Figure 3b and 3d
|-1, 0j

---

Acrobot. The acrobot system is well-known for its chaotic behavior and hence we use it as the main test case. Here we use the cost function c(s, a) s Qs; + 0.005||az]]?. where Q diag(1, 1, 0.1, 0.1), 8, Rd and d, E IR. The initial state is So = 0, O, 0, The initial parameter again sampled from 0 (0, 0.05² Т). From Figure 4c the non-smoothness grows as y increases and finally becomes completely non-differentiable when Y = 0.99 which is the most common value used for discount factor. It partially explains why the acrobot task is difficult to policy gradient methods. In Figure 4e] the Hölder exponent of J(0) at 0 Oo is estimated as 0.43155 < I, which further indicates non-difterentiabiiiy around 0g.
(a) = 0.8, deter-(h) = 0.9, dcter-(c) = 0.99, deter-(d) 7 ministic.
0.99. (c) = 0.8631 +
ministic.
ministic.
stochastic.
2.041
Figure 4: The experimental results of acrobot. In Figure 4e the linear regression result is obtained for
y = 0.9. The loss curves J(0) are presented in 4a 4d where 0 = 0u + 617(0o) with step size 10-7.
Hopper. Now we consider the Hopper task in which the cost function is defined c(s, [(s.c) a) = (1.25 s(0]) 0 all², where s(0] is the first coordinate in RR. which indicates the height of hopper. Because the number of parameters involved in the neural network is larger, the initial parameter instead sampled from 0, (O, 102 I). As we that in Figure 5a the loss curve almost a straight line when
0.8, and starts to exhibit non-smoothness when = 0.9 and becomes totally non-differentiable when 7 0.99. A supporting evidence by the Hölder exponent estimation is provided in Figure 5e where the slope is far less than
7 0.8, deter- (b) 0.9. deter-(c) 7 0.99, deter-(d) 7 ministic.
0.99.
0.5036r
ministic.
ministic.
stochastic.
1.250.
Figure 5: The experimental results of hopper. In Figure 5e the linear regression result is obtained for
? 0.9. The loss curves J(0) are presented in 5a 5d where f = 6, + ó17(0) with step size 10
Conclusion
In this paper, we initiate the study of chaotic behavior in reinforcement learning, especially focusing on how it is reflected on the fractal landscape of objective functions. method to statistically estimate the Hölder exponent at some given parameter is proposed, so that one can figure out if the training process has encountered fractal landscapes not. We believe that the theory established in this paper can help to explain many existing results in reinforcement learning, such as the hardness of complex control tasks and the fluctuating behavior of training curves. It also poses serious question the well- rell-posednees of policy gradient methods given the fact that no gradient exists in many continuous state-space RL problems. Being aware of the fact that the non-smoothness intrinsic property of the model, rather than consequence of any numerical or statistical errors, we conjecture that the framework developed in this paper might provide new insights into the limitations of wider range of deep learning problems beyond the realm of reinforcement learning.
loss landscapes an
10

---

8 Acknowledgements
Our work is supported by NSF Career CCF 2047034, NSF Al Institute CCF 2112665, ONR YIP N00014-22-1-22992, NSF CCF DASS 2217723, and Amazon Research Award. The authors thank Zichen He, Bochao Kong and Xie Wu for insightful discussions.
References
[1] A. Agarwal, S. M. Kakade, D. Lee, and G. Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-76, 2021.
[2] A. Bagirov, N. Karmitsa, and M. M. Mäkelä. Introduction to Nonsmooth Optimization. Springer, 2014.
[3] M. Barnsley. Fractals Everywhere. Academic Press, Inc., 1988.
[4] Y. Bengio, P. Simard, and Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE Transactions on Neural Networks, 5(2):157-166, 1994.
[5] G. Brockman, V. Cheung, L. Petterssson, Schneider, J. Schulman, Tang, and W. Zaremba. OpenAl Gym. arXiv preprint 1106:0:606600544: 2016.
[6] A. Camuto, G. Deligiannidis, M. Erdogdu, M. Gürbüzbalaban, Şimşekli, and L. Zhu. Fractal structure and generalization properties of stochastic optimization algorithms. arXiv preprint (0t::22006.8881, 2021.
[7] H. Clarke. Methods of Dynamic and Nonsmooth Optimization. SIAM, 1989.
[8] K. J. Falconer. Fractal Geometry: Mathematical Foundations and Applications. John Wiley, 1990.
[9] J. Fan, Z. Wang, Y. Xie, and Z. Yang. A theoretical analysis of deep Q-learning, volume 1 120, pages 486-489, 2020.
[10] M. Fazel, R. Ge, S. M. Kakade, and M. Meshahi. Global convergence of policy gradient methods for the linear quadratic regulator. Proceedings of the 35th International Conference on Machine Learning, pages 1467-1476, 2018
[11] X. Guo and B. Hu. Convergence of direct policy search for state-feedback Hoc robust control: revisit of nonsmooth synthesis with Goldstein subdifferential. arXiv preprint arXiv:2210. 1577, 2022.
[12] G. H. Hardy. Weierstrass's non-differentiable function. Transactions of the American Mathe- matical Society, 17:301-325, 1916.
[13] T. Hester, M. Vecerik, O. Pietquin, M. Lanctot, T. Schaul, B. Piot, D. Horgan, J. Quan, A. Sendonaris, Osband, G. Dulac-Amold, Agapiou, Leibo, and Gruslys. Deep Q- learning from demonstrations. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), 2018
[14] M. W. Hirsch, S. Smale, and R. Devaney. Differential Equations, Dynamical Systems, and an Introduction Chaos. Academic Press, 2013.
[15] D. W. Jordan and P. Smith. Nonlinear Ordinary Differential Equations: An introduction for Scientists and Engineers. Oxford University Press, 2007.
[16] M. Kakade. A natural policy gradient. Advances Neural Information Processing Systems 14, pages 1531-1538, 2001.
[17] H. Kantz, robust method estimate the maximal Lyapunov exponent time series. Physics Letter A, 185:77-87, 1994.

---

[18] T. P. Lillicrap. J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv: (tth:::500099777 02000, 2015.
[19] E. N. Lorenz. The Essence of Chaos. University of Washington Press, 1995.
[20] S. W. McDonald, C. Grebogia, E. Ott, and J. A. Yorke. Fractal basin boundaries. Physica, 17D:125-153, 1985.
[21] L. Metz, C. D. Freeman, S. S. Schoenholz, and T. Kachman. Gradients are not all you need. 2021.
[22] J. Millán, D. Posenato, and E. Dedieu. Continuous-action Q-learning, Machine Learning. 49:247-265, 2002.
[23] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. Fidjeland, G. Ostrovski, and et al. Human-level control through deep reinforcement learning. Nature, 518:529-533, 2015.
[24] P. Parmas, C. E. Rasmussen, J. Peters, and K. Doya. PIPPS: Flexible model-based policy search robust to the curse of chaos. Proceedings of the 35th International Conference on Machine Learning, pages 4065-4074, 2018.
[25] R. Pascanu, T. Mikolov, and Y. Bengio. On the difficulty of training recurrent neural networks. Proceedings of the 30th International Conference Machine Learning, pages 1310-1315 2013.
[26] D. Preiss. Geometry of measures in R": Distribution, rectifiability, and densities. Annals of Mathematics, 125(3):537-643, 1987.
[27] J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz. Trust region policy optimization. Proceedings of the 32nd International Conference on Machine Learning, pages 1899, 2015.
[28] Schulman, Wolski, P. Dhariwal, A. Radford, and O. Klimov, Proximal policy optimization algorithms. arXiv preprint arXiv: 1.XX::17777063477 2017.
[29] D. Silver, G. Lever, N. Heess, T. Degris, D. Wierstra, and M. Riedmiller. Deterministic policy gradient algorithms. Proceedings of the 31st International Conference on Machine Learning. pages 387-395, 2014.
[30] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, Y. Chen, T. Lillicrap, F. Hui, L. Sifre, G. Driessche, T. Graepel, and D. Hassabis. Mastering the game of Go without human knowledge. Nature, 550:354-3355 -599,,4-3,,,- 2017.
[31] H. Suh, M. Simchowitz. K. Zhang, and R. Tedrake. Do differentiable simulators give better policy gradients? Proceedings of the 39th International Conference on Machine Learning, (62:20668-2069)) 2022.
[32] R. Sutton and A. Barto. Reinforcement Learning: an Introduction. MIT Press, 1998.
[33] R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour. Policy gradient methods for rein- forcement learning with function approximation. Advances in Neural Information Processing Systems 12, pages 1057-1063, 1999.
[34] P. Thomas and E. Brunskill. Data-efficient off-policy policy evaluation for reinforcement learning. Proceedings of The 33rd International Conference on Machine Learning, pages 2139-2148, 2016.
[35] N. Tsitsiklis and B. V. Roy. Analysis of temporal-different learning with function approxi- mation. Advances in Neural Information Processing Systems 9, pages 1075-1081, 1996.
[36] S. Vallender. Calculation of the Wasserstein distance between probability distributions on the line. Theory of Probability and its Applications, 18(4):784-786, 1974.
12

---

[37] H. van Hasselt, A. Guez, and D. Silver. Deep reinforcement learning with double Q-learning. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1), 2016.
[38] O. Vinyals, I. Babuschkin, W. Czarnecki, and et al. Grandmaster level in StarCraft II using multi-agent reinforcement learning, Nature, 575:350-354, 2019.
[39] R. Wang, D. P. Foster, and S. M. Kakade. What are the statistical limits of offline RL with linear function approximation? arXiv preprint arXiv:2010.1 2020.
[40] C. J. C. H. Watkins and P. Dayan. Q-learning. Machine Learning, 8:279-292, 1992.
[41] R. J. Williams. Simple statistical suudient-follwiigg algorithms for connectionist reinforcement learning. Machine Learning. 2-229-256, 1992.
[42] L. Xiao. On the convergence rates of policy gradient methods. arXiv preprint arXiv:2201.0744, 2022.
[43] K. Zhang, B. Hu, and T. Başar. Policy optimization for H2 linear control with Ho robustness guarantee: Implicit regularization and global convergence. SIAM Journal on Control and Optimization, 59(6):0011 --099, 2021.
13

---

A A Brief introduction to chaos theory
As mentioned in the Introduction, chaos exists in many systems in the real world. Although no universal definition of chaos be made, there indeed, three features that chaotic system usually possesses 14:
Dense periodic points;
Topological transitivity;
Sensitive dependence initial conditions;
In some cases, some of these properties imply the others. important note that, despite the appearance of chaos is always accompanied by high unpredictability, the chaotic behavior is entirely deterministic and is not consequence of randomness. Another interesting fact is that trajectories in chaotic system are usually bounded, which drives us to think about the convergence of policy gradient methods beyond the boundedness of state spaces.
Lorenz attractor.
(b) Rössler attractor.
Figure 6: The Lorenz system and Rössler system standard examples of chaotic systems, in which a small perturbation in the initial state can result a significant divergence in the entire trajectory.
Actually, it can be summarized from the results in this paper that for given MDP, the following three features contribute most to its chaotic behavior:
Infinite time horizon (t 00);
Continuous state space (|AZoll - 0);
Exponential divergence (Amaz 0);
Since these features are not necessarily bound to certain types of continuous state-space MDPs, it would be exciting for future studies investigate other types MDPs using the framework developed in the paper.
B Proofs omitted in Section
B.1 Proof of Theorem 4.1
Proof. Suppose that si E S is another initial state close 5g and ||so -66ll. Let Ti E N be the
smallest integer that satisfies
2M
T Z
log(
(18)
X(0)
K2 0
14

---

where M2 = + max,ss ((s,To(s)) > 0 is the maximum of the continuous function m())) over S, then applying the Lipschitz condition of c(., m)(+) yields
T Σ 7 [((s))T((s)) To(s:)) c(s/,, mo (s -
TT
Σ
7
K2 s1,1l
Ti
Σ
K (
Me; 1ox
log( X, x,8) +2(
e A(0)
I K K20
e(A(0)+logg)
(1(( K2K
x(0) (2M2)
log 1+
A(O)
X(0)
e(A(0)+log>) -1
where K₂ > is the Lipschitz constant of c(+, (-)) over compact set S. On the other hand, the tail terms in J(-) is bounded by
Mc(s,, Te(s:)) - (o()) S
2M
+
2M
[=1]
Ti
2.2
7
2M2
K
log
log
6
X00)
7
2M2
using (0 a(3/ (x())) & 2M2. Combining the above two inequalities yields
(* (so)l
No(ss - c(s) mT((())
2 (c(s,, (s())) c(si, Te(s()) +
Σ
Mo(s,, (o())) c(s', to
laga 2(A00)+ K K2K XOO (2M2)
log
2M₂
K1
Ioga X1o]
laga
8 x(
(1(8)+log) 7)
1 7
2M2
and we complete the proof.
B.2 Proof of Lemma 4.1
Proof. For the case of notation, let
s/. s/ o." ([(ss) TT(s) and u'(s) Tar (s).
15

---

(80) - (80) =
u v((o);'((())) - (=0()0)
t
>(((S) u/ (s()) + (s') - (5)) V= (s0)
+ VT (s{) + (50) - -V - v (su)
+ +
(5() - - - (so). (' (
t
t=
Using the fact that / (2(+1)) + 0 as - oo from (A.3) yields
VT - (s0)
(1 (5/ ul (s/)) - V= (5()) + (=(())) - V
=
t=0
Σ ( (s/, u' ($1) - vs))
and the proof is completed using s/6 so.
B.3 Proof of Theorem 4.2
Proof. First, we will show that QT (s, a) is - log x(²)
Hööler continuous with respect to a. Note that
for any given E A and any a' E A such that a|a a'll 11
1QT (= a')l s le(s, c(s, + V (f(s,
VT (f)) - (f(ssa'))
< Kalla- d'll + > I a) f(8,(() (20)
< K2 |a0 a' + a'll x
< K''l -
for some K3 > 0 using the locally Lipschitz continuity of and f.
Note that V/ (s) = TT (s, (s)))) combining with Lemma 4.1 yields
[J(8' - J(0) - (s( - (s))
11 (5/ x (s()) T (5/: no (s())
y *Ka To (5/) TT((s)) x(o)
Jokz
0=0
Jog
< 7 'KKK,ll0'' - 011
x(0]
t=
K3 K4
|00
A||
x(0)
1
using the fact that (s(s) is Lipschitz continuous in a neighhorhood of (0,s) E TR. S for some constant K₁ >> O and we complete the proof.
16

---

C From the perspective of fractal theory
We will go through some basic concepts in fractal theory that are related to the study of non-smooth functions.
C.1 The Hausdorff dimension
We will show that the Hausdorff dimension is well-defined: First, it is clear that when ō < 1, (F)) non-increasing with respect to 8. Thus, (F) is non-increasing as well. Let 8 2 0 such that H- (F) < oo, then for any t > and any 8-cover {U, of F, we have
1U S 8
10:1
which implies H(FF) = 0 by taking infimum on both sides and letting å - 0. Therefore, the set {s 2 0: 0 < (F) xc) contains at most one point, which further implies inf 2 0: (F) supsup 8 2 0: H" (F) oo).
More details regarding the well- cell-posedness of Hausdorff dimension can be found in 3 8) In particular, one can easily verify that the Hausdorff dimension coincides with the standard dimension (i.c. E N) when regular manifold. Typically, the Hausdorff dimension of a fractal not an integer, and we will be exploiting this fact through the section. A famous example is the Weierstrass function as shown in Figure 7 comparison of Figure and Figure [7c (they have the same scale) gives some sense about how non-smooth the objective function can be in practice.
(
-0.4
-0.
SEAr)
-22
(a) double sector S(x, d, v). (b) The (x) over E [- (c) Magnified: x E 0.5001)
Figure 7: (a) shows how the double sector looks like. In (b) and (c), the Weierstrass function is given by W(x) = - a" cos(b" where a = 0.6, b = 7. The Hausdorff dimension of its loss curve is calculated as dimy Lw
log, 1.73. Also, according to [12. such W W(x) is nowhere
differentiable when 0 < a < 1 and ab >
C.2 Non-existence of tangent plane
Actually, when J()) is Lipschitz continuous on any compact subset of R. by the Rademacher's Theorem, we know that it is differentiable almost everywhere which implies the existence of tangent plane. As it comes to fractal landscapes, however, the tangent plane itself does not exist for almost every 0 E R.,, which makes all policy gradient algorithms ill-posed. Although similar results were obtained for higher-dimensien provides a more direct geometric intuition. First, we introduce the notion of s-sets:
cases as in (26), we focus on the two-dimensional case so that
Definition C.1. Let F C 2 be Borel set and s 2 0, then F' is called an s-set if < (F) < co.
The intuition is that: when the dimension of fractal F is fraction between and then there is no direction along which a significant part of F' concentrates within a small double sector with vertex a as shown in Figure 7al To be precise, let S(x, Ø, v) denote the double sector and > then we say that F has tangent at x E F if there exists a direction o such that for every angle o > 0, it has
1. lim sup,- H((FFB(z.r) >
(2r)*
H (F (( = 0:
2. lim
(2r)*
17

---

where the first condition states that the set F behaves like a fractal around æ, and the second condition implies that the part of F lies outside of any double sector S(z, Φ, vp) is negligible when r + Then, the main result is as follows:
Proposition C.1. (Non-existence of langent planes, ( F C R is an 8-set with < 8 2, then at almost all points of F, no tangent exists.
Therefore, "estimate the gradient" no longer makes sense since there does not exist tangent line/plane at almost every point the loss surface. This means that all policy gradient algorithms are ill-posed since there is no gradient for them estimate at all.
C.3 Accumulated uncertainty
Another issue that may emerge during training process is the accumulation uncertainty. To see how the uncertainty entered each step accumulates and eventually blows up when generating a path along fractal boundaries, let us consider the following toy problem: Suppose that the distance between the initial point 0g E R-V and the target 0* is O, and step size б₁ > 0 adapted at the k-th step, as shown in Figure Sa If there exists >> 0 such that the projection (f" - fu. 0x+1 02) 2 cdo, for all N which implies that the angle between the direction from 0g 0x+1 and the true direction
g 0g does not exceed arccos(c). in this case, successful path } that converges to 0 should
give
Σ cdo
S
Σ 10 Go Ok+1 - 02) = (0" - 00. 0" - 0p) = d2
K=
k=
using 0g + 0" as - which is equivalent to Σx= 6x S
((0)
8
Bat
07) air
(a) Generating path from 0 to
(b) Update Pmp1 from O...
Figure 8: Illustrations of the statistical challenges in implementing policy gradient algorithms fractal loss surface.
On the other hand, when walking on the loss surface, it is not guaranteed to follow the correct direction precisely all the time. For any small step size 8 >> 0, the uncertainty fraction u(d) involved in every single step can be estimated by the following result 20)
Proposition C.2. Let 8 > be the step size and B N Hausdorff dimension of loss surface of J(),, then the uncertainty u(8) ~ O(8)) when < 1.
dimg J where dim J is the
Therefore, may assume that there exists another c' 0 such that the uncertainty Un at the k-th step has UR d for all 0, I,... Then, the accumulated uncertainty
U=
U
k=0
k=
bounded when 3 = (i.e. boundary is smooth) using the earlier result Eee 66 S However,
the convergence of E k= 5% no longer guarantees the convergence of Σk=o 8% when 1 < and counterexample is the following series:
1
5% k(log(k + 2))²
for all k = 0, 1, which implies the uncertainty accumulated over the course of iterations may increase dramatically and eventually cause the sequence 0g to become random when walking on fractal boundaries.
18


Reviews:
[{"review_id": "VbGcaUitni", "reviewer": "Reviewer_dey2", "summary": "The paper tries to argue that in a certain class of continuous state-action MDPs, the policy gradient landscape can be non-smooth. It does so by showing that the Holder exponent of the policy objective $J(\\theta)$ is less than one, when the MDP's maximum Lyapunov exponent is greater than $-\\log \\gamma$. The paper complements this result by analytically analyzing multiple simple MDPs and also by empirically showing this non-smooth behavior for popular MDPs like Acrobot. \n\nUnfortunately, I propose rejecting this paper because I am not confident in its proofs and cannot follow the logic completely. Although, it is possible that I am missing something, in which case I hope that the author's rebuttal can help alleviate my concerns (please see the Weaknesses and Questions sections below.)", "questions": "I would really appreciate if the authors could clarify the following (please refer to the Weaknesses section for details):\n\n(1) What is the connection between Holder coefficient and the non-smoothness of the objective? And don't we need a bound on the \"max Holder coefficient\" for getting the non-smoothness result?\n\n(2a) Is this an actual flaw in the proof, or am I missing something?\n\n(2b) Is this an actual flaw in the proof, or am I missing something?\n\n(2c) Could you please provide more details?\n\n(2d) Am I missing something?\n\n(3) Does non-smoothness of the objective function directly imply that it is fractal in nature?", "limitations": "The paper does not comprehensively discuss the limitations of the project.\n\nAssumptions, in particular A4, could have more motivation. \n\nThe case when $\\lambda(\\theta) < -\\log \\gamma$ could be further discussed; at the very least some comment on what the authors think would happen in that case could be helpful. (Maybe this reasoning is trivial, but I'll still encourage the authors to add that.)", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "### Originality and significance:\nThe paper deals with the fundamental issue of characterizing the nature of the policy optimization landscape in continuous state-action MDPs. This setting is highly practical, and to the best of my knowledge, not widely studied. One of the primary advantage of policy gradient methods over value based methods is their ability to naturally deal with continuous action-spaces. And as the paper claims, the optimization landscape is non-smooth which might create significant difficulties for gradient based methods. This knowledge is very useful for both algorithm developers and practitioners. The approach itself seems elementary and novel to me (although I have very limited knowledge about related works). (Also, I mean \"elementary\" in a good way. This seems like those first fundamental results which other people build upon.)\n\n### Quality and clarity: \nThe paper motivates the problem well and provides a thorough literature survey, with an introductory background on chaos and fractal theory included in the appendix, which I think would be appreciated by the readers new to these fields. The main analytical results (Holder exponent of the policy gradient objective being less than one) are complemented by a number of worked out examples (simple MDPs) and corroboration by multiple simulation studies (visualizing the landscape of popular environments such as Acrobot and Humanoid showing the non-smooth nature of the landscape), providing a well-rounded treatment of the subject matter.", "weaknesses": "## Major issues (these affect my score significantly):\n\nThe major weaknesses of the paper are a lack of a coherent argument and flaws in the proofs.\n\n### 1. Disconnect between the stated result and the non-smoothness claim.\nThe main results (Theorem 4.2, line 192) says that the policy gradient objective $J$ is Holder with some exponent less than one. And the paper then concludes that $J$ is non-smooth in the policy parameters. I don't completely understand this connection. I think that if a function is $\\alpha$-Holder for some $0 < \\alpha < 1$ and is not Holder continuous of any other $\\alpha' > \\alpha$, i.e. in some sense $\\alpha$ is \"max Holder coefficient\" (not sure what the terminology is), then it would be non-smooth (can the authors provide the relevant result here as well). However, in the paper, the main result just shows that $J$ is $\\alpha$-Holder for some $\\alpha < 1$; it doesn't show that this is the maximum possible Holder coefficient. There is a discussion following Theorem 4.1, from line 152-177 that argues that the Holder coefficient for the value function should be less than one. However, if that is a result, it should be the main theorem statement (it does seem very important). The non-smoothness could then follow from the bound on the Holder coefficient, and the theorem (which the authors should state) that connects this max Holder coefficient to the non-smoothness of the function.\n\nFurther, from the experimental results (Section 6), all the figures plot $J$ vs $\\delta$. But how that is connected to the non-smoothness of the landscape is a little bit unclear. More explanation would be very helpful. \n\nThe conclusion of the paper says \"It also poses a serious question to the well-posedness of policy gradient methods given the fact that no gradient exists in many  continuous state-space RL problems.\" But I am unable to attribute this to a specific theorem or empirical result given in the paper. \n\n### 2. Potential flaws in the proofs.\nI should state that it is quite possible that these are not really flaws, and I am just unable to follow the proofs. In that case, I would appreciate if the authors could help me here. It is also possible that these are just local problems, and the veracity of the final claims remains valid.\n\n**(a) Proof of Theorem 4.1 (line 455, page 13):**\n\nIn the display following Eq. 18, I don't follow the inequality (ignoring the term $K_1K_2 \\delta$)\n\n$$ \\sum_{t=0}^{T_1} e^{(\\lambda(\\theta) + \\log \\gamma)t} \\leq \\frac{e^{\\frac{\\lambda(\\theta) + \\log \\gamma}{\\lambda(\\theta)} \\log \\left( \\frac{2M}{K_1 \\delta} \\right) + 1}}{e^{\\lambda(\\theta) + \\log \\gamma} - 1}. $$\n\nWhat I am able to compute is the following. Since $\\lambda(\\theta) + \\log \\gamma > 0$, the function $e^{(\\lambda(\\theta) + \\log \\gamma)x}$ is increasing. Therefore, using the fact that $T_1 \\geq \\frac{\\log(2M / K_1 \\delta)}{\\lambda(\\theta)}$, we get\n\n$$ \\sum_{t=0}^{T_1} e^{(\\lambda(\\theta) + \\log \\gamma)t} = \\frac{e^{(\\lambda(\\theta) + \\log \\gamma) (T_1 + 1)} - 1}{e^{(\\lambda(\\theta) + \\log \\gamma)} - 1} \\geq \\frac{e^{\\frac{(\\lambda(\\theta) + \\log \\gamma)}{\\lambda(\\theta)} \\left[ \\log \\left( \\frac{2M}{K_1 \\delta} \\right) + \\lambda(\\theta) \\right] - 1}}{e^{(\\lambda(\\theta) + \\log \\gamma)} - 1}.$$\n\n**The most important thing to note is the inequality sign is flipped.** Maybe this could be fixed using $T_1 \\leq \\frac{\\log(2M / K_1 \\delta)}{\\lambda(\\theta)}$, but then could we guarantee that $T_1$ would exist?\n\nSimilarly, I don't understand the inequality sign in the second big display on page 13: $\\frac{\\gamma^{T_1}}{1 - \\gamma} \\leq \\frac{1}{1 - \\gamma} (K_1 / 2M)^{-\\log \\gamma / \\lambda(\\theta)} \\delta^{-\\log \\gamma / \\lambda(\\theta)}$. \n\nFinally, I don't understand how the Holder continuity result follows from the last equation on page 13. Seems like one step is missing on line 464.\n\n**(b) Proof of Theorem 4.2 (line 466, page 14):**\nI don't understand the third line in the first display. In particular, how to show that\n$$ R(s_t'; u'(s_t')) + \\gamma V^{\\pi_\\theta}(s_{t+1}') = Q^\\theta (s_t', u'(s_t')).$$\n\nUsing Bellman equation (for deterministic dynamics), we know that $Q^\\theta (s_t', u'(s_t')) = R(s_t'; u'(s_t')) + \\gamma V^{\\pi_\\theta} ( f(s_t', \\pi_\\theta(s_t'))$. But is it necessary that $f(s_t', \\pi_\\theta(s_t') = s_{t+1}') = f(s_t', \\pi_{\\theta'}(s_t'))$?\n\n**(c) (MINOR) Proof of Theorem 4.3 (line 471, page 14):**\nI am unable to follow the second line and the fourth line in the first display. (I guess, I just need to think more carefully for these..)\n\n**(d) (MINOR) Example 4.1 (line 183, page 5):** \nI don't understand why $||\\Delta Z(t)|| = ||\\Delta Z_0|| \\theta^t$? I do understand that $||\\Delta Z(1)|| = | f(s_0', \\theta s_0') |$, but is $f(s_0', \\theta s_0') = \\theta s_0'$?\n\nAlso, I don't understand if we get the result $V(\\delta) - V(0) \\geq \\frac{\\gamma}{1 - \\gamma} \\delta^{(-\\log \\gamma / \\log \\theta)}$, why does it mean that $p = -\\log \\gamma / \\log \\theta$ is the largest Holder coefficient? For instance, we know that $V(\\delta) - V(0) = V(\\delta) = \\delta \\sum_{t=0}^\\infty (\\gamma \\theta)^t = \\frac{\\delta}{1 - \\gamma \\theta} \\geq \\frac{\\delta^2}{1 - \\gamma \\theta}$, for small $\\delta$ and $\\theta$. Does that mean $p = 2$ is the largest Holder coefficient? Some additional explanation would be very helpful.\n\n### 3. There is almost no exposition on how the policy optimization landscape has fractal properties.\nThere is an appendix that discusses fractal theory. However, since \"fractal\" appears in the title of the paper, these details (IMHO) shouldn't be relegated to the appendix. In particular, after skimming that appendix, it seems that the discussion there is on general fractal theory, and no explicit connection to the paper's main results (Holder exponent and non-smoothness of the objective function) is made. The main question that remains in my mind is how is the non-smoothness of the landscape connected to it being fractal? (BTW, I think the non-smoothness result in itself is of sufficient interest, and the fractal part could be safely dropped.)\n\n\n\n## Minor issues / suggestions (these do not affect my score as much; please ignore them if you don't agree):\n- line 15: References 17, 24 are not about policy gradient methods\n- line 19 (the probability of obtaining a satisfactory solution can be surprisingly low, or even close to zero in certain tasks such as acrobot): a reference would be nice. I remember the following paper talks about PG methods failing with non-zero probability (maybe that's a little bit relevant?): Mei et al. (2021) Understanding the Effect of Stochasticity in Policy Optimization. NeurIPS. \n- line 25 (Considering that even a small update in policy space can significantly change the performance metric): a reference here would be nice\n- lines 27-38: some symbols ($\\gamma$, $\\sigma$) or choices (such as the policy parameterization) are not specified\n- line 39 (As shown in Section 6, the loss curve is still fractal even when all things in the MDP are deterministic.): I could not find this result. Could you refer to the exact theorem or the experimental result?\n- line 58: Is the edge of stability work a relevant reference for this section? Such as Arora et al. (2022) Understanding Gradient Descent on Edge of Stability in Deep Learning?\n- line 73 (It also explains why the classical RL algorithms in [25] are provably efficient in finite space settings.): some references would be nice\n- lines 105: for this equation, it would be nice if you could point to the exact section of the reference [26] \n- line 110 (However, as we will see in Section 4 and 6, the existence of $\\nabla V$ may fail in many continuous MDPs even if $\\mathcal{S}$ is compact): I don't see this exact result anywhere. Could you please refer to the specific theorem or the experimental result?\n- lines 116-128: could you explicitly define $\\Delta Z_t$\n- line 128 (but is applicable to a broad class of continuous state-space MDPs having any one of these characteristics) what characteristics is the paper referring to?\n- line 133 (Definition 4.1) Should this be called local Holder continuity?\n- regarding the Assumptions (lines 146-148 / 93-97): it would be nice if they are written in the same style as a definition or theorem and you can reference to them in the paper.\n- line 141 (that the MLE of (1), say λ(θ)): I think the system here is not that given by Eq. 1, but rather $s_{t+1} = f(s_t, \\pi(s_t))$\n- line 146 (Assumption 4): This is assumption is the most non-trivial one and very critical to the analysis. Some explanation as to why this is reasonable could be useful.\n- None of the appendices are referenced in the main paper. Further, Appendices A and C seem highly tangential to the main paper, especially because chaos and fractal theory are never explicitly discussed.\n- line 154: this sentence is awkward, has a forward reference to Example 4.1, and doesn't describe that the following text will discuss a lower bound. An appropriate section heading here would be very useful.\n- lines 162-164: define $T_i$s\n- line 164 (Eq. 8): I am unable to get the factor of $e^{(\\log \\gamma) T_2}$ in the inequality.\n- line 176: should the inequality be (sign reversed): $(p-1)/(\\lambda(\\theta) + \\log \\gamma) \\geq p / \\log \\gamma$?\n- line 184: I don't understand how to get the equation following this line. Some more explanation could be helpful..\n- line 195 (Actually, the most important implication of this theorem is that $J(\\theta)$ is not guaranteed **(and is very unlikely)** to be Lipschitz continuous when): why is it very unlikely? Is this an analytical result, or an empirical observation? In either case, some references would be nice.\n- Figure 2-5: the figures and especially their font is extremely small to be read when the paper would be printed\n- line 213: define $\\omega, \\Omega$\n- line 214 (sending the variance to 0): variance of what, the policy?\n- Section 6: all the sub-figures should have axis labels. Also the figure captions could be more descriptive. \n- The text has some minor grammar / typographical issues which should be easy to fix. For instance, line 97 spelling of transitons, or line 133 (definition 4.1): suppose that some scalar $\\alpha > 0$. --- this sentence seems grammatically incorrect.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the detailed comments and questions. We focus on addressing the major issues, and will further improve the writing based on the list of minor issues. \n\n1. The main result in this paper is that given a policy parameter $\\theta$, the objective function $J(\\theta)$ is $\\frac{- \\log \\gamma}{\\lambda}$-Holder continuous when the maximum lyapunov exponent $\\lambda(\\theta) > -\\log \\gamma$. The result itself does not rule out the possibility of having stronger Holder continuity, so we also provided an example (Example 4.1) to show that there exists an MDP that satisfies all assumptions (A.1)-(A.5), but its objective function is not $p$-Holder continuous for any $p > \\frac{-\\log \\gamma}{\\lambda(\\theta)}$. A discussion and Example 4.1 following Theorem 4.1 provided further support.\n\nA continuously differentiable function is always Lipschitz (Holder exponent $\\alpha = 1$). Having smaller Holder exponents usually indicates that a function is not differentiable. Therefore, by showing that the largest Holder exponent $\\frac{-\\log \\gamma}{\\lambda(\\theta)}$ that be guaranteed is less than 1, we demonstrate that the objective function can be non-smooth. Our theory does not prohibit one from using trivial reward functions, such as $R(s, a) \\equiv 0$, which gives a constant objective whatever the MDP is. We have focused on giving the general results, instead of imposing more restrictive assumptions for ruling out different types of trivial reward functions. \n\nFor the conclusion, since all gradient-based methods work in the following way: estimate an ascent/descent direction $\\eta$ at given policy $\\theta_0$, then update the policy $\\theta' = \\theta_0 + \\eta \\delta$ along that direction. Therefore, a necessary condition is that $J(\\theta)$ must allow a linear approximation (and hence be Lipschitz) in a neighborhood of $\\theta_0$, otherwise there does not exist a monotonically increasing/decreasing direction at all. We provided theoretical and experimental results to demonstrate that $J(\\theta)$ may be non-smooth. The results are not necessarily negative, as they may open up new ways of further improving RL algorithms. \n\n2. For the questions in proofs:\n\n(a) In fact, we assumed that $T_1$ is the smallest integer that satisfies (18) (line 457-458), thus we have $\\frac{1}{\\lambda(\\theta)} \\log (\\frac{2M_2}{K_1 \\delta}) \\leq T_1 \\leq \\frac{1}{\\lambda(\\theta)} \\log (\\frac{2M_2}{K_1 \\delta}) + 1$. Therefore, it should have no sign-flipping issues. There is an error on the constant factor in our first calculation, now it is fixed as\n$$|V^{\\pi_\\theta}(s'(0)) - V^{\\pi_\\theta}(s(0))| \\leq (\\frac{e^{2( \\lambda(\\theta) + \\log \\gamma)} K_2 K_1^{\\frac{- \\log \\gamma}{\\lambda(\\theta)}} (2M_2)^{1 + \\frac{\\log \\gamma}{\\lambda(\\theta)}} }{e^{(\\lambda(\\theta) + \\log \\gamma)} - 1 } + \\frac{2 M_2}{1 - \\gamma} (\\frac{K_1}{2 M_2})^{\\frac{-\\log \\gamma}{\\lambda(\\theta)}}) \\  \\delta^{\\frac{-\\log \\gamma}{\\lambda(\\theta)}}$$\nwhich also implies the $\\frac{-\\log \\gamma}{\\lambda(\\theta)}$-Holder continuity as claimed.\n\n(b) Actually, $\\{s'(t)\\}$ is the trajectory generated by policy $\\pi_{\\theta'}$, therefore it has $f(s'(t)), \\pi_{\\theta'}(s'(t))) = s'(t+1)$ and we did not use $f(s'(t), \\pi_{\\theta'}(s'(t))) = f(s'(t), \\pi_{\\theta}(s'(t)))$. Regarding the definition of Q-function, we use the one from [25], page 78 which gives $Q^\\pi(s, a)=R(s, a)+\\gamma V^\\pi(f(s, a))$ in the deterministic case.\n\nIndeed, Lemma 4.1 is an existing result and we don't take any credit for its derivation. The undiscounted version of this lemma can be found in the appendices of [7] by Fazel et al. (Lemma 10).\n\n(c) We use the following facts here: (a) $R(s, a)$ is locally Lipschitz w.r.t. $a$; (b) when $\\|a' - a\\|$ is small enough and $0< \\alpha < 1$, it is bounded above by $\\|a' - a\\|^\\alpha$. \n\n(d) For Example 4.1, consider a different initial state $s'(0) = \\delta > 0$, by employing the policy $\\pi_\\theta(s) = \\theta s$, the MDP becomes $s'(t+1) = f(s'(t)), \\pi_\\theta(s'(t))) = \\pi_\\theta(s'(t)) = \\theta s'(t) = \\theta^t \\delta$ when $\\delta \\theta^t \\leq 1$. If $s_0 = 0$, then $s(t) = 0$ for all $t$. Therefore, $\\| \\Delta Z(t) \\| = |s'(t) - 0 | = \\delta \\theta^t$. \n\nFor the maximality of Holder exponent, suppose that there exists $p > \\alpha$ (denote $\\alpha = \\frac{-\\log \\gamma}{\\log \\theta}$ for simplicity) such that $V(s)$ is $p$-Holder continuous at $s = 0$. Then, we can find some constants $M > 0$ and $d > 0$ such that $|V(\\delta) - V(0)| \\leq M \\delta^p$ for all $|\\delta|<d$ by Definition 4.1. However, we have already had $|V(\\delta) - V(0)| \\geq \\frac{\\gamma}{1 - \\gamma} \\delta^\\alpha$ for all sufficiently small $\\delta>0$, combining them yields $\\frac{\\gamma}{1 - \\gamma} \\delta^\\alpha \\leq M \\delta^p$ as $\\delta \\rightarrow 0$, which is impossible since $p > \\alpha > 0$. Therefore, $\\alpha = \\frac{-\\log \\gamma}{\\log \\theta}$ is the largest Holder exponent. By the way, we do not have $V(\\delta) = \\sum_{t = 0}^\\infty \\gamma^t |s_t|=\\delta \\sum_{t = 0}^\\infty (\\gamma \\theta)^t$ since $|s_t| \\leq 1$ according to (12).\n\n3. Regarding the connection between Holder exponents and fractal theory, Proposition C.1 says that when the function $F: \\mathbb{R}^N \\rightarrow \\mathbb{R}$ is $\\alpha$-Holder continuous, the Hausdorff dimension of its landscape is bounded above by $\\frac{N}{\\alpha}$ where $\\frac{N}{\\alpha}$ is greater than $N$ when $\\alpha < 1$. Thus, the landscape can have a fractional dimention between $N$ and $N + 1$, which means that the landscape is truly a fractal.\n\nAnother reason why we insist to use the notion of fractal is that when mentioning non-smoothness in optimization, people conventionally think of functions like $f(x) = |x|$ or $f(x) = \\max(x, 1)$ that are much smoother than what we have seen in this paper. By associating the landscape with fractals, we encourage researchers to think beyond existing frameworks and explore innovative approaches to tackle this problem, which has barely been discussed before."}, {"review_id": "L4yFLR2cb6", "reviewer": "Reviewer_xgpg", "summary": "This paper proposes a method to understand the optimization landscape of the policy gradient method in the search for a non-smooth or fractal landscape. The method is based on the chaos theory and non-smooth analysis of the optimization objective. In particular, the paper proposed a method to estimate the Hölder exponents, which is used to identify non-smooth landscapes. The theoretical analysis is discussed with empirical validation.", "questions": "It is unclear what the conclusion of the analysis on the non-smoothness of stochastic policies is in Section 4.3. Are the stochastic policies preferred over deterministic ones if the MDP (task) has a non-smooth landscape? \n\nSome experimental details are missing. The analysis was conducted on several Gym environments; however, the learning curve and RL algorithm details are absent. What algorithm was used for policy learning? Was it a vanilla policy gradient? Was batching employed for parameter updates, or were they updated after every sample? Providing a detailed algorithm would address these questions.\n\nHow the analysis depends on any particular type of policy gradient implementation, like with a batch of the sample or a single sample for parameter update?\n\nTo assess the algorithm's performance, it is crucial to examine its reward. Therefore, in addition to the loss curve, a return curve would provide a better understanding of the challenges involved in solving a complex task with a non-smooth landscape.\n\nAcrobot is mentioned as (lines 301-302) almost unsolvable by the policy gradient method. However, many policy gradient-based algorithms, such as PPO, can already solve this task. See CleanRL benchmark results for PPO (https://github.com/vwxyzjn/cleanrl). Is the analysis in this paper restricted to some particular policy gradient-based methods?\n\nIs the experiment run for multiple random seeds? The execution of the environments (MDP) changes in each episode; thus, multiple runs would give a better understanding. Adding multiple seed runs or explaining why that is unnecessary is crucial.\n\nThe Axis labels of Figures 2, 3, 4, and 5 are too small and hard to read.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The paper tackles an important and fundamental problem in policy gradient.\n- Overall a well-written paper with a comprehensive presentation.\n- The theoretical results are explained well with necessary assumptions and analysis.\n- Empirical results are presented in support of the theoretical analysis.", "weaknesses": "- Some experimental details (algorithm, return curve, random seed) are missing.\n- Unclear how the proposed method can be integrated into various effective policy gradient methods (e.g., Vanilla Policy Gradient, PPO).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback. We're glad to hear that you liked our paper! \n\n$\\textbf{The conclusion in Section 4.3}$: We claimed that unless further assumptions are made, the worst case of stochastic policies is worse than that of deterministic policies, as shown in Example 4.3. Therefore, if we would like to solve the deterministic MDP using stochastic policies, we must be careful when choosing any specific probability distribution. We believe that it will be a promising research direction, but delving too deeply may deviate our paper from the main thread. It would be nice to see if any progress can be made in the future.\n\n$\\textbf{Integration with existing algorithms}$: We believe that it will be a promising direction for future research. In Section 5, we proposed a statistical method that determines whether a function is differentiable at a given point, which can be used to check if the training has encountered a fractal landscape. If such a scenario arises, it indicates that further measures (local smoothing, re-initialization, etc.) are required and thus the objective function can be optimized efficiently. Also, the fact that the landscape can be fractal provides novel insights for practitioners to design more effective algorithms.\n\n$\\textbf{Numerical experiments}$: Since most concerns are concentrated on the experiments, we would like to address your questions from the following aspects:\n\n1. The purpose of experiments: The numerical experiments are intended to serve as validations for the theoretical results, and the thing we are interested in is the non-smoothness of the landscape around a randomly sampled $\\theta_0$. Therefore, as long as we can observe a clear fractal behavior in the plots, it will be in support of our theory.\n\n2. How they are conducted: In each numerical task, we do the following three things:\n\n    (a) Randomly sample $\\theta_0$ from a Gaussian distribution;\n\n    (b) Perform one-step vanilla policy gradient to estimate a descent direction $\\eta$ at $\\theta_0$;\n\n    (c) Evaluate the loss $J(\\theta_0 + \\eta \\delta)$ along $\\eta$ for different $\\delta$, and observe the non-smoothness.\n\n    Therefore, it is not a training process. The central claim is that when the landscape is fractal, there is no descent direction to estimate at all, which makes all policy gradient methods ill-posed. But we agree that adding more experimental details will make the paper more self-contained.\n\n3. The RL algorithm: We used Vanilla policy gradient to estimate the gradient of the advantage function (the original objective $J$ can be non-differentiable). Since what we want to show is the non-smoothness of the landscape, we are not training the policy, nor comparing different algorithms. Suppose that we have an objective $J(\\theta)$ which is non-differentiable at $\\theta = \\theta_0$. Then all policy gradient methods fail to estimate its gradient at $\\theta_0$ accurately regardless of what the algorithm actually is, because there does not exist a gradient at all in the first place. In the experiments, we showed that Vanilla PG cannot find a descent direction in chaotic systems (acrobot, hopper), and we believe that similar results can be obtained using other variants of policy gradient methods. In a word, having fractal landscape is an intrinsic property of chaotic MDPs, and is independent of how we solve it. We will make it clearer when updating the paper.\n\n\n4. The hyper-parameters: Since it is only a one-step policy gradient algorithm, the following parameters should be sufficient to reproduce the results along with those provided in the paper:\n\n    The random seed for vanilla policy gradient: np.random.seed(42);\n\n    Minibatch = 16;\n\n    Horizon = 1000;\n\n5. Eliminating the randomness: In experiments, the policies we selected are stochastic (Gaussian distribution) so that vanilla PG is applicable. However, when plotting the loss curve $J(\\theta_0 + \\eta \\delta)$ along $\\eta$ for different $\\delta$, the problem is that if we use the stochastic policy directly, the value of objective function $J$ has to be estimated by sampling the Gaussian random variables in the policy. Since paths of Gaussian noise are recognized for their fractal nature due to inherent randomness, it will undoubtedly interfere the desired observations. The reason is that we cannot tell whether the fractal landscape is a consequence of randomness or the intrinsic chaotic behavior within the MDP. Therefore, we apply the deterministic limit of the policy (by setting variance to 0) when evaluating $J(\\theta)$ to eliminate randomness. As expected, the landscapes are fractal in chaotic systems (acrobot, hopper) even when everything is deterministic, and smooth in non-chaotic systems (inverted pendulum).\n\n$\\textbf{The solvability of acrobot}$: We agree that the word \"unsolvable\" might be ambiguous and will further clarify it in the writing. In our paper, when we refer to the acrobot task, we specifically mean the swing-up-and-balancing task, not just the swing-up part itself. To the best of our knowledge, there is still a lack of effective policy gradient algorithms that can achieve this task, even though control methods have successfully solved it many years ago (\"The Swing Up Control Problem For The Acrobot\" by Spong, 1995). As for the mentioned algorithm \"cleanRL,\" we noticed that it uses the default reward function from OpenAI Gym, which assigns -1 to all steps that do not reach the target height and assigns 0 if it achieves the target height and terminates. However, typically, a quadratic cost term like $x^T Q x$ is necessary for balancing. Therefore, using such a reward function can only swing up the acrobot and cannot stabilize it to the upright position.\n\nHope that the above responses have addressed your concerns, and we are happy to answer any further questions.\n"}, {"review_id": "8VG6wSHbE1", "reviewer": "Reviewer_bNWE", "summary": "The paper points out that the value function of some MDPs is not differentiable or even fractal in the infinite horizon setting.\n\nThis raises the question of the well-formedness of policy gradient methods.\n\nA method for statistically estimating the Hölder exponent is presented to find out whether the training process has encountered fractal landscapes.", "questions": "Would you agree with the view that for stochastic MDPs where the probability distribution of the subsequent states P(s'|s,a) is reasonably smooth and a continuum of subsequent states is possible (probably the condition is that the distribution function is differentiable) there can be no more fractal value function? The probability distribution acts like a smoothing kernel and makes everything differentiable.", "limitations": "Yes", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "* The paper describes a fundamental problem that has received little or no attention to date.\n* The presentation is well-founded and provides deep insights.\n* The Appendix is a very nice addition to the main text.\n\nRemark:\\\nI observed the presumably fractal structure of the Q-function of an MDP myself in 2017. However, I decided against elaborating and publishing this observation further at that time. I would like to congratulate the authors for their sound and profound elaboration of the description of this phenomenon.", "weaknesses": "I see no weakness.\n\nMinor notes:\n\nSome of the capitalization is inconsistent \"Hölder Exponent\", \"Hölder exponent\". \\\nI suggest:\\\n“Maximum Lyapunov Exponents” -> “maximum Lyapunov exponent”\\\n„Hölder Exponent“ -> „Hölder exponent“\n\nThere are a couple of typos:\\\n„updare” -> “update”\\\n“even small update” -> “even small updates”\\\n„transitons” -> „transitions”\\\n“pertubation” -> “perturbation”\\\n“issues[27]” -> “issues [27]”\n\nThe sentence “Similar result obtained for the H2/H∞  problem [33].” is incomplete. Perhaps it should read “Similar results are obtained for the H2/H∞  problem [33].”\n\nTo make the use of hyphens consistent, it should be \"non-linear\" instead of \" nonlinear\", analogous to \"non-smooth\".\n\n\nIn Subsection 4.1 and 4.2, the mathematical expressions should be in bold, e.g. with boldmath\n\n\nIn the References there are still some unintentional, wrong lowercase letters:\\\ngoldstein\\\nlyapunov\n\nIn “Since these features are not necessarily binded to certain types of continuous state-space MDPs”, instead of \"binded\" it should rather be \"bound\" or \"tied\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much! We are delighted that you are interested in our paper!\n\nThe question you raised is very insightful, and we would like to share some opinions about it.\n\nIn Example 4.3, we showed that if no additional assumptions are added, using stochastic policies may lead to a more non-smooth landscape than that created by deterministic policies when the underlying MDP is deterministic. In the DPG work [23], the authors proved that if the underlying MDP is stochastic and satisfies certain conditions (including the one that you suggested in the question), then the objective function is differentiable even when using a deterministic policy. \n\nIntuitively, the randomness in stochastic MDPs may create a smoother landscape, as the probability distribution may act like a smoothing kernel. A similar result is in the search gradient method (\"Natural Evolution Strategies\" by Wierstra et al.), where it smooths the objective function $J$ by convolving it with a Gaussian kernel $p(\\mu, \\sigma)$ so that the new objective $J * p$ (convolution of $J$ and $p$) is smooth w.r.t. $\\mu$ and $\\sigma$,\" allowing gradient descent algorithms. Therefore, we totally agree with your idea.\n\nJust one more thing that we want to mention: one of the main continuous-space environments for RL is control and robotics. If we ignore the error and noise in those environments, the underlying models are all deterministic as they are derived from physical laws. Therefore, a dilemma is posed to us: if we have much noise in the system, the objective function may be smoother (assuming the noise satisfies all conditions in [23]). However, in the meantime, the system will be less stable and controllable. On the other hand, if we have little noise, the objective function will be fractal and non-smooth, which makes gradient-based methods less effective.\n\nOverall, we believe that it is a very important and fundamental problem in RL that deserves more attention in the future."}, {"review_id": "2Qs5hnobgC", "reviewer": "Reviewer_Qd1b", "summary": "This paper studies the dynamics of policy gradient training in\nreinforcement learning, and argues that the policy gradient often does\nnot exist due to the lack of regularity of the training objective. The\nauthors derive a threshold on the \"maximum Lypanunov exponent\", a\nquantity they introduce which captures the sensitivity of trajectories\nto policy parameters, beyond which sufficient regularity (and existence\nof the policy gradient) cannot be guaranteed. Beyond this, the authors\ndemonstrate how the Holder coefficient of the training objective as a\nfunction of the policy parameters can be estimated from sample\ntrajectories, and validate via numerical simulations that the Holder\ncoefficient estimated from samples correlates with the stability of\npolicy gradient training.\n", "questions": "Line 57 says \"Consequently, it is not surprising that [DDPG, TRPO,\nPPO, etc] often have a low probability of obtaining a satisfactory\nsolution\". Is this true? Some of these algorithms have proven to be\nquite successful (albeit very sensitive).\n\nIn section 3.3, the \"divergence\" terms $\\Delta Z(t)$ should be defined\nexplicitly. Moreover, the definition of the Maximum Lyapunov Exponent\ncan be made more clear. It defines $\\lambda_{max}$ as the \"largest\nvalue\" such that equation (6) holds, but it's not clear what the\nmaximum is being taken with respect to here. From the sentence\npreceding definition 3.1, I think there should be a supremum over all\nperturbation directions before the limits.\n\nOn line 155, the paragraph starts by mentioning Example 4.1 which\nthe reader hasn't encountered yet. This doesn't read well.\n\nI do not understand the argument about Lipschitz (dis)continuity for\nstochastic policies around line 223. It says in the zero-variance\nlimit that  $\\pi_\\theta(a\\mid s) =\n\\delta(a - \\mu s)$ is\na Dirac measure and cannot be Lipschitz continuous, despite the fact\nthat the deterministic limit\n$\\pi_\\theta(s) = \\mu s$ is Lipschitz continuous, but you are surely\nreferring to 2 distinct notions of Lipschitz continuity here. The\nformer (as far as I can tell) is a statement about the Lipschitz\ncontinuity of the map $a\\mapsto \\pi_\\theta(a\\mid s)$, whereas the\nlatter is a statement about the Lipschitz continuity of the map\n$s\\mapsto\\pi_\\theta(s)$. These are different things, and it's not\nclear to me why it is meaningful to compare them. The fair comparison\nas I see it would be the map $s\\mapsto \\pi_\\theta(\\cdot\\mid s)$ in the\nstochastic case, which can indeed be Lipschitz continuous if the image\nis metrized by the Wasserstein distance.\n\nOn line 89, it says \"The sample space $\\mathcal{S}$ is\ncompact\". Should it not say that the state space is compact?\n\nWhy is $R$ used to denote a cost function? This is confusing.\n\nLine 110, why does the second assumption only \"apparently\" hold?\n\nOn line 118, what does $\\simeq$ mean? Is $\\|\\Delta Z(t)\\|\\simeq\ne^{\\lambda t}\\|\\Delta Z_0\\|$ the same as\n$\\|\\Delta Z(t)\\| = e^{\\lambda t} + o(1)$?\n\nWhy is assumption A4 natural? Under which conditions on the MDP/policy\nis A4 satisfied?\n\nOther policy gradient works have proposed conditions for which the\npolicy gradient is defined (see e.g. \"Deterministic Policy Gradient\nAlgorithms\" by Silver et. al, 2014; Theorems 1, 2 and conditions A1,\nA2, B1).\nIs your Theorem 2 related to these conditions? Is it easier to verify\nthe conditions of Theorem 2?\n\nIn the experiments, how exactly was the policy gradient computed? In\nparticular, how are you estimating the advantage in equation (3)? How\nare you computing the policy gradient for deterministic policies?\nAlso, equation (3) for $\\eta$ looks like it is already computing a\ngradient w.r.t. parameters, so $\\nabla_\\theta\\eta(\\theta_0)$ does not\nappear to have the right shape, especially in the expression $\\theta =\n\\theta_0 + \\delta\\nabla_\\theta\\eta(\\theta_0)$.\nI'm assuming by $\\nabla_\\theta\\eta$ you just mean $\\eta$.\n\nAre there any promising directions that RL researchers can follow in\norder to solve the \"fractal landscape\" problem?\n", "limitations": "Some assumptions are made for the estimation of the Holder exponent\nthat seem very restrictive. Also, it is not clear to me if the\ncondition on the maximum Lyapunov exponent is easier to verify or more\nintuitive than those given in earlier works on policy gradient\nmethods, which also serve the purpose to ensure that the policy\ngradient exists.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "This work studies an interesting an important problem that deep RL is\nfaced with. The chaos-theory-inspired approach taken by the authors is\nrelevant, and in particular, it is nice to see how the Holder exponent\ncan be approximated from samples. The experimental results are fairly\ninteresting, demonstrating a clear correlation between the estimated\nHolder coefficient and the stability of training.", "weaknesses": "As I understand it, the main theoretical result of the paper is that for\na small enough Lyapunov exponent, we can prove that the policy gradient\nobjective is smooth enough, but not the converse. That is, for a large\nenough Maximum Lyapunov Exponent, it is shown that sometimes the\nobjective is non-smooth, but clearly it may also still be smooth\n(consider for example any MDP with a constant reward function). It is\nclaimed on line 197 that when the Maximum Lyapunov Exponent is above the\nthreshold, the objective is \"very unlikely\" to be Lipschitz continuous,\nbut I do not find any convincing justification for this beyond\nintuition.\n\nMoreover, even if the objective is not Lipschitz continuous, it is not\nclear to me that this should necessarily raise alarms with regard to\npolicy optimization. A function that is non-diffentiable at even one\npoint (that is, a set of measure zero!) is not Lipschitz continuous, but\nI would not expect this to necessarily pose any severe optimization\nproblems for policy gradient algorithms. If the objective turns out to\nbe fractal (as suggested by the title), that would probably be much more\nsevere, but fractals are not really discussed at all in the paper. The\nauthors at one point claim that a lower Holder exponent *can* imply a\n\"more fractal\" landscape, but no evidence is given that loss landscapes\ntend to be fractal in the RL problems that we encounter.\n\nFurthermore, while I find the method of estimating the Holder exponent\nfrom samples interesting, there are many assumptions made (such as the\n\"tightness\" of the Holder continuity of the objective) that I would not\nnecessarily expect to hold in practice. Consequently, it is not clear to\nme that the constant extracted from this scheme would be an accurate\nrepresentation of the Holder exponent.\n\nThe Maximum Lyapunov Exponent introduced in this work is abbreviated to\nMLE, which should probably be avoided.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed comments and suggestions. Please see the answers below. We should clarify that the results are not meant to be negative (and will revise some of the statements) but to illustrate a source of difficulty in policy optimization that has not been discussed much in existing work, and we believe the results may lead to new ways of improving RL algorithms. \n\nWeakness:\n1. Yes, we chose the words \"very unlikely\" because the theory does not exclude the case of using trivial reward functions, such as the constant function $R(s, a)\\equiv0$ which always gives a perfectly smooth landscape as you suggested. Stronger results are possible under more restrictive assumptions but the generality will likely be weakened. \n2. The connection between Holder exponent and the Hausdorff dimension (an important characteristic of fractal) is given in Proposition C.1, which states that the landscape can have fractional dimension if its Holder exponent is less than 1. Importantly, the set of these points is not of measure zero, but determined by the measure of the set $M=(\\theta\\in\\mathbb{R}^N:\\lambda(\\theta)>-\\log\\gamma)$. For chaotic systems and the conventional $\\gamma=0.99$, the measure of $M$ is positive, indicating the landscape is truly fractal. This claim is validated by Figure 2(a) and 2(d)-2(e).\n3. Tightness assumption in Holder exponent estimation: really good question. Generally speaking, precisely estimating the Holder exponent of a high-dimensional function is hard, as the function may have different curvatures along different directions. Therefore, our methods aim to estimate whether the objective function $J(\\theta)$ is differentiable at given point. The slope is at least 2 when it is differentiable, since it has $|J(\\theta')-J(\\theta)|\\leq K\\| \\theta'-\\theta\\|$ for some $K > 0$, and further implies $Var(J(X))\\leq K'\\sigma^2$. Therefore, one can compare the slope of regression with 2 to determine the smoothness, without worrying about the precise value of the Holder exponent.\n\nQuestions:\n1. Line 57:  We agree that the word \"satisfactory\" is ambiguous and will further clarify it in the writing. In acrobot swing-up-and-balancing as typically modelled as an RL environment, the default reward function (e.g., in OpenAI Gym) is -1 to all steps that do not reach the target height, and 0 if it achieves the target height, in which case it terminates. This is a weaker version of the original control problem of minimizing the quadratic cost and stabilizing at the top (and the RL-trained policies are \"very sensitive\" as you pointed out, showing the difficulty in stabilizing).\n2. The divergence term $\\Delta Z(t)=s'(t)-s(t)$ is the difference between two trajectories at time $t$. Regarding the definition of 3.1, yes, it should be given as $$\\lambda_{max}=\\limsup_{t\\rightarrow\\infty}\\limsup_{|\\Delta Z_0|\\rightarrow 0}\\frac{1}{t}\\log\\frac{|\\Delta Z(t)|}{|\\Delta Z_0|}.$$ It does not change the main claims as the limits in the example exist.\n3. Line 223: For deterministic policies, they are directly from a function approximator which is locally Lipschitz continuous, and we are able to prove Holder continuity only if it is assumed. However, stochastic policies are determined by both mean and variance, and in general it is not Lipschitz w.r.t. the variance (e.g. Dirac function), that is why the landscape can be even more fractal in this case. Therefore, unless further assumptions (e.g., Wasserstein distance as you suggested) are made, the worst case of stochastic policies is worse than that of deterministic policies, as shown in Example 4.3. We believe that it will be a promising research direction, but delving too deeply may deviate our paper from the main thread.\n4. Line 110, if we assume the first assumption ($\\nabla V$ exists and is continuous over $\\mathcal{S}$), then the fact that any continuous function over a compact domain is bounded gives the second assumption.\n5. Line 118, the formula $|\\Delta Z(t)|\\simeq e^{\\lambda t}|\\Delta Z_0|$ says that for sufficiently small $|\\Delta Z_0|$, there exist $K_2>K_1>0$ such that $K_1e^{\\lambda t}|\\Delta Z_0|\\leq |\\Delta Z(t)|\\leq K_2 e^{\\lambda t}|\\Delta Z_0|$ when $t$ is not too large. Furthermore, it is also the motivation of assumption (A.4): the largest exponential divergence rate of trajectories is $\\lambda(\\theta)$. Positive maximal Lyapunov exponent is an indicator for chaotic systems (see [11]). Thus, a direct implication is that the objective functions in some often-used MDPs (acrobot, hopper) are non-differentiable. In contrast, the landscape of inverted pendulum is smooth as shown in Figure 3(c) since it is not chaotic.\n6. Regarding the conditions in DPG, the assumptions (underlying MDPs are stochastic) aim to avoid difficulties along the lines of our analysis, but our goal is to show that non-smooth landscapes can happen under very mild assumptions, so typical algorithms are indeed used in MDPs that do not satisfy the assumptions in the DDPG paper, and more work is needed to further improve RL algorithms.\n7. In the experiments, we use vanilla policy gradient to estimate the gradient from (3). Actually, the policies were stochastic (line 281-285) and hence (3) is applicable. When plotting, we use its deterministic limit to evaluate the objective. In figure 4(d), the landscape is fractal because we are using stochastic policy. However, the landscape in Figure 4(c), 5(c) are also fractal even if everything is deterministic, which implies that non-smoothness is not just a consequence of randomness and thus validates our theory.\n8. For the future study, given that the landscape is fractal, it will be interesting to consider techniques that can approximate the objective $J(\\theta)$ by a smooth surrogate function $J'$, then estimate the gradient of $J'$ as ascent direction. Further interesting questions would then involve how to balance the trade-off between the smoothing effects and the approximation error."}]

Author rebuttal:

Meta-review: **Summary**: This paper shows that for deterministic MDPs with continuous state and action spaces, optimization landscape in the policy space can be extremely non-smooth or fractal. The authors did this by showing that if MDP's maximum Lyapunov exponent at $\theta$ (denoted as $\lambda(\theta)$ ) is larger than $- \log{\gamma} > 1$, then "$J(\theta)$ is not guaranteed (and is very unlikely) to be Lipschitz continuous".

**Strength**:

1. Reviewers all agreed that the paper studied a fundamental problem, and the aim of understanding why and how policy gradient methods often fail in control problems is highly relevant.

2. Characterizing the pathological policy value landscape received little or no attention to date, and the paper provided very interesting ideas and insights, using maximum Lyapunov exponent characterization.

**Weaknesses**:

1. There is a gap between what was proved and the non-smoothness claim.

As mentioned in the paper, "$J(\theta)$ is not guaranteed (and is very unlikely) to be Lipschitz continuous when $\lambda(\theta) > - \log{\gamma}$".

This was mainly criticized by Reviewers Qd1b and dey2. And the direct result is that the prevalence of fractal landscapes in policy optimization is not clear to the reviewers, and nor are the consequences.

From the discussion and the paper, the situation is that there exist examples (Example 4.1) where the largest Holder exponent is $< 1$, which implies that the policy value is non-smooth. However, for the main results (Theorems 4.1 and 4.2), the situation is that the results cannot exclude smooth functions, including but not limited to constant reward functions as mentioned by authors in discussions.

This is indeed a concern, considering the importance of the problem studied and claim made in this paper. The authors also mentioned in the discussion "as long as a reward function can continuously distinguish two separate trajectories ... the objective function will be non-smooth, as shown in experiments", which seems to me they could possibly fill the gap.

The authors should fill the gap, which will make the theoretical results more convincing.

2. Re-writing / re-organizing the paper.

This is also mainly criticized by Reviewers Qd1b and dey2.

The title and main statements both indicate that certain MDPs could have fractal landscapes. However, the discussion of the fractal theory is relegated to the appendix. During rebuttal, the authors also agreed with the reviewers that the writing should be changed. The paper would be largely improved from re-writing / re-organizing.

**Recommendation**:

There are disagreements between reviews after rebuttal. After reading the paper and reviews, as well as discussions, the AC acknowledged that the paper studied an important problem and provided very interesting ideas and insights, while there are indeed two concerns. We recommend the authors to fill the gap in the theory mentioned by reviewers and re-organize the exposition.
Decision: Accept (poster)