Résumé Technique : Désapprentissage Exact dans l'Apprentissage par Renforcement

1. Formulation du Problème

Le papier traite du problème du désapprentissage exact (exact unlearning) dans le contexte de l'apprentissage par renforcement (RL), plus précisément au sein des processus de décision de Markov (MDP) tabulaires. Contrairement à l'apprentissage supervisé où les points de données sont statiques, les systèmes de RL interagissent séquentiellement avec des utilisateurs, générant des trajectoires d'états, d'actions et de récompenses.

L'objectif central est de concevoir un cadre efficace où, lors d'une demande de suppression de la part d'un utilisateur, le système peut supprimer l'influence de l'historique d'interaction de cet utilisateur. Le modèle résultant doit être indistinguable en distribution d'un modèle entraîné sur les données restantes comme si l'utilisateur supprimé n'avait jamais interagi avec le système. Cela est formalisé comme un désapprentissage exact (Définition 2.1), ce qui exige que pour toute séquence d'utilisateurs $z_{1:T}$ et un utilisateur supprimé $z_t$ remplacé par un utilisateur fictif $z'$, la sortie de l'algorithme de désapprentissage $U$ satisfasse :
$$U(A(z_{1:T}), z_t, z') \stackrel{D}{=} A(z_1, \dots, z_{t-1}, z', z_{t+1}, \dots, z_T)$$

Le papier distingue cela du désapprentissage approximatif (souvent basé sur la confidentialité différentielle), arguant que le désapprentissage exact est nécessaire pour les applications à enjeux élevés (ex: santé, assistants personnalisés) où même une faible probabilité d'influence résiduelle pourrait conduire à des violations de la vie privée ou de la sécurité.

2. Méthodologie

La solution proposée intègre trois composantes principales : la Stabilité TV (Variation Totale), les Mécanismes d'Arbre Binaire et le Couplage Maximal.

2.1. Stabilité TV et Cadre de Désapprentissage

Les auteurs s'appuient sur le concept de $\rho$-stabilité TV (Définition 2.2), où la distribution de sortie d'un algorithme varie au maximum de $\rho$ en distance de Variation Totale lorsqu'un point de donnée unique est modifié. Ils exploitent le résultat théorique selon lequel la $\rho$-stabilité TV est suffisante pour le désapprentissage exact.

Le mécanisme de désapprentissage repose sur le Couplage Maximal. Si un algorithme est $\rho$-stable TV, les distributions du modèle entraîné sur les données originales ($P$) et des données avec l'utilisateur remplacé ($Q$) possèdent un couplage où la probabilité de désaccord est exactement $\text{TV}(P, Q) \leq \rho$. Cela permet à l'algorithme de désapprentissage de :

