acceptodds
Under review as a conference paper at ICLR 2027

Unlearning Offline Stochastic Multi-Armed Bandits

Abstract

Machine unlearning aims to unlearn data points from a learned model, offering a principled way to mitigate privacy risks without full retraining, while preserving the utility of the learned model. Prior work has mainly studied unsupervised / supervised machine unlearning, leaving unlearning for sequential decision-making systems far less understood. We initiate the first study of a foundational sequential decision-making problem: offline stochastic multi-armed bandits (MAB). We formalize the privacy constraint for offline MAB and measure utility by the post-unlearning decision quality. We conduct a systematic study under two data-generation models: the fixed-sample model and the distribution model. Our analysis covers single-source requests in both models and extends to multi-source deletion in the fixed-sample setting. For these settings, our algorithmic design is built on two base mechanisms: the downward-shifted Gaussian mechanism and rollback, and we propose adaptive algorithms that switch between them according to the data regime and privacy constraint. We also provide performance guarantees across the above settings and establish lower bounds under both dataset models. Experiments validate the predicted trade-offs and show the effectiveness of the proposed methods.

Primary area:
learning theory
Keywords:
machine unlearning, multi-armed bandits, differential privacy

Reviews

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

The paper studies approximate unlearning for offline stochastic multi-armed bandits, measuring utility by the expected simple regret of the final recommendation. Its output-level definition allows O(m) stored statistics and gives the reference execution retained-data statistics plus the deleted arms' identities and counts. The proposed method screens the affected arm, then switches between exact rollback and downward-shifted Gaussian perturbation using theoretical utility costs. The paper develops single-source bounds under fixed-count and behavior-policy models, a multi-source construction under the fixed-count model, and synthetic and Yelp-derived comparisons.

Critical strengths
  1. A meaningful statistical question and a useful adaptive construction. Although exact rollback is inexpensive, deletion reduces effective coverage and can harm the final recommendation. The retained-data screen aligns the actual and reference branches, while the downward shift controls promotion of a suboptimal deleted arm. This gives a concrete approach to trading approximate unlearning against statistical utility.
  2. A substantive multi-source extension. Common candidate refinement, private source selection, conditional Gaussian perturbation and an explicitly budgeted exceptional mixture provide a coherent way to perturb only one requested source. The appendix is detailed enough to inspect the argument, and the full 200-seed rerun reproduced the synthetic multi-source percentages in Appendix B.5.
Critical weaknesses
  1. The experiments do not validate the stated switching rule at consistently calibrated privacy budgets. Equation (2) corresponds to BG < BR, but experiment_suite.py:39–53,425 applies undocumented multipliers 0.567, 0.614, 0.6215, 0.732 and 0.745 to BR. They change the chosen branch: at N=3000, k=80 and gamma=.02, the 200-seed rerun gives regret .004456 with the exact rule versus .003860 with the supplied implementation. Their selection procedure needs explanation. Single-source CSVs/CDR use the classical formula epsilon=sqrt(2log(1.25/delta))/gamma; at delta=.1 and gamma=.02 it gives 112.38, whereas the manuscript's analytic calibration requires 1313.09. A separate valid two-arm example violates even the final-recommendation inequality at the reported 112.38, .1 budget, so this is more than failure of a sufficient Gaussian certificate. It does not refute the correctly calibrated manuscript theorem. Utility gains at informative privacy levels remain unestablished, and the official supplement lacks the Yelp features/preprocessing needed to reproduce the main real-data figure.
  2. The optimality claims need narrower scope, and one lower-bound statement needs repair. For fixed 1<C*<2, both executions can reconstruct original counts using N_D(a)=N_retained(a)+k_a. Preserving the original most-frequent-arm decision therefore gives exact (0,0)-BUL and exponentially decreasing expected regret in N, independent of deletion size, under the stated i.i.d. behavior model. Algorithm 6's deletion-dependent bound is unnecessarily weak in this regime. The other lower bounds do not establish tightness of the Gaussian-dominated privacy dependence. Separately, Theorem 6 omits a needed coverage condition: with counts (50,100), N*=100, a0=1 and k=20, coverage forces arm 2 to be optimal, so a constant arm-2 rule has zero regret, contradicting the positive lower bound. The two-point proof needs both candidate optimal arms to satisfy coverage. This is a repairable statement error rather than a failure of the central privacy argument.
