# Localized exploration in contextual dynamic pricing achieves dimension-free regret

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 35 references that are in the map.
- First posted on arXiv 26 Dec 2024.

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

- [A Survey of Exploration Methods in Reinforcement Learning](https://mlsanity.com/paper/2109.00157/) (2021)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Dynamic Pricing with Demand Covariates](https://mlsanity.com/paper/1604.07463/) (2016)
- [Pseudo-Labeling for Kernel Ridge Regression under Covariate Shift](https://mlsanity.com/paper/2302.10160/) (2023)
- [Fairness-aware Online Price Discrimination with Nonparametric Demand Models](https://mlsanity.com/paper/2111.08221/) (2021)
- [High-Dimensional Dynamic Pricing under Non-Stationarity: Learning and Earning with Change-Point Detection](https://mlsanity.com/paper/2303.07570/) (2023)
- [Policy evaluation from a single path: Multi-step methods, mixing and mis-specification](https://mlsanity.com/paper/2211.03899/) (2022)

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

- [On Non-Stationary Dynamic Pricing: Adaptivity and Optimality](https://mlsanity.com/paper/2607.24115/) (2026)

## Abstract (arXiv)

We study the problem of contextual dynamic pricing with a linear demand model. We propose a novel localized exploration-then-commit (LetC) algorithm which starts with a pure exploration stage, followed by a refinement stage that explores near the learned optimal pricing policy, and finally enters a pure exploitation stage. The algorithm is shown to achieve a minimax optimal, dimension-free regret bound when the time horizon exceeds a polynomial of the covariate dimension. Furthermore, we provide a general theoretical framework that encompasses the entire time spectrum, demonstrating how to balance exploration and exploitation when the horizon is limited. The analysis is powered by a novel critical inequality that depicts the exploration-exploitation trade-off in dynamic pricing, mirroring its existing counterpart for the bias-variance trade-off in regularized regression. Our theoretical results are validated by extensive experiments on synthetic and real-world data.