Online Bidding Algorithms with Strict Return on Spend (ROS) Constraint

摘要

We study the auto-bidding problem under a strict return-on-spend constraint (ROSC), where an online algorithm decides how much to bid for each ad slot based on a revealed value and hidden allocation and payment functions. The goal is to maximize cumulative expected utility (value times winning probability) while ensuring that total expected payment does not exceed total expected utility. We prove an impossibility result showing that no online algorithm can achieve sublinear regret even when values, allocations, and payments are drawn i.i.d. from an unknown distribution. For the special case of constant valuations, we design an algorithm that strictly satisfies the ROSC and achieves regret optimal up to logarithmic factors.