Nonparametric learning methods

Robust Dynamic Pricing with Demand Learning in the Presence of Outlier Customers

OR, 2022. Articles in Advance.

On implications of demand censoring in the newsvendor problem

MS 2013

这篇文章对于连续和离散分布的 newsvendor 问题，证明了 regret 的下界，并分别给出了最优算法。

对于连续需求的问题，partial censoring 与 censoring 没有区别。

对于离散需求的问题，文章还考虑了 partial censoring 的情况，并证明了 regret bound。

有 3 个假设：

1. $x_F^\ast \leq M$ (bounded optimal order quantity);
2. if demand is continuous, $F(\cdot)$ is differentiable, and $F^{\prime}(x) \geq \varepsilon$ for all $x \geq 0$ (strictly convex cost function);
3. if demand is discrete, $|F(x)-\beta| \geq \varepsilon$ for $x=$ $x_F^\ast-1, x_F^\ast$ (minimal separation around optimal quantity).

A Nonparametric Asymptotic Analysis of Inventory Planning with Censored Demand

MOOR 2009

用 online convex optimization 得到了 censored demand 下最好的 regret 界，用排队论去 bound 住 nonperishable case。

Nonparametric Pricing Analytics with Customer Covariates

OR, 2021. Ningyuan Chen, Guillermo Gallego.

考虑一个对顾客个性化定价的问题：时间 $t \in[T]$，观测到顾客的信息(covariate) $\mathbf{X}_t$ 后，设置价格 $p_t$，获得的利润是 $Z_t$，且 $Z_t / p_t$ 是一个均值为 $d(\mathbf{X}_t, p_t)$ 的 Bernoulli 随机变量。

记 $f(\boldsymbol{x}, p) = p d(\boldsymbol{x}, p), \, f^\ast(\mathbf{X}_t) = f^{\ast}(\mathbf{X}_t, p^\ast(\mathbf{X}_t))$，regret 定义为： $$ R_\pi(T)=\sum_{t=1}^T E\left[\left(f^\ast\left(\boldsymbol{X}_t\right)-f\left(\boldsymbol{X}_t, p_t\right)\right)\right] $$ 目标是 $\inf _\pi \sup _{f \in \mathcal{C}} R_\pi(T)$，$\mathcal{C}$ 是某一函数族。文章假设 $f$ 对 $\boldsymbol{x}, p$ 是 Lipschitz 连续的。

Multimodal Dynamic Pricing

MS, 2021. Yining Wang, Boxiao Chen, David Simchi-Levi.

$$ r(p):=p \times \mathbb{E}[d \mid p]=p f(p) . $$

Dynamic Pricing

一次订货，多次调价销售，无法补货，适用于服装等快消品。

Dynamic Pricing Without Knowing the Demand Function: Risk Bounds and Near-Optimal Algorithms

OR, 2009. Omar Besbes, Assaf Zeevi.

这篇文章是大佬 Omar Besbes 引用量最高的 paper，超过500了已经，足以说明这篇文章的意义非凡。

不一样的是，这篇文章假设一个给定的库存在一段内被销售，没有补货。

设定是 Gallego and van Ryzin (1994)

需求过程服从一个 Poisson process $\lambda_t = \lambda(p(t))$，价格取值于连续集合 $[\underline{p}, \overline{p}] \cup p_{\infty}$，$\lambda(p_{\infty}) = 0$；revenue rate $r(\lambda) := \lambda \gamma(\lambda)$ 是凹的，其中 $\gamma(\cdot)$ 是 $\lambda$ 的反函数。

假设 $\lambda$ 未知。记： $$ N^\pi(t):=N\left(\int_0^t \lambda(p(s)) d s\right) \quad \text { for } 0 \leqslant t \leqslant T $$ 动态定价问题是如下的优化问题： $$ J^\pi(x, T ; \lambda):=\mathbb{E}\left[\int_0^T p(s) d N^\pi(s)\right] $$ 假设 full-information 下的最优利润是 $J^D(x, T\mid \lambda)$，则定义 regret 为： $$ \mathscr{R}^\pi(x, T ; \lambda)=1-\frac{J^\pi(x, T ; \lambda)}{J^D(x, T \mid \lambda)} \quad \in [0, 1] $$ 我们感兴趣的是 minimax regret： $$ \inf _{\pi \in \mathscr{P}} \sup _{\lambda \in \mathscr{L}} \mathscr{R}^\pi(x, T ; \lambda) . $$

Nonparametric Case

