提出最优隐目标学习法,显著提升在线库存优化的性能。
Optimal Hidden-Target Learning for Online Inventory Optimization on General Convex Sets

- 用隐目标投影法解决库存跨期依赖问题,理论更优。
- 将后悔值对常见需求概率的依赖从倒数降至平方根倒数。
- 适用于一般凸容量集,适合研究在线优化与供应链管理的人。
在线库存优化(OIO)是带有物理记忆的在线凸优化:库存结转使可行动作集依赖于历史。一种自然原则——由在线学习者选择一个隐目标,并将其投影到当前可行的订货补货集——在单线性容量约束下已被使用。本文证明该原则在任意有界凸容量集上均最优。以在线梯度下降为基学习器,该方法将一般凸集上OIO的最佳已知后悔界从对常见需求概率的逆关系改进为平方根倒数关系,并给出了匹配的下界。同一原则首次实现了强凸损失下的多项式对数级后悔保证,以及适应欧氏路径变化的动态后悔保证。分析引入了范数对齐原理:正确状态变量是隐目标到可行集的距离,采用与投影一致的范数度量。在此条件下,该距离路径上演化为一维队列,目标移动为到达,共同需求为服务。此简化为一维队列控制,解决了状态依赖问题,将保证推广至一般凸容量集,超越了以往逐项处理方法的局限。合成数据与真实库存数据的实验验证了理论结果。
原文摘要 · Abstract (English)
Online inventory optimization (OIO) is online convex optimization with physical memory: inventory carryover makes the feasible action set depend on the past. A natural principle, used in stochastic inventory learning and recently in OIO under a single linear capacity constraint, is to maintain a hidden target chosen by an online learner and implement its projection onto the currently feasible order-up-to set. We prove that this simple principle is optimal for OIO on arbitrary bounded convex capacity sets. With online gradient descent as the base learner, the method improves the best known regret guarantee for OIO on general convex sets from inverse to inverse-square-root dependence on the common-demand probability, and we prove a matching lower bound. The same principle gives the first polylogarithmic regret guarantee for strongly convex losses and the first dynamic regret guarantee adapting to Euclidean path variation on general convex capacity sets. The analysis introduces a norm alignment principle: the right state variable is the distance from the hidden target to the feasible set, measured in the same norm as the projection. Under norm alignment, this distance evolves pathwise as a scalar queue, with target movement as arrival and common demand as service. This reduction to one-dimensional queue control resolves the state dependence and extends the guarantees to general convex capacity sets, beyond the reach of prior productwise approaches. Experiments on synthetic and real-world inventory data corroborate the theory.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。