Optimal Hidden-Target Learning for Online Inventory Optimization on General Convex Sets

技术摘要：一般凸集上最优隐藏目标学习的在线库存优化

问题定义
本文研究在线库存优化（Online Inventory Optimization, OIO）问题，即学习者需从容量集 $Y \subseteq \mathbb{R}^n_+$ 中选择订货向量 $y_t$，并受物理库存约束。与标准的在线凸优化（OCO）不同，OIO 具有“物理记忆”特征：在时间 $t$ 的可行动作集 $J_t = Y \cap \{y \mid y \succeq x_t\}$ 取决于当前的库存状态 $x_t$。库存会结转，这意味着学习者不能简单地将梯度步投影到 $Y$ 上，如果结果向量低于当前库存水平。环境会选择对抗性需求 $d_t$ 和损失函数 $\ell_t$，学习者的目标是针对比较序列最小化动态或静态遗憾（regret）。

先前的工作（如 Hihat et al., 2023 的 MaxCOSD）通过自适应周期处理了一般凸容量集，实现了在均匀可能正需求（UPPD）条件下 $\tilde{O}(\sqrt{T/\mu})$ 的静态遗憾。然而，这种对 $1/\mu$（其中 $\mu$ 是共同需求冲击的概率）的依赖是次优的，且现有的隐藏目标方法由于依赖于逐分量（product-wise）的“售罄”分析，仅限于线性容量约束。

方法论：范数对齐的隐藏目标投影
作者提出，只要利用特定的几何框架，维持一个隐藏目标 $z_t$ 并将其投影到可行集 $J_t$ 的简单原则对于一般凸集也是足够的。

1. 算法： 学习者维护一个由基础在线学习算法（如在线梯度下降法 OGD）生成的隐藏目标序列 $z_t \in Y$。实现的动作是 $y_t = \text{Proj}_{J_t}^{\|\cdot\|}(z_t)$，即 $z_t$ 在特定范数 $\|\cdot\|$ 下到可行集 $J_t$ 的投影。
2. 范数对齐原则： 一个关键的方法论贡献是要求投影范数、队列状态度量以及目标移动度量都使用相同的容许范数 $\|\cdot\|$。容许范数支配 $\ell_\infty$ 范数（即 $\|x\|_\infty \le \|x\|$）。
3. 几何队列缩减： 分析的核心定义了“目标-实现差距”为 $q_t = \|z_t - y_t\|$。作者证明了一个路径几何递归（一种 Lindley 队列）：
   $$q_{t+1} \le [q_t + \|z_{t+1} - z_t\| - d^{\min}_t]_+$$
   其中 $d^{\min}_t = \min_i d_{t,i}$ 是共同需求。
   • 解释： 差距的演变类似于一个一维队列。移动隐藏目标（$z_{t+1} - z_t$）充当“到达”，而共同需求（$d^{\min}_t$）充当“服务”。
   • 意义： 这种缩减将复杂的、状态相关的可行性问题转化为一个带有额外切换成本的标准 OCO 问题。它避免了需要逐分量核算或线性约束，从而打破了以往阻碍推广到弯曲凸集的限制。

核心贡献与结果

1. 凸损失下的最优静态遗憾：
   通过将基础学习器实例化为在线梯度下降法（OGD），本文实现了 $\tilde{O}(\sqrt{T/\mu})$ 的静态遗憾。这改进了此前针对一般凸集最优为 $O(1/\mu)$ 的保证，达到了 $O(1/\sqrt{\mu})$。作者证明了匹配的下界 $\Omega(\sqrt{T/\mu})$，确立了该速率在 UPPD 条件下的极小极大最优性（minimax optimal）。

2. 强凸损失下的多对数级遗憾：
   对于 $\alpha$-强凸损失，同一框架可产生 $\tilde{O}(\log(T/\mu))$ 的遗憾界。这解决了关于在对抗性 OIO 中针对一般容量集是否能实现多对数级遗憾的开放性问题。

3. 改进的动态遗憾：
   该方法提供的动态遗憾保证取决于比较序列的欧几里得路径变分 $P_{T,2}$，而非先前隐藏目标分析中使用的 $\ell_1$ 变分 $P_{T,1}$。这消除了显式的 $n^{1/4}$ 因子，并为稠密比较器移动的情况提供了更紧凑的界。作者利用标准 OGD（针对已知变分）和光滑 OGD（SOGD，针对未知变分）来实现这些结果。

4. 通过镜像下降进行的几何敏感优化：
   该框架扩展到了带有强凸正则化项的在线镜像下降（OMD）。这使得遗憾界能够适应容量集 $Y$ 的特定几何结构以及梯度的对偶范数。例如，在梯度坐标稠密时，使用线性约束上的熵正则化可以改善与维度 $n$ 的依赖关系，相比于欧几里得投影。

5. 无维度依赖的保证：
   结果在标准 OCO 意义上是无维度的；维度 $n$ 仅通过问题参数（如 $Y$ 的直径或梯度界限）进入模型，而非作为显式的乘性因子（如 $n^{1/4}$）。

意义与主张
本文声称，“隐藏目标投影”原则（通常被视为一种经验启发式方法或局限于线性约束）在与“范数对齐”几何分析结合时，对于完整的广义凸容量集 OIO 模型是理论最优的。

• 理论统一： 本工作通过展示物理可行性约束可以与学习算法解耦，将库存控制与标准 OCO 统一起来。库存层充当一个队列清空机制，它对基础学习器施加一个切换成本，而无需基础学习器理解库存动态。
• 解决障碍： 本文证明，通过在容许范数中将状态测量为单一几何距离，可以绕过阻碍将队列分析扩展到一般凸集的障碍（即缺乏逐分量误差的守恒恒等式）。
• 实证验证： 在合成数据和真实世界 M5 预测竞赛数据上的实验证实，所提出的 HT-OGD 算法在处理线性及弯曲容量设置时，在遗憾表现上均优于 MaxCOSD 和 DDM（一种逐分量方法），验证了其在遗憾界方面的理论改进。

作者总结道，这种模块化模板——即将学习隐藏目标与通过范数对齐队列执行物理可行性分离——为未来具有状态相关约束的在线问题提供了一个稳健的框架。