# Near-Optimal Regret-Queue Length Tradeoff in Online Learning for Two-Sided Markets

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 30 references that are in the map.
- First posted on arXiv 15 Oct 2025.

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

- [Queueing Network Controls via Deep Reinforcement Learning](https://mlsanity.com/paper/2008.01644/) (2020)
- [RL-QN: A Reinforcement Learning Framework for Optimal Control of Queueing Systems](https://mlsanity.com/paper/2011.07401/) (2020)
- [Learning While Scheduling in Multi-Server Systems with Unknown Statistics: MaxWeight with Discounted UCB](https://mlsanity.com/paper/2209.01126/) (2022)
- [Queue-Learning: A Reinforcement Learning Approach for Providing Quality of Service](https://mlsanity.com/paper/2101.04627/) (2021)
- [Performance of NPG in Countable State-Space Average-Cost RL](https://mlsanity.com/paper/2405.20467/) (2024)
- [Dynamic Pricing and Matching for Two-Sided Queues](https://mlsanity.com/paper/1911.02213/) (2019)
- [Throughput Optimal Routing in Blockchain Based Payment Systems](https://mlsanity.com/paper/2001.05299/) (2019)
- [Online Learning and Optimization for Queues with Unknown Demand Curve and Service Distribution](https://mlsanity.com/paper/2303.03399/) (2023)
- [QGym: Scalable Simulation and Benchmarking of Queuing Network Controllers](https://mlsanity.com/paper/2410.06170/) (2024)
- [Learning-Based Pricing and Matching for Two-Sided Queues](https://mlsanity.com/paper/2403.11093/) (2024)

## Abstract (arXiv)

We study a two-sided market, wherein, price-sensitive heterogeneous customers and servers arrive and join their respective queues. A compatible customer-server pair can then be matched by the platform, at which point, they leave the system. Our objective is to design pricing and matching algorithms that maximize the platform's profit, while maintaining reasonable queue lengths. As the demand and supply curves governing the price-dependent arrival rates may not be known in practice, we design a novel online-learning-based pricing policy and establish its near-optimality. In particular, we prove a tradeoff among three performance metrics: tildeO(T1-γ) regret, tildeO(Tγ/2) average queue length, and tildeO(Tγ) maximum queue length for γ ∈ (0, 1/6], significantly improving over existing results [1]. Moreover, barring the permissible range of γ, we show that this trade-off between regret and average queue length is optimal up to logarithmic factors under a class of policies, matching the optimal one as in [2] which assumes the demand and supply curves to be known. Our proposed policy has two noteworthy features: a dynamic component that optimizes the tradeoff between low regret and small queue lengths; and a probabilistic component that resolves the tension between obtaining useful samples for fast learning and maintaining small queue lengths.