Thank you for taking the time to review our work. Your questions will be thoroughly addressed in the following responses.

---

Q1: I think this paper fails to discuss and compare some important baselines, and this diminishes the novelty and soundness of the approach.
Response: Thank you for highlighting the need for more extensive baseline comparisons. We acknowledge that the AReS model from [1], which focuses on global counterfactual explanations for wide-ranging population segments, offers a different perspective with its interpretable recourse summaries. Recognizing its relevance, we plan to include this model in our related work section and use it as a baseline in our experiments. This approach will help in generating a more informed prior for question determination, addressing the cold-start issue effectively. Regarding the distinctions between our work and [2], we have provided a detailed explanation in our response to the following Q2.

---

Q2: What is the difference between the proposed Bayesian PR and the method proposed in [2]? After a closer look, they are closely related and I would appreciate hearing how the proposed approach differs from the one presented in [2].
Response: Thank you for your inquiry. We have summarized the difference between our work and [2] as follows:

• Difference in personalized cost function: Unlike [2], which utilizes a linear Structural Causal Model with parameterized weight for the cost function, we employ the Mahalanobis distance to model our cost function. The reasons for choosing Mahalanobis distance and its advantages over the $\ell_1$ distance are detailed in Section 2.
• Difference in problem determination: The approach in [2] involves greedy optimization to identify an informative choice set that maximizes the Expected Utility Score (EUS), akin to listwise comparison. In contrast, our paper primarily addresses pairwise comparison, with an extension to listwise comparison discussed in Appendix A. Our goal is to identify item pairs that maximize the mutual information with the preference matrix, considering its prior distribution. We also discuss the computational benefits of pairwise over listwise comparison in Appendix A.
• Difference in posterior update: Contrary to [2]'s Bayesian inference method for inferring the posterior over weights, our method updates the posterior over the preference matrix by balancing prior-posterior distortion minimization and likelihood maximization. This approach enhances the robustness of our framework, especially in the face of user response inconsistencies.
• Difference in recourse generation: Our recourse generation method is graph-based, following the FACE method, as opposed to [2]'s reliance on a reinforcement learning-based approach, W-FARE.

The outlined distinctions highlight the unique contributions and innovative aspects of our Bayesian PR method in contrast to the methodology employed in [2]. To provide a more thorough understanding, we will incorporate this comparative analysis into both the discussion of related work and the experimental sections of our paper.

We conduct a performance comparison involving Bayesian PR, PEAR [2], and FACE on the Adult dataset. For each method, we generate the user's cost matrix $A_0$ as detailed in Section 5. Subsequently, we report the average cost and deviation across 10 users for two scenarios: using the Mahalanobis distance and the $\ell_1$ norm as the true cost functions, respectively. Notably, our Bayesian PR method achieves the lowest cost among the evaluated methods.

Table: Comparison of Bayesian PR, PEAR, and FACE using Mahalanobis distance and $\ell_1$ norm as the cost

Thank you for your comments. We appreciate the opportunity to clarify the distinctions between our work and Submission 8776. After conducting a plagiarism check with Copyleaks, we confirmed a similarity of only 5.2%, mainly due to general headings and shared references. We have summarized the difference between our paper and submission 8776 as follows:

• Major Methodological Difference: We utilize a Bayesian preference elicitation method to estimate the preference matrix $A$. This approach is based on probabilistic principles, where user preferences are iteratively updated and refined through Bayesian inference. It is designed to capture the variability and uncertainty inherent in individual preferences. On the contrary, Submission 8776 employs a graphic-like approach, focusing on finding a hyperplane closest to the Chebyshev center for segmenting the confidence set of $A$. This technique emphasizes geometric and spatial analysis, providing a different perspective on preference estimation.

• Handling Randomness and Inconsistency: In our approach, we incorporate the Bradley-Terry-Luce (BTL) model to address randomness and inconsistency in responses. The BTL model offers a probabilistic way of understanding user preferences, especially in scenarios with inherent variability. Alternatively, Submission 8776 introduces a positive margin to account for potential errors in subject judgment. This method sets a fixed error threshold, offering a distinct way of managing response uncertainties. \end{enumerate}

These differences highlight our unique approach in theory and technique compared to Submission 8776, despite targeting similar objectives in preference matrix estimation.

Q11: What is the justification for the choice $\tau\kappa = 1$?
Response: Regarding the choice of $\tau\kappa = 1$, this is based on the inverse relationship between $\tau$ and $\kappa$: by setting $\tau$ as $1/\kappa$, we ensure their product equals 1. While alternative values for $\tau$ could be determined through cross-validation, this process can be time-intensive. Importantly, our empirical findings demonstrate that the choice of $\tau \kappa=1$ yields robust performance. Specifically, this parameter setting results in lower costs when compared to other baselines, thereby validating its efficacy within the framework of our model.

