Jointly Learning Prices and Product Features

1 Introduction

In "The Ketchup Conundrum" [Gladwell, 2004] Malcolm Gladwell describes the history of market research in the food industry and the sophisticated scientific techniques used by companies like Campbell Soup and Pepsi to optimize their products to the taste of customers. In his tale about mustard, Gladwell describes how the mustard brand Grey Poupon dominated the market in the 1980s and was able to charge more than twice the price of its competitors by understanding the properties of mustard that were most desired by the market and offering a mustard product that was substantially different from its competitors.

Pricing is an important component of revenue optimization, but one equally important component is to optimize the product being offered to increase its value to consumers: How sweet should soda be? How big should the fonts be in a website to maximize engagement? What color of orange juice is the best to boost sales? Often, the design space is quite complex. Gladwell describes the design space of pasta sauce as follows: "These were designed to differ in every conceivable way: spiciness, sweetness, tartness, saltiness, thickness, aroma, mouth feel, cost of ingredients, and so forth."

In this paper we explore the question of optimizing revenue by optimizing both the pricing policy and the features of the product itself. We look at this question from the viewpoint of online learning, or more specifically, online contextual pricing. In contextual pricing a seller is presented with differentiated products represented by feature vectors and then proceed to sell them adaptively. When deciding on a price to sell each product, the seller faces a trade-off usually referred as learn/earn: lower prices are more likely to sell and guarantee revenue but more aggressive prices will allow the seller to learn more about the buyer's value and this knowledge can boost future revenues. There has been a lot of activity on contextual pricing recently [Amin et al., 2014; Bastani and Bayati, 2016; Cohen et al., 2016; Javanmard and Nazerzadeh, 2016; Lobel et al., 2017; Javanmard, 2017; Leme and Schneider, 2018; Mao et al., 2018; Liu et al., 2020] but in all those papers the seller optimizes the pricing strategy with no control of which products he is selling.

In our model, we assume that there is a space X ⊆ Rd of products that can be offered by the firm represented by feature vectors, e.g. X is the set of all the potential flavors of pasta sauce that can be produced and the features correspond to things like spiciness, sweetness, tartness, etc. The seller then repeatedly interacts with a buyer with valuation function ν : X → R by choosing a product xt ∈ X to offer and a price pt and observes whether the buyer purchases the product (pt ≤ ν(xt)) or not (pt > ν(xt)). The buyer is here assumed to be myopic and have a fixed valuation.

The learning task we consider is to optimize the revenue achieved by the seller while learning. Formally, we minimize regret during a course of T rounds defined as the difference between the seller's revenue and the best possible revenue in T rounds that can be extracted if the seller knew ν.

1.1 Our Results

We start by studying the case where there are d independent products, e.g., X = {e1, . . . , ed} where ei the i-th vector in the standard basis for Rd . The simplest algorithm for this problem is to do binary search to determine the value of each item within 1/T precision and then offer the highest value product at the lower estimate. The total regret in this approach is O(d log T ). Using a surprising idea by [Kirkpatrick and Gao, 1990] it is possible to identify the best product together with its value with only O(d + logT) queries. We also show that, using a different algorithm, we can exponentially improve the dependence on T . More precisely, we obtain a regret bound of O(d log log T ) using a parallelized version of the algorithm of [Kleinberg and Leighton, 2003] for a single item. Since our benchmark is the value of the best product, it is not enough to run separate instances of Kleinberg and Leighton's algorithm for each product. Instead we need to synchronize different instances to make sure the regret bounds are valid across products.

While our upper bound results are relatively straightforward applications/extensions of existing algorithms, our main question is whether one can do better. Namely, given that it is possible to obtain regret O(d log log T ) and O(d + log T ), it is natural to ask whether it is possible to obtain the best qualities of both bounds: a log log dependency on T and an additive dependency on d. In other words, is O(d+log logT) achievable for this problem? We answer this in the negative.

Our main result and technical contribution is a lower bound on regret showing that if T = 22d , then any deterministic algorithmmust incur Ω(d2 / log d) regret. In other words, for large T the parallel version of Kleinberg-Leighton is optimal up to log factors. The construction for the lower bound is quite intricate.

