Online Bilateral Trade under Stochastic Delays

Online bilateral trade has recently attracted significant attention in the learning and economics literature. It studies sequential pricing between arriving seller–buyer pairs, where a learner posts prices to facilitate trades and maximize the gain from trade. Existing works typically assume immediate feedback, whereas practical platforms often experience delayed and incomplete responses due to factors such as network latency, payment verification, and slow user interactions. In this paper, we study online bilateral trade under stochastic delayed and censored acceptance-only feedback, where acceptance signals arrive after random delays and missing signals may correspond either to rejection or delayed feedback. We first establish a regret lower bound showing that stochastic delays introduce an unavoidable additional cost proportional to the expected delay. For exogenous stochastic delays, we exploit boundary prices that guarantee one-sided acceptance to develop a boundary-calibrated scouting bandit algorithm achieving near-optimal regret up to logarithmic factors. We further extend our results to valuation-dependent delays, where independence-based correction fails, and propose a boundary-calibrated adaptive window elimination algorithm achieving the same regret rate.