Faster Reinforcement Learning with Value Target Lower Bounding
Authors: Le Zhao
Wei Xu
Venue: ICLR 2022 Submitted (2022)
Keywords: reinforcement learning
bellman value target
lower bound
discounted return

Abstract: We show that an arbitrary lower bound of the optimal value function can be used to improve the Bellman value target during value learning.  In the tabular case, value learning under the lower bounded Bellman operator converges to the same optimal value as under the original Bellman operator, at a potentially faster speed.  In practice, discounted episodic return from the training experience or discounted goal return from hindsight relabeling can serve as the value lower bound when the environment is deterministic.  This is because the empirical episodic return from any state can always be repeated through the same action sequence in a deterministic environment, thus a lower bound of the optimal value from the state.  We experiment on Atari games, FetchEnv tasks and a challenging physically simulated car push and reach task.  We show that in most cases, simply lower bounding with the discounted episodic return performs at least as well as common baselines such as TD3, SAC and Hindsight Experience Replay (HER).  It learns much faster than TD3 or HER on some of the harder continuous control tasks, requiring minimal or no parameter tuning.

Under review as a conference paper at ICLR 2022
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 optimal value function can 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 potentially faster speed. practice, discounted episodic return from the training experience or discounted goal return from hindsight relabeling environment is deterministic. We experiment on Atari games, FetchEnv tasks and challenging physically simulated car push and reach task. We show that in most cases, simply lower bounding with the discounted episodic return performs bet- ter as well as common baselines such TD3, SAC and Hindsight Experience Replay (HER). It learns much faster than TD3 or HER on some of the harder con- tinuous control tasks, requiring minimal additional computation and parameter tuning. We are not the first to introduce this simple yet effective technique, but the first to demonstrate its optimality in theory and effectiveness in a wide range of tasks and related baseline methods.
serve as the value lower bound when the
INTRODUCTION
In temporal difference (TD) learning, the value function is adjusted toward its Bellman target, which the reward of the current step plus the discounted value of the next state. This forms the basis of many state of the art reinforcement learning (RL) algorithms such as DQN (Mnih et al., 2013), DDPG (Liliicrap et al. 2015), TD3 (Fujimoto et al., 2018). and SAC (Haarnoja et al. 2018).
The value of the next state is typically estimated using "bootstrapped value" based on the value function itself, which is being actively learned during training. The bootstrapped values can be random very inaccurate, especially the initial stage of training. Consequently, the Bellman value targets as well as the learned value are usually far away from the optimal value.
Naturally, this leads to the following idea: If we make the value target closer to the optimal 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, we could use the observed discounted return up to episode end from the training trajectories to lower bound the value target. This makes the new value target closer to the optimal value, when the empirical return is higher than the Bellman target.
Will such way of lower bounding the value target work: Will it still converge? Will it converge the optimal value? Will it speed up value learning?
2 THEORETICAL RESULTS FOR THE TABULAR CASE
For the tabular case, value target lower bounding converges to the same optimal value as the original Bellman value learning, and the proof is also straightforward
2.1 BACKGROUND
In finite MDPs with a limited number of states and actions, table can be used to keep track of the value of each state. Using dynamic programming algorithms such value iteration, values

---

Under review as a conference paper at ICLR 2022
guaranteed to converge to the optimal through Bellman updates (Chapter 4.4 (Sutton & Barto
2018
Algorithm 1: Bellman value iteration with value target lower bounding
Data: Finite MDP p(s', r|s, a), convergence threshold Result: State value us))
(s)) 5 0;
repeat
A + 0:
for each state s do
v(s);
v(s) - max(f; max, r(s,,rls,gg,)) ru(ss)))
A - max lu(s) - =l);
end
until A 0;
The core of the algorithm is the Bellman update of the value function, B(v):
((o)(s) max Σ pls' rls, a) yo(s')
is well known that the Bellman operator, B, is a contraction mapping over value functions Denardo 1967). That is, for any two value functions i1 and v2. [B(01) B(ug)l S 7/41 U2l for the discount factor 7 E (0.1). This guarantees that any value function under the algorithm converges to the optimal value
2.2 VALUE TARGET LOWER BOUNDING CONVERGENCE THEOREM
Theorem 1. Suppose the optimal value under the Bellman operator is B (v). For any value func- tion f that lower bounds the optimal value, i.e. Vs, f(s) < B (s), if define the lower bounded Bellman operator as My B(v)= = (Bu), f), then (M, o B) (v) converges to 8 (v).
A few things to note about the proof (see Appendix A.1
First, this only proves convergence, not contraction under the original ||01 - -uyl2 metrie In the case of the Bellman operator, contraction shows that Vei, U2 value functions, - (B<)))) < 2/1u - u2|l ho Here, for value target lower bounding, there can be counter examples where M, o B does not always contract in the original metric space for value functions. Here, convergence relies on the convergence of the Bellman value iteration and the existence the fixed point v". One difficulty caused by this change is that the stopping criterion in Algorithm (A < 0) no longer works, do not have access to the converged value during learning. This is perhaps not serious concern in practice, 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.c. f(s) B(v1)ss, there is chance for the convergence to be faster. Convergence strictly faster when the lower bound f has an impact on the Tox distance between the current value and the optimal value, i.e. it increases the value target for the states where the differences between the value target and the optimal value are the largest.
Third, the lower bound function doesn't have be static during training. As long there is single f during each iteration, convergence property is preserved.
Fourth, the theory works when the underlying MDP is stochastic. Only the lower bounds based on empirical return introduced below require the MDP to be deterministic.
See, for example, page 8 for the gist of the proof https://peop's eecs. werkeley. eey..dy/ spabbee1/cs281 httpee////oaaoa////////ooororr/r
2

---

