Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies sequential bilateral trade where sellers and buyers valuations are adversarially chosen. The paper considers two types of posted price mechanisms: (1) mechanisms that post a single price and (2) mechanisms that post different prices for buyer and seller. In addition, three types of feedback are considered: full observation of the seller’s and the buyer’s valuations, observing whether the trade happens, and observing whether the seller and the buyer are willing to trade respectively. The paper proves both lower bounds and upper bounds of the regret when the performance is measured by gain from trade. It first gives a strong impossibility result that no mechanism can achieve sublinear a-regret for any a<2, so 2-regret is the best we can hope for. Second, with full feedback sublinear 2-regret is proved to be achievable. Third, for partial feedback, they show a contrast between single-price mechanisms and two-price mechanisms: with a single price, one cannot get sublinear a-regret for any constant a; but posting two prices even with one-bit feedback achieves sublinear 2-regret. Finally, they prove that there is a separation in the 2-regret bounds between full and partial feedback.
strengths_and_weaknesses: The paper studies an important problem and proves strong results. The fact that setting two prices can drastically improve the performance in the sequential setting is fascinating to me. I find no reason to reject the paper.
questions: I have no questions. 
limitations: Yes.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies a sequential bilateral trade problem, where one seller and one buyer arrive at every round. The seller and the buyer both have a private valuation of the item that are adversarial. The learning algorithm posts one or two prices for the seller/buyer and aims to minimize the alpha-regret of the trade over T rounds (alpha-regret is due to the hardness result shown by prior work). 

The paper considered different types of feedbacks including the full feedback (seller and buyer's values are revealed); the one-bit feedback (only the trade happened or not is revealed), and the two-bit feedback (whether the seller or the buyer accepts the price). The paper also studied these feedbacks with different strategy of the learner --posting one price or two prices.

The main results include a hardness result which shows that no algorithm can achieve sublinear alpha-regret when alpha<2. Then, with alpha=2, the authors provide sublinear regret algorithms with two-price strategy, one-price strategy under different types of feedbacks. When the feedback is incomplete (one-bit or two-bit), two-price algorithms are needed in order to achieve a sublinear regret rate.
strengths_and_weaknesses: Strength: 
- the paper is well-written and I appreciate that the authors provided a detailed review on the prior works, and how the setup and techniques in this work are different from those.
- I found the technical part of the paper to be interesting, including the estimation procedure using two prices and the lower bound example 's construction. 

Weaknesses:
- the upper bound results were a bit less exciting-- after doing the discretization, one can then use the prediction with experts framework on a grid of prices. 
- the results in table 1 contains a few gaps, in particular the study under the one-bit feedback seems to be quite incomplete and many questions remain open. e.g. what is the best possible regret a one-price strategy can achieve with one-bit feedback? what about the two-price strategy?

questions: (please see the above weakness section too)
- about the gaps in the current results: under the two-bit feedback system can the two-price algorithm achieve T^{2/3} regret upper bound, for example by an explore-then-commit type strategy with the discretization? 
- Is it necessary for the Block-Decomposition algorithm to know T, can one apply the doubling trick and make it independent of T?
- the paper proposed the estimation procedure to estimate the price unbiasedly -- would it be useful to apply an upper/lower confidence bound for the prices over the rounds (or reasons that was not needed/used) ?  
limitations: Yes (work is mainly theoretical)
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the sequential adversarial bilateral trade problem under various feedback models: 1) full feedback 2) one-price 1 bit feedback 3) two-price 2 bit feedback 4) two-price 1 bit feedback. This paper provides a regret lower bound of 2-approximation for the full feedback model. Additionally, they give a learning algorithm that achieves $\tilde{O}(\sqrt{T}) 2$ regret in this setting. Then, for the partial feedback model with 1 or 2-bit feedback, the authors shows that no learning algorithm can achieve sublinear regret for constant $\alpha$. Moreover, the paper provides a separation result between partial feedback and full feedback. For all the above results, the benchmark solution is the best fixed price in hindsight. 
strengths_and_weaknesses: Strength:

1. Section 1.2 introduces in detail the technical challenges of this paper, as well as related literature. 

2. This paper provides intensive theoretical analysis on the proposed algorithm in various settings.

3. This paper provides a regret lower bound on full feedback model. 

Weakness:
1. Some of the notations used in this paper are not standard, e.g., sublinear $\alpha$-regret. 

2. The result comparison table (Table 1) is informal. The paper should specify which is the lower bound for the specific setting, and which is the performance of the proposed algorithm, by adding more descriptions to the table. 

3. The review find it hard to follows some proof intuitions, even with figures (Figure 1 and Figure 2)

4. This paper doesn't have runtime analysis or experiments. 

Minor Comments:
1. [line 86] the full feedback model achieves $\tilde{O}(\sqrt{T}) 2$-regret. What does it mean?

2. [line 288] broken link 

questions: 1. Is there any \emph{existing} regret lower bound on adversarial bilateral trade similar to the settings of this paper? 

2. Does the gain from trade results of this paper implies improvement for the social welfare benchmark?

3. Is the two-price setting realizable?

4. What did the paper mean by sublinear $\alpha$-regret when $\alpha > 1$. Conventionally, sublinear regret means the total regret is sublinear in total time horizon $T$, hence algorithm with sublinear regret can be viewed as near-optimal. 

