Feature-Based Online Bilateral Trade

We thank the reviewer for the positive feedback about the paper.

1) Posting two different prices without a strict budget balance in the two-bit feedback can indeed make exploration more efficient. This approach allows us to simultaneously estimate the quantities of interest (expected valuations and the CDF of the noise) for both the buyer and the seller. In contrast, posting the same price for both forces us to separate the estimation phases for the buyer's and seller's parameters. However, note that this change does not affect the order of the regret, as it only reduces the length of the exploration phase by half. To achieve the lower regret of order $\sqrt{T}$, full observation of the valuations is required, as discussed by Cesa-Bianchi et al. in the context of non-contextual bilateral trade. In summary, we would not achieve any improvement, at least in terms of the order of regret.

2) Intuitively, scouting bandits (combined with information pooling) is a tool to avoid performing a pure exploration phase (as in ETC algorithms). We refer the reader to the sketch of proof following Theorem 3 for intuitions on the regret of the Scouting phase and to the sketch of proof following Theorem 2 for intuitions on the regret of the estimation phases of the parameters $\theta^s$ and $\theta^b$, and of the functions $I$ and $J$.

3) Approximately linear reward functions should also work, as long as the deviation from the linear model is not too large. Just as we can handle noise-induced corruption, we can also accommodate small corruptions in the model. However, if the deviations from the linear model are significant, the analysis is likely to fail, and we leave studying this new setup as an interesting direction for future work.

4) We distinguish between the existence of an $\alpha > 0$ and knowledge of such an $\alpha$. The former is necessary, as without it, the learner would be unable to build up a budget, making the tradeoff between budget and information gain impossible. However, in principle, knowledge of $\alpha$ is not required. Indeed, it should be possible to dynamically estimate $\alpha$ by dividing the time horizon into windows and adjusting the estimate based on the observations within each window. We leave this an interesting direction for future research.

5) The dependency on $\alpha$ of the regret bound is unavoidable because, intuitively, when $\alpha$ approaches zero gathering the required budget becomes impossible. Moreover, we conjecture that the dependency on $\alpha$ in Lemma 3 is tight. Hence, intuitively, $(b_t-s_t)^2$ is too small to collect enough budget when $\alpha$ is small.

We thank the reviewer for their feedback about the paper. We will start by addressing the weaknesses identified, and then we will address the reviewer’s questions.

W1) The two-bit feedback condition is a relatively mild requirement and is a reasonable assumption for most practical applications. Specifically, the learner only needs to observe whether each agent accepted or rejected the trade, which is typical in platforms that use posted price mechanisms, where both the buyer and seller independently decide to accept or decline the posted price. Indeed, this type of feedback is commonly referred to as "realistic feedback" in the literature (see, e.g., Cesa-Bianchi et al. (2021)).

W2) See question.

W3) and W4) The results for the noiseless setting are included only for completeness and are clearly marked as a “Warm up” (see Section 3), since their derivations are, indeed, rather straight forward from Cohen et al. (2020). But apart from these warm-up results, none of our main contributions for the noisy setting draws upon the results of Cohen et al. (2020).

W5) We agree that the contributions of this paper are primarily theoretical, as we analyze the problem and characterize its difficulty in terms of regret under various assumptions. We consider this a necessary step to gain a deeper understanding of the problem before exploring practical applications. Additionally, we would like to highlight that such theoretical contributions are encouraged by the ICLR guidelines.

Q1) We’re not entirely sure we fully understand the reviewer’s question, so please let us know if we are misinterpreting it. Budget balance is something the learner must enforce when determining the prices to be posted. Specifically, if the prices posted to the seller and the buyer are the same, then strong budget balance is satisfied.

Q2) We interpret "computational complexity" as referring to the "per-iteration running time." If that is correct, the per-iteration running time is polynomial in the size of the problem and independent of $T$. This aligns with the standard requirement for online learning and bandit algorithms.

We did not include numerical experiments for two main reasons: 1) the primary goal of the paper is to provide a theoretical characterization of the problem, which we consider a crucial step before exploring practical applications; 2) our algorithms are the first to be proposed and analyzed for this specific setup, meaning we lack a meaningful baseline for conducting experiments. However, our algorithms can serve as a baseline for future experimental evaluations of other approaches.

