🤖 machine learning

An Information-Theoretic Definition for Open-Ended Learning

Dieses Paper führt eine informationstheoretische Definition von offen endlichem Lernen ein, die auf dem Konzept der „Bit-Äquivalenz“ basiert, um die für die Erzielung von Belohnungen erforderliche Information zu quantifizieren, wobei demonstriert wird, dass ein lineares Wachstum in dieser Metrik offen endliche Umgebungen von klassischen Banditen unterscheidet, und präsentiert einen Algorithmus, der ein solches Lernen erreicht.

Ursprüngliche Autoren: Wanqiao Xu, Yifan Zhu, Benjamin Van Roy

Veröffentlicht 2026-06-09

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Wanqiao Xu, Yifan Zhu, Benjamin Van Roy

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 spielen ein Videospiel. In einem normalen Spiel gibt es einen Endboss, einen Highscore und einen klaren Weg zum Sieg. Sobald Sie den Boss besiegt haben, ist das Spiel „gelöst“. Sie können nicht viel besser darin werden, weil es nichts Neues mehr zu lernen gibt.

Stellen Sie sich nun eine andere Art von Spiel vor. Eines, bei dem sich mit jedem Mal Spielen neue Level, neue Mechaniken und neue Herausforderungen offenbaren, die Sie sich vorher nicht hätten vorstellen können. Das Spiel endet nie, und Sie hören nie auf, klüger zu werden. Dies ist das, was die Autoren als Open-Ended Learning (offen endendes Lernen) bezeichnen.

Die Arbeit von Xu, Zhu und Van Roy versucht, eine sehr knifflige Frage zu beantworten: Woher wissen wir, ob eine KI wirklich in einem Spiel spielt, das niemals endet, oder ob sie nur ein sehr langes, langweiliges Spiel spielt?

Hier ist die Aufschlüsselung ihrer Ideen unter Verwendung einfacher Analogien.

1. Das Problem: „Neuheit“ reicht nicht aus

Früher dachten die Leute, eine Umgebung sei „offen endend“, wenn sie der KI immer wieder neue, seltsame und interessante Dinge zum Tun bot. Die Autoren sagen: „Moment mal.“

Stellen Sie sich einen Roboter vor, der ständig zufällige, seltsame Zeichnungen generiert. Sie sind alle „neu“ (neuartig) und man kann „lernen“, sie zu erkennen. Aber wird der Roboter dadurch tatsächlich besser im Zeichnen? Nein. Er erzeugt nur Rauschen.

Die Autoren argumentieren, dass wahre Offenendigkeit nicht nur darin besteht, neue Dinge zu erschaffen; es geht darum, kontinuierlich neue Informationen benötigen zu müssen, um besser zu werden. Wenn man einen Highscore erzielen kann, ohne etwas Neues zu lernen, dann ist das Spiel nicht offen endend.

2. Das neue Werkzeug: Das „Bit-Äquivalent“

Um dies zu messen, haben die Autoren ein neues Konzept erfunden: das Bit-Äquivalent.

Betrachten Sie „Bits“ als die Währung der Information.

Das Konzept: Das „Bit-Äquivalent“ einer Belohnung ist die minimale Menge an Information, die man benötigt, um die Welt zu verstehen, um genau diese spezifische Belohnung zu verdienen.
Die Analogie: Stellen Sie sich vor, Sie versuchen, einen verborgenen Schatz zu finden.
- Wenn der Schatz ein 1-Euro-Stück ist, das auf dem Bürgersteig liegt, benötigen Sie null Bits an Information, um ihn zu finden. Sie schauen einfach nach unten.
- Wenn der Schatz ein Diamant ist, der in einer riesigen Höhle mit einer komplexen Karte versteckt ist, benötigen Sie viele Bits an Information (die Karte, das Layout, die Hinweise), um ihn zu finden.

