Arme, Züge, Belohnungen
Eine Reihe von Spielautomaten
Stell dir K Spielautomaten in einer Reihe vor. Jeder Automat zahlt eine andere durchschnittliche Belohnung, aber du kennst keine der Durchschnittswerte. Bei jedem Schritt wählst du einen Automaten, ziehst den Hebel & beobachtest die Auszahlung. Dein Ziel: die Gesamtbelohnung über viele Züge maximieren.
Diese Konfiguration definiert ein Multi-Armed Bandit Problem. K = Anzahl der Arme. Ein Zug wählt einen Arm aus. Die Belohnung stammt aus der versteckten Verteilung dieses Arms. Der mean_reward(k) von Arm k verfolgt den laufenden Durchschnitt über die Züge von k.
Exploration vs. Exploitation
Zwei Kräfte ziehen gegeneinander:
Exploitation zieht den Arm mit dem höchsten beobachteten Mittelwert der Belohnung. Gierig. Risiko: Ein Arm, der nach 2 Zügen großartig aussah, könnte zum niedrigeren wahren Mittelwert zurückkehren.
Exploration zieht einen weniger getesteten Arm, um Unsicherheit zu reduzieren. Risiko: Zeit, die mit Erkunden verbracht wird, kostet Belohnungen, die du von einem bekannten guten Arm hättest sammeln können.
Eine gute Policy mischt beides. Reine Exploitation fixiert frühe Gewinner für immer. Reine Exploration sammelt nie eine Belohnung.
ANDREA's Arms = Dataquellen
ANDREA rahmt das Training als Bandit ein. Jede Datenquelle (hermes3-general, gutenberg, dictionary, synthetic-chat, smoltalk, etc.) wirkt als Arm. Jeder Trainingsschritt zieht einen Arm: Lade ein Dokument aus dieser Quelle, führe einen Forward-Pass durch, beobachte Verlustreduktion. Mittlere Belohnung pro Quelle verfolgt, wie sehr diese Quelle den Verlust im Durchschnitt verbessert.
Warum das passt: Das Modell braucht sich während des Trainings. Frühe Schritte profitieren von breiter Exposition (viele Quellen). Spätere Schritte profitieren von gezielter Politur (wenige hochbelohnte Quellen). Ein Bandit passt sich an; ein fester Sampling-Verhältnis kann das nicht.
Die Teile benennen
Der UCB1-Score
Auer, Cesa-Bianchi & Fischer, 2002
Peter Auer & Kollegen veröffentlichten UCB1 im Jahr 2002 als finite-time Bandit-Policy mit einer Regret-Bound von O(log N). UCB1 wählt einen Arm, indem es seinen aktuellen durchschnittlichen Reward mit einem Exploration-Bonus kombiniert, der schrumpft, je öfter der Arm gezogen wird.
Die Formel
UCB(k) = mean_reward(k) + C * sqrt(ln(N) / n_k)
Glied für Glied:
- mean_reward(k): durchschnittliche Belohnung, die für Arm k über seine n_k Züge beobachtet wurde. Exploitation-Term.
- N: Gesamtzüge über alle Arme bis jetzt. Wächst jeden Schritt.
- n_k: Züge von Arm k speziell. Wächst nur, wenn k ausgewählt wird.
- C: Erkundungskonstante. Standard-Tabellenwert: 1.4 (sqrt(2)). ANDREA verwendet C=0.5.
- sqrt(ln(N) / n_k): Konfidenzradius. Ein selten gezogener Arm hat kleinen n_k & erhält einen großen Bonus; ein gut gezogener Arm hat großen n_k & erhält einen kleinen Bonus.
Warum die Formel funktioniert
ln(N) wächst langsam (logarithmisch), sodass der Zähler mit der Gesamterfahrung sanft ansteigt. n_k im Nenner schrumpft den Term, während Beweise für einen spezifischen Arm sich ansammeln. Die Quadratwurzel dämpft die Reaktion, sodass ein einzelner untererforschter Arm nicht für immer dominiert.
Auswahl per argmax_k UCB(k) jeden Schritt balanciert beide Drücke automatisch. Kein Epsilon-Parameter, kein Zeitplan, keine Temperatur. Die Mathematik regelt es.
Berechne einen UCB-Score
Warum C=0.5 statt 1.4
Der Lehrbuchwert
Auer, Cesa-Bianchi & Fischer leiten eine Regret-Beschraenkung her, die annimmt, dass die Belohnungen in [0, 1] liegen. Die Beschraenkung gilt fuer C = sqrt(2) ca. 1.414. Die meisten Lehrbuecher lehren C=1.4 als sicheren Default-Wert.
Belohnungs-Groessenordnungen von ANDREA
ANDREA berichtet Verbesserungen des Verlusts pro Schritt als Belohnung. Rohe Verbesserungen liegen bei ca. 0.001 (Verlust sinkt von 4.521 auf 4.520). Nach dem 1000x Skalierungsfaktor (besprochen in Aktivitaet 78, Belohnungs-Zuschreibung) landen die skalierten Belohnungen bei ca. 1.0 Groesse. Mittlere Belohnungen ueber die Historie eines Arms liegen in einem Band von 0.5 bis 3.0.
Betrachten Sie nun den Erkundungsbonus bei C=1.4 mit N=10000, n_k=100:
1.4 sqrt(ln(10000) / 100) = 1.4 sqrt(9.21 / 100) = 1.4 * 0.303 = 0.425
0.425 liegt im Belohnungsbereich. Akzeptabel. Nun n_k=10 (ein seltener Arm):
1.4 sqrt(9.21 / 10) = 1.4 0.960 = 1.344
1.344 liegt ÜBER den meisten beobachteten mean_rewards. Exploration dominiert: Der seltene Arm gewinnt unabhängig von seinem tatsächlichen Mittelwert. Bei vielen Quellen & langen Trainingseinheiten flutet das den Zeitplan mit Arms mit niedrigem Mittelwert.
Die Lösung: C=0.5
0.5 sqrt(9.21 / 10) = 0.5 0.960 = 0.480
0.480 liegt unter den meisten Mittelwerten der Belohnungen. Exploration findet immer noch statt (seltene Arme erhalten immer noch einen Bonus), aber mean_reward führt. ANDREA nutzt mehr aus, erkundet weniger und vermeidet Exploration-Dominanz.
Tuning als Ingenieurkunst, nicht als Theorie
Die Lehrbuch-Grenze geht von Belohnungen in [0, 1] aus. ANDREA's Belohnungen liegen ungefähr in [0, 5]. Das Skalieren der Konstante passt die Konstante an die Größenordnung der Belohnungen an. Derselbe Algorithmus, kalibrierte Umgebung.
Diagnose Exploration Dominance
Als Nächstes
Was du hast
UCB1 wählt den Arm mit der höchsten oberen Konfidenzgrenze. Die Grenze kombiniert mean_reward (ausnutzen) mit sqrt(ln(N) / n_k) skaliert mit C (erkunden). ANDREA stimmt C=0.5 ab, weil die stufenweisen Belohnungen in einem Band von 0.5 bis 3.0 liegen, & der Lehrbuchwert 1.4 den Zeitplan mit niedrig-mean-Armen flutet.
Was bleibt
Vanilla UCB1 wählt einen Arm zur Zeit aus. ANDREA wählt mehrere Fokusarme pro Phase, mischt zuerst zufällige Arme, & hält jede Phase für 7 bis 42 Schritte. Diese Struktur (Aktivität 77: Würfelphasen) verhindert, dass UCB sich zu sehr auf frühe Gewinner festlegt, während es dennoch die Anstrengung konzentriert.
Belohnungsattribution (Aktivität 78) zeigt, wo mean_reward(k) tatsächlich herkommt. Böden & Epochenstrafen (Aktivität 79) legen schützende Regeln über die UCB-Ausgabe.
Referenz
- Auer, Cesa-Bianchi, Fischer (2002). "Finite-time Analysis of the Multiarmed Bandit Problem." Machine Learning, 47, 235-256.
- ANDREA Whitepaper, Abschnitte 3.1 & 3.4.