2026/03/06 by Hangyi Zhao
#stat.ML #cs.GT #cs.LG
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 and finite first moments alone. Combining this with truncated-mean estimation, we prove that an epoch-based algorithm achieves regret \widetildeO(T1-2β(p-1)/(βp + d(p-1))) when the noise has finite p-th moment for p ∈ (1,2) and the market value function is β-Hölder, and we establish a matching Ω(⋅) 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 → 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, σp) or the parameter norm, and a cell-width tournament extends this jointly to the tail and smoothness parameters when β≤ d -- under full feedback, tail-adaptivity is free.