Under review as a conference paper at ICLR 2022
3 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 alternative lower bounds.
3.1 EPISODIC TASKS
In episodic tasks, discounted return is only accumulated up to the last step of an episode. In this case, we can wait until an episode ends, and compute future discounted returns of all time steps inside the episode. This discounted return is guaranteed to be lower bound of the optimal value, the environment deterministic, i.e. the reward sequence can be repeated using the exact same sequence of actions. (The behavior policy need not be deterministic, as long as the policy class contains the deterministic optimal policy.) To make training efficient, we can compute and store such discounted returns into the replay buffer for each time step, and simply read them out during training.
We call this variant lb-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 is d time steps away from the current state 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, we know it took d steps to reach the hindsight goal, so the discounted future return is:
Ra Σ -17"
i=0,..,d-1
(2)
= =- 1(1 - 1-)11111111))
This calculation can be done on the fly as hindsight relaheling happens, requiring no extra space and very little computation.
We call this variant Ib-GD, short for lower bounding with goal distance based return.
also apply Ib-DR and Ib-GD together, with discounted return lower bounding (lb-DR) on the original experience and goal distance return lower bounding (lb-GD) on the hindsight experience, giving the Ib-DR+GD variant, which used by Fujita et al. 2020 independently.
Additionally,
3.2 NON-EPISODIC TASKS WITH POSITIVE REWARDS
When the task is continuing, without an episode end, discounted return needs to be accumulated all the way to infinity. This makes it difficult lower bound the value rewards can be negative. When rewards are always non-negative, one can still use the discounted return of the future n-steps lower bound the value. Chapter 3.3 of Sutton & Barto (2018) has more details on episodic vs continuing tasks.
4
INTEGRATION INTO RL ALGORIHHM
4.1 BACKGROUND
The value target lower bounds can be readily plugged into RL algorithms that regresses value to target, e.g. DQN, DDPG or SAC.
In these algorithms, the action value q(s, a) is learned through squared loss with the target value In one step TD return, for batch B of experience {s, - r, s') s'}. the loss is:
Lgg
Σ (s
lg(s,a) y
(3)
3

---

Under review as a conference paper at ICLR 2022
In one step TD return, is the step TD return a(s,,,
Here, of and μl 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, we replace the value target y with the lower bounded target:
- m(x, a(,,,,r,8)) = max(S,r 7o (())))
(5)
This is subtly but importantly different from lower bounding the value directly (Oh et al. 2018 Tang 2020 qss, a) f max {(s,))) which stays overestimated (s,s initially overestimates. This is the same as was done by Fujita et al. (2020) (confirmed via personal communication),
This way of simply lower bounding the value target does not require any tuning parameter, but one can always interpolate between these two value targets using a mixing weight a:
y (1-a) a) max(ff
A small dampens the effect of the new value target, and may be desirable in practice when sumptions of the theorem can be violated, c.g. for non-deterministic tasks.
See Appendix A.2 for an illustrative example of how value target lower bounding works in practice.
EXPERIMENTS
The goal is demonstrate the sample efficiency of lower bounding the value target over baseline such DDPG, TD3, SAC and HER. Because the lower bounded value target can now look poten- tially many steps into future, we suspect it to be best suited for long horizon, sparse reward tasks. Hence, we choose to experiment on the following tasks.
5.1 ENVIRONMENTS AND TASKS
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, both empirical discounted return and hindsight relabeling with discounted goal return as lower bound are available.
5.1.1 ATART GAMES
We experiment on the classical Atari games with image input to test using discounted episodic return lower bound value target. We picked the popular games Breakout, Seaquest, Space Invaders, Atlantis, Frostbite and Q*bert, and only experimented on them. As with prior work (Oh et al.] 20018), we evaluate on the deterministic versions of the games, NoFrameskip-ve with actions repeated for fixed (four) frames.
5.1.2 EPISODIC FETCH PUSH, SLIDE AND PICKANDPLACE
The FetchEnv tasks (Plappert al. 2018 objects on 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 translates 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 for goal states.
goal conditioned tasks with robotic arm moving
4

---

Under review as a conference paper at ICLR 2022
By default the FetchEny tasks 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. 2017). As explained in Section 3.1 to allow reliable estimates of return lower bounds to be caleulated from past experience, we make them episodic by adding 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, as is done in the original FetchEnv, and such experience is not used in value target lower bounding [ 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 FetchEnv 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 at 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.)
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.
5.1.3 PIONEER PUSH AND REACH TASKS
Figure 1: The Pioneer Push task and the Push and Reach task.
This is a set of challenging goal reaching and object pushing tasks for the physically simulated car Pioneer 2dx. The is 0.4 meter long. Objects and goal positions are randomly initialized between 0.5 meter to I 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.
For the Pioneer Push task, the car has to push a block to within 0.5 meter of the dimensional goal position indicated by small red dot the ground. For the Pioneer Push and Reach task, the has to first push the object to the goal location (red dot) and then drive to a separate goal position (red ball in the air); the goal 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 La disttaeee
Similar to FetchEnv, we make the tasks episodic with sparse goal reward.
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.
Fujita et al. (220)) 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 episade start as input to the agent, so that the agent is aware of the approaching episode end.
5

---

Under review as a conference paper at ICLR 2022
5.2 BASELINES
Baselines include DDPG (Lillicrap et al. 2015). TD3 (Fujimoto et al. 2018). SAC (Haamoja al.,
2018) and HER (Andrychowicz a (011)). Implementations are based on open sourced reposito- ries, and baseline performance is verified against published results under similar settings.
5.3 HYPERPARAMETERS
The value target lower bounding method itself does not have any hyperparameter, the only hyperpa- rameters come from the baseline method. Hyperparameters for the baselines follow published work as much as possible. When tuning baseline hyperparameters, we searched for the best performance in totoal episodic reward, on one set of random seeds. Optimal hyperparameters are then fixed and evaluated on separate set of random seeds never seen during development. For the treatment, just used the optimal parameters from the baseline tuning, except for the Atari games where we found the treatment benefit from more (eight) minibatch updates of size 250 per training iteration (instead of four updates 500) and from skipping reward clipping. Hyperparameter values are detailed in Appendix A.3
5.4 RESULTS
We show evaluation performance averaged across separate training runs (five for the less stable Atari games and three for the others). Each run uses a random seed never seen during development.
5.4.1 LB-DR VS BASELINE SAC/DDPG
Figure compares lower bounding with discounted return (Ib-DR) against SAC or DDPG baseline on Atari games and the episodic FetchEnv tasks.
For most tasks, lower bounding with episodic discounted return (Ib-DR) performs similarly or better than the baselines. On Atari Breakout, Atlantis, Frostbite and bertt, and FetchPush and Fetch- PickAndPlace the gains are quite large. On Atari Seaquest, there is still a significant sample effi- ciency gain initially.
The lh-DR method effective, but is it really due to improvements to the value targets? Figure 5 (Appendix (A.4) looks the fraction of training experience where lower bounded value target is actually higher than the baseline Bellman value target over the course of training. For the episodic FetchEnv tasks, training progresses, meaningful fraction of experience start benefit from better value targets, and the average return performance also starts to improve over the baseline, although large fraction of experience benefiting from higher value targets does not always mean a much higher average return (see FetchSlide). For most Atari games, improved value target does lead to significant performance gains, the only exception being Breakout, where value improvement does not immediately lead to performance gain.
5.4.2 LB-GD AND LB- D--DR+GD VS HER
Figure compares lower bounding with goal distance return (lb-GD) and lower bounding with both goal distance and discounted return combined (Ib-DR+GD) against the much stronger HER bascline, on the goal conditioned episodic FetchEnv and Pioneer tasks.
seems on the casier FetchEny tasks, lower bounding isn't able to outperform HER, but on the more challenging Pioneer Push and Reach tasks, lower bounding is able to achieve 70% more sample efficiency. seems the more complex the task, the wider the margin of gain.
We also looked at the fraction of experience where the lower bounding goal return is higher than the Bellman target (see Appendix A.4). It quickly grows to 1-8% and then slowly drops, matching the region where the method outperforms the baselines in average return.

---

Under review as a conference paper at ICLR 2022
OR Jound)
1900
(ound)
1200
D+ 1100
250
500
4000
Arc-ggh ug..g. Eusede Polam
20000
650
000
250
350
300
3.0
0.8
1.2
0UB
3.0
Envrommort
Enrntormmnt Staps
(a) Atari Breakout
(b) Atari Seaquest
(c) Atari Space Invaders
100000
I: (surs)
16000
B-09 (wnr)
16/000
1.4000
14/000
2300
Nenaag Edterta Daar
12500
100000
A00000
80000
Avesge
1300
8200
8000
40000
000
20000
00
0.2
DU4
D8
0.8
1.2
0.0
0.4
0.0
Endrermant Stepe
20e
Envrrneent Stapp
10r
Devtreren Stepe
10r
(d) Atari Atlantis
(e) Atari Frostbite
(l) Atari Q*bert
(sum)
(oung
stpg
-10
-10
Avrrgg 3od000d000000 Ruam
Avc Merogge-0 Sosoee Ream
-90
0.
1.5
20 sed
-50
1.0
1.5
2.0
-80
0.5
1.0
2.5
2.0
Enwnamment Staee
Drvmmnment Stepss
100
Eraitromeet Stege
100
(g) FetchPush
(h) FetchSlide
(i) FetchPickAndPlace
Figure 2: Evaluated average return of value target lower bounding with discounted return (lb-DR) vs SAC or DDPG on Atari games and episodic FetchEny tasks. Solid curves are the mean across five (for Atari) or three (others) seeds, and shaded areas are +/- one standard deviation.
7

---

Under review as a conference paper at ICLR 2022
bORIIDD b-60
-10
Avcrage So Resurn
-20
-20
CD (uus
GG (ours)
B-G2 (an)
Ib-GD (oun)
her
-00
0.
0.5
3.0
25
26
-50
00
0.5
1.0
1.5
2.0
00
0.5
1.0
2,5
2.0
Envranment Shepe
Drvernment Staps
Envectmmen Steps
(a) FetchPush
(b) FetchSlide
(c) FetchPickAndPlace
It-OR-GD (ous)
DRROO (00n))
Janting Edter Bram
Ecnecte Ream
-75
-200
-00
-325
-150
90
-100
-200
0.00
0.29
0.50
0.75
1.00
1.25
Enwornrens.eess
106
EnvoommeesStess
207
(d) PioncerPush
(c) PioncerPushReach
Figure 3: Value target lower bounding with goal distance return (Ib-GD) and Ib-DR+GD HER on episodic FetchEny and Pioneer tasks. Solid curves are the mean across three seeds, and shaded areas are +/- one standard deviation.
RELATED WORK
Prior works (Fujita et al., 2020 Hoppe& & Toussaint 2020 He et al., 2016 Oh et al., 2018 Tang 2020) employed 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. Our work is the first to point out that one efficient way of doing it, namely value target lower bounding, converges to the optimal value in the tabular case. We are the first to point out that the theory works generally, even for stochastic environments. We list several possible ways of computing the lower bound from training experience, which are true lower bounds only for deterministic environments, and demonstrate the effectiveness of such lower bounds in illustrative examples and experiments on a variety of tasks.
Fujita al. (2020) used method very similar to the Ib-DR+GD variant, noted the limitation to deterministic tasks, and showed that value target lower bounding improved sample efficiency for a goal conditioned robotic grasping task. Hoppe & Toussaint (2020) similarly proposed bound the value target using simplified MDP with a subset of actions of the original MDP. Neither work gave any theoretical guarantee.
He et al. (2016) used empirical return with bootstrap to improve value learning. They integrate the lower (and upper) bounds as constraints when optimizing the Q function. Their method more difficult to use due to an additional loss and hyperparameters to tune, and is more expensive to compute than directly lower bounding the value target. Their method needs to evaluate the value function on all future time steps. This severely limits how many time steps it can look ahead when computing discounted return. They evaluated on Atari games, showing higher sample efficiency than DQN, but appears worse than value target lower bounding on Breakout, probably due to looking ahead only four time steps. The limitation to deterministic tasks wasn't 't mentioned in the paper, (but is actually present due to the use of empirical return in computing the lower bound), and neither any convergence analysis. Appendix A.5 offers more discussions related to this method and n-step returns.
8

---

Under review as a conference paper at ICLR 2022
Our work is subtly but importantly different from the prior works lower bound Q learning 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 or PPO) training (T calue 2 (u(ss) max max(((()) 1²) When the value function overestimates, the SIL value loss becomes zero, and keeps overestimating. Mixing the SIL. loss with the loss from the baseline algorithms probably helped to correct the overestimation, but no theoretical guarantee was given. In evaluation, SIL was often compared 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 off- off-policy value learning. In this work, we bound the Bellman value target (Equation [5). 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.
Kumar et al. 2020) (DisCor) also recognized that bootstrapped value targets can be inaccurate. It impacts learning adversely under function approximation, while we handle the general case. DisCor uses distribution correction sample experience with accurate bootstrap targets more frequently.
Interestingly, it is common practice to lower and upper bound the returns to the possible region, e.g. Andrychowicz et al. (0177) bounds value between 0].
CONCLUSIONS
In theory, value target lower bounding converges to the same optimal solution as the original Bellman value iteration. In practice, several ways of finding value lower bounds using empirical discounted return for deterministic episodic tasks are examined.
Precomputing discounted future return and storing into the replay buffer allows efficient lower bound computation, and can achieve much higher sample efficiency than baselines such as SAC, DDPG or TD3 in most tasks. The Appendix A.5 also includes comparisons against related methods such as td-lambda and Retrace.
Simple goal distance based return, requiring little extra space compute, achieves large gains in certain long horizon tasks over HER, and performs similarly as HER in the simpler tasks.
7.1 FUTURE WORK
There are probably better ways of finding value lower bounds that speed up training even more. There may be ways of using bootstrapped value in computing the lower bound, for n-step return targets or for non-episodic tasks.
Estimating value lower bound for environments with stochastic transitions rewards may be pos- sible, e.g. by learning a reward function to help average out the randomness in the empirical return. Extending to partially observable environments would be harder but probably still doable.
Other ways of bounding the value target, e.g. upper bounding, may be worth investigating as well, e.g. reduce overestimation in regions of poor reward.
REPRODUCIBILITY STATEMENT
Our code change is based on a publicly available RL library, with strong baselines already imple- mented. Our relatively small code change is committed to a private github repository, which we plan to open source upon publication. When running experiments, the snapshot of the code used to run each experiment is stored together with the results. Experiment parameters are gin-configured and controlled by our automation script, with each experiment label corresponding to the set of con- figurations used for that experiment, so there is little room for manual error when running many experiments across different tasks, methods and hyperparameters.
Experiments are done in simulation with pseudo randomness. We've run 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'r ve also our code on different hardware and software (CUDA and pytorch), and the results are similar though not the same at the float number level.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojciech Zaremba. Hindsight experience re- play. In Advances in Neural Information Processing Systems, volume 30, 2017.
Eric V. Denardo.
Contraction mappings in the theory underlying dynamic programming. SIAM Review, 9()):665-77,, 1967. ISSN 00361445, URL http:///ww..atcor.orrrttttaaaaa 2027440
Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. CoRR, 2.18. UHt.http///arrvv.oott//a/s/ 0tt..///1110027707777 09477)
Yasuhiro Fujita, Kota Uenishi, Avinash Ummadisingu, Prabhat Nagarajan, Shimpei Masuda, and Mario Ynocente Castro. Distributed reinforcement Jeannin of targeted grasping with active vision for mobile manipulators, 2020.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor, 2018.
Frank S. He, Yang Liu, Alexander G. Schwing, and Jian Peng. Learning to play in a day: Faster deep reinforcement learning by optimality tightening, 2016.
Sabrina Hoppe and Mare Toussaint. Qgraph-bounded q-learning: Stabilizing model-free off off-policy
deep reinforcement learning, 2020.
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 httpp:://proccednggg.. wwwp:/ocooc...oo.o.............. neurips.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver. and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint drXiv:1509.0297,, 2015.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Joannis Antonoglou, Daan Wierstra, and Martin A. Riedmiller. Playing atari with deep reinforcement learning. CoRR, abs/1312.5602, 2013.
5602
Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Marc Bellemare. Safe and efficient off- policy reinforcement learning, 2016.
Junhyuk Oh, Yijie Guo, Satinder Singh, and Honglak Lee. Self-imitation learning. CORR, abs/1 8060/800605635. 2018. URtpptt://aaxx wwwps/sswrr///////o//a/aa..sssss 10611.6666666)))
Matthias Plappert, Marcin Andrychowicz, Alex Ray, Bob McGrew, Bowen Baker, Glenn Powell, Jonas Schneider, Josh Tobin, Maciek Chociej. Peter Welinder, Vikash Kumar, and Wojciech Zaremba. Multi-goal reinforcement learning: Challenging robotics environments and request for research. CoRR. abs/1802.099444, 2018. Wtt.L/ttpp//axxx..ooo//////
09464
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. Bradford Book, Cambridge, MA, USA, 2018. ISBN 0262039249.
Yunhao Tang. Self-imitation learning via generalized lower bound q-learning abs/2006.07442. 2020. hwt.btttp///axxi.orrg///
CoRR,
07442
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double 4- learning. CoRR, 509./6609.06611, 2015. URL htt.://p///arii..o/////////0...0
10

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1 PROOF OF THEOREM I
We want to prove that under the new operator M, B, the value function converges the same optimal value function given by the Bellman operator B.
Proof. Let be the fixed point and optimal value of the original Bellman operator: o" = 8 (v),
f1 be any value function, and any state,
M (())) "² (s)
(Mx))
+
Vs where f(s) (s)
above = [f()) - (s)) =s( - f(s) < (s) B(s))(s) = [B()) - o" (s))
above =
(This is because lower bounds v² : =s) 2 f(s) > (s)))
Vs where f(s) _ (s):
above = (s) - v" (s)
<IB(v)) vs)
= =BB(v))(s) - B(e*)())())) (s)
Sy1lu1-0 -0
The last line above because the Bellman operator B contracts at rate 7,
Hence, [|M B(ri) v" v*|l>o- max, IM, (s) v² (s)l S 7/lp1 v² llac
According to the definition of convergence to v², we need find an N, such that Ve > 0, Vo * v*, Vn > N, (M, o (v1) o² |lo <.
We can easily calculate that = log, ----v- (note, 7 1) satisfies the condition, which concludes the proof that any value function in will converge to r under the lower bounded Bellman operator My o B.
This proof works for action values as well, by simply replacing the value function above v(s) with the action value q(8, a), and the value lower bound f(x) with the action value lower bound f(s, a).
A.2 AN ILLUSTRATIVE EXAMPLE
Figure Fincludes a fairly general example showing how value target lower bounding would improve value learning. Suppose enhance 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 is 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 likely speed up learning quite a bit.
A.3 HYPERPARAMETERS
Hyperparameters of the baseline algorithms follow published work the case of FetchEnv (Plappert et al. 2018). For Atari and Pioneer Push and Reach tasks, they are tuned using one set of random seeds and after keeping the hyperparameters fixed, trained with a different set of random seeds and evaluated. We avoided tuning of the parameters of the baseline method for value target lower bounding, except for the Atari games where value target lower bounding learned a bit faster with slightly more frequent training updates (8 updates of 250 transitions per training iteration) than the baseline (4 updates of 500 transitions) and without reward clipping. For Atari Atlantis, Frostbite and **bert, we report results with reward clipping as it did not affect performance much.
11

---

Under review as a conference paper at ICLR 2022
Baseline: 0
Baseline: 1
Baseline: 2
(a) Baseline: 3
Lower bounding:
Lower bounding:
Lower bounding:
Lower bounding:
Illustration of value target lower bounding speeding up value learning as training pro- gresses from stages O to 3. The task is to navigate in the state space from start state S to end state T, with sparse reward I at T and 0 elsewhere. The curve from that reaches the target. The shaded areas denote roughly states whose value has been significantly improved during training up to that stage.
Figure 4:
denotes a training experience
Baseline parameters reported below are tuned using development random seeds and fixed during evaluation with separate set of random seeds.
For the Atari games, DQN with only one training environment takes long to train so we instead use SAC as baseline. There are no strong reported results, so we tuned the hyperparameters bit and found use 30 environments, unrolling 8 time steps every training iteration, with each iteration containing 4 updates each with a minibatch 500 transitions sampled from the million time step replay buffer. 500 time steps collected before training starts. Target networks are updated every 20 training updates. Discount y = 0.99. The SAC target entropy is set to the entropy of uniformly distributing 0.1 probability mass across all but one actions. Actions (even for Space Invaders, despite being used by Mnih et al. (2013), and the latest 4 frames are stacked and rescaled [-1, 1] to form the 84x84x4 input tensor. Rewards and 1. Network structures are the same as Double DQN (van Hasselt et al. 2015)) with 3 convolution layers, with input layer 32 filters of size 8 stride then 64 filters of size stride 2 and 64 filters with size 3 stride 1, I fully connected of size 512 before output. We train for 12 million steps (48 million frames) for each task (except for Atlantis where episodes are very long and we only train for 6 million steps) and evaluate every 1000 iterations averaging across 100 episodes using e-greedy policy with 5% random actions.
outperform published Actor-Critic results on Atari Breakout (Oh et al.) 2018). We
repeated deterministically for 4 frames
clipped between -1
For FetchEny tasks, DDPG and HER learn faster than their TD3 variants and are reported here. Hyperparameters are the same as used by |llappert et al.] (2018), with 38 parallel environments unrolling 50 time steps per train iteration, training 40 updates per iteration, targets updated once every 40 updates. For each update, a minibatch of 5000 transitions are sampled from the replay buffer of size 2 million. Discount y 0.98. Actions c-greedy with 30% random actions. 80% hindsight experience. Observations are normalized to have zero mean and unit variance based on the statistics of the recent observations Networks are 3 fully connected layers of size 256. Length of the episodes are capped at 50. We train for 2 million frames and evaluate every 40 iterations averaging across 200 episodes.
For Pioneer Push and Reach tasks, TD3 is used, (we simply equip DDPG with two critics for clipped double Q learningFyjimoto et 2018)), which works better than DDPG with one critic. Param- eters are mostly the same as in FetchEnv, except for using 30 parallel environments, 100 steps of unroll per training iteration, million time step replay buffer, 50% hindsight experience, discount 0.99 and not using observation normalization. Length of the episodes are capped at 100 for Push and 200 for Push and Reach. We train for million frames for Push and 14 million for PushReach and evaluate every 200 iterations averaging across 100 episodes.
We found that the of observation normalization is critical in reproducing HER results FetchEnv.
12

---

Under review as a conference paper at ICLR 2022
For FetchEnv and Pioneer tasks, the target networks updated every 40 train updates softly, with weight 0.95 on the existing target network parameters and 0.05 on the incoming.
We use Adam optimizer with learning rate 5e for the Atari games and 1e for all others, and é = le - for all tasks.
A.4
PLOTS
0.00
0.20
0.30
bi (Aus)
b. (our))
D- (ours)
0.55
0.25
b-Dit Polan Greate Paus
0.35
Ratur
0.35
0.15
0.30
0.02
0.0
0.05
0.00
Thaiking tenatons
104
Thaniin Henearm
104
The ming harnd
204
(a) Atari Breakout
(b) Atari Seaquest
(c) Atari Space Invaders
0.90
0.50
0.30
(sum)
(ous)
0.23
0.25
0.25
DL Reaan CransePa
0.20
0.2
0.2
0.56
0.35
0:15
0.95
0.00
0.5
1.0
1.5
20
25
0.00
0.00
Theiiing Beneioos
Tru ring fernd
(d) Atari Atlantis
(c) Atari Frostbite
(f) Atari Qebert
bdR
bOR
Ib-R
0.000
0.000
0.000
0.005
0.025
9-3R Dww.
0.025
2R Patum
0.000
0.000
0.615
0.00
0.000
0.05
0.025
0.000
00
0.
0.4
0.5
0.8
100
0.000
0.0
0.2
0.5
0.5
0.8
3.2
0.000
00
0.2
0.4
0.8
05
1.0
Twiikig Broecons
Treniing Inoiioon
Trainig Dendkone
(g) FetchPush
(h) FetchSlide
(i) FetchPickAAnPlace
Figure 5: Fraction of training experience where lb-DR value target is 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.
Figure 5 shows the fraction of training experience where lb-DR value target is greater than the Bellman target from SAC/DDPG. They correlate well with actual performance (Figure 2 and with how value is learning (Figure D). For Atari Breakout the converged value is much higher than that of the baseline. It is unlike an overestimation, and is actually close the average discounted return that we also summarized in tensorboard (omitted here) | The baseline value of 2 is actually very far away from its average discounted return of 25, even though its policy is already getting a reward of
BBack of envelope calculation: an episode of reward 400 evenly spread across 1000 time steps with 0.99
step discount would lead to an average value of roughly 400/1000
40.
0.99
13

---

Under review as a conference paper at ICLR 2022
200 per episode. This is likely due to the inaccurate bootstrap values of the baseline method, and will probably take much longer to converge.
50
D-3R (p0s))
250
200
80
Moun Truking Volue
00
8:00
60
Mean Tuaain
80
20
2
2
3
Traniigg Hostors
Ind
Tiikiing Deokkcon
Traninn Hecdioos
(a) Atari Breakout
(b) Atari Seaquest
(c) Atari Space Invaders
I- (eun))
(mmm))
(su))
coc
25
20
Tharnng Valae
-0
Moan Thalingg Value
15
(Wenn Traiing
15
10
0.0
0.5
3.0
1.5
20
25
Tramiig Danationa
Traning Benatons
Traniig Fanatorr
(d) Atari Atlantis
(e) Atari Frostbite
(I) Atari Qubert
b-
b-0R
-10
-10
Moat Funnir SolLe
-20
-15
Meat
-30
0.
0.2
0.4
0.6
0.3
2.0
-30
00
0.2
0.4
0.6
0.5
1.0
-30
0.0
0.2
0.4
0.5
0.8
1.0
Trahiig toratore
Training Resuaioos
Training addons
(g) FetchPush
(h) FetchSlide
(i) FetchPickAndPPace
Figure 6: Learned values of Ib-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.
Figure 7 shows the fraction of training experience where the Ib-GD is higher than the Bellman value target from HER, in the goal conditioned (cpisodic FetchEnv and Pioneer) tasks. 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 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%).
This again correlates well with the value learned, shown in Figure g
14

---

Under review as a conference paper at ICLR 2022
DP CD CD (AMr)
DRICC (Dar))
GD bung
Roram Graae Rua
8:00 Geste Euth
0.008
80.08
0.004
0.004
0.002
b- CD pura
0.012
I--00 (wan))
0.000
0.0
02
0A4
088
100
0,000
0.0
0.2
0.4
0.8
3.0
0,000
0.0
0.2
0.44
0.8
0.6
3.0
Thaniin Bonicort
Traniing Nanatorn
Trainin tanalion
(a) FetchPush
(b) FetchStide
(c) FetchPickAndPlace
B-0RvG0 (Hu))
2-0R+G0
B-G.0 (sm))
0.00
0.08
1:00 RMU O
b-GD Rel.mnnnnn Gra.eeeeeeeeee
0.00
0.08
0.04
0:04
0.62
0.02
0.00
0.00
3e0
142
(d) PioneorPush
(c) PioncerPushReach
Figure 7: Fraction of training experience where Ib-GD or Ib-DR+GD value target greater than the Bellman target, episodic FetchEnv and Pioneer tasks, plotted against the number of training iterations. Solid curves are the mean across three seeds, and shaded areas are +/- one standard deviation.
A.5
N-STEP RETURN BASED METHODS
A.5.1 N-STEP RETURN METHODS
We also experimented with n-step return, td-lambda return and Retrace (Munos et al. 2016) but decided give up the direction due the following reasons:
1) We compared DDPG one-step return against DDPG with n-step return, td-lambda and Retrace on FetchPush, and found that a small n works similarly as the baseline one-step DDPG, and a larger hurts training. 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, for example, when off-policy low return experiences are used to compute value targets. Introducing importance sampling weights (Retrace) would help reduce the bias, but at the same time significantly downweight the off-policy high return experiences, making an ineffective use of such experiences. The overall benefit of n-step methods is limited.
None of these issues are present in value target lower bounding: (a) does not ineur any off-policy bias, and (b) long an experience renders high reward, being off-policy does not affect its ability to improve the value target.
2) Computing n-step td-lambda return requires more computation due to evaluating value networks on all n-steps of the experience, and slows down training time significantly with a large n.
On the other hand, value target lower bounding precomputes and stores discounted return in the replay buffer, and incurs very little additional computation.
3) Tuning n-step return involves many hyperparameters like the number of steps n, the td-lambda parameter, replay buffer size and prioritized replay to expire old experiences and sample recent ones more frequently, target network update parameters parameters for importance sampling. But still, after all the tuning, it only slightly outperform one- step DDPG on FetchPush SAC Breakout, and is below the lower bounding method. For td-
reduce potential overestimation, and
15

---

Under review as a conference paper at ICLR 2022
B-ORH B-GD
bORIID b-60
IND
It-GD Joun)
Mear Traaiing SAMAR
Maur Traaeno 50000
-14
-14
00
0.2
0.4
0.6
0.3
2.
00
0.2
0.4
0.6
0.2
10
0.0
0.2
0.4
0.3
0.8
1.0
Traring haralorm
Theiing lleratorm
Thaisung (aeraoone
(a) FetchPush
(b) FetchSlide
(c) FetchPickAndPlace
Ib-R-GD (wun)
I--DRIGD (Nan
1o-G poun)
he'
Noan Yous
WWen Thwaeeg Villu
-10
-90
-80
-00
-70
-30
0.0
0.5
1.0
1.3
-100
2
Traning Ewediioe
303
Training Reruion
323
(d) PioncerPush
(c) PioneerReach
Figure 8: Learned values of Ib-DR, Ib-DR+GD and HER episodic FetchEnv and Pioneer tasks, 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.
lambda and Retrace, the best performance comes from 3-step td with x= 0.95, replay buffer length 400k and all other parameters the same as the baseline DDPG or SAC. Retrace underperforming the baseline in Breakout is similarly observed in the original paper (Munos et al. 2016).
On the other hand, value target lower bounding requires no hyperparameter tuning, learns faster on most tasks and converges higher on some of the more difficult tasks.
4) Value target lower bounding can be applied on top of n-step return methods as well, so is more of an orthogonal problem.
Overall, n-step methods are much more expensive and difficult to use, and the much simpler and effective lower bounding method still maintains an advantage in effectiveness and performance. We show the performance comparison in Figure 9 with learned values in Figure I0
A.5.2 OPTIMALITY TIGHTENING WITH N-STEP RETURNS
He et al. (2016) 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. Their work is more general than the value target low bounding methods due to 1) including a value upper bound as well as lower bound, and 2) using bootstrapping, so it's applicable to non-episodic tasks as well.
Compared to value target lower bounding, several limitations exist.
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 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 0, and the lower bound may be high 2, then it's unclear which way the value function should go.
16

---

Under review as a conference paper at ICLR 2022
E-ER
B-RR (ue))
b-
-30
liniddo
-10
800
Awerge www.geetoacooo 223000 NaM
Avpape 53500k Reau
250
-20
650
150
100
50
0
00
0.2
0.4
0.8
0.8
3.0
1.2
-50
00
0.5
1.0
1.5
200
09
0.5
1.0
2.5
2.0
Encranmen Shepe
Grvernment Staps
Covestment Steps
(a) Atari Breakout
(b) FetchPush
(c) FetehPickAndPlace
Figure 9: Evaluated average return of value target lower bounding with discounted return (Ib-DR) vs SAC or DDPG, td-lambda and Retrace on Atari Breakout and episodic FetchEnv tasks. Solid curves the mean across five (for Atari) or three (others) seeds, and shaded areas are +/- one standard deviation.
3R (001)
B-BR (aun)) 6dsg
h-08 (aun))
lambda
kimidda
Wear Trarnn Varw
-10
Miai Traninn ko0u
-10
15
-22
10
0.4
04
Traning
(a) Atari Breakout
(b) FetchPush
(c) FetePPickA
Figure 10: 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.
will depend largely on the mixing weight between the two losses and whether initial values overestimate, which can be hard to tune in practice.
2) The prior work does not include any theoretical analysis and misses the limitation to only deter- ministic tasks. The lower and upper bounds are in fact not correct bounds, even on deterministic tasks, because of the use of bootstrapped values together with the empirical discounted return.
3) In order to compute the bootstrapped values, the value network needs to 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 limited (4) timesteps into the future, while Ib-DR can look all the way to the end of an episode with very little extra computation and storage.
We implemented the method (He et al. 2016) and integrated into our baselines. We ran on FetchPush and Atari Breakout, with hyperparameters number of time steps = 4 and the penalty coefficient
= 4, following the original paper.
We found that the prior method overestimates value lot due two reasons: a) taking over the n-step returns for n from to 4, and b) the use of the bootstrap value, causing the lower bound to be above what's actually achievable.
17

