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

arXiv: https://arxiv.org/abs/2603.06851 · HTML: https://mlsanity.com/paper/2603.06851/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 25 references that are in the map.
- First posted on arXiv 6 Mar 2026.

## Builds on (most cited first, 9 of 9)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Empirical risk minimization for heavy-tailed losses](https://mlsanity.com/paper/1406.2462/) (2014)
- [Mean Estimation with Sub-Gaussian Rates in Polynomial Time](https://mlsanity.com/paper/1809.07425/) (2018)
- [Bilateral Trade: A Regret Minimization Perspective](https://mlsanity.com/paper/2109.12974/) (2021)
- [Bandit algorithms: Letting go of logarithmic regret for statistical robustness](https://mlsanity.com/paper/2006.12038/) (2020)
- [(Almost) Efficient Mechanisms for Bilateral Trading](https://mlsanity.com/paper/1604.04876/) (2016)
- [A Parametric Contextual Online Learning Theory of Brokerage](https://mlsanity.com/paper/2407.01566/) (2024)
- [A Tight Regret Analysis of Non-Parametric Repeated Contextual Brokerage](https://mlsanity.com/paper/2503.02646/) (2025)

## Built on by (most cited first, 1 of 1)

- [Repeated Bilateral Trade: The Quest for Fairness](https://mlsanity.com/paper/2606.15369/) (2026)

## Abstract (arXiv)

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 ∈ (1,2) or its scale σp, and -- in the nonparametric case -- none of the effective H"older smoothness β ∈ (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 ∈ (1,2), with possibly infinite variance. An epoch-based algorithm with truncated means achieves regret widetildeO(T(2-p)/p) in the parametric model and widetildeO(T1-2β(p-1)/(β p + d(p-1))) when the market value function is β-H"older, with matching Omega(·) 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 β ∈ (0,1], interpolating between the classical nonparametric rate at p=2 and the trivial linear rate as p → 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 mathbbE[g(m,V,W) - g(π,V,W)] ≤ L|m-π|2 -- no second moment is needed.