# Plan-Driven Adaptive Bidding for First-Price Auctions with Budget Constraints under Nonstationarity

arXiv: https://arxiv.org/abs/2505.02796 · HTML: https://mlsanity.com/paper/2505.02796/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 42 references that are in the map.
- First posted on arXiv 5 May 2025.

## Builds on (most cited first, 17 of 17)

- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020)
- [Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2002.10421/) (2020)
- [Online learning in repeated auctions](https://mlsanity.com/paper/1511.05720/) (2015)
- [Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions](https://mlsanity.com/paper/2007.04568/) (2020)
- [Online Stochastic Optimization with Wasserstein Based Non-stationarity](https://mlsanity.com/paper/2012.06961/) (2020)
- [Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics](https://mlsanity.com/paper/2301.13306/) (2023)
- [Learning to Bid in Repeated First-Price Auctions with Budgets](https://mlsanity.com/paper/2304.13477/) (2023)
- [Real Time Bid Optimization with Smooth Budget Delivery in Online Advertising](https://mlsanity.com/paper/1305.3011/) (2013)
- [No-regret Learning in Repeated First-Price Auctions with Budget Constraints](https://mlsanity.com/paper/2205.14572/) (2022)
- [Online Resource Allocation under Horizon Uncertainty](https://mlsanity.com/paper/2206.13606/) (2022)
- [No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints](https://mlsanity.com/paper/2404.09832/) (2024)
- [A Field Guide for Pacing Budget and ROS Constraints](https://mlsanity.com/paper/2302.08530/) (2023)
- [Contextual Standard Auctions with Budgets: Revenue Equivalence and Efficiency Guarantees](https://mlsanity.com/paper/2102.10476/) (2021)
- [Robust Budget Pacing with a Single Sample](https://mlsanity.com/paper/2302.02006/) (2023)
- [Interpretable Deep Learning for Forecasting Online Advertising Costs: Insights from the Competitive Bidding Landscape](https://mlsanity.com/paper/2302.05762/) (2023)

## Abstract (arXiv)

We study budget pacing in repeated first-price auctions when an advertiser's private-value distributions change over time and the stationary competing-bid distribution is unknown. We ask how a feasible expenditure plan should enter online bid shading, learning, and hard budget control. We establish a plan-to-performance decomposition for a plan-driven projected-dual policy. The policy uses any feasible expenditure plan as a soft target, learns an unknown stationary competing-bid CDF from thresholds revealed after each auction, and enforces the campaign budget on every sample path. Against a distribution-informed expected-budget fluid benchmark, the uniform-plan reward gap is O(√ T)+O(mathcal WT), where mathcal WT measures heterogeneity in private-value distributions. With a supplied feasible plan, the global gap decomposes into a one-sided O(√T) fixed-plan execution term and a plan-mismatch term bounded by (b/2a)PlanError. The same analysis provides guarantees for strict and relaxed period-cap comparators, exact recovery of the global benchmark under a specific allowance vector, and separate lower bounds establishing the necessity of the temporal-heterogeneity and Plan Error terms. An upstream planner can translate forecasts or managerial priorities into a feasible spending trajectory, while the online controller adapts bids using realized thresholds and expenditures. The guarantee is modular: it evaluates the final normalized or projected plan through PlanError. A specific forecasting model can be linked to the guarantee by establishing how its primitive estimation errors propagate to this plan-quality metric.