acceptodds
Under review as a conference paper at ICLR 2027

RECOURSE AS A CONTRACT: CERTIFYING REALIZED RECOURSE UNDER BEHAVIORAL AND MODEL DRIFT

12 views

Abstract

Algorithmic recourse recommends changes intended to reverse an unfavorable decision, but a recommendation need not be implemented exactly, and the classifier may change before the individual returns. The relevant deployment question is therefore not whether the prescribed action remains valid, but whether the realized response will be accepted by the model in force at the realized return time. We formalize this requirement as a recourse contract: a high-confidence upper bound on terminal recourse failure. In practice, behavioral responses to recommendations and model evolution are typically observed in separate, unpaired data sources. Consequently, their marginal distributions may be estimable while the dependence between them, which determines terminal risk, is not. We characterize this partial-identification problem sharply, showing that the best coupling-robust set certificate attains the worst-case endpoint of the identified risk interval, and that this endpoint can become vacuous under a Strassen-type coupling condition. We then develop finite-sample contracts that remain valid for arbitrary dependence between the two channels and for action-dependent return times. We also establish a distribution-free certification floor of order , showing that limited model history creates an intrinsic barrier to strong guarantees, and identify a complementary tension between recommendation effectiveness and the transferability of behavioral evidence. Experiments on controlled synthetic environments and temporally evolving LendingClub classifiers show that independence-based and model-only certificates can substantially understate realized risk, while our contracts remain valid and expose when the available data are insufficient to support a nontrivial guarantee.

Primary area:
interpretability and explainable AI
Keywords:
Algorithmic Recourse, Model Drift, Distribution-Free Risk Control, Non-Compliance, Robustness, Finite-Sample Guarantees

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_6yvLOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies realized algorithmic recourse when applicants may implement advice imperfectly, return at action-dependent times, or never return, while the classifier may change. It formulates a cell-level recourse contract bounding terminal failure, characterizes the risk interval compatible with unpaired behavioral and model-path marginals, and develops finite-sample certificates combining behavioral tests with path-wise model tolerance sets. It also derives a certification floor and a recommendation-leverage decomposition. Synthetic experiments probe dependence, timing, and data limitations; a LendingClub study evaluates five generators using real covariates and refitted classifiers with simulated responses and return times. The reported bootstrap-based certificates concern estimation uncertainty around known model updates; a historical backtest yields abstention in every cell, limiting evidence for certification under genuine future drift.

Critical strengths
  • The setup is interesting and seems comprehensive, accounting for realized responses, non-return, and the model in force when an applicant returns (Lines 79–89). This broad formulation is an appealing aspect of the work, although I wonder whether all of its machinery is necessary.
  • The distinction between finite-sample uncertainty and uncertainty from an unidentified coupling is conceptually valuable. The sharp finite-support characterization identifies what additional marginal data alone cannot resolve (Lines 108–133).
  • The seemingly comprehensive literature review also helps situate the work (Lines 323–354).
Critical weaknesses
  • Sections 3–5 are very dense and difficult to follow (Lines 108–318). Running examples across different marginal settings, together with a brief explanation of what to do with each proposition, would help convey why the results matter. The contribution summary (Lines 54–67) did not help me appreciate the work sufficiently. Strassen’s condition is also invoked before it is explained (Lines 20–22, 56–58, 123–126), adding to the difficulty.
  • The experiments provide limited evidence of practically useful certification under genuine model drift. On LendingClub, only two of ten cells are certified, with failure bounds of 0.77 and 0.98; the historical backtest yields abstention in every cell (Lines 444–462). Moreover, the guarantee assumes historical increment paths are i.i.d. draws from the deployment increment law (Lines 193–195), whereas the authors acknowledge that the historical paths overlap and are not i.i.d. (Lines 1824–1827). These limitations leave the practical scope of the guarantees unclear, even if the certificates are valid under the stated assumptions.
Questions for authors
  • Clarification: Is the explicit response kernel needed in the problem formulation, and could you explain its role relative to the response-record distribution? The setup seems comprehensive, but I wonder whether it is more elaborate than necessary (Lines 79–89).

  • Clarification: What exactly is meant by the recommendation “logs” and the “available logs”? A concrete example of the records in the two unpaired sources would help me understand the setup (Lines 46–50, 96–100, 105–107).

  • Applicability: Under what realistic institutional data-collection process would the i.i.d. model-increment assumption hold, and how much independent model history would be available (Lines 193–195, 1824–1827)? Given the high certified failure bounds and abstention in the historical backtest, in what deployment settings would the resulting contracts be useful (Lines 444–462)?

4 comments

Response to Reviewer 6yvL (Part 1/4)

