acceptodds
Under review as a conference paper at ICLR 2027

Disagreement-Adaptive Safe Policy Updating under Protected Subgroup Constraints

Abstract

Safe policy improvement from offline data seeks to improve upon an incumbent policy while satisfying prespecified safety constraints. Existing work has studied high-confidence policy improvement under multiple fairness or safety constraints and disagreement-aware policy comparison, while it remains unclear whether candidate–incumbent disagreement can sharpen finite-sample certification across protected subgroups. To address this gap, we study safe policy updating when candidate policies may differ from the incumbent only on a small fraction of each evaluation population. We show that direct estimation of candidate–incumbent value differences yields simultaneous confidence bounds whose leading width scales as , where is the disagreement probability and is the audit sample size, and establish a protected-subgroup lower bound together with a local minimax result showing that this dependence cannot be uniformly improved near a binding subgroup constraint. We then develop DiSPU, a diagreement-adaptive framework for safe policy updating (DiSPU) that incorporates these confidence bounds into a constrained deployment optimization, and prove high-probability safety and disagreement-dependent oracle-regret guarantees. Extensive experimental results confirm that exploiting policy disagreement reduces certification conservatism and enables larger certified improvements while maintaining protected-subgroup safety.

Primary area:
causal reasoning
Keywords:
Safe policy updating, Policy disagreement, Subgroup constraints

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_uC5YOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies offline safe policy improvement under two requirements. A candidate update must not reduce overall value relative to an incumbent policy, and it must not degrade any of several prespecified protected subgroups by more than a tolerance Δs\Delta_s.

DiSPU works in three steps:

  1. It estimates each candidate–incumbent value difference directly with a paired doubly robust score. The score is exactly zero wherever the two policies agree.
  2. It builds simultaneous empirical-Bernstein lower bounds over all (population, candidate) pairs.
  3. It solves an LP over mixtures of the incumbent and the candidates using these lower bounds. The theory has four parts:
  • Simultaneous validity of the bounds (Thm. 1).
  • A variance bound: the empirical variance is at most L2p^L^2 \hat p, so the radius scales as p/n\sqrt{p/n} (Prop. 1, Cor. 1).
  • A two-point lower bound: a subgroup effect of order p/n\sqrt{p/n} cannot be reliably sign-identified (Thm. 2, Cor. 4).
  • High-probability safety and oracle-regret bounds for the LP solution (Thm. 3, Cors. 2–3). App. B extends the analysis to estimated propensities, assuming an external bound on the nuisance remainder.

Experiments use a synthetic binary-action environment and an ACS-based semi-synthetic benchmark. DiSPU is compared with RobinHood and HCPI, each run with its original IS estimator and with the paired DR estimator, plus two ablations.

Critical strengths

1. The theory is correct and carefully done. I checked every proof in Appendices A and B:

  • the empirical-Bernstein rescaling and union bound (A.1);

  • the variance identity (A.2);

  • the Bernstein step and constants (A.3);

  • the KL/Pinsker computation and Bernoulli parameter ranges (A.4);

  • the LP sandwich arguments (A.5–A.7);

  • the DR remainder (B). The proofs handle details that are often skipped:

  • They condition properly on the training σ-field.

  • They note that eq. (39) holds uniformly in θ\theta, so the data-dependent θ^\hat\theta is covered.

  • App. B states plainly that product-rate conditions do not by themselves give a finite-sample certificate. Thm. 2 is a clean construction that pins down the p/n\sqrt{p/n} resolution at which a subgroup effect can be certified.

2. The problem is well motivated, and the method is simple to deploy. Deployment needs one pass of paired scores and one LP, and the incumbent is always feasible. The Empirical-DR-LP ablation (Fig. 2) shows concretely why the confidence adjustment matters. The authors are also upfront that DiSPU is more conservative than the baselines when audit data are limited.

Critical weaknesses

1. The technical contribution is incremental, and the optimality claims are stronger than what is proved.

The mechanism is not new. The paper builds on a paired DR difference estimator whose contribution vanishes on the agreement region. Cho et al. (2025, CSPI-MT), which the paper cites, already use this estimator for certification. Narang et al. (2024) use difference estimation to reduce sample complexity.

Given that estimator, the results are standard assemblies:

  • Thm. 1 is Maurer–Pontil plus a union bound.
  • Prop. 1 is a two-line deterministic bound.
  • Cor. 1 is Bernstein's inequality applied to p^\hat p.
  • Thm. 3 and Cors. 2–3 are the usual LP sandwich argument.
  • Moving from one comparison to M∣S∣M|S| comparisons is a union bound. I do not see a new technique.

The lower-bound side is framed more strongly than it supports.

  • Cor. 4's matching upper bound comes from a trivial rule. It is attained by always deploying the incumbent, not by DiSPU. Regret is trivially at most W∗=ΓW^* = \Gamma. The Θ(p/n)\Theta(\sqrt{p/n}) rate appears only because Γ\Gamma is set to δn=132p/n\delta_n = \tfrac{1}{32}\sqrt{p/n}.
  • For larger Γ\Gamma the rate disappears. Thm. 2 allows Γ\Gamma up to p/16p/16, and there the lower bound is 58Γ\tfrac{5}{8}\Gamma, which does not shrink with nn. So "a Θ(p/n)\Theta(\sqrt{p/n}) regret rate near a binding subgroup constraint" (abstract, Sec. 5.2, Conclusion) describes this particular two-point family. It does not show that DiSPU is minimax optimal.
  • The upper and lower bounds cover different regimes. Thm. 2 is stated for zero tolerance Δ=0\Delta = 0. At Δ=0\Delta = 0, the second part of Cor. 2/Cor. 3 is vacuous (ρ∗=0\rho^* = 0). The first part requires the oracle to lie away from the boundary. So in the regime of the lower bound, the paper gives no nontrivial upper bound for DiSPU. What Thm. 2 does show is that the certification resolution is p/n\sqrt{p/n}, which matches DiSPU's radius in (p,n)(p, n) for fixed (B,κ)(B, \kappa). Even that needs a qualification. L=2B(1+κ−1)L = 2B(1+\kappa^{-1}) is hidden in eq. (6), and Prop. 1 bounds σ^2\hat\sigma^2 by L2p^∼B2p^/κ2L^2 \hat p \sim B^2 \hat p / \kappa^2. The actual variance on the disagreement region is of order B2p/κB^2 p/\kappa. The construction fixes κ=1/2\kappa = 1/2, so "cannot be improved beyond logarithmic factors" should be restricted to the dependence on pp and nn.

2. The experiments do not isolate the claimed mechanism, and the safety evaluation is incomplete.

(a) The gains appear to come from mixing, not from disagreement adaptivity.

RobinHood-DR and HCPI-DR already use the same paired DR estimator, so they also get the p\sqrt{p} variance reduction. Two things separate DiSPU from them:

  • (i) It uses empirical-Bernstein instead of Student-t bounds. If anything, this should make DiSPU more conservative.

  • (ii) It uses a mixture LP instead of a single selected candidate. Table 1 points to (ii) as the source of the gains:

  • DiSPU's gains (0.33, 0.66, 0.99, 1.32) and margins (0.84, 1.68, 2.52, 3.36) are exactly proportional to Δ\Delta, and so are their standard deviations.

  • This is the pattern you get when the LP places weight θ∝Δ\theta \propto \Delta on one candidate whose subgroup lower bound is negative. In other words, it spends the subgroup budget by randomizing in a subgroup-harming candidate.

  • At Δ=0.02\Delta = 0.02, the realized degradation of the protected group is 0.02−0.0084=0.01160.02 - 0.0084 = 0.0116 for DiSPU. It is about 0.0033 for RobinHood-DR and 0.0004 for HCPI-DR. That behavior is allowed by the problem definition. But it means the headline result is "mixtures use the tolerance budget more fully," not "disagreement-adaptive certification is less conservative."

