Nonparametric Contextual Online Bilateral Trade
Authors: Emanuele Coccia
Martino Bernasconi
Andrea Celli
Venue: ICLR 2026 Poster (2026)
Keywords: bilateral trade
online learning
contextual bandits
Primary area: learning theory

Abstract: We study the problem of contextual online bilateral trade. At each round, the learner faces a seller-buyer pair and must propose a trade price without observing their private valuations for the item being sold. The goal of the learner is to post prices to facilitate trades between the two parties. Before posting a price, the learner observes a $d$-dimensional context vector that influences the agent's valuations. Prior work in the contextual setting has focused on linear valuation models, where valuations are linear functions of the context. We provide the first characterisation of a general nonparametric setting in which the buyer’s and seller’s valuations behave according to arbitrary Lipschitz functions of the context. We design an algorithm that leverages contextual information through a hierarchical tree construction and guarantees regret $\widetilde{O}(T^{(d-1)/d})$. Remarkably, our algorithm operates under two stringent features of the setting: (1) one-bit feedback, where the learner only observes whether a trade occurred or not, and (2) strong budget balance, where the learner cannot subsidize or profit from the market participants. We further provide a matching lower bound in the full-feedback setting, demonstrating the tightness of our regret bound.

Published as a conference paper at ICLR 2026
NONPARAMETRIC CONTEXTUAL ONLINE BILATERAL TRADE
Emanuele Coccia, Martino Bernasconi' & Andrea Celli Department of Computing Sciences Bocconi University
Milan, Italy
emanuele wocciaa@ttuuoooooooooooooooooooo .tt, fmartine .bernasconi, andrea. wocllellceeeeccccccccc
ABSTRACT
We study the problem of contextual online bilateral trade. At each round, the learner faces seller-buyer pair and must propose trade price without observ- ing their private valuations for the item being sold. The goal of the learner is to post prices to facilitate trades between the two parties. Before posting a price, the learner observes a d-dimensional context vector that influences the agent's valu- ations. Prior work in the contextual setting has focused on linear models. In this work, tackle general nonparametric setting in which the buyer's and seller's s valuations behave according to arbitrary Lipschitz. functions of the context. We design an algorithm that leverages contextual information through hierarchical tree construction and guarantees regret ( Remarkably, our algorithm operates under two stringent features of the setting: (1) one-bit feedback, where the learner only observes whether a trade occurred or not, and (2) strong budget balance, where the learner cannot subsidize or profit from the market participants. We further provide a matching lower bound in the full-feedback setting, demon- strating the tightness of our regret bound.
INTRODUCTION
Bilateral trade is a fundamental economic model which describes the interaction between a seller and buyer, each with private valuations for good, who seek engage in trade with the goal of maximizing their individual utilities (Vickrey, 1961; Myerson & Satterthwaite, 1983). This scenario arises in many applications such as ridesharing platforms or energy and financial exchanges.
Recently, Desa-Bianchi et al. (2024) introduced the online bilateral trade problem, in which at each round new seller and buyer arrive with private valuations s; and 6, respectively. The valuation of the seller 8, is the lowest price they are willing to sell the item. Analogously, the valuation of the buyer, be, is the highest price the buyer willing to pay for the item. At each round t, the learner must propose a price to both the buyer and the seller without observing their private valuations. After posting price pt, trade happens if 8t S Pc. S b.. The from trade at time is
GFT b.) I(s S Pt S be)(bb- st),
and represents the total increase in social welfare generated by the trade. The goal of the learner is to maximize the cumulative gain from trade over time, which is equivalent to minimizing the regret with respect to the best policy in hindsight.
In many practical scenarios, the learner has access to side information at each round about the seller, buyer, or the item being traded. For instance, this is common in online marketplaces, where items are highly differeeniatedd and the learner can observe certain features of the item prior to setting a price. Such contextual information can be leveraged estimate the relevance of different features based on historical data. Gaucher et al. (2025) introduced the feature-based online bilateral trade problem, in which the learner observes a d-dimensional feature vector D, before posting a price at
"Corresponding author.

---

