Pricing with Contextual Elasticity and Heteroscedastic Valuation

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.

49,992 characters · 16 sections · 49 citation commands

Rendered from LaTeX for readability, not typeset faithfully. Citation keys are highlighted; maths is left as source; figures, tables and equation environments are summarised rather than reproduced; unrecognised commands are greyed out so nothing is silently dropped. Email addresses are removed.

abstractWe study an online contextual dynamic pricing problem, where customers decide whether to purchase a product based on its features and price. We introduce a novel approach to modeling a customer's expected demand by incorporating feature-based price elasticity, which can be equivalently represented as a valuation with heteroscedastic noise. To solve the problem, we propose a computationally efficient algorithm called "Pricing with Perturbation (PwP)", which enjoys an $O(\sqrt{dT\log T})$ regret while allowing arbitrary adversarial input context sequences. We also prove a matching lower bound at $\Omega(\sqrt{dT})$ to show the optimality regarding $d$ and $T$ (up to $\log T$ factors). Our results shed light on the relationship between contextual elasticity and heteroscedastic valuation, providing insights for effective and practical pricing strategies.

Introduction

Contextual pricing, a.k.a., Feature-based dynamic pricing, considers the problem of setting prices for a sequence of highly specialized or individualized products. With the growth of e-commerce and the increasing popularity of online retailers as well as customers, there has been a growing interest in this area amin2014repeated, qiang2016dynamic, javanmard2019dynamic, shah2019semi, cohen2020feature_journal, xu2021logarithmic, bu2022context.

Formulated as a learning problem, the seller has no prior knowledge of ideal prices but is expected to learn on the fly by exploring different prices and adjusting their pricing strategy after collecting every demand feedback from customers. Different from non-contextual dynamic pricing kleinberg2003value where identical products are sold repeatedly, a contextual pricing agent is expected to generalize from one product to another in order to successfully price a previously-unseen product. A formal problem setup is described below:

\fbox{\parbox{0.97\textwidth}{Contextual pricing. For $t=1,2,...,T:$

enumerate[leftmargin=*,align=left] {0pt} • A product occurs, described by a context $x_t\in\mathbb{R}^{d}$. • The seller (we) proposes a price $p_t\geq0$. • The customer reveals a demand $0\leq D_t\leq 1$. • The seller gets a reward $r_t = p_t\cdot D_t$.

} }

Here $T$ is the time horizon, and the (random) demand $D_t$ is drawn from a distribution determined by context (or feature) $x_t$ and price $p_t$. The sequence of contexts $\{x_t\}$ can be either independently and identically distributed (iids) or chosen arbitrarily by an adversary. The seller's goal is to minimize the cumulative regret against the sequence of optimal prices.

Existing works on contextual pricing usually assumes linearity on the demand, but they fall into two camps. On the one hand, the "linear demand" camp qiang2016dynamic, ban2021personalized, bu2022context assumes the demand $D_t$ as a (generalized) linear model. A typical model is $D_t = \lambda(\alpha p_t + x_t^T \beta) + \epsilon_t$. Here $\alpha<0$ is a parameter closely related to the price elasticity. We will rigorously define a price elasticity in (ref) according to parkin2002economics, where we also show that $\alpha$ is the coefficient of elasticity. Besides of $\alpha$, other parameters like $\beta\in\mathbb{R}^d$ captures the base demand of products with feature $x_t$, $\epsilon_t$ is a zero-mean demand noise, and $\lambda$ is a known monotonically increasing link function. With this model, we have a noisy observation on the expected demand, which is reasonable as the same product is offered many times in period $t$. On the other hand, the "linear valuation" camp cohen2020feature_journal, javanmard2019dynamic, xu2021logarithmic models a buyer's valuation $y_t$ as linear and assumes a binary demand $D_t = \mathds{1}[p_t\leq y_t]$. All three works listed above assume a linear-and-noisy model with $y_t=x_t^\top\theta^*+N_t$, where $\theta^*\in\mathbb{R}^d$ is an unknown linear parameter that captures common valuations and $N_t$ is an idiosyncratic noise assumed to be iid.

Interestingly, the seemingly different modeling principles are closely connected to each other. In the "linear valuation" camp, notice that a customer's probability of "buying" a product equals $\mathbb{E}[D_t]$, which is further given by

$$ \mathbb{E}[D_t|p] = \mathbb{P}[y_t \geq p ] := S(p-x_t^\top\theta^*), $$

where $S$ is the survival function of $N_t$ (i.e. $S(w)=1-\mathrm{CDF}(w)$ for $w\in\mathbb{R}$). This recovers a typical linear demand model by taking $\lambda(w)=S(-w)$ with $\alpha = -1$ and $\beta = \theta^*$. In other words, the distribution of $N_t$ completely characterizes the demand function $\lambda(\cdot)$ and vice versa.

However, the "linear demand" camp is not satisfied with a fixed $\alpha = -1$, while the "linear valuation" camp are skeptical about an observable demand $D_t$ even with zero-mean iid noise. One common limitation to both models is that neither captures how feature $x_t$ affects the price elasticity.

Our model. To address this issue, we propose a natural model that unifies the perspectives of both groups. Also, we resolve the common limitation by modeling heteroscedasticity, where we assume that the elasticity coefficient $\alpha$ is linearly dependent on feature $x_t$. This contextual modeling originates from the fact that different products have different price elasticities anderson1997price.

In specific, we assume:

equation[equation omitted — 101 chars of source]

which adopts a generalized linear demand model (GLM) and a Boolean-censored feedback simultaneously. From the perspective of valuation model, it is equivalent to assume

equation[equation omitted — 186 chars of source]

Although (ref) seems more natural than (ref), they are equivalent to each other (with reasonable assumptions on $S$). Notice that the random valuation $y_t$ is heteroscedastic, which means its variance is not the same constant across a variety of $x_t$'s. We provide a detailed interpretation of this linear fractional valuation model in appendix.

Contributions.

Our main results are twofold.

enumerate[leftmargin=*] • We propose a new demand model that assumes a feature-dependent price elasticity on every product. Equivalently, we model the heteroscedasticity on customers' valuations among different products. This model unifies the “linear demand” and “linear valuation” camps. • We propose a “Pricing with Perturbation (PwP)” algorithm that achieves $O(\sqrt{dT\log T})$ regret on this model, which is optimal up to $\log T$ factors. This regret upper bound holds for both i.i.d. and adversarial $\{x_t\}$ sequences.

Technical Novelty

To the best of our knowledge, we are the first to study a contextual pricing problem with heteroscedastic valuation and Boolean-censored feedback. Some existing works, including javanmard2019dynamic, miao2019context, ban2021personalized, wang2021dynamic, focus on related topics and achieve theoretical guarantees. However, their methodologies are not applicable to our settings due to substantial obstacles, which we propose novel techniques to overcome.

Randomized surrogate regret. \Citet{xu2021logarithmic} solves the problem with $x_t^\top\eta^*=1$, by taking the negative log-likelihood as a surrogate regret and running an optimization oracle that achieves a fast rate (i.e. an $O(\log T)$ regret). However, the log-likelihood is no longer a surrogate regret in our setting, since it is not "convex enough" and therefore cannot provide sufficient (Fisher) information. In this work, we overcome this challenge by constructing a randomized surrogate loss function, whose expectation is "strongly convex" enough to upper bound the regret.

OCO for adversarial inputs. javanmard2019dynamic and ban2021personalized study the problem with unknown or heterogeneous noise variances (i.e. elasticity coefficients), but their techniques highly rely on the distribution of the feature distributions. As a result, their algorithm could be easily attacked by an adversarial $\{x_t\}$ series. In our work, we settle this issue by conducting an online convex optimization (OCO) scheme while updating parameters. Instead of estimating from the history that requires sufficient randomness in the inputs, our algorithm can still work well for adversarial inputs.

In addition, our algorithm has more advanced properties such as computational efficiency and information-theoretical optimality. For more highlights of our algorithm, please refer to (ref).

Related Works

Here we present a review of the pertinent literature on contextual pricing and heteroscedasticity in machine learning, aiming to position our work within the context of related studies. For more related works on non-contextual pricing, contextual pricing, contextual searching and contextual bandits, please refer to wang2021multimodal, xu2021logarithmic, krishnamurthy2020contextual and zhou2015survey respectively.

\paragraph{Contextual Pricing.} As we mentioned in (ref), there are a large number of recent works on contextual dynamic pricing problems, and we refer to ban2021personalized as a detailed introduction. On the one hand, qiang2016dynamic, nambiar2019dynamic, miao2019context, wang2021dynamic, ban2021personalized, bu2022context assume a (generalized) linear demand model with noise, i.e. $\mathbb{E}[D_t] = g(\alpha p_t - \beta^\top x_t)$. Among those papers, miao2019context worksl with a fixed $\alpha$ while we assume $\alpha$ as context-dependent. wang2021dynamic and ban2021personalized are the closest to our problem setting, which consist of a generalized linear demand model and noisy observations. On the one hand, ban2021personalized assumes independent add-on noises (while we allow binary martingale observations). With the development of a least-square estimator, they present an algorithm that achieves $\tilde{O}(s\sqrt{T})$ regret (with $s$ being the sparsity factor). On the other hand, wang2021dynamic further gets rid of the independence among noises and allow them to be idiosyncratic. They proposes a UCB-based algorithm with $\tilde{O}(d\sqrt{T})$ regret and another Thompson-Sampling-based algorithm with $\tilde{O}(d^{\frac32}\sqrt{T})$ regret, both of which are sub-optimal in $d$. Moreover, all works mentioned above assume the context sequence $\{x_t\}$ to be i.i.d., whereas we consider it "too good to be true" and work towards an algorithm adaptive to adversarial input sequences. On the other hand, golrezaei2019incentive, shah2019semi, cohen2020feature_journal, javanmard2019dynamic, xu2021logarithmic, fan2021policy, goyal2021dynamic, luo2022contextual adopts the linear valuation model $y_t=x_t^\top\theta^*+N_t$, which is a special case of our model as $x_t^\top\eta^*=1$. Specifically, both javanmard2019dynamic and xu2021logarithmic achieve an $O(d\log T)$ regret with $N_t$ drawn from a known distribution with $x_t^\top\eta^* = -1$. javanmard2019dynamic also studies the setting when $x_t^\top\eta^*$ is fixed but unknown and achieves $O(d\sqrt{T})$ regret for stochastic $\{x_t\}$ sequences. In comparison, we achieve $O(\sqrt{dT\log T})$ on a more general problem and get rid of those assumptions. For a more detailed discussion, please refer to (ref).

table[table omitted — 2,343 chars of source]

