Dynamic pricing and assortment under a contextual MNL demand
Authors: Noemie Perivier
Vineet Goyal
Venue: NeurIPS 2022 Accept (2022)
Keywords: dynamic pricing
assortment optimization
multinomial logit
online learning
contextual information

Abstract: We consider dynamic multi-product pricing and assortment problems under an unknown demand over T periods, where in each period, the seller decides on the price for each product or the assortment of products to offer to a customer who chooses according to an unknown Multinomial Logit Model (MNL). Such problems arise in many applications, including online retail and advertising. We propose a randomized dynamic pricing policy based on a variant of the Online Newton Step algorithm (ONS) that achieves a $O(d\sqrt{T}\log(T))$ regret guarantee under an adversarial arrival model. We also present a new optimistic algorithm for the adversarial MNL contextual bandits problem, which achieves a better dependency than the state-of-the-art algorithms in a problem-dependent constant $\kappa$ (potentially exponentially small). Our regret upper bound scales as $\tilde{O}(d\sqrt{\kappa T}+ \log(T)/\kappa)$, which gives a stronger bound than the existing $\tilde{O}(d\sqrt{T}/\kappa)$ guarantees.

Dynamic pricing and assortment under a contextual MNL demand
Vineet Goyal
Noemie Perivier Columbia University New York, NY np2708@columbia edu
Columbia University
New York, NY vgoyal@ieor cowumbia.e..ooomooooooooo......e edu
Abstract
We consider dynamic multi-product pricing and assortment problems under an unknown demand over periods, where each period, seller decides on the price for each product the assortment of products to offer to customer who chooses according to an unknown Multinomial Logit Model (MNL). Such problems arise in many applications, including online retail and advertising. We propose a randomized dynamic pricing policy based on a variant of the Online Newton Step algorithm (ONS) that achieves a Odv'T log())) regret guarantee under an adversarial arrival model. We also present adversarial MNL. contextual bandits problem, which achieves a better dependency than the state-of-the-art algorithms in problem-dependent constant K2 (potentially exponentially small). Our regret upper bound scales (dd/ggg log(T)/R2), which gives stronger bound than the existing O(d/T/ns (x2) guarantees.
optimistic algorithm for the
Introduction
In this paper, consider the contextual dynamic pricing and assortment optimization problems faced by seller who sequentially observes a contextual demand under bandit feedback. The goal is to learn the underlying model parameters in order maximize the seller's profit. These problems arise in numerous applications, including pricing and product recommendation in online retail, as well as click-through rate predictions for web search results. Sequential learning is especially important in settings involving short selling seasons or where no historical data is available.
Problem formulation. In both the dynamic pricing and assortment problems, consider seller who sells set of N products over a time horizon of T periods. new customer arrives in each period and is offered set of products prices. In the pricing problem, the customer arrives with a consideration set and the seller has to decide on the prices of the different products in the consideration set. In the assortment problem, the seller selects the subset of products to offer the customer. In both cases we assume that the customer's purchase decisions are made according to a multinomial logit model (MNL) 28 which widely used in modeling customer preferences. In both problems, the objective to maximize the seller's expected profit, which is equivalent to minimizing its cumulative expected regret (i.e., the difference between the optimal value and the value obtained by following a given policy).
In this paper, study feature-based model, where the product utilities function of both products and customers features. In particular, we assume that each period t, the customer's utility for each product j [N] can be written under the form or,6"", where 0" is unknown model parameter and æt,j E Idd is feature vector, which can be adversarially chosen (see Sections 2.1 and 3.1 for exact definitions of the problems). Furthermore, we allow feature-dependent price sensitivities in our pricing setting and suppose that the price sensitivities can expressed as "rT, for some
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