---

Under review as a conference paper at ICLR 2022
We also improved their method by lower bounding the Bellman value target with n-step return (with bootstrap) instead of imposing the constraint on the value function itself. But it still overestimates value and does not learn as quickly the baseline one-step DDPG SAC.
We also adjusted to much lower values, hoping to control overestimation and improve over the baseline. Even with very small lambda of le-7, it is still slower than DDPG baseline on FetchPush, likely because initial values are overestimates. On Atari Breakout, with small lambda of le-7, learns slightly faster than the SAC baseline but still way below the value target lower bounding method.
A.6 A STOCHASTIC EXAMPLE
Using empirical return directly as value lower bound can lead value overestimation, as shown in the stochastic MDP example below.
Assume state So always goes to Si, and S gets reward +2 50% of the times. Then v(S)) v(S, O. However, with lower bounding. for the lucky case with reward 2, the value target for So is 7 (2, (S = 2%, and for the unlucky case with reward -2, the value target for So is y max( 2, (St) yo(Si) O. On average, o(So) will be overestimated to be 7-
is worth noting that lower bounding the action value directly as done in SIL (Oh et al. 2018 will overestimate (S1) well, whereas lower bounding the value target will produce the correct (11). This is because the same trajectory is used to both produce the Bellman value target (+22 for S₁ and the lower bound (#:2 for Si) which will be exactly the same for given trajectory.
A.7 DOES LOWER BOUNDING WITH EMPIRICAL RETURN REQUIRE THE POLICY BE DETERMINISTIC?
The use of empirical return to lower bound the optimal value does not require the policy to be deterministic. It does require the policy class to include the optimal policy (deterministic when the task is deterministic) or some policy that's close to the optimal policy. Otherwise, empirical return could still overestimate the optimal value achievable by the policy class. For example, Q learning assumes that the policy class includes the optimal policy which is the greedy one (and is deterministic). Because of that, the behavior policy can be non-deterministic and suboptimal, and doesn't t affect the learned value to reach optimality (as long as the behavior covers enough of the state space).
A.8 POTENTIAL IMPROVEMENT
Note that the goal distance based return (Ib-GD) of Section 3.1.1 is very simple way of arriving at a reasonable lower bound with near zero additional computation. The bound could be made tighter. Typically, an La distance threshold is used to judge goal achievement, which will likely be satisfied a few time steps before exactly arriving at the hindsight goal. To compute such a tighter bound would require evaluating the reward function across the trajectories of experience using all possible hindsight goal states, and storing them the replay buffer, i.e. episode length squared more computation and more storage space. It may be worth doing when episodes short, or doing it only for a small number time steps into the future when e.g. rewards are non-nege non-negative.
18


Reviews:
[{"review_id": "qgQANIQyBd2", "reviewer": "Reviewer_MXsM", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "This approach is not novel compared to say [1,2] and does not provide any meaningful insight, theoretical or empirical, over these existing papers. \n- Theoretical results are obvious. It would be interesting if the authors could provide some theoretical results suggesting that this approach might be meaningfully better, such as faster convergence. Or discuss the case where rewards/environment is stochastic. \n- Empirical benefits seem limited. There is no analysis or ablation over possible hyperparameters, different bounds, etc. \n\nMinor:\n- Notation for Theorem 1 is unexplained.\n- Algorithm 1 is unnecessary. \n\nReferences:\n- [1] He, Frank S., et al. \"Learning to Play in a Day: Faster Deep Reinforcement Learning by Optimality Tightening.\" (2016).\n- [2] Tang, Yunhao. \"Self-imitation learning via generalized lower bound q-learning.\" (2020).", "summary_of_the_paper": "The authors use the online episodic return as a lower bound to the optimal value function and show that using this bound improves performance of deep RL baselines.", "summary_of_the_review": "This approach is not novel and does not provide any meaningful insight, theoretical or empirical, over existing papers. ", "strength_and_weaknesses": "", "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": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "owV2cEdnej", "reviewer": "Reviewer_cupU", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "### Strengths \n\n1. The paper presents a simple and interesting idea. Specifically, using a value function lower bound to modify the Bellman backup is intuitive and seems simple enough that future work could build on the idea effectively. Moreover, this idea is (to my knowledge) novel. \n2. The proof of the main theorem seems correct. This result gives at least a useful sanity check that the proposed algorithm is reasonable. \n3. The paper is in general clearly written. It does a good job of conveying a simple idea simply. \n\n### Weaknesses\n\n1. The paper provides no analysis proving or even clearly demonstrating faster convergence. The main motivation for the proposed algorithm is faster convergence. So, it would strengthen the paper greatly to prove this, even under some simplifying assumptions. For example, what conditions on the lower bound would yield provably faster convergence? It would even strengthen the paper to just offer some tabular examples that could be computed in closed form where the lower bound clearly improves convergence speed, but a more general proof would be even better. Also, perhaps some larger scale examples could be created where there still are clear and obvious benefits to the proposed approach.\n2. The proposed lower bounds cannot handle stochasticity in the environment. This limitation is clear in the paper, but it a substantial limitation. For the idea to be more broadly applicable, there would need to be a way to handle stochastic environments. \n3. This is a more minor point, but the algorithm as proposed in the paper only works with actor-critic algorithms that use SARSA-style value estimation. This is not made particularly clear in the paper, but is an important point since it causes the authors to use SAC instead of a DQN-based algorithm on Atari, which is non-standard. However, I don't immediately see why there is not a way to make the algorithm work with max-Q backups as in DQN. Perhaps the authors can comment on whether the algorithm can be made to work with a DQN-style base algorithm?\n4. There are a few weaknesses with the experiments:\n   1. The improvement of the proposed method over the baseline is just not very clear in most of the experiments. Often there is no noticeable difference except in the fetch pick-place task and pioneer push-react task. In Breakout the proposed method actually seems to learn slower initially, which seems to run counter to the motivation for the method.\n   2. The value of $ \\alpha $ seems to be a bit strange and needs some explanation. First, unless I missed something, the paper only lists the value of $ \\alpha $ for the Atari games where it was 0.0005. What value was used in the other tasks? Second, if the value for $ \\alpha $ is so small, it is not clear that the proposed algorithm is making a substantial difference at all. Why is such a small value used? Is the algorithm very unstable for larger values?\n   3. In Figure 3 the values on the y-axis should be multiplied by 100 if the results are reporting percentages. Otherwise they should be labeled as the \"fraction\" of experience instead of percentage.\n5. This is a more minor thought, but I am somewhat worried that the proposed approach could cause some instability in learning and this might explain why the experimental results are not so strong. Specifically, it is well established that overestimation of the value function is often a problem (and motivated Double DQN as well as TD3). By introducing the lower bound, this problem is potentially exacerbated since the new algorithm can only increase the values being backed up. So while this may seem to learn faster, it could also increase the instability. This also may be related to why such small values of $ \\alpha$ are needed. Can the authors comment on whether they observe overestimation when using their method?", "summary_of_the_paper": "This paper proposed value target lower bounding as a simple modification to the Bellman operator that intends to improve convergence speed. It proves that using such a lower bound in the Bellman backup does not change the fixed point in the tabular setting. The paper then proposes two instantiations of particular value target lower bounds: first by using the return in deterministic episodic MDPs and second by hindsight relabeling in goal-directed tasks. Finally, the paper offers some experiments using the proposed lower bounds. ", "summary_of_the_review": "Overall, I like the idea of the value function lower bound, but don't think the paper is ready for publication yet. The paper could benefit from some tighter analysis and better examples showing the benefit of the algorithm. Moreover, the current experimental results are not quite convincing as explained above. ", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "cF4yQMdu3Ja", "reviewer": "Reviewer_hHjM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "Replacing my previous review which clearly was a misunderstanding on my end.\n\n----\n\nThe work proposes a low bound on the value by considering the current sampled return. In deterministic domains this provides a lower bound on the optimal value function v^*. Under the correct assumptions this scheme can be shown to converge.\n\nI think the work is interesting and the results are nice. Experiments themselves can be improved but are sufficient.\n\nMain limitation is deterministic MDPs -- the world isn't deterministic and almost no task is. Randomness may be small but it is not non-existent.", "summary_of_the_paper": "This work proposes to improve learning rate by lower-bounding the critic using observed trajectories.\nTheoretically, in deterministic domains, such a scheme should improve learning rate as it grounds the value towards realistic regions.", "summary_of_the_review": "Interesting work which can be of interest to the general RL community and lead to follow up research.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JWtjsbKVgdi", "reviewer": "Reviewer_e2TJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "**Significance**: The question of how to combing Monte Carlo return estimates with value functions is quite important to the design of good RL algorithms. While prior work has proposed a number of methods for doing this (e.g., TD($\\lambda$), Retrace, n-step returns), the proposed method has been relatively under-explored (though, see [1]). However, this paper does not compare to these alternative methods, so it is unclear if the proposed method is better than these prior methods. Moreoever, while the proposed method only is guaranteed to work well in deterministic environments, prior work has shown that these alternative approaches do work well in stochastic environments. I'd highly recommend that the paper be revised to include a comparison against TD($\\lambda$), Retrace and n-step returns.\n\n**Originality**: The proposed method is similar to [1]. I would recommend that the paper be revised to discuss and compare to this prior work.\n\n**Clarity**: The paper is generally clear. I'd recommend reorganizing the sections as follows: Introduction, Related Work, Background, Lower Bound, Algorithm, Results.\n\n**Correctness**: All claims seem correct. While the paper notes that the proposed method isn't guaranteed to perform well in stochastic environments, I would recommend emphasizing this claim. For example, here's a toy example that could be included to illustrate this issue:\n> Assume a bandit problem with 2 actions, one of which gets reward 1 and the other gets reward $\\pm2$. While the correct action is the first action, I believe that the proposed method will end up selecting the second (incorrect) action.\n* Is it possible to provide a guarantee that the proposed method won't perform that much worse than the optimal policy on stochastic environments?\n* \"deterministic versions of the three games\" -- Is this the standard evaluation protocol? I was under the impression that prior work usually added some randomness.\n* The hyperparameter $\\alpha$ is set to $0.0005 \\approx 0$ for the Atari results. Since $\\alpha = 0$ corresponds to the baseline, I am a bit concerned that the difference between the baseline is just random fluctuations (perhaps caused by trying multiple hyperparameters for the proposed method without correcting for the multiple testing problem).\n\n**Minor comments**:\n\n* \"Temporal Difference\" -> \"temporal difference\"\n* The introduction lacks structure. I'd recommend making sure that each paragraph is intended to explain a single idea.\n* \"seems to converge ... \"seems straightforward\" -- The use of \"seems\" makes these statements appear informal. \n* Sec. 2.2 -- I like that the general idea of value target lower bounding is introduced before the complete method.\n* \"at least as fast ... because it's more likely...\" -- Clarify whether these are theoretical or empirical claims.\n* \"which we encourage you, the reader, to come up with\" -- Avoid the use of the second person (\"you\") in formal technical writing. Perhaps: \"future work may investigate alternative lower bounds.\"\n* \"The FetchEnv tasks\" -- Add a citation.\n* Most of the details in Sec. 5.3.1 can be moved to the appendix. I'd recommend shortening this section to ~5 lines.\n* The future work discussed in the conclusion is great!\n* A.1 -- The math at the end of the proof is so terse that it is very hard to parse.\n\n\n[1] He, Frank S., et al. \"Learning to play in a day: Faster deep reinforcement learning by optimality tightening.\" arXiv preprint arXiv:1611.01606 (2016).", "summary_of_the_paper": "This paper proposes a new RL algorithm based on a modified Bellman backup equation. The main idea is to estimate the value of a state in multiple ways (using a Q function and using Monte Carlo returns) and then to take the maximum over these estimates. The paper shows that, if all estimators are lower bounds on the true value, then the proposed method converges to the optimal policy. Experiments confirm that the proposed method outperforms standard Q learning (i.e., with regular Bellman backups) on some tasks.", "summary_of_the_review": "This paper is studying an important problem, but is missing a discussion and comparison to a number of prior works. I therefore am voting to reject the paper.\n\n-------------------------\nUpdates during/after review period:\n* 11/23: Increasing score 3 -> 5 after new experiments showed that the proposed method outperforms other value estimation techniques.\n* 11/24: Increasing score 5 -> 6 after clarification of difference with (He 2016).", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In the end, this paper essentially proposes a minor variation on an idea that 1) has been published before, 2) is not used extensively at all, and 3) seems applicable (in its current form) only on deterministic environments.  This, without additional insights or analyses, seems too marginal a contribution for acceptance.

The paper is not poorly executed, and the authors engaged well during discussion, for which I would like to thank them.  I would like to encourage the authors to consider the reviewers comments, and in particularly perhaps answer more clearly and directly what they are adding to the literature.  It could be that there is something particularly insightful in the detailed differences with past work, but this has not become sufficiently clear to me during this discussion phase.
Decision: Reject