在重尾估值下，实现无需参数知识的最优交易后悔率
Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret with Infinite Variance
- 基于截断均值与自界定性质，设计分阶段算法应对无限方差估值
- 达到$ ilde{O}(T^{1-2β(p-1)/(βp + d(p-1))})$的后悔率，匹配理论下界
- 完全免调参：中位数均值定价可自动适应尾部与平滑性
研究在完整反馈下，条件于上下文时交易者估值具有有界密度但无限方差的上下文双边交易问题。我们首先将Bachoc等（ICML 2025）的自界定性质从有界估值推广至实值估值，证明在仅需有界密度和有限一阶矩条件下，任意价格π的期望后悔满足$E[g(m,V,W) - g(π,V,W)] \ leq L|m-π|^2$。结合截断均值估计，我们证明一种分阶段算法在噪声具有有限$p$阶矩（$p \in (1,2)$）且市场价值函数为$β$-Hölder时，可实现后悔率$ ilde{O}(T^{1-2β(p-1)/(βp + d(p-1))})$，并利用Assouad方法与固定支撑混合构造建立了匹配的$Ω(ullet)$下界。结果在对数因子内刻画了该问题的极小极大率，介于$ p=2 $时的经典非参数率与$ p \to 1^+ $时的平凡线性率之间。最后，我们证明这些速率可通过完全免参数的算法实现：中位数均值定价无需知道$(p, σ_p)$或参数范数即可达到参数化最优率；当$β\le d$时，单元宽度锦标赛可联合适应尾部与光滑性参数——在完整反馈下，尾部自适应是免费的。
原文摘要 · Abstract (English)
We study contextual bilateral trade under full feedback when, conditionally on the context, trader valuations have bounded density but infinite variance. We first extend the self-bounding property of Bachoc et al. (ICML 2025) from bounded to real-valued valuations, showing that the expected regret of any price $π$ satisfies $E[g(m,V,W) - g(π,V,W)] \le L|m-π|^2$ under bounded density and finite first moments alone. Combining this with truncated-mean estimation, we prove that an epoch-based algorithm achieves regret $\widetilde{O}(T^{1-2β(p-1)/(βp + d(p-1))})$ when the noise has finite $p$-th moment for $p \in (1,2)$ and the market value function is $β$-Hölder, and we establish a matching $Ω(\cdot)$ lower bound via Assouad's method with a fixed-support mixture construction. Our results characterize the minimax rate in $T$ for this problem up to logarithmic factors, interpolating between the classical nonparametric rate at $p=2$ and the trivial linear rate as $p \to 1^+$. Finally, we show these rates are achievable by fully parameter-free algorithms: median-of-means pricing attains the parametric oracle rate with no knowledge of $(p, σ_p)$ or the parameter norm, and a cell-width tournament extends this jointly to the tail and smoothness parameters when $β\le d$ -- under full feedback, tail-adaptivity is free.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。