\paragraph{Heteroscedasticity.} Since the valuation noise is scaled by a $\frac1{x_t^\top\eta^*}$ coefficient, the valuation is heteroscedastic, referring to a situation where the variance is not the same constant across all observations. Heteroscedasticity may lead to bias estimates or loss of sample information. There are several existing methods handling this problem, including weighted least squares method cunia1964weighted, White's test white1980heteroskedasticity and Breusch-Pagan test breusch1979simple. Furthermore, anava2016heteroscedastic and chaudhuri2017active study online learning problems with heteroscedastic variances and provide regret bounds. For a formal and detailed introduction, we refer the audience to the textbook of kaufman2013heteroskedasticity.

Problem Setup

Notations

To formulate the problem, we firstly introduce necessary notations and symbols used in the following sections. The sales session contains $T$ rounds with $T$ known to the seller in advance\footnote{Here we assume $T$ known for simplicity. For unknown $T$, we may apply a “doubling epoch” trick as javanmard2019dynamic without affecting the regret rate.}. At each time $t=1,2,\ldots, T$, a product with feature $x_t\in\mathbb{R}^d$ occurs and we propose a price $p_t\geq 0$. Then the nature draws a demand $D_t\sim \mathrm{Ber}(S(x_t^\top\eta^*\cdot p_t -x_t^\top\theta^*))$, where $\theta^*, \eta^*\in\mathbb{R}^d$ are fixed unknown linear parameters and the link function $S: \mathbb{R}\rightarrow[0,1]$ is non-increasing. By the end of time $t$, we receive a reward $r_t = p_t\cdot D_t$.

Equivalently, this customer has a valuation $y_t=\frac{x_t^\top\theta^* + N_t}{x_t^\top\eta^*}$ with noise $N_t\in\mathbb{R}$, and then make a decision $\mathds{1}_t = \mathds{1}[p_t\leq y_t]=D_t$ after seeing the price $p_t$. Similarly, we receive a reward $r_t = p_t\cdot\mathds{1}_t$. Assume $N_t\sim\mathbb{D}_F$ is independently and identically distributed (i.i.d.), with cumulative distribution function (CDF) $F=1-S$. Denote $s:=S'$ and $f:=F'$.

Definitions

Here we define some key quantities. Firstly, we define an expected reward function.

definition[expected reward function] Define \begin{equation} \begin{aligned} r(u, \beta, p):=\mathbb{E}[r_t|x_t^\top\theta^*=u, x_t^\top\eta^*=\beta, p_t = p]= p\cdot S(\beta\cdot p-u) \end{aligned} \end{equation} as the expected reward function.

Given this, we further define a greedy price function as the argmax of $r(u,\beta,p)$ over $p$.

definition[greedy price function] Define $J(u,\beta)$ as a greedy price function, i.e. the price that maximizes the expected reward given $u=x_t^\top\theta^*$ and $\beta=x_t^{\top}\eta^*$. \begin{equation} \begin{aligned} J(u,\beta) = \mathop{\mathrm{argmax}}_{p\in\mathbb{R}}r(u, \beta, p)=\mathop{\mathrm{argmax}}_{p\in\mathbb{R}}p\cdot S(\beta\cdot p - u)\\ \end{aligned} \end{equation}

Notice that

equation[equation omitted — 179 chars of source]

According to xu2021logarithmic, we have the following properties.

lemmaDenote $\varphi(w):=-\frac{S(w)}{s(w)}-w=\frac{1-F(w)}{f(w)}-w$, and we have $J(u, \beta)=\frac{u+\varphi^{-1}(u)}{\beta}$. Also, for $u\geq0$ and $\beta>0$, we have $\frac{\partial J(u, \beta)}{\partial u}\in(0,1)$.

Then we define a negative log-likelihood function of parameter hypothesis ($\theta, \eta$) given the results at time $t$.

definition[log-likelihood functions] Denote $\ell_t(\theta, \eta)$ as the negative log-likelihood at time $t$, and define $L_t(\theta, \eta)$ as their summations: \begin{equation} \begin{aligned} -\ell_t(\theta, \eta)=&\mathds{1}_t\cdot\log S(x_t\top\eta\cdot p_t - x_t^\top\theta)+(1-\mathds{1}_t)\cdot\log(1-S(x_t^{\top}\eta\cdot p_t - x_t^\top\theta)).\\ L_t(\theta, \eta)=&\sum_{\tau=1}^t \ell_t. \end{aligned} \end{equation}

Finally, we define a round-$t$ expected regret and a cumulative expected regret.

definition[regrets] Define $Reg_t(p_t):= r(x_t^\top\theta^*, x_t^\top\eta^*, J(x_t^\top\theta^*, x_t^\top\eta^*)) - r(x_t^\top\theta^*, x_t^\top\eta^*, p_t)$ as the expected regret at round $t$, conditioning on price $p_t$. Also, define the cumulative regret as follows \begin{equation} \begin{aligned} Regret = \sum_{t=1}^{T} Reg_t(p_t) \end{aligned} \end{equation}

Assumptions

We establish three technical assumptions to make our analysis and presentation clearer. Firstly, we assume that all feature and parameter vectors are bounded within a unit ball in Euclidean norm. This assumption is without loss of generality as it only rescales the problem.

