A Bayesian Approach to Contextual Dynamic Pricing using the Proportional Hazards Model with Discrete Price Data
Authors: Dongguen Kim
Young-Geun Choi
Minwoo Chae
Venue: NeurIPS 2025 poster ()
Keywords: Contextual dynamic pricing
Discrete price data
Bayesian approach
Cox proportional hazards model
Primary area: general_machine_learning

Abstract: Dynamic pricing algorithms typically assume continuous price variables, which may not reflect real-world scenarios where prices are often discrete. This paper demonstrates that leveraging discrete price information within a semi-parametric model can substantially improve performance, depending on the size of the support set of the price variable relative to the time horizon. Specifically, we propose a novel semi-parametric contextual dynamic pricing algorithm, namely BayesCoxCP, based on a Bayesian approach to the Cox proportional hazards model. Our theoretical analysis establishes high-probability regret bounds that adapt to the sparsity level $\gamma$, proving that our algorithm achieves a regret upper bound of $\widetilde{O}(T^{(1+\gamma)/2}+\sqrt{dT})$ for $\gamma < 1/3$ and $\widetilde{O}(T^{2/3}+\sqrt{dT})$ for $\gamma \geq 1/3$, where $\gamma$ represents the sparsity of the price grid relative to the time horizon $T$. Through numerical experiments, we demonstrate that our proposed algorithm significantly outperforms an existing method, particularly in scenarios with sparse discrete price points.

random variable A Bayesian Approach to Contextual Dynamic Pricing using the Proportional Hazards Model with Discrete Price Data
Dongguen Kim', Young-Geun Choi', Minwoo Chac DDparrmeet of Industrial and Management Engineering,
Pohang University of Science and Technology
Department of Mathematics Education, Sungkyunkwan University [dgkim, mchae)dpostech.. ac kr; vgchoi@skku..o @du
Abstract
Dynamic pricing algorithmss typically assume continuous price variables, which may not reflect real-world scenarios where prices are often discrete. This paper demonstrates that leveraging discrete price information within a semi-parametric model can substantially improve performance, depending on the size of the support set of the price variable relative to the time horizon. Specifically, we propose novel canimparametric contextual dynamic pricing algorithm, namely BayesCoxCP, based a Bayesian approach to the Cox proportional hazards model. Our theoretical analysis establishes probbbbibbbb regret bounds that adapt to the sparsity level y, proving that our algorithm achieves a regret upper bound Ö(T() + /dT) for < 1/3 and O(T2/3 + VdT) for 2 1/3, where represents the sparsity of the price grid relative to the time horizon T. Through numerical experiments, we demonstrate that our proposed algorithm significantly outperforms existing method, particularly in scenarios with sparse discrete price points.
Introduction
Contextual dynamic pricing involves updating product prices over time based on contextual infor- mation such as customer features, product attributes, and market conditions. Given its importance and practical applications in revenue management, this topic has been extensively explored across The primary objective of contextual dynamic pricing is to maximize the seller's revenue through determining optimal prices that account for both covariates and demand uncertainty. A key challenge in dynamic pricing is balancing explo- ration, which focuses on learning the underlying demand, with exploitation, which leverages current knowledge to set optimal prices. Striking this balance is essential for developing effective dynamic pricing strategies.
statistics, machine learning, and operations research 99
43 34
A commonly studied framework in contextual dynamic pricing is the binary choice model, where the 7 31).
seller receives binary purchase feedback based on the posted prices 2
24
37 44]
30
Specifically, at each time t 1,..., T, the seller observes a covariate X, E R that captures customer and product features. Based on the observed covariate and historical sales data, the seller determines price Pe for the product. The customer's 's valuation of the product, denoted
V, Rz0. is unknown to the seller. Following the posted price, the seller receives binary feedback Y E 1), indicating whether purchase occurred. 'he customer purchases the product if and only if their valuation Vi exceeds the offered price Pt. which can be expressed as Y, 1(V, > P.)- Notably, V, is not directly observed, as it is censored by Pt. In the statistical literature, such data
"Correspondence to: mchae@postech.ac..
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

structures are called case 1 interval- data, also known as current status data 18 Case 1
interval-censored data has been extensively studied in survival analysis [T]
28
38
25
20
19
We consider a contextual pricing problem under the binary choice model. Let F(u X2) = PVVV S | X2) and S(v Xx) = 1 F(E X2) be the cumulative distribution function (c.d.f.) and complementary c.d.f. (or survival function) of 1 given X,, respectively. The expected revenue from a posted price p given the covariate X, is given as Ep Y, Xx)) = pV,(V, > p X2) - ps(p Xt).
Then an optimal price P at time t is defined as a price that maximizes the expected revenue:
P E argmax Xt).
P
The regret at time t is the difference between the expected revenue generated by the optimal price P." and that from the posted price Pt. given by r(t) P(P X,) - (. X.). An important objective is to design a pricing policy that minimizes the cumulative regret over a given time horizon T, defined as R(T)= Σi=r(( r(t).
As shown in (T. designing an effective pricing policy necessitates accurately estimating the comple- mentary c.d.f. S(- X1). Thus, a wide range of contextual dynamic pricing algorithms have been developed using various models for the conditional distribution of V,2 given X Linear 3
10 31, where F(v| | Xx) = Folr - X, B), and X1) Fole- - exp(-X, B)), serve as key examples. Here, Fo(w) = P(V S e X, 0) represents the baseline c.d.f., and / E Rd captures the contextual effect. More recently. (7) proposed using the Cox proportional hazards (PH) model, in which the com- plementary c.d.f. is modeled as S(v X+) = Sa(v)exp(x) (). Here, So) = Fo(()) represents the baseline complementary c.d.f. In particular,
models 2 36 23 17
24
44
6
30
33
log-linear models 37 where F(v
cani-parametric models, which assume that both the nonparametric baseline function Fo (or Sg) and the parametric coefficient /3 are unknown, have gained considrarle attention recently due to their flexibility and interpretability [37 30 TO 31.
In real-world applications, is erucial note that offered prices are often observed only on a discrete set. For instance, retailers commonly restrict prices to convenient values for case of communication and consumer familiarity, and businesses often adhere to predefined discount levels or promotional The significance of discrete price sets in revenue management has been Much of the existing dynamic pricing literature, however, focuses on
price points 33 22
widely recognized 12
32
continuous price spaces
2 36
23
33
6 30
10 31.
From a theoretical perspective, discrete price sets provide significant advantages for estimating model parameters. In simple survival analysis setup with i.i.d. case I interval-censored observations, [4] demonstrated that the inferential performance of the underlying survival function can be improved by leveraging the fact that the monitoring time (the offered price in the dynamic pricing setting) is discretely supported. To be specific, if the monitoring time is continuous, the optimal convergence rate for estimating the unknown survival function with case 1 dntterval-censone
data is known as n 11/3, where is the sample size [21]. On the other hand, in [41]. the monitoring times are assumed to be supported on an equally spaced grid set. Then, they proved that the nonparametric maximum likelihood estimator (NPMLE) achieves convergence rate of n-((1- (1-7)/2 for y < 1/3 and n -1/3 for 2 1/3, where 7 E (0, 1] represents the sparsity level of the grid relative to the sample size n (a rigorous definition is provided in Section 2. In other words, one can achieve much faster convergence rates if the grid is sparse (7 < 1/3). Moreover, they developed an inferential procedure, such as the construction of confidence intervals, that does not depend on the unknown quantity 7, often referred to as an adaptive procedure. While the adaptive procedure in [4] is quite complicated, [5] demonstrated that a much simpler and more practical Bayes procedure is also adaptive, and that the corresponding Bayes estimator achieves the same convergence rate. Although these aforementioned theoretical results are based on non non-contettual setup and i.i.d. data, they suggest that incorporating the discrete support of the price may lead to a pricing policy with smaller cumulative regret compared to one that ignores this information.
Motivated by these insights, we propose a novel semi-parametri contextual dynamic pricing algo- rithm, BayesCoxCP, based on Bayesian approach to the Cox PH model with case I interval-censored data. The algorithm is specifically designed to exploit the discreteness of the offered price, leading to improved performance. Our theoretical contributions are threefold:
We derive the posterior convergence rate of the Bayes estimators of the semi-parametric Cox PH model under the i..dd. setup. We assume that the offered price is supported on an equally
2

---

Table 1: Existing regret bounds for contextual dynamic pricing algorithms based parameettttric models. Note that the optimal rates depend on the model and assumptions, such as the smoothness of
Fo.
MODEL
REGRET UPPER BOUND
OPTIMALITY IN T
ADAPTATION TO DISCRETE SUPPORT
METHOD
FOR V4
LINEAR
Ö((Td) im-1)
X
31
LINEAR
Ö + 113 8 1hh)
X
X
LINEAR
O(
X
AAXAA
LINEAR
Ö(Tid)
X
LOG-LINEAR
O(ridt)
X
PH
O
X
Ö + vTT) (1 1/3)
OUR
PH
O + (1
O
O
spaced grid set and prove that the posterior distribution converges at the optimal rate, which adapts to the grid sparsity. This result generalizes the work of [5], who studied the survival model without covariates, to the PH model. It is also worth noting that our prior for the baseline cumulative hazard differs from that of [5] and achieve computational benefits.
We derive the regret upper bound of the proposed BayesCoxCP algorithm. Specifically, algorithm achieves regret upper bound of order T + 1/2 for y 1/3 and T + (dT) 1/2 for > 1/3, up logarithmic factor, where " represents the grid sparsity relative to the time horizon T. Notably, the BayesCoxCP algorithm does not rely on the value of 7, i.e., our algorithm adapts to the sparsity level. A careful selection of the exploration parameter ?)t is crucial in the algorithm's 's design; see Section for further details.
We also establish a non-contextual minimax lower bound for the cumulative regret in the discrete pricing problem, as stated in Theorem 5.3 It turns out that our regret upper bound for the BayesCoxCP algorithm is optimal up to a logarithmic factor in terms T'
Through extensive numerical experiments, we empirically demonstrate that the proposed pricing algorithm significantly outperforms the Mtateoof-the-ae method when prices are discretely supported.
The remainder of this paper is organized as follows. In the following subsections, we introduce the notations used throughout the paper and provide a brief summary of related works. Section interval-censored data on grid and describes the Cox PH
introduces the basic setup for model, along with the prior distributions employed. Section 3jestablishes the convergence rate of the posterior distribution under the i.i.d. setup. Section jintroucees the BayesCoxCP algorithm and Section 3 presents its regret analysis. Finally, Section presents numerical experiments to evaluate the effectiveness of our proposed algorithm.
1.1 Notation
For two real numbers a and b, aVb and aAb denote the maximum and minimum of and b, respectively. be divergence. For metric space (F, D), the c-covering and c- b-bracketing numbers of F with respect to distance D are denoted write a O(b) or a S if a S Cb for some constant C' > 0, where C is an absolute constant unless otherwise specified. In addition, we write if Cb for some constant C' > The notation O(-) denotes the corresponding bound that ignore logarithmic factors.
For two densities and q with dominating measure v, let DH (p. q) = (f -('"'/"g'''/"'dd
the Hellinger distance and K ((p. g) log(p/ (p/q)pdu be Kullback-Leibe
as (ie, F, D) and [e, F, D). respectively.
== 2(b)
1.2 Related works
The problem of contextual dynamic pricing has been extensively studied in the literature. Many recent works have focused on semi-parametric models where Fo unknown and nonparametric. For instance,
[30 31 [0] considered linear models with unknown Fo under certain smoothness

---

assumptions. In [T]. Fo is assumed to be m(2 2)th-order smooth, achieving a regret upper bound of Ö((Td) $1
relaxed this assumption by assuming that Fo is Lipschitz continuous and second-order smooth. They obtained regret upper bound of Ö(T2/3 - ||3 - 8 I1),, where 3/ represents the estimation error of 3 Similarly, 30] considered the same setting and achieved a regret upper bound of ((T2/3d)) under the Lipschitz and second-order smoothness assumptions on Fo. while showing that under a weaker Lipschitz assumption alone, the regret upper bound increases to ((Ts/td) On the other hand, 337 used a log-linear model with a second-order smoothness assumption on Fo, achieving a regret upper bound of ((11/2(41/4 but with suboptimal dependency on the dimension d. Similar to our approach, 77] used the Cox PH model, assuming that Fo is Lipschitz continuous. They derived regret upper bound of O(T2/3d) which improves the dimensional dependency compared to [7] but their analysis limited to continuous pricing settings. The overall comparison of regret bounds from these semi- cami--aramttii studies, along with our results, summarized in Table [ In addition to these works, earlier studies often assumed that Fo is known 24 and [4 both considered linear models under these assumptions. 24 additionally analyzed the case where Fo is unknown but belongs to a parametric log-concave family, deriving regret upper bound of order T2/22
and log-concave. For instance,
Preliminaries
2.1 Basic setup
In the current and next sections, we study the behavior of the posterior distribution from the PH model for analyzing case interval-censored data on grid under the i.i.d. regime.
To set the scene, suppose that (X,, Pt, Yz), I,.... . n. are i.i.d. copies of (X, P,Y). particular, we assume that Pt's s are supported on the grid set G = . 3 within the (fixed) interval P.aa.] whose cardinality may depend on the sample size n. The grid points are assumed to be uniform in the sense that gk+1 9s + 8 for every k 2 0, where go = Pminn and K is the largest integer such that 9K S Pmax: that is, K = [(Pmax - PPmin//8] We further assume that the grid resolution 5 is controlled by two constants Y E (0, 1] and λ >> 0, according to the relation 8 kn Note that generalizations to nonuniform grids are discussed in Appendix D
Let Q-- X) denote the conditional distribution of P given X, with q(- | X) denoting the corre- sponding probability mass function. In addition, the marginal distribution of the price P is denoted by Q(-), with its probability mass function given by g(-). Let Px and px be the marginal distribution and the corresponding density of X.
2.2 Proportional hazards model for V/2
We consider the Cox PH model for the conditional distribution of V given X,. Formally, the complementary c.d.f. u - S(x] X,) of V, is modeled
S(v X₂) = (o()))xp(X)) (TxT 8)
where S-(+) is baseline complementary c.d.f., and B E Rd is regression coefficient. We assume that V2 is continuous. Let Fo So. Ao = / So and (o = ff Ao (o(udu be the c.d.f., hazard and cumulative hazard functions, respectively, corresponding to So, where F/ denotes the derivative of Fo.
We remark that the joint distribution of (X,, V.) depends on the unknown parameters (So, B, PxPxx g(- -)). Among these, While (So, 9) are the parameters of interest, while (px, 7(- ))) are treated as nuisance parameters (at least in the current and next sections). Since P, is
supported G. the joint distribution of (X,, Pr, Y:) depends on So only through the vector So = (So. So E [0, 1|K, where So, = So(gu). Here, X represents the support of the covariate X. The parameter space is defined as = {0 = (So, B) E So Red where So = (So (So. So,x) So,1 2 ... So,K 0}.

---

2.3 Prior
We note that Vi is continuous while P. discrete with support G. To reflect this structure, we model the baseline hazard function )o(-) as left-continuous step function, where the jump points are located at grid points. Let λo "o.1....,,o.K.. Ao (Ao.1....,AAp Ao.k) and
K
Aa(p) = = 1p (9k-1.9k]}.
where Ao,s log So,t- Since there is one-to-one correspondence between So and λo can impose a prior on So through X We consider an independent prior for the unknown parameters Xo and B. specified as IIg x I2 Here, Il consists of independent gammas:
Au, Gamma(a p), k = l,..,,, K
where Gamma p) denotes the gamma distribution with mean 03/p p and variance 0x/p². Gamma priors are commonly employed for Åg Bayesian analyses of the PH model, as seen in 47 We further impose the following conditions on the prior:
29
(P1) B has a continuous and positive Lebesgue density on IRd
(P2) There exist positive constants a < such that a oz S for 1, 1,..., K.
3 Posterior convergence rate under i..dd setup
8 To clarify notation, we use the superscript * to denote the true parameter, e.g., 3" and Ag. Suppose that there exists true parameter 8 (S, B*) generating the data D,, = {(x,, Pt. Y)) (We may regard px and q(- :) as known parameters if we are only interested in inferring 0.) Given the data D.,, II( D.,) be the joint posterior distribution of X and B.
Assumptions tions:
We will prove that II(.) Dn,) concentrates around 6* under the following assump-
(A1) 18 122 B for some constant B O.
(A2) xx
and px is bounded away from zero X, where X = Rd ||ll| L..
(A3) P(XT T3 # X 32) for 31 # $2.
(A4) For E X and 1 < k < K, suppose Q(G x and g(gk (x) Z 2 (logn)
if < 1/3, gggg x:) -ーー (log n) otherwise.
(A5) The support of Fi is [Umin: F.ma]] Umin < Pmin Pmax Umax, and Sj has continuous and strictly negative derivative on [Vminy Vmax]-
Assumptions (Al) and (A2) are commonly adopted in the stochastic contextual dynamic pricing
literature. Assumption A3 ensures the identifiability of the regression coefficient. Assumption (A4)
requires that the conditional distribution Q(- z) maintains certain level of uniformity over the
grid set G. For instance, when Q(- follows uniform distribution over G.
(A44) is satisfied for
any y E [0. 1]. In the contextual dynamic pricing problem, the function q( æ>) is parameterized by the pricing policy. Therefore, constructing policy that satisfies (A4) is crucial. In Section 4
we explicitly design a policy that fulfills (A4) Assumption (A5) implies that S is Lo-Lipschitz on
[Pmin: Pmax] for some constant Lo 0, and that So, and So, are bounded away from 0 and 1.
We define the distance D3 on the parameter space θ as
(0 || - So.2 + 11 -B2122.
for any 0, -So. ,So,,, = (So.2 . 32) O where || 112,2 denotes the (Q) norm with respect to a probability measure Q that is. ||Sol12.
<Σ== (So,a) (((x)) 1/2
For given parameter 0, let P2 denote the law of D,, under 0, and let Eø be the corresponding expectation. With these definitions place, we now state two theorems that establish the convergence rates of the posterior distribution
in two distinct cases: 7 1/3 and 1/3.
5

---

Theorem 3.1 (Case
< 1/3). Suppose that < 1/3 and assumptions (AI) (A5) hold. Let
En 2 Vlg + V log(d n).. Then, there exist positive constants C1,.. C2 depending only on L, B, Pmin+ Pmax: R, a, at p. such that for 2 C4.
IT (D, 0*) 2 C1 D.) & (eexp(-Canee
with p. prrobability at least (exp(-Cane,) + 1/n
Theorem 3.2 (Case y 2 1/3). Suppose that 7 2 1/3 and assumptions (Al) (A5) hold. Let
log
+ +V "VEVioo Voolld V n). Then, there exist positive constants Ci,..., Ca, depending only
Cn
on L, B, Pmin Pmax: N, at, P. such that
11 (De 0-) Cien Da) C2En,
n nz C1
(exp(-C3nec) exp (-Canà)
if 31 if
with Pg. proopbbbbyylity at least
(En + 1/ne where En.
Theorems 3.1 and 3.2 show that the convergence rate of the posterior distribution adapts to the sparsity
level 7. Importantly, when 2 1/3, the posterior achieves the convergence rate of n 1//3 -1/3, as in the continuous observation setting. In contrast, for 7 < 1/3, the posterior attains faster rate of n -12 highlighting the advantage of discrete observations in sparse grids. This result generalizes the work of [5), which focused the non-contextual case interval-censored data, the PH model.
4 Proposed BayesCoxCP algorithm
We now propose the contextual discrete pricing algorithm, namely BayesCoxCP, based on a Bayesian approach the semi-parametric Cox PH model. Consider the discrete pricing setting introduced earlier. Assume that the support of P: is G = {9k = 1,..., K) for every | = 1,..., T. where T denotes the time horizon. Here, 9k Pmin + kō for = 1,..., K, K [(Pmax - Pminmmm////m /8]. and 8 = <T for two constants E (0, 1] and >> O. Under the PH assumption with the true pair (S% 3r), the optimal price P. at time can be defined as P. E argmaxpes {p- 1p-S% (p) a*)
Let Q* denote the marginal distribution of P with its associated probability mass function denoted by q".
We employ epoch- epoch-based design that divides the given horizon T into multiple epochs and executes identical pricing policies on per-epoch basis. Such design was widely adopted the literature 44 7. Epochs are indexed by and the length of the epoch is denoted by m4. The length increases geometrically with 1, given by ni = ny 2/-1 for I 2 1. The set time indices for epoch is given by & = (E R2 + +1, 1..... E.zo } with 0, ensuring sequential partitioning of the entire horizon.
24
Posterior-based estimation Let ((, Yi) denote the data collected during epoch 1 12 1. We employ consistent prior across all epochs, denoted as II IIg x IIx, where II,, consists of independent gamma distributions:
Au, Gamma(ak, p), 1: -=11, 1,,..,,
with ag = a for t: = ,,..,,KK K and a fixed constant a > 0. The prior 11 on 3 has density with respect to the Lebesgue measure on Rd bounded away from zero in a neighborhood of 8". Common choices for II include multivariate distributions such as the normal distribution. For each epoch let D.-1) denote the joint posterior distribution of Ag and / based on the data from the previous
epoch, D.-1- We denote the point estimator for the true parameter 0* as - (S) 3,
derived from the observations D in the previous epoch. Specifically, the estimator 0 -1 is obtained as the mean of truncated posterior distribution Ii(- Dz = II(-I DI-1)/II(@ D:-1), where the truncated parameter space is defined by θ So [a, b)d for fixed constants and b.

---

Algorithm Bayes Cox Contextual Pricing Algorithm (BayesCoxCP)
Input: 7i1 the length of the first epoch; Nz: degree of exploration; A NI.: prior; a, b: truncated range
1: For t 1, ..... M1. uniformly choose Pt from G, and get reward Y;;
2: for epoch / = 2,3,.. do
3: Obtain the estimator 0- = ( from IT(- Dí-1)-
4: for time E & do
5: Observe X, and draw a binary number R from Bernoulli(1 - m))
R = 1 then P. E argmaxpes {2 {p. (p) (xp)))xp(; }-))
6:
7: else Uniformly choose Pt from
8: end if
9: Get reward Y,-
10: end for
end for
Pricing policy We denote the pricing policy for epoch I as ग X - P(g), where P(g) denotes the set of all probability distributions over the grid G. Specifically, given covariates X, for t & the distribution (X,) is defined as a mixture distribution given by
(A) (1 n) 66p (A) + m Ug(A)
for any A 9, where pI- is the myopic policy determined by the estimate Ø (8/- 1
as Pl-1 argmaxpeg {p- (p))xxx) B-)). Here, öp denotes the Dirac measure centered
P. Ug represents the discrete uniform distribution over G. and is an epoch-specific exploration parameter, defined as
" = min
in (22 12 Vlog 21-1,1
where 7/1 and 722 global constants. The design in (6) reduces the need for uniform exploration when the grid is sparse, while increasing it as the grid becomes denser, effectively balancing exploration and exploitation across different epochs. The choice of 1n directly ensures that assumption (A4) is satisfied, since ?n controls the degree of uniform exploration over the grid, which is reflected in q(- æ). This connection is rigorously established in Lemma C.4 In numerical experiments, !/1
and 1/2 are tuned to optimize the degree of exploration.
in
The pseudo-code for the proposed policy is presented in Algorithm In this algorithm, for each time I E &,, the offered price Pt solely relies on the observed covariate X, and the data from previous epochs, DI... D while the distribution of Vi only depends on X₁. Thus, Algorithm D ensures conditional independence between V2 and P: given X,, i.c., V, I P, for each E &,. Moreover, given the data from previous epochs 1,.... 1, {(x,, Pt. Y)) are independent and identically distributed observations, which facilitates separate estimation of 6" for each epoch.
For the computation of Ø-1 for each epoch I. we employ the variational Bayesian (VB) method
for the PH model with case 1 interval-censored data. The VB approach has recently emerged as computationally efficient alternative while maintaining estimation accuracy; see [29]. Alternatively, one may employ Markov chain Monte Carlo (MCMC) methods (27 which facilitate inference, such as constructing credible intervals for 6*
Regret analysis
In this section, we analyze the regret upper bound for the BayesCoxCP algorrith. Furthermore, prove the regret lower bound for the discrete pricing problem.
5.1 Regret upper bound
We first introduce several technical assumptions and a key lemma that establishes the estimation error of the estimator Ø--1 for each epoch.
7

---

We begin by assuming the following additional conditions:
(B1) For any E X, there exists a unique maximizer of the map p + p.S (p) (p))(ppp jex((e T (0)) Pmin Pmax] + IR.
(B2) The density of the unique maximizer the map p + (p) (B))) Pmin Pmax] is bounded away from zero on [pminn Pmax]-
B*);
IR
The uniqueness condition in assumption (B1) commonly adopted in the contextual dynamic pricing literature 124 44 [0] Aditionally, assumption (B2) ensures that q" (p) x 5 for all p E G.
We remark that the grid G remains unchanged across epochs in our setup, the grid sparsity relative to the sample size ny differs for each epoch. For each / = 1.2...., define as the sparsity level in epoch 4, such that K = [Pmmax Pmin)/(xs))
") Therefore, for all 2......, we have (KTg
Pmax
Pmin
Pmax Pmin 1m
n1
K
Let Qi(- | X) and g(( X) denote the conditional distribution and corresponding probability mass function of Pt given X (and D during epoch 1, respectively. The marginal distribution of Pt during epoch / is denoted by Qr, with qi as its probability mass function. Then, qr(: x) = (.)) for E X.
The following lemma provides an upper bound on the estimation error of the point estimator 0-11 epoch L.
Lemma 5.1. Let the prior II and policy mı be as described above (see 4 and 55)- Suppose that ussumptions [A3) and [A5] Then, there exist positive constants C1 C2 C3 and C4 depending on L,, B. Proin Pmax: K; P, a, and my, such that for 2 C4.
Do. (0'1000) Cie111
with probability at least 1 - 51-1 - 1/1n 16 where
log Th
+
d
in < Vloold (
(exp(-C2mat) (exp(-Can))
if < 1
and G
31
Jogni
+
d /lold nz)
if
if 2 3
Lemma 5.1 implies that --1 achieves an error bound that is adaptive to the grid sparsity level 7 in epoch 1. By leveraging the consistency of 01 and Hoeffding's 's inequality, the regret during epoch / can be upper bounded by
Σr(t) r(t) CiniDa....PP1 C2nm KE
with high probability, where C₁ and C2 are positive constants which do not scale with ny and (see Lemma B.1 for details). This inequality shows how the estimation error of 0 and the exploration
parameter nn affect the regret upper bound. Combining Lemma 5. and (6). we now state the main results regarding the regret upper bound for the BayesCoxCP algorithm.
Theorem 5.2. Under the same conditions as in Lemma [.7 along with assumptions (B1) and (B2)
there exist positive constants CI,..., Or depending on I,, B, Punin Pmnax Kr O, Ps m. 12, 7 and nn such that for T 2 Cr.
C2 C2 + T TogT
{T<? < 3
R(T) <
dT dT (d 3 TlgT
2 31
Co 1)/T7 C, lTg + 1)/72/9
<<<< 31
with probability at least where Ç
if
Theorem 5.2 shows that the BayesCoxCP algorithm achieves a regret upper bound that adapts to the unknown sparsity level 7, ensuring efficient performance without prior knowledge of ry
8

---

1000
Reigeer
Timee
BayesCooCP
Chai mt al. (2023)
(a) J 4) + U4,
10
100
Cumsuitte
1550
3853
1508
3000
808
5800
1200
30.30
11000 3800
1902
1050
3050
1800
1380
1550
3000
(b) T3.23. 1,5", 10) (7.((, 0.5", 1,
Figure 1: The cumulative regret curves compare the proposed algorithm (BayesCoxCP) with other method. Solid lines indicate averages, and bands show standard errors over replications.
Compared to existing work in continuous pricing settings, our results underscore the theoretical advantage utilizing the information that the price is discretely supported. For instance, 7 derived a regret upper bound of ((T2/sd) under similar assumptions. While this bound comparable to our result for 2 1/3, our algorithm achieves a strictly faster regret rate of O(T + 1/2) for y < 1/3, which a distinct advantage of the grid-based setting. For additional discussion on the possibility of replacing the Bayes estimator with the NPMLE and its effect on exploration parameter choice, please refer to Appendix G
5.2 Regret lower bound
In this subsection, we establish regret lower bound for the non-contextual pricing problem in the discrete pricing setting. The proof carefully incorporates ideas from (6) and [1), widely used for regret lower bounds in dynamic pricing and multi-armed bandit problems, with a focus on the discrete price setting. Specifically, for dense grids where y 2 1/3, we partition the grid set G into 7//3 segments derive the lower bound. Further details of the proof are provided Appendix B.3
Theorem 5.3. (Lower bound for non- contextual pricing) Consider non-contextual pricing problem where the valuations are sampled independently and identically from a fixed unknown distribution satisfying the c.d.f. F(v) is bounded away from O and 1 for [Pmins Pmax] and at least one maximizer of the revenue curve v - F(u)) lies over G. Then, for any > O, no pricing policy (algorithm) can achieve expected regret O(T -n if 1/3, and O(T -) if 2 1/3.
As in Theorem 5.3 the regret lower bound depends on the grid sparsity level 7 as well. Specifically, for y 1/3, the regret lower bound scales =+2 while for 2 1/3, it scales 2(T2/3). Comparing these results with Theorems B.1
3.2 and the regret upper bounds achieved by BayesCoxCP algorithm match the lower bounds in terms of 7, to logarithmic factor. Note that the dependency on the dimension is not addressed this work, leaving as a direction for future research.
Numerical experiments
In this section, we conduct numerical experiments evaluate the performance of the BayesCoxCP algorithm. Since our objective is to highlight the benefits leveraging discrete support information, focus comparison with the algorithm proposed by [7]. For comparisons of the PH model- based algorithm with other approaches, such as linear and log-lineat model-base -based algorithms, we refer
consider the following experimental setup. The covariate X, drawn from a d-dimensional ball with radius of 1/2 under uniform distribution, where d = 5. The true regression coefficient 3 is

---

set as 8" 4 la. where 1a denotes a d- d-dimensional vector of ones, For the true baseline distribution, va
consider two different mixture distributions. The first is uniform mixture distribution given by 2 (1,44) + 24, 10), where U(a, b) denotes the uniform distribution over [a, b]. The second is truncated normal mixture distribution given by (3.(5, 0.5², 1, 10) + TT.(7.75, 0.5², 10), where (N o², b) represents the truncated normal distribution with mean μs, variance a², and 9K } is chosen from [1. 10] with four different values of support [a, b). The grid set = {gi...... :
K E {10, 100, 1000, 30000). The total time horizon is set to T 30000 for all experiments. To conserve space, the detailed hyperparameter settings for algorithms used in the experiments are provided in Appendix H
The cumulative regret results for different grid sizes, averaged over 20 replications, shown in Figure I BayesCoxCP consistently achieves lower cumulative regret compared to the method proposed by 77 with the difference being particularly significant when K is small. Notably, the performance gap gradually diminishes as K increases. These findings empirically demonstrate that BayesCoxCP adapts effectively to varying grid resolutions, providing strong empirical support for its theoretical guarantees.
Acknowledgements
This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. RS-2023-00240861, RS-2023-00252026), a Korea Institute for Advancement of Technology (KIAT) grant funded by the Korea Government (MOTIE) (RS- 2024-00409092, 2024 HRD Program for Industrial Innovation). and Institute of Information & Communications Technology Planning & Evaluation(IITTP- Globall Data-X Leader HRD program grant funded by the Korea government (MSIT)
References
[1] Pierre Alquier and James Ridgway. Concentration of tempered posteriors and of their variational approximations. Annals Statistics, 48(3):1475-14977 2020.
[2] Kareem Amin, Afshin Rostamizadeh, and Umar Syed. Repeated contextual auctions with strategic buyers. In Proc. Neural Information Processing Systems, 2014.
[3] Gah- Yi Ban and Bora Keskin. Personalized dynamic pricing with machine learning: High- dimensional features and heterogeneous elasticity. Management Science, 67(9):5549-556) 2021.
[4] Omar Besbes and Assaf Zeevi. Blind network revenue management. Operations Research, 6036)11537 2012.
[5] Minwoo Chae. Adaptive Bayesian inference for current status data on a grid. Bernoulli, 29(1):403-42) 2023.
[6] Xi Chen, David Simchi-Levi, and Yining Wang. Privacy-preserving dynamic personalized pricing with demand learning. Management Science, 68(7):8878-45) 48988 2022.
[7] Young-Ges Geun Choi, Gi-Soo Kim, Yunseo Choi, Wooseong Cho, Myunghee Cho Paik, and Min-hwan Oh. Semi-parametric contextual pricing algorithm using Cox proportional hazards model. In Proc. International Conference on Machine Learning, pages 5771-5786, 2023.
[8] Gregory Cox. A generalized argmax theorem with applications. arXiv:2209.08993 2022.
arXiv preprint
[9] 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.
[10] Jianqing Fan, Yongyi Guo, and Mengxin Yu. Policy optimization using semiparametric models for dynamic pricing. Journal of the American Statistical Association, 119(545):522-566 2024.
[11] Dianne M Finkelstein and Robert A Wolfe. A semiparametrie model for regression analysis of interval-censored failure time data. Biometrics, 41(():933-945, 1985.
10

---

[12] Guillermo Gallego and Garrett Van Ryzin. Optimal dynamic pricing of inventories with stochastic demand over finite horizons. Management Science, 40(8):99--1020, 1994.
[13] Robert Gentleman and Charles J Geyer. Maximum likelihood for interval censored data: Consistency and computation. Biometrika, 81(3):618-63 623, 1994.
[14] Sébastien Gerchinovitz and Tor Lattimore. Refined lower bounds for adversarial bandits. In Proc. Neural Information Processing Systems, 2016.
[15] Subhashis Ghosal and Aad Van Der Vaart. Convergence rates of posterior distributions for noniid observations. Annals of Statistics, 35(1):192-22) -231992-22222222 2007.
[16] Subhashis Ghosal and Aad Van der Vaart. Fundamentals of Nonparametric Bayesian Inference, volume 44. Cambridge University Press, 2017.
[17] Negin Golrezaei, Adel Javanmard, and Vahab Mirrokni. Dynamic incentive-aware learning: Robust pricing in contextual auctions. In Proc. Neural Information Processing Systems, 2019.
[18] Piet Groeneboom. deconvolution. Technical report, Department of Statistics, Stanford University, Stanford, California, 1991.
Nonparametric maximum likelihood estimators for interval censoring and
[19] Piet Groeneboom and Kim Hendrickx. Current status linear regression. Annals of Statistics, 46(4):1415-1444 2018.
[20] Piet Groeneboom, Marloes H Maathuis, and Jon A Wellner. Current status data with competing risks: Limiting distribution of the mle. Annals of Statistics, 36(3::00441189, 2008
[21] Piet Groeneboom and Jon A Wellner. Information Bounds and Nonparametric Maximum Likelihood Estimation, volume 19. Birkhäuser, 2012.
[22] Pavithra Harsha, Shivaram Subramanian, andine Uichanco. Dynamic pricing of omnichannel inventories. Manufacturing & Service Operations Management, 21(1):47-65, 2019.
[23] Adel Javanmard. Perishability of data: Dynamic pricing under varying-coeffiiiet models. Journal of Machine Learning Research, 18(53):1-31, 2017.
[24] Adel Javanmard and Hamid Nazerzadeh. Dynamic pricing in high-dimensions. Journal of Machine Learning Research, 20(9):1-49, 2019.
[25] Nicholas P Jewell and Mark van der Laan. Current status data: Review, recent developments and open problems. In Handbook of Statistics, volume 23, pages
Elsevier, 2003.
[26] Robert Kleinberg and Tom Leighton. The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In Proc. IEEE Symposium on Foundations of Computer Science, pages 394-605, 2003.
[27] Xiaoyan Lin, Bo Cai, Lianming Wang, and Zhigang Zhang. A Bayesian proportional hazards model for general interval-censored data. Lifetime Data Analysis, 21:470-490. 2015.
[28] Jane C. Lindsey and Louise M Ryan. Methods for interval-censored data. Statistics in Medicine, 17(2):219-238 1998.
[29] Wenting Liu, Huiqiong Li, Niansheng Tang, and Jun Lyu. Variational Bayesian approach for analyzing censored data under the proportional hazards model. Computational Statistics & Data Analysis, 195: 107957,,, 2024.
[30] Yiyun Luo, Will Wei Sun, and Yufeng Liu. Contextual dynamic pricing with unknown noise: Explore-then-us tucb-ucc strategy and improved regrets. In Proc. Neural Information Processing Systems, pages 37445-37457 2022.
[31] Yiyun Luo, Will Wei Sun, and Yufeng Liu. Distribution-fres contextual dynamic pricing. Mathematics of Operations Research, 49(1):999-61) 2024.

---

[32] Chandrasekhar Manchiraju, Milind Dawande, and Ganesh Janakiraman. Multiproduct pricing with discrete price sets, Operations Research, 70(4):2185-2193, 2022.
[33] Sentao Miao, Xi Chen, Xiuli Chao, Jiaxi Liu, and Yidong Zhang. Context-based dynamic pricing with online clustering. Production and Operations Management, 31(9):3559-3355 3575, 2022.
[34] Velibor V MiSić and Georgia Perakis, Data analytics in operations management: A review, Manufacturing & Service Operations Management, 22(1))158-169) 2020.
[35] Chun Pan, Bo Cai, and Lianming Wang. A Bayesian approach for analyzing partly interval- censored data under the proportional hazards model. Statistical Methods in Medical Research, 29(11):3192-322 3204, 2020.
[36] Sheng Qiang and Mohsen Bayati. Dynamic pricing with demand covariates, arXiv preprint arXiv:1604.07463, 2016.
[37] Virag Shah, Ramesh Johari, and Jose Blanchet. Semi-parametrie dynamic contextual pricing. In Proc. Neural Information Processing Systems, 2019.
[38] Xiaotong Shen. Linear regression with current status data. Journal of the American Statistical Association, 95(451):842-852)) 2000.
[39] Kalyan Talluri and Garrett Van Ryzin. The Theory and Practice of Revenue Management, volume 68. Springer Science & Business Media, 2006.
[40] Inder Jeet Taneja and Pranesh Kumar. Relative information of type csiszár's f-divergence, and information inequalities. Information Sciences, 166(1):105-125, 2004.
[41] Runlong Tang, Moulinath Banerjee, and Michael R Kosorok. Likelihood based inference for current status data on a grid: boundary phenomenon and an adaptive inference procedure. Annals of Statisties, 40(1) 40(1):45-72, 2012.
[42] Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer New York, NY, 2009.
[43] Mike Mingcheng Wei and Fuqiang Zhang. Recent research developments of strategic consumer behavior in operations management. Computers Operations Research, 93:166-1777 2018.
[44] Jianyu Xu and Yu-Xiang Wang. Logarithmic regret feature-based dynamic pricing. In Proc. Neural Information Processing Systems, pages 13898-139100 2021.
[45] Yun Yang. Debdeep Pati, and Anirban Bhattacharya. a-variational inference with statistical guarantees. Annals of Statistics, 48(2):886-905, 2020.
[46] Fengshuo Zhang and Chao Gao. Convergence rates of variational posterior distributions. Annals of Statistics, 48(4))2180-2207 2020.
[47] Haiming Zhou and Timothy Hanson. A unified framework for fitting Bayesian semiparametric models to arbitrarily censored survival data, including spatially referenced data. Journal of the American Statistical Association, 113(522):57-5588 2018.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introdeution clearly state the contributions. These claims are supported by both theoretical analysis and numerical experiments.
Guidelines:
12

---

The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitation that regret lower bounds are drived only for the non-contextual pricing, and the dependence on the dimension d is not addressed. The need for future work in this direction mentioned in Section 5.2
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All iassumptions required for the theoretical results are explicitly stated the paper. Most proofs are provided in the appendix, while the main theorems, key lemmas and insights are included in the main body.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
13

---

All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The implementation details of the proposed algorithm are described in Section The experimental setup and hyperparameters are provided in Section and Appendix H
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All code necessary to reproduce the numerical experiments is included the supplemental material.
Guidelines:
14

---

The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cc.
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https Cww.eauumissioooooooo...oooo
7/nips. //wpss.ccppb..i... wttc//ublicggggucce
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if' applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide the detailed experimental settings including how cumulative regret is computed and the hyperparameter configurations in Section and Appendix H
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The experimental results are obtained via repeated trials, and error bars are shown and explained in the figure and this caption.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
15

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide the computational resources used in our experiments in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We have carefully reviewed the NeurlPS Code of Ethics and confirmed that our research does not violate any of its principles. All numerical experiments are conducted using simulated data, and thus this work do not involve any human subjects or data-related concerns.
Guidelines:
The answer NA means that the authors have reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper focuses on thcoretical analysis of regret bounds in contextual pricing, and does not have any direct socictal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: This paper is theoretical and conducts experiments solely on simulated data. No high-risk models real-world datasets are released.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.paaeesstt
package should be provided. For popular datasets, paperswi thcode. cow/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
19

---

Appendix
We begin this appendix with proof roadmap that outlines how the main lemmas and theorems are logically connected. The roadmap provides a high-level overview of the argument structure, highlighting the key intermediate steps and how they contribute the main convergence and regret results. This overview is intended to enhance clarity and to guide the reader through the subsequent detailed proofs.
Lemma A.6
Theorem 3.1
Lemma A.7
Theorem 3.2
Lemma 5.1
Lemma C.5
Lemma B.2
Thenrem 5.2
Lemma C.2, C.6, C.7
Lemma B.1
Figure 2: Proof roadmap summarizing the logical connections among lemmas and theorems leading to the main results.
A Proofs for Section
In this section, we first establish the posterior consistency of the Cox PH model, which serves as a foundation for proving the main theorems in Section 3
Lemma A.1. (Posterior consistency) Suppose that the grid resolution satisfies ô = kn 7 for > O
and y E (0, 1). and assumptions (Al) (A5)hold If < 2/3, then, for every e >> 0, there exist positive constants C₁ C2 and C3 depending on (L, B. Pmin Pmaxo K, a. a, E) such that
I1(UE DD)) < Crexp(-Can), 2 Ct,
(8)
where
U U= 0 E θ |So lo V -1BB-311 <c}
(0
with Pg- -probability at least
exp(-CCrn)
If 2 2/3, then, for every e > 0, there exist positive constants Cq, Cs and C6 depending on (L, B, Punin Praaxs Ki Q Ot P. such that
ITUE DT) < exp (-Cond), n 2 C4:
with Pg. -probability at least eexp(-Con1/))
Remark A.2. As discussed in Section 4 the conditional distribution of posted prices Q(- X) is
parameterized by the policy. By allowing uniform sampling at a rate TjI, defined (6), the policy constructed in (5) satisfies (A4) Strengthening assumption (A4) to the more restrictive condition
q(g r) Z n (log n) 1/2 for E G and E X' when 2 1/3 yields the same results as in (8) for all 7 E (0, 1]. In such case, 17 can be adjusted accordingly to satisfy this restrictive condition. However, increasing 7) leads to higher regret due to increased exploration. Therefore, imposing weak condition, as in (A4) essential for achieving a tight regret upper bound. For further details, see the proof in Section B.2
Pt,Y,) Yi) is expressed as: To begin with, for given parameter 0 = (So, 3), the joint density ps of (Xe, Pt,
p= p.y) = {So(p)=)}) {1 Se(pl=)) ((pp)))xx()))
for x E X. 9 and y E 1). where Sp(p æ²) (xp) 00 and X' denotes the support of the covariate X. Here, we suppress the dependency pa on the nuisance parameters, as they do not affect the inference of once an independent prior is used. The likeliiodd function corresponding to for the data D,, = ((X,, Pt, Y)) is given by:
1
(0)
Σ
log po Pt, Y.).
20

