Adaptive Bid Shading Optimization of First-Price Ad Inventory

https://www.researchgate.net/profile/Niklas-Karlsson-11/publication/352523808_Adaptive_Bid_Shading_Optimization_of_First-Price_Ad_Inventory/links/611195c3169a1a0103ec2b37/Adaptive-Bid-Shading-Optimization-of-First-Price-Ad-Inventory.pdf

Wykorzystanie feedback controllera do bid-shadingu przy założeniu, że nie znamy ceny, która wygrała.

Cały system podzielony jest na 3 niezależne podsystemy:

1. estymujący wartość bid requesta $v_i$, czyli wartość oczekiwaną przychodu,
2. system maksymalizujący total value przy ograniczeniu na budżet kampanii
3. bid-shading, będący systemem maksymalizującym surplus

Ad. 1.

Projektowanie tego systemu jest poza zakresem publikacji.

Ad. 2.

Zakładamy, że mamy biddera, który ma za zadanie zmaksymalizować value (value maximizer) z pojedynczym ograniczeniem na koszt (budżet). Pomysł taki sam jak w Feedback Control in Programmatic Advertising The Frontier of Optimization in Real-Time Bidding, czyli wykorzystanie mnożników Lagrange’a - rozwiązanie daje nam pojedynczy control signal $u_0=\frac{1}{\lambda }$, który jest ustalany przez mechanizm feedback controllera. Wartość bid requesta $v_i$ mnożymy przez $u_0$ dostając adjusted value $b_i^u=u_0{v}_i$.

Ten sam problem poruszany w Optimization in Online Advertising via Simultaneous Adaptive Rate and Price Feedback Control

Ad. 3.

Wartość, która jest optymalizowana w bid-shadingu to surplus. Rozważamy aukcję typu first-price. Założenie w publikacji jest takie, że nie znamy rozkładu prawdopodobieństwa nad ceną, która wygra aukcję.

Uwaga: mimo, że autorzy posługują się wszędzie pojęciem adjusted value oznaczanym $b_i^u$, to dla prostoty poniżej zamieniam to po prostu na value, $v_i$, bo nie ma to znaczenia dla zrozumienia sposobu na bid-shading.

Najpierw autorzy zakładają relację między $v_i$ a biddem $b_i$, w postaci konkretnej funkcji sterowanej przez dwa parametry $u_1$, $u_2$ (równanie (9)). Ta funkcja jest wklęsła, monotoniczna i zapewniająca że $b_i\le v_i$.

Następnie podają metodę na znalezienie takich $u_1$ i $u_2$, które optymalizują surplus $s_i$, czyli $(v_i-b_i)\cdot \mathbb{P}[win|b_i]$. Ale pomijają modelowanie $\mathbb{P}[win|b_i]$ bo optymalizują surplus na historycznych realizacjach, tzn. prawdziwych wartościach $v_i$, $b_i$ (faktycznie poniesionym koszcie) zakładając, że gdy przegraliśmy to $v_i=b_i=\text{surplus}=0$.

Estimator: Obserwujemy płynące z produkcji kolejne wartości $u_1,u_2,s$ w pewnych przedziałach czasowych, np. 5 minutowych. $s$ to średni surplus przez cały okres trwania (nie w pojedynczym przedziale). W pierwszych 5 minutach były wartości $u_1^t,u_2^t,s^t$. W kolejnych 5 minutach były wartości $u_1^{t+1},u_2^{t+1},s^{t+1}$, itd. Na serii obserwacji tego typu trenujemy model postaci $s=e^{\phi \theta }$ gdzie $\phi =[1,u_1,u_2,u_1^2,u_2^2,u_1{u}_2]$ a $\theta$ to wektor 6 parametrów (wag). Przy czym im starsze obserwacje tym mają mniejszą wagę. Wzór optymalizacyjny zawarty w (11). Do znalezienia wag używany jest model Recursive Least Squares algorithm, który minimalizuje błąd średniokwadratowy, ale w sposób online i w dodatku tak, że im starsza obserwacja tym ma mniejszą wagę.

Optimizer: W tym kroku bierzemy wyestymowane $\theta$ i używamy go do zmiany obecnych $u_1,u_2$ w takim kierunku, który maksymalizuje surplus. Kierunek w jakim zmienić $u_1,u_2$ można sobie wyliczyć na podstawie gradientu funkcji $s=e^{\phi \theta }$. O ile zmienić $u_1,u_2$ jest ustawiane ręcznie.

W dodatku po każdym updatecie do $u_1,u_2$ dodają jakiś losową wartość, żeby zachować excitation, czyli eksplorację.

W Bid shading by win-rate estimation and surplus maximization wytykają problemy z zaproponowanym tutaj rozwiązaniem: zrobienie dobrych segmentów jest trudne, informacje nie są wymieniane między segmentami, liczba segmentów szybko może eksplodować.

---

Praca wspomniana w A Survey on Bid Optimization in Real-Time Bidding Display Advertising.