Das Explorations-Exploitations-Dilemma, auch bekannt als Explore-Exploit-Tradeoff, ist ein zentrales Konzept der Entscheidungsfindung, das in Bereichen von der Ökonomie bis zur künstlichen Intelligenz auftritt. Es beinhaltet die Abwägung zwischen zwei gegensätzlichen Strategien: Exploitation, also die Auswahl der besten Option auf Grundlage des aktuellen Wissens (das unvollständig oder irreführend sein kann), und Exploration, also das Ausprobieren neuer Optionen, die zu besseren zukünftigen Ergebnissen führen könnten, auf Kosten einer verpassten Exploitationsmöglichkeit. Das Ziel der Optimierung langfristiger Belohnungen erfordert eine effektive Auflösung dieses Gleichgewichts.
Im maschinellen Lernen ist der Tradeoff grundlegend für das bestärkende Lernen (RL), eine Art des Lernens, bei der ein Agent Entscheidungen auf der Grundlage von Feedback aus einer Umgebung trifft, das verzögert oder spärlich sein kann. Der Agent muss entscheiden, ob er eine derzeit bekannte beste Strategie ausnutzt oder neue Strategien erkundet, um die zukünftige Leistung zu verbessern. Das Dilemma tritt in Bereichen wie autonomes Fahren, Empfehlungssystemen und KI für Spiele auf.
Methoden für Mehrarmige Banditen
Das Problem des mehrarmigen Banditen (MAB) ist ein klassisches Beispiel für den Tradeoff, und viele Methoden wurden dafür entwickelt. Epsilon-Greedy ist ein einfacher Ansatz, bei dem der Agent die meiste Zeit die beste bekannte Aktion ausnutzt, aber mit der Wahrscheinlichkeit Epsilon eine zufällige Aktion wählt. Thompson-Sampling balanciert Exploration und Exploitation aus, indem es Posterior-Verteilungen über Belohnungen beibehält und aus diesen Stichproben zieht. Obere-Vertrauensgrenze-Algorithmen (UCB) wählen Aktionen aus, indem sie durchschnittliche Belohnungen mit Unsicherheitsboni vergleichen.
In komplexeren Umgebungen kann ein Agent jeden Entscheidungspunkt als einen MAB behandeln, bei dem die Auszahlung die erwartete zukünftige Belohnung ist. Beispielsweise verwendet die Monte-Carlo-Baumsuche eine UCB-Variante, um die Erkundung des Spielbaums zu steuern, wie in Programmen wie Schach-Engines zu sehen ist.
Explorationsprobleme
Bestimmte Umgebungen schaffen spezifische Herausforderungen für den Tradeoff.
Spärliche Belohnung: Wenn Belohnungen nur selten auftreten, bleiben Agenten möglicherweise nicht bei der Exploration. Ein Standardbeispiel ist das Atari-Spiel Montezuma's Revenge, bei dem klare Belohnungen rar sind.
Täuschende Belohnung: Wenn einige frühe Aktionen sofortige, aber kleine Belohnungen geben und andere größere verzögerte Belohnungen, könnten Agenten in der Ausbeutung der frühen kleinen Belohnungen gefangen bleiben.
Problem des verrauschten Fernsehers: Wenn einige Beobachtungen irreduzibel verrauscht sind, wie ein Fernseher mit zufälligen Bildern, könnte ein Agent stecken bleiben und wiederholt diese unvorhersehbaren Zustände beobachten.
Diese Probleme erschweren das Erreichen eines optimalen Gleichgewichts und erfordern zusätzliche Techniken, um die Exploration zu leiten.
Methoden mit Explorationsbelohnung
Methoden mit Explorationsbelohnung wandeln das Dilemma in ein rein exploitativeres Problem um, indem sie Exploration als eine Form intrinsischer Belohnung behandeln. Der Agent zielt dann darauf ab, die Summe aus extrinsischer Belohnung von der Umgebung und intrinsischem Explorationsbonus zu maximieren. Intrinsische und extrinsische Belohnungen werden zum Zeitschritt t als r_t^e und r_t^i geschrieben.
Dieser Ansatz unterscheidet sich von der Exploitation in zwei wesentlichen Punkten: Erstens wird die Explorationsbelohnung frei vom Forscher entworfen, während externe Belohnungen von der Umgebung gegeben werden; zweitens sind extrinsische Belohnungen normalerweise stationär, während intrinsische Belohnungen nicht-stationär sind, was bedeutet, dass dieselbe Aktion immer weniger Bonus ergibt, je vertrauter sie wird.
Zählbasierte Exploration misst, wie oft ein Zustand besucht wird, und belohnt weniger besuchte Zustände, aber dies ist nur in kleinen und diskreten Zustandsräumen machbar. Dichtebasierte Exploration erweitert dies mithilfe eines Dichtemodells, wobei der Besuch eines Zustands auch teilweise Gutschrift für nahegelegene Zustände gibt. Maximum-Entropie-Exploration fügt die Entropie der Agentenpolitik als intrinsischen Term hinzu, was eine Politik fördert, die zufällige oder vielfältige Aktionen bevorzugt.
Prädiktionsbasierte Exploration
Ein Vorwärtsdynamikmodell sagt den nächsten Zustand aus dem aktuellen Zustand und der Aktion voraus: f: (s_t, a_t) abgebildet auf s_{t+1}. Während der Agent mit der Umgebung interagiert, trainiert er dieses Modell, um besser bei der Vorhersage von Zustandsübergängen für vertraute Pfade zu werden. Ein prädiktionsbasierter Explorationsbonus definiert intrinsische Belohnung als den Fehler zwischen Modellvorhersagen und tatsächlichen nächsten Zuständen. Wenn ein Zustand neuartig ist, ist der Modellfehler hoch, was diese Aktion attraktiv macht.
Exploration durch Vorhersage ist besonders nützlich in hochdimensionalen Zustandsräumen, in denen Zählungen nicht verwendet werden können. Die Fehler des Modells dienen als Schätzung für Überraschung, was den Agenten dazu ermutigt, Zustände zu suchen, die schwerer vorherzusagen sind, und fördert so eine breitere Exploration ohne externe Anleitung. Diese Methode wird häufig in neueren tiefen bestärkenden Lernsystemen verwendet.