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

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 π satisfies E[g(m,V,W) - g(π,V,W)] L|m-π|^2 under bounded density alone. Combining this with truncated-mean estimation, we prove that an epoch-based algorithm achieves regret O(T^1-2β(p-1)/(βp + d(p-1))) when the noise has finite p-th moment for p (1,2) and the market value function is β-Hölder, and we establish a matching Ω() 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 1^+.

Reproductions