To separate the two, I would want:

  • a single-candidate version of DiSPU;
  • mixture versions of the baselines;
  • CSPI-MT as an additional baseline. Plots of gain against realized subgroup degradation (a Pareto view) would also be fairer than comparing gain at a fixed Δ\Delta.

(b) The claimed leading term is not the leading term in the experiments.

The synthetic setting has B=1/2B = 1/2, κ=1/2\kappa = 1/2, M=16M = 16, ∣S∣=7|S| = 7, α=0.05\alpha = 0.05. That gives:

  • L=3L = 3;

  • ℓα=log⁡(17,920)≈9.79\ell_\alpha = \log(17{,}920) \approx 9.79;

  • a second term in eq. (3) of 14Lℓα/(3(ns−1))≈137/(ns−1)14L\ell_\alpha / (3(n_s - 1)) \approx 137/(n_s - 1). Evaluating that term:

  • At naud=10,000n_{aud} = 10{,}000 it is about 0.0137 for the overall population. That is already above the largest gains in Fig. 1 (about 0.012).

  • For a pairwise-intersection subgroup (ns≈1,000n_s \approx 1{,}000) it is about 0.137. This explains the negligible gains at small naudn_{aud}. It also means the p/n\sqrt{p/n} term becomes comparable for subgroups only around naud≈200,000n_{aud} \approx 200{,}000.

A tighter variance-adaptive bound would keep the p/n\sqrt{p/n} story and might fix the small-sample regime. Betting-based intervals, as in Karampatziakis et al. (2021), which the paper cites, are one option.

(c) Safety is reported as mean margins, but the guarantee is probabilistic.

Definition 1 bounds the probability of violation. Figs. 1–2 and Table 1 report average margins instead, and the paper does not state the number of replications or what "±" means. A mean margin above zero does not show Pr⁡(violation)≤α\Pr(\text{violation}) \le \alpha. This matters most for the Student-t baselines, which have no finite-sample guarantee. Per-method violation frequencies across replications should be reported.

(d) The evaluation is narrow for "extensive" results.

  • There are only two environments.
  • Both use binary actions, although the theory is stated for KK actions.
  • Both use known propensities e=1/2e = 1/2, so App. B is never exercised.
  • Sec. 6.3 is titled "Real-World Datasets," but actions and outcomes are simulated.
  • By construction (App. C.1), only G2∩G3G_2 \cap G_3 is harmed, so most of the six subgroup constraints are probably slack.
Questions for authors
  1. How much of the advantage comes from mixing? How much of DiSPU's advantage remains if the LP is restricted to vertices (a single candidate or the incumbent)? Conversely, how do RobinHood-DR and HCPI-DR perform when allowed to mix? Please report the selected θ^\hat\theta behind Table 1: which candidates, with what weights.
  2. How often is safety actually violated? Across replications, how often does each method violate a subgroup constraint or overall non-degradation? How many replications are behind Fig. 1 and Table 1? Is "±" a standard deviation or a standard error?
  3. How does DiSPU compare with CSPI-MT? Cho et al. (2025) also certify improvements using paired DR differences and multiple testing.
  4. Is the deployed procedure really (1−α)(1-\alpha)-safe, or (1−α/2)(1-\alpha/2)-safe? The algorithm uses ℓα=log⁡(8N/α)\ell_\alpha = \log(8N/\alpha), so the event in Thm. 1 has probability 1−α/21 - \alpha/2. The remaining α/2\alpha/2 is used only for the event EpE_p in the analysis (Cor. 1). App. B uses log⁡(4N/αaud)\log(4N/\alpha_{aud}), which seems to be the right choice for the algorithm itself.
  5. Which covariates can the semi-synthetic candidates use? If they include AGEP and RAC1P, a candidate could avoid V=1V = 1 directly. Which subgroup constraints are active in the LP?
  6. What is DiSPU's own regret on the Thm. 2 family? For Cor. 4, can you state that regret, and say explicitly that the Θ(p/n)\Theta(\sqrt{p/n}) rate holds only for Γ=δn\Gamma = \delta_n?
6 comments
AuthorsOpenReview ↗

Response to Reviewer uC5Y (Part 1)

Dear Reviewer uC5Y.

Thank you for examining the proofs carefully and recognizing the problem's motivation and the method's simplicity! We address your concerns about the contribution, sources of empirical gains, safety reporting, and regret guarantees below.

W1(a)W1 (a)

DiSPU's contribution beyond existing tools

To the best of our knowledge, DiSPU is the first framework to optimize policy deployment under protected-subgroup constraints using disagreement-adaptive simultaneous confidence bounds, with finite-sample safety guarantees and an analysis of how subgroup uncertainty limits safely deployable improvement.

GR Q1 details the distinctions between our work and RobinHood Metevieretal,˙2019Metevier et al\., 2019 and CSPI-MT Choetal,˙2025Cho et al\., 2025.

W1(b),Q6W1 (b), Q6

What is DiSPU’s regret on the Theorem 2 family, and does the Θ(p/n)\Theta(\sqrt{p/n}) rate in Corollary 4 hold only for Γ=δn\Gamma = \delta_n?

On the Theorem 2 family, DiSPU’s regret is Θ(Γ)\Theta(\Gamma), so the Θ(p/n)\Theta(\sqrt{p/n}) rate in Corollary 4 holds only at Γ=δn\Gamma = \delta_n. To remove this restriction, we proved a regret upper bound for DiSPU’s own LP on a revised family with fixed positive overall gain and subgroup tolerance, and this bound matches the leading lower-bound rate.

1. On the Theorem 2 family, DiSPU’s regret lies between 58Γ\frac{5}{8}\Gamma and Γ\Gamma, so it reduces to Θ(p/n)\Theta(\sqrt{p/n}) only at the boundary scale Γ=δn\Gamma = \delta_n.

DiSPU is (1−α)(1-\alpha)-safe under both instances (Theorem 3), so the lower bound of Theorem 2 applies to it. Since λ^∈[0,1]\hat\lambda \in [0,1], its regret is also at most Γ\Gamma: 58Γ;≤;sup⁡P∈{P−,P+}EP[WP∗−D0,P(λ^DiSPU)];≤;Γ.\frac{5}{8}\Gamma \\;\le\\; \sup_{P\in\lbrace P_-,P_+\rbrace} \mathbb{E}_P\big[W_P^* - D_{0,P}(\hat\lambda^{\mathrm{DiSPU}})\big] \\;\le\\; \Gamma. Setting Γ=δn=132p/n\Gamma = \delta_n = \frac{1}{32}\sqrt{p/n} gives the bounds 5256p/n\frac{5}{256}\sqrt{p/n} and 132p/n\frac{1}{32}\sqrt{p/n} stated in Corollary 4. For larger Γ\Gamma, the lower bound 58Γ\frac{5}{8}\Gamma does not shrink with nn, as you noted.

2. On the revised family, DiSPU’s regret is of order ΓΔplog⁡(1/α)n\frac{\Gamma}{\Delta}\sqrt{\frac{p\log(1/\alpha)}{n}} for any fixed Γ>0\Gamma > 0, matching the lower bound without requiring Γ=δn\Gamma = \delta_n.

