Contextual Dynamic Pricing with Heterogeneous Buyers
Authors: Thodoris Lykouris
Sloan Nietert
Princewill Okoroafor
Chara Podimata
Julian Zimmert
Venue: NeurIPS 2025 poster ()
Keywords: dynamic pricing
bandits
contextual
Primary area: theory
TL;DR: contextual dynamic pricing with heterogenous buyers using optimistic posterior sampling

Abstract: We initiate the study of contextual dynamic pricing with a heterogeneous population of buyers, where a seller repeatedly posts prices (over $T$ rounds) that depend on the observable $d$-dimensional context and receives binary purchase feedback. Unlike prior work assuming homogeneous buyer types, in our setting the buyer's valuation type is drawn from an unknown distribution with finite support size $K_{\star}$. We develop a contextual pricing algorithm based on optimistic posterior sampling with regret $\widetilde{O}(K_{\star}\sqrt{dT})$, which we prove to be tight in $d$ and $T$ up to logarithmic terms. Finally, we refine our analysis for the non-contextual pricing case, proposing a variance-aware zooming algorithm that achieves the optimal dependence on $K_{\star}$.

Contextual Dynamic Pricing with Heterogeneous Buyers
Thodoris Lykouris
Sloan Nietert EPFL
Princewill Okoroafor
MIT
Harvard University
1ykouris@mit.ee edu
sloan aloanniettert@epfl.co
pco9@cornel1.
Chara Podimata MIT podimata@mit.ecm edu
Julian Zimmert
Google zimmert@google, com
Abstract
We initiate the study of contextual dynamic pricing with heterogeneous population buyers, where seller repeatedly posts prices (over T rounds) that depend on the observable d-dimensional context and receives binary purchase feedback. Unlike prior work assuming homogeneous buyer types, in our setting the buyer's valuation type is drawn from unknown distribution with finite support size K,. We develop contextual pricing algorithm based on optimistic posterior sampling with regret Õ(K. /dT), which we prove to be tight in d and T up to logarithmic terms. Finally, we refine our analysis for the non-contextual pricing case, proposing a variance-aware zooming algorithm that achieves the optimal dependence on K,.
Introduction
In online learning for contextual pricing, a learner (aka seller) repeatedly sets prices for different products with the goal of maximizing revenue through interactions with agents (aka buyers customers). Concretely, in each round = 1,...,T, T, nature selects a product with a d-dimensional feature representation u4 (context) and the seller selects price p. 2 0. In the simplest variant, the linear valuation model, customers have fixed intrinsic valuation model (type) that is unknown to the learner; this has d-dimensional representation 0* whose coordinates reflect the valuation that each product feature adds, i.e., the customer's 's valuation is v (0), + E, where 6, is noise term. The customer makes purchase only when their valuation higher than the price, i.e., 02 2 Pt- The learner's is goal is to maximize revenue, i.c., the sum of the prices in rounds when purchases occur. An equivalent objective
minimize regret, which measured against benchmark that always selects the customer's 's valuation as the price for the given round.
Before outlining contributions, we highlight the unique challenge of online learning in contextual pricing. One key difficulty is that the learner faces both an infinite action space (i.e., all possible prices) and discontinuous revenue function; indeed, even small price increases deter buyer from purchasing, hence causing sharp revenue loss for the learner. However, the problem offers richer feedback structure than classical multi-armed bandits: non-purchase indicates that all higher prices would also be rejected by the buyer, while purchase confirms that all lower prices would be accepted too. The two primary approaches from the literature to tackle this problem involve estimating the unknown parameter (* through online regression or muuti-diiennionall binary search (see Section 1.1 for further discussion).
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

A crucial limitation for both approaches is that they require all customers to behave homogeneously according to a single type 8*; see the related work section for results robust small deviations from this assumption. Moving beyond this homogeneity assumption, we pose the following question:
How can one design contextual pricing algorithms with a heterogeneons population of customers?
1.1 Our Contribution
Our setting (Section 2). To study contextual pricing with a heterogeneous buyer population, we assume that the type 0e in round t is drawn from a fixed, unknown distribution D.. When D, is supported on single type 8., we recover the homogeneous setting. In our setup, the number of distinct buyer types K. = |supp D.| reflects the degree of heterogeneity. We assume that K. > 1 throughout the paper.
There are several obstacles to applying existing algorithms from the literature. First, canonical contextual pricing algorithms based on regression either compete against (simple) linear policies or assume context-independen and identically distributed (i.id.) valuation noise. In contrast, the optimal policy in our setting may best respond based on context-dependent type rather than a fixed type, and the stochasticity due to heterogeneity is inherently context-dependent and thus non-i.i.d. Second, given that the buyer rypes not observable, one cannot connect the observed feedback to shrinkage of type-dependent uncertainty sets; this rules out running canonical multi-dimennional binary search / contextual pricing algorithms for each buyer type in parallel. Third, since in our setting there is a continuum of actions, any canonical contextual bandits algorithm whose regret scales with the discretized action count (e.g., EXP4) will suffer suboptimal performance.
Our contextual pricing algorithm (Section 3). To tackle the above challenges, we employ recent advances in the contextual bandit literature that attain better scaling with the number of actions, thus evading the shortcomings of EXP4 with naive discretization. In particular, we build on the optimistic posterior sampling (OPS) approach [29] which, in our setting, maintains posterior fe over all candidate type distributions. We call these candidate type distributions models and refer to their (possibly infinite) family as D. At a high level, in every round, OPS best responds to model sampled from jr,. As typical in online learning, the posterior update penalizes models that disagree with the observed feedback (model mismatch) aiming to converge to the model D.. To encourage exploration in the absence of full information, this penalty is reduced by an optimism bias term that rewards models with the highest potential to positively contribute to the revenue. The OPS approach enables regret bounds of /T c log [D], scaling with disagreement coefficient c that measures the per-context structural complexity of the reward functions and captures the tension between exploration and exploitation. This coefficient is always bounded by the number of actions but can be much smaller in general.
Our main technical contributions in adapting OPS to heterogeneous contextual pricing are twofold. First, to bound the disagreement coefficient c, we observe that, for any fixed context, the aggregate demand function induced by D, has at most K, "jumps", thus creating K, + intervals. Over each interval, we bound the disagreement coefficient by a factor of 2. Combining these arguments with a novel decomposition lemma for the disagreement coefficient of functions with K, breakpoints, we show that e & 2(K, + 1). When K. is known, we apply a variant of OPS over a finite covering of the class D containing all possible distributions over K, types, of log cardinality dK, log T. Second, to extend our sublinear regret guarantee to the infinite model class D, we modify OPS to conservatively perturb its recommended prices (which cannot overly impact regret due to one-sided Lipschitzness of the revenue function). We then construct a coupling between the actual trajectory of OPS and one where D,, belongs the finite cover, allowing to transfer regret bounds. Finally, adapt to unknown K, by initializing OPS with a non-uniform prior over models. These technical contributions enable us to show a regret guarantee of Ö K, / Finally, we show that this guarantee is optimal (up to logarithmic terms) with respect to the dependence on both the contextual dimension and the time horizon T, establishing lower bound of ((KK.TT) for sufficiently large T = ((dK3).
Non-contextual improvements (Section 4). The above upper and lower bounds raise natural question on the optimal dependence of the regret on the number of buyer types K.; we resolve this
Each "jump" corresponds to change of type from (say) type i type 1.

---

question in the non- contexttal version of the problem (d = 1) by providing an algorithm with an upper bound of O(vK,T). Our algorithm, ZoomV, combines zooming (i.e., adaptive discretization) methods from Lipschitz bandits [13] with variance-aware confidence intervals [2]. Our analysis shows that the regret of ZoomV scales with novel variance-aware zooming dimension that can be significantly smaller than the standard measure of complexity for Lipschitz bandits. For pricing, this variance adaptation unlocks our (mmin (V,TT, 22/$3) bound (versus O(T2/3), obtained via the
standard zooming analysis).
We note that the non-contextual version of pricing for heterogeneous buyers was previously studied by [4], who establish a matching upper and lower bound if all types are "well separated" from each other. Although our algorithmic approach towards this guarantee is very different, our result can be viewed strengthening of theirs by removing this separation assumption.
Stronger type observability (Section 5). Finally, we consider contextual pricing under the as- sumption that the learner can identify each arriving type, i.e., where the learner observes ex ex-post information about the sampled type 0t. We analyze two observabilityy models: one where the learner under which a computationally efficient pricing algorithm
receives discrete identifier 2n E [K.] matches the O(K, VdT) regret bound of OPS and another where the full type vector 0, E TBd is observed - for which we reduce the dependence on K, and to achieve regret O( / min ( K., dyT). These results demonstrate how richer feedback reduces complexity in dynamic pricing.
Related work. We briefly review three existing lines of work, deferring full discussion to Appendix A. The closest to ours is contextual pricing/search, where a learner interacts with nature to learn a hidden vector 0* E Rd while receiving single-bit feedback [5, 18, 21, 17, 12, 11, 6, 19]. Under an appropriate pricing loss, this setting reduces to ours with a homogeneous buyer population, i.c., K. = 1. However, the deterministic nature of the feedback leads aggressive search policies via cutting planes that do not lend themselves to the heterogeneous case. Although some works tolerate ii.d., comlext-independent valuation noise [12, 11. 6, 19], their methods do not treat our non-i.i.d., context-dependent noise due to heterogeneity. Next is the case of non-contextual dynamic pricing where d 1, originally treated with multi- armed bandits methods by [14]. The closest non-contextual work is [4], whose Enite-types model reduces to ours with d = 1. We improve upon their regret bound, but neither our improvement nor the existing methods generalize readily to the contextual setting. Finally, our setting relates to Lipschitz bandits. Although revenue is not fully Lipschitz, it satisfies a one-sided Lipschitzness, enabling the use of zooming [13] when
(see, e-g., [24]). We successfully refine these for the non-contextual case, but contextual variants of zooming [26, 15] scale with complexity parameters which admit no direct bounds for hetcrogeneous pricing.
2 Setup and Preliminaries
Notation. Let || || and (---) denote the Euclidean norm and inner product on Rdd Let Sdt1 Bd c Rd denote the unit sphere and ball, respectively. Let A(S) denote the set of all probability measures on a measurable set S C TRd, and let supp(D) denote the support of D E A (R.)). We use (S( for those D E ASS) with supp(D)) < k. For positive integer m, let [m] = m..
Problem setup. We consider T rounds of repeated interaction between seller, a population of buyers, and an adversary. At each round & E [7], the seller posts a price pt E [0. 1] for an item to be sold and buyer, sampled from the population, decides whether or not to buy the item based on their valuation et E [0, 1]. We denote the indicator of their purchase by y:: = 11 2 pc). The valuation of the buyer is determined by two factors: their type 0,, which encodes their intrinsic preferences, and an external context ue which describes the current item to be sold and any relevant environmental factors. The learner does not know 8.. but they do know uy We employ a linear valuation model, supposing that Or and ut lie in d-dimensional spaces θ C [0, 1]d and l C gd-) respectively. and take U = (0,, uz). We assume that (8, u) E [0, 1] for all E θ and u E U. We impose no further assumptions by the adversary. On the other hand, we assume that each 0, is sampled independently from fixed distribution D, (()) that describes the buyer population, unknown to the seller. All together, the following occur at each round E [T]:
the contexts, allowing them be generated (potentially adaptively)
1. the adversary selects context u, E 21:
3

---

2. a buyer arrives with type 0₁ E ④ sampled independently from D., with valuation (ue, 0
3. the seller observes u, and posts price ps [0. for the item;
4. the seller observes the purchase decision = 1f 2 pr) and receives revenue P:Mt-
Benchmark. The seller's goal is maximize their cumulative revenue compared to that which they could have achieved with knowledge D.. To express this concisely, we introduce some additional notation. Each distribution Q over valuations in [o. 1] induces the following:
a demand function demq (p) Pv~Qlv= 2 pl.
an expected revenue function rev)(p) = p demo (p),
a revenue-maximiae best response brQ arg maxpe((.1] (p) (breaking ties arbitrarily).
and gap function gapo (p) rbr)(bro) rev (p).
Once restrict to fixed context Ut each type E θ induces valuation (u, 0). Thus, each type distribution D E A()) induces a projected valuation distribution Q = proj D, u) E A ([0, 1]). defined the law of (u, f) when 0 D. We then set dem (p, u) == demo (p), revp (p, u) = (p))(p), (u) == brq. and gapp u) == (p), accordingly. We abbreviate a subscript of D. by "*" alone, writing, e.g., dem. (p, u) and br, (u). These details are summarized in Table 1.
seller policy is (potentially randomized) map from a history {ur, Pr, yr J and the current context to a posted price An adversary policy B is (potentially randomized) map from history {u,. Pr. Vr fre(t-1 to the next context ue. We then define the seller's pricing regret by
(A) = ExE(T)) gap, (pe, uz) = =EEETry (br, (ue), u.) rev. (Pr, uz)).
where {ut, Pt hejr) are selected according to A and B. We will omit the policies from the subscript when clear from context. We focus on controlling the pricing regret in expectation, and will say that A satisfies regret bound f(T) if ([RA,s(T)) < f(T) for all B.
Our guarantees will scale with context dimension d and the degree of heterogeneity, which quantify via the support size K, ;= supp( D+)l (that may be infinite). We do not assume that K, is known to the seller. Designing an effective seller policy is challenging because D., K,, and the realized buyer types are unknown to the seller, who must carefully balance exploration and exploitation given only the current context and the history of purchase outcomes.
Basic pricing facts. Finally, we provide some basic properties of the pricing problem, with proofs in Appendix B. Essential for this work is the one-sided Lipschitzness of the expected revenue function. This is a consequence of the monotonicity of demand functions, and it has previously been used to apply techniques from Lipschitz bandits to non-contextual pricing [24].
Lemma 2.1 (One-sided Lipschitzness). Fix any distribution Q E A(O 1I) and let 0 S p<<p' D' S.
We then have revo(y') (e))(p) < demo(y)(y p) p' -p.
Problem parameters (known)
Instance parameters (unknown)
context dimension
d
type distribution
D. A())
context/feature space
U C gd-1
# types
K. = ssupp(D.)
type/preference space θ C [0, 1]d
Non-contextual primitives
Contextual primitives w.r.t. type dist. E (()) and context u E U projected value dist. rev./dem./gap rev./dem//ap for D.
w.r.t. valuation dist. Q E A(O0,
demand
dem)(p) F. Fo-olo 2 pl
proj(D, u) E A(O0, 1]) fn u) [roj D. (p)
revenue
revo( (p) = p demq (p)
gap
gap max revo(x) reev
f- u) fD. (p, u)
Table I: Summary of main notation.

---

Throughout this work, we must handle distributional uncertainty over value distributions. To compare two distributions P.Q= E P[[0, 1)), we employ the Levy metric defined by
(P. = inf > 0 demp(z - - dem@ & demp(z + + E R).
(I)
This quantity is at most and equals the side length of the largest square which can be inscribed between the graphs of demp and demo (equivalently, the CDFs of P and Q). For type distribu- tions D. E P()),, we use the Levy distance between their projected value distributions, taking dr. (D, D') == supues4- (proj( D, u), ( u))) We use this metric because, if and D' are close under d1., then there exists policy which performs well on both of them; this motivates the use of the Lévy metric throughout the dynamic pricing literature (see, e.g.. 23).
Lemma 2.2 (Pricing implication of Lévy metric bound). Suppose that D, D' E A()) satisfy (D, D*) Then the conservative best-response policy <tu) ba (u) - 0} satisfies
revp(T(()) u) 2 (brp(b( u) - and ( 2 (ev (u), u) 3s for all u E U.
3 Contextual Algorithm with Optimal Dependence on d and T
We now develop statistically efficient (albeit computationally inefficient) algorithms for contextual pricing. In Section 3.1, we treat the simpler setting where D. belongs to finite model class and K, is known. In Section 3.2, we remove these two assumptions, achieving regret Ö(K. V(T)) We also provide a regret lower bound of [2( /K.dT) even if K. is known, thus proving the optimality of our regret bound's dependence on d and T. Omitted proofs appear in Appendix C.
3.1 Warm-Up: Heterogeneous Contextual Pricing with a Finite Model Class
As warm-up, we consider pricing when D, belongs to a known, finite model class. Assumption 3.1. Assume that D, E D, where D (()) is finite and known the seller.
This realizability assumption simplifies our analysis, and the resulting algorithm extends naturally to infinite classes. We employ optimistic posterior sampling (OPS), originally studied for contextual bandits by [29] under the name "Feel-Good Thompson Sampling." In instantiation for contextual pricing, OPS (Algorithm I) maintains a posterior distribution over models, initialized at prior μr e (D). At round i with context u, U, sample model D, ~ j4t, play the best-response price = br (u+), and observe purchase feedback yt- Then, for each candidate model D E 'D we update its posterior weight 14+1 according the loss (proj (D, uz), Pt, ye), defined by
(x v) = (y demo (p)) Arevo(bre))
model mismatch
optimism bias
The "model mismatch" penalty captures the extent to which the observed demand differs from that predicted by D when p: is played. In particular,
function D D. the expected model mismatch Eg,, [[y= dem (Pt, )² Ps] is minimized only by those models D which make the same prediction as D.. i.e., those for which demp (pt, u)) dem, uz). On the other hand, the "optimism bias" reduces the loss for models which have the potential to provide large revenue, ensuring that we perform sufficient exploration.
ALGORITHM 1: OPS: Contextual Pricing with a Finite Model Class
Input:
finite model class C A(O), support size 2 1;
2 initialize uniform prior μı = Uni and optimism strength À Vlog(DI)/KX DD)//T; for each round t E [T] do observe context uy; sample model D, ~ ut:
play Pt: brp, (w:) and observe yı;
update 1 (D) (e(D) exp( uz), vi) for each D E D:
Theorem 3.2. Under Assumption 3.1, OPS with K K, achieves regret Ō( K, log (D).
5

---

The requirement of known K, is imposed for simplicity and will be removed in Section 3.2. To prove Theorem 3.2, we employ disagreement coefficient that controls the per-context complexity of balancing exploration and exploitation. In general, for an arbitrary measurable space X' and function class F X + R. we define the dixagreement coefficient of by
8a 22 PPN (3 (/EF:Epu//()))) (
dis
sup sup c.650vE((A)
In our setting, each f will measure the discrepancy between the demand function predicted by some model D and that of the true model D., for fixed context (full details will appear shortly). While not the most primitive complexity measure, variants of this quantity have been successfully used to analyze a wide variety of structured bandits and active learning problems (see Remark 3.7). The 52 /²/ scaling was historically chosen so that dFs(F) can be directly bounded by the domain size |. For our application, X' = [0. I] is the (infinite) price set and each function f É F, induced by a model D E DD and context UI measures the discrepancy between the demand functions of D and D. after projection onto u, i.e. (p) - dp u) dem, (p, u). In particular, we set
dis(D, D.) = sup dis( ((dmm u) dem. u) : D E D)).
By this definition, if dis(D, D.) is small and the seller plays price p ~ v when faced with context u, it is unlikely for model D) to disagree with D, at p if it is close D, under the (v² norm, i.e., if Eggww[(dema) [(dem (g. u) - dem, 4))²] is small. In particular, playing p ~ v guarantees that
VD E D. (revD rev. rev.) (p, u) >
E Ey (demo - dem.) )q. 2) 2)
D poorly models revenue
D incurs substantial least squares loss average
with probability at least loss, while incentivizing exploration via its optimism bonus, we are able to show the following.
_ dis D.). Since OPS penalizes models with substantial least squares
Lemma 3.3. Under Assumption 3.1 with optimism strength À > 0, OPS (Algorithm 1) achieves regret (D) D.)T + log((D))/A).
The proof in Appendix C.3 combines the OPS analysis of [29] with a decoupling lemma due to [8]. To control dis(D, D.), we show that each function of the form demp(-: u) - dem,(-, u) can be decomposed into K, + non-increasing pieces. Appendix C.4, we prove the following disagreement coefficient bound for non-increasing functions.
Lemma 3.4. Let F. [0, 1] + R be the set of nonincreasing functions. Then dis(F) S 2.
Next, we examine the useful notion of composite function classes. A function class Z R is called an N N-composite of F X + R if there exists a disjoint partition Z = Zi U .... U..UU ZN and mappings (hç Z, + X'EEENN) such that each g E G can be decomposed as g f((h,())) for all E Z and i [N], for some choice of {fe X' - [R]EENN- We show the following in Appendix C.5.
Lemma 3.5. !fG is an N-composite of then dis(g) S Ndis(F).
With these results in hand, we bound dis(D, D.) = O(K)) and prove the theorem. Even though the action space is infinite, the disagreement coefficient matches that which would arise with K, actions.
Proof of Theorem 3.2. For each U, the function u: ) is piecewise constant with K, + 1 sections, since jumps can only occur at the projections of the K, types. For any D E D, the demand demp(:, u) is monotonic, since increasing price always reduces demand. Thus, demp(.,0)
dem, (-, u) is non-increasing on each of the K, + sections, and so the function classes defining dis(D, D.) are (K, + 1) commosites of the non-increasing function class. Applying Lemmas 3.4 and 3.5 then implies that dis( 'D D.) & 2(K, + 1). The theorem then follows by the regret bound of Lemma 3.3 and choice of X.
Remark 3.6 (Comparison Thompson sampling). Standard Thompson sampling corresponds to the alternative choice of log losses: E(Q,p,) p, = log IP (F==-Berddemm(()) (p)) = v] = y log dem + (1- v) log(1- - demp(p)) ). In comparison, OPS uses the squared loss (this is not essential but simplifies analysis) and an optimism bias towards models under which the seller can attain large revenue. This

