Dynamic Pricing in the Linear Valuation Model using Shape Constraints
Authors: Daniele Bracale
Moulinath Banerjee
Yuekai Sun
Salam Turki
Kevin Stoll
Venue: Accepted by TMLR ()

Abstract: We propose a shape-constrained approach to dynamic pricing for censored data in the linear valuation model eliminating the need for tuning parameters commonly required by existing methods. Previous works have addressed the challenge of unknown market noise distribution $F_0$ using strategies ranging from kernel methods to reinforcement learning algorithms, such as bandit techniques and upper confidence bounds (UCB), under the assumption that $F_0$ satisfies Lipschitz (or stronger) conditions. In contrast, our method relies on isotonic regression under the weaker assumption that $F_0$ is $\alpha$-H\"older continuous for some $\alpha \in (0,1]$, for which we derive a regret upper bound. Simulations and experiments with real-world data obtained by Welltower Inc (a major healthcare Real Estate Investment Trust) consistently demonstrate that our method attains lower empirical regret in comparison to several existing methods in the literature while offering the advantage of being tuning-parameter free.

Published in Transactions on Machine Learning Research (04/2025)
Dynamic Pricing in the Linear Valuation Model using Shape Constraints
Daniele Bracale*
dbracale edu
Deportment of Statistics University of Michigan
Moulinath Banerjec
moulibCuuiickk edu
Department of Statistics University of Michigan
Yuekai Sun
yuckal@umich. edu
Department of Statistics University of Michigan
Kevin Stoll Welltower Inc.
kstoll@welltoouer.comm
Salam Turki Welltower Inc.
STurk@@eeltowerrcom
Reviewed on OpenReview: https: // openreevee.. net/ permff id- uKZOR4IQa0
Abstract
We propose a shape-constrained approach to dynamic pricing for censored data in the linear valuation model eliminating the need for tuning parameters commonly required by existing methods. Previous works have addressed the challenge of unknown market noise distribution Fo using stralegies ranging from kernel methods reinforcement learning algorithms, such as bandit techniques and upper confidence bounds (UCB), under the assumption that Fo satisfies Lipschitz (or stronger) conditions. In contrast, our method relies on isotonic regression under the weaker assumption that Fu is a-Hölder continuous for some a E (0, 1], for which we derive regret upper bound. Simulations and experiments with real-world data obtained by Welltower Inc (a major healthcare Real Estate Investment Trust) consistently demonstrate that our method attains lower empirical regret in comparison to several existing methods in the literature while offering the advantage of being tuning-paren parameter free.
1 Introduction
Dynamic pricing is the process of continuously adjusting product prices in response to customer feedback based on statistical learning and policy optimization. As a fundamental aspect of revenue management, dynamic pricing has been widely applied across various industries. key challenge in this area balancing the need to explore customer demand with exploiting current knowledge to set optimal prices that maximize revenue. This tradeoff between exploration and exploitation has been extensively studied in fields such statistics, machine lcarning, cconomics, and operations rescarch Besbes & Zeevi (2009); Keskin & Zeevi (2014); Cheung et al. (2017); Cesa-Bianchi el. al. (2019); den Boer & Keskin (2020). A large literalure focuses on an important dynamic pricing problem where contextual information, such as product features and market conditions, is available at each time step. By leveraging this contextual data, we aim to refine pricing strategics and improve revenue outcomes. This approach, known as feature-base or contextual
*Corresponding author

---

