Profit Maximization in Bilateral Trade against a Smooth Adversary

We address the problem of maximizing Gain from Trade (GFT) in repeated buyer-seller exchanges subject to global budget balance constraints. While this problem is well-understood in purely adversarial and stochastic settings, these environments exhibit a sharp dichotomy: adversarial environments allow for no-regret learning against the best fixed-price mechanism, whereas stochastic environments allow for no-regret learning against the best distribution over prices that is budget balanced in expectation. This gap is significant, as policies balanced in expectation can increase the GFT by a multiplicative factor of two. In this work, we bridge these extremes by studying perturbed markets, where an underlying stochastic distribution is subject to an adversarial corruption $C$. We design an algorithm that adaptively scales with the level of corruption, achieving an $\tilde{\mathcal{O}}(T^{3/4}) + \mathcal{O}(C\log(T))$ regret bound against the best budget-balanced distribution over prices. Simultaneously, our algorithm maintains the worst-case $\tilde{\mathcal{O}}(T^{3/4})$ regret bound relative to a per-round budget-balanced baseline, ensuring optimality even in fully adversarial environments.

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 $σ_p$, and -- in the nonparametric case -- none of the effective Hölder smoothness $β\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β(p-1)/(βp + d(p-1))})$ when the market value function is $β$-Hölder, with matching $Ω(\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 $β\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 $π$ to satisfy $\mathbb{E}[g(m,V,W) - g(π,V,W)] \le L|m-π|^2$ -- no second moment is needed.

We study regret minimization for learning CDF-related objectives of the form $$g(x)\cdot\mathbb{P}_{X\sim\mathcal{D}}(X\le x),$$ over $[0,1]^2$, where $g$ is a known Lipschitz function and $\mathcal{D}$ is an unknown distribution. At each round $t$, the learner selects a point $x_t$ and observes the binary feedback $\mathbb{I}(X_t\le x_t)$, where $X_t\sim\mathcal{D}$. We design an algorithm achieving regret $\widetilde{\mathcal{O}}(T^{7/10})$, improving over the previous best-known bound of $\widetilde{\mathcal{O}}(T^{3/4})$ and showing that the curse of dimensionality can be at least partially lifted for this class of objectives, though a gap remains with the $Ω(T^{2/3})$ lower bound. As an application, our techniques yield the same $\widetilde{\mathcal{O}}(T^{7/10})$ regret bound for profit maximization in repeated bilateral trade with fixed prices.