# Online learning in repeated auctions

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2015.

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

- [Distribution-free Contextual Dynamic Pricing](https://mlsanity.com/paper/2109.07340/) (2021)
- [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)
- [No-Regret Learning in Bilateral Trade via Global Budget Balance](https://mlsanity.com/paper/2310.12370/) (2023)
- [An α-regret analysis of Adversarial Bilateral Trade](https://mlsanity.com/paper/2210.06846/) (2022)
- [The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations](https://mlsanity.com/paper/2307.09478/) (2023)
- [Nash Convergence of Mean-Based Learning Algorithms in First-Price Auctions](https://mlsanity.com/paper/2110.03906/) (2021)
- [Offline Reinforcement Learning for Optimizing Production Bidding Policies](https://mlsanity.com/paper/2310.09426/) (2023)
- [Fast Rate Learning in Stochastic First Price Bidding](https://mlsanity.com/paper/2107.01835/) (2021)
- [No-Regret Learning in Partially-Informed Auctions](https://mlsanity.com/paper/2202.10606/) (2022)
- [Adversarial Constrained Bidding via Minimax Regret Optimization with Causality-Aware Reinforcement Learning](https://mlsanity.com/paper/2306.07106/) (2023)
- [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)
- [Market Making without Regret](https://mlsanity.com/paper/2411.13993/) (2024)
- [Censored Semi-Bandits for Resource Allocation](https://mlsanity.com/paper/2104.05781/) (2021)
- [Equilibrium of Data Markets with Externality](https://mlsanity.com/paper/2302.08012/) (2023)
- [Non-Stochastic CDF Estimation Using Threshold Queries](https://mlsanity.com/paper/2301.05682/) (2023)
- [Adaptive maximization of social welfare](https://mlsanity.com/paper/2310.09597/) (2023)
- [Improved learning rates in multi-unit uniform price auctions](https://mlsanity.com/paper/2501.10181/) (2025)
- [Online Bidding under RoS Constraints without Knowing the Value](https://mlsanity.com/paper/2503.03195/) (2025)
- [The (Marginal) Value of a Search Ad: An Online Causal Framework for Repeated Second-price Auctions](https://mlsanity.com/paper/2605.01756/) (2026)
- [Leveraging Reviews: Learning to Price with Buyer and Seller Uncertainty](https://mlsanity.com/paper/2302.09700/) (2023)
- [Online Ad Procurement in Non-stationary Autobidding Worlds](https://mlsanity.com/paper/2307.05698/) (2023)
- [Comparing Uniform Price and Discriminatory Multi-Unit Auctions through Regret Minimization](https://mlsanity.com/paper/2510.19591/) (2025)
- [Making the most of your day: online learning for optimal allocation of time](https://mlsanity.com/paper/2102.08087/) (2021)
- [Double Auctions with Two-sided Bandit Feedback](https://mlsanity.com/paper/2208.06536/) (2022)
- [Sequential Decision Problems with Weak Feedback](https://mlsanity.com/paper/2212.11603/) (2022)
- [Bandits for Sponsored Search Auctions under Unknown Valuation Model: Case Study in E-Commerce Advertising](https://mlsanity.com/paper/2304.00999/) (2023)

## Abstract (arXiv)

Motivated by online advertising auctions, we consider repeated Vickrey auctions where goods of unknown value are sold sequentially and bidders only learn (potentially noisy) information about a good's value once it is purchased. We adopt an online learning approach with bandit feedback to model this problem and derive bidding strategies for two models: stochastic and adversarial. In the stochastic model, the observed values of the goods are random variables centered around the true value of the good. In this case, logarithmic regret is achievable when competing against well behaved adversaries. In the adversarial model, the goods need not be identical and we simply compare our performance against that of the best fixed bid in hindsight. We show that sublinear regret is also achievable in this case and prove matching minimax lower bounds. To our knowledge, this is the first complete set of strategies for bidders participating in auctions of this type.