Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: The paper presents experimental results on the application of the gradient ARSM estimator of Yin et al. (2019) to challenging structured prediction problems (neural program synthesis and image captioning). The authors also propose two variants, ASR-K which is the ARS estimator computed on a random sample of K (among V) labels, as well as a binary tree version in which the V values are encoded as a path in a binary tree of depth O(log(V)), effectively increasing the length of sequences to be predicted but reducing the action space at each tilmestep.

The paper is self-contained and clear. The main value of the paper is to present good experimental results on challenging tasks; the ARS-K variant, although fairly straightforward, seems to be a reasonable implementation of the ARS(M) estimator.

My main criticism on the paper is that the exact nature of the contribution is not properly stated. As far as I understand, the main value of the paper is to demonstrate the effectiveness of ASR-K/M on challenging tasks. In a first read however, it seems that the authors claim an algorithmic/theoretical contribution compared to the state-of-the-art. Comparing with the paper by Yin et al. (2019), it seems to me that the technical contribution is rather incremental (the binary tree version is a variant of the hierarchical softmax, and ASR-K seems very straightforward), up to the point that the first set of experiments is actually only about vanilla ARSM.

other comments:
- what is j in Eq 4?
- RL_beam vs ASRM on neural program synthesis: the authors say that "RL_beam overfits [...] because of biased gradients", whereas "ASRM converges to a local minimum that generalizes better". I do not see why biased gradients would help fitting the data (compared to unbiased gradients). And as far as I understood, ASRM is about getting a better gradient (hence better optimization, and hence better fitting of the data), so I really do not understand this argument.

- RL_beam vs ASRM on NPS: I do not see why ASRM cannot fit the data as well as RL_beam. Is there some regularization involved? 

minor:
- "expected award" (first line section 3.1)

------ after author rebuttal

The authors answered my main concerns, I raises my score to weak accept.
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: The paper presents a novel reinforcement learning-based algorithm for contextual sequence generation. The algorithm builds on the previously proposed MIXER algorithm and improves it by integrating gradient estimates with lower variance (augment-REINFORCE-swap-merge). To further improve the runtime complexity of the proposed algorithm, binary tree-based hierarchical softmax is applied. The algorithm is evaluated on the Karel dataset for neural program synthesis and the MS COCO dataset for image captioning.

The presentation of the paper must be improved (my score assumes that this will have been done). It is nice to have the detailed derivations when trying to dive deeper into the problem, but it hinders understanding of the main concepts at the first reading. Therefore, I would highly recommend to move most of the formulas to the appendix and keep instead only key ideas with intuitive explanations. It would also free some space in the main paper for the experiments from the appendix.

Several questions on the technical side:
1. Is there any intuition why pseudo actions tend to be equal to the true one when learning progresses? What causes this? Might it enforce any structure (like uniform)?
2. When all pseudo actions are the same, the gradient is zero. In theory, zero gradient of a function corresponds to its extremum. Does it mean that when all pseudo actions are the same, an extremum is reached or is it just an artifact of this particular estimator? Can one prove any results of this kind?
3. I understand that the ARSM estimator should be unbiased for V = 2. Does the estimator remain unbiased when V > 2?
4. In the experiments, the variance is shown to reduce significantly which is nice. However, in theory, does the ARMS guarantee non-increasing variance or can it potentially go up in some cases? If it can, have it ever been observed in practice?
5. How does the runtime of the proposed algorithm compare to the competitors?

Experiments:
1. Bunel et al (2018) report higher generalization on the Karel dataset. Is the difference due to the removal of the optional grammar checker? Can the same experiments be performed with this checker on or are there any constraints of the ARSM-based method?
2. The submitted code for the NPS experiment is actually the one by Bunel et al with their comments. I could not find any instructions or scripts reproducing the results of this paper (and I didn’t have much time to figure that out). One thing I wanted to check in the code is how the variance was computed for the plots?

Minor:
1. p. 4, “expected award” >> “expected reward”
2. g_{ARSM} defined twice in (5) and in the beginning of p. 4
3. “Fig. 1 (left two) plots” and “Fig. 1 (right two) plots” not good


review_title: Official Blind Review #3

final_score: rating: 8: Accept
review_content: The authors propose a new algorithm for unbiased stochastic gradient estimation for use in reinforcement learning of sequence generation tasks (specifically neural program synthesis and image captioning). The method consists in performing correlated Monte Carlo rollouts starting from each token in the generated sequence, and using the multiple rollouts to reduce gradient variance. An interesting property of the proposed algorithm is that the number of rollouts automatically scales with the uncertainty of the policy.

The proposed algorithm is novel, and the results are promising. Implementation of the idea seems non-trivial, but the authors provide open source code. The proposed algorithm could be impactful. The paper is clearly written.

Questions for the authors:
- Can you say anything about the optimality of scaling the number of rollouts with the policy uncertainty? Does the algorithm make optimal use of the number of rollouts? i.e. is the variance minimal for the number of rollouts, or is there scope for improvement?
- The number of rollouts being random possibly complicates efficient parallel evaluation of the rollouts (batch sizes are effectively varying). This is presumably not a problem for the chosen applications, but could you discuss the limitations in a broader setting?
review_title: Official Blind Review #2

Meta-review: The paper presents a novel reinforcement learning-based algorithm for contextual sequence generation. Specifically, the paper presents experimental results on the application of the gradient ARSM estimator of Yin et al. (2019) to challenging structured prediction problems (neural program synthesis and image captioning). The method consists in performing correlated Monte Carlo rollouts starting from each token in the generated sequence, and using the multiple rollouts to reduce gradient variance. Numerical experiments are presented with promising performance. 

Reviewers were in agreement that this is a non-trivial extension of previous work with broad potential application. Some concerns about better framing of contributions were mostly resolved during the author rebuttal phase. Therefore, the AC recommends publication. 
Decision: Accept (Poster)