Adaptive Estimation Q-learning with Uncertainty and Familiarity

1 Introduction

Off-policy deep reinforcement learning algorithm is widelyused in continuous control tasks. Recent off-policy methods typically utilize actor-critic framework to pursue sampling efficiency, including Deep Deterministic Policy Gradient (DDPG) [Lillicrap et al., 2015], Twin Delayed Deep Deterministic Policy Gradient (TD3) [Fujimoto et al., 2018] and Soft Actor Critic (SAC) [Haarnoja et al., 2018], etc. However, these successful methods usually fail in Q-value estimation. Q-value is essential for reinforcement learning, and it estimates how good a state-action pair is. Moreover, the policy network is trained by directly maximizing the expected Q-value commonly. Therefore, accurate Q-value estimation is critical to training stability and the final performance.

The overestimate bias problem has been widely studied. van Hasselt et al. [van Hasselt et al., 2016] reveal that single Q function estimator may lead to overestimation problem and propose Double DQN algorithm to alleviate it. It introduces another Q network to decouple action selection and value estimation. DDPG follows the similar target of Q

∗Corresponding Author

function as Double DQN and uses noised deterministic policy gradient with the actor-critic framework to solve continuous control tasks, but unfortunately, DDPG still has overestimation problem. TD3 [Fujimoto et al., 2018] further reduces the overestimation by taking the minimum value over two separate Q-value estimators, but this leads to underestimation issue [Ciosek et al., 2019]. Inspired by TD3, many methods can further address this issue by using other operators including max [van Hasselt et al., 2016], average [Anschel et al., 2017], and softmax [Pan et al., 2020], etc., or ensemble estimator [Agarwal et al., 2020; Chen et al., 2021; Lan et al., 2020].

Recent methods can even maintain the estimation bias within a small range for most of the training time [Chen et al., 2021]. It seems the over- or underestimation bias has been well-studied, and current methods all struggle to get an accurate estimation which is in fact impossible theoretically [Thrun and Schwartz, 1993]. However, none of these methods focuses on how to estimate specific state-action pair properly to improve performance. Both over- and underestimation bias may improve learning performance, depending on the different state or situation [Lan et al., 2020]. In some cases, overestimation can help policy to be more optimistic to explore the high-value regions, and underestimation can prevent the policy from going into risky regions [Ciosek et al., 2019].

In this paper, we propose a novel method called Adaptive Estimation Q-learning (AEQ). Based on a relatively accurate Q-value estimation, we dynamically control Q-values through uncertainty and familiarity to over- or underestimate a specific state-action pair relatively. Uncertainty gives the epistemic uncertainty of state-action pairs, which can naturally serve as an upper or lower bound for ensemble Qlearning. Therefore, it keeps that the estimations of Q-values are close to the real Q-value in AEQ. Familiarity measures the potential novelty of state-action pairs and identifies experiences that may have higher returns. If the familiarity of an experience is low, the novelty of this experience is likely to be high. When low familiarity encounters with worse action, the uncertainty will give a penalty firstly. We can also consider it an optimistic estimate if uncertainty does not work either. Besides, familiarity can dynamically change with the sampling of experiences and the training process of learning, so it can control the estimation of Q-value to be overestimated or underestimated relatively when combined with uncertainty.

We integrate AEQ to TD3, and evaluate it on a series of continuous control tasks from OpenAI Gym [Brockman et al., 2016]. The results show that AEQ-TD3 outperforms the current state-of-the-art algorithms without tuning environment-specific hyperparameters. Further, we apply AEQ to SAC and set the Update-To-Data (UTD) ratio to 20 as REDQ [Chen et al., 2021], the experiments suggest that AEQ-SAC can exceed REDQ. We also conduct ablations to show our adaptive estimation is effective and robust. To ensure that our results are convincing and reproducible, we will open-source the code.

To sum up, our main contributions are as follow:

• We propose Adaptive Estimation Q-learning, which is the first method that can dynamically control Q-values through uncertainty and familiarity to over- or underestimate a specific state-action pair.
• We prove the property of our familiarity term and the role it plays in controlling the bias.
• We show AEQ is sample efficient and outperforms the state-of-the-art algorithms.
• We demonstrate that AEQ is simple to implement, and is general which can be applied to any off-policy Qlearning algorithm.

2 RelatedWork

Estimation bias in Q-learning. Thrun & Schwartz [1993] first investigate and propose the problem of estimation bias in Q-learning. Double Q-learning [Hasselt, 2010] uses two estimators to solve the overestimation issue, and Double DQN [van Hasselt et al., 2016] applies this approach to DQN. TD3 [Fujimoto et al., 2018] and SAC [Haarnoja et al., 2018] improve the performance of DDPG [Lillicrap et al., 2015] significantly by using clipped double Q-learning in continuous action space. Subsequently, some methods [Zhang et al., 2017; Li and Hou, 2019] weight the minimum and maximum estimations of Q-value. SD3 [Pan et al., 2020] applies softmax operator in updating Q-value to help reducing estimation bias. Recently, many works use ensemble to further reduce estimation bias in order to improve the performance. Averaged-DQN [Anschel et al., 2017] uses the average of multiple Q-value estimations to reduce variance. REM [Agarwal et al., 2020] also uses ensemble Q-value estimations but combines with random convex to enhance generalization in the offline setting. Maxmin Q-learning [Lan et al., 2020] controls over- and underestimation by adjusting the number of Q-value estimators. REDQ [Chen et al., 2021] reduces the variance of estimation bias through minimizing a random subset of multiple Q-value estimations, and uses a high UTD ratio to improve performance. Similar to the ensemble, distributional representation [Kuznetsov et al., 2020; Duan et al., 2021] is another way to address this issue.

Uncertainty with ensemble. Uncertainty estimation has been widely used in reinforcement learning when combined with the ensemble. Bootstrapped DQN [Osband et al., 2016] utilizes ensemble of Q-value estimator to estimate the uncertainty of Q-value to improve exploration. Multiple Qvalue estimations can also enhance exploration by applying the principle of optimism in the face of uncertainty [Ciosek et al., 2019; Chen et al., 2017]. SUNRISE [Lee et al., 2021] uses uncertainty to get the upper confidence bound (UCB) of Q-values to choose action. EDAC [An et al., 2021] leverages uncertainty with diversified Q-ensemble to penalize out-ofdistribution data points.

Novelty exploration. Most exploration strategies try to approximate the novelty of the visited state in different ways. Count-based methods [Bellemare et al., 2016; Tang et al., 2017] count how many times a state has been encountered probably to generate intrinsic rewards. In this paper, we use a simpler count-based technique to get the familiarity of a state-action pair to adjust the estimation of Q-value. Dynamics model [Pathak et al., 2019] and random network [Burda et al., 2019] can also be used to predict whether similar states have been visited. Recently, some works [Conti et al., 2018; Cideron et al., 2020] of evolutionary reinforcement learning also use the Quality-Diversity algorithms to deal with the exploration-exploitation trade-off.

3 Preliminaries

The standard reinforcement problem can be considered as a Markov decision process (MDP), defined as 〈S,A,P, r, γ〉, with the state and action space S and A, the reward function r, the transition probability P, and the discount factor γ ∈ (0, 1]. The goal of reinforcement learning is to find the optimal policy π∗ to maximize the expected discounted return Eπ[∑∞t=0 γ t rt].

DDPG [Lillicrap et al., 2015] is a widely-used off-policy algorithm based on actor-critic framework. It learns a deterministic policy πφ(s) which is as effective as stochastic policy in continuous action space. The actor parameter φ can be learned using Eq.(1).

where B is the replay buffer. The critic parameter θ can be learned by minimizing the

where y = r + γQ′θ′ (s′ , πφ′ (s′ )) is the target value. TD3 [Fujimoto et al., 2018] is an improved algorithm of DDPG, it uses clipped double Q-learning with two independent critics to obtain target value y = r + γ mini=1,2 Q′θ′i (s′ , πφ′ (s′ ) + ϵ) , but still directly applies the mean squared error to optimize like DDPG.

4 Adaptive Estimation Q-learning

In this section, we will first introduce the problem of estimation bias in Q-learning, followed by a method using uncertainty to address the estimation bias with ensemble Qlearning. Finally, we present our Adaptive Estimation Qlearning (AEQ) which uses familiarity and uncertainty to obtain an adaptive estimation, and show how to apply AEQ to modern off-policy RL algorithms in practice.

4.1 Estimation Bias Problem

Using neural networks as function approximators to estimate the Q function will lead to unavoidable bias due to inaccuracy of the network [Thrun and Schwartz, 1993]. The study shows the max operator will exaggerate this bias, and this bias will also be accumulated and propagated through temporal difference learning, eventually leads to overestimation [Thrun and Schwartz, 1993; Hasselt, 2010].

Here, we use Qπ (s, a) to denote ground truth of Qfunctions and assume each Qie (s, a) has a random approximation error eisa , where each eisa is identically distributed for each fixed (s, a) pair [Thrun and Schwartz, 1993].

Then, we can define the general updated estimation bias ZN with N estimators for each fixed (s′ , a′ ) pair as follows:

where fop is the operator that decides how to combine these N Q-values. Under the zero-mean assumption, the expected estimation bias of Q is E [Qie (s, a) - Qπ (s, a)] = 0 [Lan et al., 2020; Thrun and Schwartz, 1993]. Therefore, if E [ZN ] > 0, the Q-value will have a tendency of overestimation; and if E [ZN] < 0, the Q-value will have a tendency of underestimation.

If N = 2 and fop is specific to mini=1,2 maxa′∈A, Eq.(4) can denote the updated estimation bias of clipped double Qlearning. Because

E [Z2] < 0, which explains why TD3 and SAC will have an underestimation tendency.

4.2 Ensemble Q-learning with Uncertainty

In the following, we present our AEQ method. AEQ uses multiple estimators of Q functions like Maxmin Q-learning [Lan et al., 2020] and REDQ [Chen et al., 2021], but we use uncertainty and familiarity to get a more accurate and reasonable target.

First, we present how to use uncertainty to penalize the target of ensemble Q-learning which is similar to RAC [Li et al., 2021], and we analyze its motivation and weakness. As mentioned before, the estimation of Q-value is usually biased when using an approximator and the max operator. It is well known that the overestimation is more harmful, so we need to add a penalty term to Q-value estimation, like min. We assume the estimations of multiple Q-value estimators are obeying the Gaussian distribution for a fixed state-action pair.

If we use min to penalize multiple Q-value estimations, it is equal to taking the lower bound of the Gaussian distribution as the estimation, which will lead to potential underestimation (E [ZN ] < 0). In contrast, if we use the mean of multiple Q-values Eq.(6) as the estimation, we will have a potential risk of overestimation, so we can use the standard deviation of the Gaussian distribution Eq.(7) to measure the uncertainty, and this uncertainty can naturally become the penalty term.

where ¯Qθ′ (s′ , a′ ) is the mean of target Q-value estimations. Therefore, the update target of critics is:

We find that using the target above is better than the usual min function, because we can control the Q-value estimation between overestimation and underestimation by adjusting the β, which is similar to the weighted DDPG [He and Hou, 2020], but the adjustment range is more flexible than the weighted DDPG, which is more helpful to obtain an accurate Q-value. Further, we can get the updated estimation bias following [Li et al., 2021]:

where β is the hyperparameter to control the penalty term.