assumption[bounded feature and parameter spaces] Assume features $x_t\in\mathcal{H}_x$ and parameters $\theta\in\mathcal{H}_{\theta}, \eta\in\mathcal{H}_{\eta}$. Denote $U_p^d:=\{x\in\mathbb{R}^d, \|x\|_p\leq 1\}$ as an $L_p$-norm unit ball in $\mathbb{R}^d$. Assume all $\mathcal{H}_x, \mathcal{H}_{\theta}, \mathcal{H}_{\eta}\in U_p^d$. Also, assume $x^\top\theta>0, \forall x\in\mathcal{H}_x, \theta\in\mathcal{H}_{\theta}$ and $x^\top\eta>C_{\beta}>0, \forall x\in\mathcal{H}_x, \eta\in\mathcal{H}_{\eta}$ for some constant $C_{\beta}\in(0,1)$.

The positiveness of elasticity coefficient $x^\top\eta>0$ comes from the Law of Demand gale1955law, hildenbrand1983law, stating that the quantity purchased varies inversely with price. This is derived from the Law of Diminishing Marginal Utilities and has been widely accepted marshall2009principles. We will show the necessity of assuming an elasticity lower bound $C_{\beta}$ in (ref). In specific, we claim that any algorithm will suffer a regret of $\Omega(\frac1{C_{\beta}})$. For the simplicity of notation, we denote $[\theta; \eta]:=[\theta^\top, \eta^\top]^\top\in\mathbb{R}^{2d}$ as the combination of $d$-dimension column vectors $\theta$ and $\eta$. Since we know that $x_t^\top\theta\in[0,1]$ and $x_t^\top\eta\in[C_{\beta}, 1]$, we have $J(x_t^\top\theta, x_t^\top\eta)\in[J(0,1), J(1, C_{\beta})]$. Later we will show that the price perturbation is no more than $\frac{J(0,1)}{10}$. Therefore, we may have the following assumption.

assumption[bounded prices] For any price $p_t$ at each time $t=1,2,\ldots, T$, we require $p_t\in[c_1, c_2]$, where $c_1 = \frac{J(0,1)}2$ and $c_2 = 2J(1, C_\beta)$.

Similar to javanmard2019dynamic and xu2021logarithmic, we also assume a log-concavity on the noise CDF.

assumption[log-concavity] Every $D_t$ is independently sampled according to (ref), with $S(\omega)\in[0,1]$ and $s(\omega)=S'(\omega)>0, \forall \omega\in\mathbb{R}$. Equivalently, the valuation noise $N_t\sim\mathbb{D}_F$ is independently and identically distributed (i.i.d.), with CDF $F=1-S$. Assume that $S\in\mathbb{C}^2$, and $S$ and $(1-S)$ are strictly log-concave.

Main Results

To solve the contextual pricing problem with featurized elasticity, we propose our “Pricing with Perturbation (PwP)” algorithm. In the following, we firstly describe the algorithm and highlight its properties, then analyze (and bound) its cumulative regret, and finally prove a regret lower bound to show its optimality.

Algorithm

The pseudocode of PwP is displayed as (ref), which calls an ONS oracle ((ref)).

algorithm[algorithm omitted — 1,118 chars of source]

algorithm[algorithm omitted — 715 chars of source]

At each time $t$, it inherits parameters $\theta_t$ and $\eta_t$ from $(t-1)$ and takes in a context vector $x_t$. By trusting in $\theta_t$ and $\eta_t$, it calculates a greedy price $\hat p_t$ and outputs a perturbed version $p_t = \hat p_t + \Delta_t$. After seeing customer's decision $\mathds{1}_t$, PwP calls an “Online Newton Step (ONS)” oracle (see (ref)) to update the parameters as $\theta_{t+1}$ and $\eta_{t+1}$ for future use.

Highlights

We highlight the achievements of the PwP algorithm in the following three aspects.

In this pricing problem. As we mentioned in (ref), the key to solving this contextual elasticity (or heteroscedastic valuation) pricing problem is to construct a surrogate loss function. xu2021logarithmic adopts negative log-likelihood in their setting, which does not work for ours since it is not "convex" enough. In our PwP algorithm, we overcome this challenge by introducing a perturbation $\Delta$ on the proposed greedy price. This idea originates from the observation that the variance of $p_t$ contributes positively to the "convexity" of the expected log-likelihood, which helps "re-build" the upper-bound inequality.

In online optimization. PwP perturbs the greedy action (price) it should have taken. This idea is similar to a "Following the Perturbed Leader (FTPL)" algorithm hutter2005adaptive that minimizes the summation of the empirical risk and a random loss function serving as a perturbation. However, this might lead to extra computational cost as the random perturbation is not necessarily smooth and therefore hard to optimize. In this work, PwP introduces a possible way to overcome this obstacle: Instead of perturbing the objective function, we may directly perturb the action to explore its neighborhood. Our regret analysis and results indicate the optimality of this method and imply a potentially wide application.

In information theory. We show the following fact in the regret analysis of PwP: By adding $\Delta$ perturbation on $p_t$, we may lose $O(\Delta^2)$ in reward but will gain $O(\Delta^2)\cdot I$ in Fisher information (i.e. the expected Hessian of negative log-likelihood function) in return. By Cramer-Rao Bound, this leads to $O(\frac1{\Delta^2})$ estimation error. In this way, we quantify the information (observing from exploration) on the scale of reward, which shares the same idea with the Upper Confidence Bound lai1985asymptotically method that always maximizes the summation of empirical reward and information-traded reward.

