  Algorithmic recourse emerges as a prominent technique to promote the
explainability, transparency and hence ethics of machine learning models.
Existing algorithmic recourse approaches often assume an invariant predictive
model; however, the predictive model is usually updated upon the arrival of new
data. Thus, a recourse that is valid respective to the present model may become
invalid for the future model. To resolve this issue, we propose a novel
framework to generate a model-agnostic recourse that exhibits robustness to
model shifts. Our framework first builds a coverage-validity-aware linear
surrogate of the nonlinear (black-box) model; then, the recourse is generated
with respect to the linear surrogate. We establish a theoretical connection
between our coverage-validity-aware linear surrogate and the minimax
probability machines (MPM). We then prove that by prescribing different
covariance robustness, the proposed framework recovers popular regularizations
for MPM, including the $\ell_2$-regularization and class-reweighting.
Furthermore, we show that our surrogate pushes the approximate hyperplane
intuitively, facilitating not only robust but also interpretable recourses. The
numerical results demonstrate the usefulness and robustness of our framework.
