Abstract
The shift from second-price to first-price auctions in digital advertising introduces a strategic challenge: bid shading. Bidders must balance winning auctions against maximizing surplus under censored feedback. This paper investigates the stochastic setting where opponent bids follow a stationary distribution. We propose two algorithms, UCBid1 and UCBid1+, which leverage local quadratic properties of the utility function and novel concentration inequalities to achieve "fast" learning rates—specifically $O(\log^2 T)$ and $O(T^{1/3})$ regret—significantly outperforming the standard $O(\sqrt{T})$ rates of adversarial models.
Introduction
In programmatic advertising, the industry-wide transition from second-price (Vickrey) auctions to first-price auctions has fundamentally altered bidding strategies. In a second-price auction, truth-telling is a dominant strategy. In a first-price auction, however, bidding one's true value results in zero utility. Bidders must "shade" their bids—submitting a value lower than their true valuation—to capture surplus. This task is complicated by "censored feedback": a bidder only observes the item's value if they win, and they only observe the maximum competing bid if it is lower than their own.
The Bidding Problem as a Bandit Task
First-price bidding can be framed as a continuously-armed bandit problem. The learner faces a trade-off: bidding high increases the probability of winning and gathering data but reduces immediate profit, while bidding low maximizes profit per win but reduces the win rate. Previous literature often focused on adversarial settings where opponents adapt, leading to a standard $O(\sqrt{T})$ regret bound. This work focuses on the stochastic setting, where the maximum competing bid $M$ follows an unknown but stationary distribution $F$.
Proposed Algorithms: UCBid1 and UCBid1+
The authors introduce two algorithms based on the Upper Confidence Bound (UCB) framework:
- UCBid1: Applicable when the distribution $F$ is known but the item's value $v$ is unknown. It maintains an optimistic estimate of $v$ to determine the shaded bid.
- UCBid1+: A more practical variant where both $v$ and $F$ are unknown. It utilizes the empirical distribution of observed maximum bids to estimate $F$ and an optimistic estimate for $v$.
A key observation for UCBid1+ is that the learner observes the maximum competing bid $M$ in every round, regardless of whether they win or lose. This allows for a more direct estimation of the distribution $F$ without needing optimism over the distribution itself.
Theoretical Innovations: Breaking the $\sqrt{T}$ Barrier
The core contribution of this research lies in identifying conditions that allow for faster convergence.
The authors identify that if the bid distribution $F$ is "well-behaved" (e.g., log-concave), the utility function $U_{v,F}(b) = (v - b)F(b)$ exhibits Local Quadratic Utility near its maximum. This smoothness allows the learner to zoom in on the optimal bid more efficiently than in general non-parametric settings. Furthermore, they developed a Local Concentration Inequality that provides tighter bounds on the error of the estimated distribution $F$ specifically around the optimal bid, rather than globally.
Empirical Evaluation
The algorithms were tested on both synthetic and real-world data:
- Simulated Environments: Using Beta distributions to simulate various competitive landscapes, the algorithms consistently achieved the predicted fast rates.
- Real-World Data: Using a dataset of 56,607 bids from the agency Numberly, UCBid1+ demonstrated superior performance, reducing regret by up to five times compared to standard black-box optimizers like HOO or stoSOO.
Conclusion and Future Work
By exploiting the stochastic nature of bidding environments and the local smoothness of the utility function, this work proves that bidders can learn optimal shading strategies much faster than previously thought. While the $O(T^2)$ computational complexity of UCBid1+ presents a challenge for high-frequency applications, the theoretical jump from $O(\sqrt{T})$ to $O(T^{1/3})$ marks a significant advancement in auction theory. Future work may address non-stationary environments where bid distributions drift over time.
Summary updated