🤖 machine learning

Mean-based algorithms: A lower bound and regret

Diese Arbeit etabliert eine theoretische untere Schranke für die Lerngeschwindigkeit von Mittelwert-basierten Algorithmen in Bandit-Settings mit unbekanntem Horizont, schlägt zwei neue Algorithmen vor, die bestehende Methoden verallgemeinern, und zeigt auf, dass sie zwar etwas langsamer konvergieren können, aber dennoch eine wettbewerbsfähige Leistung erzielen und mit der Klasse der No-Regret-Algorithmen interferieren können.

Ursprüngliche Autoren: Julius Durmann, Amelie Kleber

Veröffentlicht 2026-06-04

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Julius Durmann, Amelie Kleber

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

Das große Ganze: Der „schlaue Shopper“

Stellen Sie sich vor, Sie sind ein Shopper, der versucht, das beste Café in einer neuen Stadt zu finden. Sie haben eine Liste von 10 Cafés, aber Sie wissen nicht, welches das beste ist. Sie können pro Tag nur ein Café besuchen und den Kaffee dort probieren.

Mean-basierte Algorithmen sind wie ein spezieller Typ von Shopper, der einer sehr einfachen Regel folgt: „Wenn ein Café mir in der Vergangenheit schlechten Kaffee serviert hat, werde ich dort fast nie wieder hingehen.“

Sie führen einen laufenden Durchschnitt darüber, wie gut der Kaffee in jedem Café war. Wenn Café A einen schrecklichen Durchschnitt hat, weist dieser Shopper diesem Café eine sehr geringe Wahrscheinlichkeit für einen Besuch zu. Wenn Café B einen großartigen Durchschnitt hat, besucht er es oft.

Die Arbeit stellt drei Hauptfragen über diesen Typ von Shopper:

Wie schnell kann er lernen?
Gibt es eine Grenze dafür, wie schnell er lernen kann?
Ist er „schlau“ genug, um keine riesigen Fehler zu machen (Regret/Reue)?

1. Das Problem: Der „unbekannte Horizont“ und die „blinden Geschmackstests“

In vielen Informatikproblemen weiß der Algorithmus genau, wie viele Tage er zum Shoppen zur Verfügung hat (der „Zeithorizont“). Aber im echten Leben wissen Sie nicht, ob Sie eine Woche oder ein Jahr in dieser Stadt sein werden. Dies nennt man einen unbekannten Horizont.

Außerdem bekommt der Shopper in diesem speziellen Szenario nur den Geschmack des Kaffees, den er selbst bestellt hat (Bandit-Feedback). Er sieht nicht, wie der Kaffee in den anderen 9 Cafés an diesem Tag geschmeckt hätte. Das macht das Lernen schwieriger, weil er raten muss.

2. Das „Tempolimit“ (Die untere Schranke / Lower Bound)

Die Autoren entdeckten ein grundlegendes Tempolimit für diese Shopper.

Betrachten Sie die „Lernrate“ ( $\gamma_t$ ) als die Geduldsschwelle des Shoppers.

Hohe Geduld (Hohe Schwelle): Der Shopper ist sehr wählerisch. Er hört erst auf, ein Café zu besuchen, wenn der Kaffee wirklich, wirklich schlecht im Vergleich zu den anderen ist. Er hält lange genug Zeit für das Erkunden neuer Cafés frei.
Geringe Geduld (Niedrige Schwelle): Der Shopper ist ungeduldig. Er hört schon auf, ein Café zu besuchen, wenn es nur ein kleines bisschen schlechter ist als das beste Café.

Die Entdeckung: Die Arbeit beweist, dass man nicht zu ungeduldig sein darf.
Wenn der Shopper seine Schwelle zu niedrig ansetzt (um zu schnell lernen zu wollen), wird er das Erkunden zu früh einstellen. Er könnte ein Café aufgeben, das eigentlich gut war, nur weil er zufällig ein paar schlechte Tassen bekommen hat.

