Towards Differentially Private Reinforcement Learning with General Function Approximation

Sintesi Tecnica: Verso l'Apprendimento per Rinforzo Differenzialmente Privato con Approssimazione di Funzioni Generale

Enunciato del Problema
Questo articolo affronta la sfida di realizzare un Apprendimento per Rinforzo (RL) online efficiente in termini di campioni sotto garanzie formali di privacy, quando l'ambiente è modellato con approssimazione di funzioni generale. Sebbene lavori teorici precedenti sull'RL Differenzialmente Privato (DP) abbiano stabilito limiti di rimpianto sublineari, tali risultati sono in gran parte limitati ad ambienti tabulari o a impostazioni di approssimazione lineare. Gli autori identificano un divario critico: estendere queste garanzie a classi di funzioni generali e non lineari (ad esempio, reti neurali o classi di ipotesi complesse) rimane un problema aperto. La domanda fondamentale è se sia possibile ottenere un rimpianto sublineare per l'RL privato con approssimazione di funzioni generale sotto Privacy Differenziale Congiunta (JDP), un rilassamento della DP standard adatto all'RL personalizzato in cui le azioni dei singoli utenti devono rimanere private mentre viene appresa una politica globale.

Metodologia
Gli autori propongono un framework di RL senza modello che integra tre componenti algoritmiche chiave per gestire la tensione tra esplorazione, approssimazione di funzioni generale e privacy:

1. Obiettivo di Ottimizzazione Senza Vincoli: A differenza dell'RL standard non privato che spesso si basa su ottimizzazione vincolata basata su insiemi di confidenza (ad esempio, metodi del Limite Superiore di Confidenza), l'approccio proposto adotta un obiettivo di ottimizzazione senza vincoli. Questo obiettivo bilancia esplicitamente il valore stimato (ottimismo) e l'errore statistico (perdita di Bellman). Questa formulazione evita la difficoltà di privatizzare insiemi di confidenza complessi e dipendenti dai dati.
2. Meccanismo Esponenziale per la Selezione della Politica: Per privatizzare la selezione della funzione di valore (e di conseguenza della politica) da una classe di funzioni $\mathcal{F}$, l'algoritmo impiega il Meccanismo Esponenziale. Invece di selezionare deterministicamente la funzione che massimizza il punteggio (il che rivelerebbe dati sensibili), l'algoritmo campiona una funzione $f^{(k)}$ con probabilità proporzionale a $\exp(\beta \cdot S(f))$, dove $S(f)$ è una funzione di punteggio che combina il valore ottimistico e la perdita di Bellman.
3. Aggiornamenti della Politica in Batch: Per controllare la perdita cumulativa di privacy (composizione) su $K$ episodi, l'algoritmo aggiorna la politica solo all'inizio di batch di dimensione fissa $B$. All'interno di un batch, la politica rimane fissa. Questa strategia limita il numero di volte in cui un singolo punto dati partecipa a un aggiornamento privato, consentendo un'accumulazione sublineare della perdita di privacy piuttosto che lineare.

L'articolo presenta due algoritmi specifici:

• Algoritmo 1: Progettato per MDP stocastici generali. Richiede completezza di Bellman (la classe di funzioni deve essere chiusa rispetto all'operatore di Bellman) e utilizza una perdita basata sull'errore di Bellman con una correzione infima per gestire problemi di doppio campionamento.
• Algoritmo 2: Progettato per MDP deterministici con ricompense basate sull'esito (un contesto motivato dalle applicazioni dei Modelli Linguistici su Grande Scala). Questa variante rilassa il requisito alla realizzabilità (la funzione Q ottima esiste nella classe) e sostituisce la perdita basata sull'errore di Bellman con una perdita residua di Bellman basata sull'esito, eliminando la necessità di ottimizzazione max-min.

Contributi Chiave

1. Prime Garanzie Teoriche per l'Approssimazione di Funzioni Generale: L'articolo stabilisce i primi limiti di rimpianto sublineari per l'RL online con approssimazione di funzioni generale sotto JDP.
2. Limiti di Rimpianto:
   • Per MDP stocastici generali (Algoritmo 1), il rimpianto scala come $\tilde{O}(K^{3/5})$, dipendendo dal parametro di copertura $C_{cov}$, che caratterizza la difficoltà di esplorazione.
   • Per MDP deterministici con ricompense basate sull'esito (Algoritmo 2), viene raggiunto un limite simile di $\tilde{O}(K^{3/5})$ sotto l'ipotesi più debole di realizzabilità.
   • Questi limiti corrispondono ai risultati dello stato dell'arte per il caso di approssimazione lineare nell'impostazione senza modello, nonostante la maggiore complessità delle classi di funzioni generali.
3. Prodotti Derivati Non Privati: L'analisi produce nuovi limiti di rimpianto per l'RL non privato sotto vincoli di adattabilità (batching di dimensione fissa). Specificamente, mostra che un rimpianto di $\tilde{O}(\sqrt{K})$ è ottenibile con $\sqrt{K}$ aggiornamenti sotto la condizione di copertura, completando i risultati esistenti basati sulla classe della Condizione di Eluder.
4. Chiarificazione della Letteratura sugli MDP Lineari: Gli autori identificano divari fondamentali nelle recenti affermazioni di limiti di rimpianto migliorati di $\tilde{O}(\sqrt{K})$ per l'RL privato con MDP lineari. Sostengono che le prove esistenti, basate su "commutazioni rare della politica" e trucchi del determinante, falliscono sotto vincoli di privacy perché la necessaria monotonia della matrice di progetto viene rotta dall'iniezione di rumore di privacy.

Risultati e Analisi
L'analisi teorica si basa sulla costante di copertura, una misura di complessità introdotta da Xie et al. [XFBJK22], che generalizza il concetto di difficoltà di esplorazione oltre le impostazioni lineari. La bozza di dimostrazione coinvolge:

• La decomposizione del rimpianto in un termine relativo all'"errore di addestramento" (perdita di Bellman) e un errore "on-policy" (test).
• L'uso del Meccanismo Esponenziale per limitare la deviazione tra la funzione selezionata e quella ottima (costo della privacy).
• La derivazione di una nuova disuguaglianza per relazionare l'errore on-policy all'errore di addestramento in presenza di batching, utilizzando la costante di copertura per limitare lo spostamento di distribuzione tra la politica di raccolta dati e la politica corrente.
• L'ottimizzazione della dimensione del batch $B$ e del parametro di temperatura $\eta$ per bilanciare il compromesso tra freschezza delle informazioni (rimpianto) e costo della privacy.

L'articolo include una simulazione di concetto in un contesto deterministico di ricompense basate sull'esito. I risultati dimostrano il previsto compromesso privacy-utilità: una privacy più forte (minore $\epsilon$) porta a una convergenza più lenta (più episodi di plateau), mentre il batching introduce un ritardo moderato rispetto all'apprendimento non privato e non in batch.

Significato
L'articolo afferma di fornire la prima fondazione teorica principiale per l'RL privato in contesti che riflettono applicazioni moderne, come quelle che coinvolgono Modelli Linguistici su Grande Scala (LLM) e approssimatori di funzioni complessi e non lineari. Dimostrando che la scalabilità del rimpianto $\tilde{O}(K^{3/5})$ ottenibile nelle impostazioni lineari si estende a classi di funzioni generali sotto JDP, il lavoro colma un divario significativo tra la teoria della preservazione della privacy e i sistemi RL pratici. Inoltre, esponendo difetti nella letteratura recente riguardante gli MDP lineari, l'articolo mira a chiarire il panorama dell'RL privato, assicurando che i futuri avanzamenti teorici siano costruiti su solide fondamenta analitiche. Il framework è presentato come un approccio modulare che può essere adattato a vari meccanismi di privacy e classi di funzioni.