Learning-Based Pricing and Matching for Two-Sided Queues

1. Introduction

We study pricing and matching in two-sided queueing systems with multiple types of customers and servers. Take ride sharing (Uber, Lyft, etc.) as an example. A ride order (request) can be viewed as a customer, and an available driver can be viewed as a server. A ride order can have multiple types. For example, we can view different numbers of passengers in the order as different customer types. We can also view different pick-up locations of the order as different customer types. A driver can also have multiple types. For example, we can view different vehicle capacities as different server types. We can also view different locations of the drivers as different server types. Each type of waiting ride order or driver joins a separate queue, forming a bipartite graph with customer-side (passenger-side) queues and server-side (driver-side) queues. We consider a discrete-time system. At each time slot, the ride-sharing platform will determine a price for each customer or server type. If a passenger accepts the price, they will be charged and join the queue. Similarly, if a driver accepts the price, they will be paid and join the queue. Therefore, the arrival rate of each type of ride order (or driver) is governed by the corresponding price according to some unknown demand (or supply) function. After that, the platform will match the drivers and ride orders in the queues if their types are compatible. For example, if the customer type is the number of passengers in the ride order and the server type is the capacity of the vehicle, then their types are compatible if the capacity of the vehicle is no less than the number of passengers in the ride order. The matched pairs then leave the system. The same process repeats in the next time slot. The profit of the platform is equal to the income from ride orders minus the cost paid to drivers. Assuming the demand and supply functions are unknown, the goal is to design pricing and matching algorithms to maximize the total profit of the platform over a finite time horizon while keeping the queue lengths of both customers and servers below a predetermined threshold.

Similar pricing and matching problems in two-sided queues have been studied in the literature (Caldentey et al. 2009; Adan and Weiss 2012; Gurvich and Ward 2015; Nguyen and Stolyar 2018; Chen and Hu 2020; Varma et al. 2020, 2023; Hu and Zhou 2022; Vaze and Nair 2022; Aveklouris et al. 2023, 2024). Caldentey et al. (2009), Adan and Weiss (2012), Hu and Zhou (2022), and Aveklouris et al. (2023, 2024) study matching problems in two-sided queueing systems with multiple types of demand and multiple types of supply. Nguyen and Stolyar (2018) study a two-sided queueing system with on-demand servers with the goal of designing adaptive server invitation scheme to minimize waiting times. Gurvich and Ward (2015) study a matching problem for multisided queues. However, these works do not consider pricing. Varma et al. (2020) and Chen and Hu (2020) study pricing and matching problems in two-sided queues, but they consider scenarios with strategic demand side and/or supply side, which is different from our setting, where customers and servers are not strategic, and their arrival rates are based on demand and supply functions. Vaze and Nair (2022) consider a two-sided queueing system where servers arrive at a fixed rate, and the arrival rate of customers is controlled by the price. They consider one-sided pricing and single-type customers and servers, whereas we consider two-sided pricing and matching and multiple customer and server types. The most relevant work in the literature is Varma et al. (2023), whose model is similar to ours. The differences between Varma et al. (2023) and ours include the following:

• The key difference is that they assume that the platform knows the demand and supply functions, whereas in our setting, the demand and supply functions are unknown.

• The objective in Varma et al. (2023) is the asymptotic long run expected profit of the platform subtracting a penalty that is linear in the queue length, whereas our objective is to maximize the total profit of the platform over a finite time horizon while keeping the queue lengths below a predetermined threshold during the entire time horizon.

• Varma et al. (2023) consider a large-scale regime in which they scale the arrival rates and study the profit loss in steady state. We focus on finite-time analysis without scaling the arrival rates.

There are some other related works about learning-based dynamic pricing and matching. Besbes and Zeevi (2015) study dynamic pricing with demand learning but they do not consider queueing. Chen and Shi (2024) study a dual-sourcing inventory system with demand learning, which is different from our two-sided queueing system. Tassiulas and Ephremides (1990) and Srikant and Ying (2014) study MaxWeight algorithms for scheduling in one-sided multiserver queueing systems. Our matching algorithm can also be seen as a MaxWeight algorithm but applied to a two-sided matching setting (Varma et al. 2023). Flaxman et al. (2004), Agarwal et al. (2010), Duchi et al. (2015), Shamir (2017), and Lattimore (2024) study zero-order gradient descent algorithms, some ideas from which are incorporated into parts of our pricing algorithm. There are other online learning algorithms in queueing systems (Chen et al. 2023, 2024; Yang et al. 2023), but they consider only one-sided queueing system.

The key challenge of our setting is that the demand and supply functions are unknown. Learning the demand and supply functions explicitly will not be adaptive if the demand or supply functions change over time. Therefore, we propose to learn and make pricing and matching decisions simultaneously. Although several candidate approaches exist, they are not suitable for our setting. One idea is to formulate the problem into a Markov decision process (MDP) and then use reinforcement learning (RL) to solve the MDP approximately. However, the state space of this MDP increases exponentially with the number of queues (i.e., customer and server types), so it is difficult to solve due to the curse of dimensionality. Another approach is to use bandit algorithms from Lipschitz bandits (Slivkins 2019). For example, one may discretize the price space and apply upper confidence bound (UCB)-based algorithms. However, such approaches fail to balance the matching rates and arrival rates on both sides, making it difficult to control the queue lengths. These algorithms also have a high computational complexity because the number of arms is large. Approaches from bandit convex optimization (Lattimore 2024) aim to solve convex optimization problems with bandit feedback. However, the control variables in our setting are prices and the profit function is not concave in terms of prices. The constraint set representing a set of balanced arrival rates is also not convex in terms of prices.

To deal with this challenge, we propose to use a longest-queue-first matching algorithm and a learning-based pricing algorithm, which combines gradient-free (zero-order) stochastic projected gradient ascent (Agarwal et al. 2010) with bisection search. We also borrow the idea of fluid pricing policy from Varma et al. (2023) to control the queue length by rejecting arrivals according to a predetermined queue-length threshold. In this paper, we prove that our proposed algorithm yields a sublinear regret $\tilde{O}(T^{5/6})$ when compared with a fluid-based baseline and guarantees an anytime queue-length bound $\tilde{O}(T^{2/3})$, where T is the time horizon. Furthermore, we establish a tradeoff between the regret bound and the queue-length bound: For any $\gamma \in (0,2/3]$, if we keep the queue lengths of both customers and servers below $\tilde{\mathrm{\Theta }}(T^{\gamma })$, then we have a regret upper bound $\tilde{O}(T^{1-\gamma /4})$. We prove a hardness result: The regret is at least $\mathrm{\Omega }(T^{1-\gamma })$ to maintain the queue length below $T^{\gamma }$ for a single-link system with demand and supply functions from a specific class, even when the functions are known.

2. Model

We consider a discrete-time system with two-sided queues: a customer side and a server side. There are multiple queues on each side, representing different types of customers and different types of servers. We can also view customers as demand and servers as supply. We model the system by a bipartite graph $G(\mathcal{I}\cup \mathcal{J},\mathcal{E})$, where $\mathcal{I}=\{1,2,\dots ,I\}$ is the set of customer types and $\mathcal{J}=\{1,2,\dots ,J\}$ is the set of server types with $|\mathcal{I}|=I$ and $|\mathcal{J}|=J$. $\mathcal{E}$ is the set of all compatible links, which means that a type i customer can be served by a type j server if and only if $(i,j)\in \mathcal{E}$. Figure 1 is an example with three types of customers and two types of servers ($I=3,J=2$). At each time slot, there are arrivals of customers and servers. At time slot t, let $A_{\text{c},i}(t)$ and $A_{\text{s},j}(t)$ denote the number of arrivals of type i customers and type j servers, respectively. Assume that $A_{\text{c},i}(t)$ and $A_{\text{s},j}(t)$ follow independent Bernoulli distributions. Let ${\lambda }_i(t)≔\mathbb{E}[A_{\text{c},i}(t)]$ and ${\mu }_j(t)≔\mathbb{E}[A_{\text{s},j}(t)]$. At each time slot, after the arrival of customers and servers, the platform will match the customers and servers in the queues through compatible links. Once a customer is matched with a server, that is, the customer is served by the server, they will leave the system immediately. Let $Q_{\text{c},i}(t)$ and $Q_{\text{s},j}(t)$ denote the queue length of type i customers and that of type j servers, respectively, before arrivals and matching at time slot t. Assume the queues are all empty at $t=1$.

