- 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 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.