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

arXiv:2603.06851v1 Announce Type: new
Abstract: We study contextual bilateral trade under full feedback when 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 $pi$ satisfies $mathbb{E}[g(m,V,W) – g(pi,V,W)] le L|m-pi|^2$ under bounded density alone. Combining this with truncated-mean estimation, we prove that an epoch-based algorithm achieves regret $widetilde{O}(T^{1-2beta(p-1)/(beta p + d(p-1))})$ when the noise has finite $p$-th moment for $p in (1,2)$ and the market value function is $beta$-H”older, and we establish a matching $Omega(cdot)$ lower bound via Assouad’s method with a smoothed moment-matching construction. Our results characterize the exact minimax rate for this problem, interpolating between the classical nonparametric rate at $p=2$ and the trivial linear rate as $p to 1^+$.