aiqbench analysis
This research advances the theoretical foundations of contextual bilateral trade by deriving minimax regret bounds for scenarios involving heavy-tailed distributions with infinite variance. The authors demonstrate that fully parameter-free algorithms, such as median-of-means pricing, can achieve optimal rates without prior knowledge of tail parameters or smoothness constants under full feedback conditions. These findings are significant for machine learning practitioners developing robust trading agents and online decision-making systems where data outliers cannot be ignored.
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-2\beta(p-1)/(\beta p + d(p-1))})$ when the noise has finite $p$-th moment for $p \in (1,2)$ and the market value function is $\beta$-H\"older, and we establish a matching $\Omega(\cdot)$ 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 \to 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 $\beta \le d$ -- under full feedback, tail-adaptivity is free.
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-2\beta(p-1)/(\beta p + d(p-1))})$ when the noise has finite $p$-th moment for $p \in (1,2)$ and the market value function is $\beta$-Hölder, and we establish a matching $\Omega(\cdot)$ 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 \to 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 $\beta \le d$ -- under full feedback, tail-adaptivity is free.
Machine Learning (stat.ML); Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG)
arXiv:2603.06851 [stat.ML]
(or arXiv:2603.06851v3 [stat.ML] for this version)
Full text under the publisher's open licence · 216 words
Related coverage
Prediction with Expert Advice under Heavy-Tailed Losses
arXiv · Oct 14, 2026
Parameter-Free Dynamic Regret for Online Convex Optimization under Heavy-Tailed Noise
arXiv · Jul 31, 2026
Repeated Bilateral Trade: The Quest for Fairness
arXiv · Jun 16, 2026
Futures Drop, Yields And Oil Jump Ahead Of Iran UN Address As Trump - Xi Summit Looms
zerohedge.com · Sep 23, 2026