🤖 machine learning

Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses

Dieser Beitrag stellt den ersten primal-dualen Policy-Optimierungsalgorithmus für Online-Adversarial-Linear-CMDPs mit endlichem Horizont und stochastischen Kosten vor, der durch neuartige gewichtete LogSumExp-Softmax-Policies, periodisches Policy-Mixing und regularisierte duale Updates sublineare Regret- und Verletzungsuntergrenzen von $\widetilde{\mathcal{O}}(K^{3/4})$ erreicht.

Ursprüngliche Autoren: Kihyun Yu, Seoungbin Bae, Dabeen Lee

Veröffentlicht 2026-05-13

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Kihyun Yu, Seoungbin Bae, Dabeen Lee

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind der Kapitän eines Schiffes, das durch ein stürmatisches Meer navigiert. Ihr Ziel ist es, den Bestimmungsort so schnell wie möglich zu erreichen (Minimierung des Verlusts), aber Sie haben eine strikte Regel: Sie dürfen nicht den Treibstoff ausgehen lassen (Einhaltung eines Kostenbudgets).

In den meisten früheren Studien war das Wetter vorhersehbar. Der Wind wehte in einem konstanten Muster, oder die Wellen folgten einem bekannten Zeitplan. Der Bordcomputer des Schiffes konnte das „durchschnittliche" Wetter lernen und eine sichere, effiziente Route planen.

Das Problem: Das Wetter ist nun feindselig
Dieser Artikel behandelt ein viel schwierigeres Szenario: adversarielle Umgebungen. Stellen Sie sich vor, das Wetter ist nicht nur zufällig; es versucht aktiv, Sie zu täuschen. Der Wind könnte plötzlich drehen, um Sie von der Kurslinie zu drängen, oder die Wellen könnten unvorhersehbar ansteigen, nicht wegen der Natur, sondern weil ein „Adversary" die Regeln jeden einzelnen Tag ändert, um Ihre Aufgabe zu erschweren.

Darüber hinaus haben Sie zwei Arten von Rückmeldungen:

Vollständige Information über den Sturm: Sie können Wind und Wellen klar sehen (dies ist der Verlust).
Blindstellen beim Treibstoff: Sie erfahren erst, wie viel Treibstoff Sie verbraucht haben, nachdem Sie ihn verbrannt haben, und Sie sehen den Kraftstoffmesser für die Zukunft nicht (dies ist die Kosten).

Die Lösung: Ein intelligenter, flexibler Kapitän
Die Autoren, Kihyun Yu, Seoungbin Bae und Dabeen Lee, schlagen einen neuen Algorithmus (eine Reihe von Anweisungen für den Bordcomputer) vor, der Primal-Dual Policy Optimization genannt wird.

So funktioniert es, unter Verwendung einfacher Analogien:

1. Die „Weighted LogSumExp"-Strategie (Die flexible Karte)

Normalerweise folgt ein Schiff einer einzigen, starren Karte. Wenn die Karte sagt „links abbiegen", biegt es links ab. Aber in einer feindseligen Umgebung versagt eine starre Karte.

Die Autoren haben eine neue Art von Karte erfunden, die Weighted LogSumExp Softmax Policy genannt wird.

Die Analogie: Stellen Sie sich vor, Ihr Kapitän wählt nicht nur einen Pfad aus. Stattdessen führt er einen „mentalen Stapel" aller Pfade, die er in der Vergangenheit versucht hat.
Die Wendung: Wenn ein neuer, trickreicher Wind aufkommt, betrachtet der Kapitän nicht nur den neuesten Wind. Er betrachtet die Winde der letzten Tage, gewichtet sie jedoch unterschiedlich. Manche Tage sind wichtiger als andere.
Warum es hilft: Dies ermöglicht dem Schiff, sich sofort an den „Adversary" anzupassen, der das Wetter verändert, anstatt festzustecken und einer alten, nutzlosen Karte zu folgen.

2. „Periodisches Mischen" (Das Sicherheits-Reset)