We thank the reviewer for the positive comments about the paper.

1) The Contextual Search algorithm is specifically designed for the dynamic pricing problem, since it exploits the structure of the problem to reduce the width of uncertainty sets and to maximize rewards. In particular, in the context of pricing, setting a price near the lower bound of the confidence interval increases the likelihood of a transaction, while limiting the reduction in reward to at most the width of the interval.

The tradeoff in the bilateral trade problem is fundamentally different. In particular, any price within the range between the buyer’s and seller’s valuations yields the same reward. When the uncertainty sets for the buyer’s and seller’s valuations overlap, the optimal price clearly lies within this intersection. However, selecting a price closer to the lowest or highest endpoint of the intersection, or its midpoint, does not a priori improve the reward or increase the likelihood of a trade. Moreover, the loss from selecting a price that fails to result in a transaction, or the gain from choosing an appropriate price, is not directly tied to the width of the intersection.

As a result, it is not obvious at all how Contextual Search algorithm techniques could be reconciled with bilateral trade, as they are inherently of different nature.

2) We identify two key conceptual contributions which we present in this paper:

1. Our scouting algorithm introduces the key idea of sharing information across different contexts. This new approach, which has never been explored in prior work on the bilateral trade problem, is crucial to achieve the minimax optimal rate of $T^{2/3}$.
2. Our second main contribution is a general reduction scheme that allows us to apply ETC-like algorithm designed for two-bit feedbacks in the one-bit feedback setting. This reduction is new, and can be leveraged beyond the contextual setting to balance information gains against budget constraints.

Along the way, we also introduce several new results that build on techniques previously used in the pricing and bilateral trade literature but require significant extensions due to the complexity of our setup. For example, Lemma 1 from Cesa-Bianchi et al. (2021) is extended to be able to handle the contextual version of the problem. Moreover, constructing unbiased estimators of linear expected valuations requires adapting techniques from noisy dynamic pricing to settings where features are chosen adversarially. These extensions could have broader applications beyond bilateral trade, for studying dynamic pricing problems in more challenging environments than those typically considered.

We thank the reviewer for the positive feedback about the paper.

1) The online brokerage model has several fundamental differences from our model. We will discuss this in the final version of the paper. However, we emphasize that the two problems are related only at a high level and present significantly different challenges.

In online brokerage, the agents have the same expected valuation for the good, and their roles as buyer or seller are determined based on their valuations of the good relative to each other. Specifically, at each round, agents $q$ and $q'$ have valuations $v$ and $v'$. If $v < v'$, $q$ acts as the seller and $q'$ as the buyer; if $v > v'$, the roles are reversed. In contrast, the bilateral trade problem assumes that buyer and seller roles are predetermined, typically reflecting a situation where one party owns a good that the other seeks to purchase.

These two models not only represent different situations but also differ significantly in their difficulty. In Bachoc et al., when both agents share the same expected valuation, the optimal price is simply this shared value, making the problem parametric and requiring only the learning of this expected value. Moreover, the regret is quadratic in the price error, allowing for regret rates that scale as $\sqrt{T}$ up to logarithmic factors.

In the bilateral trade problem, the buyer and seller have distinct average valuations, and the optimal price depends on the noise distributions affecting each party's valuation. Here, estimating the linear expected valuations (using techniques similar to those in Bachoc et al.) is the ``easy part’’ of the problem; the more challenging, non-parametric task is determining the optimal price. This requires estimating the cumulative distribution function of the noise. Pure exploration, as done in our Explore or Commit algorithm, yields a suboptimal regret rate. Our Scouting Bandit with Information Pooling algorithm, however, incorporates a subroutine based on the “optimism in the face of uncertainty” principle, pooling information across different contexts. This subroutine is a key contribution that allows us to achieve tight regret rates on the order of $T^{2/3}$.

2) This is undoubtedly an interesting question, which we leave as a direction for future research. Deriving meaningful lower or upper bounds for this setting will likely require entirely new techniques beyond those introduced in this paper or in previous works. Indeed, lower-bound constructions based on instances used in previous pricing or bilateral trade works have proven to be of limited use in this setting.