Equally accurate models disagree on advice: ORPM budgets for the worst case and reaches 62.5% joint validity on trees

Recourse can now be optimized against a whole set of similarly performing models with different architectures, not only against the deployed model. Earlier robust recourse either assumed bounded shifts in model parameters or covered only linear models or neural networks sharing a fixed feature extractor, requiring models to be close in parameter space. On one synthetic and five real datasets, with competing sets of linear, neural, mixed and decision-tree models, ORPM achieved higher joint validity than ROAR, ElliCE and ADV on every dataset except GMC across all budgets.

The solver casts recourse generation as a zero-sum game against an adversary that picks the worst model, so each round only requires solving one weighted ordinary recourse problem. Directly optimizing the worst case over all competing models at once is hard when model classes differ and losses are nonconvex. Each round an approximate oracle returns recourse for the current model distribution, and the adversary shifts probability mass toward models with higher loss at that recourse via multiplicative weights; with bounded loss and controlled global oracle error, the mixture gap of the response distribution converges to an approximate equilibrium, and in the convex case the averaged point carries the same guarantee.

For decision trees, whose predictions are piecewise constant, the oracle instead jointly encodes all competing trees as a mixed-integer program. Input gradients of trees give no useful search direction, so gradient-based robust recourse does not carry over directly. On COMPAS with five depth-four decision trees at budget 5, ORPM reached 62.5% joint validity, versus 46.0% for the RobX-constrained adaptation, 43.0% for the OCEAN-style method, 14.5% for the ADV surrogate and 10.0% for the ROAR surrogate.

The evaluation covers one synthetic and five real datasets, with competing sets of linear, neural, mixed and depth-four decision-tree models; recourse cost is distance in standardized feature space with immutable features fixed, so the conclusions are limited to these datasets and constructed competing sets.

Good performance on the competing set does not always establish validity for unseen models: MinL2 often matches ORPM on seen models but reaches only 0–2% joint validity on unseen ones. Increasing the budget does not uniformly reduce group disparities: on GMC ORPM's gap falls from 36.7 to 19.6 percentage points as the budget rises from 5 to 10, while on COMPAS it rises from 7.0 to 16.5 points as the budget rises from 1 to 2, and confidence intervals in these experiments are often wide.