In the context of continuous control, actor-critic architecture is widely used (Sutton et al., 1999; Peters & Bagnell, 2010) to handle the continuous action space. In actor-critic framework, a critic $Q_{\theta}$ is used to estimate the action-value function $Q_{\theta}(s,a)\approx Q^{\pi}(s,a)$, while the parametric actor $\pi_{\phi}$ optimizes its policy using the policy gradient from parametric $Q_{\theta}$. When $\pi_{\phi}$ is a deterministic function, the gradient can be expressed as follows:

which is known as deterministic policy gradient theorem (Silver et al., 2014).
$Q_{\theta}$ can be learned from the TD-target derived from the Bellman Equation (Bellman, 1957):

In the following section, when it does not lead to confusion, we use $Q_{\theta}(s)$ instead of $Q_{\theta}(s,\pi_{\phi}(s))$ for simplicity.

Q-learning update state-action values by the TD target (Sutton, 1988a) :

However, the max operator in the target can easily lead to overestimation, as discussed in van Hasselt (2010). Thus, They propose to estimate the maximum $Q$-values over all actions $\max_{a}Q(s,a)$ using the double estimator, i.e.,

where $Q^{A},Q^{B}$ are two independent function approximators for $Q$-values.

Traditional deep RL approaches suffer from sample inefficiency because of slow gradient-based updates. Episodic control is proposed to speed up the learning process by a non-parametric episodic memory (EM). The key idea is to store good past experiences in a tabular-based non-parametric memory and rapidly latch onto past successful policies when encountering similar states, instead of waiting for many steps of optimization. When different experiences meet up at the same state-action pair $(s,a)$, model-free episodic control (MFEC; Blundell et al., 2016) aggregates the values of different trajectories by taking the maximum return $R$ among all these rollouts starting from the intersection $(s,a)$. Specifically, $Q^{EM}$ is updated by the following equation:

At the execution time, MFEC selects the action according to the maximum $Q$-value of the current state. If there is no exact match of the state, MFEC performs a $k$-nearest-neighbors lookup to estimate the state-action values, i.e.,

where $s_{i}$ $(i=1,\cdots,k)$ are the $k$ nearest states from $s$.

In generalizable episodic memory (GEM), we use a parametric network $\mathcal{M}_{\theta}$ to represent the virtual memory table with parameter $\theta$, which is learned from tabular memory $\mathcal{M}$. To leverage the generalization ability of $\mathcal{M}_{\theta}$, we enhance the returns stored in the tabular memory by propagating value estimates from ${\mathcal{M}}_{\theta}$ and real returns from $\mathcal{M}$ along trajectories in the memory and take the best value over all possible rollouts, as depicted in Equation (4). Generalizable memory $\mathcal{M}_{\theta}$ is trained by performing regression toward this enhanced target and is then used to guide policy learning as well as to build the new target for GEM’s learning.

A significant issue for the procedure above is the overestimation induced from taking the best value along the trajectory. Overestimated values are preserved when doing back-propagation along the trajectory and hinder learning efficiency. To mitigate this issue, we propose to use twin networks for the back-propagation of value estimates. This twin back-propagation process uses the double estimator for estimating the maximum along trajectories, which resembles the idea of Double Q-learning (van Hasselt, 2010) and is illustrated in detail in Section 3.4. It is well known that vanilla reinforcement learning algorithms with function approximation already has a tendency to overestimate (van Hasselt, 2010; Fujimoto et al., 2018), making the overestimation reduction even more critical. To solve this challenge, we propose to use additional techniques to make the value estimation from $\mathcal{M}_{\theta}$ more conservative, which is illustrated in Section 3.5.

A formal description for GEM algorithm is shown in Algorithm 1. In the following sections, we use $Q_{\theta}$ to represent $Q_{\mathcal{M}_{\theta}}$ for simplicity. Our implementation of GEM is available at https://github.com/MouseHu/GEM.

Traditional discrete episodic memory is stored in a lookup table, learned as in Equation (2) and used as in Equation (1). This kind of methods does not consider generalization when learning values and enjoy little generalization ability from non-parametric nearest-neighbor search with random projections during execution. To enable the generalizability of such episodic memory, we use the parametric network $\mathcal{M}_{\theta}$ to learn and store values. As stated in Section 3.1, this parametric memory is learned by doing regression toward the best returns $R_{t}$ starting from the state-action pair $(s_{t},a_{t})$:

where $R_{t}$ is computed from implicit planning over both real returns in tabular memory $\mathcal{M}$ and estimates in target generalizable memory table $\mathcal{M}_{\theta}^{\prime}$, as depicted in the next section. This learned virtual memory table is then used for both policy learning and building new target.

To leverage the analogical reasoning ability of our parametric memory, GEM conducts implicit memory-based planning to estimate the value for the best possible rollout for each state-action pair. At each step, GEM compares the best return so far along the trajectory with the value estimates from $Q_{\theta}$ and takes the maximum between them. $Q_{\theta}$ is generalized from similar experiences and can be regraded as the value estimates for counterfactual trajectories. This procedure is conducted recursively from the last step to the first step along the trajectory, forming an implicit planning scheme within episodic memory to aggregate experiences along and across trajectories. The overall back-propagation process can be written in the following form:

where $t$ denotes steps along the trajectory and $T$ the episode length. Further, the back-propagation process in Equation (4) can be unrolled and rewritten as follows:

where $h$ denotes different length of rollout steps, and we define $Q_{\theta}(s_{t},a_{t})=0$ and $V_{t,h}=0$ for $t>T$.

In this section, we describe our novel twin back-propagation process to reduce trajectory-induced overestimation.

As mentioned in Section 3.1, using Equation (3.3) for planning directly can lead to severe overestimation, even if $Q_{\theta}$ is unbiased. Formally, for any unbiased set of estimators $\tilde{Q}_{h}(s,a)=Q_{h}(s,a)+U_{h}(s,a)$, where $Q_{h}(s,a)$ is the true value and $U_{h}(s,a)$ is a set of independent, zero-mean random noise, we have

which can be derived directly from Jensen’s inequality.

Thus trajectory-augmented values have a tendency to overestimate and this overestimation bias can hurt performance greatly. We propose to use twin networks, $Q^{(1)},Q^{(2)}$, to form a double estimator for estimating the best value $R_{t}$ in the value back-propagation in Equation (3.3). One network is used to estimate the length of rollouts with the maximum returns along a trajectory ($h^{*}$ in Equation (3.3)), while the other estimates how large the return is following this estimated best rollout ($V_{t,h^{*}}$ in Equation (3.3)). Formally, the proposed twin back-propagation process (TBP) is given by ¹¹1In Equation (7) & (8), index $(1,2)$ represents it can be either $(1)$ or $(2)$, while reversed index $(2,1)$ refers to the other network’s estimation, i.e. represents $(2)$ when $(1,2)$ refers to $(1)$ and vice versa.:

And each $Q$-network is updated by

Note that this twin mechanism is different from double Q-learning, where we take the maximum over timesteps while double Q-learning takes the maximum over actions.

Formal analysis in Section 4.1 shows that this twin back-propagation process does not overestimate the true maximum expectation value, given unbiased $Q_{\theta}$. As stated in van Hasselt (2010) and Fujimoto et al. (2018), while this update rule may introduce an underestimation bias, it is much better than overestimation, which can be propagated along trajectories.

The objective in Equation (8) may still prone to overestimation since $Q^{(1,2)}_{\theta}$ is not necessarily unbiased, and it is well known that deterministic policy gradient has a tendency to overestimate (Fujimoto et al., 2018). To address this issue, we further augment each $Q^{(1,2)}_{\theta}$ functions with two independent networks $Q_{A},Q_{B}$, and use clipped double Q-learning objective as in Fujimoto et al. (2018) for the estimation at each step:

Finally, we propose the following asymmetric objective to penalize overestimated approximation error,

where $\delta_{t}=Q^{(1,2)}(s_{t},a_{t})-R^{(1,2)}_{t}$ is the regression error and $(\cdot)_{+}=\max(\cdot,0)$. $\alpha$ is the hyperparameter to control the degree of asymmetry.

We first investigate the algorithmic property of the twin back-propagation process in terms of value estimation bias, which is an essential concept for value-based methods (Thrun & Schwartz, 1993; van Hasselt, 2010; Fujimoto et al., 2018). Theorem 1 indicates that our method would not overestimate the real maximum value in expectation.

The proof of Theorem 1 is deferred to Appendix B. As revealed by Theorem 1, the twin back-propagation process maintains the same non-overestimation nature of double Q-learning (van Hasselt, 2010), which ensures the reliability of our proposed value propagation mechanism.

In addition to the statistical property of value estimation, we also analyze the convergence behavior of GEM. Following the same environment assumptions as related work (Blundell et al., 2016; Zhu et al., 2020), We first derive the convergence guarantee of GEM in deterministic scenarios as the following statement.

The proof of Theorem 2 is extended based on van Hasselt (2010), and details are deferred to Appendix B. Note that this theorem only applies to deterministic scenarios, which is a common assumption for memory-based algorithms (Blundell et al., 2016; Zhu et al., 2020). To establish a more precise characterization, we consider a more general class of MDPs, named near-deterministic MDPs, as stated in Definition 4.1.

Based on the definition of near-deterministic MDPs, we formalize the performance guarantee of our approach as the following statements:

The complete proof of these statements are deferred to Appendix B. Theorem 3 ensures that, our approach is applicable to near-deterministic environments as most real-world scenarios.

We compare our method with the most popular model-free RL algorithms, including DDPG (Lillicrap et al., 2016), TD3 (Fujimoto et al., 2018) and SAC (Haarnoja et al., 2018). Conventional episodic RL such as MFEC (Blundell et al., 2016), NEC (Pritzel et al., 2017), EMDQN (Lin et al., 2018), EVA (Hansen et al., 2018) and ERLAM (Zhu et al., 2020) adopts discrete episodic memory that are only designed for discrete action space, thus we cannot directly compare with them. To compare with episodic memory-based approaches on the continuous domain, we instead choose self-imitation learning (SIL; Oh et al., 2018) in our experiments. It also aims to exploit past good experiences and share a similar idea with episodic control; thus, it can be regarded as a continuous version of episodic control. For a fair comparison, We use the same code base for all algorithms, and we combine the self-limitation learning objective with techniques in TD3 (Fujimoto et al., 2018), rather than use the origin implementation, which combines with PPO (Schulman et al., 2017).

We conduct experiments on the suite of MuJoCo tasks (Todorov et al., 2012), with OpenAI Gym interface (Brockman et al., 2016). We truncate the maximum steps available for planning to reduce the overestimation bias. The memory update frequency $u$ is set to 100 with a smoothing coefficient $\tau=0.6$. The rest of the hyperparameters are mostly kept the same as in TD3 to ensure a fair comparison. The detailed hyperparameters used are listed in Appendix C.

The learning curve on different continuous tasks is shown in Figure 2. We report the performance of 1M steps, which is evaluated with $10$ rollouts for every $10000$ steps with deterministic policies. As the results suggest, our method significantly outperforms other baseline algorithms on most tasks. Only on Hopper, GEM is not the absolute best, but all the algorithms have similar performance.

Though GEM is proposed to facilitate continuous control tasks, it also has the general applicability of boosting learning on discrete domains. To demonstrate this, we compare GEM with several advanced deep Q-learning algorithms for discrete action space, including DQN (Mnih et al., 2015), DDQN (van Hasselt et al., 2016), and Dueling DQN (Wang et al., 2016). We also include the clipped double DQN, which is adopted from a state-of-the-art algorithm of the continuous domain, TD3 (Fujimoto et al., 2018). Most of these baseline algorithms focus on learning stability and the reduction of estimation bias. We evaluate all the above algorithms on 6 Atari games (Bellemare et al., 2013). We use hyper-parameters suggested in Rainbow (Hessel et al., 2018), and other hyper-parameters for our algorithm are kept the same as in the continuous domain. As shown in Figure 3, although not tailored for the discrete domain, GEM significantly outperforms baseline algorithms both in terms of sample efficiency and final performance.

This section aims to understand each part’s contribution to our proposed algorithm, including the generalizable episodic memory, implicit memory-based planning, and twin back-propagation. We also empirically demonstrate the effect of overestimation. To check whether our method, which uses four networks, benifits from ensembling effect, we also compare our method with the random ensembling method as used in REDQ (Chen et al., 2021).

To verify the effectiveness of generalizable episodic memory, we compare our algorithm with SIL, which directly uses historical returns (which can be seen as a discrete episodic memory). As shown in both Figure 2 and Figure 4, although SIL improves over TD3, it only has marginal improvement. On the contrary, our algorithm improves significantly over TD3.

To understand the contribution of implicit planning, we compare with a variant of our method that uses $\lambda$-return rather than taking the maximum over different steps. We also compare our method with Optimality Tightening (He et al., 2017), which shares the similar idea of using trajectory-based information. As Figure 4 shows, Our method outperforms both methods, which verifies the effectiveness of implicit planning within memories.

To check the contribution of our twin network and conservative estimation, we compare the results without the twin back-propagation process and the results without asymmetric losses. The result and the estimation error are summarized in Figure 4. We can see that overestimation is severe without TBP or conservative estimation, and the performance is greatly affected, especially in games like Humanoid. In these games, the living condition for the agent is strict; thus overestimation is more severely punished.

To understand the contribution of the ensembling effect in our method, we compare our result with random ensembling as used in Chen et al. (2021), since we are not able to directly remove TBP while still using all four networks. We use the same update-to-data ratio as in GEM for a fair comparison. As Figure 4 shows, naive ensembling contributes little to performance, and overestimation reduction contributes much more than the ensembling effect.

From these comparisons, we can conclude that our generalizable memory aggregates return values much more effectively than directly using historical returns, and the twin back-propagation process contributes to the performance of GEM significantly. In addition, we verify that the merits of the twin back-propagation process mainly come from overestimation reduction rather than ensembling.