In the second part of the paper, we consider a general set X ⊆ Rd . We assume that we have an oracle that given a direction v ∈ Rd , we can efficiently compute a point in argmaxx∈X 〈x, v〉 and obtain an algorithm with regret O(d log d log log T). We obtain this result by a reduction to the Contextual Pricing problem [Leme and Schneider, 2018; Liu et al., 2020].

1.2 RelatedWork

Product Design is a formulation of a traditional problem in marketing research from the perspective of online learning. A large body of literature in marketing has been dedicated to developing techniques to understand the preferences of consumers. Particularly close to our problem is the technique known as cojoint analysis [Green and Srinivasan, 1978]. The goal of this technique is to design surveys to be sent to consumers and analyze those in order to infer what product attributes are more influential in purchase decisions. We refer to the excellent paper by Toubia, Hauser and Simester [Toubia et al., 2004] as a great introduction to the field. Methods for cojoint analysis have been derived from polyhedral techniques [Toubia et al., 2004; Toubia et al., 2003], convex programming [Evgeniou et al., 2007], statistics [Ding et al., 2005] and more recently machine learning [Chapelle and Harchaoui, 2005; Viappiani and Boutilier, 2010].

We depart from this line of literature in two major ways: (i) we focus on revenue and on the tradeoffs between learning and earning, while the traditional focus of marketing has been in learning the weights that consumers attribute to each feature; (ii) our methodological approach is rooted in online learning: we have clearly specified loss functions and obtain provable guarantees on what is achievable for such loss functions.

Our methodological approach is closely related to the literature on contextual pricing, in which differentiated products are presented to a seller who then chooses a price based on the observable features of the product. Different techniques have been applied to this problem leading to different regret bounds: stochastic gradient descent [Amin et al., 2014], statistical learning [Bastani and Bayati, 2016; Javanmard and Nazerzadeh, 2016; Javanmard, 2017], iterative partition refinement [Mao et al., 2018] and high-dimensional convex geometry [Cohen et al., 2016; Lobel et al., 2017; Leme and Schneider, 2018]. We differ from this line of work both in the benchmark against which we compute regret and more importantly in the decision variable. While in contextual pricing the decision maker is only asked to choose a price in each step, in our setting we choose a price and a product configuration.

2 ProblemDefinition

Product Design is an online decision making problem in which a firm repeatedly interacts with a buyer to sell an item from a fix set of items. The firm knows the set of products that it is capable of producing. This set of products will be represented by a set X ⊆ Rd where each product x ∈ X is identified by a set of d features. The buyer's value for each product is given by a function ν : X → R that is fixed but unknown to the firm.

At every period t = 1, 2, . . . , T , the firm chooses a product xt together with a price pt and offers xt at price pt to the buyer. The buyer accepts the offer if pt ≤ ν(xt) and rejects otherwise. The goal of the firm is to minimize its regret with respect to the maximum obtainable revenue, which is: T · maxx∈X ν(x). Formally,

We will make the common assumption that the function ν(x) is linear in the feature space, i.e., ν(x) = 〈v, x〉 for a certain vector v ∈ Rd . To fix the scale of the problem we will also assume that ‖v‖2 ≤ 1. As usual, this can be generalized to more complex functions by mapping the features to a different space 1 .

First we consider the case of Independent Products in which X = {e1, . . . , ed} and ei is the i-th coordinate vector. In this case what we learn fro pricing a certain product says nothing about the value of the buyer for other products. Next we consider General Products in which X is an arbitrary set with ‖x‖2 ≤ 1, ∀x ∈ X for which we have an oracle that returns argmaxx∈X 〈v, x〉 for any v ∈ Rd .

A natural algorithm is to try to find the best product as fast as possible and the price it at its lower estimate.

Lemma 1. If it is possible to find a pair (ˆx, ˆ ν) such that

in f(ϵ) iterations, then it is possible to obtain an 1+f(1/T) regret algorithm for Product Design.

Proof. Use the first f(1/T) iterations to obtain a pair (ˆx, ˆ ν) incurring regret at most f(1/T). From this point on, choose (ˆx, ˆ ν) in all remaining steps, always having the offer accepted and incurring regret at most T · (ν ∗ - ν(ˆx)) ≤ T · 1/T = 1.

1 In particular, this is easily generalizable to any functions of the form ν(x) = f(〈φ(x), v〉) for φ : Rd → Rd′ and f : R → R. Those include polynomials in x, logistic regression v = [1+exp(〈v, x〉)]-1 , the log-log model log v = ∑i vi log(xi), the semilog model log v = ∑i vixi, among others.

In many cases, however, it is possible to obtain exponentially better regret for Product Design than what is possible to obtain via a direct reduction to Product Finding.

3 Independent Products

In this section we explore algorithms for the Product Design problem when there are d "independent" products such that the value of any subset of products does not reveal any information about any other product. In the language of this paper, one can assume that the products are (for example) the d unit vectors in the standard basis of Rd . We derive both upper bounds (relatively straightforward extensions) and lower bound (main result, involved) on the regret.

3.1 Upper Bounds

One naive approach to this problem is to estimate the value of each product to within 1/T additive error in logT rounds (using a binary search), and after that, always sell the (approximately) best product at its estimated price. Because it takes d logT rounds to approximate the value of each item, this algorithm achieves a regret of d logT + 1. We present two algorithms which improve on this upper bound in incomparable ways: one achieves regret O(d log logT) while the other one achieves an upper bound of O(d + log T ).

We begin by showing how to get O(d log logT) total regret by parallelizing an algorithm of Kleinberg and Leighton [Kleinberg and Leighton, 2003] which achieves a regret upper bound of O(log log T ) for a single item.

Kleinberg-Leighton (KL) Algorithm for One Item

In the KL setting, there is only one item, and the buyer has a fixed unknown value v∗ ∈ [0, 1] for this item. Within a course of T rounds, the algorithm chooses a price pt in each round t, and observes whether the offer is accepted (pt ≤ v) or not (pt > v). The regret is defined as Regret = Tv - ∑Tt=1 pt · 1[pt ≤ v]. We describe the KL algorithm and the proof of the regret it obtains in the supplement for completeness. The main takeaway we need from the KL algorithm is that it obtains a regret of O(log log T).

First Algorithm: Parallelization of the Kleinberg-Leighton Algorithm

We now show how we generalize this algorithm for d independent items X = {e1, . . . , ed}. A naive idea is to run the KL algorithm on each item individually until we find its approximate value and then offer the best item for the rest of the rounds. This approach incurs linear regret since the benchmark is the value of top item and any accepted offer for a suboptimal item generates regret at least equal to its difference compared to the optimal item.

Instead, we run the KL algorithm for all items in lockstep. To be precise, we keep a set S of item that are alive, initially containing all items. We also keep an instance of the (singleitem) KL algorithm which we will use as a black-box. The algorithm will proceed in phases. Each phase will correspond to one step of the black-box KL algorithm which will correspond to |S| price offerings in the actual algorithm. In each phase s, we get a price ps from the KL black-box and offer this price to each item in S. Then we proceed as follows:

• If all offers are rejected, we feed the KL algorithm with "rejected" and move to the next phase without changing S.
• If at least one offer is accepted, we feed the KL algorithm with "accepted", remove from S all items for which the offers were rejected and proceed to the next phase.

Theorem 2. The parallelized KL algorithm achieves O(d log logT) total regret on the Product Design problem with independent items.

We prove Theorem 2 in the online supplement.

Second Algorithm: Binary Search Based Algorithm

The second algorithm is based on a clever procedure by Kirkpatrick and Gao [Kirkpatrick and Gao, 1990]. Their algorithm considers the following problem: given d integers x1, . . . , xd between 1 and n we want to determine maxi xi using only queries of the type xi ≥ p. Their algorithm finds the maximum in O(d + logn) steps. This is essentially the Product Finding problem for independent product and their algorithm automatically implies a O(d + log(1/ϵ)) mistake bound, which translates to an O(d+log(T )) regret bound for Product Design via Lemma 1. We sketch the idea behind the algorithm of Kirkpatrick and Gao in the supplement.

3.2 Lower Bound

