Research map / Bandits and online learning / Online convex optimization and games
Near-Optimal Regret-Queue Length Tradeoff in Online Learning for Two-Sided Markets
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.
Proposes a learning-based pricing policy (zeroth-order gradient ascent with bisection price search and a probabilistic two-price rule) for two-sided matching queues that achieves near-optimal regret vs. average queue length tradeoff.
Problem
Joint online learning of unknown demand/supply price-arrival curves and pricing/matching in a two-sided queueing market, seeking a Pareto-optimal tradeoff between profit regret, average queue length, and maximum queue length.
Approach
A probabilistic two-price policy: when a queue is nonempty and below a threshold, the price is perturbed by alpha with probability 1/2 and the perturbed samples are discarded, so half the samples remain useful for learning while enforcing negative drift; combined with a two-point zeroth-order gradient ascent on the fluid problem and bisection price search.
Key results
- Achieves regret O~(T^{1-gamma}), average queue length O~(T^{gamma/2}), and max queue length O(T^gamma) for gamma in (0,1/6], improving average queue length over the prior T^gamma bound.
- Regret bound cannot be pushed below O~(T^{5/6}) under this analysis; for gamma>1/6 the regret is O~(T^{5/6}) with average queue length O~(T^{1/12}).
- In simulation, the proposed policy improves over the prior threshold-based learning policy by up to 22% on the weighted objective (single-link, w=0.001).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the probabilistic two-price policy instead of the prior learning-based pricing policy | Online pricing and matching for two-sided markets · Two-sided market, time horizon T | average queue length: \tilde{O}(T^{\gamma}) -> \tilde{O} ( T^{\frac{\gamma}{2}} ) | Helped |
| Use the probabilistic two-price policy instead of the prior learning-based pricing policy | Online pricing and matching for two-sided markets · Two-sided market, time horizon T | regret: \tilde{\Theta}(T^{1-\gamma}) -> \tilde{O}(T^{1 - \gamma}) | No clear effect |
| Use the proposed algorithm rather than estimate-then-optimize | Online pricing and matching for two-sided markets · Two-sided market, time horizon T, \gamma=1/6 | average queue length: \Theta(T^{3/4}) -> \tilde{\Theta}(T^{1/12}) | Helped |
| Use the probabilistic two-price policy instead of the threshold policy | Online pricing and matching for two-sided markets · Single-link system, simulation, w=0.001, \gamma=1/6 | objective regret: up to 22% | Helped |
| Use the proposed policy rather than the genie-aided two-price policy | Online pricing and matching for two-sided markets · Single-link system, simulation, w=0.001, \gamma=1/6 | objective regret | Hurt |
| Increase the maximum-queue threshold beyond T^{1/6} | Probabilistic two-price policy · Two-sided market, time horizon T | regret: \tilde{O}(T^{5/6}) | No clear effect |
| Use a static policy rather than a two-price policy | Prior learning-based pricing policy · Two-sided market, time horizon T | average queue length: \Theta(T^{\gamma}) versus \tilde{O}(T^{\gamma/2}) | Hurt |
| Set prices to midpoints whenever the queue is nonempty and below threshold, without probabilistic price adjustment | Sample collection in the pricing algorithm · Two-sided market, time horizon T | average queue length | Hurt |
| Use biased arrival samples collected while prices are adjusted by alpha | Two-point zero-order gradient learning · Two-sided market, time horizon T | regret: \Theta(T\alpha) | Hurt |
Surprising findings
- The paper's probabilistic approach achieves a T^{1-gamma} vs T^{gamma/2} tradeoff, which the authors argue is optimal up to logs for a class of policies, while the prior threshold-based approach only achieves T^{1-gamma} vs T^{gamma}.
Limitations
- Regret bound limited to O~(T^{5/6}) and gamma restricted to (0,1/6]; gap to the sqrt(T) lower bound.
- Dependence on number of customer and server types I and J is polynomial and not optimized (I^4 J^4 (I+J)).
- Requires assumptions such as smoothness, bounded-away-from-zero derivatives, and a known initial balanced point and price intervals.
Experimental setup
Benchmarks: single-link simulated two-sided queue
Metrics: regret average queue length maximum queue length weighted objective with waiting cost
Baselines: two-price policy (known demand/supply) threshold policy balanced pricing algorithm (learning-based, static)
Builds on: two-price policy balanced pricing algorithm MaxWeight matching two-point zeroth-order gradient method
Closest papers by meaning
- Improved Bandits in Many-to-One Matching Markets with Incentive Compatibility (AAAI 2024 · similarity 0.88)
- Contextual Online Pricing with (Biased) Offline Data (NeurIPS 2025 · similarity 0.87)
- Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret (NeurIPS 2026 · similarity 0.87)
- Learning to price with resource constraints: from full information to machine-learned prices (NeurIPS 2025 · similarity 0.86)
- Improved Analysis for Bandit Learning in Matching Markets (NeurIPS 2024 · similarity 0.86)
- Wait-Less Offline Tuning and Re-solving for Online Decision Making (ICML 2025 · 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.