# Kernel Recursive Least-Squares Temporal Difference Algorithms with Sparsification and Regularization

Authors: Chunyuan Zhang; Qingxin Zhu; Xinzheng Niu
Journal: Computational Intelligence and Neuroscience
 (2016)

---

## Abstract

By combining with sparse kernel methods, least-squares temporal difference (LSTD) algorithms can construct the feature dictionary automatically and obtain a better generalization ability. However, the previous kernel-based LSTD algorithms do not consider regularization and their sparsification processes are batch or offline, which hinder their widespread applications in online learning problems. In this paper, we combine the following five techniques and propose two novel kernel recursive LSTD algorithms: (i) online sparsification, which can cope with unknown state regions and be used for online learning, (ii)L2 and L1 regularization, which can avoid overfitting and eliminate the influence of noise, (iii) recursive least squares, which can eliminate matrix-inversion operations and reduce computational complexity, (iv) a sliding-window approach, which can avoid caching all history samples and reduce the computational cost, and (v) the fixed-point subiteration and online pruning, which can make L1 regularization easy to implement. Finally, simulation results on two 50-state chain problems demonstrate the effectiveness of our algorithms.


---

## Body

## 1. Introduction

The least-squares temporal difference (LSTD) learning may be the most popular approach for policy evaluation in reinforcement learning (RL) [1, 2]. Compared with the standard temporal difference (TD) learning, LSTD uses samples more efficiently and eliminates all step-size parameters. However, LSTD also has some drawbacks. First, LSTD requires a matrix-inversion operation at each time step. To reduce computational complexity, Bradtke and Barto proposed a recursive LSTD (RLSTD) algorithm [1], and Xu et al. proposed a RLSTD(λ) algorithm [3]. But these two algorithms still require many features especially for highly nonlinear RL problems, since the RLS approximator assumes a linear model [4]. Second, when the number of features is larger than the number of training samples, LSTD is prone to overfitting. To overcome this problem, Kolter and Ng proposed an L1-regularized LSTD algorithm called LARS-TD for feature selection [5], but it is only applicable for batch learning and its implementation is complicated. On this basis, Chen et al. proposed an L2-regularized RLSTD algorithm [6]. In contrast with LARS-TD, it has an analytical solution, but it cannot obtain a sparse solution. Third, LSTD requires users to design the feature vector manually, and poor design choices can result in estimates that diverge from the optimal value function [7].In the last two decades, kernel methods have been intensively and extensively studied in supervised and unsupervised learning [8]. The basic idea behind kernel methods can be summarized as follows: By using a nonlinear transform, the origin input data can be mapped into a high-dimensional feature space, and an inner product in this space can be interpreted as a Mercer kernel function. Thus, as long as a linear algorithm can be formulated in terms of inner products, there is no need to perform computations in the high-dimensional feature space [9]. Recently, there have also been many research works on kernelizing least-squares algorithms [9–13]. Here, we only review some works related to our proposed algorithms. One typical work is the sparse kernel recursive least-squares (SKRLS) algorithm with the approximate linear dependency (ALD) criterion [11]. Compared with traditional RLS algorithms, it not only has a good nonlinear approximation ability but also can construct the feature dictionary automatically. Similarly, Chen et al. proposed an L2-regularized SKRLS algorithm with the online vector quantization [12]. Besides having the good properties of SKRLS-ALD, it can avoid overfitting. In addition, Chen et al. proposed an L1-regularized SKRLS algorithm with the fixed-point subiteration [13], which can yield a much sparser dictionary.Intuitively, we can also bring the benefits of kernel machine learning to LSTD algorithms. In fact, kernel-based RL algorithms have become more and more popular in recent years [14–22], and several works have been done for kernelizing LSTD algorithms. In an earlier paper, Xu proposed a sparse kernel-based LSTD(λ) (SKLSTD(λ)) algorithm with the ALD criterion [19]. Although this algorithm can avoid selecting features manually, it is only applicable for batch learning and its derivation is complicated. After that, Xu et al. proposed an incremental version of the SKLSTD(λ) algorithm for policy iteration [20], but this algorithm still requires a matrix-inversion operation at each time step. Moreover, the feature dictionary is required to be constructed offline, which makes this algorithm only approximate the value function correctly in the area of the state space that is covered by the training samples. Recently, Jakab and Csató proposed a sparse kernel RLSTD (SKRLSTD) algorithm by using a proximity graph sparsification method [21]. Unfortunately, its sparsification process is also offline. In addition, all of these algorithms do not consider regularization, whereas many real problems exhibit noise and the high expressiveness of the kernel matrix can result in overfitting [22].In this paper, we propose two online SKRLSTD algorithms withL2 and L1 regularization, called OSKRLSTD-L2 and OSKRLSTD-L1, respectively. Compared with the derivation of SKLSTD(λ), our derivation uses Bellman operator along with projection operator and thus is more simple. To cope with unknown state-space regions and avoid overfitting, our algorithms use online sparsification and regularization techniques. Besides, to reduce computational complexity and avoid caching all history samples, our algorithms also use the recursive least-squares and the sliding-window technique. Moreover, different from LARS-TD, OSKRLSTD-L1 uses the subiteration and online pruning to find the fixed point. These techniques make our algorithms more suitable for online RL problems with a large or continuous state space. The rest of this paper is organized as follows. In Section 2, we present preliminaries and review the LSTD algorithm. Section 3 contains the main contribution of this paper: we derive OSKRLSTD-L2 and OSKRLSTD-L1 algorithms in detail. In Section 4, we demonstrate the effectiveness of our algorithms for two 50-state chain problems. Finally, we conclude the paper in Section 5.


## 2. Background

In this section, we introduce the basic definitions and notations, which will be used throughout the paper without any further mention. We also review the LSTD algorithm, which is needed to establish our algorithms described in Section3.


### 2.1. Preliminaries

In RL and dynamic programming (DP), an underlying sequential decision-making problem is often modeled as a Markov decision process (MDP). An MDP can be defined as a tupleM=〈S,A,P,r,γ,d〉 [5], where S is a set of states, A is a set of actions, P:S×A×S→[0,1] is a state transition probability function where P(s,a,s′) denotes the probability of transitioning to state s′ when taking action a in state s, r∈R is a reward function, γ∈[0,1] is the discount factor, and d is an initial state distribution. For simplicity of presentation, we assume that S and A are finite. Given an MDP M and a policy π:S→A, the sequence s1,r1,s2,r2,… is a Markov reward process R=〈S,Pπ,Rπ,γ,d〉, where Pπ(s,s′)=∑a∈Aπ(a∣s)P(s,a,s′) and Rπ(s)=∑a∈Aπa∣s∑s′∈SPs,a,s′r(s,a,s′).RL and DP often use the state-value functionVπ(s) to evaluate how good the policy π is for the agent to be in state s. For an MDP, Vπ(s) can be defined as Vπ(s)=Eπ[∑t=0∞γtrt∣s0=s], which must obey the Bellman equation [23],(1)Vπs=Rπs+γ∑s′∈SPπs,s′Vπs′,or be expressed in vector form,(2)Vπ=Rπ+γPπVπ.If Pπ and Rπ are known, Vπ can be solved analytically; that is,(3)Vπ=I-γPπ-1Rπ,where I is the |S|×|S| identity matrix.However, different from the case in DP,Pπ and Rπ are unknown in RL. The agent has to estimate Vπ by exploring the environment. Furthermore, many real problems have a large or continuous state space, which makes Vπ(s) hard to be expressed explicitly. To overcome this problem, we often resort to linear function approximation; that is,(4)V^πs=wTϕsorV^π=Φw,where w∈Rm is a parameter vector, ϕ(s)∈Rm is the feature vector of state s, and Φ=[ϕ(s1),…,ϕ(s|S|)]T is a |S|×m feature matrix. Unfortunately, when approximating Vπ in this manner, there is usually no way to satisfy the Bellman equation exactly, because Rπ+γPπΦw may lie outside the span of Φ [5].


