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.
53,653 characters · 8 sections · 24 citation commands
An Online Algorithm for Learning Buyer Behavior under Realistic Pricing Restrictions
{0pt} {0pt} {0pt} {0pt}
Modeling the arrival and response behavior of a buyer to a collection of items sold by a seller has a rich history in operations managementcohen2016feature and machine learning kleinberg2003value,amin2014repeated, and helps answer questions such as: what assortment of items should a seller show a prospective buyer? How should she price them? Much work in this area can be divided into two categories: (1) explicitly learning the purchase model, and (2) maximizing the revenue or some other function given a behavior model.
In particular, online problems in the latter category besbes2015surprising,chakraborty2009dynamic,alaei2011bayesian,cai2011extreme,blum2011welfare, instead of learning the buyer behavior, optimizes what is known as regret, which is the difference between what the seller could have done in hindsight compared to what they did in a sequence of interactions with the buyer. Although the regret setting is appealing, the techniques and the corresponding algorithms tend to be very specialized (except for perhaps the simplest cases) and lacks universality. In particular, many of the general purpose algorithms (such as Thompson Sampling and UCB) depend linearly on the number of actions, which is not-ideal when the action space is large or infinite (as is the case for us). Specialized analysis or algorithms address this dependence issue but depend heavily on the structure of the objective and the decision problem. Further, if the objective or the decision structure changes, either because of business considerations or as new business logic is introduced, one has to design new algorithms from scratch. Thus, it is economical and convenient to decouple the estimation problem from the decision making problem and explicitly estimate the parameters of buyer behavior first (also called pure exploration).
There is a recent line of work on learning the behavior of buyers online Balcan2014,beigman2006learning,bei2016learning. Compare to these works, our algorithm does not share a key shortcoming, which is the necessity of posting unrealistic prices in the process of learning. Note that, learning buyer behavior in the offline (batch data) setting has also been addressed in recent works. For instance, in benkdd16, the authors learn the parameters of a particular buyer behavior model that considers preference lists. We believe the online setting is relatively more interesting because there is scope for real-time personalization tailored to each individual buyer compared to the offline setting.
In this paper we consider a buyer behavior where the buyer's objective is sensitive to prices. This type of sensitivity to prices to prices has been considered in the online setting STOC16p949 in the context of regret minimizing profit maximization, as well as in the offline setting benkdd16. In each interaction, the seller prices a collection of items and the buyer responds by purchasing various quantities of each item that maximizes her objective/utility. Previously proposed algorithms resort to posting unrealistic prices to induce the buyer to buy/not-buy certain items. Our algorithm eliminates this shortcoming by learning the buyer behavior while being constrained to post prices from a predefined set of realistic prices (described in Section (ref)), which is provided as an input. The practical motivation for such a constraint to be imposed is straightforward: prices of items in many commercial settings are only allowed to vary between realistic lower and upper bounds. This is because of business constraints and prior knowledge on the market value of goods and items. More involved constraints include bundle prices (where prices are tied to each other) and promotion/discount prices that are also specified by business rules. Further, all such constraints can vary arbitrarily over time.
The fact that our algorithm can learn despite such pricing constraints makes it practical and applicable in real scenarios. Internally, it exploits the concavity property of the buyer's objective and uses projected gradient descent to shrink an uncertainty ellipsoid around the true buyer model parameters.
From STOC16p949, we re-purpose the use of a gradient descent based technique (used in solving the convex program in Equation ((ref))) for interacting with the buyer. While they do not need any specific variant of the gradient descent algorithm, we explicitly choose a certain step rule (constant step length) to bound our learning errors. Our own contribution here is the use of these gradient descent moderated interactions in a "realistic" price space (an additional caveat) to enable the seller (1) approximately learn the "value" of the goods purchased by the buyer without knowing his "inherent" utility (Lemma (ref), Theorem (ref)) and, (2) split the uncertainty ellipsoids, whereas STOC16p949 use such interactions for solving a specific structured Stackelberg game (requiring very different tools and techniques in the process).
Similar to cohen2016feature, we use two specific eigenvalue lower bounding lemmas (see Lemma (ref) and (ref)) to bound the number of rounds of interaction needed by our algorithm. Their proposed algorithm, which essentially does a multidimensional binary search for the best price to post in each round can break if there is a coupling across items. On the other hand, the search procedure our algorithm follows can handle such coupling as the ellipsoidal procedure searches for parameters related to the entire universe of items. Another key difference between our setting and cohen2016feature is that we work with multiple items in each round in contrast to their single item setting. While using an ellipsoid to represent uncertainty in parameter estimation, the cut direction and the hyperplane placement is straightforward in cohen2016feature. On the other hand, in our algorithm, in the presence of realistic pricing constraints we carefully choose the cut direction as well as position the separating hyperplane by solving the dual of a specific optimization problem using projected gradient descent. Finally, note that their problem is a version of the contextual bandit problem for which general purpose algorithms are already available, whereas our problem is not a contextual bandit instance. Further, we note that algorithms in both STOC16p949 and cohen2016feature cannot be easily extended to the realistic prices setting (defined in Section (ref)), which is our key emphasis here.
For the buyer models that we consider, the utility $U(x)$ need not be linear in the bundle, so even polynomial utility functions can be learned as long as certain conditions mentioned in the assumptions of Section (ref) are met. This makes our algorithm and its analysis in Section (ref) more generally applicable.
Here we define what we mean by realistic prices which will constraint the prices that the seller can set while learning the buyer model (Section (ref)).
The price $p_i$ of an item $i$ is realistic if it lies within the interval $[p^0_i-\delta_i, p^0_i+\delta_i]$, where $p^0_i$ is the median price point and $2\delta_i$ is the length of the interval (without loss of generality, we can assume symmetry here). This leads to an $n$-orthotope, which is defined as follows:
For analysis, we will assume that the set $\mathcal{P}$ is enclosed in a Euclidean ball of radius $R$.
We represent a bundle of goods $x\in C\subseteq [0,1]^n$ (where $C$ is the feasible set) by a vector representing what fraction of each of the $n$ goods is purchased. The prices are represented by a vector $p = (p_1, \cdots, p_n) \in \mathbb{R}^n$. The price of a bundle $x$ is simply $p^Tx=\sum_{i=1}^{n} p_i \cdot x_i$. When the buyer is provided with a price vector $p$, she buys the tie-breaking utility maximizing bundle, $x^*(p)$, which is the optimal solution of the following optimization program:
Ideally, a utility maximizing buyer would maximize $U(x) - p^Tx$, where $U:[0,1]^n \rightarrow \mathbb{R}$ specifies their utility for each possible bundle. Since this could potentially lead to multiple optimal bundles (e.g., when $U$ is not strictly concave), we add a tie-breaking perturbation to the original utility function to introduce consistency in the buyer's decision making process. That is, we model the buyer's effective utility function as $U'(x) = U(x) + \frac{4}{\mu}\left(\mathlarger \sum \limits_{i=1}^{n} \sqrt{x_i}\right)$, where $\mu$ is a positive constant. There is nothing special about the choice of the tie breaking function, and many other choices can also be used to make the solution unique (for instance, we can use the Cobb-Douglas function as well). The solution $x^*(p)$ is called the induced bundle at prices $p$. The seller's goal is to learn the parameters of the function $U(.)$ by observing the bundles bought in a sequence of interactions, where the seller chooses realistic prices of items in each interaction. The complexity of any learning algorithm in this setting is typically the number of interactions the seller makes with the buyer to learn the parameters with sufficient accuracy.
Assumptions: We assume that the seller knows the set $C$ of feasible bundles. This is a mild condition, and can be mined from historical purchase data. The set $C \subseteq \text{dom } U'$ is assumed to be non-empty, compact and convex and $\forall x \in C$, $\lVert x \rVert_1 \leq \gamma_1$ and $\lVert x \rVert_2 \leq \gamma_2$ (here $\lVert a \rVert_q$ refer to the $\ell_q$-norm of vector $a$). We further assume that $C = \{ x^TPx + 2q^Tx + r \leq 0 \} $ , where $P \in \mathbf{S}^n, q\in\mathbf{R}^n, r \in \mathbf{R}$ for computational tractability of a program.
This does not affect the learning complexity as even without this assumption the program can be solved by performing an exhaustive grid search.
We also assume that the seller does not know the exact tie breaking parameter $\mu$ that the buyer uses, but knows an upper and lower bound on it i.e., $\mu \in [\mu_1,\mu_2]$. We assume tie-breaking to be the only effect of such a function and that its functional form is known beforehand.
To ensure computational tractability of the buyer's problem in Equation ((ref)), we make some generic assumptions about the buyer's utility function. Namely, we assume $U(.)$ is concave on the feasible set $C$. Also, let $U(x)$ for each $x \in C$ be non-negative and non-decreasing. Since the tie breaking perturbation $\frac{4}{\mu}\left(\mathlarger \sum \limits_{i=1}^{n} \sqrt{x_i}\right)$ is also non-negative and non-decreasing, so $U'(x)$ non-negative and non-decreasing.
Further, since $U(x)$ is concave on $C$, $U'(x) = U(x) + \frac{4}{\mu}\left(\mathlarger \sum \limits_{i=1}^{n} \sqrt{x_i}\right)$, is $\frac{1}{\mu}$-strongly concave
on the set $C$ with respect to $\lVert \cdot \rVert_2$ norm. In other words, the buyer's problem defined in Equation ((ref)) is a maximization of a strongly concave function over a convex set $C$. Hence $x^*(p)$ exists for every $p \in \mathbb{R}^n$ and is unique (follows from strong concavity). We also assume that the utility function of the buyer, $U(x)$, is $(\lambda_{val},\beta)$-H\"{o}lder continuous with respect to the $\lVert \cdot \rVert_2$ norm $-$ for all $x,x' \in C$. Thus we have, $\lvert U(x) - U(x')\rvert \leq \lambda_{val}\cdot \lVert x - x'\rVert_2^{\beta}.$ Note that this assumption of H\"{o}lder-continuity on the utilities is a mild one and is satisfied by a wide range of economically meaningful utilities like Constant Elasticity of Substitution (CES) and Cobb-Douglas utilities.
We restrict the scope of our model to utility functions with linear coefficients and known nonlinearities (these are with respect to $x$). This includes many concave utility functions (concave in the bundle) including the CES utility function (this is a function of the form $U(x) = (\sum_{i=1}^{n}\alpha_ix_i^\rho)^{\beta}$ that has linear coefficients when parameter $\beta = 1$ and $\rho < 1$), the logarithm of the Cobb-Douglas function ($\log U(x) = \sum_{i=1}^{n}\alpha_i \log x_i$), and any other function that is approximable by a positive polynomial of bundle $x$. Thus, utilities such as Separable Piecewise-Linear Concave (SPLC), CES, Cobb-Douglas or Leontief functions can also be learned in our setting (although their representation has to be transformed so that the function is linear in the parameters). Later on, without loss of generality, we will assume $U(x)= a^Tx=\sum_{i=1}^{n} a_i \cdot x_i$, with $a \in \mathbb{R}^n_+$.
\noindentOverview: Without an interesting feasible set $C$ of bundles, the learning problem in our setting can decompose into $n$ scalar learning problems that can be solved using binary search. On the other hand, when we have a non-trivial $C$ or a coupling across items through the function $U$, then binary search is no longer applicable. The algorithm that we propose for learning the unknown parameter vector $a^*$ is based on maintaining uncertainty ellipsoids around $a^*$ and successively shrinking their volume by constructing specific separating hyperplanes (based on observed purchases). At each round $t$, we start with an uncertainty ellipsoid $E_{t}$ and shrink it to get $E_{t+1}$. In particular, based on the interaction between the buyer and the seller in the current round, we cut $E_{t}$ with a hyperplane into two regions. And then we update $E_{t+1}$ as the L\"{o}wner-John ellipsoid of one of these regions.
The main technical part of our algorithm is that it works by seeking a desired purchase vector in each round. The purchase vector is then used to deduce a hyperplane that cuts the uncertainty set. Now, this purchase vector cannot be directly accessed as we can only control prices to induce purchase. Below, we show how to use gradient descent and duality to find prices that induce desired bundles.
Along with the price that induces desired bundles, we are able to get the value of these bundles. We compare these values with the minimum and maximum values that are possible given our current uncertainty set over parameter vector $a^*$ and define appropriate hyperplanes to split the uncertainty sets, thus shrinking them.\\
\noindentFinding a price that induces a specific bundle: Consider the following convex program:
where $\hat{x} \in C$ is a specific bundle. Since the utility function $U'(x)$ is non-decreasing and $1/\mu$-strongly concave, we can see that $\widehat{x}$ is the unique optimal solution of the problem in Equation ((ref)). The partial Lagrangian of this formulation ((ref)) is defined as: $\mathcal{L}(x,p) = U'(x) - p^Tx + p^T\widehat{x}$, where $p \in \mathbb{R}^n_+$ is the dual variable. We define the Lagrange dual function $g:\mathbb{R}^n \rightarrow \mathbb{R}$ to be $g(p) = \max \limits_{x \in C} \mathcal{L}(x,p) = \max\limits_{x \in C} U'(x) - p^Tx + p^T\widehat{x}$. Now the dual of the convex program in Equation ((ref)) can be defined as:
Our algorithm needs to choose a specific bundle $\widehat{x}$ and learn its value $U'(\widehat{x})$. Since we can only control prices, we show how to learn the value $U'(\widehat{x})$ by working with the dual problem. In other words, to compute $U'(\widehat{x})$, which we otherwise could not have since $U'(.)$ is unknown, we define the problem in ((ref)) such that its optimal solution is $\widehat{x}$ itself. We can compute the minimizer $\widehat{p}$ of its dual in ((ref)) because we can control prices. And, by strong duality, we will get $g(\widehat{p}) = U'(\widehat{x}) = \text{OPT}$.
Now we focus on the problem of minimizing the function $g$, which is also unknown (since $U'(.)$ is unknown). However, due to the structure of the dual problem, the function $g(p)$ can be approximately optimized using a first order optimization technique such as projected gradient descent. In particular, this is the structure we exploit: we have access to the gradients of $g$ and these turn out to be functions of $\widehat{x}$ and the actual bundles purchased by the buyer. Thus, we can set a price $p$, interact with the buyer to observe the bundle purchased $x^*(p)$ and get access to the gradient. Formally, the following Lemma (ref) shows that the bundle $x^*(p)$ purchased by the buyer gives a gradient of the Lagrange dual function $g(\cdot)$ at $p$.
Next, we focus on the restriction to realistic prices. We are constrained to set prices only from the realistic price space $\mathcal{P}$, so we can only solve a restricted version of the dual program in Equation ((ref)), which we denote as $\min\limits_{p\in \mathcal{P}} g(p).$ The following Lemma shows that instead of minimizing $g(p)$ in Equation ((ref)) over $p\in \mathbb{R}^n_+$, if it is minimized over the realistic price space $\mathcal{P}$ as defined in Definition (ref), then the optimal value remains close to OPT.
The dual function $g(p)$ is convex, and the following Lemma (ref) further shows that $g(p)$ is also strongly smooth.
Convexity and smoothness of $g(p)$ are useful below, where we give a projected gradient descent
procedure \textproc{learnvalue$(\widehat{x}, \tau)$} (Algorithm (ref)). Given a target bundle $\widehat{x} \in C$ and an error budget $\tau$ (this is the same value appearing in Lemma (ref)), \textproc{learnvalue$(\widehat{x}, \tau)$} minimizes $g(p)$ over the realistic price space $\mathcal{P}$ defined in Definition (ref), with an additive error of at most $\tau$.
Therefore, combining Lemma (ref) and Theorem (ref), we have:
Hereafter in this section, for the sake of simplicity of illustration, we focus on learning the buyer's utility function $U(x)= a^{*T}x=\sum_{i=1}^{n} a_i^* \cdot x_i$ assuming it is linear in both the coefficients and the bundle (this is without loss of generality). Hence Equation ((ref)) becomes:
\noindentInterval containing the value $U(\widehat{x})$:
It turns out that for a target bundle $\widehat{x}$, that the seller has in mind, she can compute an interval $[\,\underline{b}_t, \overline{b}_t\,]$ using the uncertainty ellipsoid $E_{t}$ such that it contains the scalar value $\widehat{x}^T{a^*}$. Lemma (ref) gives the optimum values of the following convex programs:
So, if $g(p_T)' \leq (\underline{b} + \overline{b})/2 = \widehat{x}^Tc$, then the unknown parameter $a^*$ lies in the halfspace
On the other hand if $g(p_T)' \geq (\underline{b} + \overline{b})/2 = \widehat{x}^Tc$, then by Equation ((ref)), the unknown parameter $a^*$ lies in the halfspace
Note that in \textproc{Learn-Utility} (Algorithm (ref)), the uncertainty ellipsoid $E_{t+1}$ for the next iteration is updated using the computation $E_{t+1} = \textrm{LJohn}(E_{t} \cap H_t)$, where $H_t$ is defined by either Equation ((ref)) or ((ref)). The former induces a central cut in the ellipsoid $E_t(A, c)$, i.e. the hyperplane $H_t$ passes through the center $c$ and eliminates half of the volume of the ellipsoid. On the other hand, the later hyperplane induces a shallow cut and removes less than half of the volume. Without loss of generality (as we only need an upper bound on the number of iterations needed by \textproc{Learn-Utility} to learn $a^*$), we assume that at each iteration the relevant hyperplane induces a shallow cut. That is, $H_t$ is:
where $\delta = \left(\frac{4}{\mu_1}\left(\mathlarger \sum \limits_{i=1}^{n} \sqrt{{x_t}_i}\right) + 2\tau\right)$ is the depth of the cut induced. For \textproc{Learn-Utility} to work we need the depth $\delta$ to be at most $\frac{\sqrt[]{x_t^T A_t x_t}}{n}$, i.e. $\delta \leq \frac{\sqrt[]{x_t^T A_t x_t}}{n}$. As the portion $\frac{4}{\mu_1}\left(\mathlarger \sum \limits_{i=1}^{n} \sqrt{{x_t}_i}\right)$ takes effect only in tie-breaking, i.e., we can assume $\mu_1$ to be a large constant. Hence, the constraint on the depth of the shallow cut becomes $\sqrt{x_t^TA_tx_t} \geq 2n\tau$. Also, note that the Algorithm \textproc{Learn-Utility} continues as long as $2\sqrt{x_t^TA_tx_t} > \epsilon$. So the shallow cut condition is met (in other words the algorithm is able to find an $x_t$ in each iteration) as long as $\tau < \epsilon/4n$.
Next, the computation of the L\"{o}wner-John ellipsoids of the sets that remain after shallow cuts follows from grotschel2012geometric. The L\"{o}wner-John ellipsoid of the set $E_t(A_t,c_t) \cap \{\tilde{a} \in \mathbb{R}^n: x_t^T\tilde{a} \leq x_t^{T}c + \delta\}$ is $E(A_{t+1}, c_t - \frac{1+n\alpha_t}{n+1}b_t)$, and of the set $E_t(A_t,c_t) \cap \{\tilde{a} \in \mathbb{R}^n: x_t^T\tilde{a} \leq x_t^{T}c - \delta\}$ is $E(A_{t+1}, c_t + \frac{1+n\alpha_t}{n+1}b_t)$, where $\alpha_t = - \frac{\delta}{\sqrt[]{x_t^T A_t x_t}}$, $b_t = A_t x_t/ \sqrt[]{x_t^T A_t x_t}$ and $A_{t+1} = \frac{n^2}{n^2 - 1}(1 - \alpha^2)(A_t - \frac{2(1 + n\alpha)}{(n+1)(1+\alpha)}b_tb_t^T).$
In what follows we present the performance guarantee of the Algorithm (ref). Firstly, to bound the minimum eigenvalue $\lambda_n$ at successive iterations of our algorithm, we give the following two lemmas from cohen2016feature also applicable in our setting. In cohen2016feature, they are used in the analysis of a different algorithm in a different setting (regret minimization).
Using the above two lemmas, we can show that the number of rounds needed by \textproc{Learn-Utility} is upper bounded.
Combining Theorem (ref) and (ref), we get the following bound on the interactions needed to get a tight uncertainty set around the unknown parameter $a^*$ of the buyer's utility function. Moreover, since the volume of the uncertainty sets decrease in successive iterations so having a bound on how much the minimum eigenvalue can decrease in one iteration can guarantee the tightness of the uncertainty set at termination, or alternatively, its maximum eigenvalue (for a special case: Corollary (ref)).
\noindentSolving the program in line $9$ of \textproc{Learn-Utility} :
Even though the program is not convex, but strong duality holds and it can be solved by solving the following dual which is a semidefinite program with variables $\lambda, \gamma \in \mathbf{R}$,
Specifically, if $P = I$ and $q,r=0$, then it becomes an eigenvalue problem. This leads us to the following corollary of Theorem (ref).
In this paper we proposed an efficient online algorithm which can be used by a seller to learn the behavior model of a buyer that maximizes utility, by controlling prices subject to exogenous pricing restrictions.
One of the key advantages of our algorithm is that it is amenable to exogenous pricing restrictions imposed by business and managerial constraints, making it relatively more practical and user-friendly than previously proposed approaches. Using our algorithm, practitioners can build a model of buyer behavior from purchase and pricing data, which can be subsequently used for inventory, pricing and other business decisions.
\noindentFuture Work: We completely side-step the issue of identifiability of the model in our treatment, by reporting uncertainty sets instead of point estimates of the true parameters. When allowable prices are exogenous, it may happen that the best uncertainty set is still very loose due to stringent pricing restrictions. Another important issue that we did not address here is that of modeling stochasticity in the buyer models. As our algorithm uses an ellipsoidal search template for which noisy generalizations exist, it can be extended to the the noisy case (appropriate noise models have to be specified here). Our algorithm also uses projected gradient descent while interacting with the buyer. Thus, noisy gradient information obtained from the buyer can potentially be dealt with as well.