---

Other Comments:
Thank you for the comments. We have incorporated the comments into our updated paper.

Q4: How does sampling compare to the analytical solution? A comparison to sampling is missing from the experiments. This is important for validating the quality of the approximate analytical solution as well as the computational efficiency claims.
Response: Thank you for highlighting this aspect. Our discussion following Theorem 3.2 outlines the computational efficiency of the analytical approach over sampling, particularly in terms of time complexity. Regarding the validation of the approximation's quality, we have presented histograms in the experimental section that illustrate Mahalanobis distances for various $\kappa$ values ($+\infty$, 1, 5, 10) at $T=10$. These findings indicate a clear trend: as $T$ increases, the means of these distributions consistently align closer to the actual cost values for all $\kappa$ values, with a corresponding reduction in standard deviations. Acknowledging the importance of your suggestion, we incorporate a comparison with sampling in future revisions, focusing on both the quality of the results and execution time.

We test the estimated probability and the analytic probability on four different dimensionalities. For each dimensionality, we perform Monte Carlo sampling with 100000 samples and evaluate $\langle A_i, M \rangle \leq 0, ~ i = 1, \cdots, 100000$. We report the computation time for both approaches. As we can see in the following table, the estimated probabilities match the analytical probability which concludes the validity of the analytic form. Furthermore, the computation times of the estimated probabilities grow more significantly than the analytic method as we deal with higher dimensions, justifying the need to adopt analytic probability.

Table: Comparison with sampling method for time and probability value

---

Q5: It would be good to state the overall complexity of pair choice, posterior update, and recourse generation.
Response: Thanks for your suggestion. Please refer to the response to Q1 in the global response part.

---

Q6: Does it make sense to consider negative-negative pairs? Or choosing unlabeled points for comparison? It would be good to justify the positive-positive choice.
Response: Our focus on positive-positive pairs is driven by the aim to alter the negative outcome to a positive outcome in prefactual recommendations; hence it is reasonable to consider only positive samples so that we can guide the user to improve. While negative-negative pairs or unlabeled points could provide additional data for the preference matrix $A$, our priority is efficiency and user experience. Our approach minimizes user queries, demonstrated in our experiments where only 10 questions are asked, thus reducing user burden.

---

Q7: The graph-based approach of section 5 considers only transitions between points from the training data, but it may be possible to transition to new points not in the data (possibly unrealizable). Can such transitions be accommodated in your framework? If we have access to the classifier we can know the label of any point.
Response: Yes. Our framework can theoretically accommodate transitions to new data points not present in the training data. This would involve enumerating these new points and integrating them alongside the training data within our graph structure. However, this approach raises concerns about the actionability of such transitions, as these new data points might be unrealizable in practical scenarios. In line with maintaining actionable recourse strategies, we adhere to the FACE methodology, which constructs the graph using only training data. This decision ensures that the generated recourses are both realistic and feasible.

---

Q8: What are typical path lengths in the experiments?
Response: In our experiments, the average path lengths observed for each dataset were as follows: Synthesis: 2.07, German: 2.54, Bank: 5.47, Student: 5.31.

---

Q9: What is the dimension $d$?
Response: The dimension $d$ represents the dimension of $x$.

---

Q10: The model seems rather small (90 neurons in 3 MLP layers).
Response: For the classifier, we adhere to the setup used by Wachter et al. (2017). The classifier's accuracy details are included in Appendix D of our updated paper.

Your review and feedback are highly valued, and we will be addressing your questions in the subsequent sections.

---

Q1: How to understand Eq (3) (and the rest of section 4) with kappa=inf? Also, the link function is approximated by a linear function (section 4.1), so how would that work when kappa=inf?
Response: Thank you for your question. When considering $\kappa=\infty$, as outlined in the proof of Proposition 1 and by applying the Dominated Convergence Theorem, we derive the following limit:

$

\lim_ {\kappa\rightarrow \infty} \text{Prob}(\tilde R_{ij}^\kappa(\tilde A)\neq R_{ij}) = \int_ {S_+^d} \lim_ {\kappa \rightarrow \infty} \Phi(\kappa R_{ij}\Delta_{ij}(S))f_P(S) dS = \int_ {S_+^d} \mathrm{1}_ {{R_{ij}\Delta_{ij}(S)\geq 0}} f_P(S)dS.

$

