Paper: arXiv 2407.01566

Authors: François Bachoc, Tommaso Cesari, Roberto Colomboni

Abstract

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

Complexity vs Empirical Score

  • Math Complexity: 8.5/10
  • Empirical Rigor: 2.0/10
  • Quadrant: Lab Rats — high math complexity, limited empirical testing

Why this score: The paper presents a highly theoretical framework with advanced mathematical proofs for regret bounds and structural lemmas, but lacks any empirical validation, backtesting, or implementation details, focusing solely on theoretical guarantees.

Research Flowchart

  flowchart TD
  A["Research Goal: Design optimal brokerage<br>algorithms using contextual information"] --> B["Key Methodology: Online Learning Framework<br>with sequential trader arrivals"]
  B --> C["Data/Inputs: Asset context, market conditions,<br>trader valuations v1, v2"]
  C --> D["Computational Process: Broker proposes price p(t)<br>based on context and past regret"]
  D --> E{"Trade occurs?"}
  E -- Yes<br>p(t) between v1 and v2 --> F["Update Model & Algorithm<br>Zero Regret/No Update"]
  E -- No<br>Trade Fails --> G["Update Model & Algorithm<br>Incur Regret"]
  F & G --> H["Key Outcomes: Optimal regret guarantees,<br>Parametric contextual trading algorithms"]
  style A fill:#f9f,stroke:#333,stroke-width:2px
  style H fill:#ccf,stroke:#333,stroke-width:2px
  style D fill:#9cf,stroke:#333,stroke-width:1px
  style C fill:#9f9,stroke:#333,stroke-width:1px

Evidence Card

What the authors claim, on what data, and who has checked it. Read from the paper's own text by a language model: every quote is verbatim, nothing was re-run. How to read this card

Proposes

The paper proposes a contextual online learning model for brokerage between traders and introduces algorithms (Algorithm 1 and Algorithm 2) that achieve optimal regret bounds in both 2‑bit feedback and full‑feedback settings.

Source sentence
We propose a contextual version of the online brokerage problem, that is of significant practical interest given that the broker often has access to meaningful information about the asset being traded and the 1In 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 [64]. 3 Learning in Contextual Brokerage In

Assumes 2

  • There exists an unknown linear relation between the hidden market value mt and the observed context ct, i.e., mt = c_t^⊤ φ for some unknown φ. model
    Source sentence
    The first assumption (Theorem 1.1) states that an unknown linear relation exists between the unknown market value mt and the corresponding context ct the broker observes before proposing a trading price. There exists ϕ ∈[0,1]d, unknown to the broker, such that, for each t ∈N, it holds that mt = c⊺ t ϕ.
  • Traders’ valuations are zero‑mean perturbations of the market value: V_t = m_t + ξ_t and W_t = m_t + ζ_t with E[ξ_t]=E[ζ_t]=0. statistical
    Source sentence
    The second assumption accounts for variability due to personal preferences or individual needs of the traders by modeling traders’ valuations as zero-mean perturbations of the market values. There exists an independent sequence of random variables ξ1,ζ1,ξ2,ζ2,... such that, for each t ∈N, it holds that E[ξt] = 0 = E[ζt] and Vt = mt + ξt and Wt = mt + ζt.3 Contexts.

Data

No dataset named in the text.

Costs

Not applicable The paper reports no trading or execution result.

Finds 2

  • Algorithm 1 attains a regret of order Ō(√{L d T}) in the 2‑bit feedback setting, matching a matching lower bound Ω(√{L d T}). theoretical
    Source sentence
    3 Learning in Contextual Brokerage In this section, we introduce an algorithm (Algorithm 1) for the contextual brokerage problem for which we prove regret guarantees of order̃ O( √ LdT). We conclude this section by stating a matching (up to logarithmic terms) worst-case Ω( √ LdT) regret lower bound for any algorithm, proving the optimality of Algorithm 1.
  • Algorithm 2, using full feedback, achieves a logarithmic worst‑case regret of O(L d log T), with a matching lower bound Ω(L d log T). theoretical
    Source sentence
    If the learner runs Algorithm 2 and the traders’ valuations admit a density bounded by L ≥1, then, for any time horizon T ∈N, it holds that RT ≤1 + 4LdlnT. We conclude this section by stating a matching worst-case Ω(LdlnT) regret lower bound for any algorithm in the full-feedback case, proving the optimality of Algorithm 2.

Checked by others

No other paper in the archive has been found to support or contradict these findings (compared with 5 related papers). Coverage is partial, so this is neither replication nor refutation.

Code

No repository by the authors found in the paper.

Extracted 2026-11-14 · same card as JSON · A language model chose these items: check the source sentence before relying on one.

