# Minibatch Recursive Least Squares Q-Learning

Authors: Chunyuan Zhang; Qi Song; Zeng Meng
Journal: Computational Intelligence and Neuroscience
 (2021)

---

## Abstract

The deep Q-network (DQN) is one of the most successful reinforcement learning algorithms, but it has some drawbacks such as slow convergence and instability. In contrast, the traditional reinforcement learning algorithms with linear function approximation usually have faster convergence and better stability, although they easily suffer from the curse of dimensionality. In recent years, many improvements to DQN have been made, but they seldom make use of the advantage of traditional algorithms to improve DQN. In this paper, we propose a novel Q-learning algorithm with linear function approximation, called the minibatch recursive least squares Q-learning (MRLS-Q). Different from the traditional Q-learning algorithm with linear function approximation, the learning mechanism and model structure of MRLS-Q are more similar to those of DQNs with only one input layer and one linear output layer. It uses the experience replay and the minibatch training mode and uses the agent’s states rather than the agent’s state-action pairs as the inputs. As a result, it can be used alone for low-dimensional problems and can be seamlessly integrated into DQN as the last layer for high-dimensional problems as well. In addition, MRLS-Q uses our proposed average RLS optimization technique, so that it can achieve better convergence performance whether it is used alone or integrated with DQN. At the end of this paper, we demonstrate the effectiveness of MRLS-Q on the CartPole problem and four Atari games and investigate the influences of its hyperparameters experimentally.


---

## Body

## 1. Introduction

Reinforcement learning (RL) is an important machine learning methodology for solving sequential decision-making problems. In theory, by interacting with an initially unknown environment, the RL agent can learn the optimal action policies at different states to maximize the cumulative expected return [1]. Unfortunately, in the past several decades, due to the so-called “curse of dimensionality,” RL can only be used to solve some real-world problems with the small-scale discrete or low-dimensional continuous state space. It is not until 2013 that this dilemma was partially solved by Mnih et al. [2]. By combining the Q-learning algorithm with deep learning, they proposed the preliminary version of the deep Q-network (DQN) algorithm. Two years later, Mnih et al. [3] presented the normal version of DQN, which achieves the human-level performance on 49 classical Atari games. Since then, DQN has attracted more and more research attention, and many other novel deep RL algorithms [4, 5] and new applications [6, 7] have been proposed, and thus deep RL has become a thriving research branch in artificial intelligence. However, although DQN has succeeded in some more complicated problems [8–10], it still has many drawbacks, such as slow convergence, instability, and low sample efficiency. Therefore, we will focus on how to improve the DQN’s performance in this paper.Currently, there are three main categories of research work on improving DQN. The first category mainly focuses on how to estimate action values accurately. For example, Hasselt et al. [11] proposed the double DQN, which can reduce the observed overestimation by exploiting the idea of double Q-learning. Wang et al. [12] introduced a dueling network architecture, which separately estimates state values and advantage values to improve the policy evaluation. Hausknecht and Stone [13] presented the deep recurrent Q-network, which is more suitable for solving partial observation problems, by adding recurrent LSTM layers to convolutional networks. Kim et al. [14] combined the mellowmax method with DQN to calculate the target action values, preventing overestimation effectively. Anschel et al. [15] proposed the averaged DQN, which uses some previously learned action-value estimates to produce the current action value. This algorithm can reduce the approximation error variance in the target values. The second category mainly focuses on how to explore or exploit samples efficiently. Schaul et al. [16] presented a prioritized experience replay, which can make the effective use of historical samples to improve the DQN’s convergence performance. Fortunato et al. [17] proposed the noisynet DQN, which adds noise to the deep network parameters for aiding efficient exploration. Lee et al. [18] introduced an episodic backward update to improve the sample efficiency. The third category mainly focuses on how to reduce memory and computation. Mnih et al. [19] proposed asynchronous variants of four standard reinforcement learning algorithms, such as the asynchronous one-step Q-learning algorithm and the asynchronous n-step Q-learning algorithm. Interestingly, this work also opens the door to research the asynchronous advantage actor-critic (A3C) algorithm.In traditional RL, Q-learning algorithms often use linear functions to approximate action values, which have better stability and fewer hyperparameters to be trained than DQNs [20]. In particular, the least squares (LS) type RL algorithms, such as the least squares policy iteration (LSPI) algorithm [21], the fitted-Q iteration (FQI) algorithm [22], and the recursive least squares temporal difference with forgetting factor (RLS-TD-f) algorithm [23], not only have better stability but also have faster convergence. In the research community of adaptive filtering, the LS and the recursive least squares (RLS) algorithms are famous for their fast convergence rate. Obviously, the success of LS-type RL algorithms mainly benefits from this merit. In recent years, many new machine learning algorithms, such as the extreme learning machine (ELM) [24] and the broad learning system [25, 26], have been proposed by combining LS or RLS algorithms. In practice, the last layer of the neural network used for DQN is usually a linear layer, which means that we probably can improve the DQN’s performance by integrating DQN with the LS-type RL algorithms. In fact, Levine et al. [20] proposed a hybrid approach—the least squares deep Q-network (LS-DQN), which combines DQN with LSPI or FQI. By retraining the last layer of the policy network with a batch least squares update periodically, LS-DQN can obtain better convergence performance than DQN, whereas LS-DQN is not easy to use. At each update by using LSPI or FQI, LS-DQN needs to use the current network parameters to generate a training dataset, which requires running a forward pass of the deep network for each sample in the experience replay buffer. In addition, LS-DQN needs to generate new state-action features and compute the matrix inverse. From the DQN’s learning mechanism, a perfect integrated LS-type algorithm should be able to use the inputs of the DQN’s last layer for approximating action values and should have the same learning mode as DQN.In our previous work [27], we propose two policy control algorithms called ESNRLS-Q and ESNRLS-Sarsa. They seem to meet the above requirements to some extent, although they are also difficult to integrate with DQNs. They use the same experience replay and minibatch learning mode as DQN. In addition, they can avoid computing the matrix inverse and are more suitable for online learning by using recursive least squares (RLS). Based on this work and inspired by the work of Levine et al., we propose a novel minibatch RLS Q-learning algorithm with linear function approximation, called the MRLS-Q. Our main contributions are as follows. (1) By borrowing the experience replay to remove the temporal correlation between the observed transitions, we first combine the traditional Q-learning algorithm with the RLS optimization technique. (2) By using state features rather than state-action features for linear function approximation, we make MRLS-Q able to be used alone and also be integrated into DQN seamlessly. (3) In order to reduce the computational complexity and make the RLS method suitable for training parameters in the minibatch mode, we present an average approximation method for updating the RLS autocorrelation matrix. (4) In order to alleviate the feature change of the same state and integrate MRLS-Q into DQN, we present a new method to define the feature function of MRLS-Q. (5) We demonstrate the effectiveness of MRLS-Q, alone and as the last layer of DQN, by using the CartPole problem and four Atari games, respectively. We also test the influences of its hyperparameters experimentally.The remainder of this paper is organized as follows. Section2 describes the related theories and algorithms of MRLS-Q. Section 3 represents the detailed derivation and the practical implementation of MRLS-Q. Then, in Section 4, comparison experiments on the CartPole problem and four Atari games are conducted to separately verify the effectiveness of MRLS-Q used alone and as the last layer of DQN. Finally, Section 5 summarizes the whole paper.


