Learning to Price Supply Chain Contracts against a Learning Retailer

Xuejun Zhao Krannert School of Business, Purdue University
<EMAIL_ADDRESS>
Ruihao Zhu SC Johnson College of Business, Cornell University
<EMAIL_ADDRESS>
William Haskell Krannert School of Business, Purdue University
<EMAIL_ADDRESS>
The rise of big data analytics has automated the decision making of companies
and increased supply chain agility. In this paper, we study the supply chain
contract design problem faced by a data-driven supplier who needs to respond
to the inventory decisions of the downstream retailer. Both the supplier and
the retailer are uncertain about the market demand and need to learn about it
sequentially. The goal for the supplier is to develop data-driven pricing
policies with sublinear regret bounds under a wide range of retailer’s
inventory policies for a fixed time horizon.

To capture the dynamics induced by the retailer’s learning policy, we first
make a connection to nonstationary online learning by following the notion of
variation budget. The variation budget quantifies the impact of the retailer’s
learning strategy on the supplier’s decision-making environment. We then
propose dynamic pricing policies for the supplier for both discrete and
continuous demand. We also note that our proposed pricing policy only requires
access to the support of the demand distribution, but critically, does not
require the supplier to have any prior knowledge about the retailer’s learning
policy or the demand realizations. We examine several well known data-driven
policies for the retailer, including sample average approximation,
distributionally robust optimization, and parametric approaches, and show that
our pricing policies lead to sublinear regret bounds in all these cases.

At the managerial level, we answer affirmatively that there is a pricing
policy with a sublinear regret bound under a wide range of retailer’s learning
policies, even though she faces a learning retailer and an unknown demand
distribution. Our work also provides a novel perspective in data-driven
operations management where the principal has to learn to react to the
learning policies employed by other agents in the system.

online learning, supply chain contracts, data analytics

##  1 Introduction

Rapid development of big data analytics has enabled data-driven supply chain
management for companies in different industries. According to a survey
conducted by EY Americas (2020) with 212 supply chain leaders from varying
sections and company sizes, around $18\%$ of the respondents have already
pivoted to big data analytics and $61\%$ of the respondents plan to adopt big
data analytics in the next 12-36 months. Big data analytics has also automated
the decision-making of companies, and strengthened the agility of the upstream
supply chain (e.g., suppliers) to respond to downstream (e.g., retailers and
market demand) changes. Motivated by this observation, we study the supply
chain contract design problem faced by a data-driven supplier that needs to
respond to a downstream retailer who is uncertain about market demand and
employs big data analytics tools to make inventory decisions.

We study this problem through the lens of the supplier. The supplier (she)
sells a product to a retailer (he) who faces uncertain market demand over a
selling horizon of $T$ periods, where the supplier sets a wholesale price
(i.e., contract) for the retailer in each period. Then, the retailer makes a
decision on the order quantity accordingly, which also determines the
supplier’s profit. The retailer does not know the market demand distribution
in advance, and may employ a data-driven inventory learning policy that is
_unknown_ to the supplier. The supplier does not know the market demand
distribution either, and she has to sequentially balance the trade-off between
exploring the retailer’s response to different prices and exploiting
profitable prices found so far. This situation may arise in many scenarios.
For example, when selling newly introduced products, both the supplier and the
retailer are uncertain about the demand of the product and thus have to learn
it on the fly.

The supplier’s goal is to choose the price to maximize her total profit over
the selling horizon. We measure her performance through the notion of regret
with respect to a clairvoyant benchmark who has the same information as the
retailer (and can predict his orders) and thus chooses the optimal wholesale
prices in each period. This problem is challenging due to the following two
sources of uncertainty:

  1. 1.

Unknown Market Demand: In the full information case, when both the supplier
and retailer have full knowledge about the market demand distribution, the
supplier can directly infer the ordering decisions from the retailer using
knowledge about the market demand (assuming the retailer is profit-driven).
However, when neither the supplier nor retailer has information about the
market demand, the retailer has to learn the demand distribution over time,
and the supplier cannot directly infer the retailer’s ordering decisions in
each period without knowing the retailer’s observations and inventory learning
policy.

  2. 2.

Uncertain Retailer Inventory Learning Policy: In addition, uncertainty on the
retailer’s inventory learning policy makes it particularly challenging to
optimize the supplier’s profit function, since the retailer can employ a
variety of learning policies, and each policy is a mapping from the
information received by the retailer to an order quantity. That is, the
retailer makes inventory decisions as a response to the supplier’s wholesale
prices, the observed demand realizations, and his particular inventory
learning policy. In this case, even if the supplier had known the market
demand (yet the retailer still does not know it), inferring the retailer’s
learning policy from his ordering decisions is not an easy task.

To this end, we ask the following main question: Does there exist a pricing
policy for the supplier with a sublinear regret bound that does not require
knowledge of the specific data-driven inventory learning policy used by the
retailer? If there is such a pricing policy with a sublinear regret bound,
then this policy will have no optimality gap with respect to a clairvoyant
benchmark’s profit asymptotically.

The setting in our paper is novel as well as relevant. The data-driven
newsvendor has been studied extensively in the OM literature, but the impact
of a data-driven newsvendor on its upstream supplier’s decisions has not yet
been thoroughly investigated. We approach the supplier’s problem by
formulating it as a non-stationary online optimization problem. However, the
non-stationarity in our supplier’s problem is different than in conventional
single agent non-stationary online problems. In our problem, the non-
stationarity lies in the retailer’s inventory decisions which depend on his
inventory learning policy and the information he receives. In our case, the
non-stationarity of the problem is bounded sublinearly in $T$, but the non-
stationarity of the retailer’s decisions is not necessarily bounded
sublinearly in $T$. In addition, the supplier’s online problem has a
continuous decision set instead of a finite one. The literature has studied
non-stationary online problems with infinitely many decisions, but with the
assumption that the objective function is strongly convex or at least
continuous. However, we will see that the supplier’s profit function in our
problem is not necessarily convex/concave or even continuous. Due to these
challenges, we need a novel data-driven policy to achieve sublinear regret for
the supplier.

###  1.1 Our Contributions

In this paper, we provide an affirmative answer to our main question by giving
a data-driven pricing policy that achieves sublinear regret. We emphasize that
our policy does not require the supplier to have any knowledge on the past
demand realizations or the retailer’s inventory policy. Instead, she only uses
her past interactions with the retailer, and knowledge of the support of the
demand distribution.

We propose the supplier’s policies for both discrete and continuous demand
distributions. When the demand distribution is discrete, the supplier’s profit
function admits a special structure that our policy exploits. When the demand
distribution is continuous, this special structure vanishes, but we give a
policy that approximates the supplier’s profit function and still attains
sublinear regret. The details of our contributions in this paper are
summarized below:

  1. 1.

Note that the retailer’s ordering decisions depend on the supplier’s wholesale
prices and also on the data-driven inventory learning policies used, this can
create non-stationarity in the supplier’s decision environment. To capture
this effect, we follow the notion of variation budget in the non-stationary
bandit (see Section 1.2) to quantify the difficulty of the supplier’s learning
problem. With that, even if the retailer switches policies dynamically and/or
use a mixture of them, we can encapsulate the impact through the variation
budget. Different than prior literature on non-stationary bandits (Besbes et
al. 2014a, Keskin et al. 2021, Cheung et al. 2021), we define the variation
budget in terms of the Kolmogorov distance between the distributions that
determine the retailer’s inventory decisions. Here, the use of Kolmogorov
distance turns out to be natural as it conveniently translates the variation
on retailer’s inventory decisions to the variation on the supplier’s profit
functions, and enables the development of pricing policies with provable
regret bound for our setting. We also remark that Kolmogorov distance can be
upper bounded by many other commonly used distance metrics or divergences,
e.g., total variation distance, relative entropy, Helinger distance,
Wasserstein distance, etc. (Gibbs and Su 2002).

  2. 2.

We propose a pricing policy $\pi_{\text{LUNA}}$ for the supplier that achieves
sublinear regret when the market demand distribution is discrete. In this
case, the supplier’s profit function is discontinuous and non-stationary. In
spite of this, we identify special structure in the supplier’s profit function
to resolve the challenge. We emphasize that our policy does not require any
knowledge of the variation budget or the retailer’s inventory learning policy.
Instead, our policy automatically adjusts to a wide range of retailer policies
and variation budgets.

  3. 3.

When the market demand distribution is continuous, the unique structure in the
supplier’s profit function vanishes and one cannot directly apply
$\pi_{\text{LUNA}}$. To overcome this challenge, we work on an approximation
of the supplier’s profit function. At a high level, our policy
$\pi_{\text{LUNAC}}$ for continuous demand is based on an approximate profit
function for the supplier which inherits the desired structure. Then, our
previous policy $\pi_{\text{LUNA}}$ for discrete demand can be employed as a
sub-routine for $\pi_{\text{LUNAC}}$.

  4. 4.

We show that our proposed pricing policy leads to sublinear regret bounds for
the supplier under a wide range of retailer inventory policies. We examine:
(i) sample average approximation (SAA); (ii) distributionally robust
optimization (DRO); and (iii) some parametric approaches (maximum likelihood
estimation (MLE), operational statistics, and Bayesian estimation). Under
these policies, we compute the respective variation budgets and derive the
corresponding regret bounds.

  5. 5.

We also conduct numerical experiments to compare our pricing policy with
several algorithms from the literature on non-stationary bandits, including
the Exp3.S algorithm by Besbes et al. (2014a), the deterministic non-
stationary bandit algorithm proposed by Karnin and Anava (2016), and the
Master+UCB1 algorithm proposed by Wei and Luo (2021) where each price is
treated as an arm to pull. We show that our pricing policy has the best
performance among all these benchmarks. Our results demonstrate the importance
of exploiting structural properties in data-driven operations.

  6. 6.

At the managerial level, we establish that there is an asymptotically optimal
policy for the supplier even though she faces a learning retailer and an
unknown (possibly non-stationary) demand distribution More generally, our work
shows the importance of data-driven operations management where the principal
has to learn to react to the learning policies employed by other agents in the
system. These results also further support the use of wholesale price
contracts in practice.

###  1.2 Related Works

Contract Design under Uncertainty and MAB: Supply chain contract design is a
longstanding topic, we refer to the survey by Cachon (2003). In particular,
there is an increasing interest in studying contract design under uncertainty
(Fu et al. 2018, Yu and Kong 2020). We consider the design of wholesale price
contracts. There have been efforts in the literature to justify the prevalence
of wholesale price contracts in practice (Perakis and Roels 2007, Kalkanci et
al. 2011, Yu and Kong 2020). They suggest that wholesale price contracts are
arguably the most natural form of contract for us to investigate when faced
with a learning retailer.

Our work lies at the interface between contract design and multi-armed bandit
(MAB) problems (see Bubeck et al. (2011) and Lattimore and Szepesvári (2020)).
MAB problems have also been extensively studied. In particular, they have been
used to model contract design problems. For example, Ho et al. (2016) study
repeated principle-agent interactions where the principle offers a contract to
induce the efforts of i.i.d. arriving agents.

Dynamic Pricing and Inventory Control: Dynamic pricing and online revenue
management has been studied widely in the OM literature (Broder and
Rusmevichientong 2012, Ferreira et al. 2018, Keskin and Birge 2019, den Boer
and Keskin 2020, 2022, Ban and Keskin 2021, Keskin et al. 2022, Cheung et al.
2017, Jia et al. 2022). Also see Chen and Chen (2015) for an overview of
studies on dynamic pricing. More recently, a line of works also integrate
inventory control into pricing decisions (see, e.g., Chen et al. (2022b, a)
and references therein). In this stream of literature, the decision maker is
unknown about the demand function, and has to balance the trade-off of
learning and earning while dynamically adjusting the pricing and/or inventory
decisions.

Almost all the above works focus exclusively on the stationary demand
environment, but in our case, due to the retailer’s learning strategy, the
decision environment could be dynamically changing. In this regime, Besbes and
Zeevi (2011), Keskin and Zeevi (2017), Keskin et al. (2022) study dynamic
pricing in a non-stationary environment. Keskin et al. (2021) study the online
non-stationary newsvendor problem when the $L_{2}-$norm of the variation in
mean demand is bounded. Keskin et al. (2022) study a dynamic joint inventory
and pricing problem with perishable products where the price-demand
relationship is piecewise stationary. They derive regret bound of
$\tilde{O}(T^{2/3}(\log(T))^{1/2})$ for nonparametric noise distributions and
$\tilde{O}(T^{1/2}(\log(T)))$ for parametric noise distributions,
respectively.

Unlike the previous studies whose goals are to learn the unkown demand
functions, the learning in our problem is with respect to the retailer’s data-
driven inventory learning policies. Furthermore, the non-stationarity in our
problem is mostly driven by the learning policies of the self-interested
retailer.

Non-stationary Online Learning: Many bandit problems are inherently non-
stationary. One approach is to model the non-stationarity as a drifting
environment, where some metric is used to measure the variation of the
environments. The regret analysis is done by restricting to environments with
bounded variation (Besbes et al. 2014b, 2015, Wei et al. 2016, Wei and
Srivatsva 2018, Karnin and Anava 2016, Luo et al. 2018, Cheung et al. 2019,
2021). Different metrics have been considered, which result in different
regret bounds. Besbes et al. (2014b) study a $K$-armed bandit problem where
the mean reward of the arms is changing. They derive a near-optimal policy
with regret $\tilde{O}((KV)^{1/3}T^{2/3})$ when the supremum norm of the
change in mean rewards is bounded by a known variation budget $V$. Besbes et
al. (2015) study non-stationary stochastic optimization problems where the
cost function is convex and the supremum norm of the deviations in the cost
function in each period is bounded. Chen et al. (2019a) extends the previous
work to use the $L_{p,q}-$variational functional, which better reflects local
spatial and temporal changes in the objective cost functions. These works
mostly require the DM to know the variation budget. In order to relax this
requirement, Karnin and Anava (2016) propose a restarting algorithm for the
$K-$armed bandit problem that restarts whenever a large variation in the
environment has been detected by a statistical test.

We build our supplier pricing policy based on the deterministic bandit setting
in Karnin and Anava (2016). Their algorithm is epoch-based where each epoch
consists of an exploration and an exploitation phase. In the exploration
phase, the algorithm samples from each arm once and observes the noiseless
bandit reward. In the exploitation phase, the algorithm randomly selects an
arm to sample, where the sampling distribution is calibrated to balance the
trade-off between exploration and exploitation. If the variation of the
sampled arm is detected to be above some detection threshold
$\mathcal{OV}_{B}$, then the algorithm starts the next epoch. Otherwise, the
algorithm continues the exploitation phase. This algorithm relaxes the
assumption that the DM knows the variation budget by sequentially decreasing
the detection threshold $\mathcal{OV}_{B}$ in the exploitation phase.

In another approach, one can model non-stationarity in a piecewise fashion
where the bandit remains stationary in each interval and varies across
intervals. The total number of intervals is bounded by $S$, but the start and
end time of each interval is unknown to the DM. Some algorithms have been
proposed for known $S$ (Auer et al. 2002, Garivier and Moulines 2011, Liu et
al. 2018, Luo et al. 2018, Cao et al. 2019) and unknown $S$ (Karnin and Anava
2016, Luo et al. 2018, Auer et al. 2018, 2019, Keskin et al. 2022, Chen et al.
2019b, Besson and Kaufmann 2019). We note the difference between this approach
for non-stationarity and the first one based on a variation budget. In the
first approach, only a constraint on the total variation is imposed and the
total number of intervals (where the bandit is stationary) can be linear in
$T$ as long as the total variation is bounded. On the other hand, the second
approach requires the number of intervals to be bounded, but the variation
within intervals can be substantial. Nevertheless, Wei and Luo (2021)
generalize many reinforcement learning algorithms that work optimally in
stationary environments to work optimally in non-stationary environments
without any knowledge of the variation budget $V$ or the total number of
changes $S$. We also refer to Zhou et al. (2021), Auer et al. (2008) for a
discussion of the Markovian bandit and Chen et al. (2020) for bandits with
seasonality.

The non-stationary bandit is especially relevant to revenue management and
dynamic pricing. Cheung et al. (2019, 2021) propose a sliding window upper
confidence bound algorithm for the linear bandit where the Euclidean norm of
the variation in the cost coefficients is upper bounded (but the upper bound
is unknown to the DM). Their results cover advertisement allocation, dynamic
pricing, and traffic network routing.

Multi-Agent Learning: There is a rich literature on multi-agent learning,
particularly focusing on online simultaneous games and online Stackelberg
games. See Zhang et al. (2021) for an overview on multi-agent reinforment
learning. In particular, Birge et al. (2021) consider a platform on which
multiple sellers offer products, where sellers’ pricing decisions are
incentivized by the platform’s contract, and both the sellers and the platform
do not have full knowledge about the demand price relationship. Unlike ours
where the retailer has more information on market demand than the supplier and
the latter needs to leverage her interactions with the former to learn the
market demand and maximize profit, they focus on the information advantage of
the platform over the sellers and study whether and when the platform should
release its information advantage.

###  1.3 Organization

This work is organized as follows. In Section 2, we introduce the problem
formulation which consists of the supplier’s dynamic pricing problem and the
class of retailer inventory learning policies. In Section 3, we present a
preliminary analysis of the regret of the supplier’s pricing policy when the
retailer has full knowledge about the demand distribution. Then, in Section 4
we develop the supplier’s pricing policy and its regret upper bound under a
learning retailer. We first develop the pricing policy for discrete
distributions and then extend it to continuous distributions. In Section 5, we
study several examples of retailer inventory policies under which our pricing
policy achieves sublinear regret. In Section 6 we conduct numerical
experiments and we conclude the paper in Section 7.

##  2 Problem Formulation

Throughout, we let $[N]\triangleq\\{1,\ldots,N\\}$ be the running index for
any integer $N\geq 1$. We adopt the asymptotic notations $O(\cdot)$,
$o(\cdot)$, $\Omega(\cdot)$, and $\Theta(\cdot)$ (Cormen et al. 2022). When
logarithmic factors are omitted, we use $\tilde{O}(\cdot)$,
$\tilde{o}(\cdot)$, $\tilde{\Omega}(\cdot)$, and $\tilde{\Theta}(\cdot)$. We
write ‘max’ instead of ‘sup’ and ‘min’ instead of ‘inf’. When the optimal
solution to the optimization problem does not exist, an “optimal solution”
means an $\epsilon-$optimal solution for $\epsilon>0$ arbitrarily small.

We consider a wholesale price contract between one supplier (she) and one
retailer (he) for a single product, where the retailer faces random demand.
Let $c$ be the supplier’s unit production cost and $s$ be the retailer’s unit
selling price. We use $\mathcal{W}=[0,s]$ to denote the set of admissible
wholesale prices, i.e., the supplier cannot sell for more than the retailer
selling price (we extend to the case where the supplier’s set of admissible
decisions $\mathcal{W}$ has finite cardinality in the appendix). Notice that
the supplier will gain a negative profit if she sells for less than her
production cost $c$, however we allow this possibility since occasionally
pricing for less than $c$ may help the supplier explore.