---

is crucial for obtaining frequentist (rather than Bayesian) regret bounds, as outlined in [29]. One appealing aspect of the log loss that it eliminates models which predict that the observed feedback methods for contextual pricing when K2 = 1.
would never occur, mirroring the elimination- Thus, one natural question (beyond the current scope) is whether DPS with log loss achieves regret scaling logarithnically in T when K, 1.
Remark 3.7 (Relation with existing results). Variants of the disagreement coefficient and the related Alexander capacity are well-studied in the active learning and empirical process theory literature [9]. The version above was first considered by [7]. [8] proved a regret bound which translates to Oly dis (DYT log (DI) our setting, matching Theorem 3.2. However, the sstiaationtoodeciiete (E2D) meta-algorithm which they employ is non-constructive, hence we apply OPS instead. In [29], the regret of OPS is controlled by a distinct "decoupling coefficient." " Our proof of Lemma 3.3 shows that a (slightly modified) decoupling coefficient is bounded by the disagreement coefficient.
3.2 The General Case
We now seek to eliminate the assumptions that D, belongs to finite class DD and that the support size K, is known to the seller. For the first point, we loosen the requirement that D, belongs to D and take D be large, finite cover of the full distribution space (()). Then, we replace the uniform prior [41 with a non-uniform prior that places less weight on models with large support sizes. Ultimately, this will enable choice of optimism strength À that is independent of K,, achieving our second goal. Unfortunately, if D, is close but not equal to model in D, our analysis of DPS fails.
To remedy this, we employ perturbed OPS (POPS, Algorithm 2), an OPS variant with conservatively perturbed and discretized prices. This modified algorithm and its analysis require some new notation. Given value distribution Q E A(OO, IJ). define the E-smoothed demand function dem by
dem (p) == Uni(((([))) (P - 6)].
Similarly, we let (v) == dem & (p). Define contextual extensions dem u) and dem p (p, u) as in the non-smoothed case. For discretization, write P == eN [0, 1] for prices which are multiples of a and let br == arg maxpep, rev" (p) (lifting to (w) as in the non-smoothed case).
Now, at each round t [T]. POPS samples a model D, Me from the current posterior μ4 E A(D) and computes its (discretized) best response P. = br (u.). Instead of posting price Pr directly, POPS posts Pt- = max {pr - 8,, 0). where & ~ (n, e)) is a small random perturbation. Due to this perturbation and discretization, we employ the modified loss (proj Dr, ur), (it, vt), where
EX(Q, v) (p) v)² (br
The perturbations allow us, in the analysis of POPS, couple its trajectory when run with D. & to to a trajectory where D. E D. The discretization is needed to bound a modified disagreement coefficient which appears in the analysis. All together, we obtain the following.
ALGORITHM 2: Perturbed OPS (POPS) for Contextual Pricing with Infinite Model Class discretization error E E [0, 1). finite model cover C A(O)),
Input:
model prior μn E A(D), optimism strength À > 0:
2 for each round t E [T] do observe context ue; sample model D. ~ μ4 and perturbation strength & ~ Unif([O, e )): play P: max (fr- &e, 0}, where p. br. (mx) and observe ye: update M4+1 ps exp(-e (proj D. ud) pr. 31) for each D D:
Theorem 3.8.
With appropriately luned parameters, POPS (Algorithm 2) achieves regret Ö(K. V.TTT) without prior knowledge of K.. Moreover, even for known K, > 1 and stochastic contexts, no con- textual pricing policy can achieve expected regret olyKK (K,dT) for all instances ifT 2 SdK3 log(2d).
Our analysis views the perturbation at Step 5 as being performed by nature, rather than the seller. Treating the seller's action P.,, they then observe purchase (y+- = 1) with probability
Es, [dem, (max{er Sc, 0}, we) pe, ux] Es, [dem, (p. de, vc) Pr. us] dem, (pr, uz).
7

---

justifying the definitions above. Through this lens, POPS can viewed as OPS for an alternative, smoothed demand model. To bound regret, we apply a three-step argument.
First, we show that POPS maintains our OPS regret bound when D. E D. This requires bounding a modified decoupling coefficient and is the only step where discretization is used. direct application of the previous OPS analysis provides regret bound with respect to a smoothed and discretized benchmark. Fortunately, one-sided Lipschitzness of revenue (Lemma 2.1) ensures that this modified regret benchmark is within (e)T) of the original benchmark, as we prove in Appendix C.6.
Lemma 3.9. Under Assumption 1, using prior μr E (D), discretization error & E 1), and optimism strength X > O, POPS (Algorithm 2) achieves regret (A.,TT log(1///(
ET).
Next, we show that, if there exists D E 'D whose smoothed demand function uniformly approximates that of D., then the trajectory of POPS under D. can be coupled with that under D, such that the trajectories coincide with high probability. See Appendix C.7 for the proof.
Lemma 3.10. If there exists D E 'D for which [|dem - dem Ilso S s, then the trajectory {u,, Pr, yo of POPS with type distribution D* can be coupled with that {ul, F. 1/ of POPS with rype distribution D, such that the two trajectories are identical with probability ET.
Finally, we show that, to obtain a uniform e-cover of the smoothed demand functions, suffices to find a )(=e)-cover of the type distributions under the Lévy metric di, as defined in (1). Moreover, we show that the family of all type distributions with support size most K, Ax (0), admits an appropriately small Lévy cover. For notation, we write N(X, d, r) for the size of the smallest subset
X' C X which covers set X under metric up to accuracy T (i.e., for each x E X, there exists r' E X' such that d( ar) I r). A proof of the following appears in Appendix C.8.
Lemma 3.11. D, D' E (() satisfy dr. (D, D¹) <>²/2, then IIdem dem 1lo0 S.. Moreover, we have log N (Ox(((()))))))))))))))))) dr.. Ö(K log 1/e).
For the lower bound in Appendix C. we modify a construction from [4] for the non-contextual case, so that can be tensored into d-dimensions without leaking information between orthogonal contexts.
In Appendix C.9, we combine these lemmas to prove the upper bound of Theorem 3.8.
Remark 3.12 (Bayesian analysis). Consider the Bayesian setting where D. is sampled from known prior μs E (D) (keeping D finite for simplicity). Then, Lemma 3.9 with fa = lu and BTT,T-ED,~ulf ED.--l- log (o(..)/
implies
that OPS, with μi set to μ at Step 2, achieves Bayesian regret Ö(A,TT -
Ö(K,T + Ap)) where H is Shannon entropy. For known K., X can be tuned to achieve regret ((VKTTH(W)) matching the non-BBaysiaan) bound of Theorem 3.2 with H (1) instead of log [D). Remark 3.13 (Misspecified/nossy setting). We note that POPS is inherently robust to small misspec- ifications and noise. Indeed, if D. does not have support size K, but is within Lévy distance 8 of the family Ak. (0), then the proof of Theorem 3.8 still goes through if we choose + T-T-2 + v8. incurring an additive regret overhead of V8T2. The same overhead applies (up to logarithmic fac- tors) in the noisy model where valuations are subject to mean-zero 52-sub-Gauue Gaub-Gaassinn noise, since the associated convolution can only perturb demands by Õ(8) under the Lévy metric. We do not attempt to optimize this overhead but note that one is better off using EXP4 (as below) when ô >> 1/ poly
Remark 3.14 (Large K.). Our lower bound above can be restated as Qminn / KT d d3/3T//31).
When K. (1((T/d) /d)1/3 and the second term is active, POPS no longer has an advantage over EXP4 with naively discretized actions. In particular, one can run EXP4 with policy cover of log cardinality Öde-22) and price set (e, 2e, 1}, incurring regret overhead eT due to discretization. This gives a regret bound of Ö( VdV + ETT), which balances out d2/árp4/s after tuning. Characterizing the optimal regret in this large K. regime is an interesting question beyond the current scope.
4 Non-Contextual Refinements via Zooming
Our results from Section 3 leave key open question: what is the optimal regret dependence on K.? We resolve this question for the non-contextual setting, where d = and, without loss of generality, U = for all t. To do so, we employ adaptive discretization (aka zooming) methods from Lipschitz
8

---

bandits [13] with novel variance- confidence intervals and achieve regret bound of ((K.T)) Throughout, we label the K, types (.)) = = < ((2) < .... < B(K.)) and set g = 0.
Our algorithm, ZoomV, mirrors standard zooming [13] with two key adjustments. First, since revenue is only one-sided Lipschitz, we use a dyadic price selection rule inspired by [24]. Second, our confidence intervals incorporate empirical variance, a method previously used for variance-aware K-armed bandits [2]. In more detail, ZoomV maintains a set S of active prices in [0, 1] and a variance- aware confidence interval for the expected revenue at each p E S. Each active price "covers" an interval of neighboring, larger prices, with the width of this covering interval scaling proportionally to that of the confidence interval. The intuition is that small increase in price can only marginally increase expected revenue, so it is not worth exploring such covered prices. Initially, every price in [0, 1] is covered by some point in S. At each round, ZoomV optimistically chooses price S and updates its confidence and covering intervals. If after the update there exists an uncovered price, then we add a new point to which covers it, maintaining the invariant that every price is covered.
Theorem 4.1. ZoomV (Algorithm 4) achieves regrer { (oninvKK,T V T2/3)) for non-contextual pricing, without knowledge of K.. This is minimax optimal up to logarithmic factors when K. >
To bound regret, employ a variance-aware zooming dimension which controls its performance. For comparison, we first recall the definition of the standard zooming dimension, which characterizes a certain complexity of the expected reward function rev, (p). For each 5 > O. write X == (p E [0,
gap.(y) (p) S 8) for the set of 5-approximate revenue maximizers. Write N(X, 6) = N(X. 1,6) for the smallest d-covering of set X S R. Then, for each 0, define the zooming dimension
ZoomDim(c) (c) = inff 2 0: N(s. 6/10) S co vS > 0}.
Standard zooming techniques imply that ZoomV achieves regret c2/(2+2)22-1/22-22 when ZoomDim(c) S 2, even with confidence intervals that do not incorporate empirical variance. Since the price interval [o, 1] is one-dimensional, one can bound ZoomDim(c) < 1 for = 0(1), giving regret ) Moreover, the set X5 of approximate revenue maximizers is contained in the union of K, intervals preceding the unknown types, where the interval corresponding type ((+) has width 5/ ((()) I 5 5/dem, (g(K.)). This implies ZoomD (omoDiim(<)) (c) = 0 and gives regret O(VcT), but only for c= OK, /dmm, (em,.(((.)))) (O(K.))). which may be arbitrarily large for worst-case instances.
To remedy this, we incorporate variance, writing o² (p) = p?dem,
dem. (p)) for the revenue variance when p is played. For the problematic types above with low demand, variance is also low, and the confidence intervals of ZoomV are designed to adapt to this. Specifically, our proof in Appendix D.2 shows that the regret of ZoomV scales according a variance-aware zooming dimension, defined as follows. First define the variance-weighted covering number (X, == inf (nf(_ (x): X' is a 8-cover of X}. Then, for each c >> O, we set
ZoomDimV(c) = in 2 0 (x((,,010)) S cō V6 0}.
Note that ZoomDimV(c) < ZoomDim(c)) c). since (p))) < 1. Moreover, we show ZoomDim (0omDim(10K.) = 0. implying the desired Ö(y K.T) regret. The lower bound follows from Theorem 3.8 with d = 1.
Remark 4.2 (Comparison to [4]). The non-contextual setting was previously studied by [4], whose -5
Algorithm achieves regret Ō ((KK,T) +VV++1,, where V = max (o(K.))*
They maintain a set of intervals which contain all types with substantial probability mass, gradually refining these intervals until they are all of width O1/2) at which point they employ UCB over the intervals' left endpoints. Unfortunately, the instance-dependen term VVV + 1) can blow up to infinity for worst-case realizations of D. E AK, (10, 1]), in contrast our guarantee.
5 Improved Performance with Ex-Post Type Observability
We now study dynamic pricing with heterogeneous buyer types under the additional assumption that the learner can identify each arriving type. That is, after setting price pt, the learner observes the purchase feedback 1 (u,, 0.) 2 pt} and some information about the sampled type 0,, We consider the two models of observability. In the first, the learner only observes an identifier 2, E [K,) that specifies which of the K, candidate types was drawn. In practice. the learner need not know K,

