On Reward-Balancing Methods for Reinforcement Learning

Titel: Über Reward-Balancing-Methoden für das Reinforcement Learning

Autoren: Simone Baroncini, Bahman Gharesifard, Giuseppe Notarstefano

---

1. Problemstellung

Das Paper adressiert das Problem des Reinforcement Learning (RL) im Rahmen von Markov-Entscheidungsprozessen (MDPs) mit diskontiertem Rückfluss. Herkömmliche RL-Algorithmen optimieren typischerweise die Policy, während die Belohnungsfunktion (Reward Function) fest bleibt.

Die Autoren untersuchen einen alternativen Ansatz: Reward-Balancing. Dabei wird die Belohnungsfunktion iterativ so angepasst, dass das RL-Problem in ein äquivalentes Problem transformiert wird, in dem die optimale Policy gierig (greedy) bezüglich der aktuellen Belohnungsfunktion ist. Das Ziel ist es, das Problem zu „normalisieren", sodass die Suche nach der optimalen Policy trivial wird (nämlich die Auswahl der Aktion mit dem höchsten Belohnungswert in jedem Zustand).

Die Herausforderungen bestehen darin:

1. Die Transformationen müssen die optimalen Policies des ursprünglichen Problems erhalten (Invarianz).
2. Der Ansatz muss robust gegenüber Modellunsicherheiten sein, da in der Praxis oft nur Stichproben des Übergangsmodells verfügbar sind.
3. Es muss eine systematische Methode zur Designierung solcher Normalisierungsverfahren gefunden werden, die über den aktuellen Stand der Technik (State-of-the-Art) hinausgeht.

---

2. Methodik und Theoretischer Rahmen

A. Algebraische Struktur und Gruppenwirkung

Die Autoren analysieren die Reward-Balancing-Methoden aus einer algebraischen Perspektive.

• Äquivalenzklassen: Sie definieren eine Gruppe von Transformationen (basierend auf einem injektiven linearen Operator $b$), die auf dem Raum der Belohnungsfunktionen wirkt. Zwei MDPs sind äquivalent, wenn ihre Belohnungsfunktionen in derselben Bahn (Orbit) dieser Gruppenwirkung liegen.
• Vorteils-Erhaltung: Diese Transformationen erhalten die Advantage-Funktion (den Vorteil einer Aktion gegenüber der aktuellen Policy). Das bedeutet, die relative Rangfolge der Aktionen bleibt erhalten, auch wenn sich die absoluten Werte der Wertfunktionen ändern.
• Normalform: Ein MDP ist in „Normalform", wenn die optimale Wertfunktion überall null ist. In diesem Fall ist die optimale Policy einfach diejenige, die in jedem Zustand die Aktion mit dem maximalen (und damit 0) Reward wählt.
• Faserbündel-Struktur: Der Raum der Belohnungsfunktionen wird als Hauptfaserbündel über der Menge der „normalen" Belohnungsfunktionen (Normal Set) interpretiert. Jede Bahn schneidet die Normalmenge in genau einem Punkt.

B. Kontrolltheoretische Neuformulierung

Ein zentraler Beitrag ist die Umformulierung des Normalisierungsproblems als optimaler Steuerungsproblem (Optimal Control Problem, OCP).

• Systemdynamik: Der Reward-Vektor $R_t$ wird als Zustand eines linearen, zeitinvarianten Systems betrachtet: $R_{t+1} = R_t + B \Delta_t$, wobei $\Delta_t$ die Steuergröße (die Transformation) ist.
• Ziel: Die Steuerung soll den Zustand $R_t$ in die Normalmenge (wo $\max R = 0$) stabilisieren.
• Steuerungsgesetze: Es werden verschiedene Steuerungsgesetze analysiert:
  • Ideale Rückführung: Benötigt die exakte Lösung des Problems (nicht praktikabel).
  • Full-Output Feedback: Entspricht der Value Iteration und ist äquivalent zu Algorithmen aus der Literatur.
  • Safe Reward-Balancing (RB-S): Eine nichtlineare Zustandsrückführung, die die Nicht-Positivität der Belohnung garantiert.

C. Umgang mit Modellunsicherheit (Stochastische Szenarien)

Da das wahre Übergangsmodell oft unbekannt ist, wird der Ansatz auf stochastische Szenarien erweitert.

