Z-Score Experience Replay in Off-Policy Deep Reinforcement Learning Authors: Yana Yang, Meng Xi, Huiao Dai, Jiabao Wen, Jiachen Yang, Sergio Toral Marín Published: 2024 ABSTRACT AbstractReinforcement learning, as a machine learning method that does not require pre-training data, seeks the optimal policy through the continuous interaction between an agent and its environment. It is an important approach to solving sequential decision-making problems. By combining it with deep learning, deep reinforcement learning possesses powerful perception and decision-making capabilities and has been widely applied to various domains to tackle complex decision problems. Off-policy reinforcement learning separates exploration and exploitation by storing and replaying interaction experiences, making it easier to find global optimal solutions. Understanding how to utilize experiences is crucial for improving the efficiency of off-policy reinforcement learning algorithms. To address this problem, this paper proposes Z-Score Prioritized Experience Replay, which enhances the utilization of experiences and improves the performance and convergence speed of the algorithm. A series of ablation experiments demonstrate that the proposed method significantly improves the effectiveness of deep reinforcement learning algorithms.Keywords: deep reinforcement learning, off policy, priority experience replay, z-score 1. Introduction Reinforcement learning (RL) is commonly believed to have its roots in the behaviorist theories in psychology, where habitual behaviors that yield maximum benefits for an organism are gradually formed through a continuous process of being rewarded or punished by the environment. It was not until the late 20th century that RL began to receive attention from researchers and started to be rapidly developed, being considered as one of the core techniques for designing intelligent agents [1]. In the process of interacting with the environment, an agent selects actions based on the state in the current timestep, moves to the next state, and receives rewards. This process generates experiences, and the agent learns from these experiences to continuously improve its strategy and maximize cumulative rewards. Traditional reinforcement learning methods are suitable for discrete state spaces and cannot effectively handle problems in high-dimensional continuous state spaces. Linear value function approximation or nonlinear value function approximation can parameterize the relationship between states and value functions [2] to handle problems in high-dimensional state spaces. Linear value function approximation has good convergence guarantees, but it often requires manual feature extraction and has limited modeling capacity. Nonlinear value function approximation does not have strict convergence proofs but has a powerful modeling capacity. Tesauro [3] combined temporal difference (TD) learning with nonlinear value function approximation to propose the TD-Gammon algorithm. This algorithm uses a feedforward neural network to estimate the state value function and achieves top-level human performance in Backgammon. RL interacts with the given environment via trial and error, adjusting the agent’s behavior strategy based on the received rewards [1]. This decision-making process, which resembles human experiential thinking and intuitive reasoning, has found widespread applications in the field of artificial intelligence [4,5]. However, as the complexity of application environments increases, the “curse of dimensionality” [6] limits the further development of RL. To better represent high-dimensional state spaces in complex task scenarios, DeepMind, the Google AI team, innovatively combined deep learning (DL) with RL, creating a new research focus called deep reinforcement learning (DRL) [7]. DRL combines the perceptual capability of DL with the decision-making ability of RL, enabling the learning of abstract representations from large-scale input data and using these representations to self-motivate and optimize problem-solving strategies [8]. Currently, DRL, with its end-to-end learning approach, has made significant progress in various domains such as game playing [9,10,11], robotics control [12,13,14], finance and trade [15,16,17], traffic control [18,19,20], and autonomous driving [21,22,23], where the performance of trained agents in these domains has reached or even surpassed human levels. Unlike supervised learning and unsupervised learning, RL explores the environment through continuous interaction between an agent and its environment to acquire experience (samples). Based on this experience, the agent continuously updates its policy to find an optimal strategy that adapts to the environment. RL does not have a fixed dataset during the learning process; therefore, the agent needs to consume a significant amount of time and resources in order to obtain interactive experiences. In complex environments, particularly real-world environments such as autonomous driving, RL bears considerable risks and costs. Additionally, issues like wear and tear and response delays limit the amount of experience an agent can collect. How to effectively utilize limited experiences to train an intelligent agent with the best possible strategy has become a focal point for researchers both domestically and internationally. Storing and sampling experience samples is a key problem in off-policy deep reinforcement learning. During training, these methods use the error gradient backpropagation algorithm, which requires the training sample set to be independent and identically distributed (IID) or approximately IID to converge properly. However, samples exhibit strong temporal correlations. To eliminate sample correlation, scholars use an experience replay buffer to store and manage samples, and randomly sample from the buffer during training. They require a large-capacity experience replay buffer to store the samples. To populate the buffer, the agent needs to interact frequently with the environment. However, the cost of agent–environment interactions is expensive, not only in terms of time but also in terms of safety, controllability, and recoverability. Therefore, it is of great significance to study efficient sampling, reduce the number of agent–environment interactions, and improve the learning performance of the agent for deep reinforcement learning research. This emerging research area has quickly gained attention from a large number of researchers. So far, experience replay has become a prominent technique for improving the stability and convergence speed of off-policy deep reinforcement learning (DRL) algorithms. The proposed method in this paper is adaptive, consistently adjusting to the changes in the deep network during training, resulting in a more reasonable estimation of sample priorities. Experimental results show that our approach enhances sample utilization, reduces interactions, and improves learning performance, ultimately leading to higher cumulative rewards. 2. Related Works With the continuous development of deep reinforcement learning algorithms [24], many novel algorithms have been proposed by researchers worldwide to improve sample utilization efficiency [25]. The Dynamic Counterfactual Experience Replay (DCER) algorithm [26] addresses the issues of weak active exploration ability and suboptimal convergence in traditional deep reinforcement learning algorithms by creatively adding dynamic counterfactual experiences from both on-policy and off-policy contexts. This improves the efficiency of sample utilization by incorporating experiences that differ from the actual actions taken during sampling. The Quantum Experience Replay (QER) algorithm [27], inspired by quantum computing, adaptively selects training data from the experience replay buffer based on the complexity of each data sample and the number of replays, striking a balance between exploration and exploitation. The training data are represented in a quantum form and decayed over time, considering the relationship between temporal difference error and the importance of training data to ensure diverse selection of the training dataset. Kong et al. introduced a semi-normal sampling probability window in their work [28] to effectively balance the significance and novelty of sampled data. To expedite learning speed and improve performance while alleviating performance degradation during training, they prioritize more recent training data by assigning higher sampling probabilities to it. Ramicic et al. [29] utilize unsupervised learning techniques to categorize and sample training data into different context memory buffers, further reducing the correlation between training data samples. With the continuous development of deep reinforcement learning algorithms, various mechanisms have emerged to guide the exploration of intelligent agents. Researchers worldwide have recognized the essence of exploration algorithms in deep reinforcement learning, which is to obtain as much information as possible while minimizing the search effort. Agrawal et al. [26] proposed a backward sampling algorithm combined with an optimistic optimization mechanism, providing a higher performance lower bound for solving optimal policies. The temporal difference ϵ-greedy algorithm [30] expands a single action into action sequences in the temporal dimension, replacing randomly selected actions in the ϵ-greedy algorithm. This algorithm improves the likelihood of convergence to global optima while retaining the simplicity of the ϵ-greedy algorithm. Amin et al. [31] combined the policy exploration process with the exploration trajectory data of the agent, generating trajectory data with local back-off properties in the state space, thus improving exploration efficiency and avoiding convergence to local optima. Jinnai et al. [32] used the deep coverage option method to autonomously discover task-agnostic options that encourage exploration, enhancing the exploration effectiveness of the intelligent agent and significantly reducing the time required for the agent to explore the entire state space. The active exploration method based on Bayesian models [33] utilizes the novelty of the probability transition distribution as a learning signal, applicable to both discrete and continuous environments. It calculates the Jensen–Shannon (JS) divergence and Jensen–Rényi (JR) divergence in prediction spaces of discrete and continuous environments, respectively. The agent only needs to maximize novelty measurements during the exploration process to make reasonable exploration behaviors. The widely employed exploration strategy at present is the ϵ-greedy method. In this approach, during each decision-making process, there is a probability of 1-ϵ that the optimal action is selected based on the current policy, while there is a probability of ϵ that a non-optimal action is selected. This method addresses the trade-off between exploration and exploitation. Despite its simplicity, it is still widely used as an exploration strategy in some advanced reinforcement learning models. However, its performance is still subpar. The ϵ-greedy mechanism introduces some randomness in the action selection process, which can partially address the problem. However, it still fails to account for the uncertainty of the states. Traditional deep reinforcement learning algorithms commonly use uniform sampling from the experience replay pool to extract training data, sampling data in equal proportions. However, this method treats all data with equal importance, which is clearly different from the actual situation. Researchers have proposed mechanisms such as Emphasizing Recent Experience (ERE) [34] and Prioritized Experience Replay (PER) [35] to address this issue. However, these methods all have their respective limitations and may struggle to adapt to increasingly complex demands in the current scenario. This is because the probability of sampling a sample from the replay buffer is proportional to its storage priority, which is determined by its TD error, i.e., the difference between values when the sample was last involved in training. While the PER (Prioritized Experience Replay) algorithm improves the utilization efficiency of samples to some extent, in a replay buffer with a large number of samples, only a small fraction of samples can participate in the Q network update at each time step, while the remaining samples cannot be used for training. These samples have TD errors that do not change with the updates of the Q network, leading to the storage priority of samples not accurately reflecting the true distribution of TD errors in the replay buffer. 3. Method 3.1. Background 3.1.1. Reinforcement Learning Reinforcement learning (RL) algorithms can be characterized as operating within the framework of Markov Decision Processes (MDPs). A Markov Decision Process (MDP) is defined as a tuple S,A,P,R,γ. Here, S represents the state space of the environment, A represents the set of possible actions in the environment, and P:S×A×S→[0,1] is the transition probability matrix. This matrix provides the probabilities of transitioning from one state st to another state st+1 when taking action at. The function R:S×A→R defines the reward obtained from taking a certain action in a specific state. Lastly, the discount factor γ∈[0,1] determines the relative importance of future rewards compared to immediate rewards. In a given environment, the agent receives a state st∈S at each time step t. The agent chooses an action at from the set of possible actions A based on the policy π:S×A→[0,1]. After taking the chosen action, the given environment generates a new state st+1∈S based on the transition function P. Then, the reward function R generates a reward rt and sends it to the agent. This process is illustrated in Figure 1. RL is a process of learning how to map environmental states to agent actions in order to maximize accumulated rewards [1]. The agent perceives the state of the environment, and then, using its own policy and the observed information, chooses and carries out an action. This action causes a transition in the environment’s state, and the environment provides rewards or penalties to the agent based on the action. The agent repeats this process until a predetermined terminal state is reached, concluding an iteration of the episode. Relationships among the basic elements of reinforcement learning. In RL, there are behavior policies and target policies. The behavior policy is the strategy the agent uses to select actions during the interaction with the environment, i.e., the policy used during the agent’s training process. The target policy refers to the action selection strategy adopted by the agent during the learning and optimization process using the experiences generated by the behavior policy. RL algorithms can be categorized into on-policy and off-policy algorithms based on whether the behavior policy and the target policy are the same. 3.1.2. Priority Experience Replay In order to eliminate the correlation between experiences, the experiences used for training in DQN satisfy the property of independent and identical distribution. DQN introduced the experience replay mechanism and designed an experience pool to store and manage experiences. During the training process, random sampling is used to select batches of experiences from the experience pool to renew parameters. This allows for the effective utilization of past experiences and further enhances the performance. Prioritized Experience Replay is an effective method for estimating the priority of every sample. The samples are then selected and trained on the Q network based on their priority. The priority of a sample is controlled by its TD error. The larger the absolute value of the TD error of a sample, the larger the loss it causes in training the Q network, indicating that the sample provides more significant information. Introducing randomness on the basis of priority during sampling is important. Sampling purely based on priority can decrease the diversity of the samples. Hence, in the PER algorithm, randomness is introduced to sample the experiences with probabilities proportional to their priorities, ensuring every sample has a chance to be selected. Additionally, the introduction of priorities changes the sample distribution compared to uniform sampling and introduces bias. The PER algorithm compensates for this bias by using importance sampling weights to adjust the gradient. During the calculation of the loss function gradient, the original gradient is multiplied by the importance sampling weights to update the parameters based on the compensated gradient. The PER algorithm offers great flexibility and can be widely combined with off-policy deep reinforcement learning methods. 3.1.3. Z-Score The z-score is a process of taking the difference between a number and the mean and then dividing it by the standard deviation. The z-score helps answer the question: “How many standard deviations is a given score away from the mean?” A score above the mean will have a positive z-score, and vice versa. The z-score is a technique used to determine the relative position of a particular score within a distribution. By transforming the original scores of normally distributed data into z-scores, we can use a table of areas under the normal curve to determine the area between the mean and the z-score, indicating the percentile rank of the original score in the dataset. The sum of the squares of all z-scores in a sequence is equivalent to the total number of data points in that sequence. Additionally, the z-scores have a standard deviation and variance of 1, along with a mean of 0. z-score indicates how far the score is from the mean and helps determine the position of the data point relative to the entire dataset. This process is called standardization. The formula for the transformation is as follows: where X is the original data point to be standardized, μ is the mean value, and σ is the standard deviation value. From the calculation of the z-score, it can be observed that the relationship between the original data and the mean is preserved, with the z-score of the mean equaling 0. Positive values indicate that the z-score is above the mean, while negative values indicate that it is below the mean. Furthermore, the magnitude of the difference between any original data point and the mean determines its position. Therefore, the z-score can represent both the relative size compared to other values and the position of a value. In statistics, the z-score is a critical indicator, and when the distribution of the original scores follows a normal distribution, converting all the original scores into z-scores results in a standard normal distribution. 3.2. Proposed Method The problem with the PER algorithm is that the TD error values are not updated as promptly as the Q network; thus, it is unable to accurately reflect the priority of the samples. In each iteration, the Q network updates its own parameters, while the experience replay buffer only updates the TD error values of the batch samples involved in training, which account for only a portion of the experience replay buffer’s capacity. This results in an inability of the TD error stored for the majority of the samples to accurately reflect the priority of the sample within the overall dataset. This further leads to a discrepancy between the storage priority and the actual distribution of the samples. This paper analyzes the impact of this deviation on learning and discusses how selecting samples based on the priority generated by the true or approximate TD error distribution can enable deep networks to converge to the optimal policy with higher efficiency. This paper proposes a TD error-based z-score model to correct the storage priority of samples. By using the adjusted priority distribution for active sampling, the utilization efficiency can be improved. Figure 1 illustrates the overall structure of our approach, which mainly consists of the “bias model” and “priority correction” components. The priority correction needs to be performed at every time step, while the bias model is updated once every few time steps. The overview is shown in Figure 2. Overview. Experience replay buffer is a memory system used in reinforcement learning to store and reuse past experiences. By sampling random past experiences during training, it helps break the correlation between consecutive samples, leading to more stable and efficient learning. In the PER algorithm, the experience replay buffer is represented as a collection of samples E=e1,e2,⋯,em, where each sample ek=(sk,ak,rk,sk+1) is a tuple. The index of the sample ek in E is denoted as k, i.e., ek∈E. In each iteration, the PER algorithm selects one batch sample from E for training. In this paper, the TD error value of a sample e from its last participation in training is referred to as the stored TD error and denoted as δe. Let the current time step be t, and the time step of e last participation in training be te; then, δe is calculated using Equation (2). where θt−τ(i) and θt−τ(i)− are the parameters of the Q network and target network, respectively. From the equation above, it can be observed that the parameter θ used in the calculation of the stored TD error is not a current parameter of the Q network but a parameter from a previous time step. Within z time steps, the Q network undergoes ρ iterations of parameter updates, while the stored TD error values remain unchanged. This results in a mismatch between the stored TD error of the samples and the current Q network, with a larger ρ leading to a higher degree of mismatch. When new samples are added to the experience replay buffer, for every time step participated in training, the priority of the corresponding sample is set to 1, and for samples that did not participate in training in that time step, the priority is incremented by 1. Since new samples overwrite old ones once the experience replay buffer is full, the values of all the samples range from 1 to the total number of samples in the buffer. Samples with higher values in the experience replay buffer have not been involved in training for a long time and their TD error values have not been updated periodically. Therefore, the stored priority is highly mismatched with the current Q network. Introducing an ideal calculation method for the TD error, referred to as the “true” TD error, denoted as δ, requires calculating the distribution of δ by feeding stored samples into both the Q network and the target Q network. This involves updating the TD error values of these samples, including those that participated in the previous training session. In this calculation method, the TD error of any sample is computed using the most recent parameters of the Q network and the target Q network. This is represented by Equation (3). where θ and θ− are parameters of the Q network and the target Q network, respectively. Let p(i) and preal(i) represent the stored priority and true priority of a sample, respectively, corresponding to the stored TD error value δ and the true TD error value δreal. They are calculated using Equations (4) and (5). where ϵ and α are both constant values. The distribution of δ cannot accurately reflect the true state. When δ is large, the probability of δ sample being selected is high, and the value of z is small, meaning that the Q network does not change significantly during this period and the priority deviation is small. In such cases, the stored priority can be used as an approximate estimate of the true priority. However, when δ is small, the value of z is large, and the Q network undergoes significant parameter changes over z time steps, resulting in a deviation between the stored priority and the true priority distribution. In this situation, relying solely on the stored priority based on δ cannot accurately reflect the state of the experience replay buffer. Although preal(i) is a more ideal distribution of priorities, it can only be used in small-scale problems. In large-scale reinforcement learning, calculating the distribution of pa requires feeding all the samples into the Q network and the target Q network at each time step. Due to the large number of time steps and the large capacity of the experience replay buffer, this computation incurs significant time and storage costs. This paper proposes a TD error-adaptive correction method based on the z-score method, thereby obtaining an estimation of the true priority. The paper does not directly calculate the true priority pn, but instead achieves the sampling priority that follows the updates of the Q network with minimal cost. The samples extracted from the experience replay buffer are the inputs to the z-score model. The computed results from the z-score model are the outputs of the model. In general, the lower the stored priority p of a sample, the higher the priority deviation. To make the model more generalizable across different environments and training stages, the definition of the stored priority is modified based on Equation (4). The stored priority is normalized using the maximum value of the sample priorities and denoted as pnew. The calculation method of pnew is as follows. The replay period of a sample is represented by the number of time steps since its last participation in training. The distribution of the replay period is inverted. As training progresses, samples are continuously added to the buffer. New samples and recently trained samples have a replay period of z=1. The values of all the samples range from 1 to the total number of samples in the buffer, since all samples fall within the range of the buffer’s capacity. Similarly, using the maximum value of the entire set of samples, the corresponding replay period is defined as τ and denoted as τnew. Assuming that the algorithm updates the old sample at each time step and the batch size is the same as the parameters of the original Q network update, this is equivalent to performing an additional forward inference of the Q network at each step. The calculation of z-score only involves the calculation of mean and variance, and the complexity of the calculation process is negligible compared with Q network reasoning. Through complexity analysis, the proposed z-score PER algorithm in this paper can correct the stored priority in each iteration of the Q network with minimal time and space costs. The corrected priority is then used to select samples. The pseudo-code corresponding to the algorithm is shown in Algorithm 1. Algorithm 1 z-score experience replay algorithm.Require: Minibatch k, step-size η, replay period K and size N, exponents α and β, and budget T. 1:Initialize replay memory H=∅, p1=1 2:Observe S0 and choose A0∼πθ(S0) 3:for t=1 to T do 4: Choose action At∼πθ(St) and observe St,Rt,γt 5: Store transition (St−1,At−1,Rt,γt,St) in H with maximal priority pt=maxi