We thank the reviewer for a careful reading and an accurate summary, and for finding the setup comprehensive, the separation between finite-sample and identification uncertainty conceptually valuable, and the related work useful. The summary states the key limitation of our experiments precisely; the revision now states it up front and adds the evidence it calls for (W2, Q3). Line numbers refer to the submitted version; section, appendix, table and theorem numbers refer to the revision.

W1 · Density of Sections 3–5. We agree. In the revision, five changes:

(i) A running example now accompanies Sections 3 and 4, across the data settings the reviewer mentions. Applicants advised to lower utilization either comply or substitute by raising income, and the next model rewards either utilization or income, so each model rejects exactly one of the two responses.

  • With unpaired marginals only, every failure rate from 0 to 1 is possible (Theorem 3.1), while independence gives 1/2.
  • Under a common shock the true rate is 0.68: a recorded environment identifies it (Proposition 3.4), while the dependence budget ι=H(E)\iota=H(E) gives no guarantee (Proposition 3.3).
  • If a share qq of applicants make a change that both models accept, the interval shrinks to [0,1−q][0,1-q].
  • In Section 4, the example shows why tolerance sets must cover whole update paths, and why RAC abstains when J↑=1J^{\uparrow} = 1.

(ii) Each main result is now followed by one sentence on what an institution can do with it; for example, after Theorem 4.5: calibrate on whole update paths, not single updates; after Proposition 4.7: a model budget γ\gamma needs about 3/γ3/\gamma independent update paths.

(iii) The introduction now opens with a concrete case (an applicant advised to cut the debt-to-income ratio by five points cuts it by three, while the lender retrains its model in a downturn), and the contribution summary is rewritten in plain words, each contribution stating what it means.

(iv) Strassen's condition is no longer used in the abstract or the introduction; it first appears right after Corollary 3.2, with its plain meaning: responses can be paired with future models so that every response meets a model that rejects it.

(v) Section 5 is reduced to its consequence for deployment, retitled “Which logs are needed”, and side results move to the appendix.

Response to Reviewer 6yvL (Part 2/4)

W2 · Evidence under genuine drift, and the i.i.d. assumption. We agree with the reviewer's reading.

The bootstrap study. The bootstrap paths measure estimation noise around known updates, so the two certified cells (0.77 and 0.98) test the pipeline under a correctly specified drift law, which Section 7 and Appendix D now call the oracle drift law; they are not evidence for certification at issuance. Under that law the eight uncertified cells have J↑≥0.879J^{\uparrow} \ge 0.879, so no dependence-robust contract below that level exists there at any sample size.

Genuine drift (new). We refit the classifier monthly on the previous 12 months of loans (37 models) and, at 17 issue dates in 2013–2015, calibrate RAC only on updates that had already happened, using non-overlapping windows of two monthly updates (consecutive windows share one endpoint model), under a protocol frozen before the run. Every contract RAC issued held: ROAR and Wachter in g1g_1 were certified at 0.90–0.97, against realized failure of 0.35–0.40. The levels are high because 17 windows allow only model budgets γ≥0.30\gamma \ge 0.30 (Proposition 4.7); Q3 gives the settings in which levels are useful.

The i.i.d. assumption. We agree that the 2008–2009 paths of the submitted backtest are not i.i.d., and our theory does not cover dependent histories. Their dependence does not explain the abstention, however. RAC abstained because those paths drift far more than the bootstrap paths around the 2014–2015 refits (median score 33.9 against 2.5) and are nearly copies of one another (correlation 0.97 between neighbors, 0.83 over all pairs): their two-year update windows all overlap, so a backtest restricted to non-overlapping paths has nd=1n_d = 1. With one path, RAC abstains by construction, and by Proposition 4.7(b) no distribution-free procedure that certifies with probability ω\omega can certify below 1−δ/ω1-\delta/\omega (about 0.94 at δ=0.05\delta = 0.05 and ω=0.9\omega = 0.9). Overlap could only have made certificates overconfident, and none was issued.

In the new backtest the windows do not overlap. Their scores, which is all the guarantee uses, show no trend (Spearman ∣ρ∣≤0.17|\rho|\le 0.17, p≥0.50p \ge 0.50) and no serial correlation, and no realized path is unusual for its history (conformal p≥0.20p \ge 0.20), although the updates themselves are mildly correlated between neighboring windows (0.27, against 0.08 over all pairs; a check added after the run). The data are therefore consistent with the assumption in the form the guarantee uses, although 17 windows cannot confirm it.

Response to Reviewer 6yvL (Part 3/4)

