Beyond 𝒪 ⁡ ( T ) \mathcal{O}(\sqrt{T}) Regret: Decoupling Learning and Decision-making in Online Linear Programming

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

Read Beyond 𝒪 ⁡ ( T ) \mathcal{O}(\sqrt{T}) Regret: Decoupling Learning and Decision-making in Online Linear Programming by Wenzhi Gao, Dongdong Ge, Chunlin Sun, Chenyu Xue, Yinyu Ye (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-02761.txt.

Introduction

Five researchers improve online choice under limits in a 2025 paper on linear programming. Such problems guide revenue and the use of scarce resources, with choices made one step at a time. Fast methods exist, but their error has long been stuck at a known bound.

The team sets out a frame that splits learning from the act of choosing. Under set conditions on the mirror form of the problem, the error can fall below the old bound. In one setting it shrinks at the fastest rate known from costlier methods. The authors say the split gives fresh insight into step by step choice as a whole.

Catalog record

CREATORWenzhi Gao, Dongdong Ge, Chunlin Sun, Chenyu Xue, Yinyu Ye
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE114 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-02761

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Beyond 𝒪 ⁡ ( T ) \mathcal{O}(\sqrt{T}) Regret: Decoupling Learning and Decision-making in Online Linear Programming Wenzhi Gao, Dongdong Ge, Chunlin Sun, Chenyu Xue, Yinyu Ye 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 𝒪 ⁡ ( T ) \mathcal{O}(\sqrt{T}) , which is suboptimal compared to the 𝒪 ⁡ ( log ⁡ T ) \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 𝒪 ⁡ ( T ) \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 ⁡ ( T ) o(\sqrt{T}) regret in the continuous support setting and 𝒪 ⁡ ( log ⁡ T ) \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. 1 Introduction This paper presents a new algorithmic framework to solve the online linear programming (OLP) problem. In this context, a decision-maker receives a sequence of resource requests with bidding prices and sequentially makes irrevocable allocation decisions for these requests. OLP aims to maximize the accumulated reward subject to inventory or resource constraints. OLP plays an important role in a wide range of applications. For example, in online advertising [ 4 ] , an online platform has limited advertising slots on a web page. When a web page loads, online advertisers bid for ad placement, and the platform decides within milliseconds the slot allocation based on the features of advertisers and the user. The goal is to maximize the website’s revenue and improve user experience. Another example is online auction, where an online auction platform hosts a large number of auctions for different items. The platform must handle bids and update the auction status in real-time. Besides the aforementioned applications, OLP is also widely used in applications such as revenue management [ 29 ] , resource allocation [ 15 ] , cloud computing [ 12 ] , and many other applications [ 3 ] . Most state-of-the-art algorithms for OLP are dual linear program (LP)-based [ 1 , 16 , 22 , 19 , 22 ] . More specifically, these algorithms require solving a sequence of LPs to make online decisions. However, the high computational cost of these LP-based methods prevents their application in time-sensitive or large-scale problems. For example, in the aforementioned online advertising example, a decision has to be made in milliseconds, while LP-based methods can take minutes to hours on large-scale problems. This challenge motivates a recent line of research using first-order methods to address OLP [ 18 , 10 , 4 , 5 ] , which are based on gradient information and more scalable and computationally efficient than LP-based methods. Despite the advantage in computational efficiency, first-order methods are still not comparable to LP-based methods in terms of regret for many settings. Existing first-order OLP algorithms only achieve \mathcal{O}(\sqrt{T}) regret bound with only a few exceptions. When the distribution of requests and bidding prices has finite support [ 28 ] , \mathcal{O}(T^{3/8}) regret is obtainable using a three-stage algorithm; if first-order methods are used to solve the subproblems of LP-based methods infrequently, \mathcal{O}(\log^{2}T) regret is achievable in the continuous support setting under a uniform non-degeneracy assumption [ 22 ] . However, these methods are either complicated to implement or require strong assumptions. It remains open whether there exists a general framework that allows first-order methods to break the \mathcal{O}(\sqrt{T}) regret barrier. This paper answers this question affirmatively. 1.1 Contributions • We show that first-order methods achieve o(\sqrt{T}) regret under weaker assumptions than LP-based methods. In particular, we identify a dual error bound condition that is sufficient to guarantee lower regret of first-order methods when the dual LP problem has a unique optimal solution. In the continuous-support setting, we establish an \mathcal{O}(T^{1/3}) regret result under weaker assumptions than the existing methods; In the finite-support setting, we establish an \mathcal{O}(\log T) result, which significantly improves on the state-of-the-art \mathcal{O}(T^{3/8}) result and almost matches the \mathcal{O}(1) regret of LP-based methods. For problems with \gamma -Hölder growth condition, we establish a general {\mathcal{O}(T^{\frac{\gamma-1}{2\gamma-1}}\log T)} regret result, which interpolates among the settings of no growth ( \gamma=\infty ), continuous support with quadratic growth ( \gamma=2 ) and finite support with sharpness ( \gamma=1 ). Our results show that first-order methods perform well under strictly weaker conditions than LP-based methods and still achieve competitive performance, significantly advancing their applicability in practice. • We design a general exploration-exploitation framework to exploit the dual error bound condition. The idea is to learn a good approximation of the distribution dual optimal solution. Then, the online decision-making algorithm can be localized around a neighborhood of the approximate dual solution and makes decisions in an effective domain of size o(1) , thereby achieving improved regret guarantees. We reveal an important dilemma in simultaneously using a single first-order method as both learning and decision-making algorithms: a good learning algorithm can perform poorly in decision-making. This dilemma implies an important discrepancy between stochastic optimization and online decision-making, and it is addressed by decoupling learning and decision-making: two different first-order methods are adopted for learning and decision-making. This simple idea yields a highly flexible framework for online sequential decision-making. Our analysis can be of independent interest in the broader context of online convex optimization. Table 1: Regret results in the current OLP literature. \log\log factors are ignored. Paper Setting and assumptions Algorithm Regret Lower bound [ 19 ] Bounded, continuous support, uniform non-degeneracy LP-based \mathcal{O}(\log T) Yes [ 7 ] Bounded, continuous support, uniform non-degeneracy LP-based \mathcal{O}(\log T) Yes [ 13 ] Bounded, finite support of \mathbf{a}_{t} , quadratic growth LP-based \mathcal{O}(\log^{2}T) Unknown [ 22 ] Bounded, continuous support, uniform non-degeneracy LP-based \mathcal{O}(\log T) Yes [ 9 ] Bounded, finite support, non-degeneracy LP-based \mathcal{O}(1) Yes [ 18 ] Bounded Subgradient \mathcal{O}(\sqrt{T}) Yes [ 4 ] Bounded Mirror Descent \mathcal{O}(\sqrt{T}) Yes [ 10 ] Bounded Proximal Point \mathcal{O}(\sqrt{T}) Yes [ 5 ] Bounded Momentum \mathcal{O}(\sqrt{T}) Yes [ 28 ] Bounded, finite support, non-degeneracy Subgradient \mathcal{O}(T^{3/8}) No ( \mathcal{O}(1) ) [ 22 ] Bounded, continuous support, uniform non-degeneracy Subgradient \mathcal{O}(\log^{2}T) No ( \mathcal{O}(1) ) This paper Bounded, continuous support, quadratic growth Subgradient {\mathcal{O}(T^{1/3})} No ( \mathcal{O}(\log T) ) This paper Bounded, finite support, sharpness Subgradient {\mathcal{O}(\log T)} No ( \mathcal{O}(1) ) This paper Bounded, \gamma -dual error bound, unique solution Subgradient {\mathcal{O}(T^{\frac{\gamma-1}{2\gamma-1}}\log T)} Unknown Related Literature. There is a vast amount of literature on OLP [ 23 , 25 , 24 , 2 ] , and we review some recent developments that go beyond \mathcal{O}(\sqrt{T}) regret in the stochastic input setting ( Table 1 ). These algorithms mostly follow the same principle of making decisions based on the learned information: learning and decision-making are closely coupled with each other. We refer the interested readers to [ 3 ] for a more detailed review of OLP and relevant problems. LP-based OLP Algorithms. Most LP-based methods leverage the dual

Read the complete text