Cost Adaptive Recourse Recommendation by Adaptive Preference Elicitation

Dear reviewer,

We appreciate that you review our paper and provide insightful comments. We would like to address your concerns as follows:

Therefore, it is not clear to me the benefits of ReAP over PEAR.

There are several benefits of ReAP:

1. ReAP is computationally tractable. ReAP is based on semidefinite programming and geometric calculations to find the questions. All operations in ReAP can be done in less than half a second on a laptop. In contrast, the Bayesian approach proposed by De Toni et al. (2022) is computationally intensive.
2. ReAP delivers a better solution than PEAR. In Table 8, we have shown that our method outperforms PEAR in the Adult and GMC datasets.
3. It is not trivial to generalize PEAR to the Mahalanobis cost setting while using the Mahalanobis distance as in our paper can bridge with causal models, as we described in Appendix D.2.
4. PEAR requires a linear structural causal model to define the cost of changing a specific feature, whereas our method does not require such a model.

Why did the author not include PEAR as a baseline in the main paper

Thank you for your comment. We include PEAR in the appendix for a better explanation of the formulation and the settings of the experiments. We will include these results in the main paper in our final version, in which more space is allowed.

If the number of features is truly high, we might just need to estimate only the cost of the features we need for recourse rather than the full matrix

We agree that we only need to estimate the cost associated with the features we need for recourse. However, the number of features we need for recourse can also be truly high. In this case, the number of parameters to be estimated/learned is still large.

How do you explain the fact that Watcher and ReAP achieve almost the same cost/validity in all four datasets?

Regarding validity, we employ an early stopping criterion, terminating the algorithm when a valid recourse is obtained for both algorithms. Therefore, both methods have a perfect (1.0) validity.

The objective function for Wachter is non-convex for a fixed $\lambda$ when we consider an MLP classifier. In particular, if we initialize $\lambda=0$, and then increase the value of $\lambda$, the difference in the cost of recourse compared to the initial $\lambda$ is negligible. Therefore, Watcher and ReAP achieve almost the same cost. However, our methods still show improvements over Wachter in terms of cost in all the experiments.

Dear reviewer,

We thank you for the review and thoughtful feedback!

From our understanding, the reviewer is proposing that we should employ a Bayesian approach. We agree that the Bayesian approach is a flexible and systematic framework to deal with this cost-learning problem. In fact, the reference PEAR (De Toni et al. (2022)) relies on a Bayesian framework to learn the cost function. However, the Bayesian approach is computationally intensive, and many ad-hoc adaptations need to be used in order to make it work (sampling, variational posterior, etc.). All components of the Bayesian method, including computing the posterior distribution and identifying the questions to ask the subject, require integration, which is computationally expensive.

Our ReAP method focuses on tractability. That is why we focus on a deterministic approach to solving the cost learning problem: in a noiseless setting, finding the center is done by semidefinite programming, and finding the questions is done by linear algebra computations. All components in our paper are computationally tractable. Hence, at least, we have a solution method that can be deployed in an efficient manner. Empirically, we also show that our method performs well in popular datasets.

Considering uncertainty in user response is very important, we totally understand that. In a deterministic setting, we have shown how to hedge against this uncertainty using binary variables. We report the numerical results in the table below. The table demonstrates that our method outperforms FACE in terms of cost, indicating that our approach efficiently captures the preferences considering uncertainty in user response.

Developing a Bayesian method is an attractive idea. However, we believe that it is too far away from the narrative and the goal of this paper. A Bayesian approach will significantly differ from everything we present in this paper. Thank you!

Thanks for the quick response. Based on the statistical analysis and new ablations, I will raise my score from 6 to 8.

Dear reviewer,

Thank you for being responsive in discussing our paper. We address your remaining concerns as the following:

Why not compare with Bradley-Terry models fit to individual users as T=1…10 queries are collected?

We are eager to conduct an experiment comparing the two methods. However, we cannot find the public implementation of Rawal and Lakkararaju (2022) on ArXiv, NeurIPS, or the author's website.

It seems like the method performs at least as well as baselines — but I ultimately expect some clearer evidence to be presented.

Looking at the mean and spread is not an informative way to reach a conclusion.

We propose to look at the paired difference of the cost: for each subject, we compute the ReAP cost and the competing method’s cost. We propose to test the hypotheses:

Null hypothesis: ReAP cost equals the competing method’s cost Alternative hypothesis: ReAP cost is smaller than the competing method’s cost.

In order to test the above hypothesis, we use a one-sided Wilcoxon signed-rank test to compare the paired cost values. The p-value of the test between ReAP and the baselines is reported in the following table.

Suppose we choose the significant level at 0.05. The table indicates that ReAP significantly outperforms DiCE and FACE across all datasets. ReAP outperforms Wachter in two out of three datasets, except for the Student dataset [Note that this does not imply that Wachter cost is lower than ReAP cost in the Student dataset]. Additionally, ReAP demonstrates superiority over PEAR in the GMC dataset.