As detailed in GR Q2, the construction fixes Γ>0\Gamma > 0 and Δ>0\Delta > 0, so always deploying the incumbent incurs regret of order Γ\Gamma. It gives a lower bound for every uniformly (1−α)(1-\alpha)-safe procedure and an upper bound for DiSPU’s confidence-adjusted LP. For fixed positive pp, Γ\Gamma, and Δ\Delta, and fixed outcome and overlap bounds, both have leading dependence ΓΔplog⁡(1/α)n\frac{\Gamma}{\Delta}\sqrt{\frac{p\log(1/\alpha)}{n}}, and the remaining terms are lower order when log⁡(1/α)=o(n)\log(1/\alpha) = o(n). As in Theorem 2, the outcome bound BB and overlap constant κ\kappa are fixed, so the matching dependence and the tightness of the disagreement dependence are stated in terms of pp and nn.

Thus, while the rate in the original Corollary 4 holds only at Γ=δn\Gamma = \delta_n, the strengthened Corollary 4 shows that DiSPU’s own LP attains the matching leading regret rate for any fixed positive overall gain and subgroup tolerance.

AuthorsOpenReview ↗

Response to Reviewer uC5Y (Part 2)

W2(a),Q1W2(a), Q1

Does DiSPU’s advantage come from mixing instead of disagreement adaptivity? Does DiSPU outperform the baselines only because it is the only method that deploys mixtures?

The ablation in Section 6.2 confirms the role of disagreement-adaptive paired certification in reducing conservatism. Furthermore, our RobinHood-DR and HCPI-DR implementations also optimize mixtures, so mixing itself does not give DiSPU an advantage over the baselines.

1. With the same mixture LP, replacing paired certification with separate-value bounds reduces the certified gains to negligible levels.

Paired-DR-EB-LP (DiSPU) and Separate-DR-EB-LP share the empirical-Bernstein construction, the candidate library, and the deployment LP. They differ only in whether the confidence bounds are constructed directly for the candidate–incumbent value difference or separately for the two policy values. Agreement regions contribute exactly zero to the paired score, so only the paired radius adapts to the disagreement probability.

In Figure 2, Separate-DR-EB-LP yields negligible overall gains at every tolerance, and its large safety margins indicate overly conservative deployment. DiSPU’s gains increase with the tolerance, and its reported safety margins remain positive under positive tolerances. Mixing is available to both variants, so this gap reflects reduced conservatism from paired certification.

2. RobinHood-DR and HCPI-DR also optimize mixtures over the candidate library and the incumbent, and differ from DiSPU in confidence construction and selection procedure.

RobinHood-DR uses inflated Student- tt bounds during selection to anticipate a subsequent independent safety test. HCPI-DR uses uninflated Student- tt bounds during selection and fixes its mixture before independent auditing. DiSPU uses empirical-Bernstein bounds that hold simultaneously over all candidates and evaluation populations.

Thus, the ablation supports the value of paired certification with mixing held fixed, while the full-method comparison reflects differences in confidence construction, not in the use of mixing.

AuthorsOpenReview ↗

Response to Reviewer uC5Y (Part 3)

W2(b)W2(b)

Is the p/n\sqrt{p/n} term, which should drive the confidence radius, masked by the additive correction at the experimental audit budgets?

To examine the role of the p/n\sqrt{p/n} term, we conducted a controlled radius-decomposition experiment. This term dominates the radius from moderate audit budgets onward and enables certification that separate-value bounds cannot achieve.

1. The experiment retains the original total audit-budget range and varies candidate disagreement.

We use total audit budgets from 10,000 to 200,000, retaining B=κ=1/2B=\kappa=1/2, L=3L=3, M=16M=16, and α=0.05\alpha=0.05. The evaluation populations are the overall population and two protected groups, each comprising 50% of the population. Thus, ∣S∣=3|\mathcal S|=3 and ℓα≈8.95\ell_\alpha\approx8.95. Subgroup samples are obtained by filtering one shared i.i.d. audit stream.

The 16 fixed candidates combine four policy directions with disagreement probabilities p∈0.02,0.05,0.10,0.20p\in{0.02,0.05,0.10,0.20}. Results are averaged over 2,000 independent audit repetitions and the four directions.

2. The adaptive term becomes the larger protected-group contribution from a total audit budget of 25,000 onward.

We decompose the full radius as csj=Asj+Fsc_{sj}=A_{sj}+F_s, where Asj=2σ^sj2ℓαnsA_{sj}=\sqrt{\frac{2\widehat\sigma_{sj}^2\ell_\alpha}{n_s}} and Fs=14Lℓα3(ns−1)F_s=\frac{14L\ell_\alpha}{3(n_s-1)}.

Table A. Protected-group confidence-radius decomposition at p=0.10p=0.10.

Total audit sizeAdaptive term AAAdditive term FFAdaptive share A/(A+F)A/(A+F)
10,0000.0188310.02505742.90%
25,0000.0119090.01002054.31%
50,0000.0084210.00501062.70%
100,0000.0059550.00250570.39%
200,0000.0042110.00125277.07%

In this setting, the additive term is larger at a total budget of 10,000, while the adaptive term is larger from 25,000 onward.

3. The p/n\sqrt{p/n} term also determines certification outcomes: the paired radius grows with disagreement while the separate-value radius does not, so paired bounds certify low-disagreement updates that separate-value bounds reject.

We compare paired doubly robust DRDR certification with empirical-Bernstein bounds constructed separately for the candidate and incumbent DR values. Both procedures use the same observations and candidates. At zero tolerance, certification requires nonnegative candidate lower confidence bounds for the overall population and both protected groups simultaneously.

Table B. Protected-group radii and simultaneous certification rates at a total audit size of 200,000.

Disagreement ppPaired radiusSeparate radiusPaired certification rateSeparate certification rate
0.020.0031420.01982697.26%0.00%
0.050.0042370.019850100.00%0.00%
0.10.0054630.019870100.00%46.94%
0.20.0071800.019948100.00%100.00%

The separate-value radius stays near 0.020 for every pp, while the paired radius grows with pp. At p=0.02p = 0.02, paired certification reduces the full protected-group radius by 84.15% and certifies beneficial updates in 97.26% of comparisons. Separate-value certification certifies none.

Thus, the additive correction does not mask the disagreement-adaptive p/n\sqrt{p/n} term. This term dominates the protected-group radius and is the key driver of DiSPU’s certification gains over separate-value bounds.

Reviewer_3x5iOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies safe policy updating from logged data with known propensities. A new deployment must not degrade the overall population, and each prespecified protected subgroup may lose at most a given tolerance relative to the incumbent. DiSPU estimates candidate-minus-incumbent value differences with a paired doubly robust score that is zero wherever the two policies agree. It then builds simultaneous empirical Bernstein lower bounds, and finally chooses a mixture of the incumbent and the candidates by solving a linear program over these bounds. The theory is quite extensive covering simultaneous validity, high-probability safety, oracle regret under slack conditions, and a two-point lower bound near a binding subgroup constraint. Experiments on a synthetic environment and an ACSIncome-based benchmark compare DiSPU with other SOTA methods.

Critical strengths
  1. The formulation is clean and well motivated. Overall gains that hide losses for protected subgroups are a real concern in high-stakes deployments. I checked the main proofs (simultaneous validity, the variance bound, safety, and the two-point construction), and they hold.
  2. The evaluation isolates the role of each component. All metrics use true policy values, and the ablations remove one piece at a time for the pairing and confidence radius. They show clearly that bounding the paired difference is far less conservative than bounding the two values separately.
  3. The paper is clearly written. Definitions are precise and the algorithm is simple to implement. The proofs are easy to follow.
