# Nonparametric Contextual Online Bilateral Trade

arXiv: https://arxiv.org/abs/2602.12904 · HTML: https://mlsanity.com/paper/2602.12904/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 33 references that are in the map.
- First posted on arXiv 13 Feb 2026.

## Builds on (most cited first, 14 of 14)

- [Bilateral Trade: A Regret Minimization Perspective](https://mlsanity.com/paper/2109.12974/) (2021)
- [Multidimensional Binary Search for Contextual Decision-Making](https://mlsanity.com/paper/1611.00829/) (2016)
- [No-Regret Learning in Bilateral Trade via Global Budget Balance](https://mlsanity.com/paper/2310.12370/) (2023)
- [An α-regret analysis of Adversarial Bilateral Trade](https://mlsanity.com/paper/2210.06846/) (2022)
- [Online Nonparametric Regression with General Loss Functions](https://mlsanity.com/paper/1501.06598/) (2015)
- [Approximating Gains from Trade in Two-sided Markets via Simple Mechanisms](https://mlsanity.com/paper/1706.04637/) (2017)
- [Improved Algorithms for Contextual Dynamic Pricing](https://mlsanity.com/paper/2406.11316/) (2024)
- [Fixed-Price Approximations in Bilateral Trade](https://mlsanity.com/paper/2107.14327/) (2021)
- [Approximately Efficient Bilateral Trade](https://mlsanity.com/paper/2111.03611/) (2021)
- [Locally-Adaptive Nonparametric Online Learning](https://mlsanity.com/paper/2002.01882/) (2020)
- [An Online Learning Theory of Brokerage](https://mlsanity.com/paper/2310.12107/) (2023)
- [Better Regret Rates in Bilateral Trade via Sublinear Budget Violation](https://mlsanity.com/paper/2507.11419/) (2025)
- [Feature-Based Online Bilateral Trade](https://mlsanity.com/paper/2405.18183/) (2024)
- [Tight Regret Bounds for Fixed-Price Bilateral Trade](https://mlsanity.com/paper/2504.04349/) (2025)

## Built on by (most cited first, 2 of 2)

- [Regret Minimization in Bilateral Trade With Perturbed Markets](https://mlsanity.com/paper/2605.10475/) (2026)
- [Breaking the T3/4 Barrier for Regret Minimization With Bi-Dimensional CDFs](https://mlsanity.com/paper/2607.20258/) (2026)

## Abstract (arXiv)

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