Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The authors contribute to the field of algorithmic recourse by considering how to train models such that recourse options will exist with high probability with theoretical guarantees. To do so, the authors use a method which incorporates an approach from the study of adversarial training and PAC confidence sets. 
main_review: Strengths:
1) Interesting research direction with potential real impact on the field of algorithmic recourse. 
2) Novel, as far as I can tell. 
3) Clearly written and motivated.

Weaknesses:
1) Since the paper uses a reversed version of a method that was originally introduced to reduce model brittleness, I'm not sure there was enough discussion of the effect of using such an approach on model robustness for which adversarial training was first suggested to begin with. While the authors do provide some empirical evidence in Table 3 that adding Gaussian noise did not make the models catastrophically fail. However, I think further discussion and perhaps additional results with more realistic noise additions/some examples of datasets from adversarial training literature could have made this point more convincing. 
2) I believe Wachter  et al. 2017, which is cited in this work, also included a discussion on the connection between adversarial training and counterfactuals/recourse. I'm not sure the authors acknowledged this enough (unless I missed it, happy to stand corrected).
3) Presentation and experimental section can be a bit improved, see suggestions below.


Minor comments:

1) Line 55-6 vs 57-8 -- don't they say the same thing in different words? Could you not drop one of them?
2) Line 63 -- it becomes clear later in the experimental section, but it might be helpful to readers to understand what you mean by "robust recourses". Robust how?
3) Section 3 might benefit from a summary of the 3 steps of the method in an algorithm(s) block(s).
4) Line ~153 -- might be good to quickly state $\Delta$ is constructed based on use case and domain knowledge/user specified?.
5) Line 175 -- "$g_\theta$ is approximately linear as a function of x" -- is this supposedly falsifiable from data? Is this a strong assumption in certain cases? Might help to discuss a bit more.
6) Line 197 -- "uses the PAC confidence... constructs the new...", should "constructs" be changed to "to"? Typo?
7) Eq. 4 -- extra closing bracket?
8) Table 1 -- Consider adding titles to the two bottom lines, it's a bit confusing as it stands.
9) Line 215, 222 -- cite the adult income dataset? and bail outcomes?
10) Fig 2. -- why are results from the German dataset not included for this analysis? + I might have missed this, but why would recourse neg be 0 *for any threshold* under $\lambda=0$? And for all datasets? Is it just a matter of scale that makes it hard to see? I don't think based on other papers it make sense for recourse rates to be so bad?
11) Lines 227-231 -- Is this just describing 3 fold cross-validation? If no, perhaps clarify the difference + what is the difference between the procedure for bail vs. adults/compas in this aspect?
12) Line 254-5 -- why would this be the most useful measure of recourse? Why would we want to provide recourse to individuals who already received a positive outcome?
13) Table 2 -- why does it seem to be organized as a transpose of table 1 instead of consistent with it?
14) Fig. 3 -- can you describe why recourse neg shouldn't be more monotonic in $\lambda$? Do you have an intuition?
15) Use of the term "significantly" could be more cautious.
16) Footnote 4 -- "maximize 'recourse neg" on the train set" -- can you explain why train and not validation?
17) Bibliography -- Line 370, 372 -- repeated citation?

limitations_and_societal_impact: I believe the authors are aware of societal impact of their work, and proposed it to begin with to have a positive societal impact. I did not see much discussion of limitations, however.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes the idea of training machine models that are effectively recourse ready. The authors propose leveraging adversarial training and PAC confidence sets to train models that "theoretically guarantee recourse". The experiments with four datasets demonstrate increased recourse rates while sacrificing accuracy mildly. 

main_review: Originality: 
The idea of a training recourse ready machine learning model is interesting. Looking for small perturbations that change the outcome has been the driving idea behind algorithmic recourse. However, thinking about a model that promotes recourse is unique.

Quality: 
The paper appears to be technically sound. I have a few reservations in regards to the evaluations. 

How were the features (the two features) selected for evaluation? One of the problems with providing recourse is that mutability is subjective. How will the model behave when we consider more or different features? How do the training time and recourse rates change if we increase the number of features?

We need a sensitivity analysis around $\delta$ as well. And could the authors discuss whether making a model recourse ready has any impact on diversity requirements?

I am unable to understand why the model provides CR? At best Fig 3 shows that $\lambda$ has effectively no net effect. And results show that CR works on one domain only and with limited features, which is not convincing.

Clarity: 
The paper is well written and well organised. 

