# Two-Phase Iteration for Value Function Approximation and Hyperparameter Optimization in Gaussian-Kernel-Based Adaptive Critic Design

Authors: Xin Chen; Penghuan Xie; Yonghua Xiong; Yong He; Min Wu
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Adaptive Dynamic Programming (ADP) with critic-actor architecture is an effective way to perform online learning control. To avoid the subjectivity in the design of a neural network that serves as a critic network, kernel-based adaptive critic design (ACD) was developed recently. There are two essential issues for a static kernel-based model: how to determine proper hyperparameters in advance and how to select right samples to describe the value function. They all rely on the assessment of sample values. Based on the theoretical analysis, this paper presents a two-phase simultaneous learning method for a Gaussian-kernel-based critic network. It is able to estimate the values of samples without infinitively revisiting them. And the hyperparameters of the kernel model are optimized simultaneously. Based on the estimated sample values, the sample set can be refined by adding alternatives or deleting redundances. Combining this critic design with actor network, we present a Gaussian-kernel-based Adaptive Dynamic Programming (GK-ADP) approach. Simulations are used to verify its feasibility, particularly the necessity of two-phase learning, the convergence characteristics, and the improvement of the system performance by using a varying sample set.


---

## Body

## 1. Introduction

Reinforcement learning (RL) is an interactive machine learning method for solving sequential decision problems. It is well known as an important learning method in unknown or dynamic environment. Different from supervised learning and unsupervised learning, RL interacts with the environment through trial mechanism and modifies its action policies to maximize the payoffs [1]. It is strongly connected from a theoretical point of view with direct and indirect adaptive optimal control methods [2].Traditional RL research focused on discrete state/action systems; state/action only takes on a finite number of prescribed discrete values. The learning space grows exponentially as the number of states and the number of allowed actions increase. This leads to the so-called curse of dimensionality (CoD) [2]. In order to mitigate this CoD problem, function approximations and generalization methods [3] are introduced to store the optimal value and the optimal control as a function of the state vector. Generalization methods based on parametric model such as neural networks [4–6] have become one of popular means to solve RL problem in continuous environments.Currently, research work on RL in continuous environment to construct learning systems for nonlinear optimal control has attracted attention of researchers and scholars in control domains for the reason that it can modify its policy only based on the value function without knowing the model structure or the parameters in advance. A family of new RL techniques known as Approximate or Adaptive Dynamic Programming (ADP) (also known as Neurodynamic Programming or Adaptive Critic Designs (ACDs)) has received more and more research interest [7, 8]. ADPs are based on the actor-critic structure, in which there is a critic assessing the value of the action or control policy applied by an actor and an actor modifying its action based on the assessment of values. In literatures, ADP approaches are categorized as the following main schemes: heuristic dynamic programming (HDP), dual heuristic programming (DHP), globalized dual heuristic programming (GDHP), and their action-dependent versions [9, 10].ADP researches always adopt multilayer perceptron neural networks (MLPNNs) as the critic design. Vrabie and Lewis proposed an online approach to continuous-time direct adaptive optimal control which made use of neural networks to parametrically represent the control policy and the performance of the control system [11]. Liu et al. solved the constrained optimal control problem of unknown discrete-time nonlinear systems based on the iterative ADP algorithm via GDHP technique with three neural networks [12]. In fact, different kinds of neural networks (NNs) play the important roles in ADP algorithms, such as radial basis function NNs [3], wavelet basis function NNs [13], and echo state network [14].Besides the benefits brought by NNs, ADP methods always suffer from some problems concerned in the design of NNs. On one hand, the learning control performance greatly depends on empirical design of critic networks, especially the manual setting of the hidden layer or the basis functions. On the other hand, due to the local minima in neural network training, how to improve the quality of the final policies is still an open problem [15].As we can see, it is difficult to evaluate the effectiveness of the parametric model when the knowledge on the model’s order or nonlinear characteristics of the system is not enough. Compared with parametric modeling methods, nonparametric modeling methods, especially kernel methods [16, 17], do not need to set the model structure in advance. Hence, kernel machines have been popularly studied to realize nonlinear and nonparametric modeling. Engel et al. proposed the kernel recursive least-squares algorithm to construct minimum mean-squared-error solutions to nonlinear least-squares problems [18]. As popular kernel machines, support vector machines (SVMs) also have been applied to nonparametric modeling problems. Dietterich and Wang combined linear programming with SVMs to find value function approximations [19]. The similar research was published in [20], in which the least-squares SVMs were used. Nevertheless, they both focused on discrete state/action space and lacked theoretical results on the policies obtained more or less.In addition to SVMs, Gaussian processes (GPs) have become an alternative generalization method. GP models are powerful nonparametric tools for approximate Bayesian inference and learning. In comparison with other popular nonlinear architectures, such as multilayer perceptrons, their behavior is conceptually simpler to understand, and model fitting can be achieved without resorting to nonconvex optimization routines [21, 22]. In [23], Engel et al. first applied GPs in temporal-difference (TD) learning for MDPs with stochastic rewards and deterministic transitions. They derived a new GPTD algorithm in [24] that overcame the limitation of deterministic transitions and extended GPTD to the estimation of state-action values. GPTD algorithm just addressed the value approximation, so it should be combined with actor-critic methods or other policy iteration methods to solve learning control problems.An alternative approach employing GPs in RL is model-based value iteration or policy iteration method, in which GP model is used to model system dynamics and represent the value function [25]. In [26], an approximated value-function based RL algorithm named Gaussian process dynamic programming (GPDP) was presented, which built dynamic transition model, value function model, and action policy model, respectively, using GPs. In this way, the sample set will be adjusted to such a reasonable shape with high sample densities near the equilibriums or the places where value functions change dramatically. Thus it is good at controlling nonlinear systems with complex dynamics. A major shortcoming, even if the relatively high computation cost is endurable, is that the states in sample set need to be revisited again and again in order to update their value functions. Since this condition is unpractical in real implements, it diminishes the appeal of employing this method.Kernel-based method is also introduced to ADP. In [15], a novel framework of ACDs with sparse kernel machines was presented by integrating kernel methods into critic network. A sparsification method based on the approximately linear dependence (ALD) analysis was used to sparsify the kernel machines. Obviously, this method can overcome the difficulty of presetting model structure in parametric models and realize actor-critic learning online [27]. However, the selection of samples based on the ALD analysis is an offline way without considering the distribution of the value function. Therefore, the data samples cannot be adjusted online, which makes the method more suitable for control systems with smooth dynamics, where value function changes gently.We think GPDP and ACDs with sparse kernel machines are complementary. As indicated in [28], it is known the prediction of GPs is viewed as a linear combination of the covariance between the new points and the samples. Hence it seems reasonable to introduce kernel machine with GPs to build critic network in ACDs, if the values of the samples are known or at least can be assessed numerically. And then the sample set will be adjusted online during critic-actor learning.The major problem here is how to realize the value function learning and GP models updating simultaneously, especially under the condition that the samples of state-action space can hardly be revisited infinitely in order to approximate their values. To tackle this problem, a two-phase iteration is developed in order to get optimal control policy for the system whose dynamics are unknown a priori.


## 2. Description of the Problem

In general, ADP is an actor-critic method which approximates the value functions and policies to encourage the realization of generalization in MDPs with large or continuous spaces. The critic design plays the most important role, because it determines how the actor optimizes its action. Hence, we give a brief introduction on both kernel-based ACD and GPs, in order to derive the clear description of the theoretical problem.


### 2.1. Kernel-Based ACDs

