Technische Samenvatting: Over de Steekproefcomplexiteit van Differentieel Privé Beleidsoptimalisatie

Probleemstelling

Beleidsoptimalisatie (Policy Optimization, PO) is een fundamenteel onderdeel van moderne Versterkende Leer (Reinforcement Learning, RL), met toepassingen variërend van robotica tot het trainen van Large Language Models (LLM). De implementatie van PO in gevoelige domeinen (bijvoorbeeld gepersonaliseerde gezondheidszorg, LLM-afstemming) roept echter aanzienlijke privacybezorgdheden op, aangezien recente empirisch werk heeft aangetoond dat standaardalgoritmen zoals GRPO privé-informatie kunnen lekken.

Hoewel Differentiële Privacy (DP) goed gevestigd is in toezichtleren, stelt de toepassing ervan op PO unieke uitdagingen. Standaard DP-definities gaan uit van een vast dataset waar de privacy-eenheid een enkel datapunt is. Bij PO, en met name bij on-policy learning, is het dataset dynamisch; acties worden bemonsterd op basis van het huidige beleid, wat betekent dat het wijzigen van één datapunt de volledige trajecten van toekomstige steekproeven kan veranderen. Bijgevolg zijn bestaande definities van DP niet direct toepasbaar, en blijven de kosten in termen van steekproefcomplexiteit die door privacybeperkingen in PO worden veroorzaakt, theoretisch onverkend.

Methodologie

1. Herdefiniëren van Differentiële Privacy voor PO

De auteurs formaliseren eerst een definitie van DP die is toegesneden op PO. Geput uit literatuur over privé online bandieten, definiëren zij het dataset niet als een vaste set van i.i.d. steekproeven, maar als een set van $N$ unieke "gebruikers" (bijvoorbeeld patiënten of prompts). Elke gebruiker interageert met de agent om een traject $(x, y, r)$ te genereren.

• Privacy-eenheid: Een enkele "gebruiker".
• Definitie: Een algoritme is $(\epsilon, \delta)$-DP als het wijzigen van één gebruiker in het dataset de verdeling van het uiteindelijke output-beleid niet significant verandert.
• Onderscheid: Dit verschilt van standaard DP in toezichtleren omdat de "buur"-relatie wordt gedefinieerd door de initiële staat van de gebruiker en hun interactiegeschiedenis, in plaats van een statisch record.

2. Een Unificerend Meta-algoritme

Om diverse PO-algoritmen binnen een unificerend kader te analyseren, stellen de auteurs een Meta-algoritme voor (Algoritme 1). Dit is een gebatcht, één-pass algoritme waarbij:

• Bij elke iteratie $t$ de leerder een verse batch van $m$ steekproeven verzamelt van $m$ verschillende gebruikers.
• Een PrivUpdate-oracle wordt aangeroepen om het volgende beleid $\theta_{t+1}$ te berekenen op basis van de huidige batch en privacybeperkingen.
• Privacygarantie: Door gebruik te maken van de eigenschap van parallelle compositie van DP, als de PrivUpdate-oracle voldoet aan standaard DP (Definitie 1), voldoet het gehele meta-algoritme aan de voorgestelde PO-DP-definitie (Definitie 2).

3. Instantiaties

Het kader wordt geïnstancierd voor drie veelgebruikte PO-algoritmen:

• DP-PG (Policy Gradient): Gebruikt een REINFORCE-stijl gradiëntschatter met Gaussisch ruis toegevoegd aan de gradiëntupdate (Algoritme 2).
• DP-NPG (Natural Policy Gradient): Reduceert de PO-update tot een privé regressieprobleem (minimaliseren van kwadratisch verlies tussen de voordeelfunctie en een lineaire benadering). Het maakt gebruik van een privé kleinste-kwadraten-oracle (Algoritme 3).
• DP-REBEL: Vergelijkbaar met DP-NPG reduceert het PO tot een reeks privé regressieproblemen over relatieve beloningsverschillen, gebruikmakend van de REBEL-formulering.

Belangrijkste Bijdragen en Resultaten

1. Grenzen voor Steekproefcomplexiteit

Het artikel leidt de eerste reeks grenzen voor steekproefcomplexiteit af voor differentieel privé PO-algoritmen. Het totale aantal bemonsterde trajecten is $N = m \times T$ (batchgrootte $\times$ iteraties).

• DP-PG (Eerste-orde stationair punt):
  Onder aannames van Lipschitz-gladheid bereikt het algoritme een verwachte gekwadrateerde gradiëntnorm van:
  $$\mathbb{E}[\|\nabla J(\theta_U)\|^2] \leq O_\delta\left( \frac{1}{\sqrt{N}} + \left(\frac{\sqrt{d}}{N\epsilon}\right)^{2/3} \right)$$
  Hier vertegenwoordigt de eerste term de niet-privé convergentiesnelheid, terwijl de tweede term de privékosten vertegenwoordigt.

• DP-PG (Globaal optimum):
  Onder aanvullende aannames (Fisher-niet-degeneratie en compatibele functiebenadering) is de gemiddelde regret begrensd. De steekproefcomplexiteit die nodig is om een suboptimaliteitsgaping $\alpha$ te bereiken, is:
  $$N \geq O_\delta\left( \frac{1}{\alpha^4 \gamma^4} + \frac{\sqrt{d}}{\alpha^3 \gamma^3 \epsilon} \right)$$
  waarbij $\gamma$ de ondergrens van de Fisher-informatie is. De privékosten verschijnen als een lagere-orde additieve term.

• DP-NPG en DP-REBEL:
  Door PO te reduceren tot privé regressie, maken de auteurs gebruik van bestaande resultaten uit privé stochastische optimalisatie en privé lineaire regressie.

  • Voor log-lineaire beleidsregels in lage dimensies is de steekproefcomplexiteit ongeveer $O_\delta(d/\alpha^4 + d/(\alpha^3 \epsilon))$.
  • Voor hoge dimensies hangen de grenzen af van de specifieke privé regressie-oracle die wordt gebruikt (bijvoorbeeld exponentiële mechanismen of ISSP), en tonen ze over het algemeen dat privékosten schalen met dimensionaliteit en $1/\epsilon$.

2. Structurele Inzichten

• Privékosten als Lagere-orde Term: Een centraal resultaat is dat de kosten van privacy zich vaak manifesteren als een lagere-orde term in de totale steekproefcomplexiteit. Voor constante $\epsilon$ en dimensie $d$ overheerst de privacy-overhead de convergentiesnelheid niet.
• Rol van Probleemstructuur: Het artikel benadrukt dat structurele eigenschappen van het onderliggende probleem (bijvoorbeeld Fisher-niet-degeneratie, tabulaire softmax-structuren) zowel de statistische als computationele efficiëntie aanzienlijk kunnen verbeteren, soms door afhankelijkheid van problematische parameters zoals $\gamma$ te verwijderen.

3. Empirische Validatie

De auteurs hebben proefconcept-experimenten uitgevoerd in de CartPole-v1-omgeving.

• Opzet: Standaard PG/NPG werd vergeleken met DP-PG en DP-NPG onder privacybudgetten van $\epsilon=5$ en $\epsilon=3$.
• Vondsten:
  • DP-NPG presteerde consequent beter dan DP-PG, wat het voordeel van krommingsbewuste updates zelfs onder privacybeperkingen aantoont.
  • DP-NPG met $\epsilon=5$ bereikte bijna optimale prestaties ($\sim 478$ beloning versus $492$ niet-privé), in overeenstemming met theoretische voorspellingen.
  • Zoals verwacht verslechterden de prestaties naarmate het privacybudget $\epsilon$ afnam.

Betekenis en Aanspraken

Het artikel claimt de theoretische studie van differentieel privé beleidsoptimalisatie te initiëren, met name gericht op steekproefcomplexiteit. De belangrijkste bijdragen zijn:

1. Formele Definitie: Het vaststellen van een rigoureuze definitie van DP voor PO die rekening houdt met on-policy dynamiek en de "gebruiker" als privacy-eenheid.
2. Unificerend Kader: Het bieden van een meta-algoritme dat systematische analyse van PG, NPG en REBEL onder privacybeperkingen mogelijk maakt.
3. Kwantificering van Privékosten: Het aantonen dat privékosten in PO vaak lagere-orde termen zijn, wat suggereert dat privacybehoudende PO theoretisch haalbaar is zonder prohibitieve straffen in steekproefcomplexiteit.
4. Praktische Richtlijnen: Het bieden van inzichten in hoe structurele eigenschappen (zoals Fisher-niet-degeneratie) privékosten kunnen mitigeren, en het leiden van het ontwerp van toekomstige privacybehoudende RL-algoritmen.

De auteurs merken op dat hoewel hun primaire focus theoretisch is, de resultaten klassieke niet-privé grenzen herstellen en de eerste rigoureuze analyse van steekproefcomplexiteit voor privé PO bieden. Zij erkennen beperkingen, zoals de focus op één-pass bemonstering en het ontbreken van evaluaties op grote schaal met real-world datasets, maar benadrukken de brede toepasbaarheid van hun methoden op privacygevoelige domeinen zoals RLHF en medische besluitvorming.