In the previous section we demonstrated algorithms for the Product Design problem which achieve regret O(d log log T ) and O(d+log T ) respectively. Given these two upper bounds, a natural question is whether it is possible to obtain the best properties of both bounds, i.e., an algorithm that achieves a regret of O(d + log logT). In this section we show that a O(d + log logT) bound is not achievable by any deterministic algorithm: we show this by considering a setting with d products, T = 22d and showing that any deterministic algorithm must incur Ω(d2 / log d) regret. This is the main result of the paper and goes through an involved construction.

We establish some facts about arbitrary deterministic algorithms for the Product Design problem in the form of Lemmas 3 and 4. Since regret is additive, we focus on the case where all values are in [1, 2] for the lower bound (unlike the upper bound sections where we focused on values in [0, 1]).

Deterministic algorithms as binary trees. A deterministic algorithm for the Product Design problem is simply a sequence of queries of the form "is v(xi) ≥ p?", where each query is possibly dependent on the sequence of queries previously asked and responses received (where the i and p are decided by the algorithm). This is readily portrayed as a binary tree. Each non-leaf node of this binary tree represents the query (i.e. the pair (i, p)), and every such node has at least one and at most two child edges: YES and NO 2 . Every path in this tree is an execution of this algorithm on a given input instance. Note that two instances which are sufficiently close could result in the same path being realized, but a given input instance results in a unique path in this binary tree.

2 Sometimes there need not be two child edges because one of YES or NO answers is inconsistent given the responses received so far. For example if v(x2) >= 5 was received from an earlier query and the latter question is whether v(x2) >= 4, the answer has to always be YES.

Adversary's task. The adversary's task is to construct an input instance with regret Ω(d2 / log d). Note that the adversary has full knowledge of the algorithm, i.e., the binary tree. Thus adversary's task boils down to the following: for every binary tree that represents an algorithm, picking a path from root to leaf with resulting regret Ω(d2 / log d).

Node labeling in the binary tree. Each node v in the binary tree is naturally labeled as an (n + 1)-tuple (a(v), b1(v), b2(v), . . . , bn(v)), where a(v) is the maximum price for which we have gotten a YES response so far before querying node v and bi is the minimum price at which we have gotten a NO response for item i before querying node v. Whenever bi(v) < a(v), we will set bi(v) = ∅, representing that item i can no longer be the most valuable item. The label summarizes all the relevant information obtained from the queries asked so far. Without loss of generality we only focus on algorithms that query an item i with bi(v) ̸= ∅ (for algorithms that do query such null items i, the adversary can simply answer in any manner that is not inconsistent with previous answers; the algorithm only wastes regret by making such queries).

For any deterministic algorithm A, we let Reg(A) denote the worst-case regret of A over T rounds. The following lemmas provide constraints on any protocol with low regret.

Lemma 3 (NO edges). In any length T (or lesser) path in a deterministic algorithm A's binary tree, the number of NO edges is at most Reg(A).

Proof. Consider any problem instance whose execution results in the path at hand. Each NO query contributes 1 to algorithmA's regret (since the lowest value is 1), so the total number of NO queries is at most Reg(A).

Lemma 4 (Large-gap nodes). In any length T (or lesser) path in a deterministic algorithm A's binary tree, for any d > 0 the number of nodes v where maxi bi(v) - a(v) ≥ d is at most Reg(A)/d.

Proof. Suppose there exists a path with strictly more than Reg(A)/d nodes v with maxi bi(v) - a(v) ≥ d. Consider the last node in the path (i.e, the node farthest from the root in that path) and let (a∗ , b∗1 , . . . , b∗n ) be this node's label. For every earlier node v in this path a(v) ≤ a∗ and bi(v) ≥ b∗i . At this point the adversary could, without contradicting any of the responses it gave earlier, set maxi b∗i to be the value of the maximum valued item. In this case, every previous query where the answer was a NO resulted in regret of maxi b∗i and every previous query where YES was the answer resulted in regret of maxi b∗i - a(v) ≥ maxi b∗i - a∗ ≥ d. Thus the total regret is at least d times the number of "large-gap nodes", i.e., nodes v in the path where the gap maxi bi(v) - a(v)

strictly exceeds Reg(A)/d. This contradicts A's regret to be Reg(A).

