Research map / Bandits and online learning / Online convex optimization and games
Improved Algorithms for Contextual Dynamic Pricing
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 VAPE, an algorithm alternating uniform-price valuation approximation with successive price elimination across valuation levels, achieving O~(T^{2/3}) regret for linear contextual pricing with Lipschitz noise CDF and O~(T^{(d+2β)/(d+3β)}) for Hölder valuations.
Problem
Contextual dynamic pricing with binary purchase feedback, where buyer valuations are noisy functions of the context (linear or Hölder-continuous), under minimal regularity assumptions.
Approach
A general VAPE scheme that adaptively alternates between uniform-price valuation estimation and price-increment successive elimination, sharing demand estimates for each price increment across all contexts/valuation levels (information sharing), rather than using two-phase or binned independent bandits.
Key results
- Linear valuation VAPE achieves regret O~(d^{2/3} T^{2/3}) with probability 1-O~(T^{-1}), matching the known T^{2/3} lower bound under Lipschitz-CDF noise.
- Non-parametric Hölder valuation VAPE achieves O~(T^{(d+2β)/(d+3β)}), improving the prior O~(T^{3/4}) type rates under weaker assumptions.
- Simulations show empirical regret consistent with the theoretical bound and VAPE is more robust than a prior algorithm in an adversarial context ordering.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use VAPE instead of the prior method under Lipschitz-CDF assumptions | Contextual dynamic pricing with linear valuations · Linear valuations | regret rate: \Olog(T^{\nicefrac{3}{4}}) -> \tilde{O}(T^{\nicefrac{2}{3}}) | Helped |
| Use VAPE under Lipschitz-noise and Hölder-valuation assumptions | Contextual dynamic pricing with non-parametric valuations · Non-parametric valuations | regret rate: \Olog(T^{\nicefrac{d+2\beta}{d+3\beta}}) | Mixed |
Surprising findings
- Contextual dynamic pricing with linear valuations is not harder than non-contextual pricing: the T^{3/4} rate of naive approaches is not optimal, and T^{2/3} is achievable.
Limitations
- Assumes i.i.d. noise with Lipschitz CDF and bounded noise; noise distribution cannot depend on context.
- Non-parametric rate is not shown to be optimal; the rate is above the usual T^{(d+β)/(d+2β)} bandit rate.
- Optimal dependence on dimension for linear case remains unknown.
Experimental setup
Datasets: synthetic contexts in R^3 (Gaussian, normalized)
Benchmarks: synthetic simulations of linear valuation pricing
Metrics: cumulative regret log-scale regret vs. horizon T
Baselines: Lipschitz-CDF linear pricing algorithm (Appendix F of prior work) explore-then-commit binned independent bandits (CAB1)
Builds on: successive elimination elliptical potential lemma cross-learning with graph feedback
Closest papers by meaning
- Contextual Dynamic Pricing with Heterogeneous Buyers (NeurIPS 2025 · similarity 0.92)
- Semi-Parametric Dynamic Contextual Pricing (NeurIPS 2019 · similarity 0.92)
- Pricing with Contextual Elasticity and Heteroscedastic Valuation (ICML 2024 · similarity 0.91)
- Semi-Parametric Contextual Pricing with General Smoothness (ICLR 2026 · similarity 0.91)
- Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand (NeurIPS 2026 · similarity 0.91)
- A Parametric Contextual Online Learning Theory of Brokerage (ICML 2025 · similarity 0.89)
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.