Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper aims at devising a targeted approach that takes into account the specific structure of combinatorial problems with multiple solutions. The proposed approach leverages RL to select the best targets among the solution sets at each iteration. SelectR convincingly outperforms both the naive and a cleverer baseline, showcasing the applicability of the method.

Originality
The problem of interest is relevant to a number of machine learning applications but has largely been ignored by the community up until now, as is made clear in the very complete related works section of the paper. Notably, the question of selecting the best target for learning is, as far as I am aware, novel. Consequently, so is both the approach and the baselines it is compared against.

Significance
As ML practitioners try their hand at more and more complex problems, this approach will become more and more relevant. 
Further, since this paper is the first to define the one-of-many problem, sets out to define the general framework, and defines reasonable baseline, it is very relevant.
The effort made to link the problem of interest with existing other problems mean that it's easier for readers to draw parallels, and helps bolster the paper's significance. For instance, the experimental results tend to show that naively using multiple possible solutions is worse than ignoring these data points. This is in direct contradiction with the general consensus for tasks such as machine translation, where multi-solution datasets are not available, but are longed for.

Clarity
Overall, the paper is well-written and easy to follow. A couple of things might be made clearer, though, including:
- the description of the pretraining regimen, which is a bit convoluted. It would probably help to refer to the internal M for the selection module as a target network, which it seems to be.
- the description of the reward for the selection module is a bit complicated too, and the the fact that solutions can be split into r components could be reminded here.
It would also be helpful to give more insight into why this reward was chosen (I imagine this partial-reward makes it easier to 'see' some reward than a reward for exact matching, but I'm speculating here), and what the consequences of this choice are (aside from improved performance). Does the selection module opt for the 'easiest' targets to predict? Do the targets chance as training goes along? Could the selection module be trained at a meta-level rather than at the transition-level?


Overall, this is a nicely-written paper offering a novel approach to a significant problem, and showcasing its performance improvements. It would make a nice addition to this year's ICLR.
review_title: Convincing new learning approach for multiple-solution combinatorial problems

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:

The authors work in the domain of applying neural networks to combinatorial problems with structured output space, such as sudoku and n-queens. They notice how models currently performing well at this task encounter difficulties when there are multiple possible solutions. They formalize the task of learning any of multiple given (and possibly quite different) labels and propose an RL based approach to solve that task. They show improvements over selected baselines. 

Great:
* The discussion of why the task is different from other instances of multiple labels is well argued and clear.
* Numerical examples are very helpful in following the description of the algorithms.
* The evaluation setting is well thought of: utilizing the state of the art model and comparing it to reasonable baselines (one of which is indeed current SoTA). The experiments seem reproducible, given the detailed descriptions in the appendix.


Could be improved:
* Table 2 is perhaps misleading. Table 3 with the same results with standard deviation gives a less clear answer on whether SelectR is actually always better than MinLoss (careful with significant digits, the standard deviation can’t have more than one!).
* The experiment depicted in figure 2 isn’t discussed, it doesn’t report confidence intervals, the distribution of training samples is not discussed (are there significantly less training examples with 50+ solutions, that could justify the drop in performance? A sudoku with this many solutions is likely to be quite sparse, does that affect performance?).


In summary, the paper introduces and formalizes an interesting novel task in the context of combinatorial problems with structured output space. While aspects in the evaluation could be clarified, the paper is clear and interesting. I recommend an accept, and would be willing to increase the score if my concerns are addressed.

review_title: Interesting novel task, some concerns to address in the evaluation.

final_score: rating: 5: Marginally below acceptance threshold
review_content: The quality and clarity of the paper is good overall. In my opinion the presentation is clear, the goal of the work, and the proposed solutions are presented cleanly. Authors give a few examples of the issues raised by learning from many correct solutions, which is appreciated.

In terms of significance. I believe the theory is not surprising at all, it is straightforward to see that eq.(1) will not be a consistent loss function for generalization. Now, in Lemma 2, given the definition of eq.(2), it is also not surprising to see that it is a consistent estimator, and in fact, the proofs are rather trivial. Thus, from the theoretical viewpoint these issues undermine the paper.
From the practical viewpoint, authors show that their proposed method SelectRL is better than other baselines, and my main concern in the practicality of the algorithm is that I don't see a strong case where SelectRL is significantly better than MinLoss, at least not statistically. Thus, my question here is, can authors claim that SelectRL is better than MinLoss from the experiments? If so, the gain seems small, and computationally speaking training an RL agent to select a solution seems an overkill.

Another question is: in the Random baseline, was the solution being picked uniformly at random? If so, wouldn't a distribution that is concentrated around a solution be better? I would've liked to see this in the experiments. If authors can comment on this question would be appreciated.
review_title: Contributions are borderline from first review

final_score: rating: 5: Marginally below acceptance threshold
review_content: 
	1. Summary & contributions
This paper formalizes the 'one-of-many-learning' problem and proposes a method for solving this problem.

The paper first defines the one-of-many-learning problem, where a model must learn to map an input x to one of many possible targets y, where all possible y or only a subset may be given, in particular in a combinatorial setting. The paper explains failures of naïve approaches such as summing the loss over all possible y or only taking into account the y which has the lowest loss for the current model.

The paper then introduces the 'SelectR' framework where a separate neural network model (the selection module) is trained to predict which of the targets should be used for training the main model. The models are trained jointly using RL, where the selection module is trained to match the prediction of the main model and the main model minimizes the loss on the target selected by the selection module.

The authors demonstrate improved results compared to different (relatively simple) baselines in three different constraint satisfaction problems: N-Queens, Futoshiki and Sudoku.

	2. Strengths & weaknesses
This paper addresses an interesting problem which is well motivated, well defined and clearly and extensively related to other problem settings from the literature. The paper explains the problem clearly and gives good examples of failure modes of naïve approaches, motivating an alternate approach.

The paper shows that indeed performance improvements can be achieved by using such an alternate approach which explicitly considers the one-of-many-learning problem, by training a selection module to select the target used for training dynamically, in a joint fashion using RL.

The main weakness of the paper is that the specific proposed solution/framework (training a selection module using RL) is in my opinion not well motivated. The motivating problem (with the naïve MinLoss strategy) seems to be (lack of) exploration: can't this be addressed simply by adding some randomness (e.g. sampling target proportional to loss or model probability). Why is a separate neural network module needed?

Also, I do not understand the reward structure (# predicted variables equal to main model). It seems that the selection module is trained to basically match the prediction of the main model, and the paper states that this is 'since we do not know a-priori which y is optimal for defining the loss'. How does training a separate model to match the main model prediction help overcome this problem?

While the results do show the benefit of the 'SelectR' framework, I would like to see them compared to a simple (informed) strategy such as sampling a target according to model probability / loss / MinLoss with some epsilon probability of using a random target. The results may help in answering above questions.

Although I like the writing in general, I think the paper uses too much math notation and formalism. For example, the concepts of MinLoss and SelectR are relatively simple, but the notation in terms of one-hot w_ij makes things unnecessarily hard(er) to read and complicated. I think also the Lemma's and examples would be better explained with words than with heavy math, to help understanding. As a bonus, removing a lot of the math would allow for very helpful Algorithm 1 and maybe Figure 3 of the Appendix to be included in the main text.

	3. Recommendation
My current assessment is that the paper is marginally below the acceptance threshold.

	4. Arguments for recommendation
The paper addresses a well motivated and well explained problem and the results obtained using SelectR improve over the baselines, but it does not convince (enough) that such a (relatively complicated) approach is actually beneficial from a practical point of view as simpler alternatives are underexplored (see strengths & weaknesses). Additionally, I think the paper should use less formal notation as that will make the paper easier to read without losing the content.

	5. Questions to authors
See also strengths & weaknesses
- Do I understand correctly (from the formula for the cross entropy loss function) that Example 1 assumes a model which predicts y_1 and y_2 independently? I can imagine an autoregressive (structured) model which has p(y_1 = 1) = 0.5 and p(y_2 = 1|y1=1) = 0 and p(y_2 = 1|y_1 = 0) = 1 so p(1,0)=p(0,1)=0.5, which is optimal. It seems to me that the problem arises because of the independence structure of the variables in the model combined with the loss function (i.e. summing the log-probs for all targets).
- Why does Lemma 1, which is posed as a formalization of the problem arising in Example 1, consider a zero-one loss whereas Example 1 is based on a cross-entropy loss? This is confusing to me.
- The paper repeatedly mentions a 'prediction y^hat' as output of the main model. How is this defined? The model outputs a (structured) probability distribution but y^hat seems a vector. Is this vector a sample/argmax solution?


	6. Additional feedback

Minor comments/suggestions:
- The paper claims that compared to Neural Program Synthesis (NPS), where a generated program can be verified, in the setting considered in the paper there is no such additional signal available. However, the experiments all consist of problems where a solution can be  verified easily, even if it is outside the target set, so this does seem similar to NPS.
- It seems that forcing all probability mass to concentrate on one target can be helpful for some models (i.e. Example 1 if we assume independence of the variables), but may also be (unnecessarily) restrictive for other models which could more easily divide the probability mass. Maybe this would be interesting to discuss/investigate.
- The paper notes that 'one could also backpropagate the gradient of the expected loss given Pr(y_ij)'. This seems preferred to sampling, so a bit more discussion on why this was or was not used would be interesting.
- I would not consider the parameters of the main model as 'input' for the selection module. I would just say it takes as input the prediction from the main model.

review_title: Paper defines interesting problem but motivation for RL based method could be improved

Meta-review: The reviewers are enthusiastic about this work, and the few comments that they had were appropriately addressed by the reviewers.
Decision: Accept (Poster)