The supplier and retailer interact over a series of time periods indexed by
$t\in[T]$ with $T\geq 1$. Let $\xi_{t}$ be the random demand in period
$t\in[T]$ with support $\Xi\subset\mathbb{R}_{+}$. Let $\mathcal{P}(\Xi)$ be
the set of probability distributions on $\Xi$. We denote the cumulative
distribution function (CDF) of demand $\xi_{t}$ as $F_{t}\in\mathcal{P}(\Xi)$
and whose density is $f_{t}$ (if it exists). We introduce the shorthand
$F_{1\mathrel{\mathop{\mathchar 58\relax}}t}\triangleq(F_{i})^{t}_{i=1}$ for
$t\in[T]$ for the sequences of true market demand distributions.

In each period $t$, the supplier first offers the retailer the wholesale price
$w_{t}\in\mathcal{W}$. Then, the retailer observes $w_{t}$, determines his
order quantity $q_{t}$, and the supplier earns profit
$\varphi(w_{t};q_{t})\triangleq(w_{t}-c)q_{t}$. Finally, demand $\xi_{t}$ is
realized and the retailer earns profit $R(q_{t};w_{t},\xi_{t})\triangleq
s\min\\{q_{t},\xi_{t}\\}-w_{t}q_{t}$.

The supplier only has access to past wholesale prices and corresponding
retailer order quantities. We define
$\mathcal{G}_{t}\triangleq\left\\{(w_{i},q_{i})\right\\}_{i=1}^{t}$ to be the
history of prices and order quantities by the end of period $t$ (we let
$\mathcal{G}_{0}\triangleq\emptyset$). The supplier’s (possibly randomized)
pricing policy is a sequence of mappings from $\mathcal{G}_{t}$ to the set of
probability distributions on $\mathcal{W}$ (denoted
$\mathcal{P}(\mathcal{W})$). We denote the supplier’s (possibly randomized)
pricing policy by $\pi\triangleq(\pi_{t})^{T}_{t=1}$ where
$\pi_{1}\in\mathcal{P}(\mathcal{W})$ and $\pi_{t}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{G}_{t-1}\rightarrow\mathcal{P}(\mathcal{W})$ for all $t\geq
2$. The wholesale prices under $\pi$ then follow:

$\displaystyle w_{1}\sim\pi_{1},$ (1a) $\displaystyle
w_{t}\sim\pi_{t}\left(\mathcal{G}_{t-1}\right),$ $\displaystyle\quad\forall
t\geq 2.$ (1b)

Now we characterize the retailer’s policy. Let
$\mathcal{H}_{t}\triangleq\left\\{(w_{i},q_{i},\xi_{i})\right\\}^{t}_{i=1}$ be
the retailer’s information by the end of period $t$ which consists of the
history of wholesale prices, order quantities, and demand realizations up to
period $t$ (we simply let $\mathcal{H}_{0}\triangleq\emptyset$). Then, the
retailer has access to information $\mathcal{H}_{t-1}\cup\\{w_{t}\\}$ right
before his ordering decision is made. We let $\mu=(\mu_{t})^{T}_{t=1}$ denote
the retailer’s (possibly randomized) inventory learning policy, where
$\mu_{1}\mathrel{\mathop{\mathchar 58\relax}}w_{1}\rightarrow\mathcal{P}(\Xi)$
and $\mu_{t}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{H}_{t-1}\cup\\{w_{t}\\}\rightarrow\mathcal{P}(\Xi)$ for
$t\in[2,T]$. The retailer’s order quantities under $\mu$ are then determined
by:

$\displaystyle q_{1}^{\mu}\sim\mu_{1}(w_{1}),$ (2a) $\displaystyle
q_{t}^{\mu}\sim\mu_{t}\left(\mathcal{H}_{t-1}\cup\\{w_{t}\\}\right),$
$\displaystyle\quad\forall t\geq 2.$ (2b)

We write $q_{t}^{\mu}(w_{t};\mathcal{H}_{t-1})$ to denote the retailer’s
period $t\in[T]$ response to wholesale price $w_{t}$ under policy $\mu$.

We measure the performance of the supplier’s pricing policy $\pi$ in terms of
its dynamic regret. We use a clairvoyant benchmark who can predict the
retailer’s true order quantity given any wholesale price, and the clairvoyant
does not necessarily know the true market demand distribution. For example, if
the benchmark has the demand data received by the retailer and knows the
policy in use by the retailer, then it can perfectly predict the retailer’s
order quantity given any wholesale price.

Since the retailer’s policy is unknown, we identify a class $\mathcal{M}$
(which depends on $T$ and other model parameters, we will specify
$\mathcal{M}$ shortly) of reasonable retailer policies. If the retailer’s
policy is allowed to be completely arbitrary, then we cannot always expect to
get a sublinear regret for the supplier. We then consider the supplier’s
worst-case regret over policies in $\mu\in\mathcal{M}$. Let

$w^{*}_{t}\in\arg\max_{w\in\mathcal{W}}(w-c)q_{t}^{\mu}(w;\mathcal{H}_{t-1})$
(3)

be the benchmark’s optimal wholesale price with full knowledge of how the
retailer will respond under $q_{t}^{\mu}$. Then, the regret in period $t$ when
the supplier prices at $w_{t}$ is
$(w^{*}_{t}-c)q_{t}^{\mu}(w^{*}_{t};\mathcal{H}_{t-1})-(w_{t}-c)q_{t}^{\mu}(w_{t};\mathcal{H}_{t-1})$.
The overall dynamic regret over the entire planning horizon is then:

$\text{Reg}(\pi,T)\triangleq\max_{\mu\in\mathcal{M}}{\mathds{E}}\left[\sum^{T}_{t=1}\left((w^{*}_{t}-c)q_{t}^{\mu}(w^{*}_{t};\mathcal{H}_{t-1})-(w_{t}-c)q_{t}^{\mu}(w_{t};\mathcal{H}_{t-1}\right)\right],$

where the expectation is taken with respect to both the supplier and
retailer’s possibly randomized policies, and the underlying random demand. The
clairvoyant benchmark in the dynamic regret is able to adjust its strategy
dynamically in response to the non-stationarity of the retailer response
functions $q_{t}^{\mu}(\cdot;\mathcal{H}_{t-1})$.

Dynamic regret is a stronger concept than stationary regret. In the definition
of the stationary regret, the clairvoyant benchmark must set the same
wholesale price
$w^{*}\in\arg\max_{w\in\mathcal{W}}\sum^{T}_{t=1}(w-c)q_{t}^{\mu}(w;\mathcal{H}_{t-1})$
for the entire planning horizon and the supplier’s stationary regret is

$\text{Reg}_{stat}(\pi,T)\triangleq\max_{\mu\in\mathcal{M}}{\mathds{E}}\left[\sum^{T}_{t=1}\left((w^{*}-c)q_{t}^{\mu}(w^{*};\mathcal{H}_{t-1})-(w_{t}-c)q_{t}^{\mu}(w_{t};\mathcal{H}_{t-1})\right)\right].$

It is immediate that the stationary regret is always upper bounded by the
dynamic regret.

###  2.1 Retailer Model

Now we present a specific model for how the retailer makes his ordering
decisions. For demand distribution $F\in\mathcal{P}(\Xi)$, given wholesale
price $w$ the retailer’s expected profit from ordering $q$ is
${\mathds{E}}_{F}\left[R(q;w,\xi)\right]$. If the retailer believes the demand
distribution is $F$, then his best response to wholesale price $w$ is to order

$q(w;F)\triangleq\arg\max_{q\geq 0}{\mathds{E}}_{F}[R(q;w,\xi)],$

or equivalently

$q(w;F)=\min\left\\{q\mathrel{\mathop{\mathchar 58\relax}}F(q)\geq
1-w/s\right\\},$ (4)

which maximizes his expected profit with respect to $F$.

In our setting the retailer does not know $F_{1\mathrel{\mathop{\mathchar
58\relax}}T}$, and has to implement some inventory learning policy as
mentioned before. We now characterize $\mu$ by supposing that the retailer’s
ordering decisions are all best responses to a sequence of perceived
distributions.

Let $\mu$ be the retailer’s inventory learning policy. For all $t\in[T]$,
there exists a perceived distribution $\hat{F}_{t}^{\mu}$ that is adapted to
$\mathcal{H}_{t-1}\cup\\{w_{t}\\}$, such that
$q_{t}^{\mu}(w_{t};\mathcal{H}_{t-1})=q(w_{t};\hat{F}_{t}^{\mu})$. We let
$\hat{F}_{1\mathrel{\mathop{\mathchar
58\relax}}t}^{\mu}\triangleq(\hat{F}_{1}^{\mu},\ldots,\hat{F}_{t}^{\mu})$ for
all $t\in[T]$ denote the sequences of perceived distributions. We say a
stationary retailer is one who has full knowledge about the demand
distribution, and the true distribution is stationary
($\hat{F}_{t}^{\mu}=F_{t}\triangleq F_{0}$ for all $t\in[T]$). Otherwise, we
have a learning retailer. A learning retailer introduces non-stationarity into
the supplier’s decision-making environment, even if the true market demand
distribution is stationary.

Assumption 2.1 says that, at any period $t\geq 1$, the retailer’s order
quantity $q(w_{t};\hat{F}_{t}^{\mu})$ is a best response to some data-driven
CDF $\hat{F}_{t}^{\mu}$ that only depends on the information that has been
revealed to the retailer up to period $t$ (i.e., $\mathcal{H}_{t-1}\cup
w_{t}$). In other words, the retailer’s ordering decisions and thus its entire
policy are completely determined by $\hat{F}_{1\mathrel{\mathop{\mathchar
58\relax}}T}^{\mu}$. This assumption is without loss of generality, since
$q^{\mu}_{t}$ must be adapted to $\mathcal{H}_{t-1}\cup w_{t}$ anyway. If we
are given a rule for constructing $q^{\mu}_{t}$ directly from the data, we can
always find $\hat{F}_{t}^{\mu}$ for which $q^{\mu}_{t}$ is the best response.
There may exist more than one $\hat{F}_{t}^{\mu}$ in period $t$ that satisfies
Assumption 2.1.

We also assume that the retailer knows the support of the true sequence of
demand distributions, and thus the retailer will construct $\hat{F}^{\mu}_{t}$
whose support is contained in the support of $F_{t}$. Let $\mu$ be the
retailer’s inventory policy. For all $t\in[T]$, the support of
$\hat{F}^{\mu}_{t}$ is contained in the support of $F_{t}$. In Section 5 we
show that many inventory policies satisfy Assumptions 2.1 and 2.1. For
example, under SAA, the retailer’s perceived distribution is the empirical
distribution of the observed demand samples.

###  2.2 Supplier’s Regret

Since the retailer’s order quantities are fully determined by
$\hat{F}_{1\mathrel{\mathop{\mathchar 58\relax}}T}^{\mu}$, the supplier’s task
of minimizing regret is equivalent to learning
$\hat{F}_{1\mathrel{\mathop{\mathchar 58\relax}}T}^{\mu}$. However, it is well
known that if $\hat{F}_{1\mathrel{\mathop{\mathchar 58\relax}}T}^{\mu}$ can
vary arbitrarily, then there is no pricing policy that achieves sublinear
regret for the supplier. Our main question only makes sense if we restrict the
retailer’s inventory policy (or equivalently, the sequence of
$\hat{F}_{1\mathrel{\mathop{\mathchar 58\relax}}T}^{\mu}$) to belong to a
reasonable class. In this case, we expect the variation in
$\hat{F}_{1\mathrel{\mathop{\mathchar 58\relax}}T}^{\mu}$ to be more limited
since the retailer accumulates information about the demand distribution
incrementally over time, and so their perceived distributions should not
change too much from period to period.

We need a metric to quantify this variation in
$\hat{F}_{1\mathrel{\mathop{\mathchar 58\relax}}T}^{\mu}$. Recall the
Kolmogorov distance $d_{K}$ between CDFs $F$ and $G$ with support on
$\Xi\subset\mathbb{R}_{+}$ is defined by
$d_{K}(F,G)=\max_{x\in\Xi}|F(x)-G(x)|$. The variation in the retailer’s
perceived distributions from period $t$ to period $t+1$ is then
$d_{K}(\hat{F}_{t}^{\mu},\hat{F}_{t+1}^{\mu})$, and the total variation of the
sequence $\hat{F}_{1\mathrel{\mathop{\mathchar 58\relax}}T}^{\mu}$ is
$\sum^{T-1}_{t=1}d_{K}(\hat{F}^{\mu}_{t},\hat{F}^{\mu}_{t+1})$. We note that
$d_{K}$ is computable for a wide range of possible perceived distributions. In
addition, $d_{K}$ is used in the well-known Kolmogorov-Smirnov test and thus
has an intuitive appeal for measuring the similarity between two
distributions. Furthermore, $d_{K}$ can be upper bounded by many other
distance metrics or divergences, e.g., total variation distance, relative
entropy, Helinger distance, Wasserstein distance, etc. (Gibbs and Su 2002).
This feature of $d_{K}$ greatly facilitates connecting the retailer’s policy
with the regret analysis for the supplier.

We restrict attention to the class of retailer policies for which the total
variation of $\hat{F}_{1\mathrel{\mathop{\mathchar 58\relax}}T}^{\mu}$ (given
by $\sum^{T-1}_{t=1}d_{K}(\hat{F}_{t}^{\mu},\hat{F}_{t+1}^{\mu})$) is bounded.
Specifically, let $V\geq 0$ (where $V$ is a function of $T$) be a budget for
the total variation and define the class of retailer policies:

$\mathcal{M}(V,T)\triangleq\bigg{\\{}\mu\mathrel{\mathop{\mathchar
58\relax}}\text{for any }(w_{t})^{T}_{t=1}\in\mathcal{W},\text{exists
}\hat{F}^{\mu}_{1\mathrel{\mathop{\mathchar 58\relax}}T}\text{ satisfying
Assumptions \ref{ass:retailer-learning-1} and \ref{ass:retailer-learning-
support} such that }\\\
\sum^{T-1}_{t=1}d_{K}(\hat{F}^{\mu}_{t},\hat{F}^{\mu}_{t+1})\leq V\bigg{\\}}.$

The set $\mathcal{M}(V,T)$ includes all $\mu$ such that the total variation of
$\hat{F}^{\mu}_{1\mathrel{\mathop{\mathchar 58\relax}}T}$ does not exceed $V$
for any sequence of wholesale prices. Notice that $\mathcal{M}(V,T)$ also
implicitly depends on $F_{1\mathrel{\mathop{\mathchar 58\relax}}T}$ (since the
demand samples are generated from $F_{1\mathrel{\mathop{\mathchar
58\relax}}T}$), but we suppress this dependence for brevity.

With some abuse of the notation, we write the supplier’s profit in period $t$
as a function of $w_{t}$ and $\hat{F}^{\mu}_{t}$ as
$\varphi(w_{t};\hat{F}_{t}^{\mu})\triangleq(w_{t}-c)q(w_{t};\hat{F}_{t}^{\mu})$,
when the retailer orders optimally based on the perceived distribution
$\hat{F}_{t}^{\mu}$. The supplier’s learning problem can then be framed in
terms of the sequence of her profit functions
$\\{\varphi(w_{t};\hat{F}_{t}^{\mu})\\}_{t=1}^{T}$.

The previous learning literature always considers bounded variation of the
profit functions, and proposes learning algorithms specific to this type of
variation (Besbes et al. 2014b, a, 2015). In the following example, we show
that the variation of $\hat{F}_{1\mathrel{\mathop{\mathchar
58\relax}}T}^{\mu}$ does not directly translate into the variation of
$\\{\varphi(w_{t};\hat{F}_{t}^{\mu})\\}_{t=1}^{T}$. Thus, these previously
proposed learning algorithms do not apply to our setting.

###### Example 2.1

Let $c=0$ and $s=1$. Let $\hat{F}_{t}^{\mu}$ be the CDF of a Bernoulli random
variable which takes values $0$ and $1$ with probabilities $p_{t}$ and
$1-p_{t}$, respectively, for all $t\in[T]$. Let

$p_{t}=\begin{cases}\frac{1}{2}-\epsilon,&\text{ for $t$ odd},\\\
\frac{1}{2}+\epsilon,&\text{ for $t$ even},\end{cases}$

where $\epsilon=1/T$. It is straightforward to see that
$\sum^{T-1}_{t=1}d_{K}(\hat{F}_{t}^{\mu},\hat{F}_{t+1}^{\mu})\leq
2T\epsilon=2$ but that

$\sum^{T-1}_{t=1}\max_{w\in[c,s]}|\varphi(w;\hat{F}_{t}^{\mu})-\varphi(w;\hat{F}_{t+1}^{\mu})|=\frac{T}{2}.$

We see that even if $\hat{F}_{1\mathrel{\mathop{\mathchar 58\relax}}T}^{\mu}$
has constant total variation that does not grow in $T$, the sequence of profit
functions $(\varphi(w;\hat{F}_{t}^{\mu}))^{T}_{t=1}$ can have variation that
grows linearly in $T$.

For the specific class $\mathcal{M}(V,T)$ of retailer policies, the overall
regret is then:

$\text{Reg}(\pi,T)\triangleq\max_{\mu\in\mathcal{M}(V,T)}{\mathds{E}}\left[\sum^{T}_{t=1}\left((w^{*}_{t}-c)q(w^{*}_{t};\hat{F}^{\mu}_{t})-(w_{t}-c)q(w_{t};\hat{F}^{\mu}_{t})\right)\right],$

where the expectation is taken with respect to the supplier’s possibly
randomized policy and any randomization in $\hat{F}^{\mu}_{t}$ (i.e.,
$\hat{F}^{\mu}_{t}$ is random in general because it usually depends on the
random demand realizations, and the retailer may also use a randomized
policy). For comparison, we define the stationary regret to be:

$\text{Reg}_{stat}(\pi,T)\triangleq\max_{\mu\in\mathcal{M}(V,T)}{\mathds{E}}\left[\sum^{T}_{t=1}\left((w^{*}-c)q(w^{*};\hat{F}^{\mu}_{t})-(w_{t}-c)q(w_{t};\hat{F}^{\mu}_{t})\right)\right].$

If the demand distribution is stationary, then intuitively we expect
$\hat{F}_{1\mathrel{\mathop{\mathchar 58\relax}}T}^{\mu}$ to exhibit some type
of convergence since the retailer is accumulating more information about the
same distribution. Yet, our results also apply when the true market demand
distribution is changing over time. For example, the demand distribution may
have a seasonal pattern. In this case, $\hat{F}_{1\mathrel{\mathop{\mathchar
58\relax}}T}^{\mu}$ may still have bounded variation that is sublinear in $T$.

##  3 Stationary Retailer

We first consider the special case of the supplier’s problem for a stationary
retailer to help us understand the structure of the supplier’s profit
function.

The true market demand distribution is stationary, i.e.,
$\hat{F}_{t}^{\mu}=F_{t}=F_{0}$ for all $t\in[T]$, and the retailer has full
knowledge of $F_{0}$.

Since $\mathcal{W}$ is a continuum of allowable prices, this setting is a
continuous bandit treating each price as an arm to pull. The literature
typically imposes some structure on the DM’s objective function, e.g.,
convexity or unimodality, Lipchitz continuity or Holder continuity, etc. (see
Kleinberg et al. (2013), Besbes et al. (2015)). However, the supplier’s profit
function is not necessarily continuous in our setting. Nevertheless, we will
show that we can find pricing policies that have sublinear regret bounds for
general demand distributions.

We make the following boundedness assumption on the demand distribution to
continue.

The sequence $F_{1\mathrel{\mathop{\mathchar 58\relax}}T}$ has bounded support
on $\Xi=[0,\bar{\xi}]$ for $0<\bar{\xi}<\infty$, and both the retailer and the
supplier know $\bar{\xi}$.

Under Assumption 3, we can always relate the values of the supplier’s profit
function at $w_{t}$ and $w_{t}^{\prime}$. Without loss of generality, suppose
$w_{t}^{\prime}<w_{t}$, then for any demand distribution $F$ we have

$\begin{split}\varphi(w_{t};F)-\varphi(w^{\prime}_{t};F)=&\,(w_{t}-c)q(w_{t};F)-(w^{\prime}_{t}-c)q(w^{\prime}_{t};F)\\\
\leq&\,(w_{t}-c)q(w_{t};F)-(w^{\prime}_{t}-c)q(w_{t};F)\\\
\leq&\,(w_{t}-w^{\prime}_{t})\bar{\xi}.\end{split}$ (5)

This inequality holds regardless of whether the true distribution is discrete
or continuous. In particular, we can discretize $\mathcal{W}$ with a finite
set of prices, and then bound sub-optimality of this discretization using Eq.
(5).

We consider the following simple pricing policy for the stationary retailer
that we denote by $\pi_{\text{stat}}$. The supplier first discretizes
$\mathcal{W}$ into $\lceil\sqrt{T}\rceil$ equally sized intervals, and then
takes $\mathcal{\bar{W}}_{\lceil\sqrt{T}\rceil}$ to be the wholesale prices at
the breakpoints of these intervals. In the first $\lceil\sqrt{T}\rceil$
periods, the supplier sets each price in
$\mathcal{\bar{W}}_{\lceil\sqrt{T}\rceil}$ once and collects the corresponding
profit. Let
$w^{*}_{stat}\in\arg\max_{w\in\mathcal{\bar{W}}_{\lceil\sqrt{T}\rceil}}\varphi(w;F_{0})$
be the wholesale price in $\mathcal{\bar{W}}_{\lceil\sqrt{T}\rceil}$ with the
highest profit. The supplier then sets $w_{t}=w^{*}_{stat}$ for all remaining
periods $t=T-\lceil\sqrt{T}\rceil+1,\ldots,T$.

Since $\hat{F}_{1\mathrel{\mathop{\mathchar 58\relax}}T}$ is stationary in
this case, the supplier’s profit function does not change from period to
period. The dynamic and stationary regret coincide and are:

$\text{Reg}(\pi_{\text{stat}},T)=\sum^{T}_{t=1}{\mathds{E}}\left[(w^{*}-c)q(w^{*};F_{0})-(w_{t}-c)q(w_{t};F_{0})\right],$

where $w^{*}\in\max_{w\in\mathcal{W}}(w-c)q(w;F_{0})$. Our proposed policy
$\pi_{\text{stat}}$ gives the supplier $O(\sqrt{T})$ regret. We emphasize that
this result holds for both discrete and continuous demand distributions.

###### Theorem 3.1

Suppose Assumptions 3 and 3 hold. For all $T\geq 1$, we have
$\text{Reg}(\pi_{\text{stat}},T)=O(\sqrt{T})$.

##  4 Learning Retailer

We now discuss the supplier’s problem with a learning retailer. The supplier’s
profit function is generally multi-modal, and now it is also changing shape
since the retailer is updating his perceived distributions. Towards solving
the supplier’s problem in this setting, we start with the case of a discrete
demand distribution and then extend to the continuous case via an
approximation argument. In both cases, we find a pricing policy for the
supplier with a sublinear regret bound.

###  4.1 Discrete Demand Distributions

We first assume that the demand in all time periods has common finite support.

The sequence $F_{1\mathrel{\mathop{\mathchar 58\relax}}T}$ has common support
on $M$ points: $y_{M}(\triangleq\bar{\xi})>y_{M-1}>y_{M-2}>\cdots>y_{1}\geq
0$. The support $\mathcal{Y}_{M}\triangleq\\{y_{m}\\}_{m\in[M]}$ is known to
both the supplier and the retailer. Combined with Assumption 2.1, the sequence
of perceived distributions $\hat{F}_{1\mathrel{\mathop{\mathchar
58\relax}}T}^{\mu}$ also has support on $\mathcal{Y}_{M}$ under this
assumption. Let $p_{t,m}\triangleq\hat{F}_{t}^{\mu}(y_{m})$ for $m\in[M]$
denote the values of the retailer’s perceived distribution in period
$t\in[T]$. The retailer’s order quantity given by Eq. (4) is then

$\begin{split}q_{t}=\begin{cases}y_{1},&\text{ if }0\leq 1-w_{t}/s\leq
p_{t,1},\\\ y_{m},&\text{ if }p_{t,m-1}<1-w_{t}/s\leq p_{t,m},\text{ for
}m\in\\{2,\ldots,M\\}.\end{cases}\end{split}$ (6)

We see that the retailer’s order quantity is a piecewise constant function of
the wholesale price $w_{t}$. According to Eq. (6), the retailer’s order
quantity will always be in the support of the discrete distribution and
satisfy:

$q_{t}\in\mathcal{Y}_{M}.$ (7)

Consequently, the supplier’s profit function in period $t$ is:

$\varphi(w_{t};\hat{F}_{t}^{\mu})=\begin{cases}(w_{t}-c)y_{1},&\text{ if
}0\leq 1-w_{t}/s\leq p_{t,1},\\\ (w_{t}-c)y_{m},&\text{ if
}p_{t,m-1}<1-w_{t}/s\leq p_{t,m}\text{ for }m\in[M].\end{cases}$ (8)

We see it is a piecewise linear function of $w_{t}$, with discontinuities at
the breakpoints $\\{s(1-p_{t,m})\\}_{m\in[M]}$.

We propose a pricing policy for the supplier called $\pi_{\text{LUNA}}$, where
LUNA stands for Learning Under a Non-stationary Agent. It is based on the
deterministic bandit algorithm proposed in Karnin and Anava (2016).
$\pi_{\text{LUNA}}$ works by taking advantage of the special structure of the
supplier’s profit function, as characterized in Eq. (8). In particular, the
performance of the pricing policy depends on accurate estimation of the
probabilities $\bm{p}_{t}\triangleq\left(p_{t,1},\ldots,p_{t,M}\right)$.
$\pi_{\text{LUNA}}$ indirectly estimates $\bm{p}_{t}$ by observing the
retailer’s order quantity and the supplier’s profit through Eq. (8). A good
policy is expected to maintain a somewhat accurate estimate of $\bm{p}_{t}$,
but must also hedge against large variation in $\bm{p}_{t}$. If $\bm{p}_{t}$
has varied a lot, then the optimal wholesale price may be different, and a
large regret will be incurred if the supplier fails to adapt.

The full details of $\pi_{\text{LUNA}}$ are presented in Algorithm 1. It
consists of multiple epochs, where each epoch consists of an exploration phase
followed by an exploitation phase. We let $i\geq 1$ index epochs, but we
usually omit dependence on $i$ except when necessary since each epoch follows
the same pattern. Let $\tau_{i+1}^{0}$ denote the last period of epoch $i\geq
1$ (where $\tau_{1}^{0}=0$). Then, epoch $i\geq 1$ covers periods
$t\in[\tau_{i}^{0}+1,\ldots,\tau_{i+1}^{0}]$. Each time $\pi_{\text{LUNA}}$
starts the exploration phase of a new epoch, it discards all previous
information and estimates $\bm{p}_{t}$ from scratch (since $\bm{p}_{t}$ is
non-stationary, it is the estimate for some particular period $t$). It also
constructs a set of exploratory wholesale prices, tries each price once, and
records the optimal exploratory price which led to the highest observed
supplier profit.

Once it has an initial estimate of $\bm{p}_{t}$ and an optimal exploratory
wholesale price has been found, $\pi_{\text{LUNA}}$ will enter the
exploitation phase. It first constructs a new set of wholesale prices for the
exploitation phase. Then, in each period, a wholesale price is drawn randomly
from this set according to some distribution which balances the exploration-
exploitation trade-off. Most of the time, $\pi_{\text{LUNA}}$ prices at the
nearly optimal wholesale price found in the exploration phase, while also
occasionally detecting whether the previously identified optimal wholesale
price is no longer optimal. If that is the case, then $\pi_{\text{LUNA}}$
quantifies a lower bound on the variation of $\hat{F}_{t}^{\mu}$ in the
current epoch and begins the next epoch.

####  4.1.1 Exploration Phase of $\pi_{\text{LUNA}}$

The goal of the exploration phase is to obtain an initial estimate of
$\bm{p}_{t}$ and to find the optimal wholesale price corresponding to this
initial estimate. As a first step, $\pi_{\text{LUNA}}$ discretizes
$\mathcal{W}$ into $K+1$ equal-length intervals with $K\geq 1$ equally spaced
wholesale prices (where $K$ is an input parameter to be specified later, which
is the same for every epoch). We then let
$\mathcal{\bar{W}}_{K}\triangleq\\{\bar{w}_{k}\\}^{K}_{k=1}$ be the set of
exploratory prices where:

$\bar{w}_{k}\leftarrow(k-1)\frac{(s-c)}{K}+c,\,\forall k\in[K].$ (9)

Then in each period $\tau^{0}_{i}+k$ for all $k\in[K]$, $\pi_{\text{LUNA}}$
sets the wholesale price $\bar{w}_{k}$ and the corresponding retailer order
quantity is $q(\bar{w}_{k};\hat{F}_{\tau^{0}_{i}+k}^{\mu})$. Upon setting
$\bar{w}_{k}$, $\pi_{\text{LUNA}}$ earns profit $\varphi_{k}$ given by:

$\varphi_{k}\leftarrow(\bar{w}_{k}-c)q(\bar{w}_{k};\hat{F}_{\tau^{0}_{i}+k}^{\mu}).$
(10)

Let $k^{*}\in\arg\max_{k\in[K]}\varphi_{k}$, so $\bar{w}_{k^{*}}$ is the
wholesale price that maximizes the observed profit among
$\mathcal{\bar{W}}_{K}$. By Eq. (7), we must have
$q(\bar{w}_{k^{*}};\hat{F}_{\tau^{0}_{i}+k^{*}}^{\mu})\in\mathcal{Y}_{M}$, so
we let $m^{*}\in[M]$ be such that $y_{m^{*}}\triangleq
q(\bar{w}_{k^{*}};\hat{F}_{\tau^{0}_{i}+k^{*}}^{\mu})$. With $\bar{w}_{k^{*}}$
and $y_{m^{*}}$ in hand, we begin the exploitation phase of epoch $i$.

####  4.1.2 Exploitation Phase of $\pi_{\text{LUNA}}$

If the retailer is stationary, then $\bar{w}_{k^{*}}$ will remain nearly
optimal for the rest of the planning horizon (this is exactly the supplier’s
pricing policy for a stationary retailer, see Section 3). However, as the
retailer is also learning the demand distribution, we expect
$\hat{F}_{t}^{\mu}$ to vary. If $\hat{F}_{t}^{\mu}$ has varied a lot and the
supplier still prices at $\bar{w}_{k^{*}}$, then she is likely to suffer a
large regret. The supplier’s pricing policy has to balance between
exploitation (stick to the optimal $\bar{w}_{k^{*}}$ found in the exploration
phase) and exploration (hedge against the risk that $\hat{F}_{t}^{\mu}$ has
changed a lot since the exploration phase).

We show that this balance can be achieved during the exploitation phase by
randomly choosing from a carefully chosen finite set of prices. This set of
prices is constructed based on the structure of the supplier’s profit function
through Eq. (8), and it will be different for each period $t$. We first
construct this set of prices, and then explain the intuition behind it.

We allow the pricing policy in period $t$ to have a margin of sub-optimality
$\Delta_{t}>0$ compared with $\varphi_{k^{*}}$, the highest profit observed in
the exploration phase. The sequence $\\{\Delta_{t}\\}_{t\geq 1}$ will be
chosen to be decreasing in $t$ (in particular, we will take
$\Delta_{t}=O(\sqrt{1/t})$). Then, in each period $t$, we construct a set of
prices based on $\Delta_{t}$ to sample from.

There are two cases where $\bar{w}_{k^{*}}$ becomes sufficiently sub-optimal
to end the current epoch, either: (i) the supplier’s profit at some
$w\neq\bar{w}_{k^{*}}$ has increased a lot since the exploration phase; or
(ii) the supplier’s profit at $\bar{w}_{k^{*}}$ has decreased a lot since the
exploration phase. We discuss the details of these two cases separately.

##### Case one:

In the first case, some $w\in\mathcal{W}$ with $w\neq\bar{w}_{k^{*}}$ now
earns greater profit for the supplier than $\bar{w}_{k^{*}}$. This $w$ can be
an arbitrary member of $\mathcal{W}$ as long as $w\neq\bar{w}_{k^{*}}$.
However, we cannot check every price in $\mathcal{W}$, so we construct a
specialized finite set of prices to check as follows.

We recall that $q^{\mu}_{t}\in\mathcal{Y}_{M}$ holds for all $t\in[T]$ under
Assumption 4.1, so we ask the question: Suppose the retailer’s order quantity
is $y_{m}\in\mathcal{Y}_{M}$ for some $m\in[M]$, then what wholesale price
(denoted by $w^{t}_{m}$) would give the supplier a profit that is equal to
$\varphi_{k^{*}}+\Delta_{t}$? If the retailer’s order quantity
$q(w^{t}_{m};\hat{F}_{t}^{\mu})$ under $w^{t}_{m}$ turns out to be larger than
(smaller than) $y_{m}$, then $w^{t}_{m}$ will give a higher (lower) profit
than $\varphi_{k^{*}}+\Delta_{t}$. We construct a set of wholesale prices in
this way corresponding to each $y_{m}\in\mathcal{Y}_{M}$. In period $t$, for
each $m\in[M]$, we set the corresponding wholesale prices according to:

$(w^{t}_{m}-c)y_{m}=\varphi_{k^{*}}+\Delta_{t}+\frac{y_{m}s}{K},\text{ which
gives
}w^{t}_{m}\triangleq\Big{(}\varphi_{k^{*}}+\Delta_{t}+\frac{y_{m}s}{K}\Big{)}/y_{m}+c,$
(11)

where the term $\frac{y_{m}s}{K}$ is introduced to account for the error
introduced by discretizing $\mathcal{W}$ to $\mathcal{\bar{W}}_{K}$.

If the supplier prices at $w^{t}_{m}$ in period $t$, and if
$q(w^{t}_{m};\hat{F}_{t}^{\mu})\geq y_{m}$, then $\bar{w}_{k^{*}}$ is no
longer nearly optimal since the optimality gap now exceeds $\Delta_{t}$ (i.e.,
we have $(w^{t}_{m}-c)y_{m}\geq\varphi_{k^{*}}+\Delta_{t}$). We summarize this
discussion in Lemma 4.1.

###### Lemma 4.1

If $q(w^{t}_{m};\hat{F}_{t}^{\mu})\geq y_{m}$, then $p_{t,m-1}\leq
1-w^{t}_{m}/s$ and
$\varphi(w^{t}_{m};\hat{F}_{t}^{\mu})\geq(w^{t}_{m}-c)y_{m}=\varphi_{k^{*}}+\Delta_{t}+\frac{y_{m}s}{K}$.
Otherwise, if $q(w^{t}_{m};\hat{F}_{t}^{\mu})<y_{m}$, then $p_{t,m-1}\geq
1-w^{t}_{m}/s$ and
$\varphi(w^{t}_{m};\hat{F}_{t}^{\mu})<(w^{t}_{m}-c)y_{m}=\varphi_{k^{*}}+\Delta_{t}+\frac{y_{m}s}{K}$.

In addition, if $q(w^{t}_{m};\hat{F}_{t})\geq y_{m}$, then $\hat{F}_{t}^{\mu}$
has varied a lot since the exploration phase.

###### Lemma 4.2

If $q(w^{t}_{m};\hat{F}_{t}^{\mu})\geq y_{m}$, then
$\sum_{j\in[\tau^{0}_{i}+1,t-1]}d_{K}(\hat{F}_{j}^{\mu},\hat{F}_{j+1}^{\mu})\geq\Delta_{t}/(s\,\bar{\xi})$.

##### Case two:

In the second case, the supplier’s profit from pricing at $\bar{w}_{k^{*}}$
has decreased a lot since the exploration phase. This can happen if the
retailer’s order quantity $q(\bar{w}_{k^{*}};\hat{F}_{t}^{\mu})$ in period $t$
during the exploitation phase is much smaller than the order quantity
$q(\bar{w}_{k^{*}};\hat{F}_{\tau^{0}_{i}+k^{*}}^{\mu})$ observed during the
exploration phase. Since $\bar{w}_{k^{*}}$ is the optimal price found during
the exploration phase, the policy should price frequently at $\bar{w}_{k^{*}}$
to exploit what is best. However, pricing at $\bar{w}_{k^{*}}$ does not give
useful information about the variation in $\hat{F}_{t}$. Even if $\hat{F}_{t}$
has only varied by a small amount, the profit at $\bar{w}_{k^{*}}$ can still
change drastically (recall Example 2.1). If we restart the epoch each time the
profit at $\bar{w}_{k^{*}}$ has decreased a lot, we will end up with too many
epochs and a high overall regret.

Therefore, instead of pricing at $\bar{w}_{k^{*}}$, we determine a surrogate
price $w^{t}_{0}$ which achieves two purposes: (i) the profit at $w^{t}_{0}$
is not much lower than the profit at $\bar{w}_{k^{*}}$, so we can still
exploit the optimality of $\bar{w}_{k^{*}}$ from the exploration phase (see
Eq. (13)); and (ii) unlike $\bar{w}_{k^{*}}$, when the profit at $w^{t}_{0}$
is sufficiently low, we can quantify a lower bound on the variation of
$\hat{F}^{\mu}_{t}$ (see Lemma 4.4) and correctly restart the epoch. We define
the surrogate price $w^{t}_{0}$ in period $t$ to satisfy:

$(w^{t}_{0}-c)y_{m^{*}}=\varphi_{k^{*}}-\Delta_{t}\text{ and }w^{t}_{0}\geq
0,\text{ otherwise }w^{t}_{0}=0,$

which gives

$w^{t}_{0}\triangleq\max\\{\bar{w}_{k^{*}}-\Delta_{t}/y_{m^{*}},0\\}.$ (12)

Note we require $w^{t}_{0}\geq 0$ instead of $w^{t}_{0}\geq c$. By allowing
$w^{t}_{0}<c$, the policy is able to detect variation of $\hat{F}_{t}^{\mu}$
that would otherwise not be detected.

By Eq. (5), the difference in profit between pricing at $w^{t}_{0}$ and
$\bar{w}_{k^{*}}$ is lower bounded by:

$\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})-\varphi(\bar{w}_{k^{*}};\hat{F}_{t}^{\mu})\geq-\Delta_{t}.$
(13)

We make the following inferences based on the surrogate price.

###### Lemma 4.3

