Smoothing Advantage Learning

The reinforcement learning problem can be modeled as a Markov Decision Processes (MDP) which described by a tuple $\left\langle\mathcal{S},\mathcal{A},P,R,\gamma\right\rangle$. $\mathcal{S}$ and $\mathcal{A}$ are the finite state space and finite action space, respectively. The function $P(s^{\prime}|s,a):\mathcal{S}\times\mathcal{A}\times\mathcal{S}\longmapsto[0,1]$ outputs the transition probability from state $s$ to state $s^{\prime}$ under action $a$. The reward on each transition is given by the function $R(s,a):\mathcal{S}\times\mathcal{A}\longmapsto\mathbb{R}$, whose maximum absolute value is $R_{max}$. $\gamma\in[0,1)$ is the discount factor for long-horizon returns. The goal is to learn a policy $\pi:\mathcal{S}\times\mathcal{A}\longmapsto[0,1]$ (satisfies $\sum_{a}\pi(a|s)=1$) for interacting with the environment. Under a given policy $\pi$, the action-value function is defined as

where $G_{t}=\sum_{i=0}^{\infty}\gamma^{i}R_{t+i}$ is the discount return. The state value function and advantage function are denoted by $V^{\pi}(s)=\mathbb{E}_{\pi}[Q^{\pi}(s,a)]$ and $A^{\pi}(s,a)=Q^{\pi}(s,a)-V^{\pi}(s)$, respectively. An optimal action state value function is $Q^{\star}(s,a)=\max_{\pi}Q^{\pi}(s,a)$ and optimal state value function is $V^{*}(s)=\max_{a}Q^{*}(s,a)$. The optimal advantage function is defined as $A^{*}(s,a)=Q^{*}(s,a)-V^{*}(s)$. Note that $Q^{*}(s,a)$ and $V^{*}(s)$ are bounded by $V_{\max}:=\frac{1}{1-\gamma}R_{\max}$. The corresponding optimal policy is defined as $\pi^{*}(a|s)=\arg\max_{a}Q^{*}(s,a)$, which selects the highest-value action in each state. For brevity, let $\|f\|=\max_{x}|f(x)|$ denote the $L_{\infty}$ norm. And for functions $f$ and $g$ with a domain $\mathcal{X}$, $f\geq(>)g$ mean $f(x)\geq(>)g(x)$ for any $x\in\mathcal{X}$.

The Bellman operator $\mathcal{T}^{\pi}$ is defined as,

It is known that $\mathcal{T}^{\pi}$ is a contraction (Sutton and Barto 1998) - that is, $Q^{\pi}(s,a):=\lim_{k\rightarrow\infty}(\mathcal{T}^{\pi})^{k}Q_{0}(s,a)$ is a unique fixed point. And, the optimal Bellman operator $\mathcal{T}$ is defined as,

It is well known (Feinberg 1996; Bellman and Dreyfus 1959; Bellman 1958) that the optimal $Q$ function $Q^{*}(s,a)=\max_{\pi}Q^{\pi}(s,a)$ is the unique solution $Q^{*}$ to the optimal Bellman equation and satisfies

$Q$-learning is a method proposed by Watkins (1989) that estimates the optimal value function $Q^{\star}$ through value iteration. Due to the simplicity of the algorithm, it has become one of the most popular reinforcement learning algorithms.

The advantage learning (AL) operator was proposed by Baird (1999) and further studied by Bellemare et al. (2016). Its operator can be defined as:

where $V(s)=\max_{a}Q(s,a)$, $\mathcal{T}$ is the optimal Bellman operator Eq.(2) and $\alpha\in[0,1)$. And its operator has very nice properties.

They proved that when there is no approximation error, the state value function $V_{k}(s)$, $V_{k}(s)=\max_{a}Q_{k}(s,a)$ during $k$-th $Q$-iteration with $\mathcal{T}_{AL}$, is convergent and equal to the optimal state value function $V^{*}(s)$ - this operator is optimal-preserving operator. And this AL operator can enhance the difference between $Q$-values for an optimal action and sub-optimal actions - this operator is gap-increasing operator, to make estimated $Q$-value functions less susceptible to function approximation/estimation error.

