Learning to Bid with Unknown Private Values in Budget-Constrained First-Price Auctions

Summary

This paper studies online repeated first-price auctions where the bidder’s private value for an impression is not directly observable but must be inferred from censored data. The authors adopt a Linear Treatment Effect (LTE) model, assuming the “uplift” value is generated by a linear model based on observable context vectors, and that the competitors’ highest bid also depends linearly on the same context vector. The paper states: “we posit that both the uplift value and the opponents’ highest bid are linearly generated by the same context vector xt. This joint dependence distinguishes our contribution from prior literature.” The setting is formalized as E[vt,1 − vt,0 xt] = θ⋆⊤ xt and mt = ϕ⊤ ⋆ xt + ξt, with ∥θ⋆ ∥2 ≤ 1 and ∥ϕ⋆ ∥2 ≤ 1.

The paper proposes a unified primal-dual framework for constrained FPAs that jointly learns the latent LTE valuation parameters and the competitor’s bid distribution. The authors note: “This simultaneous learning introduces a critical technical challenge: the estimation error is dynamically scaled by the Lagrangian multiplier, potentially leading to unbounded regret. We resolve this by leveraging a strong Slater condition and a novel adaptive burn-in procedure to stabilize the dual variables.”

The main contributions are threefold. First, the paper establishes a unified modeling framework for online first-price auctions where both the treatment effect and the highest competing bid depend linearly on the context, extending analysis from unconstrained bidding to global constraints within a single primal–dual architecture. Second, it provides rigorous regret analysis for three settings: unconstrained, hard budget constraint, and expected RoS constraint. The unconstrained and Budget guarantees achieve the Õ(d√T) scale, while the comparator-specific RoS bound scales as Õ(d√T/δS) through the Slater margin and the resulting dual ceiling. Since the lower bound for the unconstrained setting scales with omega(√T), the results are optimal with respect to the time horizon up to the constraint constants. Third, the paper bridges theory and practice by proposing a computationally efficient split-sample estimation procedure for the competing bid distribution, providing a constructive alternative to the existential guarantees in prior LTE work, and introducing an adaptive burn-in phase to dynamically estimate the Slater constant for the RoS setting, ensuring primal-dual convergence without prior knowledge of optimal dual variables.

The paper is organized around three main algorithmic components. Section 3 introduces a constructive bilinear CDF estimation procedure (Algorithm 1) that estimates ϕ⋆ by ridge regression on a random training subset of past rounds and forms an empirical CDF on the disjoint evaluation subset, preserving conditional independence between ϕ̂t and the Bernoulli indicators used in F̂t (b). The key result is Lemma 3.2, which provides a Bernstein-type bilinear CDF oracle: with probability at least 1 − T −1, F̂t (b) − Ft (b) ≤ ϵt √(Ft (b)(1 − Ft (b))) + ϵ2t, where ϵt = C log T √(d/t + log T ∥xt ∥Σ−1 t). This is a constructive substitute for the non-constructive subset-selection step used in earlier LTE analyses.

Section 4 builds the IPW-WLS oracle. The paper uses inverse-propensity weighting to convert censored auction feedback into noisy linear observations of the latent uplift. The truncated IPW pseudo-outcome is defined as ỹτ (b) = I[b ≥ mτ]/max ϵ2τ, F̂τ (b) vτ,1 − I[b < mτ]/max ϵ2τ, 1 − F̂τ (b) vτ,0. The WLS update uses variance weights ωτ (b) = F̂τ (b)(1 − F̂τ (b)), and the global WLS state is At−1 = λ0 I + Στ<t ωτ (bτ)xτ x⊤ τ, ut−1 = Στ<t ωτ (bτ)xτ ỹτ (bτ), θ̂t−1 = A−1 t−1 ut−1. Lemma 4.1 establishes the IPW bias and variance bounds: E[ỹτ (b) xτ, b] − θ⋆⊤ xτ ≤ C0 ϵτ στ (b) and Var(ỹτ (b) xτ, b) ≤ C1 στ (b)2. Lemma 4.2 provides the global weighted confidence bound (θ̂t−1 − θ⋆)⊤ xt ≤ βt ∥xt ∥A−1 t−1 with βt = Õ(√∆̄2).

