A Parametric Contextual Online Learning Theory of Brokerage
Authors: François Bachoc
Tommaso Cesari
Roberto Colomboni
Venue: ICML 2025 poster (2025)
Keywords: bilateral trade
regret minimization
contextual online learning
theory
Primary area: theory->online_learning_and_bandits
TL;DR: We study a contextual version of online learning for brokerage

Abstract: We study the role of contextual information in the online learning problem of brokerage between traders.
In this sequential problem, at each time step, two traders arrive with secret valuations about an asset they wish to trade.
The learner (a broker) suggests a trading (or brokerage) price based on contextual data about the asset and the market conditions.
Then, the traders reveal their willingness to buy or sell based on whether their valuations are higher or lower than the brokerage price.
A trade occurs if one of the two traders decides to buy and the other to sell, i.e., if the broker's proposed price falls between the smallest and the largest of their two valuations.
We design algorithms for this problem and prove optimal theoretical regret guarantees under various standard assumptions.

A Parametric Contextual Online Learning Theory of Brokerage
François Bachoc' Tommaso Cesari?
Roberto Colomboni
Abstract
This setting is especially relevant for over over-the-counter (OTC) markets. Serving as alternatives conventional exchanges, OTC markets operate in decentralized manner and are vital part of the global financial system." In contrast to centralized exchanges, the lack of strict protocols and reg- ulations delegates to brokers the responsibility of bridging the gap between buyers and sellers, who may not have direct access to one another. In addition to facilitating interactions between parties, brokers leverage their contextual knowl- edge and market insights determine appropriate pricing for assets. By examining factors such as supply and demand, market trends, and other asset-specific information, brokers aim to propose prices that reflect the true market value of the asset being traded. This price discovery process is a crucial aspect of broker's role, as helps ensure efficient transactions by accounting for the unique circumstances sur- rounding each asset. Additionally, in many OTC markets, as in our setting, traders choose to either buy sell depend- ing on the contingent market conditions (Sherstyuk et al., 2020). This behavior is observed across broad range of asset trades, including stocks, derivatives, art, collectibles, precious metals and minerals, energy commodities like gas and oil, and digital currencies (eryptocurrencies).
We study the role of contextual information in the online learning problem of brokerage between traders. In this sequential problem, at each time step, two traders arrive with secret valuations about an asset they wish to trade. The learner (a broker) suggests a trading (or brokerage) price based on contextual data about the asset and the market conditions. Then, the traders reveal their willingness to buy or sell based on whether their valuations are higher or lower than the brokerage price. A trade occurs if one of the two traders decides to buy and the other to sell, i.e., if the broker's proposed price falls between the smallest and the largest of their two valuations. We design algorithms for this problem and prove optimal the- oretical regret guarantees under various standard assumptions.
1. Introduction
Inspired by a recent stream of literature (Cesa-Bianchi Bianchi et al., 2021; Azar et al., 2022; Cesa-Bianchi et al., 2024b; 2023; Bolić et al., 2024; Bernasconi al., 2024; Bachoc et al., 2024), we approach the bilateral trade problem of brokerage between traders through the lens of online learning. When viewed from a regret minimization perspective, bilateral trade has been explored over rounds of seller/buyer interac- tions with broker with no prior knowledge of their private valuations. Similarly to Bolić al. (2024), we focus on the case where traders are willing either buy sell (pos- sibly short; see Section 1.1), depending on whether their valuations for the asset being traded are above or below the brokerage price.
We propose contextual version of the online brokerage problem, that is of significant practical interest given that the broker often has access to meaningful information about the asset being traded and the surrounding market conditions before having to propose a trading price. This information might help the broker to propose more targeted trading prices by inferring (an approximation of) the current market value of the corresponding asset, and ignoring it could be extremely costly in terms of missing trading opportunities.
Although an extensive amount of work has been done on non-contextual bilateral trade problems (including broker- age problems), the existing literature on the more realistic contextual versions of these problems scarce (see Sec- tion 1.3). The main reason for the slower development of contextual results is the higher complexity of these settings and the impossibility of simply adapting non-contextual al-
'IMT and IUF, Université Paul Sabatier, Toulouse. France 'EECS. University of Ottawa, Ottawa, Canada DEIIB, Po- litecnico di Milano, Milano, Italy 'Department of CS, Uni- versità degli Studi di Milano, Milano, Italy. Correspondence to: François Bachoc ffrancoisbachhor Tommaso Cesari <toesari @uottawa.ca>, Roberto Colomboni Eroberto.colombonie @ polimi.tt>.
mathhanivv-oulouse.frr
"In the US alone, the value of assets traded in OTC markets exceeded remarkable 50 trillion USD in 2020, surpassing cen- tralized markets by more than 20 trillion USD (Weill, 2020). This growth has been steadily increasing since 2016 (www.bis.org 2022).
Proceedings of the nddd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