Besides, PwP is computationally efficient as it only calls the ONS oracle for once. As for the ONS oracle, it updates an $A_t^{-1} = (A_{t-1} + \nabla_t\nabla_t^\top)^{-1}$ at each time $t$, which is with $O(d^2)$ time complexity according to the following Woodbury matrix identity

equation[equation omitted — 111 chars of source]

Regret Upper Bound

Now we analyze the regret of PwP and propose an upper bound up to constant coefficients.

theoremUnder (ref), (ref) and (ref), by taking $\Delta = \min\left\{\left(\frac{d\log T}{T}\right)^{\frac14}, \frac{J(0,1)}{10}, \frac1{10}\right\}$, the algorithm PwP guarantees an expected regret at $O(\sqrt{dT\log T})$.

In the following, we prove (ref) by stating a thread of key lemmas. We leave the detailed proof of those lemmas to (ref).

proofThe proof overview can be displayed as the following roadmap of inequalities: \begin{equation} \begin{aligned} \mathbb{E}[Regret] =\sum_{t=1}^T Reg_t(p_t)\leq&\mathbb{E}\left[\sum_{t=1}^T O\left((x_t^\top(\theta_t-\theta^*))^2 + (x_t^\top(\eta_t-\eta^*))^2 + \Delta^2\right)\right]\\ \leq&O\left(\frac{\sum_{t=1}^T \mathbb{E}\left[\ell_t(\theta_t, \eta_t) - \ell_t(\theta^*, \eta^*)\right]}{\Delta^2} + T\cdot\Delta^2\right)\\ \leq&O\left(\frac{d\log T}{\Delta^2} + T\cdot\Delta^2\right) =O(\sqrt{dT\log T}). \end{aligned} \end{equation} Here the first inequality is by the smoothness of regret function (see (ref)), the second inequality is by a special “strong convexity” of $\ell_t(\theta, \eta)$ that contributes to the surrogate loss (see (ref)), the third inequality is by Online Newton Step (see (ref)), and the last equality is by the value of $\Delta$. A rigorous version of (ref) can be found in (ref). We firstly show the smoothness of $Reg_t(p_t)$: \begin{lemma}[regret smoothness] Denote $p_t^*:=J(x_t^\top\theta^*, x_t^\top\eta^*)$. There exists constants $C_r>0$ and $C_J>0$ such that \begin{equation} \begin{aligned} Reg_t(p_t) \leq C_r\cdot (p_t-p_t^*)^2\leq C_r\cdot 2\left(C_J\cdot\left[(x_t^\top(\theta_t-\theta^*))^2 + (x_t^\top(\eta_t-\eta^*))^2\right] + \Delta^2\right). \end{aligned} \end{equation} \end{lemma} While the first inequality of (ref) is from the smoothness, and the second inequality is by the Lipschitzness of function $J(u, \beta)$. Please refer to (ref) for proof details. We then show the reason why the log-likelihood function can still be a surrogate loss with carefully randomized $p_t$. \begin{lemma}[surrogate expected regret] There exists a constant $C_l>0$ such that $\forall \theta\in\mathcal{H}_\theta, \eta\in\mathcal{H}_\eta$, we have \begin{equation} \begin{aligned} &\mathbb{E}[\ell_t(\theta, \eta) - \ell_t(\theta^*, \eta^*)|\theta_t, \eta_t]\\ \geq&\frac{C_l\Delta^2}{10}[(\theta-\theta^*)^\top, (\eta-\eta^*)^\top] \left[\begin{array}{cc} x_tx_t^\top & 0\\ 0 & x_tx_t^\top \end{array} \right] \left[\begin{array}{c} \theta-\theta^*\\ \eta-\eta^* \end{array} \right]\\ =&\frac{C_l\cdot \Delta^2}{10}\left[\left(x_t^\top(\theta-\theta^*)\right)^2 + \left(x_t^\top(\eta-\eta^*)\right)^2\right]. \end{aligned} \end{equation} \end{lemma} This is the most important lemma in this work. We show a proof sketch here and defer the detailed proof to (ref). \begin{proof}[Proof sketch of (ref)] We show that there exist constants $C_l>0, C_p>0$ such that \begin{enumerate} • $\nabla^2 \ell_t(\theta, \eta)\succeq C_l\cdot\left[ \begin{array}{cc} x_tx_t^\top & -p_t\cdot x_tx_t^\top\\ -p_t\cdot x_tx_t^\top & p_t^2\cdot x_tx_t^\top \end{array} \right]$, and • $\mathbb{E}\left[ \begin{array}{cc} x_tx_t^\top & -p_t\cdot x_tx_t^\top\\ -p_t\cdot x_tx_t^\top & p_t^2\cdot x_tx_t^\top \end{array} |\theta_t, \eta_t\right]\succeq C_p\Delta^2 \left[ \begin{array}{cc} x_tx_t^\top & 0\\ 0 & x_tx_t^\top \end{array} \right]$. \end{enumerate} The first property above relies on the exp-concavity of $\ell_t$. Notice that the second property does not hold without the $\mathbb{E}$ notation, as the left hand side is a $(a-b)^2$ form while the right hand side is in a $(a^2+b^2)$ form. In general, there exist no constant $c>0$ such that $(a-b)^2\geq c(a^2+b^2)$. However, due to the randomness of $p_t$, we have \begin{equation} \mathbb{E}[p_t^2|\hat p_t] = \mathbb{E}[p_t|\hat p_t]^2 + \Delta^2. \end{equation} In this way, the conditional expectation of the left hand side turns to $(a-b)^2 + \lambda\cdot b^2$ and we have \begin{equation} \begin{aligned} (a-b)^2+\lambda b^2=(\frac1{\sqrt{1+\frac{\lambda}2}}\cdot a - \sqrt{1+\frac{\lambda}2}\cdot b)^2 + (1-\frac1{1+\frac{\lambda}2})a^2 + \frac{\lambda}2 b^2\geq\frac{\frac{\lambda}2}{1+\frac{\lambda}2}\cdot(a^2+b^2). \end{aligned} \end{equation} Similarly, we upper bound $\left[\begin{array}{cc} x_tx_t^\top & 0\\ 0 & x_tx_t^\top \end{array}\right]$ with $\mathbb{E}[\nabla^2\ell_t(\theta, \eta)|\theta_t, \eta_t]$ up to a $C_p\cdot\Delta^2$ coefficient. With those two properties above, along with a property of likelihood function that $\mathbb{E}[\nabla\ell_t(\theta^*, \eta^*)]=0$, we can prove (ref) by taking a Taylor expansion of $\ell_t$ at $[\theta^*;\eta^*]$. \end{proof} Finally, we cite a theorem from hazan2019introduction as our (ref) that reveals the surrogate regret rate on negative log-likelihood functions. \begin{lemma} With parameters $G=\sup_{\theta\in\mathcal{H}_{\theta}, \eta\in\mathcal{H}_{\eta}}\|\nabla l_t(\theta, \eta)\|_2$, $D=\sup\|[\theta_1; \eta_1]-[\theta_2;\theta_2]\|\leq2$, $\alpha = C_e$, $\gamma=\frac12\min\{\frac1{4GD}, \alpha\}$ and $\epsilon=\frac1{\gamma^2D^2}$ and $T>4$, Keep running (ref) for $t=1,2,\ldots, T$ guarantees: \begin{equation} \begin{aligned} \sup_{\{x_t\}}\left\{\sum_{t=1}^T\ell_t(\theta_t, \eta_t) - \min_{\theta\in\mathcal{H}_{\theta}, \eta\in\mathcal{H}_{\eta}}\sum_{t=1}^T\ell_t(\theta, \eta)\right\}\leq 5(\frac1{\alpha}+GD)d\log T. \end{aligned} \end{equation} \end{lemma} With all these lemma above, we have proved every line of (ref).