In der Vergangenheit versuchten Algorithmen, ihre Strategien zu mischen (Hinzufügen eines kleinen Anteils an Zufälligkeit oder eines „sicheren Standardpfads") bei jedem einzelnen Schritt.

Das Problem: Wenn Sie Ihre Strategie zu oft mischen, wird Ihre „mentale Karte" so kompliziert und unübersichtlich, dass der Computer nicht schnell genug den besten Zug berechnen kann. Es ist, als würde man versuchen, eine Karte zu lesen, die ständig mit zu vielen Tintenschichten neu gezeichnet wird.
Die Innovation: Die Autoren erkannten, dass sie nicht jeden Tag mischen müssen. Sie „resetten" oder „mischen" die Strategie nur alle paar Tage (genauer gesagt, alle $K^{3/4}$ Episoden).
Das Ergebnis: Dies hält die Karte sauber genug, um schnell berechnet zu werden, aber häufig genug, um sicher zu bleiben. Es ist, als würde man den Kompass einmal pro Woche überprüfen und den Kurs neu kalibrieren, anstatt jede Minute.

3. Der „regularisierte" Kraftstoffmesser (Das Dual-Update)

Das Schiff muss sicherstellen, dass der Treibstoff nicht ausgeht. In mathematischen Begriffen ist dies die Dual-Variable.

Das Problem: Wenn das Schiff wenig Treibstoff hat, könnte der Computer in Panik geraten und überkorrigieren, wild zwischen „schnell fahren" und „komplett anhalten" schwankend. Diese Instabilität lässt das Schiff abstürzen.
Die Innovation: Die Autoren fügten einen „Regularisierungsterm" hinzu. Denken Sie daran als einen Stoßdämpfer am Kraftstoffmesser.
Wie es funktioniert: Wenn der Treibstoffstand zu hoch oder zu niedrig wird, zieht der Stoßdämpfer die Entscheidung sanft zurück zu einem stabilen Zentrum. Er verhindert, dass das Schiff wilde, verzweifelte Manöver durchführt, und stellt sicher, dass das Treibstoffbudget auch dann eingehalten wird, wenn das Wetter versucht, das Schiff zu täuschen.

Der große Sieg

Der Artikel beweist mathematisch, dass dieser neue Kapitän (Algorithmus) der erste ist, der diese spezifische Mischung erfolgreich bewältigt:

Feindseliges, sich änderndes Wetter (Adversarial Loss).
Blindes Treibstoff-Feedback (Stochastic Cost).
Ein massiver Ozean mit zu vielen möglichen Orten, um sie einzeln zu kartieren (Linear Function Approximation).

Das Ergebnis:
Das Schiff erreicht seinen Bestimmungsort mit einem „Regret" (wie viel langsamer es im Vergleich zum perfekten Kapitän war) und einer „Violation" (wie stark es das Treibstoffbudget überschritten hat), die sehr langsam wachsen, je länger die Reise wird. Wenn Sie die Länge der Reise verdoppeln, verdoppeln sich die Fehler nicht; sie wachsen viel langsamer (sublinear).

Zusammenfassung:
Der Artikel stellt ein intelligentes Navigationssystem vor, das eine Welt bewältigen kann, in der sich die Regeln böswillig ändern. Dies erreicht es, indem es ein flexibles, gewichtetes Gedächtnis der Vergangenheit bewahrt, seine Strategie nur bei Bedarf zurücksetzt, um effizient zu bleiben, und einen stoßdämpfenden Mechanismus verwendet, um sicherzustellen, dass seine Sicherheitsbeschränkungen nicht brechen. Es ist ein Durchbruch für die Sicherung und Effektivität von KI in unvorhersehbaren, realen Situationen.

Technische Zusammenfassung: Primal-Duale Policy-Optimierung für lineare CMDPs mit adversarischen Verlusten

Problemstellung

Dieser Artikel behandelt die Herausforderung des Sicheren Reinforcement Learning (RL) in Umgebungen, in denen Sicherheitsbedingungen trotz adversarer Störungen erfüllt werden müssen. Konkret betrachten die Autoren Finite-Horizont-Adversarial Lineare Constrained Markov Decision Processes (CMDPs).

Die Problemstellung wird durch das Tupel $\mathcal{M} = (H, \mathcal{S}, \mathcal{A}, \{P_h\}, \{f^k\}, \{g^k\}, s_1, b)$ definiert, wobei:

Adversarische Verluste: Die Verlustfunktionen $f^k = \{f^k_h\}$ werden zu Beginn jeder Episode $k$ von einem Gegner beliebig gewählt (Feedback mit vollständiger Information). Diese Verluste werden nicht aus einer festen Verteilung gezogen.
Stochastische Kosten: Die Kostenfunktionen $g^k = \{g^k_h\}$ werden i.i.d. aus einer festen Verteilung $G$ gesampelt (Bandit-Feedback) und repräsentieren Sicherheitsbedingungen.
Lineare Struktur: Die Übergangskerne, Verlustfunktionen und Kostenfunktionen besitzen eine lineare Struktur bezüglich einer bekannten Feature-Mapping-Funktion $\phi: \mathcal{S} \times \mathcal{A} \to \mathbb{R}^d$ .
Zielsetzung: Der Agent sucht eine Policy, die den kumulierten erwarteten Verlust minimiert und gleichzeitig sicherstellt, dass die erwarteten kumulierten Kosten ein Budget $b$ nicht überschreiten.

Die Leistung wird durch Regret (kumulierte Verlustdifferenz im Vergleich zur optimalen Policy) und Verletzung der Nebenbedingung (kumulierter Überschuss der Kosten über das Budget hinaus) gemessen. Das Ziel ist es, sublineare Schranken für beide Metriken zu erreichen.

Methodik

Die Autoren schlagen einen Primal-Dualen Policy-Optimierungsalgorithmus (Algorithmus 1) vor, der für das Zusammenspiel zwischen adversarischen Verlusten und stochastischen Nebenbedingungen in einem Setting mit linearer Funktionsapproximation entwickelt wurde. Der Algorithmus integriert vier Hauptkomponenten:

Epochen-Initialisierung und Feature-Kontraktion:
Der Algorithmus arbeitet in Epochen. Eine Epoche beginnt, wenn die Determinante der Designmatrix $\Lambda^k_h$ um einen multiplikativen Faktor zunimmt. Bei der Initialisierung wird die Policy auf eine uniforme Policy zurückgesetzt und der duale Variable auf Null. Entscheidend ist, dass der Algorithmus eine Feature-Kontraktion anwendet, bei der das ursprüngliche Feature $\phi$ mittels einer Sigmoid-Funktion gestaucht wird, um ein unkontrolliertes Anwachsen der Q-Funktions-Schätzungen zu verhindern. Diese Technik, adaptiert von Cassel & Rosenberg (2024), vereinfacht die Repräsentation der Policy für Argumente bezüglich der Überdeckungszahl.
Policy-Ausführung und Schätzung:
In jeder Episode führt der Agent Aktionen basierend auf der aktuellen Policy aus, beobachtet den adversarischen Verlust und die stochastischen Kosten und aktualisiert die Designmatrix. Anschließend schätzt er die Parameter für die Verlust- und Kostenfunktionen und berechnet Q-Funktions-Schätzungen ( $\hat{Q}$ ) sowie Wertfunktions-Schätzungen ( $\hat{V}$ ) unter Verwendung der kontrahierten Features und optimistischer Boni.
Periodisches Policy-Mixing:
Eine zentrale Innovation ist das periodische Policy-Mixing. Anstatt die Policy in jeder Episode zu mischen (d. h. sie in Richtung einer uniformen Policy zu stören), wendet der Algorithmus das Mischen nur einmal alle $K^B$ Episoden an (wobei $B=3/4$ ).
- Motivation: Häufiges Mischen ist notwendig, um die duale Variable zu begrenzen (via Drift-Analyse), erhöht jedoch die Komplexität der Policy-Klasse (Überdeckungszahl). Periodisches Mischen balanciert diese konkurrierenden Anforderungen aus.
- Mechanismus: Alle $K^{3/4}$ Episoden wird die aktuelle Policy $\hat{\pi}^k$ mit der uniformen Policy $\pi_{unif}$ durch eine konvexe Kombination gemischt: $\tilde{\pi}^k = (1-\theta)\hat{\pi}^k + \theta\pi_{unif}$ .
Regularisierte duale Aktualisierung:
Die duale Variable $Y^k$ (assoziiert mit der Kostennebenbedingung) wird mittels eines regularisierten Gradientenanstiegs aktualisiert:
$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]_+$
Die Regularisierungsterme ( $-4\alpha\eta H^3 Y^k$ und Konstanten) sind so gestaltet, dass sie die duale Variable in Richtung Null ziehen, was eine Lyapunov-Drift-Analyse ermöglicht, um $Y^k$ zu begrenzen, ohne sich auf starke Dualitätsannahmen zu verlassen, die in adversarischen Settings versagen.
Gewichtete LogSumExp-Softmax-Policies:
Die resultierende Policy-Klasse ist eine gewichtete LogSumExp-Softmax. Aufgrund des periodischen Mixings ist die Policy nicht einfach eine Exponentialfunktion der Summe der Q-Funktionen, sondern eine gewichtete Summe von Exponentialfunktionen partieller Summen der Q-Funktions-Schätzungen. Diese Struktur ermöglicht es der Policy, sich an adversarisch gewählte Verluste anzupassen, während eine handhabbare Überdeckungszahl erhalten bleibt.

