Riepilogo Tecnico: Unlearning Esatto nel Reinforcement Learning

1. Formulazione del Problema

Il documento affronta il problema dell'unlearning esatto (exact unlearning) nel contesto del Reinforcement Learning (RL), specificamente all'interno di processi decisionali di Markov (MDP) tabulari. A differenza dell'apprendimento supervisionato dove i punti dati sono statici, i sistemi RL interagiscono sequenzialmente con gli utenti, generando traiettorie di stati, azioni e ricompense.

L'obiettivo centrale è progettare un framework efficiente in cui, a seguito di una richiesta di cancellazione da parte di un utente, il sistema possa rimuovere l'influenza della cronologia di interazione di quell'utente. Il modello risultante deve essere indistinguibile in distribuzione da un modello addestrato sui dati rimanenti come se l'utente eliminato non avesse mai interagito con il sistema. Questo è formalizzato come unlearning esatto (Definizione 2.1), che richiede che per ogni sequenza di utenti $z_{1:T}$ e un utente eliminato $z_t$ sostituito da un dummy $z'$, l'output dell'algoritmo di unlearning $U$ soddisfi:
$$U(A(z_{1:T}), z_t, z') \stackrel{D}{=} A(z_1, \dots, z_{t-1}, z', z_{t+1}, \dots, z_T)$$

Il documento distingue questo concetto dall'unlearning approssimato (spesso basato sulla privacy differenziale), sostenendo che l'unlearning esatto sia necessario per applicazioni ad alto rischio (ad es. sanità, assistenti personali) dove anche una piccola probabilità di influenza residua potrebbe portare a violazioni della privacy o della sicurezza.

2. Metodologia

La soluzione proposta integra tre componenti principali: Stabilità TV (Total Variation Stability), Meccanismi ad Albero Binario e Accoppiamento Massimale (Maximal Coupling).

2.1. Stabilità TV e Framework di Unlearning

Gli autori si basano sul concetto di $\rho$-TV-stabilità (Definizione 2.2), in cui la distribuzione dell'output di un algoritmo cambia al massimo di $\rho$ in distanza di Total Variation quando un singolo punto dato viene modificato. Sfruttano il risultato teorico secondo cui la $\rho$-TV-stabilità è sufficiente per l'unlearning esatto.

Il meccanismo di unlearning si basa sull'Accoppiamento Massimale. Se un algoritmo è $\rho$-TV-stabile, le distribuzioni del modello addestrato sui dati originali ($P$) e sui dati con l'utente sostituito ($Q$) hanno un accoppiamento in cui la probabilità di disaccordo è esattamente $\text{TV}(P, Q) \leq \rho$. Ciò consente all'algoritmo di unlearning di:

1. Tentare di riutilizzare lo stato del modello esistente (campionare da $P$) come un campione valido per $Q$.
2. Con probabilità $1 - \text{TV}(P, Q)$, accettare il riutilizzo (nessun riaddestramento).
3. Con probabilità $\text{TV}(P, Q)$, rifiutare e riaddestrare da zero (o da un checkpoint specifico).

2.2. Meccanismo ad Albero Binario per le Somme Prefisse

Per ottenere la stabilità TV in un contesto online, gli autori adattano il meccanismo ad albero binario dalla privacy differenziale (Dwork et al., 2010).

• Struttura: Invece di memorizzare le statistiche sufficienti grezze (ad es. conteggi delle visite, ricompense), l'algoritmo mantiene un albero binario perfetto in cui ogni nodo memorizza una somma prefissa rumorosa.
• Iniezione di Rumore: Il rumore Gaussiano viene aggiunto ai nodi in una decomposizione diadica. Una somma prefissa $u_t = \sum_{i=1}^t x_i$ viene calcolata sommando $O(\log T)$ valori di nodi rumorosi.
• Stabilità: Questa struttura garantisce che il cambiamento di un singolo dato utente $x_t$ influenzi solo $O(\log T)$ nodi nell'albero, limitando la sensibilità dell'aggiornamento e consentendo la garanzia di $\rho$-TV-stabilità.

2.3. Unlearning tramite Rejection Sampling e Riflessione

L'algoritmo di unlearning (Algoritmo 3) attraversa il percorso dal nodo foglia eliminato verso la radice:

1. Aggiornamento Pulito: Aggiorna il valore "pulito" di ciascun nodo sul percorso per riflettere la sostituzione di $x_t$ con $x'_t$.
2. Accoppiamento Valore Rumoso: Per i valori "rumosi", esegue un passaggio di rejection sampling. Verifica se l'attuale valore rumoroso $\tilde{v}_b$ (generato sotto la vecchia media pulita $v_b$) può essere trattato come un campione della nuova distribuzione $N(v'_b, \sigma^2 I)$.
   • Accetta: Se accettato, il nodo viene aggiornato e il processo si sposta verso il genitore.
   • Rifiuta: Se rifiutato, l'algoritmo applica una mappa di riflessione (una tecnica di accoppiamento massimale) per generare un nuovo valore rumoroso valido e innesca un processo di riaddestramento partendo dalla foglia successiva in attraversamento post-ordine.

