# Self-Adaptive Priority Correction for Prioritized Experience Replay
## 3 Proposed Approach  
### Preliminary  
The goal of Reinforcement Learning (RL) is to maximize the cumulative reward of sequential decision tasks. The task is always modeled as a Markov Decision Process (MDP) problem, which is represented by a 5-tuple \((S,A,P,R,\gamma)\). In the 5-tuple, \(S\) represents the state space, \(A\) represents the action space, \(P\) is the state transition function, \(P:S\times A\to S\), \(R\) is the reward function, \(R:S\times A\times S\rightarrow\mathbb{R}\), and \(\gamma\) is the discount factor, \(\gamma\in(0,1)\). The cumulative reward is \(G=\sum_{t=0}^{\infty}\gamma^{t}r_{t}\)where \(r_{t}\) represents the reward at current state. DQN will update the neural network weight \(\theta_{t}\) through Equation (1).  
\[\boldsymbol{\theta_{t+1}}=\boldsymbol{\theta_{t}}+\eta(y-Q(s_{t},a_{t}; \boldsymbol{\theta_{t}}))\
abla_{\theta}Q(s_{t},a_{t};\boldsymbol{\theta_{t}}) \tag{1}\]  
where \(\eta\) is the learning rate and \(y\) is the target Q value.  
\[y=r_{t}+\gamma Q(s_{t+1},argmax_{a^{\prime}}Q(s_{t+1},a^{\prime};\boldsymbol{ \theta_{t}});\boldsymbol{\theta_{t}}) \tag{2}\]  
In this work, we use an improved DQN named Double DQN (DDQN) [22] and DDPG [12]. In DDQN, the definition of target value \(y\) shown in Equation (3), which solves the over-optimistic value estimation problem. The same idea is used in DDPG. However, the DDPG uses a policy network to output actions.  
\[y=r_{t}+\gamma Q(s_{t+1},argmax_{a^{\prime}}Q(s_{t+1},a^{\prime};\boldsymbol{ \theta_{t}});\boldsymbol{\theta^{-}}) \tag{3}\]  
From the above definition, we know that the value-based RL algorithm initially minimizes the TD error, which is defined as \(\delta=Q(s_{t},a_{t};\boldsymbol{\theta_{t}})-y\). In other words, \(\delta\) represents how surprising the sample is [37]. DeepMind used the TD-error \(\delta\) to define the priorities of samples in PER. For each data in EM, the stored probability of sampling \(p(x)\) is defined by Equation (4) [9].  
\[p(i)=\frac{p_{i}^{\alpha}}{\sum_{k}p_{k}^{\alpha}} \tag{4}\]  
where \(p_{i}=|\delta_{i}|+\epsilon\) is the stored priorities of data \(i\) and \(|\delta_{i}|\) are the stored TD-errors. The parameter \(\alpha\) represents how much prioritization is used. However, priority experience replay can introduce bias into the evaluation of loss functions. To anneal the bias, PER uses importance sampling weights Equation (5).  
\[v_{i}=\left(\frac{1}{N}\cdot\frac{1}{p(i)}\right)^{\beta} \tag{5}\]  
where \(\beta\) controls the correct strength. To reduce training fluctuations, \(v\) is usually normalized by \(1/max_{i}v_{i}\). Therefore, the final loss function of DDQN or DDPG is defined by Equation (6).  
\[loss(\boldsymbol{\theta})=E_{x\sim p(x)}\left[\left(\frac{p(x)}{min_{i}p(i)} \right)^{-\beta}(Q(x\boldsymbol{\theta})-y)^{2}\right] \tag{6}\]  
In this work, we define the real priority of data \(i\) as \(q_{i}=|\tilde{\delta_{i}}|+\epsilon\), where the \(\tilde{\delta_{i}}\) is estimated by real-time Q value function. The real sampling probability distribution is \(q(i)=q_{i}^{\alpha}/\sum_{k}q_{k}^{\alpha}\). Figure 1 shows the probability distribution of real and stored priorities. The data are sorted from small to large according to their stored priorities. The difference in priorities is obvious.  
We also train a DQN on two simple tasks--Cartpole and Mountain-car--based on different priorities. We use a 3-layers fully-connected neural network to represent the Q function. The result is illustrated in Figure 2, where the x-axis represents episodes and the y-axis represents the corresponding score. It can be noticed that DQN with real priority has higher efficiency.  
However, it is costly to obtain real priority when training with big neural networks on complex tasks. Our problem is very clear: how to estimate the value of the DDQN or DDPG's loss function for the real distribution without increasing the computational cost.