Adversarial instance construction. As discussed before, we set T = 22d . We show that given any deterministic algorithm A's binary tree, the adversary can construct an instance, i.e., a path in the binary tree, with total regret at least Ω(d2 / log d) (whereas an algorithm with regret O(d + log log T) would incur at most O(d) regret). The adversary constructs this path by constructing and concatenating many smaller paths, which we refer to as small-paths. In particular, assume to the contrary that Reg(A) < R = ⌈ d2 8 log(d+2) ⌉ = O(d2 / log d). We construct R small paths, each with exactly one NO edge, resulting in a total regret of at least R, contradicting the fact that Reg(A) < R. To keep track of the progress made so far, we annotate each node with a triple that captures a relevant summary of the history so far.

Definition 5 (Summary triple). A node v in an algorithm's binary tree is (d1, d2, k)-bounded if both:

1. mini bi(v) - a(v) ≥ d1.
2. for at least k different indices i s.t., bi(v)-a(v) ≥ d1 + d2.

By definition 5, the root node where a = 1 and bi = 2 for all i is (1, 0, 0) bounded. We now establish two important small-path constructing mechanisms for the adversary. By stringing together these two constructions, we show that the total path length is at most T consisting of R small-paths with each having exactly one NO edge, leading to a regret of at least R.

Lemma 6 (Small-path construction Case-1). Starting from a node v that is (d1, d2, k)-bounded with k > 0, the adversary is always able to find a small-path between v and v′ of length R d2 such that v′ is ( d1d2 R , d2, k -1)-bounded.

Proof. Let L = R d2 . We assume L is an integer because our invocation of this lemma will involve 1 d2 always being an integer, and R is an integer by definition. Let v = v0 be the current node with label (a(v0), b1(v0), . . . , bn(v0)) . The adversary constructs the small-path as follows. Let v1, v2, . . . be the nodes encountered by the adversary when it proceeds as specified below, and let q(vi) be the price the algorithm asks at node vi. For notation consistency let q(v-1) = a(v0).

1. At node vi: for queries that have q(vi) - q(vi-1) < d1 L , the adversary answers YES.
2. At node vi: for queries that have q(vi) - q(vi-1) ≥ d1 L the adversary answers NO and immediately terminates the small-path after the first NO answer.

Without loss of generality, we will assume that q(vj) ≥ q(vj-1), i.e. that the algorithm never asks a price lower than a previous YES query. (If the algorithm does so, we just pretend that the algorithm asked q(vj ) = q(vj-1) for the purpose of analysis.)

We claim that for at least one j ∈ {1, . . . ,L}, we have q(vj) - q(vj-1) ≥ d1 L . If not we have would have had L large-gap nodes v1, . . . , vL where for each vj , maxi bi(vj) a(vj) ≥ d2 where as by Lemma 4 the number of large-gap nodes with gap d2 should be at most Reg(A) d2 < R d2 = L.

Let j ∗ be the smallest j at which q(vj) - q(vj-1) ≥ d1 L , and thus our v′ is vj ∗. In fact, min (q(vj ∗), a(v0) +d1) - q(vj ∗-1) ≥ d1 L

From here, it is straightforward to see why v′ is ( d1d2 R , d2, k -1)-bounded. For d′1 note that:

min i bi(vj ∗)-a(vj ∗) ≥ a(v0)+d1-q(vj ∗-1) ≥ d1 L = d1d2 R Since there was exactly one NO answer, at most one bi decreased. Also a(vj ∗) + d1/L ≤ a(v0) + d1. Thus at the same value of d′2 = d2 we have k decreasing by one, giving k′ = k - 1.

Lemma 7 (Small-path construction Case-2). Starting from a node that is (d1, d2, k)-bounded with k = 0, the adversary is always able to find a small-path between v and v′ of length 2R d1 such that v′ is ( d21 4R , d1 2 , d-1)-bounded.

Proof. We proceed similarly as in case 1, Lemma 6. Let L = 2R d1 . We assume L is an integer because our invocation of this lemma will involve 1 d1 always being an integer, and R is an integer by definition. Let v = v0 be the current node with label (a(v0), b1(v0), . . . , bn(v0)) . The adversary constructs the small-path as follows. Let v1, v2, . . . be the nodes encountered by the adversary when it proceeds as specified below, and let q(vi) be the price the algorithm asks at node vi. Let again q(v-1) = a(v0) for notation consistency.

