{'fraction_non_alphanumeric': 0.0512831074679738, 'fraction_numerical': 0.016352926638382007, 'mean_word_length': 4.131684633269922, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Complete stability analysis of a heuristic ADP control design

This paper provides new stability results for Action-Dependent Heuristic Dynamic Programming (ADHDP), using a control algorithm that iteratively improves an internal model of the external world in the autonomous system based on its continuous interaction with the environment. We extend previous results by ADHDP control to the case of general multi-layer neural networks with deep learning across all layers. In particular, we show that the introduced control approach is uniformly ultimately bounded (UUB) under specific conditions on the learning rates, without explicit constraints on the temporal discount factor. We demonstrate the benefit of our results to the control of linear and nonlinear systems, including the cart-pole balancing problem. Our results show significantly improved learning and control performance as compared to the state-of-art.


Introduction
Adaptive Dynamic Programming (ADP) addresses the general challenge of optimal decision and control for sequential decision making problems in real-life scenarios with complex and often uncertain, stochastic conditions without the presumption of linearity. ADP is a relatively young branch of mathematics; the pioneering work (Werbos, 1974) provided powerful motivation for extensive investigations of ADP designs in recent decades ( ). ADP has not only shown solid theoretical results to optimal control but also successful applications (Venayagamoorthy & Harley & Wunsch, 2003). Various ADP designs demonstrated powerful results in solving complicated real-life problems, involving multi-agent systems and games (Valenti, 2007 The basic ADP approaches include heuristic dynamic programming (HDP), dual heuristic dynamic programming (DHP) and globalized DHP (GDHP) (Werbos, 1974(Werbos, , 1990; White & Sofge, 1992; Prokhorov & Wunsch, 1997). For each of these approaches there exist an action-dependent (AD) variation (White & Sofge, 1992 A classical method of investigating stability of dynamical processes is based on the Lyapunov approach. Here we are addressing a discrete time dynamical system, where the dynamics is described by a difference equation. The discrete time Lyapunov function is used to prove the stability of the controlled process under certain conditions. In this paper we generalize the results of (Liu, Sun, Si, & Guo & Mei, 2012) for deriving stability conditions for ADHDP with traditional three layer multi-layer perceptron (MLP). The work ) derives a stability condition for the system with weights adapted between the hidden and output layers only, under the assumption that networks have large enough number of neurons in the hidden layers.
The issue of how to approximate J * or J is one of the fundamental issues in ADP. The approach presented in , in effect, is equivalent to a linear basic function approach: it is easy but it leads to scalability problems. The complexity of the system is growing exponentially for the required degree of approximation of a function of given smoothness (Barron, 1994). Additional problems arise regarding the accuracy of parameter estimation, which tends to grow with the number of parameters, all other factors are kept the same. If we have too many parameters for a limited set of data, it leads to overtraining. We need more parsimonious model, capable of generalization, hence our intention is to use fewer parameters in truly non-linear networks, which is made possible by implementing more advanced learning algorithm. The present work investigates the stability property of the ADP system with MLP-based Critic, where the weights get adapted between all layers (including weights between input and hidden layers). By using Lyapunov approach, we study the uniformly ultimately bounded property of the ADHDP design. Preliminary results of our generalized stability studies have been reported in (Kozma & Sokolov, 2013), where we showed that our general approach produced improved learning and convergence results, especially in the case of difficult control problems.
The rest of the paper is organized as follows. First we briefly outline theoretical foundations of ADP and its various implementations. Next we describe the learning algorithm based on gradient descent in the Critic and Action networks. This is followed by the statement and the proof of our main results on the generalized stability criteria of the ADP approach. Finally, we illustrate the results using the examples of two systems. The first one is a simple linear system used in , and the second example is the inverted pendulum system, similar to (He, 2011).

Theoretical foundations of ADHDP control
2.1. Basic definitions. Let us consider a dynamical system (plant) with discrete dynamics, which is described by the following nonlinear difference equation: where x is the n × 1 plant state vector and u is the m × 1 control (or action) vector. Previously we reported some stability results for ADP in the general stochastic case (Werbos, 2012). In this paper we focus on the deterministic case, as described in equation (2.1) and introduce action-dependent heuristic dynamic programming (ADHDP) to control this system. The original ADHDP method has been used in the 1990's for various important applications, including the manufacturing of carbon-carbon composite parts (White & Sofge, 1992). ADHDP is a learning algorithm for adapting a system made up of two components, the Critic and the Action, Figure 1. Schematics of the implemented ADHDP design as shown in Fig. 1. These two major components can be implemented using any kind of differentiable function approximator.
In this work we use MLP as the universal function approximator (Barron, 1993;1994). The optimal value function, J * of the Bellman equation (White & Sofge, 1992), is a function of the state variables, but not of the action variables. The J function is closely related to J * function, but it is a function of both the state and the action variables. The Critic estimates a cost-to-go or value function J in the Bellman equation of dynamic programming. The function Q, used in traditional Q-learning (Si et al., 2004) is the discrete-variable equivalent of J .
The Action network represents a control policy. Each combination of weights defines a different controller, hence by exploring the space of possible weights we approximate the dynamic programming solution for the optimal controller. In the ADHDP the cost function is expressed as follows: where α is a discount factor with 0 < α < 1 and r(t) is the utility function or reinforcement signal. We require r(t) to be a bounded semidefinite function of the state x(t) and control u(t) so that the cost function is well-defined. It is easy to see from (2.2) that 0 = αJ (t + 1) + r(t) − J (t).
2.2. Action network. Next we introduce each component, starting with the Action component. The Action component will be represented by a neural network (NN), and its main goal is to generate control policy. For our purpose, MLP with one hidden layer was used. At each time step this component needs to provide an action based on state vector x(t) = (x 1 (t), . . . , x m (t)) T , so x(t) is used as an input for the Action network. If the hidden layer of the Action MLP consists of N ha nodes; the weight of the link between the input node j and the hidden node i is denoted bŷ w aij (t), for i = 1, . . . , N ha and j = 1, . . . , m. The weighted sum of all inputs, i.e., the input to a hidden node k is given as σ a k (t) = m j=1ŵ (1) a kj (t)x j (t). The output of hidden node k of the Action network is denoted by φ a k (t) = 1−e −σa k (t) 1+e −σa k (t) . Here hyperbolic tangent is used as transfer function.ŵ (2) aij (t), where i = 1, . . . , n, j = 1, . . . , N ha is the weight from j s hidden node to i s output. Finally, the output of the Action The diagram of the Action network is shown in Fig. 2. 2.3. Critic network. The Critic neural network learns to approximate J function and it uses the output of Action network as one of its inputs. This is shown in Fig. 3. The input to the Critic network is y(t) = (x 1 (t), . . . , x m (t), u 1 (t), . . . , u n (t)) T , where u(t) = (u 1 (t), . . . , u n (t)) T is output of the Action network. Just as for the Action NN, here we use an MLP with one hidden layer, which contains N hc nodes.ŵ (1) cij (t), for i = 1, . . . , N hc and j = 1, . . . , m + n is the weight from j s input to i s hidden node of Critic network. Here hyperbolic tangent transfer function is used. For convenience, the input to a hidden node k is split in two parts with respect to inputs σ c k (t) = m j=1ŵ (1) c i(m+j) (t)u j (t). The output of hidden node k of the Critic network is given as φ c k (t) = 1−e −σc k (t) 1+e −σc k (t) . Since the Critic network has only one output, we have N hc weights between hidden and output layers of the formŵ (2) ci (t). Finally, the output of the Critic neural network can be described in the formĴ(t) = N hc i=1ŵ

Gradient-descent Learning Algorithm
3.1. Adaptation of the Critic network. Let e c (t) = αĴ(t + 1) + r(t) −Ĵ(t) be the prediction error of the Critic network and E c (t) = 1 2 e 2 c (t) be the objective function, which must be minimized. Let us consider gradient descent algorithm as the weight update rule, that is,ŵ c (t + 1) =ŵ c (t) + ∆ŵ c (t). Here the last term is ∂ŵc(t) and l c > 0 is the learning rate. By applying the chain rule, the adaptation of the Critic network's weights between input layer and hidden layer is given as follows ∆ŵ Application of the chain rule for the adaptation of the Critic network's weights between hidden layer and output layer yields ∆ŵ Adaptation of the Action network. The training of the Action network can be done by using the backpropagated adaptive critic method (White & Sofge, 1992), which entails adapting the weights so as to minimizeĴ(t). In this paper we used an importance-weighted training approach, where we minimized error measure of the form E a (t) = 1 2 e 2 a (t), and e a (t) =Ĵ(t) − U c is the prediction error of the Action NN, for the sake of it is stability properties.
Let us consider gradient descent algorithm as the weight update rule, that is, w a (t+1) =ŵ a (t)+∆ŵ a (t), where ∆ŵ a (t) = l a − ∂Ea(t) ∂ŵa(t) and l a > 0 is the learning rate.
By applying the chain rule, the adaptation of the Action network's weights between input layer and hidden layer is given as ∆ŵ where Using similar approach for the Action network's weights between hidden layer and output layer, finally we get the following ∆ŵ

Lyapunov stability analysis
In this section we employ Lyapunov function approach to evaluate the stability of dynamical systems. The applied Lyapunov analysis allows to establish the UUB property without deriving the explicit solution of the state equations.

4.1.
Outline of the Lyapunov approach. Let w * c , w * a denote the optimal weights, that is, the following holds: w * c = arg minŵ c αĴ(t + 1) + r(t) −Ĵ(t) ; we assume that the desired ultimate objective U c = 0 corresponds to the success then w * a = arg minŵ a Ĵ (t) .
Consider the weight estimation error over full design, that is, over both Critic and Action networks of the following form:w(t) :=ŵ(t) − w * , then based on (3.1), (3.2), (3.4) and (3.5) we can define dynamic system of estimation errors as follows (4.1) Definition 1. A dynamical system is said to be uniformly ultimately bounded with ultimate bound b > 0, if for any a > 0 and t 0 > 0, there exists a positive number For further investigation, let us state a theorem without proof, for readers interested in the details we suggest to look at (Sarangapani, 2006;Michel & Hou & Liu, 2008). Theorem 1. If, for system (4.1), there exists a function L(w, t) such that for all w(t 0 ) in a compact set K, L(w(t), t) is positive definite and the first difference, is contained in K, then the system is UUB and the norm of the state is bounded to within a neighborhood of b.
Based on this theorem, that gives a sufficient condition, we can determine the UUB property of the dynamical system selecting an appropriate function L. For this reason, we first consider all components of our function candidate separately and investigate their properties, and thereafter we study the behavior of L function to match the condition from theorem 1.

Preliminaries.
Assumption 1. Let w * a and w * c be the optimal weights for Action and Critic networks. Assume they are bounded, i.e., w * a ≤ w max a and w * c ≤ w max c . Lemma 1. Under Assumption 1, the first difference of L 1 (t) = 1 lc tr w is the approximation error of the output of the Critic network.
Proof. Using (3.2) and taking into account that w * (2) c does not depend on t, i.e., it is optimal for each time moment t, we get the following Based on the last expression, we can find the trace of multiplication ofw (2) c (t+1) by itself in the following way: Sincew (2) c (t)φ c (t) is a scalar, we can rewrite the middle term in the above formula as follows: Here the definition ofw is applied to obtain the above expression. Now let us consider the first difference of L 1 (t) in the form Substituting the results for w (2) c (t + 1) Tw (2) c (t + 1), finally we get the statement of the lemma, as required.
Proof. Let us consider the weights from the hidden layer to output layer of the Action network which are updated according to (3.5) Based on this expression, it is easy to see that tr (w (2) a (t + 1)) Tw(2) a (t + 1) = (w (2) a (t)) Tw(2) a (t) + (4.9) Here the last formula is based on the assumption that all vector multiplications are under trace function. Now let us consider the first difference of function L 2 (t), that is, the following expression After substituting the appropriate terms in the last formula, we get Consider the last term of (4.11) After substituting this formula into ∆L 2 , we get (4.14) Finally we get the following bound for ∆L 2 (t), as required: (4.15) Remark 1. If we introduce the following normalization for the network's weights (ŵ where γ 2 > 0 is a weighting factor and a i (t) = 1 2 1 − φ 2 ci (t) ŵ Proof. Let us consider the weight update rule of the Critic network between input layer and hidden layer in the form ci (t)y j (t), for i = 1, . . . , N hc , j = 1, . . . , m + n. Following the same approach as earlier, we can expressw For convenience, we introduce the following notation for our study B T (t)B(t) = y T (t)a T (t)a(t)y T (t) = a(t) 2 y(t) 2 . Then the trace of multiplication can be written as Using the property of trace function, i.e. the following tr y(t)a T (t)w  c (t)y(t)a T (t) , we can express the last term of (4.19) as follows: Therefore, using (4.19), (4.20), the first difference of L 3 (t) can be bounded by where γ 3 > 0 is a weighting factor; and D ij (t) = 1 2 1 − φ 2 ai (t) ŵ (2) aji (t) for i = 1 . . . N ha and j = 1 . . . n.
Proof. Let us consider the weights from the input layer to the hidden layer of the Action networkw Let us consider Based on the last result, we can obtain the upper bound for ∆L 4 (t), which is given the statement of the lemma: (4.26) 4.3. Stability analysis of the dynamic system. In this section we introduce a candidate of Lyapunov function for analyzing the error estimation of the system. To this aim, we utilize the following auxilary function L = L 1 + L 2 + L 3 + L 4 .
Theorem 2. Let the weights of the Critic network and the Action network are updated according to the gradient descent algorithm, and assume that the reinforcement signal is a bounded semidefinite function. Then under Assumption 1, the errors between the optimal networks weights w * a , w * c and their estimatesŵ a (t),ŵ c (t) are uniformly ultimately bounded (UUB), if the following conditions are fulfilled: Therefore, (4.32) In particular, γ 2 > α. Similarly, for the Action network we obtain: (4.34) In particular, γ 3 > γ 1 . Notice that the norm of sum can be bounded by sum of norms, thus we have the following , a(t), D(t), correspondingly. Finally we get: Therefore, if α 2 − 4 γ1 > 0, that is, γ 1 > 4 α 2 and α ∈ (0, 1), then for l a and l c with constraints from (4.32), (4.34) and ζ c (t) , we get ∆L(t) < 0; this means that the system of estimation errors is ultimately uniformly bounded.

4.4.
Interpretation of the results. It is to be emphasized that present results do not pose any restrictions on the discount factor α, as opposed to . The choice of the discount factor depends on the given problem and the absence of any constraints on this factor is a clear advantage of our approach. A constraint on the discount factor can reduce the performance of the design. Also it should be mentioned that parameters γ 1 , γ 2 , and γ 3 allow fine-tuning of the learning in different layers of the networks, thus leading to further improved performance. Further consequences of this advantage will be the subject of our future research.

Simulation study
In this section, we consider two examples and compare our results with previous studies. In our case, we allow adaptation in the whole MLP, and denote this approach AdpF ull. Previous studies by  employ partial adaptation in the output layers only, so we call it AdpP art. We use a relatively easy example for a linear system, similar to , to demonstrate the similarity between AdpF ull and AdpP art. Then we introduce a more complicated example, to demonstrate the advantages of the more general results by AdpF ull.
5.1. Linear problem. Following (Liu et al., 2012), we consider a system described by the linear discrete time state-space equation of the form: We apply ADHDP to stabilize this system. For this purpose we utilize two neural networks, the parameters of which match the condition of Theorem 2. In the implementations we use MATLAB environment. We choose the discount factor as follows α = 0.9. The number of nodes in the hidden layer of both networks are set to N hc = N hc = 6. In the training process, the learning rates are l c = l a = 0.1. Like in , the initial state is chosen as x(0) = 1, and the weights of both Critic and Action networks are set randomly. The reinforcement learning signal is of the form r k = 0.04x 2 k + 0.01u 2 k . The convergence of the state, control and cost-to-go function for approaches from this paper and  are shown in Fig. 5 and Fig. 6, correspondingly. At each time step, we perform a fixed number of iterations to adapt the Critic and Action networks. The number of internal iterations are selected according to the given problem. In the case of the linear control we chose smaller number of iterations (up to 50), while for more difficult problems we have 100 iterations.
After learning is completed, we fix weights of both networks and test the controller. Additionally, we compare performance of the controller with that in . The corresponding graphs are shown in Fig. 7 and in Fig. 8. Our results show that AdpF ull and AdpP art control system perform similarly and they reach the equilibrium state fast, within 5 time steps. Detailed analysis shows, that AdpF ull reaches the target state in average one step earlier.

5.2.
The cart-pole balancing problem. We present the case of a nonlinear control problem to illustrate the difference between our current study and previous approaches . We consider the cart-pole balancing problem, which is a very popular benchmark for applying methods of ADP and reinforcement learning (He, 2011). We consider a system almost the same as in (He, 2011); the only difference is that for simplicity we neglect friction. The model shown in Fig. 4 can be describe as follows   Figure 8. The state trajectory (x) and control action (u) for the linear system Eq. 5.1 using AdpP art learning method.
where g = 9.8 m/s 2 , the acceleration due to gravity; m c = 1.0 kg, the mass of the cart; m p = 0.1 kg, the mass of the pole; l = 0.5 m, the half-pole length; F = ±10 N, force applied to cart center of mass. This model has four state variables (θ, x(t),ẋ,θ), where θ is the angle of the pole with respect to the vertical position, x(t) is the position of the cart on the track,ẋ is the cart velocity andθ is the angular velocity.  Figure 9. Simulated results of balancing the inverted pendulum using stability criteria due to: (a) AdpF ull learning method; initial angle is θ = 0.85; (b) AdpP art learning method; initial angle is θ = 0.85; (c) AdpF ull learning method; initial angle is θ = 2; (d) AdpP art learning method; initial angle is θ = 2.
In our current simulation, a run includes 100 consecutive trials. A run is considered successful if the last trial lasted 600 time steps where one time step is 0.02 s. A trial is a complete process from start to fall. System is considered fallen if the pole is outside the range of [−12 • , 12 • ] and/or the cart is moving beyond the range [−2.4, 2.4] m in reference to the central position on the track. The controller can apply force to the center of mass of the system with fixed magnitude in two directions. In this example, a binary reinforcement signal r(t) is considered. We utilized similar structure of Critic and Action networks as in the previous example, therefore it is possible to set the same network parameters.
Figs. 9 (a) -(d) show examples of the time dependence of the action force, the position, and the angle trajectories, respectively. These figures correspond to simulations which are produced after training is completed and weights are fixed. We will demonstrate the difference between the behavior of approaches in our current study (AdpF ull) and (Liu et al., 2012) (AdpP art). We select two initial position (0.85, 0, 0, 0) and (2, 0, 0, 0), as described next.
In Figs. 9 (a) -(b), controllers AdpF ull and AdpP art show similar performance; the initial angle has small disturbance θ = 0.85 with respect to equilibrium position. However, even in this case, one can see a small drift on the cart position from 0 to 0.15. This indicates that AdpF ull is able to properly stabilize the cart, but AdpP art has some problem with this task.
By selecting initial condition θ = 2, we observe essential differences between the two approaches, see in Figs. 9 (c) -(d). Our AdpP art approach stabilizes the cart after about 3000 steps. At the same time, the AdpP art approach produces divergent behavior; after 6000 iterations the cart moves out of the allowed spatial region [−2.4, 2.4]. This behavior is discussed in the concluding section.

Discussion and Conclusions
In this work, we introduce several generalized stability criteria for the ADHDP system trained by gradient descent over the Critic and Action networks modeled by MLPs. It is shown that ADHDP design is uniformly ultimately bounded under some constraints on the learning rates. Our approach is more general than the one available in the literature, as our system allows adaptation across all layers of the networks. This generalization has important theoretical and practical consequences.
• From theoretical point of view, it is known that an MLP with at least one hidden layer is a universal approximator in a broad sense. However, by assuming that the weights between the input and the hidden layer are not adaptable, the generalization property of the network will be limited. • As for practical aspects, the difference between our approach and previous studies is demonstrated using two problems. An easy one with a linear system to be controlled, and a more difficult system with the cart-pole balancing task. • Our results show that the two approaches give very similar results for the easier linear problem. However, we demonstrate significant differences in the performance of the two systems for more complicated tasks (pole balancing). In particular, with larger initial deviation in the pole angle, our approach is able to balance the system. At the same time, the approach using a simplified control system with non-adaptable weights between the input and hidden layer is unable to solve this difficult task. These results show the power of the applied ADP approach when using the deep learning algorithm introduced here. It is expected that our results will be very useful for training of the intelligent control and decision support systems, including multi-agent platforms, leading to more efficient real-time training and control.