## 2. Background

In this section, we briefly review the related theories and algorithms of our MRLS-Q, including the Markov decision process (MDP), DQN, and LS-DQN. In addition, we also describe some notations that will be used throughout this paper.


### 2.1. Markov Decision Process

In RL, a sequential decision problem is generally formulated as an MDP with a five-tupleS,A,P,r,γ, where S is the state space, A is the action space, Pst′|st,at∈0,1 and rst′|st,at∈ℛ are the state-transition probability and the immediate reward from the state st to the next state st′ by taking the action at, and γ∈0,1 is the discount factor. At the state st, the agent’s action at is determined by the control policy π.For a given MDP, the goal of RL is to learn the optimal policyπ∗ for maximizing the cumulative expected return Jπ, i.e.,(1)π∗=argmaxπJπ,where Jπ is usually defined in the form of discount return [1] as(2)Jπ=E∑t=0∞γtrt|s0,π,where s0 is the initial state, whereas Jπ is hardly calculated by using the above equation directly, since Pst′|st,at is unknown in RL, and st′ and rt can only be obtained by the agent’s interaction with the environment.To tackle this problem, RL usually resorts to estimating the action valueQπst,at to measure the performance of π when the initial state and action are st and at. In this paper, we assume that S is continuous and A is discrete. For this kind of MDP problems, to overcome the curse of dimensionality, Qπst,at is often approximated by linear function approximators or deep neural networks.


### 2.2. The DQN Algorithm

DQN is probably the most important algorithm in deep RL. It combines the Q-Learning algorithm with deep neural networks and uses the experience relay for breaking the correlation among samples and training network parameters.The DQN algorithm can be summarized as follows. At the current stept, the agent firstly uses the ϵ-greedy policy to select the action at as(3)at=argmaxa∈AQst,a;Θt−1,w.p.1−ϵ,a random action inA,w.p.ϵ,where ϵ is the exploration factor, Θt−1 is the policy network parameter, and Qst,a;Θt−1 is approximated by this network. Then, after taking at, the agent moves to the next state st′, obtains the reward rt, and stores st,at,st′,rt,dt into the experience replay buffer D, where dt∈0,1 denotes that st′ is the terminal state or not. Next, by using the minibatch ℳt=s^t,i,a^t,i,s^t,i′,r^t,i,d^t,ii=1,…,M sampled from D randomly, the algorithm calculates the loss of the policy network as(4)LΘt−1=12MQπS^t,a^t−QS^t,a^t;Θt−122,where S^t=s^t,1,…,s^t,MT, a^t=a^t,1,…,a^t,MT, and QπS^t,a^t is the target value of QS^t,a^t;Θt−1, which is estimated by the target network as(5)QπS^t,a^t=r^t+γ1−d^t∘maxa∈AQS^t′,a;Θ˜,where r^t=r^t,1,…,r^t,MT, S^t′=s^t,1′,…,s^t,M′T, d^t=d^t,1,…,d^t,MT, ∘ denotes the Hadamard product, and Θ˜ is the target network parameter which is copied from the policy network every some fixed steps or episodes. Finally, by using some gradient descent optimization method, the algorithm updates Θt−1 to Θt. For example, by using the SGD method [28], Θt−1 is updated as(6)Θt=Θt−1−α∇Θt−1,where α is the learning rate and ∇Θt−1 denotes ∂LΘt−1/∂Θt−1.


### 2.3. The LS-DQN Algorithm

LS-DQN is a hybrid approach, which combines the traditional LSPI or FQI algorithm with the DQN algorithm. By enjoying the stability and efficiency of LSPI or FQI, it can obtain better performance than DQN.The LS-DQN algorithm can be briefly summarized as follows. Whenever the agent runs DQN some steps, it uses LSPI or FQI to retrain the last layer of the policy network once. The retraining consists of the following three substeps. Firstly, by recalculating all samples in the experience replay buffer with the current network parameters, the policy network generates a new datasetD˜. Secondly, by using the current network parameters and the dataset D˜, the algorithm generates state-action features. Finally, the algorithm uses LSPI to retrain the current last-layer parameter ΘtL in the policy network as(7)Θt:,1LT,…,Θt:,ALTT=A−1b,where Θt:,iL is the ith column vector of ΘtL. Besides, A and b are defined as follows:(8)A=1D˜∑j=1D˜ϕs^j,a^jϕs^j,a^j−γ1−djϕs^j′,πs^j′T,b=1D˜∑j=1D˜ϕs^j,a^jrj,where ϕs^j,a^j is the state-action feature of the state-action pair s^j,a^j. As Levine et al. stated in their work [20], the algorithm can also retrain ΘtL by using FQI, since it is a batch shallow RL algorithm that computes iterative approximations of the Q-function using regression. For brevity, we will not discuss the FQI algorithm in this paper.


