# A Sarsa(λ) Algorithm Based on Double-Layer Fuzzy Reasoning

Authors: Quan Liu; Xiang Mu; Wei Huang; Qiming Fu; Yonggang Zhang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Solving reinforcement learning problems in continuous space with function approximation is currently a research hotspot of machine learning. When dealing with the continuous space problems, the classicQ-iteration algorithms based on lookup table or function approximation converge slowly and are difficult to derive a continuous policy. To overcome the above weaknesses, we propose an algorithm named DFR-Sarsa(λ) based on double-layer fuzzy reasoning and prove its convergence. In this algorithm, the first reasoning layer uses fuzzy sets of state to compute continuous actions; the second reasoning layer uses fuzzy sets of action to compute the components of Q-value. Then, these two fuzzy layers are combined to compute the Q-value function of continuous action space. Besides, this algorithm utilizes the membership degrees of activation rules in the two fuzzy reasoning layers to update the eligibility traces. Applying DFR-Sarsa(λ) to the Mountain Car and Cart-pole Balancing problems, experimental results show that the algorithm not only can be used to get a continuous action policy, but also has a better convergence performance.


---

## Body

## 1. Introduction

Reinforcement learning is a kind of machine learning methods that gets the maximum cumulative rewards by interacting with the environment [1, 2]. If a reinforcement learning problem can be modeled as a Markov decision process (MDP), methods such as dynamic programming (DP), Monte Carlo (MC), and temporal difference (DP) can be used to get an optimal policy.Classic reinforcement learning methods are generally used for dealing with discrete state and action space problems, where each of the state values or state action values is stored in a lookup table. This kind of methods can effectively solve simple tasks, but not for large, continuous space problems. At present, the most common approach to solve this problem is using function approximation methods to approximate the state value or action value function. The approximate function can generalize the learned experience from a state space subset to the entire state space. Besides, an agent can choose the best action sequence through the function approximation [3, 4]. A variety of function approximation methods are used to reinforcement learning problems at present. Sutton et al. proposed a gradient TD (GTD) learning algorithm [5], which combined TD algorithms with linear function approximation, and also introduced a new objective function related to Bellman errors. Sherstov and Stone proposed a linear function approximation algorithm based on online adaptive tile coding, in which the experimental results verified its effectiveness [6]. Heinen and Engel used incremental probabilistic neural network to approximate value function in reinforcement learning, which can be used to solve continuous state space problems well [7].Reinforcement algorithms with the function approximation methods mentioned above usually have slow convergence and generally can only be used for getting discrete action policies [5–9]. By introducing prior knowledge, reinforcement learning algorithms based on fuzzy inference systems (FIS) not only can effectively accelerate the convergence rate, but also may get continuous action policies [10–12]. Horiuchi et al. put forward fuzzy interpolation-based Q-learning, which can solve the continuous space problems [13]. Glorennec and Jouffe combined FIS and Q-learning, using prior knowledge to make the global approximator, which can effectively speed up the convergence rate. However, the algorithm cannot be used to get a continuous action policy [14]. Fuzzy Sarsa proposed by Tokarchuk et al. can effectively reduce the scale of state space and accelerate the convergence rate, but it easily causes “curse of dimensionality” when applied to multidimensional state-space problems [15]. Type-2 fuzzy Q-learning proposed by Hsu and Juang has strong robustness to noise, but its time complexity is relatively high, and meanwhile, it cannot guarantee convergence [12].Though the classicQ-iteration algorithms based on only one fuzzy inference system can be used for solving continuous action space problems, there still exist reasons for the slow convergence: for each iteration step in the learning process, there might exist a state-action pair that corresponds to different Q-values due to the structure of FIS. If the next iteration step needs to use the Q-value of the mentioned state-action pair to update the value function, the algorithm will simply select a Q-value randomly, since there are no criteria on how to choose the best one from different Q-values, which will influence the learning speed. Because this situation may happen many times in the learning process, it will greatly slow down the convergence rate.In allusion to the problem that classicQ-iteration algorithms based on the lookup table and fuzzy inference system converge slowly and cannot obtain continuous action policies as well, DFR-Sarsa(λ), which means Sarsa(λ) based on double-layer fuzzy reasoning, is proposed in this paper, and the convergence is proven theoretically. The algorithm has two-layer fuzzy reasoning. Firstly, it puts states as input of the first fuzzy reasoning layer and gets continuous actions as output. Secondly, the second fuzzy reasoning layer uses the obtained actions from the first layer as input and gets Q-value component of each activation rule of the first layer. Finally, through the combination of two-layer fuzzy reasoning, Q-values of the input states are obtained. What is more, a new eligibility trace based on gradient descent is defined, which is dependent on membership degrees of activation rule in two-layer fuzzy reasoning. Applying DFR-Sarsa(λ) and other algorithms to Mountain Car and Cart-pole Balancing problems, the results show that DFR-Sarsa(λ) not only can obtain a continuous action policy, but also has a better convergence performance.


## 2. Backgrounds

### 2.1. Markov Decision Process

In reinforcement learning framework, the process interacting with the environment can be modeled as an MDP [16], and the MDP can be described as a quadruple M=〈X,U,ρ,f〉, where(1)
Xis the state set and xt∈X is the state at time t;(2)
U is the action set and ut∈U is the action that the agent takes at time t;(3)
ρ:X×U→ℝn is the reward function, that means, after the agent takes action ut at time t, the current state transfers from xt to xt+1, and the agent receives an immediate reward r(xt,ut,xt+1) at the same time. rt represents a random reward generated from a distribution with mean r(xt,ut,xt+1);(4)
f:X×U×X→[0,1] is the state transition function, where f(x,u,x′) represents the probability of reaching x′ after taking action u in state x.The policyh(x,u) is a mapping from state space X to action space U, h:X→U, which represents the probability that the agent selects action u in state x. h(x,u) is used to solve the state value function (V-function) or action value function (Q-function). V-function satisfies (1)
(1)∀x∈X:Vh(x)=∑u∈Uh(x,u)(ρ(x,u)+γ∑x′∈Xf(x,u,x′)Vh(x′)).
And Q-function satisfies (2)
(2)∀x∈X:Qh(x,u)=ρ(x,u)+γ∑x′∈Xf(x,u,x′)Vh(x′).The objective of reinforcement learning is to get the optimal policyh*. It satisfies for all x∈X:Vh*(x)≥Vh(x). Under the optimal policy h*, the optimal V-function and optimal Q-function satisfy (3) and (4), respectively:
(3)∀x∈X:V*(x)=maxu∈U(ρ(x,u)+γ∑x′∈Xf(x,u,x′)V*(x′)),(4)∀x∈X,u∈h(x):Q*(x,u)=ρ(x,u)+γ∑x′∈Xf(x,u,x′)maxu′∈UQ*(x′,u′).Iff and ρ are known, DP is a good solution for getting optimal action policy. However if f and ρ are unknown, TD algorithms such as Q-learning or Sarsa can be the choice. Sarsa is an on-policy algorithm, and when the eligibility trace mechanism is introduced, it becomes a more efficient algorithm, which can effectively deal with temporal credit assignment. Besides, Sarsa(λ) can be combined with function approximation to solve continuous state space problems.Definition1 is a constraint on bounded MDP (mainly about state-space, action-space, reward, and value function). Attention should be given that all algorithms in this paper meet the definition.Definition 1 (bounded MDP).
Xand U are known as finite sets; let Z represent the state-action set; that is, Z:X×U, and then Z is also a finite set. Reward function ρ satisfies 0≤ρ(x,u)≤C. The bound factor of MDP is β=1/(1-γ), where γ is a discount factor. For all x∈X and for all (x,u)∈Z, 0≤V(x)≤βC and 0≤Q(x,u)≤βC hold.