Q1 · Is the response kernel needed? No, and the revision removes it from the formulation. Sections 2–7 and Algorithm 1 use only Qg,σQ_{g,\sigma}, the law of the response record (X,A,T)(X,A,T) in a cell. Its role: Qg,σQ_{g,\sigma} is the joint law of XX (from context gg), AA (from Kσ(⋅∣X)K_\sigma(\cdot\mid X)) and TT, so KσK_\sigma is the part of Qg,σQ_{g,\sigma} that the recommendation acts on. Certification needs only Qg,σQ_{g,\sigma}; KσK_\sigma is needed only to compare two recommendations (leverage), so it is defined in Appendix A.3 with those results.

The rest of the setup is there because each part changes the answer:

  • realized responses: certificates that ignore them are violated in at least 96% of synthetic repetitions and understate realized risk in 7 of 10 LendingClub cells;
  • return times: per-update model sets, which ignore when applicants return, miss up to 0.157 against a target of 0.10 (Section 7, Q3);
  • non-return counted as failure: keeps the loss computable from records.

Q2 · What are the logs? Two separate tables, and no row of one refers to a row of the other; the new Table 1 shows one record from each.

  • Response log (the “available logs”): one row per rejected applicant who received randomized advice, with context gg, recommendation σ\sigma, features XX, the realized action AA and the return time TT (or no return within the horizon). For example, a near-miss applicant advised to cut the debt-to-income ratio from 31% to 26% cuts it to 28% and returns after one update. Randomization within each context makes the log identify Qg,σQ_{g,\sigma} (Assumption 4.2).
  • Model history: one row per past update path, the coefficient changes of the refits one and two updates after a past date. On LendingClub it holds either 200 bootstrap paths (the oracle study) or 19 paths from monthly origins in 2008–2009 (the backtest); the new backtest uses the windows of the 2013–2015 monthly refits.

The two sources are unpaired: each logged cohort meets only one realized model path, and the deployment cohort will meet a future path that neither table contains. On LendingClub the covariates and model updates are real; the responses and return times are simulated. In the revision: Assumptions 4.2 and 4.3 and Algorithm 1 use the names of Table 1.

Response to Reviewer 6yvL (Part 4/4)

Q3 · When is the i.i.d. assumption realistic, how much history is available, and where are the contracts useful?

When it is realistic. Updates can be close to i.i.d. when they are routine refits of a stable pipeline, driven by independent shocks, and the update windows of different paths do not overlap; histories can also be pooled across portfolios not driven by the same shock. What the guarantee needs is weaker: it uses past paths only through their scores, so it is the past scores and the deployment score that must be i.i.d. The assumption fails across regime changes: on LendingClub the 2016 update lies above the entire bootstrap distribution (Appendix D.10). Remaining mismatch is what the model-law budget εd\varepsilon_d prices. In the revision: Section 4 states this scope under Assumption 4.3.

How much history. Required: a model budget γ\gamma needs about 3/γ3/\gamma independent update paths when it is fixed in advance (Proposition 4.7), i.e. about 30 for γ=0.10\gamma = 0.10: five years of monthly refits of one portfolio, which add six non-overlapping two-update paths a year, and less when the histories of independent portfolios are pooled. Our experiments choose the budget from a grid of ten at a stricter error level, which needs about twice as many paths. Available: our 2013–2015 monthly refits gave at most 17 windows, enough only for γ≥0.30\gamma \ge 0.30 on that grid. Model history, not behavioral data, is therefore the bottleneck.

Where the contracts are useful. Contracts are useful in three settings:

  1. The institution commits on the model channel. Judging returning applicants, for the contract horizon, by the model that issued the advice needs no model history: on LendingClub RAC then certifies all ten cells (0.37–0.69; eight if applicants exactly on the old model's boundary count as failures), with ROAR and Wachter in g1g_1 at 0.42 and 0.37 instead of 0.77 and 0.98 under the oracle law. Its cost, under our yearly refits, is approving 9–30% of a cell whom the new model rejects, typically within 1–3 points of its predicted-repayment threshold; approving whenever either model accepts adds no rejection. A lighter commitment, capping how far updates may lower advised applicants' scores, certifies ROAR and Wachter in g1g_1 at 0.51 and 0.54, with no override under the 2013–2015 monthly refits (a check added after the run) and overrides for 5–18% of these applicants under yearly updates.
  2. Enough history exists, for example pooled across portfolios: under the oracle law, ROAR in g1g_1 is certified in every subsample from nd=30n_d = 30, and its level falls steadily as history grows, from 0.90 to 0.77 at nd=200n_d = 200 (Table 20).
  3. A shared environment is recorded in both sources (Proposition 3.4); in our synthetic experiments this was the tightest certificate valid at every shock intensity.

Outside these settings, only advice that leaves a margin above the decision boundary can be certified (here ROAR and Wachter), and only at high levels; RAC then serves as an audit, showing when the data support no guarantee.

We hope the revision, in particular the clearer Sections 3–5 and the new evidence under genuine drift, addresses the reviewer's concerns, and we would be grateful if the reviewer would consider raising the score.

Reviewer_vQvkOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies realized recourse when applicants do not follow recommendations exactly, and the decision model changes before they return. It combines behavioral and model history to certify failure risk under unknown dependence. The analysis covers certification limits and is evaluated using both a synthetic and a semi-synthetic datasets.

Critical strengths

a) The distinction between prescribed recourse and realized outcomes seems relevant.

