Deep Residual Reinforcement Learning (Extended Abstract)

1 Introduction

Semi-gradient algorithms have recently enjoyed great success in deep reinforcement learning (RL) problems, e.g., DQN [Mnih et al., 2015] achieves human-level control in the Arcade Learning Environment (ALE, [Bellemare et al., 2013]). However, such algorithms lack theoretical support. Most semi-gradient algorithms suffer from divergence under nonlinear function approximation or off-policy training [Baird, 1995; Tsitsiklis and Van Roy, 1997]. By contrast, residual gradient (RG, [Baird, 1995]) algorithms are true stochastic gradient algorithms and enjoy convergence guarantees (to a local minimum) under mild conditions with both nonlinear function approximation and off-policy training. [Baird, 1995] further proposes residual algorithms (RA) to unify residual gradients and semi-gradients via mixing them together.

Residual algorithms, however, suffer from the double sampling issue [Baird, 1995]: two independently sampled successor states are required to compute the residual gradients. This requirement can be easily satisfied in model-based RL or in deterministic environments. However, even in these settings, residual algorithms have long been either overlooked or dismissed as impractical. In this paper, we aim to overturn that conventional wisdom with new algorithms built on RA and empirical results showing their efficacy.

Our contributions are twofold. First, we show the advantages of RA in a model-free RL setting with deterministic environments. While target networks [Mnih et al., 2015] are usually an important component in deep RL algorithms to stabilize training [Mnih et al., 2015; Lillicrap et al., 2015], we find a naive combination of target networks and residual algorithms, in general, does not improve performance. Therefore, we propose the bidirectional target network technique to stabilize residual algorithms. We show that our residual version of Deep Deterministic Policy Gradients (DDPG, [Lillicrap et al., 2015]) significantly outperforms vanilla DDPG in the DeepMind Control Suite (DMControl, [Tassa et al., 2018]) and MuJoCo benchmarks.

∗Contact Author

Second, we show the advantages of RA in a model-based RL setting, where a learned model generates imaginary transitions to train the value function. In general, model-based methods suffer from a distribution mismatch problem [Feinberg et al., 2018]. The value function trained on real states does not generalize well to imaginary states generated by a model. To address this issue, [Feinberg et al., 2018] train the value function on both real and imaginary states via the TD(k) trick. However, TD(k) requires that predictions k steps in the future made by model rollouts will be accurate [Feinberg et al., 2018]. In this paper, we show that RA naturally allows the value function to be trained on both real and imaginary states and requires only 1-step rollouts. Our experiments show that RA-based planning boosts performance more than TD(k)-based planning in most cases.

2 Background

We consider an MDP [Puterman, 2014] consisting of a finite state space S, a finite action space A, a reward function r : S×A→R, a transition kernel p : S×S×A→ [0, 1] and a discount factor γ ∈ [0, 1). With π : A × S → [0, 1] denoting a policy, at time t, an agent at a state St takes an action At according to π(·|St). The agent then gets a reward Rt+1 satisfying E[Rt+1] = r(St, At) and proceeds to a new state St+1 according to p(·|St, At). We use Gt .= ∑∞i=t+1 γ i-t-1Ri to denote the return from time t, vπ(s) .= Eπ[Gt | St = s] to denote the state value function of π, and qπ(s, a) .= Eπ[Gt | St = s,At = a] to denote the state-action value function of π. In the rest of this section, we use a bold capital letter to denote a matrix and a bold lowercase letter to denote a column vector. We use Pπ to denote the transition matrix induced by a policy π, i.e., Pπ[s, s′ ] .= ∑a π(s, a)p(s′ |s, a), and use dπ to denote its unique stationary distribution, assuming the chain induced by Pπ is ergodic. The reward vector induced by π is rπ[s] = ∑a π(a|s)r(s, a).

The value function vπ is the unique fixed point of the Bellman operator T [Bellman, 1957]. In a matrix form, T is defined as T v .= rπ +γPπv, where v can be any vector in RN . Here N .= |S| is the number of states.

