arXiv:2607.11210 · v2

Decoupling Corruption and Horizon in Robust Contextual Pricing

首次提交 2026-07-13 16:02

版本更新 2026-11-02 20:38

雷达观测 2026-11-04 23:42

摘要

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.