Erkunden oder Ausnutzen verständlich erklärt

Wer aus Erfahrung lernen will, welche von mehreren Ladestationen die beste ist, muss laufend abwägen: das Bewährte wählen oder Neues ausprobieren. Wer nur das Bewährte wählt, kann sich auf eine schlechte Station festlegen. Wer nur ausprobiert, nutzt sein Wissen nie. Diese Seite erklärt zuerst ohne Formeln, wie sich das Abwägen auflösen lässt, und danach für Fachleute mit Modell, Formeln, Messwerten und Grenzen. Sie ist der Einstieg in das Thema Reinforcement Learning (Lernen durch Ausprobieren und Rückmeldung) auf dieser Website.

Zuletzt aktualisiert: 28. Oktober 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Welche Ladestation ist die beste?

Stellen Sie sich einen Lagerroboter vor, der mehrere Ladestationen zur Wahl hat. An jeder Station geht das Laden mal schnell, mal langsam. Manche Stationen laden öfter schnell als andere: Die Station Nord zum Beispiel öfter als die Station Süd. Wie oft, bleibt fest, ist dem Roboter aber unbekannt. In jeder Runde wählt er eine Station und sieht danach nur, ob das Laden schnell oder langsam war. Über die Stationen, die er nicht gewählt hat, erfährt er nichts.

Ziel ist, über viele Runden möglichst oft schnell zu laden. Niemand sagt dem Roboter, welche Station die beste ist. Er muss es aus den Rückmeldungen lernen. Dieses Lernen durch Ausprobieren und Rückmeldung heißt auf Englisch Reinforcement Learning, auf Deutsch bestärkendes Lernen. Der Fall hier ist der einfachste davon: Die Wahl einer Station hat keine Folgen für die nächste Runde, und die Stationen verändern sich nicht. Ein Bild dazu: Spielautomaten mit mehreren Hebeln, von denen jeder mit eigener Wahrscheinlichkeit gewinnt. Fachleute nennen den Fall deshalb Banditenproblem, nach dem Spitznamen „einarmiger Bandit“ für solche Automaten.

Warum ist das schwer?

Ein einzelnes Ergebnis sagt wenig. Auch eine schlechte Station lädt manchmal schnell, und eine gute manchmal langsam. Nach wenigen Runden kann der Roboter eine Station für die beste halten, die es gar nicht ist.

Daraus entsteht ein Zwiespalt. Wählt der Roboter immer die Station, die bisher am besten aussah, nutzt er aus (englisch Exploitation), was er schon weiß. Probiert er andere Stationen aus, erkundet er (Exploration). Das kostet Runden, in denen er eine schlechtere Station erwischt. Zu wenig Erkunden kann dazu führen, dass er bei einer mittelmäßigen Station hängen bleibt, weil er die bessere nie getestet hat. Zu viel Erkunden verschenkt Runden, obwohl er die beste Station längst kennen könnte.

Zwei Extreme zeigen das. Ein zufälliger Roboter wählt in jeder Runde irgendeine Station: Er erkundet nur und nutzt sein Wissen nie. Ein gieriger Roboter nimmt immer die Station mit dem bisher besten Durchschnitt: Er nutzt nur aus und erkundet nie. Als Maßstab dient der entgangene Ertrag: Wie viel hätte der Roboter gewonnen, wenn er die beste Station von der ersten Runde an gekannt hätte? Je kleiner, desto besser. Das Fachwort dafür ist Regret.

Was die Demo zeigt

In der Demo spielt jeder Roboter viele Durchläufe mit denselben Stationen, jeweils mit anderem Zufall. Der gierige Roboter hat dabei ein echtes Risiko: Fallen die ersten Ergebnisse unglücklich aus, legt er sich auf eine schlechte Station fest und korrigiert das nie, weil er die anderen nicht mehr probiert. In der Demo ist ihm das bei einem Teil der Durchläufe passiert (der genaue Anteil steht im Fachteil). Sein Ergebnis hängt also stark vom Zufall der ersten Versuche ab.

Besser fährt in der Demo ein Roboter, der gierig mit kleinem Zufallsanteil wählt: Meist nimmt er die bisher beste Station, in einem festen kleinen Teil der Runden aber eine zufällige. (Fachleute nennen das Epsilon-gierig.) Bei ihm blieb in der Demo kein Durchlauf hängen. Welcher Zufallsanteil am besten ist, hängt vom Ziel ab: Von den in der Demo getesteten Anteilen war ein kleiner im Durchschnitt am besten, der nächstgrößere dafür zuverlässiger. Die Zahlen stehen im Fachteil.

