Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work proposes a probabilistic framework for navigating the trade-off between cost and robustness in algorithmic recourse. More concretely, given a user-specified recourse invalidation rate, a loss function accounting for the invalidation rate, target score, and cost is minimized to find the suggested recourse. One challenge that arises when pursuing this approach is that a naive Monte Carlo approximation of the invalidation rate is non-differentiable. This is circumvented by taking a first-order approximation of the invalidation rate, which has a differentiable closed-form expression. The cost required to achieve a given invalidation rate is derived using this expression. Finally, an upper bound on the (approximate) invalidation rate is derived. The proposed approach is evaluated empirically across various real-world data sets, demonstrating its ability to find better points across the cost-invalidation rate Pareto front than existing approaches.
strength_and_weaknesses: Strengths:
1. The problem tackled by this problem is practically relevant and, to my knowledge, has not been addressed before.
2. The proposed approach is technically sound overall.
3. This paper is very well-written and easy to follow.
4. The code the reproduce the experiments is available.

Weaknesses: 
1. My main concern with the proposed approach is its ability to thoroughly explore the cost-invalidation rate Pareto front. From a multi-objective optimization perspective, this work proposes to use a particular scalarization. However, it is unclear if the entire Pareto front can be recovered by tweaking the parameters of this scalarization. I would like the authors to discuss this.
2. I am not very familiar with the related literature, but the proposed approach seems to have little technical novelty.
3. Is there any guidance to choose $\lambda$ in practice? For example, how is $\lambda$ set in the experiments described in Table 1?
4. Noise in the empirical evaluation seems to be very low ($\sigma^2 = 0.01$). How was this value chosen? The effect of the noise should be investigated more thoroughly. 

Other minor comments:
1. The domain of $d_c$ should be $\mathbb{R}^d\times \mathbb{R}^d$ instead of $\mathbb{R}^d$.
2. In the following line, "...is the recourse invalidation rate from equation 1", "equation 1" should be "equation 2".
clarity,_quality,_novelty_and_reproducibility: This paper is very clear. The proposed approach is technically sound overall. However, I have a concern about its ability to explore a significant portion of the cost-invalidation rate Pareto front. Overall, I believe the quality of this work is reasonably high. However, there seems to be little technical novelty. The code to reproduce the experiments was included, but some details of the empirical evaluation seem to be missing. Thus, this paper performs moderately in terms of reproducibility.
summary_of_the_review: This work proposes a framework for navigating the trade-off between cost and robustness in algorithmic recourse, a problem that is practically relevant and has not been addressed before. The proposed approach is technically sound. However, I have some concerns about its ability to explore this trade-off fully. Overall this paper is well executed. However, the technical novelty it provides seems limited. I am open to changing my score after the authors' rebuttal and discussion with my fellow reviewers.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper considers a model for providing counterfactual explanations that are both easily attainable (i.e., have low cost) and robust (i.e. if the recourse action is not implemented exactly - in other words is noisy - then the output will most likely not change). Due to a natural trade-off between these two criteria, prior work only considers optimizing one at the expense of the other. To my understanding, this paper gives the first result combining both in a controllable way. 

The theoretical results of this paper are also accompanied by a validating suite of experiments.
strength_and_weaknesses: Strengths:

1) The newly introduced model appears to be a very natural way to combine the two goals, i.e., low cost and robustness.
2) The experiments seem validating enough.

Weaknesses:

1) The clarity in the presentation of the theoretical results is poor. In particular, Section 4.2 is very confusing. Upon reading the earlier sections, I was expecting a theorem that would clearly present the achieved algorithmic trade-off between the confidence parameter r and the cost of the counterfactual. 
clarity,_quality,_novelty_and_reproducibility: See previous answer.
summary_of_the_review: The proposed model and results seem like a interesting contribution to a practical problem. However, the clarity of the writing does not allow me to give a higher score, since I cannot really grasp some of the vital theoretical results of the paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this paper, the authors give a framework, called PROBE (Probabilistically Robust Recourse), to address the problem of providing low cost recourse that is also robust. Prior work in this context focused on either achieving low recourse costs, that led to mechanisms that were very sensitive to input perturbations or small shifts in the prediction model considered; or mechanisms that were highly robust, but incur high recourse costs. Further, in real life, recourse mechanisms are implemented noisily, thus, there is a need to manage the trade-offs between recourse cost and robustness effectively. The authors address the latter in this paper. Towards this, they define the notion of invalidation rate (IR), which denotes the probability with which a recourse gets invalidated due to small changes in the recourse arising due to human error. A threshold for IR is chosen by users to navigate trade offs between cost and robustness. The authors propose a new objective, that adds a Hinge loss term along with the standard objective function to ensure that the output recourse has a low probability of being invalidated. The main algorithm proposed essentially performs a gradient descent, while considering an approximation to the value of IR at each time step. The authors also give general upper bounds for the value of IR given any recourse method. Finally, an extensive empirical analysis is performed, comparing costs and IR for PROBE and other existing frameworks. 
strength_and_weaknesses: Strengths:
The main contribution of this paper is the notion of IR and how to find a good approximation to it efficiently; and the modified objective function to incorporate IR such that the output recourse not only has low cost but also low invalidation probability. I believe IR and the modified objective are of interest for developing low-cost robust recourse mechanisms. The extensive experimental results support the claims of the paper well.

