Dynamic Pricing and Learning under the Bass Model

The dynamic pricing and learning literature, often referred to as “learning and earning,” has at its focal point the objective of maximizing revenues jointly with inferring the structure of a demand model that is a priori not known to the decision maker. It is an extremely active area of current research that can essentially be traced back to two strands of work. Within the computer science community, the first paper on the topic is [26] that studies a posted price auction with infinite inventory in which the seller does not know the willingness-to-pay (or valuation) of buyers and must learn it over repeated interactions. The problem is stateless, and demand is independent from period to period; as such, it is amenable to a multi-armed bandit-type approach and in fact can be solved near-optimally (in the sense of regret bounds) using an “explore-first-exploit-later” pricing and learning strategy. Various refinements and improvements have been proposed since in what has become a very active field of study in economics, computer science and operations research. The second strand of work originates in the operations research community [7] which focuses on the same finite horizon regret criteria in the posted-price auction problem but with limited inventory. This problem is sometimes referenced as “bandits with knapsacks” due to the follow up work of [2] and subsequent papers. In that problem, the learning objective is more subtle as the system “state” is changing over time (in the dynamic programming full information solution, this state is given by the level of remaining inventory and time). For further references and historical notes on the development of the topic see, e.g., the recent survey [9].

Most of the literature that has evolved from the inception points identified above has focused on a relatively simple setting where given current pricing decision, demand is independent of past actions and demand values. In addition, much of the literature has focused on the “stateless” problem setting, which provides further simplification and tractability. With the evolution of online platforms and marketplaces, the focus on such homogeneous modeling environments is becoming increasingly less realistic. For example, platforms now rely more and more on online reviews and ratings to inform and guide consumers. Product quality information is also increasingly available on online blogs, discussion forums, and social networks, that create further word-of-mouth effects. One clear implication on the dynamic pricing and learning problem is that the demand environment can no longer assumed to be static, meaning the demand model may change from one time instance to the next; for example, in the context of online reviews, sales of the product trigger reviews/ratings, and these in turn influence subsequent demand behavior etc.

While it is possible to model demand shifts and non-stationarities in a reasonably flexible (nonparametric) manner within the dynamic pricing and learning problem (see, e.g., [25], and [6] for a general MAB formulation), this approach can be too broad and unstructured to be effective in practical dynamic pricing settings. To that end, product diffusion models, such as the popular Bass model [3, 4], are known to be extremely robust and parsimonious, capturing aforementioned word-of-mouth and imitation effects on the growth in sales of a new product. The Bass diffusion model, originally proposed by Frank Bass in 1969 [3] has been extremely influential in marketing and management science, often described as one of the most celebrated empirical generalizations in marketing. It describes the process by which new products get adopted as an interaction between existing users and potential new users. The Bass model is attractive insofar as it creates a state-dependent evolution of market response which is well aligned with the impact of recent technological developments, such as online review platforms, on the customer purchase behavior. To that end, several recent empirical studies in marketing science and econometrics utilize abundant social data from online platforms to quantify the impact of word-of-mouth effect on consumer purchase behaviors and a new product diffusion process (e.g., [34, 14, 16, 19, 23, 36], also see [15, 29] for literature surveys).

Motivated by these observations, the objective of this paper is to investigate a novel formulation of the the dynamic pricing and demand learning problem, where the evolution of demand is governed by the Bass diffusion model, and where the parameters of this model are unknown a priori and need to be learned from repeated interactions with the market.

The Bass diffusion model [3, 4] has two parameters: the “coefficient of innovation” representing external influence or advertising effect; and the “coefficient of imitation” representing internal influence or word-of-mouth effect. The principle on which we incorporate this model is that “the probability of adopting by those who have not yet adopted is a linear function of those who had previously adopted.” More precisely, the likelihood that a potential buyer buys a new item at time $t$, given that he or she has not yet bought it, is a linear function of the proportion of buyers at time $t$:

where $F(t)$ and $f(t)$ are the distribution and density functions of first-purchase times, respectively. Here, the parameter $\alpha$ is the above referenced “coefficient of innovation”, and $\beta$ is the “coefficient of imitation.” Let $m$ be the number of potential buyers, i.e., the market size, and let $X_{t}$ be fraction of customers who has already adopted the product until time $t$. Then, $mX_{t}=mF(t)$ represents the cumulative sales (aka adoptions) up until time $t$, and $m(1-X_{t})$ is the size of remaining market yet to be captured. The instantaneous sales at time $t$, $m\frac{dX_{t}}{dt}=mf(t)$ can then be expressed as

