Research map / Bandits and online learning / Online convex optimization and games
Learning to Price Homogeneous Data
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 online data pricing with N homogeneous data points and m buyer types, giving discretization schemes for pricing curves and UCB/FTPL-based learning algorithms under asymmetric (purchase-revealed) feedback.
Problem
Revenue-optimal pricing of homogeneous data to unknown buyer type distributions over T rounds, where buyers reveal their type only upon purchase; prior discretizations scale exponentially in N or in 1/epsilon.
Approach
Shows any monotone price curve can be replaced by an m-step curve with no less revenue, builds discretizations of size polynomial in N/epsilon (and smaller under smoothness or diminishing returns), and designs a UCB (stochastic) and FTPL with purchase-dependent rewards (adversarial) that handle the asymmetric feedback.
Key results
- Stochastic setting: UCB-based algorithm achieves O~(m sqrt(T)) regret for any discretization.
- Adversarial setting: FTPL-based algorithm achieves O~(m^{3/2} sqrt(T)) regret.
- Monotone discretization size O~((N/epsilon)^m), vs prior exponential-in-N or epsilon^{-2} log epsilon^{-1} exponent schemes.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the proposed monotone discretization instead of the prior exponential discretization | Data-pricing discretization · Finite buyer types | discretization size: \bigOtilde(2^N \epsilon^{-N}) -> \bigOtilde(N^m\epsilon^{-m}) | Helped |
| add the smoothness assumption and use the smooth discretization | Data-pricing discretization · Smooth monotonic valuations | discretization size: \bigOtilde(N^m\epsilon^{-m}) -> \bigOtilde\left( L^m\epsilon^{-2m} \right) | Helped |
| add the diminishing-returns assumption and use its discretization | Data-pricing discretization · Diminishing returns | discretization size: \bigOtilde\left(J^m \epsilon^{-3m} \log^m N\right) | Helped |
| use the proposed discretization schemes instead of prior-work schemes | Adversarial online data pricing · Adversarial | regret bound: \bigOtilde(m T^{\nicefrac{3}{4}}) -> \bigOtilde(m^{\nicefrac{3}{2}}\sqrt{T}) | Helped |
| use the proposed smooth discretization rather than the monotone-only discretization | Online data pricing · Smooth valuations | complexity per iteration: \bigOtilde\!\rbr{ \rbr{\frac{N}{m}} ^m T^{\,\nicefrac{m}{2}}} -> \bigOtilde\rbr{\rbr{LT}^m } | Helped |
| use the proposed diminishing-returns discretization rather than the monotone-only discretization | Online data pricing · Diminishing returns | complexity per iteration: \bigOtilde\!\rbr{ \rbr{\frac{N}{m}} ^m T^{\,\nicefrac{m}{2}}} -> \bigOtilde(J^m T^{\nicefrac{3m}{2}}) | Mixed |
Limitations
- Computational complexity is exponential in the number of types m (strong NP-hardness).
- Assumes seller knows valuation curves of all types.
- Adversarial regret carries an extra sqrt(m) factor over full-information rates.
Experimental setup
Metrics: regret discretization size time complexity per iteration
Baselines: EXP3 prior discretization schemes for unit-demand pricing (PTAS) single-item asymmetric feedback UCB
Builds on: UCB FTPL EXP3 ordered item pricing
Closest papers by meaning
- Learning to price with resource constraints: from full information to machine-learned prices (NeurIPS 2025 · similarity 0.87)
- Non-Linear Pricing Restores Tractability for a Data Seller (NeurIPS 2026 · similarity 0.87)
- Online Learning under Budget and ROI Constraints via Weak Adaptivity (ICML 2024 · similarity 0.86)
- Contextual Online Pricing with (Biased) Offline Data (NeurIPS 2025 · similarity 0.86)
- Improved learning rates in multi-unit uniform price auctions (NeurIPS 2024 · similarity 0.86)
- A Parametric Contextual Online Learning Theory of Brokerage (ICML 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.