Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret without a Variance Bound

Abstract

In contextual bilateral trade under full feedback, the posted price does not affect which valuations are observed. We show that in this model such action-independent feedback removes the polynomial adaptation penalty familiar from heavy-tailed bandits: fully parameter-free algorithms attain the oracle minimax $T$-exponents up to logarithmic factors, with no knowledge of the moment order $p \in (1,2)$ or its scale $\sigma_p$, and -- in the nonparametric case -- none of the effective H\"older smoothness $\beta \in (0,1]$. The statistic that makes model selection possible is a paired squared-loss difference, whose noise-square term cancels exactly, leaving noise damped by the candidate gap. The resulting bilateral-trade regret rates are new. Trader valuations have bounded conditional densities and heavy tails -- finite $p$-th moments for some $p \in (1,2)$, with possibly infinite variance. An epoch-based algorithm with truncated means achieves regret $\widetilde{O}(T^{(2-p)/p})$ in the parametric model and $\widetilde{O}(T^{1-2\beta(p-1)/(\beta p + d(p-1))})$ when the market value function is $\beta$-H\"older, with matching $\Omega(\cdot)$ lower bounds -- under a mild nondegeneracy condition -- via Assouad's method and a fixed-support mixture construction -- characterizing the minimax rate in $T$ up to logarithmic factors over the effective smoothness range $\beta \in (0,1]$, interpolating between the classical nonparametric rate at $p{=}2$ and the trivial linear rate as $p \to 1^+$. The enabling structural step extends the self-bounding property of Bachoc et al. (ICML 2025) from bounded to real-valued valuations: within our conditionally independent, conditionally centered noise model, bounded conditional densities and finite first moments suffice for the expected regret of any price $\pi$ to satisfy $\mathbb{E}[g(m,V,W) - g(\pi,V,W)] \le L|m-\pi|^2$ -- no second moment is needed.