Toward Optimal Regret in Robust Pricing: Decoupling Corruption and Time

arXiv:2605.08290v1 Announce Type: cross Abstract: 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 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 I left{ p_t leq 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+log^2 T) when the corruption is unknown.

Source: arXiv cs.AI | 2026-05-12