Conceptio › Archive › arXiv CS

arXiv CSopen access

Unlearning Offline Stochastic Multi-Armed Bandits

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

neural-networks

machine learning, deep learning, neural networks

Unlearning Offline Stochastic Multi-Armed Bandits

Zichun Ye * 1 Runqi Wang * 1 Xuchuang Wang 2 Xutong Liu 3 Shuai Li 1 Mohammad Hajiesmaili 2

arXiv:2605.00638v1 [cs.LG] 1 May 2026

Abstract

this information can be extracted through inference attacks (Shokri et al., 2017; Carlini et al., 2019). Motivated by the demand for unlearning, a growing line of work (Ginart et al., 2019; Guo et al., 2020; Gupta et al., 2021; Mehta et al., 2022; Zhang et al., 2022; Yuan et al., 2025) studied machine unlearning—updating a trained model so that the influence of a specified subset of training data is removed, ideally without retraining from scratch.

Machine unlearning aims to unlearn data points from a learned model, offering a principled way to process data-deletion requests and mitigate privacy risks without full retraining. 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 of both single- and multi-source unlearning scenarios under two datageneration models, the fixed-sample model and the distribution model. For these settings, our algorithmic design is built on two canonical base algorithms: Gaussian mechanism and rollback, and we propose adaptive algorithms that switch between them according to the data regime and privacy constraint. We further introduce a mixing procedure that elucidates the rationale behind these baselines. We provide performance guarantees across the above settings and establish lower bounds under both dataset models. Experiments validate the predicted tradeoffs and demonstrate the effectiveness of the proposed methods.

To formalize when data removal is sufficient, Ginart et al. (2019) introduced a probabilistic notion of unlearning, inspired by differential privacy (Dwork et al., 2014). Building on this foundation, a line of work studied supervised machine unlearning (Guo et al., 2020; Izzo et al., 2021) and unsupervised machine unlearning (Neel et al., 2021; Gupta et al., 2021; Ullah et al., 2021). Most of these results focused on the empirical risk minimization (ERM) setting, aiming to minimize the training loss on the retained dataset after deleting the requested samples, and several approaches are memory intensive (Bourtoule et al., 2021; Gupta et al., 2021). To address these limitations, Sekhari et al. (2021) introduced an unlearning definition that incorporated both test-performance guarantees and explicit storage constraints. Building on this framework, (Suriyakumar & Wilson, 2022) studied online unlearning request and (Liu et al., 2023) investigated unlearning for minimax models. While substantial progress has been made in supervised / unsupervised machine unlearning, the landscape is far less understood in sequential decision-making paradigm such as multi-armed bandits (MAB) or reinforcement learning (RL). Recent work (Ye et al., 2025) has begun exploring reinforcement unlearning and highlights that RL agents may memorize sensitive properties of environments. However, existing formulations primarily target environment-level unlearning and do not address the data-sample deletion guarantees central to machine unlearning. Moreover, they do not quantitatively formalize a privacy-style constraint, and therefore provide no sharp characterization of the resulting privacy-utility tradeoff. As a result, unlearning for decisionmaking still remains largely unexplored.

1. Introduction Modern machine learning systems are increasingly trained on third-party and user-generated data, from images to texts used in recommendation or advertising (Chen et al., 2019; Tang et al., 2023). When a user requests that certain records be deleted (unlearned) from the offline dataset, it is no longer enough to merely remove the raw data: trained models may still retain information about the deleted records, and *

Equal contribution 1 Shanghai Jiao Tong University, Shanghai, China 2 University of Massachusetts Amherst, Massachusetts, United States 3 University of Washington, Tacoma, United States. Correspondence to: Xutong Liu <[email protected]>, Shuai Li <[email protected]>.

In this work, we take a first step by studying data-level unlearning for more fundamental decision-making primitive of offline stochastic multi-armed bandits. Offline MAB learning studies how to select the best arm purely from an offline

Preprint. May 4, 2026.

Unlearning Offline Stochastic Multi-Armed Bandits Table 1. Theoretical results for the unlearning problem under various settings.

Model⋆

Unlearning Type◦

Single

Fixed-sample model (Mf )

Multi

Distribution model (Md )

⋆

Single

Results†  q q  ln(N m) ln(N m) kγ  , γ < γ0 O max N (a0 ) + N (a0 ) , N∗ q Upper bound: q  ln(N m) ln(N m)  , γ ≥ γ0 O max N (a0 )−k , N∗ q Lower bound: Ω e−ε N (a10 )−k  q q  ln(N m) ln(N m) kmax γ  , γ < γ0′ O max Nmin + Nmin , N∗ Upper bound: q q  ln(N m) ln(N m)  , γ ≥ γ0′ O max Nmin −kmax , N∗ q q C ∗ ln(N m) C ∗ ln(N m) kγC ∗ + N Upper bound: O min max{1,N −2kC ∗ } , N C ∗ ∈ [2, ∞) : q ∗ Lower bound: Ω e−ε NC−k (N −k) (N +k) C∗ 2 Upper bound: O e− 2 ln 8(C ∗ −1) + 2 ln C ∗ C ∗ ∈ (1, 2) : ∗ 2 Lower bound: Ω (2 − C ∗ )e−ε−(N −k)(2−C ) ln( C ∗ −1 )

A is the set√of base arms, |A| = m. N (a) denotes the sample counts of arm a in the offline dataset D, |D| = N . For (ε, δ)-unlearning, 2 ln 1.25

