Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
main_review: ### Strengths 

1. 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. 
2. The proof of the main theorem seems correct. This result gives at least a useful sanity check that the proposed algorithm is reasonable. 
3. The paper is in general clearly written. It does a good job of conveying a simple idea simply. 

### Weaknesses

1. 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.
2. 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. 
3. 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?
4. There are a few weaknesses with the experiments:
   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.
   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?
   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.
5. 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_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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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.

**Originality**: The proposed method is similar to [1]. I would recommend that the paper be revised to discuss and compare to this prior work.

**Clarity**: The paper is generally clear. I'd recommend reorganizing the sections as follows: Introduction, Related Work, Background, Lower Bound, Algorithm, Results.

**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:
> 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.
* Is it possible to provide a guarantee that the proposed method won't perform that much worse than the optimal policy on stochastic environments?
* "deterministic versions of the three games" -- Is this the standard evaluation protocol? I was under the impression that prior work usually added some randomness.
* 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).

**Minor comments**:

* "Temporal Difference" -> "temporal difference"
* The introduction lacks structure. I'd recommend making sure that each paragraph is intended to explain a single idea.
* "seems to converge ... "seems straightforward" -- The use of "seems" makes these statements appear informal. 
* Sec. 2.2 -- I like that the general idea of value target lower bounding is introduced before the complete method.
* "at least as fast ... because it's more likely..." -- Clarify whether these are theoretical or empirical claims.
* "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."
* "The FetchEnv tasks" -- Add a citation.
* Most of the details in Sec. 5.3.1 can be moved to the appendix. I'd recommend shortening this section to ~5 lines.
* The future work discussed in the conclusion is great!
* A.1 -- The math at the end of the proof is so terse that it is very hard to parse.


[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_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.

-------------------------
Updates during/after review period:
* 11/23: Increasing score 3 -> 5 after new experiments showed that the proposed method outperforms other value estimation techniques.
* 11/24: Increasing score 5 -> 6 after clarification of difference with (He 2016).
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
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. 
- 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. 
- Empirical benefits seem limited. There is no analysis or ablation over possible hyperparameters, different bounds, etc. 

Minor:
- Notation for Theorem 1 is unexplained.
- Algorithm 1 is unnecessary. 

References:
- [1] He, Frank S., et al. "Learning to Play in a Day: Faster Deep Reinforcement Learning by Optimality Tightening." (2016).
- [2] Tang, Yunhao. "Self-imitation learning via generalized lower bound q-learning." (2020).
summary_of_the_review: This approach is not novel and does not provide any meaningful insight, theoretical or empirical, over existing papers.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work proposes to improve learning rate by lower-bounding the critic using observed trajectories.
Theoretically, in deterministic domains, such a scheme should improve learning rate as it grounds the value towards realistic regions.
main_review: Replacing my previous review which clearly was a misunderstanding on my end.

----

The 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.

I think the work is interesting and the results are nice. Experiments themselves can be improved but are sufficient.

Main 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_review: Interesting work which can be of interest to the general RL community and lead to follow up research.
review_title: null

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