Research map / Bandits and online learning / Online convex optimization and games
Feature-Based Online Bilateral Trade
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 feature-based online bilateral trade with linear valuations, giving O(log T) regret for deterministic valuations and tight Õ(T^{2/3}) for noisy ones under two-bit feedback and strong budget balance, plus a reduction showing one-bit feedback is achievable under global budget balance.
Problem
Online bilateral trade where a learner observes adversarial feature vectors and must post prices to a seller and a buyer whose private valuations are unknown linear functions of the features, under limited (one- or two-bit) feedback and budget constraints.
Approach
Adapts ellipsoid pricing with separate uncertainty sets for seller and buyer for the noiseless case; for noisy valuations, uses a gain-from-trade decomposition into estimable integrals/CDFs and a Scouting Bandit with Information Pooling that shares feedback across increment levels; and converts a two-bit explore-or-commit algorithm into a one-bit global-budget-balanced one by spending early profit
Key results
- Deterministic two-bit strong-budget-balance setting: EP-BT achieves O(log T) regret (d^2 log T-type bound stated as 10ABd^2 log(...)).
- Noisy two-bit setting: SBIP achieves Õ(T^{2/3}) regret, claimed minimax optimal up to logs and d, matching the non-contextual Ω(T^{2/3}) lower bound.
- One-bit global-budget-balance setting: reduction yields Õ(T^{3/4}) regret for noisy valuations and polylog(T) for noiseless.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use successive elimination with information pooling across price-increment levels instead of estimating rewards uniformly over the grid with EOC-BT | Two-bit bilateral trade with noisy valuations and strong budget balance · Noisy valuations | regret: \widetilde O( T^{\nicefrac{3}{4}}) -> \widetilde O(T^{\nicefrac{2}{3}}) | Helped |
| Replace two-bit feedback with one-bit feedback and relax per-round strong budget balance to global budget balance | EOC-like bilateral trade algorithm · Noisy valuations | regret: \widetilde O(T^{3/4}) | Mixed |
| Use one-bit feedback with global budget balance under the deterministic valuation setting | EP-BT · Deterministic valuations | regret: \textnormal{polylog}(T) | Helped |
Surprising findings
- Explore-or-commit alone yields T^{3/4}, yet a careful information-pooling design recovers the T^{2/3} rate of the non-contextual case.
Limitations
- Noisy valuation results require bounded-support noise with bounded densities; linear regret lower bounds when densities are unbounded.
- One-bit algorithm relies on a well-behaved market assumption for the stated rates; otherwise rates degrade to about T^{7/8}.
- Lower-order dependence on dimension d is not optimized.
Experimental setup
Metrics: regret
Baselines: EllipsoidPricing (feature-based dynamic pricing) Scouting Bandits (non-contextual)
Builds on: EllipsoidPricing Scouting Bandits cross-learning for graph feedback
Closest papers by meaning
- Fair Online Bilateral Trade (NeurIPS 2024 · similarity 0.90)
- A Parametric Contextual Online Learning Theory of Brokerage (ICML 2025 · similarity 0.89)
- Improved Algorithms for Contextual Dynamic Pricing (NeurIPS 2024 · similarity 0.86)
- Adaptive Market Making with Inventory Constraints via Online Learning (AAAI 2025 · similarity 0.86)
- Online Learning under Budget and ROI Constraints via Weak Adaptivity (ICML 2024 · similarity 0.86)
- Learning to Price Homogeneous Data (NeurIPS 2024 · similarity 0.85)
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.