δ denote γ = . Mf has the assumption that N (a∗ ) ≥ N∗ , while Md assumes that the behavior policy satisfies d(a∗ ) ≥ C1∗ . ε More details are given in Section 2. ◦ Single-source unlearning means only one arm (i.e. a0 ) makes an unlearning request U . Let |U | = k. Multi-source unlearning means at least two arms make the request, denote them as {aui }ℓi=1 . And the unlearning request Ui from aui satisfies |Ui | = ki . q q m) ln(N m) † For single-source, γ0 = 34 πNln(N . For multi-source, Nmin = mini∈[ℓ] N (aui ), kmax = maxi∈[ℓ] ki , γ0′ = 43 Nπmin . (a0 )−k −kmax

dataset, without any additional exploration. The objective is to minimize the expected sub-optimality, which is the gap of mean reward between the best arm a∗ and the output arm â. Unequal arm coverage is a central challenge in offline learning and directly motivates the pessimism principle. Concretely, pessimism discounts poorly supported arms through lower confidence bound (LCB) estimates, and has been widely adopted with minimax-optimal guarantees (Rashidinejad et al., 2021; Li et al., 2022).

dard offline dataset models: the fixed-sample model and the distribution model. We also distinguish single- and multisource unlearning based on how many arms the unlearning request U comes from. Algorithms and theoretical results. We propose two unlearning base algorithms, the Gaussian mechanism and rollback, and develop unlearning algorithms that combine them across the above settings. Leveraging the learned model (arm), we detect whether the request U comes from a∗ , and choose between the two base algorithms according to the privacy constraint and problem parameters. Our analysis draws on pessimism principles from offline bandit learning. The results yield a simple guideline: when U comes from a∗ and the privacy constraint is relatively loose, the Gaussian mechanism yields better performance; otherwise, rollback is preferable. We also introduce a mixing procedure to motivate this baseline design. We complement our upper bounds with lower bounds for single-source unlearning under both dataset models. When ε is small, our bounds are near-tight up to logarithmic factors in several regimes, including under Mf when N∗ ≥ N (a0 ) − k and under Md . Theoretical results are summarized in Table 1.

Since conventional machine unlearning methods are not directly applicable due to fundamental differences, our goal is to address two questions: (1) How can we design unlearning algorithms, and what is the trade-off between sub-optimality and privacy? (2) Under the same privacy constraint, which unlearning mechanism yields better sub-optimality? Our contributions. Problem formulation. We initiate the study of (ε, δ)-unlearning for offline stochastic MAB. Our definition follows the general framework of Sekhari et al. (2021); Suriyakumar & Wilson (2022); Liu et al. (2023), which captures both performance on unseen test data and storage constraints. We evaluate utility via post-unlearning sub-optimality, and to systematically characterize how unlearning affects learning performance, we study two stan-

Extensive experiments. We conduct extensive experiments on synthetic offline MAB datasets to validate our theo2

Unlearning Offline Stochastic Multi-Armed Bandits

Differential privacy. A closely related line of work (Chen et al., 2020; Ren et al., 2020; Zheng et al., 2020; Tao et al., 2022; Zhou & ZHANG, 2024) studies MAB under differential privacy (DP), especially local differential privacy (LDP), where users do not trust the server and thus each user-side curator applies a DP mechanism to the raw reward (or context / arm) before it is revealed to the learner. This privacy model could be applied to offline learning (Zhou & ZHANG, 2024), where one may privatize each data point and then run an offline learner on the privatized dataset. Importantly, DP/LDP can be seen as a sufficient condition for unlearning (Guo et al., 2020; Sekhari et al., 2021; Liu et al., 2023). The downside is that achieving DP/LDP typically requires adding substantial noise, which may degrade decision quality. This motivates our central viewpoint: when unlearning from an offline dataset, we can do better than perturbing every data point by leveraging the structure of the requested deletions to achieve lower sub-optimality under the same privacy constraint.

retical findings and evaluate empirical performance. For both dataset models, our proposed algorithms consistently achieve competitive or superior performance compared to several baselines, and effectively select between Gaussian mechanism and rollback depending on the data regime and privacy constraint. These results demonstrate the robustness of our approach across different settings, and highlight the benefits of adaptivity in offline bandit unlearning. 1.1. Related Work Machine unlearning. Machine unlearning was first proposed in Cao & Yang (2015), and Ginart et al. (2019) subsequently introduced a DP-inspired notion of unlearning that has served as the foundation for much of the later literature. Existing unlearning algorithms draw on a range of techniques, including perturbed gradient descent (Neel et al., 2021; Ullah et al., 2021), projected residual updates (Izzo et al., 2021), and Newton-style updates (Guo et al., 2020; Sekhari et al., 2021; Suriyakumar & Wilson, 2022; Liu et al., 2023). The first two approaches are typically analyzed through training loss and can incur substantial storage overhead, whereas Newton-style updates could provide test loss performance and storage-efficient implementations. Despite this progress, decision-making systems have received far less attention. Our work builds on the Newton-style updates, which applies a Newton step on the model parameters that largely removes the influence of the deleted samples. This method directly motivates the Gaussian mechanism and rollback components in our algorithm design.

2. Preliminaries In this section, we introduce the model of offline stochastic MAB, including its learning and unlearning problems. 2.1. Learning for Offline Stochastic MAB Offline dataset. We focus on offline stochastic MAB. The environment has a set of base arms A denoted by [m] = {1, · · · , m}. Pulling arm a ∈ A yields a random reward r ∈ [0, 1] drawn from a fixed but unknown distribution R(a) with mean µ(a) = Er∼R(a) [r]. An offline dataset D = N {(ai , ri )}i=1 of size N is generated from these distributions, where the reward component always follows ri ∼ R(ai ) N and the arm component {ai }i=1 depends on the dataset ∗ model. Let a = arg maxa∈A µ(a) denote the best arm. We let N (a) be the sample counts of arm a in D and Z be the data point space. Therefore D ∈ Z N .

Learning for offline stochastic multi-armed bandits. Offline (or batch) learning has attracted substantial recent attention in settings where additional exploration is costly or impossible. A growing body of work studies offline RL (Fujimoto et al., 2019; Kidambi et al., 2020; Yu et al., 2020; Kumar et al., 2020; Ghasemipour et al., 2021), while parallel lines develop theory for offline bandits, including pessimism-based analyses for offline MAB and contextual MAB (Rashidinejad et al., 2021), similar methods for offline linear contextual bandits (Li et al., 2022), and more recently offline combinatorial MAB (Liu et al., 2025). Across these problems, performance hinges on coverage of the arm space, and different data-collection models yield different assumptions and guarantees. In offline MAB, two standard models are the fixed-sample model, where per-arm counts are fixed in advance (Xiao et al., 2021; Li et al., 2022; Lee et al., 2022; Wang et al., 2022), and the distribution model, where arms are drawn i.i.d. from a behavior policy (Rashidinejad et al., 2021; Zhou & ZHANG, 2024; Liu et al., 2025). However, unlearning has not been systematically studied in offline bandits. And we fill this gap by analyzing offline bandit unlearning under both models and characterizing the resulting privacy-utility tradeoff.

To comprehensively study unlearning, we consider two standard offline dataset models which decide the per-arm sample counts in D: the fixed-sample model Mf and the distribution model Md . Under Mf (Li et al., 2022; Lee et al., 2022; Wang et al., 2022), the sample-count vector N ∈ Nm is fixed in advance with ∥N ∥1 = N . The only randomness in D(N ) comes from the rewards. Under Md (Rashidinejad et al., 2021; Zhou & ZHANG, 2024; Liu et al., 2025), each arm ai is sampled i.i.d. from a behavior policy d ∈ ∆(A), and then ri ∼ R(ai ). Equivalently, each data point is sampled i.i.d. from the joint distribution D := d ⊗ R, i.e., (ai , ri ) ∼ D and D ∼ DN . Data coverage condition. Under the fixed-sample model Mf , to guarantee the learning algorithm’s performance, we 3

Unlearning Offline Stochastic Multi-Armed Bandits

require that for every dataset D(N ), a∗ satisfies N (a∗ ) ≥ N∗ for some constant N∗ . Under the distribution model Md , following Rashidinejad et al. (2021), we assume a finite concentrability coefficient C ∗ > 1 such that d(a∗ ) ≥ C1∗ . The parameter C ∗ captures deviation between the behavior policy d and the distribution induced by the optimal algorithm. It also serves to guarantee the performance via the Chernoff bound on N (a∗ ).

then unlearned with U and (2) the model trained on D \ U and then unlearned with an empty set. We emphasize that ∅ in (2) is a fictitious request therefore additional information about the realistic request U will also be stored in T (D \ U ). The (ε, δ)-UL requirement acts as a constraint in our optimization problem. Our objective is to minimize the expected sub-optimality between â′ and a∗ , subject to π ′ , π satisfying (ε, δ)-UL. More formally, under Mf , SubOpt(N , N∗ , k, ε, δ) =

Performance Metrics. A learning algorithm π trains on D and outputs an arm â ∈ A, i.e., π : Z N → A. The goal of the learning algorithm is to minimize the sub-optimality

inf

sup

π ′ ,π:(ε,δ)−U L D(N ),U ⊆D

E [µ(a∗ ) − µ(â′ )] ,

while under Md , SubOpt(N, C ∗ , k, ε, δ) =

Mf : inf sup E [µ(a∗ ) − µ(â)] , π D(N )

inf

Md : inf sup E [µ(a∗ ) − µ(â)] ,

sup

π ′ ,π:(ε,δ)−U L D∼D N ,U ⊆D

π D∼D N

E [µ(a∗ ) − µ(â′ )] .

where the expectation is taken over the generation of D and output of π. We take the LCB algorithm of Rashidinejad et al. (2021) as our default learning algorithm. This choice is motivated by its minimax-optimal guarantees under both Mf and Md when C ∗ ≥ 2. Details of LCB algorithm are provided in Section 3. For the regime C ∗ ∈ (1, 2) under Md , imitation learning leads to a sharper guarantee and we present this as an extension in Section 3.3.

The expectation is taken over the generation of D and output of π and π ′ . Throughout this paper, we assume that U is selected independently of the reward in each data point. Consequently, the empirical mean reward of each arm computed from D \ U remains an unbiased estimator of its true mean. We call the request single-source if all samples in U come from the same arm, and multi-source if U contains samples from multiple arms.

2.2. Unlearning for Offline Stochastic MAB

3. Our Results

Given an offline dataset D, an unlearning request specifies a subset U ⊆ D of size |U | = k to be deleted. In addition to the learned decision π(D) ∈ A, the unlearning procedure is allowed to access a stored statistic T (D) ∈ T , which summarizes D but does not contain the full dataset and is intended to facilitate efficient unlearning. An unlearning algorithm π ′ then takes (U, π(D), T (D)) as input and outputs an updated arm â′ ∈ A, i.e., π ′ : Z k × A × T → A. Let ∅ be the empty request. We follow the definition of (ε, δ)-unlearning in Sekhari et al. (2021); Liu et al. (2023).

Challenges of unlearning in offline bandits involve a privacyutility trade-off and must also account for storage and computation. Unlike classical machine unlearning, the effect of deletions depends on the source of U (i.e., which arm the deleted samples come from). Finally, the algorithm design and analysis must adapt to the data-generation models. In this section, we first present the learning algorithm and its sub-optimality guarantee, and then introduce two unlearning primitives, the Gaussian mechanism and rollback. Next, in Section 3.1, we propose an adaptive algorithm for singlesource unlearning under both Mf and Md and establish upper bounds. In Section 3.2, we prove lower bounds for single-source unlearning under both models. In Section 3.3, we introduce a mixing procedure to motivate the two base algorithms and present an improved learning-unlearning pair for Md when C ∗ ∈ (1, 2). Finally, we extend to multisource unlearning under Mf and establish an upper bound.

Definition 2.1 ((ε, δ)-unlearning ((ε, δ)-UL) (Sekhari et al., 2021; Liu et al., 2023)). A privacy-preserving data-removal mechanism π ′ : Z k × A × T → A performs (ε, δ)-UL for a learning algorithm π : Z N → A, if for all D ⊆ Z N , U ⊆ D, A ⊆ A: Pr [π ′ (U, π(D), T (D)) ∈ A] ≤ eε · Pr [π ′ (∅, π(D \ U ), T (D \ U )) ∈ A] + δ,

The Lower Confidence Bound algorithm. Denote µ̂(a), b(a) as the empirical mean and the penalty term of arm a respectively. Algorithm 1 calculates the LCB: µ̂(a) − b(a) for every arm based on D and outputs the arm with the largest LCB. And we have an upper bound as follows.

and Pr [π ′ (∅, π(D \ U ), T (D \ U )) ∈ A] ≤ eε · Pr [π ′ (U, π(D), T (D)) ∈ A] + δ.

Lemma 3.1 (Theorem 1 (Rashidinejad et al., 2021)). N For any offline dataset D = {(ai , ri )}i=1 , |A| =

Theorem 2.1 characterizes the indistinguishability between the output distribution of (1) the model trained on D and 4

Unlearning Offline Stochastic Multi-Armed Bandits

m, the arm â returned by Algorithm 1 follows that q ∗

2 ln m τ N∗

Mf : E [µ(a ) − µ(â)] ≤ q C ∗ ln m τ E [µ(a∗ ) − µ(â)] ≤ 2 + 2τ . N

3.1. Unlearning Algorithms and Upper Bounds

+ τ , and Md :

In this section, we consider the single-source unlearning under both models, where U comes from arm a0 and |U | = k. We propose Algorithm 2 below. The algorithm takes as input the learned arm â from Algorithm 1, the unlearning c and a confib N request U , additional statistics fb(D), µ, c dence level τ . Under Mf , N = N is fixed, whereas under Md it is sampled from behavior policy d. The key design principle is to trade off Gaussian mechanism and rollback. Intuitively, when a0 coincides with the best arm and the privacy constraint is relatively loose, adding appropriately calibrated Gaussian noise preserves performance. In all other cases, rollback is preferable. Concretely, Algorithm 2 adds Gaussian noise if â = a0 and γ < γ0 ; otherwise, it performs rollback. Detailed proofs are given in Section A.1.

Algorithm 1 LCB algorithm (Rashidinejad et al., 2021) N

Input: Dataset: D = {(ai , ri )}i=1 , a confidence level: τ ∈ (0, 1) PN 1: Set N (a) ← i=1 1 [ai = a] for all a ∈ A 2: for a ∈ A do 3: if N (a) = 0 then 4: Set the empirical mean reward µ̂(a) ← 0 5: Set the penalty b(a) ← 1 6: else Compute the empirical mean reward µ̂(a) ← 7: P N i=1 ri 1[ai =a]

Algorithm 2 Single-source unlearning algorithm Input: Output of π(D): â, unlearning request: U from c, a b N a0 , |U | = k, additional statistics T (D): fb(D), µ, confidence level: τ ∈ (0, 1) q π ln m τ 1: Set fb(D ′ ) ← fb(D), γ0 ← 34 N (a0 )−k 2: if (â = a0 ) and (γ < γ0 ) then 3: Set ∆f ← 2N3k (a0 ) , σ ← ∆f γ 4: Sample ν ∈ R from N (0, σ 2 ) Set fb(a0 ) (D′ ) ← fb(a0 ) (D′ ) + ν {Gaussian Mecha5: nism} 6: else 7: Set N ′ (a0 ) ← N (a0 ) − k 8: Compute thePnew empirical mean reward µ̂′ (a0 ) ←

N (a)

Compute the penalty b(a) ←

ln m τ 2N (a)

9: end if 10: end for

Output: â = arg maxa µ̂(a) − b(a)

Two unlearning base algorithms. Our algorithms are built around two canonical extremes derived from Newtonstyle updates: Gaussian mechanism and rollback. The Gaussian mechanism adds calibrated Gaussian noise to the learner’s output (e.g., the LCB of each arm) so that the released result satisfies the desired (ε, δ)-UL constraint. In contrast, rollback efficiently removes the request U from the stored statistics and recomputes the learner’s output on the retained dataset D \ U , which is equivalent to retraining on D \ U for offline bandit learner since the learner depends only on the LCB. Our adaptive procedures compare these two base algorithms under the same privacy budget and select the one that yields smaller sub-optimality.

µ̂(a0 )·N (a0 )− (a ,r )∈U ri 0 i N ′ (a0 )

q ln m τ Compute the new penalty b′ (a0 ) ← 2N ′ (a 0) 10: Set fb(a0 ) (D′ ) ← µ̂′ (a0 ) − b′ (a0 ) {Rollback} 11: end if Output: â′ = arg maxa fb(a) (D′ ) 9:

c b N Notations. For the rest part of Section 3, we denote µ, as the empirical mean vector and the empirical sample-count vector computed from D respectively. Denote f : Z ∗ → Rm as the function which calculates the LCB of each arm and arranges them in a vector based on a certain dataset. For any vector ν, let ν(i) be the i-th dimension of ν. Therefore fb(i) (D) is the LCB of the i-th arm on dataset D. Let γ = √ 1.25 2 ln δ , D′ = D \ U . Due to notational convenience and ε space constraint, we only provide unlearning algorithms when unlearned with the realistic non-empty set U . For algorithms when unlearned with the empty set, we place them in Section A. They are included only as references in proving (ε, δ)-UL.

Theorem 3.2. Algorithm 2 and Algorithm 1 are (ε, δ)unlearning under both Mf and Md . To more finely characterize how the sample counts of the unlearned arm a0 and the optimal arm a∗ in D affect sub-optimality, we first study Mf , where the per-arm sample counts are fixed. We provide an upper bound of SubOpt(N, N∗ , k, ε, δ). Theorem 3.3 (Mf ). Consider any offline dataset D(N ), ∗ any unlearning request q U from a0 . N (a ) ≥ N∗ , |U | = k. N (a ) ln m

0 τ When k ≤ N (a0 ) − , by setting τ = N1 , the 2 ′ arm â returned by Algorithm 2 satisfies when γ < γ0 =

Unlearning Offline Stochastic Multi-Armed Bandits 4 3

π ln(N m) N (a0 )−k ,

 O max

to utilize the definition of (ε, δ)-UL and apply Le Cam’s method on two similar instances. Detailed proofs are given in Section A.2. 1 Theorem 3.7 (Mf ). Let ε ≥ 0, δ ≤ 8√ . For any unlearne ing request U from a0 , the lower bound sub-optimality of q satisfies SubOpt(N , N∗ , k, ε, δ) = Ω e−ε N (a10 )−k .

SubOpt(N , N∗ , k, ε, δ) =

s  ln (N m)

kγ + , N (a0 ) N (a0 )



 ln (N m)  . N∗ 

while when γ ≥ γ0 , SubOpt(N , N∗ , k, ε, δ) =  s  s   ln (N m) ln (N m) . , O max  N (a0 ) − k N∗ 

Remark 3.8. If N∗ ≥ N (a0 ) − k, our upper bound is dominated by the first term. In this regime, the lower bound matches the upper bound up to a logarithmic factor when ε is relatively small. 1 Theorem 3.9 (Md ). Let ε ≥ 0, δ ≤ 8√ . For e any single-source unlearning request U , when C ∗ ∈ [2, ∞), the lower bound of sub-optimality q

Remark 3.4. Our proof reveals that when a0 = a∗ , the performance of Algorithm 2 is guaranteed by the learning algorithm (Algorithm 1), corresponding to the second term in the upper bound. When a0 ̸= a∗ , the performance of Algorithm 2 is the minimum of the Gaussian mechanism and rollback guarantees, with the dominating term switching as the privacy constraint γ varies; this trade-off is captured by the first term in the upper bound. The threshold γ0 is defined by comparing the two corresponding bounds, namely the value at which they coincide, and thus serves as the switching point between the two regimes.

satisfies SubOpt(N, C ∗ , k, ε, δ)

3.3.1 The Mixing Algorithm. To justify the rationale behind our baselines, we introduce a mixing procedure under Mf as a control baseline (as an example, we choose Mf , we could obtain the same conclusion under Md ). The mixing procedure interpolates between pure Gaussian perturbation and pure rollback. It introduces an additional parameter k ′ ∈ [0, k] that uniformly selects a subset U ′ ⊆ U to be handled via rollback first; it then adds Gaussian noise calibrated to the sensitivity of the remaining requests U \ U ′ . We show that, under the same privacy constraint, this mixing procedure cannot outperform the better of the two extremes. The algorithm and the corresponding analysis are deferred to Section A.3. In Section 4, we also include experiments that corroborate this conclusion and use the mixing procedure as an additional baseline.

N (a ) ln m

( ∗

SubOpt(N, C , k, ε, δ) = O min C ∗ ln (N m) kγC ∗ + N N

3.3. Extensions

0 τ N > 8C ∗ ln N and k ≤ N (a0 ) − , by setting 2 1 ′ τ = N , the arm â returned by Algorithm 2 satisfies

C∗ N −k

Remark 3.10. When C ∗ ∈ [2, ∞), the lower bound matches the upper bound up to a logarithmic factor when ε is relatively small. When C ∗ ∈ (1, 2), the lower bound exhibits an e−N dependence on N , which is much smaller than the generic upper bound. This motivates us to draw on ideas from imitation learning to design new learning-unlearning pairs in Section 3.3.

Theorem 3.5 (Md ). Consider any offline dataset D ∼ DN , where the behavior policy satisfies d(a∗ ) ≥ C1∗ for some C ∗ > 1, any unlearning request U q from a0 . |U | = k. When

C ∗ ln (N m) , max {1, N − 2kC ∗ }

Ω e−ε

while C∗ ∈ (1, 2), SubOpt(N,C ∗ , k, ε, 0) ∗ 2 ∗ −ε−(N −k)(2−C ) ln( C ∗ −1 ) . Ω (2 − C )e

We further consider Md , where the per-arm sample counts can vary every time. Despite this additional randomness, Algorithm 2 continues to achieve good performance as under Mf . The resulting bounds depend on the N , k, and the coverage parameter C ∗ , rather than on a fixed realization of the sample-count vector. Again we give the upper bound of SubOpt(N, C ∗ , k, ε, δ).

)! .

Remark 3.6. Under Md , similarly, when a0 = a∗ , the performance is governed by Algorithm 1, corresponding to the second term in the upper bound. When a0 ̸= a∗ , the performance is the better of the Gaussian mechanism and rollback guarantees, and the dominating term switches with the privacy constraint γ, which is captured by the first term.

3.3.2 Improved Results for C ∗ ∈ (1, 2). When C ∗ ∈ (1, 2) is known, an imitation learning rule can yield a faster dependence on N in the offline MAB setting by simply returning the most frequently selected arm in the dataset D (Rashidinejad et al., 2021). Motivated by this improvement, we design Algorithm 6 to enhance the performance under this regime, which is (0, 0)-UL with imitation learning. We have the following upper bound. The pseudo-code and corresponding analysis are deferred to Section A.4. Then we have the following upper bound.

3.2. Lower Bounds In this section, we present the lower bounds under both models for single-source unlearning. The proof idea is 6

Unlearning Offline Stochastic Multi-Armed Bandits

4. Experiments

Theorem 3.11 (Md ). Consider any offline dataset D ∼ DN , where d(a∗ ) ≥ C1∗ for some C ∗ ∈ (1, 2), any unlearningnrequest U from o a0 . |U | = k.

When k ≤ min

∗

3N (2−C )N 4 , C∗

In this section, we report experimental results on synthetic datasets. We compare Algorithm 2 with several baselines, including an Oracle, the Gaussian mechanism, rollback and the mixing algorithm under both Mf and Md . We also compare Algorithm 6 with Algorithm 2 when C ∗ ∈ (1, 2) under Md . The Oracle corresponds to Algorithm 1 executed on the original dataset without deletion, while all other methods operate on datasets subject to deletion. The mixing algorithm here refers to the k ′ = k2 case in Algorithm 4. Performance is evaluated in terms of the sub-optimality. In practice, we set γ0exp = 1.3 γ0 in all experiments to improve performance of algorithms. The theoretical guarantees remain unchanged with γ0exp . Additional experimental details for experimental settings and experimental results of Algorithm 4 and Algorithm 7 are deferred to Section B.

, the arm â′ re-

turned by Algorithm 6 satisfies SubOpt(N, C ∗ , k, ε, 0) = (N −k) (N +k) C∗ 2 O e− 2 ln 8(C ∗ −1) + 2 ln C ∗ . Remark 3.12. By switching the learning algorithm to an imitation learning rule and using rollback for unlearning, Theorem 3.11 yields a sharper upper bound with an e−N dependence on N when C ∗ → 1. This term matches the lower bound in Theorem 3.9 when C ∗ ∈ (1, 2). 3.3.3 Multi-Source Unlearning Algorithm Under Mf . For multi-source unlearning under Mf , the unlearning request U may involve multiple arms au1 , . . . , auℓ and Sℓ can be denoted as U = i=1 Ui , where Ui denotes the subset of deleted samples associated with arm aui for 1 ≤ i ≤ ℓ, and |Ui | = ki . We further define Nmin = mini∈[ℓ] N (aui ), kmax = maxi∈[ℓ] ki . We design Algorithm 7, which is (ε, δ)-UL with Algorithm 1. Its pseudo-code and corresponding analysis are deferred to Section A.5. Accordingly, the form of sub-optimality becomes SubOpt(N , N∗ , {ki }ℓi=1 , ε, δ). We now present the corresponding upper bound.

4.1. Experiments of the Fixed-Sample Model We generate 200 independent synthetic offline bandit datasets using a round-robin behavior policy over 5 arms with Bernoulli rewards µ = (0.10, 0.08, 0.06, 0.04, 0.02). To efficiently evaluate deletions, we adopt a prefix-sharing strategy (details in Section B.1). In both settings, each prefix undergoes 5 independent deletion requests. Both the hard case (a0 = a∗ ) and the easy case (a0 is the secondbest suboptimal arm) are considered, and results are averaged over 10 runs per configuration. We vary one of N , k, or γ while fixing the remaining two parameters to (N, k, γ) = (3000, 80, 0.5). Due to multiple sources of randomness, the variance across runs is heterogeneous. For clarity, we therefore report mean performance across runs.

Theorem 3.13 (Mf ). Consider any offline dataset D(N ), Sℓ any unlearning request U = i=1 Ui where Ui is selected from the data points of aui . q N (a∗ ) ≥ N∗ , |Ui | = N (a

) ln m

ui τ ki , ∀i ∈ [ℓ]. When ki ≤ N (aui ) − , ∀i ∈ [ℓ], 2 1 kmax < Nmin , by setting τ = N , the arm â′ returned q ln(N m) by Algorithm 7 satisfies when γ < γ0′ = 43 Nπmin −kmax ,

Figure 1 shows that Algorithm 2 consistently demonstrates robust and competitive performance across all settings under Mf , yielding low sub-optimality across a wide range of N , k, and γ. In the hard case, the algorithm adaptively balances k rollback and Gaussian mechanism: for large N , it favors k adding Gaussian noise, while for small N , it reliably selects rollback. Quantitatively, when varying N , Algorithm 2 achieves 35-77% and 39-73% reduction in sub-optimality relative to the Gaussian mechanism and mixing algorithm for N ≥ 2200, and 4-23% reduction relative to rollback for N ≤ 1300. In the easy case, the algorithm remains highly stable, consistently achieving at least a 76% improvement over Gaussian and staying within 11% of the best method. Similar trends are observed when varying k or γ, highlighting its overall robustness. Overall, Algorithm 2 consistently achieves low sub-optimality and ranks among the best or second-best methods across most regimes, while the baselines exhibit highly variable sub-optimality and perform well only in isolated settings.

ℓ

SubOpt(N , N∗ , {ki }i=1 , ε, δ) =  O max

s  ln (N m) Nmin



kmax γ + , Nmin

 ln (N m)  . N∗  ℓ

while when γ ≥ γ0 , SubOpt(N , N∗ , {ki }i=1 , ε, δ) =  O max

s  

ln (N m) , Nmin − kmax

 ln (N m)  . N∗ 

Remark 3.14. Our bound is consistent with the single-source case under Mf as a special instance: when ℓ = 1, we have Nmin = N (au1 ) = N (a0 ) and kmax = k1 = k, and the multi-source guarantee reduces to the corresponding singlesource bound. Future work includes designing multi-source unlearning algorithms and deriving upper bounds under Md , as well as establishing matching lower bounds for the multi-source setting. 7

Unlearning Offline Stochastic Multi-Armed Bandits

Gaussian 2

(a) Mf , hard case

5 ×103

SubOpt

5 ×102

(e) Mf , hard case

SubOpt

1.00 0.75 0.50 0.25 0.00 0.01 0.05 0.10 0.50 1.00 5.0010.00

(i) Mf , hard case

×10 2 2 1 ×10 3 2

(f) Mf , easy case

5 ×103

(d) Md , easy case

×10 2

2.0

×10 2

1.5 1.0 0.5

5 ×102

5 ×103

5 ×102

(g) Md , hard case

5 ×102

(h) Md , easy case

×10 2 2 1.00 1 ×10 3 0.75 2 0.50 1 0.25 0.00 0.01 0.05 0.10 0.50 1.00 5.0010.00 0 0.01 0.05 0.10 0.50 1.00 5.00 10.00

×10 2

SubOpt

×10 2

SubOpt

Alg2

×10 2

Mixing

(b) Mf , easy case

1.5 1.0 0.5

5 ×103

×10 2

Gaussian

SubOpt

Rollback

SubOpt

0.5

2.0 ×10

1.0

Oracle

×10 2

SubOpt

1.5

Alg2

SubOpt

×10 2

Mixing

SubOpt

Rollback

0 0.01 0.05 0.10 0.50 1.00 5.00 10.00

(j) Mf , easy case

SubOpt

Oracle

(k) Md , hard case

(l) Md , easy case

Figure 1. Comparison of Algorithm 2 with baselines under Mf (uniform) and Md (C ∗ = 5).

93% reduction in sub-optimality compared to Algorithm 2.

4.2. Experiments of the Distribution Model When C ∗ ∈ [2, ∞), we generate 200 independent synthetic offline datasets using a stochastic behavior policy that selects a∗ with probability 1/C ∗ , C ∗ = 5 and distributes the remaining probability uniformly over suboptimal arms. Other configurations are the same as those in Section 4.1. Figure 1 shows that Algorithm 2 also maintains robust and competitive performance under Md . In the hard case, it adaptively switches between Gaussian mechanism and rollk back based on N , reliably stabilizing performance. When varying N , Algorithm 2 achieves 21-72% and 24-68% reduction in sub-optimality relative to the Gaussian mechanism and mixing algorithm for N ≥ 2200, and 7-20% reduction relative to rollback for N ≤ 1300. In the easy case, the algorithm consistently attains at least a 70% improvement over Gaussian and remains either the best-performing method or within 10% of it. Similar trends are observed when varying k or γ. Overall, Algorithm 2 consistently maintains low sub-optimality across regimes, while the baselines suffer from pronounced variability in sub-optimality.

Table 2. Comparison of Algorithm 6 and Algorithm 2 under distribution model (C ∗ = 1.3). Sub-optimality

Algorithm Algorithm 6 Algorithm 2

N = 900

N = 1000

N = 1100

N ≥ 1200

0.0008 0.0120

0.0000 0.0115

0.0000 0.0110

0.0000 0.0000

5. Conclusion and Future Work In this paper, we introduce (ε, δ)-unlearning for offline stochastic MAB. We design adaptive algorithms for singlesource unlearning under both the fixed-sample and distribution models, and provide upper and lower bounds in both models. We further develop extensions including a mixing baseline, an alternative learning–unlearning pair under the distribution model when C ∗ ∈ (1, 2), and multi-source unlearning under the fixed-sample model. Experiments validate the predicted trade-offs and the effectiveness of our methods. Several promising directions for future work emerge from our results. These include tightening the remaining gaps between upper and lower bounds, extending multi-source unlearning to the distribution model (both algorithm design and theory), and generalizing our framework to contextual/linear bandits or broader offline RL settings.

The setup for C ∗ ∈ (1, 2) is identical to that for C ∗ ∈ [2, ∞) and only the range of C ∗ differs. We focus on the hard case, as the sample counts of a∗ dominates the dataset in this regime. As shown in Table 2, when C ∗ = 1.3, Algorithm 6 achieves consistently competitive performance across different deletion scenarios, yielding up to more than 8

Unlearning Offline Stochastic Multi-Armed Bandits

Impact Statement

Gupta, V., Jung, C., Neel, S., Roth, A., Sharifi-Malvajerdi, S., and Waites, C. Adaptive machine unlearning. Advances in Neural Information Processing Systems, 34: 16319–16330, 2021.

This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.

Izzo, Z., Smart, M. A., Chaudhuri, K., and Zou, J. Approximate data deletion from machine learning models. In International Conference on Artificial Intelligence and Statistics (AISTATS 2021), pp. 2008–2016, 2021.

References Bourtoule, L., Chandrasekaran, V., Choquette-Choo, C. A., Jia, H., Travers, A., Zhang, B., Lie, D., and Papernot, N. Machine unlearning. In IEEE Symposium on Security and Privacy (S&P 2021), pp. 141–159, 2021.

Kidambi, R., Rajeswaran, A., Netrapalli, P., and Joachims, T. Morel: Model-based offline reinforcement learning. Advances in Neural Information Processing Systems, 33: 21810–21823, 2020.

Cao, Y. and Yang, J. Towards making systems forget with machine unlearning. In IEEE Symposium on Security and Privacy (S&P 2015), pp. 463–480, 2015.

Kumar, A., Zhou, A., Tucker, G., and Levine, S. Conservative q-learning for offline reinforcement learning. Advances in Neural Information Processing Systems, 33: 1179–1191, 2020.

Carlini, N., Liu, C., Erlingsson, Ú., Kos, J., and Song, D. The secret sharer: Evaluating and testing unintended memorization in neural networks. In USENIX Security Symposium (USENIX 2019), pp. 267–284, 2019.

Lee, J., Tucker, G., Nachum, O., and Dai, B. Model selection in batch policy optimization. In International Conference on Machine Learning (ICML 2022), pp. 12542– 12569, 2022.

Chen, M., Beutel, A., Covington, P., Jain, S., Belletti, F., and Chi, E. H. Top-k off-policy correction for a reinforce recommender system. In ACM International Conference on Web Search and Data Mining (WSDM 2019), pp. 456– 464, 2019.

Li, G., Ma, C., and Srebro, N. Pessimism for offline linear contextual bandits using ℓp confidence sets. Advances in Neural Information Processing Systems, 35:20974– 20987, 2022.

Chen, X., Zheng, K., Zhou, Z., Yang, Y., Chen, W., and Wang, L. (locally) differentially private combinatorial semi-bandits. In International Conference on Machine Learning (ICML 2020), pp. 1757–1767, 2020.

Liu, J., Lou, J., Qin, Z., and Ren, K. Certified minimax unlearning with generalization rates and deletion capacity. Advances in Neural Information Processing Systems, 36: 62821–62852, 2023.

Dwork, C., Roth, A., et al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3–4):211–407, 2014.

