# Self-Adaptive Priority Correction for Prioritized Experience Replay
## 3 Proposed Approach
### Real Probability Prediction  
To predict the probability \(q(i)\) of each data \(i\), it is necessary to estimate real TD-error of data \(i\) and predict the sum of all priorities in EM, \(sum=\sum_{i}q_{i}^{n}\), where the \(q_{i}\) is the TD-error of data \(i\). The real TD-error of data \(i\) can be estimated by the current DDQN, which is defined in the preliminary section. In our algorithm, we only need to calculate the real TD-error for the data that are replayed. The real TD-error can be obtained directly from the DDQN loss function, as \(|\tilde{\delta_{i}}|=|Q(x;\mathbf{\theta})-y|\). Therefore, estimating the real TD-error does not incur additional computational costs. The key problem is how to predict the sum of real TD-error in EM.  
[PERSON] et al. found that there is an approximately linear relationship between real priority and stored priority [18]. However, it is not necessary to predict the priorities of all data in EM. What we care about is the relationship between the sum of real and stored priorities in EM. Although real and stored priority distributions are different (Figure 1), their sums are strongly correlated and change slowly over time, which is shown in Figure 4a. This correlation is also easy to explain because the TD-error will not change significantly in the short term, as the DQN is trained with a sufficiently small learning rate.  
In this work, we use a simple model to predict the real sum based on stored sum. Meanwhile, the timestamps of data in EM also have a strong correlation with the sum of priorities. As a result, we use a linear model to predict the real sum of priorities. Precisely, there are two features in our model, one is the sum of stored priorities \(x^{(1)}\), which is the root of sum-tree in PER. The other one is the sum of timestamps \(x^{(2)}\). The target value is the sum of real priorities \(z\). The linear model is defined by Equation (7).  
\[\begin{split}&\hat{z}=W_{1}x^{(1)}+W_{2}x^{(2)}+W_{3}\\ & x^{(1)}=\sum_{i=1}^{n}(|\delta_{i}|+\epsilon)^{\alpha}\\ & x^{(2)}=\sum_{i=1}^{n}\tau_{i}\end{split} \tag{7}\]  
where \(W_{i}\) is the parameters of our model. To solve the linear model, we only need to minimize the Mean Square Error (MSE) defined in Equation (8).  
\[J(W)=\frac{1}{m}\sum_{i=1}^{m}{(z_{i}-\hat{z}_{i})^{2}} \tag{8}\]  
Figure 4: Using a simple linear model to predict the sum of real priorities. Based on the predicted value, we can estimate the real priority of each sample.  
where \(m\) is the size of training data and \(z_{i}\) is the real probability. Imp-PER uses the historical sum of data as training data, which is shown in Figure 4a, to fit the linear model. Based on the predicted sum \(z\) and real TD-error \(\tilde{\delta}_{i}\), it is able to estimate the predicted probability of each data in the mini-batch, \(q(i)=q_{i}^{\alpha}/z\). Figure 4b shows the predicted and real probabilities of data during training on Atari game Pong. It indicates that our method can accurately predict the real probabilities of data.  
As we mentioned in Equation (6), the original importance weights \(v\) must be normalized by \(max_{i}v_{i}\). We should estimate the minimum real value \(min_{q}\). Using the same function Equation (7), we could get the value \(min_{q}\). It is costly to calculate the \(min_{q}\) every time before estimate the loss of DDQN. The next subsection gives the solution to handle it.