On the Fast Convergence of Unstable Reinforcement Learning Problems
Authors: Wang Zhang
Lam M. Nguyen
Subhro Das
Alexandre Megretski
Luca Daniel
Tsui-Wei Weng
Venue: Submitted to ICLR 2023 (2023)
Keywords: unstable reinforcement learning
LQR
optimization

Abstract:   For many of the reinforcement learning applications, the system is assumed to be inherently stable and with bounded reward, state and action space. These are key requirements for the optimization convergence of classical reinforcement learning reward function with discount factors. Unfortunately, these assumptions do not hold true for many real world problems such as an unstable linear–quadratic regulator (LQR). In this work, we propose new methods to stabilize and speed up the convergence of unstable reinforcement learning problems with the policy gradient methods. We provide theoretical insights on the efficiency of our methods. In practice, our method achieve good experimental results over multiple examples where the vanilla methods mostly fail to converge due to system instability.

Under review as a conference paper at ICLR 2023
ON THE FAST CONVERGENCE OF UNSTABLE REIN- FORCEMENT LEARNING PROBLEMS
Anonymous authors
Paper under double-blind review
ABSTRACT
For many of the reinforcement learning applications, the system is assumed to be inherently stable and with bounded reward, state and action space. These are key requirements for the optimization convergence of classical reinforcement learning reward function with discount factors. Unfortunately, these assumptions do not hold true for many real world problems such as an unstable linear- quadr-- regulator (LOR In this work, we propose new methods to stabilize and speed up the convergence of unstable reinforcement learning problems with the policy gradient methods. We provide theoretical insights on the efficiency of our methods. In practice, our method achieve good experimental results over multiple examples where the vanilla methods mostly fail to converge due to system instability.
INTRODUCTION
Reinforcement learning (RL), powered by the generalization ability of machine learning structures,
has been fairly successful in classical control tasks (Hafner & Riedmiller, 2011 Lillicra et al. (016) and problems like Atari (Mnih et al. (203)) and Go (Silver et al.) (016). RL aims to train policy to achieve maximum reward or minimize the cos which is similar to control theoretic approaches on designing controller. However, different from classical optimal control which requires full knowledge of transition dynamics, RL can learn the optimal policy from the past data directly by solving optimization problem without the knowledge of the underlying dynamics.
One of the mainstream methods to solve an RL problem is policy optimization via gradient descent. However, the convergence of the policy optimization algorithm heavily relies critical assumption of the system dynamics itself: stability In addition, to ensure the convergence of policy optimization, it requires the Lipschitz property of the cost function and its gradient. In fact, in many of the existing RI. benchmark examples such as OpenAl's classical control environments, the state space/actions/costs are clipped to ensure that the policy would never move extreme conditions and costs/states are bounded, in order to reduce the error derivatives (Mnih et al. 2015). Unfortunately, similar formulations are not directly applicable unstable systems, such as LQR with an unstable state matrix (i.e. the spectral radius of the state matrix is outside the unit circle), as the standard policy gradient based methods are likely to fail.
unapparent yet
Motivated by the above issue, in this paper we aim to enable and speed up the convergence of policy gradient methods for unstable RI. problems, we propose a logarithmic mapping method on loss functions supported by rigorous theoretical proofs and experimental results. The key contributions are summarized as follows.
We formally define the unstable RL problem in the scope "input-to-output stability, with the input actions leading to a temporal growing effect against cost output. This is the first
By unstable LQR mean the state transition matrix A in LQR (see Equation has spectral norm outside the unit circle.
Forr the rest part of this paper, we will use "minimizing cost" as objective since this is closely related to optimal control and optimization.
'In this paper. "stability" denotes "input-to-outyy (control action/state perturbation) will not lead to a large deviation in the system output cost. We use model-free methods in this paper, therefore the system output target is the cost function. For formal stability definition, please refer Section 3.1
stability, where a small perturbation of the input signal

---

Under review as a conference paper at ICLR 2023
time the convergence issue of unstable RL problems is studied, demonstrate that major issue for policy gradient methods on unstable RL problems is the slow convergence rate, which is the due to large spectral radius of the Hessian matrix.
We propose simple yet effective logarithmic mapping to alleviate this issue and speed up the convergence. We show both theoretical advantage and experimental results to support the contribution of faster convergence rate. Notably, our finite horizon problem setup does not require the bounded assumption cost function. The experiments cover LQR examples to customized nonlinear cases with neural network based policy.
We provide an efficient method to find a better initialization of control policy by optimizing it over the spectral norm of controlled system. We use it as a fast pre-processing step to effectively save the computation cost and allow larger learning rate for fast convergence.
2 BACKGROUND AND RELATED WORK
2.1 UNSTABLE DYNAMICAL SYSTEM
For many real-world unstable dynamical systems with limited explicit knowledge and practical aspects, system identification (SYSID) (Metllr et al. 1999 Ananth & Chidambaram 1999 Bond & Daniel 2008) with control (Jordan & Jacobs] 1990] Arora et al. 2011) is a 2-step approach to maneuver such system, where the SYSID step targets learning the system and the "control" step designs a controller to stabilize the system and minimize the cost. Despite most of the existing works focus the system instability itself, not many works realize the rise of optimization issues due to the diverging nature of the unstable system. [Shhaa & Doraiswami (2009) pointed out that the aforemennioned vanilla approach may fail the system identification due the rich sampling space required by unstable system and thus they proposed a close-loop algorithm to accommodate prior information into the identification process. [ar et al.] (2020) noticed the imbalanced sample influence of unstable systems and used a time-weight loss to alleviate the effect. With growing popularity of
application control/RL problems, the optimization issues from unstable systems naturally extend to many trending methods such as policy gradient. To the best of our knowledge, this work is the first attempt investigate the convergence issues of policy gradient algorithm on unstable systems and propose practical methods to alleviate this issue.
2.2 LQR PROBLEM
For a discrete-time linear system, its state equation is represented by:
I++1 Az Bu,
(1)
where, H, E R and u, R denote the system state and control action at time step A e R=*" and B Rexm are the system transition matrices. The feedback gain is parameterized by the matrix K Rmxn with
Krt-
(2)
The intermediate cost function is in the quadratic form of state Ty and control u, where Q E Raxx and Re IR" mm are given positive definite matrices to parameterize the quadratic cost. The optimal control problem can be formulated as minimizing the following target over K:
T
CK.T e E E
Σ 0=
x, Qu + un Rug
(3)
where V, = (A BK)'s, by plugging in u, = Kx, and D is the distribution of initial state. If co, then the problem is called infinite horizon LQR, otherwise when T is finite positive integer, it is called finte horizon LQR.
According Nise 2020), T-time-step system is controllable if reach any target state x² from any initial state Øo. The necessary and sufficient condition for controllability is that the controllability gramian is full rank, i.c..
rank([AT-11p) TT AB, B)) n,
2

