# Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jul 2020.

## Built on by (most cited first, 30 of 33)

- [Learning to Bid in Contextual First Price Auctions](https://mlsanity.com/paper/2109.03173/) (2021)
- [Online Bidding Algorithms for Return-on-Spend Constrained Advertisers](https://mlsanity.com/paper/2208.13713/) (2022)
- [The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations](https://mlsanity.com/paper/2307.09478/) (2023)
- [Beyond Bandit Feedback in Online Multiclass Classification](https://mlsanity.com/paper/2106.03596/) (2021)
- [Leveraging the Hints: Adaptive Bidding in Repeated First-Price Auctions](https://mlsanity.com/paper/2211.06358/) (2022)
- [No-regret Learning in Repeated First-Price Auctions with Budget Constraints](https://mlsanity.com/paper/2205.14572/) (2022)
- [No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints](https://mlsanity.com/paper/2404.09832/) (2024)
- [Nash Convergence of Mean-Based Learning Algorithms in First-Price Auctions](https://mlsanity.com/paper/2110.03906/) (2021)
- [Strategizing against No-Regret Learners in First-Price Auctions](https://mlsanity.com/paper/2402.08637/) (2024)
- [Repeated Principal-Agent Games with Unobserved Agent Rewards and Perfect-Knowledge Agents](https://mlsanity.com/paper/2304.07407/) (2023)
- [Adversarial Constrained Bidding via Minimax Regret Optimization with Causality-Aware Reinforcement Learning](https://mlsanity.com/paper/2306.07106/) (2023)
- [Optimal cross-learning for contextual bandits with unknown context distributions](https://mlsanity.com/paper/2401.01857/) (2024)
- [Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions](https://mlsanity.com/paper/2402.07363/) (2024)
- [Joint Value Estimation and Bidding in Repeated First-Price Auctions](https://mlsanity.com/paper/2502.17292/) (2025)
- [Incrementality Bidding via Reinforcement Learning under Mixed and Delayed Rewards](https://mlsanity.com/paper/2206.01293/) (2022)
- [Online Learning under Budget and ROI Constraints via Weak Adaptivity](https://mlsanity.com/paper/2302.01203/) (2023)
- [Learning and Collusion in Multi-unit Auctions](https://mlsanity.com/paper/2305.17402/) (2023)
- [Estimating and Incentivizing Imperfect-Knowledge Agents with Hidden Rewards](https://mlsanity.com/paper/2308.06717/) (2023)
- [Learning to Bid in Non-Stationary Repeated First-Price Auctions](https://mlsanity.com/paper/2501.13358/) (2025)
- [Best of Many Worlds Guarantees for Online Learning with Knapsacks](https://mlsanity.com/paper/2202.13710/) (2022)
- [Online Learning in Contextual Second-Price Pay-Per-Click Auctions](https://mlsanity.com/paper/2310.05047/) (2023)
- [Learning in Repeated Multi-Unit Pay-As-Bid Auctions](https://mlsanity.com/paper/2307.15193/) (2023)
- [Adaptive maximization of social welfare](https://mlsanity.com/paper/2310.09597/) (2023)
- [Online Bidding under RoS Constraints without Knowing the Value](https://mlsanity.com/paper/2503.03195/) (2025)
- [BAT: Benchmark for Auto-bidding Task](https://mlsanity.com/paper/2505.08485/) (2025)
- [The (Marginal) Value of a Search Ad: An Online Causal Framework for Repeated Second-price Auctions](https://mlsanity.com/paper/2605.01756/) (2026)
- [Online Ad Procurement in Non-stationary Autobidding Worlds](https://mlsanity.com/paper/2307.05698/) (2023)
- [Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback](https://mlsanity.com/paper/2502.04678/) (2025)
- [Learning to Bid with Unknown Private Values in Budget-Constrained First-Price Auctions](https://mlsanity.com/paper/2605.09448/) (2026)
- [Active Learning for Contextual Search with Binary Feedbacks](https://mlsanity.com/paper/2110.01072/) (2021)

## Abstract (arXiv)

First-price auctions have very recently swept the online advertising industry, replacing second-price auctions as the predominant auction mechanism on many platforms. This shift has brought forth important challenges for a bidder: how should one bid in a first-price auction, where unlike in second-price auctions, it is no longer optimal to bid one's private value truthfully and hard to know the others' bidding behaviors? In this paper, we take an online learning angle and address the fundamental problem of learning to bid in repeated first-price auctions, where both the bidder's private valuations and other bidders' bids can be arbitrary. We develop the first minimax optimal online bidding algorithm that achieves an widetildeO(√T) regret when competing with the set of all Lipschitz bidding policies, a strong oracle that contains a rich set of bidding strategies. This novel algorithm is built on the insight that the presence of a good expert can be leveraged to improve performance, as well as an original hierarchical expert-chaining structure, both of which could be of independent interest in online learning. Further, by exploiting the product structure that exists in the problem, we modify this algorithm--in its vanilla form statistically optimal but computationally infeasible--to a computationally efficient and space efficient algorithm that also retains the same widetildeO(√T) minimax optimal regret guarantee. Additionally, through an impossibility result, we highlight that one is unlikely to compete this favorably with a stronger oracle (than the considered Lipschitz bidding policies). Finally, we test our algorithm on three real-world first-price auction datasets obtained from Verizon Media and demonstrate our algorithm's superior performance compared to several existing bidding algorithms.