- Rating
- 3
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies contextual dynamic pricing with noiseless linear valuations and a time-varying parameter sequence subject to a known total variation budget. As a warm-up, the authors consider the simpler identical-context setting, combining binary search, lower-envelope pricing, and periodic and inconsistency-triggered restarts to establish the framework for the general contextual algorithm. For heterogeneous contexts, their multiscale shallow-pricing algorithm maintains nested feasible sets and enclosing ellipsoids at several relaxation scales. Requiring all active scales to pass a directional width check before exploitation allows a reliable coarse scale to control regret from accepted prices, while rejection-triggered restarts control the cost of overpricing. The resulting regret upper bound matches the deterministic lower bound up to logarithmic factors for fixed dimension.
Critical strengths
- An insightful multiscale algorithmic mechanism.
The coordination of width checks across scales, nested feasible sets, and rejection-triggered restarts provides an insightful way to control regret even when the finest feasible set excludes the current parameter.
- A coherent analysis with strong regret guarantees.
The algorithm and analysis fit together closely, with distinct components controlling exploration, accepted exploitation, and rejected exploitation. The matching dependence on and , up to logarithmic factors for fixed dimension among deterministic algorithms, is a meaningful theoretical achievement.
Critical weaknesses
- Limited scope of the noiseless valuation model.
The noiseless assumption limits applicability and plays a central role in the geometric and restart arguments. The intended applications and the extent to which the main insights remain useful under noisy valuations could be clarified.
Questions for authors
Q1. The noiseless valuation assumption.
(a) The noiseless valuation model seems somewhat counterintuitive to me: realized revenue drops to zero as soon as the posted price exceeds the buyer's value, even by an arbitrarily small amount. Could the authors clarify the motivation and intended scope of this modeling choice?
(b) How much of the proposed multiscale algorithm and regret analysis could extend to noisy valuations, even when the noise distribution is known? Which components would remain applicable, and which would require modification to handle stochastic feedback and its interaction with non-stationarity?
Q2. The necessity of the multiscale construction.
The current results leave open whether the single-scale baseline's inferior rate reflects an intrinsic limitation of using one scale or its particular tuning. Specifically, Example 4.1 uses prescribed prices that need not match those chosen by the single-scale algorithm, while Proposition D.4's lower bound for this algorithm is driven by repeated restarts under the selected tuning. Could the authors provide further evidence supporting the necessity of multiple scales, for example through simulation comparisons with single-scale baselines whose restart schedules and relaxation parameters are reasonably tuned, to better isolate the benefits of the multiscale construction?
Q3. Sensitivity to the variation-budget specification.
The multiscale algorithm still relies on a known global variation budget to choose its base scale and periodic restart schedule. Could the authors characterize how its regret is affected when the supplied budget substantially overestimates or underestimates the realized variation, for example through numerical experiments?
Moreover, when the variation budget is unknown, what are the main obstacles to choosing the base margin and batch length adaptively from the observed feedback?
4 comments
Response to Reviewer 7v9U (Cont.)
Q2: necessity of the multiscale construction.
We agree that Example 4.1 and Proposition D.4 alone do not settle this. The revision adds the following evidence.
-
Clarified Example 4.1 (footnote 6). The example's prices are prescribed to illustrate the geometry of relaxed constraints. We do not suggest they are generated by the single-scale algorithm.
-
Necessary tuning scales (Proposition D.5). For and , the single-scale algorithm's worst-case regret is at least for any fixed margin and window . A uniform guarantee therefore requires and . This reduces the question to tunings at square-root scales.
-
Stress test of 34 tunings at these scales (Appendix I.2). They are 25 constant-factor pairs, 8 pairs with logarithmic adjustments, and the pair matching Algorithm 2's constants. For each tuning we search for a hard instance and run the algorithm's actual prices. For the canonical tuning, grows from 1.92 at to 116.96 at and 59,756 at , against 5.93 on a stationary control at . The best of all 34 tunings still has of about 542 at .
-
Shared-sequence comparison (Appendix I.3). On the same frozen instance at , is 29.71 for Algorithm 2 and 116.96 for the single-scale method. The blocks with changing contexts contribute about 112.95 to the single-scale method's value and less than 0.007 to Algorithm 2's. The gap comes from exactly the mechanism illustrated in Example 4.1.
We note the limits of this evidence. It covers a finite family of tunings with one dimension and budget, and the separation appears only at large horizons: through , the single-scale method has lower regret on these instances. It does not prove that every single-scale tuning fails, and a formal separation remains open.
Q3: sensitivity to the variation budget.
Thank you for this comment.
Misspecified budget (Theorem G.1). With an estimate in place of , Algorithm 2's regret is , where is the realized variation. The two terms reflect the two failure modes. Overestimation shortens the restart window and enlarges the margin, adding exploration and underpricing; underestimation lets more drift accumulate within a batch. An estimate within a factor of , in either direction, inflates the variation term by at most . With no estimate, the default gives .
Obstacles to adaptive tuning (Theorems G.2 and G.3). We see three.
-
The realized variation is not identifiable from purchase decisions. Two feature paths can induce identical decisions at every price while having variations 0 and .
-
Upward drift is silent. Accepted prices carry no signal of an increase, and detecting one requires probing above the current price, which is costly when nothing has changed. Theorem G.2 makes this precise: even with identical contexts, any deterministic policy with polylogarithmic regret on a constant value incurs regret on some sequence with a single upward jump. Hence no budget-free deterministic policy attains the known-budget rate at both zero variation and variation .
-
By contrast, downward drift reveals itself through rejections. When values are nonincreasing, a budget-free policy achieves , matching the known-budget rate (Theorem G.3).
The main obstacle is therefore detecting increases without paying for probes. Meta-algorithms for unknown budgets, such as the bandit-over-bandit approach of Cheung et al. (2019), are a natural starting point for heterogeneous contexts. By Theorem G.2, any deterministic approach must pay some price relative to the known-budget rate. Characterizing the optimal budget-free rate is an interesting open question.
Thank you again for your review. If your main concerns are now resolved, we would appreciate if you could consider revising your score. Please let us know if any significant concerns remain.
Thank you for the detailed response and additional analyses. I am satisfied with the clarifications. My original rating of 3 still reflects my overall assessment, so I will keep it unchanged.
Response to Reviewer 7v9U
We sincerely thank you for the careful reading and the precise questions, which led to most of the new material in the revision. We respond to each point below.
Weakness and Q1(a): motivation and scope of the noiseless model.
The discontinuity the reviewer describes is a feature of posted prices rather than of the noiseless model. A buyer whose value is below the posted price buys nothing, with or without noise; noise only smooths the \emph{expected} revenue, by averaging over buyers. The noiseless linear model is the standard model in contextual search and pricing (Kleinberg & Leighton, 2003; Cohen et al., 2020; Lobel et al., 2018; Paes Leme & Schneider, 2018; Liu et al., 2021), and our contribution is to extend it to drifting features.
Two applications motivate this model. The first is reserve pricing in online display advertising. When an impression attracts a single bidder, the reserve price acts as a posted price with binary feedback (Amin et al., 2014). Impressions are described by feature vectors, and the bidder's value is modeled as a linear function of them (Amin et al., 2014; Cohen et al., 2020). Bids also drift over time as bidders pace spending against budget targets (Paes Leme et al., 2021). This is the noiseless model with a drifting feature vector, and the revenue cliff the reviewer describes is the actual mechanism: a reserve price just above the bid yields no sale. The second is pricing differentiated products whose market value is linear in their features, as in online marketplaces, flash sales and loan pricing (Cohen et al., 2020). In our setting, the value of each feature may shift over time.
The noiseless model is also the regime in which the first-best benchmark is attainable. With noise, no policy can attain regret sublinear in T against the full surplus (Theorem H.4). The noiseless model therefore isolates the difficulty of learning under drift from statistical uncertainty. Its intended scope is settings where willingness to pay is well predicted by observed features. When this holds only approximately, our guarantees degrade gracefully: for i.i.d. shocks with standard deviation σ≤T−3/4, the noise term is at most of order D2T, where D=d+1 (Theorem H.1).
Q1(b): extension to noisy valuations.
Section 5 and Appendix H now answer this for the full-surplus benchmark. We note that the standard contextual pricing with noise valuation literature considers the weaker expected revenue benchmark (instead of the full-surplus benchmark).
Reduction (Proposition H.2). The noisy problem reduces to noiseless pricing in dimension D=d+1, using only purchase decisions. Each shock becomes movement in an extra feature coordinate, and physical regret is at most four times the regret of the lifted problem.
Upper bounds (Theorem H.1). Charging shocks to the total variation gives O(D2+D3/2(TV+Tσ)). A noise-aware tuning (Proposition H.3) uses independence instead. Shocks of magnitude at most h=σ2/3 are absorbed by the margin. Only larger shocks can trigger restarts, and each round has one with probability at most h. This gives O(D2+D3/2TV+D2Tσ2/3).
Matching lower bound (Theorem H.4). Every policy incurs Ω(Tσ2/3) expected full-surplus regret, even with identical contexts, no drift, and a known shock distribution.
To the question of which components carry over: the relaxed margins, which now absorb small shocks as well as drift; the multiscale localization certificate, whose surviving scale covers the batch diameter plus the noise level; and the exploration bound, which holds for every feedback sequence. What changes is that a rejection no longer certifies drift, since a large shock can also cause it. Restarts are therefore charged to large shocks as well as to variation, and independence controls how many occur.