  Counterfactual explanations inform ways to achieve a desired outcome from a
machine learning model. However, such explanations are not robust to certain
real-world changes in the underlying model (e.g., retraining the model,
changing hyperparameters, etc.), questioning their reliability in several
applications, e.g., credit lending. In this work, we propose a novel strategy
-- that we call RobX -- to generate robust counterfactuals for tree-based
ensembles, e.g., XGBoost. Tree-based ensembles pose additional challenges in
robust counterfactual generation, e.g., they have a non-smooth and
non-differentiable objective function, and they can change a lot in the
parameter space under retraining on very similar data. We first introduce a
novel metric -- that we call Counterfactual Stability -- that attempts to
quantify how robust a counterfactual is going to be to model changes under
retraining, and comes with desirable theoretical properties. Our proposed
strategy RobX works with any counterfactual generation method (base method) and
searches for robust counterfactuals by iteratively refining the counterfactual
generated by the base method using our metric Counterfactual Stability. We
compare the performance of RobX with popular counterfactual generation methods
(for tree-based ensembles) across benchmark datasets. The results demonstrate
that our strategy generates counterfactuals that are significantly more robust
(nearly 100% validity after actual model changes) and also realistic (in terms
of local outlier factor) over existing state-of-the-art methods.
