- Rating
- 4
- Confidence
- 4
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies the problem of bilateral trade with one bit feedback, first under the Weak Budget Balance (WBB) constraint, then under the Global Budget Balance (GBB) constraint. They obtain algorithm with regret of order in both cases, compared to the best identical buyer and seller price for WBB, and compared to the best distribution verifying in expectation GBB for GBB constraint.
Critical strengths
This paper bridges a gap in the current understanding of stochastic bilateral trade under one bit feedback, where lower bound had been previously established, but with no matching lower bounds. This is an interesting result.
The algorithms are new, and I believe they could provide new insights to handle other problems with one bit feedback (e.g., dynamical pricing). The presentation of the first algorithm is especially clear and insightfull.
Critical weaknesses
The second algorithm is complex, and conceptually rather different to the algorithms classically used in this field. Given that the contribution of this paper is purely theoretical (1), I find it disappointing, if not a bit frustrating, that the authors did not spend more space - even in the appendix - to provide more insight on their algorithm. I believe a step-by-step explanation of how and why it works would be very beneficial.
(1) although one can only appreciate the honesty of the authors, the condition on l. 357 is not likely to be realized.
Questions for authors
How should the (infinite) set of candidate laws be constructed and updated in Algorithm GLOBAL-OFU ?
2 comments
I thank the authors for these clarifications.
Response to Reviewer 6qf3
We thank the reviewer for the positive evaluation, and we are honored by the reviewer's kind words on the presentation of the WBB algorithm.
Following this suggestion, we have revised Section 4 to improve its readability, organizing the explanation of the GBB algorithm into paragraphs that each address one step, and we have added comments throughout its pseudocode (Algorithms 2, 3 and 5) to guide the reader through each phase. At a high level, estimating the GFT and the profit of each price pair separately would lead to a bandit problem with (K+1)2 arms and only O(T3/4) regret. To avoid this, we split each side of a price pair into consecutive dyadic intervals, and by independence, the information collected on such an interval is shared by every price pair whose decomposition contains it, so the algorithm effectively learns two one-dimensional marginals instead of (K+1)2 pairs. The new paragraphs of Section 4 give the details, namely, “Difficulties in implementing OFU directly” explains why the pairs cannot be learned separately; “Recursion on dyadic intervals” shows how the recursion of Lemma 2 lets us split the prices into dyadic intervals, and describes how we design the estimates on these intervals to be reused across pairs and epochs; and “Why paths?” explains why the intervals are extended to the paths illustrated in Figure 1. We hope that these revisions improve the reading experience.
We agree with the concern about this condition, so we have relaxed it by adjusting the parameters of the GBB algorithm (line 364 of the revised version). This condition is on the number T−τ of rounds that remain after the first stage, and for example, the resolution K=8 now requires T−τ≥6.6×104 rather than about 1021 in the previous version.
We thank the reviewer for this important question, which concerns the core of our algorithm. Global-OFU represents the confidence set Fk−1 implicitly, by the constraints that its laws satisfy. It starts from the set F of all independent laws whose densities are bounded by M, and its boundary exploration keeps the laws consistent with the estimated trade probabilities at the boundary pairs, which gives F0 (Algorithm 3, line 9). At each epoch k, the algorithm optimistically selects a distribution γk over at most two price pairs by solving an infinite-dimensional problem over Fk−1 (Algorithm 3, line 13). It then locates the support pair and the dyadic interval on its paths (detailed in “Recursion on dyadic intervals” of Section 4) at which the candidates disagree most about the local trade probabilities, weighted by the probability of the pair under γk (Algorithm 3, line 16), and refines the candidates there. Since the opposite-side price changes with the support of γk from epoch to epoch, the trade probabilities observed on an interval differ across epochs and cannot be pooled directly. Independence resolves this, as the probes on an interval of one side share the acceptance probability of the opposite side, which cancels in the ratios of their trade probabilities. The algorithm therefore pools the trades on each interval across pairs and epochs and keeps only the candidates whose ratios are consistent with them (Algorithm 5). Once the remaining disagreement is small (Algorithm 3, line 17), the algorithm exploits γk in the remaining rounds.
From a computational perspective, the revised Appendix E shows that the OFU problem is equivalent to a finite-dimensional one, since its objective and constraints depend on a candidate only through O(K) numbers at the grid prices (Lemma 11), and after a change of coordinates, the image of Fk−1 in these numbers is convex and compact (Lemma 12). It also gives a polynomial-time algorithm that solves this problem approximately through O(K4) convex programs per epoch, with the guarantees of GBB and O(T2/3) regret preserved (Algorithm 8 and Corollary 4).