A generalization of the Bass diffusion model that can be harnessed for the dynamic pricing context was proposed by Robinson and Lakhani [32]. In the latter model, $p_{t}$ denotes the price posted at time $t$. Then, given previous adoption level $X_{t}$ the number of new adoptions at time instant $t$ is given by

Thus, the current price affects not only the immediate new adoptions and revenue, but also future adoptions due to its dependence on the adoption level $X_{t}$, which essentially forms the state at time $t$ in this stateful demand model. Finding a revenue-maximizing optimal pricing trajectory in such a dynamic demand model is non-trivial even when the model parameters are known, e.g., see [17] for some characterizations.

In this paper, we consider a stochastic variant of the above Bass model, where customers arrive sequentially and the number of customer arrivals (aka adoptions) $d_{t}$ until time $t$ is a non-homogeneous Poisson process with rate $\lambda_{t}$ given by the right hand side of (3). More details on the stochastic model are provided in Section 2 where we describe the full problem formulation and performance objectives.

The problem of dynamic pricing under demand learning can then be described, informally, as follows: the learner (seller) is required to dynamically choose prices $\{p_{t}\}$ to be posted at time $t\in[0,T]$, where $p_{t}$ is chosen based on the past observations that include the number of customers arrived so far, their times of arrival, and the price decisions made in the past. The number of customers $d_{t}$ arriving until any time $t$ is given by the stochastic Bass model. Note that we use the term “customer arrival” and “customer adoption” interchangeably to mean the same thing, i.e., every customer arriving at time $t$ adopts the product and pays the price $p_{t}$. We assume that the size of the market $m$ and the horizon $T$ are known to the learner, but the Bass model parameters $\alpha,\beta$ (i.e., coefficient of innovation and coefficient of imitation) are unknown. The aim is to maximize the cumulative revenue over the horizon $T$, i.e.,$\sum_{d=1}^{d_{T}}p_{d}$ via a suitable sequence of prices, where $p_{d}$ is the price paid by the $d^{th}$ customer and $d_{T}$ is the total number of adopters until time $T$. In essence, we will not be directly maximizing this quantity but rather, and much in line with the online learning and multi-armed bandits literature, will focus on evaluating a suitable notion of regret and establishing “good” regret performance of our proposed pricing and learning algorithm.

The paper makes two significant advances in the study of the aforementioned Bass model learning and earning problem. First, we present a learning and pricing algorithm that achieves a high probability $\tilde{O}\left(m^{2/3}\right)$ regret bound. Second, under certain mild restrictions on algorithm design, we provide a matching lower bound, showing that any algorithm must incur order $\Omega(m^{2/3})$ regret for this problem. The precise statements of these results are provided as Theorem 4.1 and Theorem 5.1, in Section 4 and 5 respectively. Hence the “price” of incomplete information and the “cost” of learning it on the fly, are reasonably small. Unlike most regret analysis results, in the present setting the market size $m$ is the fundamental driver of the problem complexity; our lower bound, in fact, indicates that for any fixed $\alpha,\beta$, most non-trivial instances of the problem have constant $T$ and large $m$. This is also reflected in the regret of our algorithm which depends sublinearly on market size $m$, and only logarithmically on the time horizon $T$. This insight sets the problem of dynamic pricing under Bass model uniquely apart from the typical i.i.d. and multi-armed bandit-based models for dynamic pricing.

Several other models of non-stationary demand have been considered in recent literature on dynamic pricing and demand learning. [10] studies an additive demand model where the market condition is determined by the sum of an unknown market process and an adjustment term that is a known function of the price. The paper numerically studies several sliding window and weight decay based algorithms, including one experiment where their pricing strategy is tested on the Bass diffusion model. However, they do not provide any regret guarantees under the Bass model. [8] and [13] consider the pricing problem under a piece-wise stationary demand model. [25] consider a two-parametric linear demand model whose parameters are indexed by time, and the total quadratic variation of the parameters are bounded. Many of the existing dynamic pricing and learning algorithms borrow ideas from related settings in multi-armed bandit literature. [21] and [11] study piecewise stationary bandits based on sliding window and change point detection techniques. [6, 33] and [30] study regret based on an appropriate measure of reward variation. In rested and restless bandits literature, [35] and [5] also study a related problem where the reward distribution depends on the state which follows an unknown underlying stochastic process. However, the above-mentioned models of non-stationarity are typically very broad and unstructured, and fundamentally different from the stateful structured Bass diffusion model studied here.

