# Toward Optimal Regret in Robust Pricing: Decoupling Corruption and Time

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 18 references that are in the map.
- First posted on arXiv 8 May 2026.

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

- [Dynamic Pricing in High-dimensions](https://mlsanity.com/paper/1609.07574/) (2016)
- [Learning Prices for Repeated Auctions with Strategic Buyers](https://mlsanity.com/paper/1311.6838/) (2013)
- [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)
- [Contextual Search in the Presence of Adversarial Corruptions](https://mlsanity.com/paper/2002.11650/) (2020)
- [Density-Based Algorithms for Corruption-Robust Contextual Search and Convex Optimization](https://mlsanity.com/paper/2206.07528/) (2022)
- [The entropy of lies: playing twenty questions with a liar](https://mlsanity.com/paper/1811.02177/) (2018)

## Abstract (arXiv)

We design the first regret guarantees for robust dynamic pricing that decouple the dependence on the corruption C and the time horizon T. In dynamic pricing, a seller with unlimited supply of a good interacts with a stream of buyers over ( T ) rounds, with the goal of maximizing revenue. At each round t, the seller posts a price pt, and the buyer purchases the good only if their unknown valuation v^star exceeds this price. The seller observes only the binary feedback mathbbI left pt ≤ v^star right, indicating whether a sale occurred. In the robust pricing setting, a malicious adversary is allowed to corrupt this feedback in at most C rounds. Even if the learner knows the corruption C, the best known regret bound is O(Cloglog T) by Gupta et al. [2025]. This leaves as an open problem to ``decouple'' the dependence on C and T. In this work, we resolve this open problem. In particular, we develop a robust variant of binary search that achieves regret O(C+log T) when the corruption C is known and O(C+log2 T) when the corruption is unknown.