Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret without a Variance Bound
Updated 7 h ago · first seen 11 Sept 2026
paper_01M294FT2QPSMT4G0GN4CNXJHH
- Published
- 11 Sept 2026
- T1 · 7 h ago
- arXiv
- 2603.06851
- T1 · 7 h ago
- Category
- stat.ML
- T1 · 7 h ago
Abstract
-cross 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 $\sigma_p$, and -- in the nonparametric case -- none of the effective H\"older smoothness $\beta \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 $\widetilde{O}(T^{(2-p)/p})$ in the parametric model and $\widetilde{O}(T^{1-2\beta(p-1)/(\beta p + d(p-1))})$ when the market value function is $\beta$-H\"older, with matching $\Omega(\cdot)$ 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 $\beta \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 $\pi$ to satisfy $\mathbb{E}[g(m,V,W) - g(\pi,V,W)] \le L|m-\pi|^2$ -- no second moment is needed.
Authors 1
Hangyi Zhao
Specification
- Official page
Source:arXiv (Atom API + RSS)T1observed 7 h agohigh
- Arxiv announce type
- replace
Source:arXiv (Atom API + RSS)T1observed 7 h agohigh
- arXiv id
- 2603.06851
Source:arXiv (Atom API + RSS)T1observed 7 h agohigh
- Categories
- stat.ML, cs.GT, cs.LG
Source:arXiv (Atom API + RSS)T1observed 7 h agohigh
Source:arXiv (Atom API + RSS)T1observed 7 h agohigh
- Primary category
- stat.ML
Source:arXiv (Atom API + RSS)T1observed 7 h agohigh
- Published
- 11 Sept 2026
Source:arXiv (Atom API + RSS)T1observed 7 h agohigh
Each value shows its source, tier and observation time. Conflicting claims are kept side by side and flagged — never averaged. How AI Atlas records facts →
Provenance
Attributed facts
9
Source tiers
T19
Freshest observation
7 h ago
Conflicts
None
No models linked to this paper yet.
- Authors
- Hangyi Zhao
As of
Rewind the record: see this entity's attributes exactly as AI Atlas knew them on a given day.
Claim history · Abstract
Abstractabstract1
| Value | Valid from → to | Status | Source | Confidence | Extractor |
|---|---|---|---|---|---|
| -cross 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 $\sigma_p$, and -- in the nonparametric case -- none of the effective H\"older smoothness $\beta \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 $\widetilde{O}(T^{(2-p)/p})$ in the parametric model and $\widetilde{O}(T^{1-2\beta(p-1)/(\beta p + d(p-1))})$ when the market value function is $\beta$-H\"older, with matching $\Omega(\cdot)$ 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 $\beta \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 $\pi$ to satisfy $\mathbb{E}[g(m,V,W) - g(\pi,V,W)] \le L|m-\pi|^2$ -- no second moment is needed. | → current | current | arXiv (Atom API + RSS)T1 | high | deterministic |
Claims are temporal and append-only: a new observation closes the previous claim (valid_to) instead of overwriting it. Conflicting claims from different sources are kept side by side and flagged — never averaged. Methodology →
- New paperPaperBilateral Trade Under Heavy-Tailed Valuations: Minimax Regret without a Variance Bound
New paper: Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret without a Variance Bound
arxiv
| Source | Document | Type | Tier | Last observed | Snapshots |
|---|---|---|---|---|---|
| arXiv (Atom API + RSS) | rss.arxiv.org/rss/cs.LG | feed | T1· Official | 5 h ago | 1 |
Tier 1 = official/primary, 2 = quality secondary, 3 = community, 4 = unverified. Every snapshot is archived; see all sources and the methodology.