Research map / Bandits and online learning / Online convex optimization and games
Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand
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 CMRUP, a polynomial-time contextual pricing algorithm (randomized Stage-1 estimation, conservative markdown residual-grid probing, redirect-UCB) claiming O~(T^{2/3}) regret under agnostic non-Lipschitz bounded noise, plus small synthetic experiments.
Problem
Contextual dynamic pricing with linear valuations and bounded agnostic noise whose demand curve may be discontinuous (atoms, jumps); prior best regret was O~(T^{3/4}) and smoothness-based transfer fails.
Approach
Estimate the linear component with uniformly randomized prices, then use a conservative markdown so each binary observation becomes a one-sided probe of adjacent survival levels on a one-dimensional residual grid; a UCB rule redirects to the left once confidence radii reach grid scale, paying discontinuity costs only in a limited exploration period.
Key results
- On uniform noise, CMRUP fitted regret exponent 0.67 vs 0.78 for D2-EXP4.
- On cliff noise (atom of 0.3 at w=0), CMRUP exponent 0.56 vs 0.77 for D2-EXP4.
- Claimed theoretical regret O~(T^{2/3}) for agnostic bounded noise, matching lower bounds up to logs.
Surprising findings
- Cliff-noise instance yields a lower fitted exponent than smooth uniform noise for CMRUP (0.56 vs 0.67).
Limitations
- Requires bounded noise support, i.i.d. well-conditioned stochastic contexts, and a price buffer away from boundaries.
- Experiments are small synthetic rate-verification only; D2-EXP4 run as a sampled-policy approximation.
- Horizon-dependent grid and stage lengths; doubling trick only sketched.
Experimental setup
Datasets: synthetic contextual pricing streams (uniform noise, cliff noise)
Benchmarks: synthetic uniform-noise pricing instance synthetic cliff-noise pricing instance
Metrics: cumulative pseudo-regret fitted log-log scaling exponent
Baselines: D2-EXP4
Builds on: D2-EXP4 UCB
Closest papers by meaning
- Contextual Dynamic Pricing with Heterogeneous Buyers (NeurIPS 2025 · similarity 0.91)
- Improved Algorithms for Contextual Dynamic Pricing (NeurIPS 2024 · similarity 0.91)
- Contextual Online Pricing with (Biased) Offline Data (NeurIPS 2025 · similarity 0.90)
- Transfer Faster, Price Smarter: Minimax Dynamic Pricing under Cross-Market Preference Shift (NeurIPS 2025 · similarity 0.89)
- Pricing with Contextual Elasticity and Heteroscedastic Valuation (ICML 2024 · similarity 0.88)
- Transfer Learning for Nonparametric Contextual Dynamic Pricing (ICML 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.