Non-Stationary Contextual Pricing with Safety Constraints
Authors: Dheeraj Baby
Jianyu Xu
Yu-Xiang Wang
Venue: Accepted by TMLR ()

Abstract: In a contextual pricing  problem, a seller aims at maximizing the revenue over a sequence of sales sessions (described by feature vectors) using binary-censored feedback of "sold" or "not sold". Existing methods often overlook two practical challenges (1) the best pricing strategy could change over time; (2) the prices and pricing policies must conform to hard constraints due to safety, ethical or legal restrictions. We address both challenges by solving a more general problem of "universal dynamic regret" minimization in proper online learning with exp-concave losses --- an open problem posed by Baby & Wang (2021) that we partially resolve in this paper, with attention restricted to loss functions coming from a generalized linear model.  Here "dynamic regret" measures the performance relative to a non-stationary sequence of policies, and "proper" means that the learner must choose feasible strategies within a pre-defined convex set, which we use to model the safety constraints. In this work, we consider a linear noisy valuation model for the customers. In the case of a known strictly log-concave market noise, our algorithm achieves $\tilde{O}(d^3T^{1/3}C_T^{2/3} \vee d^3)$ dynamic regret in comparison with the optimal policy series, where $T$, $d$ and $C_T$ stand for the time horizon, the feature dimension and the total variation (characterizing non-stationarity) respectively. This regret is near-optimal with respect to $T$ (within $O(\log T)$ gaps) and $C_T$, and our algorithm is adaptable to unknown  $C_T$ and remains feasible throughout. However, the dependence on $d$ is suboptimal and the minimax rate is still open.

Published in Transactions on Machine Learning Research (10/2023)
Non-Stationary straints
Contextual
Pricing
with Safety
Con
Dheeraj Baby
dheeraj@cs. ucsb. edu
Deportment of Computer Science University of California, Santa Barbara
Jianyu Xu
zu mu 1y1550ss. ucsb. edu
Department of Computer Science University of Colifornia, Santa Barbara
Yu-Xiang Wang
yuriangw@cs. ucss. edu
Department of Computer Science University of Colifornia, Santa Barbara
Reviewed on OpenReview: https: openreview. net/
nett forum? id- fWIQ90aa00
Abstract
In contextual pricing problem, seller aims maximizing the revenue sequence of sales sessions (described by feature vectors) using binary-censored feedback of "sold" or "not sold". Existing methods often overlook two practical challenges (1) the best pricing strategy could change over time; (2) the prices and pricing policies must conform to hard constraints due to safety, ethical or logal restrictions. We address both challenges by solving a more general problem of universal dynamic regret minimization in proper online learning with exp-concave losses an open problem posed by Baby Wang (2021) that we partially resolve in this paper, with attention restricted loss functions coming from a generalized linear model. Here "dynamic regret" measures the performance relative to non-stationary sequence of policies, and "proper" means that the learner must choose feasible strategies within a pre-defined convex set, which we use to model the safety constraints. In this work, we consider a linear noisy valuation model for the customers. With the market noises drawn from a known strictly log-concave distribution, our amgorithm achieves 0(dT11/3 v dd) dynamic regret in comparison with the optimal policy series, where T, d and CT stand for the time horizon, the feature dimension and the total variation (characterizing non-stationarity) respectively. This regret is near-optimal with respect to T' (within Olog gaps) and Cr, and our algorithm adaptable to unknown Cr and remains feasible throughout. However, the dependence on suboptimal and the minimax rate is still open.
1 Introduction
crature-based dynamic pricing, or conterfual pricing, is a problem where the seller sets prices for different products based on their features and aims to maximize revenue. general, eustomer will make her decision based comparison between the price and her own valuation of the product. Formally, many existing works (e.g., Cohen et al., 2020; Javanmard & Nazerzadeh, 2019; Xu & Wang, 2021; Luo et al., 2021) adopt the following linear-feature valuation model:
for equal contribution.

---

Published in Transactions on Machine Learning Research (10/2023)
Contextual pricing. For t .:
1. A context 2; E R" is revealed that describes sales session (product, customer and context).
2. The customer valuates the product as Yt x 07 + N, using st-
3. The seller proposes price v, > concurrently (according to my and historical sales records).
4. The transaction is successful if e S yr: Le., the seller gets a reward (payment) of rz = vt 1 S yc).
Here T' is the unknown time horizon, ry's s are adversarial features (which can be stochastic or non-stochastic scries), 0t's s are hidden parameters mapping features to valuations lincarly, and N2's are i.i.d. noises drawn from known distribution D. Denote 1, == I(v S We) as the Booleun-censored feedback that equals 1 if 0 S Yt and otherwise, and we only observe 1, instead of the realized Y/ at each round. Our goal is maximize the cumulative expected reward, and the regret is defined as the difference of expected rewards between 2/ and the best price at each round.
Time-variant Bchavior and Dynamic Regret. Comparing with cxisting linear contextual pricing problem settings (e.g., Cohen et al., 2020; Javanmard & Nazerzadeh, 2019; Xu & Wang, 2021) where the linear valuation parameter 0g is fixed as the same 0 over all i, in this work allow moderate changing of customers' valuations: i.c. 07's can vary over time, and the total variation Σ l10; 6 ll1 upper bounded by some Cr (which could be unknown to the seller). Here we adopt the 11-norm bound because it is reasonable metric for capturing the non-stationarity of the valuation mechanism: For instance, suppose each element of 2z indicates the amount of one component of this product, and therefore each element of 0r indicates the unit price of this component. In this example, |0 - 0 ll2 reflects the general price fluctuations on the market, i.e., the sum of market-wise price changes over all components. To characterize the performance of a pricing scheme under this non-stationary sctting, we adopt the concept of dynamic regrel. In this notion, we compare the performance of ot we propose with that of the optimal pricing policy that knows the sequence of 0; in advance. A rigorous definition of this dynamic regret will be presented in Scction 2.3.
Proper Learning. Usually, the actions/strategies we are allowed to adopt are restricted some specific safe domains. Taking any action/strategy outside this domain would probably cause risky, illegal or inconsistent outcomes. Our algorithm works by maintaining an estimate, Oz, for the true valuation parameter 0ž at each round t, and we in turn take 0, a paremetric strategy for proposing the price e, according to greedy policy (sce Section 2.3 for more details). In this work, we require that the estimate 6, must fall in specific convex and closed domain D, at each round L. Here DD can be chosen adversarially with the constraint imposed by Assumption 1. As will be explained in Section 2.4, this is to address the fact that pricing strategies must. conform to hard constraints due to safety restrictions.
Universal Dynamic Regret and Proper OCO with co-variates. Next, we take a digression and describe a general Online Convex Optimization (OCO) setting which will play a pivotal role in solving the contextual pricing problem.
Proper OCO with co-variates. For ( -= 1,2, ..., T:
1. Adversary reveals co-variate 2; Rd.
2. Learner makes decision 0, in convex domain D, C Rd.
3. Adversary reveals convex loss function (,) g. (0 21).
This sctting embodies OCO under a wide range of loss functions from the generalized linear model (GLM) family for appropriate choices of gt- The co-variates 2, can be thought of as a feature that encodes valuable information about the context in round t which can be used by the learner to make its predictions. Examples of this setting include (but are not limited to) linear regression and logistic regression.
The goal the learner is to control its universal dynamic regret:
T
R(w1r) = Σ (())) (((ws),
(1)
t=1
2

---

Published in Transactions on Machine Learning Research (10/2023)
where w1-7 {wi, W2...., ) is any comparator sequence satisfying wy E Dr for all t E [T]. This is known to be a good metric in characterizing the performance of learner in non-stationary environments (Zinkevich, 2003). Dynamic regret bounds are usually expressed in literature as functions of the time horizon T and a path length that captures the smoothness of the comparator sequence such Cr T-- |000 wt+1lli.
1.1 Summary of Contributions
Our main contributions are given below.
1. We present an algorithm ProDR (Algorithm 1) that attains an optimal (T Cf V 1)) dynamic regret (modulo dependencics in d and log T) for the sctting of proper OCO with co-variates under exp-concave losses (see Section 3.1).
2. We construct an algorithm PDRP (Algorithm 2) with a base learner ProDR, which solves the non-stationary contextual pricing problem with strictly log-concave noise. We define the dynamic regret of contextual pricing as (3) and show that PDRP achieves O(d(TT' v v1) dynamic regret guarantee (scc Section 3.2).
3. We show that any algorithm must incur dynamic regret of C(T 1) in the contextual pricing problem, which says that PDRP is minimax optimal up to d and log I'' factors (see Section 3.3).
Novelty. Owing to the reduction of Xu & Wang (2021), the non-stationary contextual pricing problem can be reduced to an OCO problem with co co-variates and exp-concave losses. The key subroutine we developed - ProDR - is the first to achieve an optimal universal dynamic regret with exp-concave losses in the proper OCO with covariate setting. ProDR makes considerable progress towards addressing the open problem posed by Baby & Wang (2021) on the more general version of the above problem with general exp-concave losses (rather than GLM with known covariates). The only existing attempt to this open problem requires the decision set to be an Lo ball (Baby & Wang, 2022b), which cannot be used to handle arbitrary convex decision sets as we do.
Summary of techniques. The key technique in deriving ProDR is novel "transfer theorem" which takes the algorithm of Baby & Wang (2022b) (Le ball decision set) and converts it to optimal algorithm for the setting of proper OCO with co-variates under arbitrary conver decision sets. This idca is similar in spirit to the ppropee-ppropet reduction in the work of Cutkosky & Orabona (2018) where they consider general convex losses. However, a direct application of their reduction scheme cannot give fast. rates for exp-concave losses. To circumvent this issue, we propose new reduction schemnes that carefully take the curvature of the losses into account thereby allowing us derive fast and optimal dynamic regret rates under exp-concave losses (see Section 3.1 for list of technical challenges). Such a "transfer theorem" could be of independent. interest and impactful in the general context of non-stationary online learning. That the non-stationary dynamic pricing problem can be optimally solved using ProDR is a testament to this fact.
1.2 Related Works
Here we discuss how our work relates to the existing literature on dynamic pricing and dynamic regret.
Dynamic Pricing Dynamic pricing has been extensively studied under the single product (non-contextual) setting (e.g. Kleinberg & Leighton, 2003; Besbes & Zeevi, 2015; Wang et al., 2021), where the goal is to find and approach the best fixed price that maximizes the expected revenue. The problem is later generalized to contextual pricing where a feature 24 occurs at each time t and the customer's valuation is dependent on x;- A widely adopted model is the linear valuation (e-g., Cohen et al., 2020; Javanmard & Nazerzadeh, 2019; Xu & Wang, 2021), where they assume all customers' valuations are a fixed feature-to-vallattin mapping (i.e., 07 is fixed, Vt) adding i.i.d. noises drawn from known distribution. As result, the best price varies on different features occurring over time, and the goal turns to approach the best price in every round. However, the optimal pricing policy is static and the regret definition is a comparison of performance between our proposed price and the optimal policy that knows A* and the noise distribution in advance. In this work, we adopt this linear valuation setting and further generalize to non-stationary cases where the lincar mapping 0 is changeable over time. As a result, the best pricing policy also changes according to 6 and we have analyze the algorithmic performance in the scale of dynamic regret. Leme et. al. (2021) also studies non-stationary
3

---

Published in Transactions on Machine Learning Research (10/2023)
pricing problems and adopts the dynamic regret metric. However, their loss function and constraints are defined on realized valuations, different from our regret function defined on the expected valuations. Also, they adopt non-contextual problem setting and assume individual variation bounds on each pair of adjacent valuations like |Mt+1 - u/l S c for some 4 > 0,t = 1,2...., ,T Under their assumptions, they achieve an Ö(T+CA) optimal regret with a matching lower bound'. Given those differences in problem settings, their regret bounds are not applicable to our problem.
Some existing works on stationary pricing problems adopt contextual bandits to achieve sub-lineas static regrets (Tuo et al., 2021; Xu & Wang, 2022). Therefore, it is also possible to reduce our non-slationary pricing problem to non-stationary bandit problem (Chen et al., 2019; Cheung et al., 2022; Zhao et al., 2020a). However, similarly to what Amin et al. (2014) indicates in stationary contextual pricing, a direct application of non-stationary bandit algorithms to our known-noise- dynamic regret. Such a reduction might be optimal without the knowledge of noise distribution, but it is beyond the scope of this work.
setting might cause sub-optimality in
Besides, a recent stream of works study the pricing problems under constraints on inventory (Chen & Gallego, 2022), reserve-price (Niu et al., 2020), fairness (Cohen al., 2021; 2022; Xu et al., 2023; Chen et al., 2023) and budget (Salehi & Mirmohammadi, 2023), etc. Our work also contributes to this series we enforce safety constraints and adaptively measure the impact of those constraints on the dynamic regret.
Dynamic Regret. There is rich body of literature aimed in minimizing the universal dynamic regret. (Eq. in OCO setting where the earliest works can be traced back to Zinkevich (2003). When the revealed losses are convex, Zhang et al. (2018) proposes algorithms to attain an optimal dynamic rogret rate of O(VT(1+ + Pr)) where Pf E || Wx+1l|2- When the loss functions are gradient Lipschitz, problem dependent regret bounds have been developed in the work of Zhao et al. (2020b). In addition to gradient Lipschitznsss, if the losses have extra curvature propertics such as exp-concavity, Baby & Wang (2021) proposes algorithms that attain a near optimal dynamic regret of OT(T1//3 V1) (Ō* hides dependencies dimensions and factors of logT). The work of Baby & Wang (2022b) shows similar rates for non-smnooth and expcconcave losses in a proper learning setting when the decision set is an Lx- ball. In contrast, our work is able to attain near optimal rates for arbitrary convex decision sets for a large family of exp-concave losses. Further Baby & Wang (2022b) also shows optimal rates for arbitrary bounded convex decision sets when the losses are strongly convex.
If we take all the comparators we in (1) to be same, one recovers the notion of static regret. There are works that aim in controlling the statie regret in any time window which makes them suitable for learning in non-stationary environments. These algorithms fall into the category of adaptive strongly adaptive regret minimization algorithms. Examples of such methods include Hazan & Seshadhri (2007); Daniely et al. (2015); Adamskiy et al. (2016); Jun et al. (2017); Cutkosky (2020); Baby et al. (2021); Zhang et al. (2021). We refer the readers to Baby & Wang (2021) and references therein for a more inclusive survey on dynamic regret and strongly adaptive algorithms.
There has also been recent advances (e.g. Zhao et al., 2022; Baby & Wang, 2022a) in applying online learning techniques to design controllers. In particular, Baby & Wang (2022a) uses a reduction from Linear Quadratic Regulator (I.QR) problem to online (mini-batch) línear regression problem due to the work of Foster & Simchowitz (2020). They employ black-box reduction technique to convert the algorithm of Baby & Wang (2022b) to one that attains optimal dynamic regret for online lincar regression under the setting of proper learning. This is facilitated by exploiting the constant hessian property of linear regression losses. However, this property will not be satisfied for exp-concave losses in general. As such is unclear that the black-box reduction techniques of Baby & Wang (2022a) are generalisable beyond linear regression. Hence the results in this paper are not directly implied by their results. We direct the readers to Baby & Wang (2022b) for an elaborate discussion about the literature on online learning and control.
1 Here we reduce their loss bound our notations.
4

---

Published in Transactions on Machine Learning Research (10/2023)
2
Notations and Problem Setup
In this section, specify necessary mathematical symbols and notations, and define functions for algorithm design and regret analysis. We also present three examples to illustrate the concept of proper learning in contextual pricing.
2.1 Symbols and Notations.
The pricing process consists of T rounds. Tz, R", Vi E, i E.R and N₂ R denote the feature vector, the linear valuation parameter, the customer's valuation, the seller's price and the noise at time i, sequentially. At each round, we receive a payoff (reward) Tt Ur Lo, where the binary variable 1, indicates the customer's ss decision, i.c., 1 = 1(u I ye).
2.2 Technical Assumptions
Denote norm-bounded domain family DØ 10 E RR 1101, S B}. We firstly present assumptions on domain constraints of 24 and 87:
Assumption 1 (Domain Constraints). Assume 34 E Dr where Dr S D2 is convex and closed, and o E Dr where every De C DJ C also convex and closed. Each Dj can be chosen adversarially and is known to the learner before time t.
Here want the customers' valuations to be bounded. Equivalently, we may also assume that D, S D and Dr C DD B/B/ for any B, > 0. With these assumptions, we know that | 0 s B, 44 E Dz I = 1,2, 1,2,...,? T, Next, we make reasonable assumption on customers' expected valuations:
Assumption 2 (Non-Negative Expected Valuation). For a customer's valuation y/r x 6,, we assume the expected valuation x. 07 0, 1. 1.,....,T.
Now we make assumptions on the distribution of noise N, We firstly present the definitions of log-concavity and strict log-comoun coycoocovityy on 1-dimensional distributions according to Prékopa (1973).
Definition 2.1 (Log-concavity and strict log-concavity). probability mcasure defined on R is said to be log-concave and only if for any pair A, B c IR of intervals, it holds that
P(AA+ + (1 - A) 2 (P(A)) (0,
Here '+' denotes Minkowski addition. Also, is strictly log-coneave and only if for any pair A, B C IR of intervals, A & B, it holds that
+ (P()) e (0.1).
Then we make the following assumption:
Assumption (Valuation noise distribution). At each time t= = 1, 2......77 T, the noise N, is independently and identically sampled from a fixed strictly log-coneave distribution D with a twice continuously differentiable cumulative distribution function (CDF) F. Furthermore, the first and second derivatives of the CDF, denoted as ff and f', respectively are bounded by two finite constants By == supweR f(w) and Bp suPwER [f(()).
According to Definition 2.1, let (i) A (-00, B = (-o0, vi and (ii) A = (z, too), B = (y. +xo) respectively, and we have F' and (1 - F)) are both strictly log concaee functions, Existing works on contextual pricing also adopt log-concavity assumptions (sce Javanmard & Nazerzadch, 2019). For a detailed discussion on log-concave distributtons, we kindly refer the audience to Bagnoli Bergstrom (2006).
All of those three assumptions are supposed hold throughout the paper.
2.3 Functions and Key Quantities
Greedily Pricing. Here we adopt two functions defined by Xu & Wang (2021) and also make use of their properties. Firstly, we introduce an expected reward function g(v, u) == Err, v, v, 0- u] v (1 F(v- - u)) that unimodal wr.t. v. Secondly, we introduce a greedily pricing function J [u) argmax, u). Ju) has two important, properties: On the one hand, J(n) is strietly monotonically
5

---

Published in Transactions on Machine Learning Research (10/2023)
increasing, with J'(u)= E (0. Therefore, J(u) and (t) are bijections, Vu E U O. On the other hand, we have V 0) [x))l22 (x [0) |al|| S 1, which guarantees low price-changing rate while modilying parameter 0.
Restrictions on Actions/ /Parametric Actions/Paramedt always exists an 0, E R such that zi 0, = J- Therefore, for any price v/2 > 0, is equivalent to firstly propose a corresponding parametric strategy 0, (satisfying 2. J- (vz)) and then set the price as J(z 0,). Since we are approaching the optimal price (which is [z, 8*)) and that of E Dr, we may restrict the strategy 0g to be taken within Dr at each time t. We will explain more on the motivation of the restrictions in Section 2.4.
Strategies. When we lake an action by present ing a price ft, there
Negative Log-likelihood. We define
(()) -0, log (1-F F(u o)] (1 -1-1, 1,) log (F(u: x TT)
(2)
as a negative log-likeihood function at round t. Also, we define an expected log-likelihooo likklihhood function L := 02,(0) Ev, [e)(2)) 0/]. For the simplicity of notations in the following sections, we denote h₂(0) = 0z, E R, and
we show a property of h0):
Lemma 2.2. For 0 E D2,, there exist constants hmin S hmax < +00 such that
1max sup [0)( /1min = inf [0)( = 1, 2, ,. T. SED
BED
We prove this by noticing that h(0) is continuous and D is closed, and the details are in Appendix B.1. With this lemma, we may know that (f) is Lipschitz (see Lemma 3.8).
Dynamic Regret. Finally, we define the cumulative dynamic regret:
T
Reg. Σ (((((
g(ve, x, 0,).
(3)
We usually measure the regret a function of T, d and the total variation CT := D 10; 0 11-
2.4
Examples
Here we present three examples where the nature requires the strategies to lie in a "safe domain", regarding risk-taking, legal or consistency concerns.
Risk Control Adopting strategies outside a pre-defined and protected decision set can be very risky in general. Concerning contextual pricing problem, an extremely low price would lead to significant loss of profit. Therefore, we have to set a lower pricing bar for each item. At each time t, suppose the lower bar is Q 0, and therefore our parametric strategy 8g should satisfy S J(r 0t). Since J(u) is monotonically increasing, we have x T,,3 2
(c)( By intersecting {0 E (Rd 2 (-)() with the Lz-norm ball D we get a convex and compact set D,, in which any parametric strategy 0 satisfies the norm bound and will lead price not less than e given the [(x f) greedy pricing policy.
Legal Concern There exist laws or regulations regarding the highest price of some specific products. For each item with feature It, suppose that cannot set price exceeding G 0. Equivalently, the parametric strategy 0, we take must satisfy J(x 0s) q. Since J(u) is monotonically increasing, this is further equivalent to x; 0, < (c)) Therefore, the restricted strategy space D, is the intersection of x 0 < (c)} with the Læ-morm ball D which is a convex and compact set. Any parametric strategy falling out of D, would lead to either v, > C or ||] > B.
Price Consistency is important for the seller to consistent on setting prices, or otherwise might cause pricing discrimination. Specifically, if two identical items with feature occur time and t t 1, then their prices must be close to each other. In other words, we require JJ T J(x 8.41)l $ C, Vr Dz c D) for some constant C 0. For each Dr, we may solve it and get

---

Published in Transactions on Machine Learning Research (10/2023)
Algorithm 1 Proper Dynamic Regret minimization (ProDR)
1: Input: Base algorithm A, barrier multiplier G" O, exp-concavity factor 3.
for f 1.2..... do Get iterate 0, from A.
Feature Ta and proper domain D, are revealed 5: Output 8, = argminged, |ar] (0 0-)l-
6: Loss 4 is revealed.
Construct (0) as in (4) and set
7:
= G G. S.((),,
where S,(0) - min (1) 0)l; Send fi(0) as loss at time t. end for
JJ -) = S J(xTo.))
Denote this set as (x)), and we have D4+1 S ( Since 0g E S,(x), Vr, the intersection is non- emply.
3 Main Results
In this section, we present and analyse our algorithms. In Section 3.1, we first study the more general problem of universal dynamic regret (1)) minimization in proper OCO setting. Results of Section 3.1 will be applied in Section 3.2 to derive optimal algorithm for the non-stationary pricing problem. All omitted proofs in this section are deferred to Appendix B.
3.1 Dynamic Regret ProDR
In this section, we study the Proper Dynamic Regret minimization (ProDR) algorithm (Algorithm 1). We consider the protocol of proper OCO with co-variates introduced in Section
The goal of this section is to control the universal dynamic regret defined in Eq. We start by listing out the assumptions we made for the OCO problem.
Assumption A constant > 0 is known such that maxeeD, |0 S B for all & [n].
Assumption 5. The losses obey [[)(( G for all t [m] and 0 D, (recall that D. C DJ from Section 2.2).
Assumption 6. The losses are a exp-concave. ie le(v) 2 (x(x) VG(x) +)+ (v x)))² for a > 0 and for all x, E D.
Assumption puts a relatively mild constraint that a box enclosing all the decision sets known ahead of time. Lipschitzness assumptions like Assumption are standard in online learning. Assumption states that the loss exhibits strong curvature in the direction of its gradients (see Hazan et al., 2007, as an example). We will exploit this curvature to derive fast regret rates.
Qualitative description of ProDR. The base algorithm A in ProDR is expected to optimally control the dynamic regret under exp-concave losses and when the decision set is box: D {z Rd || < B), where B is as in Assumption 4. The idea is to perform a black-box reduction that can convert the base algorithm A to an algorithm that attains good dynamic regret guarantee on the domains D.. Though similar ideas have been already explored in the work of Cutkosky & Orabona (2018), our way of constructing such roductions for the current problem new and interesting in its own right in the context of exp-concave online learning. Next, we expand upon this matter highlighting the differences from Cutkosky & Orabona (2018). We construct losses fe in Line of ProDR where the (.) term acts as regularizer that penalizes A for

---

Published in Transactions on Machine Learning Research (10/2023)
predicting points outside D.- We would like the losses to be exp-coneave the base algorithm A expects. However, a direct application of the techniques of Cutkosky & Orabona (2018) does not satisfy this property. We address this issue by carefully constructing ft as in Line 7 of Algorithm 1 such that: 1) gradients of both (0) and S,(0) lie in the span of co-variate and 2) (0) is exp-concave, meaning that it exhibits strong curvature along the direction of Iz. Now, 1 and 2 together implies that the surrogate losses ft still remains exp-concave as it cxhibits strong curvature along the direction of its gradiont (which is spanned by #t). The particular choice of (0) is found to be crucial in preventing the exp-concavity factor of losses fa from collapsing to zero. We will show that the dynamic regret of ProDR w.r.t. losses & is upper bounded by the dynamic regret of the base algorithm A wrt losses Ja which is well controlled.
We next describe the dynamic regret guarantees of Algorithm 1. We inherit all the notations used in the algorithm description.
Theorem 3.1. Let B min(a/221
and a(2GBB and G' 1 Let
A in ProDR algorithm be FLH-ONS (Fig.1 1 in Appendia: A) instantiated with parameters Ç 27/25, 9 = GG' and o = B. Then ProDR (Algorithm 1) satisfes
& E 4.0.) lo(we) ( - v1).
where CT = 1 G, B,B. and poly- loyyllogoit factors T. T.
|w, -
wr-illi wr-ll with wa E Dr. VVb: maxfa, and Ô hides dependence of constants
Remark 3.2 (Adaptivity to Cr). In light of the Q(dB² log T'v d //331//3 B4/3) lower bound (see Baby & Wang, 2021, Proposition 11), we see that the ProDR algorithm adapts optimally to the path variation Cr of the comparator sequence, which may not be known ahead of time.
Proof. Due to the a exp-concavity of losses & over the domain D and B S a
we have that:
2
(0) El((.) + (E) Q.) B (0
for any 0 E Dj. Hence following Hazan et al. (2007), we consider the linear-reggression-yyye surrogate losses:
(,))) = Ve,(0)) (0 (0-00))(000))33 + 1
(4)
2/B
Hence for any 0 E D. we have that
1 (.( (.(0.) 2.(
((00))e((0)
(5)
43
where we used the fact that (..)) 43.
Given that 5.(0,) = (., 0 since 07, 0, E Dr, we have
f((0)) (0)), f((.)) 2.(0.)
(6)
8

---

Published in Transactions on Machine Learning Research (10/2023)
Let us denote Vl((0) h.(0)z, where h4(0) g1(0; 0). Now, according to the definition of Se(0) and dr, we have:
(()),) =l.(0.) + G' S.((,)
(.,())) + G" min
(l.( (n - 6:)l
NED,
-,,(0) G' min he (6()))] (n 0c)l nED.
-l((0) +G' Ihe(0r)llzz (0: 0.1
=l((0)) + G" (V(((,)) (0, 0.)-
Next we proceed to upper bound the regret w.r.t. losses & by the regret w.r.t. losses fa. We need the following lemma.
Lemma 3.3. Under the assumptions of Theorem 3.1, have that
(²x(0) (.())) s G² (O)) 0.)l
for any 0 E D& where G' = 2GBBVB))
The proof is shown in Appendix B.2. With this lemma, we have
(..))) - (6.) G (V.( (0. 0.)1 f(.)).
Combining the above inequality with Eq-(6) (6) we obtain
(,, (0)) - f((O,) - f(())-
Now using (5) along with the previous relation yields that
T Σ - < Σ
T
f((0) f(())).
t=1
The following lemma specifies how to compute the sub-gradient of the regularizer term (e) in Line of Algorithm 1. Further it highlights an important property that a sub-gradient of S,(0) lies in the span of covariate (recall that (e) = h(0)z.). This is also useful for proving the joint exp-concavity of the losses Л-
Lemma 3.4. The function (0) is conver across Rd, Denole ne = argmin, |og (1 [)]- When Ve,(0.) 0) + O, we have:
(S,(0) Ver(d.), if Ve,(O)TTTn 0) < 0 Vee(O.), if ver(0.) (m(() 0) >
When (l.(0.)T(m.(0)) - 0) = 0, we have 0 (S)
The proof of Lemina 3.4 is in Appendix B.3. In the next lemma, we show that the losses Sa remain exp-concave with appropriate exp-concavity factor bounded away from zero. This is the key lemma that helps to control the regret of ProDR.
Lemma 3.5. Define 7 = / We have that the surrogate losses St are 27/25 exp-concave and 2GG' Lipschitz in Ta norm across DB
9

---

Published in Transactions on Machine Learning Research (10/2023)
Algorithm Proper Dynamic Regret Pricing (PDRP)
Input: Noise distribution ID (including its CDF and PDF f).
ProDR algorithm A instantiated in Theorem 3.1.
for = ..,,..., T: do
Feature 2e and proper domain Dj are revealed and sent to A.
4: Get 0g E Dr from A.
5: Seller proposes 1t- J(, 0,) and receive 1.
6: Send loss (() defined in (2) to A.
7: end for
As is stated earlier in this section, the intuition of this lemma comes from two facts: (1) both (,, and (0) are the span of zt, and (2) (e( exp-concave. As a result, the strong curvature of (0) along the ž direction "absorbs" the plain convexity of S,(0) and therefore guarantees the exp-concavity of f((
We defer the detailed proof to Appendix B.4. Hence from Baby Wang (2022b, Theorem 10) FLH-ONS algorithm (Fig.1 in Appendix A) run with parameters Ç ç 24/25, G GG' and Φ B can be used to control
E1(00) fc(0.) =ō (C Gf Der v1)
-0 ( v1)).
where the last line is got by plugging in the values of y and G' and upper bounding further.
3.2 Dynamic regret of PDRP
In this section, we present our main algorithm for controlling the dynamic regret on contextual pricing problem, the Proper Dynamic Regret Pricing (PDRP) (Algorithm 2).
Qualitative description of PDRP. Xu & Wang (2021) observes that the pricing problem can reduced the setting of proper OCO with co-variates and exp-concave losses. This observation, armed with the ProDR algorithm, naturally lends itself to the algorithm PDRP for controlling dynamic regret of the pricing problem.
We are now ready to present regret guarantees for the non-stationary pricing problem.
Theorem 3.6. Consider the linear noisy contertual pricing problem defined in Section 1. Assume that we know the noise distribution D eractly. By properly initializing 3,y and G' with pre-knowledge, PDRP (Algorithm 2) obeys Reg, ((d C7 v 1)), where Regr as defined in (3, Ô hides poly-logarithmmic factors of T and (a v b) ma
Proof. We start with the lemmas that help us leverage the OCO framework of Section 3.1.
Lemma 3.7. (Xu & Wang, 2021, Lemma 5 and 6) Under the assumptions in Theorem 3.6, for f D we have:
2C
TTTO) 0,) g([(x]] 0); 0,) Cdown g( 0,, x.
(F](e(() (0))))
where l, is defined in E2), C 2B, + (B Bp and
8 log(1 - F(w))
d (log(F(w))
Crown =
inf wE[-B.B+J(0)
min
> 0.
du2
du2
So we have
2C
Reg, < Caown
Ele,(0.) - E,(0)))
(7)
10

---

Published in Transactions on Machine Learning Research (10/2023)
Next, record the curvature and smoothness properties of losses Le.
Lemma 3.8. Let G = hmax defined in Lemma 2.2. Under the assumptions in Theorem 3.6, for E Dr, we have: (1) (() is G-Lipschitz in llz norm, and (2) (e( Cdown -erp-concave. Here Cexp = Cexp
B.P max [(w] riw3
[(W) (I-F(W])) } and Cdoon defined in Lemma 3.7.
This lemma is derived from Xu & Wang (2021) Lemma 7, and we defer the proof to Appendix B.5. The lemına above implies that the losses satisfy Assumption 5 in Section 3.1. Further they satisfy Assumption 6 with concavity factor of Cdown/ Ceep. So we can use the ProDR algorithm (Algorithm 1) to control the dynamic regret wrt losses l, Let 3 min(Cdown/ (/ (() and 7 (32t//3++/ and
G' =11 GBV /Cezp. Henee continuing from (q. we apply Theorem 3.1 to obtain
Regr S =o (
2/3 v1).
This completes the proof of the theorem.
Remark 3.9. Although noise distributions are known we assumed, the coefficient of our regret upper bound depends highly on the distribution. As is indicated by Xu & Wang (2021), when the noise N, is an i.i.d. Gaussian noise with zero mean and a standard deviation, this coefficient is exponentially large w.r.t. 1 as o approaches 0, which is counter-intuitive.
3.3 Lower Bound on Dynamic Pricing Regret
So far, we have developed a ProDR algorithm that is suitable for linear model, and have constructed a PDRP algorithm to solve the linear contextual pricing problem where PDRP achieves Ö(d C... v v)) dynamic regret. This upper regret bound optimal for online exp-concave optimization is shown by Baby & Wang (2021), but is it still optimal for our feature-based dynamic pricing sctting in specific? The answer is Yes. This dynamic regret is near-optimal up d and log T factors, and here we present the following theorem.
optimization of generalized
Theorem 3.10 (Lower dynamic regret bound). Let == in the contertual pricing problem we consider.
For any algorithm A, there erists specific problem selting where A has to suffer on S(T C V1) expected dynamic regret.
With this theorem, we may claim that our PDRP algorithm near-optimal. We here show a proof sketch and defer the full proof to Appendix B.6.
Proof Skelch. The proof is developed in three steps: Firstly, we construct hypothesis set θ in which there are N different {0 series whose total variations are upper bounded by Cr. For any pair of two different scries (0:)7 's in θ they are identical for T/3 out of T rounds in total, and are different by some small 5 for the rest. 2T/3 rounds. Secondly, we show that their correspouding feedback distributions are also "similar" each other under the metric of KT.-divergence. Therefore, according Fano's Tnequality, any algorithm can hardly distinguish among these distributions. Finally, we show that a failure of correctly distinguish the underlying distribution (i.e., the real {0:)T= series) will result in an C V 1) regret.
4 Conclusion
In this work, we studied the non-stationary contextual pricing problem under safety constraints. We first presented the ProDR algorithm for minimizing universal dynamic regret in the framework of proper OCO with co- variates and exp-concave losses. This contribution could be of independent interest in the context, of non-stationary online learning. As a concrete application, we constructed our pricing algorithm, PDRP, by making use of ProDR as the base learner. We showed that PDRP attains a Ö(d O v1)) dynamic regret in our pricing problem setting. Finally, we proved that this rate information-theone theoretically optimal (modulo dependencies on d and log T).
11

---

Published in Transactions on Machine Learning Research (10/2023)
Acknowledgements
The authors very grateful to the associate editor András György and three anonymous reviewers for their constructive comments. This research is partially supported by NSF Award #2007117, the Adobe Data Science Research Award and a start-up grant from the UCSB Department of Computer Science.
References
Dmitry Adamskiy, Wouter M Koolen, Alexey Chernov, and Vladimir Vovk. A closer look at adaptive regret. The Journal of Machine Learning Research, 17(1):706-726, 2016.
Kareem Amin, Afshin Rostamizadch, and Umar Syed. Repeated contextual auctions with strategic buyers. In Advances in Neural Information Processing Systems (NIPS-14), pp. 622 630, 2014.
Dheeraj Baby and Yu- Yu-Xiang Wang. Optimal dynamic regret in exp-concave online learning. In Conference on Learning Theory, pp. 359 409. PMT.R, 2021.
Dheeraj Baby and Yu-Xiang Wang. Optimal dynamic regret in LQR control. In Aduances in Neural Information Processing Systems, 2022a.
Dheeraj Baby and Yu-Xiang Wang, Optimal dynamic regret in proper online learning with strongly convex losses and beyond. In International Conference on Artificial Intelligence and Stalislics, 1805 1845. PMLR, 2022b.
Dheeraj Baby, Xuandong Zhao, and Yu-Xiang Wang, An optimal reduction of tv-denoising to adaptive online learning. In Proccedings of The 24th International Conference Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, pp. 2899-2900 2021.
Mark Bagnoli and Ted Bergstrom. Log-concave probability and its applications. In Rationality and Equilibrium: A Symposium in Honor of Marcel K. Richter, pp. 217-241. Springer, 2006.
Omar Besbes and Assaf Zeevi. On the (surprising) sufficiency of linear models for dynamic pricing with demand learning. Management Science, 61 6144)7733-33, 2015.
Nicolo Bian-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press, New York, NY, USA, 2006. ISBN 0521841089.
Ningyuan Chen and Guillermo Gallego. A primal-dum dual learning algorithm for personalized dynamic pricing with an inventory constraint. Mathematics of Operations Research, 47(4):2585-266) 2022.
Xin Chen, Zexing Xu, Zishuo Zhao, and Yuan Zhou. Personalized pricing with group fairness constraint. In Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency, pp. 1520 1530, 2023.
Yifang Chen, Chung- Wei Lee, Haipeng Luo, and Chen-Yo Yu Wei. A new algorithm for non-stationary contextual bandits: Efficient, optimal and parameter-free. In Conference on Learning Theory, pp. 696 726. PMLR, 2019.
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Hedging the drift: Learning to optimize under nonstationarity. Management Science, 68(3):1696 191169936111111-1111111111111131 2022.
Maxime C Cohen, Ian Lobel, and Renato Paes Leme. Seature-based dynamic pricing. Management Science, 66(11):4921-49) -4492,, 2020.
Maxime C Cohen, Sentao Miao, and Yining Wang. Dynamic pricing with fairness constraints. Available at SSRN 3930622, 2021.
Maxime C Cohen, Adam N Elmachtoub, and Xiao Lei. Price discrimination with fairness constraints. Management Science, 68(12):8536 8552, 2022.
12

---

Published in Transactions on Machine Learning Research (10/2023)
Ashok Cutkosky. Parameter-free, dynamic, and strongly-adaptive online learning. In International Conference on Machine Learning, pp. 2250-22000 22599.25. PMLR, 2020.
Ashok Cutkosky and Francesco Orabona. Black-box reductions for parameter-free online learning banach spaces. In Thirty- First Annual Conference on Learning Theory (COLT-18), pp. 1493 1529. PMLR, 2018.
Amit Daniely, Alon Gonen, and Shai Shalev-Shwartz. Strongly adaptive online learning. In International Conference on Machine Learning, pp. 1405-1411, 2015.
Dylan Foster and Max Simchowitz. Logarithmic regret for adversarial online control. In International Conference on Machine Learning, pp. 3211 3221. PMLR, 2020.
Elad Hazan and Comandur Seshadhri. Adaptive algorithms for online decision problems. In Electronic colloquium on compulational complexity (ECCC), volume 14, 2007.
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2-3):169-195 192, 2007.
Adel Javanmard and Hamid Nazerzadeh. Dynamic pricing in high-dimensions. The Journal of Machine Learning Research, 20(1):315-363 2019.
Kwang-Sung Jun, Francesco Orabona, Stephen Wright, and Rebecca Willett. Improved strongly adaptive online learning using coin betting. In Artificial Intelligence and Statistics, pp. 943 951. PMLR, 2017.
Robert Kleinberg and Tom Leighton. The value of knowing demand curve: Bounds on regret for online posted-price auctions. In IEEE Symposium on Foundalions of Compuler Science (FOCS-03), pp. 594 605. IEEE, 2003.
Renato Paes Leme, Balasubramanian Sivan, Yifeng Teng, and Pratik Worah. Learning price against a moving target. In International Conference on Machine Learning, pp. 6223 6232. PMLR, 2021.
Yiyun Luo, Will Wei Sun, et al. Distribation-free contextual dynamic pricing. arXiv preprint arXiv:2109.0780 2021.
Chaoyue Niu, Zhenzhe Zheng, Fan Wu, Shaojie Tang, and Guihai Chen. Online pricing with reserve price constraint for personal data markets. IEEE Transactions on Knowledge and Data Engineering, 34(4): 1928-1943, 2020.
András Prékopa. On logarithmic concave measures and functions. Acta Scientiorum Mathematicarum, 34: 335-343, 1973.
Shabnam Salehi and S Hamid Mirmohammadi. A solution approach for sponsored search advertising and dynamic pricing for a perishable product and an online retailer with budget constraint. Computers & Industrial Engineering, 177:109086, 2023.
Yining Wang, Boxiao Chen, and David Limchi-Levi. Multimodal dynamic pricing. Management Science, 67 (10):6136-6155) 36122, 2021.
Jianyu Xu and Yu-Xiang Wang. Logarithmic regret in feature-based dynamic pricing. Advances in Neural Information Processing Systems, 34:13898-1333 13990, 2021.
Jianyu Xu and Yu-Xiang Wang. Towards agnostic feature-based dynamic pricing: Linear policies vs linear valuation with unknown noise. In International Conference on Artificial Intelligence and Statistics, pp. 9643-9662. PMLR, 2022.
Jianyu Xu, Dan Qiao, and Yu-Xiang Wang. Doubly fair dynamic pricing. In International Conference on Artificial Intelligence and Statistics, pp. 9941-9975. PMLR, 2023.
Lijun Zhang, Shiyin Lu, and Zui-Hua Zhou Adaptive online learning in dynamic environments. In Proceedings of the 32nd International Conference on Neural Information. Processing Systems, pp. 1340, 2018.
13

---

Published in Transactions on Machine Learning Research (10/2023)
Lijun Zhang, Guanghui Wang, Wei-Wei Tu, Wei Jiang, and Zhi-Hua Zhou. Dual adaptivity: A universal algorithm for minimizing the adaptive regret of convex functions. Advances in Newral Information Processing Systems, 34:24968 24980, 2021.
Peng Zhao, Lijun Zhang, Yuan Jiang, and Zhi-Hua Zhou. A simple approach for non-stationary linear bandits.
In International Conference Artificial Intelligence and Statistics, pp. 746-755. PMLR, 2020a.
Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Dynamic regret of convex and smooth functions. Advances Neural Information Processing Systems, 33:12510-12520, 2020b.
Peng Zhao, Yu-Xiang Wang, and Zhi-Hua Zhou. Non-stationary online learning with memory and non- stochastic control. In International Conference on Artificial Intelligence and Slalistics, pp. 2101 2133. PMLR, 2022.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pp. 928 936, 2003.
14

---

Published in Transactions on Machine Learning Research (10/2023)
A
Preliminaries
For the sake of completeness, we recall the description of the Folow-tthe-rcaddn--Hittoo (FI.H) algorithm (sce Hazan & Seshadhri, 2007).
FLH: imputs Learning rate <, 9, Φ > 0 and T' ONS base learners E* ..... E² initialized with parameters G = g, D 20v ك and decision set D {0- Ted |10||>> I Φ). The learner Fg starts operating from time t.
( is a probability vector in R Initialize For each L, it (1g ,...,
(1)
o -1
2. In round set Vj St, 0f t- (1) (the prediction of the j base learner at time t). Play 0 Ej=1 rt (l)
3. Afler receiving loss Jt, set 0/41 and perform update for isisi:
(1) (S
(3) Σj= Us e cF((0
((+1) Addition step Set e+1 to 1/(1 + 1) and for i i ++
(0) = (1 - (1+ + 1) 10
Figure 1: FLH algorithm
Next, we describe the Online Newton Step (ONS) algorithm (see Hazan et al., 2007).
ONS: inputs Exp-concavity factor a and G, 0, Decision set D.
1. At round 1, predict 0. Let 1 min ad.. a).
At iteration
> 1 prodict:
1
Wi E argmin DED
[4-1
3 1-1
A V 1-1 011A,-17
where V. Vi(w),, A,
1a 3rD
Σ == V.V.
Figure 2: ONS algorithm
B Detailed Proof
B.1 Proof of Lemma 2.2
Proof. To begin with, we know that
f(w)
+ 11) f(w)
he(0) --1: 1- F(w)
F(w)²
where w = vz - xTo. 0. Since 30, E D, such that v, = [xx 0c), given that J'(u) E (0,1) (see Xu Wang. 2021, (q9()))), we know that w (J(-B) - B, (BB + B] is bounded a closed interval. Since we assume that f(w) O, Yw R, we know that fmin BB f(w) 0 and F(w) e [F(((BB) B), F(J() B)] (0, 1). Remember that denote B, == supweR (ww) < too. As result, we have
0 < fmin $I-F(w) SWw) < 1- [-F(BB + B)
B,
< +00
f((w) < F(J(-B)- < +o0.
B,
0 < fuon
F(w)
15

---

Published in Transactions on Machine Learning Research (10/2023)
Since he(0)
f(w) 1- [(w) for 1.
1 h(t)
f(w) for 1. 0, we know that Ihe(0) e F(w)
By [minn ( (J) (J(-B) B)- BTT Let. Amax (J]BB- (J( BB] and Amin smaar and the lemma is therefore proved.
By
B.2 Proof of Lemma 3.3 Proof. We have that for any E DDB
00:
(e((0) ((()) 1/ VB. (0 8.]|
(0-0.) (e -bo)
(1+ 2GBBBBB (Q.( (0-0.)1-
where in the last line we apply triangle inequality and the facts that Ive.(0)) 0:)1 s G110 -O.lla with |10 0e|12 - 2B
Putting G' = + 2GB3vd completes the lemma.
B.3 Proof of Lemma 3.4
Proof. For the simplicity of notation, we denote V, := VV,(0,), and we have: S,(0) min V -r-
Since (,) is convex in Rd, we have:
S2(02) +,(0)) (VS, v0 DB.
Now we conduct an orthogonal decomposition (S, μr V where v. V. 0. Let 03 = 22 and we have V (a
02) = V (x 63) Vo RR. In other words, we have S,2)) = (0a) and therefore
we have:
S,(02) -)(())) 2 S,(0,) + (VS, - 01)
S.()) + (M V7 u2 01) - + (VS, - 01) + (2 Vt), V0, E Rd P2 E R
In other words, /2/ /2/| V+ 12 < S.2) - (.))) (VS,(0)))02 01) Denote m argmin [V (x 01)1, and
12 = argmin,eD, V (a 02)1. Notice that
S,(0)) - S.(01) V, (12 02)
V (m 01)
$ V (m 02)
V (n 0,)
V (01 - 02)1
(8)
< V |10 - 02112
SG- ||0: - 02112-
Here the first inequality comes from the definition T22 the second inequality is an application of the triangular inequality, the third inequality derived from Cauchy-Schwarz Inequality, and the last inequality is from Assumption A5 on the Lipschitzness of (0) over D.. Therefore, Se(0) is G-Lipschitz as well over DB and we have:
ual V < S,(02) -((0),(000)0) - (VS, 0,) 2G1 01112.
This holds for any 0,,0, 0, E D However, we may fix 0, and 0₂ while also let μ22 - too since it holds for any P2 E R. If | ll2 # then it will fall into a contradiction. Therefore, we know that V and (S, is always in the same direction of V..
16

---

Published in Transactions on Machine Learning Research (10/2023)
Without losing generality, denote (()) == A v, In the following, we will prove that À = =1 or O. From Eq. (8) line 3, we know that Sx(02) S,(01) - V (0: 02)] Combined with the convexity of (,))), we have:
V. (01 -0)-0)) 02) (0,( S,(0i)
(0)) (02 - 01)
(9)
= V. (02 - 01).
Notice that we can choose arbitrary 0g without changing X, may let 02 0 and 02 =00 in Eq. (9):
- V S V
If V 0, * O, then we have E [-1,1]] Otherwise, we know from Eq. (9) that |V 02| A. V 02, v02, and
similarly we have À E [-1,1]. Now we denote 0. tm, and we have:
(VS,(01).04 01) + S.(O)) = S,4)
(10)
from the convexity of S. And we also have:
S(())) min V (x 04)
V (m 04)
01 7
V St((1) 2
2
(11)
1
VV, (01 01)1
Sc(O1) I (0: 04)l
Combine Eq. (10) and (11), we have:
(VS,(0)).0, 0,) S,(00,)) S,(0i) - 0,)
(12)
Plug VS.(01) XV, to Eq. (12), and we have:
A V. (0. 81) 5 V (01 -8,)
(13)
According to Eq. (13), if V. (02 02) > 0, then we have X < -1; if V (0, 02) < 0, then we have X 2 1. Since we already know that X E [-1, 1), then for the two case we should have = -1 or x =
In this case, means that vī (m) argmin [ (x 01)]. we know that S,(1))
Finally, what V. (04 - 01)
0,)/2
0. Since y
this time. Since (,) 2 o, v0 R2 we know that 8,(0) > (0,) + 0 oT (0- 0,) and a result aS,( This in fact holds the lemma.
B.4 Proof of Lemma 3.5
Proof. We begin by noticing that (0) is exp-concave over DB_ To see this, note that by the triangular inequality and Cauchy-Schware Inequality,
-0 (V - 1/ 2GB 1/(2/3))
where use the fact that [V)(a(.))la < G by Assumption A5 and |10 0.112 < 2Bvd as 0 DB and 0, Dr c DB
17

---

Published in Transactions on Machine Learning Research (10/2023)
With y defined in the statement of the lemma, we have that the losses (,) are 2y exp-concave over D (see Cesa-Bianchi & Lugosi, 2006, Section 3.3).
Now we proceed to show that the losses fe( are in-fact exp-concave with appropriate exp-concavity factor. For the sake of brevity, let us denote
vl((u)= = 2/8 Vll((.) 00 2/3 V(((.)
: (((
We have that for any u, v D
(u()) 2 L(()) + v(u)) [o (w-w) u) u)
(p( (v-
(14)
Due to convexity, we have
S.(0) 2 S.(u) + X
(15)
for some À E {- per Lemma 3.4.
Adding (14) and (15), we obtain
f())) + V (u- u)
+rp(u)² (Ve(())) (( (w-u))
f((u)) + V.((u) ( (u-v)
+7 (> p(u) (Vii(u) (u -v-w))²
(x+p(u))
(16)
Next, we proceed to obtain a lower bound on the exp-concavity factor. Note that
p(u) 2 2/B -2GBB d3 + 2/8 2 2/B
4/3
where the first inequality is via Cauchy-Schwarz Inequality and the second inequality holds due to the fact that B < 1/(8GBVd) due to the setting in Theorem 3.1
Similarly we have that
pp(u) + Xj 4GBBV +25
where in the last line we used B < 1/(8GBVd).
Combining the last two displays, we have that.
( p(u) ((Pf()
) 2 7/25.
2
Applying this lower bound to (16(1 now yields the exp-concavity of f((0) claimed in the lemma.
Next, we proceed to calculate the Lipschitz constant of ft. Since ()))2 S G, by Lemma 3.4 we conclude that G' (0) is G'G Lipschitz in L2 norm across ddd Now using Lemma 3.3 we conclude that the losses f: are G are Lipschitz in L2 norm across BB
18

---

Published in Transactions on Machine Learning Research (10/2023)
B.5 Proof of Lemma 3.8
Xu & Wang (2021, Lemma 7) has proved the -xw-cex--onncavity Here we prove the other claim Lipschitzness.
Cesy
Proof. Notice that (0) is continuous function. Therefore, for any 01. 02 E De, there exists 0g c0, + (1 - =e]02 for some e E [0, such that
(e(0:) (((2)) Vle(Os) [01 62)
= (((())xz (0) - 02)
I mmnax |2<||2 vel12|101 02ll2
(17)
Mmax 00 02112
G 02112
where maxx defined in Appendix B.1. In (17) the first equality is by Lagrange interpolation, the second equality is by definition of he (0), the third inequality is by Cauchy-Scwaarz Inequality, the fourth equality is by the assumption that Ie D2, and the last inequality is from the fact that hmax G. Since Dr is convex, we know that 0g E D. Therefore, the lemma is proven.
B.6 Lower Bound Proof (Proof of Theorem 3.10)
Here we present and prove the following theorem, which sufficient to show a S lower bound for Cr
VT
Theorem B.1. Consider fealure-bused dynomic pricing problem with d d 1, xt = 1, N₂ miid. N( 1), o For any algorithm A there erists a specific setting such that A suffer Q(TiCH)
T and Cr > 1
expected regret even with yt observable.
The sufficieccy comes from the fact that we cannot observe any realized y.' in the pricing problem (but binary indicator instead). In comparison, the lower bound in Theorem B.1 even works for observable y1 's which is sufficient to derive the binary feedback (by comparing with 2z).
Proof. To summarize the procedure of proof: Denote [n] == {1, (1.2....,n) n) for any positive integer n. Define 0n = 1,0 1 + 5(T, where 8 - Cr) ) is an additional amount. Then we construct set S C 10, consisting of randomly-sampled g(6) E 1 1,2 that we will use to construct 0, series (each indicating a specific {6;} series) later. Afterward, we will show that the (0) and the (0)( series are hard to distinguish by any algorithm, and we will further show that a large enough regret caused by this misspecification. In this way, we prove expected lower regret bound (where the expectation is also laken over different (i)).
The process to sample each (00) is as follows: We split [T] uniformly into m = 1 intervals, with each length 30 ( and Cr 2 J/ we know that m 2 10. Denote these intervals as 7,, I2. .2....... Im- For any g(0) S, we construct it in a stochastic process: For each index interval I 1,2,.... m, we generate a random variable z(() ~ Ber()) independently, and then let ((()) = z VI E Ig. Denote the vector Z6) = (2 -,
OF Since
z!! I E 10,, and we know that (0) - 1 = T Accordingly, we m 178
have [[]] - 330 2
C+
Therefore, according to Hoeffding's inequality, we have:
Pr[l][Z(= - 260 m
m
m 2m
<
>1
2.
2
6
(18)
* Pr[l][300) -300
T
T
21
e
9 V. [N].
2
6
19

---

Published in Transactions on Machine Learning Research (10/2023)
By applying union bound over all (2) pairs of i.j E [NV, we have:
Pr[lllB0 - 11 -1
T
T
Vi.j E [N] 21 N2.
2
6
Also, we know that Pr[3() * 300] = = * -
1 for i i j. By applying a union bound over all 2
2) pairs of i.j, we have Pr[ + 3 2 1 I Combining these two probability bounds, we know that in this way we can find a satislactory set S with probability al least Pr 2 1- N (e F + 2m(++))). Let N e (and therefore log N m Cr ) and then Pr 12 # 2-- 2 1 1- Since the total number of possible S (i.c., any set consisting N (repeatable) vectors E (0, is (2 and we are uniformly sampling from this whole family, the expected total mumber of satisfactory S is at least (2 N, (1 - (e कhक + + =m)) Since m 2 10 as we showed above, we have (2 (1 - (e- wh e fm)) )) 2 210x1 (1 e 50 b) 31.0325 > 1. As result, there must exist at least one satisfactory S in the whole possible set family, such that: (1) T & [|(()) 3 < 27 3 and (2) g(d) + B(3,, vi # j E [N]. We here pick this satisfactory and in the following we use it. for further proof.
(N)
(E sob + + fm)
200
Now; for each 360 E S, we generate a sequence of parameter {07 (i)) according to 3(4;; For 1,2,..., let (1) = 1 + 8. a(0) i.e., if 360) = 0, then (i) = 0o 1; if 3 = 1, then (1) = 1 + 8. Therefore, we have the following result:
.,, T, we
TV(()(())) S mm 5= CT
< CT.
4
This is because 110| 0-+1 (i)l > 0 only if 3k E [m] s.t. t lx,t + 1 I+11. As result, the total variation of this (i)} satisfies the upper bound Cr.
Now, let us consider the realized valuation sequence {vi)- For any i E [N], denote
y(1) = [z] + 2(05) 5) + 22 + 08000 6) + N2,...,,yy (T + /44) + Nr)
Let us denote the distribution of y(i) as F,, 1,2,...,N. N. Recall that x, = 1 and N₂ W 1), Vt, and we have P. = [[1+ + 8 6, 1).A((1 + 3( 6. 8,1), 1).......((
8))T Consider the difference between P. and P, while fixing 800 and 3(0,, and for any i,j [M], # j we have:
KLP.IIP,
KLIN(1 + 3100 1)11((1111 + 8L08 1)]
(8
3(008882
2
(19)
82
11366) - -860112
2
82
11 -86)111-
Again, the KT-divergence is conditioning on g(() and 300 Here the first line is from the fact that We's 's are independent for every t, the second line is by 2t = 1, the third line is from the fact that OT)N( 02)] log da 01 + +f+ 203 2. the fourth line is by calculation and the fifth line is
from that 10.00 ا 1).
Here we introduce a Fano's Inequality as the following proposition:
Proposition B.2 (Fano's Inequality). Let X1, X2...., Xn midd P where E (IP1, Pa...,, PNN is a distribution family. Let v be any function of X2....... Xn taking values in f1. NN. Let a max (P).P Then
log log N
M
UUsully denoted as B, but here we denote it as a clarity, since we have already defined (8() as vectors
20

---

Published in Transactions on Machine Learning Research (10/2023)
According to Fano's Inequality, we have:
inf V:RT (12 NY ie (1.2......
sup P.( +1) 2 inf N
P. + 2
+ log 2
1 2
no
(20)
log
log N
Here n = 1 since only one specific vii covers the whole time series and is only sampled once, and a [aM [[]y()))+x( = jex,,j 5. || - 31 S 8T is the upper bound of KL- divergences different distributions. Now we specify the function V for any pricing algorithm A: At each round t 1,2,..., suppose the algorithm A proposes a price eze. Define a vector w [w1, W2,.... wrr T
3
where wy [ug J(0 is a Boolean value. Then we let V = argming E [N]][w 361 Therefore,
2
we have:
2. | 10 2113(1a) - wwl1 + l|w - 1
21(8(0a) -33 Vj [N].j # A T
26
Here the first inequality is from the optimality of AA the second inequality is from the triangular inequality, and the third incquality is from the Hocffding bound in Eq. (18). Therefore we know that if v o then we have ||w- 3(0 12:
T which further leads to
r
1u (1))
1=1
[1[w, 1) 0] + 1ww, 0]1181" 1))(1( - (i))
J(6o) ((0,)
j(h)) + J(0))
Σ 1[1A1 2
u( = 01(051 - x(06)) + 1
1[3(0 = 1](](0, - 0(21)²
2
2
[(0r) -J(00) )2
Σ
1[ll 1,00 = 1](
2
2
1=1
= ||w 11( J(Bz)= - -((b)) )2
2
T
J(0b) - -((1))
2
12
2
Here the first line is because we omit the case where 1 [[,, = 3(0), the second line is from the definition of wh the third line from the facts of 6 < 01 and J'(u) > Vu E I. the fourth line is by the definition of Li-norm and the last line is from the fact we mentioned prior to this equation. Now we propose lemma of properties:
Lemma B.3 (Properties of g(v, u) and Ju)).. For g(v, u) and (() with N, NN 1), we have:
1. Ju) when u E (0, T and (u) < a when u E (v 41 +00).
2. Bey > 0 s.t. J'u c, Yu [-B. B).
3. 3cg 0 s.t. g(J(u), g(v, w) c,(J(u) v)2, [0, [0,B+J(B))
21

---

Published in Transactions on Machine Learning Research (10/2023)
We will show the proof of Lemma B.3 by the end of this section. With Lemma B.3, when VA + have:
T
Reg
Σ
r
2 [=1
(xt - (2)(f(
T
J(00) - -((0))
(21)
26g 12
2
T
2
20g 12 4
(0) 0))
cge} T8
48
Finally, let 8 1 ( and according to Eq. (19),(20) and (21), we have:
E Rega
sup (V + f) Σ (()
-0(00- x,07(1)))))
iE[N]
Cg
T82
sup AV * 1) M
48
1
T88
2( 2
log N
48
1
TT
TT82
=(
C
2
48
8006
800
83
-T82
-c
3
CT
48
c
1
1
T
(Gp)
}
48
2
240
144
C
C²r+
307200
This holds the theorem.
Also, since our upper regret bound w...t. T and Cr is Ō(1) when Cr < VT. which is trivial up to log T and d factors, we may conclude that our upper regret bound of Ö(T's c v 1) is optimal with respect to and Cr.
Proof of Lemma B.3. We here prove each of them.
1. According to Xu Wang (2021, Lemma 14), we know that u J(u) is monotonically increasing
since J'( E 1). Also, since agiv.u)
dv (==](u) = 1 - F(J(u) u) j(u) -f((()( u) = 0, we have J(V3) - Therefore, J(u) > 0 when
1/4 and [u) < when 0 < < V
2. From Xu Wang (2021, Appendix B.2.1.), we know that J'(u) = 1+ কলo (0, 1), Vu E R where ((w)= = L-F(W) is invertible and smooth for standard Gaussian distribution. Therefore, we know that. J'(() is continuous. Therefore, Fey such that inf J'(u) cJ.
((m)
22

---

Published in Transactions on Machine Learning Research (10/2023)
3. From the optimality of Ju) we know that da(u.a) (o- = 1 F([(u) -u) - J()) f(J(u) u) = 0.
Define q(u) = 1 - [(](u) - u) J(u) [(J(u) u). Since g(u) = 0, Vu E R, we have:
dq(u)
du =0
(J(()([((u) H()) 2) - (J(u)² J(u) 1)) f(J(w) w) =
(2) = =1+ Ju) u. (u) -
The second line is by standard Gaussian noises and some calculations, and the third line is from the fact that f(x) > for standard Gaussian distribution. Since we already know that J'(u) E (0, 1), we may then realized that J(u)2 J(u) - -2 1. Notice that gglu.)) standard gaussian noisc. Therefore, have 8" (J(w)3-u-J(x))
- 2) - u) for u- (( - - (-1) fmin <0
Au2 = (02
where smin has been defined in Appendix B.1 the universal lower bound of ʃ. This means that g(e, u) is fuan-strongh concave at u = J(,,, which further leads to the fact that there exists a neighborhood v E [J(u) B,, [u) + B.] with constant B,, such that 0² ((g(n) for ee [J(u) Bu: (uu) + Bu] we have
Lmo As a result, 2
Ou
g(J(u), - g(v,u) Ög(u, (==]()(((()) - u)
1
Pg(u, u)
(c= or [e.]aa] (J(u) o)²
dr
2
1 Smin (J(u)) - =)
2
2
fmin (J(u) - -))
Now, let us consider the case when v E (0, B + J(B) but v u [J(n) J(u) + Bu]- On the one hand, (J(u) S (B+ (- (2B) On the other hand, g(J(u), u) g(v, u) z g(J(u), u) - max(g(((u)) Ba, (J)x)) B(w, > 0. Denote Ca == inf ( (ax(g(J(u)) - B), B(u), and we have c. O. Therefore, we have:
g(J(u),u) g(v, u) cu
Cu
2B J(B))² 2 (2B J(B)J2 (J(u) v)²
(2B JB)
Finally, let cg = min finm
(28+J[B]] } and we have proved the lemma.
Gy
3 BB can be defined the inferior of By over all u [B,, B]] and still positive constant.
23


Reviews:
[{"review_id": "aopZQKvEQK", "reviewer": "Reviewer_Br6s", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I think the result is interesting and novel, and the paper is also well written making clear the technical intuition and novelties over previous works. So I am generally in support of acceptance. \n\nMy specific questions are as follows:\n1. I am curious if $C_T$ is an appropriate notion of non-stationarity in this setting. It seems like only changes in the valuations $x_t^T\\theta_t^*$ w.r.t. the fixed sequence $\\{x_t\\}_t$ should affect the regret. Is the dependence on $C_T$ a consequence of reducing the problem to estimating $\\theta_t^*$ or because the context sequence is assumed to be adversarial? Can regret bounds be given in terms of changes in the valuations?\n2. I am also confused about Remark 3.9. The dependence of the regret bounds on the noise parameters is not shown and so it is not clear how the regret scales with them or whether the dependence is optimal.\n3. I also think it should be made more clear what parameters of the noise distribution are required by the algorithm and whether these assumptions are plausible, as such matters are now hidden away in the lemmas.\n4. The regret bounds in the noise agnostic setting do not seem to be tight and even vacuous for certain regimes of $T$ and $C_T$. I am hoping the authors could comment more on what is possible in this setting.\n5. In terms of writing, I think Section 3.4 would benefit from a clear explanation of how the contextual dynamic pricing problem is reduced to contextual bandits, as the current writing is missing this.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies a contextual dynamic pricing problem where the environment can change over time. They establish optimal dynamic regret rates scaling with a total variation quantity, with the main proof strategy being a reduction to online convex optimization. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Please see above.\n\nMinor typos:\n* There should be a $J(x^T\\theta_t)$ on the LHS of the display immediately before section 3.\n* Display (12) is missing an absolute value sign.\n* The last term in parentheses of both RHS's of display (17) should be squared.\n* In the bottom of page 16, \"rxp-concavity\" is misspelled.\n* The inequality next to $\\|\\beta^{(i)}-\\beta^{(j)}\\|_1$ at the bottom of page 17 should not be there.", "broader_impact_concerns": "The work is entirely theoretical so I don't foresee any broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "sgPOUU0fyN", "reviewer": "Reviewer_MWcH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is clearly written and the problem is interesting and well motivated.\nThe technical technical approach seems reasonable and is well explained. It provides a nice extension of the result of Cutkosky & Orabona to exp-concave linear supervised learning problems.\n\nI do not believe the algorithm can be considered \"proper\" as it is normally understood in online optimization. The choice for $\\theta_t$ depends on the revealed feature $x_t$ through use of the $x_t$-dependent projection to the constraint set, while the comparator does not. So, I think this is in fact a standard example of an improper algorithm for linear learning tasks (e.g. see https://arxiv.org/abs/1803.09349 for an example of this type of improperness).\nThis is not serious concern - the requirement to have $\\theta_t$ inside a specific constraint set is still an unsolved problem even with an improper choice for $\\theta_t$, but a different phrase should be used.\n\nSome minor/typo level issues:\n\nThe set is \"closed\", not \"close\" - this typo/small mistake appears several times.\n\nPlease state that $f = F’$ in your definitions. I do not think $f$ is actually defined anywhere.\n\n**EDIT**: the original review posting contained a few concerns that I realized were not actually issues.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper discusses an application of online learning to price selection. It describes a setting in which buyer valuations are random variables with means $\\langle x_t, \\theta^\\star\\rangle$ for $x_t$ a context vector describing the product to be bought and $\\theta^\\star$ some preference parameter. The seller sees $x_t$, sets a price $v$ and gains reward $v$ if the $v$ is lower than the buyers valuation of the item. Assuming that the price is a greedy choice given some estimate $\\theta_t$ for $\\theta^\\star$, then under appropriate conditions on the noise of the buyer valuation, it is possible to define a loss function $\\ell_t(\\theta)$ of in terms of whether a purchase was made whose expectation is equal to the expected reward of the greedy strategy using this $\\theta_t$. Moreover, this loss is exp-concave. Thus, we could an exp-concave online algorithm like ONS to obtain logarithmic regret. It is my understanding that this much is the background setup, mostly from Xu & Wang 2021.\n\nNow, the authors wish to obtain low dynamic regret by leveraging recent advance in exp-concave dynamic regret by Baby & Wang 2021 to obtain low dynamic regret when the preference vector $\\theta^\\star$ is slowly varying with path length $C_T$ without knowing $C_T$ in advance. Further, to enforce some kind of realism or safety on the described prices, the estimates $\\theta_t$ must lie in some specified convex set. Baby & Wang's algorithm only works when the set is a $L_\\infty$ ball. To expend beyond the ball, the authors introduce a reduction from optimization over any domain contained in the $L_\\infty$ ball to optimization over the $L_\\infty$ ball that takes inspiration from the reduction of Cutkosky & Orabona 2018. The original reduction does not allow for logarithmic regret on exp-concave losses because it generates a non-exp-concave surrogate loss. The authors proposal leverages the fact that the algorithm gets to see the feature $x_t$ before making a decision, and that the final gradient will be proportional to $x_t$. This enables construction of a more refined surrogate that preserves exp-concavity. As a result, the authors are able to relatively quickly port over the results for exp-concave losses to achieve a dynamic regret of $\\tilde O(d^3 T^{1/3} C_T^{2/3})$.\n\nAn extension is provided that does not require as much information about the noise distribution on the buyer valuations.\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "The nomenclature issue with \"properness\" may not be critical since the technical content makes sense on its own, but it is very confusing and so I strongly recommend that it be fixed.", "broader_impact_concerns": "I have no ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "HNCCSLmG24", "reviewer": "Reviewer_1vaT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\nAs mentioned in the last question (Summary Of Contributions), this paper studies an interesting and novel problem that is of practical appeal and requires certain theoretical innovations. The paper writing is generally good -- the logic flow is very easy to follow, and the contributions and difficulties are stated very clearly. I roughly check the proof and didn't find any flaw, and I believe the results should be correct after a high-level check of the proofs.\n\nThe explanation of using \\ell_1-norm at the beginning of page 2 is highly appreciated.\n\n## Weakness\nMy first concern is about the results in Section 3.4, which looks like a \"bandit\" variant of the other part (the standard one looks like a \"full-information\" setting). Most of the contents are placed in Appendix C, and actually, I am quite confused about the algorithm presented in this part due to the lack of introduction of ADA-ILTCB+ (Chen et al., 2019). For example, the authors should at least introduce what the algorithm is, what the inputs should be, and what the output and guarantee the algorithm will produce. Current presentations only confuse the reader and make the theoretical claims hard to convince the reader.\n\nAnother question in this Section 3.4: there is one black-box approach for non-stationary stochastic bandits learning/RL (https://arxiv.org/abs/2102.05406), which should be (conceptually) easier and more general than (Chen et al., 2019). The authors may have a check and see whether this black-box approach can resolve the problem more directly.\n\nThe contents in Section 3.1 are very interesting, particularly about the transformation in the domain set. Interestingly, I recently saw a paper for non-stochastic control (https://arxiv.org/abs/2206.09257) also employing a similar spirit to ensure the feasibility of the output decision and also keeping the exp-concavity. As the arXiv paper is posted very recently, so the paper and this submission should be deemed as concurrent work, but a discussion is believed necessary now. \n\nIn Theorem 3.1, the authors are encouraged to highlight the dependence on the exp-concavity coefficient $\\alpha$, which is also a standard convention in OCO literature -- recall that the static regret is O(d/\\alpha \\cdot \\log T).\n\nOther concerns include some statements of the prior works, latex usages:\n1) P3. Section 1.2 “Dynamic Pricing” should follow with a “dot”; this non-stationary dynamic pricing problem (especially the agnostic setting) is quite related to the area of non-stationary bandits, particularly, non-stationary linear bandits and generalized linear bandits (https://arxiv.org/abs/1903.01461; https://arxiv.org/abs/2103.05324). See discussions in (Luo et al., 2021; page 5, Bandit algorithms). \n\n2) P4. On dynamic regret paragraph. One paper between (Zhang et al., 2018) and (Baby & Wang, 2021) should be mentioned --- when the loss functions are convex and gradient Lipschitz, problem-dependent universal dynamic regret can be achieved (https://dl.acm.org/doi/abs/10.5555/3495724.3496773; same regret but with improved gradient query complexity is achieved in https://arxiv.org/abs/2112.14368). It might be also helpful to the readers if the authors are willing to discuss recent efforts for other OCO settings and online control problems (https://arxiv.org/abs/2102.03758; https://arxiv.org/abs/2206.09257) and the bandit setting (https://arxiv.org/abs/1907.12340).\n3) The appendix requires some careful proofreading, as there are many typos and inconsistency between appendix and main text. E.g.,\n- Line 2 in Page 15, “Equation (9)” --> “Eq. (9)”\n- the whole proof in Appendix B.3, the latex usage of the inner product is completely wrong. Please do not use “<” and “>”, the correct usage should be “\\langle” and “\\rangle”, see guideline https://www.atqed.com/latex-inner-product\n- etc\n4) The usage of reference (citep vs citet) is not used appropriately, see the guideline in JMLR (https://www.jmlr.org/format/format.html#reference-section). A basic rule is like “In general, you shouldn't have parenthetical statements embedded in parenthetical statements. Therefore, citations within parenthetical statements should not be embedded in parentheses.” So, many places used in this paper (I guess you use \\citet or \\cite) should be replaced by \\citep\n\nAsides from above comments, some minor typos include\n\n5) P2. In “Proper Learning” paragraph, Line 5, a space is omitted before “In this work”.\n\n6) P4, Table 1, is it possible to add two rows for lower bounds of static/dynamic regret, respectively? Or simply the one for dynamic regret.\n\n7) P5. Eq. (3), better use non-italicized font for “Reg”, for example, “$\\text{Reg}$”; also elsewhere\n\n8) P8, Line 2, “the following Lemma” --> “the following lemma”\n\nTo summarize, I believe the paper studies an interesting problem and contributes nice insight to the community. The overall paper writing is of high quality (though some proofreadings are required), so I recommend the acceptance.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies an interesting problem called non-stationary contextual pricing, a natural variant of the standard pricing problem that allows the best pricing strategy to change over time. The setting is of course interesting and important, as it can capture a broader range of pricing applications, particularly those requiring modeling the non-stationarity of the users' interests. This paper studies the problem from the lens of **universal dynamic regret**, an important concept in the online learning literature. To be specific, the authors first formulate this pricing problem (under certain acceptable assumptions) as an online learning problem with exp-concave loss. Although prior work has been studied in this regard, their algorithms are not **proper** in the sense that the decision may lie out of the range of the feasible set, which is not favored in this paper -- which is called the \"safety constraint\". To address so, they have to design a new algorithm with a provable guarantee that the decisions must lie in the feasible set, and also the algorithm can enjoy nice universal dynamic regret. The major technical ingredient is an interesting \"transfer theorem\" with the cooperation of the reduction scheme [Cutkosky & Orabona, 2018]. The important caveat in the trick is that the surrogate loss should be able to keep the exp-concavity such that the reduced problem can be handled by earlier studies developed for the exp-concave online learning with $L_{\\infty}$ ball decision set. \n\nTo summarize, I believe the paper studies an interesting problem and contributes nice insight and technique to the community. The overall paper writing is of high quality (though some proofreadings are required), so I recommend the acceptance.\n\n\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Please check my comments in the last question (Strengths And Weaknesses).", "broader_impact_concerns": "The paper mainly contributes to the theoretical aspect, so I cannot find foreseeable ethical issues.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers were positive about the paper and recommended acceptance, and I also share their opinion. While their corrections and suggestions have mostly been incorporated in the manuscript, I have found a number minor issues which should be addressed/corrected in the final version.

- Abstract: Please define notation ($T$, $C_T$, $d$) used in the abstract. It would be great to mention that you consider a linear pricing model for the users, and for online learning with exp-concave losses, the attention is restricted to loss functions coming from a generalized linear model. Consider mentioning explicitly that the bound may not be optimal in $d$ and also the $\log T$ dependence (hence the dependence on $T$ is only "almost" optimal). The assumption in the paper on the noise is more restrictive than log-concave (as you require that $1-F$ is also log-concave). (Also, dynamic regret is measured relative to "the" optimal sequence of policies, not to an arbitrary one.)

- Section 3.4: Please significantly improve the presentation of this section. Make the statements of Theorem 3.10, Theorem 3.11, and Lemma 3.12 precise: For Theorem 3.10, follow what is given in the appendix: for every algorithm there exists a problem such that... For Theorem 3.11 and the lemma, describe more precisely (quantify) what you mean by high probability. Mention discretization early on in the section, otherwise it is not clear how the reduction to bandits (with finitely many actions) can be done. Add a brief description of ADA-ILTCB+. What is ADA-ILTCB*? It would be good to have a short discussion about how the bandit reduction does not fully utilize the observations (estimating the reward for other prices) and how it leads to deteriorated rates compared to the previous results. The wording is awkward at several places, including "$N_t$'s are absolutely bounded by constants", "each policy takes into an $x_t$", "integer multiplying $\Delta$/$\gamma$", "constantly bounded", "the distribution $D$ are fully agnostic", "probabilistic distribution" (should actually be density function), "distributional switching", etc.

Minor comments/typos:

- p. 1, last line: i.e -> i.e.
- p. 2, around equation (1): define $w_{1:T}=(w_1,\ldots,w_T)$
- Please make sure citations are properly integrated into sentences, e.g., on p. 2, 2  lines below equation 1, it should be (Zinkevich, 2003), or on p. 4, in the "Dynamic Regret" paragraph, "by Zhao et al. (2020b)" seems better, or on p. 4, there are too many parentheses in (e.g. (Zhao et al. 2022...)). This has already been mentioned by Reviewer 1vaT.
- p. 4, last line of the "Dynamic Regret" paragraph: "arbitrary decision sets" should be "arbitrary bounded convex decision sets"
- in the next paragraph "algorithms falls".
- p. 4, paragraph above Section 2: It is not entirely clear what you mean by having a gradient direction before making the prediction.
- p. 4, l. -2: $\theta^*$ is not defined in the text.
- p. 5, Section 2.2: it would be good to mention here again that the sets ($\mathcal{D}_x$, etc.) are convex.
- p. 5: Please discuss the assumptions that $F$ and $1-F$ are log-concave (in particular, it would be great if you could present some examples, like the sigmoid function).
- p. 5, paragraph about restrictions: It is not clear to me what you mean here by "without loss of generality". You introduced a restriction that "When we take an action by presenting a price $v_t$,
there always exists an $\theta_t$ such that $x^\top \theta_t = J^{-1}(v_t)$." and the next statement follows from this, but why can you do this without loss of generality?
- p. 6, Consistency: "we requires".
- p. 7: "losses $\ell_t$ exhibits".
- p. 7: Theorem 3.1/Remark 3.2: Please discuss the corresponding lower bound (especially since the remark talks about "optimal" adaptivity to $C_T$, hence an argument substantiating optimality would be welcome).
- p. 8: Above Lemma 3.3: $\hat{l}_t$ should be $\hat{\ell}_t$.
- p. 9, Theorem 3.6: $C_{down}$ and $C_{exp}$ are only defined in the subsequent lemmas. Please make sure they are defined before use. Compared to Theorem 3.1, a factor of 2 seems to be missing in the definition of $\beta$ (corresponding to the $\alpha/2$ term.
- p. 10, after Lemma 3.8: should be "Lemma 7 of Xu & Wang (2021)". Last line of the proof: "Theorem"->theorem.
- p. 10, Remark 3.9: You could add here your response to Reviewer Br6s that Xu and Wang "show an exponential increase on the regret as $\sigma$ gets close to zero."
- p. 10, Sec 3.3: "have construct".
- p. 11, line 4: delete "While".

Decision: Accept (poster)