A Parametric Contextual Online Learning Theory of Brokerage
gorithmic ideas and analyses to their contextual counterparts. We aim to fill this gap in the online learning literature bilateral trade to guide brokers in these contextual scenarios.
51 E2, S2.... such that, for each N, it holds that B[G] = 0= B[G]] and V, my + & and W, my + G.
Contexts. We model the sequence of contexts C12 C2,... as a deterministic [0, -04llue sequence (possibly gener- ated by an adversarial environment with knowledge of the broker's algorithm) that is initially unknown but sequen- tially discovered by the broker. As a consequence, note that the sequence of market values m,, m2,, ... can change arbitrarily (and even adversarially) from one time step to the next.*
1.1. Setting
In the following, the elements of any Euclidean space are treated as column vectors and, for any real number z, V, we denote their minimum by z and their maximum by x y-
Online protocol. We study the following problem.
At each time e I,
Gain from trade and Regret. Consistently with the ex- isting bilateral trade literature, the reward associated with each interaction is the sum of the net utilities of the traders, known as gainfrom trade. Formally, for any p, U, w e [0, 1], the utility of a price when the valuations of the traders are v and w is
Two traders arrive with private valuations V,, W [0, 1] about an asset they want to trade.
The broker observes context Ct e [0,1]' and proposes a trading price P. E [0, 1].
The two bits I(P: s Vi), P[P S Wi) (i.e., the willing- ness of each trader to buy or sell) are revealed to the broker.
g(p, 2, w) =
UUV LVVWW-p + P HUA
buyer's gain seller's gain
trade happens
= ( u w) II A p uv wv
the price Pj lies between the lowest valuation VAA W and highest valuation V4, v W. (meaning the trader with the minimum valuation is ready to sell? at Pt and the trader with the maximum valuation is cager to buy at Po). the asset is bought by the trader with the highest valuation from the trader with the lowest valuation at the brokerage price P..
The aim of the learner is to minimize the regret with respect to the best not-necessarily--ineee linear function of the contexts," defined, for any time horizon T e N, as
IE Σ (FFT,
RT =
sup
pr: [0
Market value. At any time / E N, the context e related to the traders' valuations Ve, W; via the hidden market value of the asset: a number m, [0, 1] that satisfies the two assumptions below, which are assumed to hold throughout the whole paper.
where we let GFT,(p) = g(p, V2, W₂) for all p E [0. 1]. and the expectation is taken with respect to the randomness in (Et: (e) and, possibly, the internal randomization used to choose the trading prices (P.)
1.2. Challenges and contributions
The first assumption (Assumption 1.1) states that an un- known linear relation exists between the unknown market value m, and the corresponding context e, the broker ob- serves before proposing a trading price.
Under the assumption that the traders' valuations are un- known linear functions of d-dimensional contexts perturbed by zero-mean noise with time-variable densities bounded by
Assumption 1.1 (Market values and contexts). There exists áe [0, 1J4, unknown to the broker, such that, for each I. N, it holds that m, = c.
"We remark that we are not assuming that the two processes (Ee)se seN and (C)us are i.i.d., and in fact the distributions of these random variables may change adversarially over time.
*Note that, mathematically, being competitive against a se- quence of deterministic contexts is essentially the most general achievement that can be obtained, covering, in particular, the widespread and interpretable setting of i..d.. random contexts special case.
The second assumption accounts for variability due to per- sonal preferences or individual needs of the traders by mod- cling traders' valuations as pero-mean perturbations of the market values.
"Although the market value is linear function of the contexts, remark that it is not necessarily true that the price p that maxi- mizes the total expected gain from trade is also a linear function of the contexts, let alone that this function is the linear function that maps contexts to market values! One of the contributions of this work is to prove that this is true under the assumption that the noise distributions admit bounded densities (Lemma 2.1). but it becomes false when this assumption is lifted (Example 5.1).
Assumption 1.2 (Market values and valuations). There exists an independent sequence of random variables
We remark that in most markets, traders are allowed to sell assets they do not currently own (short-selling; see, e.g., the classic Black& & Scholes 1973). For this reason, do not need to assume that traders entering the market own unit the asset.
2

---

A Parametric Contextual Online Learning Theory of Brokerage
Bounded density
General
1.3. Related Works
2-bit feedback
VLT
T
Our work extends the recent research on online learning algorithms for bilateral trade, in particular, Cesa-Bianchi et al. (2021); Azar et al. (2022); Cesa-Bianchi et al. (2024b; 2023; 2024c); Bernasconi et al. (2024), for non-contextual problems where sellers and buyers have definite roles. The stochastic case, where sellers' and buyers' valuations are i.i.d across time, is studied in 2024b). They obtain a VT regret rate in the full-feedback setting. For the two-bit feedback case, they prove lin- car worst-case lower bound, but it turns out that tight regret rate of T2/3 is possible, by assuming independence and uniformly bounded density for the sellers' and buyers' valuations. The adversarial setting is the topic of several works, In the worst-case, it is unlearnable as shown in Cesa- Bianchi al. (2021: 2024b). Nevertheless, more favor- able results exist under various relaxations. Cesa-Bianchi et al. (2023; 2024c) consider the adversarial case where the adversary is forced to be smooth, i.e., the sellers' and buyers' valuation distributions are allowed to change adver- sarially over time, but these distributions admit uniformly bounded densities. In the full-feedback case, they prove a tight /T regret rate. In the two-bit feedback case, while the problem is still unlearnable, they allow the learner to use weakly budget-balanced mechanisms, yielding sur- prisingly sharp 73/1 regret rate. We remark that in all the two-bit feedback upper bounds requiring a bounded density assumption discussed above, there are no corresponding lower bounds with a sharp dependence on the density bound. Azar et al. (2022) consider the o-regret objective, weaker than the regret. In the full-feedback case, they prove a tight 2-regret rate of VT. In the two-bit feedback case, while learning is impossible in general, they allow the learner to use weakly budget-balanced balanced mechanisms, enabling to re- cover a 2-regret of order T3/4 No matching lower bound is provided. Bernasconi et al. (2024) further relax the notion of weak budget-balance by proposing the notion of global budget-balance Under global tight regret rate of /T in the full-feedback case, and regret rate of 33/4 in the two-bit feedback case, without matching lower bound.
Full feedback
LdhnT
T
Table I. Summary of our results.
some L, we make the following contributions (see Table for a summary).
et al. (2021;
1. We prove key structural result (Lemma 2.1) with two crucial consequences. First, Lemma 2.1 shows that posting the (unknown) market value as the trading price would maximize the expected gain from trade. 6 Second, it proves that the loss paid by posting a sub- optimal price is at most quadratic in the distance from the market value.
2. In our problem, the prices we post directly affect the two bits of information we retrieve (2-bit feedback). We note that this information so scarce that it is not even enough to reconstruct bandit feedback. We solve exploitation dilemma by proposing an algorithm (Algorithm 1) that decides to ei- ther explore or exploit adaptively, based on the amount of contextual information gathered so far, and prove its optimality by showing a v LLT In regret upper bound (Theorem 3.1) and a matching (up to Vin / LdT lower bound (Theorem 3.2).
this challenging exploration-exploitttion
3. To compare and contrast the impact of our realistic 2-bit feedback in online contextual brokerage, we in- vestigate the rates that could be achieved if the traders' valuations were revealed at the end of any interaction (full feedback); for this problem, we prove that the op- timal achievable rate is exponentially faster: of order Id T, by proving matching regret upper and lower bounds (Theorems 4.1 and 4.2).
they provide
4. Finally, we investigate the necessity of the bounded density assumption: by lifting this assumption, we show that the problem becomes unlearnable (Theo- rem 5.2), even under full feedback.
Gaucher et al. (2025) investigated a noisy linear contextual version of the bilateral trade problem, where the authors obtain a tight regret bound (up to logarithmic factors) the time horizon of order 2/2 under 2-bit feedback, with mis- matching dependence on the dimension and on the bounded density parameter in the lower bound. Even though their al- gorithm can be adapted to our setting (via the reduction that sets the seller's valuation as the minimum and the buyer's as the maximum of the traders' valuations), their regret guar- antees (that would anyway be worse than our /T) are lost because they require that, conditioned to the context, the seller is independent of the buyer, which is not the case
We stress that, in all our results, the dependence on all relevant parameters is tight. In contrast, as we discuss in Section 1.3, most related works on bilateral trade obtain (at best) matching dependence in the time horizon only.
'This implies, in particular, that in our contextual setting where market prices are functions of contexts, the benchmark in the regret definition is the total expected reward of the best arbitrary sequence of prices, a benchmark that would be unattainable in similar problems (like standard adversarial bandits). This is one of the many differences hetween contextual and non-contextual settings.
3

---

A Parametric Contextual Online Learning Theory of Brokerage
in the reduction because, in general, the minimum of two random variables is not independent of the maximum of the same two random variables.
Krause, 2019; Metevier al., 2019; Foster & Krishna-
murthy, 2018; Kannan et al., 2018; Oh & Iyengar, 2019; Hu et al., 2020; Neu & Olkhovskaya, 2020; Wei et al., 2020; Krishnamurthy et al., 2020; Luo et al., 2018; Krishnamurthy et al., 2021) is contextual linear bandits. In its standard form, at the beginning of each round, an action set is re- vealed to the learner, and the assumption is that the reward (which equals the feedback) is a linear function of the ac- tion selected from the action set. Instead, in our setting, the market price is a linear function of the context, while the rewards are linked to the price the learner posts by the non-linear gain from trade function. Moreover, in contrast to contextual bandits, in our 2-bit feedback model, the feed- back differs from and not sufficient to compute the reward of the action the learner selects at every round. For these reasons, existing theoretical results from contextual línear bandits do not directly apply to our problem. Nevertheless, note that techniques from contextual linear bandits are rel- evant to our problem, for instance, the use of the elliptical potential lemma (proof of Theorem 3.1).
The brokerage problem in online learning has been in- troduced by Bolić et al. (2024) in a simpler i...d. and non-contextual setting. There, the authors study the non- contextual version of our trading problem with flexible sell- ers' and buyers' roles, with the further assumption that the sellers' and buyers' valuations form an i.i.d. sequence. Un- der the M M-bounded density assumption, they obtain tight M I and v /MT regret rates in the full-feedback and two- bit feedback settings, respectively. If the bounded density assumption is removed, they show that the learning rate degrades to V in the full-feedback case and the problem turns out to be unlearnable in the two-bit feedback case. We remark that, interestingly. under the bounded density assumption, we are able to achieve the same regret rates in the contextual version of this problem without requiring that traders share the same valuation distribution, while, without the bounded density assumption, the contextual problem is unlearnable even under full feedback.
Previously to online learning contributions, a fair amount of literature addressed game-theoretic and best-approximation aspects of bilateral trade. We refer in particular to the landmark work of Myerson and Satterthwaite (Myerson & Satterthwaite, 1983), as well as Colini- Baliii- et al. (2016; 2017); Blumrosen & Mizrahi (2016); Brustle et al. (2017); Maini-Baldeschieeec et al. (2020); Babaioff et al. (2020); Dütting et al. (2021); Deng et al. (2022); Kang et al. (2022); Archbold et al. (2023). We also refer Cesa-Bianchh et al. (2024b) for an analysis of the references above.
The non-contextual brokerage problem has also been re- cently studied with different reward function aiming at maximizing the total volume of trades (Cesari & Colomboni, 2025).
Our linear assumption appears commonly in the literature on digital markets, particularly in problems like pricing and auctions. In Cohen et al. (2016; 2020), the authors first address deterministic setting, then a noisy one with known noise distribution where they obtain regret rate of order 22/3 without presenting lower bound. The deterministic case has also been investigated in Lobel et al. (2017; 2018); Leme& & Schneider (2018; 8: 2022); Liu et al. (2021).
Finally, we point out that Amin et al. (2013); Golrezaei et al. (2019) address pricing problems related to brokerage and bilateral trade, and account for strategic aspects in this context.
The case of noisy linear functions has been studied in Xu & Wang (2021); Badanidiyuru et al. (2023); Fan et al. (2024): Luo et al. (2024); Chen & Gallego (2021); Javanmard &
2. Structural and Technical Results
Nazerzadeh (2019); Bu et al. (2022); Shah et al. (2019) with guarantees limited to parametric or semi-pan eemi-parametric noise settings, while the recent work of Tullii et al. (2024) has given the first tight T2/3 analysis of the non- parametric noise case.
We begin by presenting structural result whose economic interpretation is as follows: even if the broker does not know the traders' valuation distributions, if these valuations can be modeled as zero-mean noisy perturbations with bounded densities of some market value, then the best price to post to maximize the expected gain from trade is precisely the (unknown and time-varying) market value, and the cost of posting a suboptimal price is at most quadratic in the distance from the market value.
The only work addressing contextual brokerage is Bachoc et al. (2025), which considers a con-aarmmttric variant of our setting and derives tight (albeit considerably slower) regret bounds. Notably, their Theorem 5, combined with our Theorem 3.1 and Theorem 4.1, yields 2-regret guarantees against oracle policies that know the traders' valuations before setting prices.
In particular, this generalizes similar result appearing in Bolić et al. (2024), which can be applied only under the further assumption that, at any time step, the traders' val- uations have the exact same distribution. We argue that this assumption might be overly strong and not capture real- life behavior. This is because traders might have private
Another rich related field explored in its many variants (Hanna et al., 2023; Slivkins et al., 2023; Leme et al., 2022; Foster et al., 2021; 2019; Zhou et al., 2019; Kirschner &
4

---

A Parametric Contextual Online Learning Theory of Brokerage
preferences or contingent needs that are not known by the broker; they could be more or less volatile, have differently skewed opinions, have valuations with arbitrarily different tail behavior, etc. Instead, we merely assume that, at any time step, traders' valuations are, on average, equal to the market price (which is how market prices are essentially determined real life) but allow for arbitrarily different (hidden and time-varying) distributions, This relaxation of the assumption comes at the expense of a more subtle proof. The mathematical reason for the added difficulty is that, under the dine-iittibuttinn assumption, many of the terms appearing in the proof simplify due to symmetries, while, in our case, a different approach is needed to recover all the properties needed for our result (which we are able to obtain without introducing any new assumptions).
that [[[]] = m, = 18 [. we also have, for each T N,
T
R = sup Σ
W.)l) (E[g(CTo, v..l
1-1
1N
1 [ 2. V2, W,) V.)
g(p, v2, W.)] P-
11
3
1 [LE[ - cl c
where the supremum in the first equality is over all func- tions p": [0, 1] + [0. 1]. (o) is directed consequence of Lemma 2.1, and (+) follows from the Freezing Lemma (Cesari & Colomboni, 2021, Lemma 8).
This structural result is the key to unraveling the intricacies of the noisy contextual setting, and it is what ultimately allows us to obtain tight regret guarantees in all settings, distinguishing ours from similar contextual bilateral trade and pricing works.
We conclude this section by presenting the following tech- nical lemma, which will be used in the analyses of our Algorithms and to control the behavior of the estimators we employ. Its proof deferred to Appendix A.2.
Lemma 2.1. Suppose that V and W are two [0, 1]-valued independent random variables, with possibly different den- sities bounded by some constant L 2 1, and such that E[V] = [[[] = m. Then, for each p E [0, 1]. it holds that
We write, for any E N, 1, for the i-dimensional identity matrix. Also, for any positive definite matrix A E R we define |-| ; H - [0, (o), u VeTAc.
Lemma 2.3. Let s, E N. Let Zi...., Ze be inde- pendent sequence of [0, 1]-valued random variables. Let A1....,0 0g E [O, Let vi E [0. 1]'. Suppose that, for each r E [>] it holds that E [[ a.V. Define Is = [ai ... a.l. Define H, == 121 ... Zz]. Define
0 B[g(m, V, -g,, V(P.V,)) LL L|mm- pl²
b. == (Jaf) + S Then, if [0. 1];, we have that
Due to space constraints, we defer the technical proof of this lemma to Appendix A.1.
El u.= a w/ | [
As an immediate corollary of Lemma 2.1, we obtain the following important result that upper bounds the regret in terms of the sum of the squared distances between the prices the algorithm posts and the actual market values.
3. Learning in Contextual Brokerage
Corollary 2.2. Consider the contextual brokerage problem introduced in Section 1.1. If the valuations admit densities bounded by constant L 2 1, then, for any time horizon T E N. we have
In this section, we introduce an algorithm (Algorithm I) for the contextual brokerage problem for which we prove regret guarantees of order ((TTT)).. 'he key feature of the algorithm's 's design is deterministic rule that decides to either explore or exploit based on the amount of information gathered along the various context directions (see the defini- tion of b, on Line 4). When the algorithm explores, it posts a price drawn uniformly in [o, 1] to obtain an unbiased esti- mate of the current market value. When it exploits, it posts the scalar product of the context and the current estimate of the unknown weight vector ó built using the information retrieved during exploration rounds.
Σ (GFT, -FTT((P))
Ry =
< Σ a -
Theorem 3.1. If the learner runs Algorithm 1 and the traders' valuations admit a density bounded by T, 1, then, for any time horizon T such that LT 2 it holds that Rr $ + G</TTIn'
Proof. Given that for each e N and each p [0, 1] it holds that GFT, (p) e [0, 1], we have su E (F).(p) -
GFT, (Pt)) & and hence, recalling that m, cf Φ and
5

---

A Parametric Contextual Online Learning Theory of Brokerage
Algorithm 1
Hence, leveraging Corollary 2.2 and the previous inequality, for any T N, we have that
1: Post P1 uniformly at random in [0, 1], and observe
D1 = I[P1 V/}
2: Let by = 1, let 21 == [c]] let Vi [1] and compute
RT S
Σ A
LE [PP
01 = [212] + d (111))
1=1
3: for time 1. = 2.3.... do
4: Observe context C2
and define
bp
$ Σ (1 b,) LE [|]] 10.T.-110 - o. c.00
be
I I| 2 if then
2dla(1+2d(T-1)
t=2
1=1
LT
L E (1 bi) |Vcc| ((,,
12
5:
$
147 (td-11a)
b
6:
Post P. uniformly at random in [0, 1J. and observe
t-2
D = T(Ps Vi}
$ 2LdT In(1 2d((T-111)
be
7: Let 2t [ c.). let Y = [Y Dr] and
2=1
compute oi == (arer) 1a)"'x;Y
where in the last step we used the definition of the .i..... by. Now, given that LTT (2d 2d(T 1))) 2 1, using the convention 0/0= 0.
8: else
9:
post Pt= = c and let x2 = I1-1, Y YL-
and de Φ1-1 Φ
10:
end if
b 2ea 2
11:
end for
Σ t-2
b
Σ 2-2
(1 m
|200
(1r (0 11.)
Proof. Without loss of generality we assume that T 2 2. Note that for any & N, if b, 1, then
LT
2d In +2)(T'
E[D.] = P[P. Vi] So² Plus du B[V] E[c + dd. (1)
Σ 1A b /2c, 1
T
(E:)) b.c,efe '1.)"
8-2
2LT
d'n(1 +22
Now, fix t 2. Let = Σ b; be the total number of exploration steps done before time step t. Define recursively time steps r(1),.... (s)) as follows: let r(1) 1 and, for all n E [s 1]. define T(n + 1) == min(i i E [t 1] | i (()) 1,b; 1}. Now, for each n E [s]. define 7n, == Dr(u)- Notice that Zı....,2 Z. are well defined because for
Σ Im 100-1 (E0,), E1
= (*).
Using the elliptical potential lemma (Lattimore & Szepesvári, 2020, Lemma 19.4), we obtain
each [s] we have that b,(m) 1. Define 1 === d. For
each E [s]. define an = Cr(x). Let &b == @ and == ct. Notice that, by Equation (1), if j [x] is odd, then E[Z,]] = E [[D+G)>] (()) o = a} e). Then, with the same notation of Lemma 2.3, we can apply Lemma 2.3 to obtain
T
Σ b, 11+(s) (x) 8-1
1 1 v
2d1n(1 2d(T- 1))
[[[c F[ ot [ B[[a" S. aT [1
= 1 + 2 2LdT 2d(T
s /2a E a1)))-111))
Hence, if d < T/2, this implies that R 1 3/2 In (1 + 22((T-1) 1)) s + 6/LdT On the other hand, if d T/2, then, since L we obtain, again, R2 S s 1 L.
2a
EEi Sonn 1d-1 "dd1)))
22c (z-12) nd -1)
We conclude this section by stating matching (up to log- arithmic terms) worst-case S2 ((vLdTT) regret lower bound for any algorithm, proving the optimality of Algorithm 1.
where the last step follows by definition of 21-1-
Being / arbitrarily chosen, we have that for each / E [T]
such that 2 2,
At a high level, the proof of this result is based on first build- ing a sequence of contexts defined as a common element of the canonical basis of IRd during each one of d blocks of
BllcT c]al3] |/22 12
(a-- td 11a)-1
6

---

A Parametric Contextual Online Learning Theory of Brokerage
T/d consecutive time steps. Then, in each block, we use non-contextual lower bound construction leading regret of at least / /dddd for each block, and conclude the proof by summing over blocks. For more details on the proof of this result, see Appendix C.2.
Theorem 4.1. Consider the full-feedback version of the
contextual brokerage problem. If the learner runs Algo- rithm 2 and the traders' valuations admit density bounded by L 2 1, then, for any time horizon T E N, it holds that Rt s + 4Ld
Theorem 3.2. There exist two numerical constants a, > such that, for any L 2 2 and any time horizon T 2 max(4, (4, adL3, 2d). there exists sequence of contexts cr E [0, such that, for any algorithu a for the contextual brokerage problem, there exists a vector E [[,, and two zero-mean independent sequences (Ee)aarr and (Ce) independent of each other such that, if we define Vi c o + Ee and We i= c, +++ + Çt. then for each L E [T] it holds that cf [0, 1], Ve and W, are [o, 1]-valled random variables with density bounded by L, and the regret of a on the sequence of traders' valuations V1, W,..W....,. Vr. Wr satisfies R 2 LdT.
Due to space constraints, we defer the proof of this result Appendix B.I.
We conclude this section by stating a matching worst-case Ω Id 7) regret lower bound for any algorithm in the full-feedback case, proving the optimality of Algorithm 2.
The result is proved similarly to that of Theorem 3.2: first, in each one of d blocks of TTd consecutive time steps, we play fixed context defined as a common element of the canonical basis of R Then, in each block, we use non- contextual lower bound construction leading to a regret of at least L (T/ for the block, and conclude the proof by summing over blocks. For more details on the proof of this result, see Appendix C.I.
We remark that the previous lower bound holds even for algorithms that have prior knowledge of the sequence of contexts C1 C2.... and that Theorem 3.1 shows that Algo- rithm matches the optimal VLTT rate (up to a VinT factor) even without this a-priori knowledge.
Theorem 4.2. There exist two numerical constants a. b b>0 O such that, for any L 2 2 and any time horizon T 2 max(4 (4, adI. 2d). there exists a sequence of contexts CI....,,T [0, 1j such that, for any algorithm a for the full-feedback version of the contextual brokerage problem, there exists vector & [0, 1]d and two zero-mean indepen- dent sequences (E)) and (Se)uetr independent of each other, such that if we define V₁ == cj Φ+ S, and W, = c. Çt. then for each t E [T] it holds that c| o [0, 1J. Ve and We are [O. 1] --valeedd random variables with density bounded by L, and the regret of a on the sequence of traders' valuations V1, Wi,..., Vr, WT satisfies Ry 2 bLdln T.
4. Full Feedback
In this section, we discuss a "full feedback" version of the contextual brokerage problem to understand how the limited feedback the broker has normally access to impacts the regret. In this version, the valuations Vi and W2 are revealed at the end of each time step i.
For this problem, we modify Algorithm 1 in two ways to leverage the higher-quality feedback. First, the new algo- rithm never explores (it does not need to), i.e., by == 0 for all t. Second, the algorithm uses different (and better) unbiased estimators of m, in the columns of Y;: the valuations V, and Wr The resulting algorithm is Algorithm 2, for which we prove an optimal logarithmic worst-case regret: an exponen- tial improvement with respect to what is achievable under the classic bit feedback.
We remark that the previous lower bound holds even for algorithms that have prior knowledge of the sequence of contexts c1, C2.... and that Theorem 4. shows that Algo- rithm matches the optimal Ln T rate even without this a-priori knowledge.
5. Beyond Bounded Densities
In this final section, we investigate the general case where the traders' valuations are not assumed to have a bounded density. We begin with the following (perhaps counterin- tuitive) counterexample showing that, in general, posting the market value can be highly suboptimal if the goal is to maximize the gain from trade.
Algorithm 2
1: Observe context C1, post Pi == 1/2, and receive feed- back 1/1 W1
2: Let 11 = [e] a)) let Y1 = [V] Wi), and compute
61 = [ + +d'
Example 5.1. Let V and W be two independent uniform random variables on {0, J. 1 and = [[V] E[W] 2/5. Then argmax [0]11]] Elg(p, V, W.] = 1/5 m. and (1(4/5,V,W)) -[(()))]](////0/////0 W)] V,
3: for time 1 = 2, do. do
4: Observe context ct. post P. = c7 Φ1-1, and receive
feedback V,, W.
= 2- -
5: Let F2 [x1-1 ce c. Y, = [ Vi Wi], and
compute d. = (x d d -1,,
The phenomenon illustrated by the previous counterexample is the key to proving our final result: the unlcarnability, in general, of the brokerage problem (even when full feedback
6: end for
7

---

A Parametric Contextual Online Learning Theory of Brokerage
is available). Specifically, we exploit the fact that, in general, the optimal price time & depends not only on the market value m, cl but also properties of the adversarial and time- time-varying distributions of the perturbations & and Çt. which make it impossible to compete against the benchmark in our regret definition.
pairs (V1,,; W1, and (V12,0, W12,0) share the same dis- tribution for every 11 e N. Fix a learning algorithm for the full-feedback contextual brokerage problem, fix a time horizon T E N, and notice that since the contexts C1, C2,... are all distinct, it follows that
T M
Theorem 5.2. There exists a sequence of contexts C2, [O. 1]dh and vector de [0, 10,, such that for any algorithm for the full-feedbuck version of the contextual brokerage problem, there exists an independent sequence of zero mean random variables Ét, Si,E2, S2...., such that if the valuations of the traders at time t are V. = c o + & and W. = c/ + St, then c E [0, 1], V4, Wr are [0, 1]- valued random variables, and the regret of a on the se- quence of traders' valuations V1, Wi,..., Vr, Wr satisfies RT T..
max 0 01.-0000r(00111 p p=:00.1s--00.1
sup
B
max 0 (0,,117
sup pe[o.1]
E - (#)
max 9 1....00
Now, consider an i.idd family of Bernoulli random variables (ot)tess with parameter 1/2, independent of the whole fam- ily (Vi,, We,0 (0.. We have that
We remark that the previous unlearnability result holds even for algorithms that have prior knowledge of the se- quence of contexts 01. Cg.... and, strikingly, of the vector o, that is, even for algorithms that know the entire sequence m1, m..... of market prices in advance!
T (#)
(p (p.) (P))) (S))
[E
2 1-1
Now, for each t [T]. we see that
Proof. Assume that d 2 2 (for the case d 1, the following proof can be adapted straightforwardly by defining o and c 1/2+ + 5t, where 5 is an arbitrary small sequence of biases). Let (eN)ee leN be a sequence of distinct elements in [0, 1] and, for all t e N. let C == (at, 1 1- de, 0, .........)). 0).
E (p* (p)))))
= E B G (e.())) [.]
E
max
E
G
(p) 6.]]
Notice that (c))eN is a sequence of distinct elements in 1.4 Define o= == 1/2, 0, ......),, 0). Notice that for each t N it holds that cj Ø 1/2. Let (0, 1/16). For any 0c {0, 1), consider the following probability distribution
p=[0,1]
and long but straightforward computations show that, for each p E [0, 1]. it holds that the conditional expectation e G (p) O, is equal to
(1 (1-2(()) 0z pa- = G1 + (1 - -0) e) 6-3 + |0) + (
where f(0)= == 2(1 - 0) 200 and for any a E R. 8a is the Dirac's delta probability distribution centered in a. Consider an independent family of random variables (Er.0. (1.9)sen,ee such that for any t é N and any 0 (0.1), 1}. we have that both c and Go, are random variables with common distribution μo. Notice that for each e N and each 0 {0, 1) we have that [[ 0 [. Define, for each t N and each 0 E {0, 1}, the ran- dom variables Vz. = cc Eι,0 and W., = cT Ce.-- Notice that these are 10valud random variables and that (Vi,,, We,o)eeN.Be(o.z. is an independent family. Now, for each 0 e {0,1) and each t E N. let p (p) = {(,, Ve,, We,) and
i (+=(1-20)
- if 1 2(1 if - + +)(1
3 +
- - 20))
from which it follows that
G (p) [0 (p) pe
3 +
max
On the other hand, for each t [T]. leveraging the freezing lemma (Cesari& & Colomboni, 2021, Lemma 8), we have that
p#)) argmax 10 [[)
0 [P))
[LC (+] p.
which does exist because the function [0,1] + 10,1),7*
B G (p)] is upper semicontinuous (this can be proved, c.g., as in Desa-Bianchi et al. 2024b, Appendix B) and defined on a compact set. Furthermore, note that the previous def-
[ 0] + 0 = 11] P.
1
inition is independent of t because, for any E (0, 1), the
and again, tedious but straightforward computations show
8

---

A Parametric Contextual Online Learning Theory of Brokerage
that, for each p [0. 1], it holds that
by the MUR PRIN grant 2022EKNE5K (Learning in Mar- kets and Society), the FAIR (Future Artificial Intelligence Research) project, funded by the NexIGenerationEU pro- gram within the PNRR-PE-AN scheme, the EU Horizon 144-202-HHUMAN
| ()) 0] { 1]
=
research and innovation action un- der grant agreement 101 101120237, project ELIAS (European Lighthouse of Al for Sustainability).
+ ((++++)))((===+
+1pp== 25))
+ -
$ 3 16 +
Impact Statement
We conclude that ($) 2 T6 - - T'z 32.
I from which
it follows that there exists 01: ................................ f1 {0,1} such that
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
sup
E
Σ
Go -G
(P))
T
x: [=00.1]--00.1]
32
6. Conclusions
References
Amin, K., Rostamizadeh, A., and Syed, U. Learning prices for repeated auctions with strategic buyers. Advances in neural information processing systems, 26, 2013.
Motivated by the real-life desideratum to exploit prior infor- mation the traded assets, we investigated the noisy linear contextual online learning problem of brokerage between traders without predetermined seller/buyer roles. We pro- vided a complete picture with tight regret bounds in all the proposed settings, achieving tightness (up to log terms) in all relevant parameters.
Archbold, T., de Keijzer, B., and Ventre, C. Non-obvious manipulability for panleeparramter agents and bilateral trade. In Proceedings of the 2023 International Con- ference on Autonomous Agents and Multiagent Systems, pp. 2107-2115, USA, 2023. International Foundation for Autonomous Agents and Multiagent Systems.
Our work stands on the classic interpretation of the mar- ket value of asset the average opinion of the market participants. An alternative perspective, which we leave open for future research, is when, instead, assets have an "inherent value", and traders' valuations are systematic bi- ases or strategic deviations around this quantity. In this case, this inherent value would not the average of the traders' valuations, and new techniques will be required to analyze this setting.
Azar, Y., Fiat, A., and Fusco, F. An alpha-regret analy- sis of adversarial bilateral trade. Advances in Neural Information Processing Systems, 15:5668-1697, 2022.
Babaioff, M., Goldner, K., and Gonezarowski, A. Bulow- Klemperer-style results for welfare maximization in two- sided markets. In Proceedings of the Thirty-First Annual ACM-SIAMM Symposium Discrete Algorithmss, SODA '20, pp. 2452-2471, USA, 2020. Society for Industrial and Applied Mathematics.
Finally, we highlight that there are many other online learning problems in digital markets whose contextual ver- sion is still open, such as market making (Cesa-Bianchi et al., 2025), first-price auctions with unknown costs (Cesa- Bianchi et al., 2024a), trading-volume maximization (Cesari & Colomboni, 2025), and optimal taxation (Cesa-Bianchi al., 2025).
Bachoc, F., Cesa-Bianchi, N., Cesari, T., and Colomboni, R. Fair online bilateral trade. In Globerson, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomczak, J., and Zhang, C. (eds.), Advances in Neural Information Pro- cessing Systems, volume 37, pp. 37241-37263. Curran Associates, Inc., 2024.
Acknowledgements
The work of FB was supported by the Project GAP (ANR- 21-CE40-0007) of the French National Research Agency (ANR) and by the Chair UQPhysAI of the Toulouse AN- ITI AI Cluster. TC gratefully acknowledges the support of the University of Ottawa through grant GR002837 (Start- Up Funds) and that of the Natural Sciences and Engi- neering Research Council of Canada (NSERC) through grants RGPIN-2023-0320 (Discovery Grants Program) and DGECR2023-0022 -02088 (Discovery Grants Program, DGECR Discovery Launch Supplement). RC is partially supported
Bachoc, F., Cesari, T., and Colomboni, R. A tight regret analysis of non- non-parametric repeated contextual broker- age. In Li, Y., Mandt, S., Agrawal, S., and Khan, (eds.), Proceedings of The 28th International Conference Artificial Intelligence and Statistics, Proceedings of Machine Learning Research. PMLR, 03-05 May 2025.
Badanidiyuru, A., Feng, Z., and Guruganesh, G. Learning to bid in contextual first price auctions. In Proceedings of the ACM Web Conference 2023, pp. 3489-34999 -499, 2023.

---

A Parametric Contextual Online Learning Theory of Brokerage
Bass, R. F. Real analysis for graduate sludents. Createspace Ind Pub, USA, 2013.
Cesa-Bianchi, N., Cesari, T., Colomboni, R., Fusco, F,, and Leonardi, S. Regret analysis of bilateral trade with smoothed adversary. Journal of Machine Learning Research, 25(234): 2024c.
Bernasconi, M., Castiglioni, M., Celli, A., and Fusco, F. No- regret learning in bilateral trade via global budget balance. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024.
Cesa-Bianchi, N., Cesari, T., Colomboni, R., Foscari, L., and Pathkk, V. Market making without regret. In Pro- ceedings of Thirty Eighth Conference on Learning The- ory, volume 291 of Proceedings of Machine Learning Research, pp. 799-837. PMLR, 2025.
Black, F. and Scholes, M. The pricing of options and cor- porate liabilities. Journal of political economy, 81(3); 637-654, 1973.
Cesari, T. and Colomboni, R. An online learning theory of mading-vvluume maximization. In The Thirteenth Interna- tional Conference Learning Representations, 2025.
Blumrosen, and Mizrahi, Y. Approximating fains-froms trade in bilateral trading. In Web and Internet Economics, WINE" 16, volume 10123 of Lecture Notes in Computer Science, pp. 400-413, Germany, 2016. Springer.
Cesari, T. R. and Colomboni, R.
nearest neighbor characterization of Lebesgue points in metric measure spaces. Mathematical Statistics and Learning, 3(1):71- 112, 2021.
Bolić, N., Cesari, T., and Colomboni, R. An online learning theory of brokerage. In Proceedings of the 23rd Interna- tional Conference on Autonomous Agents and Multiagent Systems, AAMAS 224, pp- 216-224, Richland, SC, 2024. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 9798400704864.
N., Colomboni, R., and Kasy, M. Adaptive maximization of social welfare. Econometrica, 93(3):
1073-1104, 2025.
Brustle, J.. Cai, Y., Wu, F., and Zhao, M. Approximating gains from trade in two-sided markets via simple mech- anisms. In Proceedings of the 2017 ACM Conference on Economics and Computation, EC 11, pp. 589-590, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450345279.
Chen, N. and Gallego, G. Nonparametric pricing analytics with customer covariates. Operations Research, 69(3): 974-984, 2021.
Cohen, M. C., Lobel, I., and Paes Leme, R. Feature-based dynamic pricing. In Proceedings of the 2016 ACM Con- ference on Economics and Computation, pp. 817-817, 2016.
Bu, J., Simchi-Levi, D., and Wang. C. Context-based dy- namic pricing with partially linear demand model. Ad- vances in Neural Information Processing Systems, 35: 23780-23791, 2022.
Cohen, M. C., Lobel, I., and Paes Leme, Feature-based dynamic pricing. Management Science, (6(11) 4943, 2020.
Cesa-Bianchi, N., Cesari, T. R., Colomboni, R., Fusco, F., and Leonardi, S. A regret analysis of bilateral trade. In Proceedings of the 22nd ACM Conference on Economics and Computation, pp. 289-309, USA, 2021. Association for Computing Machinery.
Colini- R., de Keijzer, B., Leonardi, S., and Turchetta, S. Approximately efficient double auctions with strong budget balance. In ACM-SIAM Symposium on Discrete Algorithms, SODA 16, pp. 1424-1443, USA, 2016. SIAM.
Cesa-Bias Cesa-Bianchi, N., Cesari, T. R., Colomboni, R., Fusco, F. and Leonardi, S. Repeated bilateral trade against smoothed adversary. In The Thirty Sixth Annual Con- ference on Learning Theory, pp. 1095-1130, USA, 2023. PMLR.
Colini-Baldeschi, R., Goldberg, P. W., de Keijzer, B., Leonardi, S., and Turchetta. S. Fixed price approxima- bility of the optimal gain from trade. In Web and In- ternet Economics, WINE' 17, volume 10660 of Lecture Notes in Computer Science, pp. 146-160, Germany, 2017. Springer.
Cesa- Bianchi, N., Cesari, T., Colomboni, R., Fusco, F., and Leonardi, S. The role of transparency in repeated first-price auctions with unknown valuations. In Proceed- ings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pp. 225-236. Association for Computing Machinery, 2024a. ISBN 9798400703836.
R., Goldberg, P. W., Keijzer, B. d., Leonardi, S., Roughgarden, T., and Turchetta, S. Approx- imately efficient two-sided combinatorial auctions. ACM Transactions on Economics and Computation (TEAC), 8 (1):1-29, 2020.
Cesa-Bianche N., Cesari, T., Colomboni, R., Fusco, F,, and Leonardi, S. Bilateral trade: A regret minimization perspective. Mathematics of Operations Research, 49(1): 171-203, 2024b.
Deng, Y., Mao, J., Sivan, B., and Wang. K. Approximatell efficient bilateral trade. In STOC, pp. 718-721, Italy, 2022. ACM.
10

---

A Parametric Contextual Online Learning Theory of Brokerage
Dütting, P., Fusco, F., Lazos, P., Leonardi, S., and Reiff- enhäuser, R. Efficient two-sided markets with limited information. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pp. 1452-1465, New York, NY, USA, 2021, Asso- ciation for Computing Machinery. ISBN 9781450380539.
Kannan, S., Morgenstern, J. H., Roth, A., Waggoner, B., and
Wu, Z. S. A smoothed analysis of the greedy algorithm for the linear contextual bandit problem. Advances in Neural Information Processing Systems, 31, 2018.
Kirschner, J. and Krause, A. Stochastic bandits with context distributions. Advances in Neural Information Processing Systems, 32, 2019.
Fan, J., Guo, Y., and Yu, M. Policy optimization using semiparametric models for dynamic pricing. Journal of the American Statistical Association, 119(545):522-664 2024.
Krishnamurthy, A., Langford, J., Slivkins, A., and Zhang, C. Contextual bandits with continuous actions: Smoothing, zooming, and adapting. Journal of Machine Learning Research, 21(137):1-44 2020
Foster, D., Rakhlin, A., Simchi-Levi, D., and Xu, Y. Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement- perspec- tive. In Conference on Learning Theory, pp. 2059-2059. PMLR, 2021.
Krishnamurthy, A., Lykouris, T., Podimata, C., and Schapire, R. Contextual search in the presence of ir- rational agents. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 910- 918, 2021.
Foster, D. and Krishnamurthy, A. Contextual bandits with surrogate losses: Margin bounds and efficient algorithms. Advances in Neural Information Processing Systems, 31, 2018.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
Leme, R. P. and Schneider, J. Contextual search via intrin- sic volumes. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 268-282. IEEE, 2018.
Foster, D. J., Krishnamurthy, A., and Luo, H. Model selec- tion for contextual bandits. In Wallach, H., Larochelle, H., Beygelzimer, A., d' d'Alché- Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Leme, R. P. and Schneider, Contextual search via intrinsic volumes. SIAM Journal on Computing, 51(4):1096 1125, 2022.
Gaucher, S., Bernasconi, M., Castiglioni, M., Celli, A., and Perchet, V. Feature-based online bilateral trade. In The Thirteenth International Conference on Learning Representations, 2025.
Leme, P., Podimata, C., and Schneider, J. Corruption- robust contextual search through density updates. In Conference on Learning Theory, pp. 3504-3505. PMLR, 2022.
Golrezaei, N., Javanmard, A., and Mirrokni, V. Dynamic incentive-aware learning: Robust pricing in contextual auctions. Advances in Neural Information Processing Systems, 32, 2019.
Liu, A., Leme, R. P., and Schneider, Optimal contextual pricing and extensions. In Proceedings of the 2021 ACM- SIAM Symposium on Discrete Algorithms (SODA), pp. 1059-1078. SIAM, 2021.
Hanna, A., Yang, L., and Fragouli, C. Contexts can be cheap: Solving stochastic contextual bandits with linear bandit algorithms. In The Thirty Sixth Annual Conference on Learning Theory, pp. 1791-1821. PMLR, 2023.
Lobel, I., Paes Leme, R., and Vladu, A. Multidimensional binary search for contextual decision-making In Pro- ceedings of the 2017 ACM Conference on Economics and Computation, pp. 585-585, 2017.
Hu, Y., Kallus, N., and Mao, X. Smooth contextual ban- dits: Bridging the parametric and non-differentiable re- gret regimes. In Conference on Learning Theory, pp. 2007-2010. PMLR, 2020.
Lobel, I., Leme, R. P., and Vladu, A. Multidimensional binary search for contextual decision-making Operations Research, 66(5): 1361, 2018.
Javanmard, A. and Nazerzadeh, H. Dynamic pricing in high-dimensions. Journal of Machine Learning Research, 20(9):1-49) 2019.
Luo, H., Wei, C.-Y., Agarwal, A., and Langford, J. Ef- ficient contextual bandits in non-stationary worlds. In Conference On Learning Theory, pp. 1739-1776. PMLR, 2018
Kang, Z. Y., Pernice, F., and Vondrák, J. Fixed-price approx- imations in bilateral trade. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2964-2985, Alexandria. VA, USA, 2022. SIAM, Society for Industrial and Applied Mathematics.
Luo, Y., Sun, W. W., and Liu, Y. Distribution contextual dynamic pricing. Mathematics of Operations Research, 49(1):599-618 2024.

---

A Parametric Contextual Online Learning Theory of Brokerage
Metevier, B., Giguere, S., Brockman, S., Kobren, A., Brun, Y., Brunskill, E., and Thomas, P. S. Offline contextual bandits with high probability fairness guarantees. Ad- vances in Neural Information Processing Systems, 32, 2019.
Zhou, Z., Xu, R., and Blanchet, Learning in generalized linear contextual bandits with stochastic delays. Advances in Neural Information Processing Systems, 32, 2019.
Myerson, R. B. and Satterthwaite, M. A. Efficient mecha- nisms for bilateral trading. Journal of Economic Theory, 29(2):265-281, 1983.
Neu, G. and Olkhovskaya, J. Efficient and robust algorithms for adversarial linear contextual bandits. In Conference on Learning Theory, pp. 3049-3068. PMLR, 2020.
Oh, M.-h. and Iyengar, G. Thompson sampling for multi- nomial logit contextual bandits. Advances in Neural Information Processing Systems, 32, 2019.
Shah, V., Johari, R., and Blanchet, J. Semi- parameeraettic dynamic contextual pricing. Advances in Neural Infor- mation Processing Systems, 32, 2019.
Sherstyuk, K., Phankitnirundom, K., and Roberts, M. Randomized double auctions: gains from trade, trader roles, and price discovery. Experimental Economics, 24 (4):1-40, 2020.
Slivkins, A., Sankararaman, K. A., and Foster, D. Con- textual bandits with packing and covering constraints: A modular Lagrangian approach via regression. In The Thirty Sixth Annual Conference on Learning Theory, pp. 4656. PMLR, 2023.
Tullii, M., Gaucher, S., Merlis, N., and Perchet, V. Im- proved algorithms for contextual dynamic pricing. In Globerson, A., Mackey, L., Belgrave, D., Fan, A., Pa- quet, U., Tomezak, J., and Zhang, C. (eds.), Advances in Neural Information Processing Systems, volume 37, pp. 17. Curran Associates, Inc., 2024.
Wei, C.- Y., Luo, H., and Agarwal, A. Taking hint: How to leverage loss predictors contextual bandits? In Conference Learning Theeory pp. 3583-36344 PMLR, 2020.
Weill, P.O. The search theory over-the-counter markets. Annual Review of Economics, 12:747-773, 2020.
Williams, D. Probability with martingules. Cambridge university press, UK, 1991.
www.bis.org, OTC derivatives statisties end-June 2022. Bank for International Settlements, 2022, URL ht tps: w/www.... bis org/ / http://uloooocccpeeeeee hypttcchhh2__11_ pdf.
Xu, J. and Wang, Y.-.. Logarithmic regret in nature-bbsed dynamic pricing. Advances in Neural Information Pro- cessing Systems, 34:1 13898-13910,, 2021.
12

---

Parametric Contextual Online Learning Theory of Brokerage
A. Missing Proofs of Structural and Technical Results (Section 2)
In this section, we provide the missing proofs of our structural and technical results.
A.1. Proof of Lemma 2.1
We denote by F (resp., G) the cumulative distribution function of V (resp., W). For each pe [0, 1], from the Decomposition Lemma in (Cesa-Bianchi et al., 2024b, Lemma 1), it holds that
[V F(r) (1-C(A))
J, F(A)dA,
[[V-W)][ (1- f." G())d..
Hence, for each pe [0, 1].
P[(w-v)ll sps sps W/]] (pSW]]=F() (, [" F(A)da
= =F(p) m- [ [(FA))dA- [." F(A)dX
=f"" (m-))) (.---A)))) (1==F()) (- G()
Sf" (" G(D) (m- (1- + (1- 11) 1) So a( ((CD) f, (1--F(A)) dx (1-F()) S. G(s)as))
[" (M)))))))= JU
[[ + (F++)()))++ (f - (V-W)I(W sys]]s
Rearranging, it follows that, for each p [0,1]
B[g(o, V. W)] E - sps v}]
= S.² (F
Hence, for any e [0, 1], holds that
E[g(m, V. - s(p. v.w]]= (") AA))
Finally, since and G are absolutely continuous with weak derivative bounded by L, by the fundamental theorem of calculus (Bass, 2013, Theorem 14.16) it holds that, for p [0, 1].
E [[g,m (3(m,Vvw) - g(p, V.)]= S," f((F'')) ()))) (0)+)(()) f(m dA L/m - pp?
p/dd
A.2. Proof of Lemma 2.3
By the birs-variance decomposition:
E la T di. a [T/p]= (F(a a "w)))²
Var[a [h.)
bias
Noting that, for each & N. it holds that [[H;] = f tb, we have,
E[a G4 a aTxb] wb] (f.S + +111
-a +
13

---

A Parametric Contextual Online Learning Theory of Brokerage
and hence, by the Cauchy-Schwarz inequality applied to the scalar product (a, B) a² (fafg + +111)) by the fact that (SsJ +1) 17' (where, for any symmetric matrices A1, A2, say that A A2 if and only if A2 A is semi-positive definite), and by the fact that || I, we can control the bias term as follows
(B[a S. - a v1) (o)2
s sa (Sof. + 11) (T.f + -11
sa' (a'ss + + 11
$ sa (fasz 11)
Letting A, be the x diagonal matrix with vector of diagonal elements given by (Varl Zi]...., Varl Var[ we have Var[a vb.] = a' (f.f.
Now, given that Zi....,
, Zg are [0. 1]-valued, we have that Ag diagonal with diagonal elements less than 1, and hence L.A.f. Sest +1- which yields a control on the variance term as follows,
Varla [. s a "Saf" + (1"11"""aaa I + 11)
= =a (fof. + +1)
Putting everything together, we have
E &5 - a' w1 2a (fafz 11) 2| (1
=2llal 22 a
||[ (Een (.a
where recall that for any positive definite matrix A e (R and each Re, we have defined ||u]|A Vui Au.
B. Missing Upper Bound Proofs
In this section, we provide all missing proofs our regret upper bounds.
B.1. Proof of Theorem 4.1
Fix any t 2 2. Now, for each n é [t-1], define Zen-1 == Vn and Zen == W,. Define / := d and s 2(t-1). For each E [t-1], define 02n-1 == en =i 42n. Let 1b == @ and a == с. Notice that, if [s] is odd, then [EV=g]] بيا Φ aj v. while
aJv. Hence, we apply Lemma 2.3 obtain j [8] is even, then E[2,] E W #
E[cc_0-11 -c d] E[la" -
(Σ aajaaa)) a [ || 2
12c (2 coc))tr-11)))
||[ (v..
Hence, leveraging Corollary 2.2 and the previous inequality, for any T N, we have that
R 5 Σ ia [E [. c))l)) $ 1 +
Σ
LE Ic] 1c s1 Σ 2c 2
(EE) (VZo X
[=1
2-
1-2
ddt 2d(TT +dd(T'
11+ 2n
2Ldln 2d(T (1 s 1 2Ld
dd
where the first inequality of the second line follows from the elliptical potential lemma (Lattimore & Szepesvári, 2020, Lemma 19.4).
< T/2, this implies that Ry $ 1 (2dI) s 1 In.. If, instead, d2 T/2, then, recalling that 2 1, we obtain once again that Ry 1 4Td concluding the proof.
14

---

A Parametric Contextual Online Learning Theory of Brokerage
C. Missing Lower Bound Proofs
In this section, we provide all the missing proofs of our lower bounds, starting from that of the full-feedback setting.
C.1. Proof of Theorem 4.2
The high-level idea of this proof is to build a reduction to a non-contextual full-feedhack lower bound construction (see, e.g., the one appearing in Bolić et al. 2024, Theorem 5).
Without loss of generality, we assume that d divides T. In fact, if we prove the theorem for this case, then, by leveraging that 7 2 2d and T 4, the general case follows from
Rr 2 bLdIn((T/ddd) Ld
Let T/d. Let E1,..., Ed be the canonical basis of IR Define, for all i [d] and j E [n]] the context Oj+(i-1)n =; We assume that these contexts are known to the learner in advance and, therefore, we can restrict the proof to deterministic algorithms without any loss of generality.
Let L 2 2, Jz = [ 14T. 2- + T47. f = 40.21 + L + [[4.1]. and, for any [-1,1], 9: == [+ ( (
(
and f= f + Ic- For any E [-1,1], note that s fz s L and So f=(x) dx hence fe is valid density [o, 1] bounded by L. We will denote the corresponding probability measure by Ves set D. == [ x dw), and notice that direct computations show that D3 = + < Consider for each q [o, 1]. an i.i.d. sequence (Bg,t) ).N of Bernoulli random variables of parameter g, i..dd sequence (B, )eN of Bernoulli random variables of parameter 1/7, an i..d. sequence (U)) of uniform random variables on [0, 1J. and uniform random variables E,...., on [_ Er.J where é := 7. such that ( (eNg,))e...e(o...
196
tat), (Ut)seN, Fi,...; Fea) an independent family. Let yo: [0. 1] + [0, be such that, if U is uniform random variable on [o, 1]. then the distribution of (UU) has density f [1..1] (which exists by the Skorokhod representation theorem (Williams, 1991, Section 17.3)). For each E [-1, and t e N, define
2 Ur (1 Ge = 12+ 14
Bige (1-B 3+ Buy., B. (())((())
2)
Gr.2.. Ec,t Ve,e- Dc, and Ce,t We,- ue. In the following, if a1,-.... ag is a sequence of elements, we will use the notation aid as shorthand for (ai,..., ag)). For each EI...., Ed [-1, each i [d], and each j e [n]. define the random variables goud (j+(l-1)n == (i-)- and chuu Sj-(i-1)n (i,j+(i-1)a- The family (5f S. cELd [e[TT is an independent family, independent of (E1...., Ea), and for each e [d] and each j [n] it can be checked that the two random variables Sj+(i-1)m 5 Sj-(1-1)n are zero mean with common distribution given by Pe,- For each 6I, e
Ve, = Gr,21-1, 2e,t1, We,:
[],, let PELe == (Dei PE.), and for each i [d] and j [n]. let V j+(i-1)n (i-n-)) PEus + gfia Sj+(i-1)n and Welt j+(i-1)n == (-((i-1) SELa + Cond {ja(i-I)n' Note that these last two random variables are [0, 1]-valued zero-mean perturbations of of (-(1-1)n with shared density given by fe.. and hence bounded by L.
We will show that any algorithm has to suffer the regret inequality in the statement of the theorem if the sequence of evaluations is Vi Wf ..... Vese, Ward for some Ea. e {[0, 1].
Before doing that, we first need the following. For any , ea [-1, p [o, 1]. and t [T] let GFT," (p) g(p, Veeu Wend).
By Lemma 2.1, we have, for all Ed. 6 [-1,1],ie [d],j é [n]. and p [0.
E GFT (x) =2 S." (s) dsdd + 2(U,, p) S." (s)
which, together with the fundamental theorem of calculus -Bass,, 2013, Theorem 14.16), noting that -
E GF (-(i-))n (p)] is absolutely continuous with derivative defined a.c. by p + 2( - P) (p) yields, for any
p peJ Jz.
GFT
j-(i-1)n (ve.) GFT (t(--))) (r)] Llue, pp2
(3)
Note also that for all e Ea é [1E,, te [T], and p E [o, 1] Jz. a direct verification shows that
E (p)] s E EGGFT (1/2)]
(4)
15

---

A Parametric Contextual Online Learning Theory of Brokerage
Fix any arbitrary deterministic algorithm for the full feedback setting (0r)) i.e., (given that the contexts C1 Cr are here fixed and declared ahead of time to the learner), sequence of functions ay: (Io, 1] x [0, 1]) f-1 + +[0, 1] mapping past
feedback into prices (with the convention that a just a number in [o, I]). For each / e [T]. define az: ([0, x]x 1]) 4-1
Jr. equal to di whenever or takes values in Jr. and equal to 1/2 otherwise. Define Zi = L+ Za L+
Now, note the following
sup E1,
I.
GFT
j+(i-1)m (Dc,))
GFT
j+(i-1)n (Vr WT ..... Veld Wind (i+ )-1+((-1)n))
j=1
d Σ Σ
sup
GFT
j-((-))n (Fa.)
GFT fa(--)) (āx( wF V (-) (-1((()))))))
W
1-1 3-1
d n
L
sup
ΣΣ ==1
b
De. - ao(Ve Wind
Vend j-1+(i-1)n) W
d
L Σ
Σ
E
Dgg āz (VyEiu, W.Eua
V VLd
(+)(())))) Whus
i-1j=1
d n Σ ==1
Σ
/E. - FEg
Bua W
(-1+((-1)m) 8- 11
Whin
L
d n
E
F3
F F3
V WFan
Bia f-1+((-1)m W 1-1-(1-1)n 11
1962
=1
L
d
I8 -
BLE&| Bugg,1220-))0 1-2(111)n Bug 20 20-1))2(1)))
1962
L
d
n
Bus
B Brg 2 2011)
1962 -1
L
d
Σ
Σ
E[Z
98
1-1
where follows from (3) and the fact that ãr takes values in Jz: from the fact that the minimizer of the (P(PP)distane from Fg. in (V, e.g., (Williams, 1991, Section 9.4)); follows from the fact that, by Equation (2) and the independence of E, from
End Wf ..... (-1+(i-))n W j-1s(i-1)n) is 13 [E, VVEia,, W.Biss ....,
Ens
End (-1+ W Ens
j- (1- 1)m (see,
(ex,.)) (B:) (B))IeN) (Ut)tan). ), the conditional expectation E E vi W WFEu. ..... V.E (-1=(i-))m* W Eng j-1-(i-1)a 1)o. is
measurable function of B1s5, (42((-)))"" Bu. (((-)))=(((1)))) together with the same observation made in about the
minimization of (IP distance; and + follows from the fact that the sequence (Bi-f..) LeN
is i.i.d.
Finally, the general term of this last sum is the expected squared distance between the random parameter (drawn uniformly
over [(1 - EL) /2. (1 + É 2)2) of an i.i.d. sequence of Bernouli random variables and the conditional expectation of this
random parameter given 2(j - 1) independent realizations of these Bernoullis. A probabilistic argument shows that there exist two universal constants à, b > 0 such that, for all j 2 dI.4 and each i [d].
E Zg - E[2, B2.1...... B2 11 ²a 1
(5)
j-1
At a high level, this is because, in an event of probability Q(1), if j is large enough, the conditional expectation B[Z, Bz.,...., B2.2((-1)) is very close to the empirical average スリ-1 Σ Bz... whose expected squared distance from Z is ((1/(1(11))))))1) - 1)). For formal proof of (5) with explicit constants, we refer the reader to Bolić et al. (2024, Appendix B of the extended arxiv version). Summing over i [d] and j [n], we obtain that there exist E,,..., Ed E [-1, 1jd such that
GFT M
j+( (Pe.) GFT 1-(i-1)n (V W ..... Vend () (
((LdInn) ((IdlnT).
16

---

A Parametric Contextual Online Learning Theory of Brokerage
C.2. Proof of Theorem 3.2
The high-level idea of this proof is build a reduction to a non-contextual lower bound construction (see, e.g., the one appearing in Bolić et al. 2024, Theorem 3).
Fix I. 2 2 and 7 e N.
We will use the very same notation as in the proof of Theorem 4.2. In particular, the contexts c CT are again the same as before and declared ahead of time to the learner. We will show that for each algorithm for contextual brokerage with 2-bit feedback and each time horizon T, if 1e7 is the regret of the algorithm at time horizon T when the traders' valuations are VT WT then paa_,11) ((o 2( ((VVTT) if (((.T/d)-1/) and T Q((T))
Note that for all end e [-1,1]%, i [d]. e [n]. and p < 1.2 e > O, then, a direct verification shows that
E GFT (-(i (1/2)] 2 E G (+(1-1)n (p)]
(6)
Similarly, for all éid e [-1,1]], ie [d].
j [m], and p >> 2.2 if e; < 0, then
E GFT (-((-1)a (1/2) 2 E GFT (t ()))
(7)
Furthermore, direct verification shows that, for each End [] and t [T].
max E E(GFTF""()) (v) max E G (p) 50 = 2(1).
(8)
pe [0.1]
Now, assume that T 2 d so that, defining E = (LT/d)-1/4 we have that for any 1 6 {),, any i [d] and any [n]] the maximizer of the expected gain from trade p [[GGF(e1e..... (p) is at 2 196 and hence belongs to j+(i-1)n
the spike region Jr. If a; (resp., a₃ = -1), the optimal price for the rounds + (i 1)n,.... in belongs to the region T4T.
(2 + T4T.
1 (resp.. [ 1. ). By posting prices in the wrong region [0, 2 (resp., [ 1) in the o, = (resp., o, = -1)
case, the learner incurs (2(L²²) ( (T(TTT) instantaneous regret by (3) and (6) (resp., (3) and (7)). Then, in order 2( (LTT/) regret in the rounds + (i 1)...., in, the algorithm would
to attempt suffering less than 2( ((VL/T-.) have to detect the sign of o, and play accordingly. We will show now that even this strategy will not improve the regret of the algorithm (by more than a constant) because the cost of determining the sign of a. with the available feedback. Since for any E [d] and j e [n.] the feedback received from the two traders at time j + (i 1)n by posting a price p is (((ee)))))))) the only way to obtain information about (the sign of) o; is to post in the [p ((ree....aa)) and 1(p S W j-(f-1)n (++(i-))
costly (9(1) (i())-inttantancous regret by Equation (8)) sub-optimal region [ }.. However, posting prices in the region [ &
at time j (i - y can't give more information about o; than the information carried by v(o1e.....dd)) and (=(oee....as)) }+(f-1)n
j+(i-1)n which, in turn, can't 't give more information about o, than the information carried by the two Bernoullis B Bregs (i-(()))))) and B Bioaer 2()+(1-))n) Since only during rounds + (i - 1)m...., .., in is possible to extract information about the sign of o; and, (via an information-theoretie argument) in order to distinguish the sign of a; having access to i.i.d. Bernoulli random variables of parameter 1 requires ((1/=²) = ((VLT/d) samples, we are forced to post at least ((VLT/d) prices in the costly region [] during the rounds + (i 1)n,... in suffering a regret of (VV /LLTd) 22(1) ((VLTdd). Putting everything together, no matter what the strategy, each algorithm will pay at least 22 /TT/d) regret in each epoch
1 (i- 1),..... in for every i [d], resulting in overall regret of ((VI.T/d) d 22 (Vd.T).
17


Reviews:
[{"review_id": "DsQIQspV6d", "reviewer": "Reviewer_AKyE", "summary": "The paper introduces the contextual version of the online brokerage problem. The broker observes a (possibly adversarially generated) context and sets a trading price. The buyer and seller whose private valuations are a perturbed linear function of the context agree for the trade if the price is between the lowest and highest private valuation. The objective function is the gain-from-trade which is the difference between the private valuations subject to the fact that the trade indeed occurs. The goal is to obtain sublinear regret under full feedback and two-bit feedback. The authors propose an algorithm that gets matching regret in both settings under smoothness assumption on the densities of the perturbation. In the unbounded case, the problem becomes unlearnable.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments.\n\n**Additional references** We thank the reviewer for bringing the two additional references to our attention. We will add them to the revised version. Regarding one-sided problems (like auctions or dynamic pricing), no techniques we are aware of can be directly applied to or give clear insights into two-sided problems (like our brokerage problem) other than high-level online learning ideas (like constructing hard lower-bound instances by hiding slightly better actions in an appropriately constructed set of \"hard-to-distinguish\" actions). If the reviewer has any specific references in mind, we are happy to add them to the revised related works section. If they want us to add a concise part on related one-sided problems (like auctions or dynamic pricing), we can do that too.\n\nWith **Assumption 1.2**, we aimed to capture the variability of individual preferences rather than systematic strategic behavior around a target quantity. The assumption is consistent with economic models where the \"market price\" is the notion that aggregates strategic behaviors, asymmetric information, and biases, so that deviations from the market price reduce to *unbiased* residual noise once strategic behaviors are reflected in the market price itself. In other words, the market price does not represent an asset's inherent value but the market participants' average opinion. Importantly, our theoretical results do not require identical distributions across time. The market's opinion can vary arbitrarily (even adversarially) over time, and the noise distributions too (representing periods where opinions are more or less aligned). The only concept that remains stationary is that the market participants' average opinion determines assets' \"market values\". \n\nWe agree that altering this assumption by allowing systematic biases or strategic deviations around a notion of \"inherent value\" would be an interesting alternative path. We will mention this future research direction in the conclusions section and thank the reviewer for raising this point!\n\n**Assumption 1.1 (Market values and contexts)** is indeed an assumption on market values *and* contexts. A natural and common special case in which this assumption holds is when $|| \\phi ||_1 = 1$, i.e., when $\\phi$ is an unknown vector of weights belonging to the probability simplex, representing how important each component of the context vector $c_t$ is to determine the market value at round $t$ (with the boundary cases being $\\phi_i = \\mathbb{I}$ {$i=j$}, for some $j$, i.e., all the information necessary to reconstruct the market value is contained in a component $j$, or $\\phi_i = 1/d$ for all $i$, i.e., all components are equally as informative). In this case, $\\langle \\phi, c_t \\rangle \\in [0,1]$ for all $t$. By Holder's inequality, this can be further generalized by assuming that $||\\phi||_p \\le 1$ and $||c_t||_q \\le 1$ (where $q$ is the Holder conjugate of $p$), which is just another way of expressing boundedness of the vectors. Instead of fixing one of these specific assumptions, we opted for the most general case where only the property $\\langle \\phi, c_t \\rangle \\in [0,1]$ is assumed.\nNote that this assumption is merely for the sake of consistency (it is intuitive to model valuations and market prices all belonging to the same set $[0,1]$), but the same algorithm works, and the same analysis yields the same rate (up to a factor of $d$) if market prices are in $[0,d]$.\nThus, our core theoretical insights remain intact up to minor technical adjustments if this assumption is lifted.\n\n**Assumption 1.2: $V_t, W_t \\in [0,1]$**  \nFor $V_t = m_t + \\xi_t$ and $W_t = m_t +\\zeta_t$ to be bounded in $[0,1]$ for all $t$, the noise random variables $\\xi_t$ and $\\zeta_t$ need to be bounded in $[- m_t , 1 - m_t]$. A sufficient condition for this to happen is to assume that $m_t \\in [a,b]$, with $0<a<b<1$. This is simply stating that the value of the assets traded is never 0 (in real life, if the asset is, e.g., some stock of a company, then $m_t = 0$ only if the company goes bankrupt, in which case, of course, people would not trade the stock) or 1 (which is equally as natural since the fact that prices are normalized in $[0,1]$ means that $1$ represents an upper bound on the largest amount of money that traders would spend to exchange an asset). Note that this boundedness condition does not conflict with the zero-mean assumption but simply ensures that valuations are always interpretable as prices within the normalized range $[0,1]$.\n\nIf, in light of this discussion, the reviewer agrees that the assumptions we made (Assumptions 1.1 and 1.2) do not significantly restrict the general applicability of our theory, we'd kindly ask them if they would consider adjusting their score accordingly. We remain available for clarifications in case we missed something or if something needs further explanation.", "claims_and_evidence": "Yes, all the claims are well supported.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes, I checked the proofs of all the theoretical claims and they seem fine.", "experimental_designs_or_analyses": "The paper has no experimental section.", "relation_to_broader_scientific_literature": "The paper sheds light on the contextual version of the online brokerage problem which is practically relevant (as brokers often have external information before setting the price). The learning algorithms in the paper are quite novel to the best of my knowledge. In the 2-bit feedback model, the algorithm obtains better regret bounds (sqrt(T) vs T^⅔) than the most recent work in this area [GBC+24] under a more relaxed setting which highlights the contributions of the paper. Although constructing the lower bound instance is quite intricate and involved, the paper mostly leverages the existing work of [BCR24].\n\n[GBC+24] Gaucher, S., Bernasconi, M., Castiglioni, M., Celli, A., & Perchet, V. (2024). Feature-based online bilateral trade. arXiv preprint arXiv:2405.18183.", "essential_references_not_discussed": "Connections to the literature on learning how to price in posted price mechanisms and second-price auctions should be discussed more thoroughly. In particular, several works have explored strategic manipulation in similar auction settings:\n\n\"Dynamic Incentive-Aware Learning: Robust Pricing in Contextual Auctions\" by Negin Golrezaei, Adel Javanmard, and Vahab Mirrokni was published in the Advances in Neural Information Processing Systems 32 (NeurIPS 2019) conference proceedings. This work examines robust pricing strategies in contextual second-price auctions where bidders behave strategically.\n\nKareem Amin, Afshin Rostamizadeh, and Umar Syed. (2013). Learning prices for repeated auctions with strategic buyers. In Advances in Neural Information Processing Systems, pp. 1169–1177. This paper explores learning strategies in repeated auction settings where buyers act strategically, influencing the pricing dynamics.\n\nThere are also earlier papers that studied learning in auction settings but did not account for strategic behavior. It would be helpful to clarify whether the authors borrowed any ideas or insights from this existing literature. While there are clear differences between the settings, the nature of the feedback in both cases is similar, which raises the possibility that techniques from the earlier work could have informed the proposed approach. Addressing these connections would strengthen the positioning of the paper within the broader research landscape.", "other_strengths_and_weaknesses": "**Strengths:**\nThe learning algorithms and its analysis are quite neat and intuitive.\n\nThe authors obtain tight regret bounds for all the considered settings (up to log terms).\n\n**Weaknesses:**\nThe assumptions are possibly too strong. See details in \"questions for authors\" section.", "other_comments_or_suggestions": "NA", "questions_for_authors": "The proofs in the paper heavily rely on the two main assumptions. **Assumption 1.2**, in particular, raises some questions about its realism. This assumption states that traders' private valuations are zero-mean perturbations of the market value. However, if the market prices (which serve as the context) are adversarially generated, it seems inconsistent to assume that the traders' valuations would remain unbiased and follow a simple random pattern around the market price. In real-world financial markets, traders' valuations are influenced by complex factors such as market manipulation, asymmetric information, strategic behavior, and behavioral biases — all of which could introduce systematic deviations from the market price rather than just zero-mean noise.\n\nFurthermore, adversarial market prices suggest that the market environment itself is highly unpredictable and potentially influenced by strategic forces. Under such conditions, it seems natural to expect that traders' valuations would also reflect some degree of strategic adaptation rather than simple random perturbations. For example, traders might adjust their valuations based on market trends, competitor behavior, or even attempts to exploit the broker's algorithm. Therefore, it would be helpful if the authors could clarify the rationale behind this assumption and discuss whether relaxing it — for instance, allowing for adversarial or biased deviations in valuations — would significantly affect the theoretical results. Additionally, providing empirical or theoretical justification for why the perturbation model remains reasonable under adversarial contexts would strengthen the validity of the assumption and enhance the practical relevance of the model.\n\n2- For a fixed $ \\phi \\in [0, 1]^d %, if the contexts $c_t \\in [0, 1]^d $ are allowed to be adversarially generated, it’s not immediately clear how the inner product \n$m_t = \\langle \\phi, c_t \\rangle$ would stay within the bounded range of \\([0, 1]\\). **The range of the inner product  $\\langle \\phi, c_t \\rangle $ is theoretically $[0, d]$ because both $ \\phi $ and $ c_t $ are vectors of dimension $ d $ with entries in $[0, 1]$. **In the worst-case scenario, if all components of \\( \\phi \\) and \\( c_t \\) are maximized at 1, the inner product would reach its upper bound of  $d $, which exceeds the target range of $[0, 1]$.\n\nThis raises two key questions:  \n\n1. **Bounding the Market Value:** If the goal is to model $m_t$ as a valid market value within $[0, 1]$, how is the inner product restricted to stay in this range when the contexts are adversarially generated? If the adversarial generation of contexts is unconstrained, the inner product could easily exceed 1.  \n\n2. **Impact on Learning and Regret Bounds:** If the inner product can exceed 1, the broker’s learning strategy and regret guarantees might break down, since the reward function and the regret definition are based on the assumption that the market value is bounded within $[0, 1]$. If the true range is wider, the theoretical analysis might require adjustments or additional constraints on the adversarial nature of the contexts.\n\nOne way to address this could be to explicitly impose a normalization or projection step that ensures the computed market value remains in the interval $[0, 1]$ — for example, defining the market value as \n$\nm_t = \\min(1, \\max(0, \\langle \\phi, c_t \\rangle)).\n$\n\n3- Moreover, what are the assumptions on the random variables $\\xi$ and $\\zeta$ to ensure that the private valuations of the sellers and buyers are in $[0, 1]$?", "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": "ujGlRHaoe9", "reviewer": "Reviewer_cd62", "summary": "This paper addresses the problem of sequentially determining transaction prices between two parties based on contextual information. Transactions occur, and rewards are obtained, only when the proposed price falls between the private valuations of the two parties. It is assumed that the expected values of these private valuations can be represented by unknown linear functions of the contextual information. The paper considers two feedback settings: a \"2-bit feedback\" setting, where only the occurrence of a transaction is observable, and a \"full feedback\" setting, where the actual valuations are observable. We characterize sufficient conditions to achieve favorable regret bounds, demonstrating that good regret bounds can be attained when the valuation distributions have bounded density functions. Conversely, we also show that, without this assumption, the regret can become linear in the worst case.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review of our work and the comments on our submission.\n\nWe are pleased to read that the reviewer evaluates positively the soundness of our setting, the correctness of our results, and our discussion of the relevant related literature. \n\nIt is our understanding that no further clarification or comment is required from us at the moment, but of course, we remain available to provide them upon request.", "claims_and_evidence": "The contributions of this paper are theoretical, and all appear to be supported by correct proofs.", "methods_and_evaluation_criteria": "The evaluation metric used in this paper (the regret defined in Section 1.1) is natural and reasonable.", "theoretical_claims": "I checked the correctness of Lemma 2.1, Corollary 2.2, Lemma 2.3, Theorem 3.2, and Theorem 4.1.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "Although there are several known studies on the online brokerage problem in the context of online learning theory, research addressing contextual settings appears to be relatively scarce. \nThis paper can be viewed as an extension of existing online brokerage problems to contextual scenarios.\nMany aspects of the modeling assumptions, algorithms, and analyses resemble elements found in existing literature on online brokerage problems, online learning, and bandit problems. Essentially, the approach can be viewed as a clever combination of existing techniques.", "essential_references_not_discussed": "I am not aware of any particular relevant literature not discussed.", "other_strengths_and_weaknesses": "The assumption that noise distributions have bounded densities might seem somewhat unrealistic in practical scenarios. For example, this assumption is not satisfied if valuations follow certain discrete distributions. I view this point as a potential weakness of the paper. Nevertheless, the authors have demonstrated that without this assumption, linear regret can occur in the worst case, thus providing evidence that this assumption is essential.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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": "4F4qR0aweU", "reviewer": "Reviewer_WcHi", "summary": "This paper considers the brokerage problem between traders for contextual online bilateral trade where in each round, two traders arrive and a context is revealed, then the broker reveals a price, then broker only observes whether the trade with the given price occurred and the identity of buyer and seller. Under some assumptions on (i) the connection between market value and the context, and (ii) the traders' private valuations, they provided the following results\n- A linear regret lower bound under no assumption on the density of valuation of traders\n- When the density of the valuation is bounded by $L$, they have the following results:\n  - For the natural the 2bit information, they provided an algorithm with $\\sqrt{LdT\\ln{T}}$ regret upper bound and lower bound $\\sqrt{Ldt}$ where $d$ is context dimension and $T$ is number of rounds\n  - For the case where the broker additionally can observe the private valuations (full information), they provided an algorithm with $O(Ld \\ln{T})$ and a matching lower bound.\n\n1. An important conceptual contribution is a structural result in Lemma 2.1, which shows that under some conditions, the optimal price to post is the market value of the item. \n2. At high-level, in the 2bit information setting, they provided an exploration-exploitation separated style algorithm that given a context, it either explores by uniformly selecting a price in $[0,1]$ to update the estimated $\\hat{\\phi}$ or exploits by selecting a price using the estimated $\\hat{\\phi}$ and context $c_t$, i.e. $P_t = c_t^T \\hat{\\phi}$. To prove the regret upper bound, they upper bound the number of exploration rounds and the regret in the exploitation rounds.\n3. Note that the matching lower bound (up to logarithmic factor) shows that the exploration-exploitation separated algorithm is optimal.\n4. Additionally, the lower bound in Section 5, shows that the assumption for bounded density for valuation is needed to achieve no regret in their setting. At a high-level, when the valuation is a probability mass function, then the optimal pricing is not necessarily the market value, which is shown in Example 5.1, and then using this idea, they showed that for a distinct context sequence, $c_1, \\ldots, c_T$, it is possible to construct a sequence of valuations for $V_t, W_t$ such that the learner in all rounds is off by a constant from the benchmark because it does not know whether $V_t,W_t$ is either $V_{t,\\theta=0}, W_{t,\\theta=0}$ or $V_{t,\\theta=1}, W_{t,\\theta=1}$", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for carefully reading the paper and for their kind words! Thanks also for spotting the typos ($\\xi_{t} \\rightsquigarrow \\xi_{t,\\theta}$ and $\\zeta_{t} \\rightsquigarrow \\zeta_{t,\\theta}$) on Line  407. We will correct them in the revised version.\n\nIt is our understanding that no further clarification or comment is required from us at the moment, but of course, we remain available to provide them upon request.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "- I checked the proof of Theorem 5.2, except those tedious computations mentioned there. I think there is a minor typo in line 407, where $V_{t, \\theta}= c_t^T \\phi + \\xi_t$ where I think it should be $\\xi_{t,\\theta}$, similarly for $\\zeta_t$. But this typo doesn't impact anything.\n - I checked the high level of Theorem 3.1, although I didn't closely verify the part of the proof on the right-hand side of page 6.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "Since I'm not familiar with the area, I can't fully assess this, however, given the points mentioned in the paper, I think this could advance the knowledge of online brokerage problems. Especially because the contextual setting is relatively less explored.", "essential_references_not_discussed": "I didn't find any", "other_strengths_and_weaknesses": "Writing is very clear", "other_comments_or_suggestions": "no comments", "questions_for_authors": "no questions", "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": "BMjXten4yA", "reviewer": "Reviewer_2Azh", "summary": "This paper studies brokerage as a contextual online learning problem. Under the assumption that traders' valuations depend linearly on a context available to a broker, the authors design an algorithm achieving a regret bounded by sqrt T. They also derive a corresponding lower bound. The paper then considers the full information feedback, under which an improvement of algorithm 1 leads to a lnT bound on the regret. Here again, a corresponding lower bound is derived. Finally, the authors stress the importance of the bounded density assumption by showing that without this assumption, it is possible to build an instance for which the regret incurred by any algorithm grows linearly with the horizon.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments.\n\n**Essential References** After reviewing the submission in light of the reviewer remarks, we agree that the mentioned statements could be weakened a bit. We are happy to make the requested changes in the revised version.\n\n**Q1** Great question! One could indeed think of the traders in our model as \"impatient\". They arrive sequentially and permanently exit if unable to (or after completing a) trade immediately. Under such a sequence of \"one-shot\" interactions, misreporting valuations offers no future strategic advantage, making truthfulness naturally incentive-compatible. Similar \"single-shot participation\" modeling assumptions are not uncommon in the bilateral trade literature (Myerson and Satterthwaite, 1983; Blumrosen and Mizrahi, 2016; Colini-Baldeschi et al., 2020; Cesa-Bianchi et al., 2021), as they simplify analyses without sacrificing practical relevance (think of large markets where the broker interacts with new traders every day, like future markets, where the median trader participates in at most 4 trades before leaving the market forever; Ferko et al., Retail Traders in Futures Markets, 2024). Still, the reviewer might wonder:  \"Why not even attempt to systematically analyze recurring traders?\" The answer is that the problem wouldn't simply become harder, but unlearnable. The proof of Theorem 5.2 implies, as a corollary, that learning is impossible if valuations are chosen strategically. In fact, it gives the even stronger result that learning is impossible even against *oblivious* adversaries (i.e., when valuations are deterministic sequences of numbers in $[0,1]$ that are fixed ahead of time and don't vary as a function of the learner's actions). That said, our model still captures some degree of strategic behavior, as we discuss in our answer to Reviewer AKyE regarding Assumption 1.2.\n\n**Q2** \nGood question. \nPlease note that the algorithm SBIP in Gaucher et al. requires additional assumptions to guarantee their stated regret upper bound.\nIn particular, the noise distribution for the seller is assumed i.i.d. across times (while we can deal with time-changing noise distributions), and the same is true for the buyer.\nFurthermore, note that an algorithm for the classic bilateral trade problem needs to be adapted to the brokerage setting since, in the brokerage problem, sellers' and buyers' roles are not fixed. A way to do this is by interpreting the agent with the lower valuation as a seller and the agent with the higher valuation as a buyer. Hence setting $S_t = V_t  \\land W_t$ and $B_t = V_t \\lor W_t$. However, by doing this, the independence between sellers' and buyers' valuations, as well as the assumption that these valuations are zero-mean perturbations of a linear function of the contexts, both present in the statement of the regret guarantees in Gaucher et al., are lost.\n\nThis suggests that their algorithm might not yield sublinear guarantees in our setting.\nWe validate this intuition by running the experiments the reviewer requested and comparing our regret with theirs.\nAs we suspected, their algorithm applied to our setting suffers linear regret, while our Algorithm 1 grows at the theoretical rate of $O(\\sqrt{T})$ we proved; see picture in anonymized link: https://i.ibb.co/MkXr19t4/plot.jpg.\n\nThe experiments were run for time horizons $T = 1000, 2000, \\cdots, 10^4$ for $20$ simulations for each time horizon. At these time steps, the algorithms are tuned by using the parameters prescribed by the respective theories for each specific time horizon, and the corresponding regret is plotted. The dimension $d$ is set to $10$, the noise is uniform in $[-1/4,1/4]$, the unknown vector $\\phi$ is picked at random in the $d$-dimensional simplex, while contexts are an i.i.d. process drawn at random in $[1/4,3/4]^d$.\n\nWe remain available for clarifications in case we missed something or if something needs further explanation.\nIf our response convinces the reviewer, we'd kindly ask them if they would consider adjusting their score accordingly.", "claims_and_evidence": "Every claim made in the paper is supported by formal arguments. The authors are transparent regarding the scope of their results.", "methods_and_evaluation_criteria": "I fell that experiments are lacking. Given the simplicity of the setting, implementing Algorithm 1 in a simulated environment should not be too challenging. Specifically, comparing the performance of Algorithm 1 in a simulated environment with that of Gaucher (2024) would further support the claim that this method is superior.", "theoretical_claims": "I went rapidly through proofs in the main text and I haven’t spotted any blatant problem.", "experimental_designs_or_analyses": "Not relevant.", "relation_to_broader_scientific_literature": "The literature review is excellent. Even though I have no expertise in the specific brokerage problem, I found it easy to understand how this paper relates to existing studies. In particular, the authors compare their results to the state-of-the-art and clearly explain how their approach improves upon previous work.", "essential_references_not_discussed": "I do not think about any essential reference overlooked by the authors. I would only point out that the sentence “For these reasons, the techniques appearing in contextual linear bandits do not directly translate to our problem.“ (line 216–218) seems a bit too strong. While I understand that gain-from-trade is not linear in the context, it is still piecewise linear, and the proofs in the paper rely a lot on the linear contextual bandit machinery. Likewise, the 2-bits feedback does not look very different from what is considered in duelling and threshold bandits.", "other_strengths_and_weaknesses": "strengths:\n\nS1. the paper is very clear and well written. The assumptions and the results are clearly stated. I enjoyed reading this work. \n\nS2. The results are interesting and improve over the known state-of-the-art for this particular problem.\n \nS3. Each upper-bound on regret is supported by a corresponding lower bound, showing that the proposed algorithms achieve almost optimal performances. \n\n weaknesses:\n\nW1. I believe adding experiments would significantly improve the paper, particularly in supporting the claim that this approach outperforms that of Gaucher et al. (2024). An actual implementation seems even more necessary given that the paper aims to address a practical problem, and the reward environment appears to be relatively straightforward.\n\nW2. The paper makes the underlying assumption that traders are truthful when revealing their willingness to trade to the broker, both in the 2-bits and the full information setting. This seems quite unlikely for actual traders to be so passive and non-strategic. Under-reporting or over-reporting valuations in each period so as to bias the estimate \\hat{\\phi} seems like a simple strategy to increase gains for traders. This game-theoretic aspect is totally left aside.", "other_comments_or_suggestions": "I do not have other comments.", "questions_for_authors": "Q1. Regarding W2, can you discuss why discarding the strategic aspect of your problem makes sense? Ideally, one would want to prove that being truthful is a dominant strategy, or sustainable as a Nash equilibrium. If proving such a result is impossible, it should at least be discussed in the paper. \n\nQ2. As argued in W1, it seems easy to implement an experiment to back the theoretical results of the paper.\n\nEDIT: The authors answered both my questions in a convincing way. I changed my recommendation to Accept.", "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:

Meta-review: This paper studies the problem of learning in a repeated bilateral trade setting --- a topic that has gained traction in the recent few years. The model studied in this paper is a nice twist to what's been studied recently, namely, that either party can be a buyer or a seller. At each step $t$, two agents arrive, with private valuations $V_t$ and $W_t$, and a broker (or mechanism designer) is allowed to post a price $p_t$. If $p_t$ happens to fall in between $V_t$ and $W_t$ a trade happens, regardless of whether $V_t$ is larger or $W_t$  is larger. The valuations $V_t$ and $W_t$ are derived from a market value $m_t$ plus two (possibly correlated) zero-mean variables $\zeta_t$ and $\xi_t$, with densities bounded by $L$. I.e., $V_t = m_t + \xi_t$ and $W_t = m_t + \zeta_t$, and the market value $m_t$ itself is related to a $d$-dimensional context $c_t$ (the context is revealed to the mechanism designer) via a linear relationship $m_t = \langle c_t, \phi \rangle$. The mechanism designer seeks to minimize regret in gains from trade, namely, the difference between the gains from trade obtained by the optimal-in-hindsight function mapping contexts to prices, to the gains from trade obtained by the broker. The broker's feedback is just two bits: after posting their price $P_t$, the broker can observe whether the price is larger or smaller than $V_t$ and likewise for $W_t$. 

The committee appreciated several aspects of the paper including (a) tight regret bounds as a function of all quantities unvolved, namely, the density bound $L$, dimension $d$ and time horizon $T$, (b) a clear separation between the full feedback setting (where $V_t$ and $W_t$ are revealed after each round $t$) and the one studied in this paper, and (c) the problem itself being a nice twist to the regular bilateral trade setting.

The paper is a solid contribution to ICML.
Decision: Accept (poster)