{'fraction_non_alphanumeric': 0.04113703031149602, 'fraction_numerical': 0.007892163710015365, 'mean_word_length': 4.471532288880398, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Recursive Least Squares Policy Control with Echo State Network

The echo state network (ESN) is a special type of recurrent neural networks for processing the time-series dataset. However, limited by the strong correlation among sequential samples of the agent, ESN-based policy control algorithms are difficult to use the recursive least squares (RLS) algorithm to update the ESN's parameters. To solve this problem, we propose two novel policy control algorithms, ESNRLS-Q and ESNRLS-Sarsa. Firstly, to reduce the correlation of training samples, we use the leaky integrator ESN and the mini-batch learning mode. Secondly, to make RLS suitable for training ESN in mini-batch mode, we present a new mean-approximation method for updating the RLS correlation matrix. Thirdly, to prevent ESN from over-fitting, we use the L1 regularization technique. Lastly, to prevent the target state-action value from overestimation, we employ the Mellowmax method. Simulation results show that our algorithms have good convergence performance.


I. INTRODUCTION
Reinforcement learning (RL) is an important type of machine learning methods. By interacting with the unknown environment, the agent tries to learn the optimal control polices at different states for maximizing the cumulative expected return [1]. In the last three decades, to deal with the sequential decision problems with large discrete or continuous state space, RL algorithms mainly use the linear approximation technique to calculate the state-action values. Whereas, this technique has limited approximation ability and requires users to extract features manually. In recent years, it is gradually replaced by with the popularity of deep neural networks (DNNs) in RL, and the deep RL (DRL) [2,3] has become the research hotspot of RL. However, although DNNs are powerful, most of them are difficult to be trained. The echo state network (ESN) [4,5] is a special type of recurrent neural networks (RNNs). It has many merits of RNNs such as the good approximation ability and the automatic feature extracting ability. What is more, it can be trained efficiently by the least squares (LS) or the recursive least squares (RLS), since it only needs to train the parameters from the input layer to the output layer and from the reservoir layer to the output layer. Therefore, we will focus on how to use ESN to design the policy control algorithms in this paper.
In the past two decades, many researchers have done some work on policy control algorithms by using ESN to approximate the state-action values of the agent. Szita et al. [6] propose an ESN-Sarsa algorithm for the partially observable Markov decision process (POMDP) task, and prove the convergence of our algorithm. Chatzidimitriou and Mitkas [7] present an augmented topological neural evolution methods to train ESN, and take it as the approximator of the state-action values. Engedy and Horváth [8] use ESN and the incremental Gaussian mixture network to propose a new RL system model, which can solve the optimal control problem in the partially observable continuous state or action space. Whitley et al. [9] propose an improved ESN trained by a novel neuron selection method, and use it to solve RL tasks. Shi et al. [10] present an ESN-Q learning algorithm to solve the battery control problem. Chang and Futagami [11] propose a new algorithm by using the convolutional ESN to extract the features and using the evolutionary method to select the action of the agent, which has good performance demonstrated by some RL tasks. However, the training efficiency and learning performance of these algorithms need to be further improved, since their ESNs don't use the mini-batch training mode and don't use the LS or RLS training method.
In RL, the least squares policy iteration (LSPI) algorithm is probably the most efficient algorithm, which is first proposed by Lagoudakis et al. [12,13]. By making full use of the historical samples, it employs the LS method to solve the weight parameters directly. On this basis, Xu et al. [14] present a novel kernel-based LSPI algorithm by using the kernel sparsification technique. Zhou et al. [15] propose a batch LSPI algorithm, and prove its convergence theoretically. This algorithm stores the samples generated by agent online, and uses them in batches to update the weight parameters. Compared with the traditional policy control algorithms such as Q-learning and Sarsa, the above LSPI algorithms have faster convergence speed and better learning performance. Whereas, they requires to compute the inverse of the autocorrelation matrix at each iteration. In addition, they use the offline or semi-offline learning mode, which makes them unsuitable for the online RL control tasks. Buşoniu et al. [16] propose a socalled "online" LSPI algorithm, but it is still a semi-offline learning algorithm in essence. Until now, we have not found a true online policy control algorithm based on LS or RLS.
In response to the above problems, we propose two ESNbased RLS policy control algorithms, namely, ESNRLS-Q and ESNRLS-Sarsa. Our main contributions are as follows: 1) We employ the mini-batch learning mode and the leaky integrator ESN (LiESN) [17], which reduce the correlation of the training samples and make RLS able to be used in the ESN-based policy control algorithms. 2) We present a new meanapproximation method to update the RLS autocorrelation matrix, which can reduce the computational complexity and make the RLS algorithm suitable for training ESN in the minibatch mode. 3) We present an L 1 regularization method to prevent ESN from over-fitting. 4) We employ the Mellowmax method [18] to prevent the target state-action values from overestimation. 5) We demonstrate the effectiveness of our algorithms by using both MDP and POMDP tasks.

A. Deep Policy Control Algorithms
RL is mainly used to solve sequential decision-making problems, which are usually formulated as MDPs [1]. An MDP is a five-tuple < , , , , >, where and denote the state space and the action space, ( | , ) ∈ [0,1] and ( | , ) ∈ denote the state-transition probability and the immediate reward from the state to the subsequent state by taking the action , and γ ∈ (0,1] is the discount factor. The goal of RL is to learn the optimal policy π * for maximizing the cumulative expected return (π), that is, π * = argmax (π). Whereas, (π) is hardly calculated directly, since ( | , ) and ( | , ) are unknown in RL. For a given state , is determined by the control policy π, and and can only be obtained by the agent's interaction with the environment. In practical applications, the policy control algorithms generally use the state-action value ( , ) to measure the performance of π when initial state and action are and . In this paper, we assume that is continuous and is discrete. For this kind of MDP problems, ( , ) is often approximated by DNNs in recent years, and a lot of novel policy control algorithms such as DQN [2] and the deep Sarsa [19] are proposed.
The DQN algorithm can be reviewed as follows. First, at the current time step , the agent uses the -greedy policy to select a random action with probability or otherwise set = argmax ∈ ( , ), where ( , ) is approximated by the policy network as where and are the input and the parameter of the policy network. Then, after taking action , the agent moves to the state , gets reward , and stores( , , , )in the experience replay buffer . Next, using the mini batch = { , , , , , , ̂ , } ,⋯, sampled from ，the loss of the policy network can be calculated as , and , is the target value, which is approximated by the target network as , and is the parameter of the target neural network, which is copied from the policy network every some time steps or episodes. Note that , , ; = 0 if , is an absorbing state. Last, can be updated by some optimization algorithms such as SGD and Adam. If using SGD, the update rule is The deep Sarsa algorithm is similar to the DQN algorithm. Distinct from DQN, deep Sarsa is an on-policy algorithm, and its , is approximated as where is the action of the agent at . Note that , , ; = 0 if , is an absorbing state. where (⋅) is the activation function, is the parameter matrix from the input layer to this layer, is the parameter matrix inside this layer, is the bias, and ∈ (0,1] is the leaky rate. The output ( ) of the output layer in a LiESN is calculated as

B. Leaky Integrator ESN
where is the parameter matrix from the input layer and the reservoir layer to this layer, and is the bias. Different from general RNNs, and are determined by the random initialization, is often determined by the spectral radius method [4], and only and are required to be trained. In order to facilitate subsequent discussion and simplify the expression, we define = ( ) T ,

A. Algorithm Derivation
In this subsection, we will introduce the derivation of ESNRLS-Q and ESNRLS-Sarsa. Since the latter is similar to the former, we will mainly introduce the former, and then introduce the latter briefly.
Similar to DQN, ESNRLS-Q also uses the experience replay, the mini-batch learning mode and the -greedy policy. Different from DQN, ESNRLS-Q uses two LiESNs as the policy network and the target network, and uses RLS to update the policy network. In addition, each sample in the experience replay buffer of ESNRLS-Q is a series, which is made up of successive state-action transitions. If the number of the successive transitions is less than when the agent arrives in the absorbing state, ESNRLS-Q will use the last state-action transition to fill the sample.  , and ∈ is a full-one vector. Then，by using (7) and (8) is an absorbing state.
Secondly, we introduce the backward learning of ENRLS-Q, that is, how to use RLS to update . For simplifying expression, we define π However, we cannot obtain by the Sherman-Morrison formula [20] directly, since the last term in the right hand side of (18) is a sum of matrix product.
Next, we propose a mean-approximation method to solve this problem. Considering that all states in a series are similar and the last terms in the right hand side of (18) and (19) are the mean of the product sum, we rewrite (18)  .
ESNRLS-Sarsa is similar to ESNRLS-Q. The main difference is that ESNRLS-Sarsa is an on-policy algorithm. Similar to the deep Sarsa, π ( ) , ( ) in ESNRLS-Sarsa is calculated as is an absorbing state.

