Low-Cost Algorithmic Recourse for Users With Uncertain Cost Functions

People affected by machine learning model decisions may benefit greatly from access to recourses, i.e. suggestions about what features they could change to receive a more favorable decision from the model. Current approaches try to optimize for the cost incurred by users when adopting a recourse, but they assume that all users share the same cost function. This is an unrealistic assumption because users might have diverse preferences about their willingness to change certain features. In this work, we introduce a new method for identifying recourse sets for users which does not assume that users' preferences are known in advance. We propose an objective function, Expected Minimum Cost (EMC), based on two key ideas: (1) when presenting a set of options to a user, there only needs to be one low-cost solution that the user could adopt; (2) when we do not know the user's true cost function, we can approximately optimize for user satisfaction by first sampling plausible cost functions from a distribution, then finding a recourse set that achieves a good cost for these samples. We optimize EMC with a novel discrete optimization algorithm, Cost Optimized Local Search (COLS), which is guaranteed to improve the recourse set quality over iterations. Experimental evaluation on popular real-world datasets with simulated users demonstrates that our method satisfies up to 25.89 percentage points more users compared to strong baseline methods, while, the human evaluation shows that our recourses are preferred more than twice as often as the strongest baseline recourses. Finally, using standard fairness metrics we show that our method can provide more fair solutions across demographic groups than baselines. We provide our source code at: https://github.com/prateeky2806/EMC-COLS-recourse