There are objectives that operate at the individual vector level besides the distance and sparsity objectives in DiCE. If you’re doing T=10 queries, I think it would be fair to run DiCE with k=10 recourses optimized in parallel.

Each component in the objective of DiCE: validity and proximity, can operate on a single vector, except for the diversity term. In the implementation of DiCE, when choosing $K=1$ recourse, DiCE simply removes the diversity term. The time comparison between the two methods shows that even when generating $K=1$ recourse, our method still exhibits significantly better runtime than DiCE.

I’d be interested in seeing an ablation in the appendix comparing worst-case to centroid-cost for optimization purposes.

We conducted an experiment computing the average path lengths for the two methods, employing A* or solving the worst-case objective in Problem (7) are presented in the following table. The results indicate that the path lengths obtained by solving the worst-case objective are only marginally higher than the alternative, highlighting the effectiveness of our proposed method.

Dear reviewer,

We thank you for reviewing and providing constructive feedback. Below, we address your concerns.

Why wasn’t a comparison conducted against Rawal and Lakkararaju (2022)?

Rawal and Lakkararaju (2022) employ the Bradley-Terry model to estimate a universal cost function (one cost function for all users) and then utilize the user input to generate personalized recourse for the user. The setting of Rawal and Lakkararaju (2022) is significantly different from ours. Our setting requires learning a personalized cost function through a preference elicitation process (each user is associated with a different, personalized cost function). Therefore, the comparison between the two methods is not necessarily fair.

Moreover, the method from Rawal and Lakkaraju (2020) is addictive in features. Therefore, it is unable to recover the underlying causal graph. As in our paper, using the Mahalanobis distance can bridge with causal models, as described in Appendix D.2.

The method is its limited improvements over even simple baselines on common datasets

We do not agree with this observation. In Table 1 and Table 2, we demonstrate that our method significantly outperforms DiCE and FACE in terms of cost. Our method even outperforms the adaptive version of Wachter on three over four datasets.

What is the size of the solution set returned by DiCE? Is the comparison with ReAP fair in terms of computational cost and subject query cost?

In our experiments, we find a single recourse for each method to ensure a fair comparison. We report the computational time comparison between our method and DiCE in the table below. Our method has a significantly lower runtime compared to DiCE.

Reference

Thank you for your comment. We have included the recommended reference in our revised draft.

Why optimize over the worst-case cost function?

The terminal set $\mathcal U_{\mathbb{P}}$ is generally not a singleton as it still contains many possible matrices that conform with the feedback information. To find the recourse, we need to borrow the ideas from robust optimization, which formulates the problem as a min-max optimization problem. Looking at the worst-case situation can eliminate any bad surprises regarding the implementation cost. Practically, the min-max problem manages to provide an acceptable recourse for challenging scenarios within the domain where $A$ is a matrix satisfying $A \preceq I, A \in \mathbb{S}_{+}^d$. This approach also proves valuable when users' responses contain significant noise and inconsistencies, which in turn results in a still large search space for $A_0$ in the final round.

Dear reviewer,

We appreciate that you review our paper and provide insightful comments. We would like to address your concerns as follows:

Queries are chosen from the positive set $D_1$ only. Does it make sense to consider points from $D_0$ or new points that have no label?

We select recourse pairs from the positive set D_1 to learn the subject's cost function by comparing two recourses. It is also possible to consider points from $D_0$ or new points with no label with minimal change to our learning workflow. However, for the recourse application, asking the subject to compare points in $D_0$ may give the user a false sense of psychological expectation. As such, we only consider the positive set $D_1$ and keep the question as "Between two recourses, which one do you prefer?" so that the users know that the two points under comparison both lead to positive predicted outcomes. This setting will help reduce psychological/cognitive bias to the subject's expectations.

The worst-case objective might be too conservative, resulting in longer paths. It would be interesting to compare it at least empirically to other choices. In Table 2, what is the average path length?

The average path lengths for the two methods, employing $A^\star$ or solving the worst-case objective in Problem (7) are presented in the following table. The results indicate that the path lengths obtained by solving the worst-case objective are only marginally higher than the alternative, highlighting the effectiveness of our proposed method.

The problem in Eq (7) does not seem like the real problem that needs to be solved. The set $\mathcal U_{\mathbb{P}}$ updates after every step.

We think that the reviewer may have misunderstood the setting here: In deployment, the system will pick a fixed value of $T$, and problem (7) will be solved with $\mathcal U_{\mathbb{P}}$ being the terminal confidence set, obtained after we have asked the subject to compare $T$ rounds. Thus, we solve Eq (7) only once.

In the experiments, we conduct the experiments with varying $T$ to study the effects of the number of comparison rounds on the quality of the recourse recommendation. We do not solve (7) multiple times in our workflow.