There is also much recent work on learning and regret minimization in stateful models using general MDP and reinforcement learning frameworks (for example [37, 1, 24]). However, these results typically rely on having settings where each state can be visited many times over the learning process. This is ensured either because of an episodic MDP setting (e.g., [37]), or through an assumption of communicating or weakly communicating MDP with bounded diameter, i.e., a bound on the number of steps to visit any state from any starting state under the optimal policy (e.g., see [24, 1]). Our setting is non-episodic, and every state is transient – the state is described by the number of cumulative adopters so far and the remaining time, both of which can only move in one direction. Therefore, the results in the above and related papers on learning general MDPs are not applicable to our problem setting.

In the marketing literature, there is significant work on using the Bass model to forecast demand before launching a product. Stochastic variants of Bass model have also been considered previously, e.g., in [22, 31]. In addition to the work mentioned in the introduction, [28, 20, 38, 22] present empirical methods for using historical data from similar products or from past years to estimate Bass model parameters, in order to obtain reliable forecasts. In this context, we believe our proposed dynamic pricing and learning algorithm may provide an efficient method for adaptively estimating the Bass model parameters while optimizing revenue. However, the focus of this paper is on providing theoretical performance guarantees; the empirical performance of the proposed method has not been studied.

The work most closely related to ours is a parallel recent paper by [39]. In [39], the authors consider a dynamic pricing problem under a similar stochastic Bass model setting as the one studied here. They propose an algorithm based on Maximum Likelihood Estimation (MLE) that is claimed to achieve a logarithmic regret bound of $\tilde{O}(\log(mT))$. At first glance this regret bound seems to contradict our lower bound¹¹1Technically our lower bound only holds for algorithms that satisfy certain conditions (Assumption 1 and 2) stated in Section 5. However, we believe it is still applicable to the algorithm in [39]. Their algorithm with its constant upper bound on prices seems to satisfy both of our assumptions. of $\Omega(m^{2/3})$. However, it appears the results in [39] may have some mistakes (see, in particular, the current statement and proofs of Lemma 3, Theorem 5 and Theorem 6 in [39] which we believe contain the aforementioned inconsistencies). To the best of our understanding, these inconsistencies cannot be fixed without changing the current results in a significant way.

There is an unlimited supply of durable goods of a single type to be sold in a market with $m$ customers. We consider a dynamic pricing problem with sequential customer arrivals over a time interval $[0,T]$. We denote by $d_{t}$, the number of arrivals by time $t$; with $d_{0}=0$. At any given time $t$, the seller observes $d_{t}$, the number of arrivals so far as well as their arrival times $\{\tau_{1},\tau_{2},\dots,\tau_{d_{t}}\}$, and chooses a new price $p_{t}$ to be posted for times $t^{\prime}>t$. The seller can use the past information to update the price any number of times until the end of time horizon $T$. As mentioned earlier, in our formulation a customer arriving at time $t$ immediately adopts the product and pays the posted price $p_{t}$, and therefore the terms “adoption” and “arrival” are used interchangeably throughout the text.

The customer arrival process for any pricing policy is given by a stochastic Bass diffusion model with (unknown) parameters $\alpha,\beta$. In this model, number of arrivals $d_{t}$ by time $t$ is a non-homogeneous Poisson point process ²²2 A counting process $\{d_{t},t\geq 0\}$ is called a non-homogeneous Poisson process with rate $\lambda_{t}$ if all the following conditions hold: (a) $d_{0}=0$; (b) $d_{t}$ has independent increments; (c) for any $t\geq 0$ we have $\Pr(d_{t+\delta}-d_{t}=0)=1-\lambda_{t}\delta+o(\delta)$, $\Pr(d_{t+\delta}-d_{t}=1)=\lambda_{t}\delta+o(\delta)$, $\Pr(d_{t+\delta}-d_{t}\geq 2)=o(\delta)$. with rate $\lambda_{t}$ given by (3), the adoption rate in deterministic Bass diffusion model [32]. That is,

where $X_{t}=d_{t}/m$. For convenience of notation, we define function

