Online resource allocation improves with fewer optimization solves
Online Resource Allocation with an Endogenous Markov State: Fewer LP Solves Earn More
Machine Learning
Summary
The paper looks at how to best manage limited resources over time when the system’s state changes based on past actions. The authors find that solving optimization problems less often can actually lead to better long-term results in many cases. They introduce algorithms that balance learning about the system and making resource decisions efficiently, achieving low regret (or loss) compared to the best possible policy. The findings also highlight risks of frequently re-optimizing, which can sometimes harm performance.
What this means in practice
- •For supply chain planners: Manage inventories over time with changing demand and supply conditions by using infrequent re-optimization schedules to improve performance and reduce computational load.
- •For cloud resource managers: Optimize allocation of computing resources with state changes based on prior allocations, reducing frequent computations while maintaining high-quality service decisions.
Authors
Zhaohua Chen
Abstract
We study finite-horizon online resource allocation with i.i.d. requests and an endogenous Markov state on a finite state space: each action affects the transition of the state that governs future rewards and resource consumption. In this problem, a transient fluid LP benchmark upper bounds the expected reward of every nonanticipating policy, while a stationary LP supplies randomized state-dependent controls. We assume that the stationary LP has a unique optimum and identify primal nondegeneracy and irreducibility of the optimal induced kernel as important regularity conditions in this framework. With a known request prior, we show that, under nondegeneracy and irreducibility, both frequent and infrequent re-solving attain $O(1)$ regret. However, under a degenerate optimum, irreducibility yields the sharp worst-case $Θ(\sqrt{T})$ rate for infrequent re-solving, while frequent re-solving can incur $Ω(T)$ regret. Thus, more frequent optimization can perform asymptotically worse. With an unknown request prior, we develop a three-phase U-shaped infrequent re-solving policy that coordinates learning and inventory correction with $O(\log\log T)$ LP solves. When the optimal induced kernel is irreducible and the algorithm is given the optimal target state class and a constant-cost entrance policy, it attains $O(1)$ regret under nondegeneracy and $O(\sqrt{T})$ regret under degeneracy. Without the target-class information, linear minimax regret is unavoidable. Numerical experiments further illustrate the instability of round-by-round re-solving relative to epoch-wise infrequent re-solving, show that thresholding greatly mitigates its loss, and find that infrequent schemes remain dominant under both known and estimated priors.