There is also a price attached to each type of customer or server. Let $p_{\text{c},i}(t)$ denote the price of the type i customer and $p_{\text{s},j}(t)$ denote the price of the type j server at time slot t. At time slot t, when a customer of type i arrives, they will be charged $p_{\text{c},i}(t)$ units of money by the platform. When a server of type j arrives, they will be paid $p_{\text{s},j}(t)$ units of money by the platform. Note that the prices determine the arrival rates. Increasing the price of type i customers will reduce arrival rate ${\lambda }_i(t)$; increasing the price of type j servers will increase arrival rate ${\mu }_j(t)$. For a type i customer, the demand function is denoted by $F_i:[0,1]\to [p_{\text{c},i,\min },p_{\text{c},i,\max }]$, where the input is an arrival rate ${\lambda }_i\in [0,1]$, the output is the price $p_{\text{c},i}\in [p_{\text{c},i,\min },p_{\text{c},i,\max }]$ corresponding to this arrival rate, and $p_{\text{c},i,\min }$ and $p_{\text{c},i,\max }$ are the minimum and maximum prices for type i customer, respectively. Similarly, for type j server, the supply function is denoted by $G_j:[0,1]\to [p_{\text{s},j,\min },p_{\text{s},j,\max }]$, where the input is an arrival rate ${\mu }_j\in [0,1]$, the output is the price $p_{\text{s},j}\in [p_{\text{s},j,\min },p_{\text{s},j,\max }]$ corresponding to this arrival rate, and $p_{\text{s},j,\min }$ and $p_{\text{s},j,\max }$ are the minimum and maximum prices for a type j server, respectively. Then we have $p_{\text{c},i}(t)=F_i({\lambda }_i(t))$ and $p_{\text{s},j}(t)=G_j({\mu }_j(t))$. We make the following assumption on the demand and supply functions $F_i$ and $G_j$.

Assumption 1.

For any customer type i, $F_i$ is strictly decreasing, bijective, and $L_{F_i}$-Lipschitz. Let $F_i^{-1}$ denote the inverse function of $F_i$. Assume that $F_i^{-1}$ is $L_{F_i^{-1}}$-Lipschitz. For any server type j, $G_j$ is strictly increasing, bijective, and $L_{G_j}$-Lipschitz. Let $G_j^{-1}$ denote the inverse function of $G_j$. Assume that $G_j^{-1}$ is $L_{G_j^{-1}}$-Lipschitz.

From Assumption 1, we know $F_i(1)=p_{\text{c},i,\min },F_i(0)=p_{\text{c},i,\max }$ for any customer type i and $G_j(0)=p_{\text{s},j,\min },G_j(1)=p_{\text{s},j,\max }$ for any server type j.

The sequence of events occurring in each time slot is shown in Figure 2. At the beginning of time slot t, we first observe the lengths of all queues $Q_{\text{c},i}(t),Q_{\text{s},j}(t)$ for all i, j. Then the platform runs a pricing algorithm to decide the prices $p_{\text{c},i}(t),p_{\text{s},j}(t),\forall i,j$. The arrival rates ${\lambda }_i\left(t\right),{\mu }_j\left(t\right),\forall i,j$ will be determined by these prices, and then the actual arrivals $A_{\text{c},i}\left(t\right),A_{\text{s},j}\left(t\right),\forall i,j$ occur. Next, the platform runs a matching algorithm and then those matched customers and servers leave the system.

At time slot t, the platform makes a profit of

Our goal is to design an online pricing and matching algorithms to maximize the profit of the platform over T time slots without knowing the demand and supply functions while keeping queue lengths of both customers and servers below a predetermined threshold, that is, to maximize

while keepingbelow a predetermined threshold. To quantify the performance of the online algorithm, we compare it with the following optimal solution to a fluid-based optimization problem (Varma et al. 2023):where $\mathit{x}≔{(x_{i,j})}_{(i,j)\in \mathcal{E}}$, $\mathit{\lambda }≔{({\lambda }_i)}_{i\in \mathcal{I}}$, and $\mathit{\mu }≔{({\mu }_j)}_{j\in \mathcal{J}}$. Similar to Varma et al. (2023), we make the following assumption.

Assumption 2.

For any customer type i, the revenue function $r_i({\lambda }_i)≔{\lambda }_i{F}_i({\lambda }_i)$ is concave. For any server type j, the cost function $c_j({\mu }_j)≔{\mu }_j{G}_j({\mu }_j)$ is convex.

From Assumption 2, Objective (2) is concave. Note that the constraints are all affine. Hence, the baseline optimization problem (2)–(6) is concave, and there exists a solution that achieves the optimal value, denoted as $({\mathit{\lambda }}^{*},{\mathit{\mu }}^{*},{\mathit{x}}^{*})$.

Let ${\lambda }_i(t)$ and ${\mu }_j(t)$ be the arrival rates at time t under any policy. Then from (1), the expected profit under the policy is

Let $f^{*}$ denote the optimal value of the fluid optimization problem (2)–(6). For the profit maximization, we consider the following expected regret with respect to the fluid baseline:

where $({\mathit{\lambda }}^{*},{\mathit{\mu }}^{*})$ is an optimal solution to the fluid optimization problem. The following lemma establishes the connection between the optimal expected profit and $f^{*}$ over T time slots.

Lemma 1.

Let Assumption 1 and Assumption 2 hold. Then under any policy, we have

$$\begin{array}{l}{\displaystyle \sum _{t=1}^T\mathbb{E}}\left[{\displaystyle \sum _i{\lambda }_i}(t)F_i({\lambda }_i(t))-{\displaystyle \sum _j{\mu }_j}(t)G_j({\mu }_j(t))\right]-T{f}^{*}\hfill \\ \le {\displaystyle \sum _i(L_{F_i}+p_{\text{c},i,\max })}\mathbb{E}[Q_{\text{c},i}(T+1)]+{\displaystyle \sum _j(L_{G_j}+p_{\text{s},j,\max })}\mathbb{E}[Q_{\text{s},j}(T+1)].\hfill \end{array}$$

The proof of this lemma can be found in Appendix A. Lemma 1 means that the fluid baseline approximates the optimal profit, with an error at most proportional to the queue length at time T. This justifies the use of the regret definition (7). Specifically, let $\mathbb{E}[R^{\text{opt}}(T)]$ denote the expected regret with respect to the policy that maximizes the expected profit. Then Lemma 1 implies that

As long as the queue lengths $\mathbb{E}[Q_{\text{c},i}(T+1)]$ and $\mathbb{E}[Q_{\text{s},j}(T+1)]$ are orderwise smaller than $\mathbb{E}[R(T)]$, the regret defined in (7) approximates the “true” regret (with respect to the optimal expected profit). We consider policies that make the queue mean rate stable (Neely 2022); that is, under the policy, for all i, j,

Under any mean rate stable policy, using Lemma 1 and taking limit $T\to +\infty$, we obtain

which means that the optimal value of the fluid optimization problem is an upper bound on the asymptotic time-averaged expected profit under any mean rate stable policy. This further justifies the use of the fluid optimal value as a baseline to define regret.

We make another assumption on the problem.

Assumption 3.

There exists a known positive number $a_{\min }\in (0,1)$ such that there exists an optimal solution ${\mathit{\lambda }}^{*},{\mathit{\mu }}^{*}$ to the fluid optimization problem that satisfies ${\lambda }_i^{*}\ge a_{\min }$ and ${\mu }_j^{*}\ge a_{\min }$ for all i and j.

Assumption 3 means that we need the optimal arrival rates to be strictly greater than zero. This assumption is not restrictive, because any queue with an optimal arrival rate of zero, indicating it is redundant, can be easily identified in practice and removed from the problem formulation. Note that $a_{\min }>0$ can be any lower bound on the optimal arrival rates.

Assume that the functions $F_i$ and $G_j$ are unknown. The platform cannot directly control the arrival rates, but they can control the prices of the customers and the servers and the matching algorithm. The platform can also observe the number of arrivals and the queue lengths of all the queues. At each time slot, the platform needs to design a price for each queue (customer or server) and to make a decision on how the customers and servers are matched. The objective is to minimize the regret $\mathbb{E}[R(T)]$ while keeping the maximum queue length ${\max }_{t=1,\dots ,T}\max \{{\max }_i{Q}_{\text{c},i}(t),{\max }_j{Q}_{\text{s},j}(t)\}$ below a predetermined threshold. This anytime queue length constraint is necessary in certain practical scenarios—for instance, when the system has a finite buffer size for each queue. Moreover, customers’ experience is often affected by the anytime queue length because they typically expect a consistent level of service.

2.1. Notation