### 2.2. LSTD Algorithm

The LSTD algorithm presents an efficient way to findw such that V^π “approximately” satisfies the Bellman equation [5]. By solving the least-squares problem minu∈RmΦu-Rπ+γPπΦwD2, we can find a closest approximation Φu∗ in the span of Φ to replace Rπ+γPπΦw. Then, from (2) and (4), we can use w=u∗ for approximating Vπ. That means we can find w by solving the fixed-point equation:(5)w=fw=arg⁡minu∈Rm⁡Φu-Rπ+γPπΦwD2,where D is a nonnegative diagonal matrix indicating a distribution over states. Nevertheless, since Pπ and Rπ are unknown and since Φ is too large to form anyway in a large or continuous state space, we cannot solve (5) exactly. Instead, given a trajectory Ttπ={(si,si′,ri)∣i=1,…,t} following policy π, LSTD uses Φ^t=[ϕ(s1),…,ϕ(st)]T, Φ^t′=[ϕ(s1′),…,ϕ(st′)]T, and R^t=[r1,…,rt]T to replace Φ, PπΦ, and Rπ, respectively. Then, (5) can be approximately rewritten as(6)wt=f~wt=arg⁡minu∈Rm⁡Φ^tu-R^t+γΦ^t′wt22.Let ∂Φ^tu-R^t+γΦ^t′wt22/∂u=0; we have(7)f~wt=u∗=Φ^tTΦ^t-1Φ^tTR^t+γΦ^t′wt.Thus, the fixed point wt=f~(wt) can be found by(8)wt=Φ^tTΦ^t-γΦ^t′-1Φ^tTR^t.


## 2.1. Preliminaries

In RL and dynamic programming (DP), an underlying sequential decision-making problem is often modeled as a Markov decision process (MDP). An MDP can be defined as a tupleM=〈S,A,P,r,γ,d〉 [5], where S is a set of states, A is a set of actions, P:S×A×S→[0,1] is a state transition probability function where P(s,a,s′) denotes the probability of transitioning to state s′ when taking action a in state s, r∈R is a reward function, γ∈[0,1] is the discount factor, and d is an initial state distribution. For simplicity of presentation, we assume that S and A are finite. Given an MDP M and a policy π:S→A, the sequence s1,r1,s2,r2,… is a Markov reward process R=〈S,Pπ,Rπ,γ,d〉, where Pπ(s,s′)=∑a∈Aπ(a∣s)P(s,a,s′) and Rπ(s)=∑a∈Aπa∣s∑s′∈SPs,a,s′r(s,a,s′).RL and DP often use the state-value functionVπ(s) to evaluate how good the policy π is for the agent to be in state s. For an MDP, Vπ(s) can be defined as Vπ(s)=Eπ[∑t=0∞γtrt∣s0=s], which must obey the Bellman equation [23],(1)Vπs=Rπs+γ∑s′∈SPπs,s′Vπs′,or be expressed in vector form,(2)Vπ=Rπ+γPπVπ.If Pπ and Rπ are known, Vπ can be solved analytically; that is,(3)Vπ=I-γPπ-1Rπ,where I is the |S|×|S| identity matrix.However, different from the case in DP,Pπ and Rπ are unknown in RL. The agent has to estimate Vπ by exploring the environment. Furthermore, many real problems have a large or continuous state space, which makes Vπ(s) hard to be expressed explicitly. To overcome this problem, we often resort to linear function approximation; that is,(4)V^πs=wTϕsorV^π=Φw,where w∈Rm is a parameter vector, ϕ(s)∈Rm is the feature vector of state s, and Φ=[ϕ(s1),…,ϕ(s|S|)]T is a |S|×m feature matrix. Unfortunately, when approximating Vπ in this manner, there is usually no way to satisfy the Bellman equation exactly, because Rπ+γPπΦw may lie outside the span of Φ [5].


## 2.2. LSTD Algorithm

The LSTD algorithm presents an efficient way to findw such that V^π “approximately” satisfies the Bellman equation [5]. By solving the least-squares problem minu∈RmΦu-Rπ+γPπΦwD2, we can find a closest approximation Φu∗ in the span of Φ to replace Rπ+γPπΦw. Then, from (2) and (4), we can use w=u∗ for approximating Vπ. That means we can find w by solving the fixed-point equation:(5)w=fw=arg⁡minu∈Rm⁡Φu-Rπ+γPπΦwD2,where D is a nonnegative diagonal matrix indicating a distribution over states. Nevertheless, since Pπ and Rπ are unknown and since Φ is too large to form anyway in a large or continuous state space, we cannot solve (5) exactly. Instead, given a trajectory Ttπ={(si,si′,ri)∣i=1,…,t} following policy π, LSTD uses Φ^t=[ϕ(s1),…,ϕ(st)]T, Φ^t′=[ϕ(s1′),…,ϕ(st′)]T, and R^t=[r1,…,rt]T to replace Φ, PπΦ, and Rπ, respectively. Then, (5) can be approximately rewritten as(6)wt=f~wt=arg⁡minu∈Rm⁡Φ^tu-R^t+γΦ^t′wt22.Let ∂Φ^tu-R^t+γΦ^t′wt22/∂u=0; we have(7)f~wt=u∗=Φ^tTΦ^t-1Φ^tTR^t+γΦ^t′wt.Thus, the fixed point wt=f~(wt) can be found by(8)wt=Φ^tTΦ^t-γΦ^t′-1Φ^tTR^t.


## 3. Regularized OSKRLSTD Algorithms

To overcome the weaknesses of the previous kernel-based LSTD algorithms, we propose two regularized OSKRLSTD algorithms in this section.


### 3.1. OSKRLSTD-L2 Algorithm

