{'fraction_non_alphanumeric': 0.04899582595773509, 'fraction_numerical': 0.015035293603444131, 'mean_word_length': 4.247706422018348, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Primal-dual Learning Algorithm for Personalized Dynamic Pricing with an Inventory Constraint

We consider the problem of a firm seeking to use personalized pricing to sell an exogenously given stock of a product over a finite selling horizon to different consumer types. We assume that the type of an arriving consumer can be observed but the demand function associated with each type is initially unknown. The firm sets personalized prices dynamically for each type and attempts to maximize the revenue over the season. We provide a learning algorithm that is near-optimal when the demand and capacity scale in proportion. The algorithm utilizes the primal-dual formulation of the problem and learns the dual optimal solution explicitly. It allows the algorithm to overcome the curse of dimensionality (the rate of regret is independent of the number of types) and sheds light on novel algorithmic designs for learning problems with resource constraints.


Introduction
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 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 Gallego and Topaloglu (2019) 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.

Contributions and Insights
This paper makes two contributions to the literature. By regarding the demand from the consumer types as demands for different products, then our problem is a special case of a network dynamic pricing problem with 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. 1 See Section 1.2 and Section 5.1 for more details.
From the perspective of algorithmic design, we demonstrate the feasibility of integrating the primaldual 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. 2 This paper provides the following qualitative insights: • It pays off to explicitly learn the dual optimal solution. The pricing decisions for types of consumers are coupled through the inventory constraint. However, having an accurate estimator for the dual optimal solution helps to decouple them into independent learning problems. This is the key reason why our algorithm can achieve the near-optimal regret.
• The learning complexity depends on not only the number of primal decision variables, but also the number of dual variables. As shown by Besbes and Zeevi (2012); Slivkins (2014), a highdimensional decision vector ( in this case) usually significantly complicates learning, reflecting the curse of dimensionality. Slivkins (2014) shows that the best achievable regret for a generic learning problem without resource constraints is −1/(2+ ) where is the dimension of the decision vector 3 . In contrast, we are able to obtain the rate −1/2 whose exponent is independent of . This is because the decision variables can be decoupled if the value of the dual optimal solution is given, and thus the effective dimension of the problem is no more than the number of dual variables, which is one in our case.

Literature Review
There is a stream of rapidly growing literature on a firm's pricing problem when the demand function is unknown (e.g. Besbes and Zeevi, 2009;Araman and Caldentey, 2009;Farias and Van Roy, 2010;Broder and Rusmevichientong, 2012;den Boer andZwart, 2014, 2015;Keskin and Zeevi, 2014;Cheung et al., 2017;Keskin and Zeevi, 2018;den Boer and Keskin, 2020). See den Boer (2015) 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 (Besbes and Zeevi, 2009;Wang et al., 2014;Lei et al., 2017). 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 (Qiang and Bayati, 2016;Javanmard and Nazerzadeh, 2016;Cohen et al., 2016;Ban and Keskin, 2017;Chen and Gallego, 2019;Keskin and Birge, 2019). 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 (Gallego and Van Ryzin, 1997) and thus closely related to the literature on demand learning in that setting. Besbes and Zeevi (2012) 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. Ferreira et al.
(2018) study the same problem as Besbes and Zeevi (2012) and show that Thompson sampling can achieve the rate of regret, −1/2 , which is the best one can hope for with even one product and one resource. For continuous prices, however, Besbes and Zeevi (2012) demonstrate that learning may suffer from the curse of dimensionality. The incurred regret may grow at rate −1/( +3) with products (which is equivalent to the number of types in our problem). This is consistent with the result in Slivkins (2014), which studies a generic learning problem without inventory constraints. The tight regret bound derived in Slivkins (2014) grows at −1/( +2) for continuous decision variables. Sufficient smoothness may relieve the curse of dimensionality, as argued by Besbes and Zeevi (2012); Chen et al. (2019). In particular, with an infinite degree of smoothness with bounded derivatives, Chen et al. (2019) design an algorithm that almost achieves rate −1/2 . Global convexity helps as well, as Chen and Shi (2019) propose a gradient-based algorithm that achieves rate −1/5 . In this paper, we present a learning algorithm that achieves the optimal rate −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 Cesa-Bianchi and Lugosi (2006); Bubeck and Cesa-Bianchi (2012) for a comprehensive survey. The classic multi-armed bandit problem involves finite arms. There is a stream of literature studying the so-called continuumarmed bandit problems (Kleinberg, 2005;Auer et al., 2007;Kleinberg et al., 2008;Bubeck et al., 2011), in which there are infinite number of arms (decisions). Slivkins (2014) 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 multiarmed bandit problems with resource constraints, which is referred to as bandits with knapsacks (BwK) Badanidiyuru et al. (2013Badanidiyuru et al. ( , 2014; Agrawal and Devanur (2014). 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 Shalev-Shwartz et al. (2012) 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 Mahdavi et al. (2013), 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.

Problem Formulation
Consider a monopolistic firm selling a single product in a finite selling season , with units of initial inventory. The product cannot be replenished and perishes at the end of the horizon with zero salvage values. There are 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-consumers by a Poisson process with instantaneous rate ( ( )), where ( ) is the price charged for type-consumers at time and (·) is the demand function of type-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 (·) for = 1, . . . , and the associated optimal prices in the process. We first characterize the problem when all the information is available.

The full-information Benchmark
When (·) is known to the firm, the firm's objective is to maximize . . , ( )} is a pricing policy that is adapted to the filtration F associated with the sales process, and , ( ) is an independent Poisson process with instantaneous rate . When the inventory is depleted, then ( ) is forced to be ∞ , 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 Gallego and Van Ryzin 1997) to this problem is to consider the fluid approximation of (1). That is where we have replaced the Poisson process , ( ( ( )) in the original formulation by the intensity ( ( )). Note that the fluid approximation (2) is a deterministic optimization problem. Before presenting the primal-dual formulation of (2), we make the following standard assumption: Assumption 1. For a price domain ∈ [0, ∞ ] and = 1, . . . , , we assume 1. The demand ( ) is strictly decreasing with an inverse function −1 (·) and bounded with ( ) ≤ 1 .
It is easy to verify that this mild assumption is satisfied by most demand functions, such as the exponential demand ( ) = exp(− ) and the linear demand ( ) = − . The exponential demand, on the other hand, does not have uniformly bounded derivatives of any orders, required by Chen et al. .

Primal-dual Formulation
Consider the Lagrangian function for the fluid approximation (2) and the dual function Under Assumption 1, the following quantities are well defined R ( ) and P ( ) can be interpreted as the optimal value and optimal solution of the profit-maximization problem for type-consumers when the unit cost is . They are closely related to the dual function (4) as ( ) = + =1 R ( ); provided with a dual variable , the optimal ( ) in (4)   Remark 2. To simplify the notation, we use the same set of constants as in Assumption 1 and assume that 0 < 3 ≤ ′′ ( ) ≤ 4 ; P ( ) is Lipschitz continuous with factor 2 .
Proposition 1 states that the fluid approximation (2) admits a time-invariant pricing policy * .
Moreover, the optimal solution is closely related to the dual optimal solution * , which is usually interpreted as the shadow cost of inventory. When * > 0, the initial capacity is insufficient and thus the inventory constraint is binding by complementary slackness: = =1 (P ( * )). When * = 0, the inventory is sufficient and the optimal price * = P (0) maximizes the revenue rate ( ) as if there is no inventory constraint.

Scaled Demand and Capacity
The connection between ( , ) and ( , ) has been studied extensively in the revenue management literature. In particular, Gallego and Van Ryzin (1997) find that the revenue from the fluid approximation is an upper bound for the stochastic problem, i.e., ( , ) ≥ ( , ). The tie becomes closer when the demand and capacity scale in proportion: if we index a sequence of systems by and let , (·) = (·) and = in the th system, then the revenues satisfy ( , ) − ( , ) = ( √ ).

Since
( , ) scales linearly in , the gap between ( , ) and ( , ) diminishes relative to the earned revenue as grows. More importantly, the optimal solution to (2), { * } =1 , which also maximizes the fluid approximation for the scaled system ( , ), performs well in the stochastic problem (1) as a special suboptimal pricing policy (it is constant and thus adapted to F ). More precisely, the expected revenue for { * } =1 in the th stochastic system satisfies where is the minimum of and the stopping time when the inventory reaches zero. Combined with the fact that ≥ , { * } =1 is near-optimal in the th stochastic system. Therefore, the prices { * } =1 are the goal of our learning policy when (·) is not known to the firm.

The Learning Policy and the Target Regret
Suppose the firm does not know (·) at the beginning of the horizon. To earn high expected revenues over the horizon, the firm adopts an F -predictable pricing policy . That is, at time , only depends on the adopted prices and the observed sales for each type of consumers prior to . It then outputs a price vector { 1 ( ), . . . , ( )} for each type of consumers at time . We denote the expected revenue associated with a policy by ( , ). Clearly, the unavailability of the information regarding (·) incurs a cost to the firm, and thus ( , ) ≤ ( , ) ≤ ( , ).
The objective of this study is to design a policy so that ( , ) − ( , ) is small, especially when demand and capacity are scaled. Therefore, similar to Besbes and Zeevi (2009), we consider the following criterion, referred to as the regret, of a policy : where ( , ) is the expected revenue generates in the th stochastic system. Note that may depend on , and we suppress the dependence to simplify notations. The regret measures the revenue loss ( , ) − ( , ) relative to ( , ). The goal of the policy is to ensure lim →∞ ( , ) = 0.
That is, the learning incurs no significant cost for large systems.
It has been shown in Besbes and Zeevi (2009); Wang et al. (2014) that for = 1, any learning policy incurs regret whose rate is no less than −1/2 for some problem instances. Indeed, even if we replace ( , ) by ( , ), which is the full-information upper bound for ( , ), the quantity (6) is of order −1/2 by the discussion in Section 2.1. In other words, one cannot expect to design a learning policy whose regret grows slower than −1/2 . Thus, −1/2 (possibly with logarithmic terms in ) 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 Keskin and Zeevi (2018). In the nonparametric setting, a wider range of exploration seems mandatory because no global information is learned through local experimentation.

The Primal-dual Learning Algorithm
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 Besbes and Zeevi (2009); Wang et al. (2014), the regret of the algorithm achieves near optimality for the problem considered in Section 2.
Before proceeding, we state what the firm has information of initially. The firm knows , , , , and the constants specified by Assumption 1. Moreover, we impose a mild assumption in addition to Assumption 1. Note that * and * are the primal/dual optimal solutions to the fluid approximation (2). Assumption 2 states that although the firm does not know the optimal solutions, it does have the information of their ranges. Since , and can be arbitrary finite numbers, this assumption is not restrictive.

The Intuition
We first explain the intuition behind the algorithm. If the firm knew the full information, then it would have found the pricing policy * through the primal-dual formulation * = argmin When the information of ( ) 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 ( ) at those prices. The noisy estimator is a Poisson random variable. Then, the firm could plug the estimators into (7) to solve them "empirically", obtaining estimators for * and * for = 1, . . . , . One would imagine that the estimators for * and * are not necessarily accurate. Indeed, the accuracy of such a procedure depends crucially on two aspects: 1. The length of the period during which the price is experimented. The longer the period, the less noisy the estimators for ( ) are.
2. The granularity of the experimented prices. The estimator for ( ) is based on a discrete set of prices. It inevitably incurs discretization error in order to solve a continuous optimization problem (7).
Ideally, to obtain accurate estimators for * and * , 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, ] 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 ( ). Then (7) is solved empirically to obtain point estimators for * and * . In the next phase, those point estimators are used to form interval estimators for * and * . 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 * with high probability.
At the beginning of phase +1, the firm constructs interval estimators based on the point estimators ( ) * ( ( ) * ) and pre-specified widthΔ ( +1) (Δ ( +1) ) for all : Note that the intervals are properly truncated by [ , ] and [0, ], and this is the only reason whȳ ). Then the procedure is repeated for phase + 1.
In the last phase, phase , the algorithm behaves differently after forming the interval estimators If so, then with high probability * = 0 and the capacity is sufficient. Therefore, the price * is the unconstrained maximizer of ( ), i.e., P (0), for all . As we will show in Section 3.3, the width of the interval estimator [ ( ) , ( ) ] is roughlyΔ ( ) ∼ −1/4 . Therefore, if the firm adheres to a constant price ∈ [ ( ) , ( ) ] for type-consumers, the relative revenue loss for type-consumers in phase (ignoring the random fluctuation of Poisson arrivals) is approximately where we rely on the concavity in Assumption 1 and the fact that * ∈ [ ( ) , ( ) ] with high probability. This meets the target regret in Section 2.2. Motivated by the argument above, the algorithm simply charges a constant price ( ) = ( ) + for type-consumers until the end of the season for a pre-specified parameter . Note that we slightly mark up the prices by a small adjustment ∼ −1/4 to guarantee that the inventory is sufficient when the inventory just meets the unconstrained optimal prices, i.e., = =1 ( * ). If the firm finds 0 ∉ [ ( ) , ( ) ] at the beginning of phase , which implies that * > 0 and the capacity is insufficient with high probability, then a different procedure has to be used in phase . The method for the case of * = 0 no longer works: because * is no longer the unconstrained maximizer of ( ), even for , * ∈ [ ( ) , ( ) ], we have This implies that a constant price in [ ( ) , ( ) ] for type-consumers will fail to meet the target regret. To address the problem, let = ( ) − and = ( ) + be conservative lower and upper bounds for * . It makes sure that * ∈ [ , ] along with buffers around the boundary. The buffer guarantees that the solution to the linear interpolation (14) below is stable. Let ( ) be the cumulative sales aggregated from all types of consumers up to time . The algorithm in phase is divided into the following four steps: 1. For ∈ ( , + (log ) − ], apply to type-consumers. Record the aggregate sales rate by Clearly, ( ) is an unbiased estimator for =1 ( ).
If the solution ∉ [0, 1] (which will be shown to have negligible probability), then we project it The goal of the above steps is to ensure the deviation of ( ) from is relatively small. In particular, from Lemma 8 in Section 4, the steps guarantee | ( ) − | ∼ −1/2 . Without further exploring the price space 5 the algorithm can still meet the target regret with a little exploration on the aggregate demand rate and by controlling the aggregate sales at . We will discuss this point in Section 5. The notations are summarized in Table 1 in the appendix. The detailed steps of the algorithm are demonstrated in Algorithm 1. Note that both "Input" and "Constant" are known to the firm, while "Parameters" are computed in Section 3.3.

Choice of Parameters
Let be a sufficiently small constant (independent of ). We set the following parameter values in Step 3: The choice of parameters guarantees that * ∈ [ ( ) , ( ) ] and * ∈ [ ( ) , ( ) ] occur with high probability. Moreover, at the beginning of phase , the precision of [ ( ) , ( ) Next we point out the connections to the algorithm in Wang et al. (2014). When the capacity is sufficient, then this algorithm is closely related to that in Wang et al. (2014): both target the precision −1/4 of the interval estimators for * , and our problem becomes independent learning problems in Wang et al. (2014). This is why the choices of ( ) , ( ) ,Δ ( ) and are almost identical to that of Wang et al. (2014) except for logarithmic terms. The design and analysis diverge for insufficient capacity. In order to track the dual variable, we construct interval estimators for , which is not needed in Wang et al. (2014). 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 Wang et al. (2014).

Analysis
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 P( ) = 1 − ( −1 ); its equivalence to P( ) = ( −1 ) should be clear in the context. Before proceeding, we introduce a modified stochastic system. Technically, if the inventory is depleted at , then ( ) must be switched to ∞ , a choke price at which the demand of type-consumers is turned off, for all . We use a similar simplification to Lei et al. (2017) and consider a slightly different problem. When the inventory is depleted, instead of forced to set ∞ for all types of consumers, the firm can still use prices between [ , ]. To accommodate the extra demand, it outsources the extra demand at a unit cost . Denote the expected revenue of this modified system by˜ . Because is higher than the price charged, we must have˜ ≤ . To bound − , it suffices to bound −˜ . Therefore, from now on, we investigate the pricing policy ( ) associated with the algorithm without switching to ∞ once the inventory is depleted.
Remark 3. The benefit of studying˜ instead of is that the pricing policy can be implemented for ∈ [0, ] without having to switch to ∞ at the stopping time at which the inventory is depleted. This simplifies the analysis.
We first show that the number of phases is growing slowly in .
We next show that the last phase takes the majority of the season.
Consider the following events which are measurable with respect to F : By design, and are the key to the success of the algorithm. If in some phase , the interval estimators [ ( ) , ( ) ] and [ ( ) , ( ) ] do not contain * and * , then (8) and (9) do not make sense any more. To make things worse, the optimal primal/dual pair ( * , * ) cannot be recovered in subsequent phases and the learning policy is doomed to fail. Therefore, we want to show that ∩ occurs with high probability. The event is also crucial. Note that to estimate * , the algorithm solves a discrete  Combining Lemma 3 and Lemma 4, we have the following lemma, which states that at the beginning of phase , the probability that the algorithm "goes wrong" is negligible.
The following two lemmas characterize the cumulative sales ( ) at = , the beginning of phase . Recall that the cumulative sales ( ) can be expressed as ∫ 0 =1 , ( ( ( ))). Therefore, ) ]. Also note that in the fluid model, the inventory level at is ( * ). 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 .
Lemma 6. At the beginning of phase , the conditional expectation of ( ) given the pricing policy ( ) satisfies Lemma 7. At the beginning of phase , ( ) satisfies Roughly speaking (ignoring the logarithmic terms), Lemma 6 and 7 show that the inventory level at the beginning of phase misses the target inventory level in the fluid system by 3/4 . This is consistent with the precision of the price interval at , which satisfiesΔ ( ) ∼ −1/4 .