We use bold symbols to represent vectors in ${\mathbb{R}}^{|\mathcal{E}|}$ or ${\mathbb{R}}^I$ or ${\mathbb{R}}^J$, such as $\mathit{x},\mathit{\lambda },\mathit{\mu }$. We use subscript i or j to indicate an element of a vector, for example, ${\lambda }_i$ is the ith element of $\mathit{\lambda }$. Note that we view $\mathit{x}={(x_{i,j})}_{(i,j)\in \mathcal{E}}$ as a vector in ${\mathbb{R}}^{|\mathcal{E}|}$ rather than a matrix, and the order of elements in $\mathit{x}$ can be arbitrary as long as the order is fixed. We use subscript $\text{c}$ to indicate the customer side and $\text{s}$ for the server side. $g(T)=O(h(T))$ means that there exist positive constants C and $T_0$ such that $g(T)\le Ch(T)$ for all $T\ge T_0$; $g(T)=\mathrm{\Theta }(h(T))$ means that there exist positive constants $C_1$, $C_2$ and $T_0$ such that $C_{1}h(T)\le g(T)\le C_{2}h(T)$ for all $T\ge T_0$; and $g(T)=\mathrm{\Omega }(h(T))$ means that there exist positive constants C and $T_0$ such that $g(T)\ge Ch(T)$ for all $T\ge T_0$. We omit the base of logarithmic functions in $O(·)$, $\mathrm{\Theta }(·)$, and $\mathrm{\Omega }(·)$, for example, $\mathrm{\Theta }(\log (T))$, because the base does not affect the order. We use ${\log }^2(·)$ to denote ${(\log (·))}^2$. We use $\tilde{O}(·)$, $\tilde{\mathrm{\Theta }}(·)$, and $\tilde{\mathrm{\Omega }}(·)$ to suppress $\text{polylog}(T)$ factors.

3. Summary of Our Main Results

In this section, we provide an overview of the main results in this paper. We use a longest-queue-first matching algorithm, which is a discrete-time version of the matching algorithm in Varma et al. (2023). We propose a learning-based pricing algorithm, which combines gradient-free (zero-order) stochastic projected gradient ascent (Agarwal et al. 2010) with bisection search, illustrated in Section 4 in detail. The proposed pricing algorithm learns from samples and make pricing decisions simultaneously. Under the proposed matching and pricing algorithms, we establish the following profit-regret bound and queue-length bound:

By changing the parameters of the proposed pricing algorithm, we can achieve the following tradeoff between regret and queue length: For any $\gamma \in [0,2/3]$, there exists a set of parameters such that the algorithm can achieve:

The above results are shown in Figure 3. As the allowable queue length increases, the regret bound that we can achieve becomes better. However, if we allow the queue length to increase over $\tilde{\mathrm{\Theta }}(T^{2/3})$, the regret bound cannot be further improved and remains $\tilde{O}(T^{5/6})$.

3.1. Hardness Result

We show in the following lemma that in a single-link system, any policy that keeps the anytime queue length bounded by $T^{\gamma }$ must incur a regret of at least $\mathrm{\Omega }(T^{1-\gamma })$.

Lemma 2.

Consider a single-link system with one customer queue and one server queue with demand function $F(·)$ and supply function $G(·)$. Let $Q_{\text{c}}(t)$ and $Q_{\text{s}}(t)$ denote the customer-side queue length and server-side queue length, respectively. Consider the matching policy that matches all pairs whenever possible because there is no incentive to delay any match in a single-link system. There exists a class of problem instances that satisfies Assumption 1, Assumption 2, and Assumption 3, such that for any pricing policy satisfying ${\max }_{t=1,\dots ,T}\max \{Q_{\text{c}}(t),Q_{\text{s}}(t)\}\le T^{\gamma },$ the expected regret satisfies $\mathbb{E}[R(T)]=\mathrm{\Omega }(T^{1-\gamma })$ for any $\gamma \in [0,1/2)$.

The definition of the class of problem instances and the proof of Lemma 2 can be found in Appendix B. Our upper bound results under the proposed algorithm also hold for this problem class. Note that when the queue length threshold is a constant (i.e., $\gamma =0$), the regret under our algorithm becomes linear, which is unavoidable by Lemma 2.

4. Algorithm

In this section, we present the proposed matching and pricing algorithms in detail. The matching algorithm is to match the customers on the demand-side queues with the servers on the supply-side queues, and the pricing algorithm is to learn and design the prices without knowing the demand and supply functions.

4.1. Matching Algorithm

We use a longest-queue-first matching algorithm as shown in Algorithm 1 and Figure 4, where we present the matching algorithm for one time slot, and it is the same for all time slots. In the algorithm, for each time slot, we iterate over each queue on both the customer and server sides. For each queue, we check whether there is a new arrival in the queue. If there is a new arrival (a customer or a server), the algorithm will match the arrival with one server (or customer) in the longest compatible queue on the other side, as shown in Figure 4. After matching, we decrease the queue length by one for both matched queues. Then we move on to the next queue and repeat the process.

Algorithm 1

(Matching Algorithm)

• 1 At each time slot t, without loss of generality, assume that the arrivals come in order $A_{\text{c},1}(t),A_{\text{c},2}(t),\dots ,A_{\text{c},I}(t),A_{\text{s},1}(t),A_{\text{s},2}(t),\dots ,A_{\text{s},J}(t)$.

• 2 Initialize: ${\tilde{Q}}_{\text{c},i}\leftarrow Q_{\text{c},i}(t)$ for all i and ${\tilde{Q}}_{\text{s},j}\leftarrow Q_{\text{s},j}(t)$ for all j.

• 3 for $i=1$ to I do

• 4  Observe $A_{\text{c},i}(t)$ and update ${\tilde{Q}}_{\text{c},i}\leftarrow {\tilde{Q}}_{\text{c},i}+A_{\text{c},i}(t)$;

• 5  Let $j_i^{*}(t)\in \text{arg}\hspace{0.17em}{\text{max}}_{j:(i,j)\in \mathcal{E}}{\tilde{Q}}_{\text{s},j}$ with ties broken arbitrarily;

• 6  if $A_{\text{c},i}(t)=1$ and ${\sum }_{j:(i,j)\in \mathcal{E}}{\tilde{Q}}_{\text{s},j}>0$ then

• 7   Match the arrival $A_{\text{c},i}(t)$ with a server in queue $j_i^{*}(t)$;

• 8   Then update ${\tilde{Q}}_{\text{c},i}\leftarrow {\tilde{Q}}_{\text{c},i}-1$ and ${\tilde{Q}}_{\text{s},j_i^{*}(t)}\leftarrow {\tilde{Q}}_{\text{s},j_i^{*}(t)}-1$;

• 9 for $j=1$ to J do

• 10  Observe $A_{\text{s},j}(t)$ and update ${\tilde{Q}}_{\text{s},j}\leftarrow {\tilde{Q}}_{\text{s},j}+A_{\text{s},j}(t)$;

• 11  Let $i_j^{*}(t)=\text{arg}\hspace{0.17em}{\text{max}}_{i:(i,j)\in \mathcal{E}}{\tilde{Q}}_{\text{c},i}$ with ties broken arbitrarily;

• 12  if $A_{\text{s},j}(t)=1$ and ${\sum }_{i:(i,j)\in \mathcal{E}}{\tilde{Q}}_{\text{c},i}>0$ then

• 13   Match the arrival $A_{\text{s},j}(t)$ with a customer in queue $i_j^{*}(t)$;

• 14   Then update ${\tilde{Q}}_{\text{s},j}\leftarrow {\tilde{Q}}_{\text{s},j}-1$ and ${\tilde{Q}}_{\text{c},i_j^{*}(t)}\leftarrow {\tilde{Q}}_{\text{c},i_j^{*}(t)}-1$;

4.2. Pricing Algorithm

Because the functions $F_i,G_j$ are unknown and the arrival rates cannot be directly controlled, we cannot simply solve the optimization problem (2)–(6) and obtain the prices. In this section, we propose to combine the techniques of gradient-free (zero-order) stochastic projected gradient descent (Agarwal et al. 2010) and bisection search to solve the problem.

