Attention Loss Adjusted Prioritized Experience Replay

A Markov model with five key elements $\langle S,A,S^{\prime},r,\gamma\rangle$ is defined to describe the interaction process between the agent and environment. Among them, the state $S$ represents the possibility configuration of the agent, while vector $A$ denotes the action space. At each time step $t$, the agent follows the strategy $\pi_{\theta}$ to select the action $A_{t}$, and obtains the next state $S^{\prime}$ according to the state transition equation. In this process, the agent received immediate reward $r_{t}$ according to a function of its action and state. We call the process of environment from the initial state to the terminated state as a trajectory $\zeta$, and the agent’s goal is to maximize the expected return $R=\sum_{t=0}^{T}\gamma_{t}r_{t}$ to continuously optimize $\zeta$, where $\gamma$ and $T$ represent the discount factor and time horizon, respectively.

PER applys a non-uniform sampling strategy, which adjusts the sampled frequency of experience transitions depending on the magnitude of TD-error $\left|\delta\right|$. It has two improvements in comparison with the uniform sampling experience replay [30]. Firstly, PER assigns each experience sample $i$ with a sampling probability proportional to its TD error, and improves the training efficiency by learning important experience samples more frequently as follow:

In the formular (1), $p_{i}=\left|\delta(i)\right|+\epsilon$ is the priority of transition $i$. The hyperparameter $\alpha$ is used to smooth out extremes, and a minimal positive constant value $\epsilon$ makes sure that the sampled probability is greater than 0, which gives all transitions a chance to be selected.

Secondly, it introduces importance sampling weight ratios $\bar{w}(i)$ to correct the estimation deviation caused by shifted state-action distribution:

Note that $\bar{w}(i)\delta(i)$ will be used instead of $\delta(i)$ when updating formular (3). The hyperparameter $\beta$ increases linearly from $\beta_{0}$ to 1 along the training process.

The linear annealing of importance weight in PER cannot completely eliminate the deviation, and the sensitivity to outliers is easy to further magnify the deviation. Fujimoto et al. [14] proposed an LAP algorithm, which uses the segemental loss function

combined with priority clipping scheme to further reduce the deviation:

By combining (4) and (5), it can be seen that when the absolute value of TD error is less than and equal to 1, MSE is applied as the loss function according to (4), and the priority of transition $i$ is cut up to 1, so that the uniform sampling is performed for each transition $i$ with a sampled probability of $\frac{1}{N}$ according to (5). Similarly, if the TD error is greater than 1, MAE is used to suppress the sensitivity to outliers in (4), and the non-uniform sampling is performed according to (5). Although LAP avoids the interference of outliers on training, the uniform sampling part decreases the training speed. In addition, MAE can only suppress the sensitivity to outliers, but cannot correct the shifted distribution, and the deviation does exist. Saglam et al. [15] proposed an LA3P algorithm based on LAP, using inverse sampling to select samples with small TD error to train the network, which avoids the uncertainty caused by large TD error transition, but does not meet the requirement on sample knowledge of PER.

In PER and its improved algorithms, the hyperparameter $\beta$ is an important index to regulate the importance sampling weight (IS), which determines the correction strength of the algorithm with respect to error caused by PER. $\beta$ is positively correlated with the training progress and reaches 1 to fully compensate for esitmation error as the training ends. The PER uses the linear annealing method to make $\beta$ increase linearly with the training episodes. However, the training progress is not uniformly distributed over the scale of episodes number, and the way of linear parameter tuning may exacerbate the error. Note that the size of $\beta$ depends on the specific progress of the training; in order to quantify the training progress, we build an improved Self-Attention network to measure the training progress by calculating the similarity of sample distribution in the experience pool. At the beginning of training, the transitions in experience pool generated by the stochastic exploration of agent is random and uniform. As the training proceeds, the agent will make more use of the current optimal strategy to select high-return actions, that is to say, given a state, the action selected by the agent will be roughly the same, and the similarity of transitions sequence generated by the interaction between agent and environment will be improved. We input the mini-batch sized state-action pair sequences $X=[(S_{1},A_{1}),(S_{2},A_{2}),...,(S_{m},A_{m})]$ into the Self-Attention network, whose output is the quantized value of the sample similarity in experience pool, and $\beta$ is obtained after normalization.

