Introduction
In the landscape of modern digital advertising, manual bidding has been largely replaced by autobidders—automated agents that manage complex ad campaigns on behalf of advertisers. These agents are typically tasked with optimizing high-level objectives while adhering to strict constraints, most notably daily budgets and Return-on-Investment (ROI) targets.
While previous research has extensively explored bidding dynamics under either a budget constraint or an ROI constraint, real-world applications almost always require satisfying both simultaneously. This paper addresses this gap by introducing a novel learning algorithm designed to handle dual constraints, providing theoretical guarantees for both individual performance and global market efficiency.
The Challenge of Dual Constraints
Managing both budget and ROI constraints creates a complex optimization problem. In a competitive auction environment, many such algorithms learn and compete simultaneously. Standard game-theoretic analysis often seeks a Nash equilibrium—a stable state where no bidder has an incentive to change their strategy. However, finding such an equilibrium in large-scale ad auctions is computationally "PPAD-hard," making it an impractical benchmark for real-world systems.
The authors focus on a more practical goal: developing an algorithm that guarantees constraint satisfaction and maintains high system-wide utility even if the bidding process is chaotic and never converges to a stable equilibrium.
Methodology: Algorithm 2 and Pacing Dynamics
The paper proposes Algorithm 2, a gradient-based learning approach that utilizes two distinct "pacing multipliers":
- Budget Multiplier ($\mu^B$): This value increases if the agent is spending too quickly, signaling the need to lower bids to conserve the budget.
- ROI Multiplier ($\mu^R$): This value increases if the agent is failing to meet its ROI target, signaling the need to be more selective with bids.
The Conservative Bid
At each auction round, the algorithm calculates a bid based on the maximum (most conservative) of these two multipliers. By using the larger multiplier, the agent ensures that the most restrictive constraint takes precedence, preventing overspending or ROI dilution.
Dual-Track Updates and Bandit Feedback
The algorithm employs a variation of Stochastic Gradient Descent (SGD) to update these multipliers. Crucially, even though only the "winning" multiplier is used to place a bid, the algorithm updates both multipliers based on the auction's feedback. This allows the agent to track the "slack" in both constraints simultaneously. Furthermore, the algorithm operates under bandit feedback, meaning it only requires information about the auctions it actually participated in, rather than needing to know the outcomes of all possible bids.
Key Theoretical Insights
Efficiency Without Equilibrium
A major contribution of this work is the proof that global efficiency—measured as Liquid Welfare—remains high regardless of convergence. The authors demonstrate that when all bidders use this algorithm, the system achieves at least 1/2 of the optimal liquid welfare. This result shifts the focus from the necessity of equilibrium to the robustness of the learning dynamics themselves.
Ex-Post Satisfaction
Many existing algorithms only satisfy constraints "on average" or over a long time horizon. Algorithm 2 is designed for ex-post satisfaction, meaning it ensures that budget and ROI constraints are met with probability 1 by the end of the period. This provides a critical safety guarantee for advertisers who cannot afford to exceed their financial limits.
Regret Analysis
The paper proves that the algorithm achieves "vanishing individual regret" in adversarial environments. The regret scales at a rate of approximately $T^{7/8}$. While this rate is higher than the $T^{1/2}$ seen in simpler settings, it represents a significant theoretical bound for a dual-constraint environment with bandit feedback.
Empirical Results
The authors evaluated Algorithm 2 using synthetic simulations across 12 different problem instances, including various auction formats (first-price and second-price) and value distributions (Uniform, Gaussian, and Correlated Gaussian).
Key findings from the simulations include:
- Constraint Adherence: Algorithm 2 satisfied all constraints exactly, whereas naive baselines (such as epsilon-greedy) frequently resulted in significant constraint violations.
- Performance Parity: The algorithm performed on par with sophisticated "Best-Of-Many-Worlds" (BOMW) heuristics but offered much stronger theoretical safety guarantees.
Conclusion and Future Work
This research provides a robust framework for understanding how autobidders can navigate the dual pressures of budgets and ROI targets. By proving that high efficiency can be maintained without reaching an equilibrium, the authors offer a more realistic model for modern ad markets.
Future work may focus on tightening the $T^{7/8}$ regret bound and exploring the impact of these bidding dynamics on platform revenue. Additionally, investigating how the system responds to strategic "gaming" by individual advertisers remains an open and important question for the field.
Summary updated