Online Bidding for Contextual First-Price Auctions with Budgets under One-Sided Information Feedback

Dit artikel introduceert een nieuw biedalgoritme voor contextuele eerste-prijsveilingen met budgetbeperkingen en eenzijdige feedback, dat gebruikmaakt van een robuuste regressiemethode op basis van kwantielinvariantie om een optimale regret van $\widetilde{O}(\sqrt{T})$ te bereiken.

De kern

Stel je voor dat je een veilingmeester bent, maar dan in de digitale wereld van online reclame. Elke seconde wordt er een advertentieruimte (een "impression") verkocht aan de hoogste bieder. Dit is een eerste-prijsveiling: wie het hoogste bod uitbrengt, wint en betaalt precies dat bedrag.

Jouw doel is om zoveel mogelijk winst te maken door slim te bieden, maar je hebt een strakke portemonnee (een budget). Als je je geld opmaakt, moet je stoppen.

Het probleem? Je ziet niet alles. Je weet niet wat je concurrenten bieden, en je ziet pas of je gewonnen hebt als je wint. Als je verliest, hoor je alleen: "Je hebt te weinig geboden," maar je weet niet hoeveel ze precies boden. Dit noemen de auteurs "éénzijdige feedback" (je ziet alleen de winnaars, niet de verliezers).

Bovendien is de markt niet statisch. De prijs die concurrenten bieden, hangt af van de context: wie is de kijker? Is het een rijke man of een student? Is het ochtend of avond? Dit is de "context" ($x_t$).

De Uitdaging: Gissen in het Donker

In het verleden dachten onderzoekers dat concurrenten altijd hetzelfde bod deden, ongeacht de situatie. Maar in de echte wereld is dat niet zo. Als de kijker waardevol is, bieden concurrenten meer. Jij moet dit patroon leren terwijl je tegelijkertijd je budget beheert.

Als je te voorzichtig biedt, mis je kansen. Als je te roekeloos biedt, ben je je budget snel kwijt. En als je de concurrenten niet begrijpt, kun je niet slim bieden.

De Oplossing: Een Slimme "Gokker" met een Magische Liniaal

De auteurs van dit paper hebben een nieuw algoritme bedacht (een computerprogramma) dat dit probleem oplost. Ze gebruiken twee slimme trucs:

1. De "Magische Liniaal" (Robuuste Regressie)
Stel je voor dat je probeert de hoogte van een muur te meten, maar je mag alleen meten als je er onder de muur staat. Als je erboven staat, zie je alleen de top, maar niet hoe hoog hij precies is.
Normale meetmethoden falen hier. De auteurs gebruiken een slimme statistische truc gebaseerd op kwantielen (een soort "gemiddelde positie" in een rij).

• De analogie: Stel je hebt een rij mensen van verschillende lengtes. Je kunt alleen de lengte zien van de mensen die korter zijn dan jij. Als je je positie in de rij verandert (door je bod te veranderen), zie je een andere groep mensen.
• Door te kijken naar de verdeling van de mensen die je wel ziet, en te vergelijken met groepen die je op een andere manier ziet, kan het algoritme de "muur" (de concurrenten) reconstrueren zonder de volledige lijst te hoeven zien. Ze noemen dit kwantiel-invariantie. Het is alsof je een puzzel oplost door alleen de randstukken te bekijken, maar slim genoeg bent om te weten hoe het midden eruit moet zien.

2. De "Portemonnee-Regelaar" (Dual Update)
Je hebt een budget. Het algoritme gebruikt een virtuele "prijs" voor je geld (een Lagrange-multiplicator).

• De analogie: Stel je hebt een reisbudget. Als je merkt dat je te snel geld uitgeeft, wordt de "prijs" van elke euro die je uitgeeft, in je hoofd hoger. Hierdoor word je automatisch zuiniger. Als je geld overschiet, wordt de prijs lager en durf je meer te riskeren.
• Het algoritme past deze "prijs" continu aan op basis van hoe snel je je budget verbruikt, zodat je precies op het einde van de tijd je geld opmaakt, zonder te vroeg te stoppen.

Hoe werkt het in de praktijk?

Het algoritme werkt in fases:

1. Onderzoeken: In het begin biedt het programma bewust laag (of 0) om te kijken wat er gebeurt. Het leert de "muur" van de concurrenten kennen.
2. Leren en Toepassen: Het verdeelt de tijd in blokken. In sommige blokken leert het de concurrenten beter kennen (met de magische liniaal). In andere blokken past het de strategie toe en probeert het winst te maken.
3. Filteren: Het houdt een lijstje van "goede biedingen" bij. Als een bod duidelijk te slecht is, gooit het dat weg. Als een bod te goed is om waar te zijn, houdt het dat ook in de gaten.

Het Resultaat