Section 5 packages the unified Constrained-SquareCB-LTE template (Algorithm 2). The template defines mode-indexed shadow prices: γt = 0 for Unc, γt = Zµt for Bgt, and γt = λt/(1+λt) for RoS. The branchwise Lagrangian scores are Lbt,0 (b) = F̂t (b)(st − at b) and Lbt,1 (b) = −(1 − F̂t (b))st − at bF̂t (b), with optimistic variants Ut,0 (b) = Lbt,0 (b) + F̂t (b)ρt + Cbr ϵt and Ut,1 (b) = Lbt,1 (b) + (1 − F̂t (b))ρt + Cbr ϵt. The algorithm uses a branch threshold κbr = min 1/4, 1/(40L) and a safe truncation level zt = min βt √(d/T) + 4ϵt, 1/2. The SquareCB mixing probability is pt = 1/(2 + α∆̄t), where ∆̄t = fˆt (b̂t) − fˆt (binfo t). The played bid is truncated to the safe quantile interval [F̂t−1 (zt), F̂t−1 (1 − zt)].

Section 6 presents the Budget plug-in (Algorithms 3 and 4). The budget shadow price is γtBgt = Zµt with Z = T/B, and the dual update is µt+1 = Proj[0,1] µt exp(η(ct (bt) − B/T)). The algorithm uses a predictable stopping time τ = min t ∈ [T + 1]: St > B − 1. A critical fallback rule is introduced: when ρt exceeds the safe threshold r0 = κbr/(4(1 + Z)), the algorithm temporarily ignores the greedy branch and plays the fallback information bid maximizing ω̂t (b) on the local candidate interval. The main result, Theorem 6.1, states that under Assumptions 2.1-2.5 and 2.7, with α = Θ̃(√(T/(d∆̄2))) and η = Θ(T −1/2), the regret satisfies RTBgt ≤ Õ((1 + Z)3 dT ∆̄2) + O((1 + Z)∆1) + Õ(Z√T) + Õ((1 + Z)3 d∆̄2). Under the split-sample bilinear CDF rates ∆1 = Õ(√(dT)) and ∆̄2 = Õ(d), when T dominates lower-order burn-in terms and Z = O(1), this simplifies to RTBgt = Õ((d + Z√d)√T).

Section 7 presents the RoS plug-in (Algorithm 5). The RoS shadow price is γtRoS = λt/(1 + λt), and the dual update is λt+1 = Proj[T −1/2,Λ] λt exp(−ηg̃topt), where g̃topt = g̃t + F̂t (bt)ρt is the optimistic margin. The algorithm includes a burn-in phase of length T0 = ⌈√T⌉ that estimates the Slater margin δ̂ and sets the dual ceiling Λ = 2Cr/δ̂. The RoS plug-in uses a safe-grid and lower convex hull construction: for each safe bid, it attaches optimistic allocation–payment coordinates qt† (b) = min 1, F̂t (b) + ϵt and c†t (b) = bqt† (b), and optimizes only on vertices of the lower convex hull Htlow. The main result, Theorem 7.1, states that under Assumptions 2.1-2.6, 2.8 and 2.9, with η = Θ(T −1/2) and α = Θ̃(√(T/(d∆̄2))), the regret satisfies RTRoS (π ⋆) ≤ Õ((√(dT ∆̄2) + ∆1 + (1 + G2T)√T)/δS) and the violation satisfies VTRoS ≤ Õ(Λ(√(dT ∆̄2) + ∆1 + (1 + G2T)√T) + ∆̄1/2 2 T 3/4 + √T log(1/δfail)). Corollary 7.2 specializes these to RTRoS (π ⋆) = Õ(d√T/δS) and VTRoS = Õ(d√T/δS + d1/2 T 3/4 + √T log(1/δfail)).

The paper concludes: “We study online first-price auctions where uplift and competition share a context embedding. The main technical spine is Constrained-SquareCB-LTE: split-sample bilinear CDF estimation, IPW–WLS uplift learning, mode-specific Lagrangian branch scores, and SquareCB mixing under primal-dual updates, with Budget and RoS plug-ins and matching guarantees in Sections 6–7. The unified template isolates estimation noise from constraint handling: Budget couples spending to a stopping time via µt, whereas RoS couples margins to λt ≤ Λ with optimistic surrogates that remain stable after burn-in. A natural direction is to tighten rates under weaker feedback or adversarial context ordering.”

Based on the paper, here are the specific improvements I can make to AI systems and what the improved systems can do:

1. Real-Time Bidding (RTB) System with Latent Value Inference

