Towards Differentially Private Reinforcement Learning with General Function Approximation

Technische Samenvatting: Op weg naar differentieel privé versterkend leren met algemene functiebenadering

Probleemstelling
Dit artikel adresseert de uitdaging om sample-efficiënt online versterkend leren (RL) te realiseren onder formele privacygaranties wanneer de omgeving wordt gemodelleerd met algemene functiebenadering. Waar eerdere theoretisch werk over differentieel privé (DP) RL sublineaire spijtbetalinggrenzen heeft vastgesteld, zijn deze resultaten grotendeels beperkt tot tabulaire omgevingen of lineaire functiebenaderingssettings. De auteurs identificeren een kritieke kloof: het uitbreiden van deze garanties naar algemene, niet-lineaire functieklassen (bijvoorbeeld neurale netwerken of complexe hypotheseklassen) blijft een open probleem. De kernvraag is of sublineaire spijt bereikbaar is voor privé RL met algemene functiebenadering onder Gecombineerde Differentiële Privacy (JDP), een verzwakking van standaard DP die geschikt is voor gepersonaliseerd RL waarbij individuele gebruikersacties privé moeten blijven terwijl het globale beleid wordt geleerd.

Methodologie
De auteurs stellen een modelvrij RL-kader voor dat drie belangrijke algoritmische componenten integreert om de spanning tussen exploratie, algemene functiebenadering en privacy te hanteren:

1. Onbeperkt optimalisatiedoel: In tegenstelling tot standaard niet-privé RL, dat vaak vertrouwen op optimaalheidsset-gebaseerde beperkte optimalisatie (bijvoorbeeld Upper Confidence Bound-methoden), adopteert de voorgestelde aanpak een onbeperkt optimalisatiedoel. Dit doel balanceert expliciet de geschatte waarde (optimisme) en de statistische fout (Bellman-verlies). Deze formulering vermijdt de moeilijkheid om complexe, data-afhankelijke betrouwbaarheidssets te privatiseren.
2. Exponentiële Mechanisme voor beleidsselectie: Om de selectie van de waardenfunctie (en bijgevolg het beleid) uit een functieklass $\mathcal{F}$ te privatiseren, maakt het algoritme gebruik van het Exponentiële Mechanisme. In plaats van deterministisch de functie te selecteren die de score maximaliseert (wat gevoelige data zou lekken), sampleert het algoritme een functie $f^{(k)}$ met een waarschijnlijkheid evenredig met $\exp(\beta \cdot S(f))$, waarbij $S(f)$ een scoresfunctie is die het optimistische waarde en het Bellman-verlies combineert.
3. Batch-updates van het beleid: Om de cumulatieve privacyverlies (compositie) over $K$ episodes te controleren, update het algoritme het beleid alleen aan het begin van vaste batches van grootte $B$. Binnen een batch blijft het beleid vast. Deze strategie beperkt het aantal keren dat een enkel datapunt deelneemt aan een privé-update, waardoor een sublineaire accumulatie van privacyverlies mogelijk is in plaats van een lineaire.

Het artikel presenteert twee specifieke algoritmen:

• Algoritme 1: Ontworpen voor algemene stochastische MDP's. Het vereist Bellman-volledigheid (de functieklass moet gesloten zijn onder de Bellman-operator) en maakt gebruik van een Bellman-foutverlies met een infimum-correctie om dubbel-steekproefproblemen op te lossen.
• Algoritme 2: Ontworpen voor deterministische MDP's met uitkomstbeloningen (een setting gemotiveerd door toepassingen van Large Language Models). Deze variant verzwakt de vereiste tot realiseerbaarheid (de optimale Q-functie bestaat in de klass) en vervangt het Bellman-foutverlies door een op uitkomst gebaseerd Bellman-residu-verlies, waardoor de noodzaak voor max-min optimalisatie wordt geëlimineerd.

Belangrijkste bijdragen

