Dynamic Pricing with Monotonicity Constraint under Unknown Parametric Demand Model
Authors: Su Jia
Andrew A Li
Ramamoorthi Ravi
Venue: NeurIPS 2022 Accept (2022)
Keywords: dynamic pricing
monotonicity constraint
multi-armed bandits
online learning
markdown pricing

Abstract: We consider the Continuum Bandit problem where the goal is to find the optimal action under an unknown reward function, with an additional monotonicity constraint (or, "markdown" constraint) that requires that the action sequence be non-increasing. This problem faithfully models a natural single-product dynamic pricing problem, called "markdown pricing", where the objective is to adaptively reduce the price over a finite sales horizon to maximize expected revenues. 

Jia et al '21 and Chen '21 independently showed a tight $T^{3/4}$ regret bound over $T$ rounds under *minimal* assumptions of unimodality and Lipschitzness in the reward (or, "revenue") function. This bound shows that the demand learning in markdown pricing is harder than unconstrained (i.e., without the monotonicity constraint) pricing under unknown demand which suffers regret only of the order of $T^{2/3}$ under the same assumptions (Kleinberg '04). 

However, in practice the demand functions are usually assumed to have certain functional forms (e.g. linear or exponential), rendering the demand-learning easier and suggesting lower regret bounds. We investigate two fundamental questions, assuming the underlying demand curve comes from a given parametric family: (1) Can we improve the $T^{3/4}$ regret bound for markdown pricing, under extra assumptions on the functional forms of the demand functions? (2) Is markdown pricing still harder than unconstrained pricing, under these additional assumptions? To answer these, we introduce a concept called markdown dimension that measures the complexity of the parametric family and present tight regret bounds under this framework, thereby completely settling the aforementioned questions.

Dynamic Pricing with Monotonicity Constraint Under Unknown Parametric Demand Model
Su Jia, Andrew Li, R. Ravi Tepper School of Business Carnegie Mellon University isjial, a ravi Gandrew. cmu. edu
Abstract
We consider a Continuum-Arme' Bandit problem with an additional monotonicity constraint (or "markdown" constraint) the actions selected. This problem faith- fully models a natural revenue management problem, called "markdown pricing", where the objective is to adaptively reduce the price mize the expected revenues. Chen ([3)) and Jia et al (19)) recently showed a tight T8/1 regret bound over T rounds under minimal assumptions unimodality and Lipschitzness in the reward function. This bound shows that markdown pricing is strictly harder than unconstrained dynamic pricing (i.c., without the monotonicity constraint), which admits T2/3 regret under the same assumptions [[] However, in practice, demand functions are usually assumed to have certain functional forms (e.g. linear or exponential), rendering the demand learning easier and suggesting better regret bounds. In this work we introduce a concept, markdown dimension, that measures the complexity of a parametric family, and present optimal regret bounds that improve upon the previous 73/1 bound under this framework.
finite horizon maxi-
Introduction
Dynamic pricing under unknown demand arises naturally for the sale of new products, where the demand function is not available in advance. The seller in this case has to learn the demand function over time and hence faces leamningvvsearmnng trade-off. This problem is therefore usually formulated as Multi-Armed Bandit (MAB) model. Although bandit problems have been well understood theoretically, practice, however, we rarely see retailers implement such policies. This is a largely because some practical constraints which can potentially cause customer dissatisfaction are overlooked. For example, a price increase may sometimes create manipulative image of the retailer and negatively impact their ratings. For example, [13] analyzed the online menu prices of set of restaurants and concluded that "on average, 1% price increase leads to 3-5% decrease in online ratings". Therefore, retailers sometimes implicitly face monotonicity constraint (which we call "markdown constraint"), which requires that the prices selected be non-increasing. A pricing policy that satisfies such constraint is usually referred to as markdown pricing policy.
Thus motivated, in this work, we consider the markdown pricing problem with unknown demand, under various assumptions. Although unconstrained dynamic pricing under unknown demand has been extensively studied, little is known about markdown pricing under unknown demand. Recently, [3] and [9] independently showed that unimodality and Lipschitzness in the revenue function (defined as the product of the price and the mean demand) are necessary to achieve sublinear regret. this setting, any reasonable policy must reduce the price at a moderate rate and stop only when there sufficient evidence for overshooting the optimal price. By selecting suitable parameters, [3, 9] showed that the above policy indeed optimal, achieving tight 3/4 regret bound.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

However, in practice, it is usually assumed that the demand function has certain parametric form, such linear, exponential or logit form. Intuitively, this extra structure enables faster learning rate and suggests better regret bounds. This motivates our first question:
Q1) Can we improve the T regret bound for markdown pricing for parametric demand families?
Noticeably, there is a known separation result between under the assumption that the corresponding reward function is Lipschitz and unimodal. In fact, [3. 9] showed a tight T regret bound, which asymptotically higher than 72/33, the optimal regret bound for unconstrained pricing ([11) under the same ussumptions. This highlights the extra complexity caused by the monotonicity constraint, and motivates the next question:
Q2) Is there still provable "separation" between markdown and unconstrained pricing under parametric assumptions?
While can answer the Q1 and Q2 for specific parametric families, aim at finding unified framework that captures the hardness of demand learning for given parametric family. This motivates the following question:
Q3) Can we find general framework to unify the regret bounds for different categories of families, rather than specific results for specific families?
In this work, we propose such framework by introducing concept called markdown dimension. We provide efficient markdown policies for each markdown dimension, which we also show to be best possible, thereby completely settling the problem.
1.1 Our Contributions.
In this work, we make the following contributions.
1. New Complexity Measure for Demand Learning. We introduce a new concept called markdown dimension, which captures the complexity of performing markdown pricing on family, answering Q3. Within this framework, we provide a complete settlement of the problem as specified below.
2. Markdown Policies with Theoretical Guarantees. For each finite markdown dimension d 2 O, we present an efficient markdown pricing policy with sublinear regret. The explo- ration proceeds in phases of varying lengths. In each phase j. the policies derive confidence interval I, S fj-1 for the optimal price p" based on observations from evenly spaced prices, which are lower than the prices used in phase j 1. The exploration terminates if there is sufficient evidence that the current price is lower than p" We show that for d = 0 and d 2 1, our policies achieve regret O(log" T) and Ö(T respectively, settling Q1.
3. Separation From Unconstrained Pricing: Tight Lower Bounds. We complement our upper bounds with a matching lower bound for each integer d. More precisely, we show tight 2(log" T) lower bound for d = which is lower than the known O(log T) regret bound without this monotonicity constraint (see [2]). For finite d 2 1, we show an Q(T x41 lower bound, which not only matches our upper bound but is also higher than the tight @(T1/2 bound without markdown constraint (see [2, 10)). These lower bound results combined settle Q2
4. Impact of Smoothness:
We go further to refine our bounds and investigate the impact of smoothness of reward function around the optimal price. We consider a sensitivity parameter 8, which essentially says that the reward function is only Oss") suboptimal if the price is distance away from the optimal price. For both finite and infinite d, we extend our upper bounds to incorporate 8.
As the most basic case, one can verify from Taylor's Theorem that when the demand function is assumed to admit (i) continuous second derivative, and (ii) an optimal price in the interior of the domain, then We highlight our results for s = 2 in red in Table 1, where denotes tight upper and lower bounds.

---

Markdown Dimension
Markdown Pricing
Unconstr. Pricing
d = 0
(log T) ((Td/(tt))
eloog T) [2]
1 1 d < 00 d = 00
(VVT) [2]
(TT3/4) [3, 9]
((T2/3) [11]
Table 1: Regret bounds for 2.
1.2 Related Work
In the Multi-Armed Bandit (MAB) problem, the player is offered finite set of arms, with each arm providing random revenue from unknown probability distribution specific to that arm. The objective of the player to maximize the total revenue earned by pulling a sequence of arms (e.g. [12]). Our pricing problem generalizes this framework by using an infinite action space [0, 1] with each price p corresponding to an action whose revenue is drawn from an unknown distribution with mean R(p). In the Lipschitz Bandit problem (see, e.g., [I]), it is assumed that each z E [0, 1] corresponds to an arm with mean reward p(z), where z is an unknown L-Lipschitz function. For the one-dimensional case, [11] showed a tight ((T2/3) regret bound.
Recently there is emerging line of work on bandits with monotonicity constraint. [3] and [9] recently independently considered the dynamic pricing problem with monotonicity constraint under unknown demand function, and proved nearly-optimal 73/4 regret bound assuming the reward function is Lipschitz and unimodal. Moreover, they also showed that these assumptions are indeed minimal, in the sense that no markdown policy achieves o(T) regret without any one of these two assumptions. Motivated by fairness constraints, [8] and [15] considered general online convex optimization problem where the action sequence is required to be monotone.
Other constraints on the arm sequence motivated by practical problems are also considered in the literature. For example, motivated by the concern that customers are hostile to frequent price changes (see e.g. [5]), [4, 14] and [16] considered pricing policies with given budget in the number of price changes Motivated by clinical trials, [6] studied the best arm identification problem when the reward of the arms are monotone and the goal is to identify the arm closest to a threshold.
Model and Assumptions
We begin by formally stating our model. In this work we assume an unlimited supply of a single product. Given a discrete time horizon of T rounds, in each round t, the policy (representing the "seller") selects price Pt (the particular interval [0, 1] is without loss of generality, by scaling). The demand D, in this round is then independently drawn from a fixed distribution with unknown mean D(p:). and the policy receives revenue (or reward, which we will use interchangeably) p. for each unit sold, and hence a total of pt Dj revenue in this round. The only constraint the policy must satisfy is the markdown constraint: P1
Pr with probability 1.
The function D(p) which maps each price p to the mean demand at this price is known as the demand function. For any policy! π and demand function D(-), we use r(T, D) to denote the expected total reward of under D. Rather than evaluating policies directly in terms of r(m, D), it more informative (and ubiquitous in the literature on MAB) to measure performance using the notion of regret with respect to a certain idcalized benchmark. Specifically, since we assumed unlimited supply, when the true reward function is known, the seller simply always selects revenue- maximiinn price PD = arg maxpe|o.1] P D(p) at each round, and we denote this maximal reward rate to be rb = max [0 p- D(p). The regret of policy is then defined with respect to this quantity, and we seek to bound the worst-case value over given family of demand functions.
Definition (Regret). For any policy и and demand function D, define the regret of policy и under D Reg(m, (T, D) := ri T r(m, D). For any given family F of demand functions, the worst-case regret (or simply regret) of policy x for family F is Reg(T, F) := suppe (egg(T,)) D).
Formally, a policy is sequence æ = (mT) of mappings where n. [0, 1 x R + 10, corresponds to the decision made at time t, based on the realized demands and prices selected up till time t L.
3

---

2.1 Basic Assumptions
Now we state the common assumptions that all of our results rely on. A demand function D(-) is associated with revenue fumetion (or, reward function) R(p) p D(p). Sometimes it is more convenient to work directly with the revenue functions, which cases we abuse the notations and denote by Reg(z, (z, R) the regret of under reward function R.
Definition 2 (Optimal Price Mapping). Let F be a set of functions defined on S S R. For any function R: S + R. let (R) be the subset of its global maxima on S. The optimal price mapping p" FF + S is defined as p" (R) = inf (R).
We first introduce standard assumption (see e.g. (2]) that the derivative of R vanishes at p" (R). Assumption 1 (First Order Optimality). We assume that every reward function It is differentiable on its domain, and moreover, R2 (''p" (R)) 0.
If, in addition, R twice continuously-de diffeeeeeeeeeeee.bbeleee then by Taylor expansion around p², |R (n")
R (p" + E) = "R" ) =² + o(E?). Thus, if policy overshoots the optimal price by E, then only an (s=²) loss is incurred in each round. We next introduce a distributional assumption.
Definition 3 (Subgaussian Random Variable). Define the subgaussian norm of random variable X as || == inf 0: B[ex*" S 2). Say X subgaussian if || llve < oc.
Assumption 2 (Subgaussian noise). There exists constant C2g such that under any true demand function and any price p, the random demand X at price satisfies || S C.g.
2.2 Warm-up: Markdown Pricing on Linear Demand
To introduce the key concept, markdown dimension, let's take linear demand warm-up. Consider (x;; f) 0. - 82x for x E [2. 1] and the following natural markdown policy for F= 0): 01, 02 E 2 }]}: collect number of samples at two prices P1. P2 close to 1, and denote by d, dz the empirical mean demands. By the Fundamental Theorem of Algebra, since degree-d polynomial can be uniquely determined by its value at d distinct points, there is & R² satisfying (p::; 0) de for 1, 2. Finally, select the optimal price of ((:; 0) in remaining rounds.
This policy is "robust" in the following sense. Suppose d, deviates from the mean D(p;; f) by then the estimation error in 9 P1 PI-P2] i.e., proportional 8 and inverse proportional to the gap
between the two sample prices.
For more complex demand models, the dependence on the "divergence" of the sample prices changes. To characterize such dependence, we introduce the notion of markdown dimension. Informally, a parameterized family has markdown dimension d if for any set of d prices at distance l apart, an (6) error on the estimated demands results in an O Aa estimation error on the model parameter. We make this idea formal in the subsequent sections.
2.3 Identifiability and Robust Parametrization
trade-off for markdown pricing becomes harder to manage as the given family becomes more complex. Consider, for example, linear demand functions. If each function takes the form (pp e) = 1 + cp where only e E (0, 1) is unknown and p E [0, 1]. then the seller simply needs estimate the price elasticity e by sampling sufficiently many times at p 1.
Intuitively, the
In contrast, if the demand function is ((p a, b) = a- bp where both a, are unknown, then sampling at one price would not suffice. Rather, needs to select (at least) two distinct prices, say p and p². to fit a linear function, thereby facing the following dilemma. Suppose p < p' are far apart, then, p may be far away from the optimal price p" if p" is close to p', resulting in high regret. Otherwise, when p. p' are close-by, the demand learning requires a high volume of samples, which also leads to high regret.
Thus we reach a natural question: can we introduce a notion of complexity to measure the difficulty of performing markdown pricing on given family, and then provide tight regret bounds in terms for each level of complexity? In this work, we propose a novel concept of markdown dimension and provide nearly-optimal regret bounds in terms of this complexity metric. The formal definition relies

---

on two other concepts which we introduce in the next two subsections: the identifiability of a family, and the robustness parametrization.
Identifiability Our notion of identifiability generalizes key property of single-variable polynomi- als, that every degree-d polynomial can be uniquely determined by its values at any (d+ 1) points. To present the formal definition, we first introduce a mapping which, for fixed subset of prices, assigns each demand function profile based on its values at those prices.
Definition (Profile Mapping). Consider a set F of real- functions defined on A R. For any p (Po, Pl.....,.. Pa) E A the profite-mpppng at prices is defined as
@p F F+RR++ D (D(po), D(pL)..... D(pa)).
We may subsequently call (D) the profile of function D p.
Informally, a family of functions is said to be d-identifiable, if the graphs of any two functions intersect for at most d times. For example, the family of all degree polynomials is d-identifiable. Definition 5 (Identiffabilitty). A family F of functions defined on S C T is d-identifiable, if for any distinct po- Pi.... Pa S, the profile mapping + po.....p is injective, i.e. F(f) + F(f) for any distinct f, F..
We will soon use the following fact: if family is d-identifiable, then for any distinct po. P1.... Pa the inverse profile-mapping pp Rp + J exists, where RS is the range of the mapping Pp.
Robust Parametrization We first formally define a parametrization.
Definition 6 (Parametrizaaionn). An order-m parametrization for family FF of functions is one-to- one mapping from some set C R to F. Moreover, each θ is called a parameter.
We use ((p; 8) denote the function in F that parameter A corresponds to. For example, for D(p; 0,, 02) = 02 02 p is a parametrization of the family of linear functions. As standard assumption (see e.g. [2]), we assume O be compact, which leads to many favorable properties.
Assumption (Compact Domain). The domain θ of the parametrizztion is compact.
Under this assumption, the demand functions in F are bounded, and thus we may without loss of generality scale the range (i.e. target space) of those functions be [0, I].
Assumption 4 (Smoothness). The mapping D [0, 1] x θ - RR is twice continuously differentiable. In particular, since [0, 1] x θ is compact, under the above assumption, there exist constants (G) 0 such that (p.) 0)1 I CU) for any (p. (f) E [0, 1] θ and j 0, 1,
By abuse of notation, we view the optimal price mapping p" as being defined on θ, rather than on FF before. Formally, let (0) be the of global maxima of R(x;)) then p" p0))) = inf R(æ; 0). For
example, for D(p; 01; 02) = 02 02 p one can verify that p" 02, The next assumption allows us to "propagate" the estimation error in 0 to that of p" (8).
20g
Assumption (Lipschitz Optimal Price Mapping). The optimal price mapping p² O [0, 1] is C'-Lipschitz for some constant C** > O.
This assumption has appeared in the previous literature on parametric demand learning, see e.g. Assumption ((c) of [2]. Moreover, it is satisfied by many basic demand functions such as linear, exponential and logit demand. For instance, D(p;e) = 1 cp where p. c [0, 1]. then p (c) = minf 2: 1). which is 1-Lipschitz. Nonetheless, this assumption is somewhat unnatural as it is not made on the parametrization directly, we leave it open whether there is an assumption imposed directly on F that implies this assumption.
1
The final ingredient for robust parametrization is motivated by nice property of the natural parametrization D(p; 8) = Σ f,p² for polynomials. Consider any distinct Pu: Pi.... .d. and distinct real numbers yo: 3/1 Yd representing, for example, the mean reward at each ps. We can then uniquely determine degree-d polynomial by solving the linear equation VpO y where
5

---

0 = (fu, 01..,,0) 02)", y = (yo, 91..... Ba) and p := (po...... Pd) is the Vandermonde matrix. One can easily verify that V, is invertible if and only if p: 's are distinct, in which case we have 0 = -Vp-y. Next we consider the effect of a perturbation on y, in terms of the following separability parameter.
Ba).
Definition 7 (Separability). For any p (po:-., - Pa) [Rd+1 define hp)) = minizi Ip: Pýl-
To motivate the general definition of robustness, first consider a result specific to polynomials. Recall that Rp range of the profile mapping 4p.
Proposition (The Natural Parametrization for Polynomials is Robust). There exist constants C1, C2 > such that for any p E [0, 1]st1 with < h(p) I C1, and y E Rp with lly - ylls S C1. it holds that IVp y bl I C2 ly - Vllso h(p)
More concretely, let D(p; 0) be the underlying polynomial demand function, then y = ViD are the mean demands the prices in p. Suppose observe empirical mean demands y = (Mo, Ø1:-... -i.---> Da) at prices p. then we have a reasonable estimation 0 = V Our Proposition 1 can then be viewed upper bound the estimation error ||0 0 in terms of h(p) and y -
In order to achieve sublinear regret, we need to ensure hp) = o(1) as T oc. Moreover, the rate of this convergence crucially affects our regret bounds. Proposition establishes nice property for polynomials, that the estimation error scales as h-d,, as - 0+. We introduce robust parametrization by generalizing this property beyond polynomials. Loosely, an order-d parametrization is robust, if the bound in Proposition holds.
Definition 8 (Robust Parametrization), An order-d parametrization 0 F is robust, if (1) it satisfies Assumptions 3, 4 and 5, and
(2) there exist constants Ci. C2 > O such that for any p E Rd+1 with 0 < h()) S C1 and any
y. E Rp with ||y oo S C1 holds that || (y) 4 (y')l')) S C2 C2-1lly-y llyy h((p)
In particular, when = 0, this inequality simply says pp -1 is Cz-Lipschitz.
2.4 Markdown Dimension
Now we are ready to define the markdown dimension.
Definition 9 (Markdown Dimension). The markdown dimension (or simply dimension) for family F of functions, denoted d(F), is the minimum integer d 2 0 such that F is (i) d-identifiable, and (ii) admits robust order-d parametrization. If no finite d satisfies the above conditions, then d(FF) co.
We further illustrate our definition by considering the dimensions of some basic families. As the simplest family, one may verify that our definition of 0-dimensional family is equivalent to the separable family as defined in Section 4 of [2]. We provide more concrete examples below. Details can found in Appendix A.
Proposition 2. Let ()r; = Ei= E/=0 0zرو and suppose F [D(x;) 0 E }} satisfies Assump- tions 3, 4 and 5. Then, d(F) d.
Proposition 3 (0- (O-Dimensional Families). The following families F1. and F3 are O-dimensional. arr for E [/. and Fi (Da(.)
(1) |Single-Parameter Linear Demand] Let (x)
E 2 ]]
(2) Exponential Demand] Let (2(x) ol for x E [ 1] and F2 = (D (z) a E [1 }. el ax (3) [Logit Demand] Let Da(x) = I+et-ar for o [ and F3 = (D.(x): a [1 1]}
Finally, we observe that by our definition, if a family of functions is not d-identifiable for any d, then d(F) do. For example, for any distinct prices, there exist multiple (more precisely, infinitely many) Lipschitz functions having the same values on these d prices.
Proposition 4. Let be the set of 1 1-Lipschitz functions from [0, 1] to [0, 1]. then d(F) = co.
2.5 Sensitivity
Consider the Taylor expansion of a reward function Rxx) around an optimal price p": R(p) R(p") + 0 (p)) p²) + R(3) (p") p²)² -... Suppose the first nonzero derivative

---

is (p"). Then, the higher k, the less sensitive the revenue is to the estimation error in p². We capture this aspect in the following notion of sensitivity.
Definition 10 (Sensitivity). A reward function R is s-sensitive if it is (s 1)-times continuously differentiable with Rd (p" (R)) = =... .....
R((-1) (p" (R)) 0 and R(*) (p^ (R)) 0. A family F
of reward functions is called s-sensitive if (a) every R. E F is s-sensitive,
(b) it admits a parametrization R(;; ff) satisfying Assumptions to 5,
(c) there is a constant Ce >> such that R!*) (p" (P)) S -Cs < 0 for any R E F, and
(d) for each O I j S 8, there exists a constant CU) s.t. (2; 0) CV), Vo E [0, 1).0 E
For example, let 2 3 and R(x;0) 0 0-15 11 21 for x E [0, and any 0 RR then (R(x;)) 0) 0 E | 11} is an s-sensitive family. Note that by Taylor's Theorem, |R(p" + (DR(pp)) Oes)). Consequently, if policy emrs by in the optimal price, the regret per round is O(="), lower than the per-round regret ((=²) in the basic case. In each of the next three sections, we will first present the regret bounds for the basic case 2, and then characterize how this bound improves as increases.
3 Zero-Dimensional Family
We start with the simplest case, O-dimensional demand functions. As opposed to the optimism the face of uncertainty in UCB policies, our Cautious Myopic policy (Algorithm 1) adopts conservatism in the face of uncertainty. More precisely, we partition the time horizon into phases where phase j consists of i2 [9] log T"] rounds, and thus in total there are K O(log T log log T') phases. In each phase. the policy builds a confidence interval I for the true parameter using the samples collected in this phase, and sets the price for phase j to be the largest optimal price of any "surviving" parameter 0 E [-. We write (63 = Ek=o lx and for convenience ((0) 0.
Algorithm I Cautious Myopic (CM) Policy.
Input: a family of demand functions and time horizon T.
2: Pi <-1
% Initialization
3: for j 1,..., K do
4: for t #0-1)- +,,
((-11) 1,,.,,, + tú do
5: It 4 Pj
Select pj for ty times in phase j
6: Observe realized demand D.
7: end for
8:
d,
-== D20-147
% Empirical mean demand in phase j % Estimate parameter
9:
0
(dg)
10:
Wj + 4C2 Cary T
% Width of the confidence interval % Conservative estimation of the optimal price
11:
Pjt1 + max 1p (0) 10 0,1 S woj
12: Pj+1 &- min 11tt1
% Ensure monotonicity
13:
end for
Theorem ZZmoo-Dimnnionnal Upper Bound). Let F be any O-dimensional, s-sensitive family of demand functions. Then the Cautious Myopic (CM) Policy has regret
Reg( (Dg(CM,F) = - (Ooog"21)) T), Olog T), if 2.
if =
Remark 1. It is worth noting that this bound is asymptotically higher than the O(log I') upper bound for unconstrained pricing ([2]). Intuitively, this is because the CM policy purposely makes conservative choices of prices to avoid overshooting.
But can we achieve ologg² T) regret by behaving less conservatively? We answer this question negatively, and provide a separation between markdown and unconstrained pricing for dimension
Theorem 2 Seroo-Diennsoonal Lower Bound). There exists O-dimensional 2 2-sensitive family F
such that for any policy x, we have Reg(T, F) D(log" TT).
7

---

Dintee-Dmmenionnl Family
For dimension d, the learner needs d + distinct sample prices, opposed to just one price when = 0. This, however, incurs extra regret, since the optimal price may lie between these sample prices. A policy faces the following trade off. If the gap is large, the policy may learn the parameter efficiently, but there is potentially a higher regret due to overshooting, if the true optimal price lies between the sample prices. On the other extreme, if the gap small, there is less risk of overshooting but a slower rate of learning.
We introduce our Iterative Cautious Myopic (ICM) Policy (Algorithm 2) that hits the sweet spot. The policy consists of m phases. In phase j E [m]] it selects Pj h, ..... Pj dh each for T₃ times. Based on the observed demands at these prices, the policy computes and a confidence interval [T. U To determine the initial price Pj+1 of the next phase, we consider the relationship between the confidence interval [T, Uy] and pj dh. There are three cases: Good Event. If Pj dh > U, then we get closer to the optimal price by setting Pj+1 Uy.
estimated optimal price PJ
Dangerous Event. Lj S P3 dh < Uz. i.e. the current price is already within the confidence interval, the policy needs to behave conservatively by setting Pj+1 Pj dh to prevent from overshooting further.
3. Overshooting Event. If L, > Pj - dh, i.e., the current price has already "overshot", the policy exits the exploration phase and selects the current price the remaining rounds.
Algorithm 2 Iterative Cautious Myopic (ICM) Policy.
[ 1: Input: F, F.m, (T))j((m)) T
2: Pi t Lg +- 0, Ug f- Initialization
3: for 1, do
4: k 0, 1.......,d do
5:
Select price Pj
kh for T3 times and observe Dı,... Dr,
6:
Da + T,
Σ 2i=1 D;
% Mean demand at Pj kh
7:
end for
8:
0 T
-1
dh (Do, Da)
% Estimate the parameter
9:
wy 2h
C2 Cag d log T
Width of confidence interval
T
10:
Lg + min { (0): - p"
0
S w/
Lower confidence bound
11:
U3 - max (0)
0 p*
0
< w/
% Upper confidence bound
12:
Uf > Pj-
dh then
13:
Pj+1 + Uj
% Good event
14:
end if
15:
if U, Pj dh > L, then
16:
Ps+1 + Pj- dh
% Dangerous event
end if
18:
if' Pj dh < L, then
Break
% Overshooting event
20:
end if
end for
22:
Select the current price in every future round
% Exploitation
Theorem 3 (Upper Bound for Finite d > 1). Suppose = 2, then for h T F T a T m+ and m log T, we have Reg (ICM,F) = Ô (T More generally, for any 2 2 and m = Ó(1), there exist Ti < ... < Tm such that Reg(ICM, F)- (Tolm.s.d) where
+ (1 + +... (+) d
p(m, s, d)
(1+ + (.)m++)))- (2) (d+1)
We complement the upper bound with a nearly tight lower bound for Theorem (Lower Bound for Finite 2 1). For any d 2 2, there exists a d-dimensional family F of demand functions such that for any markdown policy x, we have Reg(m, F) ((TT"))) d"1).
as stated below.
8

---

In our proof, for each d 2 1 we construct family of (d+ (d+1)-degree, decreasing polynomial functions which is also d-dimensional- on which any policy suffers regret (2(TaiT).
Remark 2. At first glance, when d this result seems contradict the T upper bound for unimodal, Lipschitz reward family (I3, 9)). This is not a contradiction because the unimodality assumption no longer holds. In fact, degree-d polynomial with d 2 4 is in general not unimodal.
Remark 3. An interesting case is d 1. In this case, the revenue function is unimodal, so the T upper bound from [3, 9] applies, but Theorem 3 gives stronger T upper bound.
We conclude the section by pointing out limitation of results. For each d 2 1, our regret bounds is tight in the exponent of T, however, the constants in the big-O have different dependence on d. In fact, the upper and lower bound become exponentially higher and lower in d respectively as d grows.
Infinite Dimensional Family
When d = oo, it is more convenient to work with the reward function R(x) x D(x) instead of the demand function. contrast to unconstrained pricing, there no markdown policy that achieves o(T') regret on the family of Lipschitz reward functions ([3, 9]), since the reward function may have multiple local maxima. Nonetheless, [3] and [9] showed that in addition we assume the reward function to be unimodal, then the optimal regret is T Specifically, the lower bound is established by considering reward functions that may change abruptly at p". We next show that the regret bound can be improved if we instead assume the reward function changes smoothly. In spirit, our policy is similar to that of [3] and [9]: reduce the price at uniform speed and terminate when there is sufficient evidence for "overshooting" " but we will achieve improved guarantee by choosing different step size A that decreases in the smoothness
Algorithm 3 Uniform Elimination Policy (UEm,,).
1: Input: T, A, m >
2: Initialize: Lmax + 0, w f- 20220 sg V
log
m
3: for 2, A -1 do
4: By f 1- jí
5: Select price z, for the next m rounds and observe rewards Zi...., .... Z
6:
B.j
= z
% Empirical mean reward
7:
[Lj, U P3
w. T
+ w]
% Compute confidence interval
8:
if Lj Lmux then
9:
Linax + Lj
% Keep track of the highest Lj
end if
11:
if U, Lmax then
12:
h h+j
Exploration ends, define the halting price Th
13:
Break
14:
end if
15:
end for
16:
Select price 24 in all remaining rounds.
% Exploitation phase
Theorem (Upper Bound for Infinite-iimensional Family). Let FD be the family of unimodal, s-sensitive reward functions. For any 2 2, there exist m, A with Reg(UUm,,A F(l) = O 3x-1
2011
We complement the above upper bound with matching lower bound for every $ 2 2.
Theorem (Lower Bound for s-Sensitive Family). For any 2 2, there is family J of s-sensitive unimodal revenue functions such that any markdown policy π satisfies Reg(T, = (2(TTH))
Remark 4, As final remark, we point out that all our results assume d is given. If instead the learner only has knows an upper bound dmax on d, then she can simply choose the policy for dmax- We leave it open whether best-of-all-worldd algorithm exists.

---

References
[1] R. Agrawal. The continuum-amme bandit problem. SIAM journal on control and optimization. 33(6):1926-1951 1951, 1995.
[2] J. Broder and P. Rusmevichientong. Dynamic pricing under general parametric choice model. Operations Research, 60(4):965-980, 2012.
[3] N. Chen. Multi-armed bandit requiring monotone arm sequences. Advances in Neural Informa- tion Processing Systems, 34, 2021.
[4] W. Cheung. D. Simchi-Levi, and H. Wang. Dynamic pricing and demand learning with limited price experimentation. Operations Research, 6526)1172-1173,, 2017.
[5] U. M. Dholakia. The risks of changing your prices too often. Harvard Business Review, 2015.
[6] A. Garivier, P. Ménard, L. Rossi, and P. Menard. Thresholding bandit for dose-ranging: The impact of monotonicity. arXiv preprint arXiv: /7 1.04454, 2017.
[7] W. Gautschi. On the inverses of vandermonde and confluent vandermonde matrices. i, ii. Numer. Math, 4:117-123, 1962.
[8] S. Gupta and V. Kamble. Individual fairness in hindsight. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 805-806 2019.
[9] S. Jia, A. Li, and R. Ravi. Markdown pricing under unknown demand. Available SSRN 3861379, 2021.
[10] R. Kleinberg and T. Leighton. The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In 44th Annual IEEE Symposium Foundations of Computer Science, 2003. Proceedings., pages 594-605. IEEE, 2003.
[11] R. D. Kleinberg, Nearly tight bounds for the continuum- aarrnuuu--rmmed bandit problem. In Advances in Neural Information Processing Systems, pages 697-704, 2005.
[12] L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
[13] M. Luca and O. Reshef. The effect of price firm reputation. Management Science, 2021.
[14] G. Perakis and D. Singhvi. Dynamic pricing with unknown non-parametric demand and limited price changes. Available at SSRN 3336949, 2019.
[15] J. Salemm S. Gupta, and V. Kamble. Taming wild price fluctuations: Monotone stochastic convex optimization with bandit feedback. arXiv preprint arXiv:2103.0m 092877, 2021.
[16] D. Simchi-Levi and Y. Xu. Phase transitions and cyclic phenomena in bandits with switching constraints. Advances in Neural Information Processing Systems, 32, 2019.
[17] R. Vershynin. High-dimenssioal probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018
[18] A. Wald and J. Wolfowitz. Optimum character of the sequential probability ratio test. The Annals of Mathematical Statisties, 1963)322-333, 1948.
10


Reviews:
[{"review_id": "zAhcDBNLNgZ", "reviewer": "Reviewer_ZoQT", "summary": "This paper studies the dynamic (monopolistic) pricing problem under “markdown constraints” which requires pricing decisions to be nonincreasing. The decision maker does not know the form of the demand function that stays constant over time, receives bandit feedback for decisions made, and aims to minimize cumulative regret compared to the maximum achievable revenue under the optimal price. The paper first proposes a categorization for demand functions called markdown dimensionality to describe the complexity of demand functions in the context of markdown pricing. Then, the paper presents dynamic pricing algorithms for each category, respectively, as well as matching regret lower bounds demonstrating the proposed algorithms are tight. ", "questions": "The two key characteristics for demand functions in this paper are the markdown dimension and sensitivity. However, I noticed that there is no discussion on how these parameters collectively affect regret. For example, in Theorem 1 and 2, is there any intuition behind why there is a discontinuous “jump” in regret for $s=2$ for 0 markdown dimension, but for finite markdown dimension such a “jump” disappears?\n\nIn Algorithm 2 and Theorem 3, how should the decision maker choose $h$ and the phase lengths $T_1 ….T_m$?\n", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\nThe paper is well-written, and to the best of my knowledge, the key contributions regarding 1. defining markdown dimensions; 2. developing algorithms to achieve near optimal regret for each markdown dimension regime (i.e. 0, finite, and infinite markdown dimensions); and 3. presenting regret lower bounds for each regime, are novel. In my opinion, the paper presents a valuable framework to characterize the hardness of learning and dynamic monopolistic pricing under monotone constraints, and may lead to interesting research directions. I also think the paper positions itself well compared to existing papers for non-constrained dynamic pricing, as well as existing work on dynamic pricing with markdown constraints. The paper also presented a clear illustration for technical definitions such as the markdown dimension via concrete examples, and also for the proposed algorithms.\n\nWeakness: \nIn my opinion, the main weakness of the paper is that individual algorithms are presented for different demand markdown-dimension regimes, meaning that the decision maker would need to know whether the supposedly unknown demand function’s markdown dimension is 0, finite or infinite, in order for a decision maker to deploy the corresponding algorithm. Also, in the finite, non-zero markdown dimension regime, the proposed Algorithm 2 requires the decision maker to know the underlying markdown dimension of demand. The paper would be much stronger if it can either propose a single “best of all worlds” algorithm that can achieve optimal regret under demands with any markdown dimensions while being agnostic to the regime, or analyze how the algorithms proposed in the papers would perform if the regime is misspecified. This suggestion may be beyond the scope of the paper, but perhaps it would be helpful to run some simulations to shed light on relevant aspects.\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": "_6DO6wi-Jb2", "reviewer": "Reviewer_Vvni", "summary": "The paper deals with learning pricing with markdown constraints, that is that subsequent prices must be non decreasing. The authors investigate this problem in the case where the demand is a parametric function of the price, with known form but unknown values of the parameters - in this case, a tradeoff must be found between exploring to accurately learn the parameters of the model and losing a lot due to exploration (and the markdown constraint).\n\n The main contributions of the paper are (i) the introduction of \"markdown dimension\", which quantifies the how difficult it is to learn the parameters of the model from data (ii) an algorithm that balances exploration with good performance (under the concept of pessimism in the face of uncertainty) and \n(iii) an algorithm that matches the regret lower bound when the markdown dimension of the problem is infinity (in which case no algorithms with sublinear regret exist).\n", "questions": "1. Related to the weaknesses above - please illustrate, with some concrete examples, why the setting is relevant. \n2. It would be nice to provide numerical results with real datasets illustrating the performance of the proposed algorithms by fitting/assuming different kinds of models for the data. ", "limitations": "No potential negative societal impact foreseen. ", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. The analysis is nice and rigorous. \n2. From a mathematical point of view, introduction of the markdown dimension to characterize the difficulty of the problem is an intersting idea. \n3. Also, the result that knowledge of the demand model can lead to improvements in the regret (and the algorithms to achieve this) can be a good addition to the related literature of pricing with markdown constraints. \n\nWeaknesses \n1. The main weakness is that th setting is not convincingly motivated:  Since the markdown constraint is motivated by pricing problems in markets of some sort, I am not sure it is reasonable to assume that the form of demand (essentially how the market will react to the price) is known. There is no concrete example where a parametric form of the demand model is reasonable/accurate and no  numerical results to illustrate the performance of the proposed algorithms vs standard algorithms in practical problem settings. ", "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": "GlxLVp_tHZP", "reviewer": "Reviewer_ZpZo", "summary": "This work studies a single-product pricing problem under a monotonic/markdown price constraint. In this work, the authors introduce a \"markdown dimension\" $d$ that indicates the hardness of a demand curve to be learnd from customers' feedback. For each of the following cases: $d=0$, $d\\in\\mathbb{Z}^+$, $d=\\infty$, the authors propose a pricing algorithm with provable expected regret guarantees. Specifically, these bounds are optimal for $s=2$ as the authors also prove matching lower bounds. In conclusion, this work improves existing results in related literatures and introduce a new method of determining the hardness of a pricing problem.", "questions": "1, By the end of the first paragraph of Section 2: What do you mean by \"almost surely\"? As T is finite, an \"almost surely\" constraint means no violations at all, right?\n\n2, In the second paragraph of Section 2: It is better to define a policy $\\pi$ formally, as it is time-and-history dependent.\n\n3, Assumption 1: Why the optimal price can be assumed to be an interior point instead of on the boundary, without loss of generality?\n\n4, The first equation on the top of Page 4: With only differentiable assumption, there does not necessarily exist such a second-order derivatives. Notice that a twice-differentiable assumption is in Assumption 4. Therefore, I suggest the authors to state Assumption 1 more clearly.\n\n5, One line before Assumption 5: I suggest the authors to formally define the $p^*$ function in formulas.\n\n6, Assumption 5: $p^*$ is a function mapping the parameter of D to the optimal price of D. On the one hand, the property of $p^*$ is dependent on that of $D$, especially on how a $\\theta$ determines a $D(p; \\theta)$. Also, $p^*$ is not an explicit function under most circumstance, but $D$ is obviously more tractible. So I think it is not a proper way to make assumptions on $p^*$ directly.\n\n7, Proposition 4: Is this easy to be proved?\n\n8, The last paragraph on Page 6: What is $C_s$? (I guess it is the s-th coefficient of the $p^s$ term of R's polynomial approximation, but not sure if I am right.) Besides, this inequality is not always true as you neglect the Lagrangian remainders.\n\n9, The first line on Page 7: It is NOT what [10] have stated. Their definition on $\\alpha$ (albeit the $s$ here) is a Lipschitz exponent instead of a sensitive parameter. In other words, they aim at upper bound the difference while sensitivity is a lower bound of difference. This might be caused by a mistake in stating Definition 10 (i.e., $-C_6$ serves as a lower bound instead of an upper bound), but I got really confused about its name \"sensitivity\". Intuitively, a larger sensitivity would cause a larger fluctuation on reward (or demand) while changing the price, but a larger $s$ would definitely \"smoothen\" the demand curve and reduce the fluctuation caused by price changing. I am very curious why the authors did not call it a \"smoothness\"? Maybe there exist some causes in depth, and I am also not sure if this would affect the soundness.\n\n**10, Algorithm 1 Line 11: How to ensure $p_{j+1} \\leq p_j$ as $\\hat{\\theta}_j$ is a random variable?\n\n11, In Theorem 3: It might be better to rewrite the expression for $s=2$ and $s>2$, which would make both of them concise and informative.\n\n12, A few typos I have noticed:\n\n    (1) Section 1.1 line 7: \"a efficient\" --> \"an efficient\"\n    (2) Page 3 line 6: \"For for\" --> \"For\"\n    (3) Page 4 line 6 from bottom: \"In words\" --> \"In other words\"\n    ......\n\nI recommend the authors to carefully proofread the paper and fix all typos and syntax errors.", "limitations": "No discussions found in this paper. I recommend the authors to discuss the limitations of their work at the end of the main pages. There seems no negative social impact or ethic issue, and I also encourage the authors to discuss them in their Appendix.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1, The problem setting and constraints are practical: customers are indeed more sensitive to price raising than discounting.\n\n2, The new concept on \"markdown dimensionality\" is new in the field of pricing research. Also, it helps determine the hardness of pricing problems.\n\n3, Most of the regret upper bounds of the algorithms this paper proposes are proved to be optimal (up to log or loglog factors) by the authors.\n\n\nWeaknesses:\n\n1, The writing and organization of this paper is not good. In specific, there are many obvious typos and syntax errors even in the most important definitions. For instance, see Definition 10: I really suspect that the authors made a mistake in this definition, especially (c): all their applications of this definition point at a smoothness, i.e., $\\exists C>0$ such that $-C\\leq R^{(s)}(\\cdot)<0$.\n\nBased on this definition, a sensitivity can only be used to lower bound the price perturbation instead of upper-bounding it. E.g., for s=2, it is somewhat a strong convexity.\n\n2, Many key definitions and statements are ambiguous or misleading. For example, in Definition 8: Is there a definition of parameterization? and How does $\\theta$ relate to the following conditions in (2)? Notice that $\\Phi^{-1}_P(y)$ is not necessary a constant unless F is d-identifiable. Also, what does \"it\" in (1) refer to?\n\n3, For key definitions, propositions and assumptions, there are lack of explanations or insights that help the readers to understand. For example, in Definition 2: I had spent a long time until I realized that $p^*$ is the lowest best price and $p^* (R)$ is an argmax oracle. In contrast, there are redundant explanations on trivial facts. For example, the matrix-form equation under Assmption 5 is not necessary and it can be clearly described just by two equations $D = \\sum_{j=0}^d\\theta_j p^j$ and $\\theta = V_p^{-1}y$.\n\n4, The authors did not show the \"markdown dimension\" of a variety of common distributions except for the $0$-dimensional ones. In other words, there exists no example on $d\\geq1$ and $d=\\infty$, which qualifies the application of most of their theoretical results.\n\n5, This is very important to get the authors' notice:\n\n    Notice that the authors added more contents in their main pages in the supplementary materials. This is unfair to the other authors and their submissions as this actually breaks the 9-page-limit rule (although it is in the supplementary materials). The authors should separate their main pages with the proof details of upper and lower bounds and put them into an Appendix. Besides, the format of this paper seems like a \"preprint\" instead of a \"submission\" as an option in the Latex template.\n\n\n\nFrom my point of view, this paper has strong technical contributions, but the authors convey these contributions in a careless way. Not sure if it is suitable for publishing in Neurips. I'll tentatively give a 6 in advocate of their theoretical results and see what the other reviewers would say.\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": "ALW541opEUt", "reviewer": "Reviewer_CjUD", "summary": "The paper considers the monotone (markdown) price constraint in the dynamic pricing problem, where the demand has a parametric form in price.\n\nThe paper introduces a concept, the markdown dimension $d$, which measures the complexity of the parametric family.\nWhen the dimension $d=0, 1 \\le d < \\infty, d= \\infty$, the paper proposes algorithms achieving the regret $O(\\log^2 T), O(T^{d/(d+1)}), O(T^{(2s+1)/(3s+1)})$. Here, $s$ measures the degree of smoothness of revenue function at the optimal price. Also, the matching lower bounds are provided for each case.\n", "questions": "The major question is about Algorithm 1 (on page 7). Is there any step in Algorithm 1 to make sure the prices $p_j$ are decreasing? More precisely, in phase $j$ the parameter $\\theta_j$ is estimated, and the estimation may be inaccurate with a probability. The conservative price $p_{j+1}$ (line 11) obtained by the inaccurate estimation may be larger than $p_j$. After checking the algorithm and proof, I have not found any steps to prevent this.\n\nThe regret for the parametric case when $d=\\infty$, does not match the regret O(T^{3/4}) for the nonparametric unimodal case. So after imposing the parametric assumption (when $d>3$), the regret may be worse. Yet it is shown that it matches the lower bound. Does it make the definition of $d$ unnatural?\n\nAlso, I have not found the proof for Proposition 1,2,3,4 in the paper or appendix.\n\nSome typos: in Proposition 3, $b$ should be $a$. In the 2nd line of Theorem 3, there’s two \"policy\".  \n", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: It’s interesting to consider the monotonicity constraint in the parametric function. The paper shows some new results which are different from the nonparametric case. However, I find the definition of markdown dimension $d$ a little unintuitive, and it is hard to see if the concept can be applied to other applications.\n\nQuality: It’s technically sound, except for Algorithm 1 and Theorem 1. See Questions. \n\nClarity: The paper is written clearly.\n\nThere are three main results in the paper.\n\nFirst, for the simple case when the dimension $d=0$, the paper shows the minimax regret bound $O(\\log^2 T)$ which is different from the unconstraint pricing case $O(\\log T)$. The result is not surprising but still adds to the literature. In this case, there’s a one-to-one mapping from the parameter to the realized demand. Every price is informative and there’s no trade-off between learning and earning. My major concern is whether the prices in the algorithm are actually decreasing. See Questions for details.\n\nSecond, when $d >=1$, the paper shows the minimax regret bound $O(T^{d/(d+1)})$ which are new results. I think that’s the major contribution of the paper. The learning and earning tradeoff shows up in the hyperparameter $h$, i.e., the smallest magnitude that the price decreases between consecutive periods. Setting $h=O(T^{-1/(d+1)})$, the regret will be $O(T^{d/(d+1)})$. My question is how to connect the parametric result with the existing nonparametric result. See Questions for details.\n\nThird, when the function is nonparametric, the paper assumes a higher order of smoothness and proposes an algorithm (Algorithm 3). I think the contribution of this part is marginal because the generalization from Lipschitz continuous to higher-order smoothness is explored by the literature. \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": "9FuFrDRFbL", "reviewer": "Reviewer_wcPP", "summary": "This paper considers infinite-arm MAB with markdown constraints. Since existing results have shown that $T^{3/4}$ is optimal under minimal assumptions, the authors turn to study how to further improve the regret bound by assuming additional assumptions for the demand functions. To this end, they introduce a general complexity notion called *markdown dimension*. Using this notion, they not only show that a better regret bound is possible under certain complexities, but there still exists a separation between MAB with constraints and without markdown constraints. ", "questions": "Several improvements are possible based on the current status of this paper.\n- It might need more intuitions or explanations when introducing the new notion *markdown dimension*. In fact, the reviewer thinks that it would be much better to first consider some special cases and then introduce the general notion based on the intuitions from the special cases. This will help readers appreciate the contributions. \n- The current version does not contain any experiments. The reviewer thinks that this is even more necessary for this paper since the goal is to show some improvement under each particular function class. Thus, it would be good to see improvements from experiments, at least some simple numerical experiments.\n- Some possible typos: (1) the first line on Page 2, extra 'this bound'? (2) Proposition 3, b should be a?", "limitations": "Yes.  The authors adequately addressed the limitations", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- A comprehensive study of MAB with markdown constraints\n- Matching upper and lower bounds\n\n**Weaknesses**\n- No experimental results\n- Writing needs improvement", "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