Research map / Bandits and online learning / Online convex optimization and games
Learning-Augmented Online Bidding in Stochastic Settings
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies online bidding with distributional predictions (computing Pareto-optimal deterministic strategies via LPs) and with randomized learning-augmented strategies (upper and lower bounds on consistency-robustness tradeoff), plus extensions to dynamic predictions and linear search.
Problem
Online bidding (and related contract scheduling / linear search) under learning-augmented settings with stochastic predictions or randomized algorithms, where the consistency/robustness tradeoff was previously studied only for deterministic algorithms and single-valued or worst-case-optimal cases.
Approach
Restrict search to tight r-extendable partial strategies on the prediction support and solve a family of LPs (one per configuration) to obtain the Pareto-optimal deterministic strategy for distributional predictions; for randomized single-valued predictions, use a parameterized randomized geometric strategy and scalarize the two objectives with a minimax/Yao argument to derive lower bounds.
Key results
- Experiments over integer r in [4,12] on six synthetic datasets show the Pareto-optimal LP-based algorithm has better average consistency than all three geometric heuristics for every r.
- For r=4 the randomized strategy R* achieves consistency about 1.724, while for r=5 the optimal delta approaches 0.99, meaning randomization benefits quickly vanish as r grows.
- Lower bound: any randomized r-robust learning-augmented algorithm has consistency at least 1 + 1/((1+xi) r F(r)), which approaches the deterministic tight bound as r grows.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the distributional-prediction LP algorithm instead of geometric heuristics | Online bidding with distributional predictions · Six datasets; integer r within [4,12] | consistency | Helped |
| Use the distributional-prediction LP algorithm instead of geometric heuristics | Online bidding with distributional predictions · Six datasets; integer r within [4,12] | variance of consistency | Helped |
| Use geometric heuristic with ρ=ζ1 | Online bidding with distributional predictions · Experimental datasets | consistency | Hurt |
| Increase the geometric heuristic base ρ | Geometric bidding heuristics · Experimental datasets | variance of consistency | Hurt |
| Use the distributional-prediction LP algorithm instead of geometric heuristics | Online bidding with two equiprobable target points · Large r | consistency: 1 versus 2 | Helped |
| Optimize randomized geometric strategy parameters δ and a | Randomized learning-augmented bidding · r=4 | consistency: approximately equal to 1.724 | Helped |
| Use randomized learning-augmented bidding rather than the best deterministic strategy | Online bidding with a single-valued prediction · Increasing robustness requirement r | consistency | Mixed |
| Increase robustness requirement r | Optimized randomized strategy R* · Online bidding with a single-valued prediction | consistency advantage over deterministic strategies | Hurt |
| Quantize the distributional prediction into exponentially spaced levels | Algorithm for computing the Pareto-optimal strategy · Online bidding, support [m,M] | consistency: e^{1/c} | Hurt |
| Replace the full randomized algorithm with the deterministic limit as δ→1 | Rδ,a · Online bidding, predicted target | consistency: a/(a-1) | Hurt |
Surprising findings
- Randomization yields only marginal consistency gains over deterministic Pareto-optimal strategies for large robustness r, since the optimal randomization parameter delta approaches 1.
- For large r, geometric heuristics' consistency tends to 2 while the proposed algorithm's tends to 1 on simple two-point predictions.
Limitations
- Approach assumes robustness r is a constant independent of other parameters.
- Exact LP-based algorithm is exponential in the number of prediction support points k in the worst case; a quantized approximation is needed for general distributions.
- Randomized results are limited to single-valued predictions and the lower bound is not tight against the upper bound.
Experimental setup
Datasets: synthetic distributional predictions (k=4 points on [1,10^4], six generated datasets, 10 samples each)
Benchmarks: synthetic distributional predictions
Metrics: consistency robustness standard deviation of consistency over samples
Baselines: geometric heuristics (lambda * rho^i) deterministic Pareto-optimal bidding strategy randomized optimal strategy e-competitive (Kao et al.)
Builds on: Yao's principle ski rental consistency-robustness tradeoff distributional predictions framework
Closest papers by meaning
- Towards Safe and Optimal Online Bidding: A Modular Look-ahead Lyapunov Framework (ICLR 2026 · similarity 0.89)
- Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search (ICML 2025 · similarity 0.88)
- Online Learning of Optimal Bidding Strategy in Repeated Multi-Commodity Auctions (NeurIPS 2017 · similarity 0.88)
- No-Regret Online Autobidding Algorithms in First-price Auctions (NeurIPS 2025 · similarity 0.87)
- Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions (ICML 2025 · similarity 0.86)
- Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.