Critical weaknesses
  1. The main ingredients already appear in prior work. The paired score with zero contribution on agreement already appears in Cho et al. (2025). The square-root dependence on disagreement follows from that zero plus any variance-adaptive interval. In fact, the RobinHood-DR baseline, which plugs the same paired score into Student-t bounds, already has subgroup-specific, disagreement-adaptive widths. The tools are standard with Maurer-Pontil, LP sandwich argument, and two-point lower bound. It would help to state precisely what is new beyond combining these, since the abstract presents disagreement adaptivity across subgroups as the gap being filled.
  2. The local minimax result does not show that DiSPU attains the rate. In Corollary 4, the matching upper bound is attained by the rule that always deploys the incumbent, because Γ\Gamma is set at the boundary scale. So the result describes how hard the two-point family is, but it does not show that DiSPU attains the rate. In that zero-tolerance regime, DISPU's own bound in Corollary 3 reduces to the trivial one. In the construction's own setting, DiSPU's certification threshold and the indistinguishability scale of Theorem 2 also differ by two to three orders of magnitude. I would soften the claim that a matching regret rate is established, or prove an upper bound for DiSPU itself on this family.
  3. The benchmarks cannot fully support the paper's main claim. In the synthetic study, UU is independent of GG and the candidates use only UU. So the disagreement probability is the same in every subgroup, and the subgroup-specific adaptivity the paper emphasizes is never exercised. Every improvement opportunity there also harms some protected subgroup, so nothing can be gained at zero tolerance by design. In the ACS benchmark, if I read Appendix C correctly, region R1 offers a gain for everyone. However, the top-ρ\rho library would likely fill up with R4 and R3 units before reaching it, which may be why all methods revert to the incumbent at zero tolerance. A benchmark with a subgroup-safe improvement, and with disagreement that varies across subgroups, would test the main claim more directly.
  4. The experimental scope is slightly narrow. All experiments use binary actions, uniform logging, known propensities, and synthetic outcomes. That is the most favorable case for the bound constant L. Results with more actions, weaker overlap, or estimated propensities would show how far the approach extends. "Extensive" in the abstract seems strong for two environments.
Questions for authors

See Weaknesses.

4 comments
AuthorsOpenReview ↗

Response to Reviewer 3x5i (Part 1)

Dear Reviewer 3x5i.

Thank you for your positive assessment of the theoretical correctness and experimental evaluation! We address your questions about the contribution, DiSPU's own regret rate, and the additional experimental settings below.

[W1] Contribution beyond existing tools

To the best of our knowledge, DiSPU is the first framework to optimize policy deployment under protected-subgroup constraints using disagreement-adaptive simultaneous confidence bounds, with finite-sample safety guarantees and an analysis of how subgroup uncertainty limits safely deployable improvement.

GR Q1 details the distinctions between our work and RobinHood Metevieretal,˙2019Metevier et al\., 2019 and CSPI-MT Choetal,˙2025Cho et al\., 2025.

[W2] Whether DiSPU itself attains the local minimax rate

DiSPU itself attains the leading lower-bound regret rate on a revised two-point family. To show this, we proved a regret upper bound for DiSPU’s own LP, which does not rely on the always-incumbent rule or on setting Γ=δn\Gamma = \delta_n.

GR Q2 provides the construction and bounds. The revised family keeps the overall gain Γ>0\Gamma > 0 and the subgroup tolerance Δ>0\Delta > 0 fixed, so always deploying the incumbent incurs regret of order Γ\Gamma, which does not vanish. We prove a lower bound for every uniformly (1−α)(1-\alpha)-safe procedure and an upper bound for DiSPU’s confidence-adjusted LP. For fixed positive pp, Γ\Gamma, and Δ\Delta, and fixed outcome and overlap bounds, both bounds have leading dependence ΓΔplog⁡(1/α)n\frac{\Gamma}{\Delta}\sqrt{\frac{p\log(1/\alpha)}{n}}, and the remaining terms are lower order when log⁡(1/α)=o(n)\log(1/\alpha) = o(n).

Thus, DiSPU attains vanishing regret at the matching leading rate on the revised positive-tolerance family.

[W3] A benchmark with a subgroup-safe improvement and disagreement that varies across subgroups

Following your suggestion, we added a synthetic experiment that contains a subgroup-safe improvement and lets disagreement vary across subgroups. At zero tolerance, DiSPU has the highest mean overall gain at every heterogeneity level, and its overall and worst-subgroup gains are strictly positive in all repetitions.

1. The added benchmark addresses both limitations of the original synthetic study: candidate disagreement now differs across subgroups, and the library contains a candidate that improves every subgroup.

In the original synthetic study, candidates use only UU, which is independent of GG. Disagreement is thus identical across subgroups, and no improvement is subgroup-safe. In the added benchmark, λ∈{0.1,0.25,0.5,0.75,1}\lambda \in \lbrace0.1, 0.25, 0.5, 0.75, 1\rbrace controls disagreement heterogeneity. The shared library explicitly includes a candidate that improves every subgroup. Zero-tolerance certification therefore no longer depends on whether a top-ρ\rho library reaches such a candidate, the issue you raised for the ACS benchmark. All methods use this library, with an audit size of 200,000 and 100 independent repetitions.

2. At Δ=0\Delta = 0, DiSPU has the highest mean overall gain at every λ\lambda, with strictly positive overall and worst-subgroup gains and no observed safety violations in all 100 repetitions.

Table A. Overall gains and DiSPU’s worst-subgroup gain at Δ=0\Delta = 0.

λ\lambdaDiSPURobinHood-DRHCPI-DRRobinHood-ISHCPI-WIS/ISDiSPU worst-subgroup gain
0.11.831 ± 0.0061.119 ± 0.1870.774 ± 0.1900.949 ± 0.1790.709 ± 0.1761.359 ± 0.027
0.251.815 ± 0.0051.179 ± 0.1810.662 ± 0.1800.932 ± 0.1750.766 ± 0.1781.354 ± 0.028
0.51.794 ± 0.0031.209 ± 0.1740.701 ± 0.1790.902 ± 0.1730.811 ± 0.1771.360 ± 0.026
0.751.781 ± 0.0021.207 ± 0.1700.781 ± 0.1800.912 ± 0.1710.764 ± 0.1741.357 ± 0.027
11.770 ± 0.0011.156 ± 0.1700.769 ± 0.1770.904 ± 0.1690.794 ± 0.1731.358 ± 0.027

DiSPU’s standard deviations of overall gain are at most 0.007, while those of the baselines range from 0.169 to 0.191.

Thus, when subgroup disagreement is heterogeneous and a subgroup-safe candidate is available, DiSPU certifies beneficial updates at zero tolerance.

AuthorsOpenReview ↗

Response to Reviewer 3x5i (Part 2)

[W4] How does DiSPU perform beyond binary actions and uniform logging?

Following your suggestion, we added a four-action experiment with covariate-dependent logging and action-specific harm across six overlapping protected subgroups. DiSPU achieves higher overall gains than the baselines in most settings while maintaining protected-subgroup safety. GR Q3 describes the experimental setup and results.

We again thank you for these constructive suggestions! In the revised manuscript, we will clarify the contribution, strengthen Corollary 4 with the DiSPU-specific regret bound, and add the experiments on disagreement heterogeneity and multiple actions. Your suggestions have really helped us sharpen both the theoretical claim and the empirical scope of DiSPU. We sincerely hope these additions address your concerns.

