Bilateral Trade with Independent Sellers and Buyers: Tight Regret under One-Bit Feedback

We study regret minimization in repeated bilateral trade under one-bit feedback: over $T$ rounds, a learner posts a price to a seller and a price to a buyer to maximize gains-from-trade, but observes only whether trade occurs. When the two valuations are independent and drawn i.i.d. from an unknown distribution with bounded density, the tight regret was still open in two settings: weak budget balance against the best fixed price, and global budget balance against the best feasible distribution over price pairs. In both settings, the best known upper bound was $\tilde{\mathcal{O}}(T^{3/4})$, against a lower bound of $\Omega (T^{2/3})$. We close both gaps by designing two learning algorithms, one for each setting, each achieving regret $\tilde{\mathcal{O}}(T^{2/3})$. Combined with the known $\Omega (T^{3/4})$ lower bound for correlated valuations, our results reveal that independence makes learning strictly easier in both settings. Our key technical ingredient is a recursion that relies on valuation independence, enabling our algorithms to learn gains-from-trade from trade bits alone while probing only inside the price interval being explored.