Kernel-based ACDs mainly consist of a critic network, a kernel-based feature learning module, a reward function, an actor network/controller, and a model of the plant. The critic constructed by kernel machine is used to approximate the value functions or their derivatives. Then the output of the critic is used in the training process of the actor so that policy gradients can be computed. As actor finally converges, the optimal action policy mapping states to actions is described by this actor.Traditional neural network based on kernel machine and samples serves as the model of value functions, just as the following equation shows, and the recursive algorithm, such as KLSTD [29] serves as value function approximation:(1)Qx=∑i=1Lαikx,xi,where x and xi represent state-action pairs (s,a) and (si,ai), αi, i=1,2,…,L, are the weights, and (si,ai) represents selected state-action pairs in sample set and k(x,xi) is a kernel function.The key of critic learning is the update of the weights vectorα. The value function modeling in continuous state/action space is a regression problem. From the view of the model, NN structure is a reproducing kernel space spanned by the samples, in which the value function is expressed as a linear regression function. Obviously as the basis of Hilbert space, how to select samples determines the VC dimension of identification, as well as the performance of value function approximation.If only using ALD-based kernel sparsification, it is only independent of samples that are considered in sample selection. So it is hard to evaluate how good the sample set is, because the sample selection does not consider the distribution of value function, and the performance of ALD analysis is affected seriously by the hyperparameters of kernel function, which are predetermined empirically and fixed during learning.If the hyperparameters can be optimized online and the value function w.r.t. samples can be evaluated by iteration algorithms, the critic network will be optimized not only by value approximation but also by hyperparameter optimization. Moreover with approximated sample values, there is a direct way to evaluate the validity of sample set, in order to regulate the set online. Thus in this paper we turn to Gaussian processes to construct the criterion for samples and hyperparameters.


### 2.2. GP-Based Value Function Model

For an MDP, the data samplesxi and the corresponding Q value can be collected by observing the MDP. Here xi is the state-action pairs (si,ai), s∈RN, a∈RM, and Qx is the value function defined as(2)Q∗x=Rx+β∫ps′∣xVs′ds′,where Vs=maxa⁡Qx.Given a sample set collected from a continuous dynamic system,{XL,y}, where y=QXL+ε, ε~N0,v0, Gaussian regression with covariance function shown in the following equation is a well known model technology to infer the Q function: (3)kxp,xq=v1exp⁡-12xp-xqTΛ-1xp-xq,where Λ=diag⁡([w1,w2,…,wN+M]).Assuming additive independent identically distributed Gaussian noiseε with variance v0, the prior on the noisy observations becomes (4)KL=KXL,XL+v0IL,where(5)KXL,XL=kx1,x1kx1,x2⋯kx1,xLkx2,x1⋱⋮⋮⋱⋮kxL,x1⋯⋯kxL,xL.The parameterswd, v0, and v1 are the hyperparameters of the GRq and collected within the vector θ=w1⋯wN+Mv1v0T.For an arbitrary inputx∗, the predictive distribution of the function value is Gaussian distributed with mean and variance given by (6)EQx∗=Kx∗,XLKL-1y,(7)var⁡Qx=kx∗,x∗-Kx∗,XLKL-1KXL,x∗.Comparing (6) to (1), we find that if we let α=KL-1y, the neural network is also regarded as the Gaussian regression. Or the critic network can be constructed based on Gaussian kernel machine, if the following conditions are satisfied.Condition 1.
The hyperparametersθ of Gaussian kernel are known.Condition 2.
The valuesy w.r.t. all samples states XL are known.With Gaussian-kernel-based critic network, the sample state-action pairs and corresponding values are known. And then the criterion such as the comprehensive utility proposed in [26] can be set up, in order to refine sample set online. At the same time it is convenient to optimize hyperparameters, in order to approximate Q value function more accurately. Thus besides the advantages brought by kernel machine, the critic based on Gaussian-kernel will be better in approximating value functions.Consider Condition1. If the values y w.r.t. XL are known (note that it is indeed Condition 2), the common way to get hyperparameters is by evidence maximization, where the log-evidence is given by (8)Lθ=-12yTKL-1y-12log⁡KL-n2log⁡2π.It requires the calculation of the derivative of Lθ w.r.t. each θi, given by (9)∂Lθ∂θi=-12tr⁡KL-1∂KL∂θi+12αT∂KL∂θiα,where tr⁡[·] denotes the trace, α=KL-1y.Consider Condition2. For unknown system, if KL is known, that is, the hyperparameters are known (note that it is indeed Condition 1), the update of critic network will be transferred to the update of values w.r.t. samples by using value iteration.According to the analysis, both conditions are interdependent. That means the update of critic depends on known hyperparameters, and the optimization of hyperparameters depends on accurate sample values.Hence we need a comprehensive iteration method to realize value approximation and optimization of hyperparameters simultaneously. A direct way is to update them alternately. Unfortunately, this way is not reasonable because these two processes are tightly coupled. For example, temporal differential errors drive value approximation, but the change of weightsα will cause the change of hyperparameters θ simultaneously; then it is difficult to tell whether this temporal differential error is induced by observation or by Gaussian regression model changing.To solve this problem, a kind of two-phase value iteration for critic network is presented in the next section, and the conditions of convergence are analyzed.


## 2.1. Kernel-Based ACDs

Kernel-based ACDs mainly consist of a critic network, a kernel-based feature learning module, a reward function, an actor network/controller, and a model of the plant. The critic constructed by kernel machine is used to approximate the value functions or their derivatives. Then the output of the critic is used in the training process of the actor so that policy gradients can be computed. As actor finally converges, the optimal action policy mapping states to actions is described by this actor.Traditional neural network based on kernel machine and samples serves as the model of value functions, just as the following equation shows, and the recursive algorithm, such as KLSTD [29] serves as value function approximation:(1)Qx=∑i=1Lαikx,xi,where x and xi represent state-action pairs (s,a) and (si,ai), αi, i=1,2,…,L, are the weights, and (si,ai) represents selected state-action pairs in sample set and k(x,xi) is a kernel function.The key of critic learning is the update of the weights vectorα. The value function modeling in continuous state/action space is a regression problem. From the view of the model, NN structure is a reproducing kernel space spanned by the samples, in which the value function is expressed as a linear regression function. Obviously as the basis of Hilbert space, how to select samples determines the VC dimension of identification, as well as the performance of value function approximation.If only using ALD-based kernel sparsification, it is only independent of samples that are considered in sample selection. So it is hard to evaluate how good the sample set is, because the sample selection does not consider the distribution of value function, and the performance of ALD analysis is affected seriously by the hyperparameters of kernel function, which are predetermined empirically and fixed during learning.If the hyperparameters can be optimized online and the value function w.r.t. samples can be evaluated by iteration algorithms, the critic network will be optimized not only by value approximation but also by hyperparameter optimization. Moreover with approximated sample values, there is a direct way to evaluate the validity of sample set, in order to regulate the set online. Thus in this paper we turn to Gaussian processes to construct the criterion for samples and hyperparameters.


## 2.2. GP-Based Value Function Model