We find that the updated estimation bias is related to β which is constant, which leads to a critical problem. In general, the uncertainty of estimations of multiple critics is getting smaller after training the same state-action pair several times, which leads to this penalty term being smaller with the training process gradually. Due to the Eq.(9), this will lead the overestimation. Therefore, we need to add an additional term to neutralize the effect of the standard deviation term, which is the familiarity term we will introduce in the next subsection.

4.3 Adaptive Estimation with Familiarity

In this subsection, we will show how familiarity can further adjust the penalty term and over- or underestimate specific state-action pair. In this paper, we use a simple way to calculate familiarity which is similar to count-based methods. We add a count record c in the tuple (s, a, r, s′ ), which is initialized to 0 for each experience when it enters the replay buffer. Every time the experience is sampled, this record value will increase to track the number of times the experience is sampled. In addition, at each sampling, we also record the maximum count value cmax through the training and calculate the familiarity of each experience based on this value. When v ≤ i ≤ t < i +N, F i (t) is defined in Eq.(10).

where i is the number of time steps when the experience is generated, t is the number of time steps, v is the number of time steps to start sampling from the replay buffer, and N is the capacity of the replay buffer. The calculation of Eq.(10) can be divided into two cases according to whether the replay buffer is full or not. It calculates the ratio of sampling times between experience i and the experience with maximum sampling times, and these two denominators indicate the historical maximum of c in replay buffer for t ≤ N and t > N respectively. In addition, we use ci - 1 to make the F i = 0 when the experience is sampled in the first time.

Then, we combine familiarity with uncertainty, so that they can control the estimation of Q-value jointly:

where the first penalty term only contains uncertainty, and βb is used to control its weight; the second penalty term consists of the product of uncertainty and familiarity, and βs can control its weight.

Theorem 1. For any s, a, i, 0 ≤ F < 1, and the expected F i will increase with the number of training steps t grows through its life time.

Based on the property of familiarity above, the familiarity is small when the experience first enters the replay buffer, which means the penalty term will be small, making the experience be overestimated. As the number of sampling times of experience gradually increases, the familiarity will also increase, making the experience receive an appropriate underestimation.

According to Section 4.1, we can conclude the updated estimation bias when combining familiarity and uncertainty:

Based on Eq.(12), we prove that our method can reduce the bias of Q-learning to 0 under specific conditions.

Theorem 2. For any s′ , a′ , there exists a F0 satisfying Eq.(13), E [ZN ] ≈ 0.

Algorithm 1 AEQ-TD3

• 1: Initialize actor network πφ andwith parameter φ, N critic network Qiθ with parameter θi, where i ∈ 1, ..., N
• 2: Initialize target actor network πφ′ with parameter φ′ ← φ, N target critic network Qiθ′ with parameter θ′i ← θi, where i ∈ 1, ..., N
• 3: Initialize experience replay buffer B
• 4: for t = 1 to T do
• 5: Select action with exploration noise at ∼ πφ(st) + ϵ, ϵ ∼ N(0, σ), and observe reward rt and new state st+1
• 6: Store transition tuple (st, at, rt, st+1, 0) in B
• 7: Sample mini-batch of N transitions (s, a, r, s′ , c) from B
• 8: Update the corresponding c ← c+1 for each sampled experience
• 9: Compute familiarity F for each sampled experience using Eq.(10)
• 10: Compute the Q target y using Eq.(11)
• 11: for i = 1 to N do
• 12: Update critics by minimizing Eq.(2)
• 13: end for
• 14: if t mod d then
• 15: Update actor using Eq.(14)
• 16: Update target networks: θ′i ← τθi+(1-τ)θ′i , φ′ ← τ φ + (1 - τ )φ′
• 17: end if
• 18: end for

The approximation sign of Eq.(13) is due to the sample based mean and variance. Although the conditions above can not always meet usually, our method can still give an appropriate estimation of Q-value for specific state-action pair. When the critics have a large uncertainty about a new experience, the overestimation can improve the exploration; when an old experience has a large uncertainty, we believe that the state-action pair of this experience contains high risk, the underestimation can prevent the agent from entering an unstable state and improve the robustness.