2.4. Istanziazione dell'Algoritmo RL (UCB-VI con Rumore)

Gli autori istanziano questo framework per MDP tabulari modificando l'algoritmo UCB-VI (Azar et al., 2017):

• Oracolo dell'Ambiente: Codifica le statistiche delle traiettorie (visite stato-azione, transizioni, ricompense) nella struttura della somma prefissa.
• Funzione di Aggiornamento: Utilizza le somme prefisse rumorose per calcolare stime ottimistiche del valore.
• Funzione Bonus: Introduce un termine bonus specifico $b(\tilde{n})$ che tiene conto sia dell'errore di stima a campioni finiti, sia dell'errore di approssimazione introdotto dal rumore Gaussiano iniettato.

3. Contributi Chiave e Risultati

3.1. Garanzie Algoritmiche

• Unlearning Esatto: Il processo proposto (Algoritmo 2 + Algoritmo 3) raggiunge l'unlearning esatto.
• Efficienza Computazionale: Il costo computazionale atteso dell'unlearning è solo una frazione $\rho \sqrt{\ln T}$ del costo del riaddestramento da zero. Il riaddestramento viene innescato solo quando l'accoppiamento massimale fallisce, il che avviene con bassa probabilità.
• Limite di Regret (Regret Bound): L'algoritmo raggiunge un limite di regret di:
  $$R(T) = \tilde{O}\left(H^2\sqrt{SAT} + H^3S^2A + \frac{H^{2.5}S^2A}{\rho}\right)$$
  dove $S$ sono gli stati, $A$ le azioni, $H$ l'orizzonte e $T$ gli episodi.
  • I primi due termini corrispondono al comportamento standard di UCB-VI (con un costo di "burn-in" $H^3S^2A$).
  • Il terzo termine rappresenta il costo della stabilizzazione dell'algoritmo con il rumore.

3.2. Minimax Lower Bound

Il documento stabilisce un limite inferiore minimax per qualsiasi algoritmo RL $\rho$-TV-stabile:
$$R(T) = \Omega\left(H\sqrt{SAT} + \frac{HSA}{\rho}\right)$$
Questo risultato dimostra che il limite superiore proposto è quasi minimax ottimale, con un divario nel secondo termine pari a un fattore $H^{1.5}S$. Gli autori osservano che tale divario potrebbe potenzialmente essere colmato utilizzando analisi più precise (ad es. bonus di tipo Bernstein invece di quelli di tipo Hoeffding).

3.3. Confronto con la Privacy Differenziale

Il documento evidenzia che, mentre la Privacy Differenziale (DP) implica la stabilità TV, il contrario non è vero. Di conseguenza, i limiti inferiori per la DP non si applicano automaticamente agli algoritmi TV-stabili. Gli autori dimostrano che il loro limite inferiore è strettamente più forte dei precedenti limiti inferiori basati sulla DP per il RL, poiché la $\rho$-TV-stabilità è un vincolo più debole rispetto alla pura DP.

4. Significato e Rivendicazioni

Il documento sostiene di fornire il primo framework teorico e algoritmico per l'unlearning esatto provabile nel reinforcement learning. La sua importanza risiede in:

1. Colmare un Vuoto: Estendere la teoria dell'unlearning esatto dall'apprendimento supervisionato batch all'apprendimento RL sequenziale e interattivo.
2. Efficienza: Dimostrare che l'unlearning esatto può essere ottenuto con costi computazionali significativamente inferiori rispetto al riaddestramento completo, rendendolo fattibile per sistemi interattivi su larga scala (ad es. sistemi di raccomandazione, assistenti vocali).
3. Ottimalità: Stabilire che il compromesso proposto tra regret e stabilità di unlearning è quasi ottimale.
4. Passaggio Fondamentale: Caratterizzare una sottoclasse naturale di algoritmi "unlearnable" (quelli con stabilità TV) e fornire garanzie end-to-end che combinano l'apprendimento con regret ottimale e l'unlearning provabile.

Gli autori rimangono modesti riguardo ai limiti, riconoscendo che:

• I risultati sono attualmente limitati ai MDP tabulari; estendere l'approccio all'approssimazione di funzioni (spazi di stato grandi o continui) rimane una sfida aperta.
• Esiste un divario non trascurabile tra i limiti superiori e inferiori nell'analisi del regret.
• L'approccio comporta una complessità di spazio lineare ($O(T)$) a causa della struttura ad albero binario, e il trade-off ottimale spazio-tempo-utilità per l'unlearning esatto non è ancora pienamente compreso.