Now, we useL2 regularization and online sparsification to derive the first OSKRLSTD algorithm, which is called OSKRLSTD-L2.First, we use the kernel trick to kernelize (6). Suppose the feature dictionary Dt={dj∣dj∈S,j=1,…,nt}, and let Φt=[ϕ(d1),…,ϕ(dnt)]T denote the corresponding feature matrix. By the Representer Theorem [24], wt and u can be expressed as follows:(9)wt=ΦtTαt=∑j=1ntαjϕdj,u=ΦtTβ=∑j=1ntβjϕdj,where αt=[αt,1,…,αt,nt]T and β=[β1,…,βnt]T are the coefficient vector of wt and u, respectively. Then, from (6), we have(10)αt=f^αt=arg⁡minβ∈Rnt⁡Φ^tΦtTβ-R^t+γΦ^t′ΦtTαt22.By the Mercer Theorem [24], the inner product of two feature vectors can be calculated by k(si,sj)=ϕ(si)Tϕ(sj). Thus, we can define Kt=ΦtΦtT, K^t=ΦtΦ^tT, and K^t′=Φt(Φ^t′)T. On this basis, (10) can be rewritten as(11)αt=f^αt=arg⁡minβ∈Rnt⁡K^tTβ-R^t+γK^t′Tαt22.Second, we try to derive theL2-regularized solution of (11). Add an L2-norm penalty into (11); that is,(12)αt=f^αt=arg⁡minβ∈Rnt⁡K^tTβ-R^t+γK^t′Tαt22+ηβ22,where η∈[0,∞) is a regularization parameter. Let ∂(K^tTβ-R^t+γK^t′Tαt22+ηβ22)/∂β=0; we have(13)K^tK^tTβ∗-γK^t′Tαt+ηβ∗=K^tR^t.Since wt=u∗, we easily have αt=β∗ from (9). Then, the above equation can be rewritten as(14)K^tK^t-γK^t′T+ηItαt=K^tR^t,where It is the nt×nt identity matrix. Thus, αt can be analytically solved as(15)αt=K^tK^t-γK^t′T+ηIt-1K^tR^t=At-1bt,where At∈Rnt×nt and bt∈Rnt denote(16)At=K^tK^t-γK^t′T+ηIt=∑i=1tktsiΔktTsi,si′+ηIt,bt=K^tR^t=∑i=1tktsiri,where kt(·)=[k(·,d1),…,k(·,dnt)]T and Δkt(si,si′)=kt(si)-γkt(si′).Third, we derive the recursive formulas ofAt-1 and αt. Under online sparsification, there are two cases: (1) Dt=Dt-1, nt=nt-1, kt(·)=kt-1(·), Δkt(si,si′)=Δkt-1(si,si′), and It=It-1; (2) Dt=Dt-1∪{st}, nt=nt-1+1, kt(·)=[kt-1T(·),k(·,st)]T, Δkt(si,si′)=[Δkt-1T(si,si′),Δkt(si,si′)]T, where Δkt(si,si′)=k(si,st)-γk(si′,st), and It is expanded as(17)It=It-10t-10t-1T1,where 0t-1 is the nt-1 dimensional zero vector.For the first case, (16) can be rewritten as follows:(18)At=At-1+kt-1stΔkt-1Tst,st′,(19)bt=bt-1+kt-1strt.Applying the matrix-inversion lemma [25] for At-1, we get(20)At-1=At-1-1-At-1-1kt-1stΔkt-1Tst,st′At-1-11+Δkt-1Tst,st′At-1-1kt-1st.Thus, plugging (19) and (20) into (15), we obtain(21)αt=αt-1+rt-αt-1TΔkt-1st,st′At-1-1kt-1st1+Δkt-1Tst,st′At-1-1kt-1st.For the second case, (16) can be rewritten as follows:(22)At=A~thtgtTpt,bt=b~tqt,where A~t and b~t are the same as the updated At and bt when the feature dictionary keeps unchanged, ht=∑i=1tΔkt(si,si′)kt-1(si), gt=∑i=1tk(si,st)Δkt-1(si,si′), pt=∑i=1tk(si,st)Δkt(si,si′)+η, and qt=∑i=1tk(si,st)ri. However, computing ht, gt, pt, and qt requires caching all history samples, and the computational cost will become more and more expensive as t increases. Inspired by the work of Van Vaerenbergh et al. [26], we introduce a sliding window Ht to deal with these problems. Let Ht={(sj,sj′,rj)∣j=max⁡1,t-M+1,…,t}, where M is the window size. We only use the samples in Ht to evaluate ht, gt, pt, and qt; that is,(23)h~t=∑j∈HtΔktsj,sj′kt-1sj,g~t=∑j∈Htksj,stΔkt-1sj,sj′,p~t=∑j∈Htksj,stΔktsj,sj′+η,q~t=∑j∈Htksj,strj.Then, similar to those in the first case, At-1 and αt can be derived as follows:(24)At-1=1mtmtA~t-1+A~t-1h~tg~tTA~t-1-A~t-1h~t-g~tTA~t-11,(25)αt=1mtmtα~t-A~t-1h~tq~t-g~tTα~tq~t-g~tTα~t,where mt=p~t-g~tTA~t-1h~t and α~t is the same as the updated αt when the dictionary keeps unchanged.Finally, we summarize the whole algorithm in Algorithm1.Algorithm 1:OSKRLSTD-L2.
(
1)Input: π to be evaluated, k(⋅,⋅), γ, η, M
(2)for  t=1,2,…  do
(3) if  t==1  then
(4)  Initialize s1, D1=s1
(5)  Take a1 given by π, and observe s1′, r1
(6)  Initialize H1=(s1,s1′,r1)
(7)  Initialize A1-1=(k(s1,s1)(Δk1(s1,s1′)+η))-1
(8)  Initialize α1=A1-1k(s1,s1)r1
(9) else
(10)  Take at given by π, and observe st′, rt
(11)   Update Ht, Dt=Dt-1
(12)   Update αt, At-1 by (21) and (20)
(13)   if  st satisfies the sparsification condition then
(14)     Dt=Dt-1∪st, α~t=αt, A~t-1=At-1
(15)     Compute h~t, g~t, p~t and q~t by (23)
(16)     Update αt, At-1 by (25) and (24)
(17)   end if
(18)  end if
(19)  st+1=st′
(20) end forRemark 1.
Here, we do not restrict the OSKRLSTD-L2 algorithm to a specific online sparsification method. That means it can be combined with many popular sparsification methods such as the novelty criterion (NC) [27] and the ALD criterion.Remark 2.
Although the OSKRLSTD-L2 algorithm is designed for infinite horizon tasks, it can be modified for episodic tasks. When st′ is an absorbing state, it only requires setting γ=0 temporarily and setting st+1 as the start state of next episode.Remark 3.
Our simulation results show that a big sliding window cannot help improve the convergence performance of the OSKRLSTD-L2 algorithm. Thus, to save memory and reduce the computational cost, M should be set to a small integer.


### 3.2. OSKRLSTD-L1 Algorithm