Before presenting the details of our pricing algorithm, we begin by providing a simple example to understand the idea of our algorithm. We consider two customer queues, which are connected to one server queue. Let $x_1,x_2$ denote the arrival rates of customer queue 1 and customer queue 2, respectively. Then the arrival rate of the server queue should be equal to $x_1+x_2$ due to the balance constraints (3) and (4). Let $\mathit{x}(k)≔(x_1(k),x_2(k))$, where k denote the iteration. Suppose the demand and supply functions are known and the gradients $\mathit{g}(k)$ are known; that is, we have first-order access to the profit function f. In this case, we can use the gradient ascent algorithm to solve the problem, as shown in Figure 5(a), where $\eta$ is the step size. Suppose the demand and supply functions are known but the gradients are unknown; that is, we only have zero-order access to the profit function f. Then we can use the two-point zero-order method (Agarwal et al. 2010) to solve the problem, as shown in Figure 5(b). In the two point method, in each iteration k, we first sample a uniformly random direction $\mathit{u}(k)$ ($\mathit{u}(k)$ is a unit vector) and then calculate the profits using two points, $\mathit{x}(k)+\delta \mathit{u}(k)$ and $\mathit{x}(k)-\delta \mathit{u}(k)$, where $\delta$ is small number. Then we can estimate the gradient and update $\mathit{x}(k)$ using the formula in Figure 5(b). However, if the demand and supply functions and the gradients are all unknown, simply using the two-point method does not work because we even do not have zero-order access to the profit function f. As shown in Figure 5(c), for $\mathit{x}=\mathit{x}(k)+\delta \mathit{u}(k)$ or $\mathit{x}=\mathit{x}(k)-\delta \mathit{u}(k)$, to estimate the profit $f(\mathit{x})$, we need to estimate the prices of all queues $F_1(x_1),F_2(x_2),G_1(x_1+x_2)$ because $f(\mathit{x})=x_1{F}_1(x_1)+x_2{F}_2(x_2)-(x_1+x_2)G_1(x_1+x_2)$, where $x_1+x_2$ is the arrival rate of the server queue. Take $F_1(x_1)$ as an example. Estimating $F_1(x_1)$ is equivalent to finding the solution to the equation $x_1=F_1^{-1}(p)$ given $x_1$. We propose using bisection search on prices to estimate p such that $x_1=F_1^{-1}(p)$, as shown in Figure 5(c), where the horizontal axis is price p, the vertical axis is arrival rate x of the queue, and the green dashed curve is the inverse demand function $x=F_1^{-1}(p)$. We first have the initial knowledge that the price $F_1(x_1)$ will be between some lower bound and some upper bound, which forms our first search interval. Then we set the price of the queue to be the midpoint of the search interval and run the system for multiple time slots to calculate average number of arrivals per time slot. This is how we get an estimated value of $F_1^{-1}(p)$ for a chosen p. Then we determine the next search interval by comparing it with $x_1$, as shown in Figure 5(c). The bisection search stops when the accuracy is good enough. Note that during the process of running the system, we reject arrivals if the queue length is larger than or equal to a predetermined threshold, to control the queue length. After the bisection search, we obtain estimates of the profits $f(\mathit{x}(k)+\delta \mathit{u}(k))$ and $f(\mathit{x}(k)-\delta \mathit{u}(k))$. Then we can substitute these estimates into the two-point method in Figure 5(b) to get an estimate of the gradient and then update the arrival rate $\mathit{x}(k)$.

Now we present the details of the pricing algorithm in the general case. The structure of our pricing algorithm is shown in Figure 6. Before presenting the algorithm, we first define some notations and a shrunk feasible set. Let ${\mathcal{E}}_{\text{c},i}≔\{j|(i,j)\in \mathcal{E}\}$ and ${\mathcal{E}}_{\text{s},j}≔\{i|(i,j)\in \mathcal{E}\}$ denote the sets of all queues that are connected to customer queue i and server queue j, respectively. By substituting ${\lambda }_i,{\mu }_j$ and by Assumption 3, the optimization problem (2)–(6) can be equivalently rewritten as

Note that we view $\mathit{x}≔{(x_{i,j})}_{(i,j)\in \mathcal{E}}$ as a vector in ${\mathbb{R}}^{|\mathcal{E}|}$. Note that the problem (8)–(11) is also concave. Let $\mathcal{D}\subseteq {\mathbb{R}}^{|\mathcal{E}|}$ denote the feasible set of the problem (8)–(11), that is,

Let $N_{i,j}≔\max \{|{\mathcal{E}}_{\text{c},i}|,|{\mathcal{E}}_{\text{s},j}|\}$ denote the maximum cardinality of the sets ${\mathcal{E}}_{\text{c},i}$ and ${\mathcal{E}}_{\text{s},j}$. Define a shrunk set of $\mathcal{D}$ with a parameter $\delta$ as follows:

whereand $\delta \in (0,r)$. With the definition of ${\mathcal{D}}^{\prime }$, we can show (Lemma 4 in the Online Appendix) that $\mathit{x}+\delta \mathit{u}\in \mathcal{D}$ for any $\mathit{x}\in {\mathcal{D}}^{\prime }$ and any vector $\mathit{u}$ in the unit ball. To ensure that the definition of ${\mathcal{D}}^{\prime }$ is valid, we need the following assumption.

Assumption 4.

Assume that ${\sum }_{j\in {\mathcal{E}}_{\text{c},i}}\frac{a_{\min }+1}{2N_{i,j}}-a_{\min }>0$ for all i and ${\sum }_{i\in {\mathcal{E}}_{\text{s},j}}\frac{a_{\min }+1}{2N_{i,j}}-a_{\min }>0$ for all j.

As long as $a_{\min }$ is small enough, Assumption 4 holds. Because $N_{i,j}\ge |{\mathcal{E}}_{\text{c},i}|$ and $a_{\min }<1$, we have

for all i. Also, by Assumption 4, ${\sum }_{j\in {\mathcal{E}}_{\text{c},i}}(a_{\min }+1)/\left(2N_{i,j}\right)-a_{\min }>0$ for all i. Similarly, we have $1-{\sum }_{i\in {\mathcal{E}}_{\text{s},j}}(a_{\min }+1)/\left(2N_{i,j}\right)>0$ and ${\sum }_{i\in {\mathcal{E}}_{\text{s},j}}(a_{\min }+1)/\left(2N_{i,j}\right)-a_{\min }>0$ for all j. Hence, $r>0$ and the definition of ${\mathcal{D}}^{\prime }$ is valid. Let ${\mathit{x}}_{\text{ctr}}≔{\left(\right(a_{\min }+1)/(2N_{i,j}\left)\right)}_{(i,j)\in \mathcal{E}}$. We can see that ${\mathit{x}}_{\text{ctr}}\in {\mathcal{D}}^{\prime }$, which can be used as the initial point for the pricing algorithm; ${\mathit{x}}_{\text{ctr}}$ can be thought of as the “center” of the set ${\mathcal{D}}^{\prime }$.

Algorithm 2

(Pricing Algorithm)

• 1 Initialize: Choose an exploration parameter $\delta \in (0,r)$. Choose a step size $\eta \in (0,1)$. Choose an accuracy parameter $ϵ\in (0,1/e)$. Choose a queue length threshold $q^{\text{th}}$. Choose $\mathit{x}(1)={\mathit{x}}_{\text{ctr}}\in {\mathcal{D}}^{\prime }$ as the initial point. Define $e_{\text{c},i}$ and $e_{\text{s},j}$ according to (C.1) and (C.2). Define $N≔\lceil \beta \ln (1/ϵ)/{ϵ}^2\rceil$ and $M≔\lceil {\log }_2(1/ϵ)\rceil$, where $\beta >0$ is a constant.

• 2 Time step counter $t\leftarrow 1$;

• 3 Outer iteration counter $k\leftarrow 1$;

• 4 repeat

    // Step 1. generate a random direction and two points

• 5  Choose a unit vector $\mathit{u}(k)\in {\mathbb{R}}^{|\mathcal{E}|}$ uniformly at random, that is, $\Vert \mathit{u}(k){\Vert }_2=1$;

• 6  Let $x_{i,j}^{+}(k)≔{(\mathit{x}(k)+\delta \mathit{u}(k))}_{i,j}$ and $x_{i,j}^{-}(k)≔{(\mathit{x}(k)-\delta \mathit{u}(k))}_{i,j}$;

• 7  Let ${\lambda }_i^{+}(k)≔{\sum }_{j\in {\mathcal{E}}_{\text{c},i}}{x}_{i,j}^{+}(k)$, ${\lambda }_i^{-}(k)≔{\sum }_{j\in {\mathcal{E}}_{\text{c},i}}{x}_{i,j}^{-}(k)$, ${\mu }_j^{+}(k)≔{\sum }_{i\in {\mathcal{E}}_{\text{s},j}}{x}_{i,j}^{+}(k)$, ${\mu }_j^{-}(k)≔{\sum }_{i\in {\mathcal{E}}_{\text{s},j}}{x}_{i,j}^{-}(k)$;

• 8  Let ${\mathit{\lambda }}^{+}(k)$ be a vector of ${\lambda }_i^{+}(k),i=1\dots ,I$. Define similarly ${\mathit{\lambda }}^{-}(k)$, ${\mathit{\mu }}^{+}(k)$, and ${\mathit{\mu }}^{-}(k)$.

    // Step 2. bisection search to approximate $F_i({\lambda }_i^{+}(k)),F_i({\lambda }_i^{-}(k)),G_j({\mu }_j^{+}(k)),G_j({\mu }_j^{-}(k))$.

• 9  if $k=1$ then

