Online Bilateral Trade With Minimal Feedback: Don’t Waste Seller’s Time

Re: "I understand that the focus here is on minimizing feedback from the seller for obvious practical reasons (lines 52-61). However, it seems to me that the roles of the buyer and the seller are theoretically interchangeable in your setup. Therefore, I'm left with the question of whether, theoretically, your algorithm can be easily adopted in a scenario where we want to minimize the feedback from the buyer ..."

We agree with the reviewer, the roles of sellers and buyers are interchangeable, we will specify this better.

Re: "I don't quite understand how the examples mentioned in the Introduction—such as online freelance marketplaces (Upwork, Fiverr), ride-sharing platforms (Uber, Lyft, Grab), and rental intermediaries (Airbnb)—correspond to the framework presented in this paper. Could you explain in more detail how the paper's algorithm would be applied in these domains? Based on my own user experience, these platforms appear to display the seller's price directly, which seems to be a complete mismatch with the framework presented in this paper, where a broker sets a single price for both parties. "

We are not claiming that Upwork/Fiverr, Uber/Lyft/Grab, or Airbnb currently run our mechanism (a single price posted symmetrically to both sides). Many use two distinct pricing/selection steps and monetize the spread between buyer and seller prices. We propose a viable alternative: the platform quotes the buyer a transfer price $p$ and, only if the buyer accepts, pings a seller at the same $p$, yielding exactly the feedback we analyze (buyer bit each round; censored seller bit only after buyer acceptance). In this zero‑spread design, we explicitly maximize gain from trade (the traders’ joint surplus under strong budget balance), so the platform can credibly commit to optimizing user welfare rather than extracting a spread, a stance that plausibly increases entry and retention of traders. Crucially, monetization is decoupled from $p$: the platform can earn via advertising or sponsored placement, subscriptions/memberships, or fixed per‑trade fees independent of $p$, all without changing the acceptance logic or our theoretical guarantees.

Re: "The technical novelty is not clear, as the framework and algorithmic approach of this paper heavily overlap with Section 5 of 'Bilateral Trade: A Regret Minimization Perspective' by Cesa-Bianchi et al. [2024a]. Even thought the authors argue that the samples from sellers are asynchronous and asymmetric, the core concepts are the same: the decomposition principle, the grid-based approach, and the strategy of first estimating the integral terms and then using a bandit-style method to explore and exploit the local terms. The amount of new content proposed in this paper is quite limited."

We agree with the reviewer that our algorithm shares similarities with the one by Cesa‑Bianchi et al. 2024a, as also noted in our paper. However, the main contribution of our work is analytical: we establish regret bounds comparable to those of Cesa‑Bianchi et al. under strictly weaker, censored (1.5) feedback. We remark that under this 1.5 feedback the algorithm they propose (Scouting Bandits) does not even run. Additionally, the 1.5‑feedback setting poses unique challenges: seller feedback at a given price $p$ is observed only when the buyer accepts. Consequently, some prices receive very few seller‑side samples, inflating uncertainty about willingness to sell and potentially hindering optimal rates. To address this, we derive (via multiplicative Chernoff bounds) a lower bound on the number of rounds in which seller feedback is observed at price $p$. We stress that because the underlying variables are Bernoulli with potentially small means, additive Hoeffding‑type bounds (as employed by Cesa‑Bianchi et al., 2024a) are ineffective in this rare‑event regime. Together with the fact that when seller‑side confidence intervals are large the buyer‑acceptance probability is low, a careful analysis shows that these two competing effects in fact compensate each other, allowing us to recover the same regret rates despite censoring.

Re: "This paper has no experiments at all, neither on synthetic nor on real-world data. Therefore, without experiments, it's unclear how the algorithm actually performs in practice or how it behaves with a limited amount of data."

In the following table, we report the numerical values obtained by running our algorithm (using 1.5-bit feedback) and the state-of-the-art algorithm by Cesa-Bianchi et al. (2024), which uses 2-bit feedback. In each instance where we ran the two algorithms, the buyer and seller valuations were drawn from Beta distributions with the parameters $\alpha_b, \alpha_s, \beta_b, \beta_s$ specified below. Each experiment was repeated $n = 5$ times, and the final regret values correspond to the mean over these $n = 5$ runs.