## 2.1. Markov Decision Process

In RL, a sequential decision problem is generally formulated as an MDP with a five-tupleS,A,P,r,γ, where S is the state space, A is the action space, Pst′|st,at∈0,1 and rst′|st,at∈ℛ are the state-transition probability and the immediate reward from the state st to the next state st′ by taking the action at, and γ∈0,1 is the discount factor. At the state st, the agent’s action at is determined by the control policy π.For a given MDP, the goal of RL is to learn the optimal policyπ∗ for maximizing the cumulative expected return Jπ, i.e.,(1)π∗=argmaxπJπ,where Jπ is usually defined in the form of discount return [1] as(2)Jπ=E∑t=0∞γtrt|s0,π,where s0 is the initial state, whereas Jπ is hardly calculated by using the above equation directly, since Pst′|st,at is unknown in RL, and st′ and rt can only be obtained by the agent’s interaction with the environment.To tackle this problem, RL usually resorts to estimating the action valueQπst,at to measure the performance of π when the initial state and action are st and at. In this paper, we assume that S is continuous and A is discrete. For this kind of MDP problems, to overcome the curse of dimensionality, Qπst,at is often approximated by linear function approximators or deep neural networks.


## 2.2. The DQN Algorithm

DQN is probably the most important algorithm in deep RL. It combines the Q-Learning algorithm with deep neural networks and uses the experience relay for breaking the correlation among samples and training network parameters.The DQN algorithm can be summarized as follows. At the current stept, the agent firstly uses the ϵ-greedy policy to select the action at as(3)at=argmaxa∈AQst,a;Θt−1,w.p.1−ϵ,a random action inA,w.p.ϵ,where ϵ is the exploration factor, Θt−1 is the policy network parameter, and Qst,a;Θt−1 is approximated by this network. Then, after taking at, the agent moves to the next state st′, obtains the reward rt, and stores st,at,st′,rt,dt into the experience replay buffer D, where dt∈0,1 denotes that st′ is the terminal state or not. Next, by using the minibatch ℳt=s^t,i,a^t,i,s^t,i′,r^t,i,d^t,ii=1,…,M sampled from D randomly, the algorithm calculates the loss of the policy network as(4)LΘt−1=12MQπS^t,a^t−QS^t,a^t;Θt−122,where S^t=s^t,1,…,s^t,MT, a^t=a^t,1,…,a^t,MT, and QπS^t,a^t is the target value of QS^t,a^t;Θt−1, which is estimated by the target network as(5)QπS^t,a^t=r^t+γ1−d^t∘maxa∈AQS^t′,a;Θ˜,where r^t=r^t,1,…,r^t,MT, S^t′=s^t,1′,…,s^t,M′T, d^t=d^t,1,…,d^t,MT, ∘ denotes the Hadamard product, and Θ˜ is the target network parameter which is copied from the policy network every some fixed steps or episodes. Finally, by using some gradient descent optimization method, the algorithm updates Θt−1 to Θt. For example, by using the SGD method [28], Θt−1 is updated as(6)Θt=Θt−1−α∇Θt−1,where α is the learning rate and ∇Θt−1 denotes ∂LΘt−1/∂Θt−1.


## 2.3. The LS-DQN Algorithm

LS-DQN is a hybrid approach, which combines the traditional LSPI or FQI algorithm with the DQN algorithm. By enjoying the stability and efficiency of LSPI or FQI, it can obtain better performance than DQN.The LS-DQN algorithm can be briefly summarized as follows. Whenever the agent runs DQN some steps, it uses LSPI or FQI to retrain the last layer of the policy network once. The retraining consists of the following three substeps. Firstly, by recalculating all samples in the experience replay buffer with the current network parameters, the policy network generates a new datasetD˜. Secondly, by using the current network parameters and the dataset D˜, the algorithm generates state-action features. Finally, the algorithm uses LSPI to retrain the current last-layer parameter ΘtL in the policy network as(7)Θt:,1LT,…,Θt:,ALTT=A−1b,where Θt:,iL is the ith column vector of ΘtL. Besides, A and b are defined as follows:(8)A=1D˜∑j=1D˜ϕs^j,a^jϕs^j,a^j−γ1−djϕs^j′,πs^j′T,b=1D˜∑j=1D˜ϕs^j,a^jrj,where ϕs^j,a^j is the state-action feature of the state-action pair s^j,a^j. As Levine et al. stated in their work [20], the algorithm can also retrain ΘtL by using FQI, since it is a batch shallow RL algorithm that computes iterative approximations of the Q-function using regression. For brevity, we will not discuss the FQI algorithm in this paper.


## 3. The Proposed Algorithm

In this section, we will introduce the detailed derivation and the practical implementation of our proposed algorithm, respectively. Our algorithm, the MRLS-Q algorithm, can be used not only alone but also as the last layer of DQN.


### 3.1. Algorithm Derivation

