acceptodds
Under review as a conference paper at ICLR 2027

Performative Submodular Decision Making

Abstract

Modern decision-making systems increasingly operate under feedback, where deployed decisions alter future data distributions. Many such systems involve combinatorial subset selection, for which submodularity provides a tractable diminishing-returns structure and efficient approximation methods. However, decision-dependent distributions challenge the structural and algorithmic guarantees underlying classical stochastic submodular optimization. We study this phenomenon through performative submodular decision making, where the selected set both determines the utility and induces its evaluation distribution. We show that the induced performative objective may lose monotonicity and submodularity even when the realization-wise utility preserves both properties, and repeated best response retraining may decrease deployed performance or cycle. To recover tractable structure, we decouple the deployed set from the candidate set being optimized. For any fixed deployment, the resulting frozen objective remains monotone and submodular, providing the basis for approximate performative stability as a self-consistent solution concept. Moreover, under distribution-sensitivity conditions, approximate stability yields a global approximation guarantee for the original performative objective, up to an additive penalty controlled by distributional feedback. Together, these results motivate a finite-sample feedback-safe retraining method that, with high probability, guarantees improvement of the true performative objective along accepted deployments and provides a terminal quality bound upon rejection. Experiments on decision-dependent weighted coverage illustrate structural violations, retraining instability, and the reliability- conservativeness tradeoff of certification.

Primary area:
optimization
Keywords:
Performative decision making, Submodular optimization, Decision-dependent distributions, Approximate algorithm, Stochastic optimization

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_az3sOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies submodular maximization when selecting a set changes the distribution under which its utility is evaluated:

\qquad F(S)=\mathbb E_{\xi\sim D(S)}[f(S,\xi)].$$ Although $f(\cdot,\xi)$ is monotone and submodular for every realization, the performative objective need not retain these properties. The authors recover submodularity by freezing the deployment distribution, relate approximate performative stability to global performance under sensitivity assumptions, and propose a finite-sample acceptance rule that certifies improvements after redeployment. Experiments use a synthetic decision-dependent weighted-coverage model.
Critical strengths
  1. The studied problem is relevant and well motivated. Distribution-changing subset selection provides a useful connection between combinatorial optimization and performative decision making.

  2. The paper carefully separates improvement under a frozen distribution from improvement after deployment, and terminal stability from safety along the deployment trajectory.

  3. The main arguments appear reasonable. The independent certification batch and probability control across adaptive iterations are handled explicitly.

Critical weaknesses
  1. The main safety experiment uses parameters that make every nontrivial update impossible. In particular, Appendix E.2.

  2. The technical novelty of the guarantees need better justification. The main bounds primarily combine sensitivity inequalities, greedy approximation, and concentration. Performative stability and its relationship to predictive performance were already central to the original framework. The paper should identify more precisely which new difficulties arise from submodular decisions and which technical results resolve them.

Questions for authors
  1. Can the method demonstrate multiple accepted redeployments and a meaningful improvement over static greedy under identical initialization and sampling budgets?

  2. On small instances, how do the actual approximation ratios compare with the theoretical feedback-dependent error terms?

  3. When the distribution map is unknown and only sampling access is available, how can valid and sufficiently tight deployment certificates be obtained?

4 comments
AuthorsOpenReview ↗

Experimental Validation and Theoretical Contributions under Decision-Dependent Feedback

Overall Response: We sincerely thank the reviewer for the constructive and insightful comments, which have been particularly valuable in helping us identify the limitations of our experimental evaluation and clarify our theoretical contributions. In response, we have made two main revisions:

  • Experimental validation: Expanded the evaluation of the model-specific local certificate to demonstrate nontrivial safe redeployments, assess terminal performance, and quantify certificate conservativeness.

  • Theoretical contributions and limitations: Clarified the challenges and guarantees in Theorems 5.1, 6.1, and 6.2, evaluated the informativeness of the theoretical approximation bounds, and specified the structural information required for deployment certification.

