Breaking the $T^{3/4}$ Barrier for Regret Minimization With Bi-Dimensional CDFs

Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, who wish to trade a good. We study this problem from the perspective of a profit-maximizing broker within an online learning framework, where the agents' valuations are generated by a smooth adversary. We devise a learning algorithm that guarantees a $\tilde{O}(\sqrt{T})$ regret bound, which is tight in the time horizon $T$ up to poly-logarithmic factors. This matches the minimax rate for the stochastic i.i.d. case, and is also well separated from the adversarial setting, where sublinear-regret is unattainable. By extending the strong regret guarantees from the i.i.d. case to the smooth adversary, we significantly broaden the scope of settings where such fast rate is achievable, while closing an important gap in the regret landscape of this fundamental economic problem. To overcome the challenges posed by this adversary, we leverage a continuity property of smooth instances and combines this with a hierarchical net-construction of the broker's action space, which is analyzed via algorithmic chaining. We showcase the applicability of these techniques by deriving a similarly tight $\tilde{O}(\sqrt{T})$ regret bound for a related mechanism design model: the joint ads problem.

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 determine the minimax cumulative log-loss regret of a finite-alphabet, exogenously driven source with genuinely infinite input memory: independent Rademacher inputs $(U_t)$ are observed sequentially and the next binary mark has logit $\sum_{j\ge1}θ_jU_{t+1-j}$, the unknown coefficients obeying a summable envelope $|θ_j|\le r_j$, $\sum_jr_j\le B$. At horizon $T$, lag $j$ can move the logit by at most $r_j$ and is exercised in only $n_{T,j}=(T-j+1)_+$ rounds, and the two limitations combine into the sum $Γ_T(r)=\sum_{j\le T}\log(1+n_{T,j}r_j^{2})$. One coordinate-localised Bayesian mixture achieves $R_T(r)\le CΓ_T(r)$ for \emph{every} summable envelope with $C$ universal. Our main result is a matching nonasymptotic converse for the canonical exponential and polynomial envelopes; its new ingredients are a modular finite-sample information bound for logistic experiments with an exogenous random design, and a conditioning estimate for the overlapping Toeplitz lag matrix obtained by exhibiting each off-diagonal Gram sum as a sum of independent Rademacher variables indexed by the edges of a forest, needing neither local asymptotic normality nor any spectral theorem for random Toeplitz matrices. So $Γ_T(r)$ is the minimax regret scale here, giving $Θ(α^{-1}\log^{2}T)$ for $r_j=Ae^{-αj}$ and $Θ(T^{1/(2s)})$ for $r_j=Aj^{-s}$, $s>1$ --- the latter without the extra $(\log T)^{1-1/(2s)}$ factor any window-truncation analysis pays. We also show memory decay cannot determine regret, and that a profile-scaled online Newton predictor attains $O_B(Γ_T(r))$ in polynomial time per round.