Exact Unlearning in Reinforcement Learning

# Exact Unlearning in Reinforcement Learning
Source: [https://arxiv.org/html/2606.04182](https://arxiv.org/html/2606.04182)
###### Abstract

We formulate the problem of*exact unlearning*in reinforcement learning, where the goal is to design an efficient framework that enables the removal of any user’s data upon deletion request, i\.e\., the online learner’s output after unlearning is*indistinguishable*from what would have been produced had the deleted user never interacted with the learner\. For anyρ\>0\\rho\>0, we show that there exists a reinforcement learning \(RL\) algorithm that isρ\\rho\-TV\-stable and supports an exact unlearning procedure whose expected computational cost is only aρ​ln⁡T\\rho\\sqrt\{\\ln T\}fraction of the computational cost of retraining from scratch\. We construct such aρ\\rho\-TV\-stable RL algorithm for tabular Markov decision processes \(MDPs\), which achieves a regret bound of𝒪​\(H2​S​A​T\+H3​S2​A\+H2\.5​S2​A/ρ\)\\mathcal\{O\}\(H^\{2\}\\sqrt\{SAT\}\+H^\{3\}S^\{2\}A\+\{H^\{2\.5\}S^\{2\}A\}/\{\\rho\}\), whereS,A,HS,A,H, andTTdenote the number of states, the number of actions, the episode horizon, and the number of episodes, respectively\. We also establish a lower bound ofΩ​\(H​S​A​T\+S​A​H/ρ\)\\Omega\(H\\sqrt\{\\\!SAT\}\\\!\+\\\!\{SAH\}/\{\\rho\}\)forρ\\rho\-TV\-stable RL algorithms, showing that our algorithm is nearly minimax optimal\.

Machine Learning, ICML

## 1Introduction

Machine unlearning is a relatively new area of research that aims to efficiently remove the influence of specific data from a machine learning \(ML\) model in response to a data modification or deletion request\(Cao and Yang,[2015](https://arxiv.org/html/2606.04182#bib.bib42); Bourtouleet al\.,[2021](https://arxiv.org/html/2606.04182#bib.bib6)\)\. This need arises from growing privacy concerns and legal requirements mandating that certain user data, along with its effect on a model, be completely removed\. Such concerns are motivated by the vulnerability of ML models to attacks such as membership inference\(Shokriet al\.,[2017](https://arxiv.org/html/2606.04182#bib.bib24)\)and model inversion\(Fredriksonet al\.,[2015](https://arxiv.org/html/2606.04182#bib.bib22)\), which can leak sensitive training data\.

Moreover, various data protection laws have enshrined users’*right to be forgotten*, including the General Data Protection Regulation \(GDPR\) in the European Union\(GDPR,[2018](https://arxiv.org/html/2606.04182#bib.bib16)\), the California Consumer Privacy Act \(CCPA\)\(Bonta,[2022](https://arxiv.org/html/2606.04182#bib.bib21)\), the Act on the Protection of Personal Information \(APPI\) in Japan\(JDPO,[2019](https://arxiv.org/html/2606.04182#bib.bib17)\), and Canada’s proposed Consumer Privacy Protection Act \(CPPA\)\(CPPA,[2023](https://arxiv.org/html/2606.04182#bib.bib18)\)\. Beyond regulatory compliance, machine unlearning also offers practical benefits: it can be used to remove poisoned clients or compromised nodes in federated systems\(Jinet al\.,[2023](https://arxiv.org/html/2606.04182#bib.bib33)\), delete copyrighted or proprietary content from models\(Eldan and Russinovich,[2023](https://arxiv.org/html/2606.04182#bib.bib34)\), accelerate leave\-one\-out validation, support user data marketplaces, and identify high\-value data points within a model\(Ginartet al\.,[2019](https://arxiv.org/html/2606.04182#bib.bib1), p\. 2\)\.

Machine unlearning requires that the model’s output after unlearning be*indistinguishable*from the output that would have been produced had the requested user data never been included in the training process\. While there is no universally accepted definition of indistinguishability in this context, two primary notions of certified unlearning have emerged: exact unlearning\(Ullahet al\.,[2021](https://arxiv.org/html/2606.04182#bib.bib10); Ullah and Arora,[2023](https://arxiv.org/html/2606.04182#bib.bib2)\)and approximate unlearning\(Guoet al\.,[2019](https://arxiv.org/html/2606.04182#bib.bib37); Neelet al\.,[2021](https://arxiv.org/html/2606.04182#bib.bib3); Sekhariet al\.,[2021](https://arxiv.org/html/2606.04182#bib.bib36); Allouahet al\.,[2024](https://arxiv.org/html/2606.04182#bib.bib32); Van Waerebekeet al\.,[2025](https://arxiv.org/html/2606.04182#bib.bib31)\)\.

#### Why exact unlearning in RL?

Approximate unlearning is less stringent and typically enables more efficient algorithms with improved space complexity\. However, it does not guarantee full removal of a user’s influence, which can be problematic in practice, particularly because it is difficult to determine an appropriate approximation parameter that ensures adequate privacy protection\. As a result, organizations that train large\-scale models may prefer exact unlearning, accepting the cost of increased memory usage during training in order to avoid potentially catastrophic consequences of a privacy breach, especially if even a single individual can demonstrate that their personal data remains embedded in a deployed model\. This is particularly relevant for interactive systems \(recommendation, personal assistants, healthcare triage\) that continually log per\-user episodes\. Deletion requests arise for privacy \(right\-to\-be\-forgotten, membership inference risk\), safety \(removing poisoned/outlier interactions\), compliance \(per\-user auditability\), and engineering \(fast leave\-one\-user\-out diagnostics\) reasons\. Our framework lets operators retrofit a strong deletion guarantee on to regret\-optimal learners while keeping retraining rare and localized, which is valuable even in tabular settings that back many real\-world pipelines \(e\.g\., bandits with context bucketing\)\.

To date, most work on machine unlearning has focused on supervised and unsupervised learning settings, where data points are static and independently processed\. However, many real\-world systems, such as recommender platforms, digital assistants, and personalized healthcare tools, are interactive in nature and rely on reinforcement learning \(RL\) to model sequential user interactions\. In these systems, data arises not from isolated inputs but from temporally extended experiences with users\.

RL is a fundamental paradigm for sequential decision\-making, where an agent learns to maximize cumulative reward in an unknown environment through trial and error\. With its growing adoption in personalized services, ranging from online recommendations to virtual assistants and social robotics, RL algorithms increasingly interact with streams of users, adapting continuously based on their behaviors\. This naturally raises the same privacy concerns central to machine unlearning:*how can we remove the influence of a particular user’s interaction history from an RL system when requested?*

Our motivation stems from personalized, interactive systems, e\.g\., voice assistants, recommender platforms, medical data trajectories, or personalized tutors, where episodic RL interactions correspond to identifiable users\. Here is a concrete example inspired by the work of\(Shaniet al\.,[2005](https://arxiv.org/html/2606.04182#bib.bib23)\)\.

###### Example 1\.1\.

Recommender systems \(e\.g\., product recommendations on e\-commerce platforms such as Amazon\) are often modeled as MDPs, where an RL agent acts as the recommender\. The system interacts sequentially with different users, each corresponding to an episodett\. An action is an item recommendation, and the user’s state at episodettand stephhcan be represented by their lastkkselected items, i\.e\.,sh=\(ah−k,…,ah−1\)s\_\{h\}=\(a\_\{h\-k\},\\ldots,a\_\{h\-1\}\), since recent history is most relevant for prediction\. Given a recommendationaa, the user may accept it, transitioning fromsh=\(ah−k,…,ah−1\)s\_\{h\}=\(a\_\{h\-k\},\\ldots,a\_\{h\-1\}\)tosh\+1=\(ah−k\+1,…,ah−1,a\)s\_\{h\+1\}=\(a\_\{h\-k\+1\},\\ldots,a\_\{h\-1\},a\), or instead select a non\-recommended itema′a^\{\\prime\}, transitioning tosh\+1=\(ah−k\+1,…,ah−1,a′\)s\_\{h\+1\}=\(a\_\{h\-k\+1\},\\ldots,a\_\{h\-1\},a^\{\\prime\}\)\. The reward reflects the utility of selling items to the user, while thesampledrewards and transitions at episodettcapture the characteristics of the user interacting with the system\. A user who interacts with the recommender at timettmay later request removal of her interaction data, due to privacy or other concerns\. Crucially, it is not enough to delete the raw data, we must remove its influence on the trained system\.

Despite the relevance and urgency of this question, the problem of unlearning in RL remains largely unaddressed\. In this work, we aim to bridge this gap by formulating and addressing the problem of exact unlearning in RL \(see[2\.1](https://arxiv.org/html/2606.04182#A4.EGx3)\)\. Our goal is to design sample\-efficient RL algorithms that enable the efficient removal of any user’s data upon request, while ensuring that the resulting model behavior is indistinguishable from one trained without that data\. Our key results are as follows:

1. 1\.We formulate the problem of exact unlearning in reinforcement learning\. To do so, we abstract RL into a general class of sequential learning problems with prefix sum structure, and develop a unified \(un\)learning framework based on the recent notion of Total Variation \(TV\) stability\(Ullahet al\.,[2021](https://arxiv.org/html/2606.04182#bib.bib10); Ullah and Arora,[2023](https://arxiv.org/html/2606.04182#bib.bib2)\)\(see[Section3](https://arxiv.org/html/2606.04182#S3)\)\.
2. 2\.We show that, for anyρ\>0\\rho\>0, there exists an efficient RL algorithm for tabular Markov decision processes \(MDPs\) that isρ\\rho\-TV\-stable \(see[2\.2](https://arxiv.org/html/2606.04182#S2.Thmdefn2)\) and achieves a regret bound of𝒪~​\(H2​S​A​T\+H3​S2​A\+H2\.5​S2​Aρ\),\\tilde\{\\mathcal\{O\}\}\\left\(H^\{2\}\\sqrt\{SAT\}\+H^\{3\}S^\{2\}A\+\\frac\{H^\{2\.5\}S^\{2\}A\}\{\\rho\}\\right\),whereS,A,H,TS,A,H,Tdenote the number of states, the number of actions, the horizon, and the number of episodes, respectively \(see[Section4](https://arxiv.org/html/2606.04182#S4)\)\. This algorithm admits an efficient exact unlearning algorithm whose expected computational cost is onlyρ​ln⁡T\\rho\\sqrt\{\\ln T\}fraction of the cost of retraining from scratch \(see[Section3](https://arxiv.org/html/2606.04182#S3)\)\.
3. 3\.We derive a minimax lower bound ofΩ​\(H​S​A​T\+H​S​Aρ\)\\Omega\\left\(H\\sqrt\{SAT\}\+\\frac\{HSA\}\{\\rho\}\\right\)for the class ofρ\\rho\-TV\-stable RL algorithms, demonstrating that our upper bound is nearly tight \(see[Section4\.1](https://arxiv.org/html/2606.04182#S4.SS1)\)\.

#### Overview of Techniques\.

Our work builds onUllah and Arora \([2023](https://arxiv.org/html/2606.04182#bib.bib2)\)who showed that TV\-stability is both sufficient and necessary for exact unlearning in batch supervised learning in a natural coupling\-based learning framework\. Extending this theory to sequential RL is highly non\-trivial as it requires a\) establishing TV\-stable RL algorithms and \(b\) proving that these algorithms simultaneously achieve near\-optimal regret\.

We extend UCB\-VI\(Azaret al\.,[2017](https://arxiv.org/html/2606.04182#bib.bib26)\)in a non\-trivial manner to achieve exact unlearning\. Our RL algorithm is the first regret\-optimal variant that is alsoρ\\rho\-TV\-stable and supports exact unlearning\. This requires \(i\) replacing visitation statistics with binary\-tree, noise\-perturbed prefix sums while preserving optimism, \(ii\) storing intermediate sufficient statistics in a coupling\-compatible way so that unlearning can reuse randomness via maximal coupling, \(iii\) extending regret proof to control additional variance from correlated Gaussian noise, matching UCB\-VI up to log factors\.

We also establish the first minimax lower bound for the regret of TV\-stable algorithms\. Our contribution thus lies in integrating and extending these foundational ideas into the RL setting with explicit algorithms and rigorous theoretical analysis, filling a significant gap in the literature\.

#### Related Work\.

In the broader landscape, a number of important developments have emerged across different learning tasks\. While we do not attempt to be exhaustive, we highlight several key contributions\. The term machine unlearning was first introduced byCao and Yang \([2015](https://arxiv.org/html/2606.04182#bib.bib42)\), who proposed a deterministic notion of data deletion in trained models\. Their work focused on statistical query problems under restrictive structural assumptions\.Ginartet al\.\([2019](https://arxiv.org/html/2606.04182#bib.bib1)\)initiated the study of approximate unlearning via differential privacy, focusing on thekk\-means problem\. This line of work was extended to linear and logistic regression byGuoet al\.\([2019](https://arxiv.org/html/2606.04182#bib.bib37)\), and to general convex models byNeelet al\.\([2021](https://arxiv.org/html/2606.04182#bib.bib3)\)\.

The work most closely related to ours is that ofUllahet al\.\([2021](https://arxiv.org/html/2606.04182#bib.bib10)\); Ullah and Arora \([2023](https://arxiv.org/html/2606.04182#bib.bib2)\)\. These works formalize the notion of exact unlearning in the batch setting, particularly in connection with adaptive query release mechanisms\. In contrast, we study exact unlearning in the context of sequential learning, specifically within reinforcement learning and regret minimization\. While our setting is distinct, we adopt their notion of exact unlearning and build on similar algorithmic primitives, most notably, the use of prefix sums, to support efficient unlearning in an online framework\.

In the context of RL, prior work on unlearning is extremely limited\. To our knowledge, the only relevant effort is byYeet al\.\([2023](https://arxiv.org/html/2606.04182#bib.bib28)\), who introduced the concept of reinforcement unlearning\. However, in their setting, multiple distinct MDPs are trained simultaneously \(e\.g\., for different tasks or domains\), and unlearning involves removing an entire MDP rather than individual user episodes within a single MDP\. In contrast, we consider a more granular and practical objective: unlearning at the level of an individual user’s interaction\. Furthermore, whileYeet al\.\([2023](https://arxiv.org/html/2606.04182#bib.bib28)\)empirically study approximate unlearning, they do not provide theoretical guarantees or analyze its effect on regret\. Our work differs in that we provide a finite\-sample regret bound for exact unlearning, along with a matching lower bound\.

Finally, our work is related to the growing literature on differentially private reinforcement learning\(Vietriet al\.,[2020](https://arxiv.org/html/2606.04182#bib.bib41); Zhou,[2022](https://arxiv.org/html/2606.04182#bib.bib5); Chowdhury and Zhou,[2022](https://arxiv.org/html/2606.04182#bib.bib4); Qiao and Wang,[2023](https://arxiv.org/html/2606.04182#bib.bib44)\)\. While differential privacy shares conceptual similarities with approximate unlearning \(indeed, some techniques overlap\), its guarantees are fundamentally different\. Differential privacy requires that model outputs be statistically similar whether or not a single datapoint is included in the training set\. In contrast, exact unlearning demands that the resulting model be identically distributed to one trained without the deleted data\. As such, results in differential privacy and approximate unlearning do not directly imply guarantees for exact unlearning\. Nevertheless, techniques developed in the differential privacy literature, such as the binary tree mechanism, play a crucial role in our framework\.

While preparing this paper, we became aware of parallel and independent work byHuet al\.\([2025](https://arxiv.org/html/2606.04182#bib.bib19)\), which studies unlearning in the setting of online convex optimization\. While both works address unlearning in online learning, there are two key distinctions\. First, our work focuses on*exact*unlearning, whereasHuet al\.\([2025](https://arxiv.org/html/2606.04182#bib.bib19)\)develop methods for*approximate*unlearning\. Second, we analyze unlearning in the context of MDPs, a structured, sequential setting that introduces additional challenges, while their work is situated in the stateless framework of online convex optimization\.

## 2Problem Setup and Preliminaries

Sequential learning problems arise in settings where an online stream of users \(or clients\) arrives over time, and the model must make real\-time, personalized decisions based on accumulated experience\. Common applications include online recommendation systems, virtual assistants, and adaptive educational platforms, where each user interaction provides feedback that informs future predictions or recommendations\. Formally, let𝒵\\mathcal\{Z\}denote the user space, where each userzt∈𝒵z\_\{t\}\\in\\mathcal\{Z\}represents an individual arriving at timett\. The learner maintains a modelwt∈𝒲w\_\{t\}\\in\\mathcal\{W\}drawn from a model space𝒲\\mathcal\{W\}, which is used to interact with userztz\_\{t\}\. In addition to the model, the learner may maintain auxiliary meta\-datamt∈ℳm\_\{t\}\\in\\mathcal\{M\}whereℳ\\mathcal\{M\}denotes the meta\-data space \(e\.g\., state visit counts, confidence intervals, or cumulative statistics\)\.

Upon interacting with the model, each user produces a responsext∈𝒳⊆ℝdx\_\{t\}\\in\\mathcal\{X\}\\subseteq\\mathbb\{R\}^\{d\}, which captures structured feedback from the interaction, such as observed rewards, state transitions, or implicit preferences\. This response is modeled by anenvironment oracle\{𝔼​𝕆t\}t≥1\\\{\{\\mathbb\{E\}\\mathbb\{O\}\}\_\{t\}\\\}\_\{t\\geq 1\}, which maps the user and the current model history to a feedback statistic:

xt=𝔼​𝕆t​\(zt;w1:t\),\\displaystyle x\_\{t\}=\{\\mathbb\{E\}\\mathbb\{O\}\}\_\{t\}\(z\_\{t\};w\_\{1:t\}\),wherew1:t=\{w1,w2,…,wt\}w\_\{1:t\}=\\\{w\_\{1\},w\_\{2\},\\ldots,w\_\{t\}\\\}denotes the sequence of models deployed thus far\.

For example, in an online movie recommendation system, each userztz\_\{t\}could represent an individual viewer with latent preferences\. The modelwtw\_\{t\}might encode a recommendation policy or ranking of items personalized to the current user base\. Upon presenting recommendations toztz\_\{t\}, the system observes their clicks or ratings, which are summarized inxtx\_\{t\}, such as which movies were selected, how long they were watched, or how they were rated\. This user feedback, formalized asxt=𝔼​𝕆t​\(zt;w1:t\)x\_\{t\}=\{\\mathbb\{E\}\\mathbb\{O\}\}\_\{t\}\(z\_\{t\};w\_\{1:t\}\), is then used to update the learner’s model going forward\. The overarching goal of the online learner𝐀:𝒵∗→𝒲∗×ℳ∗\\mathbf\{A\}:\\mathcal\{Z\}^\{\*\}\\rightarrow\\mathcal\{W\}^\{\*\}\\times\\mathcal\{M\}^\{\*\}is to produce a sequence of models\{w1,…,wt,…\}⊂𝒲\\\{w\_\{1\},\\ldots,w\_\{t\},\\ldots\\\}\\subset\\mathcal\{W\}that improve over time, continually adapting to better serve the evolving user population\.

#### Markov Decision Processes\.

Formally, we study sequential learning problems in the framework of reinforcement learning, wherein the user behavior is modeled using a Markov decision process \(MDP\)\. Specifically, an MDP is a tupleM=\(𝒮,𝒜,H,\{ℙh\}h∈\[H\],\{r¯h\}h∈\[H\]\)M=\(\\mathcal\{S\},\\mathcal\{A\},H,\\\{\\mathbb\{P\}\_\{h\}\\\}\_\{h\\in\[H\]\},\\\{\\bar\{r\}\_\{h\}\\\}\_\{h\\in\[H\]\}\)where𝒮\\mathcal\{S\}is the finite state space withS=\|𝒮\|S=\|\\mathcal\{S\}\|,𝒜\\mathcal\{A\}is the finite action space withA=\|𝒜\|A=\|\\mathcal\{A\}\|,HHis the episode horizon,r¯h:𝒮×𝒜→\[0,1\]\\bar\{r\}\_\{h\}:\\mathcal\{S\}\\times\\mathcal\{A\}\\rightarrow\[0,1\]is the expected reward function at stephh, andℙh:𝒮×𝒜→Δ​\(𝒮\)\\mathbb\{P\}\_\{h\}:\\mathcal\{S\}\\times\\mathcal\{A\}\\rightarrow\\Delta\(\\mathcal\{S\}\), defines the transition dynamics at stephh, whereΔ​\(𝒮\)\\Delta\(\\mathcal\{S\}\)denotes the set of all distributions over𝒮\\mathcal\{S\}\.

#### Interaction Protocol\.

At each episodett, the RL algorithm interacts with a*randomly drawn*user \(data\)zt:=\{\(sht,rht\)\}h∈\[H\]∈𝒵z\_\{t\}:=\\\{\(s\_\{h\}^\{t\},r\_\{h\}^\{t\}\)\\\}\_\{h\\in\[H\]\}\\in\\mathcal\{Z\}and recommends a sequence of actionsa1t,…,aHta^\{t\}\_\{1\},\\ldots,a^\{t\}\_\{H\}\. We assume that the user data is randomly drawn according to the underlying MDP transition kernel and reward function:sh\+1t∼ℙh\(⋅\|sht,aht\)s^\{t\}\_\{h\+1\}\\\!\\sim\\\!\\mathbb\{P\}\_\{h\}\(\\cdot\|s^\{t\}\_\{h\},a^\{t\}\_\{h\}\),rht∼R​\(r¯h​\(sht,aht\)\)r^\{t\}\_\{h\}\\\!\\sim\\\!R\(\\bar\{r\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\), andR​\(r\)R\(r\)is a reward distribution over\[0,1\]\[0,1\]with meanrr\.111We view a user dataz∈𝒵z\\in\\mathcal\{Z\}\(at an episodett\) as a depth\-HHtree, which defines the sequence of all possible reward\-state pairs\(rh,sh\+1\)h∈\[H\]\(r\_\{h\},s\_\{h\+1\}\)\_\{h\\in\[H\]\}in response to any RL algorithm’s action sequence\(a1,…,aH\)∈𝒜H\(a\_\{1\},\\ldots,a\_\{H\}\)\\in\\mathcal\{A\}^\{H\}\.This user\-episode abstraction is commonly adopted in the literature on privacy\-preserving RL\(Vietriet al\.,[2020](https://arxiv.org/html/2606.04182#bib.bib41); Zhou,[2022](https://arxiv.org/html/2606.04182#bib.bib5); Chowdhury and Zhou,[2022](https://arxiv.org/html/2606.04182#bib.bib4); Qiao and Wang,[2023](https://arxiv.org/html/2606.04182#bib.bib44)\)and MDP\-based personalized recommendation systems\(Shaniet al\.,[2005](https://arxiv.org/html/2606.04182#bib.bib23)\), where users generate distinct and identifiable reward/transition feedback over time \(also see[Example1\.1](https://arxiv.org/html/2606.04182#S1.Thmexample1)\)\. Crucially, there is a single fixed tabular MDP\(𝒮,𝒜,H,Ph,rh\)\(\\mathcal\{S\},\\mathcal\{A\},H,\{P\_\{h\}\},\{r\_\{h\}\}\)throughout\. A “user”ztz\_\{t\}is purely a label for episodettthat facilitates deletion requests; it is not a latent parameter that changes the environment across episodes\. Each episode generates a trajectory under the current policy in the same MDP\. The environment oracle𝔼​𝕆t\{\\mathbb\{E\}\\mathbb\{O\}\}\_\{t\}simply packages that episode’s trajectory statisticsxtx\_\{t\}for our prefix\-sum machinery\.

#### Policies and Value Functions\.

A \(non\-stationary\) policyπ=\(π1,…,πH\)\\pi=\(\\pi\_\{1\},\\ldots,\\pi\_\{H\}\)consists of decision rulesπh:𝒮→Δ​\(𝒜\)\\pi\_\{h\}:\\mathcal\{S\}\\rightarrow\\Delta\(\\mathcal\{A\}\), whereπh​\(a\|s\)\\pi\_\{h\}\(a\|s\)defines the distribution over actions at stephhin statess\. The value function of policyπ\\piat stephhis defined asVhπ​\(s\):=𝔼π​\[∑h′=hHrh′\|sh=s\]V^\{\\pi\}\_\{h\}\(s\):=\\mathbb\{E\}\_\{\\pi\}\[\\sum\_\{h^\{\\prime\}=h\}^\{H\}r\_\{h^\{\\prime\}\}\|s\_\{h\}=s\]where the expectation is over the randomness of the trajectory induced by followingπ\\pi\. The corresponding action\-value function isQhπ​\(s,a\)=𝔼π​\[∑h′=hHrh′\|\(sh,ah\)=\(s,a\)\]Q^\{\\pi\}\_\{h\}\(s,a\)=\\mathbb\{E\}\_\{\\pi\}\[\\sum\_\{h^\{\\prime\}=h\}^\{H\}r\_\{h^\{\\prime\}\}\|\(s\_\{h\},a\_\{h\}\)=\(s,a\)\]\. We denote byπ∗\\pi^\{\*\}an optimal policy and writeV∗=Vπ∗V^\{\*\}=V^\{\\pi^\{\*\}\}andQ∗=Qπ∗Q^\{\*\}=Q^\{\\pi^\{\*\}\}\. An RL algorithm𝐀\\mathbf\{A\}is an*instantiation*of the online learner𝐀:𝒵∗→𝒲∗×ℳ∗\\mathbf\{A\}:\\mathcal\{Z\}^\{\*\}\\rightarrow\\mathcal\{W\}^\{\*\}\\times\\mathcal\{M\}^\{\*\}we defined earlier in this section\. In particular, for this instantiation of the online learner to MDPs,*the model space𝒲\\mathcal\{W\}becomes the set of all policies*and*the meta\-data spaceℳ\\mathcal\{M\}captures any auxiliary information that is produced by the RL algorithm*\(e\.g\., visitation counts, noise terms, sufficient statistics\)\.

#### Regret Minimization\.

The goal of the RL algorithm is to minimize the regret overTTepisodes:

R​\(T\)=∑t=1T\(V1∗​\(s1t\)−V1πt​\(s1t\)\)\\displaystyle R\(T\)=\\sum\_\{t=1\}^\{T\}\(V^\{\*\}\_\{1\}\(s^\{t\}\_\{1\}\)\-V^\{\\pi^\{t\}\}\_\{1\}\(s^\{t\}\_\{1\}\)\)whereπt\\pi^\{t\}is the policy used in episodett, ands1ts\_\{1\}^\{t\}is the initial state of that episode\.

In a continual stream of user interactions, it is natural to consider scenarios where a user requests the removal of their data from the system\. This request requires not only the deletion of the user’s data but also the removal of its influence on the trained model\. An unlearning algorithm is designed to facilitate this process, ensuring that the model behaves as if the deleted data had never been seen\.

Formally, we define an*unlearning algorithm*𝐔:𝒲∗×ℳ∗×𝒵×𝒵→𝒲∗×ℳ∗\\mathbf\{U\}:\\mathcal\{W\}^\{\*\}\\times\\mathcal\{M\}^\{\*\}\\times\\mathcal\{Z\}\\times\\mathcal\{Z\}\\rightarrow\\mathcal\{W\}^\{\*\}\\times\\mathcal\{M\}^\{\*\}, which takes as input a sequence of models and meta\-data, along with a target userz∈𝒵z\\in\\mathcal\{Z\}to be deleted and a dummy userz′∈𝒵z^\{\\prime\}\\in\\mathcal\{Z\}used as a replacement\. The algorithm then outputs an updated sequence of models and meta\-data in which the influence ofzzhas been effectively removed and replaced by the influence ofz′\.z^\{\\prime\}\.

To formalize this goal, we introduce a notion of*exact unlearning*for sequential learning problems, which we directly adopt from the batch learning setting developed byUllah and Arora \([2023](https://arxiv.org/html/2606.04182#bib.bib2)\)\. This definition captures the requirement that the output of the unlearning algorithm must be*indistinguishable in distribution*from the output that would have resulted hadzznever been observed\.

###### Definition 2\.1\(Exact Unlearning for Sequential Learning Problems\)\.

An unlearning algorithm𝐔\\mathbf\{U\}is said to achieve*exact unlearning*with respect to a learning algorithm𝐀\\mathbf\{A\}if, for anyT∈ℕT\\in\\mathbb\{N\}, anyt∈\[T\]t\\in\[T\], and any sequencez1,…,zT,z′z\_\{1\},\\ldots,z\_\{T\},z^\{\\prime\}in𝒵\\mathcal\{Z\}, the following holds

𝐔​\(𝐀​\(z1:T\),zt,z′\)​=𝐷​𝐀​\(z1,…,zt−1,z′,zt\+1,…,zT\),\\displaystyle\\mathbf\{U\}\(\\mathbf\{A\}\(z\_\{1:T\}\),z\_\{t\},z^\{\\prime\}\)\\overset\{D\}\{=\}\\mathbf\{A\}\(z\_\{1\},\\ldots,z\_\{t\-1\},z^\{\\prime\},z\_\{t\+1\},\\ldots,z\_\{T\}\),whereX​=𝐷​YX\\\!\\overset\{D\}\{=\}\\\!Ydenotes equality in distribution, meaning that for any eventℰ\\mathcal\{E\},Pr⁡\(X∈ℰ\)=Pr⁡\(Y∈ℰ\)\\Pr\(X\\in\\mathcal\{E\}\)\\\!=\\\!\\Pr\(Y\\in\\mathcal\{E\}\)\.

[2\.1](https://arxiv.org/html/2606.04182#A4.EGx3)formalizes the idea that deleting a user data pointztz\_\{t\}is equivalent to having replaced it with an arbitrary but fixed data pointz′z^\{\\prime\}from the outset\. The requirement that the equivalence must hold for any choice ofz′z^\{\\prime\}ensures that the notion of deletion is meaningful and practically aligned with privacy expectations\. The dummy data pointz′z^\{\\prime\}can be chosen by the algorithm designer and need not correspond to a real user; for instance, it may encode a no\-op or neutral interaction\.

Replacing data rather than removing it outright has a key algorithmic advantage\. It allows the learner to preserve any internal data structures \(e\.g\., prefix sums, counters, or trees\) without disrupting their structure\. This structural preservation is crucial for enabling efficient unlearning in online settings\.

#### Unlearning Request\.

We consider the*anytime*deletion request setting, in which a user may request deletion at any timeTT, without the learner knowingTTin advance\. WhileTTis independent of the learner’s algorithm, it necessitates the design of both anytime learning and unlearning algorithms\.

A trivial unlearning approach is to retrain the model from scratch on the modified sequencez1,…,zt−1,z′,z\_\{1\},\\ldots,z\_\{t\-1\},z^\{\\prime\},zt\+1,…,zTz\_\{t\+1\},\\ldots,z\_\{T\}\. While this satisfies the exact unlearning in[2\.1](https://arxiv.org/html/2606.04182#A4.EGx3), its computational cost is often prohibitive in practice\. In many real\-world applications, e\.g\., large\-scale recommendation systems or continual learning environments, retraining from scratch for each deletion request is simply infeasible\. Our goal is to develop more efficient unlearning methods that are significantly less costly than full retraining\.

To motivate such efficient algorithms, we turn to the concept ofalgorithmic stability, specifically in terms of Total Variation \(TV\) distance, a technique recently leveraged for certified unlearning in the batch setting\(Ullahet al\.,[2021](https://arxiv.org/html/2606.04182#bib.bib10); Ullah and Arora,[2023](https://arxiv.org/html/2606.04182#bib.bib2)\)\. The Total Variation \(TV\) distance between two probability distributionsPPandQQis defined as

TV​\(P,Q\):=supmeasurable event​ℰ\|P​\(ℰ\)−Q​\(ℰ\)\|\.\{\\text\{TV\}\}\(P,Q\):=\\sup\_\{\\text\{measurable event \}\\mathcal\{E\}\}\|P\(\\mathcal\{E\}\)\-Q\(\\mathcal\{E\}\)\|\.
###### Definition 2\.2\(ρ\\rho\-TV\-stable algorithms\)\.

Fix anyρ≥0\\rho\\geq 0\. An online learning algorithm𝐀\\mathbf\{A\}is said to beρ\\rho\-TV\-stable if, for any two user sequencesZZandZ′Z^\{\\prime\}of the same length that differ in exactly one position, we have:TV​\(𝐀​\(Z\),𝐀​\(Z′\)\)≤ρ\{\\text\{TV\}\}\(\\mathbf\{A\}\(Z\),\\mathbf\{A\}\(Z^\{\\prime\}\)\)\\leq\\rho\. Unless noted otherwise, all probabilities are over the algorithm’s internal randomness; events are Borel sets in the output space of \(w1:Tw\_\{1:T\},meta\-data\)\.

0:environment oracle

\{𝔼​𝕆t\}\\\{\{\\mathbb\{E\}\\mathbb\{O\}\}\_\{t\}\\\}and the update functionUPDATEinternal to the algorithm

1:Initialize

w1∈𝒲w\_\{1\}\\in\\mathcal\{W\}and

u0=0u\_\{0\}=0
2:for

t=1,2,…,t=1,2,\\ldots,do

3:A user

ztz\_\{t\}\(oblivious to the algorithm\) arrives

4:Use

w1:tw\_\{1:t\}to interact with user

ztz\_\{t\}via the environment oracle

xt←𝔼​𝕆t​\(zt;w1:t\)x\_\{t\}\\leftarrow\{\\mathbb\{E\}\\mathbb\{O\}\}\_\{t\}\(z\_\{t\};w\_\{1:t\}\)
5:Update the prefix sum

ut←ut−1\+xtu\_\{t\}\\leftarrow u\_\{t\-1\}\+x\_\{t\}
6:Update model via the update function

wt\+1=UPDATE​\(ut;w1:t\)w\_\{t\+1\}=\{\{\\bf\\texttt\{UPDATE\}\}\}\(u\_\{t\};w\_\{1:t\}\)
7:endfor

7:

w0,w1,…w\_\{0\},w\_\{1\},\\ldots

Algorithm 1Online algorithms with prefix sums
#### Maximal Coupling for Efficient Unlearning via TV\-stability\.

LetPP,QQdenote the distributions over the outputs of a learning algorithm run on the original data sequence and the sequence after a deletion request, respectively\. Suppose we have access to a samplex∼Px\\sim P\. The goal of unlearning is to transform this sample into one fromQQ, using an edit functionϕ:dom​\(P\)→dom​\(Q\)\\phi:\\text\{dom\}\(P\)\\rightarrow\\text\{dom\}\(Q\)such thaty:=ϕ​\(x\)∼Qy:=\\phi\(x\)\\sim Q, and such that the computational cost of applyingϕ\\phiis small\.Ullahet al\.\([2021](https://arxiv.org/html/2606.04182#bib.bib10)\)propose a general framework based on*maximal coupling*for constructing such efficient unlearning mechanisms\. A coupling ofPPandQQis a joint distributionψ\\psiwith marginalsPPandQQ\. A*maximal coupling*is a coupling that minimizes the probability of disagreement between the coupled random variables, i\.e\.,Pr\(x,y\)∼ψ⁡1​\{x≠y\}=TV​\(P,Q\)\\Pr\_\{\(x,y\)\\sim\\psi\}1\\\{x\\neq y\\\}=\{\\text\{TV\}\}\(P,Q\)\. This implies that, if the edit functionϕ\\phiinduces a maximal coupling, then with probability at least1−TV​\(P,Q\)1\-\{\\text\{TV\}\}\(P,Q\), the original samplex∼Px\\sim Pcan be reused directly as a valid sample forQQ, avoiding retraining\.

The key algorithmic challenge is twofold: \(1\) design learning algorithms that are both accurate and exhibit smallTV\-stability, and \(2\) construct edit functions that induce or approximate maximal couplings\. These components together enable fast and exact unlearning in the sequential setting\.

## 3\(Un\)Learning for Prefix Sums

In this section, we consider a class of online algorithms in[Section2](https://arxiv.org/html/2606.04182#S2), but with an additional structure ofprefix sums\. This algorithm class captures most of online learning algorithms, including reinforcement learning that we will consider later\. We present a generic template for online algorithms with prefix sums in[Algorithm1](https://arxiv.org/html/2606.04182#alg1)\. A key structure of an algorithm in this class is an internal update functionUPDATEin Line 6\. The internal update takes in the prefix sumutu\_\{t\}of the statistics queried from the previous usersz1:tz\_\{1:t\}and the output of the previous modelsw1:tw\_\{1:t\}to produce a new model outputwt\+1w\_\{t\+1\}\.

### 3\.1TV\-stable Learning with Binary Tree Mechanism

We now present[Algorithm2](https://arxiv.org/html/2606.04182#alg2), a modification of[Algorithm1](https://arxiv.org/html/2606.04182#alg1)that makes the algorithm TV\-stable and supports efficient unlearning in what follows\. The lines 4 and 5 in[Algorithm2](https://arxiv.org/html/2606.04182#alg2)are the only major modifications on top of[Algorithm1](https://arxiv.org/html/2606.04182#alg1)\.

The idea is that we use the standard binary tree mechanism in the differential privacy literature\(Dworket al\.,[2010](https://arxiv.org/html/2606.04182#bib.bib29)\)to add noise to the prefix sums, as has been done in the original exact unlearning framework of\(Ullah and Arora,[2023](https://arxiv.org/html/2606.04182#bib.bib2)\)\(see examples in\(Ullah and Arora,[2023](https://arxiv.org/html/2606.04182#bib.bib2)\)\)\. Intuitively, to perturbTTprefix sums\{ut\}t∈\[T\]\\\{u\_\{t\}\\\}\_\{t\\in\[T\]\}, one need not useTTindependent noise samples for each statisticxtx\_\{t\}\. Instead, we only need to add noises to all the dyadics and reuse these noises for any prefix sum based on its dyadic decomposition\. For example, suppose we want to add noise to the seventh prefix sumu7u\_\{7\}, we use the dyadic decomposition of77as7=4\+2\+17=4\+2\+1, and obtain a perturbed variant ofu7u\_\{7\}by\(x1\+x2\+x3\+x4\+ξ1\)\+\(x5\+x6\+ξ2\)\+\(x7\+ξ3\)\(x\_\{1\}\+x\_\{2\}\+x\_\{3\}\+x\_\{4\}\+\\xi\_\{1\}\)\+\(x\_\{5\}\+x\_\{6\}\+\\xi\_\{2\}\)\+\(x\_\{7\}\+\\xi\_\{3\}\)whereξ1,ξ2,ξ3∼𝒩​\(0,σ2​Id\)\\xi\_\{1\},\\xi\_\{2\},\\xi\_\{3\}\\sim\\mathcal\{N\}\(0,\\sigma^\{2\}I\_\{d\}\)\. Overall, each prefix sum is perturbed by at mostlog⁡T\\log Tnoise samples\. This idea can be realized by considering a perfect binary tree𝒯\\mathcal\{T\}with the following properties\. Each nodebbof the tree is associated with a fixed, independent sample of Gaussian noiseξb∼𝒩​\(0,σ2​Id\)\\xi\_\{b\}\\sim\\mathcal\{N\}\(0,\\sigma^\{2\}I\_\{d\}\)\. We store in each nodebbtwo fields: clean valuevb∈ℝdv\_\{b\}\\in\\mathbb\{R\}^\{d\}and noisy valuev~b∈ℝd\\tilde\{v\}\_\{b\}\\in\\mathbb\{R\}^\{d\}, wherev~b=vb\+ξb\\tilde\{v\}\_\{b\}=v\_\{b\}\+\\xi\_\{b\}\. A leaf nodettadditionally stores modelwtw\_\{t\}\. The clean value of a leaf nodettis zero if in initialization, orxtx\_\{t\}, if the leaf node gets an update fromxt←𝔼​𝕆t​\(zt;w1:t\)x\_\{t\}\\leftarrow\{\\mathbb\{E\}\\mathbb\{O\}\}\_\{t\}\(z\_\{t\};w\_\{1:t\}\)\. For a non\-leaf node, its clean value is the sum of the clean values of its children\. The tree supports the following operations:

- •TreeUpdate​\(x;t,𝒯\)\\texttt\{TreeUpdate\}\(x;t,\\mathcal\{T\}\): If leafttdoes not exist, create leavest,t\+1,…,2⌈log2⁡t⌉t,t\+1,\\ldots,2^\{\\lceil\\log\_\{2\}t\\rceil\}\. Iterate over each node through the path from leafttto root, and update its clean value by adding the new value and subtracting the old value of leaftt\. Consequently, the new clean value of leafttisxxand the value of any other leaves int\+1,…,2⌈log2⁡t⌉t\+1,\\ldots,2^\{\\lceil\\log\_\{2\}t\\rceil\}is zero\.
- •GetNoisyPrefixSum​\(t,𝒯\)\{\\bf\\texttt\{GetNoisyPrefixSum\}\}\(t,\\mathcal\{T\}\): Retrieve the noisy version of the prefix sum∑i=1txi\\sum\_\{i=1\}^\{t\}\{x\}\_\{i\}from the tree\. To do this, writet=b1​…​bKt=b\_\{1\}\\ldots b\_\{K\}asKK\-bit representation, whereKKis the depth of the tree\. Initializeu=0u=0\. Iterate through the path from the root to leaftt\(i\.e\., fork=1,…,Kk=1,\\ldots,K\)\. Ifbk=0b\_\{k\}=0, skip tok\+1k\+1\. Ifbk=1b\_\{k\}=1and the current node is a left child of a node, add touuthe current node’s noisy value\. Ifbk=1b\_\{k\}=1and the current node is a right child of a node, add touuthe current node’s left sibling’s noisy value\.

### 3\.2Unlearning by Maximally Coupling a Binary Tree

We now present an unlearning framework in[Algorithm3](https://arxiv.org/html/2606.04182#alg3)for[Algorithm2](https://arxiv.org/html/2606.04182#alg2)\. The idea largely follows from the original unlearning framework of\(Ullah and Arora,[2023](https://arxiv.org/html/2606.04182#bib.bib2)\), by maximally coupling the binary tree returned by[Algorithm2](https://arxiv.org/html/2606.04182#alg2)\. In fact, we can view the unlearning framework here as a simplified version of the unlearning framework of\(Ullah and Arora,[2023](https://arxiv.org/html/2606.04182#bib.bib2)\), whereas due to the sequential nature of our

0:binary tree

𝒯\\mathcal\{T\}, initial episode

t0t\_\{0\}, last episode

TT, noise variance

σ\\sigma\.

1:If the binary tree has more than

2⌈log2⁡t0⌉\+12^\{\\lceil\{\\log\_\{2\}t\_\{0\}\}\\rceil\}\+1leaves, truncate it so that the tree has only

2⌈log2⁡t0⌉2^\{\\lceil\{\\log\_\{2\}t\_\{0\}\}\\rceil\}leaves\. If the leaves

t0,t0\+1,…t\_\{0\},t\_\{0\}\+1,\\ldotsexist in the tree

𝒯\\mathcal\{T\}, then iterate over all the leaves from

t0t\_\{0\}onward, set the value of each of the leaves to zeros, and update all the non\-leaf nodes

2:for

t=t0,…,Tt=t\_\{0\},\\ldots,Tdo

3:

xt←𝔼​𝕆t​\(zt;w1:t\)x\_\{t\}\\leftarrow\{\\mathbb\{E\}\\mathbb\{O\}\}\_\{t\}\(z\_\{t\};w\_\{1:t\}\)
4:

TreeUpdate​\(xt,t;𝒯\)\\texttt\{TreeUpdate\}\(x\_\{t\},t;\\mathcal\{T\}\)
5:

u~t←GetNoisyPrefixSum​\(t,𝒯\)\\tilde\{u\}\_\{t\}\\leftarrow\\texttt\{GetNoisyPrefixSum\}\(t,\\mathcal\{T\}\)
6:

wt\+1←UPDATE​\(w1:t,u~t\)w\_\{t\+1\}\\leftarrow\{\{\\bf\\texttt\{UPDATE\}\}\}\(w\_\{1:t\},\\tilde\{u\}\_\{t\}\)
7:Save

wtw\_\{t\}to leaf

tt
8:endfor

8:

𝒯\\mathcal\{T\}

Algorithm 2TV\-stable\-Learn\(t0,Tt\_\{0\},T\)0:a binary tree

𝒯\\mathcal\{T\}, the position

ttto be unlearned, a dummy user

z′z^\{\\prime\}
1:Retrieve

xtx\_\{t\}from leaf

tt
2:Engage the environment oracle at time step

tt:

xt′=𝔼​𝕆t​\(z′;w1:t\)x^\{\\prime\}\_\{t\}=\{\\mathbb\{E\}\\mathbb\{O\}\}\_\{t\}\(z^\{\\prime\};w\_\{1:t\}\)
3:Set

b=tb=t
4:while

b≠∅b\\neq\\emptysetdo

5:Retrieve

\(vb,v~b\)\(v\_\{b\},\\tilde\{v\}\_\{b\}\)from

bband compute

vb′←vb−xt\+xt′v^\{\\prime\}\_\{b\}\\leftarrow v\_\{b\}\-x\_\{t\}\+x^\{\\prime\}\_\{t\}
6:if

Unif​\(0,1\)≤f𝒩​\(vb′,σ2​I\)​\(v~b\)f𝒩​\(vb,σ2​I\)​\(v~b\)\\texttt\{Unif\}\(0,1\)\\leq\\frac\{f\_\{\\mathcal\{N\}\(v^\{\\prime\}\_\{b\},\\sigma^\{2\}I\)\}\(\\tilde\{v\}\_\{b\}\)\}\{f\_\{\\mathcal\{N\}\(v\_\{b\},\\sigma^\{2\}I\)\}\(\\tilde\{v\}\_\{b\}\)\}then

7:

vb←vb′v\_\{b\}\\leftarrow v^\{\\prime\}\_\{b\}
8:else

9:

v~b′←vb′\+vb−v~b\\tilde\{v\}^\{\\prime\}\_\{b\}\\leftarrow v^\{\\prime\}\_\{b\}\+v\_\{b\}\-\\tilde\{v\}\_\{b\}
10:

\(vb,v~b\)←\(vb′,v~b′\)\(v\_\{b\},\\tilde\{v\}\_\{b\}\)\\leftarrow\(v^\{\\prime\}\_\{b\},\\tilde\{v\}^\{\\prime\}\_\{b\}\)
11:Call

TV\-stable\-Learn​\(t′,T\)\\texttt\{TV\-stable\-Learn\}\(t^\{\\prime\},T\)\([Algorithm2](https://arxiv.org/html/2606.04182#alg2)\), where

t′t^\{\\prime\}is the leaf that is right after node

bbin the post\-traversal order\.

12:break

13:endif

14:Set

bbas the parent of

bb
15:endwhile

15:

𝒯\\mathcal\{T\}

Algorithm 3Unlearn\(𝒯,t\)\(\\mathcal\{T\},t\)problems, we do not have to deal with permuting the dataset, thus significantly simplifying the algorithm and analysis\.

In particular, upon the deletion request for user dataztz\_\{t\}, we query the environment oracle for adummyuserz′z^\{\\prime\}, an arbitrary user data that has no correlation with the deleted user data\. We then iterate through the path from leafttto the root\. For each nodebbon the path, we update its clean value fromvbv\_\{b\}tovb′v^\{\\prime\}\_\{b\}, to account for the fact thatxtx\_\{t\}is replaced byxt′x^\{\\prime\}\_\{t\}\. The involved part is how to update the noisy valuev~b\\tilde\{v\}\_\{b\}, as all the nodes that followbbdepend on the noisy valuev~b\\tilde\{v\}\_\{b\}, not the clean valuevbv\_\{b\}\. Ideally, we want to re\-use the old value ofv~b\\tilde\{v\}\_\{b\}so that all its dependent nodes do not need to update\. This is precisely the problem of designing a maximal coupling\. This amounts to the rejection sampling step \(Line 6\-7\) that checks if the old value ofv~b\\tilde\{v\}\_\{b\}can be seen as a sample from𝒩​\(vb′,σ2​I\)\\mathcal\{N\}\(v^\{\\prime\}\_\{b\},\\sigma^\{2\}I\)\. In particular, we compute the density ratio of the two Gaussians at the old value ofv~b\\tilde\{v\}\_\{b\}, i\.e\.,f𝒩​\(vb′,σ2​I\)​\(v~b\)f𝒩​\(vb,σ2​I\)​\(v~b\)\\frac\{f\_\{\\mathcal\{N\}\(v^\{\\prime\}\_\{b\},\\sigma^\{2\}I\)\}\(\\tilde\{v\}\_\{b\}\)\}\{f\_\{\\mathcal\{N\}\(v\_\{b\},\\sigma^\{2\}I\)\}\(\\tilde\{v\}\_\{b\}\)\}and compare it against a random sample from a uniform distributionUnif​\(0,1\)\\text\{Unif\}\(0,1\)\. If it results in accept, move to the parent node of the current node and repeat\. If it results in reject, reflect the sample \(Line 9\) \(ensuring the new noisy valuev~b\\tilde\{v\}\_\{b\}has correct distribution𝒩​\(vb′,σ2​I\)\\mathcal\{N\}\(v^\{\\prime\}\_\{b\},\\sigma^\{2\}I\)by reflecting around the new mean\) and retrain from scratch from the next leaf in the post\-traversal order in the tree \(Line 11\)\.

The key result in this section is the guarantee of exact unlearning and its relative computational complexity, as long as the environment oracle has a finiteℓ2\\ell\_\{2\}sensitivity\. In particular, we assume the sensitivity of the environment oracle, imposing that changing a user data does not change the output of the environment oracle by too much\.

###### Assumption 3\.2\(ℓ2\\ell\_\{2\}sensitivity\)\.

There exists a constantB\>0B\>0such that

supt,z,z′,w1:t‖𝔼​𝕆t​\(z;w1:t\)−𝔼​𝕆t​\(z′;w1:t\)‖2≤B\.\\displaystyle\\sup\_\{t,z,z^\{\\prime\},w\_\{1:t\}\}\\\|\{\\mathbb\{E\}\\mathbb\{O\}\}\_\{t\}\(z;w\_\{1:t\}\)\-\{\\mathbb\{E\}\\mathbb\{O\}\}\_\{t\}\(z^\{\\prime\};w\_\{1:t\}\)\\\|\_\{2\}\\leq B\.

The nature of the following theorem is similar to\(Ullah and Arora,[2023](https://arxiv.org/html/2606.04182#bib.bib2), Theorem 1\), except that we focus on sequential problems rather than batch problems\. Our proof is also significantly simplified, as, again, we do not have to deal with permuting the dataset \(see[AppendixB](https://arxiv.org/html/2606.04182#A2)\)\.

###### Theorem 3\.3\.

Fix anyρ\>0\\rho\>0\. Setσ=B​log2⁡T2​ρ\\sigma=\\frac\{B\\sqrt\{\\log\_\{2\}T\}\}\{\\sqrt\{2\}\\rho\}, whereBBis the bound on sensitivity \([3\.2](https://arxiv.org/html/2606.04182#A4.EGx4)\)\. Then,

1. 1\.[Algorithm3](https://arxiv.org/html/2606.04182#alg3)is exact unlearning w\.r\.t\.[Algorithm2](https://arxiv.org/html/2606.04182#alg2),
2. 2\.[Algorithm2](https://arxiv.org/html/2606.04182#alg2)isρ\\rho\-TV\-stable,
3. 3\.The probability of retraining in unlearning isρ​2​log2⁡T\\rho\\sqrt\{2\\log\_\{2\}T\}\.

Proof Sketch \(Theorem 1\)\. The learning phase replaces raw prefix sums with correlated Gaussian noise via a binary\-tree mechanism so that each query uses only𝒪​\(log⁡T\)\\mathcal\{O\}\(\\log T\)shared noises\. In unlearning, we traverse the path from the deleted leaf to the root and maximally couple the old and new Gaussian nodes: for nodebb, we first “clean\-update” its meanvb↦vb′v\_\{b\}\\mapsto v\_\{b^\{\\prime\}\}, then perform a rejection test that reusesv~b\\tilde\{v\}\_\{b\}whenever possible; on a failure we apply the reflection mapv~b′:=vb′\+vb−v~b\\tilde\{v\}\_\{b^\{\\prime\}\}:=v\_\{b^\{\\prime\}\}\+v\_\{b\}\-\\tilde\{v\}\_\{b\}\(a Gaussian\-to\-Gaussian maximal coupling\), and retrain only from the next post\-order leaf\. This yields exact unlearning by construction and confines retraining to rare coupling failures along𝒪​\(log⁡T\)\\mathcal\{O\}\(\\log T\)nodes\.

Our unlearning[Algorithm3](https://arxiv.org/html/2606.04182#alg3)is a simplified instance of the batch tree\-coupling framework in\(Ullah and Arora,[2023](https://arxiv.org/html/2606.04182#bib.bib2)\): the sequential nature eliminates dataset permutation and reduces the coupling path to at mostlog⁡T\\log Tnodes per request, improving both exposition and constants\. We now move on to applying the above unlearning framework to RL\.

## 4Reinforcement \(Un\)Learning

Designing an unlearning framework for reinforcement learning based on the general approach from[Section3](https://arxiv.org/html/2606.04182#S3)requires instantiating the environment oracle𝔼​𝕆t\{\\mathbb\{E\}\\mathbb\{O\}\}\_\{t\}and defining the internal update functionUPDATEfor MDPs\. After such instantiation, all the unlearning guarantees in[Theorem3\.3](https://arxiv.org/html/2606.04182#S3.Thmtheorem3)remain for RL, with a specific value ofBBwe discuss shortly\. The key challenge here is, however, to designUPDATEfor RL such that the RL algorithm has regret\-optimal learning, despite being disturbed by injected noises for unlearning guarantees\. In this section, we designUPDATE, built upon the famous UCB\-VI\(Azaret al\.,[2017](https://arxiv.org/html/2606.04182#bib.bib26)\), that attains nearly minimax\-optimal regret\-stability trade\-offs\.

#### Realizing the Environment Oracle𝔼​𝕆t\{\\mathbb\{E\}\\mathbb\{O\}\}\_\{t\}and the Summary Statisticsxtx\_\{t\}for MDPs\.

During episodett, the RL algorithm interacts with userztz\_\{t\}, generating an experience sequence\(s1t,a1t,r1t,…,sHt,aHt,rHt\)\(s\_\{1\}^\{t\},a\_\{1\}^\{t\},r\_\{1\}^\{t\},\\ldots,s\_\{H\}^\{t\},a^\{t\}\_\{H\},r^\{t\}\_\{H\}\)\. The environment oracle𝔼​𝕆t\{\\mathbb\{E\}\\mathbb\{O\}\}\_\{t\}then returns summary statisticsxtx\_\{t\}that encode this trajectory\. In the MDP case, the summary statisticsxtx\_\{t\}is defined as

xt=\{xt​\[h,s,a\]\}\(h,s,a\)∈\[H\]×𝒮×𝒜,where\\displaystyle x\_\{t\}=\\\{x\_\{t\}\[h,s,a\]\\\}\_\{\(h,s,a\)\\\!\\in\\\!\[H\]\\\!\\times\\\!\\mathcal\{S\}\\\!\\times\\\!\\mathcal\{A\}\},\\text\{ where\}\(1\)
xt​\[h,s,a\]=\(1\{\(sht,aht\)=\(s,a\)\},1\{\(sht,aht,sh\+1t\)=\(s,a,s′\)\},rht⋅1\{\(sht,aht\)=\(s,a\)\}\)x\_\{t\}\[h,s,a\]=\(1\_\{\\\{\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)=\(s,a\)\\\}\},1\_\{\\\{\(s^\{t\}\_\{h\},a^\{t\}\_\{h\},s^\{t\}\_\{h\+1\}\)=\(s,a,s^\{\\prime\}\)\\\}\},r^\{t\}\_\{h\}\\cdot 1\_\{\\\{\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)=\(s,a\)\\\}\}\)\. The dimension of the output from the environment oracle isd=2​S​A​H\+S2​A​Hd=2SAH\+S^\{2\}AH, corresponding to indicators for state\-action occurrences, transitions, and associated rewards across the horizon\.

#### Sensitivity ParameterBBfor MDPs\.

Importantly, the sensitivity parameter of the environment oracle is bounded asB≤3​HB\\leq\\sqrt\{3H\}\. This follows from the observation that, in any episodett, the generated statisticxtx\_\{t\}contains at most3​H3Hnon\-zero components, one per time step for each of the indicator, transition, and reward terms, independent of the sizes of the state or action spaces\. is section is to design the internal update function for RL, grounded in the statistics constructed above\. Our proposed update function is presented in[Algorithm4](https://arxiv.org/html/2606.04182#alg4)\.

Similar to the standard \(non\-stable\) RL algorithm ofAzaret al\.\([2017](https://arxiv.org/html/2606.04182#bib.bib26)\),[Algorithm4](https://arxiv.org/html/2606.04182#alg4)follows the principle of optimistic value iteration, with adjustments to ensure stability through noise\-perturbed statistics and confidence bonuses\. In particular, letNht​\(s,a\)N^\{t\}\_\{h\}\(s,a\)andNht​\(s,a,s′\)N^\{t\}\_\{h\}\(s,a,s^\{\\prime\}\)denote the number of visits to the tuples\(h,s,a\)\(h,s,a\)and\(h,s,a,s′\)\(h,s,a,s^\{\\prime\}\), respectively, prior to episodett\. LetRht​\(s,a\)R^\{t\}\_\{h\}\(s,a\)be the total reward accumulated at\(h,s,a\)\(h,s,a\)up to that point\. Their noisy counterparts, denoted byN~ht​\(s,a\),N~ht​\(s,a,s′\),R~ht​\(s,a\)\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\),\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a,s^\{\\prime\}\),\{\\widetilde\{R\}\}^\{t\}\_\{h\}\(s,a\), are computed using the binary tree mechanism described in[Algorithm2](https://arxiv.org/html/2606.04182#alg2)\. For use in[Algorithm4](https://arxiv.org/html/2606.04182#alg4), we define the following quantities:

ϵapp​\(δ\)\\displaystyle\\epsilon\_\{\\text\{app\}\}\(\{\\delta\}\):=σ​ln⁡T​\(1\+2​log⁡\(2​T​\(S2​A​H\+2​S​A​H\)/δ\)\),\\displaystyle:=\\sigma\\ln T\\left\(1\\\!\+\\\!\\sqrt\{2\\log\(2T\(S^\{2\}AH\\\!\+\\\!2SAH\)/\\delta\)\}\\right\),r~ht​\(s,a\)\\displaystyle\{\\tilde\{r\}\}^\{t\}\_\{h\}\(s,a\):=R~h​\(s,a\)N~ht​\(s,a\),ℙ~ht​\(s′\|s,a\):=N~ht​\(s,a,s′\)N~ht​\(s,a\)\\displaystyle:=\\frac\{\{\\widetilde\{R\}\}\_\{h\}\(s,a\)\}\{\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)\},\{\\widetilde\{\\mathbb\{P\}\}\}\_\{h\}^\{t\}\(s^\{\\prime\}\|s,a\):=\\frac\{\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a,s^\{\\prime\}\)\}\{\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)\}b​\(n~\)\\displaystyle b\(\\tilde\{n\}\):=\(H\+1\)​ln⁡\(8​S​A​H​T/δ\)2​\(n~−ϵapp​\(δ4\)\)\+ϵapp​\(δ4\)n~​\(1\+2​H​\(S\+1\)\),\\displaystyle:=\(H\\\!\+\\\!1\)\\sqrt\{\\frac\{\\ln\(8SAHT/\\delta\)\}\{2\(\\tilde\{n\}\-\\epsilon\_\{\\text\{app\}\}\(\{\\frac\{\\delta\}\{4\}\}\)\)\}\}\\\!\\\!\+\\\!\\\!\\frac\{\\epsilon\_\{\\text\{app\}\}\(\{\\frac\{\\delta\}\{4\}\}\)\}\{\\tilde\{n\}\}\(1\\\!\\\!\+\\\!\\\!2H\(\\sqrt\{S\}\\\!\+\\\!1\)\),
where the first term in the bonus functionb​\(n~\)b\(\\tilde\{n\}\)is a Hoeffding\-style exploration bonus; the second term compensates for approximation error from noisy counts\. During episodett, the algorithm performs value iteration using the stable estimators\{r~ht\},\{ℙ~ht\}\\\{\{\\tilde\{r\}\}^\{t\}\_\{h\}\\\},\\\{\{\\widetilde\{\\mathbb\{P\}\}\}^\{t\}\_\{h\}\\\}and the bonus functionb​\(⋅\)b\(\\cdot\), to compute a stable approximationQ~t\{\\widetilde\{Q\}\}^\{t\}of the Q\-function\. Intuitively, the first term of the bonus function accounts for the estimation error due to finite samples, while the second term compensates for the approximation error introduced by noisy \(i\.e\., stabilized\) counts\. The algorithm then outputs greedy policyπ~t\{\\widetilde\{\\pi\}\}^\{t\}, which is used to generate action recommendationsa1:Hta^\{t\}\_\{1:H\}during episodett\.

0:

u~t=\{\(N~ht​\(s,a\),N~ht​\(s,a,s′\),R~ht​\(s,a\)\):\(h,s,a\)∈\[H\]×𝒮×𝒜\}\\tilde\{u\}\_\{t\}=\\\{\(\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\),\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a,s^\{\\prime\}\),\{\\widetilde\{R\}\}^\{t\}\_\{h\}\(s,a\)\):\(h,s,a\)\\in\[H\]\\times\\mathcal\{S\}\\times\\mathcal\{A\}\\\}, bonus function

b:ℝ→ℝb:\\mathbb\{R\}\\rightarrow\\mathbb\{R\}, and approximation error

ϵapp​\(δ4\)\\epsilon\_\{\\text\{app\}\}\(\{\\frac\{\\delta\}\{4\}\}\)\.

1:Initialize

QH\+1t​\(s,a\)=HQ^\{t\}\_\{H\+1\}\(s,a\)=H
2:for

h=H,…,1h=H,\\ldots,1do

3:if

N~ht​\(s,a\)≥2​ϵapp​\(δ4\)\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)\\geq 2\\epsilon\_\{\\text\{app\}\}\(\{\\frac\{\\delta\}\{4\}\}\)then

4:

Q~ht\(s,a\)=\(r~ht\(s,a\)\+\(ℙ~htV~h\+1t\)\(s,a\)\+b\(N~ht\(s,a\)\)\{\\widetilde\{Q\}\}^\{t\}\_\{h\}\(s,a\)=\(\{\\tilde\{r\}\}^\{t\}\_\{h\}\(s,a\)\+\(\{\\widetilde\{\\mathbb\{P\}\}\}\_\{h\}^\{t\}\{\\widetilde\{V\}\}\_\{h\+1\}^\{t\}\)\(s,a\)\+b\(\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)\)
5:

Q~ht​\(s,a\)=min⁡\{H,Q~ht​\(s,a\)\}\{\\widetilde\{Q\}\}^\{t\}\_\{h\}\(s,a\)=\\min\\\{H,\{\\widetilde\{Q\}\}^\{t\}\_\{h\}\(s,a\)\\\}
6:else

7:

Q~ht​\(s,a\)=H\{\\widetilde\{Q\}\}^\{t\}\_\{h\}\(s,a\)=H
8:endif

9:

∀\(t,h\)\\forall\(t,h\),

V~ht​\(s\)=maxa∈𝒜⁡Q~ht​\(s,a\)\{\\widetilde\{V\}\}\_\{h\}^\{t\}\(s\)=\\max\_\{a\\in\\mathcal\{A\}\}\{\\widetilde\{Q\}\}^\{t\}\_\{h\}\(s,a\)and

π~ht​\(s\)=arg​maxa∈𝒜⁡Q~ht​\(s,a\)\{\\widetilde\{\\pi\}\}^\{t\}\_\{h\}\(s\)=\{\\text\{arg\}\\max\}\_\{a\\in\\mathcal\{A\}\}\{\\widetilde\{Q\}\}^\{t\}\_\{h\}\(s,a\)
10:endfor

10:

π~t\{\\widetilde\{\\pi\}\}^\{t\}

Algorithm 4UPDATE​\(w1:t,u~t\)\{\{\\bf\\texttt\{UPDATE\}\}\}\(w\_\{1:t\},\\tilde\{u\}\_\{t\}\)The main result of this section is the following regret bound for[Algorithm4](https://arxiv.org/html/2606.04182#alg4)\.

###### Theorem 4\.1\.

Fix anyρ\>0\\rho\>0and setσ=B​log2⁡T2​ρ\\sigma=\\frac\{B\\sqrt\{\\log\_\{2\}T\}\}\{\\sqrt\{2\}\\rho\}\. In[Algorithm2](https://arxiv.org/html/2606.04182#alg2), instantiate the environment oracle𝔼​𝕆t\{\\mathbb\{E\}\\mathbb\{O\}\}\_\{t\}\(Line 3 of[Algorithm2](https://arxiv.org/html/2606.04182#alg2)\) using[Equation1](https://arxiv.org/html/2606.04182#S4.E1), and the algorithm oracleUPDATE\(Line 6 of[Algorithm2](https://arxiv.org/html/2606.04182#alg2)\) using[Algorithm4](https://arxiv.org/html/2606.04182#alg4)\. Then, the resulting reinforcement learning algorithm isρ\\rho\-TV\-stable\. Furthermore, for anyδ∈\(0,1\)\\delta\\in\(0,1\), with probability at least1−δ1\-\\delta, the regret of the algorithm satisfies:R​\(T\)≤R\(T\)\\leq

\(H3​S2​A\+H2​S​A​T\+H2\.5​S2​A/ρ\)⋅polylog​\(T,H,S,A,1/δ\)\.\(H^\{3\}S^\{2\}A\+H^\{2\}\\sqrt\{SAT\}\+H^\{2\.5\}S^\{2\}A/\\rho\)\\cdot\\text\{polylog\}\(T,H,S,A,1/\\delta\)\.

The regret bound comprises three terms: the first term captures the burn\-in cost incurred before sublinear regret behavior emerges; the second term corresponds to the standard regret bound of the UCB\-VI algorithm\(Azaret al\.,[2017](https://arxiv.org/html/2606.04182#bib.bib26)\), using a Hoeffding\-type bonus rather than a Bernstein\-type bonus; and the third term accounts for the additional cost of stabilizing the RL algorithm with Gaussian noise injection\. The complete proof is given in[AppendixC](https://arxiv.org/html/2606.04182#A3)\.

### 4\.1Minimax Lower Bounds

Next, we establish a minimax lower bound on the regret of anyρ\\rho\-TV\-stable RL algorithm\. The detailed proof is given in[AppendixD](https://arxiv.org/html/2606.04182#A4)\.

###### Theorem 4\.4\.

For anyρ\\rho\-TV\-stable RL algorithm, the following lower bound on regret holds:

R​\(T\)=Ω​\(H​S​A​T\+H​S​A/ρ\)\.\\displaystyle R\(T\)=\\Omega\\left\(H\\sqrt\{SAT\}\+HSA/\\rho\\right\)\.

This lower bound indicates that our upper bound is tight, up to a factor ofHHin the first term andH1\.5​SH^\{1\.5\}Sin the second\. The gap in the first term is reducible via sharper analysis, for example by using Bernstein\-type bonus functions in place of Hoeffding\-type bonuses, as used in our current design\.

#### On the MDP Class\.

Compared to the hard instances constructed by\(Vietriet al\.,[2020](https://arxiv.org/html/2606.04182#bib.bib41)\), we use separate absorbing states per initial state; otherwise, an RL algorithm can learn that the shared “\+” absorber dominates and bias actions for unseen initials, breaking the intended reduction toSSindependent MABs and invalidating the lower bound\. See[LemmaD\.4](https://arxiv.org/html/2606.04182#A4.Thmtheorem4)/[CorollaryD\.3](https://arxiv.org/html/2606.04182#A4.Thmtheorem3)for the S decoupled MAB simulation and theH​S​A/ρHSA/\\rhoterm in our bound\.

## 5Conclusion and Discussion

We presented the first theoretical and algorithmic framework for*provably exact unlearning*in RL, specifically within tabular Markov decision processes\. Our framework leverages Total Variation \(TV\) stability to design sample\-efficient, TV\-stable RL algorithms that enable efficient unlearning\. We established regret bounds that are nearly minimax\-optimal for the class of TV\-stable RL algorithms\.

We emphasize that TV\-stability is not necessary for unlearning in all frameworks\. Algorithms lacking TV\-stability may still permit alternative unlearning strategies, for example, through structural or compositional properties that enable bespoke procedures\. Our theory thus characterizes a natural and rich subclass of unlearnable algorithms rather than all possible approaches\. As the first results in RL to provide end\-to\-end guarantees combining regret\-optimal learning with provable unlearning, we view this as a compelling foundational step forward\.

Several important gaps remain in our understanding of exact unlearning for regret minimization and sequential learning more broadly\. First, there is still a nontrivial gap between our upper and lower bounds on regret forρ\\rho\-TV\-stable RL algorithms\. While the first term in the upper bound could potentially be tightened using sharper analysis \(e\.g\., Bernstein\-type bonuses in place of Hoeffding\-type\), it is unclear how to close the gap ofH1\.5​SH^\{1\.5\}Sin the second term\.

Second, our results are confined to the tabular setting\. Achieving exact unlearning when the state space is large or continuous, necessitating function approximation, remains an open question, presenting both statistical and algorithmic challenges\. The key insight behind our approach is maintaining sufficient statistics that support both learning and unlearning\. In tabular MDPs, these take the form of visitation counts\. In RL with function approximation \(e\.g\., linear MDPs\), one could maintain alternative sufficient statistics such as empirical covariance matrices or feature\-based summaries\. While we lack results in the general setting, this direction appears promising and may enable unlearning in more expressive models\. Developing online\-compatible, memory\-efficient unlearning under function approximation remains an important direction for future work\.

Third, exact unlearning, both in our work and in prior work\(Ullahet al\.,[2021](https://arxiv.org/html/2606.04182#bib.bib10); Ullah and Arora,[2023](https://arxiv.org/html/2606.04182#bib.bib2)\), relies on data structures such as binary trees, which incur space complexity linear in the number of episodesTT\. While it is reasonable to expect that exact unlearning requires greater space than approximate unlearning, our understanding of the optimal space\-time\-utility tradeoffs in this regime remains limited\. A fundamental question is whether it is possible to achieve exact unlearning with strong utility guarantees using only*sublinear*space complexity\.

Fourth, while TV stability provides a natural and powerful mechanism for designing efficient exact unlearning algorithms, it remains an open question whether alternative mechanisms could yield improved trade\-offs between utility, computational cost, and space complexity\.

We hope our work lays the groundwork for addressing these open questions and inspires further research on the foundations of unlearning in sequential and interactive learning systems\.

## Acknowledgements

This work was supported in part by NSF CAREER award IIS\-1943251\.

## Impact Statement

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\.

## References

- Y\. Allouah, J\. Kazdan, R\. Guerraoui, and S\. Koyejo \(2024\)The utility and complexity of in\-and out\-of\-distribution machine unlearning\.arXiv preprint arXiv:2412\.09119\.Cited by:[§1](https://arxiv.org/html/2606.04182#S1.p3.1)\.
- P\. Auer, N\. Cesa\-Bianchi, Y\. Freund, and R\. E\. Schapire \(1995\)Gambling in a rigged casino: the adversarial multi\-armed bandit problem\.InProceedings of IEEE 36th annual foundations of computer science,pp\. 322–331\.Cited by:[Remark 2\.2](https://arxiv.org/html/2606.04182#S2.Thmtheorem2.p1.1)\.
- P\. Auer, T\. Jaksch, and R\. Ortner \(2008\)Near\-optimal regret bounds for reinforcement learning\.Advances in neural information processing systems21\.Cited by:[Appendix D](https://arxiv.org/html/2606.04182#A4.13.p1.13)\.
- M\. G\. Azar, I\. Osband, and R\. Munos \(2017\)Minimax regret bounds for reinforcement learning\.InInternational conference on machine learning,pp\. 263–272\.Cited by:[§1](https://arxiv.org/html/2606.04182#S1.SS0.SSS0.Px2.p2.1),[§4](https://arxiv.org/html/2606.04182#S4.SS0.SSS0.Px2.p2.8),[§4](https://arxiv.org/html/2606.04182#S4.SS0.SSS0.Px2.p6.1),[§4](https://arxiv.org/html/2606.04182#S4.p1.5)\.
- R\. Bonta \(2022\)California consumer privacy act \(CCPA\)\.Retrieved from State of California Department of Justice: https://oag\. ca\. gov/privacy/ccpa\.Cited by:[§1](https://arxiv.org/html/2606.04182#S1.p2.1)\.
- L\. Bourtoule, V\. Chandrasekaran, C\. A\. Choquette\-Choo, H\. Jia, A\. Travers, B\. Zhang, D\. Lie, and N\. Papernot \(2021\)Machine unlearning\.In2021 IEEE symposium on security and privacy \(SP\),pp\. 141–159\.Cited by:[§1](https://arxiv.org/html/2606.04182#S1.p1.1)\.
- Y\. Cao and J\. Yang \(2015\)Towards making systems forget with machine unlearning\.In2015 IEEE symposium on security and privacy,pp\. 463–480\.Cited by:[§1](https://arxiv.org/html/2606.04182#S1.SS0.SSS0.Px3.p1.1),[§1](https://arxiv.org/html/2606.04182#S1.p1.1)\.
- S\. R\. Chowdhury and X\. Zhou \(2022\)Differentially private regret minimization in episodic markov decision processes\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.36,pp\. 6375–6383\.Cited by:[§1](https://arxiv.org/html/2606.04182#S1.SS0.SSS0.Px3.p4.1),[§2](https://arxiv.org/html/2606.04182#S2.SS0.SSS0.Px2.p1.13)\.
- CPPA \(2023\)Consumer Privacy Protection Act \(CPPA\)\.Note:[https://ised\-isde\.canada\.ca/site/innovation\-better\-canada/en/consumer\-privacy\-protection\-act](https://ised-isde.canada.ca/site/innovation-better-canada/en/consumer-privacy-protection-act)Cited by:[§1](https://arxiv.org/html/2606.04182#S1.p2.1)\.
- C\. Dwork, F\. McSherry, K\. Nissim, and A\. Smith \(2006\)Calibrating noise to sensitivity in private data analysis\.InTheory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4\-7, 2006\. Proceedings 3,pp\. 265–284\.Cited by:[Definition A\.1](https://arxiv.org/html/2606.04182#A1.Thmdefn1)\.
- C\. Dwork, M\. Naor, T\. Pitassi, and G\. N\. Rothblum \(2010\)Differential privacy under continual observation\.InProceedings of the forty\-second ACM symposium on Theory of computing,pp\. 715–724\.Cited by:[Remark 2\.2](https://arxiv.org/html/2606.04182#S2.Thmtheorem2.p1.1),[§3\.1](https://arxiv.org/html/2606.04182#S3.SS1.p2.23)\.
- R\. Eldan and M\. Russinovich \(2023\)Who’s harry potter? approximate unlearning in llms\.arXiv preprint arXiv:2310\.02238\.Cited by:[§1](https://arxiv.org/html/2606.04182#S1.p2.1)\.
- M\. Fredrikson, S\. Jha, and T\. Ristenpart \(2015\)Model inversion attacks that exploit confidence information and basic countermeasures\.InProceedings of the 22nd ACM SIGSAC conference on computer and communications security,pp\. 1322–1333\.Cited by:[§1](https://arxiv.org/html/2606.04182#S1.p1.1)\.
- GDPR \(2018\)General Data Protection Regulation \(GDPR\)\.Note:[https://gdpr\-info\.eu/](https://gdpr-info.eu/)Cited by:[§1](https://arxiv.org/html/2606.04182#S1.p2.1)\.
- A\. Ginart, M\. Guan, G\. Valiant, and J\. Y\. Zou \(2019\)Making ai forget you: data deletion in machine learning\.Advances in neural information processing systems32\.Cited by:[§1](https://arxiv.org/html/2606.04182#S1.SS0.SSS0.Px3.p1.1),[§1](https://arxiv.org/html/2606.04182#S1.p2.1)\.
- C\. Guo, T\. Goldstein, A\. Hannun, and L\. Van Der Maaten \(2019\)Certified data removal from machine learning models\.arXiv preprint arXiv:1911\.03030\.Cited by:[§1](https://arxiv.org/html/2606.04182#S1.SS0.SSS0.Px3.p1.1),[§1](https://arxiv.org/html/2606.04182#S1.p3.1)\.
- Y\. Hu, B\. Schölkopf, and A\. Sanyal \(2025\)Online learning and unlearning\.External Links:2505\.08557Cited by:[§1](https://arxiv.org/html/2606.04182#S1.SS0.SSS0.Px3.p5.1)\.
- JDPO \(2019\)Japan \- Data Protection Overview \(JDPO\)\.Note:[https://www\.dataguidance\.com/notes/japan\-data\-protection\-overview](https://www.dataguidance.com/notes/japan-data-protection-overview)Cited by:[§1](https://arxiv.org/html/2606.04182#S1.p2.1)\.
- R\. Jin, M\. Chen, Q\. Zhang, and X\. Li \(2023\)Forgettable federated linear learning with certified data unlearning\.arXiv preprint arXiv:2306\.02216\.Cited by:[§1](https://arxiv.org/html/2606.04182#S1.p2.1)\.
- V\. Karwa and S\. Vadhan \(2017\)Finite sample differentially private confidence intervals\.arXiv preprint arXiv:1711\.03908\.Cited by:[§A\.1](https://arxiv.org/html/2606.04182#A1.SS1.SSS0.Px3.p3.5),[Lemma A\.6](https://arxiv.org/html/2606.04182#A1.Thmtheorem6),[Remark D\.2](https://arxiv.org/html/2606.04182#A4.Thmtheorem2.p1.1),[Remark 4\.5](https://arxiv.org/html/2606.04182#S4.Thmtheorem5.p1.8)\.
- I\. Mironov \(2017\)Rényi differential privacy\.In2017 IEEE 30th computer security foundations symposium \(CSF\),pp\. 263–275\.Cited by:[§B\.2](https://arxiv.org/html/2606.04182#A2.SS2.1.p1.6),[§B\.2](https://arxiv.org/html/2606.04182#A2.SS2.p1.2),[Lemma B\.2](https://arxiv.org/html/2606.04182#A2.Thmtheorem2)\.
- S\. Neel, A\. Roth, and S\. Sharifi\-Malvajerdi \(2021\)Descent\-to\-delete: gradient\-based methods for machine unlearning\.InAlgorithmic Learning Theory,pp\. 931–962\.Cited by:[§1](https://arxiv.org/html/2606.04182#S1.SS0.SSS0.Px3.p1.1),[§1](https://arxiv.org/html/2606.04182#S1.p3.1)\.
- D\. Qiao and Y\. Wang \(2023\)Near\-optimal differentially private reinforcement learning\.InInternational Conference on Artificial Intelligence and Statistics,pp\. 9914–9940\.Cited by:[§1](https://arxiv.org/html/2606.04182#S1.SS0.SSS0.Px3.p4.1),[§2](https://arxiv.org/html/2606.04182#S2.SS0.SSS0.Px2.p1.13)\.
- A\. Sekhari, J\. Acharya, G\. Kamath, and A\. T\. Suresh \(2021\)Remember what you want to forget: algorithms for machine unlearning\.Advances in Neural Information Processing Systems34,pp\. 18075–18086\.Cited by:[§1](https://arxiv.org/html/2606.04182#S1.p3.1)\.
- G\. Shani, D\. Heckerman, and R\. I\. Brafman \(2005\)An mdp\-based recommender system\.Journal of machine Learning research6\(Sep\),pp\. 1265–1295\.Cited by:[§1](https://arxiv.org/html/2606.04182#S1.SS0.SSS0.Px1.p4.1),[§2](https://arxiv.org/html/2606.04182#S2.SS0.SSS0.Px2.p1.13)\.
- R\. Shariff and O\. Sheffet \(2018\)Differentially private contextual linear bandits\.Advances in Neural Information Processing Systems31\.Cited by:[Remark D\.2](https://arxiv.org/html/2606.04182#A4.Thmtheorem2.p1.1)\.
- R\. Shokri, M\. Stronati, C\. Song, and V\. Shmatikov \(2017\)Membership inference attacks against machine learning models\.In2017 IEEE symposium on security and privacy \(SP\),pp\. 3–18\.Cited by:[§1](https://arxiv.org/html/2606.04182#S1.p1.1)\.
- E\. Ullah and R\. Arora \(2023\)From adaptive query release to machine unlearning\.InInternational Conference on Machine Learning,pp\. 34642–34667\.Cited by:[§B\.1](https://arxiv.org/html/2606.04182#A2.SS1.1.p1.1),[§B\.3](https://arxiv.org/html/2606.04182#A2.SS3.2.p2.5),[Lemma B\.1](https://arxiv.org/html/2606.04182#A2.Thmtheorem1.p1.2.2),[item 1](https://arxiv.org/html/2606.04182#S1.I1.i1.p1.1),[§1](https://arxiv.org/html/2606.04182#S1.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2606.04182#S1.SS0.SSS0.Px3.p2.1),[§1](https://arxiv.org/html/2606.04182#S1.p3.1),[§2](https://arxiv.org/html/2606.04182#S2.SS0.SSS0.Px4.p4.1),[§2](https://arxiv.org/html/2606.04182#S2.SS0.SSS0.Px5.p3.2),[Remark 2\.1](https://arxiv.org/html/2606.04182#S2.Thmtheorem1.p1.1),[§3\.1](https://arxiv.org/html/2606.04182#S3.SS1.p2.23),[§3\.2](https://arxiv.org/html/2606.04182#S3.SS2.p1.1),[§3\.2](https://arxiv.org/html/2606.04182#S3.SS2.p5.1),[§3\.2](https://arxiv.org/html/2606.04182#S3.SS2.p7.1),[§5](https://arxiv.org/html/2606.04182#S5.p5.1)\.
- E\. Ullah, T\. Mai, A\. Rao, R\. A\. Rossi, and R\. Arora \(2021\)Machine unlearning via algorithmic stability\.InConference on Learning Theory,pp\. 4126–4142\.Cited by:[Lemma A\.4](https://arxiv.org/html/2606.04182#A1.Thmtheorem4),[§B\.1](https://arxiv.org/html/2606.04182#A2.SS1.SSS0.Px1.p1.6),[§B\.1](https://arxiv.org/html/2606.04182#A2.SS1.SSS0.Px2.p5.3),[item 1](https://arxiv.org/html/2606.04182#S1.I1.i1.p1.1),[§1](https://arxiv.org/html/2606.04182#S1.SS0.SSS0.Px3.p2.1),[§1](https://arxiv.org/html/2606.04182#S1.p3.1),[§2](https://arxiv.org/html/2606.04182#S2.SS0.SSS0.Px5.p3.2),[§2](https://arxiv.org/html/2606.04182#S2.SS0.SSS0.Px6.p1.17),[§5](https://arxiv.org/html/2606.04182#S5.p5.1)\.
- M\. Van Waerebeke, M\. Lorenzi, G\. Neglia, and K\. Scaman \(2025\)When to forget? complexity trade\-offs in machine unlearning\.arXiv preprint arXiv:2502\.17323\.Cited by:[§1](https://arxiv.org/html/2606.04182#S1.p3.1)\.
- G\. Vietri, B\. Balle, A\. Krishnamurthy, and S\. Wu \(2020\)Private reinforcement learning with pac and regret guarantees\.InInternational Conference on Machine Learning,pp\. 9754–9764\.Cited by:[Remark D\.5](https://arxiv.org/html/2606.04182#A4.Thmtheorem5.p1.4),[§1](https://arxiv.org/html/2606.04182#S1.SS0.SSS0.Px3.p4.1),[§2](https://arxiv.org/html/2606.04182#S2.SS0.SSS0.Px2.p1.13),[§4\.1](https://arxiv.org/html/2606.04182#S4.SS1.SSS0.Px1.p1.2),[Remark 4\.3](https://arxiv.org/html/2606.04182#S4.Thmtheorem3.p1.10),[Remark 4\.5](https://arxiv.org/html/2606.04182#S4.Thmtheorem5.p1.8)\.
- D\. Ye, T\. Zhu, C\. Zhu, D\. Wang, K\. Gao, Z\. Shi, S\. Shen, W\. Zhou, and M\. Xue \(2023\)Reinforcement unlearning\.arXiv preprint arXiv:2312\.15910\.Cited by:[§1](https://arxiv.org/html/2606.04182#S1.SS0.SSS0.Px3.p3.1)\.
- X\. Zhou \(2022\)Differentially private reinforcement learning with linear function approximation\.Proceedings of the ACM on Measurement and Analysis of Computing Systems6\(1\),pp\. 1–27\.Cited by:[§1](https://arxiv.org/html/2606.04182#S1.SS0.SSS0.Px3.p4.1),[§2](https://arxiv.org/html/2606.04182#S2.SS0.SSS0.Px2.p1.13)\.

## Appendix ATechnical Lemmas

###### Lemma A\.1\.

We have

∫min⁡\{p​\(x\),q​\(x\)\}​𝑑x≥1−12​DKL​\(P∥Q\),\\displaystyle\\int\\min\\\{p\(x\),q\(x\)\\\}dx\\geq 1\-\\sqrt\{\\frac\{1\}\{2\}D\_\{\\text\{KL\}\}\(P\\\|Q\)\},whereDKLD\_\{\\text\{KL\}\}is the KL divergence\. , andp,qp,qare the densities ofPPandQQ, respectively\.

###### Proof\.

We have

1−∫min⁡\{p​\(x\),q​\(x\)\}​𝑑x\\displaystyle 1\-\\int\\min\\\{p\(x\),q\(x\)\\\}dx=12​∫\(p​\(x\)\+q​\(x\)−2​min⁡\{p​\(x\),q​\(x\)\}\)​𝑑x\\displaystyle=\\frac\{1\}\{2\}\\int\(p\(x\)\+q\(x\)\-2\\min\\\{p\(x\),q\(x\)\\\}\)dx=12​∫\|p​\(x\)−q​\(x\)\|​𝑑x\\displaystyle=\\frac\{1\}\{2\}\\int\|p\(x\)\-q\(x\)\|dx=TV​\(P,Q\)\\displaystyle=\{\\text\{TV\}\}\(P,Q\)≤12​DKL​\(P∥Q\),\\displaystyle\\leq\\sqrt\{\\frac\{1\}\{2\}D\_\{\\text\{KL\}\}\(P\\\|Q\)\},where the last inequality is due to Pinsker’s inequality\. ∎

###### Lemma A\.2\.

We have

DKL​\(𝒩​\(μ,σ2​I\),𝒩​\(ν,σ2​I\)\)=‖μ−ν‖222​σ2\.\\displaystyle D\_\{\\text\{KL\}\}\(\\mathcal\{N\}\(\\mu,\\sigma^\{2\}I\),\\mathcal\{N\}\(\\nu,\\sigma^\{2\}I\)\)=\\frac\{\\\|\\mu\-\\nu\\\|^\{2\}\_\{2\}\}\{2\\sigma^\{2\}\}\.

###### Lemma A\.3\(Concentration of spherical Gaussians\)\.

LetX∼𝒩​\(0,σ2​Id\)X\\sim\\mathcal\{N\}\(0,\\sigma^\{2\}I\_\{d\}\)\. For anyδ\\delta, with probability at least1−δ1\-\\delta,

‖X‖2≤σ​d​\(1\+2​log⁡\(1/δ\)d\)\.\\displaystyle\\\|X\\\|\_\{2\}\\leq\\sigma\\sqrt\{d\}\\left\(1\+\\sqrt\{\\frac\{2\\log\(1/\\delta\)\}\{d\}\}\\right\)\.

###### Lemma A\.4\(Reflection coupling\(Ullahet al\.,[2021](https://arxiv.org/html/2606.04182#bib.bib10), Lemma 1\)\)\.

LetPPandQQbe two distributions overℝd\\mathbb\{R\}^\{d\}\. Letψ:ℝd→ℝd\\psi:\\mathbb\{R\}^\{d\}\\rightarrow\\mathbb\{R\}^\{d\}be a bijection such thatfP​\(ψ​\(x\)\)=fQ​\(x\)f\_\{P\}\(\\psi\(x\)\)=f\_\{Q\}\(x\)and\|d​e​t​d​ψ​\(x\)d​x\|=1\|det\\frac\{d\\psi\(x\)\}\{dx\}\|=1, whered​ψ​\(x\)/d​xd\\psi\(x\)/dxis the Jacobian of the multivariate mapψ\\psi\. Letx∼Px\\sim Pandy=xy=xifU​n​i​f​\(0,1\)≤fQ​\(x\)fP​\(x\)Unif\(0,1\)\\leq\\frac\{f\_\{Q\}\(x\)\}\{f\_\{P\}\(x\)\}andy=ψ​\(x\)y=\\psi\(x\)otherwise\. Then\(x,y\)\(x,y\)is a maximal coupling of\(P,Q\)\(P,Q\)\.

In addition, two isotropic GaussiansP,QP,Qoverℝd\\mathbb\{R\}^\{d\}with meansμP\\mu\_\{P\}andμQ\\mu\_\{Q\}such that for any two vectorsx,yx,y,fP​\(x\)=fQ​\(y\)f\_\{P\}\(x\)=f\_\{Q\}\(y\)if‖μP−x‖=‖μQ−y‖\\\|\\mu\_\{P\}\-x\\\|=\\\|\\mu\_\{Q\}\-y\\\|\. Then, with the mapψ​\(x\)=μQ\+μP−x\\psi\(x\)=\\mu\_\{Q\}\+\\mu\_\{P\}\-x,P,Q,ψP,Q,\\psisatisfy the conditions in the preceding result\.

### A\.1Connections to Different Stability Notions

Letx¯=\(x1,…,xn\)\\underline\{x\}=\(x\_\{1\},\\ldots,x\_\{n\}\)be a dataset ofnnelements where eachxi∈Ωx\_\{i\}\\in\\Omega\. Two datasets,x¯\\underline\{x\}andx¯′\\underline\{x\}^\{\\prime\}, both of sizenn, are called neighbors if they differ by one element\.

###### Definition A\.1\(Differential privacy \(DP\)\(Dworket al\.,[2006](https://arxiv.org/html/2606.04182#bib.bib27)\)\)\.

A randomized algorithmM:Ωn→ΩMM:\\Omega^\{n\}\\rightarrow\\Omega\_\{M\}is\(ϵ,δ\)\(\\epsilon,\\delta\)differentially private if for all neighboring datasetsx¯,x¯′∈Ωn\\underline\{x\},\\underline\{x\}^\{\\prime\}\\in\\Omega^\{n\}and for all measurable sets of outputsE∈ΩME\\in\\Omega\_\{M\}, we have

Pr⁡\(M​\(x¯\)∈E\)≤eϵ​Pr⁡\(M​\(x¯′\)∈E\)\+δ\.\\displaystyle\\Pr\(M\(\\underline\{x\}\)\\in E\)\\leq e^\{\\epsilon\}\\Pr\(M\(\\underline\{x\}^\{\\prime\}\)\\in E\)\+\\delta\.

Note that\(ϵ,0\)\(\{\\epsilon\},0\)\-DP is calledϵ\{\\epsilon\}\-pure\-DP\.

###### Definition A\.2\(TV\-stability\)\.

A randomized algorithmM:Ωn→ΩMM:\\Omega^\{n\}\\rightarrow\\Omega\_\{M\}isρ\\rho\-TV\-stable if for all neighboring datasetsx¯,x¯′∈Ωn\\underline\{x\},\\underline\{x\}^\{\\prime\}\\in\\Omega^\{n\}, we have

TV​\(Pr⁡\(M​\(x¯\)\),Pr⁡\(M​\(x¯′\)\)\)≤ρ\.\\displaystyle\{\\text\{TV\}\}\(\\Pr\(M\(\\underline\{x\}\)\),\\Pr\(M\(\\underline\{x\}^\{\\prime\}\)\)\)\\leq\\rho\.

###### Lemma A\.5\(Relationship between differential privacy and TV stability\)\.

We have

1. 1\.If a randomized algorithmMMis\(ϵ,0\)\(\{\\epsilon\},0\)differentially private, thenMMis\(eϵ−1\)\(e^\{\\epsilon\}\-1\)\-TV\-stable \(which is\(2​ϵ\)\(2\\epsilon\)\-TV\-stable, ifϵ∈\[0,1\]\{\\epsilon\}\\in\[0,1\]\), but not vice versa, i\.e\., there exists no absolute constantc\>0c\>0such that, ifMMisϵ\{\\epsilon\}\-TV\-stable, thenMMis\(c​ϵ,0\)\(c\{\\epsilon\},0\)\-DP\.
2. 2\.TV\-stability does not imply pure DP in the following strong sense: There does not exist any functionf:ℝ\+→ℝ\+f:\\mathbb\{R\}\_\{\+\}\\rightarrow\\mathbb\{R\}\_\{\+\}such that, ifMMisϵ\{\\epsilon\}\-TV\-stable for anyϵ∈\(0,1\)\{\\epsilon\}\\in\(0,1\), thenMMisf​\(ϵ\)f\(\{\\epsilon\}\)\-pure\-DP\.
3. 3\.A randomized algorithmMMis\(0,δ\)\(0,\\delta\)differentially private iff it isδ\\delta\-TV\-stable\.

###### Proof of[LemmaA\.5](https://arxiv.org/html/2606.04182#A1.Thmtheorem5)\.

LetP=Pr⁡\(M​\(x¯\)\)P=\\Pr\(M\(\\underline\{x\}\)\)andQ=Pr⁡\(M​\(x¯′\)\)Q=\\Pr\(M\(\\underline\{x\}^\{\\prime\}\)\)\.

#### For Part 1\.

For any measurable eventEE, ifMMis\(ϵ,0\)\(\\epsilon,0\)\-DP, thenP​\(E\)≤eϵ​Q​\(E\)P\(E\)\\leq e^\{\{\\epsilon\}\}Q\(E\)\. Thus,

P​\(E\)−Q​\(E\)≤\(eϵ−1\)​Q≤eϵ−1,\\displaystyle P\(E\)\-Q\(E\)\\leq\(e^\{\{\\epsilon\}\}\-1\)Q\\leq e^\{\{\\epsilon\}\}\-1,which implies thatTV​\(P,Q\)≤eϵ−1\{\\text\{TV\}\}\(P,Q\)\\leq e^\{\{\\epsilon\}\}\-1\. Forϵ∈\[0,1\]\{\\epsilon\}\\in\[0,1\], we haveeϵ−1≤2​ϵe^\{\{\\epsilon\}\}\-1\\leq 2\{\\epsilon\}\.

#### For Part 2\.

Now suppose thatTV​\(P,Q\)≤ϵ\{\\text\{TV\}\}\(P,Q\)\\leq\{\\epsilon\}\. We will construct a counterexample\(P,Q\)\(P,Q\)where there does not exist any functionf:ℝ\+→ℝ\+f:\\mathbb\{R\}\_\{\+\}\\rightarrow\\mathbb\{R\}\_\{\+\}such thatP​\(E\)≤ef​\(ϵ\)​Q​\(E\),∀EP\(E\)\\leq e^\{f\(\{\\epsilon\}\)\}Q\(E\),\\forall E, i\.e\.,P​\(E\)−Q​\(E\)≤\(ef​\(ϵ\)−1\)​Q​\(E\)P\(E\)\-Q\(E\)\\leq\(e^\{f\(\{\\epsilon\}\)\}\-1\)Q\(E\)\. Assume there exists suchff\. PickPPandQQsuch that there is an eventEEwherep−q=ϵp\-q=\\epsilonandq=ϵn\+1q=\{\\epsilon\}^\{n\+1\}, wherep=P​\(E\),q=Q​\(E\)p=P\(E\),q=Q\(E\)\(e\.g\.,PPandQQare supported on only two points\)\. We have

qp−q​\(ef​\(ϵ\)−1\)=ϵn​\(ef​\(ϵ\)−1\)​→n→∞​0,\\displaystyle\\frac\{q\}\{p\-q\}\(e^\{f\(\{\\epsilon\}\)\}\-1\)=\{\\epsilon\}^\{n\}\(e^\{f\(\{\\epsilon\}\)\}\-1\)\\overset\{n\\rightarrow\\infty\}\{\\rightarrow\}0,Thus, we can picknnsuch thatqp−q​\(ef​\(ϵ\)−1\)<1\\frac\{q\}\{p\-q\}\(e^\{f\(\{\\epsilon\}\)\}\-1\)<1, leading to the contradiction\.

#### For Part 3\.

It is trivial from the definition\. ∎

Part 1 implies thatϵ\{\\epsilon\}\-DP is stronger than TV\-stability, thus a lower bound forϵ\{\\epsilon\}\-DP algorithms does not trivially imply a lower bound for TV\-stable algorithms\.

The simple observation from Part 2 of[LemmaA\.5](https://arxiv.org/html/2606.04182#A1.Thmtheorem5)turns the beautiful result of\(Karwa and Vadhan,[2017](https://arxiv.org/html/2606.04182#bib.bib14), Lemma 6\.1\)from DP algorithms to TV\-stable algorithms\. In particular, the following lemma, a corollary of\(Karwa and Vadhan,[2017](https://arxiv.org/html/2606.04182#bib.bib14), Lemma 6\.1\)and Part 2 of[LemmaA\.5](https://arxiv.org/html/2606.04182#A1.Thmtheorem5), says that, if the TV distance between the two outputs of aρ\\rho\-TV\-stable algorithm on an i\.i\.d\. sample from two distributionsPPandQQ, respectively, scale withρ⋅n⋅TV​\(P,Q\)\\rho\\cdot n\\cdot\{\\text\{TV\}\}\(P,Q\)wherennis the sample size of the i\.i\.d\. samples\.

###### Lemma A\.6\(\(Karwa and Vadhan,[2017](https://arxiv.org/html/2606.04182#bib.bib14), Lemma 6\.1\)\)\.

For every pair of distributionPPandQQ, everyρ\\rho\-TV\-stable randomized algorithmM​\(x1:n\)M\(x\_\{1:n\}\), if𝕄P,𝕄Q\\mathbb\{M\}\_\{P\},\\mathbb\{M\}\_\{Q\}are the marginal distributions induced by runningMMon the i\.i\.d\. samplesx1:nx\_\{1:n\}drawn fromPPandQQ, respectively, then

TV​\(𝕄P,𝕄Q\)≤4​n​ρ​TV​\(P,Q\)\.\\displaystyle\{\\text\{TV\}\}\\left\(\\mathbb\{M\}\_\{P\},\\mathbb\{M\}\_\{Q\}\\right\)\\leq 4n\\rho\{\\text\{TV\}\}\(P,Q\)\.

The above lemma is a key to establish the lower bounds for regret ofρ\\rho\-TV\-stable RL algorithms in[AppendixD](https://arxiv.org/html/2606.04182#A4)\.

## Appendix BUnlearning Guarantees

### B\.1Proof of Part 1 of Theorem[3\.3](https://arxiv.org/html/2606.04182#S3.Thmtheorem3)

###### Proof of part 1 of[Theorem3\.3](https://arxiv.org/html/2606.04182#S3.Thmtheorem3)\.

This proof of part 1 mainly follows from the logic established in\(Ullah and Arora,[2023](https://arxiv.org/html/2606.04182#bib.bib2), Lemma 4\), only with significantly simplified steps and language – partly due to that we do not have to deal with permuting the dataset as in the original proof of\(Ullah and Arora,[2023](https://arxiv.org/html/2606.04182#bib.bib2)\)\. The key idea is, again, to show that our unlearning algorithm is a construction of an approximately maximal coupling between the distributions of the output of the learning algorithm on the original data and the modified data, respectively\.

Let𝒟=\{z1,…,zT\}\\mathcal\{D\}=\\\{z\_\{1\},\\ldots,z\_\{T\}\\\}and𝒟′=\{z1,…,zt−1,z′,zt\+1,…,zT\}\\mathcal\{D\}^\{\\prime\}=\\\{z\_\{1\},\\ldots,z\_\{t\-1\},z^\{\\prime\},z\_\{t\+1\},\\ldots,z\_\{T\}\\\}, wherettis the position where the user data needs to be deleted\. LetP,QP,Qbe the probability over the range of the tree data structure induced by the output of the learning algorithm on𝒟\\mathcal\{D\}and𝒟′\\mathcal\{D\}^\{\\prime\}, respectively\.

Let𝒯,𝒯′\\mathcal\{T\},\\mathcal\{T\}^\{\\prime\}be the binary trees constructed after running the learning algorithm on𝒟\\mathcal\{D\}and after unlearning, respectively\. We order the nodes of a tree by the post\-order traversal\. That is, whenever we talk about any sense of orders of nodes in a tree, we implicitly mean the post\-order traversal\. For example,≤b\\leq bdenotes the set of all nodes that are prior to nodebbin the post\-order traversal\. For any subset of nodesSS,𝒯S\\mathcal\{T\}\_\{S\}denotes the sub\-tree of𝒯\\mathcal\{T\}that contains only the nodes inSSandQSQ\_\{S\}denotes the marginal distribution ofQQon the nodesSS\.

The goal is to show that,

Pr⁡\(𝒯′∈E\)=Q​\(E\),∀measurable event​E\.\\displaystyle\\Pr\(\\mathcal\{T\}^\{\\prime\}\\in E\)=Q\(E\),\\forall\\text\{ measurable event \}E\.\(2\)
Recall that each nodebbin a tree consists of clean valuevbv\_\{b\}, noisy valuev~b\\tilde\{v\}\_\{b\}and a modelww\(if the node is a leaf\)\. The clean valuevbv\_\{b\}and the modelwware outputs of functions on only the noisy prefix sum of the nodes that precedebb\(in the post\-traversal order\), while the noisy valuev~b\\tilde\{v\}\_\{b\}is a noisy version ofvbv\_\{b\}, added with an independent noise\. Thus, to prove[Equation2](https://arxiv.org/html/2606.04182#A2.E2), it suffices to prove that,

Pr⁡\(𝒯~′∈E\)=Q~​\(E\),∀measurable event​E\.\\displaystyle\\Pr\(\{\\widetilde\{\\mathcal\{T\}\}\}^\{\\prime\}\\in E\)=\{\\widetilde\{Q\}\}\(E\),\\forall\\text\{ measurable event \}E\.\(3\)where𝒯~′\{\\widetilde\{\\mathcal\{T\}\}\}^\{\\prime\}is the same as𝒯~\{\\widetilde\{\\mathcal\{T\}\}\}except each node in𝒯~′\{\\widetilde\{\\mathcal\{T\}\}\}^\{\\prime\}only represents the noisy value, andQ~\{\\widetilde\{Q\}\}is the marginal distribution ofQQon the noisy values\.

We will prove[Equation3](https://arxiv.org/html/2606.04182#A2.E3)by induction bykk,

Pr⁡\(𝒯~≤k′∈E\)=Q~≤k​\(E\),∀measurable event​E\.\\displaystyle\\Pr\(\{\\widetilde\{\\mathcal\{T\}\}\}^\{\\prime\}\_\{\\leq k\}\\in E\)=\{\\widetilde\{Q\}\}\_\{\\leq k\}\(E\),\\forall\\text\{ measurable event \}E\.\(4\)

#### Base casek=1k=1\.

Ift\>1t\>1, we havePr⁡\(𝒯~≤1′∈E\)=Q~≤1​\(E\)\\Pr\(\{\\widetilde\{\\mathcal\{T\}\}\}^\{\\prime\}\_\{\\leq 1\}\\in E\)=\\tilde\{Q\}\_\{\\leq 1\}\(E\), since the deleted nodettdoes not depend on nodek=1k=1\. Consider the caset=1t=1\. In this case,\(Ullahet al\.,[2021](https://arxiv.org/html/2606.04182#bib.bib10), Lemma 1\)implies thatPr⁡\(v~1∈E\)=Q~≤1​\(E\)\\Pr\(\\tilde\{v\}\_\{1\}\\in E\)=\\tilde\{Q\}\_\{\\leq 1\}\(E\)\.

#### Induction step\.

We now proceed to the induction step: Let us assume that[Equation4](https://arxiv.org/html/2606.04182#A2.E4)holds for all nodes up tokk, we will prove that it holds for nodek\+1k\+1as well\. If the deleted positiont\>k\+1t\>k\+1,[Equation4](https://arxiv.org/html/2606.04182#A2.E4)holds fork\+1k\+1, since all nodes<t<tdo not get affected by changing nodett\.

We only need to considert≤k\+1t\\leq k\+1\. For this case, there are only the following further cases:

- •A: All rejection sampling steps prior to nodek\+1k\+1resulted in accept\. - –AP: Nodek\+1k\+1is on the path from nodettto the root - \*APA: The rejection sampling step at nodek\+1k\+1resulted in accept\. - \*APR: The rejection sampling step at nodek\+1k\+1resulted in reject\. - –AN: Nodek\+1k\+1is not on the path from nodettto the root
- •R: Some rejection sampling steps prior to nodek\+1k\+1resulted in reject\. - –RP: Nodek\+1k\+1is on the path from nodettto the root - –RN: Nodek\+1k\+1is not on the path from nodettto the root

For case RP, nodek\+1k\+1is not on the nodes that got re\-trained from scratch as we retrained the subtree starting from the leaf that is right next after nodek\+1k\+1\. Butvk\+1v\_\{k\+1\}still got updated to ensure that the clean value of nodek\+1k\+1is the sum of the clean values of its children\. Thus, we havePr⁡\(v~k\+1∈Ek\+1\|RP,𝒯~≤k′∈E≤k\)=Q~k\+1​\(Ek\+1\|E≤k\)\\Pr\(\\tilde\{v\}\_\{k\+1\}\\in E\_\{k\+1\}\|\\text\{RP\},\{\\widetilde\{\\mathcal\{T\}\}\}^\{\\prime\}\_\{\\leq k\}\\in E\_\{\\leq k\}\)=\{\\widetilde\{Q\}\}\_\{k\+1\}\(E\_\{k\+1\}\|E\_\{\\leq k\}\)\.

For case RN, nodek\+1k\+1got re\-trained from scratch, thus we must havePr⁡\(v~k\+1∈Ek\+1\|RN,𝒯~≤k′∈E≤k\)=Q~k\+1​\(Ek\+1\|E≤k\)\\Pr\(\\tilde\{v\}\_\{k\+1\}\\in E\_\{k\+1\}\|\\text\{RN\},\{\\widetilde\{\\mathcal\{T\}\}\}^\{\\prime\}\_\{\\leq k\}\\in E\_\{\\leq k\}\)=\{\\widetilde\{Q\}\}\_\{k\+1\}\(E\_\{k\+1\}\|E\_\{\\leq k\}\)\.

For case AN, we havePr⁡\(v~k\+1∈Ek\+1\|AN,𝒯~≤k′∈E≤k\)=Q~k\+1​\(Ek\+1\|E≤k\)\\Pr\(\{\\tilde\{v\}\}\_\{k\+1\}\\in E\_\{k\+1\}\|\\text\{AN\},\{\\widetilde\{\\mathcal\{T\}\}\}^\{\\prime\}\_\{\\leq k\}\\in E\_\{\\leq k\}\)=\{\\widetilde\{Q\}\}\_\{k\+1\}\(E\_\{k\+1\}\|E\_\{\\leq k\}\), as the clean value of nodek\+1k\+1does not get modified during unlearning when nodettis deleted\.

For case AP, we also havePr⁡\(v~k\+1∈Ek\+1\|AP,𝒯~≤k∈E≤k\)=Q~k\+1​\(Ek\+1\|E≤k\)\\Pr\(\{\\tilde\{v\}\}\_\{k\+1\}\\in E\_\{k\+1\}\|\\text\{AP\},\{\\widetilde\{\\mathcal\{T\}\}\}\_\{\\leq k\}\\in E\_\{\\leq k\}\)=\{\\widetilde\{Q\}\}\_\{k\+1\}\(E\_\{k\+1\}\|E\_\{\\leq k\}\), as the sub\-tree associated with nodes≤k\\leq kget unmodified during unlearning in case A, and the rejection sampling and the reflection map at nodek\+1k\+1results in a valid coupling \(\(Ullahet al\.,[2021](https://arxiv.org/html/2606.04182#bib.bib10), Lemma 1\)\)\.

Thus, we must havePr⁡\(v~k\+1∈Ek\+1\|𝒯~≤k′∈E≤k\)=Q~k\+1​\(Ek\+1\|E≤k\)\\Pr\(\{\\tilde\{v\}\}\_\{k\+1\}\\in E\_\{k\+1\}\|\{\\widetilde\{\\mathcal\{T\}\}\}^\{\\prime\}\_\{\\leq k\}\\in E\_\{\\leq k\}\)=\{\\widetilde\{Q\}\}\_\{k\+1\}\(E\_\{k\+1\}\|E\_\{\\leq k\}\)\. Overall, we have

Pr⁡\(𝒯~≤k\+1′∈E≤k\+1\)\\displaystyle\\Pr\(\{\\widetilde\{\\mathcal\{T\}\}\}^\{\\prime\}\_\{\\leq k\+1\}\\in E\_\{\\leq k\+1\}\)=Pr⁡\(v~k\+1∈Ek\+1\|𝒯~≤k′∈E≤k\)​Pr⁡\(𝒯~≤k′∈E≤k\)\\displaystyle=\\Pr\(\{\\tilde\{v\}\}\_\{k\+1\}\\in E\_\{k\+1\}\|\{\\widetilde\{\\mathcal\{T\}\}\}^\{\\prime\}\_\{\\leq k\}\\in E\_\{\\leq k\}\)\\Pr\(\{\\widetilde\{\\mathcal\{T\}\}\}^\{\\prime\}\_\{\\leq k\}\\in E\_\{\\leq k\}\)=Q~k\+1​\(Ek\+1\|E≤k\)​Q~≤k​\(E≤k\)\\displaystyle=\{\\widetilde\{Q\}\}\_\{k\+1\}\(E\_\{k\+1\}\|E\_\{\\leq k\}\)\{\\widetilde\{Q\}\}\_\{\\leq k\}\(E\_\{\\leq k\}\)=Q~≤k\+1​\(E≤k\+1\),\\displaystyle=\{\\widetilde\{Q\}\}\_\{\\leq k\+1\}\(E\_\{\\leq k\+1\}\),whereE≤k\+1=E1×…×Ek\+1E\_\{\\leq k\+1\}=E\_\{1\}\\times\\ldots\\times E\_\{k\+1\}, and where the second equation uses the induction assumption thatPr⁡\(𝒯~≤k′∈E≤k\)=Q~≤k​\(E≤k\)\\Pr\(\{\\widetilde\{\\mathcal\{T\}\}\}^\{\\prime\}\_\{\\leq k\}\\in E\_\{\\leq k\}\)=\{\\widetilde\{Q\}\}\_\{\\leq k\}\(E\_\{\\leq k\}\)\. ∎

### B\.2Proof of Part 2 of Theorem[3\.3](https://arxiv.org/html/2606.04182#S3.Thmtheorem3)

###### Definition B\.1\.

A mechanism𝒜\\mathcal\{A\}is\(α,ϵ​\(α\)\)\(\\alpha,\{\\epsilon\}\(\\alpha\)\)\-RDP if for any two datasetsSSandS′S^\{\\prime\}that differ by one entry, we have

Dα​\(𝒮∥𝒮′\)≤ϵ​\(α\)\\displaystyle D\_\{\\alpha\}\(\\mathcal\{S\}\\\|\\mathcal\{S\}^\{\\prime\}\)\\leq\{\\epsilon\}\(\\alpha\)

RDP\(Mironov,[2017](https://arxiv.org/html/2606.04182#bib.bib40)\)is proposed as a notion of DP that complements the weakness of the standard approximate DP \(e\.g\., never compromise a total breach of privacy as in\(ϵ,δ\)\(\{\\epsilon\},\\delta\)\-DP\)\. RDP implies approximate DP but not the reverse\. So in terms of weaknesses,D​P<R​D​P<A​D​PDP<RDP<ADP\.

###### Lemma B\.1\.

\(RDP implies TV stability\(Ullah and Arora,[2023](https://arxiv.org/html/2606.04182#bib.bib2)\)\) If an algorithm satisfies\(α,ϵ​\(α\)\)\(\\alpha,\{\\epsilon\}\(\\alpha\)\)\-RDP, then it satisfieslimα→1ϵ​\(α\)\\sqrt\{\\lim\_\{\\alpha\\rightarrow 1\}\{\\epsilon\}\(\\alpha\)\}\-TV stability\.

###### Lemma B\.2\(\(Mironov,[2017](https://arxiv.org/html/2606.04182#bib.bib40)\)\)\.

Letffbe a real\-valued function withℓ2\\ell\_\{2\}\-sensitivity ofBB\. The gaussian mechanism of adding𝒩​\(0,σ2\)\\mathcal\{N\}\(0,\\sigma^\{2\}\)is\(α,α​B2/\(2​σ2\)\)\(\\alpha,\\alpha B^\{2\}/\(2\\sigma^\{2\}\)\)\-RDP for anyα≥1\\alpha\\geq 1\.

###### Proof of part 2 of[Theorem3\.3](https://arxiv.org/html/2606.04182#S3.Thmtheorem3)\.

The proof is standard following the techniques in differential privacy with Gaussian noises and the two lemmas above\. In particular, we will compute the RDP of the binary tree before and after deleting one user data\. When we change one user data, there are at mostlog2⁡T\\log\_\{2\}Tnodes in the binary tree that get impacted\. Each impacted node is\(α,α​B2/\(2​σ2\)\)\(\\alpha,\\alpha B^\{2\}/\(2\\sigma^\{2\}\)\)\-RDP, by[LemmaB\.2](https://arxiv.org/html/2606.04182#A2.Thmtheorem2)\. Using the composition theorem\(Mironov,[2017](https://arxiv.org/html/2606.04182#bib.bib40), Proposition 1\), the impacted path is\(α,α​B2​log2⁡T/\(2​σ2\)\)\(\\alpha,\\alpha B^\{2\}\\log\_\{2\}T/\(2\\sigma^\{2\}\)\)\-RDP, as there are at mostlog2⁡T\\log\_\{2\}Tnodes in the path\. Since the other nodes do not get impacted, the entire tree is\(α,α​B2​log2⁡T/\(2​σ2\)\)\(\\alpha,\\alpha B^\{2\}\\log\_\{2\}T/\(2\\sigma^\{2\}\)\)\-RDP\. Thus, by[LemmaB\.1](https://arxiv.org/html/2606.04182#A2.Thmtheorem1), the entire tree isB​log2⁡T2​σ\\frac\{B\\sqrt\{\\log\_\{2\}T\}\}\{\\sqrt\{2\}\\sigma\}\-TV\-stable\. ∎

### B\.3Proof of Part 3 of Theorem[3\.3](https://arxiv.org/html/2606.04182#S3.Thmtheorem3)

###### Proof of part 3 of[Theorem3\.3](https://arxiv.org/html/2606.04182#S3.Thmtheorem3)\.

During unlearning, re\-training is only triggered when a rejection sampling step fails at some nodebbin the path from the nodettto the root\. Let us define this path bypath=\{b1,…​bl\}\\texttt\{path\}=\\\{b\_\{1\},\\ldots b\_\{l\}\\\}, in the order from the leaf nodet=b1t=b\_\{1\}to the rootblb\_\{l\}, wherel=\|path\|l=\|\\texttt\{path\}\|\. LetAcceptbe the event where the rejection sampling steps in all nodes inpathsucceed\. Letζ=\(ζ1,…,ζl\)∼Unif​\(0,1\)l\\zeta=\(\\zeta\_\{1\},\\ldots,\\zeta\_\{l\}\)\\sim\\text\{Unif\}\(0,1\)^\{l\}\. We have,

Pr⁡\(Accept\)\\displaystyle\\Pr\(\\texttt\{Accept\}\)=𝔼𝒯,ζ​∏b∈path1​\{ζb≤f𝒩​\(vb′,σ2​I\)​\(v~b\)f𝒩​\(vb,σ2​I\)​\(v~b\)\}\\displaystyle=\{\\mathbb\{E\}\}\_\{\{\\mathcal\{T\}\},\\zeta\}\\prod\_\{b\\in\\texttt\{path\}\}1\\left\\\{\\zeta\_\{b\}\\leq\\frac\{f\_\{\\mathcal\{N\}\(v^\{\\prime\}\_\{b\},\\sigma^\{2\}I\)\}\(\\tilde\{v\}\_\{b\}\)\}\{f\_\{\\mathcal\{N\}\(v\_\{b\},\\sigma^\{2\}I\)\}\(\\tilde\{v\}\_\{b\}\)\}\\right\\\}=𝔼𝒯​𝔼ζ\|𝒯​\[∏b∈path1​\{ζb≤f𝒩​\(vb′,σ2​I\)​\(v~b\)f𝒩​\(vb,σ2​I\)​\(v~b\)\}\]\\displaystyle=\{\\mathbb\{E\}\}\_\{\{\\mathcal\{T\}\}\}\{\\mathbb\{E\}\}\_\{\\zeta\|\{\\mathcal\{T\}\}\}\\left\[\\prod\_\{b\\in\\texttt\{path\}\}1\\left\\\{\\zeta\_\{b\}\\leq\\frac\{f\_\{\\mathcal\{N\}\(v^\{\\prime\}\_\{b\},\\sigma^\{2\}I\)\}\(\\tilde\{v\}\_\{b\}\)\}\{f\_\{\\mathcal\{N\}\(v\_\{b\},\\sigma^\{2\}I\)\}\(\\tilde\{v\}\_\{b\}\)\}\\right\\\}\\right\]=𝔼𝒯​\[∏b∈pathmin⁡\{1,f𝒩​\(vb′,σ2​I\)​\(v~b\)f𝒩​\(vb,σ2​I\)​\(v~b\)\}\]\\displaystyle=\{\\mathbb\{E\}\}\_\{\{\\mathcal\{T\}\}\}\\left\[\\prod\_\{b\\in\\texttt\{path\}\}\\min\\left\\\{1,\\frac\{f\_\{\\mathcal\{N\}\(v^\{\\prime\}\_\{b\},\\sigma^\{2\}I\)\}\(\\tilde\{v\}\_\{b\}\)\}\{f\_\{\\mathcal\{N\}\(v\_\{b\},\\sigma^\{2\}I\)\}\(\\tilde\{v\}\_\{b\}\)\}\\right\\\}\\right\]=𝔼𝒯​\[∏b∈pathmin⁡\{f𝒩​\(vb,σ2​I\)​\(v~b\),f𝒩​\(vb′,σ2​I\)​\(v~b\)\}\]\\displaystyle=\{\\mathbb\{E\}\}\_\{\{\\mathcal\{T\}\}\}\\left\[\\prod\_\{b\\in\\texttt\{path\}\}\\min\\left\\\{f\_\{\\mathcal\{N\}\(v\_\{b\},\\sigma^\{2\}I\)\}\(\\tilde\{v\}\_\{b\}\),f\_\{\\mathcal\{N\}\(v^\{\\prime\}\_\{b\},\\sigma^\{2\}I\)\}\(\\tilde\{v\}\_\{b\}\)\\right\\\}\\right\]=∫vb1,v~b1…​∫vbl,v~bl∏i=1lmin⁡\{1,f𝒩​\(vbi′,σ2​I\)​\(v~bi\)f𝒩​\(vbi,σ2​I\)​\(v~bi\)\}​d​P​\(vbl,v~bl\|vb≤l−1,v~b≤l−1\)​…​d​P​\(vb1,v~b1\)\\displaystyle=\\int\_\{v\_\{b\_\{1\}\},\{\\tilde\{v\}\}\_\{b\_\{1\}\}\}\\ldots\\int\_\{v\_\{b\_\{l\}\},\{\\tilde\{v\}\}\_\{b\_\{l\}\}\}\\prod\_\{i=1\}^\{l\}\\min\\left\\\{1,\\frac\{f\_\{\\mathcal\{N\}\(v^\{\\prime\}\_\{b\_\{i\}\},\\sigma^\{2\}I\)\}\(\\tilde\{v\}\_\{b\_\{i\}\}\)\}\{f\_\{\\mathcal\{N\}\(v\_\{b\_\{i\}\},\\sigma^\{2\}I\)\}\(\\tilde\{v\}\_\{b\_\{i\}\}\)\}\\right\\\}dP\(v\_\{b\_\{l\}\},\{\\tilde\{v\}\}\_\{b\_\{l\}\}\|v\_\{b\_\{\\leq l\-1\}\},\{\\tilde\{v\}\}\_\{b\_\{\\leq l\-1\}\}\)\\ldots dP\(v\_\{b\_\{1\}\},\{\\tilde\{v\}\}\_\{b\_\{1\}\}\)=∫vb1,v~b1…∫vbl,v~bl∏i=1lmin\{1,f𝒩​\(vbi′,σ2​I\)​\(v~bi\)f𝒩​\(vbi,σ2​I\)​\(v~bi\)\}f𝒩​\(vbl,σ2​I\)\(v~bl\)dP\(vbl,\|vb≤l−1,v~b≤l−1\)…dP\(vb1,v~b1\)\\displaystyle=\\int\_\{v\_\{b\_\{1\}\},\{\\tilde\{v\}\}\_\{b\_\{1\}\}\}\\ldots\\int\_\{v\_\{b\_\{l\}\},\{\\tilde\{v\}\}\_\{b\_\{l\}\}\}\\prod\_\{i=1\}^\{l\}\\min\\left\\\{1,\\frac\{f\_\{\\mathcal\{N\}\(v^\{\\prime\}\_\{b\_\{i\}\},\\sigma^\{2\}I\)\}\(\\tilde\{v\}\_\{b\_\{i\}\}\)\}\{f\_\{\\mathcal\{N\}\(v\_\{b\_\{i\}\},\\sigma^\{2\}I\)\}\(\\tilde\{v\}\_\{b\_\{i\}\}\)\}\\right\\\}f\_\{\\mathcal\{N\}\(v\_\{b\_\{l\}\},\\sigma^\{2\}I\)\}\(\\tilde\{v\}\_\{b\_\{l\}\}\)dP\(v\_\{b\_\{l\}\},\|v\_\{b\_\{\\leq l\-1\}\},\{\\tilde\{v\}\}\_\{b\_\{\\leq l\-1\}\}\)\\ldots dP\(v\_\{b\_\{1\}\},\{\\tilde\{v\}\}\_\{b\_\{1\}\}\)≥∏i=1l\(1−Bσ\)\\displaystyle\\geq\\prod\_\{i=1\}^\{l\}\(1\-\\frac\{B\}\{\\sigma\}\)≥1−l​Bσ\\displaystyle\\geq 1\-l\\frac\{B\}\{\\sigma\}≥1−B​log⁡Tσ\\displaystyle\\geq 1\-\\frac\{B\\log T\}\{\\sigma\}
where the third equality follows asζ\\zetais independent of𝒯\{\\mathcal\{T\}\}, the second inequality is due toUllah and Arora \([2023](https://arxiv.org/html/2606.04182#bib.bib2), Lemma 7\), the last inequality is due to the fact that the maximum length of the path from a leaf to the root islog⁡T\\log T, and the first inequality is due to the following inequality \(and induction fromllto11\):

∫min⁡\{1,f𝒩​\(vbi′,σ2​I\)​\(v~bi\)f𝒩​\(vbi,σ2​I\)​\(v~bi\)\}​f𝒩​\(vbl,σ2​I\)​\(v~bl\)​𝑑P​\(v~bl\|vbl\)\\displaystyle\\int\\min\\left\\\{1,\\frac\{f\_\{\\mathcal\{N\}\(v^\{\\prime\}\_\{b\_\{i\}\},\\sigma^\{2\}I\)\}\(\\tilde\{v\}\_\{b\_\{i\}\}\)\}\{f\_\{\\mathcal\{N\}\(v\_\{b\_\{i\}\},\\sigma^\{2\}I\)\}\(\\tilde\{v\}\_\{b\_\{i\}\}\)\}\\right\\\}f\_\{\\mathcal\{N\}\(v\_\{b\_\{l\}\},\\sigma^\{2\}I\)\}\(\\tilde\{v\}\_\{b\_\{l\}\}\)dP\(\{\\tilde\{v\}\}\_\{b\_\{l\}\}\|v\_\{b\_\{l\}\}\)=∫min⁡\{f𝒩​\(vbi,σ2​I\)​\(v~bi\),f𝒩​\(vbi′,σ2​I\)​\(v~bi\)\}​𝑑P​\(v~bl\|vbl\)\\displaystyle=\\int\\min\\left\\\{f\_\{\\mathcal\{N\}\(v\_\{b\_\{i\}\},\\sigma^\{2\}I\)\}\(\\tilde\{v\}\_\{b\_\{i\}\}\),f\_\{\\mathcal\{N\}\(v^\{\\prime\}\_\{b\_\{i\}\},\\sigma^\{2\}I\)\}\(\\tilde\{v\}\_\{b\_\{i\}\}\)\\right\\\}dP\(\{\\tilde\{v\}\}\_\{b\_\{l\}\}\|v\_\{b\_\{l\}\}\)≥1−12​‖vbi′−vbi‖22σ2\\displaystyle\\geq 1\-\\frac\{1\}\{2\}\\sqrt\{\\frac\{\\\|v^\{\\prime\}\_\{b\_\{i\}\}\-v\_\{b\_\{i\}\}\\\|\_\{2\}^\{2\}\}\{\\sigma^\{2\}\}\}≥1−Bσ,\\displaystyle\\geq 1\-\\frac\{B\}\{\\sigma\},where the first inequality follows from[LemmaA\.1](https://arxiv.org/html/2606.04182#A1.Thmtheorem1)and[LemmaA\.2](https://arxiv.org/html/2606.04182#A4.EGx10), and the last inequality follows from that‖vbi′−vbi‖22=‖xt−xt′‖22≤B2\\\|v^\{\\prime\}\_\{b\_\{i\}\}\-v\_\{b\_\{i\}\}\\\|\_\{2\}^\{2\}=\\\|x\_\{t\}\-x^\{\\prime\}\_\{t\}\\\|\_\{2\}^\{2\}\\leq B^\{2\}, by[3\.2](https://arxiv.org/html/2606.04182#A4.EGx4)\. ∎

## Appendix CRegret Bounds

#### Notations\.

LetNht​\(s,a\)N^\{t\}\_\{h\}\(s,a\)andNht​\(s,a,s′\)N^\{t\}\_\{h\}\(s,a,s^\{\\prime\}\)be the number of visits to\(h,s,a\)\(h,s,a\)and\(h,s,a,s′\)\(h,s,a,s^\{\\prime\}\), respectively, right before the start of episodett\. LetRht​\(s,a\)R^\{t\}\_\{h\}\(s,a\)be the total rewards collected at\(h,s,a\)\(h,s,a\)right before the start of episodett\. LetN~ht​\(s,a\),N~ht​\(s,a,s′\),R~ht​\(s,a\)\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\),\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a,s^\{\\prime\}\),\{\\widetilde\{R\}\}^\{t\}\_\{h\}\(s,a\)be the noisy variants ofNht​\(s,a\),Nht​\(s,a,s′\),Rht​\(s,a\)N^\{t\}\_\{h\}\(s,a\),N^\{t\}\_\{h\}\(s,a,s^\{\\prime\}\),R^\{t\}\_\{h\}\(s,a\), respectively, obtained from the binary mechanism in[Algorithm3](https://arxiv.org/html/2606.04182#alg3)\.

Let us define the following quantities:

ℙ^ht​\(s′\|s,a\)\\displaystyle\{\\widehat\{\\mathbb\{P\}\}\}^\{t\}\_\{h\}\(s^\{\\prime\}\|s,a\):=Nht​\(s,a,s′\)Nht​\(s,a\),\\displaystyle:=\\frac\{N^\{t\}\_\{h\}\(s,a,s^\{\\prime\}\)\}\{N^\{t\}\_\{h\}\(s,a\)\},ℙ~ht​\(s′\|s,a\)\\displaystyle\{\\widetilde\{\\mathbb\{P\}\}\}^\{t\}\_\{h\}\(s^\{\\prime\}\|s,a\):=N~ht​\(s,a,s′\)N~ht​\(s,a\),\\displaystyle:=\\frac\{\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a,s^\{\\prime\}\)\}\{\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)\},r^ht​\(s,a\)\\displaystyle\\hat\{r\}\_\{h\}^\{t\}\(s,a\):=Rht​\(s,a\)Nht​\(s,a\),\\displaystyle:=\\frac\{R^\{t\}\_\{h\}\(s,a\)\}\{N^\{t\}\_\{h\}\(s,a\)\},r~ht​\(s,a\)\\displaystyle\{\\tilde\{r\}\}\_\{h\}^\{t\}\(s,a\):=R~ht​\(s,a\)N~ht​\(s,a\),\\displaystyle:=\\frac\{\{\\widetilde\{R\}\}^\{t\}\_\{h\}\(s,a\)\}\{\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)\},ϵapp​\(δ\)\\displaystyle\\epsilon\_\{\\text\{app\}\}\(\{\\delta\}\):=σ​ln⁡T​\(1\+2​log⁡\(2​T​\(S2​A​H\+2​S​A​H\)/δ\)\)\\displaystyle:=\\sigma\\ln T\\left\(1\+\\sqrt\{2\\log\(2T\(S^\{2\}AH\+2SAH\)/\\delta\)\}\\right\)Δht\\displaystyle\\Delta\_\{h\}^\{t\}:=V~ht​\(sht\)−Vhπ~t​\(sht\)\\displaystyle:=\{\\widetilde\{V\}\}^\{t\}\_\{h\}\(s^\{t\}\_\{h\}\)\-V^\{\{\\widetilde\{\\pi\}\}^\{t\}\}\_\{h\}\(s^\{t\}\_\{h\}\)ζht\\displaystyle\\zeta\_\{h\}^\{t\}:=\[ℙh​\(V~h\+1t−Vh\+1π~t\)\]​\(sht,aht\)−Δh\+1t\\displaystyle:=\[\\mathbb\{P\}\_\{h\}\(\{\\widetilde\{V\}\}^\{t\}\_\{h\+1\}\-V^\{\{\\widetilde\{\\pi\}\}^\{t\}\}\_\{h\+1\}\)\]\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\-\\Delta^\{t\}\_\{h\+1\}

### C\.1Basic Lemmas

###### Lemma C\.1\.

Fix anyδ\\delta\. With probability at least1−δ/41\-\\delta/4, for all\(t,h,s,a\)∈\[T\]×\[H\]×𝒮×𝒜\(t,h,s,a\)\\in\[T\]\\times\[H\]\\times\\mathcal\{S\}\\times\\mathcal\{A\}and allV:𝒮×𝒜→\[−H,H\]V:\\mathcal\{S\}\\times\\mathcal\{A\}\\rightarrow\[\-H,H\], we have

1. 1\.\|N~ht​\(s,a\)−Nht​\(s,a\)\|≤ϵapp​\(δ/4\)\|\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)\-N^\{t\}\_\{h\}\(s,a\)\|\\leq\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\),
2. 2\.\|r~ht​\(s,a\)−r^ht​\(s,a\)\|≤ϵapp​\(δ/4\)\|N~ht​\(s,a\)\|\|\{\\tilde\{r\}\}\_\{h\}^\{t\}\(s,a\)\-\\hat\{r\}^\{t\}\_\{h\}\(s,a\)\|\\leq\\frac\{\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)\}\{\|\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)\|\},
3. 3\.\|\[\(ℙ~ht−ℙ^h\)​V\]​\(s,a\)\|≤ϵapp​\(δ/4\)\|N~ht​\(s,a\)\|​H​\(S\+1\)\|\[\(\{\\widetilde\{\\mathbb\{P\}\}\}^\{t\}\_\{h\}\-\{\\widehat\{\\mathbb\{P\}\}\}\_\{h\}\)V\]\(s,a\)\|\\leq\\frac\{\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)\}\{\|\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)\|\}H\(S\+1\)\.

###### Proof of[LemmaC\.1](https://arxiv.org/html/2606.04182#A3.Thmtheorem1)\.

The proof directly follows from the fact that every noisy prefix sumN~ht​\(s,a\)\{\\widetilde\{N\}\}\_\{h\}^\{t\}\(s,a\)for a fixed\(h,s,a\)\(h,s,a\)is the result of perturbingNht​\(s,a\)N^\{t\}\_\{h\}\(s,a\)with at mostlog⁡T\\log Tindependent spherical noise sampled from𝒩​\(0,σ2\)\\mathcal\{N\}\(0,\\sigma^\{2\}\)\. The final form of the lemma simply follows from the concentration of spherical Gaussians \([LemmaA\.3](https://arxiv.org/html/2606.04182#A4.EGx11)\) and the union bound over \(at most\)2​T2Tnodes andH​S2​A\+2​H​S​AHS^\{2\}A\+2HSAdimensions in eachutu\_\{t\}in the tree\. ∎

###### Lemma C\.2\(Hoeffding’s inequality\)\.

Fix anyδ\>0\\delta\>0\. With probability at least1−δ/41\-\\delta/4, for all\(t,h,s,a\)∈\[T\]×\[H\]×𝒮×𝒜\(t,h,s,a\)\\in\[T\]\\times\[H\]\\times\\mathcal\{S\}\\times\\mathcal\{A\}, we have

\|r^ht​\(s,a\)−rh​\(s,a\)\|\\displaystyle\|\\hat\{r\}^\{t\}\_\{h\}\(s,a\)\-r\_\{h\}\(s,a\)\|≤ln⁡\(8​S​A​H​T/δ\)2​Nht​\(s,a\),\\displaystyle\\leq\\sqrt\{\\frac\{\\ln\(8SAHT/\\delta\)\}\{2N^\{t\}\_\{h\}\(s,a\)\}\},\[\(ℙ^ht−ℙh\)​Vh\+1∗\]​\(s,a\)\\displaystyle\[\(\{\\widehat\{\\mathbb\{P\}\}\}\_\{h\}^\{t\}\-\\mathbb\{P\}\_\{h\}\)V^\{\*\}\_\{h\+1\}\]\(s,a\)≤H​ln⁡\(8​S​A​H​T/δ\)2​Nht​\(s,a\)\.\\displaystyle\\leq H\\sqrt\{\\frac\{\\ln\(8SAHT/\\delta\)\}\{2N^\{t\}\_\{h\}\(s,a\)\}\}\.

###### Lemma C\.3\.

Fix anyδ\>0\\delta\>0\. With probability at least1−δ/41\-\\delta/4, for all\(t,h,s,a,s′\)\(t,h,s,a,s^\{\\prime\}\):

ℙ^ht​\(s′\|s,a\)−ℙh​\(s′\|s,a\)≤\(8​H\+13\)​ln⁡\(4​T​H​S2​A/δ\)Nht​\(s,a\)\+1H​ℙh​\(s′\|s,a\)\.\\displaystyle\{\\widehat\{\\mathbb\{P\}\}\}\_\{h\}^\{t\}\(s^\{\\prime\}\|s,a\)\-\\mathbb\{P\}\_\{h\}\(s^\{\\prime\}\|s,a\)\\leq\(8H\+\\frac\{1\}\{3\}\)\\frac\{\\ln\(4THS^\{2\}A/\\delta\)\}\{N^\{t\}\_\{h\}\(s,a\)\}\+\\frac\{1\}\{H\}\\mathbb\{P\}\_\{h\}\(s^\{\\prime\}\|s,a\)\.

###### Proof of[LemmaC\.3](https://arxiv.org/html/2606.04182#A4.EGx26)\.

By Bernstein’s inequality, for any fixedt,h,s,a,s′,δt,h,s,a,s^\{\\prime\},\\delta, with probability at least1−δ1\-\\delta, we have

ℙ^ht​\(s′\|s,a\)−ℙh​\(s′\|s,a\)\\displaystyle\{\\widehat\{\\mathbb\{P\}\}\}\_\{h\}^\{t\}\(s^\{\\prime\}\|s,a\)\-\\mathbb\{P\}\_\{h\}\(s^\{\\prime\}\|s,a\)<ln⁡\(1/δ\)3​Nht​\(s,a\)\+2​ℙh​\(s′\|s,a\)​ln⁡\(1/δ\)Nht​\(s,a\)\\displaystyle<\\frac\{\\ln\(1/\\delta\)\}\{3N^\{t\}\_\{h\}\(s,a\)\}\+\\sqrt\{\\frac\{2\\mathbb\{P\}\_\{h\}\(s^\{\\prime\}\|s,a\)\\ln\(1/\\delta\)\}\{N^\{t\}\_\{h\}\(s,a\)\}\}≤\(8​H\+13\)​ln⁡\(1/δ\)Nht​\(s,a\)\+1H​ℙh​\(s′\|s,a\),\\displaystyle\\leq\(8H\+\\frac\{1\}\{3\}\)\\frac\{\\ln\(1/\\delta\)\}\{N^\{t\}\_\{h\}\(s,a\)\}\+\\frac\{1\}\{H\}\\mathbb\{P\}\_\{h\}\(s^\{\\prime\}\|s,a\),where the last inequality uses Cauchy\-Schwartz inequality\. Using the union bound and rescalingδ\\deltacompletes our proof\. ∎

###### Lemma C\.4\.

With probability at least1−δ/41\-\\delta/4, for allh∈\[H\]h\\in\[H\], we have

∑t=1Tζht≤H​32​T​ln⁡\(4​H/δ\)\.\\displaystyle\\sum\_\{t=1\}^\{T\}\\zeta^\{t\}\_\{h\}\\leq H\\sqrt\{32T\\ln\(4H/\\delta\)\}\.

###### Proof of[LemmaC\.4](https://arxiv.org/html/2606.04182#A4.EGx28)\.

For any fixedhh,\{ζht\}t∈\[T\]\\\{\\zeta^\{t\}\_\{h\}\\\}\_\{t\\in\[T\]\}is a martingale difference sequence\. Applying Azuma inequality completes our proof\. ∎

###### Lemma C\.5\.

LetI2=\{t∈\[T\]:N~ht​\(sht,aht\)≥2​ϵapp​\(δ/4\),∀h∈\[H\]\}I\_\{2\}=\\\{t\\in\[T\]:\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\\geq 2\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\),\\forall h\\in\[H\]\\\}andI1=\[T\]\\I2I\_\{1\}=\[T\]\\backslash I\_\{2\}\. If the inequalities in[LemmaC\.1](https://arxiv.org/html/2606.04182#A3.Thmtheorem1)hold, we have

\|I1\|≤3​H​S​A​ϵapp​\(δ/4\)\.\\displaystyle\|I\_\{1\}\|\\leq 3HSA\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)\.

###### Proof of[LemmaC\.5](https://arxiv.org/html/2606.04182#A4.EGx29)\.

Note that

I1=\{t∈\[T\]:∃h∈\[H\],N~ht​\(sht,aht\)<2​ϵapp​\(δ/4\)\}\.\\displaystyle I\_\{1\}=\\\{t\\in\[T\]:\\exists h\\in\[H\],\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)<2\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)\\\}\.Let us define

I1′=\{t∈\[T\]:∃h∈\[H\],Nht​\(sht,aht\)<3​ϵapp​\(δ/4\)\}\.\\displaystyle I^\{\\prime\}\_\{1\}=\\\{t\\in\[T\]:\\exists h\\in\[H\],N^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)<3\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)\\\}\.If the inequalities in[LemmaC\.1](https://arxiv.org/html/2606.04182#A3.Thmtheorem1)hold, thenI1⊆I1′I\_\{1\}\\subseteq I\_\{1\}^\{\\prime\}\. Thus, it suffices to bound\|I1′\|\|I^\{\\prime\}\_\{1\}\|\. Eacht∈I1′t\\in I^\{\\prime\}\_\{1\}must create at least one mapping to\[H\]×𝒮×𝒜\[H\]\\times\\mathcal\{S\}\\times\\mathcal\{A\}via\(h,s,a\)\(h,s,a\)such thatNht​\(s,a\)<3​ϵapp​\(δ/4\)N^\{t\}\_\{h\}\(s,a\)<3\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)and\(s,a\)=\(sht,aht\)\(s,a\)=\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\. For any\(h,s,a\)\(h,s,a\), there are at most3​ϵapp​\(δ/4\)3\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)elements inI1′I\_\{1\}^\{\\prime\}that create a mapping to\(h,s,a\)\(h,s,a\), because otherwise\(h,s,a\)\(h,s,a\)must be visited at least3​ϵapp​\(δ/4\)3\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)by somet∈I1′t\\in I^\{\\prime\}\_\{1\}, leading to a contradiction\. Overall, the number of elements inI1′I^\{\\prime\}\_\{1\}must be at most3​ϵapp​\(δ/4\)​H​S​A3\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)HSA\. ∎

### C\.2Proof of the Regret Bound

###### Lemma C\.7\(Optimism\)\.

Fix anyδ\>0\\delta\>0\. If we set the bonus function as follows:

b​\(n~\)=\(H\+1\)​ln⁡\(8​S​A​H​T/δ\)2​\(n~−ϵapp​\(δ/4\)\)\+ϵapp​\(δ/4\)n~​\(1\+2​H​\(S\+1\)\),\\displaystyle b\(\\tilde\{n\}\)=\(H\+1\)\\sqrt\{\\frac\{\\ln\(8SAHT/\\delta\)\}\{2\(\\tilde\{n\}\-\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)\)\}\}\+\\frac\{\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)\}\{\\tilde\{n\}\}\(1\+2H\(\\sqrt\{S\}\+1\)\),then, with probability at least1−δ/21\-\\delta/2, for all\(t,h,s,a\)∈\[T\]×\[H\]×𝒮×𝒜\(t,h,s,a\)\\in\[T\]\\times\[H\]\\times\\mathcal\{S\}\\times\\mathcal\{A\}, we have

Q~ht​\(s,a\)≥Qh∗​\(s,a\)​and​V~ht​\(s\)≥Vh∗​\(s\),∀\(h,s,a\)\.\\displaystyle\{\\widetilde\{Q\}\}\_\{h\}^\{t\}\(s,a\)\\geq Q^\{\*\}\_\{h\}\(s,a\)\\text\{ and \}\{\\widetilde\{V\}\}\_\{h\}^\{t\}\(s\)\\geq V^\{\*\}\_\{h\}\(s\),\\forall\(h,s,a\)\.\(5\)

###### Proof of[LemmaC\.7](https://arxiv.org/html/2606.04182#A4.EGx33)\.

We use induction to prove the lemma\. For a fixed episodett, considerh=H\+1,H,…,1h=H\+1,H,\\ldots,1\. The inequalities hold forh=H\+1h=H\+1\. AssumeV~h\+1t​\(s\)≥Vh\+1∗​\(s\)\{\\widetilde\{V\}\}\_\{h\+1\}^\{t\}\(s\)\\geq V^\{\*\}\_\{h\+1\}\(s\)for allssand somehh\. If the algorithm has never visited\(h,s,a\)\(h,s,a\)prior to episodett, thenQ~ht​\(s,a\)\{\\widetilde\{Q\}\}^\{t\}\_\{h\}\(s,a\)has never got updated; thus,Q~ht​\(s,a\)=H≥Qh∗​\(s,a\)\{\\widetilde\{Q\}\}^\{t\}\_\{h\}\(s,a\)=H\\geq Q^\{\*\}\_\{h\}\(s,a\)\. Otherwise, we have

Q~ht​\(s,a\)=\{min⁡\{H,r~h​\(s,a\)\+\(ℙ~ht​V~h\+1t\)​\(s,a\)\+b​\(N~ht​\(s,a\)\)\}if​N~ht​\(s,a\)≥2​ϵapp​\(δ/4\)Hif​N~ht​\(s,a\)<2​ϵapp​\(δ/4\)\.\\displaystyle\{\\widetilde\{Q\}\}^\{t\}\_\{h\}\(s,a\)=\\begin\{cases\}\\min\\left\\\{H,\{\\tilde\{r\}\}\_\{h\}\(s,a\)\+\(\{\\widetilde\{\\mathbb\{P\}\}\}\_\{h\}^\{t\}\{\\widetilde\{V\}\}\_\{h\+1\}^\{t\}\)\(s,a\)\+b\(\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)\)\\right\\\}&\\text\{ if \}\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)\\geq 2\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)\\\\ H&\\text\{ if \}\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)<2\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)\.\\end\{cases\}IfN~ht​\(s,a\)<2​ϵapp​\(δ/4\)\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)<2\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)orN~ht​\(s,a\)≥2​ϵapp​\(δ/4\)\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)\\geq 2\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)and the minimum isHH, thenQ~ht​\(s,a\)=H≥Qh∗​\(s,a\)\{\\widetilde\{Q\}\}^\{t\}\_\{h\}\(s,a\)=H\\geq Q^\{\*\}\_\{h\}\(s,a\)\. We only need to consider the caseN~ht​\(s,a\)≥2​ϵapp​\(δ/4\)\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)\\geq 2\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)and the minimum is notHH\. Then we have

Q~ht​\(s,a\)−Qh∗​\(s,a\)\\displaystyle\{\\widetilde\{Q\}\}^\{t\}\_\{h\}\(s,a\)\-Q^\{\*\}\_\{h\}\(s,a\)=r~h​\(s,a\)−rh​\(s,a\)\+\(ℙ~ht​V~h\+1t\)​\(s,a\)−\(ℙh​Vh\+1∗\)​\(s,a\)\+b​\(N~ht​\(s,a\)\)\\displaystyle=\{\\tilde\{r\}\}\_\{h\}\(s,a\)\-r\_\{h\}\(s,a\)\+\(\{\\widetilde\{\\mathbb\{P\}\}\}\_\{h\}^\{t\}\{\\widetilde\{V\}\}\_\{h\+1\}^\{t\}\)\(s,a\)\-\(\\mathbb\{P\}\_\{h\}V^\{\*\}\_\{h\+1\}\)\(s,a\)\+b\(\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)\)=r~ht​\(s,a\)−rh​\(s,a\)\+\[\(ℙ~ht−ℙh\)​Vh\+1∗\]​\(s,a\)\+ℙ~ht​\(V~h\+1t−Vh\+1∗\)\+b​\(N~ht​\(s,a\)\)\\displaystyle=\{\\tilde\{r\}\}^\{t\}\_\{h\}\(s,a\)\-r\_\{h\}\(s,a\)\+\[\(\{\\widetilde\{\\mathbb\{P\}\}\}\_\{h\}^\{t\}\-\\mathbb\{P\}\_\{h\}\)V^\{\*\}\_\{h\+1\}\]\(s,a\)\+\{\\widetilde\{\\mathbb\{P\}\}\}\_\{h\}^\{t\}\(\{\\widetilde\{V\}\}\_\{h\+1\}^\{t\}\-V^\{\*\}\_\{h\+1\}\)\+b\(\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)\)=r^ht​\(s,a\)−rh​\(s,a\)\+\[\(ℙ^ht−ℙh\)​Vh\+1∗\]​\(s,a\)\+ℙ^ht​\(V~h\+1t−Vh\+1∗\)\\displaystyle=\\hat\{r\}^\{t\}\_\{h\}\(s,a\)\-r\_\{h\}\(s,a\)\+\[\(\{\\widehat\{\\mathbb\{P\}\}\}\_\{h\}^\{t\}\-\\mathbb\{P\}\_\{h\}\)V^\{\*\}\_\{h\+1\}\]\(s,a\)\+\{\\widehat\{\\mathbb\{P\}\}\}\_\{h\}^\{t\}\(\{\\widetilde\{V\}\}\_\{h\+1\}^\{t\}\-V^\{\*\}\_\{h\+1\}\)\+r~ht​\(s,a\)−r^ht​\(s,a\)\+\[\(ℙ~ht−ℙ^ht\)​Vh\+1∗\]​\(s,a\)\+\(ℙ~ht−ℙ^ht\)​\(V~h\+1t−Vh\+1∗\)\+b​\(N~ht​\(s,a\)\)\\displaystyle\+\{\\tilde\{r\}\}^\{t\}\_\{h\}\(s,a\)\-\\hat\{r\}^\{t\}\_\{h\}\(s,a\)\+\[\(\{\\widetilde\{\\mathbb\{P\}\}\}\_\{h\}^\{t\}\-\{\\widehat\{\\mathbb\{P\}\}\}^\{t\}\_\{h\}\)V^\{\*\}\_\{h\+1\}\]\(s,a\)\+\(\{\\widetilde\{\\mathbb\{P\}\}\}\_\{h\}^\{t\}\-\{\\widehat\{\\mathbb\{P\}\}\}\_\{h\}^\{t\}\)\(\{\\widetilde\{V\}\}\_\{h\+1\}^\{t\}\-V^\{\*\}\_\{h\+1\}\)\+b\(\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)\)≥−\(H\+1\)​ln⁡\(8​S​A​H​T/δ\)2​Nht​\(s,a\)−ϵapp​\(δ/4\)\|N~ht​\(s,a\)\|​\(1\+2​H​\(S\+1\)\)\+b​\(N~ht​\(s,a\)\)\\displaystyle\\geq\-\(H\+1\)\\sqrt\{\\frac\{\\ln\(8SAHT/\\delta\)\}\{2N^\{t\}\_\{h\}\(s,a\)\}\}\-\\frac\{\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)\}\{\|\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)\|\}\(1\+2H\(S\+1\)\)\+b\(\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)\)≥0\\displaystyle\\geq 0where the first inequality is due to[LemmaC\.2](https://arxiv.org/html/2606.04182#A4.EGx25)and[LemmaC\.1](https://arxiv.org/html/2606.04182#A3.Thmtheorem1), and the last inequality is due to the definition of the bonus function\. and[LemmaC\.1](https://arxiv.org/html/2606.04182#A3.Thmtheorem1)and the conditionN~ht​\(s,a\)≥2​ϵapp​\(δ/4\)\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)\\geq 2\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)\. ∎

#### Regret analysis\.

We are now ready to give a full proof for part 3 of[Theorem4\.1](https://arxiv.org/html/2606.04182#S4.Thmtheorem1)\.

###### Proof of part 3 of[Theorem4\.1](https://arxiv.org/html/2606.04182#S4.Thmtheorem1)\.

LetEEbe the event that,[Equation5](https://arxiv.org/html/2606.04182#A3.E5)and all the inequalities in[LemmaC\.1](https://arxiv.org/html/2606.04182#A3.Thmtheorem1),[LemmaC\.2](https://arxiv.org/html/2606.04182#A4.EGx25), and[LemmaC\.3](https://arxiv.org/html/2606.04182#A4.EGx26)hold simultaneously\. We havePr⁡\(E\)≥1−δ\\Pr\(E\)\\geq 1\-\\delta\. LetI2=\{t∈\[T\]:N~ht​\(sht,aht\)≥2​ϵapp​\(δ/4\),∀h∈\[H\]\}I\_\{2\}=\\\{t\\in\[T\]:\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\\geq 2\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\),\\forall h\\in\[H\]\\\}andI1=\[T\]\\I2I\_\{1\}=\[T\]\\backslash I\_\{2\}\.

Under eventEE, we have

Regret​\(T\)=∑t=1TV1∗​\(s1t\)−V1π~t​\(s1t\)≤∑t=1TV~1t​\(s1t\)−V1π~t​\(s1t\)=∑t=1TΔ1t,\\displaystyle\\text\{Regret\}\(T\)=\\sum\_\{t=1\}^\{T\}V^\{\*\}\_\{1\}\(s\_\{1\}^\{t\}\)\-V^\{\{\\widetilde\{\\pi\}\}^\{t\}\}\_\{1\}\(s\_\{1\}^\{t\}\)\\leq\\sum\_\{t=1\}^\{T\}\{\\widetilde\{V\}\}^\{t\}\_\{1\}\(s\_\{1\}^\{t\}\)\-V^\{\{\\widetilde\{\\pi\}\}^\{t\}\}\_\{1\}\(s\_\{1\}^\{t\}\)=\\sum\_\{t=1\}^\{T\}\\Delta\_\{1\}^\{t\},due to[LemmaC\.7](https://arxiv.org/html/2606.04182#A4.EGx33)\.

Observe that actionaht=π~ht​\(sht\)=arg​maxa∈𝒜⁡Q~ht​\(sht,a\)a^\{t\}\_\{h\}=\{\\widetilde\{\\pi\}\}^\{t\}\_\{h\}\(s^\{t\}\_\{h\}\)=\{\\text\{arg\}\\max\}\_\{a\\in\\mathcal\{A\}\}\{\\widetilde\{Q\}\}^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a\)\. Thus,

Δht=V~ht​\(sht\)−Vhπ~t​\(sht\)=Q~ht​\(sht,aht\)−Qhπ~t​\(sht,aht\)\.\\displaystyle\\Delta\_\{h\}^\{t\}=\{\\widetilde\{V\}\}^\{t\}\_\{h\}\(s^\{t\}\_\{h\}\)\-V^\{\{\\widetilde\{\\pi\}\}^\{t\}\}\_\{h\}\(s^\{t\}\_\{h\}\)=\{\\widetilde\{Q\}\}^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\-Q^\{\{\\widetilde\{\\pi\}\}^\{t\}\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\.
For anyt∈I2t\\in I\_\{2\}, we have

Q~h​\(st,aht\)−Qhπ~t​\(sht,aht\)≤r~ht​\(sht,aht\)−rh​\(sht,aht\)\+\(ℙ~ht​V~h\+1t−ℙh​Vh\+1π~t\)​\(sht,aht\)\+bht​\(N~ht​\(sht,aht\)\)\.\\displaystyle\{\\widetilde\{Q\}\}\_\{h\}\(s^\{t\},a^\{t\}\_\{h\}\)\-Q^\{\{\\widetilde\{\\pi\}\}^\{t\}\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\\leq\{\\tilde\{r\}\}\_\{h\}^\{t\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\-r\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\+\(\{\\widetilde\{\\mathbb\{P\}\}\}\_\{h\}^\{t\}\{\\widetilde\{V\}\}^\{t\}\_\{h\+1\}\-\\mathbb\{P\}\_\{h\}V^\{\{\\widetilde\{\\pi\}\}^\{t\}\}\_\{h\+1\}\)\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\+b^\{t\}\_\{h\}\(\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\)\.
Under eventEE, for allt,ht,h, we have

\(ℙ~ht​V~h\+1t−ℙh​Vh\+1π~t\)​\(sht,aht\)\\displaystyle\(\{\\widetilde\{\\mathbb\{P\}\}\}\_\{h\}^\{t\}\{\\widetilde\{V\}\}^\{t\}\_\{h\+1\}\-\\mathbb\{P\}\_\{h\}V^\{\{\\widetilde\{\\pi\}\}^\{t\}\}\_\{h\+1\}\)\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)=\[\(ℙ~ht−ℙh\)​Vh\+1∗\]​\(sht,aht\)\+\[\(ℙ~ht−ℙh\)​\(V~h\+1t−Vh\+1∗\)\]​\(sht,aht\)\+\[ℙh​\(V~h\+1t−Vh\+1π~t\)\]​\(sht,aht\)\\displaystyle=\[\(\{\\widetilde\{\\mathbb\{P\}\}\}^\{t\}\_\{h\}\-\\mathbb\{P\}\_\{h\}\)V^\{\*\}\_\{h\+1\}\]\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\+\[\(\{\\widetilde\{\\mathbb\{P\}\}\}^\{t\}\_\{h\}\-\\mathbb\{P\}\_\{h\}\)\(\{\\widetilde\{V\}\}\_\{h\+1\}^\{t\}\-V^\{\*\}\_\{h\+1\}\)\]\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\+\[\\mathbb\{P\}\_\{h\}\(\{\\widetilde\{V\}\}^\{t\}\_\{h\+1\}\-V^\{\{\\widetilde\{\\pi\}\}^\{t\}\}\_\{h\+1\}\)\]\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)=\[\(ℙ~ht−ℙh\)​Vh\+1∗\]​\(sht,aht\)\+\[\(ℙ~ht−ℙ^h\)​\(V~h\+1t−Vh\+1∗\)\]​\(sht,aht\)\\displaystyle=\[\(\{\\widetilde\{\\mathbb\{P\}\}\}^\{t\}\_\{h\}\-\\mathbb\{P\}\_\{h\}\)V^\{\*\}\_\{h\+1\}\]\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\+\[\(\{\\widetilde\{\\mathbb\{P\}\}\}^\{t\}\_\{h\}\-\{\\widehat\{\\mathbb\{P\}\}\}\_\{h\}\)\(\{\\widetilde\{V\}\}\_\{h\+1\}^\{t\}\-V^\{\*\}\_\{h\+1\}\)\]\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\+\[\(ℙ^ht−ℙh\)​\(V~h\+1t−Vh\+1∗\)\]​\(sht,aht\)\+\[ℙh​\(V~h\+1t−Vh\+1π~t\)\]​\(sht,aht\)\\displaystyle\+\[\(\{\\widehat\{\\mathbb\{P\}\}\}^\{t\}\_\{h\}\-\\mathbb\{P\}\_\{h\}\)\(\{\\widetilde\{V\}\}\_\{h\+1\}^\{t\}\-V^\{\*\}\_\{h\+1\}\)\]\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\+\[\\mathbb\{P\}\_\{h\}\(\{\\widetilde\{V\}\}^\{t\}\_\{h\+1\}\-V^\{\{\\widetilde\{\\pi\}\}^\{t\}\}\_\{h\+1\}\)\]\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)≤H​ln⁡\(8​S​A​H​T/δ\)2​Nht​\(s,a\)\+ϵapp​\(δ/4\)N~ht​\(s,a\)​H​\(S\+1\)\\displaystyle\\leq H\\sqrt\{\\frac\{\\ln\(8SAHT/\\delta\)\}\{2N^\{t\}\_\{h\}\(s,a\)\}\}\+\\frac\{\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)\}\{\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)\}H\(S\+1\)\+\[\(ℙ^ht−ℙh\)​\(V~h\+1t−Vh\+1∗\)\]​\(sht,aht\)\+\[ℙh​\(V~h\+1t−Vh\+1π~t\)\]​\(sht,aht\)\\displaystyle\+\[\(\{\\widehat\{\\mathbb\{P\}\}\}^\{t\}\_\{h\}\-\\mathbb\{P\}\_\{h\}\)\(\{\\widetilde\{V\}\}\_\{h\+1\}^\{t\}\-V^\{\*\}\_\{h\+1\}\)\]\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\+\[\\mathbb\{P\}\_\{h\}\(\{\\widetilde\{V\}\}^\{t\}\_\{h\+1\}\-V^\{\{\\widetilde\{\\pi\}\}^\{t\}\}\_\{h\+1\}\)\]\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)≤H​ln⁡\(8​S​A​H​T/δ\)2​Nht​\(sht,aht\)\+ϵapp​\(δ/4\)N~ht​\(s,a\)​H​\(S\+1\)\\displaystyle\\leq H\\sqrt\{\\frac\{\\ln\(8SAHT/\\delta\)\}\{2N^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\}\}\+\\frac\{\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)\}\{\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s,a\)\}H\(S\+1\)\+S​H​\(8​H\+13\)​ln⁡\(T​H​S2​A/δ\)Nht​\(sht,aht\)\+1H​\[ℙh​\(V~h\+1t−Vh\+1∗\)\]​\(sht,aht\)\+\[ℙh​\(V~h\+1t−Vh\+1π~t\)\]​\(sht,aht\)\\displaystyle\+SH\(8H\+\\frac\{1\}\{3\}\)\\frac\{\\ln\(THS^\{2\}A/\\delta\)\}\{N^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\}\+\\frac\{1\}\{H\}\[\\mathbb\{P\}\_\{h\}\(\{\\widetilde\{V\}\}^\{t\}\_\{h\+1\}\-V^\{\*\}\_\{h\+1\}\)\]\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\+\[\\mathbb\{P\}\_\{h\}\(\{\\widetilde\{V\}\}^\{t\}\_\{h\+1\}\-V^\{\{\\widetilde\{\\pi\}\}^\{t\}\}\_\{h\+1\}\)\]\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)≤H​ln⁡\(8​S​A​H​T/δ\)2​Nht​\(s,a\)\+ϵapp​\(δ/4\)N~ht​\(sht,aht\)​H​\(S\+1\)\\displaystyle\\leq H\\sqrt\{\\frac\{\\ln\(8SAHT/\\delta\)\}\{2N^\{t\}\_\{h\}\(s,a\)\}\}\+\\frac\{\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)\}\{\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\}H\(S\+1\)\+S​H​\(8​H\+13\)​ln⁡\(8​T​H​S2​A/δ\)Nht​\(sht,aht\)\+\(1\+1H\)​\[ℙh​\(V~h\+1t−Vh\+1π~\)\]​\(sht,aht\)\\displaystyle\+SH\(8H\+\\frac\{1\}\{3\}\)\\frac\{\\ln\(8THS^\{2\}A/\\delta\)\}\{N^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\}\+\(1\+\\frac\{1\}\{H\}\)\[\\mathbb\{P\}\_\{h\}\(\{\\widetilde\{V\}\}^\{t\}\_\{h\+1\}\-V^\{\{\\widetilde\{\\pi\}\}\}\_\{h\+1\}\)\]\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)where the first inequality is due to[LemmaC\.2](https://arxiv.org/html/2606.04182#A4.EGx25)and the part 3 of[LemmaC\.1](https://arxiv.org/html/2606.04182#A3.Thmtheorem1), the second inequality is due toV~h\+1t≥Vh\+1∗\{\\widetilde\{V\}\}^\{t\}\_\{h\+1\}\\geq V^\{\*\}\_\{h\+1\}\([LemmaC\.7](https://arxiv.org/html/2606.04182#A4.EGx33)\) and[LemmaC\.3](https://arxiv.org/html/2606.04182#A4.EGx26), and the last inequality usesVh\+1∗≥Vh\+1π~tV^\{\*\}\_\{h\+1\}\\geq V^\{\{\\widetilde\{\\pi\}\}^\{t\}\}\_\{h\+1\}\.

In addition, under eventEE, for allt,ht,h, we have

r~ht​\(sht,aht\)−rh​\(sht,aht\)≤H​ln⁡\(8​S​A​H​T/δ\)2​Nht​\(sht,aht\)\+ϵapp​\(δ/4\)\|N~ht​\(sht,aht\)\|\.\\displaystyle\{\\tilde\{r\}\}\_\{h\}^\{t\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\-r\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\\leq H\\sqrt\{\\frac\{\\ln\(8SAHT/\\delta\)\}\{2N^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\}\}\+\\frac\{\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)\}\{\|\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\|\}\.
Overall, we have that, under eventEE, for all\(t,h\)∈I2×\[H\]\(t,h\)\\in I\_\{2\}\\times\[H\],

Δht\\displaystyle\\Delta^\{t\}\_\{h\}≤2​H​ln⁡\(8​S​A​H​T/δ\)2​Nht​\(sht,aht\)\+ϵapp​\(δ/4\)N~ht​\(sht,aht\)​\(1\+H​\(S\+1\)\)\+S​H​\(8​H\+13\)​ln⁡\(8​T​H​S2​A/δ\)Nht​\(sht,aht\)\+bht​\(N~ht​\(sht,aht\)\)⏟ξht\\displaystyle\\leq\\underbrace\{2H\\sqrt\{\\frac\{\\ln\(8SAHT/\\delta\)\}\{2N^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\}\}\+\\frac\{\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)\}\{\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\}\(1\+H\(S\+1\)\)\+SH\(8H\+\\frac\{1\}\{3\}\)\\frac\{\\ln\(8THS^\{2\}A/\\delta\)\}\{N^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\}\+b^\{t\}\_\{h\}\(\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\)\}\_\{\\xi^\{t\}\_\{h\}\}\+\(1\+1H\)​\(ζht\+Δh\+1t\)\.\\displaystyle\+\(1\+\\frac\{1\}\{H\}\)\(\\zeta^\{t\}\_\{h\}\+\\Delta^\{t\}\_\{h\+1\}\)\.By recursion overh=1,…,Hh=1,\\ldots,H, the above inequality implies that

Δ1t\\displaystyle\\Delta^\{t\}\_\{1\}≤∑h=1H\(1\+1H\)h−1​ξht\+e​∑h=1H\(1\+1H\)h​ζht\\displaystyle\\leq\\sum\_\{h=1\}^\{H\}\(1\+\\frac\{1\}\{H\}\)^\{h\-1\}\\xi^\{t\}\_\{h\}\+e\\sum\_\{h=1\}^\{H\}\(1\+\\frac\{1\}\{H\}\)^\{h\}\\zeta^\{t\}\_\{h\}≤e​∑h=1Hξht\+e​∑h=1Hζht\.\\displaystyle\\leq e\\sum\_\{h=1\}^\{H\}\\xi^\{t\}\_\{h\}\+e\\sum\_\{h=1\}^\{H\}\\zeta^\{t\}\_\{h\}\.
Thus, under eventEE, we have

∑t∈I2Δ1t≤e​∑t∈I2∑h=1Hξht\+e​∑t∈I2∑h=1Hζht\.\\displaystyle\\sum\_\{t\\in I\_\{2\}\}\\Delta^\{t\}\_\{1\}\\leq e\\sum\_\{t\\in I\_\{2\}\}\\sum\_\{h=1\}^\{H\}\\xi^\{t\}\_\{h\}\+e\\sum\_\{t\\in I\_\{2\}\}\\sum\_\{h=1\}^\{H\}\\zeta^\{t\}\_\{h\}\.\(6\)Note that we have the following inequalities:

∑t∈I2∑h1Nht​\(sht,aht\)\\displaystyle\\sum\_\{t\\in I\_\{2\}\}\\sum\_\{h\}\\frac\{1\}\{N^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\}≤∑t∈\[T\]∑h1Nht​\(sht,aht\)=∑\(h,s,a\)∑i=1NhT​\(s,a\)1i≤∑\(h,s,a\)\(1\+ln⁡\(NhT​\(s,a\)\)\)\\displaystyle\\leq\\sum\_\{t\\in\[T\]\}\\sum\_\{h\}\\frac\{1\}\{N^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\}=\\sum\_\{\(h,s,a\)\}\\sum\_\{i=1\}^\{N^\{T\}\_\{h\}\(s,a\)\}\\frac\{1\}\{i\}\\leq\\sum\_\{\(h,s,a\)\}\(1\+\\ln\(N^\{T\}\_\{h\}\(s,a\)\)\)≤H​S​A​\(1\+ln⁡\(T/S​A\)\),\\displaystyle\\leq HSA\(1\+\\ln\(T/SA\)\),and

∑t∈I2∑h1Nht​\(sht,aht\)\\displaystyle\\sum\_\{t\\in I\_\{2\}\}\\sum\_\{h\}\\frac\{1\}\{\\sqrt\{N^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\}\}≤∑t∈\[T\]∑h1Nht​\(sht,aht\)=∑\(h,s,a\)∑i=1NhT​\(s,a\)1i\\displaystyle\\leq\\sum\_\{t\\in\[T\]\}\\sum\_\{h\}\\frac\{1\}\{\\sqrt\{N^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\}\}=\\sum\_\{\(h,s,a\)\}\\sum\_\{i=1\}^\{N^\{T\}\_\{h\}\(s,a\)\}\\frac\{1\}\{\\sqrt\{i\}\}≤2​∑\(h,s,a\)NhT​\(s,a\)≤2​H​S​A​T​H\.\\displaystyle\\leq 2\\sum\_\{\(h,s,a\)\}\\sqrt\{N^\{T\}\_\{h\}\(s,a\)\}\\leq 2\\sqrt\{HSATH\}\.
Denoteϵ:=ϵapp​\(δ/4\)\{\\epsilon\}:=\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\)for simplicity\. Under eventEE, we have

∑t∈I2∑h1N~ht​\(sht,aht\)\\displaystyle\\sum\_\{t\\in I\_\{2\}\}\\sum\_\{h\}\\frac\{1\}\{\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\}≤∑t∈I2∑h1Nht​\(sht,aht\)−ϵ≤∑t∈\[T\]∑h1Nht​\(sht,aht\)\\displaystyle\\leq\\sum\_\{t\\in I\_\{2\}\}\\sum\_\{h\}\\frac\{1\}\{N^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\-\\epsilon\}\\leq\\sum\_\{t\\in\[T\]\}\\sum\_\{h\}\\frac\{1\}\{N^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\}≤H​S​A​\(1\+ln⁡\(T/S​A\)\),\\displaystyle\\leq HSA\(1\+\\ln\(T/SA\)\),and

∑t∈I2∑h1N~ht​\(sht,aht\)−ϵ\\displaystyle\\sum\_\{t\\in I\_\{2\}\}\\sum\_\{h\}\\frac\{1\}\{\\sqrt\{\{\\widetilde\{N\}\}^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\-\\epsilon\}\}≤∑t∈I2∑h1Nht​\(sht,aht\)−2​ϵ≤∑t∈\[T\]∑h1Nht​\(sht,aht\)\\displaystyle\\leq\\sum\_\{t\\in I\_\{2\}\}\\sum\_\{h\}\\frac\{1\}\{\\sqrt\{N^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\-2\\epsilon\}\}\\leq\\sum\_\{t\\in\[T\]\}\\sum\_\{h\}\\frac\{1\}\{\\sqrt\{N^\{t\}\_\{h\}\(s^\{t\}\_\{h\},a^\{t\}\_\{h\}\)\}\}≤2​H​S​A​T\.\\displaystyle\\leq 2H\\sqrt\{SAT\}\.Plugging these inequalities and[LemmaC\.4](https://arxiv.org/html/2606.04182#A4.EGx28)into[Equation6](https://arxiv.org/html/2606.04182#A3.E6), we have that, under eventEE,

∑t∈I2Δ1t\\displaystyle\\sum\_\{t\\in I\_\{2\}\}\\Delta^\{t\}\_\{1\}≤10​H2​S​A​T​ln⁡\(8​S​A​H​T/δ\)\+9​H3​S2​A​ln⁡\(T​H​S2​A/δ\)​ln⁡\(e​T/S​A\)\+8​ϵ​H2​S2​A​ln⁡\(e​T/S​A\)\.\\displaystyle\\leq 10H^\{2\}\\sqrt\{SAT\\ln\(8SAHT/\\delta\)\}\+9H^\{3\}S^\{2\}A\\ln\(THS^\{2\}A/\\delta\)\\ln\(eT/SA\)\+8\\epsilon H^\{2\}S^\{2\}A\\ln\(eT/SA\)\.\(7\)
Finally, under eventEE, we also have

∑t∈I1Δ1t≤3​H​S​A​H​ϵapp​\(δ/4\),\\displaystyle\\sum\_\{t\\in I\_\{1\}\}\\Delta\_\{1\}^\{t\}\\leq 3HSAH\\epsilon\_\{\\text\{app\}\}\(\{\\delta/4\}\),\(8\)due to[LemmaC\.5](https://arxiv.org/html/2606.04182#A4.EGx29)\.

Using[Equation7](https://arxiv.org/html/2606.04182#A3.E7)and[Equation8](https://arxiv.org/html/2606.04182#A3.E8)completes our proof\. ∎

## Appendix DLower Bounds

We will first prove a lower bound forρ\\rho\-TV\-stable algorithms for multi\-armed bandits \(MABs\) and construct a reduction from anyρ\\rho\-TV\-stable RL algorithm toρ\\rho\-TV\-stable MAB algorithms\.

###### Lemma D\.1\.

Let𝐀\\mathbf\{A\}be anyρ\\rho\-TV\-stable, sub\-linear algorithm forkk\-armed bandits\. Fix any non\-optimal armaaand letΔa\\Delta\_\{a\}be the gap between the expected mean of armaaand of the optimal arm\. Then, for sufficiently largeTT,𝐀\\mathbf\{A\}pulls armaaat least116​ρ​Δa\\frac\{1\}\{16\\rho\\Delta\_\{a\}\}many times with probability at least1/21/2, for some absolute constantcc\.

###### Proof of[LemmaD\.1](https://arxiv.org/html/2606.04182#A4.Thmtheorem1)\.

Fix any𝐀\\mathbf\{A\}be anyρ\\rho\-TV\-stable, sub\-linear algorithm forkk\-armed bandits\. Fix anykk\-armed bandit instancePPwhere the reward distribution for each arm is a Bernoulli\. Letaabe any sub\-optimal arm of this bandit instance, with the sub\-optimality gap \(i\.e\., the difference between the mean reward of the optimal arm and the mean reward of the sub\-optimal armaa\)Δa\\Delta\_\{a\}\. LetNaN\_\{a\}be the number of times out ofTTrounds that𝐀\\mathbf\{A\}pulls armaa\. Consider the event:

E=\{Na<ta\}​where​ta:=116​ρ​Δa\.\\displaystyle E=\\\{N\_\{a\}<t\_\{a\}\\\}\\text\{ where \}t\_\{a\}:=\\frac\{1\}\{16\\rho\\Delta\_\{a\}\}\.
We need to show:

Pr𝐀,P⁡\(E\)<12\.\\displaystyle\\Pr\_\{\\mathbf\{A\},P\}\(E\)<\\frac\{1\}\{2\}\.\(9\)
In particular, we will proveLABEL:eq:\_the\_number\_of\_pulls\_of\_an\_sub\-optimal\_arm\_is\_largevia two arguments: first, we show a similar inequality but for a new yet similar MAB instanceQQ, and then connect this inequality toLABEL:eq:\_the\_number\_of\_pulls\_of\_an\_sub\-optimal\_arm\_is\_largevia[LemmaA\.6](https://arxiv.org/html/2606.04182#A4.EGx16)\. In particular, consider a newkk\-armed bandit instanceQQthat has the same mean rewards for allkkarms asPP, except only that the mean reward for armaais byΔa\\Delta\_\{a\}larger than the mean reward for the optimal arm ofPP\. The expected regret of𝐀\\mathbf\{A\}inQQis at leastPrQ⁡\(E\)​\(T−ta\)​Δa\\Pr\_\{Q\}\(E\)\(T\-t\_\{a\}\)\\Delta\_\{a\}, as it follows from that underEE, the number of times an sub\-optimal arm ofQQwere pulled is at leastT−taT\-t\_\{a\}, and the sub\-optimality gap of a sub\-optimal arm inQQis at leastΔa\\Delta\_\{a\}\. For sufficiently largeTT, we haveT−ta≥T2T\-t\_\{a\}\\geq\\frac\{T\}\{2\}\. At the same time, the expected regret of𝐀\\mathbf\{A\}inQQis at mostT1−αT^\{1\-\\alpha\}for some fixedα∈\(0,1\]\\alpha\\in\(0,1\]as𝐀\\mathbf\{A\}has sublinear regrets\. Thus, we have

Pr𝐀,Q⁡\(E\)≤𝒪​\(1Tα​Δa\)≤14,\\displaystyle\\Pr\_\{\\mathbf\{A\},Q\}\(E\)\\leq\\mathcal\{O\}\(\\frac\{1\}\{T^\{\\alpha\}\\Delta\_\{a\}\}\)\\leq\\frac\{1\}\{4\},\(10\)for sufficiently largeTT\.

Now consider the following mechanismM𝐀\|𝒟:\{0,1\}ta→\{0,1\}M\_\{\\mathbf\{A\}\|\\mathcal\{D\}\}:\\\{0,1\\\}^\{t\_\{a\}\}\\rightarrow\\\{0,1\\\}that maps from atat\_\{a\}\-bit binary string to a binary output, conditioned on data𝒟\\mathcal\{D\}that is independent of𝐀\\mathbf\{A\}\. In addition, the mechanism depends on the learning algorithm𝐀\\mathbf\{A\}\.

Given a samplex¯∈\{0,1\}ta\\underline\{x\}\\in\\\{0,1\\\}^\{t\_\{a\}\}and a data𝒟∈\{0,1\}\(k−1\)​\(T−ta\)\\mathcal\{D\}\\in\\\{0,1\\\}^\{\(k\-1\)\(T\-t\_\{a\}\)\}, here is howM𝐀\|𝒟M\_\{\\mathbf\{A\}\|\\mathcal\{D\}\}produces the output onx¯\\underline\{x\}\. InitializeU=x¯U=\\underline\{x\}\. We iterate overTTsteps\. In each step: if𝐀\\mathbf\{A\}pullsaaandUUis empty, we terminate and output11; if𝐀\\mathbf\{A\}pullsaaandUUis not empty, we remove a sample fromUUand use it as a reward sample foraaand feed it back to𝐀\\mathbf\{A\}and move to next step and repeat; if𝐀\\mathbf\{A\}does not pullaa, extract from𝒟\\mathcal\{D\}a corresponding reward for the pulled arm, move to the next step and repeat\. If the iteration loop overTTsurvives all the way down to the last iterationTT, output zero, i\.e\., if afterTTiterations we have not outputted11, output0\.

We have the following properties:

- •Pr𝐀,P⁡\(E\|𝒟\)=Pr𝐀,x¯∼Pa⁡\(M𝐀\|𝒟​\(x¯\)=1\)\\Pr\_\{\\mathbf\{A\},P\}\(E\|\\mathcal\{D\}\)=\\Pr\_\{\\mathbf\{A\},\\underline\{x\}\\sim P\_\{a\}\}\(M\_\{\\mathbf\{A\}\|\\mathcal\{D\}\}\(\\underline\{x\}\)=1\), by the construction ofMM,
- •M𝐀\|𝒟​\(⋅\)M\_\{\\mathbf\{A\}\|\\mathcal\{D\}\}\(\\cdot\)isρ\\rho\-TV\-stable, because the output ofM𝐀\|𝒟​\(x¯\)M\_\{\\mathbf\{A\}\|\\mathcal\{D\}\}\(\\underline\{x\}\)is simply a deterministic map from the output of𝐀\\mathbf\{A\}on\(𝒟,x¯\)\(\\mathcal\{D\},\\underline\{x\}\)to\{0,1\}\\\{0,1\\\}and𝐀\\mathbf\{A\}isρ\\rho\-TV\-stable\.

Thus, we now apply[LemmaA\.6](https://arxiv.org/html/2606.04182#A4.EGx16)toM𝐀\|𝒟M\_\{\\mathbf\{A\}\|\\mathcal\{D\}\}, we have that for any𝒟\\mathcal\{D\},

Pr𝐀,P⁡\(E\|𝒟\)−Pr𝐀,Q⁡\(E\|𝒟\)\\displaystyle\\Pr\_\{\\mathbf\{A\},P\}\(E\|\\mathcal\{D\}\)\-\\Pr\_\{\\mathbf\{A\},Q\}\(E\|\\mathcal\{D\}\)=Pr𝐀,x¯∼Pa⁡\(M𝐀\|𝒟​\(x¯\)=1\)−Pr𝐀,x¯∼Qa⁡\(M𝐀\|𝒟​\(x¯\)=1\)\\displaystyle=\\Pr\_\{\\mathbf\{A\},\\underline\{x\}\\sim P\_\{a\}\}\(M\_\{\\mathbf\{A\}\|\\mathcal\{D\}\}\(\\underline\{x\}\)=1\)\-\\Pr\_\{\\mathbf\{A\},\\underline\{x\}\\sim Q\_\{a\}\}\(M\_\{\\mathbf\{A\}\|\\mathcal\{D\}\}\(\\underline\{x\}\)=1\)≤4​ta​ρ​TV​\(Pa,Qa\)\\displaystyle\\leq 4t\_\{a\}\\rho\{\\text\{TV\}\}\(P\_\{a\},Q\_\{a\}\)=4​ta​ρ​Δa\\displaystyle=4t\_\{a\}\\rho\\Delta\_\{a\}Hence,

Pr𝐀,P⁡\(E\)−Pr𝐀,Q⁡\(E\)\\displaystyle\\Pr\_\{\\mathbf\{A\},P\}\(E\)\-\\Pr\_\{\\mathbf\{A\},Q\}\(E\)=∑𝒟Pr𝐀,P⁡\(E\|𝒟\)​P​\(𝒟\)−∑𝒟Pr𝐀,Q⁡\(E\|𝒟\)​Q​\(𝒟\)\\displaystyle=\\sum\_\{\\mathcal\{D\}\}\\Pr\_\{\\mathbf\{A\},P\}\(E\|\\mathcal\{D\}\)P\(\\mathcal\{D\}\)\-\\sum\_\{\\mathcal\{D\}\}\\Pr\_\{\\mathbf\{A\},Q\}\(E\|\\mathcal\{D\}\)Q\(\\mathcal\{D\}\)=∑𝒟Pr𝐀,P⁡\(E\|𝒟\)​Pr⁡\(𝒟\)−∑𝒟Pr𝐀,Q⁡\(E\|𝒟\)​Pr⁡\(𝒟\)\\displaystyle=\\sum\_\{\\mathcal\{D\}\}\\Pr\_\{\\mathbf\{A\},P\}\(E\|\\mathcal\{D\}\)\\Pr\(\\mathcal\{D\}\)\-\\sum\_\{\\mathcal\{D\}\}\\Pr\_\{\\mathbf\{A\},Q\}\(E\|\\mathcal\{D\}\)\\Pr\(\\mathcal\{D\}\)≤4​ta​ρ​Δa​∑𝒟Pr⁡\(𝒟\)\\displaystyle\\leq 4t\_\{a\}\\rho\\Delta\_\{a\}\\sum\_\{\\mathcal\{D\}\}\\Pr\(\\mathcal\{D\}\)=4​ta​ρ​Δa=14\\displaystyle=4t\_\{a\}\\rho\\Delta\_\{a\}=\\frac\{1\}\{4\}where the second inequality follows from thatPPandQQhave the same arm distributions except for armaaand𝒟\\mathcal\{D\}does not contain rewards for armaa\. Now combine the above inequality with[Equation10](https://arxiv.org/html/2606.04182#A4.E10), we have

Pr𝐀,P⁡\(E\)≤14\+14=12\.\\displaystyle\\Pr\_\{\\mathbf\{A\},P\}\(E\)\\leq\\frac\{1\}\{4\}\+\\frac\{1\}\{4\}=\\frac\{1\}\{2\}\.
∎

###### Corollary D\.3\.

The expected regret of anyρ\\rho\-TV\-stable algorithms forkk\-armed bandits isΩ​\(kρ\)\\Omega\\left\(\\frac\{k\}\{\\rho\}\\right\)\.

###### Proof of[CorollaryD\.3](https://arxiv.org/html/2606.04182#A4.Thmtheorem3)\.

It follows from[LemmaD\.1](https://arxiv.org/html/2606.04182#A4.Thmtheorem1)that, for anykk\-armed bandit where the first arm is the optimal arm and all the otherk−1k\-1arms\{2,…,k\}\\\{2,\\ldots,k\\\}are sub\-optimal with sub\-optimal gaps\{Δ2,…,Δk\}\\\{\\Delta\_\{2\},\\ldots,\\Delta\_\{k\}\\\}, we have

𝔼​\[R𝐀​\(T\)\]=∑i=2kΔi​𝔼𝐀​\[Ni\]≥∑i=2kΔi​ti​Pr⁡\(Ni≥ti\)≥k−132​ρ\.\\displaystyle\\mathbb\{E\}\[R\_\{\\mathbf\{A\}\}\(T\)\]=\\sum\_\{i=2\}^\{k\}\\Delta\_\{i\}\\mathbb\{E\}\_\{\\mathbf\{A\}\}\[N\_\{i\}\]\\geq\\sum\_\{i=2\}^\{k\}\\Delta\_\{i\}t\_\{i\}\\Pr\(N\_\{i\}\\geq t\_\{i\}\)\\geq\\frac\{k\-1\}\{32\\rho\}\.∎

The next lemma shows that there exists a class of MDP instances withSSstates,AAactions andHHhorizon where anyρ\\rho\-TV\-stable RL algorithms can be simulated bySSρ\\rho\-TV\-stable MAB algorithms\.

###### Lemma D\.4\.

There exists a class of MDP instances with3​S3Sstates,AAactions andHHhorizon where anyρ\\rho\-TV\-stable RL algorithms can be simulated bySSρ\\rho\-TV\-stableAA\-armed bandit algorithms where the scale of the rewards for each MAB isHH\.

###### Proof of[LemmaD\.4](https://arxiv.org/html/2606.04182#A4.Thmtheorem4)\.

![Refer to caption](https://arxiv.org/html/2606.04182v1/hard_mdp.png)Figure 1:Hard MDPs\.To prove the hardness result, consider the following class of MDPs in[Figure1](https://arxiv.org/html/2606.04182#A4.F1)\. An MDP in this class starts uniformly at random in one ofnninitial states\. From each such state, any action from a set ofAAactions will lead to only one of the two absorbing states where the agent will stay until the end of an episode\. Such an MDP can be viewed asnnAA\-armed bandits in parallel\.

Let𝐀\\mathbf\{A\}be anyρ\\rho\-TV\-stable algorithm\. Let\{s1t\}t∈\[T\]\\\{s\_\{1\}^\{t\}\\\}\_\{t\\in\[T\]\}beTTinitial states, representingTTusers𝒰\\mathcal\{U\}\. For anys∈𝒮s\\in\\mathcal\{S\}, let𝐀s\\mathbf\{A\}\_\{s\}be all the components of the output of𝐀\\mathbf\{A\}that correspond tos1t=ss^\{t\}\_\{1\}=s\. Suppose all the episodesttwheres1t=ss\_\{1\}^\{t\}=saret1,…,tTst\_\{1\},\\ldots,t\_\{T\_\{s\}\}\. Fix any eventEs⊆ΠTsE\_\{s\}\\subseteq\\Pi^\{T\_\{s\}\}\. LetE=\{e∈ΠT:\(et1,…,etTs\)∈Es\}E=\\\{e\\in\\Pi^\{T\}:\(e\_\{t\_\{1\}\},\\ldots,e\_\{t\_\{T\_\{s\}\}\}\)\\in E\_\{s\}\\\}\. By marginalization, we have

Pr⁡\(𝐀s​\(𝒰\)∈Es\)=Pr⁡\(𝐀​\(𝒰\)∈E\)\\displaystyle\\Pr\(\\mathbf\{A\}\_\{s\}\(\\mathcal\{U\}\)\\in E\_\{s\}\)=\\Pr\(\\mathbf\{A\}\(\\mathcal\{U\}\)\\in E\)Thus, let𝒰′\\mathcal\{U\}^\{\\prime\}be a neighbor of𝒰\\mathcal\{U\}\(they differ by one user\), we have

Pr⁡\(𝐀s​\(𝒰\)∈Es\)=Pr⁡\(𝐀​\(𝒰\)∈E\)≤Pr⁡\(𝐀​\(𝒰′\)∈E\)\+ρ=Pr⁡\(𝐀s​\(𝒰′\)∈Es\)\+ρ,\\displaystyle\\Pr\(\\mathbf\{A\}\_\{s\}\(\\mathcal\{U\}\)\\in E\_\{s\}\)=\\Pr\(\\mathbf\{A\}\(\\mathcal\{U\}\)\\in E\)\\leq\\Pr\(\\mathbf\{A\}\(\\mathcal\{U\}^\{\\prime\}\)\\in E\)\+\\rho=\\Pr\(\\mathbf\{A\}\_\{s\}\(\\mathcal\{U\}^\{\\prime\}\)\\in E\_\{s\}\)\+\\rho,where the inequality is due to that𝐀\\mathbf\{A\}isρ\\rho\-TV\-stable\. Therefore, the above inequality implies that𝐀s\\mathbf\{A\}\_\{s\}is alsoρ\\rho\-TV\-stable\.

In general,𝐀s\\mathbf\{A\}\_\{s\}may not be equivalent to an MAB algorithm, as it also uses the information of𝐀\\mathbf\{A\}pulling actions for states other thanss\. Thus,𝐀s\\mathbf\{A\}\_\{s\}may be more powerful than an MAB thus it can break the lower bound in[CorollaryD\.3](https://arxiv.org/html/2606.04182#A4.Thmtheorem3)\. However, in the class of MDPs we construct, the information of𝐀\\mathbf\{A\}pulling actions for states′s^\{\\prime\}gives zero information the rewards and next states for states≠s′s\\neq s^\{\\prime\}\. Thus,𝐀s\\mathbf\{A\}\_\{s\}is a valid MAB algorithm\. ∎

###### Proof of[Theorem4\.4](https://arxiv.org/html/2606.04182#A4.EGx7)\.

The first term in our lower bound is the lower bound for any RL algorithm\(Aueret al\.,[2008](https://arxiv.org/html/2606.04182#bib.bib38)\), thus is applicable to anyρ\\rho\-TV\-stable algorithms\. We only need to prove thatH​S​Aρ\\frac\{HSA\}\{\\rho\}is also a lower bound\. We use the same MDP class as[Figure1](https://arxiv.org/html/2606.04182#A4.F1)in the proof of[LemmaD\.4](https://arxiv.org/html/2606.04182#A4.Thmtheorem4)\. Any RL algorithm must need to solveSSindependentAA\-armed bandit problems of scaleHH\. By[LemmaD\.4](https://arxiv.org/html/2606.04182#A4.Thmtheorem4), anyρ\\rho\-TV\-stable RL algorithm can be simulated bySSρ\\rho\-TV\-stable MAB algorithms that solveSSindependent MAB problems\. By[CorollaryD\.3](https://arxiv.org/html/2606.04182#A4.Thmtheorem3), each of them must incur a regret ofH​Aρ\\frac\{HA\}\{\\rho\}, whereHHis the reward scale of each MAB\. Solving an MDP in our MDP class requires to solvingSSindependent MAB problems, thus the total regret must incur at leastS​H​Aρ\\frac\{SHA\}\{\\rho\}\. ∎