---

priori. Here, we design an algorithm that matches the Ö(K, VdT) regret bound of POPS and can be implemented efficiently, using a contextual search algorithm for K2 1 as subroutine. In the second model, the learner observes the full type embedding 0g E O Here, we show that best-responding to simple plug-in estimate for D, achieves an improved regret bound of
min(K,,d)]]
Observed type identifiers. Our algorithm for the model where the learner only observes the identifier uses K, = 1 contextual search algorithm, ProjectedVol Wlmue [18], as a subroutine. We maintain a separate instance of this ProjectedVollum algorithm for each observed type and keep track of the empirical type frequencies along with the number of times we've explored each type. It then adaptively chooses which types to explore (or exploit) based on confidence estimates for the type distribution. We present the full algorithm and prove the following regret bound in Appendix E.I.
Theorem 5.1. Consider contextual dynamic pricing with ex-post type observability where the learner observes which type 2z. E [K_] arrived. Then, Algorithm 5 achieves regret Ö(K, v (T) and takes no more than time poly(K,, d, T) per round.
Observed type vectors. If the full type vector O, is revealed the end of each round, we can achieve improved regret with a simpler algorithm. Indeed, writing D, Er= òe, for the empirical type distribution after round I, we take each as the best response to D along the current context.
Theorem 5.2. Consider contextual dynamic pricing with ex-post type observability where the learner observes 0, E ② at the end of each round. Then the algorithm which plays P1 1/2 and best response Pt = br D.-,(uu, (u4) for remaining rounds achieves regret /nmnn(K, K., d) Each price can be computed in time poly (oly(K,,))
The proof in Appendix E.2 uses VC dimension bounds to show that the empirical revenue function rev D. converges uniformly in both arguments (price and context) to the true revenue function rev..
Discussion
In this work, have introduced contextual dynamic pricing with heterogeneous buyers. Our main algorithm achieves regret bound of Ö(K* VdT),, optimal up O(vK.) factor and logarithmic terms. Our analysis bounds the disagreement coefficient by leveraging a novel decomposition lemma for aggregate demand functions with K. breakpoints, thereby ensuring an efficient exploration- exploitation tradeoff. Additionally, we propose variance-aware zooming algorithm for the non- contextual pricing case, improving regret dependence on K, by incorporating adaptive discretization methods from the Lipschitz bandits literature. Finally, under stronger observability assumptions on the buyers' types, we develop efficient algorithms that significantly reduce regret to O(ymin [K, d)T), demonstrating the potential benefits of richer feedback in dynamic pricing settings.
There are several natural open questions, the first revolving around computation. The run time of POPS scales with the size of the discretized model class, which is exponential in K, and d. It would be interesting to see if there is a way to alleviate this exponential dependence, while achieving similar regret bounds. The second question around the optimal dependence on K, for the general, contextual case. While in Section 4 we showed how to optimize the dependence of our bounds on K, it is unclear how to scale this approach for the contextual version of the problem. One starting point could be the results on Zooming techniques for contextual bandits (see e.g.. 26). Finally, it would be interesting to see if our results can be applied to more broad families of settings where a learner tries to learn from heterogeneous agents while obtaining only single- bit feedback: for example, it is unknown if the approach presented in this work generalizes to general contextual search settings (i.e., with s-ball or symmetric loss) or if it generalizes for settings that share some core properties with pricing, but differ in the fundamental techniques used to address them (see e.g., 10).
Acknowledgments and Disclosure of Funding
The authors thank Jason Gaitonde and Oliver Richardson for helpful discussions on high-dimensional probability and algorithm design. We are also grateful to the Simons Institute for the Theory of Computing, as this work started during the 2all'22 semester-long program on Data-Driven Deci- sion Processes.
10

---

References
[1] K. Amin, A. Rostamizadeh, and U. Syed. Repeated contextual auctions with strategic buyers. Advances in Neural Information Processing Systems, 27, 2014.
[2] J.-Y. Audibert, R. Munos, and C. Szepesvári. Exploration-exploittiio tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19):187--1990, 2009.
[3] S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 02 2013.
[4] N. Cesa-Bianchi T. Cesari, and V. Perchet. Dynamic pricing with finitely many unknown valuations. In Garivier and S. Kale, editors, Algorithmic Learning Theory (ALT)), 2019.
[5] M. C. Cohen, I. Lobel, and R. Paes Leme. Feature-based dynamic pricing. Management Science, 66(1 (6911)49921-4443, 2020.
[6] Fan, Y. Guo, and M. Yu. Policy optimization using semiparametrie models for dynamic pricing, Journal of the American Statistical Association, 1196555):552-56, 2024.
[7] D. Foster, A. Rakhlin, D. Simchi-Levi, and Y. Xu. Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement based perspective. In Proceedings of Thirty Fourth Conference on Learning Theory (COLT), 2021.
[8] J. Foster, S. M. Kakade, Qian, and A. Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487 2021.
[9] S. Hanneke al. Theory of disagreement active learning. Foundations and Trends@ in Machine Learning, 1(2-3):131-309, 2014.
[10] C.-J. Ho, A. Slivkins, and J. W. Vaughan. Adaptive contract design for crowdsourcing markets: Bandit algorithms for repeated principal-agent problems. In Proceedings of the fifteenth ACM conference on Economics and computation, pages 359-376, 2014.
[11] A. Javanmard. Perishability of data: dynamic pricing under varying-coefficieng coefficient models. Journal of Machine Learning Research, 18(53)11-3,, 2017.
[12] A. Javanmard and H. Nazerzadeh. Dynamic pricing in high-dimensions. Journal of Machine Learning Research, 20(9): 49, 2019.
[13] R. Kleinberg, A. Slivkins, and E. Upfal. Multi-armed bandits in metric spaces. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC '08, page 681 681-699 690., New York. NY, USA, 2008. Association for Computing Machinery. ISBN 978 1605580477.. doi: 10.1145/137437..133 137 URL https://dol org/10. 1111111111111 1374376.77777 1374475.
[14] R. D. Kleinberg and T. Leighton. The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In Symposium on Foundations of Computer Science (FOCS), pages 594-605, 2003.
[15] A. Krishnamurthy, J. Langford, A. Slivkins, and C. Zhang. Contextual bandits with continuous actions: Smoothing, zooming. and adapting. Journal of Machine Learning Research, 21(137): 1-45, 2020.
[16] A. Krishnamurthy, T. Lykouris, C. Podimata, and R. Schapire. Contextual search in the presence of irrational agents. In ACM SIGACT Symposium on Theory of Computing (STOC), 2021.
[17] A. Liu, R. P. Leme, and J. Schneider. Optimal contextual pricing and extensions. In Symposium on Discrete Algorithms (SODA), 2021.
[18] I. Lobel, R. Paes Leme, and A. Vladu. Multidimensional binary search for contextual decision- making. Operations Research, 1366 2018.
[19] Y. Luo, W. W. Sun, and Y. Liu. Distribution- contextual dynamic pricing. Mathematics of Operations Research, 49(1):599-6188 2024.

---

[20] A. Maurer and M. Pontil. Empirical bernstein bounds and sample variance penalization. Conference on Learning Theory (COLT), 2009.
[21] R. Paes Leme and Schneider. Contextual search via intrinsic volumes. SIAM Journal on Computing, (1): 125, 2022.
[22] R. Paes Leme, C. Podimata, and J. Schneider. Corruption-robust contextual search through density updates. In Conference on Learning Theory (COLT), volume 178, 2022.
[23] R. Paes Leme, B. Sivan,
Y. Teng, and P. Worah. Pricing query complexity of revenue maxi- mization. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 399-415, SIAM, 2023.
[24] C. Podimata and A. Slivkins. Adaptive discretization for adversarial lipschitz bandits. In Conference on Learning Theory, pages 3788-3805. PMIRR, 2021.
[25] Shalev-Shwartz and Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[26] A. Slivkins. Contextual bandits with similarity information. In Proceedings the 24th annual Conference On Learning Theory, pages 679-702. JMLR Workshop and Conference Proceedings, 2011.
[27] A. Slivkins et Introduction multi-armed bandits. Foundations and Trends@ in Machine Learning, 12(1-2):1 2019.
(28) J. Xu and Y.-.. Wang. Towards agnostic feature-hased dynamic pricing: Linear policies vs linear valuation with unknown noise. In International Conference on Artificial Intelligence and Statistics, pages 9643-9662. PMLR, 2022.
[29] T. Zhang. Feel-good thompson sampling for contextual bandits and reinforcement learning. SIAM Journal on Mathematics of Data Science, 4(2):834-855 857, 2022.
[30] S. Zuo. Corruption-robust lipschitz contextual search. In C. Vernade and D. Hsu, editors, P Proceedings of The 35th International Conference Algorithmic Learning Theory, volume 237 of Proceedings of Machine Learning Research, pages 1234-1254, PMLR, 25-28 Feb 2024.
12

---