Liu, X., Dai, X., Zuo, J., Wang, S., Joe-Wong, C., Lui, J., and Chen, W. Offline learning for combinatorial multiarmed bandits. International Conference on Machine Learning (ICML 2025), 267:38251–38289, 2025.

Fujimoto, S., Meger, D., and Precup, D. Off-policy deep reinforcement learning without exploration. In International Conference on Machine Learning (ICML 2019), pp. 2052–2062, 2019.

Mehta, R., Pal, S., Singh, V., and Ravi, S. N. Deep unlearning via randomized conditionally independent hessians. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR 2022), pp. 10422–10431, 2022.

Ghasemipour, S. K. S., Schuurmans, D., and Gu, S. S. Emaq: Expected-max q-learning operator for simple yet effective offline and online rl. In International Conference on Machine Learning (ICML 2021), pp. 3682–3691, 2021.

Neel, S., Roth, A., and Sharifi-Malvajerdi, S. Descent-todelete: Gradient-based methods for machine unlearning. In Algorithmic Learning Theory (ALT 2021), pp. 931– 962, 2021.

Ginart, A., Guan, M., Valiant, G., and Zou, J. Y. Making ai forget you: Data deletion in machine learning. Advances in Neural Information Processing Systems, 32: 3513–3526, 2019.

Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34:11702–11716, 2021.

Guo, C., Goldstein, T., Hannun, A., and Van Der Maaten, L. Certified data removal from machine learning models. In International Conference on Machine Learning (ICML 2020), pp. 3832–3842, 2020.

Ren, W., Zhou, X., Liu, J., and Shroff, N. B. Multi-armed bandits with local differential privacy. arXiv preprint arXiv:2007.03121, 2020. 9

Unlearning Offline Stochastic Multi-Armed Bandits

Sekhari, A., Acharya, J., Kamath, G., and Suresh, A. T. Remember what you want to forget: Algorithms for machine unlearning. Advances in Neural Information Processing Systems, 34:18075–18086, 2021.

Zhang, Z., Zhou, Y., Zhao, X., Che, T., and Lyu, L. Prompt certified machine unlearning with randomized gradient smoothing and quantization. Advances in Neural Information Processing Systems, 35:13433–13455, 2022.