• Stochastisches Update: Anstelle eines festen Modells werden zufällige Realisierungen des Modells (Stichproben) verwendet. Dies führt zu einem System mit multiplikativer Rauschkomponente.
• Robuste Zulässigkeitsmenge: Die Autoren definieren eine modell-invariante zulässige Menge ($F_I(R)$). Dies ist die größte Menge von Steuerungen, die für jede mögliche Realisierung des Modells die Nicht-Positivität der Belohnungsfunktion garantiert.
• Szenario-MPC (Model Predictive Control): Um robuste Normalisierung zu erreichen, wird ein Szenario-basierter MPC-Ansatz vorgeschlagen. Dabei werden über einen Vorhersagehorizont $N$ verschiedene Modell-Szenarien simuliert, und die Steuergröße wird so gewählt, dass der durchschnittliche kumulative Output minimiert wird, unter Einhaltung der robusten Constraints.

---

3. Hauptbeiträge

1. Theoretische Analyse der Transformationsgruppe:

   • Umfassende Charakterisierung der algebraischen Struktur der Reward-Balancing-Transformationen.
   • Beweis, dass der Raum der Belohnungsfunktionen eine Faserbündel-Struktur besitzt und dass in jeder Äquivalenzklasse genau eine Normalform existiert.

2. Kontrolltheoretische Reformulierung:

   • Das Normalisierungsproblem wird als Output-Stabilisierungsproblem und als Optimal Control Problem neu definiert. Dies ermöglicht die Anwendung von Werkzeugen der Regelungstechnik (Constraints, Kostenfunktionen) für das RL-Design.

3. Robustheit und Stochastische Analyse:

   • Entwicklung einer theoretischen Grundlage für Reward-Balancing unter Modellunsicherheit.
   • Herleitung strenger probabilistischer Schranken für die Abweichung zwischen dem stochastischen Update und dem idealen Update basierend auf der Qualität der Modellstichproben.
   • Beweis der geometrischen Konvergenz für robuste Steuerungsgesetze.

4. Szenario-MPC Ansatz:

   • Einführung eines neuen Algorithmus (Szenario-MPC), der Modellunsicherheiten explizit durch Stichproben berücksichtigt und eine robustere Normalisierung als deterministische Methoden ermöglicht.

---

4. Ergebnisse und Simulationen

Die Autoren führen numerische Simulationen durch, um den vorgeschlagenen Szenario-MPC-Ansatz mit dem etablierten „Full-Output Feedback"-Algorithmus (aus der Literatur, z.B. [6]) zu vergleichen.

• Setup: Ein MDP mit zwei Zuständen und fünf Aktionen pro Zustand. Das wahre Modell ist unbekannt; es werden Stichproben mit einer gewissen Fehlermarge (bis zu 0.2 Abweichung) verwendet.
• Ergebnisse:
  • Konvergenz: Beide Methoden erreichen die Normalisierung (die Belohnungswerte konvergieren gegen 0).
  • Performance: Der Szenario-MPC zeigt eine signifikant höhere Wahrscheinlichkeit, die exakte optimale Policy zu finden, insbesondere wenn die Modellunsicherheit hoch ist.
  • Robustheit: Während der Full-Output-Feedback-Algorithmus unter Unsicherheit manchmal in suboptimale Policies konvergiert (da er auf einem einzelnen, fehlerhaften Modell basiert), führt der Szenario-MPC durch die Berücksichtigung mehrerer Szenarien zu einer stabileren und genaueren Lösung.
  • Trade-off: Der Szenario-MPC ist rechenintensiver, bietet aber eine überlegene Performance in unsicheren Umgebungen.

---

5. Bedeutung und Fazit

Dieses Paper leistet einen wesentlichen Beitrag zur Theorie des Reinforcement Learning, indem es:

1. Die Reward-Balancing-Methoden von einer heuristischen Idee zu einem rigoros mathematisch fundierten Rahmen mit klarer algebraischer und geometrischer Struktur erhebt.
2. Eine Brücke zwischen RL und Kontrolltheorie schlägt, was neue Perspektiven für das Design von Algorithmen eröffnet (z.B. durch Constraints und Kostenfunktionen).
3. Ein robustes Framework für unsichere Modelle liefert. In der Praxis sind exakte MDP-Modelle selten verfügbar; die Fähigkeit, Reward-Balancing auch unter stochastischen Modellfehlern mit garantierter Konvergenz und probabilistischen Schranken durchzuführen, ist ein großer Fortschritt.

Die vorgeschlagene Szenario-MPC-Strategie demonstriert, dass durch die gezielte Ausnutzung von Unsicherheitsmodellen die Performance von RL-Algorithmen über den aktuellen State-of-the-Art hinaus gesteigert werden kann, auch wenn dies mit einem höheren Rechenaufwand verbunden ist. Dies legt den Grundstein für zukünftige Forschung an effizienteren und robusteren Normalisierungsverfahren.