Published in Transactions on Machine Learning Research (04/2025)
pricing, allows for more customized pricing decisions that better reflect product heterogeneity, leading to more effective revenue management in today's ' data-rich environment.
This paper focuses on the problem of pricing a single product over a finite time horizon T, where the market value 24 of the product is unknown to the seller and may vary over time t= 1,2,..., T. The market value is modeled as a linear function of observed features (covariates) of the product
1/- = 0g x2 + =e:
(1)
where 2, E Rd contains 1 in the first component to consider for the intercept, dg is some unknown parameter and Dy are independent of the noise 2t that are i.i.d with unknown cumulative distribution function (c.d.f.) Fo- After the seller proposes a price Pt - (<x),, they observe whether the item is sold or not, i.e. y/: = 1(p, S vr) and collect revenue Prys- The seller aims to design a policy that maximizes the total revenue Σt=1 Petk. given the uncertainty in the market value and the limited information available to the seller, that (pe. 24, ye). The determination of the optimal revenue entails learning the model parameters (0,, Fo) for which various statistical tools have been employed such kernel-based methods, bandit technique, and UCB (Fan et al., 2021; Luo et al., 2022; 2024; Xu & Wang, 2022; Tullii et al., 2024).
Building on the remi-parametrie structure of the model and recent advances in shape-constrained statistics, we propose a novel policy that requires minimal assumptions about the underlying distribution of market. noise. Specifically, we estimate 0g using ordinary least squares (OLS) and Fo using con-parametric least squares (NPLS), subject to the natural constraint that Fo is non-decreasing.
A key advantage of our shape-constrained approach is that it is entirely data-driven and does not require the specification of any tuning parameters, unlike existing non-parametric methods. For example, the kernel-based technique proposed by Fan et al. (2021) requires bandwidth selection for optimizing the error of the est In contrast, the UCB-based strategy of Luo et al. (2022) requires a set of subjective parameters including a tuning parameter.
Contribution.
Our main contributions are:
(1) We propose new tuming parameter-free method, unlike existing non-parametric methods for estimating the market noise distribution Fo, leveraging the shape constraint that Fo is non-decreasing and assuming only that Fo is a-Hölder continuous for some E (0, 1].
(2) We derive an upper bound on the total expected regret of order )(Tv(a) "), where v: :0, - IR,
v(a)
2 1fa E (0,1/2)) + 20 1a [1/ 2ta
and δ excludes log factors (under Lipshitzianity of Fo, this rates becomes O(d//319/4)) and we provide a thorough assessment of its empirical performance with comparisons to cxisting algorithms through a number of simulations, as well as an emulation experiment based on real data. Our algorithm shows strong empirical performance:
particular, dominates the algorithm proposed by Tullii al. (2024) in their simulation setting up to very large time horizons. Additionally, our algorithm when applied to real data set obtained by Welltower Inc continues to demonstrate stronger performance than Tullii et al. (2024); Luo et al. (2022) and is competitive with the nonparametric method proposed by Fan et al. (2021), though the latter relies on stronger smoothness assumptions.
(3) Beyond the application of antitonic regression, our work involves establishing concentration inequality for the uniform norm of the antitonic regression estimator error, which is required to derive the expected regret upper bound. Although the existing literature on isotonic regression explores the rate of convergence of the uniform error, explicit tail probability bounds (stronger than Op statements) of the type presented in this work (see Theorem 4.8) appear to be missing.
1.1 Related Works
The linear valuation model for contextual dynamic pricing, as defined in Equation (1), has been extensively studied under various assumptions. Recent works have explored statistical models both linear and their
2

---

Published in Transactions on Machine Learning Research (04/2025)
Table 1: Comparison of customer valuation model- based contextual dynamic pricing algorithms with stochastic contexts under the same assumptions on fg and similar smoothness assumptions on Fo- Notes: (S): v(a) is defined in Equation (2).
METHOD
REGRET UPPER BOUND
HÖLDER CONTINUITY
LIPSCHITZ CONTINUITY
2ND ORDER SMOOTHNESS
O(dd)) 2mve11
FAN ET AL. (2021)
X
LUO ET AL. (2022)
O(T4/a))
X
V
X
TULLI ET AL. (2024)
((dT))2/))
V
X
THIS WORK
V V
X
extensions- for the pricing problem, assuming that Fo (the noise distribution) is either known, partially known' (Miao et al., 2019; Ban & Keskin, 2021; Javanmard & Nazerzadeh, 2019; Golrezaci et al., 2019), or fully unknown (Fan et al., 2021; Xu & Wang, 2022; Luo et al., 2022). For comprehensive overviews of dynamic pricing from a broader perspective, we refer readers to Den Boer (2015) and Kumar et al. (2018).
We focus on the results most relevant to our work work-specfficallyy the case where both the parameter 8g and the distribution Fo are fully unknown. In this setting, Fan et al. (2021) estimate Fo using kernel methods and derive a regret upper bound of ((dT) 2m++1 Tm-T), ), where m 2 denotes the degree of smoothness of Fo. In the realm of reinforcement learning, Luo et al. (2022) introduces the Explore-Uhen-UGE strategy, which balances revenue maximization, estimation of the linear valuation parameter, and nonparametric learning of the noise distribution. Under Lipschitz contimuity on Fo, their approach achieves a regret rate of OddT3/1), )), and under (an addilional) second-order smoothness assumption, regret of ((PTe/s)) However, their regret bounds depend on a regularization parameter X > O, which is hard to tune dynamically, and the impact of the choice of A on the regret is not clearly described. Xu & Wang (2022) propose the D2-EXP4 algorithm, which is based on discretizing both the parameter space 0g and Fg. With appropriate choices of the discrelization parameters, they establish a regret upper bound of O(T3/1 + VdT2/3). However, as noted in Xu Wang (2022, Section 6), they were unable to perform numerical experiments on D2-EXP4 due to the exponential time complexity of the EXP4 learner with a policy set of size 2T making their algorithm impractical for application. Furthermore, Assumption of their paper requires their x, and Og to have non-negative entries. While they claim that this assumption entails no loss of generality, this assumption is heavily used in the proofs of Theorem and Theorem 5 of their work, and it is far from clear whether their derivations are generalizable to the situation when such sign constraints are not imposed. While the positivity of covariates can be ensured under boundedness by adding constants and adjusting the intercept parameter, the assumption that all covariates have positive impact on the valuation is quite unrealistic for any regression model.
In contrast to Fan et al. (2021); Luo et al. (2022); Xu & Wang (2022), we propose a tuning paramoter- free policy that achieves regret upper bound of order O(T3/181/3 when = 1 (i.e. Fo is Lipschiuz). Furthermore, estimating the parameters 6g and Fo is computationally efficient: 6n is estimated using ordinary least squares (OLS), and Fo is estimated via isotonic regression 2 using the Pool Adjacontt Violators Algorithm (PAVA) introduced by Robertson et al. (1988), which, in our problem, has a computational complexity of (dd)ttoru()) (see Section 3.1).
Very recent work by Tullii et al. (2024) provides UCB-LCI LCB-based algorithm named VAPE (Valuation Approximation-Price Price Elimination). The main idea is to update the estimate of Gg at time t when 2, is far from previously observed covariate values; otherwisc, update the UCB-LCB around Fo and deploy the optimal price. They prove that their regret is upper bounded by (((d7)2/3) under Lipschitz assumption on Fo (i.e. a = 1), which attains the lower bound in T, 2(T2/3) established in Xu & Wang (2022). We summarize the regret upper bounds and the underlying assumptions in Table
Meaning is unknown but helongs parameterized family. 2 Alternatively, estimating Sg = Fo using antitonic regression.
3

---

Published in Transactions on Machine Learning Research (04/2025)
1.2 Notation
For an interval / T= b), a, b we use | b a. For any given matrix E E Rdixd, we write E > 0 or Σ < if or - is semi-dcfinite. For any event A, we let [(A) be an indicator random variable which is equal to 1 if A is true and otherwise. For
positive sequences {an)n21 (bm)n21) we write On 0 (b,) an < by if there exists positive constant C' such that an I Cbn. We denote X, Op(a,) if there exists 17 > 0 and no such that P(X, I (n) 2 1 1-1-1/1 1/n" for 2 no. In addition, we write an = Q (b,) or an 2 b, if an/bn 2 c with some constant 0. Moreover, we let (+), represent the same meaning with O(), except for ignoring log factors. For a random variable
will denote by fz, and Pa its corresponding density function and probability measure, respectively. For a c.d.f. F we will use S to denote 1 1 F. Given a function h(r,8) we write E, [h(1, y)] ff h(r, y)dPP We say that function S is a-Hölder (continuous) for some constant a E (0, 1] if (S()) - S(v) & L|u ofa for all e in it's domain.
2 Problem Setting
We consider the pricing problem where seller has single product for sale at each time period t = 1,2, ... .. Here T is the total number of periods (i.e. length of the horizon) and may be unknown to the seller. The market value of the product at time t is denoted by i and is unknown to the seller. At each period t, the seller posts a price Pt. E [Pminn Pmax] for S Pmin < Pmax < xc. Pt S Ut, a sale occurs, and the seller collects a revenue of Pt. Otherwise, no sale occurs and no revenue is obtained. Let yt be the response variable that indicates whether sale has occurred at period t:
y/- 1 11 pt):
and let Pttt the collected revenue at time t. We model the market value Ur as a linear function of the product's observable i.idd features Ia E X' C Rdd
U1 = 0g x4 21:
(3)
where 0o E Rd is unknown parameter (which includes the intercept term), and ,, are i.dd sequence of idiosyncratic noise drawn from an unknown distribution Fo with mean O and bounded support
u A (inf 2 E R Fo(z) supfz R Fo(2) < 1)).
(4)
We assumee that the first entry in x, equals to account for the intercept term in 0g. The overall procedure is summarized in Bax 1. The expected revenue for any offered price p given ot is
relp) Ez, (pl (wz > p} (x) = pPz. (vx > xx) = pSo(p - Oz),), st), So = 1 Fo-
Note that, since So is survival function, it is non-increasing. The optimal price pt at time i is defined by maximizer of the expected revenue function at the round,
pf E argmax pelp Pmaae] pSo (p 0g sr))
(5)
Note that P = Pt (x+), depends on Zt. The regret at step is defined by the difference between the expected revenues from the optimal price pi and the offered price p:: ((pt))r(ppt)) In other words, we consider the problem of maximizing revenue minimizing the following maximum regret
R(T) A ET pfllpt S v.) p.1 s vz3
where the expectation is taken with respect to the idiosyncratic noise 21, the covariates Fe, and the offered prices Pt that depend the specific policy.
4

---

