Optimal Hidden-Target Learning for Online Inventory Optimization on General Convex Sets¶
会议: NeurIPS 2026
arXiv: 2606.14679
OpenReview: https://openreview.net/forum?id=veDCFlujwu
领域: 优化/理论
关键词: 在线库存优化, 在线凸优化, 隐目标投影, 范数对齐, 极小极大遗憾界
一句话总结¶
针对一般有界凸容量约束下的在线库存优化（OIO），本文证明了简单的隐目标投影算法具备最优性，通过引入范数对齐原则将状态相关可行性规约为一维 Lindley 排队控制，将遗憾界对公共需求概率的依赖提升至最优的 \(O(\sqrt{T/\mu})\)，并给出了匹配的下界与强凸/动态扩展。
研究背景与动机¶
多周期库存控制是运筹学与随机控制的奠基性问题之一。随着数据驱动决策的发展，在线库存优化（Online Inventory Optimization, OIO）将经典周期盘点库存模型扩展到了对抗式在线学习的框架中。在每一轮决策中，零售商或仓储履约系统面对多品类商品选择补货至库存水平（order-up-to level），同时承担因需求耗尽库存产生的持有成本与缺货损失。与标准在线凸优化（OCO）相比，库存控制的核心物理特性在于库存结转（inventory carryover）：商品只能通过需求消耗，不能凭空消失；若上一轮留存库存高于梯度下降提议的新目标，该目标在物理上便不可行。这种状态相关的可行域约束打破了传统 OCO 的独立性假设。
此前处理一般凸容量约束的代表性算法 MaxCOSD 采用了自适应周期控制策略：当提出的更新与当前库存状态不兼容时，算法选择等待足够的需求清空冗余库存后再执行更新。在所有商品同时出现正需求的公共需求非退化条件（UPPD，概率参数为 \(\mu\)）下，MaxCOSD 能够取得 \(\widetilde{O}(\sqrt{T}/\mu)\) 的静态遗憾界。然而，其线性依赖反比因子 \(1/\mu\) 在多品类或间歇性需求系统中会导致极长的等待时间，成为性能瓶颈。另一类在随机单品类或线性仓库约束中广受欢迎的思路是“隐目标（hidden-target）”投影：底层在线学习器在无约束凸集上维护一个理想目标，再将其投影到当前物理可行的库存集合上。尽管隐目标方法在单线性约束下表现优异，但既有理论分析完全依赖于线性仓库预算的品类逐项消耗（productwise sell-out）与守恒关系；当面对一般弯曲凸集约束时，某一维度的物理约束会导致不相关的其他维度产生任意大幅度的向下拉扯，使得品类逐项排队分析彻底失效。
为了打破对特殊线性结构的依赖并消除次优的 \(\mu\) 依赖，本文重新审视了隐目标投影的几何本质。核心 idea：提出范数对齐原则（Norm Alignment Principle），证明在与投影算子完全一致的可容许范数度量下，隐目标到可行域的距离在路径级严格遵循标量 Lindley 排队递推，从而将高维状态相关库存控制规约为一维排队系统，在任意有界凸集上实现极小极大最优的 \(\widetilde{O}(\sqrt{T/\mu})\) 遗憾界。
方法详解¶
整体框架¶
算法采用两层解耦架构：底层运行一个标准在线凸学习器（Base Learner），在固定的有界凸容量集 \(\mathcal{Y} \subseteq \mathbb{R}_+^n\) 内更新理想隐目标 \(z_t\)；物理执行层负责将 \(z_t\) 投影到当前受物理库存约束的可执行集合 \(J_t\) 上，得到实际补货水平 \(y_t\)。环境产生需求 \(d_t\) 与损失函数 \(\ell_t\) 后，系统仅向底层学习器反馈在实际执行点 \(y_t\) 处采样的次梯度 \(g_t \in \partial \ell_t(y_t)\)，底层学习器借助线性化损失更新下一轮隐目标 \(z_{t+1}\)。
整体管道的信息流与几何排队机制可通过下方流程图直观展现：
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["当前物理库存状态 x_t 与凸容量集 Y"] --> B["构建可执行集合<br/>J_t = Y ∩ {y >= x_t}"]
C["底层学习器隐目标 z_t"] --> D["范数对齐投影<br/>y_t = Proj_Jt(z_t)"]
B --> D
D --> E["实施物理补货 y_t 并经历对抗需求 d_t"]
E --> F["标量排队递推更新<br/>q_t+1 <= [q_t + ||z_t+1 - z_t|| - d_t^min]+"]
E --> G["次梯度反馈 g_t"]
G --> H["窗口受限步长调节更新<br/>z_t+1 = Proj_Y(z_t - eta_t g_t)"]
H --> C关键设计¶
1. 范数对齐原则与标量 Lindley 排队规约：建立统一几何度量以消除维数惩罚与结构依赖
既有文献在处理隐目标误差时，通常在 \(\ell_2\) 投影下强行考察 \(\ell_1\) 范数下的目标差距，这种范数混用在一般弯曲凸集上会导致不可恢复的常数发散。本文提出范数对齐原则：必须选用一个支配 \(\ell_\infty\) 范数的可容许范数 \(\|\cdot\|\)（即对任意向量满足 \(\|x\|_\infty \leq \|x\|\)，例如所有 \(\ell_p\) 范数 \(p \in [1, \infty]\)），并严格在同一个范数下统一定义投影算子、排队状态变量 \(q_t = \text{dist}_{\|\cdot\|}(z_t, J_t) = \|z_t - y_t\|\) 以及目标移动量 \(\|z_{t+1} - z_t\|\)。
在可容许范数下，若点位移动满足 \(\|y' - y\| \leq d_t^{\min} := \min_{i} d_{t,i}\)，由可容许性直接导出坐标级下界 \(y' \succeq (y - d_t)^+ \succeq x_{t+1}\)，确保短距离位移始终物理可行。在此几何事实支撑下，通过在线段 \([y_t, z_{t+1}]\) 上构造距离 \(y_t\) 为 \(d_t^{\min}\) 的可行插值见证点 \(w_t \in J_{t+1}\)，并结合最近点投影的最优性证书与三角不等式，直接导出无分布假设的路径级标量 Lindley 排队递推：
该递推在几何上揭示了目标与物理实现的偏差演化：底层目标的位移 \(\|z_{t+1} - z_t\|\) 构成排队系统的“到达（Arrival）”，而公共需求 \(d_t^{\min}\) 构成“服务（Service）”。高维弯曲集合上的库存结转约束由此无损降维至一维队列控制。
2. 窗口受限步长调节与 OCO 切换代价规约：消除清空窗口积累误差
在 UPPD 条件下，每轮存在至少 \(\mu\) 的条件概率出现大小至少为 \(\rho\) 的公共需求冲击。在长度为 \(B_\delta = \lceil \mu^{-1} \log(T/\delta) \rceil\) 的清空窗口内，该冲击高概率至少发生一次。为了避免排队误差跨窗口累积，本文对底层学习器的移动施加局部窗口约束：要求在任意 \(B_\delta\) 窗口内累积移动不超过 \(\rho\)。由此，累积物理实现差距 \(\Delta_T^{\text{gap}} = \sum_{t=1}^T \|z_t - y_t\|\) 可直接受控于总目标移动量：\(\Delta_T^{\text{gap}} \le B_\delta \Delta_T^{\text{mv}}\)。
对于在线梯度下降（HT-OGD），通过设置衰减步长 \(\eta_t = \gamma D_2 / (G_2 \sqrt{t})\) 并将乘子约束在 \(\gamma \le \rho / (2 D_2 \sqrt{B_\delta})\)，巧妙平衡了底层 OCO 线性化遗憾 \(O(D_2 G_2 \sqrt{T}/\gamma)\) 与库存物理实现惩罚 \(G_* B_\delta \Delta_T^{\text{mv}} = O(D_2 G_2 \gamma B_\delta \sqrt{T})\)。选取最优平衡点 \(\gamma = \Theta(B_\delta^{-1/2})\)，即可得到遗憾界：
将此前最优的 \(1/\mu\) 依赖大幅降低为 \(\mu^{-1/2}\)，并且在界中完全消除了显式的品类维度因子 \(n^{1/4}\)。
3. 极小极大匹配下界构造：基于伯努利公共需求与受限动作翻转
为了证明 \(O(\sqrt{T/\mu})\) 依赖的本质最优性，本文构造了二维单纯形容量集 \(\mathcal{Y}_L = \{y \in \mathbb{R}_+^2 \mid y_1 + y_2 = 1\}\) 下的对抗实例。在需求为 0 的轮次中，物理约束 \(y_t \succeq x_t\) 结合等式约束迫使任意在线策略必须严格维持与前一轮完全相同的动作向量。因此，系统被随机划分为长度期望为 \(1/\mu\) 的常数动作区间（Block）。通过在每个独立 Block 上分配独立的随机线性损失方向，算法在 Block 内部无法调整，而离线最佳静态比较器可在全时程汇总各 Block 的不平衡度。由此证明任何算法的期望遗憾必满足 \(\Omega(\sqrt{T/\mu})\)，确立了隐目标学习在一般凸集 OIO 中的极小极大最优性。
损失函数 / 训练策略¶
对于拓展场景，算法提供了通用的拓展接口： 1. 强凸损失：利用强凸损失提供的二次下界 \(\frac{\alpha}{4}\|z_t - u\|^2\)，采用曲率自适应步长 \(\eta_t = \frac{2}{\alpha(t + s_\delta)}\)，将静态遗憾由次线性压缩至多对数阶 \(O\left(\frac{\log(T/\delta)\log T}{\mu}\right)\)。 2. 动态遗憾：以欧氏路径变差 \(P_{T,2} = \sum_{t=2}^T \|u_t - u_{t-1}\|_2\) 为基准。在 \(P_{T,2}\) 已知时采用恒定步长 \(\eta^*\)，未知时将底层替换为平滑在线梯度下降（SOGD），在一般凸集上达成 \(\widetilde{O}\left(\sqrt{(1 + P_{T,2})T/\mu}\right)\) 的动态遗憾界。 3. 在线镜像下降（HT-OMD）：若底层采用对可容许范数 \(\|\cdot\|\) 具备 \(\sigma\)-强凸正则化子 \(R\) 的 OMD，以恒定步长更新，可取得几何敏感界 \(\widetilde{O}\left(G_* \sqrt{\mathcal{B}_R T / (\sigma \mu)}\right)\)。例如在单纯形上选用负熵正则子配对 \(\ell_1\) 范数，对坐标密集型梯度可带来高达 \(\sqrt{n / \log n}\) 的界紧致性改善。
实验关键数据¶
主实验¶
论文在三类典型设置下进行了主实验对比：标准线性仓库容量集（Setting 3 of Hihat et al., 2023）、带曲面约束的正 \(\ell_2\) 球容量集 \(\mathcal{Y} = \{y \in \mathbb{R}_+^n \mid \|y\|_2 \le R\}\)，以及真实世界大型沃尔玛零售数据集（M5 Forecasting Competition, \(n=3049\) 种商品，覆盖 10 家门店共 \(T=1913\) 天）。各算法均基于报童损失（Newsvendor Loss, \(h_i=1, p_i=200\)）进行学习率调优与离线最佳固定基准比对。
| 实验环境与容量集 | 比较指标 | HT-OGD (本文) | DDM (Shi et al., 2016) | MaxCOSD (Hihat et al., 2023) | 相对优势 / 理论状态 |
|---|---|---|---|---|---|
| 线性仓库集 (\(n=100, C=175\)) | 稳态累积遗憾 (\(T=5000\)) | 最低且稳定 (次线性低斜率) | 次线性但数值显著高于本文 | 累积最快，随时间陡峭上升 | 最优调优区间宽，对学习率倍率最不敏感 |
| 弯曲 \(\ell_2\) 球面 (\(n=100, R=22.5\)) | 稳态累积遗憾 (\(T=5000\)) | 最低 (严格保持稳定次线性) | 居中 (无理论保证) | 显著落后 (周期等待开销大) | 验证了非线性凸集下排队理论的有效性 |
| M5 真实零售数据 (\(n=3049, C=6600\)) | 跨 10 门店平均静态遗憾 | 显著占优 (大幅领先 baseline) | 居中 | 劣势显著 | 在高维、非平稳、间歇性真实需求下表现优异 |
消融与理论验证实验¶
论文通过设计多组针对性单变量控制实验，对关键理论断言进行了严格验证：
| 实验配置 / 验证场景 | 核心检验变量 | 理论预期规律 | 实测表现与说明 |
|---|---|---|---|
| 维度缩放应力测试 (幂律需求 \(d_{t,i} \propto i^{-1.1}\)) | 商品品类数 \(n \in [100, 3000]\) | 移除显式 \(n^{1/4}\) 依赖，无额外维度惩罚 | 随 \(n\) 增长遗憾保持近乎平坦，显著优于传统品类分解方法 |
| 强凸损失 (二次损失 \(\frac{1}{2}(y - d_t)^2\)) | 步长策略 \(\eta_t \propto 1/t\) vs \(1/\sqrt{t}\) | \(1/t\) 达成多对数级遗憾，快于 \(1/\sqrt{t}\) | \(\eta_t \propto 1/t\) 呈现平缓对数增长，与次线性 \(1/\sqrt{t}\) 形成明显分离 |
| 动态遗憾验证 (分块常数需求，\(P_{T,2} = O(\sqrt{T})\)) | 恒定适配步长 \(\eta^*\) vs 静态衰减步长 | 变差适配步长达成 \(O(T^{3/4})\) 动态遗憾 | 适配恒定步长动态遗憾显著更低且斜率严格吻合 \(T^{3/4}\) 预测 |
关键发现¶
- 对一般凸几何的无缝迁移：在正 \(\ell_2\) 球凸集约束下，DDM 因失去线性守恒等式而缺乏收敛性证明，MaxCOSD 则因等待全品类库存消耗而频繁停滞；HT-OGD 凭借范数对齐的几何投影，在弯曲边界上表现出与线性约束下完全一致的低遗憾收敛轨迹。
- 超参数宽容度极高：在学习率乘子 \(\gamma\) 的对数网格扫描中（跨越 6 个数量级），HT-OGD 展现出了极为宽广的最优收敛平台期，而 MaxCOSD 与 DDM 稍偏离最佳学习率即出现遗憾急剧恶化。
- 真实数据鲁棒性：面对 M5 数据集中高度稀疏与间歇性的真实销售序列，即使 UPPD 条件下的常数 \(\mu\) 极小，几何投影机制依然能稳定平抑各品类的过度补货波动。
亮点与洞察¶
- 范数对齐统一几何状态量：将以往基于商品品类坐标轴逐维分解的思路，转变为“目标点到可行集凸投影距离”的全局度量，彻底摆脱了线性仓库守恒等式的束缚，不仅理论优雅且彻底解耦了算法更新与库存物理层。
- 以排队服务视角理解需求冲击：巧妙地将底层学习器的移动抽象为“排队到达”，将各品类最小的公共需求冲击抽象为“排队服务”，将复杂的带记忆物理决策降维为经典 Lindley 过程，极具启发性。
- 消除隐式维数惩罚：分析严格遵从现代 OCO 范式，所有理论上界均以集合直径 \(D\)、对偶梯度界 \(G_*\) 和需求参数 \(\mu, \rho\) 表达，消除了先前工作为缝合品类误差而强行引入的 \(n^{1/4}\) 等多项式维数包袱。
局限与展望¶
- 依赖系统级公共正需求（UPPD）：UPPD 假设所有品类在同一时刻以一定概率同时具有正需求。在成千上万种极度稀疏的长尾商品场景中，全品类同时满足正需求的概率 \(\mu\) 可能随维度指数级衰减，未来需发展基于局部清空（Local Clearing）的更细粒度理论。
- 依赖环境先验参数调优：最优步长选择需要事先知晓需求概率 \(\mu\)、冲击大小 \(\rho\) 或路径变差 \(P_T\)。尽管可借助元学习框架处理动态遗憾，但实现完全无参数自适应（Parameter-free）在线库存优化仍有待探索。
相关工作与启发¶
- vs MaxCOSD (Hihat et al., 2023)：MaxCOSD 采用自适应周期等待机制，静态遗憾界依赖于次优的 \(O(\sqrt{T}/\mu)\)；本文隐目标投影机制保持每轮连续更新与投影，将界收敛至极小极大最优的 \(O(\sqrt{T/\mu})\)。
- vs HT-OIO (Ichikawa et al., 2026)：Ichikawa 等人的分析限定在单一线性容量约束，其品类分解法引入了显式的 \(n^{1/4}\) 维数因子，且动态变差依赖于更宽松的 \(\ell_1\) 范数 \(P_{T,1}\)；本文范数对齐原则适用于任意有界凸集，去除了 \(n^{1/4}\) 并将动态变差紧缩至欧氏范数 \(P_{T,2}\)。
- vs DDM (Shi et al., 2016) / OMD (Guo et al., 2026)：既有随机库存学习多聚焦于无偏梯度采样与线性仓储下的周期策略；本文全面拓展至对抗性损失、非平稳环境以及一般凸集，并统一了镜像下降在非欧几何下的扩展。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次建立一般凸集下 OIO 的几何排队规约，提出范数对齐原则，理论突破显著。
- 实验充分度: ⭐⭐⭐⭐☆ 涵盖线性、弯曲球面、真实 M5 数据集以及关于维度、强凸、动态的多维度验证，表现扎实。
- 写作质量: ⭐⭐⭐⭐⭐ 数学推导严密自洽，几何插图与直觉铺陈清晰，符号系统规范。
- 价值: ⭐⭐⭐⭐⭐ 彻底解决了 OIO 在一般凸容量集上的理论开销瓶颈，对在线控制与带状态记忆的学习具有重要理论指导价值。