Research map / Bandits and online learning / Online convex optimization and games
No-Regret Online Autobidding Algorithms in First-price Auctions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives no-regret ROI-constrained autobidding algorithms for repeated first-price auctions against the unconditionally optimal randomized bidding strategy, achieving Õ(√T) regret with full feedback and Õ(T^{3/4}) with bandit feedback.
Problem
Online bidding by ROI-constrained value maximizers in repeated non-truthful (first-price) auctions, benchmarked against the unconditionally optimal randomized strategy in hindsight, under full or bandit (win/lose) feedback.
Approach
Shows optimal randomized bidding in first-price auctions reduces to deterministic bidding under a transformed competing-bid distribution (concave envelope of the allocation-payment curve), enabling mirror-descent primal-dual bidding; with unknown competing-bid distribution, it uses stage-based restarts with optimistic empirical CDFs (full feedback) or explore-then-exploit with conservative bidding
Key results
- Full feedback: expected regret and ROI violation both Õ(√T) against the unconditionally optimal randomized strategy in first-price auctions.
- Bandit feedback: regret and ROI violation Õ(T^{3/4}), matching the prior Lipschitz-benchmark rate but against the stronger unconditional benchmark.
- Lower bound Ω(T^{2/3}) from prior work implies Õ(√T) is impossible under bandit feedback, leaving a gap.
Surprising findings
- Deterministic bidding can be strictly suboptimal in first-price auctions; randomized bidding can exploit ROI slackness to earn higher reward.
Limitations
- Bandit-feedback regret Õ(T^{3/4}) leaves a gap to the Ω(T^{2/3}) lower bound and the ideal Õ(√T).
- Analysis is for ROI constraints only; budget constraints are only noted as extendable.
- Full-feedback algorithm requires restarts and a bound on competing-bid distribution estimation; results are for i.i.d. values and competing bids.
Experimental setup
Metrics: regret ROI violation
Baselines: truthful-auction ROI bidding (primal-dual) Lipschitz-continuous benchmark no-regret algorithm for first-price auctions
Builds on: primal-dual framework for autobidding mirror descent Lipschitz bandits autobidding
Closest papers by meaning
- Learning to Bid in Repeated First-Price Auctions with Budgets (ICML 2023 · similarity 0.91)
- Leveraging the Hints: Adaptive Bidding in Repeated First-Price Auctions (NeurIPS 2022 · similarity 0.90)
- Optimizing the coalition gain in Online Auctions with Greedy Structured Bandits (NeurIPS 2024 · similarity 0.88)
- Randomized Truthful Auctions with Learning Agents (NeurIPS 2024 · similarity 0.88)
- Non-stochastic Budgeted Online Pricing with Semi-Bandit Feedback (AAAI 2025 · similarity 0.88)
- Learning-Augmented Online Bidding in Stochastic Settings (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.