Published in Transactions on Machine Learning Research (04/2025)
Box 1: Contextual Pricing Dynamic
For each sales round T:
(1) The seller observes a context vector 22 E R..
(2) The seller offers price Pt based on 2, and the previous sales records {(z,,Pr Pro yr )
(3) Simultaneously, the customer evaluates the product at ut, which is not known to the seller.
(4) The seller observes y: = 1(4 2 pt), indicating whether the product was sold.
As the firm's goal is to design a policy that sets prices ps as close as possible to the optimal prices pz defined in Equation (5), we first estimate So) and then we plug the estimate as in Equation (6) to get an estimated optimal price pt- Accurate estimation of (0o, So) thereby ensures that the resulting policy incurs low regret.
3 Proposed Algorithm
We employ an spoch-based design (also known as the doubling trick) that segments the given horizon T into several clusters of rounds, called epochs or episodes, and exccutes identical pricing policies on a per-epoch basis. Let J1 = 10.1...., T1 - 1} be the first episode, where T₁ is a prefixed constant. For k = .,..., K = [log (T/n) + 11, define Th = Ti 2 and Ts = (TH -1,--.,..... -I....: - T1 - 1} the of times in the k-th episode.
We partition Ts into two sub-phases, T. Es E where Eg represents the exploration phase, dedicated to collecting data for estimating the parameters (fo, So), while E/ denotes the exploitation phase, during which apply the optimal prices based on the estimated parameters (0x, Sy). The length of the exploration phase, E is set to [d p(a),, chosen to minimize the expected regret R(T). Specifically, as we show in the proof of Theorem 4.10, if [E = d= for some E, E (0, 1), then R(T) is minimized if & and n satisfy the condition d'r = [d"/atn pla)), Eg is further divided into two equal-sized intervals I& and Ig. In Iş we collect data to estimate 0g. In la we collect data to estimate So. The details are stated in Algorithm 1, and a picture of a general episode Ts is shown in Figure 1. In the following portion of this section, we examine the for a fixed episode
Tk
details of eeploratiionexploiiii
Estimation of 8g. For all Is the seller observe It, deploy pt unif(pmiu: Pmux) and observes y 1 [p S v... Let H Pmax Pmin and estimate
0g OLS((I,, Hy) hel. arg ming Ttl Ener, (Hy 00 0xxz)².
Estimation of Sp. For t E Ig, the seller observe Iı, sample wi ~ ulif( propose a price pt = + 0
and observes y/ = 1 (p: S v. Estimate
S. = Antitonic( (olloonic(((,,11]) ()) = arg minses Eieñ (v+ - S(w:))²
where S is the set of non-increasing function in R.
Exploitation. For every t Ey,, observe Fe, set
Pr E argmax p(/ameaal (p xx).
(6)
and get reward (p, S $.).
3.1 Complexity of the antitonic regression
The algorithmic complexity for estimating So is ((P/a))Tu(a)) Indeed by Grotzinger & Witzgall (1984); Tibshirani et al. (2011) the computational complexity for the antitonic estimator is Onn), where n is the sample size. In our case, the estimation of So happens in (half of) the exploration phase which has length proportional to d/21 v(a) d2221 then, using that K logz(T), we have x d / TTv(a)
5

---

Published in Transactions on Machine Learning Research (04/2025)
Algorithm Semi-Parametric Pricing
Input: Time horizon T and length of the first epoch, the Hölder exponent a of So and the corresponding v(a) defined in Equation (2); the minimum and maximum of price search range, Pmin and Pmax: H = Pmax Pmuin U defined in Equation (4).
Set K [log (T/T)) + 17.
for epoch & 1.2......f. KK do
Tk 7,2k-1 length of episode k
a f- [d v(a)
/2]. length of exploration phase
J (Tk -T,,.... Th 7I + 02 - 1}
L. + {Tk -TI + ax..... Th 7i + 2a -0 1}
Fg <- T indexes of the exploration phase
Ex + [Tk
+ 2a....., Tk+1 - 1} indexes of the exploitation phase.
for t I do
Observe 2t
Sct Pt unif(pmin )_aa)) Get yt 1 {pt S vt)
end for O2 OLS((Er, Hyb IEE
for e I& do
Observe Sample wt unif(()) Set pt w1 0, Get l/+ (pr S v end for
3g - (w,, Beh
for E Fig do
Observe zt
Set price pt as defined in Equation (6).
Get ys + 1p: S v1}
end for end for
Estimate 0z
Estimate 8,
Deploy E argmax ps - 07x))
Eg
E
1
1j + 4
7g
1j
+ 24z
[x+] - -1
Figure 1: Picture of general episode Jk, 1,2,..., K.
4 Regret Analysis
Before proceeding with the regret analysis we need to discuss the convergence rates of 0. to On and Sx to So- We present our main theorems and proofs. We defer to the Appendix for the missing proofs.
4.1 Estimation of 0g
Assumption 4.1 (Bounded parameter space). The parameter A E Rud an interior point of and the parameter space θ compact convex set.

---

Published in Transactions on Machine Learning Research (04/2025)
Assumption 4.2 (Bounded i..d. contexts). (a) 22 E X C R is iid. drawn a distribution that does not involve On and Fo, and for all E X, ||æell2 I Rx for some unknown Rx > O. (b) There exists reals Cmiu; Cmax 0, s.t. Cmin < E Guaxlld, where E é Exg,, and Ia the d x d identity matrix.
Assumptions 4.1 and 4.2 are standard in the dynamic pricing literature Javanmard & Nazerzadeh (2019); Xu & Wang (2022); Luo et al. (2022); Fan et al. (2021). More precisely, the ii.d. assumption of the context and the prices 1ee. is used in Lemma 4.3 to derive a concentration inequality for the estimation of do-
Lemma 4.3. [Fan et al. (2021, Lemma 4.1)] Let ny - (T&] for simplicity of notation. Under Assumptions 4.1 and 4.2, there exist Co, C1 > 0 depending only on absolute constants given in assumptions, such that for any episode k, as long as nk 2 cud, with probobility at least 1- Quz with Quz - 2e be--rre -ia 24/16 166 2 it holds that
ng
1 - 0oll2 S Coo /dlonma/mi A Ru
(max(Bxx1a (Rx Reg Praux Pusin)
where Co.
Cmin
4.2
Estimation of So via antitonic regression
In this section, provide uniform convergence result of S5 to Sg. For simplicity of notation, we re-index I as T = .I. and we denote 02 by 0, which was estimated using data {(rt, Tt, Mr)) independent of T. In this section, all the results must be considered as conditioned on 0 = 0g. We report in Box 2 a more detailed explanation of the estimation of So during the exploration phase in T as expounded in the box highlighted in Algorithm 1.
Box 2: Sample collection for estimating So For each E T do:
(1) Observe Zt.
(2) The customer samples 2, and evaluate 2, 0 xe + 22, unknown to the firm.
(3) The firm samples W2 ~ uni independent of everything else and defines pt = wi + 0 Fr-
(4) Observe y1 = fp < w.
This produces set of data points {(pe. H1, "1)yt that we are going to use for estimating Sg- To estimate
So we would need to know &n advance, indced remember that Ely, I Pt, 24) = So - 0ī æt), which design points (p:- - 0J weT depend on 0g However, our knowledge is limited lo. and the observable design points are Pt OTx, Wy. This implies that we are only able to estimate Su(u) A B(y, wy u). We then estimate So(.) considering Ye as coming from sample in the ordinary
an approximation of
current status model, where the data has the form (w2,8t) 1i2d (w, y), the observation times have uniform density fw and whore ÿe = 1 with probability So (wx) at observation wt. Remark 4.4 (The choice of the design points wy). The choice of the distribution for w, is motivated by the fact that when the density of design points is uniform, we obtain convergence guarantees for the estimator of So. Specifically, as mentioned by Mösching & Dümbgen (2020), if the density of the design points is bounded away from zero - which holds for the uniform distribution then {w, het are "asymptotically dense" within any interval contained in U (defined in Equation (4)). Ensuring that the design points have a density bounded away from zero a sufficient condition for the convergence result in Thcorem 4.8 (sce Lemma A.2 for further details). However, this choice is not restrictive; any distribution whose density is bounded away from zero in l would still satisfy the convergence result. The only consequence of using non-uniform density is that the regret R(T) will depend on the multiplicative constant C₂ = inf int (u), which may be different from 1/|M| if fw is not the uniform density in U. Furthermore, since each episode Ts is independent of any other episode Tu for & k,, it is possible to select a different density f(()) for each episode k; provided that it remains bounded away from zero in U. An interesting extension of our work would be to adaptively update the design donsity f(() based on the previous design f(k-1) an optimal manner, namely that f(()) converges to the optimal design density as k - oc, that is the density that minimizes the integrated mean square error. This approach, known sequential optimal design, has been extensively studied in the literature (see, e.g.,
7

---

Published in Transactions on Machine Learning Research (04/2025)
Müller (1984); Zhao & Yao (2012); Bracale et al. (2024)). A key advantage of an optimal design algorithm is that it dynamically allocates more data to regions where the estimation of So is less accurate, thereby progressively improving its precision. However, it is important to note that while this adaptive approach can optimize the multiplicative constant in the regret bound, it does not affect the rate the regret itself.
Remark 4.5 (The difference between the conditional distributions of yl(p, and ylw). We want to highlight the difference between the conditional distributions of yp a) and y/w. The first is independent of 0, indeed we have that
E. [ulp x] = ( < 0 x + z>|p x]| = So(p - 0 x),
while, the distribution of y/u w depends on 0 because is generated as in Box 2, have that
{p S tr where p = w + 0T x, and, since data (w, y)
Sa(u) (y w= u) E (p.z) (1. ( p.z)
w ==
[xp))) 0g x) w = =))
(So - + 0 x - 0g x)
w
(S((S + (0 fb) Tx) w u)
-SSo (0 06) T x)) x)dP JdPp//=u (/w=a(r)
= f So(u + (0 - 0o) T (x)))(rr)
(7)
where the first equality is by definition, in the second we use the tower property and in the last equality, we use that we is sampled independently of 24- Note from Equation (7) that So(-) is non-increasing for all 0 because So - Fo, being a survival function, is non-increasing.
Proposition 4.6. So is non non-increasing for every 0 Rd. Moreover, if So is a a-Hölder with a E (0, 1], then So is a-Hölder uniformly in 0 E Rdd and (Sa(u) So()) & 10 0ol2 uniformly in E R.
Proposition 4.6 is crucial because it tells us that we can estimate So under the antitonic constraint and that Sg is close to So as long as 0 is close to fo. which will be used to prove Theorem 4.10. Guided by Proposition 4.6, we estimate Sg using antitonic regression, denoted as
S A argminses EvET(y- S(w)))²
(8)
where S is the set of non-increasing functions in R. The minimizer So is piecewise constant function with jumps at subset of {w, : E T). The order statistics on which S, is based are the order statistics of the values We and the values of the corresponding value of the observed fwe. For j = 1,.... m set
To be more specific, let < u2 < .... < um the different
= #(t we = uj}.
D = 1 -im; =uj Vi.
For every 1 1 < m let
- = -y o,0, rrs P Ej=r 0j = #(t {t: ur S w. I u,t,
It well known that S, = (u1), (o())).... (a may be represented by the following minimax and maximin formulae, see Robertson et al. (1988): for S <
So(1)) = min max Trs = max min Trs- rSj 22
22 rS)
The Sg is also known as the antitonic regression on data ((w,, v)) hET, and we will denote it as
So Antitonncc((we,) ((
We are now prepared demonstrate the convergence of S, to S.. To establish this result, we require that So a-Hölder for some a E (0, 1] uniformly in #. According to Proposition 4.6, this condition is satisfied provided we make the following assumption:
8

---

Published in Transactions on Machine Learning Research (04/2025)
Assumption 4.7. [So(u) So(v)l = Cilu- o/ for some a E (0, 1]. C1 0 and for all U.
Theorem 4.8. Let ((w,, HET be as defined in Box 2 and let Assumption 4.7 hold. Then for every K > 0 and yy > there exists no = no(7; is, ai) E EN and C' = C(C1, [u], 1e, a) > 0 (where U is defined in Equation (4)) such that
So(u)= - So(u)] S Cpp//Batt) 2 / weth.
P
sup
nT-2 n 2 no:
where Ph = log(n)/n and Un = {u E u: : [u + 6nl C U}, with on = Kpn
11(2++1)
Remark 4.9. Our Theorem 4.8 parallels Theorem 3.3 in Mösching & Dümblen (2020), with the key distinction
being the nature of the observed response variable. While Mösching & Dümbben (2020) directly observes the
response variable (which corresponds to our valuation 42), we observe the binary indicator y/+ 1 {pp - 0/ }- This difference simplifies our proof, as it only requires establishing a concentration inequality for 19re Srs (0) where
(0) - o
In our sctting, this concentration incquality can be readily obtained using Hocffding's incquality uniformly
over 0. Specifically, as demonstrated in Lemma A.1, for any constant D > 1, (MM S (D log n)1/23 is at 1/2 2 10rs (o).
least 1 - (x+1/n2)2, where (0) A maxi
4.3 Regret Upper Bound
We are now ready to establish an upper bound on the expected regret for our Algorithm 1. Theorem 4.10. Suppose that Assumptions 4-1, 4.2 and 4.7. For sufficiently large T the cumulative regret of Algorithm 1, R(T)) has upper bound of order
O log 2a (dT)), a (0, (0,1/2), 2a+1 a acT log 2 (dT)),
a E [1/2, 1].
Proof- Sketch. Fix h: 2 2 and define ny = [ and 7U [T and ag [E ne + Let So (p ax) - So Of x) and Sx (p | x)) 2 (p - x). For the exploration phase EE re(pi) - re(())] S Pmnax Ex S Ex
Now fix E En,
re(p)) - (p())) = pl (pi ax)) So (pe ax))
= =pp; (pi) xx)) - Sr (0g me)} } + pr (vt xx)) - pr (pe xx)) {1 (p (De (x)) - Po (Pe mx)
so by Equation (6)
Pmaa So(pī xx) - 3u(pi [x0) + Pmax Sx (pt xx)) - So (pe 1 mx)) = Rnolvi) + (p)),
where Rg) A [a 0% xz) - So (q Og xxe) for g E (pi,Pe): E F2z-
Lemma 4.11. If Assumptions in Theorem 4.10 hold, for k sufficiently large we have E(Ra,((g)) & (ogmss/zz) 0/20-1
+ (dlogma/ne))* for q E (pi.pe with t e Ex.
Let k 2 ko for ko be sufficiently large as in Lemma 4.11. Summing up for all t E E%, and merging with the exploration phase of episode & we get
0/20+1 (mossiffie
E Eier, re(pi) - re(pr)] S EE + |E%
+ (dlogme/ne)
Using that nę = 74 = f = 1 Enl = jol 2 x d22kv for E > to be determined such that they minimize the total regret, and that |F S [Tal = - 1 x 2 we get that the RHS of the last incquality is bounded above by
2 + d 20+1 2 R(1
vo 20+1
IK + log
2 2a++ + d d (1-5)2 22) 2) [o
9

---

Published in Transactions on Machine Learning Research (04/2025)
Here we prove the result for > 1. We defer to Appendix A.3 for the complete proof. Consider the exponents &o of the factor d, i.e. -. 2x+I and g E). As the second exponent is always negative, the regret is minimized with respect to d if we equalize the first and the third exponent, i.e. & = _ {) to get 5* = 6+2 Similarly we equalize the first two factors, to 2a+1 Consequently, the expected regret in episode k, E [Eteo re(pt) - rp()) upper bounded get v' = 3a+1' by
for the exponents of the exponential factor 24, i.e. v, 1 2a+1 and 1
2a+1 a 2 30+1 (do+2 + d (2a+1)(a+2) log(d) 20+1 + d [k log(d))2) x $2
a²
2a+1 30++ d [h: + log(d))
where we used that 204T [log (T/r)) + +1 we get
< 2 for a E (1/2,1). Putting together the phases and using that K
R(T) = E Ek=ko Eier. relpt) re(pi) s $2
3at1 dat2 [K + log(d)] & T3a+1 da+2 log (dT).
20+1
a
2a+1
5
Simulations
We first perform simulations for theoretical validation in Section 5.1 and simulation to compare our algorithm with the minimax algorithm by Tullii et al. (2024) and Fan et al. (2021) algorithm in Section 5.2.
5.1 Simulation for theoretical validation
To this end, we replicate the simulation settings used by Fan et al. (2021). We set U = (-1/2, 1/2) (known), the feature dimension d = 3 (known), the distribution of X, ~ Unif(- v //3) xd (unknown), and the coefficient 0 (an. g0 (unknown), where an = 3, A0 = (2/s, 2/s, 2/3). We also choose Pmiin = and Pmax (known). For Fo U + RR we consider different choices:
(1) a < 1: (z) = 1/2 + (4/2) 1-a sign(=)|æ)* (ign)==ig for U, for = >> 1/2, for a E (1/,, 3/4).
(2) a = 1: we use four choices Fo: a Gaussian (0, truncated at U4 the c.d.f. used by Fan et al. (2021) with density fo(=) = (1 - =²) 1( E U)}, Laplace with location 0 and scale 0.2 truncated U, and a Cauchy with location and scale 0.2 truncated 4.
We start with TI 100 and compute K 8 total episodes. At every time we follow Algorithm I to compute Pt: with the additional computation of the oracle Pf and the corresponding cumulative regret Reg(t)= = Ej=1 So(r; 0g xx)) (p. 0g xz). We repeated the experiment 36 times and we computed the mean and the 95% confidence interval in a log, - log, plot. As illustrated in Figure 2, we validate our approach by comparing the estimated slope of the linear regression of logg(t) versus (Rog(R))))) with the theoretical upper bound rate. Due to space constraints, the plot corresponding to the Fo used by Fan et al. (2021) with density fo(z) = 6 (1 - 2²) 1(2 E u)) provided in Appendix B.
Remark 5.1 (Dependence on TI). Although is generally considered a non-tuning parameter typically set to in dynamic pricing algorithms that use the doubling trick (see, e.g., Javanmard & Nazerzadeh (2019); Javanmard al. (2020; 2024)) we have included an additional simulation in Figure 3 to demonstrate the robustness of our algorithm with respect this parameter.
5.2 Comparison with Tullii et al. (2024) under Lipschitz assumption of Fo
We first recall that the regret upper bound by Tullii al. (2024) is of order (TT2/3) under Lipschitz assumption on Fo (a = 1), which is smaller than our regret upper-bound ((T3/1). For this reason, we perform the following simulations.
In their work, Tullii et al. (2024, Supplemenary Material A) compared their VAPE method the kernel-basod method by Fan et al. (2021) that is: they built. dataset of 5 contexts belonging to R3 generated by
10

---

Published in Transactions on Machine Learning Research (04/2025)
Emprrcal depe 382
Emglical skoc: 0.76
Empir dese 0.75
Thorttial dopz. 085
Thcorskal Josc: 0.0
Therttaal #apz 027
124
(og(Rag(tt)
log (Rg(( (+))
log(Reg(())
.04
93-
05
log(t)
log(t)
log(t)
Emp rial dops 5:14
118
Emrii cal depe: 0.23
Empiical sépz: 0.7
Thamtical 0.25
Themikal dope
Tteominal dosec C.D
124
(og(R)
(og(Fegg(t)
(og(Reg(())
183
47-
65-
log(t)
lag(t)
log(t)
Figure 2: This plot shows the total expected regret (blue line) with Fo.a: for (4/3, 4/2, 3/4] in the first row, and a Gaussian, Laplace, and Cauchy c.d.f. in the second row (from the left to the right). We repeated the simulation 36 times and displayed the corresponding 95% confidence intervals. The plot is in log, loga scale to show the regret rate (empirical slope): a slope of r7 indicated an O (T9) regret. The black dashed line corresponds to our theoretical regret upper bound.
Regret Curves for Different Values
31 (Empirical slope: 0.85)
62 (Empirical slope: 0.85)
124 (Empirical slope: 0.85)
11-
248 (Empirical slope: 0.85)
log(Reg(t))
8-
9
10
11 12
log(? (
Figure 3: This plot in log2 - logg scale shows the cumulative regret over time up to T 4000 for different values of TI E {31, 62, 124, 248} and with Fa,y/ for which theoretical regret rate is 0.86. For each value of Ti, we repeated the simulation 36 times and displayed the corresponding 95% confidence intervals. As we can see, the regret remains similar across different values of 7 and the the empirical slopes are close to the theoretical regret rate.
canonical Gaussian distribution and subsequently normalized. Throughout the run, the contexts are chosen from this set uniformly at random, while the noise term is picked from a Gaussian distribution truncated between -1 and 1 with mean 0 and variance 0.1. Similarly, also the parameter 8g normalized vector initially drawn from Gaussian distribution. Note that for this simulation, the error distribution twice differentiable (i.e. smoother her than what Tullii et al. (2024) and us allow in theory), then the kernel-based
11

---

Published in Transactions on Machine Learning Research (04/2025)
4000
Antitonic Algorithm
Kemel Based Algorithm
3500
Cumulative Regret
Vape Algorithm
1000
2500
1000
500
1000
2000
1000
4000
500n
6000
1000
8000
Time Horizon T
Figure 4: Regret comparison in the simulation setting of Tullii al. (2024).
method by Fan et al. (2021) is applicable with smoothness parameter m = 2. Tullii et al. (2024) showed that the semel-based method has stronger performance.
We apply our antitonic regression-based algorithm with a = 1, using the same code and simulation sctting provided by Tullii et al. (2024, Supplemenary Material A). The algorithm has been tested on time horizons T E [500, 1000, 2000, 4000, 8000]. We computed the regret 36 times and the corresponding 95% confidence interval. In Figure 4 we show the results. Although the kernel-based method by Fan et al. (2021) applies to distributions of the error that are at least twice differentiable which is the case in this simulation their algorithm has weaker performance than ours in this setting. Comparing our antitonic method with the VAPE algorithm by Tullii et al. (2024) (which have the same assumption on Fy, i.e. Lipschitzianity of Fo) the empirical performance of VAPE worse than our method up to very large time horizons (T = 8000), achieving smaller regret.
6 Real Application
This study applies our method to real data set obtained by Welltower Inc to simulate the dynamic pricing process. The dataset consists of various characteristics and the transaction price for units in the United States (see Table 2 for more details). In our experiments, algorithm in a sequential fashion to simulate the dynamic pricing game. The unique aspect of the dataset is it includes the exact transaction price, which allows us to evaluate the regret of the algorithm directly.
present each rental unit to the dynamic pricing
Table 2: Dataset description
Variable
Description
Uy: act rate d
Final transaction price. Typical rate of similar unit in the primary market area. Square footage of unit.
21.1: mkt rate d
2122 sqft
Fr.3
Type of unit (bedroom, studio, other). Median home value of primary market area.
Jr.4 med home
This datasct docsn't contain the variable V/, i.c. whether the sales occurred. Our knowledge is limited to the final transaction prices act act_rraee d. To overcome this we make the following adjustment: each time point 1, we consider the transaction price act. rate d the customer valuation it, which treat unobserved;
12

---

Published in Transactions on Machine Learning Research (04/2025)
10
Empirical CDF of the resjuals
Observed resiclullss
0.4
-12
0.2
0.0
20003
10300
60030
-0000
1002000
Time
Observed residuals
Figure 5: Residuals
Table Ordinary least squares: V/ = TT 23 + 21
Table 3: Summary Statistics
OLS
Adp E-eguaend:
Mudid:
Patataric:
2.152++324
mict Luattne .ate..d
seyit
12nin medll Iamte 200
Simin rteel Jonter rel
art Pare
Reaquaned
Df Resalnals
56652
0.597
Proh (F-stattette):
Stade
11.956
0.30
00.00
01:00
1308115.11
135.00
391300
330035
133/00
5995
0753555.94
0810115.55
181.00
501100:36
601895.52
200.0
75%
683178.86
091712258
251.00
05475.71
1752.00
1690671.96
1025672.51
1491.8
bed
0.1420
tyw
Mr) where y _ 1( 2 pe). Here the vector 2, contains all the variables in Table 2 except act _ett_ate______ d, and the first entry account for the intercept. As we assume vz = 0g xe + 2 for some unknown 0g and unknown c.d.f. Fo of zt; we validate this lincar validation model. To this end, we perform linear model using data (Ia, vy): the p-value of the F statistics is close to 0 and the slopes of all the variables are statistically significant at a significance level of 0.05 (see Table 4). The residuals and the associated empirical distribution function (an estimate of Fo) are depicted in Figure 5, from which we notice that U is approximatively -1,112), Morcover Puii and Punax are the maximum and minimum values of v4.
a price Pt is posted by the firm, which finally collects the data point (1))
Prior implementing the methods, we conducted validavaiiottonn tune the UCB algorithm's parameters À and C2, defined in Luo et al. (2022). We scarched over grid with (X, C2) {0.1, 0.5, 1, 1.5, 2, 5) {5, 10, 15, 20, 30). After selecting the optimal parameters, we ran the algorithm for each method. The initial episode length was set to 7 150, with subsequent episodes doubling in length according to = 2-2,11 for total of K = 4 episodes. Each algorithm then chooses its exploration phase according to its rule. We conducted 36 iterations, randomly shuffling the data before each run. For our algorithm, we set a = 1.
Figure 6 showcases the (empirical) revenue = Prlle, obtained using our antitonic method (blue line), the UCB method by Luo et al. (2022) (green line), the kernel method by Fan et al. (2021) (red line) and the VAPE algorithm by Tullii et al. (2024) (black line). Higher lines indicate better performance. We present three plots corresponding to different values of the smoothness parameter m, which affects only the kernel-based method by Fan et al. (2021). We let the antitonic, UCB, and VAPE methods remain the same across all three plots, while the kernel method's performance changes with varying m. Overall, our antitonic method generally outperforms the other approaches. The kernel- based method by Fan et al. (2021) also performs well and tends improve as the smoothness parameter m increascs. Despite tuning parameters, the UCB method by Luo et al. (2022) performs poorly, while as far as the VAPE algorithm by Tullii et al. (2024) shows worse performance than our method and kernel-based method by Fan et al. (2021)
13

---

Published in Transactions on Machine Learning Research (04/2025)
M
Antitonic
800
9000
2.01
UCB VAPE
Revenuee
800
800
8:01
233
300
200
1201
Time
Figure Revenue comparison
7
Conclusions
We introduced a novel method for estimating the market noise distribution Fo by leveraging its natural shape constraint: monotonicity. Our analysis lod an expected upper bound on the total regret of order O(Tv1))))/)+.) where v((x) defined in Equation (2), matching certain previous rates in T when a 1 and enjoying the additional advantage of being tuning parameter-free Compared to existing methods such Tullii et al. (2024); Fan et al. (2021); Luo et al. (2022), our proposed algorithm shows stronger empirical performance in both simulations and real data applications.
An interesting direction for future research the study lower bounds on the expected regret under the Hölder condition on So and an investigation into whether our rate matches this bound. the special case when a 1 (i.e. Lipschitzianity has been attained in Tullii et al. (2024). Another promising extension, particularly for practical applications. is the incorporation of optimal design strategies, as discussed in Remark 4.4. This could significantly improve the multiplicative constants in the regret, leading to more efficient algorithms.
Fu), the regret lower bound of 2(T2/33 established Xu Wang (2022),
Another promising avenue for further research is to integrate the Tullii et al. (2024) algorithm with our antitonic regression approach. The Tullii et al. (2024) method offers a better thcorctical upper bound, whereas our algorithm shows stronger empirical performance. potential stralegy would be to relain the Valuation Approximation step from their Algorithm while replacing the Price Elimination step with our antitonic regression procodure (as highlighted by the blue box in Algorithm 1). The final optimal price would then be computed in Equation (5). We acknowledge that this idea is preliminary, and further investigation is required to rigorously Tormalize the integration and to perform comprehensive regret analysis.
8 Code Availability
The codes are available at
ittpaa/eeoeeeaaaaaiiiiiiiiioooii TMLR 2025.
Acknowledgements
We used generative AI tools when preparing the mamuscript; we remain responsible for all opinions, findings, and conclusions or recommendations expressed the paper. This paper is based on research supported by the National Science Foundation under grants 2027737, 2113373, and 2414918.
References
Gah-Yi Ban and N Bora Keskin. Personalized dynamic pricing with machine learning: High-dimensional features and heterogeneous elasticity. Management, Science, (7(9))5549-55)) 13655955688,, 2021.
Omar Besbes and Assaf Zeevi. Dynamic pricing without knowing the demand function: Risk bounds and near-optimal algorithms. Operations research, 507 2009.
14

---

Published in Transactions on Machine Learning Research (04/2025)
Danicle Bracale, Subha Maity, Moulinath Banerjee, and Yuckai Sun. Learning the distribution map in reverse causal performative prediction. aix preprint orXiv:2405. 15172, 2024.
Nicolo Cesa-Bianchi, Tommaso Cesari, and Vianney Perchet. Dynamic pricing with finitely many unknown valuations. In Algorithmic Learning Theory, pp. 247-273. PMLR, 2019.
Wang Chi Cheung, David Sinchi-Levi, and He Wang. Dynamic pricing and demand learning with limited price experinentation. Operations Research, 63(6):1722 1731, 2017.
Arnoud V Den Boer Dynamic pricing and learning: historical origins, current research, and new directions. Surveys in operations research and management science, 20(1):1-18, 2015.
Arnoud V den Boer and N Bora Keskin. Discontinuous demand functions: Estimation and pricing, Management Science, 66(10):4516-455) 2020.
Jianqing Fan, Yongyi Guo, and Mengxin Yu. Policy optimization using semiparametric models for dynamic pricing. arXiv preprint X10: 06368, 2021.
Negin Golrezaci, Adel Javanmard, and Vahab Mirrokni. Dynamic incentive-aware learning: Robust pricing in contextual auctions. Advances in Neural Information Processing Systems, 32, 2019.
Stephen J Grotzinger and Christoph Witzgall. Projections onto order simplexes. Applied mathemalics and Optimization, 12(1):247 270, 1984.
Adel Javanmard and Hamid Nazerzadeh. Dynamic pricing high-dimensions. Journal of Machine Learningg Research, 20(9):1-49, 2019.
Adel Javanmard, Hamid Nazerzadeh, and Simeng Shao. Multi-produet dynamic pricing in high-dimension with heterogencous price sensitivity. In 2020 IEEE International Symposium on Information Theory (ISIT), pp. 2652-2657. IEEE, 2020.
Adel Javanmard, Jingwei Ji, and Renyuan Xu. Multi-task dynamic pricing in credit market with contextual information. arxvv preprint arXiv:2410.14480 2024.
N Bora Keskin and Assaf Zeevi. Dynamic pricing with an unknown demand model: Asymptotically optimal semi-myopic policies. Operations research, 62(5):1142-1116 2014.
Subodha Kumar, Vijay Mookerjee, and Abhinav Shubham. Research operations management and information systems interface. Production and Operations Management, 27(11))1893-1900 2018.
Yiyun Luo, Will Wei Sun, and Yufeng Liu. Contextual dynamic pricing with unknown noise: Explore-then-uch strategy and improved regrets. Advances in Newral Information Processing Systems, 35:37445 37457, 2022.
Yiyun Luo, Will Wei Sun, and Yufeng Liu. Distribution--ree contextual dynamic pricing. Mathematics of Operations Research, 49(1):599-618, 2024.
Sentao Miao, Chen, Xiuli Chao, Jiaxi Liu, and Yidong Zhang. Context-based dynamic pricing with online clustering. arXiv preprint 1rXi::1902.00 06199, 2019.
Alexandre Mösching and Lutz Dümbben. Monotone least squares and isotonic quantiles. 2020.
Hans-Georg Müller. Optimal designs for nonparametric kernel regression. Statistics & Probability Letters, 2 (5):285-290 290, 1984.
Tim Robertson, Richard Dykstra, and FT Wright. Order restricted statistical inference. (No Title), 1988.
Ryan J Tibshirani, Holger Hoefling, and Robert Tibshirani. Nearly-isotonic regression. Technometrics. 53(1): 54-61, 2011.
Matilde Tullii, Solenne Gaucher, Nadav Merlis, and Vianney Perchet, Improved algorithms for contextual dynamic pricing. arXiv preprint Xrx::2440. 1 11166, 2024.
15

---

Published in Transactions on Machine Learning Research (04/2025)
Jianyu Xu and Yu-Xiang Wang. Towards agnostic feature-based dynamic pricing: Linear policies linear valuation with unknown noise. In International Conference on Artificial Intelligence and Stalistics, pp- 9643 9662. PMLR, 2022.
Zhibiao Zhao and Weixin Yao. Sequential design for nonparametric inference. Canadian Journal of Statistics, 40(2):362-377, 2012.
16

---

Published in Transactions on Machine Learning Research (04/2025)
A Missing Proofs
A.1 Proof of Proposition 4.6
Proof. By Equation (7) we have Sa(u) J So + (0 00) x x))Pa()) from which we note that So is non- con-increasing, because Su non-increasing. Moreover So is a- Hö-Hlder,
[So(u) - So(u)] = / |So(u + (0 (6-6)) 6o)T x) So(r (0 - 0o) x))
< / - dP) Cilu -
and
(So(u) So(uu] / [So(u +0 (0- 00) 2)) (o(u))dPxxx)
< / C1 0o) xP (x)
$ C - 8o 12
where in the last inequality we used Cauchy-Sewarte and that | s Rx.
A.2 Proof of Theorem 4.8
We first need to Lemmas: Lemma A.1 and Lemma A.2. Lemma A.1. Let
(0) - 1 Σ (us)(
Ore jur
and
(a A max 1crgasm
0 (r)(
Then for any conslant D > 1,
P (n) < (D (D1ogn)1/2) 51-(2t) (2#
Proof. First, the by Hoeffding's inequality, since yj are independent. random variables taking values {0,1) 1} with mean So(w:), for every 7) 0 we have
P (Voosslorr S.r( n| < 26 20²
Note that M, is the maximum of the (m==)) quantities
0 Mir (0))
1/2
Consequently,
P P(M,( 2 mmm I Σ
(0///1 S,,( 2 171
ISrsssm
< 2
2
m
exp (-21%))
< exp (2log + 1) 2m
I exp (2 log( (n 1)/n (1+1)2
for arbitrary n, 2 But the right hand side converges zero as - 00 if Th (Dlogn) for some
D> 1.
17

---

Published in Transactions on Machine Learning Research (04/2025)
Before proceeding with the technical Lemma A.2, let's define
log 12 Pn.
and X()) the Lebesgue measure, and denote by Pa(.) the empirical measure of the design points wt, that mcans
(B((B - #1 B) for B cuu
Lemma A.2. Let W1, u....... Wn iid. points with density fw that satisfies inf S 2 C2 for some universal constant C2 > (which is the case for the uniform distribution), then for given constant 0, and for any 7 > 2, there erisls no no(7, ()) E N and sequence en =nn Ki, KE, a:) > en 0 such that
1
P(Ann) 1-
2 no
2(n 2
where Ang the event.
Pn (Uh) Un cU, 2 8n & kpn (11/22at1) ) C2(11cc). ((un)
inf
Proof. This is immediately dcrived from the proof of the more general result by Mösching Dümbgen (2020, Section 4.3) which can be stated as follows: let 8, > such that on - 0 while nón/ log(n) - oo (as n + oo). Then for every y 2, there exists no noly, 8,) and en = c, 8n) > En 0 such that
P inf (
Pa. (W,)) Un c u, 2 6n P(U.)
21 )
21- > -1
n 2
2(n 2)7-2'
where P(.) is the probability measure of the design points Wes that is
P(B) A f fu(()dww, for cuu,
and
en - max (cn/6n, v2cn/6n) + (πōn) 0,
where en & ylog(n + 2) 1). The value no is the smallest integer n that satisfics 6, <
Now we prove Theorem 4.8.
Proof. Let n be sufficiently large so that Un # 0 and such that the event An,y in Lemma A.2 occurs. Since fw is the uniform distribution, the value C2 defined in Lemma A.2 corresponds 1/l4/. For Un the indices
r(u) min (j (1,.... m) uj 2 8n).
j(u) A max (j E (1....,m) m) u, s u)
are well-defined, because [u- u| is subinterval of I of length 8n Note that by Lemuna A.2 this interval contains at least one observation uy. Moreover,
r(u) S j(u).
5n S ur(u) I Ui((a)) S u, Or(w)j(u) on ([u Sn, u|) > C2(1 cn)ndn,
18

---

Published in Transactions on Machine Learning Research (04/2025)
where en is defined as in Lemma A.2. Consequently, with (0) as in Lemma A.1, we have
(u) So(u)= - (o(()(()) Su)
min max Drs Sg(w)
(5)(a) #2)(1)
< max Vr(u)s So(u) 22((a
S (r())((w) Mn (0) + max Sr(u)s - So(u) s2j(u)
1/2
$ (C2(1 - ()))),)))) ) 1/2 (a) + So(ur(w)) - So(u)
11/ S (,) -1/ Ma (0) + Cj
In the first step, we used antitonicity of u + (u). and in the second last step we used antitonicity of u + So(u), and the last step utilizes that by Assumption 4.7. But on the event {M, - (D n))/2, the previous considerations implies that
sup (Bo(u)= - So(w)) S (C2(1- (C)(L= 1/2 (ologn) + C1 = Cpp//aaa)) NEM,
where C= VKD/C2 + Cin², and recall that C2 = 1/ and D is any real value strictly greater than 1.
But sup (Sa(u) - -s)) S Cpn. (2(2++1) happens in An, n (0) < (D (llogn)//3) which has probability w
P(An. n (0) S (Dlog n) 113)) PP n.7 U (0)
2 1 -(4 P(M, (0) 2 (D logg)) 1/2)
P(An.) + +MM - (Dlogn)
1 2 1 2(n + 22
11 m+1 1
D
2 (n + 2) 2
n"
where we used that by Lemma A.1, for any fixed D > we have PP (Mr, S (D (Dlogn) 2 1 - 11-(")) (2 and
by Lemma A.2 for any y > 2 we have P (An,) > 1 2(x+2)> The last two inequalities come from choosing
D sufficiently large.
Analogously one can show that on {M, < (D (Dlog (Dlog))'/3)
sup (So(u) Sa(w)) (no,,) ) weth.
1/2 (D log + C18 (2a/(2a+1)
with the same constant C and with the same probability tail.
A.3 Proof of Theorem 4.10
Fix & 2 2 and define ny = [& and 7e = [Tgl and as = |x = ny + n4. Let So (p x)) A So(p 0 x) and
3g (pl x)) A Se(p x). For the exploration phase E[ELEE, re(pt) (p() S Pmaxx [Ex S Fx Now fix
t E%
r((p)) - rp(pp)
= So (pi (xe) -p (pel mx)
= {p,So (pi xx)) Sr (pž m2) } + { Se (ot |xx)) - 3p (pr mx)) + (p (or xx) P: (Pt mx)
5o by Equation (6)
5 Pmax Solvi xz) - Su(vi ara) + Pmax
Sa (pt xx)) So (pe. xx)
= -k(((p)) + RMee(pe).
19

---

Published in Transactions on Machine Learning Research (04/2025)
where (9) - [3c(q 0g 24) So (q- 8g x1)1 for q {pt. Pe), E Ek.
By Lemma 4.11 there exists ko such that for k 2 ko, B(Rx,c(()) x log nefmee 0/2041 (pl,Pt) with t E Ey-- Summing up for all E E yields that
+ (dlog ne/me) n/22 for
(Io8Tiffie) sonnt + (dlagma/ne)
Σ E
r((pt) - re(pe) 2 |E'
Merging with the exploration phase of episode i we get
E
Σ re(p)) - rp( LEJ
x SIEal + LE/g
( fo fire
0/20+1
+ (dlog neloon///s/ 00/2
Using that nig nu fax = 1/1 [Bab] minimize the total regret, and that [E S lTkl 222k-1 2 we get that the RHS of the last inequality is
dd (T 1) x d82kv for E > to be determined such that they
E Σ LEE
re(pt) - r((p))
x d82ku kv + 2*
( (1u8letzame)
a/2n41
(dloggattete) digev
0/2
S 2k 2
2hrr d82kr
0/20+1
+
( d62ku
0/2
2 2 + d 2a+1 (1
Eo
[|: + log d)) 2a+1 + (1-( ->) [k + log(d)) (d) (
2a+1
The exponents of the factor d are E, the first and the third exponent, i.c. f= (1 () to get g" a+2 The exponents of the exponential factor "'0)
2a+1 and (1- As the second exponent always negative we equalize a
Sa
2 are v, 1 - 2a+1 and 1 - Pg: 2 Equalizing the first two factors, we get V² 3a++1 however V* >> (1 - 2
pa
2a+1
for a > 1/2, is equal for a = 1/2 and less for a < 1/2. Then for a 2 1/2 we equalizing the first and last pa to get V² 2
factors, obtaining v = 2
2+a
Case a > 1/2. The expected regret in episode k E Dree re(pt) - re (P.)] is upper bounded by
2a+1 a 2 3a+1 (da+z + d [2a+]) [k: log(d) 2a71 + dat2 (k: + log(d) s 2 3a+1 dat2 lk: + log(d))
2²
a
20+1
where we used that 2a+1
2 for a E (1/2, 1]. Putting together the phases we gel
K
R(T) = E
(pip - re(o))
S 2
a s T3at1 dat2 log (dT), Sati datz [K + log(d))
2a+1
2at1
kn LEJx
where we used that K= = [log (T/T)) 1].
Case a < 1/2. The expected retreat in episode k, EE [EiE re(pt) - re(p))], is upper bounded by
2 2kzta (datz + d [2a+1) [k log(d)) 2a+1 + dat2 + log(d))² S 2 2ta dat2 [K + log(d) 2a+1,
2
2
2t2
where we used that 2a+1 2 for a E (0, 1J. Putting logether the phases we get
2 Σ r((i)) - re(pt) S $2 ziz da + log(d))zatt 2at1 S T2ta dat2 log Za+1 (dT)),
2
R(T) = E
Σ
Lk= tEJ,
where we used that K= = -log (T/m) )++ + 11, which concludes the proof.
20

---

Published in Transactions on Machine Learning Research (04/2025)
A.4 Proof of Lemma 4.11
Let ni [/ and Vig [Tel and & E Eyg Define the event & {10,- Ooll S Bog where we recall
Rag x dllggn nx
as defined in Lemma 4.3, and
- 0x[x)) x4) Rx,( = (9
- So (q - x1) qe (p.PP).
Recall that
0x = OLS( (1,, y1) Meee
S = Antitonii(((u, 3e) Weeee
and define Sk = - where by definition in Equation (7)
Sk(u) Sz. (u) Ez[So(u + (0x 0o) T>)]-
Now let ppr for some E E. We can write
Rg,((g) (x,c())((EL)) + (L)
Analyzing the (eE(()
By Lemma 4.3 we have E|
< 2P(()) = Qn, 2e 2e- -0-0
n2/16 + 2
Analyzing the (E)
(g) is less or equal than two times
55(g- - xx)))) x.) - Se(9 0 [))) + [Se(a 0g 24) Szla 0 (() [Sa(q 0 x.) Solg 0 x. ) ((xx))
(9)
Analyzing A on EN: Define the event S₃ = fsup For ny sufficiently large, by Theorem 4.8 we have that
- -u(1)-Sa(u)) & Cpa/22at)) where P. log(n)/n
E(A) = (EA (Ex)) + E(AT(SENEE)
IE
sup
(u()) (u( n&+) + ((((S))((EE)
Auell
log Tik
(2a++11)
PPS n& 2P(S))
Tig
log nip
(1(2++1)
2A 27
+ -
log ñip
a1(2a+1)
74k
where chose 7 2
Analyzing B on E7t By Proposition 4.6, Sg is a-Hölder, then E[BI(E,)] $ 0 -0o113 < R
Analyzing C on Egi By Proposition 4.6 we have (Sa(u) - II(w)) < 100 0 11 S R.
Combining the terms ((E() and (q)(())((E)) from Equation
(9) we get
log n
a/(2+11)
dllog ny
a/2
sup Rx,( x
7kk
7g
21

---

Published in Transactions on Machine Learning Research (04/2025)
B
Additional Plots of Section 5.1
130
Empirical slope: 0.74
Theoretical slope:
12.-
12.
log(Reg(t))
11.5
11.0
10.5
10.
log(t)
Figure 7: This plot was generated using as true Fo the considered in Fan et al. (2021) with density fo(2) = 6 G - =²) 1f2 E (-1/2, 1/2)). We repeated the simulation 36 times and the corrosponding 95% confidence interval. The plot is in logz-log, scale to show the regret rate (empirical slope): a slope of " indicated an ((7") regret. The black dashed line corresponds to our theoretical regret upper bound of 3/4. The estimated slope is very close to that value.
22


Reviews:
[{"review_id": "2LCKClyFZQ", "reviewer": "Reviewer_q6TL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper is well written and easy to follow, with detailed remarks that clarify the algorithm design and the associated proof sketches.\n- The idea of isotonic regression is new to the literature of dynamic pricing.\n- The removal of tuning parameters in the existing algorithm simplifies practical implementation.\n- Good numerical performance on both simulated and real-world data.\n\nWeaknesses:\n- The paper assumes a linear valuation function, whereas Tullii et al. (2024) have addressed non-linear cases.\n- The assumption that contexts are i.i.d. is somewhat restrictive; Tullii et al. (2024) have shown that this assumption can be relaxed (under Lipschitz condition on the noise distribution).\n- The reliance on uniform price sampling for exploration—while common in the literature—may be impractical when dealing with large feasible price intervals or when the noise distribution’s support is large.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper develops a novel algorithm for dynamic pricing using a linear valuation function under three mild assumptions: (i) bounded parameters, (ii) i.i.d. contexts, and (iii) an α-Hölder continuous noise distribution. \n\nKey contributions include:\n- A novel tuning parameter-free algorithm that relies on weaker assumptions about the market noise distribution compared to existing methods.\n- An analysis of the algorithm’s regret upper bound with a new concentration inequality.\n- Numerical experiments with both simulated and real-world data. The proposed algorithm performs well on both of them.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please expand the discussion regarding the i.i.d. assumption on the context vectors. For instance, is this assumption critical to relaxing the Lipschitz condition as required in Tullii et al. (2024)? What challenges might arise when dealing with non-i.i.d. contexts while employing the UCB/LCB-based algorithm from Tullii et al. (2024) or when potentially integrating it with the proposed antitonic regression? \n\nIn addition, it would be helpful if there are more discussions about the challenges of extending the current algorithm to accommodate non-linear valuation functions.\n\nMinor Suggestions:\n\n- Potential typo in abstract: “Previous works have addressed the challenge of unknown market noise distribution $F_0$” instead of “$F$”.\n- Ensure that $S_0​$ is formally defined.", "broader_impact_concerns": "There are no broader impact concerns associated with this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "sjdoBIHW9B", "reviewer": "Reviewer_S38K", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe extension from Lipschitz to $\\alpha$-Hölder continuity represents a novel contribution.\n\nThe paper is clearly written and easy to follow; it has been a pleasure reading the paper.\n\nThe method is examined both theoretically and practically, and also applied to real-world datasets.\n\nThe regret upper bound depends on $\\alpha$, which reflects the additional complexity of the considered problem setting herein. Moreover, the regret upper bound matches existing work when $\\alpha = 1$, i.e., the well-studied Lipschitz setting.\n\nWeaknesses:\n\nIt is not completely clear what motivates the consideration of $\\alpha$-Hölder continuity, especially in the dynamic online market scenario\n\nThere is inconsistency in the naming of benchmarks in the numerical experiments, e.g., Fan Method versus Kernel Method.\n\nA regret bound in expectation does not necessarily imply a regret bound in high probability. However, in existing work, a regret bound in high probability does not necessarily imply a regret bound in expectation.\n\nIt is unclear about whether Assumption 4.10 is too strong, since assuming the existence of such minimizers can be impractical.\n\nIn a linear setting, the context $x_t$ is assumed to be i.i.d. distributed, which can be a strong assumption. In contrast, in existing work—for example, in linear contextual bandits—the context is arbitrary.\n\nThere seems to be no regret lower bound that matches the regret upper bounds. Without such a bound, one cannot claim the optimality of the method.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the dynamic pricing problem in an online market and formulates it as a regret minimization problem. The main contribution is extending the noise distribution in the feedback from Lipschitz to $\\alpha$-Hölder continuity while maintaining the same linear model commonly studied in practice. Within this new setting, the paper introduces novel algorithms and provides regret upper bounds for these algorithms. Although the paper claims the novelty of introducing a new analytical technique, this is unclear based on the current writing. A clearer demonstration of this technique, if it exists, would be beneficial.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "First, please refer to the weaknesses section for suggested changes.\n\nIt is also important to specify the necessity of having $p_{min}$ and $p_{max}$.\n\nAdditionally, it would be helpful if the paper included a discussion on the technical challenges introduced by $\\alpha$-Hölder continuity compared to the traditional Lipschitz setting. Whether such an extension is a straightforward step based on the existing results requires further justifications. \n\nLikewise, the technical novelty remains unclear, especially in the absence of any intuition or proof sketch for the theoretical results. It is not evident what the main technical contribution is with $\\alpha$-Hölder continuity. In fact, it is not fully convincing whether considering $\\alpha$-Hölder continuity has a significant impact. I believe that including proof sketches would be very beneficial. At least for now, it is unclear how the results/proof correspond to the claimed contribution (3) in Section 1, i.e. in terms of the new technique. \n\nFurthermore, it remains unclear how to choose $\\tau_1$, given that the paper claims a contribution of being tuning-parameter-free. Including a discussion or insight on this aspect would be helpful.", "broader_impact_concerns": "To the best of my knowledge, there are no concerns regarding the broader impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "YN6hgL943D", "reviewer": "Reviewer_enYp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: the paper provides the first theoretical results for Holder noise. The proposed algorithm has good empirical performance.\n\nWeaknesses: the contribution of the paper and its relation with previous works is unclear on multiple aspects.\n\n1) The comparison with the work of Tullii at al. (2024) sounds misleading. While I agree that the choice of the parameter in the paper leads to a $(1-1/log(T))$ probability, it seems more like a \"typo\" to me. Indeed, $\\alpha$ appears only in logarithmic components of the high-probability regret bound and can be reduced to any term $T^c$, with c constant, at the cost of a negligible logarithmic increase in the high-probability regret\". To conclude, their proof is essentially correct and I think the authors should consider their bound sound. Am I missing something?\n\n2) The paper is based on some assumptions that are neither common to all previous works, nor without loss of generality. Moreover, some assumptions are not clearly stated in the statements. For instance, it is not clear that you are assuming that $F_0$ is not decreasing.\nTo conclude, in the Lipschitz setting you are achieving worst (or at best, no better) regret bound with stronger assumptions. You should better highlight, e.g., in the introduction, that in this setting the regret of your algorithm is $O(T^{3/4})$.\n\nTo conclude, the only theoretical  improvement over previous woks seems the ability to handle Holder noise.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the problem of designing regret minimizers for dynamic pricing. A fundamental feature is that the regret minimizer can exploit contextual data.  In particular, at each round the market value depends linearly on an observed context and some noise. The authors achieve sublinear regret bounds assuming that the noise is Holder continuous. This is an improvement over previous works, that assume (at least) Lipschitz noise. The theoretical analysis is complemented by an empirical analysis that shows that the algorithm performs well in practice.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Clarify the relation with previous works.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Since all three reviewers recommend (lean) acceptance, we are going towards the publication of the paper. 

After the revision, all reviewers are positive towards the paper. Reviewer q6TL and S38K called for clarification on the i.i.d. assumption in the context. Reviewer S38K called for clarification on the noise assumption and parameters. Reviewer enYp discusses the comparison with Tullii et al. and clarification on noise assumption. All reviewers are fine with the revision, and the comparison with existing work is now clarified. It seems that no significant issues remain.
Decision: Accept (poster)