MRLS-Q is a new Q-learning algorithm with linear function approximation, but it is more similar to the DQN algorithm rather than the traditional Q-learning algorithm. It uses the experience replay and the minibatch training mode, separates the linear function approximator into a policy approximator and a target approximator, and uses the state features rather than the state-action features. Besides, it uses an average RLS method for updating parameters.First, we introduce the agent’s interaction with the environment. At the current stept, the agent also uses the ϵ-greedy policy to select the action at as equation (3). Note here that Qst,a;Θt−1 is approximated by the policy approximator as(9)Qst,a;Θt−1=ϕstTΘt−1:,ina,where ϕst∈ℛN is the feature vector of st, Θt−1∈ℛN×A is the policy approximator parameter, ina denotes the index of a in A, and Θt−1:,ina is the inath column vector of Θt−1. Then, the agent takes at, moves to st′, obtains rt, and stores st,at,st′,rt,dt into the experience replay buffer D.Second, we introduce the RLS update of the policy approximator parameter in the minibatch training mode. Letℳn=s^n,i,a^n,i,s^n,i′,r^n,i,d^n,ii=1,…,M denote the minibatch sampled from D at the nth step, and let ΦS^n=ϕs^n,1,…,ϕs^n,MT denote the feature matrix of S^n. Define the least squares loss function as(10)L^Θ=12M∑n=1tλt−nQπS^n,a^n−QS^n,a^n;Θ22,where λ∈0,1 is the forgetting factor and QS^n,a^n;Θ is approximated by the policy approximator as(11)QS^n,a^n;Θ=ΦS^nΘ:,ina^n,and QπS^n,a^n is estimated by the target approximator as(12)QπS^n,a^n=r^n+γ1−d^n∘maxa∈AΦS^n′Θ˜:,ina,where Θ˜ is the target approximator parameter which is copied from the policy approximator every some fixed steps or episodes. Then, the parameter learning problem of the policy approximator can be transformed into(13)Θt=argminΘL^Θ.By using the chain rule, we can get(14)∇^Θ=−1M∑n=1tλt−nΦS^nTQ^πS^n,A−Q^S^n,A;Θ,where ∇^Θ denotes ∂L^Θ/∂Θ, and an element in Q^S^n,A;Θ∈ℛM×A is defined as(15)Q^s^n,i,a;Θ=Qs^n,i,a^n,i;Θ,a=a^n,i,0,a≠a^n,i,and an element in Q^πS^n,A∈ℛM×A is defined as(16)Q^πs^n,i,a=Qπs^n,i,a^n,i,a=a^n,i,0,a≠a^n,i.Let∇^Θ=0. Then, we can get(17)Θt=At−1Bt,where(18)At=1M∑n=1tλt−nΦS^nTΦS^n,Bt=1M∑n=1tλt−nΦS^nTQ^πS^n,A.Rewrite the above two equations as the following recursive forms:(19)At=λAt−1+1MΦS^tTΦS^t,(20)Bt=λBt−1+1MΦS^tTQ^πS^t,A.Further, rewrite the above two equations as the following vector forms:(21)At=λAt−1+1M∑i=1Mϕs^t,iϕs^t,iT,(22)Bt=λBt−1+1M∑i=1Mϕs^t,iQ^πs^t,i,A,where Q^πs^t,i,A is the ith row vector of Q^πS^t,A. Unfortunately, we cannot directly use the Sherman–Morrison formula [29] to compute At−1, since the last term in the right-hand side of equation (21) is a sum of vector products.Next, we present an average approximation method to deal with the above problem. Considering that all training samples are from the same environment and thus their features have some similarity, we rewrite equations (21) and (22) as follows:(23)At≈λAt−1+kϕ¯tϕt¯T,(24)Bt≈λBt−1+kϕ¯tq¯tπ,where k is the approximation factor, and ϕ¯t and q¯tπ are defined as(25)ϕ¯t=1M∑i=1Mϕs^t,i,(26)q¯tπ=1M∑i=1MQ^πs^t,i,A.LetPt=At−1. By using the Sherman–Morrison formula for (23), we can get(27)Pt=1λPt−1−gtvtT,where(28)vt=Pt−1ϕ¯t,(29)gt=kvtλ+kvtTϕ¯t.Plugging equations (24) and (27) into (17), we finally get(30)Θt≈Θt−1+kPt−1ϕ¯tq¯tπ−q¯tλ+kvtTϕ¯t,where(31)q¯t=1M∑i=1MQ^s^t,i,A;Θt−1,where Q^s^t,i,A;Θt−1 denotes the ith row vector of Q^S^t,A;Θt−1.


### 3.2. Practical Implementation

