Research map / Bandits and online learning / Contextual bandits and Thompson sampling
A Parametric Contextual Online Learning Theory of Brokerage
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies contextual online brokerage between two traders with noisy linear valuations and 2-bit feedback, giving tight regret bounds sqrt(LdT) under bounded densities (2-bit), Ld ln T (full feedback), and linear T (no bounded density).
Problem
Online contextual brokerage: a broker posts a trading price from context each round, learning only whether each trader's valuation is above or below the price, with the goal of maximizing gain from trade against the best non-linear price function of contexts.
Approach
Shows that under bounded densities the optimal price is the (unknown) linear market value, with suboptimality quadratic in the distance; uses this to design an explore-or-exploit algorithm with 2-bit feedback that achieves sqrt(LdT ln T) regret, matched by lower bounds, while allowing non-identically distributed traders.
Key results
- Under bounded densities with 2-bit feedback, the proposed algorithm achieves regret R_T <= 1 + 6 sqrt(LdT ln T), matched up to sqrt(ln T) by a lower bound Omega(sqrt(LdT)).
- Under full feedback, regret is O(Ld ln T) (1 + 4Ld ln T), with matching Omega(Ld ln T) lower bound.
- Without bounded densities, the problem is unlearnable: regret at least T/32 even under full feedback and known contexts and market values.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| provide full valuation feedback instead of 2-bit feedback | Contextual brokerage · Contextual brokerage, bounded density | regret upper bound: 1 + 6\sqrt{LdT \ln T} -> 1 + 4 L d \ln T | Helped |
| remove the bounded-density assumption | Contextual brokerage with full feedback · Contextual brokerage, general valuations | regret: \frac{1}{32} T | Hurt |
Surprising findings
- Without bounded densities, posting the market value can be strictly suboptimal for expected gain from trade (counterexample with discrete valuations).
- Without bounded densities the contextual problem is unlearnable even under full feedback, even if the algorithm knows all market values in advance.
Limitations
- Requires bounded density assumption on valuation noise for learnability and the linear market-value model.
- Assumes market value is a linear function of contexts and zero-mean noise around it.
- Lower bounds for the 2-bit case lose a sqrt(ln T) factor relative to upper bound.
Experimental setup
Metrics: regret
Baselines: non-contextual brokerage algorithms contextual bilateral trade algorithm (noisy linear, T^{2/3})
Builds on: elliptical potential lemma bilateral trade online learning contextual linear bandits
Closest papers by meaning
- Nonparametric Contextual Online Bilateral Trade (ICLR 2026 · similarity 0.93)
- Feature-Based Online Bilateral Trade (ICLR 2025 · similarity 0.89)
- Improved Algorithms for Contextual Dynamic Pricing (NeurIPS 2024 · similarity 0.89)
- Adaptive Market Making with Inventory Constraints via Online Learning (AAAI 2025 · similarity 0.87)
- Contextual Dynamic Pricing with Heterogeneous Buyers (NeurIPS 2025 · similarity 0.86)
- Pricing with Contextual Elasticity and Heteroscedastic Valuation (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.