Die Autoren fanden eine mathematische „Untergrenze“ für diese Geduld. Es ist wie die Aussage: „Egal wie klug du bist, du kannst nicht schneller aufhören, neue Cafés zu erkunden, als eine bestimmte Geschwindigkeit erlaubt ist, sonst wirst du definitiv einen Fehler machen.“

Die Analogie: Stellen Sie sich vor, Sie versuchen, die beste Route zur Arbeit zu finden. Wenn Sie zu schnell aufhören, neue Routen auszuprobieren, weil eine mal etwas langsamer war, übersehen Sie vielleicht die perfekte Route, die nur an Regentagen auftaucht. Die Arbeit beweist, dass man ein Mindestmaß an „Umherwandern“ benötigt, um sicher zu sein, dass man die beste Option nicht übersieht.

3. Zwei neue „Shopper“ (Die Algorithmen)

Die Autoren entwickelten zwei neue Versionen dieses „mean-basierten“ Shoppers, die auch dann funktionieren, wenn man nicht weiß, wie lange man in der Stadt sein wird und nur den eigenen Kaffee probieren kann.

Der „leicht gierige“ Shopper: Eine Variation der klassischen „Epsilon-Greedy“-Strategie. Er bleibt meistens bei dem besten bekannten Café, probiert aber gelegentlich ein neues aus, um sicherzugehen.
Der „gewichtete“ Shopper: Eine Variation des berühmten „Exp3“-Algorithmus. Er gibt Cafés mit guten vergangenen Durchschnitten mehr Gewicht, behält aber eine kleine Chance bei, auch andere auszuprobieren.

Das Ergebnis: Als sie diese neuen Shopper gegen Standard-Algorithmen testeten, fanden sie heraus, dass die „mean-basierten“ Shopper zwar anfangs etwas langsamer waren, aber schließlich aufholten und genauso gut performten. Sie waren nicht so langsam, wie frühere Studien vermuten ließen.

4. Die „Regret“-Frage: Sind sie ausnutzbar?

In der Wirtschaft gibt es die Befürchtung, dass „mean-basierte“ Shopper ausnutzbar sind.

Das Szenario: Ein gerissener Cafébesitzer (der „Principal“) weiß, dass der Shopper der Regel „schlechter Durchschnitt = nicht besuchen“ folgt. Der Besitzer könnte dem Shopper am ersten Tag einen kostenlosen, fantastischen Kaffee geben, um ihn zu täuschen und ihn glauben zu lassen, dass dieses Café das beste ist. Dann erhöht der Besitzer die Preise oder senkt die Qualität, und der Shopper kommt trotzdem immer wieder, weil sein „Durchschnitt“ immer noch hoch ist.

Die Arbeit untersucht, ob diese Shopper auch unter Regret (Reue/Fehlentscheidungen, die Geld kosten) leiden.

Das Ergebnis: „Mean-basiert“ zu sein, bedeutet nicht automatisch, dass man unter Regret leidet.
Die Wendung: Die Autoren zeigen, dass es möglich ist, einen Shopper zu entwerfen, der sowohl „mean-basiert“ ist (einer einfachen Regel folgt) als auch „no-regret“ (nicht durch Tricks zu Verlusten verführt wird).

Es ist wie die Aussage: „Man kann ein einfacher Shopper sein, der schlechten Kaffee vermeidet, aber wenn man seine Regeln richtig abstimmt, kann man auch klug genug sein, um nicht von einem trickreichen Cafébesitzer reingelegt zu werden.“

Zusammenfassung der Kernaussagen

Die Regel: Mean-basierte Algorithmen sind simpel: „Vermeide Dinge, die im Durchschnitt schlecht waren.“
Das Limit: Es gibt eine harte mathematische Grenze für die Geschwindigkeit, mit der diese Algorithmen lernen können. Wenn sie versuchen, schneller zu lernen als dieses Limit, werden sie scheitern, weil sie zu früh mit dem Erkunden aufhören.
Die Leistung: Die in der Arbeit vorgeschlagenen neuen Algorithmen funktionieren gut. Sie sind konkurrenzfähig mit anderen berühmten Algorithmen, auch wenn sie zu Beginn etwas langsamer sind.
Die Sicherheit: Diese Algorithmen können so gestaltet werden, dass sie „sicher“ sind (no-regret), was bedeutet, dass sie nicht zwangsläufig leicht zu täuschen sind, entgegen dem, was einige frühere Studien suggerierten.