1. Tenter de réutiliser l'état existant du modèle (échantillonner de $P$) comme un échantillon valide pour $Q$.
2. Avec une probabilité $1 - \text{TV}(P, Q)$, accepter la réutilisation (pas de réentraînement).
3. Avec une probabilité $\text{TV}(P, Q)$, rejeter et réentraîner à partir de zéro (ou d'un checkpoint spécifique).

2.2. Mécanisme d'Arbre Binaire pour les Sommes Préfixes

Pour atteindre la stabilité TV dans un contexte en ligne, les auteurs adaptent le mécanisme d'arbre binaire issu de la confidentialité différentielle (Dwork et al., 2010).

• Structure : Au lieu de stocker les statistiques suffisantes brutes (ex: comptes de visites, récompenses), l'algorithme maintient un arbre binaire parfait où chaque nœud stocke une somme préfixe bruitée.
• Injection de Bruit : Un bruit gaussien est ajouté aux nœuds dans une décomposition dyadique. Une somme préfixe $u_t = \sum_{i=1}^t x_i$ est calculée en sommant $O(\log T)$ valeurs de nœuds bruitées.
• Stabilité : Cette structure garantit que le changement d'un seul utilisateur $x_t$ n'affecte que $O(\log T)$ nœuds dans l'arbre, limitant la sensibilité de la mise à jour et permettant la garantie de $\rho$-stabilité TV.

2.3. Désapprentissage via Échantillonnage par Rejet et Réflexion

L'algorithme de désapprentissage (Algorithme 3) parcourt le chemin allant du nœud feuille supprimé vers la racine :

1. Mise à jour Propre : Il met à jour la valeur "propre" de chaque nœud sur le chemin pour refléter le remplacement de $x_t$ par $x'_t$.
2. Couplage de Valeur Bruitée : Pour les valeurs "bruitées", il effectue une étape d'échantillonnage par rejet. Il vérifie si la valeur bruitée existante $\tilde{v}_b$ (générée sous l'ancienne moyenne propre $v_b$) peut être traitée comme un échantillon de la nouvelle distribution $N(v'_b, \sigma^2 I)$.
   • Accepter : Si accepté, le nœud est mis à jour et le processus passe au parent.
   • Rejeter : Si rejeté, l'algorithme applique une carte de réflexion (une technique de couplage maximal) pour générer une nouvelle valeur bruitée valide et déclenche un processus de réentraînement à partir de la feuille suivante en parcours post-ordre.

2.4. Instanciation de l'Algorithme de RL (UCB-VI avec Bruit)

Les auteurs instaurent ce cadre pour les MDP tabulaires en modifiant l'algorithme UCB-VI (Azar et al., 2017) :

• Oracle d'Environnement : Encode les statistiques de trajectoire (visites état-action, transitions, récompenses) dans la structure de somme préfixe.
• Fonction de Mise à Jour : Utilise les sommes préfixes bruitées pour calculer les estimations optimistes de la valeur.
• Fonction de Bonus : Introduit un terme de bonus spécifique $b(\tilde{n})$ qui rend compte à la fois de l'erreur d'estimation à échantillon fini et de l'erreur d'approximation introduite par le bruit gaussien injecté.

3. Contributions Clés et Résultats

3.1. Garanties Algorithmiques

• Désapprentissage Exact : L'algorithme proposé (Algorithme 2 + Algorithme 3) atteint le désapprentissage exact.
• Efficacité Computationnelle : Le coût computationnel attendu du désapprentissage n'est que d'une fraction $\rho \sqrt{\ln T}$ du coût du réentraînement complet. Le réentraînement n'est déclenché que lorsque le couplage maximal échoue, ce qui arrive avec une faible probabilité.
• Borne de Regret : L'algorithme atteint une borne de regret de :
  $$R(T) = \tilde{O}\left(H^2\sqrt{SAT} + H^3S^2A + \frac{H^{2.5}S^2A}{\rho}\right)$$
  où $S$ est les états, $A$ les actions, $H$ l'horizon, et $T$ les épisodes.
  • Les deux premiers termes correspondent au comportement standard de UCB-VI (avec un coût de démarrage de $H^3S^2A$).
  • Le troisième terme représente le coût de la stabilisation de l'algorithme par le bruit.

3.2. Borne Inférieure Minimax

Le papier établit une borne inférieure minimax pour tout algorithme de RL $\rho$-stable TV :
$$R(T) = \Omega\left(H\sqrt{SAT} + \frac{HSA}{\rho}\right)$$
Ce résultat démontre que la borne supérieure proposée est presque minimaxement optimale, l'écart dans le second terme étant un facteur de $H^{1.5}S$. Les auteurs notent que cet écart pourrait potentiellement être comblé en utilisant une analyse plus fine (par exemple, des bonus de type Bernstein au lieu de type Hoeffding).

3.3. Comparaison avec la Confidentialité Différentielle

Le papier souligne que bien que la Confidentialité Différentielle (DP) implique la stabilité TV, la réciproque n'est pas vraie. Par conséquent, les bornes inférieures pour la DP ne s'appliquent pas automatiquement aux algorithmes stables TV. Les auteurs prouvent que leur borne inférieure est strictement plus forte que les précédentes bornes inférieures basées sur la DP pour le RL, car la stabilité TV est une contrainte plus faible que la DP pure.

4. Signification et Revendications

Le papier affirme fournir le premier cadre théorique et algorithmique pour le désapprentissage exact prouvable dans l'apprentissage par renforcement. Sa signification réside dans :

1. Combler un Vide : Étendre la théorie du désapprentissage exact de l'apprentissage supervisé par lots à l'apprentissage par renforcement séquentiel et interactif.
2. Efficacité : Démontrer que le désapprentissage exact peut être réalisé avec des coûts computationnels nettement inférieurs au réentraînement complet, ce qui le rend faisable pour des systèmes interactifs à grande échelle (ex: systèmes de recommandation, assistants vocaux).
3. Optimalité : Établir que le compromis proposé entre le regret et la stabilité de désapprentissage est presque optimal.
4. Étape Fondatrice : Caractériser une sous-classe naturelle d'algorithmes désapprenables (ceux possédant la stabilité TV) et fournir des garanties de bout en bout combinant un apprentissage optimal en regret et un désapprentissage prouvable.

Les auteurs restent modestes quant aux limites, reconnaissant que :

• Les résultats sont actuellement confinés aux MDP tabulaires ; étendre cela à l'approximation de fonction (espaces d'états larges/continus) reste un défi ouvert.
• Il existe un écart non trivial entre les bornes supérieure et inférieure dans l'analyse du regret.
• L'approche entraîne une complexité spatiale linéaire ($O(T)$) en raison de la structure d'arbre binaire ; le compromis optimal espace-temps-utilité pour le désapprentissage exact n'est pas encore pleinement compris.