As reviewed in Section2.2, DQN generally uses gradient descent methods to update network parameters. To make MRLS-Q easier to be integrated into DQN, we next rewrite equation (30) as the “gradient descent” form of ∇Θt−1.If the loss function of MRLS-Q is defined by equation (4), by using the chain rule for equation (4), we can get(32)∇Θt−1=−1MΦS^tTQ^πS^t,A−Q^S^t,A;Θt−1.Recall the fact that we once usedkϕ¯tϕt¯T and kϕ¯tq¯tπ in equations (23) and (24) to replace 1/MΦS^tTΦS^t and 1/MΦS^tTQ^πS^t,A in equations (19) and (20), respectively, which means(33)kϕ¯tϕt¯T=1MΦS^tTΦS^t,(34)kϕ¯tq¯tπ=1MΦS^tTQ^πS^t,A.In addition, from equation (31), we can obtain(35)kϕ¯tq¯t=kMϕ¯t∑i=1MQ^s^t,i,A;Θt−1.Using equation (9) yields(36)Q^s^t,i,A;Θt−1=ϕs^t,iTΘt−1.Then, equation (35) can be written as(37)kϕ¯tq¯t=kMϕ¯t∑i=1Mϕs^t,iTΘt−1.Further, from equation (25), the above equation can be written as(38)kϕ¯tq¯t=kϕ¯tϕ¯tTΘt−1.Next, plugging equation (33) into equation (38), we have(39)kϕ¯tq¯t=1MΦS^tTΦS^tΘt−1.From equations (9) and (11), the above equation can be rewritten as(40)kϕ¯tq¯t=1MΦS^tTQs^t,i,A;Θt−1.Using equations (34) and (40), we can get(41)kϕ¯tq¯tπ−q¯t=−∇Θt−1.Therefore, we can rewrite equation (30) as(42)Θt≈Θt−1−Pt−1λ+kvtTϕ¯t∇Θt−1.It shows thatPt−1/λ+kvtTϕ¯t is the learning rate of Θt in MRLS-Q.However, although RLS has a fast convergence rate, it often suffers from overfitting. In recent years, there has been extensive research on this problem. Based on Ekşioğlu’s work [30], we add an L1 regularization term into the above equation, i.e.,(43)Θt≈Θt−1−Pt−1λ+kvtTϕ¯t∇Θt−1−ηPtsgnΘt−1,where η is the regularization factor and sgn⋅ is the sign function.Based on the above derivation, the pseudocode of MRLS-Q is summarized in Algorithm1, and the flow diagram of MRLS-Q is summarized in Figure 1. In the practical implementation, here ∇Θt−1 can be calculated by the automatic differentiation package of PyTorch or TensorFlow directly. Besides being used alone, MRLS-Q can also be used as the last layer of DQN, since it uses the same loss function and experience replay as DQN. However, there is still an obstacle to the combination of MRLS-Q and DQN. As the training goes on, the parameters of the DQN network are continuously changing, and the outputs of the same inputs are changing as well. Thus, we cannot use the inputs of the DQN’s last layer as the features of MRLS-Q directly. In order to alleviate this kind of change and integrate MRLS-Q into DQN, we present a new method to define the feature function of MRLS-Q as(44)ΦS^n=XtL1/MNL−1∑i=1M∑j=1NL−1Xt,i,jL+ν,where XtL∈ℛM×NL−1 is the output matrix of the DQN’s penultimate layer and ν is a small hyperparameter to prevent the denominator becoming zero.Figure 1
Flow diagram of MRLS-Q.Algorithm 1: MRLS-Q.
(1)
inputϕl⋅l=1,…,N, ϵ, γ, λ, k, η, M and initializeD=, Θ0, Θ˜, P0=αI(2)
for episode = 1, …, MaxEpsidoesdo(3)
initialize states1(4)
fort=1, …, MaxStepsdo(5)
select actionat with ϵ- greedy policy, and take action at(6)
measure next statest+1, reward rt and terminal state dt(7)
storest,at,st+1,rt,dt into D(8)
sample minibatchℳt from D(9)
compute loss functionLΘt−1 according to (11), (12) and (4)(10)
compute gradient∇Θt−1 according to (32)(11)
updateΘt and Pt according to (43) and (27)(12)
updateΘ˜ by Θt every fixed steps or episodes(13)
ifdt==1ort  = = MaxSteps do(14)
setP0=Pt and Θ0=Θt, and break the inner loop(15)
end if(16)
end for(17)
end for


## 3.1. Algorithm Derivation

MRLS-Q is a new Q-learning algorithm with linear function approximation, but it is more similar to the DQN algorithm rather than the traditional Q-learning algorithm. It uses the experience replay and the minibatch training mode, separates the linear function approximator into a policy approximator and a target approximator, and uses the state features rather than the state-action features. Besides, it uses an average RLS method for updating parameters.First, we introduce the agent’s interaction with the environment. At the current stept, the agent also uses the ϵ-greedy policy to select the action at as equation (3). Note here that Qst,a;Θt−1 is approximated by the policy approximator as(9)Qst,a;Θt−1=ϕstTΘt−1:,ina,where ϕst∈ℛN is the feature vector of st, Θt−1∈ℛN×A is the policy approximator parameter, ina denotes the index of a in A, and Θt−1:,ina is the inath column vector of Θt−1. Then, the agent takes at, moves to st′, obtains rt, and stores st,at,st′,rt,dt into the experience replay buffer D.Second, we introduce the RLS update of the policy approximator parameter in the minibatch training mode. Letℳn=s^n,i,a^n,i,s^n,i′,r^n,i,d^n,ii=1,…,M denote the minibatch sampled from D at the nth step, and let ΦS^n=ϕs^n,1,…,ϕs^n,MT denote the feature matrix of S^n. Define the least squares loss function as(10)L^Θ=12M∑n=1tλt−nQπS^n,a^n−QS^n,a^n;Θ22,where λ∈0,1 is the forgetting factor and QS^n,a^n;Θ is approximated by the policy approximator as(11)QS^n,a^n;Θ=ΦS^nΘ:,ina^n,and QπS^n,a^n is estimated by the target approximator as(12)QπS^n,a^n=r^n+γ1−d^n∘maxa∈AΦS^n′Θ˜:,ina,where Θ˜ is the target approximator parameter which is copied from the policy approximator every some fixed steps or episodes. Then, the parameter learning problem of the policy approximator can be transformed into(13)Θt=argminΘL^Θ.By using the chain rule, we can get(14)∇^Θ=−1M∑n=1tλt−nΦS^nTQ^πS^n,A−Q^S^n,A;Θ,where ∇^Θ denotes ∂L^Θ/∂Θ, and an element in Q^S^n,A;Θ∈ℛM×A is defined as(15)Q^s^n,i,a;Θ=Qs^n,i,a^n,i;Θ,a=a^n,i,0,a≠a^n,i,and an element in Q^πS^n,A∈ℛM×A is defined as(16)Q^πs^n,i,a=Qπs^n,i,a^n,i,a=a^n,i,0,a≠a^n,i.Let∇^Θ=0. Then, we can get(17)Θt=At−1Bt,where(18)At=1M∑n=1tλt−nΦS^nTΦS^n,Bt=1M∑n=1tλt−nΦS^nTQ^πS^n,A.Rewrite the above two equations as the following recursive forms:(19)At=λAt−1+1MΦS^tTΦS^t,(20)Bt=λBt−1+1MΦS^tTQ^πS^t,A.Further, rewrite the above two equations as the following vector forms:(21)At=λAt−1+1M∑i=1Mϕs^t,iϕs^t,iT,(22)Bt=λBt−1+1M∑i=1Mϕs^t,iQ^πs^t,i,A,where Q^πs^t,i,A is the ith row vector of Q^πS^t,A. Unfortunately, we cannot directly use the Sherman–Morrison formula [29] to compute At−1, since the last term in the right-hand side of equation (21) is a sum of vector products.Next, we present an average approximation method to deal with the above problem. Considering that all training samples are from the same environment and thus their features have some similarity, we rewrite equations (21) and (22) as follows:(23)At≈λAt−1+kϕ¯tϕt¯T,(24)Bt≈λBt−1+kϕ¯tq¯tπ,where k is the approximation factor, and ϕ¯t and q¯tπ are defined as(25)ϕ¯t=1M∑i=1Mϕs^t,i,(26)q¯tπ=1M∑i=1MQ^πs^t,i,A.LetPt=At−1. By using the Sherman–Morrison formula for (23), we can get(27)Pt=1λPt−1−gtvtT,where(28)vt=Pt−1ϕ¯t,(29)gt=kvtλ+kvtTϕ¯t.Plugging equations (24) and (27) into (17), we finally get(30)Θt≈Θt−1+kPt−1ϕ¯tq¯tπ−q¯tλ+kvtTϕ¯t,where(31)q¯t=1M∑i=1MQ^s^t,i,A;Θt−1,where Q^s^t,i,A;Θt−1 denotes the ith row vector of Q^S^t,A;Θt−1.


