Decoupling Learning and Decision-Making: Breaking the O(T) Barrier in Online Resource Allocation with First-Order Methods

Abstract

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. For the first time, we show that first-order methods can attain regret O(T^1/3) with this new framework.

Tasks

Reproductions