so that $\lambda_{t}=\lambda(p_{t},X_{t})$, with $X_{t}=d_{t}/m$.

The seller’s total revenue is simply the sum of the prices paid by the customers who arrived before time $T$, under the dynamic pricing algorithm used by the seller. We denote by $p_{d}$, the price paid by $d^{th}$ customer, i.e., $p_{d}=p_{\tau_{d}}$. Then, the revenue over $[0,T]$ is given by:

The optimal dynamic pricing policy is defined as the one that maximizes the total expected revenue $E[\text{Rev}(T)]$. We denote by $V^{\text{stoch}}(T)$, the total expected revenue under the optimal dynamic pricing policy. Then, regret is defined as the difference between the optimal expected revenue $V^{\text{stoch}}(T)$ and seller’s revenue, i.e.,

In this paper, we aim to provide a dynamic learning and pricing algorithm with a high probability upper bound of $\tilde{O}(m^{2/3})$ on regret, as well as a closely matching lower bound. Instead of analyzing the regret directly, we define a notion of “pseudo-regret,” which measures regret against the optimal revenue under the deterministic Bass model ($V^{\text{det}}(T)$). This is useful because as we will show later in (6), there is a simple expression for the optimal prices in the deterministic Bass model. This can be leveraged using a fluid model approach, widely used in the analysis of stochastic systems, which targets a deterministic “skeleton” as a stepping stone toward developing insights for policy design and complexity drivers. Later, we show more formally that the pseudo-regret upper bounds the regret measure $\text{Regret}(T)$, defined earlier, and further is within $\tilde{O}(\sqrt{m})$ of $\text{Regret}(T)$. This justifies our focus on the pseudo-regret for both the purpose of developing lower bounds, as well as analysis and upper bounds on policy performance.

Next, we discuss the expressions for optimal pricing policy and optimal revenue under the deterministic Bass model, and use those to define the notion of pseudo-regret.

Recall (refer to introduction) that the adoption process under the deterministic Bass model is described as follows: given the current adoption level $X_{t}$ and price $p_{t}$ at time $t$, the new adoptions are generated deterministically with rate ³³3A subtle but important difference between this deterministic model vs. the stochastic Bass model introduced earlier is that in the deterministic model, the increment $mdX_{t}$ in adoptions is fractional. On the other hand, in our stochastic model, the number of customer arrivals (or adoptions) $d_{t}$ is a counting process with discrete increments. This difference will be taken into account later when we compare our pseudo-regret to the original definition of regret.

The optimal price curve for the deterministic Bass model is then defined as the price trajectory $\{p_{t}\}$ that maximizes the total revenue $m\int_{0}^{T}p_{t}dX_{t}$ under the above adoption process. We denote by $V^{\text{det}}(T)$ the total revenue under the optimal price curve.

An analytic expression for the optimal price curve under the deterministic Bass model is in fact known. It can be derived using optimal control theory (see Equation (8) of [17]). For a Bass model with parameters $\alpha,\beta$, horizon $T$, and initial adoption level $0$, the price at adoption level $x$ in the optimal price curve is given by the following expression:

where $X^{*}_{T}$, the adoption level at the end of horizon $T$, is given by the following equations:

For completeness, a derivation of the above expression of $X^{*}_{T}$ is included in Appendix B. Using the above notation for optimal price curve, we can write $V^{\text{det}}(T)$, the optimal total revenue, as:

We define pseudo-regret as the difference between $V^{\text{det}}(T)$, the optimal total revenue in the deterministic Bass model, and the algorithm’s total revenue $\text{Rev}(T)$. That is,

Essentially, pseduo-regret replaces the benchmark of stochastic optimal revenue $V^{\text{stoch}}(T)$ used in the regret definition by deterministic optimal revenue $V^{\text{det}}(T)$. We show that in fact the deterministic optimal revenue is a stronger benchmark, in the sense that it is always larger than the stochastic optimal revenue. Furthermore, we show that it is within $\tilde{O}(\sqrt{m})$ of the stochastic optimal revenue. To prove this relation between the two benchmarks we demonstrate a concavity property of deterministic optimal revenue which is crucial for our results. Specifically, we define an expanded notation $V^{\text{det}}(x,T)$ as the deterministic optimal revenue starting from adoption level $x$ and remaining time $T$. Note that $V^{\text{det}}(T)=V^{\text{det}}(0,T)$. Then, we show that $V^{\text{det}}(x,T)$ is concave in $x$ for any $T$, and any market parameters $m,\alpha,\beta$. More precisely, we prove the following key lemma.