4.4 Applying AEQ to TD3 and SAC

We apply AEQ to TD3 [Fujimoto et al., 2018] called AEQTD3 and it uses actor-critic framework but with N critics. These N critics are initialized differently but are trained with the same target value Eq.(11). The actor is trained by the deterministic policy gradient with the average Q-value of N critics:

6000

Besides, we do not modify any other part of TD3, the procedure of AEQ-TD3 is summarized in Algorithm 1.

We also apply AEQ to SAC [Haarnoja et al., 2018] called AEQ-SAC. Like REDQ [Chen et al., 2021], AEQ-SAC employs a UTD = 20 to improve sample efficiency during training. Instead of using two randomly selected critics to calculate the target, AEQ-SAC uses Eq.(11) to be the target of N critics. The pseudo-code of AEQ-SAC is shown in Appendix.

5 Experiment

We evaluate our method on a range of MuJoCo [Todorov et al., 2012] continuous control tasks from OpenAI Gym [Brockman et al., 2016]. We implement our methods on TD3 [Fujimoto et al., 2018] and SAC [Haarnoja et al., 2018] as AEQ-TD3 and AEQ-SAC respectively 1 . For AEQ-TD3, we use N = 2 and N = 10 critics with three hidden layers, βb = 0.5, βs = 0.5 for every tasks, and UTD = 1 for fair comparison. For AEQ-SAC, we use N = 10 and UTD = 20 to compare with REDQ [Chen et al., 2021]. For simplicity, we will use G instead of UTD ratio in subsequent. The plots of experimental results are generated by rl-plotter 2 .

The details of the experimental setup and additional results can be found in Appendix.

5.1 Comparative Evaluation

We compare our methods with the state-of-the-art algorithms.

1 Implementations and appendix are available at: https://github. com/gxywy/AEQ

2 https://github.com/gxywy/rl-plotter

For AEQ-TD3, we compare it with PPO [Schulman et al., 2017], TD3, and SAC on five continuous control tasks: HalfCheetah, Ant, Walker2d, Hopper, and Swimmer. The time steps of each algorithm on each task is 2 × 106 .

For AEQ-SAC, we compare it with SAC, SAC20 [Chen et al., 2021], REDQ, and TQC20 [Kuznetsov et al., 2020; Li et al., 2021] on two challenging continuous control tasks: Ant and Walker2d. The time steps of each algorithm on each task is 3 × 105 following REDQ's setting.

The learning curves are shown in Figure 1 and Figure 2. Each curve is the average result of 5 random seeds with the shaded area of the standard deviation. We evaluate the performance of each algorithm every 5000 steps, and each evaluation is the average of 10 episodes. In Table 1 and Table 2, we also report the average and the standard deviation of last 10 evaluations with 5 random seeds each algorithm. As the results shown, it is obvious that our AEQ-TD3 achieve the best performance. Even if we set N = 2, our results can still outperform TD3 on every task. When G = 20, our AEQ-SAC also can achieve better sample efficiency than the state-of-the-art algorithmREDQ.

5.2 Ablation Study

We perform ablation experiments on Ant and Walker2d tasks to further analyze the effectiveness of our AEQ target. We build five variants based on TD3 but trained with different target of critic which is shown in Table 3. For all variants, we use the same network structure and N = 10 critics, and for TD3-REDQ-10 variant, we use G = 1 for fair comparison.

The final performance of different variances is shown in Figure 3 which is normalized using the average final performance of TD3. It suggests that the minimum variants and the mean variants perform poorly when increasing the number of critics N. Although REDQ can reduces the Std. of bias, it does not bring significant increase in sampling efficiency when applied REDQ's target to TD3. However, the result of AEQ-TD3-NF shows that the target with uncertainty penalty performs better. Moreover, when comparing AEQTD3 with AEQ-TD3-RF and AEQ-TD3-NF, it shows our familiarity term can improve the performance on both Ant and Walker2d tasks.

