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.
86,357 characters · 20 sections · 78 citation commands
Policy Optimization Using Semi-parametric Models for Dynamic Pricing
Dynamic pricing is the study of determining and adjusting the selling prices of products over time based on statistical learning and policy optimization. As an integral part of revenue management, it has wide applications to various industries. Research on dynamic pricing has spanned across the fields of statistics, machine learning, economics, and operations research dB15,WEI2018166,MP20. In general, a good pricing strategy often involves good statistical learning of the demand function as well as revenue optimization over time.
Recent works particularly focus on feature-based (or contextual) pricing models, where the market value of a product as well as the pricing strategy depend on some observable features of the product JN19,Ban2020PersonalizedDP. Given the product features (covariates) available through the massive real-time data in online platforms today, feature-based pricing models take product heterogeneity into account, which enable customized pricing for products.
In this work, we consider the following dynamic pricing problem: We assume that a seller sells one product at each time $t=1, \cdots, T$. Each product is attached with a known feature vector $\xb_t \in \RR^d$. In addition, the product's market value $v_t$ is linear in the features plus some i.i.d. market noise $z_t$ with an unknown cumulative distribution $F(\cdot)$: { $$ v_t = \btheta_0^\top \tilde\xb_t+z_t, \qquad z_t \sim F. $$ Here $\tilde\xb_t = (\xb_t^\top,1)^\top$ and $\btheta_0$ is some unknown parameter.} The customer makes an independent purchase decision for each product depending on whether the seller's posted price $p_t$ is higher than the market value $v_t$, after which the revenue is collected. In this case, the demand curve $P(v_t \geq p_t)$ actually depends on both the parameter $\btheta_0$ as well as the distribution of $z_t$, which admits a semi-parametric form. They need to be learned or estimated dynamically from the observed binary data that indicates whether a sale is successful. Under this setting, we propose a policy which utilizes semi-parametric estimation techniques to achieve a low regret. In particular, under mild regularity conditions, if the c.d.f. $F(\cdot)$ of $z_t$ has $m^{th}$ derivative, the regret over a time horizon $T$ is upper bounded by $\cO((Td)^\frac{2m+1}{4m-1}\log T(1+\log T/d))$, where $d$ is the number of features. This result is further generalized to a setting where the product features $\xb_t$ are not independent, as long as $\{\xb_t\}_{t\ge 1}$ is a stationary series that satisfies certain $\beta$-mixing conditions. Moreover, when $F$ is infinitely differentiable, the total regret can be upper bounded by $\tilde \cO((Td)^{\frac{1}{2}}(\log T)^{\frac32+\frac{3}{2\alpha}}(\log (d+1) + \log T/d))$. { This rate is the same as the parametric lower bound up to some logarithmic factors, i.e. where the distribution of $z_t$ is generated from a parametric class.}
Our work contributes to the recent line of dynamic pricing literature as well as the growing literature on decision making with covariate information and contributes to kernel regression. Our work is also closely related to the non-parametric statistics literature. We'll briefly review the related works in the below.
Dynamic pricing. In the classical pricing models, one aims at maximizing the revenue over time by posting price sequentially while learning the underlying demand curve or market evaluation of a product. The demand curve is typically fixed over time, and falls into a known function class. Related literature includes KL03, PBP06, BZ09, BR12, KZ2014,dBZ14, WDY14, dBZ15, BDKA15, Bianchi2019, CJD2019. { As an example, Bianchi2019 study the dynamic pricing problem where the buyer's valuation of a product is supported on a finite $K$ unknown points, and the success of a sale is determined by comparing the valuation to the proposed price. Using a generalization of UCB algorithm, the authors achieve the regret with order $\cO(K\log T)$.} For a comprehensive survey on this topic, see {dB15}.
Recently, many papers have been focusing on contextual dynamic pricing, where product heterogeneity is taken into account when modeling the demand curve or market evaluation. A common and natural choice is to model the market value of the product at time $t$ as a linear function of its features $\xb_t$ plus some market noise $z_t$, i.e. $v_t = \btheta^\top \xb_t + z_t$ where $\btheta$ is some unknown parameter Qiang2016, J17, MCCLZ19, JN19, Ban2020PersonalizedDP, WWSC20, CSW20, THL20, GJM20. Under this setting, for `truthful' buyers whose decision is based on comparing $v_t$ and offered price $p_t$, the demand curve can be expressed as a generalized linear model given feature covariates $\xb_t$, where the link function is closely related to the distribution of the market noise $z_t$ (see (ref) for a detailed reasoning). Qiang2016 assume a linear model between the demand curve and the product features. They prove that the greedy iterative least squares (GILS) algorithm achieves a regret upper bound of $\cO_d(\log T)$, where $\tilde{\cO}_{d}$ is the order that hides logarithmic terms and the dimensionality of feature $d$, and provide a matching lower bound under their setting. MCCLZ19 and Ban2020PersonalizedDP consider a generalized linear model with known link, while JN19 and WWSC20 study the same problem with high dimensional sparse parameters. The algorithms are usually a combination of statistical estimation procedures and online learning techniques. Depending on the setting, the optimal regret ranges from $\cO_d(\log T)$ to $\tilde \cO_d(\sqrt {T})$. Other related works include CSW20, THL20 where the authors explore certain differentially private policies under similar model setting; GJM20 where the authors consider the second price auction problem with multiple customers, each of which has his/her own product evaluation; and J17 where the parameter $\btheta$ in the generalized linear model changes through time.
In practice, however, the distribution of the market noise $z_t$ is usually unknown to the seller. Thus, it might be desirable to only assume that the noise density falls into some general class. As will be discussed in \S(ref), this leads to modeling the demand curve as a generalized linear model with unknown link, and will be our main focus in this paper. Compared to the previous setting, this setting is more challenging, and the related literature is sparse. JN19 propose a preliminary algorithm that achieves a regret upper bound of $\cO_{d}(T)$. Golrezaei2019 consider a second price auction with reserve where there are more than one customers, each of whom has his/her individual parameters in their demand curve model, and the customer bids are available as additional information. The authors propose the NPAC-T/NPAC-S policy that achieves a regret $\tilde{\cO}_{d}(\sqrt{T})$. GJM20 also explore the second price auction and derive a regret upper bound of $\tilde{\cO}_{d}(T^{2/3})$ compared to a `robust benchmark' where the price maximizes the revenue of the worst link function in the class. SJB2019 explore an alternative setting where the market value $v_t = \exp(\btheta^\top \xb_t + z_t)$ and $z_t$ has unknown distribution. By utilizing this specific structure, the authors propose the DEEP-C algorithm based on multi-arm bandit that has a regret upper bound of $\tilde{\cO}_{d}(\sqrt{T})$. The authors also propose some variants of the algorithm and study them via simulations. { Recently, LSL21,xu2022towards study a similar problem to ours, assuming a linear market valuation with unknown noise distribution. In particular, LSL21 provide a DIP policy that achieves regret $\cO_d(T^{2/3}+\|\hat\btheta-\btheta\|_1T)$, where $\|\hat\btheta-\btheta\|_1$ is the estimation accuracy of the parameter $\btheta$. In addition, xu2022towards presents an algorithm `D2-EXP4' that achieves regret with order $\cO(T^{3/4})$.}
{ There are some literature studying other dynamic pricing algorithms ARS14, CLPL16, MLS2018, LS18, NSW19, AA20, A2020, Ban2020PersonalizedDP, LZ20, JNS20, chen2020, LLS21. For example, MLS2018 study a non-parametric dynamic pricing pricing where the market value is modeled as a general non-parametric function $f(\xb_t)$, where $\xb_t$ are the features. A binary feedback is similarly observed based on the comparison between $f(\xb_t)$ and the proposed price. The authors apply a variation of midpoint algorithm and achieve a regret upper bound of $\cO(T^{d/(d+1)})$ with $d$ being the dimension of $\xb_t$.}
Semi-parametric and non-parametric statistical estimation. Our work is also closely related to estimation of the single index model, or the generalized linear model with an unknown link. Such model has been studied in the statistics and econometrics literature for decades, and has wide applications in fields like econometrics and finance PSS89, ICHIMURA199371, HHI93, KS93, WW94, MG94, HH96, CFGW97, XL99, DHH03, FL04. For a comprehensive summary of these works, please refer to McC00, Gyorfi2002,FY03, RWC03, T08, Hor12. Various methods have been proposed to estimate the parametric part that achieves root-$n$ consistency under certain conditions PSS89, ICHIMURA199371, KS93. CFGW97 study the generalized partial linear single index models, where the authors leverage local linear kernel regression with quasi-likelihood method to estimate both the parametric and non-parametric parts of the model. {XL99 investigate in the single index coefficient model with strong-mixing features. Estimators with uniform convergence rate to the ground truth based on kernel regression are proposed.}
Given a root-$n$ consistent estimation of the coefficients, standard univariate non-parametric regression techniques can be used to estimate the non-parametric part of the single index model that achieves $\ell_\infty$ consistency, which is necessary in deriving regret upper bounds. One common estimator is the Nadaraya-Watson estimator N64,W64. Silverman78 and MS82 establish uniform convergence results for kernel density estimator and Nadaraya-Watson estimator for regression functions. In addition, Stone80,Stone82 derive uniform convergence results for the more general local polynomial regression estimators. Masry96 prove similar results when the covariates satisfy strong-mixing conditions.
In this paper, we'll provide non-asymptotic error bounds for both coefficient estimation as well as the plug-in Nadaraya-Watson estimator in a uniform sense. These non-asymptotic bounds are useful for constructing regret bounds within a finite horizon.
Our contributions are the following: First, compared to related works, our policy achieves a low regret with few assumptions on the market noise distribution and little additional information. Given $F\in \mathbb{C}^{(m)}$ where $F$ is the c.d.f. of $z_t$, the regret over a time horizon $T$ is upper bounded by $\tilde \cO((Td)^\frac{2m+1}{4m-1})$; If $F$ is `super smooth', the bound is further reduced to $\tilde \cO(\sqrt{Td})$, which is nearly the same regret order by assuming a parametric distribution for $z_t$ as in JN19 where the $s$-sparsity on $\bbeta_0$ is imposed. Table {\red 1} illustrates the settings of our work as well as several related literatures. GJM20 choose a more `conservative' regret by comparing to a benchmark policy which minimizes revenue with the worst demand function over the whole ambiguity function class. In contrast, our notation of regret is more standard and 'accurate' in that our benchmark policy knows the exact demand function given any product features. SJB2019 consider a log-linear relation between the market value and the covariates instead of a linear relation and derive a regret upper bound of $\tilde{\cO}(\sqrt{T}d^{11/4})$. Their algorithm based on multi-arm bandit has sub-optimal dependence on the dimension $d$ in terms of both regret and complexity, and is quite difficult to implement under general conditions. Interestingly, the authors conjecture that under the linear settings, there is no policy that achieves an $\tilde{\cO}_d(\sqrt{T})$ regret. Our work partly answers their guess by providing a policy with a $\tilde{\cO}(\sqrt{Td})$ regret when the demand function is sufficiently smooth. { Compared with the DIP policy in LSL21 and its regret $\cO_d(T^{2/3}+\|\hat\btheta-\btheta\|_1T)$, we are more clear on how $\hat\btheta$ are estimated within the pricing algorithm, and we provide explicit rate on both the estimation error and the regret.} {Moreover, compared to several fully non-parametric dynamic pricing literatures, such as MLS2018 and chen2020, our algorithm scales more nicely with dimension $d$, and can easily be generalized to a high-dimensional setting. Our algorithm is also easy to implement compared to some bandit-based algorithms that need dividing the feature space into bins. }
Second, we generalize our results to the regime where the product features $\{\xb_t\}_{t\ge 1}$ are weakly dependent instead of independent, which is more likely in practice. For example, for many products (such as softwares, electric products, etc.), the features of the products evolve over time and definitely inherit some past information. In other situations, the products for sale might have some common time-dependent factors shared by all products in the same industry (such as weather condition, population composition, etc.). This setting with weakly-dependent features can also be found in literatures such as COPS2021, where the authors study an offline pricing problem with parametric models and dependent covariates.
Last but not least, we establish non-asymptotic results on the $\ell_{\infty}$ error bound of the nonparametric kernel density and regression estimation, which are potentially useful in other related study as well. As mentioned in the related literatures, most results on non-parametric kernel regression estimation are established under the asymptotic settings. Meanwhile, we believe that non-asymptotic results are necessary to achieve a finite-sample regret upper bound in the pricing problem. Please refer to Appendix (ref) for related lemmas.
Throughout this work, we use $[n]$ to denote $\{1,2,\cdots,n\}.$ For any vector $\xb\in \RR^{n}$ and $q\ge 0$, we use $\|\xb\|_{q}$ to represent the vector $\ell_q$ norm, i.e. $\|\xb\|_{q}=(\sum_{i=1}^{n}|x_i|^q)^{1/q}.$ In addition, we let $\nabla_{\xb}L(\cdot),\nabla_{\xb}^2L(\cdot)$ be the gradient vector and Hessian matrix of loss function $L(\cdot)$ with respect to $\xb$. For any given matrix $\Xb\in \RR^{d_1\times d_2}$, we use $\|\cdot\|$ to denote the spectral norm of $\Xb$ and we write $\Xb\succcurlyeq 0$ or $\Xb\preccurlyeq 0$ if $\Xb$ or $-\Xb$ is semidefinite. For any event $A$, we let $\II_{A}$ be a indicator random variable which is equal to $1$ if $A$ is true and $0$ otherwise. In addition, we use $\CC^{(m)}$ with $m\in \mathbb N$ to denote the function class which contains all functions with $m$-th order continuous derivatives. For two positive sequences $\{a_n\}_{n\ge 1}$, $\{b_n\}_{n\ge 1}$, we write $a_n=\cO(b_n)$ or $a_n\lesssim b_n$ if there exists a positive constant $C$ such that $a_n\le C\cdot b_n$ and we write $a_n=o(b_n)$ if $a_n/b_n\rightarrow 0$. In addition, we write $a_n=\Omega(b_n)$ or $a_n\gtrsim b_n$ if $a_n/b_n\ge c$ with some constant $c>0$. We use $a_n=\Theta(b_n)$ if $a_n=\cO(b_n)$ and $a_n=\Omega(b_n)$. We use notations $\cO_{d}(\cdot),\Omega_{d}(\cdot)$ and $\Theta_{d}(\cdot)$ to denote similar meanings as above while treating the variable $d$ as fixed. Moreover, we let $\tilde{\cO}(\cdot),\tilde{\Omega}(\cdot),\tilde{\Theta}(\cdot)$ represent the same meaning with $\cO(\cdot),\Omega(\cdot )$ and $\Theta(\cdot)$ except for ignoring log factors.
The rest of this paper is organized as follows. We describe the problem in \S (ref) and propose a solution in \S(ref) where some heuristic arguments are offered for bounding the regret. In \S(ref), we provide our theoretical results on the upper bounds of the regret and in \S(ref), we discuss a lower bound result. Our algorithm is illustrated in \S(ref) by intensive simulation experiments.
We consider the pricing problem where a seller has a single product for sale at each time period $t=1,2,\cdots,T$. Here $T$ is the total number of periods (i.e. length of horizon) and may be unknown to the seller. The market value of the product at time $t$ is $v_t$ and is unknown. We assume that the range of $v_t$ is contained in a closed interval in $(0,B)$. In particular, we assume that $v_t\in[\delta_v, B-\delta_v]$ for some constant $\delta_v>0$. At each period $t$, the seller posts a price $p_t$. If $p_t\le v_t$, a sale occurs, and the seller collects a revenue of $p_t$; otherwise, no sale occurs and no revenue is obtained. Let $y_t$ be the response variable that indicates whether a sale has occurred at period $t$. Then
The goal of the seller is to design a pricing policy that maximizes the collected revenue.
In this paper, we further model the market value $v_t$ as a linear function of the product's observable feature covariate $\xb_t\in \RR^{d}$. In particular, define $\tilde{\xb}_t = (\xb_t^\top,1)^\top$, where we assume $\{\xb_t\}_{t\ge 1}$ are i.i.d. samples from an unknown distribution $\PP_X$ supported on a bounded subset $ \cX \subseteq \RR^d$. Assume that
{where $\btheta_0 = (\bbeta_0^\top,\alpha_0) ^\top\in \RR^{d+1}$ is an unknown parameter, and $\{z_t\}_{t\ge 1}$ is an i.i.d. sequence of idiosyncratic noise drawn from an unknown distribution with zero mean and bounded support $(-\delta_z,\delta_z)$. The cumulative distribution function of $z_t$ is denoted by $F(\cdot)$. The above model implies that
}
In a non-dynamic setting, the model (ref) is closely related to the single index model, or generalized linear (logistic regression) model with unknown link function ICHIMURA199371,FHW95,CFGW97. In their works, it's usually assumed that $p_t = 0$ and $\{(\tilde \xb_t)\}_{t\ge 1}$ are independent observations, and the goal is to estimate $\btheta_0$ and $F$. Meanwhile, we work on the dynamic setting where we need to optimize some revenue function by iteratively deciding $p_t$ given previous observations based on dynamically learned $\btheta_0$ and $F$. These two problems are closely related but also decisively different.
We now state our objective in more details. Given observed features $\xb_t$, the expected revenue at time $t$ with a posted price $p$ is
The optimal posted price $p_t^{*}$ for a product with attribute $\xb_t$ is given by
which depends on unknown parameters and needs to be learned dynamically from the data. As in common practice, we evaluate the performance of any policy $\pi$ that governs the rule of posted prices $\{p_t\}_{t\ge 1}$ by investigating the regret compared to the `oracle pricing policy' that uses the knowledge of both $\btheta_0$ and $F(\cdot)$ and offers $p_t^{*}$ according to (ref) for any given $t$. In other words, we consider the problem of maximizing revenue as minimizing the following maximum regret
where the expectation is taken with respect to the the idiosyncratic noise $z_t$ and $\xb_t$, and $p_t(\pi)$ denotes the price offered at time $t$ by following policy $\pi$. Here $\mathcal Q(\cX)$ represents the set of probability distributions supported on a bounded set $\cX$. Our goal is to choose a good strategy $\pi$ such that the above total regret is small.
Apparently, learning $\btheta_0$ and $F(\cdot)$ over time gives the seller much more information to estimate the market value of a new product given it's feature covariates. On the other hand, the seller also wants to always give optimized price so as to maximize the expected revenue by (ref). Therefore, it's necessary to have a good policy that strikes a balance between exploration (collecting data information for learning parameters) and exploitation (offering optimal pricing based on learned parameters).
Before proposing our algorithm, we first impose some regularity condition on $F$ so that the optimization problem ((ref)) is 'well-behaved'.
Assumption (ref) ensures that $\phi(\cdot)$ is strictly increasing, which implies a unique solution to ((ref)). In fact, the first order condition of (ref) yields $$ p_t^* = g(\btheta_0^\top\tilde{\xb}_t), $$ where $g(u)\triangleq u+\phi^{-1}(-u)$.
We first propose Algorithm (ref) in \S(ref) which describes our policy for minimizing the regret given in (ref), and then provide the main idea for the regret analysis achieved by our Algorithm (ref) in \S(ref).
In the following algorithm, we divide the time horizon into `episodes' with increasing lengths. The first part of each episode is a short exploration phase where the offered prices are i.i.d. to collect the data and model parameters (i.e. $\hat\btheta$, $\hat F$) are then updated based on the collect data. The second part is an exploitation phase, where the optimal $p_t$ is offered according to the current estimate of parameters and the new $\tilde \xb_t$. The details are stated in Algorithm (ref).
Despite semiparametric model (ref) with unknown link, by offering $p_t\sim \text{Unif}(0, B)$, $By_t$ follows the linear model with regression $\tilde \xb_t^\top \btheta_0$ and this leads to the least-squares estimate (ref). To see this, it follows that
On the other hand, a uniform distribution for $p_t$ is actually critical for the above property. Suppose that $p_t$ is drawn from a c.d.f. $F_p(\cdot)$ and there is a transform $f_1$ of $y_t$ that satisfies
for all $\PP_X$, then according to (ref), we have
Since the above equation holds for all $\PP_X\in\mathcal Q(X)$, it can only be the case that $F_p$ is linear within the region $[0, B]$, which implies that $p_t$ should follow a uniform distribution.
The main idea behind our regret analysis is a balance between exploration and exploitation. This idea is shown in the following heuristic arguments. For simplicity, we assume for now that there is only one episode, and that the total length of time (horizon) $\ell$ is known and $d$ is bounded.
First, denote $\ell_1$ as the length of the exploration phase. During this phase, the regret $R_1$ at each time is bounded by a constant due to bounded distribution $F(\cdot)$ that entails bounded $p_t^*$ in (ref). Therefore, the total regret in this phase is
For the second phase, the expected regret can be controlled by the estimation error of both $\btheta$ and $g$ (which is a functional of $F$ as mentioned in ((ref))). In fact, let the regret at each time point $t$ be
Then the conditional expectation of regret at time $t$ given previous information and $\tilde \xb_t$ is
Here $\bar{\cH}_t=\sigma(\xb_1, \xb_2, \cdots, \xb_{t+1}; z_1, \cdots, z_t)$. On the other hand, under mild conditions, the above difference in revenue can further be upper bounded by an order of $(p_t - p_t^*)^2$ using Taylor expansion. Therefore, we have
In fact, $\mathbf{J_2}$ is upper bounded by $\|\hat \btheta - \btheta_0\|_2^2$ (given the Lipschitz property of $g$ according to Assumption (ref) and suitable conditions over $\PP_X$). By solving ((ref)), we prove that the squared $\ell_2$ error is of order $\cO(\ell_1^{-1})$, which is the order of $\mathbf{J_2}$. The term $\mathbf{J_1}$ is upper bounded by $\|\hat g - g\|_\infty^2$, and is further bounded by $\max\{\|\hat F - F\|_\infty^2, \|\hat F' - F'\|_\infty^2\}$. Note that by (ref), $F(\cdot)$ is the non-parametric function of $1-Y_t$ given $w_t = p_t-\tilde{\xb} _t^\top \btheta_0$, in which $p_t$ is the observed price given in the exploration phase. Since $\btheta_0$ is estimated at a faster rate, we can assume that $w_t$ is observable given a proper estimator of $\btheta_0$. Therefore, the error rate is dominated by estimating $F'(\cdot)$. Assuming $F$ has an $m$-th continuous derivative, we construct $\hat g$ using the kernel estimator with a $m$-th order kernel, and prove that $\max\{\|\hat F - F\|_\infty, \|\hat F' - F'\|_\infty\}\lesssim \cO(\ell_1^{-{(m-1)}/{(2m+1)}})$ in which a logarithmic order is ignored for simplicity of presentation. Therefore, the total regret during the exploitation phase can be upper bounded by
Combining ((ref)) and ((ref)), we know that by choosing $\ell_1$ of the order of $\ell^{(2m+1) / (4m-1)}$, we balance the regret of both exploration and exploitation phase, and the total regret during the episode is given by $$ R_1 + R_2 = \cO(\ell^{(2m+1) / (4m-1)}). $$
For a second order kernel, the above regret is of order $\cO(\ell^{5/7})$. For a relatively large $m$, the regret is close to $\cO(\ell^{1/2})$, which is actually proven to be the lower bound for a wider class of problems.
{ In this section, we divide our results into three parts. In \S(ref), we consider the setting with independent covariates and finite differentiable noise distributions. In \S(ref), we further extend our results in \S(ref) to the setting with correlated features. Finally we extend the aforementioned results to the regime with infinitely differentiable noise distributions i.e. $m=\infty$ in \S(ref).}
The main result of this section is Theorem (ref). To obtain this results, we first state some technical conditions and technical lemmas, which demonstrate the accuracy of statistical learning in each episode. These lemmas provide insights how statistical accuracy influences on the regret of our policy and have interests of their own rights.
Assume that $\|\btheta_0\|\leq R_{\Theta}$ for some constant $R_{\Theta}>0$. We also define $R_\cX := \sup_{\xb\in\cX}\|\xb\|_2$. Before stating our main results, we first make the following assumptions on $\xb_t$.
As we observe from $\Jb_1,\Jb_2$ given in (ref), bounding the regret in the exploitation phase needs to estimate both parameter $\btheta_0$ and function $g(\cdot)$. { In the following, we first present an upper bound of estimating $\btheta_0$ at the end of the exploration phase within each episode in the following Lemma (ref). Recall $|I_k|$ is the length of the $k$-th exploration phase. }
Let $\Theta_k := B(\btheta_0, R_k)$, where $R_k$ is the right hand side of (ref). We conclude from Lemma (ref) that with high probability, $R_k$ is of order at most $\sqrt{{d\log |I_k|}/{|I_k|}},$ and we can achieve similar upper bounds for $\Jb_2$ for any episode $k$.
Next, we proceed to construct the estimator $\hat g_k$ in each episode and bound its distance to $g$. Notice that $g(u) = u+\phi^{-1}(-u)$, and $\phi(u) = u-\frac{1-F(u)}{F'(u)}$. Thus, a natural way to construct $\hat g_k$ is from an estimate of $F$ and $F'$, as mentioned in our algorithm. Moreover, the uniform error bounds of our estimators $\hat F_k$ and $\hat F_k^{(1)}$ guarantee a uniform error bound of $\hat g_k$.
We use the kernel regression method and $\hat\btheta_k$ obtained above to construct $\hat F_k$ and $\hat F^{(1)}_k$. Recall that by (ref), we have $E(y_t | w_t(\btheta_0)) = 1- F\left(w_t(\btheta_0)\right)$ where $w_t(\btheta):=p_t-\tilde{\xb} _t^\top \btheta$. Recall $p_t$ is the observed price offered in the $k$-th exploration phase. Thus, given $\hat \btheta_k$, $F(\cdot)$ can be estimated by using the Nadaraya-Watson kernel regression estimator and $F'(\cdot)$ can be estimated by the derivative of the estimator. Specifically, we define
and $\hat F_k(u) = \hat F_k(u, \hat\btheta_k)$, where
for a chosen $m$-th order kernel $K$ and a suitable bandwidth $b_k$. Now, we estimate the derivative $F'(\cdot)$ by taking the derivative of the estimator. That is, $\hat F_k^{(1)}(u) =\hat F_k^{(1)}(u,\hat\btheta_k)$ where
{ Recall we mention in \S(ref) that $(-\delta_z,\delta_z)$ is the support of noise $z_t$. In addition, we also mentions that $T$ denotes the length of time horizon which is unknown. In the following, we will state other necessary assumptions to derive the regret upper bound:}
The Assumptions (ref)-(ref) are quite standard assumptions in non-parametric statistics; see fan1996local,T08 for more details. Given these assumptions, we will prove that with high probability, the estimators $\hat F_k(u,\btheta)$ and $\hat F_k^{(1)}(u, \btheta)$ are sufficiently close to { $F(u)$ and $F'(u)$} respectively given any $\btheta\in \Theta_0$ for every sufficiently large $k$. Specifically, we obtain the desired error bound for $\hat F_k(u) = \hat F_k(u,\hat\btheta_k)$ and $\hat F_k^{(1)}(u) = \hat F_k^{(1)}(u,\hat\btheta_k)$.
{
}
We next develop a uniform upper bound for term $\Jb_1$ given in (ref) for the $k$-th episode in Lemma (ref) below.
Combining the above lemmas, which give us upper bounds for terms $\Jb_1,\Jb_2$ in every episode, we have the following Theorem (ref), which provides an upper bound for the regret.
\textcolor{black}{
}
As mentioned in the introduction, we believe that in many situations, the dependence of features over time is inevitable. Thus, in this section, we generalize our results to the case where $\xb_t$ can be dependent. For this purpose, we first impose the strong-mixing condition which measure the dependence between covariates over time.
The following assumption ensures that $\{\xb_t\}_{t\ge 1}$ are not too strongly dependent. { Combining with other assumptions, we ensure that the empirical covariance matrix $\frac{1}{n}\sum_{i=1}^{n}\tilde{\xb}_i\tilde{\xb}_i^\top$ concentrate around the population version, which is necessary in deriving the regret in every episode.}
{ In order to derive the final regret upper bound under the stong-mixing setting, we also need an additional technical assumption stated below:}
{ When the covariates $\xb_i,\xb_j$ are independent, we have $g_{q,\btheta}(u_i,u_j)=0,q\in\{1,2\}$, for all $(u_i,u_j)$. Under such a mild assumption, we obtain a uniform upper bound of $|g_{q,\btheta}(u_i,u_j)|$, which is dominated by the $\beta$-mixing constant $\beta_{j-i}^{1/3}$, for all $\btheta\in\Theta_0$ and $(u_i,u_j)$ (see Appendix (ref)). Thus, this assumption essentially guarantees that the joint regression and density functions of the features still stay close to the products of their marginal ones even if they are correlated.}
{ Following similar analysis with \S(ref), we reach the following theorem which gives a regret upper bound at similar rate with Theorem (ref) under the strong-mixing feature setting.}
In \S(ref) and \S(ref), we analyze the regret upper bounds when the noise distribution $F$ has an $m$-th order continuous derivative, with any finite $m\ge 2$. The regret of our algorithm is of order $\tilde \cO((Td)^{\frac{2m+1}{4m-1}})$, which gets closer to $\tilde{\cO}(\sqrt{Td})$ as the degree of smoothness $m$ goes to infinity. In fact, this is mainly due to inaccurate estimation of $F$ and $F'$ resulting from the bias of the kernel estimator. In this section, we deal with super smooth noise distributions fan1991optimal, where $F$ is infinitely differentiable. Under mild conditions, we're able to control the bias within $\cO(1/{|I_k|^\frac{1}{2}})$ for each episode $k$ by using extremely smooth kernels. { As a reminder, here $|I_k|$ is the length of the $k$-th exploration phase. }This leads to a $\tilde \cO_{d}(\sqrt{T})$ regret bound in our algorithm. In particular, we assume the following:
Under the Assumption of (ref), for each episode $k$, we can successfully control the bias within $\cO(1/\sqrt{|I_k|})$ via an infinite order kernel MP04,Berg2009CDFAS. In order to construct an infinite order kernel $K$, we simply let $K$ be the Fourier inverse transform of some `well-behaved' function. In particular, let
be the Fourier inversion of $\kappa$ satisfying $$ \kappa(s)=\left\{
\right. $$ Here $g_{\infty}$ is any continuous, square-integrable function that is bounded in absolute value by $1$ and satisfies $g_{\infty}(|c_{\kappa}|)=1$. This defines an infinity order kernel function fan1996local.
By plugging the infinite order kernel $K$ into our algorithm, we're able to obtain the following lemma:
Following similar proof procedures of Theorems (ref) and (ref), Lemma (ref) leads to the following theorem, which gives a regret upper bound of $\tilde {\cO}_{d}(\sqrt{T})$, achieving the same convergence rate with the parametric case up to logarithmic terms JN19.
\textcolor{black}{ Algorithm (ref) can be naturally extended to the high-dimensional setting, where $\btheta_0\in \mathbb R^d$, $d$ can be large compared to $T$, while $\|\btheta_0\|_0\leq s$ for a relatively small sparsity $s$. This happens in applications when a large amount of covariate information is available, and the actual market value only depends on some essential factors. One way of extension is the following: at each episode, we can replace estimation of $\hat\btheta_k$ in (ref) with the two steps below.}
\textcolor{black}{\noindentStep 1. Let
where $$ L_k(\btheta):= \frac{1}{|I_{k}|}\sum_{t\in I_{k}} (By_t-\btheta^\top\tilde{\xb}_t)^2, \quad p(\btheta) = \sum_{j=1}^p p(|\btheta^{(j)}|) $$ for some penalty function $p(\cdot)$. As in zhao2006model, fan2001variable, mcp2010, by choosing different $p(\cdot)$ such as in the $\ell_1$, SCAD or MCP penalty, under suitable conditions such as irrepresentable condition, variable selection consistency is achieved with high probability. }
\textcolor{black}{\noindentStep 2. Let $\hat S_k = \text{supp}(\tilde \btheta_k)$, we then refit the least squares (ref) on $\hat S_k$:
Then the conclusions of Lemma (ref) hold with high probability. }
\textcolor{black}{After Step 2, we continue the remaining steps of Algorithm (ref) in the episode. In fact, if we can learn the support of $\btheta_0$, we essentially translate the problem into a low-dimensional one, and we can prove that Algorithm (ref) achieves a regret upper bound of $\Tilde \cO((Ts)^{\frac{4m+1}{2m-1}})$ if $F\in \mathcal C^{(m)}$ (or $\cO((Ts)^{1/2})$ if $F$ is super smooth).}
In this section, we illustrate the performance of our policy through large-scale simulations under various settings. Recall our model (ref), where $\xb_t\in \RR^{d}$ and $z_t$ follows distributions with bounded support and smooth c.d.f. Throughout this section, we let the dimension $d=3$ and the coefficients $\alpha_0=3$, $\bbeta_0=\sqrt{2/3}\cdot \mathbf{1}_{3\times 1}$. For each value of smoothness degree $m\in \{2,4,6\}$, we fix a density function from $\mathbb C^{(m-1)}$ for all $z_t$ (thus the c.d.f. $F$ belongs to $\CC^{(m)}$). Specifically, we set the p.d.f. of $z_t$ as $f_m(x)\varpropto({1}/{4}-x^2)^{m/2}\cdot\II_{\{|x|\le 1/2\}}$ for $m\in \{2,4,6\}$. Moreover, for each $m$, the covariates $\xb_t\in\RR^{3}$ are generated from a p.d.f. in $\CC^{(m)}$ in the following ways:
When implementing our algorithm, we divide the time horizon into consecutive episodes by setting the length of the $k$-th episode as $\ell_k=2^{k-1}\ell_0$ with $k\in\NN^{+}$ and $\ell_0=200$. We further separate every episode into an exploration phase with length $|I_k|=\min\{(d\ell_k)^{(2 m+1)/(4 m-1)},\ell_k\}$ depending on the values of $m$ and $d$. The exploitation phase contains the rest of the time in that episode. In the exploration phase, we sample $p_t$ from $\textrm{Unif}(0,B=6)$, since $B=6$ is a valid upper bound of $v_t$. In the exploitation phase, we set the kernels as follows: For any given $m\in \{2,4,6\}$ prefixed at the beginning of the algorithm, we choose the kernel function with $m$-th order. Here we choose the second, fourth, sixth-order kernel functions as $K_2(u)=35/12(1-u^2)^3\cdot \II_{\{|u|\le 1\}}$, $K_4(u)=27/16(1-11/3u^2)\cdot K_2(u)$ and $K_6(u)=297/128(1-26/3 u^2+13u^4)\cdot K_2(u)$ respectively. In episode $k$, we set the bandwidth $b_k$ as $3\cdot |I_k|^{-\frac{1}{2m+1}}$ in (ref) and (ref) according to the settings in the theoretical analysis. In reality, one can also tune the bandwidth by using cross validation at the end of every exploration phase. Moreover, when calculating $p_t=\hat g(\tilde{\xb}_t^\top\hat\btheta_k)=\tilde{\xb}_t^\top\hat\btheta_k+\hat\phi_k^{-1}(-\tilde{\xb}_t^\top\hat\btheta_k)$, we find $\hat\phi_k^{-1}(-\tilde{\xb}_t^\top\hat\btheta_k)$ as follows: First, we look for $x\in[-1,1]$ such that $\hat\phi_k(x)=-\tilde{\xb}_t^\top\hat \btheta_k$ (The interval $[-1,1]$ contains the true support of $\phi(x)$ [-0.5, 0.5], since in reality, we might only know a range of the true support). Then, we do a transformation of variable $x$ to $x(y)=-2\cdot \exp(y)/(1+\exp(y))+1$ and solve $y$ as the root of $\hat\phi_k(x(y))+\tilde{\xb}_t^\top\hat \btheta_k=0$ by using Newton's method starting at $y=0$. Finally, we set $x=-2\cdot \exp(y)/(1+\exp(y))+1$ as $\hat\phi_k^{-1}(-\tilde{\xb}_t^\top\hat\btheta_k)$ and offer $p_t$ according to the algorithm.
For any given $m\in\{2,4,6\}$, under the three covariate settings discussed above, we input $m$ into the algorithm, select the corresponding kernel and repeat Algorithm (ref) for $30$ times until $T=6300$. For each $T\in[1500,2000,3100,4000,5000,6300]$, we record the cumulative regret reg$(T)$. For the first two covariate settings, recall from Theorem (ref) that the regret reg$(T)\lesssim T^{\frac{2m+1}{4 m-1}}\log^2 T$. Thus, we plot $\tilde{\textrm{reg}}(T)$ against $\log(T)-\log(1500)$ in Figure (ref)-(ref), where $\tilde{\textrm{reg}}(T):=\log(\textrm{reg}(T))-2\log\log T-(\log(\textrm{reg}(1500))-2\log\log 1500)$;
{From Figures (ref)-(ref), we conclude that under all settings, the rates of the empirical regrets' increments produced by Algorithm (ref) (as shown by the solid blue lines) do not exceed their theoretical counterparts given in Theorems (ref) and (ref) (as shown by the dashed black lines). In many cases, the growth rates of the empirical regrets are very close to those of the theoretical lines. This demonstrates the tightness of our theoretical results. Moreover, as all the solid lines have similar growth rates, we show that Algorithm (ref) is robust to the estimation of $\btheta_0$ and $g(\cdot)$. This is further proved in Appendix (ref), where we directly plot reg$(T)$ for all the settings discussed here. See Appendix (ref) for more plots and discussions.}
\textcolor{black}{In this subsection, we provide numerical studies which illustrate differences between our methods and two highly related prior arts (`RMLP-2' and `Bandit') using both synthetic and real data. Here, `RMLP-2' is the policy proposed in JN19 that solves the same problem as ours except that the noise distribution falls in a parametric function class. In addition, we denote the policy proposed in KL03 as 'Bandit', which leverages a variant of UCB algorithm under non-parametric noise distribution that achieves $\cO(\sqrt{T})$ regret without modeling covariate information. }
\textcolor{black}{We first use synthetic data to illustrate the efficiency of our method over `RMLP-2' and `Bandit'. For each smoothness degree $m=\{2,4,6\},$ we generate our data following the same way given in \S(ref), except that we only generate the distribution of $\xb_t$ according to the first option discussed in \S(ref). We illustrate the performance of our method against those two prior arts in the following figures. Here we follow Algorithm (ref) which uses a data-driven way to determine $m$ before every episode. For RMLP-2, since there is no way the algorithm knows the true noise distribution, we instead assume the noise falls into a Gaussian distribution when executing the algorithm.}
\textcolor{black}{We see from the simulation results that the regret we achieved is much smaller than those two benchmarks. As for the comparison with RMLP-2, our method is robust to the mis-specification of the parametric function class since our algorithm can adapt to all functions in the non-parametric class. For the comparison with 'Bandit', we see that only using the non-parametric bandit algorithm without considering the contextual information (heterogeneity of product) will lose much efficiency in gaining revenue. }
\textcolor{black}{Next, we leverage a simulation based on the real data to further illustrate the merits of our Algorithm over 'RMLP-2' and 'Bandit'.}
\textcolor{black}{ We use the real-life auto loan dataset provided by the Center for Pricing and Revenue Management at Columbia University. This dataset is used by several related works Phillips2015,Ban2020PersonalizedDP,LSL21,WWSC20 and many others. The dataset contains $208,085$ auto loan applications received from July 2002 to November 2004. Some features such as the amount of loan, the borrower's information is contained in that dataset. We adopt the feature selection in the same way with Ban2020PersonalizedDP,LSL21,WWSC20 and consider the following four features: the loan amount approved, FICO score, prime rate and competitor's rate. As for the price variable, we also computed it in the same way with the aforementioned literature, where $p_t=\textrm{Monthly Payment}\cdot \sum_{t=1}^{\textrm{Term}}(1+\textrm{Rate})^{-t}-\textrm{Loan Amount}$. The rate is set as $0.12\% $, which is an approximate average of the monthly London interbank rate for the studied time period. Moreover, this dataset also records purchasing decision of the borrowers given the price set by the lender. For more details on this dataset, please refer to Phillips2015,Ban2020PersonalizedDP. }
\textcolor{black}{Note that one is not able to obtain online responses to any algorithms, thus, we follow the calibration idea proposed in Ban2020PersonalizedDP,LSL21,WCCG2020 to first estimate the binary choice model and leverage it as the ground truth to conduct online numerical experiments. To be more specific, we first scale all variables into the scale of $[0,1] $ (since the prediction results of single index model won't be affected by scale of the covariates). We randomly sample 5000 data points, estimate $\btheta_0$ and $F$ using semi-parametric estimation tools from these data. We next treat them as the underlying true parameters for our binary choice model stated in (ref). Given these key components, the remaining experiments remain almost the same as discussed in \S(ref) and \S(ref), except that here we set $\btheta_0$, distribution $F(\cdot)$ as the estimated one given above and sample $\xb_t$ from those four features above. We set $B_0=4,\ell_0=200$ and conduct Algorithm (ref) (in this algorithm, we use cross-validation to select $m$ at the beginning of every episode, details are given in Algorithm (ref)). }
\textcolor{black}{We next compare Algorithm (ref) with `RMLP-2' and `Bandit' policies. The details are given in Figure (ref). }
\textcolor{black}{To summarize, our policy outperforms the RMLP-2 JN19 and non-parametric bandit policy kleinberg2003 in terms of both the regret performance and the ability to adapt to different noise distributions.}
In this paper, we study the contextual dynamic pricing problem where the market value is linear in features, and the market noise has unknown distribution. We propose a policy that combines semi-parametric statistical estimation and online decision making. Our policy achieves near optimal regret, and is close to the regret lower bound where the market noise distribution belongs to a parametric class. We further generalize these results to the case when the product features satisfy the strong mixing condition. The practical performance of the algorithm is proved by extensive simulations.
There are several directions worth exploring in the future. First, we conjecture that the estimation accuracy of the market noise distribution $F$ is crucial in the regret. Thus, within the function class $F\in \CC^{(m)}$, we conjecture that a tighter regret lower bound $\Omega_d(T^\frac{2m+1}{4m-1})$ can be achieved instead of $\Omega_d(\sqrt{T})$, namely, our procedure is optimal. Second, in this work, we consider a linear model for the market value. In case a more complex model is appropriate, it's possible to extend our methodology to where the market value is nonlinear in product features, e.g. $v_t = \phi(\btheta_0^\top \xb_t) + z_t$ or other structured statistical machine learning model such as the additive model $v_t = f_1(x_{t1}) + \cdots + f_d(x_{td}) + z_t$. Finally, it's worth studying similar pricing problems with adversarial or strategic buyers, which is potentially more suitable in some specific applications.