Prioritized Replay

Definition

Prioritized replay is an enhancement to the standard experience replay. Instead of uniformly sampling experiences from the replay buffer, prioritized replay samples important transitions more frequently based on their priority values. It makes it possible to learn more efficiently as the agent focuses on important experiences more.

The priority of transition $i$ is calculated by TD Error. $p_i=|{\delta }_i|+ϵ$ where $\delta$ is the TD Error, and $ϵ\in {\mathbb{R}}^{+}$.

The probability of sampling transition $i$ is $P(i)=\frac{p_i^{\alpha }}{{\sum }_k{p}_k^{\alpha }}$ where $\alpha$ controls how much prioritization is used (uniform sampling if $\alpha =0$).

However, it can lead to a loss of diversity and introduce bias, but these issues can be alleviated and corrected with stochastic sampling prioritization (using $\alpha$) and Importance Sampling weights.

The Importance Sampling weights are calculated as $w_i={\left(\frac{1}{N}\cdot \frac{1}{P(i)}\right)}^{\beta }$ where

• $N$ is the size of the replay buffer
• $\beta \in [0,1]$ is annealing parameter that fully compensates the bias when $\beta =1$. It starts from $0$ and ends with $1$.

The wight $w_i$ is normalized by $\frac{1}{\underset{k}{\max }{w}_k}$ before used for stability.

Algorithm

Double DQN with Prioritized Replay

1. Initialize behavior network $Q$ and target network $\hat{Q}$ with random weights $\theta$, and the replay buffer $\mathcal{R}$ to max size $N$.
2. Repeat for each episode:
   1. Initialize sequence $s_0$.
   2. Repeat for each step of an episode until terminal, $t=0,1,\dots ,T-1$ :
      1. With probability $ϵ$, select a random action $a_t$ otherwise select $a_t=\underset{a}{\mathrm{argmax}}Q(s_t,a;\theta )$.
      2. Take the action $a_t$ and observe a reward $r_{t+1}$ and a next state $s_{t+1}$.
      3. Store transition $(s_t,a_t,r_{t+1},s_{t+1})$ in the replay buffer $\mathcal{R}$ with maximal priority $p_t=\underset{i<t}{\max }{p}_i$.
      4. For every $K$ (replay period) steps:
         1. Sample random minibatch of $B$ transitions $(s_i,a_i,r_{i+1},s_{i+1})\sim P(i)=\frac{p_i^{\alpha }}{{\sum }_k{p}_k^{\alpha }}$ from $\mathcal{R}$.
         2. Compute the importance weight $w_i=\frac{(NP(i){)}^{-\beta }}{\underset{k}{\max }{w}_k}$
         3. Compute TD Error ${\delta }_t=r_{i+1}+\gamma \hat{Q}(s_{i+1},\underset{a}{\mathrm{argmax}}Q(s_{i+1},a;\theta );\hat{\theta })-Q(s_i,a_i;\theta )$
         4. Update transition priority $p_i\leftarrow |{\delta }_i|+ϵ$
         5. Accumulate weight-change $\Delta \leftarrow \Delta +w_i{\delta }_i{\nabla }_{\theta }Q(s_i,a_i;\theta )$
      5. Update behavior network weights $\theta \leftarrow \theta +\eta \Delta$ and reset $\Delta =0$
      6. Update the target network parameter $\hat{\theta }\leftarrow \theta$ every $C$ steps.
      7. Update $s_t\leftarrow s_{t+1}$.