b) The paper reports negative results and examines situations when its guarantees become uninformative.

Critical weaknesses

a) The problem is important, but I find the main contribution difficult to follow. The introduction moves from imperfect implementation and model changes to terms like coupling bounds, dependence budgets, certification floors, and recommendation leverage. I am unclear what constitutes the advance beyond reformulating recourse as a risk-certification problem?

b) I am not convinced about the methodological advance. The method combines established techniques. While the authors acknowledge this, the significance of their combination remains unclear. Additionally, Section 5 introduces an interpretive decomposition that does not appear to contribute to the RAC algorithm. Could the authors clarify their role?

c) The claim about predictive multiplicity needs to be checked and clarified. Corollary 3.2 requires the Hall–Strassen condition, which does not follow from predictive multiplicity alone. Could the authors clarify why Section 3 treats the two as equivalent?

d) Some positive results rely on future information. For example, the LendingClub bootstrap experiment uses future model updates. Could the authors clarify how this supports the claim about certification without future information?

Questions for authors

Please address the weaknesses.

5 comments

Response to Reviewer vQvk (Part 1/3)

We thank the reviewer for a clear review, and for recognizing the relevance of the distinction between prescribed and realized recourse and the value of reporting negative results. Points (c) and (d) are correct, and the paper is changed accordingly; for (a) and (b) we explain below what is new, and the revised paper now says it directly. Line numbers refer to the submitted version; section, appendix, table and theorem numbers refer to the revision.

(a) What is the advance beyond recasting recourse as risk certification? The recasting is only the starting point. Standard risk-certification methods need records that pair each response with the model it meets on return, and no such records exist: response logs and model history are unpaired. The guarantee must also hold at whatever time the applicant chooses to return. We contribute three results that the recasting does not imply, each with a measurable consequence:

  1. Identification. With unpaired data, the tightest guarantee valid under every dependence is the upper end J↑J^{\uparrow} of the identified interval, computable by max-flow (Theorem 3.1). On LendingClub (under the oracle drift law; see (d)), J↑J^{\uparrow} exceeds the independence value J⊗J_{\otimes} by 0.10–0.25 in every cell, so independence-based bounds, which lie below J↑J^{\uparrow} in 7 (BD) and 10 (EB) of 10 cells, claim levels that no dependence-robust procedure can support. Under our synthetic common shock they fail: BD in at least 99% of repetitions once s≥0.5s \ge 0.5.
  2. Return times. Because applicants choose when to return, a contract needs control of the whole model path, not of one update (Theorem 4.5). When return times are tilted toward atypical updates, per-update sets lose their coverage guarantee: at nd=1000n_d = 1000 they miss up to 0.157 against a nominal 0.10, while path-wise sets miss at most 0.075 (Section 7, Q3).
  3. A barrier. No distribution-free procedure that certifies with probability close to one can go below roughly log⁡(1/δ)/min⁡(N,nd)\log(1/\delta)/\min(N,n_d) (Proposition 4.7). Institutions have far fewer past model updates than behavioral records, so model history, not behavioral data, limits what can be certified; (d) shows this on real history.

The recasting itself also matters, because it certifies the realized response: BetaRCE-style certificates for the prescribed action understate realized risk in 7 of 10 LendingClub cells, by up to 0.29.

On presentation, we agree that the introduction used terms before explaining them. In the revision: the introduction no longer uses the four terms the reviewer lists, states each result in plain words, and gives the answer above in its own short paragraph; the abstract no longer says “certification floor”.

Response to Reviewer vQvk (Part 2/3)

(b) Established techniques, and the role of Section 5. We agree that the components are standard (lines 69–75; Section 6 of the revision). What is new is how they must be combined, and the combination is tight:

  • In the population it loses nothing: no guarantee valid for every coupling can lie below J↑J^{\uparrow}, and certificates built from sets of model paths reach it (Theorem 3.1(ii)).
  • In finite samples it is close to the best possible: with scarce model history it matches the 1/nd1/n_d rate of the floor that no distribution-free procedure can beat, up to a constant of about 1.3 when the model budget is fixed in advance; testing several budgets raises this constant only logarithmically in their number (Proposition 4.7; Appendix A.5).
  • Each part is needed: certificates that ignore realized behavior or assume independence are violated (Section 7, Q1; numbers in (a)), and per-update model sets lose their guarantee when return times depend on the response (Q3).

