Beyond O(√T) Regret: Decoupling Learning and Decision-making in Online Linear Programming

Wenzhi Gao, Dongdong Ge, Chenyu Xue, Chunlin Sun, Yinyu YearXiv 2025 · OpenReview

TL;DR

This paper breaks the long-standing $O(\sqrt{T})$ regret barrier for first-order methods in Online Linear Programming (OLP). By identifying a fundamental "dilemma" where good learning algorithms make for poor decision-makers, the authors propose a framework that decouples these two tasks. This achieves $O(\log T)$ regret with the computational efficiency of simple gradient-based updates, making it up to 74,000 times faster than traditional LP-based methods.

The Challenge: The Regret-Complexity Trade-off

Online Linear Programming (OLP) is the engine behind real-time resource allocation, such as ad auctions and cloud scheduling. In these systems, decisions must be made instantly under budget constraints. Historically, researchers faced a trade-off:

  1. LP-based methods: Guaranteed near-perfect "regret" (the performance gap vs. an optimal hindsight strategy) of $O(\log T)$, but were computationally expensive.
  2. First-order methods: Extremely fast and scalable (e.g., subgradient descent) but typically limited to $O(\sqrt{T})$ regret.
Comparison of regret bounds across different OLP settings and algorithms.

The table above illustrates the landscape: while LP-based methods achieved logarithmic regret, first-order methods remained stuck at square-root regret or required very specific assumptions. The authors set out to bridge this gap.

Methods: The First-Order Approach and the Decoupling Framework

The authors focus on improving first-order methods, which rely on simple updates rather than solving full linear programs at every step.

The standard first-order subgradient OLP algorithm.

The Learning-Decision Dilemma

A key insight of this paper is that a single algorithm cannot effectively learn and decide simultaneously. To learn an optimal price (dual solution) accurately, an algorithm needs a tiny, vanishing step size. However, to make robust decisions in a stochastic environment, the algorithm needs a larger step size to remain "adaptive" to noise. If a stochastic shock pushes the price away from the optimum, a tiny step size prevents the algorithm from recovering fast enough, leading to massive accumulated regret.

The Solution: Decoupling

To resolve this, the authors introduce a framework that separates these tasks:

  • Phase 1: Exploration/Learning: Two processes run in parallel. One focuses purely on learning the optimal dual solution with high precision, while the other handles initial decisions.
  • Phase 2: Exploitation/Localization: Once the exploration phase ends, the algorithm "restarts" decision-making in a localized neighborhood around the learned optimal solution, using a step size specifically tuned for the problem's "Dual Error Bound."

Key Results and Insights

The proposed framework achieves significant theoretical and practical milestones:

  • Theoretical Breakthrough: It proves that first-order methods can achieve $O(\log T)$ regret in finite support settings and $O(T^{1/3})$ in continuous settings, significantly outperforming the previous $O(\sqrt{T})$ standard.
  • Massive Speed Gains: In experiments with $10^5$ iterations, the new framework was 74,000 times faster than LP-based methods (0.064s vs. 4742s) while maintaining comparable regret.
  • Robustness: Unlike previous methods that required strict "non-degeneracy" (no ties in optimal solutions), this framework works under a broader class of "Hölder error bound" conditions.

Conclusion

By decoupling learning from decision-making, this research provides a path toward online algorithms that are both theoretically optimal and practically scalable. This principle of "learning the neighborhood" before refining decisions could potentially be applied to a wide range of online convex optimization problems beyond linear programming.

Summary updated

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 $\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.
BibTeX
@misc{gao2025beyond,
  author = {Wenzhi Gao and Dongdong Ge and Chenyu Xue and Chunlin Sun and Yinyu Ye},
  title = {{Beyond O(√T) Regret: Decoupling Learning and Decision-making in Online Linear Programming}},
  year = {2025},
  eprint = {2501.02761},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.02761},
}

Loading related content...

Figure