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?
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.
3. Recommendation My current assessment is that the paper is marginally below the acceptance threshold.