Policy Evaluation: We consider the problem of finding vπ for a given policy π and use v, parameterized by w ∈ Rd , to denote an estimate of vπ, the vector form of vπ. We start with on-policy linear function approximation and use x : S → Rd to denote a feature function which maps a state to a d-dimensional feature. The feature matrix is then X .= [x(s1), . . . , x(sN)]T ∈ RN×d , and the value estimate is v .= Xw. Two commonly used objectives for learning w are the Mean Squared Projected Bellman Error (MSPBE) and the Mean Squared Bellman Error (MSBE):

Here Π is a projection operator which maps an arbitrary vector onto the column vector space of X, minimizing a dπ-weighted projection error, i.e., Πv .= X¯w, where ¯w .= argminw ||v - Xw||2dπ . With linear function approximation and fixed features, Π is linear.

There are various algorithms for minimizing MSPBE and MSBE. Temporal Difference learning (TD, [Sutton, 1988]) is commonly used to minimize MSPBE. TD updates w as

where α is a step size. Under mild conditions, on-policy linear TD converges to the point where MSPBE is 0 [Tsitsiklis and Van Roy, 1997]. TD is a semi-gradient [Sutton and Barto, 2018] algorithm in that it ignores the dependency of v(St+1) on w. There are also true gradient algorithms for optimizing MSPBE, e.g., Gradient TD methods [Sutton et al., 2009]. Gradient TD methods compute the gradient of MSPBE directly and also enjoy convergence guarantees.

[Baird, 1995] proposes residual gradient algorithms for minimizing MSBE, which updates w as

where S′t+1 is another sampled successor state for St, independent of St+1. This requirement for two independent samples is known as the double sampling issue [Baird, 1995]. If both the transition kernel p and the policy π are deterministic, we can simply use one sample without introducing bias. Otherwise, we may need to have access to the transition kernel p, which is usually not available in model-free RL. Regardless, RG is a true gradient algorithm with convergence guarantees under mild conditions.

We now expand our discussion about policy evaluation into off-policy learning and nonlinear function approximation, where the states {St} are drawn according to a behavior policy µ instead of the target policy π. True gradient algorithms like Gradient TD methods and RG remain convergent to local minima under off-policy training with any function approximator [Baird, 1995; Sutton et al., 2009; Maei, 2011]. However, the empirical success of Gradient TD

methods is limited to simple domains due to its large variance [Sutton et al., 2016]. Semi-gradient algorithms are not convergent in general, e.g., the divergence of off-policy linear TD is well-documented [Tsitsiklis and Van Roy, 1997].

Semi-gradient algorithms are fast but in general not convergent. Residual gradient algorithms are convergent but slow [Baird, 1995]. To take advantage of both, [Baird, 1995] proposes to mix semi-gradients and residual gradients together, yielding the residual algorithms. The RA version of TD [Baird, 1995] updates w as

where η ∈ [0, 1] controls how the two gradients are mixed. Little empirical study has been conducted for RA.

Control: We now consider the problem of control, where we are interested in finding an optimal policy π∗ such that qπ∗(s, a) ≥ qπ(s, a) ∀(π, s, a). We use Q, parameterized by θ, to denote our estimate of qπ. Q-learning [Watkins and Dayan, 1992] is usually used to train Q and enjoys convergence guarantees in the tabular setting. When the action space is continuous, DDPG [Lillicrap et al., 2015] is usually used as a continuous version of Q-learning. In DDPG, an actor µ : S → A, parameterized by ν, is trained to output the greedy action. DDPG updates θ and ν as

where α1, α2 are step sizes, ¯µ, ¯Q are target networks [Mnih et al., 2015; Zhang et al., 2021], which are synchronized with µ, Q periodically.

DDPG is a semi-gradient algorithms. There are also true gradient methods for control, e.g., Greedy-GQ [Maei et al., 2010] and the residual version of Q-learning [Baird, 1995]. As with Gradient TD methods, the empirical success of Greedy-GQ is limited to simple domains due to its large variance [Sutton et al., 2016].

3 Residual Algorithms inModel-free RL

In this section, we investigate how to combine RA and DDPG. In particular, we consider almost deterministic environments where the double sampling issue is not significant.

