Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: ===== Summary =====
The paper proposes an extension of multi-step dynamic programming algorithms from Efroni, Dalal, Scherrer, and Mannor (2018a, 2018b) to the reinforcement learning setting with function approximation. The multi-step dynamic programming algorithms proposed by Efroni et. al. (2018a)  find the solution of the h-step optimal Bellman operator, which applies the maximum over the next h sequence of actions. Moreover, Efroni et. al. (2018a) also showed an equivalence between h-step optimal Bellman operators and k-Policy Iteration (k-PI) and k-Value Iteration (k-VI) algorithms, which, similar to TD( 𝜆 ) but for policy improvement, take a geometric average of all future h-step returns weighted by k. The paper extends the work from Efroni et. al. (2018a, 2018b) to the deep reinforcement learning setting by proposing an approximate k-PI and k-VI algorithm based on DQN and TRPO. Finally, the paper provides empirical evaluations of k-PI and k-VI with DQN in several Atari games and of k-PI and k-VI with TRPO in several MuJoCo environments with continuous actions paces. 

Contributions:
1. The paper proposes a non-trivial extension for k-PI and k-VI to use function approximation via the DQN algorithm. 
2. Similarly, the paper proposes a non-trivial extension for k-PI and k-VI to use function approximation with continuous action spaces via the TRPO algorithm. 
3. The paper provides empirical evaluations of the four proposed algorithms and, at least for the k-PI algorithm with DQN and TRPO, demonstrates an improvement over the baselines. 

===== Decision =====
The paper represents a natural next step to the work of Efroni et. al. (2018a, 2018b). The paper extends the applicability of multi-step greedy policies to more complex environments and shows a statistically significant improvement in performance compared to the methods that it builds upon. Additionally, the ideas are presented clearly and incrementally throughout the paper, which makes it flow nicely until the part where k-PI and k-VI DQN and TRPO are introduced. This is my main complaint about the paper, the lack of simple and intuitive understanding about k-PI and k-VI with function approximation due to the complicated architectures associated with DQN and TRPO. For this reason, my rating of the paper is weak accept.

===== Detailed Comments about Decision =====
All of these are comments for which I would consider increasing my score if they were addressed. 

=== Empirical Evaluations ===
First, my main complaint is the complicated architectures and complex domains used to gain insights about k-PI and k-VI with function approximation. Big demonstrations in Atari and MuJoCo are important, but in the case of very new algorithms such as these ones, I consider it to be more important to gain insight through small domains that allow us to dig deep into the algorithms. Any small domain that would allow for big sample sizes for ablation and parameter studies would be more insightful than big demonstrations with very small sample sizes. I do not mean to be dismissive about what has been done in the paper, but it would be a great source of insight and a big improvement to what has already been done if a simple demonstration was presented in the paper. 

My suggestion would be to use a simple approximation method, such as Tile Coding with linear function approximation, in small a domain such as mountain car. This would allow for a bigger sample size and a parameter study that could provide more insight about the role of the parameters k and C_{FA} on the performance of k-PI and k-VI. 

Additionally, one of the claims in the conclusions was never emphasized in the results: “importantly, the performance of the algorithms was shown to be ‘smooth’  in the parameter k.” This was not completely obvious until I spent some time looking closely at the graph. It eventually became clear, but I think a simpler way to emphasize this is to show a plot of the cumulative reward over the whole training period with the values of k on the x-axis. Based on the top right pane of FIgure 1, this type of plot would show a smooth increase from k=0.99 to k=0.68 followed by a smooth decrease from k=0.68 to k=0. 

Finally, I have some questions about some of the choices made in the experiments and results sections:

1. Why choose 50% confidence intervals? 50% confidence intervals with a sample size of 4 in the case of DQN and 5 in the case of TRPO is equivalent to multiplying the standard error by a factor of approximately 0.7, which is narrower than using the standard error on its own. Thus, it seems that some of the conclusions would change based on using a 95% confidence interval compared to a 50% confidence interval in Tables 1 and 2. I insist in showing the performance in a small domain with a simple form of function approximation. This would complement the Atari and MuJoCo experiments by showing improvements in performance with a higher confidence. 

2. In remark one, it is pointed out that another target network \tilde Q should be used to obtain \pi_{t-1}, but this was not done to reduce the space complexity of the algorithm. How big were the networks that you used for k-PI DQN? If the network was not prohibitively big, why not implement \tilde Q instead of using an alternative that further deviates from the original k-PI algorithm? 

3. Line 19 of Algorithm 5 in Appendix A.1 is supposed to be the off-policy TD(0) update. However, it is not clear how this update is off-policy TD(0) since it based on Q and it does not have any importance sampling to correct for the difference in policies. Am I missing something? It seems that it should be off-policy Sarsa(0), but even then it would still be missing an importance sampling term (see Sutton & Barto, 2018, Equation 7.11, or Algorithm 1 of Precup, Sutton, and Singh, 2000, for more information).