Kurz gesagt: Die Arbeit zeigt uns, dass diese einfachen „Vermeide das Schlechte“-Algorithmen zwar ein Tempolimit haben, aber dennoch leistungsstarke, zuverlässige Werkzeuge zum Lernen in unsicheren Umgebungen sind.

Technisches Resümee: Mittelwertbasierte Algorithmen: Eine untere Schranke und Regret

Problemstellung

Die Arbeit untersucht mittelwertbasierte Algorithmen im Kontext des Online-Learnings, insbesondere im Rahmen des Multi-Armed-Bandit-Problems (MAB) mit Banditen-Feedback und einem unbekannten Zeithorizont.

Mittelwertbasierte Algorithmen werden durch das Prinzip definiert, dass ein Agent zukünftig mit geringer Wahrscheinlichkeit Aktionen wählt, die in der Vergangenheit niedrige durchschnittliche Belohnungen aufwiesen. Während die jüngere Literatur nahelegt, dass diese Algorithmen günstig gegen serielle, nicht-dominierte Aktionen konvergieren (was Nash-Gleichgewichte in ökonomischen Spielen approximiert), deuten empirische Studien darauf hin, dass sie in Szenarien mit Banditen-Feedback eine langsamere Konvergenz aufweisen als etablierte Algorithmen. Zudem besteht ein Spannungsverhältnis zwischen der „Ausbeutbarkeit“ (Exploitability) dieser Algorithmen in Principal-Agent-Spielen und ihren theoretischen Konvergenzgarantien.

Die spezifischen Herausforderungen sind:

Definition von mittelwertbasierten Algorithmen für den Unknown-Horizon-Fall (wo die Gesamtzahl der Runden $T$ im Voraus nicht bekannt ist).
Bestimmung der theoretischen Grenzen für die definierende Ratensequenz $\gamma_t$ der Algorithmen, welche den Schwellenwert zur Vermeidung „dominierter“ Aktionen steuert.
Klärung der Beziehung zwischen mittelwertbasierten Algorithmen und No-External-Regret-Algorithmen, insbesondere ob ein Algorithmus beide Eigenschaften unter Banditen-Feedback gleichzeitig besitzen kann.

Methodik

1. Definitionen und Vorbemerkungen

Die Autoren formalisieren zwei Definitionen von mittelwertbasierten Algorithmen:

$\gamma_t$ -mittelwertbasiert: Basierend auf den aktuellen durchschnittlichen Belohnungen $\alpha_t(a)$ . Wenn $\alpha_t(a') - \alpha_t(a) > \gamma_t$ , ist die Wahrscheinlichkeit, in Schritt $t+1$ die Aktion $a$ zu wählen, höchstens $\gamma_t$ .
Prädiktiv $\gamma_t$ -mittelwertbasiert: Basierend auf den durchschnittlichen Belohnungen des nächsten Schritts $\alpha_{t+1}$ .

Das Paper stellt fest, dass diese Definitionen gegenseitig konvertierbar sind, und konzentriert sich auf die nicht-prädiktive Variante für das Bandit-Setting.

2. Vorgeschlagene Algorithmen

Die Autoren schlagen zwei für Banditen-Feedback und unbekannte Horizonte angepasste Algorithmen vor:

Generalisiertes $\epsilon$ -Greedy: Eine Variante, bei der Aktionen als „dominiert“ gelten, wenn ihre geschätzte kumulative Belohnung signifikant niedriger ist als die anderer Aktionen. Der Algorithmus weist dominierten Aktionen eine kleine Wahrscheinlichkeit $\epsilon_t$ zu und verteilt die verbleibende Wahrscheinlichkeit auf die nicht-dominierten Aktionen.
Mean-Based Exp3: Eine Variante des Exp3-Algorithmus (Exponential-weight algorithm for Exploration and Exploitation). Sie verwendet multiplikative Gewichte basierend auf geschätzten kumulativen Belohnungen, mit einer Explorationskomponente $\epsilon_t$ , um eine ausreichende Stichprobenentnahme zu gewährleisten.

Beide Algorithmen nutzen gewichtete Schätzer (Importance-Weighted Estimators), um den Mangel an vollständigem Feedback zu handhaben.

3. Ableitung der theoretischen unteren Schranke

Um die fundamentale Grenze zu bestimmen, wie schnell diese Algorithmen lernen können, leiten die Autoren eine untere Schranke für die Ratensequenz $\gamma_t$ ab.

Adversarieller Aufbau: Sie konstruieren zwei spezifische adversarielle Umgebungen ( $x'_t$ und $x''_t$ ), die das Exploration-Exploitation-Dilemma ausnutzen. In diesen Umgebungen muss ein Algorithmus zwischen zwei Aktionen unterscheiden, die anfangs ähnlich erscheinen, sich aber später unterscheiden.
Argument der Ununterscheidbarkeit: Aufgrund des Banditen-Feedbacks kann der Algorithmus nicht zwischen den beiden Umgebungen unterscheiden, wenn er eine bestimmte Aktion zu selten spielt (um ein kleines $\gamma_t$ zu erfüllen).
Ableitung der Ungleichung: Durch Analyse der Wahrscheinlichkeit, eine dominierte Aktion in diesen konstruierten Umgebungen zu wählen, leiten sie eine notwendige Ungleichung ab: $\sum_{t=t_1}^{t_c-1} \gamma_t + k \cdot \gamma_{t_c} \geq 1$ .
Asymptotische Analyse: Sie approximieren diese Summe mittels Integralen, um zu zeigen, dass jede Ratensequenz, die schneller als $O(1/\sqrt{t})$ abfällt (speziell jede Sequenz, bei der $\gamma_t \in o(1/\sqrt{t})$ gilt), die Bedingung verletzt, die für einen Algorithmus im Bandit-Setting als mittelwertbasiert erforderlich ist.

4. Regret-Analyse

Die Autoren analysieren die Schnittmenge von mittelwertbasierten Algorithmen und No-External-Regret-Algorithmen. Sie demonstrieren, dass mittelwertbasierte Algorithmen nicht automatisch keine Regret garantieren (und in spezifischen adversariellen Setups mit sehr kleinem $\gamma_t$ linearen Regret erleiden können), es jedoch Konfigurationen gibt (speziell bestimmte Parametrisierungen von Exp3), die sowohl die mittelwertbasierte Eigenschaft als auch die No-External-Regret-Eigenschaft erfüllen.

Zentrale Beiträge

Erste untere Schranke für $\gamma_t$ : Das Paper liefert die erste formale untere Schranke für die Ratensequenz $\gamma_t$ von mittelwertbasierten Algorithmen im Bandit-Feedback-Setting. Es stellt fest, dass $\gamma_t$ nicht schneller als $O(1/\sqrt{t})$ abfallen darf. Speziell jede Sequenz $\gamma_t \in o(1/\sqrt{t})$ ist für mittelwertbasierte Algorithmen in diesem Setting ungültig.
Unknown-Horizon-Algorithmen: Die Autoren schlagen zwei konkrete mittelwertbasierte Algorithmen (generalisiertes $\epsilon$ -greedy und Mean-Based Exp3) vor, die ohne Vorabwissen über den Zeithorizont $T$ effektiv operieren.
Rekonsiliation der Definitionen: Die Arbeit klärt die Beziehung zwischen prädiktiven und nicht-przediktiven mittelwertbasierten Definitionen und zeigt deren Konvertierbarkeit auf.
Regret-Mean-Based Überlappung: Das Paper beweist, dass die Menge der mittelwertbasierten Algorithmen und die Menge der No-External-Regret-Algorithmen nicht disjunkt sind. Es konstruiert eine spezifische Exp3-Variante, die sowohl mittelwertbasiert als auch No-Regret ist.
Empirische Validierung: Durch numerische Experimente zeigen die Autoren, dass mittelwertbasierte Algorithmen zwar etwas langsamer konvergieren können als ihre Standard-Pendants, aber eine kompetitive Performance sowohl in stochastischen MAB-Settings als auch in ökonomischen Spielen (Bertrand-Oligopol) erreichen können.

Ergebnisse

Theoretische Ergebnisse

Untere Schranke: Die Sequenz $\gamma_t = \frac{1}{2\sqrt{t}+1}$ wird als kritischer Schwellenwert identifiziert. Jede Sequenz, die strikt schneller als diese abfällt (z. B. $\gamma_t = 1/t^{0.51}$ oder $\gamma_t = 1/t$ ), wird als ungültig für mittelwertbasierte Algorithmen unter Banditen-Feedback bewiesen.
Regret: Das Paper bestätigt, dass mittelwertbasierte Algorithmen nicht inhärent so „ausbeutbar“ sind, dass dies No-Regret-Garantien ausschließt. Es existieren Algorithmen, die sowohl mittelwertbasiert als auch No-Regret sind.

Empirische Ergebnisse

Stochastischer MAB: In einem 10-Arm-Bandit-Experiment zeigte der vorgeschlagene Mean-Based Exp3 (mit $\alpha=1/2$ ) im Vergleich zu einer Standard-Exp3-Konfiguration eine etwas langsamere Konvergenz zur optimalen Aktion, aber der Unterschied war marginal. Die $\epsilon$ -greedy-Varianten zeigten eine Performance, die von der Explorationsrate abhängt.
Bertrand-Oligopol: In einem wiederholten Preisspiel konvergierte der Mean-Based Exp3-Algorithmus signifikant schneller zum Nash-Gleichgewicht als bisher in ähnlicher Literatur beobachtet (z. B. Bichler et al., 2025). Die Mean-Based $\epsilon$ -greedy Algorithmen waren langsamer, was auf übermäßige Exploration bei hohem Domination-Schwellenwert zurückgeführt wurde.

Bedeutung und Behauptungen

Das Paper behauptet, eine fundamentale Grenze für die Performance mittelwertbasierter Algorithmen geliefert zu haben. Die abgeleitete untere Schranke für $\gamma_t$ erklärt, warum diese Algorithmen oft langsam lernen: Um die mittelwertbasierte Bedingung (Vermeidung dominierter Aktionen) ohne vollständiges Feedback zu erfüllen, muss der Algorithmus ein gewisses Maß an Exploration aufrechterhalten. Wenn die Explorationsrate zu schnell sinkt (d. h. $\gamma_t$ wird zu klein), kann der Algorithmus nicht zwischen Umgebungen unterscheiden und ist gezwungen, dominierte Aktionen zu spielen, was die mittelwertbasierte Definition verletzt.

Die Autoren positionieren ihre Arbeit als notwendigen Schritt, um die Bedenken hinsichtlich der „Ausbeutbarkeit“ in Principal-Agent-Spielen mit den Konvergenzgarantien in der Spieltheorie zu versöhnen. Indem sie zeigen, dass mittelwertbasierte und No-Regret-Eigenschaften koexistieren können, legen sie nahe, dass mittelwertbasierte Algorithmen eine lebensfähige Alternative für ökonomische Lern-Szenarien sind, sofern die Rate $\gamma_t$ sorgfältig gewählt wird, um die abgeleitete untere Schranke zu respektieren.

Das Paper kommt zu dem Schluss, dass mittelwertbasierte Algorithmen zwar nicht universell schneller als Standard-No-Regret-Algorithmen sind, aber eine distinkte Klasse von Lern-Dynamiken bieten können, die besonders in Settings, in denen die Konvergenz zu seriell nicht-dominierten Strategien das primäre Ziel ist, kompetitiv sein können. Die Arbeit lässt die Frage offen, ob ein Algorithmus konstruiert werden kann, der die theoretische untere Schranke $\gamma_t \approx 1/\sqrt{t}$ exakt trifft und gleichzeitig optimalen Regret beibehält.