For an MDP, the data samplesxi and the corresponding Q value can be collected by observing the MDP. Here xi is the state-action pairs (si,ai), s∈RN, a∈RM, and Qx is the value function defined as(2)Q∗x=Rx+β∫ps′∣xVs′ds′,where Vs=maxa⁡Qx.Given a sample set collected from a continuous dynamic system,{XL,y}, where y=QXL+ε, ε~N0,v0, Gaussian regression with covariance function shown in the following equation is a well known model technology to infer the Q function: (3)kxp,xq=v1exp⁡-12xp-xqTΛ-1xp-xq,where Λ=diag⁡([w1,w2,…,wN+M]).Assuming additive independent identically distributed Gaussian noiseε with variance v0, the prior on the noisy observations becomes (4)KL=KXL,XL+v0IL,where(5)KXL,XL=kx1,x1kx1,x2⋯kx1,xLkx2,x1⋱⋮⋮⋱⋮kxL,x1⋯⋯kxL,xL.The parameterswd, v0, and v1 are the hyperparameters of the GRq and collected within the vector θ=w1⋯wN+Mv1v0T.For an arbitrary inputx∗, the predictive distribution of the function value is Gaussian distributed with mean and variance given by (6)EQx∗=Kx∗,XLKL-1y,(7)var⁡Qx=kx∗,x∗-Kx∗,XLKL-1KXL,x∗.Comparing (6) to (1), we find that if we let α=KL-1y, the neural network is also regarded as the Gaussian regression. Or the critic network can be constructed based on Gaussian kernel machine, if the following conditions are satisfied.Condition 1.
The hyperparametersθ of Gaussian kernel are known.Condition 2.
The valuesy w.r.t. all samples states XL are known.With Gaussian-kernel-based critic network, the sample state-action pairs and corresponding values are known. And then the criterion such as the comprehensive utility proposed in [26] can be set up, in order to refine sample set online. At the same time it is convenient to optimize hyperparameters, in order to approximate Q value function more accurately. Thus besides the advantages brought by kernel machine, the critic based on Gaussian-kernel will be better in approximating value functions.Consider Condition1. If the values y w.r.t. XL are known (note that it is indeed Condition 2), the common way to get hyperparameters is by evidence maximization, where the log-evidence is given by (8)Lθ=-12yTKL-1y-12log⁡KL-n2log⁡2π.It requires the calculation of the derivative of Lθ w.r.t. each θi, given by (9)∂Lθ∂θi=-12tr⁡KL-1∂KL∂θi+12αT∂KL∂θiα,where tr⁡[·] denotes the trace, α=KL-1y.Consider Condition2. For unknown system, if KL is known, that is, the hyperparameters are known (note that it is indeed Condition 1), the update of critic network will be transferred to the update of values w.r.t. samples by using value iteration.According to the analysis, both conditions are interdependent. That means the update of critic depends on known hyperparameters, and the optimization of hyperparameters depends on accurate sample values.Hence we need a comprehensive iteration method to realize value approximation and optimization of hyperparameters simultaneously. A direct way is to update them alternately. Unfortunately, this way is not reasonable because these two processes are tightly coupled. For example, temporal differential errors drive value approximation, but the change of weightsα will cause the change of hyperparameters θ simultaneously; then it is difficult to tell whether this temporal differential error is induced by observation or by Gaussian regression model changing.To solve this problem, a kind of two-phase value iteration for critic network is presented in the next section, and the conditions of convergence are analyzed.


## 3. Two-Phase Value Iteration for Critic Network Approximation