In semi-gradient algorithms, value propagation goes backwards in time. The value of a state depends on the value of its successor through bootstrapping, and a target network is used to stabilize this bootstrapping. RA allows value propagation both forwards and backwards. The value of a state depends on the value of both its successor and predecessor. Therefore, we need to stabilize the bootstrapping in both directions. To this end, we propose the bidirectional target network technique. Employing this in DDPG yields Bi-Res-DDPG, which updates the critic parameters θ as:

where ¯Q, ¯µ are target networks and η ∈ [0, 1] controls how the two gradients are mixed. The actor update remains unchanged.

We compared Bi-Res-DDPG to DDPG in 28 DMControl tasks and 5 Mujoco tasks. Our DDPG implementation uses the same architecture and hyperparameters as [Lillicrap et al., 2015], which are inherited by Bi-Res-DDPG (and all other DDPG variants in this paper). For Bi-Res-DDPG, we tune η over {0, 0.05, 0.1, 0.2, 0.4, 0.8, 1} on walker-stand and use η = 0.05 across all tasks. We perform 20 deterministic evaluation episodes every 104 training steps and plot the averaged evaluation episode returns. In Figure 1, we report the improvement of AUC (area under the curve) of the evaluation curves. AUC serves as a proxy for learning speed (e.g., see Example 8.2 in [Sutton and Barto, 2018]). Bi-Res-DDPG achieves a 20% (41%) AUC improvement over the original DDPG in terms of the median (mean). Our DDPG baseline reaches the same performance level as the DDPG baseline in [Fujimoto et al., 2018] and [Buckman et al., 2018] in Mujoco tasks. An ablation study of Bi-Res-DDPG is provided in [Zhang et al., 2020] to future investigate the necessity of the bidirectional target network.

We do not expect residual updates to improve the performance of all semi-gradient baselines. However, our results do show that the residual update together with the bidirectional target network is beneficial in many tasks. Despite the popularity of semi-gradient methods, we do believe residual algorithms deserve more study. The combination of residual updates and other semi-gradient algorithms, e.g., TD3 [Fujimoto et al., 2018], is a possibility for future work. We also do not address the double sampling issue in stochastic environments. This is indeed a restriction, but we would like to emphasize that most available benchmarks with continuous actions have deterministic transitions, which indicates that this class of problems is of practical concern.

4 Residual Algorithms inModel-based RL

In model-based RL, the double sampling issue can be easily addressed by querying the learned model (either deterministic or stochastic). Given the empirical success of deterministic models and their robustness in complex tasks [Kurutach et al., 2018; Feinberg et al., 2018; Buckman et al., 2018], we consider deterministic models in this paper. Dyna [Sutton, 1990] is a commonly used model-based RL framework that trains a value function with imaginary transitions from a learned model. In this paper, we consider the combination of Dyna and DDPG. For each planning step, we sample a transition (s, a, r, s′ ) from a replay buffer and add some noise ϵ to the action a, yielding a new action ˆa. We then query a learned model with (s, ˆa) and get (ˆ r, ˆ s′ ). We aim to investigate different strategies for updating Q during planning.

One naive choice is to use the semi-gradient critic update (2). However, this suffers from the distribution mismatch problem [Feinberg et al., 2018]. When we apply (2) in an imaginary transition (s, ˆa, ˆ r, ˆ s′ ), we need the Q-value on ˆ s′ for bootstrapping. The Q-function is trained to make an accurate prediction on the state distribution of s, which is usually different from the state distribution of ˆ s′ . This distribution mismatch results from both an imperfect model and the different sampling strategies for a and ˆa. It yields an inaccurate prediction for Q(ˆ s′ , µ(ˆ s′ )), leading to poor performance [Feinberg et al., 2018]. The TD(k) trick [Feinberg et al., 2018] is one attempt to address this issue. With a real transition (s-1, a-1, r0, s0) sampled from a replay buffer, a model is unrolled for k steps following ¯µ, yielding a trajectory (s-1, a-1, r0, s0, a0, r1, s1, . . . , rk, sk). TD(k) then updates θ to minimize

With this update, Q is trained on distributions of almost all the states (s-1, . . . , sk-1), which [Feinberg et al., 2018] show helps performance. However, TD(k) still does not train Q on the last imaginary state sk, which is used for bootstrapping. On the one hand, the influence of the bootstrapping error from sk decreases as the trajectory gets longer thanks to discounting. On the other hand, even small state prediction errors typically compound as trajectories get longer, yielding a large prediction error of the state sk itself. This contradiction is deeply embedded in TD(k). Consequently, TD(k)