Sufficient Capacity
We next bound the regret when * = 0, i.e., when the capacity is not constrained.
The major steps of the proof are sketched below. We first express The first term is the expected revenue generated in each phase, and the second term accounts for the outsourcing cost explained in Remark 3. Moreover, can be expressed as =1 E ∫ +1 * ( * ) .
Thus, the difference between and the first term of (15) can thus be bounded by Because * is the unconstrained maximizer of ( ), we can apply a quadratic bound in the second line by Assumption 1. The last line follows from the high-probability event , which implies that | ( ) − * | ≤Δ ( ) in phase ≤ − 1. At the beginning of phase , we can show that Step 21 is triggered with high probability. In this case, | ( ) − * | = | ( ) − * | = | ( ) − * + | ≤Δ ( ) + is not necessarily bounded byΔ ( ) . However, is chosen carefully to match the order ofΔ ( ) . By the choice of the parameters, the order of =1 ( ) (Δ ( ) ) 2 is ((log ) 2+16 1/2 ).
To bound the second term of (15), we show that the mean of the total sales over the horizon, E =1 ∫ 0 ( ( )) , does not exceed . This is achieved by charging a markup ( ) = ( ) + in phase and this is exactly the purpose of introducing . Since the random fluctuation of Poisson arrivals is bounded by ( 1/2 ), we obtain the regret stated in Proposition 2.