In the revision: Section 6 states this right after naming the standard components.

Section 5. The reviewer is right that RAC does not use the decomposition. Its role is to say which logs RAC needs, not how RAC computes: running RAC on the logs of another recommendation σ′\sigma' to certify σ\sigma requires a total-variation shift budget at least equal to their leverage, the difference in their success rates (Corollary A.11; Corollary 5.3 of the submission). In our synthetic study the total variation between response laws is 0.90–0.98, so no such transferred contract below τ≈0.9\tau\approx 0.9 exists: each recommendation an institution plans to issue must be randomized and logged itself. In the revision: the decomposition moves to the appendix, and Section 5 is reduced to this consequence, titled “Which logs are needed: recommendation leverage”.

(c) Hall–Strassen condition versus predictive multiplicity. We agree: the two are not equivalent, and Section 3 overstated the link. The condition is Corollary 3.2(ii): J↑=1J^{\uparrow} = 1 if and only if Q(BC)≥ν(C)Q(B_C)\ge\nu(C) for every set CC of model paths. Predictive multiplicity does not imply it.

What does hold is a new part (i), proved in Appendix B.2: for every set CC of model paths, the identified set of terminal risks has width at most Q(BC∖AC)+2ν(Cc)Q(B_C\setminus A_C)+2\nu(C^c). Here Q(BC∖AC)Q(B_C\setminus A_C) is the share of realized responses that some but not all models in CC reject: an analogue of the ambiguity of Marx et al. (2020), evaluated on realized responses rather than training points. It equals that ambiguity when the models in CC are near-optimal and include the deployed one, because a response is then in BC∖ACB_C\setminus A_C exactly when some model in CC disagrees with the deployed one.

In words: if all plausible future models accept or reject the same responses, the pairing hardly matters; only disagreement leaves room for an adverse pairing. Disagreement is therefore needed for a large dependence penalty J↑−J⊗J^{\uparrow}-J_{\otimes}, and the Hall–Strassen condition is its extreme case (unless failure is certain anyway), but disagreement does not imply it. Equally accurate models produce the extreme case when they weigh features differently, so that a response that substitutes one feature for another passes one model and fails the other; disjoint groups of failures are only the simplest such case.

LendingClub check (new): taking as future models 287 refits whose 2013 log-loss is within 0.5% of the issuing model's (AUC 0.632–0.647), the condition holds for AR, PROBE and RBR, whose advice stops at the decision boundary (J↑=1J^{\uparrow} = 1), but not for ROAR and Wachter in g1g_1, whose advice leaves a margin (J↑=0.51J^{\uparrow} = 0.51 and 0.58).

In the revision: Section 3 states this after Corollary 3.2; the sentences at lines 52–53, 57–58 and 131–133 are corrected; the introduction says that multiplicity “can, but need not” make the guarantee vacuous.

Response to Reviewer vQvk (Part 3/3)

(d) Positive results that use future information. The reviewer is correct: those results do not support certification without future information. The bootstrap paths resample the realized 2014 and 2015 refits, so they measure estimation noise around models that were not known at issuance. The submitted paper noted this (lines 456–458, Appendix D.6), but only after presenting the certified contracts.

In the revision: this study is called an oracle drift-law experiment, which tests the pipeline when the drift law is correctly specified, in Section 7 and throughout Appendix D, including the table captions. Section 7 first presents the evidence that uses only information available at issuance, from three sources:

  • History from another period. Calibrated on 19 monthly refits from 2008–2009, RAC abstains in every cell rather than certify a level the history cannot support: those paths drift about 14 times more than the bootstrap paths and are nearly copies of one another (correlation 0.97 between neighbors).
  • History from the same period (new). We refit the classifier monthly (37 models) and, at 17 issue dates in 2013–2015, calibrate RAC only on updates that had already happened (non-overlapping windows of two monthly updates; consecutive windows share one endpoint model), under a protocol frozen before the run. Every contract RAC issued held: ROAR and Wachter in g1g_1 were certified at 0.90–0.97, against realized failure of 0.35–0.40. The levels are high because 17 windows allow only model budgets γ≥0.30\gamma \ge 0.30 (Proposition 4.7): the barrier of (a), on real history.
  • Commitment to the issuing model (new). If returning applicants are judged, for the contract horizon, by the model that issued the advice, no information about future models is needed: the contract becomes an exact binomial bound computed from the institution's own logs. This certifies all ten cells (0.37–0.69; eight if applicants exactly on the old model's boundary count as failures), with ROAR and Wachter in g1g_1 at 0.42 and 0.37. Its cost, under our yearly 2014/2015 refits, is approving 9–30% of a cell whom the new model rejects, typically within 1–3 points of its predicted-repayment threshold; approving whenever either model accepts adds no rejection. A lighter commitment, capping how far updates may lower advised applicants' scores, certifies ROAR and Wachter in g1g_1 at 0.51 and 0.54, with no override under the 2013–2015 monthly refits (a check added after the run) and overrides for 5–18% of these applicants under yearly updates.