Questions for authors
  1. How were the single-source switch multipliers chosen, and which rule generated the figures? Please provide comparisons using the exact Equation (2) rule and a fully specified source/deletion protocol.
  2. How much of the advantage remains when all methods use the same correctly calibrated (epsilon, delta) values, including informative privacy levels? Can you provide the Yelp inputs or an executable raw-to-feature pipeline and the missing Table 2 configuration?
  3. Can you repair Theorem 6's coverage assumptions and state precisely which regimes have matching bounds? Please address the descriptor-aware original-count rule for 1<C*<2. A shifted Laplace mechanism is also a useful comparator at the same epsilon; the existing Gaussian lower bounds do not establish its inferiority.
1 comment

We thank you for your constructive and detailed feedback.

[Weakness 1 and Question 1] Validation of calibration. We thank the reviewer for pointing out the insufficient explanation of our calibration procedure. Our theoretical bounds characterize sub-optimality only up to constant factors, and the quantities compared in Eq. (2) are theoretical utility bounds rather than exact expected sub-optimalities. In the experiments, we introduce a conservative calibration factor c∈(0,1)c\in (0,1) on the rollback-side bound, so that the Gaussian mechanism is selected only when BG<cBRB_G<cB_R. This encourages an earlier switch to rollback. For a fixed, publicly specified cc, the adjustment preserves the (ϵ,δ)(\epsilon,\delta)-unlearning guarantee and the asymptotic utility bounds up to constant factors. The coefficients were chosen based on our prior exploratory experiments. We acknowledge that this calibration was not adequately documented and provide the details and comparisons in the last page of appendix in the revised version.

[Weakness 2 and Question 3] Technical Details.

Coverage condition in Theorem 6 and Regimes with matching bounds: Please see the response to Reviewer gHZ6 on [Weakness 2 and Question 2].

Descriptor-aware original-count rule for 1<C⋆<21<C^\star<2: We thank the reviewer for this observation. We agree that, under our current Definition 1, the original arm counts can be reconstructed from the deletion descriptor. Our initial intention for 1<C⋆<21<C^\star<2 was to impose a stronger privacy requirement: the reference execution cannot access the deletion descriptor. Since imitation learning already achieves exponentially small regret in this regime, allowing reconstruction of the original counts would trivialize the unlearning problem. Nevertheless, we have decided to retain the current privacy requirement and incorporate the reviewer's observation into Algorithm 6. Specifically, the revised algorithm uses the original arm counts in both the actual and reference executions, remains (0,0)(0,0)-BUL, and achieves an improved regret bound of O(exp⁡(−N2ln⁡(C⋆)24(C⋆−1)))O\left(\exp\left(-\frac{N}{2}\ln\frac{(C^\star)^2}{4(C^\star-1)}\right)\right), independent of the deletion size kk. Please see our revised PDF.

Shifted Laplace comparison: We thank the reviewer for this suggestion. Gaussian perturbation is a natural starting point, following prior certified-unlearning frameworks for parameter-valued models. Our single-source mechanism perturbs only one LCB coordinate, therefore shifted Laplace offers a favorable alternative. By [1], Laplace noise with scale b=Δfϵb=\frac{\Delta_f}{\epsilon} achieves pure ϵ,0\epsilon,0-privacy for any ϵ>0\epsilon>0. With an appropriate downward shift, the additional sub-optimality terms for Gaussian mechanisms is $O\left(\frac{k\gamma(\epsilon,\delta)}{N(a_0)} \left[1+\sqrt{\ln(1+N\gamma(\epsilon,\delta))}\right]\right)$, for Laplace mechanism is $O\left(\frac{k}{N(a_0)\epsilon} \left[1+\ln\left(1+\frac{Nk}{N(a_0)\epsilon}\right)\right]\right)$. For fixed δ>0\delta>0, Gaussian can be preferable as ϵ→0\epsilon\to 0, since γ(ϵ,δ)\gamma(\epsilon,\delta) remains bounded, whereas Laplace noise scales as 1/ϵ1/\epsilon. Conversely, as ϵ→∞\epsilon\to\infty, Laplace has a better noise-scale dependence, and may also be preferable for small δ\delta. We will incorporate shifted Laplace as an additional base mechanism in the next version.

[Question 2] At this loose budget in the last page of revised version, although strict Eq. (2) has a narrower advantage than the tuned switch, it still achieves lower mean regret than rollback at 16/25 fixed-sample and 15/25 distributional deletion sizes in the Yelp hard case, with 14/25 pointwise paired 95% intervals wholly below zero in each model. This provides a tuning-free utility advantage in the stated regime. We include the complete Yelp dataset preprocessing and experimental reproduction protocol in the supplementary materials (YELP_PROTOCOL.md). Table 2 (pp.39-40 of the revised manuscript) reports results for Algorithms 2 and 6 (the previous version) using their untuned switching rules with codes in table2_cstar13_gamma05.py.