In this subsection, we useL1 regularization and online sparsification to derive the second OSKRLSTD algorithm, which is called OSKRLSTD-L1.First, we try to derive theL1-regularized solution of (11). Add an L1-norm penalty into (11); that is,(26)αt=f^αt=arg⁡minβ∈Rnt⁡K^tTβ-R^t+γK^t′Tαt22+2ξβ1,where ξ∈[0,∞) is a regularization parameter. However, β1 is not differentiable. Similar to Painter-Wakefield and Parr in [28], we resort to the subdifferential of g(β)=K^tTβ-(R^t+γ(K^t′)Tαt)22+2ξβ1; that is,(27)∇gβ=2K^tK^tTβ-R^t+γK^t′Tαt+2ξsgn⁡β,where sgn⁡(β) is the set-valued function defined component-wise as(28)sgn⁡βj=+1βj>0-1,+1βj=0-1βj<0.Let ∇g(β)=0, so that(29)K^tK^tTβ∗-γK^t′Tαt=K^tR^t-ξsgn⁡β∗.Since wt=u∗, we also have αt=β∗ from (9). Then, the above equation can be rewritten as(30)K^tK^t-γK^t′Tαt=K^tR^t-ξsgn⁡αt,where sgn⁡(αt) has the same meaning as sgn⁡(β). To avoid the singularity of K^t(K^t-γK^t′)T and further reduce the complexity of the subsequent derivation, we introduce ηαt into both sides; that is,(31)K^tK^t-γK^t′T+ηItαt=K^tR^t+ηαt-ξsgn⁡αt,where η∈[0,∞) is a regularization parameter. Obviously, the left hand side of (31) is the same as that of (14). Thus, from (16), the above equation can be rewritten as(32)Atαt=bt+ηαt-ξsgn⁡αt.Then, we have the following fixed-point equation:(33)αt=μt+At-1ηαt-ξsgn⁡αt,where μt denotes(34)μt=At-1bt.Unfortunately, here, αt cannot be solved analytically.Second, we investigate how to find the fixed point of (33). In L1-regularized LSTD algorithms [5, 29], researchers often used the LASSO method to tackle this problem. However, the LASSO method is inherently a batch method and is unsuitable for online learning. Instead, we resort to the fixed-point subiteration method introduced in [13]. We first use the sign function sign⁡(αt) to replace sgn⁡(αt) in (33). Then, we can construct the following subiteration:(35)αtl+1=μt+At-1ηαtl-ξsign⁡αtl,where l∈N+ denotes the lth subiteration and αt1 is initialized to μt since the fixed point will be close to μt if η and ξ are small. If the subiteration number reaches a preset value N∈N+ or αtv+1-αtv is less than or equal to a preset threshold ε∈R+, the subiteration will stop. From (32) and (28), if |(bt+ηαt-Atαt)j|<ξ, αt,j should be 0. Obviously, the replacement of sgn⁡(αt) makes αt lose the ability to select features. To remedy this situation, after the whole subiteration, we remove the weakly dependent elements from Dt according to the magnitude of αt; that is,(36)Dt=ΨItDt,where ΨIt(·) denotes the operation to remove the elements indexed by the set It, which is determined by(37)It=j∣-v≤αt,j≤v,j=1,…,nt-1,where v∈R+ is a preset threshold. Note that we do not remove the last element dnt of Dt, since |αnt| is probably very small, especially when dnt is just added to Dt. Similarly, we perform ΨIt(αt) and ΨIt(μt) to remove the weakly dependent coefficients. From (16), At-1 also requires removing some rows and columns. Unfortunately, we cannot use the method in [30] to do this like Chen et al. in [13], since At-1 is not a symmetry matrix. Considering that bt will remove the corresponding elements if Dt is pruned, we directly perform ΨIt(At-1) to remove the rows and columns indexed by It. Although this method may bring some bias into At-1, our simulation results show that it is feasible and effective. The whole fixed-point subiteration and online pruning algorithm are summarized in Algorithm 2.Algorithm 2:Fixed-point subiteration and online pruning.
(
1)Input: Dt, μt, At-1, η, ξ, N, ε, v
(2)Initialize: αt1=μt
(3)for  l=1  to  N  do
(4)Update αtl by  (35)
(5)if  αtl+1-αtl≤ε  then
(6)   Break out of the loop
(7)end if
(8)end for
(9)αt=αtl+1
(10) Determine the index set It by  (37)
(11) Perform ΨIt(Dt), ΨIt(αt), ΨIt(μt) and ΨIt(At-1)Remark 4.
Our simulation results show that Algorithm2 will converge in few iterations. Thus, Algorithm 2 does not become the computational bottleneck of the OSKRLSTD-L1 algorithm, and the maximum subiteration number N can be set to a small positive integer.Third, we derive the recursive formulas ofAt-1 and μt. Although the dictionary can be pruned by using Algorithm 2, it still has the risk of rapidly growing if new samples are allowed to be added continually. Thus, the conventional sparsification method is also required to be considered here. Similar to Section 3.1, there are two cases under online sparsification. Since At and μt have the same definitions as At and αt in the OSKRLSTD-L2 algorithm, we can directly use (20) and (24) for updating At-1 and rewrite (21) and (25) for updating μt. If st dissatisfies the sparsification condition, μt will be updated by(38)μt=μt-1+rt-μt-1TΔkt-1st,st′At-1-1kt-1st1+Δkt-1Tst,st′At-1-1kt-1st.Otherwise, μt will be updated by(39)μt=1mtmtμ~t-A~t-1h~tq~t-g~tTμ~tq~t-g~tTμ~t,where h~t, g~t, p~t, and q~t are also calculated by (23). Since Dt, At-1, and μt will be pruned by Algorithm 2 after the update, it is important to note that A~t-1 and μ~t in (39) denote At-1 and μt updated by Dt-1 but unpruned by ΨIt(·). Likewise, when (24) is used here, A~t-1 has the same meaning.Finally, we summarize the whole algorithm in Algorithm3. For episodic tasks, the modification is the same as Remark 2. In addition, similar to Remark 3, the sliding-window size M should also be set to a small integer.Algorithm 3:OSKRLSTD-L1.
(
1)Input: π to be evaluated, k(⋅,⋅), γ, η, ξ, M, N, ε, v
(2)for  t=1,2,…  do
(3) if  t==1  then
(4)   Initialize s1, D1=s1
(5)   Take a1 given by π, and observe s1′, r1
(6)   Initialize H1=(s1,s1′,r1)
(7)   Initialize A1-1=(k(s1,s1)(Δk1(s1,s1′)+η))-1
(8)   Initialize μ1=A1-1k(s1,s1)r1
(9)   Perform Algorithm 2
(10)  else
(11)    Take at given by π, and observe st′, rt
(12)    Update Ht, Dt=Dt-1
(13)    Update μt, At-1 by (38) and (20)
(14)    A^t-1=At-1, μ^t=μt
(15)    Perform Algorithm 2
(16)    if  st satisfies the sparsification condition  then
(17)      Dt=Dt-1∪st, μ~t=μ^t, A~t-1=A^t-1
(18)      Compute h~t, g~t, p~t and q~t by  (23)
(19)      Update μt, At-1 by  (39) and (24)
(20)      Perform Algorithm 2
(21)    end if
(22)  end if
(23)  st+1=st′
(24) end forRemark 5.
By pruning the weakly dependent features, the OSKRLSTD-L1 algorithm can yield a much sparser solution than the OSKRLSTD-L2 algorithm.


## 3.1. OSKRLSTD-L2 Algorithm