The abstract and introduction now state what can be certified without future information: with history from the same period the contracts hold, at high levels, and with the issuing-model commitment every cell can be certified.

We hope this addresses the reviewer's concerns, and we would be grateful if the reviewer would reconsider the score in light of the revision.

Reviewer_FPD1OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

In this paper, the authors propose a "recourse contract," which is an upper bound on the probability that a denied applicant still fails to obtain a desired outcome when they return after getting a recommendation. It accounts for instances when individuals partly comply with the recommendation, make alterations to the recommended changes, does not return or when the model updates. The authors argue that the two sources of uncertainty (how individuals respond to recommendations and how the model changes over time) are often learned from independent data sources. The authors show that in this limited regime, we can identify recourse failure only up to an interval whose upper bound is 1 (meaningless), builds a finite-sample certificate valid for any dependence structure, and proves a floor on the recourse contract given the number of past models. The authors conduct synthetic (and one semi-synthetic) experiments to demonstrate their theoretical results.

Critical strengths
  • I believe there is some novelty in discussing what happens with recourse when we assume some sort of dependence between behavioral responses and model updates.
Critical weaknesses

Clarity and Writing This paper is very difficult to read. It doesn't flow, and I found it hard (and painful) to parse all the notation. There is a lot of jargon that the authors neither introduce nor define, and it doesn't mean much to the reader. For example:

  • "path-wise model-history tolerance families" (line 63)
  • "covariate-dependent logging" (line 97)
  • "model-path miss" (line 240).

There are many other instances like this. Even "cell" is used in Definition 2.1 (line 88) before it is introduced (implicitly) as (g,σ)(g, \sigma) in Theorem 3.1. Then there are sentences like:

Robustness to the unknown coupling has a price, and that price can be total exactly under the predictive multiplicity that motivates robust recourse (line 52-53).

What does "price can be total" here mean? In general, I just had a hard time decoding what each sentence in the paper was trying to say.

Part of writing a paper is motivating the different/unique constructs that the paper introduces, and the paper does a poor job of this. Why do we need a tolerance family (Definition 4.1)? Why is recommendation leverage (Section 5) an important quantity? In each case, the construct is introduced and the paper immediately moves on to results about it.

Motivation The motivation in this paper is weak. I can see that the authors are pointing to a limitation of the current literature, which focuses on providing "robust" recourse for the prescribed action rather than the realized response under a potentially different model.

An institution that issues advice is, however, accountable for whether that advice still works in deployment (line 40-41).

Is this true? Algorithmic recourse is very much a policy motivated problem. A policy that would require institutions to provide recourse under the realized response (e.g., partial compliance) is a strong one. In fact, in most countries, institutions aren't even required to provide a specific prescription. Consumer protection laws (e.g., ECOA in the US, Right to an Explanation in the EU AI Act) requires a list of factors (an explanation).

Besides, shouldn't one expect that recourse (given by any model) should fail if one does not follow the prescribed action (regardless of "model drift")? Note that this is different to a situation where the prescribed action is infeasible (like in [1]).

Model Trajectory Assumption I am not convinced by the "model trajectory" assumption. Assumption 4.3 treats past increment paths as i.i.d. draws from the same law as the incremental changes to the model during deployment. In practice, model updates are driven by factors like shift in training distribution, or policy changes. In fact, wasn't the effect of a change in "environment" like macroeconomic conditions one of the main motivations for this work? Also, doesn't the backtest in Section 7 (lines 456-461) challenge this assumption? (i.e., using only the history available at issuance, path scores are 14 times larger)

Significance of Experimental Results After reading the experiments, I am left asking: so what? What would a practitioner take away from this? There is no practical takeaway here. Consider this conclusion/comment in the paper:

"In practice, then, model history rather than behavioral data limits what can be certified" (line 461-462)

I would have liked to see further discussion on this point. What are some of the implications?

Citations The predictive multiplicity citation is incorrect. Predictive multiplicity was introduced by Marx et al. (2020) [2], not Pawelczyk et al. (2020) or Black et al. (2021).


[1] Kothari, Avni, Bogdan Kulynych, Tsui-Wei Weng and Berk Ustun. "Prediction without Preclusion: Recourse Verification with Reachable Sets." ICLR 2024.

[2] Marx, Charles, Flavio Calmon, and Berk Ustun. "Predictive multiplicity in classification." ICML 2020.