Shokri, R., Stronati, M., Song, C., and Shmatikov, V. Membership inference attacks against machine learning models. In IEEE Symposium on Security and Privacy (S&P 2017), pp. 3–18, 2017.

Zheng, K., Cai, T., Huang, W., Li, Z., and Wang, L. Locally differentially private (contextual) bandits learning. Advances in Neural Information Processing Systems, 33: 12300–12310, 2020.

Suriyakumar, V. and Wilson, A. C. Algorithms that approximate data removal: New results and limitations. Advances in Neural Information Processing Systems, 35: 18892–18903, 2022.

Zhou, X. and ZHANG, K. W. Locally private and robust multi-armed bandits. Advances in Neural Information Processing Systems, 37:7362–7399, 2024.

Tang, G., Pan, J., Wang, H., and Basilico, J. Reward innovation for long-term member satisfaction. In ACM Conference on Recommender Systems (RecSys 2023), pp. 396–399, 2023. Tao, Y., Wu, Y., Zhao, P., and Wang, D. Optimal rates of (locally) differentially private heavy-tailed multi-armed bandits. In International Conference on Artificial Intelligence and Statistics (AISTATS 2022), pp. 1546–1574, 2022. Ullah, E., Mai, T., Rao, A., Rossi, R. A., and Arora, R. Machine unlearning via algorithmic stability. In Conference on Learning Theory (COLT 2021), pp. 4126–4142, 2021. Wang, Y., Baharav, T. Z., Han, Y., Jiao, J., and Tse, D. Beyond the best: Estimating distribution functionals in infinite-armed bandits. Advances in Neural Information Processing Systems, 35:9262–9273, 2022. Xiao, C., Wu, Y., Mei, J., Dai, B., Lattimore, T., Li, L., Szepesvari, C., and Schuurmans, D. On the optimality of batch policy optimization algorithms. In International Conference on Machine Learning (ICML 2021), pp. 11362–11371, 2021. Ye, D., Zhu, T., Zhu, C., Wang, D., Gao, K., Shi, Z., Shen, S., Zhou, W., and Xue, M. Reinforcement unlearning. To appear in Network and Distributed System Security Symposium (NDSS 2025), 2025. Yu, T., Thomas, G., Yu, L., Ermon, S., Zou, J. Y., Levine, S., Finn, C., and Ma, T. Mopo: Model-based offline policy optimization. Advances in Neural Information Processing Systems, 33:14129–14142, 2020. Yuan, H., Jin, Z., Cao, P., Chen, Y., Liu, K., and Zhao, J. Towards robust knowledge unlearning: An adversarial framework for assessing and improving unlearning robustness in large language models. Proceedings of the AAAI Conference on Artificial Intelligence (AAAI 2025), 39:25769–25777, 2025. 10

Unlearning Offline Stochastic Multi-Armed Bandits

A. Missing Proofs in Section 3 A.1. Algorithms and Upper Bounds for Single-Source Unlearning Remember that the realistic unlearning request U is from a0 , |U | = k, D′ = D \ U and N (a0 ) is the sample counts of a0 in D. We present the single-source unlearning algorithm when the unlearning request is ∅. Algorithm 3 Single-source unlearning algorithm with input ∅ Input: Output of π(D′ ), additional statistics T (D′ ): π(D) = â, a0 , k, N (a0 ), fb(D′ ), a confidence level: τ ∈ (0, 1) q π ln m τ 1: γ0 ← 43 N (a0 )−k 2: if (â = a0 ) and (γ < γ0 ) then 3: Set ∆f ← 2N3k (a0 ) , σ ← ∆f γ 4: Sample ν ∈ R from N (0, σ 2 ) 5: Set fb(a0 ) (D′ ) ← fb(a0 ) (D′ ) + ν 6: end if Output: â′ = arg maxa fb(a) (D′ )

Note that the above algorithm adds the Gaussian noise only if Algorithm 2 adds the Gaussian noise, and these noises are sampled from the same distribution. Next we prove (ε, δ)-UL for Algorithm 2 and Algorithm 1. The first step is to calculate ∆f , which is the ℓ2 sensitivity of f . q N (a0 ) ln m τ Lemma A.1. For any dataset D, any unlearning request U from a0 , when k ≤ N (a0 ) − , we have ∆f ≤ 2 3k 2N (a0 ) . Proof. For any dataset D, after the unlearning of U ⊆ D, f(a0 ) (D′ ) becomes µ̂′ (a0 ) − b′ (a0 ) where N ′ (a0 ) = N (a0 ) − k, P q µ̂(a )·N (a )− 0 0 ln m (a0 ,ri )∈U ri ′ ′ τ µ̂′ (a0 ) = and b (a ) = ′ 0 N (a0 ) 2N ′ (a0 ) . For a ̸= a0 , f(a) (D ) = f(a) (D). Now we calculate the ′ sensitivity when the dataset changes from D to D \ U = D :

∆f = max′ ∥f (D) − f (D′ )∥2 D,D

µ̂(a0 ) · N (a0 ) −

(a0 ,ri )∈U ri

m ln τ

1 + − = max′ µ̂(a0 ) − D,D N (a0 ) − k 2(N (a0 ) − k) P P p N (a0 ) · (a0 ,ri )∈U ri − k (a0 ,ri )∈D ri k ln m τ p ≤ max′ + D,D N (a0 ) (N (a0 ) − k) 2 (N (a0 ) − k) 2N (a0 ) p (b) k ln m k 3k (a) τ p = + ≤ , N (a0 ) 2 (N (a0 ) − k) 2N (a0 ) 2N (a0 )

1 2N (a0 )

where (a) comes from choosing ri = 1, ∀(a0 , ri ) ∈ U and rj = 0, ∀(a0 , rj ) ∈ D \ U , (b) comes from k ≤ N (a0 ) − q N (a0 ) ln m τ . 2 Theorem A.2 (Theorem 3.2 restated). Algorithm 2 and Algorithm 1 are (ε, δ)-unlearning. Proof. From Theorem A.1, we know that |f (D \ U ) − f (D)| ≤ ∆f ≤ 11

3k . 2N (a0 )

Unlearning Offline Stochastic Multi-Armed Bandits

Let fb1 , fb1′ denote the LCB vector at the input and output step when the inputs are ∅, π(D \ U ), T (D \ U ) respectively, we have fb1 = f (D \ U ). Similarly, let fb2 , fb2′ denote the corresponding vector when the inputs are U, π(D), T (D), then fb2 = f (D). If the unlearning algorithm adds Gaussian noise, then by the proof of the Gaussian mechanism (Theorem A.1) in Dwork et al. (2014), for any measurable set R ⊆ Rm , h i h i h i h i Pr fb1′ ∈ R ≤ eε · Pr fb2′ ∈ R + δ, Pr fb2′ ∈ R ≤ eε · Pr fb1′ ∈ R + δ. h i If the unlearning algorithm instead executes rollback, then fb2′ = f (D \ U ) = fb1 = fb1′ , and hence Pr fb1′ ∈ R = h i Pr fb2′ ∈ R . Finally, viewing g(f (D)) := arg maxa f(a) (D) as a post-processing map and applying the post-processing lemma (Proposition 2.1) in Dwork et al. (2014), we conclude that Algorithm 2 and Algorithm 1 satisfy (ε, δ)-unlearning. ∗ Theorem A.3 (Theorem 3.3 restated). q Consider any offline dataset D(N ), any unlearning request U from a0 . N (a ) ≥

