Resumo Técnico: Unlearning Exato em Aprendizado por Reforço

1. Formulação do Problema

O artigo aborda o problema do unlearning exato (desaprendizado exato) no contexto de Aprendizado por Reforço (RL), especificamente dentro de Processos de Decisão de Markov (MDPs) tabulares. Diferente do aprendizado supervisionado, onde os pontos de dados são estáticos, os sistemas de RL interagem sequencialmente com usuários, gerando trajetórias de estados, ações e recompensas.

O objetivo central é projetar um framework eficiente onde, mediante uma solicitação de exclusão de um usuário, o sistema possa remover a influência do histórico de interação desse usuário. O modelo resultante deve ser indistinguível em distribuição de um modelo treinado nos dados restantes como se o usuário deletado nunca tivesse interagido com o sistema. Isso é formalizado como unlearning exato (Definição 2.1), o que exige que para qualquer sequência de usuários $z_{1:T}$ e um usuário deletado $z_t$ substituído por um dummy $z'$, a saída do algoritmo de unlearning $U$ satisfaça:
$$U(A(z_{1:T}), z_t, z') \stackrel{D}{=} A(z_1, \dots, z_{t-1}, z', z_{t+1}, \dots, z_T)$$

O artigo distingue isso do unlearning aproximado (frequentemente baseado em privacidade diferencial), argumentando que o unlearning exato é necessário para aplicações de alto risco (ex: saúde, assistentes personalizados) onde mesmo uma pequena probabilidade de influência residual poderia levar a violações de privacidade ou de segurança.

2. Metodologia

A solução proposta integra três componentes principais: Estabilidade de TV (Variação Total), Mecanismos de Árvore Binária e Acoplamento Maximal.

2.1. Estabilidade de TV e Framework de Unlearning

Os autores baseiam-se no conceito de $\rho$-TV-estabilidade (Definição 2.2), onde a distribuição de saída de um algoritmo muda no máximo $\rho$ em distância de Variação Total quando um único ponto de dado é modificado. Eles utilizam o resultado teórico de que a $\rho$-TV-estabilidade é suficiente para o unlearning exato.

O mecanismo de unlearning baseia-se no Acoplamento Maximal. Se um algoritmo é $\rho$-TV-estável, as distribuições do modelo treinado nos dados originais ($P$) e nos dados com o usuário substituído ($Q$) possuem um acoplamento onde a probabilidade de discordância é exatamente $\text{TV}(P, Q) \leq \rho$. Isso permite que o algoritmo de unlearning:

1. Tente reutilizar o estado existente do modelo (amostrar de $P$) como uma amostra válida para $Q$.
2. Com probabilidade $1 - \text{TV}(P, Q)$, aceite a reutilização (sem retreinamento).
3. Com probabilidade $\text{TV}(P, Q)$, rejeite e retreine do zero (ou de um checkpoint específico).

2.2. Mecanismo de Árvore Binária para Somas de Prefixos

Para alcançar a TV-estabilidade em um cenário online, os autores adaptam o mecanismo de árvore binária de privacidade diferencial (Dwork et al., 2010).

• Estrutura: Em vez de armazenar estatísticas suficientes brutas (ex: contagens de visitação, recompensas), o algoritmo mantém uma árvore binária perfeita onde cada nó armazena uma soma de prefixo ruidosa.
• Injeção de Ruído: Ruído Gaussiano é adicionado aos nós em uma decomposição diádica. Uma soma de prefixo $u_t = \sum_{i=1}^t x_i$ é computada somando $O(\log T)$ valores de nós ruidosos.
• Estabilidade: Esta estrutura garante que a alteração de um único dado de usuário $x_t$ afete apenas $O(\log T)$ nós na árvore, limitando a sensibilidade da atualização e permitindo a garantia de $\rho$-TV-estabilidade.

2.3. Unlearning via Rejeição por Amostragem e Reflexão

O algoritmo de unlearning (Algoritmo 3) percorre o caminho do nó folha deletado até a raiz:

1. Atualização Limpa: Ele atualiza o valor "limpo" de cada nó no caminho para refletir a substituição de $x_t$ por $x'_t$.
2. Acoplamento de Valor Ruidoso: Para os valores "ruidosos", ele realiza uma etapa de rejeição por amostragem (rejection sampling). Ele verifica se o valor ruidoso existente $\tilde{v}_b$ (gerado sob a antiga média limpa $v_b$) pode ser tratado como uma amostra da nova distribuição $N(v'_b, \sigma^2 I)$.
   • Aceitar: Se aceito, o nó é atualizado e o processo segue para o pai.
   • Rejeitar: Se rejeitado, o algoritmo aplica um mapa de reflexão (uma técnica de acoplamento maximal) para gerar um novo valor ruidoso válido e dispara um processo de retreinamento começando do próximo folha em uma travessia pós-ordem.

2.4. Instanciação do Algoritmo de RL (UCB-VI com Ruído)

Os autores instanciam este framework para MDPs tabulares modificando o algoritmo UCB-VI (Azar et al., 2017):

• Oráculo do Ambiente: Codifica estatísticas de trajetória (visitas estado-ação, transições, recompensas) na estrutura de soma de prefixo.
• Função de Atualização: Utiliza as somas de prefixo ruidosas para computar estimativas otimistas de valor.
• Função de Bônus: Introduz um termo de bônus específico $b(\tilde{n})$ que contabiliza tanto o erro de estimativa de amostra finita quanto o erro de aproximação introduzido pelo ruído Gaussiano injetado.

3. Contribuições Principais e Resultados

3.1. Garantias Algorítmicas

• Unlearning Exato: O algoritmo proposto (Algoritmo 2 + Algoritmo 3) alcança unlearning exato.
• Eficiência Computacional: O custo computacional esperado do unlearning é apenas uma fração $\rho \sqrt{\ln T}$ do custo de retreinar do zero. O retreinamento é disparado apenas quando o acoplamento maximal falha, o que ocorre com baixa probabilidade.
• Limite de Regret (Arrependimento): O algoritmo alcança um limite de regret de:
  $$R(T) = \tilde{O}\left(H^2\sqrt{SAT} + H^3S^2A + \frac{H^{2.5}S^2A}{\rho}\right)$$
  onde $S$ é estados, $A$ é ações, $H$ é horizonte, e $T$ é episódios.
  • Os dois primeiros termos correspondem ao comportamento padrão do UCB-VI (com um custo de burn-in de $H^3S^2A$).
  • O terceiro termo representa o custo de estabilizar o algoritmo com ruído.

3.2. Limite Inferior Minimax

O artigo estabelece um limite inferior minimax para qualquer algoritmo de RL $\rho$-TV-estável:
$$R(T) = \Omega\left(H\sqrt{SAT} + \frac{HSA}{\rho}\right)$$
Este resultado demonstra que o limite superior proposto é quase minimax ótimo, com a lacuna no segundo termo sendo um fator de $H^{1.5}S$. Os autores observam que essa lacuna poderia potencialmente ser fechada usando análises mais aguçadas (ex: bônus do tipo Bernstein em vez de tipos Hoeffding).

3.3. Comparação com Privacidade Diferencial

O artigo destaca que, embora a Privacidade Diferencial (DP) implique TV-estabilidade, o inverso não é verdadeiro. Consequentemente, os limites inferiores para DP não se aplicam automaticamente a algoritmos TV-estáveis. Os autores provam que seu limite inferior é estritamente mais forte do que os limites anteriores baseados em DP para RL, visto que a TV-estabilidade é uma restrição mais fraca que a DP pura.

4. Significância e Alegações

O artigo afirma fornecer o primeiro framework teórico e algorítmico para unlearning exato provável em aprendizado por reforço. Sua significância reside em:

1. Preenchimento de uma Lacuna: Estender a teoria do unlearning exato do aprendizado supervisionado em lote para cenários de RL sequenciais e interativos.
2. Eficiência: Demonstrar que o unlearning exato pode ser alcançado com custos computacionais significativamente menores do que o retreinamento total, tornando-o viável para sistemas interativos de larga escala (ex: sistemas de recomendação, assistentes de voz).
3. Otimalidade: Estabelecer que o trade-off proposto entre regret e estabilidade de unlearning é quase ótimo.
4. Passo Fundamental: Caracterizar uma subclasse natural de algoritmos "desaprendíveis" (aqueles com TV-estabilidade) e fornecer garantias de ponta a ponta combinando aprendizado de regret-ótimo com unlearning provável.

Os autores mantêm a modéstia quanto às limitações, reconhecendo que:

• Os resultados estão atualmente confinados a MDPs tabulares; estender para aproximação de função (espaços de estados grandes/contínuos) permanece um desafio aberto.
• Existe uma lacuna não trivial entre os limites superior e inferior na análise de regret.
• A abordagem incorre em complexidade de espaço linear ($O(T)$) devido à estrutura de árvore binária, e o trade-off ideal entre espaço-tempo-utilidade para unlearning exato ainda não é totalmente compreendido.