Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret with Infinite Variance

摘要

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.