---

A.1 Proof of Lemma A.1
Lemma A.3. Under the conditions of Lemma A.T there is an exponentially consistent sequence of tests for
Ho 0 -SS; }"
H1 0 {(So: 3) E Rd 1--1111--0 - - 2 n)
for any 1) > O.
Proof. Suppose that y < 1/3. Let Tn denote the set of every disjoint pair of index sets I and 12 such
that 1 U1 [K]. Given an index set I S [K] we denote the subset of G corresponding to by
g(I) = {9k E k I]. For each (4, 12) E Tn. define So 12) := {So = (Su.1...... So.........kk E
So : So,; 2 S0.::S... < SJ for / and j E T2). We define the quadrant Qe {2
R² :aje > 0, Vj 1, ... for each e = (el....,Ea) E4) E {-1,1]4, For j = 1,..., d. let
elit, Nittee"- E (- denote the vectors where j-th element positive and negative, respectively.
Consider the following two groups of hypotheses for each (21, E Tn and e e (-1, 1-, 1]dd
with = d,...,d,
Ho 0 = (Sq, (*),
H1 11:06 Oe:
(9)
Hn 0 = (S:: B*),
Hi 0 E ,eht,
(10)
where Oci So 12) {3 E R& : :3 2 B, + 3 Qel--), aesit.
So(I. {B E Rd :3 2 83 + 3 3" {Qa--) and { = = n/Vd.
Fix arbitrary j L,...,,, ed- edit {-1, and (41, E Tn. By Lemma C.4 take constant e > 0 such that [P( > e) > 0 for all j I,..., ,, given data D. = (r,,P. P..Y... For the first group of hypotheses 99, define function Φ1 = max 212). where (D.)
1(x, E Q_ah-.
> Pc G(I)), Y2 = 1} and (1,((D;) = 1(X, E Qai., |X,, >
P. ((
0}. Under the event G (X, E Q-at-, |X,s] > P,P, E g(l1)).
for any 0 (So, B) Oci D.. we have X, B < X2 3 - ef. This implies exp(X, ()
exp(X, 8*) exp( (c) Then, the event Q2, we have
So exp(XT Ø) 2 (p >
81) exp( (p B*) A1.
where the last inequality holds because of the mean value theorem and assumptions (A)) (A2) and (A5) with positive constant As depending on M1, M2, L, B, and &. Let gn
(1+m//2 (log n) 1/2. L//2. By assumption (A4) we have g(p x) Z t. for all E X' and p E g
when 7 < 1/3. Then, for any 0 = (So. 3) E Oei-Jh.d we have
Es (0).1 Ex,,
So(P)) (xPP) (x 1
exp)) XX. 101101111 + Ex..P. [A,1
> Ex.P P.
2 Eg- ( IT
where C1 be positive constant depending on Fx and e. Similarly, under the event 22 {X, e Q > P, E G(12)), for any
(So, 3) E Oai we have exp(X, B) >
(x, 8*) expleE). Then, on the event 92 we have (p,))) < (P.) B) <
S5 (P)) (xPjexp(XXTT (1) explec) < S exp( 8*) A2, where the last inequality holds because of the mean value theorem and assumptions (AT) (A2) and (A5) with a positive constant Ag depending (AT)
on M1, M2, L, B, e and E. Then, for any 1 (So. 3) Deiia we have
Es (01.2 = Ex,.P. (1-So(P)) (xP(XT ()) 1(
[11
5% (xpp)xx((X 87) 1(02)} + Ex.PP [121
> Ex..P
2 Eg- (0 (Dr)) + C2D2lT2l4. Am.
21

---

Define the tests as where C2 be a positive constant depending on Px and e. Combining the last two displays. we have
Eg | (Dr)] Eg ( + Es (
Eg. 11, [D:) Eg- 2 D.)] + Cin(CCA,,CC22)) + 121)g
(11)
Eg- ( [P)] + qa:
where C3 be positive constant depending on C1, C2 A1. A2, Punin Pmax and Define tests as follows:
Ba- (D;))) + Eg 10 (P:()))) }
N1. 11,1 (Dn) = 1
Σ $1 >
1=1
Then, we have
Eg 1 et- 11 (D,)) = P...
(ol (D+) - -Eo- (0b] (D:)))
>
Σ
(Bo 10b (Di) To- (<r (P+)))/
t=1
< p..
Σ (ib) (D.) - -eo (D.)) >
Czn 2
exp
where the first inequality holds by [1 and the last inequality holds by Hoeffding's inequality. On the other hand, applying Hoefiding inequality Φ1 (Dt),
sup E Dei- (D.)]
sup
PR
(D.)) - (1 E. (o (D:))) ((1 (1-dr(D.)).
Σ Es (or (D.) - Eg- [ (D:)))/2
sup
p
Σ ((1 - 11 (D.)) (1 E. | (D:))) n (C
C2n nn
1+27
In
exp
2
where the first inequality holds by
III.
The construction of tests for the second group of hypotheses follows:
TTp is similar.
n
n
eit 11 (D,) ==
Σ (D.
Σ (Eg- 1d (D.) + E, (6 (D.)1)/
where 02 max 02.2) is a function with 62,1 (D:) 1(x, Q -zitt t, |Xt,jl > c, Pt
((1),, Y 1} and 22 Di) = 1fX, E Qeit, [Xt,j] > P. E ((1)), Y, = 0}. Similarly, we see that
Ep a 12 (D.)) $ cxp
2 Can
1+2
q
sup
E - 4 -1,12 (D.) < exp
6E0 .. d2
2
where C4 be a positive constant.
Note that the union of the sets in the alternative hypotheses 9 and 10 for all (71, I2) E T, and
elit, ehー E 11, with j = 1.....d d contains Q == {(S,, 3) So x IRd || 80112 2 n)
We set P := max( - {(-1._)_) (
.elit, then we have
Ep. c (D,,)] )] S d2 exp (-Cnn g
s exp (Cod V n² Csn + gm))
sup E P. (D,)) exp (-Cn 142 (2) #ce,
22

---

where C3 = min for fixed d, by the definition of On we have Eg. [ (D.)] + and suppee, Egg [1 p, (D.)] + as n + oc. By Lemma D.1I of [ō]. there exist tests Vn and constant C7 > 0 such that EZ (D.)) S
and Cg be positive constant depending on Paiin Piax and k. Then,
and s Eg[1 - (D,)) I exp(-C7n)
Suppose that 7 2 1/3. Recall the grid support G = {9k k = l...., K}. where each grid point Ike is defined as gk = Pmin + kō with ó kn 7 for some constant K > 0. Let en n-1/3 and J = [pmmax= Pmiin/ I- Define (K1..... ku)
subsequence of [K] such that J - 1, and set k. = K. + 1)Ken < Oh; S Pmin - (j 1)se, + 8 for j = I.....JJ
Pmin + -
Let T, denote the set of every disjoint pair of sets If and 1/2 such that I 12 = [J]. For each (K, [22 E Ty, define
So [2) = (S. = (So. ko.k) E : So.. 2 So So,k, < So,, for E Ij and j E 12).
Consider the following two groups of hypotheses for each [2) E Tu and ei+ -i E f 13 j = l.....d.
He : 0 (S%
H1 :::0 -
(12)
Hg : 0 (S) 8*).
H1 : A E O.t+,1.112.
(13)
where a J, = So(11,1)) x {3 E R- : 35 2 B5 + E, - 3" E Qus h. Oeitt
-
=
So 12) x (3 E Rd : 2 8] + -3 EQr } and { = =n/vo.
Fix j = 1...., d. , E (-1,1) and (T, 12) E Ty. Define the index set between &y and k
as I, {k: E [K] k S < k441 for = 1, I....,J J - 1. We define partitions I1, Iz, Iy and Ia of
set
by
I = { i 1, ,,..,, J- 1: So 2 Sü, Su 2 So J:
[2 = { 1, J,...,J-- J- 1: So < Si S0 < &oo,k;111
I3 = {4, i 1, J...,J-11. 1: So,k. < So Su 2 So }
4- = (T, i = 1, 1,...,J-- J-1 1: So 2 Sū,k. So,t211 < So ).
Note that for any 1 E I, there exists a unique /' E I such that S 2 So,k' and So, < 5
Thus, given I E I4, we can define 7 (k E / h S k} and [ -= (k E I k: > k3. For the first group of hypotheses (12). we define function d3 max(cs,11 03,2 03,3, 03,1, Φ3,5 where
2 (D.) = 1(x, E Q- X > e, P. E
U G(T), Y, = 1},
JEZ,
(D.) = 1x, E
> c, P:
P.E
V G(T,, Y: = =0,
IEL,
(D)) 1(X, E Q_ |X, > P.
V G(I),Y,
TETs
(D)) 1(X, E Q- X w > 2 P.
U ((T),Y;111 1},
IEL,
(D,) 1(x, E Q |X, > c, Pt E
U G(I) Y2 = 0}.
TET
Note that under the event P3.1 == (X+ E EQ- 1X,rl > e, P. E Urez, (( for 0 = 3). E Ogi R.Y. we have (x, 3) < exp(X,, 3r) exp(- For any 1, E In and k E 1, we have
So $ 2 Su So. + Su S
2 -ookeen +5)
2 Lo
23

---

where the second inequality holds by the definition of I1 and 75, and the last inequality holds because 8 f En for y 2 1/3. Then, on the event S3,11 we have
So(P,)ox((X7*) 8) So(P.) exp(-rE)
2 (P:(P) - 2LOKEn jexp(X) 8*) exp(-eE)
> (P)) (P) X? expp Catn
S (Pt) pxx))p(( B*) +AI -CEen
(P.) + 11/2
where the first inequality holds because exp B)
exp 3*) exp(-cE), the second inequality holds by the preceding display, the third and fourth inequality holds because of the mean value theorem
and assumptions (A1) (A2) and [A5] and the last inequality holds for sufficiently large n such that
en (2Cs) Let 9n
173 (logn) By assumption (A4) we have q(p 2)) 2 do for all
x X and p E G when 7 2 1/3.
Then, for any 0 = (So. 3) E O J.. we have
Eolos,1 (D,)] Ex P
9) 1(2 So((P) (s6(P))00XPP))1001111
Ex..R (P:) (opp))xpp((]3 87 (( A1/2 Ex,, (1
103. (D:)) + Co [ Ko
where the second inequality holds by the preceding display, and the last inequality holds with a positive constant Cg because [T:] 2 K/J for all 1....,J J 1. Similarly, there exist positive constants Cio. C11. C12 and Cia such that
Lo (Pt)) Eg- (60,2 D.)] + Cio [2 ///h//
Es Eolos,3 (D.)) Eg- |0 [D)] + Cn Kg///
Eol Eolds,a(D:)) Eg- | (D:) + C12
[
TET4
E Eelos,, > Ee- (d,ss((D)) + C13
I
IEZ.
Combining the last two displays, we have
Eg (o()) =
Ee (
Eg- (b.)), C1a ( +ZI++1I++Za)
(Za) K Σ (17) + 111g%
IEI4
Eg (db,, (D.)) C1+ (Zil+ + I2l + [Tl + Inl) Kgn/J
Eg (D,)) + Cis
(14)
where the second inequality holds because inequality holds because [[] + Izl + Izl [al J. Define tests as follows:
[T| + 11 = 7 2 K/J for all T E I4. and the last
$ S 11 R113 (D.) = 1
Σ 2z (D.) >
(Ea- (D.( + E. (gx (D.))//2
24

---

By Hoeffding's inequality and 14
we have
Egg De. Ri.4 (D.)) (D)) S Po-
(os(Di) - Es. (os( > (())3
Cssntt2 qm
S exp
Cisn C25nlt20gh go
sup BE0 -
Egg [1
[I. S exp
-9.12
The construction of tests for the second group of hypotheses follows:
13) is similar.
Define the tests as
$ ei 11,11 (Dn) = Σ (D.) > Σ
(Eg- (o. + Es (D.)11))
1=1
where 04 max 04,2, P4,3, as,4: 04.5} is function with
(D,) 1(x, E Q- et X e,
U Y. 1},
IEL,
(D,) 1xx, E Per | > c, P. E
U g(),, 0),
IEI,
(D, 1(x, E Q ai X1,) > P, E
U G(I), 1},
TETa
X1,1 > P, E (D)) = 1(x, E Q + Q
U g(), Y, 1},
IEL
(s,((D)) 1(x, E Qa P U
G(I) = 0}.
TET
Similarly, we see that
Eg. 1 11.15 (Dx)) exp
2
sup
E
1 ol 11,11
(Dx)] < exp
SE0 .g
2
where CIe be a positive constant.
Note that the union of the sets in the alternative hypotheses 12 and 13 for all (I, E Tu and
elit, e E 1] with j = 1,..., d contains O,, = ((S,, 3) E So x IRd ||.3 - 1/--1112 2 n).
We set T
( -P 1 , .R. ]. then have
Eg. [ (D.,)] s 2 exp (-Cirn 122 (h2)
Cisd V n C17m2t27 6/
S exp
sup E3 1 - '', (D.,) < exp (-17 122 (2)) 8E
where C17 = min min/C 02 and Cis be a positive constant depending on Pmin Pmax and
Then, for fixed d, by the definition of dn we have Eg. $ (D,)) -> 0 and supage, E2 [1 '' (D.)) + as n + oc. By Lemma D.11 of [16). there exist tests V and constant C19 such that Ez. [ (D..)] < exp(-C110 and supsee, B V (D,)) S exp(-C19n). The proof is then complete.
25

---

Lemma A.4. Suppose that the grid resolution satisfies ö = kn kn for > 0 and (0. (03)/ and
assumptions [A]) [A5] hold. Then, there an exponentially consistent sequence of tests for
Ho: 0 = 8"),
H1 0 e {(So. B) So Rd ||8, oo 2 m, 113 112 123
for any vn
0 and sufficiently small 1/2 > 0.
Proof. There exist constants M1, M2 (0, 1) such that M1 < Sg(e) I M2 for any e [Pain Pmax under assumption (A5) We choose 7/ to be less than min M2, M1} to ensure that {So- E Sp:
|So Si m 7 6. Consider the following two groups of hypotheses for each k E [K].
Ho 0 (S), 3r),
(15)
Ho 1o:00 0 = (S,, 3*),
H1 :0 1 Ox,
(16)
where 2R.1 = (So, 8) E So x R So, 2 S² + m. 1| 8*112 < m2 and OR.2 = ((S,, 3) E
So Rdd So, S S.. 71, || 1|2 72).
Fix arbitrary& k E [K] For the first group of hypotheses 15 define function Φ1 (D:)
I[P: - gb. Y, 1 For any 3 such that ||3- 31 < 1/2, by the Cauchy-Schward inequality and the assumption (A2)
X, (3 3*) S || - 1/1 < Lap almost surely. This implies exp(X, B) < exp(X, 3 exp(LT2) Then, for any 0 (So. 3) O we have
So exp(X (x, 8) (S + ) pxxp( (oma) exp( x, 18))
is easy to show that there exists a positive constant Cj depending on M1, M2, L and vn such that Gi S log log((S,, 7/1 0n/2)-11 log log((S m))- for any Si,e [M, M2). If we choose
sufficiently small 7/2 such that Lnpa < C₁ we have (S² + m)) eexxp(m)))) 2 S + m /2. Combining this with the previous display,
1/1 exp(XX 8*)
S exp(X 3)
> S + 2 S exp(X, 8*)
2
+ C2.
where the last inequality holds with positive constant C2 depending on M1, M2, L, B and m by assumptions (A1) (A2) (A5) and the mean value theorem. Then, for any 0 = (So. B) E Og,1 we have
Eg 10 (D:)) = Ex.P.
(o(P))opp(2 18) 1(P; = gxb
> Ex...
(P)) 8*) 1 = 9x) + C29(9k)
(17)
Eg- (0) (D:)) + C2g(ge).
In addition, for either 0 Ox.1 0", we have
Vare (D.) (g(2) = Ee (D()) (1 Eo (oi.))))
S Eg (0) (D.)
(18)
= Exx,P. [Px())exp)X A L(P: = gu}
< <((());
where Vars is the variance with respect to the distribution Pg. Define tests follows:
LN (Dw) = Σ b (D.)
Egg (o,(D)) + E. 16 (D.))/2
26

---

Then, we have
n
9 P
[Dn)] Pg-
Σ (Di) Eg- 101 (D:)))
Σ (Eg 101 (D:)l Eg. [01 [ox(D:)))22
Σ (Di) Eg. (01 (D:))) - ng((s))
< pg
(C2/8)nn2g(gz.
S exp
EE Varo- (D;) - Eg- (0 (Dt))) + (C2/6)na(0))
S exp ( C3n9(9x))
x exp (- C(ngg))
(19)
where the first inequality holds by (77 the second inequality holds by Bernstein inequality, the third inequality holds by (18) with positive constant C3 = C2/(8(1 + C2/6)), and the last inequality holds because (p)) 2 9n with
n + (log n) n nーーー- (logn) n)
if
On
if 2 3
under the assumption (A4)
On the other hand, applying
I7 (18)
and Bernstein inequality to
1 Φ1 (D:). we have
sup F3 [1
k (D.)]
o
sup P
Σ (1 (1(D)) (1 Eo 101 (D:)))) 2
Σ
(Bo (oi (D.) Ee 101 (D:)))22
C2
sup Fe
Σ (11-b)
Eg (61 (oi(()))) 2 ng(9x)
(C3/8)n²2((aa)) )a
sup exp 0
Σ Var (Eo (oi - (D.)) + (C2/6)n4(a
exp ( (- CCngg(a))
exp (-C4nga).
(20)
The construction of tests for the second group of hypotheses (16) is similar. Define the tests as follows:
(x,) 1
Σ
de (D.)
Σ (E.. [d2 (Di)) + Ea (d.)(1
1=1
where d2 (D;) = L(P: = 9k. Y2 = 0} is function. Similarly, we see that there exists positive
constant Css depending on M,, M2, L,, B, mn such that
Eg. $ (D,)] < exp(-C3ng.)
sup E 0EE..
(D.2(D.)) S exp(-Csnqu). (21)
Note that the union of the sets in the alternative hypotheses
15 and (16) for all 1,..., K
contains O va = {SS,, B) E Sp x Rd
S
Sill 2 Yh 8r 12 n2). We set th =
(aX p V (P.2). Combining 19
20 and 21 have
E
D Dn)]
K exp (-Csng.))
exx (log K - Conqn),
sup E (D..) exp (-C6n)))))
where Cs
min min,Ca,Cs) By the definition of qus we have Ey. ( (D.)] + 0 and supace..... [g D, (D.,)
0 as + when 7 < 2/3. By Lemma D.11 of [16]. there exist tests V, and a constant C7 0 such that By. [V, (D.)) S exp(-C7n) and suppce. EB [1 V, (D.)) exp(-Crn). The proof is then complete.
27

---

Lemma A.5. Suppose that the grid resolution satisfies ô = kn " for K > 0 and E [1/3. 11. and assumptions (AI) (AS) hold. Let = n. 1/3 and J = [P Punin) [ Define (k).... k2) as
a subsequence of [ such that Puiin + (j - 1) ssc < 9k, S Pmin + [j lic + ō for
and set kj- = K. Then, there is an exponentially consistent sequence of tests for
Ho 0 = (S 1*),
H1 0 {SSo, 3) E So X R
max |So,A, 25/5J-1
So.k, 2 71.133 B*1 < m3
for any ?i > 0 and sufficiently small n2 > O.
Proof. We consider the following two groups of hypotheses for each j 2, ..,,,,,
Hn 0 (8);8");
H1 11:00 E θ
(22)
Ho : 0 = 8*), H1 : f E 9,,2
(23)
where ,,,1 {SS0 3) So x Rd Sa,s, 2 S + +m; 33'12 < 1/2) and 0 {(So (3)
So x I= So.k, < So,, - 71, 3| - 12 < 12). Define the index set between kj and kj+1 as
1 { E [K] K2 k S ) for j 1, L.....JJ- 1-1. Given an index set I S [K], we denote the
subset of G corresponding to / by ((1) = {gt E E El
Fix 2, JJ 9(I,-1), 1}. For any E , and & E 1-- we have
JJ 1. For the first group of hypotheses (22
define a function Φ1 (Di) = 1(P:
So Sü 2 ko,k; Sū.k, Sü.k, Sü.
IV IV IV 2 m Lolgk; - gk
m Lo(ne 8)
7h 2
where the second inequality holds because A E ,,, and Sj is Lo-Lisschizz continuous under the assumption (A5) the third inequality holds by the definition of (k....., ky), the fourth inequality holds because ò S Ke when 7 2 1/3, and the last inequality holds for sufficiently large n such that e S m/ 0n/(4Loot (4L))). By similar argument as the proof in Lemma A.4 for a sufficiently small 1/2, there exists positive constant Cj depending on M,, M2. L, B and mn such that for 0 = (So, 3) E θ,, and & e 1/-1.
Su.k exp(X. B) Sü exp(X] + Cz.
Then, for any 0 = =So, 3) E H2,1, we have
Es [6) (D:)) P. S (a(P))xx(XXT1111 11 ((P.e
St (P.) exxp)) px 11 ((4)11)} + C1 Σ g(gh)
> Ex..P
kET,
= Eg (. + Σ 4(xx).
kET;-1
In addition, for either 0 E 9, or 0 = ,", we have
(a (D.) - (e (D.) Eo (0) (D:)l (1
Es (D.)))
< Io [0i (Dt))
Ex..P [Po()))s 8) 11P ((4+1))
Σ a(gx).
kel;-1
Define tests as follows:
$ D (D,) = 1
Σ b1 (D,) >
Σ
Egg- (6 (D.) + E, (h (D.))/2
[=1
28

---

Combining the last three displays, by Bernstein inequality, we have
Eg- (ob (D:))) > C1 n (D.)
Eg..
s g.
Σ
Σ dlk)
1=1
kET
(Cq/8) (2 a(gx))²
S exp
Ei= Varg- (01 (D:) Eg. (D:)) + (C1/6)n LkEl,-, g(gk)
S exp
Con
Σ ((gx)
kEIs-1
S exp
(-C3n|li-1lan
< exp 3C3n (gm))
(24)
where C2 C)/(((1+ /6) be positive constant, the fourth inequalith holds with positive con-
stant Cg depending on Cg and q-) because q(p) ž 4n. for any p 9 with Qn 1oog n) 1/2
under the assumption (A4) and the last inequality holds because [r K/J 2 n for any
j = -I....,,-- 1. Similarl, we have
sup E (D,)( S exp (-Can
(25)
The construction of tests for the second group of hypotheses 23 is similar. Define the tests as follows:
(D)) (D,) = 1 Σ De > Σ (Ee- [dz(D.) + Es (o2 ① 122
(26)
(=1
where 62 (D,) = I(P E G(T,), 0} is function. By a similar argument as the preceding, for any 0 ,2 k J,. and for sufficiently large such that I m m/ we have
Sü So. 2 S Sö,,, + SO,,, So, 2 Lo Iky | m 2
By a similar argument as the proof in Lemma A.4] for sufficiently small 1/2, there exists a positive constant C4 depending M,, M2. L, B and mh such that for any A O
Eg (D))] > Eg- [oz(D.) + C. Σ ((ox).
KET
In addition, for either 0 , 0 E 0*, have
Vara (d2((:)) - (s (D.)) < Es (o2(
= Ex..p [[1- (o())) B)) ((P))())))
g(gh).
kEI, Combining the last two displays, by Bernstein inequality, there exists positive constant C3 depending on C4 and (()) such that
Ez- [ (.2.. S exp (-Can 3q.).
sup #E0,,
E
(D2(( S exp (-C3n(+3q.) (27)
Note that the union of the sets in the alternative hypotheses contains O, ni := (So. 3) So x Rd max |So.;;
(2 and
23 for all j = 2, ..,
Si
N m || 3* ll2 < m.). We
set Φ,, max25)5s-1 B,, V t j.2). Combining 24
25
and
(27
we have
E o (D.)) exp
7
(log J C
=
sup E D. (D.)) exp
-Contt8qu)
0 12
29

---

where Co = min Cst. By the definition of On- we have Eg- (D.) + 0 and supaee m.
as + oo when y 2 1/3. By Lemma D.11 of [6]] there exist lests ,n and a constant C > 0 such that [V (V,.(D)) S exp(-Cyn) and suppee,,.
E [1 p, (D.)
E [1 vn (D.)] exp(-Crny The proof is then complete.
Proof of Lemma A.7 We proceed with the proof by considering two separate cases: Y 2/3 and 7 2 2/3. First, we suppose that 7 < 2/3. Let 6o > 0 be a constant to be chosen later, and define Oo {(So. (3) O Ag Ao V ||3 3 la I co). Here, Ag (Ao. A,, and
A = -A Aj.x) are K K-dimensional vectors corresponding to So and Sj. respectively, such that Ap, = log S and A = log S for = 1...., ., K. The log-likelihood ratio satisfies
P8+
Ho (x, + (1 - y) log 1 (x,p) (x, p.y) = y log Ho(r,
1 Hg. (x.p)
log
Pa
log Ho- (x, p) Ho(
log 1 Ho. (I1, p)
max
Ho(r,))
By assumption (A5) there exist constants Mn and M2 such that 0 < M1 S S (Piaax < S (Pinin)
<
M2 < 1. Note that for 0 E @eo where co S (M, (1 M2)/2) B, we have So(1) (v) E
[M /2, (1 + M2] for any E [Pmin-Pmax/] Pmax] and ||||| < 2B under assumptions (A1) and (A5)
Furthermore, by assumption (A2) both Hg. pz) and He(x, p) are bounded away from 0 and for
any X, G and 0 E O.o. Since |log p log gl S 1p- max(p= .9 for any 0 p.g < 1,
we have
pa- log Pe
Holl Holboo
(28)
00
where Co is a positive constant depending on M1, M2, T. and B. In addition, by Lemma C.2 there exist positive constants e1 and 62, depending M1, M2, I. and B, such that for any X and p E G.
Ho (x. p) - Ho( p) S cı S lo + 02 -8"12
<a Ao Ajl + c2113 3-112.
where the last inequality holds because So. - 00 < Aa - Aállo Combining the last two
displays, for 0 O.g. we have K (pe- pe) S [log(pe /po) oo < Cleo. where C₁ Colci + 02) is a positive constant. Then, we obtain
+ ca S (0 E : K (por, po) < Ciea
(29)
We denote the renormalized restriction of II to O by II We note that
II Po pg.
(D,)dI(()) > 11(()..)
II_
po (D.) (0)
A..
t=1
po-
(30)
I......) exp
log
pg-
(Di) (0)
1.0 t=1
pe
where the last inequality holds by Jensen's 's inequality. Since the log- likeelhodooo ratio is bounded from 28 by Hoeffding's 's incquality, we have
PR
Σ
log
Po-
(D.) n (po- SoPo-.Po) < con
> >1 - exp (- (- 20%
(31)
Pe
Let Ω2 be the event in the left-hand side of the last display. Thus, on the event Ω2, we have
log
Pe-
(Dr (Di)dILe (0)
nK po [dIle, con
po
1=1
> - (C + 1)com,
30

---

where the last inequality holds by 29). Combining this with (30, on the event Q2, we have
Pe
(D))
(1( exp (-(Ci + 1)oo)..
(32)
Po
Let e1 con By Lemma
C.3 with the specified prior 33 and the hyperparameter condition (P2)
there exist positive constants C3, and cs depending on Pmin Pmax, M1, M2. a, a, p and Eo, such that
(I - ~b S <1) 2 c3 cxexp(-ca oz c log- 61)
In addition, under the prior condition (PI) we have I[[]] - l* S en) 2 C2. where C2 a postive constant depending on d, en and the lower bound of the prior on neighborhood of 3r. Then, we have
II ..))) I[I - Abllo cu) I[[] 12
2 C2cyexp(( exp((ccpK - cs log_ K)
where the last inequality follows from the previous display and the fact that e1 S 6n for 2 1. Combining this with (32). on the event f2, we have
/
(D.) C2e3 exp (-caK log_ KK (C1 + 1)eon)
Po
> C203 exp (- (-CcK
(C1 + 1)con),
(33)
where the last inequality holds by C3 = 64 + 0s (log_ fo + 1) because log_ 61 < log co + log n. A.4 there exist tests 4n such that
By Lemma
A.3 and
E- [p,] S exp(-C,n),
sup
EB [1 pn S exp(-
(34)
BEU
where C4 a positive constant depending on M₁. M2, L, B, Pmin+ Pmaxi and Then, we have Ez- [I(UT) D..) < Eg- [ + Eg. [(1 t. ( D., 1 + IPg. (22)
c
Eig [ (C2ca) exp (C2K (ogKlogn + (C1 + 1)eon) sup EB [1 Dn + exp DEU
208
S <xxp(-Cnn) + C3 exp C3Cpn log (C₁ - +C1+ + 1))o)m))))))) + exp (-Con),
where the second inequality holds by 31 and (33 and the last inequality follows from (34). with Cs (C2es)=1 and C. = (2C and K < Cpn2/3 for < 2/3, where Cp is positive constant depending on Pmin= Pmax and k. We choose cu (C,/(3(Ci + 1))) A ((M, A (1-M2)/2)
B) to ensure that the second term on the right-hand side of the previous display is bounded by Css (xpp(((a/3))n) provided that n (log))) n) 2 3CtCp/ Ca. Then, we have Eg- [M(()
S exp(-C4n) + Cs exp( (Cp(-()))))) + exp (-Con)
I &Crexp(-Can),
where C7 = C5 + and Cs = (C4/3) A Co. By the Markov inequality, for n 2 (3CgCp/C4)², Pg- (II(U)D,,) 2 Cr exp(-Con) < exp(-Con),
where Cg Cs/2. This concludes the proof for the case where 7 < 2/3.
Now, we suppose that 2 2/3. Let = n 1/3 and J [Pmax Puunn) (RC2)]. Define (ki..... kk)) as subsequence of [K] such that pmin + (j 1)KE2 < 9k, I Pmin + (j 1)KCz + for = I.....J J 1, and set hi K.
Suppose that |Sa,k; St,,, < <//2 for every j 1,...,,J J. Then, for any ls [K] with ki S k ky+1 for j I....,J - 2, we have
S S S Sū - So,k5t1
< 18 - - + 1S So
< c/2 + Lolgh gk,+il
< / e/2 + Tookez + 5)
< /2 + 2Lgrez
<
31

---

where the third inequality holds by our assumption and Lo LipLipschitz continuity of S with Lo being a positive constant because (A5]ii assumed. the fourth inequality holds by the definition of ky, the fifth inequality holds because á S Ké2 for y 2 2/3, and the last inequality holds for sufficiently large so that <2 S </ ()).). Note that gk,-11 - gkyl < 2x52 by the definition of J. Then, for any l E [K] with k--1 S ke S kJ, we have
So.k - Su,k <
Combining the preceding two displays, we have Sö.k - S < 6 for any l E [K]. Similarly, for any S < Therefore, for n 2 (4Lok/e) we have
k E [K], we have So.k
(So E So ||Sa So 2 c (So So: 1|aa Sblooa 2 e/2].
(35)
Then, we can decompose
Eg. [I(UU
Da)l S E-- [u((0 E θ ||s - Sillso 2 c/2 or |3 80112 2 E} D.)]
E
[I D.) + EB- [I((U2 Dx) + Ey [13 D
(36)
(1)
(ii
(iii)
where
U1 {0 e max
|50.k, So 2 c/4 4 or ||3 1-112 2 c).
28J5J-1
U2 = 10 E θ |50 - S0,k, 2 2/2
max 2Si
|So 50,k3 < c/4).
U3 = (0 E θ: |Sa.s - Sū,k, 2 e/2
max أللوكー1 |So, - Su.,, < </4}.
The proof for (i) is similar to that of y 2/3. Let 63 > 0 be constant be chosen later. Similarly as in (35). we have
SSo E So ||Ao A 2 esn } c (So E So ||Ao Abllo C10Esn (37)
where C1o is positive constant depending on Lo and k. Then, we have
II(O2s)) ) 2 II[IAo Añllo I Ee) I[[| 8e1le S cs)
2 Cn Aolloo. S C1ocan-3
2 Ciice exp (-orJ cs log (Cioegn $) $)5)
where the second inequality holds by positive constant Cn depending on d, ea and the prior's lower bound near 3", and the last inequality follows from constants ca, C7 and cs in Lemma C.3 depending on Pmin- Pmax. M1. M2, a. a. p. C10 and e3. Similarly as in (33). there exists the event f2 such that g- (I2) S exp( - (20)) and on the event 22, we have
/ II
Pa (D,) > Ciico exp (-orJ cs log_ (Ci0gn $)J (C1 + 1)(zm)
Pa-
t=1
> C1ice exp
(-C12 - (C1 + 1)E3n)
2 C1ice exp C12Cpp logn (C1 + 1))mm).
where the second inequality holds by C12 = + es (log
(C1oes) + 1), and the last inequality holds A.5 there exist tests 2,, such that
because J < C/32//3 by the definition of J. By Lemma
Eg- [ S exp(-Ciamm)
sup
Eg
[1
Pn.1 S exp(-Cian))
where Cia is a positive constant depending on Mi, M2. L, B, Pmin. Pmax. and e. We choose <3 (C1a/(3(C) + 1))) ((Mi A M2)/2) B). Combining the last two displays, for (3C12Cp/C11)) we have
ER [[ D..) s C14 exp(-C1sn).
(38)
where C14 (C110))= 11 + 2 and C1s (Cia/3) A (e3/(2()) (2C))) are positive constants.
32

---

We now consider the term (ii). We split U2 in U2 and U2,+, where
U2. {0 θ So,k: S0 I -c/2, 25-5J-1 |So.k, -o,,, < c/4),
U2 = {0 E @ So.k: Sō. 2 2/2, 2S15J-1 (So,k - So.ky1 < <c/4].
max
Note that U2 C - U U where
U2. {0 θ ||3 318-8116 n)
-2__ {0 O: So,4. Sok S -c/ 8 < n).
for some sufficiently small positive constant depending on e. By Lemma A.3 there exist exponen-
tially consistent tests 2, for testing Ho 0 = 0" H1 0 E U,__. Similarly as (26 in the proof of Lemma A.5 construct the tests V n,2 for - by
n22 1 (D.)
Σ
Σ 1=1
(E (D)) + Eo 102 (D)))/2
where 62 (D() = L(P E (gh...... The J. Y = 0}. By similar argument as the proof in Lemma oo.
and supoeu3 Eg V 222,, + 0 By Lemma D.11 [6]. there exist exponentially consistent tests 2. for testing Ho 0", H 0 E U3__ Let nn 2n 2n.2.2. Then, there exists positive constant C16 depending on M1.
A.5 we can show that Bg- n,,,, (D.))
M2. L, B. Pmin. Pmax. and such that
1. [2,2]] S exp(-C1en),
sup DEU2.
Ey
[1 2n,2] exp((-Cien)
Then, by a similar argument as the preceding, for n 2 (3012Cp/C1o) it holds that
Eg- [T(,, Dw)l s C1 exp(-C17n),
(39)
where C17 (C16/3) A (2C()))) a positive constant.
We restrict ourselves to vectors So such that maxessgJ-1 1S - So < e/4. Suppose that So.k, Su.k, < c/4. Then, we have
So,ki
Sü So,k, So,kz + S0,kz 50
< S0
-So, S0,kk 50
e/4 e/4+e/4
= =e/2.
where the first inequality holds by the monotonicity of Sh. and the last inequality follows from our assumption and the fact that [S Sō,ual
< e/4. Thus, it holds that
U2 10 E ① So. So, 2 e/4, max |So,k, So.u, < c/4] 2515J-1
C (0 ( So.k - So 2 e/4}.
Then, it is sufficient to show that Eg. [T D.)] 0 oc, where U2,+ {6 E O So,k, So,k, 2 e/4]. Let csn 1/3 where > 0 is sufficiently small constant to be chosen
later. Similarly as in 32 there exists the event f2 such that F.. (Ng) S (xp(-<3/(CC3)m) and on the event Q2 we have
Pa (D.)dIT(O) exp + 1)ean).
e Po-
Furthermore, we have
11(O..))
11[[|Ao Añllo S e1) [1[[ 87 S e1)
2 CB exp (-07J cs log (Cioca)J) [T[] -- S (4)
2 Cisco exp (-CyJ es log (C10es)JJ d
Ciscs exp (-c7J log ( cl
33

---

where the second inequality holds by (37) and Lemma CB and the last inequality holds because [I[1 12 I c4) Cisc with positive constant Cis depending on d and the prior's lower bound near 8*. Combining the last two displays, on the event 923, we have
Po (D)) > C1scs exp (-c7J cs log- (Ciuca)) + dlog - (C1 + 1)mm))
Pa-
2 Ciaca exp Cinn log (C1 + 1)
where the last inequality holds by positive constant C19 This implies that Eg-
cs.
[IU D.)] B [ [,)1 + P (2g)
$ (Cisca) -1 exp (Cisn's logn + (C1 + 1)egná) IT(U) exp
n
20
(40)
We now prove that the prior mass of + is exponentially small. Note that
So
So,k2 exp(-Ao,ki) exp(-Ao,k2)
S Ao, Ao,
8
Au,k-
Aemddyy +11
Let X = Ek +1 do By 3
X is gamma distributed with parameters og and p. where og
+1= Okk. Then, we have
I1 (U2
S I1
01 9
$ 17
12 _
K
10p
(-
PE
$ 00 exp
80 K
- exp C2n log 2: n- C2n"7)
S exp (-021/2.111
where the second inequality holds because K - Cp5 the third inequality follows from Chernoff bounds. Here, the fourth inequality holds because K 2 n and ag S K/J a S C2n n 7-13/3 under (P2) with positive constants Czo depending on T. Puii. Pmax and k. and Cz1 = pcC, pl / (8Cp). The last incquality holds for (2C'20 log 2/C21)² Combining this with (40). we have
Cz n
Ez-
[u(U1,+ [.)]] C22 exp Cign't logn + (O1 + L)e5n
+ exp
2C3 n
where the inequality holds because 7 2 2/3 with positive constant C2 = (C18ca) -1 We choose
<s = (Caa/(((C++1)))>)MM (1MMA((221() Then, for (3C19/ C21 )3v log 2/C21)
we have
(_221 n (-3
C21
Eg MU, Dx)] C22 exp
eep
n
202
C23 exp
(41)
where the last inequality holds by postive constants C2u = C22 + and Cza = (c)
Combining (39) and (41), for n 2 (3C12Cp/C16) v (3C19/ (21)3 (2C20 2/21)) we have
ET
[U2 Da))l < C14 exp( - CC7n) + Cz3 exp (CCann
C25 exp (-Czant)
(42)
34

---

where C25 = C14 + C2s and C26 = C17 A C21 are positive constants.
By similar argument (ii), there exist positive constants C27 and C2s such that
( S C27 exp (-Cesni)
(43)
Combining (36).
42 and 43 we have
6 [I
D.)l - C29 exp (-Cson+))
where C29 = C14 + C25 C27 and
C30 = C1s A C2s A C28 are positive constants. By the Markov
inequality, have
Pg II [D,) 2 C2 exp (-Csin)) < exp <exp(-Csnn)) (-Coint)
where C31 = C This concludes the proof for the case where 7 2 2/3.
A.2 Proof of Theorem
Lemma A.6. Let O' = {(So: 3) E So,K 2 M1.So, S M2, |1 D}, where M,, M2 and
D are some positve constants such that M₁ < M2 < 1 and let P {Po 0 E e'). Under the assumption (A2] there exist positive constants C₁ and C2 depending only on M,, M2, L and D such that for every E > 0, it holds that
N(r, N',,P', PD, S (Ci/c+ (a//e+K)*(C2////
Proof. Let Sy = (So = (So, So.k) M2 2 20.1..... ... So. 2 M1 and Hy = {Ao (Ao.1...., Ao,k) : X2 S Ao,1 S ... I Λ..K I \1). where A2 log M2 and A log M1. Then, for any Ao corresponding to the vector So E Sy Ao belongs to Hig since Au,E = log So. E (12, A1] for any k 1, i..... K. For 0, let
Ha.- = (Au Hy:
=
for some positive integers M....., my satisfying mi S ... mx} Then, it not difficult to show that Hy. an e-cover of Hl with respect to || I1.o- Note that the cardinality of Ho.e is the number of K-tuples of integers (mi,..., mK) satisfying [Ai/e] mi S
S..S mg I /2//c], which is given as (LAa/e)-[Ar/ we have (e, Hb. || (loo) - (Daa/e[*K) S (A2/E K)K. Therefore, we have
based on simple combinatorics. Hence,
(ee Hy, || (1x0) S (>2/E+K))
(44)
Take any two parameters (So, 3), 0' (Sy, 8¹) O'. By Lemma C.1 and C.2 there exist positive constants C1, C2 and C3, depending on MI, M2. and D, such that for any x X and p E G.
D ) ci Ho Horloo
<c Abllo + C21113 -B1113-8111.
(45)
where C1 = 0102 and C2 = c103.
Let m == NNee((2C)) Hb, 11o0) and :- N(e/((2))) B', -11)), where B' 1B ||31|2 <
DJ. This definition implies that there exist A.. Ao, Hg such that for every Ao Hg- the inequality Ao - An,illa < </(2C;) holds for some < < m. Similarly, there exist
3 81 E 1 such that for every 3 B,, ||B Syll2 < e/(2C) holds for some < j l.
Let Ozg = (So... 8.) ),)+ E O', where So.; be the vector corresponding to Ao.; for I...., and
j 1.....44 J. By (45). for any 0 (So, B) O', there exists 0, for some 1 S m and S S
such that
(pe po.,) S Ci Ao + Cells - Bylle S.
Consequently, the covering number Nee, P', Drr) of order ml. Note that m S (2C, 12/e K)K by (44). Furthermore, by Proposition C.2 of [16). < (6)C2/e)" Therefore, we have N', < (Ca/e K)* (Ca/e)",
where C3 = 20 and C4 = 6DC are positive constants depending only on M,, M2, and D.
35

---

Proof of Theorem 3.7 First, we define the square Kullback Leibler variation as Vo(p.q) = [(log(p/q) K (p/9) ) dP. For every e 0, we define neighborhoods of 0" by
B(0 e) 10 E : K (po-, po) S VVL(P S {..
We begin by checking the prior mass condition. Note that there exist constants M₁ and M2 such that O < Mj < (v) s M2 < 1 for any E [Pninn by assumption (A5) Let U {(So, .8 E θ SSo Sill. V 3 3*112 < <o} be a neighborhood of 6", where 6o is a positive constant that can be chosen as eo ((M, A (1 M2)) A B ensure that U S θ. By 28) in the proof of Lemma
A.I. there exists a positive constant Co depending on M1, M2, L and such that for any U.
log
Pa-
Co-
po
By Lemma B.2 in [16), the uniformly bounded likelihood ratio implies that
K(po- (P)) <c.D (po- Po)
pg+
CiD (por,
Po
100
(46)
Vo(po- :po0 po) S c2DD (po- po)
po
S C2 (po
Po
where C₁ = C1 exp(Co) and C2 = 02 exp(Co) for universal constants ej and c2. By Lemma C.1 and Lemma there exist postive constants c3, C4 and cs, depending M1, M2, L and B such that for any 0 E U.
DH (p6 po) S c3ll Ho. Hø loo
$ C3llAA - Abllo + 1-113-8811
E θ || Ajllx I Cgens -|8 3-12 S Coen where C3 = C3C, and C₁ = C30, Let 0 = E
where C3 = 1/(233/Ch (2) and C. 1/ 1/C2av Vi V C2). Combining the last two displays, we have
On Du B(0" nU.
Since ||o So S || - Abllo for sufficiently large n such that 6n < <0/(Cos V Co), follows that O₂ C U, implying O, U = O,, Thus, we see that
[B G. 2 (B("", (.))
(I - Abllo CsC.)) (13 CoC.).
(47)
By Lemma C.3 with the specified prior (3) the first term in the right side of the last display is bounded below by C7 exp( K CgK (ogg((ssn)) where C7, Cs and Cg are positive constants depending Proin: Praax, M1, M2, a. and p. Let Va(R) denote the volume of a d-dimensional 2 norm ball of radius R > 0. The closed form of Va(R) R)) is given by Va(R) = 4//2 / 1) Rd where r is the gamma function. Note that T( 1) S [(d 1) d! < d for d 2 Then, the second term in the right side of the last display bounded below by Cio(VT/d))(Gee C10 is the lower bound of the prior on a neighborhood of 3 Therefore, we have
where
11 (B((", e..) C7C10 exp( CCkK CgK log (Crew)) (VF/d)
2 C7C1o exp( C&K CgK log (C - dog d dd dooo (C
C7C1o (xbloexxp(CCaaCp - CoC,n (og((C(sn)) - d log d d (CGen)) eexp(-Cnnn)),
where the third inequality holds because K 2 Opn" with positive constant Cp depending on Punin Pmax and x defined by K, and the last inequality holds by a positive constant C1 log( (og(OrCir C1C)) ) + CsCp + CCCpp( Csl + 1) log Co + 2 because log (C',) S llog CI + log holds for any C' > 0 and n² logn < nc?. Thus, by Lemma 10 of [15], there exists an event Ω, such that Pg. (2,,) 2 1/(n2.). and in 2,,.
/ (x)((en()) - (n((0))) > exp(((()) 2)ne)).
(48)
36

---

By the Kullback-Leibhe inequality, note that Eg. [e(0)] is maximized at 8 = 8", meaning its first derivative at 8 is equal to O. Additionally, for 9 == (So. () E U, note that So uniformly bounded away from 0 and 1, and 3 is bounded by assumptions [A]] [A5] Since the covariate has bounded support by assumption ( (A2)
) by a Taylor expansion, there exists a postive constant cg depending on M1, M2, I and B such that for any 0 E U, we have
co (0, s Eg. [e(0")] Eo- [e(0)] ((po,po)-
Combining this with (46). we have
CHDo S Du(po-PPo),
(49)
where Cn = co/o/ CT. Then, we have
Egg
[I((P 0-) 2 MJen [ [I( (0, 8*) 2 MJc,) nu [2) E3- [I(UU) Dn)]
Eg-
- Egg-
[T, [R,) + 07 exp(-can),
(50)
where In = 10 U DD
2 CnMMee. for large constants M and J to be chosen later, and the last inequality holds for n 0s by Lemma A.T with positive constants cg, C7 and cs depending on Mi, M2, L, B, Pmin. Pmax: Ct, O. P and k.
Define Py {pe 0 E U} and N supe>e, N (c/36, {po Pu :0:00 r. DH). By Lemma A.6. there exist positive constants C12 and C13 depending on M1, M2. L, and B such that
Nº s N (en/36, pSivee ,DH)
I (36C12/c, + KK) (3nC
exp(K log (0g(3/11// + K) + d. log(36C1s/cz))
S exp(Ciane)),
(51)
where the last inequality holds by a positive constant C1a depending on C12, C13, Pmin. Pmax and k. In addition, by Lemma 2 of [15) and Lemma 9 of [15] applied with Cn Men, where Ch M 2 2, there exist tests on that satisfy
Eg On I N exp -
(-2
1
1- cxp (-.C2
(52)
sup EN )n) S exp (- Jnea
eE.,
for any J 2 1. Then, by (48). the first term of (50) is upper bounded by Ep- [[,,, D.. < Eg. on + exp((Cn 2)me?) sup E (1 - Φn). GET
(53)
If M is sufficiently large to ensure that C2 Oi > C2M2/44 by combining 51 and the first line of (52). we have
((cu-2 22 ne,
E2 On S exp
1 exp (- M2ne))
- C
< C15 Cipexp exp
where C1s = (1 exp(-2214))
is a positive constant. If we set J = and choose M to be 112222-(04 (Cn1 +2) > C2 C2/4/4 by the second line of (52), the second
sufficiently large such that Ci2y M2 term in the right hand side (53) is bounded by
c
exp
Therefore, if we choose M to be sufficiently large such that M 2 (C1 2) V Cu/CCH, by combining the preceding two displays, (50p and (53). we have
Ez- [I(( 8*)= 2 Mcn D.. (2.) H s (Cis + 1)exp (- 1x < C17 exp (- A cs)
+ or exp(-can)
37

---

where C17 = C1s + + and C16 (C11 + V C1 are positive constants. An application of the Markov inequality yields that
Pg- (I, 8*) 2 Mc, [a,1 2 C17 exp (-Cisnea)) S exp (-Cisne where Cis = (Cia A cs) be a positive constant. Note that it is easy to show that p-.. (D 0*) 2 Mc. D.) 2 C17 exp (1(n (l2m) - 1- (I(Po(O,,) (*) 2 Me, D,) 2 Cxpexp exp (-C1sne)))
Combining the last two displays and (48) we have
Fg. ((I1(Do(0, 6*) 2 Me, D 2 C17 exp (-C1sne
< lpg. ((TT(D 0*) 2 Me, D2) 2 C17 exp (- (-(I n (.2))) + Pg. (9n)
s 1--- (O, 0*) 2 Me, D,) (2.) 2 C17 C17exp exp (- ((sne)))
Pg- (92)
- exp (=
+ n
Thus, we have that with probability at least - (oxp(-Cisnc,, + 1/nen),
we fix M = ((Dg(0, 2 Mc, (..) C17 exp (-(n)ne)))
Ci//Crr /Cr,, then the proof is complete.
A.3 Proof of Theorem 3.2
Lemma A.7. Let e' {(So E So.k 2 So.1 S M2, 1131|2 D), where M, M2 and D are some positve constants such that M1 M2 < 1, and let p' {po 0 O¹). Under the assumption [A2] there exist positive constants C₁ and C2 depending only on M,, M2. L and such that for every > 0, it holds that
N(e,P', (D)) S exp(Ci/e)(C5/ee).
Proof. Let Fo the collection of monotone functions / (pmin: Pmax) + [A2, Ail. where A - log M1 and A - log M2. Additionally, let Ao denote the cumulative hazard functions with respect to the baseline complementary c.d.f. So. Then, for any So corresponding to the vector So E {So E So So.k 2 M1, S M2}. Ao log So belongs to Fo.
Take any two parameters (So. and 0' (S% B') E O'. By Lemma C.1 and Lemma C.2 have
we
Du )o)) < Co Ex.P Ho (X. P) (X, PX, 1/2
< S S,ll2 -
$ C1 - A6ll2,0 C2113 - -
(54)
where Ex,r denotes the expectation with respect the covariate X and the price P, and Co. C1 and C2 are positive constants depending on M,,M2, L and D.
Let mn := N(E/(2C)) Fo, Il. l12.0) and := (eee(2 B", 1111)), where B' = [B E Rd ||81|2 < D}. This definition implies that there exist Ag. Ao, E Fo such that for every Ao E Fo. the inequality |A, Au,il220
m. Similarly, there exist 3I....,B1 B1 E B such that for every 3 E B, ||@ - 8yll2 < c/(2Cz) holds for some 1 s < l. Let Su,, (91.
</(2C,) holds for some 1 <
(gk((g)) )) where So,; exp(-Ao,) and 6G (So.., 33) O for i = 1,.... m and j = 1....,l. By (54), for any 0 = (S.. E O', there exists 0,g for some
E (1, (1,...,, m) and j E (1....,.}
1} such that
Du (po. Po.,) ) < CillAo - A0,il2. + C2118 - 311155
Consequently, the covering number NNe. Pi, pi, DH) is of order ml. By Proposition C.8 of [16), note that 212.)) S
m < NNj(e/(2C)) by Proposition C.2 of [66] (6DC2/c)² Therefore, we have
ee), where C3 is universal constant. Furthermore,
N(c,PP', ((c, I where C4 = 2C, C3Ai and Cs = =DCC2 are positive constants depending only on M1, M2, L and D.
(xp(C)/
38

---

where each grid point gi is defined as 9t = Pmin + kō with An 7 for some constant 0. Let J = [Ppmax Pmmi)////// (KEG,) and define (ki,...,,) ks) as subsequence of [K] such that Pmiin + (j 1)men < 9k; S Pmin + (j
we have Proof of Theorem 3.2 Recall the grid support G = {gt k = ......KK J,
J - 1, and set KJ K. Suppose that |So. Sū,,, < En for every 1)KEn + ô for = 1, IJ.
j = I...J.J. J. Then, for any K E [K] with k; I k < ky+1 for 1, J 2, we have
So - S S So - So,k
1 / - S0 + |50 - Sō,kzzi
< en + Lolgi - -k
I < + Lolgk; 9kytzl
S en + Lo(ken + +6)
< (2Lox 1)em
where the third inequality holds by our assumption and Lig-iipseiizz continuity of St with Lo being positive constant because [A5] is assumed, the fifth inequality holds by the definition of kj, and the last inequality holds because S ricn- Note that 19k, 9k,l < 2nc,, by the definition of J. Then, for any & E [K] with 1 S k < kJ,, we have
Sū Su, (2LoK + 1)
Combining the preceding two displays, there exists a positive constant C. 2Tg + such that Sü So < Cocn for any & E [K]. Similarly, for any k E [K], we have S0, Si < Cocn. Therefore, we have
II ( 0o S CDEn) 2 ([)s Sbllo.. S cn)
(55)
where S - Si maxj=1.....J |So,k, So,ky
Note that there exist constants M1 and M2 such that 0 < M1 < (g()) S M2 < 1 for any
V E [Pmin: Pmaxx] by assumption (A5) Let U (So, 3) : |S. Stll V ||3 - 88 < tg) be neighborhood of 0*, where eo is positive constant that can be chosen as 6 ((M (1 -
M2))/2) A B to ensure that U S O. Given in (47) of Theorem 3.] there exist postive constants Ci and C2 depending on M1, M2, L and B such that for sufficiently large with 6, e (C1 V C2),
II (B((", )) 2 II (I - Abllo S Clc,)) II (13 - 8 S C2c,).
Note that for 0 E U, SS. S constants in x depend on M1, M2, L and B. Thus, the inequality (55) implies that
I|A, Abl and ||S, Soll x AA Abloo where
(I A, S CoC 2 II (IIAo Abllo S cn),
where Cj is a positive constants depending on M,, M2, L and B. Combining the preceding two displays, for sufficiently large ni such that 6n < #a/(C) V C2) and 8 S (
[ (.) 2 II (IIAa Añiloo. S (ChC,)
II (1133 31 S C2cn).
Therefore, have
II (B((f, 2 CaCa expeppep CoJlog ((Cg - dlog d - (C26n))
2 ExCooxpp(CC exp(( - CbCre log - (c16x)==o dlog d - d (C2eeg(((Gnn))
2 exp((Csnna)
where the first inequality holds by Lemma C.3 with positive constants C2. Ca. Cs depending on Pmiin Pmax, Mr, M2, a, @ and p. and Ca serving as the lower bound of the prior on a neighborhood of 3*, the second inequality holds because J S Cre, holds by the definition of with positive constant C7 depending on Puin+ Pmax and K, and the third inequality holds by positive constant S
= | ne? and d dllog_ (Em) < nea Thus, by Lemma 10 [5). there exists an event Q, such that
(oC C1) +1)+ log C21 + 2 because e,
(Q,)) 2 1 - 1//ne,, and in Un.
/ exp((x.() - en (d))) 2 ())
(56)
39

---

By (49) in the proof of Theorem
3.1 there exists positive constant Cи depending on M1, M2, L
and B such that ( 8*) D (po-.P) for 0 E U. Then, we have
Eg-
[1 )²) 2 M [
Eg (IDD((8, 2 MJc,) nu [2)1 Eg- [IIUU Dw)]
$ Eg-
[ D.) [2,]) + Eg- [II(U") [D,)],
(57)
where I'm - 10 U (psrs,pp 2 CJnn for large constants M and J to be chosen later.
Define Py {po 0 U} and N sup N (c/36, {pe Pu :0 [x]: Dz). By Lemma A.7. there exist positive constants Cg and C10 depending on M1, M2. L and B such that
N = N (fn/36, SSiee DH)
1 exp(360 (36C1oe
I exp(360gnc) + d log (og(361100c
I exp(Ciime))
(58)
where the third inequality holds because =1 ne and the last inequality holds by Cn = 36Cg + 1og(3611o) + because d llognee)) < 2nc 2 In addition, by Lemma 2 of [15] and Lemma
of [5] applied with CH Men, where CH 2 2, there exist tests @n that satisfy
E On I No exp (-) -2
1
exp (-202)
(59)
( 1
(- 1
sup E (1 Φn) S exp
BeT',
for any 2 1. Then, by (56). the first term of (57) is upper bounded by
Eg- [I,, D 19, s Eij on exp((C's + 2) sup E8 2n). veT,
(60)
If M is sufficiently large to ensure that C7, Cn M /4, by combining 58 and the first line of (59), we have
Ey on S exp
((n1-)
ne?)
1
1- exp eep ( M2M
S C12 exp
C2 C2 4
1
where C12 (1 exp(-2C(1)) -1 is positive constant. If we set J and choose M to be sufficiently large such that C22 22 (2 + Css) MM2 /4, by the second line of 59 the second
term in the right hand side of (60) is bounded by
exp (-
2/ Therefore, we choose M to sufficiently large such that > (2+ C2) Cn/CH, by combining the preceding two displays, (57p and (60). we have
Eg. [I, 0*) 2 Men [.,,) S (C12 + exp (-C13ne,) + Ez. [II(U D,,)],
where C13 = (C's + 2) V Cn is a positive constant. By Lemma A.I if < 2/3, the second term on the right-hand side of the last display bounded by 02 exp( c3n) for n 2 c1, and i 2 2/3, it bounded by cs exp(-cen 1/3) for n 2 CĄ, where cI...., C6 are positive constants depending on Mj. Mg. L, B. Pmin+ Pmax, K. a. α and p. Then, we have
C14 exp (-Cinnc
if < 2 if 2 3
EB. [I( (0) 2 Men 1
C16 exp (Cinntt
where C14 = C12 + 1 + c2 C13 = C1 A 63. C16 = C12 + + 03 and C17 = C13 A cg. By the Markov inequality and (56). we have that if y < 2/3,
IID 0*) 2 Mc, D.,) S C14 exp (- (-Cisne2);
40

---

with probability at least - (exp(-C1snc)) + 1/nea), where Cis C1s/2, and if 2/3,
II(Dq(0,0*) 2 Men Dn) - C1e exp (-C2nn)).
with probability at least 1 -
+ 1 1/nen), where C19 = C17/2. If we fix M =
22 then the proof is complete.
B Proofs for Section 5
B.1 Proof of Lemma 5.1
Proof. We first consider the epoch - 1 under the condition 7-1 < 1/3. Let qi(- x)) be the conditional probability mass function of Pa given X₁ = x for & in epoch l. By Lemma C.5 q(- 2)) satisfies the assumption (A4) for every epoch 1. Then, by Theorem 3.1 there exist positive constants C1, C22 Cy and C₁ depending on L, B, Pmiin Pmax: K. az, p such that for 7 [log](cs/n1]]+
[1( (0, 0*) 2 61 Di-1) S C2 exp( 1up(-c314-1E-11
(61)
with probability least exp(- -3 -en--16 1/11111 16 We partition the parameter space
θ into two subsets θ {0 E θ DQ., (0,0") < a9-1) and θ {0 E θ
10, 2 014-1). Then, we can decompose 07-1 as
の-1
/ eciI(o D.-1)
J 0 Odi(O Di-1) + -
odi((o) D.-1)
= (1 - R--)0 + TC- -1-1
(62)
where T--1 11,2 D:-1). Here, 0--1 and Ø-11 are the mean estimates of the probability measures resulting from the restriction and normalization of the truncated posterior distribution on the sets 0.11,1 and 1,-1,, respectively. It is easy to check that the function + PQ_, 0*) is convex and bounded over the domain Ô. By Jensen's inequality, we have
De-, (0- S ( 6--1
(e-,(0,0") (T D
<1
(63)
where (- D be the probability measure obtained by restricting and renormalizing Ii(- Di-1)
to 1111, and the last incquality holds by the definition of 1/-1,1- 1 On the event that the inequality 1/(m-16711) for
66 holds, we have that with probability least exp( exp(-cam-107_) (cgg(c//n1)] + follows that
Da-,(0 (0-1000) 1-000))== S TI-1 Da.) (0-11 -Q--100)= + TI- -T 10-0001111 00-1000
C161-1 + I1(0,-1.2 Dr-1) De 10-1,000
I1(@) D!-1)
02 exp( - 111--73111
c19-11 1- 02 expl exppppcccm11e__11
(1 + vdlla ())
C1a-1
where the first inequality holds because of the convexity of the function 0 + DQ.-, (0, 6*) and 662 and the second inequality holds by (63) and the definition of 7- The third inequality follows from
( D.-1) 2 1, D combined with inequality (61p and the boundedness D over θ under the assumption (A1) The last inequality holds with positive constant C₁ depending
on C12 C, C3, 6 and B, since /d (ocpp--cp--ee_))) 02 esp(-caml-i(fn)) S E-11-
41

---

By similar arguments before, for the epoch - under the condition N1-1 2 1/3, by Theorem 3.2 there exist positive constants c5 cB o7 and cs depending on L, B, Pmiin Pmax: R. and p such that for I 2 (ogg((s/mi) 1,
((,a-1(0,0)) 2 CSEL-1 Di-1) & cock-1,
where
lexp(=crr-11 eepp 1-
if S N1-1 //2 7- 2 3:
5
2
with probability at least 1 Êk-1 1/( Since exp(-c7tk 0- S cxp(-crm/11)
1/3
unify the cases where "V-1 is either greater than less than 2/3 and obtain the bound
(T 10,,0)) 2 0561-1 D,-1) S exp(- 1/3
(64)
with probability at least 1 - ( 1/(m-167_) Similarly, for / 2 [log2(cs/n1) + 1. 1/3
we have
1 (0' 0-) 2 C2E1-1,
with probability at least exxpp(-ppppp 1/3 1/( where C2 is positive constant depending
on C5, Co2 C7 a, b and B. The proof is then complete.
B.2 Proof of Theorem 5.2
Lemma B.I. Suppose that assumptions (AI (A3)
(AS) and (BI)
B2)
hold. Suppose that the prior
distribution 11 specified as in ④ and the policy Ti for each epoch I defined by ( Then, there
exist positive constants C₁, Cz, C3 and C4 depending on L, B, Pmin Pmaxo ar a, b, Mh 1/2 and
my such that for Z C1
1471 xnā (logn))
Σ r(t) S CaniDan, LE9
C3s
1
with probability at least (exp(-Can)) 1/3 +3/n²)
Proof. The regret in epoch is decomposed and upper bounded by
Σ r(() Σ
Hg (X,, P.) P.H (X,, (x),
1ES
1E9
Σ
(Pp' Ho- (X,, P?)) Ha (X,, + (P, - -P.Ha- Pt))
13
(P.H 81 (X,, Pı) P.Ho- (X,, (.),
Ha- Pi)) P.H -1 (X,, Pt)) +Prax
Σ
Ha- (X,, P.t) - Ho- (X P?)
1331
1E8,
(1))
Pmax Σ 11 Pi) Ho. (X., P.)
(65)
(ii)
where the last incquality holds because any Pt and P. lie in G C. [Pmin Pmax] almost surely. Note that {(X,, PP))ee i..dd sample of joint distribution which satisfies P. Q2, P Q and X, ~ Px. Since P. H (X,, P?)) - P, H. (X,, Pt) E [-Pmaxx Pmnax] by Hoeffding's inequality.
it holds that
(i) < 2f (logn1)² +E
Σ
(P H HX,, Pellg-
(66)
LEEE
42

---

with probability at least - 1/n.. Let P. argmax
PEg pal--1 P). and let U denote uniform
random variable over G. By the design of Algorithm | we have Pt = RP, - (1 RJJ, where a Bernouli random variable with success probability I mh. By the law of total expectation, we have
E a- (X,, = (1-m)B P.Hg.
(X, P.) + BE
By substituting this in (66). the second term of (66) is bounded by
Σ (P. Ha P(), P.Ha ((xe
(1 mi)
Σ
E
P.Ha iXx, Pi) (X)
P. Ha
(x),,
LEE
m
EB
EE
S
Pmax
11.21
S Co
14
A And (logm)²
where the first inequality holds because P (X,, -P)))PPHppp)) Ha (X,, Pt) S by the definition
of Pr, and the last inequality holds by the definition of vn (6) and 7 with a positive constant Co depending on Puinn Pmax, K. ? and 1/2. Combining this with (66), we have
1+71 (1) <i 11
A m (logm)²²
(67)
with probability at least - 1/m2, where C₁ = 2pmax + Co is a positive constant.
For (ii) and (iii), by Lemma C.6 for every > 0, there exist positive constants e₁ and 0o depending on L, B, Pmin: Pmax: K. a, p, a, b, nı and e such that for large 2 C1, we have
SS ggi-1 - 0i + 11,31-1 - -8 <
with probability at least 1 - exp(
2/3 Note that there exist constants Mj and M2 such that 0 < M1 S (Prnax) < 5 (Piin) I M2 < by assumption (A5) Take c = C2, where
C2 ((M, A M2))/2 A B). On the event that the preceding inequality holds, we have
|||] S5 + 31 18 < Cz.
This implies that $6.11 > M1/2 > 0, S (1+ + M2)/2 1 and 1|3'-112 2B. Then, by 1/3 Lemma C.2 for any p E G and 2 c1, with probability least 1 (xp(-con/111 we have
Hx.. p) H (X..) p)1 S C.1 S (p) + C. 3 8" 11
(68)
where C3 and C4 are positive constants depending on Mi. M2, L and B.
Let 22 be the event that 688 holds. For (ii), under the event Q4, have
(ii) < C3
| -(-)))))))))))))))))))))))) (5 C4
| 3*
BEE
1E8
= C33 Σ
| - (T + Can - 18
339
Since S6 61-1 - S (P:)
< 1, by Hoeffding's inequality, there exists an event 22 such that P()2)) > 1/n2, and in 22g
P
Σ ( (P nE [| (P.) (P:)) + m² (logni) 1.). KE
Recall the definition of Pa from 8 (p 6.p + 8). Thus, we have P.P
It easy to see that if Pr p for some p E 9, then Pa E E (p S, 5)) 2 P(P: p). Let P be random
43

---

variable distributed from Qi in epoch I. By Lemma C.7 and Portmanteau theorem, we obtain
lim PPP (p - p 5)) P(P. (p 6.p 8) ) Combining these results, we have
(1 = PP = p) 2 P(Pt =p = (p). Then, for sufficiently large I, we have
B -
Σ
(p) (T (p)
PEg
S - (p) - SD)) (p(p)
Σ PEg
QK-1 (p) qk az- (P)
- C35
Σ
S (p) (p())19--1())
PEg
S Css
Σ (p)
(0)
PEG
= Cs 1 2/
where the last inequality holds by Jensen's 's inequality, and Cg be positive constant. Combining the last three displays, under the event f2 0 f22, we have
(ii) Cary (1$)-1-S00 S5ll,, + 113--1 118-1-8811 + Cani (log nz)
(Sp. Don ((S (S (7)
+ Cani (lo
(69)
where C. C3C3 C2 be a positive constant. Similarly, for (iii), under the event 22, we have
(iii) C33 S (P.) - + -
Cmml1) 1 12-
By Hoeffding's inequality, there exists event 2g such that P(2a)) 1/nî. and in Uz.
Σ -(P.))(((P))) n/E [1 (P)) - ST())) n² (log 1E9
Note that if P. E (p-6, 6,p + 5) for some p E G. then P. E {p- 8.p.p 03. By Lemma C.7 and Portmanteau theorem, we have - (p) so P(P, E (p 5.p 8)) = P(P: E
(p- - 6.p + 5)) < PPP p 5) + PP,:: p) + P..: = + 5) S 8, where the last inequality
holds by Assumption (B2) Then, for sufficiently large we have
S (P.) -()))
Σ PEg
$ (p)
S (p)
180 (p) (i() (p)) 9 (p)
Σ
(p(p) 9k- (p) (p)
PEG
C7
(6) (p) --,())) (p)
PEG
C
Σ
34-1 (p) - -5
yh-
C+ [
8-l12,c-11-
Combining the last three displays, under the event P2 nla we have
ConiDau ( 3 (5) + Cant (logmi)+
iii
(70)
where C's C3Cr V C2 be positive constant.
44

---

From 655
67 69 and 77)). for sufficiently large 1, with probability at least 1 - (exp(-c2/2")
n1 1/3) + 3//nf). it holds that
Σ (1) ci mi 1T A Ant (logm)) + Pmnx (ConiDeri 110-,,3111 (,),3)))))))))) + Canj (logm)))
Pmaax (ConiDe: (1S ( 1) (S;: 3*)) + Cani (logni)))
= ConiDaa (()) 1181-1,3-1) 1) (S) 3)) + C10 n
nnd (logmi)²
where C Pmax (CB + C8) and Cia = C1 + mm C3 are positive constants. Then, the proof is complete.
Lemma B.2. Suppose that assumptions (A7) (A3) (A5) and BI) B2) hold. Suppose that the prior
distribution II specified as and the policy Ti for each epoch I defined by ( Then, there exist positive constants CI..... Cs depending on L, B, Punnn Pmaxo Ri, P. 0, b, m, 1/2 and nı such that for 2 C2
Σr(t) rt( S
Cadini (log(d V m)) Cany (logm)) Czdén/ (log(d m)) Cgnj (log m)
14
if 7-1 < 3 if 7n11 2 3
LEE; with probability at least
St where
Ccs/n n-1 Os/nf
if <
G
1-11 2 1
Proof. By Lemma B.I there exist positive constants C1, C22 C3 and C4 depending on L,, B, Pmin Pmax: K. P. a b, mh 12 and n1 such that for / 2 C1.
Σ rt)) coniDon 10 -0-1,0) 1000))) + C3 19
n
Anj
(log mz)
(71)
with probability at least - exp(-ccpp 1/3 -3/ng. In addition, by Lemma 5.1 there exist positive
constants cs. 6b. 07 and eg depending on L. B, Pmins Pmaxs Ki, a, p. a, and ni such that for / 2 cs.
Do,,, (0- 00) S C6EL-1
(72)
with probability at least - G-1 1/(n--19- where
Mog(d V m1) + m
Vlg m
if < 3
6
log(d +
logna 721
if 2 1.
ny
and
if < 3 if 1.
G
eeep(-csh) - -csm $
Consider the epoch - satisfying 7-1 1/3. On the event both 1 126 ci V cs. we have
and 722 hold, for epoch
Σ r(1) < c2c6m161-1 + c3
1422 (logm)
And
T4
< 20206 (um-idylog(e ( + +m
14
Vlogm- mngmm1 + c3
147 (log m))
3 A n
mi
< Scidnng (log(d V vn))d
11m C2n, (logni)²,
45

---

where the second inequality holds by substituting 2m-11 and c!-1. and the last inequality holds with positive constants C Cc2cg and C₂ cp + cg because it holds that n x ni due to 7 where Cp is positive constant depending on Pmiin Pinax and K. Similarly, for epoch 2 V cs satisfying 7- 2 1/3, we have
1 Ant) (logm))
Σ Cr(t) S c2comee-11 + es 1EE2
11
20000 (VnildyVlo((d 11-1) + i (loggm1)) (log +03
1+ 2 Anf (logmi)
14
< C ni (log(d v mi)) 3 + C2n, (logm:)
Let Ω and f22 denote the events where inequalities 1 satisfying 7 < 1/3,, we obtain
71 and (22 hold, respectively. Then, for epoch
P(S U (25) < exp(-cin 1/3) - 1/(m--ii)))
- 1/(21/3 14(2//0cmm)))) cam 1/3) + 3/((n//1)))))mmmmm 1 l/(mm ( + 1/m TI-1
< C
78-1
where the second inequality holds because exp(-x) < 1/x for any x > 0 and met > 74 and the last inequality holds since N- 1/3, and C3 positive constant defined as C3 1/ 1/(22/3c)) 1/c7 7/4. Similarly, for epoch | satisfying 7t- 2 1/3, we have
P(2 U (25)= & exp(-can) + 3/n + exp(-csm, 1/3/ + 1/
$ $1/(2) 1/3 + // 1/(com + 1/m S /4//n
1/3
where the second inequality holds because neē n, 1/3 and the last inequality holds by positive constant C4 = 12 + 1/0s + 7/4. Then, the proof complete.
Proof of Theorem 5.2 Before proceeding, we may without loss of generality assume that the last
epoch is complete (i.e., T == nı n2(2N - 1) for some integer N 1). If not (i.e., n (2N-1 1)
T < ni (2 1)), the regret associated with the incomplete last epoch will be no greater than if were completed. Thus, the number of epochs N and T' satisfies T' ni (2 1). equivalently
N (Tgg(T/n1 + 1).
(T /n1) + 2, where To (0, 1) We first consider the case where 1/3. We define Ny, [Toge(TT
constant to be chosen later. Note that Noo N for sufficiently large T 22/(1-10), For epoch
1 < No we have
I I [logz (T /n1)] + logz (T //1)
and hence 14-1 2/2/-5 < T Therefore, by the equation 7 we have
Ka-1=
Pmax Pmin 1
Pmax
Pmin
14-1
7/70
K
for all 1 S Nog. If we set 70 37, then we have
Pmax - Pmin n4
Pmax
Pmin
1/3
Then, the condition 7t- 2 1/3 is sufficient to hold the preceding inequality. On the other hand, for
epoch 1 > Nop. since is an integer value, we have 12 [log (o /n1)] + 3 > log, /m1) + 2,
and hence n n12/- > Th0 Therefore, by the equation
7 and setting no = 3y, we have
Pinax Punin
14-1 7-1
<
Pmax
Pmin
nn
1/3
K
K
46

---

for all >> No and the condition N0-1 < 1/3 is sufficient to hold this inequality. By Lemma B.2 there exit positive constants C5,..., depending on B. Punin Pmax K. a, p. a, b, 17,, T/2 and n1 such that for / 2
H
eeding (log(d V vi)) = + cany (logm)² (edding (log(d v m))) + cyni m))
if > Na
Σ r(t)
(73)
if S N3y
with probability at least
St. where
cc/nin1 π-- fs/mi_1
if N3y
4
if l S N3y
For unity of notation, we denote No = - Note that No Na, for sufficiently large ( /(33)) Let f21, and 922 denote the events where the first and second inequalities in are satisfied for each epoch 1, respectively. Then, we have
73
Nav
N
}
Nav
N
I
n
Ru
n
Siz1 N=Noy
n
}
21 - Σ
c
リ-1
No+11
N
1=Nay
N
> 1 - V c6
7-11
7-11
N=No+1
2 1 - (cs V 66) log(T/// /n + +1
(74)
where the second inequality holds because " < 1/3 for > N3y. and the last inequality follows
from n 2 7 by 7 Here, is positive constant depending on Pmin. Pmax and K.
Now, we decompose the cumulative regret as
No R(T)
Nay
N
Σ
r(t)
+
Σ Σ r().
FE
I=
+1 FEEL
(ii)
(ii)
For (i), note that pSp exp(xx (pxxxxxx (*) is upper bounded by positive constant C₁ == max (p)xs))))
E [Pmin: Pmax] v E [LL, BL} depending on Pmin+ Pmax. B and L. Then, we have
(i) ME>> c
1=1 1E9:
where C2 (2 - 1)C1 be constant and does not depend on T. Let Ω be the event in the probability notation in the display (74). For (ii), under the event Ω by (73), we have
Nay
(ii <
co (log(d v mz)) + cyn (logn))*}
N=N++1
< C3s d T (log(d Ca T (log ?
where C₁ = 23 and C4 = 28c3 are positive constants. Similarly, for (iii), under the event Q we obtain
(iii)
(oadint (log(d ni)) + can,
14
(log (logni)
I=Ns+
N
Css (logld
Σ
z
(logm))
03
n
1=1
<Cs d (log(d cc - Σ
ni (logni)
1=1
<C, d (log(dV Co _ (log $
47

---

where the first inequality follows from (73), the second inequality holds for a positive constant
C5 c2. the third inequality holds because ni" I CpI7 for any 1, ......N N by ( with positive constant Cp depending on Pmin: Pmax and K. and the last inequality holds for positive
constant Cg = cp Combining the last five displays, for sufficiently large 7> C7, it holds that
R(T)= 2 C2 (Ca + Cb) T (log(d TT) + C4 (2 T) Cs T 2 (log T)
S Cs (log(d (T) + CsT 7#1 (logT)²;
with probability at least C1 log ni + 11//77, where Cj = (22/11 v (1
)
Css C2 C3 + Cs. Cg = C4 + Ce and Cio (ca V ez) es)cp" are positive constants, and the last inequality holds because 7 - T for 7 < 1/3.
Next, we consider the case where 7 2 1/3. For any epoch < N, we have 2 2 S T/m, and hence 71-1 n12! < T. Therefore, by the equation 7 we have
Pmax
Puin
n1 7-
Pmax
Pmin T
Pina
Pmin
K
K
Then, the condition Mn-1 2 2 1/3 is sufficient to hold the last display. By Lemma B.2 the event Q2 in (73) holds for all 1 No. and we have
P(L2.) 2 1- - cs/n for 1 > No.
We define N1 = log, 2/3 /n1)] + 1. Note that No < N₁ for sufficiently large T > 33/2.
Then, by the preceding display, obtain
N n
N
I21
21
Σ
c
N==++1
I=N1+1
1 23 C5
T-
I=N++1
2 1 23cs Iog((T/1 1)
where the second incquality holds because R4-1 2-13 for / > Ni + 1. Let O' be the event in the probability notation the preceding display.
Now, we decompose the cumulative regret as
N₂
N Σ Σr().
R(T) Σ
r(1)+
1=
N=
FEE
For (I), we have
(1)
<
C
C
nh 20, T3.
1=1 118
For (II), under the event St', we obtain
(II Σ
foudtnt (log(d v ni)) con (logni)*)
L=N--
< C1 d' (log(d T C12 T (log 4)
where C11 22co, and C12 2 are positive constants. Combining the last four displays, for sufficiently large T 2 C13. it holds that
R(T) S (Ioddt((
C1TT' (log 7
with probability at least 1-C log(T/ni log(T/ni+1))/72)) where Cia N2 /3/2+1, C14 2C1+012 and C15 2²/3cg cs positive constants. This completes the proof.
48

---

B.3 Proof of Theorem 5.3
Proof. Recall the grid support 9 = [gi =0=1..... 1,.... K}. where 9: Pmin + 18, 8 xT for some > 0, and K = [Pmax Pmin)/ /0]. Let Pt. r and Ye be the offered price, the revenue and the feedback at time t, respectively. Let h4 = (p1, 11 P2, r2, ................................ Pt) .P.....PPPP7. be history over times. Note that h, can be induced by (PI,31..... Pr. Uv) since = Prtt- Define a policy
(T+) where
Te a conditional distribution of price pt given -1- supported on G. We denote the conditional distribution of revenue given Pr with respect to the complementary c.d.f. S(p) = = F(p) by
PS. With abuse of notation we view n, 9 + [0, 1] and Po. [0.Pt) + [0, 1] as probability mass function. In addition, we abuse notation by writing P. = ps if for some 9i E G. For given
pe-
S-)), note that Tz = Pryt where ~ Bin(1,,(p.)) Then, we have
(r.) = S(p.) (1 ((p)(()))*= = -(pp) S(p:))=-v
(75)
For given S, let Us = .....,,pp be the reward distributions associated with K-armed bandit. For given policy и and bandit us. we denote the joint distribution of (PI.Pr.....PP Pr, ,r) by Pega. Then, the probability of obtaining a fixed configuration (P1, Pr. FT) is given by
Post (Pr, Pi.............................. .r. PT)
II
14 ( (re).
(76)
Based on this, define the expected regret by
T
R(T := Engs
(
where S(p,S) pS(p) be the expected revenue with respect S for p G. p² p be the optimal price and Egyz denotes the expectation under Pogn- Further, we define the suboptimality gap of index i by A := ,) r(a, S) for i =1... l...., K. For the simplicity notation we use Ps and Es in place of Pogn and Engx. respectively, for fixed policy
V....,K.
M2 > S(g)) 2 S(gk) M1 for some Mi M2 < 1} in the following description. Fix a policy x and suppose that < 1/3. Let > be some constant to be chosen later. We define bandit Us; = (P.5). ...... P such that for some j1 E [K].
Now, we first construct two bandits us, and es; for $1, St S -
(()) (c (c+ (. (1: 9t
if otherwise,
(77)
where be constant so that S, E S. Note that only depends on M1, M2, Paii and Pmaxx- For 1,...,KK K, let (t(t) = E._1 1(p, 9iP be the number of times price gi was chosen by the policy over times, and j = argmin Es, (N(()). Since Σ Es, [Nr(T) = T, it holds that Es, [N;; (T) T.
The second bandit us! (P ....., S is defined by
(g:) (c+ 9;
if
(i())) = (c + 26) gi
ff= A otherwise.
(78)
S (g:) = c 9,
49

---

Therefore, r(g;,11) r(gs, Si) except at index jí and the optimal price in ss, is Ir while in esg. 9y is the optimal price. Then, we have
T
R(T, S1) = Es,
Σ
r(oi S1) r(pe. St)
K
A S: Es [N:(T))
Σ
c. Es [N((T)
(T Es, (N)(T)
Tc Ps. N₁, (T) - -
2 2
where the second equality holds by the regret decomposition and the third equality holds because A Si = (c+ c) c for i + J. Similarly, we have
K
R(T,S))
Σ
A 8 Eg; [M((T)
i=1
Es JN (T)
Tc
T
Ps
N₁, (T)
2
2
Combining the last two displays and Lemma 2.6 in 42 we have
Tc
N5, S T
T) 2 )
R(T, S1) R(T,
Ps,
2)
+ Psi (gr
2
Tc
exp
(-K(Ps, Ps;)).
By Lemma 1 in [14, the KL divergence K ((Ps, Pss)) is bounded by
K(Ps,
Es, [N:(T)) (PP p.S))
i=1
Es, [N (T)
.PS)) K (P,
K(P oí Ji
T
ji p
where the first equality holds by 76),, the second equality holds by the definition of S₁ and S and the first inequality holds by the definition of index ÿi- Note that 75) implies that pS: and PS are distributions of Bernoulli random variables with parameters S (وو and S (95z). respectively. Therefore, by Corollary 3.1 in 40), we have
(Si(0;;) - S (gx) ))²
K(PS, P 34
81 (11 S (9;;))
(2eg 1/2
M M2
4
P M M2
where the second inequality holds by the definition of S, and Sy, and the last inequality holds because Ie E [pmin: Pmaa]] for any [K].
Now, it remains to choose e. Due the monotonicity of the distribution functions S and Sy, there additional constraints in choosing Specifically, by the definition of S (77) the following
50

---

condition must hold: (c+ 9n. c -1 By the direct calculations, we obtain c S - 8. Since Di E [Pmin Pmax] for any i E [K], it sufficient to choose S p satisty this condition. Similarly, we consider the monotonicity of S1. but before doing so, we divide it into two cases: (a) ji H and (b) J1 > Л. For the case (a), it is necessary that Si (g;; ) S (1 S (1) holds, and for the case (b), S (gg) S (9 must hold. By the simple calculations, S 2pmas is sufficient to satisfy the above conditions. Since VK/T < 8 if y 1/3, it is sufficient to choose e= C K/T for a small enough constant > 0. Combining this with the three preceding displays, there exists constant C₁ > 0 such that
R5
R(T, S1) + R(T, CIVKT
2 T
completes the proof for the case y < 1/3.
In the second case that 7 2 1/3, we construct another pair of bandits us, and Usy for S2, S22 E S in the following description. Let 62 - - and i1,..., is be positive integers such that pmin + jeg 8 < 9e, S Pmin + jeg for j = 1, .,... J. where J = [(Pmax
/e2]. We define partitions I of index set [K] by 1 {i E [K] ij-1 < i S is} for j = 1,....JJ J. where ip 0 with go Puin. Then, define bandit 0g, (P ..... Px such that for some f2 [J].
(2():) = (c + 62) . 9ozz
if E 1ja
(79)
(2(9:) c.... c-
if E I, for j E [J] except at f2-
Let (t) Eier, N:(t) for j I,....J,, and j/2 = argmin Es, (M))))
Since Σÿ=1 Es, (M,[M((T) T, it holds that [s (T)) s J-1- Then, the second bandit usg
(P ..... Pk²) defined by
(g.) = -cc+ Fei2
if E 4/2 if T if i E 17 for j E [J] except at j2 and 1/.
(g.)) -c+ 262) Digs
(80)
(g.) = =Cg
Therefore, r(gi, S2) r(gi, (/)) except at index E 1 and the optimal price in uS, is pe.. while in Usg. Big is the optimal price. For j = 1, 1,..., except at j2, note that A 9² 2 e2 for E 1 since r(ii, S2) + 62 and r(g,, S2) S by the definition of S2. Then, we have
K Σ
R(T,S2)
A Es, [N.(T)]
i=1
Σ
A S Es, [N(())
JE
ATT
Σ
C2 Es, (M)
JEP
62 (T Es, (M)(2))
Te.
Ps. Mg (T) S T
2
where the first inequality holds by the definition of Mj Similarly, we have
R(T,S))
Σ Σ
A Esg [N:(T)
JE(J SEI,
> 62 Esq [Mi, (T))
T62 Ps; (T) > 2
T
2
51

---

Combining the two preceding displays and Lemma 2.6 in 42 we have
Tc
T
2 )
T
+ R(T,
Ps.
Mi (T)
-
Pss (T) (T)
(81)
Tc (PK Ps:)).
exp
By Lemma in
14
we can decompose the KL divergence K (Pss,, Ps:) as
J
((Psg Ps;)
Σ
Σ Es₁
(NPT)
j=1 j=l
Σ
Es, (NP()) P.
iE!
By Corollary 3.1 in 40 and the definition of S2, S2 we have
K(P )P. = (S2(g)) (gi))
(g (3())
(262g 1)2
M1 M2
Pmin M2
for any i Then, by combining the two preceding displays, we have
K(Ps., Ps;)
Σ
Es, [N, K(P P.S)).
TET
< C2 MM (T)
(82)
< T
22
It is easy to check that 62 KT is sufficient to satisfy the monotonicity constraints of S2 and Si.. Therefore, by combining 81). 82 C2 > 0 such that
where C2 Pin. Mr Mr
and J x 6 there exists constant
R(T, Sz) + R(T,S) 2 CTT.T T
27.
It completes the proof for the 7 1/3.
C Technical Lemmas
Lemma C.I. Let O' = {(So. 3) θ So,k 2 M1.Sp.1 & M2, 11312 < D}, where M,, M, and
D are some positve constants such that 0 < Mj M2 1. Suppose that the assumption (A2) holds. Then, it holds that for any 01, O2 E e
(1 NEX DEg
Du (po,
Σ
Ho, (I.p) Ho, (z. p) px
where constants in depend only M,, My, D and L.
52

---

Proof. By the assumption (A2) there exist positive constants H1 and Hg. depending on M1, M2. D and L. such that 0 Hi (z)p,)) < H2 for all X, p and 0 O'. Then, for any 0, 02 E O', we have
/
Di (pe, po₂)
E
E
(VPO, Po, (2,P.2) v po, (x. p...)))
dx
DEN PEg y=0,1
(VHo,(z,)) v Hog (1,
JEX PEg
(V1 Hgg p) vI Ha, (x, 27
p(x)=)px(x)dz
Σ PEg
Ho, (x. He, (z, p)?
JEE
where the third identity holds because the derivative of the map + vt is bounded below and above by positive constants on the interval [H, Hz].
Lemma C.2. Let O' = {(So 3) E : So.k 2 M1.So.1 S. M2. 11312 S D), where M1, M2 and
D are some positve constants such that 0 M1 M2 1. Suppose that the assumption (A2) holds. Then, there exist positive constants C1 and C2 depending on M1, M2, D and L such that for any 0, (So,1, 11), 02 = (So,2. 82) E E and p E G, it holds that
Ha, (X,p) Hop (X, < Ci (v) So,2(0) + C21131 -82112
almost surely.
Proof. We decompose the term |Ho, (X,p) Hog (X, as
Ho, (X.p) - Ho, (X, p)1 = (p) exp((X
(oopp((T8111 8.) - So.2 (xx(XX S2)]
1So, (p) exp(X 8.) (p) eep(( 9.) + (80,2 exp((XTx))
Sp (p) exp(X T2) (83)
For the first term of the preceding display, the mean value theorem on a map t + to (c > 0 constant) yields
So (p) 51) - -0,2(2) {1) = exp(X' "xpp(X33))S0(0)) (p)) 3 8.)-1|S, (p) 2p))
for some (p(p) in (p), Sp.2 Under the assumption (A2) by the Cauchy-Schweer inequality and the boundedness of 81, we have |X 311 s || I LD almost surely. Furthermore, (p( is bounded away from 0 and 1. Then, there exists a positive constant C1 depending on M1. M2. D and L, such that exp(X T 31 31) (1))((p)exp(X 31)-1 < C.. Therefore, the first term of (83 is bounded by Ci (a (p) (p)) Similarly, for the second term of (3). applying the mean value theorem to the map t c exp(()) (d' constant) gives
(So,2())xppe exp(( 8.) (0,2(p)exp( xx)) log So.2 (o. exp) exp(x B) exp(x T (81 B2)1,
for some B between 81 and 82. Note that by the Cauchy-Sehwartz inequality, XXT (B1 32) < |1||2|181 - B2ll2- By assumption (A2) and the boundedness of So.2 and B. there exists a positive constant Cz. depending on Mr. M2, D and L, such that log (o.2()))l 8) exp(X |X) C2 almost surely. Combining these results with we have
Ha (X,p) Ho, (X, p) < Ci (p) So)) + C21 -82212
almost surely for any p E G.
53

---

Lemma C.3. Suppose that the assumption (A5) holds. If Au, ~ Gamma (kk, P) are independent for
k == L..... K, where Ac S a4 S M, and Ke S N for some positive constants A, b, M, N and
P. then there exist positive constants C1, C2 and C3 depending only on Puins Punax; A,b, M, N and p such that
II (IIAo Ao0l 5) Ci exp exp C3K log_e). 6).
Proof. First, we assume that M = L, so that ag I 1 for all K = I.... K. Fix k [I....,K}, In the model can represent Au(gt) as 5 E s=1 Ao.5. Similarly, Aā(gk) is given by 8 - 48... where A Ag(g))/6 and Añ.. (Ao(ge) Ar(ge-1))/6 for 2..... and the preceding display, we have
..... K. By combining this
A - Abllo = max
(No(9)) - Ab(xn)]
1sASk
S max I
10,5 A
K
8
k=1
Therefore, the probability on the left side of the lemma is bounded below by
K
II (I - Abllo S < 2I
Ao. - S
II A=1
II (1Ao, A S Cge),
where Cp = (K8)-1 be a postive constant depending only on pmin and Pmaxx- Since Ao, An, independent variables with Ao, Gamma(au, we have
11 (1)A0 Aiiloo E)
I I(aw) / A
Cpp
K
K Σ A=1
oz exp(-pp II 1 A=1
us ux)du ... ..d...
Mnax(AAxx-Cpee
By assumption (A5) there exist constants M1 and M2 such that 0 < Mi S 5.5( < 5 (Pmin) <
M2 < 1, and holds that N2 S Ao(v) I Nı for all [Pminn Pmaa] where N1 = - log M1 and
N₂ = log My. Note that within the interval of integration, Σ
S Ab(1x) C,Ke Ke <
NIC,K + C. Furthermore, for any < a S 1, holds that [gI(ax) I(ax 1) s Therefore, the right side of the preceding display is bounded below by
1 ah exp(=pC,,K(N) + +)) II {(Ai,) + CCE))* (max(Aū -CEE,
By the mean value theorem, the terms of the product in the preceding display is bounded below by or ( )a joa---C CGp for some Do, E (max(Ağ, - Cpc. 0), Aüj + Cpc). Since T < N₁ N2C Ope and a 1 S 0 for all Is = 1...., K, by combining the last two displays, we have
[[ - A6 <)
K
2 p exp(-pC,pl xxp(-pOpNiK)) (x) (Ccp))))))CCCC()CCCC))
+ Cp on an-K K
II
Am
Note that NIC,K + CpE = l/e: (NIC,Ke + Cpe?) S 1/(C"e) where C' = 1/(N Cp(A2/b)-1) is positive constant, as Ke & N and Ac <
by assumption. Therefore, we have
II (1 Ao Añlloe <)
- as exp(=pC,NN,K)) ( a (Ac9
2 C exepppCC.p C3Klog c),
54

---

for positive constants C1 == exp(-pC,N), :- pC + log- p+ polog_ A Aogo- Cp Coglog_ C' and C33 := b+ 2, where the first inequality holds because Ke I N and A an S by assumption, the second inequality holds because log x 2 log_ x for any a > 0, where log_ denotes the negative parts of logarithm. This concludes the proof in the case that M =.
We may assume without loss of generality that M is an positive integer. For each h: we can represent the A as the sum of independent random variables (Ao,t, m = 1..... M). where kmm is distributed from Gamma distribution with parameters ak.m 04k / and p for m 1, ..... M. Then, it satisfies the conditions of the lemma in the case of = with K and A being adjusted to M K and A/M, respectively. The proof then complete.
K,
Lemma C.4. Under the assumption (A3) for a random sample X, = (Xt,1...., Xt,),, there is constant 0 such that P([Xt,] E) for all -,, d.
Proof. Suppose that for any 0, there exists j' E {I,...,, dd such that P([Xe E) O. follows that Xeel > <) = Since > 0 is an arbitrary number, we have P[[|XXe]lo = 0) = 1. Take j argmax,=1..... [x,i and B1, B2 such that 31.. # $2.5" and B1, = $2.5 for j [d] {.*}. Note that X, (31 32) X1,- ($1.z- B1.z)). Since P([X 0) 1. we
have P(X, (9) (2) = 0) This contradicts the fact that P(X, (81 - -32) o 0) from the assumption (A3) and therefore the proof is complete.
Lemma C.5. If the pricing policy тi for each epoch is specified as in (). then the assumption (A4) satisfied.
Proof. Let (- x) be the conditional probability mass function of given X, for E &g. Note that for any x E X' and G, we have
2 xx) (x)((()))
2 m/K
M1 n =
n1 1t
(log m))
if <
71
-
))
if 2 1
where the first inequality holds by (5). the second inequality holds by 77. and the last inequality
holds by (6). Thus, the conditional probability mass function gr(- .)), parameterized by the policy Tr, satisfies the assumption (A4)
Lemma C.6. Suppose that the prior distribution is specified as in (4), and the policy n. for each epoch I is defined by 5) Suppose that assumptions (Al (A3) (A5) hold. Then, for every 0, there exist positive constants C₁ and C2 depending on L, B, Panin Punxx K, a, P. a, b, Oy and such that for 2 Ct.
||S| 1
Stiloc + +1.33 -183-11-811 -31122 Sc
with probability at least 1 (xxp--C2n/a1)
Proof. We define the distance D.c (61, 02) between 0: (Su.1, B1) and 02 (Su,2, on θ as
Doo (0,, 02) |o S0 + ||,31 82l12-
55

---

Let Q:(- x) be the conditional probability mass function of Pt given X; for t E E in epoch
1. By Lemma C.5 q(( =) satisfies the assumption (A4) for every epoch Then, by Lemma A.1 for every <> 0 and N1-1 E (0, 1]. there exist positive constants c,, and eg depending on
T, B, Pminn Pmax: 6, a; p and 6 such that for z [ogg(ci/m)) +1,
ox, (0,00) 0*) 2 e/2 D:-1) < exp (-cami.)
(84)
with probability at least - 1/3
We partition the parameter space θ into two subsets
i = 10 - 6 (x, < e/2).
+2 10 Dx, c/2].
Then, we can decompose Øi-1 as
0 O Di-1)
0 dii D 0 d Di-1)
6.
62
(1 701)0 7-162 1-1
(85)
where 7-1 = ii(22 Dz-1). Here, 0:-1 and 02 are the mean estimates of the probability measures resulting from the restriction and normalization of the truncated posterior distribution the sets θ₁ and O2, respectively. is easy check that the function >o (0, 0*) is convex and bounded over the domain θ. By Jensen's 's inequality, we have
/ (x, dii |0| D:-1) e,
<//2.
(86)
where (. (.1 D₃-1) be the probability measure obtained by restricting and renormalizing πī to θ1 and the last inequality holds by the definition of θ) the event that the inequality (84)
D
holds, for 1 2 (logg(c1/n) + 1, we have
120 0*) $ (1 T1-1)D (0-1 0-) + T-- D
10--, 00))
11(22 D D(-1)
Doc D00 (0,-,00)) ,0)
11(@) D:-1)
C
C2 exppp( -3 1-1
1/3
(1 vd(a v b) + B).
02 exp( (oxp(_c311/0 13
1/3
where the first inequality holds because of the convexity of the function
Doc (0, 8*) and (85). and the second inequality holds by (86) and the definition of 7-11 The last inequality follows from
I1@@) D,-1) > 1 11(0;-12 D
D combined with inequality (84) and the boundedness of D.
over θ under the assumption (A1) Note that the second term on the right of the preceding display is
upper bounded by e/2 for 1 2 (Log(>(L+Ci)/CC))/)))) where C₁ =
Combining this result with the preceding display, conclude that for / (llog((e1/n1)) ([oog((22/n]] + 1),
(0- -0)0) <e
1/3 with probability at least 1 - 1/31 where C2 then complete.
The proof is
56

---

Lemma C.7. Suppose that assumptions (AD) (A3)
(AS) and (BT) hold. Let observations Dj
{(X,, Ps, HIE,, be i.i.d. copies of (X, ). where Pt is random variable distributed from Q as
specified in Algorithm [ We consider the collection of random variables {Mi(p) p E (pmin: Pinax) ) where M(p)) =- (5((1) exppp"xpxXx 8*) Let Pe denote the points of maximum of M)() over (Puins Pmax) such that
Pe E argmax M(p).
(87)
PEt (Pain
Then, Pt converges to P. in distribution as DC.
Proof. We consider the collection (Mx(p) p E (aminn:mmxx] of random variables, where M&(p)- =
pSh (p)) (p)exp(X "-"1,, For each I, define the point of maximum of My (p) over p E 9 by
Pr E argmax Mp(p).
PEg
We first show that P1 converges weakly to Pe. To see this, we need to verify the conditions of Theorem of [8) We say that & Mhinlvé-KKuatooee
(PK) converges to (Pmin Pmax) if
{p E (Pmin: Pmax) lim inf Ip- gl = 0} {p E (Pmin Pinax) lim inf Ip gl = 0} = (Piin Pmax) 20000 gEG
n-000 gEG
Let N be the number of epochs for given horizon T, satisfying N = (ogg(T/n/ + 1). As - oo
implies T + co, it is easy to see that the grid set G PK converges to the continuous interval (Pmin:Pmax.:
We denote the conditional distribution of Pt given X by Qi(: | X). where Qi( | = (x)
defined in Algorithm I By the design of Algorithm I and the definition of me. the conditional distribution Qz X) satisfies the assumption (A4) for all?. Then, by Lemma A. and Theorem 6.8 of [16), for >> 0, there exist positive constants cr, 02 and cg such that for sufficiently large / with n1-1 2 C1 and for any y, we have
| - + -113-11
12 < + c2 exp (-comi.))
(88)
with probability at least 1 - exp(epcpcmpppppp 1/3), Note that there exist constants M1 and M2 such that 0 < M1 S S (Pmax) < Si (Pmiia S M2 < 1 by assumption (A5) Let Co == ((M, A (1 M2)) B)
and take < Co/2. For large such that n 2 c V (cg log /22 Co)) by 88) we have
|| >i + 3 3a112 < Co. 1/3).
with probability at least exp( -3 This implies that S > M12 0, S < (1
M2)/2 and || 2B. Then, by Lemma C.2 for any p (Pmin Pmax)) ) we can decompose as
Ma (M))) =| exp(X T - - exp() x
<G (D( + C21 3 112.
(89)
where C1 and C2 are positive constants depending on Mi. M2. L, B and Pmax. and the inequality holds almost surely. For each p E (Pmino Pmma),, there exists 8 E {2. ..., K} such that p E [9s-1.9e] Then, we have
(p) - (v) < - S + S - (p)
0 - + Lnd
where the first inequality holds by the monotonicity of 3 and the last inequality holds by To-
Lipschitz continuity of Sž under the assumption (A5) Similarly, we have (p) - 3 (p) s
|8 -S, + Lnd. By combining this with (89).
(p) - M(P) < Cs(1 Sa + -11311-8111) + L
57

---

where C3 = C1 V C2 is positive constant. Combining this with (8), for sufficiently large I and T, we have
M - (M)) S (Ca + 1)c,
with probability at least exp( (o00--31-11 ) Thus, for each p E (Pmmin-Paass M1 - M(p) as I Do in probability, implying convergence in distribution. Since p is arbitrary, M2 converges weakly MI in 8 (A) for every compact A C (Pmin: Pmax), where 8o0 (A) denote the space of real- valued bounded functions on A. By the assumption (B1) and Theorem of [8) we conclude that P; converges weekly P..
By the design of policy in Algorithm the random variable Pi is defined Pt RP, + (1 R--R),,
where R is Bernoulli distributed with success probability 1)- The variable is uniformly distributed on G. Let (Pmin: Pmax) IR be any bounded L, Lipischhttz continuous function for some positive constant L1. Then, we have
[E[((R)) - E[](P)]] [[[((P))
-
E[ 1 (1-)))-110000)) (1)-(-(--))--- R)UI] -
< 2L17iPmmxx +
where the first inequality holds because f is L, -Lipschiit function, and the last inequality holds because Pt and U are less than Pmax almost surely. By the definition of rn and Portmanteau theorem, the right-hand side of the preceding display converges to 0 as + oc. Then, we apply the Portmanteau theorem to conclude that Pi converges weekly to Pa.
D Extension to nonuniform grids
The assumption of equally spaced prices is made solely for technical convenience in developing the theory. However, with some additional technical work, our results can be readily extended more general discrete price sets. For instance, one may consider a nonuniform grid G 1.91....4.. 9K' satisfying
ab < [h++1 - gkl S 66 for all k = L,...,,,
where å x 7 and a, are constants. This more general setting implies that our theoretical findings can be extended more practical settings.
Importantly, since the regret rate in our analysis depends on the discrete set only through the sparsity level this generalization does not fundamentally change the regret behavior. Therefore, while such an extension increases technical complexity, it does not yield additional theoretical insights.
E Discussion on the Cox PH model assumption
We here provide additional discussion on our choice of the Cox PH model, addressing both its suitability and potential concerns about model misspecification.
The key distinction between the Cox PH model and standard linear demand models lies in the use of the hazard function, which is a central concept in survival analysis. Unlike linear models, which model the conditional mean of random variable, the Cox PH model focuses on modeling the hazard rate, a quantity that fully characterizes the survival distribution and is particularly well-suited to censored data settings. A key advantage of the Cox PH model is that it permits separate analysis of Ån and B. enabling theoretical development under minimal assumptions the functional form of Ao This makes the Cox PH model an appropriate and principled choice for contextual dynamic pricing.
At the same time, we note that every model carries some risk of misspecification. Models that directly target the mean (e.g., linear log-linean are often highly sensitive tail behavior and thus more vulnerable to misspecification. By contrast, models focusing the hazard rate, such as the Cox PH model, tend to be more robust in these settings. fully distribution-free approach might be preferable in order to avoid the risk of model misspecification However, such an approach does not appear to be suitable in our context, as cnterval-censored data contains very limited information about the valuation distribution.
58

---

Discussion on the variational Bayes estimator
In our theoretical analysis, the regret bounds are derived under the assumption that the estimator Ø'-1 corresponds to the posterior mean of the true Bayesian posterior, which contracts to the ground truth at the rates established in Theorems 3.1 and 3.2 In practice, employ variational Bayes (VB) approximation to obtain this estimator due to its computational efficiency in nigh-dimensional and nonparametrie settings. The variational family used in our implementation is sufficiently expressive that the VB posterior mean closely approximates the true posterior mean. As empirically demonstrated in [29], the considered VB approach performs comparably to, or better than, traditional MCMC in terms of estimation accuracy.
From a theoretical perspective, the regret bound depends directly on the convergence rate of 0 Therefore, if the VB posterior attains the same contraction rate the true posterior, the regret guarantees remain valid. Recent advances in the theoretical study VB methods (e.g.. [46 T 45]) provide sufficient conditions under which the VB posterior achieves the same contraction rate the full posterior. Although a rigorous regret analysis for VB-based estimation in our specific setting remains open, these results indicate that regret guarantees continue to hold under appropriate contraction assumptions.
G
Additional discussion on estimator replacement
Although we do not provide a formal proof, the Bayes estimator in our proposed algorithm could potentially be replaced by the NPMLE. However, even if so, careful selection of the exploration parameter ?7 crucial for designing an optimal pricing policy. As empirically demonstrated in Section 6 our choice of the exploration parameter (6) substantially improves cumulative regret compared to the parameter choice (denoted as a% in their notation), which employed the NPML.F.
H Details of the experimental setup
We use a Gamma prior with a1 = =... = == 10-5 For a prior of 3, we use multivariate nor- mal distribution, (0, Ia), where I, denotes the x d identity matrix. The truncated point estimator is computed within parameter space of 3 truncated to [-10, 10jd. The proposed algorithm involves three hyperparameters: the first-epoch size n,, the exploration parameters 7) and 7j2. These are tuned through grid search over the ranges n1 E {64, 128, 256), 171 {2 4/3 2 3/3 2 2/3 2-133 20) and ?/2 (2- 12/2 11/2 2- 10/2 2 99/2 with an initial period of To = 3000 for each combination.
For a fair comparison, the hyperparameters of 7 are also tuned using the grid search procedure. We the CoxCP algorithm with the e-greedy heuristic, described in their experiments. This algorithm involves two hyperparameters: the first-epoch size and the degree of exploration parameter т. The hyperparameters are tuned over the ranges Ti {64, 128, 256, 512, 1024) and E 1 2-3, 2-2,2-1,11 1,2,,, following the procedure outlined in their work.
2-1
Computational resources used
All experiments in this paper were conducted using a machine equipped with an Intel(R) Core(TM) 19- 10900X CPU. No GPU was used.
59


Reviews:
[{"review_id": "S95epw7eBT", "reviewer": "Reviewer_Zntn", "summary": "The authors consider the Cox proportional hazards model in the context of binary semi-parametric contextual dynamic pricing. Based on the non-contextual statistical estimation results under this Cox PH model from the statistics literature, they develop similar ones under the contextual modeling. Then an epoch-based algorithm design is utilized to incorporate those estimation results, along with imposed exploration probabilities similar to the epsilon-greedy algorithms. \n\nMatching regret upper and lower bounds are derived. The finding of improved regrets for well-designed algorithms under discrete prices is interesting, insightful and valuable in practice.", "questions": "1. For Cox PH model, statistical estimation results are developed from survival analysis literature and contribute to the optimal dynamic pricing algorithms. Could the authors discuss whether extensions, still leveraging the case 1 interval-censored data structure, but towards other semi-parametric pricing models, are possible?\n\n2. The nonuniform grids are discussed in Appendix D. The authors claim that \"with some additional technical work, our results can be readily extended to more general discrete price sets\", and \"this generalization does not fundamentally change the regret behavior\". Could the authors discuss in more details on 1) what additional technical complexities arise for nonuniform grids, and 2) why the generalization will not fundamentally change the regret behavior, is there any evidence from statistical estimation theory in survival analysis? \n\n3. The convergence rates of the posterior distributions in Theorem 3.1, Theorem 3.2 generalize the results in [4] to incorporate contextual information $X_{t}$. This key technical development in estimation errors help build the contextual dynamic pricing algorithms. Could the authors discuss the difficulties and challenges in this generalization?\n\n4. There is a phase transition of the convergence rates ($\\gamma \\geq 1/3$ and $\\gamma < 1/3$) in both the existing non-contextual and newly-developed contextual scenarios, which lead to the same transition in the derived regret rates. Could the authors give more intuitive explanations and illustrations for this phenomenon?\n\n5. In lines 309 - 311, the authors compare their regret rates with those in [6]. However, [6] considers continuous prices and thus enjoy a different benchmark. Intuitively, the continuous optimal price yields higher revenues than the discrete best price (the optimal price with the discrete set). Is it appropriate to conduct the regret comparison if the benchmarks are truly different? How would the regret rates of the authors' proposed algorithm transfer to ones under continuous prices? \n\n6. More discussions on the choice of $\\eta_{\\ell}$, and satisfaction of Assumption (A4) may be added, as both of them are crucial elements of the proposed algorithm.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. Although not first introduced in this paper, interpreting the purchase data from the binary semi-parametric contextual pricing model as the case 1 interval-censored data in survival analysis effectively captures the intrinsic nature of the data and helps bridge and revitalize the two fields. \n2. The considered discrete pricing setting is both practical and valuable, and new theoretical insights for this setting are delivered through the contributions of this paper.\n3. The essential statistical estimation analysis of this paper is based on and developed from solid research in statistic literature.\n4. The technical material is delivered with high degree of clarity and rigor. \n\nWeaknesses:\n1. More discussions are needed: 1) possibility of extension beyond Cox PH to other models (See Question 1), 2) technical differences when dealing with nonuniform grids (See Question 2), 3) challenges in generalize the non-contextual convergence rates of posterior distributions to the contextual scenario, 4) intuitive explanation of the phase transition of estimation errors and regret rates, 5) whether comparison of regret rates with those for continuous prices makes sense, and whether the authors' derived regret rates for discrete prices can transfer to ones for continuous prices. 6) crucial elements of the algorithm, e.g., choice of $\\eta_{\\ell}$ and satisfaction of Assumption (A4).", "was_revised": true, "final_justification": "The authors have provided helpful explanations and clarifications. I maintain my score for this submission.", "rebuttal": "**Q1** Extensions to other semi-parametric models under interval-censored data \n\n**A1**  We thank the reviewer for highlighting the connection between statistical estimation results and pricing algorithms.\n\nOur key theoretical insight is that once the price is discretely supported, one can construct a better pricing algorithm by leveraging this support information, which leads to improved regret rates. While our work focuses on the Cox PH model, we agree that extensions to other semi-parametric models under the case 1 interval-censored data structure are both plausible and worth exploring. For example, models such as the Proportional Odds (PO) model or the Accelerated Failure Time (AFT) model can be considered within the same framework.\n\nIf these models permit the incorporation of discrete support information, their performance could potentially be improved in a similar fashion. From a technical perspective, the Cox PH model permits separate analysis of the baseline function $F_0$ and the regression parameter $\\beta$ (see Theorem 3.3 in Huang (1996)). Once such separability is established, the theoretical analysis of $F_0$ with discrete support information becomes more tractable. Notably, Theorem 3.3 in Huang (1995) also implies that such separability holds in the PO model, suggesting that discrete support information may be exploited for pricing algorithm design in that setting.\n\nA detailed extension to such directions across a broader class of models would be interesting for future work.\n\n---\n\n**Q2** Technical challenges and justification for regret behavior under nonuniform grids\n\n**A2** In the main text, we focus on uniform grids where the grid spacing satisfies $|g_{k+1} - g_k| = \\delta$ for all $k$. In contrast, Appendix D discusses nonuniform grids where the spacing satisfies $a\\delta \\leq |g_{k+1} - g_k| \\leq b\\delta$ for some constants $0 < a \\leq b < \\infty$. In both cases, the grid spacing satisfies the asymptotic equivalence $|g_{k+1} - g_k| \\asymp \\delta$, ensuring the grid resolution is still characterized by $\\delta$.\n\nAs a result, using nonuniform grids affects only the constant factors in the regret bound through their dependence on $a$ and $b$, while the key dependence on the sparsity level $\\gamma$ remains unchanged. Hence, this generalization does not fundamentally change the regret behavior.\n\n---\n\n**Q3** Challenges in generalizing posterior convergence rates to contextual settings\n\n**A3** Our first key technical contribution lies in extending the convergence rate analysis from the non-contextual case in Chae (2023) to the Cox PH model with covariates. This extension requires substantial non-trivial techniques and effort without strong assumptions. This challenge is particularly pronounced in the Bayesian setting, where many parts of the proof are highly prior-specific in infinite-dimensional models. In our case, we would like to emphasize that the prior for the baseline hazard function is different from that used in Chae (2023), mainly for computational convenience, and this difference necessitates additional prior-specific technical developments.\n\nA second technical difficulty lies in bounding the Hellinger distance when incorporating covariates. In our setting, we show that the Hellinger distance can be bounded by a separable and additive combination of the distances between the baseline functions and the regression parameters:\n\n$$\nD_H (p_{\\theta}, p_{\\theta^\\*}) \\leq C_1 \\\\| \\mathbf{S}_0 - \\mathbf{S}_0^\\* \\\\|_2 + C_2 \\\\| \\beta - \\beta^\\* \\\\|_2,\n$$\n\nas shown in Lemmas C.1 and C.2. This additive structure is crucial for controlling the Hellinger metric entropy in the posterior contraction analysis (see Lemma A.6 and A.7).\n\nTo enable such analysis, it is essential that the posterior distribution concentrates around the true parameter, i.e., we require posterior consistency (Lemma A.1). Establishing this result under a semi-parametric model like the Cox PH model is technically demanding.\n\nA third technical point is related to Assumption (A4), which is required for proving Lemma A.1. As discussed in Remark A.2, one could impose a stronger condition than (A4) to simplify the proof and derive results as in (8) uniformly for all $\\gamma$. However, such a restrictive condition would require larger values of the exploration parameter $\\eta_l$, leading to higher regret due to excessive exploration (see lines 296–297). Hence, adopting the weaker assumption (A4) is essential in the contextual pricing problem, and proving posterior consistency under this condition is a delicate and non-trivial contribution. For further technical details, we refer the reviewer to Appendix A.1.\n\n---\n\n**Q4** Phase transition in covergence and regret rates across $\\gamma < 1/3$ and $\\gamma \\geq 1/3$\n\n**A4** We build upon a key insight from Tang et al. (2012), who first observed this phenomenon in non-contextual survival analysis. The underlying intuition is closely related to isotonic regression problems, where one aims to estimate a non-decreasing function such as the baseline function $F_0$.\n\nWhen $\\gamma < 1/3$, the grid of prices is sufficiently sparse, meaning that grid points are far enough. In this case, the estimation problem at each grid point becomes nearly independent of the others. As a result, simple pointwise estimators are already well-ordered and directly serve as valid solutions to the isotonic regression problem. This leads to improved estimation efficiency and faster convergence rates.\n\nIn contrast, when $\\gamma \\geq 1/3$, the grid becomes denser and neighboring points are more closely spaced. Consequently, the pointwise estimators can fluctuate and may violate the monotonicity. In such cases, local pooling over neighboring grid points becomes necessary to construct a valid non-decreasing estimator, which limits the convergence rate.\n\nThis transition in estimation behavior naturally extends to the regret bounds in the dynamic pricing problem. Notably, regret in our setting is influenced not only by estimation error but also by the degree of exploration (see lines 296-297). When $\\gamma < 1/3$, sparse grids allow accurate estimation at each grid point with minimal exploration. This enables the algorithm to prioritize exploitation, as reflected in the decreasing exploration parameter $\\eta_l$ defined in Eq (6). \n\nOn the other hand, for $\\gamma \\geq 1/3$, denser grids require more frequent exploration to maintain learning efficiency across the entire price space. This increased exploration effort leads to a higher regret bound. Thus, both estimation error and the degree of exploration jointly explain the phase transition observed in our regret analysis.\n\n---\n\n**Q5** Validity of regret comparison with Choi et al. (2023) under different benchmarks\n\n**A5** We appreciate the reviewer's concern regarding the validity of comparing regret bounds under different benchmarks, and we would like to clarify that our discrete price setting naturally interploates between discrete and continuous regimes.\n\nIn particular, this setting is parameterized by the grid size $K$, or equivalently the sparsity level $\\gamma$. At one extreme, when $K = c$ (i.e., $\\gamma = 0$) for some constant $c > 0$, the price set is fixed and highly sparse. At the other extreme, when $K=T$ (i.e., $\\gamma = 1$), the grid becomes dense enough to cover the continuous price setup. Our algorithm is designed to adapt to any $\\gamma \\in (0,1]$, and thus the derived regret bounds naturally extend to the continuous regime, making them comparable to those in Choi et al. (2023). The main point in lines 309-311 is to emphasize that our algorithm can achieve faster regret rates by leveraging the discreteness when the grid is sparse.\n\nMoreover, we conducted the comparison between both algorithms under the same discrete pricing benchmark by varying the grid size. As shown in Figure 1, our algorithm significantly outperforms the method in Choi et al. (2023) when the grid is sparse, due to its ability to utilize the structure of the discrete support.\n\n---\n\n**Q6** More discussions on the choice of $\\eta_l$ and satisfaction of Assumption (A4)\n\n**A6** We appreciate the reviewer's attention to the role of $\\eta_l$ and assumption (A4), both of which are indeed central to our algorithm.\n\nAs noted in lines 296–297, the choice of $\\eta_l$ directly influences the regret bound by balancing exploration and exploitation across epochs. Specifically, $\\eta_l$ controls the degree of uniform exploration over the grid, which is reflected in $q(\\cdot \\mid x)$. Since assumption (A4) requires a lower bound on $q(\\cdot \\mid x)$, an appropriate choice of $\\eta_l$ is essential to ensure this condition is satisfied. This connection is formally established in Lemma C.5. \n\nWe will revise the manuscript to better highlight the role of $\\eta_l$ and its relationship to (A4).\n\n---\n\n**References**\n- Chae. Adaptive Bayesian inference for current status data on a grid. Bernoulli, 2023.\n- Choi et al. Semi-parametric contextual pricing algorithm using Cox proportional hazards model. ICML, 2023.\n- Huang. Maximum likelihood estimation for proportional odds regression model with current status data. Analysis of Censored Data, 1995.\n- Huang. Efficient estimation for the proportional hazards model with interval censoring. Annals of Statistics, 1996.\n- Tang et al. Likelihood based inference for current status data on a grid: A boundary phenomenon and an adaptive inference procedure. Annals of Statistics, 2012."}, {"review_id": "fvsCvJROPU", "reviewer": "Reviewer_aTCm", "summary": "This paper addresses the contextual dynamic pricing problem under discrete price constraints, which better reflects many real-world retail settings where prices must come from a fixed grid. The author proposes a novel Bayesian algorithm, BayesCoxCP, which leverages the semi-parametric Cox proportional hazards model to estimate customer valuation distributions from interval-censored (binary) purchase feedback. The author uses an epoch-based pricing strategy to maintain i.i.d. data generation within every epoch to make the semi-parametric estimation doable and uses adaptive epsilon-greedy algorithm in every epoch. The author also proves a high probability regret upper bound to demonstrate that when the pricing action space is sparse, the regret rate could be better than the continuous or dense action space.", "questions": "See Strengths and Weakness", "limitations": "See Strengths and Weakness", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strength: The paper contains theoretical upper bound, lower bound, and empirical evaluation, which is quite complete and thorough. The algorithm design is concise in principle and easy to understand. This paper also uses COX PH model in a discrete space instead of continuous space and observes a phase transition phenomenon with respect to the sparsity parameter $gamma$, which is interesting.\n\nWeakness: I am not fully convinced by the setting. The grid length $\\delta=\\kappa n^{-\\gamma}$, where $n$ is the number of sample points. In the sequential contextual pricing setting, doesn’t this mean that in different rounds, or at least in different epochs, the action space of the agent is different? This is a little weird to me. Are there any existing papers that model the action space sparsity in such a way? I think the author needs to justify the setting in a more profound way.\n\nI tried to read the technical proof details, and I find it a little difficult to follow. It would be much better if the author could provide a proof sketch or a roadmap about how every lemma is fully used. Could you please provide a sketch about the proofs of thm 3.1, 3.2?\n\nThe COX PH model, to my understanding, is a way to handle and model data censoring mechanism. It allows tractable estimation to bypass censored observations. What if the data generation mechanism is more general than that? Do you have a more principled way to handle it, rather than this restricted COX model with Gamma prior? I think some discussion about that is needed at least. I feel that there should be a challenge similar to data censorship in this paper, but the author doesn’t mention that explicitly and bypasses it through COX model.", "was_revised": true, "final_justification": "I maintain my score. Thank you.", "rebuttal": "**W1** Justification of our setting\n\n**A1** We clarify that $\\delta = \\kappa n^{-\\gamma}$ is only used in the i.i.d. setup discussed in Sections 2 and 3, where $n$ denotes the number of observations. In contrast, our sequential contextual pricing setting is introduced in Section 4, where the grid resolution is defined as $\\delta = \\kappa T^{-\\gamma}$ given time horizon $T$. Importantly, under this formulation, the discrete price set (action space) $\\mathcal{G}$ remains unchanged across all epochs and rounds.\n\nIn our setup, given $T$, the discrete price set $\\mathcal{G}$ should be interpreted as a pre-specified set of all possible prices from which a seller may choose. In practice, prices are often selected from human-friendly discrete sets (e.g., $\\mathcal{G}$=\\{\\\\$5, \\\\$10, …\\}), and multiple observations are typically available for each. For instance, one seller may plan to sell a product over $T=10000$ rounds using a fine grid of $K=1000$, while another seller may consider a coarser grid with only $K=10$. In this example, the former seller corresponds to a larger value of $\\gamma$, whereas the latter corresponds to a smaller $\\gamma$. Thus, $\\gamma$ can be interpreted as a latent property that captures the seller's preference in designing the price set $\\mathcal{G}$. Since this latent $\\gamma$ is typically unknown in advance, our key contribution is to develop an algorithm that adapts to all possible values of $\\gamma \\in (0, 1]$, achieving optimal regret uniformly over this range.\n\nWe emphasize that our framework does not allow the price set $\\mathcal{G}$ to change over time as $t$ increases; it remains fixed throughout all epochs and rounds. Of course, it is possible that, up to a certain point, some prices in $\\mathcal{G}$ may not have been observed. Exploring such settings would be an interesting direction for future research.\n\n---\n\n**W2** Request for a proof sketch or roadmap\n\n**A2** We sincerely thank the reviewer for carefully engaging with the technical sections and for this insightful suggestion. We appreciate your effort to understand the proof structure and agree that providing a clear roadmap can improve the accessibility of our results.\n\nBelow, we provide a high-level proof roadmap outlining how each of the main lemmas and theorems are logically connected.\n\n**Posterior Convergence Rate (Theorem 3.1, 3.2)**  We analyze the convergence rate of the posterior under both discrete ($\\gamma < 1/3$) and continuous ($\\gamma \\geq 1/3$) regimes. The roadmap is as follows:\n\n$$\n\\text{Lemma A.1, A.6} \\to \\text{Theorem 3.1}\n$$\n\n$$\n\\text{Lemma A.1, A.7} \\to \\text{Theorem 3.2}\n$$\n\n- Lemma A.6, A.7: Provide covering number bounds in the discrete and continuous regimes, respectively.\n- Lemma A.1: Establish posterior consistency under mild assumptions.\n- Theorem 3.1, 3.2: Derive the posterior convergence rates.\n- Lemma C.1-C.4: Provide the decomposition of the Hellinger distance and the prior mass condition required for Lemma A.1, Theorem 3.1, and Theorem 3.2.\n\n**Regret Analysis (Theorem 5.2)** The regret analysis builds upon the posterior convergence results and decomposes regret across epochs:\n\n$$\n\\text{Theorem 3.1, 3.2, Lemma C.5} \\to \\text{Lemma 5.1}\n$$\n\n$$\n\\text{Lemma C.2, C.6, C.7} \\to \\text{Lemma B.1}\n$$\n\n$$\n\\text{Lemma 5.1, Lemma B.1} \\to \\text{Lemma B.2} \\to \\text{Theorem 5.2}\n$$\n\n- Lemma 5.1: Bound the estimation error of the point estimator $\\widehat{\\theta}^{l-1}$ using posterior concentration.\n- Lemma B.1: Decompose the regret into estimation error and exploration terms.\n- Lemma B.2: Derive the regret during each epoch.\n- Theorem 5.2: Aggregate per-epoch regret to derive a total regret upper bound.\n- Lemma C.2, C.6, C.7: Technical lemmas required for Lemma 5.1 and Lemma B.2.\n\nWe will incorporate this roadmap in the final version to improve the clarity and accessibility of our technical proofs.\n\n---\n\n**W3** Request for discussion on more general censoring mechanism.\n\n**A3** We thank the reviewer for the detailed and thoughtful comment. We would like to clarify why the Cox PH model is both a principled and appropriate choice, particularly in the presence of censored observations.\n\nThe key distinction between the Cox PH model and standard linear models lies in the use of the hazard function, which is a central concept in survival analysis. Unlike the linear model, which typically models the conditional mean of a random variable, the Cox PH model focuses on modeling the hazard rate, a quantity that fully characterizes the survival function. This is especially important in censored data settings, where direct observations of event times (in our case, customer valuations) are often unavailable or incomplete. In addition, the hazard function is particularly useful since it is only required to be non-negative and integrable. This flexibility makes hazard-based modeling especially well-suited to censored data.\n\nIn our work, we adopt the Cox PH model, which takes the form: $\\lambda(v \\mid x) = \\lambda_0(v) \\exp(x^\\top \\beta)$. A key advantage of this model is that it permits separate analysis of $\\lambda_0$ and $\\beta$, enabling theoretical development under minimal assumptions (e.g., non-negativity) on the functional form of $\\lambda_0$. This separability facilitates both flexibility in modeling and tractability in analysis.\n\nIn contrast, linear models such as $v = x^\\top \\beta + \\epsilon$, require explicit assumptions on the error distribution, with common choices including the Gaussian and extreme value distributions. However, these assumptions can be quite restrictive, particularly in censored data where estimating the tail behavior of $\\epsilon$ is difficult. These limitations were a primary reason we use the Cox PH model in our framework.\n\nThat said, we emphasize that our methodology is not inherently restricted to the Cox PH model. Other semi-parametric models commonly used in survival analysis, such as the Proportional Odds model, or the Accelerated Failure Time model, can also be considered within our framework. Extending our contextual dynamic pricing problem to these models under a discrete price setting is a promising direction for future work.\n\nIn implementing the Cox PH model, we place a Gamma prior on the baseline hazard function mainly for computational convenience. We would like to clarify that this choice does not reduce the inherent complexity of the model, nor does it restrict the model’s generality. \n\nWe again thank the reviewer for raising this important point and will incorporate a summary of the above discussion into the final version."}, {"review_id": "ChveJl6G2v", "reviewer": "Reviewer_nRn3", "summary": "This paper studies contextual dynamic pricing when prices are restricted to a discrete set. The authors propose a Bayesian approach using a semi-parametric proportional hazards model, showing that incorporating discrete pricing information can significantly enhance performance depending on the relationship between the price support size and the time horizon. They derive both upper and lower regret bounds for the proposed method.", "questions": "1. Technical Novelty: The core contribution appears to be extending the semi-parametric Cox proportional hazards model for pricing (Choi et al., 2023) from continuous to discrete price settings. The key technical results build on generalizing Chae (2023), which deals with non-contextual interval-censored data, to the proportional hazards setting. The authors should better articulate the technical novelty. What specific challenges arise in the discrete and contextual setting that are not addressed by existing works? Why are existing techniques insufficient, and what new theoretical tools or results are developed to address these gaps?\n\nReferences:\n\nChoi et al. (2023): Semi-parametric contextual pricing with Cox PH model. ICML.\n\nChae (2023): Adaptive Bayesian inference for current status data on a grid. Bernoulli.\n\n\n2. Modeling Assumptions and Practicality: The current formulation/algorithm design departs from realistic pricing scenarios in three key aspects:\n\n(1) As stated in Section 2.1, the model assumes $(X_t, P_t, Y_t)$ are i.i.d., which is impractical in dynamic pricing—prices are typically adapted based on historical observations.\n\n(2) Algorithm 1 assumes that in the exploration phase, the seller can uniformly sample prices from the known set $\\mathcal{G}$. However, in practice, $\\mathcal{G}$ may not be known in advance or may change over time and across contexts. In non-contextual settings, it is reasonable to explore a large price set early and narrow it down over time. In contextual settings, however, the appropriate price set is often time- and context-dependent, making the assumption of a fixed known $\\mathcal{G}$ unrealistic.\n\n(3) The algorithm relies on three tuning parameters: the first-epoch size \\( n_1 \\), and the exploration parameters \\( \\eta_1 \\) and \\( \\eta_2 \\). In Appendix Section F, the authors mention that these parameters are selected via grid search. However, in an online learning setting, it is unclear how such tuning would be performed in practice. What is the computational cost associated with jointly tuning all three parameters? Additionally, how should a practitioner determine appropriate ranges for \\( \\eta_1 \\) and \\( \\eta_2 \\), especially without access to validation data?\n\n\n3. Estimation Methodology:\nThe paper states that a variational Bayesian method is used to obtain the estimator $\\hat{\\theta}^{l-1}$. How does the theoretical regret guarantee depend on the accuracy of this estimator? Are there any conditions required for the variational Bayesian method to ensure that the regret bounds hold?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1. The problem setting is practically relevant and underexplored. While most recent work focuses on continuous pricing, discrete pricing is often more realistic in real-world applications.\n\n2. The paper’s primary contribution lies in analyzing the estimation rate of the Bayesian proportional hazards model in this discrete setting and applying it to contextual dynamic pricing.\n\n3. Despite its technical depth, the paper is generally accessible and well written.\n\nWeaknesses:\n\n1. The technical novelty beyond existing work appears limited.\n\n2. Some key modeling assumptions are overly simplistic or unrealistic for real-world applications (see detailed questions below).", "was_revised": true, "final_justification": "After rebuttal: The authors have partially addressed my major concerns on the technical novelty and the model assumptions. Hence I have updated the rating accordingly.", "rebuttal": "**Q1** Technical Novelty\n\n**A1** We appreciate the reviewer’s thoughtful reading and for highlighting the need to better articulate the technical contributions beyond prior work.\n\nOur key contribution lies in conveying the message that, in dynamic pricing problems with a discrete price set, one can leverage the size of the price support to improve revenue. While our work is inspired by Chae (2023) and Choi et al. (2023), achieving the above goal required the following important technical developments.\n\nOne of our key technical contributions is the realization that the exploration rate $\\eta_l$ must also depend on the support size $|\\mathcal{G}|$ to attain the optimal regret rate. Therefore, we utilize the support size information not only to construct the estimator $\\hat\\theta^{l-1}$ but also to determine the exploration rate, as specified in Eq (6) of the manuscript. This enables our algorithm to adapt to all values of $\\gamma \\in (0,1]$ and achieve optimal regret uniformly across this range. Balancing estimation accuracy and exploration in this discrete price setting is a technically crucial contribution not addressed in prior work.\n\nSecond, although it is natural to expect that the result of Chae (2023) can be extended to survival models incorporating covariates, developing a rigorous extension without strong assumptions requires substantial non-trivial techniques and effort. This challenge is particularly pronounced in the Bayesian setting, where many parts of the proof are highly prior-specific in infinite-dimensional models. In our case, we would like to emphasize that the prior for the baseline hazard function is different from that used in Chae (2023), mainly for computational convenience, and this difference necessitates additional prior-specific technical developments.\n\nTo the best of our knowledge, no prior work has established regret bounds for Bayesian contextual pricing algorithms under discrete support, nor have they addressed the interplay between grid sparsity, exploration scheduling, and estimation error. We thank the reviewer again for this important question, which gave us the opportunity to better clarify and articulate the core technical contributions of our work. We believe that these developments collectively address the important technical gaps not covered in existing works.\n\n---\n\n**Q2** Modeling Assumptions and Practicality\n\n**A2-(1)** We would like to clarify that the i.i.d. assumption is not used for modeling the entire sequential process of dynamic pricing, but only within each epoch for the purpose of theoretical analysis. As described in Section 4, our algorithm adopts an epoch-based design, which partitions the time horizon $T$ into multiple epochs. Within each epoch, a fixed pricing policy is applied. This design allows us to treat the data $\\{(X_t, P_t, Y_t)\\}_{t \\in \\mathcal{E}_l}$ as i.i.d. conditioned on past observations up to epoch $1, ..., l-1$. \n    This structure provides significant technical convenience, enabling us to analyze the estimation error of point estimator $\\hat\\theta^{l-1}$ at each epoch. The use of such an epoch-based design is a common strategy in the contextual pricing literature and serves as a practical bridge between theory and sequential decision-making.\n\n**A2-(2)** We would like to emphasize that our setting assumes $\\mathcal{G}$ depends on the level of the entire time horizon $T$, not varying across rounds $t$. This is a practically motivated assumption that sellers in real-world typically construct human-friendly discrete sets (e.g., $\\mathcal{G}$=\\{\\\\$5, \\\\$10, \\\\$15,...\\}) given $T$, and $\\mathcal{G}$ should be understood as a prescribed set of all possible prices from which a seller may choose. For instance, one seller may plan to sell products over $T=10000$ rounds using a fine grid of $K=1000$, while another seller may consider a coarser grid with only $K=10$. In this context, the former seller corresponds to a larger grid sparsity level $\\gamma$. Hence, $\\gamma$ can be viewed as a latent property that reflects the seller's preference in designing the price grid set $\\mathcal{G}$. Since this latent $\\gamma$ is typically unknown in advance, our key contribution is to develop an algorithm that adapts to all possible values of $\\gamma \\in (0,1]$, achieving optimal regret uniformly over this range.\n\nIn this light, we believe that our discrete price setting is more realistic than previous works assuming a fully continuous price setting. We agree with the reviewer that extending the framework to allow for time- or context-dependent price sets (e.g., $K$ is a function of both $T$ and the context dimension $d$) is an interesting direction for future work. We thank the reviewer again for encouraging us for pointing out a promising avenue for future extensions.\n\n**A2-(3)** We agree with the reviewer that hyperparameter tuning in online learning is inherently non-trivial, which remains an active area of research (refer to Cha and Cho (2025); Lee et al. (2024)). Among recent works in contextual dynamic pricing, Fan et al. (2024) propose tuning hyperparameters at the start of each epoch based on data from previous epochs. In contrast, Choi et al. (2023) adopt a more practical approach, which is similar to ours, where hyperparameters are tuned only once using data collected during an initial period $T_0$. This approach is more computationally efficient, particularly when the total horizon $T$ is large.\n\nTo assess the practical cost of tuning, we measured the average computation time required per hyperparameter configuration in our simulation setup, where the initial period length is $T_0=3000$ and the grid size is $K=100$. The average time was 23.4 seconds, making the total tuning procedure computationally efficient in practice.\n\nIn setting where a validation set is unavailable, we suggest that practitioners select hyperparameters based on prior beliefs about the desired level of exploration. If stronger exploration is preferred, larger values for $n_1$, $\\eta_1$, and $\\eta_2$ should be used; for more aggressive exploitation, smaller values are appropriate. As a practical guideline, we suggest choosing $\\eta_1$ and $\\eta_2$ below 1 to avoid excessive exploration.\n\n---\n\n**Q3** Estimation Methodology\n\n**A3** We thank the reviewer for raising this important point. In our theoretical analysis, the regret bounds are derived under the assumption that the estimator $\\hat\\theta^{l-1}$ corresponds to the posterior mean of the true Bayesian posterior, which contracts around the ground truth at the rate characterized in Theorems 3.1 and 3.2.\n\nIn practice, we employ a variational Bayes (VB) method to approximate this posterior due to its computational efficiency in high-dimensional and nonparametric settings. While the regret guarantees are not derived explicitly for the VB approximation, our implementation uses a variational family that is sufficiently expressive to closely match the posterior mean in all experiments. As empirically demonstrated in Liu et al. (2024), the considered VB approach performs comparably to, and sometimes even better than, traditional MCMC methods in terms of estimation accuracy.\n\nFrom a theoretical perspective, as the reviewer points out, the use of a VB estimator (i.e., a point estimator based on the variational posterior distribution) naturally raises questions about its impact on the regret guarantees. Although a formal regret analysis for VB-based estimation is beyond the scope of the present work, we can offer a general theoretical perspective.\n\nAccording to our regret analysis, the regret bound depends directly on the convergence rate of the estimator $\\hat{\\theta}^{l-1}$ (see lines 296–297). Therefore, if the VB estimator attains the same convergence rate as required in our analysis, the regret guarantees continue to hold.\n\nIn this regard, several general theoretical frameworks have been developed for analyzing the contraction rates of VB posteriors (e.g., Zhang and Gao (2020); Alquier and Ridgway (2020); Yang et al. (2020)). These results provide sufficient conditions under which the VB posterior achieves the same contraction rate as the full posterior, thereby preserving the regret guarantees in our setting. While a rigorous theoretical treatment of VB methods in our specific setting remains an open question, we greatly appreciate the reviewer’s insightful comment and will include a detailed discussion of this point in the final version of the paper.\n\n---\n\n**References**\n- Alquier and Ridgway. Concentration of tempered posteriors and of their variational approximations. Annals of Statistics, 2020.\n- Cha and Cho. Hyperparameters in continual learning: A reality check. TMLR, 2025.\n- Chae. Adaptive Bayesian inference for current status data on a grid. Bernoulli, 2023.\n- Choi et al. Semi-parametric contextual pricing algorithm using Cox proportional hazards model. ICML, 2023.\n- Fan et al. Policy optimization using semiparametric models for dynamic pricing. JASA, 2024.\n- Lee et al. Hyperparameter selection in continual learning. arXiv, 2024.\n- Liu et al. Variational Bayesian approach for analyzing interval-censored data under the proportional hazards model. Computational Statistics \\& Data Analysis, 2024\n- Yang et al. $\\alpha$-variational inference with statistical guarantees. Annals of Statistics, 2020.\n- Zhang and Gao. Convergence rates of variational posterior distributions. Annals of Statistics, 2020."}, {"review_id": "58eYNN9sww", "reviewer": "Reviewer_pkNR", "summary": "This paper proposes BayesCoxCP, a novel semi-parametric contextual dynamic pricing algorithm. The algorithm is based on a Bayesian formulation of the Cox proportional hazards (PH) model and is specifically designed for settings where feasible prices are drawn from a discrete set rather than a continuous range. It shows that leveraging this discreteness can lead to improved regret performance, particularly when the price grid is sparse relative to the time horizon. The paper also establishes a minimax lower bound that matches the upper bound achieved by the BayesCoxCP algorithm.", "questions": "1. I was wondering why, when $\\gamma = 1$, the regret upper bound $\\tilde{O}(T^{2/3}+\\sqrt{dT})$ still outperforms the bound $\\tilde{O}(T^{2/3}d)$ from [6] in terms of the dimension $d$. What is the reason behind this?\n\n2. Could the algorithm handle a price space containing discrete subintervals? For instance, each subinterval is $[g_k - \\delta', g_k + \\delta']$, with $\\delta'$ potentially very small. As $\\delta' \\rightarrow 0$, this would result in a discrete price space. I am not seeking formal proofs; any discussion on this point would be appreciated.\n\n[6] Young-Geun Choi, Gi-Soo Kim, Yunseo Choi, Wooseong Cho, Myunghee Cho Paik, and Min-hwan Oh. Semi-parametric contextual pricing algorithm using Cox proportional hazards model. In Proc. International Conference on Machine Learning, pages 5771–5786, 2023.", "limitations": "See weaknesses.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: The paper is generally well-written and structured. Studying dynamic pricing problems in discrete price spaces introduces an interesting and novel perspective. The paper also proposes a new algorithm supported by solid theoretical results.\n\nWeaknesses:\n1. The assumption of a known functional form for the hazard function (specifically, the Cox proportional hazards model) might limit practical applicability if the actual demand structure significantly deviates from this assumption.\n2. The assumption of a (sparse) discrete price space might be restrictive. In practice, it is common to encounter closely spaced price candidates or even price subintervals (see questions below).\n\n\nMinor comments:\n\n1. If my understanding is correct, the derived regret bound would remain valid even for non-uniform grids in the price interval, provided a certain sparsity condition is satisfied (as discussed in Appendix D). Highlighting this generalization explicitly in the main text would enhance the paper's practical relevance. Additionally, formally presenting this result as a corollary could further strengthen the paper.\n\n2. The experiments currently refer readers to [6] for performance comparisons for benchmark algorithms (linear and log-linear models). Providing direct comparisons or summarizing performance metrics in the current paper itself would improve readability and more clearly demonstrate the potential advantages of the proposed approach.\n\n[6] Young-Geun Choi, Gi-Soo Kim, Yunseo Choi, Wooseong Cho, Myunghee Cho Paik, and Min-hwan Oh. Semi-parametric contextual pricing algorithm using Cox proportional hazards model. In Proc. International Conference on Machine Learning, pages 5771–5786, 2023.", "was_revised": true, "final_justification": "The paper is generally well-written and structured. Studying dynamic pricing problems in discrete price spaces introduces an interesting and novel perspective. The paper also proposes a new algorithm supported by solid theoretical results. However, it still has the limitation on the potential model misspecification. So I keep the borderline accept.", "rebuttal": "**W1** Concern about model misspecification under the Cox PH assumption.\n\n**A1** Indeed, every model carries some risk of misspecification. The primary motivation for using a semi-parametric model such as the Cox model is to mitigate this risk. Nevertheless, model misspecification is practically unavoidable, making robustness to such misspecification a critical concern for practitioners. We first offer several general perspectives on this issue, with a particular focus on censored data.\n\nModeling the hazard rate, rather than the mean of a random variable, has a long-standing tradition in survival analysis. Estimating the mean of a survival random variable is challenging because it is often not directly observable due to censoring. In particular, the tail of the distribution plays a crucial role in determining the mean, yet it is rarely observed in censored data. This issue becomes especially severe in the case of interval-censored data, where no direct observations are available. Consequently, models that directly target the mean, such as linear or log-linear models, are highly vulnerable to model misspecification, particularly when the tail behavior is misspecified. In contrast, models targeting the hazard rate, such as the Cox model, tend to be more robust to model misspecification.\n\nA fully distribution-free approach might be preferable in order to avoid the risk of model misspecification. Unfortunately, however, such an approach does not appear to be suitable in our context, as interval-censored data contains very limited information about the valuation distribution. As a result, estimating $F(\\cdot \\mid X_t)$ (or $\\lambda(\\cdot \\mid X_t)$) without strong structural assumptions becomes extremely challenging.\n\nIn summary, we believe the Cox PH model offers a robust foundation for handling censored observations. Exploring alternative models, such as the proportional odds model, would be an interesting direction for future research. \n\nWe thank the reviewer for raising this important point. We will consider including a more detailed discussion of model misspecification issues and possible alternatives in the final version to improve clarity.\n\n---\n\n**W2 \\& Q2** Question on extending the algorithm to handle discrete subintervals in the price space.\n\n**A2** We thank the reviewer for the insightful question. As we understand, you are considering a setting where the price set is a union of small subintervals centered around discrete grid points:\n\n$$\n\\mathcal{G} = \\bigcup_{k \\in [K]} [g_k - \\delta', g_k + \\delta'],\n$$\n\nwhere $g_k - g_{k-1} = \\delta$, $\\delta \\asymp n^{-\\gamma}$, and $\\delta' \\asymp n^{-\\gamma'}$. While we do not provide a formal analysis for this generalized case, we offer the following conjecture based on theoretical insights. \n\nWe first assume that the subintervals are disjoint, which corresponds to $\\gamma' \\geq \\gamma$. If $\\gamma \\geq 1/3$, the grid becomes sufficiently dense so that the union of subintervals behaves like a continuous price regime. In this case, we conjecture that the estimation error would match the rate for continuous pricing, i.e., $n^{-1/3}$.\n\nMore intriguingly, when $\\gamma < 1/3$, the regime becomes more subtle. In the extreme case where $\\gamma = \\gamma' = 0$, the price set becomes a finite union of non-shrinking subintervals, which resembles a continuous regime. Building on insights from Tang et al. (2012), the confidence interval width around each grid point in the discrete regime is roughly $n^{-(1-\\gamma)/2}$. If each subinterval has width $\\delta' \\asymp n^{-\\gamma'}$ satisfying $\\gamma' \\geq (1-\\gamma)/2$, then each subinterval may lie entirely within the confidence region. This suggests that the algorithm could still behave similarly to the discrete regime.\n\nWe emphasize that this remains a conjecture, and we leave the formal theoretical verification as an exciting direction for future work. \n\n---\n\n**Q1** Question on why the regret bound shows better dimension dependence then Choi et al. (2023) when $\\gamma = 1$.\n\n**A3** The key reason lies in the tightness of the entropy (log-covering number) bound used in the convergence analysis. In Appendix B.1 of Choi et al. (2023), the authors leverage an entropy bound derived from Huang (1996), which states that the $\\epsilon$-covering number of the relevant function class is of the order $(1/\\epsilon^d) (e^{1/\\epsilon})$. Choi et al. (2023) approximated the log-covering number as $d/\\epsilon$, but this approximation is loose. A more accurate bound is given by  $d \\log(1/\\epsilon) + 1/\\epsilon$, which yields tighter control in the empirical process analysis. If this refined estimate is applied to their regret analysis, this leads to a tighter dependency on $d$. In particular, it would match the regret bound $\\tilde{O}(T^{2/3} + \\sqrt{dT})$ that we obtain in our setting when $\\gamma = 1$. This suggests that the dimension dependence in Choi et al. (2023) is not intrinsic, but rather an artifact of a conservative entropy approximation.\n\n---\n\n**minor1** Suggestion to highlight and formalize the extension to nonuniform grids\n\n**A4** We thank the reviewer for this helpful suggestion. As correctly noted, the derived regret bounds can be extended to the case of nonuniform grids, provided a certain sparsity condition is satisfied. Due to space constraints, we did not emphasize the nonuniform case in the main text. We agree that highlighting this generalization could enhance the paper’s practical relevance. We will revise the manuscript to emphasize this point more clearly, and we will consider formally presenting the result in Appendix D as a corollary in the final version.\n\n---\n\n**minor2** Suggestion to include direct benchmark comparisons in the experimental results\n\n**A5** We thank the reviewer for the suggestion. As noted in Section 6, our current experiments are primarily designed to highlight the benefits of leveraging discrete support information. To demonstrate this aspect, we conducted a comparative evaluation with Choi et al. (2023), which also uses the Cox PH model under a well-specified setting.\n\nThat said, we agree with the reviewer that providing direct comparisons with benchmark models such as linear and log-linear approaches would significantly improve the readability and clarity of our experimental section, rather than referring to external results. We will incorporate these comparisons into the main text in future revisions by adding additional experiments.\n\n---\n\n**References**\n- Choi et al. Semi-parametric contextual pricing algorithm using Cox proportional hazards model. ICML, 2023.\n- Huang. Efficient estimation for the proportional hazards model with interval censoring. Annals of Statistics, 1996.\n- Tang et al. Likelihood based inference for current status data on a grid: A boundary phenomenon and an adaptive inference procedure. Annals of Statistics, 2012."}]

Author rebuttal:

Meta-review: This proposes algorithm for contextual dynamic pricing under the Cox PH model and discrete price set. The model extends prior works which consider a non-contextual setting. The authors propose a Bayesian algorithm for this setting and establish both upper and lower bounds on the regret although the lower bound is for the non-contextual setting only. 

The paper is in general well-written, and the setting considered is of practical interest as the price set is likely to be discrete in practice.  On the theory end, this work characterizes two regimes of the regret, which appears to be interesting. In the initial review, there is some concern regarding the incremental contribution made by this model, but the authors did a good job in clarifying them.
Decision: Accept (poster)