Recently, Kozuno et al. (Kozuno, Uchibe, and Doya 2017) proposed generalized value iteration (G-VI), a modification to the AL:

where $m_{\tau}Q(s,\cdot):=\tau\ln\langle\frac{1}{|\mathcal{A}|},\exp{\frac{Q}{\tau}}\rangle=\tau\ln\sum_{a}\frac{1}{|\mathcal{A}|}$ $\exp{\frac{Q(s,a)}{\tau}}$ is the mellowmax operator, $\alpha\in[0,1)$.

This is very close to munchausen value iteration¹¹1In M-VI, $\langle\frac{1}{|\mathcal{A}|},\exp{\frac{Q}{\tau}}\rangle$ is replaced by $\langle 1,\exp{\frac{Q}{\tau}}\rangle$ (M-VI) (Vieillard, Pietquin, and Geist 2020). Both algorithms can be derived from using entropy regularization in addition to Kullback-Leibler (KL) divergence. In fact, they can be seen as soft $Q$ operator plus a soft advantage term. But the hyperparameters $\tau$ controls the asymptotic performance - that is, the performance gap between the optimal action-value function $Q^{*}$ and $Q^{\pi_{k}}$, the control policy $\pi_{k}$ at iteration $k$, is related to $\tau$, so both algorithms may be sensitive to the hyperparameters $\tau$ (Kim et al. 2019; Gan, Zhang, and Tan 2021). When $\tau\rightarrow 0$, it retrieves advantage learning. And taking $\alpha=1$, it retrieves dynamic policy programming (DPP) (Azar, Gómez, and Kappen 2012). In addition, a variant of AL for improved exploration was studied in (Ferret, Pietquin, and Geist 2021). In Appendix, we show that G-VI and M-VI are equivalent. Meanwhile, we also give the relationship between their convergence point and AL.

We first provide the following optimal smooth Bellman operator (Fu et al. 2019; Smirnova and Dohmatob 2020) which is used to analyze the smoothing technique:

where $\omega\in(0,1)$, and $\mathcal{T}$ is the optimal Bellman operator. They proved that the unique fixed point of the optimal smooth Bellman operator is same as the optimal Bellman operator. In fact, from the operator aspect, the coefficient $\omega$ can be expanded to $(0,\frac{2}{1+\gamma})$ (See Appendix for detailed derivation). Note that if $0<\omega<1$, the uncertainty caused by maximum operator is reduced, due to the introduction of the action-value function approximation $Q(s,a)$. And the $\mathcal{T}_{\omega}$ can be thought of as a conservative operator. While $1<\omega<\frac{2}{1+\gamma}$, the uncertainty increases, and overemphasizes the bootstrapping is both aggressive and risky in estimating TD learning.

We propose a smoothing advantage learning operator (SAL), defined as:

where $V(s)=\max_{a}Q(s,a)$, $\mathcal{T}_{\omega}$ is the smooth Bellman operator Eq.(6) and $\alpha\in\mathbb{R}$.

Note that if $\omega=1$, the $\mathcal{T}_{SAL}$ operator is reduced to the advantage learning operator $\mathcal{T}_{AL}$ Eq.(3). And when $\alpha=0$, the $\mathcal{T}_{SAL}$ operator is reduced to the optimal smooth Bellman operator $\mathcal{T}_{\omega}$ Eq.(6). In practice, the TD target of the SAL operator is calculated by a estimation - the current state estimation, the bootstrapping estimate of the next state for future return and an advantage term. Considering the fragility of the prediction of neural network-based value function approximators especially when the agent steps in an unfamiliar region of the state space, the accuracy of the estimated reinforcement signal may directly affect the performance of the algorithm. By doing this, we show that it helps to enhance the network’s ability to resist environmental noise or estimation errors by slow update/iteration. It can make the training more stable (Remark 3.3) and increase the action gap Eq.(11).

