# Logarithmic Regret in Feature-based Dynamic Pricing

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 60 references that are in the map.
- First posted on arXiv 20 Feb 2021.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [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)
- [Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices](https://mlsanity.com/paper/1912.10754/) (2019)
- [Dynamic Pricing with Demand Covariates](https://mlsanity.com/paper/1604.07463/) (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)
- [A Primal-dual Learning Algorithm for Personalized Dynamic Pricing with an Inventory Constraint](https://mlsanity.com/paper/1812.09234/) (2018)

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

- [Towards Agnostic Feature-based Dynamic Pricing: Linear Policies vs Linear Valuation with Unknown Noise](https://mlsanity.com/paper/2201.11341/) (2022)
- [Dynamic pricing and assortment under a contextual MNL demand](https://mlsanity.com/paper/2110.10018/) (2021)
- [Learning to Bid in Contextual First Price Auctions](https://mlsanity.com/paper/2109.03173/) (2021)
- [Near-Optimal Differentially Private Reinforcement Learning](https://mlsanity.com/paper/2212.04680/) (2022)
- [Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update](https://mlsanity.com/paper/2507.11847/) (2025)
- [On Dynamic Pricing with Covariates](https://mlsanity.com/paper/2112.13254/) (2021)
- [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)
- [A Parametric Contextual Online Learning Theory of Brokerage](https://mlsanity.com/paper/2407.01566/) (2024)
- [Online Pricing and Allocation with Demand Learning and Fulfillment Cost](https://mlsanity.com/paper/2501.18049/) (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)
- [Learning to Price Homogeneous Data](https://mlsanity.com/paper/2407.05484/) (2024)
- [Dynamic Assortment Selection and Pricing with Censored Preference Feedback](https://mlsanity.com/paper/2504.02324/) (2025)
- [Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand](https://mlsanity.com/paper/2605.05609/) (2026)
- [Smoothness-Adaptive Dynamic Pricing with Nonparametric Demand Learning](https://mlsanity.com/paper/2310.07558/) (2023)
- [Offline Local Search for Online Stochastic Bandits](https://mlsanity.com/paper/2604.09423/) (2026)
- [Learning Choice Model Trees for Feature-Based Multi-Product Pricing: Exact Optimization and Field Evidence](https://mlsanity.com/paper/2609.16952/) (2026)
- [Optimal Nonparametric Dynamic Pricing with Censored Demand and Adversarial Inventory](https://mlsanity.com/paper/2609.32949/) (2026)

## Abstract (arXiv)

Feature-based dynamic pricing is an increasingly popular model of setting prices for highly differentiated products with applications in digital marketing, online sales, real estate and so on. The problem was formally studied as an online learning problem [Javanmard & Nazerzadeh, 2019] where a seller needs to propose prices on the fly for a sequence of T products based on their features x while having a small regret relative to the best -- "omniscient" -- pricing strategy she could have come up with in hindsight. We revisit this problem and provide two algorithms (EMLP and ONSP) for stochastic and adversarial feature settings, respectively, and prove the optimal O(dlogT) regret bounds for both. In comparison, the best existing results are Oleft(minleftfrac1λmin2logT, √Trightright) and O(T2/3) respectively, with λmin being the smallest eigenvalue of mathbbE[xxT] that could be arbitrarily close to 0. We also prove an Omega(√T) information-theoretic lower bound for a slightly more general setting, which demonstrates that "knowing-the-demand-curve" leads to an exponential improvement in feature-based dynamic pricing.