First a proposition is given to describe the relationship between hyperparameters and the sample value function.Proposition 1.
The hyperparameters are optimized by evidence maximization according to the samples and theirQ values, and the log-evidence is given by (10)∂Lθ∂θi=-12tr⁡KL-1∂KL∂θi+12αT∂KL∂θiαT=0,i=1,…,D,where α=KL-1y. It can be proved that, for arbitrary hyperparameters θ, if α≠0, (10) defines an implicit function or a continuously differentiable function as follows:(11)θ=fα=f1αf2α⋯fDαT.Then the two-phase value iteration for critic network is described as the following theorem.Theorem 2.
Given the following conditions(1)
the system is boundary input and boundary output (BIBO) stable,(2)
the immediate rewardr is bounded,(3)
fork=1,2, ηtk→0, ∑t=1∞‍ηtk=∞,the following iteration process is convergent:(12)αt+1=αt,θt+1=θt+ηt1fαt-θt,αt+2=αt+1+ηt2kθtℵx,XL·r+βVθt,x′-kθtx,XLαt+1,θt+2=θt+1,where Vθt,x′=maxa⁡kθtx′,XLαt and kθtℵx,XL is a kind of pseudoinversion of kθtx,XL; that is, kθtx,XLkθtℵx,XL=1.Proof.
From (12), it is clear that the two phases include the update of hyperparameters in phase 1, which is viewed as the update of generalization model, and the update of samples’ value in phase 2, which is viewed as the update of critic network.
The convergence of iterative algorithm is proved based on stochastic approximation Lyapunov method.
Define that(13)Ptkθtx,XLαt=r+βVθt,x′=r+maxa⁡kθtx′,XLαt.
Equation (12) is rewritten as (14)αt+1=αt,θt+1=θt+ηt1fαt-θt,αt+2=αt+1+ηt2kθtℵx,XL·Pt+1kθtx,XLαt+1-kθtx,XLαt+1,θt+2=θt+1.
Define approximation errors as(15)
φ
t
+
2
1
=
φ
t
+
1
1
=
θ
t
+
1
-
f
α
t
+
1
=
θ
t
-
f
α
t
+
1
+
η
t
1
f
α
t
-
θ
t
=
1
-
η
t
1
φ
t
1
,
(16)
φ
t
+
2
2
=
α
t
+
2
-
α
∗
=
α
t
+
1
-
α
∗
+
η
t
2
k
θ
t
ℵ
x
,
X
L
·
P
t
+
1
k
θ
t
x
,
X
L
α
t
+
1
-
P
t
+
1
k
θ
t
x
,
X
L
α
∗
+
P
t
+
1
k
θ
t
x
,
X
L
α
∗
-
k
θ
t
x
,
X
L
α
t
+
1
=
φ
t
+
1
1
+
η
t
2
k
θ
t
ℵ
x
,
X
L
·
P
t
+
1
k
θ
t
x
,
X
L
α
t
+
1
-
P
t
+
1
k
θ
t
x
,
X
L
α
∗
+
η
t
2
k
θ
t
ℵ
x
,
X
L
·
P
t
+
1
k
θ
t
x
,
X
L
α
∗
-
k
θ
t
x
,
X
L
α
t
+
1
.
Further define that(17)λ1x,αt+1,α∗=kθtℵx,XL·Pt+1kθtx,XLαt+1-Pt+1kθtx,XLα∗,λ2x,αt+1,α∗=kθtℵx,XL·Pt+1kθtx,XLα∗-kθtx,XLαt+1.Thus (16) is reexpressed as (18)φt+22=φt+11+ηt2λ1x,αt+1,α∗+ηt2λ2x,αt+1,α∗.
Letφt=φt1Tφt2TT, and the two-phase iteration is in the shape of stochastic approximation; that is, (19)φt+11φt+12=φt1φt2+-ηt1φt10,φt+21φt+22=φt+11φt+12+0ηt2λ1x,αt+1,α∗+ηt2λ2x,αt+1,α∗.
Define(20)Vφt=φtTΛφt=φt1Tφt2TID00kθtTx∗,XLkθtx∗,XLφt1φt2,where D is the scale of the hyperparameters and x∗ will be defined later. Let kt∗ represent kθtTx∗,XLkθtx∗,XL for short.
Obviously (20) is a positive definite matrix, and x∗<∞, kt∗<∞. Hence, Vφt is a Lyapunov functional. At moment t, the conditional expectation of the positive definite matrix is (21)EtVt+2φt+2=Etφt+2TΛφt+2=Etφt+21Tφt+22TID00kt∗φt+21φt+22.
It is easy to compute the first-order Taylor expansion of (21) as (22)EtVt+2φt+2=EtVt+1φt+1+ηt2EtVt+1′φt+1φt+2-φt+1+ηt22C2Etφt+2-φt+1Tφt+2-φt+1in which the first item on the right of (22) is (23)EtVt+1φt+1=Vtφt+ηt1EtV′tφtφt+1-φt+ηt12C1Etφt+1-φtTφt+1-φt.
Substituting (23) into (22) yields (24)EtVt+2φt+2-Vtφt=ηt1EtV′tφtYt1+ηt2EtVt+1′φt+1Yt+12+ηt12C1EtYt12+ηt12C2EtYt+122,where Yt1=-φt10, (25)Yt+12=0Pt+1kθtx,XLαt+1-kθtx,XLαt+1=0λ1x,αt+1,α∗+λ2x,αt+1,α∗.
Consider the last two items of (24) firstly. If the immediate reward is bounded and infinite discounted reward is applied, the value function is bounded. Hence, αt<∞.
If the system is BIBO stable,∃Σ0,Σ1⊂Rn+m, n, m are the dimensions of the state space and action space, respectively, ∀x0∈Σ0, x∞∈Σ1, the policy space is bounded.
According to Proposition1, when the policy space is bounded and αt<∞, θt<∞, there exists a constant c1, so that (26)EVt+1′φt+1Yt+12≤c1.In addition, (27)EYt+122=Eλ1x,αt+1,α∗+λ2x,αt+1,α∗2≤2Eλ12x,αt+1,α∗+2Eλ22x,αt+1,α∗≤c2φt+12+c3φt+12≤c4Vφt+1.From (26) and (27), we know that (28)EYt+122+EVt+1′φt+1Yt+12≤C3Vφt+1+C3,where C3=max{c1,c4}. Similarly (29)EYt12+EV′tφtYt1≤C4Vφt+C4.
According to Lemma  5.4.1 in [30], EVφt<∞, and EYt12<∞ and EYt+122<∞.
Now we focus on the first two items on the right of (24).
The first itemEtV′tφtYt1 is computed as (30)EtV′tφtYt1=Etφt1Tφt2TID00kt∗-φt10=-φt12.
For the second itemEtVt+1′φt+1Yt+12, when the state transition function is time invariant, it is true that Pt+1Kθtx,XLαt+1=PtKθtx,XLαt+1, αt+1=αt. Then we have (31)
E
t
λ
1
x
,
α
t
+
1
,
α
∗
=
E
t
k
θ
t
ℵ
x
,
X
L
P
t
k
θ
t
x
,
X
L
α
t
-
k
θ
t
ℵ
x
,
X
L
P
t
k
θ
t
x
,
X
L
α
∗
=
k
θ
t
ℵ
x
,
X
L
·
E
P
t
k
θ
t
x
,
X
L
α
t
-
P
t
k
θ
t
x
,
X
L
α
∗
≤
k
θ
t
ℵ
x
,
X
L
·
E
P
t
k
θ
t
x
,
X
L
α
t
-
P
t
k
θ
t
x
,
X
L
α
∗
.
This inequality holds because of positivekθtℵx,X, kθt,iℵ>0, i=1,…,L. Define the norm Δθ,·=maxxΔθ,x, where Δ· is the derivative matrix norm of the vector1 and x∗=arg⁡maxx⁡Δθ,x. Then (32)
E
P
t
k
θ
t
x
,
X
L
α
t
-
P
t
k
θ
t
x
,
X
L
α
∗
=
max
x
⁡
E
t
P
t
k
θ
t
x
,
X
L
α
t
-
P
t
k
θ
t
x
,
X
L
α
∗
=
max
x
⁡
E
t
r
+
β
max
a
′
⁡
k
θ
t
x
′
,
X
L
α
t
-
r
+
β
max
a
′
⁡
k
θ
t
x
′
,
X
L
α
∗
=
β
·
max
x
⁡
E
t
max
a
′
⁡
k
θ
t
x
′
,
X
L
α
t
-
max
a
′
⁡
k
θ
t
x
′
,
X
L
α
∗
=
β
max
x
⁡
∫
s
′
p
s
′
∣
x
·
max
a
′
⁡
k
θ
t
x
′
,
X
L
α
t
-
max
a
′
⁡
k
θ
t
x
′
,
X
L
α
∗
d
s
′
≤
β
max
x
⁡
∫
s
′
p
s
′
∣
x
·
max
a
′
⁡
k
θ
t
x
′
,
X
L
α
t
-
max
a
′
⁡
k
θ
t
x
′
,
X
L
α
∗
d
s
′
≤
β
max
x
⁡
∫
s
′
p
s
′
∣
x
·
max
a
′
⁡
k
θ
t
x
′
,
X
L
α
t
-
k
θ
t
x
′
,
X
L
α
∗
d
s
′
=
β
·
max
x
⁡
∫
s
′
p
s
′
∣
x
max
a
′
⁡
k
θ
t
x
′
,
X
L
α
t
-
α
∗
d
s
′
=
β
max
x
⁡
∫
s
′
p
s
′
∣
x
·
max
a
′
⁡
E
t
P
t
k
θ
t
x
′
,
X
L
α
t
-
P
t
k
θ
t
x
′
,
X
L
α
∗
d
s
′
≤
β
max
x
⁡
k
θ
t
x
,
X
L
α
t
-
α
∗
=
β
k
θ
t
x
∗
,
X
L
·
φ
t
2
.Hence (33)Etλ1x,αt+1,α∗≤βkθtℵx∗,XLkθtx∗,XLφt2.
On the other hand,(34)
E
t
λ
2
x
,
α
t
,
α
∗
=
E
t
k
θ
t
ℵ
x
,
X
L
P
t
k
θ
t
x
,
X
L
α
∗
-
k
θ
t
ℵ
x
,
X
L
k
θ
t
x
,
X
L
α
t
=
E
t
k
θ
t
ℵ
x
,
X
L
P
t
k
θ
t
x
,
X
L
α
∗
-
k
θ
t
ℵ
x
,
X
L
k
θ
t
x
,
X
L
α
∗
+
k
θ
t
ℵ
x
,
X
L
·
k
θ
t
x
,
X
L
α
∗
-
k
θ
t
ℵ
x
,
X
L
k
θ
t
x
,
X
L
α
t
=
-
k
θ
t
ℵ
x
,
X
L
k
θ
t
x
,
X
L
φ
t
2
-
E
t
λ
3
x
,
θ
t
,
θ
∗
,where λ3x,θt,θ∗=Ptkθtx,XLα∗-kθtx,XLα∗ is the value function error caused by the estimated hyperparameters.
Substituting (33) and (34) into EtVt+1′φt+1Yt+12 yields (35)
E
t
V
t
+
1
′
φ
t
+
1
Y
t
+
1
2
=
E
t
k
θ
t
x
∗
,
X
L
φ
t
2
T
·
k
θ
t
x
∗
,
X
L
λ
1
x
,
α
t
+
1
,
α
∗
+
λ
2
x
,
α
t
+
1
,
α
∗
=
k
θ
t
x
∗
,
X
L
φ
t
2
T
k
θ
t
x
∗
,
X
L
·
E
t
λ
1
x
,
α
t
+
1
,
α
∗
+
E
t
λ
2
x
,
α
t
+
1
,
α
∗
≤
β
k
θ
t
x
∗
,
X
L
φ
t
2
T
k
θ
t
x
∗
,
X
L
k
θ
t
ℵ
x
∗
,
X
L
·
k
θ
t
x
∗
,
X
L
φ
t
2
-
k
θ
t
x
∗
,
X
L
φ
t
2
T
k
θ
t
x
∗
,
X
L
·
k
θ
t
ℵ
x
∗
,
X
L
k
θ
t
x
∗
,
X
L
φ
t
2
-
E
t
λ
3
x
∗
,
θ
t
,
θ
∗
≤
-
1
-
β
k
θ
t
x
∗
,
X
L
φ
t
2
2
+
k
θ
t
x
∗
,
X
L
φ
t
2
T
·
E
t
λ
3
x
∗
,
θ
t
,
θ
∗
.Obviously, if the following inequality is satisfied, (36)ηt2kθtx∗,XLφt2TEtλ3x∗,θt,θ∗<ηt1φt12+ηt21-βkθtx∗,XLφt22there exists a positive const δ, such that the first two items on the right of (24) satisfy (37)ηt1EtV′tφtYt1+ηt2EtVt+1′φt+1Yt+12≤-δ.According to Theorem  5.4.2 in [30], the iterative process is convergent; namely, φt→w.p.10.Remark 3.
Let us check the final convergence position. Obviously,φt→w.p.10, αtθt→w.p.1α∗fα∗. This means the equilibrium of the critic network meets EtPtKθ∗x,XLα∗=Kθ∗x,XLα∗, where θ∗=f(α∗). And the equilibrium of hyperparameters θ∗=fα∗ is the solution of evidence maximization that maxφ(Lφ)=maxφ(1/2)yTKθ∗-1XL,XLy+(1/2)logC+(n/2)log2π, where y=Kθ∗-1XL,XLα∗.Remark 4.
It is clear that the selection of the samples is one of the key issues. Since now all samples have values according to two-phase iteration, according to the information-based criterion, it is convenient to evaluate samples and refine the set by arranging relative more samples near the equilibrium or with great gradient of the value function, so that the sample set is better to describe the distribution of value function.Remark 5.
Since the two-phase iteration belongs to value iteration, the initial policy of the algorithm does not need to be stable. To ensure BIBO in practice, we need a mechanism to clamp the output of system, even though the system will not be smooth any longer.Theorem2 gives the iteration principle for critic network learning. Based on the critic network, with proper objective defined, such as minimizing the expected total discounted reward [15], HDP or DHP update is applied to optimize actor network. Since this paper focuses on ACD and more importantly the update process of actor network does not affect the convergence of critic network, though maybe it induces premature or local optimization, the gradient update of actor is not necessary. Hence a simple optimum seeking is applied to get optimal actions w.r.t. sample states, and then an actor network based on Gaussian kernel is generated based on these optimal state-action pairs.Up to now we have built a critic-actor architecture which is named Gaussian-kernel-based Approximate Dynamic Programming (GK-ADP for short) and shown in Algorithm1. A span K is introduced, so that hyperparameters are updated every K times of α update. If K>1, two phases are asynchronous. From the view of stochastic approximation, this asynchronous learning does not change the convergence condition (36) but benefit computational cost of hyperparameters learning.Algorithm 1:Gaussian-kernel-based Approximate Dynamic Programming.
Initialize:
θ: hyperparameters of Gaussian kernel model
XL=xi∣xi=(si,ai)i=1L: sample set
π(s0): initial policy
ηt1, ηt2: learning step size
Lett = 0;
Loop:
for  k = 1 to  K  do
t = t + 1;
at=π(st)
Get the rewardrt
Observe next statest+1
Updateα according to (12)
Update the policyπ according to optimum seeking
end  for
Updateθ according to (12)
Until the termination criterion is satisfied