Published as a conference paper at ICLR 2026
round t. They study linear model where private valuations are linear functions of the form a. 0 for some unknown parameter vector 8. In this work, we study whether it is possible to move beyond the linear valuation model. A similar question examined in the context of pricing in Mao et al. (2018).
We provide comprehensive characterization of the problem when valuations are arbitrary L- Lipschitz functions of the context vectors. A key feature of our analysis is that it operates under the one-bit feedback model: each round, the learner observes only the signal I[s, S Pt S b,), indicating whether a trade occurred or not. This is the most bilateral trade, and existing contextual no-regret algorithms can handle this feedback model only by relaxing the budget balance constraint (Gaucher et al., 2025).
setting in online
1.1 TECHNICAL CHALLENGES AND TECHNIQUES
Compared to classic online learning problems, the bilateral- trade setting presents additional techni- cal difficulties, making traditional approaches for nonparametric contextual online learning largely inapplicable. The most notable is that the reward function, which is the gain from trade (Equa- tion (1)), is non-continuous both as a function of p or as function of the valuations and b. The second challenge, and possibly more fundamental one, is the lack of observability of the reward we are trying to maximize; indeed, valuations s and 6 remain hidden, whether the trade happens or not, and so does the GFT. The only feedback received by the algorithm is the indicator of [[(s S p p b), which only signals whether the trade was accepted or not.
Although our problem has features that separate it from classic online learning, we do not need to consider a generic Lipschitz loss function, and we will heavily exploit the structure of the reward p - GFT(p|s, 9, b) and the Lipschitzness of the functions generating 8, b from the contexts. The specific shape of the GFT function (and the absence of noise) is what ultimately allows us break the lower bound of ((T((4+2)((++3) (from Lu et al., 2009; Slivkins, 2014, with p = 1) that we would obtain if our reward function were a generic Lipschitz function (see Section 1.2 for more details).
Similar to the aduptive zooming technique employed by Slivkins (2014) or the chaining approach al. (2017), we maintain a discretized representation of the context space, which
of Cesa-Biance is geometrically refined in regions in which we observe a lot of contexts. Formally, we use a tree with branching factor 2d, in which each layer l maintains an 0(2 discretization of the function mapping contexts to optimal prices. Moreover, at level L, we "mark" node if we find price that was accepted when observing a context in the region described by that node. By Lipschitzness, we know that there is a region of size O(L2-t) that contains price for all nodes of the sub-tree.
The main challenge then is to effectively utilize this information, as the discontinuity of the reward functions prevents the use of standard techniques. The key trick here is to heavily rely on randomiza- tion when posting prices. By playing uniformly at randomly on an e discretization of the identified set of good prices (that has length O(2 '9) we have a probability of at least (22'e) of winning any trade with GFT at least e, and thus we will waste only 0(2-//e) turns on expectation before finding the children node, On
a price that is accepted, marking the node with that price and continuing the other hand, losing all the trades with GFT smaller than only yields a regret of order O By tuning the parameter c, and summing over all node of the tree this leads to an overall regret of ((T(d-2)/d) which, although being sublinear, is suboptimal.
In order to obtain an optimal rate, the second trick is associated with reducing the regret suffered when guessing the right price and exploits the geometric structure of the problem. Before starting to guess a correct price in the associated interval, we perform sort of "hide-and-seek game" against the adversary generating the contexts. We probe iteratively two prices. If we win the trade, we are happy since we have zero regret. Otherwise, if we miss a trade for both prices, by geometric reasoning, we can limit the space in which the context can place the valuation, and we can show has to be very close (order of O(2-*) to the diagonal. This limits the possible GFT (and thus the regret) by O(2-1) in all subsequent nodes. This modifies the maximum regret experienced in the guessing phase to be D(2-2e/a /c) at nodes layer f, and by appropriately tuning can obtain an optimal regret of ()T(d)1)/d))
Crucially, this algorithm relies on explicit knowledge of the Lipschitz constant L, which may be un- known in a practical scenario. Building on the main structure of the vanilla algorithm, in Section 4,
2

---

Published as a conference paper at ICLR 2026
design an algorithm that works by testing geometrically increasing scales of the Lipschitz con- stant and only slightly worsens the guarantees, without requiring knowing the Lipschitz constant.
For the matching (up to logarithmic terms) lower bound of Q(T((-1)/d), we use a combination of Yao's weak minimax principle (Yao, 1977), which relates the performance of randomized algorithms in the worst instance to the performance of deterministic algorithms against a distribution over in- stances, with simple version of the McShane's s extension theorem (McShane, 1934) that shows the existence of Lipschitz extensions on the continuum of Lipschitz functions on discrete sets.
1.2 FURTHER RELATED WORKS
Bilateral trade In the offline setting, Myerson & Satterthwaite (1983) demonstrated that no mech- anism can simultaneously achieve full efficiency, incentive compatibility, individual rationality, and budget balance in general. This impossibility result motivated a long line of research aimed at designing mechanisms that achieve approximate efficiency in Bayesian settings (McAfee, 2008; Blumrosen & Mizrahi, 2016; Brustle et al., 2017; Deng et al., 2022; Kang et al., 2022).
Online bilateral trade In the online setting, Cesa- Bianchi et al. (2024) study a setting where buyer and seller valuations are i.i.d. from an unknown distribution, and the learner must enforce strong budget balance (i.e., at each round they post the same price to both the seller and the buyer). They provide no-regret algorithms for the full-feedback setting, and under partial feedback when the valuations are drawn independently for the seller and the buyer, and the underlying distribution is smooth. In the case in which valuations are generated by an adversary, Azar et al. (2022) provides an algorithm achieving tight sublinear 2-regret under weak budget balance (i.e., Pt S q, each round t). Moreover, Bernasconi et al. (2024) shows that sublinear regret is still achievable if the learner is allowed enforce global budget balance, meaning the constraint must hold over the entire horizon rather than at each round (see also Chen et al. (2025); Lunghi et al. (2025)). The most closely related work in online bilateral trade is by Gaucher al. (2025), who consider a contextual variant of the problem where valuations at time take the form 2, e, possibly with additive noise. They propose an algorithm achieving ( regret under two-bit feedback and strong budget balance, and show that sublinear regret is also attainable under one-bit feedback if global budget balance is allowed. This linear contextual valuation model builds substantial body of work in contextual pricing with linear valuations (Kleinberg & Leighton, 2003; Amin et al., 2014; Cohen et al., 2020; Lobel al., 2018; Liu et al., 2021).
Other related models A related but structurally different model is that of online brokerage (Bolić al., 2024), which differs from standard bilateral trade in that traders may act as buyers sell- ers depending on market conditions, and their valuations are drawn i.i.d. from a shared unknown distribution. Bachoc al. (2024) consider a contextual brokerage model, in which valuations are modeled as zero-mean perturbations of a market price that is linear in the agent's 's feature vector.
Online nonparametric contextual online learning The study of online learning with nonpara- metric contexts was initiated by Hazan & Megiddo (2007), in which they proved an upper bound of O(7(4+1)((+2) and context dimension d, while providing ((T(d-1)/d) lower bound. The gap was closed in Rakhlin & Sridharan (2015) for full information by providing an upper bound of (dT(d-))/) and later refined in Cesa- Bianchi et al. (2017) by providing an explicit algorithm. Both of these works also consider arbitrary Lipschitz reward function. The model was extended to arbitrary metric action spaces of dimension in Lu et al. (2009) and Slivkins (2014), that show an almost matching rate of (( (rr(dddp+))/ddppp>> ). In economic settings, the problem of nonparametric contextual information has been studied in Cesa-Bianchi et al. (2017), which examines accond-pric- auctions, and Mao et al. (2018); Chen & Gallego (2021); Tullii et al. (2024) for pricing.
Independent and concurrent work Independently, Cosson et al. (2026) considers the contextual bilateral trade model with linear contexts of Gaucher et al. (2025), focusing on the noiseless setting. They study gain from trade and profit maximization (unlike Gaucher et al. (2025) which only study gain from trade) in various feedback settings and budget balance constraints. The linear noiseless contextual setting allows for substantially better rates with respect to what is achievable in our work.
3

---

Published as a conference paper at ICLR 2026
In particular, the rates they obtain most logarithmic in the time horizon and exponential in the dimension, while ours are polynomial with exponent depending on the dimension.
PRELIMINARIES
At the beginning of each round the learner observes public context 2; [0, 1j generated by an oblivious adversary. At the same time, a new pair of buyer and seller arrives, characterized by private valuations (b,, st) E [0, 1]2. The valuations are generated from the context by two unknown functions = fa(z;) and by fxx). We assume, as it is standard in the nonparametric contextual bandits literature (see, e.g., (Slivkins, 2014; Cesa Bianchi al., 2017)), that fu, fo [0. 1] [o. 1]
are L--Lipshitz functions, ie.. fa [x) f=(x') < L||= x' o|o for all x, x' E [0, 1] (and similarly for fo). We denote the class of all L-Lipschitz functions Ft.
Objective After observing the contextual information zt, the learning picks one price E [0, 1]. and the trade accepted if both the seller and the buyer accept it, i.e., 8t S Pt S b, When the trade is accepted, it generates social welfare of b, 8, (that is, the increase in total happiness between the two market participants); in particular, the gain from trade is defined as in Equation (1). The objective is minimize the regret, which given sequence of contexts (Io, 1]9)T and two L-Lipschitz functions fsr fo. defined as
{Z1...., IT)
S6. = - ((GFT((PlfA (c))))))))))))
- fa(=))]
t=1
where the expectation is taken over the randomization of the algorithm. The regret of an algorithm is then defined Rr =e able across all functions far E FL and all context sequences Since guarantees that are asymptotic in T, we will work under the assumption that > 2d. In particular, only guarantee upper bound the regret of 2d
Rf,,,, fb, a:), which is the worst-case regret attain-
interested in regret
if T < 2d,
Feedback Our algorithm operates under partial feedback, specifically under one-bit feedback. In this feedback model, the learner observes only single bit of information indicating whether trade occurred, i.e., I(&, I Pt I by). In contrast, the lower bound is established under full feedback, where the learner observes the valuation pair (st, (s),b) after posting the price pt, irrespective of whether the trade was executed. An intermediate setting is the two-bit feedback model, in which the learner observes both I[(s; S Pt) and I[p: $ b.).
Notation We denote by Ha the d-dimensional Boolean hypercube {0, 1]d and by O₂ d- dimensional vector of zeros. We denote the projection of R onto 1²" as lc((x). Moreover, for a < b, let Jo. b]e denote the uniform grid over the interval [a, b] with step size c, where any grid point outside the interval [0. 1] is projected onto the nearest endpoint, i.e., capped to 0 if below and if above Formally, (a, 6]. == [[ (fa, a + E,..,, a + ke, b)), where k b-e
REGRET GUARANTEES FOR KNOWN LIPSCHITZ CONSTANT
In this section, we present an algorithm that guarantees regret of order ((IT(d-1)/d) in the case in which the Lipschitz parameter I, is known. In Section we extend this approach to include the case in which L is not known.
3.1 HIERARCHICAL TREE STRUCTURE
We start by defining a hierarchical partitioning of the d-dimensional hypercube. We define a tree T in which each node represents specific subset of the hypercube. A node Ne.: in the tree is defined z. The subset of the hypercube defined by a node N
by a level and a reference point
Region Ne,e) ) = [=1, 21 + 2 x... x [za, zd + 2-
The root of the tree corresponds 0 and the reference point Og- Each node Nt. has 2d children Net1, where 2, (f++1)) and h; ranges all 2d binary vectors. We denote by

---

Published as a conference paper at ICLR 2026
Algorithm
Require: Horizon T' Lipschitzness L, context dimension d.
1: for & [2'] do
2: Observe context Zt
3: Initialize & 4- 0, t- Od
4: while pr.= + 2 and Nz,z not leaf do # Traverse tree until active or leaf node reached
5: Find z' such that E Region N, where x' E E({,z)
6:
7:
if REDUCE(N has not terminated then Execute one iteration of the main loop of REDUCE(NNr.) else GUESS has not terminated then Execute one iteration of the main loop of GUEss(NN,;) GUESS (N terminates returning price p then
8:
9:
10:
11:
12:
Set node Nr,z marked by setting Pr,= f- p # If node is a marked leaf play corresponding price
13:
else Play pt,=
Algorithm 2 REDUCE(NN,.)
Set p < Pt- (,red(()( (i.e., the price associated with the parent node)
Initialization
2: Set Pr. + [o (p L2 (2-()-))), Pu + [1 (p + L2 (t-1)
3: Initialize p Pr.
4: repeat
# Main Loop
5: Post price p and observe I[(s; S p S bt) 6: if s[ S < bt) 0 then
7:
if p = pz then set p < pu: else terminate p f-
8: until p= Ø
C(e, 2) c 1)" the set of all the reference points corresponding to the children of Ne.-. Moreover, for any z' E C(e,)). we use pred + 1, 22)) denote the reference point of the parent node of NetI.=' (i.e, point 2). Under this notation, the parent node of Nt.- is N predtt))....))
We denote the set of reference points in nodes at level with Ze, which is defined recursively as Zo = O2 and Ze Then, each level i of the tree induces partition of the d-dimensional hypercube, since by con- struction, User. Region(Nr,e) = [0, 1]d. We limit the height of the tree to H [logze (T) = (llg((T)d-)).
UeE,,_,(EE, 2). Clearly, Region(Ne..)
Uzec((.)) Region(Ne+1.."
3.2 ALGORITHM
The algorithm works as outlined in Algorithm 1. In particular, each node N of the tree may be "marked with" a price pt,; E [0, 1] (Line 12).
Definition 1. node Ne.- is said to be marked if has been assigned a marking price p such that, for some context E (ogion(Ne,)) the trade is accepted at that is, [(fa(r)) S S fo(z)) = 1.
node Nr.: can be marked only if every node along the path from the root to Ne.- has already been marked. The set of marked nodes, therefore, forms rooted subtree. The free (i.e., not marked) leaves this subtree are referred to as active nodes. Intuitively, when we reach an active node Ne. our goal is to find a price that results in successful trade, that is, one satisfying [((f((z,) < S fo(x:)). To this end, we leverage the information already encoded in the tree: every node Ne. along the path from the root to Ne.: is marked with a price _e which trade occurred. These previously observed prices allow us to restrict the interval of candidate prices and form an estimate for price p that will be accepted by the valuations fa (xxe. fo(x)).
5

---

Published as a conference paper at ICLR 2026
Algorithm 3 (N
1: Let p = (t-d.pred( be the price associated to the parent node N 1. # Initialization
2: Set Pt, 1p L2 -2-(2-1) (1-1), p + L2 (2- (f-1)), with LT
3: repeat
Main Loop
4: Post price p- Unt=))), and observe T((:: S be)
5: until [s; S & b+)=
=1
6: Return p
Node-wise regret decomposition In the analysis of the algorithm, we decompose the total regret into the contributions the regret of each node. Let A C [T'] be subset of rounds. Then, we define
R(A)= = Σ (UA(())) - GFT, (ate), fo(a))).
BEA
For any node Ne.x E T, we define Te, S. [T] as the set of rounds in which the traversal of the tree stops on Ne,z (i.e., the number of rounds which N₁,- the node selected at the end of the loop of Line 4). Then, for any node Ne.z. we define the regret "accumulated on Ng,²" as the regret accumulated in rounds Te. Re, = E [R(Tr,))) Then, the overall regret can rewritten by separating contributions incurred at each level of the tree and at the nodes within that level:
Rr - Evez. Re
Any node of the tree that is never visited by Algorithm 1 has Te. 0 and thus does contribute to the overall regret.
For each observed context Tt. traverse the tree T by repeatedly selecting the child node whose associated region contains 2t, until reaching an active node or leaf node (see Line 4 of Algo- rithm 1). Then, the algorithm proceeds one of two ways: (i) if the node is not marked, we invoke one of the two routines REDUCE and GUESS described below (Lines 8 and 10); (ii) if the node is marked leaf, we post the price previously assigned (Line 13).
3.3 REDUCE ROUTINE
Consider active node Ne. and its parent .redd.) and focus the rounds E [2] such that Region Whenever Algorithm selects such node after the tree traversal, the algorithm executes one iteration of the REDUCE routine on Nr,; until its termination. The number rounds which Algorithm calls (EDUCH(NN..) is denoted by TRDDUCE
The REDUCE routine is described in Algorithm 2. Starting from the price ý Pt- (reed.)))((..)) sociated to the parent node of Nr.,, the algorithm computes two prices centered around p. each with distance (É-1), We denote such prices by = 1, L2 (c-1(- and Pe = 1o (p + (f- where the projection onto [0, 1] ensures that prices well-defined. Then, REDUCE repeatedly posts the price pL until trade is rejected (i.e., Ilss; S PL b,) 0). It then switches to posting Py until that price also rejected by one the agents. Once both rejections occur, the routine for node Ne.: terminates. From that point on, whenever the traversal ends at Nt.., Algorithm invokes the GUESS subroutine (see Section 3.4).
This procedure may appear counterintuitive, it intentionally seeks rejections of some specific prices. However, the primary objective of REDUCE is to control the regret that may accumulate the routine concludes. Specifically, upon termination, both prices pt. and pv must have been rejected once. Then, due to the Lipschitz continuity of the valuation functions, this restricts the range of future contexts for which the node Nr,: can be selected, effectively ensuring that f S O(L2-() for any context in the region corresponding Nr,., Formally
Lemma 1. Consider node Nr.z for which the REDUCE procedure terminated. Then, for any E Region (Ne,), it holds that fu(x) fa(a)) < 6.2-(
Although simple. this result is rather surprising, as it reveals a fundamental property of the problem. By viewing the context-generatin process adversarial, the previous result can be interpreted as

---

Published as a conference paper at ICLR 2026
follows: if the adversary "hides" the valuations both when PL and pa are played, then the Lipschitz constraint forces the adversary to place them close to the diagonal. procedure may not end for some nodes (indeed, for most nodes is not expected to do so). However, we show that the adversary forces termination at a specific node, then across all similar contexts (i.e., nodes in the subtree rooted at that node) the adversary's s gain remains limited. This situation is illustrated in Figure I, which also serves as intuition about the proof.
particular, the REDUCE
Now, we show that the regret incurred while running this routine is suitably upper-bounded. For- mally, let R == E (T(. be the regret accumulated by the REDUCE routine executed on node Ne,-- We can upper bound this term as follows.
Lemma (Regret due to REDUCE). For any node N₁,z with f 2 1 holds PRRDUCE & 24T.2-
3.4 GUESS ROUTINE
GPT
For an active node N₁.,, once the REDUCE procedure has ter- minated, the algorithm proceeds with the GUESS routine (see Algorithm 3). In this phase, prices are drawn uniformly at random from the set Pe.= = p L2 L2- (2-1,,,),, p + L2 122((--)]e. where Pe- (f,e the price used to mark the parent node, and e will be specified later. In the GUESS procedure, random prices are posted until trade some price p is cepted, at which point Ne,; is marked with Pt.=
xeller
The set Pt.s is chosen so that, by the Lipschitz condition, always contains a feasible price. Specifically, for every æ e Region (Ne.s) with fe(x) Z fx)), there exists a price in the interval jp (22-(e-1), p + T,2-(t-1)],, that will be accepted by the valuations (x( and fa(x). Moreover, we observe that [P = O(E L2 9) This allows us to bound the expected number of rounds required terminate the GUESS procedure, and to upper bound the regret incurred by executing it.
Figure I:
The x-axis (resp., y-
axis) represents the seller's (resp., buyer's) s) valuations. The blue (resp.. yellow) region denotes valuations for which pr. (resp., ptr) is rejected, Lemma states that if there are val- uations both in the yellow and blue one, then there cannot be any with GFT 2 6h green and red regions be the im- age of Region(Ne..) under f6). then Lemma forbids the red re- gion, but allows the green one.
Formally, we denote by T-UESS C [T] the set of rounds in which Algorithm 1 executes GUEss(Ne.z) Then, let 22,3 = E [[R[TT be the regret accumulated when GUESS is executed for note Nt,-, We provide the following upper bound on this regret term.
6L2-t. Let the
Lemma 3 (Regret due GUESS). Let Region NN,:). For any 0, consider posting prices uniformly at random from Pt.. pp (2-11-1) p + L2 L2-((-1)],, where p (e-1.pred((..) is the marking prices of the parent node. Then the regret incurred by the GUESS procedure is at most
2
ROUESS R
S <EE(Te.,>
The intuition about this result is simple: if the trades have small (i.e., less than e) GFT then the total regret is most per round. On the other hand, if the GFT is large (i.e., greater then then an e-grid over the possible prices is enough to win a trade with probability ()e22 L). which happens on average after O(L2- //e turns. In each of these turns we are only loosing ( f) because they take place after the REDUCE procedure of that node.
3.5 REGRET ANALYSIS
By using the results of the previous sections, and for an appropriate choice of e, we can now upper bound the overall regret incurred by the algorithm.
Theorem 1. For any 2d and any pair of L-Lipschitz valuation functions, Algorithu I with = LT 1/a guarantees RT OLL (TT
The proof, provided in the appendix, begins by partitioning the rounds [T] across nodes according to Equation (2). For each node, the rounds are then further subdivided based on the phase of the
7

---

Published as a conference paper at ICLR 2026
algorithm. Intuitively, for each round, we look the node "from which post price". Then, such rounds are partitioned based on whether the algorithm invoked REDUCE, GUESS, or if the node is marked leaf, specified in Line 13 of Algorithm 1. Each resulting term can be suitably upper-bounded by applying the previous lemmas.
4 UNKNOWN LIPSCHITZ CONSTANT: A MULTI-SCALE APPROACH
The algorithm presented in Section 3.2, heavily relies on the knowledge of the Lipschitz constant L. The exact knowledge of this constant is crucial proving the correctmess of the algorithm. More precisely, we exploited several Lipschitzness arguments to bound valuations. However, in many real-world scenarios may be unrealistic to assume that is known. In this section, we present an algorithm that extends the introduced in Section 3.2, removing the need for priori knowledge of L. This comes at the cost of only a slight deterioration in guarantees, yielding regret of Ö(L22r(d-1/44 instead of (LL)(d-1)/d)
We rely on geometric (i.e., multi-scale) extensions of the REDUCE and GUESS subroutines, which we call GEOMETRICREDUCE and GEOMETRICGUESS, respectively. In particular, for each node Ne.., we define a sequence of geometrically increasing Lipschitz constants L = O(2)). In GEO- METRICREDUCE we simply perform the REDUCE routines for each scale j. Crucially, terminating this procedure bounds the GFT in all subsequent nodes by ( (similarly Lemma 1), but without requiring the knowledge of L.
The construction of GEOMETRICREDUCE is more involved, and The reason is clear if we think about the analysis of GUESS. The analysis relied on a simple fact: for all trades with GFT greater than c, we have a probability of at least D2(22) /L) of marking the node, and thus we expect to finish in O(I2-*/c) rounds. However, it is also possible that the process never terminates, since there may be many trades happening with GFT less than e. Therefore, without knowledge of the constant L, the algorithm may spend many rounds working at excessively small scale, potentially leading to the loss trades with large GFT. Moreover, it becomes impossible to distinguish whether we are losing these trades because they have small GFT, simply because the chosen scale is too small for the real Lipschitz constant. The solution is to carefully increase the scale of our Lipschitz constant (more precisely, logarithmically), and to draw price from the corresponding grid uniformly random. This process is guaranteed to finish in expectation after O /c) rounds against valuations with GFT at least e, and does not require knowing beforehand. The overall algorithm is detailed in Section C and provides the following regret guarantees, which are only a O(logg(T) L) factor greater than the guarantees of Theorem
Theorem 2. Consider the nonparametric contextual bilateral trade problem, with one-bit feedback and strong budget balance with L-Lipschitz valuation functions. Then there is an algorithm that, without taking as input L, guarantees regret of RT (() 1)/d).
LOWER BOUND
In this section, we proceed to prove a matching lower bound that proves the tightness of our algo- rithm. In particular, will prove the following theorem.
Theorem 3. Any randomized algorithm under Krong-budgen balance, d-dimensional context vec- tors, and L-Lipschitz value functions, suffers regret of (LLT**) provided that T >> (4L)a. This also holds under full feedback.
From a technical perspective, the proof of Theorem 3 relies on Yao's 's weak minimax principle (Yao, 1977), which lower bounds the regret with the expected performance of deterministic algorithm against a distribution of instances. Formally:
Lemma 4 (Yao's 's weak minimax principle). For any deterministic algorithm generating {pr herry, and any distribution D, we have that Rr 2 BE E fa(a,)]+ (p)) -GFT:))
To construct hard distribution over instances, and consequently over valuation functions f. and ft, we start by considering all 2 possible assignments of discrete set of T context vectors two
8

---

Published as a conference paper at ICLR 2026
disjoint valuations (i.., such that price results in both trades being accepted). We then extend these discrete assignments to Lipschitz-continunn distribution is then taken as the uniform one over all 2 possible valuation functions. In particular, we build a distribution D over instances such that, for any deterministic algorithm, it holds
functions over the entire context space. The
Everr (o(()))))))))))) S. (x,)) -FT,,)))))))))) -GFT)))) 2 Š((TT=
We define the standard ō-grid 9 on the [0, 1] dimensional hypercube, i.e., 9 [0, 8 The set G is the set of possible contexts and, by fixing 5 T-1/d, we have that [g] T. Fix any ordering of contexts T1....,. 2T over G. We can define two valuations (5o. bb) = and ($1, b2) = (2 + C, +7). where ? > c > 0 are two parameters to be
11d.
(3 - --c) -) specified later. Notice that there is price p such that p wins both trades, in particular when the valuations are (so. bo) the only prices that get the trade accepted are in the set [ 7, 2 - =]. while under valuations (s1, b1) prices that make the trade happen are in [ + 2 + +7] For the same reason, we know that we can focus on deterministic algorithms that post prices only within one of these two intervals, since they yield GFT greater than that of any other price.
Next, for any > O, we build a family of L-Lipschitz functions from [0. 1] to {(sp, (s1,b)), In order to build our set of instances, consider a binary vector h E Hr of length T. Given context Ty the i-th bit of determines the valuations for such a context. In particular, selects (8o. bb) h, 0, and (s1, b1) if h4 = 1. For each of these binary vectors h E Hr, let füh (fh {b) : R² be the functions satisfying the corresponding assignment, i.e., ff = 8h, and (x.)
bng Note that for all # x' E G and any h E H. we have (f) (x))
and the same ||z-z'lles
holds for fh. By taking c = 1 and 7 2LT-1/4 1/d, and by noting that inf xf aeg - 2'1 2 8 = T-1/d we have that f and S are L--Lipschizz in G. Now, we need to extend the functions over the entire context domain [0, 1] which can be done in a black box way by the McShane extension theorem that we recall here
Theorem 4 (McShane's extension (McShane, 1934)). Let X C Rd be closed set, and be R-valued, L-Lipschitz function on X. Then there exists an extension f Rdd -> R that agrees with I on X and is L-Lipschitz on pdd?
We apply this on each f and take D as the uniform distribution over F= [ERH, This dis- tribution has the intuitive property that renders its history unhelpful in predicting future valuations.
Lemma 5. For any E [T]. the distribution of (st, bi) under D, conditioned the filtration up to time - 1, is uniform over {[s0, bo), b1))
We start by observing that the GFT that can be extracted from both (so, bu) and (s1, b1) is y 7/2 > O. Therefore, the benchmark will gain (h) Every fa(=)]+] = TT. On the other hand, by Lemma for any t E [7] the best expected GFT achievable by any deterministic algorithm is bounded from above by 2= = z. Since we set y -1/d we obtain that
T (7 - 6) 1--r- T
L
RT 2 2
2
concluding the proof of Theorem 3.
Remark This construction is reminiscent of that of Lu et al. (2009), who establish rate of ((T(++1)((+2)) (instantiated, as an example, in the finite MAB setting), which is higher than both our lower bound of (((((d1))/d and our upper bound of ((T(d- despite our setting appear- ing more challenging. However, this is not unexpected, since the proof of Lu et al. (2009) leverages significantly sparser grid in the context space (O(T-1/(d+2)) instead of 1(dd) They are allowed to do this since in their setting contexts can be repeated without incurring zero regret, as noise allows suboptimal actions to remain indistinguishable for longer. In contrast, in our setting, the reward function is identical whenever the same context is observed.
Note that we need T (4L)² for the valuations be well defined (i.e., in [0, 1)2).
In our proof we only care about the existence of such an extension, however, the proof of the thcorem is constructive and defines f as f(z) inf,rex (z) + T.Il - x' (l,c), (Weaver, 1999, e.g., Theorem 1.33).
9

---

Published as a conference paper at ICLR 2026
CONCLUSIONS AND FUTURE WORK
There are many interesting possible directions for future works. Similar to Slivkins (2014), one can consider general context space and derive rates that depend on its packing covering dimension. Alternatively, following Kuzborskij & Cesa-Bianchi (2020); Cesa-Bianchi et al. (2017), one may exploit additional structure in the function class mapping contexts valuations. From bilateral trade perspective, other notions of budget balance are also relevant, such as weak and global budget balance (Cesa-Bianchi et al., 2024; Bernasconi al., 2024). Under these notions, the learner may post different prices to the buyer and the seller, subject only to the constraint that the market is subsidized in each round and across all rounds. respectively. Moreover, our tight rates are attainable in part because our model does not allow for noise, unlike some general nonparametric bandit models (Lu al., 2009; Slivkins, 2014). The question of what rates can be achieved under the noisy valuations remains open. Finally, Cosson et al. (2026) also studies profit maximization. It would be interesting to study the profit maximization setting with general Lipschitz contexts.
ACKNOWLEDGMENT
The work of MB, and AC partially funded the European Union. Views and opinions pressed are however those of the author(s) only and do not necessarily reflect those of the European Union the European Research Council Executive Agency. Neither the European Union the granting authority can be held responsible for them.
This work is supported by ERC grant (Project 101 165466 PLA-STEER).
REPRODUCIBILITY STATEMENT
Full proofs are included in the Appendix, and assumptions are explicitly stated in the model.
REFERENCES
Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Repeated contextual auctions with strategic buyers. Advances in Neural Information Processing Systems, 27, 2014.
Yossi Azar, Amos Fiat, and Federico Fusco. An a-regret analysis of adversarial bilateral trade. In Advances in Neural Information Processing Systems, 2022.
François Bachoe, Tommaso Cesari, and Roberto Colomboni. A contextual online learning theory of brokerage. arXiv preprint orXiv:2407.01566, 2024.
Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Federico Fusco. No-regret learning in bilateral trade via global budget balance. In Proceedings of the 56th Annual ACM Symposium Theory of Computing, pp. 247-258, 2024.
Liad Blumrosen and Ychonatan Mizrahi. Approximating gains-from- frad-t in bilateral trading. In WINE, volume 10123 of Lecture Notes in Computer Science, pp. 400-413. Springer, 2016.
Natasa Bolić, Tommaso Cesari, and Roberto Colomboni. An online learning theory of brokerage. In Proceedings the 23rd International Conference on Autonomous Agents and Multiagent Systems, pp. 216-224, 2024.
Johannes Brustle, Yang Cai, Wu, and Mingfei Zhao. Approximating gains from trade in two-sided markets via simple mechanisms. In Proceedings of the 2017 ACM Conference Economics and Computation, pp. 589-590, 2017.
Nicolò Cesa-Bianchi, Pierre Gaillard. Claudio Gentile, and Sébastien Gerchinovitz. Algorithmic chaining and the role of partial feedback in online nonparametric learning, In Conference on Learning Theory, pp.
PMLR, 2017.
Nicolò Bianch,, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Bilateral trade: A regret minimization perspective. Mathematics of Operations Research, 49(1): 171-203, 2024.
10

---

Published as a conference paper at ICLR 2026
Houshuang Chen, Yaonan Jin, Pinyan Lu, and Chihao Zhang. Tight regret bounds for fixed exed-price bilateral trade. arXiv preprint arXiv:2504.04349, 2025.
Ningyuan Chen and Guillermo Gallego. Nonparametric pricing analyties with customer covariates. Operations Research, 69(3)977--984 2021.
Maxime C Cohen, Ilan Lobel, and Renato Paes Leme. Feature-based dynamic pricing. Management Science, 66(1 1):4921-19443 2020.
Romain Cosson, Federico Fusco, Anupam Gupta, Stefano Leonardi. Renato Paes Leme, and Matteo Russo. Contextual online bilateral trade. 2026. Private communication, to appear on the arXiv.
Yuan Deng, Jieming Mao, Balasubramanian Sivan, and Kangning Wang. Approximately efficient bilateral trade. In STOC, pp. 718-721, ACM, 2022.
Solenne Gaucher, Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Vianney Perchet. Feature-based online bilateral trade. In The Thirteenth International Conference on Learning Representations, 2025.
Elad Hazan and Nimrod Megiddo. Online learning with prior knowledge. In International Confer- ence on Computational Learning Theory, pp. 499-513. Springer, 2007.
Zi Yang Kang, Francisco Pernice, and Jan Vondrák. Fixed-price approximations in bilateral trade. SIAM, 2022.
In SODA, pp.
R. Kleinberg and Leighton. The value of knowing a demand curve: bounds on regret for online posted-price auctions. In 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 594-605, 2003.
Ija Kuzborskij and Nicolo Cesa- Disnchia Locally- nonparametric online learning. Advances in Neural Information Processing Systems, 33:1679-1689, 2020.
Allen Liu, Renato Paes Leme, and Jon Schneider. Optimal contextual pricing and extensions. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1059-1078. SIAM, 2021.
Ilan Lobel, Renato Paes Leme, and Adrian Vladu. Multidimensional binary search for contextual decision-making making. Operations Research, 66(5):1346 1361, 2018.
Tyler Lu, Dávid Pál, and Martin Pál. Showing relevant ads via context multi-armed bandits. In Proceedings of AISTATS, 2009.
Anna Lunghi, Matteo Castiglioni, and Alberto Marchesi. Better regret rates in bilateral trade via sublinear budget violation. arXiv preprint arXiv:250.111419, 2025.
Jieming Mao, Renato Paes Leme, and Jon Schneider. Contextual pricing for lipschitz buyers. Ad- vances in Neural Information Processing Systems, 31, 2018.
Preston McAfee. The gains from trade under fixed price mechanisms. Applied economics research bulletin, 1(1):1-10, 2008
EJ McShane, Extension of range of functions. Bulletin of the American Mathematical Society, 40 (12):837-842, 1934.
Roger B Myerson and Mark A Satterthwaite. Efficient mechanisms for bilateral trading. Journal of economic theory, 29(2):265-28) 1983.
Alexander Rakhlin and Karthik Sridharan. Online nonparametric regression with general loss func- tions. arXiv e-prints, pp. arXiv-1501, 2015.
Aleksandrs Slivkins. Contextual bandits with similarity information. Journal of Machine Learning Research, 15:2533-2568 2014.
11

---

Published as a conference paper at ICLR 2026
Matilde Tullii, Solenne Gaucher, Nadav Merlis, and Vianney Perchet. Improved algorithms for contextual dynamic pricing. Advances in Neural Information Processing Systems, 37:126088- 126117, 2024.
William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 16(1):8337, 1961.
Nik Weaver. Lipschitz Algebras. WORLD SCIENTIFIC, 1999. doi: 10.1 URL https: 11422/400..
//www. wwt.:oordd.ceeeii.cc.oommm
Andrew Chi-Chin Yao. Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium Foundations of Computer Science (sfes 1977), pp. 222-227. IEEE Computer Society, 1977.
12

---

Published as a conference paper at ICLR 2026
A OMITTED PROOFS FROM SECTION 3 (UPPER BOUND)
Lemma Consider a node Nt,z for which the REDUCE procedure terminated. Then, for any I E Region(Ne., it holds that fu(x) - fa(x) ) - 6L2-
Proof. Let PL = 1 (2-((-1) and = II o + L2 (2-(1-))), where p = (red is price with which we marked the parent node.
If REDUCE terminated for node Ne.,, then Line 7 of Algorithm 2 has been executed exactly twice. We denote by 4r E (T) the first time which Line is executed (i.e., the round which we observe trade rejected for PL). and analogously denote by to [I] the second time in which Line executed (i.e., the round which we observe a trade rejected at price pu). Let æ Itz and
TU Itv-
At the end of REDUCE we have two pairs (pL, LL) and (pu,2y) such that
(s(x)) > Pr. or fo(xL) PL.
and
fx(1)) > Pu or f((zv) Pu.
Moreover, by the Lipschitz condition and the fact that the parent node N 1.ed,, is marked (see Definition 1), it follows that for every E Region(Ne.)) C Region (Neionn(N--ue (t.)d() we have
(x) < (1, + L2 L2- 1 - pu and fa(a) 2 max (0, L2
L2- (2-1) Pt.
Then, by rewriting the above for zy Region N. we get that the buyer refused the trade ar price Pu. since the seller would have accepted it. Hence, fo(xv) < py. Similarly, we know that it was the seller who rejected the trade at æ,, implying (XL) > PL. Now consider any Region(Ner.) By Lipschitzness we have that
(z() - fa(x s L2 and
1f(()) - fo(vo) S L2-
from which conclude that
fz) fz) S fu(xv) fo(x)) + S PC PL + 2 = 662
This concludes the proof.
Lemma 2 (Regret due REDUCE). For any node No,₂ with f 2 1 it holds R
PREDUCE < 24L2
First, observe that in rounds belonging to TREDUCE we accumulate regret only twice, once for each rejection prices PL and pU, since accepted prices yield zero regret. Moreover, by con-
Proof.
struction have that Ne,= is active, marked and that REDUCE has been completed for (ed1.prd((..)) For any E Region S Region((Ne-1.reatt..a we can apply Lemma 1, and we get that fo(x) fa(x) < 6L2 6L2-(E-1) (E-1) 12L2- Therefore, we obtain pREDUCE < 24L2- which concludes the proof.
know that the parent node Ng-1.pred((.a) has been
Lemma 3 (Regret due to GUESS), Let E Region NN,.). (N,)). For any c O, consider posting prices uniformly at random from Pt.. (p (2-(4-1) p L2-(e-1)],. where ÿ Pt-1.pred(t.s) is the marking prices of the parent node. Then the regret incurred by the GUESS procedure at most
-
RGUESS < <E,[T
Proof. For each x E Region (Ne,z) we have that
fa(x)= < [z( + L2 (e-1) S (e-1)
where ह Region(N, (Ne--..pedd is the context the parent node's area under which p was ac- cepted. Similarly, we have that
M(x)) [b(T) I.2 (e-1) 2 2Ø I2 (t-11.
13

---

Published as a conference paper at ICLR 2026
Thus, if fo(x) fz) then the interval (f),,, fo))) is contained in the interval 15 L2 (t-111) -++
L2 (.-1)).
For any t GUESS we are going to consider two cases: (i) fb((z) fa(x)) S e, and (ii) fo(Ø)) f.a
fa(1)) > e. We let
GuEss,1 = {t E T2, fb(z)) fo (xx) =
and T22 GUESSS.2 T decomposed as
t,=
GuBss.
Then, by linearity of expectation, the regret R can be
RGUESS 2,
R (1 + R (I (1
T First, we observe that if GuESS.1 then the first term in the decomposition can be bounded above by =T=|l Indeed, in this and moreover f,=
have [fo(x)) fx()) S GFT,(- fa(r) O,
G
C Te.
Similarly, the second term be upper bounded by [ G, where G is the maximum GFT attainable. Since the REDUCE procedure must have already terminated for Ne, before GUESS is executed, we apply Lemma 1, which yields G S 6L2 Therefore, R <Bl[Te + 6L2 f. E|IT
In order to conclude the proof we have to upper bound Bi Notice that for every t E 7,2 7.GUESS.2 we have fa, fa(xt) > c. Hence, there exists at least one price p in the discretized grid Pe,: such that (x1) S I (z)). This implies that the probability terminating GUESS at each round E GUESS is at least |Pt and therefore
E E
I] S |PP,zl S 41.2
This concludes the proof.
Theorem 1. For any T > 2d and any pair of L-Lipschitz valuation functions, Algorithm I with
= LT
1/8 guarantees Rr OI.log,, (1 (TYT
Proof. For node Nr.,, let TLEAF C [T] be the set of rounds in which Line 13 of Algorithm is executed for that node (i.e., the number of times leaf node is played after being marked). Moreover, let
LEAAF
E [R(TT,EAF)
R
First, following Equation (2), we decompose the overall regret into the contributions incurred at each level and the nodes within that level:
RT ΣΣ Re,
ΣΣ
CR
REDUCE
+
R + +RI,A
GGEES
RLEAF))
where the second equality come from the fact that RREDUCE TuEEs TLAA form a partition of Te.= for each level E (0, 10,1..... ... H. and node E Zz.
f,z
REDUCE Now we are going to analyze the first term. By Lemma we have that RRCDUCE < 24 - Moreover, we recall that H = |logza T and Ze = 2dh Thus
(lgg,((T)
Σ
PREDUCE 24.1
2de-
24L T 2dH 2-1
log T1
where in the last incquality we used that that logga (T) 1/2 log(T)) and that d+ 2de- monotone
so that EH 20l-1 HH
14

---

Published as a conference paper at ICLR 2026
GUESS
Similarly, for the second term, going to proceed follows:
H
1 26
RQUESS
- Σ5
<B, + 24
(Lemma 3)
8=0 xEZI
t= sEZe
c + 24L
2dt
( 2dd)
24L log
< ET +
2dlogga (T)) 2- 200
ed
24L log T 71
< <T +
cd
Finally, by choosing c= LT we obtain
ΣΣ 0E
24 log (TT S LT + log (T)
24L
LEAF To analyze the last term, we recall that [, non-empty only if (i.e., is a leaf node) and the node was already marked. Thus we can use Lemma which shows that
RLEAF S 6L2 logga (T) [T S GLT [Tr,].
Therefore, by restricting our attention to the H-th layer we get
H
RLEAF
Σ
R
Ł=
=EZ
<
Σ
6LT 1/dB
[TH,.)
=EZH
GLT
Combining all parts Thus, the total regret can be bounded by
72 + 7d
Rr < d
LTT log( (T).
concluding the proof.
B OMITTED PROOFS FROM SECTION 5 (LOWER BOUND)
Lemma 5. For any E [T]. the distribution of (st, b() under D, conditioned on the filtration up to time - 1, is uniform over {(so, bo), (51, (s))b.)..
Proof. Since we have full feedback, we know the sequence of valuations ((*T) by br) The set of functions j that agree on these valuations for the sequence of observed contexts is 2t-1 we call this set F.. Out of these functions, half will have ht 0 and half will have htr 1, and thus the conditioned probability on (St, bz) is uniform over { bo), (81, b.)}-
C DESCRIPTION OF THE ALGORITHM FROM SECTION 4 AND OMITTED PROOFS
The algorithm's 's main loop is the vanilla one introduced in Section 3. In particular, traverse the tree until we reach an active node (Line 4 of Algorithm 4). Then we perform either the GEO- METRICREDUCE, of Algorithm 5 or GEOMETRICGUESS of Algorithm In particular, for specific
15

---

Published as a conference paper at ICLR 2026
Algorithm 4 Without knowing the Lipschitz costant
Require: Horizon T', context dimension d.
1: for E [T] do
2: Observe context Zt
3: Initialize & <- 0, 2 t- 0₂
4: while pr.z + Ø and Nr,= not leaf do # Traverse tree until an active or leaf node reached
5:
Find z' such that E Region N2+1, where z' E C({,z)
6:
e & 1,
7:
if GEOMETRICREDUCH(.N.. has not terminated then Execute one iteration of the main loop of GEOMETRICREDUCC((W... else GEoMETRICGUESS Nx,=) has not terminated then Execute one iteration of the main loop of GEOMETRICGUESS(N..)
8:
9:
10:
11:
if GEOMETRICGUESS! (Nr,z) terminates returning price then
12:
Set node Ne,₂ marked by setting Pt,= +- p
13:
else Play pt,z
# If node is a marked leaf play corresponding price
Algorithm 5 GEOMETRICREDUCE/NN
1: Set +- P(-1.pred(e, (ie. the price associated to the parent node)
# Initialization
2: Set D L,2' for E (o......) with [e 12go(2Lo)] and Lo 1/2
3: for j E ( . do
# Main Loop
4: Set p/. - [o.1] (p 122-((-1)). m + [1 (p+ 122 (22-(e-1))
5: Initialize + 1l.
6: repeat
7:
Post price p and observe [1, S - bt) if 1(s S p S by) = then
8:
9:
p = pz. then set + p else terminate +- Ø
10:
until p=
node, we continue to perform a step of the main loop of Algorithm until it meets its termination condition, one step of Algorithm 6, until terminates. Algorithm 5 simply tries sequentially all scales of I as in the plain version. Algorithm 6, the other hand, at iteration т, uses the same largest scale permissible at that iteration Line 6 of Algorithm 6, and then draws uniform prices from the associated grid (Line 7).
Lemma 6. For every > 0 and for every node Nt. there exists an algorithm that does not require knowledge of such that
-
Re, 20(e22*+
Proof. Define j = =[e + (2Lo)) and for each j E {o,.... define / In25. Note that
2- > 1. For each j we now start GEOMETRICREDDCCE on prices vi. 2 p 2 2- L,, when we get rejection both for př, and pi we increase j.
2-1(22211)) (t- i and
Claim 1. Once the GEOMeTRICREDUcE procedure concluded, then we know that for all x E Region(Ne,,) we have fo(x) fx) < 1
Proof of Claim 1. If the GROMETRICREDUGE has concluded we know that we collected tuples (1/ jt) and (ot, pb);= that were refused.
Now take any E Region Ne.,), since price (z. p) was accepted at N (.red())) we have that
[a(x) [(()) L2 (1-1) 5 L2 (2-1) -p+ 2+p2211 212
and
(b(x) Mb)) L22 (t-1) > Φ I.2 12-((-1) 2
(t-1)
16

---

Published as a conference paper at ICLR 2026
Algorithm 6 GEOMETRICGUESS(
1: Let p = (ted))) be the price associated to the parent node 1 # Initialization 2: Set 1/ Tn for j E {0, -.,....J) with [e (2g2(27.)) and To 1/2 (2-1))
3: Set P 1p 1/2-(6 1) p+ Li2- (t- 1) with T-1/4
4: Set 0
5: repeat
# Main Loop
6:
j(t) := arg max {j E (O.......
IPLs r
7: Post price p- ~ Unif(P),")) and observe [s, S p S b))
8:
T until [(s, S p b,) =1
9:
10:
Return
We take j' such that I/_1,= 2 L. Then, by plugging in the above of and ry. similarly the proof of Lemma 1, we know that
f6(2) - fx(x) s falltt f + 2L2 S vi - pi. +222222- 4lc- 2L2
where the first inequality is by Lipschitzness of far fo. Moreover, note that 2L 2 i' and thus fo(x)) (x) & 100.2 for all E Region(Ne:, This concludes the proof of Claim 1.
By performing GEOMETRICREDUCE at node Ne.,, we only suffer regret of at most 2j < 2(E + 12go(2Lo) + 1) S 48 if l 2 1 and L, 1/2 (the number of rejected trades), which multiplies the maximum regret suffered, which by Claim 1, is at most -0 and thus total regret of 80EL2-
After this phase, we start using GeoMetRIcGuESS in the following multi-scale fashion. Let be the "internal time" of the routine. At each execution 7 of GEOMETRICGUESS, we consider the largest integer j(r) so that |P!"" S r, where we defined Pi.-- = fp - 2 , + i/2-((t1)),
and thus |P|_] 4 2/e.. Now, each 7 we draw uniformly random price from the corresponding uniform grid ( Define 7* as the smallest integer so that T,2 2 I., and note that T' SL2
After 7* turns of GEOMETRICGUESS, we will have that, for all valuations with GFT at least e, there is at least one price in Pits that wins it. We then consider blocks B; defined as the intervals The probability of winning trade with GFT larger than for B; is (21r)-1, since for E B, the size of Pi remains unchanged for all E B; and smaller than 2 We can define an appropriate Markov chain to compute the expected number of times until we stop.
B, 1
Claim 2. Consider a Markov chain with states (O) and with transition probabili- lies Pa = P(s + 1[8) 1/(2* N) and (())s) = 1-pp all and [2*N..... 2 N 1). Moreover, let () 1. Then, the expected hitting time of the state starting from state N is at most 4N
Proof of Claim 2. The probability of reaching s = 2 N from = 2 is (1-1/ < se- and the probability of reaching 2 N from N is thus at most e The expected number of transitions before hitting is the sum of the expected number of transitions block B,, conditioned on reaching 2 N. We call X, the number of transitions inside of block and T the hitting time of
17

---

Published as a conference paper at ICLR 2026
0. Thus:
Σ
E B[X,| Preach 2 N)
(E x reach 2'N =0)
1=0
8=0
2 Ne
(P(reach N2 Se and X; S 22'N)
0m0
20
2
N
which is equal to N c 4N concluding the proof of Claim 2.
We can then use Claim to conclude that the expected number of turns of GEOMETRICGUESS before observing success is at most 4r", and each turn we experience regret of only 20I2- thanks to Claim I.
Thus, for each S r* we only have a regret of 10L2- per turn, and after (for r 2 T²), we have regret of most
640L22-2
<T + 807 L2
eT, +
as in the proof of Lemma 3.
The total regret for marking node is
6401,22-20
Re,
8 GBOMETRICREDUCE
1002
[E(Tr,
(3)
TST
TDT'
=0 -0(111 (1
2 28
(4)
Lemma 7. For every marked leaf node Ne,; the regret Re, is at most O(L2-'E(TA,
Proof. Since we reached leaf node, we must have concluded GEOMETRICREDUCK in the parent node and thus RLEAF < 20L2 20L2-"E[T,, by Claim 1.
Theorem 2. Consider the nonparametric contextual bilateral trade problem, with one-bit feedback and strong budget balance with L-Lipschitz valuation functions. Then there is an algorithm that, without taking as imput L, guarantees regret of Ry (12
Proof. The regret of every non-me markmdd node is upper bounded by Lemma 6, while the leaves once marked have a regret upper bounded by Lemma 7. Thus
" Σ Ž=
-22-28 28
L
R S
L12 TET
+
Σ
(L2-"EE(T,,t))
=EZH
I < Σ 0122- + O(T))
Σ
0 OLTT-
$ O/ +0
L2
HT((d22/4 + O(LT(d-1)/d)
then, by choosing 1/d and noting that H < loga (T) dd obtain that
RT S 0(log, (
concluding the proof.
18

---

Published as a conference paper at ICLR 2026
D EXPERIMENTAL EVALUATION
For completeness, we provide an empirical validation on synthetic data to confirm our theoretical findings.
We consider a setting in which valuations are quadratic functions of the context. We run our algorithm on 30 independent instances built as follows. For each run we start by uniformly sampling two matrices A, B [-1, 1J1,1 Then, for each we sample uniformly at ran- dom in [0, 1] a dd-dieensional context z₁,- We compute valuations z; Azz and x; Bæ, up to normalization to have final valuations belong to the unit square. In partic- ular, the valuations are computed
6300
330
16
02
fx( 2. Ar, d?
fo(Ie) 2, Br, + de d2
d2
We test our algorithms on d = (,, 43. run 30 repetitions for each choice of d. The results reported in Figure 2, and essentially confirm our theoreti- cal findings. expected, the learning problem becomes harder as the context dimension d increases, and the behavior of average regrets is consistent with the rates obtained in Theorem 1.
10, and
Figure 2: Average regret (together with 95% confidence intervals) in the quadratic setting.
Figure 3: Comparison between average regret and theoretical bounds.
In Figure 3 we report the logarithmic plot of the regret. In particular, for the last 10 steps, we plot log(t) vs (og(Re) for (2, 3, 4), along with the slopes associated with the theoretical bounds (i.e., f(d-1)/d) and the linear slope t (we normalize the lines so that they all start from so that we can compare more easily their slopes). We can see that the regret slope matches the theoretical guarantees. In particular, the regret grows at most as fast as (1(d-1)/d) for all d (and for = 2 appears be growing even better rate).
19


Reviews:
[{"review_id": "a8UgHXKVIp", "reviewer": "Reviewer_cm2p", "summary": "This paper studies the problem of contextual online bilateral trade in a general nonparametric setting. At each round $t$, a learner observes a context vector $x_t \\in [0, 1]^d$ and must post a single price $p_t$ to a seller-buyer pair with private valuations $s_t$ and $b_t$. The valuations are assumed to be arbitrary L-Lipschitz functions of the context, i.e., $s_t = f_s(x_t)$ and $b_t = f_b(x_t)$. The learner's goal is to minimize regret, which is the difference between the total possible gain from trade and the gain achieved by the learner's prices.", "questions": "- In Section 1.1, you mention that a first \"trick\" leads to a suboptimal regret of $\\tilde{O}(T^{(d-2)/d})$, and a second trick improves this to the optimal rate of $\\tilde{O}(T^{(d-1)/d})$. However, for any dimension $d \\ge 2$, the exponent $(d-2)/d$ is smaller than $(d-1)/d$, which would imply that the \"suboptimal\" rate is asymptotically better. Could you clarify this point? Is there a typo, or is there a nuance in the definition of \"suboptimal\" in this context?\n- What are the time and space complexities of Algorithm 1 per round? While this is a theory paper, the contributions would be strengthened by empirical validation, even on synthetic data, to demonstrate how the regret scales in practice and to verify the theoretical guarantees. Have any experiments been conducted?\n- Your work focuses on maximizing the gain from trade (a social welfare objective) under strong budget balance. Could your techniques be extended to a revenue-maximization setting, where the learner posts different prices to the buyer ($p_b$) and seller ($p_s$) and aims to maximize the cumulative revenue $\\sum_t (p_b-p_s)$?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper extends the contextual online bilateral trade framework from linear valuations to a general nonparametric setting where valuations are arbitrary Lipschitz functions of the context. The main results are achieved under the restrictive setting of one-bit feedback and strong budget balance, a setup where prior work often required relaxing one of these constraints.\n- A major strength is the tightness of the results. The paper establishes an upper bound on regret of $\\tilde{O}(T^{(d-1)/d})$ and provides a matching lower bound of $\\Omega(T^{(d-1)/d})$ up to logarithmic terms.\n-  The related work section is comprehensive and clearly situates the paper's contributions within the existing literature.\n- The section “1.1 TECHNICAL CHALLENGES AND TECHNIQUES” very clearly describes the details about the problem, algorithm, results, and the proof techniques at a high level.\n- The algorithmic components are presented in a clear, modular fashion (Algorithm 1 and its subroutines), and the accompanying descriptions in Sections 3.3 and 3.4 effectively explain the purpose of each routine.", "weaknesses": "- The assumption that valuations are deterministic functions of the context ($s_t = f_s(x_t)$, $b_t = f_b(x_t)$) is a significant limitation. Real-world valuations are typically subject to noise. The authors correctly note in the conclusion that adding noise is an open question, but the implications of this assumption on the main results could be discussed more prominently. The deterministic nature is precisely what allows certain proof techniques to work and is a key reason why the tight regret rate, which is better than in some noisy nonparametric bandit models, is achievable. A clearer discussion of this tradeoff in the main body would better contextualize the results.\n- While the contributions are substantial, their novelty could be framed more sharply against existing techniques in nonparametric bandits. The paper mentions using a hierarchical tree structure similar to adaptive zooming (Slivkins, 2014) or chaining (Cesa-Bianchi et al., 2017). However, the paper could be improved by more explicitly articulating why those methods are insufficient on their own and how the proposed \"tricks\" (especially the REDUCE routine) are essential modifications to handle the specific structure of the bilateral trade problem (e.g., the reward discontinuity and one-bit feedback).\n- The manuscript would benefit from a figure illustrating the hierarchical tree partitioning of the context space. This would provide a helpful visual aid for the core data structure of the algorithm.\n- The terminology for interacting with the market is inconsistent. The text and algorithms variously use \"post price\", \"play\", and \"pick\". Standardizing to \"post\" or \"propose\" would improve consistency.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hFkWpYp1Qi", "reviewer": "Reviewer_5FAT", "summary": "This paper studies contextual online bilateral trade in a nonparametric setting in which the buyer’s and seller’s valuations behave according to arbitrary Lipschitz functions of the context. The authors develop an algorithm through a hierarchical tree construction, achieving a low regret of $O(T^{\\frac{(d-1)}{d}})$, assuming the valuation functions are Lipschitz.\n\nThe regret is better than the lower bound of $O(T^{\\frac{(d+2)}{d+3}})$ for the general cases by exploiting the specific shape of the gains-from-trade function. The authors also develop an algorithm agnostic to the Lipschitz constant, and provide a matching lower bound.", "questions": "1. Could the authors comment on the overhead in the regret bound and applicability of the proposed algorithm in practice?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is generally well-written and clear. The collection of theoretical results is non-trivial and technically strong. The authors provide a complete picture for regret in contextual online bilateral trade in a nonparametric setting.", "weaknesses": "1. It seems that the overhead in the regret bound is pretty large, which might make the proposed algorithm not applicable in practice.\n\n2. The paper would be stronger if the authors can conduct empirical studies to validate the effectiveness of the proposed algorithm for practical instances.\n\n3. This paper could be better suited for other theory and/or econ conferences, such as EC/SODA/STOC/FOCS.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pIf7L0Zmmu", "reviewer": "Reviewer_L5Zh", "summary": "The problem of bilateral trade is a new context for online pricing problems. In essence, compared to online pricing, both a buyer and a seller present themselves with private valuations, and the agent must propose a clearing price, which, if accepted by both parties, will generate some social welfare that the agent pockets. One can also view this as a market maker pocketing the bid-ask spread, but in a setting where there is no market and thus bid/ask prices are hidden. \n\nThe objective in this paper is to study the problem with features and, in particular, the case of Lipschitz valuation models when the agent doesn’t observe his own reward, only whether or not a sale happened. The specific online learning set-up considered is adversarial contexts, from which fixed (i.e. stationary in time) but unknown Lipschitz functions generate the hidden bid and ask prices. The observability set-up is what is known as _one-bit_ feedback in online pricing, wherein only a 0/1 signal is observed corresponding to whether or not the transaction cleared. \n\nUsing sequential discretisation of the context space, the authors propose an algorithm whose regret (with respect to an omniscient planner) is of order $\\tilde{\\mathcal{O}}(T^{\\frac{d-1}{d}})$, while using Yao’s principle to provide a matching lower bound. This generalises a prior work on linear valuation models.", "questions": "While I remain sceptical of accepting this paper, the following questions might affect my view on the paper:\n\ni) Technical challenges discuss the difficulties inherent in the setting, but only compared to classical online learning settings ($\\ell 70$). What complexities are unique and insightful to bilateral trade / Gain From Trade when compared with online one-bit learning in a posted-price auction, for example? \n\nii) The algorithm obtained is not anytime (it depends on prior knowledge of $T$. While it is always possible to add a doubling trick, what is fundamentally in the way of making the algorithm properly anytime?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The results claimed are clearly presented and their proofs are succinct yet rigourous. Overall the paper's soundness is commendable from a mathematical standpoint. I would also like to highlight that the authors openly point out a limitation of their main algorithm (dependence on knowledge of the Lipschitz constant of the valuation functions) and provide an adapted algorithm.\n\nThe presentation is clear and the text is easy to follow, mostly due to the relatively new nature of the online bilateral trade problem: the problem setting is easy to explain and related works are few and well-differentiated. Nevertheless, the quality of the writing is plain to see: it is fluid, and I spotted only very few typos.", "weaknesses": "The main weakness for me is in the contribution, or perhaps its contextualisation. While technically sound, the results of the paper didn’t bring me any exciting new insight into online learning/estimation. While bilateral trade is an interesting setting, I didn’t find a clear characterisation of what key properties it has, to what extent they are unique or generalise, say to/from online auction problems. I think a broader characterisation of the problem and its properties (or a clear application if the authors would rather go that route) would add to the conversation, helping to differentiate this setting from the myriad other bandit-like settings.\n\nThe following are minor feedback:\n\n- I wouldn’t use ${\\bf Area}(N_{\\ell,z})$ to denote a set, as area refers to a scalar quantity in geometry. I would pick another synonym or word which doesn’t have a common use in mathematics, such as region, footprint, shadow…\n\n- Technically, regret was only defined for a sequence of times from $1$ to $T$, so expressions such as $\\ell$657 are under-defined, though they are comprehensible. At a minimum $(x)\\_{t=1}^T$ and $(p)\\_{t=1}^T$ should be passed as arguments along with $(f_b,f_s,T)$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0A8IoMqX8o", "reviewer": "Reviewer_xjuZ", "summary": "This work studies contextual online bilateral trade under strong budget balance and one-bit feedback. At each round t, a d-dimensional context $x_t ∈ [0,1]^d$ arrives, buyer and seller valuations are generated deterministically by unknown L-Lipschitz functions $f_b$, $f_s: [0,1]^d → [0,1]$, and the learner posts a single price p_t; a trade occurs if and only if $f_s(x_t) ≤ p_t ≤ f_b(x_t)$. The objective is to maximize cumulative gain-from-trade, $GFT(p_t|s_t,b_t) = I(s_t ≤ p_t ≤ b_t)(b_t − s_t)$, equivalently minimize regret against the in-hindsight optimal policy that knows $f_b,\\ f_s$. The main contribution is a nonparametric, context-sensitive algorithm with a hierarchical dyadic partition (an adaptive tree) of the context space. For each node (level $l$, reference point $z$), the algorithm first runs a REDUCE routine (probing two prices separated by $L·2^{−(l−1)}$ to force rejections), which geometrically constrains future GFT to $O(L·2^{−l})$ in that region by Lipschitz arguments; then a GUESS routine samples uniformly from an ε-grid around the parent’s marking price to discover an acceptable price and mark the node. With a careful per-node regret decomposition and tuning $ε = L·T^{−1/d}$, the algorithm achieves regret $\\tilde{O}(L·T^{(d−1)/d})$ under one-bit feedback and strong budget balance. A multi-scale variant removes the need to know L a priori with only a $polylog(L,T)$ loss, giving $\\tilde{O}(L^2·T^{(d−1)/d})$. Finally, the paper proves a matching (up to logs) minimax lower bound $\\Omega(L·T^{(d−1)/d})$ even under full feedback, establishing the optimal rate in this noise-free Lipschitz setting.", "questions": "The GUESS routine uses a uniform ε-grid in an interval of length O(L·2^{−(ℓ−1)}), and the analysis leverages a success probability of order 1/|grid| to bound expected time-to-mark. In high levels (large ℓ), the interval shrinks, but the number of active nodes grows; conversely, at shallow levels, the interval is wider but fewer nodes contribute. Could the authors elaborate on how sensitive the overall bound is to the specific grid spacing ε = L·T^{−1/d}? In particular, if contexts are adversarially clustered so that the algorithm revisits certain “hard” nodes disproportionately, does the node-wise decomposition still preclude superlinear accumulation at those nodes? A short intuition (beyond the formal summations) on how the per-node “mark fast or suffer only small GFT” dichotomy prevents pathological concentration would help readers build geometric intuition for the optimal T^{(d−1)/d} rate.\n\n(Will increase the score if the authors properly address my concerns.)", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1, Novel problem formulation: The REDUCE+GUESS design neatly exploits the problem’s structure—deterministic Lipschitz valuations, discontinuous GFT, and one-bit feedback—using geometric constraints to tame local regret and randomized price probing to quickly mark nodes.\n\n2, Tight regret bounds: The upper bound $\\tilde{O}(L·T^{(d−1)/d})$ with one-bit feedback and strong budget balance, plus the matching lower bound under full feedback, gives a compelling and crisp rate-optimal result in a challenging, nonparametric setting.", "weaknesses": "The most crucial issue that occurs to me is the dependence on exact Lipschitz structure (deterministic, noise-free L-Lipschitz f_s, f_b), which is central to both the algorithm and the regret analysis. However, it is not entirely clear how robust the guarantees are to even mild model misspecification (e.g., small additive noise, piecewise-Lipschitz with a few discontinuities, or approximate Lipschitzness with slack). The core REDUCE lemma (bounding future GFT by O(L·2^{−ℓ}) after two targeted rejections) drives the entire regret accounting across the tree, yet it relies critically on tight Lipschitz geometry and the absence of stochasticity in (s_t, b_t). In many practical bilateral trade scenarios, context-to-valuation mappings can exhibit small noise, context-specific irregularities, or Lipschitz violations near local kinks. Under such perturbations, the argument used to confine valuations “near the diagonal” after REDUCE may no longer hold with the same strength, potentially causing (i) GUESS to spend substantially longer at certain nodes, (ii) per-node regret to accumulate beyond the current bounds, and (iii) the overall O~(T^{(d−1)/d}) rate to degrade. While the paper’s setting is clearly stated and the results are strong within that model, this fragility leaves uncertain how well the approach carries over to slightly more realistic contexts where, for example, valuations incorporate measurement error, institutional frictions, or adversarial but small perturbations.\n\nBesides, some typos to notice:\n1, Line 079: “breaching” → “branching”?\n2, Line 461: “Ramark”\n3, Overall: “nonparametric” versus “non-parametric”", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)