Towards Safe and Optimal Online Bidding: A Modular Look-ahead Lyapunov Framework

This paper studies online bidding subject to simultaneous budget and return-oninvestment (ROI) constraints, which encodes the goal of balancing high volume and profitability. We formulate the problem as a general constrained online learning problem that can be applied to diverse bidding settings (e.g., first-price or second-price auctions) and feedback regimes (e.g., full or partial information), among others. We introduce L2FOB, a Look-ahead Lyapunov Framework for Online Bidding with strong empirical and theoretical performance. By combining optimistic reward and pessimistic cost estimation with the look-ahead virtual queue mechanism, L2FOB delivers safe and optimal bidding decisions. We provide adaptive guarantees: L2FOB achieves O Er pT, pq pν ˚ρqE c pT, pq ˘regret and O Er pT, pq Ec pT, pq ˘anytime ROI constraint violation, where E r pT, pq and E c pT, pq are cumulative estimation errors over T rounds, ρ is the average perround budget, and ν ˚is the offline optimal average reward. We instantiate L2FOB in several online bidding settings, demonstrating guarantees that match or improve upon the best-known results. These results are derived from the novel look-ahead design and Lyapunov stability analysis. Numerical experiments further validate our theoretical guarantees. ˚Equal contribution. : Corresponding author. Work done while Hengquan Guo was an intern at Tencent.