B. Over-fitting Prevention
It is well known that DNNs have the risk of over-fitting, since DNNs usually have too many parameters. The RLS algorithm is prone to over-fitting, too. Here we present an regularization method to prevent our algorithms from overfitting. Based on Ekşioğlu's work [21], we add an regularization term into (27), that is where is the regularization factor, and (⋅) is the sign function.

C. Overestimation prevention
In RL, policy control algorithms are prone to overestimation since they are based on boosting learning. DQN and the deep Sarsa use the target network to overcome this problem. Although our algorithms also use the target network, they still have the risk of overestimation, since part parameters of LiSEN are fixed. Here we employ the Mellowmax method, proposed by Kim et al. [18], to improve our algorithms. Define the Mellowmax function as where is the temperature coefficient, and is the action in . On this basis, (11) and (29) can be rewritten as follows ; ) 

A. Simulation Problems and Settings
In this simulation, in order to demonstrate the effectiveness of our algorithms, we will select DQN and the deep Sarsa for comparison. They use feed-forward neural networks (FNNs) with the Adam optimization, called as FNNAdam-Q and FNNAdam-Sarsa, respectively. Considering that LiESN and RLS can preserve more information, we will validate four algorithms on MDP and POMDP tasks. The MDP task is the CartPole-v0 problem in OpenAI Gym, and the POMDP task is a modified CartPole-v0 problem without the speed information of each state. To distinguish them, we call them as MDP-CartPole and POMDP-CartPole, respectively.    The other settings of four algorithms are as follows: 1) The capacity of is 100000, and the mini-batch size is 64. 2) At the beginning of each experiment, the agent runs 1000 episodes to collect enough samples with the completely random policy. 3) After collecting samples, the agent runs 100 episodes with the -greedy policy. 4) and are 0.01 and 0.99, respectively. 5) In each episode, the agent runs 200 time steps at most. If the running steps is less than 200, the reward of the last step is -10. 6) The target networks are updated at the end of each episode. 7) All experiments repeat 5 times. Fig. 1 and Fig. 2 show the averaged running steps of the agent with four algorithms on two tasks. It can be seen from both figures: 1) The convergence performances of our two algorithms are obviously superior to those of FNNAdam-Q and FNNAdam-Sarsa. 2) There is almost no difference between the convergence performances of our two algorithms on the same task. Whereas, there is obvious difference between the convergence performances of FNNAdam-Sarsa and FNNAdam -Q. 3) The convergence performances of our two algorithms on the POMDP-CartPole task are slightly inferior to on the MDP-CartPole task, but they are still better than those of FNNAdam -Q and FNNAdam-Sarsa on the MDP-CartPole task. That means our two algorithms are also robust for POMDP tasks.

V. CONCLUSION
Limited by the strong correlation among sequential samples of the agent, traditional ESN-based policy control algorithms use the single-series learning mode and semi-gradient descent optimization. As a result, their training efficiency and learning performances need to be improved. In this paper, we propose two novel algorithms, that is, ESNRLS-Q and ESNRLS-Sarsa. In our algorithms, we use the popular mini-batch learning mode and the LiESN model to reduce the correlation of training samples. On this basis, we present a new meanapproximation RLS method for updating LiESN to improve the training efficiency. Besides, we employ the regularization and the Mellowmax method to prevent our algorithms from over-fitting and overestimation. The simulation results of MDP-CartPole and POMDP-CartPole tasks show that our algorithms have better convergence performance than FNNAdam-Q and FNNAdam-Sarsa.