• 10   For all i, let ${\underset{¯}{p}}_{\text{c},i}^{+}(k,1)=p_{\text{c},i,\min }$, ${\overline{p}}_{\text{c},i}^{+}(k,1)=p_{\text{c},i,\max }$;

• 11   For all j, let ${\underset{¯}{p}}_{\text{s},j}^{+}(k,1)=p_{\text{s},j,\min }$, ${\overline{p}}_{\text{s},j}^{+}(k,1)=p_{\text{s},j,\max }$;

• 12   Let ${\tilde{q}}^{\text{th}}=+\infty$; // We do not reject arrivals for $k=1$.

• 13  else

• 14   For all i, let ${\underset{¯}{p}}_{\text{c},i}^{+}(k,1)=p_{\text{c},i}^{+}(k-1,M)-e_{\text{c},i}$, ${\overline{p}}_{\text{c},i}^{+}(k,1)=p_{\text{c},i}^{+}(k-1,M)+e_{\text{c},i}$;

• 15   For all j, let ${\underset{¯}{p}}_{\text{s},j}^{+}(k,1)=p_{\text{s},j}^{+}(k-1,M)-e_{\text{s},j}$, ${\overline{p}}_{\text{s},j}^{+}(k,1)=p_{\text{s},j}^{+}(k-1,M)+e_{\text{s},j}$;

• 16   Let ${\tilde{q}}^{\text{th}}=q^{\text{th}}$;

• 17  Let ${\underset{¯}{\mathit{p}}}_{\text{c}}^{+}(k,1)$ be a vector of ${\underset{¯}{p}}_{\text{c},i}^{+}(k,1),i=1\dots ,I$. Define similarly ${\overline{\mathit{p}}}_{\text{c}}^{+}(k,1)$, ${\underset{¯}{\mathit{p}}}_{\text{s}}^{+}(k,1)$, ${\overline{\mathit{p}}}_{\text{s}}^{+}(k,1)$.

• 18  t, ${\mathit{p}}_{\text{c}}^{+}(k,M)$, ${\mathit{p}}_{\text{s}}^{+}(k,M)=$ Bisection $\left({\mathit{\lambda }}^{+}\left(k\right),{\mathit{\mu }}^{+}\left(k\right),{\underset{¯}{\mathit{p}}}_{\text{c}}^{+}(k,1),{\overline{\mathit{p}}}_{\text{c}}^{+}(k,1),{\underset{¯}{\mathit{p}}}_{\text{s}}^{+}(k,1),{\overline{\mathit{p}}}_{\text{s}}^{+}(k,1),{\tilde{q}}^{\text{th}},t,M,N,ϵ\right)$;

• 19  Do Line 9–18 for ${\mathit{\lambda }}^{-}(k),{\mathit{\mu }}^{-}(k)$. Denote the counterparts of the prices by ${\underset{¯}{\mathit{p}}}_{\text{c}}^{-}(k,1)$, ${\overline{\mathit{p}}}_{\text{c}}^{-}(k,1)$, ${\mathit{p}}_{\text{c}}^{-}(k,M)$, ${\underset{¯}{\mathit{p}}}_{\text{s}}^{-}(k,1)$, ${\overline{\mathit{p}}}_{\text{s}}^{-}(k,1)$, ${\mathit{p}}_{\text{s}}^{-}(k,M)$.

  // Step 3. gradient calculation

• 20  Let $\widehat{\mathit{g}}(k)=\frac{|\mathcal{E}|}{2\delta }[\left({\sum }_{i=1}^I{\lambda }_i^{+}(k)p_{\text{c},i}^{+}(k,M)-{\sum }_{j=1}^J{\mu }_j^{+}(k)p_{\text{s},j}^{+}(k,M)\right)$ $-\left({\sum }_{i=1}^I{\lambda }_i^{-}(k)p_{\text{c},i}^{-}(k,M)-{\sum }_{j=1}^J{\mu }_j^{-}(k)p_{\text{s},j}^{-}(k,M)\right)]\mathit{u}(k)$;

    // Step 4. gradient ascent update

• 21  Projected Gradient Ascent: $\mathit{x}(k+1)={\mathrm{\Pi }}_{{\mathcal{D}}^{\prime }}(\mathit{x}(k)+\eta \widehat{\mathit{g}}(k))$;

• 22  $k\leftarrow k+1$;

• 23 until $t>T$;

The details of the proposed pricing algorithm are shown in Algorithm 2 and Algorithm 3. In the notation in Algorithms 2 and 3, $(k)$ denotes the kth outer iteration; $(k,m)$ denotes the mth bisection iteration in the kth outer iteration. As shown in Algorithm 2, we first choose $\delta ,\eta ,ϵ$, and $q^{\text{th}}$; $\delta \in (0,r)$ is an exploration parameter for estimating the gradient, and it is used to construct the set ${\mathcal{D}}^{\prime }$. We choose $\mathit{x}(1)={\mathit{x}}_{\text{ctr}}\in {\mathcal{D}}^{\prime }$ as the initial point of the algorithm; $\eta \in (0,1)$ is the step size for the gradient ascent step; and $ϵ\in (0,1/e)$ is the accuracy for the bisection algorithm. The threshold $q^{\text{th}}>0$ is used to control queue length. We also define $e_{\text{c},i}$ and $e_{\text{s},j}$, which can be later proved to be the upper bounds of the change of the prices in one outer iteration. Note that the parameters $\delta ,\eta ,ϵ,q^{\text{th}}$ can be a function of total number of time steps T and can be optimized later to obtain a sublinear regret. In each outer iteration k, we have four steps.

• Step 1: We first generate a random direction, that is, a unit vector $\mathit{u}(k)\in {\mathbb{R}}^{|\mathcal{E}|}$ that is uniformly sampled from the unit sphere, and then change $\mathit{x}(k)$ in the direction of $\mathit{u}(k)$ and also in the opposite direction of $\mathit{u}(k)$, generating $x_{i,j}^{+}(k)$ and $x_{i,j}^{-}(k)$, as shown in Line 6 of Algorithm 2. We can then calculate the arrival rates ${\lambda }_i^{+}(k),{\mu }_j^{+}(k)$ and ${\lambda }_i^{-}(k),{\mu }_j^{-}(k)$ as shown in Line 7 of Algorithm 2.

• Step 2: Next, we find the prices that approximate $F_i({\lambda }_i^{+}(k)),G_j({\mu }_j^{+}(k))$, and $F_i({\lambda }_i^{-}(k)),G_j({\mu }_j^{-}(k))$ using the bisection search shown in Algorithm 3, which will be illustrated in detail later in this section. Here, we specify the initial search intervals for the bisection search. If $k=1$, we start with search intervals $[p_{\text{c},i,\min },p_{\text{c},i,\max }]$ and $[p_{\text{s},j,\min },p_{\text{s},j,\max }]$, as shown in Lines 10 and 11 of Algorithm 2. Note that we do not reject arrivals in the first iteration because we want to quickly learn the price that can keep the queues balanced. If $k>1$, we use $p_{\text{c},i}^{+}(k-1,M_{k-1}^{+})$, $p_{\text{s},j}^{+}(k-1,M_{k-1}^{+}),p_{\text{c},i}^{-}(k-1,M_{k-1}^{-})$, and $p_{\text{s},j}^{-}(k-1,M_{k-1}^{-}),e_{\text{c},i},e_{\text{s},j}$ to construct the lower and upper bounds for the bisection algorithm, as shown in Lines 14 and 15 of Algorithm 2, where $e_{\text{c},i}=\mathrm{\Theta }(\eta ϵ/\delta +\eta +\delta +ϵ)$ and $e_{\text{s},j}=\mathrm{\Theta }(\eta ϵ/\delta +\eta +\delta +ϵ)$, and the exact expressions can be found in Appendix C.

• Step 3: The bisection algorithm will output approximated prices ${\mathit{p}}_{\text{c}}^{+}(k,M_k^{+})$, ${\mathit{p}}_{\text{s}}^{+}(k,M_k^{+})$, ${\mathit{p}}_{\text{c}}^{-}(k,M_k^{+})$, and ${\mathit{p}}_{\text{s}}^{-}(k,M_k^{+})$ that correspond to ${\mathit{\lambda }}^{+}(k),\hspace{0.17em}\hspace{0.17em}{\mathit{\mu }}^{+}(k),\hspace{0.17em}\hspace{0.17em}{\mathit{\lambda }}^{-}(k),\hspace{0.17em}\hspace{0.17em}\text{and}\hspace{0.17em}{\mathit{\mu }}^{-}(k)$, respectively, as shown in Lines 18 and 19 of Algorithm 2. Then we can use these arrival rates and prices to calculate an estimate $\widehat{\mathit{g}}(k)$ of the gradient of the objective function $f(\mathit{x})$ in (8), as shown in Line 20 of Algorithm 2.

• Step 4: With this gradient estimate, we do a projected gradient ascent as shown in Line 21 of Algorithm 2. The algorithm stops until the number of time steps $t\ge T$.

Algorithm 3

(Bisection $\left({\mathit{\lambda }}^{+/-}\right(k),{\mathit{\mu }}^{+/-}(k),{\underset{¯}{\mathit{p}}}_{\text{c}}^{+/-}(k,1),{\overline{\mathit{p}}}_{\text{c}}^{+/-}(k,1),{\underset{¯}{\mathit{p}}}_{\text{s}}^{+/-}(k,1),{\overline{\mathit{p}}}_{\text{s}}^{+/-}(k,1),{\tilde{q}}^{\text{th}},t,M,N,ϵ)$)

• 1 for $m=1$ to M do

• 2  Let $p_{\text{c},i}^{+/-}(k,m)=\frac{1}{2}({\underset{¯}{p}}_{\text{c},i}^{+/-}(k,m)+{\overline{p}}_{\text{c},i}^{+/-}(k,m))$ for all i;

• 3  Let $p_{\text{s},j}^{+/-}(k,m)=\frac{1}{2}({\underset{¯}{p}}_{\text{s},j}^{+/-}(k,m)+{\overline{p}}_{\text{s},j}^{+/-}(k,m))$ for all j;

• 4  Let $n_{\text{c},i}(k,m)=0$ for all i and $n_{\text{s},j}(k,m)=0$ for all j;

• 5  repeat

• 6   for $i=1$ to I do

• 7    if $Q_{\text{c},i}\left(t\right)\ge {\tilde{q}}^{\text{th}}$ then set price $p_{\text{c},i,\max }$ for queue i;

• 8    else set price $p_{\text{c},i}^{+/-}(k,m)$ for queue i and $n_{\text{c},i}(k,m)\leftarrow n_{\text{c},i}(k,m)+1$;

• 9   for $j=1$ to J do

• 10    if $Q_{\text{s},j}\left(t\right)\ge {\tilde{q}}^{\text{th}}$ then set price $p_{\text{s},j,\min }$ for queue j;

• 11    else set price $p_{\text{s},j}^{+/-}(k,m)$ for queue j and $n_{\text{s},j}(k,m)\leftarrow n_{\text{s},j}(k,m)+1$;

• 12   Use the above set of prices to run one step of the system;

• 13   $t\leftarrow t+1$;

• 14   Terminate the algorithm when $t>T$;

• 15  until for all queues i, $n_{\text{c},i}(k,m)\ge N$, that is, the price $p_{\text{c},i}^{+/-}(k,m)$ is run for at least N times and for all queues j, $n_{\text{s},j}(k,m)\ge N$, that is, the price $p_{\text{s},j}^{+/-}(k,m)$ is run for at least N times;

• 16  Let $t_{\text{c},i}^{+/-}(k,m,n)$ denote the time slot when the price $p_{\text{c},i}^{+/-}(k,m)$ is run for the nth time for the customer-side queue i; let $t_{\text{s},j}^{+/-}(k,m,n)$ denote the time slot when the price $p_{\text{s},j}^{+/-}(k,m)$ is run for the $n^{\text{th}}$ time for the server-side queue j;

• 17  for $i=1$ to I do

• 18   Let ${\widehat{\lambda }}_i^{+/-}(k,m)=(1/N){\sum }_{n=1}^N{A}_{\text{c},i}\left(t_{\text{c},i}^{+/-}\right(k,m,n\left)\right)$; // sample average

• 19   if ${\widehat{\lambda }}_i^{+/-}(k,m)>{\lambda }_i^{+/-}(k)$ then ${\underset{¯}{p}}_{\text{c},i}^{+/-}(k,m+1)=p_{\text{c},i}^{+/-}(k,m), {\overline{p}}_{\text{c},i}^{+/-}(k,m+1)={\overline{p}}_{\text{c},i}^{+/-}(k,m)$;

• 20   else ${\underset{¯}{p}}_{\text{c},i}^{+/-}(k,m+1)={\underset{¯}{p}}_{\text{c},i}^{+/-}(k,m), {\overline{p}}_{\text{c},i}^{+/-}(k,m+1)=p_{\text{c},i}^{+/-}(k,m)$;

• 21  for $j=1$ to J do

• 22   Let ${\widehat{\mu }}_j^{+/-}(k,m)=(1/N){\sum }_{n=1}^N{A}_{\text{s},j}\left(t_{\text{s},j}^{+/-}\right(k,m,n\left)\right)$; // sample average

• 23   if ${\widehat{\mu }}_j^{+/-}(k,m)>{\mu }_j^{+/-}(k)$ then ${\underset{¯}{p}}_{\text{s},j}^{+/-}(k,m+1)={\underset{¯}{p}}_{\text{s},j}^{+/-}(k,m), {\overline{p}}_{\text{s},j}^{+/-}(k,m+1)=p_{\text{s},j}^{+/-}(k,m)$;

• 24   else ${\underset{¯}{p}}_{\text{s},j}^{+/-}(k,m+1)=p_{\text{s},j}^{+/-}(k,m), {\overline{p}}_{\text{s},j}^{+/-}(k,m+1)={\overline{p}}_{\text{s},j}^{+/-}(k,m)$;

• 25 Let ${\mathit{p}}_{\text{c}}^{+/-}(k,M)$ be a vector of $p_{\text{c},i}^{+/-}(k,M),i=1,\dots ,I$ and define similarly ${\mathit{p}}_{\text{s}}^{+/-}(k,M)$.

• 26 return t, ${\mathit{p}}_{\text{c}}^{+/-}(k,M)$, ${\mathit{p}}_{\text{s}}^{+/-}(k,M)$

The proposed bisection algorithm is shown in Algorithm 3, which is to find the prices ${\mathit{p}}_{\text{c}}^{+/-},{\mathit{p}}_{\text{s}}^{+/-}$ such that ${\lambda }_i^{+/-}(k)\approx F_i^{-1}(p_{\text{c},i}^{+/-})$ and ${\mu }_j^{+/-}(k)\approx G_j^{-1}(p_{\text{s},j}^{+/-})$ for some given target arrival rates ${\lambda }_i^{+/-}(k),{\mu }_j^{+/-}(k)$ with initial intervals $[{\underset{¯}{p}}_{\text{c},i}^{+/-}(k,1),{\overline{p}}_{{\text{c}}_i}^{+/-}(k,1)]$ and $[{\underset{¯}{p}}_{\text{s},j}^{+/-}(k,1),{\overline{p}}_{\text{s},j}^{+/-}(k,1)]$ for all i, j. In each bisection iteration m, we first calculate the midpoints of the intervals, $p_{\text{c},i}^{+/-}(k,m)$ and $p_{\text{s},j}^{+/-}(k,m)$ for all i, j just like the standard bisection search, as shown in Lines 2 and 3 of Algorithm 3. For each queue, if the queue length is less than ${\tilde{q}}^{\text{th}}$, we will set the price with $p_{\text{c},i}^{+/-}(k,m)$ or $p_{\text{s},j}^{+/-}(k,m)$ that was just calculated; otherwise, we will temporarily reject new arrivals into the queue to control the queue length by using the prices $p_{\text{c},i,\max }$ or $p_{\text{s},j,\min }$. We will use this set of prices to run the system for a number of time slots such that every price has at least N i.i.d. samples, as shown in Lines 4–15 of Algorithm 3. Next, with the samples we obtained, we can calculate an estimate of the arrival rate corresponding to the price we set for each queue, ${\widehat{\lambda }}_i^{+/-}(k,m)$ or ${\widehat{\mu }}_j^{+/-}(k,m)$, as shown in Lines 18 and 22 of Algorithm 3. Then we can update the lower and upper bounds of the searching intervals by comparing ${\widehat{\lambda }}_i^{+/-}(k,m)$, ${\widehat{\mu }}_j^{+/-}(k,m)$ with ${\lambda }_i^{+/-}(k,m)$, ${\mu }_j^{+/-}(k,m)$, as shown in Lines 19 and 20 and Lines 23 and 24 of Algorithm 3. We conduct $M=\lceil {\log }_2(1/ϵ)\rceil$ bisection iterations to obtain sufficiently high accuracy.

5. Main Result

The main result of the paper is shown in Theorem 1.

Theorem 1.

Let Assumptions 1–4 hold. Under Algorithm 1, Algorithm 2, and Algorithm 3, if $ϵ<\delta$, $2e_{\text{c},i}\le p_{\text{c},i,\max }-p_{\text{c},i,\min }$, and $2e_{\text{s},j}\le p_{\text{s},j,\max }-p_{\text{s},j,\min }$, we have