We observe that the regret incurred by our algorithm is lower than that of Cesa-Bianchi et al. 2024a. While this may appear counterintuitive (since we use less feedback than the Scouting Bandits algorithm of Cesa-Bianchi et al.) the improvement stems from a key difference: after the initial exploration phase, we eliminate arms that are guaranteed to be suboptimal. This pruning step, absent in Scouting Bandits, allows us to restrict the subsequent bandit phase to the reduced set $K^\diamond$ (see Line 12), which can be significantly smaller than the original set of arms. In contrast, Cesa-Bianchi et al. 2024a run their algorithm over the full set, whose size is $T^{1/3}$.

Re: "I think the most concern raised from my side is the lack of numerical experiments. Although this work is theoretic-oriented and the theoretical results are contributive, I still think it is particularly necessary for this paper to have at least simulations. "

In the following table, we report the numerical values obtained by running our algorithm (using 1.5-bit feedback) and the state-of-the-art algorithm by Cesa-Bianchi et al. (2024), which uses 2-bit feedback. In each instance where we ran the two algorithms, the buyer and seller valuations were drawn from Beta distributions with the parameters $\alpha_b, \alpha_s, \beta_b, \beta_s$ specified below. Each experiment was repeated $n = 5$ times, and the final regret values correspond to the mean over these $n = 5$ runs.

We observe that the regret incurred by our algorithm is lower than that of Cesa-Bianchi et al. 2024a. While this may appear counterintuitive (since we use less feedback than the Scouting Bandits algorithm of Cesa-Bianchi et al.) the improvement stems from a key difference: after the initial exploration phase, we eliminate arms that are guaranteed to be suboptimal. This pruning step, absent in Scouting Bandits, allows us to restrict the subsequent bandit phase to the reduced set $K^\diamond$ (see Line 12), which can be significantly smaller than the original set of arms. In contrast, Cesa-Bianchi et al. 2024a run their algorithm over the full set, whose size is $T^{1/3}$.

Re: "Besides, there are some drawbacks from the modeling assumptions, e.g. the finite price set, the i.i.d. assumption, the bounded density, etc. Some of them are not well justified."

From a mathematical point of view, rescaling prices to lie within $[0,1]$ is a standard assumption in the bilateral trade literature, adopted primarily for convenience. We note, however, that our algorithm can be readily adapted to any bounded interval $[0,M]$ through an appropriate rescaling. If valuations and prices instead range over $[0, +\infty)$, and no further assumptions are made, one can easily show that any algorithm must incur linear regret. That said, from an economic point of view, it is arguably realistic to assume the existence of an upper bound $M$ on the value of any given good.

From a mathematical point of view, removing the i.i.d. assumption is known to lead to linear regret rates (see Theorem 5 in Cesa-Bianchi et al. 2024a). That said, from an economic point of view, the i.i.d. assumption can be interpreted as modeling interactions between a broker and a large, stable market. Specifically, if the population is sufficiently large that each seller–buyer pair can be viewed as independently drawn (i.e., sampling with replacement), and if the market is stable over time so that the distribution of valuations remains unchanged, then the overall process can reasonably be treated as i.i.d..

Again, from a mathematical point of view, removing the bounded density assumption (Lipschitzness of the cdf) is known to lead to linear regret rates (see Theorem 6 in Cesa-Bianchi et al. 2024a). Economically, this assumption rules out highly concentrated valuation distributions and instead reflects the idea that agents are sufficiently heterogeneous in how they value the good. This heterogeneity is a natural feature of many real-world markets, where valuations emerge from the interaction of multiple factors, such as individual preferences, time constraints, opportunity costs, available alternatives, expectations, budget limitations, and even random noise. For instance, two sellers offering the same service on platforms like Airbnb or Fiverr may have different reservation prices due to variations in location, experience, urgency, or subjective valuation of their time. Likewise, buyers differ in urgency, purpose, willingness to pay, and familiarity with the platform. Moreover, digital marketplaces are typically designed to support broad participation, encouraging diversity in both supply and demand. The bounded density assumption essentially captures markets containing a wide, continuous spectrum of agent types.

We will add this discussion about the implications of our assumptions in the revised version.

