Research map / Bandits and online learning / Online convex optimization and games
Pricing with Contextual Elasticity and Heteroscedastic Valuation
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 Pricing with Perturbation (PwP), an ONS-based contextual dynamic pricing algorithm for feature-dependent price elasticity (heteroscedastic valuation) that achieves O(sqrt(dT log T)) regret under adversarial contexts, with a matching Omega(sqrt(dT)) lower bound.
Problem
Online contextual dynamic pricing where customer demand depends on product features and price, with elasticity coefficient that itself depends linearly on features, equivalently heteroscedastic valuation with Boolean-censored feedback.
Approach
Model feature-dependent price elasticity (x^T eta * p - x^T theta GLM demand, equivalently linear-fractional valuation with heteroscedastic noise); randomly perturb the greedy price by +/-Delta so the expected negative log-likelihood becomes strongly convex, then run online Newton step on it, which handles adversarial contexts.
Key results
- PwP achieves O(sqrt(dT log T)) regret upper bound and Omega(sqrt(dT)) matching lower bound, optimal up to log T factors.
- Empirically PwP shows about T^0.56 regret on stochastic contexts and T^0.513 on an adversarial context sequence, while modified RMLP-2 suffers linear regret under the adversarial attack.
- Original homoscedastic RMLP-2 shows regret slope 0.681 in a heteroscedastic environment, versus PwP at about T^0.536.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PwP with perturbed prices rather than modified RMLP-2 with concentrated pure exploration | Contextual pricing with adversarial contexts · Simulation, adversarial contexts | regret: O(T^{0.513}) vs. linear regret | Helped |
| Model feature-dependent elasticity (heteroscedasticity) instead of ignoring it | Contextual pricing in a heteroscedastic environment · Heteroscedastic environment | regret growth exponent: 0.681 vs. \sim O(T^{0.536}) | Helped |
| Use distributed exploration at every time step rather than fixed, concentrated pure-exploration rounds | Contextual pricing under adversarial contexts · Simulation, adversarial contexts | regret: O(T^{0.513}) vs. linear regret | Helped |
| Use PwP instead of modified RMLP-2 | Contextual pricing with stochastic contexts · Simulation, stochastic contexts | regret growth exponent: \sim O(T^{0.56}) for both algorithms | No clear effect |
Surprising findings
- The modified RMLP-2 baseline incurs linear regret under an oblivious adversarial context sequence, while PwP does not.
Limitations
- Requires a lower bound C_beta > 0 on the elasticity coefficient x^T eta, with regret scaling as 1/C_beta.
- Assumes log-concave noise CDF and bounded feature/parameter spaces; the theory assumes T known.
- Model misspecification experiments show PwP can incur linear regret as T grows.
Experimental setup
Datasets: simulated data (Gaussian contexts, Gaussian noise)
Benchmarks: simulated stochastic context sequences simulated adversarial context sequences
Metrics: cumulative regret log-log regret slope
Baselines: modified RMLP-2 original homoscedastic RMLP-2
Builds on: RMLP-2 log-likelihood surrogate loss for pricing (XW21) online Newton step follow the perturbed leader
Closest papers by meaning
- Improved Algorithms for Contextual Dynamic Pricing (NeurIPS 2024 · similarity 0.91)
- Contextual Dynamic Pricing with Heterogeneous Buyers (NeurIPS 2025 · similarity 0.91)
- Contextual Online Pricing with (Biased) Offline Data (NeurIPS 2025 · similarity 0.88)
- Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand (NeurIPS 2026 · similarity 0.88)
- Transfer Learning for Nonparametric Contextual Dynamic Pricing (ICML 2025 · similarity 0.88)
- Learning to price with resource constraints: from full information to machine-learned prices (NeurIPS 2025 · 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.