Wait-Less Offline Tuning and Re-solving for Online Decision Making
This addresses computational bottlenecks in large-scale OLP applications like revenue management, offering a balanced solution for practitioners, though it is incremental in combining existing approaches.
The paper tackles the trade-off between computational efficiency and regret guarantees in online linear programming (OLP) by proposing a hybrid algorithm that periodically re-solves LP subproblems and uses first-order methods in between, achieving O(log(T/f) + sqrt(f)) regret.
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. In contrast, recent first-order OLP algorithms are more computationally efficient but typically suffer from worse regret guarantees. To address these shortcomings, we propose a new algorithm that combines the strengths of LP-based and first-order OLP methods. The algorithm re-solves the LP subproblems periodically at a predefined frequency $f$ and uses the latest dual prices to guide online decision-making. In addition, a first-order method runs in parallel during each interval between LP re-solves, smoothing resource consumption. Our algorithm achieves $\mathscr{O}(\log (T/f) + \sqrt{f})$ regret, delivering a "wait-less" online decision-making process that balances the computational efficiency of first-order methods and the superior regret guarantee of LP-based methods.