Now, we useL2 regularization and online sparsification to derive the first OSKRLSTD algorithm, which is called OSKRLSTD-L2.First, we use the kernel trick to kernelize (6). Suppose the feature dictionary Dt={dj∣dj∈S,j=1,…,nt}, and let Φt=[ϕ(d1),…,ϕ(dnt)]T denote the corresponding feature matrix. By the Representer Theorem [24], wt and u can be expressed as follows:(9)wt=ΦtTαt=∑j=1ntαjϕdj,u=ΦtTβ=∑j=1ntβjϕdj,where αt=[αt,1,…,αt,nt]T and β=[β1,…,βnt]T are the coefficient vector of wt and u, respectively. Then, from (6), we have(10)αt=f^αt=arg⁡minβ∈Rnt⁡Φ^tΦtTβ-R^t+γΦ^t′ΦtTαt22.By the Mercer Theorem [24], the inner product of two feature vectors can be calculated by k(si,sj)=ϕ(si)Tϕ(sj). Thus, we can define Kt=ΦtΦtT, K^t=ΦtΦ^tT, and K^t′=Φt(Φ^t′)T. On this basis, (10) can be rewritten as(11)αt=f^αt=arg⁡minβ∈Rnt⁡K^tTβ-R^t+γK^t′Tαt22.Second, we try to derive theL2-regularized solution of (11). Add an L2-norm penalty into (11); that is,(12)αt=f^αt=arg⁡minβ∈Rnt⁡K^tTβ-R^t+γK^t′Tαt22+ηβ22,where η∈[0,∞) is a regularization parameter. Let ∂(K^tTβ-R^t+γK^t′Tαt22+ηβ22)/∂β=0; we have(13)K^tK^tTβ∗-γK^t′Tαt+ηβ∗=K^tR^t.Since wt=u∗, we easily have αt=β∗ from (9). Then, the above equation can be rewritten as(14)K^tK^t-γK^t′T+ηItαt=K^tR^t,where It is the nt×nt identity matrix. Thus, αt can be analytically solved as(15)αt=K^tK^t-γK^t′T+ηIt-1K^tR^t=At-1bt,where At∈Rnt×nt and bt∈Rnt denote(16)At=K^tK^t-γK^t′T+ηIt=∑i=1tktsiΔktTsi,si′+ηIt,bt=K^tR^t=∑i=1tktsiri,where kt(·)=[k(·,d1),…,k(·,dnt)]T and Δkt(si,si′)=kt(si)-γkt(si′).Third, we derive the recursive formulas ofAt-1 and αt. Under online sparsification, there are two cases: (1) Dt=Dt-1, nt=nt-1, kt(·)=kt-1(·), Δkt(si,si′)=Δkt-1(si,si′), and It=It-1; (2) Dt=Dt-1∪{st}, nt=nt-1+1, kt(·)=[kt-1T(·),k(·,st)]T, Δkt(si,si′)=[Δkt-1T(si,si′),Δkt(si,si′)]T, where Δkt(si,si′)=k(si,st)-γk(si′,st), and It is expanded as(17)It=It-10t-10t-1T1,where 0t-1 is the nt-1 dimensional zero vector.For the first case, (16) can be rewritten as follows:(18)At=At-1+kt-1stΔkt-1Tst,st′,(19)bt=bt-1+kt-1strt.Applying the matrix-inversion lemma [25] for At-1, we get(20)At-1=At-1-1-At-1-1kt-1stΔkt-1Tst,st′At-1-11+Δkt-1Tst,st′At-1-1kt-1st.Thus, plugging (19) and (20) into (15), we obtain(21)αt=αt-1+rt-αt-1TΔkt-1st,st′At-1-1kt-1st1+Δkt-1Tst,st′At-1-1kt-1st.For the second case, (16) can be rewritten as follows:(22)At=A~thtgtTpt,bt=b~tqt,where A~t and b~t are the same as the updated At and bt when the feature dictionary keeps unchanged, ht=∑i=1tΔkt(si,si′)kt-1(si), gt=∑i=1tk(si,st)Δkt-1(si,si′), pt=∑i=1tk(si,st)Δkt(si,si′)+η, and qt=∑i=1tk(si,st)ri. However, computing ht, gt, pt, and qt requires caching all history samples, and the computational cost will become more and more expensive as t increases. Inspired by the work of Van Vaerenbergh et al. [26], we introduce a sliding window Ht to deal with these problems. Let Ht={(sj,sj′,rj)∣j=max⁡1,t-M+1,…,t}, where M is the window size. We only use the samples in Ht to evaluate ht, gt, pt, and qt; that is,(23)h~t=∑j∈HtΔktsj,sj′kt-1sj,g~t=∑j∈Htksj,stΔkt-1sj,sj′,p~t=∑j∈Htksj,stΔktsj,sj′+η,q~t=∑j∈Htksj,strj.Then, similar to those in the first case, At-1 and αt can be derived as follows:(24)At-1=1mtmtA~t-1+A~t-1h~tg~tTA~t-1-A~t-1h~t-g~tTA~t-11,(25)αt=1mtmtα~t-A~t-1h~tq~t-g~tTα~tq~t-g~tTα~t,where mt=p~t-g~tTA~t-1h~t and α~t is the same as the updated αt when the dictionary keeps unchanged.Finally, we summarize the whole algorithm in Algorithm1.Algorithm 1:OSKRLSTD-L2.
(
1)Input: π to be evaluated, k(⋅,⋅), γ, η, M
(2)for  t=1,2,…  do
(3) if  t==1  then
(4)  Initialize s1, D1=s1
(5)  Take a1 given by π, and observe s1′, r1
(6)  Initialize H1=(s1,s1′,r1)
(7)  Initialize A1-1=(k(s1,s1)(Δk1(s1,s1′)+η))-1
(8)  Initialize α1=A1-1k(s1,s1)r1
(9) else
(10)  Take at given by π, and observe st′, rt
(11)   Update Ht, Dt=Dt-1
(12)   Update αt, At-1 by (21) and (20)
(13)   if  st satisfies the sparsification condition then
(14)     Dt=Dt-1∪st, α~t=αt, A~t-1=At-1
(15)     Compute h~t, g~t, p~t and q~t by (23)
(16)     Update αt, At-1 by (25) and (24)
(17)   end if
(18)  end if
(19)  st+1=st′
(20) end forRemark 1.
Here, we do not restrict the OSKRLSTD-L2 algorithm to a specific online sparsification method. That means it can be combined with many popular sparsification methods such as the novelty criterion (NC) [27] and the ALD criterion.Remark 2.
Although the OSKRLSTD-L2 algorithm is designed for infinite horizon tasks, it can be modified for episodic tasks. When st′ is an absorbing state, it only requires setting γ=0 temporarily and setting st+1 as the start state of next episode.Remark 3.
Our simulation results show that a big sliding window cannot help improve the convergence performance of the OSKRLSTD-L2 algorithm. Thus, to save memory and reduce the computational cost, M should be set to a small integer.


## 3.2. OSKRLSTD-L1 Algorithm

