# Dynamic Pricing and Learning with Long-term Reference Effects

Shipra Agrawal Columbia University<EMAIL_ADDRESS>Wei Tang Columbia
University<EMAIL_ADDRESS>
###### Abstract

We consider a dynamic pricing problem where customer response to the current
price is impacted by the customer price expectation, aka reference price. We
study a simple and novel reference price mechanism where reference price is
the average of the past prices offered by the seller. As opposed to the more
commonly studied exponential smoothing mechanism, in our reference price
mechanism the prices offered by seller have a longer term effect on the future
customer expectations.

We show that under this mechanism, a markdown policy is near-optimal
irrespective of the parameters of the model. This matches the common intuition
that a seller may be better off by starting with a higher price and then
decreasing it, as the customers feel like they are getting bargains on items
that are ordinarily more expensive. For linear demand models, we also provide
a detailed characterization of the near-optimal markdown policy along with an
efficient way of computing it.

We then consider a more challenging dynamic pricing and learning problem,
where the demand model parameters are apriori unknown, and the seller needs to
learn them online from the customers’ responses to the offered prices while
simultaneously optimizing revenue. The objective is to minimize regret, i.e.,
the $T$-round revenue loss compared to a clairvoyant optimal policy. This task
essentially amounts to learning a non-stationary optimal policy in a time-
variant Markov Decision Process (MDP). For linear demand models, we provide an
efficient learning algorithm with an optimal $\widetilde{O}(\sqrt{T})$ regret
upper bound.

##  1 Introduction

In modern marketplaces, the demand for a product is influenced not only by the
current selling price but also by customers’ price expectation, aka reference
price. Intuitively, the reference price is what customers perceive as the
“normal" price for a product based on the historic market prices. When the
current price is lower than the reference price, customers are likely to
perceive a bargain or “gain", which could lead to an increased purchase. And
when the selling price is significantly higher than the reference price,
customers are likely to perceive a rip-off or “loss", potentially leading to a
negative effect on demand. The reference effects are often asymmetric, owing
to customers’ different attitudes towards a perceived loss v.s. a perceived
gain (Lattin and Bucklin, 1989, Rajendran and Tellis, 1994).

In the existing literature, a common way to model the reference price
mechanism in markets with repeated-purchases is to consider reference prices
formed endogenously based on the past prices of a product (see, e.g., Fibich
et al., 2003, Popescu and Wu, 2007, Nasiry and Popescu, 2011, Chen et al.,
2017, den Boer and Keskin, 2022). The motivation for this endogenous mechanism
stems from the observation that the returning customers in these markets may
remember the historical prices of the product.

A commonly used model for endogenously formed reference prices is the
exponential smoothing mechanism (henceforth $\mathsf{ESM}$). In
$\mathsf{ESM}$, customers’ reference prices are formed as a weighted average
that puts exponentially decreasing weights over time on past prices (Mazumdar
et al., 2005) in order to reflect the psychological intuition that customers
have a fast-diminishing memory over the past prices. In doing so,
$\mathsf{ESM}$ essentially captures a _short-term reference effect_ dominated
by the recent prices. The short-term nature of reference price effects in the
$\mathsf{ESM}$ is also evident from the observation made by the previous works
that in this setting, a fixed-price policy is near-optimal. More precisely,
the revenue on repeatedly offering the optimal fixed-price is within a
constant (independent of the sales horizon) of the optimal revenue assuming
loss-averse customers111Formal definitions of “loss-averse” vs “gain-seeking”
customers are provided in Section 2. and linear base demand model (Fibich et
al., 2003, Popescu and Wu, 2007, den Boer and Keskin, 2022). Intuitively, the
result follows from the insight that due to exponential weighting in
$\mathsf{ESM}$, only a constant number of past prices significantly influence
the current reference price and thereby the customer response.

However, the proliferation of online platforms and marketplaces has led to a
paradigm shift in customer expectation and response behavior. The reference
effects are becoming more pronounced and longer term, since the information
about historic prices is widely and easily available. It is common for
platforms like Google Hotel to put labels “Great Deal, 28% less than usual” or
“Deal, 16% less than usual” to signal how good the current hotel price is
compared to the average price of this hotel over the past year.222See Google
hotel deals policy.  Certain products in Amazon have a “Was Price” displayed,
which is determined using recent price history of the product on Amazon. A
number of third party websites, like CamelCamelCamel, PriSync, Wiser
Solutions, Price2Spy, are dedicated to price tracking and monitoring, and are
increasingly popular among customers for comparing product prices to historic
prices before making a purchase. Thus the customers no longer need to rely on
their individual memory in order to look back at historic prices over a week
or a month or even year(s). The need for studying new reference price
mechanisms with longer memory is therefore apparent, which was interestingly
also mentioned as an important avenue for future research in a recent work on
$\mathsf{ESM}$ (den Boer and Keskin, 2022).

Motivated by these observations, in this work, we consider a novel and simple
reference price mechanism aimed at capturing longer-term reference effects. In
our mechanism that we refer to as averaging reference mechanism (henceforce
$\mathsf{ARM}$), the reference price is formed as a simple average (i.e., with
equal weights) of the past prices. See formal definition in Definition 2.1.

We demonstrate that this simple modification to the reference price mechanism
significantly changes the nature of the dynamic pricing problem. Specifically,
as opposed to $\mathsf{ESM}$, the revenue of any fixed-price policy under
$\mathsf{ARM}$ can be highly suboptimal compared to the optimal revenue: the
difference can be as large as linear in sales horizon (see Proposition 1).
Furthermore, we show that a markdown policy is always near-optimal under
$\mathsf{ARM}$. This matches the practical intuition that under significant
and long-term reference effects, a seller may be able to set customer
expectations better by starting with a higher price and then decreasing it in
order to give a perception of a bargain to the customer (or, avoid the
perception of a rip-off). This result also provides a technical justification
of the widespread use of markdown pricing in industry (see, e.g., IBM, 2023,
Google, 2023) and in academic literature (Lazear, 1986, Wu et al., 2015, Jia
et al., 2021, Birge et al., 2023).

Next, we summarize our contributions. Besides modeling contributions, our
results include a detailed characterization of the optimal dynamic pricing
policy under the $\mathsf{ARM}$ model, and algorithm design and analysis for
learning and regret minimization when the demand model parameters are unknown.

###  1.1 Our Contributions and Results

A main modeling contribution of our work is to introduce and pioneer the study
of the average reference model (i.e., $\mathsf{ARM}$) in dynamic pricing and
learning literature which has thus far been dominated by the exponentially
weighted average (i.e., $\mathsf{ESM}$) model for reference effects. We
contend that $\mathsf{ARM}$ is able to capture longer-term reference effects
on customer behavior and matches the practice much more closely in its
implications on the seller’s optimal pricing strategies. We provide several
rigorous technical results to support this claim. Further, for $\mathsf{ARM}$
with linear demand models, we provide algorithmic and computational insights
towards efficiently implementable near-optimal dynamic pricing strategies, in
both full information and learning settings.

Our main technical contributions are summarized as follows.

Suboptimality of fixed-price and (near-)optimality of markdown pricing. In our
first result that sets the $\mathsf{ARM}$ model distinctively apart from
$\mathsf{ESM}$, we demonstrate that under $\mathsf{ARM}$, the revenue of any
fixed-price policy can be highly sub-optimal compared to that of the optimal
pricing policy. Specifically, in Proposition 1, we show that the difference
between these two revenues can grow linearly in sales horizon $T$.

Next, in Theorem 1, we establish the (near-)optimality of markdown pricing in
$\mathsf{ARM}$ models. Here, markdown pricing policy is defined as any policy
under which the sequence of prices offered are always decreasing (or non-
increasing) over time. In Theorem 1a, we show that under $\mathsf{ARM}$ with
gain-seeking customers, markdown pricing is optimal. And further, in Theorem
1b, we show that for loss-averse customers, markdown pricing is near-optimal:
specifically, there always exists a markdown policy that achieves a revenue
within $O(\log(T))$ of the optimal revenue in $T$ rounds.

Our results complement the existing literature supporting markdown strategies
in dynamic pricing problems (Lazear, 1986, Wu et al., 2015, Jia et al., 2021,
Birge et al., 2023, Jia et al., 2022), and provide a technical justification
for the widespread practice of such strategies (Google, 2023, IBM, 2023).

Characterization and implementation of near-optimal pricing for linear demand
models. Having established the near-optimality of the markdown pricing policy,
we then explore how to characterize and compute such a desired markdown
pricing policy. Notice that reference price effects make the dynamic pricing
problem substantially more involved. In particular, as we elaborate later,
with $\mathsf{ARM}$, under any pricing policy, demand evolves as a non-
stationary stochastic process. Finding an optimal pricing policy then amounts
to solving a time-variant Markov decision process (MDP) with continuous
action/state space. Moreover, the reward function (i.e., the seller’s revenue
function) is nonsmooth under asymmetric reference price effects. For a more
tractable setting, we follow the existing literature (Fibich et al., 2003, den
Boer and Keskin, 2022, Ji et al., 2023) and consider a linear base demand
model. Note that in this model, while the demand is linear in the offered
price, there still may be some non-linearity in demand stemming from the
asymmetry in reference price effects. For details, see Section 2.

Under the linear base demand model, firstly, in Proposition 2, we provide a
detailed structural characterizations for a (nearly) optimal markdown pricing
policy for both gain-seeking and loss-averse customers. Next, in Proposition
3, we utilize this markdown structure to provide an efficient algorithm for
computing such policies.

Learning and regret minimization under linear demand models. We also study the
dynamic pricing problem with reference effects in the presence of demand model
uncertainty. This problem is motivated by the practical consideration that the
demand model parameters may not be fully known to the seller a priori.
Instead, the seller may have to learn these (implicitly or explicitly) from
the observed customer response through sales data, in order to compute/improve
the pricing policy.

Following the previous literature, again we consider a linear base demand
model. We assume that seller has no apriori knowledge of the base demand model
parameters or the parameters of the $\mathsf{ARM}$ model. In line with the
online learning and multi-armed bandits literature, we focus on evaluating the
algorithm performance via the cumulative regret, defined as the total expected
revenue loss compared to a clairvoyant policy.

Our main contribution in this setting is a learning algorithm that achieves a
regret upper bound of $\widetilde{O}(\bar{p}^{3.5}\sqrt{T})$ (see Theorem 2).
A main insight that we derive and utilize for this algorithm is that although
under $\mathsf{ARM}$ the near-optimal markdown policies are highly non-
stationary, they can be parameterized by a two-dimensional parameter vector
which also fully characterizes the local greedy price (namely the price that
maximizes a single round revenue) under a certain range of reference prices.
This insight allows us to offer estimated greedy prices in the learning phase
and use the demand response from those prices to learn the desired markdown
policy.

Finally, in Proposition 4, we derive a regret lower bound that closely matches
our upper bound. In particular, building upon the proof of the existing lower
bounds for dynamic pricing problem, we show that even when there are no
reference effects, there exists a set of instances satisfying our assumptions
such that any learning algorithm must incur a worst-case (over this set)
expected regret of at least $\Omega(\bar{p}\sqrt{T})$.

###  1.2 Related Work

On the research related to dynamic pricing, our work mainly connects to two
streams of works: (i) dynamic pricing with reference effects, (ii) dynamic
pricing and learning (with reference effects). As we elaborate later, the
seller’s learning problem is essentially that of learning in a time-variant
MDP. Thus, our work also relates to works on reinforcement learning for non-
stationary MDP.

Dynamic pricing with reference effect. Dynamic pricing with reference effects
has been extensively studied in both revenue management and marketing
literature over the past decades (see Mazumdar et al., 2005 and Arslan and
Kachani, 2010 for a review). Below we mention mostly related works. As
previously mentioned, $\mathsf{ESM}$ is one commonly-used model for reference
price in the current literature. Under this mechanism, Popescu and Wu, (2007)
show that optimal pricing policy will eventually converge to a constant price
when customers are loss averse, similar message is also delivered in den Boer
and Keskin, (2022). In addition, Chen et al., (2017) develop strongly
polynomial time algorithms to compute the optimal prices under certain
conditions. Other works that focus on $\mathsf{ESM}$ include Fibich et al.,
(2003), Wu et al., (2015), Hu et al., (2016), Cao et al., (2019), Golrezaei et
al., (2020), just to name a few. As mentioned, two key features of
$\mathsf{ESM}$ is that it is a stationary process and customers have
diminishing memories over the past prices. These two features also appear in
other reference price mechanism like peak-end anchoring (Nasiry and Popescu,
2011). Our work differs with these works significantly as the considered
$\mathsf{ARM}$ is a different reference price model that aims to capture the
long-term reference effects.

Dynamic pricing and learning (with reference effect). The learning part of our
work also relates to the expanding literature on learning and earning in
dynamic pricing problems, see, e.g., Kleinberg and Leighton, (2003), Besbes
and Zeevi, (2009), Araman and Caldentey, (2009), Broder and Rusmevichientong,
(2012), Keskin and Zeevi, (2014), Besbes and Zeevi, (2015), Agrawal et al.,
(2023), just to name a few. We refer the interested readers to the survey by
Den Boer, 2015a . These works are focusing on learning without reference
effects. The mostly related works are den Boer and Keskin, (2022), Ji et al.,
(2023), similar to our work, they also consider learning with reference
effects. In particular, den Boer and Keskin, (2022) study dynamic pricing with
learning with linear demand model under $\mathsf{ESM}$, and Ji et al., (2023)
focus on multi-product selling setting where the reference effects are formed
by the comparison between the prices of all products. Notice that in these two
works, a fixed-price policy is already near-optimal. Thus, the high-level idea
behind the algorithms in both works is an epoch-based learning-and-earning
algorithm that integrates least squares estimation to estimate the underlying
demand parameters and compute a good estimate of the optimal fixed price. Our
work differs from these two works significantly as in our problem, the seller
needs to learn an optimal non-stationary policy, making their algorithms not
applicable to our setting.

Learning in non-stationary MDP. The underlying demand function with our
reference price mechanism essentially evolves according to a time-variant MDP.
There are also works studying dynamic pricing and learning in a non-stationary
environment, e.g., Besbes and Zeevi, (2011), Den Boer, 2015b , Chen et al.,
(2019), Keskin and Zeevi, (2017), Agrawal et al., (2021). However, these works
are either consider a very broad non-stationarity or focusing a particular
structured model which is fundamentally different from ours. There is also
much recent work on learning and regret minimization in stateful models using
general MDP and reinforcement learning frameworks (e.g., Auer et al., 2008,
Agrawal and Jia, 2017, Cheung et al., 2020, Fei et al., 2020). However, these
results typically rely on an assumption that each state can be visited many
times over the learning process. This is ensured either because of an episodic
MDP setting (e.g., Fei et al., 2020), or through an assumption of
communicating or weakly communicating MDP with bounded diameter, i.e., a bound
on the number of steps to visit any state from any starting state under the
optimal policy (e.g., Cheung et al., 2020, Agrawal and Jia, 2017). Our setting
is non-episodic, and under $\mathsf{ARM}$, the state (i.e., the reference
price) can take steps that linear in current time to reach other state.
Therefore, the results in the above papers on learning general MDPs are not
applicable to our learning problem.

##  2 Problem Formulation

We consider a dynamic pricing problem with an unlimited supply of durable
products of a single type to be sold in a market across $T$ time periods. At
the beginning of each time round $t\in[T]$, the seller sets a price
$p_{t}\in[\underline{p},\bar{p}]$ for her product, where $\underline{p}$ and
$\bar{p}$ are the pre-determined smallest and largest feasible prices
satisfying $0\leq\underline{p}<\bar{p}<\infty$. Given the price $p_{t}$, the
seller observes the demand $D_{t}$ and collects revenue $p_{t}D_{t}$. The
observed demand $D_{t}$ is influenced by: (i) the current selling price
$p_{t}$, (ii) a reference price $r_{t}$, and (iii) the unobservable demand
shocks in the following manner:

$\displaystyle D_{t}=D(p_{t},r_{t})+\varepsilon_{t}~{}.$

Here, $r_{t}\in[\underline{p},\bar{p}]$ denotes the reference price at the
beginning of round $t$; $\varepsilon_{t}\leq\bar{\varepsilon},t\in[T]$ denote
unobservable demand shocks which are independently and identically distributed
random variables with zero mean, and are all upper bounded by
$\bar{\varepsilon}\geq 0$. And, the demand function $D(\cdot,\cdot)$ is given
by

$\displaystyle
D(p_{t},r_{t})=H(p_{t})+\eta^{+}(r_{t}-p_{t})^{+}-\eta^{-}(p_{t}-r_{t})^{+}~{},$
(1)

where $H(p)$ represents the non-decreasing base demand in price with the
absence of reference effects, parameters $\eta^{+}\geq 0$ and $\eta^{-}\geq 0$
control the impact of reference price on demand: if the current selling price
$p$ is less than the reference price $r$ then the expected demand increases by
$\eta^{+}(r-p)$, but if $p$ exceeds $r$ then the expected demand decreases by
$\eta^{-}(p-r)$. The aggregate-level demands are classified as loss averse,
loss/gain neutral, or gain seeking depending on whether $\eta^{+}<\eta^{-}$,
$\eta^{+}=\eta^{-}$, or $\eta^{+}>\eta^{-}$, respectively. For presentation
simplicity, we assume $\underline{p}\equiv 0$. To avoid negative demand, we
assume that $D(p,r)\geq 0$ for all $p,r\in[0,\bar{p}]$.

The reference-price dynamics. In this paper, we consider the following
dynamics of evolution of the reference-price $(r_{t})_{t\in[T]}$.

######  Definition 2.1 ($\mathsf{ARM}$).

A reference-price dynamic is said to be an averaging reference mechanism
($\mathsf{ARM}$) if

$\displaystyle r_{t+1}=\frac{r_{1}+\sum_{s=1}^{t}p_{t}}{t+1},\quad\text{for
}t\in[T-1]~{},$ (2)

where $r_{1}$ is the starting reference price at $t=1$.

Another equivalent way to describe $\mathsf{ARM}$ is though the running
average: given reference price $r_{t}$ and selling price $p_{t}$ at time $t$,
the next reference price $r_{t+1}$ is given by:

$\displaystyle
r_{t+1}=\frac{tr_{t}}{t+1}+\frac{p_{t}}{t+1}=\zeta_{t}r_{t}+(1-\zeta_{t})p_{t},\quad\text{for
}t\in[T-1]~{},$ (3)

where $1-\zeta_{t}=\nicefrac{{1}}{{(t+1)}}$ for all $t\in[T-1]$ can be seen as
the averaging factor that captures how the current price $p_{t}$ affects the
reference price in next round. Intuitively, in this mechanism, once a product
has been around for a long time, the customer price expectations may not be
impacted much by a few rounds of price variations.

######  Remark 1.

We emphasize that our $\mathsf{ARM}$ is a non-stationary mechanism as the
averaging factor $\zeta_{t}$ is time-dependent. This stands contrast to
$\mathsf{ESM}$ where $r_{t+1}=\zeta r_{t}+(1-\zeta)p_{t}$ where the averaging
factor $\zeta$ is assumed to be a constant across the whole time horizon.

Given a price $p\in[0,\bar{p}]$ and a reference price $r\in[0,\bar{p}]$, we
denote the expected single-round revenue by function
$\mathsf{Rev}\\!\left({p,r}\right)$:

$\displaystyle\mathsf{Rev}\\!\left({p,r}\right)=p\cdot\left(H(p)-\eta^{-}(p-r)^{+}+\eta^{+}(r-p)^{+}\right).$

Given a starting reference price $r$ at time $t$, and the sales horizon $T$,
the optimal expected cumulative revenue starting from time $t$ is given by

$\displaystyle V^{*}(r,t)$
$\displaystyle\triangleq\sup_{p_{t},\ldots,p_{T}}\sum_{s=t}^{T}\mathsf{Rev}\\!\left({p_{s},r_{s}}\right),\quad\text{s.t.
}~{}r_{s+1}=\frac{sr_{s}+p_{s}}{s+1},~{}~{}~{}s\in[t,T-1]~{}.$
($\mathcal{P}_{\mathsf{OPT}}$)

