Key points are not available for this paper at this time.
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 O (T), which is suboptimal compared to the O (T) bound guaranteed by the state-of-the-art linear programming (LP) -based online algorithms. This paper establishes several important facts about online linear programming, which unveils the challenge for first-order-method-based online algorithms to achieve beyond O (T) regret. To address the challenge, we introduce a new algorithmic framework that decouples learning from decision-making. More importantly, for the first time, we show that first-order methods can attain regret O (T^1/3) with this new framework. Lastly, we conduct numerical experiments to validate our theoretical findings.
Gao et al. (Sun,) studied this question.