⚡ electrical engineering

Approximations and Learning for Continuous State and Action MDPs under Average Cost Criteria

Diese Arbeit etabliert Fehlerschranken für diskretisierungsbasierte Approximationen von kontinuierlichen Zustands- und Aktions-MDPs unter durchschnittlichen Kostenkriterien, indem sie Stetigkeitsannahmen auf schwache oder Wasserstein-Stetigkeit lockert, und schlägt synchrone sowie asynchrone quantisierte Q-Learning-Algorithmen vor, die gegen die optimalen Werte des approximierten Modells konvergieren und dadurch Nahezu-Optimalität gewährleisten.

Ursprüngliche Autoren: Ali Devran Kara, Serdar Yuksel

Veröffentlicht 2026-06-02

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Ali Devran Kara, Serdar Yuksel

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 durch eine riesige, glatte und kontinuierliche Landschaft (wie ein riesiges, offenes Feld) navigiert, um den Pfad zu finden, der über eine sehr lange Zeit die geringsten Energiekosten verursacht. Dies ist das Problem der Markov-Entscheidungsprozesse (MDPs) unter einem Durchschnittskostenkriterium.

Die Herausforderung besteht darin, dass die Welt des Roboters zu groß und zu glatt ist, um sie perfekt kartieren zu können. Man kann nicht jeden einzelnen Punkt auf dem Feld aufschreiben. Die Arbeit von Kara und Yükel ist wie ein Leitfaden dafür, wie man eine vereinfachte, blockartige Karte dieser glatten Welt erstellt, den Roboter anhand dieser blockartigen Karte lehrt und dann beweist, dass der Roboter in der echten, glatten Welt immer noch eine großartige Arbeit leistet.

Hier ist die Aufschlüsselung ihrer Arbeit unter Verwendung einfacher Analogien:

1. Das Problem: Die „glatte Welt“ vs. die „pixelierte Karte“

Stellen Sie sich die reale Welt wie ein hochauflösendes Foto vor. Es hat unendliche Details. Um einen Computer zu lehren, müssen wir dieses Foto normalerweise in ein niedrig aufgelöstes, pixeliertes Bild (ein Gitter) umwandeln.

Der alte Weg: Frühere Forscher sagten: „Damit diese pixelierte Karte funktioniert, muss der Übergang zwischen den Pixeln extrem vorhersehbar und starr sein (Total Variation Kontinuität).“ Das ist so, als müsste das Foto aus perfekten, nicht verschwommenen Blöcken bestehen.
Der neue Weg: Diese Autoren sagen: „Wir brauchen kein so strenges Foto. Wir können mit einem ‚unscharfen‘ oder ‚wackeligen‘ Foto arbeiten (Schwache oder Wasserstein-Kontinuität).“ Sie haben bewiesen, dass man selbst wenn die Übergänge zwischen den Zuständen etwas „weich“ oder „unscharf“ sind, immer noch eine zuverlässige pixelierte Karte erstellen kann.

2. Die Lösung: Bau einer „blockartigen“ Approximation

Die Autoren schlagen eine Methode vor, die kontinuierliche Welt in endliche Stücke (Bins) zu zerlegen, wie das Schneiden eines Kuchens in Scheiben.

Die Approximation: Anstatt die exakte Position des Roboters zu verfolgen, verfolgt man nur, in welcher „Scheibe“ des Kuchens sich der Roboter befindet.
Die Garantie: Sie haben genau berechnet, wie viel „Fehler“ (oder zusätzliche Kosten) diese Pixelierung einführt.
- Wenn die Welt „unscharf“, aber stabil ist, wird der Fehler kleiner, wenn man die Scheiben dünner macht.
- Sie zeigten, dass, wenn man die Scheiben klein genug macht, die Strategie, die der Roboter auf der blockartigen Karte lernt, fast so gut ist wie die perfekte Strategie für die glatte Welt.

3. Das Lernen: Den Roboter mit „Quantisiertem Q-Learning“ lehren

Sobald die Welt in Scheiben geschnitten wurde, muss der Roboter die besten Züge lernen. Das Paper führt zwei Wege vor, um den Roboter zu lehren:

Synchrones Lernen (Der „Klassenzimmer“-Ansatz): Stellen Sie sich einen Lehrer vor, der den Roboter fragt: „Wenn du in Scheibe A bist und dich nach links bewegst, was passiert dann?“ Der Lehrer simuliert dann alle möglichen Bewegungen aus jeder Scheibe zur gleichen Zeit und aktualisiert das Wissen des Roboters auf einmal. Die Autoren haben bewert, dass diese Methode konvergiert (aufhört sich zu verändern und sich auf eine Lösung festlegt).
Asynchrones Lernen (Der „echte Leben“-Ansatz): Stellen Sie sich vor, der Roboter läuft einfach auf dem Feld herum, macht Fehler und lernt dabei. Er sieht nicht alle Scheiben gleichzeitig; er sieht nur die Scheibe, in der er sich gerade befindet. Die Autoren haben bewiesen, dass der Roboter selbst mit diesen unordentlichen, Schritt-für-Schritt-Daten schließlich die korrekten Werte für die blockartige Karte lernt.

