A Contextual Online Learning Theory of Brokerage

## Abstract

Abstract We study the role of contextual information in the online learning problem of brokerage between traders.
At each round, two traders arrive with secret valuations about an asset they wish to trade.
The broker suggests a trading price based on contextual data about the asset.
Then, the traders decide to buy or sell depending on whether their valuations are higher or lower than the brokerage price. We assume the market value of traded assets is an unknown linear function of a d 𝑑 d -dimensional vector representing the contextual information available to the broker. Additionally, we model traders’ valuations as independent bounded zero-mean perturbations of the asset’s market value, allowing for potentially different unknown distributions across traders and time steps.
Consistently with the existing online learning literature, we evaluate the performance of a learning algorithm with the regret with respect to the gain from trade .
If the noise distributions admit densities bounded by some constant L 𝐿 L , then, for any time horizon T 𝑇 T : • If the agents’ valuations are revealed after each interaction, we provide an algorithm achieving O ​ ( L ​ d ​ ln ⁡ T ) 𝑂 𝐿 𝑑 𝑇 O(Ld\ln T) regret, and show a corresponding matching lower bound of Ω ​ ( L ​ d ​ ln ⁡ T ) Ω 𝐿 𝑑 𝑇 \Omega(Ld\ln T) . • If only their willingness to sell or buy at the proposed price is revealed after each interaction, we provide an algorithm achieving O ​ ( L ​ d ​ T ​ ln ⁡ T ) 𝑂 𝐿 𝑑 𝑇 𝑇 O\bigl{(}\sqrt{LdT\ln T}\bigr{)} regret, and show that this rate is optimal (up to logarithmic factors), via a lower bound of Ω ​ ( L ​ d ​ T ) Ω 𝐿 𝑑 𝑇 \Omega\bigl{(}\sqrt{LdT}\bigr{)} . To complete the picture, we show that if the bounded density assumption is lifted, then the problem becomes unlearnable, even with full feedback.

## 1 Introduction

Inspired by a recent stream of literature [, , , , , ], 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 interactions with no prior knowledge of their private valuations.
As in [], we focus on the case where traders are willing to either buy or sell, depending on whether their valuations for the asset being traded are above or below the brokerage price.

This setting is especially relevant for over-the-counter (OTC) markets.
Serving as alternatives to conventional exchanges, OTC markets operate in a decentralized manner and are a vital part of the global financial landscape.(^1^11In the US alone, the value of assets traded in OTC markets exceeded a remarkable 50 trillion USD in 2020, surpassing centralized markets by more than 20 trillion USD []. This growth has been steadily increasing since 2016 [].)
In contrast to centralized exchanges, the lack of strict protocols and regulations allows brokers to take on 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 knowledge and market insights to 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 value of the asset being traded.
This price discovery process is a crucial aspect of a broker’s role, as it helps ensure efficient transactions by accounting for the unique circumstances surrounding each asset.
Additionally, in many OTC markets, as in our setting, traders choose to either buy or sell depending on the contingent market conditions [].
This behavior is observed across a broad range of asset trades, including stocks, derivatives, art, collectibles, precious metals and minerals, energy commodities like gas and oil, and digital currencies (cryptocurrencies), among others [].

In the existing literature on online learning for bilateral trade, the contextual version of this problem has never been investigated.
This case is of significant 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 the current market value of the corresponding asset, and ignoring it could be extremely costly in terms of missing trading opportunities.
We aim to fill this gap in the online learning literature on bilateral trade to guide brokers in these contextual scenarios.

### 1.1 Setting

In the following, the elements of any Euclidean space are treated as column vectors and, for any real number $x,y$, we denote their minimum by $x\wedge y$ and their maximum by $x\vee y$.

We study the following problem. At each time $t\in\mathbb{N}$,

- $\circ$
Two traders arrive with private valuations $V_{t},W_{t}\in[0,1]$ about an asset they want to trade.
- $\circ$
The broker observes a context $c_{t}\in[0,1]^{d}$ and proposes a trading price $P_{t}\in[0,1]$.
- $\circ$
If the price $P_{t}$ lies between the lowest valuation $V_{t}\wedge W_{t}$ and highest valuation $V_{t}\vee W_{t}$ (meaning the trader with the minimum valuation is ready to sell at $P_{t}$ and the trader with the maximum valuation is eager to buy at $P_{t}$), the asset is bought by the trader with the highest valuation from the trader with the lowest valuation at the brokerage price $P_{t}$.
- $\circ$
Some feedback is disclosed.

We assume that at each time $t\in\mathbb{N}$, the traders’ valuations $V_{t}$ and $W_{t}$ are zero-mean perturbations of some (unknown) market value $m_{t}\in[0,1]$ of the asset being traded.
Specifically, we assume that there exists an independent family of random variables $(\xi_{t},\zeta_{t})_{t\in\mathbb{N}}$ such that, for each $t\in\mathbb{N}$, it holds that $\mathbb{E}[\xi_{t}]=0=\mathbb{E}[\zeta_{t}]$ and $V_{t}=m_{t}+\xi_{t}$ and $W_{t}=m_{t}+\zeta_{t}$.(^2^22We remark that we are not assuming that the two processes $(\xi_{t})_{t\in\mathbb{N}}$ and $(\zeta)_{t\in\mathbb{N}}$ are i.i.d., and in fact the distributions of these random variables may change over time.)
In particular, we note that $\mathbb{E}[V_{t}]=m_{t}=\mathbb{E}[W_{t}]$, for each $t\in\mathbb{N}$, and hence the traders’ valuations can be thought of as zero-mean perturbations of the market value of the asset due to individual preferences.

Following the recent stream of bilateral trade literature investigating the interplay between learning and the regularity of the underlying valuation distributions [, , ], we focus on the case when the traders’ valuation distributions admit densities that are uniformly bounded by some constant $L\geq 1$.
We note that this assumption is equivalent to the same uniformly bounded density assumption on the distributions of the noise $\xi_{1},\zeta_{1},\xi_{2},\zeta_{2},\dots$.
Then, we analyze what happens when the bounded density assumption is lifted.

We assume an unknown linear relation exists between the market value $m_{t}$ for the asset being traded at time $t$ and the corresponding context $c_{t}$ the broker observes before proposing a trading price. Specifically, we assume that there exists $\phi\in[0,1]^{d}$, unknown to the broker, such that, for each $t\in\mathbb{N}$, it holds that $m_{t}=c_{t}^{\top}\phi$.

We model the sequence of contexts $(c_{t})_{t\in\mathbb{N}}$ as a deterministic $[0,1]^{d}$-valued sequence, possibly generated in an adversarial manner by someone who knows the broker’s algorithm.
As explained above, we assume that the sequence of contexts is initially unknown but sequentially discovered by the broker.

Consistently with the existing bilateral trade literature, the reward associated with each interaction is the sum of the net utilities of the traders, known as *gain from trade*.
Formally, for any $p,v,w\in[0,1]$, the utility of a price $p$ when the valuations of the traders are $v$ and $w$ is

$$ $\mathrm{g}(p,v,w)\coloneqq(\underbrace{v\vee w-p}_{\textrm{buyer's net gain}}+\underbrace{p-v\wedge w}_{\textrm{seller's net gain}})\mathbb{I}\{\underbrace{v\wedge w\leq p\leq v\vee w}_{\textrm{whenever a trade happens}}\}=\left(v\vee w-v\wedge w\right)\mathbb{I}\{v\wedge w\leq p\leq v\vee w\}.$ $$

The aim of the learner is to minimize the *regret* with respect to the best function of the contexts, defined, for any time horizon $T\in\mathbb{N}$, as

$$ $R_{T}\coloneqq\sup_{p^{\star}\colon[0,1]^{d}\to[0,1]}\mathbb{E}\biggl{[}\sum_{t=1}^{T}\Bigl{(}\mathrm{GFT}_{t}\bigl{(}p^{\star}(c_{t})\bigr{)}-\mathrm{GFT}_{t}(P_{t})\Bigr{)}\biggr{]}\;,$ $$

where we let $\mathrm{GFT}_{t}(p)\coloneqq\mathrm{g}(p,V_{t},W_{t})$ for all $p\in[0,1]$, and the expectation is taken with respect to the randomness in $(\xi_{t},\zeta_{t})_{t\in\mathbb{N}}$ and, possibly, the internal randomization used to choose the trading prices $(P_{t})_{t\in\mathbb{N}}$.

Finally, we consider the two most studied types of feedback in the bilateral trade literature. Specifically, at each round $t$, only after having posted the price $P_{t}$, the learner receives either:

- $\circ$
*Full feedback*, i.e., the valuations $V_{t}$ and $W_{t}$ of the two current traders are disclosed.
- $\circ$
*Two-bit feedback*, i.e., only the indicator functions $\mathbb{I}\{P_{t}\leq V_{t}\}$ and $\mathbb{I}\{P_{t}\leq W_{t}\}$ are disclosed.

The information gathered in the full feedback model reflects *direct revelation mechanisms*, where traders disclose their valuations $V_{t}$ and $W_{t}$ prior to each round, but the price determined by the mechanism at time $t$ is based solely on the previous valuations $V_{1},W_{1},\dots,V_{t-1},W_{t-1}$. Conversely, the two-bit feedback model reflects *posted price* mechanisms. In this model, traders only indicate their willingness to buy or sell at the posted price, and their valuations $V_{t}$ and $W_{t}$ remain undisclosed.

### 1.2 Our contributions

Under the assumption that the traders’ valuations are unknown linear functions of $d$-dimensional contexts perturbed by zero-mean noise with time-variable densities bounded by some $L$,
and with the goal of designing *simple* and *interpretable* optimal algorithms,
we make the following contributions.

