面向删失需求的一仓多店系统的资源自适应原始对偶学习

# 面向带审查需求的一仓多店系统的资源自适应原对偶学习
来源: https://arxiv.org/html/2608.14096

###### 摘要
一仓多店 (OWMS) 系统是一种基础的库存网络，其中不可补货的仓库在多个店铺之间随时间分配共享库存。现有的 OWMS 学习策略建立在根据初始平均资源速率校准的固定目标之上，但这种固定目标架构无法在已实现的销售改变了每个未来时期的剩余可用资源后重新定位。我们开发了资源自适应原对偶学习 (RAPDL)，这是一种新的学习框架，它在审查需求作为剩余资源状态演变过程中跟踪原对偶重解路径。在每个时期，当前资源速率索引目标店铺分配和对偶变量，而审查销售则为同时更新两者提供梯度估计。分析结合了期望销售几何与移动目标论证，得出对数期望遗憾，改进了现有 OWMS 学习策略的最先进平方根阶保证。其底层设计和分析思想可能为其他具有耗尽共享资源的在线学习问题提供参考。数值实验进一步展示了该实用变体在不同时间范围和库存机制下的良好有限期性能。

###### 关键词
一仓多店系统; 库存学习; 审查需求; 原对偶方法; 资源自适应学习; 对数遗憾

††runningtitle: 面向 OWMS 系统的资源自适应原对偶学习
††runningauthor: Lyu
††authors: 管理科学系，管理学院，复旦大学，上海 200433，中国, [email protected]
††affiliation:

## 1 引言
一仓多店 (OWMS) 系统是一种基本的库存分配架构，它将有限的库存集中在中央仓库，并将其随时间分配给各个店铺。每次配送都会在某个地点的当前服务与以后服务另一个地点的选项之间进行权衡，从而产生系统范围内的动态分配问题 [16](https://arxiv.org/html/2608.14096#bib.bib1), [6](https://arxiv.org/html/2608.14096#bib.bib5)。应用包括一般商品分销、易腐产品分销 [13](https://arxiv.org/html/2608.14096#bib.bib6)、快时尚分销 [4](https://arxiv.org/html/2608.14096#bib.bib2), [2](https://arxiv.org/html/2608.14096#bib.bib19)、服务件物流 [19](https://arxiv.org/html/2608.14096#bib.bib32)、紧急医疗用品分配 [25](https://arxiv.org/html/2608.14096#bib.bib33)。本文关注一个有限期版本，其中仓库获得初始库存，并将其运往具有不同需求分布和经济利润率的店铺。每次分配都会改变明天的库存状态以及每个未来单位的机会成本。即使需求规律已知，精确的动态规划也是高维且强状态依赖的。在分布未知和反馈审查的情况下，管理者必须在学习需求响应的同时，保留赚取未来回报所需的库存。对于报童及相关库存问题，正密度下界提供了强凸性，将随机一阶学习转化为对数遗憾 [15](https://arxiv.org/html/2608.14096#bib.bib11), [31](https://arxiv.org/html/2608.14096#bib.bib12), [32](https://arxiv.org/html/2608.14096#bib.bib13), [23](https://arxiv.org/html/2608.14096#bib.bib16)。这些模型有效地从无约束的上游源进行补货。相比之下，对于不可补货的仓库，所有店铺和时期都在竞争同一个有限的库存池。在一家店铺的销售不可逆转地减少了后续时期每个店铺可用的资源。现有的最佳有限库存审查需求保证是针对 OWMS 及其多仓库扩展的平方根阶 [2](https://arxiv.org/html/2608.14096#bib.bib19), [28](https://arxiv.org/html/2608.14096#bib.bib22)。重解是学术界和工业界公认的用于动态资源分配的强大组织原则。它揭示了分配和稀缺价格应如何适应不断演变的资源状态，但学习工作很少将由此产生的原对偶路径本身作为被跟踪的对象。我们开发了一种新的资源自适应原对偶学习框架，该框架用使用审查需求在线跟踪由资源状态重解产生的内生原对偶路径，取代了固定目标学习。该框架为 OWMS 学习问题提供了对数遗憾保证，其设计和分析工具可能为其他具有审查反馈和耗尽共享资源的在线学习与控制问题提供参考。

### 1.1 贡献
我们的贡献总结如下：
1.  **资源自适应原对偶学习框架。** 我们引入资源自适应原对偶学习 (RAPDL $\mathsf{\{RAPDL\}}$)，这是一种新框架，它用在线跟踪由资源状态重解产生的内生原对偶路径，取代了根据初始平均资源速率校准的固定目标。RAPDL $\mathsf{\{RAPDL\}}$ 使用每个剩余时期的剩余系统库存重新索引流体 KKT 目标——首选店铺分配及其共同稀缺价格。审查销售提供可观察的随机原对偶方向来更新该目标，并同时更新重新定位下一个目标的资源状态。通过这种方式，RAPDL $\mathsf{\{RAPDL\}}$ 跟踪已知分布流体重解将产生的分配与价格路径，而无需估计需求分布或重复求解流体程序。
2.  **内生移动目标分析。** 我们的分析将遗憾分为三个组成部分。值函数平滑性控制资源索引重解路径的内在差距。期望销售几何和移动目标论证控制从学习该路径产生的差距。库存动态控制将学习到的状态实现为可行物理操作所产生的差距。每个组成部分都是对数阶的，为 RAPDL $\mathsf{\{RAPDL\}}$ 提供了 $O(\log T)$ 遗憾保证，并改进了有限库存审查需求 OWMS 文献中的最先进平方根阶保证。
3.  **数值评估。** 我们将我们的资源自适应学习方法 RAPDL $\mathsf{\{RAPDL\}}$ 与 [2](https://arxiv.org/html/2608.14096#bib.bib19) 的双二分搜索策略（一个最先进的基准）在不同的库存机制下进行比较。在同质和异质实验中，RAPDL $\mathsf{\{RAPDL\}}$ 在所有 24 组配对比较中均具有更低的平均总成本，这为我们的算法提供了短期时间范围的证据。

### 1.2 相关文献
**不可补货资源的重解与原对偶学习。** 广泛的收益管理和在线分配文献将观察到的资源消耗反馈到未来的决策中。重解策略使用剩余容量和时间范围重新计算流体程序，并在适当的结构条件下实现亚线性保证 [17](https://arxiv.org/html/2608.14096#bib.bib25), [18](https://arxiv.org/html/2608.14096#bib.bib24)。这些模型假设已知需求分布，因此不涉及学习。相关的在线 LP 工作结合了学习与在完全观察请求下的重复 LP 优化 [1](https://arxiv.org/html/2608.14096#bib.bib23), [22](https://arxiv.org/html/2608.14096#bib.bib26), [21](https://arxiv.org/html/2608.14096#bib.bib30)。这些方法通过经验 LP 求解从观察到的到达中学习对偶价格。原对偶需求学习将流体原解和对解本身视为未知。相关方法包括个性化定价中的显式学习库存影子价格 [7](https://arxiv.org/html/2608.14096#bib.bib20)，以及非参数或大动作空间网络收益管理 [9](https://arxiv.org/html/2608.14096#bib.bib27), [29](https://arxiv.org/html/2608.14096#bib.bib28), [30](https://arxiv.org/html/2608.14096#bib.bib21), [27](https://arxiv.org/html/2608.14096#bib.bib29)。这些方法通过不同的架构结合需求学习、对偶价格学习和资源反馈。在有限库存 OWMS 设定下，RAPDL $\mathsf{\{RAPDL\}}$ 而是使用审查销售来联合跟踪店铺级分配目标及其共同稀缺价格，该路径由每个剩余时期的剩余系统库存索引。
**OWMS 控制与学习。** 有限库存 OWMS 问题起源于 [16](https://arxiv.org/html/2608.14096#bib.bib1) 的双层分配设定。在需求规律已知的情况下，文献为 OWMS 问题开发了可分解的拉格朗日策略 [24](https://arxiv.org/html/2608.14096#bib.bib7), [26](https://arxiv.org/html/2608.14096#bib.bib8)。在这个已知需求的控制文献中，[5](https://arxiv.org/html/2608.14096#bib.bib9) 的策略使用已实现的需求历史自适应地重新调整其拉格朗日参数。最接近的学习论文保留了那个有限共享库存并显式地学习其稀缺价格。[2](https://arxiv.org/html/2608.14096#bib.bib19) 为 OWMS 提出了双二分搜索，[28](https://arxiv.org/html/2608.14096#bib.bib22) 将对偶割平面与原学习结合在多仓库扩展中。两者都学习一个固定的拉格朗日目标，并为此类问题获得了现有的最佳平方根阶遗憾保证。相比之下，RAPDL $\mathsf{\{RAPDL\}}$ 学习一个资源索引的原对偶路径，并在已实现的销售改变剩余资源状态后重新定位该路径。
**基于梯度的库存学习。** 对于基本的审查需求库存模型，销售和缺货观察可以提供一阶梯度信息用于基于梯度的学习 [15](https://arxiv.org/html/2608.14096#bib.bib11), [31](https://arxiv.org/html/2608.14096#bib.bib12), [23](https://arxiv.org/html/2608.14096#bib.bib16), [12](https://arxiv.org/html/2608.14096#bib.bib18)。扩展涵盖了正提前期、易腐库存、随机容量和多零售商系统 [14](https://arxiv.org/html/2608.14096#bib.bib10), [32](https://arxiv.org/html/2608.14096#bib.bib13), [33](https://arxiv.org/html/2608.14096#bib.bib15), [8](https://arxiv.org/html/2608.14096#bib.bib14), [11](https://arxiv.org/html/2608.14096#bib.bib17)。[23](https://arxiv.org/html/2608.14096#bib.bib16) 将小批量 SGD 元策略应用于仓库自身可以补货的双层系统，而 [13](https://arxiv.org/html/2608.14096#bib.bib6) 为仓库和零售商均可补货的易腐网络开发了一种离线的、基于特征的近似方法。
**论文结构。** 第 [2](https://arxiv.org/html/2608.14096#S2) 节介绍物理系统、精确比较器、流体基准。第 [3](https://arxiv.org/html/2608.14096#S3) 节推导并陈述 RAPDL $\mathsf{\{RAPDL\}}$。第 [4](https://arxiv.org/html/2608.14096#S4) 节给出主要保证并展开其遗憾分析，包括仅用于分析的期望销售几何。第 [5](https://arxiv.org/html/2608.14096#S5) 节报告计算研究，第 [6](https://arxiv.org/html/2608.14096#S6) 节总结论文。附录收集了正文中所有命题和引理的证明、支持性技术验证以及扩展草图。
**符号说明。** 全文中，$T \geq 2$，$\log$ 表示自然对数，$C < \infty$ 表示一个独立于 $T$ 的常数，该常数可能逐行变化。令 $x^{+} := \max\{x, 0\}$。

## 2 问题描述
存在店铺 $i \in [N] := \{1, \ldots, N\}$ 和时期 $t \in [T] := \{1, \ldots, T\}$。在时期 $t$ 配送前，$B_t$ 是仓库物理剩余的库存，$I_{i,t}$ 是已位于店铺 $i$ 的现有库存。决策 $Y_{i,t}$ 是店铺 $i$ 在配送*之后*的库存。仓库以不可补货的库存 $B_1 = W = \gamma T$ 开始，每个店铺初始为空，$I_{i,1} = 0$。除非另有说明，向量范数为欧几里得范数。在时期 $t$ 开始时，可行的配送后向量满足：
$$ Y_{i,t} \geq I_{i,t}, \qquad \sum_{i=1}^{N} (Y_{i,t} - I_{i,t}) \leq B_t. \tag{2.1} $$
需求、销售和状态遵循：
$$ S_{i,t} = D_{i,t} \wedge Y_{i,t}, \quad I_{i,t+1} = Y_{i,t} - S_{i,t}, \quad B_{t+1} = B_t - \sum_{i=1}^{N} (Y_{i,t} - I_{i,t}). \tag{2.2} $$
在每个时期，管理者观察状态 $(B_t, \mathbf{I}_t)$ 和过去的销售，在需求出现前选择 $\mathbf{Y}_t$，仅观察到审查销售 $\mathbf{S}_t$，然后根据 (2.2) 更新状态。未满足的需求会丢失。我们对原始不确定性施加以下条件。

###### 假设 2.1
1.  (i) 需求向量 $\{\mathbf{D}_t\}_{t \geq 1}$ 在时间上是独立同分布的。在每个时期内，它们的坐标可以任意相关，且 $D_{i,t}$ 的边际分布为 $F_i$。
2.  (ii) 分布 $F_i$ 在其支撑 $[0, \bar{d}_i]$ 上绝对连续，对于 $x \geq \bar{d}_i$ 满足 $F_i(x) = 1$，并且具有连续密度，满足已知边界：
    $$ 0 < \kappa_i \leq f_i(x) \leq K_i < \infty, \qquad 0 \leq x \leq \bar{d}_i. \tag{2.3} $$
记 $\overline{D} := \sum_{i=1}^{N} \bar{d}_i$，并假设初始资源速率满足 $0 \leq \gamma \leq \overline{D}$。对于策略 $\pi$，令 $\mathcal{U}^{\pi}$ 表示任何与需求无关的外生策略随机化，并定义需求前历史为 $H_t^{\pi} := \sigma(U^{\pi}, B_1, \mathbf{I}_1, (Y_\tau, S_\tau, B_{\tau+1}, \mathbf{I}_{\tau+1})_{\tau < t})$。在每个时期 $t$，策略 $\pi$ 在历史 $H_t^{\pi}$ 下选择一个可行配送 $\mathbf{Y}_t$。对于固定的策略 $\pi$，令 $\mathbb{P}^\pi, \mathbb{E}^\pi$ 表示条件概率和期望。我们假设每个店铺 $i$ 的单位利润、持有成本和缺货成本满足 $c_i \geq 0, h_i \geq 0, b_i \geq 0, b_i > 0$，且 $b_i - c_i > 0$。对于流体比较，令 $\mu_i := \mathbb{E} D_i$，对于库存阈值 $y \geq 0$，定义期望销售为 $m_i(y) := \mathbb{E}[D_i \wedge y] = \int_0^y (1 - F_i(u)) du$，以及期望调整运营损失为
$$ \ell_i(y) := \mathbb{E} \left[ c_i (D_i \wedge y) + h_i (y - D_i)^+ + b_i (D_i - y)^+ \right] = h_i y + b_i \mu_i - (h_i + b_i - c_i) m_i(y). \tag{2.5} $$
其中 $m_i(y)$ 是共享系统库存的期望消耗量，而 $\ell_i(y)$ 是计入期末仓库费用后的相应期望决策相关成本。通过直接的库存核算计算，对于任何可容许策略 $\pi$，
$$ J_T^{\pi} = wW + \sum_{t=1}^{T} \sum_{i=1}^{N} \mathbb{E}^{\pi} \ell_i(Y_{i,t}), \tag{2.6} $$
$$ \sum_{t=1}^{T} \sum_{i=1}^{N} \mathbb{E}^{\pi} m_i(Y_{i,t}) = W - \mathbb{E}^{\pi} \left[ B_{T+1} + \sum_{i=1}^{N} I_{i,T+1} \right] \leq W = \gamma T. \tag{2.7} $$
精确的已知分布动态基准是同一可容许策略类上的最优值：
$$ J_T^* := \inf_{\pi \in \Pi^{\text{ad}}} J_T^{\pi}. $$