Using these observations, we can prove the following relation between $\text{Pseudo-Regret}(T)$ and $\text{Regret}(T)$; all proofs can be found in the appendix.

Throughout the paper, if a potentially fractional number (like $mX^{*}_{T}$, $m^{2/3}$, $\gamma m$ etc.) is used as a whole number (for example as number of customers or as boundary of a discrete sum) without a floor or ceiling operation, the reader should assume that it is rounded down to its nearest integer.

Our algorithm is provided, as input, the market size $m$, and a constant upper bound $\phi$ on $\alpha+\beta$. For many applications, it is reasonable to assume that $\alpha+\beta\leq 1$, i.e., $\phi=1$, but we allow for more general settings. The market parameters $\alpha,\beta$ are unknown to the algorithm.

The algorithm alternates between using a low “exploratory” price aimed at observing demand in order to improve the estimates of model parameters, and using (a lower confidence bound on) the deterministic optimal prices for the estimated market parameters. Setting the exploratory price $p_{0}$ as $0$ suffices for our analysis, but more generally it can be set as any lower bound on the deterministic optimal prices, i.e., we just need $0\leq p_{0}\leq p^{*}(x,\alpha,\beta),\ \forall x$. Using a non-zero exploratory price could be better in practice.

Our algorithm changes price only on arrival of a new customer, and holds the price constant in between two arrivals. The prices are set as follows. The algorithm starts with using an exploratory price $p_{0}$ for the first $\gamma m$ customers, where $\gamma=m^{-1/3}$. The prices $p_{1},\ldots,p_{\gamma m}$ and the observed arrival times $\tau_{1},\ldots,\tau_{\gamma m}$ for the first $\gamma m$ customers are then used to obtain an estimation of $\alpha$, and a high probability error bound $A$ on this estimate. The estimate of parameter $\alpha$ is not updated in subsequent time steps. The algorithm then proceeds in epochs $i=1,2,\ldots K$. Let $\gamma_{i}=2^{i}\gamma$. Epoch $i$ starts right after customer $\gamma_{i}m$ arrives and ends either when customer $2\gamma_{i}m$ arrives, or when we reach the end of the planning horizon $T$. In the beginning of each epoch $i$, the exploratory price $p_{0}$ is again offered for the first $\gamma m$ customers in that epoch. The arrival times observed from these customers are used to update the estimate of the $\beta$ parameter and its’ high probability error bound $B_{i}$. For the remaining customers in epoch $i$, the algorithm offers a lower confidence bound $\underline{p_{i}}$ on the deterministic optimal price $p^{*}\left(\frac{d-1}{m},\alpha,\beta\right)$ computed using the current estimates of $\alpha,\beta$ and their error bounds.

Since our algorithm fixes prices between two arrivals, the arrival rate of the (Poisson) adoption process is constant in between arrivals, which in turn implies that the inter-arrival times are exponential random variables. This greatly simplifies the estimation procedure for $\alpha,\beta$, which we describe next.

Estimates $\hat{\alpha}$, and $\hat{\beta}_{i}$ for every epoch $i$ are calculated using the following equations which match the observed inter-arrival times to the expected value of the corresponding exponential random variables:

Also, we define

Then, using concentration results for exponential random variables, we can show that the error in estimates $\hat{\alpha}$ and $\hat{\beta}_{i}$ are bounded $A$ and $B_{i}$ respectively. Specifically, we prove the following result. The proof is in Appendix D.

Note that only the estimate and error bounds ($\hat{\beta}_{i}$ and $B_{i}$) for the parameter $\beta$ are updated in every epoch. The estimate and error bound ($\hat{\alpha}$ and $A$) for $\alpha$ is computed once in the beginning and remains fixed throughout the algorithm. Given $\hat{\alpha},A,\hat{\beta}_{i}B_{i}$, we define the price $\underline{p_{i}}(d/m)$ to be used by the algorithm in epoch $i$ as follows. For any $d\leq m$,

Here $p^{*}(\cdot,\cdot,\cdot)$ is the optimal deterministic price curve as given by (6). In above, we clamped the price to the range $[0,\log(e+\phi T)]$. That is, if the computed price is less than $0$ we set $\underline{p_{i}}$ to $0$; and if it is above $\log(e+\phi T)$, which is an upper bound on the optimal price (proven later in Lemma 4.4), we set $\underline{p_{i}}$ equal to this upper bound.