1. At node vi: for queries that have q(vi) -q(vi-1) < d1 2L , the adversary answers YES.
2. At node vi: for queries that have q(vi) - q(vi-1) ≥ d1 2L the adversary answers NO and immediately terminates the small-path after the first NO answer.

We again focus on the case where q(vj) ≥ q(vj-1), pretending q(vj) = q(vj-1) whenever q(vj) < q(vj-1).

We claim that for at least one j ∈ {1, . . . ,L}, we have q(vj) - q(vj-1) ≥ d1 2L . If not we have would have had L large-gap nodes v1, . . . , vL where for each vj , maxi bi(vj) - a(vj) ≥ d1 2 where as by Lemma 4 the number of large-gap nodes with gap d1 2 should be at most 2Reg(A) d1 < 2R d1 = L.

Let j ∗ be the smallest j at which q(vj) - q(vj-1) ≥ d1 2L , and thus our v′ is vj ∗. Since a(v0) + d1 2 - a(v0) ≥ d1 2 , we have min (q(vj ∗ ), a(v0) + d1 2 ) - q(vj ∗-1) ≥ d1 2L .

From here, it is straightforward to see why v′ is ( d21 4R , d1 2 , d - 1)-bounded since:

Since there was exactly one NO answer, at most one bi decreased, and thus while all other bi's are at least a(v0) + d1 and hence:

We are now ready to prove the main lower bound.

Theorem 8. No deterministic algorithm for the Product Design problem with independent items can achieve a regret of O(d + log log T ).

Proof. Recap: As discussed earlier, set T = 22d . We show that for any deterministic algorithmA, there is an instance of the Product Design problem where they must incur at least Ω(d2 / log d) total regret (whereas an algorithm with regret O(d + log log T) would incur at most O(d) regret). The adversary constructs this path by constructing and concatenating many smaller paths, which we refer to as small-paths. In particular, assume to the contrary that Reg(A) < R = d2 8 log(d+2) = O(d2 / log d). We construct R small paths, each with exactly one NO edge, resulting in a total regret of at least R, contradicting the fact that Reg(A) < R.

We start at the root node which is (1, 0, 0)-bounded and construct R small-paths as follows:

• Construct a Case-2 small-path, i.e. apply Lemma 7 once.
• Construct d - 1 Case-1 small-paths in succession, i.e., d - 1 consecutive applications of Lemma 6.
• Repeat until R paths are constructed

