新算法让在线决策更快更准，兼顾计算效率与精度。
Wait-Less Offline Tuning and Re-solving for Online Decision Making
- 定期重解线性规划，用最新价格指导实时决策。
- 每间隔频率 $f$ 重解一次，理论后悔上界为 $\mathscr{O}(\log(T/f) + \sqrt{f})$。
- 适合大规模资源分配场景，兼顾速度与性能。
在线线性规划（OLP）在收益管理和资源分配中应用广泛。当前最优的OLP算法通过反复求解包含更新资源信息的线性规划（LP）子问题来实现低后悔。然而，基于LP的方法计算开销大，难以应对大规模应用。相比之下，近期的一阶方法虽计算高效，但后悔保证较弱。为此，我们提出一种新算法，融合了基于LP和一阶方法的优势：以预设频率 $f$ 定期重解LP子问题，并利用最新的对偶价格指导在线决策；同时，在两次重解之间并行运行一阶方法，平滑资源消耗。该算法实现了 $\mathscr{O}(\log(T/f) + \sqrt{f})$ 的后悔上界，带来‘无需等待’的在线决策过程，平衡了计算效率与后悔性能。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。