I thank the authors for the detailed rebuttal to my questions, which addressed most of my concerns. I will keep my positive evaluation score.

Thank you very much for your positive response. We greatly appreciate your time and effort in reviewing our work and are glad that our rebuttal addressed your concerns.

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

This paper studies policy updating under safety constraints in an offline setting. The constraints are formulated in terms of constraints over protected groups. The authors propose an algorithm that assumes a collection of pretrained candidate policies is provided to the learner beforehand. The learner then learns a weighted combination of these candidate policies, with the goal of preserving certain properties of the policy behavior within each protected group, up to a fraction Δs\Delta_s for each protected group ss.

Critical strengths

The problem of updating models under safety constraints is interesting and potentially important, particularly from a multi group fairness perspective. In such settings, it is important to ensure that model updates do not amplify existing disparities across protected groups. The paper addresses this general direction and attempts to provide a formal framework for certifying updates under multigroup level constraints.

Critical weaknesses

I have several concerns regarding both the presentation and, more importantly, the formulation of the problem.

The first issue concerns the motivation. I found it difficult to identify concrete examples of applications where the proposed setting naturally arises, as well as a clear connection to the existing literature on safe policy/model updating. Although the paper uses the terminology of policies, the problem is formulated entirely in an offline setting. Given the substantial literature on offline learning and policy improvement, I would encourage the authors to explain more clearly what is specific to the proposed setting and why an offline formulation is particularly appropriate.

The second issue concerns the notation. Several quantities appear to be defined but are either not used later or are not clearly connected to the subsequent development. For example, H\mathcal{H}, HH, and KK (the size of the action set) appear in the notation but their roles are unclear. This makes the paper harder to follow.

The definition of the probability of disagreement is another example. It appears that the authors are adapting notation from the MDP literature, including state and action sets, but the resulting notation does not seem fully aligned with the problem actually being studied. For example around line 137 the disagreement probability is not sufficiently clear to me. If the intention is to sample according to conditional distributions over protected groups while maintaining a fixed marginal distribution over the overall population this should be stated explicitly. More generally, I think the paper would benefit from omitting unnecessary notations and defining precisely the probability space with respect to which each quantity is evaluated.

More fundamentally, I have concerns about the objective being optimized. In the optimization problem around line 160, a desirable update appears to be one that maximizes the difference between the value of the potential updated policy and that of the incumbent policy. This interpretation seems to be reinforced by the statement in line 194: "so observations in the policy agreement region make no contribution to either the estimated value difference or its empirical variability." I may be misunderstanding the intended interpretation but this seems potentially counterintuitive. If the objective focuses primarily on regions where the new policy disagrees with the incumbent, then the information encoded in the incumbent policy is effectively discarded on the agreement region. In the extreme, this could make the update looks like a new learning problem rather than a strategic update of an already trained and deployed model.

This raises a more fundamental question: what precisely constitutes an "allowable'" or "safe" update in the proposed framework? The constraints appear to require the policy value difference for each protected group ss to exceed a specified threshold. If this is intended to encourage disagreement with the incumbent policy, it would be useful to explain why this is considered as a safety constraint. In particular, is the objective intended to capture multi-group fairness, reduction of prediction errors within each group, policy improvement or something else? At present, I do not see a sufficiently direct connection between the mathematical constraints and the notion of safety described in the paper.

I think the paper could benefit from starting with a more explicit notion of a strategic and safe update of the incumbent model. One natural formulation would be to ask: given an incumbent model that has already been trained and deployed, how much information or behavioral structure inherited from that model are we willing to sacrifice in order to satisfy new group fairness or safety requirements? This would make the trade-off between the information accumulated before an audit and the new information of safety constraints introduced during the update much more explicit. I think such a formulation would also make the role of the incumbent policy substantially clear.

Minor Typos/Terminology:

  • Abstract, line 16: "To address this gap, we study safe policy updating when candidate policies may differ from the incumbent only on a small fraction of each evaluation population." What does "evaluation population" mean here? From my understanding of the optimization problem, I suspect the authors may mean the protected groups.

  • Line 133: The sentence "index the overall deployment population" is unclear. Please clarify what is meant by "deployment population" and how it differs from the other populations introduced in the paper.

  • Line 181: "Extensive experimental results show that direct paired certification can reduce conservatism..." The term "direct paired certification" does not appear to have been defined previously. I recommend introducing the terminology before using it in this statement.

  • Line 95: It seems that the relevant quantity is not model performance itself, but rather the discrepancy between the outputs of the policies across protected groups. The terminology here could therefore be made more precise.

  • Equation (1): I am not sure about the role of OO in the notation. Unless OO denotes the complete observation, including both the context and protected group membership, this notation seems inconsistent with the notation paragraph. parse.

  • Line 384: "All variants share the same candidate library, logged data, and subgroup constraints." The subsequent separate sentence introducing the "Candidate Policy Library" seems unnecessary if this has already been stated here.

Questions for authors
  • Line 62: The main question of the paper is stated as: "How can candidate-incumbent disagreement be exploited to certify safe policy improvement under prespecified protected-subgroup constraints?" I think the term "improvement" requires a more precise definition. In particular, does the reward distribution between incumbent training and the audit/update stage change? What class of strategic updates is being considered? Are the candidate policies intended to maximize disagreement with the incumbent? If so I would appreciate more discussion of why maximizing disagreement is an appropriate starting point, given that it may discard information contained in the incumbent policy.

  • Do the authors assume white-box access to the incumbent policy? If so, why the query complexity associated with interacting with the incumbent policy is completely ignored in the analysis?

  • There seems to be an important missing detail concerning how the MM candidate policies are provided to the auditor. In particular, is anything known about their performance on the training data used for the incumbent policy? What role are these candidate policies play? If they are trained on the same data as the incumbent, one might expect their disagreement with the incumbent to be relatively small. On the other hand, if they are trained on an updated dataset obtained after the audit phase, this would lead to a substantially different setting. I think this distinction should be made explicit.

  • Line 177: The authors state that "The audit samples are reserved for certification and are not used to fit either the candidate policies or the outcome regressions." How is the sample complexity defined in this setting? Does the sample complexity account only for the audit samples or should it also include the training samples required to learn the candidate policies, which appear to be assumed to be available beforehand?

  • The stated bounds depend on the probability of disagreement. Does this probability need to be estimated uniformly over the MM pretrained candidate policies by the auditor? If so, I think the corresponding estimation problem should be discussed more explicitly.

  • Line 137: The i.i.d assumption appears quite strong. It seems reasonable to assume i.i.d observations from the overall population, but conditioning on protected-group membership changes the distribution. I would appreciate clarification on precisely where the i.i.d assumption is being imposed on the subgroup conditioning.

  • Line 193: The statement that the estimator is unbiased conditional on the training data requires some additional explanation. There are several nested expectations and random quantities involved, and the claimed unbiasedness does not appear immediate without additional independence assumptions. Please provide the precise conditioning argument.

  • This is related to the earlier concern about the objective. In line 196, the paper states that "observations in the policy agreement region make no contribution to either the estimated value difference or its empirical variability." Since the candidate policies are themselves trained beforehand, what guarantees are available regarding the disagreement region between the candidate and incumbent policies? In particular, is there any assumption controlling how these disagreement regions arise from the training procedure?

  • The dependence of the upper bounds on the disagreement probability also require further discussion. In line 348, the authors state "This makes the dependence on policy disagreement explicit and shows how smaller disagreement tightens the achievable deployment guarantee." I found this interpretation somewhat difficult to reconcile with the intuition of the problem. If two policies disagree very little, there is relatively little information with which to distinguish their behavior. Conversely, larger disagreement could potentially provide more information for identifying differences between policies. Can you explain more carefully why smaller disagreement leads to tighter guarantees in their particular certification framework?

  • In the experiments, why is the audit set substantially larger than the training set? This seems potentially counterintuitive. For example, the paper considers settings with 50k training samples but audit budgets as large as 200k samples. Since the audit set is used primarily to certify safety on candidate policies, it would be useful to explain the motivation for this choice and how it relates to the intended deployment scenario.

  • Several steps in the proofs require from additional explanation. For example, in Equation (7) of the appendix, is msm_s itself a random variable depending on ss, or is it being treated as deterministic? If it is random, I was not able to follow the step in which it is treated as constant under the expectation. Similarly, the subsequent expectation calculation does not appear immediate and may require additional assumptions or an explicit conditioning argument.

  • Line 590: What probability distribution is "almost surely" referring to?

  • Line 703: These random variables appear to depend jointly on the audit set and the protected groups. Then I am not sure that the i.i.d assumption can be directly extended to these random variables. Can you please clarify this step in the proof?

  • Line 1303: "We define the estimated gain from switching the incumbent action as..." The incumbent action does not appear to have been defined beforehand. Moreover, I was not able to understand how the action depends on the difference of the clipped quantities. This part requires from a more explicit definition and some intuition.