unknown parameter a". Typically, the number of products is significantly larger than the number of features (d << N). The objective is learn across the products and obtain a regret upper bound scaling with d instead of N.
Literature review. Non-feature-basee based dynamic pricing, where the seller sells identical products to the customers over time, was initially investigated by [22] under various assumptions on the demand curve, and has since been extensively studied (see for instance 8 [1] 7 and [5]). We refer the reader to 13 for an in-depth survey of the area. On the other hand, non-feature-basee dynamic assortment optimization was first studied by ( under the assumption of independent demand for the different products. Dynamic assortment under MNL choice model has been recently considered (see for instance [6],, 37 and [39]). In particular, UCB and Thompson sampling-buss -bsed policies are proposed in and These policies achieve optimal regrets of O(VNT) in the non-feature based setting.
In this paper, we consider feature- based pricing and assortment problems. Feature-based dynamic pricing has recently received a lot of attention. Most of the existing work study a single product pricing setting under various demand models (linear, binary, generalized linear) and assume that the price sensitivity of each product (i.e., the price coefficient in the demand model) is a known
constant (see for instance [9]. 20 [5| 12]. 127. [26] 24 and [33). In the single product setting, the most related work is 66. which is the first to incorporate contextual information about the customers under the form of ceature-dependerr
price sensitivities. The benefit of this assumption is illustrated on real datasets. 6 considers a high dimensional setting with a sparsity assumption under a generalized demand model and propose a policy with near-optimal regret. However, they assume i.idd features, whereas we consider a more specific demand model (MNL model), but with adversarial features. In (2T] is considered a multiple product version of the problem, with feature- based price sensitivities and under the assumption that the demand follows a MNL model. In this last work, the features are also assumed to be i.i.d. Our multi-product pricing setting directly extends (21], and captures the single product setting with unknown (and ceature-based price sensitivity and adversarial features under a binary demand model with logistic noise, for which, to the best of our knowledge, no algorithm with near-optimal regret is known yet.
The MNL feature-based dynamic assortment problem is a variant of the contextual generalized linear bandits problem (see for instance [17], 255 and (2) with a more complicated state space, in which multiple arms are pulled at the same time. UCB and TS based policies have recently been proposed for the MNL contextual dynamic assortment problem (see for instance [11, [0 and (II). However, these work suffer from a dependency in a problem-dependen constant K22 (potentially exponentially small), which captures the 'degree of non-linearity' of the problem.
Another related stream of literature is that of combinatorial bandits (see for instance 10
23 and
[34). and in particular, top k combinatorial bandits ( (35)) ). In this framework, the agent can pull subset of arms of cardinality less than k in each round and the total reward obtained is a function
of the individual rewards for the arms played. However, the reward obtained in our setting for each
individual arm depends on the whole set of arms played in period f, whereas the rewards are supposed independent in the aforementioned works.
1.1 Our contributions.
In this work, we introduce new algorithms for the dynamic contextual pricing and assortment problems. Our main contribution is the following.
Dynamic pricing. We present a dynamic pricing policy for the multi-product MNI. model with adversarial contexts and feature-dependent price sensitivities that achieves O log(T)) regret bound. This is near-optimal given the 2( ((VTT) lower bound from (21). Based structural properties of the MNL model, and more specifically, on the self-concordantt-ikk property of the MNL log likelihood function, propose use variant of the Online Newton Step method ((T8) to update our estimators of the model parameters. We combine it with a random price shock policy to force exploration.
Closest to our pricing setting is [21], in which the authors design a multi-produet dynamic pricing policy under a MNL choice model and feature-dependent price sensitivities. The proposed algorithm achieves a Ó( ((V)) regret. However, it relies on bayesian assumption, namely the feature vectors

---

are drawn i.i.d from some unknown distribution. Our work considers an adversarial context and uses an ONS method update the parameters. Note that the connection with the Online Convex Optimization framework has been exploited in the literature (see for example the stochastic online gradient descent in [19] for the single product setting without price sensitivities), however, the problem we consider is more challenging since the presence of feature-dependen price sensitivities implics the existence of uninformative prices (i.e. prices p such that no pricing policy can learn the true model parameters when repeatedly pricing at price p). Note that all prices are informative in 19). The link between uninformative prices and the difficulty to design low regret policies was first pointed out by [8), which shows that no algorithm can achieve better regret than Q2( ()) in settings involving such prices. We address this challenge by using appropriate randomized price shocks that force exploration (we note that adding random shocks was first used in the context of dynamic pricing in [29]; however, work is the first to simultaneously use random price shocks and an ONS based update, and the analysis of our policy differs from the analysis in (29]
Our results imply a (ollog())) regret in the single product setting with adversarial contexts and without price sensitivity considered in [19], under the extra assumption that the noise follows logistic distribution. This improves over the O(vT) regret bound of [19] in this case (note that [9] studies more precisely the effect of drifts in the parameters). Note that in the same setting, but with feature-dependent price coefficients, our results also imply a Õ(VT) regret. We have become aware that a concurrent recent paper [40] also obtained a logarithmic regret for the contextual single product pricing problem without price sensitivity through a variant of the online newton method (for more general demand model with strictly log-concave noise). We would like to underscore that our theoretical results were obtained independently from this work. Furthermore, the algorithm proposed in 40) uses the exp-concavity parameter in the descent step and the regret upper bound provided scales with this potentially exponentially small constant, By leveraging the self-concordance property of the logistic loss, design algorithm which does not use such parameter, which may be better in practical applications. However, our regret upper bound still depends on this constant. We present in Appendix D some numerical comparison between the two algorithms, which confirms that our algorithm achieves a significantly better regret than the one in 40) as the exp-concavity parameter decreases.
In addition our main contribution, we present new algorithm for MNL contextual bandits.
MNL contextual bandits. We consider setting with uniform product revenues and propose a new UCB-based algorithm for the MNL assortment problem with adversarial contexts. Our algorithm achieves a regret bound of order Õ(dK VT). which is optimal as function T. One major limitation of the state-of-the-an algorithms for the MNL. contextual bandits problem (l31, 30 and (TT) is that the regret bounds scale with a problem dependent constant, which we will refer to as K2 (see Section for a formal definition); K2 quantifies the level of non-linearity of the model and can be exponentially small even for moderate size instances ((16). Our regret bound can be expressed as Gidy Ct=ni
log(log(T) /K) (where n5,, S 1 are problem dependent constants, whose value decrease as the model is further away from the linear model). Therefore, we give a significantly stronger bound than [3T], whose regret term of order vT scales with 1/kg- Note that our first order term improves for small values of {KŹ Moreover, prior knowledge of the value of K2 is often presupposed in the existing algorithms, which may be a major hindrance to their practical implementation. The quantity X2 appears for example in the design of the exploration bonuses of the UCB-MNE algorithm of (31) Our algorithm does not rely on an a priori knowledge of Kg. Our policy is based on optimistic parameter search instead of exploration bonuses, as used in [3]. The analysis relies on a concentration result on the MLE estimators, which uses a generalization of the Bernstein- like tail inequality for nolf-normalized vectorial martingales in 2 and [16]. and leverages the coff-connordant property of the MNL log loss.
We would like to mention that similar result is achieved by [16] and 2 in the logistic bandits setting. Our results cannot, however, be derived from these two works since the MNL contextual bandits problem cannot be formulated that the techniques from [6] and 2 can be efficiently extended to the MNL bandit setting, which involves overcoming few technical challenges that are specific to the MNL problem.
generalized bandits problem [.. In this work, we show
3

---

Notations. For any vector I and any positive definite matrix M E R let || = vI Mæ. Also let (0, W) be the d-dimensional ball of radius W under the norm C.. In the special case the norm e we will drop the index and refer to the d-dimensional ball as (0, W). For two symmetric matrices A, B E Rdxd A > B means that A - B is semi-defing positive. For E N. we use the notation (n] to denote the set {1,.....) n.. When it not clear from the context, we use a bold font to denote vectors.
2 Multi-product dynamic pricing
2.1 Model sefting and preliminaries
We consider a dynamic pricing problem for seller with N products represented by feature vectors T1, F2. .... NN F.. In each period t. a customer arrives with context 2, I2 and consideration set S; _ [ which can be chosen adversarially. For ease of notation, we consider a more general setting where customer features 2 and consideration set St are represented by |St| adversarially
chosen feature vectors It ..., [S. E Rd. For all t [T') let k = [Sp] and let K S N be an upper bound on kt for all t. We also define X, as the matrix whose to it as the context at time t. In each period t,
Z1,j for j E [kg] and we refer
1. The seller observes -r,,,,.., E Rd and offers prices pt.j for all E [ka]
2. The customer observes the prices, then purchases one single product E {[]]u[0}. The probability to purchase each product j is given by:
-Feg Pe.
if 2 if j -
9rs (00((0 a)),)))
1+ Ete c
,
where 0", a* Rd are model parameters, which are unknown to the policy maker. For all j E [ke], " represents the price sensitivity of customer for product j. Note that the customer has always the possibility leave without making any purchase (by selecting product 0).
3. The policy maker observes only the customer's purchase decision. The binary variable yt.j indicates whether the customer has purchased product j at time t.
For brevity, let 7- = (0", a²) and ēt. = [ Pt.l We can more simply write the utility Ur.j x 50 - " jt.j associated with each product as us = "I, Also, for each and for a given estimator "/e of the true parameter at time t. we denote by 90.5(7t:PP) Pi) the estimated purchase probability for product j (obtained by replacing 7" by > (T].
We make the following assumptions, which are standard in the dynamic pricing literature: Assumption 2.1. For all t, [Rx). || 1.
Assumption 2.2. ([(0",a*)) < W for some known constant W.
Although the contexts { (M/)) set of feasible contexts to guarantee the positiveness of the price sensitivity for all products. Following (1I, make the following assumption, which implies that the price-sensitivity of each product is not too close to zero. This assumption may be reasonable in practice: when the price of a product goes infinity, its utility should decrease significantly.
be adversarially chosen, need to slightly restrict the
Assumption 2.3. For all i E T E [kr], =T,,a* 0 2 L for some known constant L. Assumption 2.4. The upper bound K on the number of products in each set S, is constant.
Pricing policy and Benchmark. We consider non-anticipating pricing policies æ, which depend only on the history up to time i 1, H4-1 (X1, Pi, Vi, ...; X,- 1-- vr )), and the current context X₁. The objective is to design pricing policy so as to minimize the sellers' cumulative expected regret:
T
he Σ guil7 (..lrt.PPppss) =
Rd (T) =
9n)("" x, pp. )i, E

---

where Pž is the optimal vector of prices in period t. The expectation is taken over the random feedback and any source of randomization the policy.
Let Pmar
max(W:1) K. We show in Lemma ?? that for the algorithm we propose, the L prices posted at each time satisty pt.j E [0, [m,z] for all E [Ke]. Hence we can consider policies a that only post prices in [0, pmaz]-
Finally, we define the following constant, which provides information about how much feasible demand curve can deviate from the linear model (a smaller 81 implies a larger deviation from the linear model).
1
min
2r. (7. (7)
Note that our pricing policy does not directly use the value of K1. However, this constant still appears in our regret bound (see Section 2.2 for more discussion).
2.2 Dynamic pricing policy
Our algorithm combines the two following ingredients: a variant of the ONS method and random price shocks. In particular, we maintain estimators of the parameters which are updated in each iteration by using a variant of ONS on the log likelihood. In each step. our algorithm selects myopic vector of prices based on the current estimators and adds random price shocks to force exploration and avoid uninformative prices.
We first give the details on the update of the parameters. Given our estimator "/. of the true parameters time i, we let & denote the log loss time l:
(,11%) = Σ yi log(gr,;(1e pi))
j=0
For time- deme-dennddnn sequence of positive regularizers {>e (the exact value of the regularizers used in our algorithm is given in Theorem (255), the estimator obtained before projection after conducting one step our descent method is:
t: = 7t-1 Ve-
where μ Pe (2v6KK) and H, = -'E (26((%)) + Acla is the regularized Hessian of the negative log likelihood. Note that for the MNL model, 4,1 is convex (as can be deduced from Lemma ?? 1.), hence H, > for all
Let B, denote the set B (0, W) n ((0 x
2 L for [k]]]. B, represents the set of We obtain the new estimator "e by projecting %
parameters which satisfy Assumptions 2.2 and 2.3 on the feasible set of parameters:
11 Hr (fie)
where M. *(y) arg min (x-v)" H,-1 1 (x- y) is the projection relatively the norm induced by H,-1- As result, during all the course of the algorithm, our estimator also satisfies the lower and upper boundedness assumptions.
"
Finally, the seller chooses a perturbation factor 8, WH7 and computes, independently for each product j E [kx). random price shock Apr.j which takes value 5, with probability 1/2 and -o, with probability 1 1/2. The seller posts the vector of prices p% which is the sum of the random price shocks and the myopic vector of prices g(,,,,, X,0:) (see Appendix ?? for a formal definition). The pseudo code of our dynamic pricing policy is presented Algorithm
Running time: The two main computational steps of Algorithm I are calculating the inverse He and projecting the parameter back in the set of feasible parameters relative to the norm H4, The time complexity of the first step is (d which is reasonable when is not too large as in the setting we consider. The projection step also be done efficiently by formulating the problem Programming problem.
Quadratic
Using an online descent method for the parameters estimation allows to obtain a low regret algorithm despite the presence of adversarial contexts. We would like to note that based on our current analysis, simpler online method such as stochastic online gradient descent (as proposed
5

---

Algorithm Online Newton method for multiple product pricing
Input: Upper bound W on ([(""""")] lower bound L,, sequence of regularizers f21)
Initialize 01, on E Bj for all 2 1 do
WP7 w/p
For j [Ka] let Apt.i
3
w/p
W717
For j [Ks], set Pt.j = g(xrrr, Xz0r)s Apt.j Post prices pt Observe feedback Vi:
I Bi41 (n - (
Set 7++ = (fe+1, 04+1) as follows: 7441
end for
in [9] for single-product dynamic pricing without price sensitivity) would not allow to obtain sublinear regret. We would also like to mention that our method is different from the Online Newton Step presented in [88), which the classic online analogue the Newton method. The ONS method moves into the direction of V where A, is an approximation of the inverse of the Hessian. In our case, we move directly into the direction of the inverse of the Hessian multiplied by V4,, and leverage self-concordant--ike properties of the negative log likelihood function of the MNL model to show the convergence of the estimators. This allows us to avoid using the parameter 1/K1 (which corresponds to the exp-concavity parameter in the literature) in the descent step, done by the ONS algorithm.
We ready to present regret bound.
Theorem 2.5. Setting A 1, X = d log(t) (t for all 2 1, there is constant C depending only on W, L, K such that the regret of Algorithm 7 bounded as:
R (T) S Cdlog(T)VT.
The proof of Theorem 2.5 is presented in Appendix ??. We would like to point out that, even though our algorithm does not use the parameter 1/KI, it still appears within the constant C.
Under the assumptions of 19 (single product dynamic pricing with adversarial contexts and constant price sensitivity), and assuming that the noise has logistic distribution, we can show the following regret bound, which contrasts with the O(VT) upper bound established in [9
Corollary 2.6. If ki 1 for all t, and if the price coefficient is known constant, then setting A 1. A = log(t) for all t Z 1, and letting Apr,
at each step, there a constant depending with regularizers {h1 } and price shocks {Avi,1) is
only W such that the regret of Algorithm 7 bounded as:
Rd (T) Cdlog(T)..
2.3 High level ideas and sketch of the proof.
We provide here the main ideas in the proof of Theorem 2.5] The technical details are presented in Appendix ??. We first follow the classical regret analysis for dynamic pricing policies and decompose the regret between a term due to the error in the estimation of the parameters and a term due to the random price shocks. In particular, we have the following lemma.
Lemma 2.7. There exist constants Ci, C2 depending only on W, L, K, such that:
T
T
(T(T) S CiC2
ΣΣ ((ar - -a") + ((0, 0') +
Σ A
(2)
1=
Since the variances of the random price shocks are way the second term is O(VT). Therefore, to exhibit Ö(vT) regret bound, it suffices focus on upper bounding the first term. Note that follows from 2 that the regret upper bound does not require the global convergence of the estimators

---

to the true parameters. We only need to show that they converge sufficiently fast in the directions given by the contexts seen throughout the periods.
For any sequence of prices (pi our online descent method allows us to control the convergence
of the estimated utilities Wr,j = z zt,, - aip to the true utilities Vi,j = 0i,00* - xi Pt.j for
each product j E [kr]. In particular, we have the following lemma.
Lemma 2.8. There is constant Ö depending only on W, L, K such that with probability at least log(T)
1
T
(1T - 0*) -1 - a² pp)s) S Cdlog(T).
We present the proof Appendix ??. Note that the upper bound in Lemma 2.8 is valid for any sequence of prices posted by the seller. However, it is not possible, in general, to derive directly Theorem 2.5 from Lemma 2.8 without an appropriate price experimentation scheme. Suppose at each step only post the myopic vector of prices pii g( g(x,, X,0.). If the prices {pt.j) happened to be uninformative (i.e. 22 (0, 8*) - (az ")t., 0), then the left-hand side in Lemma 2.8 would be zero and the bound provided would not be useful. However, adding random price shocks allows to deviate from uninformative prices and to derive upper bound on the first term of (2) based on Lemma This concludes the proof of Theorem 2.5 If there is a single product (ke = 1); and there is price sensitivity (i.e. for all I, the coefficient in front of Pt, is known constant, that we assume to be without loss of generality), note that from Lemma 2.8 we get Ee xx (0: 0.) Od (T)) Combining this with and the choice of Apr, for all t, we immediately obtain Corollary 2.6
In 19 where price sensitivity is involved and the utility is simply written under the form u = xz "", the use of a stochastic gradient descent method allows the author to directly obtain a O(VT) bound on the sum E ot (0, 0²)2. Such bound, when combined with our random price shocks, would only give us a linear regret. By exploiting the special structure of the MNL. function and using our variant of the ONS instead of an online gradient descent, we obtain the stronger (To)(TT) bound of Lemma 2.8.
The proof of Lemma 2.8 is based on lower and an upper bound on Σt= (4,17))))1177))) Both involve Σ Σド (0, 0-) - =T,, (a, a" )p,,)² The proof of the lower bound exploits the convexity of l.11 and is based on Bernstein inequality for martingales difference sequences. This similar to the inequality used in 19). The main technical hindsight lies in the proof of the upper bound. It mimics the analysis of the Online Newton Step method presented in [18], but relies on the specific structure of the gradient and Hessian l,, for the MNL model. Moreover, it unically exploits the self concordant-lic property of 4,11 Let's first recall the definition of self-concordant like function.
Definition 2.9 (self-concordant-lik functions self-concordant like function if:
38
convex function f E (*(R) is called
(1) S (Dllul)
for t E R and M, 0, where ((t) = f(x (0 tu) for any dom(f) and R...
By adapting the proof of Lemma 4 in 38 we show Appendix ?? the following property.
Proposition 2.10. 411 is self-comcordant-like with M, (1 + Prna)) ( /6S.
We also detail Appendix ?? some useful properties satisfied by seff-conccrdanntlike functions.
3 Improved algorithm for MNL contextual bandits
3.1 Problem formulation
We consider the following MNL dynamic assortment optimization problem, also referred as the MNL contextual bandits. In each period f, the seller observes feature vectors ر E IR As
7

---

before, this represents a combination of customer and product features which can be adversarially chosen. The seller needs to decide on the set S, S [M] offer, with |S,] I K. Given the offered assortment, the customer purchases one single product E S. U (0}. Each product is purchased with probability:
if E St
(tts 0*)
14Dies,
H+ Ti if
where 8" E F is an underlying model parameter. As before, the binary variable Yt indicates whether the customer has purchased product j at time t. Note that model encompasses the contextual logistic bandit problem with finitely many arms (which corresponds to the case where K 1). The objective is to minimize the cumulative expected regret over the T periods:
T
R(T) = Σ
Σ (.((S) jESt
Σ (S, 0*) JES.
where S7 denotes the optimal assortment time t.
In [I, the authors study a more general model where a reward Pr, E [0, 1] is also revealed for each product at time f. We consider the case of uniform rewards (ri.) 1) for all products. Maximizing
Ejes, 4t.j (S,, 0) over all sets S S [N] cardinality at most K is now equivalent to selecting the
products which have the highest utility 0. Hence the set St as well as the optimal set S/ always
contain exactly K products.
Similarly as in the pricing setting, we make the following two assumptions:
Assumption 3.1. For all t [T). j [N], || S 1.
Assumption 3.2. |0 I W for some known constant W.
Following 31, we also introduce the following constant, which typically appears in connection to link function in the generalized linear bandits (017. 25
K2g |SISK llw
min min (s,(S, o > 0.
smaller value of #2 can be interpreted as a bigger deviation from the linear model. As mentioned before, the regret bound of the dynamic assortment policies of [31 and [I]] exhibit harmful dependency in l2.. Besides, an priori knowledge of the value of K2 is presupposed. Our goal is to design dynamic assortment policy which does not require prior knowledge of R2 and achieves a regret with better dependency in K2. For all E [T], let K İjes; (t., 01000)))) (S, 0*). <22, represents the degree of non-linearity for the optimal set S and depends on the unknown parameter 0* as well on the feature vectors present at time t. We show that the Ö(VT) term of our
regret bound can be replaced by a Ô (V V "2, term. Note that we always have x S hence
this is a strict improvement. As a result, a high level of non-linearity at time f induces a smaller K²,1 and positively impacts the regret.
3.2 Dynamic assortment policy
We design tight confidence set for the true parameter 0* and use it to construct upper confidence bounds on the utility of each product at time f. Our algorithm relies on optimistic parameter search over the confidence interval, as used by 2 in the logistic bandits setting. However, our setting, the seller's decision at time f involves the choice of multiple products. Hence we cannot build a unique optimistic estimator O as in 2 The key idea to do the optimistic parameter search independently for each product, generating a set of parameters (0r,) such that with high probability, ar[, an upper bound on the utility =TT00* of product j.
Confidence set. The main ingredient is the design of a confidence set for 0* We classically start by computing the maximum likelihood estimator of 0r. Let O, be the unique minimizer of the
8

---

following function, for sequence of time-dependent regularizers {At (the exact values are given in Theorem 3.4:
(0) = Σ Σ Yes log (S + 1102.
0, satisfies the equation V2, (0) = O, where the gradient of L²¹² (0) is given by: VC) E jes, (S,, Vs,)=aa. + rede. Following [2] for all 8 E [0, (), now define confidence set Ci( for 0 follows:
C( = {0 @1119((0) se(0i)ll S (6))
where (+) E= Ejes, (s. 0).ss XeO, where H²) is the Hessian of the regularized negative log likelihood evaluated at f, i.e.,
H₂(0) = Σ
Σ iES
(e, 0)
Σ
(o 0)gc (S (S,,0)2o, D
+ dela
2=1
and where
2d
4
(11 2tK
(6) = v \W + +22) +
log
1
Vx
ddp
The following proposition the analogue, in the multi-product setting, of Proposition 1 in and establishes that (ō) is confidence set for 0" The details are given in Appendix ??.
Proposition 3.3. Let E (0, 1]. Then P((L,, 0* C²))) 2 6. 6.
The proof of Proposition 3.3 builds upon the new Bernstein-lig tail inequality for self- soff-normalized
vectorial martingales presented in [16]. However, Theorem 1 in [6] does not directly apply to our setting because of the correlation between the variables { := Ht. qt., (t,, ("),,0)))) Jees, induced by the presence of multiple purchase options in period f. We thus present a generalization of Theorem I in [16] for the multiple products setting that handles such correlation.
Algorithm. Before describing our algorithm, let's introduce the following notation, which generalizes the choice probabilities given by (3) to the case where the model parameters corresponding each product are uncorrelated. More precisely, we now consider some estimator Ô d of the true parameters. For all j [N], 0, represents the parameter associated with product The estimated probability that item j is purchased at time / if assortment S C [N] is offered is computed as:
if E
(S,
1t
1+
if 0
I+Eics
Now, at time f, our algorithm uses the previous contexts and observations to compute the maximum likelihood estimator 0, as defined above and constructs the confidence set Cz()). Then, for each product [N], the algorithm finds optimistic parameter dr,5 arg maxgec. 0T,00. We offer the set S; of the K items maximizing the optimistic expected revenue (s(
(S, Ø) Σ (S,
JES
Since assumed all prices to be unit, this is equivalent offering the K products with highest Org In the case of non-uniform revenues, algorithm is still valid; however, an extra factor 1/kg would appear in the regret upper bound with current analysis. We also note that Algorithm 2 is mainly of theoretical interest, since computing each 0,, remains computationally expensive.
We now present the our upper bound on the regret of our policy.
Theorem 3.4. For 8 = kęz.. Å = 1, and X = d lloo(tK) for all t 2 1, the regret of Algorithm
2 satisfies, for some constants Ćn and Ö2 that do not depend on d, K,T T and that depend only polynomially on W:
T
K2
R(T) s (d
Σ
22,
+
log 2
K2

---

Algorithm 2 OFU-MNL
Input: Upper bound K on the size of assortment, 6, sequence {Xe?T.)
for all /. 2 1 do
Observe feature vectors (Ir,,1, F
Set 0g arg min L, (0)
For j = -,.... N, set Br.j = arg max o
Offer set S = arg s (s)
Receive feedback y
end for
3.3
High level ideas and sketch of the proof
We first condition on the event that 0" E (,)) for all t 2 1. Proposition 3.3 shows that this happens with high probability. From Lemma ?? (Appendix ??), we have the following concentration result on the optimistic parameter fe, associated with each product [N]:
- (l,col (1 (6)))
(4)
Now, using the optimistic choice of assortment made by the algorithm as well as the fact that 2,, B an upper bound on the true utility for each product, we can first bound the regret as follows:
R(T)
Σ
Σ JES;
the (S;,
Σ (S JES.
S
Σ
Σ JES.
(S..
Σ (S,,
JES.
T
Σ 4t 8" (S,,,, 0r (0, 00) + R2(T) = Rí R1 + R2(T).
where RT' is a second order term which we will prove to be of order O K log log(KT))//sg To show that the first term is of order O Kdllo(KT), ΣT= nلم we first use the concentration result stated in which implies the following upper bound, for some C'> 0:
R2 (T) CVdlog(KT)
Σ 1.
(S, 0" (0,00"))),sss,)00 01000
Using that H0*) 2 K2 ΣT= Ejes, T.,j we could already show that this term is of order Ö(VT) by applying the Elliptical Potential Lemma from M. However, we would then obtain a term with linear dependency in 1/K2. We show that the local information given by the terms (Se 6* (S, } and the self-coneordaane-like property of the log loss can be used derive a tighter bound on the above sum. The complete version of the proof is provided in Appendix ??.
4 Conclusion
In this paper, we study contextual dynamic pricing and assortment optimization problems under MNL choice model. We present dynamic pricing policy based on a variant of the Online Newton Step method combined with random price shocks that achieves near-optimal regret for the MNL model with adversarial contexts and dependent price sensitivities. We also propose a new optimistic algorithm for the adversarial MNL contextual bandits problem. Both our algorithms leverage the self- concordant property the MNL log likelihood function to achieve better dependency on potentially exponentially small parameters than existing algorithms. An interesting research direction would be to extend our results other choice models, such as the nested logit model, which another widely used model in the Revenue Management literature.
10

---

References
[1] Yasin Abbasi-yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Shywo-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24, pages 2312-2320. Curran Associates, Inc., 2011.
[2] Mare Abeille, Louis Faury, and Clément Calauzènes. Instance-wise minimax-optimal algorithms for logistic bandits, 2020.
[3] Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Mnl-bandit: A dynamic learning approach to assortment selection. CoRR, abs/1706.03880, 2017.
[4] Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Thompson sampling for the mnl-bandit. CoRR, 0tss1706600077,.20 2017.
[5] Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Repeated contextual auctions with strategic buyers. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, editors, Advances Neural Information Processing Systems, volume 27, pages 622-630. Curran Associates, Inc., 2014.
[6] GahhYi Ban and N. Bora Keskin. Personalized dynamic pricing with machine learning. SSRN Electronic Journal, 01 2017.
[7] Omar Besbes and Assaf Zeevi. Dynamic pricing without knowing the demand function: Risk bounds and near-optimal algorithms. Operations Research, 57(6):1407-1400, 2009.
[8] Josef Broder and Paat Rusmevichientong. Dynamic pricing under general parametric choice model. Operations Research, 60:965 -80,, 08 2012.
[9] Felipe Caro and Jérémic Gallien. Dynamic assortment with demand learning for seasonal consumer goods. Management Science, ((2)):27-292,, 2007.
[10] Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013, volume 28 of JMLR Workshop and Conference Proceedings, pages 151-159, JMLR.org. 2013.
[11] Xi Chen, Yining Wang, and Yuan Zhou. Dynamic assortment optimization with changing contextual information, 2019.
[12] Maxime C. Cohen, Ilan Lobel, and Renato Paes Leme. Feature-based dynamic pricing. In EC 16, 2016.
[13] Arnoud V. Den Boer. Dynamic pricing and learning: Historical origins, current research, and new directions. Surveys in Operations Research and Management Science, 20, 06 2015.
[14] Arnoud V. Den Boer and Bert Zwart. Mean square convergence rates for maximum quasi- likelihood estimator. Stochastic Systems, 4:375-403, 01 2014.
[15] Vivek F. Farias and Benjamin Van Roy. Dynamic pricing with a prior on market response. Operations Research, 58(1):1-29, 2010.
[16] Louis Faury, Mare Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits, 2020.
[17] Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In J. Lafferty, C. Williams, J. Shawe- Taylor, R. Zemel, and A. Culotta, editors, Advances Neural Information Processing Systems, volume 23, pages 386-594. Curran Associates, Inc., 2010.
[18) Flad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Mach. Learn., 69(2-3):169-199 2007.

---

[19] Adel Javanmard. Perishability of data: Dynamic pricing under 2017.
models,
[20] Adel Javanmard and Hamid Nazerzadeh. Dynamic pricing in high-dimensions, 2018.
[21] Adel Javanmard, Hamid Nazerzadeh, and Simeng Shao. Multi-productt dynamic pricing in high-dimensions with heterogeneous price sensitivity, 2019.
[22] Robert Kleinberg and Tom Leighton. The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS '03, page 594, USA, 2003. IEEE Computer Society.
[23] Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvári. Tight regret bounds for stochastic combinatorial semi-bandits. CoRR, abs/141000944 2014.
[24] Renato Paes Leme and Jon Schneider. Contextual search via intrinsic volumes. In Mikkel Thorup, editor, 59th IEEE Anmual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 268-282 IEEE Computer Society, 2018.
[25] Lihong Li, Yu Lu, and Dengyong Zhou, Provable optimal algorithms for generalized linear contextual bandits. CoRR, abs/ 0td//703.0000 700400 2017.
[26] Allen Liu, Renato Paes Leme, and Jon Schneider. Optimal contextual pricing and extensions. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 13, 2021, pages 1059-1078. SIAM, 2021.
[27] Ilan Lobel, Renato Paes Leme, and Adrian Vladu. Multidimensional binary search for contextual decision-making. Oper. Res., 66(5):1346-136)) 2018.
[28] D. Mefadden. Modelling the choice residential location. Transportation Research Record, 1977.
[29] Mila Nambiar, David Simchi-Levi and He Wang. Dynamic learning and pricing with model misspecification. Management Science, 65(1 1):4880-5000, 2019.
[30] Min-hwan Oh and Garud Iyengar. Thompson sampling for multinomial logit contextual bandits. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, F. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32, pages 3151-3161. Curran Associates, Inc., 2019.
[31] Min-hwan Oh and Garud Iyengar. Multinomial logit contextual bandits: Provable optimality and practicality. In Thirty-Fifihh AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty- Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 9205-9213. AAAI Press, 2021.
[32] R. L. Plackett. The analysis of permutations. Journal of the Royal Statistical Society. Series (Applied Statistics), (4(2):193-203) 1975.
[33] Sheng Qiang and Mohsen Bayati. Dynamic pricing with demand covariates, 2016.
[34] Lijing Qin, Shouyuan Chen, and Xiaoyan Zhu. Contextual combinatorial bandit and its appli- cation on diversified online recommendation. In Mohammed Javeed Zaki, Zoran Obradovic, Pang-Ning Tan, Arindam Banerjee, Chandrika Kamath, and Srinivasan Parthasarathy, edi- tors, Proceedings of the 2014 SIAM International Conference on Data Mining, Philadelphia. Pennsylvania, USA, April 24-26, 2014, pages 461-469. SIAM, 2014.
[35] Idan Rejwan and Yishay Mansour. Combinatorial bandits with full-bandit feedback: Sample complexity and regret minimization. CoRR, awssaabss......... 122.4
12624, 2019.
[36] Paat Rusmevichientong Zuo-Jun Max Shen, and David B. Shmoys. Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Operations Research, 2010. 2010.
12

---

[37] Denis Sauré and Assaf Zeevi. Optimal dynamic assortment planning with demand learning. Manufacturing Service Operations Management, 15(3):387-404, 2013.
[38] Quoc Tran-Dinh, Yen-Huan Li, and Volkan Cevher. Composite convex minimization involving self-concordant-iik cost functions, 2018.
[39] Yining Wang, Xi Chen, and Yuan Zhou. Near-optimal policies for dynamic multinomial logit assortment selection models. S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31, pages 3101-3110. Curran Associates, Inc., 2018.
[40] Jianyu Xu and Yu- Xu-Xiang Wang. Logarithmic regret feature-based dynamic pricing. CoRR, abs/2102.10221, 2021.
2021.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information how to answer these questions. For each question, change the default [TODO] to [Yes]. [No], or [N/A] You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license the code and datasets? [Yes] See Section.
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix for the complete proofs.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)?[
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
13

---

(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "g-Uc5jx9k8U", "reviewer": "Reviewer_eXno", "summary": "This paper studied dynamic multi-product pricing and assort problems under the Multinomial Logit Model (MNL). For multi-product pricing problems, they proposed the Online Newton method for multiple product pricing algorithms with $O(d\\sqrt{T}\\log(T))$ regret bound. For assort problems, they proposed OFU-MNL with better dependency on the problem-dependent parameter $\\kappa$.", "questions": "The author mentioned that optimal regret bound $(O(\\sqrt{T}))$ is achievable in the case of a single product with Feature-based dynamic pricing. Does it mean that if we apply the algorithm in the paper to a single product, it will lead to a slightly worse regret bound compared to the optimal one? \n\nCan the author comment on the running of Algorithm 1? Since it requires an inverse of a Hessian matrix at every time step, it may not be as efficient as first-order methods.", "limitations": "There is no potential societal impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "For dynamic pricing, the paper extends the current literature to multiple products with feature-dependent price sensitivities. I believe it is an important extension and has many applications in practice. The idea is that it can consider the problem as an online convex optimization problem and use a famous technique (Online Newton step) to deal with it. However, due to the existence of uninformative prices, it can break the ONS algorithm. Therefore, the proposed algorithm needs to introduce random shock to increase exploration. \n\nTechnically, both online newton step and random shocks have been applied to dynamic pricing under different settings as the authors pointed out in the literature, therefore I am not surprised when the authors can derive the regret bound for a new setting of multiple products. I think a very strong assumption in the paper compared to the related work is that after each round $t$, the seller can observe $q_t$, the customer probability of buying products (so that the seller can update the estimate $\\gamma_t$). In Xu and Wang's work (Logarithmic Regret in Feature-based Dynamic Pricing), it seems that they only require observing indicator $y_t$ of customer buying the product or not, which is more practical. \n\nExperiment: the experiment results in Appendix D show an advantage of the proposed algorithm compared to a similar online Newton method (ONSP) with a single product. However, the experiment result is not convincing since it is based on a stochastic setting whereas all the theoretical results in this paper focus on adversarial counterparts.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "eoxgl9FURLA", "reviewer": "Reviewer_zMXk", "summary": "In this paper, the authors studied contextual dynamic pricing and assortment optimization problems under the MNL choice model. They proposed two algorithms: (1) a dynamic pricing algorithm which combines a variant of the ONS algorithm and random price shocks, and showed that this algorithm achieves $O(d \\sqrt{T} \\log{T})$ regret under adversarial arrival. (2) an optimistic algorithm for the adversarial MNL contextual bandits problem, and showed that it achieves better dependency on parameter $\\kappa$ than existing algorithms, where $\\kappa$ is a problem-dependent constant that measures deviation from the linear model. ", "questions": "1. In Algorithm 2, there is a step that requires one to choose the set of $K$ items maximizing the expected revenue. Are you simply selecting the $K$ items with the highest $x_{t, i}^\\top \\tilde{\\theta}_i$ here? \n2. If so, any ideas what will happen when the rewards are no longer uniform and we also need to consider assortments with size less than $K$?\n", "limitations": "None.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The dynamic pricing policy proposed in Section 2 uses interesting ideas that combine ONS method with random price shocks, and is shown to attain near-optimal performance. \n2. The optimistic algorithm for adversarial MNL contextual bandits proposed in Section 3 is shown to achieve better dependency on $\\kappa$, and does not assume knowledge of $\\kappa$ a priori. \n3. The authors provide clear and thorough proof for their theoretical results. \n\nWeaknesses: \n1. The authors provided a brief discussion of related literature on contextual dynamic pricing/assortment problems in the beginning of section 1. It could be desirable to have a separate and more detailed discussion of related work that compares this work with the previous literature. \n2. While the regret bounds are theoretically sound, it could be good to also include some numerical studies here to demonstrate the performance of the algorithm and verify the dependency on parameters $T$ and $d$ of the regret bound. Another thing that is missing from the current work is the runtime for both algorithms. \n3. It appears that the design of the algorithms leverages the self-concordant property of the MNL log likelihood function. More discussions can be provided here to motivate why the use of self-concordant property is important to the proof. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3aDQ9-c6xxV", "reviewer": "Reviewer_rfSu", "summary": "In this work, the authors study two different online-learing problems, a multi-product dynamic pricing problem and a multi-product dynamic assortment optimization problems, under a multinomial logit (MNL) model choice model. In the pricing problem, at each round t, a customer comes with a candidate set of features describing her preference on corresponding products, and the seller (we) are asked to set prices for these candidate products. After seeing these prices, the customer will choose at most one of them to buy, according to the MNL model with linear parameters. The goal is to maximize the expected revenue. In the assorting problem, the situation is slightly different: At each round t, a customer comes with a set of features describing her preference on all products, and the seller (we) are asked to propose a list of $\\leq K$ products as candidates. After seeing these candidates, the customer would take at most one product from these candidates. In the assorting problem, the goal is to maximize the probability of not-buying-empty.\n\nIn this work, the authors propose algorithms for both problems: For the pricing prolem, they propose an Online-Newton (ON)-based pricing algorithm which achieves an $O(d\\log{T}\\sqrt{T})$ regret. This result matches the existing information-theoretic lower bound at $\\tilde{O}(\\sqrt{T})$. For the assorting problem, they propose an OFU-MNL algorithm that achieves an $O(d\\sqrt{\\kappa T}+d^2\\frac{\\log(T)}{\\kappa})$ regret. This result improve the existing results by reducing the dependence on $\\frac1{\\kappa}$ as $\\kappa=o(1)$.", "questions": "Please point it out directly in the rebuttal if I am wrong in the following questions/suggestions.\n\n1, In Line 34 the authors mentioned the regret on the assorting problem, without firstly describing the goal of assorting and the (informal) definition of its regret. This could be confusing to the readers.\n\n2, In Line 86, the authors mentioned that an $O(d\\log{T})$ regret is implied by their result for single-product pricing problem. However, I did not find such a reduction in the paper. Is there a remark/corollary regarding this, or a trivial reduction to this result?\n\n3, In Line 93, the authors mentioned that their ON-based pricing algorithm outperforms the ONS-based pricing algorithm in [41] by improving the dependence on a \"potentially exponentially small constant\". However, I did not find (1) how the small constant is like and (2) what improvement this work has made, in either the main pages or Appendix D. Only descriptive words are in Line 181-191\n\nI guess this small constant could be $\\kappa$ as is mentioned in Line 190-191, but I am not quite sure: (1) a $\\kappa$ is defined for the assorting problem (see Line 267) instead of the pricing problem (as they have different definitions on the $q_{t,j}$ functions), and (2) the constant in the regret of Algorithm 1 is also $\\Omega(\\frac1{\\kappa^2}$ (see Line 592). Please explain this issue briefly as [41] adopts a quite similar method and this work indeed outperforms [41] in practice.\n\n4, In Line 139, I think it is not a proper way to describe the probabilistic distribution like this: As the authors only specified the probability of product $j$ being purchased, a straightforward question could be: how are these purchases correlated to each other? Of course, we know from context that these purchases are mutually exclusive and the probability is a multinomial on these products, but this could still be very misleading. I suggest the authors clarify this part by saying \"the customer purchases one product $j\\in[k_t]\\cup 0$ ...\".\n\n5, There should be an explanation on Assumption 2.3. My understanding: price elasticity (or \"price sensitivity\" in this work) should not be too small (i.e., close to 0). This is reasonable and practical, but needs explanation.\n\n6, In Line 166, where does this $\\lambda$ sequence come from? This makes the adjacent paragraph (Line 166-169) unclear. (A minor issue: for the convexity of $l_t$, either prove it or cite it.)\n\n7, In Line 196, the author said that they treated $K$ as a constant. This is important for regret analysis and comparison, so I suggest the authors to make it as an assumption and state it with other assumptions (e.g., after Assumption 2.3).\n\n8, In Line 219, the author said \"it is meaningful only with random price experimentation\". This seems not very clear to me. Does it mean that you have to further make use of the randomness of $p_{t,j}$ to upper bound the first term of (1)?\n\nMaybe an equation showing how to apply Lemma 2.6 to the proof of Theorem 2.4 would be more informative and concise.\n\n9, In Line 257, the author denoted the \"optimal assortment\" as $S_t^*$. My understanding: $S^* = \\arg\\max_S q_{t,j}(S, \\theta^*)$, i.e., minimize the prob of choosing nothing. This is equivalent to maximizing the sum of $exp\\{x^{\\top}\\theta\\}$? Is that right?\n\nBesides, I noticed a number of notation inconsistence in this paper. Therefore, I strongly recommend the authors to carefully examine the paper and fix all notation issues.", "limitations": "The authors indeed discussed the potential extension of this work (e.g., \"the nested logit model\" as mentioned in their conclusions). However, there's not much on the social impact. This is not a big issue as it is a theoretic-oriented research, but I recommend the authors to discuss more on the limitations and potential social impacts (especially these negative aspects) in their Appendix.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1, This work studies online multi-product pricing and assortment problems and proposes provable algorithms. The problem setting is meaningful. Their regret upper bounds are either optimal (for pricing) or better than existing results (for assortments).\n\n2, For the pricing problem, they use Online Newton method + self-concordant-like property to substitute the role of an ONS algorithm, while also saving the regret dependence on constants. Their numerical result (in Appendix) also shows the significance of their work over existing methods in practice.\n\nWeakness:\n\n1, Their improvement from existing theoretical results on the assorting problem is not substantial.\n\n2, Problem formulation and literature reviews are insufficient: It is unclear how to place this work in the stream of pricing/assorting researches.\n\nOverall, this is a good work to get in, and I would like to raise my score as long as the authors properly address my concerns.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept