Optimal strategies in Markov decision processes with finitely additive evaluations

Das Papier widerlegt die Vermutung, dass in Markov-Entscheidungsprozessen mit endlich additiven Bewertungen immer eine optimale Strategie existiert, indem es ein Gegenbeispiel konstruiert, bei dem eine speziell gestaltete Aggregationsladung weder eine reine noch eine randomisierte optimale Strategie zulässt.

Das Wesentliche

Das Dilemma des unendlichen Spiels: Warum es manchmal keine perfekte Strategie gibt

Stellen Sie sich vor, Sie spielen ein unendliches Brettspiel. In jedem Zug erhalten Sie eine Belohnung (oder einen Verlust). Ihr Ziel ist es, über die Ewigkeit hinweg die bestmögliche Gesamtsumme zu erzielen.

Normalerweise denken wir dabei an zwei Dinge:

1. Der Durchschnitt: Was bekomme ich im Schnitt pro Zug?
2. Der Abzinsung: Was bekomme ich jetzt, ist wichtiger als das, was ich in 100 Jahren bekomme (wie bei Zinsen).

In diesem Papier untersuchen die Autoren eine viel seltsamere Art, das Spiel zu bewerten. Sie nutzen ein mathematisches Werkzeug, das sie „Aggregationsladung" nennen. Stellen Sie sich diese Ladung wie einen sehr speziellen Richter vor, der über das Spiel urteilt.

