📊 statistics

Learning to Bid in Repeated Second-Price Auctions with Dynamic Values and Aggregated Feedback

Dieser Beitrag adressiert die Herausforderung des Erlernens von Geboten in wiederholten Zweitpreisauktionen mit dynamischen Werten, die von vergangenen Ergebnissen und aggregiertem Feedback abhängen, und schlägt einen Konfidenzschranken-basierten Algorithmus vor, der für stückweise lineare bzw. allgemeine glatte Primitivfunktionen nahezu optimale Regret-Schranken von $\widetilde{O}(\log N)$ bzw. $\widetilde{O}(N^{1/3})$ erreicht, ohne explizite Randomisierung zu erfordern.

Ursprüngliche Autoren: Benjamin Heymann, Otmane Sakhi

Veröffentlicht 2026-05-28

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Benjamin Heymann, Otmane Sakhi

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 betreiben einen Limonade-Stand auf einem belebten Marktplatz. Alle paar Minuten kommt ein neuer Kunde vorbei, und Sie müssen entscheiden, wie viel Sie für eine Tasse verlangen. Dies ist eine Zweitpreisauktion: Wenn Sie den Verkauf gewinnen, zahlen Sie nicht Ihren Angebotspreis; Sie zahlen den Betrag, den der zweithöchste Bieter zu zahlen bereit war.

Normalerweise würden Sie in der Wirtschaftswissenschaft einfach Ihren „wahren Wert" (den Wert, den die Limonade für Sie hat) verlangen. Doch diese Arbeit führt eine Wendung ein: Ihr Wert ändert sich basierend auf Ihrer jüngsten Vergangenheit.

Das Problem der „Limonaden-Müdigkeit"

In dieser Geschichte wird ein Kunde, dem Sie eine Tasse Limonade verkaufen, für eine Weile „satt" oder „müde" von Limonade. Wenn Sie versuchen, ihm fünf Minuten später eine weitere Tasse zu verkaufen, ist diese für ihn fast nichts wert. Er braucht Zeit, um seinen Durst wiederherzustellen.

Dies nennt die Arbeit dynamische Werte.

Das Dilemma: Wenn Sie jetzt eine Tasse verkaufen, erhalten Sie sofort Geld, aber Sie könnten die Chance zerstören, derselben Kundin später eine wertvollere Tasse zu verkaufen.
Die Falle: Wenn Sie jedes Mal einfach Ihren „wahren Wert" bieten (wie in einer Standardauktion), werden Sie langfristig Geld verlieren, weil Sie zu oft verkaufen und Ihren eigenen Produktpreis entwerten. Sie benötigen eine Strategie, die sagt: „Ich lasse diesen Verkauf aus, um den Kunden für einen besseren Moment später zu schonen."

Die Herausforderung: Sie kennen die Regeln nicht

Das Problem wird schwieriger, weil Sie zwei entscheidende Dinge nicht kennen:

Wie schnell sich Kunden erholen: Sie wissen nicht genau, wie lange es dauert, bis ein Kunde wieder durstig wird (die Arbeit nennt diese Funktion $k$ ).
Wie wettbewerbsfähig der Markt ist: Sie wissen nicht, wie viel andere Limonadenstände zu bieten bereit sind (die Arbeit nennt diese Funktion $q$ ).

Sie müssen diese Regeln lernen, während Sie das Spiel spielen, und dabei versuchen, so viel Geld wie möglich zu verdienen.

Die Lösung: Ein intelligenter, selbstkorrigierender Leitfaden

Die Autoren schlagen einen Weg vor, diese Regeln zu lernen und die perfekte Bietstrategie zu finden, ohne eine Glaskugel zu benötigen. Sie verwenden eine Mischung aus Raten und mathematischer Planung.

Stellen Sie sich ihre Methode wie ein GPS für Ihren Limonadenstand vor:

Die Karte (Der Löser): Sie verwenden eine komplexe mathematische Formel (eine Differentialgleichung), die wie eine Karte funktioniert. Sie sagt Ihnen das perfekte Gebot, wenn Sie alle Regeln wüssten.
Der Kompass (Die Schätzer): Da Sie die Regeln nicht kennen, nutzen Sie Ihre vergangenen Verkaufsdaten, um eine grobe Karte zu erstellen.
- Sie schauen sich an, wie viel Geld Sie nach verschiedenen Zeitabständen verdient haben, um zu erraten, wie schnell sich Kunden erholen.
- Sie schauen sich die Preise an, die Sie gezahlt haben, als Sie gewonnen haben, um zu erraten, wie wettbewerbsfähig die anderen Stände sind.
Die Feedback-Schleife: Sie stecken Ihre „grobe Karte" in den Rechner für die „perfekte Strategie". Dies liefert Ihnen einen neuen Bietplan. Sie probieren ihn aus, sammeln weitere Daten, aktualisieren Ihre Karte und versuchen es erneut.

