In reinforcement learning, experience replay stores past samples for further\nreuse. Prioritized sampling is a promising technique to better utilize these\nsamples. Previous criteria of prioritization include TD error, recentness and\ncorrective feedback, which are mostly heuristically designed. In this work, we\nstart from the regret minimization objective, and obtain an optimal\nprioritization strategy for Bellman update that can directly maximize the\nreturn of the policy. The theory suggests that data with higher hindsight TD\nerror, better on-policiness and more accurate Q value should be assigned with\nhigher weights during sampling. Thus most previous criteria only consider this\nstrategy partially. We not only provide theoretical justifications for previous\ncriteria, but also propose two new methods to compute the prioritization\nweight, namely ReMERN and ReMERT. ReMERN learns an error network, while ReMERT\nexploits the temporal ordering of states. Both methods outperform previous\nprioritized sampling algorithms in challenging RL benchmarks, including MuJoCo,\nAtari and Meta-World.\n