# Learning to Bid in Non-Stationary Repeated First-Price Auctions arXiv: https://arxiv.org/abs/2501.13358 ยท HTML: https://mlsanity.com/paper/2501.13358/ ## Key facts - Cited by 5 papers in the map (data through 14 Oct 2026). - Builds on 34 of its 65 references that are in the map. - First posted on arXiv 23 Jan 2025. ## Builds on (most cited first, 30 of 34) - [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013) - [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013) - [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015) - [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018) - [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018) - [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015) - [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021) - [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016) - [A Simple Approach for Non-stationary Linear Bandits](https://mlsanity.com/paper/2103.05324/) (2021) - [Hedging the Drift: Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1903.01461/) (2019) - [Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards](https://mlsanity.com/paper/1405.3316/) (2014) - [Display Advertising with Real-Time Bidding (RTB) and Behavioural Targeting](https://mlsanity.com/paper/1610.03013/) (2016) - [Optimal Dynamic Regret in Exp-Concave Online Learning](https://mlsanity.com/paper/2104.11824/) (2021) - [Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions](https://mlsanity.com/paper/2007.04568/) (2020) - [Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond](https://mlsanity.com/paper/2201.08905/) (2022) - [Artificial Intelligence and Auction Design](https://mlsanity.com/paper/2202.05947/) (2022) - [Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics](https://mlsanity.com/paper/2301.13306/) (2023) - [Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence](https://mlsanity.com/paper/2205.08674/) (2022) - [Optimal anytime regret with two experts](https://mlsanity.com/paper/2002.08994/) (2020) - [The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations](https://mlsanity.com/paper/2307.09478/) (2023) - [Pacing Equilibrium in First-Price Auction Markets](https://mlsanity.com/paper/1811.07166/) (2018) - [Learning to Bid in Repeated First-Price Auctions with Budgets](https://mlsanity.com/paper/2304.13477/) (2023) - [Towards Optimal Algorithms for Prediction with Expert Advice](https://mlsanity.com/paper/1409.3040/) (2014) - [A Stability Principle for Learning under Non-Stationarity](https://mlsanity.com/paper/2310.18304/) (2023) - [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) - [Optimal cross-learning for contextual bandits with unknown context distributions](https://mlsanity.com/paper/2401.01857/) (2024) - [Bayesian Nash Equilibrium in First-Price Auction with Discrete Value Distributions](https://mlsanity.com/paper/1906.09403/) (2019) - [Online Second Price Auction with Semi-bandit Feedback Under the Non-Stationary Setting](https://mlsanity.com/paper/1911.05949/) (2019) - [Learning and Optimization with Seasonal Patterns](https://mlsanity.com/paper/2005.08088/) (2020) ## Built on by (most cited first, 5 of 5) - [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) - [Optimizing Bidding Strategies in First-Price Auctions in Binary Feedback Setting with Predictions](https://mlsanity.com/paper/2506.15817/) (2025) - [A Simple Reduction Scheme for Constrained Contextual Bandits with Adversarial Contexts via Regression](https://mlsanity.com/paper/2602.05019/) (2026) - [Constrained Contextual Bandits with Adversarial Contexts](https://mlsanity.com/paper/2605.06190/) (2026) ## Abstract (arXiv) First-price auctions have recently gained significant traction in digital advertising markets, exemplified by Google's transition from second-price to first-price auctions. Unlike in second-price auctions, where bidding one's private valuation is a dominant strategy, determining an optimal bidding strategy in first-price auctions is more complex. From a learning perspective, the learner (a specific bidder) can interact with the environment (other bidders, i.e., opponents) sequentially to infer their behaviors. Existing research often assumes specific environmental conditions and benchmarks performance against the best fixed policy (static benchmark). While this approach ensures strong learning guarantees, the static benchmark can deviate significantly from the optimal strategy in environments with even mild non-stationarity. To address such scenarios, a dynamic benchmark--representing the sum of the highest achievable rewards at each time step--offers a more suitable objective. However, achieving no-regret learning with respect to the dynamic benchmark requires additional constraints. By inspecting reward functions in online first-price auctions, we introduce two metrics to quantify the regularity of the sequence of opponents' highest bids, which serve as measures of non-stationarity. We provide a minimax-optimal characterization of the dynamic regret for the class of sequences of opponents' highest bids that satisfy either of these regularity constraints. Our main technical tool is the Optimistic Mirror Descent (OMD) framework with a novel optimism configuration, which is well-suited for achieving minimax-optimal dynamic regret rates in this context. We then use synthetic datasets to validate our theoretical guarantees and demonstrate that our methods outperform existing ones.