13 comments
AuthorsOpenReview ↗

Response to Reviewer TLW4 (Part 1)

Dear Reviewer TLW4.

Thank you for recognizing the importance of safe policy updating under protected-subgroup constraints! We address your questions about the motivation, policy construction, sampling assumptions, and proof details below.

W1(a)W1(a)

In which concrete applications does this setting arise?

The setting arises when an institution updates a decision rule already in use and must limit losses within prespecified groups. One example is an employment agency updating its counseling referral rule. The agency’s existing rule maps applicant characteristics to a counseling program. A new rule may raise six-month reemployment overall while lowering it within a protected subgroup, so an overall gain alone cannot establish subgroup safety. This example follows the randomized evaluation of job-search counseling and its later use in safe policy improvement research Behagheletal,˙2014;Choetal,˙2025Behaghel et al\., 2014; Cho et al\., 2025.

W1(b)W1(b)

Compared with existing safe and offline policy improvement, what is specific to this setting?

Unlike offline policy learning, DiSPU certifies an update against a deployed incumbent instead of learning a new policy from scratch Kitagawa&Tetenov,2018;Athey&Wager,2021Kitagawa \& Tetenov, 2018; Athey \& Wager, 2021. Unlike existing safe policy improvement, it certifies every protected subgroup. GR Q1 details the distinctions from existing related work.

W1(c)W1(c)

Why is an offline formulation appropriate for a policy-updating problem?

Subgroup harm must be ruled out before an update reaches individuals, so certification must rely on logged data instead of online exploration. Online exploration would expose protected subgroups to the very losses the constraints are meant to prevent. Instead, an earlier randomized pilot with recorded assignment probabilities and sufficient overlap provides the logged data. An independent audit sample then certifies a candidate library fixed in advance. Each individual receives one assignment, so a “policy” here is a contextual-bandit rule that maps covariates to a single action, not a sequential MDP policy.

[W2, W3] Roles of H\mathcal H, HH, and KK, and the definition of disagreement probability

The symbols you identified all have clear roles. They specify the subgroup constraints, the number of simultaneous comparisons, and the action summation in the paired estimator, respectively. The disagreement probability psjp_{sj} is the probability that candidate djd_j changes the incumbent’s action under the subgroup distribution P0(⋅∣Gs=1)P_0(\cdot \mid G_s = 1), which matches your interpretation of subgroup conditioning.

1. H\mathcal{H} enters the subgroup constraints in Equation 44, HH sets the number of comparisons in Equation 33, and KK sets the action summation in Equation 11.

Here, H={1,…,H}\mathcal{H} = \{1, \dots, H\} indexes the HH prespecified protected subgroups and their safety constraints in Equation 44. Including the overall population gives H+1H+1 evaluation populations. With MM candidates, the number of simultaneous comparisons is therefore N=M(H+1)N = M(H+1), which enters the confidence adjustment in Equation 33.

The action set A={0,…,K−1}\mathcal{A} = \{0, \dots, K-1\} specifies the summation in the paired score in Equation 11. Our setting is a contextual bandit. Each observation contains pretreatment covariates XX, one logged action AA, and an outcome YY, and each policy maps XX to one of the KK actions.

2. As you suggested, the disagreement probability conditions a fixed overall distribution on subgroup membership: psj=Pr⁡P0(dj(X)≠b(X)∣Gs=1)p_{sj} = \Pr_{P_0}(d_j(X) \ne b(X) \mid G_s = 1).

Let P0P_0 denote the overall distribution and GsG_s indicate membership in subgroup ss. In the protected-subgroup setting, Ps=P0(⋅∣Gs=1)P_s = P_0(\cdot \mid G_s = 1). Conditional on the training data, the incumbent bb and candidate djd_j are fixed. Their disagreement probabilities are p0j=Pr⁡P0(dj(X)≠b(X)),psj=Pr⁡P0(dj(X)≠b(X)∣Gs=1).p_{0j} = \Pr_{P_0}\big(d_j(X) \ne b(X)\big), p_{sj} = \Pr_{P_0}\big(d_j(X) \ne b(X) \mid G_s = 1\big).

Thus, psjp_{sj} measures the fraction of subgroup ss on which the candidate changes the incumbent’s action. The randomness is over individuals’ covariates in the specified population. Changing ss evaluates the same fixed policies within a different subgroup of P0P_0.

Thus, the symbols you identified enter the subgroup constraints and certification procedure, and psjp_{sj} is the probability that djd_j changes the incumbent’s action under the conditional distribution of subgroup ss within a fixed overall population.

AuthorsOpenReview ↗

Response to Reviewer TLW4 (Part 2)

[W4, W5, Q1] Does DiSPU maximize disagreement and discard the incumbent? What counts as a safe improvement?

A safe improvement in DiSPU is an update that, with probability at least 1−α1-\alpha, does not reduce the overall expected outcome and keeps every protected subgroup’s loss relative to the incumbent within its prespecified tolerance. Among such updates, DiSPU maximizes the certified overall gain instead of disagreement, and agreement regions keep, not discard, the incumbent’s decisions.

1. The objective is the overall value gain, and disagreement enters only as a cost to certification.

Since V0(b)V_0(b) is fixed, maximizing D0(θ)=V0(πθ)−V0(b)D_0(\theta)=V_0(\pi_\theta)-V_0(b) (line 160) is the same as maximizing the deployed policy’s expected outcome. Equation 44 maximizes a lower confidence bound on this gain. The bound’s radius grows at the psj/ns\sqrt{p_{sj}/n_s} rate (Proposition 1, Corollary 1). A candidate that changes more decisions is therefore penalized unless its gain is correspondingly larger. Our candidates switch only where the estimated gain is largest and positive, and they change to at most 2%–20% of decisions AppendixC2˙Appendix C\.2.

2. The statement at line 194 means that the incumbent’s decisions are retained on agreement regions, not that its information is ignored.