Ein entscheidender Einblick: Die Autoren weisen darauf hin, dass die „blockartige“ Sicht des Roboters auf die Welt eigentlich ein Trick ist. Da der Roboter nur weiß, in welcher Scheibe er sich befindet, aber nicht den exakten Punkt innerhalb dieser Scheibe, lernt er technisch gesehen ein „teilweise beobachtbares“ Problem (wie ein Spiel zu spielen, bei dem man das ganze Spielfeld nicht sehen kann). Trotzdem beweist ihre Mathematik, dass der Roboter dennoch die optimale Strategie für die blockartige Karte lernt.

4. Das Ergebnis: „Nahezu-Optimalität“

Der wichtigste Anspruch bezieht sich auf das Endergebnis.

Der Roboter lernt die beste Strategie für die blockartige, pixelierte Karte.
Die Autoren beweisen, dass diese Strategie auch für die reale, glatte Welt nahezu optimal ist.
Denken Sie daran, wie man lernt, in einem Simulator mit einem niedrig aufgelösten Bildschirm zu fahren. Die Autoren beweisen, dass die Fahrkünste, die man dort lernt, fast perfekt auf das Fahren eines echten Autos auf einer echten Autobahn übertragbar sind, sofern der Simulator gut genug ist (die Scheiben klein genug sind).

Zusammenfassung des „Zaubers“

Das Paper macht im Wesentlichen drei Dinge:

Die Regeln gelockert: Sie zeigten, dass man keine perfekt starre Welt braucht, um eine gute Approximation zu bauen; eine „unscharfe“ Welt funktioniert ebenfalls.
Die Brücke gebaut: Sie entwickelten spezifische Algorithmen (Synchron und Asynchron), die es einem Roboter ermöglichen, auf einer vereinfachten, blockartigen Version einer komplexen Welt zu lernen.
Den Transfer bewiesen: Sie haben mathematisch garantiert, dass die auf der blockartigen Karte gelernte Strategie der perfekten Strategie so nahe kommt, dass sie praktisch dieselbe ist, vorausgesetzt, die Blöcke sind klein genug.

Kurz gesagt: Sie haben herausgefunden, wie man einem Roboter beibringt, eine glatte, unendliche Welt zu navigieren, indem man ihn auf einer vereinfachten, blockartigen Version üben lässt, und sie haben bewiesen, dass Übung den Meister macht.

Technisches Resümee: Q-Learning unter dem Durchschnittskostenkriterium für kontinuierliche MDPs

1. Problemformulierung

Diese Arbeit befasst sich mit der Herausforderung, Markov-Entscheidungsprozesse (MDPs) mit kontinuierlichen Zustands- und Aktionsräumen unter dem unendlichen Horizont mit Durchschnittskostenkriterium zu lösen. Das Modell ist definiert durch ein Tupel $(X, U, \mathcal{T}, c)$ , wobei $X$ und $U$ Standard-Borel-Räume (vollständige, separierbare metrische Räume) sind, $\mathcal{T}$ der Übergangskern ist und $c$ die Kostenfunktion darstellt. Das Ziel ist es, eine Strategie $\pi$ zu finden, die die langfristigen durchschnittlichen Kosten minimiert:
$J^*(x) := \inf_{\pi} \limsup_{T \to \infty} \frac{1}{T} \mathbb{E}^\pi_x \left[ \sum_{t=0}^{T-1} c(x_t, u_t) \right]$

Die Autoren heben hervor, dass während endliche Horizonte und diskontierte Kostenprobleme für kontinuierliche Räume unter Nutzung der Kontraktionseigenschaften von Bellman-Operatoren gut untersucht sind, Probleme mit Durchschnittskosten einzigartige Schwierigkeiten aufweisen. Insbesondere entfernt der Mangel an einem Diskontierungsfaktor die unmittelbare Kontraktionsabbildung, was alternative Stabilitäts- und Ergodizitätsannahmen erforderlich macht. Darüber hinaus konzentriert sich die bestehende Literatur zum Reinforcement Learning (RL) mit Durchschnittskosten weitgehend auf endliche Räume oder legt restriktive strukturelle Annahmen vor (z. B. lineare Dynamiken, Lipschitz-Strategien), die die Anwendbarkeit auf allgemeine kontinuierliche Räume einschränken.

2. Methodik

