Anthony Pineci, Yunzong Xu
We prove that the simple principle of maintaining a hidden target and projecting it is optimal for online inventory optimization on general convex sets.
Online inventory optimization is an online convex optimization problem where physical memory (inventory carryover) makes the feasible action set depend on the past. Prior work only showed optimality under a single linear capacity constraint, and optimal algorithms and regret lower bounds for general convex capacity sets were unknown.
We use the principle of maintaining a hidden target chosen by an online learner and projecting it onto the currently feasible order-up-to set. Using online gradient descent as the base learner, we introduce a norm alignment principle that reduces the distance from the hidden target to the feasible set to a scalar queue, thereby resolving state dependence via one-dimensional queue control.
We improve the regret guarantee for general convex capacity sets from inverse to inverse-square-root dependence on the common-demand probability and prove a matching lower bound. We provide the first polylogarithmic regret guarantee for strongly convex losses and the first dynamic regret guarantee adapting to Euclidean path variation on general convex sets. Experiments on synthetic and real-world inventory data corroborate the theory.