## 4. Simulation and Discussion

In this section, we propose some numerical simulations about continuous control to illustrate the special properties and the feasibility of the algorithm, including the necessity of two phases learning, the specifical properties comparing with traditional kernel-based ACDs, and the performance enhancement resulting from online refinement of sample set.Before further discussion, we firstly give common setup in all simulations:(i)
The spanK=50.(ii)
To make output bounded, once a state is out of the boundary, the system is reset randomly.(iii)
The exploration-exploitation tradeoff is left out of account here. During learning process, all actions are selected randomly within limited action space. Thus the behavior of the system is totally unordered during learning.(iv)
The same ALD-based sparsification in [15] is used to determine the initial sample set, in which wi=1.8, v0=0, and v1=0.5 empirically.(v)
The sampling time and control interval are set to 0.02 s.


### 4.1. The Necessity of Two-Phase Learning

The proof of Theorem2 shows that properly determined learning rates of phases 1 and 2 guarantee condition (36). Here we propose a simulation to show how the learning rates in phases 1 and 2 affect the performance of the learning.Consider a simple single homogeneous inverted pendulum system:(38)s˙1=s2s˙2=Mpgsins1-τcoss1dMpd,where s1 and s2 represent the angle and its speed, Mp=0.1kg, g=9.8m/s2, d=0.2m, respectively, and τ is a horizontal force acting on the pole.We test the success rate under different learning rates. Since, during the learning the action is always selected randomly, we have to verify the optimal policy after learning; that is, an independent policy test is carried out to test the actor network. Thus the success of one time of learning means in the independent test the pole can be swung up and maintained within[-0.02,0.02] rad for more than 200 iterations.In the simulation, 60 state-action pairs are collected to serve as the sample set, and the learning rates are set toηt2=0.01/(1+t)0.018, ηt1=a/(1+t0.018), where a is varying from 0 to 0.12.The learning is repeated 50 times in order to get the average performance, where the initial states of each run are randomly selected within the bound[-0.4,0.4] and [-0.5,0.5] w.r.t. the dimensions of s1 and s2. The action space is bounded within [-0.5,0.5]. And, in each run, the initial hyperparameters are set to e-2.5e0.5e0.9e-1e0.001.Figure1 shows the result of success rates. Clearly, with ηt2 fixed, different ηt1’s affect the performance significantly. In particular, without the learning of hyperparameters, that is, ηt1=0, there are only 6 successful runs over 50 runs. With the increasing of a the success rate increases till 1 when a=0.08. But as a goes on increasing, the performance becomes worse.Figure 1
Success times over 50 runs under different learning rateηt1.Hence both phases are necessary if the hyperparameters are not initialized properly. It should be noted that the learning rates w.r.t. two phases need to be regulated carefully in order to guarantee condition (36), which leads the learning process to the equilibrium in Remark 3 but not to some kind of boundary where the actor always executed the maximal or minimal actions.If all samples’ values on each iteration are summed up and all cumulative values w.r.t. iterations are depicted in series, then we have Figure2. The evolution process w.r.t. the best parameter a=0.08 is marked by the darker diamond. It is clear that, even with different ηt1, the evolution processes of the samples’ value learning are similar. That means, due to BIBO property, the samples’ values must be finally bounded and convergent. However, as mentioned above, it does not mean that the learning process converges to the proper equilibrium.Figure 2
The average evolution processes over 50 runs w.r.t. differentηt1.


### 4.2. Value Iteration versus Policy Iteration

As mentioned in Algorithm1, the value iteration in critic network learning does not depend on the convergence of the actor network, and, compared with HDP or DHP, the direct optimum seeking for actor network seems a little aimless. To test its performance and discuss its special characters of learning, a comparison between GK-ADP and KHDP is carried out.The control objective in the simulation is a one-dimensional inverted pendulum, where a single-stage inverted pendulum is mounted on a cart which is able to move linearly, just as Figure3 shows.Figure 3
One-dimensional inverted pendulum.The mathematic model is given as(39)s˙1=s2+ε,s˙2=gsin⁡s1-Mpds22cos⁡s1sin⁡s1/Md4/3-Mpcos2⁡s1/M+cos⁡s1/Md4/3-Mpcos2⁡s1/Mu,s˙3=s4,s˙4=u+Mpds22sin⁡s1-s˙2cos⁡s1M,where s1 to s4 represent the state of angle, angle speed, linear displacement, and linear speed of the cart, respectively, u represents the force acting on the cart, M=0.2kg, d=0.5m, ε~U(-0.02,0.02), and other denotations are the same as (38).Thus the state-action space is 5D space, much larger than that in simulation 1. The configurations of the both algorithms are listed as follows:(i)
A small sample set with 50 samples is adopted to build critic network, which is determined by ALD-based sparsification.(ii)
For both algorithms, the state-action pair is limited to[-0.3,0.3], [-1,1], [-0.3,0.3], [-2,2], [-3,3] w.r.t. s1 to s4 and u.(iii)
In GK-ADP, the learning rates areηt1=0.02/(1+t0.01) and ηt2=0.02/(1+t)0.02.(iv)
The KHDP algorithm in [15] is chosen as the comparison, where the critic network uses Gaussian kernels. To get the proper Gaussian parameters, a series of σ as 0.9, 1.2, 1.5, 1.8, 2.1, and 2.4 are tested in the simulation. The elements of weights α are initialized randomly in -0.5,0.5, the forgetting factor in RLS-TD(0) is set to μ=1, and the learning rate in KHDP is set to 0.3.(v)
All experiments run 100 times to get the average performance. And in each run there are 10000 iterations to learn critic network.Before further discussion, it should be noted that it makes no sense to figure out ourselves with which algorithm is better in learning performance, because, besides the debate of policy iteration versus value iteration, there are too many parameters in the simulation configuration affecting learning performance. So the aim of this simulation is to illustrate the learning characters of GK-ADP.However to make the comparison as fair as possible, we regulate the learning rates of both algorithms to get similar evolution processes. Figure4 shows the evolution processes of GK-ADP and KHDPs under different σ, where the y-axis in the left represents the cumulated weights, ∑i‍αi, of the critic network in kernel ACD, and the other y-axis represents the cumulated values of the samples, ∑i‍Q(xi),xi∈XL, in GK-ADP. It implies although, with different units, the learning processes under both learning algorithms converge nearly at the same speed.Figure 4
The comparison of the average evolution processes over 100 runs.Then the success rates of all algorithms are depicted in Figure5. The left six bars represent the success rates of KHDP with different σ. With superiority argument left aside, we find that, such fixed σ in KHDP is very similar to the fixed hyperparameters θ, which needs to be set properly in order to get higher success rate. But unfortunately there is no mechanism in KHDP to regulate σ online. On the contrary, the two-phase iteration introduces the update of hyperparameters into critic network, which is able to drive hyperparameters to better values, even with the not so good initial values. In fact, this two-phase update can be viewed as a kind of kernel ACD with dynamic σ, when Gaussian kernel is used.Figure 5
The success rates w.r.t. all algorithms over 100 runs.To discuss the performance in deep, we plot the test trajectories resulting from the actors, which are optimized by GK-ADP and KHDP, in Figures6(a) and 6(b), respectively, where the start state is set to 0.20-0.20.Figure 6
The outputs of the actor networks resulting from GK-ADP and KHDP.
(a)
The resulted control performance using GK-ADP
(b)
The resulted control performance using KHDPApparently the transition time of GK-ADP is much smaller than KHDP. We think, besides the possible well regulated parameters, an important reason is nongradient learning for actor network.The critic learning only depends on exploration-exploitation balance but not the convergence of actor learning. If exploration-exploitation balance is designed without actor network output, the learning processes of actor and critic networks are relatively independent of each other, and then there are alternatives to gradient learning for actor network optimization, for example, the direct optimum seeking Gaussian regression actor network in GK-ADP.Such direct optimum seeking may result in nearly nonsmooth actor network, just like the force output depicted in the second plot of Figure6(a). To explain this phenomenon, we can find the clue from Figure 7, which illustrates the best actions w.r.t. all sample states according to the final actor network. It is reasonable that the force direction is always the same to the pole angle and contrary to the cart displacement. And clearly the transition interval from negative limit −3N to positive 3N is very short. Thus the output of actor network, resulting from Gaussian kernels, intends to control angle bias as quickly as possible, even though such quick control sometimes makes the output force a little nonsmooth.Figure 7
The final best policies w.r.t. all samples.It is obvious that GK-ADP is with high efficiency but also with potential risks, such as the impact to actuators. Hence how to design exploration-exploitation balance to satisfy Theorem2 and how to design actor network learning to balance efficiency and engineering applicability are two important issues in future work.Finally we check the samples values, which are depicted in Figure8, where only dimensions of pole angle and linear displacement are depicted. Due to the definition of immediate reward, the closer the states to the equilibrium are, the smaller the Q value is.Figure 8
TheQ values projected on to dimensions of pole angle (s1) and linear displacement (s3) w.r.t. all samples.If we execute 96 successful policies one by one and record all final cart displacements and linear speed, just as Figure9 shows, the shortage of this sample set is uncovered that, even with good convergence of pole angle, the optimal policy can hardly drive cart back to zero point.Figure 9
The final cart displacement and linear speed in the test of successful policy.To solve this problem and improve performance, besides optimizing learning parameters, Remark4 implies that another and maybe more efficient way is refining sample set based on the samples’ values. We will investigate it in the following subsection.


### 4.3. Online Adjustment of Sample Set

Due to learning sample’s value, it is possible to assess whether the samples are chosen reasonable. In this simulation we adopt the following expected utility [26]:(40)Ux=ρhEQx∣XL+β2log⁡var⁡Qx∣XL,where h(·) is a normalization function over sample set and ρ=1, β=0.3 are coefficients.LetNadd represent the number of samples added to the sample set, Nlimit the size limit of the sample set, and Tx=x0,x1,…,x(Te) the state-action pair trajectory during GK-ADP learning, where Te denotes the end iteration of learning. The algorithm to refine sample set is presented as Algorithm 2.Algorithm 2:Refinement of sample set.
f
o
r  l = 1 to  the  end  of  T(x)
Calculate E[Q(x(l))∣XL] and var[Q(xl)∣XL] using (6) and (7)
Calculate U(x(l)) using (40)
e
n
d  for  l
Sort allU(x(l)), l=1,…,Te in ascending order
Add the firstNadd state-action pairs to sample set to get extended set XL+Nadd
i
f  L + Nadd > Nlimit
Calculate hyperparameters based on XL+Nadd
for  l = 1  to  L + Nadd
Calculate E[Q(x(l))∣XL+Nadd] and var[Q(xl)∣XL+Nadd] using (6) and (7)
Calculate U(x(l)) using (40)
end  for  l
Sort all U(x(l)), l=1,…,L+Nadd in descending order
Delete the first L + Nadd − Nlimit samples to get refined set  XNlimit
e
n
d  ifSince in simulation 2 we have carried out 100 runs of experiment for GK-ADP, 100 sets of sample values w.r.t. the same sample states are obtained. Now let us apply Algorithm2 to these resulted sample sets, where T(x) is picked up from the history trajectory of state-action pairs in each run, and Nadd=10, Nlimit=60, in order to add 10 samples into sample set.We repeat all 100 runs of GK-ADP again, with the same learning ratesη1 and η2. Based on 96 successful runs in simulation 2, 94 runs are successful in obtaining control policies swinging up pole. Figure 10(a) shows the average evolutional process of sample values over 100 runs, where the first 10000 iterations display the learning process in simulation 2 and the second 8000 iterations display the learning process after adding samples. Clearly the cumulative Q value behaves a sudden increase after sample was added and almost keeps steady afterwards. It implies, even with more samples added, there is not too much to learn for sample values.Figure 10
Learning performance of GK-ADP if sample set is refined by adding 10 samples.
(a)
The average evolution process ofQ values before and after adding samples
(b)
The enhancement of the control performance about cart displacement after adding samplesHowever if we check the cart movement, we will find the enhancement brought by the change of sample set. For thejth run, we have two actor networks resulting from GK-ADP before and after adding samples. Using these actors, We carry out the control test, respectively, and collect the absolute values of cart displacement, denoted by S3b(j) and S3a(j), at the moment that the pole has been swung up for 100 instants. We define the enhancement as (41)Ej=S3bj-S3ajS3bj.Obviously the positive enhancement indicates that the actor network after adding samples behaves better. As all enhancements w.r.t. 100 runs are illustrated together, just as Figure10(b) shows, almost all cart displacements as the pole is swung up are enhanced more or less except for 8 times of failure. Hence with proper principle based on the sample values, the sample set can be refined online in order to enhance performance.Finally let us check which state-action pairs are added into sample set. We put all added samples over 100 runs together and depict their values in Figure11(a), where the values are projected onto the dimensions of pole angle and cart displacement. If only concerning the relationship between Q values and pole angle, just as Figure 11(b) shows, we find that the refinement principle intends to select the samples a little away from the equilibrium and near the boundary -0.4, due to the ratio between ρ and β.Figure 11
TheQ values w.r.t. all added samples over 100 runs.
(a)
Projecting on the dimensions of pole angle and cart displacement
(b)
Projecting on the dimension of pole angle