$$\begin{array}{l}\mathbb{E}\left[R\right(T\left)\right]=O(\frac{{\log }^4(1/ϵ)}{{ϵ}^4{q}^{\text{th}}}+\frac{T}{q^{\text{th}}}+T^2{ϵ}^{\frac{\beta }{2}+1}+T{ϵ}^{\frac{\beta }{2}-1}\log (1/ϵ)+\frac{T\max \{\frac{{\log }^2(1/ϵ)}{{ϵ}^2},q^{\text{th}}\}(\eta +\delta )}{q^{\text{th}}}+\frac{Tϵ}{\delta }+\frac{{\log }^2(1/ϵ)}{\eta {ϵ}^2}),\end{array}$$(15)

and the queue length

$$\underset{t=1,\dots ,T}{\max }\max \left\{\underset{i}{\max }{Q}_{\text{c},i}\right(t),\underset{j}{\max }{Q}_{\text{s},j}(t\left)\right\}\le \max \{2\lceil {\log }_2(1/ϵ)\rceil \lceil \frac{\beta \ln (1/ϵ)}{{ϵ}^2}\rceil ,q^{\text{th}}\}.$$(16)

Based on Theorem 1, we optimize the regret bound by setting the parameters $ϵ,\eta ,\delta ,q^{\text{th}}$ to be a function of T. Assume that $q^{\text{th}}$ and $\beta$ are large enough. Then we can first focus on minimizing the order of the following term:

If we ignore logarithmic order, the optimal solution is $ϵ=T^{-1/3}$, $\eta =\delta =T^{-1/6}$, and the optimal order of (17) is $\tilde{O}(T^{5/6})$. By setting $\beta =5$ and $q^{\text{th}}=\mathrm{\Theta }\left(T^{2/3}\right)$, we obtain $\mathbb{E}[R(T)]=\tilde{O}(T^{5/6})$. We summarize the above result as the following corollary.

Corollary 1.

Let Assumptions 1–4 hold. Under Algorithm 1, Algorithm 2, and Algorithm 3, with parameters $ϵ=T^{-1/3}$, $\eta =\delta =T^{-1/6}$, $q^{\text{th}}=T^{2/3}$, $\beta =5$, for sufficiently large T such that $\delta <r$, $ϵ<1/e$, $2e_{\text{c},i}\le p_{\text{c},i,\max }-p_{\text{c},i,\min }$, and $2e_{\text{s},j}\le p_{\text{s},j,\max }-p_{\text{s},j,\min }$, we can achieve a sublinear regret as

$$\mathbb{E}[R(T)]=\tilde{O}(T^{\frac{5}{6}}),$$

and the queue length

$$\underset{t=1,\dots ,T}{\max }\max \{\underset{i}{\max }{Q}_{\text{c},i}(t),\underset{j}{\max }{Q}_{\text{s},j}(t)\}=\tilde{O}(T^{\frac{2}{3}}).$$

From (15) and (16) in Theorem 1, we can see that there is a tradeoff between minimizing the regret and minimizing the queue length. Firstly, we should not set $q^{\text{th}}$ to be greater than the order of $T^{2/3}$ because it will not benefit the regret bound orderwisely because $q^{\text{th}}=T^{2/3}$ is large enough to achieve the optimal order of (17). However, we can reduce $q^{\text{th}}$ so that the queue-length bound can be improved, although we may suffer a larger regret. Suppose we want the queue-length bound to be the order of $\tilde{O}(T^{\gamma })$, where $\gamma <2/3$. Then we need to set $q^{\text{th}}=\tilde{\mathrm{\Theta }}\left(T^{\gamma }\right)$ and $ϵ\ge \tilde{\mathrm{\Theta }}(T^{-\gamma /2})$ by (16). From (15), we need to set the parameters $ϵ,\eta ,\delta ,\beta$ to optimize the regret bound. Assume $\beta$ is large enough. Then optimizing the regret bound is equivalent to minimizing the order of the following term (ignoring logarithmic terms):

The optimal solution is $ϵ=T^{-\gamma /2}$, $\eta =\delta =T^{-\gamma /4}$, and the optimal order of (18) is $T^{1-\gamma /4}$. By setting $\beta =4/\gamma -1$, we obtain $\mathbb{E}[R(T)]=\tilde{O}(T^{1-\gamma /4})$. We summarize the above tradeoff as the following corollary.

Corollary 2.

Let Assumptions 1–4 hold. For any $\gamma \in (0,\frac{2}{3}]$, under Algorithm 1, Algorithm 2, and Algorithm 3, with parameters $ϵ=T^{-\gamma /2}$, $\eta =\delta =T^{-\gamma /4}$, $q^{\text{th}}=T^{\gamma }$, $\beta =4/\gamma -1$, for sufficiently large T such that $\delta <r$, $ϵ<1/e$, $2e_{\text{c},i}\le p_{\text{c},i,\max }-p_{\text{c},i,\min }$, and $2e_{\text{s},j}\le p_{\text{s},j,\max }-p_{\text{s},j,\min }$, we can achieve a sublinear regret as

$$\mathbb{E}[R(T)]=\tilde{O}(T^{1-\gamma /4}),$$

and the queue length

$$\underset{t=1,\dots ,T}{\max }\max \{\underset{i}{\max }{Q}_{\text{c},i}(t),\underset{j}{\max }{Q}_{\text{s},j}(t)\}=\tilde{O}(T^{\gamma }).$$

From Corollary 1 and Corollary 2, when the allowable queue length increases (up to $\tilde{\mathrm{\Theta }}(T^{2/3})$), the regret bound that we can achieve becomes better. However, even if we allow the queue length to increase over $\tilde{\mathrm{\Theta }}(T^{2/3})$, the regret bound cannot be improved and remains $\tilde{O}(T^{5/6})$.

6. Proof Roadmap

In this section, we present a proof roadmap for Theorem 1. The complete proof of Theorem 1 can be found in the Online Appendix. In the proof roadmap, we will consider the choice of parameters as in Corollary 1 to make the proof idea clear, that is, $ϵ=T^{-1/3}$, $\eta =\delta =T^{-1/6}$, $q^{\text{th}}=T^{2/3}$, $\beta =5$.

For the first outer iteration, we have no control of the queue length, so the queue length will possibly increase up to $MN=\tilde{\mathrm{\Theta }}(T^{2/3})$. Also, because the queue length is controlled by the threshold $q^{\text{th}}=T^{2/3}$ after the first outer iteration, the queue-length bound is $\tilde{O}(T^{2/3})$.

For the regret bound, the proof roadmap is shown in Figure 7. We first define an event $\mathcal{C}$, which means that the estimations of all the arrival rates are $ϵ$-accurate. Then the regret can be divided into the regret when the event $\mathcal{C}$ occurs and the regret when the event $\mathcal{C}$ does not occur. We show in Lemma 5 in the Online Appendix that the complement of the event, ${\mathcal{C}}^{\text{c}}$, happens with low probability. Intuitively, because for each estimation we use $N=\tilde{O}(1/{ϵ}^2)$ samples, we can obtain $ϵ$ accuracy with high probability by Hoeffding’s inequality. Note that Lemma 5 cannot be proved by simply applying Hoeffding’s inequality, and we will discuss the challenge in Section 7.

Therefore, the regret when the event $\mathcal{C}$ does not happen can be bounded. For the regret when the event $\mathcal{C}$ happens, that is, the estimations are $ϵ$-accurate, we further divide it into two parts. One part is the regret when the lengths of all the queues are less than the threshold $q^{\text{th}}$ so that there is no queue that is rejecting arrivals, and the other part is the regret induced by rejecting arrivals when there exists a queue whose length is greater than or equal to the threshold $q^{\text{th}}$. For the latter part, we can bound it by the expected number of time slots when a queue is rejecting arrivals. We show in Lemma 6 in the Online Appendix that this can be bounded by $O(T^{5/6})$. The proof is using Lyapunov drift analysis with a Lyapunov function $V_{\text{c}}(t)≔{\sum }_i{Q}_{\text{c},i}^2(t)$ for the customer side and $V_{\text{s}}(t)≔{\sum }_j{Q}_{\text{s},j}^2(t)$ for the server side. The challenge of the proof will be discussed in Section 7.

For the part of regret when there is no queue that is rejecting arrivals, regret is induced by zero-order optimization process. We show in the Online Appendix that this part of regret can be bounded by $\tilde{O}(T^{5/6})$. The intuition is as follows. If there is only one run of the system in each outer iteration, then from the literature of two-point method of zero-order optimization (Agarwal et al. 2010), the regret will be bounded by $O(\sqrt{K})$, where K is the number of outer iterations. In our algorithm, there are $\tilde{\mathrm{\Theta }}(T^{2/3})$ runs of the systems in each outer iterations, and there are $\tilde{\mathrm{\Theta }}(T^{1/3})$ outer iterations. Hence, the regret will be bounded by $\tilde{\mathrm{\Theta }}(T^{2/3})O(\sqrt{T^{1/3}})=\tilde{O}(T^{5/6})$. However, the proof needs additional steps because, even in the same outer iteration, the prices and arrival rates are changing. In fact, we need to connect the actual prices to the prices corresponding to $\mathit{x}(k)$. Moreover, there can be dependence between the arrival rate estimation and the randomness of the optimization algorithm, which we will discuss in Section 7.