limitations: If the paper could explain how the "gain from trade" benchmark outperforms the standard social welfare benchmark, that would be great.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the problem optimizing gains from trade when a buyer with value b and seller with cost s arrive online. The process sets a single price p = q or two prices p and q, a trade happens if s <= p <= q <= b. The gain from trade is (b-s). Gain from trade is harder objective to optimize as the value is zero if no trade happens. 

The authors consider online pricing with the goal of minimizing regret compared to the optimal gains from trade in hindsight. In this model 1-regret is not possible, so authors consider 2-regret where the optimal hindsight gains from trade - 2 x achieved gains from trade is sub-linear in the number of steps T. 

They consider three different models on what information is available: Full feedback where the planner learns (s, b), 2 bit feedback where the planner learns if (s < p) and (q < b) and 1 bit feedback where the planner learns if the trade happened or not. The authors provide variety of lower bounds on the regret-approximation and regret as a function of T and provide close/matching upper bounds. 

In particular the authors show.
* a lower bound of 2 for the regret approximation in full feedback model
* A matching upper and lower bound of O(\sqrt(T)) for the regret in the full feedback model. 
* A lower bound of O(T) for regret with two bit feedback and single price. 
* A lower bound of O(T^{2/3})  with two prices and two bit feedback. 
* Upper bound of O(T^{3/4}) with two prices and 1 bit feedback. 
strengths_and_weaknesses: The results in this paper are comprehensive and the questions studied seem interesting.  

The results are non-trivial. The upper bound in the full information model comes from multiplicative weights. For the two lower bound the authors provide specific constructions that have high gains from trade in hindsight but the gains from trade of any pricing algorithm are much lower. The lower bound constructions for the two bid feedback models are much more involved. The upper bound for two bit feedback model is also involved. 

A big weakness is in the presentation of the paper. A lot of the details in the main body are difficult to follow without consulting the appendix. The appendix itself has also becomes difficult to follow due to having to refer back to the main paper. Perhaps the authors could find a better way to split the content. As an example, the lower bound constructions in Figure 1 and Figure 2 made no sense without the verbal description. 

Another concern is about the correctness of some of the results. The more involved results in the paper are also hard to follow. In particular, Section 4.2 does not make complete sense even after putting it together with the appendix. 
The estimator \hat{GFT} is defined without a subscript but is later used with a variety of subscripts. The subscript h^{-1}(p) seems like a typo and should be h(p). The subscript \tau refers to a batch of requests. It's not clear what is going on here. 
I am also not sure how \hat(GFT)(p_i) is evaluated when the model only allows posting one pair of prices. Please clarify in the block decomposition algorithm, what price is posted in step 10. It will be important for authors to clarify this and assure that their result is indeed correct. 

I also found some typos in the lower bound result for the two bit feedback model and haven't checked the correctness of the rest of the result as it is fairly complex. Please consider including a statement of Theorem 4 from Bartok et al. for completeness.

Other typos:
Page 17, line 629: define N_{\Delta}
Page 17, line 632: Claim only holds for integer \alpha. But the extension to other values in between follows.
Page 18, line 649: Clarify what q is. 
Page 19, line 692: 
Why is E[GFT(p)] for p in [0, 1/3] not 1/8? And the next line not 1/8 + 1/24?

Update after rebuttal: 
The authors response about the GFT estimator’s definition makes sense to me and I no longer think that the approach us fundamentally wrong. I will look at the proof some more. 


questions: * Please clarify the details for the result in Section 4.2.
limitations: Authors note some of the gaps in their results. There are no societal impact implications to note.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies online bilateral trade in the adversarial setting. Previously, there had been some work on online bilateral trade but in the stochastic setting. The authors prove a number of results. First, note that one cannot hope to have an online algorithm that is able to compete with the optimal GFT (this is a result due to Cesa-Bianchi et al.).They further strengthen this to show that one cannot obtain any approximation ratio better than 1/2 even with full feedback, even in the adversarial setting.

On the upper bound side, the authors show that sqrt(T log T) 2-regret is possible when full feedback is available.

They also consider different feedback models. In the one-bit feedback model, one is allowed to post a single price and observes only the event of whether or not a trade occurs. In the two-bit feedback model, one sees two events: the event that the buyer is willing to trade and the event that the seller is willing to trade. They also consider two ways of “pricing”. The first is to use a single price and the second is to use two prices.

On the upper bound side, they show that in the one-bit feedback model, can obtain 2-regret of T^{3/4} by using two prices. If one uses only a single price then one has 2-regret at least T. They also show T^{2/3} 2-regret with two prices in the two-bit feedback model.
strengths_and_weaknesses: **Strengths.**
- I think the problem is very nice and I think the authors prove a number of very nice results. The techniques are very nice (Lemma 1 is a very neat trick). I think this paper is a pretty solid contribution.

**Weaknesses.**
- None
questions: - Mention in abstract that only a single seller and single buyer is considered.
- Line 288, missing reference
- Out of curiosity, I wonder if the authors consider multiple buyers and/or multiple sellers at all?
- Line 50, it mentions that Deng et al give a BIC mechanism for approximating the first-best GFT. This is slightly inaccurate in that they analyzed a known mechanism. For example, the mechanism was also discussed in "Approximating Gains from Trade in Two-sided Markets
via Simple Mechanisms" by Brustle, Cai, Wu, and Zhao.
limitations: Limitations discussions looks good. They filled out the checklist.
review_title: null

Meta-review: metareview: This is an interesting paper on bandit with non-trivial structure and algorithms.

All the reviews are positive, as is my own opinion. 

I quite happily suggest acceptance for this paper.
confidence: Certain
Decision: Accept