Where dj(x)=b(x)d_j(x)=b(x), both policies have the same expected outcome. This region adds zero to the value difference and no estimation noise, and the deployed mixture still follows bb there. The incumbent is also the reference in every constraint and the fallback when no candidate is certified. An update therefore modifies the incumbent locally instead of learning a new policy.

3. Safety is an outcome-based no-harm requirement for each protected subgroup, not a criterion based on prediction error or parity. It is certified for mixtures over a fixed library containing the incumbent, without assuming any change in the reward distribution.

Definition 1 requires V0(πθ^)≥V0(b)V_0(\pi_{\hat\theta})\ge V_0(b) and Vs(πθ^)≥Vs(b)−ΔsV_s(\pi_{\hat\theta})\ge V_s(b)-\Delta_s for every s∈Hs\in\mathcal{H}, and Δs=0\Delta_s=0 rules out any subgroup loss. This follows Thomas et al. 20212021 and Metevier et al. 20192019. The updates considered are mixtures over {b,d1,…,dM}\{b,d_1,\dots,d_M\}, which is fixed before auditing. The LP only decides how much weight to move from bb to the candidates. Both policies are compared under the audit distribution, which represents deployment, so the incumbent’s training distribution plays no role. Theorem 3 shows that all constraints hold jointly with probability at least 1−α1-\alpha.

Thus, DiSPU does not maximize disagreement: it maximizes certified overall gain, retains the incumbent’s decisions where candidates agree, and certifies an update as safe only if it neither lowers the overall outcome nor exceeds any subgroup’s loss tolerance.

[W6] Should the problem be formulated as how much incumbent information to sacrifice for new fairness requirements?

DiSPU starts from an explicit notion of a safe update: the incumbent is the protected baseline, not something to be sacrificed, and an update replaces it only to the extent certified as safe.

1. The safety constraints protect the incumbent’s performance and do not require departing from it.

Definition 1 requires V0(πθ)≥V0(b)V_0(\pi_\theta) \ge V_0(b) and Vs(πθ)≥Vs(b)−ΔsV_s(\pi_\theta) \ge V_s(b) - \Delta_s for every protected subgroup. Because these constraints are defined relative to the incumbent, the incumbent always satisfies them. Setting Δs=0\Delta_s = 0 forbids any subgroup loss, and a positive Δs\Delta_s is a prespecified bound on loss, not a requirement to change the incumbent.

2. The incumbent’s decisions are retained by default and replaced only where improvement is certified.

The incumbent is always a feasible solution of the LP, and DiSPU reverts to it fully when no candidate can be certified. Elsewhere, the deployed mixture keeps the incumbent’s decisions on agreement regions.

3. This formulation follows safe policy improvement literature, which differs from trading inherited information for newly imposed requirements.

HCPI Thomasetal,˙2015Thomas et al\., 2015 and RobinHood Metevieretal,˙2019Metevier et al\., 2019 likewise return a new policy only if, with high probability, it does not underperform the baseline. The formulation you describe fits a setting in which new requirements may force the incumbent itself to change. In our setting, the incumbent meets the requirements by construction, so no such sacrifice arises.

Thus, our setting certifies improvements over the incumbent within subgroup loss limits Δs\Delta_s, and it never sacrifices the incumbent’s information to meet new fairness requirements.

AuthorsOpenReview ↗

Response to Reviewer TLW4 (Part 3)

[Q2] Does DiSPU require white-box access to the incumbent

Certification requires only black-box access to the incumbent's prescribed actions.

To compute Equation 11, the auditor evaluates b(x)b(x) once per audit observation and reuses that action in every candidate comparison. These queries require no new outcome observations.

Q3(a)Q3(a)

How are candidate policies provided to the auditor, and what role do they play?

Candidates are update proposals frozen before auditing, and the auditor needs only black-box access to their actions. The audit then decides how much of each proposal can be safely deployed.

Any procedure may produce the library {d1,…,dM}\lbrace d_1,\dots,d_M \rbrace, provided its construction is independent of the audit sample. The auditor evaluates each dj(x)d_j(x) once per audit context, as for the incumbent, and estimates every candidate–incumbent value difference overall and within each protected subgroup. The LP in Equation 44 then mixes the candidates with the incumbent, which remains feasible as a fallback. DiSPU thus certifies and combines candidates but does not train them.

Q3(b)Q3(b)

Is anything known about candidates’ performance on the incumbent’s training data?

No knowledge of candidate performance on the incumbent’s or any other training data is required, because certification relies only on the independent audit sample.

The analysis conditions on the training σ\sigma-field Ftr\mathcal{F}_{\mathrm{tr}}, under which the library is fixed. The confidence bounds use only paired scores computed on the audit sample, so training performance never enters certification. Theorems 1 and 3 therefore hold for any fixed library, whatever its candidates achieve on the training data.

Q3(c)Q3(c)

Does training on the incumbent’s data limit disagreement, and does training on data updated after the audit change the setting?

Training on the incumbent’s data does not by itself make disagreement small. Training on data updated after the audit does not change the setting.

1. Disagreement is determined by where a candidate departs from the incumbent, not by the data it is trained on.

In our experiments, all 16 candidates share one training split, yet their switching budgets set empirical disagreement caps of 2%, 5%, 10%, and 20% AppendixC2˙Appendix C\.2. Small disagreement also favors certification, since the confidence radius tightens at the psj/ns\sqrt{p_{sj}/n_s} rate.

2. Candidates trained on updated data simply enter a new update round, which DiSPU certifies with the same guarantees.

Section 3 allows candidates from any training procedure whose data are independent of the audit samples, so updated training data fit the same formulation. Each round is certified on its own audit sample. Analyzing adaptively repeated update rounds is the sequential extension noted in Section 7.

Thus, whether candidates use the incumbent’s training data or data updated after the audit, the setting is unchanged, since disagreement is set by candidate construction and each update round is certified on its own audit sample.

[Q4] Samples counted in the sample complexity

The sample complexity at line 177 counts only audit observations used for certification. The analysis conditions on candidate policies and outcome regressions fitted using independent training data, so the training samples are excluded.

[Q5] Whether disagreement probabilities must be estimated

The auditor computes the confidence radii from observed paired-score variances and does not need to estimate the population disagreement probabilities psjp_{sj} to run DiSPU.

1. The deployment LP uses the empirical variance in Equation 33.

The radius is computed directly from the paired scores. Disagreement enters because a score is zero whenever the candidate and incumbent agree.

2. Uniform disagreement control expresses the computed radii in terms of population quantities in the analysis.

Let p^sj=1ns∑i=1ns1dj(Xis)≠b(Xis)\widehat p_{sj}=\frac{1}{n_s}\sum_{i=1}^{n_s}\mathbf 1{d_j(X_{is})\neq b(X_{is})}. Proposition 1 bounds the sample variance in terms of p^sj\widehat p_{sj}. Corollary 1 then applies Bernstein's inequality and a union bound to control p^sj\widehat p_{sj} by psjp_{sj} simultaneously over all candidates and evaluation populations. This yields the population-disagreement interpretation of the confidence widths, while the algorithm uses only the observed scores.

Thus, running DiSPU does not require the auditor to separately estimate psjp_{sj}, and Corollary 1 already provides simultaneous disagreement control across all candidates and evaluation populations for the theoretical rate analysis.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Shared Author Rebuttal (General Responses Part 1)

Dear Reviewers,

Thank you for your careful reading and constructive suggestions! We address the shared concerns about DiSPU's contribution, regret guarantees, and experimental scope below. The individual responses refer to these answers as GR Q1–Q3.

[GR Q1] DiSPU's contribution beyond existing tools