Lower Bounds

We claim that PwP is near-optimal in information theory, by proposing a matching regret lower bound in (ref). We present the proof with valuation model to match with existing results.

theoremConsider the contextual pricing problem setting with Bernoulli demand model given in (ref). With all assumptions in (ref) hold, any pricing algorithm has to suffer a $\Omega(\sqrt{dT})$ worst-case regret, with $T$ the time horizon and $d$ the dimension of context.

proofThe main idea is to reduce $d$ numbers of 1-dimension problems to this problem setting. In fact, we may consider the following problem setting: \begin{enumerate} • Construct set $X=\{x_i:=[0,\ldots, 0,1,0,\ldots,0]^\top\in\mathbb{R}^d\text{ with only }i^{\text{th}}\text{ place being 1}, i=1,2,\ldots, d\}$. • Let $\theta^*=[\frac{u_1}{\sigma_1}, \frac{u_2}{\sigma_2}, \frac{u_3}{\sigma_3}, \ldots, \frac{u_d}{\sigma_d}]^\top, \eta^*=[\frac1{\sigma_1}, \frac1{\sigma_2}, \frac1{\sigma_3}, \ldots, \frac1{\sigma_d}]^\top$, and therefore we have $\frac{x_i^\top\theta^*+N_t}{x_i^\top\eta^*} = u_i + \sigma_i\cdot N_t$. • At each time $t=1,2,\ldots, T$, sample $x_t\sim X$ independently and uniformly at random. \end{enumerate} In this way, we divide the whole time series $T$ into $d$ separated sub-problems, where the Sub-Problem $i$ has a valuation model $y_t(i) = u_i + \sigma_i\cdot N_t$, for $i=1,2,\ldots, d$. Let $N_t\sim\mathcal{N}(0,1), t=1,2,\ldots, T$, and $y_t(i)\sim\mathcal{N}(u_i, \sigma_i^2)$ are independent Gaussian random variables. For each Sub-Problem $i$, it has a time horizon as $\frac Td$ in expectation. Let $u_i=\sqrt{\frac{\pi}2}$ and let each $\sigma_i^2$ be chosen from $\{1, 1-(\frac{T}{d})^{-\frac14}\}$. According to broder2012dynamic and xu2021logarithmic, the regret lower bound of each sub-problem is $\Omega(\sqrt{\frac Td})$. Therefore, the total regret lower bound is $d\cdot\Omega(\sqrt{\frac Td}) = \Omega(\sqrt{Td})$.

Numerical Experiments

figure*[figure* omitted — 1,195 chars of source]

Here we conduct numerical experiments to validate the low-regret performance of our algorithm PwP. Since we are the first to study this heteroscadestic valuation model, we do not have a baseline algorithm working for exactly the same problem. However, we can modify the RMLP-2 algorithm in javanmard2019dynamic by only replacing their max-likelihood estimator (MLE) for $\theta^*$ with a new MLE for both $\theta^*$ and $\eta^*$. This modified RMLP-2 algorithm does not have a regret guarantee in our setting, but it may still serve as a baseline to compare with.