Insufficient Capacity
When * > 0, the inventory is depleted at in the fluid system. We first show that the cumulative sales at the end of the horizon under the algorithm misses the target by ( 1/2 ). and The intuition behind the proof is explained below. We first show that ( ) and ( ) estimate Note that regardless of the first − 1 phases, the remaining inventory is − ( ) at . Using ( ) for a fraction (1 − ) of phase serves as a corrective force to ensure the aggregate sales over the horizon to be close to (the error bound (log ) 1/2 is caused by the random fluctuation of the Poisson arrivals).
Algorithm 1 does not explore the price space in phase , and thus the precision of and in Step 26 is of order −1/4 . Therefore, one would expect the sales to type-consumers miss the target ( * ) by −1/4 × = 3/4 . This is indeed the case. However, Lemma 8 guarantees that a simple exploration (Step 28, 32 and 35) is effective and leads to higher precision ( ( 1/2 ) for the aggregate sales of all types of consumers. This is crucial to the proof of the next proposition.
Combining Proposition 2 and Proposition 3 and recalling that can be an arbitrarily small constant, we obtain the main theorem.
Theorem 1. Suppose Assumptions 1 and 2 hold. For any > 0, we can select such that the regret of the primal-dual learning algorithm satisfies where the constant is independent of .
By Besbes and Zeevi (2009), no learning policy can achieve regret that grows slower than −1/2 with = 1. Therefore, ignoring the logarithmic terms, the primal-dual learning algorithm achieves near-optimal regret.

Discussion
In this section, we discuss several salient features of the primal-dual learning algorithm and clarify our findings in comparison to the literature.

The Fundamental Limit of Online Learning
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 Slivkins (2014): for a general Lipschitz-continuous objective function with a -dimensional decision vector without resource constraints, the optimal rate of regret is −1/(2+ ) . (2019) show that when the objective function is locally concave, then the optimal rate is slightly better, and may be adjusted to −2/(3+ ) . The number of decisions is the number of products in network dynamic pricing, or in this paper. Note that setting = 1 recovers the rate −1/2 in dynamic pricing (one product with one constraint) (Besbes and Zeevi, 2009;Wang et al., 2014). This is not good news: as the number of products increases, the rate deteriorates dramatically, which is referred to as the curse of dimensionality. It is also consistent with the finding in Besbes and Zeevi (2012). 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 (Badanidiyuru et al., 2013;Agrawal and Devanur, 2014;Ferreira et al., 2018) does not apply to our setting. (2019) design a learning algorithm for network dynamic pricing that achieves rate −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 (Slivkins, 2014) and network dynamic pricing what property makes the latter easier to learn? Li et al. (2019) and references there in reveal that it may be due to the intrinsic concavity structure of network dynamic pricing. In particular, Li et al. (2019) show that in the setting of Slivkins (2014), if the objective function is concave, then the regret is dimension-free ( −1/2 ), because one can resort to gradient-based algorithms. In network dynamic pricing, Assumption 1 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.

Some recent papers have shed new light on this fundamental problem. Chen and Shi
This opens up a new research question: can the −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 −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 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 independent learning problems with one decision variable, i.e., ( −1/2 ). It doesn't lead to dimension-free regret automatically when the constraint is binding, as the -dimensional decision variables can be regarded as a vector on a ( − 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 5.3. Therefore, our result confirms that −1/2 may be achievable. Moreover, we provide the first dimension-free algorithm that is not gradient-based in the context.

Learning in the Primal and Dual Spaces
The algorithm provides point and interval estimators for both the primal and dual optimal solutions, * and * , 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 Besbes and Zeevi 2012). This is not surprising given the primal-dual formulation in Section 2.1 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 * helps to decouple the problem into independent learning problems of the form max ( ) ( − * ) for = 1, . . . , . These independent learning problems are known to have regret ( −1/2 ) (the parametric version of such problems is solved in Keskin and Zeevi 2014; den Boer and Zwart 2014). However, * 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.