[1] Differential Privacy.

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

This paper proposes a machine unlearning method in offline stochastic multi-armed bandits. The authors formalize the privacy constraint and measure utility by post-unlearning decision quality. They systematically investigate two data-generation models: the fixed-sample model and the distribution model, covering single-source requests in both and extending to multi-source deletion in the fixed-sample setting. For these settings, the proposed adaptive algorithms dynamically switch between two base mechanisms, namely the downward-shifted Gaussian mechanism and rollback, according to the data regime and privacy constraints. The paper establishes theoretical performance guarantees and lower bounds under both dataset models, and experiments validate the predicted trade-offs and the effectiveness of the proposed methods.

Critical strengths

(+) The paper establishes a clear analytical framework for unlearning in this foundational decision-making problem.

(+) The statistical trade-off between exact rollback and the approximate mechanism is insightful.

Critical weaknesses

(-) The practical gain of the approximate mechanism relative to the cheap exact rollback is not yet sufficiently supported. I acknowledge that the authors admit on page 2 that exact rollback is computationally cheap and position the goal at statistical utility. Therefore, my question is: under what specific deletion demands and protection strengths is it worthwhile to adopt the proposed approximate mechanism? The current description of the recommendation service does not sufficiently explain the correspondence among arms, rewards, and deletion requests. In particular, it does not clarify why deletion is independent of rewards, and why output-level guarantees that allow a trusted internal state to retain historical statistics are suitable for this scenario. A more direct evidence issue is that, on page 40, the multi-source experiments at delta=0.1 report two calibrated budgets of ≈1.2506 × 10^7 and ≈ 1313.0903, respectively. These very loose certificates are insufficient to demonstrate a significant utility advantage over exact rollback under meaningfully binding unlearning guarantees. This concern targets the strength of the experimental support and does not mean that the actual outputs have been proven to leak to the corresponding degree. The paper needs to more clearly explain the correspondence between the application and the guarantees, and provide a utility comparison with a clear justification for the budget choices.

(-) The lower bound conclusion in Theorem 6 lacks the necessary coverage condition. The main text only requires that the other arm has sufficient sample coverage, whereas the proof in the appendix also relies on the arm to which the deleted samples belong satisfying the corresponding coverage condition (page 7 of the main text, page 20 of the appendix). Without this condition, in some allowed instances, the optimal arm can be determined solely based on the coverage constraint, resulting in zero decision loss, which contradicts the positive lower bound claimed in the theorem. The authors need to add the necessary condition, unify the presentation in the main text and the appendix, and clarify whether the correction affects the conclusion regarding the matching of upper and lower bounds. Theorem 15 and its proof on page 20 adopt a stronger coverage condition and treat the source arm as one of the two arms with sufficient coverage. The authors should clarify that the source arm is also eligible to be the optimal arm in the allowed instances, and align the main text, the appendix, and the discussion on the matching of upper and lower bounds. This issue appears to be fixable by adding assumptions, but the current version overstates the applicability of the lower bound conclusion.

Questions for authors

Q1: The authors need to make a clarification of the application and guarantee.

Q2: The authors need to explain the lower-bound claim in Theorem 6 lacks a necessary coverage condition.

See Critical Weaknesses part for more details.

1 comment

We thank you for your constructive and detailed feedback.

[Weakness 1 and Question 1] Application and guarantee. Due to space constraints, our application example was briefly presented, and we apologize for the lack of clarity. Consider an e-commerce recommendation service where each arm represents a product and each reward represents user feedback, such as a click. For example, after a promotional campaign ends, the service may be required to remove its interaction records from the dataset DD under a predefined data-use policy. Such deletions are determined by the campaign period rather than observed rewards, consistent with our reward-independence assumption. In this setting, the data-use policy may permit the service to retain the deletion descriptor within a trusted backend, while requiring an output-level unlearning guarantee for externally observable outputs. Since these interactions are not highly sensitive, the application may prioritize recommendation quality under a relatively relaxed privacy requirement. Our formulation captures this trade-off by protecting the observable recommendation while allowing the trusted service to retain internal statistics.

Regarding practical utility, our main contribution is to establish a theoretical framework for understanding the privacy–utility trade-off in offline bandit unlearning. Our analysis reveals two distinct statistical costs: when the deleted arm is optimal and the deletion size increases, rollback suffers from reduced sample coverage, whereas Gaussian perturbation may achieve better utility at the cost of privacy noise. This insight motivates our adaptive mechanism-selection framework, which can potentially extend beyond the specific mechanisms studied here. We acknowledge that we overlooked the large privacy budgets in some experiments, which limits their practical significance under meaningful privacy constraints. Nevertheless, we believe that identifying this previously unexplored trade-off provides a valuable foundation for future research on unlearning in decision-making systems. We hope to further improve the practical relevance of our framework by exploring alternative perturbation mechanisms, such as the Laplace mechanism, that may offer better privacy–utility trade-offs.

