Beyond $\mathcal{O}(\sqrt{T})$ Regret: Decoupling Learning and Decision-making in Online Linear Programming
This work addresses a bottleneck in revenue management and resource allocation by enhancing regret bounds for first-order online learning algorithms, representing a strong specific gain rather than a broad paradigm shift.
The paper tackles the suboptimal regret of first-order methods in online linear programming, which typically achieve O(√T) regret compared to O(log T) bounds from LP-based algorithms, and shows that under certain error bound conditions, first-order algorithms can achieve o(√T) regret in continuous settings and O(log T) in finite settings, significantly improving state-of-the-art results.
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.