Appendix
A Extended Discussion on Related Work
Our work relates closely to three lines of work: (I) contextual pricing/search; (II) non-contextual pricing; and (III) Lipschitz bandits.
(I) Contextual pricing/search. The closest line to our work is contextual pricing/search. In contextual search, there is a repeated interaction between a learner and nature, where the learner trying to learn a hidden vector 8" E Fd over time while receiving only single-bit bit feedback. Mathematically, at each round E [T], the learner receives a (potentially adversarially chosen) context
We E Rd and decides to query y/: E R.. The learner receives feedback o = sgn( (u,, 0*) ye) E (-1,+1) and incurs loss (e (u)) [5]. Notably, the learner does not observe ( (we, 0))
only the binary feedback Tt. When the loss function & corresponds to the lost revenue as result of posting price y/ (i.e., the "pricing loss"), this setting reduces to ours with a homogeneous buyer population, i.e., K. = 1. The contextual search literature has also considered two other loss functions: the symmetric/absslltt loss (ey,, (u, ))) := y/- (u,, I and the e-ball loss ( (we, (*)) = 1l - (u, 8 > E), which are motivated by settings other than pricing.
There have been two approaches in the literature for learning in contextual pricing and contextual search (for homogeneous agents/buyers). The first approach (e.g.. 5, 18, 21, 17) employs a version of multidimensional binary search: specifically, the algorithms maintain a "knowledge set" with all the possible values of 0* which are "consistent" with the feedback that nature has given thus far. Similar to traditional binary search, the query point is chosen to be the point that (given the nature's s feedback) will eliminate roughly half of the current knowledge set. As the knowledge set shrinks, the learner ends up with a small knowledge set for the possible values of 0*; this is enough to guarantee sublinear regret. The series of works in [5, 18, 21, 17] optimized regret bounds for the three different loss functions (i.e., symmetric, E-ball, and pricing). The specific algorithms were different at each paper, but they all maintained "binary search" flavor. Most of the algorithms employing a multidimensional binary search approach can be "robustified" to very little noise in the agents' responses; since the learner will irrevocably shrink the knowledge set according to the feedback received from nature, they can only afford very few mistakes.
The second approach (e.g.. 12, 11, 6, 19) focuses exclusively on pricing settings. This approach uses regression-baie algorithms for learning the correct price and needs to assume stochastic noise in the buyers' responses. There have also been works studying other aspects of contextual pricing (e.g.. strategic agents [1] and unknown noise distribution [28)). Apart from the methodological differences with our work, both streams of literature focus on a homogeneous agent population and cannot be readily adapted for heterogeneous population setting.
Moving closer to the heterogeneous agents problem, [16] studied "corruption-rohuss" contextual search, where the agent population is mostly homogeneous, except for C o(T) corrupted agent responses. Their regret bounds were subsequently strengthened by [22], but the latter approach only works for contextual search with absolute and e-ball loss and does not cover the pricing loss. This model has been also studied with a Lipschitz target function [30]. Learning with corruptions can be seen as a first step towards learning from heterogeneous agents, but the approaches above do not scale appropriately for truly heterogeneous agent populations. In contrast, we focus on fully heterogeneous settings, where we do not constrain the number or the size of the different buyer types.
(II) Non-contextuall pricing. The special case of d = 1, where there is no context to inform decision- making, was introduced by [14], who studied non-contextual dynamic pricing for homogeneous, stochastic, and adversarial buyer population. For the adversarial buyer population, the authors assumed that there can be T different valuations and showed tight regret bounds of ( In contrast, in our setting, we assume that users are "clustered" in K, types), and so the lower bound of 2(T2/33 of Kleinberg and Leighton [14] does not apply.
The closest to our work is the work of [4], who consider pricing a heterogeneous agent population with an unknown number of types, but the types are still limited to be less than o(T). Throughout the paper, we discuss how their bounds relate to ours for the special case of d 1. None of the aforementioned techniques readily generalize to contextual pricing settings.
13

---

(III) Lipschitz bandits. Finally, our work is related to the literature on Lipschitz bandits. Although the pricing loss is not fully Lipschitz, it has recently been observed that satisfies a one-sided
Lipschirzness. This allows to leverage techniques from adaptive discretization [13] ] to obtain improved bounds for 1. Zooming had previously been applied to pricing (see, e-g., 24), but these algorithms are insufficient for the K, -types setting. Indeed, their performance scales with a zooming dimension ZoomDim that is too large here, On the other hand, ZoomV uses variance-aware confidence intervals that its performance scales with smaller, variance-aware zooming dimension ZoomDimV. In particular, while ZoomDim im can equal for worst-case instances, we show that ZoomDimV 0 (with lower-order scaling constant at most K,).
Finally, [15] consider contextual bandits with continuous action spaces, which encompasses the setting of this work. Their regret bounds cover the case where, for a fixed context, the expected reward Lipschitz the learner's action. Although their analysis can be adapted to the one-sided Lipschitz setting of pricing, their results either require stochastic contexts incur large regret due naïve discretization. Even the stochastic case, their regret bound scales with a policy zooming coefficient that does not appear to admit useful bound in terms of K.
B Proofs for Section 2
B.1 One-Sided Lipschitzness of Revenue (Proof of Lemma 2.1)
We simply bound rev) (p)) pp' de'm - pdemo(p) S demo(p)( -p) pp' using monotonicity of demand functions.
B.2 Pricing Implication of Lévy Metric Bound (Proof of Lemma 2.2)
By the definition of di, it suffices to prove the lemma when d = 1. The first revenue lower bound holds by Lemma 2.1. For the second, omitting the context and writing [x] = max(#, 0j, we use the Lévy metric guarantee to bound
re (T)
[br =]+ dem (lbrp E]+)
|br <]+ demp (brD - E)
(demand equals 1 for S 0)
[brp E]+ (dem (br 23)=
(dy bound)
[brn e|+ (demp (br s)
(monotonicity of dem
rev 2s
revn(brr)) 28
(br maximizes rev
brp dem br )') 25
brp (dem (br E) E) - 28
(d, bound)
br demp (brn:) 36
rev ( 3s,
as desired.
C Proofs for Section 3
To unify analysis of Sections 3.1 and 3.2, we introduce more general problem setup and algorithm.
C.1 Generalized Problem Setup
To start, we replace the price set [0, 1] with subset P S [0, 1]. which will remain [0, 1] in Section 3. but will be restricted to finite for Section 3.2. Then, instead of selecting type distribution D.. we have the adversary choose demand function f" which maps price E P and context u E l/ to a purchase probability I (p. u) E [0, 1). Then, at round
the adversary selects context u, E U and the learner posts price Pt E P. purchase decision y/ E {0, 1] is sampled independently from Ber(J" (pe, wz)). This abstracts away our previous notions of buyer types and values and will also model the smoothed environment of Section 3.2. We impose the corresponding notion of realizability.
14

---

Setting C.1 (realizabilityy general), Under the setup described above, the demand function f belongs known, finite class F of measurable functions from P to [0, 1].
Often, we shall fix a context and consider univariate (non-contextual) demand functions. Given a univariate demand function : [0, 1] [0, 1), we define the corresponding revenue function (p) p g(p), best-response bry arg m rev, (breaking ties arbitrarily), and gap gap, (p) (brg) - (p), For contextual demand function f : [0, 1] x u - [0, 1] and context U. write proj(J, u) for the induced univariate demand function + [(p u). We define r u) = revpro((S.w) (p), bry(u) = br proj((( gapy (P. u) = paPproj(S.w) (p), and proj(F, u) = {proj(f. u) : F). along with rev. = r. br, = bry-, and gap. = g.p,.. r.. Finally, we define
fis = sup dis dis((11))))) ((f(, f.(.)) F)),
well
generalizing the definition in Section 3.1. Regret is defined as the sum of gaps Σ gap, (Pr, uz).
C.2 Generalized OPS and its Regret Guarantee
We now present a extension of OPS and POPS to the generalized setup of Appendix C.I. Both can be recovered for appropriate choices of F and P, which we will discuss later. First, for a univariate demand function g [0, 11. price p. and purchase decision y, we define loss
(g = (g(p) y)² - (brg)
(3)
We now adapt OPS this setting, introducing GOPS (Algorithm 3).
ALGORITHM 3: COPS: Generalized OPS for Contextual Pricing with Finite Model Class
Input:
finite demand function class F, model prior μu A(F), optimism strength À > 0:
2 for each round t E [T] do observe context We: sample demand function ft pe: play Pt br (ux) and observe yt: update M(+1(f) x pe(f) exp( exp((Ex u.), Pt.))))))) for each f E F;
We prove the following regret bound.
Lemma C.2. Under Setting C.I, with model prior μl ((F) and optimism strength X 2 4/T, GOPS (Algorithm 3) achieves regret 25X(dis(F, 1)TTog' (T) + log(\//n(s>)//>
Our proof employs the following decoupling lemma.
Lemma C.3 (8). Let G be a finie family of univariate demand functions and fix g" E G. Then, for any A()) and 7y 0, we have
Ey [lo(br,) - g (brr)) < dis(9) (r + (( - -br
This is simply Lemma E.2 of [8] with function class ---g" ig E g} and A -+0 0. In proof, g and g" will be the projections of F and f* onto a fixed context u U.
The remainder of our analysis is a slight modification to that of [29], which we provide for complete- ness. For each round [T] of OPS. we adopt the following notation:
history up to round l: S, = {ur, Jr. Mr D
true univariate demand function: of = proj( uz).
univariate demand function posterior: Vt = proj(u,, u) == Law (proj(f, (proj( u)), sampled univariate demand function: Se = proj(fe: uz), so that pt = brg.
independently sampled univariate demand function (for analysis): ÿ: 14.
regret: REG, == rev.(b,, (br, (u.), we) rev. (Pc. u.) rev (pt) rev (pt),
15

---

least-squares errors: LS((g) = (o(pi) - (pi)))
"feel-good" (optimism) bonuses: FG+(g) = (br revsr (br )
loss discrepancies: (L) = (x Pt. 31) - , Vt):
potential function: Z, Es, log (n-it exp( Ei= ( uz))).
Our proof requires several supporting lemmas. The first is basic concentration result.
Lemma C.4. For e 2 O and a random variable X supported on (0, 1}. we have log Expp -cx)
(2ee² c) E. For X supported on [a, b), we have log exxp(eX) I cE X a)
Proof. For the first inequality, we bound
+ log Bexp(-cXX) S E/exp(-cXX - - S E[-cxX cX + = (5 c) E.
The second inequality exactly Hoeffding's lemma.
The next lemma mirrors Lemma 4 of [29]. This is consequence of the definition of A and the uub-Gaussianity of its components.
Lemma C.S. For round of GOPS (Algorithm 3), we have
3 log Eggur E sp exp(-ALo(g) - - By-e, LS,(g) + Agg. FG,(g) + +
note that this lemma does not rely on how pt selected.
Proof. Let g and y (yrlur denote the discrepancy between the observed and expected demand. Since demands lic in [0, Lemma C.4 with X gives
(eee pe) (er(sc(Pt) be independent. Let y- (p:)
By exp(-22 (p:) ) g(p:))) s exp(E(si(p)) - )((p))) exp(tLS.(g))
(4)
Moreover, we have
Ab. = - (s + (p:) - g(vi))
= - AFGr(g)
22 (p:) ((p))) (S((g) + AFG.(g).
Combining with (4) gives
Ey exp((AAL((1) < exp(-)1S.(0) + AFG)(g))
Therefore, we have
log gyy exp( ALelg)) < lo exp (L) AFG((g))
2
log E, exp (xp(- + log E, (xp(3)
where the last inequality follows by Hölder's inequality. For the first term, we use Lemma C.4 with X (g) and e
3 to bound
2 log(B exp(= exp(- (l))
2
- e) E, Lg:(g)
5 E, LS,(g)
3
3 2
16
For the second term, we apply the lemma with X = FG((g) and c= 3A to obtain
3 _x2
log E, (x)(3)G((()) < AE, FG)(g) + 2
Combining, we have
5
Egg (p((-A((g))
E, LS)(g) + FG;
FG:(g) + _
16
implying the lemma.
16

---

Our last helper lemma mirrors Lemma 5 of [29].
Lemma C.6. For round of GOPS (Algorithm 3), we have
3
( - (F) - + x (Z - -Z)).
41
This lemma also does not rely on how prices are chosen.
Proof. Recall that μl = Uni Defining Wi(f St) == exp(- -i= AL, ur])), we
have Z, = Es, log E f~wp Wi(1 St). Note that
Wi-1ff St-1)
p+( Eyngs Wi-1(f (S--1) (2(1).
We then bound
Ex-ps Wi(S (tt) St)
Z: = -1 + Es, log
E Bp-m W 1
B Wz-1(f St-1) (xp(-AL u)))
Z,-1 + Es, log
Erwms Wr-lff S(-1)
Z1-1 + +Es, log LogEiwg (rp, exp( - ue)))
(0) I 7 + S.-1.MM... log E we Egne exp( (-,+(g)
(6)
3 x² < Z (L) (EFG
where (a) uses Jensen's inequality and (b) uses Lemma C.4. Rearranging gives the lemma.
Now, return to Lemma C.2, where will finally incorporate price selection rule and the decoupling lemma.
Proof of Lemma C.2. For each round / [T', we recall that pt brg, and decompose
REG; = re (brgz) rev (pt)
r 9. (pt) revg; (pt)] - [rev (brg.) ) rev (br )]
reev ga (Pt) re (P:) - FG+(gt).
Conditioning on S,-1 and ue, we apply Lemma C.3 with
to obtain
E gev (pt) rev,; (p:) St-1. ue]
= Bywn [rev,(brg) - rev (br,)]
< BRn., [lg(br,) 97 (br,))]
1
S 24A dis(F, f-) log2(2X V e) +
Eg.gev [G((r,)) - 96 (br,))
41
1
24A dis 2 (4X Ve) +
E [
4X
Taking expectations over S,-1 and we we bound
1
E EREG,
24X f4) log (4X e) ELS. (0:) (FG(
41
242 f.) log (4X V ve)
+
; -
( Zz).
2 X
using Lemma C.6. Summing over t E [T] and noting that Z, = 0, we bound
x>
3
1 ZT.
B[R(T)) < T 24 (di
+
Moreover, by realizability, we have
ZT 2 Es, log(ui log(ll Wf" S)) (P)(((((.))
17

---

Combining, we obtain
B[R(T)) < 24Adis(F. (41 -41-1 Ve) + 3 2
(og(Hi(ff.)
(4x-1 ve)) log(ai (f.))
((25A(dds(F. (4X
s (T(33 log(un
desired.
C.3 Base Regret Bound for OPS (Proof of Lemma 3.3)
Under the general setup of Appendix C.I, we take to the class of demand functions induced by D, set p = [0,1]. 1.. and fix μ4 Uni By these choices, GOPS coincides exactly with DPS, as does our notion of regret. Thus, Lemma C.2 gives the desired regret bound of
((25X(dis(D,DD) 1) log2 (og(m)(D.)) OXATdis(D) D.) + log( (D)
C.4 Disagreement Coefficient Bound for Non-increasing Functions (Proof of Lemma 3.4)
Fixing f E F.V. V E A[00, 1]), and E [0, 1]. suppose that Ey S E² and [f(p) > f(p) 6, then f(4) > for all q S p by monotonicity. Thus, IP PP S p)8² I [f = e?. 6, we analogously have Faru(q 2 p)6² S Eg (f) 2.. Thus, for
Otherwise, if (p)
E A(2), we have
P Ppwp
Af
E F:
E [f = Al(l)) > 8)
e²) 82)
< P pmD
P Papr(q S
S)
V VP
82
2²
=²) 82
PP PPpv p~v
P S
+
P Pa +Pp
2 p) s
8z
2 82
82
Plugging this into the definition of dis finishes the proof.
C.5 Disagreement Coefficient Bound for Composite Classes (Proof of Lemma 3.5)
For any distribution E A(2), write 14 h4 v/2, for law of h:(p) when p conditioned on p E 2,, and let (1) = (p (p& E Zz). We then bound
82 P Pouule,
Ag Eg: [gp)) Ag(p)) > 6)
dis(g) = sup sup Einp, =.8>0vEP(2)
82 < sup sup Einpy Prner 2.550vE((2)
[f EF (v) Ey ( ~ =6)
82 Eingto
I sup sup c.520vEP(2))
E
(2 (ist))))ss(F)) dis(F)
Nd)s(FF,
as desired. Here, the first inequality uses that (g 2 (1) Enyer ([(+(x)) for some f F. and the second uses that P4 E A(X) and the definition of dis.
C.6 Base Regret Bound for POPS (Proof of Lemma 3.9)
POPS as generalized OPS. We observe that POPS an instance of GOPS (Algorithm 3), with discretized price set P Ps and smoothed demand function class FF = {demi, D E D) (where
18

---

each f E FF is viewed as function on Pe x 2/ rather than [o, 1] x 2f). Here, we view each Pr as the posted price instead of p.. Indeed, taking f* demf.. we have
Eige Ip,, up] = = (p:, uz)
and, for value distribution Q E A[0,, 1J) with smoothed demand function g dem we have (Q, pt, u+) (g, Pe, ue),
where l on the right hand size defined in (3). We do note, however, that the regret benchmark with smoothed demands and discretized prices differs slightly from the original benchmark.
Fixing the regret benchmark. Applying Lemma C.2 for this choice of P and F, we have that
log(Uu (D.))
E
(br, (we), u+) - (e,, uz)
- (225
Note that
T rev (pe, uz) = E
rev. (pt, uz)
so the regret bound above measures cumulative revenue in line with our original regret definition. Although the benchmark does not match that in the original definition, we have |rev (br[(u:) u)) rev, (br,(w)) (we). uz) ] = (s)) for all & [7'] due to one-sided Lipschitzness (Lemma 1). Consequently,
the regret of POPS is bounded by
B[R(T)) = ( TX(dis(F. - log(s1 (D+)) + ET
X
It remains to bound the disagreement coefficient by O(K)), giving the lemma. Our argument below mirrors that in the proof Theorem 3.2 but takes into account the smoothing and discretization.
Bounded disagreement coefficient. For each E U, the function (-mf(-.w) u) with domain Pe is piecewise constant with O(K)) sections. Indeed, the unsmoothed demand function dem, u) is piecewise constant with O(K)) sections, and smoothing can only introduce new sections at the O(K,) prices in Pe that are within distance e of a previous section boundary. Moreover, smoothing preserves monotonicity of demand functions. Hence, the function classes defining dis(F, are O(K,) comppostes of the nonincreasing function class. Applying Lemmas 3.4 and 3.5 then implies that dis(F, f.) O(.), giving the lemma.
C.7 Trajectory Coupling (Proof of Lemma 3.10)
Fix any round / with context n, and best-response price P.- Since I1/ Sú. 1:0 S E, feedback coincides with that which would have been obtained if D. = D with probability at least 1 conditioned on u, and p.. Since the update to μt is only function of u,, p., and y/ (notably, not the realized price Pt). we can iterate through all rounds and apply a union bound to obtain the lemma. O
C.8
Metric Entropy Bound (Proof of Lemma 3.11)
For part one, fix D' A(O) with di (D. < <2/2. Then, for all E U and [0, 1]. we have fb u) = Em.- [demp (max{p - 6, 03, u)]
Note that the maximum unneeded since proj(D,u) D, u) is supported on [o. 1] and places no mass on negative values. Writing Q proj(D, D. u) and Q' = proj(D* D', ,2),,, we then have
1fb(0.u) f5- u)l = (0or0))(()0))) (dem (p- 8) demo (f 5)]
1
L demp(ø 6) dem (p- 5) d8
1
8 dtm)(t) dem (t) dt
19

---

d1) demor (1) dl
Writing T = 22/2, we further have
!. demo(t) demq/ (t) dt
1+7 demo (t - -% demo (t) df
demo(1 - demor (1) dl +
S 2T,
where the last step uses the fact that dr. dq. Consequently, we have (V, u) (p, u) S ! .2
T. A symmetric argument gives the reverse bound. = 2T= as desired.
For part two, let C = [C1. C2.......... C denote the intersection of the standard partition Rd into cubes of side length s/ v with θ C [0, 1jd. Denote the lexicographically smallest vertex of each C₁ by C₁s and note that log(n) Oddlog(//))) Given any E A (#), we define the initial discretization Dn Σi= dr. We obtain the final discretized measure Ó by rounding each weight to neighboring multiple of e/ K (choice doesn't it matter so long this is always possible). Then, for any context E gd-1 and price p E [0, 1], we have
maintain unit mass,
Pe-D 0) p) IP P (u, S S
POND (u, 0) S =) - (00p0(((u00) S S.
using that each cube in C has diameter and that the mass in each cube was perturbed by at most e/K' K (so with K cubes the probability of any event is shifted by at most e). Thus, dD, D) s Using balls and bins, we can thus bound
+ K/E
N(Ax e) =n n
S nn (2K/e)* exp(O((dlog(dde) + K logg (K/e)))).
K
as desired.
C.9 Proof of Theorem 3.8, Upper Bound
Upper bound. Fix & = T and À = vd/T. We now construct D and p1. Write M = [log T7, and, for = 1,...,,,, take D. to a minimal (s2 (2//2)-cvver of 22:()) under the Lévy metric. By Lemma 3.11, we have log [D,] O log 1/E). Now set D = D1 U... U Da and take (D) (21(D())~ for D D. This ensures that log( Log(1/Hı (D)) ( Tog for D E D,.
Assume without loss of generality that M 2 log K.; otherwise, the regret bound is vacuous. Then, there exists Đ E D Plog K. S D such that di. (D, D.) S /²/2 and |demm dem bo S E, again using Lemma 11 Thus, by Lemma 3.10, the realized trajectory of POPS (u, Pt. Pt. V1 ) can be coupled with an alternative trajectory {u', f4. p/,, T of POPS with type distribution D, such that (ut, Pe. ye 1T [ut, P.. v/3f=1 with probability at least eT. By Lemma 3.9, we have
rev (14), pev ai) (E(T]
-VT log (D)) Ō(K.VaT).
At this point, we can use the coupling guarantee and the bound d1 (D. D.) < to show that the left hand side above and the true expected regret differ by (EE2T) = 0(1), giving the theorem.
Specifically, by the coupling guarantee, we have
E E(R(T)) <
rev. (br, (ut), we) rev. rev. uz)
E
+ +
rev. (br, (u6), w/) - (ve,
E +1
20

---

Since D.) < Lemma 2.2 implies that rev, (br, u4) S revp(br, u4) + O(=2) for all rounds t. We further have
Elrev. u/) d/ Pol - rev (De, u()
S rev (Pe, u/) +
Eirev (p/: u4) u/ - Prl +
Eirev (p/. u/) p/ p. El +
Combining the above, we obtain
B[R(T) E
rev, (br, (1)), u4) - rev. reve u4)
E
+ +
$ E
rev (br b u4) - rev.(pe: u4)
E
+ +(ETT))
T
T
E
rev / (br (bbb(((()))) (14), un)
3
- E
E(rev, (pe, u/) u/ Pel E
+ 0
E
rev rev ( (u(), u4)
E
- E
uhe pl, E9 E rev d (p/, w/)
3 + +
$
E
rev (er (bbr((u)) (1(),, u4)
rev (p's u/)
E 01
T
$
E
rev (br (1))) (1)),
Σ
rev b (p/x u4)
+0
1=1
=(KKvaTT)
desired.
C.10 Proof of Theorem 3.8, Lower Bound
Previously, [4] gave lower bound of ( (K,T) for the non-contextual case. We now modify their one-dimensional construction so that it can be cleanly tensored into d dimensions, when K, 2 4.
One-dimensional construction (K, 2 4). Starting in ID, we define valuations 02 .... S
"K, by vi = aK. -6.22-2 Define the base distribution Qo on (uI,..., PK. } by
i
[K. - 1] i K,
Qo(v:)
2K.
2k.-2
2
Observe that each valuation 22 has the same expected revenue of 1/2. Indeed, we compute
dem@. (v:) = Σ Qa(1,)
125
(K, i)
2K.
2
2K,
(5)
2K, - 2
and
2K, -2
(22,, -i
1
revo, (w:) v.demq. =
4K, 2i - 2
2K, -
2
21

---

Now, for E f2..... K, -1,, and increasing the probability of vi by the some small 0, to be determined. That we define
1}, we define distribution Q2 by slightly lowering the probability of 2
E, i ==
2k. + E,
Qf(1;)= =
i = K.
O.W.
which is well-defined so long as S 2K.-2' In contrast the construction in [4], our 2j distributions share the same multiset of probability weights, differing only in the locations of the perturbed valuations, This allows us to tensor these problem instances into a d-dimensional instance without leaking information between instances.
Moreover, the hardness result of [4] is maintained, which applies even if K, is known to the learner. The proof is quite similar, so we defer it to Appendix C.11.
Lemma C.7 (Regret of one-dimensional family, K, 2 4). Fix any number of types K2 2 4 and T 2 K3 Let A be any algorithm for non-contextull pricing. Then, for tuned and an instance Q. drawn uniformly at random from {Q₂ jeej)e....... (e.(.....K.-1)) A suffers expected regret at least O(VK.T).
Tensoring one-dimensional instances. To extend these one-dimensional distributions into d dimen- sions, define the base distribution Do E ( 1)d)) as follows. For E [K.], let 0, = =['..... u.] e K. Rd = Qo(e;), and take Du == Σ ur,ōg. That is, 0 E [0, 1]dd has all entries equal to and wi the probability Du places on 6,, taken to match Qu vs. By design, the marginal distribution of
Do along each coordinate is Qo. Now, for selection j = (J1: (J1.....Jal dd)= E f2...., K. - 1)d define the perturbed instance D, by starting from Do and modifying
follows:
Adjust the probabilities wy and W2 by wi < w1 - E and W/ + W2 t..
For each dimension e [d], permute the tth coordinates of the 0g vectors that the marginal distribution of their éth coordinates coincides with 2₁,-
Specifically, we define D, = =ER úr00 where
2k -2 2K.
E,
+ E,
i =
ú ==
i == K.
21
2k.-2' o.w.
and 1. = Ua(t), for any permutation a of [K.] such that a(je - = 1, o = 2, and (K.) K.. Simply swapping je - and and je with works unless je 3, in which case one can send 2 + 1, + 2, and + 3. As claimed above, this construction ensures that for each dimension E [d], the marginal distribution of Dj is Qic- Indeed, for each E [K.]. we have
2K.-2 6, je
2K. tE, = je i i= K. O.W.
POWDY =1)
2K.-2: (v.)
Lower bounding the regret. For the contextual setting, we sample selection j = (j1 .1.....jjl ja) (2.... K, - 1]d uniformly at random and set D, to the perturbed instance Dj. We consider stochastic contexts, where each u, the standard basis vector along coordinate é, sampled uniformly at random from [d]. Now, fix any contextual pricing policy A for this this randomized environment. Our level intuition is that, for each coordinate E [d]. the sub-environment during the roughly T/d rounds when l, = mirrors that Lemma C.7, and so we incur regret 2( D(VK,, K,, T/d) during such rounds. Summing over é E [d] then gives the lower bound.
To formalize this, note that each coordinate sampled at least T' [T/2d] times under an event with probability at least 1 - 1/T. This follows by Chernoff bound a union bound over coordinates
22

---

since T 2 8d (2g( Then, for each & E [d], there is natural policy A induced for the non- contextual setting of Lemma C.7 with time horizon T". To start, Ae samples valuation distribution Qe uniformly random from (Q)) K. for each l' * Further, instantiates simulated copy of A and a counter initialized at 1, tracking the round of this simulation. Then, for round ..... T', , Ae performs the following:
1. If > T, play pr = 1 for remaining rounds and terminate. 2. Otherwise, sample & uniformly from [d].
3. Submit the associated context as u, to and receive suggested price P--
4. If f f, play price Pr' Pr. submit the purchase feedback ÿr = ye A, increment 7 <- + 1, and continue to the next round.
5. Otherwise, submit Ür ~ Ber(x:) where x is the demand Q₁, at pr. increment T + + ++1 1, and return Step 1.
By design, if A is run under the setting of Lemma C.7, its simulated copy of A experiences feedback indistinguishable from that described our setting above. Thus, writing Te for the rounds of our initial setting where & = l and conditioning on & (under which [Te] 2 T"), we have
E
Σ TET
gap. (pr.u) un)
3
2 E(RA(
2 E[RA
= _2(KK.//d)
since 7 2 K and T 2 2d. We then compute
([RA(T)) (T) 8] -1
E
gap, (pt. ue)
E -1
(=1
LET
E
gap+ gap+(pr, m))
E -1
t=1
LIET
= KTT),
as desired.
Small K.. If K. = 2, simpler mie-dimensional construction suffices. We set i1 = 1/4, 8/2 =
1/2, that demo, (v1) 1, demo. (v1) 1/2, and revo, (v) (v2) = 1/4. We then define (1) = 1/2 4 and (12)2 = 1/2 + e, so that rev (v)) 1/4 and revo (v2) = 1/4 e/2. Moreover, taking we assumed), we can simply employ the standard 2-armed bandits lower bound (e.g., using the same techniques as in Appendix C.11) to show that no algorithm can achieve regret o(VT) for both instances. Our argument above, tensoring one-dimensi instances and obtaining contextual lower bound, still goes through, since Q+ and Q- share the same set of probability weights, giving lower bound of Ω( ((VTd) for a worst-case instance. For K, 3. we can easily tweak the K, = construction place negligible mass at V3 and the lower bound still holds.
1/2, Q0(11) Qu(22)
1/vT (valid so long as T > 4. which
C.11 Non-contextual Lower Bound (Proof of Lemma C.7)
We first recall some basic information theory. Write KL(p (I == Ep log (lggd//dq)) for the Kullback- Leibler divergence between distributions and g the same domain X. When and q are Bernoulli distributions with success probabilities a, b E [0, 1], we write KL(a || b) = KL(p) (p q)-
Fact C.8 (Pinsker's inequality). For p. 9 E (X) and M 2 O, we have
E I, [f & M / KL q). f
sup
23

---

Fact C.9 (Bermoulii KL bound). For a. E [0, 1] such that a + ò E (0, 1), we have
82
KL(a |I a +8 (a + 6)(1 60(
a -0- 5)*
Fact C.10 (KL chain rule). For distributions p, q over sequences X = ="==XI,--. Ex)
EX",
KL(plla) Σ Ex Ex--p (pL( XI....,,,-I))lllee (1x X XI....,X.-I))]
where | x1) denotes the conditional distribution of X; under given X1. X
Next, we observe that, if the buyer valuations are drawn from 2,, the price vj achieves expected revenue at least 1/2 + Q(s) whereas all other U, of Vj achieve revenue 1/2. Indeed, the demand function of Q2 is identical to Qo at all vs + Vg. and at we have
revq, (uz) = (d (1²) + E) = 1/2 E0y 2 1/2 E/2. Thus, gapq, (v)) 2 e/2 1(i j}} Also, for i 1, Eq. (5) implies that 1/2 demou (v:) 1 5/6.
So, imposing that our perturbation size e is less than 1/12, have that
KL (v:) demo, (u:)) < I -2
(6)
for all i,j E K2,
Now, let J be drawn uniformly at random from ( ......,,, K. - 1}. so that Q, coincides with the random instance from the lemma statement. Conditioned on let the valuations V (V...... Vrr) be drawn i.i.d. from QJ,iee, V ~ ~ Under this set up, is the unique optimal price, and playing by for i * J incurs regret (s)). We will be comparing to the alternative world where V ~ Q and all arms have equal expected revenue of 1/2. All expectations under this alternative will be clearly denoted as such.
Without loss of generality, assume that the fixed pricing algorithm A is deterministic (since may condition on any internal randomness of A).. Applying A to instance QJ induces a random sequence of prices Pi..... Pr. where Pt each is function of the previous purchase decisions Y, 1 (V, 2 Pr) for r E [t 1--1] 1]. Without loss of generality, we may assume that each P. belongs to U2.-... ,.. -,,,-K,,,, since rounding up the nearest element of this set can only increase expected revenue. Thus, defining the empirical frequencies
N₂ IIP:=
we have Σ/=2 N, T. Conditioned on J, the regret of A over the rounds is
RA(T) = Σ gapo, (Pt)
T
I(P
1=1
2 (T- Nj),
Thus, we have in expectation over J and V that
y (T)) 2
(T - y (Ny)).
(7)
We next control Ey,vr [Ny) using the KL chain rule and Pinsker's inequality. Fixing (2...., K. 1}. write q-(-) and go(-) for the induced distributions on the entire purchase sequence yr (Y,,..,, Yr) under Q, and Qu. respectively. By the chain rule, we compute
KL(go q3)) = Σ
Eyr ~mo [L Y....., Y...,,,,))) 1) (Y, Y....,,y. Yz-1))]
24

---

ByT~uy ~upo
[K Pt) (Y Pi) -(P; = ,
By ~00
[LL(dem demo, 1(P: = u,y)]
1=1
< 24
E EYT 10 [1[P] =,}
(Eq. 6)
t=1
24e Eyy [
In short, Yo and Qj only distinguishable for rounds in which A selects price vij, and even in these rounds their divergence is bounded. Now, since N, is deterministic function of y for fixed A,
Ey By ~ [2y] S go [Ng] + FT V 224Ev-q.lN.)
Taking expectation over / then gives
[Nv & EJ EVT NJo] + ET /2AB, [Er [N
Since ΣØ²2 N, T and J is uniform over {2....,,, K, - 1}. K. 2 4, follows that
1 K.-1
E, E ev No1]
Σ
EVT [N₃] = T T
$ K. 2
K.-2
1=2
Plugging this into (7) gives
E (R())] 2
E
(T
E,,t
E T EV 24
1
T
2
K. -2
We now set 3/24 / (K. 2)/T.. Our construction required that S 11/(2,,-
- 2) and S 1/12,
which are satisfied under assumption that T > K.. This yields a final lower bound of
2 8 E 24 K. -2 2
= (((V.TT)
as desired.
D Proofs for Section
To fully specify the algorithm, we introduce the following notation:
Since our analysis exclusively reasons about the true type distribution D., we abbreviate dem dem,, rev rev., gap gap+, and br br.. For each price p E [0, 1] and round E [T'], we write
Te(p) = {r E [t - 1] = p} for the set of previous rounds where p was played,
nx(p) = [T)) for the count of these rounds,
pt(p) = [z(p] ETET(() p9: for the average revenue during these rounds,
Vi(p) = -T ΣFET, (pi) n4 ( for the sample variance, and
d2(p) p² de - dem(p)) for the population variance (unknown to the seller).
When nx(p) O, set ur (p)
v.(p) O. When (p) take Vt(p) ac.
Defining confidence radius r. (p) = / 10V((p) log T 12 log()))) (taken +oo if n<(p) < 1), ne(p) m.(p)
variant of Bernstein's 's incquality shows that [p((p) rev(p) < re(p) w.h.p. (see Lemma D.3).
25

---

ALGORITHM 4: ZoomV: Variance-Aware Zooming for Non-Contextual Pricing
Initialize: active price set
( : 1,,,..... [logg [1};
for each round 1. [T] do play Pt E arg max index; (q): 3
observe = 1{0, S Pt} and update r (P:); if price p 1/T becomes uncovered then
- min q E S : ( > pc)
S SU ((p + /)
Write UCB:(p) = pc(p) + r (p), so that rev(p) - UCB,(p) w.h.p.
We say price p is covered by q S S p [g. rr(g)] and q is the largest active price no greater than i.e., q= max E of S p). One-sided Lipschitzness of the revenue function (Lemma 2.1) implies that rev(p) rev(g) S (g) w.h.p.
Define the index of price S as index, (4) = UCB,(1) + rx(2) Each price p covered by some satisfies rev(p) S index
D.1 Main Regret Bound for ZoomV (Proof of Theorem 4.1)
As mentioned, the lower bound follows by that in Theorem 3.8 when d = 1. For the upper bound, we prove a generic regret bound in Appendix D.2 depending on the variance-aware zooming dimension.
Lemma D.1. For e > 0, ZoomV achieves regret ((c2 T2-1/(2+))), where z = ZoomDimV(c)).
Next, we prove the zooming dimension bounds claimed in Section 4. Lemma D.2. We have ZoomDimV(10K.)) 0 and ZoomDimV(10)) ZoomDim(10) 1.
Proof. For each 5 > 0 and type E K.)] let X denote the set of activated arms with gap, (p) S that lie in the interval (0(--1), }()) to the left of type i. Since revenue is linearly increasing within each such interval, with slope d; dem( the gap condition requires that each E Xg also satisfies 2 (() 5d;- Moreover, for p E X((),, we have (p()) S d, Thus, we obtain
(X 8/20) < Σ (X. 8/20) - Σ KE[K.]
10d dc S 20K.,
KE(K.)
implying the first bound. For the second, we note that N(X,, 5/20) & N 1], 5/20) - 208-1_
Combining the two lemmas gives the theorem. Indeed, the VK.T bound follows by Lemma D.1 with e = 10K, and 0, using Lemma D.2. Similarly, the T2/3 bound follows by taking c = 10 and 1.
D.2 Base Regret Bound for ZoomV (Proof of Lemma D.1)
We begin with a few helper lemmas. Throughout, we assume that 2 3 (otherwise the regret bound holds trivially). Our proofs mirror those of similar lemmas in [27]. with small adjustments to handle the variance-adjusted confidence radii and the dyadic price selection rule.
Lemma D.3 (Concentration). Write Eetean for the event that
10 100 log me(p)
126 log(T') ne (x( -
(p<(p) rev(p)) S rx()) <
for all t E [T) and all E [0, 1]. Then P(Eteea)) 2 87
Proof. For fixed p E [0, and E [T], Theorems 10 and 11 of Maurer and Pontil [20] imply that
(μ((p) rev(p)) S (x(p)
26

---

11 log T me(p) -
(ox(p) vV((p) Σ
with probability 1 1 87-5, We note that similar bounds appear in [2]. which inspired adjustments to the confidence intervals. Under this event, we further bound
10V, (p) log T
12 log mp(p)
(p()
ne(p)
10o (p) logT
10 T (+(p)
lo
12 log'T (p(
(x(p)
nx(p) -1
(p) log T
126
$
(p)
me(p) -1
Taking union bound over the above must hold for all E [7] with probability least 1 87-4 Now, the same Chernoff bound argument used in Claim 4.13 of Slivkins et al. [27] implies that (p) rev(p)] (p) for all p E [0, 1] and t E [T] with probability at least 1 87-2 One technical observation is that Claim 1.13 requires that the set arms every played by the algorithm is
finite. This holds for ZoomV due our dyadic arm activation rule.
Lemma D.4 (Covering invariant). At the beginning of each round, every price p 2 1/T is covered by some active arm.
Proof. round 1, re(q) = oo for all active arms S, and so all arms larger than 1/T are covered by our choice of S. Now, suppose that the lemma holds up to round t, and that playing pa causes price E R to become uncovered. Then, by the definition of covering, we must have
Pr Pt + Fe+ (p:) < S Pt + re.e),
where is the nearest active price to the right of pt. selected at Step 6. First, verify that the added price, p' (p= + 9)/2, is less than Since T(+1 (Pt) must be less than one, must have T4+1 (p) - 1 n,(p) 2 12. Thus, we can bound
(p+ m+1 (1 1) 1)
Σ
Σ
(y7 yrz! yra)
T TTET++1pp)
22
Σ
Σ
(Um Vra)²
(me(p) + (p)((p)
an TT( m=T
m((p) - Ve(p)
(p(p) +
2 V(()).
13
Consequently, one can show that
10V_1(() (p) logT
12 ne(p)
3 10V((p) T ne(p)
12 log)(T ne(p)
3
(141(p)) V (p( +
(pt).
Combining, we find that p' = (p. + 4)/2 < + (p(e < <:: + < as desired. Moreover, p' could not have already been active at round t; otherwise, Pt would not have been covering Finally, once pf is added, it covers p since (1+1(p') co.
Lemma D.5 (Gap bound). Condition on Echean- Then gap(p) S 5re(p) and (x(p) < 252 log
gap(p)"
504 log T for all [0, 1] and t E [T]. (ap())
27

---

Proof. Write ş max(br, 71, and fix any price E [0, 1]. Consider some round t at which is played. By Lemma D.4, we know that p was covered at the beginning of round by some price q E S. and that had a higher index than q. Hence,
index: (p) 2 index:
(since was played) (by definition of index) (concentration guarantee) (p covered by g)
(QB rr(g)
2 m(a) + +rx(g)
rev(f).
Moreover, index; (p) S pp(p) + (p) S rev(p) + (p). Thus,
gap(p) = rev(p.) - rev(p) - T + rev()) rev(p) S T + 3r.(p).
Now, if ne (p) < 12, gap(p) < 1 (p)) Otherwise, the bound above implies that gap(p) < 5r(+1 (p). Since Te (p) only changes when p is played and gap(p) I 5r((p) when f = 1, this guarantee
holds for all t. For the other bound, we apply concentration to obtain
10 10 (p) log T
126 126log(T))
gap(p) $
(2(p)
(p) -
Rearranging and solving the quadratic inequality in (z(p) gives the stated result.
Compared to the standard gap bound lemma for zooming (see, e.g.. Lemma 4.14 of 27), Lemma D.5 adapted to the variance of each price We can now prove the regret bound.
Lemma D.6 (Active arm separation). Conditioned on Ecleans consider any three consecutive active arms y which did not belong S at initialization. Then
to (gap(z)..)a(()))
Proof. If y was activated before 2, then z must have been added as the midpoint of active arms and y +22((z y) 22 y at round Ts. when y must have not covered 2z - y. Thus, by Lemma D.5, we would have 2(2 x) 2(z - y) = (2z 3) > gga((y). On the other hand, if was activated after 2, then must have been added as the midpoint of æ and 2 at round Ty. when must have not A(y).
covered Again, by Lemma D.5, this would imply
Proof of Lemma D.1 We freely condition Eclean since the complement has negligible probability O(T-2) 2). For each > O, let Y3s S X25 denote the set of activated prices p with gap(p) E [ö, 26). In what follows,
say that two prices are adjacent if they are neighboring within Ys. Note that most Olog 7)) of the prices in Y8 were activated at initialization. Consider the set Y which, for each such price, contains this price and up to two neighboring prices, such that the remaining prices Y8 \ Y can be split into triples of neighboring prices. We then decompose
Ys \ Y = [PL.1 < P12 < P1.3 < P2,1 < P2.2 P2,3 < <... Pn.1 < Po. < Pn,3),
where Pt,1- Ps,2, Pt,3 are neighboring for each i E [n]. By Lemma D.6, we have Pt.3 - Pi,1 > 8/10 for all [n]. and so pi,e- Pj. 5/10 for all k [3] whenever i
1. Thus, we can
partition Ys YP into most 6 packings, each of which has separation at least 8/10. Of course any (5110)-packing of Ys S X28 is contained within a (6/5)-cover of X25- Consequently, we have
E S 6N (N2s, 8/5) + Ollo T) S 6c5- + Olog
PEYs
Noting that (6/110)paccking within [0.1] can have cardinality at most 108-1, further bound |Ys| = O(log 7' + --1). Thus, by Lemma D.5, the regret incurred due to posting prices in Ys is at most
28 Σ (p))(p) log(T))- 2 +log(T)8-)) = [og[(T]0 Σ (p) + log(T))
pEYs
PEY,
= -100)(()) 11~ +lo==+oo(()66 log(T)5-1) + log(T))
8-1))
28

---

= - (T))-1)
Now we sum over 1/2, ....,,.......................... where will be tuned later, giving total regret bound of
log(1/a)
Σ
clog (log(T)2/(+t)) +og ( + aff = O( (0))==((c((()aatt0 log (T)a + aT).
1=1
Taking a (clog(T)/T)) we obtain the desired bound of -111111))1))111141)
E Proofs for Section 5
We first recall some results from Japnik-Chervonee (VC) theory. Given distributions D, D' over a finite domain X, define the total variation distance | - DD''lllrv = supagx -
Lemma E.1 (Section 28.1 of 25). Fix finite set X, a function family J S 10, distribution DE (X), and å (0, 1). Then, for X1...., X, sampled i.i.d. from D, we have
n T Σ f(x.) =
=o(v =(x))=
V Vllo(nn/V) V +oggn//)) log(1/6)
sup fEF
E (fnDD[(()]
"
with probability at least Lemma E.2 (Theorem 9.3 of 25), The family F {0, 1/x² has VC dimension |X and the family of linear thresholds over Rdd has VC dimension d + 1. The former result implies that, under the setting above, we have
where V is the VC dimension F.
| 1D-Dullrv = =0 o
log((/n//1)) (1/8)
n
with probability at least 1-
We also recall Bernstein's 's inequality for the case of i.idd Bernoulli random variables. Lemma E.3 (Theorem 2.10 of 3). For i.i.d. XI.... X,, Ber(p) and 8 O,
Σ X4 S pm + / (1/0))(()))))) log( 1/
1=1
with probability al least
We now turn to the main proofs.
E.1 Observed Type Identifiers (Proof of Theorem 5.1)
To state our result for the first setting, we introduce e-ball performance metric for contextual search. This is slight strengthening of the standard e-ball metric Σi 1
v,| e}.
Definition E.4 (Strong e-ball regret). Let A be a contextual pricing policy which, at round t E [T] with context u, outputs price Pt E [0, 1] along with confidence width w, [0, 1). For (0. 1). we say that A achieves strong e-ball regret R(T) for contextual search if, when K, = and D. òg.
we have Ip. we| < w. for each round and Σ 1 (w, > 8) < R(T), where
(ur. 0-)-
That is, A produces e-accurate estimates for the true values, outside of up R(T) rounds for exploration, and it can identify when these estimates are accurate. In practice, this tends to require that A maintain confidence set around 0, whose width, when projected onto the current context, is greater than & for at most R(T)) rounds. Fortunately, there are existing efficient algorithms which achieve low e-ball regret.
Lemma E.5 (18), For e E (0, 1), there exists a contextual search algorithm ProjectedVolume(e) based on the ellipsoid method, with strong e-ball regret Od and running time poly (d, 1/e) per round.
We now present our algorithm (Algorithm 5), which uses Pro ProjectedVolume as subroutine.
AAthhouhh [18] state slightly weaker guarantee, instead bounding ΣT= 1 p1-11 > =} = O(dlog(/s)) this strengthened result is immediate from their proof.
29

---

ALGORITHM 5: Contextual Pricing with Ex-Post Type Identification
initialize: observed types I = 2. (dlog(T)/T;
2 for each round t E [T] do observe context We; exists E I such that (,, ue) > E and mi(1) < ET' then play P: price( A., u,) and observe yı: observe type 2, E [.];
update algorithm A; with yr if 2t i;
increment mi) by
else
10
let S {i E I: width(Ai, wx) S <e);
11
define F(i) = Ejes mi())
1-1 ((price(A), ue) 2 price(A;;, 44} for each E S;
12
set '" arg m F(i) ,,, uz);
13
play p. (oniceeeee(A u4) E, 0} and observe yr:
14
observe type E [K*];
15
increment (*)) by 1;
2 & I then
17
initialize copy As, of ProjectedVolume(() and set I + IU
Overview of Algorithm We maintain set I of observed types, initially empty, and an accuracy e (tuned to minimize regret). We will initialize an independent copy A; of ProjectedVolume for each i added to I. Since these copies are simulated, we are free to query the price price u²) and confidence width (,, uz) for context u, without updating A; Moreover, for each i E I, the algorithm maintains frequency count ne (i), recording the number of rounds which we have followed the recommended price of A,, along with an exploration count my (i), recording the number of rounds which we have played the price of A, due to its lack of confidence along the current context. At each round f, we perform the following:
If there is an observed type E I such that width(AA; u²) > and that its number of exploration plays mi) is below a threshold of eT/K., K., the algorithm plays price(A,, uz). observes the outcome and the realized type 2t, and updates A, if 2 = i. In addition, we increment (1) and (i).
Otherwise, it defines active set S {i E I width(Ai; u.) S e). computes for each i S the score
Σ n (i) 1 price(A); u1) 2 price(A.,, ue) JES
F(1)
and plays Pt max un) 0} where i arg mag F(i) price(AA, u.) It then observes Ys and 2, and updates the frequency count n4+1 ( Here, F is an estimate for the demand at the price suggested by A,, and so i is an estimate for the revenue maximizing type. We pull back the price recommended by A,. by e to avoid issues due to estimation error.
Bounding exploration regret. Write for the set of exploration rounds. By design, an exploration round is one in which some type i is used with (idth(A; uz) > and exploration counter satisfying (i) < =T. Trivially, [Tl =T, can ineur regret at most eT = Ö(VdT) during exploration.
Bounding mass of types which saturate exploration threshold. Next, consider any type that has been explored sufficiently so that mt (i) sT after time T; denote by S' the set of all such types. We will show that D. plays small mass on S'. Fix E S' and write Ti, for the exploration rounds where we follow A, Conditioned on Tı,, we note that X, = 1 f i). E Tí are i...d. Bernoulli random variables with Pr(X, = 1) = (1). Defining
S = Σ X
TET1,
30

---

our guarantee for Projeccedoolume (Lemma E.5) and the width condition for exploration imply that S O(dlog(d/E) On the other hand, by Bernstein's inequality (Lemma E.3), we have
S 2 mr mr - mm log(7)
ITg( 3
with probability at least 1/T. Since (i) eT / d' log(T), the dominant term is mr( for T greater than a sufficiently large constant. Thus, we deduce that
eT D.) 0 dlog d)
or equivalently,
(1) S 00( dllg(d/e)
sT
Summing over all types in S' (of which there most K,) and taking union bound, the total mass in is at most
D.(S") = D.) K, dlog(a/e)
= ET
(8)
iES'
with probability at least 1 K-KK// We condition on this bound holding for the remainder of the proof, since doing contributes negligible K, to the regret. We also condition the event that, for each round é & [I'] the empirical frequencies of (all) types deviate from their true masses by at most (vv K, log(T)/() in total variation. This is permissible by Lemma E.2 and a union bound rounds.
Bounding exploitation regret. Fix an exploitation round f, and recall the of accurately estimated types
{i I: width(Ai, ux) S Ee).
Write U1....... UK. [0, 1] for the true values round f. By our construction and the s-ball guarantee for ProjectedVolume A, returns a price that an E-accurate estimate of 0s for each E S. Moreover, by analysis above, the mass types outside of S is quite small. We thus bound
K.
dem,(pt, we) = D.(1) (us 2 pr)
(1) 2 pr} - pok-KKKVdd/T dd/T
(Eq. (8))
iES
ni(
1(; 2 pd 0 (K, d/T) (o,
(TV bound)
Σ iES
1/ 2 price(Ar.,.)) =) -o...odlog((T)) /dlog(T)/1)
(choice of p.)
Σ (i)
1 (price(AA, un) price(Air, u.) (...V(((K(())) dlog(T))/
(i
t
iES
= F(i.)) ō (K, / /dlog(T)/t).
(choice of F)
Consequently, we bound rev, w+) + (Ö(K) (l.g))o((T))/ from below by
F(i") Z price(A:., u4) F((") -
max price( AG, w.) F()) - JES
(choice of i*)
(i( (price(Aii, uz) 2 2
max P P
(rev. maximized at jump)
SES
-Ö(K, (dlo((T))))/)
max p pE
2p (prii ur) 2
(TV bound)
31

---

(.(0)((0)p+8) -Ö(K, V....VVlloli /llgg()//))
max P pE|0,1]
e S)
K,
max
Σ ==1
(i) (2+p+ -Ö(K, -O(K.vdlog())/)
(Eq. (8))
pE
max pdem, (p e. Ö(K, K, /dlog(T)/)
pE[0,1]
max rev. E, u4) - -2 6 Kr dllog()/tt
pe[0.1]
max rev, u4) - 33 - (V..vllo((T)/ pE
All together, we see that playing ps incurs regret at most Ö K, /log////tt). Summing over exploitation rounds and adding the exploration regret gives a total bound of
R(T) Σ (K.vvloo(TT)/ + Ö(VaT) = Ō(K.
as desired.
E.2 Observed Type Vectors (Proof of Theorem 5.2)
first show that re concentrates tightly around rev., using a simple VC bound.
Lemma E.6. Fix D Ax(()) (8) and let Dj be the empirical measure of ii.. samples from D. We then have
rev u) - rev (p (p.u)) =0 (
(K, d) log(t) log(1/5)
sup 1E(0.1),uEM4
with probability at least
Proof. We compute
sup WE we(
revvp(p, u) rev u))
sup 1e(o.I].eel
demp u) dem D. (p,u)
sup Ea-D[f(0)] - Eg-5, [[()]] JEF
where F. is the space of linear threshold functions fp.. supp(D) - (0, 1) given by fp,((0) [[,u, 0) p}. The result then follows by Lemma E.2.
Now, our best response policy ensures that, at each round > 1, we have
rev. (pt, uz) = rev D,-, (Pe, ue) + rev. (pt. u)) revpe, カ.-, (Pe, uz)
sup rrev, (p, u) rev rev (p, u) rev D._, (br, (we); ut) pe(0,11,uEu
2 rev. (br, (u)), uz) - sup revv (p, u) - rev (p,
pε|0.1],uEu
Consequently, regret is at most
R(T) < $1+2
Σ
sup
rrev. u) rev (p,
0. .Jee
1=1
log(t)
min K., d
(Lemma E.6 with 6 t-)
Ö(v Almmminfee min(K,,d)) d}T).
desired,
32

---

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:
We summarize key contributions and results, which all have proofs.
Guidelines:
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 to other settings.
It is fine to include aspirational goals as motivation long is 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: [NA]
Justification: This is a theoretical work and we point out all necessary assumptions for the applicability of the results
Guidelines:
The answer NA means that the paper has no 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 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
33

---

Justification:
We provide the full set of assumptions and a complete proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch 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 affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper does not contain any experimental work.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 are 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 is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of 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) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either 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 to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers 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?
34

---

Answer: [NA]
Justification:
The paper does not contain any experimental work.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we 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 NeurIPS code and data submission guidelines (https: /CodeSubmic / //nips. wttpccccpppccccceeececccccccccct /tte:///ggiiieeeeeeeuuubiiiiii ssisnnonllll onPolicy))) for more details.
The authors should provide instructions on data access and preparation, including how 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. If 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 possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not contain any experimental work. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of 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, or 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: [NA]
Justification: The paper does not contain any experimental work.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call 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.
35

---

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 enrors 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 error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in 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 execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not contain any experimental work.
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, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well 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 make 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 https: http///eerrpppeeeeee cc ht/pppllcc/hhhhiccuddee.e..
Answer:
[Yes]
Justification:
We abide by the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS 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 a 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 is theoretical work without any clear and immediate social 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.
The conference expects that many papers will be foundational research and not tied to 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 improvement in the quality of generative models could be used to
36

---

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 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal 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 a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no 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 to 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 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
Are the creators 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?
Question:
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 (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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 package should be provided. For popular datasets, paperswi thcode. com 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 has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
37

---

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 the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing 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 release new assets
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information 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 to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
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 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 on 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 we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
38

---

The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non non-standard components.
Please refer to our LLM policy (https: httpss///neurrte tweurips.cc/ooofeeeeeeeeeee e for what should or should not be described.
39


Reviews:
[{"review_id": "3A0dxXWnDH", "reviewer": "Reviewer_4ydy", "summary": "This paper studies dynamic pricing policy optimization in the presence of $K^\\star$ heterogeneous buyers, each associated with an unknown parameter $\\theta_t$. The authors build upon the recently proposed Optimistic Posterior Sampling (OPS) approach to develop their algorithm. They establish a near-optimal regret bound of $O(K^\\star \\sqrt{dT})$, which is optimal in both the dimension $d$ and the time horizon $T$. Furthermore, they derive a sharper upper bound of $O(\\sqrt{K^\\star T})$ in the special case where covariates are not involved.", "questions": "1. The authors model the buyer's valuation as $v_t = \\mathbf{u}_t^\\top \\theta_t $, implying that the customer's value is fully determined by the observed covariates. It would be more realistic and flexible to include a noise term in this formulation—for example, $v_t = \\mathbf{u}_t^\\top \\theta_t + Z_t $, where $Z_t $ is an i.i.d. random noise term. This would better capture potential randomness in customer behavior not explained by covariates.\n\n2. As mentioned in the weakness section, the clarity of the paper could be significantly improved by refining the notation. For example, the function $\\mathrm{proj}(\\cdot)$ is defined but not clearly explained, and some notations like $\\mathrm{dem}_Q$ may be confusing to readers. Additionally, when citing results or introducing new concepts, it would be helpful to provide more detailed explanations or context. Without this, readers may find it difficult to follow the technical developments.\n\n3. It would be beneficial to include more real data experiments to demonstrate the effectiveness of this proposed method in reality and compare it with existing methods.", "limitations": "See the questions.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength: This paper explores a novel and important setting in dynamic pricing, where buyers are heterogeneous and not drawn from a single population. The authors propose a new algorithm along with theoretical guarantees that are near-optimal, making a valuable contribution to the literature.\n\nWeakness: The writing could be improved for clarity. In particular, the paper introduces many non-standard notations, which would benefit from clearer explanations. It would be helpful if each assumption or definition were followed by an intuitive explanation or example to aid reader understanding.", "was_revised": true, "final_justification": "I have read the authors' rebuttal and the other reviews. I would prefer to keep my current score, as my concerns have not been fully addressed. The paper would benefit from an empirical evaluation to support the proposed method.", "rebuttal": "Thank you for taking the time to review our submission and for the clarifying questions.\n\n**Q1, added noise:** In the presence of such added noise, our existing analysis mostly goes through, except for the bound on the disagreement coefficient. This noise smooths out demand functions, and we would then require a bound on the disagreement coefficient for the induced family of smoothed demand functions. When the noise has low variance, matching our existing disagreement coefficient bound is still possible (after introducing price discretization). In fact, our extension from a finite to infinite model class in Section 3.2 employs such an argument (see end of proof in Section B.6). The analysis there can tolerate bounded noise up to scale 1/T, without worsening our regret bound. A slight extension of this argument can extend to sub-Gaussian noise of the same scale. We will add a remark summarizing this explanation for the noisy setting to the end of Section 3.2.\n\nWe suspect that noise at substantially larger scales would worsen the achievable regret, but an exact characterization of this question is beyond the current scope. We remark that a noise threshold of 1/T appears in previous literature on contextual search with a single type, while noise at much larger levels leads to a jump in regret from logarithmic to polynomial. We expect that a similar jump arises in our setting but this is definitely an intriguing open direction and we will explicitly add it as an open question.\n\n**Q2, clarity:** We apologize for the confusion regarding notation. We will tweak the introduction of the projection operator as follows: \n\n\"Once we restrict to a fixed context $u \\in \\mathcal{U}$, each type $\\theta \\in \\Theta$ induces value $v = \\langle u,\\theta \\rangle$. Thus, each type distribution $D \\in \\Delta(\\Theta)$ induces a projected value distribution $Q = \\mathsf{proj}(D,u) \\in \\Delta([0,1])$, where $\\mathsf{proj}(D,u)$ denotes the probability law of $\\langle u,\\theta \\rangle$ when $\\theta \\sim D$.\"\n\nMoreover, we will add a table in Section 2, before “Basic pricing facts”, which contains all of the main notation terms with their definitions (proj, rev, dem, gap, etc.).\n\nWe will seek to include clarifying explanations where appropriate throughout the paper. In particular, for the disagreement coefficient, we will add the following:\n\n\"In our application, each function $f$ will represent the gap between the demand function predicted by some model $D$ and that of the true model $D\\_\\star$, for a fixed context. In our analysis, the distribution $\\nu$ will be supported on prices which our algorithm estimates to be near-optimal based on historical feedback. The disagreement coefficient is small if, by playing price $p$ sampled from $\\nu$, it is unlikely for any model $D$ to disagree substantially with $D\\_\\star$ at $p$ if this model agrees with $D\\_\\star$ on average.\"\n\nThis is inherently a bit tricky to conceptualize due to the nested quantifiers, but we emphasize that the disagreement coefficient is a standard quantity of interest in active learning and empirical process theory (see the existing Remark 3.7).\n\n**Q3, experiments:** Unfortunately, there are significant limitations to performing meaningful experiments (beyond fully synthetic ones which simply verify the theorem statements). Indeed, while there are large datasets containing purchase records of the form “item - buyer - price - purchase decision”, the buyers’ values are unavailable. Thus, in order to determine purchase decisions for prices not used in the dataset, we must simulate buyer behavior. One could fit a $K\\_\\star$-types model to the dataset, and then use this for simulations/evaluation, but such an experiment would not tell us whether or not the performance of POPS translates to practice (since we are using the $K\\_\\star$-types assumption to simulate). In summary, it is non-trivial to design a proper experiment for our setting due to the necessary reliance on synthetic purchase feedback, and we view this as beyond the scope of this work."}, {"review_id": "s6IZRj6Dw7", "reviewer": "Reviewer_rYR5", "summary": "This paper considers the contextual pricing setting with a twist: the incoming agents/buyers have heterogeneous types that are sampled from an unknown distribution with support $K^* $. Prior works considered the buyers to have fixed but unknown type. Clearly, the optimal context-dependent pricing strategy depends on knowing the unknown type distribution (this is the offline optimal against which regret is defined). The work proposes algorithms for this setting based optimal posterior sampling. When the distribution is known to be from a given set, and $K^* $ is known, a $\\tilde{O}(K^*\\sqrt{dT})$ bound is given (Theorem 3.2) that is tight upto the $K$ factor (lower bound is for $\\sqrt{K}$). This guarantees are maintained when assumptions about knowing $K$ and distribution set are relaxed to an extent. The work also focuses on tightening the bound for $K$ for non-contextual settings (via zooming) and the setting where agent types are observed after each round (called ex-post observability)", "questions": "See above.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Overall I am in the middle with this paper\n\n### Strengths\nThe overall model of the paper is fairly attractive and natural. Agents having heterogenous types from an unknown distribution is very natural and standard in many dynamic pricing settings. The paper also answers the natural questions of learning under both type feedback (ex-post observability) and just realized actions. The technical work in the paper is fairly competent. \n\n### Weaknesses\nMy main criticism of the work is it seems to not mention or hand-wave some important claims. There's also parts of the work that seem a bit unfocused. I expand below.\n\nIn section 3.2, you assume that $\\mathcal{D}$ is not known but the algorithm uses a a finite large cover of the whole distribution space $\\Delta(|\\Theta|)$. This clearly is an epsilon cover, the size of which scales exponentially in d. So it is not clear to me whether the algorithm 2 is computationally efficient/feasible since we need to sample and update from this very large cover. Further, this also relies on the support size being discrete - this isn't a big issue, but it inconsistent with line 150 where you claim that $K^* $ may be infinite. I don't see any results in the paper that support this. \n\nI also find the results on the non-contextual setting that leverages the zooming algorithm also a bit unfocused. The work is ostensibly about the contextual pricing setting, so it's uncertain what considering the non-contextual setting as a major section in the work achieves. This is akin to pricing a single item to a heterogenous set of buyers that arrive online - there have been relevant works here.", "was_revised": true, "final_justification": "I think the work has a fair technical contribution, but the exposition of the results and formalness of the arguments could be improved. The rebuttal maintained this perspective.", "rebuttal": "Thank you for taking the time to review our submission and for the clarifying questions.\n\n**Weakness, exponential cover:** Yes, the cover is exponential in $d$, and Algorithm 2 is statistically efficient but computationally inefficient (as stated in the intro to Section 3). In this case, even designing a statistically efficient algorithm required significant care. These computational issues were the motivation for Section 5, where we incorporate additional information in order to design computationally efficient algorithms. \n\n**Weakness, infinite types case:** You are correct to point out that the submission did not treat infinite $K\\_\\star$ in the contextual setting — we explored this regime but ended up removing the relevant remark due to space. We will add the following back to the end of Section 3.3 in the revised manuscript:\n\n\"Large/infinite $K\\_\\star$: Our lower bound above can be restated as $\\Omega(\\min\\\\{\\sqrt{K\\_\\star d T}, d^{1/3}T^{2/3}\\\\})$. When $K\\_\\star = \\Omega((T/d)^{1/3})$ and the second term is active, POPS no longer has an advantage over EXP4 with naively discretized actions. In particular, one can run EXP4 with a policy cover of log cardinality $\\widetilde{O}(d \\varepsilon^{-2})$ and price set $\\{\\varepsilon,2\\varepsilon, \\dots, 1\\}$, incurring regret overhead $\\varepsilon T$ due to discretization. This gives a regret bound of $\\widetilde{O}(\\sqrt{Td^2\\varepsilon^{-3}} + \\varepsilon T)$, which balances out to $d^{2/5}T^{4/5}$ after tuning. Characterizing the optimal regret in this large $K_\\star$ regime is an interesting question beyond the current scope.\"\n\nIn the non-contextual case, Theorem 4.1 features a worst-case $T^{2/3}$ bound which holds for all $K\\_\\star$ (even infinite).\n\n**Weakness, non-contextual contribution:** The non-contextual setting in the paper is significant in trying to understand what the optimal dependence on $K\\_\\star$, the number of types, is. For the contextual setting, we obtain regret $K\\_\\star \\sqrt{dT}$ but are unable to achieve $\\sqrt{K\\_\\star dT}$. However, our $d=1$ result shows that $\\sqrt{K\\_\\star}$ dependence is possible in some cases. Moreover, our $\\sqrt{K\\_\\star T}$ bound closes a gap in the existing literature on dynamic pricing with finitely many types, fully resolving the optimal regret up to logarithmic factors. As discussed in Remark 4.4, the recent work of Cesa-Bianchi, Cesari, & Perchet includes an additional instance-dependent term that can explode to infinity. Finally, we believe that our algorithmic methodology and analysis, which replaces the standard zooming dimension with a smaller variance-aware dimension, may be of independent interest."}, {"review_id": "VR9IDcixPT", "reviewer": "Reviewer_XQTx", "summary": "The paper studies the well-established problem of contextual dynamic pricing, assuming the existence of several buyers. Formally, the valuation $v_t$ at every round is a linear function of a context, known by the agent, and a vector of coefficients $\\theta_t$, drawn in an i.i.d. fashion with respect to the distribution $D$ with finite support, in which each element represents a different buyer. By employing a Thompson Sampling-inspired algorithm, the paper manages to bound the expected regret by $K_{\\star}\\sqrt{dT}$ where $K_{\\star}$ is the number of buyers, $d$ the dimension of the context space and $T$ the number of rounds. Concurrently, they prove a lower bound for the same model of the order of $\\sqrt{K_{\\star}dT}$. The question of which is the right dependency with respect to $K_{\\star}$ is answered in the paper for the non-contextual case, for which a bound of the order of $\\mathcal{O}(\\min\\{\\sqrt{K_{\\star}T}, T^{2/3}\\})$ is obtained. Lastly, they provide some additional results for the case in which the learner can rely on some additional information, specifically, after every round, it has access to either the type of the buyer or the whole parameter vector $\\theta_t$.", "questions": "1.  On the line of what I stated in the Strengths and Weaknesses section, I wonder if the assumption on the boundedness of support of the buyers could be relaxed, for instance, assuming that only a finite amount of them are chosen with probability bigger than a threshold or assuming concentrated zones of buyers for which the corresponding parameters $\\theta$ are similar. \n\n\n2. The paper leaves the question of which is the correct dependency on $K_{\\star}$ in the general case open. Do you think it is possible to generalize the analysis of Section 4 to the contextual case, or do you have any insights about what the right rate could be?", "limitations": "The limitations have been addressed.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper investigates the well-known problem of dynamic pricing, focusing on the less-studied setting of multiple buyers, therefore the results are novel and of interest to the community. Furthermore, the paper is written in a clear and precise way where all the assumptions needed are clearly stated and the results, together with the steps to achieve them, are well-motivated and easy to follow.   \n\nThe weaknesses of this work are the theoretical assumptions posed, which represent a limitation to the applicability of the results stated. Specifically, the setting analysed by this paper only considers the case in which the number of buyers is finite, by assuming that the distribution with which the vectors $\\theta_t$ are drawn has bounded support.\n\nI also want to point out that in [1], they also study the problem of contextual dynamic pricing with multiple buyers. While the model they consider is different and therefore the results they obtain are not comparable, I think it should be mentioned nonetheless.\n\n---\n[1]  Contextual Pricing for Lipschitz Buyers, J. Mao et al., NeurIPS 2018", "was_revised": true, "final_justification": "I think this is a valid paper, hence I keep my positive score unchanged.", "rebuttal": "Thank you for taking the time to review our submission and for the clarifying questions.\n\nThank you for pointing out [1], we will update our literature review to include their work.\n\nRegarding Q1, this is an interesting question. We first note that our bound on the disagreement coefficient extends even to unbounded type distributions (it is a consequence of monotonicity and a bounded number of jumps for the demand functions). That being said, our bound on the covering number requires that the support of the types is bounded. However, if instead of being supported in the unit cube, the types were supported in $[0,R]^d$, we would still get a covering number bound of $\\widetilde{O}(d K\\_\\star \\log(R/\\varepsilon))$, leading to regret $\\widetilde{O}(K\\_\\star \\sqrt{d T \\log R})$ with only logarithmic dependence on $R$. If one imposes additional structure on the type distribution, this would be reflected in a smaller covering number and lower regret. We will add a short remark to this effect at the end of Section 3.2.\n\nRegarding Q2, our attempts to generalize the analysis of Section 4 to higher dimensions encountered a number of significant challenges. It is difficult to maintain uncertainty sets in high dimensions without incurring an exponential dependence in the dimension. While this is achievable for $d=1$, a key difficulty for $d > 1$ with multiple types is that you do not know which type the feedback you obtain at time $t$ corresponds to. This is why, in Section 5, we consider a model where types are identified, allowing for simpler, more efficient algorithms. Currently, we lack substantial evidence to make a conjecture on the optimal regret."}, {"review_id": "6j3U2fdfnW", "reviewer": "Reviewer_9ki1", "summary": "This paper studies the contextual dynamic pricing problem. \nIn this problem, in each round, an unknown type $\\theta_t$ is drawn from an unknown distribution, and a context $u_t$ is adversarially chosen. \nThe value is then $v_t = \\theta_t \\cdot u_t$, and the agent should pick a price $p_t$. \nThe problem is to maximize the total revenue. \nThe paper proposes an algorithm with a regret of $\\tilde{O}(\\sqrt{K_* T})$ when $K_*$ is known, and another algorithm with regret $\\tilde{O}(K_*\\sqrt{T})$ when $K_*$ is unknown. \nHere $K_*$ is the support size of the type distribution. \nThe paper also considers the non-contextual case and the model with ex-post type observations and presents corresponding algorithms.", "questions": "In section 3.2, what do you mean by \"take $\\mathcal D$ to be a large, finite cover of the full distribution space\"? \nWhat is $\\mathcal D$ formally?", "limitations": "Yes.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Overall, the results given in this paper are interesting. \nNevertheless, I think the paper has a lot to improve in its presentation. \nIn general, the paper is written in a too technical and notation-heavy manner with many technical definitions, while the intuitions of the given algorithms/analysis are lacking. \nThis makes the paper hard to follow, and also makes it hard to evaluate the contributions of this work. \nFor example, for Section 3, I highly recommend that the authors put technical details into the appendix and present more intuition on the presented analysis (e.g., the disagreement coefficient), and address how the underlying techniques are related to previous works. \nIn Sections 4 and 5, since the two algorithms discussed are not even given in the main body, the pure analysis seems too dry and hard to follow.", "was_revised": true, "final_justification": "I will keep my score.", "rebuttal": "Thank you for taking the time to review our submission and for the clarifying questions.\n\n**Weakness, overly technical:** As suggested by the reviewer, we will update the writing of the paper to present more intuition for the algorithms/concepts and move more of the technical analysis to the appendix. In particular, for the disagreement coefficient, we will add the following:\n\n\"In our application, each function $f$ will represent the gap between the demand function predicted by some model $D$ and that of the true model $D\\_\\star$, for a fixed context. In our analysis, the distribution $\\nu$ will be supported on prices which our algorithm estimates to be near-optimal based on historical feedback. The disagreement coefficient is small if, by playing price $p$ sampled from $\\nu$, it is unlikely for any model $D$ to disagree substantially with $D\\_\\star$ at $p$ if this model agrees with $D\\_\\star$ on average.\"\n\nThis is inherently a bit tricky to conceptualize due to the nested quantifiers, but we emphasize that the disagreement coefficient is a standard quantity of interest in active learning and empirical process theory (see the existing Remark 3.7).\n\nIn Section 4, we will remove the technical lemmas (4.2 and 4.3) and extend the discussion after the theorem to better describe the variance-aware zooming dimension and why it can be significantly smaller. The key here is that, when expected revenue at a price is small, so is the variance of the revenue at this price.\n\nIn Section 5, we will update the discussion after Theorem 5.2 to be less technical, instead focusing on the high-level fact that best responding to historical data leads to dependence on the VC dimension of the relevant function class.\n\n**Q1, cover details:** $\\mathcal{D}$ is taken to be a large set of distributions such that every distribution $D$ over the type space $\\Theta$ is close to some $D’ \\in \\mathcal{D}$ under the Levy distance. See Appendix C.9 for the precise construction, where we specify “close” and also construct the needed nonuniform prior over $\\mathcal{D}$. Since the exact details require some careful parameter tuning and several concerns were raised about Section 3 being too technical, we prefer to leave the full construction in the appendix. However, we will add a pointer after introducing $\\mathcal{D}$ to this appendix section to direct the reader to a more detailed discussion."}, {"review_id": "6eIVf3XaAm", "reviewer": "Reviewer_SUXR", "summary": "In this paper the authors propose algorithms for posting prices when buyers have unknown, diverse preferences and the seller sees some buyer-specific context. It learns these preferences over time to make better pricing decisions. The methods work both when the number of buyer types is known or unknown and adapt to different feedback levels, achieving near-optimal performance in all cases.", "questions": "Can these techniques be extended to different (and more general) settings? Can the author provide a short discussion on this point?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "To me, this paper makes an interesting contribution to the community working in this field, and I cannot identify any real weaknesses. The algorithms are simple, and the analysis is non-trivial. Furthermore, I believe that modifying the zooming algorithm to achieve tighter results in the presence of one-sided Lipschitzness is an interesting idea. As a minor suggestion, the authors could include a table summarizing all the notation, as it is quite annoying to search for symbols across different pages.", "was_revised": true, "final_justification": "I gave the paper a positive score because I think it's a good article that offers an interesting contribution. Some improvements to the presentation of the paper should be implemented in the camera-ready version.", "rebuttal": "Thank you for taking the time to review our submission and for the clarifying questions.\n\nThank you for the suggestion. We will include a table before “Basic pricing facts” in Section 2 summarizing all of the main notation (rev, dem, proj, br, etc.). \n\nYes, the techniques extend to a broader class of pricing problems. As noted in Appendix C.1, we present a more general formulation involving a class of contextual demand functions that are not necessarily Lipschitz. Provided that the disagreement coefficient of this class is bounded, our algorithm yields a regret guarantee that scales with the disagreement coefficient."}]

Author rebuttal:

Meta-review: The paper studies a contextual dynamic pricing problem in which buyers can be categorized into $K_*$ types, each characterized by an unknown feature vector. Buyers arrive according to an unknown i.i.d. distribution (with features $\theta_t$), alongside contextual information $u_t$, and the buyer's valuation is equal to $v_t=\theta_t^Tu_t$. The seller posts a price only based on $u_t$, and the buyer purchases the item only if its valuation is higher than the price. The seller aims to maximize its cumulative revenue. The authors propose a pricing algorithm based on Optimistic Posterior Sampling, which exhibits a regret bound of $O(K_*\sqrt{dT})$ after $T$ rounds (and for $ d$-dimensional contexts). The bound is shown to be tight in $d$ and $T$. They additionally prove a tighter bound of $O(\sqrt{K_*T})$ for the non-contextual case. Finally, they provide additional results when the seller receives additional information on the buyer at the end of each round.

The reviewers found the model to be novel and well-motivated. They also mostly considered the technical contributions to be valuable and the results interesting and relevant to the community. The only major concern raised by the reviewers was due to the clarity of the exposition and the notations used. The authors have committed to improving this aspect and are expected to implement the modifications they promised in their response.
Decision: Accept (poster)