Toward Optimal Regret in Robust Pricing: Decoupling Corruption and Time

We design the first regret guarantees for robust dynamic pricing which decouples 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 $p_t$, and the buyer purchases the good only if their unknown valuation $v^{\star }$ exceeds this price. The seller observes only the binary feedback $\mathbb{I}[p_t\le v^{\star }]$, 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 $\mathcal{O}(C\log \log T)$ by Gupta et al. [2025]. They left 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 $\mathcal{O}(C+\log T)$ when the corruption $C$ is known and $\mathcal{O}(C+{\log }^{2}T)$ when the corruption is unknown.