commentIn the following part, we will compare the cumulative regrets of our ONSPP algorithm with the (modified) RMLP-2 in the following two scenarios: \begin{enumerate} • The linear-fractional valuation $y_t = \frac{x_t^\top\theta^* + N_t}{x_t^\top\eta^*}$. • A fully-linear valuation $y_t = x_t^\top\theta^* + x_t^\top\eta^*\cdot N_t$. \end{enumerate} Notice that the second valuation model is also heteroscedastic, but the linear scalar only multiplies with the noise. We design the first experiment to show the regret performance of our algorithm, and the second experiment to imply the generality of our valuation model and our algorithm to model-misspecified settings. In order to show the regret dependence w.r.t. $T$, we plot all cumulative regret curves in log-log plots, where an $\alpha$ slope indicates an $O(T^\alpha)$ dependence. We repeat each experiment for 20 times. \subsection{Performances on well-assumed model} In this part, we test our algorithm ONSPP and the modified RMLP-2 on the correct demand model (as assumed in (ref)) with both stochastic and adversarial $\{x_t\}$ sequences, respectively.

We test PwP and the modified RMLP-2 on the demand model assumed in (ref) with both stochastic and adversarial $\{x_t\}$ sequences, respectively. Basically, we assume $T=2^{16}$ $d=2$, $N_t\sim\mathcal{N}(0, \sigma^2)$ with $\sigma=0.5$, and we repeatedly run each algorithm for 20 times in each experiment setting. In order to show the regret dependence w.r.t. $T$, we plot all cumulative regret curves in log-log plots, where an $\alpha$ slope indicates an $O(T^\alpha)$ dependence.

\paragraph{Stochastic $\{x_t\}$.} We implement and test PwP and RMLP-2 on stochastic $\{x_t\}$'s, where $x_t$ are iid sampled from $\mathcal{N}(\mu_x, \Sigma_x)$ (for $\mu_x = [10, 10, \ldots, 10]^\top$ and some randomly sampled $\Sigma_x$) and then normalized s.t. $\|x_t\|_2\leq 1$. The numerical results are shown in (ref). Numerical results show that both algorithms achieve $\sim O(T^{0.56})$ regrets, which is close to the theoretic regret rate at $O(\sqrt{T\log T})$.

\paragraph{Adversarial $\{x_t\}$.} Here we design an adversarial $\{x_t\}$ sequence to attack both algorithms. Since RMLP-2 divides the whole time horizon $T$ into epochs with length $k=1,2,3,\ldots$ sequentially and then does pure exploration at the beginning of each epoch, we may directly attack those pure-exploration rounds in the following way: (1) In each pure-exploration round (i.e. when $t=1,3,6,\ldots, \frac{k(k+1)}2, \ldots$), let the context be $x_t=[1,0]^{\top}$; (2) In any other round, let the context be $x_t=[0,1]^{\top}$. In this way, the RMLP-2 algorithm will never learn $\theta^*[2]$ and $\eta^*[2]$ since the inputs of pure-exploration rounds do not contain this information. Under this oblivious adversarial context sequence, we implement PwP and RMLP-2 and compare their performance. The results are shown in (ref), indicating that PwP can still guarantee $O(T^{0.513})$ regret (close to $O(\sqrt{T\log T})$) while RMLP-2 runs into a linear regret.

As a high-level interpretation, the performance difference is because PwP adopts a "distributed" exploration at every time $t$ while RMLP-2 makes it more "concentrated". Although both PwP and RMLP-2 take the same amount of exploration that optimally balance the reward loss and the information gain (and that is why they both perform well in stochastic inputs), randomly distributed exploration would save the algorithm from being "attacked" by oblivious adversary. In fact, this phenomenon is analog to $\epsilon$-Greedy versus Exploration-first algorithms in multi-armed bandits. We will discuss more in (ref).

So far, we have presented the numerical results of running PwP and a modified RMLP-2 on the well-assumed demand model as (ref) (or (ref) equivalently). Besides of that, we also conduct experiments on a model-misspecification setting to show the robustness, where the true demand (or valuation) distribution is not the same as (ref) or (ref). The numerical results are presented in (ref).

