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

arXiv:2603.06851 · stat.ML, cs.GT, cs.LG · Submitted 2026-03-06 · Read on arXiv

stat.ML, cs.GT, cs.LG

Submitted: 2026-03-06

Updated: 2026-09-09

Comments: 29 pages. v4: title changed (v3: Minimax Regret with Infinite Variance); abstract and introduction reframed around the feedback-interface message; adds a formal parametric two-point lower bound and corollaries on the price of adaptivity; corrections to the lower-bound construction and epoch assembly; related work expanded

License: http://creativecommons.org/licenses/by/4.0/

The gist: In contextual bilateral trade under full feedback, the posted price does not affect which valuations are observed.

Terminology

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 σ p, and -- in the nonparametric case -- none of the effective Hölder smoothness β 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 (T(2-p)/p) in the parametric model and (T 1-2β(p-1)/(βp + d(p-1))) when the market value function is β-Hölder, with matching Ω(times) 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 β 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 π to satisfy E[g(m,V,W) - g(π,V,W)] Lm-π squared -- no second moment is needed.

Sources

Related papers