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

2026-03-10 · Source: stat.ML updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning · Depth: Expert, long

Summary

This research investigates contextual bilateral trade where trader valuations exhibit heavy-tailed noise, specifically with infinite variance but bounded density and finite $p$-th moments for $p \in (1,2)$. The authors extend the "self-bounding property" from prior work, demonstrating that expected regret is bounded by $L|m-\pi|^2$ even with real-valued, heavy-tailed valuations, requiring only bounded density and $\mathbb{E}[|\xi|]<\infty$. They propose an epoch-based algorithm utilizing truncated-mean estimation to achieve tight regret rates. For the parametric case, the algorithm yields $\widetilde{O}(T^{(2-p)/p})$ regret, while the nonparametric setting with $\beta$-Hölder market value functions achieves $\widetilde{O}(T^{1-2\beta(p-1)/(\beta p+d(p-1))})$ regret. These rates are proven to be minimax optimal through matching lower bounds derived using Assouad's method and a smoothed moment-matching construction, characterizing the exact minimax rate for this problem and interpolating between classical nonparametric rates at $p=2$ and linear rates as $p \to 1^{+}$.

Key takeaway

For AI Researchers and Scientists developing online pricing mechanisms in markets with heavy-tailed valuation noise (e.g., financial or real estate), your models must account for infinite variance. The generalized self-bounding property allows you to focus on robust mean estimation, suggesting that algorithms using truncated-mean estimators are optimal. Implement epoch-based learning with these estimators to achieve minimax regret rates, especially when $p<2$, as standard OLS approaches will fail.

Key insights

Bilateral trade regret with heavy-tailed valuations is bounded by squared estimation error, enabling robust learning.

Principles

• Bounded density alone controls regret via squared estimation error.
• Truncated-mean estimation is effective for heavy-tailed data.
• Minimax rates interpolate between finite and infinite variance regimes.

Method

An epoch-based algorithm uses truncated-mean estimation on score vectors or local averages to estimate valuations, then sets prices based on these estimates for the current epoch.

In practice

• Use truncated-mean estimators for financial market data with heavy tails.
• Apply epoch-based learning for online pricing in two-sided markets.

Topics

• Bilateral Trade
• Heavy-Tailed Distributions
• Minimax Regret
• Truncated-Mean Estimation
• Contextual Online Learning

Best for: AI Researcher, AI Scientist, Research Scientist

Related on AIssential

• Toward Simultaneously Optimal Regret in U-Calibration — A new U-calibration algorithm achieves simultaneously optimal regret rates for both general and smooth proper loss functions.
• On Stability and Decomposition of Sample Quantiles under Heavy-Tailed Distributions — This paper addresses the instability of sample quantiles, particularly Value-at-Risk (VaR), when estimated parameters like projection direction and quantile threshold are derived from heavy-tailed financial returns.
• The Boosting Paradox — Machine learning struggles in finance due to market adaptivity, adversarial competition, and irreducible uncertainty, despite theoretical power.
• Revisiting Active Sequential Prediction-Powered Mean Estimation — Optimal confidence width in active sequential prediction-powered mean estimation favors a high constant query probability.
• Refined Risk Bounds for Unbounded Losses via Transductive Priors — Transductive priors and exponential weights yield tighter risk bounds for unbounded losses in sequential learning.
• Regret-Based $(ε,δ)$-optimal Stopping Criteria for Bayesian Optimization — New regret bounds enable provably optimal stopping for Bayesian Optimization, ensuring ε-optimality with high probability.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by stat.ML updates on arXiv.org.