These revisions have helped us more precisely distinguish what our framework guarantees from its current practical limitations. We address the reviewer's concerns in detail below. The revisions addressing this review are mainly highlighted in purple in the revised manuscript.

Weakness1: The main safety experiment uses parameters that make every nontrivial update impossible. In particular, Appendix E.2.

Response: We agree that the global certificate used in the original experiment is overly conservative and prevents all nontrivial updates. However, this reflects the limitations of the general certificate rather than an inherent inability of the feedback-safe retraining framework to accept updates.

To demonstrate this distinction, we additionally evaluate the model-specific local certificate under cold-start initialization. The method accepts at least one certified redeployment in all runs for γ≤1\gamma\leq 1 and in 96%–100% of runs for γ=2\gamma=2, with no observed safety violations. These results demonstrate that nontrivial safe redeployments are achievable with a tighter certificate, although certification remains conservative in some settings.

Changes: We have updated Section 7.2 and expanded the certificate diagnostics in Appendix E.4.4 (highlighted in purple).

Weakness2: The technical novelty of the guarantees need better justification. The main bounds primarily combine sensitivity inequalities, greedy approximation, and concentration. Performative stability and its relationship to predictive performance were already central to the original framework. The paper should identify more precisely which new difficulties arise from submodular decisions and which technical results resolve them.

Response: We appreciate this observation. We acknowledge that our proofs build on established sensitivity inequalities, greedy approximation, and concentration techniques. We have revised the manuscript to clarify the two difficulties introduced by decision-dependent feedback and the corresponding theoretical guarantees.

  1. Global approximation without performative submodularity. Although the frozen objective remains submodular, the original performative objective need not be. We introduce approximate performative stability for set-valued decisions and establish, in Theorem 5.1, a quantitative stability-to-optimality guarantee for the original objective under controlled distributional sensitivity. Theorem 6.1 further translates this relationship into a conditional terminal guarantee for greedy retraining.
  2. Deployment safety under distributional feedback. Improvement under the frozen objective does not necessarily imply improvement after redeployment. Theorem 6.2 addresses this mismatch through distribution-shift certificates and independent finite-sample validation, providing high-probability improvement guarantees for accepted redeployments and a conditional terminal approximation guarantee.

Our contribution is therefore not a new greedy algorithm or concentration inequality, but the connection between approximate stability, global decision quality, and certified deployment safety for decision-dependent set optimization.

Changes: We have clarified the theoretical motivation and corresponding guarantees in the Introduction, reorganized Section 4, and refined the presentation of Theorems 5.1, 6.1, and 6.2 (highlighted in teal, blue and purple).

AuthorsOpenReview ↗

Experimental Validation and Theoretical Contributions under Decision-Dependent Feedback

Q1: Can the method demonstrate multiple accepted redeployments and a meaningful improvement over static greedy under identical initialization and sampling budgets?

Response: We conducted additional experiments using identical initializations and matched function-evaluation budgets. Although the local certificate enabled safe redeployments, we did not consistently observe multiple accepted updates or establish a statistically significant improvement in terminal performance over static greedy.

These findings highlight a limitation of the current method: the theoretical guarantee ensures improvement for accepted redeployments, but does not guarantee repeated adaptation or superiority over static greedy. The additional certificate diagnostics also show that conservativeness can prevent beneficial updates.

Changes: We have expanded Section 7.2 and Appendix E.4.4 to clarify the distinction between deployment reliability and terminal performance, and to quantify certificate conservativeness.

Q2: On small instances, how do the actual approximation ratios compare with the theoretical feedback-dependent error terms?

Response: We conducted additional small-instance experiments to compare the empirical approximation ratios with the feedback-dependent terminal guarantee in Theorem 6.2.

Across 80 experimental settings, the median empirical approximation ratio is 0.9908, with a median conservative lower bound of 0.9747 based on simultaneous confidence intervals. In contrast, the theoretical lower bound remains positive for γ∈{0,0.01,0.05}\gamma\in \{0,0.01,0.05\} but becomes non-informative for the tested γ≥0.25\gamma\geq 0.25, primarily due to the feedback-dependent penalty. These results indicate that the theoretical guarantee can be substantially conservative, particularly under stronger feedback, even when the empirical approximation performance remains high.

Changes: We have added this comparison to Appendix E.4.4 (highlighted in purple).

Q3: When the distribution map is unknown and only sampling access is available, how can valid and sufficiently tight deployment certificates be obtained?

Response: Our current certificates require structural information in addition to sampling access. The global certificate uses a known upper bound on distributional sensitivity, while the model-specific local certificate exploits the parameters of the weighted-coverage softmax model. Samples from the current deployment are used to estimate frozen improvements, without requiring samples from candidate-induced distributions.

When the distribution map and its sensitivity bounds are unknown, constructing valid and sufficiently tight certificates from samples alone requires additional assumptions. This setting is beyond the scope of our current analysis, and developing data-driven deployment certificates remains an important direction for future work.

Changes: We have clarified the structural information required for the global and model-specific certificates in Section 6.2 (highlighted in blue) and discussed the limitations of certificate construction under unknown distribution maps in the Conclusion (highlighted in purple).

Thank you again for your valuable comments. We hope these revisions address your concerns and would appreciate further suggestions to improve our manuscript.

Thank you for the detailed reply. I have read thru your response and the changes in the revised manuscript. Most of my concerns have been addressed, and I will therefore raise my score.

Thank you very much for taking the time to review our responses and revised manuscript. We sincerely appreciate your thoughtful feedback and reconsideration of our work.

Reviewer_CURpOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the submodular maximization problem under the assumption that the state of the utility function depends on the selected set. Consequently, optimizing performance under the current data distribution is different from optimizing performance after the decision changes that distribution. The authors show that the resulting objective is no longer necessarily submodular, rendering existing results in this field not directly applicable. They develop approximation algorithms under additional assumptions about the objective function.

Critical strengths
  1. This paper tackles an interesting variant of the classical submodular maximization problem, which has the potential for many real-world applications.
  2. The authors demonstrate the hardness of the problem and develop approximation algorithms for it.
Critical weaknesses
  1. My major concern is that the problem setting is overly broad. Technically, it is straightforward to verify that the class of performative objectives defined in the paper includes every normalized, bounded, nonnegative set function. In this sense, the paper essentially studies how to optimize an arbitrary objective function efficiently and effectively. Therefore, the negative results, including the loss of monotonicity and submodularity, are rather trivial.
  2. The second part of the paper appears rather natural to me. The authors make additional assumptions regarding the distribution of states and the variation of the decoupled objective with respect to the deployed set, and then develop approximation algorithms under these assumptions. This part seems incremental given the extensive existing literature on approximate submodular maximization.
  3. My overall impression is that this paper tackles an interesting but overly general research problem, and its technical contributions are incremental.
Questions for authors

See my weakness part.

6 comments
AuthorsOpenReview ↗

Clarifying the Problem Scope and Technical Contributions

Overall Response: We sincerely thank the reviewer for the thoughtful and critical comments. Your concerns prompted us to reconsider the problem scope, motivation, and technical contributions, and to substantially reorganize the manuscript rather than merely clarify individual points. Specifically, we have

  • Revised the Abstract, Introduction, and Related Work to better distinguish our structured problem setting from the general formulation and existing literature;
  • Reorganized Section 4 to connect the challenges of structural loss and deployment instability with our main contributions;
  • Strengthened the discussion of Theorems 5.1, 6.1, and 6.2 to explicitly characterize when the approximation guarantees are informative.

These revisions have helped us present the scope and contributions of our work more precisely. We greatly appreciate the reviewer's guidance. The main revisions are highlighted in teal, and we provide detailed responses below.

Q1: My major concern is that the problem setting is overly broad. Technically, it is straightforward to verify that the class of performative objectives defined in the paper includes every normalized, bounded, nonnegative set function. In this sense, the paper essentially studies how to optimize an arbitrary objective function efficiently and effectively. Therefore, the negative results, including the loss of monotonicity and submodularity, are rather trivial.

Response: We agree that the unrestricted formulation can represent arbitrary normalized, bounded, nonnegative set functions, and that the loss of monotonicity and submodularity is therefore not, by itself, a substantive contribution. Our original presentation did not sufficiently clarify the distinction between the general modeling framework and the structured setting underlying our positive guarantees.

Our main focus is on decision-dependent submodular optimization under explicit distributional sensitivity assumptions. Under Assumptions 5.1 and 5.2, we establish a stability-to-optimality relationship with an explicit feedback-dependent error term. This characterizes when approximately stable decisions retain meaningful global approximation guarantees despite the possible loss of submodularity of the performative objective. We further study how such decisions can be obtained through retraining and how accepted redeployments can be certified against performance degradation.

Changes: We have clarified the problem scope in the Introduction and Problem Statement, reorganized Section 4, and explicitly characterized the conditions for nontrivial approximation guarantees in Theorems 5.1 and 6.1. Appendix B.2 verifies the regularity assumptions for the weighted-coverage softmax model.

Q2: The second part of the paper appears rather natural to me. The authors make additional assumptions regarding the distribution of states and the variation of the decoupled objective with respect to the deployed set, and then develop approximation algorithms under these assumptions. This part seems incremental given the extensive existing literature on approximate submodular maximization.

Response: We acknowledge that our analysis builds on established greedy approximation, sensitivity, and concentration techniques. Our contribution is not a new greedy algorithm, but a quantitative connection between approximate performative stability, global approximation, and deployment safety under decision-dependent feedback.

First, we introduce approximate performative stability for set-valued decisions as a self-consistent solution concept. More importantly, Theorem 5.1 establishes its quantitative connection to global approximation for the original performative objective, even when this objective is neither monotone nor submodular. Specifically, an α\alpha-approximately performatively stable decision satisfies

\qquad \kappa=\frac{\rho\Delta_{\mathcal I}}{\mathrm{OPT}}.$$ This identifies an explicit regime, $\kappa<1$, in which approximate stability yields a nontrivial global approximation. Theorem 6.1 further establishes this guarantee for terminal greedy retraining, conditional on its stopping criterion. Second, **Theorem 6.2 connects certified deployment safety with terminal approximation.** It guarantees, with high probability, improvement along every accepted redeployment and, upon rejection before the iteration limit, a global approximation bound with explicit errors from distributional feedback, greedy approximation, and finite-sample estimation. The key distinction from classical submodular maximization is that our guarantees concern the original decision-dependent objective and the safety of redeployment, rather than only the optimization of a fixed-distribution submodular objective.
AuthorsOpenReview ↗

Clarifying the Problem Scope and Technical Contributions

Changes: We have revised the presentation of the main theoretical contributions in Sections 5–6, clarifying the stability-to-optimality connection in Theorem 5.1, its algorithmic realization in Theorem 6.1, and the combination of deployment safety and conditional terminal approximation in Theorem 6.2.

Q3: My overall impression is that this paper tackles an interesting but overly general research problem, and its technical contributions are incremental.

Response: We appreciate this assessment. We have revised the manuscript to better distinguish the structured setting underlying our guarantees from the general formulation and to clarify the specific theoretical contributions beyond classical submodular maximization.

Changes: We have strengthened the motivation and application discussion, clarified the scope and limitations of our results, and expanded the Related Work to better position our contributions.

Thank you again for your valuable comments. We hope these revisions address your concerns and would appreciate further suggestions to improve our manuscript.

I would like to thank the authors for their clarification, which has addressed some of my concerns. However, my primary concern regarding the technical contribution of this study remains unresolved.

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

The paper studies subset selection when the selected set changes the distribution under which its utility is evaluated. It shows that this feedback can destroy monotonicity and submodularity and cause repeated optimization to cycle. Thus, a static and sequential greedy might fail badly to provide a reasonable solution. The authors relate approximate performative stability to global approximation guarantees and develop finite-sample certification of safe redeployments, that is a redeployment that does not degrade the function value as the selected set and its implied distribution changes.

Critical strengths

The problem is well motivated, and the formulation is clearly explained. Overall, the paper is a good read. The paper introduces a formulation of performative submodular optimization with good potential for follow-up work.

Critical weaknesses

Some assumptions need further justification and concrete examples to motivate them. Some guarantees would benefit from clarification, particularly about when their bounds are informative; please see my questions below. The experimental section could better demonstrate the practical benefit of feedback-safe retraining beyond static greedy. In Table 2, the a posteriori method achieves a final objective similar to naive repeated greedy, while the feedback-safe method ties static greedy. I understand that the a posteriori method causes fewer harmful intermediate updates. However, I would like to better understand the practical significance of this benefit when the final utility is essentially unchanged. How large are the intermediate performance decreases, and what are the practical consequences of avoiding them?

Questions for authors
  1. Could you explicitly define “retraining” at its first use in the introduction?

  2. Is sample access to D(S)D(S) realistic in the intended applications? Could you provide a concrete example beyond the simulator used in the experiments?

  3. For Assumption 5.2, could you instantiate the states (ξ,ξ′)(\xi,\xi'), the metric dΩd_\Omega, and the constants LξL_\xi and λ\lambda in a concrete example?

  4. Suppose every pointwise marginal contribution is uniformly bounded by (c), so that OPT≤kc\mathrm{OPT}\le kc. Could you give examples in which the additive penalty in Theorem 6.1 is small relative to OPT, making the guarantee informative?

  5. In Lemma C.1 and line 352, the factor kk in ηgr\eta_{\mathrm{gr}} raises a question about sample requirements. How large must NgrN_{\mathrm{gr}} be for the error to be small relative to the frozen optimum? Could Algorithm 1 also clarify the roles of NgrN_{\mathrm{gr}} and NN?

  6. How can a valid, reasonably tight certificate C(Rt,Tt)C(R_t,T_t) be obtained under sample-only access?

  7. Could you instantiate the terms in Γt\Gamma_t from Theorem 6.2 in a concrete example and show when the approximation guarantee is informative?

  8. In the algorithm line 9, why is the rejected candidate RtR_t being returned together with TtT_t ? The return only returns TKT_K.

  9. Could you comment on the number of oracle calls (function evaluations) required by your algorithm and compare it with static greedy?

2 comments
AuthorsOpenReview ↗

Clarifications of Theoretical Guarantees, Sampling Assumptions, and Deployment Certification

Overall comment: We sincerely thank the reviewer for the constructive and detailed comments, which have helped us clarify the assumptions, theoretical guarantees, and practical scope of our methods. In response, we have made two main improvements.

  • First, we have provided a concrete verification of the regularity assumptions, clarified the information required for deployment certification, and added numerical illustrations of when our approximation guarantees are informative.
  • Second, we have expanded the experimental evaluation to distinguish terminal stability from deployment-level safety and to examine the conservativeness of the proposed certificates.

These revisions have strengthened both the theoretical presentation and the experimental interpretation of our work. We provide point-by-point responses below. Revisions addressing this review are highlighted in blue.

Q1. Could you explicitly define “retraining” at its first use in the introduction?

Response: Thank you for the suggestion. We have clarified that retraining involves two steps: (i) approximately optimizing a candidate subset under the distribution induced by the current deployment and (ii) redeploying the candidate, thereby inducing a new distribution.

Changes: We have explicitly defined retraining at its first occurrence in the Introduction.

Q2. Is sample access to D(S)D(S) realistic in the intended applications? Could you provide a concrete example beyond the simulator used in the experiments?

Response: Thank you for this question. Sample access is plausible in applications where observations can be collected under the currently deployed decision. For example, in wireless sensing and control, sensing schedules and resource allocation affect queueing, semantic-age, and beam-alignment dynamics. Operational measurements under the current configuration can provide samples of the induced system states.

Our algorithms require samples only under the current deployment, without counterfactual samples from undeployed candidates. Constructing valid deployment certificates additionally requires known sensitivity bounds or model-specific structural information.

Changes: We have clarified the sample-access assumption in Section 3 and added a wireless sensing and control example in the Introduction.

Q3. For Assumption 5.2, could you instantiate the states (ξ,ξ′)(\xi,\xi'), the metric dΩd_\Omega, and the constants LξL_\xi and λ\lambda in a concrete example?

Response: Thank you for the suggestion. We verify Assumptions 5.1–5.2 for the decision-dependent weighted-coverage model in Section 7. The states ξ,ξ′∈Δm−1\xi,\xi'\in\Delta^{m-1} are topic-preference vectors, equipped with the metric dΩ(ξ,ξ′)=∥ξ−ξ′∥1d_\Omega(\xi,\xi')=\|\xi-\xi'\|1. Since cj(S)∈[0,1]c_j(S)\in[0,1] for all jj, Assumption 5.2 holds with Lξ=1/2L_\xi=1/2. For the softmax distribution model, let βB=max⁡j,ℓ,e∣Bje−Bℓe∣\beta_B=\max_{j,\ell,e}|B_{je}-B_{\ell e}|. Coupling the distributions using the same latent random variable yields

\leq \frac{\gamma\beta_B}{2}|S\triangle T|.$$ Thus, Assumption 5.1 holds with $\lambda=\gamma\beta_B/2$, giving $\rho=L_\xi\lambda=\gamma\beta_B/4$. **Changes:** We have provided a concrete verification of both assumptions in Appendix B.2. **Q4.** Suppose every pointwise marginal contribution is uniformly bounded by $c$, so that $\mathrm{OPT}\le kc$. Could you give examples in which the additive penalty in Theorem 6.1 is small relative to $\mathrm{OPT}$, making the guarantee informative? **Response:** Thank you for raising this important point. Theorem 6.1 provides a meaningful approximation guarantee when the relative additive penalty $(2k(1 -1/e)L_\xi\lambda+\tau)/{\mathrm{OPT}}$ is sufficiently small. For the weighted-coverage model, Appendix B.2 establishes $L_\xi\lambda=\gamma\beta_B/4$. Consider an instance with $m=n=k=5$, where each element covers a distinct topic with strength $0.5$. The full set $V$ achieves $\mathrm{OPT}=0.5$. Taking $\gamma\beta_B=0.01$ and $\tau=10^{-4}$, the additive penalty is approximately $0.0159$, or $3.18\%$ of $\mathrm{OPT}$. Consequently, whenever the termination condition holds, Theorem 6.1 guarantees $$F(S_t)\geq 0.6003\ \mathrm{OPT}.$$ This example illustrates that the guarantee remains informative under nonzero decision-dependent feedback. **Changes:** We have clarified the conditions for a nontrivial approximation guarantee in Theorem 6.1 and provided the corresponding sensitivity constants for the weighted-coverage model in Appendix B.2.
AuthorsOpenReview ↗

Clarifications of Theoretical Guarantees, Sampling Assumptions, and Deployment Certification

Q5. In Lemma C.1 and line 352, the factor kk in ηgr\eta_{\mathrm{gr}} raises a question about sample requirements. How large must NgrN_{\mathrm{gr}} be for the error to be small relative to the frozen optimum? Could Algorithm 1 also clarify the roles of NgrN_{\mathrm{gr}} and NN?

Response: Thank you for highlighting this issue. By Lemma C.1, to ensure ηgr≤ϵrelGt⋆\eta_{\rm gr}\leq\epsilon_{\rm rel}G_t^\star, where Gt⋆=max⁡S∈IkG(S;Tt)G_t^\star=\max_{S\in\mathcal I_k}G(S;T_t), it suffices to choose

\frac{2k^2M^2}{\epsilon_{\rm rel}^2(G_t^\star)^2} \log\frac{2Kkn}{\delta_{\rm gr}}.$$ This bound is sufficient and may be conservative; a uniform choice across deployments requires a positive lower bound on $G_t^\star$. We have also clarified that $N_{\rm gr}$ is the batch size used to estimate marginal gains during greedy optimization, whereas $N$ is the size of an independent certification batch. With fresh samples at each greedy round, one response requires at most $kN_{\rm gr}$ samples. **Changes:** We have clarified the sample requirement in Section 6.2 and the roles of $N_{\rm gr}$ and $N$ in Algorithm 1. **Q6.** How can a valid, reasonably tight certificate $C(R_t,T_t)$ be obtained under sample-only access? **Response:** Thank you for this question. Our certificates do not require samples from candidate-induced distributions, but they do require structural information beyond sampling access alone. Under Assumptions 5.1–5.2, a known upper bound $\bar\rho\geq L_\xi\lambda$ gives the global certificate $$C_{\rm global}(R,T)=\bar\rho|R\triangle T|.$$ For the weighted-coverage softmax model, Proposition D.1 further provides a tighter, model-specific certificate: $$C_{\rm loc}(R,T)= \frac{\gamma}{4} \operatorname{osc}(c(R)) \operatorname{osc}\bigl(B(\mathbf 1_T-\mathbf 1_R)\bigr).$$ The local certificate is computed from known model parameters and candidate sets, while samples from the current deployment are used to estimate frozen improvements. Table 6 illustrates that the local certificate can be substantially tighter than the global one. Thus, certificate validity requires either a known sensitivity bound or model-specific structural information, even when only samples from the current deployment are available. **Changes:** We have clarified the construction and computation of both certificates in Section 6.2. **Q7:** Could you instantiate the terms in $\Gamma_t$ from Theorem 6.2 in a concrete example and show when the approximation guarantee is informative? **Response:** Thank you for the suggestion. We provide a concrete numerical illustration using the weighted-coverage softmax model. Consider $n=20$, $m=8$, $k=5$, and $\mathrm{OPT}\geq0.5$, with nonzero feedback satisfying $\gamma\beta_B=0.01$. For a one-element exchange, the model-specific certificate satisfies $C_{\rm loc}(R_t,T_t)\leq0.005$. With $N_{\rm gr}=1.5\times10^6$, $N=10^6$, and suitable confidence parameters, the feedback, greedy estimation, certification, and tolerance terms yield $\Gamma_t<0.0486$. Consequently, if the algorithm terminates upon rejecting a candidate, Theorem 6.2 guarantees, with probability at least (0.95), $$F(T_t)>0.5349\,\mathrm{OPT}.$$ This illustrates that the terminal guarantee can remain nontrivial under nonzero decision-dependent feedback. **Changes:** We have added the complete parameter specification and error calculations in Appendix D.1. **Q8:** In the algorithm line 9, why is the rejected candidate $R_t$ being returned together with $T_t$? The return only returns $T_K$. **Response:** Thank you for pointing out this inconsistency. The rejected candidate $R_t$ is used only to evaluate the terminal bound in Theorem 6.2 and is not part of the deployed solution. **Changes:** We have revised line 9 of Algorithm 1 to return $T_t$ only, while line 12 returns $T_K$ when the maximum number of tests is reached. **Q9.** Could you comment on the number of oracle calls (function evaluations) required by your algorithm and compare it with static greedy? **Response:** Thank you for this question. Let $J\leq K$ denote the number of executed certification tests. Under direct evaluation of empirical marginal gains, one greedy response requires at most $$Q_{\rm gr} =2N_{\rm gr}\left(kn-\frac{k(k-1)}{2}\right)$$ function evaluations, while each certification test requires $2N$ additional evaluations. Thus, we have $Q_{\rm alg}\leq J(Q_{\rm gr}+2N)$. In comparison, static greedy requires only $Q_{\rm gr}$ evaluations. Hence, the additional cost of feedback-safe retraining is at most $(J-1)Q_{\rm gr}+2JN$. When the first candidate is rejected, only one greedy response and one certification test are required. **Changes:** We have added the function-evaluation complexity and its comparison with static greedy in Appendix E. **Thank you again for your valuable comments. We hope these revisions address your concerns and would appreciate further suggestions to improve our manuscript.**

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.