=== Contradictory Claims in the Results ===
There are a few claims that contradict with what is shown in Table 1 and 2.

In the last paragraph of Section 5.1.1 it says that “[the table 1] show[s] that setting N(k) = T leads to a clear degradation of the final training performance on all the domains except Enduro.” This is only true in two out of four games presented in Table 1. In Seaquest the lower confidence bound of the performance of k-PI with k=0.68 is 4643, whereas the upper confidence bound of the performance of k-PI with N(k) = T is 4837; the intervals clearly overlap. Similarly, in the game of Enduro, where k-PI with N(k) = T is said to have better performance, the lower confidence bound of k-PI with N(k) =T is 530, whereas for k-PI with k=0.84 the upper confidence bound is 575; again, the confidence intervals overlap. Hence, neither of these two claims are fully justified, and it is certainly not a “clear degradation of the final training performance.”

Similarly, in Section 5.2.2, k-PI is said to have a better performance than N(k) = T based on the results of Table 2. However, similar calculations show that this is only true for the Ant domain.

===== Minor Comments =====
1. I believe there is a typo in the last column of Table 1, it should be a \kappa instead of a 𝜆.

2. In the second paragraph above Equation 7, the convergence of PI and VI are said to converge to the optimal value with linear rate, but the rate of convergence is O( \gamma^N ), i.e., exponential. Similarly, for the k-PI and k-VI their rate of convergence is O( \ksi ( \kappa )^{N( \kappa )} ), which is also exponential. 

===== References =====
Precup, Doina; Sutton, Richard S.; and Singh, Satinder, "Eligibility Traces for Off-Policy Policy Evaluation" (2000).ICML '00 Proceedings of the Seventeenth International Conference on Machine Learning. 80.Retrieved fromhttps://scholarworks.umass.edu/cs_faculty_pubs/80

R. Sutton and A. Barto. Reinforcement learning: An introduction. 2018.

Y. Efroni, G. Dalal, B. Scherrer, and S. Mannor. Beyond the one step greedy approach in reinforcement learning. In Proceedings of the 35th International Conference on Machine Learning, 2018a.

Y. Efroni, G. Dalal, B. Scherrer, and S. Mannor. Multiple-step greedy policies in approximate and online reinforcement learning. In Advances in Neural Information Processing Systems, pp. 5238–5247, 2018b.

review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: The main contributions of this paper are k-PI-DQN and k-VI-DQN, which are model-free versions of dynamic programming (DP) methods k-PI and k-VI from another paper (Efroni et al., 2018).  The deep architecture of the two algorithms follows that of DQN.  Efroni et al. (2018b) already gave a stochastic online (model-free) version of k-PI in the tabular setting.  Although this paper is going one step further extending from tabular to function approximation, I feel that the paper just combined known results, the shaped reward from Efroni et al (2018a) and DQN.  The extension seems straightforward.  Mentioning previous results from Efroni et al (2018a) and (2018b) does not justify the extension would possess the same property or behaviour.   The experiments were only comparing their methods with different hyperparameters, with only a brief comparison to DQN.  
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: This paper focuses on the implementation and some empirical evaluations of a class of algorithms designed to find optimal strategies/values of large MDP.

The basic idea of these algorithm (called \kappa-PI or \kappa-VI) is to combine two type of classical approaches:
- policy/value iteration 
- k-step ahead computation (instead of just 1-ahead, and actually, k should be quite big or even infinite with an auxiliary appropriate discount rate).

The theoretical formulation of \kappa-PI and \kappa-VI involves solving, at each iteration, another auxiliary MDP problem (where the discount rate is of order \kappa\gamma). This is basically what this paper suggests to do, and implements. 

The experiments are a bit difficult for me to read, as the baselines (\kappa=0 and =1, say) are compared with "the best \kappa" which seems to be problem dependent, so I do not know if there is a clear message.
review_title: Official Blind Review #1

Meta-review: This paper extends recent multi-step dynamic programming algorithms to reinforcement learning with function approximation.  In particular, the paper extends h-step optimal Bellman operators (and associated k-PI and k-VI algorithms) to deep reinforcement learning.  The paper describes new extensions to DQN and TRPO algorithms.  This approach is claimed to reduce the instability of model-free algorithms, and the approach is tested on Atari and Mujoco domains. 

The reviewers noticed several limitations of the work.  The reviewers found little theoretical contribution in this work and they were unsatisfied with the empirical contributions.  The reviewers were unconvinced of the strength and clarity of the empirical results with the Atari and Mujoco domains along with the deep learning network architectures.  The reviewers suggested that simpler domains with a simpler function approximation scheme could enable more through experiments and more conclusive results.  The claim in the abstract of addressing the instabilities was also not adequately studied in the paper.

This paper is not ready for publication.  The primary contribution of this work is the empirical evaluation, and the evaluation is not sufficiently clear for the reviewers.
Decision: Reject