The attention function can usually be described as a nonlinear fitting network that maps a query and a set of key-value pairs to the output [31, 32]. Its output is essentially a weighted sum containing importance weights. In practice, we package queries, keys and values into the corresponding matrices Q, K and V, and the output of attention value is calculated as follows:

where $d_{k}$ is the dimension of queries and keys vectors, dividing the dot-product $Q\cdot K^{T}$ by $\sqrt{d_{k}}$ to prevent the gradient from disappearing.

In order to meet the needs of similarity calculation on internal elements of the input sequence, this paper optimizes the Self-Attention network properly and removes the value vector, and the attention module only outputs the similarity of key-query pairs. Considering that X is a list constructed of m state-action pair vectors, referring to the physical meaning of vector projection, we measure the similarity between $Q$ and $K$ by the sum of the projections among the corresponding vectors, where $Q=XW_{Q}$, $K=shuffle(Q)$, and both of them maintain dimensions consistent with X; $W_{Q}$ represents the initial weight matrix of $Q$. Since the similarity is calculated for the internal elements of $X$, we need to do projection operation after randomly rearranging the order of the elements (by shuffle operation) in $Q$ for each $q_{i}$ and $k_{i}$. The process for improved Self-Attention network to calculate the attention value is shown as follows:

where $\bullet$ stands for projection sum operation of the corresponding elements between $Q$ and $K$. The input of the Self-Attention module is the state-action pair sequence, and the output attention value represents the similarity of the elements in $X$. After passing through the fully connection layer, the attention value is normalized by the activation function to obtain $\beta$. The schematic diagram of Self-Attention mechanism is shown in Fig. 1. Note that the schematic diagram in this paper only depicts the network structure of ALAP under A-C framework, and the combination of ALAP with the algorithm based on value-function is similar and it is omitted here.

We can see that the Attention network’s input is a mini-batch sized sequence of experience transitions provided by PS in Fig.1. However, PS exploits the fixed standard to screen out samples, thus its sample distribution cannot restore the real situation in experience pool, which inspires us to design the Double-Sampling mechanism.

The core idea of ALAP is to quantitatively describe the training progress by calculating the similarity of the sample distribution in experience pool through the attention module. Therefore, the sample distribution from data source of the attention module should be consistent with the sample distribution in experience pool. However, the priority based sampling way artificially changes sample’s visited frequency, so that the data source obtained by PS cannot reflect the real situation of data distribution in whole experience pool. Hence, we need to rely on random uniform sampling to provide data input for the attention module. In addition, the model network still needs PS to provide high-quality training samples. To sum up, we propose a parallel sampling method called Double-Sampling mechanism, which covers both PS and RUS. For ease of description, we define the data source acquired by PS as $s$ and the data source obtained by RUS as $s^{*}$.

In the training process, the priority based sampling provides data samples for training model, and the uniform sampling is only responsible for providing data as input for attention module to fit $\beta$, which can correct the estimation error in real time. The key point of the Double-Sampling mechanism is not to interfere with the normal operation of training, and to collect data in the same experience pool $D$ using both sampling procedures simultaneously. Since the two sampling procedures are done simultaneously, even though the sampled batchsize is much smaller than the volume of the experience pool $D$, there is still a certain probability that the same sample will be selected for both sampling methods, resulting in instability of the algorithm. As a result, we propose a concept of mirror buffer $D^{*}$ and construct a mirror experience pool with the same data distribution as the original one. At each iteration step, the mirror buffer $D^{*}$ adds and updates experience samples at the same time as the original experience pool $D$ to keep the data synchronized.

It is worth noting that, although from the physical level, the two sampling steps are carried out in two different buffers, but from the data level, they are actually operated in the same experience pool. The schematic diagram of Double-Sampling mechanism is shown in Fig.2.

Finally, in order to reduce the sensitivity of the algorithm to outliers, ALAP follows the Huber loss function applied in LAP and LA3P; unlike them, we remove the sample priority clipping part and use PER-sampled data to train the model throughout the whole process to ensure unbiased Q-value function estimation without sacrificing training speed. The overall operation flow of ALAP is shown in Algorithm 1.