Questions for authors
  • Is tˉ\bar t a parameter? (line 83) If so, who chooses it, and how should it be set?
  • What does "covariate-dependent logging" mean? (line 97)
  • How exactly does Strassen's condition in Corollary 3.2 match predictive multiplicity? Line 131 claims that predictive multiplicity "is exactly its condition," but the corollary is about mm equally likely future models that fail disjoint groups of responses. Why would models in a Rashomon set fail on disjoint groups of responses?
  • How should we think about the environment EE? Is it something an institution can observe and record in practice? What would EE be in the LendingClub setting?
  • Why is ϵ=0\epsilon = 0 in the experiments?
5 comments

Response to Reviewer FPD1 (Part 1/5)

We thank the reviewer for a detailed review and for noting the novelty of studying dependence between behavioral responses and model updates. Line numbers refer to the submitted version; section, appendix, table and theorem numbers refer to the revision.

W1 · Clarity and notation. We agree. Each term the reviewer lists is now removed or defined at first use:

  • “path-wise model-history tolerance families”: no longer used;
  • “covariate-dependent logging”: defined in Section 2 (see Q2);
  • “model-path miss”: replaced by the miss mass, the probability that the future model path leaves the calibrated set;
  • “cell”: a pair (g,σ)(g,\sigma) of a context and a recommendation, now defined before Definition 2.1;
  • “the price can be total” (lines 52–53): a guarantee valid under every possible dependence can have failure rate 1, i.e. be no guarantee; the sentence is rewritten and its multiplicity claim corrected (Q3).

Why a tolerance family? Theorem 3.1(i) bounds the risk through any set CC of model paths, at the cost ν(Cc)\nu(C^c) of the paths it leaves out. A tolerance family is a nested collection of such sets, fixed in advance, from which the model history selects one with a PAC bound on ν(Cc)\nu(C^c) (Theorem 4.5). The sets contain whole update paths, not single models, because applicants return at times they choose; per-update sets lose their guarantee there (Section 7, Q3).

Why recommendation leverage? Leverage is the difference in realized success between two recommendations. It matters through one consequence: under a total-variation shift budget, logs of one recommendation certify another only at a cost at least equal to their leverage (Corollary A.11; Corollary 5.3 of the submission), so each recommendation must be logged under randomization.

In the revision: other terms are explained at first use; Section 4 opens with a four-step overview of the procedure; Section 5 keeps only the leverage consequence above, and the other leverage results move to the appendix.

W2 · Motivation. (a) Accountability (lines 40–41). We agree: rules such as ECOA's require the reasons for a denial, not a prescription, and the introduction overstated this premise. In the revision: the premise is dropped. The contract is motivated by the institution's own interest: failed advice either loses a potential customer or, if the applicant is approved anyway, lowers the institution's standards. A contract is stated as a guarantee an institution can choose to offer or audit, not a legal requirement. Because σ\sigma can be any advice policy, the same contract can audit existing recourse generators or guidance attached to stated denial reasons.

(b) Should recourse not fail anyway when the action is not followed? Not necessarily: the relation runs both ways, which is why we certify the realized response. In our semi-synthetic LendingClub data (responses are simulated; Appendix D.3):

  • under ROAR in g1g_1, only 45.6% of recipients comply fully, yet 80.4% of realized post-action states are accepted by the current model (Table 16): ROAR's advice leaves a margin, so most partial compliers still cross the decision boundary;
  • conversely, even if every recipient carried out the prescription exactly, the failure rate would remain 0.26–0.76 across cells (Table 17, computed under independence).

As full compliance is only 39–49%, a guarantee for exact compliers alone would miss most recipients. Unlike infeasible actions (Kothari et al., 2024), here the action is feasible but is not taken as prescribed. In the revision: Section 7 reports these numbers and this conclusion, and Kothari et al. (2024) is cited with this distinction.

Response to Reviewer FPD1 (Part 2/5)

W3 · Model-trajectory assumption. We agree that the assumption must be tested, not only stated. We answer the reviewer's three concerns in turn.

What the assumption covers. Macroeconomic shocks motivate dependence between the two channels, and RAC is valid under every such dependence: Assumption 4.3 leaves the dependence between deployment responses and the deployment path unrestricted (lines 194–195). It restricts only the law of model updates: future update paths must follow the same law as past ones, in their scores, which is all the guarantee uses. Shocks are therefore covered if the history contains them at the rate they occur in deployment; a regime the history has never seen, or a shift in the training distribution or a policy change that alters the law of updates, is not. A budget εd\varepsilon_d prices such a mismatch: if the law of the path score shifts by at most εd\varepsilon_d in Kolmogorov distance, Theorem 4.6 holds with τ=η+ε+γ+εd\tau=\eta+\varepsilon+\gamma+\varepsilon_d.

