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 $(\tilde{O}(T^{\alpha }),\tilde{O}(T^{1-\alpha /3}))$ 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 $(\tilde{O}(T^{2/3}),\tilde{O}(T^{3/4}))$.