Adaptive Bidding Policies for First-Price Auctions with Budget Constraints under Non-stationarity

Researchers Yige Wang and Jiashuo Jiang have published a significant paper tackling a core problem in modern digital advertising: how a budget-constrained bidder should learn to bid optimally in repeated first-price auctions. This challenge has become critical due to the industry's widespread transition from second-price to first-price auction formats, a shift that fundamentally changes optimal bidding strategy and renders traditional 'truthful bidding' suboptimal. Their proposed solution is a dual-gradient-descent-based policy that dynamically adjusts a bidder's strategy by maintaining a dual variable tied to budget consumption.

The paper analyzes two key scenarios. In the first, an 'uninformative setting' where future market conditions are unknown and potentially non-stationary, the algorithm achieves a regret bound of ~O(sqrt(T)) plus a term capturing market variation, a result proven to be mathematically optimal. In the second, an 'informative setting' where a prediction of budget allocation is available, the variation term is eliminated, yielding a cleaner ~O(sqrt(T)) regret bound tied directly to prediction error. The researchers further refine their benchmark by introducing a per-period budget allocation plan, which also achieves ~O(sqrt(T)) regret and includes robustness guarantees against deviations from the planned strategy.