用有偏离线数据做动态定价,首次给出紧致的误差边界。
Contextual Online Pricing with (Biased) Offline Data
- 基于乐观面对不确定性原则设计算法,融合离线数据与在线学习。
- 在有偏数据下,理论证明误差随时间增长速度可控且最优。
- 适合有历史数据但质量不高的电商、平台类定价系统参考。
我们研究带有有偏离线数据的上下文在线定价问题。对于标量价格弹性情形,识别出衡量离线数据与未知在线最优之间距离的实例相关量 $δ^2$。我们证明,时间长度 $T$、偏倚界 $V$、离线数据量 $N$、数据分散度 $λ_{ ext{min}}( ildeΣ)$ 以及 $δ^2$ 共同决定统计复杂度。一种乐观面对不确定性(OFU)策略实现了极小最大值、实例相关的后悔界 $\tilde{\mathcal{O}}\big(d\sqrt{T} \wedge (V^2T + \frac{dT}{λ_{\text{min}}(\hatΣ) + (N \wedge T) δ^2})\big)$。对于一般价格弹性情形,建立了最坏情况下的极小最大值最优率 $\tilde{\mathcal{O}}\big(d\sqrt{T} \wedge (V^2T + \frac{dT}{λ_{\text{min}}(\hatΣ)})\big)$,并提出了广义 OFU 算法达到该速率。当偏倚界 $V$ 未知时,设计了一种鲁棒变体,始终保证次线性后悔,并在真实偏倚较小时显著优于纯在线方法。这些结果首次为存在有偏离线数据的上下文定价提供了紧致的后悔保证。我们的技术可直接推广至带偏倚离线数据的随机线性多臂老虎机,获得类似结果。
原文摘要 · Abstract (English)
We study contextual online pricing with biased offline data. For the scalar price elasticity case, we identify the instance-dependent quantity $δ^2$ that measures how far the offline data lies from the (unknown) online optimum. We show that the time length $T$, bias bound $V$, size $N$ and dispersion $λ_{\min}(\hatΣ)$ of the offline data, and $δ^2$ jointly determine the statistical complexity. An Optimism-in-the-Face-of-Uncertainty (OFU) policy achieves a minimax-optimal, instance-dependent regret bound $\tilde{\mathcal{O}}\big(d\sqrt{T} \wedge (V^2T + \frac{dT}{λ_{\min}(\hatΣ) + (N \wedge T) δ^2})\big)$. For general price elasticity, we establish a worst-case, minimax-optimal rate $\tilde{\mathcal{O}}\big(d\sqrt{T} \wedge (V^2T + \frac{dT }{λ_{\min}(\hatΣ)})\big)$ and provide a generalized OFU algorithm that attains it. When the bias bound $V$ is unknown, we design a robust variant that always guarantees sub-linear regret and strictly improves on purely online methods whenever the exact bias is small. These results deliver the first tight regret guarantees for contextual pricing in the presence of biased offline data. Our techniques also transfer verbatim to stochastic linear bandits with biased offline data, yielding analogous bounds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。