Zwei weitere Verfahren, im Fachteil beschrieben, gehen gezielter vor: Sie zählen mit, wie oft sie jede Station schon getestet haben, und probieren die weniger getesteten bevorzugt aus. In den langen Läufen der Demo sammeln sie langsamer entgangenen Ertrag an als die einfachen Regeln. Dafür kostet das Testen zu Beginn Runden: In diesen Läufen liegt der gierige Roboter im Durchschnitt zunächst vorn und fällt erst später zurück.

Warum ein einzelner Durchlauf täuscht

Obwohl der gierige Roboter in der Demo bei einem Teil der Durchläufe festhängt, gewinnt er in dem Beispiel, das die Demo beim Öffnen zeigt, im einzelnen Durchlauf, und zwar schlicht mit Glück: Seine ersten Versuche trafen gleich die beste Station. Wer nur diesen einen Durchlauf sieht, zieht den falschen Schluss. Belastbar ist erst der Vergleich über viele Durchläufe, wie ihn die Demo in ihren drei Auswertungen weiter unten zeigt. Das gilt für jede Auswertung eines Lernverfahrens, bei der der Zufall mitspielt.

Wie ernst ist das Modell zu nehmen?

Die Demo ist stark vereinfacht. Erstens sind die Stationen erzeugt, nicht in einem echten Lager gemessen, und ihre Eigenschaften bleiben fest; die Wahl hat keine Folgen für spätere Runden. Zweitens haben echte Auswahlprobleme, etwa die Wahl eines Lieferanten, ein Preistest oder der Vergleich zweier Bestellregeln, mehr Möglichkeiten mit ähnlicheren Ergebnissen, und diese können sich mit der Zeit ändern. Die Demo zeigt, wie das Abwägen funktioniert, nicht welcher Wert in einem bestimmten Betrieb passt.

Was Sie mitnehmen: Wenn ein System oder ein Planer aus Erfahrung zwischen mehreren Möglichkeiten wählt, fragen Sie, ob es auch dann weiter Alternativen ausprobiert, wenn eine Möglichkeit bisher gut aussieht, und wer die Höhe dieses Anteils festlegt. Ein Verfahren, das nur das bisher Beste wählt, kann sich auf eine schlechte Möglichkeit festlegen. Das gilt, solange die Möglichkeiten fest bleiben und jede Wahl keine Folgen für die nächste hat. Im Betrieb erkennen Sie zu wenig Ausprobieren daran, dass eine Möglichkeit seit Wochen nicht mehr geprüft wurde, obwohl sich die Bedingungen geändert haben.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.

• Modell: \(K\) Ladestationen, Station \(k\) liefert mit fester, unbekannter Wahrscheinlichkeit \(\theta_k\) eine kurze Ladezeit (Reward 1), sonst eine lange (Reward 0): ein Bernoulli-Bandit ohne Zustand und ohne Folgen für künftige Runden. Die beste Station liegt um einen wählbaren Abstand über dem Maximum der übrigen \(K-1\) Stationen, die um eine Grundrate mit wählbarer Streuung schwanken. Die Schwierigkeit des Problems ist so ein eigener Regler.
• Maßstab: das Regret \(R(T)\), der Erwartungswert des entgangenen Ertrags (nicht der verrauschte tatsächliche), und der Anteil der Ziehungen der besten Station in den letzten 10 % der Runden.
• Verfahren: Zufällig, Gierig (eine nie gezogene Station zählt als \(+\infty\)), Epsilon-gierig (Mischung), UCB1 (Mittelwert plus Vertrauensbonus) und Thompson Sampling (Beta-Posterior je Station, Beta(1,1)-Vorwissen). Ein Gleichstand wird zufällig unter den Bestplatzierten aufgelöst.
• Experimente: drei Experimente mit festen Zufalls-Seeds: wie das Regret mit der Zeit wächst, wie die Erkundungsrate Epsilon Regret und Risiko des Festlegens beeinflusst, und wie der Abstand zwischen bester und zweitbester Station UCB1 und Thompson Sampling trifft.

Die Formeln

Der Maßstab ist das kumulierte Regret. Dabei ist \(\theta^* = \max_k \theta_k\) die Erfolgswahrscheinlichkeit der besten Station und \(a_t\) die in Runde \(t\) gewählte Station:

\[R(T) = \sum_{t=1}^T (\theta^* - \theta_{a_t})\]

Gierig wählt \(a_t = \arg\max_k \hat\theta_k(t)\) mit dem Mittelwert \(\hat\theta_k(t)\) der bisherigen Ziehungen von Station \(k\). Epsilon-gierig wählt mit Wahrscheinlichkeit \(\varepsilon\) zufällig und sonst gierig. UCB1 addiert zum Mittelwert einen Vertrauensbonus, der mit der Zahl \(n_k(t)\) der Ziehungen von Station \(k\) schrumpft und für selten gezogene Stationen wächst (Auer, Cesa-Bianchi und Fischer 2002):

\[a_t = \arg\max_k \left(\hat\theta_k(t) + \sqrt{\dfrac{2\ln t}{n_k(t)}}\right)\]

Thompson Sampling startet mit dem Vorwissen Beta(1,1) je Station. Nach \(n_k\) Ziehungen mit \(s_k\) Erfolgen ist der Posterior (die Verteilung von \(\theta_k\) nach Sicht der bisherigen Daten) eine Beta-Verteilung. Das Verfahren zieht aus jedem Posterior eine Stichprobe und wählt \(a_t = \arg\max_k \tilde\theta_k\) mit

\[\tilde\theta_k \sim \text{Beta}(s_k+1, n_k-s_k+1)\]

Für UCB1 gilt mit \(\Delta_k = \theta^* - \theta_k\) die Schranke von Auer, Cesa-Bianchi und Fischer (2002): logarithmisch in \(T\), linear in \(1/\Delta_k\).

\[R(T) = O\!\left(\sum_{k \ne k^*} \dfrac{\ln T}{\Delta_k}\right)\]

Ohne Erkunden (Gierig) und bei fester Erkundungsrate (Epsilon-gierig) wächst das Regret asymptotisch linear in \(T\). Die Schranke ist asymptotisch; für endliche \(T\) sagt sie nichts über die Konstanten.

Befunde

Alle Zahlen stammen aus der README der Demo; deren Tests prüfen sie mit Toleranz (tests/test_claims.py). Die Experimente laufen alle auf einem einzigen erzeugten Banditen (K=10, Abstand 0,10, Voreinstellung der Demo); die Seeds ändern nur die Zufallszahlen der Verfahren, die Aussagen gelten also für diesen Banditen. Die Zeilen über mehrere Zufalls-Seeds sind Mittel, und „±“ ist der Standardfehler des Mittels über die Seeds. Die Zeilen mit Voreinstellungen (Presets) sind Einzelläufe mit Zufalls-Seed 3 und 1000 Runden und deshalb nicht belastbar. Kleineres Regret ist besser.

