Online Bilateral Trade With Minimal Feedback: Don’t Waste Seller’s Time
Authors: Francesco Bacchiocchi
Matteo Castiglioni
Roberto Colomboni
Alberto Marchesi
Venue: NeurIPS 2025 poster ()
Keywords: Bilateral Trade
Online Learning
Censored Feedback
Primary area: theory

Abstract: Online learning algorithms for designing optimal bilateral trade mechanisms have recently received significant attention. This paper addresses a key inefficiency in prior two-bit feedback models, which synchronously query both the buyer and the seller for their willingness to trade. This approach is inherently inefficient as it offers a trade to the seller even if the buyer rejects the offer. We propose an asynchronous mechanism that queries the seller only if the buyer has already accepted the offer. Consequently, the mechanism receives one bit of feedback from the buyer and a "censored" bit from the seller---a signal richer than the standard one-bit (trade/no-trade) feedback, but less informative than the two-bit model. Assuming independent valuations with bounded densities---the same distributional conditions underlying the two-bit results of Cesa-Bianchi et al. [2024a]---we design an algorithm that achieves $\tilde{O}(T^{2/3})$ regret against the best fixed price in hindsight. This matches the lower bound for the strictly richer two-bit model, showing that our mechanism elicits the minimal feedback necessary to attain optimal rates.

