# Learning to Bid with Unknown Private Values in Budget-Constrained First-Price Auctions

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 52 references that are in the map.
- First posted on arXiv 10 May 2026.

## Builds on (most cited first, 29 of 29)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (2022)
- [Optimal No-regret Learning in Repeated First-price Auctions](https://mlsanity.com/paper/2003.09795/) (2020)
- [Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions](https://mlsanity.com/paper/2007.04568/) (2020)
- [Auto-bidding and Auctions in Online Advertising: A Survey](https://mlsanity.com/paper/2408.07685/) (2024)
- [Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics](https://mlsanity.com/paper/2301.13306/) (2023)
- [Real-Time Bidding Benchmarking with iPinYou Dataset](https://mlsanity.com/paper/1407.7073/) (2014)
- [Learning to Bid in Contextual First Price Auctions](https://mlsanity.com/paper/2109.03173/) (2021)
- [Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence](https://mlsanity.com/paper/2205.08674/) (2022)
- [Online Bidding Algorithms for Return-on-Spend Constrained Advertisers](https://mlsanity.com/paper/2208.13713/) (2022)
- [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)
- [Leveraging the Hints: Adaptive Bidding in Repeated First-Price Auctions](https://mlsanity.com/paper/2211.06358/) (2022)
- [No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints](https://mlsanity.com/paper/2404.09832/) (2024)
- [A Field Guide for Pacing Budget and ROS Constraints](https://mlsanity.com/paper/2302.08530/) (2023)
- [Online Causal Inference for Advertising in Real-Time Bidding Auctions](https://mlsanity.com/paper/1908.08600/) (2019)
- [On the Complexity of Equilibrium Computation in First-Price Auctions](https://mlsanity.com/paper/2103.03238/) (2021)
- [Joint Value Estimation and Bidding in Repeated First-Price Auctions](https://mlsanity.com/paper/2502.17292/) (2025)
- [Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules](https://mlsanity.com/paper/2303.16388/) (2023)
- [Learning to Bid in Non-Stationary Repeated First-Price Auctions](https://mlsanity.com/paper/2501.13358/) (2025)
- [Online Learning in Contextual Second-Price Pay-Per-Click Auctions](https://mlsanity.com/paper/2310.05047/) (2023)
- [Online Bidding under RoS Constraints without Knowing the Value](https://mlsanity.com/paper/2503.03195/) (2025)
- [No-Regret Online Autobidding Algorithms in First-price Auctions](https://mlsanity.com/paper/2510.16869/) (2025)
- [The (Marginal) Value of a Search Ad: An Online Causal Framework for Repeated Second-price Auctions](https://mlsanity.com/paper/2605.01756/) (2026)

## Built on by (most cited first, 1 of 1)

- [Fast A/B/n Testing: Exact Multi-Policy Comparison via Tree-Coupled Feedback Sharing](https://mlsanity.com/paper/2608.12831/) (2026)

## Abstract (arXiv)

We study the operational problem of automated bidding in repeated first-price auctions under budget and return-on-spend (RoS) constraints. In this setting, an auto-bidder must translate advertiser goals and constraints into real-time bids while learning two latent objects: the causal uplift value of each ad impression and the highest competing bid (HoB) needed to win it. We model uplift values and HoBs through a shared-context Linear Treatment Effect (LTE) structure and analyze both full-information and binary HoB feedback. We develop Dual-LTE, a dual-aware online learning framework that coordinates value estimation, HoB estimation, and budget/RoS control through confidence-guided exploration. We prove regret and constraint-violation guarantees that scale as widetildeO(√T) under full-information HoB feedback and widetildeO(T2/3) under binary win/loss feedback, where widetildeO(·) hides problem-dependent and logarithmic factors. Semi-synthetic experiments using real auction covariates show that Dual-LTE achieves lower regret than the baselines across budget and RoS settings, while illustrating the tradeoff between regret and constraint violation. Our results provide operational guidance for DSPs and platform auto-bidders that manage advertiser budgets or seek to meet ROAS targets. When impression values must be learned, value estimation should be coordinated with budget or ROAS control: the auto-bidder should follow the Lagrangian bidding rule only when value estimates are sufficiently accurate given the current constraint pressure and should otherwise use controlled exploration.