In this subsection, we useL1 regularization and online sparsification to derive the second OSKRLSTD algorithm, which is called OSKRLSTD-L1.First, we try to derive theL1-regularized solution of (11). Add an L1-norm penalty into (11); that is,(26)αt=f^αt=arg⁡minβ∈Rnt⁡K^tTβ-R^t+γK^t′Tαt22+2ξβ1,where ξ∈[0,∞) is a regularization parameter. However, β1 is not differentiable. Similar to Painter-Wakefield and Parr in [28], we resort to the subdifferential of g(β)=K^tTβ-(R^t+γ(K^t′)Tαt)22+2ξβ1; that is,(27)∇gβ=2K^tK^tTβ-R^t+γK^t′Tαt+2ξsgn⁡β,where sgn⁡(β) is the set-valued function defined component-wise as(28)sgn⁡βj=+1βj>0-1,+1βj=0-1βj<0.Let ∇g(β)=0, so that(29)K^tK^tTβ∗-γK^t′Tαt=K^tR^t-ξsgn⁡β∗.Since wt=u∗, we also have αt=β∗ from (9). Then, the above equation can be rewritten as(30)K^tK^t-γK^t′Tαt=K^tR^t-ξsgn⁡αt,where sgn⁡(αt) has the same meaning as sgn⁡(β). To avoid the singularity of K^t(K^t-γK^t′)T and further reduce the complexity of the subsequent derivation, we introduce ηαt into both sides; that is,(31)K^tK^t-γK^t′T+ηItαt=K^tR^t+ηαt-ξsgn⁡αt,where η∈[0,∞) is a regularization parameter. Obviously, the left hand side of (31) is the same as that of (14). Thus, from (16), the above equation can be rewritten as(32)Atαt=bt+ηαt-ξsgn⁡αt.Then, we have the following fixed-point equation:(33)αt=μt+At-1ηαt-ξsgn⁡αt,where μt denotes(34)μt=At-1bt.Unfortunately, here, αt cannot be solved analytically.Second, we investigate how to find the fixed point of (33). In L1-regularized LSTD algorithms [5, 29], researchers often used the LASSO method to tackle this problem. However, the LASSO method is inherently a batch method and is unsuitable for online learning. Instead, we resort to the fixed-point subiteration method introduced in [13]. We first use the sign function sign⁡(αt) to replace sgn⁡(αt) in (33). Then, we can construct the following subiteration:(35)αtl+1=μt+At-1ηαtl-ξsign⁡αtl,where l∈N+ denotes the lth subiteration and αt1 is initialized to μt since the fixed point will be close to μt if η and ξ are small. If the subiteration number reaches a preset value N∈N+ or αtv+1-αtv is less than or equal to a preset threshold ε∈R+, the subiteration will stop. From (32) and (28), if |(bt+ηαt-Atαt)j|<ξ, αt,j should be 0. Obviously, the replacement of sgn⁡(αt) makes αt lose the ability to select features. To remedy this situation, after the whole subiteration, we remove the weakly dependent elements from Dt according to the magnitude of αt; that is,(36)Dt=ΨItDt,where ΨIt(·) denotes the operation to remove the elements indexed by the set It, which is determined by(37)It=j∣-v≤αt,j≤v,j=1,…,nt-1,where v∈R+ is a preset threshold. Note that we do not remove the last element dnt of Dt, since |αnt| is probably very small, especially when dnt is just added to Dt. Similarly, we perform ΨIt(αt) and ΨIt(μt) to remove the weakly dependent coefficients. From (16), At-1 also requires removing some rows and columns. Unfortunately, we cannot use the method in [30] to do this like Chen et al. in [13], since At-1 is not a symmetry matrix. Considering that bt will remove the corresponding elements if Dt is pruned, we directly perform ΨIt(At-1) to remove the rows and columns indexed by It. Although this method may bring some bias into At-1, our simulation results show that it is feasible and effective. The whole fixed-point subiteration and online pruning algorithm are summarized in Algorithm 2.Algorithm 2:Fixed-point subiteration and online pruning.
(
1)Input: Dt, μt, At-1, η, ξ, N, ε, v
(2)Initialize: αt1=μt
(3)for  l=1  to  N  do
(4)Update αtl by  (35)
(5)if  αtl+1-αtl≤ε  then
(6)   Break out of the loop
(7)end if
(8)end for
(9)αt=αtl+1
(10) Determine the index set It by  (37)
(11) Perform ΨIt(Dt), ΨIt(αt), ΨIt(μt) and ΨIt(At-1)Remark 4.
Our simulation results show that Algorithm2 will converge in few iterations. Thus, Algorithm 2 does not become the computational bottleneck of the OSKRLSTD-L1 algorithm, and the maximum subiteration number N can be set to a small positive integer.Third, we derive the recursive formulas ofAt-1 and μt. Although the dictionary can be pruned by using Algorithm 2, it still has the risk of rapidly growing if new samples are allowed to be added continually. Thus, the conventional sparsification method is also required to be considered here. Similar to Section 3.1, there are two cases under online sparsification. Since At and μt have the same definitions as At and αt in the OSKRLSTD-L2 algorithm, we can directly use (20) and (24) for updating At-1 and rewrite (21) and (25) for updating μt. If st dissatisfies the sparsification condition, μt will be updated by(38)μt=μt-1+rt-μt-1TΔkt-1st,st′At-1-1kt-1st1+Δkt-1Tst,st′At-1-1kt-1st.Otherwise, μt will be updated by(39)μt=1mtmtμ~t-A~t-1h~tq~t-g~tTμ~tq~t-g~tTμ~t,where h~t, g~t, p~t, and q~t are also calculated by (23). Since Dt, At-1, and μt will be pruned by Algorithm 2 after the update, it is important to note that A~t-1 and μ~t in (39) denote At-1 and μt updated by Dt-1 but unpruned by ΨIt(·). Likewise, when (24) is used here, A~t-1 has the same meaning.Finally, we summarize the whole algorithm in Algorithm3. For episodic tasks, the modification is the same as Remark 2. In addition, similar to Remark 3, the sliding-window size M should also be set to a small integer.Algorithm 3:OSKRLSTD-L1.
(
1)Input: π to be evaluated, k(⋅,⋅), γ, η, ξ, M, N, ε, v
(2)for  t=1,2,…  do
(3) if  t==1  then
(4)   Initialize s1, D1=s1
(5)   Take a1 given by π, and observe s1′, r1
(6)   Initialize H1=(s1,s1′,r1)
(7)   Initialize A1-1=(k(s1,s1)(Δk1(s1,s1′)+η))-1
(8)   Initialize μ1=A1-1k(s1,s1)r1
(9)   Perform Algorithm 2
(10)  else
(11)    Take at given by π, and observe st′, rt
(12)    Update Ht, Dt=Dt-1
(13)    Update μt, At-1 by (38) and (20)
(14)    A^t-1=At-1, μ^t=μt
(15)    Perform Algorithm 2
(16)    if  st satisfies the sparsification condition  then
(17)      Dt=Dt-1∪st, μ~t=μ^t, A~t-1=A^t-1
(18)      Compute h~t, g~t, p~t and q~t by  (23)
(19)      Update μt, At-1 by  (39) and (24)
(20)      Perform Algorithm 2
(21)    end if
(22)  end if
(23)  st+1=st′
(24) end forRemark 5.
By pruning the weakly dependent features, the OSKRLSTD-L1 algorithm can yield a much sparser solution than the OSKRLSTD-L2 algorithm.


## 4. Simulations

In this section, we use a nonnoise chain and a noise chain [2, 20, 31] to demonstrate the effectiveness of our proposed algorithms. For comparison purposes, RLSTD [1] and SKRLSTD [21] algorithms are also tested in the simulations. To analyze the effect of regularization and online pruning on the performance of our algorithms, the OSKRLSTD-L2 algorithm with η=0 and the OSKRLSTD-L1 algorithm with v=0 (called OSKRLSTD-0 and OSKRLSTD-L1u, resp.) are tested here, too. In addition, the effects of the sliding-window size on the performance of our algorithms and OSKRLSTD-L1u are evaluated as well.


### 4.1. Simulation Settings

As shown in Figure1, in both chain problems, each chain consists of 50 states, which are numbered from 1 to 50. For each state, there are two actions available, that is, “left” (L) and “right” (R). Each action succeeds with probability 0.9, changing the state in the intended direction, and fails with probability 0.1, changing the state in the opposite direction. The two boundaries of each chain are dead-ends, and the discount factor γ of each chain is set to 0.9. For the nonnoise chain, the reward is 1 only in states 10 and 41, whereas, for the noise chain, the reward is corrupted by an additive Gaussian noise 0.3N(0,1). Due to the symmetry, the optimal policy for both chains is to go right in states 1–9 and 26–41 and left in states 10–25 and 42–50. Here, we use it as the policy π to be evaluated. Note that the state transition probabilities are available only for solving the true state-value functions Vπ, and they are assumed to be unknown for all algorithms compared here.Figure 1
The 50-state chain problem.In the implementations of all tested algorithms for both chain problems, the settings are summarized as follows: (i) For all OSKRLSTD algorithms, the Mercer kernel is defined askx,y=exp⁡(-x-y2/16), the sparsification condition is defined as mindj∈Dt-1st-dj>2, and the sliding-window size M is set to 5. Besides, for the OSKRLSTD-L1 algorithm, the regularization parameters η and ξ are set to 0.8 and 0.3, the maximum subiteration number N is set to 10, the precision threshold ε is set to 0.1, and the pruning threshold v is set to 0.4; for the OSKRLSTD-L1u algorithm, η, ξ, and N are the same as those in the OSKRLSTD-L1 algorithm; for the OSKRLSTD-L2 algorithm, ξ is set to 1. (ii) For the SKRLSTD algorithm, the Mercer kernel and the sparsification condition are the same as those in each OSKRLSTD algorithm. (iii) For the RLSTD algorithm, the feature vector ϕ(s) consists of 19 Gaussian radius basis functions (GRBFs) plus a constant term 1, resulting in a total of 20 basis functions. The GRBF has the same definition as the Mercer kernel used in each OSKRLSTD algorithm, and the centers of GRBFs are uniformly distributed over [1,50]. In addition, the variance matrix C0 of RLSTD is initialized to 0.4I, where I is the 20 × 20 identity matrix. (iv) In the simulations, each algorithm performs 50 runs, each run includes 100 episodes, and each episode is truncated after 100 time steps. In particular, the SKRLSTD algorithm requires an extra run for offline sparsification before each regular run.


