📊 statistics

Learning Sequential Decisions from Multiple Sources via Group-Robust Markov Decision Processes

Dieses Paper schlägt ein gruppenrobustes Markov-Entscheidungsprozess-Framework mit merkmalsweisen Unsicherheitsmengen und einem pessimistischen Offline-Algorithmus vor, um robuste sequentielle Entscheidungsstrategien aus heterogenen Multi-Site-Daten zu lernen, wobei Suboptimalitätsgarantien erreicht werden, ohne sich auf starke Annahmen der Zustand-Aktions-Rechteckigkeit zu verlassen.

Ursprüngliche Autoren: Mingyuan Xu, Zongqi Xia, Tianxi Cai, Doudou Zhou, Nian Si

Veröffentlicht 2026-02-03

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Mingyuan Xu, Zongqi Xia, Tianxi Cai, Doudou Zhou, Nian Si

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 versuchen, einem Roboter beizubringen, wie er eine komplexe Stadt durchquert, um Pakete auszuliefern. Sie haben keine Zeit, den Roboter herumfahren und gegen Dinge prallen zu lassen (das ist „Online-Lernen“, was gefährlich und teuer ist). Stattdessen geben Sie dem Roboter eine riesige Bibliothek von Fahrprotokollen aus drei verschiedenen Städten: New York, Chicago und Miami.

Hier ist das Problem:

New York hat viele Ampeln und enge Straßen.
Chicago hat riesige offene Alleen, aber eisige Winter.
Miami hat starken Regen und andere Verkehrsregeln.

Wenn Sie die Protokolle einfach zu einem einzigen großen Haufen zusammenwerfen, lernt der Roboter vielleicht eine „Mittelweg“-Strategie, die in einer durchschnittlichen Stadt ganz okay funktioniert, aber im schlimmsten Fall (wie bei einem Schneesturm in Chicago) kläglich scheitert. Das nennt man Distributional Shift (Verteilungsverschiebung).

Wenn Sie den Roboter separat für jede Stadt lehren, wird er vielleicht ein Experte für New York, aber völlig ahnungslos in Miami, oder er wird verwirrt sein, weil es in keiner einzelnen Stadt genug Daten gibt, um sich über die Regeln sicher zu sein.

Dieses Paper schlägt einen intelligenten Weg vor, den Roboter mithilfe der Daten aller drei Städte zu lehren und ihn gleichzeitig auf die schlechtmögliche Version jeder Stadt vorzubereiten.

Die Kernidee: „Der schlimmste Wetterbericht“

Die Autoren behandeln den Lernprozess wie ein Spiel zwischen zwei Charakteren:

Der Roboter (Der Agent): Will die beste Route finden, um Pakete auszuliefern.
Der Widersacher (Der Wetterbericht): Will das Leben des Roboters so schwer wie möglich machen, indem er die schlimmsten möglichen Verkehrsbedingungen oder Verkehrsregeln aus den vorhandenen Daten auswählt.

Normalerweise kann der Wetterbericht die Regeln für jede einzelne Straßenecke unabhängig voneinander ändern. Das macht die Mathematik unlösbar (es ist, als würde man versuchen, das Wetter für jedes einzelne Atom in der Atmosphäre gleichzeitig vorherzusagen).

Der Trick des Papers:
Die Autoren führen eine clevere Abkürzung namens „Feature-wise Rectangularity“ (merkmaleweise Rechteckigkeit) ein.
Anstatt dem Wetterbericht zu erlauben, jede einzelne Regel unabhängig voneinander zu ändern, sagen sie: „Okay, Wetterbericht, du kannst die Regeln für ‚Ampeln‘, ‚Straßenbreite‘ und ‚Wetter‘ unabhängig voneinander ändern, aber du musst die gleiche ‚Worst-Case‘-Logik auf alle von ihnen gemeinsam anwenden.“

Denken Sie an das wie an ein Menü aus Zutaten.

Der alte Weg: Der Koch (Wetterbericht) kann das Salz in der Suppe, den Zucker im Kuchen und das Gewürz im Eintopf für jedes Gericht unabhängig voneinander austauschen. Das ist chaotisch und schwer zu planen.
Der neue Weg (Dieses Paper): Der Koch kann das Salz, den Zucker und das Gewürz austauschen, aber er muss dies auf eine strukturierte Weise tun, die das „Geschmacksprofil“ des Gerichts respektiert. Dies hält die Mathematik lösbar und ist dennoch sehr vorsichtig.

Wie der Algorithmus funktioniert: „Der vorsichtige Koch“

Der Algungorithmus des Papers (Algorithmus 1) arbeitet in drei Schritten, wie ein vorsichtiger Koch, der ein Essen für einen wählerischen Gast zubereitet:

Lernen von jeder Stadt separat (Ridge-Regression):
Zuerst schaut sich der Roboter die Protokolle aus New York, Chicago und Miami separat an. Er versucht, die Regeln für jede Stadt zu erraten. Aber da die Daten etwas unordentlich oder unvollständig sein könnten, fügt er einen „Sicherheitsbuffer“ (genannt Pessimismus) zu seinen Vermutungen hinzu. Er geht davon aus, dass die Daten leicht fehlerhaft sein könnten.
Der „Worst-Case“-Mix (Zeilenweise Minimierung):
Nun kombiniert der Roboter diese Vermutungen. Anstatt sie zu mitteln (was die schlechten Teile verbergen würde), prüft er jede einzelne Regel und fragt: „Was ist die schlimmste Version dieser Regel über alle drei Städte hinweg?“

Wenn New York sagt „Geschwindigkeitsbegrenzung ist 30“, Chicago „25“ und Miami „35“ sagt, nimmt der Roboter die 25.
Er baut eine Strategie basierend auf der niedrigsten (sichersten) Schätzung für jedes einzelne Merkmal auf. Dies stellt sicher, dass der Robot nicht abstürzt, egal welche verborgene „Worst-Case“-Realität einer der Städte auftaucht.

Die Sicherheitsstrafe:
Wenn der Roboter eine bestimmte Situation nicht oft genug in den Protokollen gesehen hat (z. B. hat er nur 5 Regentage in Miami gesehen), fügt der Algorithmus eine große „Strafe“ für diese Vermutung hinzu. Er sagt dem Roboter: „Vertraue dieser Zahl nicht; du hast nicht genug Daten. Nimm das Schlimmste an.“ Dies verhindert, dass der Roboter aufgrund kleiner, glücklicher Stichproben übermäßig selbstbewusst wird.

Die „Gruppen“-Strategie: Ähnliche Städte clustern

Das Paper schlägt auch einen zweiten Trick vor. Was ist, wenn Sie 50 Städte haben, aber 10 davon sehr ähnlich sind (z. B. alle Küstenstädte)?
Anstatt sie als 10 separate Probleme zu behandeln, können Sie sie in eine einzige „Super-Küsten“-Gruppe zusammenfassen.

Warum? Es gibt Ihnen mehr Daten, um die Regeln des „Küstenfahrens“ zu lernen.
Die Einschränkung: Sie müssen sicherstellen, dass die Städte tatsächlich ähnlich sind. Wenn Sie eine Wüstenstadt mit einer Küstenstadt zusammenlegen, wird die Regel Ihrer „Super-Gruppe“ unsinnig sein. Das Paper liefert die Mathematik, um zu beweisen, dass das Zusammenfassen (Pooling) die Städte schneller und genauer lernen lässt, solremann die Städte in der Gruppe ähnlich genug sind.

Die Ergebnisse: Warum es wichtig ist

Die Autoren haben dies in Computersimulationen getestet:

Naives Pooling: Das bloße Zusammenmischen aller Daten. Ergebnis: Der Roboter scheiterte in den schlimmsten Szenarien, weil er die einzigartigen Gefahren spezifischer Städte ignorierte.
Separates Lernen: Das Lernen für jede Stadt allein. Ergebnis: Der Roboter war instabil und machte Fehler, weil er für eine einzelne Stadt nicht genügend Daten hatte.
Die Methode dieses Papers: Ergebnis: Der Roboter lernte eine Strategie, die konsistent sicher und effizient war, selbst in den schlimmsten Szenarien. Er fand den „Sweet Spot“ zwischen zu vorsichtig und zu leichtsinnig zu sein.

Zusammenfassend

Dieses Paper liefert uns ein mathematisches Rezept, um von mehreren verschiedenen Quellen (wie Krankenhäusern, Städten oder Fabriken) zu lernen, ohne voraussetzen zu müssen, dass sie alle exakt gleich sind. Es baut ein Entscheidungssystem auf, das robust ist: Es bereitet sich auf die schlimmste mögliche Version der gesehenen Daten vor und stellt sicher, dass der endgültige Plan auch dann sicher funktioniert, wenn Dinge schiefgehen oder Daten fehlen.

Es ist, als würde man einen Piloten nicht nur auf das „Durchschnittswetter“ trainieren, sondern indem man die schlimmste Kombination aus Wind, Regen und Turbulenzen simuliert, die in irgendeinem der Trainingsprotokolle gefunden wurde, um sicherzustellen, dass er unter allen Umständen sicher landen kann.

Technisches Resümee: Lernen sequenzieller Entscheidungen aus multiplen Quellen via Group-Robust Markov Decision Processes

Problemformulierung

Diese Arbeit adressiert die Herausforderung, robuste Strategien für sequenzielle Entscheidungsfindungen aus Offline-Datensätzen zu erlernen, die über mehrere Standorte (z. B. Krankenhäuser) hinweg gesammelt wurden, welche einen gemeinsamen Anwendungskontext teilen, aber Heterogenität aufweisen. Im Standard-Offline-Reinforcement-Learning (RL) werden Strategien aus vorab gesammelten Daten erlernt, ohne weitere Interaktion mit der Umgebung. Offline-Daten aus multiplen Standorten leiden jedoch häufig unter zwei kritischen Problemen:

Distributional Shift (Verteilungsverschiebung): Offline-Trajektorien werden durch Behavior-Policies generiert, die möglicherweise nicht die Zustands-Aktions-Verteilung der optimalen Policy abdecken.
Standortspezifische Heterogenität: Variationen in den Datenerfassungsprotokollen, der Populationszusammensetzung und den Umweltbedingungen bedeuten, dass Trajektorien nicht aus einem einzigen, fixen Markov-Entscheidungsprozess (MDP) generiert werden. Stattdessen besitzt jeder Standort $k$ seinen eigenen Übergangskern $P_k$ und seine eigene Belohnungsfunktion $r_k$ .

Die Autoren modellieren diesen Kontext als einen Group-Linear Distributionally Robust MDP (DRMDP). Die zugrunde liegende Annahme ist, dass alle Standorte eine gemeinsame, bekannte Feature-Map $\phi: \mathcal{S} \times \mathcal{A} \to \mathbb{R}^d$ teilen, die Übergangskerne und Belohnungsfunktionen jedoch linear in diesen Features mit standortspezifischen Parametern $(\theta^k_h, \mu^k_h)$ sind. Das Ziel ist es, eine Strategie zu erlernen, die unter der Worst-Case-Umweltverschiebung innerhalb einer plausiblen Unsicherheitsmenge performt, die durch das Konvexhull der standortspezifischen Verteilungen definiert ist.

Methodik

1. Feature-weise (d-rechteckige) Unsicherheitsmengen

Um die durch multiple Standorte entstehende Unsicherheit zu handhaben und gleichzeitig die rechnerische Handhabbarkeit zu gewährleisten, schlagen die Autoren eine feature-weise (d-rechteckige) Unsicherheitsmenge vor.

Struktur: Im Gegensatz zu einem Standard-Cross-Site-Konvexhull, der die Unsicherheit über alle Features hinweg koppelt (was zu nicht-rechteckigen Mengen und NP-schwerer Planung führt), erlaubt dieser Ansatz dem Adversary, die Mischgewichtungen unabhängig für jede Feature-Dimension $i \in [d]$ zu wählen.
Definition: Für jeden Schritt $h$ und jedes Feature $i$ wählt der Adversary einen Mischungsvektor $\alpha_{h,i} \in \Delta^{K-1}$ , um eine worst-case Mischung der standortspezifischen Parameter zu bilden. Die Unsicherheitsmenge $\mathcal{U}_h$ ist so definiert, dass Belohnung und Übergang für ein beliebiges $(s, a)$ Linearkombinationen der Standortparameter sind, gewichtet durch diese feature-spezifischen Mischungen.
Vorteil: Diese Relaxation bewahrt die entscheidende Cross-Site-Heterogenität und stellt gleichzeitig die robusten Bellman-Rekursionen wieder her, was das Problem berechenbar macht.

2. Pessimistische Value Iteration Algorithm

Die Autoren entwickeln einen Offline-Algorithmus (Algorithmus 1) basierend auf pessimistischer Value Iteration, der drei Kernkomponenten umfasst:

Per-Site Ridge Regression: Für jeden Standort $k$ schätzt der Algorithmus die Bellman-Target-Koeffizienten $\hat{\nu}^k_h$ mittels Ridge-Regression auf dem lokalen Datensatz $D_k$ . Dies liefert standortspezifische Schätzungen der linearen Parameter.
Feature-weise Worst-Case-Aggregation: Anstatt zu mitteln, führt der Algorithmus eine zeilenweise Minimum-Bildung über die geschätzten Koeffizienten aller Standorte durch. Speziell wird für jede Feature-Dimension $i$ der robuste Koeffizient als $\min_{k \in [K]} (\hat{\nu}^k_h)_i$ gesetzt. Dies erfasst das Worst-Case-Szenario über die Standorte hinweg für jedes Feature.
Datenabhängiger Pessimismus-Penalty: Um die Schätzunsicherheit und den Distributional Shift zu berücksichtigen, wird ein Penalty-Term vom Q-Wert subtrahiert. Dieser Penalty wird unter Verwendung der Diagonalen der inversen Design-Matrizen (Kovarianzmatrizen) aus der Ridge-Regression berechnet. Der Penalty skaliert mit dem Feature-Vektor $\phi(s, a)$ und der maximal beobachteten Unsicherheit über alle Standorte für jede Feature-Dimension hinweg.

3. Cluster-Level Erweiterung

Um die Stichprobeneffizienz zu verbessern, wenn Standorte Ähnlichkeiten aufweisen, schlagen die Autoren eine Erweiterung auf Cluster-Ebene vor. Standorte werden basierend auf bekanntem Wissen über Ähnlichkeiten in Cluster partitioniert. Innerhalb eines Clusters werden die Datensätze zu einem "Super-Standort" zusammengeführt, und der robuste Bellman-Operator wird auf die Cluster-Level-Repräsentanten angewendet. Dieser Ansatz nutzt größere gepoolte Stichprobenmengen aus und begrenzt gleichzeitig den durch die Intra-Cluster-Heterogenität eingeführten Fehler.

Theoretische Ergebnisse

Das Paper liefert endliche Suboptimalitäts-Schranken für den vorgeschlagenen Algorithmus unter einer robusten partiellen Coverage-Annahme.

Suboptimalitäts-Zerlegung: Die Suboptimalität wird in Spurious Correlation, intrinsische Unsicherheit und Optimierungsfehler zerlegt.
Konvergenzrate: Unter der Annahme, dass die standortspezifischen empirischen Kovarianzmatrizen die zweiten Momente der robusten optimalen Policy-Besuchsdistribution dominieren, ist die Suboptimalität der gelernten Strategie $\hat{\pi}$ beschränkt durch:
$\text{SubOpt}(\hat{\pi}; s) \leq O\left( d^2 H^2 \sqrt{\frac{\log(d K H N_{\max}/\xi)}{N_{\min}}} \right)$
wobei $N_{\min}$ die minimale Stichprobengröße über die Standorte hinweg ist, $d$ die Feature-Dimension ist, $H$ der Horizont ist und $K$ die Anzahl der Standorte darstellt.
Cluster-Level Schranke: Für den Cluster-Level-Algorithmus enthält die Schranke einen zusätzlichen Bias-Term, der proportional zur Intra-Cluster-Parameter-Diskrepanz ( $\Delta_h$ ) ist, was zeigt, dass das Pooling vorteilhaft ist, solange die Heterogenität innerhalb der Cluster kontrolliert bleibt.