Cited References (65)

  1. A Tight Regret Analysis of Non-Parametric Repeated Contextual Brokerage (2025) — link
  2. Market Making without Regret — → 2411.13993
  3. Improved Algorithms for Contextual Dynamic Pricing (2024) — link
  4. Feature-Based Online Bilateral Trade (2024) — link
  5. Fair Online Bilateral Trade (2024) — link
  6. An Online Learning Theory of Brokerage (2023) — link
  7. No-Regret Learning in Bilateral Trade via Global Budget Balance (2023) — link
  8. Adaptive maximization of social welfare (2023) — link
and 57 more
  1. The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations (2023) — link
  2. Repeated Bilateral Trade Against a Smoothed Adversary (2023) — link
  3. Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression (2022) — link
  4. Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms (2022) — link
  5. Non-Obvious Manipulability for Single-Parameter Agents and Bilateral Trade (2022) — link
  6. Approximately efficient bilateral trade (2021) — link
  7. Distribution-free Contextual Dynamic Pricing (2021) — link
  8. Policy Optimization Using Semiparametric Models for Dynamic Pricing (2021) — link
  9. Bilateral Trade: A Regret Minimization Perspective (2021) — link
  10. Learning to Bid in Contextual First Price Auctions✱ (2021) — link
  11. Fixed-Price Approximations in Bilateral Trade (2021) — link
  12. Logarithmic Regret in Feature-based Dynamic Pricing (2021) — link
  13. A Regret Analysis of Bilateral Trade (2021) — link
  14. Randomized double auctions: gains from trade, trader roles, and price discovery (2021) — link
  15. Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective (2020) — link
  16. The Search Theory of Over-the-Counter Markets (2020) — link
  17. A Nearest Neighbor Characterization of Lebesgue Points in Metric Measure Spaces (2020) — link
  18. Bandit Algorithms (2020) — link
  19. Efficient two-sided markets with limited information (2020) — link
  20. Taking a hint: How to leverage loss predictors in contextual bandits? (2020) — link
  21. Optimal Contextual Pricing and Extensions (2020) — link
  22. Contextual search in the presence of irrational agents (2020) — link
  23. Dynamic Incentive-Aware Learning: Robust Pricing in Contextual Auctions (2020) — link
  24. Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits (2020) — link
  25. Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes (2019) — link
  26. Stochastic Bandits with Context Distributions (2019) — link
  27. Model selection for contextual bandits (2019) — link
  28. Bulow-Klemperer-Style Results for Welfare Maximization in Two-Sided Markets (2019) — link
  29. Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adapting (2019) — link
  30. Semi-parametric dynamic contextual pricing (2019) — link
  31. Contextual bandits with surrogate losses: Margin bounds and efficient algorithms (2018) — link
  32. Nonparametric Learning and Optimization with Covariates (2018) — link
  33. Contextual Search via Intrinsic Volumes (2018) — link
  34. A Smoothed Analysis of the Greedy Algorithm for the Linear Contextual Bandit Problem (2018)
  35. Fixed Price Approximability of the Optimal Gain from Trade (2017) — link
  36. Efficient Contextual Bandits in Non-stationary Worlds (2017) — link
  37. Approximating Gains from Trade in Two-sided Markets via Simple Mechanisms (2017) — link
  38. Approximating Gains-from-Trade in Bilateral Trading (2016) — link
  39. Approximately Efficient Two-Sided Combinatorial Auctions (2016) — link
  40. Multidimensional Binary Search for Contextual Decision-Making (2016) — link
  41. Dynamic Pricing in High-dimensions (2016) — link
  42. Feature-based Dynamic Pricing (2016) — link
  43. Approximately Efficient Double Auctions with Strong Budget Balance (2016) — link
  44. Learning Prices for Repeated Auctions with Strategic Buyers (2013) — link
  45. Real analysis for graduate students (2011)
  46. Efficient Mechanisms for Bilateral Trading (1983) — link
  47. The Pricing of Options and Corporate Liabilities (1973) — link
  48. An Online Learning Theory of Trading-Volume Maximization (2025)
  49. Regret Analysis of Bilateral Trade with a Smoothed Adversary (2024)
  50. Context-Based Dynamic Pricing with Partially Linear Demand Model (2022) — link
  51. An alpha-Regret Analysis of Adversarial Bilateral Trade (2022) — link
  52. Thompson Sampling for Multinomial Logit Contextual Bandits (2019)
  53. Offline Contextual Bandits with High Probability Fairness Guarantees (2019)
  54. Learning in Generalized Linear Contextual Bandits with Stochastic Delays (2019)
  55. Probability with Martingales (1991) — link
  56. end-June
  57. Corruption-robust contextual search through density updates

1 of 65 cited works are in the corpus; resolved via arXiv source bundles, Semantic Scholar and OpenAlex. Corpus-wide: 2596 linked papers.