### 4.2. Simulation Results

We first report the comparison results of all tested algorithms with the simulation settings described in Section4.1. Their learning curves are shown in Figure 2. At each episode, the root mean square error (RMSE) of each algorithm is calculated by RMSE=(1/50)∑j=150((1/50)∑s=150(V^jπ(s)-Vπ(s))2)0.5, where Vπ(s) is solved by (1) and V^jπ(s) is the approximate value of the jth run. From Figure 2, we can observe that (i) OSKRLSTD-L2 and OSKRLSTD-L1 can obtain the similar performance as RLSTD and converge much faster than SKRLSTD. (ii) Without regularization, the performance of OSKRLSTD-0 becomes very poor, especially in the noise chain. In contrast, OSKRLSTD-L2 and OSKRLSTD-L1 still perform well. (iii) The performance of OSKRLSTD-L1u is only slightly better than that of OSKRLSTD-L1, which indicates that online pruning has little effect on the performance. Figure 3 illustrates V^π(s) approximated by all tested algorithms at the final episode. Clearly, OSKRLSTD-0 has lost the ability to approximate Vπ(s) of the noise chain. Figure 4 shows the dictionary growth curves of all tested algorithms. Compared with RLSTD and SKRLSTD, all OSKRLSTD algorithms can construct the dictionary automatically, and OSKRLSTD-L1 yields a much sparser dictionary. Figure 5 shows the average subiterations per time step in OSKRLSTD-L1 and OSKRLSTD-L1u. As episodes increase, the subiterations decline gradually. In addition, online pruning can reduce the subiterations significantly. Even in the noise chain, the subiterations are small. Finally, the main simulation results of all tested algorithms at the final episode are summarized in Table 1.Table 1
Main simulation results on both chains at the final episode.
Algorithm
Nonnoise chain
Noise chain
RMSE
Dictionary size
Subiterations
RMSE
Dictionary size
Subiterations
RLSTD
0.47 ± 0.03
20
—
0.50 ± 0.04
20
—
SKRLSTD
0.47 ± 0.05
15.36 ± 0.78
—
0.49 ± 0.06
15.32 ± 0.71
—
OKRLSTD-L2
0.45 ± 0.05
15.30 ± 0.81
—
0.47 ± 0.04
15.32 ± 0.84
—
OKRLSTD-L1
0.49 ± 0.08
11.52 ± 1.16
1.81 ± 1.82
0.53 ± 0.10
12.42 ± 1.13
2.60 ± 2.56
OKRLSTD-0
2.21 ± 0.05
15.25 ± 0.87
—
32.92 ± 68.67
15.24 ± 0.77
—
OKRLSTD-L1u
0.44 ± 0.05
15.40 ± 0.76
5.08 ± 3.24
0.47 ± 0.05
15.28 ± 0.88
4.90 ± 3.26Figure 2
Learning curves of all tested algorithms.
(a)
In the nonnoise chain
(b)
In the noise chainFigure 3
V
^
π
(
s
) approximated by all tested algorithms at the final episode.
(a)
In the nonnoise chain
(b)
In the noise chainFigure 4
Dictionary growth curves of all tested algorithms.
(a)
In the nonnoise chain
(b)
In the noise chainFigure 5
Average subiterations in OSKRLSTD-L1 and OSKRLSTD-L1u algorithms.
(a)
In the nonnoise chain
(b)
In the noise chainNext, we evaluate the effect of the sliding-window size on our proposed algorithms and OSKRLSTD-L1u with M=1,5,10,…,45,50. The logarithmic RMSEs of each algorithm at the final episode are illustrated in Figure 6. Note that the parameter settings of these algorithms are the same as those described in Section 4.1 except for M. From Figure 6, OSKRLSTD-L1 and OSKRLSTD-L1u obviously become worse rather than better as the window size increases, and OSKRLSTD-L2 has a strong adaptability to different window sizes. The reason for this result is analyzed as follows: From the derivation of our algorithms, the influence of the window size is mainly manifest in At-1. Since here At-1 is calculated by recursive update instead of matrix inversion and samples are used one by one, using too many history samples together may increase the calculation error. In OSKRLSTD-L2, a moderate regularization parameter η can relieve the influence of this error. In contrast, in OSKRLSTD-L1 and OSKRLSTD-L1u, the subiteration may expand the influence. Especially for OSKRLSTD-L1, online pruning can introduce the new error, which further worsens the convergence performance. To verify the above analysis, we reset η=0.6, ξ=0.3, and N=1 for OSKRLSTD-L1 and OSKRLSTD-L1u and reevaluate the effect of the window size. The new results are illustrated in Figure 7. As expected, OSKRLSTD-L1 and OSKRLSTD-L1u can also adapt to M. Nevertheless, there is still no proof that a big window size can help improve the convergence performance of OSKRLSTD-L2 and OSKRLSTD-L1. Thus, as stated in Remark 3, M is suggested to be set to a small integer in practice.Figure 6
Effect of the sliding-window sizeM on three OSKRLSTD algorithms.
(a)
In the nonnoise chain
(b)
In the noise chainFigure 7
Effect of the sliding-window sizeM on three OSKRLSTD algorithms with new parameters.
(a)
In the nonnoise chain
(b)
In the noise chain


## 4.1. Simulation Settings

As shown in Figure1, in both chain problems, each chain consists of 50 states, which are numbered from 1 to 50. For each state, there are two actions available, that is, “left” (L) and “right” (R). Each action succeeds with probability 0.9, changing the state in the intended direction, and fails with probability 0.1, changing the state in the opposite direction. The two boundaries of each chain are dead-ends, and the discount factor γ of each chain is set to 0.9. For the nonnoise chain, the reward is 1 only in states 10 and 41, whereas, for the noise chain, the reward is corrupted by an additive Gaussian noise 0.3N(0,1). Due to the symmetry, the optimal policy for both chains is to go right in states 1–9 and 26–41 and left in states 10–25 and 42–50. Here, we use it as the policy π to be evaluated. Note that the state transition probabilities are available only for solving the true state-value functions Vπ, and they are assumed to be unknown for all algorithms compared here.Figure 1
The 50-state chain problem.In the implementations of all tested algorithms for both chain problems, the settings are summarized as follows: (i) For all OSKRLSTD algorithms, the Mercer kernel is defined askx,y=exp⁡(-x-y2/16), the sparsification condition is defined as mindj∈Dt-1st-dj>2, and the sliding-window size M is set to 5. Besides, for the OSKRLSTD-L1 algorithm, the regularization parameters η and ξ are set to 0.8 and 0.3, the maximum subiteration number N is set to 10, the precision threshold ε is set to 0.1, and the pruning threshold v is set to 0.4; for the OSKRLSTD-L1u algorithm, η, ξ, and N are the same as those in the OSKRLSTD-L1 algorithm; for the OSKRLSTD-L2 algorithm, ξ is set to 1. (ii) For the SKRLSTD algorithm, the Mercer kernel and the sparsification condition are the same as those in each OSKRLSTD algorithm. (iii) For the RLSTD algorithm, the feature vector ϕ(s) consists of 19 Gaussian radius basis functions (GRBFs) plus a constant term 1, resulting in a total of 20 basis functions. The GRBF has the same definition as the Mercer kernel used in each OSKRLSTD algorithm, and the centers of GRBFs are uniformly distributed over [1,50]. In addition, the variance matrix C0 of RLSTD is initialized to 0.4I, where I is the 20 × 20 identity matrix. (iv) In the simulations, each algorithm performs 50 runs, each run includes 100 episodes, and each episode is truncated after 100 time steps. In particular, the SKRLSTD algorithm requires an extra run for offline sparsification before each regular run.