Later in Lemma 4.1, we show that the quantities $L_{\alpha},L_{\beta i}$ play the role of Lipschitz constants for the optimal price curve: they provide high probability upper bounds on the derivatives of the optimal price curve with respect to $\alpha,\beta$ respectively. Consequently (in Corollary 4.1), we can show that with high probability the price defined in (13) will be lower than the corresponding deterministic optimal price. The reason that the algorithm uses a lower confidence bound on the optimal price is that we want to acquire at least as many customers in time $T$ as the optimal trajectory. The intuition here is that losing customers (and the entire revenue associated with those customers) can cost a lot more than losing a little bit of revenue from each customer.

Our algorithm is described in detail as Algorithm 1.

We first give an intuitive explanation for why our algorithm works well. As mentioned earlier in the introductory sections, there is a simple closed form expression for the optimal prices in the deterministic model for any $\alpha,\beta,T$ (see (6)–(8)). Moreover, the definition of pseudo-regret and Lemma 2.2 allows us to replace the stochastic optimal revenue $V^{\text{stoch}}(T)$ with the deterministic optimal revenue $V^{\text{det}}(T)$. Our algorithmic strategy is then to follow (an estimate of) the deterministic optimal price trajectory, and show that the resulting revenue is close to the deterministic optimal revenue with high probability.

To prove this, we show that the prices $\underline{p_{i}}$ used by our algorithm were set so that they lower bound the deterministic optimal price with high probability. Intuitively, using a lower price would ensure that the algorithm sees at least as many as optimal number of customer adoptions in horizon $T$, so that the gap in revenue can be bounded simply by the gap in prices paid by those customers. The final piece of the puzzle is to show that we can learn or estimate $\alpha,\beta$ at a fast enough rate so that the estimated prices are increasingly close to the optimal price and we do not lose too much revenue from learning.

In the remainder of this section we outline the proof of Theorem 4.1 in four steps. All the missing proofs from this section can be found in Appendix D.

In Lemma 3.1 we provided a high probability upper bound on the estimation error in $\alpha,\beta$ in each epoch of the algorithm. Using these error bounds and the definition of price $\underline{p_{i}}$ in (13), we can show that the prices offered by the algorithm are close to optimal and lower bound the corresponding optimal price with high probability. Specifically, we prove the following result.

From the expressions of $A$ (error bound for $\hat{\alpha}$) vs. $B_{i}$ (error bound for $\hat{\beta}_{i}$ in epoch $i$) in (12), observe that $A=\tilde{O}(m^{-1/3})$ and $B_{i}=\tilde{O}(\frac{1}{\gamma_{i}}m^{-1/3})$. Therefore, the estimation of $\beta$ is the bottleneck here: it has an extra $\frac{1}{\gamma_{i}}$ factor in the error bound. This is because the imitation factor $\beta$ is multiplied with the current adoption level in the definition of the Bass model (see (2)). This means that the estimation error on $\beta$ is likely to be large when the adoption level is low. This is why the algorithm needs to keep updating the estimate of $\beta$ in each epoch but not $\alpha$.

The above lemma and the definition of $\underline{p_{i}}$ immediately implies the following.

Using the fact that there are $\gamma_{i}m$ customers in epoch $i$, and the price difference bound in Lemma 4.1 in Step 1, we can show that we lose at most $\tilde{O}\left(\gamma_{i}m\left(L_{\alpha}m^{-1/3}+L_{\beta i}\frac{1}{\gamma_{i}}m^{-1/3}\right)\right)=$ $\tilde{O}\left(m^{2/3}\right)$ revenue per epoch. This loss bound per epoch is when compared to the optimal revenue earned from the same $\gamma_{i}m$ customers, assuming that the stochastic trajectory is given as much time as needed to reach the same number of customers. More precisely, let $\text{Rev}_{i}$ denote the algorithm’s revenue from the $(2\gamma_{i}m\wedge mX^{*}_{T})-\gamma_{i}m$ customers in an epoch $i$ completed by the algorithm, and $V^{\text{det}}_{i}$ denote the potential revenue from those customers if they paid the deterministic optimal price instead. Then, we prove the following bound.

