- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
This paper studies exact unlearning of a single feedback row in product combinatorial semi-bandits, where the learner explores in doubling phases, commits to a slate (one block of items per position), and then stops collecting feedback. It requires category-wise stability: the public actions on the original and erased tables must be within total variation , conditional on a pre-feedback category label of the deleted row's action, with protected groups per position. With items in total, served per round, and gap , it proves minimax pseudo-regret on a class with a unique optimal slate and comparable gaps. Its Envelope learner attains this rate without knowing the gaps. In the phase containing the missing row, it uses the largest commitment probability over all fillings of the missing reward, so under a shared random draw the erased run stops no later than the factual one and can be replayed from collected feedback alone.
Critical strengths
-
Exact replay from collected feedback. Under a shared random draw, the completion envelope makes the erased run stop no later than the factual run, so replay never needs uncollected feedback. The envelope is the smallest local rule with this property (Proposition B.1).
-
Matching characterization of the stability cost. Theorem 1's lower bounds hold against adaptive learners and are attained by a learner that does not know the gaps, so the regret cost of category-wise stability is tight up to logarithmic factors. Corollary 1 adds that the arrangement of categories matters, not only their number. Two labelings with the same number of equally likely categories differ in cost by a factor of , the number of candidate blocks per position.
Critical weaknesses
-
The main text is not self-contained. The central argument and the limits of the contribution are left to the appendix.
- The body does not define some of the terms in its theorem statements, such as the "causal learners" of Theorem 1 and the "factual tape" of Theorem 2.
- The key stability bound is asserted without explanation. Section 5 states that the best filling raises the certificate by at most in expectation given the category, but it does not show that the category enters through the conditional inverse-propensity weight, where the constant comes from, or that the bound relies on reward-independent sampling. The ingredients (the coupling and the inflation factor ) appear in separate paragraphs, and the reader must reconstruct the argument from Lemmas B.5–B.6 in a 44-page appendix.
- The conclusion part (section 7) consists of three abstract sentences that state neither the results nor any limitation.
- The restrictions that bound the contribution (a single request, gap regularity, and reward-independent probing) appear only as scattered appendix remarks.
- The introduction cites no prior work, and the related work omits standard exact-unlearning references (Ginart et al., 2019; Bourtoule et al., 2021; Sekhari et al., 2021; Neel et al., 2021) as well as online learning with deletions (Hu et al., 2025).
-
The paper has no narrative thread. Sections and paragraphs follow one another without a stated purpose or transition. The introduction has no roadmap and no list of contributions, so the reader is never told what each section establishes. Section titles name the paper's own constructions rather than what is shown, which could be confusing to the reader. For example, section 5, "Exact replay with a completion envelope", is titled after a coined term, yet it presents the main learner and the regret bound that attains Theorem 1 (Theorem 2), not only replay. Material also sits apart from where the titles place it. Section 3, "Setting and guarantees", omits the product action class, the protected groups and the reward model, which first appear in Section 4. Sections end without transitions. Section 4 closes with a paragraph on private learning and appendix pointers. Section 5 then opens on the "Envelope" learner, which has been named only once before, in passing. Within Section 5, the envelope (Eq. 10) is defined through a commitment probability whose ingredients (sampling rule, scores, certificate and gate; Eqs. 11–14) are given only afterwards. Each paragraph opens a new topic without linking to the previous one. The reader therefore cannot tell why each piece is introduced or how it serves the main results, which compounds W1.
Questions for authors
- Deletion is executed after training, when the factual run has already been served. What does the system output or store after unlearning? Why is reconstructing the full erased run, including a counterfactual earlier commitment, the right target? Can the construction handle online deletion, that is, a request arriving while the learner is still exploring, after which it must continue as if the row had been erased (as allowed by Nguyen-Tang and Arora, 2026)?
- The guarantee covers a single request. If the envelope is taken over the joint fillings of several missing rows, does the erased run still stop no later than the factual one? Does slope give one-step stability on inputs that already contain missing markers, so that Lemma A.2 yields for requests? If not, is the obstacle technical, or is there a counterexample?
- Theorem 2's upper bound carries a factor that the lower bound lacks. What is the rate when gaps are not comparable, that is, for large ? Relatedly, the proof of Lemma B.6 uses the fact that the deleted row's action still has law given the rest of its phase, which holds only because sampling is fixed in advance. Is reward-independent sampling therefore necessary for category-wise stability itself, and not only for replay from collected feedback?
- Omit-only replay, which simply drops the missing reward, fails on 14 of 4608 synthetic requests and on none from real data. Under what conditions does it fail? Please characterize when the envelope is needed, or state that its value is a worst-case guarantee.
5 comments
Dear Reviewer,
We have updated our point-by-point response and the follow-up “New guarantees, stronger evidence and a clearer narrative” in this thread.
The updates explain the changes to self-containment and narrative, answer all four questions, and summarize the additional contributions. We would be grateful for your reassessment and any remaining concerns.
Thank you for your time and consideration.
I thank the authors for the detailed responses and for the considerable effort they have put into revising the manuscript. The revision addresses the concerns raised in my review. However, the manuscript has since changed substantially. The current version changes the title, introduces a second learner (Gibbs) with a new serving guarantee, adds an adaptive refinement of Envelope with new proofs, and reports experiments on new datasets. The total length of paper expand from 55 pages at submission to 86 pages now. These are new contributions rather than further validation of the submitted results, and they cannot be adequately reviewed within the discussion period. I am keeping my scores unchanged. I believe the paper would benefit from resubmission, where its new contributions can receive a full review.
New guarantees, stronger evidence and a clearer narrative
Thank you again for your detailed guidance on self-containment, narrative and the replay target. Alongside the point-by-point revisions in our main response, the wider discussion has led to additional results that make the paper's contributions easier to explain and assess.
1. A clearer distinction between the two learning guarantees.
Envelope learns when to stop collecting feedback; Gibbs uses a budget chosen in advance. Both provide category stability and exact replay from retained feedback.
Appendix K.19 now proves a sufficient Gibbs budget for near-optimal expected serving reward under the stated mean and probing assumptions. This budget does not grow with the number of later serving rounds.
The result also addresses your interest in multiple omissions: with the stated confidence, the serving-value bound holds simultaneously for every set of up to r removed acquired rows. It averages over the final Gibbs slate draw. This is a fixed-budget utility result; Envelope's separate repeated-deletion conditions remain explicit in Appendix H.
2. A concrete answer to what replay must retain and recompute.
Appendix K.20 explains why original Envelope needs to reconstruct only the affected phase. If both executions continue, their score reset makes the later execution identical; otherwise the erased execution has already committed.
We also prove a certificate, based on public action counts, identifying completed phases whose responses can be discarded while preserving every separate single-withdrawal reconstruction. Across nine recorded commerce workloads, 5.43%–34.87% of acquired responses qualify.
This gives a precise retained-state rule: keep the required action/time metadata and saved randomness, while discarding responses certified unnecessary for this replay task. The percentages are certified response counts after collection.
3. Verified improvements to adaptive stopping.
Appendix K.21 adds adaptive refinements, including feedback reuse across phases, with proofs preserving category stability, exact single-erasure replay and the original regret order in the stated single-position setting.
The best tested fixed-budget Gibbs achieves 40.394 regret here. Its stronger result illustrates the complementary fixed-budget contribution; complete Gibbs and Sparsemax comparisons remain available.
4. Broader evaluation and a stronger reproducibility record.
The evaluation now covers chronological recommendation logs, full catalogs, commerce, randomized email and advertising benchmarks. We added comparisons under matched category protection, collection-budget grids, file-backed withdrawal tests and optimized-cache baselines, with independent erased-reference checks. We retain the weaker regimes and modest cache gains (Appendix K).
The technical appendices also provide the bounded repeated-deletion extension and counterexample, reconciliation of the earlier lower bound, and diagnoses of the numerical reproducibility discrepancies with a pinned reference environment (Appendices H–J).
5. More substance with a clearer presentation.
Your concern that readers had to reconstruct the story from the appendix guided the revision. The main text now introduces the setup before the theorems, builds the learner in order, and explains the stability reasoning directly. The same running example connects these steps.
We also simplified the abstract and shortened the appendix by 16 pages, preserving the proofs and retaining extended plots and tables in a companion detailed record. The original structure, core guarantees and ten-page main text remain intact.
We hope you will consider these additions alongside our direct answers to your four questions. We respectfully ask you to reconsider your rating to 3, or 4 if the revised paper warrants stronger support. Thank you for helping us make both the argument and its practical implications clearer.