We use $V^{\mathbf{p}}(r,t)$ to denote the seller’s revenue on applying a
price sequence $\mathbf{p}=(p_{s})_{s\geq t}$, starting with a reference price
$r$ at time $t$. For notation simplicity, when starting time $t=1$, we use the
notation $V^{*}(r)\equiv V^{*}(r,1),V^{\mathbf{p}}(r)\equiv
V^{\mathbf{p}}(r,1)$. We use $\mathbf{p}^{*}(r,t)\triangleq(p^{*}_{s})_{s\geq
t}$ to denote an optimal pricing policy that maximizes $V^{\mathbf{p}}(r,t)$.

Dynamic pricing and learning under unknown model parameters. We also consider
a partial-information setting where demand function is initially unknown to
the seller and has to be inferred from the observed demand response to offered
prices. In this part, to make the problem more tractable, we focus on linear
base demand models, i.e., $H(p)\triangleq b-ap$. Here $a\in\mathbb{R}$ and
$b\in\mathbb{R}$ are the base demand model parameters which captures the
customers’ price-sensitivity and the market size, respectively.

Then, in the learning setting, we assume that the base demand parameters
$(a,b)$ and the reference effect parameters $(\eta^{+},\eta^{-})$, are all
apriori unknown to the seller. At any time $t$, given reference price $r_{t}$,
on offering a price $p_{t}$, the seller can observe a noisy outcome from
demand response function
$D(p_{t},r_{t})=b-ap_{t}+\eta^{+}(r_{t}-p_{t})^{+}-\eta^{-}(p_{t}-r_{t})^{+}$,
which may be used to infer the demand model and thereby the optimal pricing
policy. To aid this inference, we make the following assumption on the base
demand model $H(p)$; similar assumptions are commonly made in the existing
literature on dynamic pricing with linear demand models (see, e.g., Keskin and
Zeevi, 2014, den Boer and Keskin, 2022, Ji et al., 2023, den Boer and Zwart,
2014).

######  Assumption 2.1.

Assume that the maximizer of the function $pH(p)$ with linear demand model
$H(p)=b-ap$, lies in the interior of the feasible price range $[0,\bar{p}]$.
In particular, assume $\frac{b}{2a}\leq\bar{p}-\Omega(1)$.

We use vector $I=(a,b,\eta^{+},\eta^{-})$ to denote the parameters of a given
problem instance. We assume that all parameters are normalized so that
$I\in[0,1]^{4}$. We use $\mathcal{I}\subseteq[0,1]^{4}$ to denote the
parameter set of all feasible instances satisfying 2.1.

An online dynamic pricing algorithm $\pi_{\mathsf{ALG}}$ maps all the
historical information collected up to this time round into a price in
$[0,\bar{p}]$. Given a starting reference price $r_{1}\in[0,\bar{p}]$, we
measure the performance of a pricing algorithm $\pi_{\mathsf{ALG}}$ via the
$T$-period cumulative regret, or regret, which equals to the total expected
revenue loss incurred by implementing the algorithm $\pi_{\mathsf{ALG}}$
instead of a clairvoyant optimal pricing policy for the problem instance with
parameter $I$, i.e.,

$\displaystyle\text{\bf
REG}^{\pi_{\mathsf{ALG}}}\\!\left[{T,I}\right]\triangleq
V^{*}(r_{1})-\mathbb{E}_{\mathbf{p}\sim\pi_{\mathsf{ALG}}}\\!\left[{V^{\mathbf{p}}(r_{1})}\right]~{},$

where the expectation
$\mathbb{E}_{\mathbf{p}\sim\pi_{\mathsf{ALG}}}\\!\left[{\cdot}\right]$ is over
the sequence of prices induced by the algorithm $\pi_{\mathsf{ALG}}$ when run
starting from reference price $r_{1}$ on a problem instance with parameter
$I$.

##  3 Characterizing (Near-)Optimal Pricing Policy

In this section, we derive our main results on the structure and computation
of optimal and near-optimal dynamic pricing policies under $\mathsf{ARM}$.

First in Section 3.1, we show that a fixed (aka static) price policy, which is
known to be near-optimal under $\mathsf{ESM}$, can indeed be highly suboptimal
in $\mathsf{ARM}$ in the sense that it can suffer with a linear revenue loss
compared to the optimal policy.

Next, in Section 3.2, we demonstrate that a markdown policy is optimal for
$\mathsf{ARM}$ when customers are gain-seeking, and near-optimal (within
$O(\log(T))$ revenue) when customers are loss-averse.

Finally, in Section 3.3, we provide a detailed characterization and
computational insights for this markdown policy for the case when the base
demand model $H(p)$ is linear. This characterization will be later utilized in
Section 4 for learning and regret minimization under demand uncertainty.

###  3.1 The Sub-Optimality of Fixed Price

We refer to $\mathbf{p}$ as a fixed price policy if $\mathbf{p}=(p,\ldots,p)$
for some $p\in[0,\bar{p}]$. We show that under $\mathsf{ARM}$, any fixed-price
policy can have linear (in number of rounds $T$) revenue loss compared to an
optimal pricing policy, even if we restrict to the linear base demand model
and loss-neutral customers.

######  Proposition 1.

There exists an $\mathsf{ARM}$ problem instance with linear base demand model,
i.e., $H(p)=b-ap$ and loss-neutral customers (i.e., $\eta^{+}=\eta^{-}$), and
an initial reference price $r_{1}$ such that for any fixed-price policy
$\mathbf{p}$, we have $V^{*}(r_{1})-V^{\mathbf{p}}(r_{1})=\Omega(T)$.

The above results highlight a fundamental difference between our
$\mathsf{ARM}$ model and the previously well-studied $\mathsf{ESM}$ model for
reference effects. In particular, for the base linear demand, when the
reference-price dynamics follow $\mathsf{ESM}$ and when the customers are
loss-neutral, previous work (den Boer and Keskin, 2022) have shown that the
seller can safely ignore the reference effect (notice that when the reference
effects are ignored, the single-round expected revenue would equal $p(b-ap)$
and thus the optimal fixed-price would be $\nicefrac{{b}}{{2a}}$). They show
that a fixed-price policy with the selling price at $\nicefrac{{b}}{{2a}}$
yields a revenue very close to the revenue under the optimal pricing policy:
the difference between these two revenues is bounded by a constant independent
of the sales horizon $T$. However, the above Proposition 1 shows that the
performance of such fixed-price policy can be arbitrarily bad under
$\mathsf{ARM}$.

######  Remark 2.

We would like to note that a fixed-price policy has the (nearly) same revenue
under both $\mathsf{ESM}$ and our $\mathsf{ARM}$. Together with the results in
Proposition 1, this demonstrates that under $\mathsf{ARM}$, the optimal
revenue can be significantly higher than the optimal revenue under
$\mathsf{ESM}$.

We prove Proposition 1 by showing that when customers are loss-neutral, there
exists a simple two-price policy with $\Omega(T)$-larger revenue compared to
the revenue obtained under any fixed-price policy. The policy starts with the
higher price, and then at some round, switches to the lower price which is
offered for the remaining rounds.

###  3.2 The (Near) Optimality of Markdown Pricing

In this section, we show that for any $\mathsf{ARM}$ problem instance $I$,
there always exists a markdown pricing policy that is near-optimal. We first
define the markdown pricing policy.

######  Definition 3.1 (Markdown pricing policy).

A markdown pricing policy is defined as any pricing policy which, when applied
starting at any $t_{1}\in[T]$ and reference price $r$, generates a price curve
$(p_{t})_{t\geq t_{1}}$ satisfying $p_{t}\geq p_{t+1}$ for all $t\geq t_{1}$.

The main results of this subsection are summarized as follows:

######  Theorem 1 (Near Optimality of Markdown Pricing Policy).

Fix any starting reference price $r_{1}\in[0,\bar{p}]$ at time $t=1$,

  1. 1a

when $\eta^{+}\geq\eta^{-}$, i.e., when customers are gain-seeking, optimal
pricing policy is a markdown policy;

  2. 1b

when $\eta^{+}<\eta^{-}$, i.e., when customers are loss-averse, there exists a
markdown policy $\mathbf{p}$ that is near-optimal, namely,
$V^{*}(r_{1})-V^{\mathbf{p}}(r_{1})=O\left(\bar{p}(\bar{p}-r_{1})(\eta^{-}+\eta^{+})\ln
T\right)$.

From the above results, we can see that the optimality of the markdown pricing
policy depends on the relative values of reference effects $\eta^{+}$ and
$\eta^{-}$. When the customers are gain-seeking (i.e.,
$\eta^{+}\geq\eta^{-}$), the optimal pricing policy is a markdown policy. This
characterization shares certain similarity with previous results on the
optimal pricing policy when the reference-price dynamics follow the
$\mathsf{ESM}$. In particular, Hu et al., (2016) have shown that when the
customers are insensitive to the loss (i.e., $\eta^{+}>0,\eta^{-}=0$) and they
only remember the most recent price (i.e., the averaging factor $\zeta$ in
$\mathsf{ESM}$ equals to $0$), the optimal pricing policy is a cyclic markdown
pricing policy. While in our setting with $\mathsf{ARM}$, no matter how
customers are sensitive to the losses, as long as customers value more on the
gains, the optimal pricing policy is always a markdown policy.

On the other hand, when customers are loss-averse (i.e., $\eta^{+}<\eta^{-}$),
the markdown pricing policy may not be optimal. However, it is guaranteed that
there exists a markdown pricing policy that is near-optimal, namely, its total
revenue is within $O\left(\ln T\right)$ of the optimal revenue.

To prove Theorem 1, we first show the optimality of markdown pricing policy
when the customers are gain-seeking. This is summarized in the following
lemma.

######  Lemma 3.1.

Fix any starting time $t_{1}\in[T]$ and an starting reference price
$r_{t_{1}}=r$, when $\eta^{+}\geq\eta^{-}$, the optimal pricing policy
starting from time $t_{1}$ is a markdown pricing policy.

The main intuition behind the above markdown optimality is that: under
$\mathsf{ARM}$, the high price and low price contribute the same to the
reference prices in later rounds. Since customers are gain-seeking, i.e., the
impact of a perceived gain (how low is price compared to reference price) is
more than the impact of the same amount of perceived loss, it is always better
for the seller to charge the high price before the low price. Indeed, we prove
the above results by showing that whenever under a pricing policy
$\mathbf{p}=(p_{t})_{t\in[t_{1},T]}$ there is an increase in price, i.e.,
$p_{k}<p_{k+1}$ for some time rounds $k$ and $k+1$, then we can obtain a new
pricing policy $\mathbf{p}^{\prime}$ with a higher payoff by simply switching
the prices $p_{k}$ and $p_{k+1}$ at time round $k$ and $k+1$.

To analyze performance of the markdown pricing policy when the customers are
loss-averse, we first show that when the starting reference price is the
highest possible price $\bar{p}$, then even in this case, the optimal policy
is a markdown pricing policy. Intuitively, in this case, the markdown policy
will never offer a price $p_{t}$ that is above the current reference price
$r_{t}$, so there is never a perceived loss.

######  Lemma 3.2.

Fix any starting time $t_{1}\in[T]$ and an starting reference price
$r_{t_{1}}=\bar{p}$, if $\eta^{+}<\eta^{-}$, then the optimal pricing policy
starting from time $t_{1}$ is a markdown pricing policy.

We then show the following Lipschitz property on how the optimal revenue
$V^{*}(r,t_{1})$ depends on the starting reference price $r$. Notably, this
property holds for any reference effects.

######  Lemma 3.3 (Optimal revenue gap w.r.t. different starting reference
price).

Fix any starting time $t_{1}\in[T]$, the optimal revenue function
$V^{*}(r,t_{1})$ is increasing w.r.t. reference price $r$. Moreover, for any
$(\eta^{+},\eta^{-})$, we have $V^{*}(r^{\prime},t_{1})-V^{*}(r,t_{1})\leq
O\left(\bar{p}t_{1}(r^{\prime}-r)(\eta^{-}+\eta^{+})\ln\nicefrac{{T}}{{t_{1}}}\right)$
for any $r^{\prime}\geq r$.

The near optimality of markdown pricing for loss-averse customers immediately
follows by combining Lemma 3.2 and Lemma 3.3. Namely, fix an arbitrary
starting reference price, one can simply implement the price sequence from
optimal pricing policy (which is a markdown pricing policy) for starting
reference price $\bar{p}$, then one can guarantee near-optimal revenue. The
missing proofs for the above three lemmas and the detailed proof of Theorem 1
are deferred to Section A.2.

###  3.3 Characterizing Near-optimal Markdown Price Curve

In preceding discussions, we show the near optimality of markdown pricing
policy. In this section, focusing on base linear demand, namely, $H(p)=b-ap$,
we provide detailed structural characterizations for such near-optimal
markdown policy. We also provide computational results for computing such
policy.

The structure of the near-optimal markdown price curve. When the base demand
is $H(p)=b-ap$, we can characterize the following structure of a
(near-)optimal markdown policy:

######  Proposition 2.

Given a problem instance $I=(a,b,\eta^{+},\eta^{-})$ with linear base demand
model, and a starting reference price $r$, we define price curve
$\tilde{\mathbf{p}}(r)\triangleq(p_{t})_{t\in[T]}$ as:

$p_{t}=\begin{cases}\begin{aligned} &\bar{p},&&t\in[t^{\dagger}-1]&&\\\
&p^{\dagger},&&t=t^{\dagger}&&\\\
&p_{t-1}-\frac{\eta^{+}r_{t-1}}{2(a+\eta^{+})t+\eta^{+}},~{}~{}&&t\in[t^{\dagger}+1,T-1],~{}~{}&&\\\
&\frac{\eta^{+}r_{T}+b}{2(a+\eta^{+})},&&t=T,&\end{aligned}\end{cases}$

where $p^{\dagger}$ and $t^{\dagger}$ are some deterministic functions of
$(a,b,\eta^{+},r)$, and $r_{t}=\frac{r+\sum_{s=1}^{t-1}p_{s}}{t},t\in[T]$.
Then the price curve $\tilde{\mathbf{p}}(r)$ is optimal when
$\eta^{+}=\eta^{-}$, i.e., $V^{*}(r)=V^{\tilde{\mathbf{p}}(r)}(r)$.

Furthermore, the price curve $\tilde{\mathbf{p}}(\bar{p})$ (i.e., the above
price curve computed with $r=\bar{p}$) is near optimal when
$\eta^{+}\neq\eta^{-}$, namely, for any starting reference price $r$,
$V^{*}(r)-V^{\tilde{\mathbf{p}}(\bar{p})}(r)\leq O\left(\ln T\right)$.

We can see that price curve $\tilde{\mathbf{p}}(r)$ keeps charging the price
as the highest possible price $\bar{p}$ until the time round $t^{\dagger}-1$,
and then at $t^{\dagger}$ it strictly markdowns its price to $p^{\dagger}$.
Given the price $p_{t}$ at time round $t\geq t^{\dagger}$, the markdown amount
for the next price $p_{t+1}$ depends on the previous reference price $r_{t}$,
and the current time round $t+1$, and also the parameters $a,b,\eta^{+}$. In
particular, the parameters $a,\eta^{+}$ control the degree of the markdown
amount. The time round $t^{\dagger}$ and the price $p^{\dagger}$ can be
determined by the parameters $(a,b,\eta^{+})$, and the starting reference
price $r$.

We below give a graph illustration in Figure 1 about the shape of the price
curve $\tilde{\mathbf{p}}$. In the figure, we show that the time round
$t^{\dagger}$ could be strictly larger than first time round (see Figure 1a),
or could equal to first time round $t=1$, which in this case, the price curve
then becomes a strict markdown price curve (see Figure 1b) throughout the
sales horizon.

$\bar{p}$$p^{\dagger}$$t^{\dagger}$$p_{T}$$t=1$

(a)

$\bar{p}$$p^{\dagger}$$p_{T}$$t=1$

(b)

Figure 1:  An illustration of the price curve defined in Proposition 2.

######  Remark 3.

It is worth noting that the price curve defined in Proposition 2 only depends
on the gain effect parameter $\eta^{+}$. This property will be helpful in
designing our learning algorithm in Section 4.

###### Proof Sketch of Proposition 2.

The full proof is provided in Section A.3. Below we outline the ideas for
proving the optimality of $\tilde{\mathbf{p}}(r)$ when customers are loss-
neutral. We note that we can re-write the seller’s problem
$\mathcal{P}_{\mathsf{OPT}}$ using the following Bellman Equation:

$\displaystyle
V^{*}(r,t)=\sup_{p\in[0,\bar{p}]}~{}~{}\mathsf{Rev}\\!\left({p,r}\right)+V^{*}\left(\frac{tr+p}{t+1},t+1\right)~{}.$
($\mathcal{P}_{\mathsf{OPT-BE}}$)

When customers are loss-neutral, namely $\eta^{+}=\eta^{-}$, the single-shot
revenue function $\mathsf{Rev}\\!\left({p,r}\right)$ is differentiable in
$p,r$. Thus, we are able to apply the first-order optimality condition and
envelope theorem for the optimal price to the above program
$\mathcal{P}_{\mathsf{OPT-BE}}$ to deduce a condition on the partial
derivatives on the single-shot revenue function
$\mathsf{Rev}\\!\left({p,r}\right)$. In particular, we show that the optimal
prices $p_{t}^{*},p_{t+1}^{*}$ at time round $t,t+1$, repectively must satisfy
(partial derivatives are denoted by corresponding subscripts):

$\displaystyle\mathsf{Rev}_{p}\\!\left({p_{t}^{*},r}\right)+\frac{1}{t+1}\mathsf{Rev}_{r}\\!\left({p_{t+1}^{*},\frac{tr+p_{t}^{*}}{t+1}}\right)-\mathsf{Rev}_{p}\\!\left({p_{t+1}^{*},\frac{tr+p_{t}^{*}}{t+1}}\right)=0~{}.$
(4)

Substituting the revenue function $\mathsf{Rev}\\!\left({p,r}\right)$ with the
base linear demand can lead to the price markdown rule in Proposition 2.
Together with Theorem 1, we can deduce that the price curve defined in
Proposition 2 is indeed optimal for loss-neutral customers.

For customers with $\eta^{+}\neq\eta^{-}$, we use Lemma 3.1 and Lemma 3.2 to
show that the price curve $\tilde{\mathbf{p}}(\bar{p})$ is always near-
optimal. ∎

Computing a near-optimal markdown policy. Solving for an optimal pricing
policy (i.e., the set of equations $\mathcal{P}_{\mathsf{OPT-BE}}$) amounts to
solving a dynamic program with non-smooth and non-concave objective function
(as customers may have asymmetric reference effects, i.e.,
$\eta^{+}\neq\eta^{-}$) and time-variant transition function. Here, we show
that, by leveraging the markdown structure for the price curve defined in
Proposition 2, we are able to design an efficient algorithm that computes a
near-optimal markdown pricing curve.

######  Proposition 3 (Computing near-optimal Markdown).

For any $(\eta^{+},\eta^{-})$, there exists an algorithm (see Algorithm 3)
that solves only $O(\ln T)$ linear systems to compute the price curve
$\tilde{\mathbf{p}}(r)$ defined in Proposition 2 for any $r\in[0,\bar{p}]$.

###### Proof Sketch of Proposition 3.

The full proof is provided in Section A.3. Here we provide a proof sketch for
the case $\eta^{+}=\eta^{-}$. When $\eta^{+}=\eta^{-}$, the single-round
revenue function $\mathsf{Rev}\\!\left({\cdot,\cdot}\right)$ becomes smooth
and concave. By leveraging the optimality condition we have derived in (4), we
can show that the partial price sequence $(p_{t})_{t\in[t^{\dagger},T]}$ in
price curve $\tilde{\mathbf{p}}(r)$ can be solved by solving a system of
linear equations, i.e., a linear system $\bm{A}\mathbf{p}=\mathbf{b}$ where
$\bm{A}$ is $(T-t^{\dagger}+1)\times(T-t^{\dagger}+1)$ matrix and $\mathbf{b}$
is $(T-t^{\dagger}+1)$-dimensional vector. Both matrix $\bm{A}$ and vector
$\mathbf{b}$ can be determined by model parameter $I$, time round
$t^{\dagger}$, reference price $r_{t^{\dagger}}$ at time $t^{\dagger}$ and
sales horizon $T$ (see formal definitions of $\bm{A}$ and $\mathbf{b}$ in
Definition A.1). Thus, to determine the optimal policy for loss-neutral
customers, it suffices to determine the time round $t^{\dagger}$ (as reference
price $r_{t^{\dagger}}=\frac{r+(t^{\dagger}-1)\bar{p}}{t^{\dagger}}$ can be
determined by $t^{\dagger}$). Since this price curve $\tilde{\mathbf{p}}$ is a
markdown curve, we can deduce that the time round $t^{\dagger}$ is the
smallest time round such that the corresponding linear system
$\bm{A}\mathbf{p}=\mathbf{b}$ has a feasible solution. Thus, we can use a
binary search to determine the location of time $t^{\dagger}$. As there at
most $O(\ln T)$ steps to binary search the time $t^{\dagger}$, the algorithm
only solves at most $O(\ln T)$ many of linear systems to obtain the price
curve $\tilde{\mathbf{p}}(r)$ for any $r\in[0,\bar{p}]$. ∎

##  4 Learning and optimization under demand uncertainty

The proceeding section has analyzed the structure of the near-optimal pricing
policy under the $\mathsf{ARM}$ when the seller has the complete information
about the underlying demand function. This assumption obviously hinders
effective application of the resulting pricing policies in practice, where
demand functions are typically unknown and have to be learned from sales data.
In this section, we explore the design of the dynamic learning-and-pricing
policies in the presence of demand model uncertainty and customer reference
effects. In particular, we focus on a base linear demand model, namely,
$H(p)=b-ap$, and initially, the seller does not know the model parameter
$I=(a,b,\eta^{+},\eta^{-})$. In Section 4.1, we first discuss the challenges
in the seller’s dynamic pricing and learning problem, and then in Section 4.2,
we present solutions and proposed learning algorithm.

###  4.1 The Learning Challenges

When the seller has demand uncertainty, a key difficulty to design a low-
regret learning algorithm is the dynamic nature of the both reference-price
dynamics and the optimal pricing policy. Such non-stationarity creates unique
challenges to our problem.

Challenge one: learning in a non-stationary environment. One tempting dynamic
pricing-and-learning algorithm is to first estimate the model parameter
$I=(a,b,\eta^{+},\eta^{-})$. If we had a good estimate for the parameter $I$,
then we can compute the price curve $\tilde{\mathbf{p}}(r)$ with the estimated
model parameters. By Proposition 2, this price curve is near-optimal when
computed with true model parameters. Thus, if one can establish some kind of
Lipschitz property, we may be able to extend the near-optimality to the
estimated price curve. However, there are two main difficulties in
implementing this idea: (1) A typical approach to estimate the model parameter
is using the “iterated least squares” (Keskin and Zeevi, 2014), which charges
a test price for certain rounds, and another different price for other certain
rounds and then uses the observed demand to estimate the model parameter. This
approach relies on a crucial assumption that the underlying demand is
stationary and does not change over time. But in our setting, the underlying
demand function is non-stationary and depends on the choices of the past
prices through the reference price. Moreover, the underlying demand function
may also be non-smooth as customers may have asymmetric reference effects. It
is unclear how to use or modify this typical approach to account for the non-
stationarity and reference effects to learn the model parameters
$(a,b,\eta^{+},\eta^{-})$, especially learn the reference effect parameters
$(\eta^{+},\eta^{-})$. (2) In addition, the near-optimal price curve
$\tilde{\mathbf{p}}$ is highly non-stationary, and the price in this curve
depends on its current time and the model parameters in a highly non-trivial
way. It is unclear how this price curve changes w.r.t. the model parameter,
and thus it is difficult to establish the Lipschitz property of seller’s
cumulative revenue function w.r.t. the model parameter.

Challenge two: sensitivity to the reference price. Under $\mathsf{ARM}$, the
optimal revenue $V^{*}(r_{t},t)$ over the remaining rounds $[t,T]$ can be
quite sensitive to the starting reference price $r_{t}$ at time $t$. Indeed,
one can see that when the reference price $r_{t}$ is not close to the
reference price $r_{t}^{*}$ under the optimal pricing policy, then even though
the seller can use an optimal pricing policy (i.e., $\mathbf{p}^{*}(r_{t},t)$)
w.r.t. this reference price $r_{t}$ for the remaining rounds, the collected
revenue $V^{*}(r_{t},t)$ could be much smaller than the optimal revenue
$V^{*}(r_{t}^{*},t)$: the difference of these two revenues could be as large
as in the order of $O(t(r_{t}^{*}-r_{t})\ln\nicefrac{{T}}{{t}})$ (see Lemma
3.3). Intuitively, in this problem, the seller needs to learn and follow not
only the (near-)optimal price curve but also the reference price curve. One
potential fix is one can periodically try to move the current reference price
$r_{t}$ towards to a target reference price $r_{t^{\prime}}$ that is close to
the reference price $r_{t^{\prime}}^{*}$ at time $t^{\prime}$ under optimal
pricing policy. However, this fix does not work as (1) the seller does not
actually know $r_{t^{\prime}}^{*}$ (as she does not know the optimal pricing
policy); (2) even if the seller knew $r_{t^{\prime}}^{*}$, one may need
$\Omega(t\left|r_{t^{\prime}}-r_{t}\right|)$ rounds to reach to the reference
price $r_{t^{\prime}}$ from the reference price $r_{t}$ at time $t$, which
could lead to linear regret when $t$ is in the order of $T$. This challenge
makes certain restart mechanisms, which is a common approach used to tackle
the problem in learning with time-variant MDP (Besbes et al., 2014, Cheung et
al., 2020), inapplicable under $\mathsf{ARM}$.

###  4.2 Solution Ideas and the Proposed Learning Algorithm

In this section, we present our solution to the above challenges and our
proposed algorithm details.

Reparameterizing the price curve. The key observation in our algorithm design
is that we can generalize and reparameterize the price curve
$\tilde{\mathbf{p}}(r)$ defined in Proposition 2 in the following way: we can
generalize the price curve $\tilde{\mathbf{p}}(r,t_{1})$ with an arbitrary
starting time $t_{1}$ and starting reference price $r$ at this time; moreover,
instead of looking at the model parameter $I$, we can reparameterize the price
curve such that it depends on the model parameter $I$ only through a two-
dimensional policy parameter $\theta\in\Theta$ where
$\Theta\subseteq\mathbb{R}_{+}\times\mathbb{R}_{+}$ is a policy parameter
space that will be defined later. In particular, we have the following
generalized version of Proposition 2:

######  Lemma 4.1 (Generalized and reparameterized version of Proposition 2).

Given a policy parameter $\theta=(C_{1},C_{2})\in\Theta$, a starting reference
price $r$ at time $t_{1}\in[T]$, we define price curve
$\tilde{\mathbf{p}}(r,t_{1},\theta)\triangleq(p_{t})_{t\in[t_{1},T]}$ as:

$p_{t}=\begin{cases}\begin{aligned} &\bar{p},&&t\in[t_{1},t^{\dagger}-1]&&\\\
&p^{\dagger},&&t=t^{\dagger}&&\\\
&p_{t-1}-\frac{C_{1}r_{t-1}}{t+C_{1}},~{}~{}&&t\in[t^{\dagger}+1,T-1],~{}~{}&&\\\
&C_{1}r_{T}+C_{2},&&t=T,&\end{aligned}\end{cases}$

where $p^{\dagger}$ and $t^{\dagger}$ are some deterministic functions of
$(\theta,r,t_{1})$, and
$r_{t}=\frac{t_{1}r+\sum_{s=t_{1}}^{t-1}p_{s}}{t},t\in[t_{1},T]$. Given an
instance $I=(a,b,\eta^{+},\eta^{-})$, let
$\theta^{*}\triangleq(C_{1}^{*},C_{2}^{*})$ with

$\displaystyle C_{1}^{*}\triangleq\frac{\eta^{+}}{2(a+\eta^{+})},\quad
C_{2}^{*}\triangleq\frac{b}{2(a+\eta^{+})}~{}.$

Then the price curve $\tilde{\mathbf{p}}(r,t_{1},\theta^{*})$ is optimal when
$\eta^{+}=\eta^{-}$, i.e.,
$V^{*}(r,t_{1})=V^{\tilde{\mathbf{p}}(r,t_{1},\theta^{*})}(r,t_{1})$.
Furthermore, the price curve $\tilde{\mathbf{p}}(\bar{p},t_{1},\theta^{*})$ is
near-optimal when $\eta^{+}\neq\eta^{-}$, namely, for any starting reference
price $r$,
$V^{*}(r,t_{1})-V^{\tilde{\mathbf{p}}(\bar{p},t_{1},\theta^{*})}(r,t_{1})\leq
O\left(t_{1}\ln\nicefrac{{T}}{{t_{1}}}\right)$.

One benefit of the above generalization is that it provides a way to obtain a
price curve starting from any time $t_{1}$ that is near-optimal for the
remaining rounds as long as $t_{1}$ is not very large (e.g., if $t_{1}$ is
sublinear in $T$). By reparameterization, we also note that even though the
price curve $\tilde{\mathbf{p}}(r,t_{1},\theta^{*})$ heavily depends on the
starting time $t_{1}$, the universal constants $C_{1}^{*}$ and $C_{2}^{*}$ to
characterize this curve are fixed irrespective of the starting time round
$t_{1}$ and the starting reference price $r$ at $t_{1}$. This allows design of
an algorithm that first does some price explorations for sublinear rounds in
order to estimate these universal constants, and then implements the near-
optimal price curve for the remaining rounds based on these estimated
parameters.

######  Remark 4.

From 2.1 and non-negative demand at price $\bar{p}$, we know that the price
upper bound $\bar{p}$ must satisfy
$\nicefrac{{b}}{{2a}}<\bar{p}<\nicefrac{{b}}{{(a+\eta^{+})}}$, which implies
that one must have $a>\eta^{+}$. With this observation, we can deduce
$C_{1}^{*}<\nicefrac{{1}}{{4}},C_{2}^{*}\geq\nicefrac{{\bar{p}}}{{2}}$. Thus,
the the policy parameter $\theta^{*}$ induced by all possible
$I\in\mathcal{I}$ effectively satisfies that
$\theta^{*}\in[0,\nicefrac{{1}}{{4}})\times(\nicefrac{{\bar{p}}}{{2}},\infty)=:\Theta$.

######  Remark 5.

When $\eta^{+}=0$ and $\eta^{-}>0$, i.e., there is only loss reference effect,
the price curve defined in Proposition 2 would become a fixed-price policy
that keeps charging the price $\nicefrac{{b}}{{2a}}$.

Learning the policy parameter via greedy price. The above observations
motivate us to design an algorithm that could efficiently learn a good
estimate for the policy parameter $\theta^{*}=(C_{1}^{*},C_{2}^{*})$ defined
in Lemma 4.1. Interestingly, we observe that the greedy price for a certain
range of reference prices $r$ is also fully characterized by the policy
parameter $\theta^{*}$. In particular, let
$\delta\triangleq\bar{p}-\max_{I\in\mathcal{I}}\frac{b}{2a}$, then we can show
that given any reference price $r\in(\bar{p}-\delta,\bar{p}]$, the greedy
price $p^{\mathsf{GR}}(r)$ that maximizes the single-shot revenue function
$\mathsf{Rev}\\!\left({p,r}\right)$ subject to the constraint $p\leq r$ for
this reference price $r$ satisfies $p^{\mathsf{GR}}(r)\in[0,r]$, and moreover,
it can be characterized as follows (see Lemma 5.1)

$\displaystyle
p^{\mathsf{GR}}(r)\triangleq\frac{b+\eta^{+}r}{2(a+\eta^{+})}=C_{1}^{*}r+C_{2}^{*}~{}.$

The above observation implies that if we can learn two greedy prices
$p^{\mathsf{GR}}(r^{\circ})$ and $p^{\mathsf{GR}}(r^{\diamond})$ for two
different reference prices $r^{\circ}$ and $r^{\diamond}$, respectively. Then
we can solve the following system of two linear equations to get the policy
parameter $\theta^{*}=(C_{1}^{*},C_{2}^{*})$:

$\left\\{\begin{array}[]{l}p^{\mathsf{GR}}(r^{\circ})=C_{1}^{*}r^{\circ}+C_{2}^{*}~{},\\\
p^{\mathsf{GR}}(r^{\diamond})=C_{1}^{*}r^{\diamond}+C_{2}^{*}~{}.\end{array}\right.$
(5)

In addition, we observe that the single-shot revenue function
$\mathsf{Rev}\\!\left({\cdot,r}\right)$ over the price range $[0,r]$ is
strongly-concave and smooth. Thus, we can learn the greedy price by utilizing
ideas from stochastic convex optimization techniques. Notably, in our problem,
the seller can only learn a noisy demand value $D_{t}(p_{t},r)$ for the
expected demand $D(p_{t},r)$ at the chosen price $p_{t}$. With this feedback
structure, the problem of learning greedy price $p^{\mathsf{GR}}(r)$
essentially reduces to stochastic convex optimization with bandit feedback.

Algorithm 1 Dynamic pricing and learning under $\mathsf{ARM}$

1:Input: Horizon $T$, starting reference price $r_{1}$, price upper bound
$\bar{p}$.

2:Initialization: $T_{1}$; $r^{\circ}$, $r^{\diamond}$.

3:/* Exploration phase 1: learning an estimate
$\hat{p}^{\mathsf{GR}}(r^{\circ})$ for reference price $r^{\circ}$ */

4:Run $\mathsf{LearnGreedy}(T_{1},r^{\circ},\bar{p})$ to get
$\hat{p}^{\mathsf{GR}}(r^{\circ})$, and let $t$ be the current time step.

5:/* Exploration phase 2: learning an estimate
$\hat{p}^{\mathsf{GR}}(r^{\diamond})$ for reference price $r^{\diamond}$ */

6:Run $\mathsf{LearnGreedy}(T_{1},r^{\diamond},\bar{p})$ to get
$\hat{p}^{\mathsf{GR}}(r^{\diamond})$.

7:/* Exploitation phase */

8:Compute policy parameter estimate $\hat{\theta}=(\hat{C}_{1},\hat{C}_{2})$
from (7) using $\hat{p}^{\mathsf{GR}}(r^{\circ})$,
$\hat{p}^{\mathsf{GR}}(r^{\diamond})$.

9:/* Suppose current time is $T_{2}$ */

10:Compute the price curve $\tilde{\mathbf{p}}(\bar{p},T_{2},\hat{\theta})$
defined as in Lemma 4.1 with $\hat{\theta}$, and implement this price curve
for remaining rounds.

The algorithm details. With the above challenges and solutions in mind, we
design an “explore-then-exploit”-style policy-parameter learning algorithm. At
a high-level, our algorithm first learns estimates
$\hat{p}^{\mathsf{GR}}(r^{\circ})$, $\hat{p}^{\mathsf{GR}}(r^{\diamond})$ of
two greedy prices $p^{\mathsf{GR}}(r^{\circ}),p^{\mathsf{GR}}(r^{\diamond})$
for two carefully-set reference prices $r^{\circ},r^{\diamond}$, respectively.
Then the algorithm uses $\hat{p}^{\mathsf{GR}}(r^{\circ})$,
$\hat{p}^{\mathsf{GR}}(r^{\diamond})$ to construct an estimate $\hat{\theta}$
for the policy parameter $\theta^{*}\in\Theta$ by substituting these in (5).
Finally, it implements the price curve defined in Lemma 4.1 with the estimated
$\hat{\theta}$ for the remaining rounds. We summarize our proposed algorithm
in Algorithm 1.

  * $\bullet$

In both $\mathsf{Exploration\ phase\ 1}$ and $\mathsf{Exploration\ phase\ 2}$:
we design a stochastic convex optimization with bandit feedback algorithm to
learn two greedy price estimates $\hat{p}^{\mathsf{GR}}(r^{\circ})$ (in
$\mathsf{Exploration\ phase\ 1}$) and $\hat{p}^{\mathsf{GR}}(r^{\diamond})$
(in $\mathsf{Exploration\ phase\ 2}$). We summarize the steps of learning
greedy price in Algorithm 2, $\mathsf{LearnGreedy}$($T_{1},r,\bar{p}$), which
takes a time budget $T_{1}$, a reference price $r$, and the price upper bound
$\bar{p}$ as the input. In particular, we use $T_{1}$ to balance the
estimation error $|\hat{p}^{\mathsf{GR}}(r)-p^{\mathsf{GR}}(r)|$ and the
regret incurred in this algorithm; use reference price $r$ to learn the greedy
price $p^{\mathsf{GR}}(r)$; and use the price upper bound $\bar{p}$ to control
the learning rate. One difficulty here is while running the Algorithm 2, the
reference price will not remain fixed, but evolve according to $\mathsf{ARM}$.
Thus, to learn the greedy price for a particular reference price $r$, before
each learning round $t$ in Algorithm 2, we use a subroutine
$\mathsf{ResetRef}(t,r_{t},r^{\diamond})$ (described as Algorithm 4 in
Appendix B) to reset the current reference price to the reference price $r$.

  * $\bullet$

In $\mathsf{Exploitation\ Phase}$: we first construct the estimate
$\hat{\theta}=(\hat{C}_{1},\hat{C}_{2})$ using (5) with the estimates
$\hat{p}^{\mathsf{GR}}(r^{\circ})$ and $\hat{p}^{\mathsf{GR}}(r^{\diamond})$.
Suppose $T_{2}$ is the time that the algorithm enters in this phase, we then
compute the price curve $\tilde{\mathbf{p}}(\bar{p},T_{2},\hat{\theta})$
(defined in Lemma 4.1) with the policy parameter estimate $\hat{\theta}$, and
starting time $T_{2}$ (note that here we compute the price curve with starting
reference price $\bar{p}$, this price curve is near-optimal, by Lemma 4.1, for
any $(\eta^{+},\eta^{-})$ if we had $\hat{\theta}=\theta^{*}$ ). Then we
implement this price curve for remaining rounds.

1:Input: Budget $T_{1}$, reference price $r$, price upper bound $\bar{p}$.

2:Initialization: Initialize $p_{1}=p^{\mathsf{GR}}_{1}\in[0,\bar{p}]$
arbitrarily; let $d=\frac{1}{2}(r-\max_{I\in\mathcal{I}}\frac{b}{2a})$.

3:Initialization: Initialize $s\leftarrow 0,t\leftarrow 0$.

4:/* Counter $t$ records all time rounds */

5:/* Counter $s$ records learning rounds */

6:while $t<T$ and $s<T_{1}$ do

7: $t\leftarrow t+\mathsf{ResetRef}(t,r_{t},r)+1$. /* Use
$\mathsf{ResetRef}(t,r_{t},r)$ to reset reference price to $r$. */

8: $s\leftarrow s+1$.

9: Pick $\kappa\in\\{-1,1\\}$ uniformly at random.

10: Set the price $p_{t}\leftarrow p^{\mathsf{GR}}_{s}+\kappa d$, and observe
the realized demand $D_{t}(p_{t},r)$.

11: Let
$p^{\mathsf{GR}}_{s+1}\leftarrow\mathsf{PROJ}_{[d,r-d]}\left(p^{\mathsf{GR}}_{s}+\frac{p_{t}D_{t}(p_{t},r)}{2\bar{p}ds}\kappa\right)$.

12:end while

13:Return
$\hat{p}^{\mathsf{GR}}(r)=\frac{\sum_{s=1}^{T_{1}}p^{\mathsf{GR}}_{s}}{T_{1}}$,
and the current time $t$.

Algorithm 2 $\mathsf{LearnGreedy}$: Bandit stochastic convex optimization for
learning greedy price

##  5 Regret Analysis

In this section, we derive an upper bound the regret of Algorithm 1 for any
problem instance that has parameter $I=(a,b,\eta^{+},\eta^{-})$ in
$\mathcal{I}$. Recall that $\mathcal{I}\subseteq[0,1]^{4}$ was defined as the
set of all feasible parameter vectors satisfying 2.1.

######  Theorem 2.

With
$T_{1}=\widetilde{\Theta}\left(\frac{\bar{p}^{2}\sqrt{T}}{\sqrt{1+\bar{p}}}\right)$,
for any instance $I\in\mathcal{I}$, any starting reference price
$r\in[0,\bar{p}]$ at $t=1$, Algorithm 1 has expected regret

$\displaystyle\text{\bf
REG}^{\pi_{\mathsf{ALG}}}\\!\left[{T,I}\right]\leq\widetilde{O}\left(\bar{p}^{3}\sqrt{\bar{p}T}\right)~{}.$

As a comparison, for the setting where reference-price dynamics follow
$\mathsf{ESM}$, den Boer and Keskin, (2022), which also focuses on linear base
demand model, proposed a learning algorithm with a regret upper bound of
$\widetilde{O}(\nicefrac{{\bar{p}^{6}\sqrt{T}}}{{(1-\zeta)^{2}}})$ for loss
averse customers333The dependence of regret bound on $\bar{p}$ has not been
explicitly mentioned in the results of this paper. We have derived it here to
the best of our understanding of their proof.. Here, $\zeta$ is the constant
averaging factor as described in Remark 1. $\zeta_{t}=\nicefrac{{t}}{{(t+1)}}$
so that $1/(1-\zeta_{t})=t+1$. Thus naive application of their algorithm in
our setting with $\mathsf{ARM}$ would incur a linear regret. This again
highlights the previously mentioned observation that our $\mathsf{ARM}$ is
fundamentally different from $\mathsf{ESM}$.

Also note that our regret upper bound in Theorem 2 depends polynomially on the
price upper bound $\bar{p}$. When there is no reference effect, Keskin and
Zeevi, (2014) have shown that no learning algorithm can have regret growing
slower than $\Omega(\sqrt{T})$, even when restricted to instances satisfying
2.1. We build upon their proof to derive the following more detailed lower
bound that shows that for any learning algorithm, the dependence of regret on
$\bar{p}$ is unavoidable even when there are no reference effects.

######  Proposition 4.

Given a price upper bound $\bar{p}\geq 1$, consider the following problem
instances $\mathcal{I}^{\prime}$: let $\eta^{+}=\eta^{-}\equiv 0$, $b\equiv
1$, and $a\in[\frac{3}{4\bar{p}},\frac{1}{\bar{p}}]$. Then clearly all
instances in $\mathcal{I}^{\prime}$ satisfy 2.1. And the expected regret of
any algorithm $\pi_{\mathsf{ALG}}$ satisfies that
$\sup_{I\in\mathcal{I}^{\prime}}\text{\bf
REG}^{\pi_{\mathsf{ALG}}}\\!\left[{T,I}\right]\geq\frac{\bar{p}\sqrt{T-1}}{3\sqrt{1+36\pi^{2}}}$.

The proof of above Proposition 4 is in Section C.1. We below provide a proof
outline of Theorem 2. All missing proofs in the following subsection are in
Section C.2 to Section C.4.

###  5.1 Proof of Theorem 2

In this subsection, we provide an outline of different steps involved in
proving Theorem 2.

Step 1: Bounding the estimation error of the policy parameter.

In this step, we bound the estimation error $\|\hat{\theta}-\theta^{*}\|$ of
the policy parameter estimate $\hat{\theta}$, which is computed using the
outputs of Algorithm 2 for two reference prices $r^{\circ},r^{\diamond}$.
Given any reference price $r\in[0,\bar{p}]$, we consider the following greedy
price $p^{\mathsf{GR}}(r)$, which maximizes the single round revenue function
among all prices in the range $[0,r]$:

$p^{\mathsf{GR}}(r)\triangleq\max_{p\in[0,r]}~{}\mathsf{Rev}\\!\left({p,r}\right)=\max_{p\in[0,r]}~{}p\left(H(p)+\eta^{+}(r-p)\right)~{}.$
(6)

We first show that when the reference price $r$ satisfies
$r\in(\bar{p}-\delta,\bar{p}]$, we always have $p^{\mathsf{GR}}(r)\in[0,r]$,
and it can be fully characterized by the policy parameter $\theta^{*}$.

######  Lemma 5.1.

Fix any reference price $r\in(\bar{p}-\delta,\bar{p}]$, then greedy price
$p^{\mathsf{GR}}(r)=C_{1}^{*}r+C_{2}^{*}\in(0,r)$.

With the above Lemma 5.1, we can see that on fixing two different reference
prices $r^{\circ},r^{\diamond}\in(\bar{p}-\delta,\bar{p}]$, the greedy prices
$p^{\mathsf{GR}}(r^{\circ}),p^{\mathsf{GR}}(r^{\diamond})$ satisfy Equation 5.
And therefore, given the estimates $\hat{p}^{\mathsf{GR}}(r^{\circ})$,
$\hat{p}^{\mathsf{GR}}(r^{\diamond})$ to the greedy price
$p^{\mathsf{GR}}(r^{\circ})$ and $p^{\mathsf{GR}}(r^{\diamond})$, we can use
Equation 5 to compute a policy parameter estimate
$\hat{\theta}=(\hat{C}_{1},\hat{C}_{2})$ as follows

$\displaystyle\hat{C}_{1}=\frac{\hat{p}^{\mathsf{GR}}(r^{\diamond})-\hat{p}^{\mathsf{GR}}(r^{\circ})}{r^{\diamond}-r^{\circ}};\quad\hat{C}_{2}=\frac{\hat{p}^{\mathsf{GR}}(r^{\circ})r^{\diamond}-\hat{p}^{\mathsf{GR}}(r^{\diamond})r^{\circ}}{r^{\diamond}-r^{\circ}}~{}.$
(7)

We then have the following estimation error on the policy parameter estimate
$\hat{\theta}$:

######  Proposition 5.

Given two reference prices $r^{\circ},r^{\diamond}\in(\bar{p}-\delta,\bar{p}]$
where $r^{\circ}<r^{\diamond}$, let $\hat{\theta}=(\hat{C}_{1},\hat{C}_{2})$
be the estimated parameter obtained from Line $12$ in Algorithm 1, then the
following holds with probability at least $1-2\delta$ for
$\delta\in(0,\nicefrac{{1}}{{e}})$:

$\displaystyle\left\|\hat{\theta}-\theta^{*}\right\|\leq
O\left(\frac{\bar{p}^{2}\sqrt{\bar{p}\left(\log\left(\log\nicefrac{{t}}{{\delta}}\right)+1\right)}}{(r^{\diamond}-r^{\circ})\sqrt{T_{1}}}\right)~{}.$

The key step to prove Proposition 5 is the following characterization on how
the estimated greedy price $\hat{p}^{\mathsf{GR}}(r)$ is close to the true
greedy price $p^{\mathsf{GR}}(r)$.

######  Lemma 5.2.

Let $\delta\in(0,\nicefrac{{1}}{{e}})$ and let $r$ be the reference price to
the input of Algorithm 2. For any $T_{1}\geq 4$, we have the following holds
with probability at least $1-\delta$:

$\displaystyle\left|\hat{p}^{\mathsf{GR}}(r)-p^{\mathsf{GR}}(r)\right|\leq
O\left(\frac{\bar{p}^{2}}{d}\sqrt{\frac{\left(\log\left(\log\nicefrac{{T_{1}}}{{\delta}}\right)+1\right)}{T_{1}}}\right)~{},$

where $d$ is the parameter defined in Line 2 in Algorithm 2.

Our Algorithm 2 is built on Shamir, (2013), which proposed an algorithm for
stochastic strongly-convex optimization with bandit feedback with assuming
that the distance between the maximizer and the domain boundary is at least
$d$. We satisfy this assumption by carefully choosing the distance parameter
$d$ such that the greedy price $p^{\mathsf{GR}}(r)$ is always in the range
$[d,r-d]$ (see Lemma 5.1).

Intuitively, Algorithm 2 utilizes a well-known $1$-point gradient estimate
technique, to get an unbiased estimate of the gradient at the chosen price by
randomly querying for a (noisy) value of the function around it. For general
strongly-concave-and-smooth function (i.e., not necessarily being quadratic),
the attainable estimation error of the maximizer is
$\Theta(T_{1}^{-\nicefrac{{1}}{{4}}})$ (Shamir, 2013, Agarwal et al., 2010,
Jamieson et al., 2012). Instead, by leveraging the quadratic structure of the
revenue function $\mathsf{Rev}\\!\left({\cdot,r}\right)$, the gradient
estimates we construct have much smaller variance compared to the one for
general function, which allows us to obtain an improved estimation error
$O(T_{1}^{-\nicefrac{{1}}{{2}}})$.

With the estimation error bound in Lemma 5.2, Proposition 5 follows
immediately by the triangle inequality. The missing steps to prove Lemma 5.2
are provided in Section C.2.

Step 2: Bounding the total resetting regret.

In this step, we bound the total regret incurred from running the subroutine
$\mathsf{ResetRef}(\cdot,\cdot,)$ (i.e., Algorithm 4) before each of the
($2T_{1}$) learning round in Algorithm 2. In particular, we upper bound these
regrets by upper bounding the total number of rounds used in invoking
$\mathsf{ResetRef}(\cdot,\cdot,)$. The main results in this subsection are
summarized in the following lemma:

######  Lemma 5.3.

In all $\mathsf{Exploration\ phase\ 1}$ and $\mathsf{Exploration\ phase\ 2}$
of Algorithm 2, the number of rounds used in running
$\mathsf{ResetRef}(\cdot,\cdot,)$ is $O(T_{1})$.

Step 3: Bounding Lipschitz error in policy parameter space.

In this step, we establish a Lipschitz property of the revenue function
$V^{\tilde{\mathbf{p}}(r,t_{1},\theta)}(r,t_{1})$ with respect to the policy
parameter $\theta$ for the case of symmetric reference effects, i.e., when
$\eta^{+}=\eta^{-}\equiv\eta$. Since in this case
$V^{\tilde{\mathbf{p}}(r,t_{1},\theta^{*})}(r,t_{1})=V^{*}(r,t)$, this allows
us to bound the gap
$V^{*}(r,t_{1})-V^{\tilde{\mathbf{p}}(r,t_{1},\theta)}(r,t_{1})$ in terms of
policy parameter estimation error $\|\theta^{*}-\theta\|$. Later, we describe
how we use this result in the next step to establish regret for arbitrary
$\eta^{+},\eta^{-}$.

######  Proposition 6 (Bounding the Lipschitz error).

Assume $\eta^{+}=\eta^{-}\equiv\eta$. Fix a starting time $t_{1}\in[T]$, a
starting reference price $r$ at time $t_{1}$. Then, the following holds for
all $\theta\in\Theta$,

$\displaystyle
V^{\tilde{\mathbf{p}}(r,t_{1},\theta^{*})}(r,t_{1})-V^{\tilde{\mathbf{p}}(r,t_{1},\theta)}(r,t_{1})\leq
O\left((a+\eta)\bar{p}^{2}\left\|\theta^{*}-\theta\right\|^{2}(T-t_{1})\left(\ln\nicefrac{{T}}{{t_{1}}}\right)^{2}\right)~{}.$

###### Proof Sketch of Proposition 6.

A typical way to establish the Lipschitz property of a function is to bound
the gradient of this function, namely
$\nabla_{\theta}V^{\tilde{\mathbf{p}}(r,t_{1},\theta)}(r,t_{1})$. In our
problem, the dependence of the total revenue function
$V^{\tilde{\mathbf{p}}(r,t_{1},\theta)}(r,t_{1})$ over the policy parameter
$\theta$ is through the corresponding price curve
$\tilde{\mathbf{p}}(r,t_{1},\theta)$ (defined in Lemma 4.1), and this price
curve depends on the policy parameter in a highly non-trivial way. Thus, it is
not clear how to directly compute and bound the gradient
$\nabla_{\theta}V^{\tilde{\mathbf{p}}(r,t_{1},\theta)}(r,t_{1})$. Instead, we
use a two-step approach to establish the Lipschitz property of function
$V^{\tilde{\mathbf{p}}(r,t_{1},\theta)}(r,t_{1})$.

  * $\bullet$

Bounding the revenue gap
$\left|V^{\mathbf{p}}(r,t_{1})-V^{\mathbf{p}^{\prime}}(r,t_{1})\right|$ via
the distance on the price sequences
$\left\|\mathbf{p}-\mathbf{p}^{\prime}\right\|$: We first show that when the
optimal price curve $\tilde{\mathbf{p}}(r,t_{1},\theta^{*})$ (i.e., the price
curve defined in Lemma 4.1 computed with true policy parameter $\theta^{*}$)
is a strict markdown price curve, then the seller’s total revenue function
$V^{\mathbf{p}}(r,t_{1})$ is strongly concave over the price sequence
$\mathbf{p}$ (see below Lemma 5.4). We prove this result by bounding the
eigenvalues of the Hessian matrix
$\nabla^{2}_{\mathbf{p}}V^{\mathbf{p}}(r,t_{1})$. We note that this result
does not require the price sequence $\mathbf{p}$ is the price curve computed
in Lemma 4.1.

######  Lemma 5.4 (Strong concavity of function $V^{\mathbf{p}}$).

Fix a starting time $t_{1}\in[T]$ and starting reference price $r$. If the
price curve $\tilde{\mathbf{p}}(r,t_{1},\theta^{*})$ is a strict markdown
price curve (i.e., $t^{\dagger}=t_{1}$), then there exists two positive,
finite constants $c_{1}$ and $c_{2}$ where $c_{1}>c_{2}$, such that the
eigenvalue $\lambda_{V}$ of the Hessian matrix
$\nabla^{2}_{\mathbf{p}}V^{\mathbf{p}}(r,t_{1})$ satisfies
$\lambda_{V}\in\left[-2(a+\eta)c_{1},-2(a+\eta)c_{2}\right]$.

  * $\bullet$

Bounding the price curve distance
$\left\|\tilde{\mathbf{p}}(r,t_{1},\theta_{1})-\tilde{\mathbf{p}}(r,t_{1},\theta_{2})\right\|$
via the parameter distance $\|\theta_{1}-\theta_{2}\|$: We next establish a
“Lipschitz property” for the price curve $\tilde{\mathbf{p}}(r,t_{1},\theta)$
in terms of the differences between the policy parameters (see Lemma 5.5).

######  Lemma 5.5 (Lipschitz error on the price curve).

Fix a starting time $t_{1}\in[T]$ and starting reference price $r$. If price
curves $\tilde{\mathbf{p}}(r,t_{1},\theta_{1})$ and
$\tilde{\mathbf{p}}(r,t_{1},\theta_{2})$ are both strict markdown price
curves, then we have
$\left\|\tilde{\mathbf{p}}(r,t_{1},\theta_{1})-\tilde{\mathbf{p}}(r,t_{1},\theta_{2})\right\|\leq
O\left(\bar{p}\left\|\theta_{1}-\theta_{2}\right\|\sqrt{T-t_{1}}\ln\nicefrac{{T}}{{t_{1}}}\right)$.

Combining above two results can prove Proposition 6 when the both price curves
$\tilde{\mathbf{p}}(r,t_{1},\theta^{*})$ and
$\tilde{\mathbf{p}}(r,t_{1},\theta)$ are strictly markdown. On the other hand,
as we can see from Lemma 4.1, the curve
$\tilde{\mathbf{p}}(r,t_{1},\theta^{*})$ (or
$\tilde{\mathbf{p}}(r,t_{1},\theta)$) is not necessarily a strict markdown
curve, as it may keep charging the same price $\bar{p}$ for initial certain
rounds. For this case, notice there must exist a time round
$t^{\dagger}\in[t_{1},T]$ such that the partial price sequence
$\tilde{\mathbf{p}}(r_{t^{\dagger}},t^{\dagger},\theta^{*})=(p_{t})_{t\geq
t^{\dagger}}$ in $\tilde{\mathbf{p}}(r,t_{1},\theta^{*})$ must still be a
strict markdown price curve (and similarly, it holds true for
$\tilde{\mathbf{p}}(r,t_{1},\theta)$). Thus, in the analysis, we also bound
the gap between the time rounds at which the two price curves start to
strictly markdown their prices. Notably, we show that the revenue gap incurred
due to such time round gap is negligible compared to the revenue gap incurred
due to the policy parameter distance $\|\theta-\theta^{*}\|$. ∎

Step 4: Putting it all together. We now put all pieces together to show the
regret bound of Algorithm 1.

###### Proof of Theorem 2.

Let $(r_{t}^{*})_{t\in[T]}$ be the resulting reference price sequence under
the optimal policy $\mathbf{p}^{*}$. Let $\pi_{\mathsf{ALG}}$ be the pricing
policy implemented by Algorithm 1, and let $\mathbf{p}$ be the realized price
sequence from algorithm $\pi_{\mathsf{ALG}}$. Suppose $T_{2}\in[T]$ is the
first time round (notice that this is a random variable) that the Algorithm 1
enters in the Exploitation phase. According to our algorithm design, we know
that the pricing decisions over the time window $[T_{2},T]$ is the price curve
$\tilde{\mathbf{p}}(\bar{p},T_{2},\hat{\theta})$ with the starting reference
price $\bar{p}$ and parameter $\hat{\theta}$. Let
$\bar{R}\triangleq\max_{p,r}\mathsf{Rev}\\!\left({p,r}\right)$. For any
instance $I\in\mathcal{I}$, the total regrets can be decomposed and bounded as
follows:

$\displaystyle\text{\bf REG}^{\pi_{\mathsf{ALG}}}\\!\left[{T,I}\right]=~{}$
$\displaystyle
V^{*}(r_{1})-\mathbb{E}_{\mathbf{p}\sim\pi_{\mathsf{ALG}}}\\!\left[{V^{\mathbf{p}}(r_{1})}\right]$
$\displaystyle\overset{(a)}{\leq}~{}$
$\displaystyle\mathbb{E}_{\pi_{\mathsf{ALG}}}\\!\left[{O(T_{2}\bar{R})+V^{*}\left(r_{T_{2}}^{*},T_{2}\right)-V^{\tilde{\mathbf{p}}(\bar{p},T_{2},\hat{\theta})}\left(r_{T_{2}},T_{2}\right)}\right]$
$\displaystyle\overset{(b)}{\leq}~{}$
$\displaystyle\mathbb{E}_{\pi_{\mathsf{ALG}}}\\!\left[{O(T_{2}\bar{R})+V^{*}\left(\bar{p},T_{2}\right)-V^{\tilde{\mathbf{p}}(\bar{p},T_{2},\hat{\theta})}\left(r_{T_{2}},T_{2}\right)}\right]$
$\displaystyle\overset{(c)}{\leq}~{}$
$\displaystyle\mathbb{E}_{\pi_{\mathsf{ALG}}}\\!\left[{O(T_{2}\bar{R})+V^{*}\left(\bar{p},T_{2}\right)-V^{\tilde{\mathbf{p}}(\bar{p},T_{2},\hat{\theta})}\left(\bar{p},T_{2}\right)+O\left(\eta^{+}\bar{p}T_{2}\left|r_{T_{2}}-\bar{p}\right|\log\frac{T}{T_{2}}\right)}\right]$

where inequality (a) holds true by observing that the regret incurred in first
$T_{2}$ rounds is at most $T_{2}\bar{R}$; inequality (b) holds true by lemma
3.3 where $r_{T_{2}}^{*}\leq\bar{p}$; inequality (c) holds true by Lemma A.1
which bounds the revenue gap when a same price curve is applied with two
different starting reference prices.

We now observe that by Lemma 3.2, the optimal pricing policy to achieve
$V^{*}(\bar{p},T_{2})$ is a markdown pricing policy, thus,
$V^{*}(\bar{p},T_{2})$ exactly equals to the optimal revenue
$V^{*}(\bar{p},T_{2}\mid(\eta^{+},\eta^{+}))$ when the customers have
symmetric reference effects $\eta^{+}=\eta^{-}$ with starting reference price
$\bar{p}$. Here, we slightly abuse the notation and let
$V^{*}(r,t\mid(\eta^{+},\eta^{+}))$ feature that this cumulative revenue is
computed with reference effect parameter $(\eta^{+},\eta^{+})$. Moreover, the
cumulative revenue
$V^{\tilde{\mathbf{p}}(\bar{p},T_{2},\hat{\theta})}\left(\bar{p},T_{2}\right)$
is obtained by applying the markdown price curve
$\tilde{\mathbf{p}}(\bar{p},T_{2},\hat{\theta})$ with the starting reference
price $\bar{p}$ at time $T_{2}$. Thus, it only depends parameter $\eta^{+}$,
and
$V^{\tilde{\mathbf{p}}(\bar{p},T_{2},\hat{\theta})}\left(\bar{p},T_{2}\right)$
also equals to the cumulative revenue
$V^{\tilde{\mathbf{p}}(\bar{p},T_{2},\hat{\theta})}\left(\bar{p},T_{2}\mid(\eta^{+},\eta^{+})\right)$
when customers have $\eta^{+}=\eta^{-}$ with the starting reference price
$\bar{p}$. With this observation, we can further bound the regret as follows:

$\displaystyle\text{\bf REG}^{\pi_{\mathsf{ALG}}}\\!\left[{T,I}\right]\leq~{}$
$\displaystyle\mathbb{E}_{\pi_{\mathsf{ALG}}}\left[O(T_{2}\bar{R})+V^{*}\left(\bar{p},T_{2}\mid(\eta^{+},\eta^{+})\right)-V^{\tilde{\mathbf{p}}(\bar{p},T_{2},\hat{\theta})}\left(\bar{p},T_{2}\mid(\eta^{+},\eta^{+})\right)\right.$
$\displaystyle\left.+O\left(\eta^{+}\bar{p}T_{2}\left|r_{T_{2}}-\bar{p}\right|\log\frac{T}{T_{2}}\right)\right]$
$\displaystyle\overset{(a)}{\leq}~{}$
$\displaystyle\mathbb{E}_{\pi_{\mathsf{ALG}}}\left[O(T_{2}\bar{R})+O\left(\eta^{+}\bar{p}T_{2}\left|r_{T_{2}}-\bar{p}\right|\log\frac{T}{T_{2}}\right)+\delta\bar{R}\cdot\left(T-T_{2}\right)\right.$
$\displaystyle\left.+(1-\delta)O\left(\frac{\left(\bar{p}\log\left(\log\nicefrac{{T_{1}}}{{\delta}}\right)+1\right)\bar{p}^{4}}{\bar{p}^{2}T_{1}}\cdot(a+\eta^{+})\bar{p}^{2}(T-T_{2})\left(\log\frac{T}{T_{2}}\right)^{2}\right)\right]$
$\displaystyle\overset{(b)}{\leq}~{}$ $\displaystyle
O\left(\bar{p}^{3}\sqrt{(1+\bar{p})T(\log\log T+1)}(\log
T)^{\nicefrac{{3}}{{2}}}\right)=\widetilde{O}\left(\bar{p}^{3}\sqrt{\bar{p}T}\right)~{}.$

where inequality (a) holds by the fact that we are able to use Proposition 6
to bound the revenue gap via the policy parameter estimation error that we
obtain in Proposition 5 for symmetric reference effects $\eta^{+}=\eta^{-}$;
inequality (b) holds true by Lemma 5.3 where we have $T_{2}=O(T_{1})$, and by
noticing that $\bar{R}\leq\bar{p}(1+\bar{p})$, and we optimize
$T_{1}=\Theta\left(\bar{p}^{2}\sqrt{\frac{T(\log\log T+1)\log
T}{1+\bar{p}}}\right)=\widetilde{\Theta}\left(\frac{\bar{p}^{2}\sqrt{T}}{\sqrt{1+\bar{p}}}\right)$
and $\delta=\nicefrac{{1}}{{T}}$ to get the desired regret. ∎

##  6 Conclusions and Future Directions

In this work, we study dynamic pricing problem where customer response to the
current price is impacted by a reference price, which is formed by following
an averaging-reference mechanism ($\mathsf{ARM}$). We demonstrate that a
fixed-price policy is highly suboptimal in this setting, which sets it
distinctively apart from the well-studied $\mathsf{ESM}$ dynamics for
reference price effects. We also establish the (near-)optimality of markdown
pricing in $\mathsf{ARM}$ models. We show that under $\mathsf{ARM}$ with gain-
seeking customers, markdown pricing is optimal, and for loss-averse customers,
markdown pricing is near-optimal in the sense that the revenue achieved is
within $O(\log(T))$ of the optimal revenue.

Investigating this problem further for a linear base demand model, we provide
a detailed structural characterizations of a near-optimal markdown pricing
policy for both gain-seeking and loss-averse customers, along with an
efficient algorithm for computing such policies. We then study the dynamic
pricing and learning problem, where the demand model parameters are apriori
unknown. We provide an efficient learning algorithm with an asymptotically
optimal revenue performance.

Below we mention a few possible avenues for future research. First, what is
the general characterization of the optimal pricing policy when the underlying
base demand model beyond linear? We notice that for general base demand model,
the condition (4) for optimal prices that we derive here still holds. It would
be interesting to explore further what additional structural characterizations
we can infer from this condition. Second, the learning part of our work also
considers a linear base demand model. Though it is already interesting and
challenging enough to develop efficient learning algorithm for this case, it
would be interesting to generalize our idea to more general or non-parametric
demand models.

## References

  * Agarwal et al., (2010) Agarwal, A., Dekel, O., and Xiao, L. (2010).  Optimal algorithms for online convex optimization with multi-point bandit feedback.  In Colt, pages 28–40. Citeseer.
  * Agrawal et al., (2023) Agrawal, S., Feng, Y., and Tang, W. (2023).  Dynamic pricing and learning with bayesian persuasion.  arXiv preprint arXiv:2304.14385.
  * Agrawal and Jia, (2017) Agrawal, S. and Jia, R. (2017).  Optimistic posterior sampling for reinforcement learning: worst-case regret bounds.  Advances in Neural Information Processing Systems, 30.
  * Agrawal et al., (2021) Agrawal, S., Yin, S., and Zeevi, A. (2021).  Dynamic pricing and learning under the bass model.  In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 2–3.
  * Araman and Caldentey, (2009) Araman, V. F. and Caldentey, R. (2009).  Dynamic pricing for nonperishable products with demand learning.  Operations research, 57(5):1169–1188.
  * Arslan and Kachani, (2010) Arslan, H. and Kachani, S. (2010).  Dynamic pricing under consumer reference-price effects.  Wiley encyclopedia of operations research and management science.
  * Auer et al., (2008) Auer, P., Jaksch, T., and Ortner, R. (2008).  Near-optimal regret bounds for reinforcement learning.  Advances in neural information processing systems, 21.
  * Besbes et al., (2014) Besbes, O., Gur, Y., and Zeevi, A. (2014).  Stochastic multi-armed-bandit problem with non-stationary rewards.  Advances in neural information processing systems, 27.
  * Besbes and Zeevi, (2009) Besbes, O. and Zeevi, A. (2009).  Dynamic pricing without knowing the demand function: Risk bounds and near-optimal algorithms.  Operations research, 57(6):1407–1420.
  * Besbes and Zeevi, (2011) Besbes, O. and Zeevi, A. (2011).  On the minimax complexity of pricing in a changing environment.  Operations research, 59(1):66–79.
  * Besbes and Zeevi, (2015) Besbes, O. and Zeevi, A. (2015).  On the (surprising) sufficiency of linear models for dynamic pricing with demand learning.  Management Science, 61(4):723–739.
  * Birge et al., (2023) Birge, J. R., Chen, H., and Keskin, N. B. (2023).  Markdown policies for demand learning with forward-looking customers.  Operations Research.
  * Broder and Rusmevichientong, (2012) Broder, J. and Rusmevichientong, P. (2012).  Dynamic pricing under a general parametric choice model.  Operations Research, 60(4):965–980.
  * Cao et al., (2019) Cao, P., Zhao, N., and Wu, J. (2019).  Dynamic pricing with bayesian demand learning and reference price effect.  European Journal of Operational Research, 279(2):540–556.
  * Chen et al., (2017) Chen, X., Hu, P., and Hu, Z. (2017).  Efficient algorithms for the dynamic pricing problem with reference price effect.  Management Science, 63(12):4389–4408.
  * Chen et al., (2019) Chen, Y., Wen, Z., and Xie, Y. (2019).  Dynamic pricing in an evolving and unknown marketplace.  Available at SSRN 3382957.
  * Cheung et al., (2020) Cheung, W. C., Simchi-Levi, D., and Zhu, R. (2020).  Reinforcement learning for non-stationary markov decision processes: The blessing of (more) optimism.  In International Conference on Machine Learning, pages 1843–1854. PMLR.
  * (18) Den Boer, A. V. (2015a).  Dynamic pricing and learning: historical origins, current research, and new directions.  Surveys in operations research and management science, 20(1):1–18.
  * (19) Den Boer, A. V. (2015b).  Tracking the market: Dynamic pricing and learning in a changing environment.  European journal of operational research, 247(3):914–927.
  * den Boer and Keskin, (2022) den Boer, A. V. and Keskin, N. B. (2022).  Dynamic pricing with demand learning and reference effects.  Management Science, 68(10):7112–7130.
  * den Boer and Zwart, (2014) den Boer, A. V. and Zwart, B. (2014).  Simultaneously learning and optimizing using controlled variance pricing.  Management science, 60(3):770–783.
  * Fei et al., (2020) Fei, Y., Yang, Z., Wang, Z., and Xie, Q. (2020).  Dynamic regret of policy optimization in non-stationary environments.  Advances in Neural Information Processing Systems, 33:6743–6754.
  * Fibich et al., (2003) Fibich, G., Gavious, A., and Lowengart, O. (2003).  Explicit solutions of optimization models and differential games with nonsmooth (asymmetric) reference-price effects.  Operations Research, 51(5):721–734.
  * Gill and Levit, (1995) Gill, R. D. and Levit, B. Y. (1995).  Applications of the van trees inequality: a bayesian cramér-rao bound.  Bernoulli, pages 59–79.
  * Goldenshluger and Zeevi, (2009) Goldenshluger, A. and Zeevi, A. (2009).  Woodroofe’s one-armed bandit problem revisited.  The Annals of Applied Probability, pages 1603–1633.
  * Golrezaei et al., (2020) Golrezaei, N., Jaillet, P., and Liang, J. C. N. (2020).  No-regret learning in price competitions under consumer reference effects.  Advances in Neural Information Processing Systems, 33:21416–21427.
  * Google, (2023) Google (2023).  Transforming specialty retail with ai.  pages 26–Nov–2023.
  * Hu et al., (2016) Hu, Z., Chen, X., and Hu, P. (2016).  Dynamic pricing with gain-seeking reference price effects.  Operations Research, 64(1):150–157.
  * IBM, (2023) IBM (2023).  Ibm markdown optimization.  pages 26–Nov–2023.
  * Jamieson et al., (2012) Jamieson, K. G., Nowak, R., and Recht, B. (2012).  Query complexity of derivative-free optimization.  Advances in Neural Information Processing Systems, 25.
  * Ji et al., (2023) Ji, S., Yang, Y., and Shi, C. (2023).  Online learning and pricing for multiple products with reference price effects.  Available at SSRN 4349904.
  * Jia et al., (2021) Jia, S., Li, A., and Ravi, R. (2021).  Markdown pricing under unknown demand.  Available at SSRN 3861379.
  * Jia et al., (2022) Jia, S., Li, A., and Ravi, R. (2022).  Dynamic pricing with monotonicity constraint under unknown parametric demand model.  Advances in Neural Information Processing Systems, 35:19179–19188.
  * Keskin and Zeevi, (2014) Keskin, N. B. and Zeevi, A. (2014).  Dynamic pricing with an unknown demand model: Asymptotically optimal semi-myopic policies.  Operations research, 62(5):1142–1167.
  * Keskin and Zeevi, (2017) Keskin, N. B. and Zeevi, A. (2017).  Chasing demand: Learning and earning in a changing environment.  Mathematics of Operations Research, 42(2):277–307.
  * Kleinberg and Leighton, (2003) Kleinberg, R. and Leighton, T. (2003).  The value of knowing a demand curve: Bounds on regret for online posted-price auctions.  In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 594–605. IEEE.
  * Lattin and Bucklin, (1989) Lattin, J. M. and Bucklin, R. E. (1989).  Reference effects of price and promotion on brand choice behavior.  Journal of Marketing research, 26(3):299–310.
  * Lazear, (1986) Lazear, E. P. (1986).  Retail pricing and clearance sales.  The American Economic Review, 76(1):14–32.
  * Mazumdar et al., (2005) Mazumdar, T., Raj, S. P., and Sinha, I. (2005).  Reference price research: Review and propositions.  Journal of marketing, 69(4):84–102.
  * Nasiry and Popescu, (2011) Nasiry, J. and Popescu, I. (2011).  Dynamic pricing with loss-averse consumers and peak-end anchoring.  Operations research, 59(6):1361–1368.
  * Popescu and Wu, (2007) Popescu, I. and Wu, Y. (2007).  Dynamic pricing strategies with reference effects.  Operations research, 55(3):413–429.
  * Rajendran and Tellis, (1994) Rajendran, K. N. and Tellis, G. J. (1994).  Contextual and temporal components of reference price.  Journal of marketing, 58(1):22–34.
  * Rakhlin et al., (2012) Rakhlin, A., Shamir, O., and Sridharan, K. (2012).  Making gradient descent optimal for strongly convex stochastic optimization.  In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 1571–1578.
  * Shamir, (2013) Shamir, O. (2013).  On the complexity of bandit and derivative-free stochastic convex optimization.  In Conference on Learning Theory, pages 3–24. PMLR.
  * Wu et al., (2015) Wu, S., Liu, Q., and Zhang, R. Q. (2015).  The reference effects on a retailer’s dynamic pricing and inventory strategies with strategic consumers.  Operations Research, 63(6):1320–1335.

##  Appendix A Missing Proofs in Section 3

###  A.1 Missing Proofs of Section 3.1

See 1

###### Proof of Proposition 1.

We consider following problem instance: $\eta^{-}=\eta^{+}\equiv\eta$,
$r_{1}=0$, and the base demand is a linear demand $H(p)=b-ap$. Let
$\mathbf{p}(p)=(p,\ldots,p)$ denote a fixed-price policy that keeps charging
the price $p$ throughout the sales horizon. The total revenue under the fixed-
price policy is $\mathbf{p}$:

$\displaystyle V^{\mathbf{p}(p)}(r_{1})=Tp(b-ap)+\sum_{t=1}^{T}\eta
p(r_{t}-p)=Tp(b-ap)+\eta p(r_{1}-p)\sum_{t=1}^{T}\frac{1}{t}~{}.$

Let
$p^{*,\text{fixed}}=\mathop{\mathrm{arg\,max}}_{p\in[0,\bar{p}]}V^{\mathbf{p}}(r_{1})$
be the optimal fixed-price, and $V^{*,\text{fixed}}(r_{1})$ be its
corresponding total revenue, then we have

$\displaystyle p^{*,\text{fixed}}=\frac{Tb+\eta
r_{1}\sum_{t=1}^{T}\frac{1}{t}}{2\left(Ta+\eta\sum_{t=1}^{T}\frac{1}{t}\right)},\quad
V^{*,\text{fixed}}(r_{1})=\frac{\left(Tb+\eta
r_{1}\sum_{t=1}^{T}\frac{1}{t}\right)^{2}}{4\left(Ta+\eta\sum_{t=1}^{T}\frac{1}{t}\right)}\overset{(a)}{\leq}\frac{Tb^{2}}{4a}~{},$

where inequality (a) is due to $r_{1}=0$. Given a time round $T_{1}\in[T]$,
and let $\alpha=\frac{T}{T_{1}}$. We now consider the following non-fixed-
price policy $\mathbf{p}=(p_{t})_{p_{t}\in[T]}$ where
$p_{t}=p_{u}\mathbf{1}\\!\left\\{{t\leq\alpha
T_{1}}\right\\}+p_{d}\mathbf{1}\\!\left\\{{t\geq\alpha T_{1}+1}\right\\}$,
where $p_{u},p_{d}$ are determined later. Under the policy $\mathbf{p}$, the
total revenue is

$\displaystyle V^{\mathbf{p}}(r_{1})$
$\displaystyle=T_{1}p_{u}(b-ap_{u})+\sum_{t=1}^{T_{1}}\eta
p_{u}(r_{t}-p_{u})+(T-T_{1})p_{d}(b-ap_{d})+\sum_{t=T_{1}+1}^{T}\eta
p_{d}(r_{t}-p_{d})$ $\displaystyle=T_{1}p_{u}(b-ap_{u})+\sum_{t=1}^{T_{1}}\eta
p_{u}\frac{r_{1}-p_{u}}{t}+(T-T_{1})p_{d}(b-ap_{d})+\sum_{t=T_{1}+1}^{T}\eta
p_{d}\frac{r_{1}+T_{1}p_{u}-T_{1}p_{d}}{t}$ $\displaystyle=\alpha
Tp_{u}(b-ap_{u})-\eta p_{u}^{2}\ln(\alpha T)+T(1-\alpha)p_{d}(b-ap_{d})+\eta
p_{d}\alpha T(p_{u}-p_{d})\ln\frac{1}{\alpha}$
$\displaystyle=T\cdot\left(\alpha
p_{u}(b-ap_{u})+(1-\alpha)p_{d}(b-ap_{d})+\eta
p_{d}\alpha(p_{u}-p_{d})\ln\frac{1}{\alpha}\right)-\eta p_{u}^{2}\ln(\alpha
T)~{}.$

Given the value of $\alpha$, we choose $p_{u}$ and $p_{d}$ as follows

$\displaystyle
p_{d}=\frac{(1-\alpha)b+\eta\alpha\frac{b}{2a}\ln\frac{1}{\alpha}}{2(a(1-\alpha)+\eta\alpha\ln\frac{1}{\alpha})-(\eta\ln\frac{1}{\alpha})^{2}\frac{\alpha}{2a}},\quad
p_{u}=\frac{b+\eta p_{d}\ln\frac{1}{\alpha}}{2a}~{}.$ (8)

Essentially, we choose the above $p_{u},p_{d}$ such that it maximizes the
total revenue $V^{\mathbf{p}}(r_{1})$ under the value $\alpha$. With the above
value of $p_{u},p_{d}$, let $A(\alpha)\triangleq\alpha
p_{u}(b-ap_{u})+(1-\alpha)p_{d}(b-ap_{d})+\eta
p_{d}\alpha(p_{u}-p_{d})\ln\frac{1}{\alpha}$. With the above definitions, we
have

$\displaystyle V^{*}(r_{1})-V^{*,\text{fixed}}(r_{1})$ $\displaystyle\geq
V^{\mathbf{p}}(r_{1})-\frac{b^{2}T}{4a}$ $\displaystyle=TA(\alpha)-\eta
p_{u}^{2}\ln(\alpha T)-\frac{b^{2}T}{4a}$
$\displaystyle=T\cdot\left(A(\alpha)-\frac{b^{2}}{4a}\right)-\eta
p_{u}^{2}\ln(\alpha T)~{}.$

Notice that it is easy to find values for $a,b,\alpha,\eta$ such that we have
$A(\alpha)-\frac{b^{2}}{4a}\geq C$ for some positive constant $C>0$. For
example, let $b=2,a=1,\eta=0.5,\alpha=0.3$, we have
$A(\alpha)-\frac{b^{2}}{4a}=0.0318$. Moreover, under the above choices of
$a,b,\eta,\alpha$, we also have $p_{u}=1.2787$ and $p_{d}=0.926$, and consider
$\bar{p}=\frac{b}{a+\eta}=1.3333$. This implies that the above defined pricing
policy $\mathbf{p}$ is indeed a feasible pricing policy. Thus, we can conclude
that $V^{*}(r_{1})-V^{*,\text{fixed}}(r_{1})=\Omega(T)$. ∎

###  A.2 Missing Proofs of Section 3.2

See 3.1

###### Proof of Lemma 3.1.

Consider a pricing policy $\mathbf{p}=(p_{t})_{t\in[t_{1},T]}$ where the
reference price at time $t$ is $r_{t}$ and $p_{t}<p_{t+1}$. Now consider a new
pricing policy $\mathbf{p}^{\prime}=(p_{s}^{\prime})_{s\in[t_{1},T]}$ where:
(1) $p_{t}^{\prime}\leftarrow p_{t+1},p_{t+1}^{\prime}\leftarrow p_{t}$; (2)
$p_{s}^{\prime}\leftarrow p_{s}$ for all $s\in[t_{1},T]\setminus\\{t,t+1\\}$.
Let $r_{t}^{\prime},r_{t+1}^{\prime}$ be the induced reference price at rounds
$t,t+1$ under policy $\mathbf{p}^{\prime}$, respectively. By definition, we
have $r_{t}^{\prime}=r_{t}$, moreover, we also have the following observation

$\displaystyle
r_{t+1}^{\prime}=\frac{tr_{t}^{\prime}+p_{t}^{\prime}}{t+1}=\frac{tr_{t}+p_{t+1}}{t+1}>\frac{tr_{t}+p_{t}}{t+1}=r_{t+1}~{}.$
(9)

Notice that the revenue difference between the policy $\mathbf{p}^{\prime}$
and policy $\mathbf{p}$ is

$\displaystyle\Delta$ $\displaystyle\triangleq
p_{t}^{\prime}\left(\eta^{-}((r_{t}^{\prime}-p_{t}^{\prime})\wedge
0)+\eta^{+}((r_{t}^{\prime}-p_{t}^{\prime})\vee
0)\right)+p_{t+1}^{\prime}\left(\eta^{-}((r_{t+1}^{\prime}-p_{t+1}^{\prime})\wedge
0)+\eta^{+}((r_{t+1}^{\prime}-p_{t+1}^{\prime})\vee 0)\right)$ $\displaystyle-
p_{t}\left(\eta^{-}((r_{t}-p_{t})\wedge 0)+\eta^{+}((r_{t}-p_{t})\vee
0)\right)-p_{t+1}\left(\eta^{-}((r_{t+1}-p_{t+1})\wedge
0)+\eta^{+}((r_{t+1}-p_{t+1})\vee 0)\right)$
$\displaystyle=p_{t+1}\left(\eta^{-}((r_{t}-p_{t+1})\wedge
0)+\eta^{+}((r_{t}-p_{t+1})\vee
0)\right)+p_{t}\left(\eta^{-}((r_{t+1}^{\prime}-p_{t})\wedge
0)+\eta^{+}((r_{t+1}^{\prime}-p_{t})\vee 0)\right)$ $\displaystyle-
p_{t}\left(\eta^{-}((r_{t}-p_{t})\wedge 0)+\eta^{+}((r_{t}-p_{t})\vee
0)\right)-p_{t+1}\left(\eta^{-}((r_{t+1}-p_{t+1})\wedge
0)+\eta^{+}((r_{t+1}-p_{t+1})\vee 0)\right)$

To analyze whether $\Delta\geq 0$, we below consider two cases

  1. 1.

When $r_{t}\geq p_{t}$. Under this case, we know that

$\displaystyle r_{t+1}-r_{t}$
$\displaystyle=\frac{tr_{t}+p_{t}}{t+1}-r_{t}=\frac{p_{t}-r_{t}}{t+1}\leq 0$
$\displaystyle r_{t+1}^{\prime}-p_{t}$
$\displaystyle=\frac{tr_{t}+p_{t+1}}{t+1}-p_{t}=\frac{t(r_{t}-p_{t})+p_{t+1}-p_{t}}{t+1}>0$

Thus, we have

$\displaystyle\Delta$
$\displaystyle=p_{t+1}\left(\eta^{-}((r_{t}-p_{t+1})\wedge
0)+\eta^{+}((r_{t}-p_{t+1})\vee
0)\right)+p_{t}\eta^{+}(r_{t+1}^{\prime}-p_{t})$ $\displaystyle-
p_{t}\eta^{+}(r_{t}-p_{t})-p_{t+1}\left(\eta^{-}((r_{t+1}-p_{t+1})\wedge
0)+\eta^{+}((r_{t+1}-p_{t+1})\vee 0)\right)$

We further consider following two sub-cases

    1. (a)

When $p_{t+1}\geq r_{t}$. Under this sub-case, we have

$\displaystyle r_{t+1}-p_{t+1}$
$\displaystyle=\frac{tr_{t}+p_{t}}{t+1}-p_{t+1}=\frac{t(r_{t}-p_{t+1})+p_{t}-p_{t+1}}{t+1}<0$
$\displaystyle r_{t+1}^{\prime}-r_{t}$
$\displaystyle=\frac{tr_{t}+p_{t+1}}{t+1}-r_{t}=\frac{p_{t+1}-r_{t}}{t+1}\geq
0$

Thus, we have

$\displaystyle\Delta$
$\displaystyle=p_{t+1}\eta^{-}(r_{t}-p_{t+1})+p_{t}\eta^{+}(r_{t+1}^{\prime}-p_{t})-p_{t}\eta^{+}(r_{t}-p_{t})-p_{t+1}\eta^{-}(r_{t+1}-p_{t+1})$
$\displaystyle=p_{t+1}\eta^{-}(r_{t}-r_{t+1})+p_{t}\eta^{+}(r_{t+1}^{\prime}-r_{t})\geq
0$

    2. (b)

When $p_{t+1}<r_{t}$. Under this sub-case, we have

$\displaystyle r_{t+1}^{\prime}-r_{t}$
$\displaystyle=\frac{tr_{t}+p_{t+1}}{t+1}-r_{t}=\frac{p_{t+1}-r_{t}}{t+1}<0$

Thus, we have

$\displaystyle\Delta$
$\displaystyle=p_{t+1}\eta^{+}(r_{t}-p_{t+1})+p_{t}\eta^{+}(r_{t+1}^{\prime}-p_{t})$
$\displaystyle-
p_{t}\eta^{+}(r_{t}-p_{t})-p_{t+1}\left(\eta^{-}((r_{t+1}-p_{t+1})\wedge
0)+\eta^{+}((r_{t+1}-p_{t+1})\vee 0)\right)$

Now suppose we have $r_{t+1}\leq p_{t+1}$, then

$\displaystyle\Delta$
$\displaystyle=p_{t+1}\eta^{+}(r_{t}-p_{t+1})+p_{t}\eta^{+}(r_{t+1}^{\prime}-p_{t})-p_{t}\eta^{+}(r_{t}-p_{t})-p_{t+1}\eta^{-}(r_{t+1}-p_{t+1})$
$\displaystyle=p_{t+1}\eta^{+}(r_{t}-p_{t+1})-p_{t+1}\eta^{-}(r_{t+1}-p_{t+1})+p_{t}\eta^{+}(r_{t+1}^{\prime}-r_{t})$
$\displaystyle=p_{t+1}\eta^{+}(r_{t}-p_{t+1})-p_{t+1}\eta^{-}(r_{t+1}-p_{t+1})-p_{t}\eta^{+}\frac{r_{t}-p_{t+1}}{t+1}$
$\displaystyle\overset{(a)}{>}p_{t}\eta^{+}(r_{t}-p_{t+1})-p_{t+1}\eta^{-}(r_{t+1}-p_{t+1})-p_{t}\eta^{+}\frac{r_{t}-p_{t+1}}{t+1}$
$\displaystyle=p_{t}\eta^{+}(r_{t}-p_{t+1})\cdot\left(1-\frac{1}{t+1}\right)+p_{t+1}\eta^{-}(p_{t+1}-r_{t+1})\geq
0$

where in inequality (a) we use the fact that $p_{t}<p_{t+1}$.

Now suppose we have $r_{t+1}>p_{t+1}$, then we have

$\displaystyle\Delta$
$\displaystyle=p_{t+1}\eta^{+}(r_{t}-p_{t+1})+p_{t}\eta^{+}(r_{t+1}^{\prime}-p_{t})-p_{t}\eta^{+}(r_{t}-p_{t})-p_{t+1}\eta^{+}(r_{t+1}-p_{t+1})$
$\displaystyle=p_{t+1}\eta^{+}(r_{t}-r_{t+1})+p_{t}\eta^{+}(r_{t+1}^{\prime}-r_{t})$
$\displaystyle=\eta^{+}\cdot\left(p_{t+1}\frac{r_{t}-p_{t}}{t+1}+p_{t}\frac{p_{t+1}-r_{t}}{t+1}\right)=\eta^{+}\cdot\frac{r_{t}(p_{t+1}-p_{t})}{t+1}\geq
0$

Thus, under this sub-case, we also have $\Delta\geq 0$.

  2. 2.

When $r_{t}<p_{t}$. Under this case, we have $r_{t}<p_{t}\leq p_{t+1}$, and
moreover

$\displaystyle r_{t+1}-r_{t}$
$\displaystyle=\frac{tr_{t}+p_{t}}{t+1}-r_{t}=\frac{p_{t}-r_{t}}{t+1}>0$
$\displaystyle r_{t+1}-p_{t+1}$
$\displaystyle=\frac{tr_{t}+p_{t}}{t+1}-p_{t+1}=\frac{t(r_{t}-p_{t+1})+p_{t}-p_{t+1}}{t+1}<0$

Thus, we have

$\displaystyle\Delta$
$\displaystyle=p_{t+1}\eta^{-}(r_{t}-p_{t+1})+p_{t}\left(\eta^{-}((r_{t+1}^{\prime}-p_{t})\wedge
0)+\eta^{+}((r_{t+1}^{\prime}-p_{t})\vee 0)\right)$ $\displaystyle-
p_{t}\eta^{-}(r_{t}-p_{t})-p_{t+1}\eta^{-}(r_{t+1}-p_{t+1})$
$\displaystyle=p_{t+1}\eta^{-}(r_{t}-r_{t+1})-p_{t}\eta^{-}(r_{t}-p_{t})+p_{t}\left(\eta^{-}((r_{t+1}^{\prime}-p_{t})\wedge
0)+\eta^{+}((r_{t+1}^{\prime}-p_{t})\vee 0)\right)$

Now suppose we have $r_{t+1}^{\prime}\leq p_{t}$, then

$\displaystyle\Delta$
$\displaystyle=p_{t+1}\eta^{-}(r_{t}-r_{t+1})-p_{t}\eta^{-}(r_{t}-p_{t})+p_{t}\eta^{-}(r_{t+1}^{\prime}-p_{t})$
$\displaystyle=p_{t+1}\eta^{-}(r_{t}-r_{t+1})+p_{t}\eta^{-}(r_{t+1}^{\prime}-r_{t})$
$\displaystyle=\eta^{-}\cdot\left(p_{t+1}(r_{t}-r_{t+1})+p_{t}(r_{t+1}^{\prime}-r_{t})\right)$
$\displaystyle=\eta^{-}\cdot\left(p_{t+1}\frac{r_{t}-p_{t}}{t+1}+p_{t}\frac{p_{t+1}-r_{t}}{t+1}\right)=\eta^{-}\cdot\frac{r_{t}(p_{t+1}-p_{t})}{t+1}\geq
0$

Now suppose we have $r_{t+1}^{\prime}>p_{t}$, then

$\displaystyle\Delta$
$\displaystyle=p_{t+1}\eta^{-}(r_{t}-r_{t+1})-p_{t}\eta^{-}(r_{t}-p_{t})+p_{t}\eta^{+}(r_{t+1}^{\prime}-p_{t})$
$\displaystyle\overset{(a)}{\geq}p_{t+1}\eta^{-}(r_{t}-r_{t+1})-p_{t}\eta^{-}(r_{t}-p_{t})+p_{t}\eta^{-}(r_{t+1}^{\prime}-p_{t})$
$\displaystyle=p_{t+1}\eta^{-}(r_{t}-r_{t+1})+p_{t}\eta^{-}(r_{t+1}^{\prime}-r_{t})\geq
0$

where in inequality (a), we use the fact that $\eta^{+}\geq\eta^{-}$. Thus,
under this case, we always have $\Delta\geq 0$

Putting all pieces together, we can prove the statement. ∎

See 3.3 To prove Lemma 3.3, we first show the following lemma which bound the
revenue gap when implementing a same pricing policy under different starting
reference prices.

######  Lemma A.1.

Fix any policy $\mathbf{p}$, we have $0\leq
V^{\mathbf{p}}(r^{\prime},t_{1})-V^{\mathbf{p}}(r,t_{1})\leq
O\left(\bar{p}t_{1}(r^{\prime}-r)(\eta^{-}+\eta^{+})\ln\frac{T}{t_{1}}\right)$
for any $r^{\prime}\geq r$.

###### Proof of Lemma A.1.

Fix any pricing policy $\mathbf{p}=(p_{t})_{t\in[t_{1},T]}$, let
$(r_{t})_{t\in[t_{1},T]}$ (resp. $(r_{t}^{\prime})_{t\in[t_{1},T]}$) be the
resulting reference price path under the starting reference price $r$ (resp.
$r^{\prime}$). Then by definition, for any $t\in[t_{1},T]$, we have

$\displaystyle
r_{t}^{\prime}-r_{t}=\frac{r^{\prime}t_{1}+\sum_{s=t_{1}}^{t-1}p_{s}}{t}-\frac{rt_{1}+\sum_{s=t_{1}}^{t-1}p_{s}}{t}=\frac{t_{1}(r^{\prime}-r)}{t}\geq
0~{}.$

Thus,

$\displaystyle V^{\mathbf{p}}(r^{\prime},t_{1})-V^{\mathbf{p}}(r,t_{1})$
$\displaystyle=~{}$
$\displaystyle\sum_{t=t_{1}}^{T}p_{t}\cdot\left(\eta^{-}((r_{t}^{\prime}-p_{t})\wedge
0-(r_{t}-p_{t})\wedge 0)+\eta^{+}((r_{t}^{\prime}-p_{t})\vee
0-(r_{t}-p_{t})\vee 0)\right)\geq 0$

where the last inequality is due to the fact that $r_{t}^{\prime}\geq r_{t}$
for all $t\in[t_{1},T]$. Moreover,

$\displaystyle V^{\mathbf{p}}(r^{\prime},t_{1})-V^{\mathbf{p}}(r,t_{1})$
$\displaystyle=~{}$
$\displaystyle\sum_{t=t_{1}}^{T}p_{t}\cdot\left(\eta^{-}((r_{t}^{\prime}-p_{t})\wedge
0-(r_{t}-p_{t})\wedge 0)+\eta^{+}((r_{t}^{\prime}-p_{t})\vee
0-(r_{t}-p_{t})\vee 0)\right)$ $\displaystyle\leq~{}$
$\displaystyle\sum_{t=t_{1}}^{T}p_{t}\cdot\left(\eta^{-}\frac{t_{1}(r^{\prime}-r)}{t}+\eta^{+}\frac{t_{1}(r^{\prime}-r)}{t}\right)=\bar{p}t_{1}(r^{\prime}-r)(\eta^{-}+\eta^{+})\sum_{t=t_{1}}^{T}\frac{1}{t}$
$\displaystyle=~{}$ $\displaystyle
O\left(\bar{p}t_{1}(r^{\prime}-r)(\eta^{-}+\eta^{+})\ln\frac{T}{t_{1}}\right)~{}.$

∎

We now prove Lemma 3.3.

###### Proof of Lemma 3.3.

Fix any pricing policy $\mathbf{p}=(p_{t})_{t\in[t_{1},T]}$, let
$(r_{t})_{t\in[t_{1},T]}$ (resp. $(r_{t}^{\prime})_{t\in[t_{1},T]}$) be the
resulting reference price path under the starting reference price $r$ (resp.
$r^{\prime}$).

Let $\mathbf{p}^{*}(r,t_{1})$ (resp. $\mathbf{p}^{*}(r^{\prime},t_{1})$) be
the optimal pricing policy under the starting reference price $r$ (resp.
$r^{\prime}$). Then,

$\displaystyle V^{*}(r^{\prime},t_{1})-V^{*}(r,t_{1})\geq
V^{\mathbf{p}^{*}(r,t_{1})}(r^{\prime},t_{1})-V^{\mathbf{p}^{*}(r,t_{1})}(r,t_{1})\geq
0~{},$

where last inequality is by Lemma A.1. Moreover,

$\displaystyle V^{*}(r^{\prime},t_{1})-V^{*}(r,t_{1})$ $\displaystyle\leq
V^{*}(r^{\prime},t_{1})-V^{\mathbf{p}^{*}(r^{\prime},t_{1})}(r,t_{1})=O\left(\bar{p}t_{1}(r^{\prime}-r)(\eta^{-}+\eta^{+})\ln\frac{T}{t_{1}}\right)~{},$

where last equality is by Lemma A.1, thus completing the proof. ∎

See 3.2

###### Proof of Lemma 3.2.

We prove by contradiction. Let us fix $r_{t_{1}}=\bar{p}$. Suppose under a
pricing policy $\mathbf{p}=(p_{t})_{t\in[t_{1},T]}$, there exists a time step
$k\in[t_{1},T]$ such that the resulting reference price $r_{k}$ satisfies
$r_{k}<p_{t_{1}}$. Then it implies that there exists a time step $s<k$ such
that (i) $p_{s}<p_{k}$; (ii) $p_{t}\geq p_{k}$ for all $t<s$. We now define a
new pricing policy $\mathbf{p}=(p_{t}^{\prime})_{t\in[t_{1},T]}$ such that it
satisfies (1) $p_{s}^{\prime}=p_{k},p_{k}^{\prime}=p_{s};$ (2)
$p_{t}^{\prime}=p_{t},\forall t\in[t_{1},T]\setminus\\{s,k\\}$. Then we
consider

$\displaystyle
V^{\mathbf{p}^{\prime}}(\bar{p},t_{1})-V^{\mathbf{p}}(\bar{p},t_{1})$
$\displaystyle=~{}$ $\displaystyle\sum_{t\in[s,k]}p_{t}^{\prime}\cdot
H(p_{t}^{\prime})+p_{t}^{\prime}\cdot\left(\eta^{-}((r_{t}^{\prime}-p_{t}^{\prime})\wedge
0)+\eta^{+}((r_{t}^{\prime}-p_{t}^{\prime})\vee 0)\right)$
$\displaystyle\quad-\sum_{t\in[s,k]}p_{t}\cdot
H(p_{t})+p_{t}\cdot\left(\eta^{-}((r_{t}-p_{t})\wedge
0)+\eta^{+}((r_{t}-p_{t})\vee 0)\right)$ $\displaystyle\overset{(a)}{\geq}~{}$
$\displaystyle p_{s}^{\prime}\cdot
H(p_{s}^{\prime})+p_{s}^{\prime}\cdot\left(\eta^{-}((r_{s}^{\prime}-p_{s}^{\prime})\wedge
0)+\eta^{+}((r_{s}^{\prime}-p_{s}^{\prime})\vee 0)\right)$
$\displaystyle+p_{k}^{\prime}\cdot
H(p_{k}^{\prime})+p_{k}^{\prime}\cdot\left(\eta^{-}((r_{k}^{\prime}-p_{k}^{\prime})\wedge
0)+\eta^{+}((r_{k}^{\prime}-p_{k}^{\prime})\vee 0)\right)$ $\displaystyle-
p_{s}\cdot H(p_{s})+p_{s}\cdot\left(\eta^{-}((r_{s}-p_{s})\wedge
0)+\eta^{+}((r_{s}-p_{s})\vee 0)\right)$ $\displaystyle-p_{k}\cdot
H(p_{k})+p_{k}\cdot\left(\eta^{-}((r_{k}-p_{k})\wedge
0)+\eta^{+}((r_{k}-p_{k})\vee 0)\right)$ $\displaystyle\overset{(b)}{=}~{}$
$\displaystyle
p_{k}\cdot\eta^{+}(r_{s}-p_{k})+p_{s}\cdot\left(\eta^{-}((r_{k}^{\prime}-p_{s})\wedge
0)+\eta^{+}((r_{k}^{\prime}-p_{s})\vee 0)\right)$ $\displaystyle-
p_{s}\cdot\eta^{+}(r_{s}-p_{s})-p_{k}\eta^{-}(r_{k}-p_{k})$

where inequality (a) is due to the fact that for any $t\in[s+1,k-1]$,
$r_{t}^{\prime}-r_{t}=\frac{p_{k}-p_{s}}{t}>0$, and $p_{t}^{\prime}=p_{t}$,
thus we have
$\mathsf{Rev}\\!\left({p_{t}^{\prime},r_{t}^{\prime}}\right)\geq\mathsf{Rev}\\!\left({p_{t},r_{t}}\right)$,
and equality (b) is due to $r_{s}\geq p_{k}>p_{s}$ and $r_{k}<p_{k}$. Let
$A\triangleq\sum_{s=s+1}^{k-1}p_{t}$. Then we notice that

$\displaystyle r_{k}=\frac{sr_{s}+p_{s}+A}{k}\leq
r_{s}\quad\Rightarrow\quad(k-s)r_{s}-A\geq p_{s}\geq 0$

Let $\Delta$ denote the right-hand-side of the above equation (b). We below
consider two possible cases:

  1. 1.

When $r_{k}^{\prime}\geq p_{s}$. Under this case, we know that

$\displaystyle\Delta$
$\displaystyle=p_{k}\cdot\eta^{+}(r_{s}-p_{k})+p_{s}\cdot\eta^{+}(r_{k}^{\prime}-p_{s})-p_{s}\cdot\eta^{+}(r_{s}-p_{s})-p_{k}\eta^{-}(r_{k}-p_{k})$
$\displaystyle=p_{k}\cdot\eta^{+}(r_{s}-p_{k})+p_{s}\cdot\eta^{+}(r_{k}^{\prime}-r_{s})-p_{k}\eta^{-}(r_{k}-p_{k})$
$\displaystyle\geq
p_{k}\cdot\eta^{+}(r_{s}-p_{k})+p_{s}\cdot\eta^{+}(r_{k}^{\prime}-r_{s})-p_{k}\eta^{+}(r_{k}-p_{k})$
$\displaystyle=p_{k}\cdot\eta^{+}(r_{s}-r_{k})+p_{s}\cdot\eta^{+}(r_{k}^{\prime}-r_{s})$
$\displaystyle=\eta^{+}\cdot\left(p_{k}\frac{kr_{s}-sr_{s}-p_{s}-A}{k}+p_{s}\frac{sr_{s}+p_{k}+A-kr_{s}}{k}\right)$
$\displaystyle=\eta^{+}\cdot\frac{p_{k}(k-s)r_{s}-p_{k}p_{s}-p_{k}A+p_{s}(s-k)r_{s}+p_{k}p_{s}+p_{s}A}{k}$
$\displaystyle=\eta^{+}\cdot\frac{(p_{k}-p_{s})((k-s)r_{s}-A)}{k}\geq 0$

  2. 2.

When $r_{k}^{\prime}<p_{s}$. Under this case, we know that

$\displaystyle\Delta$
$\displaystyle=p_{k}\cdot\eta^{+}(r_{s}-p_{k})+p_{s}\cdot\eta^{-}(r_{k}^{\prime}-p_{s})-p_{s}\cdot\eta^{+}(r_{s}-p_{s})-p_{k}\eta^{-}(r_{k}-p_{k})$
$\displaystyle=\eta^{+}\cdot\left(p_{k}(r_{s}-p_{k})-p_{s}(r_{s}-p_{s})\right)+\eta^{-}\left(p_{k}(p_{k}-r_{k})-p_{s}(p_{s}-r_{k}^{\prime})\right)$

When $p_{k}(r_{s}-p_{k})-p_{s}(r_{s}-p_{s})\geq 0$, we have

$\displaystyle\Delta\geq\eta^{-}\left(p_{k}(p_{k}-r_{k})-p_{s}(p_{s}-r_{k}^{\prime})\right)\geq
0$

where the last inequality is due to $p_{k}>p_{s},r_{k}<r_{k}^{\prime}$.

When $p_{k}(r_{s}-p_{k})-p_{s}(r_{s}-p_{s})<0$, with the assumption that
$\eta^{-}\geq\eta^{+}$ we have

$\displaystyle\Delta$
$\displaystyle\geq\eta^{-}\cdot\left(p_{k}(r_{s}-p_{k})-p_{s}(r_{s}-p_{s})\right)+\eta^{-}\left(p_{k}(p_{k}-r_{k})-p_{s}(p_{s}-r_{k}^{\prime})\right)$
$\displaystyle=\eta^{-}\cdot\left(p_{k}(r_{s}-r_{k})-p_{s}(r_{s}-r_{k}^{\prime})\right)\geq
0$

Putting all pieces together, we can prove the statement. ∎

See 1

###### Proof of Theorem 1.

When $\eta^{+}\geq\eta^{-}$, Theorem 1 holds true due to Lemma 3.1. When
$\eta^{+}<\eta^{-}$, for this case, let the policy $\mathbf{p}^{*}(\bar{p})$
be the optimal pricing policy under the reference effect $(\eta^{-},\eta^{+})$
and under the starting reference price $\bar{p}$. From Lemma 3.2, we know that
policy $\mathbf{p}^{*}(\bar{p})$ is a markdown pricing policy. Thus,

$\displaystyle
V^{*}(r_{1})-V^{\mathbf{p}^{*}(\bar{p})}(r_{1})\overset{(a)}{\leq}V^{*}(\bar{p})-V^{\mathbf{p}^{*}(\bar{p})}(r_{1})\overset{(b)}{\leq}O\left(\bar{p}(\bar{p}-r_{1})(\eta^{-}+\eta^{+})\ln
T\right)$

where inequality (a) is by Lemma 3.3 with $\bar{p}\geq r_{1}$, and inequality
(b) is by Lemma A.1. ∎

###  A.3 Missing Proofs of Section 3.3

To prove Proposition 2, we prove the following generalized and reparameterized
version presented in Section 4: See 4.1

###### Proof of Lemma 4.1.

We first prove the optimality of price curve
$\tilde{\mathbf{p}}(r,t_{1},\theta^{*})$ when $\eta^{+}=\eta^{-}$. Then we
show the near optimality of price curve
$\tilde{\mathbf{p}}(\bar{p},t_{1},\theta^{*})$ when $\eta^{+}\neq\eta^{-}$.
The optimality of $\tilde{\mathbf{p}}(r,t_{1},\theta^{*})$ when
$\eta^{+}=\eta^{-}$. In the proof, we show that the optimal pricing policy
$\mathbf{p}^{*}(r,t_{1})=\tilde{\mathbf{p}}(r,t_{1},\theta^{*})$. Let
$\eta^{+}=\eta^{-}\equiv\eta$. Fix a time window $[t_{1},T]$ and an starting
reference price $r_{t_{1}}=r$ at time $t_{1}$. Recall that seller’s program
$\mathcal{P}_{\mathsf{OPT-BE}}$

$\displaystyle
V^{*}(r,t)=\max_{p\in[0,\bar{p}]}\mathsf{Rev}\\!\left({p,r}\right)+V^{*}\left(\frac{tr+p}{t+1},t+1\right)~{}.$

We denote partial derivatives by using subscripts. By first-order optimality
condition, we know that the optimal price $p_{t}^{*}$ must satisfy

$\displaystyle\mathsf{Rev}_{p}\\!\left({p_{t}^{*},r}\right)+V^{*}_{r}\left(\frac{tr+p_{t}^{*}}{t+1},t+1\right)\frac{1}{t+1}=0~{}.$
(10)

By envelope theorem, we have

$\displaystyle
V^{*}_{r}(r,t)=\mathsf{Rev}_{r}\\!\left({p_{t}^{*},r}\right)+V^{*}_{r}\left(\frac{tr+p_{t}^{*}}{t+1},t+1\right)\frac{t}{t+1}~{}.$
(11)

From (10), we have
$V^{*}_{r}\left(\frac{tr+p_{t}^{*}}{t+1},t+1\right)=-(t+1)\mathsf{Rev}_{p}\\!\left({p_{t}^{*},r}\right)$,
substituting it in (11) and we get

$\displaystyle V^{*}_{r}(r,t)$
$\displaystyle=\mathsf{Rev}_{r}\\!\left({p_{t}^{*},r}\right)-t\mathsf{Rev}_{p}\\!\left({p_{t}^{*},r}\right)=\eta
p_{t}^{*}-t\left(p_{t}^{*}H_{p}(p_{t}^{*})+H(p_{t}^{*})+\eta r-2\eta
p_{t}^{*}\right)~{}.$

Thus, we can also deduce that

$\displaystyle
V^{*}_{r}\left(\frac{tr+p_{t}^{*}}{t+1},t+1\right)=\mathsf{Rev}_{r}\\!\left({p_{t+1}^{*},\frac{tr+p_{t}^{*}}{t+1}}\right)-(t+1)\mathsf{Rev}_{p}\\!\left({p_{t+1}^{*},\frac{tr+p_{t}^{*}}{t+1}}\right)~{}.$

Finally, substitute the above formula into (10) and obtain a condition which
does not depend on the value function anymore:

$\displaystyle\mathsf{Rev}_{p}\\!\left({p_{t}^{*},r}\right)+\frac{1}{t+1}\mathsf{Rev}_{r}\\!\left({p_{t+1}^{*},\frac{tr+p_{t}^{*}}{t+1}}\right)-\mathsf{Rev}_{p}\\!\left({p_{t+1}^{*},\frac{tr+p_{t}^{*}}{t+1}}\right)=0$

where we have used the fact that $\mathsf{Rev}_{r}\\!\left({p,r}\right)=\eta
p$. For base linear demand $H(p)=b-ap$, the above equality gives us

$\displaystyle p^{*}_{t}=p^{*}_{t+1}+\frac{\eta
r}{2(a+\eta)(t+1)+\eta}=p^{*}_{t+1}+\frac{C_{1}^{*}r}{t+1+C_{1}^{*}}~{}.$ (12)

From Theorem 1, we know that when $\eta^{+}=\eta^{-}$, the optimal pricing
policy is a markdown pricing policy. Together with the above observation, we
can deduce that the optimal pricing policy
$\mathbf{p}^{*}=(p_{t}^{*})_{t\in[t_{1},T]}$ must keep charging the price as
the highest possible price $\bar{p}$ for until time round $t^{\dagger}$, and
then markdowns its prices according to (12) for the remaining rounds.

It now remains to characterize the time $t^{\dagger}$ and the price
$p^{\dagger}$. From Theorem 1 and (12), we know optimal pricing policy
$\mathbf{p}^{*}=(p_{t}^{*})$ must satisfy that there exists a time round
$t^{\dagger}\in[t_{1},T]$ and a price $p^{\dagger}$ at time $t^{\dagger}$ such
that:

$\displaystyle p_{t}^{*}$
$\displaystyle=\left\\{\begin{array}[]{ll}\bar{p}&\text{if
}t\in[t_{1},t^{\dagger}-1]\\\ \displaystyle p^{\dagger}&\text{if
}t=t^{\dagger}\\\ \displaystyle
p_{t-1}^{*}-\frac{C_{1}^{*}r_{t-1}^{*}}{t+C_{1}^{*}}&\text{if
}t\in[t^{\dagger}+1,T-1]\\\ \displaystyle
C_{1}^{*}r_{t}^{*}+C_{2}^{*}&\text{if }t=T\end{array}\right.$

where $(r_{t}^{*})$ is the reference price sequence from optimal pricing
policy.

Let $r^{\dagger}\triangleq r_{t^{\dagger}}^{*}$. We can now roll out the above
relation for the price $p_{t+1}^{*}$ until we can write the price $p_{t+1}$ as
a function of the initial price $p^{\dagger}$:

$\displaystyle
p_{t+1}^{*}=A_{t+1}(C_{1}^{*})p^{\dagger}+B_{t+1}(C_{1}^{*},r^{\dagger})~{}.$

where
$(A_{t}(C_{1}^{*}),B_{t}(C_{1}^{*},r^{\dagger}))_{t\in[t^{\dagger},T-1]}$ are
defined as follows:

$\displaystyle A_{t}(C_{1}^{*})$
$\displaystyle=\left\\{\begin{array}[]{ll}1&\text{if }t=t^{\dagger}\\\
\displaystyle
A_{t-1}(C_{1}^{*})-\frac{C_{1}^{*}}{t+C_{1}^{*}}\frac{1}{t-1}\cdot\sum_{s=t^{\dagger}}^{t-2}A_{s}(C_{1}^{*})&\text{if
}t\in[t^{\dagger}+1:T-1]\\\
\displaystyle\frac{C_{1}^{*}\sum_{s=t^{\dagger}}^{T-1}A_{s}(C_{1}^{*})}{T}&\text{if
}t=T\end{array}\right.$ $\displaystyle B_{t}(C_{1}^{*},r^{\dagger})$
$\displaystyle=\left\\{\begin{array}[]{ll}0&\text{if }t=t^{\dagger}\\\
\displaystyle
B_{t-1}(C_{1}^{*},r^{\dagger})-\frac{C_{1}^{*}}{t+C_{1}^{*}}\frac{1}{t-1}\cdot\left(t^{\dagger}r^{\dagger}+\sum_{s=t^{\dagger}}^{t-2}B_{s}(C_{1}^{*},r^{\dagger})\right)&\text{if
}t\in[t^{\dagger}+1:T-1]\\\ \displaystyle
C_{1}^{*}\cdot\frac{t^{\dagger}r^{\dagger}+\sum_{s=t^{\dagger}}^{T-1}B_{s}(C_{1}^{*},r^{\dagger})}{T}&\text{if
}t=T\end{array}\right.$

From (12), we can also deduce

$\displaystyle
p^{\dagger}=C_{2}^{*}+C_{1}^{*}\sum_{s=t^{\dagger}+1}^{T}\frac{p_{s}^{*}}{s}~{}.$

Plugging in the relation
$p_{t}^{*}=A_{t}(C_{1}^{*})p^{\dagger}+B_{t}(C_{1}^{*},r^{\dagger})$ and
$p_{T}^{*}=C_{1}^{*}r_{T}+C_{2}^{*}$, we can pin down the price $p^{\dagger}$
as follows:

$\displaystyle
p^{\dagger}=\frac{\bar{B}_{[t^{\dagger},T]}(C_{1}^{*},r^{\dagger})+C_{2}^{*}+\frac{C_{1}^{*}C_{2}^{*}}{T}}{1-\bar{A}_{[t^{\dagger},T]}(C_{1}^{*})}=p\left([t^{\dagger},T],r^{\dagger},(C_{1}^{*},C_{2}^{*})\right)~{}.$

where we intentionally feature the
$[t^{\dagger},T],r^{\dagger},(C_{1}^{*},C_{2}^{*})$ dependence of
$p\left([t^{\dagger},T],r^{\dagger},(C_{1}^{*},C_{2}^{*})\right)$ prominently
and

$\displaystyle\bar{A}_{[t^{\dagger},T]}(C_{1}^{*})$
$\displaystyle=C_{1}^{*}\cdot\left(\sum_{s=t^{\dagger}+1}^{T-1}\frac{A_{s}(C_{1}^{*})}{s}+\frac{C_{1}^{*}}{T^{2}}\sum_{s=t^{\dagger}}^{T-1}A_{s}(C_{1}^{*})\right)$
$\displaystyle\bar{B}_{[t^{\dagger},T]}(C_{1}^{*},r^{\dagger})$
$\displaystyle=C_{1}^{*}r^{\dagger}+C_{1}^{*}\cdot\left(\sum_{s=t^{\dagger}+1}^{T-1}\frac{B_{s}(C_{1}^{*},r^{\dagger})}{s}+\frac{C_{1}^{*}}{T^{2}}\left(t^{\dagger}r^{\dagger}+\sum_{s=t^{\dagger}}^{T-1}B_{s}(C_{1}^{*},r^{\dagger})\right)\right)~{}.$

Clearly, the time step $t^{\dagger}\in[t_{1},T]$ in optimal pricing policy
should satisfy that

$\displaystyle
t^{\dagger}=\min\left\\{k\in[t_{1},T]:p\left([t^{\dagger},T],\frac{t_{1}r+(t^{\dagger}-t_{1})\bar{p}}{t^{\dagger}},(C_{1}^{*},C_{2}^{*})\right)\in[0,\bar{p}]\right\\}~{}.$

We finish the proof of this part by showing the existence of $t^{\dagger}$.
Let us look at the final time round $T$ with the starting reference price
$r_{T}=\frac{t_{1}r+(T-t_{1})\bar{p}}{T}\in[0,\bar{p}]$, then according to the
above definition, we have

$\displaystyle
p\left([T,T],r_{T},(C_{1}^{*},C_{2}^{*})\right)=C_{2}^{*}+C_{1}^{*}r_{T}\overset{(a)}{\leq}\bar{p}$

where inequality (a) is due to the fact that
$\bar{p}-(C_{2}^{*}+C_{1}^{*}r_{T})\geq\bar{p}-(C_{2}^{*}+C_{1}^{*}\bar{p})=\frac{2a\bar{p}-b+\eta\bar{p}}{2(a+\eta)}\geq
0$ due to $\bar{p}>\nicefrac{{b}}{{2a}}$ from 2.1.

The near optimality of $\tilde{\mathbf{p}}(\bar{p},t_{1},C_{1}^{*})$ when
$\eta^{+}\neq\eta^{-}$. In this part, we also write
$V^{*}(r,t_{1}\mid(\eta^{-},\eta^{+}))$ to emphasize that it is the optimal
value under the starting reference price $r$ and customers reference effect
parameters $(\eta^{-},\eta^{+})$.

When $\eta^{+}\geq\eta^{-}$, let
$\mathbf{p}^{*}(\bar{p},t_{1})=(p_{t,\bar{p}}^{*})_{t\in[t_{1},T]}$ be the
optimal pricing policy under starting reference price $\bar{p}$ and customers’
reference effects $(\eta^{+},\eta^{-})$. Let $(r_{t,\bar{p}}^{*})_{t\in[T]}$
be the resulting reference price sequence under policy
$\mathbf{p}^{*}(\bar{p},t_{1})$ and starting reference price $\bar{p}$. We
first note that

$\displaystyle V^{*}(\bar{p},t_{1}\mid(\eta^{+},\eta^{-}))$
$\displaystyle=\sum_{t=t_{1}}^{T}p_{t,\bar{p}}^{*}\cdot\left(H(p_{t,\bar{p}}^{*})+\eta^{-}\left(r_{t,\bar{p}}^{*}-p_{t,\bar{p}}^{*}\right)\wedge
0+\eta^{+}\left(r_{t,\bar{p}}^{*}-p_{t,\bar{p}}^{*}\right)\vee 0\right)$
$\displaystyle\overset{(a)}{=}\sum_{t=t_{1}}^{T}p_{t,\bar{p}}^{*}\cdot\left(H(p_{t,\bar{p}}^{*})+\eta^{+}\left(r_{t,\bar{p}}^{*}-p_{t,\bar{p}}^{*}\right)\right)$
$\displaystyle=V^{*}(\bar{p},t_{1}\mid(\eta^{+},\eta^{+}))~{}.$

where equality (a) is by Theorem 1 where we know that policy
$\mathbf{p}^{*}(\bar{p},t_{1})$ must be a markdown pricing policy, and given
the starting reference price $\bar{p}$, we then must have
$p_{t,\bar{p}}^{*}\leq r_{t,\bar{p}}^{*}$ for all $t\in[t_{1},T]$. Since the
optimal pricing policy when customers have symmetric reference effects
$\eta^{+}=\eta^{-}$ is also a markdown policy, we can conclude that policy
$\mathbf{p}^{*}(\bar{p},t_{1})$ also maximizes
$V^{\mathbf{p}}(r,t_{1}\mid(\eta^{+},\eta^{+}))$. In other words, we have
policy
$\mathbf{p}^{*}(\bar{p},t_{1})=\tilde{\mathbf{p}}(\bar{p},t_{1},\theta^{*})$.

Then,

$\displaystyle
V^{*}(r,t_{1}\mid(\eta^{+},\eta^{-}))-V^{\tilde{\mathbf{p}}(\bar{p},t_{1},\theta^{*})}(r,t_{1}\mid(\eta^{+},\eta^{-}))$
$\displaystyle\overset{(a)}{\leq}V^{*}(\bar{p},t_{1}\mid(\eta^{+},\eta^{-}))-V^{\tilde{\mathbf{p}}(\bar{p},t_{1},\theta^{*})}(r,t_{1}\mid(\eta^{+},\eta^{-}))$
$\displaystyle\overset{(b)}{\leq}O\left(t_{1}\eta^{+}\bar{p}(\bar{p}-r)\ln\nicefrac{{T}}{{t_{1}}}\right)$

where inequality (a) is by Lemma 3.3 with $r\leq\bar{p}$, and inequality (b)
is by Lemma A.1.

When $\eta^{-}>\eta^{+}$, follow Lemma 3.2 and the similar argument above, we
know that policy $\mathbf{p}^{*}(\bar{p},t_{1})$ also maximizes
$V^{\mathbf{p}}(\bar{p},t_{1})=\tilde{\mathbf{p}}(\bar{p},t_{1},\theta^{*})$.
Then we have

$\displaystyle
V^{*}(r,t_{1})-V^{\tilde{\mathbf{p}}(\bar{p},t_{1},\theta^{*})}(r,t_{1})\leq
V^{*}(\bar{p},t_{1})-V^{\tilde{\mathbf{p}}(\bar{p},t_{1},\theta^{*})}(r,t_{1})$
$\displaystyle=V^{\mathbf{p}^{*}(\bar{p},t_{1})}(\bar{p},t_{1})-V^{\tilde{\mathbf{p}}(\bar{p},t_{1},\theta^{*})}(r,t_{1})$
$\displaystyle\leq
O\left(t_{1}\bar{p}(\bar{p}-r)(\eta^{-}+\eta^{+})\ln\nicefrac{{T}}{{t_{1}}}\right)$

where the last inequality is by Lemma A.1. ∎

Then the proof of Proposition 2 follows immediately.

###### Proof of Proposition 2.

Proposition 2 follows by noting that $t_{1}=1$ in Lemma 4.1. ∎

1:Input: starting reference price $r$, time horizon $T$,
$\theta^{*}\leftarrow(C_{1}^{*},C_{2}^{*})$.

2:Initialization: $t_{1}\leftarrow 1$.

3:while $t_{1}<T$ do

4: $t^{\dagger}\leftarrow\frac{t_{1}+T}{2}$.

5: Let
$r_{t^{\dagger}}\leftarrow\frac{r+(t^{\dagger}-1)\bar{p}}{t^{\dagger}}$.

6: Solve the linear system
$\bm{A}_{[t^{\dagger},T]}(\theta^{*})\mathbf{p}=\mathbf{b}_{[t^{\dagger},T],r_{t^{\dagger}}}(\theta^{*})$
where
$\bm{A}_{[t^{\dagger},T]}(\theta^{*}),\mathbf{b}_{[t^{\dagger},T],r_{t^{\dagger}}}(\theta^{*})$
are defined as in Definition A.1.

7: Let $t_{1}\leftarrow\frac{t_{1}+t^{\dagger}}{2}$ if
$\mathbf{p}\in[0,\bar{p}]^{T-t^{\dagger}+1}$, otherwise let
$t_{1}\leftarrow\frac{t^{\dagger}+T}{2}$.

8:end while

9:Return $\tilde{\mathbf{p}}(r)=(p_{t})_{t\in[T]}$ where
$p_{t}\leftarrow\bar{p}\mathbf{1}\\!\left\\{{t<t^{\dagger}}\right\\}+\mathbf{p}[t-t^{\dagger}+1]\mathbf{1}\\!\left\\{{t\geq
t^{\dagger}}\right\\}$ for all $t\in[T]$.

Algorithm 3 Computing the pricing curve $\tilde{\mathbf{p}}(r)$

See 3

###### Proof of Proposition 3.

Notice that the price curve $\tilde{\mathbf{p}}(r)$ is optimal to the loss-
neutral customers. Thus, To prove Proposition 3, it suffices to show that
there exists an algorithm that can solve for an optimal pricing policy for
loss-neutral customers by solving at most $O(\ln T)$ linear systems.

When $\eta^{+}=\eta^{-}=\eta$, the derived optimality condition (12) can be
reformulated as follows: for any $t\in[t^{\dagger},T]$

$\displaystyle
p_{t}^{*}=C_{1}^{*}r_{t}^{*}+C_{1}^{*}\sum_{s=t+1}^{T}p_{s}^{*}+C_{2}^{*}$
$\displaystyle=C_{1}^{*}\cdot\frac{t^{\dagger}r^{\dagger}+\sum_{s=t^{\dagger}}^{t-1}p_{s}^{*}}{t}+C_{1}^{*}\sum_{s=t+1}^{T}p_{s}^{*}+C_{2}^{*}~{}.$

As we can see, given a time round $t^{\dagger}$ and the reference price
$r^{\dagger}$ at this round, the above condition essentially says that the
optimal price $p_{t}^{*}$ can be represented by a linear combination over all
other prices $(p_{s}^{*})_{s\in[t^{\dagger},T]\setminus\\{t\\}}$. In other
words, the partial price sequence $(p_{t}^{*})_{t\in[t^{\dagger},T]}$ forms a
linear system where the matrix and vector in this system depend on model
parameters $C_{1}^{*},C_{2}^{*},t^{\dagger},r^{\dagger},T$. In particular, the
linear system can be defined as follows:

######  Definition A.1 (Linear system).

Given a time window $[t^{\dagger},T]$ and an starting reference price
$r_{t^{\dagger}}=r^{\dagger}$ at time $t^{\dagger}$. We define the following
matrix $\bm{A}_{[t^{\dagger},T]}(\theta^{*})$ and the vector
$\mathbf{b}_{[t^{\dagger},T],r^{\dagger}}(\theta^{*})$ which takes parameter
$\theta^{*}=(C_{1}^{*},C_{2}^{*})$ (defined as in (4.1)) as input:

$\displaystyle\bm{A}_{[t^{\dagger},T]}(\theta^{*})$
$\displaystyle={\left[\centering\begin{tabular}[]{ccccccc}$\displaystyle
1$&$\displaystyle-\frac{C_{1}^{*}}{t^{\dagger}+1}$&$\displaystyle-\frac{C_{1}^{*}}{t^{\dagger}+2}$&$\displaystyle-\frac{C_{1}^{*}}{t^{\dagger}+3}$&$\displaystyle\ldots$&$\displaystyle-\frac{C_{1}^{*}}{T-1}$&$\displaystyle-\frac{C_{1}^{*}}{T}$\\\
$\displaystyle-\frac{C_{1}^{*}}{t^{\dagger}+1}$&$\displaystyle
1$&$\displaystyle-\frac{C_{1}^{*}}{t^{\dagger}+2}$&$\displaystyle-\frac{C_{1}^{*}}{t^{\dagger}+3}$&$\displaystyle\ddots$&$\displaystyle-\frac{C_{1}^{*}}{T-1}$&$\displaystyle-\frac{C_{1}^{*}}{T}$\\\
$\displaystyle-\frac{C_{1}^{*}}{t^{\dagger}+2}$&$\displaystyle-\frac{C_{1}^{*}}{t^{\dagger}+2}$&$\displaystyle
1$&$\displaystyle-\frac{C_{1}^{*}}{t^{\dagger}+3}$&$\displaystyle\ddots$&$\displaystyle-\frac{C_{1}^{*}}{T-1}$&$\displaystyle-\frac{C_{1}^{*}}{T}$\\\
$\displaystyle\vdots$&$\displaystyle\ddots$&$\displaystyle\ddots$&$\displaystyle\ddots$&$\displaystyle\ddots$&$\displaystyle\ddots$&$\displaystyle\vdots$\\\
$\displaystyle-\frac{C_{1}^{*}}{T-2}$&$\displaystyle-\frac{C_{1}^{*}}{T-2}$&$\displaystyle-\frac{C_{1}^{*}}{T-2}$&$\displaystyle\ddots$&$\displaystyle
1$&$\displaystyle-\frac{C_{1}^{*}}{T-1}$&$\displaystyle-\frac{C_{1}^{*}}{T}$\\\
$\displaystyle-\frac{C_{1}^{*}}{T-1}$&$\displaystyle-\frac{C_{1}^{*}}{T-1}$&$\displaystyle-\frac{C_{1}^{*}}{T-1}$&$\displaystyle\ddots$&$\displaystyle-\frac{C_{1}^{*}}{T-1}$&$\displaystyle
1$&$\displaystyle-\frac{C_{1}^{*}}{T}$\\\
$\displaystyle-\frac{C_{1}^{*}}{T}$&$\displaystyle-\frac{C_{1}^{*}}{T}$&$\displaystyle-\frac{C_{1}^{*}}{T}$&$\displaystyle\cdots$&$\displaystyle-\frac{C_{1}^{*}}{T}$&$\displaystyle-\frac{C_{1}^{*}}{T}$&$\displaystyle
1$\end{tabular}\<EMAIL_ADDRESS>(13)
$\displaystyle\mathbf{b}_{[t^{\dagger},T],r^{\dagger}}(\theta^{*})$
$\displaystyle={\left[\centering\begin{tabular}[]{ccccccc}$\displaystyle
C_{1}^{*}r^{\dagger}+C_{2}^{*}$&$\displaystyle\frac{C_{1}^{*}t^{\dagger}r^{\dagger}}{t^{\dagger}+1}+C_{2}^{*}$&$\displaystyle\frac{C_{1}^{*}t^{\dagger}r^{\dagger}}{t^{\dagger}+2}+C_{2}^{*}$&$\displaystyle\ldots$&$\displaystyle\frac{C_{1}^{*}t^{\dagger}r^{\dagger}}{T-1}+C_{2}^{*}$&$\displaystyle\frac{C_{1}^{*}t^{\dagger}r^{\dagger}}{T}+C_{2}^{*}$\end{tabular}\<EMAIL_ADDRESS>
So if we pin down the time round $t^{\dagger}$ and the reference price
$r^{\dagger}$ at this time round, then the optimal price sequence for the
remaining times $(p_{t}^{*})_{t\in[t^{\dagger},T]}$, which satisfies the
condition (12), must also be the solution to the linear system
$\bm{A}_{[t^{\dagger},T]}(\theta^{*})\mathbf{p}=\mathbf{b}_{[t^{\dagger},T],r^{\dagger}}(\theta^{*})$.
Recall that by Theorem 1, we know optimal pricing policy must be a markdown
pricing policy, by Proposition 2, the reference price $r^{\dagger}$ satisfies
$r^{\dagger}=\frac{r+\bar{p}(t^{\dagger}-1)}{t^{\dagger}}$. Thus, to solve the
optimal pricing policy $(p_{t}^{*})_{t\in[T]}$, it suffices to determine the
time round $t^{\dagger}$. Recall that by Theorem 1, we know optimal pricing
policy must be a markdown pricing policy. Thus, the time round $t^{\dagger}$
is smallest time index such that the solution
$\bm{A}_{[t,T]}(\theta^{*})\mathbf{p}=\mathbf{b}_{[t,T],\frac{r+(t-1)\bar{p}}{t}}(\theta^{*})$
is a feasible solution in $[0,\bar{p}]^{T-t+1}$. That is,

$\displaystyle
t^{\dagger}\leftarrow\min\left\\{t\in[T]:\mathbf{p}\in[0,\bar{p}]^{T-t+1}\text{
s.t. }\mathbf{p}\text{ solves
}\bm{A}_{[t,T]}(\theta^{*})\mathbf{p}=\mathbf{b}_{[t,T],r_{t}}(\theta^{*}),r_{t}=\frac{r+(t-1)\bar{p}}{t}\right\\}$

With the above observation, we can have a binary search algorithm to pin down
the time round $t^{\dagger}$. We summarize our algorithm as in Algorithm 3. ∎

##  Appendix B Missing Algorithms in Section 4

1:Input: Current time step $t$, the reference price $r_{t}$ for this time $t$,
and a target reference price $r$

2:if $r_{t}<r$ then

3: Let
$N(t,r_{t},r)\triangleq\min\\{N\in\mathbb{N}:(t+N+1)r-tr_{t}-N\bar{p}\in(0,\bar{p})\\}$.

4: Keep setting the price $\bar{p}$ with $N(t,r_{t},r)$ rounds and then set
the price $(t+N(t,r_{t},r)+1)r-tr_{t}-N(t,r_{t},r)\bar{p}$ for $1$ round.

5: Return $N(t,r_{t},r)+1$.

6:else if $r_{t}>r$ then

7: Let
$N(t,r_{t},r)\triangleq\min\\{N\in\mathbb{N}:(t+N+1)r-tr_{t}\in(0,\bar{p})\\}$.

8: Keep setting the price $0$ with $N(t,r_{t},r)$ rounds and then set the
price $(t+N(t,r_{t},r)+1)r-tr_{t}$ for $1$ round.

9: Return $N(t,r_{t},r)+1$.

10:else

11: Return $0$.

12:end if

Algorithm 4 $\mathsf{ResetRef}(t,r_{t},r)$: Reset to the target reference
price

##  Appendix C Missing Proofs in Section 5

###  C.1 Proof for Section C.1

See 4

###### Proof of Proposition 4.

Our lower bound proof is based on the proof of Theorem $1$ in Keskin and
Zeevi, (2014) with certain necessary modifications. We first show that all
instances in $\mathcal{I}$ satisfy 2.1. Notice that this assumption implies

$\displaystyle\frac{b}{2a}<\bar{p}\leq\frac{b}{a}~{}.$

Since $b\equiv 1$, above condition implies that
$\frac{1}{2\bar{p}}<a\leq\frac{1}{\bar{p}}$. By construction, we know
$a\in[\frac{3}{4\bar{p}},\frac{1}{\bar{p}}]$ for all $I\in\mathcal{I}$. Thus
given $\bar{p}\geq 1$, all instances $I\in\mathcal{I}$ satisfy 2.1.

Given an instance $I\in\mathcal{I}$, let $p(I)=\frac{b}{2a}=\frac{1}{2a}$. Let
$\Lambda$ be an absolutely continuous density on $\mathcal{I}$, taking
positive values on the interior of $\mathcal{I}$ and zero on its boundary.
Then, the multivariate van Trees inequality (cf. Gill and Levit, 1995) implies
that

$\displaystyle\mathbb{E}_{\Lambda}\\!\left[{\mathbb{E}^{\pi_{\mathsf{ALG}}}_{I}\\!\left[{\left(p_{t}-p(I)\right)^{2}}\right]}\right]\geq\frac{\left(\mathbb{E}_{\Lambda}\\!\left[{C(I)\left(\frac{\partial
p(I)}{\partial
I}\right)^{\top}}\right]\right)^{2}}{\mathbb{E}_{\Lambda}\\!\left[{C(I)\mathcal{F}_{t-1}^{\pi_{\mathsf{ALG}}}(I)C(I)^{\top}}\right]+\widetilde{\mathcal{F}}(\Lambda)}~{}.$
(14)

where $\widetilde{\mathcal{F}}(\Lambda)$ is the Fisher information for the
density $\Lambda$, and $\mathbb{E}_{\Lambda}\\!\left[{\cdot}\right]$ is the
expectation operator with respect to density $\Lambda$. Notice that for all
$I=(a,b)\in\mathcal{I}$, we have $C(I)\left(\frac{\partial p(I)}{\partial
I}\right)^{\top}=-\frac{p(I)}{2a}$, and
$\mathcal{F}_{t-1}^{\pi_{\mathsf{ALG}}}(I)=\nicefrac{{\mathbb{E}^{\pi_{\mathsf{ALG}}}_{I}\\!\left[{\mathcal{J}_{t-1}}\right]}}{{\sigma^{2}}}$
where

$\displaystyle\mathcal{J}_{t}\triangleq\left[\begin{array}[]{cc}t&\sum_{s=1}^{t}p_{s}^{\top}\\\
\sum_{s=1}^{t}p_{s}&\sum_{s=1}^{t}p_{s}p_{s}^{\top}\end{array}\right]$

denotes the empirical Fisher information, $(p_{s})_{s\geq 1}$ are the pricing
choices realized from algorithm $\pi_{\mathsf{ALG}}$. Using these identities
and adding up inequality (14) for $t=2,\ldots,T$, we obtain

$\displaystyle\sum_{t=2}^{T}\mathbb{E}_{\Lambda}\\!\left[{\mathbb{E}^{\pi_{\mathsf{ALG}}}_{I}\\!\left[{\left(p_{t}-p(I)\right)^{2}}\right]}\right]\geq\sum_{t=2}^{T}\frac{\left(\mathbb{E}_{\Lambda}\\!\left[{\frac{p(I)}{2a}}\right]\right)^{2}}{\sigma^{-2}\mathbb{E}_{\Lambda}\\!\left[{C(I)\mathbb{E}^{\pi_{\mathsf{ALG}}}_{I}\\!\left[{\mathcal{J}_{t-1}}\right]C(I)^{\top}}\right]+\widetilde{\mathcal{F}}(\Lambda)}~{}.$

Since $\mathbb{E}_{\Lambda}\\!\left[{\cdot}\right]$ is a monotone operator, we
further have

$\displaystyle\sup_{I\in\mathcal{I}}\sum_{t=2}^{T}\mathbb{E}^{\pi_{\mathsf{ALG}}}_{I}\\!\left[{\left(p_{t}-p(I)\right)^{2}}\right]\geq\sum_{t=2}^{T}\frac{\inf_{I\in\mathcal{I}}\left(\frac{p(I)}{2a}\right)^{2}}{\sup_{I\in\mathcal{I}}\sigma^{-2}C(I)\mathbb{E}^{\pi_{\mathsf{ALG}}}_{I}\\!\left[{\mathcal{J}_{t-1}}\right]C(I)^{\top}+\widetilde{\mathcal{F}}(\Lambda)}~{}.$
(15)

Note due to the fact that $C(I)=[-p(I)1]$, we have
$C(I)\mathbb{E}^{\pi_{\mathsf{ALG}}}_{I}\\!\left[{\mathcal{J}_{t-1}}\right]C(I)^{\top}=\sum_{s=1}^{t-1}\mathbb{E}^{\pi_{\mathsf{ALG}}}_{I}\\!\left[{(p_{s}-p(I))^{2}}\right]$.
Thus, (15) implies that

$\displaystyle\sup_{I\in\mathcal{I}}\sum_{t=2}^{T}\mathbb{E}^{\pi_{\mathsf{ALG}}}_{I}\\!\left[{\left(p_{t}-p(I)\right)^{2}}\right]\geq\sum_{t=2}^{T}\frac{\sigma^{2}\inf_{I\in\mathcal{I}}\left(\frac{p(I)}{2a}\right)^{2}}{\sup_{I\in\mathcal{I}}\sum_{s=1}^{t-1}\mathbb{E}^{\pi_{\mathsf{ALG}}}_{I}\\!\left[{(p_{s}-p(I))^{2}}\right]+\sigma^{2}\widetilde{\mathcal{F}}(\Lambda)}~{}.$

Recall the definition of our regret, we then have

$\displaystyle\text{\bf
REG}^{\pi_{\mathsf{ALG}}}\\!\left[{T,I}\right]=\sum_{t=1}^{T}\mathbb{E}^{\pi_{\mathsf{ALG}}}_{I}\\!\left[{p(I)(b-ap(I))-p_{t}(b-ap_{t})}\right]=a\sum_{t=1}^{T}\mathbb{E}^{\pi_{\mathsf{ALG}}}_{I}\\!\left[{\left(p(I)-p_{t}\right)^{2}}\right]~{}.$

Thus,

$\displaystyle\sup_{I\in\mathcal{I}}\text{\bf
REG}^{\pi_{\mathsf{ALG}}}\\!\left[{T,I}\right]$
$\displaystyle=\sup_{I\in\mathcal{I}}a\sum_{t=1}^{T}\mathbb{E}^{\pi_{\mathsf{ALG}}}_{I}\\!\left[{\left(p(I)-p_{t}\right)^{2}}\right]$
$\displaystyle\geq
a_{\min}\sup_{I\in\mathcal{I}}\sum_{t=1}^{T}\mathbb{E}^{\pi_{\mathsf{ALG}}}_{I}\\!\left[{\left(p(I)-p_{t}\right)^{2}}\right]$
$\displaystyle\geq
a_{\min}\sum_{t=2}^{T}\frac{\sigma^{2}\inf_{I\in\mathcal{I}}\left(\frac{p(I)}{2a}\right)^{2}}{\sup_{I\in\mathcal{I}}\sum_{s=1}^{t-1}\mathbb{E}^{\pi_{\mathsf{ALG}}}_{I}\\!\left[{(p_{s}-p(I))^{2}}\right]+\sigma^{2}\widetilde{\mathcal{F}}(\Lambda)}$
$\displaystyle\geq
a_{\min}^{2}\sum_{t=2}^{T}\frac{\sigma^{2}\inf_{I\in\mathcal{I}}\left(\frac{p(I)}{2a}\right)^{2}}{\sup_{I\in\mathcal{I}}\text{\bf
REG}^{\pi_{\mathsf{ALG}}}\\!\left[{t-1,I}\right]+a_{\min}\sigma^{2}\widetilde{\mathcal{F}}(\Lambda)}$
$\displaystyle\geq
a_{\min}^{2}\frac{(T-1)\sigma^{2}\inf_{I\in\mathcal{I}}\left(\frac{p(I)}{2a}\right)^{2}}{\sup_{I\in\mathcal{I}}\text{\bf
REG}^{\pi_{\mathsf{ALG}}}\\!\left[{T,I}\right]+a_{\min}\sigma^{2}\widetilde{\mathcal{F}}(\Lambda)}$
$\displaystyle=\frac{a_{\min}^{2}(T-1)\sigma^{2}\inf_{I\in\mathcal{I}}\left(\frac{p(I)}{2a}\right)^{2}}{\sup_{I\in\mathcal{I}}\text{\bf
REG}^{\pi_{\mathsf{ALG}}}\\!\left[{T,I}\right]\left(1+\frac{a_{\min}\sigma^{2}\widetilde{\mathcal{F}}(\Lambda)}{\sup_{I\in\mathcal{I}}\text{\bf