Optimal No-Regret Learning in Repeated First-Price Auctions

Yanjun Han (), Tsachy Weissman () and Zhengyuan Zhou ()
Additional contact information
Yanjun Han: Courant Institute of Mathematical Sciences and Center for Data Science, New York University, New York, New York 10012
Tsachy Weissman: Department of Electrical Engineering, Stanford University, Stanford, California 94305
Zhengyuan Zhou: Stern School of Business, New York University, New York, New York 10012

Operations Research, 2025, vol. 73, issue 1, 209-238

Abstract: We study online learning in repeated first-price auctions where a bidder, only observing the winning bid at the end of each auction, learns to adaptively bid to maximize the cumulative payoff. To achieve this goal, the bidder faces censored feedback: If the bidder wins the bid, then the bidder is not able to observe the highest bid of the other bidders, which we assume is i.i.d. drawn from an unknown distribution. In this paper, we develop the first learning algorithm that achieves a near-optimal O ˜ ( T ) regret bound, by exploiting two structural properties of first-price auctions, that is, the specific feedback structure and payoff function. We first formulate the feedback structure in first-price auctions as partially ordered contextual bandits, a combination of the graph feedback across actions (bids), the cross-learning across contexts (private values), and a partial order over the contexts. We establish both strengths and weaknesses of this framework by showing a curious separation that a regret nearly independent of the action/context sizes is possible under stochastic contexts but is impossible under adversarial contexts. In particular, this framework leads to an O ( T log 2.5 T ) regret for first-price auctions when the bidder’s private values are independent and identically distributed. Despite the limitation of this framework, we further exploit the special payoff function of first-price auctions to develop a sample-efficient algorithm even in the presence of adversarially generated private values. We establish an O ( T log 3 T ) regret bound for this algorithm, hence providing a complete characterization of optimal learning guarantees for first-price auctions.

Keywords: Machine Learning and Data Science; online learning; first-price auction; regret analysis; graph feedback; censored demand (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2020.0282 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:1:p:209-238

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().