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.
52,649 characters · 13 sections · 46 citation commands
Towards Agnostic Feature-based Dynamic Pricing: Linear Policies vs Linear Valuation with Unknown Noise
In a dynamic pricing process, a seller presents prices for the products and adjusts these prices according to customers' feedback (i.e., whether they decide to buy or not) to maximize the revenue. Existing works on the single-product pricing problem kleinberg2003value, wang2021multimodal assume that customers make decisions only according to the comparisons between prices and their own (random) valuations, and the goal is to find out a best fixed price that maximizes the (expected) revenue. In general, the single-product pricing problem has been well studied under a variety of assumptions.
However, these methods are not applicable when there are thousands of highly differentiated products with no experience in selling them. This motivates the idea of “contextual pricing” cohen2020feature_journal, mao2018contextual, javanmard2019dynamic, liu2021optimal, where each sale session is described by a context that also affects the valuation and pricing.
\fbox{\parbox{0.98\textwidth}{Contextual pricing. For $t=1,2,...,T:$
} }
Here $T$ is the time horizon known to the seller in advance\footnote{Here we assume $T$ known for simplicity of notations. In fact, if $T$ is unknown, then we may apply a “doubling epoch” trick as javanmard2019dynamic and the regret bounds are the same.}, $x_t$'s can be either stochastic (i.e., each $x_t$ is independently and identically distributed) or adversarial (i.e., the sequence $\{x_t\}_{t=1}^T$ are arbitrarily chosen and fixed by nature before $t=0$), and $\mathds{1}_t:=\mathds{1}(v_t\leq y_t)$ is an indicator that equals $1$ if $v_t\leq y_t$ and $0$ otherwise. In this work, we consider two distinct problem setups that make use of the feature vector $x_t$.
These two problem setups --- although quite similar at a glance --- are intrinsically different. The LP problem makes no assumptions on the $x_t\rightarrow y_t$ mapping, i.e., agnostic learning. Customers' valuations are not necessarily linear (and can be deterministic/noisy/stochastic/adversarial), but the seller competes with the optimal policy in a constrained family. In contrast, the LV problem makes mild modeling assumptions about the distribution of $y_t$ given $x_t$ while keeping the policy class unrestricted. In other words, LP is modeling our strategy while LV is modeling the nature. We adopt regret as a metric of algorithmic performance: For the LP problem, we compare its (expected) reward with that of the optimal fixed $\beta^*$ in hindsight (i.e., an ex post regret); For the LV problem, we compare its (expected) reward with the largest expected reward condition on $\theta^*$ and $\mathbb{D}$ (i.e., an ex ante regret). We will clarify the difference between LP and LV in Appendix (ref) with more details and examples. We emphasize that in both settings, the distributions of the valuation are unknown and non-parametric, and we are interested in designing no-regret algorithms and characterizing the complexity.
\ifbool{compact}{\noindentSummary of Results.}{\paragraph{Summary of Results.}} Our contributions are threefold.
To the best of our knowledge, we are the first to study the LP problem and the version of the LV problem with no assumption on the noise. Comparing to the existing literature on this problem cohen2020feature_journal,javanmard2019dynamic, our model makes fewer assumptions. Our results for LP is information-theoretically optimal, and our results in LV improve over the best known upper and lower bounds (from $\tilde{O}(T^{\frac23\vee(1-\alpha)})$ on i.i.d. $x_t$'s with an indeterministic $\alpha$ and $\Omega(T^{\frac35})$ in luo2021distribution).
\ifbool{compact}{\noindentTechnical Novelty.}{\paragraph{Technical Novelty.}} In this work, we make use of the half-Lipschitz nature in pricing problems: the probability of a price to be accepted will not decrease as the price decreases. This has been used in kleinberg2003value and cohen2020feature_journal. However, they directly applied this property in discretizing the action and policy spaces, which would lead to a linear regret in our LV problem setting. In our algorithm D2-EXP4, we settle this issue by also discretizing the noise distribution space and include these discretized CDF's as part of policy candidates. We also carefully adopt a conservative “markdown”\footnote{A price markdown is defined as a reduction on the selling price.} on the discretized output price to ensure a large-enough probability of acceptance. In this way, we get rid of all assumption on the noise distribution (even the basic Lipschitzness assumed by luo2021distribution) while achieving a sub-linear regret. This discretization method, along with the price markdown, can be easily transferred to any pricing problem settings with unknown i.i.d. noise. For the lower bound proof, we adapt the nested intervals and bump functions introduced by kleinberg2004nearly for continuum bandits to our pricing problem models, and extend the $\Omega(T^{\frac23})$ regret lower bound on non-continuous demand functions kleinberg2003value to Lipschitz ones.
In this section, we discuss how our work relates to the existing literature on (contextual/non-contextual) pricing, bandits, and contextual search.
\paragraph{Non-Contextual Dynamic Pricing.} Dynamic pricing was extensively studied under the single-product (non-contextual) setting kleinberg2003value, besbes2009dynamic, besbes2012blind, wang2014close, besbes2015surprising, chen2019nonparametric, wang2021multimodal. The crux of pricing is to learn the demand curve (i.e., the noise distribution in our LP problem) from Boolean-censored feedback. wang2021multimodal concludes existing results and characterizes the impact of different assumptions on the demand curve on the minimax regret. The problem of contextual dynamic pricing is more challenging mainly because we need to learn the valuation parameter $\theta^*$ and the noise distribution jointly. Knowing one would imply a learning algorithm for another javanmard2019dynamic, luo2021distribution, but learning both together makes the problem highly nontrivial.
\paragraph{Contextual Dynamic Pricing.} There is a growing body of recent works focusing on the LV model of the contextual dynamic pricing problem cohen2020feature_journal, javanmard2019dynamic, xu2021logarithmic, luo2021distribution, fan2021policy, but most of them make strong assumptions about the noise. Table (ref) lists the best existing results under these assumptions. Besides these works, cohen2020feature_journal also achieved an $O(d \log T)$ regret when the variance of the Sub-Gaussian noise is extremely small, i.e., $\tilde{O}(1/T)$. It is worth mentioning that our “Linear-EXP4” shares the same discretization factor with “ShallowPricing” algorithm in cohen2020feature_journal, but ours solves a different problem. The closest works to ours are the recent luo2021distribution and fan2021policy that study the LV problem under only smoothness and log-concavity assumptions. In luo2021distribution, they develop a UCB-style algorithm that achieves $\tilde{O}(T^{\frac23\vee(1-\alpha)})$ regret for noises with $2^{\text{nd}}$-order smooth and log-concave CDF's, assuming the existence of a good-enough estimator that might approach $\theta^*$ with $O(T^{-\alpha})$ error only with the logged data. However, such an estimator was neither described nor trivial to construct with $\alpha >0$. In fan2021policy, they present a two-phase algorithm, with an exploration phase followed by an exploitation phase, and achieves $\tilde{O}((Td)^{\frac{2m+1}{4m-1}})$ regret for noises with $m^{\text{th}}$-order smooth ($m\geq2$) and “well-behaved”\footnote{A property defined similarly as log-concavity.} CDF's. In comparison, our “D2-EXP4” algorithm achieves an $\tilde{O}(T^{\frac34})$ regret with no distributional assumptions such as Lipschitzness or smoothness.
\paragraph{Bandits} A multi-armed bandit (MAB) is an online learning model where one can only observe the feedback of the selected action at each time. Both LP and LV can be reduced to contextual bandits langford2007epoch, agarwal2014taming as long as the policies and prices are finite. In this work, we make use of an “EXP-4” algorithm auer2002nonstochastic in a new way: By carefully discretizing the parameter space and distribution functions, we enable EXP-4 agents to find out near-optimal policies among infinite continuum policy spaces. There exists another family of bandit problem: continuum-armed bandit (CAB) agrawal1995continuum, kleinberg2004nearly, auer2007improved, where the action space is continuum and the reward function is Lipschitz. In this work, we adapt the (bump functions, nested intervals) structures in kleinberg2004nearly to our lower bound proof. This adaptation is non-trivial since (1) their reward functions is not suitable for pricing problems, and (2) their feedback is not Boolean-censored.
Our results on the LP problem reveal that a reduction to contextual bandits is “tight” in regret bounds. A similar situation also occurs in kleinberg2003value on non-contextual pricing. These results indicate a pricing feedback is not substantially richer than a bandit feedback in information theory, which is surprising as a pricing feedback indicates the potential feedback of a “halfspace” rather than a single point. However, does this imply we cannot get any extra information from a pricing feedback? Notice that we are matching a no-Lipschitz upper bound with a Lipschitz lower bound! In fact, a revenue curve is naturally “half Lipschitz”, which helps us get rid of this assumption. We will discuss this property in Paragraph (ref).
\paragraph{Contextual search} Contextual pricing is cohesively related to contextual search problems leme2018contextual, lobel2018multidimensional, liu2021optimal, krishnamurthy2020contextual where they also learn from Boolean feedback and usually assume linear contexts. However, they are facing slightly different settings: leme2018contextual, lobel2018multidimensional are noiseless and could achieve an optimal $O(\log\log{T})$ regret; liu2021optimal allows noises directly on customers' decisions instead of the valuations in our setting; krishnamurthy2020contextual allows only small-variance valuation noises that is similar to cohen2020feature_journal.
\paragraph{Symbols and Notations.} Now we introduce the mathematical symbols and notations involved in the following pages. The game consists of $T$ rounds. $x_t, \beta^*, \theta^*\in\mathbb{R}^d_+, y_t, N_t\in\mathbb{R}, v_t\in\mathbb{R}_+$\footnote{We do not assume $y_t\geq0$ since some customer would not buy anything despite the price.}, where $d\in\mathbb{Z}_+$. At each round, we receive a payoff (reward) $r_t=v_t\cdot\mathds{1}_t$ where $\mathds{1}_t:=\mathds{1}(v_t\leq y_t)$ indicates the acceptance of $v_t$, i.e., $\mathds{1}_t=1$ if $v_t\leq y_t$ and 0 otherwise. For LP problem, we denote $F_{LP}(v|x)$ as a demand function, i.e. the probability of price $v$ being accepted given feature $x$. Therefore, $F_{LP}(v|x)$ is non-increasing with respect to $v$, for any $x\in\mathbb{R}^d$. For LV problem, we specifically denote $u_t=x_t^{\top}\theta^*$ as the noiseless valuation (or expected valuation for zero-mean noises), and denote $F$ as its CDF. Finally, we define $h(v,x) = v\cdot F_{LP}(v|x)$ as an expected revenue function of price $v$ given feature $x$ in an LP problem, and $g(v, u, F):=v\cdot(1-F(v-u))$ as an expected revenue function of price $v$ given any noiseless valuation $u$ and noise distribution $F$ in an LV problem.
We may use discretization methods in the following sections. Here we adopt the notation in cohen2020feature_journal by denoting
as the $\gamma$-lower/upper rounding of $x$, which discretize $x$ as its nearest smaller/larger integer multiples of $\gamma$. Similarly, for $\theta\in\mathbb{R}^d$, we may define $\lfloor{\theta}\rfloor_{\gamma}:=[\lfloor{\theta_1}\rfloor_{\gamma}, \lfloor{\theta_2}\rfloor_{\gamma}, \ldots, \lfloor{\theta_d}\rfloor_{\gamma}]^{\top}$ and $\lceil{\theta}\rceil_{\gamma}:=[\lceil{\theta_1}\rceil_{\gamma}, \lceil{\theta_2}\rceil_{\gamma}, \ldots, \lceil{\theta_d}\rceil_{\gamma}]^{\top}$. Based on this, we define a counting set $N_{\gamma, a}:=\left\{0,1,2,\ldots, \lfloor\frac{a}{\gamma}\rfloor\right\}$.
\paragraph{Regret Definitions.} Next we define the regrets in both problems.
Again, we aim at competing with the best fixed $\beta^* = \mathop{\mathrm{argmax}}_{\beta}\sum_{t=1}^{T} h(x_t^{\top}\beta, x_t)$ in an LP problem, and with the global best pricing policy (maximizing expected revenue at every $t$) in an LV problem.
\paragraph{Summary of Assumptions} We specify the problems by the following assumptions:
These assumptions are mild and common for algorithm design. Based on these assumptions above, we only have to consider prices in $[0, B]$ for LP problems and $[0, B+1]$ for LV problems. Besides, we assume that $T\geq d^4$ for a simplicity of comparing among different terms in regret bounds. In Section (ref), we will introduce more assumptions to the distribution functions to demonstrate that our lower bounds hold even if those assumptions are made.
In this section, we propose two algorithms, Linear-EXP4 and D2-EXP4, for LP and LV problems respectively. Both of them are based on the EXP-4 algorithm auer2002nonstochastic along with discretized policy sets. First of all, we define these policy sets:
Definition (ref) is straightforward as we use $\Delta^d$-grids to discretize the $[0,1]^d$ space. Definition (ref) actually represents such a family of CDF: the random variable is defined on $[-1,1]$, and its CDF equals some integer multiple of $\gamma$ when ${v}$ (or $-{v}$) itself is an integer multiple of $\gamma$; for those ${v}$ in between these grids, CDF connects the two endpoints as linear. In a word, each CDF in $\mathcal{F}_{\gamma}$ is a piecewise linear function with every integer-multiple-$\gamma$ points valuating some integer-multiple-$\gamma$ as well. From the definitions above, we know that $|\Omega_{\Delta, d}|=O\left((\frac{1}{\Delta})^d\right)$. Also, we have $|\mathcal{F}_{\gamma}|=\binom{\frac3{\gamma}}{\frac1{\gamma}} =O(2^{\frac3{\gamma}})$ according to a “balls into bins” model in combinatorial counting: At each point $\frac{\pm i}{\gamma}$ (for $i\in[\frac2\gamma]$) the CDF can increase by $j\cdot\gamma$, with $j$ being a non-negative integer, and the summation of all increases is $1$ (i.e., $\frac1\gamma$ of $\gamma$ increments).
Finally we introduce the EXP-4 algorithm auer2002nonstochastic for adversarial contextual bandits. With a finite action set $A$ and policy set $\Pi$, the EXP-4 agent has a regret guarantee at $O(\sqrt{T|A|\log{|\Pi|}})$ in $T$ rounds (comparing with the optimal policy in $\Pi$). The following is a simplified version of EXP-4 that illustrates its mechanism. For a more detailed introduction, please directly refer to auer2002nonstochastic.
\fbox{\parbox{0.93\textwidth}{EXP-4.
} }
Here we present our “Linear-EXP4” algorithm for the linear policy pricing problem. It takes $\Omega_{\Delta, d}$ as the policy set and plug it into EXP-4 algorithm, which is straightforward but significant in reducing the regret. The pseudo-code of Linear-EXP4 is summarized as Algorithm (ref).
Here the EXP-4 agent $\mathcal{E}_{LP}$ would approach the best policy $\pi^*$ in $\Pi^{LP}_{\Delta, \gamma}$ within a reasonable regret. Therefore, we have to carefully choose $\Delta$ and $\theta$ such that the regrets of both $\mathcal{E}_{LP}$ and $\pi^*$ are well bounded.
Here we present our “Discrete-Distribution-EXP-4” algorithm, or D2-EXP4 for the linear noisy valuation pricing problem. Though it originates EXP-4 as well as Linear-EXP4 above, the reduction is not as straightforward. In fact, the policy set is defined as follows:
For each policy in $\Pi^{LV}_{\Delta, \gamma}$, it firstly takes a $\hat{\theta}$ from $\Omega_{\Delta, d}$ and a $\hat{F}$ from $\mathcal{F}_{\gamma}$, and then generate an “optimal incremental price” $w^*(x)$ greedily as if they are the true parameter $\theta^*$ and the true noise distribution $F$. Finally, the policy take an action (price) that is the summation of $\gamma$-lower roundings of $\hat{u}=x^{\top}\hat{\theta}$ and $w^*(x)$ to fit in the action set $A_{\gamma}:=\{0, \gamma, 2\gamma, \ldots, \lfloor{B+1}\rfloor_{\gamma}\}$, and minus a $(B+1)\gamma$ amount. We know that $|\Pi^{LV}_{\Delta, \gamma}| = |\Omega_{\Delta, d}|\cdot|\mathcal{F}_{\gamma}| = O((\frac1{\Delta})^d\cdot2^{\frac3{\gamma}})$. We present the psuedo-code of D2-EXP4 as Algorithm (ref).
D2-EXP4 is straightforward that it takes the $\gamma$-rounding of a greedy price, except the $(B+1)\gamma$ price markdown. This is because we want a conservative price, and the $(B+1)\gamma$ markdown is to compensate the “exaggerate” $\lceil\theta\rceil_{\gamma}$ parameter we adopt in $\Pi^{LV}_{\Delta, \gamma}$. We will include more details in Paragraph (ref) below and in Section (ref).
\paragraph{Adversarial Features and Agnostic Distributions} Notice that both algorithms are suitable for adversarial $x_t$ series, which is a property of EXP-4. It is worth mentioning that our Linear-EXP4 makes no assumptions on the distribution of $y_t\text{ given } x_t$, and that D2-EXP4 assumes no pre-knowledge or technical assumptions on the noise distribution (despite that noises are bounded). \paragraph{Conservative Pricing Strategy} Both of our algorithms adopt a conservative strategy while pricing: In Linear-EXP4, a good-enough linear policy is the $\gamma$-lower rounding of parameter $\beta^*$; in D2-EXP4, we even define each policy by proposing a “greedy-and-safe” price which takes a $(B+1)\gamma$-markdown on the output of the optimal greedy pricing policy. This is because of the “half-Lipschitz” nature of a demand curve: decreasing the price would at least maintain the chance of being accepted. Since we do not make any Lipschitz or smoothness assumptions on the distributions, these discretizations might marginally increase the price and cause drastic change of the expected revenue. In order to avoid this, it is always better to decrease the proposed price by an acceptable small amount as it guarantees the probability of acceptance. \paragraph{Computational Efficiency} Our algorithms require exponential computations w.r.t. dimension $d$ since the EXP-4 agent requires exponential time to evaluate each policy in the policy set. An “optimization oracle”-efficient contextual bandit algorithm in agarwal2014taming can be used in place of EXP-4 to achieve a near-optimal regret (up to logarithmic factors), but it requires the input features $x_t$ to be drawn from an unknown fixed distribution.
In this section, we analyze our Linear-EXP4 and D2-EXP4 algorithm and prove their $\tilde{O}(d^{\frac13}T^{\frac23})$ and $O(T^{\frac34})$ regret bounds, respectively. Also, we present a scenario where a lower bound construction with $\tilde{\Omega}(T^{\frac23})$ regret fits for both LP and LV problems, even under stronger assumptions including stochastic $x_t$'s, Lipschitz distribution functions and unimodal demand curves.
Here we propose the following theorem as a regret bound of Linear-EXP4. This only requires the assumption that features $x_t$'s and (potential) optimal parameter $\beta^*$ is bounded by $L_2$-norm, without making any specifications on the feature-valuation mapping.
The proof of Theorem (ref) is straightforward based on the existing $O(\sqrt{T|A|\log{|\Pi|}})$ bound of EXP-4. We only have to bound the error of the optimal policy in $\Pi_{\Delta, \gamma}$. Now we present our result on D2-EXP4:
The proof of Theorem (ref) is more sophisticated than that of Theorem (ref), but they shares similar structures: we figure out one specific policy in $\Pi^{LV}_{\Delta, \gamma}$ that is close to the optimal policy of the LV problem. The main idea of this proof is to find out a tuple of $(\hat{\theta}, \hat{F})$ that approaches the true parameter and distribution, and to verify that the policy built on this approaching tuple is reliable only within small tractable error. The highlight is that we do not assume any Lipschitzness on the distribution, which is quite different from existing approximation methods. In fact, it is the natural property of pricing problems that enables this: for two prices $v_1\geq v_2$, the probability of $v_2$ being accepted is greater (or equal) than that of $v_1$, and thus $(v_1-v_2)\geq g(v_1, u, F)-g(v_2, u, F)$. We may call it a Half-Lipschitz property since it only upper bounds the increasing rates.
Here we show a proof sketch of Theorem (ref), and leave the bulk to Appendix (ref).
In this part, we present an $\tilde{\Omega}(T^{\frac23}d^{\frac13})$ and an $\tilde{\Omega}(T^{\frac23})$ regret lower bounds that hold for LP and LV problems respectively. We will firstly claim a lower bound for non-contextual pricing problem, and then generalize the result to LP and LV.
The detailed proof of Theorem (ref) is in Appendix (ref), and in the main pages we briefly demonstrate the constructions of the subproblem family where we achieve this lower bound.
Here we take the idea of kleinberg2004nearly where they make use of bump functions and nested intervals to ensure Lipschitz continuity and unimodality, sequentially. Since that their model is not capturing a revenue curve and that their feedback is numerical instead of Boolean, we have to adjust their design to satisfy the pricing setting. On the one hand, the probability of a price to be accepted, i.e., the rate $\frac{\mathbb{E}[r(v)]}{v}$, is non-increasing as the prices increases, which is not guaranteed for that of a reward function of a continuum bandit (if we treat $v$ as an action). In this proof, we adopt a series of transformations to convert the “bump function tower” into a revenue curve while keeping all monotonically-increasing/decreasing intervals unchanged. On the other hand, we still use the KL-divergence to distinguish among distributions, but in a different way. As for Boolean feedback, we only need to calculate the KL-divergence of two Bernoulli random variables, which can be upper bounded by a quadratic term of their probabilistic difference.
The constructions of bump-based revenue curves are illustrated in Figure (ref). Firstly, we define a nested-interval series $[0,1]=[a_0,b_0]\supset[a_1,b_1]\supset\ldots\supset[a_{k}, b_{k}]\supset\ldots$, where $b_k=a_k+w_k$, $w_{k}=3^{-k!}$. We let $a_k$ be chosen from the discrete set $\{a_{k-1}+\frac{w_{k-1}}3+i\cdot{w_k}, i=0,1,2,\ldots, \frac{w_{k-1}}{3w_k}\}$. Secondly, we construct Lipschitz bump functions in each $[a_k, b_k]$ interval, the middle one-third of which is a plain line Thirdly, we add all these bump function up, which forms a “tower” with its peak randomly generated by the series of tightening intervals $\{[a_k, b_k]\}$. Finally, it is transformed into a revenue curve after a series of operations.
If we treat this randomly-generated function a uniformly-distrbuted family of functions, then we can further prove our lower bound: On the one hand, we prove that the feedback cannot accurately locate where the “peak of the tower” is, from the perspective of information theory. In fact, any algorithm would have a constant chance of missing the peak. On the other hand, the cost of missing a peak can be lower bounded, and thus the expected regret is as well lower bounded by their product.
With this theorem holds, we can soon get the following two corollaries:
It is worth mentioning that the noise distribution is itself an (inversed) demand function on $(v-u)$, i.e., it is non-increasing as $(v-u)$ gets larger. Based on this insight, the derivation of Corollary (ref) is straightforward: any non-feature pricing problem with bounded i.i.d. $y_t$'s can be reduced to an LV problem up to constant coefficients. In fact, suppose $y_t\in[a,b], 0\leq a<b$ in a non-feature pricing problem, and then we might define an LV problem by setting $d=1, \theta^*=\frac{a+b}{b-a}\text{ and } x_t=1, \forall t\in\mathbb{Z}_+$ since now $x_t^{\top}\theta^*+N_t\in[a,b]$. As long as the definition of LV problem does not specify the distributional properties (besides being bounded), the distribution family in the proof of Theorem (ref) can be reduced to an LV problem as well. In this way, the $\tilde{\Omega}(T^{\frac23})$ lower bounds are applicable to LV problems.
In this section, we conduct numerical experiments to show the validity of Linear-EXP4. We assume $d=2, B=1$ as basic parameters, and assume a Gaussian noisy valuation model i.e., $y_t = u_t + N_t$ where $N_t\sim\mathcal{N}(0, \frac1{16})$ independently for all $t$. For the convenience of comparing with a fixed optimal linear policy $\beta^*$, we let $u_t = J^{-1}(x_t^{\top}\beta^*)$ for each $t$, where $J(u)=\mathop{\mathrm{argmax}}_v g(v,u, 1-\Phi_{\mathcal{N}(0, \frac1{16})})$ is a greedy pricing function defined in xu2021logarithmic\footnote{They also show the existence of $J^{-1}(v)$ by showing that $J'(u)\in(0,1)$.}. In other words, the linear price $v_t^*=x_t^{\top}\beta^*$ always maximizes the expected reward for any $t$, and we may calculate the empirical ex ante regret (i.e., comparing the empirical performance with the maximizer of expected regret at each round) by comparing $v_t\cdot\mathds{1}(v_t\leq y_t)$ with $x_t^{\top}\beta^*\cdot\mathds{1}(x_t^{\top}\beta^*\leq y_t)$. According to Hoeffding's Inequality, the ex post regret that we adopt for the LP problem is only $\tilde{O}(\sqrt{T})$ different from the empirical ex ante regret. Given that the regret rate of Linear-EXP4 is $\tilde{\Theta}(T^{\frac23})$, we may ignore this difference and only show the ex ante regret in our experiments. Since the EXP-4 learner requires pre-knowledge on $T$ and is not an any-time algorithm (i.e., the cumulative regret is meaningful only at $t=T$), we execute Linear-EXP4 for a series of $T=\lfloor2^{\frac k3}\rfloor$ for $k=27, 28, \ldots, 48$. We repeat every experiment 20 times for each setting and then take an average. The results are shown in Figure (ref)
We were unable to conduct numerical experiments on D2-EXP4 due to the exponential time complexity of the EXP-4 learner along with the $2^{T^{\frac14}}$-size policy set. We provide the code of D2-EXP4 in our supplementary materials.
In this section, we discuss potential extensions of this work and our conjectures on the regret of LV problems.
\paragraph{From Linear to Non-Linear} Both LP and LV problems are based on a linear principle of feature-price/valuation relationships, which is not reasonable in many real-world situations (for example, the price of a diamond). Based on our specifications on LP and LV problems, we may similarly define two corresponding problems: (1) We make no assumptions on the $x_t\rightarrow y_t$ mapping, but compare with the optimal policy in a parametric non-linear model space. (2) We directly assume that the $x_t\rightarrow y_t$ is a parametric non-linear function adding some unknown (and non-parametric) noise, and compare with the optimal price. We may slightly modify our Linear-EXP4 and D2-EXP4 to deal with these two problems by just replacing the linear discretized policy set with another non-linear one. However, we should be careful about any discretization involved: the $\gamma$-roundings of non-linear policy parameters do not necessarily lead to a slightly lower price (maybe either higher or much lower). Like what we designed in D2-EXP4, we still have to ensure the parametric optimal policy itself performs within a $[-O(\gamma), 0]$ range from the global optimal policy. \paragraph{The Minimax Regret(s) of LV} Existing works on solving LV have achieved various regret bounds with different assumptions. This is quite different from the linear regression problem where noise distributions do not significantly affect the result. To the best of our knowledge, we are the first to get rid of all assumptions (despite bounded-noise assumption \footnote{If the noise is neither bounded nor parametrized, then any finite-time algorithm will suffer a linear regret when the noise is very large and prices are always being accepted.}). However, we did not close the regret gap in this setting. This problem is similar to a non-feature pricing problem as we adopt the same lower bound proof in this work, but the situations are entirely different: In non-feature pricing, we aim at a fixed optimal price, and we only have to know the valuation distribution around the optimal price. However, in an LV problem, we have to approach the exact linear valuation adding an optimal increment for each feature, and the optimal increments are not fixed for different valuations. As a result, we have to know the whole noise distribution. This drastically increases the hardness of LV, and we conjecture LV with a $\Theta(T^{\alpha})$ regret where $\alpha>\frac23$.
\paragraph{Dependence on Noise Scale $R$} In this work we assume the noise $N_t\in[-1,1]$. Based on this assumption, we construct a discrete noise CDF family $\mathcal{F}_{\gamma}$ whose size is $\binom{\frac3\gamma}{\frac1\gamma}$. When it changes to $N_t\in[-R, R]$ for larger $R$, the number of discrete CDF is $\binom{\frac{2R+1}\gamma}{\frac1\gamma}\leq (\frac{2R+1}\gamma)^{\frac1\gamma}$. Also, this would increase the upper bound of prices from $(B+1)$ to $(B+R)$, which would increase the number of actions by $\frac R{\gamma}$. Recall that the regret of EXP-4 is $O(\sqrt{KT\log{N}})$ where $K$ is the number of actions and $N$ is the number of policies (i.e., \# discrete $\theta$ times \# discrete CDF). Therefore, the dependence on $R$ is $O(\sqrt{R\log{R}})$.
In this work, we have studied two agnostic feature-based dynamic pricing problems: a linear pricing policy (LP) problem with no assumptions on feature-valuation mappings, and a linear noisy valuation (LV) problem with agnostic noise distributions. For the LP problem, we have presented a Linear-EXP4 algorithm whose $\tilde{O}(T^{\frac23}d^{\frac13})$ regret matches the $\tilde{\Omega}(T^{\frac23}d^{\frac13})$ lower bound up to logarithmic factors. For the LV problem, we have proposed an $\tilde{O}(T^{\frac34})$-regret algorithm D2-EXP4 along with an $\tilde{\Omega}(T^{\frac23})$ lower bound proof even with stochastic, Lipschitz and unimodal assumptions, and both of them substantially improve existing results from $O(T^{\frac23\cup(1-\alpha)})$ (with smoothness assumptions and indeterministic $\alpha$) and $\Omega(T^{\frac35})$ respectively. Both Linear-EXP4 and D2-EXP4 allow adversarial features. Besides, we have discussed the prospective generalization of this work and development of future research in feature-based dynamic pricing.
The work is partially supported by the Adobe Data Science Award and a start-up grant from the UCSB Department of Computer Science.