1. Eerste theoretische garanties voor algemene functiebenadering: Het artikel vestigt de eerste sublineaire spijtbetalinggrenzen voor online RL met algemene functiebenadering onder JDP.
2. Spijtbetalinggrenzen:
   • Voor algemene stochastische MDP's (Algoritme 1) schalen de spijtbetalingen als $\tilde{O}(K^{3/5})$, afhankelijk van de dekbaarheidparameter $C_{cov}$, die de exploratie-moeilijkheid karakteriseert.
   • Voor deterministische MDP's met uitkomstbeloningen (Algoritme 2) wordt een vergelijkbare $\tilde{O}(K^{3/5})$-grens bereikt onder de zwakkere realiseerbaarheidsaanname.
   • Deze grenzen komen overeen met de state-of-the-art resultaten voor het lineaire functiebenaderingsgeval in het modelvrije setting, ondanks de verhoogde complexiteit van algemene functieklassen.
3. Niet-privé bijproducten: De analyse levert nieuwe spijtbetalinggrenzen op voor niet-privé RL onder adaptiviteitsbeperkingen (vaste grootte batching). Specifiek toont het aan dat $\tilde{O}(\sqrt{K})$ spijt bereikbaar is met $\sqrt{K}$ updates onder de dekbaarheidsvoorwaarde, wat bestaande resultaten op basis van de Eluder-voorwaarde-klass aanvult.
4. Verduidelijking van de literatuur over lineaire MDP's: De auteurs identificeren fundamentele gaten in recente claims van verbeterde $\tilde{O}(\sqrt{K})$ spijtbetalinggrenzen voor privé RL met lineaire MDP's. Zij betogen dat bestaande bewijzen die vertrouwen op "zeldzame beleidswisselingen" en determinanttrucs falen onder privacybeperkingen, omdat de nodige monotonie van de ontwerpmatrix wordt verbroken door de injectie van privacyruis.

Resultaten en Analyse
De theoretische analyse rust op de dekbaarheidconstante, een complexiteitsmaat geïntroduceerd door Xie et al. [XFBJK22], die het concept van exploratiemoeilijkheid generaliseert buiten lineaire settings. Het bewissketch omvat:

• Het ontleden van spijt in een term gerelateerd aan de "trainingsfout" (Bellman-verlies) en een "on-policy" (test) fout.
• Het gebruik van het Exponentiële Mechanisme om de afwijking tussen de geselecteerde functie en de optimale functie te begrenzen (privacykosten).
• Het afleiden van een nieuwe ongelijkheid om de on-policy fout te relateren aan de trainingsfout in aanwezigheid van batching, waarbij de dekbaarheidsconstante wordt gebruikt om de distributieverandering tussen het dataverzamelbeleid en het huidige beleid te begrenzen.
• Het optimaliseren van de batchgrootte $B$ en de temperatuurparameter $\eta$ om de afweging tussen informatieversheid (spijt) en privacykosten in evenwicht te brengen.

Het artikel omvat een proof-of-concept simulatie in een deterministische uitkomst-beloningsetting. De resultaten tonen de verwachte privacy-gebruiksafweging aan: sterkere privacy (lagere $\epsilon$) leidt tot langzamere convergentie (hogere plateau-episodes), terwijl batching een matige vertraging introduceert in vergelijking met niet-privé, niet-batched leren.

Betekenis
Het artikel claimt de eerste principiële theoretische basis te bieden voor privé RL in settings die moderne toepassingen weerspiegelen, zoals die waarbij Large Language Models (LLM's) en complexe, niet-lineaire functiebenaderaars betrokken zijn. Door aan te tonen dat de in lineaire settings bereikbare $\tilde{O}(K^{3/5})$ spijtbetalingsschaling uitbreidt naar algemene functieklassen onder JDP, overbrugt dit werk een significante kloof tussen privacybehoudende theorie en praktische RL-systemen. Bovendien, door gebreken in recente literatuur over lineaire MDP's bloot te leggen, streeft het artikel ernaar het landschap van privé RL te verduidelijken, zodat toekomstige theoretische vooruitgang wordt gebouwd op gezonde analytische fundamenten. Het kader wordt gepresenteerd als een modulaire aanpak die kan worden aangepast aan verschillende privacymechanismen en functieklassen.