Research map / Bandits and online learning / Online convex optimization and games
Contextual Dynamic Pricing with Heterogeneous Buyers
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 contextual dynamic pricing against a heterogeneous buyer population with K* valuation types, proposing optimistic posterior sampling (regret Õ(K*√(dT)), tight in d and T) and a variance-aware zooming algorithm for the non-contextual case.
Problem
Dynamic pricing with binary purchase feedback when buyers are heterogeneous: valuation types are drawn from an unknown distribution with unknown finite support size K*, and the seller observes only a context and whether the buyer purchased.
Approach
Adapts optimistic posterior sampling (feel-good Thompson sampling) to pricing by bounding its disagreement coefficient by 2(K*+1) using monotone demand pieces, adds perturbed/discretized prices and a Levy-metric cover to handle infinite model classes, and for d=1 uses zooming with variance-aware confidence intervals.
Key results
- POPS achieves regret Õ(K*√(dT)) without knowing K*, and a lower bound Ω(√(K* dT)) holds for T ≥ 8dK*^3 log(2d), so the bound is tight in d and T up to logs.
- Zooming achieves Õ(min{√(K*T), T^{2/3}}) regret for non-contextual pricing, matching the lower bound up to logs when K*>1.
- With ex-post type-identifier observability, an algorithm achieves Õ(K*√(dT)); with full type-vector observability, plug-in best response achieves Õ(√(min{K*,d}T)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use variance-aware confidence intervals with adaptive zooming | Non-contextual pricing · Non-contextual pricing | regret: O(T^{2/3}) versus \widetilde{O}(\min\{\sqrt{K_\star T}, T^{2/3}\}) | Helped |
| reveal the arriving type identifier | Contextual dynamic pricing · Contextual pricing with observed type identifiers | expected regret: \widetilde{O}(K_\star\sqrt{dT}) | Helped |
| reveal the full type vector instead of only purchase feedback | Contextual dynamic pricing · Contextual pricing with observed type vectors | expected regret: \widetilde{O}(K_\star\sqrt{dT}) -> \widetilde{O}(\sqrt{\min\{K_\star,d\}T}) | Helped |
Surprising findings
- The disagreement coefficient of the demand-function class is O(K*) independent of the infinite price set, so the bound matches what K* actions would give.
- Regret of the variance-aware zooming algorithm is 0-dimensional in variance-aware zooming dimension, giving T^{2/3} even when K* is large.
Limitations
- The main contextual algorithm is computationally inefficient, with run time scaling with the exponentially large discretized model class.
- The contextual optimal dependence on K* is not resolved; there is a Õ(√K*) gap to the lower bound.
- For large K* (around (T/d)^{1/3} or more) the lower bound is dominated by a T^{2/3} term and EXP4-style discretization is competitive.
Experimental setup
Metrics: pricing regret
Baselines: EXP4 with discretized prices corruption-robust contextual search Feng et al. non-contextual heterogeneous pricing
Builds on: feel-good Thompson sampling zooming for Lipschitz bandits contextual search
Closest papers by meaning
- Improved Algorithms for Contextual Dynamic Pricing (NeurIPS 2024 · similarity 0.92)
- Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand (NeurIPS 2026 · similarity 0.91)
- Pricing with Contextual Elasticity and Heteroscedastic Valuation (ICML 2024 · similarity 0.91)
- Contextual Online Pricing with (Biased) Offline Data (NeurIPS 2025 · similarity 0.87)
- Transfer Learning for Nonparametric Contextual Dynamic Pricing (ICML 2025 · similarity 0.87)
- Transfer Faster, Price Smarter: Minimax Dynamic Pricing under Cross-Market Preference Shift (NeurIPS 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.