Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This paper combines combines submodular surrogates for sequential decision making with imitation learning. Specifically, it proposes to learn an acquisition function g by imitating an expert which is assumed to be following a greedy policy wrt a general submodular surrogate f. This is accomplished by regularizing g to encourage diminishing returns and monotonicity. The learning algorithm is a modified version of DAgger which is consistent with the expert and provably near-optimal utility. Results outperform baselines on various sequential decision making tasks.


Novelty/Impact
- Elegant, novel combination of DAgger with submodular regularization
- Potentially impactful idea (comparison to additional baselines would confirm this)
- Theoretical contribution is a straightforward combination of (Ross, 2011) and (Golovin and Krause, 2011). On its own this is not very impactful

Experiments:
- Good, concise experiments across a range of applications. 
- The expert's utility function is shown to exhibit submodularity, strengthening the validity of the proposed approach
- Baselines are illustrative, but the paper would benefit from having additional baselines (for example [1-2] for active learning)

Clarity/Correctness:
- In the proof of Theorem 2, can you explain the first inequality when bounding the one-step gain of $\hat{\pi}$? What if $\pi^{exp}$ is not along the learned trajectory?
- Do the baselines in section 6.1 use Algorithm 1 (i.e. DAgger) with different loss functions?
- typo: "groundset" should be "ground set"

Pros
- Good organization
- Potentially high impact
- Thorough experimental methodology

Cons
- Some statements unclear
- Somewhat weak baselines
- Limited theoretical contribution

Questions:
- Is the bound in Theorem 2 tight?
- How does the algorithm perform when the surrogate is non-monotone?
- Is the poor performance on noisy set cover due to noisy data or submodularity being violated?


[1] Wei, Iyer, and Bilmes. Submodularity in Data Subset Selection and Active Learning, ICML 2015. http://proceedings.mlr.press/v37/wei15.html

[2] BADGE Ash et al. Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds, ICLR 2020. https://arxiv.org/abs/1906.03671


EDIT: The authors addressed my main concerns, fixed a crucial bug in the claim/proof of Theorem 2, and added many more clarifying details to a revised submission. Therefore I will keep my rating the same

review_title: Nice idea, but some questions

final_score: rating: 7: Good paper, accept
review_content: Authors propose to approximate the marginal gain of the submodular function (also called discrete derivative) with a neural network. The data for training the model is collected with DAgger, and therefore the proposed method inherits guarantees of DAgger.

Clarity: My main concern is that some of the important details are not discussed in the paper. Authors only mention that $g$, the marginal gain approximator, is a neural network; I couldn't find any discussions on what kind of neural network was used. Since the input of the neural network includes a power set, the input representation of the data as well as the neural network architecture would be of interest. Also, the description of protein engineering experiment is a bit confusing. It mentions that the expert is trained on a downstream regression task, but it is also mentioned that 'LeaSure is trained to emulate a greedy oracle for maximizing the stability of protein G', which is inconsistent. Even in the Appendix C, details on the experiments such as the description of parameters or the pseudocode of the algorithm are deferred to references.

Quality: The main claim of the paper is that the cost of evaluating the expert policy can be reduced by approximating it as a neural network. However, there are many factors contributing the cost of employing the proposed method, as a potentially large neural network would need to be trained, and data points for training the network should be acquired. A larger neural network would make it more expensive to evaluate $g$, diminishing the value of approximating the expert. Also, a larger neural network may be less sample-efficient. It would be interesting to discuss how these other cost factors should be considered in order to optimize the total cost. 

Originality, Significance: The idea of approximating the marginal gain with a neural network seems new, and also broadly applicable across applications of submodular optimization.

Pros:
* The idea is original and creative
* The proposed method is widely applicable

Cons:
* The practical utility is quite uncertain and questionable
* The paper lacks important details, even the architecture of neural networks used

---

In the revision, authors provided detailed clarifications on their approach and practical utility of the proposed method. Therefore, I am changing the rating of my review.
review_title: Potentially useful idea, but the paper is lacking details

final_score: rating: 6: Marginally above acceptance threshold
review_content: 1. Summary of the paper contributions
    (1) This paper proposes a 'submodular-norm' based regularization term when learning a score function based on data-driven optimization, which encourages the underlying utility function to exhibit "diminishing return". The learned scoring function can be used as a greedy heuristic in combinatorial sequential decision making tasks, in which expert policy is expensive to evaluate.
    (2) The proposed approach can be easily integrated with other imitation learning pipelines when the considered problems fall into the (approximate) submodular set. This is shown in the experiment section by examples including set cover, learning active learning,  and learning to imitate expert design in protein engineering.

2. Strong and weak points of the paper
    (1) Strong points: The considered problem is interesting and meaningful. This paper provides a new 'submodular-norm' when learning the scoring function, which seems to be effective in the shown examples. Since the proposed algorithm is a specialization of  the DAgger algorithm (Ross et al., 2011), the performance guarantee for the learned scoring function is established.
    (2) Weak points: Although the proposed algorithm can achieve the desired performance guarantees in Theorem 1 and 2, these results are a natural extension (or direct result) of prior work Ross et al., 2011. The proposed 'submodular-norm' seems to be effective in the shown 3 examples, but many details are omitted. This makes it hard to tell the proposed algorithm's effectiveness and efficiency in practice.

3. My recommendation
    I tend to reject this paper, but am open to change my score after rebuttal. My main concern is on the experiment part, which lack many details and baseline methods. 

4. Supporting arguments for your recommendation
    The paper's theoretical results are a natural extension or direct result of prior work, so I focus more on the empirical performance part such as whether the propose algorithm is efficient to train and the effectiveness compared to baseline methods. Although the results shown in the paper seem to be effective, many details and baseline methods are not shown. Also, the second example of learning active learning policy seems to be not very efficient. Because it needs a (noisy) expert scoring function value for every evaluated data point. This 'expert' scoring function is trained for every data point encountered in training. Although it uses only 10 epochs to obtain this value, it is still very time-consuming considering the rollout length and the total number of rounds.

5. Questions
    (1) For the m shown in Theorem 1, is it the T in Algorithm 1 step 7?
    (2) What does the k stand for in Theorem 2?
    (3) For the 3 examples, can the author/s provide details on how the labeled tuples are generated? Is it by following Algorithm 1? If so, what's the \beta and N values for these examples?
    (4) For set cover example, the compared DSF generalizes better to larger rollout lengths as shown in Fig. 1. Does it mean the DSF may achieve the total of 119 species with least number of rollout sets in the superset? Any result in this metric?
    (5) For the 3 examples, the estimated scoring function g is parametrized by neural network. Can the author/s provide details on how the parametrization is constructed? 
    (6) Why does the author/s not include other imitation learning methods as baseline like Liu et al., 2018 discussed in Section 2?
    (7) How to determine the regularization parameters \lambda and \gamma? For other compared methods, did the author/s tune their hyper-parameters?
    (8) The 'no regularizer' policy in Fig. 2 is adapted from Konyushkova et al., 2017 without hand-engineered features. Will this lower the method of Konyushkova et al., 2017's performance in general?
review_title: Needs more details on experiments

Meta-review: This paper considers the problem of sequential decision making through the lens of submodular maximization. I read the paper myself and found the idea quite appealing and interesting. The authors also make a very effective rebuttal and brought a borderline paper into a clear accept. 
Decision: Accept (Poster)