Multiple Resource Constraints
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 5.1. Next we briefly introduce the extension to multiple resources.
Suppose there are resources, with initial capacity = ( 1 , . . . , ), and product consumes units of resource . The Lagrangian (3) can be reformulated as For a fixed we define . and the dual function As for the implementation of the algorithm, the exploration of the first −1 phases is essentially the same (Step 5 to Step 14). When finding the point estimator for ( ) * , Equation (8) is vectorized, and the optimal vector ( ) * is obtained by testing the grid in the confidence set of , which is a hyper-rectangle since each entry of has a confidence interval. Normally the grid size explodes exponentially in the size of , i.e., , and this is precisely causing the curse of dimensionality. However, in this algorithm (8) 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 −1/4 , similar to (11), under properly chosen parameters. For products with sufficient capacity (a product enjoys sufficient capacity if 0 ∈ [ ( ) ,¯ ( ) ] for all such that > 0), this already leads to the optimal regret. For products with insufficient capacity, it is unclear how the linear interpolation (14) can be implemented in the high dimension. We thus leave the algorithm and regret analysis in this case for future research.

Controlling the Aggregate Sales
As explained in Section 3.2 and the remark following Proposition 3, when * > 0, the interval estimators for * at the beginning of phase are still too wide ( −1/4 ). Instead of exploring the price space further and attempting to narrow down the intervals in phase , the algorithm simply controls the aggregate sales within an error margin of 1/2 (Step 25 to 40 in Algorithm 1 and Lemma 8). Focusing on a single quantity (the aggregate sales) turns out much easier than controlling decision variables. In fact, we suspect that no learning policy could estimate all * with precision −1/2 at the end of the horizon 6 .
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 3. In particular, the derivatives of the revenue rates −1 ( ) with respect to the demand rate are all equal to * at optimality = ( * ) for = 1, . . . , . This allows the firm to control the regret by the deviation of the aggregate sales.