Hauptbeiträge

Erste sublineare Schranken für adversarische lineare CMDPs:
Der Artikel stellt den ersten Algorithmus vor, der sublineare Regret- und Verletzungs-Schranken für lineare CMDPs mit adversarischen Verlusten und stochastischen Kosten erreicht. Die Schranken betragen $\tilde{O}(K^{3/4})$ , wobei $K$ die Anzahl der Episoden ist.
Neues Argument für die Überdeckungszahl:
Die Autoren etablieren ein neuartiges Argument für die Überdeckungszahl der gewichteten LogSumExp-Softmax-Policies. Im Gegensatz zu Standard-Softmax-Policies, bei denen die Gewichte uniform sind, führt der Mischprozess variierende Gewichtsparameter $\zeta_i$ ein. Die Autoren beweisen, dass der Logarithmus der Überdeckungszahl für diese Klasse als $\tilde{O}(n^2 d^2)$ wächst, wobei $n$ die Anzahl der Mischschritte und $d$ die Feature-Dimension ist. Dieses Ergebnis ist nicht-trivial, da die Gewichtsparameter sowohl vom Mischparameter als auch von den Q-Funktions-Schätzungen abhängen.
Algorithmische Komponenten zur Kontrolle:
Der Artikel führt zwei neuartige Komponenten ein, um gemeinsam die Überdeckungszahl und die duale Variable zu kontrollieren:
- Periodisches Policy-Mixing: Reguliert die Häufigkeit des Mischens, um zu verhindern, dass die Überdeckungszahl zu stark wächst (was bei $O(K)$ Mischschritten geschehen würde), während es dennoch häufig genug auftritt, um die duale Variable zu begrenzen.
- Regularisierte duale Aktualisierung: Eine neue Aktualisierungsregel, die einen Regularisierungsterm integriert, um eine driftbasierte Analyse zu ermöglichen, was die Begrenzung der dualen Variable ohne starke Dualität erlaubt.

Ergebnisse

Theoretische Garantien:
Unter der Slater-Bedingung (Annahme 1) und unter der Annahme $H^2 \leq K$ erreicht der Algorithmus mit einer Wahrscheinlichkeit von mindestens $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)$
Verletzung der Nebenbedingung: $\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 Metriken skalieren sublinear mit $K$ (insbesondere $K^{3/4}$ ), was darauf hindeutet, dass der durchschnittliche Regret und die durchschnittliche Verletzung der Nebenbedingung gegen Null konvergieren, wenn die Anzahl der Episoden zunimmt.

Numerische Experimente:
Der Algorithmus wurde an einem modifizierten Job-Scheduling-CMDP mit adversarischen Verlusten evaluiert. Über $100.000$ Episoden hinweg:

Regret: Wuchs sublinear, was die theoretische Schranke bestätigt.
Verletzung der Nebenbedingung: Wuchs anfangs schnell, konvergierte jedoch nach etwa 45.000 Episoden gegen Null, was die Fähigkeit des Algorithmus validiert, Sicherheitsbedingungen langfristig einzuhalten.

Bedeutung und Behauptungen

Der Artikel beansprucht, der erste beweisbar effiziente Algorithmus für sicheres RL mit linearer Funktionsapproximation in adversarischen Settings zu sein. Seine Bedeutung liegt in der Überbrückung der Lücke zwischen:

Tabellarischen adversarischen CMDPs: Frühere Arbeiten (z. B. Qiu et al., 2020) behandelten adversarische Settings, waren jedoch auf kleine, endliche Zustandsräume beschränkt.
Linearen stochastischen CMDPs: Frühere Arbeiten (z. B. Ghosh et al., 2022) handhabten große Zustandsräume, gingen jedoch von stationären (stochastischen) Umgebungen aus.

Durch die Einführung der gewichteten LogSumExp-Softmax-Policy und der Strategie des periodischen Mixings demonstrieren die Autoren, dass es möglich ist, große Zustandsräume (via linearer Approximation) und adversarische Verluste gleichzeitig zu handhaben. Der Artikel vermerkt bescheiden, dass zwar $\tilde{O}(K^{3/4})$ erreicht wird, die optimale Schranke von $\tilde{O}(\sqrt{K})$ jedoch eine offene Frage für dieses spezifische Setting bleibt, insbesondere hinsichtlich des Trade-offs zwischen Mischschritten und Überdeckungszahlen. Die Arbeit hebt zudem die Schwierigkeit hervor, dualen Updates auf Basis von Besetzungsmaßen auf Policy-basierte Methoden in adversarischen linearen CMDPs zu erweitern, und rechtfertigt damit den vorgeschlagenen Ansatz der primal-dualen Policy-Optimierung.