The environment cartpole-v0 is utilized to test all the algorithms. In the comparison experiments, all algorithms execute different sampling manners to draw mini-batch samples from the corresponding experience pool of volume $2\times 10^{4}$ for training the model, which is consturcted by 3-layer ReLU MLP with 24 units per layer. During the training, the agent chooses the action based on the $\epsilon-greedy$ strategy, the decay rate of $\epsilon$ is 0.0002, and a non-zero lower bound $\epsilon\geq$ 0.0001 is set to maintain the exploration ability of the agent. The total training episodes and the maximum simulation steps of each episode are both 200. The Adam optimizer is used to optimize the network parameters with a learning rate of 0.001 and a discount factor of 0.99. In cartpole-v0, the cartpole keeps the inverted pendulum upright through the left and right displacement, and any behavior of the agent, including the termination action, can be rewarded with a return value of 1. Since the maximum step per episode is 200, the maximum bonus the cart can get is 200 as well.

To avoid unintentional outcomes, we investigate the effectiveness of ALAP against other algorithms under batchsize=32, 64, 128, and we ran each case 20 times.

Fig.3 shows the average reward comparison curves between ALAP + DQN, LAP + DQN, PER + DQN and DQN. To compare the algorithm variance and stability, we set a 50$\%$ confidence interval, and drew the confidence bands of each curve, which is also applied in other two environments. It is clearly that the ALAP algorithm outperforms others in terms of training speed and average reward. The ALAP algorithm achieves steady state much faster and has a greater reward value. In terms of stability, the ALAP algorithm has a narrower confidence band during the whole training phase, indicating that it can efficiently minimize variation and is more resilient to outliers. The LAP algorithm is slightly inferior to ALAP in terms of convergence speed and quality because LAP partially utilizes uniformly sampled data to train the model at the expense of training speed, but it still provides some suppression to outliers. PER does have an improvement in convergence speed and reward peaks compared to DQN, but it has a large variance in the training process.

The scene simple is applied to evaluate the algorithms. Both original and mirror buffers are set with volume of $10^{6}$ to provide transitions for different sampling methods. The network model contains 2-layer ReLU MLP, with 64 neurons in each hidden layer. The total number of training episodes is 2000, the maximum simulation step is 25, the learning rate is 0.001, and the discount factor is 0.95. In this environment, there is just one agent and one obstacle, and the agent’s reward depends inversely on how far away from the obstruction it is. We still trained 20 times under each batchsize to collect the comparison results.

Fig.4 shows the average reward curves of ALAP + DDPG, LAP + DDPG, PER + DDPG, and the conventional DDPG. It demonstrates that ALAP has the best performance with respect to convergence speed and training variance in the face of different batchsize configurations. PER performs poorly under A-C framework, converging slower than baseline when the mini-batch is too large or too small, and PER consistently has the largest variance throughout the training process that shows the extremely instability. Compared with PER, the training variance of LAP is alleviated, but its convergence speed is not significantly improved. Overall, ALAP solves the problem of the degraded performance of PER when embedded in the A-C framework.

The classical environment for Multi-to-Multi pursuit evasion game simple$\_$tag is used to test all the algorithms. In simple$\_$tag, both the pursuers and the evaders empoly a zero-sum reward structure, where the reward of the pursuers is inversely proportional to their relative distance from the evaders, while the evaders are rewarded in the opposite way. To visually compare the algorithms’ strengths and weaknesses; we use MADDPG as a baseline to train evaders, while we train the pursuers with the improved algorithm simultaneously, and record their average reward. During training, we trace the model structure and hyperparameter configurations of simple, each agent follows the parameterized policy $\pi_{i}$, and 20 comparative tests were completed under each batchsize.

Fig.5 shows the average reward curves of ALAP + MADDPG, LAP + MADDPG, PER + MADDPG, and MADDPG under different batchsize configurations. From Fig.5, we can see that under any mini-batch condition, the convergence speed and the average reward of ALAP are much higher than those of other algorithms. Although the stability of LAP decreases after mini-bach $\geq$ 64, its average reward and convergence speed are still higher than those of PER and MADDPG. The performance of PER is even worse than that of baseline after mini-batch $\geq$ 64, and the huge variance in the early stage of training is the reason that restricts the quality of its training.