mlsanityData to 14 Oct 2026

No-regret Learning in Repeated First-Price Auctions with Budget Constraints

arXiv 2205.14572 ↗First posted 29 May 2022cs.GT cs.LGcited by 9

Not on the map. Why?

Abstract (arXiv)

Recently the online advertising market has exhibited a gradual shift from second-price auctions to first-price auctions. Although there has been a line of works concerning online bidding strategies in first-price auctions, it still remains open how to handle budget constraints in the problem. In the present paper, we initiate the study for a buyer with budgets to learn online bidding strategies in repeated first-price auctions. We propose an RL-based bidding algorithm against the optimal non-anticipating strategy under stationary competition. Our algorithm obtains widetilde O(√ T)-regret if the bids are all revealed at the end of each round. With the restriction that the buyer only sees the winning bid after each round, our modified algorithm obtains widetilde O(T^frac712)-regret by techniques developed from survival analysis. Our analysis extends to the more general scenario where the buyer has any bounded instantaneous utility function with regrets of the same order.

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Builds on 16 of its 47 references that are in the map. First posted on arXiv 29 May 2022.

Builds on

16 of 47 references.

References · 16

  1. 2013Bandits with Knapsackscited by 164
  2. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 129
  3. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  4. 2015Linear Contextual Bandits with Knapsackscited by 82
  5. 2020Q-learning with Logarithmic Regretcited by 60
  6. 2014Resourceful Contextual Banditscited by 45
  7. 2015An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectivescited by 43
  8. 2020Nearly Minimax Optimal Reinforcement Learning for Discounted MDPscited by 42
  9. 2020Dynamic Incentive-aware Learning: Robust Pricing in Contextual Auctionscited by 34
  10. 2020Learning to Bid Optimally and Efficiently in Adversarial First-price Auctionscited by 33
  11. 2020Regret Bounds for Discounted MDPscited by 19
  12. 2021Learning to Bid in Contextual First Price Auctionscited by 19
4 more
  1. 2022Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergencecited by 18
  2. 2021Fast Rate Learning in Stochastic First Price Biddingcited by 7
  3. 2014Perfect Bayesian Equilibria in Repeated Salescited by 6
  4. 2017Online Learning of Optimal Bidding Strategy in Repeated Multi-Commodity Auctionscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 1; 2024: 0; 2025: 5; 2026: 2.

9 papers.

  1. 2022Online Bidding Algorithms for Return-on-Spend Constrained Advertiserscited by 17
  2. 2023Online Learning under Budget and ROI Constraints via Weak Adaptivitycited by 5
  3. 2025Learning to Bid in Non-Stationary Repeated First-Price Auctionscited by 5
  4. 2025Regret Minimization for Piecewise Linear Rewards: Contracts, Auctions, and Beyondcited by 3
  5. 2025Online Bidding under RoS Constraints without Knowing the Valuecited by 2
  6. 2025Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedbackcited by 1
  7. 2025Plan-Driven Adaptive Bidding for First-Price Auctions with Budget Constraints under Nonstationaritycited by 0
  8. 2026Guiding the Recommender: Information-Aware Auto-Bidding for Content Promotioncited by 0
  9. 2026A3M: Adaptive, Adversarial and Multi-Objective Learning for Strategic Bidding in Repeated Auctionscited by 0