---

Under review as a conference paper at ICLR 2023
where is the dimension of the state. In this paper, we assume the LQR is controllable. For unstable LQR in the infinite horizon, the cost function is not traceable since CK.7 - 0o when T - oc. To bypass this barrier, in this paper focus T steps, which is consistent with our unstable RL setup later. In practice, infinite horizon cases are similarly approximated by finite step trajectories (Fazel al. 20T8]) so that the implementations identical. To distinguish the finite horizon LQR setup in Hambly et al. (2021), we have the policy matrix K fixed along the trajectory instead of time-varying (Ke) for 0, 1, O,I,,.,,
finite horizon case and consider the cost for the first
2.3 CONVERGENCE OF POLICY GRADIENT METHODS
Despite the increasing popularity of policy gradient method, there has been little understanding on the convergence property of such methods. Only until recently, there are some work trying to tackle this problem from different perspectives. Zhang et al. (2019) proved the asymptotic convergence of policy gradient methods to stationary points, and later they extended the work and proposed MRPG (Modified Random-Horizon Policy Gradient) to almost surely converge actual local optimal policies (Zang et al.] 2020). [Bhandari & Russo (2019) studied the convergence rate for policy gradient methods under gradient dominance condition and they attained a linear convergence rate in Bhandari & Russo p) Agarwal et al. (2020) extensively studied the convergence rate under various combination of algorithms and function approximation for both first-order and quasi second-order policy gradient methods.
As special setting of RL, there a rising interest in studying the convergence of policy gradient method under LQR application. |Fazel et al. (2018) was the first to achieve the global convergence of policy gradient methods for Mhinite-horizon LQR problems, by proving the gradient domination and smoothness conditions. In their work, the infinite-horizon setup and smoothness/bounded cost assumptions are dependent on system stability, these assumptions no longer holds if A BK becomes unstable and objective function goes to infinity. In practice, the vanilla policy gradient method struggles to converge if the autonomous system is unstable, as we will also show in our experiments in Section 4.1 Bhandari & Russo 2019) extends the LQR setup more general class of control policies and identifies the structural conditions for convergence to optimal stationary point. Perdomo al. (202T) proposes to stabilize dynamical system with discounted annealing algorithm by gradually increasing discount factor 7 dependent on the system and current policy, which can ensure the boundedness of infinite-horizon system cost, In the scenario of finite horizon LQR and stochastic noise. Hambly et al. (2021) provides a global linear convergence guarantee. (Tu & Recht (2018) studied Least- Squarrs Temporal Difference (LSTD) method on LQR and number of samples needed for LSTD estimator of value function.
Nevertheless, all the above work require the assumption of the system to be stable under the policy throughout optimization, or equivalently, A - B3 K has a spectral radius less than 1. Unfortunately, with an unstable A and random initialization of policy K, this assumption is mostly invalid. contrast, our proposed algorithm target at finite horizon setup which shares an identical implementation with infinite horizon based methods but does not require this assumption at all.
PROPOSED METHODS
3.1 FORMULATING INSTABILITY
In the dynamical system literature, stability usually denotes input-to-state stable (ISS) (Sontag & Wang, 1995) in system dynamics, where small deviation of system state control action perturbation will not lead to dramatic change of future states. Formally, consider a general continuous dynamical system à fxx u) with continuously differentiable s(.) and z((1, Fo, u) denote the trajectory of x given initial condition Do and control feedback u. Then the system is ISS if there exist IC function 7 I + RR and K.C function 3 R² x R+ + Rt, s.t.
ISS:
[|,[(1, wo; wIll S >=) + 101.
(5)
where |/ul|0o supf [[u(t]]}} < de for t 2 0. Function 7(-) is called K. function if 7(-) is con- tinuously increasing and (0) = 0, 3(.,)) is called KCC function if B(,, t) is function for all the t 2 0.
3

---

Under review as a conference paper at ICLR 2023
In this paper, we refer to stability the poput-to-outpur (IO) stability (Sontag & Wang 1999). Let the output y = (x)(t) be a function of æ, for instance, y can be the quadratic function to regulate the error other system properties we wish stabilize. The system is input-to-output (I/O) stable if there exist K. function 7()) : IR+ - IR+ and K.C. function ((+,)) R+ x lR+ - IR+ s.t.
1/O stable:
(1 mu, 4 S +(11=1+=) + (l
(6)
Both ISS and I/O stability indicate bounded inputs leading to bounded system behavior, while there does not exist any causal relationship between the two with arbitrary choice of output function y(-). For further clarification, we provide linear system example in Appendix [A] In reinforcement learning setting, the "cost-to-go" but not necessarily the whole trajectory is always observable to the agent, because the returned cost serves as the evaluation metric for RI algorithm. Thus, I/O stability is a more suitable stability concept for analyzing general RL problems.
3.2 UNSTABLE RL PROBLEMS
Road-map for convergence rate analysis:
In this following. we formulate the unstable RL problems and provide a theoretical view of conver- gence rate bound under the vanilla setting and our proposed method. First, we formulate Markov decision process (MDP) problem with cost formulation in Assumption [32 where the cost function is allowed to exponentially grow against time with some base numbers {du}. corresponding to the base number C' in Equation (7). We also assume the Lipschitz property (Assumption and local strong convexity (Assumption 3.5) of such 6 against model parameter O. Based on the above assumptions, we derive the bound of the spectral norm for the Jacobian matrix of the cost function towards parameters (Theorem 3.9). For the optimization process, we view it as dynamical system, translating the necessary condition for monotonic decreasing as bounding the updating step by the inverse of the spectral norm. In order to satisfy such condition for convergence, the learning rate should be bounded and therefore the convergence rate is limited. The deterministic optimization results are summarized in Theorem 3.12 for vanilla policy gradient and in Theorem 3.15 for our proposed logarithmic mapping. The stochastic convergence results are discussed in Section defer most of the proofs to Appendix E. due to space constraints.
We
3.2.1 PROBLEM FORMULATION AND ASSUMPTIONS
To formulate the problem, consider a discrete-time continuous state MDP (S, ASS.PP.CC where S is the continuous state space, A is the continuous action space, P(*++ 18,, a) is the transition probability, ce(s, a) is the immediate cost at time step and so is the initial condition. Assume that the cost is upper bounded by polynomial of time step, s.t.,
(ca(s,)) a)l S DC
with positive constants D > O and C 0. The target to find an optimal policy to minimize the accumulated cost. When C < 1, the cost is bounded by D independent of l and the system is I/O stable with bounded output being the common setup for RL problems. In this work, we consider a more general setting without the upper bound on C. That is, the step cost could grow exponentially with time step f. potentially violating Equation (6) where ?[I[u||>>) being independent of
Remark 3.1. One way to solve the infinite horizon version of this problem is introducing a discount factor 7 strictly smaller than C. Then the problem could be formulated into classical bounded RL problem with finite expected cost return for infinite steps. However, if C' is much larger than 1, this approach does not work because the weights for future time-steps vanishes quickly. A corresponding experiment is shown in a later section (Section 4.1p
Instead, we formulate the problem into finite time horizon of finite time step T E Zt, with trajectory cost er (s, 8) as the value function of initial state s E IR" and policy parameter 0 e Rd.
Σ 10 =s) =))
UT (T(,, E (op(sr
(r) = EAND (s)
4

---

Under review as a conference paper at ICLR 2023
where (0) is the expectation of (s 8) over the initial state distribution and the optimization object. For a vanilla policy gradient method, we have update step:
0 + 0 (VVV
(8)
The gradient has Hessian matrix:
JT - (O))
(9)
Denote Pmaz (A) = max : is an eigenvalue of }} as the spectral radius of the state matrix A.
Pmin (A) min [|| is eigenvalue of A} as the smallest absolute value of eigenvalues.
Assumption 3.2. Assume (0) can be parameterized by basis function E(ee] ~ EE= (0)5
Φx (0) Σx=1 de /i (8)", where d2 > 0 and 0 I C < (x) S C.
Remark 3.3. The motivation of such basis functions is inspired by the departing output trajectories of unstable systems. Finite horizon LQR example is a special case of our formulation above, where the control matrix K and cost function CK.T corresponds the policy parameter 0 and cost function
(0), The LQR step cost x Qu, +u, Ru, can be rewritten as xo (A - BKY* (Q K RK) (A- BK) 2o. which is bounded by | 1=ol==1 | BK] The ||- B-BK| term corresponds to á in Assumption 3.2 with exponential growth with time step t and other terms remain positive constant. Therefore, the finite horizon LQR cost can be formulated into Assumption regardless of stability. The formulation is also valid for optimal control problems with polynomial cost functions or other unstable RI problems with exponentially growing cost as a function of time.
Assumption 3.4. Assume (0) is twice differentiable and Lipschitz, the gradient of (x) is also Lipschitz continuous, s.t.,
(ox( (0x) - 1 02 ll [(x((1) - ox (02) & L2 01 0211
for L1, L2 E RR, RR+00, 01 E Rd. Assumption 3.5. Assume local a-strong convexity of (f):
(O (0: + 02) 2 (0:) + 0g (0,) 2 =122112
for all the 01,02 02 E IRd and 0g = arg min (x)
BgRd
Remark 3.6. The strong convexity assumption is indeed a "strong" one for many of the unstable RL examples and policy basis functions. Even for the LQR problems, the cost function not global- convex (Fazel et al. 2018). The purpose of such assumption is to pave the path for convergence rate analysis. Here we argue that the initialization or the beginning epochs could lead the optimization into a local strong convexity, after which our convergence rate analysis is applicable. Like many other popular optimization methods in ML field such as gradient descent, we do not guarantee the algorithm's 's convergence to the global optimal. In practice, the stochastic gradient method could find a optr-altimal result.
3.2.2 CONVERGENCE RATE DERIVATION
Lemma 3.7. Update the value function VT by policy gradient method with 0 0- VoVT()) choose step size < 2/ max Pmon (Jr V Jr())), then Vr( is monotonically decreasing. EE(0.1]
Remark 3.8. The idea of Lemma 3.7 is inspired by Proposition 3.4 in Bertsekas & Tsitsiklis 1996).
With the quadratic approximation the value function, the proper step size is necessary condition for monotonically increasing because large steps are likely to overshoot. For a multi multi-dimension problem, the upper bound of the learning rate dependent on the "steepest" component corresponding to the spectral radius of the Jacobian matrix or the "smoothness" of the function. Different from the well-known convergence result of constant step size optimization for the global L-smooth function, the local smoothness between the two steps. In other words, the function is guaranteed to decrease if the step size 7 is small enough to ensure that: (a) the update step is small; and, (b) the Pmaz does not change too much.
5

---

Under review as a conference paper at ICLR 2023
Theorem 3.9. If Vr( satisfies Assumption 3.2 and Assumption 3.4 using the vanilla gradi-
ent descent algorithm from Equation (8 then Pmax (Jr(0))
k-= de L1 (E t0)
1= t(t
- 1(t (0)
Theorem 3.10. Suppose VT(0) satisfies Assumption 3.2 and Assumption
using the vanilla gradi- (0)=))+)) L2 ( t(t
3.4
ent descent algorithm from Equation (8). if < 1/ Σ k= dg L1 (E
(0)) then the update step requirement in Lemma satisfied.
3.7 for monotonic decrease of value function
By Theorem 3.10 we claim that to stabilize the convergence for the finite horizon unstable problem, the learning rate 1y needs to be smaller than the inverse of polynomial term of max (f)), otherwise the optimization is likely to diverge. At the beginning of optimization, when the system is not well controlled by the feedback policy, a small learning rate is needed. If fix or decaying learning rate scheduler is used, this constraint requiring small starting learning rate slows down the policy convergence in the later part of the optimization. Therefore, a customized learning rate which is dependent on the system "instability" is needed for fast and steady convergence.
Proposition 3.11. For lwice-diiferentiabll f. f is a-strong function if and only if V f(x) & al for some a > 0 and E Rd.
Proof. For twiee-differentiaale function, c-strong convexity is equivalent to the smallest eigenvalue of Hessian of f being lower bounded by a.
Theorem 3.12. Assume oN (0) is local strong convex as stated in Assumption 3.5 and the decreasing
learning rate 1j satisfies the conditions in Theorem 3.10 then if we run gradient descent for Vr(()), it
yields solution:
110: - 0-12 S 1'100 1.112
(10)
where v denotes the convergence rate and its square is lower bounded, 8.1., 2 (1
2w Pmoo (0,]
T
where w" = minn
d+l(
(()(())-)
k=0
LOGARITHMIC MAPPING OF FINITE HORIZON VALUE FUNCTION:
In the vanilla setup, the value function of gradient descent is (0). We propose logarithmic mapping,
Vr( (V)),,,
(11)
to regularize the spectral radius of gradient Jacobian and gradient variance. The sampled gradient approximation has the form of
V (0) = - Σ ())
(12)
Remark 3.13. Notice the unbiased estimation is in the form of log( ; Σ (r(s,, f)) instead of Equa- tion (2) We apply logarithm mapping in each realization reduce the stochastic variance for optimization consideration. Equation (12) can also be viewed as expectation of the stochastic realizations of (O)).
Theorem 3.14. Consider the parameterization of Vr((0) and Lipschitz condition in Assump- tion 3.2 and Assumption 3.4 if we run gradient descent for logarithm mapped (r) n Vr (0)/ Em dg [L [ tox (0) + L22 (T oo t(t 1) (0)))))) then the update step re- quirement Lemma 3.7 for monotonic decrease of value function is satisfied.
Proof. The update step under logarithmic mapping is,
- 0 0 V = =0
V+(0) (oV)(().
77
(13)

---

Under review as a conference paper at ICLR 2023
The learning rate 77 is equivalently normalized by (0) and by utilizing Theorem 3.10 we have the proof completed.
Theorem 3.15.
Assume (0) is local strong convex as stated in Assumption 3.5 and the decreasing learning rate Tn < T(--)- then running the gradient descent for logarithm mapped (--(0)
with Equation
13 Dyields a solution
- S q:10: - 0.11",
where the square of the step convergence rate qi has a varying lower bound s.1. 2 (1
200
Proce (rr())
Remark 3.16. Compared with Equation 15 the (moz(Jr(0)) (Jr(0)) term is proportional to the inverse of Pmoz
2w"a
current spectral radius instead of the maximum spectral radius throughout the optimization trajectory. Considering an unstable system initialized with random policy, the initial (JT (0n)) could be much larger than Pmaz (Jr( for Or in the later part of the optimization. Practically, using the
logarithmic mapping achieves much faster convergence rate.
3.3 STOCHASTIC CASE
The above convergence rate analysis is based on deterministic optimization. The convergence of stochastic sampled gradient method with a diminishing learning step. provided in Theorem E,,8 and Theorem E.9 are deferred to Appendix As the proof sketch, first assume small i...d. noise for the realization of Φu (0) and its gradient (Assumption E.4). then get the variance of updating step (Lemma D.5 and Lemma E.6) followed by stochastic convergence proof. We also discuss the stochastic convergence rate under fix learning step setup.
3.4 REGULATING SPECTRAL RADIUS AS FAST PRE- PROCESSING
When an unstable system is controlled by random policy and initialized by arbitrary condition, the internal states/outputs will most likely grow unboundedly due to the system instability. In many of the RI. scenarios, agent stability is required but usually neglected property for optimal or near- optimal solutions. For discrete linear system, the spectral radius (largest absolute value of system cigenvalues) being strietly less than 1 is a sufficient condition for exponential stability. For non-linear systems without an explicit form of state transition matrix, we expect the next time step state norm does not deviate function from initial policy. To speed up the optimization, we propose a fast pre- pre-processing method by finding a policy close to the stable zone. The algorithm is shown in Algorithm I In the pre-process, we neglect the value function and only regulate the spectral radius of the system dynamics estimated by power iteration.
much from the current step. It is computationally costly optimize the value
Algorithm 1 Regulating system spectral norm by power iteration
Input: system state transition function f, finite time step T, batch size Initialize policy parameter 0
f = N do
Sample (=f.....6.....)))
Loss +-
for 0 to 1' do
for = 1 to b parallel do
2+1 < fa 8)
Loss Loss max |
||
1,0)
end for end for Loss + Loss/b
Update parameters: 0 + v)V Loss
end for Output: policy parameter 0
7

---

Under review as a conference paper at ICLR 2023
Algorithm 2 Policy Gradient for LQR
system state transition matrix A and B, quadratic cost matrix Q and R, finite time step T, batch size b, discount factor y Initialize policy matrix Ko
Input:
for = to N do Sample {=p....g....2
V < 0
for = to parallel do
for = 0 to T do
u, f- Kx²
4 t Ari + But
V+ V + taa Qut + ut Rui)
end for end for
V < V/b
Update parameters: K K -VVVV
end for
Output: policy matrix K
4 EXPERIMENTS
In this section, we use LQR as illustrative examples to demonstrate the efficacy of our methods. We also apply these methods to general unstable RL applications in continuous control and defer the results to Appendix [D] Note that our implementation of policy gradient methods, we assume the gradient from penalty towards model parameters is directly accessible, despite of the implicit environment dynamics to the optimization process. With the focus of the paper being on the controller decision for the system, our implementation trains a deterministic actor model instead of a full actor-critic model. We bypass the critic modeling with a directly approximated critic function, but methods could be extended to more general RL algorithm such as actor-critic.
4.1 LQR
The IQQ system matrices A, and positive-definite cost matrices Q. R are randomly generated. To regulate the "instability" of the autonomous system, the spectral radius of A can be manipulated by multiplying the original random matrix with ratio between the desired spectral radius and that of the original random matrix. A vanilla LQR policy gradient method is shown in Algorithm 2 In each batch, we run 10 fixed time steps from 300 random initial states. For each experiment, we run 3 random seeds for reproducibility. We use Pytorch (Paszke et al., 2019) as the optimization platform and carry all the simulations on single CPU since the tasks are relatively light-duty.
Figure a shows the vulnerability of optimization for unstable systems with large learning rates. For Pmoz (A) 0.5 and 1, the model is trainable across all the learning rates, where larger learning rates lead to smaller losses after 100 epochs. For Pmaz (A) = 1.5, the largest 2 learning rates could crash the optimization and only the smallest learning rate works for Pmaz (A) 2. The observation is consistent with Lemma 3.7s s claim that the optimization step size should be bounded for training stability. However, small learning rate could result in slow convergence. Therefore, the major challenge for vanilla policy gradient method on unstable RL problem is how to find an optimal learning rate without crashing the optimization. In our experiments, log intervals such as {le-1, 1e-2, and select the largest one without breaking the optimization (if any of random experiments fails, we consider that the optimization failed and then use smaller learning rate).
test different learning rates by
In Figure pp we compare the vanilla gradient method and its variants with our proposed logarithmic mapping. The subplots are normalized cost difference towards optimal, normalized policy difference to the optimal and estimated spectral norm by power iteration, respectively. Note that the y-axis of the cost figure is log scale. The optimal policy K* is,
K' (B PB R B PA,
8

---

Under review as a conference paper at ICLR 2023
where P is the solution to the infinite horizon algebraic Riccati equation,
P= P= AT (P- P + R) P) + Q.
Because the sampled cost is approximated by rolling out from many random initial states, it could be smaller than theoretical cost". Therefore, the cost difference plot could disappear in the log scale when the solution is very close to optimal policy. Besides, we only draw the seed variance above the value mean in the log scale for clear visualization.
When optimizing the model with vanilla sum loss function from random initialization without any pre- processing, the system starts from an extremely unstable condition with large cost. From Lemma 3.7 small learning rate is needed when the system is unstable with control policy parameters. In practice, le-14 is the maximum learning rate to accommodate the instability with 1e-13 crashing the optimization. If we an efficient policy pre-process with total of 300 episodes, could use 1e-8 as learning rate. During the optimization, the controller gradually stabilizes and the fixed learning rate is then too small for further parameter update. The policy and corresponding cost move very slowly to optimal and almost stagnate at certain point, and optimization is impractical. We also tested other discount factor such as y 0.5 to shrink the cost and allow a larger learning rate 1e-7, but this method also fails because the small fy neglects the long term effect of the dynamics with spectral radius reaching 2. Combining our proposed pre-process and log mapped loss function, we are able to use 1e-2 learning rate and both cost and policy parameters approach optimal quickly.
Audit
10
10-3
optimization fails
1.0
200
600
500
B00
1000
10P
0.5
10
0.0
8
109
5
2.0
2.0
10" 10
10
10
0.5
600
1000
Seariing
boch
(a) Vanilla PG LQR loss difference optimal after 100 epochs under different learning rates and spectral radius (missing point for Pmnz 1.5, 2 means the cost goes to NaN when optimization crashes)
(b) LQR loss difference to optimal: vanilla loss vs log mapping, Pmuee (A) = 5. Combining log- arithmic mapping and pre-processing, our method reaches near optrmmltimal solution quickly and other methods are likely to diverge.
Figure 1: LQR experiments
Other than Pmaz (A) case, we further conducted experiments with Pmoz (A) and Pmoaa (A) 10 and defer them to Appendix
5 CONCLUSION AND FUTURE WORK
This paper focuses on the gradient-basee based optimization for special branch of RL problems. Due to the unstable nature of the system, small deviation leads to exponentially growing effects on the state evolution trajectory and the reward/cost function, which raises issues for gradient-based optimizations. We proposed two methods to alleviate the effect of instability and their effectiveness is validated from both theoretical and experimental points of view.
Regarding the future work, proving the global convergence our finite horizon setup is needed to extend (Fazel et al. 2018)'s 'ss work to unstable cases. In this paper, we examine the experiments only on model-free RL where the reward functions are directly approximated. Our methods has the potential to be applied to other RL algorithms such actor-critic. In addition, for model- -ased RL, coupling stability regularization into the dynamics modeling could be another path to tackle the unstable RI. problems.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in markov decision processes. In Conference on Learning Theory, pp. 64-66. PMLR, 2020.
I. Ananth and Manickam Chidambaram. Closed-loop identification of transfer function model for unstable systems. Journal of the Franklin Institute, 336(7):1055-1061, 1999.
Ashish Arora, Yogesh V. Hote, and Mahima Rastogi. Design of pid controller for unstable system. In Control, Computation and Information Systems, 2011.
Dimitri Bertsekas, Incremental gradient, subgradient, and proximal methods for convex optimization:
A survey. Optimization, 2010(1-38)3,, 2011.
Dimitri Bertsekas and John N Tsitsiklis. Neuro-dynamic programming. Athena Scientific, 1996.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. arXiv preprint FrXiv:1906.01780 2019.
Jalaj Bhandari and Daniel Russo. On the linear convergence of policy gradient methods for finite mdps. In International Conference on Artificial Intelligence and Statistics, pp. 2386-2394, PMLR, 2021.
Bradley N Bond and Luca Daniel. Guaranteed stable projection-based model reduction for indefinite and unstable linear systems. In 2008 IEEE/ACM International Conference on Computer-Aided Design, pp. 728-735. IEEE, 2008.
Maryam Fazel, Rong Ge, Sham M. Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. In International Conference on Machine Learning, pp. 1467-1476. PMLR, 2018.
Roland Hafner and Martin Riedmiller. Reinforcement learning in feedback control. Machine Learning, 84(1-2))137-169 2011.
Ben Hambly, Renyuan Xu, and Huining Yang. Policy gradient methods for the noisy linear quadratic regulator over a finite horizon. SIAM Journal on Control and Optimization, (9(5):3359-339) 2021.
Michael Jordan and Robert Jacobs. Learning to control an unstable system with forward modeling. In Advances in Neural Information Processing Systems, volume 2. Forgan-Kaufman 1990.
Timothy P. Lillicrap. Jonathan J. Hunt, Alexander Pritzel, Nicolas Manfred Otto Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv: (et.:00999.291 2016.
Feng Lin, W. Zhang, and R.D. Brandt. Robust hovering control of a pvtol aircraft. IEEE Transactions on Control Systems Technology, 733:3433-35,, 1999, doi: 10.1 16518477776....
Bernard Mettler, Mark B Tischler, and Takeo Kanade. System identification of small-size unmanned helicopter dynamics. In Annual Forum Proceedings- American Helicopter Society, volume 2, pp. 1706-1717. Citeseer, 1999.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 1rXiv:1312.5602, 2013.
Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattic, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):529-535 2015.
Kamil Nar, Yuan Xue, and Andrew M. Dai. Learning unstable dynamical systems with -ime-weighted logarithmic loss. arXiv preprint arXiv:2007.05 189, /89, 2020.
10

---

Under review as a conference paper at ICLR 2023
Lam Nguyen, Phuong Ha Nguyen, Marten Dijk, Peter Richtárik, Katya Scheinberg, and Martin Takác. Sgd and hogwild! convergence without the bounded gradients assumption. International Conference Machine Learning, pp. 3750-3755 PMLR, 2018.
Norman S Nise. Control systems engineering. John Wiley Sons, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vitito Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019.
Juan C. Perdomo, Jack Umenberger, and Max Simchowitz. Stabilizing dynamical systems via policy gradient methods. NeurIPS, 2021.
Mohammad Shahab and Rajamani Doraiswami. Identification of a class of unstable processes. In 2009 5th IEEE GCC Conference Exhibition, pp. 1-4, 2009. doi: 10.1 101//E/EECC.22009957722222
David Silver, Aja Huang, Christopher Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schritwieser, Ioannis Antonoglou, Veda Pannerrshelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529:484 503, 2016.
Eduardo D. Sontag. Input to State Stability: Basic Concepts and Results. 2008.
Eduardo D Sontag and Yuan Wang. On characterizations of the input-to state stability property. Systems & Control Letters, 24(5):351-359, 1995.
Eduardo D. Sontag and Yuan Wang. Notions of input to output stability. Systems
& Control Letters, 38(4):235-22) 248. 1999. ISSN 0167-6911. doi: https://doi.or//10 1016680167-69111199000773
URL https::
www.aaitttttttttttteoooeoooeeeee peon/science//
article/pii 67691 59000705
Stephen Tu and Benjamin Recht. Least-Squares Temporal Difference Learning for the Linear Quadratic Regulator. In Proceedings of the 35th International Conference on Machine Learning. pp. 5005-5014. PMLR, 2018
Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Başar. Convergence and iteration complexity of policy gradient method for on Decision and Control (CDC), pp. 7415-7422, 2019. doi: 10.1009/CDC40024220999999 9000000.
reinforcement learning. In 2019 IEEE 58th Conference
Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Basar. Global convergence of policy gradient methods (almost) locally optimal policies. SIAM Journal Control and Optimization, 58(6): 3586-3612, 2020.


Reviews:
[{"review_id": "Owh4PI2x3u", "reviewer": "Reviewer_1dw6", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper analyzes the convergence of policy gradients on I/O unstable problems, in particular unstable LQR problems. Under a variety of assumptions, the authors claim to proof an bound on the learning rate, related to the largest spectral eigenvalue of the dynamics matrix of LQR. Experiments show that a log mapping of the objective stabilizes gradient descend on LQR's policy matrix K.", "summary_of_the_review": "I admit that I was not able to follow the paper. I am uncertain whether this is the fault of the paper or mine. While I recommend to reject the paper, I am happy to change my mind if more qualified reviewers think the paper deserves publication.\n\n**Post-rebuttal**\n\nI thank the authors for their attempt to explain their paper, but I still feel that I do not understand the paper enough to give a certain recommendation. Due to this uncertainty I retain my previous recommendation to reject the paper.", "strength_and_weaknesses": "I have to admit that I did not understand this paper. In particular, I cannot say how realistic Assumption 3.2 is, and how Theorems 3.14 and 3.15 proof stability. However, the experimental results look good, even though I find it hard to say how general they are.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JaZEfDJZOR", "reviewer": "Reviewer_xiDA", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper considers gradient descent algorithms for computing a parameter of the optimal policy according to a possibly unstable trajectory of a Markov decision process. It is shown that under technically strong assumptions such as continuity, convexity, and smoothness, the rates of convergence will be linear, assuming that the horizon is short enough. ", "summary_of_the_review": "I prefer to give the authors a chance to see how they can convince the reviewers that their paper is interesting, important, and innovative. \n\n--------------------------------\npost rebuttal: this reviewer carefully read the rebuttal and updated the review. ", "strength_and_weaknesses": "I like the general idea of the paper; it has an understandable approach and puts forward an interesting and to some extent important problem. The writing in most of the manuscript is acceptable, but some improvements help. The technicalities seems based on strong assumptions though.\n\nThe deterministic nature of the dynamics restricts applicability of the approach to data-driven problems. Also importantly, in case of randomly or adversarially disturbed dynamics, the stabilization needs to be different since other than the initial state, the innovation can cause instability. Although the authors claim that the method is applicable to disturbed dynamics, the analysis does not seem so. Further, the existing literature of learning-based stabilization is not covered (enough). The setting and analysis of the GD does not seem innovative and seems a little artificial. The enumeration looks strange. In some places the language is not articulate enough, e.g., in Lemma 3.7. \n\nThe technical assumptions, e.g., 3.3 and 3.4, are a little restrictive and seem consequential. So, I think further justifications and intuitive arguments are needed. Importance of the main results Thm 3.9 and 3.10 are not clear, and it is also unclear what technical difficulties need to be addressed to obtain them. Finally, considering the step size upper bounds, applicability of the algorithms to only small time horizons renders the framework limited in the sense that the step size will be so small that the method will have no superiority to other learning based stabilization approaches, even if it is somehow applicable. \n\nThe edits the authors provided in the resubmitted version do not seem adequate. I suggest the authors to do further rewrites and to go deeper for proving interesting results.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0BVT35M-ki", "reviewer": "Reviewer_tyRg", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper focuses on the gradient-based optimization for a special branch of RL problems. Due to the unstable nature of the system, small deviation leads to exponentially growing effects on the state\nevolution trajectory and the reward/cost function, which raises issues for gradient-based optimizations. The authors proposed two methods to alleviate the effect of instability and their effectiveness is validated from\nboth theoretical and experimental points of view.", "summary_of_the_review": "This paper focuses on the gradient-based optimization for a special branch of RL problems.\nOverall, the paper seems to contain interesting results. \nThe presentations need to be improved as mentioned in the previous comments. ", "strength_and_weaknesses": "Overall, the paper seems to contain interesting results. \nSome comments to improve the paper are summarized below:\n1) For an MDP with finite and discrete state and action spaces, the stable MDP is not clear. \nOnly for MDPs with continuous state and action spaces, that are main focus of the paper, stability is meaningful. \nIn abstract and introduciton, the system is not clearly indicated, and hence, it is very confuzing at the beginning on what stability means for MDPs.\nTherefore, it would be better to indicate that the system is an MDP with continuous spaces at the beginning. \n2) In assumption 3.2, it is not clear what is the basis function. In the explanation after assumption 3.2., it says that || A-BK||^2 corresponds to \\phi. \nHowever, || A-BK||^2 is scalar number, while \\phi needs to span the function space. This discussion seems to be unreasonable. \n3) The convergene results in Theorem 3.9 and Theorem 3.10 are not clear. It is not clear why the inequality leads to convergence. Some improvement of presentation may be needed.\n4) It would be better to indicate earlier in section 3.2.2. that the results are all for deterministic settings.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject