Technische Samenvatting: Primaal-Duale Policy Optimalisatie voor Lineaire CMDP's met Adversariële Verliezen

Probleemstelling

Dit artikel adresseert de uitdaging van Veilig Versterkend Leren (RL) in omgevingen waar veiligheidsbeperkingen moeten worden nageleefd ondanks adversariële verstoringen. Specifiek beschouwen de auteurs Lineaire Beperkte Markov Beslissingsprocessen (CMDP's) met Adversariële Verliezen en een Eindige Horizont.

De setting wordt gedefinieerd door de tuple $\mathcal{M} = (H, \mathcal{S}, \mathcal{A}, \{P_h\}, \{f^k\}, \{g^k\}, s_1, b)$, waarbij:

• Adversariële Verliezen: De verliesfuncties $f^k = \{f^k_h\}$ worden willekeurig gekozen door een adversary aan het begin van elke episode $k$ (feedback met volledige informatie). Deze verliezen worden niet getrokken uit een vaste verdeling.
• Stochastische Kosten: De kostenfuncties $g^k = \{g^k_h\}$ worden i.i.d. getrokken uit een vaste verdeling $G$ (bandit-feedback), wat veiligheidsbeperkingen vertegenwoordigt.
• Lineaire Structuur: De overgangskernen, verliesfuncties en kostenfuncties bezitten een lineaire structuur met betrekking tot een bekende feature-mapping $\phi: \mathcal{S} \times \mathcal{A} \to \mathbb{R}^d$.
• Doel: De agent zoekt een beleid dat de cumulatieve verwachte verliezen minimaliseert, terwijl ervoor wordt gezorgd dat de cumulatieve verwachte kosten een begroting $b$ niet overschrijden.

De prestatie wordt gemeten aan de hand van Regret (cumulatief verschil in verliezen vergeleken met het optimale beleid) en Beperkingsovertreding (cumulatieve extra kosten boven de begroting). Het doel is om sublineaire grenzen voor beide metrieken te bereiken.

Methodologie

De auteurs stellen een Primaal-Duale Policy Optimalisatie algoritme voor (Algoritme 1) dat is ontworpen om de wisselwerking tussen adversariële verliezen en stochastische beperkingen in een setting met lineaire functiebenadering te hanteren. Het algoritme integreert vier hoofdbestanddelen:

1. Epoch-initialisatie en Feature-contractie:
   Het algoritme werkt in epochs. Een epoch begint wanneer de determinant van de ontwerp-matrix $\Lambda^k_h$ toeneemt met een multiplicatieve factor. Bij initialisatie wordt het beleid gereset naar een uniform beleid en wordt de duale variabele gereset naar nul. Cruciaal maakt het algoritme gebruik van feature-contractie, waarbij de oorspronkelijke feature $\phi$ wordt verkleind met een sigmoid-functie om te voorkomen dat schattingen van de Q-functie onbeheerd oplopen. Deze techniek, overgenomen van Cassel & Rosenberg (2024), vereenvoudigt de beleidsrepresentatie voor argumenten rondom overdekkingsgetallen.

2. Beleidsexecutie en Schatting:
   In elke episode voert de agent acties uit op basis van het huidige beleid, observeert de adversariële verliezen en stochastische kosten, en werkt de ontwerp-matrix bij. Vervolgens schat het de parameters voor de verlies- en kostenfuncties en berekent het schattingen van de Q-functie ($\hat{Q}$) en de waarde-functie ($\hat{V}$) met behulp van de gecontracteerde features en optimistische bonussen.

3. Periodieke Beleidmixing:
   Een kerninnovatie is periodieke beleidmixing. In plaats van het beleid te mixen (het te verstoren richting een uniform beleid) in elke episode, past het algoritme mixing slechts één keer elke $K^B$ episodes toe (waarbij $B=3/4$).

   • Motivatie: Frequente mixing is noodzakelijk om de duale variabele te begrenzen (via drift-analyse), maar verhoogt de complexiteit van de beleidsklasse (overdekkingsgetal). Periodieke mixing balanceert deze concurrerende eisen.
   • Mecanisme: Elke $K^{3/4}$ episodes wordt het huidige beleid $\hat{\pi}^k$ gemixt met het uniform beleid $\pi_{unif}$ via een convexe combinatie: $\tilde{\pi}^k = (1-\theta)\hat{\pi}^k + \theta\pi_{unif}$.

4. Geregulariseerde Duale Update:
   De duale variabele $Y^k$ (geassocieerd met de kostenbeperking) wordt bijgewerkt met een geregulariseerde gradiënt-ascent stap:
   $$Y^{k+1} \leftarrow \left[ (1 - 4\alpha\eta H^3)Y^k + \eta(\hat{V}^k_{g,1}(s_1) - b - 4\alpha H^3 - 4\theta H^2) \right]_+$$
   De regularisatietermen ($-4\alpha\eta H^3 Y^k$ en constanten) zijn ontworpen om de duale variabele naar nul te trekken, wat een Lyapunov-drift-analyse mogelijk maakt om $Y^k$ te begrenzen zonder te vertrouwen op sterke dualiteitsaannames die in adversariële settings falen.

5. Gewogen LogSumExp Softmax-beleiden:
   De resulterende beleidsklasse is een gewogen LogSumExp softmax. Vanwege de periodieke mixing is het beleid geen eenvoudige exponentiële van de som van Q-functies, maar een gewogen som van exponentiële van partiële sommen van Q-functieschattingen. Deze structuur stelt het beleid in staat zich aan te passen aan willekeurig gekozen verliezen, terwijl een hanteerbaar overdekkingsgetal behouden blijft.

Belangrijkste Bijdragen

1. Eerste Sublineaire Grenzen voor Adversariële Lineaire CMDP's:
   Het artikel presenteert het eerste algoritme dat sublineaire regret- en beperkingsovertredingsgrenzen bereikt in de setting van lineaire CMDP's met adversariële verliezen en stochastische kosten. De grenzen zijn $\tilde{O}(K^{3/4})$, waarbij $K$ het aantal episodes is.

2. Nieuw Argument voor Overdekkingsgetallen:
   De auteurs stellen een nieuw argument voor overdekkingsgetallen op voor gewogen LogSumExp softmax-beleiden. In tegenstelling tot standaard softmax-beleiden waarbij gewichten uniform zijn, introduceert het mixingsproces variërende gewichtsparameters $\zeta_i$. De auteurs bewijzen dat de logarithme van het overdekkingsgetal voor deze klasse groeit als $\tilde{O}(n^2 d^2)$, waarbij $n$ het aantal mixingsstappen is en $d$ de feature-dimensie. Dit resultaat is niet-triviaal omdat de gewichtsparameters afhankelijk zijn van zowel de mixingsparameter als Q-functieschattingen.

3. Algoritmische Componenten voor Controle:
   Het artikel introduceert twee nieuwe componenten om gezamenlijk het overdekkingsgetal en de duale variabele te controleren:

   • Periodieke Beleidmixing: Reguleert de frequentie van mixing om te voorkomen dat het overdekkingsgetal te groot wordt (wat zou gebeuren bij $O(K)$ mixingsstappen), terwijl het toch frequent genoeg voorkomt om de duale variabele te begrenzen.
   • Geregulariseerde Duale Update: Een nieuwe update-regel die een regularisatieterm bevat om drift-gebaseerde analyse mogelijk te maken, waardoor het begrenzen van de duale variabele mogelijk wordt in afwezigheid van sterke dualiteit.

Resultaten

Theoretische Garanties:
Onder de Slater-conditie (Aanneming 1) en aannemende dat $H^2 \leq K$, bereikt het algoritme met een waarschijnlijkheid van ten minste $1-\delta$:

• Regret: $\tilde{O}\left(\sqrt{d^3}H^4 K^{3/4} + dH^3 K^{3/4} + d^3 H^4 K^{1/2} + \frac{H^6}{\gamma^2} K^{1/4} + \frac{dH^6}{\gamma^2}\right)$
• Beperkingsovertreding: $\tilde{O}\left(\frac{dH^5}{\gamma} K^{3/4} + \sqrt{d^3}H^4 K^{3/4} + d^3 H^4 K^{1/2}\right)$

Beide metrieken schalen sublineair met $K$ (specifiek $K^{3/4}$), wat aangeeft dat de gemiddelde regret en gemiddelde beperkingsovertreding naar nul convergeren naarmate het aantal episodes toeneemt.

Numerieke Experimenten:
Het algoritme werd geëvalueerd op een aangepaste job-scheduling CMDP met adversariële verliezen. Over $100.000$ episodes:

• Regret: Groeide sublineair, wat de theoretische grens bevestigde.
• Beperkingsovertreding: Groeide aanvankelijk snel maar convergeerde naar nul na ongeveer 45.000 episodes, wat de capaciteit van het algoritme valideert om op de lange termijn aan veiligheidsbeperkingen te voldoen.

Betekenis en Claims

Het artikel claimt het eerste bewezen efficiënte algoritme te zijn voor veilig RL met lineaire functiebenadering in adversariële settings. De betekenis ligt in het overbruggen van de kloof tussen:

1. Tabulaire Adversariële CMDP's: Eerdere werken (bijv. Qiu et al., 2020) hanteerden adversariële settings maar waren beperkt tot kleine, eindige toestandenruimtes.
2. Lineaire Stochastische CMDP's: Eerdere werken (bijv. Ghosh et al., 2022) hanteerden grote toestandenruimtes maar namen stationaire (stochastische) omgevingen aan.

Door de invoering van het gewogen LogSumExp softmax-beleid en de periodieke mixingsstrategie, demonstreren de auteurs dat het mogelijk is om grote toestandenruimtes (via lineaire benadering) en adversariële verliezen gelijktijdig te hanteren. Het artikel merkt nederig op dat hoewel $\tilde{O}(K^{3/4})$ wordt bereikt, de optimale $\tilde{O}(\sqrt{K})$-grens een open vraag blijft voor deze specifieke setting, met name wat betreft de afweging tussen mixingsstappen en overdekkingsgetallen. Het werk benadrukt ook de moeilijkheid om dual-updates gebaseerd op bezettingsmaten uit te breiden naar op beleid gebaseerde methoden in adversariële lineaire CMDP's, wat de voorgestelde aanpak van primaal-duale policy optimalisatie rechtvaardigt.