Weaknesses:
1) How were the r values chosen for each dataset? A small description of this would be useful.
2) Are there any convergence guarantees for PROBE? Is it guaranteed that the IR will be less than r eventually?
clarity,_quality,_novelty_and_reproducibility: The framework proposed by this paper is novel, in the sense that it studies the question of robust low-cost recourse mechanisms under noisy implementations. The problem and applications are well motivated in the paper. Relevant examples and intuition specified whenever applicable help better understand the subject matter. Overall, it is a well-written paper.
summary_of_the_review: Overall, I believe the contributions of this work are interesting to the Algorithmic Recourse community. The proposed framework is simple, cost effective, and powerful in terms of allowing users to choose the trade off parameter r. Following are a few line-by-line comments.

Minor Comments:
- Page 3: para 2, end of line 5: should be minimax
- Page 3: equation (1), remove extra ‘)’ in term 1 of rhs
- Page 4: equation (3), should it be R(x’; r , \sigma^2 I)? Also, remove extra ‘)’ in the second term.
- Page 4: last para, line 3, a output -> an output
- Page 5: Sec 4.2 para 1, line 5, Section not referenced
- Page 9: para 1, line 2, recousre -> recourse
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: 1. The paper proposed a new user-driven algorithmic framework PROBE (Probabilistically Robust Recourse) that tackles two independently well-studied challenges in algorithmic recourse  -- (1) recourse cost, and (2) robustness under noisy human implementation. This is the first study where both recourse cost and robustness are simultaneously optimized. 

2. PROBE enables the end users to navigate the tradeoffs between recourse cost and robustness via an input parameter $r$ which is a user-defined upper-bound on the invalidation rate i.e., recourse can be invalidated at most $r$ percent of the time. Note that $r=1$ corresponds to high-risk and low recourse cost and $r=0$ is low-risk and high-cost recourse. 

3. The main contributions of this paper are (i) the definition of the recourse invalidation rate (IR) in Definition 1 and Equation (2) (ii) approximating the invalidation rates of any given instance w.r.t different underlying prediction models like linear models, non-linear models and tree-based models, etc. Thus, the paper efficiently implements the PROBE algorithm (1) using the closed form of approximated invalidation rates (Theorem 1). 

4. There are an extensive set of experiments conducted on multiple datasets comparing PROBE to existing algorithms that minimize recourse cost (Watcher, AR-LIME, DICE, and GS -- Figure 5) and robust algorithms (ROAR, ARAR - Figure 5). Their empirical evaluation using well-defined measures like "recourse accuracy (RA)", "average recourse invalidation rate (AIR)" and "average cost (AC)" show that PROBE generated recourses that are more robust than existing baselines (Table 1). Further, the empirical evaluation supported the theoretical upper bounds on IR in Proposition 3.  


strength_and_weaknesses: Strengths : 
1. The area of algorithmic recourse has a great impact and is an important problem to study. The current work addresses an important problem of managing the trade-off between two highly desired objectives (recourse cost and robustness). 
2. The definition of invalidation rate is characterized in a closed-form such that PROBE can be efficiently implemented. 
3. The empirical evaluation on multiple datasets showed no violation with the theoretical guarantees provided (Figure 5 and Proposition 3)


Weaknesses : 
1. The convergence of the algorithm PROBE is not discussed. Since the optimization of the objective in Equation (3) in PROBE as discussed is being done via gradient descent, it would be interesting to compare the convergence of PROBE with existing baselines.
2. The presentation of the paper can be improved in various places like (1) Referencing the proofs in the main paper. (2) Outline the additional experiment results in the appendix.

clarity,_quality,_novelty_and_reproducibility: The presentation of the paper can be improved. Proofs and the experimental details in the appendix needs some referencing in the main paper. There are minor typos. 
summary_of_the_review: I believe the paper has studied an important problem and made strong technical contributions. The empirical evaluation is extensive and the results are inline with the theoretical analysis. The presentation of the paper in my opinion can be improved to help readability.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: It has become clear that in AI/ML—driven decisions (e.g., in loan decisions), individuals who are adversely impacted (e.g., their loan application getting denied by the ML system) are provided a means for recourse. Known approaches achieve low cost---ease of implementation---or robustness to small perturbations, but not both due to the inherent trade-offs between the cost and robustness. Also, these known approaches do not provide users with the ability to control these trade-offs. This paper develops what may be the first rigorous algorithmic framework for users to manage this trade-off. Specifically, the paper’s Probabilistically ROBust rEcourse (PROBE) approach lets end-users choose the probability with which a recourse could get invalidated if the recourse is implemented somewhat noisily. Both rigorous theory and promising experimental results are presented. 

The paper is very well-written. The authors are encouraged to show better how the proposed approach can explore the whole Pareto frontier for the tradeoff.

justification_for_why_not_higher_score: The paper does not rise to the level of oral/spotlight: e.g., the authors do not consider the whole Pareto frontier of the tradeoff. 
justification_for_why_not_lower_score: Impressive combination of theory and experimentation for an increasingly-important problem domain in explainable AI.
Decision: Accept: poster