突破在线线性规划的平方根后悔上界，实现更优决策性能。
Beyond $\mathcal{O}(\sqrt{T})$ Regret: Decoupling Learning and Decision-making in Online Linear Programming
- 分离学习与决策过程，构建新框架提升算法效率
- 连续支持下实现小o(√T)后悔，有限支持下达O(log T)水平
- 适用于资源分配与收益管理场景，适合关注优化理论的研究者
在线线性规划在收益管理和资源配置中具有重要作用，近年来研究聚焦于高效的梯度类在线学习算法。尽管这类方法在实践中表现良好，但其后悔值通常不超过𝑂(√𝑇)，低于基于线性规划（LP）的最优算法所保证的𝑂(𝑙𝑜𝑔𝑇)。本文建立了一个通用框架，在LP对偶问题满足特定误差边界条件时，可超越𝑂(√𝑇)的后悔上界。首次证明在连续支持下，梯度类算法可实现𝑜(√𝑇)后悔；在有限支持下，即使不依赖非退化假设，也能达到𝑂(𝑙𝑜𝑔𝑇)后悔。结果显著改进了现有最先进性能，并为序贯决策提供了新视角。
原文摘要 · Abstract (English)
Online linear programming plays an important role in both revenue management and resource allocation, and recent research has focused on developing efficient first-order online learning algorithms. Despite the empirical success of first-order methods, they typically achieve a regret no better than $\mathcal{O} ( \sqrt{T} )$, which is suboptimal compared to the $\mathcal{O} (\log T)$ bound guaranteed by the state-of-the-art linear programming (LP)-based online algorithms. This paper establishes a general framework that improves upon the $\mathcal{O} ( \sqrt{T} )$ result when the LP dual problem exhibits certain error bound conditions. For the first time, we show that first-order learning algorithms achieve $o( \sqrt{T} )$ regret in the continuous support setting and $\mathcal{O} (\log T)$ regret in the finite support setting beyond the non-degeneracy assumption. Our results significantly improve the state-of-the-art regret results and provide new insights for sequential decision-making.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。