## 4.1. The Necessity of Two-Phase Learning

The proof of Theorem2 shows that properly determined learning rates of phases 1 and 2 guarantee condition (36). Here we propose a simulation to show how the learning rates in phases 1 and 2 affect the performance of the learning.Consider a simple single homogeneous inverted pendulum system:(38)s˙1=s2s˙2=Mpgsins1-τcoss1dMpd,where s1 and s2 represent the angle and its speed, Mp=0.1kg, g=9.8m/s2, d=0.2m, respectively, and τ is a horizontal force acting on the pole.We test the success rate under different learning rates. Since, during the learning the action is always selected randomly, we have to verify the optimal policy after learning; that is, an independent policy test is carried out to test the actor network. Thus the success of one time of learning means in the independent test the pole can be swung up and maintained within[-0.02,0.02] rad for more than 200 iterations.In the simulation, 60 state-action pairs are collected to serve as the sample set, and the learning rates are set toηt2=0.01/(1+t)0.018, ηt1=a/(1+t0.018), where a is varying from 0 to 0.12.The learning is repeated 50 times in order to get the average performance, where the initial states of each run are randomly selected within the bound[-0.4,0.4] and [-0.5,0.5] w.r.t. the dimensions of s1 and s2. The action space is bounded within [-0.5,0.5]. And, in each run, the initial hyperparameters are set to e-2.5e0.5e0.9e-1e0.001.Figure1 shows the result of success rates. Clearly, with ηt2 fixed, different ηt1’s affect the performance significantly. In particular, without the learning of hyperparameters, that is, ηt1=0, there are only 6 successful runs over 50 runs. With the increasing of a the success rate increases till 1 when a=0.08. But as a goes on increasing, the performance becomes worse.Figure 1
Success times over 50 runs under different learning rateηt1.Hence both phases are necessary if the hyperparameters are not initialized properly. It should be noted that the learning rates w.r.t. two phases need to be regulated carefully in order to guarantee condition (36), which leads the learning process to the equilibrium in Remark 3 but not to some kind of boundary where the actor always executed the maximal or minimal actions.If all samples’ values on each iteration are summed up and all cumulative values w.r.t. iterations are depicted in series, then we have Figure2. The evolution process w.r.t. the best parameter a=0.08 is marked by the darker diamond. It is clear that, even with different ηt1, the evolution processes of the samples’ value learning are similar. That means, due to BIBO property, the samples’ values must be finally bounded and convergent. However, as mentioned above, it does not mean that the learning process converges to the proper equilibrium.Figure 2
The average evolution processes over 50 runs w.r.t. differentηt1.


## 4.2. Value Iteration versus Policy Iteration

As mentioned in Algorithm1, the value iteration in critic network learning does not depend on the convergence of the actor network, and, compared with HDP or DHP, the direct optimum seeking for actor network seems a little aimless. To test its performance and discuss its special characters of learning, a comparison between GK-ADP and KHDP is carried out.The control objective in the simulation is a one-dimensional inverted pendulum, where a single-stage inverted pendulum is mounted on a cart which is able to move linearly, just as Figure3 shows.Figure 3
One-dimensional inverted pendulum.The mathematic model is given as(39)s˙1=s2+ε,s˙2=gsin⁡s1-Mpds22cos⁡s1sin⁡s1/Md4/3-Mpcos2⁡s1/M+cos⁡s1/Md4/3-Mpcos2⁡s1/Mu,s˙3=s4,s˙4=u+Mpds22sin⁡s1-s˙2cos⁡s1M,where s1 to s4 represent the state of angle, angle speed, linear displacement, and linear speed of the cart, respectively, u represents the force acting on the cart, M=0.2kg, d=0.5m, ε~U(-0.02,0.02), and other denotations are the same as (38).Thus the state-action space is 5D space, much larger than that in simulation 1. The configurations of the both algorithms are listed as follows:(i)
A small sample set with 50 samples is adopted to build critic network, which is determined by ALD-based sparsification.(ii)
For both algorithms, the state-action pair is limited to[-0.3,0.3], [-1,1], [-0.3,0.3], [-2,2], [-3,3] w.r.t. s1 to s4 and u.(iii)
In GK-ADP, the learning rates areηt1=0.02/(1+t0.01) and ηt2=0.02/(1+t)0.02.(iv)
The KHDP algorithm in [15] is chosen as the comparison, where the critic network uses Gaussian kernels. To get the proper Gaussian parameters, a series of σ as 0.9, 1.2, 1.5, 1.8, 2.1, and 2.4 are tested in the simulation. The elements of weights α are initialized randomly in -0.5,0.5, the forgetting factor in RLS-TD(0) is set to μ=1, and the learning rate in KHDP is set to 0.3.(v)
All experiments run 100 times to get the average performance. And in each run there are 10000 iterations to learn critic network.Before further discussion, it should be noted that it makes no sense to figure out ourselves with which algorithm is better in learning performance, because, besides the debate of policy iteration versus value iteration, there are too many parameters in the simulation configuration affecting learning performance. So the aim of this simulation is to illustrate the learning characters of GK-ADP.However to make the comparison as fair as possible, we regulate the learning rates of both algorithms to get similar evolution processes. Figure4 shows the evolution processes of GK-ADP and KHDPs under different σ, where the y-axis in the left represents the cumulated weights, ∑i‍αi, of the critic network in kernel ACD, and the other y-axis represents the cumulated values of the samples, ∑i‍Q(xi),xi∈XL, in GK-ADP. It implies although, with different units, the learning processes under both learning algorithms converge nearly at the same speed.Figure 4
The comparison of the average evolution processes over 100 runs.Then the success rates of all algorithms are depicted in Figure5. The left six bars represent the success rates of KHDP with different σ. With superiority argument left aside, we find that, such fixed σ in KHDP is very similar to the fixed hyperparameters θ, which needs to be set properly in order to get higher success rate. But unfortunately there is no mechanism in KHDP to regulate σ online. On the contrary, the two-phase iteration introduces the update of hyperparameters into critic network, which is able to drive hyperparameters to better values, even with the not so good initial values. In fact, this two-phase update can be viewed as a kind of kernel ACD with dynamic σ, when Gaussian kernel is used.Figure 5
The success rates w.r.t. all algorithms over 100 runs.To discuss the performance in deep, we plot the test trajectories resulting from the actors, which are optimized by GK-ADP and KHDP, in Figures6(a) and 6(b), respectively, where the start state is set to 0.20-0.20.Figure 6
The outputs of the actor networks resulting from GK-ADP and KHDP.
(a)
The resulted control performance using GK-ADP
(b)
The resulted control performance using KHDPApparently the transition time of GK-ADP is much smaller than KHDP. We think, besides the possible well regulated parameters, an important reason is nongradient learning for actor network.The critic learning only depends on exploration-exploitation balance but not the convergence of actor learning. If exploration-exploitation balance is designed without actor network output, the learning processes of actor and critic networks are relatively independent of each other, and then there are alternatives to gradient learning for actor network optimization, for example, the direct optimum seeking Gaussian regression actor network in GK-ADP.Such direct optimum seeking may result in nearly nonsmooth actor network, just like the force output depicted in the second plot of Figure6(a). To explain this phenomenon, we can find the clue from Figure 7, which illustrates the best actions w.r.t. all sample states according to the final actor network. It is reasonable that the force direction is always the same to the pole angle and contrary to the cart displacement. And clearly the transition interval from negative limit −3N to positive 3N is very short. Thus the output of actor network, resulting from Gaussian kernels, intends to control angle bias as quickly as possible, even though such quick control sometimes makes the output force a little nonsmooth.Figure 7
The final best policies w.r.t. all samples.It is obvious that GK-ADP is with high efficiency but also with potential risks, such as the impact to actuators. Hence how to design exploration-exploitation balance to satisfy Theorem2 and how to design actor network learning to balance efficiency and engineering applicability are two important issues in future work.Finally we check the samples values, which are depicted in Figure8, where only dimensions of pole angle and linear displacement are depicted. Due to the definition of immediate reward, the closer the states to the equilibrium are, the smaller the Q value is.Figure 8
TheQ values projected on to dimensions of pole angle (s1) and linear displacement (s3) w.r.t. all samples.If we execute 96 successful policies one by one and record all final cart displacements and linear speed, just as Figure9 shows, the shortage of this sample set is uncovered that, even with good convergence of pole angle, the optimal policy can hardly drive cart back to zero point.Figure 9
The final cart displacement and linear speed in the test of successful policy.To solve this problem and improve performance, besides optimizing learning parameters, Remark4 implies that another and maybe more efficient way is refining sample set based on the samples’ values. We will investigate it in the following subsection.


