首次实现鲁棒定价中扰动与时间的解耦，显著降低后悔值。
Toward Optimal Regret in Robust Pricing: Decoupling Corruption and Time
- 提出一种鲁棒二分搜索算法，分离扰动次数与时间的影响。
- 已知扰动时后悔值为 $\mathcal{O}(C + \log T)$，未知时为 $\mathcal{O}(C + \log^2 T)$。
- 适合关注动态定价鲁棒性与低后悔学习的研究者。
我们设计了首个在鲁棒动态定价中将扰动量 $C$ 与时间跨度 $T$ 的依赖关系解耦的后悔保证。在动态定价中，卖家在 $T$ 轮内与连续买家交互，目标是最大化收益。每轮卖家设定价格 $p_t$，若买家未知估值 $v^ ext{⋆}$ 高于该价格则购买，卖家仅能观察到二元反馈 $\oldsymbol{1}\{ p_t \leq v^ ext{⋆} \}$。在鲁棒定价设定中，恶意对手可在最多 $C$ 轮内篡改反馈。即使学习者知道 $C$，现有最优后悔界为 $\mathcal{O}(C\log\log T)$（Gupta 等，2025）。如何实现 $C$ 与 $T$ 的解耦仍是开放问题。本文解决该问题：我们开发了一种鲁棒二分搜索变体，在 $C$ 已知时达到 $\mathcal{O}(C + \log T)$ 回悔，在 $C$ 未知时达到 $\mathcal{O}(C + \log^2 T)$ 回悔。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。