Die Autoren definieren eine Umgebung nur dann als Open-Ended, wenn die KI, um immer bessere Belohnungen zu erhalten, immer mehr Informationen (Bits) sammeln muss, und zwar in einem stetigen, linearen Tempo. Wenn die KI Belohnungen erhalten kann, ohne neue Informationen zu lernen, ist die Umgebung „geschlossen“.

3. Der Test: Warum alte Spiele versagen

Die Autoren haben diese Definition an „klassischen“ KI-Spielen (genannt Bandit-Umgebungen) getestet. Sie fanden heraus, dass fast alle von ihnen den Test auf Offenendigkeit nicht bestehen.

Endliche Spiele (Der Finite-Armed Bandit): Stellen Sie sich einen Spielautomaten mit 10 Hebeln vor. Sobald Sie herausgefunden haben, welcher Hebel am meisten auszahlt, ziehen Sie einfach immer diesen einen. Sie hören auf zu lernen. Das „Bit-Äquivalent“ hört auf zu wachsen.
Unendliche Spiele (Der Infinite-Armed Bandit): Stellen Sie sich einen Spielautomaten mit unendlich vielen Hebeln vor, aber jeder Hebel ist völlig zufällig und steht in keiner Beziehung zu den anderen. Sie können jedes Mal einen neuen Hebel ziehen und eine neue Belohnung erhalten, aber Sie lernen keinen Musterzusammenhang. Sie bauen kein tieferes Verständnis der Maschine auf. Die Information, die Sie gewinnen, hilft Ihnen nicht dabei, langfristig bessere Belohnungen zu erzielen.

In beiden Fällen stößt die KI an eine Wand, an der sie nicht besser werden kann, ohne mehr zu lernen, aber die Umgebung erlaubt dies nicht durch kontinuierliches Lernen.

4. Die Lösung: Das „unersättliche“ Spiel

Die Autoren haben daraufhin ein neues, maßgeschneidertes Spiel entwickelt, den Insatiable Linear Bandit (den unersättlichen linearen Banditen).

Der Aufbau: Stellen Sie sich eine riesige, unendliche Reihe von Lichtschaltern vor. Jeder Schalter steuert ein winziges Stück Ihres Scores. Einige Schalter sind defekt (sie senken Ihren Score) und einige sind gut (sie erhöhen ihn).
Der Haken: Sie wissen nicht, welche Schalter gut sind. Sie müssen sie umlegen, um es herauszufinden.
Warum es funktioniert: Da die Reihe unendlich ist, gibt es immer einen neuen, noch unentdeckten Abschnitt von Schaltern, die gut sein könnten. Um einen höheren Score zu erzielen, müssen Sie ständig mehr Schalter umlegen und das Muster lernen, welche davon funktionieren. Sie können das Spiel nie „lösen“, da das Spiel unendlich tief ist.

5. Die Strategie: „Truncated Thompson Sampling“

Die Autoren haben auch versucht, einer KI beizubringen, wie man dieses neue Spiel spielt. Sie fanden heraus, dass Standard-KI-Strategien scheiterten:

Zu gierig: Wenn die KI versucht, die gesamte unendliche Reihe auf einmal zu lernen, wird sie überfordert und macht Fehler, die ihren Score schaden.
Zu klein: Wenn die KI nur die ersten 10 Schalter betrachtet und den Rest ignoriert, hört sie nach einer Weile auf, sich zu verbessern.

Die Gewinnstrategie: Die Autoren entwickelten eine Methode namens Truncated Thompson Sampling (TTS).

Die Analogie: Stellen Sie sich vor, Sie lesen eine riesige, unendliche Enzyklopädie.
- Versuchen Sie nicht, das ganze Buch an einem Tag zu lesen (Sie werden scheitern).
- Lesen Sie nicht ewig nur die erste Seite (Sie werden nichts Neues lernen).
- Der TTS-Weg: Lesen Sie das erste Kapitel. Meistern Sie es. Dann gehen Sie zum zweiten Kapitel über. Dann zum dritten. Sie erweitern Ihr „Lesefenster“ immer gerade so weit, dass Sie Ihrer Lernkurve immer einen Schritt voraus bleiben.