## 3.2. Practical Implementation

As reviewed in Section2.2, DQN generally uses gradient descent methods to update network parameters. To make MRLS-Q easier to be integrated into DQN, we next rewrite equation (30) as the “gradient descent” form of ∇Θt−1.If the loss function of MRLS-Q is defined by equation (4), by using the chain rule for equation (4), we can get(32)∇Θt−1=−1MΦS^tTQ^πS^t,A−Q^S^t,A;Θt−1.Recall the fact that we once usedkϕ¯tϕt¯T and kϕ¯tq¯tπ in equations (23) and (24) to replace 1/MΦS^tTΦS^t and 1/MΦS^tTQ^πS^t,A in equations (19) and (20), respectively, which means(33)kϕ¯tϕt¯T=1MΦS^tTΦS^t,(34)kϕ¯tq¯tπ=1MΦS^tTQ^πS^t,A.In addition, from equation (31), we can obtain(35)kϕ¯tq¯t=kMϕ¯t∑i=1MQ^s^t,i,A;Θt−1.Using equation (9) yields(36)Q^s^t,i,A;Θt−1=ϕs^t,iTΘt−1.Then, equation (35) can be written as(37)kϕ¯tq¯t=kMϕ¯t∑i=1Mϕs^t,iTΘt−1.Further, from equation (25), the above equation can be written as(38)kϕ¯tq¯t=kϕ¯tϕ¯tTΘt−1.Next, plugging equation (33) into equation (38), we have(39)kϕ¯tq¯t=1MΦS^tTΦS^tΘt−1.From equations (9) and (11), the above equation can be rewritten as(40)kϕ¯tq¯t=1MΦS^tTQs^t,i,A;Θt−1.Using equations (34) and (40), we can get(41)kϕ¯tq¯tπ−q¯t=−∇Θt−1.Therefore, we can rewrite equation (30) as(42)Θt≈Θt−1−Pt−1λ+kvtTϕ¯t∇Θt−1.It shows thatPt−1/λ+kvtTϕ¯t is the learning rate of Θt in MRLS-Q.However, although RLS has a fast convergence rate, it often suffers from overfitting. In recent years, there has been extensive research on this problem. Based on Ekşioğlu’s work [30], we add an L1 regularization term into the above equation, i.e.,(43)Θt≈Θt−1−Pt−1λ+kvtTϕ¯t∇Θt−1−ηPtsgnΘt−1,where η is the regularization factor and sgn⋅ is the sign function.Based on the above derivation, the pseudocode of MRLS-Q is summarized in Algorithm1, and the flow diagram of MRLS-Q is summarized in Figure 1. In the practical implementation, here ∇Θt−1 can be calculated by the automatic differentiation package of PyTorch or TensorFlow directly. Besides being used alone, MRLS-Q can also be used as the last layer of DQN, since it uses the same loss function and experience replay as DQN. However, there is still an obstacle to the combination of MRLS-Q and DQN. As the training goes on, the parameters of the DQN network are continuously changing, and the outputs of the same inputs are changing as well. Thus, we cannot use the inputs of the DQN’s last layer as the features of MRLS-Q directly. In order to alleviate this kind of change and integrate MRLS-Q into DQN, we present a new method to define the feature function of MRLS-Q as(44)ΦS^n=XtL1/MNL−1∑i=1M∑j=1NL−1Xt,i,jL+ν,where XtL∈ℛM×NL−1 is the output matrix of the DQN’s penultimate layer and ν is a small hyperparameter to prevent the denominator becoming zero.Figure 1
Flow diagram of MRLS-Q.Algorithm 1: MRLS-Q.
(1)
inputϕl⋅l=1,…,N, ϵ, γ, λ, k, η, M and initializeD=, Θ0, Θ˜, P0=αI(2)
for episode = 1, …, MaxEpsidoesdo(3)
initialize states1(4)
fort=1, …, MaxStepsdo(5)
select actionat with ϵ- greedy policy, and take action at(6)
measure next statest+1, reward rt and terminal state dt(7)
storest,at,st+1,rt,dt into D(8)
sample minibatchℳt from D(9)
compute loss functionLΘt−1 according to (11), (12) and (4)(10)
compute gradient∇Θt−1 according to (32)(11)
updateΘt and Pt according to (43) and (27)(12)
updateΘ˜ by Θt every fixed steps or episodes(13)
ifdt==1ort  = = MaxSteps do(14)
setP0=Pt and Θ0=Θt, and break the inner loop(15)
end if(16)
end for(17)
end for