In this scenario, we can also use the linear function $v \mapsto v$ to approximate the step function $v \mapsto \mathrm{1}_ {\{v \geq 0\}}$. This approximation leads us to the following expression when $\kappa = \infty$

$

\text{Prob}(\tilde R_{ij}^\kappa(\tilde A)\neq R_{ij}) \approx E_P[R_{ij}\langle M_{ij}, \tilde A\rangle].

$

Accordingly, we can set $\tau=1$ in this context. We will include the discussion of the case $\kappa=\infty$ in the Appendix.

---

Q2: May be good to show empirically how this assumption affects the results vs using final kappa.
Response: We have empirically tested the impact of the $\kappa$ assumption, showcased in Figures 4 to 7 in Appendix D. These histograms display Mahalanobis distances for different $\kappa$ values ($+\infty$, 1, 5, 10) at $T=10$. The results reveal a consistent trend: with increasing $T$, the distribution means converge towards the true cost values for all $\kappa$ values, accompanied by reduced standard deviations. This indicates our framework's robustness and precision, effectively handling variations in finite $\kappa$.

---

Q3: There are several layers of approximation, it would be helpful to clearly state all of them in a single place before giving all the details. It may also be helpful to do some ablation studies and see how each level of approximation affects the overall performance.
Response: Thank you for the suggestion. Our method primarily involves two approximations: first, we consider the case $\kappa = \infty$ in mutual information computation for an analytical expression (Section 3); second, we approximate the sigmoid function with a linear function for posterior updates. The computational error in Algorithm 1, controlled by the stopping criteria $\\|\Sigma_{(k)}-\Sigma_{(k-1)}\\|<10^{-6}$, is minimal. Empirical results (Figures 4 to 7) show that as iterations increase, the approximations yield values closer to the true costs for all datasets and $\kappa$ values, with diminishing standard deviations. Detailed ablation studies for each approximation level remain a potential future research direction.

Thank you for your review and feedback. In the upcoming sections, we will address the questions you have raised.

---

Q1: Can the approach be adapted to work with recourse strategies that generalize beyond training examples?
Response: Yes. After estimating the preference matrix $A$ with a Wishart distribution $P_T\sim \mathcal{W}(m_T,\Sigma_T)$ using the Bayesian preference elicitation framework from sections 3 and 4, we can integrate the gradient-based recourse generation method proposed by Wachter et al. (2017). In applying the gradient-based recourse generation method, we work with a given machine learning model $f_w(x)$ and a loss function $g$ to measure the difference between $f_w(x)$ and the target prediction, which is 1 in our case. The optimization problem, adapted from Wachter et al. (2017), is defined as:

$

  \min_{x}\max_{\lambda}~\lambda g(f_w(x),1) + (x-x_0)^\top (m_T\Sigma_T)(x-x_0).

$

Here, $m_T\Sigma_T$ serves as an approximation for the preference matrix $A$. The maximization over $\lambda$ is achieved by iteratively solving for $x$ and increasing $\lambda$ to find a close solution, as described in Wachter et al. (2017). We can also explore other methods like gradient descent-ascent in minimax problems or considering the dual problem. Exploring the extension of our framework to encompass scenarios beyond the training samples, along with these alternative solution methods, could be a potential direction for our future research.

---

Q2: Can you comment on the impact of the lack of a causal perspective on recourse achievement and cost minimization?
Response: We acknowledge the theoretical importance of the causal perspective on the recourse problem as highlighted by Karimi et al., which we refer to in our introduction. However, our approach pragmatically navigates the complexities and variability of expert opinions, as well as the challenges in scaling this method to larger networks. This decision reflects the practical difficulties in establishing a universally accepted causal graph, especially in contexts with diverse expert perspectives or in expansive networks. Additionally, certain datasets, like the adult dataset, often lack a clear, consensus-driven causal graph, as discussed by Mahajan et al. [A]. This further underscores the adaptability of our methodology in scenarios where a causal approach may not be feasible or effective.

[A] Mahajan, Divyat, Chenhao Tan, and Amit Sharma. ''Preserving causal constraints in counterfactual explanations for machine learning classifiers.'' arXiv preprint arXiv:1912.03277 (2019).

For Experiments:
Q1: I don't think the proposed algorithm is better than the baselines because it has almost the same cost as FACE if using as the true cost. The improvement in Mahalanobis distance as the true cost is not compatible because this is the same distance used in the algorithm and to some extent, the algorithm cracks the ground truth.
Response: We apologize for any misunderstanding. In the context of Table 1, we specifically use Mahalanobis distance as the true cost. In this setup, our framework accurately specifies the cost function type to align with the Mahalanobis distance, whereas FACE misspecifies it. As a result, our method demonstrates improved cost efficiency compared to FACE when Mahalanobis distance is the true cost.

