acceptodds
Withdrawn from ICLR 2027

Online Bilateral Trade under Stochastic Delays

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

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.

Primary area:
learning theory
Keywords:
Online Learning, Bilateral Trade, Game Theory

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_jygVOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

This paper discusses the online bilateral trade problem between a buyer and seller, which is essentially a dynamic pricing problem, studied previously in [1,2]. The work inputs the new novel condition of adding feedback delay the problem. This results in a slightly new bandit problem where the learn to gain-from-trade problem setting is imbued with delayed feedback. The authors provide new poly- logarithmic bounds w.r.t. to this setting.

Critical strengths

The mathematical argumentation in this paper is precise and relatively straightforward. The learner undergoes several additional exploration steps before a PAC guarantee is obtained such that even in this delayed feedback setting no-regret guarantees on expectation can be obtained.

The methods in the this paper have real economic interpretation and importance, a real use case exists.

Critical weaknesses

This study of this problem is becoming rather incremental - as basically, we are adding the idea of delayed feedback to results that are generally encompassed [1,2]. I admit that the argumentation and methods are rather clever, but the extension is relatively not ambitious in its scope. (For example what would be more interesting is if the bilateral trade problem setting involved two - or more - agents with agency , where both sides are strategic (e.g. Myerson–Satterthwaite, Chatterjee–Samuelson) and you can get impossibility results - no efficient, incentive-compatible, budget-balanced mechanism. If we consider learning in these problem settings, it could be the next step (at least in my opinion) - instead of tinkering with additional delayed feedback.

The seem to be many constants in this paper, I would like to know to which extent these constants scale, in comparison to a general time horizon. Is there a numerical factor for all the constants c∗,Ccal,Csc...c_*, C_{cal}, C_{sc} ... etc. Can a single constant upper bound the combination of all constants?

Questions for authors

Are there any empirical results to compare and examine against an established baseline. In principle would EXP3 or UCB work as a price learning algorithm or perhaps the learn-to-price method from [3]? Since there is no strategic interaction between buyer and seller, this is quite analogous to learning the valuation (except the valuation is within a window). Therefore, how exactly do these results stand against standard bandit/demand learning models.

Furthermore, how much does the model collapse when a bandit model for GFT that does not considered delayed feedback is used instead of one with delayed feedback? Any empirical or theoretical analysis here?

[1] Cesa-Bianchi, Nicolò, et al. “A Regret Analysis of Bilateral Trade.” Proceedings of the 22nd ACM Conference on Economics and Computation, ACM, 2021, pp. 289–309.

[2] Bernasconi, Martino, et al. “No-Regret Learning in Bilateral Trade via Global Budget Balance.” Proceedings of the 56th Annual ACM Symposium on Theory of Computing, ACM, 2024, pp. 247–58.

[3] Kleinberg, R., & Leighton, T. (2003). The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. (pp. 594–605). IEEE.

Reviewer_yqioOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper adresses the problem of bilateral trade under delayed feedback. The setting is the following: two-bit feedbacks are received, and the agent works under strong budget balance (it posts the same price for the buyer and the seller); the seller and buyers valuations are assumed to be i.i.d., independent of one another, and with Lipschitz-continuous c.d.f. The feedback are received with some form of censored delay: the agent only observes if the trade is accepted, and this signal comes with some i.i.d. delay. The authors first establish a worst case lower bound on the regret of any algorithm in this problem; then they provide an algorithm for the easy setting where the delays are independent of the price posted, before proposing an algorithm for the case where the delays may depend on the price posted.

Critical strengths

The analysis of the algorithms is rigorous.

Critical weaknesses

My main concern is about the significance of this work. Delays have been well-studied in bandit algorithm, and they do not seem to add any major difficulty to bilateral trade, nor change the complexity of the problem. In both cases, delays can be estimated or upper bounded by a first step of posting prices 1 (always accepted by the seller) and 0 (always accepted by the buyer). Then, the classical scouting algorithm works (accounting for the necessity to wait before estimating the rewards).

The regret upper bound is effectively unchanged, and grows as O~(T2/3)\tilde{O}(T^{2/3}) - I will remind the authors that using the Landau notations, O(T2/3T+Clog⁡(T))=O(T2/3T)O(T^{2/3}\sqrt{T} + C\log(T)) = O(T^{2/3}\sqrt{T}) for any (possibly problem-dependent) constant CC. Thus, there is no major difficulty to handle the delays (it basically works as follows : estimate how long you need to receive enough feedback, and then make sure that you wait enough when estimating your reward), and no impact on the regret - either in the upper bound, or in the lower bound, which is unchanged for the regime of interest.

A minor concern is about the validity of the claims. Theorem 1 claims that the worst case regret is ≥cmax⁡(T2/3,μ)\geq c \max (T^{2/3}, \mu), where μ\mu is the expectation of the delay, and cc is an absolute constant. For μ\mu large enough, and TT small enough, it would imply that the regret is larger than TT, which I doubt is the case. Anyway, the T2/3T^{2/3} rate follows for Cesa-Bianchi et al., and it is no wonder that the regret is at least of order μ\mu, as it is the unavoidable time to wait before receiving the first feedbacks and being able to adapt to the feedbacks.

Questions for authors

A more realistic and maybe more interesting setting would be to consider the case where the delays also depend on the price posted: after all, when the seller receives price 1, they may not need to thing about it for too long. It's also a setting where the delays are intrinsically more difficult to estimate. Could you adapt your algorithms to handle this case ?

Reviewer_UVkZOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper is about online learning in bilateral trade when agents’ valuations are i.i.d. across rounds and acceptance feedback may be observed with some delay. In particular, the authors assume that the delay is stochastic and affects the number of rounds after which the learner observes whether the seller or the buyer accepted the price offered in a previous round. First the authors provide a minimax lower bound showing that dependence on the delay is unavoidable in the regret guarantees of any algorithm. The authors then design algorithms with regret guarantees with respect to an optimal fixed price maximizing the gain from trade (GFT) in two different settings. When delays are independent of valuations and when delays may depend on valuations.

Critical strengths

The fact that an online marketplace or platform may experience delays in receiving feedback is a natural extension of the model of Cesa-Bianchi et al. (2024). Therefore, I think that the motivation behind the paper is well justified. Another strength is that the authors also consider delays that depend on agents' valuations, rather than restricting their analysis to independent delays.

Critical weaknesses

I believe the writing of the paper should be improved to meet the standard expected of an ICLR paper. Below, I list some points that I found confusing when reading the paper.

  • At line 309, the authors write Pr⁡(Db≤L)\Pr(\mathcal{D}^b \le L), although Db\mathcal{D}^b is a probability distribution.
  • The choices of mm and m0m_0 required for the regret guarantee are not stated alongside Algorithm 1, where they are inputs, or in Theorem 2. So it is not clear how to set mm and m0m_0 to achieve the regret guarantees stated in Theorem 2.
  • The rationale behind the estimators F^k\hat F_k and G^k\hat G_k at lines 272-273 is unclear. The authors do not provide any intuition on why these estimators work (see also questions).
  • The regret is denoted in 3 different ways: RTR_T, RT,\mathcal{R}_T, RR_bandit.
  • Algorithm 1 includes several waiting periods (Line 5, 15) without specifying which prices the learner posts during those rounds.

Furthermore, it is not fully clear to me how technically novel Algorithm 1 is. It appears quite close to Scouting Bandits by Cesa-Bianchi et al. (2024), with corrections and normalizations in the estimators of the terms defining the GFT to account for delays. The authors should explain more clearly which technical challenges require new ideas beyond this adaptation. In addition, the authors focus only on GFT maximization, which makes sense and is well justified in the literature. At the same time, I think they could also discuss why they did not study revenue or profit maximization problems, since these may also be affected by some form of delay.

Questions for authors

Clarification requests:

  • Can you please explain why the estimators F^k\hat F_k and G^k\hat G_k at lines 272-273 work? Specifically, are they unbiased even after clipping?
  • What are the main technical challenges behind Algorithm 1?

Future work:

  • Could the authors better explain their choice of GFT maximization under a single-price mechanism, rather than profit maximization? Are there some structural challenges or profit maximization is a future work?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.