## 4. Experiments

In this section, we use two sets of experiments to demonstrate the effectiveness of MRLS-Q. Our experiments are divided into two sections. In Section4.1, we test MRLS-Q on the CartPole problem as an independent algorithm. In Section 4.2, we test MRLS-Q on four Atari games as the last layer of DQN.


### 4.1. The CartPole Problem

In this set of experiments, we firstly verify the performance of MRLS-Q on the CartPole-v0 problem, which is from the OpenAI Gym. For comparison purposes, we build a new algorithm called Adam-Q, by replacingPt−1/λ+kvtTϕ¯t in equation (42) with the Adam optimizer, since the traditional Q-learning algorithm with linear function approximation is hardly convergent in 100 episodes. Then, we verify the influences of hyperparameters on MRLS-Q, experimentally.To compare the performance between MRLS-Q and Adam-Q, the experimental settings are summarized as follows. (1) Both algorithms use 400 radial basis functions (RBFs) for action-value approximation. These RBFs are generated from104 random samples in the CartPole’s state space, by using eight scikit-learn RBFSamplers [31] with kernel parameters {0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0}. (2) The exploration rate ϵ is initialized to 0.95 and is gradually decreased to 0.01 over 1000 steps. (3) The discount factor γ is 0.99. (4) The capacity of the experience replay buffer D is 104, and the minibatch size is 32. The learning starts when the number in D reaches the minibatch size. (5) The policy approximator parameter Θ0 and the target approximator parameter Θ˜ are initialized randomly. (6) Θ˜ is updated by Θt each step. Note that the performances of both algorithms will get worse if we increase the update steps, since the CartPole problem is very simple and both algorithms converge fast. (7) The max norm of ∇Θt−1 is clipped to 1 by the L2 norm. (8) The two algorithms run five times and 100 episodes for each time. In each episode, each algorithm runs 200 steps at most. (9) Besides, in Adam-Q, the learning rate, β1, and β2 of Adam are 0.001, 0.9, and 0.999; in MRLS-Q, the initialization P0, the forgetting factor λ, the regularization factor η, and the approximation factor k are 0.5I, 1, 10−5, and 1/32, respectively. The average result of this experiment is shown in Figure 2(a). It can be seen that our MRLS-Q has better convergence than Adam-Q.Figure 2
Performance comparison and hyperparameter influences on MRLS-Q. (a) Adam-Q vs. MRLS-Q. (b) Influence ofD’s capacity. (c) Influence of P’s initialization. (d) Influence of k value.
(a)(b)(c)(d)To investigate hyperparameter influences on MRLS-Q, we testD∈500,1000,5000,10000, P0∈0.1I,0.2I,0.5I,I, and k∈1/2,1/8,1/32,1/128, respectively. The other settings of these experiments are the same as what we did for MRLS-Q in the previous experiment. The average results of these experiments are presented in Figures 2(b)–2(d). From Figure 2(b), it shows that the capacity of D has a significant influence on the performance of MRLS-Q. The larger capacity will result in the better performance, since big D is helpful to remove the correlation between the observed transitions. From Figure 2(c), it can be seen that MRLS-Q is robust to the initialization P0, whereas too big P0 will make MRLS-Q become unstable and too small P0 will make MRLS-Q converge slowly. From Figure 2(d), it can be seen that k also has a significant influence on MRLS-Q. From equation (29), bigger k will make Pt update with higher strength. If state feature values change greatly, k should be set to a big value.


### 4.2. Four Atari Games

In this set of experiments, we verify MRLS-Q as the last layer of DQN on four Atari games: Pong-v0, Breakout-v0, SpaceInvaders-v0, and RiverRaid-v0, which are from the OpenAI Gym. Here we choose the traditional DQN algorithm with the Adam optimizer for comparison. For Adam-DQN and in the second to fifth layers of Hybrid-DQN, the learning rate,β1, and β2 of Adam are 0.0000625, 0.9, and 0.999; in the last layer of Hybrid-DQN, the initialization P0, the forgetting factor λ, the regularization factor η, the approximation factor k, and ν are 0.1I, 1, 10−8, 1/2, and 10−12, respectively. Note that here we use a big k to update Pt for adapting to the feature change.The average evaluation results are presented in Figure3. It shows that Hybrid-DQN can speed up the convergence of all tested games. Figure 3(a) is much clearer to demonstrate this advantage, since the Pong game is much simpler than other three games. In addition, Figures 3(a), 3(c), and 3(d) show that Hybrid-DQN can improve the convergence quality of Pong, SpaceInvaders, and RiverRaid, and Figure 3(b) shows that Hybrid-DQN can improve the learning stability of Breakout. In summary, by integrating our MRLS-Q, Hybrid-DQN can improve the stability and performance. Compared with the LS-DQN algorithm, MRLS-Q can be used as the last layer of DQN directly, and thus Hybrid-DQN is easier to use.Figure 3
Performance comparison between Adam-DQN and Hybrid-DQN. (a) Pong. (b) Breakout. (c) SpaceInvaders. (d) RiverRaid.
(a)(b)(c)(d)


## 4.1. The CartPole Problem