算法分为 “learning” phase (exploration) + “pricing” phase, 由两个参数 $(\tau, \kappa)$ 组成

• $[0, \tau]$ 进行 exploration，等间距地选取 $\kappa$ 个价格点 $\{p_i: i = 1, \dots, \kappa\}$，每个价格点学习 $\Delta = \tau / \kappa$ 段时间
• 计算 $\hat{d}(p_i)$ 为平均需求到达速率，$\hat{p}^u=\underset{1 \leqslant i \leqslant \kappa}{\arg \max }\left\{p_i \hat{d}\left(p_i\right)\right\}, \hat{p}^c=\underset{1 \leqslant i \leqslant \kappa}{\arg \min }\left|\hat{d}\left(p_i\right)-x / T\right|$，再令 $\hat{p}=\max \left\{\hat{p}^c, \hat{p}^u\right\}$
• $(\tau, T]$ 以价格 $\hat{p}$ 进行 exploitation

$$ \frac{C^{\prime}}{n^{1 / 2}} \leqslant \inf _{\pi \in \mathscr{P}_n} \sup _{\lambda \in \mathscr{P}} \mathscr{R}_n^\pi(x, T ; \lambda) \leqslant \frac{C(\log n)^{1 / 2}}{n^{1 / 4}}, $$

Parametric Case

假定 demand function 有参数 $\theta \in \Theta$，对 $\lambda(p; \theta)$ 做如下假设：

Assumption 2. (i) There exists a vector of distinct prices $\vec{p}=\left(p_1, \ldots, p_k\right) \in[\underline{p}, \bar{p}]$ such that:

• (a) For some $l_0>0, \min _{1 \leqslant i \leqslant k} \inf _{\theta \in \Theta} \lambda\left(p_i ; \theta\right)>l_0$.
• (b) For any vector $\vec{d}=\left(d_1, \ldots, d_k\right)$, the system of equations $\left\{\lambda\left(p_i ; \theta\right)=d_i, i=1, \ldots, k\right\}$ has a unique solution in $\theta$. Let $g(\vec{p}, \vec{d})$ denote this solution. We assume in addition that $g(\vec{p}, \cdot)$ is Lipschitz continuous with constant $\alpha>0$.
• (c) For $i=1, \ldots, k, \sqrt{\lambda\left(p_i ; \theta\right)}$ is differentiable on $\Theta$.

(ii) For some $\bar{K}_2>0,\left|\lambda(p ; \theta)-\lambda\left(p ; \theta^{\prime}\right)\right| \leqslant \bar{K}_2\left\|\theta-\theta^{\prime}\right\|_{\infty}$ for all $p \in[\underline{p}, \bar{p}]$ and $\theta, \theta^{\prime} \in \Theta$.

$$ \sup _{\theta \in \Theta} \mathscr{R}_n^\pi(x, T ; \theta) \leqslant \frac{C(\log n)^{1 / 2}}{n^{1 / 3}} $$ 参数化的需求下的 regret bound 要优于非参数需求，但是相应地，可能会存在 model misspecification。

Close the Gaps: A Learning-While-Doing Algorithm for Single-Product Revenue Management Problems

OR, 2014. Zizhuo Wang, Shiming Deng, Yinyu Ye.

这篇文章的设定类似于 「OR, 2009. Omar Besbes, Assaf Zeevi.」提出了达到理论下界的方法。

文章提出的算法叫做 DPA (Dynamic pricing algorithm)，相比之前的算法复杂了很多，其遗憾值为： $$ \sup _{\lambda \in \Gamma} R_n^\pi(x, T ; \lambda) \leqslant \frac{C(\log n)^{4.5}}{\sqrt{n}} $$

DPA (Dynamic pricing algorithm)

算法的思想大概就是，先粗糙地等间隔估计一番，那根据这样的结果，可以将最优价格所在的区间适当缩小。

最后，文章用 KL 散度给出了一个理论下界的例子和证明。

Dynamic Pricing Under a General Parametric Choice Model

OR, 2012. Josef Broder, Paat Rusmevichientong.

顾客以离散的时间到达商店，人们的 willness-to-pay $V_t$ 满足 $d(p; \mathbf{z}) = P(V_t \geqslant p)$ 。

Assumption 1

• $0<d_{\min } \leqslant d(p ; \mathbf{z}) \leqslant d_{\max }<1$ for all $p \in \mathscr{P}$ and $\mathbf{z} \in \mathscr{Z}$.

• The revenue function $p \mapsto r(p ; \mathbf{z})$ has a unique maximizer $p^\ast(\mathbf{z}) \in \mathscr{P}$.

• The function $\mathbf{z} \mapsto p^\ast(\mathbf{z})$ is L-Lipschitz, that is, $\left|p^\ast(\mathbf{z})-p^\ast(\overline{\mathbf{z}})\right| \leqslant L\|\mathbf{z}-\overline{\mathbf{z}}\|$ for all $\mathbf{z}, \overline{\mathbf{z}} \in \mathscr{Z}$.

• The revenue function $p \mapsto r(p ; \mathbf{z})$ is twice differentiable with $\sup _{p \in \mathscr{P}, \mathbf{z} \in \mathcal{X}}\left|r^{\prime \prime}(p ; \mathbf{z})\right| \leqslant c_r$.

Blind Network Revenue Management

OR, 2012. Omar Besbes, Assaf Zeevi.

Explore then Exploit

On Implications of Demand Censoring in the Newsvendor Problem

MS, 2013. Omar Besbes, Alp Muharremoglu

Data-Driven Inventory Control with Shifting Demand

POM, 2021. Boxiao Chen.

Dynamic Inventory Control with Stockout Substitution and Demand Learning

MS, 2020. Boxiao Chen, Xiuli Chao.

The key feature of our problem is that the firm knows neither the demand distribution nor the customers’ substitution probabilities a priori; thus it needs to learn them from sales data on the fly while concurrently maximizing total profit.

离散的初始需求分布，对于产品 $k$ $$ \mathbb{P}\left(D_t^{0 k}=m\right)=w^{k m}, \quad \text { for } m=0,1, \ldots $$ 经一轮替代后的需求分布是 $$ D_t^k\left(\mathbf{w}, \mathbf{a}, \mathbf{y}_t\right)=D_t^{0 k}+\sum_{j \neq k} D_t^{j k}\left(a^{j k}, y_t^j\right), \qquad D_t^{k j}\left(a^{k j}, y_t^k\right)=\sum_{\ell=1}^{\left(D_t^{0 k}-y_t^k\right)^{+}} 1_{\ell}, $$ $1_\ell$ 是一个以 $a^{kj}$ 为均值的 Bernoulli 随机变量。

因此时期 $t$ 的 profit 就是 $$ \sum_{k=1}^K \left(p^k \min \left\{D_t^k\left(\mathbf{w}, \mathbf{a}, \mathbf{y}_t\right), y_t^k\right\}-h^k\left(y_t^k-D_t^k\left(\mathbf{w}, \mathbf{a}, \mathbf{y}_t\right)\right)^{+}-b^k\left(D_t^k\left(\mathbf{w}, \mathbf{a}, \mathbf{y}_t\right)-y_t^k\right)^{+}\right) $$ Clairvoyant Optimal Policy

当各种信息已知时，存在一个最优的 myopic policy $\mathbf{y}^\ast=\mathbf{y}^\ast(\mathbf{w}, \mathbf{a})$.

Data-Driven Algorithm for Stockout Substitution ($D^2AS^2$ )

主要结论：

• regret lower bound 是 $O(\log T)$
• regret upper bound 是 $O((\log T) (\log \log T)^2)$

在这篇文章的 online appendix 中，有一些有价值的 concentration inequality

An efficient learning framework for multiproduct inventory systems with customer choices

POM, 2022. Xiangyu Gao, Huanan Zhang.

Stochastic Gradient Descent — OCO

通过随机梯度下降法来做在线学习，能够考虑删失数据。

A Nonparametric Asymptotic Analysis of Inventory Planning with Censored Demand

MOR, 2009. Woonghee Tim Huh, Paat Rusmevichientong.

是基于 OCO-SGD 的在线库存管理最早期的文章, 投稿于 2007 年。(OCO-SGD 最早于 2003 年发表 在计算机顶会 icml）。 $$ Q(y)=h \cdot E[y-D]^{+}+b \cdot E[D-y]^{+} $$ 每个需求分布 $D$ 的样本 $w$ 给出了 $Q(y)$ 左导数的无偏估计: $$ Q^{\prime}(y ; w)=(h+b) \mathbf{1}_{[y \geq w]}-b, \quad \mathrm{E}_{w \sim D}\left[Q^{\prime}(y ; w)\right]=Q^{\prime}(y) $$ 对于 censored demand 的 newsvendor 问题来说, 如果已知最优库存水平的上界 $\bar{y}$, 执行策略： $$ \hat{y}_{t+1}=P_{[0, \bar{y}]}\left(\hat{y}_t-\epsilon_t H_t\left(\hat{y}_t\right)\right), \text { where } H_t\left(\hat{y}_t\right)= \begin{cases}h, & \text { if } D_t<\hat{y}_t \\ -b, & \text { if } D_t \geq \hat{y}_t\end{cases} $$ 步长 $\epsilon_t=O(1 / \sqrt{t})$

这是一种在线随机梯度下降法, 随机梯度只有两种情况, 适用于 censored demand。 根据 OCO 的相关理论可以得到 regret 界为 $O(\sqrt{T})$ 。

如果 $Q(y)$ 强凸, 那么有 $O(\log T)$ 的 regret 界的算法。

对 nonperishable 的情况, 库存水平设置为 $y_{t+1}=\max \left\{\hat{y}_{t+1}, x_{t+1}\right\}$, 是上期库存和 SGD 结果 取大。

An adaptive algorithm for finding the optimal base-stock policy in lost sales inventory systems with censored demand

MOR, 2009. Woonghee Tim Huh, Ganesh Janakiraman, John A. Muckstadt, Paat Rusmevichientong.

考虑提前期非零的多周期报童问题，这个问题的最优策略比较复杂，所以文章聚焦于最优的 base-stock policy。应用一种修改的 OCO-SGD 算法，文章得到了 $O(T^{2/3})$ 的 regret 界。

Online Sequential Optimization with Biased Gradients: Theory and Applications to Censored Demand

IJOC, 2014. Woonghee Tim Huh, Paat Rusmevichientong.

文章将在线随机梯度下降法推广到随机梯度有偏的情况，得到了此时的 regret bound。接着文章把 $1/\sqrt{T}$ 的 regret 界推广到一类非凸函数上，这类非凸函数定义为序贯凸(sequentially convex)的，并给出了相应的算法。这是文章的理论贡献。

然后文章给出了序贯凸的一些实例，比如，当未知的需求分布非 i.i.d，但是有季节性，就可以应用之前所述的算法。

Technical Note—Nonparametric Data-Driven Algorithms for Multiproduct Inventory Systems with Censored Demand

OR, 2016. Cong Shi, Weidong Chen, Izak Duenyas.

将 OCO-SGD newsvendor 推广到 multi-product system 上，并且假设每个 product 的需求分布是互相独立的。

Technical Note—Perishable Inventory Systems: Convexity Results for Base-Stock Policies and Learning Algorithms Under Censored Demand

OR, 2018. Huanan Zhang, Xiuli Chao, Cong Shi.

考虑产品的生命周期有限（$m$ periods），这个问题的最优策略比较复杂，所以文章聚焦于最优的 base-stock policy。依然是使用的修改的 OCO-SGD 算法，得到 regret 界是 $\sqrt{T}$.

Optimal Learning Algorithms for Stochastic Inventory Systems with Random Capacities

POM, 2020. Weidong Chen, Cong Shi, Izak Duenyas.

在 newsvendor 的基础上，考虑供给也存在不确定性。

Feature-Based Nonparametric Inventory Control with Censored Demand

SSRN. Jingying Ding, Woonghee Tim Huh, Ying Rong.

文章做了六个假设：

1. 需求随机变量 $D_t = w \cdot x_t + \delta_t$ 是线性于外生特征 $x_t$ 的，$\delta_t$ 是 iid 的噪声
2. $w$ 取值于一个紧集 $\Omega_0$
3. $x_t$ 取值于一个紧集 $\mathbb{X}$，第一个分量是 1，可以 normalize 到 $X$ 是非负的，$x_U = \max_t \| x_t \|$
4. 存在紧集 $\Omega$ 使得 $\forall x_t \in \mathbb{X},\, z \in \Omega$ 都存在 $\underline{\delta}, \overline{\delta}$ 使得 $\underline{\delta} \leq z \cdot x_t - w \cdot x_t \leq \overline{\delta}, \; \forall t \in T$；$\Omega_0$ 和 $\Omega$ 都可以取成一个 box，方便后续的投影
5. 误差项 $\delta_t$ 的 CDF $\Phi(\cdot)$ 和 PDF $\phi(\cdot)$，支撑集为 $[\underline{\delta}, \overline{\delta}]$，$\phi(\cdot)$ 有下界 $\theta$
6. 对任何特征向量 $x$，都有 $\inf \mathrm{E}[D \mid x ] > 0$ .

对于 clairvoyant policy，如果 DM 知道 $w$ 和 $\delta_t$ 的分布，那么最优的 order-up-to level 是 $y_t^\ast = w^\ast \cdot x_t$；其中 $\left(w^\ast\right)_1 =(w)_1+\Phi^{-1}\left(b/(b+h)\right),\; \left(w^\ast\right)_j =(w)_j, j=2, \ldots, N$ .

文章提出了一个 Feature-Based Adaptive Inventory Algorithm .

初始持有库存 $u_1 = 0$；随机取 $z_1 \in \Omega$ ，并令 $y_1 = \hat{y}_1 = z_1 \cdot x_1$

接着重复执行： $$ \begin{aligned} & z_{t+1}=P_{\Omega}\left(z_t-\varepsilon_t H_t\left(z_t\right)\right) \\ & \hat{y}_{t+1}=z_{t+1} \cdot x_{t+1} \\ & y_{t+1}=\max \left\{\hat{y}_{t+1}, u_{t+1}\right\} \end{aligned} $$ 其中 $$ H_t\left(z_t\right)= \begin{cases}h \cdot x_t, & \text { if } D_t<\hat{y}_t \\ -b \cdot x_t, & \text { if } D_t \geq \hat{y}_t\end{cases} $$ Dynamic Shrinkage

在实践中 FAI 算法在迭代的前几步可能误差会比较大一些，SGD用的是无偏的梯度，文章引入了 dynamic shrinkage 的思想在一开始用有偏但是方差更小的梯度进行替代。

最后，在数值实验上，文章对比了四种方法：FAI, DS, ERM 和不考虑特征的。其中 ERM 用的是 uncensored demand data。

SAA

使用 sample average approximation 作为策略，考虑的都是 observable demand。

Provably Near-Optimal Sampling-Based Policies for Stochastic Inventory Control Models

MOR, 2007. Retsef Levi, Robin O. Roundy, David B. Shmoys.

给出了使 SAA 的解足够好所必须要的 sample 的个数。

The Data-Driven Newsvendor Problem: New Bounds and Insights

OR, 2015. Retsef Levi, Georgia Perakis, Joline Uichanco.

借助 WMS 这一概念收紧了 Levi(2007) 的 bound。

Technical Note—Data-Driven Newsvendor Problem: Performance of the Sample Average Approximation

OR 2022. Meichun Lin, Woonghee Tim Huh, Harish Krishnan, Joline Uichancob.

正式证明了对连续需求分布使用 SAA 方法得到的 regret 界是 $O(\log T)$ 的，证明的过程中引入了一个新的性质叫做 local flatness (around optimal order quantity)，有这个性质能得到 $\log T$ 的界，没这个性质只有 $\sqrt{T}$ 的界。

Early work / Other (without regret bound)

Adaptive ordering and pricing for perishable products

OR, 2000. APOSTOLOS N. BURNETAS, CRAIG E. SMITH.

在 demand censoring 下使用随机逼近的方法，

$$ Q_{n+1}=Q_n\left(1-\frac{Y_n-r}{n}\right), \quad r = \frac{p-c}{p-s} $$

$Y_n$ 是否缺货的 indicator。

利用了随机逼近的相关理论来说明 $Q_n \to Q^\ast$ .

Adaptive Data-Driven Inventory Control with Censored Demand Based on Kaplan-Meier Estimator

OR, 2011. Woonghee Tim Huh, Retsef Levi, Paat Rusmevichientong, James B. Orlin.

Kaplan-Meier estimator is used to construct an empirical cumulative distribution function (CDF) based on censored observations, generalizing the empirical CDF for uncensored data.

KM 估计量用于对 censored data 构建 CDF:

$Z_t=\min \left\{D_t, Y_t\right\}, \quad \delta_t=\mathbf{I}\left[D_t \leqslant Y_t\right]$, 有 $T$ 个 observation $\left\{\left(Z_1, \delta_1\right), \ldots,\left(Z_T, \delta_T\right)\right\}$ 进行排序使得, $Z_{(t)} \leqslant Z_{(t+1)}$; 如果 $Z_{(t)}=Z_{(t+1)}$, 就 $\delta_{(t)} \geqslant \delta_{(t+1)}$ 这时候的 KM 统计量是

$$ \bar{F}_T(d)=\prod_{t: Z(t) \leqslant d}\left(\frac{T-t}{T-t+1}\right)^{\delta_{(t)}} $$

文章证明了 KM 统计量得到的订货量的渐进最优性，但是没有证明其 regret bound。