Der spezielle Richter (Die „Aggregationsladung")

Dieser Richter hat eine seltsame Regel: Er gibt jedem einzelnen Zug null Gewicht. Er schaut sich nicht den 1. Zug an, nicht den 100. und nicht den 1.000.000. Er schaut sich das Gesamtbild an.

• Wenn Sie in den ungeraden Zügen gewinnen und in den geraden verlieren, zählt er das als 50/50.
• Er ignoriert die Zeit. Für ihn ist der 1. Zug genauso wichtig wie der 1.000.000. Zug.

Bisher wussten die Mathematiker: Wenn dieser Richter eine bestimmte „vernünftige" Regel befolgt (die sogenannte „Zeitwert des Geldes"-Regel), dann gibt es immer eine perfekte Strategie. Man kann einfach eine feste Regel aufstellen (z. B. „Immer Zug A machen"), und man gewinnt maximal.

Die große Frage

Die Autoren stellten sich die Frage: Gilt das immer? Gibt es für jeden möglichen Richter und jedes Spiel eine perfekte Strategie?

Die Antwort, die sie gefunden haben, ist ein hartes „Nein".

Die Geschichte vom „Gerade-oder-Ungerade"-Spiel

Um das zu beweisen, konstruierten sie ein kleines, aber perfides Spiel (das „Even-or-Odd"-MDP):

• Das Spielfeld: Es gibt drei Räume. Sie starten in Raum 1.
• Die Wahl: In Raum 1 müssen Sie sich entscheiden:
  • Option A (T): Sie bekommen 1 Punkt jetzt, aber im nächsten Zug (Raum 2) bekommen Sie 0.
  • Option B (B): Sie bekommen 0 jetzt, aber im nächsten Zug (Raum 3) bekommen Sie 1.
• Der Zyklus: Nach dem nächsten Zug landen Sie wieder in Raum 1 und müssen wieder wählen.

Das Spiel ist also ein ewiger Wechsel: 1-0-1-0-1-0... oder 0-1-0-1-0-1...

Das Problem:
Der Richter, den die Autoren sich ausgedacht haben, ist ein „Spalter". Er besteht aus zwei Teilen:

1. Teil 1 (Der Ungerade-Richter): Er schaut nur auf die ungeraden Züge (1, 3, 5...). Er will, dass Sie dort gewinnen.
2. Teil 2 (Der Gerade-Richter): Er schaut nur auf die geraden Züge (2, 4, 6...). Aber er ist so konstruiert, dass er eine sehr spezielle Art von Gewinn bevorzugt, die schwer zu erreichen ist.

Das Dilemma:

• Wenn Sie immer Option A wählen (1, 0, 1, 0...), gewinnen Sie perfekt für den Ungeraden-Richter. Aber für den Geraden-Richter ist das eine Katastrophe, weil Sie in den geraden Zügen immer 0 bekommen.
• Wenn Sie immer Option B wählen (0, 1, 0, 1...), ist es umgekehrt.
• Wenn Sie wechseln (A, B, A, B...), bekommen Sie immer 0,5 im Durchschnitt. Das ist besser als nichts, aber nicht das Maximum.

Der Clou: Warum es keine Lösung gibt

Die Autoren zeigen, dass Sie versuchen können, den Richter zu täuschen, indem Sie Ihre Strategie langsam ändern.

• Sie könnten sagen: „Ich mache 99% der Zeit Option A, aber ganz selten Option B." Das bringt Ihnen fast die maximale Punktzahl für den ersten Teil des Richters.
• Aber sobald Sie das tun, verliert der zweite Teil des Richters ein wenig von seiner Zufriedenheit.
• Wenn Sie versuchen, den zweiten Teil zufriedener zu machen, verliert der erste Teil wieder Punkte.

Es ist wie ein ewiges Hin und Her:
Stellen Sie sich vor, Sie versuchen, einen Ball so zu werfen, dass er gleichzeitig zwei verschiedene Ziele trifft, die sich aber gegenseitig ausschließen. Je näher Sie dem einen Ziel kommen, desto weiter entfernen Sie sich vom anderen.

Das Schlimmste ist: Sie können sich der perfekten Punktzahl (1,0) beliebig nah annähern, aber Sie werden sie niemals erreichen.

• Strategie A gibt Ihnen 0,99.
• Strategie B gibt Ihnen 0,999.
• Strategie C gibt Ihnen 0,9999.

Es gibt immer eine bessere Strategie als die vorherige, aber es gibt keine, die die beste ist. Es gibt keinen „Sieg", der unangefochten ist.

Was bedeutet das für uns?

In der Welt der Mathematik und der Wirtschaft (Markov-Entscheidungsprozesse) haben wir oft angenommen, dass es immer eine „beste Lösung" gibt, wenn wir nur lange genug suchen.

Diese Arbeit zeigt uns eine tiefe Wahrheit: Manchmal gibt es keine perfekte Lösung.
Wenn die Art und Weise, wie wir Erfolg messen (unsere „Bewertungsregel"), zu komplex oder zu widersprüchlich ist, dann kann es sein, dass wir uns in einer endlosen Spirale von „fast perfekt" befinden, ohne jemals das Ziel zu erreichen.

Die Moral der Geschichte:
Manchmal ist die Suche nach dem absolut perfekten Plan vergeblich, weil die Regeln des Spiels selbst so konstruiert sind, dass sie jede feste Regel unterlaufen. Es gibt Momente, in denen das „Beste" nur ein theoretischer Horizont ist, den man nie erreicht, egal wie schnell man läuft.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des vorliegenden Papers auf Deutsch:

Titel

Optimale Strategien in Markov-Entscheidungsprozessen mit endlich additiven Bewertungen
(Optimal strategies in Markov decision processes with finitely additive evaluations)

1. Problemstellung und Motivation

Das Paper untersucht unendlich-horizontige Markov-Entscheidungsprozesse (MDPs) mit endlichen Zustands- und Aktionsräumen. Der zentrale Unterschied zu klassischen MDPs liegt in der Bewertungsmethode der Strategien:

• Klassisch: Oft wird der diskontierte Erwartungswert oder der langfristige Durchschnittsertrag (limiting average) verwendet.
• Dieses Paper: Die Bewertung erfolgt durch Aggregation der unendlichen Folge der erwarteten Stufenbelohnungen mittels eines diffusen Charges (eines endlich additiven Wahrscheinlichkeitsmaßes auf der Menge der Stufen $\mathbb{N}$). Ein diffuses Charge $\mu$ weist jeder einzelnen Stufe das Gewicht 0 zu ($\mu(\{n\}) = 0$).

Hintergrund:
Neyman [2023] zeigte, dass wenn das Aggregations-Charge das „Prinzip des Zeitwerts des Geldes" (time value of money principle) erfüllt, in jedem MDP eine reine stationäre optimale Strategie existiert.
Die offene Frage: Existiert eine optimale Strategie (rein oder randomisiert) für jedes beliebige diffuse Charge, auch wenn es das Prinzip des Zeitwerts des Geldes nicht erfüllt?

2. Methodik und Modell

2.1 Mathematisches Fundament

• Charges: Ein Charge $\mu$ ist eine endlich additive Wahrscheinlichkeitsmaß auf der Potenzmenge von $\mathbb{N}$.
• Diffuse Charges: $\mu(\{n\}) = 0$ für alle $n \in \mathbb{N}$.
• Integration: Der Payoff einer Strategie $\sigma$ wird als Integral der erwarteten Belohnungen $E_\sigma[r_t]$ bezüglich des Charges $\mu$ definiert:
  $$u_\mu(\sigma) = \int_{t \in \mathbb{N}} E_\sigma[r_t] \, \mu(dt)$$
• Topologie: Die Autoren nutzen die Topologie der punktweisen Konvergenz auf der Menge der Charges, um Grenzwerte von Folgen von Charges zu konstruieren.

2.2 Das Gegenbeispiel (Even-or-Odd MDP)

Um die Nichtexistenz optimaler Strategien zu beweisen, konstruieren die Autoren ein spezifisches MDP:

• Zustände: $S = \{1, 2, 3\}$. Startzustand ist 1.
• Aktionen: In Zustand 1 gibt es zwei Aktionen: $T$ (Top) und $B$ (Bottom). In Zuständen 2 und 3 gibt es jeweils nur eine deterministische Aktion.
• Übergänge & Belohnungen:
  • Aktion $T$ in Zustand 1: Belohnung 1, Übergang zu Zustand 2.
  • Aktion $B$ in Zustand 1: Belohnung 0, Übergang zu Zustand 3.
  • Aus Zustand 2 und 3 geht es deterministisch zurück zu Zustand 1.
  • Belohnung in Zustand 2 ist 0, in Zustand 3 ist 1.
• Struktur: Der Prozess verläuft in Blöcken von zwei Stufen. In jeder ungeraden Stufe $t$ muss der Entscheider wählen: Entweder Belohnung 1 jetzt und 0 im nächsten Schritt ($T$), oder 0 jetzt und 1 im nächsten Schritt ($B$).

2.3 Konstruktion des Aggregations-Charges $\mu$

Der entscheidende Teil ist die Konstruktion eines speziellen diffusen Charges $\mu$, das keine optimale Strategie zulässt.

1. Basis-Charge: Ein Frequenz-Charge $\phi$ (translation invariant) wird gewählt.
2. Teilmengen: Es werden Mengen $E_n$ definiert, wobei $E_0$ die ungeraden Zahlen sind und $E_n$ ($n \ge 1$) Zahlen der Form $k \cdot 2^n$ sind.
3. Folge von Charges: Es wird eine Folge von Charges $\mu_n$ definiert, die auf den Mengen $E_n$ konzentriert sind.
4. Grenzwert: Da der Raum der Charges kompakt ist, existiert ein Häufungspunkt $\mu^*$ der Folge $\{\mu_n\}$.
5. Das finale Charge: $\mu = \frac{1}{2}\mu_0 + \frac{1}{2}\mu^*$.
   • $\mu_0$ ist auf ungeraden Stufen konzentriert.
   • $\mu^*$ ist auf einer Struktur konzentriert, die „späte" gerade Stufen bevorzugt.

3. Hauptergebnisse

Theorem 3: Nichtexistenz optimaler Strategien

Im konstruierten „Even-or-Odd MDP" mit dem Charge $\mu$ existiert keine optimale Strategie, weder rein noch randomisiert.

Beweisidee:

1. Der Wert des Spiels ist 1 ($v_\mu = 1$):
   Es lässt sich zeigen, dass für jedes $\epsilon > 0$ eine Strategie existiert, die einen Payoff von $1 - \epsilon$erzielt. Dies wird erreicht, indem man die Aktion$B$(die den hohen Payoff in der nächsten Stufe liefert) nur in sehr spezifischen, weit entfernten Intervallen spielt, die von$\mu^*$stark gewichtet werden, aber$\mu_0$ kaum beeinflussen.
2. Keine Strategie erreicht 1:
   Angenommen, es gäbe eine Strategie $\sigma$ mit Payoff 1. Dann müsste die Menge der Stufen, an denen der erwartete Payoff $> 1/2$ ist, das Maß 1 bezüglich $\mu$ haben.
   • Dies impliziert, dass sowohl $\mu_0$ als auch $\mu^*$ diese Menge das Maß 1 geben müssen.
   • Aufgrund der Struktur des MDPs (Payoff $r_t + r_{t+1} = 1$) ist es unmöglich, in beiden aufeinanderfolgenden Stufen einen Erwartungswert $> 1/2$ zu haben.
   • Eine detaillierte Analyse zeigt einen Widerspruch: Eine Strategie, die gut für $\mu_0$ ist (häufig $T$ wählen), ist schlecht für $\mu^*$, und umgekehrt. Jede Strategie, die versucht, beide Komponenten zu optimieren, scheitert daran, den exakten Wert 1 zu erreichen.

Weitere Ergebnisse (Abschnitt 5)

• Nicht-Existenz stationärer Strategien: Selbst wenn eine optimale (nicht-stationäre) Strategie existiert, muss sie nicht stationär sein. Das Paper zeigt ein Beispiel, wo eine reine optimale Strategie existiert, aber keine stationäre Strategie den optimalen Wert erreicht.
• Nicht-diffuse Charges: Wenn das Charge nicht diffus ist (d.h. eine diskrete Komponente hat), existiert unter bestimmten Bedingungen wieder eine optimale Strategie (basierend auf dynamischer Programmierung). Die Nichtexistenz ist also ein Phänomen, das spezifisch für die Kombination aus unendlichem Horizont und rein diffusen Aggregationen auftritt.

4. Bedeutung und Beitrag

1. Auflösung einer offenen Frage: Das Paper beantwortet die von Neyman [2023] aufgeworfene Frage negativ. Es zeigt, dass die Existenz einer optimalen Strategie nicht garantiert ist, wenn das Aggregations-Charge nicht das Prinzip des Zeitwerts des Geldes erfüllt.
2. Pathologische Natur der Lösung: Das Ergebnis demonstriert, dass bei Verwendung von endlich additiven Maßen (diffusen Charges) die üblichen Intuitionen der Optimierung (Existenz eines Maximums) versagen können. Der Supremum-Wert wird erreicht, aber nie von einer konkreten Strategie realisiert.
3. Methodische Innovation: Die Konstruktion des Charges $\mu$ durch die Kombination eines Frequenz-Charges und eines Häufungspunkts einer spezifischen Folge von Charges ist ein elegantes und technisch anspruchsvolles Werkzeug, um die Nicht-Kompaktheit der Menge der erreichbaren Payoffs unter bestimmten Bedingungen zu zeigen.
4. Implikationen für die Theorie: Die Ergebnisse warnen davor, Annahmen über die Existenz optimaler Strategien in MDPs mit allgemeinen endlich additiven Bewertungen zu treffen, ohne spezifische Eigenschaften des Aggregationsmaßes (wie die des Zeitwerts des Geldes) zu überprüfen.

Fazit

Die Autoren beweisen, dass in MDPs mit endlich additiven, diffusen Aggregationen die Existenz einer optimalen Strategie (rein oder randomisiert) nicht allgemein gewährleistet ist. Durch ein sorgfältig konstruiertes Gegenbeispiel zeigen sie, dass der Wert des Spiels zwar definiert ist, aber keine Strategie diesen Wert tatsächlich annimmt. Dies unterstreicht die subtilen und manchmal kontraintuitiven Eigenschaften von Optimierungsproblemen unter Verwendung von endlich additiven Maßen.