In this set of experiments, we firstly verify the performance of MRLS-Q on the CartPole-v0 problem, which is from the OpenAI Gym. For comparison purposes, we build a new algorithm called Adam-Q, by replacingPt−1/λ+kvtTϕ¯t in equation (42) with the Adam optimizer, since the traditional Q-learning algorithm with linear function approximation is hardly convergent in 100 episodes. Then, we verify the influences of hyperparameters on MRLS-Q, experimentally.To compare the performance between MRLS-Q and Adam-Q, the experimental settings are summarized as follows. (1) Both algorithms use 400 radial basis functions (RBFs) for action-value approximation. These RBFs are generated from104 random samples in the CartPole’s state space, by using eight scikit-learn RBFSamplers [31] with kernel parameters {0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0}. (2) The exploration rate ϵ is initialized to 0.95 and is gradually decreased to 0.01 over 1000 steps. (3) The discount factor γ is 0.99. (4) The capacity of the experience replay buffer D is 104, and the minibatch size is 32. The learning starts when the number in D reaches the minibatch size. (5) The policy approximator parameter Θ0 and the target approximator parameter Θ˜ are initialized randomly. (6) Θ˜ is updated by Θt each step. Note that the performances of both algorithms will get worse if we increase the update steps, since the CartPole problem is very simple and both algorithms converge fast. (7) The max norm of ∇Θt−1 is clipped to 1 by the L2 norm. (8) The two algorithms run five times and 100 episodes for each time. In each episode, each algorithm runs 200 steps at most. (9) Besides, in Adam-Q, the learning rate, β1, and β2 of Adam are 0.001, 0.9, and 0.999; in MRLS-Q, the initialization P0, the forgetting factor λ, the regularization factor η, and the approximation factor k are 0.5I, 1, 10−5, and 1/32, respectively. The average result of this experiment is shown in Figure 2(a). It can be seen that our MRLS-Q has better convergence than Adam-Q.Figure 2
Performance comparison and hyperparameter influences on MRLS-Q. (a) Adam-Q vs. MRLS-Q. (b) Influence ofD’s capacity. (c) Influence of P’s initialization. (d) Influence of k value.
(a)(b)(c)(d)To investigate hyperparameter influences on MRLS-Q, we testD∈500,1000,5000,10000, P0∈0.1I,0.2I,0.5I,I, and k∈1/2,1/8,1/32,1/128, respectively. The other settings of these experiments are the same as what we did for MRLS-Q in the previous experiment. The average results of these experiments are presented in Figures 2(b)–2(d). From Figure 2(b), it shows that the capacity of D has a significant influence on the performance of MRLS-Q. The larger capacity will result in the better performance, since big D is helpful to remove the correlation between the observed transitions. From Figure 2(c), it can be seen that MRLS-Q is robust to the initialization P0, whereas too big P0 will make MRLS-Q become unstable and too small P0 will make MRLS-Q converge slowly. From Figure 2(d), it can be seen that k also has a significant influence on MRLS-Q. From equation (29), bigger k will make Pt update with higher strength. If state feature values change greatly, k should be set to a big value.


## 4.2. Four Atari Games

In this set of experiments, we verify MRLS-Q as the last layer of DQN on four Atari games: Pong-v0, Breakout-v0, SpaceInvaders-v0, and RiverRaid-v0, which are from the OpenAI Gym. Here we choose the traditional DQN algorithm with the Adam optimizer for comparison. For Adam-DQN and in the second to fifth layers of Hybrid-DQN, the learning rate,β1, and β2 of Adam are 0.0000625, 0.9, and 0.999; in the last layer of Hybrid-DQN, the initialization P0, the forgetting factor λ, the regularization factor η, the approximation factor k, and ν are 0.1I, 1, 10−8, 1/2, and 10−12, respectively. Note that here we use a big k to update Pt for adapting to the feature change.The average evaluation results are presented in Figure3. It shows that Hybrid-DQN can speed up the convergence of all tested games. Figure 3(a) is much clearer to demonstrate this advantage, since the Pong game is much simpler than other three games. In addition, Figures 3(a), 3(c), and 3(d) show that Hybrid-DQN can improve the convergence quality of Pong, SpaceInvaders, and RiverRaid, and Figure 3(b) shows that Hybrid-DQN can improve the learning stability of Breakout. In summary, by integrating our MRLS-Q, Hybrid-DQN can improve the stability and performance. Compared with the LS-DQN algorithm, MRLS-Q can be used as the last layer of DQN directly, and thus Hybrid-DQN is easier to use.Figure 3
Performance comparison between Adam-DQN and Hybrid-DQN. (a) Pong. (b) Breakout. (c) SpaceInvaders. (d) RiverRaid.
(a)(b)(c)(d)


## 5. Conclusion

How to improve convergence and stability of the DQN algorithm is one of the key issues in deep RL. In this paper, we propose MRLS-Q, a linear RLS function approximation algorithm with the similar learning mechanism to DQN. MRLS-Q can be used not only alone but also as the last layer of DQN. Similar to LS-DQN, the Hybrid-DQN with MRLS-Q can enjoy rich representations from deep RL networks as well as stability and data efficiency of the RLS method, but it can seamlessly integrate MRLS-Q and thus is easier to use. In MRLS-Q, we use the experience replay to break the correlation between training samples, present an average RLS optimization method to improve the convergence performance and reduce the computational complexity, employ anL1 regularization technique to prevent overfitting, and propose a new method to define the feature function for alleviating the feature change of the same state and integrating MRLS-Q into DQN. Experiment results on the CartPole problem demonstrate that MRLS-Q has better convergence than Adam-Q and reveal the hyperparameter influences on MRLS-Q. In addition, experiment results on four Atari games demonstrate that DQN can improve convergence and stability by integrating with MRLS-Q.



---

*Source: 5370281-2021-10-08.xml*