Die vier getesteten Strategien

Die Arbeit testet vier verschiedene Wege, dieses Lernen durchzuführen:

Der Ansatz „Einfach weitermachen": Sie aktualisieren einfach ständig Ihre Karte und bieten basierend darauf. Die Arbeit beweist, dass Sie, wenn Sie dies lange genug tun, schließlich die perfekte Strategie herausfinden, selbst ohne zufälliges „Erkunden". Es ist wie das Gehen durch einen Flur; irgendwann stoßen Sie auf die richtige Tür.
Der Ansatz „Erkunden, dann festlegen": Sie verbringen etwas Zeit damit, sehr hoch zu bieten (nur um die Regeln schnell zu lernen), und wechseln dann für den Rest des Tages zu Ihrem besten Schätzwert. Dies ist schnell und effizient.
Der Ansatz „Konfidenzgrenze" (Der Gewinner): Dies ist die ausgefeilteste Methode. Sie erstellt eine „Sicherheitszone" um Ihre Schätzungen herum.
- Wenn Sie sich bei den Regeln nicht sicher sind, verhält sie sich etwas aggressiver, um mehr zu lernen.
- Wenn Sie Zuversicht haben, verhält sie sich konservativ, um Ihre Gewinne zu schützen.
- Das Ergebnis: Diese Methode lernt die optimale Strategie unglaublich schnell. Die Arbeit beweist, dass sie im Vergleich zur perfekten Strategie sehr wenige Fehler macht, die nur logarithmisch (sehr langsam) mit der Zeit wachsen. Dies erreicht sie ohne zufälliges Pfeilwerfen (Randomisierung), um zu lernen, was in diesem Bereich eine große Leistung ist.

Warum dies wichtig ist

Die Arbeit zeigt, dass Sie selbst dann, wenn Ihr Wert sich basierend auf Ihren vergangenen Handlungen ändert (wie bei Ad-Fatigue im digitalen Marketing), immer noch lernen können, perfekt zu bieten.

Die große Erkenntnis: Sie müssen die Zukunft oder den Wettbewerb nicht perfekt kennen. Durch die intelligente Kombination aus Schätzen der Regeln aus Daten und Lösen einer Planungs-Gleichung können Sie lernen, so zu bieten, dass Ihr langfristiger Gewinn maximiert wird, selbst in einer komplexen, sich verändernden Umgebung.

Kurz gesagt: Bieten Sie nicht einfach nur mit dem Herzen. Bieten Sie intelligent, lernen Sie aus Ihren Gewinnen und Verlusten und lassen Sie die Mathematik Ihnen sagen, wann Sie aufhören und auf die nächste Gelegenheit warten sollten.

Technische Zusammenfassung: Lernen von Geboten in wiederholten Zweitpreisauktionen mit dynamischen Werten und aggregiertem Feedback

1. Problemformulierung

Diese Arbeit behandelt das Problem des Lernens optimaler Bietstrategien in wiederholten Zweitpreisauktionen, bei denen der Wert des Bieters dynamisch ist. Im Gegensatz zu statischen Modellen, bei denen die Bewertung eines Bieters unabhängig von früheren Aktionen ist, hängt hier der Wert eines Auktionserfolgs von der seit dem letzten erfolgreichen Gewinn verstrichenen Zeit ab. Spezifisch ist die Wertfunktion $k(\tau)$ eine konkave, steigende Funktion der Zeit $\tau$ seit dem letzten Gewinn, was Phänomene wie die Ad-Fatigue von Nutzern in der digitalen Werbung widerspiegelt.

Das Setting umfasst:

Kontinuierliche Zeit: Auktionen treffen gemäß einem Poisson-Prozess mit Intensität $\mu$ ein.
Dynamische Werte: Die Belohnung für einen Gewinn zum Zeitpunkt $t$ beträgt $k(t - T_{last})$ , wobei $T_{last}$ der Zeitpunkt des vorherigen Gewinns ist.
Stationärer Wettbewerb: Die Gebote der Konkurrenten (Preis, der übertroffen werden muss) werden i.i.d. aus einer unbekannten, stetigen Verteilungsfunktion (CDF) $q$ gezogen.
Aggregiertes Feedback: Der Bieter beobachtet die Ergebnisse einzelner Auktionen oder Preise nicht unmittelbar. Stattdessen wird das Feedback erst am Ende einer „Episode" (eine Sequenz von Auktionen, die zu einem zufälligen Zeitpunkt endet, der aus einer Exponentialverteilung mit Rate $\gamma$ gezogen wird) offengelegt. Das Feedback besteht aus dem gesamten Wert, der von der Episode generiert wurde.
Lernziel: Der Bieter muss die unbekannten Primitiven $k$ (Wertdynamik) und $q$ (Wettbewerbsverteilung) erlernen, um die kumulierte erwartete Auszahlung über $N$ Episoden zu maximieren und das Regret zu minimieren, definiert als $Regret(N) = \sum_{l=1}^N (V_{\pi^*}(0) - V_{\pi_l}(0))$ .

2. Methodik und Theoretischer Rahmen

2.1 Charakterisierung der optimalen Steuerung