N∗ , |U | = k. When k ≤ N (a0 ) − q m) γ < γ0 = 43 πNln(N (a0 )−k ,

N (a0 ) ln m τ , by setting τ = N1 , the arm â′ returned by Algorithm 2 satisfies when 2

 SubOpt(N , N∗ , k, ε, δ) = O max

s  ln (N m) 

kγ + , N (a0 ) N (a0 )

 ln (N m)  . N∗ 

while when γ ≥ γ0 ,  SubOpt(N , N∗ , k, ε, δ) = O max

s  ln (N m) N (a0 ) − k



s ,

 ln (N m)  . N∗ 

Proof. Note that through the proof, a0 has been fixed whereas a∗ depends on the reward distributionqunderlying D(N ).

When γ < γ0 , we first consider the case where a0 = a∗ . Denote E1 as the event that |µ̂(a) − µ(a)| ≤ a on the dataset D. Applying Hoeffding’s inequality for a fixed arm a, we have s # " ln m 2τ τ ≥1− , Pr |µ̂(a) − µ(a)| ≤ 2N (a) m

ln m τ 2N (a) for all arms

which implies that Pr [E1 ] ≥ 1 − 2τ using the punion bound. Furthermore, regardless of whether a0 = â occurs or not, we could always let E2 be the event that |ν| ≤ σ 2 ln m τ = t, according to the property of Gaussian Md , we have t2

Pr [|ν| ≤ t] ≥ 1 − 2e− 2σ2 = 1 −

2τ , m

then we obtain Pr [E2 ] ≥ 1 − τ since m ≥ 2. Therefore under the condition that E = E1 ∩ E2 occurs, for every a ∈ A and ν, we have r m |µ̂(a) − µ(a)| ≤ b(a), |ν| ≤ σ 2 ln . τ If the event a0 = â occurs, Algorithm 2 will add Gaussian noise sampled from N (0, σ 2 ). In view of the definition of â′ , for â′ ̸= a∗ , we have µ̂(a∗ ) − b(a∗ ) + ν ≤ µ̂(â′ ) − b(â′ ) ⇒ µ(a∗ ) ≤ µ(â′ ) + 2b(a∗ ) − ν, and this occurs only if ν < 0. Then we have s E [µ(a∗ ) − µ(â′ ) | a0 = â] ≤ s ≤

2 ln m 1 τ + ∗ N (a ) Pr [E2 ] 2 ln m σ τ +√ . N (a0 ) 2π 12

Z σ√2 ln m τ 0

√

x2 x e− 2σ2 dx 2πσ

Unlearning Offline Stochastic Multi-Armed Bandits

If the event a0 ̸= â occurs, Algorithm 2 will execute rollback on a0 = a∗ . Before the rollback, we know that fb(â) (D) is the largest among all a ∈ A. Since fb(a) (D′ ) = fb(a) (D) for every a ̸= a∗ , â′ is either â or a∗ after the rollback. Then the expected sub-optimality will not be worse than the learning algorithm, from Theorem 3.1, we have s s 2 ln m 2 ln m ∗ ′ τ τ E [µ(a ) − µ(â ) | a0 ̸= â] ≤ + τ = + τ. N (a∗ ) N (a0 ) In conclusion, the expected sub-optimality satisfies: E [µ(a∗ ) − µ(â′ )] ≤ E [µ(a∗ ) − µ(â′ ) | E] + Pr [E c ] · E [µ(a∗ ) − µ(â′ ) | E c ] = E [(µ(a∗ ) − µ(â′ )) 1 [a0 = â] | E] + E [(µ(a∗ ) − µ(â′ )) 1 [a0 ̸= â] | E] +

2 X

Pr Ejc

j=1

s ≤ Pr [a0 = â | E] · s

2 ln m σ τ + √ + 3τ N (a0 ) 2π

2 ln (N m) 3kγ 3 + √ + . N (a0 ) 2 2πN (a0 ) N

≤

2 ln m σ τ +√ N (a0 ) 2π

! + Pr [a0 ̸= â | E] ·

2 ln m τ +τ N (a0 )

! + 3τ

The second case is a0 ̸= a∗ . If the event a0 = â occurs, then Algorithm 2 adds Gaussian noise only to fb(a0 ) (D), while leaving fb(a) (D) unchanged for all a ̸= a0 . If the noise realization ν ≥ 0, the selected arm remains â′ = a0 , and the resulting sub-optimality is controlled by the guarantee of the learning algorithm. If ν ≤ 0, the guarantee still holds, since all coordinates of fb(a) (D) for a ̸= a0 are unchanged. If instead the event a0 ̸= â occurs, then Algorithm 2 executes rollback on arm a0 , and the expected sub-optimality cannot be worse than that of the learning algorithm. Therefore, when a0 ̸= a∗ , the expected sub-optimality satisfies s s 2 ln (N m) 2 ln (N m) 1 E [µ(a∗ ) − µ(â′ )] ≤ E [µ(a∗ ) − µ(â)] ≤ +τ ≤ + . ∗ N (a ) N∗ N In conclusion, when γ < γ0 , the upper bound satisfies  q ln(N m) kγ  , + O N (a ) N (a ) 0 0 q E [µ(a∗ ) − µ(â′ )] = ln(N m)  , O N∗ Thus

 SubOpt(N , N∗ , k, ε, δ) = O max

s  ln (N m) 

a0 = a∗ , a0 ̸= a∗ .

kγ + , N (a0 ) N (a0 )

 ln (N m)  . N∗ 

When γ ≥ γ0 . Algorithm 2 executes rollback. When a0 ̸= a∗ , we could similarly prove that the performance will be guaranteed by the learning algorithm, s 2 ln (N m) 2 E [µ(a∗ ) − µ(â′ )] ≤ + . N∗ N q m ln τ When a0 = a∗ , we change the definition of E2 to be the event that |µ̂(a) − µ(a)| ≤ 2N (a) for every a ∈ A and q ln m |µ̂′ (a0 ) − µ(a0 )| ≤ 2(N (a0τ)−k) for a0 after the rollback of k points. According to our assumption, U is independent of 13

Unlearning Offline Stochastic Multi-Armed Bandits

the reward of a0 , thus µ̂′ (a0 ) is unbiased with respect to µ(a0 ). We could also applying Hoeffding’s inequality to bound the probability s # " ln m 2τ ′ τ Pr |µ̂ (a0 ) − µ(a0 )| ≤ ≥1− ≥ 1 − τ, 2(N (a0 ) − k) m which implies that Pr [E1 ] ≥ 1 − 3τ using the union bound. Therefore the upper bound satisfies E [µ(a∗ ) − µ(â′ )] ≤ E [µ(a∗ ) − µ(â′ ) | E] + Pr [E c ] · E [µ(a∗ ) − µ(â′ ) | E c ] s s 2 ln m 2 ln (N m) 4 τ ≤ + 4τ = + . N (a0 ) − k N (a0 ) − k N In conclusion, when γ ≥ γ0 , the upper bound satisfies  q ln(N m)  , O qN (a0 )−k E [µ(a∗ ) − µ(â′ )] = ln(N m)  , O N∗

a0 = a∗ , a0 ̸= a∗ .

Then we obtain that  SubOpt(N , N∗ , k, ε, δ) = O max

s  ln (N m) 

N (a0 ) − k

s ,

 ln (N m)  . N∗ 

How to obtain γ0 The threshold γ0 is optimized in the case a0 = a∗ , since the upper bound is fixed to be O when a0 ̸= a∗ . Let s s 2 ln m 2 ln m 3kγ τ τ = + √ , N (a0 ) − k N (a0 ) 2 2πN (a0 ) √ q 4 πN (a0 ) ln m π ln m τ τ √ ≈ 4 √ and we could obtain that γ = √ 3 N (a0 )−k = γ0 . 3

N (a0 )−k

N (a0 )−k+

ln(N m) N (a∗ )

N (a0 )

We first give the lemma for binomial random variable N (a∗ ). Lemma A.4 (Lemma 4 in (Rashidinejad et al., 2021)). With probability at least 1 − e− N (a∗ ) ≥

N d(a∗ ) 8

, one has

1 N d(a∗ ). 2

Theorem A.5 (Theorem 3.5 restated). Consider any offline dataset D ∼ DN , where the behavior policy satisfies d(a∗ ) ≥ C1∗ q N (a0 ) ln m τ for some C ∗ > 1, any unlearning request U from a0 . |U | = k. When N > 8C ∗ ln N and k ≤ N (a0 ) − , by 2 1 ′ setting τ = N , the arm â returned by Algorithm 2 satisfies (s )! r C ∗ ln (N m) C ∗ ln (N m) kγC ∗ ∗ SubOpt(N, C , k, ε, δ) = O min , + . max {1, N − 2kC ∗ } N N N Proof. We first consider the case where a0 = a∗ . Denote E1 as the event that N (a∗ ) ≥ 2C . From Theorem A.4 we q ∗m N ln − 8C τ ∗ ≥ 1 − τ . Denote E2 as the event that |µ̂(a) − µ(a)| ≤ 2N (a) know that Pr [E1 ] ≥ 1 − e for all arms a ∈ A and q m ln |µ̂′ (a0 ) − µ(a0 )| ≤ 2(N (a0τ)−k) for a0 after the rollback of k points. According to our assumption, U is independent of the reward of a0 , thus µ̂′ (a0 ) is unbiased with respect to µ(a0 ). Applying Hoeffding’s inequality for a fixed arm a, we have s " # ln m 2τ τ Pr |µ̂(a) − µ(a)| ≤ ≥1− , 2N (a) m

Unlearning Offline Stochastic Multi-Armed Bandits

and

" Pr |µ̂′ (a0 ) − µ(a0 )| ≤

# ln m 2τ τ ≥1− ≥ 1 − τ, 2(N (a0 ) − k) m

which implies that Pr [E2 ] ≥ 1 − 3τ using the p union bound. Furthermore, regardless of the branch Algorithm 2 takes, we could always let E3 be the event that |ν| ≤ σ 2 ln m τ = t, according to the property of Gaussian Md , we have t2

Pr [|ν| ≤ t] ≥ 1 − 2e− 2σ2 = 1 −

2τ , m

then we obtain Pr [E3 ] ≥ 1 − τ since m ≥ 2. Therefore under the condition that E = E1 ∩ E2 ∩ E3 occurs, for every a ∈ A and ν, we have s r ln m N m ′ τ N (a0 ) ≥ , |µ̂(a) − µ(a)| ≤ b(a), |µ̂ (a0 ) − µ(a0 )| ≤ , |ν| ≤ σ 2 ln . 2C ∗ 2(N (a0 ) − k) τ If the event a0 = â and γ < γ0 occurs, Algorithm 2 will add Gaussian noise sampled from N (0, σ 2 ). In view of the definition of â′ , for â′ ̸= a∗ , we have µ̂(a∗ ) − b(a∗ ) + ν ≤ µ̂(â′ ) − b(â′ ) ⇒ µ(a∗ ) ≤ µ(â′ ) + 2b(a∗ ) − ν, and this occurs only if ν < 0. Then we have s E [µ(a∗ ) − µ(â′ ) | a0 = â, γ < γ0 ] ≤ s ≤

2 ln m 1 τ + N (a∗ ) Pr [E2 ]

Z σ√2 ln m τ 0

√

x2 x e− 2σ2 dx 2πσ

2 ln m σ τ +√ = Rg . N (a0 ) 2π

If either a0 ̸= â or γ ≥ γ0 occurs, Algorithm 2 executes rollback. Then the sub-optimality satisfies s 2 ln m ∗ ′ τ E [µ(a ) − µ(â ) | a0 = â, γ ≥ γ0 ] ≤ = Rr . N (a0 ) − k According to the definition of γ0 , it is the threshold at which Rg = Rr ; moreover, for γ < γ0 , we have Rg < Rr . Therefore, E [µ(a∗ ) − µ(â′ ) | a0 = â] = 1 [Rg < Rr ] · Rg + 1 [Rg ≥ Rr ] · Rr = min {Rr , Rg } . If the event a0 ̸= â occurs, then Algorithm 2 executes rollback on arm a0 = a∗ . Prior to rollback, fb(â) (D) is the largest coordinate among all a ∈ A. Moreover, rollback only modifies the coordinate corresponding to a∗ : for every a ̸= a∗ , we have fb(a) (D′ ) = fb(a) (D). Consequently, after rollback the selected arm â′ can only be either â or a∗ . Therefore, the expected sub-optimality is no worse than that of the learning algorithm. By Theorem 3.1, we have s s m 2 ln 2 ln m τ τ E [µ(a∗ ) − µ(â′ )] ≤ + τ = + τ. N (a∗ ) N (a0 ) Therefore when a0 = a∗ , the expected sub-optimality satisfies: E [µ(a∗ ) − µ(â′ )] ≤ E [µ(a∗ ) − µ(â′ ) | E] + Pr [E c ] · E [µ(a∗ ) − µ(â′ ) | E c ] = E [(µ(a∗ ) − µ(â′ )) 1 [a0 = â] | E] + E [(µ(a∗ ) − µ(â′ )) 1 [a0 ̸= â] | E] +

3 X j=1

s ≤ Pr [a0 = â | E] · min {Rr , Rg } + Pr [a0 ̸= â | E] ·

2 ln m τ +τ N (a0 )

≤ min {Rr , Rg } + 5τ (s ) r 4C ∗ ln (N m) 4C ∗ ln (N m) 3kγC ∗ 5 ≤ min , +√ + . ∗ max {1, N − 2kC } N N 2πN 15

! + 5τ

Pr Ejc

Unlearning Offline Stochastic Multi-Armed Bandits

The second case is a0 ̸= a∗ . If the event a0 = â and x = 1 occurs, Algorithm 2 will add Gaussian noise to fb(a0 ) (D). However, this will not affect fb(a) (D), a ̸= a0 . If ν ≥ 0, â′ will still be a0 , the performance will be guaranteed by the learning algorithm. If ν ≤ 0, the performance will also be guaranteed by the learning algorithm since fb(a) (D) of every a ̸= a0 remains the same. If either a0 ̸= â or x = 0 occurs, Algorithm 2 will execute rollback on a0 , and the expected sub-optimality will not be worse than that of the learning algorithm, thus in conclusion, when a0 ̸= a∗ , the expected sub-optimality satisfies r C ∗ ln (N m) 2 ∗ ′ ∗ E [µ(a ) − µ(â )] ≤ E [µ(a ) − µ(â)] ≤ 2 + . N N Therefore Algorithm 2 satisfies that  q q  C ∗ ln(N m) C ∗ ln(N m) kγC ∗  + N , max{1,N −2kC ∗ } , O min N q E [µ(a∗ ) − µ(â′ )] =  C ∗ ln(N m)  , O N

a0 = a∗ , a0 ̸= a∗ ,

which is (r ∗

SubOpt(N, C , k, ε, δ) = O min

C ∗ ln (N m) kγC ∗ + , N N

C ∗ ln (N m) max {1, N − 2kC ∗ }

)! .

A.2. Lower Bounds for Single-Source Unlearning 1 Theorem A.6 (Theorem 3.7 restated). Let ε ≥ 0, δ ≤ 8√ . For any unlearning request U from a0 , the lower bound of e sub-optimality satisfies s ! 1 −ε SubOpt(N , N∗ , k, ε, δ) = Ω e . N (a0 ) − k

Proof. To prove the lower bound, we could first relax the model by allowing that π ′ has access to the entire dataset D rather than T (D). Since the point space Z is bounded and providing additional information only helps. Moreover, because π(D) is a deterministic function of D, it is without loss of generality to rewrite π ′ (U, π(D), T (D)) as π ′ (U, D) and π ′ (∅, π(D \ U ), T (D \ U )) as π ′ (∅, D \ U ). We construct two instances I1 and I2 to prove the lower bound, where the rewards are drawn from some Bernoulli distributions supported on [0, 1]. Let µI1 and µI2 represent the vectors of arm mean rewards in I1 and I2 . In particular, 1 1 µI1 = ( + ∆, ), 2 2

1 1 µI2 = ( − ∆, ). 2 2

Here 0 ≤ ∆ ≤ 15 and its value will be specified later. Let D1 (N ), D2 (N ) denote the two datasets respectively, where a0 = 1 and N = (N (a0 ), N − N (a0 ))⊤ . In addition, the reward distribution underlying D1 (N ) is µI1 , while that underlying D2 (N ) is µI2 . Finally, let U1 , U2 be the corresponding unlearning request from D1 (N ), D2 (N ) respectively. Let ED,U [] represent the expectation conditioned on D, U . From the definition, for any algorithm π, π ′ , we have ED1 (N ),U1 [µ(a∗ ) − µ(â′ )] = Pr [â′ = a2 ] · ∆ = Pr [π ′ (U1 , D1 (N )) = a2 ] · ∆ (a)

≥ e−ε (Pr [π ′ (∅, D1 (N ) \ U1 ) = a2 ] − δ) · ∆

= e−ε Pr [π ′ (∅, D1 (N ) \ U1 ) = a2 ] · ∆ − e−ε δ∆,

(1)

where (a) is because π, π ′ are (ε, δ)-UL. Similarly for D2 , U2 , we have ED2 (N ),U2 [µ(a∗ ) − µ(â′ )] ≥ e−ε Pr [π ′ (∅, D2 (N ) \ U2 ) = a1 ] · ∆ − e−ε δ∆. 16

(2)

Unlearning Offline Stochastic Multi-Armed Bandits

Next we generate U1 by selecting k points in the data points of a0 from D1 (N ) uniformly and randomly, while U2 is generated in the same way from D2 (N ). Therefore U and the rewards of each point will be mutually independent. Denote N ′ = (N (a0 ) − k, N − N (a0 ))⊤ as the sample-count vector after unlearning request U . Then we apply the classic Le Cam’s method to give a lower bound of SubOpt(N , N∗ , k, ε, δ). Denote TV(·, ·) as the total variation distance between two distributions, KL(·∥·) as the KL-divergence of two distributions. We have SubOpt(N , N∗ , k, ε, δ) 1 ED1 (N ),U1 [µ(a∗ ) − µ(â′ )] + ED2 (N ),U2 [µ(a∗ ) − µ(â′ )] ≥ 2 e−ε ∆ = (Pr [π ′ (∅, D1 (N ) \ U1 ) = a2 ] + Pr [π ′ (∅, D2 (N ) \ U2 ) = a1 ]) − e−ε δ∆ 2 −ε ∆ (a) e = (Pr [π ′ (∅, D1 (N ′ )) = a2 ] + Pr [π ′ (∅, D2 (N ′ )) = a1 ]) − e−ε δ∆ 2 e−ε ∆ ≥ (1 − TV (π ′ (∅, D1 (N ′ )), π ′ (∅, D2 (N ′ )))) − e−ε δ∆ 2 (b) e−ε ∆ ≥ exp (−KL (π ′ (∅, D1 (N ′ ))∥π ′ (∅, D2 (N ′ )))) − e−ε δ∆ 4 (c) e−ε ∆ exp (−KL (D1 (N ′ )∥D2 (N ′ ))) − e−ε δ∆ ≥ 4 (d) e−ε ∆ ≥ exp −10∆2 (N (a0 ) − k) − e−ε δ∆, 4 where (a) is from U and the reward being mutually independent, (b) is from Bretagnolle–Huber inequality, (c) is from the 1+2∆ data processing inequality, (d) is from direct calculation and the fact that ln 1−2∆ ≤ 5∆ when 0 ≤ ∆ ≤ 15 . By choosing n o q 1 ∆ = min 15 , 12 5(N (a10 )−k) , when δ ≤ 8√ , we have e e−ε SubOpt(N , N∗ , k, ε, δ) ≥ 16

1 = Ω e−ε 5e(N (a0 ) − k)

1 N (a0 ) − k

! .

1 Theorem A.7 (Theorem 3.9 restated). Let ε ≥ 0, δ ≤ 8√ . For any single-source unlearning request U , when C ∗ ∈ [2, ∞), e the lower bound of sub-optimality satisfies ! r C∗ ∗ −ε , SubOpt(N, C , k, ε, δ) = Ω e N −k

while C ∗ ∈ (1, 2), ∗

SubOpt(N, C , k, ε, 0) = Ω

2 − C∗ 2 ∗ exp −(N − k)(2 − C ) ln . eε C∗ − 1

Proof. Following the proof of Theorem A.6, we relax the model and rewrite π ′ (U, π(D), T (D)) as π ′ (U, D) and π ′ (∅, π(D\ U ), T (D \ U )) as π ′ (∅, D \ U ). For C ∗ ≥ 2, we construct two closely related instances I1 and I2 as in Theorem A.6, where µI1 and µI2 represent the vectors of arm mean rewards in I1 and I2 . In particular, 1 1 µI1 = ( + ∆, ), 2 2

1 1 µI2 = ( − ∆, ). 2 2

The only difference is the value of ∆, which will be specified later. For the behavior policy d, let dI1 (1) = dI2 (1) = C1∗ , 1 dI1 (2) = dI2 (2) = 1 − C1∗ . Since C ∗ ≥ 2, we have 1 − C∗ ≥ C1∗ for I2 . Let D1 (N, C ∗ ) denote the dataset obtained by ∗ drawing N i.i.d. samples from dI1 ⊗ µI1 and D2 (N, C ) denote the dataset which draws N i.i.d. samples from dI2 ⊗ µI2 . Finally, let U1 , U2 be the unlearning request from D1 (N, C ∗ ), D2 (N, C ∗ ) respectively. 17

Unlearning Offline Stochastic Multi-Armed Bandits

From the definition, for any algorithm π, π ′ , we have ED1 (N,C ∗ ),U1 [µ(a∗ ) − µ(â′ )] = Pr [â′ = a2 ] · ∆ = Pr [π ′ (U1 , D1 (N, C ∗ )) = a2 ] · ∆ (a)

≥ e−ε (Pr [π ′ (∅, D1 (N, C ∗ ) \ U1 ) = a2 ] − δ) · ∆

= e−ε Pr [π ′ (∅, D1 (N, C ∗ ) \ U1 ) = a2 ] · ∆ − e−ε δ∆,

(3)

where (a) comes from π, π ′ are (ε, δ)-UL. Similarly for D2 , U2 , we have ED2 (N,C ∗ ),U2 [µ(a∗ ) − µ(â′ )] ≥ e−ε Pr [π ′ (∅, D2 (N, C ∗ ) \ U2 ) = a1 ] · ∆ − e−ε δ∆.

(4)

Next we generate U1 by selecting k points in D1 uniformly and randomly, while U2 is generated in the same way from D2 . We have the following lemma: Lemma A.8. ∀i = 1, 2, Di (N − k, C ∗ ) and Di (N, C ∗ ) \ Ui follows the same distribution.

Proof. It is sufficient to prove the case of i = 1, while i = 2 follows the same. We need to prove that for any N arms {X1 , · · · , XN } sampled from dI1 , after drawing a random set S = {i1 < i2 < · · · < iN −k } from [N ] uniformly and randomly, the distribution of the remaining set Xi1 , · · · , XiN −k is the same as drawing N − k samples {Y1 , · · · , YN −k } from dI1 . Fix arbitrary values a1 , · · · , aN −k ∈ A. We need to compute Pr Xi1 = a1 , · · · , XiN −k = aN −k . By the law of total probability with respect to the random index set S, we have X Pr Xi1 = a1 , . . . , XiN −k = aN −k = Pr [S] · Pr Xi1 = a1 , . . . , XiN −k = aN −k S S∈[N ]

S0 ∈[N ]

N N −k

(a)

Pr Xi1 = a1 , . . . , XiN −k = aN −k S0 ,

(5)

where (a) is because S is chosen uniformly from [N ] and independently of {X1 , . . . , XN }. For a fixed S0 = {i1 < · · · < iN −k }, the randomness of Xi1 , · · · , XiN −k only comes from dI1 , thus −k NY Pr Xi1 = a1 , . . . , XiN −k = aN −k S0 = d(ai ). i=1

Bring this back to Equation (5), we obtain that

X Pr Xi1 = a1 , . . . , XiN −k = aN −k = S0 ∈[N ]

N −k Y

N N −k

d(ai ) =

i=1

N −k Y

d(ai ) = Pr [Y1 = a1 , . . . , YN −k = aN −k ] ,

i=1

which is exactly the joint mass function of (N − k) i.i.d. samples from common law d. 18

Unlearning Offline Stochastic Multi-Armed Bandits

Similarly we apply Le Cam’s method to give a lower bound of SubOpt(N, C ∗ , k, ε, δ). We have 1 ED1 (N,C ∗ ),U1 [µ(a∗ ) − µ(â′ )] + ED2 (N,C ∗ ),U2 [µ(a∗ ) − µ(â′ )] 2 e−ε ∆ = (Pr [π ′ (∅, D1 (N, C ∗ ) \ U1 ) = a2 ] + Pr [π ′ (∅, D2 (N, C ∗ ) \ U2 ) = a1 ]) − e−ε δ∆ 2 −ε ∆ (a) e (Pr [π ′ (∅, D1 (N − k, C ∗ )) = a2 ] + Pr [π ′ (∅, D2 (N − k, C ∗ )) = a1 ]) − e−ε δ∆ = 2 e−ε ∆ ≥ (1 − TV (π ′ (D1 (N − k, C ∗ ), π ′ (D2 (N − k, C ∗ ))) − e−ε δ∆ 2 (b) e−ε ∆ ≥ exp (−KL (π ′ (D1 (N − k, C ∗ )∥π ′ (D2 (N − k, C ∗ ))) − e−ε δ∆ 4 (c) e−ε ∆ exp (−KL (D1 (N − k, C ∗ )∥D2 (N − k, C ∗ ))) − e−ε δ∆ ≥ 4 (d) e−ε ∆ 4∆2 (N − k) − e−ε δ∆, exp − ≥ 4 C∗

SubOpt(N, C ∗ , k, ε, δ) ≥

where (a) is from Theorem A.8, (b) is from Bretagnolle–Huber inequality, (c) is from the data processing n o (d) is qinequality, 1+2∆ from direct calculation and the fact that ln 1−2∆ ≤ 5∆ when 0 ≤ ∆ ≤ 51 . By choosing ∆ = min

1 1 5, 2

C∗ 5(N −k)

, when

1 , we have δ < 8√ e

e−ε SubOpt(N, C , k, ε, δ) ≥ 16

∗

C∗ = Ω e−ε 5e(N − k)

C∗ N −k

! .

When C ∗ ∈ (1, 2), the proof is similar to the case C ∗ ∈ [2, ∞). We construct new instances that are different in both the reward distributions as well as the behavior policy. More specifically, 1 1 µI1 = ( + ∆, ), 2 2

1 1 µI2 = ( , + ∆). 2 2

∗

1 1 Here we set ∆ = 2−C 2 . For the behavior policy d on A, dI1 (1) = dI2 (2) = C ∗ , dI1 (2) = dI2 (1) = 1 − C ∗ . Therefore 1 ∗ ∗ ∗ ∗ in both datasets a satisfy d(a ) ≥ C ∗ . The notations D1 (N, C ), D2 (N, C ), U1 , U2 are defined analogously. Moreover, we generate U1 and U2 in the same manner as in the case C ∗ ≥ 2, from D1 (N, C ∗ ) and D2 (N, C ∗ ) respectively. And we could also establish Theorem A.8 for Di (N − k, C ∗ ) and Di (N, C ∗ ) \ Ui , ∀i = 1, 2. Similarly we have

1 ED1 (N,C ∗ ),U1 [µ(a∗ ) − µ(â′ )] + ED2 (N,C ∗ ),U2 [µ(a∗ ) − µ(â′ )] 2 e−ε ∆ = (Pr [π ′ (∅, D1 (N, C ∗ ) \ U1 ) = a2 ] + Pr [π ′ (∅, D2 (N, C ∗ ) \ U2 ) = a1 ]) 2 e−ε ∆ ≥ (1 − TV (π ′ (D1 (N − k, C ∗ ), π ′ (D2 (N − k, C ∗ ))) 2 e−ε ∆ ≥ exp (−KL (D1 (N − k, C ∗ )∥D2 (N − k, C ∗ ))) . 4

SubOpt(N, C ∗ , k, ε, 0) ≥

(6)

From direct calculation, we have KL (D1 (N − k, C ∗ )∥D2 (N − k, C ∗ )) = (N − k) · KL (dI1 ⊗ µI1 ∥dI2 ⊗ µI2 ) = (N − k) KL (dI1 ∥dI2 ) +

2 X

! dI1 (a) · KL (µI1 (a)∥µI2 (a))

a=1

1+∆ 1 1 + 2∆ 1−∆ 1 1 − 2∆ = (N − k) · − ln + − ln C∗ 2 C∗ − 1 C∗ 2 C∗ − 1 ∗ (N − k)(2 − C ) 2 = ln . ∗ ∗ C C −1 19

Unlearning Offline Stochastic Multi-Armed Bandits

Bring this result back to Equation (6), we obtain the conclusion ∗) 2 − C ∗ −ε− (N −k)(2−C ln( C ∗2−1 ) C∗ ·e 8 ∗ 2 = Ω (2 − C ∗ )e−ε−(N −k)(2−C ) ln( C ∗ −1 ) .

SubOpt(N, C ∗ , k, ε, 0) ≥

A.3. The Mixing Algorithm In this section, we study the mixing algorithm and investigate whether it can outperform the two base algorithms: Gaussian mechanism or rollback. For clarity of exposition, we present the algorithm under Mf (we could obtain similar conclusion under Md ). When a0 ̸= a∗ , rollback is always preferable, since it does not degrade the performance of the underlying learning algorithm. Accordingly, Algorithm 4 retains the initial check â = a0 . Let U ′ ⊆ U denote the subset of points that are first handled via rollback, and write |U ′ | = k ′ . After rolling back U ′ , the ′ ) ′ algorithm adds Gaussian noise to the LCB vector with σ = 2(N3(k−k (a0 )−k′ ) . The parameter k interpolates between the two extremes: k ′ = k recovers pure rollback, whereas k ′ = 0 recovers the pure Gaussian-noise mechanism. Algorithm 4 Single-source unlearning mixing algorithm under Mf c, unlearning request: U from a0 , |U | = k, a confidence b N Input: Output of π(D): â, additional statistics T (D): fb(D), µ, level: τ ∈ (0, 1), mixing parameter: k ′ ∈ [0, k] 1: Set fb(D ′ ) ← fb(D) 2: if â ̸= a0 then 3: k′ ← k 4: end if 5: Set N ′ (a0 ) ← N (a0 ) − k ′ and choose k ′ data points in U uniformly and randomly, denote them as U ′ P 6: Compute the new empirical mean reward µ̂′ (a0 ) ← 7: Compute the new penalty b′ (a0 ) ←

µ̂(a0 )·N (a0 )− (a ,r )∈U ′ ri 0 i N ′ (a0 )

ln m τ 2N ′ (a0 )

8: Set fb(a0 ) (D ′ ) ← µ̂′ (a0 ) − b′ (a0 ) 3(k−k′ )

9: Set ∆f ← 2(N (a0 )−k′ ) , σ ← ∆f γ 10: Sample ν ∈ R from N (0, σ 2 ) 11: Set fb(a0 ) (D ′ ) ← fb(a0 ) (D ′ ) + ν

Output: â′ = arg maxa fb(a) (D′ )

Algorithm 5 Single-source unlearning mixing algorithm under Mf with input ∅ Input: Output of π(D′ ), additional statistics T (D′ ): π(D) = â, a0 , k, N (a0 ), fb(D′ ), a confidence level: τ ∈ (0, 1), mixing parameter: k ′ ∈ [0, k] 1: if â ̸= a0 then 2: k′ ← k 3: end if 3(k−k′ ) 4: Set ∆f ← 2(N (a0 )−k′ ) , σ ← ∆f γ 5: Sample ν ∈ R from N (0, σ 2 ) 6: Set fb(a0 ) (D ′ ) ← fb(a0 ) (D ′ ) + ν Output: â′ = arg max fb(a) (D′ ) a

Theorem A.9. Algorithm 4 and Algorithm 1 are (ε, δ)-unlearning. We first calculate the ℓ2 sensitivity of f . After the unlearning of U ′ , fb(a0 ) (D′ ) becomes µ̂′ (a0 ) − b′ (a0 ) where N ′ (a0 ) = 20

Unlearning Offline Stochastic Multi-Armed Bandits P q µ̂(a0 )·N (a0 )− (a ,r )∈U ′ ri ln m ′ ′ 0 i τ b b N (a0 ) − k ′ , µ̂′ (a0 ) = and b (a ) = 0 N ′ (a0 ) 2N ′ (a0 ) . For a ̸= a0 , f(a) (D ) = f(a) (D). Now we ′ ′ calculate ∆f when the dataset changes from D \ U to D \ U = D :

∆f = max ∥f (D \ U ′ ) − f (D′ )∥2 ′ ′ D\U ,D

s ! 1 1 ′ = max µ̂ (a0 ) − + − N (a0 ) − k 2(N (a0 ) − k) 2(N (a0 ) − k ′ ) D\U ′ ,D ′ P P p (N (a0 ) − k ′ ) (a0 ,ri )∈U \U ′ ri − (k − k ′ ) (a0 ,ri )∈D\U ′ ri (k − k ′ ) ln m τ p ≤ max + (N (a0 ) − k ′ ) (N (a0 ) − k) D\U ′ ,D ′ 2 (N (a0 ) − k) 2(N (a0 ) − k ′ ) p (b) (k − k ′ ) ln m k − k′ 3(k − k ′ ) (a) τ p = ≤ + , N (a0 ) − k ′ 2(N (a0 ) − k ′ ) 2 (N (a0 ) − k) 2(N (a0 ) − k ′ ) µ̂′ (a0 ) · (N (a0 ) − k ′ ) −

(a0 ,ri )∈U \U ′ ri

m ln τ

where (a)qcomes from choosing ri = 1, ∀(a0 , ri ) ∈ U \ U ′ and rj = 0, ∀(a0 , rj ) ∈ D \ U , (b) comes from k ≤ N (a ) ln m

0 τ N (a0 ) − . Thus, by following the same proof as Theorem 3.2, we conclude that Algorithm 4 and Algorithm 1 2 satisfy (ε, δ)-unlearning.

Theorem A.10 (Mfq ). Consider any offline dataset D(N ), any unlearning request U from a0 . N (a∗ ) ≥ N∗ , |U | = k.

When k ≤ N (a0 ) −

N (a0 ) ln m τ , by setting τ = N1 , the arm â′ returned by Algorithm 4 satisfies 2

 SubOpt(N , N∗ , k, ε, δ) = O max

s  ln (N m) 

N (a0 ) − k ′

′

(k − k )γ ln (N m) , N (a0 ) − k ′

 ln (N m)  . N∗ 

q m ln τ for every a ∈ A Proof. We first consider the case where a0 = a∗ . Denote E1 as the event that |µ̂(a) − µ(a)| ≤ 2N (a) q m ln and |µ̂′ (a0 ) − µ(a0 )| ≤ 2(N (a0τ)−k′ ) for a0 after the rollback of k ′ points. Applying Hoeffding’s inequality for a fixed arm a, we have s " # ln m 2τ τ ≥1− . Pr |µ̂(a) − µ(a)| ≤ 2N (a) m According to our assumption, U is independent of the reward of a0 and U ′ is drawn from U uniformly and randomly, thus µ̂′ (a0 ) is unbiased regard to µ(a0 ). We could also applying Hoeffding’s inequality to bound the probability s # " ln m 2τ ′ τ Pr |µ̂ (a0 ) − µ(a0 )| ≤ ≥1− ≥ 1 − τ, ′ 2(N (a0 ) − k ) m which implies that Pr [E1 ] ≥ 1 − 3τ using the punion bound. Furthermore, regardless of whether a0 = â happens or not, we could always let E2 be the event that |ν| ≤ σ 2 ln m τ = t, according to the property of Gaussian Md , we have t2

Pr [|ν| ≤ t] ≥ 1 − 2e− 2σ2 = 1 −

2τ , m

then we obtain Pr [E2 ] ≥ 1 − τ . Therefore under the condition that E = E1 ∩ E2 happens, for every a ∈ A and ν, we have r m ′ ′ |µ̂(a) − µ(a)| ≤ b(a), |µ̂ (a0 ) − µ(a0 )| ≤ b (a0 ), |ν| ≤ σ 2 ln . τ If the event a0 = â happens, Algorithm 4 will first execute rollback of k ′ points and then add Gaussian noise sampled from N (0, σ 2 ). In view of the definition of â′ , for â′ ̸= a∗ , we have µ̂′ (a∗ ) − b′ (a∗ ) + ν ≤ µ̂(â′ ) − b(â′ ) ⇒ µ(a∗ ) ≤ µ(â′ ) + 2b′ (a∗ ) − ν. 21

Unlearning Offline Stochastic Multi-Armed Bandits

and this occurs only if ν < 0. Then we have s ∗

′

E [µ(a ) − µ(â ) | a0 = â] ≤

2 ln m σ τ +√ . ′ N (a0 ) − k 2π

If the event a0 ̸= â happens, Algorithm 4 will execute rollback on a0 = a∗ . Before the rollback, we know that fb(â) (D) is the largest among all a ∈ A. Since fb(a) (D′ ) = fb(a) (D) for every a ̸= a∗ , â′ is either â or a∗ after the rollback. Then the expected sub-optimality will not be worse then the learning algorithm, and s ∗

E [µ(a ) − µ(â)] ≤

2 ln m τ + 2τ = N (a∗ )

2 ln m τ + 2τ. N (a0 )

In conclusion, the expected sub-optimality satisfies: E [µ(a∗ ) − µ(â′ )] ≤ E [µ(a∗ ) − µ(â′ ) | E] + Pr [E c ] · E [µ(a∗ ) − µ(â′ ) | E c ] = E [(µ(a∗ ) − µ(â′ )) 1 [a0 = â] | E] + E [(µ(a∗ ) − µ(â′ )) 1 [a0 ̸= â] | E] +

2 X

Pr Ejc

j=1

s ≤ Pr [a0 = â | E] · s

2 ln m σ τ + √ + 4τ N (a0 ) − k ′ 2π

2 ln (N m) 4 3(k − k ′ )γ √ + . + ′ ′ N (a0 ) − k 2 2π(N (a0 ) − k ) N

≤ ≤

2 ln m σ τ +√ N (a0 ) − k ′ 2π

! + Pr [a0 ̸= â | E] ·

2 ln m τ +τ N (a0 )

! + 4τ

The second case is a0 ̸= a∗ . If the event a0 = â occurs, then Algorithm 4 first rolls back k ′ points and subsequently adds Gaussian noise to fb(a0 ) (D). This operation does not affect fˆ(a) (D) for any a ̸= a0 . If the noise realization satisfies ν ≥ 0, then â′ remains a0 , and the performance is guaranteed by the learning algorithm. If ν ≤ 0, the performance is still guaranteed, since all coordinates f(a) (D) for a ̸= a0 remain unchanged. If instead the event a0 ̸= â occurs, then Algorithm 4 executes rollback on arm a0 , and the expected sub-optimality is no worse than that of the learning algorithm. Therefore, when a0 ̸= a∗ , the expected sub-optimality under Algorithm 4 is no worse than under the learning algorithm, and thus s ∗

′

∗

E [µ(a ) − µ(â )] ≤ E [µ(a ) − µ(â)] ≤

2 ln m τ +τ ≤ N (a∗ )

2 ln m τ + τ. N∗

In conclusion, the upper bound satisfies  q ln(N m) (k−k′ )γ  , a0 = a∗ , O ′ + N (a )−k ′ N (a )−k 0 0 ∗ ′ q E [µ(a ) − µ(â )] = ln(N m)  , a0 ̸= a∗ . O N∗

Comparison

We optimize the upper bound when a0 = a∗ : s E [µ(a∗ ) − µ(â′ )] ≤

2 ln (N m) 3(k − k ′ )γ 4 √ + + . ′ N (a0 ) − k ′ N 2 2π(N (a0 ) − k ) 22

Unlearning Offline Stochastic Multi-Armed Bandits

Let f (x) = 2

π ln(N m) 3(k−x)γ N (a0 )−x + 2(N (a0 )−x) , 0 ≤ x ≤ k. Then we calculate the derivative:

p ′

f (x) =

π ln (N m) (N (a0 ) − x) − 3γ(N (a0 ) − k) . (N (a0 ) − x)2

Since the denominator is positive, the numerator is monotonically decreasing as x increases, then the minimum point is obtained at k ′ = 0 or k ′ = k. A.4. Improved Results for C ∗ ∈ (1, 2) Algorithm 6 Single-source unlearning algorithm under Md (C ∗ ∈ (1, 2)) c, unlearning request U from a0 , |U | = k Input: Output of â = π(D), additional statistics: N c′ ← N c, N c′ ← N c(a ) − k 1: Set N 0 (a0 ) c′ Output: â′ = arg maxa N (a)

When the input of unlearned request is ∅, Algorithm 6 simply outputs the learned arm π(D \ U ), which is the arm with the most sample counts computed from D \ U . Then we prove the following theorem. Theorem A.11. Algorithm 6 and imitation learning are (0, 0)-unlearning. c′ as the sample-count vector at the output step. Similarly, Proof. When the inputs are ∅, π(D \ U ), T (D \ U ), denote N 1 ′ c let N2 denote the corresponding vector when the inputs are U, π(D), T (D). In either cases, the algorithm outputs the c′ = N c′ = N c′ , where N c′ is the sample-count vector of D \ U . Viewing g(N c) = arg maxa N c(a) as a same vector, i.e. N 1 2 post-processing map, we obtain that Algorithm 6 and the imitation learning rule are (0, 0)-unlearning. Theorem A.12 (Theorem 3.11 restated). Consider any offline DN , where d(a∗ ) ≥ C1∗ for some C ∗ ∈ (1, 2), n dataset D ∼ o any unlearning request U from a0 . |U | = k. When k ≤ min

∗

3N (2−C )N 4 , C∗

, the arm â′ returned by Algorithm 6 satisfies

(N −k) (N +k) C∗ 2 SubOpt(N, C ∗ , k, ε, 0) = O e− 2 ln 8(C ∗ −1) + 2 ln C ∗ . Proof. When a0 = a∗ , we bound E [µ(a∗ ) − µ(â′ )] as follows, E [µ(a∗ ) − µ(â′ )] ≤ Pr [â′ ̸= a∗ ] ≤ Pr [∃a ̸= a∗ , N (a) ≥ N (a∗ ) − k] ≤ Pr [N − N (a∗ ) ≥ N (a∗ ) − k] N +k ∗ = Pr N (a ) ≤ . 2 ∗

)N , we have that N 2+k ≤ CN∗ . Then applying Chernoff’s bound for binomial random variables, we have Since k ≤ (2−C C∗ N +k N +k 1 ∗ Pr N (a ) ≤ ≤ exp −N · KL Ber Ber 2 2N C∗ N + k (N + k)C ∗ N −k (N − k)C ∗ = exp −N ln + ln 2N 2N 2N 2N (C ∗ − 1) ∗ (a) N +k 2 N −k C ≤ exp ln ∗ − ln , 2 C 2 8(C ∗ − 1) N −k C∗ ∗ where (a) is from k ≤ 3N . When C → 1, the second term ln ∗ 4 2 8(C −1) dominates, and the resulting probability is

on the order of (C ∗ − 1)

N −k

, which matches the lower bound in Theorem 3.9 in its dependence on N, C ∗ , k. 23

Unlearning Offline Stochastic Multi-Armed Bandits

When a0 ̸= a∗ , we know that N −k N +k E [µ(a∗ ) − µ(â′ )] ≤ Pr [N − N (a∗ ) − k ≥ N (a∗ )] ≤ Pr N (a∗ ) ≤ ≤ Pr N (a∗ ) ≤ . 2 2 Therefore this bound is smaller than the corresponding bound in the case a0 = a∗ . In conclusion, (N −k) (N +k) C∗ 2 SubOpt(N, C ∗ , k, ε, 0) = O e− 2 ln 8(C ∗ −1) + 2 ln C ∗ .

A.5. Multi-Source Unlearning under Mf Algorithm 7 Multi-source unlearning algorithm under Mf c, unlearning request: U = Sℓ Ui , Ui is from au , b N Input: Output of π(D): â, additional statistics T (D): fb(D), µ, i i=1 |Ui | = ki , a confidence level: τ ∈ (0, 1) 1: Set fb(D ′ ) ← fb(D) 2: for i = 1 to ℓ do 3: if (â = auiq ) then π ln m

4: 5: 6:

γ0 ← 34 Nmin −kτmax if (γ < γ0 ) then i Set ∆f ← 2N3k (au ) , σ ← ∆f γ

7: 8: 9: 10: 11:

Sample ν ∈ R from N (0, σ 2 ) Set fb(aui ) (D′ ) ← fb(aui ) (D′ ) + ν end if else Set N ′ (aui ) ← N (aui ) − ki

Compute the new empirical mean reward µ̂′ (aui ) ← q ln m 13: Compute the new penalty b′ (aui ) ← 2N ′ (aτu ) i 14: Set fb(aui ) (D′ ) ← µ̂′ (aui ) − b′ (aui ) 15: end if 16: end for Output: â′ = arg maxa fb(a) (D′ ) 12:

P µ̂(aui )·N (aui )− (au ,r )∈U rj N ′ (aui )

Algorithm 8 Multi-source unlearning algorithm under Mf with input ∅ ℓ

Input: Output of π(D′ ), additional statistics T (D′ ): π(D) = â, {aui }i=1 , ki , N (aui ) for i ∈ [ℓ], fb(D′ ), a confidence level: τ ∈ (0, 1) 1: for i = 1 to ℓ do 2: if (â = auiq ) then 3: 4: 5:

π ln m

γ0′ ← 43 Nmin −kτmax if (γ < γ0 ) then i Set ∆f ← 2N3k (au ) , σ ← ∆f γ i

6: Sample ν ∈ R from N (0, σ 2 ) 7: Set fb(aui ) (D′ ) ← fb(aui ) (D′ ) + ν 8: end if 9: end if 10: end for

Output: â′ = arg maxa fb(a) (D′ ) 24

Unlearning Offline Stochastic Multi-Armed Bandits ℓ ℓ We let au1 be the arm with the largest fb(a) (D) among {aui }i=1 without loss of generality. Therefore if â ∈ {aui }i=1 , then ′ ′ â = au1 . Moreover, let µ̂ (a) = µ̂(a), b (a) = b(a) if arm a does not rollback.

For every aui , the way to achieve (ε, δ)-UL is the same as Algorithm 2. Since Algorithm 7 will add gaussian noise to at most one arm au1 and execute rollback on other arms, by applying Theorem 3.2, we could obtain that Algorithm 7 and ℓ Algorithm 1 are (ε, δ)-UL. Then we give an upper bound of sub-optimality SubOpt(N , N∗ , {ki }i=1 , ε, δ). Sℓ Theorem A.13 (Theorem 3.13 restated). Consider any offline dataset D(N ), any unlearning request Ui where q U = i=1 N (aui ) ln m ∗ τ , ∀i ∈ [ℓ], Ui is selected from the data points of aui . N (a ) ≥ N∗ , |Ui | = ki , ∀i ∈ [ℓ]. When ki ≤ N (aui ) − 2 q ln(N m) kmax < Nmin , by setting τ = N1 , the arm â′ returned by Algorithm 7 satisfies when γ < γ0′ = 34 Nπmin −kmax , s    s  ln (N m) k · γ ln (N m)  max ℓ SubOpt(N , N∗ , {ki }i=1 , ε, δ) = O max + , .  Nmin Nmin N∗  while when γ ≥ γ0′ ,  ℓ

SubOpt(N , N∗ , {ki }i=1 , ε, δ) = O max

s  

ln (N m) , Nmin − kmax

 ln (N m)  . N∗ 

q m ln τ ℓ Proof. When γ < γ0′ , we first consider the case where a∗ ∈ {aui }i=1 . Denote E1 as the event that |µ̂(a) − µ(a)| ≤ 2N (a) q ln m ℓ ′ τ for every a ∈ A on dataset D and |µ̂′ (aui ) − µ(aui )| ≤ 2(N (au −ki ) for every aui ∈ {aui }i=1 on D . Applying i

ℓ

Hoeffding’s inequality for a fixed arm a ∈ A and aui ∈ {aui }i=1 , we have s s # " # " ln m ln m 2τ 2τ ′ τ τ ≥1− , Pr |µ̂ (aui ) − µ(aui )| ≤ ≥1− Pr |µ̂(a) − µ(a)| ≤ 2N (a) m 2(N (aui ) − ki ) m ℓ

which implies that Pr [E1 ] ≥ 1 − 4τ using the unionpbound. Furthermore, regardless of whether â ∈ {aui }i=1 occurs or not, we could always let E2 be the event that |ν| ≤ σ 2 ln m τ = t, according to the property of Gaussian Md , we have t2

Pr [|ν| ≤ t] ≥ 1 − 2e− 2σ2 = 1 −

2τ , m

then we obtain Pr [E2 ] ≥ 1 − τ since m ≥ 2. Therefore under the condition that E = E1 ∩ E2 occurs, for every a ∈ A, ℓ aui ∈ {aui }i=1 and ν, we have s r ln m m ′ τ |µ̂(a) − µ(a)| ≤ b(a), |µ̂ (aui ) − µ(aui )| ≤ , |ν| ≤ σ 2 ln . 2(N (aui ) − ki ) τ ℓ If the event â ∈ {aui }i=1 (i.e. â = au1 ) occurs, Algorithm 7 will add Gaussian noise sampled from N (0, σ 2 ) to fb(au1 ) (D) and execute rollback on aui , 2 ≤ i ≤ ℓ. There are also two branches of whether â = a∗ or not. If â = a∗ , in view of the definition of â′ , for â′ ̸= â, we have

µ(â′ ) ≥ fb(â′ ) (D′ ) ≥ fb(a∗ ) (D) + ν ≥ µ(a∗ ) − 2b(a∗ ) + ν. Else â ̸= a∗ , for â′ ̸= â, we have µ(â′ ) ≥ fb(â′ ) (D′ ) ≥ fb(â) (D) + ν ≥ fb(a∗ ) (D) + ν ≥ µ(a∗ ) − 2b(a∗ ) + ν. otherwise â′ = â and the sub-optimality is bounded by the learning algorithm. And in both branches â′ ̸= â occurs only if ν < 0. Similarly we could prove that s 2 ln m σ ∗ ′ τ +√ . E [µ(a ) − µ(â )] ≤ N (a∗ ) 2π 25

Unlearning Offline Stochastic Multi-Armed Bandits ℓ

If the event â ∈ / {aui }i=1 occurs, Algorithm 7 will execute rollback on all aui . Before the rollback, we know that fb(â) (D) > fb(a∗ ) (D) ≥ µ(a∗ ) − 2b(a∗ ) and fb(â) (D) remains the same after the rollback. For any â′ ̸= â, we know that µ(â′ ) ≥ fb(â′ ) (D′ ) ≥ fb(â) (D) ≥ fb(a∗ ) (D) ≥ µ(a∗ ) − 2b(a∗ ). In conclusion, when a∗ = auj for some j ∈ [ℓ], the expected sub-optimality satisfies: E [µ(a∗ ) − µ(â′ )] ≤ E [µ(a∗ ) − µ(â′ ) | E] + Pr [E c ] · E [µ(a∗ ) − µ(â′ ) | E c ] 2 h h i i h h i i X ℓ ℓ = E (µ(a∗ ) − µ(â′ )) 1 â ∈ {aui }i=1 E + E (µ(a∗ ) − µ(â′ )) 1 â ∈ / {aui }i=1 E + Pr Ejc j=1

s h i ℓ ≤ Pr â ∈ {aui }i=1 E · s ≤ s ≤

2 ln m σ τ +√ N (a∗ ) 2π

s i h ℓ + Pr â ∈ / {aui }i=1 E ·

2 ln m τ +τ N (a∗ )

! + 5τ

2 ln m σ τ + √ + 5τ ∗ N (a ) 2π 2 ln (N m) 5 3kmax γ + . + √ Nmin N 2 2πNmin ℓ

ℓ

The second case is a∗ ∈ / {aui }i=1 . Regardless of whether the event â ∈ {aui }i=1 occurs or not, fb(a∗ ) (D) will remain the same. Thus the expected sub-optimality will not be worse than the learning algorithm, therefore s 2 ln (N m) 2 E [µ(a∗ ) − µ(â′ )] ≤ E [µ(a∗ ) − µ(â)] ≤ + . N∗ N In conclusion, when γ < γ0′ , the upper bound satisfies  q  ℓ ln(N m) kmax γ  , a∗ ∈ {aui }i=1 , O Nmin + Nmin q E [µ(a∗ ) − µ(â′ )] =  ℓ ln(N m)  , a∗ ∈ / {aui }i=1 . O N∗ ℓ

ℓ

When γ ≥ γ0′ , Algorithm 7 executes rollback on all a ∈ {aui }i=1 . Additionally when a∗ ∈ / {aui }i=1 , we could similarly prove that the expected sub-optimality will not be worse than the learning algorithm, thus s 2 ln (N m) 2 ∗ ′ ∗ E [µ(a ) − µ(â )] ≤ E [µ(a ) − µ(â)] ≤ + . N (a∗ ) N ℓ

When a∗ ∈ {aui }i=1 , the upper bound satisfies E [µ(a∗ ) − µ(â′ )] ≤ E [µ(a∗ ) − µ(â′ ) | E] + Pr [E c ] · E [µ(a∗ ) − µ(â′ ) | E c ] s 2 ln (N m) 5 ≤ + . Nmin − kmax N In conclusion, when γ ≥ γ0′ , the upper bound satisfies  q  ℓ ln(N m) O , a∗ ∈ {aui }i=1 ,  Nmin −kmax ∗ ′ q E [µ(a ) − µ(â )] =  ℓ ln(N m)  , a∗ ∈ / {aui }i=1 . O N∗

Unlearning Offline Stochastic Multi-Armed Bandits ℓ

How to obtain γ0′ Similarly, the threshold γ0′ is optimized in the case a∗ ∈ {aui }i=1 , since the upper bound is fixed to be q ℓ ln(N m) O when a∗ ∈ / {aui }i=1 . Let ∗ N (a ) s

and we could obtain that γ = 3√N

2 ln m τ = Nmin − kmax √ m

2 ln m 3kmax γ τ + √ , Nmin 2 2πNmin

πNmin ln τ √ √ ≈ 43 −k Nmin −kmax + Nmin ) ( min max 4

π ln m ′ τ Nmin −kmax = γ0 .

B. Experiments The experiments are performed on a Dell Inspiration 16 PLUS 7620 laptop equipped with a 12th Generation Intel(R) Core(TM) i7-12700H CPU running at 2.30 GHz, alongside 16 GB of RAM. The operating system utilized is Windows 11, and the Python version employed is 3.13.5. B.1. Additional Experimental Details of Section 4.1 We generate synthetic offline bandit data using a round-robin behavior policy over 5 arms with Bernoulli rewards µ = (0.10, 0.08, 0.06, 0.04, 0.02). For each experimental configuration, we generate 200 independent trajectories and evaluate the algorithms under a prefix-sharing protocol. Unless otherwise stated, trajectories are partitioned into blocks with an effective block size of B = 100. Deletion protocols. For experiments that vary the total sample size N or the parameter γ, deletions always target the first 5 blocks of a designated arm a0 . For experiments that vary the deletion size k, we fix N = 3000 and delete all samples of arm a0 within a sequence of consecutive blocks, with the number of blocks ranging from 1 to 25. Under the round-robin behavior policy, each block contains approximately B/5 = 20 samples per arm. As a result, deleting between 1 and 25 consecutive blocks of arm a0 corresponds to deletion sizes ranging from k = 20 to k = 500, which explains the range of k considered in Figure 1. In both experimental settings, each prefix is subjected to 5 independent deletion requests. We consider both the hard deletion case, where a0 = a∗ is the optimal arm, and the easy deletion case, where a0 is the second-best suboptimal arm. All results are averaged over 10 independent runs per configuration. Reporting protocol. Due to multiple sources of randomness—including stochastic rewards, the behavior policy, and randomized baselines—the variance across runs is highly heterogeneous across methods and parameter regimes. Plotting error bars in a single figure would therefore significantly clutter the visualization and obscure the main trends. For clarity, we only report mean performance across runs. Implementation details. Although we describes blocks of size B = 100 for ease of exposition here, in the actual implementation we generate blocks of size B/2 = 50. Two consecutive blocks are treated as a single logical block when reporting results, so that the effective block size remains B = 100. This design choice is motivated by the mixing baseline: for each logical block, we split the samples into two disjoint subsets, using one half for the rollback step and the other half for the Gaussian mechanism. Generating blocks of size B/2 allows this split to be implemented cleanly at the block level without introducing additional randomness. Importantly, this implementation detail does not affect the total sample size, the prefix-sharing protocol, or the effective deletion sizes reported in the main text. All reported results are therefore consistent with the description in Section 4.1. B.2. Additional Experimental Details of Section 4.2 To study the C ∗ ∈ [2, +∞) case, we study the performance of our methods under a stochastic behavior policy that selects the optimal arm with probability 1/C ∗ , C ∗ = 5 and distributes the remaining probability uniformly over suboptimal arms, inducing controlled imbalance in the data. Prefixes of length N ∈ {1000, . . . , 5000} are used. For experiments varying N or γ, deletions target a designated arm with k = 80 samples per prefix. For experiments varying the deletion size k (ranging from 20 to 500 at fixed N = 3000), k consecutive samples are removed. In both cases, each prefix undergoes 5 independent deletion requests. The configurations are also averaged over 10 runs for each configuration. This setup isolates the effect of data imbalance on unlearning performance. 27

Unlearning Offline Stochastic Multi-Armed Bandits

B.3. Experiments of Algorithm 4 In the experiments below, we focus exclusively on the hard deletion case where a∗ = a0 . This choice is motivated by the design of Algorithm 4, in which the mixing parameter is set to k ′ = k whenever â ̸= a0 . As a result, for easy deletion cases (a∗ ̸= a0 ), different values of η do not produce meaningful differences across algorithms, and including these cases would not provide additional insights. We adopt the same experimental setup as described below to evaluate the performance of Algorithm 4, except for a minor implementation difference in the fixed-sample model. Specifically, in the fixed-sample model, each logical block of size B = 100 is further partitioned into 4 equal-sized sub-blocks of size B/4 = 25. This construction allows us to implement different mixing ratios η ∈ {0, 0.25, 0.5, 0.75, 1}, where η = k ′ /k controls the fraction of samples allocated to the rollback step, and the remaining samples are processed using the Gaussian mechanism. In particular, η = 0 corresponds to the pure Gaussian mechanism, while η = 1 corresponds to the pure rollback procedure. Intermediate values of η are realized by assigning the corresponding number of sub-blocks to rollback. Apart from this block-level construction in the fixed-sample model, all other aspects of the experimental protocol—including data generation, prefix-sharing, deletion strategies, and evaluation metrics—remain identical to those described in the main text. In particular, the experiments under the distribution model use exactly the same configuration as in Section 4. Figure 2 shows that optimal performance is achieved at the two extremes η = 0 and η = 1 at almost all time, which validates the design choices behind Algorithm 2 and Algorithm 6. We only need to consider the trade-off between Gaussian mechanism and rollback.

= 0.0

Oracle ×10 2

= 0.25 2.0

2.0 1.5 1.0 0.5

= 0.5

0.5 4

5 ×103

(a) Mf , hard case

×10 2

5 ×102

(b) Mf , hard case

×10 2

2.0 1.5

1.0

SubOpt

1.5 1.0

1.0

0.5

SubOpt

2 2.0 ×10

1.00 0.75 0.50 0.25 0.00 0.005 0.050 0.500 5.000 50.000

SubOpt

1.0

= 1.0

×10 2

1.5

= 0.75

0.5

0.5 1

(d) Md , hard case

5 ×103

5 ×102

(e) Md , hard case

0.0 0.005 0.050 0.500 5.000 50.000 (f) Md , hard case

∗

Figure 2. Comparison of Algorithm 4 with baselines under Mf (uniform) and Md (C = 5) when fixing γ = 0.5 and k = 80, fixing γ = 0.5 and N = 3000, and fixing k = 80 and N = 3000.

B.4. Experiments of Algorithm 7 The experimental setup follows the same protocol as described in Section B.1, except that we focus exclusively on the fixed-sample setting, in accordance with the theoretical analysis of the multi-source unlearning algorithm. For the 5-arm fixed-sample model with ordering 0 > 1 > 2 > 3 > 4, the hard case corresponds to deleting k samples each from arms 0 and 1, while the easy case corresponds to deleting k samples each from arms 2 and 3. All other aspects of the experimental protocol—including block construction, prefix-sharing, and evaluation over multiple independent runs—remain identical to those described in Section B.1. 28

Unlearning Offline Stochastic Multi-Armed Bandits

Figure 3 shows that Algorithm 7 consistently exhibits robust and competitive performance across all configurations. In the hard case, where deletions affect the top arms, Algorithm 7 remains consistently competitive and avoids the sharp degradation observed for the Gaussian mechanism under large γ or large k. Quantitatively, when N = 2000 and γ = 0.05, it achieves 8% (k = 40) and 9% (k = 80) reduction in sub-optimality relative to the Gaussian mechanism, and 17% (k = 40) and 12% (k = 80) reduction relative to rollback when deletions are severe. As N increases, the performance gap narrows and Algorithm 7 remains perform better than Gaussian mechanism and rollback, demonstrating stable behavior even under adversarial deletion patterns. In the easy case, the algorithm achieves sub-optimality that is nearly identical to the Oracle and rollback baselines across all settings, while significantly outperforming the Gaussian mechanism. For example, when N = 2000 and γ = 0.5, Algorithm 7 reduces sub-optimality by more than 80% relative to the Gaussian mechanism, and remains either the best-performing method or within 1% of it. This behavior persists as N increases to 4000, indicating that the algorithm scales favorably with sample size while maintaining stability. Overall, these results highlight a consistent trend: while baseline methods can be optimal in specific regimes, their performance varies substantially across configurations. In contrast, Algorithm 7 maintains low sub-optimality across both hard and easy cases, offering a robust trade-off between accuracy and unlearning effectiveness in the multi-source fixed-sample setting.

Oracle

Rollback

Gaussian

Alg7

2.00 1.75

SubOpt (×10 2)

0.6 0.4

1.50 1.25 1.00 0.75

0.2

0.50

0.0

0.00

(a) Mf , hard case

Figure 3. Comparison of Algorithm 7 with baselines under Mf (uniform).

0) ,8

0.5 00 ,

0.5

00 ,

5, 8

(b) Mf , easy case

(40

(N, , k)

(40

0.0 00 ,

(40

0.0

(40

00 ,

5, 4

0) ,8

0.5

(20

00 ,

0.5

5, 8

00 ,

0.0 00 ,

(20

0.0

(20

00 ,

5, 4

) 80 .5,

) 40

.5, (40

0) ,8

00 (40

(N, , k)

0) (40

.05

) (40

.05

80 .5,

) 40

(20

.5,

,8 (20

0) ,0 00 (20

,0 00 (20

.05

0.25

.05

SubOpt (×10 2)

0.8

Record · ID 151746 · SHA-256 f861819cf8f1bcb3
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.