Kalana Kalupahana, Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi
原文摘要
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 $\mathbb{I} \left\{ p_t \leq v^\star \right\}$, indicating whether a sale occurred. In the \emph{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]. 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 $\mathcal{O}(C+\log T)$ when the corruption $C$ is known and $\mathcal{O}(C+\log^2 T)$ when the corruption is unknown.
We study robust repeated contextual pricing, where valuations depend linearly on the features. At each round $t\in[T]$, a seller observes a context, posts a price, and receives only a possibly corrupted binary sale feedback. When the seller knows an upper bound $C$ on the number of corrupted rounds, we design an algorithm with regret $\mathcal O(Cd+d^2\log T)$, where $d$ is the context dimension. This is the first guarantee for robust contextual pricing that separates the dependence on the corruption budget $C$ from the horizon $T$, closing the problem left open by Gupta, Guruganesh, Paes Leme, and Schneider (2025). In this work, we go even further by developing a randomized algorithm that attains regret of order $\mathcal{O}(Cd+d^2\log T+d\log^2T)$ with high probability, without knowing the number of corrupted rounds $C$. Finally, we show that randomized algorithms that do not know $C$ cannot guarantee regret of order $\mathcal{O}(C)+o(\log^2 T)$ with high probability, even in the one dimensional non-contextual case.