Aufbauend auf der Formulierung der dynamischen Programmierung in kontinuierlicher Zeit aus [6] charakterisieren die Autoren die optimale Politik $\pi^*$ über die Bellman-Wertfunktion $V^*(\tau)$ . Das optimale Gebot erfüllt eine Differentialgleichung, die aus dem Bellman-Wert abgeleitet ist:
$\dot{\pi}(t) = \dot{k}(t) - \gamma(V^*(0) + k(t)) + \mu f(\pi(t)) + \gamma \pi(t)$
wobei $f(v) = q(v)v - p(v)$ und $p(v)$ der erwartete gezahlte Preis ist. Die Lösung erfordert die Bestimmung einer spezifischen Anfangsbedingung $V^*(0)$ , sodass die resultierende Trajektorie beschränkt bleibt; ein Problem, das mittels eines Bisektionsverfahrens (der „Solver" $S$ ) gelöst wird.

2.2 Lernen der Primitiven durch Plug-in-Schätzer

Da $k$ und $q$ unbekannt sind, schlagen die Autoren vor, sie aus Daten zu lernen und die Schätzwerte in den Solver $S$ einzuspeisen.

Schätzung von $k$ : Modelliert als stückweise lineare, konkave, steigende Funktion. Die Schätzung erfolgt mittels projizierter gewöhnlicher Kleinstquadrate (OLS) auf aggregierten Episodendaten, wobei der unbeschränkte Schätzer auf die konvexe Menge der konkaven Funktionen projiziert wird.
Schätzung von $q$ : Modelliert als stückweise lineare, steigende CDF. Die Schätzung verwendet die Maximum-Likelihood-Schätzung (MLE) auf Gewinn/Verlust-Ergebnisse und beobachtete Preise (wenn Gewinne eintreten).

2.2 Extension-Invarianz-Theorem

Ein wesentlicher theoretischer Beitrag ist das Extension-Invarianz-Theorem (Theorem 4.1). Es stellt fest, dass zur Identifizierung der optimalen Politik nicht die gesamte Verteilung $q$ gelernt werden muss. Es reicht aus, $q$ nur bis zum maximalen optimalen Gebot $\beta(\pi^*)$ genau zu schätzen. Diese Erkenntnis entkoppelt die Notwendigkeit einer vollständigen Exploration des Gebotsraums von der Anforderung, die optimale Politik zu lernen, sofern der Lernalgorithmus sicherstellt, dass Gebote den relevanten Bereich abdecken.

3. Algorithmen und Regret-Schranken

Der Artikel analysiert vier Algorithmen, die auf Plug-in-Schätzern basieren:

Asymptotische Konvergenz (Iterativer Plug-in): Ein iterativer Ansatz, bei dem Daten gesammelt, Schätzer aktualisiert und die Politik neu berechnet werden. Theorem 5.1 beweist, dass, wenn die Politiksequenz einen Bereich erkundet, in dem $q$ identifizierbar ist (d. h. $\limsup \beta(\pi_n) > 0$ ), die Politik asymptotisch gegen die optimale konvergiert. Dies garantiert jedoch keine Regret-Schranken für endliche Zeit.
Zwei-Phasen- und Drei-Phasen-Algorithmen: Diese folgen einer „Explore-Then-Commit"-Struktur.
- Zwei-Phasen: Eine feste explorative Politik (Bieten des maximalen Werts) läuft für $N_1$ Episoden, um sowohl $k$ als auch $q$ zu lernen, gefolgt von der Ausbeutung.
- Drei-Phasen: Trennt das Lernen von $k$ und $q$ . Zuerst lernt eine feste Politik $k$ ; dann leitet die gelernte $k$ eine Politik zum Lernen von $q$ ; schließlich erfolgt die Ausbeutung.
- Ergebnis: Beide erreichen ein sublineares Regret von $O(\sqrt{N})$ (Theoreme 5.4 und 5.5).
Konfidenzschranken-Algorithmus (Online-Lernen): Ein Online-Algorithmus, inspiriert von Upper-Confidence-Bound (UCB)-Prinzipien.
- Er konstruiert optimistische Schätzungen für $k$ (UCB) und pessimistische Schätzungen für $q$ (Lower Confidence Bound, LCB), um Exploration und Ausbeutung auszugleichen.
- Entscheidend ist, dass er ein nahezu logarithmisches Regret $\tilde{O}(\log N)$ für stückweise lineare Primitiven erreicht (Theorem 5.7), ohne explizite Randomisierung zu benötigen, die typischerweise bei Erstpreisauktionen erforderlich ist.
- Der Algorithmus erweist sich als nahezu minimax-optimal, da eine untere Schranke von $\Omega(\log N)$ hergeleitet wird (Theorem 5.8), was die Komplexität des statischen Falls trotz des dynamischen Settings widerspiegelt.
Allgemeine glatte Primitiven: Die Ergebnisse werden auf allgemeine glatte Primitiven (stetig differenzierbar mit Lipschitz-stetigen Ableitungen) erweitert, indem sie durch stückweise lineare Funktionen approximiert werden. Dies ergibt eine Regret-Schranke von $\tilde{O}(N^{1/3})$ (Theorem 5.10).

4. Hauptbeiträge

Erste Regret-Analyse für dynamische Werte: Dies ist die erste Arbeit, die Regret-Schranken für das Lernen von Geboten in wiederholten Zweitpreisauktionen bereitstellt, bei denen die Werte von der Zeit seit dem letzten Gewinn abhängen, ein Setting, das sich von Standardmodellen mit statischen Werten oder Budgetbeschränkungen unterscheidet.
Extension-Invarianz: Der Beweis, dass eine genaue Schätzung der Wettbewerbsverteilung nur bis zur Schwelle des optimalen Gebots erforderlich ist, was die Lernanforderung vereinfacht.
Optimale Regret-Raten: Der Nachweis, dass ein nahezu logarithmisches Regret in diesem komplexen, dynamischen Setting ohne explizite Randomisierung erreichbar ist und die theoretische untere Schranke des statischen Falls erreicht.
Integration von Steuerung und Lernen: Die Arbeit verbindet kontinuierliche Zeit-Optimalsteuerung (via ODE-Charakterisierung der optimalen Politik) und modellbasiertes Reinforcement Learning (via Plug-in-Schätzung) und bietet einen Rahmen für Probleme mit Zustands-Resets.

5. Bedeutung und Behauptungen

Die Autoren behaupten, dass diese Studie einen theoretisch fundierten Ansatz für das Auto-Bidding in Umgebungen mit dynamischen Werten bietet, wie z. B. in der digitalen Werbung, wo Ad-Fatigue weit verbreitet ist. Die Bedeutung liegt in:

Praktische Relevanz: Sie adressiert das „Planungsproblem", bei dem unmittelbare Gewinne gegen eine zukünftige Wertdegradation abgewogen werden müssen, eine Herausforderung, die einfache Feature-Engineering-Methoden oder überwachtes Lernen nicht optimal lösen können.
Theoretische Einsicht: Sie zeigt, dass das Problem selbst bei aggregiertem Feedback und dynamischen Werten in Bezug auf Regret-Raten (logarithmisch vs. Quadratwurzel) nicht unlösbar schwieriger wird als im statischen Fall, sofern die richtigen Schätz- und Steuerungswerkzeuge eingesetzt werden.
Breitere Auswirkungen: Der Rahmen bietet Einsichten für die breitere Literatur zum Reinforcement Learning, insbesondere für Steuerungsprobleme in kontinuierlicher Zeit, die Resets und nichtlineare Belohnungen beinhalten.

Der Artikel schließt damit, dass die Analyse zwar theoretisch ist, die Kombination aus Plug-in-Schätzung mit lösungsbasierten Differentialgleichungen jedoch einen gangbaren Weg für praktische Anwendungen in realen Auktionssystemen nahelegt. Numerische Experimente stützen die theoretischen Befunde und zeigen, dass der Konfidenzschranken-Algorithmus in Bezug auf das Regret-Wachstum Explore-Then-Commit-Strategien übertrifft.