Diverse and Plausible Algorithmic Recourse via Tractable Recourse Distributions

Algorithmic recourse aims to provide individuals with actionable changes to reverse unfavorable automated decisions (e.g., loan denials). Existing methods typically treat recourse as an optimization problem, generating a small, fixed set of counterfactuals. This often forces a trade-off between diversity, plausibility, and feasibility. The authors ask: can we instead model the entire space of feasible recourse as a probability distribution to naturally generate diverse and realistic alternatives?

The authors propose Tractable Recourse Distributions (TRD). Instead of solving a new optimization problem for every individual, they use the positive-class distribution—learned once as a probabilistic circuit (PC)—and apply exponential tilting. By incorporating cost functions for proximity and sparsity directly into the PC, they transform the base distribution into a factual-specific recourse distribution. Because smooth and decomposable PCs are closed under this type of tilting, the resulting distribution remains tractable, allowing for exact likelihood evaluation and efficient sampling without retraining the model.

TRDs allow for the generation of diverse and plausible recourse sets by sampling from the tilted distribution rather than solving for isolated points. The framework provides explicit control over the trade-off between proximity and sparsity through tilting parameters. Experiments on standard tabular benchmarks and MNIST demonstrate that TRDs simultaneously achieve high validity, plausibility, and diversity. Furthermore, the authors show that even after enforcing hard feasibility constraints (such as actionability and causal consistency) via conditioning and rejection sampling, the framework retains enough probability mass to provide valid recourse for all tested instances.

This work shifts the paradigm of algorithmic recourse from point-based optimization to density-based modeling. By representing the space of possible interventions as a distribution, it provides a more comprehensive view of the options available to an individual. This approach avoids the need for ad-hoc diversity objectives and allows for a more flexible, user-centric generation of recommendations that adapt to the underlying structure of the data.