In this section, let’s prove that the $Q_{k}$, during $k$-th $Q$-iterations with $\mathcal{T}_{SAL}$, converges to a unique fixed point, and our algorithm can increase the larger action gap value Eq.(11) compared with AL algorithm, when there is no approximation error.

Thus under an all-preserving operator, all optimal actions remain optimal, and the order of good and bad actions of $\hat{Q}^{*}$ remains the same as $Q^{*}$. Compared with the definition of optimality-preserving operator 2.1, the definition 3.1 is more restrictive. Because the operator $\mathcal{T}^{\prime}$ is an all-preserving operator, the $\mathcal{T}^{\prime}$ must be an optimality-preserving operator.

From Eq. (7), we have

where $A_{k}\hat{B}_{k}(s,a)=Q_{k-1}(s,a)+\lambda V_{k-2}(s)+\lambda^{2}V_{k-3}(s)+\cdots+\lambda^{k-1}V_{0}(s)$, $A_{k}=\frac{1-\lambda^{k}}{1-\lambda}=1+\lambda+\lambda^{2}+\cdots+\lambda^{k-1}$ is the weighted regular term, $\lambda=1-\omega+\alpha$, $B_{k}(s)=\max_{a_{k-1}}\hat{B}_{k}(s,a)$, and $V_{i}(s)=\max_{a}Q_{i}(s,a)$, $Q_{i}(s,a)$ is $i$-th $Q$-iterations, $i=1,2,\cdots,k-1$. For simplicity, we assume $Q_{0}(s,a)=0$. See Appendix for detailed derivation.

Now let’s prove that the the smoothing advantage learning operator $\mathcal{T}_{SAL}$ is both all-preserving and gap-increasing.

The proof of the theorem is given in Appendix.

This result shows the relationship between the stable point $\hat{Q}^{*}(s,a)$ and the optimal point $Q^{*}(s,a)$. The $\hat{Q}^{*}(s,a)$ and $Q^{*}(s,a)$ not only have the same maximum values, but also have the same order of good and bad actions. If $\omega=1$, the $\mathcal{T}_{SAL}$ operator is reduced to the advantage learning operator $\mathcal{T}_{AL}$. Hence the above analysis applies to the $\mathcal{T}_{AL}$ operator as well - that is, the advantage learning operator $\mathcal{T}_{AL}$ is all-preserving. More importantly, it’s possible that $\alpha$ is greater than $1$. This not only generalizes the properties of the advantage learning operator $\mathcal{T}_{AL}$ (Bellemare et al. 2016) (where it is concluded that $\hat{V}^{*}(s)\triangleq\max_{a}\hat{Q}^{*}(s,a)=V^{*}(s)$ and satisfy $0\leq\alpha<1$), but also implies that all optimal actions of $Q^{*}(s,a)$ remain optimal through the operator $\mathcal{T}_{AL}$ instead of at least ones (Bellemare et al. 2016). This later advantage may be the main reason for the good performance of $\mathcal{T}_{AL}$ (shown in the experimental section).

Next, we will give the relationship between the operator $\mathcal{T}_{SAL}$ and $\mathcal{T}$ in term of action-gap value.

The proof of the theorem is given in Appendix.

This result shows that the action gap $Gap(\mathcal{T}_{SAL};s,a)$ is a multiple of the $Gap(\mathcal{T};s,a)$. It also reveals how hyperparameters of $\omega$ and $\alpha$ affect the action gap. Furthermore, in the case of $\omega=1$, the action gap $Gap(\mathcal{T}_{SAL};s,a)$ is equal to the $Gap(\mathcal{T}_{AL};s,a)$. From Theorem 3.2, if $0\leq\alpha<\omega\leq 1$, we can conclude that