### 2.2. Fuzzy Inference System

FIS is a system that can handle fuzzy information. Typically, it mainly consists of a set of fuzzy rules whose design and interaction are crucial to the FIS’s performance.There are many types of fuzzy inference systems at present [17] in which a simple type of FIS named TSK-FIS is described as follows:
(5)RuleRr:ifx1isχ1rAND⋯ANDxnisχnrtheny=gr(x),
where the first part is called antecedent and the second part is called consequent. Rr  means rth rule in the rule base. x=(x1,x2,…,xN) is an N-dimensional input variable. χir is the fuzzy set in the rth fuzzy rule which corresponds to the ith dimension of input variable. A membership function μχr,i(xi) is usually used to describe it. y=gr(x) is a polynomial function with an input variable x. If the input x is a vector, the output y is also a vector. When gr(x) is a constant, FIS is called zero-order FIS.When the FIS has an exact input valuex=(x1,x2,…,xN), we can calculate the firing strength ϕr(x) of the rth rule (for T-norm product):
(6)ϕr(x)=μχr,1(x1)·μχr,2(x2)·⋯·μχr,N(xN),r=1,…NR.ϕr(x) is used to calculate the output of FIS: set firing strength ϕr(x) as weight, multiply their corresponding consequent and sum up; then we can obtain the final output Y(x) as follows:
(7)Y(x)=∑(ϕ1(x)y1+ϕ2(x)y2+⋯+ϕNR(x)yNR)∑(ϕ1(x)+ϕ2(x)+⋯+ϕNR(x)).TSK-FIS can be used for function approximation which approximates the objective function by updating the consequent of fuzzy rules. In general, the approximation error is measured by mean square error (MSE). When FIS gets an optimal approximation performance, the vectorθ, which consists of all rules consequents, satisfies (8)
(8)θ=argminθ∑i=1N(Yi(x)-Y^i(x))2,
where Yi(x) is the objective function and Y^i(x) is its approximate function.


## 2.1. Markov Decision Process

In reinforcement learning framework, the process interacting with the environment can be modeled as an MDP [16], and the MDP can be described as a quadruple M=〈X,U,ρ,f〉, where(1)
Xis the state set and xt∈X is the state at time t;(2)
U is the action set and ut∈U is the action that the agent takes at time t;(3)
ρ:X×U→ℝn is the reward function, that means, after the agent takes action ut at time t, the current state transfers from xt to xt+1, and the agent receives an immediate reward r(xt,ut,xt+1) at the same time. rt represents a random reward generated from a distribution with mean r(xt,ut,xt+1);(4)
f:X×U×X→[0,1] is the state transition function, where f(x,u,x′) represents the probability of reaching x′ after taking action u in state x.The policyh(x,u) is a mapping from state space X to action space U, h:X→U, which represents the probability that the agent selects action u in state x. h(x,u) is used to solve the state value function (V-function) or action value function (Q-function). V-function satisfies (1)
(1)∀x∈X:Vh(x)=∑u∈Uh(x,u)(ρ(x,u)+γ∑x′∈Xf(x,u,x′)Vh(x′)).
And Q-function satisfies (2)
(2)∀x∈X:Qh(x,u)=ρ(x,u)+γ∑x′∈Xf(x,u,x′)Vh(x′).The objective of reinforcement learning is to get the optimal policyh*. It satisfies for all x∈X:Vh*(x)≥Vh(x). Under the optimal policy h*, the optimal V-function and optimal Q-function satisfy (3) and (4), respectively:
(3)∀x∈X:V*(x)=maxu∈U(ρ(x,u)+γ∑x′∈Xf(x,u,x′)V*(x′)),(4)∀x∈X,u∈h(x):Q*(x,u)=ρ(x,u)+γ∑x′∈Xf(x,u,x′)maxu′∈UQ*(x′,u′).Iff and ρ are known, DP is a good solution for getting optimal action policy. However if f and ρ are unknown, TD algorithms such as Q-learning or Sarsa can be the choice. Sarsa is an on-policy algorithm, and when the eligibility trace mechanism is introduced, it becomes a more efficient algorithm, which can effectively deal with temporal credit assignment. Besides, Sarsa(λ) can be combined with function approximation to solve continuous state space problems.Definition1 is a constraint on bounded MDP (mainly about state-space, action-space, reward, and value function). Attention should be given that all algorithms in this paper meet the definition.Definition 1 (bounded MDP).
Xand U are known as finite sets; let Z represent the state-action set; that is, Z:X×U, and then Z is also a finite set. Reward function ρ satisfies 0≤ρ(x,u)≤C. The bound factor of MDP is β=1/(1-γ), where γ is a discount factor. For all x∈X and for all (x,u)∈Z, 0≤V(x)≤βC and 0≤Q(x,u)≤βC hold.


## 2.2. Fuzzy Inference System

FIS is a system that can handle fuzzy information. Typically, it mainly consists of a set of fuzzy rules whose design and interaction are crucial to the FIS’s performance.There are many types of fuzzy inference systems at present [17] in which a simple type of FIS named TSK-FIS is described as follows:
(5)RuleRr:ifx1isχ1rAND⋯ANDxnisχnrtheny=gr(x),
where the first part is called antecedent and the second part is called consequent. Rr  means rth rule in the rule base. x=(x1,x2,…,xN) is an N-dimensional input variable. χir is the fuzzy set in the rth fuzzy rule which corresponds to the ith dimension of input variable. A membership function μχr,i(xi) is usually used to describe it. y=gr(x) is a polynomial function with an input variable x. If the input x is a vector, the output y is also a vector. When gr(x) is a constant, FIS is called zero-order FIS.When the FIS has an exact input valuex=(x1,x2,…,xN), we can calculate the firing strength ϕr(x) of the rth rule (for T-norm product):
(6)ϕr(x)=μχr,1(x1)·μχr,2(x2)·⋯·μχr,N(xN),r=1,…NR.ϕr(x) is used to calculate the output of FIS: set firing strength ϕr(x) as weight, multiply their corresponding consequent and sum up; then we can obtain the final output Y(x) as follows:
(7)Y(x)=∑(ϕ1(x)y1+ϕ2(x)y2+⋯+ϕNR(x)yNR)∑(ϕ1(x)+ϕ2(x)+⋯+ϕNR(x)).TSK-FIS can be used for function approximation which approximates the objective function by updating the consequent of fuzzy rules. In general, the approximation error is measured by mean square error (MSE). When FIS gets an optimal approximation performance, the vectorθ, which consists of all rules consequents, satisfies (8)
(8)θ=argminθ∑i=1N(Yi(x)-Y^i(x))2,
where Yi(x) is the objective function and Y^i(x) is its approximate function.