Die Arbeit verwendet einen zweigleisigen Ansatz: endliche Approximation mittels Quantisierung und Reinforcement-Learning-Algorithmen, die für diese Approximationen entwickelt wurden.

2.1 Diskretisierung und Approximation

Die Kernmethodik besteht darin, einen endlichen Zustands-, endlichen Aktions-approximierten MDP durch Quantisierung der kontinuierlichen Räume zu konstruieren.

Zustandsquantisierung: Der Zustandsraum $X$ wird in disjunkte Klassen $\{B_i\}_{i=1}^M$ mit Repräsentanten $y_i$ partitioniert. Eine Abbildung $q: X \to Y$ (wobei $Y$ die endliche Menge der Repräsentanten ist) wird definiert.
Aktionsquantisierung: Der Aktionsraum $U$ wird durch eine endliche Menge $\Lambda$ approximiert.
Konstruktion des approximierten Modells: Das approximierte Modell $(\hat{X}, \hat{U}, \hat{\mathcal{T}}, \hat{c})$ wird unter Verwendung eines Gewichtungsmaßes $\mu$ (oft das invariante Maß des Zustandsprozesses) definiert. Die approximierten Kosten- und Übergangskerne sind Mittelwerte der ursprünglichen Funktionen über die Quantisierungsklassen:
$\hat{c}(y_i, u) = \int_{B_i} c(z, u) \mu_{y_i}(dz), \quad \hat{\mathcal{T}}(A|y_i, u) = \int_{B_i} \mathcal{T}(A|z, u) \mu_{y_i}(dz)$
Gelockerte Stetigkeitsbedingungen: Eine signifikante methodische Neuerung ist die Lockerung der Bedingung der Total Variation (TV)-Stetigkeit, die in der bisherigen Approximationsliteratur Standard ist (z. B. Saldi et al., 2018). Die Autoren etablieren Approximationsergebnisse unter:
1. Schwacher Stetigkeit (Feller): Ausreichend für die asymptotische Konvergenz der Fehler, wenn die Gittergrößen gegen Null gehen.
2. Wasserstein-Stetigkeit: Ausreichend, um explizite Konvergenzraten (Fehlergrenzen) zu etablieren, wenn die Gittergrößen gegen Null gehen.

2.2 Reinforcement-Learning-Algorithmen

Das Papier schlägt quantisierte Q-Learning-Algorithmen vor, um die optimale Strategie für das approximierte Modell direkt aus Daten zu lernen.

Synchroner Algorithmus (Algorithmus 1): Aktualisiert Q-Werte für alle Zustands-Aktions-Paare im endlichen Gitter simultan. Er stützt sich auf die Stichprobenentnahme von Zuständen aus jeder Klasse gemäß einem vorgegebenen Maß.
Asynchroner Algorithmus (Algorithmus 2): Aktualisiert Q-Werte basierend auf einer einzelnen Trajektorie des ursprünglichen kontinuierlichen Prozesses. Dies ist praktischer, führt jedoch ein nicht-markovsches Rauschen ein, da der quantisierte Prozess $q(X_t)$ kein Markov-Kette ist (er ist ein teilweise beobachtbarer MDP aus der Perspektive des quantisierten Zustands).
Konvergenzmechanismus: Um das Durchschnittskostenkriterium und die Unbeschränktheit der Q-Iterationen (im Gegensatz zu diskontierten Fällen) zu handhaben, nutzen die Autoren:
- Span-Semi-Normen für synchrone Updates.
- Ergodizitätsannahmen: Die Explorationsstrategie muss ein eindeutiges invariantes Maß mit vollem Support über den quantisierten Klassen induzieren.
- Verschobene Updates (Shifted Updates): Der asynchrone Algorithmus subtrahiert einen Referenzwert (basierend auf einer spezifischen Klasse), um die Iteration zu stabilisieren, indem er den quantisierten Prozess als POMDP behandelt.

3. Zentrale Beiträge

Die Arbeit leistet drei primäre Beiträge und erweitert damit den Stand der Technik der durchschnittskostenbasierten Steuerung in kontinuierlichen Räumen:

Approximationstheorie mit schwächeren Bedingungen:
- Die Autoren liefern Fehlergrenzen für endliche Approximationen unter schwacher Stetigkeit und Wasserstein-Stetigkeit, wodurch die strikte Total-Variation-Stetigkeit gelockert wird, die in früheren Arbeiten (z. B. Saldi et al., 2018) erforderlich war.
- Sie stellen fest, dass unter Wasserstein-Stetigkeit (mit einer Kontraktionskonstante $K_T < 1$ ) der Fehler der optimalen durchschnittlichen Kosten proportional zum Quantisierungsfehler (speziell $L_X^\delta$ ) abnimmt.
- Unter alleiniger schwacher Stetigkeit beweisen sie die asymptotische Konvergenz der Kosten der approximierten Strategie gegen die optimale Kostenstruktur, wenn die Diskretisierung feiner wird.
Konvergenz von quantisiertem Q-Learning:
- Das Papier etabliert die fast sichere Konvergenz sowohl synchroner als auch asynchroner Q-Learning-Algorithmen für kontinuierliche Räume.
- Entscheidend ist der Beweis, dass diese Algorithmen zu den optimalen Q-Werten des konstruierten endlichen approximierten Modells konvergieren und nicht nur zum ursprünglichen kontinuierlichen Modell. Diese Unterscheidung ist essenziell, da der quantisierte Prozess nicht streng markovsch ist.
- Die Analyse verallgemeinert bisherige Ergebnisse (z. B. Kara und Yüksel, 2023) von diskontierten Kosten auf das anspruchsvollere Durchschnittskostenkriterium, was eine neue technische Analyse zur Handhabung unbeschränkter Q-Iterationen erfordert.
Garantien für Nahezu-Optimalität:
- Durch die Kombination der Approximationsfehlergrenzen mit der Konvergenz der Lernalgorithmen zeigt das Papier, dass die mittels quantisiertem Q-Learning gelernten Strategien nahezu optimal für den ursprünglichen kontinuierlichen MDP sind.
- Der Leistungsverlust wird explizit in Abhängigkeit von der Quantisierungsauflösung und den Lipschitz-Konstanten der Kosten- und Übergangskerne begrenzt.

4. Wichtige Ergebnisse und Theoreme

Theorem 1 & 2 (Approximationsgrenzen): Legen obere Schranken für die Differenz zwischen den optimalen durchschnittlichen Kosten des Originalmodells ( $\rho$ $ρ$ ) und des approximierten Modells ( $\hat{\rho}$ $\overset{ρ}{^}$ ) fest.
- Unter Wasserstein-Stetigkeit: $|\rho - \hat{\rho}| \leq C \cdot (L_X)^\delta$ , wobei $L_X$ der Quantisierungsfehler ist.
- Unter schwacher Stetigkeit: $\lim_{n \to \infty} \rho(\pi_n) = \rho$ .
Theorem 5 & 6 (Algorithmenkonvergenz): Beweisen, dass die synchronen und asynchronen Q-Learning-Iterationen zu den optimalen Q-Werten des endlichen approximierten Modells konvergieren. Die asynchrone Konvergenz beruht auf der Ergodizität des Zustandsprozesses unter der Explorationsstrategie.
Korollar 1: Kombiniert die Approximations- und Lernergebnisse, um zu zeigen, dass die gelernte Strategie $\hat{\pi}$ die Bedingung $\rho(\hat{\pi}) - \rho \leq \epsilon$ erfüllt, wobei $\epsilon$ gegen Null geht, wenn die Größe des Quantisierungsgitters gegen Null geht.

5. Bedeutung und Behauptungen

Die Autoren positionieren diese Arbeit als Lösung offener Probleme in der Literatur bezüglich Reinforcement Learning für durchschnittskostenbasierte MDPs mit kontinuierlichen Räumen.

Lockerung von Annahmen: Das Papier beansprucht einen signifikanten theoretischen Fortschritt durch den Übergung von der Total-Variation-Stetigkeit, die oft zu restriktiv für praktische Modelle ist, hin zu schwacher Stetigkeit und Wasserstein-Stetigkeit. Dies erweitert die Klasse der Systeme (z. B. solche mit additivem Rauschen oder spezifischen Dynamiken), für die theoretische Garantien bereitgestellt werden können.
Überbrückung von Theorie und Praxis: Durch den Beweis, dass Q-Learning zur Lösung eines wohldefinierten endlichen Approximationsmodells konvergiert, liefert das Papier eine rigorose Rechtfertigung für die Verwendung von diskretisierungsbasierter RL in kontinuierlichen Durchschnittskosten-Settings. Es klärt, dass die „Nahezu-Optimalität“ eine direkte Folge der Approximationsqualität ist und kein Artefakt des Lernalgorithmus.
Handhabung nicht-markoverscher Quantisierung: Das Papier adresset explizit die technische Schwierigkeit, dass der quantisierte Zustandsprozess ein POMDP und kein MDP ist, und liefert einen Konvergenzbeweis für das asynchrone Lernen in diesem Setting unter Durchschnittskostenkriterien – eine Lücke, die zuvor in der Literatur (z. B. Wan et al., 2021) festgestellt wurde.

Das Papier schließt mit einer numerischen Fallstudie zu einem kontinuierlichen Steuerungsproblem ab, die die Konvergenz der Wertfunktionen und die Reduktion des Regrets bei steigender Quantisierungsrate demonstriert und damit die theoretischen Schranken validiert.