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

arXiv: https://arxiv.org/abs/2501.02761 · HTML: https://mlsanity.com/paper/2501.02761/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 33 references that are in the map.
- First posted on arXiv 6 Jan 2025.

## Builds on (most cited first, 19 of 19)

- [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020)
- [Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods](https://mlsanity.com/paper/2312.08531/) (2023)
- [Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds](https://mlsanity.com/paper/1909.05499/) (2019)
- [Simple and Fast Algorithm for Binary Integer and Online Linear Programming](https://mlsanity.com/paper/2003.02513/) (2020)
- [Uniformly bounded regret in the multi-secretary problem](https://mlsanity.com/paper/1710.07719/) (2017)
- [Primal Beats Dual on Online Packing LPs in the Random-Order Model](https://mlsanity.com/paper/1311.2578/) (2013)
- [RSG: Beating Subgradient Method without Smoothness and Strong Convexity](https://mlsanity.com/paper/1512.03107/) (2015)
- [An Improved Analysis of LP-based Control for Revenue Management](https://mlsanity.com/paper/2101.11092/) (2021)
- [Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions](https://mlsanity.com/paper/2210.07996/) (2022)
- [Near-Optimal Primal-Dual Algorithms for Quantity-Based Network Revenue Management](https://mlsanity.com/paper/2011.06327/) (2020)
- [Joint Online Learning and Decision-making via Dual Mirror Descent](https://mlsanity.com/paper/2104.09750/) (2021)
- [Optimal Regularized Online Allocation by Adaptive Re-Solving](https://mlsanity.com/paper/2209.00399/) (2022)
- [Infrequent Resolving Algorithm for Online Linear Programming](https://mlsanity.com/paper/2408.00465/) (2024)
- [Faster Subgradient Methods for Functions with H"olderian Growth](https://mlsanity.com/paper/1704.00196/) (2017)
- [Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-dependent Competitive Ratios](https://mlsanity.com/paper/1905.04770/) (2019)
- [Solving Linear Programs with Fast Online Learning Algorithms](https://mlsanity.com/paper/2107.03570/) (2021)
- [Decoupling Learning and Decision-Making: Breaking the O(√T) Barrier in Online Resource Allocation with First-Order Methods](https://mlsanity.com/paper/2402.07108/) (2024)
- [Online Linear Programming with Batching](https://mlsanity.com/paper/2408.00310/) (2024)
- [Wait-Less Offline Tuning and Re-solving for Online Decision Making](https://mlsanity.com/paper/2412.09594/) (2024)

## Built on by (most cited first, 4 of 4)

- [Online Resource Allocation with Continuous Random Consumption: Regret under Degeneracy](https://mlsanity.com/paper/2607.02196/) (2026)
- [Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates](https://mlsanity.com/paper/2607.02150/) (2026)
- [A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret](https://mlsanity.com/paper/2609.05895/) (2026)
- [Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving](https://mlsanity.com/paper/2609.28263/) (2026)

## Abstract (arXiv)

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 (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 O ( √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 ) regret in the continuous support setting and 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.