acceptodds
Under review as a conference paper at ICLR 2027

Optimal Contextual Pricing in Non-stationary Environments

Abstract

We study contextual dynamic pricing in a non-stationary environment. In each round, a seller observes a buyer's context, posts a price, and receives only binary purchase feedback. The buyer's value is linear in the context and an unobserved feature vector that may change over time, subject to a known total variation budget . We measure dynamic regret against the first-best benchmark that extracts each buyer's full value. For identical contexts, we develop a deterministic algorithm that combines binary-search exploration, lower-envelope pricing, and two complementary restart mechanisms. It achieves regret . With heterogeneous contexts, a new geometric difficulty arises: small feature changes can leave a relaxed feasible set narrow but far from the current feature vector. To address this difficulty, we introduce a multiscale shallow-pricing algorithm that maintains relaxed feasible sets and ellipsoidal approximations at several variation scales. Larger scales provide reliable localization certificates, while the smallest active scale determines the exploitation price. The algorithm achieves dynamic regret . Both guarantees match the identical-context lower bound up to logarithmic factors.

Primary area:
learning theory
Keywords:
Dynamic Pricing, Online Learning, Regret Minimization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_7v9UOpenReview ↗
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
  1. 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.

  1. 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 TT and VV, up to logarithmic factors for fixed dimension among deterministic algorithms, is a meaningful theoretical achievement.

Critical weaknesses
  1. 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 VV 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