[Weakness 2 and Question 2] Coverage condition in Theorem 6. We thank the reviewer for pointing out this omission in the main text. Theorem 6 should explicitly require that at least two arms have at least N⋆N_{\star} observations. This allows us to construct two instances where a0a_0 is optimal in one instance but suboptimal in the other, with both candidate optimal arms having at least N⋆N_{\star} observations. Thus, both instances satisfy the coverage condition used in our analysis.

For the upper bound, we only require N(a⋆)≥N(a^{\star}) \ge N⋆N_{\star}. If only one arm has at least N⋆N_\star observations, the optimal arm can be directly identified from the coverage condition, making the problem trivial. We therefore do not discuss this degenerate case separately. We have corrected the statement of Theorem 6 and clarified the discussion on the matching of upper and lower bounds in the corresponding remark in the revised PDF.

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

This paper proposes unlearning offline bandits. In this setting, an offline bandits algorithm already learned a policy π\pi from a dataset DD. Unlearning requires that, given a subset U⊂DU\subset D, the output policy should be similar to that learned from D−UD - U. The paper proposes an algorithm that can adaptively choose between rollback and Gaussian mechanism. It proves the upper bound of the proposed algorithm and a nearly matching lower bound.

Critical strengths
  1. The problem is interesting and there is a great potential along this direction.
Critical weaknesses
  1. The scope is somewhat limited. It is restricted in stochastic multi-armed bandits.
  2. Also because of this simple model, it is hard to verify why we need another algorithm than simple rollback. For example, in the last page, the experiment somehow derives a privacy budget ε≈107\varepsilon\approx 10^7, which indicates Gaussian mechanism requires nearly no privacy guarantee, and therefore no need to unlearn, which is contradict to the motivation of this paper.
Questions for authors
  1. Can authors clearly explain, when the Gaussian mechanism should be used and what are some possible examples showing rollback has clear disadvantage.
2 comments

We thank you for your constructive and detailed feedback.

[Weakness 1] Scope of our paper. We deliberately choose stochastic MAB as a foundational decision-making setting to initiate the study of certified unlearning beyond supervised and unsupervised learning. To the best of our knowledge, this is the first systematic study of certified unlearning for offline stochastic bandits. This setting allows us to formalize the problem, identify the fundamental privacy–utility trade-off, and establish upper and lower bounds, providing a theoretical foundation for future research on unlearning in more general decision-making problems.

Our framework also provides a natural starting point for extensions to contextual and offline linear bandits. For contextual bandits, the LCB-based approach of Rashidinejad et al. [1] allows our mechanism to be applied to individual context–action pairs. For offline linear bandits, the PUNC algorithm of Li et al. [2] generalizes LCB-based learning to linear reward models, providing a basis for extending our rollback and Gaussian perturbation mechanisms. These extensions require additional sensitivity and utility analyses, which we leave for future work.

[Weakness 2 and Question 1] Motivation beyond rollback and privacy budgets. Our main contribution is to establish a theoretical framework for understanding the privacy–utility trade-off in offline bandit unlearning, rather than simply proposing an alternative to rollback. Our analysis reveals two distinct statistical costs: when the deleted arm is optimal and the deletion size increases, rollback suffers from reduced sample coverage, while Gaussian perturbation may achieve better utility at the cost of privacy noise. This insight motivates our adaptive mechanism-selection approach, which we believe is applicable beyond the specific Gaussian mechanism studied here.

We acknowledge that we overlooked the large privacy budgets in some experiments, which limits their practical significance under meaningful privacy constraints. Nevertheless, we believe that identifying this previously unexplored trade-off and developing an adaptive framework represent meaningful steps toward understanding unlearning in decision-making systems. We hope to build on these insights by exploring alternative perturbation mechanisms, such as the Laplace mechanism, to achieve better privacy–utility trade-offs in future work.

[1] Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism.

[2] Pessimism for Offline Linear Contextual Bandits using ℓp\ell_p Confidence Sets.

Thanks for the responses. Given the current the form, I am still concern about the privacy-utility trade-off. Unlearning in decision-making may be a new formulation, but from this simple model and the results, it is hard to justify its importance and practical relevance. I decide to keep my score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.