A Contextual Online Learning Theory of Brokerage

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.

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.

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).

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.

Dear reviewers, we thank you all for your invaluable comments and suggestions.

The biggest concern, which most of you seem to share, is the technical novelty of this work. In particular, compared to its non-contextual counterpart [1].

To make a long story short, adding context to a setting is a major change that requires algorithmic and proof ideas that are totally orthogonal to those of their non-contextual counterparts. This is because, in the presence of contexts, the problem goes from learning values to learning functions---a vastly more challenging task. Also, consider the two-bit feedback setting. In the absence of contexts, it is clear that it is optimal to carry out the entire exploration first and then to stick to exploitation. However, with contexts, the relevance of exploration depends on the context, so we need to balance exploration and exploitation in an online fashion.

That said, the fact that multiple reviewers asked for similar clarifications worried us that our message was not conveyed effectively.

Therefore, we prefer to withdraw the paper, spend some time reworking the writing, incorporating all your precious comments, and resubmit it later.

We sincerely thank you for your hard work and for taking time off of your busy schedule to review our submission.

Warm regards,

The authors

Dear reviewers, we thank you all for your invaluable comments and suggestions.

The biggest concern, which most of you seem to share, is the technical novelty of this work. In particular, compared to its non-contextual counterpart [1].

To make a long story short, adding context to a setting is a major change that requires algorithmic and proof ideas that are totally orthogonal to those of their non-contextual counterparts. This is because, in the presence of contexts, the problem goes from learning values to learning functions---a vastly more challenging task. Also, consider the two-bit feedback setting. In the absence of contexts, it is clear that it is optimal to carry out the entire exploration first and then to stick to exploitation. However, with contexts, the relevance of exploration depends on the context, so we need to balance exploration and exploitation in an online fashion.

That said, the fact that multiple reviewers asked for similar clarifications worried us that our message was not conveyed effectively.

Therefore, we prefer to withdraw the paper, spend some time reworking the writing, incorporating all your precious comments, and resubmit it later.

We sincerely thank you for your hard work and for taking time off of your busy schedule to review our submission.

Warm regards, The authors