comment\begin{figure}[t] \caption{Regrets of misspecified ONSPP with expanded contexts, in comparison with a baseline RMLP-2 knowing the correct model. The results show that ONSPP still have a sub-linear regret with context expansions, indicating that our GLM with Boolean demand model shown in (ref) can be generalized to the fully-linear model of (ref) in practice.} \end{figure} \subsection{Performances on misspecified model} In this subsection, we consider a model-misspecified setting, where the true valuation model is \begin{equation} y_t = x_t^\top\theta^* + x_t^\top\eta^*\cdot N_t \end{equation} However, our ONSPP algorithm still models it as $\tilde{y}_t = \frac{x_t^\top\tilde{\theta}^* + \tilde{N}_t}{\tilde{x}_t^\top\tilde{\eta}^*}$, where $\tilde{x}_t\in\mathbb{R}^q$ is an expanded version of the original context $x_t$ (i.e. $\tilde{x}_t = \pi(x_t)$ for some fixed expanding policy $\pi$) and $\tilde{\theta}^*, \tilde{\eta}^*\in\mathbb{R}^q$ are some fixed parameters\footnote{We may assume $q\geq d$ without loss of generality.}. From the ONSPP's perspective, the noise $\tilde{N_t}$'s are also drawn from the same distribution as $N_t$'s. Therefore, ONSPP is trying to learn those misspecified $\tilde{\theta}^*$ and $\tilde{\eta}^*$ in order to performance well in cumulative regrets. We are curious whether the expansion of context (from $x_t$ to $\tilde{x}_t$) would leverage the hardness of model misspecification. For $x = [x_1, x_2, \ldots, x_d]^\top$, denote $x^n:=[x_1^n, x_2^n, \ldots, x_d^n]^\top$. Then for any context $x\in\mathbb{R}^d$, we specify each context-expanding policy as follows: \begin{equation} \begin{aligned} &\pi(x; x_0, \mathbf{a})\\ :=& [x; (x-x_0)^{a_1}; (x-x_0)^{a_2}; \ldots; (x-x_0)^{a_m}]^\top\in\mathbb{R}^{(m+1)d}. \end{aligned} \end{equation} The policy $\pi$ in (ref) is a polynomial expansion of $x$ with index list $\mathbf{a}=[a_1, a_2, \ldots, a_m]\in\mathbb{Z}^m$, where $x_0\in\mathbb{R}^d$ is a fixed start point of this expansion. Now we consider the baseline to compare with. We claim that it is very challenging to solve the contextual pricing problem with customers' valuations being (ref) with theoretic regret guarantees (although the $\Omega(\sqrt{T})$ lower bound given by javanmard2019dynamic still holds), and there are no existing algorithms targeting at this problem setting. However, there are still some straightforward algorithms that might approach it: For example, a max-likelihood estimate (MLE) of $\theta^*$ and $\eta^*$. In fact, we may still reuse the framework of RMLP-2 by replacing its MLE oracle according to the distribution given by (ref). In the following, we will compare the performances of \begin{enumerate} • ONSPP algorithm on the misspecified valuation model, with expanded context $\{x_t\}$'s, and • RMLP-2 algorithm on the correct fully-linear model ((ref)), with original context $\{x_t\}$'s. \end{enumerate} We implement ONSPP and RMLP-2 on stochastic $\{x_t\}$ sequences (since RMLP-2 has already failed in the adversarial setting) and get numerical results shown as (ref). Here we choose $x_0 = [0.5, 0.5]^\top$ and $\mathbf{a} = [0,1]$. For a model-misspecified online-learning algorithm, there generally exists an $O(\epsilon\cdot T)$ term in the regret rate, where $\epsilon$ is a parameter measuring the distance between the global optimal policy and the best proper policy (i.e. the best policy in the hypothesis set). However, our numerical results imply that ONSPP may still achieve a sub-linear regret even in this model-misspecified setting, whereas the baseline RMLP-2 that takes the correct model runs into a linear regret. These results imply that \begin{enumerate} • Our linear-fractional valuation model of (ref) can be generalized to a fully-linear valuation model of (ref) in practice. • Our ONSPP algorithm can still perform well in model-misspecification settings, and even better than a baseline MLE algorithm on the correct model. \end{enumerate} For the first phenomenon that our valuation model can be generalized with context expansion tricks, we may understand it as a Taylor expansion (and we take a linear approximation) at $x_0=[0.5, 0.5]^\top$. For the second phenomenon that ONSPP outperforms RMLP-2, it might be caused by the non-convexity of the log-likelihood function of the valuation model specified in (ref). As a result, while RMLP-2 is solving a non-convex MLE and getting estimates far from the true parameters, ONSPP instead works on an online convex optimization problem within a larger space (which probably contain the underground truth) due to context expansions. Unfortunately, we do not have a rigorous proof of those two phenomenons above. We also notice that the choice of expansion index list $\mathbf{a}$ would affect the cumulative misspecification regret, and we refer to (ref) for more details.

Discussion

Here we discuss the motivation and the limitation of making (ref). We leave the majority of discussion to (ref).

Necessity of lower-bounding $x_t^\top\eta^*$ from 0. As we state in (ref), the price elasticity coefficient $x_t^\top\eta^*$ is lower bounded by a constant $C_{\beta}>0$. On the one hand, this is necessary since we cannot have an upper bound on the optimal price without this assumption. On the other hand, according to (ref), we know that $r(u,\beta, p) = r(u, 1, \beta\cdot p)\cdot\frac1{\beta}$, which indicates that the reward is rescaled by $\frac1{\beta}$. As a result, the regret should be proportional to $\frac1{C_{\beta}}$. Although a larger (i.e. closer to $0$) elasticity would lead to a more smooth demand curve, this actually reduce the information we could gather from customers' feedback and slow down the learning process. We look forward to future researches getting rid of this assumption and achieve more adaptive regret rates.

Conclusion

In summary, our work focuses on the problem of contextual pricing with highly differentiated products. We propose a contextual elasticity model that unifies the “linear demand” and “linear valuation” camps and captures the price effect and heteroscedasticity. To solve this problem, we develop an algorithm PwP, which utilizes Online Newton Step (ONS) on a surrogate loss function and proposes perturbed prices for exploration. Our analysis show that it guarantees a $O(\sqrt{dT\log T})$ regret even for adversarial context sequences. We also provide a matching $\Omega(\sqrt{dT})$ regret lower bound to show its optimality (up to $\log T$ factors). Besides, our numerical experiments also validate the regret bounds of PwP and its advantage over existing method. We hope this work would shed lights on the research of contextual pricing as well as online decision-making problems.