## 4.3. Online Adjustment of Sample Set

Due to learning sample’s value, it is possible to assess whether the samples are chosen reasonable. In this simulation we adopt the following expected utility [26]:(40)Ux=ρhEQx∣XL+β2log⁡var⁡Qx∣XL,where h(·) is a normalization function over sample set and ρ=1, β=0.3 are coefficients.LetNadd represent the number of samples added to the sample set, Nlimit the size limit of the sample set, and Tx=x0,x1,…,x(Te) the state-action pair trajectory during GK-ADP learning, where Te denotes the end iteration of learning. The algorithm to refine sample set is presented as Algorithm 2.Algorithm 2:Refinement of sample set.
f
o
r  l = 1 to  the  end  of  T(x)
Calculate E[Q(x(l))∣XL] and var[Q(xl)∣XL] using (6) and (7)
Calculate U(x(l)) using (40)
e
n
d  for  l
Sort allU(x(l)), l=1,…,Te in ascending order
Add the firstNadd state-action pairs to sample set to get extended set XL+Nadd
i
f  L + Nadd > Nlimit
Calculate hyperparameters based on XL+Nadd
for  l = 1  to  L + Nadd
Calculate E[Q(x(l))∣XL+Nadd] and var[Q(xl)∣XL+Nadd] using (6) and (7)
Calculate U(x(l)) using (40)
end  for  l
Sort all U(x(l)), l=1,…,L+Nadd in descending order
Delete the first L + Nadd − Nlimit samples to get refined set  XNlimit
e
n
d  ifSince in simulation 2 we have carried out 100 runs of experiment for GK-ADP, 100 sets of sample values w.r.t. the same sample states are obtained. Now let us apply Algorithm2 to these resulted sample sets, where T(x) is picked up from the history trajectory of state-action pairs in each run, and Nadd=10, Nlimit=60, in order to add 10 samples into sample set.We repeat all 100 runs of GK-ADP again, with the same learning ratesη1 and η2. Based on 96 successful runs in simulation 2, 94 runs are successful in obtaining control policies swinging up pole. Figure 10(a) shows the average evolutional process of sample values over 100 runs, where the first 10000 iterations display the learning process in simulation 2 and the second 8000 iterations display the learning process after adding samples. Clearly the cumulative Q value behaves a sudden increase after sample was added and almost keeps steady afterwards. It implies, even with more samples added, there is not too much to learn for sample values.Figure 10
Learning performance of GK-ADP if sample set is refined by adding 10 samples.
(a)
The average evolution process ofQ values before and after adding samples
(b)
The enhancement of the control performance about cart displacement after adding samplesHowever if we check the cart movement, we will find the enhancement brought by the change of sample set. For thejth run, we have two actor networks resulting from GK-ADP before and after adding samples. Using these actors, We carry out the control test, respectively, and collect the absolute values of cart displacement, denoted by S3b(j) and S3a(j), at the moment that the pole has been swung up for 100 instants. We define the enhancement as (41)Ej=S3bj-S3ajS3bj.Obviously the positive enhancement indicates that the actor network after adding samples behaves better. As all enhancements w.r.t. 100 runs are illustrated together, just as Figure10(b) shows, almost all cart displacements as the pole is swung up are enhanced more or less except for 8 times of failure. Hence with proper principle based on the sample values, the sample set can be refined online in order to enhance performance.Finally let us check which state-action pairs are added into sample set. We put all added samples over 100 runs together and depict their values in Figure11(a), where the values are projected onto the dimensions of pole angle and cart displacement. If only concerning the relationship between Q values and pole angle, just as Figure 11(b) shows, we find that the refinement principle intends to select the samples a little away from the equilibrium and near the boundary -0.4, due to the ratio between ρ and β.Figure 11
TheQ values w.r.t. all added samples over 100 runs.
(a)
Projecting on the dimensions of pole angle and cart displacement
(b)
Projecting on the dimension of pole angle


## 5. Conclusions and Future Work

ADP methods are among the most promising research works on RL in continuous environment to construct learning systems for nonlinear optimal control. This paper presents GK-ADP with two-phase value iteration which combines the advantages of kernel ACDs and GP-based value iteration.The theoretical analysis reveals that, with proper learning rates, two-phase iteration is good at making Gaussian-kernel-based critic network converge to the structure with optimal hyperparameters and approximate all samples’ values.A series of simulations are carried out to verify the necessity of two-phase learning and illustrate properties of GK-ADP. Finally the numerical tests support the viewpoint that the assessment of samples’ values provides the way to refine sample set online, in order to enhance the performance of critic-actor architecture during operation.However there are some issues needed to be concerned in future. The first is how to guarantee condition (36) during learning, which is now determined by empirical ways. The second is the balance between exploration and exploitation, which is always an opening question, but seems more notable here because bad exploration-exploitation principle will lead two-phase iteration to failure not only to slow convergence.



---

*Source: 760459-2015-09-16.xml*