## 3. DFR-Sarsa(λ)

### 3.1. The Update ofQ-Value

Under the framework of MDP, two-layer fuzzy inference structures are constructed to approximateQ-function. Figure 1 shows the framework using two-layer fuzzy reasoning to approximate Q-function, where the inputs of FIS1 are states; the outputs are continuous actions obtained by FIS1 through fuzzy reasoning; the inputs of FIS2 are continuous actions obtained from FIS1; the outputs are the components of Q-value of the continuous actions. Then, the two-layer FISs are combined to get the approximating Q-function of continuous action C(x).Figure 1
Framework of approximating theQ-value functions by using double-layer fuzzy reasoning.The main structure of the two-layer FIS is described as follows.(1) The rule of FIS1 is given as follows:(9)RuleRr:ifx1isχ1rAND⋯ANDxnisχnrtheny=ur,1withqr,1=θr,1ory=ur,2withqr,2=θr,2⋮ory=ur,Mwithqr,M=θr,M,
where x=(x1,x2,…,xN) is the state and ur,j is the jth discrete action in the rth fuzzy rule. The action space is divided into M discrete actions. qr,j is a component of Q-value corresponding to the jth discrete action in the rth fuzzy rule. When the state is x, the firing strength of the rth rule is
(10)φr(x)=μχr,1(x1)·μχr,2(x2)·⋯·μχr,N(xN).
If φr(x)>0, we call the rth rule “the activation rule.”In the activation ruleRr, we select an action from M discrete actions by ε-greedy action selection policy according to the value qr,j. The selected action is called activation action, denoted by u~r. Therefore, by multiplying activation actions selected from FIS1 to its firing strength φr(x) and summing them up, we get the continuous action C(x) as follows:
(11)C(x)=∑r=1NRφr(x)u~r∑r=1NRφr(x).We callC(x) a continuous action because the change of C(x) is smooth with state x, which does not mean that any action in action space can be selected in state x. To simplify (11), regularize the firing strength φr(x) as follows:
(12)ϕr(x)=φr(x)∑r=1NRφr(x);
so (11) can be written as
(13)C(x)=∑r=1NRϕr(x)u~r.(2) The rule of FIS2 is given as follows:(14)R~r,1:ifuisνr,1thenqr,1=θr,1R~r,2:ifuisνr,2thenqr,2=θr,2⋮R~r,M:ifuisνr,Mthenqr,M=θr,M.The construction ofR~r,j depends on FIS1. The core of the fuzzy set νr,j is the jth action of the rth rule in FIS1, and its membership function is described as σνi,j(u); the value qr,j from the consequent part of the rule equals the value qr,j in FIS1.Set the continuous actionC(x) obtained from FIS1 as the input of FIS2; it can activate NR~ rules of FIS2. Through fuzzy reasoning of FIS2, we can get the Q-value component of the rth rule in FIS1 as follows:
(15)Q~r(x,C(x))=∑j=1Mσνr,j(C(x))θr,j∑j=1Mσνr,j(C(x)).In the same way of getting (12), regularize the membership function σνr,j(C(x)) in (15); we get
(16)μνr,j(C(x))=σνr,j(C(x))∑j=1Mσνr,j(C(x));
then (15) can be written as
(17)Q~r(x,C(x))=∑j=1Mμνr,j(C(x))θr,j.From (17), we can get Q~r(x,C(x)), the Q-value component obtained by the activation rule Rr of FIS1. So when taking continuous action C(x), the Q-value of all activation rules in FIS1 is given as follows:
(18)Q(x,C(x))=∑r=1NRϕr(x)Q~r(x,C(x))=∑r=1NR∑j=1Mϕr(x)μνr,j(C(x))θr,j.From (18) we can see that Q-value depends on fuzzy sets of the two-layer FIS and their shared consequent variables θr,j. Since fuzzy sets are set according to prior knowledge in advance, they are no longer changed in the algorithm. In order to get convergent Q-value, the FISs require updating θr,j until convergence.In order to minimize the approximation error of FIS, that is, parameter vectorθ meets (8), the algorithm uses gradient descent method to update the parameter vector θ as follows:
(19)θt+1=θt-12α∇θt[rt+1+γQt(xt+1,ut+1)-Qt(xt,ut)]2=θt+α[rt+1+γQt(xt+1,ut+1)-Qt(xt,ut)]∇θtQt(xt,ut),
where the bracket part in (19) is the TD error. Set δ=rt+1+γQt(xt+1,ut+1)-Qt(xt,ut); combining the backward TD(λ) algorithm [1], we get
(20)θt+1=θt+αδet,
where α is a step-size parameter and et is the eligibility trace vector at time t, which corresponds to parameter vector θt. It is updated as follows:
(21)et(r,j)⟵{γλet-1(r,j)+∇θtQt(xt,ut),if∇θtQt(xt,ut)≠0→,γλet-1(r,j),else.et of (21) is a kind of accumulating trace [1], where γ is the discount factor and λ is the decay factor. ∇θtQt(xt,ut) represents the gradient vector obtained by the partial derivative of Q-function on each dimension of parameter vector at time t [1]. According to (18), we get the gradient value of each dimension in θt at time t as follows:
(22)∇θr,jtQt(x,u)=∇θr,jt∑i=1NR∑j=1Mϕr(x)μνr,j(u)θr,j=ϕr(x)μνr,j(u),11111111111111111111wherer=1,…,NR,j=1,…,M;
then (21) can be further expressed as
(23)et(r,j)⟵{γλet-1(r,j)+ϕr(x)μνr,j(u),ifϕr(x)≠0andμνr,j(u)≠0,γλet-1(r,j),else.


### 3.2. The Learning Process of DFR-Sarsa(λ)

In this section, DFR-Sarsa(λ) is proposed based on the algorithm Sarsa in literature [1] and the content of MDP in Section 2.1. DFR-Sarsa(λ) not only can solve reinforcement learning problems with continuous state and discrete action space, but also can solve problems with continuous state and continuous action space. Algorithm 1 describes the general process of DFR-Sarsa(λ).Algorithm 1:DFR-Sarsa(λ).
(1) Initialize parameter vector θ=0→, eligibility trace vector e=0→, discount factor γ, step-size parameter α
(2)Repeat(for every episode):
(3)x← initial state
(4) According to   (10), compute ϕr(x), r=1,…,NR
(5) According toɛ-greedy policy, select activation action u~r, r=1,…,NR
(6) According to   (13), select action u when state is x
(7) According to   (16), compute μνr,j(u), r=1,…,NR, j=1,…,M
(8) According to   (17) and (18), compute Qu
(9) Repeat(for each step of episode)
(10)  Update eligibility trace:e(r,j)←γλe(r,j)+ϕr(x)μνr,j(u), r=1,…,NR, j=1,…,M
(11)  Take actionu, receive next state x′ and reward r
(12)δ←r-Qu
(13)  According toɛ-greedy policy, select activation action u~r, r=1,…,NR
(14)  According to   (13), select action u′ when state is x′
(15)  According to   (16), compute μνr,j(u′), r=1,…,NR, j=1,…,M
(16)  According to   (10), compute ϕr(x′), r=1,…,NR
(17)  According to   (17) and (18), compute Qu′
(18)δ←δ+γQu′
(19)θ←θ+αδe
(20)u←u′
(21)Until x′ is the terminal state
(22) Until preset episode number or other terminal condition meets


### 3.3. Convergence Analysis

In the literature [18, 19], the convergence of on-policy TD(λ) using linear function approximation is analyzed in detail. When this kind of algorithm meets some assumptions and lemmas, it converges with probability 1. Since DFR-Sarsa(λ) is exactly such an on-policy TD(λ) algorithm, it can be proved to be convergent when it satisfies some assumptions and lemmas in literature [18]. And this paper will not take too much details for its convergence proof.Assumption 2.
The state transition function and reward function of MDP follow stable distributions.Lemma 3.
The Markov chain that DFR-Sarsa(λ) depends on is irreducible and aperiodic, and the reward and value function are bounded.Proof.
Firstly, we prove its irreducibility. According to the property of Markov process, if any two states of a Markov process can be transferred from each other, it is irreducible [20]. DFR-Sarsa(λ) is used for solving reinforcement learning problems that satisfy MDP framework, and the MDP meets Definition 1. Thus for any state x in the MDP, there must exist an f that meets f(x,u,x′)≥0, which indicates that state x can be visited infinitely. Therefore, each state can be transferred to any other state. So the Markov chain of DFR-Sarsa(λ) is irreducible.
Secondly, we prove that it is aperiodic. For the irreducible Markov chain, if one of the states in Markov chain is proved aperiodic, the entire Markov chain can be proved aperiodic. In addition, if a state of the Markov Chain has the property of autoregression, the state can be proven aperiodic [20]. For state x of the MDP, there must exist a state transition satisfying f(x,u,x)>0, which indicates that state x is autoregressive. From the above analysis, we can conclude that the MDP is aperiodic. Therefore, the Markov chain that DFR-Sarsa(λ) depends on is aperiodic.
Finally, we prove that its reward and value function are bounded. Literature [1] shows that value function is a discounted accumulating reward function, which satisfies the equation Q(x,u)=∑i=0∞γiρ(x,u), γ∈(0,1). By Definition 1, we know that the reward function ρ is bounded, and it satisfies 0≤ρ(x,u)≤C, where C is a constant. Hence
(24)Q(x,u)=∑i=0∞γiρ(x,u)<∑i=0∞γiC=limi→∞(1-γi)1-γC=C1-γ.
By Inequation (24), we can conclude that value function Q(x,u) is bounded.
In summary, Lemma3 is proved.Condition 1.
For each membership functioni, there exists a unique state xi that μi(xi)>μi(x), for all x≠xi, while the other membership functions in state xi are 0; that is, μi′(xi)=0, for all i′≠i.Lemma 4.
The basis functions of DFR-Sarsa(λ) are bounded, and the basis function vector is linearly independent.Proof.
Firstly, we prove the basis functions are bounded. Fromϕr(x)∈[0,1] and μνr,j(C(x))∈[0,1], we get
(25)∥ϕr(x)μνr,j(C(x))∥∞≤1,
where ∥·∥∞ represents infinite norm. Since the basis function of DFR-Sarsa(λ) is known as ϕr(x)μνr,j(C(x)) from (25), we get that the basis functions of DFR-Sarsa(λ) are bounded.
Secondly, we prove the basis function vector is linearly independent. In order to make the basis function vector linearly independent, let the basis functions meet Condition1 [21], where the function form is shown in Figure 4. From literature [21] we know that, when Condition 1 is met, the basis function vector is linearly independent.
The requirement in Condition1 can be relaxed appropriately by making the membership degree of μi′(xi) at state xi a small value, for example, a Gaussian membership function with smaller standard deviation. Applying the membership function to DFR-Sarsa(λ), experimental results show that DFR-Sarsa(λ) is convergent, though the convergence still cannot be given theoretically.
In summary, Lemma4 is proved.Lemma 5.
Step-size parameterα of DFR-Sarsa(λ) satisfies (26)
(26)∑t=0∞αt=∞,∑t=0∞αt2<∞.Proof.
Set step-size parameter of DFR-Sarsa(λ)  α=1/(t+1), where t is the time step. By Newton power series expansion, we get
(27)∑t=0∞αt=∑t=0∞(1+12+⋯+1t)=ln(t+1)+r,
where r=0.577218 is Euler's constant. Because lnt is an increasing function, it satisfies ∑t=0∞αt=∞ when t→∞.
Cosider(28)∑t=0∞αt2=∑t=0∞(12+(12)2+⋯+(1t)2)<2t-1t=2-1t;
the inequality part in Inequation (28) can be proven by induction; thus ∑t=0∞αt2<∞ is met when t→∞.
By (27) and Inequation (28), we get that the step-size parameter of DFR-Sarsa(λ) satisfies (26); thus we proved Lemma 5.Theorem 6.
Under the condition of Assumption2, if DFR-Sarsa(λ) satisfies Lemma 3 to Lemma 5, the algorithm converges with probability 1.Proof.
Literature [18] gives the related conclusion that, under the condition of Assumption 2, when on-policy TD(λ) algorithms with linear function approximation meet certain conditions (Lemma 3 to Lemma 5), the algorithms converge with probability 1. DFR-Sarsa(λ) is just such an algorithm and it meets Assumption 2 and Lemma 3 to Lemma 5. So we get that DFR-Sarsa(λ) converges with probability 1.


## 3.1. The Update ofQ-Value

Under the framework of MDP, two-layer fuzzy inference structures are constructed to approximateQ-function. Figure 1 shows the framework using two-layer fuzzy reasoning to approximate Q-function, where the inputs of FIS1 are states; the outputs are continuous actions obtained by FIS1 through fuzzy reasoning; the inputs of FIS2 are continuous actions obtained from FIS1; the outputs are the components of Q-value of the continuous actions. Then, the two-layer FISs are combined to get the approximating Q-function of continuous action C(x).Figure 1
Framework of approximating theQ-value functions by using double-layer fuzzy reasoning.The main structure of the two-layer FIS is described as follows.(1) The rule of FIS1 is given as follows:(9)RuleRr:ifx1isχ1rAND⋯ANDxnisχnrtheny=ur,1withqr,1=θr,1ory=ur,2withqr,2=θr,2⋮ory=ur,Mwithqr,M=θr,M,
where x=(x1,x2,…,xN) is the state and ur,j is the jth discrete action in the rth fuzzy rule. The action space is divided into M discrete actions. qr,j is a component of Q-value corresponding to the jth discrete action in the rth fuzzy rule. When the state is x, the firing strength of the rth rule is
(10)φr(x)=μχr,1(x1)·μχr,2(x2)·⋯·μχr,N(xN).
If φr(x)>0, we call the rth rule “the activation rule.”In the activation ruleRr, we select an action from M discrete actions by ε-greedy action selection policy according to the value qr,j. The selected action is called activation action, denoted by u~r. Therefore, by multiplying activation actions selected from FIS1 to its firing strength φr(x) and summing them up, we get the continuous action C(x) as follows:
(11)C(x)=∑r=1NRφr(x)u~r∑r=1NRφr(x).We callC(x) a continuous action because the change of C(x) is smooth with state x, which does not mean that any action in action space can be selected in state x. To simplify (11), regularize the firing strength φr(x) as follows:
(12)ϕr(x)=φr(x)∑r=1NRφr(x);
so (11) can be written as
(13)C(x)=∑r=1NRϕr(x)u~r.(2) The rule of FIS2 is given as follows:(14)R~r,1:ifuisνr,1thenqr,1=θr,1R~r,2:ifuisνr,2thenqr,2=θr,2⋮R~r,M:ifuisνr,Mthenqr,M=θr,M.The construction ofR~r,j depends on FIS1. The core of the fuzzy set νr,j is the jth action of the rth rule in FIS1, and its membership function is described as σνi,j(u); the value qr,j from the consequent part of the rule equals the value qr,j in FIS1.Set the continuous actionC(x) obtained from FIS1 as the input of FIS2; it can activate NR~ rules of FIS2. Through fuzzy reasoning of FIS2, we can get the Q-value component of the rth rule in FIS1 as follows:
(15)Q~r(x,C(x))=∑j=1Mσνr,j(C(x))θr,j∑j=1Mσνr,j(C(x)).In the same way of getting (12), regularize the membership function σνr,j(C(x)) in (15); we get
(16)μνr,j(C(x))=σνr,j(C(x))∑j=1Mσνr,j(C(x));
then (15) can be written as
(17)Q~r(x,C(x))=∑j=1Mμνr,j(C(x))θr,j.From (17), we can get Q~r(x,C(x)), the Q-value component obtained by the activation rule Rr of FIS1. So when taking continuous action C(x), the Q-value of all activation rules in FIS1 is given as follows:
(18)Q(x,C(x))=∑r=1NRϕr(x)Q~r(x,C(x))=∑r=1NR∑j=1Mϕr(x)μνr,j(C(x))θr,j.From (18) we can see that Q-value depends on fuzzy sets of the two-layer FIS and their shared consequent variables θr,j. Since fuzzy sets are set according to prior knowledge in advance, they are no longer changed in the algorithm. In order to get convergent Q-value, the FISs require updating θr,j until convergence.In order to minimize the approximation error of FIS, that is, parameter vectorθ meets (8), the algorithm uses gradient descent method to update the parameter vector θ as follows:
(19)θt+1=θt-12α∇θt[rt+1+γQt(xt+1,ut+1)-Qt(xt,ut)]2=θt+α[rt+1+γQt(xt+1,ut+1)-Qt(xt,ut)]∇θtQt(xt,ut),
where the bracket part in (19) is the TD error. Set δ=rt+1+γQt(xt+1,ut+1)-Qt(xt,ut); combining the backward TD(λ) algorithm [1], we get
(20)θt+1=θt+αδet,
where α is a step-size parameter and et is the eligibility trace vector at time t, which corresponds to parameter vector θt. It is updated as follows:
(21)et(r,j)⟵{γλet-1(r,j)+∇θtQt(xt,ut),if∇θtQt(xt,ut)≠0→,γλet-1(r,j),else.et of (21) is a kind of accumulating trace [1], where γ is the discount factor and λ is the decay factor. ∇θtQt(xt,ut) represents the gradient vector obtained by the partial derivative of Q-function on each dimension of parameter vector at time t [1]. According to (18), we get the gradient value of each dimension in θt at time t as follows:
(22)∇θr,jtQt(x,u)=∇θr,jt∑i=1NR∑j=1Mϕr(x)μνr,j(u)θr,j=ϕr(x)μνr,j(u),11111111111111111111wherer=1,…,NR,j=1,…,M;
then (21) can be further expressed as
(23)et(r,j)⟵{γλet-1(r,j)+ϕr(x)μνr,j(u),ifϕr(x)≠0andμνr,j(u)≠0,γλet-1(r,j),else.


## 3.2. The Learning Process of DFR-Sarsa(λ)

In this section, DFR-Sarsa(λ) is proposed based on the algorithm Sarsa in literature [1] and the content of MDP in Section 2.1. DFR-Sarsa(λ) not only can solve reinforcement learning problems with continuous state and discrete action space, but also can solve problems with continuous state and continuous action space. Algorithm 1 describes the general process of DFR-Sarsa(λ).Algorithm 1:DFR-Sarsa(λ).
(1) Initialize parameter vector θ=0→, eligibility trace vector e=0→, discount factor γ, step-size parameter α
(2)Repeat(for every episode):
(3)x← initial state
(4) According to   (10), compute ϕr(x), r=1,…,NR
(5) According toɛ-greedy policy, select activation action u~r, r=1,…,NR
(6) According to   (13), select action u when state is x
(7) According to   (16), compute μνr,j(u), r=1,…,NR, j=1,…,M
(8) According to   (17) and (18), compute Qu
(9) Repeat(for each step of episode)
(10)  Update eligibility trace:e(r,j)←γλe(r,j)+ϕr(x)μνr,j(u), r=1,…,NR, j=1,…,M
(11)  Take actionu, receive next state x′ and reward r
(12)δ←r-Qu
(13)  According toɛ-greedy policy, select activation action u~r, r=1,…,NR
(14)  According to   (13), select action u′ when state is x′
(15)  According to   (16), compute μνr,j(u′), r=1,…,NR, j=1,…,M
(16)  According to   (10), compute ϕr(x′), r=1,…,NR
(17)  According to   (17) and (18), compute Qu′
(18)δ←δ+γQu′
(19)θ←θ+αδe
(20)u←u′
(21)Until x′ is the terminal state
(22) Until preset episode number or other terminal condition meets


## 3.3. Convergence Analysis

In the literature [18, 19], the convergence of on-policy TD(λ) using linear function approximation is analyzed in detail. When this kind of algorithm meets some assumptions and lemmas, it converges with probability 1. Since DFR-Sarsa(λ) is exactly such an on-policy TD(λ) algorithm, it can be proved to be convergent when it satisfies some assumptions and lemmas in literature [18]. And this paper will not take too much details for its convergence proof.Assumption 2.
The state transition function and reward function of MDP follow stable distributions.Lemma 3.
The Markov chain that DFR-Sarsa(λ) depends on is irreducible and aperiodic, and the reward and value function are bounded.Proof.
Firstly, we prove its irreducibility. According to the property of Markov process, if any two states of a Markov process can be transferred from each other, it is irreducible [20]. DFR-Sarsa(λ) is used for solving reinforcement learning problems that satisfy MDP framework, and the MDP meets Definition 1. Thus for any state x in the MDP, there must exist an f that meets f(x,u,x′)≥0, which indicates that state x can be visited infinitely. Therefore, each state can be transferred to any other state. So the Markov chain of DFR-Sarsa(λ) is irreducible.
Secondly, we prove that it is aperiodic. For the irreducible Markov chain, if one of the states in Markov chain is proved aperiodic, the entire Markov chain can be proved aperiodic. In addition, if a state of the Markov Chain has the property of autoregression, the state can be proven aperiodic [20]. For state x of the MDP, there must exist a state transition satisfying f(x,u,x)>0, which indicates that state x is autoregressive. From the above analysis, we can conclude that the MDP is aperiodic. Therefore, the Markov chain that DFR-Sarsa(λ) depends on is aperiodic.
Finally, we prove that its reward and value function are bounded. Literature [1] shows that value function is a discounted accumulating reward function, which satisfies the equation Q(x,u)=∑i=0∞γiρ(x,u), γ∈(0,1). By Definition 1, we know that the reward function ρ is bounded, and it satisfies 0≤ρ(x,u)≤C, where C is a constant. Hence
(24)Q(x,u)=∑i=0∞γiρ(x,u)<∑i=0∞γiC=limi→∞(1-γi)1-γC=C1-γ.
By Inequation (24), we can conclude that value function Q(x,u) is bounded.
In summary, Lemma3 is proved.Condition 1.
For each membership functioni, there exists a unique state xi that μi(xi)>μi(x), for all x≠xi, while the other membership functions in state xi are 0; that is, μi′(xi)=0, for all i′≠i.Lemma 4.
The basis functions of DFR-Sarsa(λ) are bounded, and the basis function vector is linearly independent.Proof.
Firstly, we prove the basis functions are bounded. Fromϕr(x)∈[0,1] and μνr,j(C(x))∈[0,1], we get
(25)∥ϕr(x)μνr,j(C(x))∥∞≤1,
where ∥·∥∞ represents infinite norm. Since the basis function of DFR-Sarsa(λ) is known as ϕr(x)μνr,j(C(x)) from (25), we get that the basis functions of DFR-Sarsa(λ) are bounded.
Secondly, we prove the basis function vector is linearly independent. In order to make the basis function vector linearly independent, let the basis functions meet Condition1 [21], where the function form is shown in Figure 4. From literature [21] we know that, when Condition 1 is met, the basis function vector is linearly independent.
The requirement in Condition1 can be relaxed appropriately by making the membership degree of μi′(xi) at state xi a small value, for example, a Gaussian membership function with smaller standard deviation. Applying the membership function to DFR-Sarsa(λ), experimental results show that DFR-Sarsa(λ) is convergent, though the convergence still cannot be given theoretically.
In summary, Lemma4 is proved.Lemma 5.
Step-size parameterα of DFR-Sarsa(λ) satisfies (26)
(26)∑t=0∞αt=∞,∑t=0∞αt2<∞.Proof.
Set step-size parameter of DFR-Sarsa(λ)  α=1/(t+1), where t is the time step. By Newton power series expansion, we get
(27)∑t=0∞αt=∑t=0∞(1+12+⋯+1t)=ln(t+1)+r,
where r=0.577218 is Euler's constant. Because lnt is an increasing function, it satisfies ∑t=0∞αt=∞ when t→∞.
Cosider(28)∑t=0∞αt2=∑t=0∞(12+(12)2+⋯+(1t)2)<2t-1t=2-1t;
the inequality part in Inequation (28) can be proven by induction; thus ∑t=0∞αt2<∞ is met when t→∞.
By (27) and Inequation (28), we get that the step-size parameter of DFR-Sarsa(λ) satisfies (26); thus we proved Lemma 5.Theorem 6.
Under the condition of Assumption2, if DFR-Sarsa(λ) satisfies Lemma 3 to Lemma 5, the algorithm converges with probability 1.Proof.
Literature [18] gives the related conclusion that, under the condition of Assumption 2, when on-policy TD(λ) algorithms with linear function approximation meet certain conditions (Lemma 3 to Lemma 5), the algorithms converge with probability 1. DFR-Sarsa(λ) is just such an algorithm and it meets Assumption 2 and Lemma 3 to Lemma 5. So we get that DFR-Sarsa(λ) converges with probability 1.


## 4. Experiments

In order to verify DFR-Sarsa(λ)’s performance about the convergence rate, iteration steps after convergence, and the effectiveness of continuous action policy, we take two problems as experimental benchmarks: Mountain Car and Cart-pole Balancing. These two problems are classic episodic tasks with continuous state and action spaces in reinforcement learning, which are shown in Figures 2 and 3, respectively.Figure 2
Mountain Car.Figure 3
Cart-pole Balancing.Figure 4
Triangular membership functions (except the domains of states are different, the form of membership functions of position, and velocity is described in Figure4. Besides, the form of membership functions in Section 4.2 is also the same).


### 4.1. Mountain Car

Mountain Car is a representative problem with continuous state space, as shown in Figure2. Suppose the underpowered car cannot accelerate up directly to reach the top of the right side. So, it has to move around more than once to get there. Modeling the task as an MDP, in which the state represented a two-dimensional variable: location and speed; that is, x=[y,v]. The action is the force that drives the car to move horizontally, which is bounded in [-1,1]. In this problem, the system dynamics are described as follows:
(29)vt+1=bound[vt+0.001ut+gcos(3yt)],yt+1=bound[yt+1],
where bound(vt)∈[-0.07,+0.07], bound(yt)∈[-1.5,+0.5], and g=0.0025 is a constant related to gravity. In addition, time step is 0.1 s and the reward function is as follows:
(30)rt={-1,y<0.5,0,y≥0.5.
Equation (30) is a punishment reward function, where rt means the reward received at time t.In the simulation, the number of episodes is set to 1000. The maximum time step in each episode is also set to 1000. The initial state of the car isy=-0.5, u=0. When the car arrives to the destination (y=0.5) or the time steps exceed 1000, we finish this episode and begin a new one. The experiment will end after 1000 episodes.In order to show the effectiveness of DFR-Sarsa(λ), we compare the algorithm with Fuzzy Sarsa proposed by Tokarchuk et al. [15], GD-Sarsa(λ) proposed by Sutton et al. [3], and Fuzzy Q(λ) proposed by Zajdel [22]. Additionally, the effect of eligibility trace on the convergence performance is also tested.At present, there is no proper way to select parameters that make the four algorithms have their best performance, respectively. In order to make the comparison more reasonable, the parameters that exist in all of the four algorithms will be set at the same value, while the parameters that do not exist in all of the four algorithms will be set at the value from where it firstly comes.We first set the parameters of DFR-Sarsa(λ): 20 triangular fuzzy sets whose cores are equidistant are used to partition each state variable, which results in 400 fuzzy rules. Similarly, use eight triangular fuzzy sets whose cores are equidistant to partition the continuous action space, where the number of fuzzy rules is 8. Set the other parametersε=0.001, α=0.9, λ=0.9, and γ=1.0. The form of fuzzy partition in Fuzzy Sarsa is the same as in DFR-Sarsa(λ). Other parameters are set to ε=0.001, α=0.9, and γ=0.9. GD-Sarsa(λ) uses 10 tilings of 9×9 to divide state space, where the parameters are set as the best experimental parameters given in literature [1]: ε=0.001, α=0.14, λ=0.3, and γ=1.0. The form of fuzzy partition in Fuzzy Q(λ) Sarsa is also the same as in DFR-Sarsa(λ). Other parameters are set in accordance with literature [22] to ε=0.005, α=0.1, λ=0.1, and γ=0.995.DFR-Sarsa(λ), Fuzzy Sarsa, GD-Sarsa(λ), and Fuzzy Q(λ) are applied to Mountain Car. Figure 5 shows the average result in 30 independent simulation experiments. The x-coordinate indicates the number of episodes, and y-coordinate represents the average time steps the car drives from the initial state to the target. As can be seen from Figure 5, the convergence performance of DFR-Sarsa(λ) is better than those of the other three algorithms.Figure 5
Comparisons on convergent efficiency of the four algorithms.The detailed performance of the four algorithms is shown in Table1 (the benchmark time is the average time of a single iteration of DFR-Sarsa(λ)).Table 1
Performance comparison of the four algorithms in Mountain Car problem.
Algorithm
DFR-Sarsa (λ)
FuzzyQ (λ)
GD-Sarsa (λ)
Fuzzy Sarsa
Average episodes
86
98
118
103
Average steps
79
101
134
112
Average time within an iterative step
100%
80%
30%
65%In order to test the effectiveness of the proposed eligibility trace, DFR-Sarsa(λ) with eligibility trace and DFR-Sarsa without eligibility trace are both applied in Mountain Car. Figure 6 shows the convergence performance of these two algorithms. It can be seen that these two algorithms converge in the same average time steps, but the convergence speed of DFR-Sarsa(λ) is better than that of DFR-Sarsa.Figure 6
The effect of eligibility traces on convergent efficiency of DFR-Sarsa(λ).


### 4.2. Cart-Pole Balancing

Figure3 shows a Cart-pole Balancing system, in which the cart can move left or right on the horizontal plane. A pole is hinged to the cart, which can rotate freely within a certain angle. The task is to move the cart horizontally to keep the pole standing in a certain range [-π/2,π/2]. Similarly, modeling the task as an MDP, the state is a two-dimensional variable, which is represented by the vertical angle of pole θ, and the angular velocity of the pole θ˙; that is, x=[θ,θ˙]. These two state variables satisfy θ∈[-π/2,π/2] (rad) and θ˙∈[-16π,16π] (rad/s). The action is the force exerted on the cart, which ranges from −50 N to 50 N. In addition, the force is added by a noise force which is uniformly distributed in [-10N,10N].  The system dynamics are described as
(31)θ¨=gsin(θ)-aml(θ˙)2sin(2θ)/2-αcos(θ)u4l/3-amlcos2(θ),
where g=9.8 m/s2 is acceleration of gravity, m=2.0 kg is the mass of pole, M=8.0 kg is the mass of cart, l=0.5 m is the length of pole, and constant α=1/(m+M). The change of reward depends on the change of state. At each time step (0.1 s), when the angle of the pole with vertical direction is no more than π/2, reward 0 is received. While the angle is more than π/2, the reward is −1, and the episode ends.The parameter setting in this example is similar to the settings in Section3.1, so we only give the difference here: 12 equidistant triangular fuzzy sets are used to partition the continuous action space, which leads to 144 fuzzy rules.DFR-Sarsa(λ) and GD-Sarsa(λ) are executed on 30 independent simulations on Cart-pole Balancing; the results are shown in Figure 7, where the x-coordinate represents the number of episodes; the y-coordinate represents the average time steps. As can be seen from Figure 7, the convergence performance of DFR-Sarsa(λ) is also better than GD-Sarsa(λ).Figure 7
Comparisons on convergent efficiency of the two algorithms.The detailed performance of the two algorithms is shown in Table2 (the benchmark time is the average time of a single iteration of DFR-Sarsa(λ)).Table 2
Performance comparison of the two algorithms in Cart-pole Balancing problem.
Algorithm
Episodes
Average time within an iterative step
Minimum episodes
Average episodes
DFR-Sarsa(λ)
135
155
100%
GD-Sarsa(λ)
179
204
46%Figure8 shows the results of GD-Sarsa(λ) and DFR-Sarsa(λ) on Cart-pole Balancing task, respectively. We have known that GD-Sarsa(λ) is based on discrete action policies, while DFR-Sarsa(λ) is based on continuous action policies. From Figure 8 we can see that the continuous action policy obtained by DFR-Sarsa(λ) can make the pole’s angle change in only a small angle, while discrete action policy obtained by GD-Sarsa(λ) makes the pole’s angle change in a large range. This fact indicates that policies obtained by DFR-Sarsa(λ) are much more stable than that of GD-Sarsa(λ). Thus, DFR-Sarsa(λ) is more suitable for applications which require more stable policies.Changes of the pole angleθ when using the two mentioned algorithms, respectively.
(a)
(b)


## 4.1. Mountain Car

Mountain Car is a representative problem with continuous state space, as shown in Figure2. Suppose the underpowered car cannot accelerate up directly to reach the top of the right side. So, it has to move around more than once to get there. Modeling the task as an MDP, in which the state represented a two-dimensional variable: location and speed; that is, x=[y,v]. The action is the force that drives the car to move horizontally, which is bounded in [-1,1]. In this problem, the system dynamics are described as follows:
(29)vt+1=bound[vt+0.001ut+gcos(3yt)],yt+1=bound[yt+1],
where bound(vt)∈[-0.07,+0.07], bound(yt)∈[-1.5,+0.5], and g=0.0025 is a constant related to gravity. In addition, time step is 0.1 s and the reward function is as follows:
(30)rt={-1,y<0.5,0,y≥0.5.
Equation (30) is a punishment reward function, where rt means the reward received at time t.In the simulation, the number of episodes is set to 1000. The maximum time step in each episode is also set to 1000. The initial state of the car isy=-0.5, u=0. When the car arrives to the destination (y=0.5) or the time steps exceed 1000, we finish this episode and begin a new one. The experiment will end after 1000 episodes.In order to show the effectiveness of DFR-Sarsa(λ), we compare the algorithm with Fuzzy Sarsa proposed by Tokarchuk et al. [15], GD-Sarsa(λ) proposed by Sutton et al. [3], and Fuzzy Q(λ) proposed by Zajdel [22]. Additionally, the effect of eligibility trace on the convergence performance is also tested.At present, there is no proper way to select parameters that make the four algorithms have their best performance, respectively. In order to make the comparison more reasonable, the parameters that exist in all of the four algorithms will be set at the same value, while the parameters that do not exist in all of the four algorithms will be set at the value from where it firstly comes.We first set the parameters of DFR-Sarsa(λ): 20 triangular fuzzy sets whose cores are equidistant are used to partition each state variable, which results in 400 fuzzy rules. Similarly, use eight triangular fuzzy sets whose cores are equidistant to partition the continuous action space, where the number of fuzzy rules is 8. Set the other parametersε=0.001, α=0.9, λ=0.9, and γ=1.0. The form of fuzzy partition in Fuzzy Sarsa is the same as in DFR-Sarsa(λ). Other parameters are set to ε=0.001, α=0.9, and γ=0.9. GD-Sarsa(λ) uses 10 tilings of 9×9 to divide state space, where the parameters are set as the best experimental parameters given in literature [1]: ε=0.001, α=0.14, λ=0.3, and γ=1.0. The form of fuzzy partition in Fuzzy Q(λ) Sarsa is also the same as in DFR-Sarsa(λ). Other parameters are set in accordance with literature [22] to ε=0.005, α=0.1, λ=0.1, and γ=0.995.DFR-Sarsa(λ), Fuzzy Sarsa, GD-Sarsa(λ), and Fuzzy Q(λ) are applied to Mountain Car. Figure 5 shows the average result in 30 independent simulation experiments. The x-coordinate indicates the number of episodes, and y-coordinate represents the average time steps the car drives from the initial state to the target. As can be seen from Figure 5, the convergence performance of DFR-Sarsa(λ) is better than those of the other three algorithms.Figure 5
Comparisons on convergent efficiency of the four algorithms.The detailed performance of the four algorithms is shown in Table1 (the benchmark time is the average time of a single iteration of DFR-Sarsa(λ)).Table 1
Performance comparison of the four algorithms in Mountain Car problem.
Algorithm
DFR-Sarsa (λ)
FuzzyQ (λ)
GD-Sarsa (λ)
Fuzzy Sarsa
Average episodes
86
98
118
103
Average steps
79
101
134
112
Average time within an iterative step
100%
80%
30%
65%In order to test the effectiveness of the proposed eligibility trace, DFR-Sarsa(λ) with eligibility trace and DFR-Sarsa without eligibility trace are both applied in Mountain Car. Figure 6 shows the convergence performance of these two algorithms. It can be seen that these two algorithms converge in the same average time steps, but the convergence speed of DFR-Sarsa(λ) is better than that of DFR-Sarsa.Figure 6
The effect of eligibility traces on convergent efficiency of DFR-Sarsa(λ).


## 4.2. Cart-Pole Balancing

Figure3 shows a Cart-pole Balancing system, in which the cart can move left or right on the horizontal plane. A pole is hinged to the cart, which can rotate freely within a certain angle. The task is to move the cart horizontally to keep the pole standing in a certain range [-π/2,π/2]. Similarly, modeling the task as an MDP, the state is a two-dimensional variable, which is represented by the vertical angle of pole θ, and the angular velocity of the pole θ˙; that is, x=[θ,θ˙]. These two state variables satisfy θ∈[-π/2,π/2] (rad) and θ˙∈[-16π,16π] (rad/s). The action is the force exerted on the cart, which ranges from −50 N to 50 N. In addition, the force is added by a noise force which is uniformly distributed in [-10N,10N].  The system dynamics are described as
(31)θ¨=gsin(θ)-aml(θ˙)2sin(2θ)/2-αcos(θ)u4l/3-amlcos2(θ),
where g=9.8 m/s2 is acceleration of gravity, m=2.0 kg is the mass of pole, M=8.0 kg is the mass of cart, l=0.5 m is the length of pole, and constant α=1/(m+M). The change of reward depends on the change of state. At each time step (0.1 s), when the angle of the pole with vertical direction is no more than π/2, reward 0 is received. While the angle is more than π/2, the reward is −1, and the episode ends.The parameter setting in this example is similar to the settings in Section3.1, so we only give the difference here: 12 equidistant triangular fuzzy sets are used to partition the continuous action space, which leads to 144 fuzzy rules.DFR-Sarsa(λ) and GD-Sarsa(λ) are executed on 30 independent simulations on Cart-pole Balancing; the results are shown in Figure 7, where the x-coordinate represents the number of episodes; the y-coordinate represents the average time steps. As can be seen from Figure 7, the convergence performance of DFR-Sarsa(λ) is also better than GD-Sarsa(λ).Figure 7
Comparisons on convergent efficiency of the two algorithms.The detailed performance of the two algorithms is shown in Table2 (the benchmark time is the average time of a single iteration of DFR-Sarsa(λ)).Table 2
Performance comparison of the two algorithms in Cart-pole Balancing problem.
Algorithm
Episodes
Average time within an iterative step
Minimum episodes
Average episodes
DFR-Sarsa(λ)
135
155
100%
GD-Sarsa(λ)
179
204
46%Figure8 shows the results of GD-Sarsa(λ) and DFR-Sarsa(λ) on Cart-pole Balancing task, respectively. We have known that GD-Sarsa(λ) is based on discrete action policies, while DFR-Sarsa(λ) is based on continuous action policies. From Figure 8 we can see that the continuous action policy obtained by DFR-Sarsa(λ) can make the pole’s angle change in only a small angle, while discrete action policy obtained by GD-Sarsa(λ) makes the pole’s angle change in a large range. This fact indicates that policies obtained by DFR-Sarsa(λ) are much more stable than that of GD-Sarsa(λ). Thus, DFR-Sarsa(λ) is more suitable for applications which require more stable policies.Changes of the pole angleθ when using the two mentioned algorithms, respectively.
(a)
(b)


## 5. Conclusions

In allusion to the problem that classic reinforcement learning algorithms based on lookup table or function approximation converge slowly and are difficult to obtain continuous action policies, this paper presents an algorithm with eligibility trace based on double-layer fuzzy reasoning—DFR-Sarsa(λ). Firstly, the algorithm constructs two fuzzy reasoning layers to approximate Q-function, which are associated with state, action, and Q-value. Then, it uses gradient descent method to update eligibility trace and the consequent of fuzzy rules in the two FISs. Applying the proposed algorithm and other three similar relatively new algorithms to Mountain Car and Cart-pole Balancing system, experimental results show that, compared with reinforcement learning algorithms using only one fuzzy inference system, our algorithm requires fewer steps to convergence, though it increases the time complexity; compared with algorithms based on lookup table or some other function approximation methods, DFR-Sarsa(λ) has better convergence performance and can obtain a continuous action policy.The performance of DFR-Sarsa(λ) relies on the two-layer fuzzy inference systems, while the performance of fuzzy inference system mainly depends on the fuzzy sets and fuzzy rules. In this paper, the type of fuzzy sets and the number of rules are given as prior knowledge, and they are no longer changed during the learning process. In order to achieve a much better convergence performance, we will focus on using appropriate optimization algorithms to optimize the membership functions and adjust the fuzzy rules adaptively.



---

*Source: 561026-2013-12-05.xml*