No-Regret Online Autobidding Algorithms in First-price Auctions

2025/10/19 by Yuan Deng, Y. G. Li, Deng, Yuan +5
Business, Management and Accounting · Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Consumer Market Behavior and Pricing #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.2510.16869

openalex publication_date 2025/10/19 · openalex created_date 2025/10/22 · openalex updated_date 2026/07/28

Abstract

Automated bidding to optimize online advertising with various constraints, e.g. ROI constraints and budget constraints, is widely adopted by advertisers. A key challenge lies in designing algorithms for non-truthful mechanisms with ROI constraints. While prior work has addressed truthful auctions or non-truthful auctions with weaker benchmarks, this paper provides a significant improvement: We develop online bidding algorithms for repeated first-price auctions with ROI constraints, benchmarking against the optimal randomized strategy in hindsight. In the full feedback setting, where the maximum competing bid is observed, our algorithm achieves a near-optimal \widetildeO(√(T)) regret bound, and in the bandit feedback setting (where the bidder only observes whether the bidder wins each auction), our algorithm attains \widetildeO(T^3/4) regret bound.

Citations

• Online Bidding under RoS Constraints without Knowing the Value
• Auto-bidding and Auctions in Online Advertising: A Survey
• No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints
• To Spend or to Gain: Online Learning in Repeated Karma Auctions
• Efficiency of the Generalized Second-Price Auction for Value Maximizers
• Auction Design for Bidders with Ex Post ROI Constraints
• Strategic Budget Selection in a Competitive Autobidding World
• Auction Design for Value Maximizers with Budget and Return-on-spend Constraints
• Multi-Platform Budget Management in Ad Markets with Non-IC Auctions
• Learning to Bid in Repeated First-Price Auctions with Budgets
• A Field Guide for Pacing Budget and ROS Constraints
• Online Learning under Budget and ROI Constraints via Weak Adaptivity
• Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics
• Online Bidding Algorithms for Return-on-Spend Constrained Advertisers
• Efficiency of the First-Price Auction in the Autobidding World
• Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence
• Online Learning with Vector Costs and Bandits with Knapsacks
• Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions
• Dual Mirror Descent for Online Allocation Problems
• Introduction to Multi-Armed Bandits
• Contextual Bandits with Cross-learning
• Online learning in repeated auctions

Related

• No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints
• No-regret Learning in Repeated First-Price Auctions with Budget Constraints
• Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics
• Online Bidding Algorithms for Return-on-Spend Constrained Advertisers
• Online Bidding under RoS Constraints without Knowing the Value