Towards Safe and Optimal Online Bidding: A Modular Look-ahead Lyapunov Framework
Hengquan Guo, Haobo Zhang, Junwei Pan, Shudong Huang, Nianhua Xie, Lei Xiao, Haijie Gu, Jie Jiang
Abstract
This paper studies online bidding subject to simultaneous budget and return-on-investment (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 (\mathcal{E}\_r(T,p)+(\nu^* / \rho) \mathcal{E}\_c(T,p))$ regret and $O (\mathcal{E}\_r(T,p)+\mathcal{E}\_c(T,p))$ anytime ROI constraint violation, where $\mathcal{E}_r(T,p)$ and $\mathcal{E}_c(T,p)$ are cumulative estimation errors over $T$ rounds, $\rho$ is the average per-round budget, and $\nu^*$ 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.
BibTeX
@inproceedings{
guo2026towards,
title={Towards Safe and Optimal Online Bidding: A Modular Look-ahead Lyapunov Framework},
author={Hengquan Guo and Haobo Zhang and Junwei Pan and Shudong Huang and Nianhua Xie and Lei Xiao and Haijie Gu and Jie Jiang and Xin Liu},
booktitle={The Fourteenth International Conference on Learning Representations},
year={2026},
url={https://openreview.net/forum?id=AtbRCnvcrZ}
}