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

arXiv:2603.06851v3 Announce Type: replace-cross Abstract: 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 pi satisfies E[g(m,V,W) - g(pi,V,W)] le L|m-pi|^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-2eta(p-1)/(eta p + d(p-1))}) when the noise has finite p-th moment for p in (1,2) and the market value function is eta-Holder, and we establish a matching Omega(dot) 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 o 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, sigma_p) or the parameter norm, and a cell-width tournament extends this jointly to the tail and smoothness parameters when eta le d -- under full feedback, tail-adaptivity is free.

Source: arXiv cs.LG | 2026-07-27