• Improvement: Replace the common assumption that impression value is known before bidding. Instead, use the paper’s Linear Treatment Effect (LTE) model to infer the causal uplift (value) from observable context vectors (user demographics, device, browsing history) using IPW-WLS, even when only censored outcomes (win/loss) are observed.

• Capability: The AI can now bid in first-price auctions without a valuation oracle. It learns the marginal value of an impression from past auction outcomes and context, handling the fact that it only sees the treated value if it wins and the control value if it loses.

2. Budget-Constrained Bidding with Pacing and Exploration

• Improvement: Integrate the paper’s primal-dual framework with a normalized dual multiplier (µ t) and a predictable stopping time. Use the SquareCB mixing rule to balance exploitation (greedy Lagrangian bid) and exploration (information bid maximizing F̂(b)(1-F̂(b))). Add a fallback rule when the confidence radius (ρ t) is too large to avoid low-information regions.

• Capability: The AI can now bid under a hard budget constraint (B ≤ T) while achieving near-optimal regret Õ(d√T). It dynamically paces spending, avoids overshooting the budget, and actively explores to shrink estimation error, all without knowing the true value function.

3. Return-on-Spend (RoS) Constrained Bidding with Dual Stability

• Improvement: Use the RoS-specific algorithm with a burn-in phase to estimate the Slater margin (δ S) and set a dual ceiling (Λ). Use a safe-grid and lower convex hull of the payment curve to handle non-convex first-price payments. Use optimistic margin updates (g̃ t opt) to stabilize the dual variable λ t.

• Capability: The AI can now satisfy a soft RoS target (e.g., return on spend ≥ 1) with both regret and violation guarantees. It handles the non-packing constraint without prior knowledge of the optimal dual variable, and the burn-in ensures the dual multiplier remains bounded, preventing unstable bidding behavior.

4. Joint Estimation of Competitor Bids and Own Value

• Improvement: Implement the split-sample bilinear CDF estimator (Algorithm 1) that uses ridge regression on a random training subset to estimate the competitor’s bid parameter (φ⋆) and an empirical CDF on a disjoint evaluation subset. This replaces non-constructive existence proofs with a computationally efficient, constructive method.

• Capability: The AI can now simultaneously learn the distribution of the highest competing bid (as a function of context) and its own uplift value. This is critical for bid shading in first-price auctions, where the optimal bid depends on both the value and the probability of winning.

5. Handling Censored Data with Inverse Propensity Weighting (IPW)

• Improvement: Use the truncated IPW pseudo-outcome (Equation 5) with variance weights ω t(b) = F̂ t(b)(1-F̂ t(b)) to convert censored auction feedback into unbiased linear observations of the latent value. This is integrated into a weighted least-squares (WLS) update with a confidence radius ρ t.

• Capability: The AI can now learn from data where the outcome is only partially observed (win/loss). It correctly accounts for selection bias by weighting observations by their inverse probability of being observed, and it truncates extreme weights to maintain statistical stability.

6. Adaptive Exploration-Exploitation Trade-off

• Improvement: Use the SquareCB mechanism (Equation 15) to mix between the greedy bid (maximizing the current Lagrangian score) and an information bid (maximizing the variance proxy ω̂ t(b)). The mixing probability is adaptive to the estimated score gap Δ̄ t.

• Capability: The AI automatically balances short-term profit with long-term learning. When the greedy and information bids are close, it explores more; when they are far apart, it exploits more, ensuring the cumulative regret remains near-optimal while the confidence radius shrinks at a controlled rate.

7. Handling Non-Convex Payment Landscapes

• Improvement: For RoS constraints, use the lower convex hull of the (allocation, payment) pairs to create a convexified planning domain. This allows the AI to reason about randomized bids (mixtures) that can be strictly better than any deterministic bid.

• Capability: The AI can now optimize over a convexified bid space, enabling it to find superior bidding strategies that involve randomization between bids, which is particularly important when the payment function is non-convex (as in first-price auctions).

8. Robustness to Estimation Error

• Improvement: The algorithms include fallback mechanisms (e.g., playing the information bid when ρ t > r 0) and safe-grid truncation (zt) to avoid regions of high uncertainty. The regret bounds explicitly account for estimation errors (Δ1, Δ2) and the Slater margin (δ S).

• Capability: The AI system is robust to initial estimation errors and does not waste rounds in low-information regions. It gracefully degrades performance when the model is uncertain, and its guarantees are explicitly tied to the quality of the estimators, providing predictable performance.