Online Bilateral Trade With Minimal Feedback: Don't Waste Seller's Time
Francesco Bacchiocchi Politecnico di Milano
Matteo Castiglioni
Politecnico di Milano
francesco. wwwchiacchi aacchiocchh@@olimii it
matteo. castiigiiiiiii@lliiiiiiii.. it
Roberto Colomboni Politecnico di Milano & Università degli Studi di Milano
Alberto Marchesi
Politecnico di Milano al alberto. marchesi
@polimi..... www.ceee@@oooommiiiii.........mi
roberto. col www.omoooooooooooooooooooooooo @polimiplmm....mmmmm
Abstract
Online learning algorithms for designing optimal bilateral trade mechanisms have recently received significant attention. This paper addresses key inefficiency prior two-bit feedback models, which synchronously query both the buyer and the seller for their willingness to trade. This approach is inherently inefficient as it offers a trade to the seller even when the buyer rejects the offer. We propose an asynchronous mechanism that queries the seller only if the buyer has already accepted the offer. Consequently, the mechanism receives one bit of feedback from the buyer and "censored" bit from the seller-a signal richer than the standard one-bit (trade/no-trade) feedback, but less informative than the two-bit model. Assuming independent valuations with bounded densities -the same distributional conditions underlying the two-bit results Cf Cesa-BBini al. [2024a] we design algorithm that achieves (T7)) regret against the best fixed price in hindsight. This matches the lower bound for the strictly richer two- bit model, showing that mechanism elicits the minimal feedback necessary attain optimal rates.
Introduction
In bilateral trade problem, a broker faces two rational agents seller and buyer-who wish to trade an object. Each agent has their own private valuation for the object and seeks to maximize their utility. The goal of the broker is to design mechanism that intermediates between the seller and the buyer, in order to make trade happen. Ideally, mechanism for bilateral trade should be efficient, i.e., it should maximize the sum of agents' utilities, while also ensuring incentive compatibility and individual rationality. A well-known mechanism that achieves this objective is the VCG mechanism [Vickrey] 1961]. Unfortunately, the VCG mechanism fails to meet budger balance, requiring the broker to subsidize the market and incur in financial losses. Indeed, general impossibility result by Myerson and Satterthwaite [9833 shows that full efficiency cannot be attained while simultaneously maintaining incentive compatibility, individual rationality, and budget balance.
recent line of research (see, e.g., (Cesa-Bianche et al. 2021 2024a Azar et al., 2022 cireumvents the impossibility result by Myerson and Satterthwaite/ 1983 through the lens of online learning. This done by addressing repeated bilateral trade problems, where the broker faces a sequence of sellers and buyers willing to trade objects, over time horizon T. At each time f, new seller and new buyer arrive, each of them with their own private valuation of the object, say S, and B,, respectively. The broker then proposes a trading price P. to both agents. Thus, the seller is willing to trade S, < P., while buyer if B, P.. The trade happens only if both agents accept the price P,, with
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

the buyer paying the trading price to the seller and receiving the object, resulting in strong budger balance (i.e., the broker neither subsidize nor extract revenue from the market). In such an online learning framework, the full-efficiency requirement is relaxed by comparing the performance of the broker over the T time steps against the best fixed price in hindsight. Specifically, the performance evaluated in terms of the gain from trade, which intuitively encodes the net gain in agents" utilities, defined as (B, - S,) S P: S Br} at each time t.
Previous works have focused on three models that differ in the kind of feedback that the broker receives at the end of each time step f. In the full-feedbac model, the broker observes the valuations St and B, of the agents. In the two-bit model, the broker separately observes whether each of the two agents is willing to trade or not, namely they observe both [[S; S Pt) and I(P: < B.). Finally, in the one-bit model, they only observe whether the trade has occurred or not, namely I[S, S P. S B,}.
While simple, the one-bit model is insufficient for learning optimal anisms (Cesa-Bianchi et al. [024a]. This motivates the study of richer feedback models, such as the two-bit one, where learning becomes possible under the assumption of independent seller/buyer valuations with bounded densities (Cesa-Bianchi et al. [002aa]. However, such mechanisms rely on synchronous interaction protocols that are inherently inefficient: they query the seller even when the buyer has already rejected the trade. In this paper, we address the following two natural questions:
mech-
What is the minimal feedback required to learn optimal mechunisms? Is it possible to query the seller only when trade opportunity arises?
From a more application-orian oriented perspective, these questions raise from the insight that would generally be more efficient- and more reasonable-to implement asynchronous interaction protocols, in which the seller is approached only if the buyer has already agreed to trade at the proposed price. This approach is especially relevant in many practical applications such as, e-g., online freelance marketplaces (Upwork, Fiverr), ride-sharing platforms (Uber, Lyft, Grab), rental intermediaries platforms - sellers are often involved in multiple simultaneous trading scenarios involving different objects. In such settings, requiring the sellers to make a decision each time a potential buyer for any of their objects appears would impose an excessive burden on them. Furthermore, in many cases, sellers prefer to disclose as little information as possible to the broker in order to protect their reputation.
Our Results We study-for the first time, to the best of our knowledge- online learning in bilateral trade problems with asynchronous interaction protocols. The key challenge in such a setting is that the broker receives a particular asymmetric feedback that is richer than one-bit feedback, but way less informative than two-bit feedback. Specifically, the broker receives one bit of feedback from the buyer, by observing I, 2 P.) at every time I, while they only observe "censored"' bit of feedback from the seller, as they get to know I[S; < } only when the buyer accepts the trade. The main sesely-budge--ball
result of the paper is a fixed price in hindsight, assuming independent sellers and buyers' valuations with bounded densities. Notice that both assumptions are required, since removing even one of the two assumptions makes the problem not learnable even with two-bit feedback (Cea-BBianche et al.) 2024a]. We remark that our result matches the regret rate that -ieaa-Biancch et al. [2024a] obtained using the more informative two-bit feedback, under the same distributional assumptions. Moreover, it matches the lower bound by Cesa- -asachianchi et al. 2024a] for the richer two-bit bit feedback model, showing that:
algorithm that attains ((7%)a) regret against the best
Asynchronous protocols are not only efficient, but they also allow the broker to
elicit the minimal feedback necessary to altain optimal regret rates!
1.1 Challenges and Techniques
Our algorithm builds upon the idea of scouting bandits, which have been originally introduced by Cesa-Bianchh et al. 2024a for two-bit models. This idea exploits a suitable decomposition of the expected gain from trade g()) for a fixed price p E [0, 1], which is defined as follows:
g(p) P(S sp
P 2 Md
P < xdd
(a)
(c)
(b)
(d)

---

where S and B are generic random variables representing the valuations of the seller and the buyer, respectively. [Cesa-Bianchi Bianchi et al. [2024a] leverage the two-bit feedback by first conducting a uniform exploration phase to estimate the integral terms (b) and (d). Using these estimates, they construct a proxy for the expected reward function in which (b) and (d) are replaced with their empirical counterparts. Then, they run a handit algorithm with this proxy, since the two-bit feedback provides, at each time step, unbiased estimates of terms (a) and (c), thereby allowing the learner to reconstruct the proxy reward function.
Our asymmetric feedback model introduces a new significant challenge: the feedback received from the seller is "censored", as the learner gets to know the value of I[S,; < P only when the buyer accepts the trade, i.e., when [[P, < B 1. This "censored" seller's ss feedback makes the scouting bandits approach by (CeseCeaiina Bianchi et al. 2024a| unsuitable for our setting: the estimator they build for the integral term (d) cannot be recovered due to missing observations, and the bandit feedback needed to estimate term (a) may be "censored" and thus unavailable. Furthermore, our feedback breaks the symmetry in estimating the four components in the decomposition of the expected gain from trade provided by the two-bit feedback. Indeed, in our model, estimating (a) is harder than estimating (c), and estimating (d) is harder than estimating (b). Consequently, the main challenge faced in this paper is how to effectively estimate (a) and (d) under "censored" seller's feedback. Our key technical contribution is addressing this challenge
In order to address the challenge, we provide a lower bound on the number of time steps in which the value of I[S, S p} (i.e., the seller's feedback for p) is observed, for every price p. particular, if price p is posted for H times (and IP[ 2 y] is large enough), we can lower bound the number of times that seller's s feedback is observed as 52 H P 2 pl). by using Chernoff's concentration bound. Notably, the usual additive concentration bounds are of no help this setting. Indeed, our random variables are Bernoulli that might have small mean, making additive bounds non-meaningful Moreover, the lower bound on the number of times the seller's feedback is observed could still be small. As consequence, we may lack sufficient samples to build precise confidence bounds around terms (a) and (d), thus precluding the direct application of standard UCB-like techniques. However, we observe that when the confidence intervals on seller-related quantities are large, the buyer's probability of accepting the trade low, resulting in two effects that counterbalance each other. More formally, the error on term (d) is scaled by the buyer's acceptance probability-nane -namely, term (c). A symmetric argument holds for terms (a) and (b).
1.2 Related Works
Our work contributes to the line of research initiated by Cesa-Bianchi et al. [2024a], which studies bilateral trade through the lens of online learning. Among other results, [Ceaa Bianchi al. [2024a] show that strongly- wel--buddgetaaadd balanced mechanisms are learnable with two-bit feedback when the seller/buyer distributions are independent and admit bounded density, while the same problem is unlearnable under one-bit model.
Subsequent work focuses mainly on adversarial settings. Azar et al. [022] design algorithms that guarantee no-2-regret. (Cesa-Biand) et al. [2024b) provide sublinear regret guarantees assuming a smoothed adversary. [Bernasconi et al. [2024]. Chen et al. [2025) remove the smoothness assumption by relaxing the budget balance constraint to hold globally. Lunghi et al. [2026] go even further by analyzing which regret rates are attainable by relaxing the global budget constraint (i.e., by allowing for its violation). Other works study extensions of bilateral trade to multiple buyers [Babaioff et al.
2024 Lunghi et al. 2025), different objectives [Bachoe et al., 2024 contextual settings |Gaucher ct al. 2025]. ), divisible items [Bolić et al. 2025). J. and situations where traders have no predetermined seller and buyer's 'ss roles [Bolić et al.) 2024 Cesari and Colomboni 2025 Bachoc et al. 2025a
There also a rich literature on bilateral trade without learning, focusing on providing approximations
of an optimal mechanism (Colini-Baldeschi et al.] [0166] [017]] Blumrosen and Mizrahi 2016 Brustle
ct al. 2017, Colini-Baldeschi et al. 2020 Babaioff et al. 20200] Dütting et al. 202 Deng ct al.
2022
Kang and Vondrák 2019
Archbold et al. 2023
We remark that, from a technical point of view, the roles of the seller and the buyer in our framework are completely interchangeable without requiring additional effort. Indeed, the case in which we query the buyer only when the seller agrees to trade at given price can be tackled with the same approach presented here.
3

---

2
Preliminaries
In this paper, we study online learning in repeated bilateral trade problems. In this section, we introduce the notation and all the definitions needed in the rest of the paper.
2.1 Bilateral Trade
The learner (a broker) repeatedly interacts with the environment. At each time step E [7], new seller and new buyer arrive with (random) valuation S, and B, in [0, [
The learner offers (random) price Pt E [0, 1] to the buyer and the seller. A trade happens if and only if the buyer and the seller accept the proposed price, i.e., when St S P. S B,. This ensures strong budget balance is satisfied during learning. The learner's performance is evaluated through the net increase market value (i.e., the net increase in agents' utilities), also known as gain from trade. Specifically, if we define the gain from trade function as
gft: [0, 1 [0,
(p.
(b-p (1- (b- s)I{s S ps b}
buyer's
sellers's
trade happens
net gain
and the gain from trade (random) function at time t
GFT;; [0, 1] + [0, 10.11,p- - gft(p, St, B.).
the gain from trade rewarded to the learner by posting P; the random variable GF.),
We assume that the sequence of sellers' valuations S2.... and the sequence of buyers' valuations B1, B..... are i.i.d. sequences, independent of each other. Moreover, for ease of presentation, introduce two additional random variables S and B, which are distributed as Sy and B,, respectively. We assume that S and B are independent of each other and of the two sequences S2....... and B1, . and that they admit L-Lipschitz continuous cumulative distribution functions (cdf)
For notational convenience, also define the random function
GFT : [0, 1] [0, 1],
p S,
and the expected gain from trade function as
g [0, 1| + [0, 1], p+ E[GFT()]
We notice that consequently, being defined on the compact set [0, 1). it admits maximum. From this point on, fix a point p² E [0, 1] where this maximum is attained.
et al. 2024a Lemma 2] ensures that g is upper semicontinuous and,
2.2 Do Not Waste the Seller's Time: An Asynchronous Protocol
is well known (see Cesa-Bianchi et al. 2024a] ) that learning is impossible with one-bit feedback,
i.e., when the learner only observes the outcome of the trade I(S, < P. < B,} after each time step f. For this reason, previous works focus on two-bit bit feedback, where the leaner can separately observe seller and buyer's 's willingness to trade, namely IÇS, < P.} and I(P, B, }. In this paper, we show that the regret attainable with two-bit feedback can also be obtained with a weaker feedback, under the same assumptions. In particular, a trading price to the buyer, and, then, offers the same price to the seller only if the buyer has already expressed their willingness to trade the proposed price. This protocol introduces new asymmetric feedback model in which the leaner receives one bit of feedback from the buyer, while it gets "censored" bit from the seller, their willingness trade is observed only when the buyer accepts to the trade at the proposed price.
consider asynchronous protocol that first proposes
The asynchronous interaction protocol between the learnrr (a broker) and the environment (the sequence of sellers and buyers) is formally presented in Online Protocol
Let n E N, we denote with [n] = {1,...,,1) n the set of the first n natural numbers.
"hhe edf Lipschitz assumption equivalent to the bounded density one of Cesa-Bianchh al. 2024a

---

Online Protocol Asynchronous Repeated Bilateral Trade
1: for time step i 1.. do
2: The learner chooses P. E [0,
3: The learner observes (PP < BB}
4: P; S B,, then the learner observes I {(, S Pr]
5: The learner gains (but does nol observe) (F:),(P)
Regret Given a time horizon T N, the goal of the learner minimize the regret with respect to the gain from trade, defined as
T RT Σ (x(e') "ale")-B[g(P)) B[g(P:)))
where p" E arg pe
3 Algorithm
In this section, present online learning algorithm that achieves optimal regret guarantees under the asynchronous interaction protocol introduced in Section 2 Our learning algorithm restricted to using finite grid of prices. In Section 4 we show that this results in small loss that depends the granularity of the grid and the Lipschitz constant L. Specifically, we denote by Pk S [0, 1] the uniform grid of prices Pk R-1/K for [K], where K is suitable parameter. More formally, let Pk= = (pk ke(K]-
3.1 Additional Notation
Before moving to the description of our algorithm, we need to introduce some additional notation that is useful to deal with the stochastic feedback observed by posting prices the grid. For each E [K] and each j E N, we denote with to (k, the j-th time step in which the broker sets price Pk Pr (if this time step exists, otherwise, set it to +o0), and with (k, the j-th time the broker sets price pı E PR and the buyer accepts to buy (it this time step exists, otherwise we set +0o). For technical reasons (i.e., having well-defined random variables for every A E [K] and j E N), we also assume given another i..dd. family of pairs of random variables (5k.) B independent of (81, B1), (S2, B2).... such that, for any k E [K] and j E N, the pair (5% Bk,)) shares the same distribution as (S, B). For each k [K] and j E N, we then set
(ie((.)) if (k,, < t00, BB
Sk.5 = (ts(k))) tf < t00
B =
otherwise,
otherwise
In this way, the family (Sk Be.K)ee[KTJeN is well-defined independent family of pairs of random variables such that, for every & E [K], the sequence (Sk.j- BaJ)jeN is i...d,, and, additionally, for every j E N, the pair (Sa., BR.j) shares the same distribution as (S, B).
3.2 Algorithm Description
We are now ready to introduce our algorithm achieving optimal regret guarantees under the asyn- chronous interacton protocol (Algorithm 2). The algorithm takes input a time horizon T, and it builds the uniform grid 'Px C [0, 1] with K = [T points. At very high level, our algorithm performs an initial exploration phase in which the broker plays each of the prices Pk a number of times equal H := [a' This exploration phase is necessary to compute an optimistic estimate of the expected gain from trade, as defined in eq. (1) in the following. Once this exploration phase concluded, in the remaining time steps, Algorithm executes a K Karree bandit-style algorithm by selecting, at each time, the price ps E Px that maximizes suitable optimistic estimate of the expected gain from trade. Notice that several additional components discussed in the following are needed to deal with the limited feedback.
5

---

Algorithm 2 More than one-bit less than two-bit bilateral trade
1: Input: time horizon T
2: Set + 72, + K + 1 Tk.0 + O, @x.o + 0,8k,u 0 Vk [K]
3: Set Px t- {pk ]E(K]] with pa +- 1-1/K Ak [K], K +
4: for / = 1, ...,...,, T do
5: if S KK then
Exploration Phase
6: Set < [1/H] and post price Pe < Pt
7: else
Bandit Phase
8:
Select E argmax;ek* UCB (see eq. and post price Pe +- P
9:
for k 1,2. ..K do
b Update Counters
10:
if НK then
11:
Ng f miniss QH
12:
K + {k E [K] QK 2 32 32log(KT3
F& KH Link
K-1
2j H H 2 pi}, Vk E K
14:
GK + I
KNt Eim1 Ej=1
IS pi), Ak K
15:
Set Th, + Tk,-1 + 1(P: }k}
16:
Set 2 - 2x,--1 I[P: - Pb: PHt P v B.}
17:
Set Sk, <- Sk,--1 + I(P: = [[S S PI) S B.)
Set DR,e The
Quit and pu,t +
Sa.1
DA.t
We now provide more detailed description of how the algorithm works. Specifically, in the first KH time steps, Algorithm prescribes the broker to play each price on the grid Pk exactly H times the first H time steps on Pl, the next H on p2, and so forth-so that this initial phase has length K H. Furthermore, independently of the round / E [T], Algorithm 2 maintains counters that track how many times each price Pt: has been selected. Precisely, each round E [T]: TE, counts the number of times the broker has proposed price pk up to round [T]: Qx.e counts the number of times the buyer has accepted to buy at price pę; and Sx, counts the number of times both the buyer and the seller have agreed to trade at price Pk.
Once the exploration phase is completed i.e., after KH rounds rounds-Algorithm Algorithm identifies a subset of arms K C [K] such that, for each h E K the number of samples collected from the seller's s distribution when the broker has proposed price Pı is larger than suitable constant. After that, the algorithm ignores all the arms not in K while for each arm in K it designs upper confidence
bound on the gain from trade (refined at each round), by exploiting the decomposition:
g(p) PIS S
P +
P < A
(1)
(a)
(c)
(d)
which is formally derived in Cesa-Biaancii et al.
2024a Lemma 1].
Furthermore, order to build the upper confidence bounds to be used in the subsequent bandit-style procedure, for each & E K after the exploration phase Algorithm computes two estimates of the integral terms (b) and (d) in eq. ( which are defined as follows:
K- H KH
N (SE, S SP),
[Br 2 ps),
GR
KN
i= 1=
==
where
No min Q ISk
Let us remark that the definition of the term N₂ is necessary to ensure that, in the sum in Ög, we have the same number observations of the seller's valuation for each price p: with S k. Indeed, while for every pk always observe whether the buyer accepts to buy or not, we do not have analogous

---

information for the seller, since the observation of seller's feedback is conditioned on the buyer's decision buy at the given price.
In the remaining rounds > KH, Algorithm 2 performs a UCB-style procedure using K as the can guarantee useful concentration
set of arms. This refinement of the arm set is necessary, properties only for the arms in K Specifically, at each round > K H. Algorithm computes optimistic upper confidence bounds UCB,,, on the value of each g(px) for prices pa such that & K formally defined as follows:
1og(21/))
2 12g(220) FA +
UCB = jiR,
2Qu,
HK
log(2T/6))
2 2lg(22/))
+
Gk +
(3)
2Tx,
KN
One of the main challenges in algorithm analysis will be to show that the upper confidence bounds concentrate on the true mean. This is particularly challenging since Qk. might be small.
Regret Analysis
In this section, we prove the regret guarantees attained by Algorithm 2 In the following, for the ease of presentation and to avoid repetitions, we assume that a time horizon T' is given as a parameter, and we set every occurrence of to T2 and every occurrence of K and H [T'/3], as in Algorithm
Our algorithm can be easily extended to an anytime version that does not need knowledge of T by using the standard doubling trick [Cesa-Bianchi and Lugosi 2006
4.1 Restrict the Set of Candidate Prices
In the following, we will show that our algorithm has no regret with respect to the best price on the grid Px. This is sufficient since the best price in Px performs almost well as the best price in the interval [0, 1]. as we formally show in the following lemma.
Lemma 1. It holds that:
max g(p) 2 g(pp" L/K. PEPK
Proof. Let k* [K] be such that Pk* minimizes the distance from p² among all the points in Pg. Noticing that a random variable 1/L-smooth an only its edf L-Lipschitz continuous, Cesa-Bianchi et al. 2024b) Lemma 1] ensures that g is L-Lipschitz continuous, and hence
g(p")
max g(p) I g(p") g(px-) ) I L 1p" ps < L/K.
PEPK
4.2 Define a Clean Event
We now introduce some definitions aid the presentation. First, define set K. (unknown to the learner) that intuitively identifies the prices pk E Px in which feedback about the seller can be observed with sufficiently high probability, under the asynchronous interaction protocol.
Definition 1. We define K. as the subset of le E [K] such that:
P(B Pk] -// logg (
We will show that for prices in K. our estimates are sufficiently accurate, while prices not in KC can be ignored. Indeed, this is because they achieve negligible expected gain from trade.
Moreover, we also introduce the following definition of clean event E. Intuitively, this is decomposed into four different events, namely ε₁, E2, Eg, and Eq. These events are related different high- probability concentration bounds. The event E₁ is defined as follows:
Th. PP pul
E
n
(=HK
7

---

Intuitively, under this event, the broker receives feedback about the seller at price at least half of the times the price Ps proposed. weighted by the probability that the buyer accepts it. It can be shown that this event holds with high probability by the aid of Chernoff's inequality. This event guarantees that we observe a constant fraction of the "expected" samples.
The event E2 is related the estimates Gx and Ps of the integrals appearing in the definition of gain from trade. In particular, it requires that the estimates lie in their respective confidence intervals. Formally, have:
Eg
n KEK:
Gx
Ph PIS
A/dA
210g(2/5)
1
KNN
K
2 (2/() HK
Pk P[ Aa
K
kE[K]
Pe.
The underlying idea is to show that GR is close to its expectation up to Ô (//KN, NN,) with high probability due to combination of Chernoff and Azuma-Hoeffding Hoeffding's inequality. Moreover, the expectation B[Ga] is close the integral term (d) in eq. (1. leveraging the rectangle rule to compute integrals and the fact that the integrand function monotone to obtain telescopic simplifications. An analogous argument holds for the terms F' as well.
Furthermore, &g is the event in which the estimates Pu,t and kx.t of the probabilities of the seller and the buyer accepting the trade, respectively. lie confidence intervals that shrink as the inverse the square root of the number of observed samples.
T Eg
log(2T/5)
1og(2T/0)
n
SPIS S pa. S PR.t +
2Q
2Qu,r
t=KK
KE[K]
T
log(2T/6)
log(2T/8)
< < 2 pa] S Dz. +
2Tk,
2Tk,.t
(=HK kE[R]
That &g holds with high probability a consequence Hoeffding's 's inequality and a union bound, once we realize that, for each & E [K]. the sequence (Skg, BR.j)jeN is i.i.d..
Finally, the event & guarantees that if a price pk has too low probability of being accepted by the buyer, i.e., k & IC, then such price will not belong to the set K of candidate optimal prices used by the algorithm in the second phase. Formally, we have:
E = N (O.KEE S 32 AEEK
KT 8
Intuitively, also the probability of event Ea can be bounded by using Chernoff inequality. This event important to avoid running the second phase on prices pke that have too low a probability of being accepted by the buyer. This would result in small number of samples and huge confidence intervals. Moreover, such prices can be safely discarded as their expected gain from trade small.
Finally, by bounding each event separately and applying union bound, we obtain the following lemma, which establishes the probability with which the clean event & holds.
Lemma 2. Let == E n & 4 Then, we have;
P| OKKT8).
We defer the formal proof of this lemma to the Appendix.
4.3 Bound the Regret
Next, we introduce two crucial lemmas that enable us to derive the regret guarantees Algorithm 2 Intuitively, the first lemma shows that, under the clean event E, the first term of the upper confidence

---

bound employed by Algorithm concentrates towards the first term in the gain from trade decom- position, i.e., the product of (a) and (b), at the desired rate. Moreover, it shows that our confidence bounds are always optimistic, an essential requirement for UCB-like algorithms. The second lemma shows an analogous result, but for the second terms.
Lemma 3. Let k K. Then, for each 1. 2 HK, conditional on the event &, we have:
0
Pa.t +
1og(2T/0)
F&t
2 210g(2/0)
+
1 K
P
P[B 2 MjP m.
2Q
HK
where 1) C' (7)
T (T
- VTx..)
and C > 0 is an absolute constant.
The above lemma shows that the difference between the first component of the confidence bound UC (defined in eq. (3) and the first component of the expected gain from trade is proportional to TT.T.. At a first glance, this is not what we would expect since the empirical mean fuu. is estimated using QR, samples. Thus, the confidence bound of fúg, is proportional to 1/ver... However, such a term is multiplied by (an upper bound of) the probability that the buyer accepts the offer, i.e. F|B 2 Pk]. Thus, if the confidence term is large (i.e., when Qx, t is small). then the probability that the buyer accepts the trade is low, These two effects compensate for each other, and the resulting contribution ends up scaling as /T.TE. We defer the formal proof of this lemma the Appendix.
Lemma 4. Let k E K. Then, for each I. 2 HK, conditional on the event &, we have:
ss (oat + v 2
/1og(2T/8)
2 2lo((2/8)
1
Pa] J
Ph P(S AAds n,
Gk
P(B
2Tk,
KN
K
where 1) = C'log (H)
71/ +
Tiu.. and C > O is an absolute constant.
Similarly to Lemma the estimate GR is constructed using number of samples that depends on the probability that the buyer accepts to trade at price pt- This component is mirrored with respect to the one in Lemma 3 rather than having limited samples for the probability estimate vx,,, here may have few samples compute Gg. the term that corresponds the integral estimates. Nonetheless, a similar argument shows that this does not affect the rate at which the confidence bound shrinks, since the confidence interval around Gj. is scaled by an upper bound on the buyer's acceptance compensating for the lower sample size. We defer the formal proof of this lemma to the Appendix.
We now ready present our main result. Theorem 1. Algorithm 2 guarantees regret Ry - ((T%)))
We now present the high-level ideas behind the proof, deferring the formal argument to the Appendix.
To derive regret guarantees for our algorithm, we analyze separately the two phases it executes. The exploration phase always incurs regret of order (TT%)s,, as the exploration strategy is deterministic and runs for (?7"/s rounds. To provide an upper bound on the regret suffered in the second phase of our algorithm, we consider two cases depending on whether l** belongs to K not. If k* K then we can show that P[B 2 p -//)) and, consequently, g(px-) O(T-1/a) Therefore, for any possible set K", the regret suffered by our algorithm is Rr (T
1/a)
Conversely, if 1.* E K i.e., PA- is not removed before the second phase, then, noticing that Kº ~ KC, Lemmas 3 and 4 guarantee that (i) the confidence bounds of each suboptimal arm scale as 1/min(T7/8 e and (ii) all the estimates remain optimistic. By applying a UCB-style analysis and using Lemma we obtain that the cumulative regret in this phase is also of order O(1%))).
5 Conclusions, Limitations, and Future Research
This work introduced new asynchronous protocol for repeated bilateral trade, where the broker interacts with seller only after securing agreement from buyer. Despite the censored nature

---

of the seller's s feedback, we showed that the broker can still achieve the optimal (T regret rate previously known only under the richer two-bit feedback model [Cesa- Bianchi et al., 2024a Combined with the known impossibility of learning under one-bit feedback [Cesa- Bianchi et al. 2024a], this work suggests that our protocol elicits the minimal amount of information necessary to enable optimal learning.
While our theoretical guarantees are optimal, some limitations suggest interesting directions for future research. First, our analysis focuses on stationary environments. Although adversarial bilateral trade known to unlearnable even under full feedback and when competing with the best fixed price in hindsight [Cesa- Aasa-Bianchi et al. 2024a], it would be valuable to explore intermediate settings lying in between the i.i.d. and fully adversarial dynamics, perhaps by relaxing the notion of learnability to allow for (dynamic) Q-regret. Another limitation of our work is the absence of contextual information that the broker might observe before posting price. Extending the framework to contextual settings-where the broker might have access to side information encoding item characteristics, market conditions, or user profiles- remains a challenging and interesting open problem in our censored framework. Finally, following recent works [Bachoc al. 2024 Cesari and Colomboni 2025]. an intriguing direction for future research is to study alternative objectives, such as fair gain from trade or trading volume, which reflect different priorities for the broker.
Acknowledgments and Disclosure of Funding
FB, MC, RC. and AM are partially supported by the FAIR (Future Artificial Intelligence Research) project, funded by the NextGenerationFUU program within the PNRR-PE-A- scheme (M4C2, In- vestment 1.3, Line on Artificial Intelligence) and by the EU Horizon project ELIAS (European Lighthouse of AI for Sustainability, No. 101 101 120237). RC is partially supported by the MIUR PRIN grant 2022EKNE5K (Learning in Markets and Society). AM is partially supported by the Italian MIUR PRIN 2022 project "Targeted Learning Dynamies: Computing Efficient and Fair Equilibria through No-Regret Algorithms".
References
Thomas Archbold, Bart de Keijzer, and Carmine Ventre. Non-obvious manipulability for single- parameter agents and bilateral trade. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pages 2107-2115, 2023.
Yossi Azar, Amos Fiat, and Federico Fusco. An a-regret analysis of adversarial bilateral trade. Advances in Neural Information Processing Systems, 15:1685- 2022.
Moshe Babaioff, Kira Goldner, and Yannai A Gonezarowski. Bulow Bulow-klemperer kwekkkeer-mstttbbeee results for welfare maximization in two-sided markets. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2452-2471. SIAM, 2020.
Moshe Babaioff, Amitai Frey, and Noam Nisan. Learning to maximize gains from trade in small markets. In Proceedings of the 25th ACM Conference on Economics and Computation, pages 195-195, 2024.
François Bachoe, Nicold Cesa-Bianchi, Tom Cesari, and Roberto Colomboni. Fair online bilateral trade. Advances in Neural Information Processing Systems, 37:37241-37263, 2024.
François Bachoc, Tommaso Cesari, and Roberto Colomboni. A contextual online learning theory of brokerage. In Forty-second International Conference Machine Learning, 2025a.
François Bachoc, Tommaso Cesari, and Roberto Colomboni. A tight regret analysis of por-maraettric repeated contextual brokerage. In The 28th International Conference on Artificial Intelligence and Staristics, 2025b.
Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Federico Fusco. No-regret learning in bilateral trade via global budget balance. Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 247-258, 2024.
10

---

Liad Blumrosen and Yehonatan Mizrahi. Approximating thins--rom-tree in bilateral trading. In Web and Internet Economies: 12th International Conference, WINE 2016, Montreal, Canada, December 11-14, 2016, Proceedings 12, pages 400-413. Springer, 2016.
Natasa Bolić, Tommaso Cesari, and Roberto Colomboni. An online learning theory of brokerage. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, page 216 216-224, 2024. ISBN 9798400704864.
Natasa Bolić, Tommaso Cesari, Roberto Colomboni, and Christian Paravalos. Online learning in the repeated mediated newsvendor problem. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025.
Johannes Brustle, Yang Cai, Fa Wu, and Mingfei Zhao. Approximating gains from trade in two-sided markets via simple mechanisms. In Proceedings of the 2017 ACM Conference on Economics and Computtation, pages 589-590, 2017.
Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge University Press, USA, 2006.
Nicolò Desa-Bianchi, Tommaso R Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. regret analysis of bilateral trade. Proceedings of the 22nd ACM Conference on Economics and Computation, pages 289-309, 2021. 2021.
Nicolò Cesa-Bianche Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Bilateral trade: A regret minimization perspective. Mathematics of Operations Research, 49(1): 171-203, 2024a.
Nicolò Cesa- Bisa-Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Regret analysis of bilateral trade with a smoothed adversary. Journal of Machine Learning Research, 25(234):1-36, 2024b.
Tommaso Cesari and Roberto Colomboni. An online learning theory of trading-volune maximization. In The Thirteenth International Conference on Learning Representations, 2025.
Houshuang Chen, Yaonan Jin, Pinyan Lu, and Chihao Zhang. Tight regret bounds for fixed-price bilateral trade. arXiv preprint arXiv:2504.04349, 2025.
Riccardo Colini Baidi-,,,deechh, Bart de Keijzer, Stefano Leonardi, and Stefano Turchetta. Approximately efficient double auctions with strong budget balance. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms,, pages 1424 1443. SIAM, 2016.
Riccardo Dolini-Baldeschi. Paul Goldberg, Bart de Keijzer, Stefano Leonardi, and Stefano Turchetta. Fixed price approximability of the optimal gain from trade. In Web and Internet Economics: 13th International Conference, WINE 2017, Bangalore, India, December 17-20, 2017, Proceedings 13, pages 146-160. Springer, 2017.
Riccardo Colini-Baldesee Paul W Goldberg, Bart de Keijzer, Stefano Leonardi, Tim Roughgar- den, and Stefano Turchetta. Approximately efficient two-sided combinatorial auctions. ACM Transactions Economics and Computation (TEAC), 8(1):1-29, 2020.
Yuan Deng, Jieming Mao, Balasubramanian Sivan, and Kangning Wang. Approximately efficient bilateral trade. In Proceedings of the 54th Annual ACM SIGACT Symposium Theory of Computing, pages 718-721, 2022.
Paul Dütting, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenhäüserr Efficient two-sided markets with limited information. Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pages 1452-1465, 2021.
Solenne Gaucher, Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Vianney Perchet. Feature-based online bilateral trade. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net, 2025. URL https
//openreview.nete net/ wttp://wwww..ttt..oooooooooo//or

---

Zi Yang Kang and Jan Vondrák. Fixed-price approximations to optimal efficiency in bilateral trade. Available SSRN 3460336, 2019.
Anna Lunghi, Matteo Castiglioni, and Alberto Marchesi. Online two-sided markets: Many buyers enhance learning. arXiv preprint arXiv:2503.01529 2025.
Anna Lunghi, Matteo Castiglioni, and Alberto Marchesi. Better regret rates in bilateral trade via sublinear budget violation. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms,, 2026.
Roger B Myerson and Mark A Satterthwaite. Efficient mechanisms for bilateral trading. Journal of economic theory, 29(2)2655-281, 1983.
William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance 16(1):8-37, 1961.
12

---

Omitted Proofs
In order to prove Lemma 2 need introduce some auxiliary useful lemmas.
Lemma 5. It holds P[E1] 2 6.
Proof. Let s 2 H be an integer, and let l E K. By the Chernoff bound and the fact that the variables are all i..dd, we have:
T BBRi 2 pa] S -2222222 ?PIB 2 pk)
P
S
u 2 lox (KT
177)
Slou (KT*)) /6)
KT2
T 31/pp
slog (K (8)
KT2
KT
I 2 HK, then The 2 H according to the definition of Ta and how our algorithm works. It follows that
UÚ
Th= 2 pel }
P
Oki S
2
t=HK
UUUK
TheT 2 pk) n (Tr, =s]
2hT S
2
Li=H t=HKeK
T
Tea Tstp|B 2 mel
Σ ΣP
QcA S
n (Tr.t =s]
2
= HK KEK
T Σ EP
T( 2 S 2 2 z pk]
(Th, = 8}
HI=HK REK
Σ ΣΣW
P
IiBR, 2 pk S 2 1 pR]
s= |=HK KEK
88.
Hence,
P
n
n
Chit >
The PI pul 21-8,
2
L= K. KEK
which concludes the proof.
Lemma 6. It holds
Pt
21og(2/8)
Gx
PPS < sjax
21 2K6.
KN
K
MER
Proof. Under the event E,, for all i E [K] such that P 2 p.l 2 8T 1/3 Log(KT? we have:
H 2 2 Tr, H 2 p.] = ク HP B N prl.
since T. = H for every E [K]. according how our algorithm works. This implies that, under the event ε,, the following holds:
No = min H
> min HP|B 2 p.]
HPIB 2 pk] : ni.
iSk
2
2
13

---

As first step, we prove that, conditioned to the event {Nr = = the estimates G2 concentrate around their expectation. Specifically, whenever é 2 Rg. the following holds:
P
C - |[GH|| - V
log (2/0) Kl
{Nv = e3 21-
(4)
Indeed, by Hauma-Hoeffliee inequality, we have:
k US SP:
P
PIS < pil
S 2K 2KElog(2/0)
21-8.
;=1==1
Furthermore, noticing that
i
G - -B(GR]]
1
Σ T(S S SPi}
ΣΣ ;=15=1
PIS S spil
K
and that {.V& f} E is P-independent from S1, S2..... we have:
p GR B[Gul s
2log(2/0)
[[V== 83 N
P
Gr 11GG
S
2 2log(2/0)
KE
KE
2 1 - 6
showing that Equation 4 Tholds. Therefore, we can prove that:
2l0g(2/5)
P
Gk - B[Ga] $
&1
KN
H
| - EIGH|| -
2 2log(2/0)
2
Σ
P
(N+ = n&
[NN = e [1]
KL
2=0,
H1
2
Σ
(1- (1-5)P( (1
(1
8=
E2
where the first inequality holds because of the law of total probability, noticing that P[N -| O for all l < nn, while the second inequality by eq.
(4). Thanks to the i.i.d. hypothesis we have:
E[G1]
1"H
Ph PJS dAA
k
N
HSis S <pi)
Ph P(S < Ajda
KN
j=1
k
- -/
PD
P(S & pi]
PlS < Njd
K
i - PISS da 1+=(+);
P
K
Now, due to the fact that À + P(S < X]
a non-decreasing function, have that
i
s (+)
S
<
s K
dA
K
- 11 (1)
P(S & Pk] - P(S < 0
PP
S < K
-
PP
s
<
K
K
K
K
14

---

Thus, the following holds:
PIS S 2jd1 S //
Pk
22og(2/8)
P
Gk
&
2
KN₂
Thus, thanks to Lemma
we have:
p
Gk
/0
P[S S xjd2 -
21ox(2/8)
KN
K
Ph P[S - X dd 2
2 2lo((2/0)
1 Pf1
2 P
Gk
+ K
&
KN
2 1 - 28.
Finally, taking union bound over all possible sets of arms K, we prove the lemma.
Lemma 7. It holds
in LEEK
2 1og(2/0))
1 11
P
Pk
rplk PIBZ Ph
PI
+
2
K6
KH
K
Proof. Thanks to the i.i.d. hypothesis and the fact that À + P 2 A] is non-increasing function, with an argument analogous to that provided in the proof of Lemma we have that
E[ [
P(B 2 paas 1 K
By Azuma-Hooffiinn inequality, we have:
ΣΣ I(Bij 2 p.)
EIPBZI pil S 2kH log(2/8) & / /KH 1og(2/6)
with probability Hence, to conclude, it is enough to notice that
k ΣΣ'RE
F E[FA]
IBB,j 2 pp ΣE
KH
j=1
and take union bound over all possible sets of arms [K].
Lemma 8. It holds P[[a]] 2 1- 2KT6.
Proof. Fix &s E K and > HK. Recall that, by definition,
1( S Pk)
P
2x.1
Employing union bound and the Hoeffding incquality, we have that:
1og(2T/5)
log (2)
f
S PIS S pm] Pr. +
2Q
2Qu,t
with probability at least
8. Thus, taking a union bound, we have:
(og(2T/6)
log log(2T (2T 28)
IP
PS pkl S Pi. +
21 KT8.
2Qk
2Qk,t
kE(K]
With an analogous argument, it is possible to show that:
(2g(2T/6)
log log(2T/6) 2Tr.tt
Uk.t
<P Pt. S Un.t +
21 KTS.
2Tx,t
[E[K] t-
Thus, taking a union bound, we have that the lemma holds.
15

---

Lemma 9. It holds P[E,] 2 -
Proof. Let c = 8T 1/3 log( /KT2/8) and i/ := KH If & K, then P[B 2 pal S c. Therefore, we
can employ the multiplicative Chernoff inequality as follows:
Plèx 2 (1 + c) 2 pk]] Se
with FB2Pc Thus, get:
2
HP 2 pkl
FI2 Pk.
2 pk] +d| S exp
+ P[B2 pc)
< exp
EH
2
P 2
8
8/3
S
KT
KT
since x/(x + 2) 2 1/3, for every x 2 a result, we have:
P[Q,.HK - 2Hc] = P[ s 2 2 P(
S P pal + c 2 1
KT2
recalling that bR.HK = Hx. Furthermore, we notice that:
[3/ 2He S 1611666114 (og(kTT//0 16 T
log( (KT///) S 32 log(ko* KT /6²²/))
Thus, by taking a union bound, we have:
P
n
(Q.HKK S (22og((T)//))
2
2
T2
Agg
concluding the proof.
Lemma 2. Let = & E & E.. Then, we have:
P E 2 1 O(KT5).
Proof. Thanks to Lemmas
5
8 and by taking a union bound we have:
P [ 2
(5KT + 2) 1 O(T6)),
concluding the proof.
Lemma 3. Let k E K. Then, for each
HK, conditional on the event E, have:
log(2T/0)
( p
2 2lo((2/0)
1 -PISS
05 iun.
S pM]
P[B 2 Ypla S m
2Q
HK
K
PM
where 7) == C'log (7)
and C > 0 is absolute constant.
T
Tuu
Proof. We first prove that:
1og(2T/6) 2Q
log((2 2/0)
(ia. +
Fr +
HK
K
is the (optimistic) estimator of
PP.S < pk]
P(B > d)
Pk.
16

---

To do so, we observe that under the event E, we have:
log(2T/8)
2 22gg(2
1
Aiiee +
Fk +
+
-PSS & pk]
PIB 2 A/dA
2
HK
K
(2gg(2T)))
(log(2/6)
2
P(S S p&l +
PIB = Na +
+
QKTt
HK
K
-P[S S pkl
PIB AjdX
Pe
log log (2T
8log(2/6)
(lg(22//0)
PPB 2 Aj + P(S & puly
Qkat
HK
VHKQK
2 K
2 log(2TT0)
P[S S pa]
Qhee
2 2log (2T//))
20 loloo((1) (2T//
PIB pk]
Qx,t
T
(4)
Now, notice that, since h I. by assumption, have Qk. TR, [B2 2 pk] for all HK, under the event E. Therefore, the following holds:
2 1og((T/5)) P 2 pkl S
41og(27/0) Tr,IP B 2 pk]
P(B 2 p&l <2 1og(2T/1
Qk.t
VTu,
Putting all together, we have:
jun, +
log(2T/0)
f +
2 (2g((26))
+
1
PiS S pn]]
P[B 2 Ajda
2Qkt
HK
K
log
Thut
T1/3
Finally, notice that:
(pn.t +
log log(2T/6) 2QR
2 llg
P|S < pa] as direct consequence of being under the clean event This concludes the proof.
PIB Aalr
Pr +
HK
K
Lemma 4. Let K. Then, for each t. HK, conditional the event E, have:
1og(2T/6)
2 log((//8)
- PPB Pm] /
Ph PPS < AA S
0 Dn.t +
Gk +
+
2Tk.t
KNz
K
(2ta
where 17 = Colog (4)
T
and C > 0 is an absolute constant.
TE.
Proof.
Notice that the first inequality is trivially given by the fact that, under the event E, the quantity
log(2T(6)
(2/6)
Dz, +
G +
+
2TR,1
KN
K
is an (optimistic) estimator of
Pt PiS < Ajd.
P 2 pt]
17

---

For the second inequality, we notice that, under the event E:
log(2T/6)
(20)(2/))
P 2 Ptl /
DE
ik,0 +
Gk +
+
PIS S Aj
27k,
KN
K
ECBnNEs
2 2
PN
8log(2/8) KNr
PIB 2 pkl +
PIS - dxp
The
K
PK
P(B 2 ph]
PIS AAdA
ECε
2 (og(2T/6)
PE
log(2/0)
PIS S AjdV + 4PB 2 paly
Tk,t
KHPPB Pk.
4v2 (2T//8)2)))
2
2 2log(21/0)
V KHPIB 2 pk. Tr.t +
P(B pa]
K
Te.t
kEK
1
log
0
+
8
TK,t
T
concluding the proof.
Theorem 1. Algorithm guarantees regret Rr = Ö(T4)).
Proof. We first notice that, by defining
T
R7 = Σ g(p") Σ g(P.),
1=1
have that R = [[ and
Rr [
< + < + 6 033
is then sufficient to control the magnitude of Rr under the clean event E. Hence, from this point under the clean event E.
on, assume
Let k* E arg max g(P)).
First, notice that, if Plpk S B] S 647 1/3 log (KT2/))) then
g(p=-) = BBB S) pk- < B E P H = P[B pn-] < 1/3 log( (T /8),
where we used (B- 5) < 1 and (S < p < B} C [B 2 p}. Thus, when P(pe- < B <
6/3-1/3 log( ( we have, due to Lemma that if we pay an additional term whose instanta- neous regret is upper bounded by L,K, we can control Rr by comparing our performance against the performance of the best point in the grid pk=, from which
TL
Rr = GCT 1/3 + = Ō(T2/3).
K
Hence, we are left to analyze what happens when P(pp < B] > 64T 1/3 log KT2 which we assume being the case from this point on. First, since P(ps- S B} > 64T 1/3 ( /8), given that & C E, it follows that A* E K
We now notice that for each In the clean event E, we have that & holds, and hence for each h & K. we have that Qr. S 327 log 2 /8). It follows that, in the clean event E, k E Kº implies k K, i.e. K K.
K we have that QK.HK > 327 log(KT2 by definition.
18

---

Now, we recall that Lemma 3 and Lemma Sa iimply that, under the event &, for all t 2 HK + 1 and k K:
g(px) I UCB S g(pk) 1
(5)
where I1,t-1 == C'oog
and C 0 is universal constant. (We use UCB because Pt chosen at the start of round based only on information up to time 1-)
Ti/a
If, for every E [0, 1]. we define the quantity Ap == x(px-) - g(p), then, for each / 2 HK + 1, if
ke Kº such that P. Pk, by eq. 5 we have
g(pk-)
max g(pa) max AEK
UCBR,1-1 U- + 1
REK
and hence
P
S M
In addition, by Lemma and the fact that the instantaneous regret is upper bounded by 1, we have:
LT
T
Rr S HK
+
+
Σ
AP.
K
t=HK+1
Now, we have
Σ
Σ
P
keK*
Σ
Mht 1PP- pn}
kg {=HK+1
T
Č log 1)
1[P:=pa)
by the definition of k,t-1
8)
T1/3
VTr.-1
kE t= HK+1
T Ò logl
Σ
I[ = pk + Σ Σ
KP =
T1/3
VT,,-11
keK t=Hk+1
keK* H
T Σ
T(P: = px}
< Ö log
1+
Σ
T1/3
TK,-11
I=
kEK t=
[[P pk]
Ō log
T2/3
Σ
7
(TA--
kEK
t=IK+1
I(P: = P&)
E0log
T2/3
Σ
Σ
TR.I-1
BEK*(=HK- HK-
I 12/TT.
Th. by (a)
< < EClog log
2/1 + 2 Σ
VTT
kEK
Ō log 8
T2/3 2
KKo
Σ TR. ke
(b)
s δ log 7
2/23 + 2/KT]
2)72
19

---

where (a) and (b) can be proved as follows
T
T
(a)
Σ
where me =
Σ
T(p: pp)= H [T133]
VTR
v
H
(i-1)
t
H+mg-
H+
Σ
vj S
dr 2(V
+ mm mi -
V
HH-1
-=H
s m/m I /TTT..
T TeT S
(b) EVTEr
TE,T S
|K9 E
TE. S VKT,
since
ETE
3 Σ [(p:pk =
kEK
KEK
kEK
t=1
Hence
T T2/3 Ō(T2/8)
B S E' E' log
concluding the proof.
Experimental Results
In this section, we present some experimental results obtained on seaheticaally-gneraaie instances. Specifically, we consider instances where the seller's valuations are sampled from Beta distribution with parameters a, and S., while the buyer's valuations are sampled from Beta distribution with parameters Or, and (gg- For each instance, we evaluate the performance of our algorithm and the Scouting Bandits al algorithm Cesa-Bianchi et al. [2021] in terms of cumulative regret. To this end, we run both algorithms on each instance n. 5 times and report the mean and standard deviation of the achieved cumulative regret.
Table I: Comparison between our algorithm and the one of (Cesa-Bianchi et al. [021 in terms of cumulative regret across different instances where buyers and sellers' valuations distributed according to Beta distributions.
Parameter
Instance
Instance 2
Instance
Time horizon (?')
10000
50000
10000
(Ots, (4)
(5.0, 10.0)
(5.0, 10.0)
(10.0, 10.0)
(0b, (6)
(15.0, 10.0)
(15.0, 10.0)
(15.0, 10.0)
Regret + std (ours) Regret + std (Csa-Biianhii et al. (2021)
199.6 + 17.1
714.4 + 73.1
135.2 + 22.1
732.0 + 21.4
2253.8 75.2
548.8 16.4
Table 2: Comparison between algorithm and the of Cesa-Binchii al. 2021 in terms of cumulative regret across different instances where buyers and sellers' valuations are distributed according to Beta distributions.
Parameter
Instance
Instance 5
Instance 6
Time horizon (1") (a,, B.)
50000
10000
50000
(10.0, 10.0)
(2.0, 3.0)
(2.0, 3.0)
(as, (6)
(15.0, 10.0)
(10.0, 10.0)
(10.0, 10.0)
Regret + std (ours) Regret + std (Cesa-Bianchi et al. (222
326.5 + 84.0
168.5 +: 28.8
439.2 136.2
2381.0 + 98.1
583.5 + 27.6
2502.4 + 52.2
We observe that the regret incurred by our algorithm lower than that of Cesa-Bianhhi et al. 2021 While this may appear counterintuitive (since we use less feedback than the Scouting Bandits algorithm of Cesa-Biachii et al. (202T), the improvement stems from a key difference. Indeed, after the initial exploration phase, we eliminate arms that are guaranteed to be suboptimal. This pruning
20

---

step, absent in Scouting Bandits, allows us to restrict the subsequent bandit phase to the reduced set K which can be significantly smaller than the original set of arms. contrast, "Ceaa-Biande et al.) 2021 run their algorithm over the full set, whose size 7
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, we state the main theorem of the paper in the abstractiintroduction..
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Discussed section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
22

---

Justification:
All our results have a complete proof in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: the paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
23

---

Answer: [NA]
Justification:
The paper does not include data or code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppi.ccppulli//uuuii wwwiiccgguie///eeeeeeeeis CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
24

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The paper conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed, since the work is mainly theoretical.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
25

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
26

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
27

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The paper does not involve LLMs as any important, original, non-standard components.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
28


Reviews:
[{"review_id": "jDFYHbLomJ", "reviewer": "Reviewer_WMxL", "summary": "This paper studies the online bilateral trading problem, where a market maker (“broker”) aims at facilitating trades between pairs of buyers and sellers (drawn i.i.d.) arriving over time $t=1,2,\\ldots, T$ with a price $p_t$ in the middle. The performance is measured by regret on the gain from trade against the best fixed price in hindsight. The authors introduced an asynchronous feedback protocol, where the broker always observes the buyer’s willing-to-trade $1[p_t\\leq B_t]$ but only observes a  feedback from the seller’s side $1[S_t\\leq p_t]$ if the buyer has accepted the price, thus formulating a 1.5-bit-feedback censored feedback model. In this paper, the authors propose an algorithm that achieves $\\tilde{O}(T^{2/3})$ regret, which is near-optimal even for the two-bit feedback problem setting. The algorithm applies a pure-exploration-then-UCB strategy.", "questions": "### Questions:\n\nPlease see “weakness” above. Also, what is the computational complexity of the algorithm, particularly the $K$-dependence as you adopt the grid-based approach?\n\n### Suggestions:\n\nSome typos to fix: e.g. Line 138 (the equation): “sellers’s”.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strength:\n\nThis problem is novel and well-motivated as it is only necessary to ask the seller’s side when the buyer has approved the trading. The 1.5-bit feedback model (as sometimes 1 and sometimes 2) is more difficult than the previous two-bit feedback model, and it is non-trivial to achieve the same regret rate. Regarding the identical regret rate (in big O notation), it also justifies that the 1.5-bit model is not losing too much information from the two-bit model, which aligns with many existing literatures on pricing and trading with censored feedback. Besides, the algorithmic analysis is rigorous and sound, with assumptions, theorems and lemmas clearly stated. The paper is overall well written.\n\n### Weakness:\n\nI 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. The reason is simple as I would like to know whether the feedback censoring effect on the seller’s side is harming the reward or affecting the regret in practice (although the regret rate is the same in big O notation). There are two possible results as I expect: (1) The cumulative reward of proposed algorithm decreases faster than the baseline oracle, leading to a larger regret on the 1.5-bit problem than the original two-bit problem. This means that the algorithm suffers more than the baseline oracle from the censoring effect. (2) The regret is even smaller than the two-bit case, indicating that the baseline oracle suffers more than the algorithm (or the player in general). While (1) could be more reasonable, I wonder if (2) indeed happens, then it might still not be a “Waste of Seller’s Time” to ask both sides simultaneously. Do you agree with that?\n\nBesides, 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.", "was_revised": true, "final_justification": "The rebuttal resolves my concerns and I lift my grading.", "rebuttal": "**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. \"**\n\nIn 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.\n\n| Parameter                                        | Instance 1              | Instance 2               | Instance 3                          | Instance 4                          | Instance 5                          | Instance 6                          |\n|--------------------------------------------------|--------------------------|---------------------------|--------------------------------------|--------------------------------------|--------------------------------------|--------------------------------------|\n| Time horizon                                     | 10000                   | 50000                    | 10000                               | 50000                               | 10000                               | 50000                               |\n| ($\\alpha_s$, $\\beta_s$)                          | (5.0, 10.0)              | (5.0, 10.0)               | (10.0, 10.0)                         | (10.0, 10.0)                         | (2.0, 3.0)                           | (2.0, 3.0)                           |\n| ($\\alpha_b$, $\\beta_b$)                          | (15.0, 10.0)             | (15.0, 10.0)              | (15.0, 10.0)                         | (15.0, 10.0)                         | (10.0, 10.0)                         | (10.0, 10.0)                         |\n| **Cumulative Regret ± std (ours, 1.5 feedback)** | $199.56 \\pm 17.14$       | $714.44 \\pm 73.07$        | $135.21 \\pm 22.12$                   | $326.51 \\pm 83.98$                   | $168.53 \\pm 28.78$                   | $439.17 \\pm 136.17$                 |\n| Cumulative Regret ± std (2-bit feedback)         | $732.00 \\pm 21.41$       | $2253.76 \\pm 75.22$       | $548.83 \\pm 16.35$                   | $2380.95 \\pm 98.14$                  | $583.48 \\pm 27.58$                   | $2502.37 \\pm 52.19$                 |\n\nWe 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}$.\n\n**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.\"**\n\nFrom 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.\n\nFrom 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..\n\nAgain, 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.\n\nWe will add this discussion about the implications of our assumptions in the revised version.\n\n\n**Re: \"What is the computational complexity of the algorithm, particularly the dependence as you adopt the grid-based approach?\"**\n\nThe 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.\n\n\n\nNicolò 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."}, {"review_id": "E0cNbLecRn", "reviewer": "Reviewer_KuvA", "summary": "The paper studies the problem of online bilateral trading in an asynchronous setting. There are three agents involved; the seller, the buyer and the broker. At each round $t$, the broker sets a price $p_t$ and the trade occurs if $S_t<p_t<B_t$. The problem has been studied under different feedback models, namely the full feedback, where the broker observes both buyer’s and seller’s valuation, the 2-bit model where the broker observes separately the boolean random variable $X_1 = p<B$ and $X_2= p>S$ and the 1-bit model where the broker only observes the ternary boolean $X = S<p<B$. They consider an asynchronous model in between 1-bit and 2-bit, where the broker only observes the boolean $X_2= p>S$ if the buyer first accepts the price $p_t$.\nThe authors give an online learning algorithm that operates over a uniform grid of size $K=\\lceil T^{1/3} \\rceil $.They prove that their online bilateral trading algorithm in the latter feedback setting that achieves regret of $O(T^{2/3})$.", "questions": "Have you considered studying information-accuracy tradeoffs such as:\n- How much mutual information about the optimal price does each feedback bit supply ?\n- What regret rates are achievable if you deliberately limit feedback to, say, one bit every other round, or to noisy bits?\n- How much “value” does each bit contribute toward narrowing down the optimal price?\n\nFraming the problem in an information-theoretic bandit lens, that is, bounding regret in terms of cumulative mutual information between observations and the optimal actio, would let you precisely quantify when and why extra seller signals cease to help.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n- The paper is well written and well organized.\n- The idea of exploring a feedback model between 1-bit and 2-bits is novel in such a setting. \n\n### Weaknesses \n- 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.", "was_revised": true, "final_justification": "The authors fully addressed my questions. I remain very positive for the novelty of this paper.", "rebuttal": "**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.\"**\n\nGreat 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:\n\n$f_S(u)= M  \\mathbf{1}_{[0,\\frac{1}{2M}]}(u) + M  \\mathbf{1} _{[x-\\frac{1}{2M}, x]} (u)$,\n\nand the buyer pdf\n\n$f_B(u)=M   \\mathbf{1}_{[1-\\frac{1}{2M}\\,1]}(u) +M \\mathbf{1} _{[x\\,x+\\frac{1}{2M}]}(u)$,\n\nso 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.\nOn 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$,\n\n\n$$|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|$$\n$$\\le\n\\max \\left( (F_B(q) - F_B(p)) \\int_0^q F_S(u) du, (F_S(q) - F_S(p)) \\int_q^1 (1 - F_B(u)) du \\right) + \\max \\left( F_S(p) \\int_p^q (1 - F_B(u)) du, (1 - F_B(p)) \\int_p^q F_S(u) du \\right)\n$$\n$$\n\\le L |q - p|^\\alpha + |q - p| \\le (L + 1) |q - p|^\\alpha.\n$$\n\n\nwhere 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.\nWhether these rates are minimax‑optimal under Hölder cdfs is an interesting open question we leave for future work.\n\n\n\n\n**\"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?\"**\n\nVery 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."}, {"review_id": "v4KV8ppfRy", "reviewer": "Reviewer_VQjt", "summary": "The authors propose an asynchronous protocol for the online bilateral trade problem, designed to be more efficient by not wasting a seller's time. The proposed asynchronous mechanism queries the buyer and only approaches the seller if the buyer agrees to the price. The main contribution is an algorithm for this new setting that achieves a regret that matches the known lower bound.", "questions": "See weakness.", "limitations": "Yes.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength:\n1. The paper's primary strength is the introduction of the \"Don't Waste Seller's Time\" asynchronous protocol. This is a more efficient model.\n\n2. The analysis presents a technical contribution in handling the \"censored\" seller feedback. The authors overcome the challenge of having potentially fewer samples for the seller's valuation by showing that when this occurs, the buyer's acceptance probability is also low. \n\nWeakness:\n1. 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.\n\n2. 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.\n\n3. 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.", "was_revised": true, "final_justification": "After reading the response, my comment and scores remain the same.", "rebuttal": "**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. \"**\n\nWe 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.\n\n**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.\"**\n\nWe 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.\n\n\n**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.\"**\n\nIn 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.\n\n| Parameter                                        | Instance 1              | Instance 2               | Instance 3                          | Instance 4                          | Instance 5                          | Instance 6                          |\n|--------------------------------------------------|--------------------------|---------------------------|--------------------------------------|--------------------------------------|--------------------------------------|--------------------------------------|\n| Time horizon                                     | 10000                   | 50000                    | 10000                               | 50000                               | 10000                               | 50000                               |\n| ($\\alpha_s$, $\\beta_s$)                          | (5.0, 10.0)              | (5.0, 10.0)               | (10.0, 10.0)                         | (10.0, 10.0)                         | (2.0, 3.0)                           | (2.0, 3.0)                           |\n| ($\\alpha_b$, $\\beta_b$)                          | (15.0, 10.0)             | (15.0, 10.0)              | (15.0, 10.0)                         | (15.0, 10.0)                         | (10.0, 10.0)                         | (10.0, 10.0)                         |\n| **Cumulative Regret ± std (ours, 1.5 feedback)** | $199.56 \\pm 17.14$       | $714.44 \\pm 73.07$        | $135.21 \\pm 22.12$                   | $326.51 \\pm 83.98$                   | $168.53 \\pm 28.78$                   | $439.17 \\pm 136.17$                 |\n| Cumulative Regret ± std (2-bit feedback)         | $732.00 \\pm 21.41$       | $2253.76 \\pm 75.22$       | $548.83 \\pm 16.35$                   | $2380.95 \\pm 98.14$                  | $583.48 \\pm 27.58$                   | $2502.37 \\pm 52.19$                 |\n\nWe 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}$."}, {"review_id": "0t1RowYQbV", "reviewer": "Reviewer_vJmF", "summary": "Bilateral trading refers to the situation in which a buyer and a seller wish to trade an asset through an intermediary. The goal of the intermediary is to post a price that maximizes gains from trade (or, equivalently, total welfare). In an online learning setting, the price is chosen dynamically based on the feedback received by the intermediary at the end of each trading round. In the one-bit model, the intermediary only observes whether the trade has occurred or not. However, it is known that this is insufficient for learning optimal price-setting strategies. In the two-bit model, the intermediary simultaneously observes whether the buyer and the seller are willing to trade. In this case, it is known that the bound on the regret is O(T^{2/3}). The contribution of this paper is to show that the same bound can be achieved under weaker feedback (3/2-bit, roughly speaking). The paper presents an algorithm where the seller is queried only after the buyer accepts the trade, effectively minimizing the amount of information that the intermediary has to collect from the seller while still achieving an optimal regret rate.", "questions": "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 (i.e., query the buyer only after the seller accepts the trade). In this case, I recommend briefly mentioning it somewhere in the paper, dropping \"Don't Waste Seller's Time\" from the title, and keeping only \"Online Bilateral Trade With Minimal Feedback\" for clarity.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The problem formulation is precise. The paper is well-written, and it has been a pleasure to read. Although the work is strongly based Cesa-Bianchi et al. [2024a] and incremental, the extension to asynchronous interaction is new to the best of my knowledge. The result of achieving an optimal regret rate with minimal feedback is strong.", "was_revised": true, "final_justification": "The authors confirmed that the roles of sellers and buyers are interchangeable, which adds value to the proposed framework. Moreover, the authors provided numerical experiments that furhter strenghten their work. The only reason why I maintain my original evaluation of 5, instead of increasing to 6, is that I see the contribution focused on a specific sub-area instead of one or more areas of AI.", "rebuttal": "**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 ...\"**\n\nWe agree with the reviewer, the roles of sellers and buyers are interchangeable, we will specify this better."}]

Author rebuttal:

Meta-review: Reviewers are positive about paper's writing and like the results. However, there are concerns on paper's technical contributions and practical relevance. Overall, the paper is slightly above borderline. 

I share reviewers' concerns. And here are some of my suggestions for improving practical relevance (not required for a theory-focused paper, but good to have):
1) Offer extra evidence that the online bilateral trade algorithms with more or less feedback are used in any practical scenarios, and how sellers react to them. It's impossible to judge if "Don’t Waste Seller’s Time" is an important/relevant issue to solve to start with, from a practical perspective. 
2) It would be helpful to have the numerical simulation in rebuttal together with more baselines, including strategies that care less about asymptotic performance but more on performance with reasonable size inputs.
Decision: Accept (poster)