In other words, the operator SAL helps to enlarge the gap between the optimal action-value and the sub-optimal action values. This is beneficial to improve the robustness of the estimated $Q$ value against environmental noise or estimation errors.

In the previous section, we discussed the convergence of the SAL in the absence of approximation error. In this section, we prove that our algorithm can achieve more stable training compared with AL algorithm by error propagation (Remark 3.3). Now, we derive the performance bound for approximate SAL, defined by

where $V_{k}(s)=\max_{a}Q_{k}(s,a)$, $\mathcal{T}$ is the optimal Bellman operator Eq.(2), $0\leq\alpha<\omega<\frac{2}{1+\gamma}$, $\epsilon_{k}$ is an approximation error at $k$-iteration. In general, when calculating the $\mathcal{T}Q_{k}$, error $\epsilon_{k}$ is inevitable, because (1) we do not have direct access to the optimal Bellman operator, but only some samples from it, and (2) the function space in which $Q$ belongs is not representative enough. Thus there would be an approximation error $\mathcal{T}Q_{k}(s,a)+\epsilon_{k}$ between the result of the exact value iteration (VI) and approximate VI (AVI) (Munos 2007; Azar, Gómez, and Kappen 2012; Kozuno, Uchibe, and Doya 2017; Vieillard, Pietquin, and Geist 2020; Smirnova and Dohmatob 2020). Just for simplicity, we assume that $Q_{0}(s,a)=0$ throughout this section.

The proof of the theorem is given in Appendix.

From the above analysis, we know that the performance of the algorithm is bounded by the convergence rate term and the error term. These two terms have a direct effect on the behavior of our algorithm. Since the convergence rate of approximate SAL is much slower than the approximate AL and approximate VI, the upper error bound of the performance is very lower compared with approximate AL. This is beneficial to alleviate incorrect action gap values. From the Figure 2, we show the difference between $AL(\epsilon)$ and $SAL(\epsilon)$. It’s pretty straightforward to see that $SAL(\epsilon)$ is very different from $AL(\epsilon)$ in the early stages. This result shows that this is consistent with our motivation. The estimated $Q$ function obtained by the approximate value function may be more accurate compared with approximate AL. In the next section, we see that our method can effectively alleviate incorrect action gap values.

To verify the effectiveness of the smoothing advantage learning (SAL), we replace the original optimal Bellman operator used in AL (Bellemare et al. 2016) with the optimal smooth Bellman operator. Algorithm 1 gives the detailed implementation pipeline in Appendix. Basically, the only difference we made over the original algorithm is that we construct a new TD target for the algorithm at each iteration, which implements an empirical version of our SAL operator with the target network, and all the remaining is kept unchanged.

We conduct all the experiments mainly based on (Lan et al. 2020). The test procedures are averaged over 10 test episodes every 5000 steps across 5 independent runs. Particularly, we choose $\alpha$ from the set of {0.2, 0.3, 0.5, 0.9} for AL (Bellemare et al. 2016). For SAL, we choose $\omega$ and $\alpha$ among {0.2, 0.3, 0.5, 0.9}, but the hyperparameters satisfy $\alpha<\omega$. For Munchausen-DQN (M-DQN) (Vieillard, Pietquin, and Geist 2020), we fix $\tau=0.03$, choose $\alpha$ from the set of {0.2, 0.3, 0.5, 0.9}. Since G-VI is equivalent to M-VI (M-DQN is a deep version of M-VI) (see the theorem 2.1 in Appendix), we don’t conduct this experiment for G-VI. The number of target networks $N$ is chosen from {2, 3, 5, 9} for Average DQN (A-DQN) (Anschel, Baram, and Shimkin 2017). For a fair comparison, we optimize hyperparameter settings for all the compared methods on each environment before reporting the results. Please see Appendix for more details about experimental settings.

