cs.GTNov 6, 2026

Contextual Search and Bilateral Trade with a Trace-Square-Root Potential

Authors: Romain Cosson, Federico Fusco, Anupam Gupta, Stefano Leonardi, Renato Paes Leme, Matteo Russo

Organizations: Computer Science Department, New York University, NYC, United States. · Department of Computer, Control, and Management Engineering, Sapienza University, Rome, Italy. · Google Research, NYC, United States. · EPFL, Lausanne, Switzerland.

Abstract

We present a unified potential method for contextual search and bilateral trade with one-bit feedback and obtain order-tight algorithms for both problems. Our framework starts from a Bayesian perspective in which the unknown target (for contextual search) and the unknown pair of valuations (for bilateral trade) are sampled from a known prior distribution. In that model, the decision maker bases its prediction on the posterior distribution, obtained by conditioning on feedback received in previous rounds. For Bayesian contextual search, we present an algorithm with a total loss bounded by O(TrΣ)O(\mathrm{Tr} \sqrt Σ), where ΣΣ is the covariance matrix of the target's prior; and for contextual bilateral trade, our algorithm's regret is bounded by O(TrΣS+TrΣB)O(\mathrm{Tr} \sqrt{Σ_S}+\mathrm{Tr} \sqrt{Σ_B}), where ΣSΣ_S and ΣBΣ_B are the covariance matrices of the seller's and buyer's valuations. We then use ideas from this Bayesian setting and adapt a ``dual'' of this trace-square-root potential to the classical worst-case setting, where the target and valuations are chosen adversarially from the unit Euclidean ball. For both contextual search and bilateral trade, we obtain tight O(d)O(\sqrt d)-regret algorithms. These results match the existing lower bounds up to a constant factor and improve on the previous guarantees of O(dlog⁡d)O(d\log d) for contextual search and of O(d6d)O(d6^d) for bilateral trade.

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Mar 6, 2026

Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret without a Variance Bound

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 TT-exponents up to logarithmic factors, with no knowledge of the moment order p∈(1,2)p \in (1,2) or its scale σpσ_p, and -- in the nonparametric case -- none of the effective Hölder smoothness β∈(0,1]β\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 pp-th moments for some p∈(1,2)p \in (1,2), with possibly infinite variance. An epoch-based algorithm with truncated means achieves regret O~(T(2−p)/p)\widetilde{O}(T^{(2-p)/p}) in the parametric model and O~(T1−2β(p−1)/(βp+d(p−1)))\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 TT up to logarithmic factors over the effective smoothness range β∈(0,1]β\in (0,1], interpolating between the classical nonparametric rate at p=2p{=}2 and the trivial linear rate as p→1+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 E[g(m,V,W)−g(π,V,W)]≤L∣m−π∣2\mathbb{E}[g(m,V,W) - g(π,V,W)] \le L|m-π|^2 -- no second moment is needed.
Nov 5, 2026

Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price Mechanism

Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations. We study this problem from the perspective of a profit-maximizing broker in a regret minimization framework. At each time step, a new seller and buyer arrive and the broker proposes a trading price to each agent. The trade happens if both agents accept, and the profit of the broker is the difference between the price received from the buyer and the one paid to the seller. At the end of each interaction, the learner only observes whether the trade occurred, and its goal is to achieve sublinear regret relative to the best fixed pair of prices in hindsight. We start by investigating the adversarial version of the problem, where buyer and seller valuations are generated by an adversary. In this setting, we construct a polynomial-time learning algorithm with a O~(T23)\tilde O(T^{\frac 23}) regret rate, which is nearly tight even if the valuations are drawn i.i.d. from independent distributions, thus matching the rate for one-sided pricing. Our adversarial algorithm combines a localized estimation procedure with an information-based minimax construction. We then consider valuations drawn i.i.d. from independent distributions satisfying the monotone-hazard-rate (MHR) property and provide a learning algorithm with nearly tight O~(T)\tilde{O}(\sqrt{T}) regret. The algorithm combines localized estimation with a stochastic convex bandit routine applied to the negative logarithm of expected profit. Finally, we complement this result by showing a separation between MHR and regular distributions, proving that the minimax regret rate in the latter setting is Θ~(T35)\tilde Θ(T^{\frac 35}). This last result contrasts with the O~(T)\tilde{O}(\sqrt{T}) regret bound that can be obtained for one-sided pricing with regular distributions.
Jul 7, 2026

Contextual Procurement Auctions with Bandit Learning

We study repeated contextual procurement auctions in which producers have private costs and the platform must learn context-dependent product values from bandit feedback. The objective is welfare rather than revenue or a virtual-cost surrogate: regret is the total surplus loss relative to the full-information efficient procurement rule. We first show that the natural UCB allocation rule attains O~(ngT)\tilde O(\sqrt{ngT}) welfare regret under truthful bids, but its adaptive bid-dependent learning path does not by itself give a truthfulness guarantee. To obtain exact incentives, we design a bid-independent explore-then-commit mechanism with empirical critical payments; it is dominant-strategy truthful and has O~((ng)1/3T2/3)\tilde O((ng)^{1/3}T^{2/3}) regret. We then introduce frozen-payment UCB, which estimates payments in an initial bid-independent exploration phase, freezes those payment estimates, and continues adaptive UCB allocation learning afterwards. Under a smoothed truthful-path margin condition, this mechanism gives a regret-incentive tradeoff: the near-UCB tuning attains O~(ngT)\tilde O(\sqrt{ngT}) welfare regret, while the average per-round gain from any fixed deviation is at most O~(T−1/4)\tilde O(T^{-1/4}) for fixed n,gn,g. A matching lower bound shows that this frozen-payment frontier is unavoidable.