Indem die KI den Umfang dessen, was sie zu lernen versucht, langsam erweitert, kann sie ewig neue „gute Schalter“ finden, und ihr Score (und die Information, die sie besitzt) steigt linear an.

Zusammenfassung

Das Paper behauptet:

Wahre Offenendlichkeit bedeutet eine Umgebung, in der man, um besser zu werden, kontinuierlich neue Informationen in einem stetigen Tempo lernen muss.
Die meisten aktuellen KI-Spiele sind nicht offen endend, da man irgendwann aufhört, neue Informationen lernen zu müssen, um Belohnungen zu erhalten.
Sie haben ein neues Spiel gebaut (den Insatiable Linear Bandit), in dem man lernen muss, um sich zu verbessern.
Sie haben eine neue KI-Strategie entwickelt (Truncated Thompson Sampling), die dieses Spiel erfolgreich spielt, indem sie ihren Wissenshorizont langsam erweitert, was beweist, dass Open-ended Learning unter den richtigen Bedingungen möglich ist.

Technisches Resümee: Eine informationstheoretische Definition für Open-Ended Learning

Problemstellung

Die Arbeit befasst sich mit dem Mangel an einer kohärenten theoretischen Definition von Open-Endedness (Offenheit) in KI-Systemen. Während die bestehende Literatur offene Umgebungen als solche charakterisiert, die zunehmend neuartige und komplexe Aufgaben präsentieren, oder sie über die Neuartigkeit und Lernbarkeit von Agenten-produzierten Artefakten definiert, versäumen es diese Definitionen zu erfassen, ob ein Agent in der Lage ist, seine Fähigkeiten durch Interaktion nachhaltig zu verbessern. Das Generieren neuartiger Policies impliziert nicht zwangsläufig den Erwerb von Information, die eine verbesserte Performance ermöglicht.

Die Autoren schlagen vor, Open-Endedness zu formalisieren, indem sie die Beziehung zwischen erwartetem Reward (Belohnung) und der benötigten Information zur Erzielung dieses Rewards untersuchen. Die zentrale Frage lautet: Erlaubt eine Umgebung eine nachhaltige Verbesserung des Rewards, die eine kontinuierliche Akquisition nützlicher Information mit einer nicht verschwindenden Rate erfordert?

Methodik und Definitionen

Das Bit-Äquivalent

Der zentrale methodische Beitrag ist die Einführung des Bit-Äquivalents ( $B_\rho$ ). Dieses Konzept quantifiziert die minimale Menge an Information (gemessen in Nats) über den Umgebungsparameter $\theta$ , die erforderlich ist, um eine Aktion zu wählen, die einen erwarteten Reward von mindestens $\rho$ liefert.

Formal gilt für ein erwartetes Reward-Niveau $\rho$ :
$B_\rho = \inf_{A: \mathbb{E}[r_\theta(A)] \geq \rho} I(\theta; A)$
wobei $I(\theta; A)$ die gegenseitige Information (Mutual Information) zwischen dem Umgebungsparameter und der Aktion ist.

Durchschnittliches Bit-Äquivalent und Open-Endedness

Die Performance eines Agenten $\pi$ über die Zeit $T$ wird durch das durchschnittliche Bit-Äquivalent ( $B_T(\pi)$ ) charakterisiert, definiert als der zeitliche Durchschnitt der Bit-Äquivalente der erzielten Rewards:
$B_T(\pi) = \frac{1}{T} \sum_{t=0}^{T-1} B_{\mathbb{E}_\pi[R_{t+1}]}$