De auteurs bewijzen wiskundig dat hun algoritme optimaal presteert.

• Regret (Spijt): In de wereld van algoritmes is "regret" het verschil tussen wat je had kunnen verdienen als je alles perfect wist, en wat je echt verdiend hebt.
• Hun algoritme zorgt dat deze spijt zo klein mogelijk blijft: het groeit alleen met de wortel van de tijd ($\sqrt{T}$). Dit betekent dat naarmate je langer speelt, je gemiddelde prestatie steeds dichter bij de perfecte prestatie komt.

Waarom is dit belangrijk?

Vroeger waren de modellen te simpel (ze dachten dat alles statisch was). Dit paper is de eerste die drie moeilijke dingen tegelijk oplost:

1. Context: Concurrenten reageren op de situatie.
2. Budget: Je hebt een limiet aan geld.
3. Onvolledige informatie: Je ziet niet alles wat er gebeurt.

Dit is een enorme stap voor online adverteerders, maar ook voor andere markten zoals cloud-opslag of zelfs de elektriciteitsmarkt, waar bedrijven ook moeten bieden met een budget en onvolledige informatie.

Kort samengevat:
Het is alsof je een blinddoek op hebt tijdens een veiling, maar je hebt een slimme bril die je helpt de andere bieders te raden door te kijken naar wie er wint en wie er verliest, terwijl je tegelijkertijd je portemonnee in de gaten houdt zodat je niet failliet gaat. En het werkt verrassend goed!

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Online Bidding for Contextual First-Price Auctions with Budgets under One-Sided Information Feedback", geschreven in het Nederlands.

1. Probleemstelling

Het paper onderzoekt het probleem van het leren van biedstrategieën in herhaalde eerste-prijsveilingen (first-price auctions) onder begrotingsbeperkingen. De context is die van digitale advertentiemarkten, waar de markt is verschoven van tweede-prijsveilingen (waar waarheidsgetrouwe biedingen de dominante strategie zijn) naar eerste-prijsveilingen.

Kernkenmerken van het probleem:

• Eerste-prijsveiling: De hoogste bieder wint en betaalt zijn eigen bieding. Bieders moeten strategisch "schaduwen" (bieden onder hun private waarde) om winst te maken.
• Begrotingsbeperking: De bieder heeft een totale begroting $B$ over een tijdsinterval $T$. De som van de winnende biedingen mag deze begroting niet overschrijden.
• Contextuele Competitie: De hoogste bieding van concurrenten ($d_t$) is niet statisch, maar hangt af van de context van de impressie ($x_t$). Het model is lineair: $d_t = \alpha x_t + z_t$, waarbij $\alpha$ onbekend is en $z_t$ ruis is uit een onbekende verdeling $G$.
• Eenzijdige Informatie (One-Sided Feedback): Dit is de grootste uitdaging. De bieder observeert de concurrentenbieding $d_t$ alleen als hij verliest ($b_t < d_t$). Als hij wint, weet hij alleen dat $d_t < b_t$, maar niet de exacte waarde. Dit creëert een gecensureerd dataset-probleem.

Het doel is om een strategie $\pi$ te vinden die de totale verwachte beloning maximaliseert, onderworpen aan de begrotingsbeperking, terwijl de onbekende parameters ($\alpha$ en $G$) worden geleerd. De prestatie wordt gemeten aan de hand van regret (het verschil tussen de optimale strategie en de gekozen strategie).

2. Methodologie

De auteurs ontwikkelen een nieuw algoritme dat drie complexe aspecten combineert: schatting van parameters onder censuur, budgetbeheer en contextueel leren.

A. Robuuste Regressie via Kwantiel-Invariantie (Schatting van $\alpha$)

Omdat concurrentenbiedingen alleen worden waargenomen bij verlies, kunnen traditionele methoden (zoals Kwantiel Kleinste Kwadraten) niet worden gebruikt. De auteurs introduceren een kwantielgebaseerde schatter (Algoritme 1):

• Principe: Ze benutten het feit dat bepaalde conditionele kwantielen van de residuen identificeerbaar blijven, zelfs onder censuur.
• Methode: De steekproef wordt opgesplitst in twee groepen op basis van de mediaan van de context $x_t$. Voor een kandidaat-parameter $\alpha$ worden de residuen berekend. Censuurpunten (waarbij de bieding te hoog was) worden behandeld als $-\infty$ en hebben geen invloed op de kwantielberekening.
• Doel: De parameter $\hat{\alpha}$ wordt gevonden door de absolute verschil tussen de $p$-kwantielen van de twee groepen te minimaliseren.
• Resultaat: Ze bewijzen dat deze schatter een foutmarge heeft van $\tilde{O}(1/\sqrt{n})$, wat optimaal is.

B. Dual Update en Lagrangiaans Dualiteit (Budgetbeheer)