It is easy to verify that conditions applicable for applying the respective lemmas are met. In particular, after every d small-paths constructed, we have k = 0 making it fit to invoke Case-2 Lemma 7, and for the next d-1 rounds we have k decreasing by one from d - 1 to 0 making it fit to invoke Lemma 6. Also note that whenever we invoke Lemma 6 we have d2 = 1 2r for some non-negative integer r, making 1 d2 integral, and thus making the R d2 used in Lemma 6 integral. Similarly 1 d1 is always integral when we invoke Lemma 7, making 2R d1 used in that lemma integral (d1 is 1 at the first invocation of Lemma 7, and at the subsequent i-th invocation it will be of the formR · ( 1 2R )(d+1)i · 2- d+1 d ·[(d+1)i-1-1] .

Note that after every d paths contructed by the adversary, the state summary changes

Each such "cycle" (i.e., d consecutive paths) has a total path length of 2R d1 + (d - 1) R d2 = 2Rd d1 , because d2 = d1/2 here. So the total length of all the paths when we complete η cycles is:

We claim that when η = Rd = d 8 log(d+2) , the RHS above namely 2Rdη(4R)(d+1)η-1 is at most T = 22d . To see this, the logarithm of the upper bound in (1) is given by

where we used the fact that d is large enough in a few inequalities. It follows that the total length of our feasible path was at most T and it has at least R no edges because of R small-paths with one NO edge each, thus violating Lemma 3 and contradicting our assumption that Regret(A) < R.

4 General Products

Finally, we study the Product Design problem for a generic set X ⊆ Rd . We will solve this by a reduction to a contextual learning problem. Contextual pricing is an online decision making problem very similar to ours with two major differences: the products to be sold in each iteration are chosen by an adversary and the regret is computed with respect to the value of products chosen. Formally, there is a fixed unknown valuation v ∈ Rd , ‖v‖2 ≤ 1. In each iteration an adversary chooses a product xt ∈ Rd , ‖xt‖ ≤ 1 and the decision maker then chooses a price pt. After choosing the price, the decision maker learns whether pt ≤ 〈v, xt〉 or not. The regret of contextual pricing is given by:

Note that the benchmark in Contextual Pricing is ∑t 〈v, xt〉 while the benchmark in Product Design is T · maxx∈X 〈v, x〉. The algorithms in [Cohen et al., 2016; Lobel et al., 2017; Leme and Schneider, 2018; Liu et al., 2020] provide a gurantee with respect to a stronger benchmark, which is based on the notion of the width of the knowledge set. The knowledge set is the set of all values ˆ v that are consistent with the observations so far. To be precise, if σt ∈ {-1,+1} corresponds to the feedback at time t (i.e. σt = +1 if pt ≤ 〈v, xt〉 and σt = -1 otherwise) then the knowledge set is given by:

Given a certain vector x ∈ Rd we define the width of the knowledge set in direction x as:

Using those notions we can define an upper bound on the Contextual Pricing regret, which we call width-based regret:

A contextual pricing algorithm is reasonable if pt ≥ pt := minˆ v∈Kt 〈xt, ˆ v〉 since the price pt is always guaranteed to sell. For any reasonable algorithm, the following bound holds: RegretCP ≤ WRegretCP since the regret in a nosale event can always be upper bounded by 1 and the regret of a sale can always be bounded by 〈v, xt〉 - pt ≤ maxˆ v∈Kt 〈ˆ v, xt〉 - minˆ v∈Kt 〈xt, ˆ v〉 = width(Kt, xt).

We say that an algorithm has width-based regret R if WRegretCP ≤ R. We note that all the algorithms we have referenced obtain regret bounds by bounding the width-based regret. In particular, the result of Liu, Paes Leme, and Schneider implies that:

Theorem 9. There is a reasonable algorithm for contextual pricing such that WRegretCP ≤ O(d log d log log T ).

We now use that result to obtain an algorithm for Product Design with the same regret:

Theorem 10. Given a reasonable algorithm for contextual pricing with width-based regret R, it is possible to obtain an algorithm for Product Design with regret R.

Proof. Design an algorithm as follows: in period t, find (xt, ˆ v) ∈ argmaxx∈X,ˆ v∈Kt 〈xt, ˆ v〉 and feed xt to the Contextual Pricing algorithm and obtain pt. Now, feed (xt, pt) to the Product Design algorithm.

To show that the regret of the product discovery in at most WRegretCP observe that in the case of a no-sale the regret incurred is maxx∈X 〈v, x〉 which is at most 1 which is the amount attributed to a no-sale event by WRegretCP. In the case of a sale, the regret incurred is maxx∈X 〈v, x〉 - pt. Note that maxx∈X 〈v, x〉 ≤ maxx∈X,ˆ v∈Kt 〈ˆ v, x〉 = maxˆ v∈Kt 〈ˆ v, xt〉 and pt ≥ minˆ v∈Kt 〈ˆ v, xt〉 since the contextual pricing algorithm is reasonable, therefore, the regret incurred by product discovery is at most width(Kt, xt). Putting it all together:

Corollary 11. There is a O(d log d log logT) regret algorithm for Product Design for general product sets X.

Although the Contextual Pricing algorithm of [Liu et al., 2020] is a polynomial-time algorithm, we rely on an NP-hard problem to choose the product xt in each step. Given two convex sets K1,K2, finding the pair of point that maximizes the dot product maxx1∈K1,x2∈K2 〈x1, x2〉 is NP-hard. When K1 = K2 this becomes the maximum-norm problem that was shown to be NP-hard by Bodlaender et al [Bodlaender et al., 1990]. We leave as an open problem how to obtain this regret guarantee in polynomial-time for a generic X having access to an oracle that for every ˆ v returns ˆx ∈ argmaxx∈X 〈x, ˆ v〉.