Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors propose a recourse methodology to deal with model biases/fairness issues in producing equitable outcomes for all users (classes).  
main_review: The paper addresses an important issue of dealing with model bias in producing fair user outcomes. My main concern with the paper is the lack of clear supporting arguments on why the choice of cost models (including knowing the distribution over the cost functions) is the right one? I am not clear about the assumptions made in the proposed cost function that each user adopts.  First, how is the cost function effectively computed even with the use of a recourse set? Next, how is the recourse set itself guaranteed to always produce at least one reasonable counterfactual in the set?  More specifically, even as the authors acknowledge knowing the exact cost function by each user is difficult, their explanation of using the recourse set to get around this problem with high confidence is unclear to me.  Intuitively, it seems a measure like diversity will be more effective when the cost functions are unknown/private to the user.  

summary_of_the_review: I am not completely convinced the proposed model of computing a recourse set to minimize the expected cost for the user is always effective in the absence of knowing the cost function even approximately.   The experiments to show the effectiveness with respect to the proposed baseline are inconclusive with respect to natural measures like diversity.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the problem of algorithmic recourse is studied where the goal is to find best recourse (counterfactual set) that is optimized for user cost. The author proposed new user-incurred cost evaluation method, Expected Minimum Cost (EMC), which approximate user satisfaction without assuming a fixed global user cost function, and instead consider user cost functions as hidden and user-specific. Specifically, the authors define cost function for each user as a set of feature-specific functions of user-incurred cost when transitioning between feature states, and define MinCost as the minimum transition cost across possible recourses. To cover diverse user cost functions, they propose to model user cost distribution with a hierarchical sampling procedure and estimated expected minimum cost by drawing samples from it. Next, they formulate a discrete optimization problem using EMC as objective, and propose a search algorithm (COLS) for best recourse generation. They introduce three new metrics for user satisfaction (all related to MinCost): FS@k, Coverage and PAC. Finally, they test with two real-world datasets and show that COLS achieves significant outperformance against baselines (that optimize for distance-based metrics) on the newly proposed metrics and show that their method is doing better in fairness as well. 
main_review: Pros
-	This paper proposes a new way of evaluating user satisfaction which differs from existing methods that measures on heuristics such as distance/diversity or assume a fixed global user cost function. It is more flexible and realistic, and thus could be an interesting direction to follow. The proposed formulation is quite novel and technically non-trivial, with some theoretical grounding.
-	The experimental results are very strong on the 3 newly proposed metrics. The authors also conduct extensive ablation studies on different aspects of the problem, although many of them are deferred to the supplementary. 
-	The discussion is pretty comprehensive, and they also included a fairness analysis.

Concerns
-	One major issue is on the readability of the paper. It is certainly good that the paper contains a lot of information, however currently it seems that the main text is a bit too packed such that very limited detail about the main methodology is provided. In fact, both the core sampling and optimization algorithms are described in the appendix, and it is very hard for this reviewer to understand them solely based on the descriptions in section 4. Perhaps the authors could reorganize the content such that less space is spent on repeating the contributions/motivations. 
-	As algorithmic recourse is a rarely new domain and may not be well-known by general audience, it might be better to translate the domain-specific terminologies into plain language or more general language in ML in the introduction part. 
-	It seems the newly introduced evaluation metrics are generated using the same sampling distribution used for computing EMC, wouldn’t that be a bit circulated to evaluate something where the ground-truth is closely related to the objective used for optimization? Is there any way to evaluate on more realistic user cost rather than simulating it with the same distribution as the one used in EMC? The authors talk about distributional shift regime in the appendix, that still the ground-truth distribution is from the same family of the EMC distribution (mixture of percentile shift and linear cost). It might be more convincing if it is from a totally independent distribution.

Questions
-	What is used as the initial starting set for COLS? 
-	In the problem formulation in (2), does it mean that the best recourse set would consist at least one desired outcome solution but it may not be the one with lowest cost? If so how do one achieve balance between outcome and satisfaction?
-	What is the computational complexity of the algorithm?
-  Is there any downside from the underperformance in distance-based metrics?

summary_of_the_review: In this paper the author proposed a new way for evaluating and optimizing user satisfaction. The technical contributions are solid and the results are rather promising despite the potential bias toward EMC. The paper contains fruitful discussion and ablation studies, although it can be further improved in terms of clarity. Therefore, I would like to give a weak accept.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work introduces a new method for identifying actionable recourses for users with user-specific cost functions. Users’ cost functions are hidden from the recourse method. The paper proposed a discrete optimization algorithm COLS to solve the objective EMC. It further used a popular real-world dataset to illustrate the performance.
main_review: I enjoyed reading this paper in general. My major comments are:

1.	In Section 4.1, it is assumed that there is a distribution over all the cost functions D_c for the population. Is the distribution D_c known or unknown? A more practical setting is that D_c is unknown. Then how to use Monte Carlo Estimation to approximate the expectation of the MinCost?

For different users u, it is assumed that C_u follows distribution D_c. However, in the introduction, it claims that “we propose a method for identifying a user-specific recourse set that contain at least one good solution for the user”. However, it seems inconsistent between the motivation and the assumption. Why do all users share the same distribution of the cost function? Is the framework generalizable to the setting with different distribution?

2.	Theorem 4.1 proves the monotonicity of Cost-Optimized Local Search Algorithm. But how does ExpMinCost(s_u, S_t^best; {C_i}_{i=1}^M) converge? Theorem 4.1 does not imply that, but it is a very important question.

3.	Why choosing Equation (3) and Equation (4) as metrics to measure recourse quality? What is the advantage of choosing a threshold function? How to choose k in real cases?

4.	In the numerical experiments, could you compare with other functions that measure the recourse quality in previous recourse papers? I think my main concern is on FS@k. Is using FS@k equivalent to the following: assume there exists a black-box algorithm that can output the indicator that if the total cost is smaller than k, then the distance function can be used to measure the recourse quality.
 Could you use numerical experiments to emphasize the advantage of using FS@k compare to other measure functions such as weighted sum of costs?

5.   What is the computational complexity of your algorithm? How is that compared to other benchmarks?

6.    Why is fairness an important issue in this work? Could you comment more on this part to motivate?

summary_of_the_review: This paper studied an interesting problem. To improve the paper, the author may want to illustrate the advantage of using FS@k and how it is very different from state-of-art measure functions, both conceptually and numerically.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper aims to find algorithmic recourse that has low-cost to the users. Unlike previous work, the authors do not assume that there is a known global cost function that is shared by all users.
main_review: I do not think this papers achieves what it sets out to do. It is mentioned in the related work, how the closest literature to the paper is other cost-based approaches to finding recourse and different from those approaches, this paper drops the assumption that there is a known global cost function that is shared by all users. First, the paper formulates $\mathrm{MinCost}(\cdot;\mathcal{C}_u)$ as the cost function of user $u$, which is characterized by the unknown transition matrices $\mathcal{C}_u$. However then, the paper assumes a distribution $\mathcal{D}$ over $\mathcal{C}_u$ 's of different users is known and proposes to optimize $\mathbb{E}_\mathcal{C}{}_\sim{}_\mathcal{D}[\mathrm{MinCost}(\cdot;\mathcal{C})]$, which is effectively a known global cost function (with respect to user state $\mathbf{s}_u$ and recourse set $\mathcal{S}$). Is this not the case?

Having said that, the proposed cost function has a certain structure and it is still novel: (i) authors propose a hierarchical cost distribution as the particular $\mathcal{D}$ they consider and (ii) by only considering the element with the minimum cost for each sample from $\mathcal{D}$, they exploit the fact that each users only really requires one recourse that they are happy with to be satisfied. Proposing a new cost-based objective like this could still be a valuable contribution. But then, the paper needs to be positioned accordingly and highlight the merits of optimizing a cost-based objective structured in this new way. Note that the current experiments are not helpful in comparing against other cost-based objectives proposed in previous work: cost functions of the users are simulated according to the proposed cost function, then of course, a method that optimizes it would perform better than methods optimizing other cost functions.

Some of the conclusions made in the results section suffer from user preferences being simulated as well. For instance, at the end of "Q2," the authors conclude that high diversity is not necessary to satisfy individual users; this is of course true for the simulated users since their cost function is designed to ignore diversity in the first place.

summary_of_the_review: I believe the claim that the paper relaxes the assumption of knowing a global cost function is not true. However, it still introduces an interesting new objective to optimize for when finding algorithmic recourse.
review_title: null

Meta-review: This paper makes an interesting contribution to the literature on algorithmic recourse. More specifically, while existing literature assumes that there is a global cost function that is applicable to all the users, this work addresses this limitation and models user specific cost functions. While the premise of this paper is interesting and novel, there are several concerns raised by the reviewers in their reviews and during the discussion: 1) While the authors allow flexibility to model user specific cost functions, they still make assumptions about the kind of cost functions. E.g., they consider three hierarchical cost sampling distributions, each of which model percentile shift, linear shift, and a mixture of these two shifts. The authors do not clearly justify why these shifts and a mixture of these shifts is reasonable. Prior work already considers lot more flexible ways of modeling cost functions (in a global fashion). For example, Rawal et. al. 2020 actually learns costs by asking users for pairwise feature comparisons. Isn't this kind of modeling allowing more flexibility than sticking to percentile/linear shifts and their mixture? 2) Several reviewers pointed out that the main paper does not clearly explain all the key contributions. While the authors have updated their draft to address some part of this concern, reviewers opine that the methods section of the paper still does not discuss the approach and the motivation for the various design choices (e.g., why a mixture of percentile and linear shifts?) clearly. 3) Reviewers also opine that some of the evaluation metrics also need more justification. For instance, Why is fraction satisfied measured at k = 1 i.e, FS@1 measured and why not FS@2 or FS@3? Will the results look different for other values of k here? 4) Given that Rawal et. al. 2020 is a close predecessor of this work, it would be important to compare with that baseline to demonstrate the efficacy of the proposed approach. This comparison is missing. 

Given all the above, we are unable to recommend acceptance at this time. We hope the authors find the reviewer feedback useful.
Decision: Reject