Existing methods cannot certify a policy update against every protected subgroup with confidence bounds that tighten as the candidate departs less from the incumbent. To our knowledge, DiSPU is the first method to solve this problem and the first to establish how much improvement such certification can safely deploy.

1. RobinHood and HCPI cannot exploit disagreement. DiSPU’s bound for each subgroup scales with that subgroup’s own disagreement, psj/ns\sqrt{p_{sj}/n_s}.

RobinHood and HCPI bound the candidate’s and incumbent’s values separately. A candidate that changes few decisions is therefore certified as conservatively as one that changes many. DiSPU certifies the paired difference, whose score is zero wherever the two policies agree (Proposition 1, Corollary 1). A candidate that rarely changes decisions within a subgroup thus receives a tight bound for that subgroup, however much it changes elsewhere.

2. CSPI-MT can neither certify protected subgroups nor provide finite-sample guarantees. DiSPU certifies all overlapping subgroups simultaneously, in finite samples, for the deployment it selects.

CSPI-MT tests only overall improvement, and it relies on a Gaussian approximation. DiSPU’s bounds hold with probability at least 1−α1-\alpha simultaneously over all candidate–population pairs, including overlapping subgroups (Theorem 1). They also hold uniformly over all mixtures of the library Equation(39Equation (39). DiSPU therefore optimizes and certifies the deployment on the same audit sample, without a separate safety test (Theorem 3). Inserting the paired score into Student-tt bounds provides neither of these guarantees.

3. No existing method establishes how much improvement a subgroup-safe update can deploy. DiSPU proves lower and upper bounds that match at leading order, both governed by subgroup disagreement.

Corollaries 2–3 bound DiSPU’s regret by its disagreement-dependent radii. Theorem 2 shows that a subgroup effect of order p/n\sqrt{p/n} cannot be sign-identified. Every uniformly safe procedure must therefore forgo beneficial updates with nonvanishing probability. The strengthened Corollary 4 shows that DiSPU’s own regret matches this lower bound at the leading rate (Γ/Δ)plog⁡(1/α)/n(\Gamma/\Delta)\sqrt{p\log(1/\alpha)/n}.

Thus, DiSPU goes beyond existing methods and is the first to solve the problem of exploiting candidate–incumbent disagreement to certify safe policy updates under protected-subgroup constraints. It also provides rigorous and novel theoretical guarantees.

AuthorsOpenReview ↗

Shared Author Rebuttal (General Responses Part 2)

[GR Q2] Strengthened regret guarantees for DiSPU itself

Following your suggestions, we have strengthened Corollary 4 to establish a regret upper bound for DiSPU itself. It matches the leading lower-bound rate on a revised two-point family with fixed positive overall gain and subgroup tolerance. It does not require Γ=δn\Gamma=\delta_n.

1. The revised construction keeps the overall gain and subgroup tolerance fixed.

The replacement for Corollary 4 uses a two-point family with Γ>0\Gamma>0 and Δ>0\Delta>0, where D0,±(d)=ΓD_{0,\pm}(d)=\Gamma, D1,±(d)=−Δ±δn,αD_{1,\pm}(d)=-\Delta\pm\delta_{n,\alpha}, and δn,α=116plog⁡(1/α)n≤Δ2\delta_{n,\alpha}=\frac{1}{16}\sqrt{\frac{p\log(1/\alpha)}{n}}\leq\frac{\Delta}{2}.

The oracle candidate weights are 11 and Δ/(Δ+δn,α)\Delta/(\Delta+\delta_{n,\alpha}). The difficulty is therefore to determine the safely deployable proportion of a candidate whose overall gain remains fixed and positive.

2. The lower bound applies to every uniformly safe procedure, and the upper bound analyzes DiSPU's actual LP.

Every procedure that is (1−α)(1-\alpha)-safe under both instances satisfies $\sup_\nu\mathbb E_\nu[R_\nu] \geq\frac{5}{288}\frac{\Gamma}{\Delta} \sqrt{\frac{p\log(1/\alpha)}{n}}.$

For DiSPU, we establish sup⁡νEν[(RνDiSPU)+]≤min⁡{Γ,ΓΔan+an2Γ}\sup_{\nu} \mathbb{E}_{\nu} \left[ (R_{\nu}^{\mathrm{DiSPU}})_{+} \right] \leq \min \left\lbrace \Gamma, \frac{\Gamma}{\Delta} a_{n} + \frac{a_{n}^2}{\Gamma} \right\rbrace, where an=L(1+2ℓα)pn+14Lℓα3(n−1)a_n=L\left(1+\sqrt{2\ell_\alpha}\right)\sqrt{\frac{p}{n}}+\frac{14L\ell_\alpha}{3(n-1)} and ℓα=log⁡(16/α)\ell_\alpha=\log(16/\alpha). The lower bound follows from the difficulty of distinguishing the two audit distributions. The upper bound uses the 1/Δ1/\Delta-Lipschitz dependence of the LP's deployment weight on the subgroup lower confidence bound, together with the paired-score variance bound.

3. The bounds have matching leading dependence for fixed positive pp, Γ\Gamma, and Δ\Delta.

With fixed outcome and overlap bounds, the leading dependence is ΓΔplog⁡(1/α)n\frac{\Gamma}{\Delta}\sqrt{\frac{p\log(1/\alpha)}{n}}, and the remaining terms are lower order when log⁡(1/α)=o(n)\log(1/\alpha)=o(n).

DiSPU therefore achieves vanishing regret on this positive-tolerance family with fixed overall gain.

[GR Q3] Performance with multiple actions under nonuniform logging

Following your suggestions, we evaluated DiSPU’s performance in a broader setting, including four actions and covariate-dependent nonuniform logging. DiSPU achieves higher overall gains in most reported comparisons while maintaining subgroup safety.

1. The added experiment extends both the action space and the logging mechanism.

Each of the four actions is optimal on a nonzero region of the policy covariate space. Logging probabilities depend on covariates and range from 0.200.20 to 0.300.30. We conducted 100 independent repetitions, each with fresh training and audit data, across five audit budgets from 10,000 to 200,000 and subgroup tolerances Δ∈0,0.01,…,0.06\Delta\in{0,0.01,\ldots,0.06}.

Table A. Selected overall gains in the four-action experiment (mean ± standard deviation).

Method50k, Δ=0\Delta=050k, Δ=0.06\Delta=0.06200k, Δ=0\Delta=0200k, Δ=0.06\Delta=0.06
DiSPU (Ours)5.10 ± 0.026.02 ± 0.025.53 ± 0.016.45 ± 0.02
RobinHood-DR4.00 ± 0.474.34 ± 0.583.06 ± 0.553.27 ± 0.64
HCPI-DR1.99 ± 0.531.78 ± 0.571.79 ± 0.522.39 ± 0.62
RobinHood-IS3.95 ± 0.474.44 ± 0.572.81 ± 0.553.01 ± 0.64
HCPI-WIS/IS1.91 ± 0.521.71 ± 0.561.89 ± 0.532.06 ± 0.60
CSPI-MT-SG4.84 ± 0.126.03 ± 0.024.94 ± 0.066.04 ± 0.01

2. DiSPU continues to certify beneficial updates, including at zero subgroup tolerance.

The reported comparisons show higher overall gains for DiSPU in most settings while preserving protected-subgroup safety. They also include beneficial updates certified under the strict requirement Δ=0\Delta=0.

These results extend the empirical support for DiSPU to multiple actions, covariate-dependent logging, and heterogeneous subgroup effects.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.