- 1.
We prove a structural result ([Lemma 1](#Thmlemma1)) with two crucial consequences. First, [Lemma 1](#Thmlemma1) shows that posting the traders’ (unknown) expected valuation as the trading price would maximize the expected gain from trade. Second, it proves that the loss paid by posting a suboptimal price is at most quadratic in the distance from an optimal one.
- 2.
In the full feedback setting, we introduce an algorithm based on ridge regression estimation ([Algorithm 1](#algorithm1)) and, leveraging the previous lemma, we prove its optimality by showing matching $Ld\ln T$ regret upper and lower bounds ([Theorems 1](#Thmtheorem1) and [2](#Thmtheorem2)).
- 3.
In the two-bit feedback setting, the prices we post directly affect the information we retrieve. We note that this information is so scarce that it is not even enough to reconstruct bandit feedback. We solve this challenging exploration-exploitation dilemma by proposing an algorithm ([Algorithm 2](#algorithm2)) that decides to either explore or exploit adaptively, based on the amount of contextual information gathered so far, and prove its optimality by showing a $\sqrt{LdT\ln T}$ regret upper bound ([Theorem 3](#Thmtheorem3)) and a matching (up to a $\sqrt{\ln T}$) $\sqrt{LdT}$ lower bound ([Theorem 4](#Thmtheorem4)).
- 4.
Finally, we investigate the necessity of the bounded density assumption: by lifting this assumption, we show that the problem becomes unlearnable ([Theorem 5](#Thmtheorem5)).

To the best of our knowledge, our work is the first to analyze a *non-parametric noisy contextual* bilateral trade problem (in fact, the first that analyzes a *contextual* bilateral trade problem in general) and one of only two works on bilateral trade (the other one being []) where the dependence on *all* relevant parameters is tight.
As we discuss in [Section 1.3](#S1.SS3), most related works on non-contextual bilateral trade obtain (at best) a matching dependence in the time horizon only, while those on non-parametric noisy contextual pricing/auctions lack matching lower bounds altogether.

### 1.3 Related Works

Building upon the foundational work of Myerson and Satterthwaite [], a rich body of research has investigated bilateral trade from a game-theoretic and best-approximation standpoint [, , , , , , , , , ]. For an insightful analysis of this literature, see [].

Our work builds upon the recent research on bilateral trade within online learning settings. Given the close relationship between our and these existing works, we discuss these connections in detail.
First, to the best of our knowledge, the existing online learning literature on bilateral trade *never* discussed contextual problems.
In [, , , , , ], the authors studied non-contextual bilateral trade problems where sellers and buyers have definite roles.
[, ] show that the adversarial setting is unlearnable, and hence they focus on the case where sellers’ and buyers’ valuations form an i.i.d. process. They obtain a $\sqrt{T}$ regret rate in the full-feedback setting. For the two-bit feedback case, they show that the problem is unlearnable in general, but it turns out to be learnable at a tight regret rate of $T^{2/3}$ by assuming that sellers’ and buyers’ valuations are independent of each other and they admit a uniformly bounded density.
[] show that learning is achievable in the adversarial case if the weaker $\alpha$-regret objective is considered.
Specifically, in the full-feedback case, they obtain a tight $2$-regret rate of $\sqrt{T}$. In the two-bit feedback case, they show that learning is impossible in general, but by allowing the learner to use weakly budget-balanced mechanisms, they recover a $2$-regret of order $T^{3/4}$, without a matching lower bound.
In a different direction, [, ] show that learning is achievable in the adversarial case if the adversary is forced to be *smooth*, i.e., the sellers’ and buyers’ valuation distributions may change adversarially over time, but these distributions admit uniformly bounded densities. In the full-feedback case, they obtain a tight $\sqrt{T}$ regret rate. In the two-bit feedback case, they show that the problem is still unlearnable, but, by allowing the learner to use weakly budget-balanced mechanisms, they prove a surprisingly sharp $T^{3/4}$ regret rate.
[] propose the notion of globally budget-balanced mechanisms, a further relaxation of the weakly budget-balanced notion, under which they show that learning is achievable in the adversarial case at a tight regret rate of $\sqrt{T}$ in the full-feedback case, and at a regret rate of $T^{3/4}$ in the two-bit feedback case, without a matching lower bound.
We remark that in all the papers we discussed so far, every two-bit feedback upper bound that requires a bounded density assumption lacks a corresponding lower bound with a sharp dependence on this parameter.
The closest to our setting is the one proposed in [].
There, the authors study the non-contextual version of our trading problem with flexible sellers’ and buyers’ roles, with the further assumption that the sellers’ and buyers’ valuations form an i.i.d. sequence.
Under the $M$-bounded density assumption, they obtain tight $M\ln T$ and $\sqrt{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 $\sqrt{T}$ 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.

Our linear assumption appears commonly in the literature on digital markets, particularly in problems like pricing and auctions.
In [, ], the authors first address a deterministic setting, then a noisy one with *known* noise distribution where they obtain a regret rate of order $T^{2/3}$ without presenting a lower bound.
The deterministic case has also been investigated in [, , , , ].

Notably, the best results currently known only apply to deterministic settings, while, in the case of noisy linear functions, to the best of our knowledge [, , , , , , , ], the only known guarantees are limited to parametric or semi-parametric settings, a clear general picture of the minimax rates is still missing, and only slow upper bounds of order $T^{2/3}$ are known in the non-parametric case where the noise distribution is unknown.
In contrast, thanks to our [Lemma 1](#Thmlemma1), we are able to address the trading problem even in the non-parametric noisy linear case, obtaining optimal rates (matched by corresponding lower bounds) which are significantly faster than the ones known for pricing.

Another rich related field explored in its many variants [, , , , , , , , , , , , , , , , ] is contextual linear bandits.
In its standard form, at the beginning of each round, an action set is revealed to the learner, and the assumption is that the reward (which equals the feedback) is a linear function of the action 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 feedback differs from and is not sufficient to compute the reward of the action the learner selects at every round.
For these reasons, the techniques appearing in contextual linear bandits do not directly translate to our problem.

## 2 Structural Results

We begin by presenting a structural result whose economic interpretation is as follows:
even if the broker does not know the traders’ valuation distribution, 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 market value.
In particular, this generalizes a similar result appearing in [], which holds under the further assumption that the valuations have the exact same distribution.
The following result also gives a representation formula for the expected gain from trade, which implies in particular that the cost of posting a suboptimal price is only quadratic in the distance from the market value.
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 pricing works.

###### Lemma 1 .

Suppose that $V$ and $W$ are two $[0,1]$-valued independent random variables, with possibly different densities bounded by some constant $L\geq 1$, and such that $\mathbb{E}[V]=\mathbb{E}[W]\eqqcolon m$.
Then, for each $p\in[0,1]$, it holds that

$$ $0\leq\mathbb{E}\bigl{[}\mathrm{g}(m,V,W)-\mathrm{g}(p,V,W)\bigr{]}\leq L\left\lvert m-p\right\rvert^{2}\;.$ $$

###### Proof.

We denote by $F$ (resp., $G$) the cumulative distribution function of $V$ (resp., $W$).
For each $p\in[0,1]$, from the Decomposition Lemma in [, Lemma 1], it holds that

$$ $\displaystyle\mathbb{E}\bigl{[}(W-V)\mathbb{I}\{V\leq p\leq W\}\bigr{]}$ $\displaystyle=F(p)\int_{p}^{1}\bigl{(}1-G(\lambda)\bigr{)}\,\mathrm{d}\lambda+\bigl{(}1-G(p)\bigr{)}\int_{0}^{p}F(\lambda)\,\mathrm{d}\lambda\;,$ $\displaystyle\mathbb{E}\bigl{[}(V-W)\mathbb{I}\{W\leq p\leq V\}\bigr{]}$ $\displaystyle=G(p)\int_{p}^{1}\bigl{(}1-F(\lambda)\bigr{)}\,\mathrm{d}\lambda+\bigl{(}1-F(p)\bigr{)}\int_{0}^{p}G(\lambda)\,\mathrm{d}\lambda\;.$ $$

Hence, for each $p\in[0,1]$,

$$ $\mathbb{E}\bigl{[}(W-V)\mathbb{I}\{V\leq p\leq W\}\bigr{]}=F(p)\int_{p}^{1}\bigl{(}1-G(\lambda)\bigr{)}\,\mathrm{d}\lambda+\bigl{(}1-G(p)\bigr{)}\int_{0}^{p}F(\lambda)\,\mathrm{d}\lambda\\ \begin{aligned} &=F(p)\left(m-\int_{0}^{p}\bigl{(}1-G(\lambda)\bigr{)}\,\mathrm{d}\lambda\right)+\int_{0}^{p}F(\lambda)\,\mathrm{d}\lambda-G(p)\int_{0}^{p}F(\lambda)\,\mathrm{d}\lambda\\ &=\int_{0}^{p}F(\lambda)\,\mathrm{d}\lambda+(m-p)F(p)-pG(p)+G(p)\int_{0}^{p}\bigl{(}1-F(\lambda)\bigr{)}\,\mathrm{d}\lambda+F(p)\int_{0}^{p}G(\lambda)\,\mathrm{d}\lambda\\ &=\int_{0}^{p}\left(F+G\right)(\lambda)\,\mathrm{d}\lambda+(m-p)\left(F+G\right)(p)-G(p)\left(m-\int_{0}^{p}\bigl{(}1-F(\lambda)\bigr{)}\,\mathrm{d}\lambda\right)+\left(F(p)-1\right)\int_{0}^{p}G(\lambda)\,\mathrm{d}\lambda\\ &=\int_{0}^{p}(F+G)(\lambda)\,\mathrm{d}\lambda+(m-p)(F+G)(p)-\left(G(p)\int_{p}^{1}\bigl{(}1-F(\lambda)\bigr{)}\,\mathrm{d}\lambda+\bigl{(}1-F(p)\bigr{)}\int_{0}^{p}G(\lambda)\,\mathrm{d}\lambda\right)\\ &=\int_{0}^{p}(F+G)(\lambda)\,\mathrm{d}\lambda+(m-p)(F+G)(p)-\mathbb{E}\bigl{[}(V-W)\mathbb{I}\{W\leq p\leq V\}\bigr{]}\;.\end{aligned}$ $$

Rearranging, it follows that, for each $p\in[0,1]$,

$$ $\displaystyle\mathbb{E}\bigl{[}\mathrm{g}(p,V,W)\bigr{]}$ $\displaystyle=\mathbb{E}\bigl{[}(W-V)\mathbb{I}\{V\leq p\leq W\}\bigr{]}+\mathbb{E}\bigl{[}(V-W)\mathbb{I}\{W\leq p\leq V\}\bigr{]}$ $\displaystyle=\int_{0}^{p}(F+G)(\lambda)\,\mathrm{d}\lambda+(m-p)(F+G)(p)\;.$ $$

Hence, for any $p\in[0,1]$, it holds that

$$ $\displaystyle\mathbb{E}\bigl{[}\mathrm{g}(m,V,W)-\mathrm{g}(p,V,W)\bigr{]}$ $\displaystyle=\int_{p}^{m}\bigl{(}(F+G)(\lambda)-(F+G)(p)\bigr{)}\,\mathrm{d}\lambda\geq 0\;.$ $$

Finally, since $F$ and $G$ are absolutely continuous with weak derivative bounded by $L$, by the fundamental theorem of calculus [, Theorem 14.16] it holds that, for $p\in[0,1]$,

$$ $\mathbb{E}\bigl{[}\mathrm{g}(m,V,W)-\mathrm{g}(p,V,W)\bigr{]}=\int_{p}^{m}\int_{p}^{\lambda}(F^{\prime}+G^{\prime})(\vartheta)\,\mathrm{d}\vartheta\,\mathrm{d}\lambda\leq 2L\int_{p}^{m}|\lambda-p|\,\mathrm{d}\lambda=L|m-p|^{2}\;.\qed$ $$

As a corollary of [Lemma 1](#Thmlemma1), we obtain the following 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.

###### Corollary 1 .

Consider the setting introduced in [Section 1.1](#S1.SS1).
If the valuations admit densities bounded by a constant $L\geq 1$, then, for any time horizon $T\in\mathbb{N}$, we have

$$ $R_{T}=\mathbb{E}\left[\sum_{t=1}^{T}\bigl{(}\mathrm{GFT}_{t}(c_{t}^{\top}\phi)-\mathrm{GFT}_{t}(P_{t})\bigr{)}\right]\leq\sum_{t=1}^{T}1\land\Bigl{(}L\mathbb{E}\left[|P_{t}-c_{t}^{\top}\phi|^{2}\right]\Bigr{)}\;.$ $$

###### Proof.

Given that for each $t\in\mathbb{N}$ and each $p\in[0,1]$ it holds that $\mathrm{GFT}_{t}(p)\in[0,1]$, we have

$$ $\sup_{p\in[0,1]}\mathbb{E}\bigl{[}\mathrm{GFT}_{t}(p)-\mathrm{GFT}_{t}(P_{t})\bigr{]}\leq 1\;,$ $$

and hence, recalling that $m_{t}=c_{t}^{\top}\phi$ and that $\mathbb{E}[V_{t}]=m_{t}=\mathbb{E}[W_{t}]$, we also have, for each $T\in\mathbb{N}$,

$$ $\displaystyle R_{T}$ $\displaystyle=\sup_{p^{\star}\colon[0,1]^{d}\to[0,1]}\sum_{t=1}^{T}1\land\Bigl{(}\mathbb{E}\bigl{[}\mathrm{g}\bigl{(}p^{\star}(c_{t}),V_{t},W_{t}\bigr{)}\bigr{]}-\mathbb{E}\bigl{[}\mathrm{g}(P_{t},V_{t},W_{t})\bigr{]}\Bigr{)}$ $\displaystyle\overset{(\circ)}{=}\sum_{t=1}^{T}1\land\Bigl{(}\mathbb{E}\bigl{[}\mathrm{g}\bigl{(}c_{t}^{\top}\phi,V_{t},W_{t}\bigr{)}\bigr{]}-\mathbb{E}\bigl{[}\mathrm{g}(P_{t},V_{t},W_{t})\bigr{]}\Bigr{)}$ $\displaystyle\overset{(*)}{=}\sum_{t=1}^{T}1\land\mathbb{E}\biggl{[}\Bigl{[}\mathbb{E}\bigl{[}\mathrm{g}(c_{t}^{\top}\phi,V_{t},W_{t})-\mathrm{g}(p,V_{t},W_{t})\bigr{]}\Bigr{]}_{p=P_{t}}\biggr{]}\overset{(\circ)}{\leq}\sum_{t=1}^{T}1\land\left(L\mathbb{E}\bigl{[}\left\lvert P_{t}-c_{t}^{\top}\phi\right\rvert^{2}\bigr{]}\right)\;,$ $$

where $(\circ)$ follows from [Lemma 1](#Thmlemma1), and $(*)$ from the Freezing Lemma [, Lemma 8].
∎

###### Lemma 1 .

###### Proof.

###### Corollary 1 .

###### Proof.

## 3 Full Feedback

In this section, we focus on the full feedback setting, corresponding to direct revelation mechanisms.
We show that performing ridge regression to obtain an estimate of the unknown vector $\phi$ and using it as a proxy linear function to convert contexts into prices ([Algorithm 1](#algorithm1)) is enough to achieve logarithmic regret.
In the following, we denote by $\boldsymbol{1}_{d}$ the $d$-dimensional identity matrix.

Figure: Algorithm 1 Ridge Regression Pricing — Full Feedback

###### Theorem 1 .

Consider the full-feedback setting introduced in [Section 1.1](#S1.SS1). If the learner runs [Algorithm 1](#algorithm1) and the traders’ valuations admit a density bounded by $L\geq 1$, then, for any time horizon $T\in\mathbb{N}$, it holds that
$R_{T}\leq 1+4Ld\ln T$.

###### Proof.

Recall that $(\xi_{t},\zeta_{t})_{t\in\mathbb{N}}$ is an independent family of zero mean random variables each of them admitting a density bounded by $L$, that for any $t\in\mathbb{N}$, it holds that $m_{t}=c_{t}^{\top}\phi$, that $m_{t}+\xi_{t}=V_{t}\in[0,1]$ and that $m_{t}+\zeta_{t}=W_{t}\in[0,1]$.
For any $t\in\mathbb{N}$, simple calculations show that

$$ $\displaystyle\mathbb{E}\bigl{[}|c_{t+1}^{\top}\hat{\phi}_{t}-c_{t+1}^{\top}\phi|^{2}\bigr{]}$ $\displaystyle=\bigl{(}\underbrace{\mathbb{E}\left[c_{t+1}^{\top}\hat{\phi}_{t}-c_{t+1}^{\top}\phi\right]}_{\text{bias}}\bigr{)}^{2}+\underbrace{\mathrm{Var}[c_{t+1}^{\top}\hat{\phi}_{t}]}_{\text{variance}}.$ $$

which is the well-known decomposition of the quadratic error with bias and variance of the estimator $c_{t+1}^{\top}\hat{\phi}_{t}$ for the quantity $c_{t+1}^{\top}\phi$. Noting that, for each $t\in\mathbb{N}$, it holds that $\mathbb{E}[Y_{t}^{\top}]=x_{t}^{\top}\phi$, we have,

$$ $\displaystyle\mathbb{E}[c_{t+1}^{\top}\hat{\phi}_{t}-c_{t+1}^{\top}\phi]$ $\displaystyle=c_{t+1}^{\top}(x_{t}x_{t}^{\top}+d^{-1}\boldsymbol{1}_{d})^{-1}x_{t}x_{t}^{\top}\phi-c_{t+1}^{\top}(x_{t}x_{t}^{\top}+d^{-1}\boldsymbol{1}_{d})^{-1}(x_{t}x_{t}^{\top}\phi+d^{-1}\phi)$ $\displaystyle=-c_{t+1}^{\top}(x_{t}x_{t}^{\top}+d^{-1}\boldsymbol{1}_{d})^{-1}d^{-1}\phi\eqqcolon(\circ)\;,$ $$

and hence, by the Cauchy-Schwarz inequality applied to the scalar product $(a,b)\mapsto a^{\top}(x_{t}x_{t}^{\top}+d^{-1}\boldsymbol{1}_{d})^{-1}b$, by the fact that $(x_{t}x_{t}^{\top}+d^{-1}\boldsymbol{1}_{d})^{-1}\preceq d^{-1}\boldsymbol{1}_{d}^{-1}$ (where, for any two symmetric matrices $A_{1},A_{2}$, we say that $A_{1}\preceq A_{2}$ if and only if $A_{2}-A_{1}$ is semi-positive definite), and by the fact that $\left\lVert\phi\right\rVert_{2}^{2}\leq d$, we can control the bias term as follows

$$ $\displaystyle\left(\mathbb{E}[c_{t+1}^{\top}\hat{\phi}_{t}-c_{t+1}^{\top}\phi]\right)^{2}=(\circ)^{2}\leq c_{t+1}^{\top}(x_{t}x_{t}^{\top}+d^{-1}\boldsymbol{1}_{d})^{-1}c_{t+1}~{}\cdot~{}d^{-1}\phi^{\top}(x_{t}x_{t}^{\top}+d^{-1}\boldsymbol{1}_{d})^{-1}d^{-1}\phi$ $\displaystyle\qquad\qquad\leq c_{t+1}^{\top}(x_{t}x_{t}^{\top}+d^{-1}\boldsymbol{1}_{d})^{-1}c_{t+1}~{}\cdot~{}d^{-1}\phi^{\top}(d^{-1}\boldsymbol{1}_{d})^{-1}d^{-1}\phi\leq c_{t+1}^{\top}(x_{t}x_{t}^{\top}+d^{-1}\boldsymbol{1}_{d})^{-1}c_{t+1}.$ (1) $$

For each $t\in\mathbb{N}$, letting $\Delta_{t}$ be the $2t\times 2t$ diagonal matrix with vector of diagonal elements given by $\left(\mathrm{Var}[V_{1}],\mathrm{Var}[W_{1}],\mathrm{Var}[V_{2}],\mathrm{Var}[W_{2}],\ldots,\mathrm{Var}[V_{t}],\mathrm{Var}[W_{t}]\right)$, we have

$$ $\displaystyle\mathrm{Var}[c_{t+1}^{\top}\hat{\phi}_{t}]$ $\displaystyle=c_{t+1}^{\top}(x_{t}x_{t}^{\top}+d^{-1}\boldsymbol{1}_{d})^{-1}(x_{t}\Delta_{t}x_{t}^{\top})(x_{t}x_{t}^{\top}+d^{-1}\boldsymbol{1}_{d})^{-1}c_{t+1}.$ (2) $$

Now, for each $t\in\mathbb{N}$, given that $V_{1},W_{1},\dots,V_{t},W_{t}$ are $[0,1]$-valued, we have that $\Delta_{t}$ is diagonal with diagonal elements less than $1$, and hence
$x_{t}\Delta_{t}x_{t}^{\top}\preceq x_{t}x_{t}^{\top}+d^{-1}\boldsymbol{1}_{d}$, which yields a control on the variance term as follows,

$$ $\displaystyle\mathrm{Var}[c_{t+1}^{\top}\hat{\phi}_{t}]\leq c_{t+1}^{\top}(x_{t}x_{t}^{\top}+d^{-1}\boldsymbol{1}_{d})^{-1}(x_{t}x_{t}^{\top}+d^{-1}\boldsymbol{1}_{d})(x_{t}x_{t}^{\top}+d^{-1}\boldsymbol{1}_{d})^{-1}c_{t+1}=c_{t+1}^{\top}(x_{t}x_{t}^{\top}+d^{-1}\boldsymbol{1}_{d})^{-1}c_{t+1}\;.$ $$

In the end, for each $t\in\mathbb{N}$, we have

$$ $\displaystyle\mathbb{E}\bigl{[}|c_{t+1}^{\top}\hat{\phi}_{t}-c_{t+1}^{\top}\phi|^{2}\bigr{]}$ $\displaystyle\leq 2c_{t+1}^{\top}(x_{t}x_{t}^{\top}+d^{-1}\boldsymbol{1}_{d})^{-1}c_{t+1}=2\left\lVert c_{t+1}\right\rVert_{(x_{t}x_{t}^{\top}+d^{-1}\boldsymbol{1}_{d})^{-1}}^{2}$ $\displaystyle=2\left\lVert c_{t+1}\right\rVert_{(2\sum_{s=1}^{t}c_{s}c_{s}^{\top}+d^{-1}\boldsymbol{1}_{d})^{-1}}^{2}\;=\left\lVert\sqrt{2}c_{t+1}\right\rVert_{(\sum_{s=1}^{t}(\sqrt{2}c_{s})(\sqrt{2}c_{s})^{\top}+d^{-1}\boldsymbol{1}_{d})^{-1}}^{2}\;,$ (3) $$

where, for any positive definite matrix $A\in\mathbb{R}^{d\times d}$ and each $u\in\mathbb{R}^{d}$, we have defined
$\left\lVert u\right\rVert_{A}\coloneqq\sqrt{u^{\top}Au}$.
Now, for any time horizon $T\in\mathbb{N}$, leveraging [Corollary 1](#Thmcorollary1), we have that

$$ $\displaystyle R_{T}$ $\displaystyle\leq\sum_{t=1}^{T}1\land\Bigl{(}L\mathbb{E}\left[|P_{t}-c_{t}^{\top}\phi|^{2}\right]\Bigr{)}\leq 1+\sum_{t=1}^{T-1}1\land\Bigl{(}L\mathbb{E}\left[|c_{t+1}^{\top}\hat{\phi}_{t}-c_{t+1}^{\top}\phi|^{2}\right]\Bigr{)}$ $\displaystyle\leq 1+L\sum_{t=1}^{T-1}1\land\left\lVert\sqrt{2}c_{t+1}\right\rVert_{(\sum_{s=1}^{t}(\sqrt{2}c_{s})(\sqrt{2}c_{s})^{\top}+d^{-1}\boldsymbol{1}_{d})^{-1}}^{2}\eqqcolon(\star)\;.$ $$

From here, we apply the elliptical potential lemma [, Lemma 19.4] to obtain that, for any time horizon $T\in\mathbb{N}$,

$$ $R_{T}\leq(\star)\leq 1+2Ld\ln\left(\frac{dd^{-1}+2d(T-1)}{dd^{-1}}\right)=1+2Ld\ln\bigl{(}1+2d(T-1)\bigr{)}\leq 1+2Ld\ln(2dT)\;.$ $$

If $d<T/2$, this implies that $R_{T}\leq 1+2Ld\ln(2dT)\leq 1+4Ld\ln T$.
If, instead, $d\geq T/2$, then, recalling that $L\geq 1$, we obtain once again that $R_{T}\leq T\leq 1+4Ld\ln T$, concluding the proof.
∎

We conclude this section by stating a matching worst-case $\Omega(Ld\ln T)$ regret lower bound for any algorithm in the full-feedback case, proving the optimality of [Algorithm 1](#algorithm1).

At a high level, the proof of this result is based on first building a sequence of contexts defined as a common element of the canonical basis of $\mathbb{R}^{d}$ during each one of $d$ blocks of $T/d$ consecutive time-steps.
Then, in each block, an adaptation of the non-contextual full-feedback lower bound construction in [, Theorem 3] yields a lower bound of order $L\ln(T/d)$.
Summing over blocks gives the result.
For a full proof of this result, see [Appendix A](#A1).

###### Theorem 2 .

There exist two numerical constants $a,b>0$ such that, for any $L\geq 2$ and any time horizon $T\geq\max(4,adL^{5},2d)$, there exists a sequence of contexts $c_{1},\dots,c_{T}\in[0,1]^{d}$ such that, for any algorithm $\alpha$ for the contextual brokerage problem with full feedback, there exists a vector $\phi\in[0,1]^{d}$ and two zero-mean independent sequences $(\xi_{t})_{t\in[T]}$ and $(\zeta_{t})_{t\in[T]}$ independent of each other, such that if we define $V_{t}\coloneqq c_{t}^{\top}\phi+\xi_{t}$ and $W_{t}\coloneqq c_{t}^{\top}\phi+\zeta_{t}$, then for each $t\in[T]$ it holds that $c_{t}^{\top}\phi\in[0,1]$, $V_{t}$ and $W_{t}$ are $[0,1]$-valued random variables with density bounded by $L$, and the regret of $\alpha$ on the sequence of traders’ valuations $V_{1},W_{1},\dots,V_{T},W_{T}$ satisfies
$R_{T}\geq bLd\ln T$.

We remark that the previous lower bound holds even for algorithms that have prior knowledge of the sequence of contexts $c_{1},c_{2},\dots$ and that [Theorem 1](#Thmtheorem1) shows that [Algorithm 1](#algorithm1) matches the optimal $Ld\ln T$ rate even without this *a-priori* knowledge.

###### Theorem 1 .

###### Proof.

###### Theorem 2 .

## 4 Two-bit Feedback

In this section, we focus on the two-bit feedback setting, corresponding to posted-price mechanisms.
We show that a simple deterministic rule that decides to either explore (by posting a price drawn uniformly in $[0,1]$ to gather feedback to reconstruct the cumulative distribution functions of the traders’ valuations) or exploit (by posting the scalar product of the context and the current ridge regression estimate of the unknown weight vector $\phi$) based on the amount of information gathered along the various context dimensions ([Algorithm 2](#algorithm2)) is enough to achieve $\widetilde{\mathcal{O}}\bigl{(}\sqrt{LdT}\bigr{)}$ regret.
We recall that $\boldsymbol{1}_{d}$ is the $d$-dimensional identity matrix. Also, for any positive definite matrix $A\in\mathbb{R}^{d\times d}$, we define
$\left\lVert\cdot\right\rVert_{A}\colon\mathbb{R}^{d}\to[0,\infty)$,
$v\mapsto\sqrt{v^{\top}Av}$.

Figure: Algorithm 2 Scouting Ridge Regression Pricing — Two-bit Feedback

###### Theorem 3 .

Consider the two-bit feedback setting introduced in [Section 1.1](#S1.SS1). If the learner runs [Algorithm 2](#algorithm2) and the traders’ valuations admit a density bounded by $L\geq 1$, then, for any time horizon $T$ such that $LT\geq 2d\ln\bigl{(}1+2d(T-1)\bigr{)}$, it holds that
$R_{T}\leq 1+4\sqrt{LdT\ln T}$.

###### Proof.

Without loss of generality we assume that $T\geq 2$.
Note that for any $t\in\mathbb{N}$, if $b_{t}=1$, then

$$ $\mathbb{E}[D_{t}]=\mathbb{P}[P_{t}\leq V_{t}]=\int_{0}^{1}\mathbb{P}[u\leq V_{t}]\,\mathrm{d}u=\mathbb{E}[V_{t}]=\mathbb{E}[c_{t}^{\top}\phi+\xi_{t}]=c_{t}^{\top}\phi\;,$ $$

and, analogously, $\mathbb{E}[E_{t}]=c_{t}^{\top}\phi$. It follows that $\mathbb{E}[Y_{t}^{\top}]=x_{t}^{\top}\phi$, for any $t\in\mathbb{N}$.
Now, for any $t\in\mathbb{N}$, using the very same arguments as in the proof of [Theorem 1](#Thmtheorem1), from the fact that $\mathbb{E}[Y_{t}^{\top}]=x_{t}^{\top}\phi$ we can deduce an analogous of ([3](#S3.Ex18)), and, from the fact that the variances of the random variables $D_{1},E_{1},\dots,D_{t},E_{t}$ (for the indexes for which they are defined) are less than or equal to $1$,
we can deduce an analogous of ([2](#S3.E2)).
These two results team up to yield a bound analogous to ([3](#S3.Ex20)): for $t\in\{2,3,\dots\}$,

$$ $\displaystyle\mathbb{E}\bigl{[}|c_{t}^{\top}\hat{\phi}_{t-1}-c_{t}^{\top}\phi|^{2}\bigr{]}\leq 2\left\lVert c_{t}\right\rVert_{\left(x_{t-1}^{\phantom{\top}}x_{t-1}^{\top}+d^{-1}\boldsymbol{1}_{d}\right)^{-1}}^{2}\;.$ $$

Hence, leveraging [Corollary 1](#Thmcorollary1), for any $T\in\mathbb{N}$, we have that

$$ $\displaystyle R_{T}$ $\displaystyle\leq\sum_{t=1}^{T}1\land\Bigl{(}L\mathbb{E}\left[|P_{t}-c_{t}^{\top}\phi|^{2}\right]\Bigr{)}\leq\sum_{t=2}^{T}(1-b_{t})L\mathbb{E}\left[|c_{t}^{\top}\hat{\phi}_{t-1}-c_{t}^{\top}\phi|^{2}\right]+\sum_{t=1}^{T}b_{t}$ $\displaystyle\leq L\sum_{t=2}^{T}(1-b_{t})\left\lVert\sqrt{2}c_{t}\right\rVert_{\left(x_{t-1}^{\phantom{\top}}x_{t-1}^{\top}+d^{-1}\boldsymbol{1}_{d}\right)^{-1}}^{2}+\sum_{t=1}^{T}b_{t}\leq\sqrt{2LdT\ln\bigl{(}1+2d(T-1)\bigr{)}}+\sum_{t=1}^{T}b_{t}\;.$ $$

Now, given that $LT/\bigl{(}2d\ln\bigl{(}1+2d(T-1)\bigr{)}\bigr{)}\geq 1$, using the convention $0/0=0$,

$$ $\displaystyle\sum_{t=2}^{T}b_{t}$ $\displaystyle=\sum_{t=2}^{T}\frac{b_{t}\left\lVert\sqrt{2}c_{t}\right\rVert_{\left(x_{t-1}^{\phantom{\top}}x_{t-1}^{\top}+d^{-1}\boldsymbol{1}_{d}\right)^{-1}}^{2}}{\left\lVert\sqrt{2}c_{t}\right\rVert_{\left(x_{t-1}^{\phantom{\top}}x_{t-1}^{\top}+d^{-1}\boldsymbol{1}_{d}\right)^{-1}}^{2}}\leq\sqrt{\frac{LT}{2d\ln(1+2d(T-1))}}\sum_{t=2}^{T}1\land b_{t}\left\lVert\sqrt{2}c_{t}\right\rVert_{\left(2\sum_{s=1}^{t-1}b_{s}c_{s}c_{s}^{\top}+d^{-1}\boldsymbol{1}_{d}\right)^{-1}}^{2}$ $\displaystyle=\sqrt{LT/\left(2d\ln\bigl{(}1+2d(T-1)\bigr{)}\right)}\sum_{t=1}^{T-1}1\wedge\left\lVert b_{t+1}\sqrt{2}c_{t+1}\right\rVert_{\left(\sum_{s=1}^{t}(b_{s}\sqrt{2}c_{s})(b_{s}\sqrt{2}c_{s})^{\top}+d^{-1}\boldsymbol{1}_{d}\right)^{-1}}^{2}\eqqcolon(*).$ $$

Using the elliptical potential lemma [, Lemma 19.4], we obtain

$$ $\displaystyle\sum_{t=1}^{T}b_{t}$ $\displaystyle\leq 1+(*)\leq 1+\sqrt{LT/\bigl{(}2d\ln\bigl{(}1+2d(T-1)\bigr{)}\bigr{)}}\cdot 2d\ln\bigl{(}1+2d(T-1)\bigr{)}=1+\sqrt{2LdT\ln\bigl{(}1+2d(T-1)\bigr{)}}\;.$ $$

Hence, if $d<T/2$, this implies that
$R_{T}\leq 1+2\sqrt{2LdT\ln\left(1+2d(T-1)\right)}\leq 1+4\sqrt{LdT\ln T}$.
On the other hand, if $d\geq T/2$, then, since $L\geq 1$, we obtain, again, $R_{T}\leq T\leq 1+4\sqrt{LdT\ln T}$.
∎

We conclude this section by stating a matching (up to logarithmic terms) worst-case $\Omega\bigl{(}\sqrt{LdT}\bigr{)}$ regret lower bound for any algorithm in the two-bit-feedback case, proving the optimality of [Algorithm 2](#algorithm2).

At a high level, the proof of this result is based on the same trick (as in the proof of [Theorem 2](#Thmtheorem2)) of choosing contexts equal to vectors of the canonical basis of $\mathbb{R}^{d}$ in order to obtain $d$ independent $1$-dimensional sub-instances.
In each block, an adaptation of the non-contextual full-feedback lower bound construction in [, Theorem 5] yields a lower bound of order $\sqrt{LT/d}$.
Summing over blocks gives the result.
For more details on the proof of this result, see [Appendix B](#A2).

###### Theorem 4 .

There exist two numerical constants $a,b>0$ such that, for any $L\geq 2$ and any time horizon $T\geq\max(4,adL^{3},2d)$, there exists a sequence of contexts $c_{1},\dots,c_{T}\in[0,1]^{d}$ such that, for any algorithm $\alpha$ for the contextual brokerage problem with two-bit feedback, there exists a vector $\phi\in[0,1]^{d}$ and two zero-mean independent sequences $(\xi_{t})_{t\in[T]}$ and $(\zeta_{t})_{t\in[T]}$ independent of each other such that, if we define $V_{t}\coloneqq c_{t}^{\top}\phi+\xi_{t}$ and $W_{t}\coloneqq c_{t}^{\top}\phi+\zeta_{t}$, then for each $t\in[T]$ it holds that $c_{t}^{\top}\phi\in[0,1]$, $V_{t}$ and $W_{t}$ are $[0,1]$-valued random variables with density bounded by $L$, and the regret of $\alpha$ on the sequence of traders’ valuations $V_{1},W_{1},\dots,V_{T},W_{T}$ satisfies
$R_{T}\geq b\sqrt{LdT}$.

We remark that the previous lower bound holds even for algorithms that have prior knowledge of the sequence of contexts $c_{1},c_{2},\dots$ and that [Theorem 3](#Thmtheorem3) shows that [Algorithm 2](#algorithm2) matches the optimal $\sqrt{LdT}$ rate (up to a $\sqrt{\ln T}$ factor) even without this *a-priori* knowledge.

###### Theorem 3 .

###### Proof.

###### Theorem 4 .

## 5 Beyond Bounded Densities

In this final section, we investigate the general case where the valuations of the traders are not assumed to have a bounded density, and we show that the problem is, in general, unlearnable.

At a high level, the main reason why the problem becomes unlearnable is that [Lemma 1](#Thmlemma1) and its [Corollary 1](#Thmcorollary1) fail to hold.
In fact, the optimal price at time $t$ depends in general not only on the market value $m_{t}=c_{t}^{\top}\phi$, but also on properties of the *time-varying* distributions of the perturbations $\xi_{t}$ and $\zeta_{t}$, which essentially turns our problem into a fully-adversarial one where we strive to compete against time-varying policies.
For a full proof of the following theorem, see [Appendix C](#A3).

###### Theorem 5 .

There exists a sequence of contexts $c_{1},c_{2},\dots\in[0,1]^{d}$ and a vector $\phi\in[0,1]^{d}$, such that for any algorithm $\alpha$ for the contextual brokerage problem under full feedback, there exists an independent sequence of zero mean random variables $\xi_{1},\zeta_{1},\xi_{2},\zeta_{2},\dots$, such that if the valuations of the traders at time $t$ are $V_{t}=c_{t}^{\top}\phi+\xi_{t}$ and $W_{t}=c_{t}^{\top}\phi+\zeta_{t}$, then $c_{t}^{\top}\phi\in[0,1]$, $V_{t},W_{t}$ are $[0,1]$-valued random variables, and the regret of $\alpha$ on the sequence of traders’ valuations $V_{1},W_{1},\dots,V_{T},W_{T}$ satisfies
$R_{T}=\Omega(T)$.

We remark that the previous unlearnability result holds even for algorithms that have prior knowledge of the sequence of contexts $c_{1},c_{2},\dots$ and, strikingly, of the vector $\phi$.

###### Theorem 5 .

## 6 Conclusions, Limitations, and Open Problems

Conclusions. Motivated by the real-life *desideratum* to exploit prior information on the traded assets, we investigated the noisy linear contextual online learning problem of brokerage between traders without predetermined seller/buyer roles.
We provided a complete picture with tight regret bounds in all the proposed settings, i.e., under full and two-bit feedback, and with or without regularity assumptions on the noise distributions, achieving tightness (up to $\log$ terms) in all relevant parameters.

Limitations and Open Problems.
One limitation of our work is the assumption that contexts have a linear relationship with market values.
While linearity is a common and reasonable assumption in contextual settings, exploring other relationships beyond the linear case would be interesting.
Another limitation of our setting is that it models traders’ valuations as noisy perturbations of the market value and does not encompass cases where contextual information on traders’ profiles is available.
We leave the study of these extensions to future research.

## Acknowledgements

The work of FB was supported by the Projects BOLD (ANR-19-CE23-0026) and GAP (ANR-21-CE40-0007) of the French National Research Agency (ANR).
RC is partially supported by the MUR PRIN grant 2022EKNE5K (Learning in Markets and Society), funded by the NextGenerationEU program within the PNRR scheme, the FAIR (Future Artificial Intelligence Research) project, funded by the NextGenerationEU program within the PNRR-PE-AI scheme, the EU Horizon CL4-2022-HUMAN-02 research and innovation action under grant agreement 101120237, project ELIAS (European Lighthouse of AI for Sustainability).
TC gratefully acknowledges the support of the University of Ottawa through grant GR002837 (Start-Up Funds) and that of the Natural Sciences and Engineering Research Council of Canada (NSERC) through grants RGPIN-2023-03688 (Discovery Grants Program) and DGECR2023-00208 (Discovery Grants Program, DGECR - Discovery Launch Supplement).

## Appendix A Proof of Theorem 2

Without loss of generality, we assume that $d$ divides $T$.
In fact, if we prove the theorem for this case, then, by leveraging that $T\geq 2d$ and $T\geq 4$, the general case follows from

$$ $R_{T}\geq bLd\ln\bigl{(}\left\lfloor T/d\right\rfloor d\bigr{)}\geq\frac{b}{2}Ld\ln T\;.$ $$

Let $n\coloneqq T/d$.
Let $e_{1},\dots,e_{d}$ be the canonical basis of $\mathbb{R}^{d}$.
Define, for all $i\in[d]$ and $j\in[n]$, the context $c_{j+(i-1)n}\coloneqq e_{i}$.
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\geq 2$,
$J_{L}\coloneqq\bigl{[}\frac{1}{2}-\frac{1}{14L},\frac{1}{2}+\frac{1}{14L}\bigr{]}$,
$f\coloneqq\mathbb{I}_{\left[0,\frac{3}{7}\right]}+L\mathbb{I}_{J_{L}}+\mathbb{I}_{\left[\frac{4}{7},1\right]}$,
and, for any $\varepsilon\in[-1,1]$,
$g_{\varepsilon}\coloneqq-\varepsilon\mathbb{I}_{\left[\frac{1}{7},\frac{3}{14}\right]}+\varepsilon\mathbb{I}_{\left(\frac{3}{14},\frac{2}{7}\right]}$
and $f_{\varepsilon}\coloneqq f+g_{\varepsilon}$
.
For any $\varepsilon\in[-1,1]$, note that $0\leq f_{\varepsilon}\leq L$ and $\int_{0}^{1}f_{\varepsilon}(x)\,\mathrm{d}x=1$, hence $f_{\varepsilon}$ is a valid density on $[0,1]$ bounded by $L$.
We will denote the corresponding probability measure by $\nu_{\varepsilon}$, set $\bar{\nu}_{\varepsilon}\coloneqq\int_{[0,1]}x\,\mathrm{d}\nu_{\varepsilon}(x)$, and notice that direct computations show that $\bar{\nu}_{\varepsilon}=\frac{1}{2}+\frac{\varepsilon}{196}$.
Consider for each $q\in[0,1]$, an i.i.d. sequence $(B_{q,t})_{t\in\mathbb{N}}$ of Bernoulli random variables of parameter $q$, an i.i.d. sequence $(\tilde{B}_{t})_{t\in\mathbb{N}}$ of Bernoulli random variables of parameter $1/7$, an i.i.d. sequence $(U_{t})_{t\in\mathbb{N}}$ of uniform random variables on $[0,1]$, and uniform random variables $E_{1},\dots,E_{d}$ on $[-\bar{\varepsilon}_{L},\bar{\varepsilon}_{L}]$, where $\bar{\varepsilon}_{L}:=\frac{7}{L}$, such that $\left((B_{q,t})_{t\in\mathbb{N},q\in[0,1]},(\tilde{B}_{t})_{t\in\mathbb{N}},(U_{t})_{t\in\mathbb{N}},E_{1},\dots,E_{d}\right)$ is an independent family.
Let $\varphi\colon[0,1]\to[0,1]$ be such that, if $U$ is a uniform random variable on $[0,1]$, then the distribution of $\varphi(U)$ has density $\frac{7}{6}\cdot f\cdot\mathbb{I}_{[0,1]\setminus[1/7,2/7]}$ (which exists by the Skorokhod representation theorem [, Section 17.3]).
For each $\varepsilon\in[-1,1]$ and $t\in\mathbb{N}$, define

$$ $G_{\varepsilon,t}\coloneqq\left(\frac{2+U_{t}}{14}(1-B_{\frac{1+\varepsilon}{2},t})+\frac{3+U_{t}}{14}B_{\frac{1+\varepsilon}{2},t}\right)\tilde{B}_{t}+\varphi(U_{t})(1-\tilde{B}_{t})\;,$ (4) $$

$V_{\varepsilon,t}\coloneqq G_{\varepsilon,2t-1}$, $W_{\varepsilon,t}\coloneqq G_{\varepsilon,2t}$, $\xi_{\varepsilon,t}\coloneqq V_{\varepsilon,t}-\bar{\nu}_{\varepsilon}$, and $\zeta_{\varepsilon,t}\coloneqq W_{\varepsilon,t}-\bar{\nu}_{\varepsilon}$.
In the following, if $a_{1},\dots,a_{d}$ is a sequence of elements, we will use the notation $a_{1:d}$ as a shorthand for $(a_{1},\dots,a_{d})$.
For each $\varepsilon_{1},\dots,\varepsilon_{d}\in[-1,1]$, each $i\in[d]$, and each $j\in[n]$, define the random variables $\xi^{\varepsilon_{1:d}}_{j+(i-1)n}\coloneqq\xi_{\varepsilon_{i},j+(i-1)n}$ and $\zeta^{\varepsilon_{1:d}}_{j+(i-1)n}\coloneqq\zeta_{\varepsilon_{i},j+(i-1)n}$.
The family $\bigl{(}\xi^{\varepsilon_{1:d}}_{t},\zeta^{\varepsilon_{1:d}}_{t}\bigr{)}_{t\in[T],\varepsilon_{1:d}\in[-1,1]^{d}}$ is an independent family, independent of $(E_{1},\dots,E_{d})$, and for each $i\in[d]$ and each $j\in[n]$ it can be checked that the two random variables $\xi^{\varepsilon_{1:d}}_{j+(i-1)n},\zeta^{\varepsilon_{1:d}}_{j+(i-1)n}$ are zero mean with common distribution given by $\nu_{\varepsilon_{i}}$.
For each $\varepsilon_{1},\dots,\varepsilon_{d}\in[-1,1]$, let $\phi_{\varepsilon_{1:d}}\coloneqq(\bar{\nu}_{\varepsilon_{1}},\dots,\bar{\nu}_{\varepsilon_{d}})$, and for each $i\in[d]$ and $j\in[n]$, let $V^{\varepsilon_{1:d}}_{j+(i-1)n}\coloneqq c^{\top}_{j+(i-1)n}\phi_{\varepsilon_{1:d}}+\xi^{\varepsilon_{1:d}}_{j+(i-1)n}$ and $W^{\varepsilon_{1:d}}_{j+(i-1)n}\coloneqq c^{\top}_{j+(i-1)n}\phi_{\varepsilon_{1:d}}+\zeta^{\varepsilon_{1:d}}_{j+(i-1)n}$.
Note that these last two random variables are $[0,1]$-valued zero-mean perturbations of $c^{\top}_{j+(i-1)n}\phi_{\varepsilon_{1:d}}$ with shared density given by $f_{\varepsilon_{i}}$, 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 $V^{\varepsilon_{1:d}}_{1},W^{\varepsilon_{1:d}}_{1},\dots,V^{\varepsilon_{1:d}}_{T},W^{\varepsilon_{1:d}}_{T}$, for some $\varepsilon_{1},\dots,\varepsilon_{d}\in[0,1]$.

Before doing that, we first need the following.
For any $\varepsilon_{1},\dots,\varepsilon_{d}\in[-1,1]$, $p\in[0,1]$, and $t\in[T]$ let $\mathrm{GFT}^{\varepsilon_{1:d}}_{t}(p)\coloneqq\mathrm{g}(p,V^{\varepsilon_{1:d}}_{t},W^{\varepsilon_{1:d}}_{t})$
.

By [Lemma 1](#Thmlemma1), we have, for all $\varepsilon_{1},\dots,\varepsilon_{d}\in[-1,1],i\in[d],j\in[n]$, and $p\in[0,1]$,

$$ $\mathbb{E}\bigl{[}\mathrm{GFT}^{\varepsilon_{1:d}}_{j+(i-1)n}(p)\bigr{]}=2\int_{0}^{p}\int_{0}^{\lambda}f_{\varepsilon_{i}}(s)\,\mathrm{d}s\,\mathrm{d}\lambda+2(\bar{\nu}_{\varepsilon_{i}}-p)\int_{0}^{p}f_{\varepsilon_{i}}(s)\,\mathrm{d}s\;,$ $$

which, together with the fundamental theorem of calculus —[, Theorem 14.16], noting that $p\mapsto\mathbb{E}\bigl{[}\mathrm{GFT}^{\varepsilon_{1:d}}_{j+(i-1)n}(p)\bigr{]}$ is absolutely continuous with derivative defined a.e. by $p\mapsto 2(\bar{\nu}_{\varepsilon_{i}}-p)f_{\varepsilon_{i}}(p)$— yields, for any $p\in J_{L}$,

$$ $\mathbb{E}\bigl{[}\mathrm{GFT}^{\varepsilon_{1:d}}_{j+(i-1)n}(\bar{\nu}_{\varepsilon_{i}})\bigr{]}-\mathbb{E}\bigl{[}\mathrm{GFT}^{\varepsilon_{1:d}}_{j+(i-1)n}(p)\bigr{]}=L|\bar{\nu}_{\varepsilon_{i}}-p|^{2}\;.$ (5) $$

Note also that for all $\varepsilon_{1},\dots,\varepsilon_{d}\in[-\bar{\varepsilon}_{L},\bar{\varepsilon}_{L}]$, $t\in[T]$, and $p\in[0,1]\setminus J_{L}$, a direct verification shows that

$$ $\mathbb{E}\bigl{[}\mathrm{GFT}^{\varepsilon_{1:d}}_{t}(p)\bigr{]}\leq\mathbb{E}\left[\mathrm{GFT}^{\varepsilon_{1:d}}_{t}\left(1/2\right)\right]\;.$ (6) $$

Fix any arbitrary deterministic algorithm for the full feedback setting $(\alpha_{t})_{t\in[T]}$, i.e., (given that the contexts $c_{1},\dots,c_{T}$ are here fixed and declared ahead of time to the learner), a sequence of functions $\alpha_{t}\colon\bigl{(}[0,1]\times[0,1]\bigr{)}^{t-1}\to[0,1]$ mapping past feedback into prices (with the convention that $\alpha_{1}$ is just a number in $[0,1]$). For each $t\in[T]$, define $\tilde{\alpha}_{t}\colon\bigl{(}[0,1]\times[0,1]\bigr{)}^{t-1}\to J_{L}$ equal to $\alpha_{t}$ whenever $\alpha_{t}$ takes values in $J_{L}$, and equal to $1/2$ otherwise.
Define $Z_{1}\coloneqq\frac{1+E_{1}}{2},\dots,Z_{d}\coloneqq\frac{1+E_{d}}{2}$.

Now, note the following

$$ $\displaystyle\sup_{\varepsilon_{1:d}\in[-\bar{\varepsilon}_{L},\bar{\varepsilon}_{L}]^{d}}\sum_{i=1}^{d}\sum_{j=1}^{n}\mathbb{E}\Bigl{[}\mathrm{GFT}^{\varepsilon_{1:d}}_{j+(i-1)n}(\bar{\nu}_{\varepsilon_{i}})-\mathrm{GFT}^{\varepsilon_{1:d}}_{j+(i-1)n}\bigl{(}\alpha_{t}(V^{\varepsilon_{1:d}}_{1},W^{\varepsilon_{1:d}}_{1},\dots,V^{\varepsilon_{1:d}}_{j-1+(i-1)n},W^{\varepsilon_{1:d}}_{j-1+(i-1)n})\bigr{)}\Bigr{]}$ $\displaystyle\;\overset{(\ref{e:reduction_to_J_L})}{\geq}\sup_{\varepsilon_{1:d}\in[-\bar{\varepsilon}_{L},\bar{\varepsilon}_{L}]^{d}}\sum_{i=1}^{d}\sum_{j=1}^{n}\mathbb{E}\Bigl{[}\mathrm{GFT}^{\varepsilon_{1:d}}_{j+(i-1)n}(\bar{\nu}_{\varepsilon_{i}})-\mathrm{GFT}^{\varepsilon_{1:d}}_{j+(i-1)n}\bigl{(}\tilde{\alpha}_{t}(V^{\varepsilon_{1:d}}_{1},W^{\varepsilon_{1:d}}_{1},\dots,V^{\varepsilon_{1:d}}_{j-1+(i-1)n}W^{\varepsilon_{1:d}}_{j-1+(i-1)n})\bigr{)}\Bigr{]}$ $\displaystyle\;\overset{\spadesuit}{=}L\sup_{\varepsilon_{1:d}\in[-\bar{\varepsilon}_{L},\bar{\varepsilon}_{L}]^{d}}\sum_{i=1}^{d}\sum_{j=1}^{n}\mathbb{E}\Bigl{[}\bigl{\lvert}\bar{\nu}_{\varepsilon_{i}}-\tilde{\alpha}_{t}(V^{\varepsilon_{1:d}}_{1},W^{\varepsilon_{1:d}}_{1},\dots,V^{\varepsilon_{1:d}}_{j-1+(i-1)n},W^{\varepsilon_{1:d}}_{j-1+(i-1)n})\bigr{\rvert}^{2}\Bigr{]}$ $\displaystyle\;\geq L\sum_{i=1}^{d}\sum_{j=1}^{n}\mathbb{E}\Bigl{[}\bigl{\lvert}\bar{\nu}_{E_{i}}-\tilde{\alpha}_{t}(V^{E_{1:d}}_{1},W^{E_{1:d}}_{1},\dots,V^{E_{1:d}}_{j-1+(i-1)n},W^{E_{1:d}}_{j-1+(i-1)n})\bigr{\rvert}^{2}\Bigr{]}$ $\displaystyle\;\overset{\varheartsuit}{\geq}L\sum_{i=1}^{d}\sum_{j=1}^{n}\mathbb{E}\Bigl{[}\bigl{\lvert}\bar{\nu}_{E_{i}}-\mathbb{E}[\bar{\nu}_{E_{i}}\mid V^{E_{1:d}}_{1},W^{E_{1:d}}_{1},\dots,V^{E_{1:d}}_{j-1+(i-1)n},W^{E_{1:d}}_{j-1+(i-1)n}]\bigr{\rvert}^{2}\Bigr{]}$ $\displaystyle\;=\frac{L}{196}\sum_{i=1}^{d}\sum_{j=1}^{n}\mathbb{E}\Bigl{[}\bigl{\lvert}E_{i}-\mathbb{E}[E_{i}\mid V^{E_{1:d}}_{1},W^{E_{1:d}}_{1}\dots,V^{E_{1:d}}_{j-1+(i-1)n},W^{E_{1:d}}_{j-1+(i-1)n}]\bigr{\rvert}^{2}\Bigr{]}$ $\displaystyle\;\overset{\vardiamondsuit}{\geq}\frac{L}{196}\sum_{i=1}^{d}\sum_{j=1}^{n}\mathbb{E}\Bigl{[}\bigl{\lvert}E_{i}-\mathbb{E}[E_{i}\mid B_{\frac{1+E_{i}}{2},1+2(i-1)n},\dots,B_{\frac{1+E_{i}}{2},2(j-1)+2(i-1)n}]\bigr{\rvert}^{2}\Bigr{]}$ $\displaystyle\;\overset{\clubsuit}{=}\frac{L}{196}\sum_{i=1}^{d}\sum_{j=1}^{n}\mathbb{E}\Bigl{[}\bigl{\lvert}E_{i}-\mathbb{E}[E_{i}\mid B_{\frac{1+E_{i}}{2},1},\dots,B_{\frac{1+E_{i}}{2},2(j-1)}]\bigr{\rvert}^{2}\Bigr{]}$ $\displaystyle\;=\frac{L}{49}\sum_{i=1}^{d}\sum_{j=1}^{n}\mathbb{E}\Bigl{[}\bigl{\lvert}Z_{i}-\mathbb{E}[Z_{i}\mid B_{Z_{i},1},\dots,B_{Z_{i},2(j-1)}]\bigr{\rvert}^{2}\Bigr{]}$ $$

where follows from ([5](#A1.E5)) and the fact that $\tilde{\alpha}_{t}$ takes values in $J_{L}$;
from the fact that the minimizer of the $L^{2}(\mathbb{P})$-distance from $\bar{\nu}_{E_{i}}$ in $\sigma(V^{E_{1:d}}_{1},W^{E_{1:d}}_{1},\dots,V^{E_{1:d}}_{j-1+(i-1)n},W^{E_{1:d}}_{j-1+(i-1)n})$ is $\mathbb{E}\bigl{[}\bar{\nu}_{E_{i}}\mid V^{E_{1:d}}_{1},W^{E_{1:d}}_{1},\dots,V^{E_{1:d}}_{j-1+(i-1)n},W^{E_{1:d}}_{j-1+(i-1)n}\bigr{]}$ (see, e.g., [, Section 9.4]);
follows from the fact that, by [Equation 4](#A1.E4) and the independence of $E_{i}$ from $\left((B_{q,t})_{t\in\mathbb{N},q\in[0,1]},(\tilde{B}_{t})_{t\in\mathbb{N}},(U_{t})_{t\in\mathbb{N}}\right)$, the conditional expectation $\mathbb{E}\bigl{[}E_{i}\mid V^{E_{1:d}}_{1},W^{E_{1:d}}_{1},\dots,V^{E_{1:d}}_{j-1+(i-1)n},W^{E_{1:d}}_{j-1+(i-1)n}\bigr{]}$ is a measurable function of $B_{\frac{1+E_{i}}{2},1+2(i-1)n},\dots,B_{\frac{1+E_{i}}{2},2(j-1)+2(i-1)n}$, together with the same observation made in about the minimization of $L^{2}(\mathbb{P})$ distance; and follows from the fact that the sequence $\left(B_{\frac{1+E_{i}}{2},t}\right)_{t\in\mathbb{N}}$ 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-\bar{\varepsilon}_{L})/2,(1+\bar{\varepsilon}_{L})/2]$) of an i.i.d. sequence of Bernoulli 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 $\tilde{a},\tilde{b}>0$ such that, for all $j\geq\tilde{b}L^{4}$ and each $i\in[d]$,

$$ $\mathbb{E}\Bigl{[}\bigl{\lvert}Z_{i}-\mathbb{E}[Z_{i}\mid B_{Z_{i},1},\dots,B_{Z_{i},2(j-1)}]\bigr{\rvert}^{2}\Bigr{]}\geq\tilde{a}\frac{1}{j-1}\;.$ (7) $$

At a high level, this is because, in an event of probability $\Omega(1)$, if $j$ is large enough, the conditional expectation $\mathbb{E}[Z_{i}\mid B_{Z_{i},1},\dots,B_{Z_{i},2(j-1)}]$ is very close to the empirical average $\frac{1}{2(j-1)}\sum_{s=1}^{2(j-1)}B_{Z_{i},s}$, whose expected squared distance from $Z$ is $\Omega\bigl{(}1/(j-1)\bigr{)}$.
For a formal proof of ([7](#A1.E7)) with explicit constants, we refer the reader to [, Appendix B of the extended arxiv version].
Summing over $i\in[d]$ and $j\in[n]$, we obtain that there exist $\varepsilon_{1},\dots,\varepsilon_{d}\in[-1,1]^{d}$ such that

$$ $\displaystyle\sum_{i=1}^{d}\sum_{j=1}^{n}\mathbb{E}\Bigl{[}\mathrm{GFT}^{\varepsilon_{1:d}}_{j+(i-1)n}(\bar{\nu}_{\varepsilon_{i}})-\mathrm{GFT}^{\varepsilon_{1:d}}_{j+(i-1)n}\bigl{(}\tilde{\alpha}_{t}(V^{\varepsilon_{1:d}}_{1},W^{\varepsilon_{1:d}}_{1},\dots,V^{\varepsilon_{1:d}}_{j-1+(i-1)n},W^{\varepsilon_{1:d}}_{j-1+(i-1)n})\bigr{)}\Bigr{]}$ $\displaystyle\qquad=\Omega(Ld\ln n)=\Omega(Ld\ln T)\;.$ $$

## Appendix B Proof of Theorem 4

Fix $L\geq 2$ and $T\in\mathbb{N}$.
We will use the very same notation as in the proof of [Theorem 2](#Thmtheorem2). In particular, the contexts $c_{1},\dots,c_{T}$ 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 $R_{T}^{\varepsilon_{1:d}}$ is the regret of the algorithm at time horizon $T$ when the traders’ valuations are $V^{\varepsilon_{1:d}}_{1},W^{\varepsilon_{1:d}}_{1},\dots,V^{\varepsilon_{1:d}}_{T},W^{\varepsilon_{1:d}}_{T}$, then $\max_{\sigma_{1:d}\in\{-1,1\}^{d}}R_{T}^{(\sigma_{1}\varepsilon,\dots,\sigma_{d}\varepsilon)}=\Omega\bigl{(}\sqrt{dLT}\bigr{)}$ if $\varepsilon=\Theta\bigl{(}(LT/d)^{-1/4}\bigr{)}$ and $T=\Omega(dL^{3})$.

Note that for all $\varepsilon_{1:d}\in[-1,1]^{d}$, $i\in[d]$, $j\in[n]$, and $p<\frac{1}{2}$, if $\varepsilon_{i}>0$, then, a direct verification shows that

$$ $\mathbb{E}\left[\mathrm{GFT}^{\varepsilon_{1:d}}_{j+(i-1)n}\left(1/2\right)\right]\geq\mathbb{E}\bigl{[}\mathrm{GFT}^{\varepsilon_{1:d}}_{j+(i-1)n}(p)\bigr{]}\;.$ (8) $$

Similarly, for all $\varepsilon_{1:d}\in[-1,1]^{d}$, $i\in[d]$, $j\in[n]$, and $p>\frac{1}{2}$, if $\varepsilon_{i}<0$, then

$$ $\mathbb{E}\left[\mathrm{GFT}^{\varepsilon_{1:d}}_{j+(i-1)n}\left(1/2\right)\right]\geq\mathbb{E}\bigl{[}\mathrm{GFT}^{\varepsilon_{1:d}}_{j+(i-1)n}(p)\bigr{]}\;.$ (9) $$

Furthermore, a direct verification shows that, for each $\varepsilon_{1:d}\in[-1,1]^{d}$ and $t\in[T]$,

$$ $\max_{p\in[0,1]}\mathbb{E}\bigl{[}\mathrm{GFT}^{\varepsilon_{1:d}}_{t}(p)\bigr{]}-\max_{p\in[\frac{1}{7},\frac{2}{7}]}\mathbb{E}\bigl{[}\mathrm{GFT}^{\varepsilon_{1:d}}_{t}(p)\bigr{]}\geq\frac{1}{50}=\Omega(1)\;.$ (10) $$

Now, assume that $T\geq dL^{3}/14^{4}$ so that, defining $\varepsilon\coloneqq(LT/d)^{-1/4}$, we have that for any $\sigma_{1:d}\in\{-1,1\}^{d}$, any $i\in[d]$ and any $j\in[n]$, the maximizer of the expected gain from trade $p\mapsto\mathbb{E}\bigl{[}\mathrm{GFT}^{(\sigma_{1}\varepsilon,\dots,\sigma_{d}\varepsilon)}_{j+(i-1)n}(p)\bigr{]}$ is at $\frac{1}{2}+\frac{\sigma_{i}\varepsilon}{196}$ and hence belongs to the spike region $J_{L}$.
If $\sigma_{i}=1$ (resp., $\sigma_{i}=-1$) case, the optimal price for the rounds $1+(i-1)n,\dots,in$ belongs to the region $\bigl{(}\frac{1}{2},\frac{1}{2}+\frac{1}{14L}\bigr{]}$ (resp., $\bigl{[}\frac{1}{2}-\frac{1}{14L},\frac{1}{2}\bigr{)}$).
By posting prices in the wrong region $\bigl{[}0,\frac{1}{2}\bigr{]}$ (resp., $\bigl{[}\frac{1}{2},1\bigr{]}$) in the $\sigma_{i}=1$ (resp., $\sigma_{i}=-1$) case, the learner incurs a $\Omega(L\varepsilon^{2})=\Omega\bigl{(}\sqrt{L/dT}\bigr{)}$ instantaneous regret by ([5](#A1.E5)) and ([8](#A2.E8)) (resp., ([5](#A1.E5)) and ([9](#A2.E9))).
Then, in order to attempt suffering less than $\Omega\bigl{(}\sqrt{L/T}\cdot n\bigr{)}=\Omega\bigl{(}\sqrt{LT/d}\bigr{)}$ regret in the rounds $1+(i-1)n,\dots,in$, the algorithm would have to detect the sign of $\sigma_{i}$ 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 of the cost of determining the sign of $\sigma_{i}$ with the available feedback.
Since for any $i\in[d]$ and $j\in[n]$, the feedback received from the two traders at time $j+(i-1)n$ by posting a price $p$ is $\mathbb{I}\{p\leq V^{(\sigma_{1}\varepsilon,\dots,\sigma_{d}\varepsilon)}_{j+(i-1)n}\}$ and $\mathbb{I}\{p\leq W^{(\sigma_{1}\varepsilon,\dots,\sigma_{d}\varepsilon)}_{j+(i-1)n}\}$, the only way to obtain information about (the sign of) $\sigma_{i}$ is to post in the costly ($\Omega(1)$-instantaneous regret by [Equation 10](#A2.E10)) sub-optimal region $[\frac{1}{7},\frac{2}{7}]$
.
However, posting prices in the region $[\frac{1}{7},\frac{2}{7}]$ at time $j+(i-1)n$ can’t give more information about $\sigma_{i}$ than the information carried by $V^{(\sigma_{1}\varepsilon,\dots,\sigma_{d}\varepsilon)}_{j+(i-1)n}$ and $W^{(\sigma_{1}\varepsilon,\dots,\sigma_{d}\varepsilon)}_{j+(i-1)n}$, which, in turn, can’t give more information about $\sigma_{i}$ than the information carried by the two Bernoullis $B_{\frac{1+\sigma_{i}\varepsilon}{2},2(j+(i-1)n)-1}$ and $B_{\frac{1+\sigma_{i}\varepsilon}{2},2(j+(i-1)n)}$.
Since only during rounds $1+(i-1)n,\dots,in$ is possible to extract information about the sign of $\sigma_{i}$ and, (via an information-theoretic argument) in order to distinguish the sign of $\sigma_{i}$ having access to i.i.d. Bernoulli random variables of parameter $\frac{1+\sigma_{i}\varepsilon}{2}$ requires $\Omega(1/\varepsilon^{2})=\Omega\bigl{(}\sqrt{LT/d}\bigr{)}$ samples, we are forced to post at least $\Omega\bigl{(}\sqrt{LT/d}\bigr{)}$ prices in the costly region $\bigl{[}\frac{1}{7},\frac{2}{7}\bigr{]}$ during the rounds $1+(i-1)n,\dots,in$ suffering a regret of $\Omega\bigl{(}\sqrt{LT/d}\bigr{)}\cdot\Omega(1)=\Omega\bigl{(}\sqrt{LT/d}\bigr{)}$.
Putting everything together, no matter what the strategy, each algorithm will pay at least $\Omega\bigl{(}\sqrt{LT/d}\bigr{)}$ regret in each epoch $1+(i-1)n,\dots,in$ for every $i\in[d]$, resulting in an overall regret of $\Omega\bigl{(}\sqrt{LT/d}\bigr{)}\cdot d=\Omega\bigl{(}\sqrt{dLT}\bigr{)}$.

## Appendix C Proof of Theorem 5

Assume that $d\geq 2$ (for the case $d=1$, the following proof can be adapted straightforwardly by defining $\phi=1$ and $c_{t}=1/2+\varepsilon_{t}$, where $\varepsilon_{t}$ is an arbitrary small sequence of biases).
Let $(a_{t})_{t\in\mathbb{N}}$ be a sequence of distinct elements in $[0,1]$ and, for all $t\in\mathbb{N}$, let $c_{t}\coloneqq(a_{t},1-a_{t},0,0,\dots,0)$.
Notice that $(c_{t})_{t\in\mathbb{N}}$ is a sequence of distinct elements in $[0,1]^{2}$.
Define $\phi\coloneqq(1/2,1/2,0,0,\dots,0)$.
Notice that for each $t\in\mathbb{N}$ it holds that $c_{t}^{\top}\phi=1/2$.
Let $\varepsilon\in(0,1/16)$.
For any $\theta\in\{0,1\}$, consider the following probability distribution

$$ $\mu_{\theta}\coloneqq\left(\frac{1}{4}+(1-2\theta)\varepsilon\right)\delta_{-\frac{1}{2}}+\frac{1}{2}\delta_{2(1-\theta)\varepsilon-2\theta\varepsilon}+\left(\frac{1}{4}-(1-2\theta)\varepsilon\right)\delta_{\frac{1}{2}}\;,$ $$

where for any $a\in\mathbb{R}$, $\delta_{a}$ is the Dirac’s delta probability distribution centered in $a$.
Consider an independent family of random variables $(\xi_{t,\theta},\zeta_{t,\theta})_{t\in\mathbb{N},\theta\in\{0,1\}}$
such that for any $t\in\mathbb{N}$ and any $\theta\in\{0,1\}$, we have that both $\xi_{t,\theta}$ and $\zeta_{t,\theta}$ are random variables with common distribution $\mu_{\theta}$.
Notice that for each $t\in\mathbb{N}$ and each $\theta\in\{0,1\}$ we have that $\mathbb{E}[\xi_{t,\theta}]=0=\mathbb{E}[\zeta_{t,\theta}]$.
Define, for each $t\in\mathbb{N}$ and each $\theta\in\{0,1\}$, the random variables $V_{t,\theta}\coloneqq c_{t}^{\top}\phi+\xi_{t}$ and $W_{t,\theta}\coloneqq c_{t}^{\top}\phi+\zeta_{t}$. Notice that these are $[0,1]$-valued random variables and that $(V_{t,\theta},W_{t,\theta})_{t\in\mathbb{N},\theta\in\{0,1\}}$ is an independent family.
Now, for each $\theta\in\{0,1\}$ and each $t\in\mathbb{N}$, let

$$ $p^{\#}(\theta)\in\operatorname*{argmax}_{p\in[0,1]}\mathbb{E}\Bigl{[}\mathrm{g}\bigl{(}p,V_{t,\theta},W_{t,\theta}\bigr{)}\Bigr{]}\;,$ $$

which does exist because the function $[0,1]\to[0,1],p\mapsto\mathbb{E}\Bigl{[}\mathrm{g}\bigl{(}p,V_{t,\theta},W_{t,\theta}\bigr{)}\Bigr{]}$ is upper semicontinuous (this can be proved as in [, Appendix B]) and defined on a compact set. Furthermore, note that the previous definition is independent of $t$ because, for any $\theta\in\{0,1\}$, the pairs $(V_{t_{1},\theta},W_{t_{1},\theta})$ and $(V_{t_{2},\theta},W_{t_{2},\theta})$ share the same distribution for every $t_{1},t_{2}\in\mathbb{N}$.
Fix a learning algorithm for the full-feedback contextual brokerage problem, fix a time horizon $T\in\mathbb{N}$, and notice that since the contexts $c_{1},c_{2},\dots$ are all distinct, it follows that

$$ $\displaystyle\max_{\theta_{1},\dots,\theta_{T}\in\{0,1\}^{T}}\sup_{p^{\star}\colon[0,1]^{d}\to[0,1]}\mathbb{E}\biggl{[}\sum_{t=1}^{T}\Bigl{(}\mathrm{g}\bigl{(}p^{\star}(c_{t}),V_{t,\theta_{t}},W_{t,\theta_{t}}\bigr{)}-\mathrm{g}(P_{t},V_{t,\theta_{t}},W_{t,\theta_{t}})\Bigr{)}\biggr{]}$ $\displaystyle\quad=\max_{\theta_{1},\dots,\theta_{T}\in\{0,1\}^{T}}\sum_{t=1}^{T}\left(\sup_{p\in[0,1]}\mathbb{E}\bigl{[}\mathrm{g}(p,V_{t,\theta_{t}},W_{t,\theta_{t}})\bigr{]}-\mathbb{E}\bigl{[}\mathrm{g}(P_{t},V_{t,\theta_{t}},W_{t,\theta_{t}})\bigr{]}\right)$ $\displaystyle\quad=\max_{\theta_{1},\dots,\theta_{T}\in\{0,1\}^{T}}\mathbb{E}\left[\sum_{t=1}^{T}\Bigl{(}\mathrm{g}\bigl{(}p^{\#}(\theta_{t}),V_{t,\theta_{t}},W_{t,\theta_{t}}\bigr{)}-\mathrm{g}(P_{t},V_{t,\theta_{t}},W_{t,\theta_{t}})\Bigr{)}\right]\eqqcolon(\#)\;.$ $$

Now, consider an i.i.d. family of Bernoulli random variables $(\Theta_{t})_{t\in\mathbb{N}}$ with parameter $1/2$, independent of the whole family $(V_{t,\theta},W_{t,\theta})_{t\in\mathbb{N},\theta\in\{0,1\}}$.
We have that

$$ $\displaystyle(\#)$ $\displaystyle\geq\mathbb{E}\left[\sum_{t=1}^{T}\Bigl{(}\mathrm{g}\bigl{(}p^{\#}(\Theta_{t}),V_{t,\Theta_{t}},W_{t,\Theta_{t}}\bigr{)}-\mathrm{g}(P_{t},V_{t,\Theta_{t}},W_{t,\Theta_{t}})\Bigr{)}\right]$ $\displaystyle=\sum_{t=1}^{T}\biggl{(}\mathbb{E}\Bigl{[}\mathrm{g}\bigl{(}p^{\#}(\Theta_{t}),V_{t,\Theta_{t}},W_{t,\Theta_{t}}\bigr{)}\Bigr{]}-\mathbb{E}\bigl{[}\mathrm{g}(P_{t},V_{t,\Theta_{t}},W_{t,\Theta_{t}})\bigr{]}\biggr{)}\eqqcolon(\$)$ $$

Now, for each $t\in[T]$, we see that

$$ $\displaystyle\mathbb{E}\Bigl{[}\mathrm{g}\bigl{(}p^{\#}(\Theta_{t}),V_{t,\Theta_{t}},W_{t,\Theta_{t}}\bigr{)}\Bigr{]}$ $\displaystyle=\mathbb{E}\biggl{[}\mathbb{E}\Bigl{[}\mathrm{g}\bigl{(}p^{\#}(\Theta_{t}),V_{t,\Theta_{t}},W_{t,\Theta_{t}}\bigr{)}\mid\Theta_{t}\Bigr{]}\biggr{]}$ $\displaystyle=\mathbb{E}\biggl{[}\max_{p\in[0,1]}\mathbb{E}\Bigl{[}\mathrm{g}\bigl{(}p,V_{t,\Theta_{t}},W_{t,\Theta_{t}}\bigr{)}\mid\Theta_{t}\Bigr{]}\biggr{]}$ $$

and long but straightforward computations show that, for each $p\in[0,1]$, it holds that

$$ $\displaystyle\mathbb{E}\Bigl{[}\mathrm{g}\bigl{(}p,V_{t,\Theta_{t}},W_{t,\Theta_{t}}\bigr{)}\mid\Theta_{t}\Bigr{]}=\begin{cases}\frac{1}{4}+\varepsilon(1-2\Theta_{t})&\text{ if }0\leq p<\frac{1}{2}-2\Theta_{t}\varepsilon+2(1-\Theta_{t})\varepsilon\;,\\ \frac{3}{8}+2\varepsilon^{2}&\text{ if }p=\frac{1}{2}-2\Theta_{t}\varepsilon+2(1-\Theta_{t})\varepsilon\;,\\ \frac{1}{4}-\varepsilon(1-2\Theta_{t})&\text{ if }\frac{1}{2}-2\Theta_{t}\varepsilon+2(1-\Theta_{t})\varepsilon<p\leq 1\;,\end{cases}$ $$

from which it follows that

$$ $\displaystyle\max_{p\in[0,1]}\mathbb{E}\Bigl{[}\mathrm{g}\bigl{(}p,V_{t,\Theta_{t}},W_{t,\Theta_{t}}\bigr{)}\mid\Theta_{t}\Bigr{]}=\frac{3}{8}+2\varepsilon^{2}\;.$ $$

On the other hand, for each $t\in[T]$, leveraging the freezing lemma [, Lemma 8], we have that

$$ $\displaystyle\mathbb{E}\bigl{[}\mathrm{g}(P_{t},V_{t,\Theta_{t}},W_{t,\Theta_{t}})\bigr{]}$ $\displaystyle=\mathbb{E}\Bigl{[}\mathbb{E}\bigl{[}\mathrm{g}(P_{t},V_{t,\Theta_{t}},W_{t,\Theta_{t}})\mid P_{t}\bigr{]}\Bigr{]}=\mathbb{E}\biggl{[}\Bigl{[}\mathbb{E}\bigl{[}\mathrm{g}(p,V_{t,\Theta_{t}},W_{t,\Theta_{t}})\bigr{]}\Bigr{]}_{p=P_{t}}\biggr{]}$ $\displaystyle=\mathbb{E}\biggl{[}\left[\frac{1}{2}\mathbb{E}\bigl{[}\mathrm{g}(p,V_{t,\Theta_{t}},W_{t,\Theta_{t}})\mid\Theta_{t}=0\bigr{]}+\frac{1}{2}\mathbb{E}\bigl{[}\mathrm{g}(p,V_{t,\Theta_{t}},W_{t,\Theta_{t}})\mid\Theta_{t}=1\bigr{]}\right]_{p=P_{t}}\biggr{]}$ $$

and again, tedious but straightforward computations show that, for each $p\in[0,1]$, it holds that

$$ $\displaystyle\frac{1}{2}\mathbb{E}\bigl{[}\mathrm{g}(p,V_{t,\Theta_{t}},W_{t,\Theta_{t}})\mid\Theta_{t}=0\bigr{]}+\frac{1}{2}\mathbb{E}\bigl{[}\mathrm{g}(p,V_{t,\Theta_{t}},W_{t,\Theta_{t}})\mid\Theta_{t}=1\bigr{]}$ $\displaystyle\quad=\frac{1}{4}\left(\mathbb{I}\left\{p<\frac{1}{2}-2\varepsilon\right\}+\mathbb{I}\left\{\frac{1}{2}+2\varepsilon<p\right\}\right)+\left(\frac{5}{16}+\frac{\varepsilon}{2}+\varepsilon^{2}\right)\left(\mathbb{I}\left\{p=\frac{1}{2}-2\varepsilon\right\}+\mathbb{I}\left\{p=\frac{1}{2}+2\varepsilon\right\}\right)$ $\displaystyle\qquad+\left(\frac{1}{4}+\varepsilon\right)\mathbb{I}\left\{\frac{1}{2}-2\varepsilon<p<\frac{1}{2}+2\varepsilon\right\}$ $\displaystyle\quad\leq\frac{5}{16}+\frac{\varepsilon}{2}+\varepsilon^{2}\;.$ $$

We conclude that

$$ $(\$)\geq\frac{T}{16}+\left(\varepsilon^{2}-\frac{\varepsilon}{2}\right)T\;,$ $$

from which it follows that there exists $\theta_{1},\dots,\theta_{T}\in\{0,1\}$ such that

$$ $\sup_{p^{\star}\colon[0,1]^{d}\to[0,1]}\mathbb{E}\biggl{[}\sum_{t=1}^{T}\Bigl{(}\mathrm{g}\bigl{(}p^{\star}(c_{t}),V_{t,\theta_{t}},W_{t,\theta_{t}}\bigr{)}-\mathrm{g}(P_{t},V_{t,\theta_{t}},W_{t,\theta_{t}})\Bigr{)}\biggr{]}\geq\frac{T}{16}+\left(\varepsilon^{2}-\frac{\varepsilon}{2}\right)T\geq\frac{T}{32}\;.$ $$

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 5
presentation: 4
questions: One question regarding the comparison with https://arxiv.org/abs/2405.18183, it seems in their paper, they show a matching lower bound $T^{2/3}$ for the two-bit feedback model, noisy distribution, strong budget balance (propose the same trading price for seller and buyer, which is the same as your setting), however, you achieved $O(\sqrt{T\log T})$ regret. Can you elaborate a bit more here? Is it because the seller and buyer in your setting shares the same expected valuation (market price)?
soundness: 3
strengths: The paper analyzes a very interesting problem, online bilateral trade. I am not quite convinced the algorithm proposed in this paper will be very useful in practice or can be really applied to any real system, but this is still an interesting theoretical paper and my review is mainly based on this point.

The theoretical analysis is sound and the conveys a complete story.

The paper is well written.
summary: This paper analyzes the problem of online learning of bilateral trading in the contextual setting. The authors provide a comprehensive regret analysis for different feedback settings. In particular, the authors analyze two feeback models, full information feedback model and the two-bit feedback and they show tight regret analysis (upper bound and matching lower bounds) for both settings.
weaknesses: I am not convinced the paper passes the bar of ICLR.

This paper seems an extension to the previous paper "An online learning theory of brokerage" and generalizes the results to the contextual setting. Can you elaborate more what is the main challenge this paper addresses on top of the previous paper?

Some related work is missing https://arxiv.org/abs/2405.18183, which has been posted to ArXiv this May, that analyzes a very similar setting, where the authors in that paper also discussed single-bit feedback model. If possible, can the authors compare a bit with that one?

---

confidence: 3
contribution: 1
initial_rating: 5
presentation: 3
questions: - It seems the broker is completely altruistic. Could brokers not typically profit by imposing a spread between buy and sell prices? So, could $ p $ be a range rather than a single point, and what impact would this have on the current work?
- What would happen if the buyer and seller did not declare their prices truthfully? (This is more of an extension question, but in an open market, this seems like the more common case.)
- Since Lemma 1 reaches the same conclusion as Thm 2.3 in [1], couldn’t we simply use the result from [1]?
- Why must the buyer and seller have the same valuation? Could $ E[V] \neq E[W] $?
- If I understand correctly, Thms. 2 and 4 state that it’s impossible to have sub-logarithmic performance guarantees for a specific sequence of contexts. In what ways is this significant to the paper? And how could it be relevant for future work?
soundness: 3
strengths: - This paper addresses a very relevant and practical economic problem: brokering a sale between parties under a fair valuation for a product, involving quantified uncertainty.
- The mathematical tools used to obtain the theoretical results are advanced and innovative.
- The proofs are rigorous, and some theorems provide non-trivial results, especially regarding the learnability of the problem under specific circumstances.

An additional note: Theorem 5 stipulates that there will be best-case linear regret with an unbounded $ L $, making a finite $ L > 1 $ a valid requirement. However, from my perspective, the assumption of a finite $ L $ in a bounded interval is quite mild, and it's safe to say that most random distributions in this economic setting would adhere to it.
summary: This paper discusses online bandit learning for bilateral trade and is largely a follow-up to [1]. In this brokerage game, a buyer and seller share equal valuations on average, and it is the strategy of the broker to set the brokerage price, $ p $, as close as possible to this amount, $ m $, to maximize the "gain from trade." A sale only occurs when $ p $ falls between realized values $ V $ and $ W $, which are random variables distributed around $ m $. This repeated online learning setting was investigated in [1], and the current work adds a context that causally affects $ E[m] $ via a set of $ d $ parameters. The paper presents two problem settings identical to [1]: full-feedback, where the realized valuations of the buyer and seller are revealed to the agent, and two-bit feedback, where only whether a sale occurred is revealed, making it more challenging. Two algorithms based on ridge regression are proposed to address this problem, each providing logarithmic regret bounds. Additional theorems establish a lower bound on regret under specific revelation of context sequences, and the final theorem, Theorem 5, addresses the (un)learnability of this problem when a core bounded probability assumption is lifted.

[1] Bolić, Nataša, Tommaso Cesari, and Roberto Colomboni. "An online learning theory of brokerage." arXiv preprint arXiv:2310.12107 (2023).
weaknesses: - The major weakness is the level of contribution compared to previous work [1] and the amount of verbatim text copied from one document to another. As mentioned, the problem setting is almost identical, except that additional context is provided. A word-for-word comparison between the two documents shows high similarity scores for the first half of the document. If this is a follow-up to [1], it should be stated more clearly, and some redundancy could be reduced by not rewriting the exact same language from [1] in the current draft.
- In reviewing the theoretical results, there seems to be some repetition: Lemma 1 provides the same result as Thm 2.3 in [1], and Theorems 1 and 3 demonstrate almost identical regret bounds as Algorithm 1 and 2 in [1], albeit with different algorithms and arguments. This somewhat reduces the degree of contribution, as adding context to the same problem as [1] results in finding a new algorithm that retains nearly identical regret bounds as [1], which makes the result rather incremental.
- Economic assumptions: The assumption that both the buyer and seller have the exact same valuation seems somewhat unrealistic. Isn’t it generally the case that, in markets, parties value goods differently? Furthermore, why should agents act under a true valuation? Could they not be strategic in their decisions? It also appears that the broker is entirely altruistic—facilitating a trade but seemingly not profiting from it.

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: I am wondering if some results could be also obtained if the learner only has one-bit feedback, namely only observe whether the trade happens or not.
soundness: 3
strengths: The studied problem is well-motivated and interesting. Previous works approaching bilateral trade problem focus on a context-free setting, while this work introduces context to the problem. Obtaining tight regret bounds are not trivial in this contextual setting. A nice result of this paper is that they also establish the necessities of the bounded density assumption.
summary: The paper studies a online contextual brokerage problem. The game operates as follows: At each time round $t$:  

1. two traders arrive with private valuations $V_t, W_t$ arrives. 
2. the broker observes a context $c_t\in\mathbb{R}^d$ and proposes a price $P_t$
3. if the price $P_t$ is between the lowest valuation $V_t\vee W_t$ and highest valuation $V_t\wedge W_t$ (meaning the trader with the minimum valuation is ready to sell at $P_t$ and the trader with the maximum valuation is eager to buy at $P_t$), the asset is bought by the trader with the highest valuation from the trader with the lowest valuation at the brokerage price $P_t$.

The paper assumes that both $V_t, W_t$ are random variables with same expected value $m_t = c_t^\top\phi$ for some unknown vector $\phi$. The the reward of each interaction is the sum of the net utilities of the traders, known as gain from trade. The goal of the learner is to minimize the regret with respect to the best function of the contexts. The paper considers two types feedback: (1) full feedback — both valuations $V_t, W_t$ are revealed to the learner at the end of each round (2) two-bit feedback — only the indicator functions $\mathbb{I}\{P_t\le V_t\}$ and $\mathbb{I}\{P_t\le W_t\}$ are disclosed.

Let $L$ denotes the upper bounded density of the valuation distributions. The paper shows that in the full feedback setting, an ridge regression estimation-based algorithm can achieve a tight $\Theta(Ld\ln T)$ regret. For the two-bid feedback, the paper shows an tight $\Theta(\sqrt{Ld T})$ regret bound. The paper concludes by showing that the bounded density assumption is necessary to obtain subliner regrets.
weaknesses: Maybe one concern is that there seems not much novelty in the developed algorithm. For example, for the algorithm of the full-feedback, the algorithm seems to be a direct application of using the regression to compute the estimate of the unknown vector. The authors may consider adding discussions about the novelty of the proposed algorithm, or the challenges of the learner's problem.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: See the weaknesses mentioned.
soundness: 3
strengths: - The paper is fairly well-written and key ideas and assumptions exposited quite nicely
- The technical results look sound. The full feedback algorithm based on online ridge regression is reasonable and I am especially intrigued by the algorithm for the 2-bit feedback case, where it essentially attempts to reconstruct the CDF. I would actually appreciate a bit more discussion on the intuition behind the algorithm. Although some of the techniques borrow from previous works in terms of novelty, I don't see this as a shortcoming. 
- The technical bounds provided here are nearly tight. Both the full-feedback and 2-bit feedback models have matching lower bounds, and the authors show the necessity of the bounded distributional assumption.
summary: This paper studies an online model of OTC markets, where traders arrive at each round with private valuations, a brokers proposes a price, and traders engage if the price is consistent with their valuations. At each round/product, they assume an unknown ground truth market price $m_t$ exists, with both the traders valuations being sampled from a distribution that is an unbiased estimator of this price. Further, the broker observes a context $c_t$, which is linearly consistent with $m_t$ as follows: $\langle c_t, \phi \rangle = m_t$. The work studies two feedback model (at round's end, either observe the private valuation or just the traders participation) and provide tight bounds in both settings. While I think the technical work here is sound and parts of the results interesting, I am not fully convinced by the conceptual model the problem attempts to study and the additional insights it offers beyond the current literature.
weaknesses: My major critique of the paper arises from it's conceptual model of the OTC marketplace and the additional insights it provides compared to existing literature. 

- In "A Regret Analysis of Bilateral Trade" (Cesa-Bianchi, 2021) at each time step a (buyer, seller) pair arrives, with the buyer having maximum valuation $b_t$ and seller having minimum valuation $s_t$. It is clear that a trade happens if the proposed price $p_t \in [s_t, b_t]$. In this paper, however, the role of the buyer and seller are not determined. Two parties arrive, and depending on the p_t given, either could be a buyer or seller. This is quite strange and only really makes sense if both traders own the underlying asset - so either can be the seller. I am not sure how to justify this/be on board with this model and realistic this is in OTC markets.

- In this model, both trader's valuation arise from a stochastic process, which in expectation, is equal to the market price, which is crucially consistent with the context observed by the learner. So $E[V_t] = E[W_t] = m_t = \langle c_t, \phi \rangle$. This is also quite a strange and strong assumption; this notion of an expected ground truth market price agreed both buyer and seller parties is not present in (Cesa-Bianchi, 2021). In general, market price arises endogenously due to trading between different parties with possibly heterogenous expected valuations. Am I correct to say that if both traders are highly concentrated (low variance), then the GFT should be very small since they both have the same EV? Moreover, it requires consistency with the learner's context. On theoretical models, I am happy to be lenient with assumptions, but I worry that in this case, it does not provide any more natural insights or technical benefits over what is currently proposed in the literature (see below):

- I am trying to understand the novelty or additional insight this paper provides over "An Online Learning Theory of Brokerage" (Bolic, 2024), which the authors cite. That paper does not make a contextual assumption, nor do they make an assumption about mean of the trader's distribution - however, they assume both traders valuations are from same fixed distribution. In this model, trader's don't need to have the same distribution, but the same mean, which is consistent with the market price the context reveals. Beyond these differences, the model is nearly identical and the bounds achieved are also identical. I am not sure if the different distributional assumption can truly be justified as loosening the model since it requires an additional sort of internal consistency with the context - $E[V_t] = E[W_t] = m_t = \langle c_t, \phi \rangle$. I understand why this assumption is made from a technical/learning perspective, but conceptually, I don't see any immediate reasons to think this model is more natural than the one in (Bolic, 2024) or (Cesa Bianchi, 2021) which clearly delineates buyers and sellers, both of which give similar bounds. 

- Why use this strange notation for $a \wedge b$ denoting $min(a, b)$ and $a \vee b$ denoting $max(a,b)$? Makes it much harder to parse.