In the previous step, we upper bounded the potential revenue loss for the $\gamma_{i}m$ customers that arrive in any epoch $i$ of the algorithm. However it is possible that the algorithm reaches the end of time horizon $T$ early and never even get to observe some customers, i.e. $d_{T}<X^{*}_{T}m$. In that case the algorithm would incur an additional regret due to fewer adoptions. Therefore, we need to show that our total number of adoptions in time $T$ cannot be much lower than that in the optimal trajectory. To show this, we use the observation made in Step 1 that in each epoch the algorithm offered a lower confidence bound on the optimal prices (note that the exploration price $p_{0}=0$ is always a lower bound on the optimal prices). Due to the use of lower prices, we can show that with high probability our final number of adoptions can be at most $\tilde{O}(\sqrt{m})$ below the optimal number of adoptions in the deterministic Bass model. Further, we can prove an $O(\log(T))$ upper bound on the optimal price, which allows us to easily bound the revenue loss that may result from the small gap in number of adoptions. Lemma 4.3 and Lemma 4.4 make these results precise.

These two results combined tell us that, compared to the optimal, we lose at most $\tilde{O}(\sqrt{m}\log(T))$ revenue due to fewer adoptions. The dominant term in regret comes from the seller losing roughly $\tilde{O}(m^{-1/3})$ revenue on each customer, which led to $\tilde{O}(m^{2/3})$ revenue loss per epoch in Step 2.

Finally, we put the previous steps together to prove Theorem 4.1. Since the number of customers in each epoch grows geometrically and there are at most $m$ customers in total, the number of epochs is bounded by $O(\log(m))$. By Step 2, the algorithm loses at most $\approx m^{2/3}$ revenue on adoptions in each epoch. By Step 3, it loses at most $\approx\sqrt{m}\log(T)$ revenue due to missed adoptions. The total regret is therefore bounded by $\approx(\log(m)m^{2/3}+\sqrt{m}\log(T))$.

Theorem 5.1 highlights the regime of horizon $T$ where this learning problem is most challenging. In this problem, we observe that if $T$ is large, the seller can simply offer a high price for the entire time horizon and still capture most of the market, making the problem trivial. Specifically, for $T\geq\Omega(\log(m))$, under an additional assumption that there is a constant upper bound on price, we can show that an $O(\log(m))$ upper bound on regret can be trivially achieved by offering the maximum price at all times (see Lemma F.1). On the other hand, when $T=o(1)$, then we can show that achieving a sublinear (in $m$) regret is trivial for any algorithm. This is because from (7) we have that in this case the optimal number of adoptions $X^{*}_{T}\leq\frac{\alpha+\beta}{e}T=o(1)$. Furthermore, from Lemma 4.4 we know that all prices in the optimal curve can be bounded by $p^{*}_{max}=O(1)$ in this case. This means that the optimal revenue is at most $mX^{*}_{T}p^{*}_{max}=o(m)$, i.e., sublinear in $m$. Intuitively, for such a small $T$, the word-out-mouth effect never comes into play (i.e., the $\alpha+\beta x$ term in the Bass model is dominated by $\alpha$), making the problem uninteresting. Our lower bound result therefore pinpoints the exact order of $T$, i.e., $T=\Theta(1/(\alpha+\beta))$, where the difficult and interesting instances of this problem come from.

In the rest of this section, we describe the proof of Theorem 5.1. We first provide an intuition for our lower bound and then go over the proof outline.

We start with showing that the pseudo-regret of any algorithm can be lower bounded in terms of its cumulative pricing errors. Therefore, in order to achieve low regret, any algorithm must be able to estimate optimal prices accurately.

Next, we observe that in this problem, the main difficulty for any algorithm comes from the difficulty in estimating the market parameter $\beta$. Since $\beta$’s observed influence on the arrival rate of customers is proportional to the current adoption level $x$, one cannot estimate $\beta$ accurately when $x$ is small. This makes intuitive sense because when the number of adopters is small, we do not expect to be able to measure the word of mouth effect accurately. In fact, we demonstrate that for any $\varepsilon$, before the adoption level exceeds $\left(\frac{m}{\varepsilon}\right)^{2/3}$, no algorithm can distinguish two markets with Bass model parameters $(\alpha,\beta)$ vs. $(\alpha,\beta+\varepsilon)$. Further, we can show that in some problem instances (specifically for instances with $T=\Theta(1/(\alpha+\beta))$), the optimal prices for the first $m^{2/3}$ customers are very sensitive to the value of $\beta$. Therefore, if an algorithm’s estimation of $\beta$ is not accurate, it cannot accurately compute the optimal price for these customers. This presents an impossible challenge for any algorithm: it needs an accurate estimate of $\beta$ in order to compute an accurate enough optimal price for the first $m^{2/3}$ customers, but it cannot possibly obtain such an accurate estimate while the adoption level is that low; thus, it must incur pricing errors resulting in the given lower bound on regret.