Om de begrotingsbeperking aan te pakken, gebruiken ze een Lagrangiaans dualiteitsbenadering:

• Het oorspronkelijke geconstrueerde probleem wordt omgezet in een dual probleem met een Lagrange-multiplicator $\lambda$.
• $\lambda$ fungeert als een "prijs" voor het verbruik van de begroting.
• De multiplicator wordt bijgewerkt via Online Gradient Descent op basis van het verschil tussen het gemiddelde budgetverbruik en de toegestane limiet.

C. Het Biedalgoritme (Algoritme 2)

Het totale algoritme werkt in fasen:

1. Exploratie: Een initiële fase ($2\sqrt{T}$rondes) waarbij er niet wordt geboden om data te verzamelen voor een eerste schatting van$\alpha$.
2. Fase-gebaseerd Leren: De resterende tijd wordt opgedeeld in paren van fasen ($A_i, B_i$).
   • In fase $A_i$ wordt $\alpha$ opnieuw geschat met de robuuste kwantielmethode.
   • In fase $B_i$ worden de verwachte beloning en kosten geschat op basis van de huidige schatting van $\alpha$.
3. Actieve Set Mechanisme: Het algoritme selecteert de kleinste bieding uit een "actieve set" die voldoet aan de geschatte optimale strategie. Dit minimaliseert de kosten terwijl de kans op winnen behouden blijft.
4. Stopconditie: Het proces stopt zodra de resterende begroting te laag is om nog te bieden.

3. Belangrijkste Bijdragen

1. Nieuw Probleemformulering: Dit is het eerste werk dat simultaan begrotingsbeperkingen, contextuele concurrentie (waarbij de tegenstander afhangt van de context) en eenzijdige feedback behandelt. Eerdere werken verwaarloosden meestal een van deze aspecten.
2. Verwijdering van Distributie-aannames: In tegenstelling tot eerdere studies die aannamen dat de ruisverdeling $G$ bekend is, werken de auteurs in een setting waar zowel de lineaire parameter $\alpha$ als de ruisverdeling $G$ volledig onbekend zijn.
3. Novel Estimation Technique: De introductie van de robuste regressie op basis van conditionele kwantiel-invariantie. Deze methode overwint het probleem van bid-afhankelijke censuur en is op zich waardevol voor andere statistische leerproblemen.
4. Optimale Regret Bound: Ze bewijzen dat hun algoritme een regret van $\tilde{O}(\sqrt{T})$ bereikt. Dit is orde-optimaal (order-optimal), wat betekent dat het de beste mogelijke snelheid van convergentie haalt, rekening houdend met de logaritmische factoren.

4. Resultaten

• Theoretische Garantie: Onder redelijke aannames (Lipschitz-continuïteit van de verdeling, begrensdheid van waarden, identificeerbaarheid van parameters) wordt bewezen dat de regret begrensd is door $O(\sqrt{T} \ln T)$.
• Meerdimensionale Uitbreiding: Het paper breidt de methode uit naar een meerdimensionale context ($\alpha \in \mathbb{R}^d$). Het algoritme schat elke dimensie onafhankelijk en bereikt een regret van $\tilde{O}(\sqrt{dT})$.
• Numerieke Experimenten: Simulaties met $T=5000$ en verschillende ruisverdelingen (Normaal, Log-Normaal, Uniform) tonen aan dat het voorgestelde algoritme (met context) significant beter presteert dan een niet-contextueel algoritme (gebaseerd op eerdere werken), vooral wat betreft het minimaliseren van regret.

5. Betekenis en Impact

Deze paper is van groot belang voor de theorie van online leren en veilingtheorie, met name voor de digitale advertentie-industrie:

• Praktische Relevantie: De verschuiving naar eerste-prijsveilingen in de ad-tech sector maakt dit onderzoek direct toepasbaar. De "eenzijdige feedback" is een realiteit in moderne platforms (zoals Google Ad Manager), waar winnaars vaak meer informatie krijgen dan verliezers.
• Robuustheid: De methode is robuust tegen onbekende ruisverdelingen, wat cruciaal is in dynamische markten waar het gedrag van concurrenten niet statisch is.
• Methodologische Vooruitgang: De combinatie van kwantiel-regressie voor censuurproblemen met dual-gradient methoden voor budgetbeheer opent nieuwe wegen voor onderzoek in constrained online learning. Het biedt een blauwdruk voor hoe agents kunnen leren in complexe, gedeeltelijk waarneembare omgevingen met strikte beperkingen.

Kortom, het paper levert een wiskundig onderbouwde en praktisch bruikbare oplossing voor een van de meest uitdagende problemen in moderne online veilingen: hoe effectief te bieden met een beperkt budget wanneer je maar beperkte informatie hebt over je concurrenten en hun biedingen afhankelijk zijn van de context.