Research map / Bandits and online learning / Online convex optimization and games
Learning to price with resource constraints: from full information to machine-learned prices
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.
Proposes three re-solve-based pricing algorithms for knapsack-constrained dynamic pricing under linear demand: a boundary-attracted re-solve method with O(log T) regret under full information, a learning algorithm with O(sqrt(T)) regret with no prior information, and an estimate-then-select method using machine-learned informed prices with known error bound.
Problem
Dynamic pricing with resource (knapsack) constraints under linear demand with noise, where the seller must balance learning unknown demand parameters against revenue maximization and inventory consumption; the goal is low regret relative to the fluid benchmark, including when the fluid problem is de
Approach
Re-solve the fluid model at each period but push prices toward the upper bound when expected demand is near zero (boundary attraction), which avoids the non-degeneracy assumption and yields log regret; with no information, add a variance-inducing perturbation around a momentum anchor to ensure exploration; with an informed price-demand pair and known error bound, select between trusting the inform
Key results
- Full-information Boundary Attracted Re-solve Method achieves O(log T) regret without non-degeneracy assumption (Theorem 2.1 bound O(zeta^2 n^2 ||B^{-1}|| log T)).
- No-information algorithm achieves O(sqrt(T)) regret, matched by a sqrt(T) lower bound.
- Estimate-then-select algorithm achieves O(min{rho sqrt(T), (eps^0)^2 T + C' log T}), which is optimal order given the matching lower bound; numerical runs show near-constant regret in full-information and informed-price settings even under degeneracy.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use boundary attraction in the re-solve method without a non-degeneracy condition | Full-information dynamic pricing with resource constraints · Dynamic pricing with resource constraints, full information | regret: O(\zeta^2n^2\norm{B^{-1}}_2\log T) | Helped |
| Learn demand parameters online and perturb prices to enforce exploration | Periodic-review re-solve with parameter learning · Dynamic pricing with resource constraints, no prior information | regret: O\prn{(\zeta^2+\norm{B^{-1}}_2)\sqrt{T}} | Helped |
| Use an informed price-demand pair with a known upper bound on estimation error | Estimate-then-select re-solve with parameter learning · Dynamic pricing with resource constraints, informed price with known error bound | regret: O(\min\{\rho\sqrt{T},(\epsilon^0)^2T+C'\log T\}) | Helped |
| Provide an informed price-demand pair but not its accuracy bound | Online pricing policy · Dynamic pricing with resource constraints, informed price without known error bound | regret: \Omega(\sqrt{T}) | No clear effect |
Surprising findings
- Without an upper bound on the informed price error, no policy can beat the zero-information O(sqrt(T)) rate even when the informed pair is given.
Limitations
- Analysis restricted to a linear demand model with sub-Gaussian noise.
- Informed-price algorithm requires a known upper bound on estimation error and an assumption that the informed demand exceeds the infinite-resource demand.
- Experiments are limited to a small two-product synthetic instance.
Experimental setup
Benchmarks: synthetic linear demand instances
Metrics: regret
Baselines: first-order correction re-solve (non-degeneracy based)
Builds on: bandits with knapsacks fluid approximation re-solving single-step difference analysis
Closest papers by meaning
- Contextual Online Pricing with (Biased) Offline Data (NeurIPS 2025 · similarity 0.89)
- Transfer Learning for Nonparametric Contextual Dynamic Pricing (ICML 2025 · similarity 0.88)
- Learning to Price Homogeneous Data (NeurIPS 2024 · similarity 0.87)
- Improved Algorithms for Contextual Dynamic Pricing (NeurIPS 2024 · similarity 0.87)
- Pricing with Contextual Elasticity and Heteroscedastic Valuation (ICML 2024 · similarity 0.87)
- Online Resource Allocation With General Constraints (NeurIPS 2026 · similarity 0.87)
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.