# Towards Agnostic Feature-based Dynamic Pricing: Linear Policies vs Linear Valuation with Unknown Noise

arXiv: https://arxiv.org/abs/2201.11341 · HTML: https://mlsanity.com/paper/2201.11341/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 26 references that are in the map.
- First posted on arXiv 27 Jan 2022.

## Builds on (most cited first, 8 of 8)

- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Dynamic Pricing in High-dimensions](https://mlsanity.com/paper/1609.07574/) (2016)
- [Multidimensional Binary Search for Contextual Decision-Making](https://mlsanity.com/paper/1611.00829/) (2016)
- [Contextual Search via Intrinsic Volumes](https://mlsanity.com/paper/1804.03195/) (2018)
- [Policy Optimization Using Semi-parametric Models for Dynamic Pricing](https://mlsanity.com/paper/2109.06368/) (2021)
- [Logarithmic Regret in Feature-based Dynamic Pricing](https://mlsanity.com/paper/2102.10221/) (2021)
- [Distribution-free Contextual Dynamic Pricing](https://mlsanity.com/paper/2109.07340/) (2021)
- [On Dynamic Pricing with Covariates](https://mlsanity.com/paper/2112.13254/) (2021)

## Built on by (most cited first, 21 of 21)

- [Near-Optimal Differentially Private Reinforcement Learning](https://mlsanity.com/paper/2212.04680/) (2022)
- [Improved Algorithms for Contextual Dynamic Pricing](https://mlsanity.com/paper/2406.11316/) (2024)
- [Doubly Fair Dynamic Pricing](https://mlsanity.com/paper/2209.11837/) (2022)
- [Pricing with Contextual Elasticity and Heteroscedastic Valuation](https://mlsanity.com/paper/2312.15999/) (2023)
- [Density-Based Algorithms for Corruption-Robust Contextual Search and Convex Optimization](https://mlsanity.com/paper/2206.07528/) (2022)
- [Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewards](https://mlsanity.com/paper/2306.01121/) (2023)
- [Online learning in bandits with predicted context](https://mlsanity.com/paper/2307.13916/) (2023)
- [Online Pricing and Allocation with Demand Learning and Fulfillment Cost](https://mlsanity.com/paper/2501.18049/) (2025)
- [Dynamic Pricing in the Linear Valuation Model using Shape Constraints](https://mlsanity.com/paper/2502.05776/) (2025)
- [Dynamic Pricing with Adversarially-Censored Demands](https://mlsanity.com/paper/2502.06168/) (2025)
- [Contextual Dynamic Pricing with Strategic Buyers](https://mlsanity.com/paper/2307.04055/) (2023)
- [Learning to Price with Resource Constraints: From Full Information to Machine-Learned Prices](https://mlsanity.com/paper/2501.14155/) (2025)
- [Contextual Online Bilateral Trade](https://mlsanity.com/paper/2602.12903/) (2026)
- [Minimax Optimality in Contextual Dynamic Pricing with General Valuation Models](https://mlsanity.com/paper/2406.17184/) (2024)
- [Transfer Faster, Price Smarter: Minimax Dynamic Pricing under Cross-Market Preference Shift](https://mlsanity.com/paper/2505.17203/) (2025)
- [Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand](https://mlsanity.com/paper/2605.05609/) (2026)
- [Parameter-Adaptive Dynamic Pricing](https://mlsanity.com/paper/2503.00929/) (2025)
- [Contextual Learning for Stochastic Optimization](https://mlsanity.com/paper/2505.16829/) (2025)
- [Contextual Dynamic Pricing with Heterogeneous Buyers](https://mlsanity.com/paper/2512.09513/) (2025)
- [Learning to Price and Stock Under Contextual and Censored Demand](https://mlsanity.com/paper/2609.06083/) (2026)
- [Optimal Nonparametric Dynamic Pricing with Censored Demand and Adversarial Inventory](https://mlsanity.com/paper/2609.32949/) (2026)

## Abstract (arXiv)

In feature-based dynamic pricing, a seller sets appropriate prices for a sequence of products (described by feature vectors) on the fly by learning from the binary outcomes of previous sales sessions ("Sold" if valuation ≥ price, and "Not Sold" otherwise). Existing works either assume noiseless linear valuation or precisely-known noise distribution, which limits the applicability of those algorithms in practice when these assumptions are hard to verify. In this work, we study two more agnostic models: (a) a "linear policy" problem where we aim at competing with the best linear pricing policy while making no assumptions on the data, and (b) a "linear noisy valuation" problem where the random valuation is linear plus an unknown and assumption-free noise. For the former model, we show a tildeTheta(dfrac13Tfrac23) minimax regret up to logarithmic factors. For the latter model, we present an algorithm that achieves an tildeO(Tfrac34) regret, and improve the best-known lower bound from Omega(Tfrac35) to tildeOmega(Tfrac23). These results demonstrate that no-regret learning is possible for feature-based dynamic pricing under weak assumptions, but also reveal a disappointing fact that the seemingly richer pricing feedback is not significantly more useful than the bandit-feedback in regret reduction.