Efficient and Provably Robust Algorithmic Recourse via the Rashomon Set
Bohdan Turbal, Iryna Voitsitska, Lesia Semenova
Algorithmic recourse offers actionable explanations for model predictions by identifying minimal input changes to improve an outcome.A critical challenge is ensuring these explanations are robust, especially when the set of near-optimal models (the Rashomon set) is present, as multiple models can equally well explain the data. Such multiplicity means that recourse actions valid for one model might fail for another, making the explanations unreliable.This paper presents a novel framework for generating efficient and provably robust algorithmic recourse. By optimizing counterfactuals over an ellipsoidal approximation of the Rashomon set, our method finds explanations that are inherently robust to model multiplicity. We provide theoretical guarantees on the uniqueness, cost, and stability of the generated counterfactuals. Our approach produces explanations that are  shorter and more robust than those from baselines, offering a practical pathway to more reliable recourse.