7. Challenges in the Proof

In this section, we discuss the challenges in the proof of Theorem 1 and the methods we use to overcome them.

The first challenge is to prove that the event ${\mathcal{C}}^{\text{c}}$ occurs with low probability (Lemma 5 in the Online Appendix). The event $\mathcal{C}$ is defined as

where $t_{\text{c},i}^{+}(k,m,n)$ is the time slot when the price $p_{\text{c},i}^{+}(k,m)$ is run for the nth time for the customer-side queue i, and similarly, we define $t_{\text{c},i}^{-}(k,m,n)$, $t_{\text{s},j}^{+}(k,m,n)$, and $t_{\text{s},j}^{-}(k,m,n)$. In the definition, we require that the accurate estimation holds for any arrival rates within [0, 1] because we want to ensure the independence between the event $\mathcal{C}$ and the randomness of $\mathit{u}(k)$ in Algorithm 2, which we will discuss later in this section. To prove that the event $\mathcal{C}$ holds with high probability, simply using Hoeffding’s inequality with the union bound does not work because arrival rates are continuous random variables within [0, 1]. Therefore, we use a discretization idea that is similar to the covering argument for linear bandits (Lattimore and Szepesvári 2020). We define a set ${\mathcal{S}}_{[0,1]}$, a discretized version of [0, 1] with resolution $ϵ/2$, and rewrite the first inequality in the definition of $\mathcal{C}$ as $\left|\right(1/N){\sum }_{n=1}^N𝟙\{U_{\text{c},i}^{+}(k,m,n)\le \lambda \}-\lambda |<ϵ$, where $U_{\text{c},i}^{+}(k,m,n)$ is a random variable uniformly distributed in [0, 1] that is generated independently at the very beginning of the process, and similarly, we can rewrite other inequalities in the definition of $\mathcal{C}$. We can bound the quantization error and then use Hoeffding’s inequality and the union bound over $\lambda \in {\mathcal{S}}_{[0,1]}$ to bound the probability of ${\mathcal{C}}^{\text{c}}$.

The second challenge is to prove the upper bound on the expected number of time slots when the length of one of the queues is greater than or equal to the threshold $q^{\text{th}}$ (Lemma 6 in the Online Appendix). As mentioned in the proof roadmap in the previous section, we use Lyapunov drift analysis with quadratic Lyapunov functions. The challenge is how we make sure that the actual arrival rates are balanced or almost balanced. We know that $\mathit{x}(k)\in {\mathcal{D}}^{\prime }$, so the corresponding arrival rates are balanced. Because ${\mathit{x}}^{+}(k)$ and ${\mathit{x}}^{-}(k)$ are $\delta$-close to $\mathit{x}(k)$, their corresponding arrival rates are almost balanced. We want to prove that the actual arrival rates are close enough to the almost balanced arrival rates corresponding to ${\mathit{x}}^{+}(k)$ or ${\mathit{x}}^{-}(k)$. To show this, we use an important property that the true price corresponding to ${\mathit{x}}^{+}(k)$ or ${\mathit{x}}^{-}(k)$ is within the search interval of the bisection algorithm with high probability and an important fact that the width of the search interval is small enough for $k\ge 2$. Therefore, the actual arrival rates are also almost balanced for $k\ge 2$.

The third challenge is bounding the regret induced by zero-order optimization conditioned on $ϵ$-accurate arrival rate estimations (Lemma 7 in the Online Appendix). As mentioned in the proof roadmap in the previous section, the challenge is that there could be dependence between the estimation of arrival rates and the randomness ($\mathit{u}(k)$) in the optimization algorithm. By defining the event $\mathcal{C}$ such that the $ϵ$-accuracy is required for all arrival rates in [0, 1], we can show that the event $\mathcal{C}$ is independent of $\mathit{u}(k)$. Note that if we change the definition of $\mathcal{C}$ such that only the estimations of the actual arrival rates are $ϵ$-accurate, this independence does not hold. This independence between $\mathcal{C}$ and $\mathit{u}(k)$ is essential so that, conditioned on the event $\mathcal{C}$, we can use the proof idea of two-point method of zero-order optimization to bound the regret.

8. Numerical Results

In this section, we present numerical results of the proposed algorithm and compare its performance with that of the UCB algorithm with uniform discretization designed for Lipschitz bandits (Slivkins 2019).

We consider a system with three types of customers ($I=3$) and three types of servers ($J=3$). The compatibility graph is given by $\mathcal{E}=\{(1,1),(1,2),(1,3),(2,1),(2,2),(3,2),(3,3)\}.$ The demand and supply functions are given by $F_i({\lambda }_i)=2(1-{\lambda }_i)$ for all $i=1,2,3$ and $G_j({\mu }_j)=2{\mu }_j$ for all $j=1,2,3$. We compare the following algorithms.

• Proposed algorithm: The parameters are set to $q^{\text{th}}=t^{2/3}$, $\beta =1.0$, $ϵ=1.0\times t^{-1/3}$, $\delta =0.2\times t^{-1/6}$, $\eta =0.1\times t^{-1/6}$, and $e_{\text{c},i}=e_{\text{s},j}=8\max \{ϵ,\delta ,\eta \}$.

• Discretization-UCB: We first discretize the price space uniformly and then apply UCB algorithm as in Slivkins (2019). We gradually refine the discretization so that the discretization error decreases at the rate of $T^{-1/(I+J+2)}$, which theoretically achieves the optimal regret order for Lipschitz bandits according to Slivkins (2019).

• Discretization-UCB with $w>0$: As mentioned in the introduction, the discretization-UCB algorithm fails to balance the matching rates and arrival rates, making it difficult to control the queue length. Therefore, we modify this algorithm by adding a penalty/bonus term such that the reward of pulling an arm at time t becomes

  $$(\text{profit} \text{at} \text{time} t)-w\left({\displaystyle \sum _i{Q}_{\text{c},i}}(t+1)+{\displaystyle \sum _j{Q}_{\text{s},j}}(t+1)-{\displaystyle \sum _i{Q}_{\text{c},i}}(t)-{\displaystyle \sum _j{Q}_{\text{s},j}}(t)\right),$$

where the additional term is the increase/decrease of the total queue length. Note that when $w=0$, it reduces to the original discretization-UCB algorithm.

For all the algorithms, we set a queue length threshold of $q^{\text{th}}=t^{2/3}$ for fair comparison, which can be viewed as the buffer size of each queue. All the algorithms use the longest-queue-first matching policy.

Figure 8 presents the results of the profit regret and the maximum queue lengths. Note that both the x axis and y axis of the figures are in log scale. We can see that the proposed algorithm significantly outperforms the discretization-UCB algorithm ($w=0$) in terms of both profit regret and maximum queue length. The maximum queue length under the discretization-UCB algorithm grows at the same rate as the threshold $t^{2/3}$, meaning that the queue lengths consistently hit the buffer size. This indicates that the discretization-UCB algorithm fails to control the queue lengths. The regret under the discretization-UCB algorithm grows almost linearly with t, because rejecting arrivals whenever the queue length hits the buffer size (threshold) incurs a constant regret, and the queue lengths hit the threshold frequently. The modified discretization-UCB algorithms with $w=1.0$ and $w=2.0$ achieve a better maximum queue length performance. However, their profit regret remains significantly worse than that of the proposed algorithm. The reason could be that the additional penalty/bonus affects the exploration of the arms (prices).

Sensitivity analysis of the proposed algorithm to its parameters, along with additional numerical results, can be found in the Online Appendix.

9. Conclusions

We studied the pricing and matching problem for two-sided queueing systems with unknown demand and supply functions. We proposed a novel learning-based pricing algorithm that combines zero-order stochastic projected gradient ascent with bisection search. We proved that the proposed algorithm yields a sublinear regret $\tilde{O}(T^{5/6})$ and guarantees an anytime queue-length bound $\tilde{O}(T^{2/3})$ and established a tradeoff between the regret bound and the queue-length bound: $\tilde{O}(T^{1-\gamma /4})$ versus $\tilde{O}(T^{\gamma })$ for $\gamma \in (0,2/3].$ In addition to ride-sharing platforms, the proposed algorithm also has potential applications in online marketplaces and healthcare systems.