Does the backtest challenge it? Yes: the backtest shows that history from another period can violate Assumption 4.3. It calibrated on 19 monthly origins in 2008–2009 to cover updates in 2014–2015. These paths drift 14 times more than the bootstrap paths around the 2014–2015 refits and are nearly copies of one another (correlation 0.97 between neighbors), so they amount to about one path. RAC therefore abstains in every cell, whereas a bootstrap calibration would have been overconfident (the path one year later scores 13.97 against a bootstrap radius of 3.70).

New test with history from the same period. We refit the classifier monthly on the previous 12 months of loans (37 models). At 17 issue dates in 2013–2015, RAC is calibrated only on updates that had already happened (non-overlapping windows of two monthly updates; consecutive windows share one endpoint model), under a protocol frozen before the run.

  • The path scores show no trend (Spearman ∣ρ∣≤0.17|\rho|\le 0.17, p≥0.50p \ge 0.50) and no serial correlation, and no realized path is unusual for its history (conformal p≥0.20p \ge 0.20). The updates themselves are mildly correlated between neighboring windows (0.27, against 0.08 over all pairs; a check added after the run).
  • Every contract RAC issued held: ROAR and Wachter in g1g_1 were certified at 0.90–0.97, against realized failure of 0.35–0.40.
  • The levels are high because 17 windows allow only model budgets γ≥0.30\gamma \ge 0.30 (Proposition 4.7); W4 shows how to lower them.

New test when the assumption fails. In our synthetic environment, increments 1.5 times larger raise the model miss at γ=0.10\gamma = 0.10 to 0.62 (0.069 when the assumption holds), yet contracts fail only once the deployment risk itself exceeds the certified level. A simple check of whether the latest paths in the history score higher than the rest flagged every gradual amplification or tightening of updates, while its flag rate otherwise stayed close to the test's nominal 5% level (2% with no change, 6.5–8% for harmless changes); a flag costs only an unneeded abstention or recalibration, and abstaining or recalibrating on a flag left no contract violated. An abrupt change that leaves no trace in the history cannot be detected from history; εd\varepsilon_d states how much of it a contract tolerates.

In the revision: Section 4 states this scope and where the assumption is plausible (routine refits of a stable pipeline, or histories pooled across portfolios whose updates are not driven by the same shock); Section 7 presents both backtests with the oracle study; new appendix sections give the details and the violation study.

Response to Reviewer FPD1 (Part 3/5)

W4 · What should a practitioner take away? We agree that the implications were left implicit. In the revision, Section 7 ends with four takeaways, with new LendingClub results:

  1. Certify the realized response, and assume independence only where it is credible. BetaRCE-style certificates for the prescribed action understate realized risk in 7 of 10 LendingClub cells, by up to 0.29. Under our synthetic common shock, independence-based certificates fail: BD in at least 99% of repetitions once s≥0.5s \ge 0.5, EB in 77% at s=1s = 1.
  2. Model history, not behavioral data, limits what can be certified. With 5,000 logged units per cell the behavioral floor is 0.0016 (Appendix C.5), while no distribution-free procedure that is valid at δ=0.10\delta = 0.10 and certifies with probability close to one can go below 0.21 with 10 independent update paths, or below 0.074 with 30 (Proposition 4.7).
  3. The levers are therefore on the model channel.
    • The strongest is to judge returning applicants, for the contract horizon, by the model that issued the advice. The model channel then drops out, and the contract becomes an exact binomial bound from the institution's own logs. On LendingClub this certifies all ten cells instead of two (0.37–0.69; eight if applicants exactly on the old model's boundary count as failures), with ROAR and Wachter in g1g_1 at 0.42 and 0.37 instead of 0.77 and 0.98 under the oracle law. Its cost, under our yearly refits, is approving 9–30% of a cell whom the new model rejects, typically within 1–3 points of its predicted-repayment threshold; approving whenever either model accepts adds no rejection.
    • A lighter commitment caps how far updates may lower advised applicants' scores. It certifies ROAR and Wachter in g1g_1 at 0.51 and 0.54, with no override under the 2013–2015 monthly refits (a check added after the run) and overrides for 5–18% of these applicants under yearly updates.
    • Pooling update histories across portfolios adds paths.
  4. Without a commitment, only advice that leaves a margin above the decision boundary can be certified (here ROAR and Wachter), and only at high levels; with the issuing-model commitment, every cell can. When no lever is available, abstention is the informative output: it tells the institution that its data support no guarantee.

W5 · Citation. Thank you. The introduction now credits the notion of predictive multiplicity to Marx et al. (2020), as do Section 3 and Appendices B.2 and D.9; Pawelczyk et al. (2020), Black et al. (2021) and Turbal et al. (2025) are cited only as work on recourse under multiplicity and model instability.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.