Technische Samenvatting: Exact Unlearning in Reinforcement Learning

1. Probleemformulering

Het artikel behandelt het probleem van exact unlearning in de context van Reinforcement Learning (RL), specifiek binnen tabulaire Markov Decision Processes (MDP's). In tegenstelling tot supervised learning, waarbij datapunten statisch zijn, interageren RL-systemen sequentieel met gebruikers en genereren zij trajecten van toestanden, acties en beloningen.

Het kernobjectief is het ontwerpen van een efficiënt framework waarbij het systeem, bij een verzoek tot verwijdering door een gebruiker, de invloed van de interactiegeschiedenis van die gebruiker kan verwijderen. Het resulterende model moet indistinguishable in distribution (in distributie ononderscheidbaar) zijn van een model dat getraind is op de resterende data alsof de verwijderde gebruiker nooit met het systeem heeft geïnteracteerd. Dit wordt geformaliseerd als exact unlearning (Definitie 2.1), wat vereist dat voor elke reeks gebruikers $z_{1:T}$ en een verwijderde gebruiker $z_t$ vervangen door een dummy $z'$, de output van het unlearning-algoritme $U$ voldoet aan:
$$U(A(z_{1:T}), z_t, z') \stackrel{D}{=} A(z_1, \dots, z_{t-1}, z', z_{t+1}, \dots, z_T)$$

Het artikel onderscheidt dit van approximate unlearning (vaak gebaseerd op differential privacy) en voert aan dat exact unlearning noodzakelijk is voor toepassingen met hoge inzet (bijv. de gezondheidszorg, gepersonaliseerde assistenten) waar zelfs een kleine waarschijnlijkheid van residuele invloed kan leiden tot privacyinbreuken of veiligheidschendingen.

2. Methodologie

De voorgestelde oplossing integreert drie hoofdonderdelen: Total Variation (TV) Stability, Binary Tree Mechanisms, en Maximal Coupling.

2.1. TV-Stability en Unlearning Framework

De auteurs bouwen voort op het concept van $\rho$-TV-stability (Definitie 2.2), waarbij de outputdistributie van een algoritme met maximaal $\rho$ verandert in Total Variation afstand wanneer een enkel datapunt wordt gewijzigd. Zij maken gebruik van het theoretische resultaat dat $\rho$-TV-stability voldoende is voor exact unlearning.

Het unlearning-mechanisme rust op Maximal Coupling. Als een algoritme $\rho$-TV-stable is, hebben de distributies van het model getraind op de originele data ($P$) en de data met de vervangen gebruiker ($Q$) een koppeling waarbij de waarschijnlijkheid van een verschilات exact $\text{TV}(P, Q) \leq \rho$ is. Dit stelt het unlearning-algoritme in staat om:

1. Te proberen de bestaande modeltoestand te hergebruiken (een sample trekken uit $P$) als een geldige sample voor $Q$.
2. Met een waarschijnlijkheid van $1 - \text{TV}(P, Q)$ de hergebruik te accepteren (geen hertraining).
3. Met een waarschijnlijkheid van $\text{TV}(P, Q)$ de hergebruik te verwerpen en vanaf nul te hertrainen (of vanaf een specifiek checkpoint).

2.2. Binary Tree Mechanism voor Prefix Sums

Om TV-stability te bereiken in een online setting, passen de auteurs het binary tree mechanism aan uit de differential privacy (Dwork et al., 2010).

• Structuur: In plaats van ruwe voldoende statistieken (bijv. bezoekfrequenties, beloningen) op te slaan, onderhoudt het algoritme een perfecte binaire boom waarbij elke node een ruisige prefix sum opslaat.
• Ruisinjectie: Ruis wordt toegevoegd aan nodes in een dyadische decompositie. Een prefix sum $u_t = \sum_{i=1}^t x_i$ wordt berekend door de waarden van $O(\log T)$ ruisige nodes op te tellen.
• Stability: Deze structuur zorgt ervoor dat het wijzigen van de data van een enkele gebruiker $x_t$ slechts $O(\log T)$ nodes in de boom beïnvloedt, wat de sensitiviteit van de update beperkt en de $\rho$-TV-stability garantie mogelijk maakt.

2.3. Unlearning via Rejection Sampling en Reflection

Het unlearning-algoritme (Algoritme 3) doorloopt het pad van de verwijderde leaf node naar de root:

1. Clean Update: Het werkt de "schone" waarde van elke node op het pad bij om de vervanging van $x_t$ door $x'_t$ te reflecteren.
2. Noisy Value Coupling: Voor de "ruisige" waarden voert het een rejection sampling stap uit. Het controleert of de bestaande ruisige waarde $\tilde{v}_b$ (gegenereerd onder de oude schone gemiddelde $v_b$) behandeld kan worden als een sample uit de nieuwe distributie $N(v'_b, \sigma^2 I)$.
   • Accept: Indien geaccepteerd, wordt de node bijgewerkt en gaat het proces naar de ouder.
   • Reject: Indien geweigerd, past het algoritme een reflection map toe (een maximal coupling techniek) om een nieuwe geldige ruisige waarde te genereren en triggert het een hertraining proces beginnend bij de volgende leaf in een post-order traversatie.

2.4. RL Algoritme Instantiatie (UCB-VI met Ruis)

De auteurs instantiëren dit framework voor tabulaire MDP's door het UCB-VI algoritme (Azar et al., 2017) te modificeren:

• Environment Oracle: Codeert trajectstatistieken (state-action bezoeken, transities, beloningen) in de prefix sum structuur.
• Update Function: Gebruikt de ruisige prefix sums om optimistische waardeschattingen te berekenen.
• Bonus Function: Introduceert een specifieke bonus term $b(\tilde{n})$ die rekening houdt met zowel de eindige-steekproef schattingsfout als de benaderingsfout geïntroduceerd door de geïnjecteerde Gaussische ruis.

3. Belangrijkste Bijdragen en Resultaten

3.1. Algoritmische Garanties

• Exact Unlearning: Het voorgestelde algoritme (Algoritme 2 + Algoritme 3) bereikt exact unlearning.
• Computationele Efficiëntie: De verwachte computationele kosten van unlearning zijn slechts een $\rho \sqrt{\ln T}$ fractie van de kosten van volledig hertrainen. Hertraining wordt alleen getriggerd wanneer de maximal coupling faalt, wat met een lage waarschijnlijkheid gebeurt.
• Regret Bound: Het algoritme bereikt een regret bound van:
  $$R(T) = \tilde{O}\left(H^2\sqrt{SAT} + H^3S^2A + \frac{H^{2.5}S^2A}{\rho}\right)$$
  waarbij $S$ toestanden, $A$ acties, $H$ horizon en $T$ episodes zijn.
  • De eerste twee termen komen overeen met standaard UCB-VI gedrag (met een $H^3S^2A$ burn-in kosten).
  • De derde term vertegenwoordigt de kosten van het stabiliseren van het algoritme met ruis.

3.2. Minimax Lower Bound

Het artikel stelt een minimax lower bound vast voor elk $\rho$-TV-stable RL-algoritme:
$$R(T) = \Omega\left(H\sqrt{SAT} + \frac{HSA}{\rho}\right)$$
Dit resultaat toont aan dat de voorgestelde upper bound bijna minimax optimaal is, waarbij het gat in de tweede term een factor $H^{1.5}S$ is. De auteurs merken op dat dit gat potentieel gedicht kan worden met een scherpere analyse (bijv. Bernstein-type bonuses in plaats van Hoeffding-type).

3.3. Vergelijking met Differential Privacy

Het artikel benadrukt dat hoewel Differential Privacy (DP) TV-stability impliceert, het omgekeerde niet waar is. Bijgevolg zijn de lower bounds voor DP niet automatisch van toepassing op TV-stable algoritmen. De auteurs bewijzen dat hun lower bound strikt sterker is dan eerdere DP-gebaseerde lower bounds voor RL, aangezien TV-stability een zwakkere restrictie is dan pure DP.

4. Betekenis en Claims

Het artikel claimt het eerste theoretische en algoritmische framework te bieden voor bewijsbaar exact unlearning in reinforcement learning. De significantie ligt in:

1. Het overbruggen van een kloof: Het uitbreiden van de theorie van exact unlearning van batch supervised learning naar sequentiële, interactieve RL-settings.
2. Efficiëntie: Het aantonen dat exact unlearning kan worden bereikt met computationele kosten die aanzienlijk lager zijn dan volledige hertraining, wat het haalbaar maakt voor grootschalige interactieve systemen (bijv. aanbevelingssystemen, stemassistenten).
3. Optimaliteit: Het vaststellen dat de voorgestelde trade-off tussen regret en unlearning stability bijna optimaal is.
4. Fundamentele Stap: Het karakteriseren van een natuurlijke subclass van onlearnbare algoritmen (die met TV-stability) en het bieden van end-to-end garanties die regret-optimale learning combineren met bewijsbaar unlearning.

De auteurs blijven bescheiden over beperkingen en erkennen dat:

• De resultaten momenteel beperkt zijn tot tabulaire MDP's; het uitbreiden naar functie-approximatie (grote/continue toestandsruimtes) blijft een open uitdaging.
• Er is een niet-triviaal gat tussen de upper en lower bounds in de regret-analyse.
• De aanpak een lineaire ruimtecomplexiteit ($O(T)$) met zich meebrengt vanwege de binaire boomstructuur, en de optimale ruimte-tijd-nut utiliteit trade-off voor exact unlearning is nog niet volledig begrepen.