Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
72,438 characters · 22 sections · 55 citation commands
A Primal-dual Learning Algorithm for Personalized Dynamic Pricing with an Inventory Constraint
Keywords: network revenue management, multi-armed bandit, learning and earning, dynamic pricing, online retailing
Dynamic pricing is practiced in many industries including travel, entertainment, and retail. When the capacity cannot be adjusted within the sales horizon, dynamic pricing can increase revenues significantly by adjusting prices in response to the changes in the marginal value of capacity that are driven by the demand and pricing process. The presence of online channels has enabled sellers to use personalized dynamic pricing to different consumer types resulting in potentially higher firm profits. The types may correspond to the features of a consumer, such as age, gender and address, which can be observed or inferred through membership programs and browser cookies. Along with opportunities come challenges. The aggregate demand forecasts from historical data, which usually reflects the price sensitivity of the entire market, is of little use. Instead, the firm has to form accurate demand estimates for each type of consumers.
In this paper, we consider a firm selling a product over a finite sales horizon. The inventory is given at the beginning of the horizon and not allowed to be replenished. The inability to order additional inventory is a hard constraint in the travel industry as it is nearly possible to add capacity to a plane or to a hotel in the short run. In fashion retailing, this is also a hard constraint as production and distribution lead-times may be larger than the sales horizon. We assume there are $M$ different consumer types. The types may be determined in advance by clustering algorithms, which can be applied to each consumer to label its type. We refer the reader to Chapter 8 in gallego2019revenue for ideas on how to cluster consumer types into a reasonable number of types. Although the type of each consumer is observed by the firm, the demand functions associated with each type are not known initially. Therefore, the firm has to experiment different prices for each type of consumers to learn the demand functions and find the optimal prices. Therefore, it features the exploration/exploitation (learning/earning) trade-off.
We propose a learning algorithm for the personalized dynamic pricing problem described above. Compared to the literature, our algorithm explicitly learns the dual solution, in addition to the optimal prices in the primal space. This allows the algorithm to achieve the near-optimal regret, a measure commonly used to assess learning algorithms.
This paper makes two contributions to the literature. By regarding the demand from the $M$ consumer types as demands for $M$ different products, then our problem is a special case of a network dynamic pricing problem with $M$ products and a single resource constraint. To the best of our knowledge, no algorithm has achieved the optimal rate of regret under the general assumptions.\footnote{The algorithm in chen2018self achieves the same regret assuming the objective function is infinitely smooth with uniformly bounded derivatives. However, such assumption are often too restrictive. For example, the $k$th derivative of $d(p)=\exp(-ap)$ is not uniformly bounded for $a>1$ as $k\to\infty$.} See Section (ref) and Section (ref) for more details.
From the perspective of algorithmic design, we demonstrate the feasibility of integrating the primal-dual formulation and learning. The dual variable is not a typical target to learn in the learning literature, because unlike the primal variables, it cannot be experimented directly. In our algorithm, we empirically estimate the Lagrangian function and sequentially form interval estimators for the dual optimal solution. This approach may provide novel algorithmic architectures for other learning problems with resource constraints.\footnote{In other learning algorithms involving primal-dual explorations such as badanidiyuru2013bandits, the dual optimal solution is not learned explicitly. So the design of their algorithm is fundamentally different from ours.}
This paper provides the following qualitative insights:
There is a stream of rapidly growing literature on a firm's pricing problem when the demand function is unknown besbes2009dynamic,araman2009dynamic,farias2010dynamic,broder2012dynamic,denboer2014simul,den2015dynamicor,keskin2014dynamic,cheung2017dynamic,keskin2018incomplete,den2019discontinuous. See den2015dynamic for a comprehensive survey. Since the firm does not know the optimal price, it has to experiment different (suboptimal) prices and update its belief about the underlying demand function. Therefore, the firm has to balance the exploration/exploitation trade-off, which is usually referred to as the learning-and-earning problem in this line of literature. Among them, our paper is related to those with nonparametric formulations and inventory constraints besbes2009dynamic,wang2014close,lei2014near. In addition, we consider personalized dynamic pricing for multiple types of consumers, while most of the above papers consider a single type.
Personalized dynamic pricing can be regarded as a special case of learning with contextual information qiang2016dynamic,javanmard2016dynamic,cohen2016feature,ban2017personalized,chen2018nonparametric,keskin2019dynamic. The main difference of our paper from this stream of literature is summarized below. First, instead of representing the contextual information by a feature vector, we choose to use discrete types to categorize consumers. This could be the outcome of a clustering procedure that pre-processes consumer data. Since the number of types is arbitrary, our setup is merely a technical simplification without losing too much practical generality. Second, we use a nonparametric formulation for the objective function. That is, the demand functions of each type of consumers are only required to satisfy some basic assumptions such as continuity without any specific forms. Third, unlike this literature, we consider an inventory constraint and thus the pricing decision made over time has intertemporal dependence.
The problem studied in this paper is a special case of the multi-product dynamic pricing problem over a network gallego1997multiproduct and thus closely related to the literature on demand learning in that setting. besbes2012blind study the multi-product network revenue management problem with unknown demand functions when the price for each product are chosen from a discrete set. (Hereafter we use network revenue management to highlight the setup of a price menu, in contrast to network dynamic pricing that allows for continuous prices.) The proposed algorithm achieves diminishing regret when the inventory and demand are scaled in proportion. ferreira2017online study the same problem as besbes2012blind and show that Thompson sampling can achieve the rate of regret, $n^{-1/2}$, which is the best one can hope for with even one product and one resource. For continuous prices, however, besbes2012blind demonstrate that learning may suffer from the curse of dimensionality. The incurred regret may grow at rate $n^{-1/(d+3)}$ with $d$ products (which is equivalent to the number of types in our problem). This is consistent with the result in slivkins2014contextual, which studies a generic learning problem without inventory constraints. The tight regret bound derived in slivkins2014contextual grows at $n^{-1/(d+2)}$ for $d$ continuous decision variables. Sufficient smoothness may relieve the curse of dimensionality, as argued by besbes2012blind,chen2018self. In particular, with an infinite degree of smoothness with bounded derivatives, chen2018self design an algorithm that almost achieves rate $n^{-1/2}$. Global convexity helps as well, as chen2019network propose a gradient-based algorithm that achieves rate $n^{-1/5}$. In this paper, we present a learning algorithm that achieves the optimal rate $n^{-1/2}$ with one resource constraint and arbitrary number of products (consumer types), without imposing smoothness conditions.
This paper is also related to the vast literature studying multi-armed bandit problems. See cesa2006prediction,bubeck2012regret for a comprehensive survey. The classic multi-armed bandit problem involves finite arms. There is a stream of literature studying the so-called continuum-armed bandit problems kleinberg2005nearly,Auer2007,kleinberg2008multi,bubeck2011x, in which there are infinite number of arms (decisions). slivkins2014contextual provides a tight regret bound on a generic learning problem with multiple continuous decision variables; the regret deteriorates exponentially as the number of decisions increases, demonstrating the curse of dimensionality. This line of literature does not consider resource constraints. Recently, there are studies combining multi-armed bandit problems with resource constraints, which is referred to as bandits with knapsacks (BwK) badanidiyuru2013bandits,badanidiyuru2014resourceful,agrawal2014bandits. The regret derived in those papers is not directly comparable to ours, because the decisions are discrete in their setting. For discrete decisions, the curse of dimensionality does not emerge. This paper is also related to online convex optimization (OCO); see shalev2012online for a review. It is worth pointing out that the duality approach has also been used in BwK and OCO to implement the algorithm and prove the regret bound. However, the dual optimal solution is typically not learned explicitly. One exception is mahdavi2013stochastic, whose algorithm learns the dual solutions by gradient descent in the primal/dual space. In their OCO setting, the function is given in each period and the gradient can be evaluated, which does not apply to our problem.
Consider a monopolistic firm selling a single product in a finite selling season $T$, with $c$ units of initial inventory. The product cannot be replenished and perishes at the end of the horizon with zero salvage values. There are $M$ types of consumers. Consumers with the same type have similar features such as education backgrounds, ages, and addresses. The firm observes the type of each arriving consumer, and is allowed to price-discriminate according to the type. This is referred to as personalized pricing, which is increasingly popular in online retailing due to the observation that the demand function differs dramatically across types. Therefore, we model the arrival of type-$m$ consumers by a Poisson process with instantaneous rate $d_m(p_m(t))$, where $p_m(t)$ is the price charged for type-$m$ consumers at time $t$ and $d_m(\cdot)$ is the demand function of type-$m$ consumers.
We focus on the case that the information of the demand function associated with each type and the type distribution among the population is absent at the beginning of the season. The objective of the firm is to maximize the expected revenue collected over the horizon, subject to the inventory constraint. To achieve the goal, the firm has to learn the demand function $d_m(\cdot)$ for $m=1,\dots,M$ and the associated optimal prices in the process. We first characterize the problem when all the information is available.
When $d_m(\cdot)$ is known to the firm, the firm's objective is to maximize
where $\bm p(t)=\left\{p_1(t),\ldots,p_M(t)\right\}$ is a pricing policy that is adapted to the filtration $\mathcal F_t$ associated with the sales process, and $N_{m,t}(\lambda_t)$ is an independent Poisson process with instantaneous rate $\lambda_t$. When the inventory is depleted, then $\bm p(t)$ is forced to be $\bm p_{\infty}$, which is a menu of choke prices at which future demand from all types is turned off.
A classic approach in revenue management (e.g., see gallego1997multiproduct) to this problem is to consider the fluid approximation of (ref). That is
where we have replaced the Poisson process $N_{m,t}(d_m(p_m(t))$ in the original formulation by the intensity $d_m(p_m(t))$. Note that the fluid approximation (ref) is a deterministic optimization problem. Before presenting the primal-dual formulation of (ref), we make the following standard assumption:
It is easy to verify that this mild assumption is satisfied by most demand functions, such as the exponential demand $d(p)=a\exp(-bp)$ and the linear demand $d(p)=a-bp$. The exponential demand, on the other hand, does not have uniformly bounded derivatives of any orders, required by chen2018self.
Consider the Lagrangian function for the fluid approximation (ref)
and the dual function
Under Assumption (ref), the following quantities are well defined
$\mathcal R_m(z)$ and $\mathcal P_m(z)$ can be interpreted as the optimal value and optimal solution of the profit-maximization problem for type-$m$ consumers when the unit cost is $z$. They are closely related to the dual function (ref) as $g(z)=cz+T\sum_{m=1}^M\mathcal R_m(z)$; provided with a dual variable $z$, the optimal $\bm p(t)$ in (ref) is time-invariant: $p_m(t)\equiv \mathcal P_m(z)$. The properties are summarized below (see also gallego2019revenue):
Proposition (ref) states that the fluid approximation (ref) admits a time-invariant pricing policy $p^{\ast}_m$. Moreover, the optimal solution is closely related to the dual optimal solution $z^{\ast}$, which is usually interpreted as the shadow cost of inventory. When $z^{\ast}>0$, the initial capacity is insufficient and thus the inventory constraint is binding by complementary slackness: $c=T\sum_{m=1}^Md_m(\mathcal P_m(z^{\ast}))$. When $z^{\ast}=0$, the inventory is sufficient and the optimal price $p^{\ast}_m=\mathcal P_m(0)$ maximizes the revenue rate $pd_m(p)$ as if there is no inventory constraint.
The connection between $J^D(T,c)$ and $J(T,c)$ has been studied extensively in the revenue management literature. In particular, gallego1997multiproduct find that the revenue from the fluid approximation is an upper bound for the stochastic problem, i.e., $J^D(T,c)\ge J(T,c)$. The tie becomes closer when the demand and capacity scale in proportion: if we index a sequence of systems by $n$ and let $d_{m,n}(\cdot)=nd_m(\cdot)$ and $c_n = nc$ in the $n$th system, then the revenues satisfy $J^D_{n}(T,c)-J_n(T,c)=O(\sqrt{n})$. Since $J^D_{n}(T,c)$ scales linearly in $n$, the gap between $J_n^D(T,c)$ and $J_n(T,c)$ diminishes relative to the earned revenue as $n$ grows. More importantly, the optimal solution to (ref), $\{p^{\ast}_m\}_{m=1}^M$, which also maximizes the fluid approximation for the scaled system $J^D_n(T,c)$, performs well in the stochastic problem (ref) as a special suboptimal pricing policy (it is constant and thus adapted to $\mathcal F_t$). More precisely, the expected revenue for $\{p^{\ast}_m\}_{m=1}^M$ in the $n$th stochastic system satisfies
where $\tau$ is the minimum of $T$ and the stopping time when the inventory reaches zero. Combined with the fact that $J_n^D\ge J_n$, $\{p^{\ast}_m\}_{m=1}^M$ is near-optimal in the $n$th stochastic system. Therefore, the prices $\{p^{\ast}_m\}_{m=1}^M$ are the goal of our learning policy when $d_m(\cdot)$ is not known to the firm.
Suppose the firm does not know $d_m(\cdot)$ at the beginning of the horizon. To earn high expected revenues over the horizon, the firm adopts an $\mathcal F_t$-predictable pricing policy $\pi$. That is, at time $t$, $\pi_t$ only depends on the adopted prices and the observed sales for each type of consumers prior to $t$. It then outputs a price vector $\{P_1(t),\ldots,P_m(t)\}$ for each type of consumers at time $t$. We denote the expected revenue associated with a policy $\pi$ by $J^{\pi}(T,c)$. Clearly, the unavailability of the information regarding $d_m(\cdot)$ incurs a cost to the firm, and thus $J^{\pi}(T,c)\le J(T,c)\le J^D(T,c)$.
The objective of this study is to design a policy so that $J(T,c)-J^{\pi}(T,c)$ is small, especially when demand and capacity are scaled. Therefore, similar to besbes2009dynamic, we consider the following criterion, referred to as the regret, of a policy $\pi$:
where $J_n^{\pi}(T,c)$ is the expected revenue $\pi$ generates in the $n$th stochastic system. Note that $\pi$ may depend on $n$, and we suppress the dependence to simplify notations. The regret measures the revenue loss $J_n^D(T,c)-J_n^{\pi}(T,c)$ relative to $J_n^D(T,c)$. The goal of the policy $\pi$ is to ensure $\lim_{n\to\infty}R_n^{\pi}(T,c)=0$. That is, the learning incurs no significant cost for large systems.
It has been shown in besbes2009dynamic,wang2014close that for $M=1$, any learning policy incurs regret whose rate is no less than $n^{-1/2}$ for some problem instances. Indeed, even if we replace $J_n^{\pi}(T,c)$ by $J_n(T,c)$, which is the full-information upper bound for $J_n^{\pi}(T,c)$, the quantity (ref) is of order $n^{-1/2}$ by the discussion in Section (ref). In other words, one cannot expect to design a learning policy whose regret grows slower than $n^{-1/2}$. Thus, $n^{-1/2}$ (possibly with logarithmic terms in $n$) is the target regret of our proposed learning policy. It is also worth noticing that we adopt a nonparametric formulation. In parametric formulations, one may estimate the parameter using historical data and conduct a policy that maximizes the objective based on the estimator, without deliberate exploration. The so-called certainty-equivalence control may or may not lead to incomplete learning as shown by keskin2018incomplete. In the nonparametric setting, a wider range of exploration seems mandatory because no global information is learned through local experimentation.
In this section, we introduce an algorithm (learning policy) based on the primal-dual formulation. We first explain the steps of the algorithm, and then analyze its regret. Combined with the lower bound for regret in besbes2009dynamic,wang2014close, the regret of the algorithm achieves near optimality for the problem considered in Section (ref).
Before proceeding, we state what the firm has information of initially. The firm knows $M$, $T$, $n$, $c$, and the constants specified by Assumption (ref). Moreover, we impose a mild assumption in addition to Assumption (ref).
Note that $p^{\ast}_m$ and $z^{\ast}$ are the primal/dual optimal solutions to the fluid approximation (ref). Assumption (ref) states that although the firm does not know the optimal solutions, it does have the information of their ranges. Since $\underline p,\overline p$ and $\overline z$ can be arbitrary finite numbers, this assumption is not restrictive.
We first explain the intuition behind the algorithm. If the firm knew the full information, then it would have found the pricing policy $p_m^\ast$ through the primal-dual formulation
When the information of $d_m(p)$ is not available, both optimization problems are unsolvable. However, the firm can experiment with different prices and use the observed sales as a noisy but unbiased estimator for $d_m(p)$ at those prices. The noisy estimator is a Poisson random variable. Then, the firm could plug the estimators into (ref) to solve them “empirically”, obtaining estimators for $z^{\ast}$ and $p_m^{\ast}$ for $m=1,\ldots,M$. One would imagine that the estimators for $z^{\ast}$ and $p_m^{\ast}$ are not necessarily accurate. Indeed, the accuracy of such a procedure depends crucially on two aspects:
Ideally, to obtain accurate estimators for $z^{\ast}$ and $p_m^{\ast}$, the firm would set a refined grid of prices for each type of consumers and try each price for a long period during the season. Those suboptimal prices, however, lead to substantial revenue loss.
To solve the exploration/exploitation dilemma, we divide $[0,T]$ into multiple phases. After each phase, the sales for each type of consumers during the phase are observed at a set of prices to form estimators for $d_m(p)$. Then (ref) is solved empirically to obtain point estimators for $z^{\ast}$ and $p_m^{\ast}$. In the next phase, those point estimators are used to form interval estimators for $z^{\ast}$ and $p_m^{\ast}$. The interval estimators help to narrow down the range of prices to experiment. Therefore, as the algorithm enters new phases, the burden to explore is gradually relieved and it can afford to try a more refined price grid for a longer period of time. The revenue loss is also limited because the experimented prices fall into a narrow interval containing $p_m^{\ast}$ with high probability.
Next we explain the details of the algorithm. Let $\{P_1(t),\ldots,P_M(t)\}$ be the stochastic pricing policy associated with $\pi$. Without further mention, we always suppose that when the inventory is depleted, $P_m(t)$ is automatically switched to the choke price $p_{\infty}$ for all $m$. Given $n$, the algorithm divides $[0,T]$ into consecutive phases $k=1,2,\ldots,K$. The length of phase $k$ is $\tau^{(k)}$. We also denote the beginning of phase $k$ by $t_k$. Thus $t_k = \sum_{i=1}^{k-1}\tau^{(i)}$. Let $\epsilon>0$ be a small constant.
At the beginning of phase $k$, the firm has interval estimators for $p_m^{\ast}$ and $z^{\ast}$, $[\underline p_{m}^{(k)},\overline p_{m}^{(k)}]$ and $[\underline{z}^{(k)},\overline z^{(k)}]$, obtained from the last phase, which ensure that $p^{\ast}_m\in [\underline p_{m}^{(k)},\overline p_{m}^{(k)}]$ and $z^{\ast}\in [\underline{z}^{(k)},\overline z^{(k)}]$ with high probability. During phase $k$, the price interval $[\underline p_{m}^{(k)},\overline p_{m}^{(k)}]$, whose length is denoted $\Delta_m^{(k)}$, is discretized to $N^{(k)}+1$ equally spaced grid points, i.e., $p_{m,j}^{(k)}\triangleq \underline p_{m}^{(k)}+j \delta_m^{(k)}$ for $j=0,\ldots,N^{(k)}$ and $\delta_m^{(k)}\triangleq\Delta^{(k)}_m/N^{(k)}$. During phase $k$, the algorithm sets price $p_{m,j}^{(k)}$ for type-$m$ consumers for a period of length $\tau^{(k)}/(N^{(k)}+1)$.
At the end of phase $k$, the observed sales, $D_{m,j}^{(k)}$, from type-$m$ consumers at price $p_{m,j}^{{(k)}}$ is a Poisson random variable with mean $nd_m(p_{m,j}^{{(k)}}) \tau^{(k)}/(N^{(k)}+1)$. Therefore, an unbiased estimate for $d_m(p_{m,j}^{(k)})$ is
To form a point estimator for $z^{\ast}$, the firm substitutes $\hat d^{(k)}_{m,j}$ into $g(z)$ (the right-hand side of the first equation of (ref)), i.e.,
To find $z\in [\underline{z}^{(k)},\overline z^{(k)}]$ that maximizes the above expression, the firm divides $[\underline{z}^{(k)},\overline z^{(k)}]$, whose length is denoted $\Delta_z^{(k)}$, into $N_z^{(k)}$ equally spaced grid points, $\underline{z}^{(k)}+j \delta_z^{(k)}$ for $j=0,\ldots, N_z^{(k)}$ and $\delta_z^{(k)}\triangleq\Delta_z^{(k)}/(N_z^{(k)}+1)$. Therefore, a point estimator for $z^{\ast}$ can be obtained as follows\footnote{Alternatively, the firm can find $z^{(k)\ast}$ by solving the first-order condition for $g(z)$, $c-T\sum_{m=1}^M d_m(\mathcal P_m(z))=0$, using the empirical version of $d_m$ and $\mathcal P_m$. The regret analysis holds for this case. Also note that in theory we can find the optimal $z^{(k)\ast}$ exactly without discretization, as the equation is solved offline. The discretization is for practical purposes.}:
Based on $ z^{(k)\ast}$, the firm can obtain point estimators for $p_m^{\ast}$ by the second equation in (ref):
This completes the procedure in phase $k$.
At the beginning of phase $k+1$, the firm constructs interval estimators $[\underline p_{m}^{(k+1)},\overline p_{m}^{(k+1)}]$ ($[\underline{z}^{(k+1)},\overline z^{(k+1)}]$) based on the point estimators $p_m^{(k)\ast}$ ($z^{(k)^{\ast}}$) and pre-specified width $\bar\Delta^{(k+1)}$ ($\bar\Delta_z^{(k+1)}$) for all $m$:
Note that the intervals are properly truncated by $[\underline p,\overline p]$ and $[0,\overline z]$, and this is the only reason why $\bar \Delta^{(k+1)}$ ($\bar \Delta^{(k+1)}_z$) can potentially be different from $\Delta_m^{(k+1)}$ ($\Delta_z^{(k+1)}$). Then the procedure is repeated for phase $k+1$.
In the last phase, phase $K$, the algorithm behaves differently after forming the interval estimators $[\underline p_{m}^{(K)},\overline p_{m}^{(K)}]$ and $[\underline{z}^{(K)},\overline z^{(K)}]$. At the beginning of phase $K$, the firm checks whether $0\in [\underline{z}^{(K)},\overline z^{(K)}]$. If so, then with high probability $z^{\ast}=0$ and the capacity is sufficient. Therefore, the price $p_m^{\ast}$ is the unconstrained maximizer of $pd_m(p)$, i.e., $\mathcal P_m(0)$, for all $m$. As we will show in Section (ref), the width of the interval estimator $[\underline p_{m}^{(K)},\overline p_{m}^{(K)}]$ is roughly $\bar\Delta^{(K)}\sim n^{-1/4}$. Therefore, if the firm adheres to a constant price $p_m\in [\underline p_{m}^{(K)},\overline p_{m}^{(K)}]$ for type-$m$ consumers, the relative revenue loss for type-$m$ consumers in phase $K$ (ignoring the random fluctuation of Poisson arrivals) is approximately
where we rely on the concavity in Assumption (ref) and the fact that $p_m^{\ast}\in [\underline p_{m}^{(K)},\overline p_{m}^{(K)}]$ with high probability. This meets the target regret in Section (ref). Motivated by the argument above, the algorithm simply charges a constant price $p^{(K)}_m = \overline p_{m}^{(K)}+ \alpha$ for type-$m$ consumers until the end of the season for a pre-specified parameter $\alpha$. Note that we slightly mark up the prices by a small adjustment $\alpha\sim n^{-1/4}$ to guarantee that the inventory is sufficient when the inventory just meets the unconstrained optimal prices, i.e., $c=T\sum_{m=1}^Md_m(p_m^{\ast})$.
If the firm finds $0\notin [\underline{z}^{(K)},\overline z^{(K)}]$ at the beginning of phase $K$, which implies that $z^{\ast}>0$ and the capacity is insufficient with high probability, then a different procedure has to be used in phase $K$. The method for the case of $z^{\ast}=0$ no longer works: because $p_m^{\ast}$ is no longer the unconstrained maximizer of $pd_m(p)$, even for $p_m,p_m^{\ast}\in [\underline p_{m}^{(K)},\overline p_{m}^{(K)}]$, we have
This implies that a constant price in $[\underline p_{m}^{(K)},\overline p_{m}^{(K)}]$ for type-$m$ consumers will fail to meet the target regret. To address the problem, let $p_m^l = \underline{p}_m^{(K)}-\alpha$ and $p_m^u = \overline{p}^{(K)}_m+\alpha$ be conservative lower and upper bounds for $p_m^{\ast}$. It makes sure that $p_m^\ast\in [p_m^l,p_m^u]$ along with buffers around the boundary. The buffer guarantees that the solution to the linear interpolation (ref) below is stable. Let $S(t)$ be the cumulative sales aggregated from all types of consumers up to time $t$. The algorithm in phase $K$ is divided into the following four steps:
The goal of the above steps is to ensure the deviation of $S(T)$ from $nc$ is relatively small. In particular, from Lemma (ref) in Section (ref), the steps guarantee $|S(T)-nc|\sim n^{-1/2}$. Without further exploring the price space\footnote{Recall that the interval estimators for $p_m^{\ast}$, $\bar\Delta^{(K)}\sim n^{-1/4}$, are still too wide to meet the target regret.} the algorithm can still meet the target regret with a little exploration on the aggregate demand rate and by controlling the aggregate sales at $T$. We will discuss this point in Section (ref). The notations are summarized in Table (ref) in the appendix. The detailed steps of the algorithm are demonstrated in Algorithm (ref). Note that both “Input” and “Constant” are known to the firm, while “Parameters” are computed in Section (ref).
Let $\epsilon$ be a sufficiently small constant (independent of $n$). We set the following parameter values in Step (ref):
Therefore,
The choice of parameters guarantees that $p_m^{\ast}\in [\underline p_{m}^{(k)},\overline p_{m}^{(k)}]$ and $z^{\ast}\in [\underline{z}^{(k)},\overline z^{(k)}]$ occur with high probability. Moreover, at the beginning of phase $K$, the precision of $[\underline p_{m}^{(K)},\overline p_{m}^{(K)}]$ and $[\underline{z}^{(K)},\overline z^{(K)}]$ is $\bar\Delta^{(K)}\sim \bar\Delta^{(K)}_z\sim n^{-1/4}$.
Next we point out the connections to the algorithm in wang2014close. When the capacity is sufficient, then this algorithm is closely related to that in wang2014close: both target the precision $n^{-1/4}$ of the interval estimators for $p_m^{\ast}$, and our problem becomes $M$ independent learning problems in wang2014close. This is why the choices of $\tau^{(k)}$, $ N^{(k)}$, $\bar\Delta^{(k)}$ and $K$ are almost identical to that of wang2014close except for logarithmic terms. The design and analysis diverge for insufficient capacity. In order to track the dual variable, we construct interval estimators for $z$, which is not needed in wang2014close. In the last phase, based on the estimation of the dual variable, we solve for the optimal prices of all the types simultaneously. This is how we overcome the curse of dimensionality. Note that the dimensionality issue doesn't arise in wang2014close.
In this section, we analyze the regret of the primal-dual learning algorithm. To simplify the notation, we sometimes resort to a less rigorous expression, such as $\ensuremath{\mathsf{P}}(A)=1-O(n^{-1})$; its equivalence to $\ensuremath{\mathsf{P}}(A^c)=O(n^{-1})$ should be clear in the context.
Before proceeding, we introduce a modified stochastic system. Technically, if the inventory is depleted at $t$, then $P_m(t)$ must be switched to $p_{\infty}$, a choke price at which the demand of type-$m$ consumers is turned off, for all $m$. We use a similar simplification to lei2014near and consider a slightly different problem. When the inventory is depleted, instead of forced to set $p_{\infty}$ for all types of consumers, the firm can still use prices between $[\underline p, \overline p]$. To accommodate the extra demand, it outsources the extra demand at a unit cost $\overline p$. Denote the expected revenue of this modified system by $\tilde J^{\pi}_n$. Because $\overline p$ is higher than the price charged, we must have $\tilde J_n^{\pi}\le J_n^{\pi}$. To bound $J_n^D-J_n^{\pi}$, it suffices to bound $J_n^D-\tilde{J}_n^{\pi}$. Therefore, from now on, we investigate the pricing policy $P_m(t)$ associated with the algorithm without switching to $p_{\infty}$ once the inventory is depleted.
We first show that the number of phases is growing slowly in $n$.
We next show that the last phase takes the majority of the season.
Consider the following events which are measurable with respect to $\mathcal F_{t_k}$:
By design, $A_k$ and $B_k$ are the key to the success of the algorithm. If in some phase $k$, the interval estimators $[\underline p_{m}^{(k)},\overline p_{m}^{(k)}]$ and $[\underline{z}^{(k)},\overline z^{(k)}]$ do not contain $p_m^{\ast}$ and $z^{\ast}$, then (ref) and (ref) do not make sense any more. To make things worse, the optimal primal/dual pair $(p_m^{\ast},z^{\ast})$ cannot be recovered in subsequent phases and the learning policy is doomed to fail. Therefore, we want to show that $A_k\cap B_k$ occurs with high probability. The event $C_k$ is also crucial. Note that to estimate $z^{\ast}$, the algorithm solves a discrete and empirical version of the dual function, i.e., (ref). If $\mathcal P_m(z)$ does not fall into the interval estimator for some $z$, then $\max_{j_m = 0,\ldots, N^{(k)}} \hat d_{m,j_m}^{(k)}(p_{m,j_m}^{(k)}-z)$ in (ref) may provide a negatively biased estimator for $\mathcal R_m(z)$. As a result, the minimization in (ref) may not find the correct value.
From the definitions, it is easy to see that $A_k\supseteq B_k\cap C_k$. The following two lemmas show that $B_k$ and $C_k$ occur with high probability.
Combining Lemma (ref) and Lemma (ref), we have the following lemma, which states that at the beginning of phase $K$, the probability that the algorithm “goes wrong” is negligible.
The following two lemmas characterize the cumulative sales $S(t)$ at $t=t_K$, the beginning of phase $K$. Recall that the cumulative sales $S(t_K)$ can be expressed as $\int_0^{t_K}\sum_{m=1}^MdN_{m,t}(nd_m(P_m(t)))$. Therefore, $\ensuremath{\mathsf{E}}[S(t_K)] =n\ensuremath{\mathsf{E}}[\int_0^{t_K}\sum_{m=1}^Md_m(P_m(t))dt]$. Also note that in the fluid model, the inventory level at $t_K$ is $n\sum_{k=1}^{K-1}\tau^{(k)}\sum_{m=1}^Md_m(p_m^{\ast})$. Therefore, the next two lemma state that the cumulative sales process does not deviate too much from that in the fluid system at the beginning of phase $K$.
Roughly speaking (ignoring the logarithmic terms), Lemma (ref) and (ref) show that the inventory level at the beginning of phase $K$ misses the target inventory level in the fluid system by $n^{3/4}$. This is consistent with the precision of the price interval at $t_K$, which satisfies $\bar\Delta^{(K)}\sim n^{-1/4}$.
We next bound the regret when $z^{\ast}= 0$, i.e., when the capacity is not constrained.
The major steps of the proof are sketched below. We first express $\ensuremath{\mathsf{E}}[\tilde{J}_n^{\pi}]$ as
The first term is the expected revenue generated in each phase, and the second term accounts for the outsourcing cost explained in Remark (ref). Moreover, $J_n^D$ can be expressed as $\sum_{k=1}^K\ensuremath{\mathsf{E}}\left[\int_{t_k}^{t_{k+1}} p_m^{\ast}d_m(p_m^{\ast})dt\right]$. Thus, the difference between $J_n^{D}$ and the first term of (ref) can thus be bounded by
Because $p^{\ast}_m$ is the unconstrained maximizer of $pd_m(p)$, we can apply a quadratic bound in the second line by Assumption (ref). The last line follows from the high-probability event $A_k$, which implies that $|P_m(t)-p^{\ast}_m|\le \bar\Delta^{(k)}$ in phase $k\le K-1$. At the beginning of phase $K$, we can show that Step (ref) is triggered with high probability. In this case, $|P_m(t)-p^{\ast}_m|=|p_m^{(K)}-p_m^{\ast}|=|\overline p^{(K)}_m-p_m^{\ast}+\alpha|\le \bar\Delta^{(K)}+\alpha$ is not necessarily bounded by $\bar\Delta^{(K)}$. However, $\alpha$ is chosen carefully to match the order of $\bar\Delta^{(K)}$. By the choice of the parameters, the order of $n\sum_{k=1}^K\tau^{(k)}(\bar\Delta^{(K)})^2$ is $O((\log n)^{2+16\epsilon}n^{1/2})$.
To bound the second term of (ref), we show that the mean of the total sales over the horizon, $n\ensuremath{\mathsf{E}}\left[ \sum_{m=1}^M\int_0^Td_m(P_m(t))dt \right]$, does not exceed $nc$. This is achieved by charging a markup $p_m^{(K)}=\overline p^{(K)}_m+\alpha$ in phase $K$ and this is exactly the purpose of introducing $\alpha$. Since the random fluctuation of Poisson arrivals is bounded by $O(n^{1/2})$, we obtain the regret stated in Proposition (ref).
When $z^{\ast}>0$, the inventory is depleted at $T$ in the fluid system. We first show that the cumulative sales at the end of the horizon under the algorithm misses the target $nc$ by $O(n^{1/2})$.
The intuition behind the proof is explained below. We first show that $D_l^{(K)}$ and $D_u^{(K)}$ estimate $n\sum_{m=1}^Md_m(p_m^l)$ and $n\sum_{m=1}^Md_m(p_m^u)$ with precision $n^{1/2}$ (ignoring the logarithmic terms), because they are Poisson random variables with means of order $n$ and thus the standard deviations are $O(n^{1/2})$. With such precision, $\theta$ (Step (ref)) approximately solves
Note that regardless of the first $K-1$ phases, the remaining inventory is $nc-S(t_K)$ at $t_K$. Using $p_m^l$ ($p_m^u$) for a fraction $\theta$ ($1-\theta$) of phase $K$ serves as a corrective force to ensure the aggregate sales over the horizon to be close to $nc$ (the error bound $(\log n)^{\epsilon}n^{1/2}$ is caused by the random fluctuation of the Poisson arrivals).
Algorithm (ref) does not explore the price space in phase $K$, and thus the precision of $p_m^l$ and $p_m^u$ in Step (ref) is of order $n^{-1/4}$. Therefore, one would expect the sales to type-$m$ consumers miss the target $nTd_m(p^{\ast}_m)$ by $n^{-1/4}\times n=n^{3/4}$. This is indeed the case. However, Lemma (ref) guarantees that a simple exploration (Step (ref), (ref) and (ref)) is effective and leads to higher precision ($O(n^{1/2}$) for the aggregate sales of all types of consumers. This is crucial to the proof of the next proposition.
Different from Proposition (ref), $p^{\ast}_m$ is not the unconstrained maximizer of $p_m^{\ast}d_m(p_m^{\ast})$ when $z^{\ast}>0$. Therefore, if we follow (ref), the difference is approximately
which clearly does not meet our target $n^{1/2}$. The remedy to this situation is the following key observation. Let $r^{\ast\prime}_m$ and $r^{\ast\prime\prime}_m$ be the first- and second-order derivative of $r_m(\lambda)=\lambda d^{-1}_m(\lambda)$ at $\lambda=d_m(p_m^{\ast})$. By Taylor's expansion, the difference in revenue rate can be expressed as
Because $\lambda = d_m(p_m^{\ast})$ maximizes $r_m(\lambda)-\lambda z^{\ast}$ by the primal-dual formulation (Proposition (ref)), the first-order condition implies $r^{\ast\prime}_1=r^{\ast\prime}_2=\ldots=r^{\ast\prime}_M=z^{\ast}$. Therefore, an improved bound for (ref) can be derived:
The first term can be bounded by $(\log n)^{\epsilon}n^{1/2}$ by Lemma (ref); this is the reason why we need to bound the aggregate sales. The second term is of the same order as $n\sum_{k=1}^K\tau^{(k)}(\bar\Delta^{(K)})^2$ with high probability, which has been shown to meet the target in the remarks following Proposition (ref).
Combining Proposition (ref) and Proposition (ref) and recalling that $\epsilon$ can be an arbitrarily small constant, we obtain the main theorem.
By besbes2009dynamic, no learning policy can achieve regret that grows slower than $n^{-1/2}$ with $M=1$. Therefore, ignoring the logarithmic terms, the primal-dual learning algorithm achieves near-optimal regret.
In this section, we discuss several salient features of the primal-dual learning algorithm and clarify our findings in comparison to the literature.
This paper sets out on a quest to identify the fundamental limit of online learning (the optimal rate of regret) in the multi-product dynamic pricing problem over a network with a single resource. The first benchmark is provided in slivkins2014contextual: for a general Lipschitz-continuous objective function with a $d$-dimensional decision vector without resource constraints, the optimal rate of regret is $n^{-1/(2+d)}$. Recently, chen2018nonparametric show that when the objective function is locally concave, then the optimal rate is slightly better, and may be adjusted to $n^{-2/(3+d)}$. The number of decisions $d$ is the number of products in network dynamic pricing, or $M$ in this paper. Note that setting $d=1$ recovers the rate $n^{-1/2}$ in dynamic pricing (one product with one constraint) besbes2009dynamic,wang2014close. This is not good news: as the number of products $d$ increases, the rate deteriorates dramatically, which is referred to as the curse of dimensionality. It is also consistent with the finding in besbes2012blind. The quest to understand whether online learning is complicated by dimensionality in multi-product dynamic pricing problem is for continuous decision variables as is the case in dynamic pricing. The rate of regret from papers assuming discrete decisions badanidiyuru2013bandits,agrawal2014bandits,ferreira2017online does not apply to our setting.
Some recent papers have shed new light on this fundamental problem. chen2019network design a learning algorithm for network dynamic pricing that achieves rate $n^{-1/5}$ regardless of the number of products or constraints. Although the rate doesn't seem to be optimal, it does not depend on the dimension of the problem (the number of products or the number of resources). One may then question the fundamental difference between a general learning problem slivkins2014contextual and network dynamic pricing what property makes the latter easier to learn? li2019dimension and references there in reveal that it may be due to the intrinsic concavity structure of network dynamic pricing. In particular, li2019dimension show that in the setting of slivkins2014contextual, if the objective function is concave, then the regret is dimension-free ($n^{-1/2}$), because one can resort to gradient-based algorithms. In network dynamic pricing, Assumption (ref) is commonly adopted to guarantee good behavior of the optimal policy. Since the objective function is concave after one transforms the decision variable from price to quantity, it somehow inherits the dimension-free nature.
This opens up a new research question: can the $n^{-1/2}$ rate be obtained for learning in network dynamic pricing? This paper takes a step forward to a positive answer of this question as we can confirm the rate $n^{-1/2}$ under two simplifications: The objective function in our setting can be expressed as the sum of the revenues collected from each of the $M$ types of consumers, and thus separable in terms of the decision variables (prices); there is a single resource constraint. The first simplification implies that, when the inventory constraint is not binding, then the optimal rate of regret should be the same as $M$ independent learning problems with one decision variable, i.e., $O(Mn^{-1/2})$. It doesn't lead to dimension-free regret automatically when the constraint is binding, as the $M$-dimensional decision variables can be regarded as a vector on a $(M-1)$-dimensional manifold, after a proper transformation. On the manifold, the objective function is not separable in terms of the transformed decision variables any more. The second simplification can be relaxed as argued in Section (ref). Therefore, our result confirms that $n^{-1/2}$ may be achievable. Moreover, we provide the first dimension-free algorithm that is not gradient-based in the context.
The algorithm provides point and interval estimators for both the primal and dual optimal solutions, $p_m^{\ast}$ and $z^{\ast}$, in each phase. It turns out that such learning is necessary, as the regret of a policy that only learns the primal space incurs much higher regret (see, e.g., Section 4 of besbes2012blind). This is not surprising given the primal-dual formulation in Section (ref) since the revenues collected from different types of consumers are only coupled through the inventory constraint. Therefore, having an accurate estimator for the dual optimal solution $z^{\ast}$ helps to decouple the problem into $M$ independent learning problems of the form $\max_{p} d_m(p)(p-z^{\ast})$ for $m=1,\ldots,M$. These independent learning problems are known to have regret $O(n^{-1/2})$ (the parametric version of such problems is solved in keskin2014dynamic,denboer2014simul). However, $z^{\ast}$ is not given upfront and has to be learned. The key design of the algorithm is to nest the learning processes in the primal and dual spaces to narrow down the primal/dual optimal solutions sequentially.
The motivation of the study is personalized pricing, which can be recast as a multi-product dynamic pricing problem with a single constrained resource as mentioned in the introduction. We believe our algorithm may be applied to a generic multi-product dynamic pricing problemwith multiple resource constraints, as long as the demand is separable, as mentioned in Section (ref). Next we briefly introduce the extension to multiple resources.
Suppose there are $L$ resources, with initial capacity $\bm c=(c_1,\dots,c_L)$, and product $m$ consumes $a_{ml}$ units of resource $l$. The Lagrangian (ref) can be reformulated as
For a fixed $\bm z$ we define
and the dual function
As for the implementation of the algorithm, the exploration of the first $K-1$ phases is essentially the same (Step (ref) to Step (ref)). When finding the point estimator for $\bm z^{(k)\ast}$, Equation (ref) is vectorized, and the optimal vector $\bm z^{(k)\ast}$ is obtained by testing the grid in the confidence set of $\bm z$, which is a hyper-rectangle since each entry of $\bm z$ has a confidence interval. Normally the grid size explodes exponentially in the size of $\bm z$, i.e., $L$, and this is precisely causing the curse of dimensionality. However, in this algorithm (ref) is solved offline, i.e., the computation is not counted toward the final regret. In the beginning of the last phase, the dual/primal variables may have been estimated with error $n^{-1/4}$, similar to (ref), under properly chosen parameters. For products with sufficient capacity (a product $m$ enjoys sufficient capacity if $0\in [\underline z^{(K)}_{l}, \bar z^{(K)}_{l}]$ for all $l$ such that $a_{ml}>0$), this already leads to the optimal regret. For products with insufficient capacity, it is unclear how the linear interpolation (ref) can be implemented in the high dimension. We thus leave the algorithm and regret analysis in this case for future research.
As explained in Section (ref) and the remark following Proposition (ref), when $z^{\ast}>0$, the interval estimators for $p_m^{\ast}$ at the beginning of phase $K$ are still too wide ($n^{-1/4}$). Instead of exploring the price space further and attempting to narrow down the intervals in phase $K$, the algorithm simply controls the aggregate sales within an error margin of $n^{1/2}$ (Step (ref) to (ref) in Algorithm (ref) and Lemma (ref)). Focusing on a single quantity (the aggregate sales) turns out much easier than controlling $M$ decision variables. In fact, we suspect that no learning policy could estimate all $p_m^{\ast}$ with precision $n^{-1/2}$ at the end of the horizon\footnote{The case we study is different from wang2014close, in which the market-clearing price $d^{-1}(c/T)$ can be learned with precision $n^{-1/2}$. In our case, there are $m$ types of consumers and there are still $m-1$ degrees of freedom when a vector of prices $(p_1,\ldots,p_m)$ are market clearing.}.
Surprisingly, controlling the aggregate sales is sufficient to meet the target regret, even though the estimators for the optimal prices are not precise enough. The reason is explained by the remarks following Proposition (ref). In particular, the derivatives of the revenue rates $\lambda d^{-1}_m(\lambda)$ with respect to the demand rate $\lambda$ are all equal to $z^{\ast}$ at optimality $\lambda=d_m(p^{\ast}_m)$ for $m=1,\ldots,M$. This allows the firm to control the regret by the deviation of the aggregate sales.
Across different phases, the interval estimators for the optimal price $p_m^{\ast}$ may overlap for some $m$. In this case, the demand estimated at certain prices in the previous phases may be reused. For example, if $[\underline p_m^{(k)},\overline p_m^{(k)}]$ and $[\underline p_m^{(k+1)},\overline p_m^{(k+1)}]$ overlap, then for some $j_1$ and $j_2$ the price grid points $p_{m,j_1}^{(k)}$ and $p_{m,j_2}^{(k+1)}$ may be close, and the demand estimate for $p_{m,j_1}^{(k)}$ can provide useful information for $p_{m,j_2}^{(k+1)}$. In our algorithm, the data from previous phases are not reused mainly for the analysis, because data reuse introduces complex dependence between phases. In practice, we believe that data reuse may facilitate the learning of the demand function and increase the efficiency of the policy.
In a recent paper, den2019discontinuous study discontinuous demand functions, which is by far the most general assumption on smoothness, although their demand function has a parametric form. In our setting, Assumption (ref) rules out the possibility of discontinuity, and our algorithm is unlikely to work for discontinuous functions. This is because discontinuous functions cannot be concave, and they break the primal-dual formulation and thus the foundation of the algorithm. We also believe that in the nonparametric setting, no algorithm can achieve sublinear regret when the demand function can be discontinuous. Consider the following example: there is one type of consumer ($M=1$); we normalize the time horizon ($T=1$) and there is sufficient capacity ($c=100$). Let the price range be $p\in[0,1]$. Consider the demand (revenue) function satisfying
Because the capacity is not constrained, the problem is conceptually equivalent to the multi-armed bandit problem with $K$ arms. (The difference of continuous/discrete time is non-consequential in this case.) It is well-known that the minimax lower bound for the regret of such a learning problem is $O(\sqrt{Kn})$. Since $K$ can be arbitrarily large, the regret cannot possibly be controlled.
\singlespacing