must assume the model is accurate for k-step unrolling, which is usually hard to satisfy in practice.

In this paper, we seek to mitigate this distribution mismatch issue through RA. For an imaginary transition (s, ˆa, ˆ r, ˆ s′ ), RA naturally allows the Q-function to be trained on both s and ˆ s′ , without requiring further unrolling like TD(k). The use of RA in model-based planning is inspired by the theoretical results from [Li, 2008], who proves that TD makes better predictions than RG. On a real transition, this accelerates backward value propagation by providing better bootstrapping. However, on an imaginary transition from a model, the value function is never trained on the imaginary successor state. It is questionable whether we should trust the value prediction on an imaginary state as much as a real state. We, therefore, propose to use RA on imaginary transitions, which encourages the Q-function to be consistent with the model as showed by [Li, 2008].

We now evaluate RA in model-based planning experimentally. We compare the performance of Dyna-DDPG (i.e., use the semi-gradient to update the critic with imaginary transitions), Res-Dyna-DDPG (i.e., use residual algorithms to update the critic with imaginary transitions ), and MVE-DDPG (i.e., use the TD(k) trick to update the critic with imaginary transitions following [Feinberg et al., 2018]). We consider five Mujoco tasks used by [Buckman et al., 2018], which is a superset of tasks used by [Feinberg et al., 2018]. In [Feinberg et al., 2018], the unrolling steps of MVE-DDPG are different for different tasks, which serve as domain knowledge. For a fair comparison, [Buckman et al., 2018] set k = 3 for all tasks in their baseline MVE-DDPG. In our empirical study, we followed this convention.

To separate planning from model learning, we consider planning with an oracle model. In this section, we restrict our empirical study on Mujoco tasks as we do not have direct access to the oracle models in DMControl tasks. We tune hyperparameters for Dyna-DDPG and Res-Dyna-DDPG on Walker and set η = 0.2 for all tasks. See [Zhang et al., 2020] for more details. The results are reported in Figure 2. Curves are averaged over 8 independent runs and shadowed regions indicate standard errors. Both Dyna-DDPG and MVE-DDPG with an oracle model improve performance in 2 of 5 games, while Res-Dyna-DDPG improves performance in 4 out of 5 games. These results suggest that RA is a more effective approach to exploit a model for planning. In HalfCheetah, both MVE-DDPG and Res-Dyna-DDPG fail to outperform Dyna-DDPG. This could suggest that the distribution mismatch problem is not significant in this task. Furthermore, MVE-DDPG exhibits instability in HalfCheetah, which is also observed by [Buckman et al., 2018]. The results of planning with a learned model is provided in [Zhang et al., 2020], where the relative performance is similar to that of planning with an oracle model.

Note in Res-Dyna-DDPG, we use the naive residual algorithms without the bidirectional target network. Our preliminary experiments show that introducing the bidirectional target network during planning does not further boost performance. The main purpose of a target network is to stabilize bootstrapping (value propagation). Due to the distribution mismatch problem on imaginary transitions, however, it may be more important for the value function to be consistent with the model than simply propagating the value in either direction. This may reduce the importance of the bidirectional target network.

5 Conclusions

In this paper, we compare two classical RL methods, RG and TD, in both model-based and model-free settings. See [Zhang et al., 2020] for a detailed review of related work. We propose the bidirectional target network technique to stabilize bootstrapping in both directions in RA, yielding a significant performance boost. We also demonstrate that RA is a more effective approach to the distribution mismatch problem in model-based planning than the existing TD(k) method. Our empirical study showed the efficacy of RA in deep RL problems, which has long been underestimated by the community. A possibility for future work is to study RA in model-free RL with stochastic environments, where the double sampling issue cannot be trivially resolved.

Acknowledgments

SZ is generously funded by the Engineering and Physical Sciences Research Council (EPSRC). This project has received funding from the European Research Council under the European Union's Horizon 2020 research and innovation programme (grant agreement number 637713). The experiments were made possible by a generous equipment grant from NVIDIA.