Definition von Open-Endedness: Eine Umgebung wird als open-ended definiert, wenn es einen Agenten $\pi$ gibt, sodass das durchschnittliche Bit-Äquivalent linear mit der Zeit wächst:
$B_T(\pi) = \Omega(T)$
Ein Agent erreicht Open-Ended Learning, wenn er diese lineare Wachstumsrate realisiert.

Analytischer Rahmen

Die Autoren analysieren diese Definition im Kontext von Bandit-Umgebungen. Sie unterscheiden zwischen:

Informationsgewinn ( $\gamma_T$ ): Die gesamte gegenseitige Information $I(\theta; H_T)$ , die in der Historie enthalten ist.
Bit-Äquivalent-Wachstum: Die spezifische Information, die für Verbesserungen des Rewards erforderlich ist.

Die Arbeit stellt fest, dass während ein sublinearer Informationsgewinn eine Nicht-Open-Endedness impliziert, ein linearer Informationsgewinn nicht hinreichend für Open-Endedness ist. Eine Umgebung kann zwar eine lineare Informationsakquisition ermöglichen, aber wenn diese Information nicht in ein nachhaltiges, reward-relevantes Bit-Äquivalent-Wachstum übersetzt wird, ist die Umgebung nicht open-ended.

Zentrale Beiträge und Ergebnisse

1. Negative Ergebnisse: Klassische Umgebungen sind nicht Open-Ended

Die Arbeit beweist, dass mehrere Standard-Bandit-Umgebungen das Kriterium der Open-Endedness verfehlen:

Finite-armed Bandits: Selbst mit nicht-gaußschem Rauschen, das einen unendlichen Informationsgewinn erlaubt, begrenzt der endliche Aktionsraum das Bit-Äquivalent durch $\log |A|$ . Somit gilt $B_T(\pi) \leq \log |A|$ , was nicht $\Omega(T)$ entspricht.
Finite-dimensional Linear Bandits (Gauß): Der Informationsgewinn wächst als $O(d \log T)$ , was sublinear ( $o(T)$ ) ist.
Gaussian Process (GP) Bandits: Unter Standard-Kernel-Annahmen (z. B. Matérn, Squared Exponential) sorgt das spektrale Abklingen der Eigenwerte des Kernels dafür, dass der Informationsgewinn sublinear ist.
Infinite-Armed Bandits (i.i.d. Mittelwerte): Trotz potenziell unbeschränktem Informationsgewinn wächst das durchschnittliche Bit-Äquivalent höchstens logarithmisch ( $O(\log T)$ ), da die schwache Kopplung zwischen unabhängigen Armen ein lineares Wachstum nützlicher Information verhindert.

2. Positives Ergebnis: Der „Insatiable Linear Bandit“

Die Autoren konstruieren eine spezifische Umgebung, den insatiable linear bandit, welcher open-ended ist.

Setup: Der Aktionsraum $A$ besteht aus unendlichdimensionalen binären Vektoren mit endlicher Unterstützung ( $a \in \{0,1\}^\mathbb{N}, \|a\|_1 < \infty$ ). Der Parameter $\theta \in \mathbb{R}^\mathbb{N}$ hat unabhängige Komponenten $\theta_i \sim \mathcal{N}(-1, 1)$ . Der Reward ist $r_\theta(a) = \langle \theta, a \rangle + \text{noise}$ .
Schlüsseleigenschaft: Im Gegensatz zu GP-Bandits sind die Eigenwerte des Kernels in der Koordinatenbasis nicht summierbar, wodurch die Bedingungen für das spektrale Tail-Verhalten verletzt werden, die den Informationsgewinn begrenzen würden.
Ergebnis: Die Autoren beweisen, dass $B_T(\pi) = \Omega(T)$ für diese Umgebung gilt, womit die Definition von Open-Endedness erfüllt ist.

3. Algorithmisches Versagen und Erfolg

Die Arbeit analysiert, warum klassische Algorithmen im insatiable linear bandit scheitern, und schlägt eine erfolgreiche Alternative vor:

Versagen von Thompson Sampling (TS): Standard-TS versucht, über die voll-unendlichdimensionale Posterior-Verteilung zu optimieren. Da die Posterior-Stichprobe $\theta^{(t)}$ mit Wahrscheinlichkeit 1 unendlich viele positive Koordinaten hat, ist das Supremum des Rewards innerhalb des zulässigen Aktionsraums $A$ nicht erreichbar. Selbst mit endlicher Trunkierung divergiert der erwartete Reward des Maximierers gegen $-\infty$ , wenn die Größe der Trunkierung zunimmt.
Versagen von Fixed Truncation (FT): Das Festlegen einer endlichen Dimension $M$ begrenzt die Informationsakquisition auf $O(M \log 2)$ , was ein lineares Wachstum verhindert.
Erfolg von Truncated Thompson Sampling (TTS): Die Autoren führen TTS ein, das eine Sequenz von Lernzielen verwendet. Anstatt das vollständige $\theta$ $θ$ oder eine feste Trunkierung zu lernen, erhöht der Agent die Trunkierungsebene $m_t$ $m_{t}$ dynamisch über die Zeit.
- Mechanismus: Der Agent wählt eine Trunkierungsebene $m_t$ basierend auf der Historie, zieht eine Stichprobe der Posterior für die ersten $m_t$ Koordinaten und handelt optimal für diesen trunkierten Parameter.
- Theoretische Garantie: Durch eine sorgfältige Planung des Wachstums von $m_t$ (Abwägung zwischen Exploration neuer Koordinaten und Exploitation bereits gelernter) erreicht TTS einen kumulativen Reward von $\Omega(T^2)$ . Da Reward-Wachstum ein Bit-Äquivalent-Wachstum impliziert, erreicht TTS $B_T(\pi) = \Omega(T)$ und beweist damit Open-Ended Learning.

Bedeutung und Limitationen

Bedeutung

Die Arbeit liefert die erste quantitative, informationstheoretische Definition von Open-Endedness, die die Leistungsverbesserung direkt mit dem Erwerb nützlicher Information verknüpft. Sie zeigt auf:

Reward allein ist unzureichend: Hohe oder unbeschränkte Rewards garantieren keine Open-Endedness; die Informationskosten zur Erzielung dieser Rewards sind die kritische Metrik.
Klassische Annahmen sind unzureichend: Unbeschränkte Rewards und unendliche Aktionsräume (die oft als Voraussetzung für Open-Endedness angenommen werden) sind keine hinreichenden Bedingungen.
Lernziele sind entscheidend: Das Erreichen von Open-Endedness erfordert, dass ein Agent seine Lernziele anpasst (z. B. via TTS), anstatt zu versuchen, den vollständigen Umgebungszustand zu lernen oder eine statische Approximation beizubehalten.

Limitationen

Die Autoren weisen explizit auf zwei wesentliche Limitationen hin:

Bandit-Setting: Die Definition und Analyse beschränken sich derzeit auf Bandit-Umgebungen (zustandslos). Die Erweiterung dieses Rahmens auf zustandsbehaftete, nicht-stationäre oder vollständige Reinforcement Learning (RL) Umgebungen ist ein notwendiger nächster Schritt.
Abhängigkeit von Hyperparametern: Der vorgeschlagene TTS-Algorithmus erfordert eine vordefinierte Sequenz von Lernzielen (Trunkierungsebenen). Die Autoren räumen ein, dass das Design von Agenten, die diese Ziele autonom ohne bewusste Wahl von Hyperparametetern bestimmen können, eine offene Herausforderung bleibt.

Die Arbeit schließt mit dem Hinweis, dass der TTS-Agent zwar als „Sanity Check“ für die Intuition dient, dass Agenten ihre Lernziele kontinuierlich erweitern müssen, der Rahmen jedoch eine rigorose Grundlage für zukünftige theoretische Analysen und Designprinzipien für Open-Ended Learning bietet.