Re: "What is the computational complexity of the algorithm, particularly the dependence as you adopt the grid-based approach?"

The per-round computational complexity of our algorithm is linear $K=T^{1/3}$, with $K$ being the size of the grid employed by our algorithm.

Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Bilateral trade: A regret minimization perspective. Mathematics of Operations Research, 49(1): 171–203, 2024a.

That sounds really excited (and counterintuitive which is not bad). I am supporting this work with an increased score, while I also have the following suggestions:

(1) For the numerical experiments, maybe it is possible to also improve the baseline (Cesa-Bianchi et al. 2024) with your policy elimination design. This helps explain whether the indeed optimal regret (from the perspective of problem hardness) of the 1.5-bit feedback problem is smaller than that of the 2-bit one.

(2) Please not only print the regret comparisons but also the reward comparisons on two aspects: one for baselines, and the other for algorithms. This helps indicate how the 1.5-bit feedback contrasts the 2-bit one.

Re: "It would be valuable to discuss how sensitive the algorithm is to violations (e.g., if densities have unbounded spikes) and whether weaker smoothness conditions (e.g., Hölder) suffice."

Great question. Without regularity, sublinear regret cannot be guaranteed uniformly. In particular, if one allows unbounded density spikes, we can tune the spike height with the time horizon to force linear regret for any learning algorithm. Formally, we can adapt the lower‑bound idea of Cesa‑Bianchi et al. (2024a, Thm. 6) to smoothed distributions: let the seller pdf be:

$f_S(u)= M \mathbf{1}_{[0,\frac{1}{2M}]}(u) + M \mathbf{1} _{[x-\frac{1}{2M}, x]} (u)$,

and the buyer pdf

$f_B(u)=M \mathbf{1}_{[1-\frac{1}{2M}\,1]}(u) +M \mathbf{1} _{[x\,x+\frac{1}{2M}]}(u)$,

so both integrate to 1, for some $x$ near $\frac{1}{2}$. First, by Yao’s principle, it suffices to consider deterministic algorithms in this i.i.d. setting. If we choose $M=2^{\Theta(T)}$, then for any deterministic algorithm there exists an $x$ such that the algorithm never plays in the optimal interval $[x-\tfrac{1}{2M},x+\tfrac{1}{2M}]$, yielding $\Omega(T)$ regret. Intuitively, locating that interval requires $\Omega(\log M)=\Omega(T)$ informative plays (a “binary‑search‑like” effort); until then, the per‑round regret remains bounded away from zero. Equivalently: no uniform sublinear rate is possible over classes that permit arbitrarily tall, narrow spikes. On the other hand, weaker smoothness suffices. If the cdfs $F_S$ and $F_B$ are $\alpha$-Hölder with constant $L$, one can still control the discretization error. Using Lemma 1 of Cesa‑Bianchi et al. (2024a), for $0\le p<q\le 1$,

$|g(q) - g(p)| =\left| F_S(p) \int_p^1 (1 - F_B(u))du + (1 - F_B(p)) \int_0^p F_S(u)du - \left( F_S(q) \int_q^1 (1 - F_B(u)) du + (1 - F_B(q)) \int_0^q F_S(u) du \right) \right|$

where the last inequality uses $|q-p|\le1$ and $\alpha\in(0,1]$. Thus $g$ is $\alpha$-Hölder, the discretization bias scales as $K^{-\alpha}$, and with appropriate tuning of $K$ one obtains sublinear regret. Whether these rates are minimax‑optimal under Hölder cdfs is an interesting open question we leave for future work.

"Re: Have you considered studying information-accuracy tradeoffs such as: How much mutual information about the optimal price does each feedback bit supply ? What regret rates are achievable if you deliberately limit feedback to, say, one bit every other round, or to noisy bits? How much “value” does each bit contribute toward narrowing down the optimal price?"

Very interesting questions! Unfortunately, we are not familiar with the literature analyzing online learning algorithms through the information-theoretic lens; thus, we cannot fully answer the questions raised by the Reviewer. However, we believe that such questions are very relevant to our paper, as they go towards the direction of deeply understanding what is the contribution of asymmetric feedback to learning the optimal price. We will surely investigate these aspects in future works.