# Self-Adaptive Priority Correction for Prioritized Experience Replay
## 3 Proposed Approach
### Algorithm Description  
Algorithm 1 shows the whole training process of Double DQN with Imp-PER. In our preliminary experiments, we find it is unnecessary to update the linear model at each iteration. We train the linear model every \(K\) steps. Lines 6-9 show the linear model training process. The most costly step  
Figure 7: The Mean Absolute Percentage Error (MAPE) of uniform, stored, and importance sampling. Each experiment runs 1000 times. The red, green, and blue curves represent imp, store, and uniform, respectively.  
is to calculate the real priority of each data (line 8), which needs to sweep the whole EM by DDQN. The parameter \(K\) has little effect on the accuracy of the model prediction. In our experiments, \(K\) is set to \(10^{5}\), which greatly reduces the time overhead of training the linear model. Lines 17-25 are the main process of Imp-PER. First, we sample a mini-batch of data. The data \(j\) is sampled according to probability \(p(j)\) (line 18), which is the stored priority. Then, real TD-error is computed by DDQN (line 19). We use the current TD-error \(\tilde{\delta}_{j}\) to update the stored priority of data \(j\) (line 20). By using the real \(\tilde{\delta}_{j}\) and predicted sum \(\tilde{z}\), we could compute the real probability \(q_{j}\) (line 21). Different from the original PER, the IS weight uses real probability \(q_{j}\) instead of stored probability \(p_{j}\) (line 22). Then, our IS weight is computed based on \(p_{j}\) and \(q_{j}\) (line 23). IS weight must be truncated by \([\tau_{min},\tau_{max}]\). The two IS weights are used to update DDQN (line 24). As we mentioned before, the DDPG algorithm has a similar training framework. DDPG + PER [12] shows the details of DDPG's implementation.  
**Input**: Linear model update period \(K\), sum predict period \(D\), budget \(T\), mini-batch size \(k\), learning rate \(\eta\), discount factor \(\gamma\), importance strength \(\beta\), exponential smoothing \(\rho\), smoothing index \(\alpha\), target network update \(L\)  
**Output**: the parameter of DDQN \(\mathbf{\theta}\)  
```
1:choose action \(a_{0}\sim\epsilon-greedyQ(s_{0},a;\mathbf{\theta})\)
2:for t = 1 to \(T\)do
3:execute \(a_{t-1}\) and observe \(s_{t}\), \(r_{t}\).
4: store tuple (\(s_{t-1}\), \(a_{t-1}\), \(s_{t}\), \(r_{t}\)) into EM with maximal priority \(p_{t}=max_{i<t}p_{i}\)
5:if t%K==0 then
6: calculate feature \(x^{(1)}=\sum_{i=1}^{n}(|\delta_{i}|+\epsilon)^{\alpha}\)
7: calculate feature \(x^{(2)}=\sum_{i=1}^{n}\tau_{i}\)
8: predict real TD-error \(\tilde{\delta}=Q(s_{t},a_{t};\mathbf{\theta}_{t})-y\)
9: estimate parameters \(w\) of Linear model based on Equation (8)
10:endif
11:if t%D==0 then
12: calculate feature \(x^{(1)}=\sum_{i=1}^{n}(|\delta_{i}|+\epsilon)^{\alpha}\)
13: calculate feature \(x^{(2)}=\sum_{i=1}^{n}\tau_{i}\)
14: predict sum \(z\) and minimum td-error based on Equation (7)
15: smooth sum \(\tilde{z}\) and \(min_{q}\) according to Equation (10)
16:endif
17:for j = 1 to \(k\)do
18: sample data \(j\sim p(j)\) according to Equation (4)
19: compute current TD-error \(\tilde{\delta}_{j}=Q(s_{j},a_{j};\mathbf{\theta}_{t})-y_{j}\)
20: update priority \(p_{j}\leftarrow|\tilde{\delta}_{j}|\)
21: compute real priority probability \(q_{j}(\frac{|\tilde{\delta}_{j}|+\epsilon)^{\alpha}}{\tilde{z}}\)
22: compute org IS weight \(v_{j}=\left(\frac{q_{j}}{min_{q}}\right)^{\alpha}\)
23: new IS weight \(w_{j}=clip\left(\frac{q_{j}}{|\tau_{min}},\tau_{max}\right)\)
24:\(\Delta\leftarrow\Delta+w_{j}\cdot v_{j}\cdot\tilde{\delta}_{j}\cdot\
abla_{ \theta}Q(\tilde{s}_{j};a_{j};\mathbf{\theta}_{t})\)
25:endfor
26: update weights \(\mathbf{\theta}\leftarrow\mathbf{\theta}+\eta\cdot\Delta\), reset \(\Delta=0\)
27:if t%L==0 then
28: update target Q network \(\mathbf{\theta}^{-}=\mathbf{\theta}\)
29:endif
30: choose next action \(a_{t}\sim\epsilon-greedyQ(s_{t},a;\mathbf{\theta})\)
31:endfor
```  
**Algorithm 1** Double DQN with Imp-PER.