If $q(w^{t}_{0};\hat{F}_{t}^{\mu})\geq y_{m^{*}}$, then $p_{t,m^{*}-1}\leq
1-w^{t}_{0}/s$ and
$\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})\geq(w^{t}_{0}-c)y_{m^{*}}\geq\varphi_{k^{*}}-\Delta_{t}$.
Otherwise, if $q(w^{t}_{0};\hat{F}_{t}^{\mu})<y_{m^{*}}$, then
$p_{t,m^{*}-1}\geq 1-w^{t}_{0}/s$ and
$\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})<(w^{t}_{0}-c)y_{m^{*}}=\varphi_{k^{*}}-\Delta_{t}$.

If the retailer’s order quantity satisfies
$q(w^{t}_{0};\hat{F}_{t}^{\mu})<y_{m^{*}}$, then we know that
$\hat{F}_{t}^{\mu}$ has varied a lot since the beginning of epoch $i$.

###### Lemma 4.4

If $q(w^{t}_{0};\hat{F}_{t}^{\mu})<y_{m^{*}}$, then
$\sum_{j\in[\tau^{0}_{i}+1,t-1]}d_{K}(\hat{F}_{j}^{\mu},\hat{F}_{j+1}^{\mu})\geq\Delta_{t}/(s\,\bar{\xi})$.

####  4.1.3 Algorithm and regret bound

In each period $t$, we construct the set of wholesale prices
$\\{w^{t}_{0},w_{1}^{t},\ldots,w_{M}^{t}\\}$, and $\pi_{\text{LUNA}}$ will
randomly sample from $\\{w^{t}_{0},w_{1}^{t},\ldots,w_{M}^{t}\\}$ according to
a distribution that is changing over time. Based on the discussion of the
previous two cases, the exploitation phase continues until
$q(w^{t}_{m};\hat{F}_{t}^{\mu})\geq y_{m}$ for some $m\in[M]$, or
$q(w^{t}_{0};\hat{F}_{t}^{\mu})<y_{m^{*}}$. In both cases, $\hat{F}_{t}^{\mu}$
is guaranteed to have varied a lot since the exploration phase, and
$\pi_{\text{LUNA}}$ starts the next epoch. Let $\mathcal{U}([M])$ denote the
uniform distribution on $\\{1,2,\ldots,M\\}$.

1 Input: Time horizon $T$, supplier production cost $c$, retailer selling
price $s$, support $\mathcal{Y}_{M}$, grid size $K$;

2 Update current period $t\leftarrow 1$;

3 Set epoch $i\leftarrow 1$ and $\tau^{0}_{1}\leftarrow 0$;

4 for  _epoch $i=1,2,\cdots$_ do

5 Exploration:

6 Price at $\bar{w}_{k}$ (see Eq. (9)) and observe $\varphi_{k}$ (see Eq.
(10)) for the first $K$ periods in epoch $i$;

7 Let $k^{*}\in\arg\max_{k\in[K]}\varphi_{k}$ and $m^{*}$ be such that
$y_{m^{*}}=q\left(\bar{w}_{k^{*}};\hat{F}_{\tau^{0}_{i}+k^{*}}^{\mu}\right)$;

8 Exploitation:

9 In period $t$, set $\Delta_{t}\leftarrow\sqrt{M/(t-\tau^{0}_{i})}$;

10 Compute prices $w^{t}_{m}$ for $m\in[M]$ and $w^{t}_{0}$ according to Eq.
(11) and Eq. (12), respectively;

11 Select wholesale price $w_{t}\leftarrow w_{m_{t}}^{t}$ according to the
distribution  $m_{t}=\begin{cases}0,&\text{ w.p.
}1-\sqrt{\frac{M}{t-\tau^{0}_{i}}},\\\ \mathcal{U}([M]),&\text{ w.p.
}\sqrt{\frac{M}{t-\tau^{0}_{i}}},\end{cases}$

12 Observe retailer’s order $q(w_{t};\hat{F}_{t}^{\mu})$;

13 if  _ $q(w_{m_{t}}^{t};\hat{F}_{t}^{\mu})\geq y_{m_{t}}$ for $m_{t}\in[M]$
or $q(w_{m_{t}}^{t};\hat{F}_{t}^{\mu})<y_{m^{*}}$ for $m_{t}=0$ _ then

14 $\tau^{0}_{i+1}\leftarrow t$ and start the next epoch $i\leftarrow i+1$ ;

15

Algorithm 1 Learning Under Non-stationary Agent (LUNA)

Theorem 4.5 upper bounds the regret of Algorithm 1 as a function of $V$ and
$K$ (notice that $\pi_{\text{LUNA}}$ does not need to know $V$, but $K$ is an
input). When in addition $V$ is known, the decision maker can choose $K$
optimally as a function of $V$ to minimize the regret.

###### Theorem 4.5

Suppose Assumption 4 holds.

(i) For all $K\geq 1$,
$\text{Reg}(\pi_{\text{LUNA}},T)=\tilde{O}(\bar{\xi}^{\frac{4}{3}}V^{\frac{1}{3}}M^{\frac{1}{3}}T^{\frac{2}{3}}+\frac{\bar{\xi}\,T}{K}+\bar{\xi}^{\frac{5}{3}}KV^{\frac{2}{3}}M^{-\frac{1}{3}}T^{\frac{1}{3}})$.

(ii) If the supplier knows $V$, then $K$ can be chosen optimally as
$K^{*}=\lceil T^{\frac{1}{3}}V^{-\frac{1}{3}}\bar{\xi}^{-\frac{1}{3}}\rceil$,
and the minimized regret is
$\text{Reg}(\pi_{\text{LUNA}},T)=\tilde{O}(\bar{\xi}^{\frac{4}{3}}V^{\frac{1}{3}}M^{\frac{1}{3}}T^{\frac{2}{3}})$.

(iii) If the supplier does not know $V$, then $K$ can be chosen obliviously as
$\hat{K}=\lceil\bar{\xi}^{-\frac{1}{3}}T^{\frac{1}{3}}\rceil$, and the regret
is
$\text{Reg}(\pi_{\text{LUNA}},T)=\tilde{O}(\bar{\xi}^{\frac{4}{3}}V^{\frac{1}{3}}M^{\frac{1}{3}}T^{\frac{2}{3}}+\bar{\xi}^{\frac{4}{3}}V^{\frac{2}{3}}M^{-\frac{1}{3}}T^{\frac{2}{3}})$.

According to Theorem 4.5, using our pricing policy $\pi_{\text{LUNA}}$, the
supplier can achieve a sublinear regret bound if $V=\tilde{o}(T)$ and if
$V=\tilde{o}(\sqrt{T})$ when the supplier knows $V$ and does not know $V$
respectively.

###  4.2 Proof Outline of Theorem 4.5 ($\pi_{\text{LUNA}}$)

Here we overview the proof of Theorem 4.5, all detailed expressions and
derivations referenced here appear in Appendix 9. We first do the regret
analysis for a single epoch $i$ (which consists of periods
$t\in[\tau_{i}^{0}+1,\tau_{i+1}^{0}]$), and then assemble these into an
overall regret bound. To begin, we decompose the regret in epoch $i$ into:

$\begin{split}\sum^{\tau^{0}_{i+1}}_{t=\tau^{0}_{i}+1}\bigg{\\{}\varphi(w^{*}_{t};\hat{F}_{t}^{\mu})-\varphi(w_{t};\hat{F}_{t}^{\mu})\bigg{\\}}=\sum^{\tau^{0}_{i+1}}_{t=\tau^{0}_{i}+1}\bigg{\\{}\varphi(w^{*}_{t};\hat{F}_{t}^{\mu})-\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})\bigg{\\}}+\bigg{\\{}\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})-\varphi(w_{t};\hat{F}_{t}^{\mu})\bigg{\\}},\end{split}$

where the first part
$\text{Reg}_{i}^{c}(\pi_{\text{LUNA}})\triangleq\sum^{\tau^{0}_{i+1}}_{t=\tau^{0}_{i}+1}\\{\varphi(w^{*}_{t};\hat{F}_{t}^{\mu})-\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})\\}$
(the superscript ‘c’ is for ‘clairvoyant’) is the regret incurred by always
pricing at $w^{t}_{0}$ compared to the clairvoyant benchmark, and the second
part
$\text{Reg}_{i}^{0}(\pi_{\text{LUNA}})\triangleq\sum^{\tau^{0}_{i+1}}_{t=\tau^{0}_{i}+1}\\{\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})-\varphi(w_{t};\hat{F}_{t}^{\mu})\\}$
(the superscript ‘0’ corresponds to the surrogate price) is the regret
incurred compared with the benchmark of always pricing at the surrogate price
$w^{t}_{0}$. We analyze these two parts separately.

##### Part I of the regret

To upper bound $\text{Reg}_{i}^{c}(\pi_{\text{LUNA}})$, we define the
following subset of periods of epoch $i$:

$\mathcal{E}^{i}\triangleq\left\\{t\in[\tau^{0}_{i}+\max\\{M+2,K\\}+1,\tau^{0}_{i+1}]\mathrel{\mathop{\mathchar
58\relax}}q(w^{t}_{m};\hat{F}_{t}^{\mu})<y_{m},\,\forall m\in[M],\text{ and
}q(w^{t}_{0};\hat{F}_{t}^{\mu})\geq y_{m^{*}}\right\\}.$

If $t\in\mathcal{E}^{i}$, then $\hat{F}_{t}^{\mu}$ has not varied a lot within
epoch $i$ and pricing at $w^{t}_{0}$ remains nearly optimal. On the other
hand, if $t\notin\mathcal{E}^{i}$, then pricing at $w^{t}_{0}$ is no longer
nearly optimal either because the profit at $w^{t}_{0}$ has gone down, or the
profit at some $w^{t}_{m}\neq w^{t}_{0}$ has gone up. We can further decompose

$\begin{split}\varphi(w^{*}_{t};\hat{F}_{t}^{\mu})-\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})&=\left(\varphi(w^{*}_{t};\hat{F}_{t}^{\mu})-\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})\right)\mathds{1}(t\in\mathcal{E}^{i})+\left(\varphi(w^{*}_{t};\hat{F}_{t}^{\mu})-\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})\right)\mathds{1}(t\notin\mathcal{E}^{i}),\\\
\end{split}$

and then upper bound these expressions separately. First we upper bound the
regret
$\varphi(w^{*}_{t};\hat{F}_{t}^{\mu})-\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})$
for periods $t\in\mathcal{E}^{i}$. The next result takes effect after period
$\tau_{i}^{0}+\max\\{M+2,K\\}$ and only applies to the exploitation phase.

###### Lemma 4.6

For all
$t\in[\tau^{0}_{i}+\max\\{M+2,K\\}+1,\tau^{0}_{i+1}]\cap\mathcal{E}^{i}$, we
have
$\varphi(w^{*}_{t};\hat{F}_{t}^{\mu})-\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})\leq
2\Delta_{t}+\frac{\bar{\xi}s}{K}$.

Next we upper bound
$E^{i}\triangleq\sum^{\tau^{0}_{i+1}}_{t=\tau^{0}_{i}+\max\\{M+2,K\\}+1}\mathds{1}(t\notin\mathcal{E}^{i})$,
the number of periods when $t\notin\mathcal{E}^{i}$ (during the exploitation
phase of epoch $i$).

###### Lemma 4.7

With probability at least $1-1/T^{2}$, $E^{i}\leq
2\log(T)\sqrt{M(\tau^{0}_{i+1}-1-\tau^{0}_{i})}+1$.

We combine Lemmas 4.6 and 4.7, and summarize the resulting bound on
$\text{Reg}_{i}^{c}(\pi_{\text{LUNA}})$ in Eq. (29) in Appendix 9.

##### Part II of the regret

To upper bound $\text{Reg}_{i}^{0}(\pi_{\text{LUNA}})$, we note

$\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})-\varphi(w_{t};\hat{F}_{t}^{\mu})=\left(\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})-\varphi(w_{t};\hat{F}_{t}^{\mu})\right)\mathds{1}(w_{t}\neq
w^{t}_{0})$

for all $t$. That is, the supplier can only incur regret with respect to the
benchmark of always pricing at $w^{t}_{0}$ if $w_{t}\neq w^{t}_{0}$. Let

$T_{i}(K)\triangleq\left|\\{t\in[\tau^{0}_{i}+K+1,\tau^{0}_{i+1}]\mathrel{\mathop{\mathchar
58\relax}}m_{t}\neq 0\\}\right|$

be the number of periods in the exploitation phase of epoch $i$ when
$\pi_{\text{LUNA}}$ does not select $m_{t}=0$ (and price at $w^{t}_{0}$). The
next lemma upper bounds $T_{i}(K)$.

###### Lemma 4.8

(Karnin and Anava 2016, Lemma A.2) For all $K\geq 1$, we have
$T_{i}(K)\leq\sqrt{11\log(T)M(\tau^{0}_{i+1}-1-\tau^{0}_{i})}$ with
probability at least $1-1/T^{2}$.

We summarize the resulting bound for $\text{Reg}_{i}^{0}(\pi_{\text{LUNA}})$
in Eq. (30) in Appendix 9.

##### Combining the two parts of the regret

We combine Eq. (29) and Eq. (30) to upper bound the regret for epoch $i$ in
Eq. (LABEL:equ:appendix-retailer-learning-7). To derive the supplier’s total
regret over the entire planning horizon $T$, we also need an upper bound on
$I$ (the total number of epochs). In Lemmas 4.2 and 4.4, we showed that when
an epoch ends, $\hat{F}_{t}$ has varied a lot within the current epoch. Since
the total variation of $\hat{F}_{1\mathrel{\mathop{\mathchar 58\relax}}T}$
over the entire planning horizon is bounded, the total number of epochs $I$
must be bounded by the variation budget.

###### Lemma 4.9

We have
$I\leq(s\,\bar{\xi})^{\frac{2}{3}}V^{\frac{2}{3}}M^{-\frac{1}{3}}T^{\frac{1}{3}}+1$
almost surely.

Based on Lemma 4.9 and Eq. (LABEL:equ:appendix-retailer-learning-7), we obtain
our final regret bound in Eq. (32), concluding the proof.

###  4.3 Continuous Demand Distributions

We now turn to the continuous case. We may also use the upcoming approach when
the support of the demand distribution is finite but very large, so we do not
specifically require $F_{1\mathrel{\mathop{\mathchar 58\relax}}T}$ and
$\hat{F}_{1\mathrel{\mathop{\mathchar 58\relax}}T}^{\mu}$ to have densities
for this treatment. We do suppose that Assumption 3 is in force throughout
this subsection.

When $\hat{F}_{t}^{\mu}$ is continuous, under Assumption 3, $q_{t}$ can take
any value in the interval $[0,\bar{\xi}]$. In contrast, when
$\hat{F}_{t}^{\mu}$ has support on $\mathcal{Y}_{M}$, the retailer’s order
quantity always satisfies $q_{t}\in\mathcal{Y}_{M}$. $\pi_{\text{LUNA}}$ used
this fact to track the variation of $\hat{F}_{1\mathrel{\mathop{\mathchar
58\relax}}T}^{\mu}$ when demand has support on $\mathcal{Y}_{M}$, but it is
much harder to infer the behavior of $\hat{F}_{t}^{\mu}$ in the continuous
case. Our strategy is based on approximating $[0,\bar{\xi}]$ with a finite
subset of equally spaced points. Let $N\geq 1$ be the size of this subset, and
let $\mathcal{Z}_{N}\triangleq\\{z_{n}\\}_{n\in[N]}$ be equally spaced points
on $[0,\bar{\xi}]$ defined by: $z_{n}=(n-1)\,\bar{\xi}/(N-1)$ for all
$n\in[N]$.

We call our pricing policy for the continuous case Learning Under Non-
stationary Agent with Continuous Distribution (LUNAC), denoted
$\pi_{\text{LUNAC}}$, which calls $\pi_{\text{LUNA}}$ as a subroutine on
$\mathcal{Z}_{N}$. The details of $\pi_{\text{LUNAC}}$ are outlined in
Algorithm 2. In each period, $\pi_{\text{LUNAC}}$ enacts the wholesale price
$w_{t}$ suggested by $\pi_{\text{LUNA}}$ and receives the feedback
$q(w_{t};\hat{F}_{t}^{\mu})$. $\pi_{\text{LUNAC}}$ then maps the feedback
$q(w_{t};\hat{F}_{t}^{\mu})$ to some $z_{n}\in\mathcal{Z}_{N}$, which is then
given to $\pi_{\text{LUNA}}$, which then outputs a recommended price.

1 Input: Time horizon $T$, supplier production cost $c$, retailer selling
price $s$, $N\geq 1$ and $\mathcal{Z}_{N}$;

2 Initialize $\pi_{\text{LUNA}}$ with $\mathcal{Z}_{N}$;

3 while  _$t\leq T$_ do

4 Set the wholesale price $w_{t}$ suggested by $\pi_{\text{LUNA}}$ and observe
retailer’s order $q(w_{t};\hat{F}_{t}^{\mu})$;

5 Find $n$ such that $z_{n-1}<q(w_{t};\hat{F}_{t}^{\mu})\leq z_{n}$ for some
$2\leq n\leq N$ ($n=1$ if $q(w_{t};\hat{F}^{\mu}_{t})=0$), and take $z_{n}$ as
the feedback to $\pi_{\text{LUNA}}$.

Algorithm 2 Learning Under Non-stationary Agent with Continuous Distribution
(LUNAC)

The retailer’s order quantities are determined by
$\hat{F}_{1\mathrel{\mathop{\mathchar 58\relax}}T}^{\mu}$ (which may have
support on all of $[0,\bar{\xi}]$), while we are running $\pi_{\text{LUNA}}$
as a subroutine on the finite set $\mathcal{Z}_{N}$. To analyze the behavior
of the $\pi_{\text{LUNA}}$ subroutine, we introduce a sequence of fictitious
perceived distributions with support on $\mathcal{Z}_{N}$ that are based on
the retailer’s actual perceived distributions. Let $\tilde{F}^{\mu}_{t}$ be
the fictitious distribution on $\mathcal{Z}_{N}$ for period $t$, which
satisfies

$\tilde{F}^{\mu}_{t}(z_{n})=\hat{F}_{t}^{\mu}(z_{n}),\,\forall n\in[N],$ (14)

for all $t\in[T]$. We introduce the shorthand
$\tilde{F}^{\mu}_{1\mathrel{\mathop{\mathchar
58\relax}}t}\triangleq(\tilde{F}^{\mu}_{i})^{t}_{i=1}$ for $t\in[T]$ for the
partial sequences of fictitious perceived distributions.

We will establish that, under Eq. (14), the wholesale prices output by
$\pi_{\text{LUNAC}}$ under $\hat{F}_{1\mathrel{\mathop{\mathchar
58\relax}}t}^{\mu}$ coincide with the wholesale prices output by
$\pi_{\text{LUNA}}$ on $\mathcal{Z}_{N}$ under
$\tilde{F}_{1\mathrel{\mathop{\mathchar 58\relax}}t}$. Let $\omega$ be a
sample path of the randomization of $\pi_{\text{LUNA}}$, and let $\Omega$ be
the set of all such sample paths. All the randomization in
$\pi_{\text{LUNAC}}$ comes from the randomization in $\pi_{\text{LUNA}}$ on
$\mathcal{Z}_{N}$, so we can compare both algorithms on $\Omega$. Let
$w^{\text{LUNAC}}_{t}(\hat{F}_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}^{\mu};\omega)$ be the wholesale price output by
$\pi_{\text{LUNAC}}$ given the distributions
$\hat{F}_{1\mathrel{\mathop{\mathchar 58\relax}}t-1}^{\mu}$ under $\omega$,
and let $w^{\text{LUNA}}_{t}(\tilde{F}^{\mu}_{1\mathrel{\mathop{\mathchar
58\relax}}t-1};\omega)$ be the wholesale price output by $\pi_{\text{LUNA}}$
given the distributions $\tilde{F}^{\mu}_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}$ under $\omega$.

###### Lemma 4.10

For all $t\in[T]$ and $\omega\in\Omega$,
$w^{\text{LUNAC}}_{t}(\hat{F}_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}^{\mu};\omega)=w^{\text{LUNA}}_{t}(\tilde{F}^{\mu}_{1\mathrel{\mathop{\mathchar
58\relax}}t-1};\omega)$.

Loosely speaking, Lemma 4.10 says that $\pi_{\text{LUNAC}}$ sets wholesale
prices by approximating $\hat{F}_{t}^{\mu}$ with $\tilde{F}^{\mu}_{t}$ in each
period. It then outputs the wholesale prices given by $\pi_{\text{LUNA}}$,
which pretends the retailer’s perceived distribution is actually
$\tilde{F}^{\mu}_{t}$. This interpretation suggests that if
$\hat{F}_{1\mathrel{\mathop{\mathchar 58\relax}}T}^{\mu}$ has bounded
variation, then $\tilde{F}_{1\mathrel{\mathop{\mathchar 58\relax}}T}$ should
have bounded variation, as shown in Lemma 4.11.

###### Lemma 4.11

For all $t\in[T-1]$, $d_{K}(\tilde{F}_{t}^{\mu},\tilde{F}_{t+1}^{\mu})\leq
d_{K}(\hat{F}_{t}^{\mu},\hat{F}_{t+1}^{\mu})$.

Theorem 4.12 below bounds the regret of $\pi_{\text{LUNAC}}$ (see Algorithm
2). $\pi_{\text{LUNAC}}$ does not require the variation budget $V$ as an
input, but we get an improved regret bound with knowledge of $V$.

###### Theorem 4.12

Suppose Assumption 3 holds.

(i) If the supplier knows $V$, then $N$ can be chosen optimally as
$N^{*}=\lceil\bar{\xi}^{-\frac{1}{4}}V^{-\frac{1}{4}}T^{\frac{1}{4}}\rceil$,
and
$\text{Reg}(\pi_{LUNAC},T)=\tilde{O}(\bar{\xi}^{\frac{5}{4}}V^{\frac{1}{4}}T^{\frac{3}{4}})$.

(ii) If the supplier does not know $V$, then $N$ can be chosen obliviously as
$\hat{N}=\lceil\bar{\xi}^{-\frac{1}{4}}T^{\frac{1}{4}}\rceil$, and
$\text{Reg}(\pi_{LUNAC},T)=\tilde{O}(\bar{\xi}^{\frac{5}{4}}V^{\frac{1}{3}}T^{\frac{3}{4}}+\bar{\xi}^{\frac{17}{12}}V^{\frac{2}{3}}T^{\frac{7}{12}})$.

According to Theorem 4.12, the supplier can achieve a sublinear regret bound
if $V=\tilde{o}(T)$ when the supplier knows $V$ and if
$V=\tilde{o}(T^{\frac{5}{8}})$ when she does not know $V$, respectively.
Theorem 4.5 shows that the supplier has a sublinear regret bound only if
$V=\tilde{o}(T^{\frac{1}{2}})$, when there is no approximation of
$\mathcal{W}$. The improvement from $V=\tilde{o}(T^{\frac{1}{2}})$ to
$V=\tilde{o}(T^{\frac{5}{8}})$ is achieved by approximation of the
distribution. The supplier indirectly controls the number of epochs, and so a
discrete approximation may lead to a better regret bound when $V$ is large. It
follows that the supplier can use $\pi_{\text{LUNAC}}$ not only when the
distribution is continuous, but also for discrete distributions where the
supplier believes the unknown $V$ is large.

###### Remark 4.13

When the supplier does not know $V$, she can combine LUNAC with the BOB
framework (Cheung et al. 2019, 2021), which we refer to as LUNAC-N. The
implementation details of $\pi_{\text{LUNAC-N}}$ are presented in Appendix 11,
and the upper bound on the regret of $\pi_{\text{LUNAC-N}}$ is presented in
Theorem 11.1.

Before we end this section, we comment on the difference between our
discretization approach and those approaches used for the continuous bandit.
The decision set is continuous in a continuous bandit, and it is common to
approximate the decision set with a finite set. Instead of finding the optimal
decision in the original continuous decision set, an optimal decision is found
from the finite set, and then the regret is established through a regularity
assumption (e.g., Lipschitz or Holder continuity) on the reward/cost function.
We do not directly approximate the continuous decision set. Instead, we
approximate the supplier’s profit function by finding an approximate
distribution $\tilde{F}_{t}$ for $\hat{F}_{t}^{\mu}$ (albeit both the true
profit function and $\hat{F}_{t}^{\mu}$ are unknown). Our approach relies on
the bilinearity of the supplier’s profit function in $w$ and $q$, and it does
not require the regularity assumptions on the objective from the continuous
bandit literature.

##  5 Examples of Retailer’s Strategies

We investigate several well known data-driven retailer inventory learning
policies in this section, and show that our proposed pricing policies achieve
sublinear regret for all of them. We emphasize that we do not need to know the
retailer’s exact inventory policy to achieve sublinear regret, we only mean to
illustrate that these popular inventory policies satisfy our key assumption on
the total variation of $\hat{F}_{1\mathrel{\mathop{\mathchar
58\relax}}T}^{\mu}$. In addition, the examples in this section suppose that
the retailer does not have prior knowledge of $V$. Instead, these examples
help provide guidance on refining $V$ in practice.

###  5.1 Sample Average Approximation (SAA)

SAA is arguably the most widely studied approach for data-driven optimization
(Levi et al. 2015, Kleywegt et al. 2002). We let $\mu_{\text{e}}$ denote the
retailer’s inventory policy based on SAA. For all $t\in[T]$, let
$\hat{F}^{\text{e}}_{t}$ be the empirical CDF constructed from the (not
necessarily i.i.d.) demand samples $(\xi_{i})^{t-1}_{i=1}$ defined by
$\hat{F}^{\text{e}}_{t}(x)\triangleq\frac{1}{t-1}\sum^{t-1}_{i=1}\mathds{1}(\xi_{i}\leq
x)$ for all $x\geq 0$ (note that in period $t$, the retailer only got access
to the demand realizations in the previous $t-1$ periods). Under
$\mu_{\text{e}}$, given wholesale price $w_{t}$, the retailer’s order quantity
satisfies $q^{e}_{t}=q_{t}(w_{t};\hat{F}^{\text{e}}_{t})$.

We can upper bound the total variation $V$ of the sequence
$\hat{F}^{\text{e}}_{1\mathrel{\mathop{\mathchar 58\relax}}T}$ for arbitrary
$F_{1\mathrel{\mathop{\mathchar 58\relax}}T}$ (i.e., the true distribution can
be changing arbitrarily).

###### Proposition 5.1

$\mu_{\text{e}}\in\mathcal{M}(\log(T)+1,T)$.

Next we bound the supplier’s regret under $\pi_{\text{LUNA}}$ (if the
distribution has finite support) or $\pi_{\text{LUNAC}}$ (if the distribution
has continuous support). The proof follows from Theorem 4.5 and Proposition
5.1.

###### Theorem 5.2

Suppose the retailer follows $\mu_{\text{e}}$.

(i) Suppose $F_{1\mathrel{\mathop{\mathchar 58\relax}}T}$ have support on
$\mathcal{Y}_{M}$, then
$\text{Reg}(\pi_{\text{LUNA}},T)=\tilde{O}(\bar{\xi}^{\frac{4}{3}}M^{\frac{1}{3}}T^{\frac{2}{3}})$.

(ii) Suppose $F_{1\mathrel{\mathop{\mathchar 58\relax}}T}$ have support on
$[0,\bar{\xi}]$, then
$\text{Reg}(\pi_{\text{LUNAC}},T)=\tilde{O}(\bar{\xi}^{\frac{5}{4}}T^{\frac{3}{4}}+\bar{\xi}^{\frac{17}{12}}T^{\frac{7}{12}})$.

###  5.2 Distributionally Robust Optimization (DRO)

We suppose Assumption 3 holds for this subsection. The DRO approach is based
on the worst-case expected profit over an uncertainty set of demand
distributions. We let $\mu_{\text{r}}$ denote the retailer’s inventory
learning policy based on DRO. In each period $t$, the retailer has an
uncertainty set $\mathcal{D}_{t}\subset\mathcal{P}(\Xi)$ that he believes
contains the true market demand distribution. We consider uncertainty sets
which consist of distributions that are “close” to the empirical distribution
$\hat{F}^{\text{e}}_{t}$, and we measure closeness on $\mathcal{P}(\Xi)$ with
the $\phi-$divergence. Recall the $\phi-$divergence, denoted $d_{\phi}$, for
distributions $F,\,G\in\mathcal{P}(\Xi)$ with $F\ll G$ (where $F\ll G$ means
$F$ is absolutely continuous with respect to $G$) is defined by
$d_{\phi}(F,G)=\int_{\Xi}\phi\left(dF/dG\right)dG$ for a convex function
$\phi$ such that $\phi(1)=0$. Let $\epsilon_{t}\geq 0$ be the retailer’s
confidence level in period $t$. The retailer’s data-driven uncertainty sets
under $\mu_{\text{r}}$ are
$\mathcal{D}_{\epsilon_{t}}^{\phi}(\hat{F}^{\text{e}}_{t})\triangleq\\{F\in\mathcal{P}(\Xi)\mathrel{\mathop{\mathchar
58\relax}}d_{\phi}(F,\hat{F}^{\text{e}}_{t})\leq\epsilon_{t}\\}$. A retailer
who is more confident that $\hat{F}^{\text{e}}_{t}$ is close to the true
distribution $F_{0}$ should choose a smaller $\epsilon_{t}$, and vice versa.

The DRO literature has proposed multiple methods for choosing the confidence
level $\epsilon_{t}$, see the review by Rahimian and Mehrotra (2019). One way
is to leverage the asymptotic or finite sample performance of the uncertainty
set. In other words, we would choose $\epsilon_{t}$ so that the optimal value
of the DRO problem gives a finite sample guarantee on the retailer’s original
stochastic optimization problem.

Duchi et al. (2016) uses the optimal value of a DRO problem based on smooth
$\phi-$divergences to provide asymptotic confidence intervals for the optimal
value of the original (full information) stochastic optimization problem. We
will evaluate the performance of $\pi_{\text{LUNA}}$ and $\pi_{\text{LUNAC}}$
when $\epsilon_{t}$ is chosen by this method. Let $\chi^{2}_{1}$ be a Chi-
squared random variable with degree of freedom one.

###### Theorem 5.3

(Duchi et al. 2016, Theorem 4) Suppose the following conditions hold:

(i) The function $\phi\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}_{+}\to\mathbb{R}$ is convex, three times differentiable
in a neighborhood of $1$, and satisfies $\phi(1)=\phi^{\prime}(1)=0$.

(ii) There exists a measurable function $M\mathrel{\mathop{\mathchar
58\relax}}\Xi\to\mathbb{R}_{+}$ such that for all $\xi\in\Xi$,
$R(\cdot;w,\xi)$ is $M(\xi)-$Lipschitz with respect to some norm $\|\cdot\|$
on $\Xi$.

(iii) The function $R(\cdot;w,\xi)$ is proper and lower semi-continuous for
$F_{0}$-almost all $\xi\in\Xi$.
For any $\rho\geq 0$, let $\epsilon_{t}=\rho/t$ for all $t\geq 1$. Then,

$\lim_{t\to\infty}\mathds{P}\left(\max_{q\in\Xi}{\mathds{E}}_{F_{0}}[R(q;w,\xi)]\geq
l_{t}\right)=1-\frac{1}{2}\mathds{P}(\chi^{2}_{1}\geq\rho),$ (15)

where
$l_{t}\triangleq\max_{q\in\Xi}\inf_{F\in\mathcal{D}_{\epsilon_{t}}^{\phi}(\hat{F}^{\text{e}}_{t})}{\mathds{E}}_{F}[R(q;w,\xi)]$.

Theorem 5.3 says that the optimal value of the retailer’s problem with
knowledge of $F_{0}$ can be lower bounded by $l_{t}$ (the optimal value of the
DRO problem for uncertainty set
$\mathcal{D}_{\epsilon_{t}}^{\phi}(\hat{F}^{\text{e}}_{t})$) with probability
$1-\frac{1}{2}\mathds{P}(\chi^{2}_{1}\geq\rho)$, as $t\to\infty$ for
confidence levels $\epsilon_{t}=\rho/t$. Note that Assumption 3 must be
satisfied for this result to hold.

Let $\alpha\in[0,1]$ be a confidence level and $\chi^{2}_{1,\beta}$ denote the
$\beta-$quantile of the $\chi^{2}_{1}$ distribution. Theorem 5.3 suggests that
in order to ensure the asymptotic coverage of the optimal value as in Eq.
(15), the confidence levels should be chosen as

$\epsilon_{t}=\chi_{1,1-2\alpha}^{2}/(t-1),\,\forall t\geq 2.$ (16)

Confidence levels chosen in this way are usually overly conservative, and the
retailer may choose a smaller $\epsilon_{t}$ in practice. In this case, we get
a conservative estimate of $V$ by this method.

Under $\mu_{\text{r}}$, in period $t$ the retailer orders

$q^{r}_{t}\in\arg\max_{q\geq
0}\min_{F\in\mathcal{D}_{\epsilon_{t}}^{\phi}(\hat{F}^{\text{e}}_{t})}\,{\mathds{E}}_{F}[R(q;w_{t},\xi)].$
(17)

The objective in Eq. (17) is the retailer’s worst-case expected profit. Then,
corresponding to $q^{r}_{t}$, the perceived distribution

$\hat{F}_{t}^{\text{d}}\in\arg\min_{F\in\mathcal{D}_{\epsilon_{t}}^{\phi}(\hat{F}^{\text{e}}_{t})}{\mathds{E}}_{F}[R(q^{r}_{t};w_{t},\xi)],$

is the distribution in
$\mathcal{D}_{\epsilon_{t}}^{\phi}(\hat{F}^{\text{e}}_{t})$ which attains the
worst-case expected profit (which also depends on $w_{t}$).

We consider three widely used $\phi-$divergences: the KL-divergence $d_{KL}$
(where $\phi(x)=x\log(x)$), the $\chi^{2}-$distance $d_{\chi^{2}}$ (where
$\phi(x)=(x-1)^{2}$), and the Hellinger distance $d_{H}$ (where
$\phi(x)=\left(\sqrt{x}-1\right)^{2}$). For these three, Proposition 5.4 upper
bounds the total variation $V$ of the sequence
$\hat{F}_{1\mathrel{\mathop{\mathchar 58\relax}}T}^{\text{d}}$ as a function
of $\epsilon_{1\mathrel{\mathop{\mathchar
58\relax}}T}=(\epsilon_{t})_{t=1}^{T}$.

###### Proposition 5.4

Under Assumption 3, suppose the retailer follows $\mu_{\text{r}}$ with
confidence levels $\epsilon_{1\mathrel{\mathop{\mathchar 58\relax}}T}$.

(i) If $d_{\phi}=d_{KL}$, then
$\mu_{r}\in\mathcal{M}\left(\log(T)+1+\sum^{T}_{t=1}\sqrt{2\epsilon_{t}},T\right)$.

(ii) If $d_{\phi}=d_{\chi^{2}}$, then
$\mu_{r}\in\mathcal{M}\left(\log(T)+1+\sum^{T}_{t=1}\sqrt{\epsilon_{t}},T\right)$.

(iii) If $d_{\phi}=d_{H}$, then
$\mu_{r}\in\mathcal{M}\left(\log(T)+1+2\sum^{T}_{t=1}\epsilon_{t},T\right)$.

Using the specific choice of $\epsilon_{2\mathrel{\mathop{\mathchar
58\relax}}T}$ in Eq. (16) and $\epsilon_{1}$ = 1, Theorem 5.5 characterizes
the performance of $\pi_{\text{LUNA}}$ and $\pi_{\text{LUNAC}}$ for
$d_{\phi}\in\\{d_{KL},d_{\chi^{2}},d_{H}\\}$. Theorem 5.5 follows directly
from Theorem 4.5, Theorem 4.12, and Proposition 5.4.

###### Theorem 5.5

Suppose Assumptions 3 and 3 hold, and suppose the retailer follows
$\mu_{\text{r}}$ where $\epsilon_{1\mathrel{\mathop{\mathchar 58\relax}}T}$
are chosen as in Eq. (16).

(i) If $d_{\phi}\in\\{d_{KL},d_{\chi^{2}}\\}$, then
$\text{Reg}(\pi_{\text{LUNAC}},T)=\tilde{O}\big{(}\bar{\xi}^{\frac{17}{12}}T^{\frac{11}{12}}\big{)}$.

(ii) If $d_{\phi}=d_{H}$ and $F_{0}$ has support on $\mathcal{Y}_{M}$, then
$\text{Reg}(\pi_{\text{LUNA}},T)=\tilde{O}(\bar{\xi}^{\frac{4}{3}}M^{\frac{1}{3}}T^{\frac{2}{3}}+\bar{\xi}^{\frac{4}{3}}M^{-\frac{1}{3}}T^{\frac{2}{3}})$.

(iii) If $d_{\phi}=d_{H}$ and $F_{0}$ has support on $[0,\bar{\xi}]$, then
$\text{Reg}(\pi_{\text{LUNAC}},T)=\tilde{O}(\bar{\xi}^{\frac{5}{4}}T^{\frac{3}{4}}+\bar{\xi}^{\frac{17}{12}}T^{\frac{7}{12}})$.

###  5.3 Parametric Approach

We continue to suppose Assumption 3 is in force for this subsection. We
additionally suppose that the retailer has a parametric model for $F_{0}$
determined by the parameter $\theta\in\mathbb{R}^{d}$. Let
$\Theta\subset\mathbb{R}^{d}$ be the set of admissible parameter values, and
let $\\{F_{\theta}\\}_{\theta\in\Theta}$ be the corresponding parametric
family. If $F_{0}$ belongs to a parametric family, then Assumption 3 is not
likely to be satisfied (since many parametric distributions such as the normal
and exponential distributions have unbounded support). In this case, we relax
to the following assumption.

The retailer’s order quantity is upper bounded by $\bar{q}$. That is, for any
$w_{t}$ and $\hat{F}^{\mu}_{t}$, the retailer’s order satisfies
$q(w_{t};\hat{F}^{\mu}_{t})=\min\\{\min\\{q\mathrel{\mathop{\mathchar
58\relax}}\hat{F}^{\mu}_{t}(q)\geq 1-w_{t}/s\\},\bar{q}\\}$. Assumption 5.3
states that even if the supplier’s price $w_{t}$ is low enough and the
perceived distribution $\hat{F}^{\mu}_{t}$ has unbounded support, the retailer
will not place arbitrarily large orders. Assumption 5.3 is also consistent
with practical constraints, e.g., warehouse and transportation capacity.

We consider three specific methods for the parametric setting: (i) maximum
likelihood estimation (MLE); (ii) operational statistics; and (iii) the
parametric Bayesian approach.

####  5.3.1 Maximum likelihood Estimation (MLE)

We focus on MLE for the exponential family, where a distribution belongs to
the exponential family if its probability density function $f(x;\theta)$ for
$x$ in its support can be written as:

$f(x;\theta)=h(x)\exp{\left(\eta(\theta)^{T}\cdot T(x)-A(\theta)\right)}.$
(18)

In Eq. (18), $\eta(\theta)$ is the natural parameter, $T(x)$ is the sufficient
statistic, $h(x)$ is the base measure, and $A(\theta)$ is the log-partition
function which normalizes the density function. The exponential family
includes the Poisson and Categorical distributions (for discrete demand), and
the Normal and Exponential distributions (for continuous demand).

We let $\mu_{\text{m}}$ denote the retailer policy based on MLE. Under
$\mu_{\text{m}}$, the retailer produces an estimate $\theta_{t}$ of $\theta$
in each period $t$ by maximizing the likelihood function of the past demand
samples. This procedure has a special form for the exponential family. Let
$\mu\triangleq{\mathds{E}}_{F_{\theta}}[T(\xi)]$, then the MLE for $\mu$ based
on demand samples $(\xi_{i})_{i=1}^{t-1}$ is:

$\mu_{t}=\frac{\sum^{t-1}_{i=1}T(\xi_{i})}{t-1},\,t\geq 2.$

One can then obtain the estimator $\theta_{t}$ for $\theta$ through the
estimator $\mu_{t}$ for $\mu$ by the relationship between $\mu$ and $\theta$,
which depends on the particular distribution. Under $\mu_{\text{m}}$, in each
period $t\in[T]$, the retailer’s perceived distribution is the fitted
distribution

$\begin{split}\hat{F}_{t}^{\text{m}}(x)=\begin{cases}F_{\theta_{t}}(x),\,&0\leq
x<\bar{q};\\\ 1,\,&x\geq\bar{q}.\end{cases}\end{split}$ (19)

This sequence satisfies Assumption 2.1 and the discontituity in
$\hat{F}^{m}_{t}$ is introduced by Assumption 5.3. The retailer then orders
$q^{\text{m}}_{t}=q_{t}(w_{t},\hat{F}_{t}^{\text{m}})$ where
$q_{t}(w_{t},\hat{F}_{t}^{\text{m}})=\min\\{\min\\{q\mathrel{\mathop{\mathchar
58\relax}}F_{\theta_{t}}(q)\geq 1-w/s\\},\bar{q}\\}$.

We will investigate the variation of $\hat{F}_{1\mathrel{\mathop{\mathchar
58\relax}}T}^{m}$ for some canonical distributions in the exponential family.
Let ${\rm P}(\lambda)$ denote the Poisson distribution with mean $\lambda$;
let ${\rm C}(M)$ denote the categorical distribution with support size $M$;
let ${\rm E}(\lambda)$ denote the exponential distribution with rate
$\lambda$; and let ${\rm N}(\mu,\sigma^{2})$ denote the normal distribution
with mean $\mu$ and variance $\sigma^{2}$.

In Proposition 5.6, we derive the total variation of
$\hat{F}_{1\mathrel{\mathop{\mathchar 58\relax}}T}^{m}$. Note the categorical
distribution has bounded support so it automatically satisfies Assumption 5.3.

###### Proposition 5.6

Suppose the retailer follows $\mu_{\text{m}}$.

(i) If $F_{0}={\rm P}(\lambda)$, then
$\mu_{m}\in\mathcal{M}\left((\ln{(T)}+1)\left(4\ln{(T)}+2\lambda\right),T\right)$
with probability at least $1-1/T$.

(ii) If $F_{0}={\rm C}(M)$, then
$\mu_{m}\in\mathcal{M}\left(\ln{(T+1)},T\right)$.

(iii) If $F_{0}={\rm E}(\lambda)$, then
$\mu_{m}\in\mathcal{M}\left(16\ln{(2T^{2})}-1+\left(1+2\ln{(2T^{2})}\right)(\ln{(T)}+1),T\right)$
with probability at least $1-1/T$.

(iv) If $F_{0}={\rm N}(\mu,\sigma^{2})$, with $\sigma^{2}$ known and $\mu$
unknown to the retailer, then
$\mu_{m}\in\mathcal{M}\left(1+\frac{1}{\sigma}\sqrt{(\ln(T)+1)\left(\mu^{2}+2\sigma^{2}\ln{(2T^{2})}\right)},T\right)$
with probability at least $1-1/T$.

The next result on the supplier’s regret bound follows directly from Theorem
4.5, Theorem 4.12, and Proposition 5.6.

###### Theorem 5.7

Suppose the retailer follows $\mu_{\text{m}}$.

(i) Suppose $F_{0}={\rm P}(\lambda)$, then
$\text{Reg}(\pi_{\text{LUNAC}},T)=\tilde{O}(\bar{q}^{\frac{5}{4}}T^{\frac{3}{4}}+\bar{q}^{\frac{17}{12}}T^{\frac{7}{12}})$
with probability at least $1-1/T$.

(ii) Suppose $F_{0}={\rm C}(M)$, then
$\text{Reg}(\pi_{\text{LUNA}},T)=\tilde{O}(\bar{q}^{\frac{4}{3}}M^{\frac{1}{3}}T^{\frac{2}{3}})$.

(iii) Suppose $F_{0}={\rm E}(\lambda)$, then
$\text{Reg}(\pi_{\text{LUNAC}},T)=\tilde{O}(\bar{q}^{\frac{5}{4}}T^{\frac{3}{4}}+\bar{q}^{\frac{17}{12}}T^{\frac{7}{12}})$
with probability at least $1-1/T$.

(iv) Suppose $F_{0}={\rm N}(\mu,\sigma^{2})$, then
$\text{Reg}(\pi_{\text{LUNAC}},T)=\tilde{O}(\bar{q}^{\frac{5}{4}}T^{\frac{3}{4}}+\bar{q}^{\frac{17}{12}}T^{\frac{7}{12}})$
with probability at least $1-1/T$.

####  5.3.2 Operational Statistics

Here we suppose $F_{0}={\rm E}(\lambda)$, the exponential distribution with an
unknown rate $\lambda>0$. Liyanage and Shanthikumar (2005), Chu et al. (2008)
propose the operational statistics approach for the retailer facing
exponential demand with unknown rate. In this approach, the retailer first
specifies a class of admissible policies, then finds a policy within this
class to maximize his out-of-sample expected profit.

We let $\mu_{\text{o}}$ denote the retailer’s inventory policy based on
operational statistics, which is implemented as follows. According to Liyanage
and Shanthikumar (2005), given wholesale price $w_{t}$ and i.i.d. demand
samples $(\xi_{i})_{i=1}^{t-1}$, the retailer’s order quantity that maximizes
his out-of-sample expected profit is
$(t-1)\left(\left(\frac{s}{w_{t}}\right)^{\frac{1}{t}}-1\right)\frac{\sum^{t-1}_{i=1}\xi_{i}}{t-1}$
for $t\geq 2$. The order quantity is directly determined by the data, and its
derivation does not involve estimating $\lambda$. However, we still can find a
sequence of distributions $\hat{F}^{\text{o}}_{2\mathrel{\mathop{\mathchar
58\relax}}T}$ satisfying Assumption 2.1 that map $w_{t}$ to the order quantity
under operational statistics. For all $t\geq 2$, define the rates
$\lambda_{t}$ so that
$\frac{1}{\lambda_{t}}=\frac{(t-1)\left(\left(\frac{s}{w_{t}}\right)^{\frac{1}{t}}-1\right)\left(\frac{\sum^{t-1}_{i=1}\xi_{i}}{t-1}\right)}{\ln\left(\frac{s}{w_{t}}\right)}$,
and then set the perceived distribution to be

$\hat{F}^{\text{o}}_{t}(x)=\begin{cases}{\rm E}(\lambda_{t})(x),\,&0\leq
x<\bar{q},\\\ 1,\,&x\geq\bar{q}.\end{cases}$

Then, under $\mu_{\text{o}}$ the retailer equivalently solves
$q^{\text{o}}_{t}=q(w_{t},\hat{F}^{\text{o}}_{t})$ where
$q(w_{t},\hat{F}^{\text{o}}_{t})=\min\\{\min\\{q\mathrel{\mathop{\mathchar
58\relax}}{\rm E}(\lambda_{t})(q)\geq 1-w/s\\},\bar{q}\\}$ for all $t\geq 2$.

We now derive the total variation of
$\hat{F}^{\text{o}}_{1\mathrel{\mathop{\mathchar 58\relax}}T}$.

###### Proposition 5.8

Suppose $F_{0}={\rm E}(\lambda)$, and the retailer follows $\mu_{\text{o}}$.
Then,
$\mu_{o}\in\mathcal{M}\left(21+40\ln{(T)}+4(\ln{(T)})^{2},T\right)$ with
probability at least $1-1/T$.

###### Theorem 5.9

Suppose $F_{0}={\rm E}(\lambda)$, and the retailer follows $\mu_{\text{o}}$.
Then,
$\text{Reg}(\pi_{\text{LUNAC}},T)=\tilde{O}(\bar{q}^{\frac{5}{4}}T^{\frac{3}{4}}+\bar{q}^{\frac{17}{12}}T^{\frac{7}{12}})$
with probability at least $1-1/T$.

####  5.3.3 Parametric Bayesian approach

We now suppose demand is ${\rm E}(\Lambda)$ where the rate $\Lambda$ is random
and has a gamma prior distribution $f_{\Lambda}$ with parameter
$\alpha,\beta>0$, i.e.,
$f_{\Lambda}(\lambda)=\frac{(\beta/\lambda)^{\alpha+1}}{\beta\Gamma(\alpha)}\exp\\{-\beta/\lambda\\}$.
Exponential demand distributions with a gamma prior are widely studied in the
OM literature (Azoury 1985).

We let $\mu_{\text{b}}$ denote the retailer’s inventory learning policy under
the Bayesian approach. Given $w_{t}$, the retailer orders

$\arg\max_{q\geq 0}\,\int_{0}^{\infty}{\mathds{E}}_{{\rm
E}(\Lambda)}[R(q;w_{t},\xi)]f_{\Lambda|(\xi_{i})^{t-1}_{i=1}}\left(\lambda\right)d\lambda,$
(20)

where $f_{\Lambda|(\xi_{i})^{t-1}_{i=1}}$ is the posterior density function
with respect to the demand samples from the previous $t-1$ periods. Lim et al.
(2006) show that the retailer’s optimal order quantity as a solution to Eq.
(20) is
$\left(\beta+\sum^{t-1}_{i=1}\xi_{i}\right)\left(\left(\frac{s}{w_{t}}\right)^{1/(\alpha+t-1)}-1\right)$.
For all $t\in[T]$, define the rates $\lambda_{t}$ so that

$\frac{1}{\lambda_{t}}=\frac{\left(\beta+\sum^{t-1}_{i=1}\xi_{i}\right)\left(\left(s/w_{t}\right)^{\frac{1}{\alpha+t-1}}-1\right)}{\ln\left(s/w_{t}\right)},$

and then set

$\hat{F}^{b}_{t}=\begin{cases}{\rm E}(\lambda_{t})(x),\,&0\leq x<\bar{q},\\\
1,\,&x\geq\bar{q}.\end{cases}$

Then, $\hat{F}^{b}_{t}$ is the retailer’s perceived distribution that maps the
supplier’s wholesale price $w_{t}$ to the retailer’s order quantity
$q^{b}_{t}$ via $q^{b}_{t}=q(w_{t},\hat{F}^{b}_{t})$ where
$q(w_{t},\hat{F}^{b}_{t})=\min\\{\min\\{q\mathrel{\mathop{\mathchar
58\relax}}{\rm E}(\lambda_{t})(q)\geq 1-w/s\\},\bar{q}\\}$.

We derive the total variation of $\hat{F}^{b}_{1\mathrel{\mathop{\mathchar
58\relax}}T}$ similarly to Proposition 5.8, and so we omit the proof.

###### Proposition 5.10

Suppose demand is exponentially distributed with mean $1/\lambda$ and the
retailer follows $\mu_{\text{b}}$. Then,
$\mu_{\text{b}}\in\mathcal{M}(18(\alpha+1)+(40\alpha+39)\ln{(T)}+4(\alpha+1)(\ln{(T)})^{2},T)$
with probability at least $1-1/T$.

Next we bound the regret of $\pi_{\text{LUNAC}}$ when the retailer follows
$\mu_{\text{b}}$.

###### Theorem 5.11

Suppose the retailer follows $\mu_{\text{b}}$. Then,
$\text{Reg}(\pi_{\text{LUNAC}},T)=\tilde{O}(\bar{q}^{\frac{5}{4}}T^{\frac{3}{4}}+\bar{q}^{\frac{17}{12}}T^{\frac{7}{12}})$
with probability at least $1-1/T$.

##  6 Numerical Experiments

###  6.1 Empirical Performance

We evaluate the empirical performance of $\pi_{\text{LUNA}}$ when the true
market demand distributions $F_{1\mathrel{\mathop{\mathchar 58\relax}}T}$ are
discrete. In order to control the total variation of
$\hat{F}^{\mu}_{1\mathrel{\mathop{\mathchar 58\relax}}T}$, we directly
construct $\hat{F}_{1\mathrel{\mathop{\mathchar 58\relax}}T}^{\mu}$ as
follows. For $t\in[T]$, we set $\hat{F}_{t}^{\mu}$ to be the CDF of a
Bernoulli random variable which takes values $0$ and $1$ with probabilities
$p_{t,0}$ and $p_{t,1}=1-p_{t,0}$, respectively, and let

$p_{t,0}=\frac{1}{2}+\frac{3}{10}\sin{\frac{5V\pi t}{3T}},\,t\in[T],$ (21)

for fixed $V>0$. Then, the total variation satisfies

$\sum^{T-1}_{t=1}d_{K}(\hat{F}^{\mu}_{t},\hat{F}^{\mu}_{t+1})=C\,V,$

for some constant $C>0$.

Figure 1: Performance of $\pi_{\text{LUNA}}$ for discrete distributions

Figure 1 shows the dynamic regret of $\pi_{\text{LUNA}}$ as a function of the
number of rounds when $K$ is optimally chosen (assuming the supplier knows
$V$, with shorthand ‘opt-$K$’) and obliviously chosen (assuming the supplier
does not know $V$, with shorthand ‘obl-$K$’). We take different values of $V$
to compare the growth rate of the regret for the same pricing policy. The
regrets are plotted on a log-log scale, so the slope in this plot corresponds
to the exponent of the regret, i.e., the slope is $\alpha$ if the regret grows
in $\Theta(T^{\alpha})$.

We see that the slope roughly matches our theoretical results (see Theorem
4.5). When $V=1$, the regret bounds corresponding to opt-$K$ and obl-$K$
overlap. When $V=T^{1/3}$, opt-$K$ grows more slowly than obl-$K$ but has a
smaller constant term than opt-K (we did not optimize for the constant terms).
Also notice that the gap in the regret bounds between opt-K and obl-$K$ is
small (i.e., the regret bounds for opt-$K$ and obl-$K$ are respectively
$\tilde{O}(V^{\frac{1}{3}}T^{\frac{2}{3}})$ and
$\tilde{O}(V^{\frac{2}{3}}T^{\frac{2}{3}})$, and the gap is
$V^{\frac{1}{3}}$). Even when $K$ is optimally chosen, obl-$K$ can have better
performance than opt-$K$ within a large range of $T$ (in our case, $T\leq
2\times 10^{5}$) because of the constant terms dominating the regret bounds.

###  6.2 Comparison between Different Algorithms

In this subsection, we compare $\pi_{\text{LUNA}}$ with some pricing policies
that are designed for non-stationary bandits. Specifically, we compare
$\pi_{\text{LUNA}}$ with the following benchmarks:

  1. 1.

The Exp3.S algorithm by Besbes et al. (2014a), which is designed for non-
stationary multi-armed bandits with known variation budget $B_{T}$. Notice we
distinguish $B_{T}$ from our variation budget $V$ because $B_{T}$ refers to
the norm of variation in the mean bandit feedback and $V$ refers to the total
Kolmogorov variation in the sequence
$\hat{F}^{\mu}_{1\mathrel{\mathop{\mathchar 58\relax}}T}$. The regret upper
bound for Exp3.S is
$\tilde{O}(d^{\frac{1}{3}}B^{\frac{1}{3}}_{T}T^{\frac{2}{3}})$ with $d$ arms,
see Besbes et al. (2014a).

  2. 2.

The deterministic non-stationary bandit algorithm proposed by Karnin and Anava
(2016) for multi-armed bandits with unknown variation budget $B_{T}$. The
regret upper bound for this algorithm is
$\tilde{O}(d^{\frac{1}{2}}T^{\frac{1}{2}}+d^{\frac{1}{3}}B^{\frac{1}{3}}_{T}T^{\frac{2}{3}})$.

  3. 3.

The Master+UCB1 algorithm proposed by Wei and Luo (2021) for non-stationary
stochastic bandits with unknown variation budget $B_{T}$. The regret upper
bound is $\tilde{O}(B^{\frac{1}{3}}_{T}T^{\frac{2}{3}})$.

We note that all of these pricing policies are designed for problems with
finitely many admissible decisions. For fair comparison, we developed a
version of $\pi_{\text{LUNA}}$ that works when $\mathcal{W}$ is finite which
we call $\pi_{\text{LUNAF}}$ (see Appendix 12). Since Exp3.S requires the
variation budget $B_{T}$ as an input, we calculate $V$ in our problem and
simply let $B_{T}=V$.

Figure 2: Performance comparison

Figure 3: Performance comparison

_Notes:_ (Left) $\hat{F}_{t}^{\mu}$ is set according to Eq. (21). (Right)
$\hat{F}_{t}$ is the CDF of the Bernoulli distribution and the retailer adopts
SAA.

We compare the regret of these benchmark algorithms with $\pi_{\text{LUNAF}}$
in Figure 3 and Figure 3. In Figure 3, we directly simulated the retailer’s
ordering decisions by setting $\hat{F}_{t}^{\mu}$ as in Eq. (21). In Figure 3,
we set the true distribution $F_{t}$ to be Bernoulli which takes values $0$
and $1$ with probabilities $p_{t}$ and $1-p_{t}$ respectively where $p_{t}$ is
also determined by Eq. (21), i.e.,

$p_{t}=\frac{1}{2}+\frac{3}{10}\sin{\frac{5V\pi t}{3T}},\,t\in[T],$

in which case the true market demand distribution is non-stationary. We also
suppose the retailer follows $\mu_{\text{e}}$. In both experiments, we let
$\mathcal{W}$ contain $d=\lceil T^{\frac{1}{2}}\rceil$ equally spaced prices
lying in $[0,s]$.

From Figures 3 and 3, we see that $\pi_{\text{LUNAF}}$ outperforms the
benchmarks, and the performance of the benchmarks is relatively close to each
other. These results suggest that the supplier benefits from using the
structure of the profit function in her pricing policy, instead of applying a
black box algorithm. In addition, based on the results in Figure 3, we see
$\pi_{\text{LUNAF}}$ still performs well even when the true market demand
distribution is non-stationary.

###  6.3 Experiment on Semi-synthetic Data Set

For our final experiment, we collected the weekly sales data of avocados in
California from $2020$ to $2022$ (Hass Avocado Board 2022). Avocado sales can
be non-stationary and vary from month to month, see, e.g., Keskin et al.
(2021). In order to approximate this non-stationarity, we first group the
weekly sales data by month $m=\\{1,\ldots,12\\}$. Then, to generate the daily
sales in month $m$, we divide the weekly sales in month $m$ by $7$ and treat
it as a sample of daily demand in month $m$. We repeat this procedure for all
the weeks from $2020$ to $2022$ to get demand samples for each month of the
year. Finally, we divide the daily sales by $1,000,000$ and round it to the
nearest integer to build an approximate discrete daily demand distribution for
avocados (in millions of units). Given the daily demand samples for each
month, we then bootstrap the daily demand for a planning horizon of $T$ days
(assuming the first day in the horizon starts on Jan $1$st). In this way, we
generate random demand realizations for the retailer.

Figure 4: Performance comparison

We suppose the retailer follows $\mu_{\text{e}}$, and $\mathcal{W}$ has
cardinality $d=\lceil T^{\frac{1}{2}}\rceil$. We compare the performance of
the pricing policies for this setting in Figure 4. We see that
$\pi_{\text{LUNAF}}$ outperforms the other policies in this setting as well.
Exp3.S and Master-UCB1 have almost identical performance here, and the
deterministic non-stationary bandit algorithm by Karnin and Anava (2016)
outperforms both Exp3.S and Master-UCB1. This application further demonstrates
that our pricing policy performs well even for non-stationary demand
distributions.

##  7 Conclusion

In this paper, we studied the supplier’s pricing problem facing a retailer who
is learning the demand distribution and employs data-driven inventory learning
policies. We model the non-stationarity of the retailer’s inventory decisions
through the non-stationarity of his “perceived” distributions. Then, we use
the Kolmogorov distance to measure the variation of the retailer’s perceived
distributions and identify a tractable class of retailer policies. For both
discrete and continuous demand distributions, we proposed pricing policies for
the supplier and derived sublinear regret upper bounds. Our main conclusion is
that the supplier can achieve asymptotically vanishing regret, even when the
retailer is also learning the demand distribution, as long as the retailer’s
inventory policies belong to a reasonable class with bounded variation.

Much of the literature on optimization and learning in OM focuses on learning
the random demand or unknown demand-price relationship. However, our work
investigates the important problem of learning the learning policies
implemented by a secondary agent in a multi-agent setting. This study brings
new perspectives into learning in multi-agent problems in supply chain and
inventory management, where the controller must learn to react to the learning
policies by other agents in the system.

At the same time, we acknowledge some directions for future research. First,
it is worth investigating information-theoretic lower bounds on the supplier’s
regret in our problem setting. Second, it may be possible to improve the
supplier’s regret bound when the non-stationarity has additional structure
(e.g., seasonal demand patterns).

## References

  * Adell and Jodrá (2006) Adell JA, Jodrá P (2006) Exact kolmogorov and total variation distances between some familiar discrete distributions. _Journal of Inequalities and Applications_ 2006:1–8.
  * Auer et al. (2002) Auer P, Cesa-Bianchi N, Freund Y, Schapire RE (2002) The nonstochastic multiarmed bandit problem. _SIAM journal on computing_ 32(1):48–77.
  * Auer et al. (2019) Auer P, Chen Y, Gajane P, Lee CW, Luo H, Ortner R, Wei CY (2019) Achieving optimal dynamic regret for non-stationary bandits without prior information. _Conference on Learning Theory_ , 159–163 (PMLR).
  * Auer et al. (2018) Auer P, Gajane P, Ortner R (2018) Adaptively tracking the best arm with an unknown number of distribution changes .
  * Auer et al. (2008) Auer P, Jaksch T, Ortner R (2008) Near-optimal regret bounds for reinforcement learning. _Advances in neural information processing systems_ 21\.
  * Azoury (1985) Azoury KS (1985) Bayes solution to dynamic inventory models under unknown demand distribution. _Management science_ 31(9):1150–1160.
  * Ban and Keskin (2021) Ban GY, Keskin NB (2021) Personalized dynamic pricing with machine learning: High-dimensional features and heterogeneous elasticity. _Management Science_ 67(9):5549–5568.
  * Besbes et al. (2014a) Besbes O, Gur Y, Zeevi A (2014a) Optimal exploration-exploitation in multi-armed-bandit problems with non-stationary rewards. Technical report, Columbia Business School Working paper.
  * Besbes et al. (2014b) Besbes O, Gur Y, Zeevi A (2014b) Stochastic multi-armed-bandit problem with non-stationary rewards. _Advances in neural information processing systems_ 27\.
  * Besbes et al. (2015) Besbes O, Gur Y, Zeevi A (2015) Non-stationary stochastic optimization. _Operations research_ 63(5):1227–1244.
  * Besbes and Zeevi (2011) Besbes O, Zeevi A (2011) On the minimax complexity of pricing in a changing environment. _Operations research_ 59(1):66–79.
  * Besson and Kaufmann (2019) Besson L, Kaufmann E (2019) The generalized likelihood ratio test meets klucb: an improved algorithm for piece-wise non-stationary bandits. _Proceedings of Machine Learning Research vol XX_ 1:35.
  * Birge et al. (2021) Birge JR, Chen H, Keskin NB, Ward A (2021) To interfere or not to interfere: Information revelation and price-setting incentives in a multiagent learning environment. _Available at SSRN 3864227_ .
  * Broder and Rusmevichientong (2012) Broder J, Rusmevichientong P (2012) Dynamic pricing under a general parametric choice model. _Operations Research_ 60(4):965–980.
  * Bubeck et al. (2011) Bubeck S, Munos R, Stoltz G, Szepesvári C (2011) X-armed bandits. _Journal of Machine Learning Research_ 12(5).
  * Cachon (2003) Cachon GP (2003) Supply chain coordination with contracts. _Handbooks in operations research and management science_ 11:227–339.
  * Cao et al. (2019) Cao Y, Wen Z, Kveton B, Xie Y (2019) Nearly optimal adaptive procedure with change detection for piecewise-stationary bandit. _The 22nd International Conference on Artificial Intelligence and Statistics_ , 418–427 (PMLR).
  * Chen et al. (2022a) Chen BB, Simchi-Levi D, Wang Y, Zhou Y (2022a) Dynamic pricing and inventory control with fixed ordering cost and incomplete demand information. _Management Science_ 68(8):5684–5703.
  * Chen et al. (2022b) Chen BB, Wang Y, Zhou Y (2022b) Optimal policies for dynamic pricing and inventory control with nonparametric censored demands. _Management Science_ .
  * Chen and Chen (2015) Chen M, Chen ZL (2015) Recent developments in dynamic pricing research: multiple products, competition, and limited demand information. _Production and Operations Management_ 24(5):704–731.
  * Chen et al. (2020) Chen N, Wang C, Wang L (2020) Learning and optimization with seasonal patterns. _arXiv preprint arXiv:2005.08088_ .
  * Chen et al. (2019a) Chen X, Wang Y, Wang YX (2019a) Nonstationary stochastic optimization under $l_{p,q}$-variation measures. _Operations Research_ 67(6):1752–1765.
  * Chen et al. (2019b) Chen Y, Lee CW, Luo H, Wei CY (2019b) A new algorithm for non-stationary contextual bandits: Efficient, optimal and parameter-free. _Conference on Learning Theory_ , 696–726 (PMLR).
  * Cheung et al. (2017) Cheung WC, Simchi-Levi D, Wang H (2017) Dynamic pricing and demand learning with limited price experimentation. _Operations Research_ 65(6):1722–1731.
  * Cheung et al. (2019) Cheung WC, Simchi-Levi D, Zhu R (2019) Learning to optimize under non-stationarity. _The 22nd International Conference on Artificial Intelligence and Statistics_ , 1079–1087 (PMLR).
  * Cheung et al. (2021) Cheung WC, Simchi-Levi D, Zhu R (2021) Hedging the drift: Learning to optimize under nonstationarity. _Management Science_ .
  * Chu et al. (2008) Chu LY, Shanthikumar JG, Shen ZJM (2008) Solving operational statistics via a bayesian analysis. _Operations Research Letters_ 36(1):110–116.
  * Cormen et al. (2022) Cormen TH, Leiserson CE, Rivest RL, Stein C (2022) _Introduction to algorithms_ (MIT press).
  * den Boer and Keskin (2020) den Boer AV, Keskin NB (2020) Discontinuous demand functions: estimation and pricing. _Management Science_ 66(10):4516–4534.
  * den Boer and Keskin (2022) den Boer AV, Keskin NB (2022) Dynamic pricing with demand learning and reference effects. _Management Science_ .
  * Duchi et al. (2016) Duchi J, Glynn P, Namkoong H (2016) Statistics of robust optimization: A generalized empirical likelihood approach. _arXiv preprint arXiv:1610.03425_ .
  * EY Americas (2020) EY Americas (2020) How the future of work will change the digital supply chain. https://www.ey.com/en_us/consulting/how-the-future-of-work-will-change-the-digital-supply-chain, accessed: 2022-10-04.
  * Ferreira et al. (2018) Ferreira KJ, Simchi-Levi D, Wang H (2018) Online network revenue management using thompson sampling. _Operations research_ 66(6):1586–1602.
  * Fu et al. (2018) Fu Q, Sim CK, Teo CP (2018) Profit sharing agreements in decentralized supply chains: a distributionally robust approach. _Operations Research_ 66(2):500–513.
  * Garivier and Moulines (2011) Garivier A, Moulines E (2011) On upper-confidence bound policies for switching bandit problems. _International Conference on Algorithmic Learning Theory_ , 174–188 (Springer).
  * Gibbs and Su (2002) Gibbs AL, Su FE (2002) On choosing and bounding probability metrics. _International statistical review_ 70(3):419–435.
  * Hass Avocado Board (2022) Hass Avocado Board (2022) Volume data and category data. URL https://hassavocadoboard.com/.
  * Ho et al. (2016) Ho CJ, Slivkins A, Vaughan JW (2016) Adaptive contract design for crowdsourcing markets: Bandit algorithms for repeated principal-agent problems. _Journal of Artificial Intelligence Research_ 55:317–359.
  * Jia et al. (2022) Jia H, Shi C, Shen S (2022) Online learning and pricing for network revenue management with reusable resources. _Available at SSRN 4225832_ .
  * Kalkanci et al. (2011) Kalkanci B, Chen KY, Erhun F (2011) Contract complexity and performance under asymmetric demand information: An experimental evaluation. _Management science_ 57(4):689–704.
  * Karnin and Anava (2016) Karnin ZS, Anava O (2016) Multi-armed bandits: Competing with optimal sequences. _Advances in Neural Information Processing Systems_ 29:199–207.
  * Keskin and Birge (2019) Keskin NB, Birge JR (2019) Dynamic selling mechanisms for product differentiation and learning. _Operations research_ 67(4):1069–1089.
  * Keskin et al. (2022) Keskin NB, Li Y, Song JS (2022) Data-driven dynamic pricing and ordering with perishable inventory in a changing environment. _Management Science_ 68(3):1938–1958.
  * Keskin et al. (2021) Keskin NB, Min X, Song JSJ (2021) The nonstationary newsvendor: Data-driven nonparametric learning. _Available at SSRN 3866171_ .
  * Keskin and Zeevi (2017) Keskin NB, Zeevi A (2017) Chasing demand: Learning and earning in a changing environment. _Mathematics of Operations Research_ 42(2):277–307.
  * Kleinberg et al. (2013) Kleinberg R, Slivkins A, Upfal E (2013) Bandits and experts in metric spaces. _arXiv preprint arXiv:1312.1277_ .
  * Kleywegt et al. (2002) Kleywegt AJ, Shapiro A, Homem-de Mello T (2002) The sample average approximation method for stochastic discrete optimization. _SIAM Journal on Optimization_ 12(2):479–502.
  * Lattimore and Szepesvári (2020) Lattimore T, Szepesvári C (2020) _Bandit algorithms_ (Cambridge University Press).
  * Levi et al. (2015) Levi R, Perakis G, Uichanco J (2015) The data-driven newsvendor problem: new bounds and insights. _Operations Research_ 63(6):1294–1306.
  * Lim et al. (2006) Lim AE, Shanthikumar JG, Shen ZM (2006) Model uncertainty, robust optimization, and learning. _Models, Methods, and Applications for Innovative Decision Making_ , 66–94 (INFORMS).
  * Liu et al. (2018) Liu F, Lee J, Shroff N (2018) A change-detection based framework for piecewise-stationary multi-armed bandit problem. _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32.
  * Liyanage and Shanthikumar (2005) Liyanage LH, Shanthikumar JG (2005) A practical inventory control policy using operational statistics. _Operations Research Letters_ 33(4):341–348.
  * Luo et al. (2018) Luo H, Wei CY, Agarwal A, Langford J (2018) Efficient contextual bandits in non-stationary worlds. _Conference On Learning Theory_ , 1739–1776 (PMLR).
  * Perakis and Roels (2007) Perakis G, Roels G (2007) The price of anarchy in supply chains: Quantifying the efficiency of price-only contracts. _Management Science_ 53(8):1249–1268.
  * Rahimian and Mehrotra (2019) Rahimian H, Mehrotra S (2019) Distributionally robust optimization: A review. _arXiv preprint arXiv:1908.05659_ .
  * Wei et al. (2016) Wei CY, Hong YT, Lu CJ (2016) Tracking the best expert in non-stationary stochastic environments. _Advances in neural information processing systems_ 29\.
  * Wei and Luo (2021) Wei CY, Luo H (2021) Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach. _Conference on Learning Theory_ , 4300–4354 (PMLR).
  * Wei and Srivatsva (2018) Wei L, Srivatsva V (2018) On abruptly-changing and slowly-varying multiarmed bandit problems. _2018 Annual American Control Conference (ACC)_ , 6291–6296 (IEEE).
  * Yu and Kong (2020) Yu Y, Kong X (2020) Robust contract designs: Linear contracts and moral hazard. _Operations Research_ 68(5):1457–1473.
  * Zhang et al. (2021) Zhang K, Yang Z, Başar T (2021) Multi-agent reinforcement learning: A selective overview of theories and algorithms. _Handbook of Reinforcement Learning and Control_ 321–384.
  * Zhou et al. (2021) Zhou X, Xiong Y, Chen N, Gao X (2021) Regime switching bandits. _Advances in Neural Information Processing Systems_ 34\.

Electronic Companion

##  8 Additional material for Section 3

###  8.1 Proof of Theorem 3.1

We have

$\begin{split}\text{Reg}(\pi_{\text{stat}},T)&=\sum^{T}_{t=1}{\mathds{E}}\left[(w^{*}-c)q(w^{*};F_{0})-(w_{t}-c)q(w_{t};F_{0})\right]\\\
&=\sum^{\lceil\sqrt{T}\rceil}_{t=1}{\mathds{E}}\left[(w^{*}-c)q(w^{*};F_{0})-(w_{t}-c)q(w_{t};F_{0})\right]\\\
&+\sum^{T}_{t=\lceil\sqrt{T}\rceil+1}{\mathds{E}}\left[(w^{*}-c)q(w^{*};F_{0})-(w^{*}_{stat}-c)q(w^{*}_{stat};F_{0})\right]\\\
&\leq\lceil\sqrt{T}\rceil
s\bar{\xi}+(T-\lceil\sqrt{T}\rceil)s\bar{\xi}/\lceil\sqrt{T}\rceil\\\
&=O(\sqrt{T}),\end{split}$

where the first inequality follows from Eq. (5) and the fact that
$|w^{*}-w^{*}_{stat}|\leq s/\lceil\sqrt{T}\rceil$ by the discretization of
$\mathcal{W}$.

##  9 Additional material for Section 4

###  9.1 Proof of Lemma 4.1

Suppose $q(w_{m}^{t};\hat{F}_{t}^{\mu})\geq y_{m}$, then it follows from Eq.
(6) that $p_{t,m-1}\leq 1-w_{m}^{t}/s$, and
$\varphi(w_{m}^{t};\hat{F}_{t}^{\mu})\geq(w_{m}^{t}-c)y_{m}=\varphi_{k^{*}}+\Delta_{t}+\frac{y_{m}s}{K}$.
The previous inequality follows from the fact that
$q(w_{m}^{t};\hat{F}_{t}^{\mu})\geq y_{m}$ and the previous equality follows
by construction of $w_{m}^{t}$ (see Eq. (11)). The proof is similar for the
case $q(w_{m}^{t};\hat{F}_{t}^{\mu})<y_{m}$.

###  9.2 Proof of Lemma 4.2

We will show that if $q(w_{m}^{t};\hat{F}_{t}^{\mu})\geq y_{m}$, then

$\max_{k\in[K]}\max_{x\in[0,\bar{\xi}]}|\hat{F}_{t}^{\mu}(x)-\hat{F}_{\tau^{0}_{i}+k}^{\mu}(x)|\geq\Delta_{t}/(s\,\bar{\xi}).$
(22)

It will then follow from the reverse triangle inequality that the total
variation over epoch $i$ is:

$\sum^{\tau^{0}_{i+1}-1}_{t=\tau^{0}_{i}+1}\max_{x\in[0,\bar{\xi}]}|\hat{F}_{t+1}^{\mu}(x)-\hat{F}_{t}^{\mu}(x)|\geq\Delta_{t}/(s\bar{\xi}).$

Recall $(p_{\tau^{0}_{i}+k,m})_{k\in[K]}$ are the values of
$\hat{F}_{t}^{\mu}$ at $y_{m}$ during the exploration phase in epoch $i$
(i.e., for periods $t\in[\tau^{0}_{i}+1,\tau^{0}_{i}+K]$). To show Eq. (22),
we start with the following Lemma 9.1.

###### Lemma 9.1

During the exploration phase of epoch $i$, we must have

$\max_{k\in[K]}p_{\tau^{0}_{i}+k,m-1}\geq
1-\frac{\varphi_{k^{*}}/y_{m}+c}{s}-\frac{1}{K},$ (23)

for all $m\in[M]$ with $m\neq m^{*}$, where the term $\frac{1}{K}$ is due to
the discretization error.

###### Proof 9.2

Proof of Lemma 9.1 For a contradiction, suppose there exists some
$m^{\prime}\in[M]$ with $m^{\prime}\neq m^{*}$ such that

$s(1-p_{\tau^{0}_{i}+k,m^{\prime}})>\varphi_{k^{*}}/y_{m^{\prime}}+c+\frac{s}{K},\,\forall
k\in[K].$ (24)

We let $k^{\prime}\in[K]$ be such that
$\bar{w}_{k^{\prime}}\in[s(1-p_{\tau^{0}_{i}+k^{\prime},m^{\prime}-1})-\frac{s}{K},s(1-p_{\tau^{0}_{i}+k^{\prime},m^{\prime}-1})]$
(notice that such $k^{\prime}$ must exist by the discretization). We then have
$\varphi(\bar{w}_{k^{\prime}};\hat{F}_{\tau^{0}_{i}+k^{\prime}}^{\mu})=(\bar{w}_{k^{\prime}}-c)q(\bar{w}_{k^{\prime}};\hat{F}^{\mu}_{\tau^{0}_{i}+k^{\prime}})\geq(\bar{w}_{k^{\prime}}-c)y_{m^{\prime}}\geq(s-s\,p_{\tau^{0}_{i}+k,m^{\prime}-1}-c-\frac{s}{K})y_{m^{\prime}}>\varphi_{k^{*}}$
where the first inequality follows since $\bar{w}_{k^{\prime}}\leq
s(1-p_{\tau^{0}_{i}+k^{\prime},m^{\prime}-1})$ and then according to Eq. (8),
$q(\bar{w}_{k^{\prime}};\hat{F}^{\mu}_{\tau^{0}_{i}+k})\geq y_{m^{\prime}}$.
The second inequality follows since $\bar{w}_{k^{\prime}}\geq
s(1-p_{\tau^{0}_{i}+k^{\prime},m^{\prime}-1})-\frac{s}{K}$ and the last
inequality follows from Eq. (24). Thus we have shown that Eq. (24) is a
contradiction of the fact that $k^{*}\in\arg\max_{k\in[K]}\varphi_{k}$.

On the other hand, since $q(w_{m}^{t};F_{t})\geq y_{m}$ for some $m\in[M]$, we
have

$p_{t,m-1}\leq
1-w_{m}^{t}/s=1-\frac{(\varphi_{k^{*}}+\Delta_{t})/y_{m}+1/K+c}{s},$ (25)

where the inquality follows from Lemma 4.1 and the equality follows from Eq.
(11). Combining Eq. (23) and Eq. (25) gives:

$\max_{k\in[K]}(p_{\tau^{0}_{i}+k,m-1}-p_{t,m-1})\geq\Delta_{t}/(s\,y_{m})\geq\Delta_{t}/(s\bar{\xi}).$

It follows that
$\max_{k\in[K]}\max_{x\in[0,\bar{\xi}]}|\hat{F}_{\tau^{i}_{0}+k}^{\mu}(x)-\hat{F}_{t}^{\mu}(x)|\geq\Delta_{t}/(s\,\bar{\xi})$,
and the Lemma holds.

###  9.3 Proof of Lemma 4.3

There are two cases: (i) $\bar{w}_{k^{*}}-\Delta_{t}/y_{m^{*}}\geq 0$; and
(ii) $\bar{w}_{k^{*}}-\Delta_{t}/y_{m^{*}}<0$. In the first case where
$\bar{w}_{k^{*}}-\Delta_{t}/y_{m^{*}}\geq 0$, we have
$w^{t}_{0}=\bar{w}_{k^{*}}-\Delta_{t}/y_{m^{*}}$ and the proof is similar to
Lemma 4.1. In the second case where $\bar{w}_{k^{*}}-\Delta_{t}/y_{m^{*}}<0$,
$w^{t}_{0}=0$ and we have $q(0;\hat{F}^{\mu}_{t})=\bar{\xi}\geq y_{m^{*}}$
(the retailer will order as much as possible since the order cost is zero). In
this case, we have $p_{t,m^{*}-1}\leq 1-w^{t}_{0}/s=1$ (by Eq. (6)) and
$\varphi(w^{t}_{0};\hat{F}^{\mu}_{t})\geq(w^{t}_{0}-c)y_{m^{*}}\geq(\bar{w}_{k^{*}}-\Delta_{t}/y_{m^{*}}-c)y_{m^{*}}=\varphi_{k^{*}}-\Delta_{t}$.

###  9.4 Proof of Lemma 4.4

When $q(w_{0}^{t};\hat{F}_{t}^{\mu})<y_{m^{*}}$, we must have $w^{t}_{0}>0$.
Otherwise, if $w^{t}_{0}=0$, the retailer will always order
$q(0;\hat{F}^{\mu}_{t})=\bar{\xi}$ since the order cost is zero. Thus we can
restrict to $\bar{w}_{k^{*}}-\Delta_{t}/y_{m^{*}}>0$.

We will show that if $q(w_{0}^{t};\hat{F}_{t}^{\mu})<y_{m^{*}}$, then

$\max_{k\in[K]}\max_{x\in[0,\bar{\xi}]}|\hat{F}_{\tau^{0}_{i}+k}^{\mu}(x)-\hat{F}_{t}^{\mu}(x)|\geq\Delta_{t}/(s\,\bar{\xi}),$

and consequently

$\sum^{\tau^{0}_{i+1}-1}_{t=\tau^{0}_{i}+1}\max_{x\in[0,\bar{\xi}]}|\hat{F}_{t}^{\mu}(x)-\hat{F}_{t+1}^{\mu}(x)|\geq\Delta_{t}/(s\,\bar{\xi}).$

First notice that according to the policy implementation, we have (by the
relation $y_{m^{*}}=q(\bar{w}_{k^{*}};\hat{F}_{\tau^{0}_{i}+k^{*}}^{\mu})$ and
Eq. (8)) that:

$p_{\tau^{0}_{i}+k^{*},m^{*}-1}<1-\bar{w}_{k^{*}}/s.$ (26)

Next, since $q(w_{0}^{t};\hat{F}_{t}^{\mu})<y_{m^{*}}$, we have

$p_{t,m^{*}-1}\geq
1-w_{0}^{t}/s=1-(\bar{w}_{k^{*}}-\Delta_{t}/y_{m^{*}})/s=1-\bar{w}_{k^{*}}/s+\Delta_{t}/(s\,y_{m^{*}}),$
(27)

where the first inequality follows from Lemma 4.3 and the first equality
follows from Eq. (12). Combining Eq. (26) and Eq. (27) gives

$p_{t,m^{*}-1}-p_{\tau^{0}_{i}+k^{*},m^{*}-1}\geq\Delta_{t}/(s\,y_{m^{*}})\geq\Delta_{t}/(s\,\bar{\xi}),$

and it follows that
$\max_{k\in[K]}\max_{x\in[0,\bar{\xi}]}|\hat{F}_{\tau^{i}_{0}+k}^{\mu}(x)-\hat{F}_{t}^{\mu}(x)|\geq\Delta_{t}/(s\,\bar{\xi})$.

###  9.5 Proof of Theorem 4.5

Here we complete the details of the proof of Theorem 4.5. We use superscript
$i$ to denote quantities corresponding to epoch $i$ since those quantities
vary from epoch to epoch. That is, we use $\varphi^{i}_{k}$ to denote the
profit observed during period $k\in[K]$ of the exploration phase of epoch $i$,
and $\varphi^{i}_{k^{*}}$ to denote the optimal profit observed during the
exploration phase in epoch $i$.

Abusing notation, let
$\text{Reg}(\pi,\hat{F}^{\mu}_{t_{1}\mathrel{\mathop{\mathchar
58\relax}}t_{2}})\triangleq\sum^{t_{2}}_{t=t_{1}}\varphi(w^{*}_{t};\hat{F}_{t}^{\mu})-\varphi(w_{t};\hat{F}_{t}^{\mu})$
be the regret incurred from periods $t\in[t_{1},t_{2}]$ when the supplier
follows $\pi$, given the sequence of perceived distributions
$\hat{F}_{t_{1}\mathrel{\mathop{\mathchar 58\relax}}t_{2}}^{\mu}$. The regret
incurred in epoch $i$ (for periods $t\in[\tau^{0}_{i}+1,\tau^{0}_{i+1}]$) for
$\pi_{\text{LUNA}}$ is then:

$\text{Reg}\left(\pi_{\text{LUNA}},\hat{F}^{\mu}_{\tau^{0}_{i}+1\mathrel{\mathop{\mathchar
58\relax}}\tau^{0}_{i+1}}\right)=\sum^{\tau^{0}_{i+1}}_{t=\tau^{0}_{i}+1}\varphi(w^{*}_{t};\hat{F}_{t}^{\mu})-\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})+\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})-\varphi(w_{t};\hat{F}_{t}^{\mu}).$

We will bound the first part
$\text{Reg}_{i}^{c}(\pi_{\text{LUNA}})\triangleq\sum^{\tau^{0}_{i+1}}_{t=\tau^{0}_{i}+1}\varphi(w^{*}_{t};\hat{F}_{t}^{\mu})-\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})$
and the second part
$\text{Reg}^{0}_{i}(\pi_{\text{LUNA}})\triangleq\sum^{\tau^{0}_{i+1}}_{t=\tau^{0}_{i}+1}\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})-\varphi(w_{t};\hat{F}_{t}^{\mu})$
separately.

##### Part I of the regret

To bound the first part $\text{Reg}^{c}_{i}(\pi_{\text{LUNA}})$, recall the
set (for epoch $i$):

$\mathcal{E}^{i}=\left\\{t\in[\tau^{0}_{i}+\max\\{M+2,K\\}+1,\tau^{0}_{i+1}]\mathrel{\mathop{\mathchar
58\relax}}q(w^{t}_{m};\hat{F}_{t}^{\mu})<y_{m},\,\forall m\in[M],\text{ and
}q(w^{t}_{0};\hat{F}_{t}^{\mu})\geq y_{m^{*}}\right\\}.$

Then, we have

$\begin{split}&\quad\text{Reg}^{c}_{i}(\pi_{\text{LUNA}})\\\
&\leq\sum^{\tau^{0}_{i+1}}_{t=\tau^{0}_{i}+\max\\{M+2,K\\}+1}\left(\varphi(w^{*}_{t};\hat{F}_{t}^{\mu})-\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})\right)+s\bar{\xi}\max\\{M+2,K\\}\\\
&\leq\sum^{\tau^{0}_{i+1}}_{t=\tau^{0}_{i}+\max\\{M+2,K\\}+1}\left[\left(\varphi(w^{*}_{t};\hat{F}_{t}^{\mu})-\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})\right)\mathds{1}(t\notin\mathcal{E}^{i})+\left(\varphi(w^{*}_{t};\hat{F}_{t}^{\mu})-\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})\right)\mathds{1}(t\in\mathcal{E}^{i})\right]\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+s\bar{\xi}\max\\{M+2,K\\}\\\
&\leq\sum^{\tau^{0}_{i+1}}_{t=\tau^{0}_{i}+\max\\{M+2,K\\}+1}\left[s\bar{\xi}\mathds{1}(t\notin\mathcal{E}^{i})+\left(\varphi(w^{*}_{t};\hat{F}_{t}^{\mu})-\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})\right)\mathds{1}(t\in\mathcal{E}^{i})\right]\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+s\bar{\xi}\max\\{M+2,K\\}.\end{split}$
(28)

It then follows from Eq. (28), Lemma 4.6, and Lemma 4.7 that

$\begin{split}&\text{Reg}^{c}_{i}(\pi_{\text{LUNA}})\\\
\leq\,&\sum^{\tau^{0}_{i+1}}_{t=\tau^{0}_{i}+\max\\{M+2,K\\}+1}\left[s\bar{\xi}\mathds{1}(t\notin\mathcal{E}^{i})+\left(\varphi(w^{*}_{t};\hat{F}_{t}^{\mu})-\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})\right)\mathds{1}(t\in\mathcal{E}^{i})\right]+s\bar{\xi}\max\\{M+2,K\\}\\\
\leq\,&s\bar{\xi}\left[\max\\{M+2,K\\}+1+2\log(T)\sqrt{M(\tau^{0}_{i+1}-1-\tau^{0}_{i})}\right]\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+\sum^{\tau^{0}_{i+1}}_{t=\tau^{0}_{i}+\max\\{M+2,K\\}+1}2\Delta_{t}+(\tau^{0}_{i+1}-1-\tau^{0}_{i})s\bar{\xi}\left(\frac{1}{K}\right)\\\
\leq\,&s\bar{\xi}\left[M+K+3+2\log(T)\sqrt{M(\tau^{0}_{i+1}-1-\tau^{0}_{i})}\right]+4\sqrt{M(\tau^{0}_{i+1}-1-\tau^{0}_{i})}+(\tau^{0}_{i+1}-1-\tau^{0}_{i})s\bar{\xi}\left(\frac{1}{K}\right)\end{split}$
(29)

where the last inequality follows since

$\displaystyle\sum^{\tau^{0}_{i+1}}_{t=\tau^{0}_{i}+\max\\{M+2,K\\}+1}2\Delta_{t}=\sum^{\tau^{0}_{i+1}}_{t=\tau^{0}_{i}+\max\\{M+2,K\\}+1}2\sqrt{M/(t-\tau^{0}_{i})}\leq
4\sqrt{M(\tau^{0}_{i+1}-1-\tau^{0}_{i})}.$

##### Part II of the regret

For the second part of the regret $\text{Reg}^{0}_{i}(\pi_{\text{LUNA}})$, we
have the equivalence

$\begin{split}\text{Reg}^{0}_{i}(\pi_{\text{LUNA}})&=\sum^{\tau^{0}_{i+1}}_{t=\tau^{0}_{i}+1}\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})-\varphi(w_{t};\hat{F}_{t}^{\mu})\\\
&=\left(\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})-\varphi(w_{t};\hat{F}_{t}^{\mu})\right)\mathds{1}(w_{t}\neq
w^{t}_{0})\\\ &\leq\bar{\xi}s\left[K+T_{i}(K)\right].\end{split}$

Then, by Lemma 9.4 we have

$\text{Reg}^{0}_{i}(\pi_{\text{LUNA}})\leq\bar{\xi}s\left[K+\sqrt{11\log(T)M(\tau^{0}_{i+1}-1-\tau^{0}_{i})}\right],$
(30)

with probability at least $1-1/T^{2}$.

##### Combining the two parts of the regret

Combining Eqs. (29) and (30), and using the union bound, we have with
probability at least $1-1/T$ that (where we let $I$ be the total number of
epochs)

$\displaystyle\begin{split}&\quad\text{Reg}\left(\pi_{\text{LUNA}},\hat{F}_{1\mathrel{\mathop{\mathchar
58\relax}}T}^{\mu}\right)\\\
&=\sum^{T}_{t=1}\varphi(w^{*}_{t};\hat{F}_{t}^{\mu})-\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})+\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})-\varphi(w_{t};\hat{F}_{t}^{\mu})\\\
&=\sum^{I}_{i=1}\text{Reg}^{c}_{i}(\pi_{\text{LUNA}})+\sum^{I}_{i=1}\text{Reg}^{0}_{i}(\pi_{\text{LUNA}})\\\
&\leq
s\bar{\xi}(M+2K+3)I+\left(2s\bar{\xi}\log(T)+4\right)\sum^{I}_{i=1}\sqrt{M(\tau^{0}_{i+1}-1-\tau^{0}_{i})}+\sum^{I}_{i=1}(\tau^{0}_{i+1}-1-\tau^{0}_{i})s\bar{\xi}\frac{1}{K}\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+\sum^{I}_{i=1}\bar{\xi}s\sqrt{11\log(T)M(\tau^{0}_{i+1}-1-\tau^{0}_{i})}\\\
&\leq
s\bar{\xi}(M+2K+3)I+\left(2s\bar{\xi}\log(T)+4+\bar{\xi}\sqrt{11\log(T)}\right)\left(\sum^{I}_{i=1}\sqrt{M(\tau^{0}_{i+1}-1-\tau^{0}_{i})}\right)+\frac{T}{K}.\end{split}$
(31)

It then follows that

$\displaystyle\begin{split}\text{Reg}(\pi_{\text{LUNA}},T)&=\sup_{\mu\in\mathcal{M}(V,T)}{\mathds{E}}\left[\text{Reg}\left(\pi_{\text{LUNA}},\hat{F}_{1\mathrel{\mathop{\mathchar
58\relax}}T}^{\mu}\right)\right]\\\ &\leq
s\bar{\xi}(M+2K+3)I+\left(2s\bar{\xi}\log(T)+4+\bar{\xi}\sqrt{11\log(T)}\right)\left(\sum^{I}_{i=1}\sqrt{M(\tau^{0}_{i+1}-1-\tau^{0}_{i})}\right)+\frac{T}{K}\\\
&\leq
s\bar{\xi}(M+2K+3)I+\left(2s\bar{\xi}\log(T)+4+\bar{\xi}\sqrt{11\log(T)}\right)\sqrt{MTI}+\frac{T}{K}.\\\
&=\tilde{O}\left(\bar{\xi}^{\frac{4}{3}}V^{\frac{1}{3}}M^{\frac{1}{3}}T^{\frac{2}{3}}+\frac{\bar{\xi}T}{K}+\bar{\xi}^{\frac{5}{3}}KV^{\frac{2}{3}}M^{-\frac{1}{3}}T^{\frac{1}{3}}\right),\end{split}$
(32)

where the second inequality follows by Jensen’s inequality (using
$\sum^{T}_{i=1}(\tau^{0}_{i+1}-\tau^{0}_{i}-1)=T$), and the last equality
follows by Lemma 4.9. The rest of the argument follows by setting
$K^{*}=\lceil T^{\frac{1}{3}}V^{-\frac{1}{3}}\bar{\xi}^{-\frac{1}{3}}\rceil$
and $\hat{K}=\lceil\bar{\xi}^{-\frac{1}{3}}T^{\frac{1}{3}}\rceil$.

###  9.6 Proof of Lemma 4.6

Since
$t\in\mathcal{E}^{i}\cap[\tau^{0}_{i}+\max\\{M+2,K\\}+1,\tau^{0}_{i+1}]$, we
have by Lemma 4.3 that

$\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})\geq(w^{t}_{0}-c)y_{m^{*}}\geq\varphi^{i}_{k^{*}}-\Delta_{t}.$

At the same time, by Eq. (8), the optimal supplier profit in period $t$
satisfies:

$\varphi(w^{*}_{t};\hat{F}_{t}^{\mu})=\max_{m\in[M-1]}(s-s\,p_{t,m}-c)y_{m+1}.$

We then have

$\displaystyle\varphi(w^{*}_{t};\hat{F}_{t}^{\mu})$
$\displaystyle=\max_{m\in[M-1]}(s-s\,p_{m,t}-c)y_{m+1}$
$\displaystyle\leq\max_{m\in[M-1]}(w^{t}_{m+1}-c)y_{m+1}$
$\displaystyle=\Delta_{t}+\frac{\bar{\xi}s}{K}+\varphi^{i}_{k^{*}},$

where the inequality follows from Lemma 4.1. Therefore,

$\displaystyle\varphi(w^{*}_{t};\hat{F}_{t}^{\mu})-\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})=\varphi(w^{*}_{t};\hat{F}_{t}^{\mu})-\varphi^{i}_{k^{*}}+\varphi^{i}_{k^{*}}-\varphi(w^{t}_{0};\hat{F}_{t}^{\mu})\leq
2\Delta_{t}+\frac{\bar{\xi}s}{K}.$

###  9.7 Proof of Lemma 4.7

We make use of the following supporting result.

###### Lemma 9.3

Let $(t_{n})_{n=1}^{N}\in[\tau^{0}_{i}+\max\\{M+2,K\\}+1,\tau^{0}_{i+1}-1]$
for $N\geq 1$ be the sequence of periods where $t_{n}\in\mathcal{E}^{i}$. Let

$s=\arg\min_{s^{\prime}\geq
1}\left\\{\sum^{s^{\prime}}_{n=1}\frac{1}{\sqrt{M(t_{n}-\tau^{0}_{i})}}\geq
2\log(T)\right\\},$

then $E^{i}\leq s$ with probability at least $1-1/T^{2}$.

The proof of Lemma 9.3 follows from Lemma 9.4 below and Karnin and Anava 2016,
Theorem A.4.

###### Lemma 9.4