Decoupling Learning and Decision-Making: Breaking the
  $\mathcal{O}(\sqrt{T})$ Barrier in Online Resource Allocation with
  First-Order Methods
Wenzhi Gao Chunlin Sun Chenyu Xue Dongdong Ge Yinyu Ye
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 several important facts about online
linear programming, which unveils the challenge for first-order-method-based
online algorithms to achieve beyond $\mathcal{O}(\sqrt{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 $\mathcal{O}(T^{1/3})$ with this new
framework. Lastly, we conduct numerical experiments to validate our theoretical
findings.