Data Reuse
Across different phases, the interval estimators for the optimal price * may overlap for some . In this case, the demand estimated at certain prices in the previous phases may be reused. For example, if [ ( ) , ( ) ] and [ ( +1) , ( +1) ] overlap, then for some 1 and 2 the price grid points ( ) , 1 and ( +1) , 2 may be close, and the demand estimate for ( ) , 1 can provide useful information for ( +1) , 2 . 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.

Discontinuous Demand
In a recent paper, den Boer and Keskin (2020) 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 1 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 ( = 1); we normalize the time horizon ( = 1) and there is sufficient capacity ( = 100). Let the price range be ∈ [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 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 ( √ ). Since can be arbitrarily large, the regret cannot possibly be controlled.
Appendix A Table of  The dual optimal solution on the primal/dual grids using the empirical estimates for (·) ( ) * The primal optimal solution on the price grids using the dual variable ( ) * and the empirical estimates for (·) , (

Appendix B Proofs
We first provide two lemmas and their proofs that will be used repeatedly in the proof of the main result.
Proof of Lemma 9: The result follows from the following bound for Poisson tail probabilities: Let be a Poisson random variable with mean . Then for any > 0, we have For a proof, see, e.g., Canonne (2017). To prove Lemma 9, letting = and = and we have Because grows polynomially in , we have lim →∞ = 0. Therefore, there exists a constant 1 that only depends on , , and , such that for ≥ 1 It is clear that for any > 0, the decay of the above term is faster than − . Therefore, we can always find such a constant .
Lemma 10. Suppose is a Poisson random variable with mean , then we have Proof of Lemma 10. Note that Var( ) = . Applying the Cauchy-Schwartz inequality, we have This completes the proof.
Because (·) is concave with a second-order derivative bounded above by − 3 < 0 by Assumption 1, −1 is decreasing whose first-order derivative is bounded above by [− 4 , − 3 ]. This implies that (·) is strictly decreasing in whose first-order derivative is bounded below by −1/ 3 . Thus, we conclude that P ( ) is strictly increasing and the derivative is bounded.
Part two follows from the envelop theorem and the fact that (·) is strictly decreasing by Assumption 1 and the proof of part one.
For part three, note that ( ) = + =1 R ( ). Since R ( ) is twice differentiable and convex by part two, the claim follows.
For part four, note that the objective function is concave and the constraint is linear in ( ( )). Therefore, Slater's condition implies strong duality and complementary slackness. The proofs can also be found in Gallego et al. (2019).
Substituting it into Lemma 7, it suffices to show is ((log ) 2 −1/2 ). By the triangle inequality and the union bound, we have The second term is ((log ) 2 / ) shown by Lemma 6. The first term can be bounded by where the last inequality follows from Chebyshev's inequality. Now note that conditional on F , ( ) for ∈ ( , +1 ] is measurable and thus ∫ +1 , ( ( ( ))) is a Poisson random variable with mean ∫ +1 ( ( )) . Therefore, by Assumption 1. Thus, the first term of (34) can be bounded by when (log ) 16 > 1 . This completes the proof.
Proof of Proposition 2: The total revenue˜ can be expressed as the sales revenue minus the outsourcing cost: where we use˜ , to denote the revenue earned in phase (ignoring the inventory constraint). First note that The second inequality follows from P( ) = ((log ) 2 −1 ) by Lemma 5, the tower property and the fact that ∈ F . The last bound is due to the fact that E ˜ , F is the mean of a Poisson random variable which is bounded above by 1 ( ) .
The second inequality follows from a similar argument below (36). Therefore, adding up (37) for all − 1 phases and (38), we have obtained that From (35), it remains to bound E The first inequality is due to ≥ =1 ( * ). The second inequality is due to . In the third inequality we replace ( * ) by ( ( ) ) and use the bound derived before. Note that conditional on F , , ( ( ( ) )) is a Poisson process with rate ( ( ) ). Therefore, for a sufficiently large (we require (log ) > 4 2 / below) The first inequality is due to the fact that 2 3/4 (log ) 1+8 − −1 2 (log ) 1+9 3/4 ( ) ≤ 0 for (log ) > 4 2 / and by ( ) > /2 from Lemma 2. The second line is due to the tower property. The third line follows from Lemma 10. Combining the above result with (39) and (35), we have proved Proposition 2.
This completes the proof.