QR-DQN

Definition

The Quantile-Regression DQN (QR-DQN) algorithm is a Distributional Reinforcement Learning algorithm that approximates the distribution of random return using quantile regression.

Architecture

QR-DQN estimates a set of $N$ quantiles $\{{\hat{\tau }}_i{\}}_{i=1}^N$ of return distribution, where ${\hat{\tau }}_i=\frac{2i-1}{2N}$ represents the midpoint of $i$-th quantile interval. This can be seen as adjusting the location of the supports of a uniform probability mass to approximate the desired quantile distribution.

The quantile distribution $Z$ with uniform probability $\frac{1}{N}$ is constructed as $Z(s,a)=\frac{1}{N}\sum _{i=1}^N(s,a){\delta }_{z_i(s,a)}$ where ${\delta }_x$ is a Dirac’s delta function at $x$, and $\{z_i(s,a)\}$ are the outputs of the network, representing the estimated quantile values. These values are obtained by applying the inverse CDF of the return distribution to the quantile midpoints $z_i(s,a)=F_Z^{-1}({\hat{\tau }}_i)$.

Using the estimated quantile values as a support minimizes the Wasserstein Distance between the true return distribution and the estimated distribution.

Quantile Regression

Given data set $\{x_j\}$, a $\tau$-quantile $q_{\tau }$ minimizes the loss $\sum _{j=1}^N{\rho }_{\tau }(x_j-q_{\tau })$, where ${\rho }_{\tau }(x)=x(\tau -1(x<0))$ is a quantile loss function.

The quantile values are estimated by minimizing the quantile Huber loss function. Given a transition $(s,a,r,s^{\prime })$, the loss is defined as $L(\theta )=\sum _{i=1}^N{E}_j[{\rho }_{{\hat{\tau }}_i}^{\kappa }(\mathcal{T}{z}_j-z_i(s,a))]=\frac{1}{N}\sum _{i=1}^N\sum _{j=1}^N{\rho }_{{\hat{\tau }}_i}^{\kappa }(\mathcal{T}{z}_j-z_i(s,a))$ Where:

• $\mathcal{T}{z}_j=r+\gamma z_j(s^{\prime },a^{\ast })$ and $a^{\ast }=\underset{a}{\mathrm{argmax}}Q(s^{\prime },a)$.
• ${\rho }_{\tau }^{\kappa }(x)=L_{\kappa }(x)(\tau -1(x<0))$ where $L_{\kappa }(x)$ is Huber Loss.

Algorithm

1. Initialize behavior network $Q$ and target network $\hat{Q}$ with random weights $\theta$, and the sample 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}$.
      4. Sample a random transition $(s_t,a_t,r_{t+1},s_{t+1})$ from $\mathcal{R}$.
      5. Select a greedy action $a^{\ast }=\underset{a}{\mathrm{argmax}}Q(s_{t+1},a)=\underset{a}{\mathrm{argmax}}\frac{1}{N}\sum _{i=0}^{N-1}{z}_i(s_{t+1},\alpha ;\hat{\theta })$
      6. Compute the target quantile values $\mathcal{T}{z}_j(s_{t+1},a^{\ast };\hat{\theta })=r_{t+1}+\gamma z_j(s_{t+1},a^{\ast })$.
      7. Perform Gradient Descent on the loss $L(\theta )=\sum _{i=1}^N{E}_j[{\rho }_{{\hat{\tau }}_i}^{\kappa }(\mathcal{T}{z}_j(s_{t+1},a^{\ast };\hat{\theta })-z_i(s_t,a_t;\theta ))]$.
      8. Update the target network parameter $\hat{\theta }\leftarrow \theta$ every $C$ steps.
      9. Update $s_t\leftarrow s_{t+1}$.