AuthorsOpenReview ↗

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 TT 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\sigma\le T^{-3/4}, the noise term is at most of order D2TD^2\sqrt{T}, where D=d+1D=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+1D=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σ))\widetilde{O}\bigl(D^2+D^{3/2}(\sqrt{TV}+T\sqrt{\sigma})\bigr). A noise-aware tuning (Proposition H.3) uses independence instead. Shocks of magnitude at most h=σ2/3h=\sigma^{2/3} are absorbed by the margin. Only larger shocks can trigger restarts, and each round has one with probability at most hh. This gives O~(D2+D3/2TV+D2Tσ2/3)\widetilde{O}\bigl(D^2+D^{3/2}\sqrt{TV}+D^2T\sigma^{2/3}\bigr).

  • Matching lower bound (Theorem H.4). Every policy incurs Ω(Tσ2/3)\Omega(T\sigma^{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.

AuthorsOpenReview ↗

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 d=3d=3 and V=1V=1, the single-scale algorithm's worst-case regret is at least c⋅min⁡{T,max⁡{Tδ,T/a,1/δ,a}}c\cdot\min\{T,\max\{T\delta,T/a,1/\delta,a\}\} for any fixed margin δ\delta and window aa. A uniform O~(T)\widetilde{O}(\sqrt{T}) guarantee therefore requires δ=Θ~(T−1/2)\delta=\widetilde{\Theta}(T^{-1/2}) and a=Θ~(T)a=\widetilde{\Theta}(\sqrt{T}). 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, RT/TR_T/\sqrt{T} grows from 1.92 at T=106T=10^6 to 116.96 at T=1020T=10^{20} and 59,756 at T=1032T=10^{32}, against 5.93 on a stationary control at T=1032T=10^{32}. The best of all 34 tunings still has RT/TR_T/\sqrt{T} of about 542 at T=1032T=10^{32}.

  • Shared-sequence comparison (Appendix I.3). On the same frozen instance at T=1020T=10^{20}, RT/TR_T/\sqrt{T} 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 T=1012T=10^{12}, 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 V^\widehat{V} in place of VV, Algorithm 2's regret is O~(d2+d3/2(TV^+V(θ)T/V^))\widetilde{O}\bigl(d^2+d^{3/2}(\sqrt{T\widehat{V}}+V(\theta)\sqrt{T/\widehat{V}})\bigr), where V(θ)V(\theta) 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 κ\kappa of V(θ)V(\theta), in either direction, inflates the variation term by at most κ+1/κ\sqrt{\kappa}+1/\sqrt{\kappa}. With no estimate, the default V^=1\widehat{V}=1 gives O~(d2+d3/2T(1+V(θ)))\widetilde{O}\bigl(d^2+d^{3/2}\sqrt{T}(1+V(\theta))\bigr).

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 (T−1)/2(T-1)/2.

  • 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 T/polylog⁡(T)T/\operatorname{polylog}(T) 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 1/41/4.

  • By contrast, downward drift reveals itself through rejections. When values are nonincreasing, a budget-free policy achieves O(log⁡T+T(v1−vT))O\bigl(\log T+\sqrt{T(v_1-v_T)}\bigr), 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.

Reviewer_HqjoOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies contextual dynamic pricing in a non-stationary environment, where buyers' valuations are linear in observable contexts and unobserved feature vectors that evolve over time under a known total variation budget VV. The authors consider dynamic regret against a first-best oracle that knows each buyer's valuation. For identical contexts, they propose an algorithm combining binary search, lower-envelope pricing, and periodic and inconsistency-triggered restarts, achieving O~(TV+1)\widetilde O(\sqrt{TV}+1) regret. For heterogeneous contexts, they develop a multiscale shallow-pricing algorithm that maintains relaxed feasible sets and ellipsoidal approximations at multiple variation scales, achieving O~(d2+d3/2TV)\widetilde O(d^2+d^{3/2}\sqrt{TV}) regret. The bounds are optimal in their dependence on TT and VV, up to logarithmic factors.

Critical strengths

The paper addresses a meaningful extension of the well-established noiseless contextual pricing problem to non-stationary environments. A key technical contribution is identifying the geometric difficulty that arises when applying single-scale shallow pricing to changing hidden features: small parameter variations can produce feasible sets that are narrow but poorly localized. The proposed multiscale construction provides an interesting solution to this issue. The regret guarantees are theoretically strong, matching the lower bound in their dependence on the horizon and variation budget up to logarithmic factors for fixed dimension. The paper also provides a useful progression from the identical-context setting to the general contextual case, helping motivate the main algorithmic ideas.

Critical weaknesses

I have two main concerns:

  1. The authors define the variational measure for capturing non-stationarity to be the quantity defined by the cumulative euclidean distances of the changes in the consecutive hidden features. Further they assume that an upper-bound on this variation to be known. I find this to be overly restrictive given the fact that the hidden features themselves are not observable making it difficult to even verify such a bound. This limits the practical applicability of the methods in this paper. This is the main blocker influencing my judgement.

  2. The authors do not mention about the computational complexity of their methods. Especially in Algorithm 2, Line 14 (computing the price ptp_t), the learner has to solve an optimization problem whose feasible region is defined by a constraint set that grows over time. How efficiently can such prices be computed?

As a minor concern, even though I understand that this paper is primarily of theoretical nature, experiments on real-data can be useful.

Questions for authors

Please see the section on Critical Weaknesses.

5 comments
AuthorsOpenReview ↗

Response to Reviewer Hqjo

We sincerely thank you for the detailed review and for stating clearly which concern weighs most. We address the known variation budget first, then computational cost, then experiments.

Weakness 1: the known variation budget.

We agree that the realized variation cannot be verified from data. In fact, it cannot even be estimated: in the revision (Appendix G.1), two feature paths induce identical purchase decisions at every price, yet one has zero variation and the other has variation (T−1)/2(T-1)/2. Rather than assume the budget is verifiable, we have added results showing how little the algorithm needs to know, and what is achievable with no budget at all (Section 5 and Appendix G).

  • rough estimate suffices (Theorem G.1). Run Algorithm 2 with any estimate V^\widehat{V} in place of VV. Its regret is O~(d2+d3/2(TV^+V(θ)T/V^))\widetilde{O}\bigl(d^2+d^{3/2}(\sqrt{T\widehat{V}}+V(\theta)\sqrt{T/\widehat{V}})\bigr), where V(θ)V(\theta) is the realized variation. The estimate need not bound V(θ)V(\theta). If V^\widehat{V} is within a factor κ\kappa of V(θ)V(\theta), in either direction, the variation term grows by at most a factor κ+1/κ\sqrt{\kappa}+1/\sqrt{\kappa}, so the rate is preserved up to constants.

  • A budget-free default. With no information at all, setting V^=1\widehat{V}=1 gives O~(d2+d3/2T(1+V(θ)))\widetilde{O}\bigl(d^2+d^{3/2}\sqrt{T}(1+V(\theta))\bigr). This retains the T\sqrt{T} rate whenever the realized variation is bounded, and degrades linearly beyond.

  • Some price for not knowing the budget is unavoidable (Theorem G.2). Even with identical contexts, any deterministic policy with polylogarithmic regret on a constant value incurs regret T/polylog⁡(T)T/\operatorname{polylog}(T) on some sequence with a single upward jump of 1/41/4. Consequently, every budget-free deterministic policy incurs Ω(T)\Omega(\sqrt{T}) regret on the stationary sequence or on such a jump sequence, while a known budget permits O(log⁡T)O(\log T) regret on the stationary sequence. The default tuning above attains O~(T)\widetilde{O}(\sqrt{T}) on both, which is the best uniform guarantee on this family up to logarithmic factors. The obstacle is that an increase in value is invisible from accepted prices unless the seller probes above its current price, and each probe is costly when nothing has changed.

  • Adaptation is possible when that obstacle is absent (Theorem G.3). When values are nonincreasing, each rejection reveals a decrease. A budget-free deterministic policy then achieves O(log⁡T+T(v1−vT))O\bigl(\log T+\sqrt{T(v_1-v_T)}\bigr), matching the known-budget rate.

The known-budget formulation follows the variation-budget framework of Besbes et al. (2014; 2015). Theorem G.1 shows that in our setting the budget can be replaced by a rough estimate, which may come from domain knowledge or comparable products. Theorems G.2 and G.3 delineate when no estimate is needed. A fully adaptive algorithm for heterogeneous contexts that pays only the price identified in Theorem G.2 is an interesting direction for future work.

Weakness 2: computational complexity.

We have added a complexity analysis (footnote 7 and Appendix F).

  • Price in Line 14 is one convex program (Proposition F.1). The lower-envelope price is the optimal value of a second-order cone program (SOCP): minimize ⟨ut,x⟩\langle u_t,x\rangle over x≥0x\ge 0 with ∥x∥≤1\lVert x\rVert\le 1, subject to the relaxed feedback constraints. All scales share one feedback history and differ only in a common offset, so a single SOCP that computes the smallest consistent relaxation classifies every scale as active or not. Each round therefore uses at most one SOCP with at most d+1d+1 variables, at most a−1a-1 feedback constraints, dd nonnegativity constraints, and one ball constraint. The ellipsoid updates add O(d2log⁡T)O(d^2\log T) arithmetic per round. The algorithm runs in polynomial time.

  • Constraint set does not grow with TT. Constraints are discarded at every restart, so a batch holds at most a−1a-1 of them. An exploration-only variant (Proposition F.2) adds a constraint only after exploration rounds. It satisfies the same regret bound as Theorem 4.1 and holds at most O(d2log⁡2T)O(d^2\log^2T) constraints per batch. With an interior-point solver, each solve then costs O(d5log⁡3T(1+log⁡(g0/ε)))O\bigl(d^5\log^3T(1+\log(g_0/\varepsilon))\bigr) arithmetic operations to accuracy ε\varepsilon, where g0g_0 is the initial duality gap. On all shared instances in Appendix I.3, this variant's regret matches the original's at the displayed precision.

AuthorsOpenReview ↗

Response to Reviewer Hqjo (Cont.)

Minor: experiments on real data.

We have added numerical experiments in Appendix I, on deliberately constructed instances with d=3d=3 and V=1V=1. Their main purpose is to complement Example 4.1. That example uses prescribed prices, whereas the experiments run the single-scale algorithm with its own prices and feedback. They provide numerical evidence that single-scale shallow pricing, even when tuned at the scales required by Proposition D.5, does not attain the square-root regret of our multiscale algorithm on these instances. With the same setup, we also evaluate three ablations of our algorithm, each of which changes one of its components.

  • Single-scale stress test (Appendix I.2). Proposition D.5 shows that a single-scale shallow-pricing method can have a uniform O~(T)\widetilde{O}(\sqrt{T}) guarantee only with margin δ=Θ~(T−1/2)\delta=\widetilde{\Theta}(T^{-1/2}) and window a=Θ~(T)a=\widetilde{\Theta}(\sqrt{T}). We test 34 tunings at these scales, using the algorithm's actual prices and purchase feedback. For the canonical tuning, normalized regret RT/TR_T/\sqrt{T} grows from 1.92 at T=106T=10^6 to 116.96 at T=1020T=10^{20}, compared with 4.01 on a stationary control. At T=1032T=10^{32}, the best of all 34 tunings still has RT/TR_T/\sqrt{T} of about 542.

  • Comparison on shared sequences (Appendix I.3). All methods run on the same frozen instances. Algorithm 2's RT/TR_T/\sqrt{T} grows slowly, from 3.94 at T=106T=10^6 to 29.71 at T=1020T=10^{20}, consistent with its log⁡2T\log^2T factor. At T=1020T=10^{20} it incurs about 74.6% less regret than the single-scale baseline. The ablations show that both restart mechanisms matter: without periodic restarts, RT/TR_T/\sqrt{T} reaches 63,531 at T=1020T=10^{20}.

We hope these additions address the main concern. We would be glad to clarify any point during the discussion period, and would appreciate it if you would reconsider your score.

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.

Reviewer_uW3hOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studied contextual dynamic pricing with binary purchase feedback in a non-stationary environment. Buyer's value is linear in context. The feature vector may change over time. For identical contexts, the paper combines binary search exploration, a lower-envelope price and two complementary restart mechanisms. For heterogeneous contexts, the paper develops a multiscale shallow-pricing algorithm. A larger scale certifies localization, and the smallest active scale sets the price. The paper is purely theoretical.

Critical strengths
  1. This paper studies an interesting topic, pricing under a non-stationary environment. It solves difficulties arising from the interaction between contextual heterogeneity and non-stationarity.
  2. The theoretical results are well provided.
Critical weaknesses

The paper has no experiments. Although the paper gives theoretical guarantee, pricing problem is a very practical problem. To show the practical meaningful of the proposed methods, real data analysis is necessary.

Questions for authors
  1. Can you give some experimental results and compare with existing methods?
  2. The upper bound has d2d^2 and d3/2d^{3/2} factors, while the lower bound does not depend on d. Is anything known about the optimal dependence on d?
2 comments
AuthorsOpenReview ↗

Response to Reviewer uW3h

We sincerely thank you for the positive assessment and for the questions on empirical evaluation and on the dependence on dimension. We respond to each point below.

Weakness and Q1: experiments and comparison with existing methods.

We have added numerical experiments in Appendix I, on deliberately constructed instances with d=3d=3 and V=1V=1. Their main purpose is to complement Example 4.1. That example uses prescribed prices, whereas the experiments run the single-scale algorithm with its own prices and feedback. They provide numerical evidence that single-scale shallow pricing, even when tuned at the scales required by Proposition D.5, does not attain the square-root regret of our multiscale algorithm on these instances. With the same setup, we also evaluate three ablations of our algorithm, each of which changes one of its components.}

  • Single-scale stress test (Appendix I.2). Proposition D.5 shows that a single-scale shallow-pricing method can have a uniform O~(T)\widetilde{O}(\sqrt{T}) guarantee only with margin δ=Θ~(T−1/2)\delta=\widetilde{\Theta}(T^{-1/2}) and window a=Θ~(T)a=\widetilde{\Theta}(\sqrt{T}). We test 34 tunings at these scales, using the algorithm's actual prices and purchase feedback. For the canonical tuning, normalized regret RT/TR_T/\sqrt{T} grows from 1.92 at T=106T=10^6 to 116.96 at T=1020T=10^{20}, compared with 4.01 on a stationary control. At T=1032T=10^{32}, the best of all 34 tunings still has RT/TR_T/\sqrt{T} of about 542.

  • Comparison on shared sequences (Appendix I.3). All methods run on the same frozen instances. Algorithm 2's RT/TR_T/\sqrt{T} grows slowly, from 3.94 at T=106T=10^6 to 29.71 at T=1020T=10^{20}, consistent with its log⁡2T\log^2T factor. At T=1020T=10^{20} it incurs about 74.6% less regret than the single-scale baseline. The ablations show that both restart mechanisms matter: without periodic restarts, RT/TR_T/\sqrt{T} reaches 63,531 at T=1020T=10^{20}.

Q2: optimal dependence on dd.

Thank you for this question. The optimal dependence on dd is open, and we have added a remark discussing it at the end of Appendix E, after the proof of Theorem 4.1.

  • Lower bounds. Our lower bound is inherited from identical contexts and is therefore dimension-free. Some growth in dd is nevertheless unavoidable even without variation. If the contexts cycle through the coordinate vectors, the problem splits into dd fixed-value pricing problems with values in [0,1/d][0,1/\sqrt{d}]. The Kleinberg--Leighton lower bound then gives Ω(dlog⁡log⁡(T/d))\Omega\bigl(\sqrt{d}\log\log(T/d)\bigr) for deterministic algorithms in our normalization. Under their normalization, Liu et al. (2021) establish Ω(dlog⁡log⁡T)\Omega(d\log\log T) for stationary contextual pricing. Whether the variation-dependent term must grow with dd remains open: the same construction gives nothing beyond Ω(TV)\Omega(\sqrt{TV}), because the norm constraint shrinks each coordinate's value range.

  • Where upper-bound factors come from. Up to lower-order terms, our proof bounds the regret by E(T/a+V/δ)+F(Tδ+aV)E(T/a+V/\delta)+F(T\delta+aV). Here E=O(d2log⁡2T)E=O(d^2\log^2T) is the number of exploration rounds per batch, which comes from the volume decrease of shallow cuts (Cohen et al., 2020). F=8dF=8d bounds the loss of an accepted price and comes from the width threshold 4dλ4d\lambda below which a shallow cut is unavailable. Balancing the four terms gives d3/2=d2⋅dd^{3/2}=\sqrt{d^2\cdot d}, the geometric mean of the two factors, while d2d^2 is the exploration cost of a single batch.

  • Possible improvements. An improvement in either factor would carry over to the regret bound. In the stationary problem, intrinsic-volume methods (Paes Leme & Schneider, 2018; Liu et al., 2021) attain O(dlog⁡log⁡T+dlog⁡d)O(d\log\log T+d\log d), compared with O(d2log⁡2T)O(d^2\log^2T) for our bound at V=0V=0. Whether such methods remain effective under the relaxed, multiscale constraints needed to track drift is an interesting open question.

Thanks for your detailed response. I am satisfied with your response. However, my original rating 3 is a reasonable evaluation of your paper. So I keep my score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of revisions

We thank the three reviewers for your careful reading and constructive comments. The reviews raised five shared themes: the known variation budget (Hqjo, 7v9U), the noiseless valuation model (7v9U), the necessity of multiple scales (7v9U), computational cost (Hqjo), and empirical evaluation (uW3h, Hqjo). We have revised the manuscript to address each of them, with all changes marked in blue. The model, the algorithms, and the main theorems in Sections 3 and 4 are unchanged. The main text adds only a short discussion section (Section 5), all new formal statements and proofs are in the appendix, and the main text remains within the 10-page limit.

1. Budget uncertainty and valuation noise (new Section 5, Appendices G and H)

  • Misspecified budget (Theorem G.1). Algorithm 2 tuned with any estimate V^\widehat{V} has regret O~(d2+d3/2(TV^+V(θ)T/V^))\widetilde{O}\bigl(d^2+d^{3/2}(\sqrt{T\widehat{V}}+V(\theta)\sqrt{T/\widehat{V}})\bigr), where V(θ)V(\theta) is the realized variation. No relation between V^\widehat{V} and V(θ)V(\theta) is assumed. An estimate within a factor κ\kappa of V(θ)V(\theta), in either direction, inflates the variation term by at most κ+1/κ\sqrt{\kappa}+1/\sqrt{\kappa}. With no estimate, the default V^=1\widehat{V}=1 gives O~(d2+d3/2T(1+V(θ)))\widetilde{O}\bigl(d^2+d^{3/2}\sqrt{T}(1+V(\theta))\bigr).

  • Unknown budget (Theorems G.2 and G.3). Without a budget, the direction of change matters even for identical contexts. Any deterministic policy with polylogarithmic regret on a constant value incurs regret T/polylog⁡(T)T/\operatorname{polylog}(T) on some sequence with a single upward jump. Hence every budget-free deterministic policy incurs Ω(T)\Omega(\sqrt{T}) regret on the stationary sequence or on such a jump sequence, and the default tuning attains O~(T)\widetilde{O}(\sqrt{T}) on both. When values are nonincreasing, a budget-free policy achieves O(log⁡T+T(v1−vT))O\bigl(\log T+\sqrt{T(v_1-v_T)}\bigr).

  • Valuation noise (Theorems H.1 and H.4). With i.i.d. shocks of variance at most σ2\sigma^2, a reduction to noiseless pricing in dimension D=d+1D=d+1 gives full-surplus regret O~(D2+D3/2TV+D2Tσ2/3)\widetilde{O}\bigl(D^2+D^{3/2}\sqrt{TV}+D^2T\sigma^{2/3}\bigr). Every policy, even one that knows the shock distribution, incurs Ω(Tσ2/3)\Omega(T\sigma^{2/3}), so the noise dependence is tight at fixed dimension.

2. Computational complexity (footnote 7, Appendix F). Each round uses at most one second-order cone program (SOCP) with at most d+1d+1 variables, plus O(d2log⁡T)O(d^2\log T) arithmetic. An exploration-only variant keeps the regret bound of Theorem 4.1 and caps the number of feedback constraints at O(d2log⁡2T)O(d^2\log^2T) per batch (Proposition F.2).

3. Necessity of multiple scales (footnote 6, Appendix D.4.2, Appendix I). Proposition D.5 shows that a single-scale method can have a uniform O~(T)\widetilde{O}(\sqrt{T}) guarantee only with margin δ=Θ~(T−1/2)\delta=\widetilde{\Theta}(T^{-1/2}) and window a=Θ~(T)a=\widetilde{\Theta}(\sqrt{T}). Appendix I stress-tests 34 tunings at these scales using the single-scale algorithm's actual prices. It also compares Algorithm 2 with the single-scale baseline and three ablations on shared sequences.

4. Minor edits. One sentence in the abstract on these extensions, a remark on the dependence on dd (end of Appendix E), cross-references in Appendices A and B.1, and notation fixes.

We respond to each reviewer individually below.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.