Faster Reinforcement Learning with Value Target Lower Bounding
Authors: Le Zhao
Wei Xu
Venue: Submitted to ICLR 2023 (2023)
Keywords: Reinforcement Learning
Bellman equation
value improvement
sample efficiency

Abstract: We show that an arbitrary lower bound of the maximum achievable value can be used to improve the Bellman value target during value learning.  In the tabular case, value learning using the lower bounded Bellman operator converges to the same optimal value as using the original Bellman operator, at a potentially faster speed.  In practice, discounted episodic return in episodic tasks and n-step bootstrapped return in continuing tasks can serve as lower bounds to improve the value target.  We experiment on Atari games, FetchEnv tasks and a challenging physically simulated car push and reach task.  We see large gains in sample efficiency as well as converged performance over common baselines such as TD3, SAC and Hindsight Experience Replay (HER) in most tasks, and observe a reliable and competitive performance against the stronger n-step methods such as td-lambda, Retrace and optimality tightening.  Prior works have already successfully applied a special case of lower bounding (using episodic return), but are limited to a small number of episodic tasks.  To the best of our knowledge, we are the first to propose the general method of value target lower bounding (with possibly bootstrapped return), to demonstrate its optimality in theory, and effectiveness in a wide range of tasks over many strong baselines.

Under review as a conference paper at ICLR 2023
FASTER REINFORCEMENT LEARNING WITH VALUE TARGET LOWER BOUNDING
Anonymous authors Paper under double-blind review
ABSTRACT
We show that an arbitrary lower bound of the maximum achievable value can be used to improve the Bellman value target during value learning. In the tabular case, value learning using the lower bounded Bellman operator converges to the same optimal value as using the original Bellman operator, at a potentially faster speed. In practice, discounted episodic return in episodic tasks and n-step boot- strapped return in continuing tasks can serve as lower bounds to improve the value target. We experiment on Atari games, FetchEnv tasks and challenging physi- cally simulated car push and reach task. We see large gains in sample efficiency as well as converged performance over common baselines such TD3, SAC and Hindsight Experience Replay (HER) in most tasks, and observe a reliable and competitive performance against the stronger n-step methods such td- td-lambda. Retrace and optimality tightening. Prior works have already successfully applied a special case of lower bounding using episodic return, to a limited number of episodic tasks. To the best of our knowledge, we are the first to propose the gen- eral method of value target lower bounding with possibly bootstrapped return, to demonstrate its optimality in theory, and effectiveness in wide range of tasks over many strong baselines.
INTRODUCTION
The value function is key concept dynamic programming approaches to Reinforcement Learn- ing (RL) (Bellman| 1957p. Given starting state, the value function estimates the sum of all fu- ture rewards (usually time-discuunted). In temporal difference (TD) learning, the value function is adjusted toward its Bellman target which simply adds the reward of the current step with the (dis- counted) value of the next state (Sutton & BBarto 2018). This forms the basis of many state of the art RL algorithms such DQN (Mnih al. 2013). DDPG (Lillicrap al. 2016). TD3 (Fujimoto ct al. 2018). and SAC (Haarnoja et al. 2018).
The value of the state is typically estimated derived from the value function itself, which is being actively learned during training, process called "bootstrapping". The bootstrapped values can be random and far from the optimal value, especially at the initial stage of training, or with sparse reward tasks where rewards can only be achieved through long sequence of actions. Consequently, the Bellman value targets as well as the learned values are usually far away from the optimal value (the value of the optimal policy).
Naturally, this leads to the following idea: value, we may speedup TD learning. For example, we know that the optimal value is just the expected discounted return of the optimal policy, which always upper bounds the expected return of any policy. For episodic RL tasks, could use the observed discounted return up to episode end from the training trajectories to lower bound the value target. When the empirical return is higher than the Bellman target, lower bounding brings the new value target closer the optimal value.
If we can make the value target closer to the optimal
For continuing or non-episodic tasks, is less clear how a lower bound may be estimated. When a continuing task return negative rewards, lower bound may not even exist. One could use the n-step bootstrapped return as a lower bound, but bootstrapped return can overestimate and be greater than the optimal value. It is unclear whether the resulting algorithm will still converge.

---

Under review as a conference paper at ICLR 2023
Algorithm 1 Value iteration with value target lower bounding
Input: Finite MDP p(s', rls,a), convergence threshold 8, lower bound f(s) of the maximum achievable value ('(s)
Output: State value v(s)
v(s) +-0 0
repeat
A --0 0
pp(s) f- v(s)
for each state s do
ö(s) - max ,,, p(st,r/s,,)) rxp()))
(s))) f max (f(s),(s)
0(8) ús(s)
< max (A, (u(s) - - (s))
end for
until A <
This work presents a general framework proving that value target lower bounding converges to the optimal value for both the episodic and non-episodic cases, under certain conditions for the lower bound function. We demonstrate faster training with an illustrative example and extensive experiments variety of environments over strong baselines.
2
THEORETICAL RESULTS FOR THE TABULAR CASE
Here we show for the tabular case, arbitrary functions below a certain bootstrap bound can be used lower bound the value target still converge to the same optimal value.
2.1 BACKGROUND
In finite MDPs with limited number of states and actions, a table can keep track of the value of each state. Using dynamic programming algorithms such value iteration, values are guaranteed to converge to the optimum through Bellman updates (Chapter 4.4 (Sutton & Barto 2018))
The core of the value iteration algorithm (Algorithm) T B(v), where v(s') is the bootstrapped value:
is the Bellman update of the value function,
((v)(s) = max Σ p(sss +
Here a is an available action in state 8. 8' is the resulting state, and r the resulting reward, of executing in 8, with p(8', rrss being the transition probability.
is well known that the Bellman operator, B, is a contraction mapping over value functions (Denardo) 1967). is, for any two value functions 01 and 12 [I (((()))B())))l S STلle - loo for the discount factor 7 E [0, 1) and || == max; [za] (the Loo norm). This guarantees that any value function under the algorithm converges the optimal value 8 (=0(w) (v)
((2)))loo
2.2 CONVERGENCE OF VALUE TARGET LOWER BOUNDING
Definition 2.1.
The expected n-step bootstrapped return for a given policy æ and value function v(s) defined as the expected bootstrapped return of taking n steps according to policy m:
G (so) ET (ri
n-1 rn (((ss))
Here, the step rewards r; and the resulting n-th step state s, are random variables, with the expecta- tion E taken all possible n-step trajectories under the policy and the given MDP.
For the gist of the proof, for example page of h/tps::/peopp e.cec. www.eerrkeeee....k werkeley.ed. edu "pabbee1 / www.:/actureeaanneeeeere htt.r//eeeerrre//ectcrreeeeopppp
2

---

Under review as a conference paper at ICLR 2023
Definition 2.2. Given the current learned value function v(s), policy class II, the maximum achiev- able value of a state s is defined as:
G (s) nET),
G
(3)
This is tight definition of maximum because for each state 8, a different policy T(s) and a different number of steps (s) can be used to achieve the maximum (s). the maximum achievable bootstrapped return of any single policy or any mixture of policies for any number of steps.
The theorem below says any function not exceeding the maximum achievable value can be used to lower bound the value target, and still achieve the optimal value in convergence.
Theorem 2.3. Under the same assumptions for Bellman value contraction, for any function that lower bounds the maximun achievable value, i.e. vss, fs) S (s), if we define the lower bounded Bellman operator as B = max(B(u), then B (v) = (x(().
Note, the value v(s) and the bootstrapped value can be inaccurate, and even above the optimal value. As consequence, when n is finite, the maximum achievable value (*(s) (and f) can be above the maximum expected return (i.e. the optimal value). On the other hand. when n is sufficiently large, the effect of the bootstrap value uss,,) diminishes (see Equation 2). and the maximum achievable value becomes the maximum expected return (i.e. the optimal value). Therefore, Vs, G*(s) is no smaller than the optimal value 8 (s).
As special case of the theorem, as long is below the optimal value, value target lower bounding converges correctly:
Corollary 2.4. If function f lower bounds the optimal value, ie. vs, f(8) B7 (c) B (v))...
B (v)(s), then
few things to note about the proof of Theorem 2.3 (included in Appendix A.1
First, this only proves convergence, not contraction under the original || 02 lo metric. In the case of the Bellman operator, contraction shows that Vo,, 1/ value functions, [|B((1)) - (l2)) S allui - 02lloc. Here, for value target lower bounding, what's proved convergence o" at a rate of not contraction. There can be counter examples where the distance between 01 and 02 under one application of By can increase in the original Loe metric space, even though U1 and d2 are both getting closer to x² at rate of 7/ One difficulty caused by convergence instead of contraction is that the stopping criterion in Algorithm (A < 0) no longer works, due to the inaccessible v* during learning. In practice, this may not be a serious concern, people often train algorithms for fixed number of iterations or time steps.
Second, based on the proof, the new algorithm is at least as fast as the original. When the lower bound actually improves the value target, i.e. f(s) > B(vi) (s), there is chance for the convergence to be faster. Convergence is strictly faster when the lower bound f has an impact on the Lox distance between the current value and the optimal value, i.c. it increases the value target for the states where the differences between the current value and the optimal value are the largest.
Third, the lower bound function doesn't 't have to be static during training. As long as there is a single if during each training update, convergence is preserved.
The following sections detail how to compute lower bounds of the maximum achievable value (Sec- tion 3) how to integrate the lower bounds into state of the art RL algorithms (Section 4 and provide an illustration how this method may benefit value learning in practice (Section
EXAMPLE LOWER BOUND FUNCTIONS
We show a few cases where lower bound functions can be readily obtained from the training expe- rience. Future work may investigate alternatives.
3

---

Under review as a conference paper at ICLR 2023
3.1 EPISODIC TASKS
In episodic tasks, discounted return is accumulated up to the last step of an episode. During training, wait until episode ends, and compute discounted returns for all time steps. To make more efficient, we compute and store the discounted return for each time step into the replay buffer, and read it out when the experience is used in training, which adds very little computation to the baseline one-step TD learning.
(80)
Σ r'r(si,;)) 10.0.000
(4)
We call this variant "Ib-DR", short for lower bounding with discounted return.
3.1.1 EPISODIC WITH HINDSIGHT RELABELED GOALS
In goal conditioned tasks, one helpful technique is hindsight goal relabeling (Andrychowicz et al., 2017]. It takes future state that d time steps away from the current state as the hindsight relabeled goal for the current state. When the goal is reached, reward of 0 is given, otherwise a -1 reward is given for each time step.
In this case, know it took d steps to reach the hindsight goal, so the discounted future return is:
f(so) = Σ -1y
d-1
(5)
=- --1 /11(11)))
This calculation can be done on the fly hindsight relabeling happens, requiring no extra space and very little computation.
We call this variant "Ib-GD", short for lower bounding with goal distance based return.
Additionally, we can also apply lb-DR and lb-GD together, with discounted episodic return (Ib- DR) on the original experience and goal distance based return (lb-GD) on the hindsight experience, giving the "Ib-DR+GD" variant, which was used in Fujita et al. (2020).
3.2 IN GENERAL (INCLUDING NON-EPISODIC TASKS)
If the task is continuing, without an episode end discounted return needs to be accumulated all the way infinity. When rewards are always non- negative, one can still use the accumulated discounted reward of the future n-steps to lower bound the value. But accumulated n-step discounted reward no longer a lower bound when rewards can be negative, which case, the more general lower bounding with bootstrapped return can be used: given trajectory of training experience 80:
+ 72 + + - rn + ((nn)
(6)
In this case, two variations are possible: Given a trajectory of length n,
1. compute u(s;) for all i [1, n] and take the maximum of all (T) obtain tighter lower bound. We call this variant "Ib-b-nstep":
((00 max 1E(1.n)
(T)
2. only evaluate on the last (i.e. the nih) step and use the ntt-ssee bootstrapped return as the lower bound, which involves less compute but results in a looser bound. (When n is large enough, this becomes the lb-DR variant.) We call this variant "bb-b-nstep-only".
[(x0) = G (T)
(8)
Chapterr 3.3 of Sutton& Barto 2018 has details on episadic vs continuing tasks.
4

---

Under review as a conference paper at ICLR 2023
The general bootstrapped returns allow lower bounding be applied non-episodic tasks, with bit extra computation in the case of lb-b-nstep-only. to evaluate value on the nith step. The cost can be high for a large for the lb- lb-b-nstep variant, but still comparable to typical n-step return based methods like td- id-lambda.
4 INTEGRATION INTO RL ALGORIHHM
4.1 BACKGROUND
The value target lower bounds can be readily plugged into TD learning based algorithms that regress value to a target, e.g. DQN, DDPG or SAC.
In these algorithms, the action value (s,, a) is learned through squared loss with the target value In one step TD return, for batch B of experience {s, + r, s', the loss is:
Lg
Σ (s,a,n""))
la(3,a) y/²
(9)
In one step TD return, y the one step TD return ((,,
(s),, +g ks()))
(10)
Here, o' and μ' are the bootstrap value and policy functions, typically following the value and policy functions in a delayed schedule during training. (They are also called "target value" and "target policy", and are very different from the "value target" y in this paper.)
4.2 VALUE TARGET LOWER BOUNDING
With lower bounding, replace the value target with the lower bounded target:
max(f,r (s' ((()))
(1I)
but is subtly and importantly different from lower bounding the q value directly (Oh al. 2018 Tang 2020 g(8, a) <- max(ʃ, q(8, a)). which stays overestimated if q(s, a) initially overestimates.
This way of lower bounding the value target is the same as was done by Fujita et al. (2020).
Fujita et al. (2020) only used episodic return lower bound the value target, while we introduce the general framework of lower bounding with possibly bootstrapped return.
4.3
AN ILLUSTRATIVE EXAMPLE
Figure I inclludes a fairly general example showing how value target lower bounding would improve value learning. Suppose we enhance an off policy algorithm such as DDPG with value target lower bounding (Ib-DR), when there is no training experience hitting the target state, no meaningful train- ing happens for the baseline lb-DR. However, when there one trajectory hitting the target state, all states along the trajectory will soon be propagated with meaningful return, and nearby states will also enjoy faster learning. As the state space becomes larger and the time horizon longer, successful trajectory will speed up learning quite bit.
At the core of the above illustration is this simpler example: Consider simple chain states 81 to 8n, with 8; going to 81+1- It emits reward I and terminates when the agent is at the end of the chain, state 8x, and emits reward 0 elsewhere. Suppose we have already collected an experience of traversing the chain once, and start training with zero initial value. The basic value iteration algorithm would back up the reward just one step along the chain for each iteration of training, converging in iterations. However, value target lower bounding trains much faster. Given the collected experience, we precompute the empirical return of each state G(s,) = -== which is also the optimal value. Thus, one training iteration already populates all states with the optimal value.
5

---

Under review as a conference paper at ICLR 2023
Baseline: 0
Baseline: 1
Baseline: 2
Baseline: 3
Lowerbound 0
Lowerbound
Lowerbound
Lowerbound
Figure Illustration of value target lower bounding speeding up value learning as training pro- gresses from stages 0 to 3. The task is to navigate in the state space from start state S to end state T, with sparse reward at T and 0 elsewhere. The curve from denotes training experience that reaches the target. The shaded areas denote states with high value.
5 EXPERIMENTS
The goal is demonstrate the sample efficiency of lower bounding the value target over baseline such as DDPG, TD3, SAC and HER. Because the lower bounded value target can now look many steps into the future, we expect it to be better suited for long horizon, sparse reward tasks. Hence, we choose to experiment on sampled subset of Atari games, the goal conditioned FetchEnv tasks and the harder goal conditioned Pioneer Push and Reach tasks. See details of the experiment setup in Appendix A.2
5.1 BASELINES
Baselines include DDPG (Lillicrap et al. 2016). TD3 (Fujimoto et al. 2018), SAC (Haamoja et al., 2018) and HER (Andrychowicz et al. 2017; Plappert al.) 2018). Implementations are based on open sourced repositories, and baseline performance is verified against published results under similar settings. The Appendix 6. and A.5
include results on more basclines such as DDQN (van Hasselt et al. 2015), td-labmda (Sutton & Barto 2018) and Retrace (Munos et al. 2016).
5.2 HYPERPARAMETERS
Value target lower bounding is applied top of these baselines without any additional hyperpa- rameter (Section 4 The only hyperparameters come from the baselines. These hyperparameters follow published work much possible. When baseline hyperparameters need to be tuned for an environment, e.g. Atari games or Pioneer tasks, we search for the best performance in total episode reward averaged across all tasks for that environment hyperparameters are fixed and evaluated on a separate set of random seeds never seen during devel- opment. Value target lower bounding simply uses the the parameter values optimal for the baselines. Details are in Appendix A.3
of random seeds, then the optimal
5.3 RESULTS
We report results on both episodic and continuing/non-cpiseee tasks. We report evaluation perfor- mance averaged across several runs the algorithms (five the less stable Atari games and three for the others). Each run uses random seed never seen during development. Due to space con- straints, the main paper only reports performance aggregated across all tasks for each environment. During each we take one task and one random seed, run baseline and treatment algorithms, and record whether treatment agent evaluates strictly above the baseline agent as training progresses. We average across all the runs of the same environment, and plot the fraction of times where treatment contaniiin
above baseline and when it is statistically significant in Figure 2 Appendix A.4 contains per task evaluation eurves.

---

Under review as a conference paper at ICLR 2023
10
5-01-00 -gritiin Vale dion
02
(a) Atari (lh-DR) (b) Atari (bootstrapped) (c) FetchEny (episodic)
(d) Pioneer
Aggregated evaluation performance: The fraction of times where treatment performs strictly above baseline, plotted along the number of time steps used for training. The fraction being above 0.5 means treatment more often better. We use, for Atari (Ib-DR), 85 runs 17 games each with 5 seeds, for Atari (bootstrapped), 20 runs 4 games 5 seeds, for episodic FetchEnv, runs 3 tasks 3 seeds, and for Pioneer, 6 runs 2 tasks 3 seeds. Statistical significance is calculated with one sided sign test at significance level p < 0.05.
Figure 2:
1,00
BUN JUIT beraarage
BOGHAA pott arage
424
3.00
33m
004
000
022
84
06
35
300
(a) Atari (lb-DR)
(b) Atari (bootstrapped)
(c) FetchEnv (episodic)
(d) Pioneer
Average fraction of training experience where lower bounding improves Bellman value target, plotted along the number of iterations of training. The solid curve is the average of the fraction across all runs number of tasks times number of seeds, and the shaded area is +/- one standard deviation. Other setups are the same as Figure 2
Figure 3:
5.3.1 LOWER BOUNDING VS BASELINES SAC/DDPG/HER
Figure compares the lower bounding treatment with SAC, DDPG or HER baseline on 17 sam- pled Atari games, the FetchEnv tasks and the Pioneer tasks. For all the environments, value target lower bounding is not only more sample efficient, but also enjoys a higher converged performance. After training starts, it quickly gains ground and outperforms the baseline for 70% to 100% of the runs. It keeps that advantage even at the end of the training, outperforming baseline in converged performance. These plots show most of the times treatment above bascline, and during most of the training process, the improvement is statistically significant.
Appendix A.4 shows the magnitude of change with total episode return plotted for each task. There is often large gains in sample efficiency and sometimes much higher converged performance. Among all the 22 tasks, only one task (Atari Breakout) shows Ib-DR underperforming the baseline.
Investigations show that the loss on Atari Breakout is likely due to the mismatch between train- ing objective and evaluation metric. During training, raw rewards are clipped to [-1, 1] and step discounted at y 0.99 to compute value, while in evaluation, total reward is the unclipped and undiscounted sum of all episode rewards. The discount and clipping together severely penalizes large rewards earned later in the episode, which is what's 's happening for Breakout, because hitting top layer block produces a reward of while hitting a bottom layer block produces only 1. When we non-clipped rewards or higher y in training, the lower bounding method performs much better in total reward. This train-test discrepancy and another bias of not discounting the state distribution Thomas 2014) are likely present in prior works using policy gradient methods on Atari games.
7

---

Under review as a conference paper at ICLR 2023
5.3.2 VALUE TARGET IMPROVEMENT
The Ib-DR method is mostly effective, but is it really due to improvements to the value targets? Figure looks at the fraction of training experience where lower bounding actually improves the Bellman value target over the course of training. Overall, improved value target roughly coincides with performance gains. Appendix shows the plots per each task.
The Appendix also has more results, comparing with baselines such as n-step methods, DDQN and optimality tightening, and more analyses such as ablations and robustness to hyperparameter choices.
RELATED WORKS
Prior works (Fujita al., 2020 Hoppe & Toussaint 2020 He al., 2017 Oh et al. 2018 Tang 2020) employ several different ways of computing future returns and using that as a lower bound to improve value learning. It is quite easy to introduce biases and inefficiencies into the process and end up with a suboptimal or inefficient algorithm, e.g. see discussion below about Self Imitation Learning and episodic control (Oh et al. 2018 Tang 2020 Blundell et al., 2016), or n-step methods. Our work is the first to propose the general form of value target lower bounding (possibly with bootstrapping) for both the episodic and non-episodic tasks, to show its convergence to the optimal value in the tabular case, and to demonstrate its effectiveness in extensive experiments on wide range of tasks.
Fujita et al. (2020)'s 's method is similar to a special case (the Ib-DR+GD variant) of the general method. It was used as a part of a large system and was shown to improve sample efficiency for robotic grasping task. Hoppe & Toussaint 2020) also bound the value target. But instead of using empirical return, they use a simplified MDP with a subset of actions. Though without the- oretical proof and only experimented on limited set of tasks, both works show that value target lower bounding increases sample efficiency empirically. Our work, in addition to the theory and the more general method, shows that lower bounding improves both sample efficiency and converged performance in wide range of tasks.
Optimality tightening (He al. 2017) also uses empirical return with bootstrap improve value learning, but in different way. It formulates value learning as a constrained optimization problem using the empirical bootstrapped value to provide the lower and upper constraints of the value func- tion. In the experiments, the Lagrangian multiplier is fixed rather than being learnt, which would likely lead to suboptimal solutions. Our Ib-b-nstep method also uses bootstrapped value. We lower bound the value target directly, which is simpler, more efficient, and likely more optimal. Our frame- work includes even more efficient and effective methods like Ib-DR for episodic tasks. Appendix A.5 offers more discussions and results related to the optimality tightening method.
Our work is subtly but importantly different from the prior works on lower bound Q learning or Self Imitation Learning (SIL) (Oh et al.) 2018 Tang 2020). SIL uses empirical return R to lower bound the value function itself (instead of the value target). This is achieved by adding an off policy value loss during on-policy (AC PPO) training (T.sit function overestimates, the SIL value loss becomes zero, and keeps overestimating. Mixing the SIL loss with the loss from the baseline algorithms probably helped correct the overestimation, but no theoretical guarantee was given. In evaluation, SIL was often compared to on-policy Actor Critic or PPO baselines, so it was not clear how much of the gain was due to lower bounding and how much due to off- off-po value learning. In this work, we bound the Bellman value target (Equation IT] so overestimates are automatically corrected via Bellman updates, and convergence is guaranteed in the tabular case. We also use off-policy algorithms as baselines for a cleaner comparison.
2 (l((s)) max(u(s), R) (2). When the value
Episodic control (Blundell et al., 2016) and follow-up works (Lin et al. 2018 Sarrico et al., 2019 Hu et al.) 2021 Ma et al. (022) use episodic memory from past experiences to develop value lower bounds. When multiple experiences start from the same state, the maximum episodic return is stored in the episodic memory slot for that state. This provides potentially tighter lower bound than the episodic return used in this paper (which only uses the episodic return from the one episode where the transition is sampled). During control, the action that maximizes the stored episodic return is picked. For the general non non-tabular case, function approximation is used to represent states, which bootstraps values of states never encountered in training before. The original episodic control and
8

---

Under review as a conference paper at ICLR 2023
few of the variations (Blundell et al.] 2016 Lin al. 2018: Sarrico et al. 2019) lower bound the value function itself, not the value target, similar to how Self Imitation Learning (Oh et al. 2018) does. Hence, an initially overestimated episodic value, due to either improper initialization or function approximation, stays overestimated throughout training, because it never goes through the Bellman operator. These methods may not converge the optimal value even for tabular de- terministic environments. Follow-up works (Hu et al. [021] Ma et al.) 2022) use implicit memory based planning, which essentially lower bound the value target with function based on episodic return, and avoid the earlier overestimation problem (see Appendix (A.8). Maximum entropy Mel- lowmax episodic control (Sarrico et al. 2019) uses a temperature controlled softmax based operator to generate the action probabilities and is similar to the discrete version of SAC. Overall, episodic memory is an interesting tool to come up with tight value target lower bounds, while the value target lower bounding we propose is more general along two directions: the theory works for stochastic environments, and for non-episodic tasks (with experiments in Appendix (A.4.3).
Hindsight Experience Replay (HER) (Andrychowicz et al. 2017 is related prior work to compare to. HER is simple, effective, efficient, and also relies on the unbiased replay of past experiences, as explained in Appendix A.7] HER works best in sparse reward goal conditioned tasks. Unlike our work, HER additionally requires the task to be goal conditioned, and relies on full knowledge of the reward function to work. HER also has one additional hyperparameter to tune the proportion of hindsight experience. Our method is more general, applicable to non-goal conditioned tasks and dense reward scenarios, e.g. Atari games. We employ the orthogonal idea of value target lower bounding to improve RL training, and provide additional significant gains even on top of HER, as shown in the experiments on hard continuous control tasks.
N-step return methods such as td-lambda (Sutton & Barto 2018) and Retrace (Munos et al. 201 6 also look a few steps ahead to obtain a better value. Traditionally, this requires careful off policy correction, and the value can still be far from the optimal value due to the often suboptimal behavior policy. This work shows that value target lower bounding efficiently and effectively looks ahead much further without the need for off-policy correction. Lower bounding with episodic return is also more efficient, without having to compute value of all n-steps. Appendix A.55 has more detailed observations and discussions.
7 CONCLUSIONS
Overall, value target lower bounding is simple method without any additional hyperparameters to tune. It is efficient, highly effective, and theoretically justified. It can be readily applied to any TD learning based RL algorithms, such DQN, DDPG and SAC. In theory, value target lower bounding converges to the same optimal solution as the original Bellman operator, at a speed at least as fast. practice, extensive experiments across a wide range of tasks show that it greatly improves sample efficiency, and in several cases even converge to higher performance.
For episodic tasks, discounted episodic return lower bound is efficient and effective, achieving much higher sample efficiency and converged performance than one-step baselines such as SAC, DDPG or TD3 in most tasks, and is competitive among n-step baselines. For goal conditioned tasks, simple goal distance based return achieves higher value than Hindsight experience relabeling (HER) in difficult long horizon tasks.
For non-episodic tasks or in general, lower bounding with n-step bootstrapped return outperforms one-step baselines and is a strong competitor to the n-step methods such as (truncated) td-lambda and Retrace.
7.1 FUTURE WORK
There could be better value lower bounds that improve training even more. One such direction is to use planning (e.g. Monte Carlo Tree Search, the Cross Entropy Method or using subgoals) to achieve tighter lower bounds with the help of a model of the task.
Other ways of bounding the value target may be worth investigating well. An example is value upper bounding, to reduce value overestimation. However, given the disparate motivation from lower bounding, which is to speed up value improvement, leave upper bounding to future work.

---

Under review as a conference paper at ICLR 2023
ETHICS STATEMENT
This research belongs to basic reinforcement learning, accelerating the training of reinforcement learning algorithms. Helpful agents trained on benevolent tasks will learn faster, will malicious agents trained to do damage. All the usual societal impact of reinforcement learning algorithms apply. The reader and user has to use caution and their own judgments when applying these au- tomation algorithms to the real world: careful testing and scaling is needed, starting from virtual simulations, testing lab environment, to small scale real world tests, and eventually full scale deployment with careful monitoring in place.
REPRODUCIBILITY STATEMENT
Our code change is based on a publicly available RL library, with strong baselines already imple- mented. Our relatively small code change committed to private github repository, which plan to open source upon publication. Experiment parameters are configured and controlled by an au- tomation script, with each experiment label corresponding to the set of configurations used for that experiment, so there is little room for manual error when running many experiments across different tasks, methods and hyperparameters. When running experiments, the snapshot of the code used to run each experiment is stored together with the results for verification.
Experiments are done in simulation with pseudo randomness. We've run our code on different ma- chines with different GPU hardware using the same docker image, and the results are reproducible up to every float number using the same random seed. In a few cases, we're ve also run our code on different versions of hardware and software (CUDA and pytorch), and the results are similar, though not the same at the float number level.
REFERENCES
Marcin Andrychowicz, Dwight Crow, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin. Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. In Is- abelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vish- wanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 5048-5058, 2017. URL httpts:::pprcceeiinnggg nwur.gg...................... .tml
Ioannis Antonoglou, Julian Schrittwieser, Sherjil Ozair, Thomas Hubert, and David Silver. Plan- ning in stochastic environments with a learned model. In International Conference on Learning Representations, 2022. WtRLhttss:// http:://pperreeieeeee / net wew.ee/eoorrrrteooo00aaaaaeeaee
Richard Bellman. Dynamic Programming. Princeton Univ. Press, Princeton, NJ, USA, 1957. ISBN 0-691-07951-X.
Léonard Blier and Yann Ollivier. Unbiased methods for multi-goal reinforcement learning. CoRR, abs/2106.08866 2021. URL /RRl://cpss//rrrv..rr//////////
08863
Charles Blundell, Benigno Uria, Alexander Pritzel, Yazhe Li, Avraham Ruderman, Joel 2 Leibo, Jack Rae, Daan Wierstra, and Demis Hassabis. Model-free episodic control, 2016. URL https:
044.66666644660 04460
Elliot Chane-Sane, Cordelia Schmid, and Ivan Laptev. Goal-conditioned reinforcement learning with imagined subgoals. In Marina Meila and Tong Zhang (eds.). Proceedings of the 38th In- ternational Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 1430-1440. PMLR, 18-24 Jul 2021. URL https: htttps://procediiim .ng.mmrrs .mr..
press/viss chane wane2lannaaaa
Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine. Deep reinforcement learning in handful of trials using probabilistic dynamics models. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, pp. 4779- Red Hook, NY, USA, 2018. Curran Associates Inc.
10

---

Under review as a conference paper at ICLR 2023
Eric V. Denardo. Contraction mappings in the theory underlying dynamic programming. SIAM Review, 9(2):163-177, 1967. ISSN 00361445. URL http: httt:://ww... jstor wrt. 2027440
Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation enror in actor-critic methods. CoRR, 2018. / 110.10977777777777
Yasuhiro Fujita, Kota Uenishi, Avinash Ummadisingu, Prabhat Nagarajan, Shimpei Masuda, and Mario Castro. Distributed reinforcement learning of targeted grasping with active vision for mobile manipulators. In JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 9712-9719, Oct 2020.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In Jemnifer Dy and An- dreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1861-1870. PMIR, 10-15 Jul 2018. URL www.bttps:.. httt::://pprceeeee www.in............mmm..m....m.mm press. wwtp:/peesss/e//eeeaaeeee jan Bb html
Danijar Hafner, Timothy Lillicrap, Ian Fischer, Ruben Villegas, David Ha, Honglak Lee, and James Davidson. Learning latent dynamics for planning from pixels. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2555 2565. PMLR, 09-15 Jun 2019. URL UtLhttps:: petttps:/prroeeeeet http://pooecccceeeee/eo ngs. mlr www.sppssseeeeee....p.p http9///aafff/a/ 9a html
Frank S. He, Yang Liu, Alexander G. Schwing, and Jian Peng. Learning to play in a day: Faster deep reinforcement learning by optimality tightening. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26. 2017, Conference Track Proceedings. wwt.
OpenReview.net, 2017. URL htttt:://opeeeere///// wtt.:/eeeeeoooommmerrreeeeeeeeee
Sabrina Hoppe and Marc Toussaint. Qgraph-bounded q-lamiing Stabilizing model-free pol-po deep reinforcement learning. CoRR, abs/2007.07582, 2020. URL https://arxiv.oom
abs/2007.c 07582
Hao Hu, Jianing Ye, Guangxiang Zhu, Zhizhou Ren, and Chongjie Zhang. Generalizable episodic memory for deep reinforcement learning. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 4380-4390. PMLR, 18-24 Jul 2021. URL htttps://proceeding ngs. mlr. pww.sprsssssss v hww.99/hh..hhcc...
Aviral Kumar, Abhishek Gupta, and Sergey Levine. Discor: Corrective feedback in reinforce- ment learning via distribution correction. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Bal- can, and H. Lin (eds.). Advances in Neural Information Processing Systems, volume 33, pp. 18560-18572. Curran Associates, Inc., 2020. URL http:: httpl/tttt/:pppceddiiiii neurips. Paper-ap.rr.ee pdf
Sameera Lanka and Tianfu Wu. Archer: Aggressive rewards to counter bias in hindsight experrieeee replay. NewrlPS 2018 Deep Reinforcement Learning Workshop, 2018. URL httpttttp///aiia
org bogg/bb//880 00000/10000000000000
Timothy P. Lillicrap. Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference Learning Representations, ICLR 2016, San Juan Puerto Rico May 2-4, 2016, Conference Track Proceedings, 2016. URLhttp: 7/arxiv. org aww.abaaa0000 /000 02971
Zichuan Lin, Tianqi Zhao, Guangwen Yang, and Lintao Zhang. Episodic memory deep nentwwrks. In Proceedings of the Twenty-Sevente International Joint Conference on Artificial Intelligence, IJCAI-18, pp. 2433-2439 International Joint Conferences Artificial Intelligence Organiza- tion, 7 2018. doi: 10.249633ijcai.201833 2018//337... 201 8/337
URL https: ://tps

---

Under review as a conference paper at ICLR 2023
Xiaoteng Ma, Yiqin Yang, Hao Hu, Jun Yang. Chongjie Zhang, Qianchuan Zhao, Bin Liang, and Qihan Liu. Offline reinforcement learning with value- based episodic memory. In International Conference Learning Representations, 2022. URL/Ltps:// wttpreewwwwweeee/rruuueo
1d=RC7qv/9X111/
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wierstra, and Martin A. Riedmiller. Playing atari with deep reinforcement learning. CoRR, abs/1312.5602, 2013. httl:stp://axx..org////o//// wttp:/orrrg.aba1........... 5602
Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Mare G. Bellemare. Safe and efficient off- policy reinforcement learning. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Is- abelle Guyon, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain. pp. 1046 1054, 2016. URL ht http::::/ptocceepnnngggo///////s neurips. ca/ .html
Suraj Nair and Chelsea Finn. Hierarchical foresight: Self-supervised learning long-horizon tasks via visual subgoal generation. In International Conference on Learning Representations, 2020.
URL httpttt/ppppeeeiieeette net. wwtp//eorrrrm.. oot.:e/forrum2dddllllgg22-2111
Soroush Nasiriany, Vitchyr Pong. Steven Lin, and Sergey Levine. Planning with goal-conditioned policies. Advances in Neural Information Processing Systems, 2019.
Junhyuk Oh, Yijie Guo, Satinder Singh, and Honglak Lee. Self-imitation learning. CoRR, 05635
05035, 2018 URLhtt::://arxix org/
Matthias Plappert, Marein Andrychowicz, Alex Ray, Bob McGrew, Bowen Baker, Glenn Powell, Jonas Schneider, Josh Tobin, Maciek Chociej, Peter Welinder, Vikash Kumar, and Wojeiech Zaremba. Multi-goal reinforcement learning: Challenging robotics environments and request for research. CoRR, abs/ 80009444 2018.
http://abs1100...0000 802. 09464
Stuart J. Russell and Peter Norvig. Artificial Intelligence: A Modern Approach (4th Edition). Pear- son, 2020. ISBN 97801346 10993,
cs www.beereeeeee wtt.rreeeeeeeu///////e..
Marta Sarrico, Kai Arulkumaran, Andrea Agostinelli, Pierre Richemond, and Anil Anthony Bharath. Sample-efficient reinforcement learning with maximum entropy mellowmax episodic control. CoRR, wwtp///11...9....... 2019. URL httpt::://axxi.oog/bbbooo 19611.9111111111
Julian Schritwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy P. Lillicrap, and David Silver. Mastering atari, go, chess and shogi by planning with a learned model. CoRR, abs/1911 1.02655,, 2019, http://///aai org
org/ abs /bs//911........ 08265
David Silver and Kamil Ciosek. Compositional Planning Using Optimal Option Models. In Pro- ceedings of the 29th International Conference on Machine Learning, pp. 165. icml.ce Omni- press, 2012.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. A Bradford Book, Cambridge, MA, USA, 2018. ISBN 0262039249.
Yunhao Tang. Self-imitation learning via generalized lower bound q-learning 0ss/2006.074422 2020. URL.httss///axxvv.ooo hat.rrggabb//0000 07442
CoRR,
Philip Thomas. Bias in natural actor-critic algorithms. In Eric P. Xing and Tony Jebara (eds.), Proceedings of the 31st International Conference on Machine Learning, volume 32 Proceed- ings of Machine Learning Research, pp. 441 448, Bejing, China, 22 24 Jun 2014. PMLR. URL mlr press pre.ppggsssrr...essee...ee v22/ thomas14. html
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double 4- learning. CoRR, abs/1509.0646) 2015. URL http::t/ttt:/i/// org/ abs/ 1509. 66461
Weirui Ye, Shaohuai Liu, Thanard Kurutach, Pieter Abbeel, and Yang Gao. Mastering atari games with limited data. CoRR, 0bb/2111.00222 2021. URL hhtpt:t/////// arxiv. wwwp://..rg/ab//l1llloe
00210
12

---

Under review as a conference paper at ICLR 2023
Haonan Yu, Wei Xu, and Haichao Zhang. Taac: Temporally abstract actor-critic for continuous control. In NewrIPS, 2021.
Haichao Zhang, Wei Xu, and Haonan Yu. Generative planning for temporally coordinated explo- ration in reinforcement learning. In International Conference on Learning Representations, 2022. URL https: httpp:://ppereeeeeeeet/ net / forum? 1d=Y2HES8wIdE.
13

---

Under review as a conference paper at ICLR 2023
A
APPENDIX
A.1
PROOFS
Before going on to Theorem 2.3 we first prove the easier Corollary 2.4
We want show that given lower bound of the optimal value, Vs, ((s) < _ (v))s,, under the new operator B,, the value function converges to the same optimal value function given by the Bellman operator B.
Proof. Let v" be the fixed point and optimal value of the original Bellman operator: o" = 8 (v), v any value function, and any state.
First, for the simple case of Vs, where f(s) < (s). the new operator backs off to the Bellman operator, and follows the convergence of the Bellman operator:
(s(()(s)- (s))
max((Be)(ss) f(s)) e- (s)
= (((v)ss)-'"((
- ((()))s))B(()(()))
Stlle- --1le-vvlle v=1oo
Second, Vs, where f(s) > B(v)(s),
[By(t)(s) - v²
= =|max (max(B(v)(s),,))))) f()) - v-
=If(s) - -s)ss)
=o"(s (s) f(s) (because f lower bounds of (s) 2 f(s))
<v"(s) (s) (because f(s) > B(v)(s))
=|B(v)(s) (s()]]
<|B(u)(s) (s)]
=s)(v)(s) Bs)))(s))
Stlle 10
Therefore, the distance to the optimal value shrinks by y with every application of By:
[IBy(u) 0² loo max, (o) u (s)l < >/lv lol
According to the definition convergence to v", we need to find an N, such that > Ve o 0*, Vn > N, (b) 2/ < E.
We can easily calculate that any N 2 log, ||---||> (note, < 1) satisfies the condition, which concludes the proof that any value function will converge to v under the lower bounded Bellman operator By.
Note, from the proof above, we can see that By converges faster than y (the speed of Bellman contraction), when the lower bound is strictly above the Bellman value target, i.e. f(s) > (s)
Now for Theorem 2.3 given the maximum achievable value G" (s) and given that f(s) < (s),, we want to show convergence to the optimal value.
Proof. First, Vs, where f() < (s)) the value target backs off to the original Bellman target, and the distance to the optimal value shrinks rate
Second, Vs, where f(s) < 0 (s), it follows from Corollary 2.4 that the distance to the optimal value shrinks at rate 7.
Last, we only need to prove for any s, where f(s) 2 (s) and f(s) 2 (s)),s), the distance to the optimal value still shrinks:
14

---

Under review as a conference paper at ICLR 2023
- [maxx((()(66) - (s)
=I/(s) - (8)]
-f(s) 6*)
<G" (s)
According the definition of G" in Equation of the main text:
max ( -
reII,m[[l.+o))
Now suppose n' and nsss achieves the maximum bootstrapped value G*):):
GGt (s) (s)
According to the definition of n-step bootstrapped value (s) in Equation of the main text:
=E" (ri + 7r2 + ... (-())_1pp))))))) Tn(s) + 7 = ((n(s)))) - (s)
(The expectation above is over all possible ntte- trajectories of the given policy n and MDP.)
Suppose H² is the optimal policy, which achieves maximum value of for any number of steps and state s:
=E" (ri + 772 + 7 ((())) ((()) + (())((s)))))
E" (ri + 7/2 + +.. 7 -() ((())) + 7 ml)) (Sn(s)))
SR" (nr + y²2 + + ((=) rnce) + m())) ((s(()))
In(e)
E" (ri + 422 +... (m)) ((()) + m()))²
(This because n² maximizes the expected n-step bootstrapped value. So the expected value any other policy, e.g. n², bootstrapped with cannot be greater.)
=n fo((n(s)) v² (sn(s))
S (o(sn(s)) - v² (sn(s)))
=p((s) Σ fn" (Sn(s)(s) x (u(Sn(s)) - o² (8n(e))))
am(()
(1) max (u(s) 00 (s)
S9 min, n()) max ((()) n² (s)
-y n(e) n. 100
This means in the case of overestimated bootstrap values, the new operator promises shrink at rate of min, n({), and overall, the new operator will at least shrink at rate of y.
Note, from the proof above, By converges at speed of min, n(e), which could be faster than 7, the speed of Bellman contraction.
that when the lower bound overestimates, i.e. f(s) 2 os(s,,
These proofs work for stochastie MDPs, because we treat trajectory rewards and states as random variables conditioned on the MDP and the policy. The proofs work for action values well, by simply replacing the value function above v(s) with the action value q(s, and the value lower bound (s) with the action value lower bound as.
o in theory can be different for different state s, so that when unrolling from state sy for a few steps into s; it still follows x' (ssu), instead of '' (s:). However, it's easy to prove (by contradiction) that there exists a single policy x' which achieves the maximum achievable value (as long as ties are split deterministically..
15

---

Under review as a conference paper at ICLR 2023
A.2 EXPERIMENT SETUPS
We experiment on three sets of tasks with different input characteristics and control difficulty. Some of the tasks are not goal conditioned, so only lower bounding with empirical discounted return is available. Some of them are goal conditioned, so both empirical discounted return and hindsight relabeling with discounted goal return are available as lower bounds.
A.2.1 ATARI GAMES
We experiment on the classical Atari games with image input to test using discounted episodic return to lower bound value target. We picked the popular games Breakout, Seaquest, Space Invaders (these three were used for hyperparameter tuning by Mnih et al. (2013), Atlantis, Frostbite and Q*bert (these three were highlighted in (He et al. 2017)). and sampled another 11 games from the total 56 (simply using one out of every five games in alphabetical order). As with prior work (Mmih) al. 2013 Oh et al. 2018)) we evaluate on the standard NoFrameskip-v4 versions of the games with actions repeated for fixed four frames and each game started with up to 30 random number of noop steps before handing to the agent (to initialize the pseudo random number generator differently across episodes). Each episode of the games is capped at 10,000 time steps, with the last time step having discount 0.99 when the time limit is reached, i.e. resetting the game without ending the episode. For any regular game end, e.g. after losing all lives, the episode ends with last step discount of 0. Because the games are episodic, both lb-DR and lb-b-nstep methods can be applied.
A.2.2 FETCH PUSH, SLIDE AND PICKANDPLACE
The FetchEnv tasks (Plappert et al. 2018) are goal conditioned tasks with a MuJoCo simulated robotic arm moving objects on a table. Robot states and object position serve as input. The agent outputs continuous actions taking the form of relative positions to move to. A PID controller trans- lates the relative position actions into the exact torque applied at each joint. Rewards are sparse and goal-conditioned, with -1 for non-goal states and 0 for goal states.
By default the FetchEnv tasks are non-episodic. They reset every 50 steps, but all steps including the step right before task reset have the same positive discount (Andrychowicz et al. (017). As plained in Section 3.1 to use episodic discounted return as lower bound, we can make them episodic by adding a gym wrapper around the environment to end an episode after its goal is achieved, and reset the task. When goal is not reached within 50 steps, we just reset the task without ending the episode, is done in the original FetchEnv, and such experience is not used in value target lower bounding 3 This also changes the nature of the tasks, so the agent does not have to stay at the goal state indefinitely, but instead only needs to reach the goal position as fast as possible. This makes the episodic FetchEny tasks slightly easier to train than the original tasks, because the agent only needs to reach the goal state quickly, instead of having to reach and stay the goal position indefinitely. (There are ways to avoid changing the desired behavior by e.g. including agent's 's speed into the goal state or requiring the agent to stay at the goal position for several time steps before ending the episode. This seems orthogonal to the main idea here, and is not included in this work.)
We experiment on both the original/non-episodii FetchEnv tasks (with Ib-b-ristep methods) and the episodic FetchEny tasks (with Ib-DR and Ib-GD methods).
Compared with the Atari games, the inputs are simpler, no longer image based, but the control task is continuous, under realistic physical simulation and harder.
A.2.3 PIONEER PUSH AND REACH TASKS
This is set of challenging goal reaching and object pushing tasks for the car Pioneer 2dx, physically simulated with Gazebo. The car is 0)44 meter long. Objects and goal positions are randomly initial- ized between 0.5 meter to meter of each other inside a 10 meter by 10 meter flat space. Inputs are the car and object states and the goal positions, and actions are the forces applied on the two driving wheels.
Fujita et al. 2020) chose to end episodes when either a maximum of T time steps is reached or the goal is reached, and provided the agent with the number of timesteps since episode start as input to the agent, so that the agent is aware of the approaching episode end.
16

---

Under review as a conference paper at ICLR 2023
Figure 4: The Pioneer Push task and the Push and Reach task.
For the Pioneer Push task, the car has to push block to within 0.5 meter of the 2 dimensional goal position indicated by small red dot on the ground. For the Pioneer Push and Reach task, the car separate goal position
has to first push the object to the goal location (red dot) and then drive (red ball in the air); the goal is achieved when the concatenation of the two goal locations (for Push and for Reach) is within 0.5 of the concatenated achieved positions (of the block and the car) in Ly-distance.
These tasks are episodic with sparse goal reward, and we only test the Ib-GD and Ib-DR+GD meth- ods on them with HER as baseline. (TD3 without HER takes too long to train.)
These tasks take longer time accomplish, and also take longer time to train than the FetchEnv tasks. Some of the reasons are the force based wheel control instead of the higher level position control, and the arena space being much larger than just a tabletop.
A.3 HYPERPARAMETERS AND BASELINES
Table 1 lists the hyperparameters of the baseline algorithms. For FetchEnv, they follow published work (Plappert et al., 2018). For Atari and Pioneer tasks, they are tuned using one set of random seeds and after keeping the hyperparameters fixed, trained with different set of random seeds and evaluated. Value target lower bounding has no parameter, and we did not re-tune any parameters of the baseline RL algorithms for value target lower bounding. When comparing lb-b-nstep methods with other n-step methods, we simply use the same n as the other baselines.
For the Atari games, the original DQN setup with only to train so we decided to tune SAC as baseline and found it to outperform published Actor-Critic results (Oh et al. 2018) and our tuned DDQN (results in Appendix (A.6).
training environment takes too long
To use SAC on discrete actions, we simply swap out SAC's value networks (which take in continuous action and state input and produce the value) with DQN's Q networks (which take in state as input and output n heads, each head for one action logit). We pass the output of the Q networks (administered by the temperature a) through softmax compute the action probabilities, and to further sample actions. We ignore actor losses because there is no separate actor network, and only use critic losses train the networks.
The reason we can use Q with temperature and softmax to compute action probabilities is that for discrete actions, maximizing the SAC objective max, Ip(a, (Q(s, a.) - a log pogp(a; s))] subject to Σ p(a,, s) = 1 directly gives the solution p(a,, s) x exp(Q(s, (a)aa) See Appendix D of Yu ct al. 2021 for a similar derivation.
For Pioneer Push and PushReach tasks, TD3 is used, (we simply equip DDPG with two crities for clipped double Q learning (Fujimoto et al. 2018)), which works better than DDPG with one critic.
17

---

Under review as a conference paper at ICLR 2023
Table 1: Hyperparameters for all the tasks
Hyperparameters: Tasks
Atari (SAC)
FetchEnv (DDPG)
Pioneer (TD3)
Parallel environments
30
38
30
Unrolls per train iteration
8
50
100
Updates per train iteration
4
40
40
Mini-bate mani-batch size
500
5,000
5,000
Training updates per target network update
20
40
Target update weight Discount per time step Initial collect steps Total training time steps
0.95
0,95
0.95
0.99
0.98
0.99
100,000
10,000
10,000
12 million (x4 en- vironment frames) 10,000
2 million
Push: 5 million,
PushReach: 14 mil
Max steps before task reset
50
Push:
100,
PushReach: 200 million
Replay buffer size Adam optimizer learn rate
million 5e-4
2 million
le
1e-3
Network structure
conv 8,
4),
fc(256, 256, 256)
fc(256, 256, 256)
(64, 4. 2), (64, 3.
1)) + fc(5122))
Number of critics e-greedy for evaluation
2
1
2
0.05
0.3
0.3
Evaluation interval in train iters
1000
40
200
Evaluation episodes
100
200
100
Life loss as ferminal
Yes
n/a
n/a
Action repeat
4
n/a
n/a
Image scaling
[-1, 1]
n/a
n/a
Frame stacking
n/a
n/a
Reward clipping
[-1.
n/a
n/a
SAC target entropy
calculated
n/a
n/a
Hindsight percentage
n/a
80%
50%
Observation normalization
No
Yes
No
TD-lambda: À
0.95
0.95
n/a
n-step bootstrap:
3
2
n/a
Adam à 1e for all tasks.
Netowrk structure for Atari follows DDQN (van Hasselt al. 2015).
Life loss in Atari games is treated terminal state in training, following EfficientZero (Ye et al. 2021
The SAC target entropy is set to the entropy uniformly distributing 0.1 probability mass across all but one actions.
Observations are normalized to have zero mean and unit variance based on the statistics of the training observations, and found the normalization to be critical in reproducing HER results FetchEnv.
18

---

Under review as a conference paper at ICLR 2023
A.4 RESULTS
Applying lower bounding (e.g. lb-DR) on different baseline algorithms e.g. DDPG or SAC results in different treatment methods. Since we always compare treatment with its corresponding baseline, throughout the paper, we simply call the treatment lb-DR etc. without mentioning the baseline algorithm.
A.4.1 LB-DR (EPISODIC RETURN) VS BASELINE SAC/DDPG
Figure Saane5Scommg compares lower bounding with discounted return (Ib-DR) against SAC or DDPG baseline on 17 sampled Atari games and the episodic FetchEnv tasks.
For 16 out of the 17 Atari games, lower bounding with episodic discounted return (lb-DR) performs least as well as the baseline, often much better. more than half the Atari games and on Fetch PickAndPlace task, there large gains in both sample efficiency and final performance. On FetchPush and a few of the Atari games (Alien, Bank Heist and Fishing Derby), there about 70% sample efficiency gain with similar converged performance. Among all the 20 tasks, only task (Atari Breakout) shows lb-DR underperforming the baseline.
A.4.1.1 Value learning plots
This section presents plots of learned value and how often value is improved by the proposed meth- ods, in order to show the effect lower bounding on value improvement.
Figure 6 shows the fraction of training experience where lb-DR value target is greater than the Bellman target from SAC/DDPG on the 17 Atari games and the episodic FetchEnv tasks (without hindsight). They correlate well with actual performance (Figure 5 and with how value is learning (Figure 7p.
19

---

Under review as a conference paper at ICLR 2023
200
1000
(a) Atari Alien
(b) Atari Atlantis
(c) Atari Bank Heist
(d) Atari Breakout
1010
0.
(e) Atari Centipede
(f) Atari Enduro
(g) Fishing Derby
(h) Atari Frostbite
11500
150
(i) Atari Ice Hockey
Atari Ms Pacman
(k) Atari Qu
(1) Atari River raid
5000
2000
(m) Road Runner
(n) Atari Seaquest
(0) Space Invaders
(p) Atari Time Pilot
20
(q) Atari Zaxxon
(r) FetchPush
(s) FetchSlide
(L) PickAndPlace
Figure 5: Evaluated average return of value target lower bounding with discounted return (lb-DR)
vs SAC or DDPG on Atari games and episodic FetchEnv tasks. Solid curves are the mean across five (for Atari) three (others) seeds, and shaded areas are +/- one standard deviation.
20

---

Under review as a conference paper at ICLR 2023
210
0.20
2.00
3.00
2.0
000
005
(a) Atari Alien
(b) Atari Atlantis
(c) Atari Bank Heist
(d) Atari Breakout
2.1
012
0112
2.0
Toaling Denatona
maating tandon
Thaning rentoos
Thaning PANDOOR
(e) Atari Centipede
(f) Atari Enduro
(g) Atari Fishing Derby
(h) Atari Frosthite
Box
Bal Sum
(i) Atari Ice Hockey
(i) Atari Ms Pacman
(k) Atari Q*bert
(1) Atari River raid
2.2
punt
Bon
coe
axs
2.00
cot
8.00
3.00
5.0
000
makingg sandors
(m) Atari Road Runner
(n) Atari Seaquest
(o) Atari Space Invaders
(p) Atari Time Pilot
20125
0.000
3.04
1419
1007
0200
2208
2.00
0.00
100ng
(q) Atari Zaxxon
(r) FetchPush
(s) FetchSlide
(0) FetchPPicAAndPlace
Figure 6: Fraction of training experience where Ib-DR value target greater than the Bellman target, on Atari games and episodic FetchEnv tasks, plotted against the number of training iterations. Solid curves are the mean across five (for Atari) or three (others) seeds, and shaded areas are +/- one standard deviation.
21

---

Under review as a conference paper at ICLR 2023
Mext
0:00 Oom
Brudimo
(a) Atari Alien
(b) Atari Atlantis
(c) Atari Bank Heist
(d) Atari Breakout
jaind
178
(c) Atari Centipede
(f) Atari Enduro
(g) Atari Fishing Derby
(h) Atari Frostbite
174
bomt
12a
120
Thanng TMADOO
Tranig Seatons
Thanngg
Traning pration
(i) Atari Ice Hockey
Atari Ms Pacman
(k) Atari Qebert
Atari River raid
8:08 junt)
G-OR (wel))
Mid
(m) Atari Road Runner
(n) Atari Seaquest
Atari Space Invaders
(p) Atari Time Pilot
(q) Atari Zaxxon
(r) FetchPush
(8) FetchSlide
(t) FetchPickAnnPllce
Figure 7: Learned values of lb-DR and SAC (for Atari games) and DDPG (for FetchEnv tasks), evaluated on the training experience and plotted against the number of training iterations. Solid curves are the mean across five (for Atari) three (others) seeds, and shaded areas are +/- one standard deviation.
22

---

Under review as a conference paper at ICLR 2023
b-0th CD (cus)
-10
B-47 (345))
-15
far
Ausrage Trauum
Aecrig Eskodit Redum
-20
-00
-30
-35
(a) FetchPush
(b) FetchSlide
(c) PickAndPlace
-00
-100
-120
-340
-100
-100
(b
Erwionmeer
206
Crvmomment Stene
327
(d) PioneerPush
(e) PushReach
Figure 8: Value target lower bounding with goal distance return (lb-GD) and Ib-DR+GD vs HER on episodic FetchEnv and Pioneer tasks. Solid curves are the mean across three seeds, and shaded areas are +/- one standard deviation.
A.4.2 LB-GD (GOAL DISTANCE RETURN) AND LB- GRD Vs HER
Figure X compares lower bounding with goal distance return (Ib-GD) and lower bounding with both goal distance and discounted return combined (Ib-DR+GD) against the much stronger HER baseline, on the goal conditioned episodic FetchEnv and Pioncer tasks.
On the easier FetchEnv tasks, lower bounding is similar as HER, but on the more challenging Pioneer Push and Reach tasks, lower bounding is able to achieve over 70% more sample efficiency, It seems the harder the task, the wider the margin of gain.
A.4.2.1 Value learning plots
This section presents plots of learned value and how often value improved by the proposed meth- ods, in order to show the effect of lower bounding value improvement.
FigureJshow the fraction of training experience where the Ib-GD is higher than the Bellman value target from HER, in the goal conditioned (episodic FetchEnv and Pioneer) tasks, and the learned value. It seems, for FetchEnv tasks, where Ib-GD only performs slightly better than HER, the fraction of experience with improved value target is quite small (less than 1%). Hindsight relabeling is probably already producing fairly high value targets. For Pioneer Push and Reach tasks, Ib-GD performs much better in average return, and the fraction of experience with higher value target is also much larger (peaking around 2-8%).
23

---

Under review as a conference paper at ICLR 2023
3-50+G0 (hung
0.004
0.0035
tour)
0.000
0.0030
(atun Paat
Bn Pase
10.033
0.008
0.0022
0.0030
0.035
0.004
0.0030
0.002
0.003
b- gunn)
0.0000
I--00 (wan))
0.000
0.5
0.2
02.4
0.88
1.0
0.
0.2
0.4
08
3.0
0.0
0.2
01.4
0.8
0.5
3.0
Traring Dessaforts
(a) FetchPush
(b) FetchSlide
(c) AencPPickAAnPPlaee
0,025
(oun)
B-BR (O01))
0.57
I--00 (hur)
8-40 Regum Graee Dare
6,020
0.00
0.29
0.04
0.000
B-GD
0.03
0:22
001
5.000
0.00
1.0
Taining teent
105
Triin ng (NEROSTE
145
(d) PioneerPush
(e) PioneerPushReach
b DD100 (ous)
ORHOD (oun)
lb DR+3D (curs) Ib-GD (sun)
B-G3 (oun)
CD (curs) 1ol
Tran ng Saaa
Moon Toahrra
-6
-7
-12
Trining Hecatiee
103
(f) FetchPush
(g) FetchSlide
(h) FetePPickAnnPlace
(uun)
-10
-20
Moun Trakerg Vilae
-22
-30
Traking
-00
-00
-70
0.0
0.5
1.0
3.5
0
Franiing Reladoons
363
Trainng teraion
1x3
PioneerPush
PioneerReach
Figure 9: Fraction of training experience where Ib-GD Ib-DR+GD value target is greater than the Bellman target (a-e) and learned values (f-j), on episodic FetchEny and Pioncer tasks, plotted against the number of training iterations. Solid curves the mean across three seeds, and shaded areas are +/- one standard deviation.
24

---

Under review as a conference paper at ICLR 2023
2000
300
2:000
220
2000
150
b soap (cuns)
2200
3,000
300
Snaup
1000
500
0
Shace
307
Atari Breakout
(b) Atari Seaquest
(c) Atari Frostbite
[-o Zemp Dound
8000
opilighten 3atp
Aepugge Edtokk Rouu
0000
.....
4020
Aeatage
Brbltep (ourg rptigrendcep
ambda
depo
0.
0.2
D44
0.5
2.0
1.0
12
Ensinoemen Steao
Emironment Stepes
Enikcoment Steps
(d) Atari Q*bert
(c) FetchPush
(f) PickAndPlace
Figure 10: Evaluated average return of value target lower bounding with n-step bootstrapped return (lb-b-nstep) vs SAC or DDPG, td-lambda, Retrace and original/non-episodie FetchEnv tasks. for Atari and 2 for FetchEnv tasks. Solid curves the mean across five (for Atari) or three (others) seeds; shaded areas are +/- one standard deviation.
on Atari games and the
A.4.3 n-STEP BOOTSTRAPPED METHODS
Figure T0 shows performance of lb-b Ib-b-nstep methods on subset of the Atari games (episodic) and the original (non-episodic) FetchEnv tasks. Besides SAC/DDPG, baselines also include n-step meth- ods such td-lambda, Retrace (Munos et al. 2016) and optimality tightening (He et al. 2017)) Ib-b-ristep methods are at least as good as the best baseline method, and clearly outperforms the baselines in two of the six tasks.
A.4.3.1 Value learning plots
Figure II shows the fraction experience where Ib-b-ristep lower bounds are above one step Bell- man value targets. There seems be correlation between improving the value target over more experience and actually improving the policy, at least for FetchEnv tasks. The correlation does not seem clear as that of lb-DR. With bootstrapping, the fractions are generally higher than those of lb-DR in Figure 6 potentially due to overestimated bootstrap values.
A.4.4 n-STEP METHOD ABLATIONS
The following three sections include ablations which show the lower bounding methods to be robust to variations in the hyperparameters.
A.4.4.1 lb-b-niteep with different (number of steps)
Figure 12
shows the effect of how the number of steps in n-step bootstrapped return impacts lower bounding performance. The ib-b-nstep method not very sensitive to the value n, typically, the higher the value the better the performance, while n-step methods like ld-lamada or Retrace would degrade a lot as n increases above or 4. We also observe lower value overestimation as n increases (Figure T6).
25

---

Under review as a conference paper at ICLR 2023
It-b-aaap (oung
I-t--aaen (oun)) mpsigttnnnnng
b-ddamp (un)) ope- (ple--3ddp
b Reteecum O cros haat:
0.7
655
as
0.6
84
0.5
ca
0.5
0.1
92
Trakning to stlans
Iwrt
Train ng kerakons
Traniing teatons
(a) Atari Breakout
(b) Atari Seaquest
(c) Atari Frostbite
It-b-0san (nung
D-- 2:0-20m)/0111
opt-igyaan 2olle
0.90
bdd hoam Baaaaaaaaaaaaot Creane Rau3
0.E
b:00 haam Greass
0.85
0.20
0.5
0.35
0.30
0.10
0.00
Trahning to stians
Ind
bx
faral
142
(d) Atari Qubert
(e) FetchPush
(f) FetchPickAnndPlce
Figure 11: Fraction of training experience where Ib-b-nstep value target or
lower bound is greater than the value target of baselines SAC (for Atari games) and DDPG (for FetchEnv tasks), plotted against the number of training iterations. Solid curves are the mean across five (for Atari) three (others) seeds, and shaded areas are +/- one standard deviation.
A.4.4.2 lb-b-nstep vs lb-b-nstep-only (only n-th step)
Figure shows the effect of taking maximum of all 2- to n-step bootstrapped returns versus only using the n-step bootstrapped return. seems using the maximum bootstrapped return of all to n-steps, hence tighter lower bound, works better than only using the n-step return.
A.4.4.3 lb-b-ristep (bootstrap) Ib-DR (episodic return)
In continuing tasks (with negative rewards), we have to use the bootstrapped lb- Ib-b-ristep method. But for episodic tasks, should we use bootstrapped return episodic return value target lower bound? In theory, Ib-b-ristep-only becomes Ib-DR when n large enough. In practice, in terms of effec- tiveness, can compare Ib-b-nstep with Ib-DR on the Atari games (Figure I0 and 5 respectively Ib-b-risep is better than lb-DR on Atari Breakout. On Seaquest, the two are similar. On the other two games: Frostbite and Q*bert, episodic return is better. It seems lb-DR is better tasks where rewards are more sparse and longer term planning is needed. terms of efficiency, as n becomes larger, the memory and compute efficient lb-DR method will become attractive. Overall, both methods show clear advantage over the baselines.
A.4.4.4 Value learning plots
Figure 14 shows the fraction of experience where Ib-b-nistep lower bounds are above one step Bell- man value targets.
Figures 15 and 16 show the learned value of the Ib-b-ristep and lb-b-nstep-only methods. It's con- venient to look at the FetchEny tasks which should always have non-positive value. From Figure 16 a)), seems n increases, value decreases, maybe due more accurate estimates of value. From T6 it seems the tighter lower bounds of Ib-b-nstep method do lead to slightly more overestimation value.
26

---

Under review as a conference paper at ICLR 2023
0-5 Jaled (S4n))
-15
D-- S338es (M4rs) 100g
Avcragg Epcolc Potum
-28
30
-05
85
Aeeroge
FetchPush
PickAndPlace
Figure 12: Evaluated average return of value target lower bounding with n-step bootstrapped return (lb-b-nstep) with different the original/non-episenn FetchEnv tasks. Solid curves are the mean across three seeds, and shaded areas are +/- one standard deviation.
-10
-20
215425 (ours)
only (our))
Average S15000 Rotan
deog
-30
-38
hose (oum
-00
Lirap (sun)
Tamp ony (uan))
bas Lemporty (um))
6530
Envionent Staps
200
Eneicnmmnt Sters
108
(a) FetchPush
(b) PickAndPlace
Figure 13: Evaluated average return of value target lower bounding with all n-step bootstrap (Ib-b- ristep) and nth-step only (lb-b-nstep-only) on the original/non-episaee EntchEnv tasks. Solid curves the mean across three seeds, and shaded areas are +/- one standard deviation.
roso Sunp
Coo bold
043
8.0
5.0
FetchPush
(b) FetchPickAnnPlace
(c) FetchPush
(d) FetchPickAndPlace
Figure 14: Fraction of training experience where 1b-b-rstep Ib-b-nstep-only improves over the baseline Bellman value target, evaluated on the training experience and plotted against the number of training iterations. Solid curves are the mean across three seeds, and shaded areas are +/- one standard deviation.
27

---

Under review as a conference paper at ICLR 2023
Overs brnnd
Traiing
(a) Atari Breakout
(b) Atari Seaquest
(c) Atari Frostbite
(d) Atari Qubert
Thaning
Bradoors
(c) FetchPush
(1) FetchPickAnnPlace
Figure 15: Learned values of Ib-b-ristep and SAC (for Atari games), DDPG (for FetchEnv tasks), optimality-tightenil td-lambda and Retrace, evaluated the training experience and plotted against the number training iterations. Solid curves are the mean across five (for Atari) or three (others) seeds, and shaded areas +/- one standard deviation.
slog
Share Oonrd
Tuaing
Tranng
(a) FetchPush
(b) FenchPickAnnPlace
(c) FetchPush
(d) FetchPickAndPlace
Figure 16: Learned values of lb- lb-b-nstep, lb- lb-b-nstep-only. DDPG (for FetchEnv tasks), optimality- tightening. td-lambda and Retrace evaluated on the training experience and plotted against the num- ber of training iterations. Solid curves are the mean across three seeds, and shaded areas are +/- one standard deviation.
28

---

Under review as a conference paper at ICLR 2023
A.5 1-STEP RETURN BASED METHODS
A.5.1 1-STEP RETURN METHODS
lb-b-niteep methods and n-step return methods are similar in their data and computation require- ments, and we already compare their performance in Figure 10.
Here, we additionally compare lb-DR directly with n-step methods in Figure 17
254
0332
lumziii reblado
DF
4000
B: (sura) Malamiiaa oce
300
540
Fectigg 20000 PN0SE
250
200
2000
350
2000
100
1.000
50
1000
0.0
0.2
0.4
0.6
0.8
1.0
1.2
00
0.2
08
0.8
1.2
00
0.2
0.5
0.5
Envrommrr Stots
Ervforment Shaps
Enwrsnmar Stace
(a) Atari Breakout
(b) Atari Seaquest
(c) Atari Frostbite
B-GR (wars)
b-0R (aun))
12000
In 1--anttds 640g
10000
Avcrage trrsodi 7utkam
Aveaag Eutood Retar
9002
8000
4000
2002
0.2
0.0
12
(d) Atari Qrbert
(e) FetchPush
(f) FetchPickAndPlace
Figure 17: Evaluated average return of value target lower bounding with discounted return (lb-DR) vs SAC or DDPG, td-lambda and Retrace four Atari games and the episodic FetchEny tasks. Solid curves are the mean across five (for Atari) or three (others) seeds, and shaded areas are +/- one standard deviation.
During experimentation, we found that n-step methods typically harder tune and more expen- sive to compute.
1) Tuning n: A small n for n-step methods works similarly the baseline one-step method, and a larger n hurts performance. This is likely due to the off-policy bias in n-step return causing the n-step estimate to be potentially worse than the one-step estimate. Introducing importance sampling weights (Retrace) would help reduce the bias, but at the same time significantly downweight the off- off-policy high return experiences, making an ineffective use of such experiences.
None of these issues exist in value target lower bounding: (a) It does not incur any off off-policy bias, and (b) as long as an experience renders high reward, being off-policy does not affect its ability to improve the value target.
2) Tuning involves other hyperparameters like the td-lambda parameter, replay buffer size, priori- tized replay (to potentially expire old experiences and sample recent ones more frequently), target network update parameters (to reduce potential overestimation), and parameters for importance sam- pling. But still, after all the tuning, it only slightly outperforms one-step DDPG on FetchEnv or SAC on Atari games, and is often below the lower bounding methods. For td-lambda and Retrace, the best performance comes from 2-step (for FetchEnv) or 3-step (for Atari) td with À 0.95, all other pa- rameters the same as the baseline DDPG or SAC, Retrace underperforming the baseline in Breakout and Frostbite is similarly observed in the original paper (Munos al. 2016).
29

---

Under review as a conference paper at ICLR 2023
4.5
b-5i (ouss tsAattiia
b-OR (lun)
12
13 luncoa
reltsce
2.0
2.-
Moont haaaaa
10.0
7.5
1.5
5.0
1.0
25
0.5
5 104
0.0
Traning bandhan
Tramnng Banatona
104
Traning teratone
104
(a) Atari Breakout
(b) Atari Seaquest
(c) Atari Frosthite
17.5
DR (oung
kambaa
OR (ouns
43sg
odos
Iiaa Tranre Vaak
Noun Tranire vaku
12.5
:0.0
-12
7.5
-20
0
0.4
0.4
1.0
Thakning toruaor
Training
Traniing Herudara
(d) Atari Qebert
(c) FetchPush
(f) FetchPickAndPlace
Figure 18: Learned values of lb-DR and SAC (for Atari games), DDPG (for FetchEnv tasks), td- lambda and Retrace, evaluated on the training experience and plotted against the number of training iterations. Solid curves are the mean across five (for Atari) or three (others) seeds, and shaded areas are +/- one standard deviation.
On the other hand, value target lower bounding with episodic return requires no hyperparameter tuning, (lb-b-nstep with bootstrapping is not very sensitive to the choice of n), and learns faster on most tasks and converges higher on many tasks.
3) Computing n-step td-lambda return requires more computation due to evaluating value networks on all n-steps of the experience. limits how large n can be due to GPU memory limits, and slows down training time significantly with large
On the other hand, value target lower bounding precomputes and stores episodic discounted return in the replay buffer, and incurs very little additional computation.
Overall, n-step methods are much more expensive and difficult to use, and the much simpler and effective lower bounding methods maintain advantage in both effectiveness and efficiency. We show the performance comparison in Figure 17 with learned values in Figure T8
A.5.2 OPTIMALITY TIGHTENING WITH S-P RETURNS
He et al.] (2017) use bootstrapped n- step return to lower and upper bound the value during training. They frame the problem as a constrained optimization problem where the distance between the value and the Bellman value target is minimized subject to the constraints that the value function must be within the lower (and upper) bounds. This is similar to our Ib-b-nstep method, except instead of applying constraint improve the value target, which is likely more optimal and more efficient. In their experiments, the Lagrangian multiplier was fixed, which would likely lead suboptimal solutions, and theoretical guarantee was given. For episodic tasks, even more efficient and effective methods like Ib-DR exist.
the value,
the bootstrapped return to directly lower bound and
Some detailed differences:
The prior work bounds the value function itself (similar to lower bound q learning (Oh et al. 2018 Tang 2020)), instead of bounding the Bellman value target. This could cause suboptimal training
30

---

Under review as a conference paper at ICLR 2023
because the Bellman target itself could be outside the bounds, causing contradictory training targets and losses. Imagine the current value for a state is 1, its Bellman value target may be a low O, and the lower bound may be high 2, then it's unclear which way the value function should go. It will depend largely on the mixing weight between the two losses À and whether initial values overesti- mate, which can be hard to tune in practice. In their experiments, fixed Lagrangian multiplier À was used, which makes the method likely non-optimal.
2) In order to compute the bootstrapped values, the value network needs be evaluated on all future time steps, severely increasing GPU memory consumption and compute. Because of this increase in compute. in experiments, it could only look at a limited (4) timesteps into the future, while Ib-DR and Ib-b-nstep-only can look ahead much further with very little extra computation and storage.
We implemented the optimality tightening method (He et al. 2017), using only the lower bounds to be comparable to the other methods, and integrated into our baselines. We ran on FetchPush and FetchPickAndPlace with hyperparameters number of time steps n 2, and the penalty coefficient following the original paper. Results in Figure show optimality tightening to be either not as stable or not optimal as our lb-b-ristp. We also ran it on Atari games, and found that optimality tightening overestimates value a lot, leading to much worse behavior than even the SAC baseline. The constrained optimization formulation might have an adverse effeet during RL training, and the upper bounds in the original optimality tightening work may be necessary to bring training back on track.
will be interesting to see whether value target upper bounding with bootstrapped values (as pro- posed in (He et al. 2017) value upper bound constraints) can lead to optimal converged value in theory, and whether the upper bounds would help optimality tightening in experiments. However, tight upper bounds are not as readily available as lower bounds. This is because during RL training, the agent's 's performance hopefully increases, which makes it difficult to come up with a proper up- per bound before the optimal value is known. Additionally, the motivation for using upper bounding would be, for example, to avoid value overestimation, which is very different from the motivation of faster value improvement for lower bounding. Hence, we see upper bounding as out of the scope of this work.
A.6 VALUE TARGET LOWER BOUNDING ON DDQN
Because DQN is more popular baseline for the Atari games, we ve also applied value target lower bounding (lb-DR) on DDQN, and ran on subset of the Atari games. Different from (van Hasseli et a 2015), our implementation of DDQN finds the maximal action using the target critic network and evaluates the target value on the target network. It also uses two critic replicas like (Fujimoto) jet al. 2018). Figure 19 shows the results. Compared to SAC (Figure 5). DDQN either lowers the baseline performance or the treatment (Ib-DR) performance, and does not seem as strong as SAC.
Juinn)
2500
I- Saind
I- (we))
1200
1400
20
54
54
62
24
13
15
42
0A4
13 82 08 09 20
04 08
(a) Atari Breakout
(b) Atari Seaquest
(c) Atari Frostbite
(d) Atari Qabert
Figure 19: Evaluated average return of value target lower bounding with discounted return (Ib-DR) implemented on DDQN vs DDQN baseline on four of the Atari games. Solid curves are the mean across five seeds, and shaded areas are +/- one standard deviation.
31

---

Under review as a conference paper at ICLR 2023
A.7 UNBIASED EXPERIENCE REPLAY
RL methods like Hindsight Experience Replay can introduce hindsight bias (Plappert et al. 2018 Lanka & Wu 2018 Blier & Ollivier] 2021) in training due future step from an experience being used to relabel an earlier step of the same experience, possibly biasing the distribution of training experience, overestimating value and making the task seem easier than it really is. MuZero (Schrittwieser et al., 2019) assumes deterministic transitions and could also exhibit bias in stochastic environments (Antonoglou et al. 2022). Similar to HER, in this work, the future return from an experience when directly used to lower bound the value target computed from the same experience could also introduce bias to the value target. This bias could lead to value overestimation, as shown in the example below.
Assume state So always goes to St. S₁ gives reward +2 or -2, 50% of the times randomly, and transitions to the terminal state. For this case, the true values are v(So) v(Si) 0. For one lucky experience with reward +2, empirical return for So is 27, and for an unlucky one, -2y. Averaging the two leads the unbiased estimate of return for So. O, which could be safely used as valid lower bound. However, if the lower bound is computed only using one lucky experience or one unlucky experience, then the lower bounded value target for Sp y max(2, v(S))) and
max ( v(S))) respectively, averaging to be 7 max((2,((51) max 2,n(81)) 21+0 = which overestimates v(So)
2
Existing work ARCHER (Lanka Wu 2018) and stochastic MuZero (Antonoglou et al. 2022) al- ready follow up HER and MuZero, proposing unbiased sampling or model enhancements to address the bias. Thus, the specific way of using the episodic or bootstrapped return from the sampled tran- sition to lower bound the value target of the transition could be biased in stochastic environments, but future work may propose unbiased sampling methods to reduce or remove the bias of empirical return based lower bounds.
Luckily, when reward sequences are reproducible, which is largely satisfied for many tasks in the macroscopic physical world, where reproducibility is often assumed, empirical return lower bound- ing always produces an unbiased estimate of the value target. For the tasks in this paper. both Atari games and physical simulators have near deterministic transitions, with pseudo randomness affecting reproducibility. However, seems the impact is small, as we do not observe any apparent overestimation, and lower bounding still produces quite large improvements. This is consistent with the observations of prior works such as Fujita et al. 2020)
A.8 MORE ABOUT EPISODIC CONTROL
The original episodic control [Blundell al. 2016 simply applies Q(s,a) max(Q(s. a), R) where R is the newly observed return for the entry (8, a) in the episodic memory Q This lower bounds the Q value directly, and if Q is already overestimated due initialization function ap- proximation, it will stay overestimated, because the overestimation never goes through Bellman contraction.
Hu et al. (2021) corrects the problem by using implicit memory based planning in the following way. For an episode of length T', current step i T, the value target is defined recursively
rr max Q0(1411,4))) rx
if T if
R₂
(12)
This back propagation process can be further unrolled as follows. Define value as
Ve,1 = ri + 7 (Q((s,,))) 0z)
if > if 0
(13)
Given planning horizon h, the value target for the value Qo a:) is just RG:
*For this argument, can simply assume v(Si) to he the correct value.
32