5.3 Effect of Familiarity

In order to study the effect of our familiarity term further, we first select some experiences with the indexes: 0, 105 , 2×105 , 3×105 , 4×105 to track the familiarity F and the number of sampling times c.

In Figure 4, we find all F is increasing with c, and this conclusion is consistent with Theorem 1. The result also suggests the experience that enters the replay buffer first will increase faster in familiarity than the experience that enters the replay buffer later, and the former will also have a larger familiarity in the end. This phenomenon implies that our familiarity will pay less attention to newer experiences and tend to give them less punishment in Q-value estimation.

Then, we study the tendency of our penalty term βbˆσQ′ + βsFˆσQ′ during the training, the results are shown in Figure

5. Overall, our penalty term will increase because the uncertainty in the initial training process of the network, and then decreases due to the neutralization effect of familiarity, and eventually remain almost constant after the training is stable. However, it is just the tendency of the average sampled experiences, which does not mean all experiences follow the same rules, and each experience will have its own tendency in our algorithm. In addition, although our penalty term is changing, the average Q-value keeps increasing, which suggests that our adaptive term does not disturb the training process.

5.4 Estimation Bias

In order to figure out how AEQ estimates in practice, we measure the estimation bias of both AEQ-TD3 and AEQSAC. For AEQ-TD3, the Q-value estimations are averaged over 1000 states sampled from the replay buffer every 50000 time steps. The true Q-values are estimated by averaging the discounted long-term rewards obtained by rolling out the current policy starting from the sampled states every 50000 time steps. The setting above is basically same with the original paper of TD3. The results in Figure 6 show that AEQTD3 will have a large estimation bias in the beginning, but will reduce gradually through training achieving better performance.

For AEQ-SAC, we follow the REDQ's setting of estimating the bias for fair comparison, which the states is not sampled from the replay buffer. The results in Figure 7 show that AEQ-SAC controls the estimation bias better and is close to 0. Moreover, AEQ-SAC can adjust the estimation bias dynamically.

5.5 Hyperparameter Sensitivity

The hyperparameter βb and βs will directly affect the weight of familiarity term and the estimation of Q-values. Therefore, we study the sensitivity of βb and βs on HalfCheetah task and we choose them from [0.1, 0.3, 0.5, 0.7]. The results are shown in Figure 8, which indicates the performance of AEQTD3 always better than TD3 in 4 tested βb and βs. The results also suggest that βb and βs should not too large or too small to keep the penalty term and adaptive term in a certain range. Besides, the sensitivity to βb and βs indicates in part that the uncertainty and familiarity term we proposed is effective.

6 Conclusion

In this paper, we present AEQ that controls the over- and underestimation bias for specific state-action pair adaptively using uncertainty and familiarity. Our method is simple to implement on any off-policy actor-critic RL algorithm, including the most commonly used TD3 and SAC. We not only analyze the property and the effect of familiarity theoretically, but also perform the ablation experiments to demonstrate it can improve the performance with the uncertainty. The results on continuous control tasks suggest that our AEQ can be useful in controlling the estimation bias and can outperform the state-of-the-art performance on sample efficiency.

We think future work should combine familiarity with the density model and focus on investigating how to find a more appropriate metric to over- and underestimate for specific state-action pair.

Acknowledgments

We sincerely thank the anonymous reviewers for their careful work and thoughtful suggestions, which have greatly improved this article. This work was supported by the Natural Science Research Foundation of Jilin Province of China under Grant Nos. 20220101106JC and YDZJ202201ZYTS423, the National Natural Science Foundation of China under Grant No. 61300049, the Fundamental Research Funds for the Central Universities (Jilin University) under Grant No. 93K172022K10, the Fundamental Research Funds for the Central Universities (Northeast Normal University) under Grant No. 2412022QD040, and the National Key R&D Program of China under Grant No. 2017YFB1003103.