How BiCB Revolutionizes Real‑Time Bidding for Live Ads with Light‑Weight Optimization

Abstract

Live streaming ads require second‑level bidding decisions under budget and per‑click‑cost (CPC) constraints. Existing auto‑bidding methods either assume full‑day traffic knowledge or are computationally heavy. BiCB (Binary Constrained Bidding) combines an analytically derived optimal bidding formula from linear‑program (LP) duality with a statistical traffic‑prediction module, yielding a lightweight online algorithm that closely approximates the offline LP optimum.

Problem Background

Live ads operate under Real‑Time Bidding (RTB) with a Generalized Second Price auction. An advertiser’s auto‑bidding problem can be expressed as a linear program that maximizes total conversion value subject to budget and CPC upper‑bound constraints. In practice the future traffic distribution is unknown, making the problem an online, irreversible decision process.

When only a budget constraint is considered (Budget‑Constrained Bidding, BCB), the LP reduces to a knapsack problem. A greedy algorithm that ranks requests by conversion‑per‑cost ratio (i.e., value‑to‑cost) achieves near‑optimal performance because each request’s granularity is small.

However, the greedy approach requires knowledge of the entire day’s traffic, which is unavailable in real‑time. This motivates a binary‑constrained bidding solution that does not rely on full traffic foresight.

Methodology

We extend the classic LP by adding lower‑bound constraints (e.g., minimum CPC, CTR, ROI), yielding a generalized knapsack formulation. Applying Lagrangian dual analysis gives an optimal bidding rule of the form: bid_i = max{0, (v_i - λ) / (μ)} where v_i is the predicted value of request i , and λ, μ are dual variables associated with the budget and CPC bounds. The rule is evaluated online for each request: if the computed bid satisfies the constraints the request is won, otherwise it is rejected.

The dual variables are not known a priori because they depend on the cumulative spend and clicks over the day. We estimate them using a traffic‑prediction model trained on historical data that outputs cumulative cost COST(t) and cumulative clicks CLK(t) for any time interval t. Given a candidate set of dual variables, we simulate the entire day using the predicted COST and CLK and check whether:

total spend ≤ budget;

average CPC ≤ upper bound;

average CPC ≥ lower bound.

If any condition is violated, the dual variables are adjusted (via binary search or gradient descent) and the simulation is repeated until all constraints are satisfied. Because the prediction model is lightweight, this iterative adjustment can be performed in seconds.

BiCB Algorithm

Future traffic prediction replaces the “time‑machine” required by offline LP.

Analytically derived optimal bidding formula from LP duality.

Online decision loop runs every few seconds (e.g., 10 s), far below the query‑per‑second rate of typical CTR models.

The algorithm therefore avoids explicit modeling of sparse, delayed conversion signals and relies only on well‑established CTR‑type predictors for COST and CLK.

Experimental Evaluation

Offline experiments compare BiCB against several baselines:

Offline LP (theoretical optimum with full traffic knowledge).

BiCB* (BiCB with perfect traffic prediction).

Manual Bidding (fixed bid).

Local PID controllers for each dual variable.

Online LP (fixed dual variables from offline solution).

IQL (offline reinforcement learning).

Decision Transformer (DT) based auto‑bidding.

Two scenarios are evaluated:

BCB – budget‑only constraint.

BiCB – budget plus CPC upper and lower bounds.

Results show that BiCB attains about 98 % of the offline LP optimum, while BiCB* nearly matches the optimum. Online deployment confirms that the dual variables remain almost constant throughout the day, indicating stable convergence.

Conclusion

BiCB extends the LP auto‑bidding framework with upper and lower bound constraints, derives a closed‑form optimal bidding rule via dual analysis, and couples it with a lightweight traffic‑prediction module. The resulting algorithm achieves near‑optimal performance with minimal computational overhead and has been fully deployed in a large‑scale live‑ad platform.