No Free Best-of-Both-Worlds Learning in Repeated Bilateral Trade

We study best-of-both-worlds learning in repeated bilateral trade with two-bit feedback. When seller and buyer valuations are independent, minimax regret scales as $\Theta(T^{2/3})$; under general bounded-density distributions it degrades to $ \Theta(T^{3/4})$. This regime-dependent gap naturally raises a question: can a single algorithm adapt optimally to both? We first resolve this negatively: any algorithm achieving $O(T^\alpha)$ regret on independent-values instances necessarily suffers $\Omega(T^{1-\alpha/3})$ regret on some dependent-values instance. We then characterize the optimal tradeoff and construct a meta-algorithm achieving $\bigl(\widetilde O(T^{\alpha}),\widetilde O(T^{1-\alpha/3})\bigr)$ for every $\alpha\in[2/3,3/4]$. Finally, we show that this tradeoff can be bypassed with mild side information: knowing the optimal same-price gain suffices to recover the classical best-of-both-worlds guarantee $\bigl(\widetilde O(T^{2/3}),\widetilde O(T^{3/4})\bigr)$.