Significance: 
The idea is both interesting and relevant to the algorithmic recourse community. 
limitations_and_societal_impact: None discussed sufficiently.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper develops an adversarial training framework for training models such that they are likely to have recourse options (small changes to the input which lead to switching decisions from 0 to 1); and a method for providing a PAC-inspired guarantee that an algorithm has recourse options with high probability.
main_review: I'm going to separate my review into general concerns about the setup, and then comments on the technical merits of the paper that assume that the general concerns are mitigated. The technical details of this paper are strong but they require that the setup makes sense (and that's where most of my concerns are) - so it's helpful to separate the two. 

**[Setup  concerns]** The key premise of this paper is that negative automated decisions require "small" actionable recourse with high probability. They give the example of an "applicant denied a loan, a counterfactual explanation might be: “to get a loan, increase your income by $1,000”", and want such recourse to occur with high probability. Given the massive impact that some of these systems have on applicants (bail decisions, recidivism, etc.), this is a desirable property (although it is not obvious that most recourses should be "small"): if we're going to use machine learning to assist in such consequential decisions, at the very least we should provide a recourse avenue to those who get an undesirable prediction; and recourse based on counterfactual inputs has become a popular approach in the explainable AI community. 

That said, I find the idea of using adversarial-style training (proposed in this paper) to ensure a model has a way of providing recourse worrying, because it asks to ensure that counterfactual inputs for recourse exist under the model without addressing whether or not such inputs *should* lead to a positive decision in reality? Overall very little attention is paid to whether, $f_\theta(x+\delta) = f(x+\delta)$  - i.e. whether the proposed recourse would be labeled as true under some true labelling process, $f$? This seems very problematic given that adversarial examples are usually used to highlight the arbitrariness of machine learning decisions when input data differs by small amounts from the training distribution. If the recourse suggestions have no grounding in reality---and the proposed adversarial training procedure seems likely to make this problem worse---then I'd worry that you're asking people to make arbitrary (and likely costly) changes to their lives in order to satisfy a model (e.g. it's good that it's possible to enforce constraints to ensure the procedure doesn't suggest decreases to income to qualify for a loan, but such constraints shouldn't be necessary if the proposed recourse set had any grounding in reality). 

The results shown in the recourse correctness are give some defence against this critique, but I don't know that I share their conclusions - in Figure 3, $\lambda = 0$ and  $\lambda = 2.$ are not significantly different from each other, and generally there is a lot of overlap in the confidence intervals, so I'm not sure you can conclude that the training algorithm "training algorithm encourages the existence of causally grounded recourses," especially from only a single dataset. 

This concern is the primary reason for my vote to reject. That said, this isn't my area of research, so I'll happily increase my score if the rebuttal and / or other reviewers convince me this isn't such an issue, hereafter I assume that these concerns are not an issue when evaluating the technical contribution...

**[Technical merit]** There are two parts to the approach - the adversarial training, and an approach to choosing the decision threshold such that we ensure a model "Probably Approximately has REcourse" (PARE; analogous to PAC guarantees). Both leverage existing techniques but were very well executed, and I particularly enjoyed the way that the paper uses PAC confidence sets [Park et al 2020] to ensure recourse with high probability. I could imagine such guarantees being required by regulators.

The experiments show that the method is works as intended and provides recourse options that are relatively robust.
limitations_and_societal_impact: See [setup concerns] above.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The author(s) proposed an adversarial training-based classification algorithm that guarantees affected individuals receive recourse with a high probability. The paper considers an interesting topic. The numerical experiments demonstrate the effectiveness of the proposed algorithm. 
main_review: **Pros**

* The paper is written clearly and well-organised.

* The topic is interesting. The author(s) considered classification algorithms that ensure adversarial examples do exist. 

**Cons**

* It remains unclear to me why it is useful to consider algorithms with actionable recourses in practice. It would be helpful if the author(s) could discuss this in more detail.

* The author(s) considered counterfactual explanations but did not adopt a causal framework for problem formulation. It would be better if a counterfactual outcome framework is used to present the problem, the methods and the results. 
limitations_and_societal_impact: I suggest the author(s) to discuss more about the motivations of learning classifiers with actionable recourses. In addition, the author(s) might want to adopt a counterfactual outcome framework to formulate their problems.
review_title: null

Meta-review: The paper studies how to train models that offer good opportunity for recourse, quantifying what that might mean in terms of probabilities and providing algorithms with guarantees on these. The paper is an interesting and valuable contribution to the area of algorithmic recourse and was well reviewed by the referees. Many useful and detailed suggestions were made and the authors should incorporate these into a camera ready version.
Decision: Accept (Poster)