Firstly, we evaluate the proposed smoothing advantage learning algorithm (SAL) (see Algorithm 1 in Appendix) with a series of comparative experiments ( SAL vs. AL (Bellemare et al. 2016)) on the Gym and MinAtar environments. As before, we evaluate the average of 10 test episodes every 5000 steps across 5 independent runs. And we plot the corresponding mean and 95% confidence interval in all figures.

Figure 3 gives the results of the SAL algorithm. We observed from the figure that compared to DQN, the original AL seems to not improve the performance significantly. And compared to DQN and the original AL, the SAL learns slower at the early stage, but as the learning goes on, our algorithm accelerates and finally outperforms the compared ones at most of the time. This provides us some interesting empirical evidence to support our conjecture that slow update at the early stage of the learning procedure is beneficial.

To further investigate the reason behind this, we evaluate the action gap between the optimal and sub-optimal $Q$ values, by sampling some batches of state-action pairs from the replay buffer, and then calculate the averaged action gap values as the estimate. The figure (g) and (h) of Figure 3 gives the results. It shows that the action gap of SAL is two to three times as much as that of DQN, and is much higher than that of AL as well. From theorem 3.3, we know that the performance of the algorithm is bounded by the convergence speed term and the error term. These two terms have a direct effect on the behavior of our algorithm. In particular, at the early stage of learning, since the accumulated error is very small, the performance of the algorithm is mainly dominated by convergence speed term. However, since the convergence rate of approximate SAL is much slower than the approximate AL and approximate VI (see remark 3.2), we can see that the mixing update slows down the learning in the beginning. After a certain number of iterations, the convergence speed terms of all three algorithms (SAL, AL, and VI) become very small (as Remark 3.2 indicates, this term decreases exponentially with the number of iterations). Consequently, the performance of the algorithm is mainly determined by the second term, i.e., the accumulated error term. This explains why at the later stage, learning stabilizes and leads to higher performance. In fact, by comparing (c) and (g) of Figure 3 or comparing (d) and (h) of Figure 3, one can see that the performance acceleration stage consistently corresponds to the increasing the action gap stage. Intuitively, increasing the action gap which increase the gap between the optimal value and the sub-optimal value help to improve the algorithm’s performance, as this helps to enhance the network’s ability to resist error/noise and uncertainty. This verifies our theoretical analysis.

In addition, Figure 1 and Figure 3 aren’t contradictory. Figure 1 shows the optimal parameter $\alpha=0.9$ in the original paper of AL. In Figure 3, we search for the best parameter separately on each environment for all algorithms among the candidates. We also try to adjust the $\alpha$ value of AL separately to increase the action gap in Appendix, but we find that the performance of the AL algorithm doesn’t improve only by increasing the action gap value. We find that the action gap values are incorrectly increased at the early stage of learning. It is no benefit, as the target network tends to be unreliable in predicting the future return. And we also see that incorrect action gap value is rectified at a later stage. Thus, the difficulty of learning is increased, and the performance of the algorithm is reduced. At the same time, our method also tries to get a larger action gap value by adjusting the parameters $\omega$ and $\alpha$ in Appendix. One can see that our method can adjust the parameters $\omega$ and $\alpha$ to steadily increase the action gap value. By comparing these two methods, we know that our proposed method can effectively alleviate the bad factors by errors, thus can learn more quickly.

Secondly, we analyze the influence of $\omega$ and $\alpha$ on the action gap values in SAL. Figure 4 and Figure 5 shows the results. It can be seen that for a fixed $\alpha$ value, the action gap value is decreasing monotonically w.r.t. $\omega$, while for a fixed $\omega$, the action gap value is increasing monotonically w.r.t. $\alpha$. This is consistent with our previous theoretical analyses. In practice, we would suggest setting a higher value for $\alpha$ and a lower value for $\omega$, so as to improve our robustness against the risk of choosing the wrong optimal action.

Finally, Table 1 gives the mean and standard deviation of average returns for all algorithms across the six games at the end of training. According to these quantitative results, one can see that the performance of our proposed method is competitive with other methods.