## 4.2. Simulation Results

We first report the comparison results of all tested algorithms with the simulation settings described in Section4.1. Their learning curves are shown in Figure 2. At each episode, the root mean square error (RMSE) of each algorithm is calculated by RMSE=(1/50)∑j=150((1/50)∑s=150(V^jπ(s)-Vπ(s))2)0.5, where Vπ(s) is solved by (1) and V^jπ(s) is the approximate value of the jth run. From Figure 2, we can observe that (i) OSKRLSTD-L2 and OSKRLSTD-L1 can obtain the similar performance as RLSTD and converge much faster than SKRLSTD. (ii) Without regularization, the performance of OSKRLSTD-0 becomes very poor, especially in the noise chain. In contrast, OSKRLSTD-L2 and OSKRLSTD-L1 still perform well. (iii) The performance of OSKRLSTD-L1u is only slightly better than that of OSKRLSTD-L1, which indicates that online pruning has little effect on the performance. Figure 3 illustrates V^π(s) approximated by all tested algorithms at the final episode. Clearly, OSKRLSTD-0 has lost the ability to approximate Vπ(s) of the noise chain. Figure 4 shows the dictionary growth curves of all tested algorithms. Compared with RLSTD and SKRLSTD, all OSKRLSTD algorithms can construct the dictionary automatically, and OSKRLSTD-L1 yields a much sparser dictionary. Figure 5 shows the average subiterations per time step in OSKRLSTD-L1 and OSKRLSTD-L1u. As episodes increase, the subiterations decline gradually. In addition, online pruning can reduce the subiterations significantly. Even in the noise chain, the subiterations are small. Finally, the main simulation results of all tested algorithms at the final episode are summarized in Table 1.Table 1
Main simulation results on both chains at the final episode.
Algorithm
Nonnoise chain
Noise chain
RMSE
Dictionary size
Subiterations
RMSE
Dictionary size
Subiterations
RLSTD
0.47 ± 0.03
20
—
0.50 ± 0.04
20
—
SKRLSTD
0.47 ± 0.05
15.36 ± 0.78
—
0.49 ± 0.06
15.32 ± 0.71
—
OKRLSTD-L2
0.45 ± 0.05
15.30 ± 0.81
—
0.47 ± 0.04
15.32 ± 0.84
—
OKRLSTD-L1
0.49 ± 0.08
11.52 ± 1.16
1.81 ± 1.82
0.53 ± 0.10
12.42 ± 1.13
2.60 ± 2.56
OKRLSTD-0
2.21 ± 0.05
15.25 ± 0.87
—
32.92 ± 68.67
15.24 ± 0.77
—
OKRLSTD-L1u
0.44 ± 0.05
15.40 ± 0.76
5.08 ± 3.24
0.47 ± 0.05
15.28 ± 0.88
4.90 ± 3.26Figure 2
Learning curves of all tested algorithms.
(a)
In the nonnoise chain
(b)
In the noise chainFigure 3
V
^
π
(
s
) approximated by all tested algorithms at the final episode.
(a)
In the nonnoise chain
(b)
In the noise chainFigure 4
Dictionary growth curves of all tested algorithms.
(a)
In the nonnoise chain
(b)
In the noise chainFigure 5
Average subiterations in OSKRLSTD-L1 and OSKRLSTD-L1u algorithms.
(a)
In the nonnoise chain
(b)
In the noise chainNext, we evaluate the effect of the sliding-window size on our proposed algorithms and OSKRLSTD-L1u with M=1,5,10,…,45,50. The logarithmic RMSEs of each algorithm at the final episode are illustrated in Figure 6. Note that the parameter settings of these algorithms are the same as those described in Section 4.1 except for M. From Figure 6, OSKRLSTD-L1 and OSKRLSTD-L1u obviously become worse rather than better as the window size increases, and OSKRLSTD-L2 has a strong adaptability to different window sizes. The reason for this result is analyzed as follows: From the derivation of our algorithms, the influence of the window size is mainly manifest in At-1. Since here At-1 is calculated by recursive update instead of matrix inversion and samples are used one by one, using too many history samples together may increase the calculation error. In OSKRLSTD-L2, a moderate regularization parameter η can relieve the influence of this error. In contrast, in OSKRLSTD-L1 and OSKRLSTD-L1u, the subiteration may expand the influence. Especially for OSKRLSTD-L1, online pruning can introduce the new error, which further worsens the convergence performance. To verify the above analysis, we reset η=0.6, ξ=0.3, and N=1 for OSKRLSTD-L1 and OSKRLSTD-L1u and reevaluate the effect of the window size. The new results are illustrated in Figure 7. As expected, OSKRLSTD-L1 and OSKRLSTD-L1u can also adapt to M. Nevertheless, there is still no proof that a big window size can help improve the convergence performance of OSKRLSTD-L2 and OSKRLSTD-L1. Thus, as stated in Remark 3, M is suggested to be set to a small integer in practice.Figure 6
Effect of the sliding-window sizeM on three OSKRLSTD algorithms.
(a)
In the nonnoise chain
(b)
In the noise chainFigure 7
Effect of the sliding-window sizeM on three OSKRLSTD algorithms with new parameters.
(a)
In the nonnoise chain
(b)
In the noise chain


## 5. Conclusion

As an important approach for policy evaluation, LSTD algorithms can use samples more efficiently and eliminate all step-size parameters. But they require users to design the feature vector manually and often require many features to approximate state-value functions. Recently, there are some works on these issues by combining with sparse kernel methods. However, these works do not consider regularization and their sparsification processes are batch or offline. In this paper, we propose two online sparse kernel recursive least-squares TD algorithms withL2 and L1 regularization, that is, OSKRLSTD-L2 and OSKRLSTD-L1. By using Bellman operator along with projection operator, our derivation is more simple. By combining online sparsification, L2 and L1 regularization, recursive least squares, a sliding window, and the fixed-point subiteration, our algorithms not only can construct the feature dictionary online but also can avoid overfitting and eliminate the influence of noise. These advantages make them more suitable for online RL problems with a large or continuous state space. In particular, compared with the OSKRLSTD-L2 algorithm, the OSKRLSTD-L1 algorithm can yield a much sparser dictionary. Finally, we illustrate the performance of our algorithms and compare them with RLSTD and SKRLSTD algorithms by several simulations.There are also some interesting topics to be studied in future work: (i) How to select proper regularization parameter should be investigated. (ii) A more thorough simulation analysis is needed, including an extension of our algorithms to learning control problems. (iii) Eligibility traces would be combined for further improving the performance of our algorithms. (iv) The convergence and prediction error bounds of our algorithms will be analyzed theoretically.



---

*Source: 2305854-2016-06-29.xml*