  As predictive models are increasingly being deployed in high-stakes decision
making (e.g., loan approvals), there has been growing interest in post hoc
techniques which provide recourse to affected individuals. These techniques
generate recourses under the assumption that the underlying predictive model
does not change. However, in practice, models are often regularly updated for a
variety of reasons (e.g., dataset shifts), thereby rendering previously
prescribed recourses ineffective. To address this problem, we propose a novel
framework, RObust Algorithmic Recourse (ROAR), that leverages adversarial
training for finding recourses that are robust to model shifts. To the best of
our knowledge, this work proposes the first solution to this critical problem.
We also carry out detailed theoretical analysis which underscores the
importance of constructing recourses that are robust to model shifts: 1) we
derive a lower bound on the probability of invalidation of recourses generated
by existing approaches which are not robust to model shifts. 2) we prove that
the additional cost incurred due to the robust recourses output by our
framework is bounded. Experimental evaluation on multiple synthetic and
real-world datasets demonstrates the efficacy of the proposed framework and
supports our theoretical findings.
