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

Q: What market setting and feedback model does the paper study?

The paper studies online contextual bilateral trade where each round reveals a context vector and valuations depend on an unknown function, while the broker receives full feedback by observing both traders’ valuations.

Q: How do the authors model heavy-tailed valuations and what key difficulty arises?

Valuations are assumed to have bounded conditional densities but infinite variance, motivated by heavy-tailed noise such as Student’s t with degrees of freedom ν<2. The resulting infinite-variance setting makes standard estimators like ordinary least squares fail.

Q: What estimator and strategy are used to achieve minimax regret?

The method uses epoch-based algorithms combined with truncated-mean estimation. This, together with the extended self-bounding property, yields the exact minimax regret rate up to logarithmic factors.

Jul 16, 2026

Upload by Lucas Martin

Bilateral trade with full feedback is studied under contextual settings where valuations have bounded conditional densities but infinite variance. The work extends Bachoc et al. self-bounding from bounded to real-valued valuations, deriving a regret bound driven by squared estimation error using bounded density alone and minimal moment assumptions. With epoch-based truncated-mean estimation, the paper identifies the exact minimax regret rate (up to logarithmic factors), interpolating between the classical nonparametric case at p=2 and the limiting linear regime as p approaches 1+. Additional assumptions ensure unique optimal pricing.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages16

Reading Time40 min

Abstract

Introduction

Related work

Setup and the Structural-Algorithmic Gap

arXiv :2603 .06851v2 [ stat .ML] 13 Jul 2026 Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret with Infinite Variance Hangyi Zhao [hyz0815@stanford. edu](hyz0815@stanford. edu) July 14, 2026 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 π satisfies E[g(m, V, W) − g(π, V, W)] ≤ L|m − π|2 under bounded density alone. Combining this with truncated-mean estimation, we prove that an epoch-based apbrn(it1d,hm2vi)a acanAhdssietoveheuadsm’rsegarmretketetha(Tluw2βuan(1ioe)/nd-(βsipsu+pdβp(1o¨lm)d) ) werixt,haurenndecthwoneestnerostuicsatebiolhaishnsfiaOnmuriteatrepchsu-tilthnsmog Ωchamr( ae)cnlttoefwrioezrre the exact minimax rate for this problem, interpolating between the classical nonparametric rate at p=2 and the trivial linear rate as p → 1+ . 1 Introduction Bilateral trade—the simplest two-sided market—requires a broker to set prices between a buyer anda seller whose private valuations are unknown. The celebrated impossibility theorem of Myerson and Satterthwaite [13] shows that no incentive-compatible, individually rational, budget-balanced mechanism can achieve full efficiency in a single round. This spurred a rich literature on approximate mechanisms [4] and, more recently, on online bilateral trade, where the broker learns from repeated interactions and regret—the cumulative loss from suboptimal pricing—replaces the single-shot efficiency objective. Bachoc, Cesari, and Colomboni [3] initiated the study of contextual online bilateral trade, where a public context vector xt arrives each round and trader valuations depend on an unknown function m(xt) . Under bounded noise densities and finite variance, they established an O (Ld log T) pawaregrasrmsuetetbsofriceqprurieecgrntingetlyabtrtoueaπndteindstaiennadd[a2o]nf (LdyatsTtrm)uobctstouurLna| dlmidigπe|rh2t, twisreotd-bhuiectsinfeeglefrdb-boegaureckndtc; itnohgnetnprrooolnptpeoarrtymae:mtanetheersicetsxpimeteatctitineogdn. However, their algorithms rely on ordinary least squares, which requires finite variance (E[ξ2] < ∞ ) . In many applications—financial markets, insurance, real estate—valuations exhibit heavy tails well-modeled by Student’s t (ν) with ν < 2, where the variance is infinite [11] . This raises a natural question: what regret is achievable when the noise has bounded density but infinite variance? We answer this question with three contributions. (C1) We extend the self-bounding property from bounded to real-valued valuations (Lemma 3.1), showing that bounded density alone—without any moment condition beyond E[|ξ|] < ∞—suffices to control regret via squared estimation error.(C2) We design epoch-based algorithms using truncated-mean estimation [5] and prove tight rceegasstreaeb,tlrwisathhesermea: t(g(2(po,w)/2p)er)iins tbothheunedpmsaroviammena Aettsripsoc cauaraads’emsaetmneedrthnd(Td[ 11]2βisc(poe)/in(βpHoedddw(s)ma))iofinoxtethhd-enseunossppnopra(tramC3mi)xettrWuricee construction (Proposition 6.1, Remark 6.2), proving that our rates are minimax optimal in T up to logarithmic factors for nondegenerate class parameters (the parametric dimension dependence of the lower bound is left open; Remark 6.2) . The constructed instances also satisfy Assumption 2.4, a mild regularity condition at zero under which the optimal price is unique. 1.1 Related work Bilateral trade. Online bilateral trade was initiated by Cesa-Bianchi et al. [7] and has since been studied under various feedback models and distributional assumptions; see [3] and references therein. The contextual setting was introduced in [3] (parametric) and [2] (nonparametric), both under finite-variance noise. Our work extends this line to the infinite-variance regime. Robust mean estimation. Estimation un

FAQs

What market setting and feedback model does the paper study?

The paper studies online contextual bilateral trade where each round reveals a context vector and valuations depend on an unknown function, while the broker receives full feedback by observing both traders’ valuations.

How do the authors model heavy-tailed valuations and what key difficulty arises?

Valuations are assumed to have bounded conditional densities but infinite variance, motivated by heavy-tailed noise such as Student’s t with degrees of freedom ν<2. The resulting infinite-variance setting makes standard estimators like ordinary least squares fail.

What estimator and strategy are used to achieve minimax regret?

The method uses epoch-based algorithms combined with truncated-mean estimation. This, together with the extended self-bounding property, yields the exact minimax regret rate up to logarithmic factors.

Jul 16, 2026

Upload by Lucas Martin