Towards Differentially Private Reinforcement Learning with General Function Approximation

Resumo Técnico: Rumo ao Aprendizado por Reforço com Privacidade Diferencial e Aproximação de Função Geral

Declaração do Problema
Este artigo aborda o desafio de alcançar Aprendizado por Reforço (RL) online com eficiência de amostra sob garantias formais de privacidade, quando o ambiente é modelado com aproximação de função geral. Embora trabalhos teóricos anteriores sobre RL com Privacidade Diferencial (DP) tenham estabelecido limites de arrependimento sublineares, esses resultados estão amplamente restritos a ambientes tabulares ou configurações de aproximação de função linear. Os autores identificam uma lacuna crítica: estender essas garantias para classes de funções gerais e não lineares (por exemplo, redes neurais ou classes de hipóteses complexas) permanece um problema em aberto. A questão central é se o arrependimento sublinear é alcançável para RL privado com aproximação de função geral sob Privacidade Diferencial Conjunta (JDP), um relaxamento do DP padrão adequado para RL personalizado, onde as ações individuais dos usuários devem permanecer privadas enquanto a política global é aprendida.

Metodologia
Os autores propõem um framework de RL sem modelo que integra três componentes algorítmicos-chave para lidar com a tensão entre exploração, aproximação de função geral e privacidade:

1. Objetivo de Otimização sem Restrições: Diferentemente do RL não privado padrão, que frequentemente depende de otimização baseada em conjuntos de confiança (por exemplo, métodos de Limite Superior de Confiança), a abordagem proposta adota um objetivo de otimização sem restrições. Este objetivo equilibra explicitamente o valor estimado (otimismo) e o erro estatístico (perda de Bellman). Essa formulação evita a dificuldade de privatizar conjuntos de confiança complexos e dependentes de dados.
2. Mecanismo Exponencial para Seleção de Política: Para privatizar a seleção da função de valor (e, consequentemente, da política) a partir de uma classe de funções $\mathcal{F}$, o algoritmo emprega o Mecanismo Exponencial. Em vez de selecionar deterministicamente a função que maximiza a pontuação (o que vazaria dados sensíveis), o algoritmo amostra uma função $f^{(k)}$ com probabilidade proporcional a $\exp(\beta \cdot S(f))$, onde $S(f)$ é uma função de pontuação que combina o valor otimista e a perda de Bellman.
3. Atualizações de Política em Lotes: Para controlar a perda cumulativa de privacidade (composição) ao longo de $K$ episódios, o algoritmo atualiza a política apenas no início de lotes de tamanho fixo $B$. Dentro de um lote, a política permanece fixa. Essa estratégia limita o número de vezes que qualquer ponto de dados individual participa de uma atualização privada, permitindo uma acumulação sublinear da perda de privacidade em vez de uma linear.

O artigo apresenta dois algoritmos específicos:

• Algoritmo 1: Projetado para MDPs estocásticos gerais. Requer completude de Bellman (a classe de funções deve ser fechada sob o operador de Bellman) e utiliza uma perda de erro de Bellman com uma correção de ínfimo para lidar com problemas de dupla amostragem.
• Algoritmo 2: Projetado para MDPs determinísticos com recompensas de resultado (uma configuração motivada por aplicações de Modelos de Linguagem de Grande Escala). Esta variante relaxa o requisito para realizabilidade (a função Q ótima existe na classe) e substitui a perda de erro de Bellman por uma perda de resíduo de Bellman baseada em resultado, eliminando a necessidade de otimização max-min.

Principais Contribuições

1. Primeiras Garantias Teóricas para Aproximação de Função Geral: O artigo estabelece os primeiros limites de arrependimento sublineares para RL online com aproximação de função geral sob JDP.
2. Limites de Arrependimento:
   • Para MDPs estocásticos gerais (Algoritmo 1), o arrependimento escala como $\tilde{O}(K^{3/5})$, dependendo do parâmetro de cobertura $C_{cov}$, que caracteriza a dificuldade de exploração.
   • Para MDPs determinísticos com recompensas de resultado (Algoritmo 2), um limite similar de $\tilde{O}(K^{3/5})$ é alcançado sob a suposição mais fraca de realizabilidade.
   • Esses limites igualam os resultados mais avançados para o caso de aproximação de função linear no cenário sem modelo, apesar da complexidade aumentada das classes de funções gerais.
3. Subprodutos Não Privados: A análise produz novos limites de arrependimento para RL não privado sob restrições de adaptividade (agrupamento em lotes de tamanho fixo). Especificamente, mostra que um arrependimento de $\tilde{O}(\sqrt{K})$ é alcançável com $\sqrt{K}$ atualizações sob a condição de cobertura, complementando resultados existentes baseados na classe de Condição Eluder.
4. Esclarecimento da Literatura de MDPs Lineares: Os autores identificam lacunas fundamentais em recentes alegações de limites de arrependimento $\tilde{O}(\sqrt{K})$ melhorados para RL privado com MDPs lineares. Eles argumentam que as provas existentes, que dependem de "troca rara de política" e truques de determinante, falham sob restrições de privacidade porque a monotonicidade necessária da matriz de projeto é quebrada pela injeção de ruído de privacidade.

Resultados e Análise
A análise teórica depende da constante de cobertura, uma medida de complexidade introduzida por Xie et al. [XFBJK22], que generaliza o conceito de dificuldade de exploração além dos cenários lineares. O esboço da prova envolve:

• Decompor o arrependimento em um termo relacionado ao "erro de treinamento" (perda de Bellman) e um erro "na política" (teste).
• Usar o Mecanismo Exponencial para limitar o desvio entre a função selecionada e a ótima (custo de privacidade).
• Derivar uma nova desigualdade para relacionar o erro na política ao erro de treinamento na presença de lotes, utilizando a constante de cobertura para limitar a mudança de distribuição entre a política de coleta de dados e a política atual.
• Otimizar o tamanho do lote $B$ e o parâmetro de temperatura $\eta$ para equilibrar o trade-off entre a frescura da informação (arrependimento) e o custo de privacidade.

O artigo inclui uma simulação de prova de conceito em um cenário de recompensa de resultado determinístico. Os resultados demonstram o trade-off esperado entre privacidade e utilidade: privacidade mais forte (menor $\epsilon$) leva a uma convergência mais lenta (mais episódios de platô), enquanto a introdução de lotes gera um atraso moderado em comparação com o aprendizado não privado e sem lotes.

Significado
O artigo afirma fornecer a primeira fundação teórica principista para RL privado em cenários que refletem aplicações modernas, como aquelas envolvendo Modelos de Linguagem de Grande Escala (LLMs) e aproximadores de função complexos e não lineares. Ao demonstrar que a escala de arrependimento $\tilde{O}(K^{3/5})$ alcançável em cenários lineares se estende a classes de funções gerais sob JDP, o trabalho preenche uma lacuna significativa entre a teoria de preservação de privacidade e sistemas práticos de RL. Além disso, ao expor falhas na literatura recente sobre MDPs lineares, o artigo visa esclarecer o panorama do RL privado, garantindo que avanços teóricos futuros sejam construídos sobre fundamentos analíticos sólidos. O framework é apresentado como uma abordagem modular que pode ser adaptada a vários mecanismos de privacidade e classes de funções.