Frage	Befund
Wächst das Regret linear oder logarithmisch? (30 feste Seeds, Runden 500 bis 20 000)	Steigung einer Ausgleichsgeraden von log(Regret) gegen log(Runde): Zufällig 1,00 (exakt linear), Gierig 0,92, Epsilon-gierig (0,1) 0,72, UCB1 0,50, Thompson Sampling 0,22 (deutlich flacher als linear).
Zieht Gierig anfangs an UCB1 vorbei?	Bei Runde 10 000 liegt Gierig im Mittel noch vorn (445 gegen 466 bei UCB1); erst bei Runde 15 000 dreht sich das um (663 gegen 526). Die Anfangs-Erkundung von UCB1 kostet zunächst mehr, als sie bringt.
Wie stark soll man erkunden? (20 000 Runden, 60 feste Seeds)	Gierig (Epsilon 0) bleibt bei 40,0 % der Seeds auf einer schlechten Station hängen (Regret 1030,7 ± 179,4, riesige Streuung). „Hängen geblieben“ heißt: In den letzten 10 % der Runden wird die beste Station in weniger als 10 % der Fälle gezogen. Das beste mittlere Regret liefert Epsilon 0,05 (388,4 ± 41,7). Epsilon 0,1 ist mit 547,4 ± 20,0 im Mittel schlechter, aber deutlich zuverlässiger (kein hängen gebliebener Lauf).
Wie schwer ist das Problem? (30 feste Seeds, 20 000 Runden)	Abstand 0,02 (schwer): UCB1 657,7 ± 9,7, Thompson Sampling 150,2 ± 7,2. Abstand 0,20 (leicht): UCB1 415,3 ± 6,4, Thompson Sampling 56,5 ± 2,0. Beide wachsen mit sinkendem Abstand, wie die Schranke es vorhersagt. Thompson Sampling bleibt bei jedem der getesteten Abstände unter UCB1 (Chapelle und Li 2011).
Standardfall (K=10, Abstand 0,10, 1000 Runden, Zufalls-Seed 3; Einzellauf)	Gierig gewinnt hier zufällig (Regret 11,3, 100 % beste Station, ein einzelner glücklicher Lauf). Thompson Sampling 72,5 (87 %), UCB1 142,9 (55 %), Epsilon-gierig 32,1 (86 %), Zufällig 244,4 (9 %).
Kleiner und großer Abstand (Einzelläufe)	Bei Abstand 0,02 fällt UCB1 auf 37 % beste Station (Regret 106,9), Thompson Sampling hält 92 % (Regret 25,2). Bei Abstand 0,20 erreicht UCB1 86 % (Regret 148,1), Thompson Sampling 99 % (Regret 21,8).
Viele Stationen (K=20; Einzellauf)	UCB1 trifft nur 23 % (Regret 216,9). Mehr Stationen heißt eine längere Aufwärmphase, bevor irgendein Lernen greift.

Grenzen

• Feste Erfolgswahrscheinlichkeiten: Ändert sich eine Station mit der Zeit, lernen alle fünf Verfahren einen veralteten Wert; UCB1 und Thompson Sampling haben kein Vergessen eingebaut. Gleitende Fenster, diskontierte Zähler oder ein gleitender UCB setzen dort an.
• Keine Folgen für künftige Runden: Sobald eine Wahl den Zustand verändert, ist es kein Bandit mehr, sondern ein Markov-Entscheidungsprozess.
• Ein Entscheider, keine Gegenspieler: Bei mehreren sich gegenseitig beeinflussenden Entscheidern ist die Umgebung nicht mehr stationär; das ist ein anderes Problem (adversariales Online-Lernen).
• Bernoulli-Reward: Bei kontinuierlichen Rewards ändern sich die Bonusformel von UCB1 und die Beta-Verteilung von Thompson Sampling.
• Ein erzeugter Bandit: Alle Experimente laufen auf demselben Banditen; die Zahlen und ihre Standardfehler gelten für dieses Vehikel und seine Regler, nicht für andere Stationen. Reale Auswahlprobleme haben oft mehr Stationen mit ähnlicheren Werten, also einen kleineren Abstand.
• Einzelne Messreihen: Dass Epsilon 0,05 das kleinste mittlere Regret liefert, ist ein Befund dieser Messung, kein allgemeiner bester Wert. Das Skalengesetz der Schranke gilt nur asymptotisch: Bei zehnmal kleinerem Abstand steigt das Regret von UCB1 hier nicht auf das Zehnfache. Dass Thompson Sampling UCB1 schlägt, ist hier gemessen und nicht bewiesen.
• Nicht enthalten: kontextuelle Bandits (Merkmale je Runde), nicht-stationäre und adversariale Bandits sowie Gauß'sche Rewards. Gierig hat in der Demo kein Sicherheitsnetz wie abklingendes Epsilon oder optimistische Startwerte.

Quellen

• Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002): Finite-time analysis of the multiarmed bandit problem. Machine Learning 47, 235–256.
• Thompson, W. R. (1933): On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25, 285–294.
• Chapelle, O., & Li, L. (2011): An empirical evaluation of Thompson sampling. Advances in Neural Information Processing Systems 24.
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/bandit-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen. Die Namen, Jahre und die Aussagen zu Auer et al. (2002), Thompson (1933) und Chapelle und Li (2011) stammen aus der README der Demo; die vollständigen Angaben (Zeitschrift, Seiten) stammen aus dem Gedächtnis des Autors und sind nicht gegen die Originale geprüft. Dass „±“ ein Standardfehler ist, dass die Experimente einen einzigen erzeugten Banditen mit den Reglern der Voreinstellung verwenden und die Seeds nur die Zufallszahlen der Verfahren ändern, steht im Quelltext (bd_evaluation.py), nicht in der README.