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

Abstract

In this paper, we study learning to bid in repeated first-price auctions with a hard budget constraint. We focus on one-sided information feedback: the highest competing bid is observed after a loss but remains unobserved after a win. The competing bid depends on the impression context through an unknown coefficient and additive noise with an unknown distribution. To learn this model from censored observations, we propose a regression method based on conditional quantile invariance. Combining this estimator with bid elimination and a dual update procedure, we obtain expected regret growing at most as the square root of the horizon, up to logarithmic factors, against the optimal hard-budget policy under the stated regularity, identifiability, visibility, and effective-value conditions. This matches the horizon dependence of established lower bounds for general first-price auction learning. We also discuss a structured multi-dimensional extension in which contexts lie on a monotone one-dimensional manifold.