# Self-Adaptive Priority Correction for Prioritized Experience Replay
## 4 Experiments
### Performance Comparison
#### 4.2.2 Time Cost Analysis  
Before comparing the data utilization, we analyze the time cost in each algorithm. All-time measurements are done under the same server configuration. In each iteration, there are three main processes here. The first one is the sample, which needs to search on the sum-tree. When the capacity  
\begin{table}
\begin{tabular}{l c c c} \hline \hline
**Methods** & \(\mathbf{0-2(\hat{e^{\prime}})}\) & \(\mathbf{2-4(\hat{e^{\prime}})}\) & \(\mathbf{4-6(\hat{e^{\prime}})}\) \\ \hline ATDC-PER & 76 & 54 & 48 \\ Imp-PER & **6** & **3** & **0.7** \\ \hline \hline \end{tabular}
\end{table}
Table 3: The MAPE of each method on game Pong. Each cell represents the mean value of the corresponding period. Bold font shows the best performance.  
Figure 10: The accuracy of predicted TD-error’s sum on game BeamRider and Pong. The coral, green, and blue curves represent real, before fix model, and after fix model, respectively.  
of EM goes larger, the sampling time, whose time complexity is \(O(logN)\), becomes a bottleneck. The second one is PER update, which is the same time complexity as sampling. The last one is the DDQN or DDPG update, which is executed on GPU. As we mentioned before, it is costly to correct all priorities by using current DDQN or DDPG. We measure the time cost to correct all priorities of EM (capacity is \(10^{6}\)). All data must be predicted by DDQN on GPU, it needs 150+ s. We can see that the update cost is very high.  
The time cost is shown in Table 4. The second column shows the total time cost at each iteration. ATDC-PER will spend \(10\times\) time compare to Org-PER. In the third column, we can see ATDC-PER needs more time to correct the priorities. However, our method only spends a little more time. Because we do not need to correct the priorities of all data in EM. On the other hand, the time to update PER is the same, which is only updates the priorities of the current mini-batch of data. In the last column, our algorithm Imp-PER spend a little more time to update DDQN or DDPG. This extra time is used to calculate the importance weights. Except for these times, our method and ATDC-PER both need to train the priority prediction model. The time cost of ATDC-PER is \(160+\) s, while Imp-PER spends about \(20\) s. To further reduce training time, the prediction model is trained per \(10^{5}\) steps. Therefore, the time cost of the prediction model is ignored. However, the total time also contains some small processing, including the cost of eliminating outliers and so on.  
Although ATDC-PER can effectively improve data utilization, its execution time is too long to make it widely used. Our algorithm Imp-PER could effectively improve data utilization without significant additional time overhead. From the time analysis, Imp-PER is only 10% slower than Org-PER. Compared with the improved data utilization and the improved policy quality, this time cost is completely acceptable. Specifically, data utilization and policy quality improvement refer to using the same data to get a higher score (policy quality). In subsection X and subsection Y, we made a detailed comparison of related indicators of data utilization and policy quality. In general, Imp-PER uses about 10% more training time, and gets about 30% improvement in data utilization and 15% (atari) and 51% (mujoco) final policy quality improvements, making the PER technology more effective and practical. The next section provides more analysis details.