A formal proof of Theorem 5.1 is obtained through the following four steps. All the missing proofs from this section can be found in Appendix E.

First we show that the pseudo-regret of an algorithm can be lower bounded in terms of cumulative pricing errors made by the algorithm. Note that this result is not apriori obvious because as we have discussed earlier, prices have long term effects on the adoption curve: the immediate loss of revenue in the current round by offering too low of a price might be offset by the fact that we saved some time for the future rounds (lower price means faster arrival rate). On the other hand, if we offer a price that is higher than the optimal price, the resulting delay in customer arrival (higher price means slower arrival rate) may lead to less remaining time and fewer adoptions, which could be more harmful than the immediate extra revenue. The result proven here is crucial for precisely quantifying these tradeoffs and lower bounding the regret in terms of pricing errors.

To obtain this result, we first lower bound the impact of offering a suboptimal price at any time, on the remaining value in the deterministic Bass model. Given any current adoption level $x$ and remaining time $T^{\prime}$, the impact or ‘disAdvantage’ $A^{det}(x,T^{\prime},p)$ of price $p$ is defined as the total decrease in value over the remaining time when $p$ is offered for an infinitesimal time and then optimal policy is followed. That is,

We prove the following lemma lower bounding this quantity.

Now recall that pseudo-regret is defined as the total difference in revenue of the algorithm, which is potentially offering suboptimal prices, compared to the deterministic optimal revenue $V^{\text{det}}(T)$. We use the above result to quantify the impact of offering suboptimal prices for the first $n\approx m^{2/3}$ customers, along with a bound on difference in stochastic vs. deterministic optimal revenue, to obtain the following lower bound on the pseudo-regret:

Here, $p_{x}$ denotes the price trajectory obtained on using the algorithm’s prices in the deterministic Bass model, and $\pi^{*}_{x}$ denote the prices that would minimize the disadvantage at each point in this trajectory. A more precise statement of this result is in Lemma E.2 in Appendix E.

The remaining proof focuses on lower bounding the cumulative difference in pricing errors $(\pi^{*}_{x}-p_{x})^{2}$ that any algorithm must make for the first $n\approx m^{2/3}$ customers.

Consider two markets with parameters $(\alpha,\beta)$, and $(\alpha,\beta+\epsilon)$ for some constant $\epsilon$. We show that for the first $n\approx\left(\frac{m}{\epsilon}\right)^{2/3}$ customers, any pricing algorithm will be “wrong” with a constant probability. Here by being wrong we mean that the algorithm will set a price that is closer to the optimal price of the other market. Lemma E.3 and Corollary E.1 formalize this idea. The proof is based on a standard information theoretic analysis using KL-divergence.

Next we show that for $T=\Theta(\frac{1}{\alpha+\beta})$, the difference between the optimal prices for the two markets ($(\alpha,\beta)$ and $(\alpha,\beta+\varepsilon)$) is large ($\approx\frac{\alpha\varepsilon}{(\alpha+\beta)^{2}}$). We show this by proving a bound on the derivative of optimal price with respect to $\beta$. Lemma E.4 in Appendix E gives the precise statement.

Finally, we put together the observations made in the previous three steps to prove Theorem 5.1. We have shown that with constant probability any algorithm will make a pricing mistake for the first $\approx(\frac{m}{\epsilon})^{2/3}$ customers [Step 2] and that this mistake will be large (on the order of $\epsilon$) [Step 3] under the condition that $T=\Theta(1/(\alpha+\beta))$. We also have a lower bound on pseudo-regret in terms of total (square of) pricing errors made over the first $n\approx m^{2/3}$ customers [Step 1]. Combining these observations with an appropriately chosen $\epsilon$ gives us that the pseudo-regret is lower bounded by $O(\epsilon^{2}(\frac{m}{\epsilon})^{2/3})\approx O(m^{2/3})$.

All the missing details of this proof can be found in Appendix E.