Near-Optimal Regret-Queue Length Tradeoff in Online Learning for Two-Sided Markets
Authors: Zixian Yang
Sushil Mahavir Varma
Lei Ying
Venue: NeurIPS 2025 poster ()
Keywords: online learning
two-sided markets
queueing
pricing
regret
tradeoff
Primary area: theory

Abstract: 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: $\tilde{O}(T^{1-\gamma})$ regret, $\tilde{O}(T^{\gamma/2})$ average queue length, and $\tilde{O}(T^{\gamma})$ maximum queue length for $\gamma \in (0, 1/6]$, significantly improving over existing results (Yang & Ying, 2024). Moreover, barring the permissible range of $\gamma$, 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 (Varma et al., 2023) 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.

Near-Optimal Regret-Queue Length Tradeoff in Online Learning for Two-Sided Markets
Zixian Yang
Department of Electrical Engineering and Computer Science University of Michigan Ann Arbor, MI 48 48109 zixian@umi ch. edu
Sushil Mahavir Varma
Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109 sushilv@umich edu
Lei Ying
Department of Electrical Engineering and Computer Science University of Michigan Ann Arbor, MI 48109 leiying@umich. edu
Abstract
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 anline-learning-baeee pricing policy and establish near-optimality. In particular, we prove a tradeoff among three performance metrics: Ó(TI->) regret, Ó(T>/2) average queue length, and Ö(T)) maximum queue length for y E (0, 1/6]. significantly improving over existing results [Л] Moreover, barring the permissible range of 7. 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 in 22 which assumes the demand and supply curves to be known. Our proposed policy has two noteworthy features: 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.
Introduction
We study a two-sided market, wherein, heterogeneous customers and servers arrive into the system and join their respective queues. Any compatible customer-server pair can then be matched, at which point they leave the system instantaneously. More formally, the system described by a bipartite graph, where the vertices are customer and server queues while the edges represent compatibility between them.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Such canonical wwo-sided/matching queueing model is useful in studying matching in emerging applications like online marketplaces 2). For example, matching customers and drivers ride- hailling systems, customers and couriers in meal-delivery platforms, tasks and workers on crowdsoureing platforms, etc. Furthermore, matching queues are a versatile tool for modeling diverse applications beyond online marketplaces. In particular, different variants of matching queues are prevalent in modeling applications like assemble-to-order systems
[ payment channel networks [4], and
quantum switches [5].
Motivated by these applications, we study matching a two-sided queueing model with an additional lever of modulating the arrival rates via pricing. For example, a higher price offered to the customer or a lower price offered to the server reduces their arrival rate. Our objective is to devise a joint dynamic pricing and matching policy to maximize the profit for the system operator and minimize the delay for customers and servers. Specifically, we focus on characterizing the Pareto frontier of regret and average queue length, where regret is defined as the loss in profit compared to the so-called fluid benchmark (see (5) for a precise definition).
This model was first introduced and studied in [2] They proposed dynamic pricing and matching policy and established a O(n' regret and (22 queue length for r E [O. 1] in the steady state, where 1) is the system size. They also showed that such trade-off between regret and queue length is the best possible for large class of policies. However, the proposed pricing policy of (2) is based on the optimal solution of the so-called fluid problem which relies on knowing the demand and supply curves. These curves are typically estimated using historical data. Thus, any estimation error leads to an error the optimal fluid solution, resulting in a ((n) regret in the steady state. So, it is essential to simultaneously estimate the demand and supply curves and optimize the pricing policy.
Building [21, the paper [ proposed learning- pricing policy that iteratively updates the price based on zeroth-order stochastic projected gradient ascent on the fluid optimization problem. They establish a é(T²) -)) regret and ((T7) average queue length bounds for y E [o, 1/6], where T is the time horizon (plays a similar role as 7) in 2). So, while this pricing scheme is parameter-agnostic, is not Pareto optimal as it does not achieve - y versus 7/2 tradeoff. One can understand this sub-optimality by observing that their pricing scheme mimics static policy as T - op opposed to two-price policy as in (2)
To this end, we develop pricing policy that achieves the best of both worlds: parameter-agnostic pricing scheme that mimics two-price policy. We establish an improved é(T1-7) regret and 6(T7/2) average queue length for E [0, 1/6]. We show that this trade-off, that is. 1 versus 7/2 as in [2. is optimal up to logarithmic factors under a class of policies. The only discrepancy is in the permissible value of y. In particular, prevents from improving the regret beyond 6(T5/ Nonetheless, we significantly improve over [1] and achieve a near-optimal trade-off between regret and average queue length. Additionally, our policy also allows us ensure ((T") maximum queue length.
incur additional learning error compared to [2] which
Our pricing scheme is a novel dynamic probabilistic policy that optimizes the tension between obtaining useful samples for fast learning and maintaining small queue lengths while incurring low regret. At the time L [T]. let p(t) be the price prescribed by the learning scheme for a fixed customer type with queue length Q(I) E Z4. Then, we are inclined to set price p(() to obtain useful samples for learning. but that may increase the queue length. Our policy resolves this difficulty as follows. If Q(t) 0, set the price to be p(t) to prioritize learning when the queue length is empty. Similarly, if Q(t)= > qhh set the price to be the maximum price to prioritize high negative drift when the queue length is large. For the in-between case of 0 < Q(t) < ش²d we set the price to be p(t) with probability 1/2 and p(t) + a otherwise. Such a probabilistic scheme ensures that half of the collected samples is useful in learning. In addition, a E R is suitably picked to optimize the trade-off between maintaining low queue lengths and incurring small regret. In other words, we converge to an optimal two-price policy as T - 00, as opposed to a static policy in [ which is known to be sub-optimal.
1.1 Related Work
Contrary to the classical literature on online learning 6 poses an additional challenge of strong correlations over time induced by maintaining queue, in
9 10,
learning in queueing systems

---

addition to its countable state space invoking the curse of dimensionality. A recent surge of literature has emerged better understand online learning in queueing.
One line of work views the queueing system as a Markov decision process and uses reinforcement learning methods in an attempt to learn global optimal policy [15] 16). These methods are broadly applicable to many types of queueing systems. Contrary to this, our focused approach allows us to exploit the structural result that two-price policy is near optimal 2 to restrict our policy space. resulting in more efficient and practical learning scheme.
In line with our approach, another line of work exploits the structure of either the model [17]. the stationary distribution [18), or the (near) optimal policy [3] Closest to ours is the paper [19 that learns to price for queueing system with single server and single queue, where arrivals follow a Poisson process and service times are independent and identically distributed with general distribution. However, they assume uniform stability of the queueing system, circumventing one of the main challenges we tackle in this work. This assumption allows them to learn a static pricing policy and show its optimality [20]. On the other hand, we focus on learning a dynamic pricing policy and demonstrate its benefits, which we believe is novel in the literature on learning in queues.
2 Problem Formulation
We are using the model developed by 11 We present the model in this section for completeness. We study a discrete-ting system that contains two sets (sides) of queues: one for customers and the other for servers. Each side includes multiple queues represent various types of customers or servers. Customers can be seen as demand, and servers as supply. This system can be modeled using a bipartite graph G(Z J J, E). where I = {1, ................................ I) denotes customer types and J =1, 21,2, ......... ...,,..... J} denotes server types, with [Z] I and |J| J. The set & includes all compatible links, that is, type customer can be served by type j server if and only (i, Figure | jillustaates this with three customer types and two server types (I = 3, J 2).
prices
Platform
prices
(Control Pricing and Matching)
matching
(t)
Qc)
2, (t)
f
Pa.(t)
M4 (t)
Pe.a (t)
Qc2 (t)
A²(()
(2.(t)
Ps
(t)
Qaa (t)
(t)
(1)
Excompatible
per-server-type queues
per-customer-type queues
set of links
Figure 1: The model, an example with 3 types of customers and 2 types of servers.
At the beginning of each time slot f, the platform observes Qc,((t) and Qs,(t) for all i E I and j e J, where (t, and Qa,(t) represent the queue lengths of type i customers and type j servers, respectively. Assume that all queues price for each queue, i.e., for each type of customer and server. Let Pr.,(!) represent the price for a type customer and (() the price for type j server in time slot l. The price Pe,i(!) means that type customer will be charged (t) units of money by the platform when they join the queue. The price Pa,((t (t) means that type j server will receive Ps.j(t) units of money from the platform when they join the queue. These prices will influence the arrivals of the customers and servers. In time slot f, let (t, represent the number of type customer arrivals, and (t) the number of type j server arrivals. Assume (t) and (t. are independently distributed according to Bernoulli distributions. Define (t) == [t) and (t) E[A (t)]. We use a demand function and a supply function to model the relation between the price and the arrival rate for each customer and each server. For a type customer, the demand function, F3 [0, 1] [pe,s.min: Pe,t,max],
initially empty / 1. Then the platform determines the
[Pe.smmin.P...max)) models the relation between the arrival rate (1) [0, 1] and the price ((.)(() [po.i.min:PP.. Pe,i.max], with Pe,i.min and ma. as the minimum and maximum prices, respectively. Similarly, the supply function
for a type j server, G5 [0, 1] [pi paj. models the relation between the arrival rate
3

---

(t(t) E [0, 1] and the price Pt.s(t) E (Pe.iamim Po.j.max where Pe.j.min and pa.j.max are the minimum and maximum prices for a type server. We make the following assumption on F; and G3 as in M: Assumption 1. For any customer rype i, F; is strictly decreasing. bijective, and LF, -ipsschht Its inverse function F,- is --p-shiipsccitz For any server type j. G3 is strictly increasing, bijective, and LG, Lipschitz. Its inverse function Gj1 is L -ipssiihht
Thus, the price (c) determines the arrival rate Ae(() through X,(1) = (pe.(()) for all i I and the price Pa.j(t) determines the arrival rate (t) through (ty() = (t)) for all j J. After arrivals in the time slot t, the platform matches customers and servers the queues via compatible links. Once customer is matched with server, both exit the system immediately.
Objectives: Consider a finite time horizon T. As in [ we consider three performance metries, profi,, average queue length, and maximum queue length, as shown as follows:
Profit(T) E Σ (((O))((((())
Σ (t,(t)) + _
AvgQLen(T)) T
MaxQLen(T)
max !=l....?
max
max Qe,((1) max Qna(1).
Our goal to design an online pricing and matching algorithms to maximize the profit of the platform without knowing the demand and supply functions, while maintaining reasonable maximum and average queue lengths.
Baseline: We compare the profit of an online algorithm with the optimal value of a fluid-based optimization problem (2 as follows:
max 2,
Σ Dis for alli pj= Σ Jis for all e J, KG.JEE
(2)
Tij 20 for all (L,)) A. E (0, for i jE
(3)
where À= := (Az)sez and μ (Kz)jez can be viewed as steady-state arrival rates, and (1.))) can be viewed as steady-state matching rates. The constraints ( can be viewed as balance equations. We adopt the following assumptions in 22:
Assumption 2. The function X FAA)). is concave in X for all and the function (5Gg(1g) is convex in Hj for all j.
Assumption 3. There exists known positive number amin (0. for which there exists optimal
solution (X ,,,, xxx) to the optimization problem [-33. satisfying xt,- > O, amin & X 1 and
amin & 14 < for all and j.
Assumption limliee that the profit function -,, (1y) is concave and the optimization problem defined by (3 is concave. This concavity assumption follows from the economic law of diminishing marginal return: as the arrival rate increases, the marginal return, that is, the derivative of the profit function, decreases, which implies that the profit function is concave. Assumption 3 means that there exists an optimal solution that resides in the interior of the feasible set. This means that no links or queues are redundant and no queues reach maximum arrival rates in this optimal solution. This is a mild assumption because:
If any redundant links queues exist, they can likely be easily identified in practice and removed from the problem.
Suppose each time slot is set to be sufficiently small when modeling real-world arrival rates. Then, an arrival rate of 1 in this discrete-time model with Bernoulli arrivals corresponds to sufficiently large actual arrival rate. In this case, no queue would reach the maximum arrival rate in the optimal solution due to the concavity of the profit function w.r.t. arrival rates.

---

We consider policies that make the queue mean rate stable (2]) i.e., under the policy, for all i.
Jim 1 F(QQ.:
[T) 0. T-x
lim
As shown in [1. the optimal value of the fluid optimization problem (-33) is upper bound on the asymptotic time-averaged expected profit under any mean rate stable policy. Therefore, we use the optimal value of the fluid problem baseline define expected regret:
- Engay(ot - E Σ [((())((A)))))) - (AAGEEAA))--EOOOGGGG En((t))
E[R(T)] == T
Challenges:
We face several challenges in addressing this problem:
The first challenge the unknown demand and supply functions F; and G,. The objective and constraints of the optimization problem (- are in terms of arrival rates but the platform can only control the prices directly. we choose to use prices as the control variable of the optimization problem, then the problem becomes nonconcave due to nonlinear equations in the constraint set, and the constraint set becomes unknown. This the key challenge compared to case of single-sided queue [19], where balance equations are not needed.
We are considering an online learning setting where learning and decision making occur simul- tancously. It is not acceptable to first estimate the demand and supply functions through running the system with difference prices (c.g., nonparametric regression) and then solve the optimization problem, because the queue lengths can grow linearly over time in the estimation process due to imbalanced arrival rates. An example can be found in Appendix A
It is challenging to characterize and achieve the optimal tradeoff between regret and queue length. The paper [1] obtain ( regret and Ô(T)) average queue length bounds, but we know from 2 that this tradeoff is not optimal. It is worth studying whether there exists algorithm that achieves a near-optimal tradeoff' between regret and average queue length in this learning setting.
Let E., [[(T] denote the expected profit regret under policy ग and problem instance d. The problem instance d specifies the bipartite graph G(Z u J, E) and the demand and supply functions. Let AvgQLen,,al (T(()) denote the average queue length under policy and problem instance d. Let (I<(), (())) denote the exponents of the objective values under the worst case, i.c.,
Definition of Pareto-optimal tradeoff::
x(1 ④ lim sup (sup (euppEr.all (((())
T-
and
v()) = lim sup log, (sup AvgQLen,,,(TT
T
point (x(()) ), ((T))) is said to be better than another point (1((22) y ((T2)) xf (((m))== & (x(2)) and y(m) & ((T2) with at least one inequality strict. A point (z(m), y (())) (=) is Pareto-optimal if there is no other policy x' that satisfies x(m²' & srm) and y(T') & y()) with at least one inequality strict. The set of all Pareto-optimal points forms the Pareto frontier.
Notation: Bold symbols denote vectors RIEI, RD or R', such as x, X, μ.. Subscript or refer individual elements of a vector; for example, A; represents the 5th element of X. Note that (L,))e is treated as vector in RIE), The order of elements in can be arbitrary, provided is consistent. Additionally, we use the subscript e for the customer side and s for the server side.
Main Results
In this section, we provide overview of the main results in this paper. We longest-queue-firss matching algorithm and propose a novel learning-ban pricing algorithm, which will be described in Section detail. The new algorithm achieves the following profit-regret bound and queue-length bounds:
E[R(T)] = ÖTT-T)) AvgQLen(T) = Ö(T²), MaxQLen(T) -0(m)
5

---

for any E [0,1/6], where y is a hyperparameter in the proposed algorithm. The formal statements of the results can be found in Appendix B As the allowable queue length increases, the achievable regret bound improves. However, the regret bound cannot be further reduced below ( in our result. Compared to [ the average queue length in this tradeoff is significantly improved from Ö(T*) to Ó(Tr/) while the regret and the maximum queue length remain the same.
Near-optimal tradeoff: This Ö(T versus Ö(Tr/3) tradcoff between regret and average queue length matches the (17²-7) regret and (1)??²) queue length tradeoff in 2 up to logarithmic factors, where they show the tradeoff' is optimal in their setting. The parameter 7 in ( is the scaling of arrival rates in their setting, which plays a similar role as the time horizon T in our setting because both characterize the scaling of the number of arrivals to the system. We now establish that this trade-off between regret and average queue length is nearly optimal. We restrict ourselves to a single-link system, i.e., 7 J and drop the subseripts i and j. Consider the matching policy that matches all pairs whenever possible. Note that in single-link system, there is no incentive to delay any possible match, as doing so only results in increased queue lengths. Similar to AvgQLen(T)). define
AvgQrLen (T) :- + Σ [1)=(1)² + (.) Assuming an upper bound on Avg the lemma below obtains lower bound on the regret.
Lemma 1. Let Assumption [and Assumption Poonptttoonoo.......... Assume that the functions FF) (negative revenue) and xG(xx) (cost) are both strongly convex. Also assume the unique optimal solution to the fluid optimization problem X* = =1²² & [0,1} to avoid the trivial case.
Fix a r e [0, 1/2]. Then, for sufficiently large T, for any pricing policy for which v Len()) & Tv/2 and E[Q.(T + 1)2 QT + 1) = (T)), we must have E(R(T)) = (TT
Proof of Lemma 1 can be found in Appendix J in [22]. Note that the above lemma assumes Tw/2 which is slightly stronger than assuming AvgQLen(T) < Tv/2 as
VAvgQ'Lent (T)
AvgQLen(T) (T) by Jensen's ' inequality and the fact that Qc(t)² + Q.(t)² = (Qe(t) + (t)) (by Lemma in [T). In particular, our proof strategy requires handle on a higher moment of the queue length to obtain the required bound on the regret. In Appendix K in [22), we show that V AAvgQ'Len(TT)
VAvgQ* T))
O (AvvgQIennT)) for large class of pricing policies that are a small perturbation of a static pricing policy satisfying a natural negative drift condition. Such a class of policies is ubiquitous in the literature (20 2 [2] on dynamic pricing in queues.
To understand the 1 7 versus 7/2 trade-off, consider a general pricing policy given by XQQc, Qx). pa(c, Qs) E [X* - a, X + ai] for some > O. For any such policy, the average queue length is at least ((1/a) as the difference in the arrival rates is ((a) [23]. Also, denote the regret as a function of the arrival rate for each time slot by and note that r(x*) 0. By Taylor's expansion, the cumulative regret in time T for arrival rate X + Oaa) (O(ar'(X*) + (X)))))) where the first order term vanishes as r'(*)= 0 by the first order optimality conditions. Thus, in summary. the queue length is of the order 1/az and the regret is T By substituting = 7-2/2 we obtain that the y versus 2/2 trade-off is fundamental.
Comparison with (1 The paper ID employs a pricing policy with an admission control threshold th In such a setting, the queue length of the order ((qgh) as the underlying system dynamics is a symmetric random walk between [0, g Jth In addition, the regret is equal to Σ Pr[((t)- = qhh ie., the proportion of the time we hit the boundary, which is approximately equal to T/qth. Thus, by picking 9th TV, it will result in a - y versus y trf This intuition shows that the approach of [ will not be able to result in the optimal 1 - y versus 7/22 trade-off.
Scaling with the number of customer/server types: The regret upper bound scales with the number of customer types and server types J as Ö(T=JA(I + J)T The average queue length upper bound scales with I and J as Ó(IJ + Jyrn/2). The maximum queue length does not scale with or J. We believe the dependencies on I and J can be improved, as our analysis mainly focuses on obtaining the correct dependence in terms of the time horizon T.
4 Algorithm
In this section, we will describe the matching algorithm we use and propose a novel pricing algorithm, under which we can achieve the results in the previous section.

---

Matching algorithm: We use the same matching algorithm proposed in M. which is a discretized version of the Max Weight algorithm in (2) At each time slot, we iterate through all queues on both the customer and server sides. For each queue, we first check for new arrivals. If a new arrival is detected (either a customer or a server), the algorithm matches with an entity from the longest compatible queue on the opposite side.
Pricing algorithm: We propose a novel pricing algorithm that aims to achieve the optimal tradeoff between regret and average queue length, while having a guarantee of anytime maximum queue length. Same as [ we use the techniques of zero-order stochastic projected gradient ascent [9] and bisection search in the pricing algorithm. The key innovation lies in how we implement the a a-perturbed two-price policy mentioned in the intuition in Section [ in the learning setting. We propose novel probabilistic two-price policy, where we reduce the arrival rate by perturbing the price with a constant probability for each queue when the queue nonempty and the length less than a predefined threshold. This probabilistic two-price policy achieves near-optimal tradeoff between regret and average queue length, while having guarantee of anytime maximum queue length. The rest of this section provides a detailed explanation of our pricing algorithm.
4.1 Two-Point Zero-Order Method
Note that under Assumption the fluid problem
can be equivalently rewritten as 333
max f(x)= = Σ Σ
Lis
F
Σ
zis
Σ
Dij G3
Σ
Izss
(6)
JEE,,
JEE
JEE,,)
iEEn.
s.b. Σ
Fi.s elamin 1J for all i E I,
Σ
Fi.
[amins 1] for all E J,
(7)
jeE,,
iEE.,
Di,j 00 for all (..))EE.
(8)
where Eo, : (i((i.) E) and ENj = j) E 83. Given that the demand and supply functions Fi and Gj are unknown, we cannot solve the problem (6)-(8) directly. Suppose we have zero-order access the objective function (o) i.e., the value of the objective function can be evaluated given any input variable æ. Then, we can use the two- zero-order method [9] We will present the main idea here. the method, we begin with an initial feasible solution and perform projected gradient ascent, estimating the gradient at each iteration using two points that are perturbed from the current solution. Specifically, it can be described in the following steps:
Let D'' denote a shrunk set of D with parameter ō >> The word "shrunk" means that æ + du E D for any D and any vector u in the unit ball, which was proved in [I] with the definition of D' under some mild assumptions. The details about D' are presented in Appendix C for completeness. The algorithm begins with an initial feasible solution x=1)= E D'.
(1) Initial feasible point:
Let DD denote the feasible set of the problem (6)-(8)
(8).
(2) Generate random direction and two points: In each iteration k. we begin by sampling unit vector u (t) in a uniformly random direction. Next, we perturb the current solution æ(k) in the direction of (k)) and the opposite direction of zukk), generating two points, axk)) + du(k) and a=k)) - (k)) We know that if the current solution ar ar(k)) is in the shrunk set D', then the two points will be in the feasible set D and hence are feasible.
(3) Estimate the function values in the two points: If we have zero-order access of the objective function f. we can obtain the function values f(((k) + du(k)) and f(x(k) Ōu(k)). However, we do not have zero-order access to f since we do not even have zero-order access to the demand and supply functions F, and Gy. In this case, known arrival rates as inputs. We will use a bisection search method similar to to estimate the values, which will be described later in Section 4.2
need to estimate the values of F; and Gj given some
(4) Gradient Calculation:
With the estimation of the two function values f(x(()) + Su(k)) and [(=(k) ōu(k)), the gradient (kk [ (f(x<(k) + du(k)) - f(xr(k) ōu(k)))u((k)
(5) Projected gradient ascent: With the estimated gradient (k)), we perform a step of projected gradient ascent with a step size m. æ(k + 1) (z(k) + r/ (k)).
7

---

Then the algorithm repeats Step (2)-(5) for the next iteration. This part of the pricing algorithm is the same as the balanced pricing algorithm in [T] and the details of the algorithm can be found in Appendix D for completeness.
4.2 Bisection Search Method
In this section, we will illustrate the bisection search method that we mentioned in the previous section. The bisection search takes the target arrival rates and the price searching intervals for all queues as inputs and outputs the estimated prices corresponding to the input arrival rates with accuracy e. The bisection search can be illustrated in the following steps:
(1) Calculate the midpoints: In each bisection iteration m (m = 1, M. M = [log2 (I/c)D,
first calculate the midpoint of the price searching interval for each queue. Note that the initial price searching intervals when k = 1 and m = 1 are predetermined at the beginning of the pricing algorithm, and the initial price searching intervals when > and m are calculated from the output of the bisection search in the previous outer iteration k - 1, which can be found in Line I 17 in Algorithm|] [ The underlying idea is that the price will not change too much since the corresponding target arrival rate will not change too much due to the small step size 17.
(2) Run the system to collect samples: Next, we run the system with the midpoints for certain number of time slots to obtain N samples of each arrival rate corresponding to each midpoint, where N ((3/22) In(1/c) and B > 0 is constant. How we run the system collect samples is the key difference between our proposed algorithm and that of []. We propose a probabilistic two-price
policy and will present later in Section 4.3
(3) Estimate the arrival rates and update the price searching intervals: Then, we can obtain an estimate of the arrival rate for each queue by taking the average of N samples. For each queue on the customer side, if the estimated arrival rate is greater than the input arrival rate, we should increase the price to reduce the arrival rate because the demand function is decreasing, so the price searching interval should be updated to the upper half of the previous price searching interval. Otherwise, the price searching interval should be updated to the lower half of the previous price searching interval. For each queue on the server side, we should do the opposite since the supply function is increasing.
Then the algorithm repeats Step (1)-(3) for the next bisection iteration. The details of the algorithm can be found in Appendix
4.3 Probabilistic Two-Price Policy
In this section, we propose a novel pricing policy called probabilistic two-price policy for Step (2) in Section 4.2 Recall that the goal of Step (2) is to collect samples to estimate the arrival rates corresponding to the prices of the midpoints. For an estimate of accuracy e, we need N ((1/²)) number of samples according the central limit theorem.
The key challenge in setting prices in this sample collection process is that we need to consider and balance three objectives. First, we need to set prices be the midpoints collect samples for learning. Second, we need to control the average queue length and maximum queue length during this sample collection process. Third, we need to minimize the regret. For fast learning, we want to set the prices to be the midpoints as frequently as possible. However, simply using the midpoints to run the system for N time slots will not give us any way control the queue lengths. To control the maximum queue length, we use threshold 9th as in [ when the queue length exceeds gh we reject arrivals by setting the highest price Pe,s,max for customer queue or the lowest price Pa.i.min for server queue j. However, this threshold policy cannot achieve an optimal tradeoff' between average queue length and regret. A challenging question is whether we can achieve near-optimal tradeoff.
Challenges:
We propose the probabilistic two-price policy, which resolves the tension between obtaining useful samples for fast learning and maintaining small queue lengths, providing a positive answer to the above question. The pseudo-code of the proposed policy can be found in Algorithm 3 in Appendix G The proposed policy can be explained in the following steps:
(1) At the beginning of the algorithm, we initialize counters to track the number of useful arrival rate samples for each queue, shown in Line D in Algorithm 3
8

---

(2) Control the maximum queue length: As in [ for each queue, we use a threshold 9th to control the maximum queue length. If the queue length exceeds or equals the threshold, we will set the price to the maximum (for customer queues) or the minimum (for server queues) to reject new arrivals, as shown Line and Line 10 in Algorithm
(3) Control the average queue length with probabilistic approach: To control the average queue length, we propose a probabilistic approach of adjusting the price, to reduce the arrival rate for each queue when the queue is nonemply and the length is less than the threshold qth Specifically, for each customer queue, with a constant probability (set to 1/2 for simplicity), we increase the price by small amount to reduce the arrival rate; for each server queue, with a constant probability, we decrease the price by a to reduce the arrival rate, as shown in Line and in Algorithm When the queue is empty, keep the original prices of the midpoints, as shown in Line and Line 12
and Line [1
(4) With the above prices, we run the system for time slot. For each queue, we keep the arrival sample only when the original price is used, discarding the sample when the price is adjusted, as shown in Line and Line 13 in Algorithm 3 We repeat Step (2) and Step (3) and run the system until the number of samples we keep is no less than for every queue. Finally, the algorithm returns the samples we keep.
Difficulties introduced by learning and algorithmic innovations: The paper [2 proposed a two- price policy (the a-perturbed policy mentioned in Section (3) when the queue length exceeds predetermined threshold, they reduce the arrival rate by small amount a. The idea was to ensure that we always have an a negative drift that reduces the queue lengths in expectation. However, in the learning setting where the demand and supply functions are unknown, the objective of setting prices not only induce a negative drift to control queue lengths, but also to yield useful samples for learning. Note that every time we adjust the price by a to induce a negative drift, these arrival samples become biased. These biases influence the value estimates of the two points, which in turn affect the gradient estimates in the two-point gradient ascent method, ultimately impacting the regret. Using these biased samples will lead to regret of at least order (TTa). To achieve the optimal trade-off between average queue length and regret, the regret must be (TTa²) in Section 3 Therefore, in our policy, we discard these biased samples, making them unusable for learning. Hence, it is important to ensure that negative drift is enforced while not wasting too many samples. The novel probabilistic approach enables us obtain useful samples with a constant fraction of time for fast learning, while also ensuring negative drift through reducing arrival rates by ((a)) with a constant probability when the queue is nonempty. By setting a we are able to achieve a near-optimal tradeoff between average queue length and regret.
mentioned in the intuition
Technical innovations: The analysis related to the proposed probabilistic two-price policy is novel. Specifically, the new technical challenges and the corresponding innovations include:
One challenge in the analysis is to bound the number of useless samples that are collected at the time of adjusting prices to reduce the arrival rate for queue-length control. The proposed probabilistic approach controls the fraction of time spent adjusting prices, thereby bounding the number of useless samples. This can be formally established using Wald's 's lemma, as shown in Appendix L.4.1 in 22
Another challenge in the analysis is to bound the regret induced by adjusting prices by The regret induced by adjusting prices can be bounded by the first-order error and the second-order error. The difficulty is to prove that the first-order error is no greater than the second-order error in the learning setting. To show this, we combine the KKT condition (Appendix L.3 in (22) and the Lyapunov drift method (Lemma 5 in (22. proof in Appendix O in (22
4.4 Computational Complexity
The proposed pricing algorithm has computational complexity Ö((T JJT IJTT-47),, along with T1 calls to projection oracle. The projection can be implemented by solving convex quadratic program using interior point methods, which have a computational complexity of ((IJ))3.55 24]. Hence, the overall computational complexity is Ó( JYT (1J)36611-41)
Proposed

---

Numerical Results
In this section, present simulation results for the proposed algorithm and compare its performance with the two-price policy (with known demand and supply functions) from and the threshold policy from 0
To compare the performance of these algorithms, we consider the following objective function:
Σ Σ (d(T) wE[W., Ed(() (Pa,(T) wE[Ws,(T)I))
(9)
where We, (T, denotes the waiting time of the customer arriving queue time slot T and W (r) denotes the waiting time of the server arriving at queue j at time slot т. The constant w >> 0 can be viewed as the compensation the platform pays for per unit time the customer/server wait. This objective can be shown to be equivalent to maximizing the originally defined profit minus the sum of the queue lengths multiplied by (see Appendix H). Therefore, the regret of the objective (9) can be calculated by [[[R(()) wt Attnv)Len(t)..
3.5
0.30
Two-price policy - known (Varma al., 2023)
Prottt Proft: Rogrett 0.001x qucue Length
(Prafts Regrett 0.801x Queue Length)
0.25
Threshold policy
(Yang Ying. 2024)
Percentage improvementt of
2.5
Probabilistic two-price policy (Proposed)
0.15
0.10
1.5
0.05
0.00
-0.05
0.5
0.0
-0.15
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
1c6
1c6
(a) E| [[(())] wtAvgQLen(t).
(b) Percentage improvement over the threshold policy M.
Figure Comparison among the two-price policy (no learning, known demand and supply functions) [2). the threshold policy [I], and the proposed probabilistic two-price policy with = 0.001. The shaded area 95% confidence interval with independent runs.
Figure 2 presents the performance of the algorithms in single-link system with 0.001 and y = =/66. We can see that the proposed algorithm significantly improves upon the algorithm [T] by up to 22%. The two-price policy from [2] outperforms the other two algorithms because it is genie-aided policy that assumes full knowledge of the true demand and supply functions, thereby bypassing the challenges associated with learning.
Details of the simulation are provided in Appendix H where we report the regret, average queue length, and maximum queue length of these algorithms, and also compare their performance under a different weight value w 0.01. We also test sensitivity the performance of the proposed algorithm to parameter tuingg. We conduct simulation for multi-link system as well.
Comparison with recent methods for queueing control: Most of the work on reinforcement learning for queueing in the literature (25) 26] 22 28 [6] does not utilize the special structure of our pricing and matching problem, and it is difficult to trade off between profit and queue length. When facing the curse of dimensionality of queueing systems, the works 25 26 28 use deep reinforcement learning, which does not have any theoretical guarantee on the performance. On the other hand, our approach circumvents the curse of dimensionality by restricting to the set of probabilistic two po-prrie policies as opposed to a fully dynamic policy, as we know that two-price policy near-optimal. Other adaptive optimization approaches, such as those that discretize the price space and apply UCB-based methods, fail balance matching rates and arrival rates on both sides, making it difficult to control queue lengths.
10

---

Acknowledgments
The work of Zixian Yang and Lei Ying is supported in part by NSF under grants 2112471, 2207548. 2228974, and 2240981.
References
[1] Zixian Yang and Lei Ying. Learning-basee baasdd pricing and matching for two-sided queues. arXiv preprint arXiv:2403. 1093, 2024.
[2] Sushil Mahavir Varma, Pornpawee Bumpensanti, Siva Theja Maguluri, and He Wang. Dynamic pricing and matching for two-sided queues. Operations Research, 71(1):83-100, 2023,
[3] Itai Gurvich and Amy Ward. On the dynamic control of matching queues. Stochastic Systems, 4(2):479-55 523, 2015.
[4] Sushil Mahavir Varma and Siva Theja Maguluri. Throughput optimal routing in blockchain- based payment systems. IEEE Transactions on Control of Network Systems, 8(4):1859-188 1868, 2021.
[5] Martin Zubeldia, Prakirt R. Jhunjhunwala, and Siva Theja Maguluri. Matching queues with abandonments in quantum switches: Stability and throughput analysis, 2022.
[6] P Auer. Finite-time analysis of the multiarmed bandit problem, 2002.
[7] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (ICML-03), pages 228-936 2003.
[8] Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex opti- mization in the bandit setting: gradient descent without a gradient. arXiv preprint cs/0408007, 2004.
[9] Alekh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi-point bandit feedback. In Colt, pages 28-40. Citeseer, 2010.
[10] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[11] Zixian Yang, R Srikant, and Lei Ying. Learning while scheduling in multi-server systems with unknown statistics: Maxweight with discounted ucb. International Conference on Artificial Intelligence and Statistics, pages 4275-4312. PMLR, 2023.
[12] Sanne van Kempen, Jaron Sanders, Fiona Sloothaak, and Maarten G. Wolf. Learning payoff's while routing skill-based queues, 2024.
[13] Yueyang Zhong, John R Birge, and Amy R Ward. Learning to schedule in multiclass many- server queues with abandonment. Operations Research, 2024.
[14] Jingjing Sun, Jim Dai, and Pengyi Shi. Inpatient overflow management with proximal policy optimization, 2024.
[15] Bai Liu, Qiaomin Xie, and Eytan Modiano. Reinforcement learning for optimal control of queueing systems. In 2019 57th annual allerton conference on communication, control, and computing (allerton), pages 663-670. IEEE, 2019.
[16] Yashaswini Murthy, Isaac Grosof, Siva Theja Maguluri, and R. Srikant. Performance of npg in countable state-space average-cost rl, 2024.
[17] Lucas Weber, Ana Bušié, and Jiamin Zhu. Reinforcement learning and regret bounds for admission control, 2024.
[18] Céline Comte, Matthieu Jonckheere, Jaron Sanders, and Albert Senen-Cerda. Score-aware policy-gradient methods and performance guarantees using local Цyapunov conditions: Applica- tions to product-form stochastic networks and queueing systems, 2023.

---

[19] Xinyun Chen, Yunan Liu, and Guiyu Hong. Online learning and optimization for queues with unknown demand curve and service distribution, 2023.
[20] Jeunghyun Kim and Ramandeep Randhawa. The value dynamic pricing in large queueing systems. Operations Research, 66(2):409-425, 2018.
[21] Michael Neely. Stochastic network optimization with application communication and queueing systems. Springer Nature, 2022.
[22] Zixian Yang, Sushil Mahavir Varma, and Lei Ying. Near-optimal regret-queue length tradeoff in online learning for two-sided markets. arXiv preprint arXiv:2510.10997, 2025.
[23] Sushil Mahavir Varma and Siva Theja Maguluri. heavy traffic theory of matching queues. 2021.
[24] Yurii Nesterov and Arkadii Nemirovskii. Interior-point polynomial algorithms in convex programming. SIAM, 1994.
[25] Majid Raeis, Ali Tizghadam, and Alberto Leon-Garcia. Queue-learning: A reinforcement learning approach for providing quality of service. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 461-468, 2021.
[26] Jim G Dai and Mark Gluzman. Queueing network controls via deep reinforcement learning. Stochastic Systems, 12(1):30-67, 2022.
[27] Bai Liu, Qiaomin Xie, and Eytan Modiano. RI-qn: A reinforcement learning framework for optimal control of queueing systems. ACM Trunsactions on Modeling and Performance Evaluation of Computing Systems, 7(1):1-35, 2022.
[28] Haozhe Chen, Ang Li, Ethan Che, Jing Dong, Tianyi Peng, and Hongseok Namkoong. Qgym: Scalable simulation and benchmarking of queuing network controllers. Advances in Neural Information Processing Systems, 37:92401-92411 2024.
[29] Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. In 2 st Annual Conference Learning Theory, number 101, pages 355-366, 2008.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Please refer to Section and Section 3
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Please refer to Section I Section and Appendix B
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Please refer to Section Appendix B for the full set of assumptions. Please refer to Appendix Appendix K, Appendix L, Appendix M. Appendix N, and Appendix O in 22 for the complete proof.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proof' can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Please refer to Section 5 Jand Appendix
H
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
Please refer the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https
/ "pipsscc/puulic//uui /ttee//guuddeeeeedeuuuuumbbbba ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Please refer Section 5 Appendix
H and the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Please refer to Section 5 Appendix and the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
15

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please refer to Appendix H
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: http://pp...ppppcccccccccccddaaa
Answer: [Yes]
Justification: We have reviewed the Code of Ethics and the research in the paper conforms with it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Please refer to Appendix
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Please refer the supplementary material for the code.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
19

---

A An Esimate-Thenn-ptimizz Algorithm
Consider the following estimate-then-opiine algorithm. First, we try prices uniformly in the price space. For each queue, to obtain an accuracy of Ç for the estimation of the demand/supply function, we need discretize the space into ((1/c) points, and for each point, we need at least (11(22) samples according to the central limit theorem. In this process, the queue length will increase linearly over time, up (1/(²). Using the estimated functions, we can obtain solution with accuracy and we can use this solution until the time horizon T. Hence, the worst-case average queue length will be (1/ç²² + (T- (/) The lowest worst-case average queue length that this approach can achieve is ((13/4) with Ç T-114 while our approach can achieve a much smaller average queue length ((T)/12) with 7 = 1/6 according to the results Section
B Formal Statements of Theoretical Results
In this section, we will present formal theoretical results for the proposed algorithm described in Section 4 and discuss the difficulties in the analysis.
B.1 Assumptions
To derive theoretical results, we impose the following additional assumptions.
We make the following assumption on the knowledge of the initial feasible point and the initial price searching intervals as in M.
Assumption 4 (Initial Balanced Arrival Rates). Assume that the initial point x(1) E D' and the initial pricing searching intervals {[eo, Po.el. (ea, PaIIeiII.Je satisfy
Σ (1) fECo,
Fr (Fe,) - + v Ec, P.
PT (p.)) + - Vecil0 for all
Σ xis(1) E iEE,
GJ (va)) -
-
-Et ViEnalo G. (Pa.)) + vleaslo for all i,
-e,
Le,t $2cc,is Paj - Pos & 20aj, for i,j.
The small numbers Cr,i and Gaj can be found in Appendix E
Discussion on Assumption 4 As in M. we assume that a feasible point x(1) E and the corresponding price bounds are known. We set the initial feasible point to be this point and use these bounds as the initial price searching intervals. Note that this point æ(1) and the prices are usually not optimal. This assumption is mild, because in real application, usually have some existing pricing strategy that may not be optimal but usually has approximately balanced arrival rates.
We make the following assumption about the objective function ff and an optimal solution. Assumption (Weaker Strong Convexity). There exists a positive constant such that there is an Band the following:
optimal solution (X* 1t,, x²) satisfying Assumption 3
f(x*) f(x)
x 112
(10)
for all x E DD'
Discussion on Assumption 5 The equation (10 in Assumption means that the optimal solution satisfies a property that is weaker than strong convexity. In fact, it is necessary condition for strong convexity.
Under Assumption and Assumption without loss of generality,
assume amin satisfies
Omin +
Gmin > 0 for all i
(11)
2N
jeCo.f
Σ
amin +1
amin 0 for all j
(12)
2N
20

---

To see this, notice that [II and 122 hold as long as the constant amin is sufficiently small. If (11 or (12) does hold, we can always find another constant diin such that d & Gmin and Amin satisfies II and (22 Then, we can use this mnn and all the results in this paper still hold.
We make the following assumption about the functions F F,. and Gj.
Assumption 6 (Smoothness & Nonzero Derivatives). We make the following assumptions on the demand and supply functions.
(1) Assume for all customer type i and all server type j. the function F; is 8p-1-smooth, the function Gj² is Ba, 1-smooth, the function F; -r.-smotth, and the function Gj is Ba, -smooth, i.e.,
dF. dF)
(p)
$ 8pp-110 1p: -p2l -Pal.
dp
dp
P-
P-
(p)
(G)
8o, 1p1 p2/.
dp
dp
p-p1
PTP2
(FF(A)
dFF(A)
& 8, 1A1 -22
dA
Ax-21
dd
A-
(dG(W)
(dG,(1) dl
Bc, 1M1 -22
dp
1--2
for all prices P1,P2 and all arrival rates X1, 22, P1,
(2) Assume for all customer type i and all server type j. the derivatives of FT! and GJ1 are lower bounded by constant, i.e.,
dF (p)
3C, for all p [po.i,inn Pe,i,max],
dp
dG, (p)
for all p e [Ps.j.min, Paxj
dp
where Ct, is constant independent Tf
Discussion Assumption 6 Assumption 61) means that the demand and supply functions FT7 G. F., and Gj are smooth. The smoothness assumption is common the optimization literature. Assumption (/2) means that the derivatives of these functions are bounded away from zero, which necessary ensure that the arrival rate be reduced through adjusting the price. Nonzero derivatives is usually true in practice.
B.2 Theoretical Bounds
Suppose the proposed algorithm described in Section 4 Let the parameters n, e, ô, a, 9th be functions T. Let 7), e, 8, a be nonincreasing in and q* be nondecreasing in T. We have the following theoretical bounds.
Theorem 1. Let Assumption
hold. Suppose < 8, T > 2MN, a is orderwise greater 17 + 5 e)/a 0, then for sufficiently large T, have
than DE 17 8 c). Le. lim
E[R(T)) = o ( T
log (1/e)
ar aVTlog((/e)) +Ta (V7 (v v8
+ n 7 6)
tth +
T
ne²
5
+ +Taa + gth
T2 4 -1 + Tet - =lo((1/)))
(13)
and the queue lengths
AvgQLen(T)) 5 (0
4th (Teftl + (o--oo)(/)))) MaxQLen(T) < th
(14)
a
21

---

Proof of Theorem can be found in Appendix L in [22]. In the regret bound 13 the term T/q is caused by rejecting arrivals when queue lengths exceed qth The term
caused by the zero-order projected stochastic gradient ascent with biased gradient estimation. The term av logl)///)/) + Ta(
v + vo) + Ta + 9th caused by reducing arrival rates through adjusting the prices by a. The term T a +1 + Te _ -1 log(1/e) is caused by the estimation error of the arrival rates.
In order to obtain the tradeoff among regret, average queue length, and maximum queue length, first set 9th = T for a fixed y. By first optimizing the order of the regret bound (33 with respect to the parameters e, 7) 6, at and then optimizing the order of the average queue length bound (14) over a without compromising the order of the regret bound, we can obtain the following corollary.
Corollary 1. Let all the assumptions in Theorem / hold. For any Y (0, d setting parameters 1/2
9th = - e T-2y, ô 7 a T-
1/7 - 1, for sufficiently large T, we can
achieve a sublinear regret as
E[R(T)] = =(())>>
and the queue lengths
ArgQLen(T) = Ö(TT), MaxQLen (T) ET
For any r E (/. 11, setting parameters 9th T c= T- n = 8= a= T-1/12 B 5.
for sufficiently large T, we can achieve a sublinear regret as
E[R(T)]= Ö
and the queue lengths
ArgQLen(T) (1T)) MaxQLen(T) & TT"
We can see from Corollary T that compared to [I. the average queue length bound is significantly improved from Ö(T)) to Ó(T)) with the use of the probabilistic two-price policy while the regret bound remains the same order, We remark that this tradeoff between regret and average queue length, Ö(T versus Ô(T²), matches the optimal tradeoff in [2] up to logarithmic order, although they do not consider learning in their setting. As the allowable maximum queue length increases (up to T2/6), the achievable regret bound improves. However, increasing the maximum queue length beyond T1/6 does not further enhance the regret bound, which remains at Ö(75/6) (after parameter optimization). Hence, will not let y increase over 1/6.
B.3 Discussion
Reason for choosing probabilistic approach: The probabilistic pricing scheme adjusts the price to reduce the arrival rate with a certain probability for each nonempty queue. Therefore, for each nonempty queue, with a certain probability, the arrival rate will strictly smaller than the sum of the average matching rates over all the connected links. So the lengths of nonempty queues will decrease, making the average queue length bounded. Other approaches, such as threshold policies in (2. can also control the average queue length, but they will induce a larger regret do not have any theoretical guarantee for the induced regret. The reason that these threshold approaches introduce strong correlation among price adjustment decisions across different time slots, making it difficult to bound the number of useless samples. The proposed probabilistic pricing decouples this correlation, providing theoretically guaranteed regret and average queue length, well near-optimal tradeoff between them.
Range of 7: One (possible) limitation of our result is the restricted range of x E (0, 1/6]. First, note that, in the learning setting, cannot expect to have better regret than VT as shown in (29] Thus, we should expect to have at best e (0. 1/2]. In our setting, we incur an even larger regret of 5 as the function we are maximizing a concave function of the arrival rates but we cannot directly set the arrival rates; we are only allowed to set the prices which in turn determines the arrival rates. This extra dependency forces us to implement line search to first try several different prices to set the correct arrival rate, which in turn allows us implement one iteration of the gradient algorithm. This
22

---

additional step seems to be necessary due to the constraints imposed by the system and results in an additional regret. Having said that, we are not sure what the best possible regret (somewhere between vT and T and it is an interesting future direction. We believe such lower bound is non-trivial due to the dual learning setup (using prices to learn the arrival rate and then using the arrival rate learn the optimal profit).
Possible Extension of the Probabilistic Approach: In problems of joint queueing, learning, and optimization, the correlation among them is usually complicated. One of the fundamental trade-offs in such problems is to optimize an objective while ensuring sustained low queue lengths. Thus, making mistakes during online learning in queues has sustained effect as queues build up. and so, one needs to carefully select the actions (prices in our case) to determine the optimal action while keeping low queue lengths. The idea of probabilistic algorithm partially decouples these two phenomena: allows to exploration of the prices to optimize the profit while ensuring low queue lengths. This decoupling allows for tight analysis, resulting characterizing the optimal trade-off between profit and queue length. Thus, we believe that the idea of using such probabilistic algorithm could be widely applicable in the context of online learning in queues.
23

---

C
Definitions of the Shrunk Feasible Set D
The definition of the shrunk set D' is as follows.
111-13
D'
a for all 24,
Omin
amin 2N
2N
Σ
Omin + 1
1 -1- :) Σ
Amin
Di.s"
E
Amin
2N
2N
J'EEx,
JeEEe
(1- --- (1
Omin + (
}
Σ
2N
j'EE.,
Amin + IV.
[11-- -
amin + 1
2N
E
2N
4min
PeE
1
Ounn +
(15)
2N
3'EE...
where Nog == maxi |Ea denotes the maximum cardinality of the sets Eo,i and Engi
r: min
+ amin
1
Σ
@min + 111
Umin + 1
1.j
2N
|E,,l
2N
|Eal
2N
f'EE.,
V'E
Omin
amin +
|Ecpil
2N
Omin
[Eng]
2N
Omin
(16)
f'eEe
WeEns
and E (0, r).
Under the conditions and 12). can be shown that x + du D for any æ D' and any vector in the unit ball []]
24

---

D Pricing Algorithm - Two-Point Zero-Order Projected Gradient Ascent
We present the details of the pricing algorithm two-point zero-order projected gradient ascent in Algorithm | which is the same as the balanced pricing algorithm in [[] The index (A)) denotes the hth outer iteration (iteration of the gradient ascent) and (k; m)) denotes the m bisection iteration in the hhhh outer iteration.
Algorithm Pricing algorithm
I: Initialize: Choose an exploration parameter E (0, r). Choose step size 1/ E (0, 1). Choose an accuracy parameter e e (0, 1/e). Choose queue length threshold qth Choose a two-price
parameter Choose xx1) D' as the initial point. Choose some initial price searching intervals
(e,, Po.a] for customer type Lee.5 Pr.j] for server type j. Define Ge, and éx.j according to (17
and 18 in Appendix
Define N = (l((1/e) and M := [log2 2. where 3 > 0 a constant.
2: Time step counter
3: Outer iteration counter is
4: repeat
5: // generate a random direction and two points
6: Choose unit vector u(k) (Réel uniformly random, i.c., |/
7: Let o. (k) = (z(k) + 5r(())) and J. == (x(k) Su(k))is
8:
Let XT (k)
Ejece zt x7(k) (k) Ejec, (k)( Hz (k) Eiec,, zt MJ (k) = DiEE,, (k)
9:
Let A (K) be a vector of X (k) 1..., Define similarly ( /= (k), and μ (T()
10:
// bisection search to approximate (k)), FT(A (k)), G,(1 (k)), G5(15 (k)) to esti-
mate the profits in the two points.
11:
i = 1 then
12:
For all let 2,t,(h, 1) = Ro,s' Per (ki 1) = Pc,i
13:
For all j. let p., (k; = P2ij" Pag (k, 1) = -Pa.j
14:
else
For all let 2.,, (ki, 1) Pt: (k: 1, 1, Ce,is Pe, Pe, MM Ce.
For all j, let p.t, 1),1) PTj (k: L, M, Ea,j. (k,
(k, 1) PT M, Ea.j
17:
end if
Let (k, 1) be vector of (k; 1), 1 1....I. I. Define similarly Dt (ki 1). p (k. 1).
p (k. 1).
19:
f. pt (), p. (K) =
Bisection A *k:), f (k), (k, (b. (k. 1), 4hh N,
Do Line 11 20 for X (k), 14 (k). Denote the counterparts of the prices by P. (k. 1), P (k: 1),
pe (k, M), P. (k, 1), P. (k, 1), P M).
22: // gradieen calculation
Let g(k)
[8]
(2 AT (k)p M) Σ M5 (k)ptt (k,)
25
( N7 (k)p Σ Mr (k) (k. u(())
25:
// gradient ascent update
26:
Projected Gradient Ascent: æ(k: + 1) = II + (k))
27:
A: < l: + 1;
28:
until
25

---

E
Definitions of Ce. and Eaj
The definitions of Geii and Ex,j are shown follows:
2 LF
Σ LF (1+ bog! (Po,t, maa Pe,s' mminm)
Cc,
6
J
Σ
Loy (I Ie, (Pa.s, Paij' Pass.min))
+ 2chsr; (1+ Lpp (pe,i,max - Pe, (gii)
+
+ 1
Σ 8=1
(L,E + Pe,t max) +
Σ (e + -Poss.max) +Baskmax)) + 28|E|1/2LF,
(17)
11e =0
+ 17 + + cc).
277 3//33 LG,
Σ LFg (1+ Dgg (De,) maa -P.s..min))
6
J
Σ Log (1+ Lasg Hezy (Doil.max max Pe..l Pa.s)miu)) + ZeLic, (177 (Daj.max - Pe...min))
Lazg
5'-1
+ +
Σ (Tg + De. +
Σ
E + Pa Prsy + 2818 1/2 L., (18)
8
- ( ( +
26

---

Bisection Search
We present the details of the bisection search method in Algorithm which is similar to that in [. The key difference over [I] is how we run the system to collect samples. The inputs to the bisection search include the arrival rates A x+/=(A (k) and 4 (kt), the price searching intervals h.pp::-(/ (ks, 1), the two-price parameter a, the threshold parameter p pk/ 1), p (k, 1). D 1).p."
4th the number of bisection iterations M, and the number of samples for each queue in each bisection iteration N. The bisection search will output the prices pe/ (ks, M) and ps + (k; M) such that A/ (l)) (r (ke, M)) and 2u / (k) Gj (pE.) (k. M)) for all i,
(1). (w).2t/ -k, / 1pt/-(e (k. 1), 2. (1.1). (k, (k, 2",,,,,,, Algorithm 2 Bisection (k), (+)) -
for m to M do
2: // Calculate the midpoints
3: Let Po t// (k, m) = _/ (pt/ (k, mk) + Po.i (k, (k,m) for all +/- (k, m) - (e.)- (k, m) + Ps.j +/- (k, mk) for all j 5: I/ Run the system to collect N samples with the midpoints
4:
Ps.j Let Pet
6: Let +// (k, m, denote the time slot when the price Pe.i +/- -=/((t, (k,m) is run for the nhth time for
+/- the customer queue i; Let 1 (ki, m, n) denote the time slot when the price Ps. (k, m) is run for the n²h time for the server queue, (1t// (k, m, ne))
7: t. (te (,, ne))) (1.
= =ProbTwoPrice po (K,,
(k, m). p +/- m), 9th .N, NNt // Key innovation over
where pe / (k, m) denotes vector of Peçi for = 1 to / do
+/- (k, M), I and similarly for ps + (k: (k, m).
8:
9:
// Estimate the arrival rates
10:
Let 2, (k.m) = N Σm= (t
(tt/ n, (k,m, n)) // sample average
I/ Update the price searching intervals
if A7 m). > 2, / (k) then
12:
E p+/- pt/-(k,m + 1) pe. (k, m), pt. (k, m + 1) Pe, (k, m)
14:
else
p./ (k, m 1) p.d/ 10/--(s,m)) (k, P.d (k, m + 1) pt/["(k:) m)
16:
end if end for
18:
for 1 J do
// Estimate the arrival rates
Let ag a// (k, = N En= A (t + (k, m, n)) // sample average
20:
21:
I/ Update the price searching intervals
if a mk uu +/- (k) then
22:
23:
+/ (k, m + P +/ p pt/-(k, (k,m 1) 2.1 (k, Pou
(k, m)
24:
else
p (k,m +1) = (k. +// (k, m + p.. p
Pa.j +/-
25:
end if
27:
end for
28:
end for Return / .), pt// -kk
29:
27

---

G
Probabilistic Two-Price Policy
The pseudo-code of the proposed probabilistic two-price policy presented in Algorithm 3 where ( (k, m, n) denotes the time slot in which the price of the midpoint is run for the th time for the customer queue i and +0 (k, m, n) for server queue j.
Algorithm 3 ProbTwoPrice p (ks m). P. (k. m) a, "h, N.
1: Let ne. (k; m) and (k, m) 0 for all i,
2: repeat
3: for 1 to I do
4: (t. 3 9th then set price Pe,.max for queue i // to control the maximum queue length
5: else if < (t, < 9th then for queue i, set price: control the average queue length
min(p?, (ks m) a, Pe,i.max); w.p. 1/2
po! (k,
w.p. 1/2
+/- else set price Pe,i (ke, m) for queue i.
6:
if price=pp.1 -/- (k. m) then (k, m) (k, m) + 1 // the number of useful samples
7:
8:
end for
9:
for j
do if (t)((t) > 4th then set price paj.min for queue j // to control the maximum queue length else 0 < (t)(t) < 8th then for queue j. set price: // to control the average queue length
10:
11:
max(p=] +/- (k, m)) - a, Pag.min), w.p. 1/2
+/- (k,
w.p. 1/2
+/- else set price Ps. (k, m) for queue j.
12:
if price=p5.) -/- (ks, m) then nay (ks, m) nee (k, m) // the number of useful samples
13:
14: end for
Run the system with the above set of prices for one time slot.
16: L- (+1
17: Terminate the algorithm when >
+/- 18: until for all queues i, (k, m.) >> N, i.e., the price Pe, (ke m) is run for at least N times and
+/- (ks, m) is run for at least N times for all queues j. nay (k. 3 N, i.e., the price P
19: Return (1, (k, m, n))) ME(N (1s 4/- (k, m, mef
28

---

H Details of the Simulation and Additional Numerical Results
H.1 Single-Link System
We present details of the simulation and additional simulation results in a single-link system in the following.
H.1.1
Setting
Consider system with customer queue and J server queue. The demand function of the customer queue is F()) 2(1 A), where À E [0, 1] is the arrival rate of the customer queue. The supply function of the server queue is G(u) = 2p,, where μ E [o, 1] is the arrival rate the server queue. We compare the performances among three algorithms:
This policy assumes that the demand and supply functiins are known. To balance queue length and regret, this policy uses the following two-price method. If the queue length is empty, uses the prices corresponding to the optimal solution of the fluid optimization problem. If the queue is nonempty, it uses a slightly-perturbed version of the optimal prices to reduce the arrival rates.
Two-price policy [2]
Threshold policy [I]: This policy does not know the demand and supply functions and uses learning-based pricing algorithm. To balance queue length and regret, this policy uses a threshold method, rejecting arrivals when the queue length reaches exceeds threshold.
Probabilistic two-price policy (proposed): This policy does not know the demand and supply functions. It uses novel probabilistic method, which adjusts the prices to reduce the queue length with a prefixed probability when the queue is nonempty.
H.1.2 Comparison
7 1/6, and 9th = = t- 1, 0.2 22/2, B 1.0, e. c, 6.0 x max 7, e), Gmin 0.01, which of the same order as in Corollary I The common parameters the three algorithm are set to be equal for fair comparison.
For the proposed algorithm,
0.2 t7,
To compare the performance of these algorithms, we consider an objective function defined as
Σ ((((())))) wE(We,(T))
(C,()( +F wF(Wa,(T)))
(19)
where W (r,)(T) denotes the waiting time of the customer arriving queue i time slot 7 and W (T)(()) denotes the waiting time of the server arriving at queue j at time slot 7. The constant w > 0 can be viewed as the compensation the platform pays for per unit time the customer/server wait. This
objective (9 is equivalent to
Profit(t) -
ΣΣ
(20)
where (t) denotes the total waiting time up to time for the 1tth customer arriving at queue i Ws,s.(()) (t) denotes the total waiting time up to time for the tth server arriving at queue j. and ws is constant. A similar objective is also used in (2). Note that the sum of waiting times of all customers and servers equal to the sum of the queue lengths over time, which counts every customer and server present at each time slot. Hence, the objective (20) is equal to
Profi((()
Σ E (ma(T) + Σeas(T)
Then, the regret of this objective is given by:
f(x
Profit(() Σ
E Σ
Qei(T) -
29

---

-[ Σ E
E[R()) wt..gg)
which is the sum of the profit regret and the holding cost.
In the simulation, we test two different w; w 0.001 and w 0.01. Note that the optimal profit each time slot is f(=*) 0.25 the fluid solution. Therefore, choosing a even larger w is not reasonable because further increasing will cause negative utility even for the case where the demand and supply functions are known.
Figure 2 in Section D shows the performance of these algorithms and the percentage improvement of the proposed probabilistic two-price policy over the threshold policy [ with 0.001.
The shaded areas in all figures in this paper represent 95% confidence intervals, calculated from 10 independent runs using the Python function reaborn.relpion
Figure present the comparison results with different weight, w 0.01, on the holding cost. We observe that the proposed probabilistic two-price policy significantly improves upon the threshold policy by up to 25%.
1.0 1e5
0.30
Two-price policy known
Proftt Rogret + 0.01x quean Longth
(Varma 2023)
Percentage Improvement (Profit Regrut o.nix Quaue Lengt))
0.8
Threshold policy (Yang Ying, 2024)
0.20
Probabilistic owa-price policy (Proposed)
0.15
0.05
0.00
0.2
-0.05
0.0
-0.1
0.2
0.4
0.6
0.8
0.2
0.4
0.8
1.0
1c6
(a) E[[(t)) + wtAvgQLen(t).
(b) Percentage improvement over the threshold policy
Figure 3: Comparison among the two-price policy (no learning, known demand and supply functions) (2). the threshold policy (1. and the proposed probabilistic two-price policy with 0.01, in single-link system.
The regret, the average queue length, and the maximum queue length of the algorithms are shown in Figure 4 Note that the X-axis and Y-axis of Figure 4 are in log-scale. The regret performance of the proposed probabilistic two-price policy is similar to the threshold policy (.]. However, we can see that the average queue length of the proposed probabilistic two-price policy is significantly better than the threshold policy because we use novel probabilistic two-price method to reduce the average queue length without hurting the regret performance. The slope of the proposed probabilistic two-price policy is significantly smaller than that of the threshold policy [.. which is consistent with our theoretical results. As for the maximum queue length, the performance of the proposed probabilistic two-price policy and that of the threshold policy are the same, because both uses threshold to reject the arrivals when the queue length exceeds the threshold. The two-price policy has a larger maximum queue length because it does not use such a hard threshold.
H.1.3 Tradeoff' Between Regret and Queue Length
Figure shows the tradeoff between profit regret and average queue length for the proposed prob- abilistic two-price policy as we change the parameter 7 from 1/12 1/6. Each point the blue
curve (regret) is generated by first computing the ratio log, R(t). which represents the growth order of log,
regret with respect to time, for each time slot E [10*, 100], and then averaging over these time slots.
Similarly, each point in the red curve (average queue length) is obtained by computing log, AvgQLen(() logg
30

---

2²
24
2
21
Profic negret
21
2'
Two Two-price policy known (Varma et al., 2023)
Two-price policy
(Varma al., 2023)
Threshold policy
2"
policy
21
(Yang Ying, 2024)
(Yang Ying, 2024)
Probabilistic two-pric prooppiiceeeee policy (Proposed)
Probabilistic two-price policy (Proposed)
2
2
2
29
2
2
2
2
2
2
Time
Time
(a) The profit regret.
(b) The average queue length.
2
24
2a
Moximum
2a
Twaa awa-price policy known (Varma al., 2023)
Threshold policy (Yang & Ying, 2024)
2
Probabilistic two price policy (Proposed)
27
2
2
(c) The maximum queue length.
Figure 4: Comparison of regret, average queue length, and maximum queue length among the two-price policy (no learning, known demand and supply functions) (2), the threshold policy [1], and the proposed probabilistic two-price policy, in single-link system.
and averaging over the same time slots. We observe that as 7 increases, the growth order of regret decreases while the growth order of average queue length increases, confirming the tradeoff predicted by our theoretical results. By a simple least square fitting, we can obtain the slopes of the curves in Figure 5]] The fitted function of the blue curve (regret) is y -1.484. 0.927 and the fitted function of the red curve (average queue length) is = 0.615r 0.011, which implies that the regret 7 70.977-14484 and the average queue length is 70.6655-0.011 Although they are exactly equal to 2 and 70.57 - -1..8444.0.. 00.615 x 224, which is similar to - -1/0.5 = -2. This result confirms
the near-optimal tradeoff, Ö(T1-7) versus ((T)/2), in Corollary
H.1.4 Sensitivity to Parameter Tuning
We test the sensitivity of the performance of the proposed probabilistic two-price policy to parameter tuning. We test the multiplicative constant of the parameters e, 6, and 1). Figure ( shows the performances for different multiplicative constants in the parameter i.e., the constant C' for e = Ct-27, We can see that the performances are almost same. Figure shows the performances for different multiplicative constants in the parameter ö, i... the constant C/ for Ct Figure shows the performances for different multiplicative constants the parameter 77, i.c., the constant for 77 Ct
H.2 Multi-Link System
We present simulation results in multi-link system in the following.
31

---

0.82
Profit Regret
0.80
Average Length
0.16
0.76
0.12
log
80.74
0.10
0.70
0.06
0.68
0.04
0.66
0.02
Figure 5: Tradeoff between regret and average queue length.
216
coefficient
E coefficient
24
0.6
0.6
0.8
2
1.0
Aucroge Length
Proftt Begrat
1.2
230
1.4
29
2
27
2
2
2
2
2
219
27
2
2
230
Time
Time
(a) The profit regret.
(b) The average queue length
2
coefficient
0.6
24
1.0
1.2
Maximum Quoue
2a
1.4
2a
21
29
2
225
Time
(c) The maximum queue length
Figure 6: Sensitivity testing for different for the proposed probabilistic two-price policy.
H.2.1 Setting
Consider a system with three types of customers and three types of servers (I = J. 3). The
compatibility graph E = {(1, 1), (1,3), (2, (2, (2, (3, 2). (3, 3)). The demand functions are (.(),) 2(1 X,) for all i 1,3. The supply functions are Gy(1t) 24, for all j 1, 2, 3. compare the same three algorithms as in the single-link simulation, i.e., the two-price policy 2 the threshold policy []] and the proposed probabilistic two-price policy.
32

---

2
6 coefficient
coefficient
2
0.1
0.2
0.2
212
0.3
0.3
Regret
0.4
0.5
0.5
28
26
2
22
2-1
2
2
2
210
Time
Time
(a) The profit regret.
(b) The average queue length
2a
6 coefficient
0.1
2a
0.2
0.4
Maximum Quzue
2
0.5
22
21
27
28
232
2
2
2
230
(c) The maximum queue length
Figure Sensitivity testing for different å the proposed probabilistic two-price policy.
H.2.2 Comparison
For the proposed algorithm, we set 7 = 1/6, and 17, 8 -
0.2 x 12/2 B = 1.0, e = = 8.0 x max(6, 7). ). Omin 0.01, which are the same order as in Corollary The common parameters of the three algorithm set be equal for fair comparison.
Consider the same objective as that in the single-link simulation.
Figure 9 present the comparison results with = 0.01, on the holding cost. We observe that the proposed probabilistic two-price policy significantly improves upon the threshold policy [T] by up to 34% for large f. Figure preseett the comparison results with a different weight, w 0.005. We observe that the proposed probabilistic two-price policy significantly improves upon the threshold policy by up to 12% for large We observe that in the multi-link system, initially for small I, proposed probabilistic Iwo-price policy may not perform as good as threshold policy. t. increases, our proposed policy quickly outperforms the threshold policy. This is because, as I. increases, the improvement in queue length performance under our proposed algorithm becomes more significant. Figure [I shows the performance of these algorithms with much smaller weight, w = 0.001. In this case, although our proposed policy does not perform as good as the threshold policy, it improves f increases. The comparison depends the weight on the holding cost and the time horizon.
II
The regret, the average queue length, and the maximum queue length of the algorithms are shown in Figure [2 The observations are similar to the single-link simulation. The regret performance of proposed probubilistic two-price policy is similar to the threshold policy [1] However, the average queue length of the proposed probabilistic two-price policy significantly better than the threshold policy. As for the maximum queue length, the performance of the proposed probabilistic two-price
33

---

2
n coefficient
coefficient
21c
0.2
212
0.3
2²
0.3
Regret
0.4
0.4
0.5
Queue
28
26
2
22
2-1
2
2
Time
Time
(a) The profit regret.
(b) The average queue length
23
coefficient
0.1
0.2
0.3
0.4
Maximum Quzue
2
0.5
22
21
27
232
2
2
2
230
(c) The maximum queue length
Figure Sensitivity testing for different v for the proposed probabilistic two-price policy.
policy and that of the threshold policy the same. The two-price policy has larger maximum
queue length.
H.3
Compute Resources
All the simulations computer. On a personal computer with Intel Core i5-9400 CPU @2.90GHz, 10 runs the simulation of the single-link system (T' 10%) for all three algorithms take approximately 20 minutes, and 10 runs of the simulation of the multi-link system (T 107) for all three algorithms take approximately 6 hours.
compute-inee intentsveenneeeeeeeeee and all results can be reproduced on standard personal
34

---

3.0
Two-price policy - known (Varma et al., 2023)
Purcantagn Impromemeet of (Profit (Proit Regret 0.01x Dueue Lengtt
2.5
Threshold policy
(Yhin & Ying, 2024)
0.2
2.0
Probabilistic two price palicy (Proposed)
0.000
1.5
-0.2
-0.4
1.0
-0.6
0.5
-0.8
0.0
1.0
0.6
0.8
Time
1c7
Time
1e7
(a) [[R(t)] wtAvgQLen(t).
(b) Percentage improvement over the threshold policy [[]
Figure 9: Comparison among the two-price policy (no learning, known demand and supply functions)
21. the threshold policy [I], and the proposed probabilistic two-price policy with w 0.01, in multi-link system.
2.00
0.6
Pramt Regret +0.000 0.005x Quaue Langh
1.75
Twa-price policy known
(Varma et al., 2023) 2023)
Percentarge Imprro mmprovement of 0.005 Length)
0.4
policy (Yang Ying. 2024)
1.50
0.2
Probabilistic two-price policy (Proposed)
1.25
0.0
1.00
0.75
-0.4
-0.6
0.25
00.8
0.00
0.2
0.4
0.5
0.8
1.0
Time
1c7
Time
1e7
[[M(O]] WLen))Len()).
Percentage improvement the threshold policy
Figure 10: Comparison among the two-price policy (no learning, known demand and supply functions) []. the threshold policy [T], and the proposed probabilistic two-prit two-price policy with w 0.005, in multi-link system.
1.4 1e6
0.0
Length
Two-price policy - known (Varma al., 2023)
(Prott Regret + 0.801 x Queue Lengthi
1.2
Threshold policy (Yang Ying, 2024)
-0.5
1.0
Purcentagn Imprrou improvement
Probabilistic two-price policy (Proposed)
-1.0
-1.5
0.6
Regret
0.4
0.2
0.0
0.6
0.6
0.8
Time
1c7
Time
1e7
(a) E[R(t)] wtAvgQLen(t).
(b) Percentage improvement over threshold policy
Figure 11: Comparison among the two-price policy (no learning, known demand and supply functions)
[] the threshold policy [1, and the proposed probabilistic two-price policy with w 0.001, in multi-link system.
35

---

2n
Two--rice policy known (Varma 2023)
224
Threshold policy (Yang Ying. 2024)
2
22
Probabilistic two-price policy (Proposed)
Proftt Regret
2
212
21
Two--rice palicy known
2a
20
2023)
Threshold policy (Yang Ying,
2-1
Probabilistic two-price policy (Proposed)
20
23
2
2
21
23
27
2
2
2
20
2
22
23
(a) The profit regret.
(b) The average queue length.
Maximum Length
2
22
2-
Two-price policy known (Varma et al., 2023)
Threshold policy (Yang Ying, 2024)
2-1
Probabilistic two-price policy (Proposed)
2-2
21
23
25
27
2
23
25
277
29
22
2
Time
(c) The maximum queue length.
Figure 12: Comparison of regret, average queue length, and maximum queue length among the two-price policy (no learning, known demand and supply functions) (2), the threshold policy [0. and the proposed probabilistic two-price policy, in multi-link system.
36

---

I
Societal Impacts
This paper presents work whose goal is to advance the fields of online learning in queueing systems. There are potential positive societal impacts, including improving efficiency and promoting prof- itability in applications like add-hailing, meal-delivery, and crowdsoureing. We are not aware of any negative societal impacts of this work.
37


Reviews:
[{"review_id": "VwMbawJ5nW", "reviewer": "Reviewer_C861", "summary": "The paper investigates online learning-based pricing policies in two-sided queueing markets with heterogeneous, price-sensitive arrivals, where customers and servers form matching pairs and depart from separate queues. The objective is to maximize platform profit while maintaining reasonable queue lengths, even when underlying demand and supply curves are unknown. The main contribution is the design and analysis of a dynamic, probabilistic pricing and matching policy that achieves a near-optimal tradeoff among regret $\\tilde{O}(T^{1-\\gamma})$, average queue length $\\tilde{O}(T^{\\gamma/2})$, and maximum queue length $\\tilde{O}(T^\\gamma)$. The paper provides theoretical analysis demonstrating improvements over prior learning-based approaches, and presents simulation results comparing the new method to relevant baselines.", "questions": "1. How does the method perform compared to recent RL/adaptive optimization baselines for online queue control? Why were these not included in the main experimental benchmark?\n\n2. Is it possible to estimate the demand function using nonparametric regression and make decisions based on the resulting estimated steady-state matching rates?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The model is well-motivated, addresses practical scenarios in online marketplaces, and is formalized with clear notation and reasonable economic and queueing assumptions. Assumptions are stated and discussed.\n\n2. The proposed algorithm introduces a randomized two-price policy to resolve the tension between learning and queue management, resulting in provably superior performance metrics. This dynamic and probabilistic treatment of pricing is argued to be widely applicable.\n\n3. The work provides a thorough theoretical analysis of the regret/queue length trade-off in learning-based pricing for two-sided queues. Regret and queue length bounds are carefully derived and supported by matching lower bounds, offering evidence for near-optimality up to log factors and strengthening the results in prior literature.\n\nWeaknesses:\n\n1. The proposed trade-off holds only for $\\gamma \\in (0, 1/6]$. For larger $\\gamma$, the bound on regret does not improve (remains $\\tilde{O}(T^{5/6})$), leaving a gap. The trade-off curve thus does not offer a smooth interpolation to the regime where queue lengths can be significantly higher for improved regret. Also, the regret bound hides large constants.\n\n2. The multi-stage learning algorithm (incorporating projected stochastic gradient, repeated bisection search, and a complex exploration mechanism) involves numerous tunable parameters ($\\eta$, $\\delta$, $\\epsilon$, $\\alpha$, $q^\\text{th}$) and repeated sample-collection via resets or altering queues. While the theoretical roles are justified, there is little discussion or analysis of runtime, computational costs, or scaling to large-scale practical systems (e.g., with many customer/server types).", "was_revised": true, "final_justification": "Having reviewed the rebuttal, I believe the paper is suitable for acceptance at NeurIPS.", "rebuttal": "We thank the reviewer for the positive comments and valuable suggestions.\n\n**Comment:** \"The multi-stage learning algorithm (incorporating projected stochastic gradient, repeated bisection search, and a complex exploration mechanism) involves numerous tunable parameters ($\\eta$, $\\delta$, $\\epsilon$, $\\alpha$, $q^{\\mathrm{th}}$) and repeated sample-collection via resets or altering queues. While the theoretical roles are justified, there is little discussion or analysis of runtime, computational costs, or scaling to large-scale practical systems (e.g., with many customer/server types).\"\n\n**Response:** The numerical results in Appendix M.1.4 (Figures 6,7,8) show that the tunable parameters can take a wide range of values while maintaining similar performance. Therefore, we can just set a $\\gamma\\in(0,1/6]$ according to our main results in Section 3 to balance the regret and queue lengths. Then the values of $\\eta$, $\\delta$, $\\epsilon$, $\\alpha$, and $q^{\\mathrm{th}}$ will be determined by $\\gamma$, as shown in Corollary 1 in Appendix A.2.\n\n\nThe proposed pricing algorithm has computational complexity $\\tilde{O}((I+J)T + IJT^{1-4\\gamma})$, along with $T^{1-4\\gamma}$ calls to a projection oracle, where $T$ is the time horizon, $I$ is the number of customer types, $J$ is the number of server types. The projection can be implemented by solving a convex quadratic program using interior point methods, which have a computational complexity of $\\tilde{O}((IJ)^{3.5})$ [A]. Hence, the overall computational complexity is $\\tilde{O}((I+J)T + (IJ)^{3.5} T^{1-4\\gamma})$.\n\nThe regret upper bound scales with the number of customer types $I$ and server types $J$ as $O(I^4J^4(I+J)T^{1-\\gamma})$. \nThe average queue length upper bound scales with $I$ and $J$ as $O(IJ(I+J)T^{\\gamma/2})$.\nThe maximum queue length does not scale with $I$ or $J$. We believe the dependencies on $I$ and $J$ can be improved, as our analysis mainly focuses on obtaining the correct dependence in terms of the time horizon $T$.\n\nWe will add the above computational complexity and the scaling to the revision.\n\n**Comment:** \"How does the method perform compared to recent RL/adaptive optimization baselines for online queue control? Why were these not included in the main experimental benchmark?\"\n\n**Response:** Most works on reinforcement learning (RL) for queueing in the literature [B] [C] [D] [E] [F] do not utilize the special structure of our pricing and matching problem, and it is difficult to trade off between profit and queue length. When facing the curse of dimensionality of queueing systems, the works [B] [C] [E] use deep RL, which does not have any theoretical guarantee on the performance. On the other hand, our approach circumvents the curse of dimensionality by restricting to the set of probabilistic two-price policies as opposed to a fully dynamic policy, as we know that a two-price policy is near-optimal. This way, we only need to learn $O(I+J)$ parameters as opposed to $O(e^{I+J})$ for a fully dynamic policy.\n\n\nOther adaptive optimization approaches:\nLipschitz bandit algorithms, such as those that discretize the price space and apply UCB-based methods, fail to balance matching rates and arrival rates on both sides, making it difficult to control queue lengths. Bandit convex optimization is also inapplicable, as the objective is nonconcave in prices, and the constraint set for balancing arrival rates is both nonconvex and unknown in terms of prices.\n\nWe will add a discussion in the revision.\n\n\n**Comment:** \"Is it possible to estimate the demand function using nonparametric regression and make decisions based on the resulting estimated steady-state matching rates?\"\n\n**Response:** It is difficult because we are considering an online learning setting where learning and decision making occur simultaneously. Nonparametric regression does not address how to select a data collection policy.\nIf we estimate the demand function by trying different prices without considering the arrival-rate balance or regret, both queue lengths and regret can grow linearly over time in the estimation process.\nFor example, suppose that we try prices uniformly in the price space. For each queue, to obtain an accuracy of $\\zeta$ for the estimation of the demand/supply function, we need to discretize the space into $\\Theta(1/\\zeta)$ points, and for each point, we need at least $\\Theta(1/\\zeta^2)$ samples according to the central limit theorem. In this process, the queue length will increase linearly over time, up to $\\Theta(1/\\zeta^3)$. Using the estimated functions, we can obtain a solution with accuracy $\\zeta$, and we can use this solution until the time horizon $T$. Hence, the worst-case average queue length will be $\\Theta(1/\\zeta^3 + (T - 1/\\zeta^3)\\zeta)$. The lowest worst-case average queue length that this approach can achieve is $\\Theta(T^{3/4})$ with $\\zeta=T^{-1/4}$, while our approach can achieve a much smaller average queue length $\\tilde{\\Theta}(T^{1/12})$ with $\\gamma=1/6$.\n\nThere is a short discussion on Page 5, Lines 161-164, and we will add a more detailed discussion in the revision.\n\n**References**\n\n[A] Yurii Nesterov and Arkadii Nemirovskii. Interior-point polynomial algorithms in convex programming. SIAM, 1994.\n\n[B] Majid Raeis, Ali Tizghadam, and Alberto Leon-Garcia. Queue-learning: A reinforcement learning approach for providing quality of service. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 461–468, 2021.\n\n[C] Jim G Dai and Mark Gluzman. Queueing network controls via deep reinforcement learning. Stochastic Systems, 12(1):30–67, 2022.\n\n[D] Bai Liu, Qiaomin Xie, and Eytan Modiano. Rl-qn: A reinforcement learning framework for optimal control of queueing systems. ACM Transactions on Modeling and Performance Evaluation of Computing Systems, 7(1):1–35, 2022.\n\n[E] Haozhe Chen, Ang Li, Ethan Che, Jing Dong, Tianyi Peng, and Hongseok Namkoong. Qgym: Scalable simulation and benchmarking of queuing network controllers. Advances in Neural Information Processing Systems, 37:92401–92419, 2024.\n\n[F] Yashaswini Murthy, Isaac Grosof, Siva Theja Maguluri, and R. Srikant. Performance of npg in countable state-space average-cost rl, 2024."}, {"review_id": "vIAaWaogfr", "reviewer": "Reviewer_6iW3", "summary": "This paper studies the two-sided matching model developed in [1], where multi-class arrivals occur on each side (think riders on one side and drivers on the other). The platform controls \"pricing\" (affects arrival rates) and \"matching\" decisions in each round (the latter is subject to a compatibility graph) to ensure long-term stability of the system; matched units exit the system immediately. Metrics of interest are (i) Profit over T rounds; (ii) Avg. Queue Length over T rounds; and (iii) Max Queue Length over T rounds, starting from an empty system at t=0. The authors establish a near-optimal trade-off between profit-regret and avg. queue length, which is achieved by their pricing/matching algorithm. A bound on the max queue length is also provided. Numerical experiments are provided showing effectiveness of the proposed solution vis-a-vis the baseline policies in [1] and [2].", "questions": "Please see the previous section.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: \n1. Paper is well-written and accessible.\n2. The proposed pricing/matching algorithm achieves a near-optimal trade-off between profit-regret and avg. queue length, while matching the bound on max queue length from prior work.\n\nWeaknesses:\n1. The model and matching algorithm are identical to [1], lacking any novelty. The innovation lies in the proposed pricing algorithm, which is a probabilistic adaption of the two price policy in [2] (for known supply and demand) to the online learning setting -- this adaption achieves the desired trade-off.\n2. A very similar (near-optimal) trade-off is already established in [2], albeit under a slightly different (but related) scaling parameter.\n3. It appears that the paper borrows heavily from the modeling, algorithmic, and analytic machinery already built in [1,2].\n4. The underlying model itself (in my opinion) is not general enough (like K-MAB for instance) to warrant an independent study on a question already addressed in [1] to a large extent.\n\nOf course, the paper identifies a gap (namely, the trade-off implied by results in [1] being weaker than that established in [2]) and addresses it via a neat solution. But weaknesses pointed out above give it an incremental look that may not interest many.\n\nThat said, I'm open to revising my scores pending a convincing author rebuttal.", "was_revised": true, "final_justification": "The authors provided some additional context which was useful. There are technical merits to the algorithm/analysis that warrant an accept. That said, there is room to improve the writing/positioning for a broader audience especially given that this paper builds upon prior work [1,2] that itself is somewhat niche.", "rebuttal": "We greatly appreciate the reviewer's openness in reevaluating the score. We first would like to comment that it is indeed true that both the model and the matching algorithm are identical to [1]. In fact, both the model and MaxWeight matching are standard in the two-sided queue literature, not just in this paper and [1,2]. The contribution of this paper is on learning and pricing, not on modeling and matching. Our new probabilistic two-price policy allows us to achieve the near-optimal regret-queue tradeoff and close a significant gap in the literature. The proof machinery follows Lyapunov drift analysis, which is standard in stochastic control and online learning. However, while the structure of the proof and the machinery may look standard and similar to [1], like using the Lyapunov analysis for stability in control, every proof requires a customized analysis of the drift to obtain the desired bound. The drift analysis is not a plug-and-play.  Proving our result requires several technical innovations that will be explained later in this rebuttal. \n\n**Comment:** \"A very similar (near-optimal) trade-off is already established in [2], albeit under a slightly different (but related) scaling parameter.\"\n\n**Response:** Thank you for your comment. As you rightly pointed out, the near-optimal trade-off scaling in the case of known demand and supply curves is known in the literature [2]. However, prior to our work, it was unclear whether the same trade-off continues to hold in the learning setting when these curves are unknown. We fill this gap by showing that a similar trade-off continues to hold, albeit the range of $\\gamma$ is restricted to $[0, 1/6]$, which is primarily because of the errors introduced due to learning. To establish this result, we needed to overcome several technical challenges as compared to [2], and we outline the two main challenges below:\n\n- As the demand and supply curves are known in [2] and as they define a one-to-one mapping between the prices and the arrival rates, the analysis in [2] directly works with the arrival rates without loss of generality. However, in the learning setting, we are restricted to controlling the prices and observing the arrival rates as a response. This restriction introduces the first major challenge: the optimization problem (1)-(3) is nonconvex in the space of prices, and the constraints are nonlinear in terms of the prices, and it involves the unknown demand and supply curves. Thus, we cannot directly implement a zero-order learning scheme on (1)-(3), and so, we are forced to go back and forth in terms of prices and (estimated) arrival rates.\n- The objective of [2] is to understand the regret-queue-length trade-off in the steady state. While in the learning setting, it doesn't make sense to consider such a long-term objective to analyze the cost of learning. Thus, we carry out a finite-time analysis of the underlying queueing system, which leads to several technical challenges. Please refer to the comment below for a more detailed discussion on the technical challenges.\n\n\n**Comment:** \"It appears that the paper borrows heavily from the modeling, algorithmic, and analytic machinery already built in [1,2].\"\n\n**Response:** The novel algorithmic and analytic contributions compared to [1,2] include:\n\n- **Algorithmic contributions:** Our novel probabilistic two-price policy is fundamental to achieving the near-optimal tradeoff between profit regret and average queue length. In particular, the pricing policies in [1] and [2] are unable to achieve this trade-off in the learning setting. Specifically, [1] introduces a static pricing policy with a limited waiting area, which achieves a sub-optimal trade-off scaling as it lacks a dynamic component in the pricing policy. We have discussed this briefly on Page 6, Lines 215–220 in the paper. On the other hand, while the two-price policy of [2] is dynamic, it still may fail to achieve the trade-off in the learning setting. In the learning setting, price adjustments not only control queues but also affect the learning process. Adjusting prices introduces bias into arrival samples, degrading gradient estimates and increasing regret. Our probabilistic policy addresses this by reducing arrival rates by $\\Theta(\\alpha)$ (via adjusting prices) with a constant probability when the queue is nonempty. This probabilistic component ensures both negative drift and fast learning with unbiased samples. By tuning $\\alpha$, we achieve a near-optimal balance between queue length and regret. (See Page 8, Lines 336–352.) We continue to use the MaxWeight matching algorithm as in [1, 2], as it is known to perform well and is agnostic to the demand and supply curves; thus, it can be easily implemented in the learning setting. Note that MaxWeight is a standard approach that has been used beyond two-sided queues, including high-speed switches, wireless scheduling, etc.   \n- **Technical/Analytic contributions:** Proving that the probabilistic two-price policy achieves a near-optimal tradeoff requires addressing new analytical challenges beyond [1,2], as outlined on Pages 8–9, Lines 353–364. In particular, our approach has the following two technical innovations that go beyond both [1] and [2], which are only possible due to our probabilistic two-price policy:\n    - First, we bound the number of biased samples caused by price adjustments. This is handled by showing, via Wald’s lemma (Appendix I.4.1), that the time spent on such adjustments is bounded while the time spent in collecting unbiased samples is sufficient.\n    - Second, we bound the regret from these adjustments by analyzing both first-order and second-order errors. Our bounds on the first-order errors are much sharper compared to [1], resulting in a better regret-queue-length trade-off. Moreover, unlike [2], this requires a more involved analysis in our finite-time learning setting, where the actual arrival rates are suboptimal, vary across iterations, and only approximately satisfy the balance equation. We address this by combining the KKT conditions (Appendix I.3) and a drift argument (Lemma 5, proof in Appendix L).\n- **Fundamental tradeoff:** Lemma 1 establishes a new lower bound beyond [1,2], identifying the fundamental tradeoff between regret and queue length in the finite-time setting.\n\n\n\n**Comment:** \"The underlying model itself (in my opinion) is not general enough (like K-MAB for instance) to warrant an independent study on a question already addressed in [1] to a large extent.\"\n\n**Response:** Thank you for your comment. We believe that the two-sided queueing model with pricing and matching applies to many real-world systems, such as ride-hailing, meal delivery, and crowdsourcing platforms.\nFor example, in ride-hailing, riders and drivers form two sides of queues awaiting matching. The platform charges riders and pays drivers upon arrival, with prices influencing their arrival rates. A similar structure holds for customers and couriers in meal delivery, and for tasks and workers in crowdsourcing. In these systems, the demand and supply curves are often unknown, and one needs to constantly learn them using the historical data. One approach is then to use the estimated curves to solve the optimal pricing scheme (see comment \\#3 of Reviewer C861 for more discussion), but this approach may lead to linearly growing regret and queue length in the estimation process. Such a difficulty motivated the analysis in this work, which combines estimation with optimization.\n\nAlso note that our probabilistic approach decouples the complex correlations between *fast learning* (obtaining useful samples for learning) and *low queueing delay*, while providing the flexibility to tune the policy parameters to optimize objectives such as *profit maximization*. We believe such an idea is quite general and may be broadly applicable to online learning in queueing systems. We briefly discuss the potential of our approach on Page 14, Lines 537-546."}, {"review_id": "UFS90guoyh", "reviewer": "Reviewer_jgX5", "summary": "This paper studies pricing and matching in a two-sided market with both demand queues and server queues. The authors propose an online algorithm and analyze the corresponding performance metrics, including upper bounds on regret, average queue length, and maximum queue length. Since these metrics inherently conflict with one another, the authors also characterize the trade-off between regret and average queue length and show that the resulting trade-off is optimal.", "questions": "The authors compare their results to Varma et al. (2023) and Yang & Ying (2024) throughout the paper. From the perspective of algorithm design, how does the proposed algorithm fundamentally differ from the one in Yang & Ying (2024)?\n\nEchoing the weakness above, I would appreciate a more concrete definition or intuitive explanation of the Pareto frontier. The authors repeatedly emphasize that $(1 - \\gamma)$ and $\\gamma$ is not an optimal trade-off, while $(1 - \\gamma)$ and $\\gamma/2$ is optimal. Could the authors clarify what this trade-off represents and why one is considered better than the other?\n\nMy next question concerns the definition of profit at the bottom of Page 3. According to the current definition, any customer who joins the queue contributes to profit, regardless of when (or whether) the customer is served or how long the wait time is. Suppose the algorithm sets a very low price in the last period $T$, causing many customers to join the queue. Under the regret definition in Equation (5), would this result in negative regret? Could the authors clarify how this edge case is handled?\n\nIn Lines 201 and 202, why does the equation $Q_c(t)^2 + Q_s(t)^2 = (Q_c(t) + Q_s(t))^2$ hold? What is the intuition behind this equality?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe paper is well written, and the motivation, problem formulation, assumptions, and algorithm analysis are all clearly presented. In particular, the authors provide thoughtful and meaningful discussions to justify their assumptions and to contextualize the results in comparison with existing literature.\n\nWeaknesses:\n\nThe performance metric, i.e., the Pareto frontier, is not explicitly defined in the paper. I suggest that the authors introduce this concept, even briefly, to help readers who are unfamiliar with multi-objective trade-off analysis. For example, the authors repeatedly state that the trade-off between $(1 - \\gamma)$ and $\\gamma$ is suboptimal, while $(1 - \\gamma)$ and $\\gamma/2$ is optimal. Without a formal definition or intuitive explanation of the Pareto frontier, this claim is not clear to readers with limited background in this area.", "was_revised": true, "final_justification": "I appreciate the authors’ detailed response and their efforts to clarify key aspects of the paper. My questions are all well addressed, particularly regarding the algorithmic contribution. Overall, I find this paper will be of interest to the community, and thus I would like to keep my original positive rating.", "rebuttal": "We thank the reviewer for the positive comments and valuable suggestions.\n\n**Comment:** \"From the perspective of algorithm design, how does the proposed algorithm fundamentally differ from the one in Yang \\& Ying (2024)?\"\n\n**Response:** The probabilistic two-price policy is the fundamental difference compared to (Yang \\& Ying, 2024).\nYang \\& Ying (2024) employs a pricing policy with an admission control threshold. When the queue length reaches or exceeds the threshold, any new arrivals will be rejected to control the queue length.\nThis approach fails to achieve the optimal $1-\\gamma$ versus $\\gamma/2$ tradeoff as discussed in on Page 6, Lines 215–220.\nThe two-price policy in (Varma et al., 2023)---without our probabilistic component---is insufficient in the learning setting. \nIn (Varma et al., 2023), the arrival rate is reduced by a small amount when the queue exceeds a threshold, inducing a negative drift that reduces the queue lengths in expectation. However, in the learning setting, price adjustments not only control queues but also affect the learning process. Adjusting prices introduces bias into arrival samples, degrading gradient estimates and increasing regret. \nOur novel probabilistic two-price policy addresses this by reducing arrival rates by $\\Theta(\\alpha)$ (via adjusting prices) with a constant probability when the queue is nonempty. This probabilistic component ensures both negative drift and fast learning with unbiased samples. By tuning $\\alpha$, we achieve a near-optimal balance between queue length and regret. (See Page 8, Lines 336–352.)\n\n**Comment:** \"Echoing the weakness above, I would appreciate a more concrete definition or intuitive explanation of the Pareto frontier. The authors repeatedly emphasize that $1-\\gamma$ and $\\gamma$ is not an optimal trade-off, while $1-\\gamma$ and $\\gamma/2$ is optimal. Could the authors clarify what this trade-off represents and why one is considered better than the other?\"\n\n**Response:** We will add the following definition in the revision.\nLet $E_{\\pi,d}[R(T)]$ denote the expected profit regret under policy $\\pi$ and problem instance $d$. The problem instance $d$ specifies the number of customer queues, the number of server queues, the set of compatible links, and the demand and supply functions. Let $\\mathrm{AvgQLen}_{\\pi,d}(T)$ denote the average queue length under policy $\\pi$ and problem instance $d$. \nLet $(x(\\pi),y(\\pi))$ denote the exponents of the objective values under the worst case, i.e., \n\n$$\nx(\\pi)\\coloneqq \\limsup_{T\\rightarrow\\infty} \\log_T (\\sup_d \\mathbb{E}_{\\pi,d}[R(T)])\n$$\n\nand \n$$\ny(\\pi)\\coloneqq \\limsup_{T\\rightarrow\\infty} \\log_T (\\sup_d \\mathrm{AvgQLen}_{\\pi,d}(T)).\n$$\n\nA point $(x(\\pi_1),y(\\pi_1))$ is said to be better than another point $(x(\\pi_2),y(\\pi_2))$ if $x(\\pi_1) \\le x(\\pi_2)$ and $y(\\pi_1)\\le y(\\pi_2)$\nwith at least one inequality strict.\n\nA point $(x(\\pi),y(\\pi))$ is Pareto-optimal if there is no other policy $\\pi'$ that satisfies $x(\\pi') \\le x(\\pi)$ and $y(\\pi')\\le y(\\pi)$\nwith at least one inequality strict. The set of all Pareto-optimal points forms the Pareto frontier.\n\nAccording to the above definition, $(1-\\gamma,\\gamma/2)$ is better than $(1-\\gamma,\\gamma)$ since $\\gamma/2 < \\gamma$, which means that we can achieve orderwise smaller average queue length while maintaining the same order of profit regret. The $1-\\gamma$ versus $\\gamma/2$ tradeoff means that as we increase the value of $\\gamma$, the profit regret $\\tilde{\\Theta}(T^{1-\\gamma})$ decreases while the average queue length $\\tilde{\\Theta}(T^{\\gamma/2})$ increases. Lemma 1 shows that this tradeoff is Pareto-optimal for $\\gamma\\in[0, 1/2]$ for a large class of policies.\n\n**Comment:** \"According to the current definition, any customer who joins the queue contributes to profit, regardless of when (or whether) the customer is served or how long the wait time is. Suppose the algorithm sets a very low price in the last period $T$, causing many customers to join the queue. Under the regret definition in Equation (5), would this result in negative regret? Could the authors clarify how this edge case is handled?\"\n\n**Response:** Since our model is discrete-time and the arrival in each time slot/period is Bernoulli, at most one customer will arrive for each queue in each time slot. Hence, only changing the policy in the last period will not significantly influence the regret, and the influence is negligible when $T$ is large. \nIf we set this price for many periods to reduce the profit regret, the queue length will increase significantly. \nThe profit regret defined in (5) could possibly be negative under certain extreme policies, but this comes at the cost of very large queue lengths, which are impractical in real systems. Lemma 1 shows that the regret will not be negative if the average queue length is small.\n\n**Comment:** \"In Lines 201 and 202, why does the equation $Q_c(t)^2 + Q_s(t)^2 = (Q_c(t) + Q_s(t))^2$ hold? What is the intuition behind this equality?\"\n\n**Response:** This equation holds since $Q_c(t)Q_s(t)=0$ for any $t$. \nThe intuition is that if both queues are nonempty, the customers and servers should have already been matched under the greedy matching policy, so such a situation should not occur."}, {"review_id": "1eYTQUMMhk", "reviewer": "Reviewer_QxRW", "summary": "The paper studies a queuing system where customers and servers have probabilities to join the system at each time step. These probabilities depend on prices set by the learner, the higher the price of the customer, the smaller probability the customer joins, and conversely for the server. The mapping between prices and probabilities of arrival is unknown, contrary to earlier references.\n\nThe goal of the learner is to provide a Pareto-optimal tradeoff between the two following objectives. (1) maximizing the profit, which is computed from the fact that the learner pays the servers (with the prices set to the servers) and earns money from the customers (again with the prices set to the customers). (2) minimising the queue length, that is taking care that not too many customers and servers join the system and do not exit it quickly.\n\nThe paper defines a notion of cumulated regret, as the difference between the achieved profit and a profit obtained by optimising a \"static\" version of the queuing system, where the optimisation necessitates to know the mapping between prices and probabilities of arrival. The paper proposes a new algorithm that has an hyper parameter. Varying the hyper-parameter enables to explore the Pareto front of the problem, by giving Pareto-optimal pairs of regret / queue length. The algorithm has a learning component of the mapping between prices and probabilities of arrival. The paper provides a family of lower bounds that confirm Pareto-optimality. Finally, numerical experiments are provided, confirming the improvement brought by the new algorithm, over existing ones.", "questions": "I am not sure to understand well the sentence on Lines 79-80.\n\nSome readers may not be familiar with the definition of a M/G/1 queue. \n\nLine 93 sets(sides), a space is missing.\n\nLine 100, this is for all i,j?\n\nLine 110-117. I am troubled by the mapping from arrival rate to price. This can erroneously make the reader think that prices are caused by arrival rates? However, I understand that the learner chooses the prices freely, and that the chosen price causes an arrival rate. Would it be clearer to rather introduce mappings from prices to arrival rate?\n\nLemma 1 is for I = J = 1. Could there be a similar lower bound for general values of I and J?\n\nIn Figure 2 which value of the hyperparameter gamma was used?", "limitations": "YES", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "STRENGTHS I think the topic is relevant, interesting, and elegant, being at the crossroads between learning and queuing theory. The theoretical setting is precisely introduced and the proofs are significant and appear to be challenging. The results provide an improvement on the literature, as the previous literature either provided guarantees that were not Pareto-optimal, or worked with known mappings between prices and probabilities of arrival.  \n\n\nWEAKNESSES This is just a minor weakness in my opinion: the paper uses a significant space of the main text to explain the challenges to establish their results (end of Section 2, end of Section 4). This space could have been used to provide more technical details or pedagogical explanations (like the very clear Figure 1).", "was_revised": true, "final_justification": "Given the author's response to me, and to the other reviews, I am quite confident in my positive evaluation of the paper, in the end.", "rebuttal": "We thank the reviewer for the positive comments and valuable suggestions.\n\n**Comment:** \"I am not sure to understand well the sentence on Lines 79-80.\"\n\n**Response:** Thank you for catching the grammatical error and for letting us know that the original wording was hard to follow.\nWe will rewrite the sentence as follows:\n\n\"One line of work views the queueing system as a Markov decision process (MDP) and uses reinforcement learning methods in an attempt to learn a global optimal policy [15, 16]. These methods are broadly applicable to many types of queueing systems.\"\n\n**Comment:**\n\"Some readers may not be familiar with the definition of a M/G/1 queue.\"\n\n**Response:**\nWe will rewrite the sentence as follows:\n\n\"Closest to ours is [19] that learns to price for a queueing system with a single server and a single queue, where arrivals follow a Poisson process and service times are independent and identically distributed with a general distribution.\"\n\n**Comment:** \"Line 93 sets(sides), a space is missing.\"\n\n**Response:** Thanks for pointing out. We will add a space in the revision.\n\n**Comment:** \"Line 100, this is for all i,j?\"\n\n**Response:** Yes, we observe queue lengths for all $i,j$. We will clarify it in the revision.\n\n**Comment:** \"Line 110-117. I am troubled by the mapping from arrival rate to price. This can erroneously make the reader think that prices are caused by arrival rates? However, I understand that the learner chooses the prices freely, and that the chosen price causes an arrival rate. Would it be clearer to rather introduce mappings from prices to arrival rate?\"\n\n**Response:** Thanks for pointing out. We originally wanted to keep the notation consistent with [1,2]. In the revision, we will first introduce mappings from prices to arrival rate and then introduce the inverse mapping.\n\n**Comment:** \"Lemma 1 is for I = J = 1. Could there be a similar lower bound for general values of I and J?\"\n\n**Response:** Thank you for your comment. While our lower bound is restricted to the special case of $I=J=1$, it is sufficient to conclude the worst-case near-optimality of our upper bound. While we do not prove a formal lower bound for general $I, J$, intuitively, such a lower bound should hold generally. In particular, a general two-sided queueing model with a general compatibility graph should be worse off compared to the two-sided queueing model on a complete bipartite graph $G(I \\cup J, I \\times J)$. In addition, this complete bipartite graph model behaves similarly to a two-sided queueing model with $I=J=1$, where all the waiting customers and waiting servers are clubbed into a single queue [resource pooling]. Thus, the regret and queue lengths for a general two-sided queueing model could be lower bounded by its corresponding ``resource pooled'' single-link ($I=J=1$) two-sided queue.\n\n**Comment:** \"In Figure 2 which value of the hyperparameter gamma was used?\"\n\n**Response:** We set $\\gamma=1/6$ in Figure 2, which is mentioned in Appendix M.1.2. We will add this in the main text in the revision."}]

Author rebuttal:

Meta-review: **Summary**

The paper studies a two-sided market with price-sensitive customers and servers, aiming to maximize platform profit while controlling queues. It proposes an online-learning pricing policy that achieves near-optimal performance, improving regret–queue length trade-offs over prior work. The policy balances learning efficiency with system stability through dynamic and probabilistic mechanisms.

**Strengths**

The model studied in the paper is well motivated and the paper provides interesting results.

**Weaknesses**

There are only some minor issues raised by the Reviewers (see the reviews).

**Decision**

All the Reviewers agree that this is a good paper. Thus, I recommend **acceptance**.
Decision: Accept (poster)