Turning to Table 2, where the true cost is modeled as the $\ell_1$ norm, FACE specifies the cost function correctly, while our framework does not. Nonetheless, even with this misspecification, our method exhibits competitive performance, matching or surpassing FACE in cost efficiency on the Synthetic and Student datasets. This contrast between Tables 1 and 2 underscores the adaptability and resilience of our approach in handling various cost function scenarios.

Q2: Why the baselines are not compared in Section 6.3?
Response: In Section 6.3, we focused on comparing our method with the graph-based FACE method due to its direct relevance. Comparisons with non-graph-based methods are detailed in the Appendix, owing to space constraints in the main text, ensuring a comprehensive yet concise presentation.

---

For Theoretical Analysis:
Q1: The complexity analysis of the whole proposed algorithm is missing or lacks discussion.
Response: Please refer to the response to Q1 in the global response part.

---

Other Comments:
Thanks for the comments. We incorporate the comments in the our updated paper.

Your review is appreciated, and we would like to express our gratitude. We will proceed to address your questions in the forthcoming sections.

---

For Presentation:
Q1: It's not clear enough why this paper applies Mahalanobis distance is selected. Why does this distance make sense to serve as the cost function? How is it compared with many other distance functions and other cost functions?
Response: In Section 2, we justify our choice of Mahalanobis distance over Euclidean or Manhattan ($\ell_1$) distances for preference modeling. This distance stands out for its ability to account for variances and correlations among dimensions, providing a nuanced view of individual, non-uniform preferences and subjective 'closeness', which Euclidean distance, treating all dimensions equally, fails to capture. Additionally, Mahalanobis distance incorporates a personalized matrix $A$, relevant in scenarios where costs involve cognitive elements and complex preference structures. This metric's effectiveness is widely recognized in the field of metric learning, as evidenced by literature like Kulis (2013), Yang & Jin (2006), and Bellet et al. (2013). Its adaptability to unique data distributions makes it particularly suitable for intricate, subjective decision-making modeling.

Furthermore, minimizing this distance aligns with the innate human tendency to achieve desired outcomes with the least effort. By using the Mahalanobis distance, we create a Riemannian manifold, introducing an element of curvature through the preference matrix $A$ [A]. This approach effectively encapsulates the complex interplay between preference and cost, enabling us to accurately model the diverse aspects of individual decision-making.

[A] Arvanitidis, Georgios, Lars K. Hansen, and S$ø$ren Hauberg. "A locally adaptive normal distribution." Advances in Neural Information Processing Systems 29 (2016).

Q2: The main message of the main theorem of this paper is hard to follow. In (2) of Theorem 3.2, I don't believe any author could easily figure out the asymptotic manner of this probability (either it's a constant, close to 0, or close to 1?).
Response: We apologize for any confusion caused. The main intent of Theorem 3.2 is to establish an analytical formula for calculating the probability $\mathbb{P}(\Delta_{ij}(\tilde A))$. This probability is a constant value when the items $x_i$ and $x_j$ and the parameters of the Wishart distribution, namely the degrees of freedom $m_{t-1}$ and scale matrix $\Sigma_{t-1}$ are given.

Q3: Following 2, the complexity of the proposed algorithm is unclear and there is no analysis on how many samples (how large $M$) are needed for the algorithm.
Response: As for the complexity of the proposed algorithm, please refer to the response to Q1 in the global response section. Regarding the number of samples ($M$), our algorithm doesn't impose a specific limit. The choice of $M$ affects performance and computational efficiency: larger $M$ enhances robustness but increases computation, while smaller $M$ reduces computational load but may affect outcomes.

Q4: It's not clear what is the difference between the proposed algorithm with FACE. Does FACE also use the shortest path? If so, what's their cost?
Response: The primary distinction between our proposed algorithm and FACE lies in the modeling of the cost function. FACE assumes a uniform $\ell_1$ norm as the cost function for all users, which does not account for the diversity in individual cost preferences. In contrast, our approach utilizes the Mahalanobis distance to model a personalized cost function. We employ Bayesian preference elicitation to accurately estimate the weighting matrix $A$, tailoring the cost function to individual user preferences.

Both our method and FACE use the shortest path approach in their respective algorithms. However, the key difference is in how the cost associated with each path is calculated and personalized, which in our model is achieved through the Mahalanobis distance and the estimated matrix $A$, as opposed to the standard $\ell_1$ norm used by FACE.