Experimentelle Ergebnisse

Die Autoren validieren ihren Ansatz durch Simulationen auf episodischen linearen MDPs mit $K=3$ bis $4$ Standorten.

Vergleich: Der vorgeschlagene "Sitewise"-Algorithmus wird mit folgenden Benchmarks verglichen:
- Naive Pooling: Aggregation aller Daten und Anwendung von Standard-Pessimistic Value Iteration (PEVI).
- Per-Site PEVI (Average-Q): Mittelung der Q-Funktionen aus unabhängigen standortspezifischen PEVI-Läufen.
- Per-Site PEVI (Min-Q): Bildung des punktweisen Minimums der standortspezifischen Q-Funktionen.
Performance: Der vorgeschlagene Algorithmus erzielt konsistent eine signifikant geringere robuste Suboptimalität im Vergleich zu allen Benchmarks.
- Naive Pooling ist nicht robust gegenüber standortspezifischen Distributional Shifts, da es auf die Optimierung der durchschnittlichen Performance statt auf das Worst-Case-Szenario abzielt.
- Per-Site Methoden leiden unter hoher Varianz aufgrund begrenzter lokaler Stichprobenmengen und mangelndem Informationsaustausch.
Konvergenz: Empirische Skalierungsgesetze bestätigen die theoretische $O(N_{\min}^{-1/2})$ Konvergenzrate.
Notwendigkeit von Pessimismus: Experimente zeigen, dass das Entfernen des Pessimismus-Penalty (Setzen der Skalierungskonstante $c=0$ ) zu einem Scheitern der effizienten Konvergenz führt, da der Greedy-Estimator zu Rauschen in endlichen Stichproben neigt, insbesondere in Szenarien mit unausgewogener Datenabdeckung.

Bedeutung und Ansprüche

Das Paper beansprucht, einen prinzipienbasierten Ansatz für robustes Planning in Multi-Site Offline-RL-Settings zu liefern, ohne sich auf starke $(s, a)$ -rechteckige Annahmen verlassen zu müssen.

Handhabbarkeit vs. Robustheit: Durch die Einführung der $d$ -rechteckigen Unsicherheitsmenge schließen die Autoren die Lücke zwischen der Unhandlichkeit allgemeiner Cross-Site-Konvexhulls und der übermäßigen Konservativität von Standard- $(s, a)$ -rechteckigen robusten MDPs.
Privatsphäre und Effizienz: Der Algorithmus kommuniziert lediglich aggregierte Standort-Zusammenfassungsstatistiken (Ridge-Regression-Koeffizienten und Kovarianzdiagonalen) anstatt roher Trajektorien, was die Kommunikationskosten reduziert und die Privatsphäre erhöht.
Umgang mit Heterogenität: Das Framework modelliert und nutzt die Heterogenität über Standorte hinweg explizit, um sicherzustellen, dass die gelernte Strategie gegenüber der Worst-Case-Standortkonfiguration robust ist, was eine fundamentale Limitation von Standard-Offline-RL bei Multi-Source-Daten adressiert.

Die Autoren räumen ein, dass ihre Methode auf einer linearen Struktur innerhalb der Standorte basiert und dass die $d$ -rechteckige Approximation zu konservativen Schätzungen führen kann. Sie schlagen vor, dass zukünftige Arbeiten engere Approximationen und die Integration von Representation Learning untersuchen könnten, um nicht-lineare Feature-Mappings zu handhaben.