Towards Safe and Optimal Online Bidding: A Modular Look-ahead Lyapunov Framework
Authors: Hengquan Guo
Haobo Zhang
Junwei Pan
Shudong Huang
Nianhua Xie
Lei Xiao
Haijie Gu
Jie Jiang
Xin Liu
Venue: ICLR 2026 Poster (2026)
Keywords: online bidding
budget constraints
ROI constraints
Lyapunov optimization
Primary area: optimization

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.

Published as a conference paper at ICLR 2026
TOWARDS SAFE AND OPTIMAL ONLINE BIDDING: A MODULAR AHEAD LYAPUNOV FRAMEWORK
Hengquan HHaboo Zhang" " Junwei Pan Shudong Huang", Nianhua Xie?, Lei Xiao", Haijie Gu², Jie Jiang', Xin Liu" SIST, ShanghaiTech University, China, Tencent Inc., China (guohq, zhanght2023, l ( haanngaai wechh.hhaiieehh..eeee.... wew.teeh.....eeeeeee.eeee en, jenaspan@tencent.com
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 learn- ing 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 combin- ing optimistic reward and pessimistic cost estimation with the look-ahead virtual queue mechanism, L.FOBB delivers safe and optimal bidding decisions. We pro- vide adaptive guarantees: L2FOB achieves (E, p) + (r*/p)Ec(TTp)) regret and (T))) + P)) anytime ROI constraint violation, where (T, and (T. p) are cumulative estimation errors over rounds, P is the average per- round budget, and v* 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 derived from the novel look-ahead design and I Lyapunov stability analysis. Numerical experiments further validate our theoretical guarantees.
INTRODUCTION
Autobidding systems play an increasingly central role in the online advertising ecosystem, which channels hundreds of billions of dollars annually, continues to grow rapidly, and already accounts for the majority of total ad spend Aggarwal al. (2024); |cMarketer (2025). Operationally, significant portion of digital ad inventory is allocated through real-time auctions that clear in milliseconds at an Internet scale. Platforms run billions of these auctions daily, making bidding strategy design a criti- cal problem. Typically, an advertiser aims to maximize cumulative payoff over fixed horizon (e.g., a day or a week) while respecting both a limited budget and a target eeturn-o-innvestmen (ROI) that captures profitability requirements during the period. With both budget and ROI constraints, online bidding must balance volume (e.g., impressions/clicks) and profitability: spending too fast sacrifices late-stage opportunities, spending too slowly leaves inventory unused, and pursuing volume low ROI undermines profitability. This paper tackles this problem and presents a modular framework for safe and optimal online bidding under both budget and ROI constraints.
Most prior work studies online bidding under only budget constraints, where total expenditure is limited Balseiro & Gur (2019); Balseiro al. (2020): Chen et al. (2024): Wang al. (2023); Guo & Liu (025).. Budget constraints are comparatively easier to handle because costs are non-negative, so feasibility reduces to controlling one-sided cumulative resource. However, modern advertise- ment markets require profitability control Golrezaci et al. (2021b), introducing ROI constraints with both packing and covering property: per-step violations can be offiet over time, so long-horizon planning is essential. While Castiglioni et al. (2022) adopts an appropriate violation metric for ROI constraints, their analysis requires Slater's 's condition (existence of a strictly feasible policy). Such an assumption is difficult to certify for ROI constraints and incompatible with budget hard-stopping
Equal contribution. Corresponding author. Work done while Hengquan Guo was an intern Tencent.

---

Published as a conference paper at ICLR 2026
in many markets. In Castiglioni al. 2025), online bidding formulation incorporates both bud- get ROI constraints, but their metric counts the number of constraint violations rather than the amount of violation. As result, the proposed algorithm does not fully navigate the tradeoff between payoff and constraint violations. Moreover, existing approaches are tailored to specific environments and settings: for example, first-price or second-price auctions, bandits convex optimization, and full information or partial information. There is no unified framework that captures the practical online bidding paradigm, which leads to the following:
Can we design a unified, modular framework for safe and optimal online bidding under both budget and ROI constraints, with adaptive provable guarantees without Slater's condition?
In this paper, we propose L,FFOB (Look-ahead I Lyapunov Framework for Online Bidding), which provides a positive answer to this question. Our main contributions are follows:
Unified problem formulation. We formulate online bidding general constrained online learn- ing problem: an agent maximizes cumulative reward subject to budget and ROI constraints. Un- like prior work tied to specific auction models, present a unified framework by treating reward r(v, b) and cost c, b) as general functions of context v and bid 6. As long as general online re- gression oracles for reward and cost are provided, as is common in the literature Foster & Rakhlin (2020); Slivkins et al. (2023), our framework is applied to different bidding environments with adaptive theoretical guarantees, providing unified approach to online bidding.
Algorithm design. L2FOB builds upon primal dual methods for constrained online learning Yu & Neely (2020); (Slivkins et al.] (2023); Guo & Liu (2024), but adopts a Lyapunov perspective with look-ahead virtual queues and potential-shaped multipliers. To balance reward with budget and ROI constraints, L2FOB maintains two virtual queues, Op (budget) and Q, (ROI), which track real-time constraint satisfaction. Unlike these previous works where virtual queues directly accumulate violations, L2FOB only tracks "unsafe decisions" via the clip operator (-) yield- ing stricter safety and stronger guarantees. In the primal decision, rather than using fixed queue lengths, I,2FOB introduces look-ahead queues that predict the induced violation before acting, enabling more precise violation control. We adopt convex potential function to provide more flexible stability control. Together, these choices enable a modular framework with provably strong guarantees for online bidding optimization.
Theoretical guarantees. L2FOB provides general, strong, and adaptive theoretical guarantees: it achieves O (T, (v* p)) regret and (E, p) ET. anytime ROI violation, where E, (T, p) and p)) are the cumulative reward and cost estimation errors of the regression oracle, P is the average budget per round, and D* is the offline optimal average reward. These results are established with hard stopping due to budget constraints and without assuming Slater's condition, providing guarantees that are more applicable in practice. We instantiate the framework for first-price auctions with budget constraints and for second-pris pooondpiicceaae auctions with both budget and ROI constraints, derive tighter guarantees, and apply it to constrained contextual bandits to match the best-known results. Detailed instantiations and comparisons provided in Section We run experiments in corresponding settings and demonstrate superior performance. Full details appear in Appendix D
MODEL AND PRELIMINARIES
In this section, we formalize the general paradigm of online bidding under budget and return-on- investment (ROI) constraints and introduce the associated performance metrics.
Safe Online Bidding under Constraints. In this work, we study online auctions from the perspec- tive of a single bidder interacting with a large population over T rounds. In each round t, the bidder observes a context 2 E X drawn from a known distribution, submits a bid by E R+, and receives stochastic feedback r, r(v,, b.) + Ca c(ve, b.) + Ef; where the unknown reward function and cost function are r(v,, by) e [o, Rmaxx and c(v,, by) e [o, Cmax]. ef fr.e) denote random noise terms.
To keep the formulation modular and widely applicable, we deliberately leave the forms of the context, reward, and cost unspecified. For example, the context could be the private value of the bidder and the reward is r(v,, b.) I(b, > de) - bz), where d, is the highest competing bid,
2

---

Published as a conference paper at ICLR 2026
under first-price payments the cost is c(v), b,) Ilb de)bt. Our framework also covers settings where i/ encodes predictive features such as pCTR (predicted click throkghh rate) / pCVR (predicted conversion rate), in which case the reward and cost can be user-specified functions, thereby unifying a broad class of online bidding models within a single problem formulation. For each round E [7], the objective is choose bidding decisions that maximize cumulative expected revenue while ensuring the return- cetuu--on-investen (ROI) remains at least and the daily spend stays within a budget cap B. Formally, we consider the following constrained optimization problem:
T
I18X Σ
r(v,, be) s.t. Σ
dur, be) & B, Σ r(ve, be) 3
Σ cccr,br)
(1)
Assumptions and Baselines. We first introduce some basic notations and definitions. The optimal bid action 6* is defined the solution to the following offline problem:
max E [r(v, b)] s.t. E [c(v, b)] & p. E[r(v, b)] > [E[c
b
Let y* == Elr b*]] denote the optimal expected reward, T ] T denote the stopping time at which the budget is exhausted under algorithm, i.c.
argmin r'E[T]
cler, (e).bb) B
(3)
t=1
The regret of algorithm over horizon T is defined as
Regret(T) Tv* E
r(ve, bi)
(4)
where } denotes the bidding sequence of the decision maker.
While the bidding rule guarantees the budget constraint, we assess compliance with the ROI con- straint via the following stronger anytime violation measures:
(toi(t) E
Σ c((ss,b)
Σ r(vs by)
(5)
To establish a unified framework for the safe online bidding problem in diverse settings, we introduce the following general online regression oracle assumption.
Assumption There exist online learning oracles {O)r, such that the reward and cost estimators Fe b) and cx b) satisfy the following conditions with a high probability of at least p:
[F( r(v, < <[()),
(a( c(c, E((p), ve X. Ret (T
where define the general cumulative error as (T, Einee and (T(T, ΣL (pp).
Our oracle assumption is mild and encompasses standard optimistic regression oracles. Classical op- timism in the face of uncertainty designs already satisfy it et al. (2010); Foster al. 2018 Fos-
Ter & Rakhlin (2020); for constrained online learning/bidding, the estimators in Guo & Liu 2025);
Wang et al. (2023); Vijayan et al. (202)); Castiglioni et al.] (2025) also satisfy it. Richer function
classes can also be accommodated by building confidence bounds via neural random features as in
Zhou et al. (020). Although the realized estimation error does depend on the data distribution
duced by the policy, the oracle error bounds are uniform over all action selection rules satisfying the
boundedness and noise conditions. Hence, these bounds are effectively independent the specific sampling strategy.
Under Assumption [ we can construct optimistic and pessimistic plug-in estimators as follows:
fr b) = Fr b) + of
(optimistic upper confidence bound reward),
bvv = C.v,b) b) of (pessimistic lower confidence bound cost).
On the higb-brobabilltty event w (which occurs with probability least 1 p), the following results hold simultancously for all (v, b) and all t E [T]]
0 & (2 r(v. b) & 20, 0 a c(u,b) (v, b) $ 26ç.

---

Published as a conference paper at ICLR 2026
3 SAFE ONLINE BIDDING ALGORITHM
We propose L2FOB (Look-ahead Lyapunov Framework for Online Bidding), a modular, safe, and optimal online bidding framework under budget and ROI constraints. Our framework leverages online regression oracles to produce optimistic reward and pessimistic cost estimates. To enforce the constraints, L2FOB maintains two virtual queues, Qp and Qy, to track budget and ROI feasibility, and uses the convex potential function (()) to guarantee safety. At the core is a look-ahead virtual- queue mechanism that incorporates predicted one-step constraint violations
refine the reward- constraint tradeoff. Prior works require Slater's condition for ROI constraints, namely, the existence of strictly feasible margin E ((r, 6)] > y H[c(v. b)] + f. E > 0, which means the ROI target has slack. The designs of L2FOB allow us to provide provable safe and optimal guarantees without Slater's condition.
Algorithm Look-ahead I. Lyapunov Framework for Online Bidding (L22FBB
Require: Convex potential ( (-)2: initial estimators (n(),)) and è (:5,,, virtual queues (0) = (0) = 0 and Thp = 17y T.
for 1 to T do
2: Observe: bidding opportunity with context er from the learning oracles.
3: Construct estimators: +x(--) and e,(:-)).
4: Look-ahead virtual queue updates: for any b >0 O.
Qp(t, b) = Q, - no (E, 6)] - p)*
(6)
b), = Q, 1) 1) (1.uréda - fr(e, b))+
(7)
5: Bid action: choose by as maximizer of
Ae(ve, b) (Qp(t b) (Er - ((0
(8)
6: Submit bid b,: observe reward rt and cost ct.
7:
Virtual queue updates:
Qx(1) = (t -
0) 1) 1)) + n, (E. bb) bb))+
(9)
(t) = (t
(10)
8: Estimators update: update f( and ē
9: Stopping rule: E c(v,, b.) > B then break.
10:
end for
Lhok-Ahead Virtual Queue Tracing. The key design that distinguishes 1.2FOB from prior work is the look-ahead virtual queue tracing. While [Slivkins et al. (2023); Han et al. (2023); Guo & Liu (2024) 2025) update dual variables only after observing cost feedback, L2FOB computes look-ahead virtual queues for each candidate bid before the decision. The queues act as dynamic pacing variables that modulate exploration and conservatism. By incorporat- ing predicted violations into the queues, L2FOB internalizes feasibility at decision time rather than merely tracking the past, yielding more precise safety control. L2FOB passes the queues through a convex potential function ((.) and uses its derivative the time-varying multipliers Ap(t) == (', b)), (t) == 4' ('QQ, b)). The choice of Lyapunov function is often re- garded as more of an art than strict technique, with different designs yielding different analytical outcomes. For example, ((x) is set to be ex in Sinha & Vaze (2024) to achieve the best-known results constrained online convex optimization.
this paper, we show that the classical choice ((x) = 2 is sufficient; however, we retain a tunable design to enable L2FOB to flexibly control constraint violations.
Safe Online Bidding Decision. Given context v, and the optimistic and pessimistic estimators. L2FOB selects b, e R by greedily maximizing the surrogate objective in (8) This resembles a dul step where the primal module maximizes approximate Lagrangian
I(ve, b) r(v,, b) (t) (c(o,, b) p) (x((( b) r(c. b)),
with (t) and (t) denoting the offline optimal dual variables. However, L2FOB has the fol- lowing key differences: First, we apply the clip (.) that penalties activate only when the
4

---

Published as a conference paper at ICLR 2026
estimated constraints violated, which lets the algorithm focus reward maximization when constraints appear satisfied and supports a more flexible penalty design. Second, L2FOB enforces constraints in mean-field fashion, where E. denotes expectation over the context marginal. This focuses the penalty on systematic risk rather than per-context noise and yields smoother safety control. Moreover, the dual approximators utilize a convex potential ((-) in conjunction with a look-ahead virtual queue mechanism, which enhances violation detection and mitigates overly aggressive updates. Unlike Guo & Liu (2025); Wang al. (2023) Castiglioni al. (2025), which are tailored to specific problem environments and settings, L2FOB adapts broadly through
the general online regression oracle assumption.
In summary, L2FOB is modular framework that combines general optimistic and pessimistic esti- mation with look-ahead virtual queue tracing and potential-shaped multipliers. It can apply to vari- ous bidding environments by applying dedicated online regression oracles. The look-ahead design is indeed closely related in spirit to one-step model predictive control, where a Lyapunov function is used a surrogate for long-term performance, and the controller chooses the current action by greedily optimizing one-step prediction that combines immediate reward/cost with the change in this function Rawlings al. (2020). The key difference is that the "state" of our Lyapunov function is given by virtual queues that track constraints rather than the plant state.
4 MAIN RESULTS AND PROOF SKETCH
In this section, we first provide the regret and violation guarantee of the L2FOB algorithm in the following main theorem.
Theorem Under Assumption
7 the L2FOB framework achieves
Regret = (T,)) v** EdT...)
= ((E Wi [T].
To our knowledge, Theorem T the first adaptive guarantees on both regret and ROI violation for safe online bidding. The bounds scale with the oracle errors (T, and (T, Moreover, we provide a stronger anytime ROI violation that guarantees safety over the whole time horizon. Theorem I shows that any learning procedure satisfying Assumption [] can be plugged into the framework. In Section 5] we instantiate Theorem in the settings of Wang et al. (2023), Castiglioni et al. (2025) and Guo et al. (2025), demonstrating how the framework adapts to these environ- ments. In the settings considered by WWang et al.] (2023); (Castiglioni et al. (2025). we show that L2FOB achieves improved theoretical guarantees via Theorem [ In the constrained bandit setting of'Guo et al. (2025), our results match the best-known guarantees and can be further tightened given sufficiently accurate learning oracles.
Remark While we do not provide strict zemo-voolation guarantee, all these results are obtained without assuming Slater's condition, which makes them more generally applicable. When Slater's condition does hold, strict zero-violation guarantee can be enforced by solving tightened problem with a safety margin (e.g., replacing "y with + ö for some >> 0), as in Liu et al. (2021), : Castiggioon et al. 20255) Even without such tightening, our method already achieves low constraint violation as established in the proofs
by controlling the stricter metric E
- -- (EEu,, b.) r(v,b,))) ]
in Section
4.1 PROOF OF THEOREM
In this section, we provide proof sketch of Theorem I a detailed version can be found in Appendix
We first present the following key lemma, which provides unified bound on regret and Lyapunov drift and serves as the key for proving Theorem
Let by be the bidding action of the 12FOB algorithm, then for any bidding action b, the following inequality holdy
Lemma
fr,,, b) Fr(,,, + -0000000------00----00--00000000
< hrgp://hff4.aka000oooo/r////044n fr(,,,)))
5

---

Published as a conference paper at ICLR 2026
We use convex potential function ((-) to provide more flexible control of the virtual queues. We adopt the most common quadratic function ((xx) = x² but allow it to be tunable to provide more flexible violation control. This design, together with the rectified constraint and the look-ahead virtual queues, yields the following lemma, which removes the need for Slater's 's condition (existence of strictly feasible solution) assumed in [Slivkins et al.] (023) Guo & Liu (2024 2025). Note that Guo et al. (2025) circumvents Slater's ' condition through a mean-field approach that leverages the context distribution, but it focuses on contextual bandits with a single constraint. Through the above key lemma, we then derive the Lyapunov stability of L2FOB.
Lyapunov Stability, Lyapunov drift analysis has long been used certify the stability of control policies in networking and operations research Hajek (1982); |Eyilmaaz & Srikant (2012), where stability is enforced by controlling queue lengths. In our setting, we leverage virtual queues to track the constraint violation over time. We adopt this perspective by modeling the budget and ROI constraints with the virtual queues Qp and Q,, which can be viewed as stochastic/Markovinn processes. The following lemma, derived from Lemma I formalizes this stability property of virtual queues and provides an explicit bound on the virtual queues.
Lemma 2 Under the L2FOB algorithmm, the following inequality holds for any e [T],
The lemma implies stability of the budget and ROI constraints under L2FOB over the whole horizon T. Based on it, we can now derive the corresponding regret and anytime ROI violation guarantees.
Constraint Violation. We begin with simple observation. The relationship between queue lengths and cumulative violation follows directly from the update rules in ( and 110..
Up [(E,CG(e,bo) p)* (T()), thy Σ (1, fa b,)))
Q+(1,, (11)
To derive a guarantee on ROI violation, we employ the following decomposition, which decouples the anytime violation into oracle estimation error terms and estimated violation.
E
Σ yu ba) ba)
<
(F.()c(1,bb)) - b(),+
E
(E, b.) b.)),
+ +E((T.p))7E.(T...
< ((),(0)) + (T,)) (T,
Finally, applying Lemma to bound the expected queue lengths yields the violation bound in The- orem Then, we provide the proof of regret bound.
Regret (before stopping and after stopping): We begin by introducing the decomposition of regret in (4) which separates the decision process into the reward gap before stopping and after stopping.
Regret(T) =
Σ r(u,, b+)
Σ r(u,, bt)
-E[T-r]
(r(v,, b*) - r(v,, (01,,,,)) bz))
Regrot after stopping
Regret before stopping
For regret before stopping, we apply Lemma with b = b*, rearrange the terms, sum the resulting inequality up the stopping time T, and take expectations, which yields
E
(r(vi,b") -
E
((Q,(()"))),n,BBlbl... p)+
+ E
The following lemma, which provides an upper bound on the cross terms, completes the proof of the regret bound after stopping.

---

Published as a conference paper at ICLR 2026
Lemma 3 Let b* be the optimal solution (2) then the following results hold that,
E
"'0,((00"))n,,BCllc... ,)*
& 2n G Cooza = =(1),
I0
(', (B, - -r((u,b)))) & 21 m
For regret after stopping, we first recall the definition of stopping time 7 that is 7
argmin { ا c(ur, bi) e B}. which gives
-'E[T]
Σ (a(., b.) - p) + + Σ be) (e(ue,be)) 30 B,
Taking the expectation and rearranging the inequality, we have
E E - r] - - Tp]
(c)(vr,b)) - p)+ Σ (o(1),b))-((vp
< -
Σ (B. p) + Ed(,Tp)
<
E
Combining with the fact in we complete the proof of Theorem 1
5 INSTANTIATIONS OF THE MODULAR ALGORITHM: SETTINGS, RESULTS, AND COMPARISONS
In this section, instantiate L2FOB in several online bidding environments and learning models, specify the oracle choices and their cumulative errors, and derive regret and violation bounds via Theorem T For first-price auctions in |aang et al. (2023), using the same empirical estimators, obtain a regret bound ( + n²/ ///pp/))///////))//)) //p//T)) improving their result by factor of l/p. Note that Wang itt al. (2023) does not incorporate ROI constraints. For second-pric -price auctions under the uncertantty problem in Castiglioni et al. (2025), while they do not provide an ROI violation metrie, instantiat- ing their estimators within L2FOB yields sublinear regret and sublinear violation, and our analysis explicitly considers hard-stopping in the regret, which theirs does not. For constrained contextual bandits Guo et al. (2025), which deliver state-of-the-art guarantees without Slater's 's condition, adopt- ing the same learning oracles allows L2FOB to match their guarantees. Moreover, when stronger estimators available, our framework can provide refined regret and violation bounds, whereas their algorithm cannot. Note that across all these settings, our results provide an anytime guarantee on ROI violation, whereas prior studies state guarantees only at the terminal horizon T.
5.1 FIRST-PRICE AUCTION UNDER BUDGET CONSTRAINTS
We consider the same setting as Wang et al. (203)), where single advertiser participates in repeated first-price auctions over rounds with a total spend budget Tp. In round the bidder has private value v E [0, Um submits a bid 6 R* faces the highest competing bid d,, and wins iff by 3 d. Let Jt = I(b, 2 de). Then the reward and cost functions are
re( b,) = 2z(U2 - be), celve, be) 2gbbe
and the process stops when the budget is exhausted (or at T), i.e. feasibility requires DT_ ((r,, by) & B for the stopping time & T. Equivalently, the expected reward and cost (conditioning on d, only) can be written via the win probability G(b) = Pr(d, & b) as
b(u,b) = (v - Gb),,, c(v, b) = bG(b).
In Wang et al. (2023), the first-price-with-bee models inherently satisfy Assumption [ When the platform reveals d, after each round, estimate the win CDF by the empirical CDF G.(b)

---

Published as a conference paper at ICLR 2026
Ex I(dg < b) and use
Fe(u, b) (v (b) b(v,b) bG.(6).
Uniform concentration then yields high-probabilityy oracle error bounds Et Eg ensuring that As- sumption I holld. Specifically, we have
(T. O (1 Tmm ET(T.P) = ( Tmn
Plugging the above cumulative learning error into Theorem L.2FOB achieves Õ((1 + u* /p)VT) regret and Õ (V) anytime ROI violation, where (-)) hides logarithmic factors in T.
Remark 2 Our guarantee substantially improves over Wang et al. (2023) Although they report Ö(VT) regret, the dependences on and v* are hidden, and the exact bound is Ó (1+v*//a /²²)//) (see Appendix B.3 of Wang al. (2023)) Consequently, their result is meaningful only in the large budget regime B = Tp (T)), ), since v²1 /²/p² grows without bound as the budget shrinks. In contrast, our bound scales as Ó(( + v* (p)VT) and remains informative under small budgets B ((VT). Moreover, WWan al. (203)) only considers budget constraints, whereas L2FOB handles both budgel and ROT constraints and provides explicil guarantees on regret and on the cumulative amount of violation. For budget constraints, Slater's condition typically holds because the bidder can choose a null (zero-spend) action; nevertheless, L2FOB does not require it, enabling harder settings in which every bid incurs positive cost or minimun spend is mandated.
5.2 BIDDING UNDER UNCERTAINTY WITH BUDGET AND ROI CONSTRAINTS
We adopt the setting of Castiglioni et al. 2025), which emphasizes uncertainty in online bidding: the revenue and cost of advertising campaigns are unknown and must be learned online from sequential data. An advertiser manages N subcampaigns over T rounds. In round f, a bid Zj,t X, R+ chosen for each subcampaign Cj. yielding expected clicks (zy(23,) and expected cost (T(,)))-
With per-click values vy. the round-/ expected revenue is Σド= uy (ag,e). Then the per-round optimization problem is
N Σ
DW 1y-1o,y(3sh
N
max (
(z))) s.t. Σ,-1
7.
Σ cg(()))) <p.
Within a round, each subcampaign's bid is fixed, but bids may be updated across rounds. Set the action to be the vector b, := Ia and define
N
r(u, bi) Σ (ben) bl) Σ (b(o)))
This embeds the multi-subcampaiin problem directly into our constrained online learning formu- lation, and it satisfies our regression-orach assumption by plugging in the estimators for n. and (.))) Following Castiglioni et al. (2025). model n.)(-) and cz(-) with independent Gaussian pro- cesses and use UCB/LCB envelopes. Let a (x) and ( be posterior standard deviations and "/ the usual GP-UCB confidence schedule. Then the oracle errors can be taken
(x)
of =
of 0(
Then, by standard Gaussian process concentration results Srinivas et al. (2009); Krause & Ong (2011); Kim & Sanz-Alonso (2025) and following the derivation in Castiglioni al. (2025), obtain
(T(T 0(1 T 1r>n.a ..)) (TTT)))
T
Σ
75.
j=1
where 7irr is the GP information gain for subcampaign j. Instantiating L2FOB with the GP-UCB oracles and applying Theorem Nyields
Regret(T) = = #0) TEN
T BaT). VROI(() (ao(()=o(VT)))) T..)). Vie [T].
8

---

Published as a conference paper at ICLR 2026
In this setting, L2FOB is, the best of our knowledge, the first method attain optimal- order regret together with ROI violation guarantees. By contrast, Castiglion et al. (2025) quantifies safety by the number of violating rounds. Their analysis implies that achieving sublinear regret entaily (T) violating rounds under this count-based metric, and their regrel analysis does not ac- count for budget-induced hard-stopping. Counting violations is improper for online bidding, where pacing can recycle unspent budget and small, controlled per-round violations can be offset later. L2FOB instead measures and controls the cumulative ROI violation and explicitly models the hard- stopping induced by the budget, yielding guarantees that are stronger in theory and better aligned with practice than Castiglioni et al. (2025). Moreover, L2FOB can leverage recent advances in Bayesian optimization analysis Twazaki & Takeno 2025 to lighten orucle errors, further improving regret and violation bounds.
Remark 3
5.3 CONSTRAINED CONTEXTUAL BANDITS FOR BIDDING
We next study the constrained contextual bandit formulation for online bidding in Guo et al. 2025 Contextual bandits fit our framework naturally: the bid can be modeled as a discrete action b, E A or as policy mapping contexts actions. The reward and cost are unknown, context-dependent func- tions that must be learned online from noisy bandit feedback. They made a similar assumption on learning oracle errors, which gives & (T', p) Ö(VT), EC = Ö(VT). Instantiating L2FOB with these oracles and applying Theorem gives
(T) = Ō(1 + +=***** /p)VT), VROI(t) - (aant)-ō(vT)) vt E [T].
Our results match the best-known guarantees for constrained contextual bandits, as established by Guo et al.] (2025). Their approach also requires prior knowledge of the context distribution to en- force constraints in mean-field manner. However, although Guo et al.] (2025) considers general constraints, it does not explicitly handle multiple simultaneous constraints, so its applicability to online bidding with both budget and ROI constraints unclear. L2FOB offers anytime control of violations, thereby covering the metric VROI(T) in Guo al. (025).. Moreover, results modular and adaptive, depending explicitly on oracle errors, which enables refined guarantees as highlighted in the remark below.
Remark (Bridging the gap.) The regret lower bound for non-contextual bandits with budget con- straints is proved to be S((TTv= + (v* /p) /P) in Badanidiyuru al. (2018). For contextual ban- dits with budget constraints, the best-known guarantee is O((1+ + v² /)) T) as shown in Guo et al. (2025), which leaves a gap between contextual and non-contextual settings. If one could design Ö(VTv"), Ex(T.p) Ö(VB). then Theorem 1 would yield RTgret(T)) = O(VTV* + (v* (P)BB,, which matches the non-contextual lower bound. This hy- pothesis is plausible because these error bounds hold in the non-contextual case Badanidiyuru et al.) (2018). At present, is unclear how to attain such adaptive learning oracles contextual settings. Even if such oracles were available, the methods of Guo & Liu (2025): : Guo al. (2025) would still not reach this bound because their dual updates made hard to introduce a flexible choice of na-
learning oracles with (T,
which our look-ahead design enables.
CONCLUSION
In this paper, we study safe online bidding under budget and refurn-on-investmenn (ROT) constraints, where the budget imposes a hard stopping condition and the ROI enforces a long-run profitability threshold. We introduced L2FOB, Look-ahead Lyapunov Framework for Online Bidding that pairs optimistic/psssiiitic estimators with look-ahead virtual queue penalties and yields adaptive bounds on regret and cumulative violation without requiring Slater's condition. Our algorithm pro- vides a modular, safe, and optimal framework. We instantiate L2FOB in several online bidding environments and show that the resulting guarantees match or improve the knotn results. The experiments further validate the theoretical results.

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This work was supported by the National Natural Science Foundation of China under Grant 62302305.
REFERENCES
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. International Conference on Machine Learning, pp. 1638-1646. PMLR, 2014.
Gagan Aggarwal, Ashwinkumar Badanidiyuru, Santiago R Balseiro, Kshipra Bhawalkar, Yuan Deng, Zhe Feng, Gagan Goel, Christopher Liaw, Haihao Lu, Mohammad Mahdian, et al. Auto- bidding and auctions in online advertising: A survey, ACM SIGecom Exchanges, 22(1):159-183, 2024.
Shipra Agrawal and Nikhil Devanur, Linear contextual bandits with knapsacks. Advances Neural Information Processing Systems, 29, 2016.
Shipra Agrawal and Nikhil R Devanur. Bandits with concave rewards and convex knapsacks. In Pro- ceedings of the fifteenth ACM conference on Economics and computation, pp. 189-1006, 2014.
Ashwinkumar Badanidiyuru. John Langford, and Alcksandrs Slivkins. Resourceful contextual ban- dits. In Conference on Learning Theory, pp. 100--1134. PMLR, 2014.
Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knapsacks. Journal of the ACM (JACM), 65(3):1-55, 2018.
Ashwinkumar Badanidiyuru, Zhe Feng, and Guru Guruganesh. Learning bid in contextual first price auctions. In Proceedings of the ACM Web Conference 2023, pp. 3489-3497, 2023.
Santiago Balseiro, Negin Golrezaci, Mohammad Mahdian, Vahab Mirrokni, and Jon Schneider. Contextual bandits with cross-learning. Advances in Neural Information Processing Systems, 32, 2019.
Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. Dual mirror descent for online allocation prob- lems. In International Conference on Machine Learning, pp. 613-628. PMLR, 2020.
Santiago R Balseiro and Yonatan Gur. Learning in repeated auctions with budgets: Regret mini- mization and equilibrium. Management Science, 65(9):3952-35) -3668, 2019.
Santiago R Balseiro, Haihao Lu, and Vahab Mirrokni. The best of many worlds:: Dual mirror descent for online allocation problems. Operations Research, 11(1):101-119, 2023.
Dimitris Bertsimas, David Gamarnik, and John N Tsitsiklis. Performance of multiclass markovian queueing networks via piecewise linear Yyapunov functions. Annals of Applied Probabilit, pp- 1384-1428, 2001.
Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Giulia Romano, and Nicola Gatti. unifying framework for online optimization with long-term constraints. Advances in Neural Information Processing Systems, 35:33589-33602, 2022.
Matteo Castiglioni, Andrea Celli, and Christian Kroer. Online learning under budget and roi con- straints via weak adaptivity. In International Conference on Machine Learning, pp. 5792-5816.
PMLR, 2024.
Matteo Castiglioni, Alessandro Nuara, Giulia Romano, Giorgio Spadaro, Francesco Trovò, and Nicola Gatti. Safe online bid optimization with return investment and budget constraints. In Proceedings of the 3/st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 1, pp. 73-81, 2025.
Zhaohua Chen, Chang Wang. Qian Wang, Yugi Pan, Zhuming Shi, Zheng Cai. Yukun Ren, Zhi- hua Zhu, and Xiaotie Deng. Dynamic budget throttling in repeated second second-price auctions. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pp. 9598-9606, 2024.
10

---

Published as a conference paper at ICLR 2026
Evgenii Chzhen, Christophe Giraud, Zhen Li, and Gilles Stoltz. Small total-cost constraints in contextual bandits with knapsacks, with application to fairness. Advances in Neural Information Processing Systems, 36, 2024.
Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis,, John Langford, Lev Reyzin, and Tong Zhang. Efficient optimal learning for contextual bandits. In Proceedings of the Twenty- Seventh Conference on Uncertainty in Artificial Intelligence, pp. 169-178. AUAI Press, 2011.
ISBN 9780974903972.
eMarketer. Worldwide ad spending forecast 2025, 2025. URL https: www. emarketer: com/ conttett/oooowwwie-aaaaaaa
forecast-202. Accessed
Atilla Eryilmaz and R Srikant. Asymptotically tight steady-state queue length bounds implied by drift conditions. Queueing Systems: Theory and Applications, 72(3-4):311335, 2012.
Zhe Feng, Swati Padmanabhan, and Di Wang. Online bidding algorithms for return-on-spend con- strained advertisers. In Proceedings of the ACM Web Conference 2023, pp. 3550-3560, 2023.
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning. pp. 3199-3211 PMLR, 2020.
Dylan Foster, Alekh Agarwal, Miroslav Dudík, Haipeng Luo, and Robert Schapire. Practical con- textual bandits with regression oracles. In International Conference on Machine Learning, pp. 1539-1548. PMLR, 2018.
Negin Golrezaei, Patrick Jaillet, Jason Cheuk Nam Liang, and Vahab Mirrokni. Bidding and pricing in budget and roi constrained markets. arXiv preprint arXiv:2107.07725, 8(8.1):3, 2021a.
Negin Golrezaei, Ilan Lobel, and Renato Paes Leme. Auction design for roi-constrained buyers. In Proceedings of the Web Conference 2021, pp. 3941-3952, 2021b.
Hengquan Guo and Xin Liu. Stochastic constrained contextual bandits via lyapunov optimization based estimation to decision framework. In The Thirty Seventh Annual Conference on Learning Theory, pp. 2204 2231, PMLR, 2024.
Hengquan Guo and Xin Liu. On stochastic contextual bandits with knapsacks in small budget regime. In Proceedings of the International Conference Learning Representations, 2025.
Hengquan Guo, Lingkai Zu, and Xin Liu. Triple-optimistic learning for stochastic contextual bandits with general constraints. In International conference on machine learning. PMLR, 2025,
Bruce Hajek. Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied probability, 14(3):502-525, 1982.
Yanjun Han, Tsachy Weissman, and Zhengyuan Zhou. Optimal no-regret learning in repeated first- price auctions. Operations Research, 73(1 73(1):00,,238, 2025.
Yuxuan Han, Jialin Zeng, Yang Wang. Yang Xiang, and Jiheng Zhang. Optimal contextual bandits with knapsacks under realizability via regression oracles. In International Conference on Artificial Intelligence and Statistics, pp. 5011-5035. PMLR, 2023.
Shogo Iwazaki and Shion Takeno. Improved regret analysis in gaussian process bandits: Optimal- ity for noiseless reward, rkhs norm, and non-stationary variance. In Forty-second International Conference on Machine Learning, 2025.
Hwanwoo Kim and Daniel Sanz-Alonso. Enhancing gaussian process surrogates for optimization and posterior approximation via random exploration. SIAM/ASA Journal on Uncertainty Quan- tification, 1054-10044100 2025.
Andreas Krause and Cheng Ong. Contextual gaussian process bandit optimization. In J. Shawe- Taylor, R. Zemel, P. Bartlett, F. Percira, and K.Q. Weinberger (eds.), Advances in Neural Infor- mation Processing Systems, volume 24, Curran Associates, Inc., 2011.

---

Published as a conference paper at ICLR 2026
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual tandextual-anddit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661-670, 2010.
Xin Liu, Bin Li, Pengyi Shi, and Lei Ying. An efficient pessimistic-opiimisti algorithm for stochas- tic linear bandits with general constraints. Advances in Neural Information Processing Systems, 34:24075-24005 2021.
Brendan Lucier, Sarath Pattathil, Aleksandrs Slivkins, and Mengxiao Zhang. Autobidders with budget and roi constraints; Efficiency, regret, and pacing dynamics. In The Thirty Seventh Annual Conference on Learning Theory, pp. 3642-3643. PMLR, 2024.
Michael Neely, Stochastic network optimization with application to communication and queueing systems. Springer Nature, 2022.
Tao Qin and Yan Liu. Introducing letor 4.0 datasets. arXiv preprint arXiv: 2013.
James Blake Rawlings, David Mayne. Moritz Diehl, al. Model predictive control: theory, computation, and design, volume 2. Nob Hill Publishing Madison, WI, 2020.
David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 47(3):1904- 2022.
Abhishek Sinha and Rahul Vaze. Optimal algorithms for online convex optimization with adversarial constraints. Advances in Neural Information Processing Systems, 777441274-41302 2024.
Vidyashankar Sivakumar, Shiliang Zuo, and Arindam Banerjee. Smoothed adversarial linear con- textual bandits with knapsacks. In International Conference Machine Learning, pp. 20253- 20277. PMLR, 2022.
Aleksandrs Slivkins, Karthik Abinav Sankararaman, and Dylan J. Foster. Contextual bandits with packing and covering constraints: modular lagrangian approach via regression. Annual Conference Computational Learning Theory, 2023.
Rayadurgam Srikant and Lei Ying. Communication networks: An optimization, control and stochas- tic networks perspective. Cambridge University Press, 2014.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian pro- cess optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995, 2009.
Liang Tang, Yexi Jiang, Lei Li, and Tao Li. Ensemble contextual bandits for personalized recom- mendation. Proceedings of the 8th ACM Conference on Recommender Systems, pp. 73-80, 2014.
Leandros Tassiulas and Anthony Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput multihop radio networks. IEEE TRANSAC- TIONS ON AUTOMATIC CONTROL, 31(2)). 1992.
Rahul Vaze and Abhishek Sinha. Online bidding algorithms with strict return spend (ros) straint. CORR, 2025.
Sushant Vijayan, Zhe Feng, Swati Padmanabhan, Karthikeyan Shanmugam, Arun Suggala, and Di Wang. Online bidding under ros constraints without knowing the value. In Proceedings of the ACM on Web Conference 2025, pp. 3096-3107, 2025.
Qian Wang, Zongjun Yang, Xiaotie Deng, and Yuqing Kong. Learning to bid in repeated first-price auctions with budgets. In International Conference on Machine Learning, pp. 36494-36513. PMLR, 2023.
Huasen Wu, Rayadurgam Srikant, Xin Liu, and Chong Jiang. Algorithms with logarithmic sublin- ear regret for constrained contextual bandits. Advances in Neural Information Processing Systems, 28, 2015.
12

---

Published as a conference paper at ICLR 2026
Hao Yu and Michael J Neely. A low complexity algorithm with of (VT) regret and o(1) constraint violations for online convex optimization with long term constraints. The Journal of Machine Learning Research, 21(1):1-24, 2020.
Wei Zhang, Yanjun Han, Zhengyuan Zhou, Aaron Flores, and Tsachy Weissman. Leveraging the hints: Adaptive bidding in repeated first-price auctions. Advances in Neural Information Process- ing Systems,
2022.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with baseb exploration. In International conference machine learning, pp. 11492-1 1502. PMLR, 2020.
13

---

Published as a conference paper at ICLR 2026
A RELATED WORKS
Learning in repeated auctions with constraints has been studied across auction formats, feedback regimes, and safety notions. For first-price auctions with single advertiser and a hard budget, Wang et al. (023)) propose primal dual methods with ((vT) regret under both full-information and one-sided feedback; In Tang et al. (2014); Balseiro et al. 2020 2023), second-price auctions with budget constraints is also considered, where TTng et al. (2014) claims their results holds under large budget regime; [Baaanidiyuru et al.] (202)) study first-price auction while focusing on the linear model setting; with only binary win/loss signals, Balseiro al. (2019) employ cross-learning to obtain Ö(T2)3) regret, and Zhang et al. (2022) exploit side information "hints" about the maximum competing bid. In Han et al. (2025). they leverage graph- feedbbak and partial partial-order order structure in first-price markets to attain optimal regret rates. Feng al. (2023); Golrezaei et al (2021a) studied second-price price auctions with budget and return- ceturn-on-speen on-spend (RoS) constraints and Vaze & Sinha (2025) considered the case with only RoS constraints. [Castiglioni et al.] (2025) study budget and ROI constrained bidding under full uncertainty via Bayesian optimization. Their safety metric counts violating rounds rather than measuring cumulative violations. CCstigliooi et al.] (2024) studies a general online learning problem with both budget and ROI constraints, but in setting without context. They do not require prior knowledge of the Slater constant, although they still assume that Slater condition holds. Vijayan et al.) (2025) also adopts UCB/LCB style estimators design algorithms and establishes O(VT)) regret and violation bounds under budget and RoS constraints. However, they do not consider hard stopping upon budget exhaustion and focus on a bandit-only setting. To avoid assuming Slater's condition, their algorithm solves linear program each round, which introduces additional computational overhead. There are also works on multi-agent bidding dynamics Balseiro & Gur (2019); Lucier et al. (2024), which analyze equilibria and regret; this line differs from our single-advertis
Tocus. Despite this progress, there is no single framework that uniformly handles general reward/cost models, heterogeneous feedback, and simultaneous budget and ROI constraints with amount- based safety guarantees. Moreover, analyses focused on budget constraints often suppress the dependence on the average spend rate p = B/T, obscuring behavior in amall-budget regimes common in practice.
Another parallel line of work studies contextual bandits (CB) with constraints. Early CB algo- rithms relied on classification oracles Dudik et al.] (201T); Agarwal et al. (2014), whereas later work developed regression oracle methods Foster et al. (2018); Foster & Rakhlin (2020); Simchi- Levi & Xu 2022) that are more computationally practical and broadly applicable. Our oracle as- sumption subsumes these regression- based designs but is more general: we allow arbitrary function classes and plug-in estimators (including, but not limited to, contextual bandit regressors). Within constrained CB, much attention has focused on knapsack (budget) constraints (Badanidiyuru et al. (2014); y: AArawal & Devanur (2014); Wu et al. (2015) ; Agrawal & Devanur (2016); [Badanidiyuru ctt al. (0188); Sivakumar et al. (2022); Chzhen et al. (2024) Guo & Liu (002)). For linear models under Slater's condition, optimal guarantees of O(1 E* ())T) have been established Agrawal & Devanur (2016) and be further extended to general function class in Guo & Liu (202)). ) but these results address only budget control, whereas practical bidding must also enforce profttaiiiity (ROI). Long-run constraints with cumulative-violatio metrics were studied in Slivkinsss et al. (2023), which achieved ((vT/5) regret and violation under Slater's condition. Subsequent work Guo & Liu 2024 Guo et al. (2025) tried to relax Slater, where Guo et al. 2025) obtained Ö( +=///b/// /b)VT) re- gret for knapsack and ((VT) regret and violation for certain long-term constraints without Slater's condition. However, it neither offers modular, adaptive guarantees nor provides a single mechanism that simultaneously handles budget and general long-term constraints. In contrast, framework unifies budget and ROI control, eliminates the need for Slater's s condition, and remains compatible with general regression oracles, yielding adaptive guarantees across modeling choices.
B DISCUSSION ON LYAPUNOV STABILITY
Lyapunov drift analysis has been widely used to study the stability of control policies in stochas- tie queueing networks (see Hajek 1982 Tassiulas & Ephremides (1992). A policy is called stable when the induced queue lengths remain finite or uniformly bounded, and smaller queues typically in- dicate better performance. Modern analytical frameworks providing upper bounds on queue lengths to ensure stability are developed in Bertsimas et al. (200T); EFryllmzz & Srikant 2012). For broader
14

---

Published as a conference paper at ICLR 2026
introduction to Lyapunov optimization and its applications, refer readers to Necly 2022
Srikant
& Ying (2014).
C COMPARISON TABLE
In this section, we provide a detailed comparison of settings in Section S
Budget constraint constraint
ROI
ROI
Budget regime
Slater's condition free
Reference
Regret
Generalization
violation
Wang ct al. 2023
x
Ö( WT)
x
((T)
This work
0(11 WNT
Õ(VI)
((VT)
Table Our results and related work in the first-price auction.
Budget constraint
ROI
ROI
Budget regime
Slater's
Reference
Regret
violation
condition
Generalization
Castiglioni 2025
This work
0(11+ WNTMM
OlTTHiN a(V))
Table 2: Our results and related work in online bidding under uncertainty, where Ti. = Σn Y.T
Budget constraint
ROI constraint
ROI
Budget regime
Slater's
Reference
Regret
Generalization
violation
condition free
Guo et al. 2025
x
6 (1
NT
x
D(VT)
This work
ō( WT)
Õ(VT) 2(VT)
V
Table Our results and related work the contextual bandit.
D EXPERIMENTS
In this section, evaluate the proposed algorithm across different auction settings and learning methods. Specifically, we first reproduce the first-price auction environment of Wang et al. (2023); then consider the constrained bandit setting Guo al. (2025), where the reward is modeled as advertisement relevance; we also conduct sensitivity analysis on the choice of n) in the first-price auction environment.
For each experiment, we report the average reward 1 Σ rs and the real-time ROI Σ curve shows the mean over 20 independent runs with different random seeds, and shaded regions indicate 95% confidence intervals.
E! - Each
While L2FOB theoretically assumes access to the context distribution to perform mean-field evalua- tion the constraints, deploy variant that directly utilizes the current context v, when selecting by in practice. Under this implementation, L.2OBB still achieves superior performance in all experi- ments, demonstrating strong robustness.
D. FIRST-PRICE AUCTION UNDER BOTH BUDGET AND ROI CONSTRAINTS
In this setting, follow the empirical setup of Wang et al. (2023) and additionally impose return- on-investment (ROI) constraint to evaluate the algorithm' 's profitability. Specifically, the time hori- zon is set T 10a with total budget B 10a, yielding per-round budget p B/T 0.01.
15

---

Published as a conference paper at ICLR 2026
The ROI threshold is 7 1.8. The private value (context) is sampled e No.66, 0.1), and the competing bid as d, ~ (0.4, 0.1). We restrict v to the interval [0, 1], and any values of it or de exceeding 1 are truncated to 1.
For the baseline of Wang et al. (2023), set the step size to 1/vTT, as specified in their paper. For L2FOB, we use constant learning rates for the dual variables, with 7pp = 7 = 0.6. This choice framework allows '
does not conflict with setup in L2FOB. As noted after Theorem [ and fhy beyond the ((vT) scaling. When the oracle errors are of order Ö(vT), constant order choices of ?p and 7 also suffice. Intuitively, M[ar) governs the trade-off between reward and the budget/ROI constraints. Thanks
rectified design that incorporates the clip operator (-)+, even relatively large values of Mar> have a limited adverse impact on performance; see the sensitivity study in Appendix D.3
0.10
Wang al. (2023)
L2FOB
1.75
1.50
Averaged Reward
0.08
1.25
0.06
Averaged
1.00
0.75
0.50
0.02
0B
0.25
Wang et al. (2023)
0.00
ROI threshold=16
2000
4000
8000
10000
2000
4000
6000
8000
10000
Round
Round
Figure I: The averaged reward and averaged ROI of L2FOB and algorithm in Wang et al. (2033) in first-price auction setting.
The results Figure D show that L2FOB significantly outperforms the algorithm of Wang et al. (2023) in both reward and ROI under the first-price auction setting. L2FOB satisfies the ROI thresh- old stably over time, consistent with our anytime ROI violation guarantee (Theorem [T). By contrast, the method of Wang al. (2023), which does not explicitly enforee an ROI constraint, fails to reach the target profitability level and maintains a persistently low ROL. Moreover, L,FOB achieves higher and more stable average rewards throughout the horizon.
D.2 CONSTRAINED CONTEXTUAL BANDIT FOR BIDDING
We also consider the constrained contextual bandit setting in Guo et al. (2025). In this setting, we conduct experiments the large-scale learning-to-rant dataset MSLR W WEB30k Qin & Liu (203)), where each bidding action yields a corresponding relevance score. Following the experimental con- 5000, and B 1000, yielding a per-round budget of p = B/T 0.2. Within the bandit abstraction, the action (bid) b, corresponds to selecting an arm. We take the contextual feature U, and the reward r, from the dataset, and sample the cost as (0.2,, 0.02). To better approximate real-world noise, we corrupt both the observed rewards and costs by adding Gaussian noise (0, 0.05).
figuration of Guo al. (2025), we set ? 1.3,
As in Guo et al. (2025), we use a gradient-boosse boosted tree estimator as the learning oracle for the reward model and estimate the cost via empirical means. For the scaling terms, we also set 7)p 77- 0.6 in our algorithm. Because Guo et al. (2025) considers single-constraint setting, we adapt their method to multiple-constraint setting that simultancously enforces both a budget constraint and an ROI constraint. The experimental results are reported in Figure 2 While
adaptation enables the algorithm of [uoo et al. (0025) to operate under both budget and ROI constraints, the results show that our algorithm consistently outperforms Guo et al. (2025) in both average reward and ROI. Moreover, L2FOB maintains stable ROI performance over the time horizon and ultimately satisfies the ROI target.
16

---

Published as a conference paper at ICLR 2026
0.40
L2FO8
Guo al. (2025)
3.0
Guo al. (2025)
0.35
RGI threshold=1.3
Averaged RO)
Averaged
1.5
0.20
0.15
1000
3000
4000
1000
4000
5000
Round
Round
Figure 2: The averaged reward and averaged ROI of L2FOB and algorithm in Guo et al. (025 in the constrained contextual bandit setting.
D.3 SENSITIVITY ANALYSIS
Recall that in L2FOB we set пo 77 = V.. However, L2FOB allows more flexible choice of these scaling terms, both theoretically and empirically. Specifically, M(p,) may range from constant order ((1) up O(T) without affecting our theoretical guarantees. This due our rectified design that incorporates the clipping operator (-) on the constraints, which allows the algorithm focus on optimizing reward for actions predicted to be safe. Consequently, once the scaling terms are sufficiently large, further increases have little impact on performance. We focus on studying the influence of ROI scaling terms f7, and evaluate four representative values, that is
Thy (0.06, 0.6, 6, 603.
0.07
0,
2.0
0,
Averaged Reward
0.06
6.0
0.05
60.0
Averaged ROI
0.04
0.03
4p 1,-0..0
0.02
0.5
n,
0.01
6.00
9, - 60.0
0.00
0.0
threshold
4000
10800
8000
Round
Round
Figure 3: Sensitivity study on scaling term Yhy
Figure aliigns with our theoretical analysis of the scaling terms. Specifically, setting Ty {0.06, 0.6,6) strikes mild tradeoff between cumulative reward and ROI violation. However, when we set 77, = 60, the performance differs only slightly from 6. This aligns with our theoretical analysis: thanks to the rectified design of L2FOB, the algorithm does not become over-conservative under large constraint scaling, allowing more flexible control.
E DETAILED PROOFS
E. PROOF OF LEMMA
Lemma (Restatement of Lemma I Let b, be the bidding action selected by the L2FOB algo- rithm at round t. Then, for any bidding action b e RR., the following inequality holds:
+0 fe( 6) Fr( b.) -(Q -
<
( ftce,)))))
17

---

Published as a conference paper at ICLR 2026
To give the proof, we first give the following lemma that bridges the decision process with the potential drift:
Lemma Let (()) be any convex potential function, and update Qp(() and Qx(1) according to ( and 10). Then, for every round t,
(()((t) < ((Op(t 1oatt-1) ()) - p)+, $ (Q2(1)) & (00)0))))00.0)))))00(((000)00000 +0,
fe(v, b,)))*
Proof We prove the first inequality, then the second follows by the same argument. By convexity (and differentiability) of क for any x, y have ((y) & ((x) + (v) x). With y Qp(t) and
I pplt - 1),
T (Q,(1)) & ((Q Q 1))
(1 -
where the last equality holds due to the update rule
From the decision rule in we can directly obtain that for any bid decision i, the following inequality holds:
Fe(Ur. 4' (' (E),
fr b)]} p)+ p)+ (E.rvv))) (v, b,)))}+
Efr(U; bb) ((Q
where we have (p(t) = Qp b,) and (t) (t, b.) according the definition. Rearrange the inequality, we can get:
(v, b) fr,,, bt) + 4 ( (,00,,))))))000000000000)aaaaaa, (v),,,)))))
< (E. b)] p) (( b(
We can then apply Lemma to get:
(1),,
p)) ()) fe(vr, b)])
Add r(v,, b) r(u,, by) on both sides and rearrange the inequality, we can get:
r(v; b) - bl,,, ((Q,(t) - (tpp(t- 1)) + (Q2(()) (t 1))
<r(v;, b) - ()(,, + - r(v,,b))
+ (E) b)] p)+ + (B), fr(v,, b)])
<|r(ve, - [7,(,, bn) - r((e,
+
p) (1) b) f( b)])
<4. + (t, (), b]] - -)++ + 1 (Q, (B), [b
- fr b)])+
where the last inequality holds from the online regression oracle assumption and the optimistic reward estimators, thereby completing the proof.
E.2 PROOF OF LEMMA
Lemma (Restatement of Lemma 3 Let ba be an optimal solution to 2 Then, with stopping
time T,
E
p)+
& C2 T2 0(1),
E
- b((1,b+)))+
< 2 0(1).
18

---

Published as a conference paper at ICLR 2026
We prove the first result, then the second follows by the same argument. On the higb-probability event w from Assumption ! we have, for all t E [2]] and all (v, E X x R+,
(r( > r(v,b) b), c(v, 6) > &(e,b)
Applying the law of total expectation,
E
(( p)+
E
p E.lā(v, ((
-c(,,60))) b]]+
E
&' ( c(u,b*)]*
where the last step uses ((z) x² so that F'(x) 2x, the bound of cost function, the fact that Qp(t) & Qp(T) & TCmaz and (()) < to uniformly bound the summand on w. Choosing
p T-4 yields the final results.
E.3
PROOF LEMMA
Lemma (Restatement of Lemma 2 Under the L2FOB algorithm, for any e [T].
[[Q,(t)) & Cg. [[], Cg.
where
Cg (5 Rmar 2mpp /22 + 2n, M T2) 1/2
Applying Lemma I taking expectations, setting b = 1 and summing the resulting inequality over t yields
Σ (r(Us, b*) - r(u,, b.)) +
<
E +
1' ([006cc) p)+
Σ (2, B, - - (u,
< <4E, (T,p) + + 2m 2 man!
2 2n, 2aaz/ T2,
where the last inequality follows from Lemma together with the preceding arguments. Rearrange the inequality, and we obtain (f)(Q,(t)) ([)(),
<4E,(T,p) + 2np Chann 22 2n, Crann T + E Σ (r(v,)be) -r(
<TE,(T,p) + 2np C2 22 + 20,, Crann T22 + TR
mazi
We let the potential function (xx) x², then this inequality yields that
E[Q,(1)² [(], [[Q,(())] (1),
(T, 2n, T 2n, C T TR TRmax 55TRmas + Cmas T22 2n,, Cman T
where the first inequality holds according to Jensen's inequality, the last inequality holds due to the property of the reward function. Since [0)² 0 and ([), > 0, then by setting C2 (57 Rmaz + Cn Chaae/T T22 2 Canae/ 1/2 we complete the proof of Lyapunov stability.
19

---

Published as a conference paper at ICLR 2026
E.4 PROOF OF REGRET
Recall that we have the following decomposition of regret:
E(T)
r(us, bb)
E 7]
(r(v,, b*) r(ve, be))
Regret after stopping
Regret before stopping
We first derive the result for regret before stopping. Recall Lemma inequality, have
let be and rearrange the
fe(ve, 6*) be) <4c7 + Φ(Q,(t - 1)) (()( + (t, 1)) (t)(
fr(v, b*]]
Summing up the above inequality over T and taking the expectation, have
(r(0,, r(ve, bo))
E
Σ ((C, p)+ +=(0(2(00)+000000000
+
Σ
Φ (QQ (,,,(((,))),),,,,rrr(a)))))))))0 (((,,"""))
44
of
E
15 "[ p)+
t=1
+ E
@' (Q),
b*),++)))+++
where the first inequality follows by telescoping the potential functions, the second by the initializa- tion (0) 0 and (0) O. Then we can apply Lemma 3 to derive that
E
Σ (r(ve, b*) - r(v, b())
<4
E
((Q,(ttt"))n((Bll(u(bb""""" p)+
+
E
s (1)
<T, + 2n, C2 T + 2 T T2
(T,P))
For regret after stopping, Recall the definition of stopping time that
argmin r'((T]
c b,) B g
which gives
Σ (alo,, p) +pp Σ - (x(r, > B,
Taking the expectation and rearranging the inequality, we have
1 E Tp]
E T
7| 8
20

---

Published as a conference paper at ICLR 2026
Σ b)) + pP)+
(c((v)))))
- 2e(,, b+))
1
1
[T]) + Ec(T,P)
1
(Cg
+ Ec(T..))
0 Mpp
where the second inequality holds since in [1 show that
Up (B,la(u,b))- 0)* & Qp(T).
Applying the law of expectation indicates that
E
Σ (ce(ve, bi) pp
=E
E (e,
<E
E (E, p)
[T)]
Up
This implies that the cumulative estimated violation is upper bounded by the terminal virtual queue, then we can apply Lemma 2 to derive the last inequality. Combining all these terms, we complete the proof of regret bound in Theorem |
E.5
PROOF OF CONSTRAINT VIOLATION
Recall in M.] we have the following results for estimation violation of ROI constraint,
T/r Σ (E,l77a(V, b.) b.(v,, Q2()).
For constraint violation, we can derive the following decomposition that
70(v,, b.) - r(ve. b.))
E,lyclu,bo b.) (w)
(Eo(7c(v. bb) b(),ba)))+
(Eolycs(u.bo b.) bo)
([r(c(o,bb)) - b,)(),))))
(E.. r(,,,)))),,,,
<E
Σ (.,,)),))
((] (T, pT.
Th
C (T, + (T.
1/
Then, applying Lemma we can derive the constraint violation, which completes the proof of Theorem
21

---

Published as a conference paper at ICLR 2026
STATEMENT ON LARGE LANGUAGE MODELS (LLMS) USAGES
The large language model was used only as a general-purpose writing aid for English grammar checking and minor polishing. The LLM did not contribute research ideation, problem formula- tion, algorithm design, experiment setup, analysis, or substantive writing of any technical content. All methods, results, and conclusions were conceived, written, and verified by the authors.
22


Reviews:
[{"review_id": "W2fbjB7hkK", "reviewer": "Reviewer_p36P", "summary": "This paper studies the problem of online bidding with a budget constraint and a return-on-investment (ROI) constraint. The authors develop a general, modular framework for this problem and propose an algorithm called L2FOB. This algorithm uses a combination of optimistic reward estimates, pessimistic cost estimates, and a one-step look ahead to optimize for the bids. The authors prove adaptive bounds on regret and ROI constraint violation in terms of errors of the reward and cost estimators.", "questions": "Please see the weaknesses section.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The authors develop a modular framework and algorithm that can be applied to many specific settings (as they do in Section 5).\n\n* The proposed algorithm uses a nice look-ahead function to bound a potential function, which they then use to bound the Lyapunov drift and resulting regret bound. This is a neat idea. This idea seems similar to one-step model predictive control in control theory.\n\n* The bounds on regret and ROI constraint violation are adaptive in terms of the error bounds of the reward and cost estimators. The authors achieve this regret bound without Slater's condition, although the trade-off (as they note) is that instead of strict ROI constraint satisfaction they incur some violation.", "weaknesses": "(Combined weaknesses and questions into one section.)\n\n* The look-ahead idea is nice. As I mentioned in the strengths section, this seems similar to one-step model predictive control in control theory. It would be nice to discuss this area of related work in the paper. On a related note, how helpful would it be to consider a $k$-step look-ahead?\n\n* The problem setup assumes that the context distribution is known and uses it to compute the expectations over $v$ in lines 4, 5 and 7 in Algorithm 1. Is it necessary to assume a known context distribution? How does your algorithm behave if the updates are noisy - either through point estimates, empirical estimates using the history, or an approximately known context distribution?\n\n* Can your ideas be generalized to non-bidding problems in online optimization with constraints? How well does your algorithm scale with the number of constraints?\n\n* The ROI constraint is not satisfied strictly, although this comes with the advantage of not assuming Slater's condition.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7QHY2BSqEL", "reviewer": "Reviewer_sRuk", "summary": "The paper study the online bidding problem under budget (hard) and ROI constraints, in stochastic contextual settings. The authors propose an algorithm based on a Lyapunov framework which attains regret and violations that scale linearly in the error of some online learning oracles which are assumed to exist and are used to estimate the reward and the constraints functions. Finally, the authors show how the setting they study generalise many well known problems (e.g., first price auctions) and the specific guarantees of the algorithm in the aforementioned settings.", "questions": "See weaknesses.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The main strength of the paper is the setting studied. Indeed it generalises many \"online bidding\" problems, thus being of interest for the community. Second, I find particularly interesting the fact that the algorithm presented does not require Slater's condition to obtain the desired bound.", "weaknesses": "I have the following concerns on the paper:\n\n1. First, the authors miss a fundamental related work ([1]). In [1], the authors study an online learning problem with budget and roi constraints as in this paper. The only difference is that the authors study a non-contextual setting. Moreover, [1] requires some form of Slater's condition on the ROI constraint to obtain the optimal bounds. Nonetheless, [1] attains guarantees for adversarial settings, too.\n2. I find peculiar that the context distribution is assumed to be known. I believe it is not standard in the literature of contextual bandits, while it seems fundamental for the employment of the algorithm, since the expectation on the context distribution is computed at each round.\n3. Paragraph \"Assumptions and Baselines\" is not formal enough. Specifically, Equation (2) is meaningless as it is. First, it is not clear over which distribution the expectation is taken. Moreover, if the expectation is taken over the context distribution, as it seems given that $v_t$ is not used in (2), the problem collapse to a non contextual online learning problem.  \n4. Throughout the paper, the authors claim that they bound the positive ROI violation (using $()^+$). Nonetheless, the standard metric is used in the theorems. \n5. Finally, I don't understand the proof step at line 299. I think the inequality holds paying a $\\sqrt T$ factor thanks to the Azuma inequality. Instead, the authors claims that it works as it is. \n\n[1] \"Online Learning under Budget and ROI Constraints via Weak Adaptivity\", ICML 2024", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RUZZiF3c0o", "reviewer": "Reviewer_mJ77", "summary": "This paper formulates the general online bidding problem as an online learning problem with both the budget and target return-on-investment (ROI) constraints. Under this general learning problem, the authors proposed a primal–dual algorithm using a Lyapunov perspective, and they also show an regret upper bound for this algorithm with no budget overuse but some ROI violations. Additionally, for several specific settings, this upper bound matches the optimal regret order.", "questions": "See the weaknesses section.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. To my best knowledge, the idea of using Lyapunov function is novel.\n\n2. The theoretical result holds in a very general framework, and also achieves strong performances in several specific but important settings.\n\n3. Numerical results are also included in the appendix to illustrate the performance.", "weaknesses": "1. My main concern is about the compatibility of the learning oracle and the proposed algorithm with partial information feedback (bandit setting). Specifically, when showing sqrt{T} results in Section 5, the authors state that bounds on \\Epsilon(T,p) can be obtained following some other papers. However, their arm selection process might be different from this paper. How to guarantee that the bound still holds? Could the authors elaborate more on these bounds and provide a more detailed version of the proofs? I will raise my score is this question is addressed.\n\n2. It seems the algorithm works when only one budget constraint exists. This assumption may limit the applicability. I wonder whether a similar statement holds when there are multiple budget constraints, especially Lemma 3?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "C7gwBbgd7M", "reviewer": "Reviewer_3r7f", "summary": "This paper provides a framework and an algorithm for ROI and budget constrained bidding in repeated auctions. \nThe framework relies on the notions of look-ahead virtual queue tracing, instead of using a more standard primal-dual approach. \nThe results are expressed in term of error made by prediction oracles. \nThe framework is used to revisite previous works.", "questions": "* see weakness", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The topic of budget and ROI constrained bidding  has already attracted a lot of attention, \nand I find the framework proposed by the authors practical and intuitive (compared too, for instance, dual approaches).", "weaknesses": "* The writing is not always clear, and I urge the authors to check each paragraph clarity.\n* What would, IMHO, what could really improve the paper would be: \n1. to clarify the positioning with respect to the other papers on the topic (stochastic vs adversarial env, slack assumtions...). A table would be very welcome. \n2. to better explain what the Lyapunov Framework is in general, it feels like some references and explanation could be added on the topic. For instance, could the authors tell the readers where the name comes from?\n \n* the practicality of the assumption should be more discussed. For instance, how do you compute the \"E(...)\" in the algorithm in practice?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)