Online Bidding under RoS Constraints without Knowing the Value
Sushant Vijayan, Zhe Feng, Swati Padmanabhan, Karthikeyan Shanmugam, Arun Suggala, Di Wang
Abstract
We consider the problem of bidding in online advertising, where an advertiser aims to maximize value while adhering to budget and Return-on-Spend (RoS) constraints. Unlike prior work that assumes knowledge of the value generated by winning each impression (e.g., conversions), we address the more realistic setting where the advertiser must simultaneously learn the optimal bidding strategy and the value of each impression opportunity. This introduces a challenging exploration-exploitation dilemma: the advertiser must balance exploring different bids to estimate impression values with exploiting current knowledge to bid effectively. To address this, we propose a novel Upper Confidence Bound (UCB)-style algorithm that carefully manages this trade-off. Via a rigorous theoretical analysis, we prove that our algorithm achieves 𝑂 ( √︁ 𝑇 log(|B|𝑇 )) regret and constraint violation, where 𝑇 is the number of bidding rounds and B is the domain of possible bids. This establishes the first optimal regret and constraint violation bounds for bidding in the online setting with unknown impression values. Moreover, our algorithm is computationally efficient and simple to implement. We validate our theoretical findings through experiments on synthetic data, demonstrating that our algorithm exhibits strong empirical performance compared to existing approaches.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
3 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- No-Regret Online Autobidding Algorithms in First-price Auctions cites Dual Mirror Descent for Online Allocation Problems
- Towards Safe and Optimal Online Bidding: A Modular Look-ahead Lyapunov Framework cites An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints
- Towards Safe and Optimal Online Bidding: A Modular Look-ahead Lyapunov Framework cites Dual Mirror Descent for Online Allocation Problems
- Towards Safe and Optimal Online Bidding: A Modular Look-ahead Lyapunov Framework cites A Unifying Framework for Online Optimization with Long-Term Constraints
- Auto-bidding under Return-on-Spend Constraints with Uncertainty Quantification cites Dual Mirror Descent for Online Allocation Problems
- Auto-bidding under Return-on-Spend Constraints with Uncertainty Quantification cites A Unifying Framework for Online Optimization with Long-Term Constraints
Cited by top-tier papers3
- No-Regret Online Autobidding Algorithms in First-price AuctionsYilin Li, Yuan Deng, Wei Tang, Hanrui ZhangNeurIPS 2025 · 4 citations
- Towards Safe and Optimal Online Bidding: A Modular Look-ahead Lyapunov FrameworkHengquan Guo, Haobo Zhang, Junwei Pan, Shudong Huang et al.ICLR 2026
- Auto-bidding under Return-on-Spend Constraints with Uncertainty QuantificationJiale Han, Chun Gan, Chengcheng Zhang, Jie He et al.WWW 2026
Builds on11
- Dual Mirror Descent for Online Allocation ProblemsSantiago R. Balseiro, Haihao Lu, Vahab S. MirrokniICML 2020 · 102 citations
- Towards Efficient Auctions in an Auto-bidding WorldYuan Deng, Jieming Mao, Vahab S. Mirrokni, Song ZuoWWW 2021 · 87 citations
- An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General ConstraintsXin Liu, Bin Li, Pengyi Shi, Lei YingNeurIPS 2021 · 63 citations
- A Unifying Framework for Online Optimization with Long-Term ConstraintsMatteo Castiglioni, Andrea Celli, Alberto Marchesi, Giulia Romano et al.NeurIPS 2022 · 59 citations
- Online mirror descent and dual averaging: keeping pace in the dynamic caseHuang Fang, Nick Harvey, Victor S. Portella, Michael P. FriedlanderICML 2020 · 38 citations
Related papers
- Online Bidding Algorithms for Return-on-Spend Constrained Advertisers✱Zhe Feng, Swati Padmanabhan, Di WangWWW 2023 · 38 citations
- No-Regret Algorithms in non-Truthful Auctions with Budget and ROI ConstraintsGagan Aggarwal, Giannis Fikioris, Mingfei ZhaoWWW 2025 · 13 citations
- Safe Online Bid Optimization with Return on Investment and Budget ConstraintsMatteo Castiglioni, Alessandro Nuara, Giulia Romano, Giorgio Spadaro et al.KDD 2025
- Improved Online Learning Algorithms for CTR Prediction in Ad AuctionsZhe Feng, Christopher Liaw, Zixin ZhouICML 2023 · 9 citations
- Online Learning under Budget and ROI Constraints via Weak AdaptivityMatteo Castiglioni, Andrea Celli, Christian KroerICML 2024 · 12 citations