---

Under review as a conference paper at ICLR 2023
R2 = Vene, where h- = arg max Vi, h20
(14)
The maximum over planning horizons h in Equation 14 allows existing values from the episodic memory Qo(s; 0i) for < i i T influence and lower bound the return of the current trajectory. As the episodic memory contains information about the trajectories from past experience, the final value target is influenced not just by the current trajectory, but also past trajectories that share a similar state as any of the states on the current trajectory.
Qo(Et, ae) and Vi. are carefully defined to be for all states after the episode ends i.e. This allows the episode end to always have the correct value to begin with, proper value can be backed up the trajectory to all earlier states. Equation I4 also importantly requires h to be above when taking the maximum over planning horizons. This way, the value target for (s az) is not influenced by @s, q)) itself. Only (0(s ac+i) (for > 0) can influence the value target for Qs(s,, a)), and they have go through the Bellman operator (see Equation 13 when h 0). This means any initial overestimation will contract.
T.
Episodic memory provides an interesting tool compute tight value target lower bounds for near deterministic tasks, with a computational cost similar to a typical n-step return method.
A.9 ADDITIONAL RELATED WORKS
Planning methods can look into the future to achieve higher value targets and better control. Ex-
amples include Monte Carlo Tree Search (MCTS) (Schrittwieser et al.. [019 Ye et al. (02T) and Model Predictive Control (MPC) or receding horizon planning with raw actions (Chua et al. [2018]
Hafner et al. 2019; Zhang et al., 2022). options (Silver & Ciosek 2012). or subgoals (Nasiriany) et al.) 2019: Nair Finn 2020 Chane-Sane et al. 2021). Planning methods use either dynamics model together with the learned value or just the learned value (in the case of goal conditioned tasks) (Nasiriany et al.) 2019) to improve policy or value estimates. Planning typically happens during roll out (Nasiriany al.[20119 but also be used improve the value target, in Reanalyze of MuZero (Schrittwieser et al. 2019; Ye et al.) (021). During value improvement, if planning takes the maximum over set of possible future values (e.g. from different trajectories
in the case of MPC). and if this set includes the one step Bellman value target, then the planner is essentially using alternative trajectories and their values to lower bound the Bellman value target. In this sense, the theory developed here can potentially justify and improve Reanalyze. In general, planning is orthogonal value target lower bounding, and typically requires additional components and lot more compute than the basic TD learning does. Therefore, we leave it to future work to explore the synergy between the two.
Our work can be seen as extension of the admissible heuristics (bounds) method (Russell & Norvig 2020) into the RL domain. Admissible heuristics speed up the search for the optimal so- lution. For example. it is common practice to lower and upper bound the returns to the possible region, e.g. Andrychowicz et al. (2017) bounds value targets between [- Oj. Episodic return (Section 3.1 provides a tighter bound. addition, our work extends the idea to the case of lower bounding with bootstrapped values, which can overestimate the value. We prove it still converges to the optimal value.
Kumar al. 2020) (DisCor) also recognizes that bootstrapped value targets can be inaccurate. This bias impacts learning adversely under function approximation. DisCor uses distribution correc- tion sample experience with accurate bootstrap targets more frequently, while value target lower bounding aims to directly reduce the bias.
A. POTENTIAL IMPROVEMENT
Note that the goal distance based return (lb-GD) of Section 3.1.1 is a very simple way of arriving at reasonable lower bound with near zero additional computation. The bound could be made tighter. Typically, an L2 distance threshold is used to judge goal achievement, which will likely be satisfied few time steps before exactly arriving at the hindsight goal. To compute such tighter bound would require evaluating the reward function across the trajectories of experience using all possible hindsight goal states, and storing them in the replay buffer, i.e. episode length squared more
33

---

Under review as a conference paper at ICLR 2023
computation and more storage space. It may be worth doing when episodes short, or doing only for a small number time steps into the future when e.g. rewards are non non-negative.
34


Reviews:
[{"review_id": "wAPqsHP9Pjc", "reviewer": "Reviewer_7q5U", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper replaces the value target in TD-based methods with a lower bound of the optimal value function. Convergence was shown in the tabular case and the authors introduced several lower bounds that can be applied to practical algorithms. The authors demonstrated the effectiveness of their method on a series of challenging high-dimensional tasks.", "summary_of_the_review": "While I think the paper does have some merits and introduces a simple yet effective idea, I do not believe the paper is ready for publication in its current form.\n", "strength_and_weaknesses": "Strength:\n- The proposed method is simple and straightforward and can potentially be augmented to many RL algorithms\n- The theoretical analysis does appear to be correct and the convergence result is quite intuitive\n- The related work section is well-written. Since many similar but not entirely identical methods have been proposed, I think the authors did a good job of placing their work within the context of other literature and differentiating their algorithm\n\nWeakness:\n- The authors claimed to introduce a faster technique, however the only analysis on how the proposed method could be “faster” is the third to last paragraph where the authors claimed that the new algorithm is at least as fast as the original. If faster RL is one of the claims of the algorithm, some new analysis in terms of convergence rate would be much appreciated.\n- I could be missing something here, in Section 3 you mentioned using the observed discounted return as a lower bound. When the environment is deterministic, this is certainly true, however in a stochastic environment, this would no longer be the case since it is always possible to get a very large return on an arbitrary rollout. Similarly, the lower bounds proposed in Section 3.2 has a similar issue.\n- The illustrative example in Section 4.3 is not entirely clear, could you give some additional clarification on why the proposed method speeds up learning in this case?\n- Though variations of both SAC and DDPG work for discrete action spaces, both were originally designed for continuous action spaces and are not standard for Atari. I understand the choice of SAC and DDPG since the purpose is to show improvements on a TD-based algorithm but was there a particular reason for using the Atari environments here instead of e.g. MuJoCo?\n- To add on to the previous point, I think while the experiments do show that the proposed methodology can work on complex difficult tasks, it doesn’t help us understand where the improvements actually come from. In this regard, a toy example to demonstrate for example under what scenarios we see faster convergence would be extremely helpful.\n- 3-5 seeds seem very small to give any conclusive results though I understand in some labs computational resources could be limited.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "ubEKJwefYE", "reviewer": "Reviewer_8emL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper explores the use of lower bounds for for value targets in order to improve the sample efficient in Reinforcement Learning algorithms. The authors outline the design of easily computable value lower bounds across different environment settings (episodic or continuous) and algorithms (n-step TD, SAC, HER). They theoretically justify the use of these lower bounds for faster convergence of value iteration. The intuition behind this is closely related to seeding the initial value to a lower bound during value iteration in tabular settings for faster convergence. Moreover, the empirical results demonstrate that the use of value lower bounds under different settings does improve the sample efficiency of these algorithms.", "summary_of_the_review": "\n\nOverall, the paper builds on the rich body of work done previously with different algorithms and the experiments shown are comprehensive and show promising results. However, it further experiments with more sample efficient algorithms such as rainbow and its variants is most welcome.", "strength_and_weaknesses": "Strengths:\n\n- The paper is thorough in that the authors do highlights subtle differences between convergence and contractions, and I do agree with authors that we can generally ignore that fact for empirical studies as we apply this for multiple amounts of time.\n    \n- This also builds into and connects to a lot of episodic learning papers where it can be viewed as simply adding a lower bound term into the value learning and get better rewards[1,2,3], It would be wonderful if the authors could throw some light towards this as these advances have mostly been without theoretical insights.\n    \n- The authors provide reasoning for discrepancies in the results such as “breakout” where the clipping of rewards has a significant effect in the lower bounds.\n    \n\nWeakness:\n\n- It is not clear on this method will improve sample efficiency for algorithms that are designed to be sample efficient to begin with, for example rainbow. Will simply increasing the number of backups during training iterations have a similar effect?\n    \n\nMinor clarity\n\n- When we say ““One such condition is when reward sequences are reproducible, under which, the empirical return from a single experience provides an unbiased estimate of the lower bounded value target” ([pdf](zotero://open-pdf/library/items/4UI97JPI?page=31)) ” Does it mean that it is stochastic in nature ? [pg 31]\n    \n- Could we reprhase “upper bounds are not as readily available as lower bounds” to “tight upper bounds are not as readily available as tight lower bounds”. As v_max can be a trivial upper bound. [pg 30]\n    \n\n[1] Ma, X., Yang, Y., Hu, H., Liu, Q., Yang, J., Zhang, C., Zhao, Q., & Liang, B. (2022). Offline Reinforcement Learning with Value-based Episodic Memory. *ArXiv, abs/2110.09796*.\n\n[2] Sarrico, M., Arulkumaran, K., Agostinelli, A., Richemond, P.H., & Bharath, A.A. (2019). Sample-Efficient Reinforcement Learning with Maximum Entropy Mellowmax Episodic Control. *ArXiv, abs/1911.09615*.\n\n[3] Lin, Z., Zhao, T., Yang, G., & Zhang, L. (2018). Episodic Memory Deep Q-Networks. *ArXiv, abs/1805.07603*.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "7iAOA683O6n", "reviewer": "Reviewer_JN96", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper suggests using a function that lower-bounds the optimal Q function (such as Monte-Carlo returns) as target values in Q-learning methods for faster convergence. The authors provide a theoretical justification for this technique and propose several variants for episodic/goal-reaching/non-episodic settings. They demonstrate that the proposed technique applied to Q-learning methods (SAC, DDPG, TD3) helps improve performance in diverse environments.", "summary_of_the_review": "I believe this is a borderline paper. Since most of my concerns lie in the experimental results, I would be happy to increase my score if the authors provide a more extensive evaluation of their method.\n\n*Post-rebuttal update*: Thank you for the response. I checked the comparisons between lb-DR and DDQN on four Atari games in Appendix A.6, but I am still not fully convinced regarding lb-DR's performance as the number of games is highly limited (4 out of 56 games for DDQN and (an unusual set of) 17 games out of 56 for SAC), especially given the simplicity of the method. Hence, I would vote for a weak reject for now.", "strength_and_weaknesses": "## Strengths\n- The proposed method is simple and sensible.\n- Their theorems provide insights into their method.\n- The limitations of the proposed method and theorems are well addressed throughout the paper.\n\n## Weaknesses\n- The main weakness of this work is on its experimental setup. They use somewhat unusual combinations of base RL algorithms and environments. For example, they use SAC for Atari games, which is an uncommon choice especially given that Atari games have a discrete action space. I believe it would be desirable to test and compare their method with more widely used setups. How does the method perform with DQN or Rainbow on Atari games? Also, the authors only evaluate their method on an unusual subset of 17 games. Is there any previous work that uses the same setting? Could the authors provide additional results on the other games?\n- The novelty of the method is limited (please see the section below for details).\n- The proposed value target lower bounding technique can only be applied to deterministic environments. That being said, I believe this technique can still benefit some (deterministic or stochastic) environments in the real world, especially when initial target values are not informative enough.\n- The code is not released.\n\n## Questions\n- How do the authors modify SAC to deal with discrete actions?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject