Wait-Less Offline Tuning and Re-solving for Online Decision Making

Online linear programming (OLP) has found broad applications in revenue management and resource allocation. State-of-the-art OLP algorithms achieve low regret by repeatedly solving linear programming (LP) subproblems that incorporate updated resource information. However, LP-based methods are computationally expensive and often inefficient for large-scale applications. By contrast, recent first-order OLP algorithms are more computationally efficient but typically suffer from weaker regret guarantees. To address these shortcomings, we propose a new algorithm that combines the strengths of LPbased and first-order OLP algorithms. Our algorithm re-solves the LP subproblems periodically at a predefined frequency f and uses the latest dual prices to guide online decision-making. In parallel, a first-order method runs during each interval between LP re-solves and smooths resource consumption. Our algorithm achieves O(log(T /f ) + √ f ) regret and delivers a "waitless" online decision-making process that balances computational efficiency and regret guarantees. Extensive experiments demonstrate at least 10-fold improvements in regret over firstorder methods and 100-fold improvements in runtime over LP-based methods.